Jean-Marie Mirebeau

Albert Cohen, Nira Dyn, Frédéric Hecht et al.

A simple greedy refinement procedure for the generation of data-adapted triangulations is proposed and studied. Given a function of two variables, the algorithm produces a hierarchy of triangulations and piecewise polynomial approximations on these triangulations. The refinement procedure consists in bisecting a triangle T in a direction which is chosen so as to minimize the local approximation error in some prescribed norm between the approximated function and its piecewise polynomial approximation after T is bisected. The hierarchical structure allows us to derive various approximation tools such as multiresolution analysis, wavelet bases, adaptive triangulations based either on greedy or optimal CART trees, as well as a simple encoding of the corresponding triangulations. We give a general proof of convergence in the Lp norm of all these approximations. Numerical tests performed in the case of piecewise linear approximation of functions with analytic expressions or of numerical images illustrate the fact that the refinement procedure generates triangles with an optimal aspect ratio (which is dictated by the local Hessian of of the approximated function in case of C2 functions).

Jean-Marie Mirebeau

We introduce a modification of the Fast Marching Algorithm, which solves the generalized eikonal equation associated to an arbitrary continuous riemannian metric, on a two or three dimensional domain. The algorithm has a logarithmic complexity in the maximum anisotropy ratio of the riemannian metric, which allows to handle extreme anisotropies for a reduced numerical cost. We prove the consistence of the algorithm, and illustrate its efficiency by numerical experiments. The algorithm relies on the computation at each grid point of a special system of coordinates: a reduced basis of the cartesian grid, with respect to the symmetric positive definite matrix encoding the desired anisotropy at this point.

Jean-Marie Mirebeau, Albert Cohen

We study the properties of a simple greedy algorithm for the generation of data-adapted anisotropic triangulations. Given a function f, the algorithm produces nested triangulations and corresponding piecewise polynomial approximations of f. The refinement procedure picks the triangle which maximizes the local Lp approximation error, and bisect it in a direction which is chosen so to minimize this error at the next step. We study the approximation error in the Lp norm when the algorithm is applied to C2 functions with piecewise linear approximations. We prove that as the algorithm progresses, the triangles tend to adopt an optimal aspect ratio which is dictated by the local hessian of f. For convex functions, we also prove that the adaptive triangulations satisfy a convergence bound which is known to be asymptotically optimal among all possible triangulations.

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.

Jean-Marie Mirebeau, Albert Cohen

We propose and study quantitative measures of smoothness which are adapted to anisotropic features such as edges in images or shocks in PDE's. These quantities govern the rate of approximation by adaptive finite elements, when no constraint is imposed on the aspect ratio of the triangles, the simplest examples of such quantities are based on the determinant of the hessian of the function to be approximated. Since they are not semi-norms, these quantities cannot be used to define linear function spaces. We show that they can be well defined by mollification when the function to be approximated has jump discontinuities along piecewise smooth curves. This motivates for using them in image processing as an alternative to the frequently used record variation semi-norm which does not account for the geometric smoothness of the edges.

Jean-Marie Mirebeau

Given a function f defined on a bidimensional bounded domain and a positive integer N, we study the properties of the triangulation that minimizes the distance between f and its interpolation on the associated finite element space, over all triangulations of at most N elements. The error is studied in the Lp norm and we consider Lagrange finite elements of arbitrary polynomial degree m-1. We establish sharp asymptotic error estimates as N tends to infinity when the optimal anisotropic triangulation is used, recovering the earlier results on piecewise linear interpolation, an improving the results on higher degree interpolation. These estimates involve invariant polynomials applied to the m-th order derivatives of f. In addition, our analysis also provides with practical strategies for designing meshes such that the interpolation error satisfies the optimal estimate up to a fixed multiplicative constant. We partially extend our results to higher dimensions for finite elements on simplicial partitions of a domain of arbitrary dimension. Key words : anisotropic finite elements, adaptive meshes, interpolation, nonlinear approximation.

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

Given a function f defined on a bidimensional bounded domain and a positive integer N, we study the properties of the triangulation that minimizes the distance between f and its interpolation on the associated finite element space, over all triangulations of at most N elements. The error is studied in the W1p norm and we consider Lagrange finite elements of arbitrary polynomial order m-1. We establish sharp asymptotic error estimates as N tends to infinity when the optimal anisotropic triangulation is used. A similar problem has been studied earlier, but with the error measured in the Lp norm. The extension of this analysis to the W1p norm is crucial in order to match more closely the needs of numerical PDE analysis, and it is not straightforward. In particular, the meshes which satisfy the optimal error estimate are characterized by a metric describing the local aspect ratio of each triangle and by a geometric constraint on their maximal angle, a second feature that does not appear for the Lp error norm. Our analysis also provides with practical strategies for designing meshes such that the interpolation error satisfies the optimal estimate up to a fixed multiplicative constant. We discuss the extension of our results to finite elements on simplicial partitions of a domain of arbitrary dimension, and we provide with some numerical illustration in two dimensions.

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?

Yuliya Babenko, Tatyana Leskevich, Jean-Marie Mirebeau

Adaptive approximation (or interpolation) takes into account local variations in the behavior of the given function, adjusts the approximant depending on it, and hence yields the smaller error of approximation. The question of constructing optimal approximating spline for each function proved to be very hard. In fact, no polynomial time algorithm of adaptive spline approximation can be designed and no exact formula for the optimal error of approximation can be given. Therefore, the next natural question would be to study the asymptotic behavior of the error and construct asymptotically optimal sequences of partitions. In this paper we provide sharp asymptotic estimates for the error of interpolation by splines on block partitions in IRd. We consider various projection operators to define the interpolant and provide the analysis of the exact constant in the asymptotics as well as its explicit form in certain cases.

Jean-Marie Mirebeau

We present a family of nonconforming vector finite elements of arbitrary order for problems posed on the space (curl) intersected with H(div) on a bidimensional domain. This result was first stated as a conjecture by Brenner and Sung. In contrast an extension of the same conjecture to three dimensional domains is disproved.

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.

Da Chen, Jean-Marie Mirebeau, Laurent D. Cohen

In this paper, we propose a novel curvature-penalized minimal path model via an orientation-lifted Finsler metric and the Euler elastica curve. The original minimal path model computes the globally minimal geodesic by solving an Eikonal partial differential equation (PDE). Essentially, this first-order model is unable to penalize curvature which is related to the path rigidity property in the classical active contour models. To solve this problem, we present an Eikonal PDE-based Finsler elastica minimal path approach to address the curvature-penalized geodesic energy minimization problem. We were successful at adding the curvature penalization to the classical geodesic energy. The basic idea of this work is to interpret the Euler elastica bending energy via a novel Finsler elastica metric that embeds a curvature penalty. This metric is non-Riemannian, anisotropic and asymmetric, and is defined over an orientation-lifted space by adding to the image domain the orientation as an extra space dimension. Based on this orientation lifting, the proposed minimal path model can benefit from both the curvature and orientation of the paths. Thanks to the fast marching method, the global minimum of the curvature-penalized geodesic energy can be computed efficiently. We introduce two anisotropic image data-driven speed functions that are computed by steerable filters. Based on these orientation-dependent speed functions, we can apply the proposed Finsler elastica minimal path model to the applications of closed contour detection, perceptual grouping and tubular structure extraction. Numerical experiments on both synthetic and real images show that these applications of the proposed model indeed obtain promising results.

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.)