Search

Your search keyword '"Sivignon A"' showing total 34 results
Start Over Author "Sivignon A" Topic [info.info-ti]computer science [cs]/image processing [eess.iv]
34 results on '"Sivignon A"'

1. Average Curve of n Digital Curves

Author

Isabelle Sivignon, GIPSA - Architecture, Géométrie, Perception, Images, Gestes (GIPSA-AGPIG), Département Images et Signal (GIPSA-DIS), Grenoble Images Parole Signal Automatique (GIPSA-lab ), Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Institut Polytechnique de Grenoble - Grenoble Institute of Technology-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes [2016-2019] (UGA [2016-2019])-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Institut Polytechnique de Grenoble - Grenoble Institute of Technology-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes [2016-2019] (UGA [2016-2019])-Grenoble Images Parole Signal Automatique (GIPSA-lab ), Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Institut Polytechnique de Grenoble - Grenoble Institute of Technology-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes [2016-2019] (UGA [2016-2019])-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Institut Polytechnique de Grenoble - Grenoble Institute of Technology-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes [2016-2019] (UGA [2016-2019]), and Sivignon, Isabelle

Subjects
050101 languages & linguistics, Arithmetic mean, Digital curves, 05 social sciences, 02 engineering and technology, [INFO.INFO-CG]Computer Science [cs]/Computational Geometry [cs.CG], Fast algorithm, [INFO.INFO-CG] Computer Science [cs]/Computational Geometry [cs.CG], [INFO.INFO-TI] Computer Science [cs]/Image Processing [eess.IV], [INFO.INFO-TI]Computer Science [cs]/Image Processing [eess.IV], Distance Transform, 0202 electrical engineering, electronic engineering, information engineering, Applied mathematics, Visibility, 020201 artificial intelligence & image processing, 0501 psychology and cognitive sciences, Squared deviations, Distance transform, ComputingMilieux_MISCELLANEOUS, Mathematics
Abstract

Building on [23], we investigate the problem of defining and computing the average of digital curves. Given n digital curves that satisfy compatibility conditions, a set - called the gap - in which the average curve is looked for, is defined. The proposed definition rewrites the classical arithmetic mean for curves by (i) defining the distance between each point of the gap and its projection on each curve and (ii) computing the points that minimize the sum of squared deviations. We show that, algorithmically speaking, computing such projections comes down to computing a distance transform with visibility constraints. We propose a fast algorithm to compute a good approximation of these distance maps and finally show that the average curve can be obtained using classical watershed algorithm.

Published
2019

2. Efficient distance transformation for path-based metrics

Author

David Coeurjolly, Isabelle Sivignon, Origami (Origami), Laboratoire d'InfoRmatique en Image et Systèmes d'information (LIRIS), Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Université de Lyon-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École Centrale de Lyon (ECL), Université de Lyon-Université Lumière - Lyon 2 (UL2)-Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Université Lumière - Lyon 2 (UL2), GIPSA Pôle Géométrie, Apprentissage, Information et Algorithmes (GIPSA-GAIA), Grenoble Images Parole Signal Automatique (GIPSA-lab), Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes (UGA)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP ), Université Grenoble Alpes (UGA)-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes (UGA)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP ), Université Grenoble Alpes (UGA), and ANR-15-CE40-0006,CoMeDiC,Métriques convergentes pour le calcul digital(2015)

Subjects
Dimension (graph theory), 020207 software engineering, 02 engineering and technology, [INFO.INFO-CG]Computer Science [cs]/Computational Geometry [cs.CG], Separable space, Combinatorics, Transformation (function), Medial axis, [INFO.INFO-TI]Computer Science [cs]/Image Processing [eess.IV], Signal Processing, Metric (mathematics), Path (graph theory), 0202 electrical engineering, electronic engineering, information engineering, 020201 artificial intelligence & image processing, Computer Vision and Pattern Recognition, Ball (mathematics), Voronoi diagram, Software, MathematicsofComputing_DISCRETEMATHEMATICS, Mathematics
Abstract

In many applications, separable algorithms have demonstrated their efficiency to perform high performance volumetric processing of shape, such as distance transformation or medial axis extraction. In the literature, several authors have discussed about conditions on the metric to be considered in a separable approach. In this article, we present generic separable algorithms to efficiently compute Voronoi maps and distance transformations for a large class of metrics. Focusing on path-based norms (chamfer masks, neighborhood sequences), we propose efficient algorithms to compute such volumetric transformation in dimension n . We describe a new O ( n ⋅ N n ⋅ log N ⋅ ( n + log f ) ) algorithm for shapes in a N n domain for chamfer norms with a rational ball of f facets (compared to O ( f ⌊ n 2 ⌋ ⋅ N n ) with previous approaches). Last we further investigate a more elaborate algorithm with the same worst-case complexity, but reaching a complexity of O ( n ⋅ N n ⋅ log f ⋅ ( n + log f ) ) experimentally, under assumption of regularity distribution of the mask vectors.

Published
2020

3. Fast recognition of a Digital Straight Line subsegment: Two algorithms of logarithmic time complexity

Author

Isabelle Sivignon, GIPSA - Architecture, Géométrie, Perception, Images, Gestes (GIPSA-AGPIG), Département Images et Signal (GIPSA-DIS), Grenoble Images Parole Signal Automatique (GIPSA-lab), Université Stendhal - Grenoble 3-Université Pierre Mendès France - Grenoble 2 (UPMF)-Université Joseph Fourier - Grenoble 1 (UJF)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Centre National de la Recherche Scientifique (CNRS)-Université Stendhal - Grenoble 3-Université Pierre Mendès France - Grenoble 2 (UPMF)-Université Joseph Fourier - Grenoble 1 (UJF)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Centre National de la Recherche Scientifique (CNRS)-Grenoble Images Parole Signal Automatique (GIPSA-lab), and Université Stendhal - Grenoble 3-Université Pierre Mendès France - Grenoble 2 (UPMF)-Université Joseph Fourier - Grenoble 1 (UJF)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Centre National de la Recherche Scientifique (CNRS)-Université Stendhal - Grenoble 3-Université Pierre Mendès France - Grenoble 2 (UPMF)-Université Joseph Fourier - Grenoble 1 (UJF)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Centre National de la Recherche Scientifique (CNRS)

Subjects
Discrete mathematics, Farey fan, Logarithm, Applied Mathematics, Computation, Digital geometry, local convex hull, Direct-sequence spread spectrum, subsegment, Digital subscriber line, [INFO.INFO-TI]Computer Science [cs]/Image Processing [eess.IV], Discrete Mathematics and Combinatorics, Arithmetic function, Farey sequence, Digital straight segment recognition, Algorithm, Time complexity, Mathematics
Abstract

Given a Digital Straight Line (DSL) of known characteristics ( a , b , μ ) , we address the problem of computing the characteristics of any of its subsegments. We propose two new algorithms that use the fact that a digital straight segment (DSS) can be defined by its set of separating lines. The representation of this set in the Z 2 space leads to a first algorithm of logarithmic time complexity. This algorithm precises and extends existing results for DSS recognition algorithms. The other algorithm uses the dual representation of the set of separating lines. It consists of a smart walk in the so called Farey fan, which can be seen as the representation of all the possible sets of separating lines for DSSs. Indeed, we take profit of the fact that the Farey fan of order n represents in a certain way all the digital segments of length n . The computation of the characteristics of a DSL subsegment is then equivalent to the localization of a point in the Farey fan. Using fine arithmetical properties of the fan, we design a fast algorithm of theoretical complexity O ( log ( n ) ) where n is the length of the subsegment. Experiments show that our algorithms are also efficient in practice, with a comparison to the ones previously proposed by Lachaud and Said (2013): in particular, the second one is faster in the case of “small” segments.

Published
2015

4. Petit manuel de survie en milieu digital

Author

gérard, yan, Sivignon, Isabelle, Laboratoire d'Informatique, de Modélisation et d'optimisation des Systèmes (LIMOS), Université Blaise Pascal - Clermont-Ferrand 2 (UBP)-Université d'Auvergne - Clermont-Ferrand I (UdA)-SIGMA Clermont (SIGMA Clermont)-Ecole Nationale Supérieure des Mines de St Etienne (ENSM ST-ETIENNE)-Centre National de la Recherche Scientifique (CNRS), GIPSA - Architecture, Géométrie, Perception, Images, Gestes (GIPSA-AGPIG), Département Images et Signal (GIPSA-DIS), Grenoble Images Parole Signal Automatique (GIPSA-lab ), Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Institut Polytechnique de Grenoble - Grenoble Institute of Technology-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes [2016-2019] (UGA [2016-2019])-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Institut Polytechnique de Grenoble - Grenoble Institute of Technology-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes [2016-2019] (UGA [2016-2019])-Grenoble Images Parole Signal Automatique (GIPSA-lab ), Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Institut Polytechnique de Grenoble - Grenoble Institute of Technology-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes [2016-2019] (UGA [2016-2019])-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Institut Polytechnique de Grenoble - Grenoble Institute of Technology-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes [2016-2019] (UGA [2016-2019]), Étienne BAUDRIER , Loïc MAZO, SIGMA Clermont (SIGMA Clermont)-Université d'Auvergne - Clermont-Ferrand I (UdA)-Ecole Nationale Supérieure des Mines de St Etienne-Centre National de la Recherche Scientifique (CNRS)-Université Blaise Pascal - Clermont-Ferrand 2 (UBP), and Sivignon, Isabelle

