This paper presents a fast algorithm for normalized cross-correlation (NCC) that allows efficient computation in the transform domain. NCC is widely used for feature matching and tracking, but traditional methods compute it in the spatial domain, which is computationally expensive. The proposed algorithm computes NCC using transform domain convolution, which can be significantly faster, especially for large search windows.
The paper discusses various feature tracking approaches, including SSDA, gradient descent search, snakes, and wavelets. Each method has its own advantages and limitations. NCC is not invariant to scale, rotation, or perspective distortions, but it remains a viable option for many applications due to its simplicity and efficiency.
The key idea of the proposed algorithm is to precompute integrals of the image and its square over the search window. This allows the computation of the numerator and denominator of the NCC formula using precomputed values, significantly reducing the computational cost. The algorithm uses fast Fourier transform (FFT) to compute the cross-correlation in the frequency domain, which is more efficient than direct spatial domain computation.
The paper also discusses the performance of the algorithm in special effects image processing, where accurate tracking of movement and features is essential. The algorithm is compared with other methods, and it is shown that the transform domain approach is faster, especially for larger search windows. The algorithm is also compared with commercial image compositing systems, and it is found to be competitive in terms of performance.
The paper concludes that NCC remains a viable option for many applications, despite its limitations. It is simple to implement, requires no user parameters, and can be used as a component of more sophisticated matching schemes. The proposed algorithm provides a fast and efficient way to compute NCC, making it suitable for real-time applications.This paper presents a fast algorithm for normalized cross-correlation (NCC) that allows efficient computation in the transform domain. NCC is widely used for feature matching and tracking, but traditional methods compute it in the spatial domain, which is computationally expensive. The proposed algorithm computes NCC using transform domain convolution, which can be significantly faster, especially for large search windows.
The paper discusses various feature tracking approaches, including SSDA, gradient descent search, snakes, and wavelets. Each method has its own advantages and limitations. NCC is not invariant to scale, rotation, or perspective distortions, but it remains a viable option for many applications due to its simplicity and efficiency.
The key idea of the proposed algorithm is to precompute integrals of the image and its square over the search window. This allows the computation of the numerator and denominator of the NCC formula using precomputed values, significantly reducing the computational cost. The algorithm uses fast Fourier transform (FFT) to compute the cross-correlation in the frequency domain, which is more efficient than direct spatial domain computation.
The paper also discusses the performance of the algorithm in special effects image processing, where accurate tracking of movement and features is essential. The algorithm is compared with other methods, and it is shown that the transform domain approach is faster, especially for larger search windows. The algorithm is also compared with commercial image compositing systems, and it is found to be competitive in terms of performance.
The paper concludes that NCC remains a viable option for many applications, despite its limitations. It is simple to implement, requires no user parameters, and can be used as a component of more sophisticated matching schemes. The proposed algorithm provides a fast and efficient way to compute NCC, making it suitable for real-time applications.