System and method for deformable object recognition

• US 8,260,059 B2
• Filed: 05/05/2008
• Issued: 09/04/2012
• 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
• Primary Examiner(s): Carter, Aaron W
• Application Number:
  US12/115,059
• Publication Number:
  US 20090185715A1
• Time in Patent Office: 1,583 Days
• Field of Search: 382/154, 382215-218, 382/240, 382/285, 345419-427, 356 12- 14, 348 42- 60, 359462-477
• US Class Current: 382/215
• 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 image points within said search image that corresponds to the range of nonlinear transformations for which the at least one precomputed model should be searched;

(h) computing a global match metric for each affine model pose at the coarsest discretization level of the search space, said global match metric combining the results of a local metric, where for the local metric the parts of the model are searched in a restricted range of local affine 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 nonlinear 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 nonlinear deformation transformation and propagating said deformation transformation to the next level; and

(m) providing the nonlinear 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 point sets.

6. The method of claim 4, wherein each part is composed of a number of points where the point sets 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 nonlinear deformation 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 nonlinear deformation transformation is a 3D pose.

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

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

13. The method of claim 4, wherein the computed nonlinear deformation 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 non-transitory 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, consisting of:

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

(h) means for computing a global match metric for each affine model pose at the coarsest discretization level of the search space, said global match metric combining the results of a local metric, where for the local metric the parts of the model are searched in a restricted range of local affine 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 nonlinear 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 nonlinear deformation transformation and propagating said deformation transformation to the next level; and

(m) means for providing the nonlinear 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 image points within said search image that corresponds to the range of nonlinear transformations for which the at least one precomputed model should be searched;

(g) compute a global match metric for each affine model pose at the coarsest discretization level of the search space, said global match metric combining the results of a local metric, where for the local metric the parts of the model are searched in a restricted range of local affine 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 nonlinear 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 nonlinear deformation transformation and propagating said deformation transformation to the next level; and

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