JPH0962838A - High-speed pattern matching method - Google Patents

Abstract

(57) Abstract: A method for realizing high-speed and high-accuracy pattern matching for images of all properties by reducing the amount of calculation as compared with the conventional one without losing the information of the input image. I will provide a. A reference image is divided into a plurality of templates, any one of them is selected as a reference template, and only the reference template is scanned on the inspection object image while the reference template and the inspection object at each scanning position are scanned. The correlation coefficient with the object image is calculated. Only when the correlation coefficient of the reference template is equal to or greater than a preset threshold value, the correlation coefficient is calculated for other templates, and when the correlation coefficients of all templates are equal to or greater than the threshold value, the position of the reference image at this time is set. It is stored as one of the candidates, and the presence / absence and the position of the inspection object are recognized based on the correlation coefficients of all the candidates after the scanning.

Description

Detailed Description of the Invention

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a pattern matching method suitable for high speed detection and positioning of an inspection object by pattern matching.

[0002]

2. Description of the Related Art Image processing technology has been widely used in recent years as a means for automating measurement and inspection. This is because image processing handles two-dimensional data, and therefore it is necessary to process a very large amount of data, but recent improvements in the processing speed of computers have made it possible to process a large amount of data in a short time. It is due to that. However, the resolution of the most accessible camera at present is 500 x 500
Although it is about pixels, even in this case, one screen consists of 250,000 huge pixels, so even if a relatively high-speed computer with a processing performance of 1 microsecond per pixel is used, It takes 0.25 seconds to process the pixel of. Actually, since the input time of image data and the output time of processed data are added to this,
The total processing time exceeds 0.25 seconds, which is a problem when processing a moving inspection object. Therefore, in order to perform high-speed image processing, it is essential to develop an image processing algorithm that can improve the performance of the computer and reduce the processing amount without impairing the reliability of the processing result. ing.

As a typical image processing algorithm, a method called pattern matching is known. In this method, the whole or part of the object to be found, that is, the reference image is stored in advance, and the same image area as the reference image is found from the image obtained by photographing the inspection object, that is, the inspection object image. .

Most of the conventional pattern matching methods are such that the characteristics of the reference image, for example, the size and center position of the bright area are calculated in advance, and an image close to this characteristic is searched for from the inspection target image. This method has been widely used because of its advantages such as high processing speed because the processing amount can be greatly reduced because it is replaced with a substitute characteristic called an image feature. However, this method has a drawback in that the detection ability is greatly affected by how the features of the reference image are selected, and therefore a practical inspection apparatus cannot be manufactured unless the engineer has extensive image processing experience.

Another method is to store the reference image as it is and search for the same image as the reference image from the inspection target image. The feature of this method called template matching is that you only need to register the reference image in advance.
After that, since the image processing apparatus automatically finds an image region close to the reference image from the inspection target image according to the set algorithm, almost no specialized knowledge is required. However, as will be described later, this method has a drawback that the processing time becomes very long because the amount of calculation becomes enormous.

Recently, the performance of computers has improved, and various techniques for speeding up template matching have been devised and partially put into practical use. As a template matching method, a method using a normalized correlation coefficient, which is said to have the highest recognition ability at present, will be described. The normalized correlation coefficient φ is expressed by the following equation (1).

[0007]

[Equation 1]

Here, T (i, j) is a template and F (i, j) is a value of each pixel of the input image. For example, the calculation of equation (1)
When using a template with a size of 50X50 pixels to perform a normalized correlation operation on an input image composed of 500X500 pixels, it is necessary to perform four arithmetic operations five billion times.
In this case, even if a 50MIPS high-speed arithmetic processor is used, it takes 250 seconds for calculation. As described above, the conventional template matching using the normalized correlation coefficient has a big problem that an enormous amount of time is required for the arithmetic processing in addition to the advantage that the image can be stably recognized even when the brightness of the image changes. There was not practical.

Therefore, in order to solve the problem of the arithmetic processing time, various methods for performing arithmetic processing at high speed have been devised. The most common and simplest method among them is to extract pixel data by thinning out pixel data from the input image at certain intervals, and perform a normalized correlation operation using the thinned out pixel data. is there. Since the calculation of the normalized correlation coefficient represented by the equation (1) is composed of the square term, this method called the decimation method can reduce the calculation time rapidly when the number of pixels to be calculated decreases. For example, if every four pixels are extracted, the amount of calculation is reduced to 1/16, and the calculation time is shortened.

