Template matching apparatus and method thereof

• US 8,509,544 B2
• Filed: 03/02/2009
• Issued: 08/13/2013
• Est. Priority Date: 03/13/2008
• Status: Expired due to Fees

• Current Assignee: Kabushiki Kaisha Toshiba (Toshiba Corporation)
• Original Assignee: Kabushiki Kaisha Toshiba (Toshiba Corporation)
• Inventors: Ohmori, Yoshihiro
• Primary Examiner(s): Desire, Gregory M
• Application Number:
  US12/736,129
• Publication Number:
  US 20110002549A1
• Time in Patent Office: 1,625 Days
• Field of Search: 382/217, 382/218, 382/298
• US Class Current: 382/217
• CPC Class Codes: G06V 10/7515 Shifting the patterns to accommodate for positional errors
• CPC Class Codes: G06V 10/758 Involving statistics of pixels or of feature values, e.g. histogram matching
• CPC Class Codes: G06V 30/2504 Coarse or fine approaches, e.g. resolution of ambiguities or multiscale approaches

Abstract

A template matching apparatus includes a template input unit configured to input the template image; a signal input unit configured to input an image to be matched; a template scaling unit configured to scale the template image; a matching unit configured to match a scaled template image and an input image; a scaling factor determining unit configured to determine a scaling factor of the template image on the basis of a similarity obtained by matching; and a result output unit configured to output a result of matching when matching within a range of a predetermined scaling factor is completed.

Claims

1. A template matching apparatus comprising:

a signal input unit configured to input an input signal;

a matching unit configured to (1) obtain similarities between the input signal and a template at different search positions on the input signal, the template being an initial template having a predetermined initial size or a scaled template obtained by expanding or reducing the initial template by a given scaling factor, (2) obtain the similarities on the basis of a distribution of amount of characteristics of the template and a distribution of amount of characteristics in a search window on the input signal at respective search positions, and (3) obtain a highest similarity from among the similarities;

a limit value calculating unit configured to calculate an upper limit value of expansion or a lower limit value of reduction of the scaling factor of the template from the highest similarity so that the highest similarity obtained when the template is expanded or reduced does not exceed a threshold value;

a scaling unit configured to expand or reduce the template on the basis of the scaling factor within the upper limit value of expansion or the lower limit value of reduction; and

a repeat control unit configured to expand and reduce the template, by the scaling unit, until a template having a size included in a given range is achieved and repeat searching on the basis of the expanded or reduced template by the matching unit.

2. A template matching apparatus comprising:

a signal input unit configured to input an input signal;

a first matching unit configured to (1) obtain first similarities between the input signal and a template at different search positions on the input signal, the template being an initial template having a predetermined initial size or a scaled template obtained by expanding or reducing the initial template by a given scaling factor, (2) obtain the first similarities on the basis of a distribution of amount of characteristics of the template and a distribution of amount of characteristics in a search window on the input signal at respective search positions, and (3) obtain a highest first similarity from among the first similarities;

an estimating unit configured to estimate an estimated highest similarity for the input signal when the template is expanded or reduced on the basis of the highest first similarity;

a first limit value calculating unit configured to calculate an upper limit value and a lower limit value of the scaling factor of the template from the estimated highest similarity so that a highest similarity when the template is expanded or reduced does not exceed a threshold value;

a scaling unit configured to scale the template by the scaling factor within the scaling range determined by the upper limit value and the lower limit value;

a second matching unit configured to (1) obtain second similarities between the input signal and the scaled template while moving a search position on the input signal, (2) obtain the second similarities on the basis of a distribution of amount of characteristics on the scaled template and a distribution of amount of characteristics in a search window on the input signal at respective search positions and (3) obtain a highest second similarity among the second similarities;

a second limit value calculating unit configured to calculate a scaling range including an upper limit value of expansion or a lower limit value of reduction of the scaling factor of the template from the highest second similarity so that a highest similarity when the template is expanded or reduced does not exceed the threshold value;

a backtrack unit configured to change the scaling factor used in the scaling unit when the scaling range obtained by the second limit value calculating unit and the scaling range whereby a size of the template used by the first matching unit for searching is determined are not overlapped;

a renewing unit configured to control the estimating unit to use the highest second similarity instead of the highest first similarity when the scaling range obtained by the second limit value calculating unit and the scaling range whereby the size of the template used by the first matching unit for searching is determined are overlapped; and

a repeat control unit configured to expand or reduce the template, by the scaling unit, until the size of the template reaches a given range and repeat the search by the template expanded or reduced, by the first matching unit and the second matching unit.

3. The template matching apparatus according to claim 2, wherein when the first limit value calculating unit or the second limit value calculating unit expands or reduces the template having n dimensions at the scaling factor α

(where, α

>

0) which is a scaling factor in which the lengths of all dimensions of the n-dimensional template are the same scale, the first limit value calculating unit or the second limit value calculating unit calculates the upper limit value and the lower limit value of the scaling factor α

by;

S/θ

<

α

ⁿ<

1/(1+S−

θ

) 

 

(A)

where S (0≦

S≦

1) is a highest similarity of a previous time calculated by the first matching unit or the second matching unit, and θ

(0≦

θ

≦

1) is the threshold value.

4. The template matching apparatus according to claim 2, wherein the first matching unit or the second matching unit calculates the similarities on the basis of a normalized histogram intersection.

5. The template matching apparatus according to claim 4, wherein when expanding or reducing the template having n dimensions are scaled at the scaling factor α