Subjects
[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM], [INFO.INFO-TI] Computer Science [cs]/Image Processing [eess.IV], [INFO.INFO-TI]Computer Science [cs]/Image Processing [eess.IV], [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], [INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS], [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]
Abstract

National audience; Saviez-vous que les légos ou Minecraft possèdent leur propre géométrie ? Bien sûr, la dénomination est différente mais il s’agit bien d’étudier les formes que l’on peut construire avec des briques élémentaires à faces carrées. En imagerie, les carrés et les cubes sont respectivement appelés pixels et voxels et trouvent une représentation naturelle dans la grille des entiers Z2 et Z3. Bizarrement, le but premier de cette théorie n’est pas de construire des vaisseaux spatiaux, des châteaux remplis de ninjas ou des villes titanesques mais des droites, des cercles, des sphères ou tout objet mathématique qui ressemble un tant soit peu aux figures de la géométrie élémentaire.En dehors de ses applications ludiques, la géométrie digitale se définit comme la géométrie de Z2, Z3 ou plus généralement Zn, autant dire des espaces peu favorables à la géométrie. Si vous vous aventurez sur le chemin qui mène dans ces contrées hostiles à la pensée mathématique et informatique, vous risquez de croiser le membre de l’une de ses tribus archaïques. Au cas fort improbable où vous arriveriez à communiquer avec cet être primitif, vous en apprendrez peut-être un peu plus sur les raisons étranges qui leur font développer cette géométrie rudimentaire en milieu si hostile :— d’abord sans doute une certaine nostalgie pour les jeux de construction, — pour les esthètes, la beauté de la théorie,— et pour d’autres, l’ambition de jouer aux Mac Gyver de la géométrie mais derrière ces fantaisies extravagantes qui peuvent les rendre sympathiques, voir naïfs ou inoffensifs, se terre un argument de fond qui ne relève pas de la simple lubie mais de l’emprise du numérique sur les sciences et technologies actuelles.De tous temps, les sciences physiques à moyennes et grandes échelles ont guidé le développement d’une partie des mathématiques et en particulier de théories géométriques continues telles que la géométrie différentielle avec en soubassement le corps des nombres réels ou complexes. Ce paradigme (R) a fait ses preuves mais sa nature continue le rend fondamentalement inadapté au traitement des données recueillies par les millions de périphériques qui alimentent les bases de données du monde entier. Les capteurs enregistrent des données sous forme digitale, soit à une résolution fixée des tableaux d’entiers c’est-à-dire des fonctions de Zd à valeur dans Z. Peut-on les traiter comme si c’étaient des fonctions de Rd dans R ? Probablement pas sans précautions mais c’est pourtant la voie la plus courante : l’usager pioche l’outil dont il a besoin dans les mathématiques continues, puis il recherche le moyen de l’appliquer à des structures entières, parfois grâce à un bricolage dont il garde le secret tant il existe d’innombrables façons de faire. Même si le résultat peut s’avérer significatif, passer par les nombres réels, c’est-à-dire une théorie basée sur des suites rationnelles de Cauchy convergentes, pour ensuite l’appliquer dans un cadre entier via des probabilités, une autre théorie ou un subterfuge est un détour considérable. Puisque de très nombreuses données à traiter se présentent sous la forme d’objets composés d’entiers -le b.a.-ba des nombres pourquoi ne pas développer une théorie géométrique qui soit directement adaptée à ce format de données ? C’est le chemin que nous vous proposons d’explorer. Il parcourt un territoire primitif encore largement vierge et donc propice à la recherche. Les agités du bocal dont je vous ai déjà parlé -on pourrait aussi les appeler des pionniers ont bien sûr commencé à le défricher mais en comparaison de l’ampleur de la tâche, on en peut pas dire qu’ils soient très nombreux. C’est un travail en cours, un chantier à ciel ouvert et un terrain de jeu sur lequel il est vivement recommandé de s’aventurer en dehors des chemins balisés. Mais avant de vous lâcher en pleine jungle, nous vous proposons un itinéraire balisé. Alors, remontez vos chaussettes, aspergez-vous de citronnelle, empoignez vos coupe-coupes et suivez le guide...

Published
2016

5. Representation of Imprecise Digital Objects

Author

Isabelle Sivignon, GIPSA - Architecture, Géométrie, Perception, Images, Gestes (GIPSA-AGPIG), Département Images et Signal (GIPSA-DIS), Grenoble Images Parole Signal Automatique (GIPSA-lab ), Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Institut Polytechnique de Grenoble - Grenoble Institute of Technology-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes [2016-2019] (UGA [2016-2019])-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Institut Polytechnique de Grenoble - Grenoble Institute of Technology-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes [2016-2019] (UGA [2016-2019])-Grenoble Images Parole Signal Automatique (GIPSA-lab ), and Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Institut Polytechnique de Grenoble - Grenoble Institute of Technology-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes [2016-2019] (UGA [2016-2019])-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Institut Polytechnique de Grenoble - Grenoble Institute of Technology-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes [2016-2019] (UGA [2016-2019])

Subjects
Pixel, business.industry, Digital geometry, shape analysis, 020207 software engineering, 02 engineering and technology, [INFO.INFO-CG]Computer Science [cs]/Computational Geometry [cs.CG], imprecision, [INFO.INFO-TI]Computer Science [cs]/Image Processing [eess.IV], 0202 electrical engineering, electronic engineering, information engineering, Ball (bearing), contour, 020201 artificial intelligence & image processing, Computer vision, Digital conversion, Imperfect, Artificial intelligence, business, Digitization, Shape analysis (digital geometry), Mathematics, Digital object
Abstract

International audience; In this paper, we investigate a new framework to handle noisy digital objects. We consider digital closed simple 4-connected curves that are the result of an imperfect digital conversion (scan, picture, etc), and call digital imprecise contours such curves for which an imprecision value is known at each point. This imprecision value stands for the radius of a ball around each point, such that the result of a perfect digitization lies in the union of all the balls. In the first part, we show how to define an imprecise digital object from such an imprecise digital contour. To do so, we define three classes of pixels : inside, outside and uncertain pixels. In the second part of the paper, we build on this definition for a volumetric analysis (as opposed to contour analysis) of imprecise digital objects. From so-called toleranced balls, a filtration of objects, called λ-objects is defined. We show how to define a set of sites to encode this filtration of objects.

Published
2016

6. Walking in the Farey fan to Compute the Characteristics of a Discrete Straight Line Subsegment

Author

Isabelle Sivignon, GIPSA - Architecture, Géométrie, Perception, Images, Gestes (GIPSA-AGPIG), Département Images et Signal (GIPSA-DIS), Grenoble Images Parole Signal Automatique (GIPSA-lab), Université Pierre Mendès France - Grenoble 2 (UPMF)-Université Stendhal - Grenoble 3-Université Joseph Fourier - Grenoble 1 (UJF)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Centre National de la Recherche Scientifique (CNRS)-Université Pierre Mendès France - Grenoble 2 (UPMF)-Université Stendhal - Grenoble 3-Université Joseph Fourier - Grenoble 1 (UJF)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Centre National de la Recherche Scientifique (CNRS)-Grenoble Images Parole Signal Automatique (GIPSA-lab), Université Pierre Mendès France - Grenoble 2 (UPMF)-Université Stendhal - Grenoble 3-Université Joseph Fourier - Grenoble 1 (UJF)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Centre National de la Recherche Scientifique (CNRS)-Université Pierre Mendès France - Grenoble 2 (UPMF)-Université Stendhal - Grenoble 3-Université Joseph Fourier - Grenoble 1 (UJF)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Centre National de la Recherche Scientifique (CNRS), and Sivignon, Isabelle

Subjects
Discrete mathematics, Computation, Order (ring theory), 0102 computer and information sciences, 02 engineering and technology, 01 natural sciences, Fast algorithm, Combinatorics, Digital subscriber line, [INFO.INFO-TI] Computer Science [cs]/Image Processing [eess.IV], 010201 computation theory & mathematics, [INFO.INFO-TI]Computer Science [cs]/Image Processing [eess.IV], 0202 electrical engineering, electronic engineering, information engineering, Arithmetic function, Farey sequence, Digital geometry, 020201 artificial intelligence & image processing, Point (geometry), Mathematics
Abstract

