(For copyrighted material, see note below.)

Publications of J.-O. Lachaud

(Go to Short version)

[Int. Journals | Int. Conferences | Book chapters ]

Publications in international journals

  1. J.-O. Lachaud and B. Thibert, Properties of Gauss Digitized Shapes and Digital Surface Integration , Journal of Mathematical Imaging and Vision , pages 1 - 19, 2015.

    Abstract: This paper presents new topological and geometric properties of Gauss digitizations of Euclidean shapes, most of them holding in arbitrary dimension d. We focus on r-regular shapes sampled by Gauss digitization at gridstep h. The digitized boundary is shown to be close to the Euclidean boundary in the Hausdorff sense, the minimum distance h√d/2 being achieved by the projection map ξ induced by the Euclidean distance. Although it is known that Gauss digitized boundaries may not be manifold when d >= 3, we show that non-manifoldness may only occur in places where the normal vector is almost aligned with some digitization axis, and the limit angle decreases with h. We then have a closer look at the projection of the digitized boundary onto the continuous boundary by ξ. We show that the size of its non-injective part tends to zero with h. This leads us to study the classical digital surface integration scheme, which allocates a measure to each surface element that is proportional to the cosine of the angle between an estimated normal vector and the trivial surface element normal vector. We show that digital integration is convergent whenever the normal estimator is multigrid convergent, and we explicit the convergence speed. Since convergent estimators are now available in the literature, digital integration provides a convergent measure for digitized objects.

    Keywords: Gauss digitization, geometric inference, digital integral, multigrid convergence, set with positive reach. Math classification: 65D18, 68U05, 65D30.

  2. L. Cuel and J.-O. Lachaud and Q. Mérigot and B. Thibert, Robust Geometry Estimation Using the Generalized Voronoi Covariance Measure , SIAM Journal on Imaging Sciences

    Abstract: The Voronoi covariance measure (VCM) of a compact set K of R^d is a tensor-valued measure that encodes geometrical information on K and which is known to be resilient to Hausdorff noise but sensitive to outliers. In this paper, we generalize this notion to any distance-like function δ and define the δ-VCM. Combining the VCM with the distance to a measure and also with the witnessed-k-distance, we get a provably good tool for normal estimation that is resilient to Hausdorff noise and to outliers. We present experiments showing the robustness of our approach for normal and curvature estimation and sharp feature detection.

    Keywords: geometric inference, normal estimation, curvature estimation, distance to a measure, Voronoi covariance measure, power diagram.

  3. J. Levallois, D. Coeurjolly and J.-O. Lachaud, Scale-space feature extraction on digital surfaces , Computers & Graphics 51: 177 - 189, 2015. International Conference Shape Modeling International.

    Abstract: A classical problem in many computer graphics applications consists in extracting significant zones or points on an object surface, like loci of tangent discontinuity (edges), maxima or minima of curvatures, inflection points, etc. These places have specific local geometrical properties and often called generically features. An important problem is related to the scale, or range of scales, for which a feature is relevant. We propose a new robust method to detect features on digital data (surface of objects in Z3), which exploits asymptotic properties of recent digital curvature estimators. In [1, 2], authors have proposed curvature estimators (mean, principal and Gaussian) on 2D and 3D digitized shapes and have demonstrated their multigrid convergence (for C 3-smooth surfaces). Since such approaches integrate local information within a ball around points of interest, the radius is a crucial parameter. In this article, we consider the radius as a scale-space parameter. By analyzing the behavior of such curvature estimators as the ball radius tends to zero, we propose a tool to efficiently characterize and extract several relevant features (edges, smooth and flat parts) on digital surfaces.

    Keywords: feature extraction, digital geometry, scale-space, curvature estimation, multigrid convergence, integral invariants.

  4. D. Coeurjolly and J.-O. Lachaud and J. Levallois, Multigrid convergent principal curvature estimators in digital geometry , Computer Vision and Image Understanding , 129: 27 - 41, 2014.

    Abstract: In many geometry processing applications, the estimation of differential geometric quantities such as curva- ture or normal vector field is an essential step. In this paper, we investigate a new class of estimators on digital shape boundaries based on Integral Invariants. More precisely, we provide both proofs of multigrid convergence of principal curvature estimators and a complete experimental evaluation of their performances.

    Keywords: digital geometry, curvature estimation, multigrid convergence, integral invariants.

  5. A. Vacavant, T. Roussillon, B. Kerautret and J.-O. Lachaud, A combined multi-scale/irregular algorithm for the vectorization of noisy digital contours , Computer Vision and Image Understanding , 117(4): 438 - 450, 2013.

    Abstract: This paper proposes and evaluates a new method for reconstructing a polygonal representation from arbitrary digital contours that are possibly damaged or coming from the segmentation of noisy data. The method consists in two stages. In the first stage, a multi-scale analysis of the contour is conducted so as to identify noisy or damaged parts of the contour as well as the intensity of the perturbation. All the identified scales are then merged so that the input data is covered by a set of pixels whose size is increased according to the local intensity of noise. The second stage consists in transforming this set of resized pixels into an irregular isothetic object composed of an ordered set of rectangular and axisaligned cells. Its topology is stored as a Reeb graph, which allows an easy pruning of its unnecessary spurious edges. Every remaining connected part has the topology of a circle and a polygonal representation is independently computed for each of them. Four different geometrical algorithms, including a new one, are reviewed for the latter task. These vectorization algorithms are experimentally evaluated and the whole method is also compared to previous works on both synthetic and true digital images. For fair comparisons, when possible, several error measures between the reconstruction and the ground truth are given for the different techniques.

    Keywords: noisy object analysis, multi-scale noise detection, irregular grids, Reeb graph.

  6. J.-O. Lachaud and M. Said, Two efficient algorithms for computing the characteristics of a subsegment of a digital straight line , Discrete Applied Mathematics 161(15): 2293 - 2315, 2013.

    Abstract: We address the problem of computing the exact characteristics of any subsegment of a Digital Straight Line (DSL) with known characteristics (a slope a/b, a shift to origin μ). We present here two new algorithms that solve this problem, whose correctnesses are fully proved. Their principle is to descend/climb the Stern-Brocot tree of fractions in a topdown/bottom-up way. The top-down algorithm SmartDSS has a time complexity which depends on the sum of the quotients of the continued fraction of the output slope and on the number of pattern repetitions. As a corollary, its time complexity is bounded by the sum of the quotients of the continued fraction of the input slope, Said and Lachaud (2009) [18]. The bottom-up algorithm ReversedSmartDSS has a time complexity proportional to the difference of depth of the input slope and the slope of the output segment, Said and Lachaud (2011) [17]. As a corollary, its complexity is thus logarithmic in the coefficients of the input slope. These algorithms are also efficient in practice, as shown by a series of experiments comparing these new algorithms with standard arithmetic digital straight segment recognition.

    Keywords: discrete geometry, standard lines, digital straight segment recognition, Stern-Brocot tree.

  7. B. Kerautret and J.-O. Lachaud, Meaningful Scales Detection along Digital Contours for Unsupervised Local Noise Estimation , IEEE Transaction on Pattern Analysis and Machine Intelligence 43(12): 2379 - 2392, 2012.

    Abstract: The automatic detection of noisy or damaged parts along digital contours is a difficult problem since it is hard to distinguish between information and perturbation without further a priori hypotheses. However, solving this issue has a great impact on numerous applications, including image segmentation, geometric estimators, contour reconstruction, shape matching, or image edition. We propose an original strategy to detect the relevant scales at which each point of the digital contours should be considered. It relies on theoretical results of asymptotic discrete geometry. A direct consequence is the automatic detection of the noisy or damaged parts of the contour, together with its quantitative evaluation (or noise level). Apart from a given maximal observation scale, the proposed approach does not require any parameter tuning and is easy to implement. We demonstrate its effectiveness on several datasets. We present different direct applications of this local measure to contour smoothing and geometric estimators whose algorithms initially required a noise/scale parameter to tune: They show the pertinence of the proposed measure for digital shape analysis and reconstruction.

    Keywords: Local noise detection, Discrete geometry, Maximal segments, shape analysis.

  8. J.-O. Lachaud and X. Provençal, Two linear-time algorithms for computing the minimum length polygon of a digital contour, Discrete Applied Mathematics, 159(18): 2229 - 2250, 2011.

    Abstract: The Minimum Length Polygon (MLP) is an interesting first order approximation of a digital contour. For instance, the convexity of the MLP is characteristic of the digital convexity of the shape, its perimeter is a good estimate of the perimeter of the digitized shape. We present here two novel equivalent definitions of MLP, one arithmetic, one combinatorial, and both definitions lead to two different linear time algorithms to compute them. This paper extends the work presented in Provençal and Lachaud (2009), by detailing the algorithms and providing full proofs. It includes also a comparative experimental evaluation of both algorithms showing that the combinatorial algorithm is about 5 times faster than the other. We also checked the multigrid convergence of the length estimator based on the MLP.

    Keywords: Discrete geometry, Shape analysis, Minimum length polygon, Multigrid convergent length estimator, Combinatorics on words.

  9. E. Bretin, J.-O. Lachaud and É. Oudet, Regularization of Discrete Contour by Willmore Energy, Journal of Mathematical Imaging and Vision, 40(2): 214 - 229, 2011.

    Abstract: We propose a novel approach to reconstruct shapes from digital data. Contrarily to most methods, reconstructed shapes are smooth with a well-defined curvature field and have the same digitization as the input data: the range of application we have in mind is especially postprocessing to image segmentation where labelled regions are digital objects. For this purpose, we introduce three new algorithms to regularize digital contours based on the minimization of Willmore energy: our first algorithm is based on tools coming from discrete geometry, the second is related to convex geometry while the third approach is a constrained phase field minimization. The three algorithms are described in details and the convergence of the phase field approach is investigated. We present a comparative evaluation of all three methods, in terms of the accuracy of curvature estimators and computation time.

    Keywords: Regularization, Digital geometry, Willmore energy, Phase field reconstruction, Convex geometry

  10. G. Damiand, A. Dupas and J.-O. Lachaud. Fully deformable 3D digital partition model with topological control. Pattern Recognition Letters, 32(9): 1374-1383, 2011.

    Abstract: The main contribution of this paper is the definition of multi-label simple points ensuring that the partition topology remains invariant during a deformation process. The definition is based on intervoxel properties, and uses the notion of collapse on cubical complexes. This work is an extension of a restricted definition that prohibits the move of intersections of boundary surfaces. A deformation process is carried out with a greedy energy minimization algorithm. A discrete area estimator is used to approach at best standard regularizers classically used in continuous energy minimizing methods. The effectiveness of our approach is illustrated by the deformation of topologically correct initial partitions of a 3D medical image to minimize its energy.

    Keywords: Simple Point, Deformable Model, Intervoxel Boundaries, Multi-Label Image, Cubical complexes

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

    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:

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

    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

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

    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

  14. B. Kerautret, J.-O. Lachaud and B. Naegel, Curvature based corner detector for discrete, noisy and multi-scale contours , International Journal of Shape Modeling , 14(2): 127 - 145, 2008.

    Abstract: Estimating curvature on digital shapes is known to be a difficult problem even in high resolution images. Moreover the presence of noise contributes to the insta- bility of the estimators and limits their use in many computer vision applications like corner detection. Several recent curvature estimators, which comes from the dis- crete geometry community, can now process damaged data and integrate the amount of noise in their analysis. In this paper, we propose a comparative evaluation of these estimators, testing their accuracy, efficiency, and robustness with respect to several type of degradations. We further compare the best one with the visual curvature proposed by Liu et al., a recently published method from the computer vision community. We finally propose a novel corner detector, which is based on curvature estimation, and we provide a comprehensive set of experiments to compare it with many other classical cor- ner detectors. Our study shows that this corner detector has most of the time a better behavior than the others, while requiring only one parameter to take into account the noise level. It is also promising for multi-scale shape description.

    Keywords: curvature estimators, corner detection, multi-scale analysis, dominant point extraction.

  15. S. Alayrangues, X. Daragon, J.-O. Lachaud, and P. Lienhardt. Equivalence between Closed Connected n-G-maps without Multi-Incidence and n-Surfaces. Journal of Mathematical Imaging and Vision, 32(1): 1-22. 2008.

    Abstract:
    Many combinatorial structures have been designed to represent the topology of space subdivisions and images. We focus here on two particular models, namely the n-G-maps used in geometric modeling and computational geometry and the n-surfaces used in discrete imagery. We show that a subclass of n-G-maps is equivalent to n-surfaces. To achieve this, we provide several characterizations of n-surfaces. Finally, the proofs being constructive, we show how to switch from one representation to another effectively.

    Keywords:
    combinatorial structures, subdivisions, generalised maps, n-surfaces, geometric modeling, computational geometry, discrete imagery

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

    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

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

    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

  18. S. Peltier, S. Alayrangues, L. Fuchs, and J.-O. Lachaud. Computation of homology groups and generators. Computers & Graphics, 30(1):62-69, 2006.

    Abstract: Topological invariants are extremely useful in many applications related to digital imaging and geometric modeling, and homology is a classical one, which has not yet been fully explored in image applications. We present an algorithm that computes the whole homology of an object of arbitrary dimension: Betti numbers, torsion coefficients and generators. Effective implementation of this algorithm have been realized in order to perform experimentations. Results on classical shapes in algebraic topology and on discrete objects are presented and discussed.

    Keywords: Topological invariant, shape invariant, homology groups, image analysis

  19. J.-O. Lachaud and B. Taton. Deformable Model with a Complexity Independent from Image Resolution. Computer Vision and Image Understanding, 99(3): 453-475. 2005.

    Abstract:
    We present a parametric deformable model which recovers image components with a complexity independent from the resolution of input images. The proposed model also automatically changes its topology and remains fully compatible with the general framework of deformable models. More precisely, the image space is equipped with a metric that expands salient image details according to their strength and their curvature. During the whole evolution of the model, the sampling of the contour is kept regular with respect to this metric. By this way, the vertex density is reduced along most parts of the curve while a high quality of shape representation is preserved. The complexity of the deformable model is thus improved and is no longer influenced by feature-preserving changes in the resolution of input images. Building the metric requires a prior estimation of contour curvature. It is obtained using a robust estimator which investigates the local variations in the orientation of image gradient. Experimental results on both computer generated and biomedical images are presented to illustrate the advantages of our approach.

    Keywords:
    deformable model, topology adaptation, resolution adaptation, curvature estimation, segmentation/reconstruction.

  20. D. Attali and J.-O. Lachaud. Delaunay conforming iso-surface; skeleton extraction and noise removal. Computational Geometry: Theory and Applications, 19(2-3):175-189, 2001.

    Abstract: Iso-surfaces are routinely used for the visualization of volumetric structures. Further processing (such as quantitative analysis, morphometric measurements, shape description) requires volume representations. The skeleton representation matches these requirements by providing a concise description of the object. This paper has two parts. First, we exhibit an algorithm which locally builds an iso-surface with two significant properties: it is a 2-manifold and the surface is a subcomplex of the Delaunay tetrahedrization of its vertices. Secondly, because of the latter property, the skeleton can in turn be computed from the dual of the Delaunay tetrahedrization of the iso-surface vertices. The skeleton representation, although informative, is very sensitive to noise. This is why we associate a graph to each skeleton for two purposes: (i) the amount of noise can be identified and quantified on the graph and (ii) the selection of the graph subpart that does not correspond to noise induces a filtering on the skeleton. Finally, we show some results on synthetic and medical images. An application, measuring the thickness of objects (heart ventricles, bone samples) is also presented.

    Keywords: Volumetric imaging; Iso-surface; Delaunay tetrahedrization; Voronoi graph; Skeleton

  21. J.-O. Lachaud and A. Montanvert. Continuous analogs of digital boundaries: A topological approach to iso-surfaces. Graphical Models, 62:129--164, 2000.

    Abstract:
    The definition and extraction of objects and their boundaries within an image are essential in many imaging applications. Classically, two approaches are followed. The first considers the image as a sample of a continuous scalar field: boundaries are implicit surfaces in this field; they are often called iso-surfaces. The second considers the image as a digital space with adjacency relations and classifies elements of this space as inside or outside: boundaries are pairs composed of one inside element and one outside element; they are called digital boundaries. In this paper, we show that these two approaches are closely related. This statement holds for arbitrary dimensions. To do so, we propose a local method to construct a continuous analog of a digital boundary. The continuous analog is designed to satisfy properties in the Euclidean space that are similar to the properties of its counterpart in the digital space (e.g., connectedness, closeness, separation). It appears that this continuous analog is indeed a piecewise linear approximation of an iso-(hyper)surface (i.e., a triangulated iso-surface in the three-dimensional case). Furthermore, we derive significant digital boundary properties from its continuous analog using the Jordan-Brouwer separation theorem: new Jordan pairs, new adjacencies between boundary elements, new Jordan triples. We conclude this paper by illustrating the 3D case more precisely. In particular, we show that a digital boundary can be transformed directly into a triangulated iso-surface. The implementation of this transformation and its efficiency are discussed with a comparison with the classical marching-cubes algorithm.

    Keywords:
    digital topology, isosurface extraction, marching cubes, digital surface tracking, Jordan-Brouwer theorem, simplicial complexes

  22. J.-O. Lachaud and A. Montanvert. Deformable Meshes with Automated Topology Changes for Coarse-to-fine 3D Surface Extraction. Medical Image Analysis, 3(2):187-207, 1999.

    Abstract:
    This work presents a generic deformable model for extracting objects from volumetric data with a coarse-to-fine approach. This model is based on a dynamic triangulated surface which alters its geometry according to internal and external constraints to perform shape recovery. A new framework for topology changes is proposed to extract complex objects: within this framework, the model dynamically adapts its topology to the geometry of its vertices according to simple distance constraints. In order to speed up the process, an algorithm of pyramid construction with any reduction factor transforms the image into a set of images with progressive resolutions. This organization into a hierarchy, combined with a model which can adapt its sampling to the resolution of the workspace, enables a fast estimation of the shapes included in the image. After that, the model searches for finer and finer details while relying successively on the different levels of the pyramid.

    Keywords:
    3D biomedical imagery, image analysis, image segmentation, shape recovery, deformable models, automated topology changes, multiresolution, snakes, 3D pyramid, deformable surface

