WESD-Weighted Spectral Distance for Measuring Shape Dissimilarity

Ender Konukoglu, Ben Glocker, Antonio Criminisi, Kilian M. Pohl

TL;DR

This paper introduces the Weighted Spectral Distance (WESD), a novel method for quantifying shape differences between objects. WESD leverages the eigenvalues of the Laplace operator, offering a theoretically sound and intuitively meaningful way to measure shape dissimilarity that overcomes limitations of previous spectral methods.

What Problem Does This Paper Address?

Accurately measuring shape dissimilarity is crucial in many fields, from manufacturing and medical imaging to computer vision. While spectral methods, which use eigenvalues of the Laplace operator as shape descriptors, have shown promise, existing distances based on these descriptors suffer from theoretical and practical issues. Specifically, they often struggle with the infinite, divergent nature of eigenvalue sequences, leading to distances that are sensitive to arbitrary parameter choices and don't always behave as true metrics. This paper aims to bridge this gap by proposing a new spectral distance that is theoretically robust, intuitive, and practically useful.

Methods

The core contribution is the Weighted Spectral Distance (WESD), defined as:

$$ \rho(\Omega_\lambda, \Omega_\xi) = \left( \sum_{n=1}^{\infty} \left| \frac{\lambda_n - \xi_n}{\lambda_n \xi_n} \right|^p \right)^{1/p} $$

where $\lambda_n$ and $\xi_n$ are the eigenvalues of the Laplace operator for two shapes $\Omega_\lambda$ and $\Omega_\xi$, and $p$ is a parameter.

The derivation of WESD is rooted in the analysis of the heat-trace, a mathematical tool that links the Laplace spectrum to the intrinsic geometry of an object. This analysis provides WESD with a clear geometric intuition and a more robust mathematical foundation. Key properties proven include:

  • Convergence: WESD converges even though it's defined over the entire infinite sequence of eigenvalues, provided $p > d/2$ (where $d$ is the object's dimension).
  • Pseudometric: WESD satisfies the properties of a pseudometric (non-negativity, identity of indiscernibles, symmetry, and triangle inequality).
  • Approximation: WESD can be accurately approximated using a finite number of eigenvalues, with a controllable truncation error.
  • Normalization: WESD can be mapped to the $[0, 1)$ interval, making it suitable for comparisons and integration with other scores.
  • Multi-scale aspect: The parameter $p$ allows WESD to capture shape differences at different scales, with higher $p$ values emphasizing coarser features and lower $p$ values focusing on finer details.

Datasets

The paper evaluates WESD on several datasets:

  • Synthetic Data:
    • 2D objects (discs and more complex shapes) with random deformations to test shape ordering.
  • 3D objects (humans, centaurs, horses) from the TOSCA dataset for low-dimensional embedding.
  • Real Data:
    • Subcortical brain structures from the LPBA40 dataset for clustering.
  • Left ventricle blood pool from 4D cardiac MRI scans for temporal analysis.
  • SHREC Dataset: A standard benchmark for 3D non-rigid object retrieval.

Key Insights and Ideas

  • Heat-trace as the Intuitive Link: Deriving WESD from the heat-trace provides a strong geometric intuition for why spectral differences matter and how they relate to shape. It's not just an arbitrary mathematical construction.
  • The Power of the Infinite Sum: Unlike previous methods that truncate eigenvalue sequences arbitrarily, WESD's definition over the entire spectrum, coupled with the convergence guarantee, makes it more robust and less sensitive to parameter choices.
  • Multi-scale Control via 'p': The parameter $p$ isn't just a mathematical convenience; it actively controls the scale at which WESD "sees" shape differences. This is a powerful feature for applications where specific scales are of interest.
  • Stability in Embeddings: WESD's stability with respect to the number of modes ($N$) is a significant practical advantage, leading to more reliable low-dimensional representations of shape data.

Key Results

  • Shape Ordering: WESD successfully orders deformed objects based on their visual similarity to a reference, demonstrating its ability to capture meaningful shape variations.
  • Low-Dimensional Embeddings: WESD produces stable and well-separated 2D embeddings of objects, outperforming the PSD (shape-DNA) method, especially in its robustness to the number of modes used.
  • Shape Retrieval: WESD achieves competitive results on the challenging SHREC dataset for 3D object retrieval, comparable to existing methods like PSD.
  • Medical Image Analysis: WESD effectively clusters subcortical brain structures and captures the dynamic changes in heart shape during a cardiac cycle, highlighting its utility in medical applications.

Limitations and Future Work

  • Isospectral Shapes: The paper acknowledges that Laplace spectra are not unique identifiers of shape (isospectral non-congruent objects exist). However, they argue this is a theoretical concern rarely encountered in practice with smooth shapes.
  • Computational Cost: Computing Laplace eigenvalues can be computationally intensive, especially for high-dimensional data or when a large number of modes are required for accurate approximations.
  • Parameter Selection: While WESD offers more stability than PSD, choosing optimal values for $p$ and $N$ still requires consideration based on the specific application and desired scale sensitivity. The paper provides guidance on this trade-off.
  • Future Work: The authors suggest further exploration of WESD's multi-scale properties and its application to a wider range of problems. The paper also hints at potential extensions and combinations with other shape analysis techniques.

Summary updated

Abstract

This paper presents a new distance for measuring shape dissimilarity between objects. Recent publications introduced the use of eigenvalues of the Laplace operator as compact shape descriptors. Here, we revisit the eigenvalues to define a proper distance, called Weighted Spectral Distance (WESD), for quantifying shape dissimilarity. The definition of WESD is derived through analyzing the heat trace. This analysis provides the proposed distance with an intuitive meaning and mathematically links it to the intrinsic geometry of objects. We analyze the resulting distance definition, present and prove its important theoretical properties. Some of these properties include: 1) WESD is defined over the entire sequence of eigenvalues yet it is guaranteed to converge, 2) it is a pseudometric, 3) it is accurately approximated with a finite number of eigenvalues, and 4) it can be mapped to the $([0,1))$ interval. Last, experiments conducted on synthetic and real objects are presented. These experiments highlight the practical benefits of WESD for applications in vision and medical image analysis.
BibTeX
@article{konukoglu2013wesd,
  author = {Ender Konukoglu and Ben Glocker and Antonio Criminisi and Kilian M. Pohl},
  title = {{WESD-Weighted Spectral Distance for Measuring Shape Dissimilarity}},
  journal = {IEEE Trans. Pattern Anal. Mach. Intell.},
  year = {2013},
  doi = {10.1109/tpami.2012.275},
}

Loading related content...

Figure