JPH09102039A - Template matching method - Google Patents

Abstract

(57) Abstract: A template matching method capable of detecting a graphic that is enlarged, reduced, or rotated in a wide range with respect to a template graphic. SOLUTION: In a first sampling step 40, in a template image, polar coordinate type sampling points are defined at geometrical distance positions in the radial direction and at geometrical intervals in the angular direction. To obtain polar template image data. Second sampling step 5
At 0, polar coordinate type target image data is obtained at each scanning point of the target image in the same manner as in the first sampling step 50. Then, in the template matching step 60,
The polar coordinate type template image data is superimposed on the polar coordinate type target image data, and the maximum normalized correlation value at each scanning point is obtained while moving the polar coordinate type template image data in the radial direction and the angular direction. The matching point is detected based on the normalized correlation value of.

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a template matching method for checking whether or not a known small image is included in input image data by superposing an input image and a template image. is there.

[0002]

2. Description of the Related Art In image processing technology, various pattern matching methods are used to check whether or not a known small image is included in an input image.
Of these pattern matching methods, the template matching method is the simplest method and is widely used in practice.

FIG. 13 is a diagram for explaining a conventional template matching method. As shown in FIG. 13A, the area size of a known rectangular small image f to be searched called a template is MX × MY, and as shown in FIG. 13B, the input rectangular target image The area size of g is NX × NY. Further, the level of the density value of the template image data and the target image data is set to 256 levels having a value of 0 to 255, and the density value of the template image data is a two-dimensional matrix f [i] [j] (0 ≦ i ≦ MY-1,
0 ≦ j ≦ MX-1), the density value of the input image data is g [i] [j] (0 ≦ i ≦ NY-1, 0 ≦ j ≦ NX-1).
And stored in The representative point of the template image data is, for example, the upper left corner point, and the normalized correlation value when the representative point is matched with the scanning point (k, l) of the target image data is defined by the following equation.

[0004]

(Equation 1) Here, f _ave is the average density value of the template image data, and g _ave is the average density value of the current processing target range for the target image data. The value of the equation (1) takes a value from -1 to +1. When the representative point of the template image data is aligned with the scanning point (k, l) of the target image data, the template image f and the target image g are Is completely matched, corr (k, l) = 1.0. Then, as the degree of coincidence between the template image f and the target image g decreases, corr (k, l) becomes smaller than +1.

In the conventional template matching method,
The template image data is superimposed on the target image data, and as shown in FIG. 13C, the template image data is sequentially scanned over the entire area of the target image data to calculate the normalized correlation value at each scanning point. After that, the template image is provided at the point that gives the maximum value among the normalized correlation values at each of these scanning points, and that the maximum value is greater than or equal to a predetermined specified value C ₀ (for example, C ₀ = 0.8). Is detected.

[0006]

By the way, in the conventional template matching method, the small figure detected in the target image and the template figure are, in principle, congruent in terms of size and orientation. It is assumed. Therefore, even if the small figure and the template figure in the target image have the same size, they cannot be detected if the directions are different. Further, even if the small figure and the template figure in the target image face the same direction, if they are different in size, they cannot be detected. However, it is possible to detect a figure that is slightly enlarged / reduced or rotated by devising the method of setting the above-mentioned specified value C ₀ . However, the detectable range is 90 to 110% in the enlargement / reduction ratio and within ± 10 degrees in the rotation angle, and there is a limit of the detectable range here. As described above, the conventional template matching method has a problem that it is not possible to detect a graphic that is enlarged / reduced or rotated in a wide range with respect to the template graphic in the template image.

The present invention has been made based on the above circumstances, and provides a template matching method capable of detecting a graphic that is enlarged / reduced or rotated in a wide range with respect to a template graphic in a template image. It is intended to be provided.

[0008]

