JPH02159682A - Template matching system - Google Patents

Abstract

PURPOSE:To reduce the frequency of calculation in a lower level and to reduce the whole frequency of calculation by detecting a position supposed to include a pattern based upon a threshold at a retrieval stage in an upper level, and executing the retrieval of the lower level at the detected position. CONSTITUTION:In the case of calculating mutual correlation values in accordance with the size of a template 3, an interval between the template 3 and a picture element 2 to be calculated on an input image 1 coated with the template 3 is hierarchied into several levels, correlation values are calculated at a rough position interval successively from a level having the small number of picture elements to be calculated, and at the time of detecting a high position, the level is successively dropped to find out the position of the maximum correlation value. Consequently, the frequency of operation in the lower level can be reduced and the whole frequency of operation can be also reduced.

Description

[Detailed Description of the Invention] [Industrial Application Field] The present invention relates to a template matching method using images, and in particular, a pattern position detection method that enables high-speed recognition and is more resistant to the effects of illumination and noise than binary image processing. Regarding the method.

[Conventional technology]

Conventionally, template matching in a position detection method using a template involves translating a template based on a gray scale image pixel by pixel with respect to the detection target screen, and calculating a cross-correlation value for the range covered by the template.
The position of the pattern is determined by finding the point with the largest value.

The cross-correlation value is defined as 9th order.

Now, the input image l is Fij (where i=1.N; J-
1, M). Here, i=l, N is a pixel identification subscript in the horizontal direction,
j=1. M is a pixel identification subscript from the top to the bottom of the screen. The template is.

Suppose that it is composed of pixels Tij (where i=1.n; j=1.m). The cross-correlation value rij is expressed by a quadratic equation when the upper left positions of the five partial images (images covered by the template on the human image) are i and j.

(ΣF0)) ・ ・ ・ (1) However, S2 nm Σ=ΣΣ 1 Shukuden 1161 p-1+ (k-1) q-j+ (j!-1) Calculated value regarding only the template image value (ΣT,,Σ
T-, etc.) can be treated as a constant value because it is calculated in advance.

This cross-correlation value rlj takes a value in the range of -1≦riJ≦1, and when rij≦O, the value 1 indicates that the template and the input image are completely the same.

Indicates that there is no relationship between the two images.

In normal template matching, the template is moved pixel by pixel relative to the input image.

Calculate the correlation value given by formula (1), and calculate the value to a certain value (the correlation value indicates how much it correlates with the template, so in order to recognize the pattern,
Judgment is made based on whether the value is above a certain threshold. ), and the position where the maximum value is reached is detected as the position where the pattern exists. The amount of calculation in this case is: ■ If the amount of calculation per pixel is 1, the number of places that can be moved is (N-m+1) to calculate one cross-correlation value (nXm).
)X(M-m+1), so the total amount of calculation is:

((nXm)X (N-n+1)X (M-m+1)・
...(2) becomes.

[Problem to be solved by the invention]

In this traditional template matching method.

Compared to the binarization method, it is more resistant to the effects of lighting and noise, but the problem is that the amount of calculation increases depending on the size and range of the template, making it impossible to detect the position of the pattern at high speed. SUMMARY OF THE INVENTION An object of the present invention is to provide a high-speed template matching method that solves this problem and requires fewer calculations.

[Means to solve the problem]

In order to solve the above problem, the present invention hierarchizes the interval between the template and the calculation target pixels of the input image covered by the template when calculating the cross-correlation value into several levels depending on the size of the template.

For each level, set the threshold value in advance for the conditions that allow you to go to the lower level, and first calculate the correlation value at coarse position intervals starting from the level with the fewest pixels to be calculated (the highest level). If you find a position that is above the threshold and has a higher value than the surroundings.

Compute its location and its neighborhood at a lower level,
The level is lowered one after another, and finally the position of the maximum correlation value at the lowest level (in units of one pixel) is determined.

[Effect]

According to the present invention, the locations where a pattern is likely to exist are first found at coarse position intervals using a threshold value, and the locations are searched one after another at lower levels, so the number of calculations at lower levels is reduced, and the overall The number of calculations is also reduced. Compared to the conventional method of calculating cross-correlation values by shifting one pixel at a time, the number of calculations can be significantly reduced and speed can be increased. (However, this degree changes depending on the size of the template and the size of the image to be recognized.) [Example] An example of the present invention will be described using the drawings.

1 and 2 are detailed explanatory views of the present invention, respectively.

The image to be used in this embodiment is an image scanned by the rask scan method, as shown in FIG. In FIG. 1, a partial image 2 having the same size as a template 3 is cut out from an input image l, and a cross-correlation value is calculated for the template 3 and each corresponding pixel. It is assumed that this value corresponds to the upper left position of the cut out partial image 2.

As shown in FIG. 1, the template 3 is a partial image obtained by cutting out an arbitrary part from the manual image 4 for template extraction.

First, a partial image of the input image 4 for template extraction is cut out and stored in a template memory.

Use as a template. At this time, first, set the template hierarchy level and set the threshold for each level.
Regarding the setting of the layering level of the template, if the number of pixels in either the vertical or horizontal direction of the template, whichever is longer, is tp, (as shown in Figure 2, the size of the template is nX
If m is 02m, then tp=n. ) t p / 2 L *-1≦A
...(3).

A is the maximum number of pixels among the number of calculation target pixels in the vertical direction and the number in the horizontal direction at the maximum level number Lm, and it is necessary to set an appropriate value. here.

Template size is 100x100 pixels.

If A=16, Lm=4. FIGS. 3 to 6 are diagrams showing positions and calculation target pixels for calculating cross-correlation values at each level, respectively.

As for setting the threshold value at each level, level 3
Similarly, the pixel to be calculated is set to the highest value of the 4 bell 3 threshold values. Level 2. Similarly, for level 1, cross-correlation values are calculated within eight neighborhoods of 2 pixels each and 1 pixel interval.

(Figure 5.

The threshold value of each level (Figure 6 shows the case of level 2.1) is a measure of whether or not to search at a lower level at each level.

The threshold value actually used is the threshold value obtained so far multiplied by an appropriate coefficient and used as the threshold value for each level. The coefficient used is approximately 0.8 to 0.9. In this way, the threshold value is set appropriately. The threshold value is very important; if this value is too low, the number of calculations will increase significantly.

Moreover, if it is too high, the pattern cannot be detected.

Below, the final threshold value of each level 4, 3, 2.1 is t
11a+t 113. t 111+ t hl
shall be.

FIG. 7 is a diagram illustrating in detail the template matching method of the present invention. First, at level 4, two
'+1i 1 pixel interval (the cross-correlation value is calculated every 177 pixels. The pixels used to calculate the correlation value at level 4 are the calculation target pixels at level 4, 24-1 pixel interval (8! pixel interval) ). This is the same for other levels. Then, if the correlation value rij becomes larger than the threshold value th at a certain IF (i, J), then 2' at that position
-'i! Eight neighboring positions of j prime interval (8m! prime interval) (
l-8,j-8) (1-8,J) (1-8,l
+8) (i, J-8) (1, l+8) (N+8°J-8
)018. J) Calculate the correlation value at level 4 using (l+8.J+s). The desired position is (N+3.j
3), the position (i, j) has the highest value at level 4 because the correlation value is higher nearer to the position. If other positions are high,
The cross-correlation value is calculated for the positions that have not been calculated in the vicinity of that position, and the position whose value is higher than the threshold value and higher than the eight surrounding neighbors is found (.Next, if this position is found, the level One level lower, the search will be at level 3.

At level 3, (i, J) and eight neighboring positions (1-4, j-4) (i-4, j) (i-4,
l+4)(i,j 4)(i,l+4)(l+4゜j
-4) (l+4.N (l+4.l+4). Here, (++4.j 4) is the threshold (!
! It is larger than thz and is the largest among the nine.

Next, to check whether the value of (++4.j-4) is larger than its surroundings, we calculate the uncalculated positions of its eight neighbors (i, J-8) (i-1-4, J-8) N
+8. j-8) (1+8. J-4) (
1+8. Calculate the 5 locations of j) and find the position with the highest value between these values and the value at (l+4.3-4).Since (l+4.J 4) was found at level 3, it is is a level 2 search. if.

At this level 3, if all the values are smaller than the threshold value th, the process returns to level 4 and the next digit 1 (++11.3) is calculated.

Note that B is a portion where the template and the partial image overlap when the calculated position is (i, j).

At level 2, as in level 3, (1+4.j-4) and eight neighboring positions (l+2.J-6) (1+2.J-4)
(l+2゜J-2) (l+4.J-6) (1-)-4
, J~2)(1+6.j-6)(N+6.j-4)(1
+6°j-2). Then, the four positions of the first order (1+2. j-4) (1+2. j-2)
(1+4゜j-4) N+4. j-2) will take the maximum value above the threshold th. This is determined in the same way as done for level 3. If a position equal to or higher than the threshold value is not found at this level, the process returns to level 4 in the same way as level 3.

