Fast Eigen Phase Matching

Yusuke Sekikawa, Ikuro Sato, Koichiro Suzuki, Yuichi Yoshida, Kosuke O. HaraJournal of the Japan Society for Precision Engineering 2016 · DOI

Abstract

We propose a fast and robust algorithm for rotation invariant template matching (RITM). By utilizing the circularity of in-plane rotation and decomposing the template matrix using a low-frequency Fourier basis, we significantly accelerate the matching process via Fast Fourier Transforms (FFT). Additionally, we extract phase information from complex gradient images to improve robustness against illumination changes and background clutter. Experiments demonstrate that the matching process becomes approximately 15 times faster than naive implementations while maintaining high accuracy in challenging industrial environments.

Introduction: The Challenge of Rotation Invariant Matching

Template matching—locating a specific "template" image within a larger "query" image—is a cornerstone of industrial automation. However, standard methods struggle when objects are rotated. The "naive" approach involves correlating the query with hundreds of rotated versions of the template, which is computationally exhaustive.

Query image showing a textureless industrial part on a cluttered background.

While feature-based methods like SIFT or SURF are popular for their speed, they often fail on industrial parts that lack distinct textures or sharp corners. Correlation-based methods are more robust for these parts but are typically too slow for real-time applications. This paper introduces "Fast Eigen Phase Matching" to bridge this gap, creating a method as robust as correlation but as fast as feature-based matching.

Methodology

The proposed method achieves efficiency and robustness through two primary innovations:

1. Mathematical Acceleration (Eigen + FFT)

Instead of performing hundreds of individual correlations, the algorithm uses Eigen-decomposition to represent the set of rotated templates using a small number of "basis" images. By recognizing that in-plane rotation has a circular property, the researchers represented the template matrix using a truncated Discrete Fourier Transform (DFT) basis. This allows the replacement of heavy spatial correlations with much faster FFT operations, reducing computational complexity from $O(N \cdot M)$ to $O(M \log_2 M)$.

2. Robust Phase-Based Feature Extraction

Standard intensity-based matching is highly sensitive to lighting variations. The authors convert images into complex gradient images and extract the phase information. Because the direction of an edge (phase) is far more stable than its magnitude under varying illumination, this approach effectively filters out background clutter and lighting shifts that typically cause standard tools to fail.

Results and Performance

The algorithm was evaluated using a dataset of textureless L-shaped industrial parts against backgrounds of increasing complexity (Q-1 to Q-4).

Speed: The proposed method demonstrated a dramatic reduction in operational time. On a GPU, the process took only 35ms, representing a roughly 15x speedup compared to standard Normalized Cross-Correlation (NCC) baselines.

Operational time comparison between NCC and the proposed method.

Accuracy: In the most difficult test cases featuring complex backgrounds and varying light, the proposed method maintained a 99.7% detection rate. In contrast, standard NCC and the popular SURF algorithm dropped to 0% accuracy under the same conditions, proving the necessity of phase-based features for industrial clutter.

Conclusion

Fast Eigen Phase Matching provides a high-performance solution for industrial RITM. By combining the mathematical efficiency of FFT-based Eigen-decomposition with the robustness of phase-based features, the algorithm achieves significant speedups while remaining reliable in cluttered, poorly lit environments. Future work will focus on extending the method to handle scale variations and full 3D pose estimation.

Summary updated

Abstract

We propose a fast and robust algorithm for rotation invariant template matching (RITM). Correlation-based template matching is one of the basic techniques used in computer vision. Among them, RITM, locates a known template in a query irrespective of the template's translation and orientation has been widely put to use in many industrial applications. A naive implementation of RITM requires intensive computation since one needs to correlate query with a set of rotated templates (Template matrix). Eigen template method utilizes the Eigen decomposition of Template matrix to approximate the matching score, thus speeded up the RITM by reducing the number of correlations. We utilize the circularity of inplane rotation and decomposed Template matrix using low-frequency part of the Fourier basis. This decomposition further speeds up the matching process by FFT. We also extract phase information of complex gradient images as a feature, which improve the robustness for illumination changes and background clutter. Experiments revealed that the matching processes becomes 15 times faster compared to the naive implementation of RITM while obtaining robustness for illumination and background fluctuations.
BibTeX
@article{sekikawa2016fast,
  author = {Yusuke Sekikawa and Ikuro Sato and Koichiro Suzuki and Yuichi Yoshida and Kosuke O. Hara},
  title = {{Fast Eigen Phase Matching}},
  journal = {Journal of the Japan Society for Precision Engineering},
  year = {2016},
  doi = {10.2493/jjspe.82.1054},
}
Figure