Similarity determination among patterns using affine-invariant features

• US 5,719,959 A
• Filed: 05/09/1995
• Issued: 02/17/1998
• Est. Priority Date: 07/06/1992
• Status: Expired due to Fees

• Current Assignee: Canon Inc.
• Original Assignee: Canon Inc.
• Inventors: Krtolica, Radovan V.
• Primary Examiner(s): Couso, Jose L.
• Assistant Examiner(s): Bella, Matthew C.
• Application Number:
  US08/437,049
• Time in Patent Office: 1,015 Days
• Field of Search: 382/182, 382/186, 382/187, 382/191, 382/194, 382/197, 382/198, 382/209, 382/218, 382/202
• US Class Current: 382/209
• CPC Class Codes: G06V 30/10 Character recognition
• CPC Class Codes: G06V 30/18181 Graphical representation, e.g. directed attributed graph
• CPC Class Codes: G06V 30/186 by deriving mathematical or geometrical properties from the whole image

Abstract

Pattern recognition, for instance optical character recognition, is achieved by forming a skeletal representation (400) of a pattern (300), processing the skeletal diagram (400) to improve representation of curved lines (308) in the pattern (300), representing the processed skeletal diagram (500) by a connectivity matrix (602), and finding a minimum spectral distance between the connectivity matrix (602) and a set of template matrices corresponding to known patterns.

Claims

1. A computer-implemented process of detecting, analyzing and recognizing a physical pattern, regardless of particular handwriting style or font, among a set of known template patterns, the physical pattern and the template patterns each having a plurality of lines connecting a plurality of line endpoints and line intersections, the process comprising the steps of:

a) detecting and labeling as a plurality of nodes said line endpoints and line intersections of said physical pattern;

b) determining a set of connected node pairs responsive to existence of said lines among said nodes;

c) forming a detected connectivity matrix responsive to the results of step b;

d) determining, by a computer system, a spectrum for said detected connectivity matrix;

e) determining, by said computer system, a spectral distance metric indicating a degree of relative similarity between said detected connectivity matrix and each of a set of template connectivity matrices corresponding to said set of known template patterns; and

f) recognizing said physical pattern as that template pattern whose connectivity matrix has a minimum spectral distance metric indicating a maximum degree of similarity to said detected connectivity matrix.

2. A computer-implemented process as set forth in claim 1, further comprising the steps of:

determining a degree of curvature of one of said lines;

replacing the connected node pair corresponding to said one line with at least two new connected node pairs responsive to said degree of curvature to increase the total number of node pairs in the physical pattern; and

forming said detected connectivity matrix responsive to the results of said replacing step.

4. A computer-implemented process as set forth in claim 1, wherein the physical pattern is an optical character and the set of known template patterns comprises alphanumeric characters.

5. A computer-implemented process as set forth in claim 1, wherein said spectrum comprises a set of eigenvalues for said detected connectivity matrix.

3. A computer-implemented process of detecting, analyzing and recognizing a physical pattern among a set of known template patterns, the physical pattern and the template patterns each having a plurality of lines connecting a plurality of line endpoints and line intersections, the physical pattern having a thickness of stroke, the process comprising the steps of:

a) detecting and labeling as a plurality of nodes said line endpoints and line intersections of said physical pattern;

b) determining a set of connected node pairs responsive to existence of said lines amount said nodes;

c) determining a degree of closeness among a subset of said set of connected node pairs relative to said thickness of stroke;

d) replacing said subset with a single node responsive to said degree of closeness;

e) forming a detected connectivity matrix responsive to the results of steps b and d;

f) determining, by a computer system, a spectrum for said detected connectivity matrix;

g) determining, by said computer system, a spectral distance metric between said detected connectivity matrix and each of a set of template connectivity matrices corresponding to said set of known template patterns; and

f) recognizing said physical pattern as that template pattern whose connectivity matrix has a minimum spectral distance metric to said detected connectivity matrix.

6. Apparatus for detecting, analyzing and recognizing a physical pattern, regardless of particular handwriting style or font, among a set of known template patterns, the physical pattern and the template patterns each having a plurality of lines connecting a plurality of line endpoints and line intersections, the apparatus comprising:

a first processing element for detecting and labeling as a plurality of nodes said line endpoints and line intersections of said physical pattern, determining therefrom a set of connected node pairs responsive to existence of said lines among said nodes, and forming therefrom a detected connectivity matrix;

detected pattern memory for storing a first data set representative of said detected connectivity matrix;

template memory for storing a second data set representative of template connectivity matrices corresponding to said set of known template patterns; and

a second processing element for receiving said first data set and said second data set, for determining therefrom a minimum spectral distance metric indicating a degree of relative similarity between said detected connectivity matrix and said template connectivity matrices, and for recognizing said physical pattern as one of said set of known template patterns responsive to said minimum spectral distance metric indicating a maximum degree of similarity.

7. Apparatus as in claim 6, wherein said first processing element comprises a scanner and a computer controlled by a first stored processing program, and said second processing element comprises said computer controlled by a second stored processing program.

8. Apparatus as in claim 7, wherein said first stored processing program and said second stored processing program form modules of an overall stored processing program.

9. Apparatus as in claim 6, wherein said first data set representative of said detected connectivity matrix comprises spectral data.

10. Apparatus as in claim 6, wherein said second data set representative of template connectivity matrices comprises spectral data.