According to a first aspect of the present invention for achieving the above object, in a template matching method for detecting a portion of a target image which matches a template figure in a template image, In the first circular area that contains the template figure in the template image, the center of the first circular area is the origin, and the radial direction is set to the geometrical distance position, and the angular direction is equal By setting the polar coordinate type sampling points determined at a series interval, by sampling the image density of the template image at the polar coordinate type sampling points set in the first circular region,
A first sampling step of obtaining polar coordinate type template image data, and a second circular region centered on each scanning point in the target image, with the center of the second circular region as the origin, the polar coordinate type sampling points And sampling the image density of the target image at the polar coordinate type sampling points set in the second circular region to obtain polar coordinate type target image data at each scanning point. By superposing the polar coordinate type template image data on the polar coordinate type target image data and moving the polar coordinate type template image data in the radial direction and the angular direction, the polar coordinate type target image data and the polar coordinate type After obtaining the maximum normalized correlation value with the template image data, A template matching step of detecting, as a matching point, a point that gives the maximum value among the maximum normalized correlation values and that the maximum value is equal to or greater than a predetermined specified value. Is.

A template matching method according to a second aspect of the present invention is the method according to the first aspect, wherein the vertical axis is a column of radial sampling points of the polar coordinate type sampling points, and the horizontal axis is the horizontal axis. After constructing a virtual search space in which a row of sampling points in the angular direction of the polar coordinate type sampling points is arranged, and arranging the polar coordinate type target image data at a predetermined position in the virtual search space, the virtual search space In the above, the polar coordinate type template image data is superimposed on the polar coordinate type target image data, and the maximum normalized correlation value is obtained while moving the polar coordinate template image data in the vertical axis direction and the horizontal axis direction. To do.

According to a third aspect of the present invention, there is provided a template matching method according to the second aspect, wherein a rectangular area designated by a preset rotation angle allowable range and an enlargement / reduction rate allowable range is set to the virtual area. The present invention is characterized in that a search area in a search space is set, and a representative point of the polar coordinate template image data is moved within the search area.

A template matching method according to a fourth aspect of the present invention is the template matching method according to the first to third aspects of the invention.
The first circular area is centered at the center position of the rectangular area of the template image, and the radius of the smaller half of the vertical length and the horizontal length of the rectangular area is set. It is characterized by that. Claim 5
The template matching method according to the invention described in claim 1, in the invention described in claims 1 to 4, wherein the number of sampling points in the radial direction of the polar coordinate type sampling points set in the first circular region is the first It is characterized in that it is not more than a value obtained by dividing the radius of one circle area by the distance between adjacent pixels.

[0012]

According to the first aspect of the present invention, polar coordinate type sampling points defined by geometrical distances in the radial direction and geometric progressions in the angular direction are constructed by the above construction. The template matching is performed using the polar coordinate type image data set and sampled at the polar coordinate type sampling points. When performing this template matching, first, the sampling point in the angular direction is arranged on the horizontal axis and the sampling point in the radial direction is arranged on the vertical axis to construct a virtual search space, and the polar coordinate type target image data is virtually searched. It is placed at a predetermined position in the space. Then, in this virtual search space, the polar coordinate type template image data is superimposed on the polar coordinate type target image data, and the maximum normalized correlation value is obtained while moving the polar coordinate template image data in the radial direction and the angular direction. here,
Moving the polar coordinate type template image data in the angular direction is equivalent to rotating the template image around its center. In the virtual search space, moving the polar coordinate type template image data in the radial direction corresponds to enlarging or reducing the template image with respect to its center. Therefore, by moving the polar coordinate type template image data on the polar coordinate type target image data in the radial direction and the angle direction, it is possible to perform template matching in consideration of rotation and scaling of the template figure in the target image. it can.

[0013]

DESCRIPTION OF THE PREFERRED EMBODIMENTS One embodiment of the present invention will be described below with reference to the drawings. FIG. 1 is a diagram for explaining a template matching method according to an embodiment of the present invention. In the template matching method according to the present embodiment, a polar coordinate type sampling point is set in the template and the target image, and the image density is sampled at the polar coordinate type sampling point, whereby polar coordinate type template image data and polar coordinate type target image data are obtained. And perform template matching. As shown in FIG. 1, this template matching method includes a target image data reading step 10, a template image data setting step 20, a sampling condition / template matching condition setting step 30, and a first sampling step 40.
A second sampling step 50, a template matching step 60, and a template matching result display / storing step 70.

In the step 10 of reading the target image data,
For example, the rectangular target image data is input by driving a CCD camera or the like, or when the rectangular target image data is already stored in the image data file, the predetermined target image data is read from the image data file. hand,
The target image data is stored in the processing target image data area. At this time, at the same time, information such as the size of the rectangular area and the density value of the target image is acquired. Further, in the template image data setting step 20, if rectangular image data called a template is previously stored in the image data file, the predetermined template image data is read from the image data file and the template image data is read. Stored in the image data area of the template. Alternatively, when the template image data is not stored in the image data file, the target image or the like is displayed on the display device, and a part of the image represented in the target image is framed by using the input device. By designating, the designated image is registered as a template image, and the template image data is stored in the image data area of the template. At this time, at the same time, information such as the size of the rectangular area and the density value of the template image is acquired.

