Browse Prior Art Database

High Speed Correlation Method

IP.com Disclosure Number: IPCOM000080021D
Original Publication Date: 1973-Oct-01
Included in the Prior Art Database: 2005-Feb-26
Document File: 3 page(s) / 47K

Publishing Venue

IBM

Related People

Cooley, JW: AUTHOR [+2]

Abstract

There is described herein a FFT (Fast Fourier Transform) based procedure to be used in those situations where there are a large number of classes, each represented by a high dimensional reference vector, and wherein there is a classification procedure based upon a maximum correlation with the reference vector over a large shift range. The method described significantly reduces computation in that situation where the allowable maximum shift is large, but small compared to the reference vector dimensionality.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 52% of the total text.

Page 1 of 3

High Speed Correlation Method

There is described herein a FFT (Fast Fourier Transform) based procedure to be used in those situations where there are a large number of classes, each represented by a high dimensional reference vector, and wherein there is a classification procedure based upon a maximum correlation with the reference vector over a large shift range. The method described significantly reduces computation in that situation where the allowable maximum shift is large, but small compared to the reference vector dimensionality.

The method is particularly applicable to the implementation of pattern recognition, schemes which decide in favor of that pattern which maximizes the correlation function. The method is a modification of the FFT method of evaluating correlation functions and is particularly advantageously employed when a number of cross-correlations are being evaluated.

The method is described in mathematical form. However, an algorithm is facilely derivable therefrom which is readily implementable into program form, based upon known methods of programming Fast Fourier Transform (FFT) techniques.

In considering the method, let it be assumed that x (j), wherein j = 0,1,...,N-1 is a vector whose class membership is uncertain. Let it be further assumed that y(1)(j),...,y(L)(j), wherein j = 0,1,...N-1 are L reference vectors corresponding to L classes of vectors. Let it be assumed that it is desired to decide the class membership x(j) on the basis of the functions

(Image Omitted)

l = 1,...,L or some normalized version of these functions. Typically, it would be decided in favor of the maximum of m(1),..., m(L) where In these cases, it is desired to calculate

(Image Omitted)

in as an efficient manner as is possible.

If the foregoing calculation is performed directly using the defining formula for gamma(l)(k) approximately (N-K/2)L(2K+1) multiply-adds are required. A second method of evaluating gamma(l)(k) for l = 1,..., L ; -K </- k = K is by the fast Fourier transform. In this latter method, at least 2K zeros are appended to x(j), y(1)(j),..., y(L)(j) and their discrete Fourier transforms are taken. If these transforms are termed a(n), b(1)(n),..., b (n), respectively, then the products a(n)b(1)(n), a(n)b(2) (n),...., a(n)b(L)(n) are formed, where a(n) is the complex conjugate of a(n-) and their inverse discrete Fourier transforms are taken. Terming these latter Fourier transforms z(1)(j),..., z(L)(j), then the gamma(l) (k) are obtained as gamma(l)(k) = z(l)(k) -K </- k </- K l = 1,...,L. If it is assumed that the b(1)(n),..., b(L)(n) are stored and not calculated each time, then this approach requires approximately 2(L+1)(N+2K) log (N+2K) multiply-adds. Therefore if 2 log(2) (N+2K) over 2K+1 < < 1 the substantial advantage presented by the fast Fourier transform approach becomes quickly apparent.

1

Page 2 of 3

In many situations, K is very small compared with N. Consequently, advantage can be taken of this fact and a m...