Towards Topological-Transformation Robust Shape Comparison: A Sparse Representation Based Manifold Embedding Approach

Longwen Gao, Shuigeng ZhouAAAI 2014 · DOI

Introduction

Comparing non-rigid 3D shapes—such as a human figure in various poses—remains a fundamental challenge in computer vision. Most existing state-of-the-art methods, including Generalized Multidimensional Scaling (GMDS), operate under the assumption of isometry. This assumption posits that the geodesic distance (the shortest path along a surface) between any two points remains constant during deformation. However, real-world objects are often elastic; stretching or compressing a shape alters these geodesic distances, causing traditional algorithms to fail. This paper introduces a novel approach that is robust to such "topological transformations" by leveraging sparse representation (SR) for manifold embedding.

Methodology

The core of the proposed method is the Manifold Neighborhood Representation (MNR). Instead of mapping a 3D shape to a lower-dimensional space (like a 2D plane), the authors embed the shape's manifold into a high-dimensional coefficient space. This approach prioritizes local neighborhood structures over global distances.

Sparse Representation Model

The researchers developed an improved SR model to represent each point on a shape as a weighted combination of its neighbors. Key refinements include:

  • Removal of Constraints: By eliminating the "sum-to-one" constraint common in previous models, the algorithm achieves better resilience against noise and outliers.
  • Distance-Weighted Regularization: A regularization matrix $Q(i)$ is introduced to penalize the selection of distant points, ensuring that only the immediate local structure of the manifold is captured.
  • Efficient Optimization: The high-dimensional problem is solved using the Limited-memory BFGS (L-BFGS) algorithm, which manages the large number of variables efficiently.

Similarity Measurement

To compare two embedded shapes without the high cost of manual point-to-point correspondence, the authors utilize QR decomposition and a greedy bipartite graph matching algorithm. This provides a robust approximation of the distance between two manifolds.

Experimental Evaluation

The method was evaluated using the TOSCA dataset, a standard benchmark for non-rigid shape similarity. The dataset includes various models such as humans (David, Michael, Victoria), cats, dogs, and centaurs in diverse poses.

The TOSCA dataset showcasing various non-rigid shapes and poses used in the study.

The "David" human model served as the reference standard for comparison against other transformed shapes. The experiments focused on three primary scenarios: scaling, stretching, and random topological noise.

Results and Discussion

The proposed MNR approach was compared against GMDS and Elastic Net Constraints (ENC).

  • Robustness to Deformation: While GMDS and ENC showed significant fluctuations in distortion metrics when shapes were scaled or stretched by up to 30%, the proposed method maintained a nearly flat, stable distance metric.
  • Clustering and Classification: The method successfully clustered shapes by category. Even under extreme deformation, "cat" models remained distinct from "dog" or "human" models, whereas competing methods often produced overlapping error curves.
  • Noise Tolerance: In tests where 3,400 points on the manifolds were randomly disturbed, the MNR method remained stable, significantly outperforming the noise-sensitive GMDS.

The results suggest that focusing on local affine subspaces via high-dimensional embedding preserves spatial information more effectively than traditional dimensionality reduction techniques for non-rigid comparison.

Conclusion

This research presents a significant step toward topological-transformation robust shape comparison. By shifting the focus from global geodesic distances to local manifold structures through sparse representation, the method handles elastic deformations that baffle isometric-based approaches. While the computational cost of high-dimensional embedding remains a consideration for very dense meshes, the stability and accuracy of the MNR approach offer a promising framework for complex applications in shape tracking and biomedical imaging.

Summary updated

BibTeX
@inproceedings{gao2014towards,
  author = {Longwen Gao and Shuigeng Zhou},
  title = {{Towards Topological-Transformation Robust Shape Comparison: A Sparse Representation Based Manifold Embedding Approach}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2014},
  doi = {10.1609/aaai.v28i1.9132},
}
Figure