System and method for object recognition

• US 7,062,093 B2
• Filed: 09/26/2001
• Issued: 06/13/2006
• Est. Priority Date: 09/27/2000
• Status: Active Grant

• Current Assignee: MvTec Software GmbH (MvTec LLC)
• Original Assignee: MvTec Software GmbH (MvTec LLC)
• Inventors: Steger, Carstan
• Primary Examiner(s): CHANG, JON CARLTON
• Application Number:
  US09/965,236
• Publication Number:
  US 20020057838A1
• Time in Patent Office: 1,721 Days
• Field of Search: 382/215, 382/216, 382/240, 382/217, 382/218
• US Class Current: 382/216
• CPC Class Codes: G06V 10/7515 Shifting the patterns to accommodate for positional errors

Abstract

A system and method recognize a user-defined model object within an image. The system and method recognize the model object with occlusion when the model object to be found is only partially visible. The system and method also recognize the model object with clutter when there may be other objects in the image, even within the model object. The system and method also recognize the model object with non-linear illumination changes as well as global or local contrast reversals. The model object to be found may have been distorted, when compared to the user-defined model object, from geometric transformations of a certain class such as translations, rigid transformations by translation and rotation, arbitrary affine transformations, as well as similarity transformations by translation, rotation, and scaling.

Claims

1. A method for recognizing model object in a first image comprising the steps of:

(a) acquiring in electronic memory the first image of the model object;

(b) transforming the first image of the model object into a multi-level representation consistent with a recursive subdivision of a search space, said multi-level representation including at least the first image;

(c) generating at least one precomputed model of the model object for each level of discretization of the search space, said precomputed model consisting of a plurality of model points with corresponding direction vectors, said model points and direction vectors being generated by an image processing operation that returns a direction vector for at least each model point;

(d) acquiring in electronic memory a current image;

(e) transforming the current image into a multi-level representation consistent with a recursive subdivision of the search space, said multi-level representation including at least the current image;

(f) performing an image processing operation on each transformed image of the multi-level representation that returns a direction vector for a subset of model points within said current image that corresponds to the range of translations for which the at least one precomputed model should be searched;

(g) computing a match metric that uses the direction information of the at least one precomputed model and the transformed image for all possible model poses of the at least one precomputed model in the coarsest discretization level of the search space;

(h) determining those model poses whose match metric exceeds a user-selectable threshold and whose match metric is locally maximal, and generating a list of instances of the at least one precomputed model in the coarsest discretization level of the search space from said model poses and said match metrics;

(i) tracking said instances of the at least one precomputed model in the coarsest discretization level of the search space through the recursive subdivision of the search space until a finest level of discretization is reached; and

(j) providing the model pose of the instances of the model object on the finest level of discretization.

3. The method of claim 1, wherein for each level of the discretization according to step (b) the following steps are performed:

(c1) performing feature extraction in the first image of the current level of discretization, and for each transformation in the discretized search space at the current level of discretization;

(c2) transforming the extracted model points and direction vectors by the current transformation; and

(c3) adding all transformed model points along with their transformed direction vectors to the list of instances of the at least one precomputed model.

5. The method of claim 3, wherein step (i) is followed by the following step:

(i′

) discarding overlapping and/or extraneous instances from the list of instances.

20. A computer program product comprising program code means stored on a computer readable medium for performing the method of claim 1 when said computer program product is run on a computer.

2. A method for recognizing a model object in a first image comprising the steps of:

(a) acquiring in electronic memory the first image of the model object;

(b) transforming the first image of the model object into a multi-level representation consistent with a recursive subdivision of a search space, said multi-level representation including at least the first image;

(c) generating at least one precomputed model of the model object for each level of discretization of the search space, said precomputed model consisting of a plurality of model points with corresponding direction vectors, said model points and direction vectors being generated by an image processing operation that returns a direction vector for at least each model point;

(d) acquiring in electronic memory a current image;

(e) transforming the current image into a multi-level representation consistent with a recursive subdivision of the search space, said multi-level representation including at least the current image;

(f) performing an image processing operation on each transformed image of the multi-level representation that returns a direction vector for a subset of model points within said current image that corresponds to the range of translations for which the at least one precomputed model should be searched;

(g) computing a match metric that uses the direction information of the at least one precomputed model and the transformed image for all possible model poses of the at least one precomputed model in the coarsest discretization level of the search space;

