JPS5842902B2 - Specific pattern extraction device - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION The present invention relates to an apparatus for extracting a specific pattern from a complex image and determining its position in the image.

Conventional specific pattern extraction devices convert video signals into processing targets (
(hereinafter referred to as the target pattern), one part of the pattern (hereinafter referred to as the partial pattern) is sequentially extracted, the degree of similarity with the standard pattern is examined, and if this is greater than a preset value, the extracted partial pattern is determined to be a specific pattern, At this time, most of the methods find the position of a partial pattern in the target pattern.

However, the above-mentioned method has a drawback in that the detection ability deteriorates even for minute changes in the shape of the target pattern.

A minute change in shape means, for example, when a circle has a specific pattern, it changes size or becomes an ellipse. This often occurs depending on the direction of image capture.

An object of the present invention is to detect a specific pattern such as a circle or an ellipse by focusing on the symmetry of the pattern, without using the standard pattern shown in the conventional example, and to find the position of the specific pattern extraction. The goal is to provide equipment.

In order to achieve this object, the basic configuration of the device of the present invention includes a first means for inputting a binarized and discretized video signal as a target pattern, and a predetermined two-dimensional partial pattern sequentially from the target pattern. a second means for extracting, a third means for determining the degree of point symmetry of the partial pattern, a fourth means for determining whether the partial pattern is similar to a specific pattern, and a second means for determining the point symmetry of the partial pattern; and a fifth means for determining the location of the specific pattern within.

Further, if necessary, a sixth means for determining the degree of similarity near the center between the partial pattern and the specific pattern, and a comprehensive judgment of the result of the sixth means and the result of the third means, determine whether the partial pattern is the specific pattern. The fourth step is to determine whether it is similar to
and the means of

a seventh means for determining the peripheral similarity between the partial pattern and the specific pattern, and combining the result of the seventh means, the result of the third means, and the result of the sixth means, as necessary. and fourth means for determining whether the partial pattern is similar to the specific pattern by comprehensive determination.

The target pattern is two-dimensionally discretized as shown in Figure 1, and each discretized picture element takes a logical binary value of "0" or "1", and is a specific pattern to be recognized or It contains other patterns.

Here, to simplify the explanation, the target pattern is usually “0”.
It is assumed that a specific pattern or other pattern exists in this pattern as "1".

Such a target pattern is, for example, a binary conversion method that converts time-series signals sequentially output from an imaging device such as a TV camera into "1" if the level exceeds a predetermined amount, and "0" if the level is less than a predetermined amount. This can be determined by performing the processing and discretization processing by periodic sampling on all video signals.

Here, the specific pattern is a pattern to be detected that is included in the target pattern.

In the case of the present invention, the condition is that the shape is point symmetrical, but the size and shape are not limited to one type, and for example, when a circle is used as a specific pattern, an ellipse is also included in this range. The size is also determined to include everything within a certain range.

The partial pattern is a group of picture element information obtained by cutting out a part of the target pattern two-dimensionally by the second means.

Regarding the concrete implementation method of the second means, please refer to the patent application filed in 1973.
Please refer to No. 92433 (Japanese Patent Publication No. 12492/1983) for details.

FIG. 2a shows an example of a partial pattern for detecting a circle or an ellipse, and shows the case of 10XIO picture elements.

In this way, the center point of the partial pattern is called the "reference point",
It is promised that the position of the partial pattern will be expressed based on this reference point.

Next, third, sixth, and seventh means for determining point symmetry and similarity for determining whether a partial pattern is a specific pattern will be explained.

1. A sixth means for determining the degree of similarity near the center of a partial pattern will be described.

This is the degree of similarity with a specific pattern in a "central region" set near a reference point, for example, the number of picture elements Ml of "1" or the number of picture elements M' of "0" in this central region. ).

Figure 2 shows the 2× in the partial pattern of Figure 2 a.
This is an example in which two picture elements are used as the central region.

Next, a seventh means for determining the degree of similarity around a partial pattern will be described.

This is the degree of similarity between a "peripheral area" set up around the reference point and a specific pattern in this surrounding area.For example, the number of picture elements "0" (N ').

Figure 2C shows 40 in the partial pattern of Figure 2A.
This is an example in which a picture element is a peripheral picture element.

The point symmetry used in the third means is the logarithm L (-I or unmatched picture element logarithm of matching picture elements obtained when comparing picture elements that have a point symmetry relationship with the reference point of the partial pattern as the origin). is a prime number L').

Here, we investigated the matching state over the entire partial pattern, but since ideally these regions can be said to have point symmetry when the state is determined in the central region and peripheral regions, we excluded these regions. The degree of point symmetry may be checked only in the area.

FIG. 2d is a point symmetry comparison area when FIG. 2a is used as a partial pattern.

Here, as further modified examples, FIGS. 3a, b, and c are shown.

List d.

This is a modification of FIG. 2a, b, c, and d, and has the advantage of reducing the size of the circuit.

Using the above similarity near the center, similarity around the periphery: point symmetry, a comprehensive judgment can be made by the fourth means, and the shape can be recognized.

For example, if the similarity M of the central region is a predetermined value M m in
The state near the center is determined based on whether the degree of similarity N in the surrounding area is smaller than a predetermined value N' max , and the state of the periphery is determined based on whether the degree of similarity N in the surrounding area is smaller than a predetermined value N' max . The state of point symmetry is determined based on whether or not it is smaller than max, and when all of the above three determination conditions are satisfied, the extracted partial pattern can be determined to be a specific pattern.

In addition, in the case of Mmin=4 in the example of FIG. The nearby state determination can also be said to be used to limit the minimum size of a specific pattern.

Similarly, in the case of N'm a x-〇, instead of finding N' by counting, the state of all picture elements is
It can be realized by a logic circuit that determines whether or not ", and this peripheral state determination can be said to be used to limit the maximum size of a specific pattern.

Note that the value of point symmetry L or L' can be used as a measure of how close the pattern is to the specific pattern.

That is, it is also possible to select the pattern with the minimum point symmetry L' and detect it as being close to a specific pattern.

The fifth means for determining the location of the specific pattern may be based on the coordinates of the reference point of the partial pattern that can be pressed to the target pattern based on the above results.

Below, a device and a circuit configuration for actually performing the above processing will be explained using specific examples.

Here, the specific pattern is a circular shape including an ellipse, and whether or not a partial pattern is similar to the specific pattern is determined comprehensively based on the degree of point symmetry, the state near the center, and the peripheral state. The shape of is a cross.

FIG. 4 is a basic circuit configuration block diagram, in which a time-series video signal 10 from an imaging device 1 such as a TV camera driven by a timing signal 18 output from a timing signal generation circuit 4 is processed by a binarization/sampling circuit. 2 becomes a binary signal 11 in pixel units that is discretized, and this sequentially sent pixel information is further processed by a partial pattern generation circuit 3 to convert one-dimensional time-series pixel information into a two-dimensional time-series pixel group. This becomes partial pattern information 12 of the information.

Both the binarization/sampling circuit 2 and the partial pattern generation circuit 3 are synchronized as a whole by a timing signal 18.

Using the partial pattern information 12 obtained in this way, the point pair recalculation circuit 5 calculates the number 13 of mismatched picture elements between point-symmetrical pixels in the partial pattern, and the center vicinity state calculation circuit 6 calculates the number of mismatched picture elements 13 between point-symmetric picture elements in the partial pattern. The number of "1" picture elements 14 in the region is determined, and the peripheral state calculating circuit 7 determines the number of "1" picture elements 15 in the peripheral region within the partial pattern.

These three results are determined by a specific pattern determining circuit 8, and a detection signal 16 indicating whether or not the partial pattern can become a specific pattern is obtained, as well as a degree of similarity 17 between the specific pattern at this time.

From the specific pattern detection signal 16, the similarity 17, and the partial pattern position signal 18, the position detection circuit 9Fc obtains a specific pattern position signal 19 indicating where the specific pattern exists in the target pattern.

The specific pattern detection signal 16 is the shape recognition result of the specific pattern, and the specific pattern position signal 19 is the position recognition result of the specific pattern.

Here, the processing time of the processing circuits 5, 6, 7, 8, and 9 is that all processing must be completed before the next partial pattern is sent, and the video signal is sampled at 6 MHz and the picture elements are When creating information, partial patterns are usually created at 6 MHz, and the total processing time is 167 MHz.
Click the button if it can be kept within ns.

Next, each block will be explained in more detail.

What is shown in FIG. 5 is a schematic representation of the imaging surface of the imaging device, and the timing signals 41 to 46 are expressed accordingly.

Of the timing signals, 41 and 42 are a horizontal sweep waveform and a vertical sweep waveform of the TV camera, which scan the imaging plane from left to right and from top to bottom.

Then, using 43 sampling pulses, it is discretized into the picture elements shown in the figure.

These 43 sampling pulses are further used as timing signals in the partial pattern generation circuit, and the operating principle of this partial pattern generation circuit is disclosed in the aforementioned Japanese Patent Application No. 46-92433 (Japanese Patent Publication No. 51-12).
No. 492).

The timing signal 44 is a pulse for initial setting, and is outputted once at the beginning for one imaging plane scan, and is used in the position detection circuit together with the horizontal coordinates 45 and the vertical coordinates 46.

As shown in FIG. 6, the point pair recalculation circuit 5 processes the intermediate area excluding the central area and the peripheral area in the partial pattern, and calculates the mismatch state between picture elements in a point symmetrical relationship by 12 (Exclusive OR game)
At this time, the result of "1" is sent to the counting circuit 52, and in the counting circuit, the exclusive OR gate 51 counts the output of "1" to obtain the number 13 of point-symmetric picture elements that do not match.

As shown in FIG. 7, the near-center state calculation circuit 6 processes the center area (here, the four central pixels) in the partial pattern, and calculates the number of pixels that are ``1''. 61
The number of "1" picture elements in the central area, 14, is determined by counting.

As shown in FIG. 8, the peripheral state calculation circuit 7 processes the peripheral area (in this case, eight peripheral pixels) in the partial pattern, and calculates the number of pixels that are '1''. 71 to find the number of "1" picture elements 15 in the surrounding area.

The specific pattern determination circuit 8, as shown in FIG.
This is a circuit that performs determination and detection of a specific pattern using the results of the three point symmetrical states, the near-center state, and the surrounding states.

A comparison circuit 81 determines whether the number 13 of point-symmetric picture elements that do not match is less than a predetermined value, a comparison circuit 82 determines whether the number 14 of "1" picture elements in the central area is greater than or equal to a predetermined value,
The comparison circuit 83 determines whether the number of picture elements 15 of "1" in the peripheral area is less than a predetermined value, and when the above three results are established, the AND gate 84 obtains the specific pattern detection signal 16, and The specific pattern similarity 17 at this time is obtained through the gate 85.

As shown in FIG. 10, the position detection circuit 9 uses the specific pattern detection signal 16 and the specific pattern similarity 17, and also uses the horizontal coordinate (or X coordinate) 45 shown in FIG. Vertical coordinate (or y coordinate)
46 and an initial state setting signal 44 to detect the position of a specific pattern existing in the target pattern.

91°92 is a memory circuit for storing the similarity and coordinates of the first detected specific pattern, and 92.93 is a memory circuit for storing the similarity and coordinates of the first detected specific pattern.
This is a storage circuit for storing the degree of similarity and coordinates of the specific pattern detected the th time, and the nth one is stored in the 95.96th storage circuit.

Here, the allowable number of specific patterns is n, but
A counter that counts the number of specific patterns is 97, and each time the counter pulse 104 comes, Ka, a2...
an changes from "0" to "1" K, and the AND gates 98 to 103 at which the signal a, ~an, which indicates the presence or absence of this specific pattern, is "1" are turned on, and the stored specific pattern is changed. The similarity of 19.1 to 195 and the coordinates 191' to 19a are output.

The initial state setting signal 44 contained in the counter 97 is a signal for clearing the contents of the counter.
The signals of ~an are all "0", which means that the specific pattern does not exist.

In addition, the exits b1 to bn of the counter are 1 to n when the 1st to nth specific pattern candidate points are sent for the first time.
A signal to be stored in the th storage circuit, which indicates the presence or absence of a specific pattern using a counter pulse.
Immediately before either force γO" changes to "1", a, ~
One pulse is output of any one of s to bn corresponding to an.

To explain the signals in terms of time flow, the initial state setting signal 44
a, ~an, b1~bn are cleared, and then when the counter pulse 104 comes, 1 pulse take is output, and a becomes "1" in level when the initial state setting signal 44 comes, and then When the counter pulse 104 comes, one pulse b2 is output and a2 also becomes "1" in level, and is output in order every time the counter pulse 104 comes.

Next, since all of the specific pattern determining circuits including n memory circuits perform processing operations equally and in parallel, only the first specific pattern determining circuit will be described.

The previous specific pattern similarity from the storage circuit 91 and the new specific pattern similarity 17 sent from the specific pattern detection circuit 8 are compared by the comparison circuit 105, and if the new specific pattern similarity 1T is small, it is updated. The output is "1" indicating that it is necessary.

Further, the pre-specific pattern coordinates from the storage circuit 92 and the (7) Already memorized 1
“1” is the same as the th specific pattern candidate.
The output is “.

If both 105 and 106 are "l", a signal indicating that the current specific pattern is in the same position as the first pattern and that the current specific pattern needs to be updated because its similarity is smaller is output. It is obtained by gate 107 and synchronized with specific pattern detection signal 16 from specific pattern detection circuit 8 and AND gate 108 .

If the specific pattern is not stored at all, naturally a1=0, so the AND gate 98°99 is turned off, so both the comparison circuits 105 and 106 are turned off, and the AND gate 108 is also turned off. , at this time, the gate 112 that detects that all the signals are "0" is turned on, and when the specific pattern detection signal 16 comes, it passes through the AND gate 113 and becomes a counter pulse 104, generating a memory pulse b.

This is superimposed by the OR gate 109 on the specific pattern update signal from the AND gate 108, and the new specific pattern similarity 17 and its coordinates 45 and 46 are stored in the storage circuits 98 and 99 through the AND gates 110 and 111, respectively. .

After b occurs, a1 becomes “1”, so 98°99
The 0 gate is opened, and when the next specific pattern candidate arrives, a comparison is made at 105 and 106.

As a result, if the distance is large due to 106, then 11
2 is turned on, the counter 97 is operated by the specific pattern detection signal 16, a second specific pattern setting signal b2 is generated, and the similarity and coordinates of the specific pattern are stored in the storage circuits 93 and 94.

In this way, as a final result, the similarity degrees and coordinates for the number of existing specific patterns are stored in the storage circuit, and (19,", 191") to (19).

191).

