JPH0664614B2 - Hierarchical structured template matching method - Google Patents

Description

The present invention relates to an image processing device, and more particularly to a hierarchical structured template matching method.

[Prior Art] Conventionally, as a matching method for a template [Template, so-called mask with a template], a template is used as an entire candidate point region in an input image (hereinafter, simply referred to as “image”). A method has been employed in which the degree of coincidence between the template and the image is calculated at a resolution of one pixel at each position while shifting the position by one pixel, and the position of the candidate point having the maximum degree of coincidence is obtained.

Here, the candidate point is a point serving as a reference of a position where the template is shifted, that is, moved to match the template.

As a prior art example, there is a template matching method disclosed in JP-A-60-200375.

In this prior art example, "In the template matching method in which a template is scanned for the input digital image pattern when recognizing a position to be recognized in the input digital image pattern, and the two are matched, the position is recognized. A small weight is given to the matching unit area near the boundary among the matching unit areas of, and a large weight is given to the matching unit area far from the boundary to form a template. It is a template matching method for matching.

Further, as a reference example, there is an image recognition method and apparatus disclosed in JP-A-61-34675.

The reference example is "in the image processing method, in which an image of an object is picked up by an image pickup device, the image is sent to an image recognition device for image processing, and position information is sent to a working tool based on position information from the image recognition device. A pattern in which an interference check region is arranged in one image arbitrarily selected from the images in the field of view of the image pickup device, and whether or not an image of another object interferes in this pattern If there is interference,
It is an image recognition method that searches repeatedly until an image of the object without interference is detected. "

[Problems to be solved by the invention]

However, in the conventional matching method, since the position of the candidate point that maximizes the degree of matching between the template and the image is obtained, when the template or the candidate point area is large, a huge number of pixel-to-pixel calculations are required.

For example, the target of matching is I as shown in FIG.
It is stored in the template 10 in the range of × J pixels, and the positional deviation of the matching target 30 is DX, X in the X and Y directions, respectively.
Consider the case where there are DY pixels.

If the position of the template on the image is represented by the upper left position of the template shown in FIG. 7, the candidate point area 71 in this case is a range of DX × DY pixels.

If the template 10 is shifted by one pixel over the entire candidate point area 71 in the range of DX × DY pixels, the template 10 and the target
You must take the procedure of finding the degree of agreement between the images 20 including 30.

As a measure of coincidence, Using, and counting'T (I, J) -F (I, J) 'as one pixel calculation, (I × J) × (DX × DY) times of pixel calculation is required.

Note that T (I, J) and F (I, J) are the density values of the template pixel and image pixel in (I, J).

Thus, the prior art example is a template matching method that can improve the detection accuracy by eliminating the influence of unstable elements existing at the boundary between the recognized pattern in the input digital image pattern and the background pattern, and its technical field is Although they are the same, the point of view and idea are completely different means.

Further, the reference example is merely an image recognition method capable of preventing interference between a tool such as a manipulator that operates based on position information and an object other than the object of this tool.

Here, the present invention overcomes the drawbacks of the conventional example and provides a hierarchical structural template matching method that executes template matching with a small number of pixel operations when the template or candidate point area is large. To that end.

[Means for solving problems]

As a means for solving the above problems, the present invention performs matching with a template image as a target input image in a plurality of stages, and further, for each stage, the size of the template image, the sampling rate, and the candidate. In the hierarchical structural floor template matching method in which the point region is gradually reduced, when the total number of stages is N and each stage from the first stage to the (N−1) th stage is represented as the Mth stage, In the first step, the target input image and the template image are matched at each position determined by the sampling rate 2 ^{N −1} in the given candidate point region, and the position at which the degree of coincidence is the maximum is matched. Is designated as the reference position for the matching in the second stage, and in each stage from the second stage to the (N-1) th stage, the reference position designated in the previous stage is designated. Is set as a candidate point area within a square area of ± 2 ^{N−M + 1} pixels, and matching is performed at each position determined by the sampling rate 2 ^N−M in this area, and the degree of coincidence at that time is the maximum. Is designated as a reference position for matching in the next stage, and in the Nth stage, matching is performed at all positions within a square region of ± 2 pixels centered on the reference position designated in the (N-1) th stage, The feature is that the position where the degree of coincidence at that time is maximum is determined as a true coincident point.

(Operation) In the above configuration, matching between the target input image and the template image is performed as follows.

In the first stage, 2 ^N within the predetermined candidate point area
^-1 matching the sampling rate for each pixel is performed, only the position where the maximum degree of coincidence is obtained is designated as a reference position in the second stage.