Given a Digital Straight Line (DSL) of known characteristics (a,b,μ), we address the problem of computing the characteristics of any of its subsegments. We propose a new algorithm as a smart walk in the so called Farey Fan. We take profit of the fact that the Farey Fan of order n represents in a certain way all the digital segments of length n. The computation of the characteristics of a DSL subsegment is then equivalent to the localization of a point in the Farey Fan. Using fine arithmetical properties of the fan, we design a fast algorithm of theoretical complexity $\mathcal{O}(\log(n))$ where n is the length of the subsegment. Experiments show that our algorithm is faster than the one previously proposed by Said and Lachaud in [15,14] for "short" segments.

Published
2013

7. On digital plane preimage structure

Author

Florent Dupont, David Coeurjolly, Jean-Marc Chassery, Isabelle Sivignon, Fabien Feschet, Laboratoire d'InfoRmatique en Image et Systèmes d'information (LIRIS), Institut National des Sciences Appliquées de Lyon (INSA Lyon), Institut National des Sciences Appliquées (INSA)-Université de Lyon-Institut National des Sciences Appliquées (INSA)-Université de Lyon-Centre National de la Recherche Scientifique (CNRS)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École Centrale de Lyon (ECL), Université de Lyon-Université Lumière - Lyon 2 (UL2), Laboratoire de Logique, Algorithmique et Informatique (LLAIC1), Université d'Auvergne - Clermont-Ferrand I (UdA), Laboratoire des images et des signaux (LIS), Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique de Grenoble (INPG)-Université Joseph Fourier - Grenoble 1 (UJF), Université Lumière - Lyon 2 (UL2)-École Centrale de Lyon (ECL), Université de Lyon-Université de Lyon-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS), and Université Joseph Fourier - Grenoble 1 (UJF)-Institut National Polytechnique de Grenoble (INPG)-Centre National de la Recherche Scientifique (CNRS)

Subjects
Mathematics::Dynamical Systems, Applied Mathematics, Structure (category theory), Straight segment, Geometry, 0102 computer and information sciences, 02 engineering and technology, [INFO.INFO-CG]Computer Science [cs]/Computational Geometry [cs.CG], Nonlinear Sciences::Cellular Automata and Lattice Gases, 01 natural sciences, Digital plane, Dimension (vector space), 010201 computation theory & mathematics, [INFO.INFO-TI]Computer Science [cs]/Image Processing [eess.IV], 0202 electrical engineering, electronic engineering, information engineering, Discrete Mathematics and Combinatorics, Digital geometry, 020201 artificial intelligence & image processing, Mathematics
Abstract

In digital geometry, digital straightness is an important concept both for practical motivations and theoretical interests. Concerning the digital straightness in dimension 2, many digital straight line characterizations exist and the digital straight segment preimage is well known. In this article, we investigate the preimage associated to digital planes. More precisely, we present first structure theorems that describe the preimage of a digital plane. Furthermore, we present a bound on the number of preimage faces under some given hypotheses.

Published
2005

8. On Three Constrained Versions of the Digital Circular Arc Recognition Problem

Author

Isabelle Sivignon, Laure Tougne, Tristan Roussillon, Geometry Processing and Constrained Optimization (M2DisCo), Laboratoire d'InfoRmatique en Image et Systèmes d'information (LIRIS), Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Université de Lyon-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École Centrale de Lyon (ECL), Université de Lyon-Université Lumière - Lyon 2 (UL2)-Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Université Lumière - Lyon 2 (UL2), and Sivignon, Isabelle

Subjects
Mathematical optimization, Boundary (topology), 0102 computer and information sciences, 02 engineering and technology, Radius, 01 natural sciences, Arc (geometry), [INFO.INFO-TI] Computer Science [cs]/Image Processing [eess.IV], 010201 computation theory & mathematics, Simple (abstract algebra), [INFO.INFO-TI]Computer Science [cs]/Image Processing [eess.IV], 0202 electrical engineering, electronic engineering, information engineering, 020201 artificial intelligence & image processing, Center (algebra and category theory), Point (geometry), Algorithm, Digitization, MathematicsofComputing_DISCRETEMATHEMATICS, Mathematics
Abstract

International audience; This paper focuses on the on-line recognition of digital arcs. The main contribution is to propose a simple and linear algorithm for three subproblems: on-line recognition of digital arcs coming from the digitization of a disk having (i) a fixed radius, (ii) a boundary that con- tacts a fixed point and (iii) a center that belongs to a fixed straight line. Solving such subproblems is interesting in itself, but also for the recog- nition of digital arcs. Indeed the proposed algorithm can be used as an oracle in multidimensional search techniques or can be iteratively used in a naive manner. Moreover, since the algorithm is on-line, it is a means of segmenting digital curves in a very fast way.

Published
2009

9. Hierarchical Discrete Medial Axis for Sphere-Tree Construction

Author

David Coeurjolly, Alain Broutta, Isabelle Sivignon, Geometry Processing and Constrained Optimization (M2DisCo), Laboratoire d'InfoRmatique en Image et Systèmes d'information (LIRIS), Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Université de Lyon-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École Centrale de Lyon (ECL), Université de Lyon-Université Lumière - Lyon 2 (UL2)-Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Université Lumière - Lyon 2 (UL2), and Sivignon, Isabelle

Subjects
Quantitative Biology::Neurons and Cognition, Computer science, ComputingMethodologies_IMAGEPROCESSINGANDCOMPUTERVISION, Discrete geometry, 020207 software engineering, 0102 computer and information sciences, 02 engineering and technology, Topology, 01 natural sciences, Image synthesis, [INFO.INFO-TI] Computer Science [cs]/Image Processing [eess.IV], 010201 computation theory & mathematics, Medial axis, [INFO.INFO-TI]Computer Science [cs]/Image Processing [eess.IV], 0202 electrical engineering, electronic engineering, information engineering, Collision detection, ComputingMethodologies_COMPUTERGRAPHICS, Shape analysis (digital geometry)
Abstract

International audience; In discrete geometry, the Distance Transformation and the Medial Axis Extraction are classical tools for shape analysis. In this pa- per, we present a Hierarchical Discrete Medial Axis, based on a pyramidal representation of the object, in order to efficiently create a sphere-tree, which has many applications in collision detection or image synthesis.

Published
2009

10. What Does Digital Straightness Tell About Digital Convexity ?

Author

Laure Tougne, Isabelle Sivignon, Tristan Roussillon, Sivignon, Isabelle, Geometry Processing and Constrained Optimization (M2DisCo), Laboratoire d'InfoRmatique en Image et Systèmes d'information (LIRIS), Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Université de Lyon-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École Centrale de Lyon (ECL), Université de Lyon-Université Lumière - Lyon 2 (UL2)-Institut National des Sciences Appliquées de Lyon (INSA Lyon), and Université de Lyon-Université Lumière - Lyon 2 (UL2)

Subjects
Computer science, Regular polygon, Boundary (topology), 0102 computer and information sciences, 02 engineering and technology, Edge (geometry), 01 natural sciences, Convexity, Combinatorics, Set (abstract data type), [INFO.INFO-TI] Computer Science [cs]/Image Processing [eess.IV], 010201 computation theory & mathematics, [INFO.INFO-TI]Computer Science [cs]/Image Processing [eess.IV], TheoryofComputation_ANALYSISOFALGORITHMSANDPROBLEMCOMPLEXITY, 0202 electrical engineering, electronic engineering, information engineering, Digital geometry, 020201 artificial intelligence & image processing, Point (geometry), Segmentation, Algorithm
Abstract

International audience; The paper studies local convexity properties of parts of dig- ital boundaries. An online and linear-time algorithm is introduced for the decomposition of a digital boundary into convex and concave parts. In addition, other data are computed in the same time without any extra cost: the hull of each convex or concave part as well as the Bezout points of each edge of those hulls. The proposed algorithm involves well- understood algorithms: adding a point to the front or removing a point from the back of a digital straight segment and computing the set of maximal segments. The output of the algorithm is useful either for a polygonal representation of digital boundaries or for a segmentation into circular arcs.

Published
2009

11. Algorithms for Fast Digital Straight Segments Union

Author

Isabelle Sivignon, GIPSA - Architecture, Géométrie, Perception, Images, Gestes (GIPSA-AGPIG), Département Images et Signal (GIPSA-DIS), Grenoble Images Parole Signal Automatique (GIPSA-lab), Université Pierre Mendès France - Grenoble 2 (UPMF)-Université Stendhal - Grenoble 3-Université Joseph Fourier - Grenoble 1 (UJF)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Centre National de la Recherche Scientifique (CNRS)-Université Pierre Mendès France - Grenoble 2 (UPMF)-Université Stendhal - Grenoble 3-Université Joseph Fourier - Grenoble 1 (UJF)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Centre National de la Recherche Scientifique (CNRS)-Grenoble Images Parole Signal Automatique (GIPSA-lab), and Université Pierre Mendès France - Grenoble 2 (UPMF)-Université Stendhal - Grenoble 3-Université Joseph Fourier - Grenoble 1 (UJF)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Centre National de la Recherche Scientifique (CNRS)-Université Pierre Mendès France - Grenoble 2 (UPMF)-Université Stendhal - Grenoble 3-Université Joseph Fourier - Grenoble 1 (UJF)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Centre National de la Recherche Scientifique (CNRS)

