PSEUDOCORRELATION - A FAST, ROBUST, ABSOLUTE, GRAY-LEVEL IMAGE ALIGNMENT ALGORITHM

A new image alignment algorithm-pseudocorrelation-has been developed based on the application of Monte Carlo techniques to the calculation of a cross-correlation integral for grey-scale images. It has many advantages over cross-correlation: it is at least a factor of 10 faster than fast-Fourier-transform-based cross-correlation, and requires 8 times less memory. Its high speed allows for the search space of geometric transformations between images to include magnification and rotation as well as translations without the search time becoming too long. It allows noise to be taken into account, making calculation of a robust, absolute probability of good alignment possible. It is relatively insensitive to differences in quality between images. This article describes the pseudocorrelation algorithm in detail and presents the results of tests of the effects of contrast enhancement, resolution differences, and noise on the algorithm's performance. These tests show that the algorithm is well suited to the task of automated alignment of very low contrast images from video electronic portal imaging devices.