A statistical algorithm for efficient computation of correlations

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