Jean‐Marie Mirebeau

Remco Duits, Stephan P. L. Meesters, Jean-Marie Mirebeau et al.

We present a PDE-based approach for finding optimal paths for the Reeds-Shepp car. In our model we minimize a (data-driven) functional involving both curvature and length penalization, with several generalizations. Our approach encompasses the two and three dimensional variants of this model, state dependent costs, and moreover, the possibility of removing the reverse gear of the vehicle. We prove both global and local controllability results of the models. Via eikonal equations on the manifold $\mathbb{R}^d \times \mathbb{S}^{d-1}$ we compute distance maps w.r.t. highly anisotropic Finsler metrics, which approximate the singular (quasi)-distances underlying the model. This is achieved using a Fast-Marching (FM) method, building on work by Mirebeau. The FM method is based on specific discretization stencils which are adapted to the preferred directions of the Finsler metric and obey a generalized acuteness property. The shortest paths can be found with a gradient descent method on the distance map, which we formalize in a theorem. We justify the use of our approximating metrics by proving convergence results. Our curve optimization model in $\mathbb{R}^{d} \times \mathbb{S}^{d-1}$ with data-driven cost allows to extract complex tubular structures from medical images, e.g. crossings, and incomplete data due to occlusions or low contrast. Our work extends the results of Sanguinetti et al. on numerical sub-Riemannian eikonal equations and the Reeds-Shepp Car to 3D, with comparisons to exact solutions by Duits et al. Numerical experiments show the high potential of our method in two applications: vessel tracking in retinal images for the case $d=2$, and brain connectivity measures from diffusion weighted MRI-data for the case $d=3$, extending the work of Bekkers et al. We demonstrate how the new model without reverse gear better handles bifurcations.

Jean-David Benamou, Francis Collino, Jean-Marie Mirebeau

We introduce a novel discretization of the Monge-Ampere operator, simultaneously consistent and degenerate elliptic, hence accurate and robust in applications. These properties are achieved by exploiting the arithmetic structure of the discrete domain, assumed to be a two dimensional cartesian grid. The construction of our scheme is simple, but its analysis relies on original tools seldom encountered in numerical analysis, such as the geometry of two dimensional lattices, and an arithmetic structure called the Stern-Brocot tree. Numerical experiments illustrate the method's efficiency.

Jean-Marie Mirebeau

We study the discretization of the Escape Time problem: find the length of the shortest path joining an arbitrary point of a domain, to the domain's boundary. Path length is measured locally via a Finsler metric, potentially asymmetric and strongly anisotropic. This Optimal Control problem can be reformulated as a static Hamilton Jacobi, or Anisotropic Eikonal, Partial Differential Equation, as well as a front propagation model. It has numerous applications, ranging from motion planning to image segmentation. We introduce a new algorithm, Fast Marching using Anisotropic Stencil Refinement (FM-ASR), which addresses this problem on a two dimensional domain discretized on a cartesian grid. The local stencils used in our discretization are produced by arithmetic means. The complexity of the FM-ASR, in an average sense over all grid orientations, only depends (poly-)logarithmically on the anisotropy ratio of the metric, while most alternative approaches have a polynomial dependence. Numerical experiments show, in several occasions, that the accuracy/complexity compromise is improved by an order of magnitude or more.

Jérôme Fehrenbach, Jean-Marie Mirebeau

We introduce a new discretization scheme for Anisotropic Diffusion, AD-LBR, on two and three dimensional cartesian grids. The main features of this scheme is that it is non-negative, and has a stencil cardinality bounded by 6 in 2D, by 14 in 3D, despite allowing diffusion tensors of arbitrary anisotropy. Our scheme also has good spectral properties, which permits larger time steps and avoids e.g. chessboard artifacts. AD-LBR relies on Lattice Basis Reduction, a tool from discrete mathematics which has recently shown its relevance for the discretization on grids of strongly anisotropic Partial Differential Equations. We prove that AD-LBR is in 2D asymptotically equivalent to a finite element discretization on an anisotropic Delaunay triangulation, a procedure more involved and computationally expensive. Our scheme thus benefits from the theoretical guarantees of this procedure, for a fraction of its cost. Numerical experiments in 2D and 3D illustrate our results.

Jérémy Bleyer, Guillaume Carlier, Vincent Duval et al.

Upper bound limit analysis allows one to evaluate directly the ultimate load of structures without performing a cumbersome incremental analysis. In order to numerically apply this method to thin plates in bending, several authors have proposed to use various finite elements discretizations. We provide in this paper a mathematical analysis which ensures the convergence of the finite element method, even with finite elements with discontinuous derivatives such as the quadratic 6 node Lagrange triangles and the cubic Hermite triangles. More precisely, we prove the $Γ$-convergence of the discretized problems towards the continuous limit analysis problem. Numerical results illustrate the relevance of this analysis for the yield design of both homogeneous and non-homogeneous materials.

Jean-Marie Mirebeau

