JP2004362186A - Template matching method and apparatus - Google Patents

Abstract

A method and an apparatus capable of speeding up template matching using pyramid structure data are provided.
A matching operation between a low-resolution image of an object and a template image thereof is started (state A), and when a predetermined matching result is obtained (state C), a high-resolution image 11b is obtained. And the template 11b 'is started, and both matching operations are performed in parallel to perform template matching (state D). In such a configuration, when a correlation value equal to or more than a predetermined value is obtained in matching at a lower hierarchical level for an image with a lower resolution and matching is successful, matching at a higher resolution is performed for an image with a higher resolution while continuing matching at the hierarchical level. Can be performed in parallel, and template matching can be performed at a higher speed as compared with waiting for the end of matching in a lower layer and starting matching in an upper layer.
[Selection diagram] Fig. 4

Description

[0001]
TECHNICAL FIELD OF THE INVENTION
The present invention provides a template matching method and apparatus, and more particularly, a pyramid that performs template matching of a low-resolution image and a high-resolution image of an object using a low-resolution image template and a high-resolution image template, respectively. The present invention relates to a template matching method and apparatus using structure data.
[0002]
[Prior art]
2. Description of the Related Art Conventionally, there has been known a component mounter that sucks a component supplied from a feeder by a head unit and mounts the component on a predetermined substrate. In such a component mounter, the picked-up component is photographed with a CCD camera, and the image is processed to recognize the position (posture) of the component, correct the component position, and mount the component, thereby improving the mounting accuracy. Let me. For such component recognition, the template image (component reference image) is shifted by one pixel with respect to the entire captured image in order to know the position of the component image in the captured image. Meanwhile, there is known template matching in which a correlation value of a corresponding region between a template image and a captured image is calculated and matching is performed.
[0003]
Such a template matching requires an enormous amount of calculation and a large amount of processing time. Therefore, a template matching method using pyramid structure data is known as a method for speeding up the processing. In this method, a captured image and a template image are reduced, a rough matching position is obtained by performing template matching between the reduced images, and then the matching position obtained in the previous process is sequentially reduced while sequentially reducing the reduction ratio. Performs detailed template matching within an area limited to the vicinity of the original image.For example, a plurality of images with different resolutions lower than the original image are prepared, and the image with the lowest resolution is used as a template image. By matching, find a plurality of candidate points having a matching degree equal to or more than a predetermined threshold value, and then match the vicinity of the previous candidate point with an image having the second lowest resolution, and here again, Find multiple candidate points, repeat this, and finally match the candidate points in the original image and map the point with the highest matching score. It is a bridging result (Patent Document 1).
[0004]
[Patent Document 1]
JP-A-10-21389 (Claim 1)
[0005]
[Problems to be solved by the invention]
However, in the conventional template matching method using the pyramid structure data, since there is only one matching operation module, if the entire image is not matched with one image, a candidate for the next highest resolution image is obtained. There was a problem that the speed could not be increased because a point could not be found.
[0006]
The present invention has been made to solve such a problem, and an object of the present invention is to provide a template matching method and apparatus capable of speeding up template matching using pyramid structure data with a simple configuration. And
[0007]
[Means for Solving the Problems]
The present invention has been made in order to solve the above problems.
In a template matching method for performing template matching of a low-resolution image and a high-resolution image of an object using a low-resolution image template and a high-resolution image template, respectively,
Start matching operation with low resolution image template,
When a predetermined matching operation result is obtained from the matching operation, the matching operation using the high-resolution image template is started, and then both the matching operations using the low-resolution image template and the high-resolution image template are performed in parallel. A configuration that performs template matching is adopted.
[0008]
In the present invention,
In a template matching device that performs template matching using a low-resolution image template and a high-resolution image template for a low-resolution image and a high-resolution image of an object,
A low-resolution image matching calculation unit that performs a matching calculation using the low-resolution image template;
A high-resolution image matching operation unit that performs a matching operation using the high-resolution image template;
When a predetermined matching operation result is obtained from the matching operation by the low-resolution image matching operation unit, the high-resolution image matching operation unit is activated, and both the matching operations by the low-resolution image template and the high-resolution image template are performed. , A matching control means for controlling the low-resolution image matching calculation means and the high-resolution image matching calculation means is adopted.
[0009]
In such a configuration, if matching for a low-resolution image succeeds, matching for a higher-resolution image is performed in parallel while continuing the matching, so that template matching using pyramid structure data is accelerated. It is possible to do.
[0010]
BEST MODE FOR CARRYING OUT THE INVENTION
Hereinafter, the present invention will be described in detail based on embodiments shown in the drawings.
[0011]
FIG. 1 illustrates an image recognition circuit 12 that captures an image of an object 11 with a CCD camera 10 and recognizes an image of the object. The target object 11 is, for example, an electronic component supplied from a component supply device and mounted on a substrate by a component mounter, but is not limited to such an electronic component, and is assembled in a factory assembly or inspection process, or It also includes general objects such as parts to be inspected, such as objects that are photographed by a camera or the like and whose position is recognized.
[0012]
The image recognition circuit 12 includes an image compression circuit 17 for compressing an image of the object captured by the CCD camera 10, an image memory 13 for storing the image of the object 11 and the compressed image, and a template serving as a reference image of the object. It comprises a template memory 14 for storing images, a matching operation module (matching operation means) 15 for performing a matching operation based on the template, and a matching controller (matching control means) 16 for controlling the matching operation module 15.
[0013]
A detailed configuration of the image recognition circuit 12 is shown in FIG. 2. In the present invention, template matching using pyramid structure data is performed, so that an image of an object captured by the camera 10 is used by the image compression circuit 17. Then, compressed images of, for example, 1/4 and 1/16 are formed and stored in the image memory 13. For this purpose, the image memory 13 stores an original image (uncompressed image) of the object input from the camera 10 and an image having a lower resolution than the original image compressed to 1/4 in area ratio. And an image memory 13c for storing an original image and an image having a lower resolution than the 1/4 compressed image and compressed to an area ratio of 1/16.
[0014]
The original image, the 1/4 compressed image, and the 1/16 compressed image become pyramid-structured data. Correspondingly, a template memory 14a for storing the template image of the original image, the template image of the original image is compressed to 1/4. And a template memory 14c for storing a template image obtained by compressing the template image of the original image to 1/16, and a matching operation module 15 for storing the template image in the original image. A matching operation module 15a that performs a matching operation on the 、 compressed image, a matching operation module 15b that performs a matching operation on the 圧 縮 compressed image, and a matching operation module 15c that performs a matching operation on the 1/16 compressed image are provided.
[0015]
The matching controller 16 outputs a matching command to each of the matching operation modules 15a to 15c, receives a matching result from each of the matching operation modules, and controls each of the matching operation modules. The matching calculation modules 15a to 15c perform a matching calculation with reference to the image memories 13a to 13c and the template memories 14a to 14c according to a calculation command from the matching controller 16, and return a calculation result to the matching controller 16.
[0016]
With such a configuration, the pyramid structure is hierarchized, and the image memory 13a, the template memory 14a, and the matching operation module 15a form the layer 1, and the image memory 13b, the template memory 14b, and the matching operation module 15b form the layer 2. The layer 3 is formed by the image memory 13c, the template memory 14c, and the matching operation module 15c.
[0017]
Hereinafter, how the matching using the pyramid structure data is performed in the configuration of the matching device illustrated in FIG. 2 will be described.
[0018]
In the following description, it is assumed that the matching controller 16 outputs a calculation command to the matching calculation modules 15a to 15c of each layer, when the matching in each layer 1 to 3 starts, until the matching range ends.
[0019]
As shown in FIG. 4, an original image 11a of the circular object 11 and an image 20a of a foreign substance such as dust are captured and stored in the image memory 13a. , 13c store the images 11b and 11c of the object and the images 20b and 20c of the foreign matter, which have been compressed to 1/4 and 1/16, respectively. It is also assumed that reference images (template images) 11a 'to 11c' corresponding to the respective compression ratios of the object 11 are stored in the template memories 14a to 14c.
[0020]
First, in step S1 of FIG. 3, the matching controller 16 outputs an instruction to the matching operation module 15c to start matching at the lowest resolution layer 3. As a result, matching between the lowest resolution image compressed to 1/16 stored in the image memory 13c and the low resolution image template (image) of 1/16 compression stored in the template memory 14c is performed. Is started, and the matching calculation using the template is started by the matching calculation module 15c.
[0021]
The template matching at the third layer is performed by performing the matching operation by moving the entire matching image frame 30 including the image 11c 'in the template memory 14c as the matching frame (template) 30 on the image memory 13c. Therefore, when the matching is started in step S1, as shown in the state A of FIG. 4, the matching frame is shifted from the state where the upper left corner of the matching frame 30 is set to the upper left corner of the image memory 13c to the right for each pixel. When the movement of the line is completed, the matching frame moves for each pixel along the next line, and the operation is repeated, and the matching operation ends when the matching frame moves to the end of the memory image. .
[0022]
Each time such a matching frame moves, the matching calculation module 15c performs a matching calculation between the template image 11c 'and the image 11c of the target object, and outputs a matching calculation result (correlation value). If the predetermined matching calculation result cannot be obtained, the determination in step S2 is denied, and the process proceeds to step S6. Here, since a predetermined matching calculation result has not been obtained yet, the determination in step S6 is denied, and the determination in step S8 is also denied, so that the matching calculation in the hierarchy 3 is continued. For example, since a predetermined correlation value cannot be obtained even when the image 20c of the foreign substance is scanned, the matching in the layer 3 is continued as in the state B.
[0023]
When the matching is advanced and the matching frame 30 advances to the center position and the template image 11c 'substantially matches the image 11c of the target object as shown in a state C in FIG. 4, the correlation value becomes smaller than a predetermined threshold value. As the result becomes larger and a predetermined matching calculation result is obtained, the determination in step S2 is affirmed. At this time, since the matching in the hierarchy 2 has not been performed yet, the determination in step S3 is denied, and the matching in the hierarchy 2 is started in step S4. This state is illustrated in state D of FIG.
[0024]
The position of the matching frame 30 '(corresponding to the entire image area of the template memory 14b and serving as a template in the hierarchy 2) at the start of the matching in the layer 2 is such that the upper left corner of the matching frame 30' is the upper left corner of the image memory 13b. Is set at a position advanced by a predetermined number of pixels and lines, instead of the initial position that coincides with. Specifically, a position returned by a predetermined number of pixels to the left and above the position of the matching frame 30 ′ corresponding to the position of the matching frame 30 in the state C in which the matching calculation result in the hierarchy 3 is equal to or more than a predetermined threshold value Is set to a position that does not return to the initial position (state D of hierarchy 2).
[0025]
From the state D, the matching controller 16 outputs a matching calculation command to the matching calculation module 15b in addition to the matching calculation module 15c (step S4), so that the low-resolution image template stored in the template memory 14c Both matching operations using the high-resolution image template stored in the template memory 14b are performed in parallel, and matching in layers 3 and 2 is performed in parallel. The flow of the matching in the layer 2 is illustrated by steps S11 to S18, and each step corresponds to the steps S1 to S18 in the layer 3.
[0026]
If the result of the matching operation on the layer 3 becomes greater than or equal to a predetermined threshold value while the matching is performed in parallel on the layers 3 and 2, the determinations in steps S2 and S3 are affirmed, and the matching is performed in step S5. The calculation result is saved. At this time, the matching controller 16 controls the matching calculation module 15c so as to suspend the matching in the hierarchy 3 until the matching calculation in the hierarchy 2 ends.
[0027]
When the matching in the layer 2 is completed, the matching operation module 15b becomes unused. At this time, since the result of the matching operation is stored, the determination in step S6 is affirmed, and the matching controller 16 returns to the matching operation module 15b again. An operation instruction is output, and the matching operation in layer 2 is restarted based on the stored matching operation result in layer 3, and the stored matching operation result is cleared (step S7). The matching restart position in this layer 2 depends on the saved matching operation result, and a predetermined number of pixels to the left of the matching frame 30 'corresponding to the position of the matching frame 30 when the predetermined matching operation result is obtained. At the position returned to the upper side, the position is set so as not to return to the matching start position of the first matching frame 30 '(the position of the matching frame 30' shown in the state D in FIG. 4). After that, the above-described parallel matching operation in layers 3 and 2 is performed.
[0028]
As described above, when the result of the matching operation at the lower resolution layer becomes equal to or higher than the predetermined threshold value again, the matching at the higher resolution layer is performed again, so that more reliable template matching can be performed.
[0029]
The matching relationship between the lowest resolution layer 3 (image compression ratio 1/16) and the next highest resolution layer 2 (image compression ratio 1/4) is as follows: layer 2 and higher resolution layer 1 (image compression ratio). This is the same as the relationship with the matching in the original image (compression ratio 1/1), and when a predetermined matching calculation result is obtained in the layer 2, the matching controller 16 also outputs a calculation command to the matching calculation module 15a. (Step S14), three matching operations in layers 3, 2, and 1 are performed in parallel. Further, when a predetermined matching calculation result is obtained again in the hierarchy 2, the matching in the hierarchy 1 is restarted based on the matching result in the hierarchy 2. The flow of the matching in the layer 1 is illustrated in FIG. 3 by steps S21 to S24.
[0030]
In layer 1, there is no higher-resolution layer, so the loop is repeated until the matching calculation result becomes equal to or greater than a predetermined threshold. In step S23, the matching calculation result is stored. If the matching calculation result exceeds a predetermined threshold value a plurality of times in the loop, the one having the highest correlation value among them is determined as the matching calculation result. Overwrite and save. Finally, the position of the template when the highest correlation value is obtained in the layer 1 is set as the position (area) where the imaged target exists.
[0031]
By controlling the plurality of matching calculation modules by the matching controller in this manner, it is possible to perform matching at the lowest resolution (3) and also perform matching at the higher hierarchy (2, 1) in parallel. Will be possible.
[0032]
In the above-described embodiment, the image compression ratio is three types of 1/1, 1/4, and 1/16, and has three layers. However, images having two or three or more types of compression ratios are generated. It is also possible to perform a matching operation at a plurality of hierarchies corresponding thereto. The matching controller 16 is constituted by, for example, a CPU, a DSP, or a circuit dedicated to a controller, and the matching operation modules 15a to 15c are similarly constituted by a CPU, a DSP, or a circuit dedicated to matching.
[0033]
In the above-described embodiment, each of the memories 13a to 13c and 14a to 14c is independently provided. However, if the memory access from the matching operation module is sufficiently faster than the processing of the matching operation module, FIG. As shown, one image memory 40 and one template memory 41 are provided, and the image memory 40 is subdivided into three to form image memories 40a to 40c for storing images for each of the first to third layers. The template memory 41 can also be divided into three, and used as template memories 41a to 41c for the respective layers 1 to 3. At this time, since there is only one bus that can access the memory, the bus controllers 43 and 44 that control the bus when a plurality of matching operation modules simultaneously access the memory are provided.
[0034]
With the configuration as shown in FIG. 5, it is possible to control the matching controller so that all the matching calculation modules are used for matching of one layer, and to speed up by sequentially executing the matching of each layer. It is.
[0035]
【The invention's effect】
As described above, in the present invention, matching at a lower layer for an image with a low resolution is started, and if a correlation value equal to or more than a predetermined value is obtained at that layer and matching is successful, matching at that layer is continued. In addition, matching at a higher layer for an image with a higher resolution can be performed in parallel, which is faster than starting matching at a higher layer after waiting for matching at a lower layer. Template matching becomes possible.
[Brief description of the drawings]
FIG. 1 is a block diagram showing a configuration of a template matching device.
FIG. 2 is a block diagram showing a detailed configuration of a template matching device.
FIG. 3 is a flowchart showing a flow of performing template matching using pyramid structure data.
FIG. 4 is an explanatory diagram showing a flow of performing template matching using pyramid structure data.
FIG. 5 is a block diagram showing a detailed configuration of another embodiment of the template matching apparatus.
[Explanation of symbols]
Reference Signs List 10 CCD camera 11 Object 13 Image memory 14 Template memory 15 Matching operation module 16 Matching controller

Claims (4)

In a template matching method for performing template matching of a low-resolution image and a high-resolution image of an object using a low-resolution image template and a high-resolution image template, respectively,
Start matching operation with low resolution image template,
When a predetermined matching operation result is obtained from the matching operation, the matching operation using the high-resolution image template is started, and then both the matching operations using the low-resolution image template and the high-resolution image template are performed in parallel. A template matching method characterized by performing template matching. When the matching calculation is performed in parallel and a predetermined matching calculation result is obtained from the matching calculation using the low-resolution image template, the matching calculation using the high-resolution image template is completed. 2. The template matching method according to claim 1, wherein the matching operation using the high-resolution image template is restarted based on the result. In a template matching device that performs template matching using a low-resolution image template and a high-resolution image template for a low-resolution image and a high-resolution image of an object,
A low-resolution image matching calculation unit that performs a matching calculation using the low-resolution image template;
A high-resolution image matching operation unit that performs a matching operation using the high-resolution image template;
When a predetermined matching operation result is obtained from the matching operation by the low-resolution image matching operation unit, the high-resolution image matching operation unit is activated, and both the matching operations by the low-resolution image template and the high-resolution image template are performed. Is performed in parallel, matching control means for controlling the low-resolution image matching calculation means and the high-resolution image matching calculation means,
A template matching device comprising: The matching control means performs the matching calculation using the high-resolution image template when the matching calculation is performed in parallel, and when a predetermined matching calculation result is obtained from the matching calculation using the low-resolution image template. 4. The template matching apparatus according to claim 3, wherein after completion, control is performed to restart the matching calculation using the high-resolution image template based on the matching calculation result.

Images