In the sampling condition / template matching condition setting step 30, the number of sampling points in the radial direction, the number of sampling points in the angular direction, the rotation angle permissible range, the enlargement / reduction ratio permissible range, and the specified value of the normalized correlation value. Etc. are set. In the present embodiment, the template image is rotated and enlarged / reduced within the rotation angle allowable range and the enlargement / reduction ratio allowable range set here, and it is checked whether or not the image is included in the target image. However, for the rotation angle allowable range, the default value is -180 degrees to +1.
The full angle range of 80 degrees is given. In addition, the specified value of the normalized correlation value serves as a threshold value for determining whether or not the target image includes the template image.

In the first sampling step 40, in the first circular region containing the template figure in the template image, with the center of the first circular region as the origin, the geometrical distance in the radial direction. Polar coordinate type sampling points that are determined by the position and are determined at an arithmetic series interval in the angular direction are set. Then, the image density of the template image is sampled at the set polar coordinate type sampling points to obtain polar coordinate type template image data. Second sampling step 5
In 0, a polar coordinate type sampling point is set in the second circular area centered on each scanning point in the target image, with the center of the second circular area as the origin, as in the first sampling step 40. . Then, by sampling the image density of the target image at the set polar coordinate type sampling points, polar coordinate type target image data at each scanning point is obtained. Although only one polar coordinate type template image data is created, the polar coordinate type target image data is created each time the scanning point changes.

In the template matching step 60, the polar coordinate type target image data is superposed on the polar coordinate type target image data, and the polar coordinate type template image data is moved in the radial direction and the angular direction to obtain the polar coordinate type target image data. The maximum normalized correlation value with the polar coordinate type template image data is obtained. After that, a point that gives the maximum value among the maximum normalized correlation values for each scanning point and that the maximum value is equal to or larger than a predetermined specified value is detected as a matching point. In the template matching result display / storing step 70, the template matching result is displayed on the CRT display device or stored in the storage means.

Next, the template matching method of this embodiment will be described in detail. 2 is a diagram for explaining a procedure for creating polar coordinate type template image data from a rectangular template image, FIG. 3 is a diagram for explaining a procedure for creating polar coordinate type target image data from a rectangular target image, and FIGS. 6 is a diagram for explaining a virtual search space, and FIGS. 7 and 8 are diagrams for explaining a matching process using polar coordinate type image data.

First, a rectangular target image is input using a CCD camera or the like. Now, the area size of this target image is
As shown in FIG. 3A, it is assumed that NX × NY. The operator also sets a rectangular template for the figure to be detected. The area size of this template image is assumed to be MX × MY, as shown in FIG. Next, the operator uses the number S of sampling points in the radial direction, the number T of sampling points in the angular direction, the rotation angle allowable range, the enlargement / reduction ratio allowable range, the specified value C ₀ of the normalized correlation value, and the like on the keyboard. Input from an input device such as. Here, the allowable rotation angle range is -180 degrees to +18.
Scaling rate allowable range is 50% to 200 in the entire range of 0 degree.
%, And the specified value C ₀ of the normalized correlation coefficient is 0.
Suppose that it is set to 8.

Next, polar coordinate type sampling points are set for the template image. First, in a rectangular template image, a template figure is included, and if possible, a first circular area centered on the center of gravity of the figure is set. Normally, as shown in FIG. 2A, the central position (x _c , y _c ) of the rectangular area of the template image =
Centering around (MX / 2, MY / 2), length M in x direction
The smaller half of the lengths MY in the X and y directions is the radius M.
Set a circular area to be R. Here, if the meaningful portion of the template figure extends beyond the set circular area, the area size of the template image is increased so that the meaningful portion is not outside the circular area. Need to do so. In this way, the first circular region is set for the template image, and its center (x _c , y _c ) and the radius MR are obtained. In the following, the template image in the first circular area will also be referred to as a circular template image.

