US3614736A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Pattern recognition apparatus and methods invariant to translation, scale change and rotation
Assignee: International Business Machines Corp
•
Filing: 1968-05-21
•
Granted: 1971-10-19
•
Expires: 1988-05-21
Abstract
Abstract A pattern recognition system is disclosed which will recognize patterns irrespective of their translation rotation or scale change. Input data may be provided by a scanner or other suitable data source. Means for calculating the center of gravity, or alternatively the autocorrelation function are provided which can be employed; and then the data can be transformed for an actual or simulated annular or equivalently radial scan, with exponential spacing along radii. Alternatively, a straightforward raster scan may be employed for recognition which is invarient to translation only. The output is then processed in means for cross correlating with known patterns. The result is preferably raised to the Nth power and summed. Alternatively, 2 can be raised to the power of the cross correlation times K and summed which is easily done on a digital computer, or finally the result can be subjected to maximum operation. In all cases, the pattern is then processed through corresponding means for normalization including a storage device, a multiplier and a decision function unit. Prior to operation for pattern recognition, the system is operated with the normalization storage connected through an inverter to the output of one of the Nth power, power of 2 or maximum operation units for receiving the appropriately processed data relative to a sample for normalization. Then the appropriate normalization may be supplied for each mode of processing after cross correlation.
Inventors
- 👤 John A Mclaughlin
- 👤 Josef Raviv
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-24 12:32
CPC Classifications
G; G06; G06V; G06V10/00; G06V10/40; G06V10/42; G06V10/20; G06V10/70; G06V10/74; G06V10/75
Claims Analysis
Total Claims: 16
Claim 1
Independent Claim
222 words
A pattern recognition method for operating data handling apparatus including a first step for receiving data representing an unknown pattern, means for effectively scanning by sampling selectively at exponentially spaced points on said pattern starting at a predetermined point for producing scanned data, cross-correlating said scanned data with a plurality of known patterns, an Nth power step for raising each output value of said crosscorrelating step to the Nth power, where N n+1 and n is an integer greater than one and summing over a range of shifted values of relative positions of the sample with respect to the reference wherein the functions of the above steps are defined by the formula as follows: where S(1) (Z) is a function of sampling a sample pattern S with an exponential scan as a function of an independent variable quantity Z in which several numerical values of Z are selected as desired to sample the pattern, and where Ra(1)(Z+K1) is a function resulting from an exponential scan of a reference Ra which is adapted to be shifted linearly by an independent variable K1 which is varied by numerical increments for the purpose of cross-correlation as values of K1 are substituted into the expression and preselected and normalizing the output signal of said power step with a signal representative of where C1 is a constant.
Claim 2
Dependent Claim
222 words
A pattern recognition method for operating data handling apparatus including a first step for receiving data representing an unknown pattern, means for effectively scanning by sampling selectively at exponentially spaced points on said pattern starting at a predetermined point for producing scanned data, cross-correlating said scanned data with a plurality of known patterns, an Nth power step for raising each output value of said crosscorrelating step to the Nth power, where N n+1 and n is an integer greater than one and summing over a range of shifted values of relative positions of the sample with respect to the reference wherein the functions of the above steps are defined by the formula as follows: where S(1) (Z) is a function of sampling a sample pattern S with an exponential scan as a function of an independent variable quantity Z in which several numerical values of Z are selected as desired to sample the pattern, and where Ra(1)(Z+K1) is a function resulting from an exponential scan of a reference Ra which is adapted to be shifted linearly by an independent variable K1 which is varied by numerical increments for the purpose of cross-correlation as values of K1 are substituted into the expression and preselected and normalizing the output signal of said power step with a signal representative of where C1 is a constant.
Claim 3
Independent Claim
218 words
A method for operating data handling apparatus for recognizing a pattern comprising: first receiving data representing said pattern, effectively scanning by sampling selectively at exponentially spaced points on said received pattern starting at a predetermined point for producing scanned data, cross-correlating said scanned data with a plurality of known patterns, an Nth power step for raising each output value of said cross-correlating step to the Nth power, where N n+1 and n is an integer greater than one and for summing over a range of shifted values of relative positions of the sample reference wherein the functions of the above steps are defined by the formula as follows: where S(1) (Z) is a function of sampling a sample pattern S with an exponential scan as a function of an independent variable quantity Z in which several numerical values of Z are selected as desired to sample the pattern, and where Ra(1)(Z+K1) is a function resulting from an exponential scan of a reference Ra which is adapted to be shifted linearly by an independent variable K1 which is varied by numerical increments for the purpose of cross-correlation as values of K1 are substituted into the expression and preselected and means for normalizing the output signal of said power step with a signal representative of where C1 is a constant.
Claim 4
Independent Claim
218 words
A method for operating data handling apparatus for recognizing a pattern comprising: first receiving data representing said pattern, effectively scanning by sampling selectively at exponentially spaced points on said received pattern starting at a predetermined point for producing scanned data, cross-correlating said scanned data with a plurality of known patterns, an Nth power step for raising each output value of said cross-correlating step to the Nth power, where N n+1 and n is an integer greater than one and for summing over a range of shifted values of relative positions of the sample reference wherein the functions of the above steps are defined by the formula as follows: where S(1) (Z) is a function of sampling a sample pattern S with an exponential scan as a function of an independent variable quantity Z in which several numerical values of Z are selected as desired to sample the pattern, and where Ra(1)(Z+K1) is a function resulting from an exponential scan of a reference Ra which is adapted to be shifted linearly by an independent variable K1 which is varied by numerical increments for the purpose of cross-correlation as values of K1 are substituted into the expression and preselected and means for normalizing the output signal of said power step with a signal representative of where C1 is a constant.
Claim 5
Dependent Claim
250 words
A pattern recognition method for operating data handling apparatus including the data processing steps as follows: a first step for receiving data representing said pattern, effectively selectively sampling by annularly scanning said centered pattern centered at a predetermined point with radii spaced exponentially for producing scanned data, cross-correlating said scanned data with a plurality of known patterns, an Nth power step for raising each output value of said cross-correlating step to the Nth power, where N n+1 and n is an integer greater than one and summing over a range of shifted values of relative sample with respect to the reference positions wherein the functions of the above steps are defined by the formula as follows: where (2) (Z, theta ) is a function of sampling a sample pattern S with an exponential scan as a function of an independent variable quantity Z and an independently varying angular quantity theta , and where Ra(2) (Z+K1, theta + theta (1)) is an exponential scan of a reference pattern Ra with a concomitant angular scan theta and where K1 represents an independent variable providing a linear shift for purposes of cross-correlation with the sample function S(2) (Z, theta ) and where theta (1) represents an independent variable providing an angular shift for cross-correlation with the sample function S(2) (Z, theta ) where K1 and theta (1) are varied by preselected numerical increments, means for normalizing the output signal of said power means with a signal representative of where C1 is a constant.
Claim 6
Dependent Claim
250 words
A pattern recognition method for operating data handling apparatus including the data processing steps as follows: a first step for receiving data representing said pattern, effectively selectively sampling by annularly scanning said centered pattern centered at a predetermined point with radii spaced exponentially for producing scanned data, cross-correlating said scanned data with a plurality of known patterns, an Nth power step for raising each output value of said cross-correlating step to the Nth power, where N n+1 and n is an integer greater than one and summing over a range of shifted values of relative sample with respect to the reference positions wherein the functions of the above steps are defined by the formula as follows: where (2) (Z, theta ) is a function of sampling a sample pattern S with an exponential scan as a function of an independent variable quantity Z and an independently varying angular quantity theta , and where Ra(2) (Z+K1, theta + theta (1)) is an exponential scan of a reference pattern Ra with a concomitant angular scan theta and where K1 represents an independent variable providing a linear shift for purposes of cross-correlation with the sample function S(2) (Z, theta ) and where theta (1) represents an independent variable providing an angular shift for cross-correlation with the sample function S(2) (Z, theta ) where K1 and theta (1) are varied by preselected numerical increments, means for normalizing the output signal of said power means with a signal representative of where C1 is a constant.
Claim 7
Independent Claim
245 words
A method for recognizing a pattern comprising: a first step for receiving data representing said pattern, determining the center of gravity of the pattern based upon the output of said first step to produce data representing a centered pattern, effectively selectively sampling by annularly scanning said centered pattern data centered at a predetermined point with radii spaced exponentially for Producing scanned data, cross-correlating said scanned data with a plurality of known patterns, an Nth power step for raising each output value of said means for cross-correlating step to the Nth power, where N n+1 and n is an integer greater than one and for summing over a range of shifted values of relative positions of the sample with respect to the reference wherein the functions of the above steps are defined by the formula as follows: where S(1) (Z) is a function of sampling a sample pattern S with an exponential scan as a function of an independent variable quantity Z in which several numerical values of Z are selected as desired to sample the pattern, and where Ra(1) (Z+K1) is a function resulting from an exponential scan of a reference Ra which is adapted to be shifted linearly by an independent variable K1 which is varied by numerical increments for the purpose of cross-correlation as values of K1 are substituted into the expression and preselected and normalizing the output signal of said power step with a signal representative of where C1 is a constant.
Claim 8
Independent Claim
245 words
A method for recognizing a pattern comprising: a first step for receiving data representing said pattern, determining the center of gravity of the pattern based upon the output of said first step to produce data representing a centered pattern, effectively selectively sampling by annularly scanning said centered pattern data centered at a predetermined point with radii spaced exponentially for Producing scanned data, cross-correlating said scanned data with a plurality of known patterns, an Nth power step for raising each output value of said means for cross-correlating step to the Nth power, where N n+1 and n is an integer greater than one and for summing over a range of shifted values of relative positions of the sample with respect to the reference wherein the functions of the above steps are defined by the formula as follows: where S(1) (Z) is a function of sampling a sample pattern S with an exponential scan as a function of an independent variable quantity Z in which several numerical values of Z are selected as desired to sample the pattern, and where Ra(1) (Z+K1) is a function resulting from an exponential scan of a reference Ra which is adapted to be shifted linearly by an independent variable K1 which is varied by numerical increments for the purpose of cross-correlation as values of K1 are substituted into the expression and preselected and normalizing the output signal of said power step with a signal representative of where C1 is a constant.
Claim 9
Dependent Claim
223 words
A pattern recognition apparatus comprising: first means for receiving data representing an unknown pattern comprising means for effectively scanning by sampling selectivity at exponentially spaced points on said pattern starting at a predetermined point for producing scanned data, means for cross-correlating said scanned data with a plurality of known patterns, Nth power means for raising each output value of said means for cross-correlating to the Nth power, where N n+1 and n is an integer greater than one and for summing over a range of shifted values of relative positions of the sample with respect to the reference wherein the functions of the above means are defined by the formula as follows: where S(1) (Z) is a function of sampling a sample pattern S with an exponential scan as a function of an independent variable quantity Z in which several numerical values of Z are selected as desired to sample the pattern, and where Ra(1) (Z+K1) is a function resulting from an exponential scan of a reference Ra which is adapted to be shifted linearly by an independent variable K1 which is varied by numerical increments for the purpose of cross-correlation as values of K1 are substituted into the expression and preselected and means for normalizing the output signal of said power means with a signal representative of where C1 is a constant.
Claim 10
Dependent Claim
223 words
A pattern recognition apparatus comprising: first means for receiving data representing an unknown pattern comprising means for effectively scanning by sampling selectivity at exponentially spaced points on said pattern starting at a predetermined point for producing scanned data, means for cross-correlating said scanned data with a plurality of known patterns, Nth power means for raising each output value of said means for cross-correlating to the Nth power, where N n+1 and n is an integer greater than one and for summing over a range of shifted values of relative positions of the sample with respect to the reference wherein the functions of the above means are defined by the formula as follows: where S(1) (Z) is a function of sampling a sample pattern S with an exponential scan as a function of an independent variable quantity Z in which several numerical values of Z are selected as desired to sample the pattern, and where Ra(1) (Z+K1) is a function resulting from an exponential scan of a reference Ra which is adapted to be shifted linearly by an independent variable K1 which is varied by numerical increments for the purpose of cross-correlation as values of K1 are substituted into the expression and preselected and means for normalizing the output signal of said power means with a signal representative of where C1 is a constant.
Claim 11
Dependent Claim
223 words
Apparatus for recognizing a pattern comprising: first means for receiving data representing said pattern, means for effectively scanning by sampling selectively at exponentially spaced points on said received pattern starting at a predetermined point for producing scanned data, means for cross-correlating said scanned data with a plurality of known patterns, Nth power means for raising each output value of said means for cross-correlating to the Nth power, where N n+1 and n is an integer greater than one and for summing over a range of shifted values of relative positions of the sample with respect to the reference wherein the functions of the above means are defined by the formula as follows: where S(1) (Z) is a function of sampling a sample pattern S with an exponential scan as a function of an independent variable quantity Z in which several numerical values of Z are selected as desired to sample the pattern, and where Ra(1) (Z+K1) is a function resulting from an exponential scan of a reference Ra which is adapted to be shifted linearly by an independent variable K1 which is varied by numerical increments for the purpose of cross-correlation as values of K1 are substituted into the expression and preselected and means for normalizing the output signal of said power means with a signal representative of where C1 is a constant.
Claim 12
Dependent Claim
223 words
Apparatus for recognizing a pattern comprising: first means for receiving data representing said pattern, means for effectively scanning by sampling selectively at exponentially spaced points on said received pattern starting at a predetermined point for producing scanned data, means for cross-correlating said scanned data with a plurality of known patterns, Nth power means for raising each output value of said means for cross-correlating to the Nth power, where N n+1 and n is an integer greater than one and for summing over a range of shifted values of relative positions of the sample with respect to the reference wherein the functions of the above means are defined by the formula as follows: where S(1) (Z) is a function of sampling a sample pattern S with an exponential scan as a function of an independent variable quantity Z in which several numerical values of Z are selected as desired to sample the pattern, and where Ra(1) (Z+K1) is a function resulting from an exponential scan of a reference Ra which is adapted to be shifted linearly by an independent variable K1 which is varied by numerical increments for the purpose of cross-correlation as values of K1 are substituted into the expression and preselected and means for normalizing the output signal of said power means with a signal representative of where C1 is a constant.
Claim 13
Dependent Claim
243 words
A pattern recognition apparatus first means for receiving data representing said pattern, means for effectively selectively sampling by annularly scanning said centered pattern centered at a predetermined point with radii spaced exponentially for producing scanned data, means for cross-correlating said scanned data with a plurality of known patterns, Nth power, means for raising each output value of said means for cross-correlating to the Nth power, where N n+1 and n is an integer greater than one and summing over a range of shifted values of relative positions of the sample with respect to the reference wherein the functions of the above means are defined by the formula as follows: where S2 (Z, theta ) is a function of sampling a sample pattern S with an exponential scan as a function of an independent variable quantity Z and an independently varying angular quantity theta , and where Ra(2) (Z+K1, theta + theta (1)) is an exponential scan of a reference pattern Ra with a concomitant angular scan theta and where K1 represents an independent variable providing a linear shift for purposes of cross-correlation with the sample function S(2) (Z, theta ) and where theta (1) represents an independent variable providing an angular shift for cross-correlation with the sample function S(2) (Z, theta ) where K1 and theta (1) are varied by preselected numerical increments, means for normalizing the output signal of said power means with a signal representative of where C1 is a constant.
Claim 14
Dependent Claim
243 words
A pattern recognition apparatus first means for receiving data representing said pattern, means for effectively selectively sampling by annularly scanning said centered pattern centered at a predetermined point with radii spaced exponentially for producing scanned data, means for cross-correlating said scanned data with a plurality of known patterns, Nth power, means for raising each output value of said means for cross-correlating to the Nth power, where N n+1 and n is an integer greater than one and summing over a range of shifted values of relative positions of the sample with respect to the reference wherein the functions of the above means are defined by the formula as follows: where S2 (Z, theta ) is a function of sampling a sample pattern S with an exponential scan as a function of an independent variable quantity Z and an independently varying angular quantity theta , and where Ra(2) (Z+K1, theta + theta (1)) is an exponential scan of a reference pattern Ra with a concomitant angular scan theta and where K1 represents an independent variable providing a linear shift for purposes of cross-correlation with the sample function S(2) (Z, theta ) and where theta (1) represents an independent variable providing an angular shift for cross-correlation with the sample function S(2) (Z, theta ) where K1 and theta (1) are varied by preselected numerical increments, means for normalizing the output signal of said power means with a signal representative of where C1 is a constant.
Claim 15
Dependent Claim
248 words
Apparatus for recognizing a pattern comprising: first means for receiving data representing said pattern, means for determining the center of gravity of the pattern based upon the output of said first means to produce data representing a centered pattern, means for effectively selectively sampling by annularly scanning said centered pattern centered at a predetermined point with radii spaced exponentially for producing scanning data, means for cross-correlating said scanned data with a plurality of known patterns, Nth power means for raising each output value of said means for cross-correlating to the Nth power, where N n+1 and n is an integer greater than one and for summing over a range of shifted values of relative positions of the sample with respect to the reference wherein the functions of the above means are defined by the formula as follows: where S(1) (Z) is a function of sampling a sample pattern S with an exponential scan as a function of an independent variable quantity Z in which several numerical values of Z are selected as desired to sample the pattern, and where Ra(1) (Z+K1) is a function resulting from an exponential scan of a reference Ra which is adapted to be shifted linearly by an independent variable K1 which is varied by numerical increments for the purpose of cross-correlation as values of K1 are substituted into the expression and preselected and means for normalizing the output signal of said power means with a signal representative of where C1 is a constant.
Claim 16
Dependent Claim
248 words
Apparatus for recognizing a pattern comprising: first means for receiving data representing said pattern, means for determining the center of gravity of the pattern based upon the output of said first means to produce data representing a centered pattern, means for effectively selectively sampling by annularly scanning said centered pattern centered at a predetermined point with radii spaced exponentially for producing scanning data, means for cross-correlating said scanned data with a plurality of known patterns, Nth power means for raising each output value of said means for cross-correlating to the Nth power, where N n+1 and n is an integer greater than one and for summing over a range of shifted values of relative positions of the sample with respect to the reference wherein the functions of the above means are defined by the formula as follows: where S(1) (Z) is a function of sampling a sample pattern S with an exponential scan as a function of an independent variable quantity Z in which several numerical values of Z are selected as desired to sample the pattern, and where Ra(1) (Z+K1) is a function resulting from an exponential scan of a reference Ra which is adapted to be shifted linearly by an independent variable K1 which is varied by numerical increments for the purpose of cross-correlation as values of K1 are substituted into the expression and preselected and means for normalizing the output signal of said power means with a signal representative of where C1 is a constant.
References Cited (Backward Citations)
US3104369A
Cited
US3104371A
Cited
US3196394A
Cited
US3292148A
Cited
US3196397A
Cited
US3278899A
Cited
US3492646A
Cited
US3435244A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1974-10-18 | 1975-04-19 | 1975-10-19 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1978-10-18 | 1979-04-19 | 1979-10-19 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 1982-10-18 | 1983-04-19 | 1983-10-19 | $7700.00 | Window Closed / Lapsed |