Subjects
Logarithm, Digital straight segment, Digital geometry, 020207 software engineering, Union, 02 engineering and technology, Direct-sequence spread spectrum, [INFO.INFO-TI]Computer Science [cs]/Image Processing [eess.IV], 0202 electrical engineering, electronic engineering, information engineering, Arithmetic function, 020201 artificial intelligence & image processing, Arithmetic, Time complexity, Algorithm, Mathematics
Abstract

International audience; Given two Digital Straight Segments (DSS for short) of known minimal characteristics, we investigate the union of these DSSs: is it still a DSS ? If yes, what are its minimal characteristics ? We show that the problem is actually easy and can be solved in, at worst, logarithmic time using a state-of-the-art algorithm. We moreover propose a new algorithm of logarithmic worst-case complexity based on arithmetical properties. But when the two DSSs are connected, the time complexity of this algorithm is lowered to O(1) and experiments show that it outperforms the state-of-the art one in any case.

Published
2014

12. A Near-Linear Time Guaranteed Algorithm for Digital Curve Simplification Under the Fréchet Distance

Author

Isabelle Sivignon, GIPSA - Architecture, Géométrie, Perception, Images, Gestes (GIPSA-AGPIG), Département Images et Signal (GIPSA-DIS), Grenoble Images Parole Signal Automatique (GIPSA-lab), Université Pierre Mendès France - Grenoble 2 (UPMF)-Université Stendhal - Grenoble 3-Université Joseph Fourier - Grenoble 1 (UJF)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Centre National de la Recherche Scientifique (CNRS)-Université Pierre Mendès France - Grenoble 2 (UPMF)-Université Stendhal - Grenoble 3-Université Joseph Fourier - Grenoble 1 (UJF)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Centre National de la Recherche Scientifique (CNRS)-Grenoble Images Parole Signal Automatique (GIPSA-lab), Université Pierre Mendès France - Grenoble 2 (UPMF)-Université Stendhal - Grenoble 3-Université Joseph Fourier - Grenoble 1 (UJF)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Centre National de la Recherche Scientifique (CNRS)-Université Pierre Mendès France - Grenoble 2 (UPMF)-Université Stendhal - Grenoble 3-Université Joseph Fourier - Grenoble 1 (UJF)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Centre National de la Recherche Scientifique (CNRS), Debled-Rennesson, I., Domenjoud, E., Kerautret, B., Even, and P. (Eds.)

Subjects
Geographic information system, business.industry, Fréchet distance, 0102 computer and information sciences, 02 engineering and technology, 01 natural sciences, Maximum error, lcsh:QA75.5-76.95, Negative shift, Quality (physics), 010201 computation theory & mathematics, Polygonal chain, [INFO.INFO-TI]Computer Science [cs]/Image Processing [eess.IV], 0202 electrical engineering, electronic engineering, information engineering, 020201 artificial intelligence & image processing, lcsh:Electronic computers. Computer science, business, Algorithm, Time complexity, Mathematics
Abstract

International audience; In this paper, we propose an algorithm that, from a maximum error and a digital curve (4- or 8-connected), computes a simplification of the curve (a polygonal curve) such that the Fréchet distance between the original and the simplified curve is less than the error. The Fréchet distance is known to nicely measure the similarity between two curves. The algorithm we propose uses an approximation of the Fréchet distance, but a guarantee over the quality of the simplification is proved. Moreover, even if the theoretical complexity of the algorithm is in O(n log(n)), experiments show a linear behaviour in practice.

Published
2014

13. Droites et plans discrets

Author

Sivignon, Isabelle, Debled-Rennesson, Isabelle, Geometry Processing and Constrained Optimization (M2DisCo), Laboratoire d'InfoRmatique en Image et Systèmes d'information (LIRIS), Université Lumière - Lyon 2 (UL2)-École Centrale de Lyon (ECL), Université de Lyon-Université de Lyon-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS)-Université Lumière - Lyon 2 (UL2)-École Centrale de Lyon (ECL), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS), Applying Discrete Algorithms to Genomics and Imagery (ADAGIO), Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université Henri Poincaré - Nancy 1 (UHP)-Université Nancy 2-Institut National Polytechnique de Lorraine (INPL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université Henri Poincaré - Nancy 1 (UHP)-Université Nancy 2-Institut National Polytechnique de Lorraine (INPL)-Centre National de la Recherche Scientifique (CNRS), Coeurjolly David, Montanvert Annick, Chassery Jean-Marc, Sivignon, Isabelle, Coeurjolly David, Montanvert Annick, Chassery Jean-Marc, Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Université de Lyon-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École Centrale de Lyon (ECL), Université de Lyon-Université Lumière - Lyon 2 (UL2)-Institut National des Sciences Appliquées de Lyon (INSA Lyon), and Université de Lyon-Université Lumière - Lyon 2 (UL2)

Subjects
[INFO.INFO-CG] Computer Science [cs]/Computational Geometry [cs.CG], [INFO.INFO-TI] Computer Science [cs]/Image Processing [eess.IV], [INFO.INFO-TI]Computer Science [cs]/Image Processing [eess.IV], [INFO.INFO-CG]Computer Science [cs]/Computational Geometry [cs.CG]
Abstract

414 p. - ISBN 978-2-7462-1643-3

Published
2007

14. Polygonalisation et polyédrisation réversibles

Author

Sivignon, Isabelle, Sivignon, Isabelle, David Coeurjolly, Annick Montanvert, Jean-Marc Chassery, Geometry Processing and Constrained Optimization (M2DisCo), Laboratoire d'InfoRmatique en Image et Systèmes d'information (LIRIS), Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Université de Lyon-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École Centrale de Lyon (ECL), Université de Lyon-Université Lumière - Lyon 2 (UL2)-Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Université Lumière - Lyon 2 (UL2), David Coeurjolly, Annick Montanvert, and Jean-Marc Chassery

Subjects
[INFO.INFO-CG] Computer Science [cs]/Computational Geometry [cs.CG], [INFO.INFO-TI] Computer Science [cs]/Image Processing [eess.IV], [INFO.INFO-TI]Computer Science [cs]/Image Processing [eess.IV], [INFO.INFO-CG]Computer Science [cs]/Computational Geometry [cs.CG]
Published
2007

15. Minimal Decomposition of a Digital Surface into Digital Plane Segments is NP-Hard

Author

David Coeurjolly, Isabelle Sivignon, Geometry Processing and Constrained Optimization (M2DisCo), Laboratoire d'InfoRmatique en Image et Systèmes d'information (LIRIS), Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Université de Lyon-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École Centrale de Lyon (ECL), Université de Lyon-Université Lumière - Lyon 2 (UL2)-Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Université Lumière - Lyon 2 (UL2), and Sivignon, Isabelle

Subjects
Polynomial, Computer science, ComputerApplications_COMPUTERSINOTHERSYSTEMS, 0102 computer and information sciences, 02 engineering and technology, Decision problem, [INFO.INFO-CG]Computer Science [cs]/Computational Geometry [cs.CG], 01 natural sciences, Reduction (complexity), Digital plane, [INFO.INFO-CG] Computer Science [cs]/Computational Geometry [cs.CG], [INFO.INFO-TI] Computer Science [cs]/Image Processing [eess.IV], 010201 computation theory & mathematics, [INFO.INFO-TI]Computer Science [cs]/Image Processing [eess.IV], 0202 electrical engineering, electronic engineering, information engineering, Decomposition (computer science), 020201 artificial intelligence & image processing, Digital surface, Geometric modeling, Algorithm
Abstract

International audience; This paper deals with the complexity of the decomposition of a digital surface into digital plane segments (DPS for short). We prove that the decision problem (does there exist a decomposition with less than k DPS ?) is NP-complete, and thus that the optimisation problem (finding the minimal number of DPS) is NP-hard. The proof is based on a polynomial reduction of any instance of the well-known 3-SAT problem to an instance of the digital surface decomposition problem. A geometric model for the 3-SAT problem is proposed.

Published
2006

16. Reversible Polygonalization of a 3D Planar Discrete Curve: Application on Discrete Surfaces

Author

Jean-Marc Chassery, Isabelle Sivignon, Florent Dupont, Laboratoire d'InfoRmatique en Image et Systèmes d'information (LIRIS), Institut National des Sciences Appliquées de Lyon (INSA Lyon), Institut National des Sciences Appliquées (INSA)-Université de Lyon-Institut National des Sciences Appliquées (INSA)-Université de Lyon-Centre National de la Recherche Scientifique (CNRS)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École Centrale de Lyon (ECL), Université de Lyon-Université Lumière - Lyon 2 (UL2), Laboratoire des images et des signaux (LIS), Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique de Grenoble (INPG)-Université Joseph Fourier - Grenoble 1 (UJF), and Sivignon, Isabelle

Subjects
Surface (mathematics), Computer science, Discrete geometry, Geometry, 0102 computer and information sciences, 02 engineering and technology, Computer Science::Computational Geometry, Computational geometry, [INFO.INFO-CG]Computer Science [cs]/Computational Geometry [cs.CG], 01 natural sciences, Polyhedron, Transformation (function), Planar, [INFO.INFO-CG] Computer Science [cs]/Computational Geometry [cs.CG], [INFO.INFO-TI] Computer Science [cs]/Image Processing [eess.IV], 010201 computation theory & mathematics, Face (geometry), TheoryofComputation_ANALYSISOFALGORITHMSANDPROBLEMCOMPLEXITY, [INFO.INFO-TI]Computer Science [cs]/Image Processing [eess.IV], Polygon, 0202 electrical engineering, electronic engineering, information engineering, 020201 artificial intelligence & image processing, Algorithm, MathematicsofComputing_DISCRETEMATHEMATICS, ComputingMethodologies_COMPUTERGRAPHICS
Abstract

International audience; Reversible polyhedral modelling of discrete objects is an important issue to handle those objects. We propose a new algorithm to compute a polygonal face from a discrete planar face (a set of voxels belonging to a discrete plane). This transformation is reversible, i.e. the digitization of this polygon is exactly the discrete face. We show how a set of polygons modelling exactly a discrete surface can be computed thanks to this algorithm.

Published
2005

17. Discrete Surfaces Segmentation into Discrete Planes

Author

Isabelle Sivignon, Jean-Marc Chassery, Florent Dupont, Sivignon, Isabelle, Laboratoire d'InfoRmatique en Image et Systèmes d'information (LIRIS), Institut National des Sciences Appliquées de Lyon (INSA Lyon), Institut National des Sciences Appliquées (INSA)-Université de Lyon-Institut National des Sciences Appliquées (INSA)-Université de Lyon-Centre National de la Recherche Scientifique (CNRS)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École Centrale de Lyon (ECL), Université de Lyon-Université Lumière - Lyon 2 (UL2), Laboratoire des images et des signaux (LIS), and Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique de Grenoble (INPG)-Université Joseph Fourier - Grenoble 1 (UJF)

Subjects
Surface (mathematics), Computer science, Segmentation-based object categorization, Plane (geometry), ComputingMethodologies_IMAGEPROCESSINGANDCOMPUTERVISION, Discrete geometry, Scale-space segmentation, Class (philosophy), Image processing, 0102 computer and information sciences, 02 engineering and technology, [INFO.INFO-CG]Computer Science [cs]/Computational Geometry [cs.CG], 01 natural sciences, Combinatorics, [INFO.INFO-TI] Computer Science [cs]/Image Processing [eess.IV], [INFO.INFO-CG] Computer Science [cs]/Computational Geometry [cs.CG], 010201 computation theory & mathematics, [INFO.INFO-TI]Computer Science [cs]/Image Processing [eess.IV], Euclidean geometry, 0202 electrical engineering, electronic engineering, information engineering, 020201 artificial intelligence & image processing, Segmentation, Algorithm
Abstract

International audience; This paper is composed of two parts. In the first one, we present an analysis of existing discrete surface segmentation algorithms. We show that two classes of algorithms can actually be defined according to discrete surface and plane definitions. In the second part, we prove the link between the two classes presented. To do so, we propose a new labelling of the surface elements which leads to a segmentation algorithm of the first class that can be easily transformed into a segmentation algorithm of the second class.

Published
2004

18. Digital Plane Preimage Structure

Author

Florent Dupont, Isabelle Sivignon, Jean-Marc Chassery, Fabien Feschet, David Coeurjolly, Sivignon, Isabelle, Laboratoire d'InfoRmatique en Image et Systèmes d'information (LIRIS), Université Lumière - Lyon 2 (UL2)-École Centrale de Lyon (ECL), Université de Lyon-Université de Lyon-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS), Laboratoire de Logique, Algorithmique et Informatique (LLAIC1), Université d'Auvergne - Clermont-Ferrand I (UdA), Laboratoire des images et des signaux (LIS), Université Joseph Fourier - Grenoble 1 (UJF)-Institut National Polytechnique de Grenoble (INPG)-Centre National de la Recherche Scientifique (CNRS), Institut National des Sciences Appliquées de Lyon (INSA Lyon), Institut National des Sciences Appliquées (INSA)-Université de Lyon-Institut National des Sciences Appliquées (INSA)-Université de Lyon-Centre National de la Recherche Scientifique (CNRS)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École Centrale de Lyon (ECL), Université de Lyon-Université Lumière - Lyon 2 (UL2), and Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique de Grenoble (INPG)-Université Joseph Fourier - Grenoble 1 (UJF)

