Method of image processing using parametric template matching

• US 5,943,442 A
• Filed: 06/03/1997
• Issued: 08/24/1999
• Est. Priority Date: 06/12/1996
• Status: Expired due to Fees

• Current Assignee: Nippon Telegraph and Telephone Corporation
• Original Assignee: Nippon Telegraph and Telephone Corporation
• Inventors: Tanaka, Kouichi, Sano, Mutsuo, Ohara, Syuuichi, Okudaira, Masashi
• Primary Examiner(s): Shalwala, Bipin H.
• Application Number:
  US08/867,765
• Time in Patent Office: 812 Days
• Field of Search: 382/181, 382/190, 382/191, 382/195, 382/197, 382/201, 382/203, 382/206, 382/209, 382/216, 382/217, 382/220, 382/228, 382/300
• US Class Current: 382/216
• CPC Class Codes: G06V 10/7515 Shifting the patterns to accommodate for positional errors

Abstract

In a template matching method, a region that has a plurality of normalized reference template images as vertex template images in a space of a template-pixel-size dimension is considered, and the vertex template images are linearly interpolated by a parameter w to provide a normalized interpolated template image of a magnitude 1 in the space. Then, matching between the normalized interpolated image and a search image is performed using a normalized correlation therebetween as a similarity measure, by which is obtained a parameter that provides the maximum normalized correlation value, and this normalized correlation value is determined as the maximum one.

Claims

1. A template matching method for matching an image with a plurality of template images to detect the maximum correlation value therebetween, comprising the steps of:

(a) calculating an inverse matrix H^-1 of a correlation matrix H using, as its elements, normalized correlations between a plurality of first template images;

(b) calculating a normalized correlation between a normalized image of each of a plurality of normalized first template images and at least one normalized second template image to obtain a correlation vector G; and

(c) calculating, from said correlation vector G and said inverse matrix H^-1, an estimated parameter w that maximizes a normalized correlation between said normalized second template image and a normalized interpolated template image obtained by linearly combining, by said estimated parameter w, said normalized first template images.

2. The method of claim 1, wherein:

said plurality of normalized first template images are a plurality of predetermined normalized reference template images and said second template image is a normalized matching region image at a position (x,y) in a search image;

said step (a) is a step of calculating an inverse matrix H^-1 of a correlation matrix H that uses, as its elements, normalized correlations between a plurality of reference template images (g₀, . . . , g_M);

said step (b) is a step of calculating normalized correlations between a plurality of normalized reference template images (g₀, . . . ,g_M) and a matching region image f(x,y) normalized at said position (x,y) in said search image to obtain said correlation vector G; and

said step (c) includes a step of calculating a normalized interpolated template image g_w from said estimated parameter w;

said method further comprising the steps of;

(d) calculating and storing a normalized correlation between the normalized interpolated template image g_w and the matching region image f(x,y) at the position (x,y);

(e) repeating the steps (b) through (d) while sequentially shifting the position (x,y) in the search image; and

(f) finding out the maximum one of the stored normalized correlations, thereby detecting a position where the normalized correlation value is at the maximum.

3. The method of claim 2, wherein said correlation matrix in said step (a) is calculated by the following equation:

##EQU38##

4. The method of claim 2, wherein said estimated parameter w in said step (c) is calculated by a method of Lagrange multiplier.

5. The method of claim 2, where in said normalized interpolated template image <

g>

_w, is calculated by

6. The method of claim 1, wherein:

said plurality of normalized first template images include at least one normalized matching region image at a position (x,y) or its vicinity in said search image and said second template image is a preset normalized reference template image;

said step (a) is a step of calculating an inverse matrix H^-1 of a correlation matrix H that uses, as its elements, normalized correlations between said plurality of matching region images (f₀, . . . , f_M);

said step (b) is a step of calculating normalized correlations between a plurality of matching region images (f₀, . . . ,f_M) normalized at said position (x,y) in said search image and a normalized reference template image g to obtain said correlation vector G; and

said step (c) includes a step of calculating a normalized interpolated template image <

f>

_w from said estimated parameter w.

7. The method of claim 6 further comprising the steps of:

(p-1) setting, as said position (x,y), each of lattice points defined on said search image at sampling intervals Δ

x and Δ

y larger than the pixel spacing of said search image, calculating at said each lattice point normalized correlation values between said reference template image and matching region images in said search image at a plurality of angles θ

spaced by a predetermined angular distance Δ

θ

apart with respect to said reference template image, and determining the maximum one of said normalized correlation values as a normalized correlation value at said each lattice point;

(p-2) selecting at least one maximum normalized correlation value from said normalized correlation values at said each lattice point and setting its position and angle corresponding to said selected maximum normalized correlation value, as a candidate position-angle (x_c,y_c,θ

_c); and

