Template matching method and image processing device

• US 7,085,418 B2
• Filed: 03/05/2002
• Issued: 08/01/2006
• Est. Priority Date: 03/06/2001
• Status: Expired due to Fees

• Current Assignee: Kabushiki Kaisha Toshiba (Toshiba Corporation)
• Original Assignee: Kabushiki Kaisha Toshiba (Toshiba Corporation)
• Inventors: Kaneko, Toshimitsu, Hori, Osamu
• Primary Examiner(s): Mehta, Bhavesh M.
• Assistant Examiner(s): SHAH, UTPAL D
• Application Number:
  US10/087,935
• Publication Number:
  US 20020154820A1
• Time in Patent Office: 1,610 Days
• Field of Search: 382216-221
• US Class Current: 382/219
• CPC Class Codes: G06T 7/20 Analysis of motion motion estimation for coding, decoding, compressing or decompressing digital video signals H04N19/43, H04N19/51

Abstract

A template matching method for searching a matching area having the highest correlation with a template including a reference point in a first image from a second image, the template matching method comprising calculating a difference between a corresponding point of the reference point in the second image and an estimated point of the reference point which is calculated by the template matching method, and determining at least one of parameters of the template matching, the parameters comprising the reference point, a size of the template and resolutions of the first and second images based on the difference.

Claims

1. A parameter determination method of a template matching searching from a second image a matching area having the highest correlation with a template including a reference point in a first image, method comprising:

calculating, based on the first image, a difference between a corresponding point in the second image corresponding to the reference point and a calculated point in the second image which is obtained by the template matching; and

determining, based on the difference, at least one of parameters of the template matching, the parameters comprising a location of the reference point, a size of the template and resolutions of the first and second images;

wherein the difference comprises an upper bound of average distance between the corresponding point and the calculated point.

2. The method according to claim 1, wherein the calculating calculates the following upper bound u:

$u=\underset{e\in <br><br>S}{\sum <br><br>}<br><br><br><br>e<br><br><br><br>P<br><br>\left(e\right)$

where, s is a searching range, e is an error vector, and P(e) is a probability that an error indicated by the error vector e is generated as a result of the template matching and is expressed as follows;

$P<br><br>\left(e\right)\le <br><br>\exp <br><br>\left\{-\frac{1}{2}<br><br>{\mathrm{NE}}_{\mathrm{TM}}<br><br>\left(e\right)\right\}$

where

$E_{\mathrm{TM}}<br><br>\left(e\right)=\underset{0<<br><br>\mathrm{\rho <br><br>}<<br><br>1}{\max }<br><br>E_{\mathrm{TM}}<br><br>\left(e,\mathrm{\rho <br><br>}\right),<br><br>E_{\mathrm{TM}}<br><br>\left(e,\mathrm{\rho <br><br>}\right)=R<br><br>\left\{{\mathrm{\gamma <br><br>}}_2^2<br><br>\frac{\mathrm{\rho <br><br>}}{1+\mathrm{\rho <br><br>}}+\log <br><br>\left(1-{\mathrm{\rho <br><br>}}^2\right)\right\}+\left(1-R\right)<br><br>{\mathrm{\gamma <br><br>}}_1^2<br><br>\mathrm{\rho <br><br>}<br><br>\left(1-\mathrm{\rho <br><br>}\right),<br><br>{\mathrm{\gamma <br><br>}}_1^2=\frac{1}{<br><br>W_1<br><br>}<br><br>\underset{p\in <br><br>W_1}{\sum <br><br>}<br><br>\frac{{\mathrm{\Delta <br><br>}}^2<br><br>\left(p,e\right)}{{\mathrm{\sigma <br><br>}}^2},{\mathrm{\gamma <br><br>}}_2^2=\frac{1}{<br><br>W_2<br><br>}<br><br>\underset{p\in <br><br>W_2}{\sum <br><br>}<br><br>\frac{{\mathrm{\Delta <br><br>}}^2<br><br>\left(p,e\right)}{{\mathrm{\sigma <br><br>}}^2}$

where W₁=W(O)∩

W(e), W₂=W^C(O)∩

W(e), and W₃=W(O)∩

W^c(e),

W^c represents complement of W,

W(O) is a template having the corresponding point as the center, and

W(e) is an area displaced by the error vector e.

3. An article of manufacture comprising a computer usable medium having computer readable program code means embodied therein, the computer readable program searching from a second image a matching area having the highest correlation with a template including a reference point in a first, the computer readable program code means comprising:

computer readable program code means for causing a computer to calculate, based on the first image, a difference between a corresponding point in the second image corresponding to the reference point a calculated point in the second image which is obtained by template matching; and

computer readable program code means for causing a computer to determine, based on the difference, at least one of parameters of the template matching, the parameters comprising a location of the reference point, a size of the template and resolutions of the first and second images;

wherein the difference comprises an upper bound of average distance between the corresponding point and the calculated point.

4. The article of manufacture according to claim 3, wherein the calculating calculates the following upper bound u:

$u=\underset{e\in <br><br>S}{\sum <br><br>}<br><br><br><br>e<br><br><br><br>P<br><br>\left(e\right)$

