Numerical Approaches for Linear Left-invariant Diffusions on SE(2), their Comparison to Exact Solutions, and their Applications in Retinal Imaging

Jiong Zhang, Remco Duits, Bart M. ter Haar RomenyarXiv 2014 · DOI · OpenReview

Abstract

Left-invariant PDE-evolutions on the roto-translation group $SE(2)$ (and their resolvent equations) have been widely studied in the fields of cortical modeling and image analysis. They include hypo-elliptic diffusion (for contour enhancement) proposed by Citti & Sarti, and Petitot, and they include the direction process (for contour completion) proposed by Mumford. This paper presents a thorough study and comparison of the many numerical approaches, which, remarkably, is missing in the literature. Existing numerical approaches can be classified into 3 categories: Finite difference methods, Fourier based methods (equivalent to $SE(2)$-Fourier methods), and stochastic methods (Monte Carlo simulations). There are also 3 types of exact solutions to the PDE-evolutions that were derived explicitly (in the spatial Fourier domain) in previous works by Duits and van Almsick in 2005. Here we provide an overview of these 3 types of exact solutions and explain how they relate to each of the 3 numerical approaches. We compute relative errors of all numerical approaches to the exact solutions, and the Fourier based methods show us the best performance with smallest relative errors. We also provide an improvement of Mathematica algorithms for evaluating Mathieu-functions, crucial in implementations of the exact solutions. Furthermore, we include an asymptotical analysis of the singularities within the kernels and we propose a probabilistic extension of underlying stochastic processes that overcomes the singular behavior in the origin of time-integrated kernels. Finally, we show retinal imaging applications of combining left-invariant PDE-evolutions with invertible orientation scores.

Introduction

In computer vision and medical imaging, processing complex structures like crossing blood vessels or interrupted contours remains a significant challenge. A powerful mathematical framework for addressing this involves "lifting" a 2D image into a 3D "orientation score" by adding an extra dimension for local edge orientation. This approach is biologically inspired by the primary visual cortex (V1), where orientation columns are organized into hypercolumns that respond to specific edge orientations in the visual field.

Biological motivation: Orientation columns in the visual cortex V1 map to curves in the image plane.

By processing images in this lifted space, we can disentangle crossing structures that would otherwise be ambiguous in a standard 2D representation. This requires solving partial differential equations (PDEs) on the Euclidean motion group $SE(2)$, specifically for tasks like contour enhancement (denoising) and contour completion (filling gaps).

Methodology: Lifting and Diffusion on SE(2)

The core of the proposed framework is the transformation of a 2D image $f(x, y)$ into an orientation score $U_f(x, y, \theta)$ using an invertible wavelet-like transform $\mathcal{W}_\psi$. This "lifting" process separates overlapping structures based on their local orientation.

Lifting a 2D image into a 3D orientation score on $SE(2)$ to disentangle crossing structures.

To process these scores, the authors evaluate three primary numerical approaches:

  1. Finite Difference (FD): Employs a grid-based stencil. To maintain rotation invariance, 2nd-order B-spline interpolation is used, which is necessary to preserve the left-invariant property of the operators on $SE(2)$.
  2. Fourier-Based Techniques (FBT): These methods transform the PDE into the frequency domain. This results in a 5-band matrix system that can be inverted efficiently, directly relating to the spectral decomposition of exact solutions.
  3. Stochastic (Monte Carlo): Approximates the diffusion kernel by simulating thousands of "random walks" of particles that move and rotate simultaneously.

Benchmarking Against Exact Solutions

A major contribution of this work is the first rigorous benchmark of these numerical methods against exact analytical solutions. These exact solutions, derived in the spatial Fourier domain, involve complex non-periodic Mathieu functions.

The authors identified a significant bottleneck: standard software implementations (like those in Mathematica) for Mathieu functions are often unstable or slow for the parameter ranges required in image processing. To overcome this, they developed a custom "Own Mathieu Implementation" (OMI) that is 30 times faster and significantly more robust than standard tools.

Key Results

  • Accuracy: Fourier-based methods (FBT) emerged as the most accurate, achieving relative errors often below 1%. In contrast, FD methods typically showed a ~5% error offset, primarily due to the blurring introduced by B-spline interpolation required for rotation invariance.
  • Computational Efficiency: The OMI algorithm reduced the computation time for a standard kernel from approximately 4000 seconds to 137 seconds.

Addressing Kernel Singularities

Standard mathematical kernels for these diffusion processes often exhibit "singularities" (infinite spikes) at the origin, which can be problematic for practical applications like filling in gaps. The authors propose a "Gamma-distribution" fix: instead of integrating the diffusion over a simple exponential time distribution, they use a Gamma distribution. This effectively "spreads the ink," eliminating the singularity and making the kernels more effective for contour completion.

Applications in Retinal Imaging

The practical utility of these left-invariant PDE-evolutions was demonstrated on high-resolution optical images of the human retina. By applying $SE(2)$ diffusion to orientation scores, the authors were able to enhance the vascular tree while preserving critical crossing and bifurcation points. This enhancement significantly improved the performance of vessel tracking algorithms, which often fail when vessels overlap or branch complexly.

Conclusion

This study establishes Fourier-based techniques as the gold standard for solving linear left-invariant diffusions on $SE(2)$. While finite difference methods remain essential for non-linear, adaptive diffusions, FBT offers superior accuracy and speed for linear enhancement and completion tasks. Future work will explore scaling these methods to 3D medical imaging ($SE(3)$), such as Diffusion-Weighted MRI, where disentangling crossing fibers is a critical problem.

Summary updated

Abstract

Left-invariant PDE-evolutions on the roto-translation group $SE(2)$ (and their resolvent equations) have been widely studied in the fields of cortical modeling and image analysis. They include hypo-elliptic diffusion (for contour enhancement) proposed by Citti & Sarti, and Petitot, and they include the direction process (for contour completion) proposed by Mumford. This paper presents a thorough study and comparison of the many numerical approaches, which, remarkably, is missing in the literature. Existing numerical approaches can be classified into 3 categories: Finite difference methods, Fourier based methods (equivalent to $SE(2)$-Fourier methods), and stochastic methods (Monte Carlo simulations). There are also 3 types of exact solutions to the PDE-evolutions that were derived explicitly (in the spatial Fourier domain) in previous works by Duits and van Almsick in 2005. Here we provide an overview of these 3 types of exact solutions and explain how they relate to each of the 3 numerical approaches. We compute relative errors of all numerical approaches to the exact solutions, and the Fourier based methods show us the best performance with smallest relative errors. We also provide an improvement of Mathematica algorithms for evaluating Mathieu-functions, crucial in implementations of the exact solutions. Furthermore, we include an asymptotical analysis of the singularities within the kernels and we propose a probabilistic extension of underlying stochastic processes that overcomes the singular behavior in the origin of time-integrated kernels. Finally, we show retinal imaging applications of combining left-invariant PDE-evolutions with invertible orientation scores.
BibTeX
@misc{zhang2014numerical,
  author = {Jiong Zhang and Remco Duits and Bart M. ter Haar Romeny},
  title = {{Numerical Approaches for Linear Left-invariant Diffusions on SE(2), their Comparison to Exact Solutions, and their Applications in Retinal Imaging}},
  year = {2014},
  eprint = {1403.3320},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1403.3320},
}
Figure