In each of the stages from the second stage to the (N-1) th stage, matching is performed only at the peripheral positions around the reference position designated in the previous stage, which is determined by the predetermined sampling rate in each stage. The position where the degree of coincidence at that time is maximum is designated as the reference position for matching in the next stage.

In this way, the range in which the true coincidence points are present is gradually narrowed down, and in the Nth stage, that is, the final stage, all positions within a square region of ± 2 pixels centered on the reference position specified in the previous stage. That is, matching is performed at 25 positions, and the position where the maximum degree of matching is obtained is determined to be the true matching point.

(Example) Hereinafter, an example of the present invention will be described with reference to FIGS. 1 to 5.

FIG. 3 is an explanatory view schematically showing the present invention, which corresponds to an image of the matching target 30 in the template 10,
A template area 31, a template area 32, a template area 33, a template area 34, ... Are set, but in FIG. 3, four template areas are provided.

That is, according to the present invention, template matching is divided into N (natural number) stages, the original image is stored in the template memory, and N template regions are I × J, (1/2) × (J X2), (I / 4) x (J / 4), (I / 8) x (J / 8), ... (I / 2 ^N-1 ) x (J / 2 ^N-1 ) pixel range (FIG. 3), there is no restriction on the relative positional relationship between template regions, and the template region number used in the Mth stage is M, 2 ^{N −} in each of the X and Y directions from the template region. Hierarchical structured template matching in which all the templates are composed of (I / 2 ^{N -1} ) × (J / 2 ^{N -1} ) pixels by using pixels sampled every ^M pixels as a template. Is the way.

In the following, as an example, description will be made by adopting the same one as described above as a measure of the degree of matching when performing the four-step template matching shown in FIG.

First, in the first stage, a template region of I × J pixels
31 is used and the candidate point area is the entire DX × DY pixel. Then, template matching is performed by setting the sampling rate of the template region and the image to one pixel in eight pixels in both the X and Y directions. The state of sampling is shown in FIG.

That is, each of the template area 31 and the image 20 (I /
8) × (J × 8) pixels, [(I + DX) / 8] × [(J +
DY) / 8] Compress to pixels and perform template matching.

As a result, the template region 31 can be positioned with an accuracy of 8 pixels.

In the first stage, the necessary pixel calculation is (I / 8) × (J × 8) pixels in the template region 31, and the number of candidate points (not shown) is (DX / 8) × (DY /
8) Therefore, [(I / 8) × (J / 8)] × [(DX / 8) × (DY /
8)] times. Note that 481, 482, 483, ... Are sampling points.

In the second stage, the template region 32 of (I / 2) × (J / 2) pixels is used, and the candidate point region is added to the position obtained in the first stage by adding the relative positional relationship between the template regions 31 and 32. It is set within a range of ± 8 pixels around the position. This is shown in FIG. 5 (a), and FIG. 5 (b) is an enlarged view of the candidate point region 52 at the second stage. Note that 51 is the maximum matching score in the first stage, and 521, 522, 523, ... 52n are candidate points, of which 52c is a candidate point at the center of the position where the relative positional relationship of the previous regions 31, 32 is added.

Then, template matching is performed with a sampling rate of 1 pixel for every 4 pixels.

As a result, the template region 32 can be positioned with an accuracy of 4 pixels. The state of sampling is shown in Fig. 4 (b),
441, 442, 443, ... are sampling points.

In this way, in the second step, the necessary pixel calculation is (I / 8) × (I / 8) × (J / 8) pixels in the template area 32 (J × 8) × (5 × 5) times.

In the third stage, the template region 33 of (I / 4) × (J / 4) pixels is used, and the candidate point region is added to the position obtained in the second stage by adding the relative positional relationship between the template regions 32 and 33. It is set within a range of ± 4 pixels with the centered position as the center.

Then, template matching is performed with the sampling rate set to one pixel for every two pixels. This is shown in FIG. 4 (c). 421, 422, 423, ... Are sampling points.

As a result, the template region 33 can be positioned with an accuracy of 2 pixels.

The number of pixel calculations required in the third stage is the same as in the second stage.

In the fourth stage, the template region 34 of (I / 8) × (J / 8) pixels is used, and the candidate point region is added to the position obtained in the third stage by adding the relative positional relationship between the template regions 33 and 34. It is set within a range of ± 2 pixels with the centered position as the center.

Then, template matching is performed with a sampling rate of one pixel at a time. This is shown in FIG. 4 (d), and 411 ... Sampling points.

As a result, the template region 34 can be positioned with an accuracy of one pixel.

The required number of pixel calculations in the fourth stage is the same as in the second stage.

FIG. 1 is a block diagram showing a circuit configuration in one embodiment of the present invention.