Publications in international conferences

  1. B. Kerautret and A. Kr\"ahenb\"uhl and I. Debled-Rennesson and J.-O. Lachaud, 3D Geometric Analysis of Tubular Objects Based on Surface Normal Accumulation , In Proc. Image Analysis and Processing (ICIAP 2015), Genova, Italy , volume 9279 of LNCS, pages 319 - 331, 2015. Springer.

    Abstract: This paper proposes a simple and efficient method for the reconstruction and extraction of geometric parameters from 3D tubular objects. Our method constructs an image that accumulates surface normal information, then peaks within this image are located by tracking. Finally, the positions of these are optimized to lie precisely on the tubular shape centerline. This method is very versatile, and is able to process various input data types like full or partial mesh acquired from 3D laser scans, 3D height map or discrete volumetric images. The proposed algorithm is simple to implement, contains few parameters and can be computed in linear time with respect to the number of surface faces. Since the extracted tube centerline is accurate, we are able to decompose the tube into rectilinear parts and torus-like parts. This is done with a new linear time 3D torus detection algorithm, which follows the same principle of a previous work on 2D arc circle recognition. Detailed experiments show the versatility, accuracy and robustness of our new method.

    Keywords: Tubular objects analysis, centerline extraction, mesh data, partial scan data, heightmap data, digital data, tube reconstruction.

  2. F. Grélard and F. Baldacci and A. Vialard and J.-O. Lachaud, Precise Cross-Section Estimation on Tubular Organs , In Proc. Computer Analysis of Images and Patterns (CAIP'2015), La Valetta, Malta , volume 9257 of LNCS, pages 277 - 288, 2015. Springer.

    Abstract: In this article we present a new method to estimate precisely the cross-section of tubular organs. Obtaining a precise cross-section is the critical step to perform quantitative analysis of those organs, for which diameter or area are often correlated to pathologies. Our estimation method, based on a covariance measure from the Voronoi cells of the set of studied points, can be computed either from the skeleton representation, or from the whole set of voxels of the segmented tubular organ. This estimator can give a cross-section estimation from any point of the organ, and is both more accurate and more robust to segmentation errors than state-of-the-art methods.

    Keywords: Tubular organ analysis, cross-section estimation, Voronoi covariance measure.

  3. J. Levallois, D. Coeurjolly and J.-O. Lachaud, Parameter-Free and Multigrid Convergent Digital Curvature Estimators , In Proc. Int. Conf. on Discrete Geometry for Computer Imagery (DGCI'2014), Sienna, Italy , volume 8668 of LNCS, pages 162 - 175, 2014. Springer.

    Abstract: In many geometry processing applications, the estimation of differential geometric quantities such as curvature or normal vector field is an essential step. Focusing on multigrid convergent estimators, most of them require a user specified parameter to define the scale at which the analysis is performed (size of a convolution kernel, size of local patches for polynomial fitting, etc). In a previous work, we have proposed a new class of estimators on digital shape boundaries based on Integral Invariants. In this paper, we propose new variants of these estimators which are parameter-free and ensure multigrid convergence in 2D. As far as we know, these are the first parameter-free multigrid convergent curvature estimators.

    Keywords: curvature estimation, multigrid convergence, integral invariants, digital straight segments, parameter-free estimators.

  4. L. Cuel, J.-O. Lachaud and B. Thibert, Voronoi-Based Geometry Estimator for 3D Digital Surfaces , In Proc. Int. Conf. on Discrete Geometry for Computer Imagery (DGCI'2014), Sienna, Italy , volume 8668 of LNCS, pages 134-149, 2014. Springer.

    Abstract: We propose a robust estimator of geometric quantities such as normals, curvature directions and sharp features for 3D digital surfaces. This estimator only depends on the digitisation gridstep and is defined using a digital version of the Voronoi Covariance Measure, which exploits the robust geometric information contained in the Voronoi cells. It has been proved in [1] that the Voronoi Covariance Measure is resilient to Hausdorff noise. Our main theorem explicits the conditions under which this estimator is multigrid convergent for digital data. Moreover, we determine what are the parameters which maximise the convergence speed of this estimator, when the normal vector is sought. Numerical experiments show that the digital VCM estimator reliably estimates normals, curvature directions and sharp features of 3D noisy digital shapes.

    Keywords: digital estimators, Voronoi covariance measure, stability, Hausdorff noise, normal estimation, feature detection.

  5. D. Coeurjolly, J.-O. Lachaud and J. Levallois, Integral based Curvature Estimators in Digital Geometry In Proc. Int. Conf. Discrete Geometry for Computer Imagery (DGCI'2013), Sevilla, Spain , volume 7749 of LNCS, pages 215 - 227, 2013. Springer.

    Abstract: In many geometry processing applications, the estimation of differential geometric quantities such as curvature or normal vector field is an essential step. In this paper, we investigate a new class of estimators on digital shape boundaries based on Integral Invariants. More precisely, we provide both proofs of multigrid convergence of curvature estimators and a complete experimental evaluation of their performances.

    Keywords: digital geometry, curvature estimation, multigrid convergence, integral invariant.

  6. M. Postolski, M. Janaszewski, Y. Kenmochi and J.-O. Lachaud, Tangent estimation along 3D digital curves , In Proc. 21st International Conference on Pattern Recognition (ICPR'2012), Tsukuba, Japan , pages 2079 - 2082, nov 2012.

    Abstract: In this paper, we present a new three-dimensional (3D) tangent estimator by extending the well-known two-dimensional (2D) λ-maximal segment tangent (λ-MST) estimator, which has very good theoretical and practical behaviors. We show that our proposed estimator keeps the same time complexity, accuracy and experimental asymptotic behaviors as the original 2D one.

    Keywords: tangent estimation, accuracy, convergence, pattern recognition, shape, time complexity.

  7. B. Kerautret, J.-O. Lachaud and M. Said, Meaningful Thickness Detection On Polygonal Curve In Proc. 1st Int. Conf. on Pattern Recognition Applications and Methods (ICPRAM'2012), Vilamoura, Algarve, Portugal , pages 372-379, 2012.

    Abstract: The notion of meaningful scale was recently introduced to detect the amount of noise present along a digital contour (Kerautret and Lachaud, 2009b). It relies on the asymptotic properties of the maximal digital straight segment primitive. Even though very useful, the method is restricted to digital contour data and is not able to process other types of geometric data like disconnected set of points. In this work, we propose a solution to outcome this limitation. It exploits another primitive called the Blurred Segment (Debled-Rennesson et al., 2006) which controls the straight segment recognition precision of disconnected sets of points. The resulting noise detection provides precise results and is also more simple to implement. A first application of contour smoothing demonstrates the efficiency of the proposed method. The algorithms can also be tested online (Kerautret et al., 2011).

    Keywords: shape analysis, noise detection, meaningful scale, contour representation.

  8. T. Roussillon and J.-O. Lachaud, Accurate Curvature Estimation along Digital Contours with Maximal Digital Circular Arcs , In Proc. Int. Workshop Combinatorial Image Analysis (IWCIA2011), Madrid, Spain , volume 6636 of LNCS, pages 43 - 55, 2011. Springer.

    Abstract: We propose in this paper a new curvature estimator based on the set of maximal digital circular arcs. For strictly convex shapes with continuous curvature fields digitized on a grid of step h, we show that this estimator is mutligrid convergent if the discrete length of the maximal digital circular arcs grows in Ω(h^(-1/2)). We indeed observed this order of magnitude. Moreover, experiments showed that our estimator is at least as fast to compute as existing estimators and more accurate even at low resolution.

    Keywords: Digital contour, Maximal digital circular arc, Curvature estimator.

  9. J.-O. Lachaud and X. Provençal, Dynamic Minimum Length Polygon , In Proc. Int. Workshop Combinatorial Image Analysis (IWCIA2011), Madrid, Spain , volume 6636 of LNCS, pages 208 - 221, 2011. Springer.

    Abstract: This paper presents a formal framework for representing all reversible polygonalizations of a digital contour (i.e. the boundary of a digital object). Within these polygonal approximations, a set of local operations is defined with given properties, e.g., decreasing the total length of the polygon or diminishing the number of quadrant changes. We show that, whatever the starting reversible polygonal approximation, iterating these operations leads to a specific polygon: the Minimum Length Polygon. This object is thus the natural representative for the whole class of reversible polygonal approximations of a digital contour. Since all presented operations are local, we obtain the first dynamic algorithm for computing the MLP. This gives us a sublinear time algorithm for computing the MLP of a contour, when the MLP of a slightly different contour is known.

    Keywords: Digital contour, Minimum Length Polygon, Dynamic algorithm, Polygonal approximation.

  10. E. Charrier and J.-O. Lachaud, Maximal Planes and Multiscale Tangential Cover of 3D Digital Objects , In Proc. Int. Workshop Combinatorial Image Analysis (IWCIA2011), Madrid, Spain , volume 6636 of LNCS, pages 132 - 143, 2011. Springer.

    Abstract: The sequence of maximal segments (i.e. the tangential cover) along a digital boundary is an essential tool for analyzing the geometry of two-dimensional digital shapes. The purpose of this paper is to de- fine similar primitives for three-dimensional digital shapes, i.e. maximal planes defined over their boundary. We provide for them an unambiguous geometrical definition avoiding a simple greedy characterization as previous approaches. We further develop a multiscale theory of maximal planes. We show that these primitives are representative of the geometry of the digital object at different scales, even in the presence of noise.

    Keywords: Digital plane, Maximal planes, Tangential cover, Multiscale analysis.

  11. G. Damiand, A. Dupas and J.-O. Lachaud, Combining Topological Maps, Multi-Label Simple Points, and Minimum-Length Polygons for Efficient Digital Partition Model , In Proc. Int. Workshop Combinatorial Image Analysis (IWCIA2011), Madrid, Spain , volume 6636 of LNCS, pages 56 - 69, 2011. Springer.

    Abstract: Deformable models have shown great potential for image segmentation. They include discrete models whose combinatorial formulation leads to efficient and sometimes optimal minimization algorithms. In this paper, we propose a new discrete framework to deform any partition while preserving its topology. We show how to combine the use of multilabel simple points, topological maps and minimum-length polygons in order to implement an efficient digital deformable partition model. Our experimental results illustrate the potential of our framework for segmenting images, since it allows the mixing of region-based, contour-based and regularization energies, while keeping the overall image structure.

    Keywords: Topological Map, ML-Simple Point, Minimum-Length Polygon, Deformable Model, Interpixel Boundaries, Multi-Label Image.

  12. B. Kerautret, J.-O. Lachaud and T. P. Nguyen, Circular arc reconstruction of digital contours with chosen Hausdorff error , In Proc. Int. Conf. on Discrete Geometry for Computer Imagery (DGCI2011), Nancy, France , volume 6607 of LNCS, pages 247 - 259, 2011. Springer.

    Abstract: We address the problem of constructing an approximate continuous representation of a digital contour with guarantees on the Hausdorff error between the digital shape and its reconstruction. Instead of polygonalizing the contour, we propose to reconstruct the shape with circular arcs. To do so, we exploit the recent curvature estimators. From their curvature field, we introduce a new simple and efficient algorithm to approximate a digital shape with as few arcs as possible at a given scale, specified by a maximal admissible Hausdorff distance. We show the potential of our reconstruction method with numerous experiments and we also compare our results with some recent promising approaches. Last, all these algorithms are available online for comparisons on arbitrary shapes.

    Keywords: Digital contour approximation, circular arc reconstruction, GMC curvature estimator.

  13. T. Roussillon and J.-O. Lachaud, Delaunay properties of digital straight segments , In Proc. Int. Conf. on Discrete Geometry for Computer Imagery (DGCI2011), Nancy, France , volume 6607 of LNCS, pages 308 - 319, 2011. Springer.

    Abstract: We present new results concerning the Delaunay triangulation of the set of points of pieces of digital straight lines. More precisely, we show how the triangulation topology follows the arithmetic decomposition of the line slope as well as its combinatorial decomposition (splitting formula). A byproduct is a linear time algorithm for computing the Delaunay triangulation and the Voronoi diagram of such sets.

    Keywords: Digital straight segment, Splitting formula, Continued fraction, Voronoi diagram, Delaunay triangulation.

  14. M. Said and J.-O. Lachaud, Computing the Characteristics of a SubSegment of a Digital Straight Line in Logarithmic Time , In Proc. Int. Conf. on Discrete Geometry for Computer Imagery (DGCI2011), Nancy, France , volume 6607 of LNCS, pages 320 - 332, 2011. Springer.

    Abstract: We address the problem of computing the exact characteristics of any subsegment of a digital straight line with known characteristics. We present a new algorithm that solves this problem, whose correctness is proved. Its principle is to climb the Stern-Brocot tree of fraction in a bottom-up way. Its worst-time complexity is proportionnal to the difference of depth of the slope of the input line and the slope of the output segment. It is thus logarithmic in the coefficients of the input slope. We have tested the effectiveness of this algorithm by computing a multiscale representation of a digital shape, based only on a digital straight segment decomposition of its boundary.

    Keywords: Standard lines, Digital straight segment recognition, Stern-Brocot tree.

  15. T. P. Nguyen, B. Kerautret, I. Debled-Rennesson and J.-O. Lachaud Unsupervised, Fast and Precise Recognition of Digital Arcs in Noisy Images In Proc. International Conference Computer Vision and Graphics (ICCVG2010), Warsaw, Poland, volume 6374 of LNCS, part I, pages 59-68, 2010. Springer.

    Abstract: In image processing and pattern recognition, the accuracy of most algorithms is dependent on a good parameterization, generally a computation scale or an estimation of the amount of noise, which may be global or variable within the input image. Recently, a simple and linear time algorithm for arc detection in images was proposed [1]. Its accuracy is dependent on the correct evaluation of the amount of noise, which was set by the user in this former version. In the present work we integrate a promising unsupervised noise detection method [2] in this arc recognition method, in order to process images with or without noise, uniformly distributed or variable within the picture. We evaluate the performance of this algorithm and we compare it with standard arc and circle detection methods based on extensions of the Hough transform.

    Keywords: image processing, digital arc recognition, noise detection.

  16. M. Said, J.-O. Lachaud and F. Feschet, Multiscale Analysis of Digital Segments by Intersection of 2D Digital Lines, In Proc. 20th International Conference on Pattern Recognition (ICPR2010), Istanbul, Turkey , pages 4097-4100, august 2010. IEEE.

    Abstract: A theory for the multiscale analysis of digital shapes would be very interesting for the pattern recognition community, giving a digital equivalent of the continuous scale-space theory. We focus here on providing analytical formulae of the multiresolution of Digital Straight Segments (DSS), which is a fundamental tool for describing digital shape contours.

    Keywords: digital straight segment, multiresolution, digital straight line intersection.

  17. A. Dupas, G. Damiand and J.-O. Lachaud, Multi-Label Simple Points Definition for 3D Images Digital Deformable Model. In Proc. Int. Conf. on Discrete Geometry for Computer Imagery (DGCI'2009), Montréal, Québec, volume 5810 of LNCS, pages 156-167, 2009. Springer.

    Abstract: The main contribution of this paper is the definition of multilabel simple points that ensures that the partition topology remains invariant during a deformable partition process. The definition is based on simple intervoxel properties and is easy to implement. A deformation process is carried out with a greedy energy minimization algorithm. A discrete area estimator is used to approach at best standard regularizers classically used in continuous energy minimizing methods. The effectiveness of our approach is shown on several 3D image segmentations.

    Keywords: digital topology, simple Point, deformable model, multi-label image.

  18. X. Provençal and J.-O. Lachaud, Two linear-time algorithms for computing the minimum length polygon of a digital contour. In Proc. Int. Conf. on Discrete Geometry for Computer Imagery (DGCI'2009), Montréal, Québec, volume 5810 of LNCS, pages 104-117, 2009. Springer.

    Abstract: The Minimum Length Polygon (MLP) is an interesting first order approximation of a digital contour. For instance, the convexity of the MLP is characteristic of the digital convexity of the shape, its perimeter is a good estimate of the perimeter of the digitized shape. We present here two novel equivalent definitions of MLP, one arithmetic, one combinatorial, and both definitions lead to two different linear time algorithms to compute them.

    Keywords:Digital convexity, minimum length polygon, digital straight segment, Lyndon words, Christoffel words, Duval algorithm.

  19. F. de Vieilleville and J.-O. Lachaud, Digital Deformable Model Simulating Active Contours . In Proc. Int. Conf. on Discrete Geometry for Computer Imagery (DGCI'2009), Montréal, Québec, volume 5810 of LNCS, pages 203-216, 2009. Springer.

    Abstract: Deformable models are continuous energy-minimizing techniques that have been successfully applied to image segmentation and tracking since twenty years. This paper defines a novel purely digital deformable model (DDM), whose internal energy is based on the minimum length polygon (MLP). We prove that our combinatorial regularization term has “convex” properties: any local descent on the energy leads to a global optimum. Similarly to the continuous case where the optimum is a straight segment, our DDM stops on a digital straight segment. The DDM shares also the same behaviour as its continuous counterpart on images.

    Keywords: Digital deformable model, active contour, minimum length polygon.

  20. M. Said and J.-O. Lachaud, Multiscale Discrete Geometry. In Proc. Int. Conf. on Discrete Geometry for Computer Imagery (DGCI'2009), Montréal, Québec, volume 5810 of LNCS, pages 118-131, 2009. Springer.

    Abstract: This paper presents a first step in analyzing how digital shapes behave with respect to multiresolution. We first present an analysis of the covering of a standard digital straight line by a multi-resolution grid. We then study the multi-resolution of Digital Straight Segments (DSS): we provide a sublinear algorithm computing the exact characteristics of a DSS whenever it is a subset of a known standard line. We finally deduce an algorithm for computing a multiscale representation of a digital shape, based only on a DSS decomposition of its boundary.

    Keywords: multiscale geometry, digital contours, standard lines, digital straight segment recognition, Stern-Brocot tree, multi-resolution.

  21. B. Kerautret and J.-O. Lachaud. Multiscale Analysis of Discrete Contours for Unsupervised Noise Detection. In Proc. Int. Workshop on Combinatorial Image Analysis (IWCIA2009), Cancun, Mexico, volume 5852 of LNCS, pages 187-200, 2009. Springer.

    Abstract: Blurred segments [2] were introduced in discrete geometry to address possible noise along discrete contours. The noise is not really detected but is rather canceled out by thickening digital straight segments. The thickness is tuned by a user and set globally for the contour, which requires both supervision and non-adaptive contour processing. To overcome this issue, we propose an original strategy to detect locally both the amount of noise and the meaningful scales of each point of a digital contour. Based on the asymptotic properties of maximal segments, it also detects curved and flat parts of the contour. From a given maximal observation scale, the proposed approach does not require any parameter tuning and is easy to implement. We demonstrate its effectiveness on several datasets. Its potential applications are numerous, ranging from geometric estimators to contour reconstruction.

    Keywords: Noise detection, discrete contour, maximal segments.

  22. F. de Vieilleville, J.-O. Lachaud, P. Herlin, O. Lezoray and B. Plancoulain, Top-Down Segmentation of Histological Images Using a Digital Deformable Model. In Proc. Advances in Visual Computing (ISVC'2009), Las Vegas, Nevada, volume 5875 of LNCS, pages 327-336, 2009. Springer

    Abstract: This paper presents a straightforward top-down segmenta- tion method based on a contour approach on histological images. Our approach relies on a digital deformable model whose internal energy is based on the minimum length polygon and that uses a greedy algorithm to minimise its energy. Experiments on real histological images of breast cancer yields results as good as that of classical active contours.

    Keywords: histological images, digital deformable model, minimum length polygon, top-down segmentation, active contours.

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

    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

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

    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

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

    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

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

    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

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

    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

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

    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

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

    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

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

    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

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

    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

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

    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

  33. S. Peltier, S. Alayrangues, L. Fuchs, J.-O. Lachaud. Computation of homology groups and generators. 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 195-205, 2005. Springer.

    Abstract:
    Topological invariants are extremely useful in many applications related to digital imaging and geometric modelling, and homology is a classical one. We present an algorithm that computes the whole homology of an object of arbitrary dimension: Betti numbers, torsion coefficients and generators. Results on classical shapes in algebraic topology are presented and discussed.

    Keywords:
    digital topology, topological invariants, homology computation, generators, Smith Normal Form, simplicial homology

  34. J.-O. Lachaud and B. Taton. Resolution Independent Deformable Model. In Proc. 17th int. Conf. on Pattern Recognition (ICPR'2004), Cambridge, United Kingdom, 23-26 August, volume II, pages 237-240, 2004. IEEE Computer Society Press.

    Abstract:
    In this paper we propose a parametric deformable model that automatically adapts its topology and that recovers accurately image components with a complexity independent from the resolution of input image. The main idea is to equip the image space with a metric that expands interesting features in the image depending on their geometry.

    Keywords:
    3D image segmentation, shape recovery, deformable models, snakes, automated topology changes, adaptive resolution, Riemannian geometry, Lagrangian mechanics, deformable surface, structure tensor

  35. S. Alayrangues, X. Daragon, J.-O. Lachaud, and P. Lienhardt. Equivalence between Regular n-G-maps and n-surfaces. In R. Klette and J. Zunic, editors, Proc. Int. Work. Combinatorial Image Analysis (IWCIA'2004), Auckland, New Zealand, December 1-3, volume 3322 of LNCS, pages 122-136, 2004. Springer.

    Abstract:
    Many combinatorial structures have been designed to represent the topology of space subdivisions and images. We focus here on two particular models, namely the n-G-maps used in geometric modeling and computational geometry and the n-surfaces used in discrete imagery. We show that a subclass of n-G-maps is equivalent to n-surfaces. We exhibit a local property characterising this subclass, which is easy to check algorithmatically. Finally, the proofs being constructive, we show how to switch from one representation to another effectively.

    Keywords:
    combinatorial structures, subdivisions, generalised maps, n-surfaces, geometric modeling, computational geometry, discrete imagery

  36. J.-O. Lachaud and B. Taton, Deformable Model with Adaptive Mesh and Automated Topology Changes. In M. Rioux, P. Boulanger and G. Godin, editors, Proc. 4th int. Conf. 3-D Digital Imaging and Modeling (3DIM'2003), Banff, Alberta, Canada, 2003. IEEE Computer Society Press.

    Abstract:
    Due to their general and robust formulation deformable models offer a very appealing approach to 3D image segmentation. However there is a trade-off between model genericity, model accuracy and computational efficiency. In general, fully generic models require a uniform sampling of either the space or their mesh. The segmentation accuracy is thus a global parameter. Recovering small image features results in heavy computational costs whereas generally only restricted parts of images require a high segmentation accuracy. This paper presents a highly deformable model that both handles fully automated topology changes and adapts its resolution locally according to the geometry of image features. The main idea is to replace the Euclidean metric with a Riemannian metric that expands interesting parts of the image. Then, a regular sampling is maintained with this new metric. This allows to automatically handle topology changes while increasing the model resolution locally according to the geometry of image components. By this way high quality segmentation is achieved with reduced computational costs.

    Keywords:
    3D image segmentation, shape recovery, deformable models, snakes, automated topology changes, adaptive resolution, Riemannian geometry, Lagrangian mechanics, deformable surface, structure tensor

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

    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

  38. J.-O. Lachaud. Coding cells of digital spaces: a framework to write generic digital topology algorithms. In Proc. Int. Work. Combinatorial Image Analysis (IWCIA'2003), Palermo, Italy, volume 12 of Electronic Notes in Discrete Mathematics, 2003.

  39. Abstract:
    This paper proposes a concise coding of the cells of n-dimensional finite regular grids. It induces a simple, generic and efficient framework for implementing classical digital topology data structures and algorithms. Discrete subsets of multidimensional images (e.g. regions, digital surfaces, cubical cell complexes) have then a common and compact representation. Moreover, algorithms have a straightforward and efficient implementation, which is independent from the dimension or sizes of digital images. We illustrate that point with generic hypersurface boundary extraction algorithms by scanning or tracking. This framework has been implemented and basic operations as well as the presented applications have been benchmarked.

    Keywords:
    digital topology, Khalimsky topology, digital surface tracking, cell coding

  40. B. Taton and J.-O. Lachaud. Deformable Model with non-Euclidean Metrics. In A. Heyden, G. Sparr, M. Nielsen, and P. Johansen, editors, Proc. 7th European Conference on Computer Vision (ECCV'2002), Copenhagen, Denmark, volume 2352 (part III) of LNCS, pages 438-453, 2002. Springer, Berlin.

    Abstract:
    Deformable models like snakes are a classical tool for image segmentation. Highly deformable models extend them with the ability to handle dynamic topological changes, and therefore to extract arbitrary complex shapes. However, the resolution of these models largely depends on the resolution of the image. As a consequence, their time and memory complexity increases at least as fast as the size of input data. In this paper we extend an existing highly deformable model, so that it is able to locally adapt its resolution with respect to its position. With this property, a significant precision is achieved in the interesting parts of the image, while a coarse resolution is maintained elsewhere. The general idea is to replace the Euclidean metric of the image space by a deformed non-Euclidean metric, which geometrically expands areas of interest. With this approach, we obtain a new model that follows the robust framework of classical deformable models, while offering a significant independence from both the size of input data and the geometric complexity of image components.

    Keywords:
    image segmentation, deformable model, non-Euclidean geometry, topology adaptation, optimization

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

    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

Book chapters

  1. D. Coeurjolly, J.-O. Lachaud and T. Roussillon, Multigrid Convergence of Discrete Geometric Estimators , In Digital Geometry Algorithms , volume 2 of LNCVB, pages 395 - 424, 2012. Springer.

    Abstract: The analysis of digital shapes requires tools to determine accurately their geometric characteristics. Their boundary is by essence discrete and is seen by continuous geometry as a jagged continuous curve, either straight or not derivable. Discrete geometric estimators are specific tools designed to determine geometric information on such curves. We present here global geometric estimators of area, length, moments, as well as local geometric estimators of tangent and curvature. We further study their multigrid convergence, a fundamental property which guarantees that the estimation tends toward the exact one as the sampling resolution gets finer and finer. Known theorems on multigrid convergence are summarized. A representative subsets of estimators have been implemented in a common framework (the library DGtal), and have been experimentally evaluated for several classes of shapes. Thus, the interested users have all the information for choosing the best adapted estimators to their applications, and readily dispose of an efficient implementation.

    Keywords: digital estimators, multigrid convergence, length estimation, tangent estimation, curvature estimation.

  2. J.-O. Lachaud, Digital Shape Analysis with Maximal Segments In Applications of Discrete Geometry and Mathematical Morphology , volume 7346 of LNCS, pages 14 - 27, 2012.

    Abstract: We show in this paper how a digital shape can be efficiently analyzed through the maximal segments defined along its digital contour. They are efficiently computable. They can be used to prove the multigrid convergence of several geometric estimators. Their asymptotic properties can be used to estimate the local amount of noise along the shape, through a multiscale analysis.

    Keywords: discrete geometry, digital shape analysis, digital straight segments, geometric estimators, multigrid convergence, noise detection, digital convexity.

  3. J.-O. Lachaud and S. Valette, Géométrie discrète et images numériques, chapter 12. Approximation par triangulation. Traité IC2. Hermès, 2007. In french.

    Abstract:
    Dans ce chapitre, nous traitons de l'approximation des surfaces discrètes par des maillages. Cette transformation ne sera pas forcément réversible. La relaxation de cette contrainte offre en effet plus de flexibilité. Nous aborderons plusieurs problématiques :

    • Volumique vers surfacique. Les surfaces discrètes ne sont pas toujours exploitables directement, et la transformation de l'image 3D directement en une représentation surfacique (un maillage) est parfois souhaitable, notamment pour le rendu ou l'extraction quantitative de caractéristiques. Nous verrons une technique d'extraction de surfaces d'intérêt directement à partir d'une image 3D, binaire ou non.
    • Surface discrète vers surface triangulée. Il est parfois commode de passer d'une représentation par surface discrète à une représentation par surface triangulée. Nous présenterons deux techniques complémentaires~: la dualité surface discrète et isosurface pour construire une surface triangulée approchant la surface discrète (approximation réversible), une technique non réversible d'approximation de surface discrète sous forme d'une surface triangulée, qui est basée sur de la triangulation de points caractérisques par amincissement homotopique.
    • Simplification et remaillage de surfaces. Un maillage possède parfois trop d'éléments pour être affiché ou traité sur une machine possédant des ressources limitées (mémoire, vitesse). La simplification du maillage résout ce problème en réduisant son nombre d'éléments tout en conservant au mieux les caractérisques géométriques initiales. Plusieurs critères peuvent être pris en compte lors de la simplification : type des éléments crées (triangles, quadrangles, polygones), qualité de l'approximation (distance de Hausdorff), qualité des éléments générés (rapport d'aspect, régularité de la triangulation). D'autre part, l'efficacité de certaines applications est parfois dépendante de la qualité du maillage (régularité de l'échantillonnage, facteur de forme des éléments). En particulier, la précision des applications de simulation par éléments finis est directement dépendante du facteur de forme des éléments du maillage. Dans ce cas, remailler un modèle permet de rester fidèle à la forme initiale de l'objet, tout en améliorant les résultats d'une éventuelle simulation numérique.

    Keywords: triangulated surface, surface reconstruction, triangulation, digital surface, surface approximation, isosurface

  4. J.-O. Lachaud and R. Malgouyres, Géométrie discrète et images numériques, chapter 3. Topologie, courbes et surfaces discrètes. Traité IC2. Hermès, 2007. In french.

    Abstract:
    La topologie digitale est l'étude des propriétés des objets discrets qui sont indépendantes de leurs propriétés métriques. L'existence d'un trou dans un objet (au sens où un anneau a un trou et un pantalon a deux trous) n'est pas modifiée par une déformation ``continue'' de l'objet. D'un point de vue algorithmique, on cherche souvent à concevoir des méthodes de traitement d'image qui ne modifient pas la topologie des objets (connexité, existence d'un trou, etc). Le formalisme mathématique nécessaire pour définir de telles méthodes est assez abstrait.
    Au sens de la topologie, on peut dire que toutes les courbes fermées simples sont équivalentes (ou homéomorphes), et toute courbe fermée simple dans le plan possède un trou, au sens où elle sépare le plan (théorème de Jordan). La notion de déformation continue est formalisée dans la notion d'homotopie. Cette notion permet d'associer aux objets discrets des objets algébriques (des groupes), de manière qu'à deux objets topologiquement équivalents soient associés deux groupes équivalents. Ces invariants algébriques sont fondamentaux dans l'étude des propriétés topologiques des objets. Cette même notion d'homotopie permet de définir les points simples, qui sont les points qu'on peut enlever d'un objet sans en modifier la topologie. Les points simples sont en particulier à la base des algorithmes de squelettisation topologique.
    D'autres notions fondamentales en topologie sont les frontières et les surfaces. Par exemple, la frontière d'un objet connexe sans cavité est connexe. Une telle frontière doit satisfaire la propriété de séparation de Jordan. En topologie digitale, on se donne les outils pour définir des frontières et surfaces discrètes qui ont une bonne propriété de séparation. Ces frontières sont ensuite munies de structures de graphes, qui permettent de les construire et de les parcourir efficacement. Des outils existent ensuite pour estimer la géométrie de ces objets ou pour en fabriquer des modèles géométriques.

    Keywords: digital topology, digital surface, surface tracking, homotopy, topological invariant


When the paper is published under a copyrighted format, the provided files are only preprints.