An Extended Scheme for Shape Matching with Local Descriptors

Kazunori Iwata, Hiroki Yamamoto, Kazushi MimuraIEICE Trans. Information and Systems 2021

Introduction

Shape matching is a cornerstone of computer vision, enabling systems to recognize handwritten characters, identify biological specimens, or categorize objects based on their contours. Most contemporary approaches rely on Local Descriptors (LDs)—mathematical "fingerprints" of individual points on a shape's boundary. By finding the most similar fingerprints between two shapes, an algorithm can establish a correspondence.

However, local descriptors are susceptible to noise. Minor distortions, such as a fold in a leaf or a tremor in a hand-drawn line, can lead to incorrect point mappings. While humans intuitively understand that neighboring points on one shape should map to neighboring points on another, standard algorithms often treat points in isolation to avoid the computational complexity of checking spatial consistency.

Methodology

To address these challenges, researchers from Hiroshima City University proposed an extended matching scheme that incorporates spatial context without sacrificing computational efficiency. Their approach is descriptor-agnostic, meaning it can enhance the performance of various existing LDs like Shape Context or Distance Sets.

The Extended Cost Function

The core of the proposal is a modified cost function that penalizes "unsmooth" mappings. In a standard match, the cost is simply the dissimilarity between the descriptors of point p and its match M(p). The extended scheme adds a penalty term: if the neighbors of p are mapped to points far away from M(p), the total cost increases. This encourages the algorithm to find mappings where local geometry is preserved.

Conceptual diagram of the extended matching scheme where point p and its neighbors are mapped to M(p) and its corresponding neighborhood.

Branch-and-Bound Optimization

Evaluating every possible combination of neighbor matches would lead to a combinatorial explosion. To maintain practical processing speeds, the authors employed a Branch-and-Bound (BB) optimization strategy. The algorithm begins with the most likely matches identified by conventional methods and explores alternative mappings only when they show promise. By "pruning" branches of the search tree that exceed a predefined cost threshold, the system identifies optimal or near-optimal matches efficiently.

The Branch-and-Bound search tree used to optimize point matching while pruning suboptimal paths.

Experimental Evaluation

The scheme was tested on two distinct datasets to evaluate its robustness:

  1. Handwritten Symbol Dataset: 50 clean, simple shapes representing various icons (e.g., gender symbols, wheelchairs).
  2. Quercus Leaf Dataset: 168 images across 10 species of oak leaves. This dataset is significantly more challenging due to natural variations like tears, stains, and folds, as well as high inter-species similarity.

Results and Discussion

The extended scheme consistently outperformed conventional matching across all tested descriptors. On the difficult leaf dataset, the retrieval rate improved from 43.56% to 44.29% when using the "mixture of vMDs" descriptor.

Crucially, the computational overhead was minimal. For the symbol dataset, the processing time increased by less than a second per shape. Beyond quantitative metrics, the scheme provided qualitative improvements, successfully correcting "crossed wire" errors where conventional methods incorrectly mapped points across the shape's topology. This makes the matching process more "explainable," as the resulting point-to-point correspondences align more closely with human geometric intuition.

Conclusion

The proposed extended scheme demonstrates that incorporating local spatial consistency significantly improves shape recognition accuracy. By utilizing Branch-and-Bound optimization, the researchers achieved these gains with negligible impact on speed. Future work will focus on automating the selection of hyperparameters—such as the number of neighbors and the pruning tolerance—to make the system more adaptable to diverse datasets.

Summary updated

BibTeX
@article{iwata2021extended,
  author = {Kazunori Iwata and Hiroki Yamamoto and Kazushi Mimura},
  title = {{An Extended Scheme for Shape Matching with Local Descriptors}},
  journal = {IEICE Trans. Information and Systems},
  year = {2021},
}
Figure