US4783828A — Two-dimensional object recognition using chain co…

Claim 1

Independent Claim 237 words

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.

Claim 2

Dependent Claim 237 words

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.

Claim 3

Dependent Claim 99 words

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.

Claim 4

Dependent Claim 48 words

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.

Claim 5

Independent Claim 245 words

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.

Claim 6

Independent Claim 245 words

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.

Claim 7

Dependent Claim 103 words

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.

Claim 8

Dependent Claim 48 words

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.

Claim 9

Independent Claim 254 words

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.

Claim 10

Independent Claim 254 words

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.

Claim 11

Dependent Claim 46 words

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.

Claim 12

Independent Claim 205 words

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.

Claim 13

Independent Claim 205 words

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.

Claim 14

Dependent Claim 44 words

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.

Annuity Stage	Window Opens	Payment Deadline	Surcharge Period Until	Estimated Fee	Status
3.5 Years (Year 4)	1991-11-08	1992-05-09	1992-11-08	$2000.00	Window Closed / Lapsed
7.5 Years (Year 8)	1995-11-08	1996-05-09	1996-11-08	$3760.00	Window Closed / Lapsed
11.5 Years (Year 12)	1999-11-08	2000-05-09	2000-11-08	$7700.00	Window Closed / Lapsed

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

Abstract

Inventors

Bibliographic Details

Claims Analysis

References Cited (Backward Citations)

USPTO Annuity & Maintenance Windows

Assigned Categories & Tags

Assign Category Tag