(d) performing said steps (a) through (c) for said candidate position-angle (x_c,y_c,θ

_c) at said each lattice point, and determining a position-angle that maximizes the normalized correlation between said normalized interpolated template image and said normalized reference template image, as an estimated position-angle (x_s,y_s,θ

_s) of a matching region most similar to said matching region image in said search image.

8. The method of claim 7, further comprising a step of performing said step (d) again after setting said estimated position-angle (x_s,y_s,θ

_s) in said step (d) as a new candidate position-angle (x_c,y_c,θ

_c) and reducing said sampling intervals Δ

x and Δ

y and said angular distance Δ

θ

by dividing with reduction ratios Z_x, Z_y and Z.sub.θ

larger than unity.

9. The method of claim 7 or 8, wherein said plurality of matching region images in said step (b) are region images defined at four positions displaced Δ

x and Δ

y from a reference matching position (x_c,y_c) in vertical and horizontal directions, respectively.

10. The method of claim 6, further comprising the steps of:

(p-1) setting, as said position (x,y), each of lattice points defined on said search image at sampling intervals Δ

x and Δ

y larger than the pixel spacing of said search image, calculating at said each lattice point normalized correlation values between said reference template and matching regions in said search image at a plurality of angles θ

spaced by a predetermined angular distance Δ

θ

apart with respect to said

reference template, and determining the maximum one of said normalized correlation values as a normalized correlation value at said each lattice point;

(p-2) selecting at least one maximum normalized correlation value from said normalized correlation values at said each lattice point and calculating its position and angle corresponding to said selected maximum normalized correlation value, as a candidate position-angle (x_c,y_c,θ

_c);

(d) performing said steps (a) through (c) for each of said candidate position-angles (x_c,y_c,θ

_c), and determining each position-angle that maximizes the normalized correlation between said normalized interpolated template image and said normalized reference template image, as an estimated position-angle (x_s,y_s,θ

_s), respectively; and

(e) calculating, based on said estimated position-angle obtained for each of said plurality of candidate positions-angles, the position-angle of said normalized interpolated template image that provides the maximum normalized correlation value for said reference template image.

11. The method of claim 10 further comprising a step of performing said step (d) a plurality of times after setting said estimated position-angle (x_s,y_s,θ

_s) in said step (d) as a new candidate position-angle (x_c,y_c,θ

_c) and reducing said sampling intervals Δ

x and Δ

y and said angular distance Δ

θ

by dividing with reduction ratios Z_x, Z_y and Z.sub.θ

larger than unity and a step of determining one of a plurality of estimated positions-angles obtained by the repetition of said step (d) that provides the maximum normalized correlation value, as the position-angle of the matching region image most similar to said reference template image.

12. The method of claim 10 or 11, wherein said plurality of matching region images in said step (b) are region images defined at the four positions displaced ±

Δ

x and ±

Δ

y from said reference matching position (x_c,y_c) in vertical and horizontal directions, respectively.

13. The method of claim 8 or 11, wherein said step (d) is performed repeatedly until said Δ

x and Δ

y become smaller than one-pixel spacing of said search image.

14. The method of claim 7 or 10, wherein said step (d) includes a step of splitting a quadrangle region, which has corners at said four positions, by two diagonal lines of said quadrangle region into four triangle regions each having a corner at said candidate position (x_c,y_c) in common to them, performing said steps (a), (b) and (c) using, as said first template images, three vertex template images having vertices of vectors defined by matching region images on said search image at the three corners of each triangle region to determine interpolation parameters w that maximizes said normalized correlations with said reference template images, calculating the vertex position of a normalized interpolated template image defined by that one of the four interpolation parameters obtained for said four triangle regions which provides the maximum normalized correlation value, and determining said vertex position as said estimated position (x_s,y_s).

15. The method of claim 7 or 10, wherein said step (d) includes a step of performing said steps (a), (b) and (c) using, as said first template images, two vertex template images having vertices of vectors defined by matching region images in said search image at angular positions apart from said angle θ

_c by Δ

θ

on both sides thereof to determine an interpolation parameter w that maximizes said normalized correlation with said reference template image, and determining as an estimated position a vertex angular position of a normalized interpolated template image defined by said interpolation parameter.

16. A recording medium on which there is recorded a template matching procedure for matching an image with a plurality of template images to detect the maximum correlation value therebetween, said procedure comprising the steps of:

(a) calculating an inverse matrix H^-1 of a correlation matrix H using, as its elements, normalized correlations between a plurality of first template images;

(b) calculating normalized correlations between normalized images of said plurality of first template images and at least one normalized second template image to obtain a correlation vector G; and

(c) calculating from said correlation vector G and said inverse matrix H^-1 of said correlation matrix H an estimated parameter w that maximizes a normalized correlation between said normalized second template image and a normalized interpolated template image obtained by linearly combining, by said estimated parameter w, said normalized first template images.