Two-dimensional object recognition using chain codes, histogram normalization and trellis algorithm

• US 4,783,828 A
• Filed: 06/02/1986
• Issued: 11/08/1988
• Est. Priority Date: 06/02/1986
• Status: Expired due to Term

• Current Assignee: Honeywell Incorporated (Honeywell International Inc.)
• Original Assignee: Honeywell Incorporated (Honeywell International Inc.)
• Inventors: Sadjadi, Firooz A.
• Primary Examiner(s): Boudreau, Leo H.
• Assistant Examiner(s): Couso, Jose L.
• Application Number:
  US06/870,603
• Time in Patent Office: 890 Days
• Field of Search: 350/13, 350/136, 350/166, 382/13, 382/18, 382/20-22, 382/25, 382/28, 382/34, 382/42, 382/51, 382/56
• US Class Current: 382/170
• CPC Class Codes: G06V 10/469 Contour-based spatial representations, e.g. vector-coding
• CPC Class Codes: G06V 30/248 involving plural approaches, e.g. verification by template match; Resolving confusion among similar patterns, e.g. "O" versus "Q" G06V30/242 takes precedence

Abstract

A system for classifying a two-dimensional object, the object having a boundary. The system includes a sensor for sensing the boundary of the object, a processor which assigns a chain code to the boundary of the object and memory for storing a plurality of chain code histograms corresponding to known two-dimensional objects. A histogram is generated from the object'"'"'s assigned chain code and correlated in the processor with a chain code histogram from memory. A final ambiguity between the normalized chain code of the object and the chain code of the correlating known object is resolved through application of a Viterbi algorithm.

Claims

1. A classification processor for classifying an unknown two-dimensional object having a chain code by correlating an unknown object'"'"'s chain code histogram with stored chain code histograms of known two-dimensional objects comprising:

means for generating a histogram from the unknown object'"'"'s chain code reflecting size and orientation of the unknown object;

means for correlating the generated histogram with a stored chain code histogram of a known object, comprising;

means for selecting a stored chain code histogram of a known object;

means for comparing the unkown object'"'"'s chain code histogram with the selected known object'"'"'s histogram in a vertical chain code histogram domain;

first means for generating a first correlation factor in the vertical domain to determine scaled size of the unknown object;

means for comparing the unknown object'"'"'s chain code histogram with the selected known object'"'"'s histogram in a horizontal chain code histogram domain;

second means for generating a second correlation factor in the horizontal domain to determine rotational orientation of the unknown object;

means for normalizing the known object'"'"'s chain code hostogram by shifting the known object'"'"'s chain code histogram horizontally and vertically as required to match a scaled size and a rotational orientation of the chain code histogram of a known object; and

means for applying a Viterbi algorithm for resolving a final ambiguity in deciding whether or not the generated histogram and the stored histogram are similar by processing the histograms with a distance function.

2. The device of claim 1 wherein the means for applying the Viterbi algorithm further comprises means for generating a distance function equal to differences in each chain code state between the unknown object'"'"'s normalized chain code and the chain code of the known two-dimenisonal object wherein the algorithm is stopped before processing of the chain code histograms is completed when a set threshold of the distance function is exceeded thus deeming no match between the unkown object and the known object, or the algorithm continues to completion thereby deeming a match between the unknown object and the known object.

3. The device of claim 2 further comprising means for selecting another stored histogram of another known object upon the deeming no match between the known object and the unknown object, for correlating the unknown object'"'"'s chain code histogram with another stored chain code histogram of another known object.

4. A method for classifying a two-dimensional object having a chain code by correlating the object'"'"'s chain code histogram with stored chain code histograms of known two-dimensional objects, with steps comprising:

generating a chain code histogram from the unknown object'"'"'s chain code reflecting size and orientation of the unknown object, wherein the chain code assigned to a boundary of the object is assigned according to a chain code rule containing at least eight directional elements;

correlating the generated chain code histogram with a stored chain code histogram of a known object, comprising;

comparing the unknown object'"'"'s chain code histogram with a stored histogram of the known object in a vertical chain code histogram domain;

