EP0281725A2
Expired / Lapsed
EP
⏱️ 0.0 years remaining
Method and apparatus for generating size and orientation invariant shape features
Assignee: GTX Corp
•
Filing: 1988-01-08
•
Granted: —
•
Expires: 2008-01-08
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 arrays 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
EP
Data Source
google_patents
Last Synchronized
2026-11-09 10:35
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: 21
Claim 1
Independent Claim
114 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 the perimeter pixels of the scanned character; (b) means for operating on the x and y coordinates to determinate 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 ininformation therefrom.
Claim 2
Independent Claim
114 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 the perimeter pixels of the scanned character; (b) means for operating on the x and y coordinates to determinate 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 ininformation therefrom.
Claim 3
Dependent Claim
32 words
The system of Claim 1 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 4
Dependent Claim
20 words
The system of Claim 2 including means for computing the area and an aspect ratio of each minimum bounding rectangle.
Claim 5
Dependent Claim
29 words
The system of Claim 2 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 6
Dependent Claim
19 words
The system of Claim 4 including means for determining the sum of the computed distances between adjacent center points.
Claim 7
Dependent Claim
24 words
The system of Claim 1 including means for effectively rotating the character relative to an x,y coordinate system to produce the different relative orientations.
Claim 8
Independent Claim
130 words
A system for extracting features of a character, the system comprising in combination: (a) means for generating x and y coordinates of each respective perimeter pixel; (b) means for operating on the x and y coordinates to generate perimeter distances between each pair of perimeter pixels; (c) means for operating on the x and y coordinates and the center of the character to produce the radial distances between the center and the respective perimeter pixels; (d) means for resampling the radial distances by using the perimeter distances to produce a fixed number of resampled radial distances each corresponding to an equal proportion of the total perimeter length; and (e) means for operating on the resampled radial distances to eliminate size and orientation information therefrom, to thereby produce the extracted features.
Claim 9
Independent Claim
130 words
A system for extracting features of a character, the system comprising in combination: (a) means for generating x and y coordinates of each respective perimeter pixel; (b) means for operating on the x and y coordinates to generate perimeter distances between each pair of perimeter pixels; (c) means for operating on the x and y coordinates and the center of the character to produce the radial distances between the center and the respective perimeter pixels; (d) means for resampling the radial distances by using the perimeter distances to produce a fixed number of resampled radial distances each corresponding to an equal proportion of the total perimeter length; and (e) means for operating on the resampled radial distances to eliminate size and orientation information therefrom, to thereby produce the extracted features.
Claim 10
Dependent Claim
18 words
The system of Claim 7 including means for performing a real Fourier transform on the resampled radial distances.
Claim 11
Independent Claim
121 words
A system for extracting features of a character, the system comprising in combination: (a) means for electronically scanning the character to produce perimeter pixel data and means responsive to the perimeter pixel data for generating x and y coordinates of each perimeter pixel; (b) means for operating on the x and y coordinates to generate perimeter distances between each pair of perimeter pixels; (c) means for operating on the x and y coordinates to produce a measurement of an angle tangent to the perimeter at every perimeter pixel; and (d) means for resampling the tangent angles by using the perimeter distances to produce a fixed number of resampled tangent angles each corresponding to an equal proportion of the total perimeter length.
Claim 12
Independent Claim
121 words
A system for extracting features of a character, the system comprising in combination: (a) means for electronically scanning the character to produce perimeter pixel data and means responsive to the perimeter pixel data for generating x and y coordinates of each perimeter pixel; (b) means for operating on the x and y coordinates to generate perimeter distances between each pair of perimeter pixels; (c) means for operating on the x and y coordinates to produce a measurement of an angle tangent to the perimeter at every perimeter pixel; and (d) means for resampling the tangent angles by using the perimeter distances to produce a fixed number of resampled tangent angles each corresponding to an equal proportion of the total perimeter length.
Claim 13
Dependent Claim
28 words
The system of Claim 9 including means for subtracting an increment of circularity from each resampled tangent angle to produce the fixed number of corrected resampled tangent angles.
Claim 14
Dependent Claim
23 words
The system of Claim 10 including means for performing a real Fourier transform on the corrected resampled tangent angles to produce harmonic coefficients.
Claim 15
Dependent Claim
82 words
The system of Claim 11 including means for generating smoothed tangent angle increments by producing a moving average difference of the corrected resampled tangent angles; means for comparing each of the tangent angle increments to a threshold and incrementing a concavity indicator if that tangent angle increment is less than the concavity threshold; and means for comparing each of the tangent angle increments to a threshold and incrementing a convexity indicator if that tangent angle increment is greater than the convexity threshold.
Claim 16
Dependent Claim
104 words
13 . A system for extracting features of a character, the system comprising: (a) means for scanning the character to produce perimeter pixel data and means operating on the perimeter pixel data for generating x and y coordinates, respectively, of each of the corresponding perimeter pixels; (b) means for resampling the x and y coordinates by operating thereon to produce a fixed number of resampled x and y coordinates numbers each representing an equal proportion of the total number of x and y coordinates, respectively; and (c) means for performing a complex Fourier transform on the resampled x and coordinates to produce harmonic coefficients.
Claim 17
Dependent Claim
104 words
13 . A system for extracting features of a character, the system comprising: (a) means for scanning the character to produce perimeter pixel data and means operating on the perimeter pixel data for generating x and y coordinates, respectively, of each of the corresponding perimeter pixels; (b) means for resampling the x and y coordinates by operating thereon to produce a fixed number of resampled x and y coordinates numbers each representing an equal proportion of the total number of x and y coordinates, respectively; and (c) means for performing a complex Fourier transform on the resampled x and coordinates to produce harmonic coefficients.
Claim 18
Independent Claim
93 words
A system for extracting features of a character, the method comprising: (a) means for scanning the character to produce pixel data; (b) means for operating on the pixel data to generate a plurality of hypothetical contiguous ring regions surrounding the character, and means for producing a plurality of ring variables corresponding to the respective ring regions; (c) means for determining the number of dark pixels of the characters that lie within each ring region and setting the corresponding ring variable to that number; and (d) means for eliminating size information from ring variable.
Claim 19
Independent Claim
93 words
A system for extracting features of a character, the method comprising: (a) means for scanning the character to produce pixel data; (b) means for operating on the pixel data to generate a plurality of hypothetical contiguous ring regions surrounding the character, and means for producing a plurality of ring variables corresponding to the respective ring regions; (c) means for determining the number of dark pixels of the characters that lie within each ring region and setting the corresponding ring variable to that number; and (d) means for eliminating size information from ring variable.
Claim 20
Independent Claim
100 words
A system for extracting features of a character, the system comprising: (a) means for scanning the character to produce pixel data; (b) means for operating on the pixel data to generate a plurality of hypothetical contiguous slice regions of a circle surrounding the character, and means for producing a plurality of slice variables corresponding to the respective slice regions; (c) means for determining the number of dark pixels of the characters the lie within each slice region and setting its corresponding slice variable equal to that number; and (d) means for eliminating size information from each of the slice variables.
Claim 21
Independent Claim
100 words
A system for extracting features of a character, the system comprising: (a) means for scanning the character to produce pixel data; (b) means for operating on the pixel data to generate a plurality of hypothetical contiguous slice regions of a circle surrounding the character, and means for producing a plurality of slice variables corresponding to the respective slice regions; (c) means for determining the number of dark pixels of the characters the lie within each slice region and setting its corresponding slice variable equal to that number; and (d) means for eliminating size information from each of the slice variables.
References Cited (Backward Citations)
No citation records indexed.
USPTO Annuity & Maintenance Windows
Maintenance schedule is calculated for granted US utility patents.