where, s is a searching range, e is an error vector, and P(e) is a probability that an error indicated by the error vector e is generated as a result of the template matching and is expressed as follows;

$P<br><br>\left(e\right)\le <br><br>\exp <br><br>\left\{-\frac{1}{2}<br><br>{\mathrm{NE}}_{\mathrm{TM}}<br><br>\left(e\right)\right\}$

where

$E_{\mathrm{TM}}<br><br>\left(e\right)=\underset{0<<br><br>\mathrm{\rho <br><br>}<<br><br>1}{\max }<br><br>E_{\mathrm{TM}}<br><br>\left(e,\mathrm{\rho <br><br>}\right),<br><br>E_{\mathrm{TM}}<br><br>\left(e,\mathrm{\rho <br><br>}\right)=R<br><br>\left\{{\mathrm{\gamma <br><br>}}_2^2<br><br>\frac{\mathrm{\rho <br><br>}}{1+\mathrm{\rho <br><br>}}+\log <br><br>\left(1-{\mathrm{\rho <br><br>}}^2\right)\right\}+\left(1-R\right)<br><br>{\mathrm{\gamma <br><br>}}_1^2<br><br>\mathrm{\rho <br><br>}<br><br>\left(1-\mathrm{\rho <br><br>}\right),<br><br>{\mathrm{\gamma <br><br>}}_1^2=\frac{1}{<br><br>W_1<br><br>}<br><br>\underset{p\in <br><br>W_1}{\sum <br><br>}<br><br>\frac{{\mathrm{\Delta <br><br>}}^2<br><br>\left(p,e\right)}{{\mathrm{\sigma <br><br>}}^2},{\mathrm{\gamma <br><br>}}_2^2=\frac{1}{<br><br>W_2<br><br>}<br><br>\underset{p\in <br><br>W_2}{\sum <br><br>}<br><br>\frac{{\mathrm{\Delta <br><br>}}^2<br><br>\left(p,e\right)}{{\mathrm{\sigma <br><br>}}^2}$

where W₁=W(O)∩

W(e), W₂=W^c(O)∩

W(e), and W₃=W(O)∩

W^c(e),

W^c represents complement of W,

W(O) is a template having the corresponding point as the center, and

W(e) is an area displaced by the error vector e.

5. An image processing device for searching from a second image a matching area having the highest correlation with a template including a reference point in a first image, comprising:

a calculation unit configured, based on the first I mage, to calculate a difference between a corresponding point in the second image corresponding to the reference point and a calculated point which is obtained by template matching; and

a determination unit configured to determine, based on the difference, at least one of parameters of the template matching, the parameters comprising a location of the reference point, a size of the template and resolutions of the first and second images;

wherein the difference comprises an upper bound of average distance between the corresponding point and the calculated point.

6. The image processing device according to claim 5, wherein the calculation unit is configured to calculate the following upper bound u:

$u=\underset{e\in <br><br>S}{\sum <br><br>}<br><br><br><br>e<br><br><br><br>P<br><br>\left(e\right)$

where, s is a searching range, e is an error vector, and P(e) is a probability that an error indicated by the error vector e is generated as a result of the template matching and is expressed as follows;

$P<br><br>\left(e\right)\le <br><br>\exp <br><br>\left\{-\frac{1}{2}<br><br>{\mathrm{NE}}_{\mathrm{TM}}<br><br>\left(e\right)\right\}$

where

$E_{\mathrm{TM}}<br><br>\left(e\right)=\underset{0<<br><br>\mathrm{\rho <br><br>}<<br><br>1}{\max }<br><br>E_{\mathrm{TM}}<br><br>\left(e,\mathrm{\rho <br><br>}\right),<br><br>E_{\mathrm{TM}}<br><br>\left(e,\mathrm{\rho <br><br>}\right)=R<br><br>\left\{{\mathrm{\gamma <br><br>}}_2^2<br><br>\frac{\mathrm{\rho <br><br>}}{1+\mathrm{\rho <br><br>}}+\log <br><br>\left(1-{\mathrm{\rho <br><br>}}^2\right)\right\}+\left(1-R\right)<br><br>{\mathrm{\gamma <br><br>}}_1^2<br><br>\mathrm{\rho <br><br>}<br><br>\left(1-\mathrm{\rho <br><br>}\right),<br><br>{\mathrm{\gamma <br><br>}}_1^2=\frac{1}{<br><br>W_1<br><br>}<br><br>\underset{p\in <br><br>W_1}{\sum <br><br>}<br><br>\frac{{\mathrm{\Delta <br><br>}}^2<br><br>\left(p,e\right)}{{\mathrm{\sigma <br><br>}}^2},{\mathrm{\gamma <br><br>}}_2^2=\frac{1}{<br><br>W_2<br><br>}<br><br>\underset{p\in <br><br>W_2}{\sum <br><br>}<br><br>\frac{{\mathrm{\Delta <br><br>}}^2<br><br>\left(p,e\right)}{{\mathrm{\sigma <br><br>}}^2}$

where W₁=W(O)∩

W(e), W₂=W^c(O)∩

W(e), and W₃=W(O)∩

W^C(e),

W^c represents complement of W,

W(O) is a template having the corresponding point as the center, and

W(e) is an area displaced by the error vector e.