After that, a geometric series for determining sampling points in the radial direction in the first circular area is determined. The value of the first term r ₀ of this geometric series is preset. On the other hand, since the ratio r _t (> 1.0) is S, the number of sampling points in the radial direction is S, the condition r ₀ × r _t ^S that the S-th term is included in the first circular region. ^-1 = MR ··· (2) is obtained. Thus, the geometric series is determined. The distance position from the center of the first circular region to each of the S-th terms of the determined geometric series becomes the sampling point in the radial direction. Now, the row of sampling points in the radial direction is defined as r ₀ , r ₁ , r ₂ , ..., R _S-1 ... (3). By the way, if the distance S between adjacent pixels is d, and the number S of sampling points in the radial direction is larger than a value obtained by dividing the radius MR of the first circular region by d, the distance between adjacent pixels is A large number of sampling points will be included. As will be described later, with respect to such sampling points, since the image density is sampled by performing interpolation using the density values in the same pixel, almost the same sampling result can be obtained. For this reason,
Generally, it is desirable to set the number S of sampling points in the radial direction to a value equal to or less than a value obtained by dividing the radius MR of the first circular region by the distance between adjacent pixels.

Further, an arithmetic series for determining sampling points in the angular direction in the first circular area is determined. The value of the first term q ₀ of this arithmetic series is preset as, for example, q ₀ = 0. On the other hand, the tolerance q _t is given by q _t = 360 ÷ T since the number of sampling points in the angular direction is T.
In this way, the arithmetic series is determined, and the angle given by each term up to the T-th in the determined arithmetic series becomes the sampling point in the angular direction. The sequence of sampling points in the angular direction is 0 = q ₀ , q ₁ , q ₂ , ..., Q _T-1 ... (4). Generally, the smaller the tolerance q _t , that is, the sampling interval in the angular direction, the better, but since the sampling processing time increases in proportion to this, the number T of sampling points in the angular direction is It is desirable to set it in consideration of the processing time. In addition, how much the template figure is rotated to detect,
The number T of sampling points in the angular direction should be set in consideration of the accuracy with which the rotation should be determined. For example, the angular sampling interval is
One of the angular intervals such as 1, 2, 3, 5, 10, 15, 22.5, 45 degrees may be selected.

A sequence of sampling points in the radial direction of the template image thus obtained {r _i } (i =
0, 1, ..., S-1) and a sequence of sampling points in the angular direction {q _j } (j = 0, 1, ..., T-1), as shown in FIG. , The center of the first circular region (x
_c , y _c ) as an origin, and a polar coordinate sampling point (r
_i , q _j ) are set. Also, the xy Cartesian coordinates corresponding to this polar coordinate type sampling point (r _i , q _j ) are expressed as follows: x = r _i × cosq _j + x _c y = r _i × sinq _j + y _c (5) Obtained from the relational expression, a coordinate correspondence table of polar coordinates (r _i , q _j ) and Cartesian coordinates (x, y) is created. here,
x and y are generally real numbers.

Next, polar coordinate sampling is performed on the template image. First, each polar coordinate type sampling point (r _i , q _j ) is converted into a corresponding point (x, y) using the above coordinate correspondence table. Next, based on the rectangular template image data, the density values of the four pixel points closest to this point (x, y) are calculated, and using this,
The density value at the point (x, y) is calculated by interpolation. And
The concentration values of points the calculated (x, y), the corresponding polar coordinate-type sampling points (r _i, q _j) to a concentration value, this two-dimensional matrix f of polar coordinate type template image data '[i] [ j] (i = 0, 1, ..., S-1, j = 0, 1, ..., T-1) ... (6). That is, as shown in FIG. 2C, this polar coordinate type template image data has a column of sampling points in the radial direction in the row direction {r _i } (i = 0, 1, ..., S).
−1), S × T obtained by taking a sequence {q _j } (j = 0, 1, ..., T-1) of sampling points in the angular direction in the sequence direction.
Are arranged in the table.