Subjects
Mathematics::Dynamical Systems, Dual transformation, Applied Mathematics, 010102 general mathematics, Structure (category theory), Straight segment, Geometry, 02 engineering and technology, [INFO.INFO-CG]Computer Science [cs]/Computational Geometry [cs.CG], Nonlinear Sciences::Cellular Automata and Lattice Gases, 01 natural sciences, Digital plane, Dimension (vector space), [INFO.INFO-TI] Computer Science [cs]/Image Processing [eess.IV], [INFO.INFO-CG] Computer Science [cs]/Computational Geometry [cs.CG], [INFO.INFO-TI]Computer Science [cs]/Image Processing [eess.IV], 0202 electrical engineering, electronic engineering, information engineering, Discrete Mathematics and Combinatorics, Digital geometry, 020201 artificial intelligence & image processing, 0101 mathematics, ComputingMilieux_MISCELLANEOUS, MathematicsofComputing_DISCRETEMATHEMATICS, Mathematics
Abstract

In digital geometry, digital straightness is an important concept both for practical motivations and theoretical interests. Concerning the digital straightness in dimension 2, many digital straight line characterizations exist and the digital straight segment preimage is well known. In this article, we investigate the preimage associated to digital planes. More precisely, we present structure theorems that describe the preimage of a digital plane. Furthermore, we present a bound on the number of preimage faces.

Published
2003

19. Faithful polygonal representation of the convex and concave parts of a digital curve

Author

Tristan Roussillon, Isabelle Sivignon, Geometry Processing and Constrained Optimization (M2DisCo), Laboratoire d'InfoRmatique en Image et Systèmes d'information (LIRIS), Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Université de Lyon-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École Centrale de Lyon (ECL), Université de Lyon-Université Lumière - Lyon 2 (UL2)-Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Université Lumière - Lyon 2 (UL2), GIPSA - Architecture, Géométrie, Perception, Images, Gestes (GIPSA-AGPIG), Département Images et Signal (GIPSA-DIS), Grenoble Images Parole Signal Automatique (GIPSA-lab), Université Stendhal - Grenoble 3-Université Pierre Mendès France - Grenoble 2 (UPMF)-Université Joseph Fourier - Grenoble 1 (UJF)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Centre National de la Recherche Scientifique (CNRS)-Université Stendhal - Grenoble 3-Université Pierre Mendès France - Grenoble 2 (UPMF)-Université Joseph Fourier - Grenoble 1 (UJF)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Centre National de la Recherche Scientifique (CNRS)-Grenoble Images Parole Signal Automatique (GIPSA-lab), and Université Stendhal - Grenoble 3-Université Pierre Mendès France - Grenoble 2 (UPMF)-Université Joseph Fourier - Grenoble 1 (UJF)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Centre National de la Recherche Scientifique (CNRS)-Université Stendhal - Grenoble 3-Université Pierre Mendès France - Grenoble 2 (UPMF)-Université Joseph Fourier - Grenoble 1 (UJF)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Centre National de la Recherche Scientifique (CNRS)

Subjects
Curve orientation, Convex set, Regular polygon, 0102 computer and information sciences, 02 engineering and technology, 01 natural sciences, Convexity, Combinatorics, 010201 computation theory & mathematics, Artificial Intelligence, [INFO.INFO-TI]Computer Science [cs]/Image Processing [eess.IV], Signal Processing, Polygon, Pattern recognition (psychology), 0202 electrical engineering, electronic engineering, information engineering, 020201 artificial intelligence & image processing, Point (geometry), Computer Vision and Pattern Recognition, Representation (mathematics), Software, Mathematics
Abstract

International audience; From results about digital convexity, we define a reversible polygon that faith- fully represents the maximal convex and concave parts of a digital curve. Such a polygon always exists and is unique in the general case. It is computed from a given digital curve in linear-time using well-known routines: adding a point at the front of a digital straight segment and removing a point from the back of a digital straight segment. It may helps to extract perceptually meaningful parts of shape outlines or lines.

Published
2011

20. Measure of Straight Lines for Digital Contour Analysis

Author

David Coeurjolly, Isabelle Sivignon, Geometry Processing and Constrained Optimization (M2DisCo), Laboratoire d'InfoRmatique en Image et Systèmes d'information (LIRIS), Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Université de Lyon-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École Centrale de Lyon (ECL), Université de Lyon-Université Lumière - Lyon 2 (UL2)-Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Université Lumière - Lyon 2 (UL2), ANR geodib, and ANR-06-BLAN-0225,GEODIB,Géométrie des Objets Discrets Bruités(2006)