Another method is disclosed in Japanese Patent Laid-Open No. 5-189.
According to Japanese Patent Laid-Open No. 570, a template, which is normally represented in two dimensions, is converted into two one-dimensional templates by adding pixel densities in each of two independent X-directions and Y-directions and converting the template into an input image. After performing the same conversion, the one-dimensional window is scanned, the one-dimensional similarity calculation is performed, and the similarities calculated by these two one-dimensional templates are combined to achieve high matching in both the X and Y directions. The accuracy is said to be obtained. In this method, the amount of normalized correlation calculation is reduced to the extent of one-dimensional calculation processing, so that the hardware can be realized with a small-scale circuit and the calculation time can be considerably shortened.

[0011]

However, in the former method, the extracted image has a lack of information as compared with the input image. Therefore, when the contour shape of the target image is complicated, There is a possibility that highly accurate matching may not be possible due to the lack of information. In the latter method, the pixel information is not lost as in the former method, but since the density addition cancels a slight density change, the density of the image suddenly changes. Such an image has a problem that high matching accuracy cannot be obtained.

An object of the present invention is to reduce the amount of calculation as compared with the conventional one in the pattern matching method using the normalized correlation calculation without losing the information of the input image, so that the density of the image changes rapidly. An object of the present invention is to provide a method for realizing high-speed and high-accuracy pattern matching for images of all properties including such images.

[0013]

In order to solve these problems, in the present invention, a reference image obtained by photographing an object to be a master is divided into a plurality of templates. While selecting any one of the reference templates and scanning only this reference template on the inspection object image obtained by photographing the inspection object, the similarity between the reference template and the inspection object image at each scanning position The normalized correlation calculation for calculating is performed and the correlation coefficient is sequentially calculated.

In the process of scanning, only when the calculated correlation coefficient of the reference template is equal to or more than a preset threshold value, even for templates other than the reference template, the template corresponding to the position of the reference template at this time is also used. Calculate the correlation coefficient at each position,
If the calculated correlation coefficients of all the templates are all equal to or greater than the threshold value, the positions of all the templates at this time, that is, the positions of the reference images are stored as one of the candidates for the position where the inspection object exists.

Then, when the reference template has completely scanned over the inspection object image, if there is no candidate, it is determined that there is no inspection object similar to the reference image, and there is one candidate. If there is only one, it is determined that the inspection object exists in this candidate, and if there are more than one candidate, the total value is calculated for the correlation coefficient of all templates calculated for each candidate. It is determined that the inspection object exists in the candidate having the maximum total value.

[0016]

DESCRIPTION OF THE PREFERRED EMBODIMENTS One embodiment of the present invention will be described with reference to the drawings. FIG. 1 is a schematic diagram of a position / orientation recognition system for a target object using an image processing apparatus to which the present invention is applied. The inspection object 4 is photographed by the camera 1, the image is taken into the image processing device 2, predetermined image processing is performed, and the determination result is displayed on the monitor 3. When applied to a robot system (not shown), the camera 1 is held at the tip of the robot arm, and the data after image processing is transmitted to the controller of the robot as an output signal from the image processing device 2 to obtain position data for controlling the robot. Correct the attitude data. In FIG. 1, a rectangular frame drawn around the inspection object displayed on the monitor 3 represents an image processing area called a window.

The processing flow of this embodiment will be described below. The term "(step **)" in the description is shown in FIG.
It corresponds to each processing step of the flowchart showing the processing flow of the template matching of the present invention shown in FIG.

First, the teaching of the reference image in the present invention will be described. Generally, in the process of teaching a reference image in template matching, a window shown on the monitor 3 shown in FIG. 1 is set for a master object, and image data of the master object is used as a reference image. It is stored in the storage device in the processing device.
In the present invention, the stored reference image is further divided into a plurality of small areas called templates, and the templates are stored in the storage device in the image processing apparatus (step 3).
2). As described above, in the present invention, image data obtained by photographing the entire master object is referred to as a reference image, and image data obtained by dividing the reference image into a plurality of small areas is referred to as a template. To do.

In the present embodiment, as shown in FIG. 2, the reference image is equally divided into four templates. In this case, the storage device in the image processing apparatus stores the image data of the four templates 1 to 4 as shown in FIG. It should be noted that in the present invention, the processing is performed centering on one template, so any one of the plurality of divided templates is set as the reference template which is the center of this processing. In this embodiment, the template 1 is set as the reference template.

Next, matching between the inspection object and the reference image in the present invention will be described. FIG. 4 shows an example of a monitor screen imaged of an actual inspection object. In addition, in the present invention, the image on the monitor screen obtained by photographing the inspection object is referred to as an inspection object image. In the matching between the reference image and the inspection object image, first, the template 1 set as the reference template and the inspection object image are matched. Specifically, the template 1 is placed at the upper left of the inspection object image (step 33), and the correlation coefficient is calculated by performing the calculation of the equation (1) between the template 1 and the inspection object image at this position ( Step 35). The correlation coefficient calculated here takes a value of 0 or more and 1 or less, where 0 is 0% matching and 1 is 100 matching.
Will represent%. Normally, due to a slight influence of noise or the like on the image, the correlation coefficient does not reach 1 even in the state where the template 1 and the inspection object image completely match. Generally, if the correlation coefficient is 0.9 or more, it means that the degree of coincidence is quite high.

