Introduction
Representing 2D shapes through their skeletal structures, such as the Medial Axis Transform (MAT), provides an intuitive way to capture the "biological" or structural essence of an object. However, these representations are notoriously sensitive to boundary noise. A minor perturbation on a shape's contour can lead to the emergence of significant skeletal branches, known as ligatures, which drastically alter the topology of the skeleton. This instability poses a significant challenge for structural matching algorithms that rely on graph or tree representations. This paper introduces a robust geometric measure for 2D shape similarity that addresses these instabilities by weighting skeletal branches based on their contribution to the shape's boundary.
The Challenge of Skeletal Instability
Traditional shape-matching systems often treat skeletons as shock-trees or graphs. While these structures are descriptive, they lack stability; two perceptually similar shapes might have vastly different skeletal topologies due to small deformations or noise. If an algorithm treats all skeletal branches with equal weight, it may fail to recognize the similarity between a smooth shape and a slightly "bumpy" version of the same shape. The goal is to develop a similarity metric that varies smoothly even when the underlying skeletal structure undergoes abrupt topological changes, such as branch contraction or splicing.
Methodology: A Boundary-Based Skeletal Measure
The authors propose a novel measure defined as the rate of change of a shape's boundary length ($l$) relative to its skeletal length ($s$).
1. The Geometric Measure
For every point along the skeleton, there are at least two corresponding points on the shape's boundary where the maximal inscribed circle is bitangent. The core innovation lies in calculating how much the boundary length increases as one moves a unit distance along the skeleton. This measure effectively quantifies the "importance" of each skeletal segment.
2. Theoretical Foundation: The Hamilton-Jacobi Framework
Rather than being a mere heuristic, this measure is shown to be mathematically proportional to the divergence of the gradient of the distance map. By utilizing a Hamilton-Jacobi (reaction-diffusion) approach to skeletonization, this measure can be extracted as a natural byproduct of the process. This theoretical grounding links global boundary properties to local skeletal attributes.
3. Key Properties
The proposed measure possesses several critical properties for robust shape matching:
- Continuity: As a skeletal branch disappears, the measure approaches zero. This ensures that the similarity metric remains stable during "branch contraction" or "splicing" events where the skeleton's topology flips.
- Bending Invariance: The measure is invariant to bending deformations. When a shape is bent, the boundary length lost on the concave side is compensated by the gain on the convex side, leaving the total measure for that skeletal segment unchanged. This allows the metric to capture the intrinsic "mass" of the shape's components.
4. Matching via Weighted Tree-Edit Distance
Shapes are represented as "shock-trees," where nodes correspond to skeletal segments. The authors employ a tree-edit distance framework where the costs associated with adding, removing, or matching branches are determined by the new geometric measure. This weighting ensures that insignificant branches (ligatures) have minimal impact on the overall similarity score.
Experimental Evaluation
The method was evaluated using several targeted datasets to test specific aspects of its performance:
- Synthetic Deformations: Testing stability by gradually shrinking a protrusion on a rectangle.
- Morphing Sequences: Using sequences like "Sand shark to Swordfish" and "Donkey to Hare" to verify that the similarity measure changes monotonically as one shape transforms into another.
- Tool and Diversity Databases: Discriminating between similar objects (pliers vs. wrenches) and clustering a 25-shape set including animals, hands, and spectacles.
Results and Discussion
The experimental results highlight the effectiveness of the weighted skeletal measure:
- Monotonicity: In morphing experiments, the distance measure increased perfectly monotonically. This demonstrates the measure's ability to distinguish between shapes with identical skeletal topologies but different proportions.
- Clustering Accuracy: The weighted shock-trees significantly outperformed unweighted versions. For instance, unweighted trees often confused objects with similar "bone counts" but different "flesh," such as matching a monkey wrench to a human hand. The new measure correctly prioritized the geometric significance of the branches.
- Stability: The system successfully handled topological transitions without discontinuous jumps in the distance metric, proving its robustness against noise-induced skeletal "shattering."
Conclusion and Future Work
This paper presents a principled approach to stabilizing skeletal shape representations by integrating a boundary-based geometric measure into a tree-matching framework. By linking the measure to the divergence of the distance map, the authors provide a solid theoretical basis for identifying salient shape features.
While the results are promising, the authors note that the method remains sensitive to occlusion, which can drastically alter the skeleton and its boundary correspondence. Future research will focus on improving robustness to occlusion, scaling the evaluation to larger databases, and exploring the impact of curvature-dependent boundary smoothing on the measure. Additionally, there is potential in using this measure to identify small but perceptually salient features that might otherwise be discarded by traditional pruning methods.
Summary updated