Counting circuit 52 used in the circuit of 5.6.7 in the above example
, 61, 71 are shown in FIG. 11, and a specific circuit example of the counter 97 used in the circuit 9 is shown in FIG.

The counting circuit is a circuit that counts the number of signal lines that are logically "1", and the one shown in Figure 11 counts the pulses of n signal valves P, ~Pn, which are the targets of counting. 203 to shift register 201, shift register 20
In 1, one gate of the AND gate 204 is selected while changing the location every time the shift pulse force is applied, and the signals P, ~Pn input to that gate are determined, and the OR gate 205
The counter 202 counts through the time.

When the shift register 201 receives n pulses and makes one cycle, the counter 202 counts the number of signals that are "1" among P and -Pn.

The counter 9T shown in FIG. 12 is configured by shift registers 210 and 211 that are reset by 44 and turn on signal lines in sequence by 104.

When the count pulse 104 comes, the shift register 21
0 operates and turns on the signals in order from the left.

This count pulse 104 is then delayed for 4 hours by the delay circuit 212, and then the shift register 2110 line corresponding to the dose line turned on in the shift register 210 is turned on, and specific pattern candidate presence signals a1 to an are output.

At this time, the signal line 210 is on and the signal line 211 is off is determined by the gate of 213, and the delay circuit 212
A pulse force having a width of delay time t is output as a specific pattern candidate setting pulse from one of .