Next, the calculated correlation coefficient of the template 1 is compared with a preset threshold value. As described above, the calculation of the correlation coefficient between the template and the image of the inspection object at an arbitrary position of the template and the comparison between the calculated correlation coefficient and the threshold are referred to as template matching in the present invention. As with the correlation coefficient, the threshold value is set to a value of 0 or more and 1 or less. However, as described above, the correlation coefficient does not reach 1 even when the template and the image of the inspection object completely match, and therefore, if the threshold value is set extremely high, there is no match. On the contrary, if the threshold value is set extremely low, many matching points will appear, and the processing time for judgment will be long. Therefore, the threshold setting depends on the nature of the inspection object. The value will be set appropriately.

In the comparison between the calculated correlation coefficient and the threshold value, if the correlation coefficient is less than or equal to the threshold value (step 36N),
It is determined that the image data of the inspection object corresponding to the image data of the template 1 does not exist at this position, the template 1 is shifted to the right by one pixel with respect to the input image (step 45), and the matching is performed again as described above. Is performed (step 35). The operation of shifting the template by one pixel in the matching process is called template scanning. There are various scanning methods, but in the most commonly used method, the template is first placed at the upper left of the inspection object image, and then the template is moved right by one pixel so that the template is the inspection object image. After reaching the right end of the, the template is returned to the left end of the inspection object image, further shifted by one pixel below, moved to the right again, and finally the template moves to the rightmost bottom of the inspection object image. Repeat this until.

On the other hand, if the correlation coefficient of the template 1 becomes larger than the threshold value during the scanning of the template 1 used as the reference template (step 36).
Y), templates other than the reference template, that is, templates 2 and subsequent templates are also matched. Here, since the relative position of the template other than the reference template to the reference template is determined at the stage when the reference image is divided into a plurality of templates, the template other than the reference template is scanned like the reference template. No need to
Matching may be performed only in the position of each template relative to the reference template (step 39).

That is, in this embodiment, since the reference image is divided as shown in FIG. 3, the relative position of the template 2 to the reference template (template 1) is to the right of the template 1. The template 2 is matched only at the position. Similarly, the matching is sequentially performed for the template 3 and the template 4. In this case, the template 3 is arranged under the template 1, and the template 4 is arranged under the template 1 on the lower right side, that is, on the right side of the template 3.

If the correlation coefficient is greater than or equal to the threshold value for all four templates, this position is counted as one of the candidates for the position where the inspection object exists, and is stored in the storage device in the image processing apparatus. (Step 43). Since there may be a plurality of candidates depending on the shape of the inspection object and the setting of the threshold value, normally, even if a candidate is found in the middle of the processing, the processing is further continued and all the candidates are extracted.

Then, when the scanning of the entire screen is completed, the position where the inspection object is present is determined from all the extracted candidates based on the correlation coefficient of each candidate. Specifically, when there are no candidates (step 46N),
It is determined that there is no inspection object similar to the reference image (step 48), and if there is only one candidate (step 46Y), it is determined that the inspection object exists in this candidate, and When there are a plurality of candidates (step 46Y), the total value of the correlation coefficients of all the templates calculated for each candidate is calculated, and the candidate having the maximum total value has the inspection object. (Step 47).

According to this embodiment, since the reference image is equally divided into four templates, the area of one template is 1/4 of that of the reference image. Equation (1)
As shown in, the calculation amount of the correlation coefficient is obtained by the square of the area of the template, and in this case, the calculation amount is 1 /
Since it is reduced to 16, the processing time required for calculating the correlation coefficient itself can be reduced to 1/16. Even if the processing time required for the determination including the calculation time for narrowing down the position where the inspection object exists is selected from among multiple existence candidates, the total processing time is compared with that for matching in all areas of the reference image. It is shortened to 1/10 or less.

As described above, according to the present embodiment, it is determined that the inspection object is present, though the processing time is significantly shortened as compared with the conventional matching for the entire area of the reference image. At all the positions, since all four templates generated by dividing the reference image have been matched,
The recognition accuracy is exactly the same as that obtained by performing matching on the entire area of the reference image.

