1,223,348. Pattern recognition; calculating. INTERNATIONAL BUSINESS MACHINES CORP. 25 April, 1969 [21 May, 1968], No. 21209/69. Headings G4A and G4R. A pattern recognition system compares an effective Nth order self-scale function or Nth order hybrid self function of an unknown pattern with the same function of a reference pattern, or generates and raises to the Nth power the cross-correlation of unknown and reference pattern data. Data from a raster scan of the unknown pattern is stored in a first utility memory as data with associated X and Y co-ordinates, the centre of gravity of the pattern is calculated from this information and the co-ordinates are then altered so as to be relative to this centre of gravity as origin (displaced by a constant vector so that no co-ordinate will be negative). The data is then transferred to a second utility memory in such a way that the results simulate an annular scan of the pattern with exponentially increasing radius, using addresses read from the second memory to address the first. Apart from these addresses and the transferred data, the second memory contains polar coordinates of the data. The data and polar coordinates are transferred to an input signal memory and from there the data is crosscorrelated with reference data from L reference memories in turn, where L is the number of possible patterns, as follows. For a given reference memory, the locations of a correlation result memory are addressed in turn, and for each, each item of data in the input signal memory is multiplied by data obtained by addressing the reference memory with the concatenation of the polar co-ordinates associated with the data item in the input signal memory, each incremented by a respective quantity preloaded in the addressed location of the correlation result memory and either changed, if necessary, to lie in a certain range or preventing addressing if outside a certain range. The results of the multiplications are accumulated, then stored in the addressed location of the correlation result memory. The correlation results for a given reference pattern are then either each raised to the Nth power and then accumulated, or each raised as a power to 2 and then accumulated, or the largest is selected. Whichever of these three non-linear operations is used, a result is obtained for each of the reference patterns. Each such result is divided (or multiplied) by a respective normalization factor from a memory to give a quantity, the largest of such quantities from the reference patterns considered so far, being passed together with reference pattern identifiers, to an output memory for a recognition decision. In the case of the third non-linear operation above (" largest "), quantities in effect selected from the correlation result memory indicating size, rotation &c. are also passed. The raising to the Nth power is done by repeated multiplication by itself, whereas the raising as a power to 2 is done by loading a shift register with 000 ... 0001, and left-shifting while decrementing the quantity to be raised, to zero. Autocorrelation may replace the centre of gravity manipulations. The cross-correlation may be done with the original pattern data. During a learning mode using reference patterns, the reference memories are loaded with what they would be correlated with in recognition mode, and the normalization factor memory is loaded with the square-roots of the results from the non-linear operation used (on the reference patterns). The operations above are equivalent to evaluating similarity functions which are the normalized integral of the product of the Nth order autocorrelation functions of the unknown pattern and a reference pattern (translation invariant), or similar quantities using Nth order self scale functions (which are integrals invariant to scale change) or Nth order hybrid self-functions (which are integrals invariant to scale and rotation) in place of the Nth order autocorrelation functions, or normalized quantities involving sums of exponentials of sums of products, or normalized quantities involving maxima of sums of products. Integrals are evaluated as sums, operations being electric digital throughout. The mathematical expressions are given in the Specification.
展开▼