Next, polar coordinate type sampling points are set for the target image, and polar coordinate sampling is executed. In this case, the method of setting the polar coordinate type sampling points is basically the same as that for the template image, but the upper limit of the set allowable enlargement / reduction ratio is 100.
If it is larger than%, it needs to be slightly modified. Now, consider a case where the center of the circular template image is superimposed on the scanning point (x _t , y _t ) in the target image to perform template matching. Further, the upper limit of the allowable enlargement / reduction ratio range is P _max (%). First, in the case of P _max ≦ 100, a second circular region having the same radius MR as the first circular region is set around the scanning point (x _t , y _t ) while P _max > 100. , The scanning point (x _t , y _t )
A second circular region having a radius of MR × P _max / 100 is set with respect to the center. Next, the sampling points in the radial direction of the target image are set using the geometric series that defines the sampling points in the radial direction of the template image. When P _max ≦ 100, the number of sampling points in the radial direction of the target image is S, and the row of sampling points in the radial direction is set by the equation (3) as in the case of the template image. . On the other hand, P _max > 10
In the case of 0, it is necessary to increase the number of sampling points in the radial direction as much as the second circle area is larger than the first circle area. Therefore, conditions ^{_{100r t L ≧ P max ···· (}} 7) calculates the smallest natural number L satisfying, the number of radial sampling points for the target image, radial sampling for the template image A total of S + L is obtained by newly adding L sampling points to the number S of points. The row of sampling points in the radial direction obtained in this way is defined as r ₀ , r ₁ , ..., R _S-1 , r _S , ..., R _{S + L-1} (8). To do. In the following, L is 0 or a natural number,
In either case of P _max ≦ 100 and P _max > 100,
The sequence of sampling points in the radial direction of the target image will be expressed by equation (8).

Also, the angle direction of the target image is sampled.
For the pulling point sequence, see P_max≤100, P_max>
In either case of 100, the template image
Similar to the above, set by equation (4). in this way
Sampling of the target image obtained by
Sequence of points {r _k} (K = 0, 1, ..., S + L-1) and the angle
Sequence of sampling points {q_j} (J = 0, 1, ...
 , T-1), as shown in FIG.
In the circular area of, its center (x_t, Y_t) As the origin
Coordinate type sampling point (r_k, Q_j) Is set. Ma
In addition, this polar coordinate type sampling point (r_k, Q_j) Compatible
X-y Cartesian coordinates, x = r_k× cosq_j+ X_t y = r_k× sinq_j+ Y_t .... Obtained from the relational expression of (9), polar coordinates (r_k, Q_j) And Cartesian coordinates
A coordinate correspondence table with (x, y) is created. here,
x and y are generally real numbers.

After that, each polar coordinate type sampling point (r _k , q _j ) is converted into a corresponding point (x, y) using the above coordinate correspondence table, and the density value of this point (x, y) is converted. , Is calculated using the same interpolation method as in the case of polar coordinate sampling for the template image. Then, the density value of the point that the calculated (x, y), polar sampling points (r _k, q _j) to a concentration value, this matching scanning point (x _t, y _t) for polar type target image data in the , Two-dimensional matrix g ′ [k] [j] (k = 0, 1, ..., S + L-1, j = 0, 1, ..., T-1). That is, the polar coordinate type target image data at the scanning point (x _t , y _t ) is r _k (k = 0, 1, ..., S + L−1) in the row direction as shown in FIG. 3B. ,
They are arranged in a (S + L) × T table in which q _j (j = 0, 1, ..., N−1) is taken in the column direction. Here, FIG.
A circle C ₁ having a radius r _S-1 shown in (a) has the same size as the first circle region, and in the polar coordinate type target image data g ′ [k] [j] shown in FIG. 3 (b). The portion including the points sampled in the area within the circle C ₁ is the standard size portion including the same number of sampling points as the polar coordinate type template image data f ′ [i] [j]. The circle C ₂ of radius r _{S + L-1} shown in FIG. 3A is the upper limit P of the allowable scaling ratio range.
It corresponds to _max and represents the second circular area. Further, in FIG. 3B, the lower limit P _{min of the} allowable scaling ratio range
The sampling point in the radial direction corresponding to is shown as r _U-1 .

