Method for scale and rotation invariant pattern recognition

• US 5,063,605 A
• Filed: 06/04/1990
• Issued: 11/05/1991
• Est. Priority Date: 06/04/1990
• Status: Expired due to Term

• Current Assignee: Honeywell Incorporated (Honeywell International Inc.)
• Original Assignee: Honeywell Incorporated (Honeywell International Inc.)
• Inventors: Samad, Tariq
• Primary Examiner(s): Boudreau, Leo H.
• Application Number:
  US07/549,871
• Time in Patent Office: 519 Days
• Field of Search: 382/45, 382/46, 382/68, 382/44, 382/30, 382/28, 250/578, 250/208
• US Class Current: 382/293
• CPC Class Codes: G06V 10/20 Image preprocessing
• CPC Class Codes: G06V 10/7515 Shifting the patterns to accommodate for positional errors

Abstract

A method for scale and rotation invariant pattern recognition. The method involves the recogniziing of patterns, such as visual images of objects, irrespective of scale or two-dimensional orientation. A prior art format for representing data known as a polar exponential grid or PEG format is utilized. For storage, patterns are centered, transformed into a PEG representation, and the centered PEG representation is stored in an associative memory. For recall, patterns are likewise centered and transformed into a PEG representation. They are then first scaled up until the outer layer of the PEG grid is activated, and then incrementally rotated until either a desired level of match is found with some stored pattern, or until a 360 degrees rotation has been completed without a match. Hardware implementation for the PEG transformation and for the incremental rotation and scaling are described.

Claims

1. A method for preparing an image of an object for representation is an associative memory comprising the steps of:

preparing on a rectilinear grid of source cells a digitized image of said object within a background which is centered relative to its "center of mass",

preparing a polar grid format having a circumference fully contained within said background and large enough to fully contain any object to be represented and destination cells formed by a plurality of sectors of equal angles and a plurality of rings spaced at different radii from the center of said circumference,

mapping said image from said rectilinear grid to said polar grid and determining for each of said destination cells the number of said source cells within its bounds occupied by said object, and

designating as active each of said destination cells for which said number exceeds a predetermined criterion.

2. A method pursuant to claim 1 wherein said rings are exponentially spaced relative to said center of said circumference.

3. A method for scale and rotation invariant pattern recognition comprising the steps of:

A. centering an object image, which may be a prototype object image or a test object image, to a canonical position,

B. digitizing said object image to form a digitized object image (DOI) having Cartesian coordinates and storing said DOI,

C. mapping said stored DOI to a polar grid having (1) equal angled sectors and (2) a set of cells formed by said sectors and rings spaced from the origin of said polar grid,

D. forming an ordered representation of said cells in which each cell for which the percentage of overlap relative thereto to said DOI exceeds a predetermined percentage as the status of an active cell,

E. if said DOI is a test DOI (TDOI), go to step H,

F. if said DOI is a prototype DOI (PDOI), storing said ordered representation of said cells in an associative memory with a learning operation,

G. fetching a test object image for centering and returning to said step A,

H. applying said ordered representation of said cells to said associative memory with a recall operation,

I. declaring success if an associative match occurs,

J. if indexing has not been performed, go to step L,

K. determining if said indexing has been performed through 360° and

, if so, declaring failure,

L. indexing said ordered representation of said cells through an angle equal in size to the angle described by the equal angled sectors in step C, and returning to step H.

4. A method according to claim 3 wherein said rings are exponentially spaced relative to said origin of said polar grid.

5. A method for scale and rotation invariant pattern recognition, as set forth in claim 3 and further comprising a modification to step K wherein when said indexing has been performed through 360°

and no match is determined, a scaling of said ordered representation is performed and the method is returned to step H until the object image ordered representation and a predetermined number of scaling operations has been performed.

6. A method as set forth in claim 3 wherein between steps H and I scaling said ordered representation if no associative match occurs and applying said scaled-up ordered representation of said cells to said associative memory with a recall operation, then scaling further until a predetermined number of scaling operations has been performed and reapplying said ordered representation of said cells to said associative memory with a recall operation at each scaling iteration, and declaring success if an associative match occurs at any stage in the scaling and matching operation.

7. Apparatus for scale and rotation invariant pattern recognition, comprising:

a source image plane, having rectangular coordinates formed of rectangular cells, and

a polar destination unit having polar coordinates formed of polar cells, each of said polar cells related by logical correspondents in an overlapping relationship and in communication consistent with and through said relationship with a group of said rectangular cells, and

amplifier means for each of said polar cells having inputs in corresponding ones of said rectangular cells and threshold means for each of said amplifier means effective to turn on said amplifier means when a predetermined number of said rectangular cells to said amplifier means are actuated.

8. Apparatus according to claim 7 including control means for switching the status of each of said polar cells from a source cell to a contiguously located adjacent one of said polar cells which is a destination cell.

9. Apparatus according to claim 8 wherein said contiguously located destination cell is angularly adjacent said source cell.

10. Apparatus according to claim 8 wherein said contiguously located destination cell is radially outward from said source cell.

11. A PEG cell for an array of polar arranged cells each having a state output indicating the state thereof and in which said array said PEG cell would have a radially inward neighbor cell (I) and an angularly adjacent neighbor cell (A), said PEG cell comprising, respective inputs (II) and (IA) connected respectively to said state outputs of said (I) and (A) cells, scale and rotate control inputs, a one bit state register having data and set inputs and an output for indicating the state of said PEG cell, means connecting said scale and rotate inputs to said register and to said (II) and (IA) inputs so that a set signal on one of said control inputs will enable a corresponding one of said state outputs of said (I) and (A) cells to be relayed to and provide a state output for said register.