We introduce a monotone (degenerate elliptic) discretization of the Monge-Ampere operator, on domains discretized on cartesian grids. The scheme is consistent provided the solution hessian condition number is uniformly bounded. Our approach enjoys the simplicity of the Wide Stencil method, but significantly improves its accuracy using ideas from discretizations of optimal transport based on power diagrams. We establish the global convergence of a damped Newton solver for the discrete system of equations. Numerical experiments, in three dimensions, illustrate the scheme efficiency.

Jean-Marie Mirebeau

We address the discretization of optimization problems posed on the cone of convex functions, motivated in particular by the principal agent problem in economics, which models the impact of monopoly on product quality. Consider a two dimensional domain, sampled on a grid of N points. We show that the cone of restrictions to the grid of convex functions is in general characterized by N^2 linear inequalities; a direct computational use of this description therefore has a prohibitive complexity. We thus introduce a hierarchy of sub-cones of discrete convex functions, associated to stencils which can be adaptively, locally, and anisotropically refined. Numerical experiments optimize the accuracy/complexity tradeoff through the use of a-posteriori stencil refinement strategies.

Albert Cohen, Jean-Marie Mirebeau

We survey the main results of approximation theory for adaptive piecewise polynomial functions. In such methods, the partition on which the piecewise polynomial approximation is defined is not fixed in advance, but adapted to the given function f which is approximated. We focus our discussion on (i) the properties that describe an optimal partition for f, (ii) the smoothness properties of f that govern the rate of convergence of the approximation in the Lp-norms, and (iii) fast refinement algorithms that generate near optimal partitions. While these results constitute a fairly established theory in the univariate case and in the multivariate case when dealing with elements of isotropic shape, the approximation theory for adaptive and anisotropic elements is still building up. We put a particular emphasis on some recent results obtained in this direction.

Jean-Marie Mirebeau

Mesh adaption procedures for finite element approximation allows one to adapt the resolution, by local refinement in the regions of strong variation of the function of interest. This procedure plays a key role in numerous applications of scientific computing. The use of anisotropic triangles allows to improve the efficiency of the procedure by introducing long and thin triangles that fit in particular the directions of the possible curves of discontinuity. Given a norm X of interest and a function f to be approximated, we formulate the problem of optimal mesh adaptation, as minimizing the approximation error over all (possibly anisotropic) triangulations of prescribed cardinality. We address the four following questions related to this problem: I. How does the approximation error behave in the asymptotic regime when the number of triangles N tends to infinity, when f is a smooth function ? II. Which classes of functions govern the rate of decay of the approximation error as N grows, and are in that sense naturally tied to the problem of optimal mesh adaptation? III. Could this optimization problem, which is posed on triangulations of a given cardinality N, be replaced by an equivalent more tractable problem posed on a continuous object? IV. Is it possible to produce a near-optimal sequence of triangulations using a hierarchical refinement procedure?

J. -M. Mirebeau

The fast marching algorithm, and its variants, solves numerically the generalized eikonal equation associated to an underlying riemannian metric. A major challenge for these algorithms is the non-isotropy of the riemannian metric. Applications of the eikonal equation to image processing often involve pronounced anisotropies, which motivated the design of new algorithms. A recently introduced variant of the fast marching algorithm addresses the problem of large anisotropies using an algebraic tool named lattice basis reduction. The numerical complexity of this algorithm is insensitive to anisotropy, under weak assumptions. We establish in this paper, in the simplified setting of a constant riemannian metric, that the accuracy of this algorithm is also extremely robust to anisotropy : in an average sense, it is independent of the anisotropy ratio. We also extend this algorithm to higher dimension.

Jean-Marie Mirebeau

Mesh adaptation for finite element approximation is a procedure used in numerous applications. The use of thin and long anisotropic triangles improves the efficiency of the procedure. When piecewise linear finite elements are used, the aspect ratio for mesh adaptation is generally dictated by the absolute value of the (estimated) hessian matrix of the approximated function. We give in this paper the corresponding aspect ratio for piecewise quadratic finite elements.

Chong Di, Shuwang Zhou, Da Chen et al.

The computation of minimal paths for the applications in tracking tubular structures such as blood vessels and roads is challenged by complex morphologies and environmental variations. Existing approaches can be roughly categorized into two research lines: the point-wise based models and the segment-wise based models. Although segment-wise approaches have obtained promising results in many scenarios, they often suffer from computational inefficiency and heavily rely on a prescribed prior to fit the target elongated shapes. We propose a novel framework that casts segment-wise tracking as a Markov Decision Process (MDP), enabling a reinforcement learning approach. Our method leverages Q-Learning to dynamically explore a graph of segments, computing edge weights on-demand and adaptively expanding the search space. This strategy avoids the high cost of a pre-computed graph and proves robust to incomplete initial information. Experimental reuslts on typical tubular structure datasets demonstrate that our method significantly outperforms state-of-the-art point-wise and segment-wise approaches. The proposed method effectively handles complex topologies and maintains global path coherence without depending on extensive prior structural knowledge.

Da Chen, Jean-Marie Mirebeau, Minglei Shu et al.

