A skeletal measure of 2D shape similarity

Andrea Torsello, Edwin R. Hancock

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

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