Preimage as karcher mean using diffusion maps: Application to shape and image denoising

Nicolas Thorstensen, Florent Ségonne, Gabriel Peyré, Universite Paris-est, Ecole Des Ponts Paristech2009

TL;DR

This paper introduces a novel method for "pre-image" estimation in Diffusion Maps, a powerful manifold learning technique. By framing the pre-image problem as finding a Karcher mean interpolation, the authors achieve state-of-the-art results in shape and image denoising, particularly for occluded or noisy data.

What Problem Does This Paper Address?

Manifold learning techniques, like Diffusion Maps, are excellent at uncovering the underlying low-dimensional structure of complex data (e.g., shapes, images). They map this data into a "feature space" where analysis is easier. However, a crucial step is often mapping data back from this feature space to the original data space – this is the "pre-image problem." This is particularly challenging when dealing with noisy or incomplete data, as the mapping from the original space to the feature space might not be perfectly reversible. Existing methods for this pre-image problem, often tied to Kernel PCA, struggle with robustness to noise and occlusions. This paper aims to bridge this gap by developing a more robust pre-image estimation method specifically for Diffusion Maps, enabling better denoising and reconstruction of shapes and images.

Methods

The core contribution is the formulation of the pre-image problem as finding a Karcher mean. Diffusion Maps embed data points into a feature space, and the authors propose to model the manifold in this feature space as a set of Karcher means of neighboring points. A Karcher mean is essentially a generalized "average" point on a manifold that minimizes the sum of squared distances to a set of other points.

Here's a breakdown of their approach:

  • Diffusion Maps: They leverage Diffusion Maps to create a non-linear embedding of the data. This embedding captures the intrinsic geometry of the data manifold, making it robust to noise and sampling density variations.
  • Out-of-Sample Extension: They use the Nyström extension method to extend the Diffusion Map embedding to new, unseen data points.
  • Pre-image as Karcher Mean: For a given point in the feature space (which might be a noisy or occluded data point), they identify its m+1 nearest neighbors in the feature space using the diffusion distance. The pre-image is then defined as the Karcher mean of these neighbors, which minimizes the squared distance between the embedded Karcher mean and the target feature point.
  • Projection onto Manifold: To ensure the reconstructed pre-image stays on the learned manifold, they incorporate a projection step. This involves projecting the gradient of the error onto the tangent space of the manifold at the current estimate, effectively guiding the reconstruction process to remain within the learned data structure.

Datasets

  • Synthetic 2D Shapes: Used for demonstrating shape interpolation.
  • Real 2D Images (USPS dataset): Used for image denoising experiments.
  • 3D Shapes (MRI ventricles): Used for shape reconstruction from occluded data.

No new benchmarks were introduced; the paper evaluates against existing datasets and methods.

Key Insights and Ideas

  • Karcher Mean as a Natural Interpolator: Framing the pre-image problem as finding a Karcher mean provides a principled way to interpolate between neighboring data points, especially in the context of Diffusion Maps. This is more robust than simple linear interpolation.
  • Diffusion Distance is Key: The use of the diffusion distance to identify neighbors in the feature space is crucial. It captures the connectivity and intrinsic geometry of the manifold, leading to more meaningful interpolations.
  • Manifold Projection Enhances Robustness: Explicitly projecting the reconstruction back onto the learned manifold significantly improves the quality of the denoised/reconstructed shapes, preventing artifacts and ensuring the output resembles plausible data points.
  • Pre-image Problem is Central to Denoising: The paper highlights that for many manifold learning-based denoising methods, the pre-image estimation is the bottleneck. Solving this effectively unlocks better performance.

Key Results

  • Superior Denoising: The proposed method achieves state-of-the-art results in image denoising on the USPS digit dataset, outperforming several existing Kernel PCA-based methods in terms of PSNR. For example, at a noise level of $\sigma^2=0.85$, their method achieved an average PSNR of 17.32 dB with a training set of 60 samples, compared to 13.87 dB for the best competing method.
  • Robust Reconstruction of Occluded Shapes: The method successfully reconstructs occluded 3D shapes (MRI ventricles), demonstrating its ability to handle significant data corruption. The average reconstruction error was 0.58, significantly better than nearest neighbor (1.81) or mean of neighbors (1.1) approaches.
  • Natural Shape Interpolation: Visual results show that the Karcher mean interpolation produces smooth and natural-looking intermediate shapes when interpolating between two points on the manifold. The projection onto the manifold further refines these interpolations.

Limitations and Future Work

  • Parameter Selection: The paper acknowledges that the dimension of the reduced space (m) needs to be guessed, which is a common issue in manifold learning.
  • Computational Cost: While not explicitly detailed as a limitation, gradient descent for Karcher mean computation can be computationally intensive.
  • Future Work: The authors suggest exploring the application of their projection operator to other tasks like segmentation with shape priors, interpolation, and manifold denoising. They are also interested in investigating the pre-image problem when the training data itself contains heavy noise, and exploring manifolds with complex topologies.

Summary updated

BibTeX
@misc{thorstensen2009preimage,
  author = {Nicolas Thorstensen and Florent Ségonne and Gabriel Peyré and Universite Paris-est and Ecole Des Ponts Paristech},
  title = {{Preimage as karcher mean using diffusion maps: Application to shape and image denoising}},
  year = {2009},
}
Figure