Reference numeral 1 is a TV (television) camera, and 2 is an A / D converter for converting a video signal from the TV camera into a digital signal. The output of the A / D converter 2 is sent to and stored in the image memory 3. A template image is stored in advance in the template memory 4 of FIG.

After inputting the image, the CPU (central processing unit) unit 9 sends a template area to the address generation unit 5 via the bus 8.
When the candidate point area and the sampling rate are designated and activated, the address generator 5 continuously generates read addresses for the image memory 3 and the template memory 4,
The matching unit 6 includes an image memory 3 and a template.
The contents of the memory 4 are sent in synchronization with each one pixel.

The matching degree calculated by the matching unit 6 is sent to the maximum matching point detecting unit 7 and the position of the candidate point having the maximum matching degree of the template 10 is detected.

The result is read by the CPU unit 9.

This sequence is repeated N times until the final (N) stage.

FIG. 2 shows a flow chart showing the sequence.

That is, in step 21, the image area is input from the camera 1,
In step 22, A / D conversion is performed by the A / D converter 2, the image memory 3 is stored in step 23, and step 24
Then, the CPU 9 designates the address generator 5 to select the first-stage template region, candidate point region, and sampling rate.

Then, the outputs of the image memory 3 and the template 4 are matched in step 25, and the maximum matching score is detected in step 26.
If the determination is NO in step 27, the template area, candidate point area, and sampling rate in the next step of step 28 are
It is selected by the designation of the CPU 9, and the process returns to the matching in step 25, which is repeated N times, and at the end of step 29, the template is matched.

〔The invention's effect〕

In the conventional pattern matching method, if the template region 31 is used, (I / J) × (DX / DY) times, however, according to the hierarchical structural template matching method of the present invention, the template is processed in N stages. -When matching is performed, [(I / 2 ^N-1 ) x (J / 2 ^N-1 )] x [(DX / 2 ^N-1 ) x (DY / 2 ^N-1 ) + (N-1) x (5 × 5)] pixel calculation is enough.

To show this more concretely, for example, when I, J = 256 and DX, DY = 64, the template area 31 is used in the conventional method as follows: (256 × 256) × (64 × 64) ≈ 268 × 10 ⁶ times are required for pixel operations, however, according to the present invention [(256/8) × (256/8)] × [(64/8) × (64/8) + 3 × (5 × 5 )] ≈ 142 × 10 ³ pixel calculations are required.

Thus, by using the hierarchical structural template matching method according to the present invention, the number of pixel operations can be reduced to about 1/24 ^(N-1) when I, J, DX, DY are sufficiently large, and the matching can be performed. This significantly promotes the efficiency of, and leads to the improvement of reliability as compared with the case where matching is performed with the entire image using only a small template.

[Brief description of drawings]

FIG. 1 is a block diagram showing a circuit configuration in an embodiment of the present invention, and FIG. 2 is a flow chart showing its operation sequence.
A chart, FIG. 3 is a schematic diagram of the present invention, FIG. 4 is a transition diagram of the sampling rate at each stage of the present invention, and FIG. 5 is a maximum degree of coincidence in one stage of the present invention and the second stage. FIGS. 6 and 7 are explanatory views of a conventional example. 1 ... TV camera 2 ... A / D converter 3 ... Image memory 4 ... Template memory 5 ... Address generation unit 6 ... Matching unit 7 ... Maximum matching point candidate detection unit 8 ... Bus 9 ... … CPU 10… Template 481,482,483,… 441,442,443,…, 421,422,423,… 411 ……
Sampling points 51 …… The maximum matching score in the first stage 52 …… Candidate point area in the second stage 521,522,523,… 52c,… 52n …… Candidate points.

Claims (1)

[Claims] 1. The matching between a target input image and a template image is performed in a plurality of stages, and the size of the template image, the sampling rate,
In the hierarchical structural template matching method in which the candidate point area is gradually reduced, the total number of steps is N, and each step from the first step to the (N-1) th step is referred to as the Mth step. In the first step, the target input image and the template image are matched at each position determined by the sampling rate 2 ^N−1 in an arbitrary candidate point region in the target input image, and the matching degree at that time is determined. The maximum position is designated as the reference position for matching in the second stage, and in each stage from the second stage to the (N−1) th stage, ± 2 ^N− with the reference position designated in the previous stage as the center. the ^{M + 1} pixel square region and the candidate point area, performs matching for each position determined by the sampling rate 2 ^N-M in this region, position coincidence degree at that time is the maximum Is designated as a reference position for matching in the next stage, and in the Nth stage, matching is performed at all positions within a square area of ± 2 pixels centered on the reference position designated in the (N-1) th stage, A hierarchical structured template matching method characterized in that the position at which the degree of matching at that time is maximum is determined as a true matching point.