Hierarchical component based object recognition

• US 7,239,929 B2
• Filed: 08/29/2003
• Issued: 07/03/2007
• Est. Priority Date: 08/30/2002
• Status: Active Grant

• Current Assignee: MvTec Software GmbH (MvTec LLC)
• Original Assignee: MvTec Software GmbH (MvTec LLC)
• Inventors: Ulrich, Markus, Steger, Carsten
• Primary Examiner(s): Paladini; Albert W.
• Application Number:
  US10/652,360
• Publication Number:
  US 20040042661A1
• Time in Patent Office: 1,404 Days
• Field of Search: 703/2, 703/22, 345/420, 382/154, 382/236, 382/294, 700/182, 700/98
• US Class Current: 700/98
• CPC Class Codes: G06F 18/28 Determining representative reference patterns, e.g. by averaging or distorting; Generating dictionaries
• CPC Class Codes: G06V 10/422 for representing the structure of the pattern or shape of an object therefor
• CPC Class Codes: G06V 10/754 involving a deformation of the sample pattern or of the reference pattern; Elastic matching
• CPC Class Codes: G06V 10/772 Determining representative reference patterns, e.g. averaging or distorting patterns; Generating dictionaries

Abstract

The present invention provides a method for the recognition of objects in an image, where the objects may consist of an arbitrary number of parts that are allowed to move with respect to each other. In the offline phase the invention automatically learns the relative movements of the single object parts from a sequence of example images and builds a hierarchical model that incorporates a description of the single object parts, the relations between the parts, and an efficient search strategy. This is done by analyzing the pose variations (e.g., variations in position, orientation, and scale) of the single object parts in the example images. The poses can be obtained by an arbitrary similarity measure for object recognition, e.g., normalized cross correlation, Hausdorff distance, generalized Hough transform, the modification of the generalized Hough transform, or the similarity measure. In the online phase the invention uses the hierarchical model to efficiently find the entire object in the search image. During the online phase only valid instances of the object are found, i.e., the object parts are not searched for in the entire image but only in a restricted portion of parameter space that is defined by the relations between the object parts within the hierarchical model, what facilitates an efficient search and makes a subsequent validation step unnecessary.

Claims

1. A method for constructing a hierarchical model consisting of the following steps:

a) constructing an initial object decomposition into components based on a model image;

b) determining the relative poses of the components in a plurality of example images with respect to the model image;

c) determining whether a plurality of components moves in an identical or similar manner over the sequence of example images and, if so, grouping such components, resulting together with the ungrouped components in the object parts;

d) determining the relative poses of said grouped components in each example image;

e) forming a hierarchical model, consisting of a root object part at the top of the hierarchy and a plurality of object parts at lower levels of the hierarchy, from the object parts using an optimization criterion that takes into account the relative poses of the object parts; and

f) determining relative search spaces of the object parts to be used in the object recognition phase.

2. The method of claim 1, wherein the initial object decomposition is done by the user.

3. The method of claim 1, wherein the initial object decomposition is done automatically using a grouping method.

4. The method of claim 1, wherein the connected components of the image edges are used as initial components.

5. The method of claim 1, wherein the image edges are computed by an edge operator that at least provides the edge magnitude.

6. The method of claim 5, wherein said edge operator is a Sobel operator.

7. The method of claim 1 where the step of determining the relative poses of the components includes a further step of:

Eliminating the influence of neighboring components during pose determination.

8. The method of claim 1 wherein determining the relative poses includes:

Using an object recognition method that is based on gray value correlation as similarity measure.

9. The method of claim 1 wherein determining the relative poses includes:

using an object recognition method that is based on geometric features as similarity measure.

10. The method of claim 9, wherein said object recognition method is based on the generalized Hough transform.

11. The method of claim 9, wherein said object recognition method is based on the dot product of the edge gradient directions.

12. The method of claim 9, wherein said object recognition method is based on the Hausdorff distance.

13. The method of claim 1 further including the step of:

Eliminating ambiguous matches by selecting the match with highest probability.

14. The method of claim 13, wherein the match with the highest probability is selected to be the match that causes the smallest variation of relative poses in the example image with respect to the model image.

15. The method of claim 1 wherein determining whether a plurality of components moves in an identical or similar manner over the sequence of example images includes the steps of:

Computing the relative movement for each pair of components in each example image;

Computing a statistically value (mean, median, or maximum) of the relative movements over the example images;

Computing a dissimilarity matrix containing the statistical values; and

Clustering the dissimilarity matrix successively until the remaining statistical values exceed a user-defined threshold.

16. The method of claim 1 wherein determining whether a plurality of components moves in an identical or similar manner over the sequence of example images includes the steps of:

Computing the relative movement for each pair of components in each example image;

Calculating the probabilities that two components belong to the same object part using statistical methods;

Computing a similarity matrix containing the probabilities; and

Clustering the similarity matrix successively until the remaining probabilities are below a user-defined threshold.

17. The method of claim 15 wherein the grouping of the components includes:

Merging all components that are contained in the same cluster, calculated in claim 15.

18. The method of claim 16 wherein the grouping of the components includes:

Merging all components that are contained in the same cluster, calculated in claim 16.

