Method and apparatus for pattern recognition
First Claim
1. A method for recognizing an unknown, machine-readable pattern as a particular one of a group of known reference patterns comprising:
- providing a group of known reference patterns;
computing the Fourier Transform of each of said group of known reference patterns such that each of the Fourier Transforms of each of said group of known reference patterns includes a center and a zero reference point;
correcting the zero reference point to the center of each said Fourier Transform of each of said group of known reference patterns;
converting the real and imaginary parts of each Fourier Transform to amplitude and phase angle form;
correcting the converted phase angle for proper quadrature;
providing a first memory;
storing said corrected and converted Fourier Transformed reference patterns into a first memory;
computing an amplitude normalization constant for each of said Fourier Transformed patterns;
storing the computed normalization constant for each of said Fourier Transformed patterns in said first memory;
scanning an unknown pattern to be recognized;
generating an electrical signal indicative of said scanned unknown pattern;
providing a second memory;
digitizing said generated electrical signal;
temporarily storing said digitized electrical signal in the second memory;
retrieving said temporarily stored, digitized signal from said second memory;
computing the Fourier Transform of each of said digitized electrical signals such that each Fourier Transform of each of said computed digitized electrical signals includes a center and a zero reference point;
correcting the zero reference point to the center of each Fourier Transform of each of said computed digitized electrical signals indicative of said scanned unknown pattern;
converting the real and imaginary parts of each Fourier Transform of each unknown pattern to amplitude and phase angle form;
correcting the phase angle of each of said converted unknown patterns for proper quadrature;
storing said corrected and converted Fourier Transformed unknown patterns into said second memory, each of said converted, Fourier Transformed unknown patterns having amplitude values with differences existing therebetween;
computing an amplitude normalization constant for each of said Fourier Transformed unknown patterns;
normalizing the amplitude values of the converted Fourier Transformed, unknown pattern stored in said second memory by multiplying same with said normalization constant to eliminate the absolute difference in amplitude value between the Fourier Transformed unknown pattern and each Fourier Transformed reference pattern;
correcting for phase alignment error;
correcting for quadrant error;
computing the phase difference between the Fourier Transformed unknown pattern and each Fourier Transformed reference pattern;
weighting the phase difference by the amplitude of the Fourier Transformed unknown pattern at each frequency point;
comparing the absolute phase differences between the Fourier Transformed unknown pattern and the Fourier Transformed reference patterns;
summing the amplitude and phase differences over all Fourier Transformed reference patterns;
determining the best amplitude difference match between the Fourier Transformed unknown pattern and the Fourier Transformed reference pattern and the best phase difference match between the Fourier Transformed unknown pattern and the Fourier Transformed reference pattern, in combination;
computing the average differences between the Fourier Transformed unknown pattern and the Fourier Transformed reference patterns;
weighting the amplitude difference and phase difference, in combination, equally for each Fourier Transformed reference pattern and by the amount that they are less than the average differences, said weighted reference patterns having at least a first, and a second and minimum values; and
locating the minimum value to identify the particular Fourier Transformed reference pattern which is the "best match" for the Fourier Transformed unknown pattern.
0 Assignments
0 Petitions
Accused Products
Abstract
A method and apparatus for recognizing an unknown character, pattern, or indicia, or the like as being a particular one of a group of known reference characters, patterns, indicia, or the like. In the preferred embodiment, the system converts scanned and digitized MICR data and uses it to identify the character. The reference characters and the unknown character are Fourier Transformed and various corrections are made for eliminating the absolute amplitude difference from the recognition process, while simultaneously providing a method of correcting for position differences between the reference charcter and the unknown character. Provisions are made for weighting the phase differences proportional to the expected accuracy of the phase data to minimize the effects of noise on the measurement, and for combining the amplitude and phase data to define a single "best match" criteria for the unknown character. The input data is stored in memory and later converted to real and imaginary frequency components through the Fourier Transform process. The real and imaginary parts are converted to amplitude and phase as a function of frequency and both the amplitude and the phase data are corrected for position errors and the like. They are then compared to a set of amplitude and phase data for the group of standard known characters. The particular one of the known reference characters which is closest to the transform of the unknown character is designated as the "best match". The second minimum is located, and the percentage that the best match is better than the second best match is used to determine a margin of error criteria.
-
Citations
27 Claims
-
1. A method for recognizing an unknown, machine-readable pattern as a particular one of a group of known reference patterns comprising:
-
providing a group of known reference patterns; computing the Fourier Transform of each of said group of known reference patterns such that each of the Fourier Transforms of each of said group of known reference patterns includes a center and a zero reference point; correcting the zero reference point to the center of each said Fourier Transform of each of said group of known reference patterns; converting the real and imaginary parts of each Fourier Transform to amplitude and phase angle form; correcting the converted phase angle for proper quadrature; providing a first memory; storing said corrected and converted Fourier Transformed reference patterns into a first memory; computing an amplitude normalization constant for each of said Fourier Transformed patterns; storing the computed normalization constant for each of said Fourier Transformed patterns in said first memory; scanning an unknown pattern to be recognized; generating an electrical signal indicative of said scanned unknown pattern; providing a second memory; digitizing said generated electrical signal; temporarily storing said digitized electrical signal in the second memory; retrieving said temporarily stored, digitized signal from said second memory; computing the Fourier Transform of each of said digitized electrical signals such that each Fourier Transform of each of said computed digitized electrical signals includes a center and a zero reference point; correcting the zero reference point to the center of each Fourier Transform of each of said computed digitized electrical signals indicative of said scanned unknown pattern; converting the real and imaginary parts of each Fourier Transform of each unknown pattern to amplitude and phase angle form; correcting the phase angle of each of said converted unknown patterns for proper quadrature; storing said corrected and converted Fourier Transformed unknown patterns into said second memory, each of said converted, Fourier Transformed unknown patterns having amplitude values with differences existing therebetween; computing an amplitude normalization constant for each of said Fourier Transformed unknown patterns; normalizing the amplitude values of the converted Fourier Transformed, unknown pattern stored in said second memory by multiplying same with said normalization constant to eliminate the absolute difference in amplitude value between the Fourier Transformed unknown pattern and each Fourier Transformed reference pattern; correcting for phase alignment error; correcting for quadrant error; computing the phase difference between the Fourier Transformed unknown pattern and each Fourier Transformed reference pattern; weighting the phase difference by the amplitude of the Fourier Transformed unknown pattern at each frequency point; comparing the absolute phase differences between the Fourier Transformed unknown pattern and the Fourier Transformed reference patterns; summing the amplitude and phase differences over all Fourier Transformed reference patterns; determining the best amplitude difference match between the Fourier Transformed unknown pattern and the Fourier Transformed reference pattern and the best phase difference match between the Fourier Transformed unknown pattern and the Fourier Transformed reference pattern, in combination; computing the average differences between the Fourier Transformed unknown pattern and the Fourier Transformed reference patterns; weighting the amplitude difference and phase difference, in combination, equally for each Fourier Transformed reference pattern and by the amount that they are less than the average differences, said weighted reference patterns having at least a first, and a second and minimum values; and locating the minimum value to identify the particular Fourier Transformed reference pattern which is the "best match" for the Fourier Transformed unknown pattern. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15)
-
11. The method of claim 10 further including the step of computing a first and a second phase correction by selecting a frequency which is higher than the previously selected frequency and calculating the phase shift by the equations which take into account the digital implementation of the method as given by:
- ##EQU9## where "n1 " is the transform point chosen to estimate the first phase correction, where "φ
'"'"' (n)" is the phase after the first correction applied to all "n" phase values, "n2 " is the transform point chosen to estimate the second phase correction, and "φ
"u (n)" is the phase after the second phase correction which is applied to all "n" phase values. The resulting phase angles are then adjusted to range from -180°
to +180°
by the equations;
space="preserve" listing-type="equation">If φ
>
+180°
, then φ
=φ
-360°
; and
space="preserve" listing-type="equation">If φ
<
-180°
, then φ
=φ
+360°
.
- ##EQU9## where "n1 " is the transform point chosen to estimate the first phase correction, where "φ
-
12. The method of claim 1 wherein the step of computing the absolute phase difference between the Fourier Transformed unknown pattern and the Fourier Transformed reference pattern, with the phase differences weighted by the amplitude of the unknown character at each frequency point being given by the Equation ##EQU10## where the term Au (n)/C2 is the amplitude weighting factor at the nth frequency and the phase difference which must be adjusted to the range -180°
- to +180°
or given by the equations;
space="preserve" listing-type="equation">If φ
>
+180°
, then φ
=φ
-360°
; and
space="preserve" listing-type="equation">If φ
<
-180°
, then φ
=φ
+360°
.
- to +180°
-
13. The method of claim 12 wherein the step of summing the amplitude and phase differences includes computing the sum of the amplitude differences by the Equation ##EQU11## and computing the sum of the phase differences by the Equation ##EQU12##
-
14. The method of claim 13 wherein the step of determining a combined amplitude and phase match value is determined for each reference pattern by the Equation ##EQU13## where NS is the number of known reference characters and the equation essentially weights the amplitude and phase differences equally and by the amount they are less than the average differences so that a perfect match in amplitude and phase produce a value of Mk =0.
-
15. The method of claim 1 wherein said step of locating the second minimum to determine a margin of error criteria is computed by the Equation ##EQU14## where MINhd 1 l is the first minimum value and MIN2 is the second minimum value.
-
-
16. A method for recognizing an unknown, machine-readable character as being a particular one of a group of known reference characters comprising the steps of:
-
providing a set of known reference characters; Fourier Transforming the set of known reference characters; storing the Fourier Transformed set of known reference characters in a database; Fourier Transforming the unknown character to be recognized; comparing the complete Fourier Transform, utilizing both the amplitude and phase portions of the Fourier Transform, of the unknown character with each of the complete Fourier Transforms including both the amplitude and phase portions, of the known reference characters to determine a best match; further comparing the complete Fourier Transform of the unknown character with each of the complete Fourier Transforms of the reference characters to determine a second best match; and computing the percentage difference between the second best match and the best match to provide the margin of error of the recognition process, such margin of error being usable to adjust recognition probability and false alarm rates.
-
-
17. The system for recognizing an unknown character as being a particular one of a group of known reference characters comprising;
-
means for scanning a media for an unknown, machine-readable character; means for generating an electrical signal indicative of the scanned unknown character; means for digitizing the electrical signal indicative of the scanned unknown character; and first memory means for storing the digitized value of the unknown character; means for introducing a group of known reference characters; a central processing unit for controlling said scanning means used to generate the electrical signal; video display means responsive to said central processing unit for displaying the contents of said first memory means; a Fourier Transform processor means for; (a) calculating the complete Fourier Transform of each of said group of known reference characters; (b) performing amplitude spectra matching calculations; (c) performing phase angle matching calculations; (d) performing position correction calculations; (d) performing phase angle corrections; (f) calculating amplitude weighting factors for phase adjustment purposes; (g) performing adjustments for proper quadrature; (h) computing normalization constants for each of the known reference characters; (i) computing the absolute amplitude difference between the complete Fourier Transformed unknown character and the complete Fourier Transformed reference characters; (j) computing the absolute phase difference between the complete Fourier Transformed unknown character and the complete Fourier Transformed known reference characters; (k) computing a combined amplitude and phase match value for each of the complete Fourier Transformed known reference characters; (l) determining a minimum value indicating the "best match" between the complete Fourier Transformed unknown character and the complete Fourier Transformed known reference character; (m) determining a second minimum value indicating a "second best match" between the complete Fourier Transformed unknown character and the complete Fourier Transformed known reference character; (n) computing and determining a second minimum value and determining the percentage that the best match is better than the second best match; and (o) utilizing the determined percentage as a margin of error criterion for adjusting recognition probability and the probability of false alarm rates.
-
-
18. An improved method for recognizing an unknow machine-readable character as a particular one of a group of known reference characters including computing the complete Fourier Transform of a group of unknown characters, converting both the real and imaginary part of each Fourier Transform to amplitude and phase form, correcting the phase angles for proper quadrature, computing amplitude and time base normalization constants for each Fourier Transform, computing the Fourier Transform of the digital values of the unknown characters, converting the real and imaginary parts of each Fourier Transform of each of said unknown characters into amplitude and phase form, wherein the improvement comprises the steps of:
-
(a) normalizing the amplitude value of each of the unknown characters by a normalization constant to eliminate the absolute amplitude between unknown and known reference characters; (b) computing the amplitude difference between unknown characters and each known reference character; (c) computing a first and second phase correction; (d) computing the absolute phase difference between each unknown character and each of the known reference characters; (e) summing the amplitude and phase differences; and (f) determining the combined amplitude and phase match value for a "best match" to indicate which of the group of known reference characters corresponds to the unknown character. - View Dependent Claims (19, 20, 21, 22, 23, 24, 25, 26, 27)
-
Specification