US4802230A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and apparatus for generating size and orientation invariant shape features
Assignee: GTX Corp
•
Filing: 1987-03-13
•
Granted: 1989-01-31
•
Expires: 2007-03-13
Abstract
Abstract A system extracts a set of size invariant, rotation invariant features from pixel data of a character and sends the set of features to a statistical decision tree to effectuate automatic recognition of a character. The set of extracted features includes a first group obtained by generating arrays representable as dimensions and other geometric qualities of six minimum bounding rectangles rotated about the character, including the distances between the center points of the rotated bounding rectangles. A second group of features is extracted by generating a group of arrays representing the perimeter pixel locations, radii lengths, and direction codes. The arrays of that group are "resampled" to generate corresponding 64 point arrays. The resampled array of direction codes is smoothed and incremental direction codes are computed and compared to preselected thresholds to obtain features that indicate prominent convex and concave portions of the character. A third group of features is extracted by dividing a circle bounding the character into eight rings and 24 slices and counting the number of character pixels contained in each ring and in each slice. Various Fourier transforms, autocorrelations, moment calculations, and sorting operations are performed on many of the aforementioned arrays to yield further size and orientation invariant features. The distance between the centroid of the largest hole of the character and the center of the character is computed. The ratios of the perimeters of first and second holes of the character to the outer perimeter are computed.
Inventors
- 👤 Steven L. Horowitz
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-29 20:16
CPC Classifications
G; G06; G06V; G06V10/00; G06V10/40; G06V10/46; G06V10/478; G06V30/00; G06V30/10; G06V30/18; G06V30/18086; G06V30/182; G06V30/186
Claims Analysis
Total Claims: 23
Claim 1
Independent Claim
112 words
A method of operating a computer to extract size-invariant, orientation-invariant features of an electronically scanned character, the method comprising the steps of: (a) providing a plurality of x and y coordinates of a plurality of perimeter pixels of the scanned character; (b) operating on the x and y coordinates to determine values of a preselected parameter of a plurality of minimum bounding polygons each oriented differently relative to the character, each minimum bounding polygon having a plurality of sides each of which touches at least one respective perimeter point of the character, respectively; and (c) operating on the values of eliminate size and orientation information therefrom, to thereby produce the extracted features.
Claim 2
Independent Claim
112 words
A method of operating a computer to extract size-invariant, orientation-invariant features of an electronically scanned character, the method comprising the steps of: (a) providing a plurality of x and y coordinates of a plurality of perimeter pixels of the scanned character; (b) operating on the x and y coordinates to determine values of a preselected parameter of a plurality of minimum bounding polygons each oriented differently relative to the character, each minimum bounding polygon having a plurality of sides each of which touches at least one respective perimeter point of the character, respectively; and (c) operating on the values of eliminate size and orientation information therefrom, to thereby produce the extracted features.
Claim 3
Dependent Claim
32 words
The method of claim 1 wherein each minimum bounding polygon is a minimum bounding rectangle and step (c) includes determining the dimensions of two mutually perpendicular sides of each minimum bounding rectangle.
Claim 4
Dependent Claim
21 words
The method of claim 2 wherein step (b) includes computing the area and an aspect ratio of each minimum bounding rectangle.
Claim 5
Dependent Claim
30 words
The method of claim 2 wherein step (b) includes determining the coordinates of the center points of each of the minimum bounding rectangles, and computing distances between those center points.
Claim 6
Dependent Claim
20 words
The method of claim 4 wherein step (b) includes determining the sum of the computed distances between adjacent center points.
Claim 7
Dependent Claim
16 words
The method of claim 1 wherein step (c) includes computing a one-dimensional moment of the values.
Claim 8
Dependent Claim
19 words
The method of claim 1 wherein step (c) includes sorting various ones of the values of the preselected parameter.
Claim 9
Dependent Claim
18 words
The method of claim 7 wherein step (c) includes performing a preselected arithmetic combination of preselected sorted values.
Claim 10
Dependent Claim
21 words
The method of claim 1 wherein step (c) includes performing a real Fourier transform on the values of the preselected parameter.
Claim 11
Dependent Claim
18 words
The method of claim 1 wherein step (c) includes performing an autocorrelation on the values of the parameter.
Claim 12
Dependent Claim
37 words
The method of claim 2 including effectively rotating each of the minimum bounding rectangles except a first one through a 15 degree angle relative to a prior one, wherein there are 6 of the minimum bounding rectangles.
Claim 13
Dependent Claim
25 words
The method of claim 1 wherein step (c) includes effectively rotating the character relative to an x,y coordinate system to produce the different relative orientations.
Claim 14
Independent Claim
116 words
A system for extracting size-invariant, orientation-invariant features of a character, the system comprising in combination: (a) means for scanning the character and means responsive to the scanning means for producing a plurality of x and y coordinates of a plurality of perimeter pixels of the scanned character; (b) means for operating on the x and y coordinates to determine values of a preselected parameter of a plurality of minimum bounding polygons each oriented differently relative to the character, each minimum bounding polygon having a plurality of sides each of which touches at least one respective perimeter point of the character, respectively; and (c) means for operating on the values to eliminate size and orientation information therefrom.
Claim 15
Independent Claim
116 words
A system for extracting size-invariant, orientation-invariant features of a character, the system comprising in combination: (a) means for scanning the character and means responsive to the scanning means for producing a plurality of x and y coordinates of a plurality of perimeter pixels of the scanned character; (b) means for operating on the x and y coordinates to determine values of a preselected parameter of a plurality of minimum bounding polygons each oriented differently relative to the character, each minimum bounding polygon having a plurality of sides each of which touches at least one respective perimeter point of the character, respectively; and (c) means for operating on the values to eliminate size and orientation information therefrom.
Claim 16
Dependent Claim
32 words
The system of claim 13 wherein each minimum bounding polygon is a minimum bounding rectangle and including means for determining the dimensions of two mutually perpendicular sides of each minimum bounding rectangle.
Claim 17
Dependent Claim
20 words
The system of claim 14 including means for computing the area and an aspect ratio of each minimum bounding rectangle.
Claim 18
Dependent Claim
29 words
The system of claim 14 including means for determining the coordinates of the center points of each of the minimum bounding rectangles, and computing distances between those center points.
Claim 19
Dependent Claim
19 words
The system of claim 16 including means for determining the sum of the computed distance between adjacent center points.
Claim 20
Dependent Claim
15 words
The system of claim 13 including means for computing a one-dimensional moment of the values.
Claim 21
Dependent Claim
18 words
The system of claim 13 including means for sorting various ones of the values of the preselected parameter.
Claim 22
Dependent Claim
20 words
The system of claim 18 including means for performing a a plurality of preselected arithmetic combination of preselected sorted values.
Claim 23
Dependent Claim
24 words
The system of claim 13 including means for effectively rotating the character relative to an x,y coordinate system to produce the different relative orientations.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1992-01-31 | 1992-08-01 | 1993-01-31 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1996-01-31 | 1996-08-01 | 1997-01-31 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2000-01-31 | 2000-08-01 | 2001-01-31 | $7700.00 | Window Closed / Lapsed |