The minimal geodesic models based on the Eikonal equations are capable of finding suitable solutions in various image segmentation scenarios. Existing geodesic-based segmentation approaches usually exploit image features in conjunction with geometric regularization terms, such as Euclidean curve length or curvature-penalized length, for computing geodesic curves. In this paper, we take into account a more complicated problem: finding curvature-penalized geodesic paths with a convexity shape prior. We establish new geodesic models relying on the strategy of orientation-lifting, by which a planar curve can be mapped to an high-dimensional orientation-dependent space. The convexity shape prior serves as a constraint for the construction of local geodesic metrics encoding a particular curvature constraint. Then the geodesic distances and the corresponding closed geodesic paths in the orientation-lifted space can be efficiently computed through state-of-the-art Hamiltonian fast marching method. In addition, we apply the proposed geodesic models to the active contours, leading to efficient interactive image segmentation algorithms that preserve the advantages of convexity shape prior and curvature penalization.

Da Chen, Jack Spencer, Jean-Marie Mirebeau et al.

The Voronoi diagram-based dual-front active contour models are known as a powerful and efficient way for addressing the image segmentation and domain partitioning problems. In the basic formulation of the dual-front models, the evolving contours can be considered as the interfaces of adjacent Voronoi regions. Among these dual-front models, a crucial ingredient is regarded as the geodesic metrics by which the geodesic distances and the corresponding Voronoi diagram can be estimated. In this paper, we introduce a type of asymmetric quadratic metrics dual-front model. The metrics considered are built by the integration of the image features and a vector field derived from the evolving contours. The use of the asymmetry enhancement can reduce the risk of contour shortcut or leakage problems especially when the initial contours are far away from the target boundaries or the images have complicated intensity distributions. Moreover, the proposed dual-front model can be applied for image segmentation in conjunction with various region-based homogeneity terms. The numerical experiments on both synthetic and real images show that the proposed dual-front model indeed achieves encouraging results.

Da Chen, Jean-Marie Mirebeau, Huazhong Shu et al.

The geodesic model based on the eikonal partial differential equation (PDE) has served as a fundamental tool for the applications of image segmentation and boundary detection in the past two decades. However, the existing approaches commonly only exploit the image edge-based features for computing minimal geodesic paths, potentially limiting their performance in complicated segmentation situations. In this paper, we introduce a new variational image segmentation model based on the minimal geodesic path framework and the eikonal PDE, where the region-based appearance term that defines then regional homogeneity features can be taken into account for estimating the associated minimal geodesic paths. This is done by constructing a Randers geodesic metric interpretation of the region-based active contour energy functional. As a result, the minimization of the active contour energy functional is transformed into finding the solution to the Randers eikonal PDE. We also suggest a practical interactive image segmentation strategy, where the target boundary can be delineated by the concatenation of several piecewise geodesic paths. We invoke the Finsler variant of the fast marching method to estimate the geodesic distance map, yielding an efficient implementation of the proposed region-based Randers geodesic model for image segmentation. Experimental results on both synthetic and real images exhibit that our model indeed achieves encouraging segmentation performance.

Gonzalo Sanguinetti, Erik Bekkers, Remco Duits et al.

We propose a Fast Marching based implementation for computing sub-Riemanninan (SR) geodesics in the roto-translation group SE(2), with a metric depending on a cost induced by the image data. The key ingredient is a Riemannian approximation of the SR-metric. Then, a state of the art Fast Marching solver that is able to deal with extreme anisotropies is used to compute a SR-distance map as the solution of a corresponding eikonal equation. Subsequent backtracking on the distance map gives the geodesics. To validate the method, we consider the uniform cost case in which exact formulas for SR-geodesics are known and we show remarkable accuracy of the numerically computed SR-spheres. We also show a dramatic decrease in computational time with respect to a previous PDE-based iterative approach. Regarding image analysis applications, we show the potential of considering these data adaptive geodesics for a fully automated retinal vessel tree segmentation.

Jean-Marie Mirebeau, Jérôme Fehrenbach, Laurent Risser et al.

Anisotropic Non-Linear Diffusion is a powerful image processing technique, which allows to simultaneously remove the noise and enhance sharp features in two or three dimensional images. Anisotropic Diffusion is understood here in the sense of Weickert, meaning that diffusion tensors are anisotropic and reflect the local orientation of image features. This is in contrast with the non-linear diffusion filter of Perona and Malik, which only involves scalar diffusion coefficients, in other words isotropic diffusion tensors. In this paper, we present an anisotropic non-linear diffusion technique we implemented in ITK. This technique is based on a recent adaptive scheme making the diffusion stable and requiring limited numerical resources. (See supplementary data.)

Quentin Mérigot, Jean-Marie Mirebeau

We introduce a numerical method for extracting minimal geodesics along the group of volume preserving maps, equipped with the L2 metric, which as observed by Arnold solve Euler's equations of inviscid incompressible fluids. The method relies on the generalized polar decomposition of Brenier, numerically implemented through semi-discrete optimal transport. It is robust enough to extract non-classical, multi-valued solutions of Euler's equations, for which the flow dimension is higher than the domain dimension, a striking and unavoidable consequence of this model. Our convergence results encompass this generalized model, and our numerical experiments illustrate it for the first time in two space dimensions.