Thus, from the rectangular image data of the template and the target image, one polar coordinate type template image data f ′ [i] [j] and the polar coordinate type target image data g ′ at the scanning point (x _t , y _t ). Once [k] [j] is obtained, template matching is performed next. First, FIG.
Construct a two-dimensional virtual search space as shown in. In this virtual search space, a row of sampling points in the angular direction is arranged on the horizontal axis and a row of sampling points in the radial direction is arranged on the vertical axis. Then, the polar coordinate type target image data g ′ [k] [j] is arranged at a predetermined position in the virtual search space. Specifically, as shown in FIG. 5, the polar coordinate type target image data g ′ [k] [j] is converted into the corresponding orthogonal coordinate position (r _k , q _j ) in the virtual search space, that is, the region R ₁ Place it inside. In addition, the polar coordinate type target image data g ′ [k] [j] is displaced by, for example, +360 degrees in the horizontal axis direction from the orthogonal coordinate position (r _k ,
q _{j + N} ), that is, the rectangular coordinate position (r _k , q) arranged in the region R ₂ and shifted by −360 degrees in the horizontal axis direction.
_jN ), that is, in the region R ₃ . Then, in this virtual search space, the polar coordinate type template image data f ′ [i] [j] is overlaid on the polar coordinate type target image data g ′ [k] [j] to obtain the polar coordinate template image data f ′ [i] [j. ] In the radial and angular directions to obtain the maximum normalized correlation value.

Here, in this embodiment, polar coordinate type sampling points are set at geometrical distance positions in the radial direction and at geometrical intervals in the angular direction. By performing template matching using polar coordinate type image data sampled at polar coordinate type sampling points, the following two things are possible. First, as shown in FIG. 7, by moving the polar template image data in the virtual search space in the angular direction, the same effect as rotating the circular template image around its center can be obtained. Second, since the sampling points in the radial direction are set in geometric progression, for any two adjacent sampling points in the radial direction, the ratio of the distances of these two points from the origin is Is constant and determined only by the common ratio r _t . Therefore, as shown in FIG. 8, by moving the polar coordinate type template image data in the radial direction in the virtual search space, the same effect as enlarging or reducing the circular template image with respect to its center can be obtained.

The template matching process is specifically performed as follows. Now, as shown in FIG. 6, the rotation angle allowable range of −180 to +180 degrees set in the sampling condition / template matching condition setting step 30 and 5
A rectangular area designated by the 0 to 200% enlargement / reduction rate allowable range is set as a search area R ₀ . The search region R ₀ is a region in the virtual search space where the representative point of the polar coordinate type template image data is moved. Then, as shown in FIG. 4, assuming that the representative point of the polar coordinate type template image data is the upper left corner point (r _S-1 , q ₀ ), the representative point of the polar coordinate type image data is moved over the entire search region R _0. A normalized correlation value between the template image data f ′ [i] [j] and the polar coordinate type target image data g ′ [k] [j] is obtained. Here, when the representative point is aligned with the position where the enlargement / reduction ratio is smaller than 100%, the number of sampling points in the radial direction that can be used in the template matching process is less than S, but in this case, Of the sampling points in the radial direction, only a predetermined number from the largest may be used for the template matching process. Generally, the polar coordinate type sampling points are closer to the origin, and the polar coordinate type sampling points near the origin point have almost the same density value. This is because there is no need to place importance on it. Also,
When the representative point is aligned with the position where the enlargement / reduction ratio is greater than 100%, for the same reason, the sampling point in the radial direction used for the template matching processing is
It is sufficient to use only a predetermined number from the larger one. Then, of the normalized correlation values obtained at each representative point, the maximum normalized correlation value is stored in the storage means.

Next, the entire surface of the target image is scanned, and at each scanning point, the maximum normalized correlation value is obtained in the same manner as above, and this is stored in the storage means. Thereafter, among the maximum normalized correlation values at each scanning point stored in the storage means, a point that gives a maximum value and the maximum value is equal to or larger than a predetermined specified value is detected as a matching point. . When the matching point is detected, it is determined that the matching point includes the template image. on the other hand,
If no matching points are detected, this target image will contain
It is determined that the template image is not included. Thereafter, the template matching result is displayed on the display device and stored in the storage means.

From the practical point of view, it is desirable that the template matching method described above be performed by the processing procedure shown in FIG. That is, since the calculation for the template image need only be done once in terms of the program, first, after setting the sampling condition and the template matching condition (step12), the template image data is set (step14), Perform one sampling process (step 16). Next, the target image data is read (step 18), and the second sampling process is performed at one scanning point in the target image (step 22). After performing the template matching process (step 24), the template matching result is displayed on the display device and stored in the storage means (step 26). Next, it is determined whether template matching processing has been performed at all scanning points of the target image (step 28). If processing has not been performed at all scanning points, the process proceeds to step 22 and the next scanning is performed. The same processing is repeated at the points. On the other hand, in step 28,
When it is determined that the processing has been performed at all the scanning points, it is determined whether there is another target image to be processed (step 32). If there is another target image, the process proceeds to step 18 and the same process is repeated, while if there is no other target image, the process ends.

