Nicolas Normand Jeanpierre Guédon Florent Autrusseau (Eds.) 7 4 Discrete Geometry 6 9 S C for Computer Imagery N L 19th IAPR International Conference, DGCI 2016 Nantes, France, April 18–20, 2016 Proceedings 123 Lecture Notes in Computer Science 9647 Commenced Publication in 1973 Founding and Former Series Editors: Gerhard Goos, Juris Hartmanis, and Jan van Leeuwen Editorial Board David Hutchison Lancaster University, Lancaster, UK Takeo Kanade Carnegie Mellon University, Pittsburgh, PA, USA Josef Kittler University of Surrey, Guildford, UK Jon M. Kleinberg Cornell University, Ithaca, NY, USA Friedemann Mattern ETH Zurich, Zürich, Switzerland John C. Mitchell Stanford University, Stanford, CA, USA Moni Naor Weizmann Institute of Science, Rehovot, Israel C. Pandu Rangan Indian Institute of Technology, Madras, India Bernhard Steffen TU Dortmund University, Dortmund, Germany Demetri Terzopoulos University of California, Los Angeles, CA, USA Doug Tygar University of California, Berkeley, CA, USA Gerhard Weikum Max Planck Institute for Informatics, Saarbrücken, Germany More information about this series at http://www.springer.com/series/7412 é Nicolas Normand Jeanpierre Gu don (cid:129) Florent Autrusseau (Eds.) Discrete Geometry for Computer Imagery 19th IAPR International Conference, DGCI 2016 – Nantes, France, April 18 20, 2016 Proceedings 123 Editors NicolasNormand Florent Autrusseau IRCCyN IRCCyN University of Nantes University of Nantes Nantes Nantes France France Jeanpierre Guédon IRCCyN University of Nantes Nantes France ISSN 0302-9743 ISSN 1611-3349 (electronic) Lecture Notesin Computer Science ISBN 978-3-319-32359-6 ISBN978-3-319-32360-2 (eBook) DOI 10.1007/978-3-319-32360-2 LibraryofCongressControlNumber:2016935975 LNCSSublibrary:SL6–ImageProcessing,ComputerVision,PatternRecognition,andGraphics ©SpringerInternationalPublishingSwitzerland2016 Thisworkissubjecttocopyright.AllrightsarereservedbythePublisher,whetherthewholeorpartofthe material is concerned, specifically the rights of translation, reprinting, reuse of illustrations, recitation, broadcasting, reproduction on microfilms or in any other physical way, and transmission or information storageandretrieval,electronicadaptation,computersoftware,orbysimilarordissimilarmethodologynow knownorhereafterdeveloped. Theuseofgeneraldescriptivenames,registerednames,trademarks,servicemarks,etc.inthispublication doesnotimply,evenintheabsenceofaspecificstatement,thatsuchnamesareexemptfromtherelevant protectivelawsandregulationsandthereforefreeforgeneraluse. Thepublisher,theauthorsandtheeditorsaresafetoassumethattheadviceandinformationinthisbookare believedtobetrueandaccurateatthedateofpublication.Neitherthepublishernortheauthorsortheeditors give a warranty, express or implied, with respect to the material contained herein or for any errors or omissionsthatmayhavebeenmade. Printedonacid-freepaper ThisSpringerimprintispublishedbySpringerNature TheregisteredcompanyisSpringerInternationalPublishingAGSwitzerland Preface Following DGCI 2014 held in Siena, Italy, DGCI 2016, the 19th in a series of inter- nationalconferencesonDiscreteGeometryforComputerImagery,washeldinNantes, France, April 18–20, 2016. DGCI 2016 attracted a good number of research contri- butionsfromacademicandresearchinstitutionsinourfield.Atotalof51paperswere submittedfromallovertheword.Afterthereviewingprocess,32paperswereaccepted with22fororalpresentationand10forposterpresentation,allinasingle-tracksession. Three international well-known speakers were invited for specific lectures: Matthias Beck (San Francisco State University), Hugues Talbot (ESIEE Paris), and Jacques- Olivier Lachaud (Université Savoie Mont Blanc). We are pleased that DGCI was held under the sponsorship of the International AssociationofPatternRecognition(IAPR).Forthefirsttime,DGCIalsohadthehonor of producing a special issue of the Journal of Mathematical Imaging and Vision. We would like to thank all contributors, the invited speakers, all reviewers, and members of the Steering Committees, and all the people who made this conference happen. We are grateful to our financial support institutions—the Region Pays-de-la- Loire, Nantes Métropole, the University of Nantes, the CNRS, and Polytech Nantes. We also thank our industry support: Rozo Systems and Keosys. Last,butnotleast,wethankalltheparticipantsandhopethateveryonefoundgreat interestintheDGCI2016programandalsohadaverygoodtimeinourcityofNantes. April 2016 Nicolas Normand Jeanpierre Guédon Florent Autrusseau Organization Nicolas Normand IRCCyN, University of Nantes, France Jeanpierre Guédon IRCCyN, University of Nantes, France Florent Autrusseau IRCCyN, University of Nantes, France Program Chairs Nicolas Normand IRCCyN, University of Nantes, France Jeanpierre Guédon IRCCyN, University of Nantes, France Florent Autrusseau IRCCyN, University of Nantes, France David Coeurjolly LIRIS, CNRS, Lyon, France Program Committee Joost Batenburg CWI, Amsterdam, The Netherlands Valerie Berthé LIAFA, CNRS, Paris, France Gilles Bertrand LIGM, ESIEE Paris, Noisy-le-Grand, France Isabelle Bloch LTCI, Telecom ParisTech, Paris, France Sara Brunetti University of Siena, Italy Michel Couprie LIGM, ESIEE Paris, Noisy-le-Grand, France Guillaume Damiand LIRIS, CNRS, Lyon, France Laurent Fuchs XLIM, University of Poitiers, France Yan Gerard ISIT, Auvergne University, France Rocio Gonzalez-Diaz University of Seville, Spain Yukiko Kenmochi LIGM, University of Paris-Est, France Bertrand Kerautret Loria, University of Lorraine, France Christer Kiselman Uppsala University, Sweden Walter Kropatsch Vienna University of Technology, Austria Xavier Provençal LAMA, University Savoie Mont Blanc, France Robin Strand Centre for Image Analysis, Uppsala, Sweden Imants Svalbe Monash University, Melbourne, Australia Edouard Thiel LIF, University of Aix-Marseille, France Contents Invited Talks Convergent Geometric Estimators with Digital Volume and Surface Integrals. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 Jacques-Olivier Lachaud Discrete Calculus, Optimisation and Inverse Problems in Imaging. . . . . . . . . 18 Hugues Talbot Combinatorial Tools Number of Words Characterizing Digital Balls on the Triangular Tiling. . . . . 31 Benedek Nagy Generation of Digital Planes Using Generalized Continued-Fractions Algorithms. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 Damien Jamet, Nadia Lafrenière, and Xavier Provençal Discretization Curve Digitization Variability. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59 Étienne Baudrier and Loïc Mazo Discretizations of Isometries. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71 Pierre-Antoine Guihéneuf Discrete Tomography A Tomographical Interpretation of a Sufficient Condition on h-Graphical Sequences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95 Srecko Brlek and Andrea Frosini Geometrical Characterization of the Uniqueness Regions Under Special Sets of Three Directions in Discrete Tomography. . . . . . . . . . 105 Paolo Dulio, Andrea Frosini, and Silvia M.C. Pagani A Comparison of Some Methods for Direct 2D Reconstruction from Discrete Projected Views. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117 Preeti Gopal, Ajit Rajwade, Sharat Chandran, and Imants Svalbe VIII Contents Discrete and Combinatorial Topology Homotopic Thinning in 2D and 3D Cubical Complexes Based on Critical Kernels. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131 Michel Couprie and Gilles Bertrand P-Simple Points and General-Simple Deletion Rules . . . . . . . . . . . . . . . . . . 143 Kálmán Palágyi Two Measures for the Homology Groups of Binary Volumes. . . . . . . . . . . . 154 AldoGonzalez-Lorenzo,AlexandraBac,Jean-LucMari,andPedroReal Shape Classification According to LBP Persistence of Critical Points . . . . . . 166 Ines Janusch and Walter G. Kropatsch Shape Descriptors Signature of a Shape Based on Its Pixel Coverage Representation. . . . . . . . . 181 Vladimir Ilić, Joakim Lindblad, and Nataša Sladoje Computation of the Normal Vector to a Digital Plane by Sampling Significant Points . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 194 Jacques-Olivier Lachaud, Xavier Provençal, and Tristan Roussillon Finding Shortest Triangular Path in a Digital Object . . . . . . . . . . . . . . . . . . 206 Apurba Sarkar, Arindam Biswas, Shouvick Mondal, and Mousumi Dutt A Measure of Q-Convexity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 219 Péter Balázs and Sara Brunetti Models for Discrete Geometry Symmetric Masks for In-fill Pixel Interpolation on Discrete p:q Lattices . . . . 233 Imants Svalbe and Arnaud Guinard Digital Surfaces of Revolution Made Simple . . . . . . . . . . . . . . . . . . . . . . . 244 Eric Andres and Gaelle Largeteau-Skapin OnFunctionalityofQuadragintaOctantsofNaiveSpherewithApplication to Circle Drawing. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 256 Ranita Biswas and Partha Bhowmick Encoding Specific 3D Polyhedral Complexes Using 3D Binary Images . . . . . 268 Rocio Gonzalez-Diaz, Maria-Jose Jimenez, and Belen Medrano Interactive Curvature Tensor Visualization on Digital Surfaces . . . . . . . . . . . 282 Hélène Perrier, Jérémy Levallois, David Coeurjolly, Jean-Philippe Farrugia, Jean-Claude Iehl, and Jacques-Olivier Lachaud Contents IX Construction of Digital Ellipse by Recursive Integer Intervals. . . . . . . . . . . . 295 Papia Mahato and Partha Bhowmick Morphological Analysis Parallelization Strategy for Elementary Morphological Operators on Graphs . . . 311 Imane Youkana, Jean Cousty, Rachida Saouli, and Mohamed Akil Digitization of Partitions and Tessellations. . . . . . . . . . . . . . . . . . . . . . . . . 323 Jean Serra and B. Ravi Kiran Geometric Transforms nD Quasi-Affine Transformations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 337 Marie-Andrée Jacob-Da Col and Loïc Mazo Minimal Paths by Sum of Distance Transforms. . . . . . . . . . . . . . . . . . . . . . 349 Robin Strand Bijective Rigid Motions of the 2D Cartesian Grid. . . . . . . . . . . . . . . . . . . . 359 Kacper Pluta, Pascal Romon, Yukiko Kenmochi, and Nicolas Passat On Weighted Distances on the Khalimsky Grid . . . . . . . . . . . . . . . . . . . . . 372 Gergely Kovács, Benedek Nagy, and Béla Vizvári Digital Disks by Weighted Distances in the Triangular Grid. . . . . . . . . . . . . 385 Benedek Nagy and Hamid Mir-Mohammad-Sadeghi Discrete Shape Representation, Recognition and Analysis Representation of Imprecise Digital Objects . . . . . . . . . . . . . . . . . . . . . . . . 401 Isabelle Sivignon Recognition of Digital Polyhedra with a Fixed Number of Faces. . . . . . . . . . 415 Yan Gérard Centerlines of Tubular Volumes Based on Orthogonal Plane Estimation. . . . . 427 Florent Grélard, Fabien Baldacci, Anne Vialard, and Jean-Philippe Domenger Adaptive Tangential Cover for Noisy Digital Contours . . . . . . . . . . . . . . . . 439 Phuc Ngo, Hayat Nasser, Isabelle Debled-Rennesson, and Bertrand Kerautret Author Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 453