Shape Analysis Using the Edge-Based Laplacian

Furqan Aziz, Richard C. Wilson, Edwin R. HancockSSPR/SPR 2012 · OpenReview

Abstract

This paper presents a novel analysis and application of the eigensystem of the edge-based Laplacian of a graph. The advantage of using the edge-based Laplacian over its vertex-based counterpart is that it significantly expands the set of differential operators that can be implemented in the graph domain. We commence by presenting a new mesh characterization based on the adjacency matrix of the mesh that captures both the geometric and topological properties of the shape. We use the edge-based eigenvalues to develop a novel method for defining pose-invariant signatures for non-rigid three-dimensional shapes based on the edge-based heat kernel. To illustrate the utility of our method, we perform numerous experiments applying the method to correspondence matching and classifying non-rigid three-dimensional shapes represented in terms of meshes.

Introduction

In 3D computer vision, analyzing non-rigid shapes—such as a human body in various poses—remains a significant challenge. Traditional methods for point matching and shape classification often rely on the Laplace-Beltrami operator, typically defined over the vertices of a mesh. However, vertex-based approaches struggle to perfectly replicate continuous physical properties, such as the finite speed of wave propagation. This paper proposes a shift in focus from vertices to edges, utilizing an edge-based Laplacian to bridge the gap between discrete graph theory and continuous mathematical analysis, resulting in more stable and informative shape characterizations.

Methodology

The proposed framework redefines shape descriptors through a three-step process:

  1. Geometric Adjacency Matrix: A symmetric adjacency matrix is constructed using the "cotangent formula," which calculates weights based on the angles opposite an edge. These weights are normalized by the area of surrounding triangles to minimize dependence on the specific triangulation of the mesh.
  2. Edge-Based Eigensystem: By deriving eigenvalues and eigenfunctions for the edge-based Laplacian, the authors expand the available differential operators in the graph domain compared to traditional vertex-based systems.
  3. Heat Kernel Signatures (EHKS & GEHKS):
    • Local EHKS: Captures how heat spreads from a specific point over time, creating a multi-scale vector of local details.
  4. Global GEHKS: Aggregates local signatures into a histogram to encode the broad global structure of the entire shape.
Figure 2: EHKS visualization across various shape classes including ants, bears, and hands, demonstrating the descriptor's ability to capture heat diffusion patterns across diverse topologies.

Experimental Evaluation

The method was evaluated using the SHREC 2010 dataset, which consists of 10 shape classes (e.g., humans, ants, octopuses), each containing 20 different non-rigid poses. The experiments focused on two primary tasks: correspondence matching (identifying the same point across different poses) and shape classification.

Results and Discussion

The Edge-based Heat Kernel Signature (EHKS) demonstrated superior performance and robustness compared to the state-of-the-art Wave Kernel Signature (WKS):

  • Pose Invariance: The edge-based Laplacian allows the graph to behave more like a continuous physical surface. As shown in Figure 3, the EHKS remains consistent across various human poses, allowing for clear segmentation of feature points like the head, hands, and feet in the eigenspace.
  • Correspondence Matching: In human body matching tests, EHKS achieved 8-9 successful matches per trial, outperforming the 6-8 matches achieved by WKS.
  • Classification Accuracy: For shape classification, the global descriptor (GEHKS) achieved a Rand index of 0.8514, significantly higher than the 0.7893 recorded for WKS.
  • Robustness: The method maintained high accuracy even when Gaussian noise was introduced to the 3D models, whereas vertex-based methods showed marked degradation.
Figure 3: (a) EHKS applied to six different human poses showing pose-invariant heat distribution. (b) Successful segmentation of feature points (Head, Hands, Feet) based on the first three eigenvectors.

Conclusion

By shifting the mathematical focus to edges, this research provides a more robust framework for non-rigid 3D shape analysis. While the current implementation assumes closed meshes and involves significant computational complexity for eigensystem calculation, it opens new avenues for applying various partial differential equations (PDEs) to graph-based shape analysis. Future work will explore boundary condition refinements and optimized solvers for real-time applications.

Summary updated

Abstract

This paper presents a novel analysis and application of the eigensystem of the edge-based Laplacian of a graph. The advantage of using the edge-based Laplacian over its vertex-based counterpart is that it significantly expands the set of differential operators that can be implemented in the graph domain. We commence by presenting a new mesh characterization based on the adjacency matrix of the mesh that captures both the geometric and topological properties of the shape. We use the edge-based eigenvalues to develop a novel method for defining pose-invariant signatures for non-rigid three-dimensional shapes based on the edge-based heat kernel. To illustrate the utility of our method, we perform numerous experiments applying the method to correspondence matching and classifying non-rigid three-dimensional shapes represented in terms of meshes.
BibTeX
@inproceedings{aziz2012shape,
  author = {Furqan Aziz and Richard C. Wilson and Edwin R. Hancock},
  title = {{Shape Analysis Using the Edge-Based Laplacian}},
  booktitle = {SSPR/SPR},
  year = {2012},
  url = {https://openreview.net/forum?id=Vx1e5N8Vnc5},
}
Figure