The "invaders" algorithm: range of values modulation for accelerated correlation

In this paper, we present an algorithm that allows the simultaneous calculation of several cross correlations. The algorithm works by shifting the range of values of different images/signals to occupy different orders of magnitude and then combining them to form a single composite image/signal. Because additional signals are placed in the space usually occupied by a single signal, we call this the "invaders algorithm," to imply that extra signals invade the space that normally belongs to a single signal. After correlation is performed, the individual results are recovered by performing the inverse operation. The limitations of the algorithm are imposed by the finite length of the mantissa of the hardware used, the precision of the algorithm that performs the cross correlation (e.g., the precision of the fast Fourier transform (FFT)) and by the actual values of the images/signals that are to be combined. The algorithm does not require any special hardware or special FFT algorithm. For typical 256 x 256 images, an acceleration by a factor of at least two in the calculation of their cross correlations is guaranteed using an ordinary PC or a laptop. As for smaller sized templates, tenfold accelerations may be achieved.