Generalized shape autocorrelation for shape acquisition and recognition

• US 5,351,310 A
• Filed: 12/08/1993
• Issued: 09/27/1994
• Est. Priority Date: 05/21/1991
• Status: Expired

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Mohan, Rakesh, Califano, Andrea
• Primary Examiner(s): Boudreau, Leo H.
• Application Number:
  US08/162,966
• Time in Patent Office: 293 Days
• Field of Search: 382/22, 382/25, 382/8, 382/41, 382/21, 348/125, 348/134, 348/135, 348/141
• US Class Current: 382/199
• CPC Class Codes: G06V 10/42 Global feature extraction by analysis of the whole pattern, e.g. using frequency domain transformations or autocorrelation
• CPC Class Codes: G06V 10/46 Descriptors for shape, contour or point-related descriptors, e.g. scale invariant feature transform [SIFT] or bags of words [BoW]; Salient regional features colour feature extraction G06V10/56
• CPC Class Codes: H01B 1/121 Charge-transfer complexes

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 describe the geometry of local shapes in the image. In turn, triplets of local shape descriptors are used to compute high dimension indices. These indices are used for accessing the lookup table having the models. The models are used for the automatic recognition of target shapes.

Claims

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 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

(c) 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 shapes in said digitized target image;

(c) grouping three or more noncontinuous combinations of said global 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 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) a shape table;

(6) 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 global shapes in said digitized target image;

(3) means for grouping three or more noncontinuous combinations of said global 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.

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.