TL;DR
This paper introduces a novel algorithm and hardware structure for digital Normalized Cross-Correlation (NCC) by reformulating it in terms of a first-order moment. This approach significantly reduces multiplication complexity and enables efficient hardware implementation using a systolic array, offering a promising solution for real-time signal and image processing applications.
What Problem Does This Paper Address?
Normalized Cross-Correlation (NCC) is a fundamental technique in signal and image processing for tasks like feature matching, motion tracking, and object recognition. However, its high computational complexity, particularly the inner-product calculation, poses a significant challenge for real-time applications and efficient hardware implementation. Existing fast NCC algorithms, such as those based on Fast Fourier Transform (FFT) or decomposition methods, have limitations including being ill-suited for discrete domains, requiring complex multiplications, or lacking generality for arbitrary-length correlations. The paper aims to overcome these limitations by developing a simpler, faster, and more hardware-friendly NCC method.
Methods
The core innovation of this paper lies in transforming the NCC computation. The authors first establish a relationship between the inner-product in cross-correlation and a first-order moment. This allows them to rewrite the NCC formula to primarily involve first-order moments. They then leverage a pre-existing fast algorithm for computing first-order moments, which notably avoids multiplications. This enables a rapid computation of the first-order moment within the new NCC formula, leading to a fast NCC algorithm with reduced complexity.
For hardware implementation, the paper proposes a systolic array structure. This structure is derived from the fast first-order moment algorithm, which is inherently suitable for systolic architectures. The proposed systolic array is designed to be scalable and efficient, further optimized to reduce addition complexity by exploiting an even-odd relationship in the moment computation.
Datasets
Not discussed in the paper. The paper focuses on algorithmic and structural development rather than empirical evaluation on specific datasets.
Key Insights and Ideas
- NCC as a First-Order Moment: The central insight is that the complex inner-product operation in NCC can be elegantly reformulated as a first-order moment. This re-framing is the key to simplifying the computation.
- Multiplication-Free First-Order Moment: The paper builds upon existing work that computes first-order moments using only additions, effectively eliminating multiplications from this critical component of NCC.
- Systolic Architecture for Efficiency: The inherent regularity of the first-order moment computation lends itself perfectly to systolic arrays, allowing for parallel processing and efficient hardware implementation.
- Addition Complexity Optimization: Recognizing that the multiplication-free approach can increase additions, the authors introduce an even-odd relationship to reduce this additive burden.
- Hardware-Friendly Design: The proposed systolic array is designed with simplicity and modularity in mind, aiming for efficient implementation on hardware with fewer multipliers.
Key Results
The paper presents a new algorithm and systolic structure for digital NCC. The proposed algorithm is claimed to perform arbitrary-length NCC with a simple procedure and fewer multiplications compared to existing methods. The systolic array implementation is designed for fast hardware execution.
- Algorithmic Complexity: The paper claims the proposed algorithm reduces multiplication complexity significantly. While the exact quantitative reduction is presented in comparative tables, the core idea is to shift complexity from multiplications to additions, which are generally less costly in hardware.
- Hardware Complexity: The proposed systolic array is designed to be hardware-efficient, utilizing fewer multipliers and offering a competitive adder count and latency compared to existing structures, especially for longer sequences.
- Performance Comparison: Comparisons with direct calculation, FFT-based, DA-based, and a fast NCC algorithm show that the proposed algorithm has lower multiplication numbers than FFT and DA-based methods. Its addition number is also shown to be lower than the fast NCC algorithm for N > 320. The execution time comparison on a mobile phone indicates that the proposed algorithm's execution time is less than FFT-based methods for N < 5500 and comparable to the fast NCC algorithm, without being involved with noise.
Limitations and Future Work
- Addition Complexity: The paper acknowledges that while multiplications are reduced, the algorithm still requires a significant number of additions. Future work is suggested to focus on further reducing these additions.
- Hardware Complexity Dependence: The hardware complexity of the proposed structure is dependent on the parameter L (related to the maximum value in the correlation kernel). While advantageous for typical scenarios where L is relatively small, it's worth noting this dependency.
- General Applicability: The authors suggest that the proposed algorithm and array could also be applied to digital filters and various transforms, indicating potential for broader applications beyond NCC.
Summary updated