generating a first correlation factor in the vertical domain to determine scaled size of the unknown object;

comparing the unkown object'"'"'s cahin code histogram with a stored histogram of the known object in a horizontal chain code histogram domain;

generating a second correlation factor in the horizontal domain to determine rotational orientation of the unkown object;

comparing horizontal and vertical correlation factors with predetermined thresholds;

providing results of comparisons of correlation factors, which indicate whether correlating of the unknown object'"'"'s chain code histogram of the known object should continue; and

normalizing the unknown object'"'"'s chain code histogram and chain code; and

applying a Viterbi algorithm for resolving a final ambiguity in deciding whether or not the generated histogram and the stored histogram are similar by processing the histograms with a distance function.

5. The method of claim 4 wherein the step for applying the Viterbi algorithm further comprises generating a distance function equal to a difference between the unknown object'"'"'s normalized chain code and the chain code of the correlating known two-dimensional object for each chain code state wherein the algorithm is stopped before processing of the chain code histograms is completed when a set threshold of the distance function is exceeded thus deeming no match between the unknown object and the known object and the known object, or the algorithm continues to completion thereby deeming a match between the unknown object and the known object.

6. The method of claim 5 further comprising means for selecting another stored histogram of another known object upon the deeming no match between the known object and the unknown object, for correlating the unknown object'"'"'s chain code histogram with another stored chain code histogram of another known object.

7. A system for classifying an unknown two-dimensional object, the object having a boundary, comprising:

a sensor for sensing the boundary of the object;

means for assigning a chain code to the boundary of the object according to a chain code rule containing at least eight directional elements;

memory for storing a plurality of chain code histograms of known two-dimensional objects;

means for generating a histogram from the assigned chain code reflecting size and orientation of the unknown object;

means for correlating the generated histogram with a chain code histogram of a known object, comprising;

means for selecting a stored chain code histogram of a known two-dimensional object from the memory;

means for comparing the object'"'"'s chain code histogram with the selected histogram in a vertical chain code histogram domain;

means for generating a first correlation factor in the vertical domain to determine scaled size of the unknown object;

means for comparing the object'"'"'s chain code histogram with the selected histogram in a horizontal chain code histogram domain;

a second means for generating a second correlation factor in the horizontal chain code histogram domain to determine rotational orientation of the unknown object;

means for comparing first and second correlation factors with predetermined theresholds; and

means for normalizing the object'"'"'s chain code histogram and chain code; and

means for applying a Viterbi algorithm for resolving a final ambiguity in deciding whether or not the generated histogram and the stored histogram are similar in that the unknown object matches a known object represented by the stored histogram.

8. The system of claim 7 wherein the means for applying the Viterbi algorithm further includes a means for generating a distance function equal to differences in each chain code state between the object'"'"'s normalized chain code and the chain code of the correlating known two-dimensional object.

9. A method for classifying an unknown two-dimensional object, the object having a boundary, with steps comprising:

sensing the boundary of the object;

assigning a chain code to the boundary of the object, according to a chain code rule containing at least eight directional elements;

storing a plurality of chain code histograms of known two-dimensional objects;

generating a chain code histogram from the assigned chain code reflecting size and orientation of the unknown object;

correlating the generated histogram with a stored chain code histogram of a known object, comprising;

selecting a histogram from the plurality of chain code histograms of known two-dimensional objects;

comparing the object'"'"'s chain code histogram with the selected histogram in a vertical chain code histogram domain;

generating a correlation factor in the vertical domain;

comparing the object'"'"'s chain code histogram with the selected histogram in a horizontal histogram domain;

generating a second correlation factor in the horizontal domain;

comparing correlation factors with predetermined theresholds; and

normalizing the object'"'"'s chain code histogram and chain code; and

applying a Viterbi algorithm for resolving a final ambiguity in deciding whether or not the generated histogram and the stored histogram are similar in that the unknown object matches a known object represented by the stored histogram.

10. The method of claim 9 wherein the step for applying the Viterbi algorithm further includes generating a distance function equal to the difference between the object'"'"'s normalized chain code and the chain code of the correlating known two-dimensional object for each chain code state.