19. The method of claim 1 wherein forming a hierarchical model from the object parts using an optimization criterion that takes into account the relative poses of the object parts includes the following steps:

Computing a variation measure for each directed pair of object parts;

Computing an optimization criterion based on the variation measure;

Computing an optimum hierarchical search tree based on the optimization criterion.

20. The method of claim 19, wherein the variation measure of one pair of object parts is a strictly monotonic increasing function of the search effort that must be expended by the object recognition method to search the second object part with respect to the first object part.

21. The method of claim 19 wherein the optimization criterion minimizes the overall sum of all variation measures, which are included in the hierarchical search.

22. The method of claim 19 wherein the optimum hierarchical search tree is calculated based on the optimization criterion by calculating the minimum spanning arborescence of the graph that describes the mutual variation measures.

23. The method of claim 1 wherein determining relative search spaces of the object parts to be used in the object recognition phase includes:

Computing for each directed pair of object parts the search space of the second object part with respect to the pose of the first object part.

24. The method of claim 23, wherein the search space is the convex hull of the poses over all example images in the n-dimensional pose space, where n describes the number of pose parameters.

25. The method of claim 24, further including:

Enlarging the search space by computing enclosing geometric shapes of the convex hull.

26. The method of claim 24 further including:

Enlarging the search space by a user-given tolerance.

27. A method for object recognition using a hierarchical model consisting of the following steps:

a) finding the root object part of the hierarchical model in the search image;

b) using the found pose of the previous object parts to construct search spaces for the object parts in the next lower level of the object hierarchy;

c) searching the object parts in said search spaces;

d) iterating steps b) and c) until all object parts of the model hierarchy have been searched; and

e) providing the poses of all object parts.

28. The method of claim 27, wherein finding the root object part of the hierarchical model includes:

Using an object recognition method that is based on gray value correlation as similarity measure.

29. The method of claim 27, wherein finding the root object part of the hierarchical model includes:

Using an object recognition method that is based on geometric features as similarity measure.

30. The method of claim 29, wherein said object recognition method is based on the generalized Hough transform.

31. The method of claim 29, wherein said object recognition method is based on the dot product of the edge gradient directions.

32. The method of claim 29, wherein said object recognition method is based on the Hausdorff distance.

33. The method of claim 27 wherein using the found pose of the previous object parts to construct search spaces for the object parts in the next lower level of the object hierarchy includes:

Transforming the search spaces of the object parts in the next lower level that are stored in the hierarchical model according to the pose parameters of the found pose of the previous object parts.

34. The method of claim 27 wherein searching the object parts in said search spaces includes:

using an object recognition method that is based on gray value correlation as similarity measure.

35. The method of claim 27 wherein searching the object parts in said search spaces includes:

using an object recognition method that is based geometric features as similarity measure.

36. The method of claim 27 wherein the step of iterating steps b) and c) until all object parts of the model hierarchy have been searched includes the following steps:

Checking whether the object part was not found;

Checking whether the object part was found more than once;

Computing a score value of the hierarchical match;

Checking whether a user-defined minimum score value can still be reached for the hierarchical match candidate; and

Checking whether all object parts of the model hierarchy have been searched.

37. The method of claim 36, wherein the step of checking whether the object part was not found includes:

Checking whether no valid match was returned by the object recognition method; and

If so, applying a special treatment for the object parts that in the search hierarchy reside directly below the missing object part.

38. The method of claim 37, wherein the step of applying a special treatment for the object parts that in the search hierarchy reside directly below the missing object part includes:

Treating the object parts also as missing.

39. The method of claim 37 wherein the step of applying a special treatment for the object parts that in the search hierarchy reside directly below the missing object part includes:

Searching the object parts relative to the already found object part that in the search hierarchy resides closest above the missing object part.

40. The method of claim 37, wherein the step of applying a special treatment for the object parts that in the search hierarchy reside directly below the missing object part includes:

Searching the object parts relative to the already found object part from which the search effort is minimal.

41. The method of claim 36 wherein the step checking whether the object part was found more than once includes the steps:

Checking whether more than one valid match was returned by the object recognition method;

If so, cloning the hierarchical match candidate according to the number of found object part instances;

Assigning each match of the object part to one hierarchical match candidate; and

Continuing the search for each hierarchical match candidate.

42. The method of claim 36 wherein computing a score value of the hierarchical match candidate includes:

Computing the score value of the hierarchical match candidate as a weighted sum of the score values of the individual object part matches.

43. The method of claim 42, wherein the weights are chosen according to the size of the object parts.

44. The method of claim 42 wherein the weights are chosen by the user.

45. The method of claim 36 wherein checking whether a user-defined minimum score value can still be reached for the hierarchical match includes:

Computing the sum of the current hierarchical match score and the score that can be achieved by the remaining object parts at most;

Checking the sum of being below the user-defined minimum score value; and

If so deleting the hierarchical match candidate.

46. The method of claim 27 further including the steps of:

Computing the overlap between the hierarchical match candidates;

Checking whether the overlap of two hierarchical match candidates exceeds a user-defined maximum value; and

If so, deleting the hierarchical match candidate with lower score.