A statistical algorithm for efficient computation of correlations

Author

Schils, George F.

Author_Institution

Sandia Nat. Lab., Livermore, CA, USA

Volume

40

Issue

11

fYear

1992

fDate

11/1/1992 12:00:00 AM

Firstpage

2857

Lastpage

2863

Abstract

A statistical method is employed to approximate the operation of correlation. By using Bernoulli sampling to generate the template or correlation mask, a sparse template can be produced. The sampling procedure is shown to produce an unbiased estimate of the correlation signal. The variance of the output signal is also evaluated. Various approximation accuracies can be obtained by proper design of the correlation template. Because the templates produced by this technique are binary and sparse, the correlation operation can be implemented very efficiently. It is shown that the computational complexity of this algorithm for implementing correlation is N² (for images), where N is the linear dimension of the images. The technique is illustrated on an example

Keywords

computational complexity; correlation theory; image processing; pattern recognition; signal processing; statistical analysis; Bernoulli sampling; computational complexity; correlation mask; correlation operation; correlation signal; image processing; output signal variance; pattern recognition; signal processing; sparse template; statistical algorithm; stochastic process; Autocorrelation; Finite impulse response filter; Frequency domain analysis; Multidimensional systems; Pattern recognition; Signal design; Signal processing algorithms; Signal sampling; Statistical analysis; Wiener filter;

fLanguage

English

Journal_Title

Signal Processing, IEEE Transactions on

Publisher

ieee

ISSN

1053-587X

Type

jour

DOI

10.1109/78.165680

Filename

165680