A Skeletal Measure of 2D Shape Similarity

Andrea Torsello, Edwin R. Hancock

TL;DR

This paper introduces a robust geometric measure for 2D shape similarity based on the rate of change of a shape's boundary length relative to its skeletal length. By integrating this measure into a tree-edit distance framework, the authors create a shape-matching system that remains stable even when noise or small deformations cause the skeleton's topology to flip or "shatter."

What Problem Does This Paper Address?

Skeletal representations, like the Medial Axis Transform, are intuitive ways to describe shapes because they capture the "biological" structure of an object. However, they are notoriously unstable. A tiny bump on a smooth boundary can sprout a large skeletal branch (a "ligature"), radically changing the skeleton's topology.

Traditional structural matching algorithms (which treat skeletons as graphs or trees) struggle with this instability; if two nearly identical shapes have slightly different skeletal branching patterns due to noise, the algorithm might see them as completely different. The authors seek a measure that can "weight" skeletal branches by their actual importance to the shape, allowing for a similarity metric that varies smoothly even when the skeleton's structure undergoes abrupt changes.

Methods

The core innovation is a shape-measure defined as the rate of change of boundary length with distance along the skeleton.

  1. The Measure: For every point on the skeleton, there are at least two corresponding points on the shape's boundary (where the bitangent circle touches). The authors calculate how much the boundary length ($l$) increases as you move a distance ($s$) along the skeleton.
  2. Hamilton-Jacobi Framework: The authors show that this measure is not just a heuristic—it is mathematically proportional to the divergence of the gradient of the distance map. This allows the measure to be extracted "for free" during the skeletonization process if using the Hamilton-Jacobi (reaction-diffusion) approach.
  3. Properties:
    • Continuity: The measure goes to zero as a branch disappears, ensuring smooth transitions during "branch contraction" or "splicing."
    • Bending Invariance: If you bend a shape (like a piece of wire), the boundary length lost on the inside of the curve is gained on the outside, leaving the total measure unchanged.
  4. Matching: The shapes are represented as "shock-trees." The authors use a tree-edit distance algorithm where the cost of adding, removing, or matching branches is determined by this new geometric measure.

Datasets

The paper evaluates the method using several small but targeted datasets:

  • Synthetic Deformations: A rectangle with a protrusion that gradually shrinks to zero to test stability.
  • Morphing Sequences: Two sequences (Sand shark to Swordfish; Donkey to Hare) used to test if the similarity measure changes monotonically as one shape transforms into another.
  • Tool Database: A collection of silhouettes of pliers and wrenches to test discrimination between perceptually similar objects.
  • 25-Shape Diversity Set: A broader set including brushes, spectacles, various animals, and human hands used for clustering experiments.

Key Insights and Ideas

  • Ligature Identification: The authors demonstrate that "ligatures" (branches caused by noise or junctions) naturally have very low values of this measure. This provides a principled way to prune or de-emphasize noise without arbitrary thresholds.
  • The "Aha" Moment on Bending: The proof of bending invariance is a highlight. It shows that the measure captures the intrinsic "mass" of the shape's parts rather than just their spatial arrangement.
  • Divergence as Relevance: Linking the boundary-to-skeleton ratio to the divergence of the distance map provides a solid theoretical bridge between differential geometry and computer vision. It turns a global property (boundary length) into a local skeletal attribute.

Key Results

  • Monotonicity: In the morphing experiments, the distance measure increased perfectly monotonically as the shapes diverged. This proves the measure can disambiguate shapes that have identical skeletal topologies but different proportions.
  • Clustering Accuracy: When clustering the 25-shape database, the weighted shock-trees (using the new measure) significantly outperformed unweighted trees. The unweighted version frequently confused objects with similar "bone counts" but different "flesh" (e.g., matching a monkey wrench to a hand).
  • Stability: The measure successfully handled "splicing" transitions—where skeletal branches merge or split—without the distance metric jumping discontinuously.

Limitations and Future Work

  • Occlusion: The authors acknowledge that, like most skeletal methods, this measure is highly sensitive to occlusion. If part of a shape is hidden, the skeleton (and its boundary correspondence) changes drastically.
  • Scale of Evaluation: While the results are mathematically sound, the experimental validation was performed on a relatively small database (25 shapes). The authors note that large-scale experiments are needed to prove its robustness in massive databases.
  • Future Directions: The authors suggest investigating how curvature-dependent boundary evolution (smoothing) impacts the measure and exploring its use in identifying "small but salient" features that current pruning methods might accidentally discard.

Summary updated

Abstract

This paper presents a geometric measure that can be used to gauge the similarity of 2D shapes by comparing their skeletons. The measure is defined to be the rate of change of boundary length with distance along the skeleton. We demonstrate that this measure varies continuously when the shape undergoes deformations. Moreover, we show that ligatures are associated with low values of the shape-measure. The measure provides a natural way of overcoming a number of problems associated with the structural representation of skeletons. The first of these is that it allows us to distinguish between perceptually distinct shapes whose skeletons are ambiguous. Second, it allows us to distinguish between the main skeletal structure and its ligatures, which may be the result of local shape irregularities or noise. We illustrate how the new shape-measure can be used for the purposes of clustering shock-trees of the same shape class.
BibTeX
@inproceedings{torsello2001skeletal,
  author = {Andrea Torsello and Edwin R. Hancock},
  title = {{A Skeletal Measure of 2D Shape Similarity}},
  booktitle = {IWVF},
  year = {2001},
  doi = {10.1007/3-540-45129-3\_23},
}
Figure