As described above, according to the present invention, only a specific pattern is extracted from a complex target pattern, and the positions existing in the target pattern of multiple specific patterns are accurately determined as the closest position to the specific pattern. You can ask for it.

Here, the specific pattern has an allowable width without being limited to one type of size or shape under the condition of a point-symmetric shape, and it is determined by how to take the partial pattern, central area, peripheral area, and when detecting the specific pattern. The examples described here are not intended to limit or reduce the scope of the present invention, which is determined by the settings of Mmin, Nmax, and Lmax used.

[Brief explanation of drawings]

Figure 1 is an explanatory diagram showing the relationship between the target pattern, partial pattern, and specific pattern. Figures 2 and 3 are for recognizing whether the cut out partial pattern is a specific pattern (in the case of a circle). FIG. 4 is a configuration diagram of an embodiment of the present invention. FIG. 5 is an explanatory diagram showing the relationship between captured images and timing signals. FIGS. 6 to 12 are diagrams of the embodiment. FIG.

Claims (1)

[Claims] 1. A first means for obtaining a spatially discretized video signal representing a bright and dark state as a target pattern, and a second means for sequentially cutting out predetermined two-dimensional partial patterns from the target pattern. and a third means for determining the degree of similarity with the specific pattern from the degree of point symmetry of each partial pattern with respect to the reference point;
a fourth means for determining a partial pattern that is most similar to the specific pattern based on the degree of similarity; and a fifth means for outputting a position corresponding to a reference point of the determined partial pattern as an existing position of the specific pattern. A specific pattern extraction device comprising: 2. The third means includes a central region of the partial pattern;
2. The specific pattern extracting device according to claim 1, comprising means for determining the degree of similarity with the specific pattern in at least one of the intermediate region and the peripheral region.