Subjects
business.industry, Process (computing), 020207 software engineering, 02 engineering and technology, Computer Science::Computational Geometry, Measure (mathematics), Electronic, Optical and Magnetic Materials, Integral geometry, Set (abstract data type), Contour analysis, [INFO.INFO-TI]Computer Science [cs]/Image Processing [eess.IV], Euclidean geometry, 0202 electrical engineering, electronic engineering, information engineering, Digital geometry, 020201 artificial intelligence & image processing, Computer vision, Computer Vision and Pattern Recognition, Artificial intelligence, Electrical and Electronic Engineering, business, Software, Digitization, Mathematics
Abstract

International audience; In digital geometry, objects such as digital straight lines can be considered as equivalent classes of Euclidean straight lines with re- spect to a digitization process. This paper investigates the analysis of the set of straight lines whose digitization is a given digital straight seg- ment with the help of tools from integral geometry. After a definition of a measure on such sets, we illustrate several applications of it in digital geometry for contour analysis.

Published
2011

21. Measure of circularity for parts of digital boundaries and its fast computation

Author

Laure Tougne, Tristan Roussillon, Isabelle Sivignon, Laboratoire d'InfoRmatique en Image et Systèmes d'information (LIRIS), Institut National des Sciences Appliquées de Lyon (INSA Lyon), Institut National des Sciences Appliquées (INSA)-Université de Lyon-Institut National des Sciences Appliquées (INSA)-Université de Lyon-Centre National de la Recherche Scientifique (CNRS)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École Centrale de Lyon (ECL), Université de Lyon-Université Lumière - Lyon 2 (UL2), and ANR-06-BLAN-0225,GEODIB,Géométrie des Objets Discrets Bruités(2006)

Subjects
Computation, Digital data, Boundary (topology), Discrete geometry, 0102 computer and information sciences, 02 engineering and technology, Computational geometry, 01 natural sciences, Measure (mathematics), 010201 computation theory & mathematics, Artificial Intelligence, [INFO.INFO-TI]Computer Science [cs]/Image Processing [eess.IV], Signal Processing, 0202 electrical engineering, electronic engineering, information engineering, Digital geometry, 020201 artificial intelligence & image processing, Digital signal, Computer Vision and Pattern Recognition, Algorithm, Software, Mathematics
Abstract

International audience; This paper focuses on the design of an effective method that computes the measure of circularity of a part of a digital boundary. An existing circularity measure of a set of discrete points, which is used in computational metrology, is extended to the case of parts of digital boundaries. From a single digital boundary, two sets of points are extracted so that the circularity measure computed from these sets is representative of the circularity of the digital boundary. Therefore, the computation consists of two steps. First, the inner and outer sets of points are extracted from the input part of a digital boundary using digital geometry tools. Next, the circularity measure of these sets is computed using classical tools of computational geometry. It is proved that the algorithm is linear in time in the case of convex parts thanks to the specificity of digital data, and is in O(n log n) otherwise. Experiments done on synthetic and real images illustrate the interest of the properties of the circularity measure.

Published
2010

22. Measure of Straight Lines and its Applications in Digital Geometry

Author

Coeurjolly, David, Sivignon, Isabelle, Geometry Processing and Constrained Optimization (M2DisCo), Laboratoire d'InfoRmatique en Image et Systèmes d'information (LIRIS), Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Université de Lyon-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École Centrale de Lyon (ECL), Université de Lyon-Université Lumière - Lyon 2 (UL2)-Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Université Lumière - Lyon 2 (UL2), ANR-06-BLAN-0225,GEODIB,Géométrie des Objets Discrets Bruités(2006), Coeurjolly, David, and Programme 'blanc' - Géométrie des Objets Discrets Bruités - - GEODIB2006 - ANR-06-BLAN-0225 - BLANC - VALID

Subjects
[INFO.INFO-TI] Computer Science [cs]/Image Processing [eess.IV], [INFO.INFO-TI]Computer Science [cs]/Image Processing [eess.IV], Computer Science::Computational Geometry
Abstract

International audience; In digital geometry, objects such as digital straight lines can be considered as equivalent classes of Euclidean straight lines with re- spect to a digitization process. This paper investigates the analysis of the set of straight lines whose digitization is a given digital straight seg- ment with the help of tools from integral geometry. After a definition of a measure on such sets, we illustrate several applications of it in digital geometry.

Published
2009

23. Automatic computation of pebble roundness using digital imagery and discrete geometry

Author

Tristan Roussillon, Hervé Piégay, Laure Tougne, Franck Lavigne, Isabelle Sivignon, Geometry Processing and Constrained Optimization (M2DisCo), Laboratoire d'InfoRmatique en Image et Systèmes d'information (LIRIS), Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Université de Lyon-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École Centrale de Lyon (ECL), Université de Lyon-Université Lumière - Lyon 2 (UL2)-Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Université Lumière - Lyon 2 (UL2), Environnement Ville Société (EVS), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Université de Lyon-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS)-École nationale supérieure d'architecture de Lyon (ENSAL)-École des Mines de Saint-Étienne (Mines Saint-Étienne MSE), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-École Nationale des Travaux Publics de l'État (ENTPE)-Université Jean Monnet [Saint-Étienne] (UJM)-Université Jean Moulin - Lyon 3 (UJML), Université de Lyon-Université Lumière - Lyon 2 (UL2)-École normale supérieure - Lyon (ENS Lyon), Laboratoire de géographie physique : Environnements Quaternaires et Actuels (LGP), Université Paris 1 Panthéon-Sorbonne (UP1)-Université Paris-Est Créteil Val-de-Marne - Paris 12 (UPEC UP12)-Centre National de la Recherche Scientifique (CNRS), ANR-06-BLAN-0225,GEODIB,Géométrie des Objets Discrets Bruités(2006), Université Lumière - Lyon 2 (UL2)-École Centrale de Lyon (ECL), Université de Lyon-Université de Lyon-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS)-Université Lumière - Lyon 2 (UL2)-École Centrale de Lyon (ECL), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS), École normale supérieure - Lyon (ENS Lyon)-École des Mines de Saint-Étienne (Mines Saint-Étienne MSE), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Université Lumière - Lyon 2 (UL2)-Université Jean Moulin - Lyon 3 (UJML), Université de Lyon-Université de Lyon-Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université Jean Monnet [Saint-Étienne] (UJM)-École Nationale des Travaux Publics de l'État (ENTPE)-École nationale supérieure d'architecture de Lyon (ENSAL)-Centre National de la Recherche Scientifique (CNRS), Environnement, Ville, Société (EVS), École normale supérieure de Lyon (ENS de Lyon)-École des Mines de Saint-Étienne (Mines Saint-Étienne MSE), and Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université Jean Monnet - Saint-Étienne (UJM)-École Nationale des Travaux Publics de l'État (ENTPE)-École nationale supérieure d'architecture de Lyon (ENSAL)-Centre National de la Recherche Scientifique (CNRS)

Subjects
010504 meteorology & atmospheric sciences, Computer science, Computation, Discrete geometry, Sedimentary particle, 010502 geochemistry & geophysics, 01 natural sciences, Measure (mathematics), Digital image, symbols.namesake, Bedload transport, Computers in Earth Sciences, River continuum, 0105 earth and related environmental sciences, Hydrology, Data processing, Ground truth, [SHS.GEO]Humanities and Social Sciences/Geography, Physical abrasion, Roundness (object), Fourier transform, [INFO.INFO-TI]Computer Science [cs]/Image Processing [eess.IV], symbols, Roundness, Algorithm, Information Systems, Shape description
Abstract

International audience; The shape of sedimentary particles is an important property, from which geographical hypotheses related to abrasion, distance of transport, river behavior, etc. can be formulated. In this paper, we use digital image analysis, especially discrete geometry, to automatically compute some shape parameters such as roundness i.e. a measure of how much the corners and edges of a particle have been worn away. In contrast to previous works in which traditional digital images analysis techniques such as Fourier transform (Diepenbroek et al., 1992, Sedimentology, 39) are used, we opted for a discrete geometry approach that allowed us to implement Wadell's original index (Wadell, 1932, Journal of Geology, 40) which is known to be more accurate, but more time consuming to implement in the field (Pissart et al., 1998, Geomorphologie: relief, processus, environnement, 3). Our implementation of Wadell's original index is highly correlated (92%) with the round- ness classes of Krumbein's chart, used as a ground-truth (Krumbein, 1941, Journal of Sedimentary Petrology, 11, 2). In addition, we show that other geometrical parameters, which are easier to compute, can be used to provide good approximations of roundness. We also used our shape parameters to study a set of pebbles digital images taken from the Progo basin river network (Indonesia). The results we obtained are in agreement with previous works and open new possibilities for geomorphologists thanks to automatic computation.

Published
2009

24. Minimum Decomposition of a Digital Surface into Digital Plane Segments is NP-Hard

Author

