Abstract: This paper presents a generic pre-processor for expediting conventional template matching techniques. Instead of locating the best matched patch in the reference image to a query template via exhaustive search, the proposed algorithm rules out regions with no possible matches with minimum computational efforts. While working on simple patch features, such as mean, variance and gradient, the fast pre-screening is highly discriminative. Its computational efficiency is gained by using a novel octagonal-star-shaped template and the inclusion-exclusion principle to extract and compare patch features. Moreover, it can handle arbitrary rotation and scaling of reference images effectively. Extensive experiments demonstrate that the proposed algorithm greatly reduces the search space while never missing the best match.
Introduction
Template matching is a fundamental task in computer vision, involving the localization of a query template within a larger reference image. However, the search space expands exponentially when accounting for variations in rotation and scale. Traditional exhaustive search methods become computationally prohibitive in these scenarios. While robust feature-based methods like SIFT exist, they remain expensive for high-resolution imagery. This work introduces a high-speed pre-processor designed to rapidly discard non-matching regions, allowing sophisticated algorithms to focus on a small subset of candidate regions.
Methodology
The Two-Stage Framework
The proposed approach employs a two-stage framework to optimize the matching process. In the first stage, a fast screening pre-processor rules out regions that are significantly different from the template based on simple statistical features. The second stage then applies a standard high-accuracy algorithm, such as SIFT or Best-Buddies Similarity (BBS), to the remaining candidate regions to pinpoint the exact match.
Octagonal-Star Template and Integral Images
A key innovation is the use of an octagonal-star-shaped template. While circular templates are ideal for rotation invariance, they are computationally expensive. The octagonal star, formed by the superposition of a square and a diamond, approximates a circle while maintaining straight edges. This geometric property allows for the application of the inclusion-exclusion principle using integral images (summed area tables).
By utilizing integral images, features such as mean, variance, and gradients can be calculated in constant time, significantly reducing the overhead of the screening process.
Feature Representation and Scale Invariance
The screening process relies on discriminative features extracted from the image. These features are often represented through a set of basis components that capture essential image characteristics.
To handle scale variations without exhaustive resizing, the algorithm aggregates features from multiple scales into a quantized feature set. This allows for simultaneous multi-scale checking, based on the assumption that if a large patch matches, its central region should exhibit similar feature characteristics.
Experimental Results
The algorithm was evaluated on the MIT database (13,500 test cases) and the Visual Tracker Benchmark (35 video clips). Key findings include:
- Search Space Reduction: On average, the algorithm prunes approximately 80% of the search regions.
- Computational Speedup: Integration with existing methods yielded significant improvements: SIFT was 50% faster, BBS saw a 55% reduction in time, and FAsT-Match was sped up by 30%.
- Reliability: The screening process maintained a near-perfect recall rate, never missing the best match in 13,500 test cases and preserving over 99.8% of the ground truth area.
- Efficiency: The pre-processing step is extremely lightweight, requiring only 0.1 to 0.4 seconds for 1280x960 images.
Conclusion
The proposed fast screening algorithm provides a robust and efficient pre-processing step for rotation and scale-invariant template matching. By leveraging a novel template shape and optimized integral image calculations, it dramatically reduces the computational burden of subsequent high-precision matching algorithms without sacrificing accuracy. Future work may involve incorporating more complex descriptors or deep-learning-based features to further enhance robustness against extreme viewpoint and lighting changes.
Summary updated