As described above, in the present embodiment, the templates other than the reference template, that is, the templates of templates 2 to 4 are used only when the correlation coefficient of the template 1 as the reference template becomes larger than the threshold value. It is supposed to be matched, but 4
This position is stored as one of the candidates for the position where the inspection object exists only when the correlation coefficient is greater than or equal to the threshold value for all of the two templates. Therefore, even in the process of matching the templates 2 to 4, It is not necessary to perform matching on all of these templates. For example, when the correlation coefficient of this template 2 becomes smaller than the threshold value in the matching of template 2, this position is not a candidate for the position where the inspection object exists. Therefore, matching may not be performed on the remaining templates 3 and 4 (step 4).
1N).

In this way, when the number of divisions of the reference image is set to a large number, or when the threshold value is set low, the number of reference templates whose correlation coefficient is greater than or equal to the threshold value increases, other than the reference template. When the calculation amount of the template becomes large, unnecessary matching processing is eliminated, and the processing time can be further shortened.

In the present embodiment, the reference image is equally divided into four templates, but the present invention is not limited to this, and the number of divisions and the shape of the template may be set arbitrarily according to the usage form. However, with regard to the number of divisions, the more divisions there are, the more reliably candidates can be narrowed down, and as a result the recognition accuracy improves. However, if there are too many divisions, processing time will increase. It can be said that it is desirable to appropriately set a value according to the property of the object.

Further, in the present embodiment, the four correlation coefficients calculated for each candidate are summed up, and it is determined that the inspection object exists at the position of the candidate having the maximum total value. However, the present invention is not limited to this, and even if the average value of the four correlation coefficients calculated for each candidate is calculated and it is determined that the inspection target object exists at the position of the candidate having the maximum average value. Alternatively, the minimum value of the four correlation coefficients calculated for each candidate may be extracted, and it may be determined that the inspection target object exists at the position of the candidate having the maximum minimum value.

Further, in this embodiment, one threshold value is set for all the divided templates, but the present invention is not limited to this, and threshold values corresponding to each template may be set respectively. .

[0034]

As described above, according to the present invention, the taught reference image is divided into a plurality of templates, and one of them is arbitrarily selected.
Each template is selected as a reference template, and matching is first performed in this reference template, and at the position where the correlation coefficient is equal to or more than a preset threshold value, the remaining templates are also sequentially matched in the same manner. Therefore, the calculation of the correlation coefficient of the template for matching is mostly spent on the calculation of the correlation coefficient of the standard template, which is significantly slower than the conventional method that performs matching in the entire area of the reference image. Is shortened.

In addition, at the position where the inspection object is determined to exist, matching is eventually performed for all the templates, so that the result with exactly the same precision as when matching is performed for the entire area of the reference image is obtained. can get.

As described above, according to the present invention, the recognition accuracy can be maintained at the same level as the conventional method for performing matching in the entire area of the reference image, while the processing time can be greatly shortened. It has become possible to realize high-speed and high-precision pattern matching without missing or converting image information of the inspection object.

[Brief description of drawings]

FIG. 1 is a schematic diagram of a position / orientation recognition system for a target object using an image processing apparatus to which the present invention is applied.

FIG. 2 shows a case where a reference image is 4
This shows the one template divided equally.

FIG. 3 is a diagram illustrating a case where a divided 4 is used in an embodiment of the present invention.
It shows an example image of one template.

FIG. 4 is an example of a monitor image at the time of matching.

FIG. 5 is a flowchart showing a processing flow of template matching of the present invention.

[Explanation of symbols]

 2 Image processing device 4 Inspection object

Claims (1)

[Claims] 1. An inspection target image obtained by photographing an inspection target is scanned with a reference image stored in advance, and a normalized correlation operation for calculating the similarity between the two images is performed, and the normalization is performed. In the pattern matching method of the image processing device for extracting an image region similar to the reference image in the inspection object image based on the correlation coefficient of both images calculated by the generalized correlation calculation, the reference image has an arbitrary shape. Divided into a plurality of templates each having, and selecting any one of the plurality of templates as a reference template, and scanning only the reference template on the inspection object image while inspecting the reference template at each scanning position. Sequentially calculating the correlation coefficient with the object image, and only when the correlation coefficient is greater than or equal to a preset threshold value When the correlation coefficients are calculated and the calculated correlation coefficients of all the templates are all equal to or more than the threshold value, the positions of all the templates at this time, that is, the positions of the reference images are stored as candidates for the position where the inspection object exists. However, when the reference template finishes scanning all over the inspection object image, it is determined that the inspection object similar to the reference image does not exist when there is no candidate, and the candidate is When there is only one, it is determined that the inspection object exists in this candidate, and when there are a plurality of candidates, the total value of the correlation coefficients of all templates calculated for each candidate is calculated. A high-speed pattern matching method, characterized in that it is determined that the inspection object is present in the candidate having the maximum total value calculated.