Generalized shape autocorrelation for shape acquistion and recognition

Abstract

The invention provides automatic acquisition and recognition of complex visual shapes within images. During an acquisition phase, models are derived from interest points acquired from a target shape. The models are stored in and can be retrieved from a lookup table via high dimension indices. When an image is inputted, triplets of interest points in the image are used to compute local shape descriptors, which descrb the geometry of local shapes in the image. In turn, triplets of local shape descriptors are used to compute high dimension indices. These indices arm used for accessing the lookup table having the models The models are used for the automatic recognition of target shapes.

The following is claimed: 
     
       1. A computer-implemented method for recognizing objects and for automatic acquisition of models of objects, comprising the steps of: (1) acquiring a model of an object, comprising, (a) digitizing said object to generate a digitized image;   (b) detecting local shapes in said digitized image;   (c) grouping three or more .[.noncontinuous.]. .Iadd.noncontiguous .Iaddend.combinations of said local shapes to generate a first index;   (d) generating an entry for each group of local shapes consisting of a name of said digitized image, and information about the translation, rotation, and scale of said digitized image; and   (e) storing said entry in a shape table at said first index; and     (2) recognizing a target object that appears in a physical scene, comprising, (a) digitizing said target object to generate a digitized target image;   (b) detecting .[.global.]. .Iadd.local .Iaddend.shapes in said digitized target image;   (c) grouping three or more .[.noncontinuous.]. .Iadd.noncontiguous .Iaddend.combinations of said .[.global.]. .Iadd.local .Iaddend.shapes to generate a second index;   (d) accessing said shape table and retrieving entries from said shape table that correspond to said second index;   (e) collecting said retrieved entries from said shape table into a vote table; and   (f) selecting said retrieved entry with a highest vote in order to recognize said target image.     
     
     
       2. The method of claim 1, further comprising the steps of: creating a local lookup table;   entering local shapes to be recognized by the system into said local lookup table by synthetic generation; and   using said local lookup table to detect local shapes in said digitized image.   
     
     
       3. The method of claim 1, further comprising the steps of: transforming three or more edge points of said digitized image into local groupings;   analyzing said local groupings in a parameter space;   comparing the geometric characteristics of said local groupings with local shape entries in a local lookup table;   according votes to said local shape entries which correspond with said geometric characteristics; and   adopting local shape descriptors corresponding to local shape entries which have a high number of votes.   
     
     
       4. The method of claim 1, further comprising the steps of: converting three or more local shapes of said digitized target image into global groupings;   analyzing said global groupings in a parameter space;   comparing the geometric characteristics of said global groupings with global shape entries in said shape table;   according votes to said global shape entries which correspond with said geometric characteristics; and   adopting global shape descriptors corresponding to global shape entries which have a high number of votes.   
     
     
       5. A computer-based system for recognizing objects and for automatic acquisition of models of objects, comprising: (a) means for acquiring a model of an object, comprising, (1) means for digitizing said object to generate a digitized image;   (2) means for detecting local shapes in said digitized image;   (3) means for grouping three or more .[.noncontinuous.]. .Iadd.noncontiguous .Iaddend.combinations of said local shapes to generate a first index;   (4) means for generating an entry for each group of local shapes consisting of a name of said digitized image, and information about the translation, rotation, and scale of said digitized image; and   (5) means for storing said entry in said shape table at said first index; and     (b) means for recognizing a target object that appears in a physical scene, comprising, (1) means for digitizing said target object to generate a digitized target image;   (2) means for detecting local shapes in said digitized target image;   (3) means for grouping three or more .[.noncontinuous.]. .Iadd.noncontiguous .Iaddend.combinations of said .[.local.]. shapes to generate a second index;   (4) means for accessing said shape table and for retrieving entries from said shape table that correspond to said second index;   (5) means for collecting said retrieved entries from said shape table into a vote table and for selecting said retrieved entry with a highest vote in order to recognize said target image.     
     
     
       6. The computer-based system of claim 5, further comprising: (a) a camera adapted for viewing said target object and producing a signal indicative of said target object; and   (b) a digitizer, connected to said camera, for digitizing said target object represented by said signal and storing said digitized target image in a storage medium.   
     
     
       7. The computer-based system of claim 5, further comprising: a local shape table;   means for entering local shapes to be recognized into said local shape table by synthetic generation; and   means for using said local shape table to detect local shapes in said digitized image.   
     
     
       8. The computer-based system of claim 5, further comprising: means for transforming three or more edge points of said digitized image into local groupings;   means for analyzing said local groupings in a parameter space;   means for comparing the geometric characteristics of said local groupings with local shape entries in a local lookup table;   means for according votes to said local shape entries which correspond with said geometric characteristics; and   means for adopting local shape descriptors corresponding to local shape entries which have a high number of votes.   
     
     
       9. The computer-based system of claim 5, further comprising: means for converting three or more local shapes of said digitized target image into global groupings;   means for analyzing said global groupings in a parameter space;   means for comparing the geometric characteristics of said global groupings with global shape entries in said global shape table;   means for according votes to said global shape entries which correspond with said geometric characteristics; and   means for adopting global shape descriptors corresponding to global shape entries which have a high number of votes.   
     
     
       10. The computer-based system of claim 5, further comprising: means for generating a recognition signal from said selected retrieved entry, wherein said recognition signal is indicative of a recognized target object.