Discrete geometry

( Martin Braure de Calignon , Luc Brun , François de Vieilleville , Fabien Feschet , Bertrand Kerautret , J.-O. Lachaud , Xavier Provençal , Anne Vialard )

Discrete geometry or digital topology deals with objects and shapes lying in the digital plane (commonly Z2 for 2D images and Z3 for 3D). The main application domain of discrete geometry is naturally image analysis and pattern recognition, generally following some segmentation algorithm. I am especially interested in how discrete geometry tends toward Euclidean geometry as the resolution gets finer and finer. This is why I have explored several topics in this field:

digital straight segments along digital contours

We have tried to understand how maximal segments (the inextensible DSS of a contour) along the contour of a digital convex set relate to its edges. Interesting relations and bounds have been obtained, some of them are essential to obtain asymptotic properties of digitized shapes.

[ deVieilleville07a , deVieilleville06b , deVieilleville06a , deVieilleville05a ]

digital convexity and word combinatorics

Christoffel words are word combinatoric analogs of digital straight segments. We have shown a new definition of digital convexity which is simply that the Lyndon factorization of a digital contour should be Christoffel words. This is a nice simple characterization of convexity, which induces a very fast algorithm for convexity test.

[ Brlek09a , Brlek08a ]

discrete geometric estimators of length, tangent, curvature, area, normals

Several types of digital straight segments may be defined along digital contours or surfaces. Some of them are interesting for estimating the linear geometry of the digitized shape. We have precisely studied and compared length, tangent and curvature estimators.
For length and tangent estimation, it appears that maximal segments are a sound basis for their estimation. The λ-MST estimator performs a convex combination of the directions of each maximal segment covering the point of interest. It is the best compromise between accuracy, time computation (optimal), maximal error, isotropy, convexity conservation, multgrid convergence. It induces a fine length estimator by simple integration.
For curvature, analyzing the linear geometry of digital contours is not sufficient. We have proposed a global optimization approach, which estimates the real shape that minimizes its squared curvature while being digitized as the object of interest. This approach is not only good for perfect shape digitization but also for noisy or perturbated digital shapes.
We have also worked on the geometry of digital surfaces in arbitrary dimensions. We have proposed a normal, an area, and a tangent estimator that are defined and implemented for nD digital surfaces. Their principle is to combine 2D geometric estimation along specific contours traced on the digital surface.

[ deVieilleville09a , Kerautret09a , deVieilleville08a , Kerautret08b , Kerautret08a , Lachaud07a , Lachaud05a , Lachaud03c ]

multigrid convergence of discrete geometric estimators

A fundamental problem when designing geometric estimator is that they are few objective criteria for assessing and evaluating them. Indeed, there are infinitely many shapes with same digitization. One way to compare two geometric estimators is to compare their accuracy as the resolution gets finer and finer. If an estimator gets more and more accurate as the resolution increases, we say that it is multigrid convergent. The speed of convergence may also be a good argument.
We have studied the multigrid convergence of several discrete geometric quantities and estimators, and also constructs new continuous estimators with convergence properties. Let h be the grid step and let us study the family of convex shapes with C2 boundaries. We obtain

[ deVieilleville09a , deVieilleville08a , Lachaud07a , deVieilleville07a , deVieilleville06b ]

discrete deformable models

One of the interest in studying the multigrid convergence of discrete geometric features is to be able to replace continuous variational problems by discrete counterparts, while knowing how far away we are from the true continuous answer. Resolution by differential equations may then be replaced by combinatorial optimization. We have applied this ideas for designing a digital analog of the classical snake [Kass, Witkin, Terzopoulos87] and also for defining energies in a bottom-up segmentation algorithm using combinatorial pyramids.
Applications to huge biomedical images is currently under investigation (FOGRIMMI project. Mining huge microscopic images. [ Project main page ] )

[ Braure06a , Lachaud01a ]

geometry of noisy digital shapes

For curvature, analyzing the linear geometry of digital contours is not sufficient. We have proposed a global optimization approach, which estimates the real shape that minimizes its squared curvature while being digitized as the object of interest. This approach is not only good for perfect shape digitization but also for noisy or perturbated digital shapes. The idea is to use blurred digital straight segments to obtain possible bounds on the local tangent, and then to find an optimal shape within these bounds. The resulting curvature estimator is extremely robust to noise, while being accurate even at low resolution. This estimator has been successfully applied to corner detection.
Project GeoDIB. Geometry of digital noisy objects. [ Project main page ]

[ Kerautret09a , Kerautret08c , Kerautret08b , Kerautret08a ]

multiresolution analysis of digital shapes

The objective here is to understand shapes with a multi-resolution approach. Although widely spread in signal processing or scale-space community for images, such an approach does not exist yet on digital shapes. For instance, the following questions arise: how geometric primitives are transformed by subsampling ? what is the evolution of maximal segments under a subsampling and how we can relate it to a blurred segments ?
PhD Thesis of Mouhammad Said. Project GeoDIB. Geometry of digital noisy objects. [ Project main page ]

applications to image analysis and pattern recognition

Discrete geometric estimators are very useful in image analysis and pattern recognition application. Discrete deformable models have been used to segment heart ventricles in cardiac MR images. Discrete geometry combined with bottom-up pyramid techniques have been used to extract pyramid of images. Curvature estimators have been used to detect corner along contours. Furthermore, given a shape a priori, we have used to match shapes with their curvature signature in medical images. First results are very promising. Applications to huge biomedical images is currently under investigation (FOGRIMMI project. Mining huge microscopic images. [ Project main page ] )

[ Kerautret08c , Kerautret08b , Braure06a , Lachaud01a ]

deVieilleville09a , Brlek09a , Kerautret09a , Kerautret08c , Kerautret08b , Brlek08a , Kerautret08a , deVieilleville08a , Lachaud07a , deVieilleville07a , deVieilleville06b , Braure06a , deVieilleville06a , deVieilleville05a , Lachaud05a , Lachaud03c , Lachaud01a