SYSTEM AND METHOD FOR DEFORMABLE OBJECT RECOGNITION

• US 20090185715A1
• Filed: 05/05/2008
• Published: 07/23/2009
• Est. Priority Date: 01/18/2008
• Status: Active Grant

• Current Assignee: MvTec Software GmbH (MvTec LLC)
• Original Assignee: MvTec Software GmbH (MvTec LLC)
• Inventors: Hofhauser, Andreas, Steger, Carsten
• Granted Patent: US 8,260,059 B2
• Time in Patent Office: Days
• US Class Current: 382/103
• CPC Class Codes: G06V 10/754 involving a deformation of the sample pattern or of the reference pattern; Elastic matching

Abstract

The present invention provides a system and method for detecting deformable objects in images even in the presence of partial occlusion, clutter and nonlinear illumination changes. A holistic approach for deformable object detection is disclosed that combines the advantages of a match metric that is based on the normalized gradient direction of the model points, the decomposition of the model into parts and a search method that takes all search results for all parts at the same time into account. Despite the fact that the model is decomposed into sub-parts, the relevant size of the model that is used for the search at the highest pyramid level is not reduced. Hence, the present invention does not suffer the speed limitations of a reduced number of pyramid levels that prior art methods have.

Claims

1. A method for recognizing a model object in images, under general nonlinear deformations, comprising the steps of:

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

(b) transforming the 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 image of the object;

(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 each model point;

(d) generating a subdivision of said plurality of model points into a plurality of parts, where a deformed instance of the model is represented by transforming the parts;

(e) acquiring in electronic memory a search image;

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

(g) 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 search image that corresponds to the range of transformations for which the at least one precomputed model should be searched;

(h) computing a global match metric that combines the results of a local metric, where for the local metric the parts of the model are searched in a restricted range of transformations close to the precomputed model and the maximal fit of each part is taken as the contribution of said part to the global match metric;

(i) 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 the model poses;

(j) computing a deformation transformation that describes the local displacements of the parts;

(k) 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;

(l) computing at each level the respective deformation transformation and propagating said deformation transformation to the next level; and

(m) providing the model pose and the deformation transformation of the instances of the model object on the finest level of discretization.

2. The method of claim 1, wherein the location of the parts is determined at a resolution that is higher than the finest discretization level.

3. The method of claim 2, wherein additionally to the user-selectable threshold only up to a user-selectable number maximum of the best instances of hypothesis are generated into the list of possible matches on the coarsest discretization level.

4. The method of claim 3, wherein the score for the local match metric of each part must exceed a local user-selectable threshold, otherwise the part is assumed to be occluded and discarded from further processing.

5. The method of claim 4, wherein each part is composed of a number of points where the subdivision generates overlapping points set.

6. The method of claim 4, wherein each part is composed of a number of points where the points set are disjunctive sets.

7. The method of claim 6, wherein the subdivision is done using k-means clustering.

8. The method of claim 6, wherein the subdivision is done using normalized cuts.

9. The method of claim 4, wherein the computed transformation is a perspective transformation.

10. The method of claim 4, wherein the model generation additionally receives as input metric information about the internal geometry of the imaging device and the model and the computed transformation is a 3D pose.

11. The method of claim 4, wherein the computed transformation is a thin-plate spline.

12. The method of claim 4, wherein the computed transformation is a cylindrical transformation.

13. The method of claim 4, wherein the computed transformation is a harmonic interpolation.

14. The method of claim 4, wherein the sum of the normalized dot product of the direction vectors of the transformed model part and the search image is used in the local score metric.

15. The method of claim 4, wherein the absolute value of the sum of the normalized dot product of the direction vectors of the transformed model part and the search image is used in the local score metric.

16. The method of claim 4, wherein the sum of absolute value of the normalized dot product of the direction vectors of the transformed model part and the search image is used in the local score metric.

18. A computer-readable medium having computer-executable instructions for performing the method of claim 1.

17. A system for recognizing an object in images under general nonlinear deformations, comprising:

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

(b) means for transforming the 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 image of the object;

(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 each model point;

(d) means for generating a subdivision of said plurality of model points into a plurality of parts, where a deformed instance of the model is represented by transforming the parts;

(e) means for acquiring in electronic memory a search image;

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

(g) 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 search image that corresponds to the range of transformations for which the at least one precomputed model should be searched;

(h) means for computing a global match metric that combines the results of a local metric, where for the local metric the parts of the model are searched in a restricted range of transformations close to the precomputed model and the maximal fit of each part is taken as the contribution of said part to the global match metric;

(i) 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 the model poses;

(j) means for computing a deformation transformation that describes the local displacements of the parts;

(k) 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;

(l) means for computing at each level the respective deformation transformation and propagating said deformation transformation to the next level; and

(m) means for providing the model pose and the deformation transformation of the instances of the model object on the finest level of discretization.

19. A system for recognizing an object in images under general nonlinear deformations comprising an imaging device, a memory and a processor, the memory adapted to acquire an image of the model object, the processor adapted to:

(a) transform the 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 image of the object;

(b) generate 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 each model point;

(c) generate a subdivision of said plurality of model points into a plurality of parts, where a deformed instance of the model is represented by transforming the parts;

(d) acquire in electronic memory a search image;

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

(f) perform 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 search image that corresponds to the range of transformations for which the at least one precomputed model should be searched;

(g) compute a global match metric that combines the results of a local metric, where for the local metric the parts of the model are searched in a restricted range of transformations close to the precomputed model and the maximal fit of each part is taken as the contribution of said part to the global match metric;

(h) determine 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 the model poses;

(i) compute a deformation transformation that describes the local displacements of the parts;

(j) track 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;

(k) compute at each level the respective deformation transformation and propagating said deformation transformation to the next level; and

(l) provide the model pose and the deformation transformation of the instances of the model object on the finest level of discretization.