Design Of Fast Template Matching Algorithm Based On Hartley Transform

The full-search zero-mean normalized cross-correlation algorithm (ZNCC) is the most applied image matching algorithms. However, the computational cost of ZNCC is very high. A fast ZNCC algorithm based on fast discrete Hartley transform (DHT) is proposed in this paper. And the performance of this algorithm is studied thoroughly.First, the principle of the algorithm is discussed. The Hartley transform is discussed in detail to provide a mathematical basis for the algorithm. In this algorithm, the cross-correlation surface is computed holistically by separable 2D FHT. The technique of image integration is also integrated into the algorithm to normalize the correlation surface rapidly in spatial domain.Second, the computational cost of this algorithm is analyzed compared with the original ZNCC and the zero-mean normalized cross-correlation algorithm based FFT (FFT_ZNCC). The influence to the computational cost caused by data extending is studied and a feasible solution is proposed. Also, two different quantification strategies using fixed point are brought forward, shifting progressive and reserve of space.Finally, the algorithm is implemented based on the DSP platform. The Experimental results show that the computation efficiency of the proposed algorithm is 10-100 times as high as that of the original ZNCC and about 1.57 times as FFT-based algorithm. Compared to the boundary-based fast ZNCC algorithms, the acceleration ratio of the presented algorithm is independent to the image content, that is, the max response time of the presented algorithm is greatly deduced. Moreover, the complete cross-correlation surface could be acquired with our algorithm, which can't be obtained with the boundary-based algorithms. Therefore, the presented algorithm is more suitable for navigation applications.