Flux Graphs for 2D Shape Analysis

Morteza Rezanejad, Kaleem SiddiqiShape Perception in Human and Computer Vision 2013 · DOI · DBLP

Introduction

In computer vision, representing 2D shapes effectively is a fundamental requirement for tasks such as object recognition and classification. One of the most prominent methods for shape representation is the medial axis transform (MAT), or skeletonization. By reducing a shape to its internal skeleton, researchers can capture its topological and geometric essence. However, traditional skeletal representations face three significant challenges: high computational costs for distance transforms, incomplete boundary reconstruction from the skeleton, and overly complex graph structures (such as Shock Graphs) that are sensitive to noise and computationally expensive to match.

This paper introduces Flux Graphs, a novel graph representation that addresses these limitations. By optimizing the underlying distance transform and introducing a new saliency measure based on the "uniqueness of inscribed disks," the proposed method creates a shape descriptor that is significantly less complex than existing alternatives while maintaining comparable performance in object recognition tasks.

Methodology

The construction of Flux Graphs involves a multi-step pipeline designed to improve efficiency and structural clarity.

1. Distance Transform Optimization

Computing a flux-based skeleton requires a distance transform to determine the distance from every internal point to the nearest boundary point. Standard brute-force approaches are computationally intensive. To mitigate this, a spatial hashing technique is implemented. By partitioning the image into a grid, the algorithm restricts its search for boundary points to the closest grid cells, resulting in a dramatic reduction in computation time.

2. High-Fidelity Boundary Reconstruction

Previous skeletal methods often failed to fully reconstruct the original shape's boundary, particularly at skeleton endpoints and junction points. This work improves reconstruction by utilizing a higher-order (4-point) stencil to better estimate tangent vectors. Furthermore, explicit geometric formulas are introduced to reconstruct missing circular boundary arcs at the skeleton's terminal and intersection points, ensuring a more faithful representation of the original silhouette.

3. Skeleton Simplification via Uniqueness of Disks

To eliminate "ligatures"—noisy, unstable branches caused by minor boundary perturbations—a new saliency measure called Uniqueness of Disks is introduced. A skeletal point is deemed salient if its maximal inscribed disk does not significantly overlap with the disks of other skeletal branches. By combining this measure with Average Outward Flux (AOF), the method prunes non-essential branches without losing the core topology of the object.

4. Flux Graph Abstraction

The remaining salient skeletal fragments are merged into a Directed Acyclic Graph (DAG) known as a Flux Graph. The edges in this graph are directed based on the average radii of the inscribed disks, flowing from larger sections of the shape to smaller ones, providing a hierarchical structural description.

Experimental Results

The proposed method was evaluated using a standard benchmark dataset consisting of 1,664 2D view-based silhouettes derived from 13 different 3D graphics models (128 views per object).

Computational and Structural Efficiency

  • Speed: The grid-based spatial hashing optimization reduced average computation time for the distance function from 28.4 seconds to 4.37 seconds, representing an ~85% speedup.
  • Reconstruction Accuracy: The improved boundary reconstruction method increased the coverage of the original shape from a range of 66–88% in previous methods to 97–98%.
  • Graph Complexity: Flux Graphs are significantly more compact than Shock Graphs. On average, they contain ~50% fewer nodes, ~56% fewer edges, and ~26% less depth.

Recognition Performance

Despite the drastic reduction in complexity, Flux Graphs achieved recognition rates nearly on par with Shock Graphs in 2D view-based object recognition tasks. This demonstrates that the simplified graph retains the essential structural information required for robust identification.

Discussion and Future Work

The study highlights that "less is more" in shape representation; a massive portion of a shape's skeleton can be discarded while still allowing for 98-99% reconstruction of the original visual area. The Uniqueness of Disks provides a mathematically sound way to prune noise while preserving topology.

A current limitation is that the evaluation utilized a greedy DAG matcher originally tuned for Shock Graphs. Because this matcher does not fully exploit the specific geometric features of Flux Graphs, the current recognition results likely represent an underestimation of the framework's true potential. Future research will focus on developing custom similarity measures and many-to-many matching algorithms specifically tailored for Flux Graphs, as well as extending the application to complex tasks like pose estimation.

Summary updated

BibTeX
@inproceedings{rezanejad2013flux,
  author = {Morteza Rezanejad and Kaleem Siddiqi and Morteza Rezanejad},
  title = {{Flux Graphs for 2D Shape Analysis}},
  booktitle = {Shape Perception in Human and Computer Vision},
  year = {2013},
  doi = {10.1007/978-1-4471-5195-1\_3},
}
Figure