Isabelle Sivignon, David Coeurjolly, Geometry Processing and Constrained Optimization (M2DisCo), Laboratoire d'InfoRmatique en Image et Systèmes d'information (LIRIS), Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Université de Lyon-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École Centrale de Lyon (ECL), Université de Lyon-Université Lumière - Lyon 2 (UL2)-Institut National des Sciences Appliquées de Lyon (INSA Lyon), and Université de Lyon-Université Lumière - Lyon 2 (UL2)

Subjects
Polynomial, Optimization problem, ComputerApplications_COMPUTERSINOTHERSYSTEMS, 0102 computer and information sciences, 02 engineering and technology, Digital object, [INFO.INFO-CG]Computer Science [cs]/Computational Geometry [cs.CG], 01 natural sciences, Combinatorics, Reduction (complexity), 0202 electrical engineering, electronic engineering, information engineering, Decomposition (computer science), Discrete Mathematics and Combinatorics, Boolean expression, Mathematics, Discrete mathematics, Decomposition, Applied Mathematics, Complexity, Decision problem, Digital plane, 010201 computation theory & mathematics, [INFO.INFO-TI]Computer Science [cs]/Image Processing [eess.IV], 020201 artificial intelligence & image processing, Geometric modeling
Abstract

International audience; This paper deals with the complexity of the decomposition of a digital surface into digital plane segments (DPS for short). We prove that the decision problem (does there exist a decomposition with less than $\lambda$ DPS ?) is NP-complete, and thus that the optimisation problem (finding the minimum number of DPS) is NP-hard. The proof is based on a polynomial reduction of any instance of the well-known 3-SAT problem to an instance of the digital surface decomposition problem. A geometric model for the 3-SAT problem is proposed.

Published
2008

25. Finding a Minimum Medial Axis of a Discrete Shape is NP-hard

Author

David Coeurjolly, Isabelle Sivignon, Jérôme Hulin, Geometry Processing and Constrained Optimization (M2DisCo), Laboratoire d'InfoRmatique en Image et Systèmes d'information (LIRIS), Université Lumière - Lyon 2 (UL2)-École Centrale de Lyon (ECL), Université de Lyon-Université de Lyon-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS)-Université Lumière - Lyon 2 (UL2)-École Centrale de Lyon (ECL), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS), Laboratoire d'informatique Fondamentale de Marseille - UMR 6166 (LIF), Université de la Méditerranée - Aix-Marseille 2-Université de Provence - Aix-Marseille 1-Centre National de la Recherche Scientifique (CNRS), Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Université de Lyon-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École Centrale de Lyon (ECL), Université de Lyon-Université Lumière - Lyon 2 (UL2)-Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Université Lumière - Lyon 2 (UL2), and Coeurjolly, David

Subjects
General Computer Science, Bounded approximation algorithm, 0102 computer and information sciences, 02 engineering and technology, 01 natural sciences, Theoretical Computer Science, Combinatorics, Set (abstract data type), Medial axis, Completeness (order theory), 0202 electrical engineering, electronic engineering, information engineering, Representation (mathematics), Mathematics, Discrete mathematics, Straight skeleton, Approximation algorithm, Minimum medial axis, NP-completeness, Euclidean distance, Computer Science::Graphics, [INFO.INFO-TI] Computer Science [cs]/Image Processing [eess.IV], 010201 computation theory & mathematics, Bounded function, [INFO.INFO-TI]Computer Science [cs]/Image Processing [eess.IV], 020201 artificial intelligence & image processing, Computer Science(all)
Abstract

International audience; The medial axis is a classical representation of digital objects widely used in many applications. However, such a set of balls may not be optimal: subsets of the medial axis may exist without changing the reversivility of the input shape representation. In this article, we first prove that finding a minimum medial axis is an NP-hard problem for the Euclidean distance. Then, we compare two algorithms which compute an approximation of the minimum medial axis, one of them providing bounded approximation results.

Published
2008

26. Computation of Binary Objects Sides Number using Discrete Geometry, Application to Automatic Pebbles Shape Analysis

Author

Tristan Roussillon, Laure Tougne, Isabelle Sivignon, Geometry Processing and Constrained Optimization (M2DisCo), Laboratoire d'InfoRmatique en Image et Systèmes d'information (LIRIS), Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Université de Lyon-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École Centrale de Lyon (ECL), Université de Lyon-Université Lumière - Lyon 2 (UL2)-Institut National des Sciences Appliquées de Lyon (INSA Lyon), and Université de Lyon-Université Lumière - Lyon 2 (UL2)

Subjects
[INFO.INFO-TI]Computer Science [cs]/Image Processing [eess.IV], 0202 electrical engineering, electronic engineering, information engineering, 020207 software engineering, 020201 artificial intelligence & image processing, 02 engineering and technology, [INFO.INFO-CG]Computer Science [cs]/Computational Geometry [cs.CG]
Abstract

International audience; We are working in collaboration with geographers to study a set of pebbles digital images. Among the features geographers want to get automatically, pebble sides number is intuitively defined as shown in Fig 1. It is merely computed after a thick polygonalisation of pebble contour. We propose an incremental and linear algorithm, free of restrictive hypothesis, which relies on previous works of Debled et al. [DRFRD05, DRFRD06, DRRRD05]. We give some results on synthetical and real images.

Published
2007

27. Optimization Schemes for the Reversible Discrete Volume Polyhedrization Using Marching Cubes Simplification

Author

Isabelle Sivignon, David Coeurjolly, Florent Dupont, Laurent Jospin, Geometry Processing and Constrained Optimization (M2DisCo), Laboratoire d'InfoRmatique en Image et Systèmes d'information (LIRIS), Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Université de Lyon-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École Centrale de Lyon (ECL), Université de Lyon-Université Lumière - Lyon 2 (UL2)-Institut National des Sciences Appliquées de Lyon (INSA Lyon), and Université de Lyon-Université Lumière - Lyon 2 (UL2)

Subjects
Binary Object, Marching cubes, Discretization, Computer science, ComputingMethodologies_IMAGEPROCESSINGANDCOMPUTERVISION, Discrete geometry, 0102 computer and information sciences, 02 engineering and technology, Topology, 01 natural sciences, Marching tetrahedra, Polyhedron, 010201 computation theory & mathematics, [INFO.INFO-TI]Computer Science [cs]/Image Processing [eess.IV], Isosurface, Euclidean geometry, 0202 electrical engineering, electronic engineering, information engineering, 020201 artificial intelligence & image processing, Cube, Algorithm, ComputingMethodologies_COMPUTERGRAPHICS
Abstract

International audience; The aim of this article is to present a reversible and topologically correct construction of a polyhedron from a binary object. The proposed algorithm is based on a Marching Cubes (MC for short) surface, a digital plane segmentation of the binary object surface and an optimization step to simplify the MC surface using the segmentation information.

Published
2006

28. Discrete analytical curve reconstruction without patches

Author

Rodolphe Breton, Eric Andres, Florent Dupont, Isabelle Sivignon, Laboratoire d'InfoRmatique en Image et Systèmes d'information (LIRIS), Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Université de Lyon-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École Centrale de Lyon (ECL), Université de Lyon-Université Lumière - Lyon 2 (UL2), SIGNAL-IMAGE-COMMUNICATION (SIC), Université de Poitiers-Centre National de la Recherche Scientifique (CNRS), and Deutsches Forschungszentrum für Künstliche Intelligenz GmbH = German Research Center for Artificial Intelligence (DFKI)

Subjects
Marching cubes, Pixel, Order (ring theory), 020207 software engineering, 02 engineering and technology, computer.software_genre, Topology, [INFO.INFO-CG]Computer Science [cs]/Computational Geometry [cs.CG], law.invention, Invertible matrix, Analytic geometry, Voxel, law, [INFO.INFO-TI]Computer Science [cs]/Image Processing [eess.IV], Signal Processing, Euclidean geometry, 0202 electrical engineering, electronic engineering, information engineering, 020201 artificial intelligence & image processing, Computer Vision and Pattern Recognition, Algorithm, computer, Mathematics, Standard model (cryptography)
Abstract

International audience; Invertible Euclidean reconstruction methods without patches for 2D and 3D discrete curves are proposed. From a discrete 4-connected curve in 2D, or 6-connected curve in 3D, the proposed algorithms compute a polygonal line which digitization with the standard model is equal to all the pixels or voxels of the curve. The framework of this method is the discrete analytical geometry and parameter spaces are used in order to simplify the algorithms. Moreover, the reconstructed polyline is more compact than classical methods such as the Marching Cubes.

Published
2005

29. Digital intersections: minimal carrier, connectivity and periodicity properties

Author

Jean-Marc Chassery, Florent Dupont, Isabelle Sivignon, Laboratoire d'InfoRmatique en Image et Systèmes d'information (LIRIS), Institut National des Sciences Appliquées de Lyon (INSA Lyon), Institut National des Sciences Appliquées (INSA)-Université de Lyon-Institut National des Sciences Appliquées (INSA)-Université de Lyon-Centre National de la Recherche Scientifique (CNRS)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École Centrale de Lyon (ECL), Université de Lyon-Université Lumière - Lyon 2 (UL2), Laboratoire des images et des signaux (LIS), and Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique de Grenoble (INPG)-Université Joseph Fourier - Grenoble 1 (UJF)

