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:
[ deVieilleville07a , deVieilleville06b , deVieilleville06a , deVieilleville05a ]
[ deVieilleville09a , Kerautret09a , deVieilleville08a , Kerautret08b , Kerautret08a , Lachaud07a , Lachaud05a , Lachaud03c ]
[ deVieilleville09a , deVieilleville08a , Lachaud07a , deVieilleville07a , deVieilleville06b ]
[ Braure06a , Lachaud01a ]
[ Kerautret09a , Kerautret08c , Kerautret08b , Kerautret08a ]
[ 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:
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:
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:
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(h2/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:
Keywords:
|
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:
Keywords:
|
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:
Keywords:
|
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:
Keywords:
|