Robust Template Matching Using Multiple-Layered Absent Color Indexing

Guodong Wei, Ying Tian, Shun'ichi Kaneko, Zhengang Jiang

TL;DR

This paper introduces ABC-ML, a novel template matching method that leverages color histograms for robust object detection. By dividing images into multiple layers and focusing on both "apparent" (frequent) and "absent" (infrequent) colors, ABC-ML significantly improves precision and overcomes the common "shift" problem in histogram-based approaches, achieving state-of-the-art results.

What Problem Does This Paper Address?

Traditional template matching algorithms often struggle with variations in images, such as rotation, deformation, scaling, and illumination changes. While color histograms are robust to these variations, they typically lack precise location information, leading to a "shift" problem where the detected object is close but not perfectly centered. This paper aims to bridge this gap by developing a method that combines the robustness of color histograms with the precision needed for accurate localization, even under challenging conditions.

Methods

The core of the proposed method, ABC-ML (Absent Color Indexing with Multiple Layers), involves several key innovations:

  • Total Color Space (TCS): Instead of using the full range of color values (e.g., in CIE L*a*b* space), TCS defines a minimum usable range for histogram bins. This is determined by analyzing the color distribution in a dataset, making the process more efficient and precise.
  • Absent Color Indexing: The method decomposes the original color histogram into two parts: "apparent" color histograms (representing frequent colors) and "absent" color histograms (representing low-frequency or vacant bins). By inverting and analyzing these "absent" colors, the algorithm gains a richer understanding of the image's color distribution, particularly for distinguishing similar objects.
  • Multiple-Layered Structure: To address the precision issue, the template image is divided into three layers. Each layer is processed using the absent color indexing concept. The layers are constructed based on an "isotonic principle," ensuring that the center of the object remains consistent across layers. This layered approach indirectly incorporates positional information, mitigating the shift problem inherent in standard histogram methods.
  • Similarity Measure: The final similarity is a weighted combination of the intersections of both apparent and absent color histograms from each layer.

Datasets

The paper utilizes the following datasets for training and evaluation:

  • Girl2 data from OTB-2015: Used for demonstrating the concept of Total Color Space (TCS).
  • Real-world images and open data: Used for general experiments and comparisons.
  • Skiing data from OTB-2015: A benchmark dataset used for evaluating the performance of ABC-ML against other methods under various challenges like illumination variation, scale variation, deformation, and rotation.

Key Insights and Ideas

  • "Absent" colors are valuable: The paper highlights that low-frequency or vacant bins in color histograms, often discarded, contain crucial information for distinguishing similar objects and improving matching precision.
  • Layering adds positional context: By dividing the image into multiple layers and applying color analysis to each, the method implicitly encodes positional information, a significant limitation of traditional histogram-based approaches.
  • Isotonic principle for stability: The use of the isotonic principle in constructing the layers ensures that the central location of the object is maintained, contributing to robust matching even with deformations.
  • TCS for efficiency: Defining a Total Color Space reduces computational overhead and improves the relevance of histogram bins by focusing on the effective color range.

Key Results

The ABC-ML approach demonstrated state-of-the-art performance across various challenges:

  • Robustness: It showed high discrimination ability and robustness in cases of rotation, deformation, occlusion, scaling, and illumination variation.
  • Precision: Compared to other color histogram-based methods (CI, CCH, ABC), ABC-ML achieved significantly lower location errors (Euclidean distance), with notable improvements in deformation (2.23 pixels vs. 14.31 for ABC) and scale variation (9.21 pixels vs. 11.04 for ABC).
  • Overall Performance: In a comparison with eight other histogram-based and template-based approaches (SSD, NCC, CCH, CI, BBS, QATM, Siam R-CNN, ABC) on the Skiing dataset, ABC-ML achieved the best overall performance, scoring highest in Accuracy, Precision, Recall, and F-Measure (e.g., 0.6431 F-Measure).
  • Speed: The method is computationally efficient, with a computation cost of approximately 0.1865 seconds for matching a 50x50 pixel reference image in a 100x100 pixel scene.

Limitations and Future Work

  • Computational Cost of Layers: While the multiple-layered structure improves precision, the paper acknowledges that increasing the number of layers can increase computational costs.
  • Extension to Other Domains: The authors suggest that the multiple-layered model can be extended to other application domains to provide approximate position information and reduce algorithm complexity.
  • Further Optimization: While efficient, further research could explore optimizations for even faster real-time applications.

Summary updated

Abstract

Color is an essential feature in histogram-based matching. This can be extracted as statistical data during the comparison process. Although the applicability of color features in histogram-based techniques has been proven, position information is lacking during the matching process. We present a conceptually simple and effective method called multiple-layered absent color indexing (ABC-ML) for template matching. Apparent and absent color histograms are obtained from the original color histogram, where the absent colors belong to low-frequency or vacant bins. To determine the color range of compared images, we propose a total color space (TCS) that can determine the operating range of the histogram bins. Furthermore, we invert the absent colors to obtain the properties of these colors using threshold h T . Then, we compute the similarity using the intersection. A multiple-layered structure is proposed against the shift issue in histogram-based approaches. Each layer is constructed using the isotonic principle. Thus, absent color indexing and multiple-layered structure are combined to solve the precision problem. Our experiments on real-world images and open data demonstrated that they have produced state-of-the-art results. Moreover, they retained the histogram merits of robustness in cases of deformation and scaling.
BibTeX
@inproceedings{wei2022robust,
  author = {Guodong Wei and Ying Tian and Shun'ichi Kaneko and Zhengang Jiang},
  title = {{Robust Template Matching Using Multiple-Layered Absent Color Indexing}},
  booktitle = {Sensors},
  year = {2022},
  url = {https://openreview.net/forum?id=o0UTwF4QOw},
}
Figure