On optimizing template matching via performance characterization

• US 7,865,019 B2
• Filed: 07/26/2006
• Issued: 01/04/2011
• Est. Priority Date: 07/27/2005
• Status: Active Grant

• Current Assignee: Siemens Corp. (Siemens AG)
• Original Assignee: Siemens Corp. (Siemens AG)
• Inventors: Han, Tony X., Ramesh, Visvanathan, Zhu, Ying
• Primary Examiner(s): Ahmed; Samir A.
• Assistant Examiner(s): HU, FRED H.
• Application Number:
  US11/493,311
• Publication Number:
  US 20070025594A1
• Time in Patent Office: 1,623 Days
• Field of Search: None
• US Class Current: 382/209
• CPC Class Codes: G06T 7/33 using feature-based methods
• CPC Class Codes: G06T 7/35 using statistical methods
• CPC Class Codes: G06V 10/7515 Shifting the patterns to accommodate for positional errors

Abstract

The performance of template matching is characterized by deriving the distribution of warp parameter estimate as a function of the ideal template, the ideal warp parameters and a given perturbation or noise model. An expression for the Probability Mass Function of the parameter estimate is provided. The optimal template size for template matching is the one that provides the best matching performance which is calculated from the minimum entropy of the parameter estimate.

Claims

1. A method for tracking a data object in a plurality of consecutive images by evaluating a first image and a sequential second image comprising the steps:

a) constructing from the first image a template candidate region containing a landmark image feature;

b) for the template candidate region, deriving by a processor from the first image an optimally sized template by minimizing an entropy of a predictive probability distribution of a warp estimate that is a function of a template size, image data of the first image, and a prior probability distribution over a plurality of warp parameters;

d) identifying a second landmark in the second image by template matching using an estimated warp parameter;

e) assigning the second image as the first image and assigning a third image sequential to the second image as the second image; and

g) repeating steps a) to e) until the plurality of consecutive images has been evaluated.

2. The method of claim 1, wherein the optimal size of a template is determined by evaluating a theoretical performance model for template matching.

3. The method of claim 2, wherein the theoretical performance model is a statistical model.

4. The method of claim 2, wherein the theoretical performance model is a predictive model.

5. The method of claim 2, wherein the theoretical performance model is a statistical and a predictive model.

6. The method of claim 2, wherein the theoretical performance model is a function of image data around a landmark.

7. The method of claim 2, wherein the theoretical performance model is a function of a noise parameter in the first image.

8. The method of claim 2, wherein the theoretical performance model is a function of a range of assumed warps between the first image and the second image.

9. The method of claim 2, wherein the theoretical performance model is described by a predictive probability distribution of an estimated warp parameter.

10. The method of claim 9, wherein a predictive probability distribution computation can be approximated as

11. The method of claim 9, wherein the predictive probability distribution is depending on the size of the template.

12. The method of claim 11, wherein the size of the template is optimal when the entropy of the predictive probability distribution is minimal.

13. A system to process an image from image data, including:

a processor;

application software operable on the processor for tracking a data object in a plurality of consecutive images by evaluating a first image and a sequential second image comprising the steps;

a) constructing from the first image a template candidate region containing a landmark image feature;

b) for the template candidate region, deriving from the first image an optimally sized template by minimizing an entropy of a predictive probability distribution of a warp estimate that is a function of a template size, image data of the first image, and a prior probability distribution over one or more warp parameters;

c)

d) identifying a second landmark in the second image by template matching using an estimated warp parameter;

e) assigning the second image as the first image and assigning a third image sequential to the second image as the second image; and

g) repeating steps a) to e) until the plurality of consecutive images has been evaluated.

14. The system of claim 13, wherein the optimal size of a template is determined by evaluating a theoretical performance model for template matching.

15. The system of claim 14, wherein the theoretical performance model is a statistical model.

16. The system of claim 14, wherein the theoretical performance model is a predictive model.

17. The system of claim 14, wherein the theoretical performance model is a statistical and a predictive model.

18. The system of claim 14, wherein the theoretical performance model is a function of image data around a landmark.

19. The system of claim 14, wherein the theoretical performance model is a function of a noise parameter in the first image.

20. A method for tracking a data object in a plurality of consecutive images by evaluating a first image and a sequential second image comprising the steps:

a) constructing a plurality of template candidate regions (L1, L2, . . . Lk) from landmark locations;

b) for each of the plurality of template candidate regions, deriving by a processor an optimally sized template (L1, S1), (L2, S2), . . . (Lk, Sk) using a performance model;

c) estimating warp parameters (W1, W2, . . . Wk) that minimize a measure of distance between a warped template of optimal size and a candidate region in the second image;

d) identifying second landmarks in the second image by using the estimated warp parameters;

e) assigning the second image as the first image and assigning a third image sequential to the second image as the second image;

f) selecting landmark locations in the first image;

g) repeating steps a) to f) until all sequential images have been evaluated; and

wherein the optimal size of a template is determined by evaluating a theoretical performance model for template matching that is described by a predictive probability distribution of an estimated warp parameter and wherein a predictive probability distribution computation can be approximated as