Disconnected Skeleton: Shape at its Absolute Scale

Cagri Aslan, Aykut Erdem, Erkut Erdem, Sibel Tari

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 the stable properties of the shape instead of inaccurately measured secondary details. The new representation does not suffer from the common instability problems of 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 the 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.

Introduction

In the field of computer vision, skeletal representations (or medial axes) serve as a fundamental tool for capturing the structural essence of 2D shapes. However, traditional skeletonization methods are plagued by instability; minor perturbations or noise on a shape's boundary can lead to the emergence of significant, spurious skeletal branches. While pruning techniques are often employed to mitigate this "jitter," they frequently rely on arbitrary thresholds and fail to resolve underlying topological instabilities.

This research introduces a "disconnected skeleton" representation that prioritizes structural stability over connectivity. By intentionally allowing the skeleton to break into discrete branches at a coarse "absolute scale," we derive a robust, point-set-like description that remains invariant to noise while effectively capturing the primary components of a shape.

Methodology

The proposed framework shifts the focus from local geometric properties to global regularization through several key innovations.

Linear Diffusion at Absolute Scale

Rather than utilizing the standard distance transform, which is highly sensitive to boundary noise, we employ a linear diffusion equation (analogous to the heat equation). The shape boundary is evolved until it reaches an "absolute scale" ($σ^*$). At this stage, high-frequency boundary details are suppressed, leaving a stable "ribbon-like" core.

3D surface representation of a shape, likely resulting from the diffusion process used to identify skeletal features.

Disconnectedness as a Feature

The heavy regularization applied during diffusion often results in skeletal branches that do not meet, creating a disconnected representation. Each branch serves as a stable "primitive" representing a major part of the shape, such as a limb or torso. This approach avoids the "saddle point instability" common in previous PDE-based methods.

Illustration of medial axis construction (c) and the morphological operations of erosion and dilation (d).

Global and Semi-Local Coordinate Frames

To overcome the limitations of local coordinate frames, we introduce a global Euclidean frame based on major skeletal branches. This handles global transformations like scale and rotation. For articulated shapes, a "semi-local" frame is utilized to describe the pose of individual parts relative to the shape's center of mass.

Matching Algorithm

Shape comparison is performed using a branch-and-bound algorithm. Skeletal branches are treated as primitives characterized by attributes such as length, polar coordinates, and "sign" (indicating a protrusion or indentation). This allows for tunable sensitivity, enabling the system to distinguish between shapes like '6' and '9' when necessary.

Results

The method was evaluated on a database of 180 shapes across 30 categories, including animals and tools.

  • Accuracy: The system achieved a 98% score on the Bull’s eye test, a standard retrieval benchmark.
  • Precision-Recall: Precision remained at approximately 88% even at 100% recall, demonstrating high effectiveness in returning relevant results.
  • Efficiency: The process is computationally efficient, taking approximately 2 seconds per image on standard hardware, outperforming previous edge-strength function methods.
  • Robustness: Qualitative analysis confirms the system's ability to match shapes despite missing parts (e.g., matching a four-fingered hand to a five-fingered one) by recognizing global spatial organization.

Conclusion

The disconnected skeleton offers a stable and flexible alternative to traditional medial axis representations. By embracing disconnectedness at an absolute scale, the framework achieves high recognition accuracy and robustness to deformation. Future work will focus on extending the formulation to shapes with holes and addressing ambiguities in highly symmetric objects.

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 the stable properties of the shape instead of inaccurately measured secondary details. The new representation does not suffer from the common instability problems of 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 the 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