As described above, in the template matching method according to the present embodiment, the polar coordinate type is determined at the geometrical distance position in the radial direction and at the geometric progression intervals in the angular direction. After setting the sampling points, the image density is sampled at the polar coordinate type sampling points to obtain the polar coordinate type template image data and the polar coordinate type target image data. Moving the polar coordinate type template image data in the angular direction corresponds to rotating the template image, and moving the polar coordinate type template image data in the radial direction changes the template image. This is equivalent to enlarging / reducing. Therefore, by moving the polar coordinate type template image data on the polar coordinate type target image data in the radial direction and the angle direction, it is possible to perform template matching in consideration of rotation and scaling of the template figure in the target image. it can.

Further, the present inventors have actually performed image processing using the template matching method of this embodiment and verified the effect. Here, for ease of processing, the figure to be detected is rotated with respect to one target image,
The matching possibility was examined using a plurality of enlarged and reduced template images. As the target image, as shown in FIG. 10, an image in which two sets of parallel two lines intersect each other was used. The image size of this target image is 512 × 480 pixels. The four template images shown in FIG. 11 were used. The first template image shown in FIG. 11A is created by designating a portion where the two lines intersect at right angles from the target image, and the image size is 12
It has 8 × 128 pixels. The second template image is obtained by rotating the first template image by 30 degrees around its center, as shown in FIG. 11 (b). The third template image is obtained by enlarging the first template image by 130% as shown in FIG. 11 (c). Then, the fourth template image is shown in FIG.
As shown in, the first template image is obtained by rotating it about its center by 30 degrees and enlarging it by 130%.
When the present inventors performed matching processing using these four template images, it was possible to perform matching with extremely high accuracy regardless of which template image was used. Considering that the conventional template matching method can detect a figure within a scaling ratio of 90 to 110% and a rotation angle within ± 10 degrees, in the template matching method of the present embodiment, a template figure is It was confirmed that the rotation angle range and the enlargement / reduction ratio range of the figure that can be detected by the method can be greatly expanded. Further, the template matching method according to the present embodiment is
As the computing power of computers will increase in the future,
It seems that the scope of application can be further expanded by increasing the number of sampling points. For this reason,
In particular, it is suitable for use in the field of factory automation, robot vision, image monitoring, and the like.

It should be noted that the present invention is not limited to the above embodiment, and various modifications are possible within the scope of the invention. For example, in the above embodiment, when the maximum normalized correlation value is obtained in the virtual search space, the representative point of the polar coordinate type template image data may be binary-searched. In this case, first, as shown in FIG. 12, the four corner positions P ₁ in the search region R ₀ determined by the rotation angle allowable range (−180 to +180 degrees) and the enlargement / reduction ratio allowable range (50 to 200%). , P ₂ , P
_The representative points are superposed on ₃ and P ₄ , the normalized correlation value at each position is calculated, and the corner position that gives the largest normalized correlation value is obtained. Next, among the four regions R ₀₁ , R ₀₂ , R ₀₃ , and R ₀₄ obtained by dividing the search region R ₀ , the region including the obtained corner position is similarly the largest in the normalized correlation value. A corner position giving a normalized correlation value is obtained. In this way, the area to be searched sequentially is reduced, and the maximum normalized correlation value is obtained.
The processing time can be shortened. The method of scanning the representative points by the binary search is particularly effective when the correlation value changes smoothly with respect to the change of the representative points.

Further, in the above embodiment, when sampling the density value at the polar coordinate type sampling point, the case where the interpolation method using the density values of the four pixel points closest to the sampling point is used is described. As the interpolation method used for, for example, a method of assigning the density value of the pixel point closest to the sampling point, or the four pixel points closest to the sampling point and their density values, and the four density points and the sampling points A method such as linear interpolation using the distance to the pixel point may be used.

[0037]

