Image analysis – Pattern recognition – Feature extraction
Reexamination Certificate
1999-06-03
2001-08-14
Au, Amelia M. (Department: 2623)
Image analysis
Pattern recognition
Feature extraction
C382S205000, C382S277000
Reexamination Certificate
active
06275613
ABSTRACT:
FIELD AND BACKGROUND OF THE INVENTION
The present invention relates to model-based object recognition and, more particularly, to a method for object recognition based on transformation hashing and chamfer matching.
In applications such as automatic vision, it often is necessary to identify an object in a digital image of a scene. For example, a robot on an assembly line may need to identify a portion of a workpiece that the robot needs to work on. Typically, the image consists of a rectangular array of image pixels, each pixel having a certain gray level. In model-based object recognition, instead of working with the gray levels, feature pixels that correspond to corners and edges of objects in the scene are identified in the image, using conventional edge detection and corner detection algorithms. See, for example, J. Canny, “A computational approach to edge detection”,
IEEE Transactions on Pattern Analysis and Machine Intelligence
, vol. PAMI-8 no. 6 pp. 679-698 (November 1986); H. Moravec, “Towards automatic visual obstacle avoidance”, 5
th International Joint Conference on Artificial Intelligence
p. 584 (1977); and R. M. Harelick and L. G. Shapiro,
Computer and Robot Vision
(Addison-Wesley, 1992), vol. 1 sec. 8.10 pp. 410-419, “Corner detection” and vol. 2 sec. 16.4 pp. 332-348, “An interest operator”. The object whose presence is suspected in the image, or whose location in the image is sought, is represented as a model that includes several model points, called “feature points”, that correspond to corners or edges of the sought object. A subset of the image feature pixels is sought that corresponds in some sense to the model feature points. If such a subset is found, that subset is presumed to be part of an outline of the sought object.
The prior art method of model-based object recognition that is closest to the present invention is that described in Yehezkel Lamdan and Haim J. Wolfson, “Geometric hashing: a general and efficient model-based recognition scheme”, Second International Conference on Computer Vision, IEEE Computer Society, 1988, pp. 238-249. A better, more specific name for this prior art method is “basis set hashing”. According to this method, the sought object is represented as a two-dimensional model consisting of a set of feature points. The method is most simply explained with reference to two-dimensional similarity transformations (rotations, translations and scaling). Pairs of feature points are considered in turn. For each pair of feature points, a coordinate system is formed in which one of the feature points of the pair has coordinates (0,0), and the other feature point of the pair has coordinates (1,0), so that the two points of the pair define one unit vector of a basis set of the coordinate system. The coordinates of the feature points collectively in this coordinate system constitute a representation of the model, specifically, the result of the similarity transformation of the feature point coordinates that transforms the first point of the pair to (0,0) and the second point of the pair to (1,0). Similar representations of the image are formed, using pairs of feature pixels.
The remainder of the method of Lamdan and Wolfson consists of looking for one or more image representations that include one of the model representations, to within the level of discretization represented by the pixels of the image. With m points in the model and n pixels in the set of feature pixels, if matching a model representation to an image representation has complexity t, then the complexity of brute force matching is m
2
n
2
t, which is of the order n
5
in the worst case. Therefore, Lamdan and Wolfson construct a hash table. Each entry of the hash table corresponds to an image pixel that includes one or more of the points of the model representations, and is a list of all the model representations having points that fall within that image pixel. Matching is done by assigning tallies to the model representations. All the tallies initially are 0. Pairs of feature points are selected as a potential base pair and all other feature points are transformed using this base. For each feature pixel with an entry in the hash table, 1 is added to the tally of each model representation listed in that entry. The model representation with the highest tally identifies the location of the object in the image. If no tallies exceed a predetermined threshold, then it is concluded that the object does not appear in the image. The fact that the hash table can be constructed in advance makes this method suitable, in principle, to real-time object recognition.
The above description of the prior art method of Lamdan and Wolfson is based on two-dimensional similarity transformations. The method also could be based on more complicated transformations, for example, on three-dimensional similarity transformations of three-dimensional models, or on affine transformations. The coordinate systems of the representations then are of higher dimensionality, for example, dimension
3
for three-dimensional similarity transformations and two-dimensional affine transformations. The run-time complexity for object recognition is m
k
+1
for k-dimensional representation coordinate systems.
SUMMARY OF THE INVENTION
According to the present invention there is provided a method for locating a base model in an image including a plurality of image pixels, including the steps of: (a) transforming the base model to obtain a plurality of transformed models, each transformed model including a plurality of transformed model pixels; (b) tabulating, for each image pixel corresponding to one of the transformed model pixels, all the transformed models that include the one transformed model pixel; (c) identifying, from among the image pixels, a plurality of relevant pixels; (d) for each relevant pixel, assigning a score to each transformed model that is tabulated for the each relevant pixel; and (e) for each transformed model, summing the scores to obtain a tally.
According to the present invention there is provided a system for locating a base model in an image including a plurality of image pixels, including: (a) a software module including a plurality of instructions for: (i) transforming the base model to obtain a plurality of transformed models, each transformed model including a plurality of transformed model pixels, (ii) tabulating, for each image pixel corresponding to one of the transformed model pixels, all the transformed models that include the one transformed model pixel, (iii) identifying, from among the image pixels, a plurality of relevant pixels, (iv) for each relevant pixel, assigning a score to each transformed model that is tabulated for each relevant pixel, and (v) for each transformed model, summing the scores to obtain a tally; (b) a processor for executing the instructions; and (c) a memory for storing the base model, the image and the transformed models.
The method of the present invention is similar to the method of Lamdan and Wolfson, with two important differences.
The first difference is that instead of making a hash table of model representations, the method of the present invention makes a hash table of transformed models. A set of transformed models is constructed, and discretized, in accordance with the image discretization, to provide, for each transformed model, a set of transformed model pixels. Each entry of the hash table corresponds to an image pixel that coincides with a transformed model pixel of at least one transformed model, along with a list of all the transformed models in which that pixel appears as a transformed model pixel. Because of this difference, object recognition is effected without transforming the image pixels at run time. The complexity of run-time object recognition, according to the present invention, is of order m, rather than the order m
k
+1
complexity of the prior art method. To distinguish the original model from the transformed models, the original model is referred to herein as the “base model”.
The second difference is that chamfer ma
Au Amelia M.
Dastouri Mehrdad
Friedman Mark M.
Medsim Ltd.
LandOfFree
Method for locating a model in an image does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method for locating a model in an image, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for locating a model in an image will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2544180