(α

>

0) which is the scaling factor in which the lengths of all dimensions of the n-dimensional template are the same scale, the first matching unit or the second matching unit calculates a highest similarity of this time by a function S (*) shown by an expression (B), where S (0≦

S ≦

1) is a highest similarity calculated by a search of the previous time by the first matching unit or the second matching unit, θ

(0≦

θ

≦

1) is the threshold value, hw and ht are m-dimensional vectors which represent a histogram as the distribution of the amount of characteristics in the search window on the input signal and the distribution of the amount of characteristics of the template respectively, and hwi, hti are i^th histogram elements of the amount of characteristics in the search window on the input signal and the amount of characteristics of the template respectively,

wherein the the first limit value calculating unit or the second limit value calculating unit calculates the upper limit value and the lower limit value of the scaling factor α

by a following expression (C);

6. The template matching apparatus according to claim 2, wherein when expanding or reducing at the scaling factor α

i (α

i>

0 and 1<

i<

n) in which the lengths of respective dimensions of the n-dimensional template are different, the first limit value calculating unit or the second limit value calculating unit calculates the upper limit value and the lower limit value of the scaling factor α

by a following expression (D);

7. The template matching apparatus according to claim 2, wherein the first matching unit or the second matching unit divides the input signals into a plurality of regions and performs the search individually for the respective divided regions.

8. The template matching apparatus according to claim 2, wherein the first matching unit or the second matching unit calculates the similarity using a norm on the basis of an average brightness value.

9. A computer-implemented template matching method executed by a processor of a computer apparatus, the method comprising:

inputting an input signal;

(1) obtaining first similarities between the input signal and a template at different search positions on the input signal, the template being an initial template having a predetermined initial size or a scaled template obtained by expanding or reducing the initial template by a given scaling factor, (2) obtaining the first similarities on the basis of a distribution of an amount of characteristics of the template and a distribution of an amount of characteristics in a search window on the input signal at respective search positions, and (3) obtaining a highest first similarity from among the first similarities;

estimating an estimated highest similarity for the input signal when the template is expanded or reduced on the basis of the highest first similarity;

calculating an upper limit value and a lower limit value of the scaling factor of the template from the estimated highest similarity so that a highest similarity when the template is expanded or reduced does not exceed a threshold value;

scaling the template by the scaling factor within the scaling range determined by the upper limit value and the lower limit value;

(1) obtaining second similarities between the input signal and the scaled template while moving a search position on the input signal, (2) obtaining the second similarities on the basis of a distribution of the amount of characteristics on the scaled template and a distribution of the amount of characteristics in a search window on the input signal at respective search positions, and (3) obtaining a highest second similarity among the second similarities;

calculating a scaling range including an upper limit value of expansion or a lower limit value of reduction of the scaling factor of the template from the highest second similarity so that a highest similarity when the template is expanded or reduced does not exceed the threshold value;

changing the scaling factor when the scaling range including the upper limit value of expansion or the lower limit value of reduction of the scaling factor of the template and the scaling range whereby a size of the template used to obtain the first similarities is determined are not overlapped;

controlling the highest second similarity to be used in the estimating instead of the highest first similarity when the scaling range including the upper limit value of expansion or the lower limit value of reduction of the scaling factor of the template and the scaling range whereby the size of the template used to obtain the first similarities are overlapped; and

expanding or reducing the template until the size of the template reaches a given range and repeating the search on the basis of the expanded or reduced template.

10. A non-transitory computer-readable medium including a template matching program stored thereon, which when executed, causes a computer, to perform operations comprising:

inputting an input signal;

(1) obtaining first similarities between the input signal and a template at different search positions on the input signal, the template being an initial template having a predetermined initial size or a scaled template obtained by expanding or reducing the initial template by a given scaling factor, (2) obtaining the first similarities on the basis of a distribution of an amount of characteristics of the template and a distribution of an amount of characteristics in a search window on the input signal at respective search positions, and (3) obtaining a highest first similarity from among the first similarities;

estimating an estimated highest similarity for the input signal when the template is expanded or reduced on the basis of the highest first similarity;

calculating an upper limit value and a lower limit value of the scaling factor of the template from the estimated highest similarity so that a highest similarity when the template is expanded or reduced does not exceed a threshold value;

scaling the template by the scaling factor within the scaling range determined by the upper limit value and the lower limit value;

(1) obtaining second similarities between the input signal and the scaled template while moving a search position on the input signal, (2) obtaining the second similarities on the basis of a distribution of the amount of characteristics on the scaled template and a distribution of the amount of characteristics in a search window on the input signal at respective search positions, and (3) obtaining a highest second similarity among the second similarities;

calculating a scaling range including an upper limit value of expansion or a lower limit value of reduction of the scaling factor of the template from the highest second similarity so that a highest similarity when the template is expanded or reduced does not exceed the threshold value;

changing the scaling factor when the scaling range including the upper limit value of expansion or the lower limit value of reduction of the scaling factor of the template and the scaling range whereby a size of the template used to obtain the first similarities is determined are not overlapped;

controlling the highest second similarity to be used in the estimating instead of the highest first similarity when the scaling range including the upper limit value of expansion or the lower limit value of reduction of the scaling factor of the template and the scaling range whereby the size of the template used to obtain the first similarities are overlapped; and

expanding or reducing the template until the size of the template reaches a given range and repeating the search on the basis of the expanded or reduced template.