(h) determining those model poses whose match metric exceeds a user-selectable threshold and whose match metric is locally maximal, and generating a list of instances of the at least one precomputed model in the coarsest discretization level of the search space from said model poses and said match metrics;

(i) tracking said instances of the at least one precomputed model in the coarsest discretization level of the search space through the recursive subdivision of the search space until a finest level of discretization is reached; and

(j) providing the model pose of the instances of the model object on the finest level of discretization;

wherein in step (c) for each level of discretization according to step (b), and for each transformation in the discretized search space at the current level of discretization according to step (b) the following steps are performed;

(c1) transforming the first image of the current level of discretization by the current transformation using anti-aliasing methods;

(c2) performing feature extraction in the transformed image to generate at least one feature points; and

(c3) adding any segmented feature points along with their direction vectors to the list of instances of the at least one precomputed model.

4. The method of claim 2, wherein step (i) is followed by the following step:

(i′

) discarding overlapping and/or extraneous instances from the list of instances.

6. The method of claim 4, wherein step (i′

) is followed by the following step;

(ii″

) refining the pose information to a resolution higher than the finest discretization level.

7. The method of claim 6, wherein (ii″

) further comprises the step of extrapolating the maxima of the match metric.

8. The method of claim 7, wherein (ii″

) is followed by the following steps to further refine the model pose;

(iii′

″

) extracting feature points in at least the first image;

(iv′

″

) robustly finding the correspondences between model points and feature points; and

(v′

″

) minimizing the average distance of the model points to the feature points using a least-squares fitting algorithm.

9. The method of claim 7, wherein each of the steps (c) and (f) further comprises the step of performing feature extraction in the transformed image representation.

10. The method of claim 9, wherein at least one of line filtering, edge filtering, corner detection, and region-based segmentation is used for the feature extraction.

11. The method of claim 10, wherein in step (g) the sum of the dot product of the direction vectors of the transformed model and the first image over all model points of the at least one precomputed model is used for computing said match metric.

12. The method of claim 10, wherein the sum of the normalized dot product of the direction vectors of the transformed model and the first image over all model points of the at least one precomputed model is used for computing said match metric.

13. The method of claim 10, wherein the absolute value of the sum of a normalized dot product is used for computing said match metric.

14. The method of claim 10, wherein the sum of the absolute values of a plurality of normalized dot products is used for computing said match metric.

15. The method of claim 10, wherein in step (g) the sum of the absolute values of the angles that the direction vectors in the at least one precomputed model and the direction vectors in the first image is used for computing said match metric and where the local minima of the match metric are used to extract the pose information instead of the local maxima.

16. The method of claim 12, wherein the contribution of direction vectors that are caused by noise is discarded.

17. The method of claim 13, wherein the contribution of direction vectors that are caused by noise is discarded.

18. The method of claim 14, wherein the contribution of direction vectors that are caused by noise is discarded.

19. A system for recognizing model object in a first image comprising:

(a) means for acquiring in electronic memory a first image of the model object;

(b) means for transforming the fist image of the model object into a multi-level representation consistent with a recursive subdivision of a search space, said multi-level representation including at least the first image;

(c) means for generating at least one precomputed model of the model object for each level of discretization of the search space, said precomputed model consisting of a plurality of model points with corresponding direction vectors, said model points and direction vectors being generated by an image processing operation that returns a direction vector for at least each model point;

(d) means for acquiring in electronic memory a current image;

(e) means for transforming the current image into a multi-level representation consistent with a recursive subdivision of the search space, said multi-level representation including at least the current image;

(f) means for performing an image processing operation on each transformed image of the multi-level representation that returns a direction vector for a subset of model points within said current image that corresponds to the range of translations for which the at least one precomputed model should be searched;

(g) means for computing a match metric that uses the direction information of the at least one precomputed model and the transformed image for all possible model poses of the at least one precomputed model in the coarsest discretization level of the search space;

(h) means for determining those model poses whose match metric exceeds a user-selectable threshold and whose match metric is locally maximal, and generating a list of instances of the at least one precomputed model in the coarsest discretization level of the search space from said model poses and said match metrics;

(i) means for tracking said instances of the at least one precomputed model in the coarsest discretization level of the search space through the recursive subdivision of the search space until a finest level of discretization is reached; and

(j) means for providing the model pose of the instances of the model object on the finest level of discretization.