Template Matching Method, Template Matching Apparatus, And Recording Medium That Records Program For It

• US 20080273800A1
• Filed: 01/11/2006
• Published: 11/06/2008
• Est. Priority Date: 01/11/2005
• Status: Active Grant

• Current Assignee: NEC Corporation
• Original Assignee: NEC Corporation
• Inventors: Hatabu, Atsushi
• Granted Patent: US 7,813,558 B2
• Time in Patent Office: Days
• US Class Current: 382/209
• CPC Class Codes: G06T 7/74 involving reference images or patches
• CPC Class Codes: G06V 10/7515 Shifting the patterns to accommodate for positional errors
• CPC Class Codes: G06V 30/2504 Coarse or fine approaches, e.g. resolution of ambiguities or multiscale approaches

Abstract

There is provided a template matching method having a small amount of calculation and high detection accuracy. The amount of calculation is reduced while minimizing the degradation of the detection accuracy by calculating the similarity between a template image region and a reference image region at rough position intervals and estimating by interpolation of the similarity at a position where it is not calculated from the similarity calculated at a peripheral position. At the time, even if the gradient of a similarity greatly changes at the minimal point, estimation can be realized with high accuracy by executing estimation making use of the directional gradients of the similarity obtained in plural different directions independently. Additionally, occurrence of wrong detection is avoided by the restriction to disable the difference between the estimated similarity and adjacent similarity to exceed a threshold, which is defined based on the similarity between the template image region and the image region obtained by moving the template image region in the same direction as or in the opposite direction to the direction of estimation.

Claims

1. A template matching method of detecting the position of an image region similar to a template image region from on a reference image, comprising:

calculating the similarity of the image region to the template image region at rough position intervals;

estimating the similarity at a position, where the similarity is not calculated, making use of the directional gradients of similarity obtained independently in a plurality of directions from the calculated values of similarity; and

determining the position having a small calculated or estimated value of the similarity as the position of the similar image region.

2. A template matching method according to claim 1, wherein estimating the similarity makes use of the similarity estimated up to that time in addition to the calculated values of similarity.

3. A template matching method of narrowing down the position of a similar image region stepwise based on a multistep search method, comprising detecting the position of the similar image region by the template matching method according to claim 1 at a search step before the final step thereof.

4. A template matching method according to claim 1 further comprising restricting the value range of the estimated similarity value such that the difference between the estimated similarity value and the similarity of a periphery used for the estimation or the gradient of the similarity does not exceed a threshold value.

5. A template matching method according to claim 4, further comprising determining the threshold value based on the magnitude of the similarity calculated from the template image region and an image region, which is obtained by moving the template image region in the same direction as or in the opposite direction to an estimation direction vector obtained by subtracting the position of the nearby image region from the position where the similarity is estimated.

6. A template matching method according to claim 1, further comprising estimating, when five reference image regions A, B, C, D, E are sequentially located on a straight line, the degree of similarity at the position C from an interpolation value extrapolated assuming gradient continuity from the similarity in the image regions A, B and from an interpolation value extrapolated assuming gradient continuity from the similarity in the image regions D, E in the estimation of the degree of similarity.

7. A template matching apparatus for detecting the position of an image region similar to a template image region from on a reference image, comprising:

means for calculating the similarity of the image region to the template image region at rough position intervals;

means for estimating the similarity at a position, where the similarity is not calculated, making use of the gradients of the similarity obtained independently in a plurality of directions from the calculated values of similarity; and

means for determining the position having a small calculated or estimated value of the similarity as the position of the similar image region.

8. A template matching apparatus according to claim 7, further comprising means for estimating the degree of similarity making use of the similarity estimated up to that time in addition to the calculated values of similarity.

9. A template matching apparatus for narrowing down the position of a similar image region stepwise based on a multistep search method, further comprising detecting the position of the similar image region by the template matching apparatus according to claim 7 at a search step before the final step thereof.

10. A template matching apparatus according to claim 7, further comprising means for restricting the value range of the estimated similarity value such that the difference between the estimated similarity value and the similarity of a periphery used for the estimation or the gradient of the similarity does not exceed a threshold value.

11. A template matching method according to claim 10, further comprising means for determining the threshold value based on the magnitude of the similarity calculated from the template image region and an image region, which is obtained by moving the template image region in the same direction as or in the opposite direction to an estimation direction vector obtained by subtracting the position of the nearby image region from the position where the degree of similarity is estimated.

12. A template matching method according to claim 7 further comprising means for estimating, when five reference image regions A, B, C, D, E are sequentially located on a straight line, the degree of similarity at the position C from an interpolation value extrapolated assuming gradient continuity from the similarity in the image regions A, B and from an interpolation value extrapolated assuming gradient continuity from the similarity in the image regions D, E in the estimation of the degree of similarity.

13. A computer readable recording medium that records a program for causing a computer to execute a template matching method of detecting the position of an image region similar to a template image region from on a reference image, wherein:

the method calculates the similarity of the image region to the template image region at rough position intervals;

the method estimates the similarity at a position, where the similarity is not calculated, making use of the gradients of similarity obtained independently in a plurality of directions from the calculated values of similarity; and

the method determines the position having a small calculated or estimated value of the similarity as the position of the similar image region.

14. A recording medium according to claim 13, wherein the degree of similarity is estimated making use of a similarity estimated up to that time in addition to the calculated values of similarity.

15. A computer readable recording medium that records a program for causing a computer to execute a template matching method of narrowing down the position of a similar image region stepwise based on a multistep search method, characterized in that the template matching method detects the position of the similar image region by being executed by a computer based on a program recorded on the recording medium according to claim 13 at a search step before the final step thereof.

16. A recording medium according to claim 13, wherein the method restricts the value range of the estimated similarity value such that the difference between the estimated similarity value and the similarity of a periphery used for the estimation or the gradient of the similarity does not exceed a threshold value.

17. A recording medium according to claim 16, wherein the method determines the threshold value based on the magnitude of the similarity calculated from the template image region and an image region, which is obtained by moving the template image region in the same direction as or in the opposite direction to an estimation direction vector obtained by subtracting the position of the nearby image region from the position where the degree of similarity is estimated.

18. A recording medium according to claim 13, wherein the method estimates, when five reference image regions A, B, C, D, E are sequentially located on a straight line, the degree of similarity at the position C from an interpolation value extrapolated assuming gradient continuity from the similarity in the image regions A, B and from an interpolation value extrapolated assuming gradient continuity from the similarity in the image regions D, E in the estimation of the degree of similarity.