Subjects
Intersection curve, Line segment intersection, 0102 computer and information sciences, 02 engineering and technology, Parallel, Topology, [INFO.INFO-CG]Computer Science [cs]/Computational Geometry [cs.CG], 01 natural sciences, Computer Graphics and Computer-Aided Design, Intersection, 010201 computation theory & mathematics, Line–line intersection, Modeling and Simulation, [INFO.INFO-TI]Computer Science [cs]/Image Processing [eess.IV], Euclidean geometry, 0202 electrical engineering, electronic engineering, information engineering, Arithmetic function, Digital geometry, Mathematics::Metric Geometry, 020201 artificial intelligence & image processing, Geometry and Topology, Software, Mathematics
Abstract

International audience; Digital geometry is very different from Euclidean geometry in many ways and the intersection of two digital lines or planes is often used to illustrate those differences. Nevertheless, while digital lines and planes are widely studied in many areas, very few works deal with the intersection of such objects. In this paper, we investigate the geometrical and arithmetical properties of those objects. More precisely, we give some new results about the connectivity, periodicity, and minimal parameters of the intersection of two digital lines or planes.

Published
2004

30. Towards an Invertible Euclidean Reconstruction of a Discrete Object

Author

Eric Andres, Rodolphe Breton, Florent Dupont, Isabelle Sivignon, SIGNAL-IMAGE-COMMUNICATION (SIC), Université de Poitiers-Centre National de la Recherche Scientifique (CNRS), Laboratoire d'InfoRmatique en Image et Systèmes d'information (LIRIS), Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Université de Lyon-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École Centrale de Lyon (ECL), and Université de Lyon-Université Lumière - Lyon 2 (UL2)

Subjects
Marching cubes, Computer science, Discrete geometry, 020207 software engineering, Image processing, 02 engineering and technology, Extension (predicate logic), [INFO.INFO-CG]Computer Science [cs]/Computational Geometry [cs.CG], Topology, law.invention, Algebra, Analytic geometry, Invertible matrix, law, [INFO.INFO-TI]Computer Science [cs]/Image Processing [eess.IV], Euclidean geometry, 0202 electrical engineering, electronic engineering, information engineering, 020201 artificial intelligence & image processing, Cube, Surface reconstruction
Abstract

International audience; An invertible Euclidean reconstruction method for a 2D curve is proposed. Hints on an extension to 3D are provided. The framework of this method is the discrete analytical geometry. The reconstruction result is more compact than classical methods such as the Marching Cubes. The notions of discrete cups and patches are introduced. patches are introduced.

Published
2003

31. Decomposition of a 3D Discrete Object Surface

Author

Isabelle Sivignon, Florent Dupont, Jean-Marc Chassery, Laboratoire d'InfoRmatique en Image et Systèmes d'information (LIRIS), Institut National des Sciences Appliquées de Lyon (INSA Lyon), Institut National des Sciences Appliquées (INSA)-Université de Lyon-Institut National des Sciences Appliquées (INSA)-Université de Lyon-Centre National de la Recherche Scientifique (CNRS)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École Centrale de Lyon (ECL), Université de Lyon-Université Lumière - Lyon 2 (UL2), Laboratoire des images et des signaux (LIS), Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique de Grenoble (INPG)-Université Joseph Fourier - Grenoble 1 (UJF), and Sivignon, Isabelle

Subjects
[INFO.INFO-CG] Computer Science [cs]/Computational Geometry [cs.CG], [INFO.INFO-TI] Computer Science [cs]/Image Processing [eess.IV], TheoryofComputation_ANALYSISOFALGORITHMSANDPROBLEMCOMPLEXITY, [INFO.INFO-TI]Computer Science [cs]/Image Processing [eess.IV], [INFO.INFO-CG]Computer Science [cs]/Computational Geometry [cs.CG], ComputingMethodologies_COMPUTERGRAPHICS
Abstract

International audience; This paper deals with the polyhedrization of discrete volumes. The aim is to do a reversible transformation from a discrete volume to a Euclidean polyhedron, i.e. such that the discretization of the Euclidean volume is exactly the initial discrete volume. We propose a new polynomial algorithm to split the surface of any discrete volume into pieces of naive discrete planes with well-defined shape properties, and present a study of the time complexity as well as a study of the influence of the voxel tracking order during the execution of this algorithm.

32. From digital plane segmentation to polyhedral representation

Author

David Coeurjolly, Isabelle Sivignon, Coeurjolly, David, Laboratoire d'InfoRmatique en Image et Systèmes d'information (LIRIS), Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Université de Lyon-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École Centrale de Lyon (ECL), and Université de Lyon-Université Lumière - Lyon 2 (UL2)

Subjects
Surface (mathematics), Process (computing), 0102 computer and information sciences, 02 engineering and technology, Construct (python library), Object (computer science), 01 natural sciences, Visualization, Combinatorics, Polyhedron, [INFO.INFO-TI] Computer Science [cs]/Image Processing [eess.IV], 010201 computation theory & mathematics, TheoryofComputation_ANALYSISOFALGORITHMSANDPROBLEMCOMPLEXITY, [INFO.INFO-TI]Computer Science [cs]/Image Processing [eess.IV], Euclidean geometry, 0202 electrical engineering, electronic engineering, information engineering, Mathematics::Metric Geometry, 020201 artificial intelligence & image processing, Segmentation, Algorithm, MathematicsofComputing_DISCRETEMATHEMATICS, Mathematics
Abstract

Many applications, manipulation or just visualization of discrete volumes are time consuming problems. The general idea to solve these difficulties is to transform, in a reversible way, those volumes into Euclidean polyhedra. A first step of this process consists in a Digital Plane Segmentation of the discrete object's surface. In this paper, we present an algorithm to construct an optimal, in the number of vertices, discrete volume polyhedral representation (i.e. vertices and faces adjacencies).

33. Duality and geometry straightness, characterization and envelope

Author

David Coeurjolly, Isabelle Sivignon, Jean-Marc Chassery, Coeurjolly, David, Laboratoire des images et des signaux (LIS), Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique de Grenoble (INPG)-Université Joseph Fourier - Grenoble 1 (UJF), Geometry Processing and Constrained Optimization (M2DisCo), Laboratoire d'InfoRmatique en Image et Systèmes d'information (LIRIS), Institut National des Sciences Appliquées de Lyon (INSA Lyon), Institut National des Sciences Appliquées (INSA)-Université de Lyon-Institut National des Sciences Appliquées (INSA)-Université de Lyon-Centre National de la Recherche Scientifique (CNRS)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École Centrale de Lyon (ECL), Université de Lyon-Université Lumière - Lyon 2 (UL2)-Institut National des Sciences Appliquées de Lyon (INSA Lyon), and Université de Lyon-Université Lumière - Lyon 2 (UL2)

Subjects
Computer science, Computation, 010102 general mathematics, ComputingMethodologies_IMAGEPROCESSINGANDCOMPUTERVISION, Duality (optimization), Discrete geometry, Image processing, Geometry, 02 engineering and technology, Convex polygon, Computational geometry, 01 natural sciences, Hough transform, law.invention, [INFO.INFO-TI] Computer Science [cs]/Image Processing [eess.IV], law, [INFO.INFO-TI]Computer Science [cs]/Image Processing [eess.IV], Computer Science::Computer Vision and Pattern Recognition, 0202 electrical engineering, electronic engineering, information engineering, 020201 artificial intelligence & image processing, 0101 mathematics, Envelope (mathematics), Focus (optics)
Abstract

International audience; Duality applied to geometrical problems is widely used in many applications in computer vision or computational geometry. A classical example is the Hough Transform to detect linear structures in images. In this paper, we focus on two kinds of duality/polarity applied to geometrical problems: digital straightness detection and envelope computation.

34. Generation and Recognition of Digital Plane using Multi-dimensional Continued Fractions

Author

Thomas Fernique, Arithmétique informatique (ARITH), Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier (LIRMM), Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM), and David Coeurjolly and Isabelle Sivignon and Laure Tougne and Florent Dupont

Subjects
Discrete mathematics, digital plane recognition, continued fractions, 0102 computer and information sciences, 02 engineering and technology, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], Brun algorithm, 01 natural sciences, Connection (mathematics), Hyperplane, Chain (algebraic topology), 010201 computation theory & mathematics, [INFO.INFO-TI]Computer Science [cs]/Image Processing [eess.IV], Pattern recognition (psychology), 0202 electrical engineering, electronic engineering, information engineering, Multi dimensional, 020201 artificial intelligence & image processing, generalized substitution, Mathematics
Abstract

International audience; This paper extends, in a multi-dimensional framework, pattern recognition technics for generation or recognition of digital lines. More precisely, we show how the connection between chain codes of digital lines and continued fractions can be generalized by a connection between tilings and multi-dimensional continued fractions. This leads to a new approach for generating and recognizing digital hyperplanes.

Published
2008

Catalog

Books, media, physical & digital resources
See catalog results