As described above, according to the first aspect of the invention, the radial position is set to a geometric series distance position, and the angular direction is set to a geometric progression interval. After the polar coordinate type sampling point is set, the image density is sampled at the polar coordinate type sampling point to obtain the polar coordinate type template image data and the polar coordinate type target image data. When the template image data is moved, moving the polar coordinate type template image data in the angular direction corresponds to rotating the template image, and moving the polar coordinate type template image data in the radial direction, This is equivalent to enlarging / reducing the template image. Can be provided radial direction on the elephant image data, the rotation of the template figure in the target image by moving angularly, and the expanded template matching method can be performed in consideration of the matching process is also reduced.

[Brief description of the drawings]

FIG. 1 is a diagram illustrating a template matching method according to an embodiment of the present invention.

FIG. 2 is a diagram for explaining a procedure for creating polar coordinate type template image data from a rectangular template image.

FIG. 3 is a diagram for explaining a procedure for creating polar coordinate type target image data from a rectangular target image.

FIG. 4 is a diagram for explaining a virtual search space.

FIG. 5 is a diagram for explaining a virtual search space.

FIG. 6 is a diagram for explaining a virtual search space.

FIG. 7 is a diagram for explaining a matching process using polar coordinate type image data.

FIG. 8 is a diagram for explaining a matching process using polar coordinate type image data.

FIG. 9 is a diagram for explaining an example of a processing procedure of the template matching method according to the present embodiment.

FIG. 10 is a diagram for explaining a target image actually used by the inventors when verifying the template matching method according to the present embodiment.

FIG. 11 is a diagram for explaining a template image actually used by the inventors when verifying the template matching method according to the present embodiment.

FIG. 12 is a diagram for explaining an operation of scanning a representative point of polar template image data in a binary search manner.

FIG. 13 is a diagram for explaining a conventional template matching method.

[Explanation of symbols]

10 Step of reading target image data 20 Step of setting template image data 30 Step of setting sampling conditions / template matching conditions 40 First sampling step 50 Second sampling step 60 Template matching step 70 Template matching result display / storing step

Claims (5)

[Claims] 1. A template matching method for detecting, in a target image, a portion corresponding to a template figure in a template image, wherein a first circular region including the template figure in the template image has a first With the center of the circle area as the origin,
The radial direction is set to a geometrical distance position,
Regarding the angular direction, setting polar coordinate type sampling points set at an arithmetic progression interval, and sampling the image density of the template image at the polar coordinate type sampling points set in the first circular region. According to the first sampling step of obtaining polar coordinate type template image data, in a second circular area centered on each scanning point in the target image, with the center of the second circular area as the origin, the polar coordinate type By setting sampling points and sampling the image density of the target image at the polar coordinate type sampling points set in the second circular area, a second type of polar coordinate type target image data at each scanning point is obtained. Sampling step, the polar coordinate type template image data on the polar coordinate type target image data After superimposing, by moving the polar coordinate type template image data in the radial direction and the angular direction, after obtaining the maximum normalized correlation value between the polar coordinate type target image data and the polar coordinate type template image data, A template matching step of detecting, as a matching point, a point that gives a maximum value among the maximum normalized correlation values for a scanning point and that the maximum value is equal to or greater than a prescribed value. Template matching method characterized by. 2. A row of radial direction sampling points of the polar coordinate type sampling points is arranged on the vertical axis, and a row of angular direction sampling points of the polar coordinate type sampling points is arranged on the horizontal axis. After constructing a virtual search space and arranging the polar coordinate type target image data at a predetermined position in the virtual search space, the polar coordinate type template image data is superimposed on the polar coordinate type target image data in the virtual search space, 2. The template matching method according to claim 1, wherein the maximum normalized correlation value is obtained while moving the polar coordinate template image data in the vertical axis direction and the horizontal axis direction. 3. A rectangular area designated by a preset rotation angle allowable range and an enlargement / reduction rate allowable range is set as a search area in the virtual search space, and a representative of the polar coordinate template image data is set in the search area. The template matching method according to claim 2, wherein the point is moved. 4. The first circular area is centered on the center position of the rectangular area of the template image, and the radius of the smaller half of the vertical length and the horizontal length of the rectangular area is set. 4. The template matching method according to claim 1, wherein the template matching method is performed by the following method. 5. The number of radial sampling points of the polar coordinate type sampling points set in the first circular area is obtained by dividing the radius of the first circular area by the distance between adjacent pixels. 5. The template matching method according to claim 1, wherein the template matching method is equal to or less than a predetermined value.