Disconnected Skeleton: Shape at Its Absolute Scale

Cagri Aslan, Aykut Erdem, Erkut Erdem, Sibel Tari

TL;DR

This paper introduces a novel "disconnected skeleton" representation for 2D shape recognition that prioritizes stability over connectivity. By applying excessive regularization via a linear diffusion equation, the authors extract only the most prominent skeletal branches, creating a robust, point-set-like description that excels at matching shapes despite noise, deformations, or articulations.

What Problem Does This Paper Address?

In computer vision, "skeletons" (or medial axes) are a classic way to represent the structure of a shape. However, traditional skeletons are notoriously "jittery." A tiny bump on the boundary of a shape can sprout a massive, complex skeletal branch, making it very difficult to compare two similar objects if their boundaries aren't perfectly smooth.

Researchers usually try to fix this by "pruning" the skeleton—cutting off the small, noisy branches. But pruning is often arbitrary and can still leave behind unstable structures. The authors of this paper ask: What if we stop trying to keep the skeleton connected and instead only compute the parts we are absolutely sure about?

Methods

The core of the approach is a shift from local geometry to global regularization.

  1. Linear Diffusion at Absolute Scale: Instead of using the standard distance transform (which is sensitive to noise), the authors use a linear diffusion equation (essentially the heat equation). They evolve the shape boundary until it reaches an "absolute scale" ($\sigma^*$). At this scale, secondary details have melted away, leaving only the "ribbon-like" core of the shape.
  2. Disconnectedness as a Feature: Because they use such heavy regularization, the skeletal branches often don't meet in the middle. They remain disconnected. Each branch represents a stable "primitive" of the shape (like a limb or a torso).
  3. Global and Semi-Local Frames: Traditional skeletons use local coordinate frames that change at every point. This paper proposes a global Euclidean frame based on "major branches" to handle scale and rotation. To handle articulation (like an arm moving), they introduce a "semi-local" frame that describes the pose of a part relative to the body center.
  4. Matching Algorithm: Shapes are compared using a branch-and-bound algorithm. Each skeletal branch is treated as a primitive with attributes like length, location (in polar coordinates), and "sign" (whether it represents a protrusion or an indentation).

Datasets

The authors evaluated their method on a diverse 2D shape database consisting of 180 shapes across 30 categories (including animals, tools, and symbols). This dataset is designed to test sensitivity to orientation, scale, articulation, and boundary noise. They specifically highlight results on "cat," "dinosaur," and "hand" shapes to demonstrate how the system handles non-rigid transformations.

Key Insights and Ideas

  • Stability over Connectivity: The most radical idea here is that a skeleton doesn't need to be a connected graph to be useful. By letting the skeleton break apart, you actually gain a more stable "point set" representation that isn't distracted by topological noise.
  • The "Absolute Scale": The authors argue there is a natural scale for every shape where its description is as simple as possible without losing its identity. Finding this scale via diffusion prevents the "saddle point instability" found in previous PDE-based skeletonization methods.
  • Handling the "6 vs 9" Problem: Most shape descriptors strive for total invariance. However, the authors point out that sometimes you want to be sensitive to orientation (to tell a '6' from a '9') or articulation. Their framework allows for "tunable" sensitivity by choosing which coordinate frames to use during matching.

Key Results

  • High Accuracy: The system achieved a 98% score on the Bull’s eye test, a standard benchmark for shape retrieval.
  • Precision-Recall: Even at 100% recall, the precision remained around 88%, indicating that the framework is highly effective at returning relevant shapes at the top of query results.
  • Computational Efficiency: Despite using complex PDEs, the method is fast. Computing a description for a standard image takes about 2 seconds on 2005-era hardware (a 2 GHz Pentium 4), making it significantly faster than previous "Edge Strength Function" methods.
  • Robustness: Qualitative results show the system correctly matching a five-fingered hand to a four-fingered hand by recognizing the global spatial organization of the remaining parts.

Limitations and Future Work

  • Closed Boundaries Only: The current mathematical formulation is limited to shapes with closed boundaries. It cannot currently process "open" curves or line drawings.
  • The "Hole" Problem: Shapes with holes (like a donut or a letter 'B') are tricky. The diffusion process tends to shrink holes differently than external boundaries, making it difficult to define a single "center" for the coordinate frame.
  • Complex Symmetries: While the system handles most shapes well, objects with high-order perfect symmetry (like a square or a cross) can create ambiguities in the coordinate frame that require generating multiple alternative descriptions.

The authors are currently working on extending the "disconnected skeleton" logic to handle shapes with holes by replacing simple minima with sequences of parabolic points.

Summary updated

Abstract

We present a new skeletal representation along with a matching framework to address the deformable shape recognition problem. The disconnectedness arises as a result of excessive regularization that we use to describe a shape at an attainably coarse scale. Our motivation is to rely on stable properties the shape instead of inaccurately measured secondary details. The new representation does not suffer from the common instability problems of the traditional connected skeletons, and the matching process gives quite successful results on a diverse database of 2D shapes. An important difference of our approach from the conventional use of skeleton is that we replace the local coordinate frame with a global Euclidean frame supported by additional mechanisms to handle articulations and local boundary deformations. As a result, we can produce descriptions that are sensitive to any combination of changes in scale, position, orientation and articulation, as well as invariant ones.
BibTeX
@article{aslan2008disconnected,
  author = {Cagri Aslan and Aykut Erdem and Erkut Erdem and Sibel Tari},
  title = {{Disconnected Skeleton: Shape at Its Absolute Scale}},
  journal = {IEEE Trans. Pattern Anal. Mach. Intell.},
  year = {2008},
  doi = {10.1109/tpami.2007.70842},
}
Figure