Flash system for fast and accurate pattern localization

• US 6,546,137 B1
• Filed: 01/25/1999
• Issued: 04/08/2003
• Est. Priority Date: 01/25/1999
• Status: Expired due to Fees

• Current Assignee: Siemens Corp. (Siemens AG)
• Original Assignee: Siemens Corporate Research Incorporated (Siemens AG)
• Inventors: Fang, Ming, Lai, Shang-Hong
• Primary Examiner(s): Mehta, Bhavesh M.
• Assistant Examiner(s): AZARIAN, SEYED H
• Application Number:
  US09/236,725
• Time in Patent Office: 1,534 Days
• Field of Search: 382/217, 382/226, 382/147, 382/209, 382/141, 382/157, 382/259, 382/220, 382/107, 382/195, 382/294, 382/129, 382/105, 382/216, 382/243, 382/278, 340/934, 340/935, 340/937, 700/83, 700/85
• US Class Current: 382/217
• CPC Class Codes: G06T 7/0004 Industrial image inspection
• 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

Abstract

A fast localization with advanced search hierarchy system for fast and accurate object localization in a large search space is based on an assumption that surrounding regions of a pattern within a search range are always fixed. The FLASH system comprises a hierarchical nearest-neighbor search system and an optical-flow based energy minimization system. The hierarchical nearest-neighbor search system produces rough estimates of the transformation parameters for the optical-flow based energy minimization system which provides very accurate estimation results and associated confidence measures.

Claims

1. A method for providing pattern localization, comprising the steps of:

applying a window template to a desired portion of an input image,

computing an input feature vector representing the image within the window template;

comparing the input feature vector with a plurality of reference feature vectors to find a best match, each reference feature vector representing a corresponding one of a plurality of spatially-transformed reference image templates associated with a reference image;

estimating spatial transformation parameters of the image within the window template based on the best match; and

processing the estimated spatial transformation parameters to obtain a more precise localization of a desired pattern of the input image within the window template.

3. The method of claim 1, wherein the step of processing the estimated spatial transformation parameters comprises the step of utilizing an iterative energy minimization process.

4. The method of claim 1, wherein the step of computing the input feature vector comprises the steps of:

resampling the image within the window template;

normalizing the resampled image;

wavelet transforming the normalized image; and

selecting desired waveform coefficients for generating the input feature vector.

5. The method of claim 1, further comprising the steps of:

generating the plurality of reference feature vectors; and

training a hierarchical competitive layer neural network using the plurality of reference feature vectors, wherein the step of comparing is performed using the trained hierarchical competitive layer neural network.

6. The method of claim 5, wherein the step of generating the plurality of reference feature vectors comprises the steps of:

generating a plurality of reference image templates from a reference image;

spatially-transforming each reference image template by applying at least one transformation parameter vector to each reference image template; and

generating a reference feature vector from the image within each spatially-transformed reference image template.

7. The method of claim 6, wherein the step of generating a reference feature vector comprises the steps of:

resampling the image within each of the spatially-transformed reference image templates;

normalizing each resampled image;

wavelet transforming each normalized image; and

selecting desired waveform coefficients from each wavelet transform to generate corresponding reference feature vectors.

8. The method of claim 6, wherein the transformation parameter vectors are selected from a predetermined set.

2. The method of claim wherein the spatial transformation parameters include parameters of one of an affine transformation and a 2D rigid transformation comprising scaling and rotation transformations.

9. A system for providing pattern localization, comprising:

a feature vector generator for computing an input feature vector representing an input image within a window template;

a comparator for selecting a best match between the input feature vector and a reference feature vector from a set of reference features vectors, each reference feature vector in the set representing a corresponding one of a plurality of spatially-transformed reference image templates associated with a reference image;

an estimator adapted to estimate the spatial transformation parameters of the input image based on the best match; and

a processor adapted to process the estimated spatial transformation parameters to obtain a more precise localization of a desired pattern of the input image within the template window.

10. The system of claim 9, wherein the spatial transformation parameters include parameters of one of an affine transformation and a 2D rigid transformation comprising scaling and rotation transformations.

11. The system of claim 9, wherein the processor is adapted to estimate the spatial transformation parameters utilizing an iterative energy minimization process.

12. The system of claim 9, wherein the input feature vector generator comprises:

means for resampling the input image within the window template;

means for normalizing the resampled image;

means for wavelet transforming the normalized image; and

means for selecting desired waveform coefficients to generate the input feature vector.

13. The system of claim 9, further comprising:

a reference feature vector generator adapted to generate a plurality of reference feature vectors; and

a trainer adapted to train a hierarchical competitive layer neural network using the plurality of reference feature vectors, wherein the comparator implements the trained hierarchical competitive layer neural network.

14. The system of claim 13, wherein the reference feature vector generator comprises:

means for generating a plurality of reference image templates from a reference image;

means for spatially-transforming each reference image template by applying at least one transformation parameter vector to each reference image template; and

means for generating a reference feature vector from the image within each spatially-transformed reference image template.

15. The system of claim 14, wherein the means for generating a reference feature vector comprises:

means for resampling the image within each of the spatially-transformed reference image templates;

means for normalizing each resampled image;

means for wavelet transforming each normalized image; and

means for selecting desired waveform coefficients from each wavelet transform to generate corresponding reference feature vectors.

16. The system of claim 14, wherein the transformation parameter vectors are selected from a predetermined set.

17. A program storage device readable by a machine, tangibly embodying a program of instructions executable by the machine to perform method steps for providing pattern localization, the method steps comprising:

applying a window template to a desired portion of an input image;

computing an input feature vector representing the image within the window template;

comparing the input feature vector with a plurality of reference feature vectors to find a best match, each reference feature vector representing a corresponding one of a plurality of spatially-transformed reference image templates associated with a reference image;

estimating spatial transformation parameters of the image within the window template based on the best match; and

processing the estimated spatial transformation parameters to obtain a more precise localization of a desired pattern of the input image within the window template.