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 Z² for 2D images and Z³ 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

digital convexity

discrete geometric estimators of length, tangent, curvature

discrete deformable models

multigrid convergence of discrete geometric estimators

geometry of noisy digital shapes

multiresolution analysis of digital shapes

applications to image analysis

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

the average length of maximal segments is between O(h^1/3) and O(h^1/3log(h))
the average number of maximal segments is Θ(h^2/3)
the direction of maximal segments tends uniformly toward the real tangent direction at rate O(h^1/3)
on average, it is likely that its tends toward the real tangent direction at rate O(h^2/3) almost everywhere
its integration gives a length estimator with convergence rate O(h^1/3), experimentally O(h^1/3)
the multigrid convergence curvature estimator by circumcircle relies on the hypothesis that maximal segments grows at some Θ(h^1/2). The published proof [Coeurjolly03] is thus no more valid.
we have also improved standard estimators based on polynomial fit and gaussian derivative convolution with computation windows defined by maximal segments, and obtain multigrid convergent estimators.

[ 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

F. de Vieilleville and J.-O. Lachaud. Comparison and improvement of tangent estimators on digital curves. Pattern recognition. 42(8): 1693-1707, 2009.

[BibTeX reference] [paper PDF] [paper PS] [Elsevier ScienceDirect]

Abstract: Many contour-based applications rely on the estimation of the geometry of the shape, such as pattern recognition or classification methods. This paper proposes a comprehensive evaluation on the problem of tangent estimators on digital curves. The methods taken into account use different paradigms : approximation and digital geometry. In the former paradigm, methods based on polynomial fitting, smoothing and filtering are reviewed. In the latter case of digital geometry, we consider two methods that mainly rely on digital straight line recognition [Lachaud06d] and optimization [Kerautret08a]. The comparison takes into account objective criteria such as multi-grid convergence, average error, maximum error, isotropy and length estimation. Experiments underline that adaptive methods based on digital straight line recognition often propose a good trade-off between time and precision and that if precision is to be sought, non-adaptive methods can be easily transformed into adaptive methods to get more accurate estimations.

Keywords:

S. Brlek, J.-O. Lachaud, X. Provençal and C. Reutenauer. Lyndon + Christoffel = digitally convex. Pattern recognition. 42(10): 2239-2246, 2009.

[BibTeX reference] [paper PDF] [Elsevier ScienceDirect]

Abstract: Discrete geometry redefines notions borrowed from Euclidean geometry creating a need for new algorithmical tools. The notion of convexity does not translate trivially, and detecting if a discrete region of the plane is convex requires a deeper analysis. To the many different approaches of digital convexity, we propose the combinatorics on words point of view, unnoticed until recently in the pattern recognition community. In this paper, we provide first a fast optimal algorithm checking digital convexity of polyominoes coded by their contour word. The result is based on linear time algorithms for both computing the Lyndon factorization of the contour word and the recognition of Christoffel factors that are approximations of digital lines. By avoiding arithmetical computations the algorithm is much simpler to implement and much faster in practice. We also consider the convex hull computation and relate previous work in combinatorics on words with the classical Melkman algorithm.

Keywords: Digital convexity; Lyndon words; Christoffel words; Convex hull

B. Kerautret and J.-O. Lachaud. Curvature estimation along noisy digital contours by approximate global optimization. Pattern recognition. 42(10): 2265 - 2278, 2009.

[BibTeX reference] [paper PDF] [paper PS] [Elsevier ScienceDirect]

Abstract: In this paper, we introduce a new curvature estimator along digital contours, which we called global min-curvature (GMC) estimator. As opposed to previous curvature estimators, it considers all the possible shapes that are digitized as this contour, and selects the most probable one with a global optimization approach. The GMC estimator exploits the geometric properties of digital contours by using local bounds on tangent directions defined by the maximal digital straight segments. The estimator is then adapted to noisy contours by replacing maximal segments with maximal blurred digital straight segments. Experiments on perfect and damaged digital contours are performed and in both cases, comparisons with other existing methods are presented.

Keywords: Discrete geometry; Digital contours; Curvature estimation; Feature detection; Robustness to noise

H. G. Nguyen, B. Kerautret, P. Desbarats and J.-O. Lachaud Discrete Contour Extraction from Reference Curvature Function. In Proc. 4th Int. Symp. Advances in Visual Computing (ISVC 2008), Las Vegas, Nevada, volume 5359 of LNCS, pages 1176-1185, dec 2008. Springer.

[BibTeX reference] [paper PDF] [poster PDF zipped] [LNCS]

Abstract: A robust discrete curvature estimator was recently proposed by Kerautret et al. [1]. In this paper, we exploit the precision and stability of this estimator in order to define a contour extraction method for analysing geometric features. We propose to use a reference curvature function for extracting the frontier of a shape in a gray level image. The frontier extraction is done by using both geometric information represented by the reference curvature and gradient information contained in the source image. The application of this work is done in a medical application.

Keywords: contour extraction, shape of reference, global curvature estimator

B. Kerautret, J.-O. Lachaud and B. Naegel Comparison of Discrete Curvature Estimators and Application to Corner Detection. In Proc. 4th Int. Symp. Advances in Visual Computing (ISVC 2008), Las Vegas, Nevada, volume 5358 of LNCS, pages 710-719, dec 2008. Springer.

[BibTeX reference] [paper PDF] [slides PDF] [LNCS]

Abstract: Several curvature estimators along digital contours were proposed in recent works [1,2,3]. These estimators are adapted to non perfect digitization process and can process noisy contours. In this paper, we compare and analyse the performances of these estimators on several types of contours and we measure execution time on both perfect and noisy shapes. In a second part, we evaluate these estimators in the context of corner detection. Finally to evaluate the performance of a non curvature based approach, we compare the results with a morphological corner detector [4].

Keywords: digital geometry, discrete curvature estimator, corner detection, geometry of noisy shapes

S. Brlek and J.-O. Lachaud and X. Provençal. Combinatorial view of digital convexity. In, D. Coeurjolly, I. Sivignon, L. Tougne and F. Dupont, eds, Proc. Int. Conf. Discrete Geometry for Computer Imagery (DGCI'2008), Lyon, France, volume 4992 of LNCS, pages 57-68, april 2008. Springer.

[BibTeX reference] [paper PS gzipped] [Springer]

Abstract:
The notion of convexity translates non-trivially from Euclidean geometry to discrete geometry, and detecting if a discrete region of the plane is convex requires analysis. In this paper we study digital convexity from the combinatorics on words point of view, and provide a fast optimal algorithm checking digital convexity of polyominoes coded by the contour word. The result is based on the Lyndon factorization of the contour word, and the recognition of Christoffel factors that are approximations of digital lines.

Keywords: digital convexity, word combinatorics, Lyndon words, Christoffel words, convexity test

B. Kerautret and J.-O. Lachaud Robust estimation of curvature along digital contours with global optimization. In, D. Coeurjolly, I. Sivignon, L. Tougne and F. Dupont, eds, Proc. Int. Conf. Discrete Geometry for Computer Imagery (DGCI'2008), Lyon, France, volume 4992 of LNCS, pages 334-345, april 2008. Springer.

[BibTeX reference] [paper PS gzipped] [Springer]

Abstract:
In this paper we introduce a new curvature estimator based on global optimisation. This method called Global Min-Curvature exploits the geometric properties of digital contours by using local bounds on tangent directions defined by the maximal digital straight segments. The estimator is adapted to noisy contours by replacing maximal segments with maximal blurred digital straight segments. Experimentations on perfect and damaged digital contours are performed and in both cases, comparisons with other existing methods are presented.

Keywords: discrete geometry, discrete curvature estimator, optimization, curvature minimization, feature extraction

F. de Vieilleville and J.-O. Lachaud. Experimental Comparison of Continuous and Discrete Tangent Estimators Along Digital Curves. In Proc. Int. Workshop on Combinatorial Image Analysis (IWCIA'2008), Buffalo, NY, volume 4958 of LNCS, pages 26-37, march 2008. Springer

[BibTeX reference] [paper PS gzipped] [Springer]

Abstract:
Estimating the geometry of a digital shape or contour is an important task in many image analysis applications. This paper proposes an in-depth experimental comparison between various continuous tangent estimators and a representative digital tangent estimator. The continuous estimators belong to two standard approximation methods: least square fitting and gaussian smoothing. The digital estimator is based on the extraction of maximal digital straight segments [Lachaud05a,Lachaud06d]. The comprehensive comparison takes into account objective criteria such as isotropy and multigrid convergence. Experiments underline that the proposed digital estimator addresses many of the proposed objective criteria and that it is in general as good - if not better - than continuous methods.

Keywords: discrete geometry, discrete geometric estimators, tangent estimators, multigrid convergence

J.-O. Lachaud, A. Vialard and F. de Vieilleville, Fast, Accurate and Convergent Tangent Estimation on Digital Contours. Image and Vision Computing, 25(10): 1572-1587. 2007

[BibTeX reference] [paper PS gzipped] [Elsevier ScienceDirect]

Abstract: This paper presents a new tangent estimator to digitized curves based on digital line recognition. It outperforms existing ones on important criteria while keeping the same computation time: accuracy on smooth or polygonal shapes, isotropy, preservation of inflexion points and convexity, asymptotic behaviour. Its asymptotic convergence (sometimes called multigrid convergence) is proved in the case of convex shapes.

Keywords: Digitized curves, tangent estimator, digital straight segment, multigrid convergence, maximal segments

F. de Vieilleville, J.-O. Lachaud, and F. Feschet. Maximal digital straight segments and convergence of discrete geometric estimators. Journal of Mathematical Imaging and Vision, 27(2): 471-502. 2007.

[BibTeX reference] [paper PS gzipped] [Springer]

Abstract: Discrete geometric estimators approach geometric quantities on digitized shapes without any knowledge of the continuous shape. A classical yet difficult problem is to show that an estimator asymptotically converges toward the true geometric quantity as the resolution increases. We study here, on Convex Digital Polygons, the convergence of local estimators based on Digital Straight Segment (DSS). This problem is closely linked to the asymptotic growth of maximal DSS, for which we show bounds both about their number and sizes. These results not only give better insights about digitized curves but indicate that curvature estimators based on local DSS recognition are not likely to converge. We indeed invalidate a conjecture which was essential in the only known convergence theorem of a discrete curvature estimator. The proof involves results from arithmetic properties of digital lines, digital convexity, combinatorics, continued fractions and random polytopes.

Keywords: digital straight segments, digital convex polygon, maximal segments, discrete curvature estimator, multigrid convergence, asymptotic digital geometry

F. de Vieilleville and J.-O. Lachaud. Convex shapes and convergence speed of discrete tangent estimators. In Proc. Int. Symposium on Visual Computing (ISVC'2006), Lake Tahoe, Nevada, volume 4292 of LNCS, pages 688-697, November 2006. Springer.

[BibTeX reference] [paper PS gzipped] [LNCS]

Abstract: Discrete geometric estimators aim at estimating geometric characteristics of a shape with only its digitization as input data. Such an estimator is multigrid convergent when its estimates tend toward the geometric characteristics of the shape as the digitization step h tends toward 0. This paper studies the multigrid convergence of tangent estimators based on maximal digital straight segment recognition. We show that such estimators are multigrid convergent for some family of convex shapes and that their speed of convergence is on average O(h^2/3). Experiments confirm this result and suggest that the bound is tight.

Keywords: Digitized convex shapes, tangent estimator, digital straight segment, multigrid convergence, convergence speed, maximal segments

M. Braure de Calignon, L. Brun, and J.-O. Lachaud. Combinatorial pyramids and discrete geometry for energy-minimizing segmentation. In Proc. Int. Symposium on Visual Computing (ISVC'2006), Lake Tahoe, Nevada, volume 4292 of LNCS, pages 306-315, November 2006. Springer.

[BibTeX reference] [paper PDF] [LNCS]

Abstract: This paper defines the basis of a new hierarchical framework for segmentation algorithms based on energy minimization schemes. This new framework is based on two formal tools. First, a combinatorial pyramid encode efficiently a hierarchy of partitions. Secondly, discrete geometric estimators measure precisely some important geometric parameters of the regions. These measures combined with photometrical and topological features of the partition allows to design energy terms based on discrete measures. Our segmentation framework exploits these energies to build a pyramid of image partitions with a minimization scheme. Some experiments illustrating our framework are shown and discussed.

Keywords: image segmentation, energy minimization, combinatorial pyramid, digital geometry

F. de Vieilleville and J.-O. Lachaud. Revisiting Digital Straight Segment Recognition. In A. Kuba, K. Palágyi, and L.G. Nyúl, editors, Proc. Int. Conf. Discrete Geometry for Computer Imagery (DGCI'2006), Szeged, Hungary, volume 4245 of LNCS, pages 355-366, October 2006. Springer.

[BibTeX reference] [paper PS gzipped] [LNCS]

Abstract: This paper presents new results about digital straight segments, their recognition and related properties. They come from the study of the arithmetically based recognition algorithm proposed by I. Debled-Rennesson and J.-P. Reveillès in 1995. We indeed exhibit the relations describing the possible changes in the parameters of the digital straight segment under investigation. This description is achieved by considering new parameters on digital segments: instead of their arithmetic description, we examine the parameters related to their combinatoric description. As a result we have a better understanding of their evolution during recognition and analytical formulas to compute them. We also show how this evolution can be projected onto the Stern-Brocot tree. These new relations have interesting consequences on the geometry of digital curves. We show how they can for instance be used to bound the slope difference between consecutive maximal segments.

Keywords: digital straight segment recognition, combinatoric representation of discrete line, Stern-Brocot tree, maximal segments

F. de Vieilleville, J.-O. Lachaud and F. Feschet. Maximal digital straight segments and convergence of discrete geometric estimators. In, Proc. 14th Scandinavian Conference on Image Analysis (SCIA'2005), Joensuu, Finland, volume 3540 of LNCS, pages 988-1003, 2005. Springer.

[BibTeX reference] [paper PS gzipped] [LNCS]

Abstract:
Discrete geometric estimators approach geometric quantities on digitized shapes without any knowledge of the continuous shape. A classical yet difficult problem is to show that an estimator asymptotically converges toward the true geometric quantity as the resolution increases. We study here the convergence of local estimators based on Digital Straight Segment (DSS) recognition. It is closely linked to the asymptotic growth of maximal DSS, for which we show bounds both about their number and sizes. These results not only give better insights about digitized curves but indicate that curvature estimators based on local DSS recognition are not likely to converge. We indeed invalidate an hypothesis which was essential in the only known convergence theorem of a curvature estimator. The proof involves results from arithmetic properties of digital lines, digital convexity, combinatorics, continued fractions and random polytopes.

Keywords:
discrete geometry, digital straight segments, lattice convex polygon, asymptotic convergence, multigrid convergence, digital curvature estimation

J.-O. Lachaud, A. Vialard, and F. de Vieilleville. Analysis and comparative evaluation of discrete tangent estimators. In E. Andrès, G. Damiand, and P. Lienhardt, editors, Proc. Int. Conf. Discrete Geometry for Computer Imagery (DGCI'2005), Poitiers, France, volume 3429 of LNCS, pages 140-151, 2005. Springer.

[BibTeX reference] [paper PS gzipped] [LNCS]

Abstract:
This paper presents a comparative evaluation of tangent estimators based on digital line recognition on digital curves. The comparison is carried out with a comprehensive set of criteria: accuracy on smooth or polygonal shapes, behaviour on convex/concave parts, computation time, isotropy, aymptotic convergence. We further propose a new estimator mixing the qualities of existing ones and outperforming them on most mentioned points.

Keywords:
discrete geometry, discrete tangent estimators, digital straight segments

J.-O. Lachaud and A. Vialard, Geometric measures on arbitrary dimensional digital surfaces. In Proc. Int. Conf. Discrete Geometry for Computer Imagery (DGCI'2003), Napoli, Italy, November 2003, volume 2886 of Lecture Notes in Computer Science, pages 434-443, 2003. Springer.

[BibTeX reference] [paper PS gzipped] [slides PDF] [LNCS]

Abstract:
This paper proposes a set of tools to analyse the geometry of multidimensional digital surfaces. Our approach is based on several works of digital topology and discrete geometry: representation of digital surfaces, bel adjacencies and digital surface tracking, 2D tangent computation by discrete line recognition, 3D normal estimation from slice contours. The main idea is to notice that each surface element is the crossing point of n-1 discrete contours lying on the surface. Each of them can be seen as a 4-connected 2D contour. We combine the directions of the tangents extracted on each of these contours to compute the normal vector at the considered surface element. We then define the surface area from the normal field. The presented geometric estimators have been implemented in a framework able to represent subsets of n-dimensional spaces. As shown by our experiments, this generic implementation is also efficient.

Keywords:
discrete geometry, digital surface, geometric estimators, normal estimation, area estimation

J.-O. Lachaud and A. Vialard. Discrete deformable boundaries for the segmentation of multidimensional images. In C. Arcelli, L. P. Cordella, and G. Sanniti di Baja, editors, Proc. 4th Int. Workshop on Visual Form (IWVF4), Capri, Italy, volume 2059 of Lecture Notes in Computer Science, pages 542-551, 2001. Springer-Verlag, Berlin.

[BibTeX reference] [paper PS gzipped] [poster PS gzipped] [LNCS]

Abstract:
Energy-minimizing techniques are an interesting approach to the segmentation problem. They extract image components by deforming a geometric model according to energy constraints. This paper pro\-poses an extension to these works, which can segment arbitrarily complex image components in any dimension. The geometric model is a digital surface with which an energy is associated. The model grows inside the component to segment by following minimal energy paths. The segmentation result is obtained {\em a posteriori} by examining the energies of the successive model shapes. We validate our approach on several 2D images.

Keywords:
image segmentation, discrete deformable model, energy-minimization, digital surface