If the position of (l+2.j-2) is found at level 2, the first order will be a search at level 1.

At level 1, as before, (l+2.j-2) and its eight neighboring positions (N+1.j-3) (i+l, j-2) (N+
1゜j-1)(l+2.j-3)(l+2,j-1)(
++3. j-3) (N+3.j-2)(N+3゜j-1
) Calculate the correlation value of . Then, (N+3.j-3)
is the maximum value when it is equal to or greater than the threshold value Lh. and,
Make sure that this position is greater than the eight surrounding neighbors,
Find the position of this pattern.

If there is no place where the value is equal to or higher than the threshold value th+ at level 1, the process returns to level 4 in the same way as level 3.

In this way, the position of the pattern is detected, but it is assumed that it is known in advance that there is only one pattern in the human image in which the pattern is to be detected that has a correlation value greater than the threshold value. For example, template matching ends when the search at level 1 ends. However, if there is a similar pattern in the input image, even after completing the search at level 1, the system continues to return to the upper level and searches for pattern positions with higher correlation values for unsearched locations. There is a need.

FIG. 8 is a diagram showing a specific example of a circuit for implementing the present invention. The A/D converted image signal.

It passes through multiplexer 103 and is stored in input image memory 92 . At this time, the address of the input image memory 92 is supplied from the image storage address generation circuit 96. A template is obtained by transferring a certain rectangular area portion of this input image memory 92 to the template memo 1J93. C.P.
U91 reads the template memory 93 and obtains a constant value (ΣT.

ΣT") is calculated. Then, the CPU 91 calculates.

The start, interval, and end of the address are given to the address generation circuits 94 and 95, and the human image memory 92. Each address of the template memory 93 is generated and the data of the two memories are read out, and the product-sum calculator 97 calculates the sum of the input image data, ΣF, and the product-sum calculator 98 calculates the sum of the squares of the input image data, ΣF2 product. A sum calculator 99 calculates the sum ΣT-F of the products of the input image data and the template data by performing parallel processing. The CPU 91 reads data from the product-sum calculator, calculates a correlation value between the template and the input image from which the template has been cut out, and determines a threshold value.

Next, the search image is imported into a human image, and the data for calculating the correlation value as described above is input to the sum-of-products calculator 97.9.
8.99, and the CPU 91 calculates the correlation value.

FIG. 9 is a flowchart showing the template matching method of the present invention.

〔Effect of the invention〕

As explained above, in this method, a place where a pattern is likely to exist is found based on the threshold value in the search stage at the upper level, and the lower level search is performed at that position, so the number of calculations at the lower level is , and the overall number of calculations is considerably reduced.

Now, the size of the template is 100 x 100 pixels, and the size of the input image is 512 x 480 pixels.

If A = 16, the line is moved pixel by pixel. In the conventional method, it is calculated using equation (2), and the total number of calculations = (100x
100)x (512-100+t)X (480-1
00+1) = 157353xlO' times.

On the other hand, in the method of the present invention, the number of calculations for each level is as follows. (Division of an integer results in a rounded down integer.) Number of calculations at level 4 = (100/8xlOO/8) X [(512-100+1)/17X (480-1
00+1)/17+N41 =76032+144・N4 Number of calculations at level 3 = (100/4X100/4)XN3 -625・N3 Number of calculations at level 2 = (100/2x 100/2) xN2=2500
・N2 Number of calculations at level 1 = (100X100)XNI =10000・N1 Therefore, total number of calculations +144・N4+625・N3+2500・N2+10
000·Nl, where N4. N3. N2. If Nl≧O and searching for completely uncorrelated images, N4=N3=N2=N
1=O.

If we consider the case where the optimal search is performed (the search in the lower order occurs only once), N4-8+5=13 N5=9+5=14 N2=9+5=1 4 Nl-9+5=14 Next door.

The total number of calculations = 261.654 times, which is about 1/6000 of the conventional method.

But actually, the template image, the input image.

Then, depending on the setting of the threshold value, etc., the number of times at the upper level increases, and becomes about 1/1000th of the number of times of the conventional method.

Position detection using template matching for grayscale images is more resistant to changes in illumination and noise than position detection for patterns in binary images, but the problem is that it requires a huge number of calculations and is too slow. However, in the method of the present invention, the number of calculations can be significantly reduced in most cases compared to the conventional method, and template matching can be performed at high speed.

[Brief explanation of the drawing]

1 and 2 are diagrams respectively explaining in detail the template matching method of the embodiment of the present invention, FIG. 8 is a diagram showing a specific example of a circuit for implementing the present invention, and FIG. is a flowchart representing the template matching method of the present invention. l... Input image 2... Partial image 3... Template 4... Input image for template extraction 91...
... CPL) 92 ... Input image memory 93 ... Template memory 94.95 ... Address generation circuit 96 ...
・・Image storage address generation circuit 97.98.99・・
. . . Product-sum calculation unit lOO~102.107-110 . . . Buffer gate 103.104 . . . Multiplexer 105.
...D/A converter 1st patent applicant Yaskawa Electric Manufacturing Co., Ltd. Figure 4 (Figure 5 Figure c Level 3) Engraving of the Figure drawing (no changes to the content)゛No. 1986 Patent Application No. 315356 Name of the invention Template Matching method Person making the amendment Relationship with the case Patent applicant First application form As shown in the engraving attached to the attached drawing (no changes in content)

Claims (1)

[Claims] 1. In a pattern recognition method that captures an image from a camera, A/D converts it, stores it in an image memory, processes the data of the input image stored in the image memory, and recognizes a pattern. , a grayscale image template of n pixels in the vertical direction and m pixels in the horizontal direction (n and m are natural numbers) is defined, and the input image and the corresponding range are defined for the input image stored in the image memory with respect to the range covered by the template. A template matching method characterized by searching for the location of a recognition target by finding a cross-correlation value with a template and finding the location where the value is the highest above a predetermined threshold. 2. Depending on the size of the template, the interval between pixels to be calculated when calculating the cross-correlation value is hierarchically divided into several levels, and the threshold value of the correlation value is set in advance for each level. A template matching method is characterized in that it consists of the following steps [1] to [5] from the highest level to the next lower level. [1] At the level with the largest pixel interval of level number Lm, scan the input image by moving the template parallel to the required screen by 2^L^m+1 pixels,
Regarding the range covered by the template, 2^L^m-
The cross-correlation is calculated at a pixel interval of 1, and it is determined whether the value is greater than or equal to a set threshold value. If it is less than the threshold, go to calculation of the next position; if it is more than the threshold, go to [2]. [2] Calculate the cross-correlation values at eight neighboring positions with an interval of 2^L^m-1 pixels around that position, and if there is a place where the value is greater than the center value, then use that position as the center. Calculate the values of the positions of the eight surrounding neighbors, find the position where the center value is larger than the eight neighbors, and go to [3]. [3] If the current level number L is 1, the current position is the location of the recognition target, and if the level is not 1 [4]
go to [4] At that position, lower the level number by one and calculate the cross-correlation values at that position and at eight neighboring positions at 2^L^m-1 pixel intervals around that position. If all values are less than the threshold for that level, set the level to the maximum level number and return to [1]. Otherwise, go to [5]. [5] Set the largest value as the current position, calculate the values of the eight neighboring positions around that position, and find the position with a value larger than the value of the current position. Eight neighbors of the current position. If there are no high values, go to [3]. 3. At each level, shift the position of the template by one pixel to the eight neighboring pixel intervals of that level, calculate the cross-correlation value at the pixel interval of that level, and set the smallest value of those eight values to that level. 3. The template matching method according to claim 1, wherein the threshold value of each level is determined by multiplying this value by an appropriate coefficient.