Lecture Notes in Computer Science 7749 CommencedPublicationin1973 FoundingandFormerSeriesEditors: GerhardGoos,JurisHartmanis,andJanvanLeeuwen EditorialBoard DavidHutchison LancasterUniversity,UK TakeoKanade CarnegieMellonUniversity,Pittsburgh,PA,USA JosefKittler UniversityofSurrey,Guildford,UK JonM.Kleinberg CornellUniversity,Ithaca,NY,USA AlfredKobsa UniversityofCalifornia,Irvine,CA,USA FriedemannMattern ETHZurich,Switzerland JohnC.Mitchell StanfordUniversity,CA,USA MoniNaor WeizmannInstituteofScience,Rehovot,Israel OscarNierstrasz UniversityofBern,Switzerland C.PanduRangan IndianInstituteofTechnology,Madras,India BernhardSteffen TUDortmundUniversity,Germany MadhuSudan MicrosoftResearch,Cambridge,MA,USA DemetriTerzopoulos UniversityofCalifornia,LosAngeles,CA,USA DougTygar UniversityofCalifornia,Berkeley,CA,USA GerhardWeikum MaxPlanckInstituteforInformatics,Saarbruecken,Germany Rocio Gonzalez-Diaz Maria-Jose Jimenez Belen Medrano (Eds.) Discrete Geometry for Computer Imagery 17thIAPRInternationalConference,DGCI2013 Seville, Spain, March 20-22, 2013 Proceedings 1 3 VolumeEditors RocioGonzalez-Diaz Maria-JoseJimenez BelenMedrano UniversityofSeville AppliedMathIDepartment Avd.ReinaMercedess/n 41012Seville,Spain E-mail:{rogodi;majiro;belenmg}@us.es ISSN0302-9743 e-ISSN1611-3349 ISBN978-3-642-37066-3 e-ISBN978-3-642-37067-0 DOI10.1007/978-3-642-37067-0 SpringerHeidelbergDordrechtLondonNewYork LibraryofCongressControlNumber:2013932474 CRSubjectClassification(1998):I.3.5,I.4.1,I.4,I.3,I.5,G.2 LNCSSublibrary:SL6–ImageProcessing,ComputerVision,PatternRecognition, andGraphics ©Springer-VerlagBerlinHeidelberg2013 Thisworkissubjecttocopyright.Allrightsarereserved,whetherthewholeorpartofthematerialis concerned,specificallytherightsoftranslation,reprinting,re-useofillustrations,recitation,broadcasting, reproductiononmicrofilmsorinanyotherway,andstorageindatabanks.Duplicationofthispublication orpartsthereofispermittedonlyundertheprovisionsoftheGermanCopyrightLawofSeptember9,1965, inistcurrentversion,andpermissionforusemustalwaysbeobtainedfromSpringer.Violationsareliable toprosecutionundertheGermanCopyrightLaw. Theuseofgeneraldescriptivenames,registerednames,trademarks,etc.inthispublicationdoesnotimply, evenintheabsenceofaspecificstatement,thatsuchnamesareexemptfromtherelevantprotectivelaws andregulationsandthereforefreeforgeneraluse. Typesetting:Camera-readybyauthor,dataconversionbyScientificPublishingServices,Chennai,India Printedonacid-freepaper SpringerispartofSpringerScience+BusinessMedia(www.springer.com) Preface The organizationof the 17thInternational Conference on Discrete Geometry for Computer Imagery (DGCI 2013) has been a rewarding experience for our An- dalusian research group, Combinatorial Image Analysis (CIMAgroup). As or- ganizers, we are pleased with the participation of many researchers from all around the world, taking into account the financial difficulties of our times. In- deed,submissions from26different countriesconfirmthe internationalstatus of the conference. This collection documents the contributions presented at DGCI 2013,which focus on geometric transforms, discrete and combinatorial tools for image segmentation and analysis, discrete and combinatorial topology, discrete shape representation,recognitionand analysis,models for discrete geometry, morpho- logical analysis, and discrete tomography. Followinga peer-reviewingprocessbyatleasttwoqualifiedreviewers,34pa- perswereaccepted,outof56submissions.Altogether,22paperswerescheduled for oral presentation in single-track sessions, and 12 papers were presented as posters. Ithasbeenagreathonorforustocountontheparticipationofthreeinterna- tionally well-knownresearchersas invitedspeakers:HerbertEdelsbrunner(Pro- fessor at the Institute of Science and Technology, Vienna University, Austria), Francisco Escolano (Associate Professor at the University of Alicante, Spain), and Konrad Polthier (MATHEON-Professor and Director of the Mathematical Geometry Processing group at Freie Universit¨at Berlin, Germany). We would like to expressour gratitude to the Reviewing and ProgramCom- mittee members for their valuable comments, which enabled the authors to im- prove the quality of their contributions. We are also grateful to the Steering Committee for giving us the chance to organize this event and especially to David Coeurjolly for his support and helpful advice. DGCI 2013 has been supported by the International Association of Pattern Recognition(IAPR). DGCI conferencesarethe maineventsassociatedwith the TechnicalCommittee on Discrete GeometryIAPR-TC18.This conferencecould nothavebeenorganizedwithoutoursponsoringinstitutions:UniversityofSeville (Vice-rectorate for Research, Vice-rectorate of Internationalization, the Mathe- matics Institute IMUS, the Research and Teaching Foundation FIDETIA, Ap- plied Math-I Department), Spanish Ministry of Economy and Competitiveness (ProjectMTM2012-32706),andEuropeanScienceFoundation(ACATprogram). We arealsogratefulto the SchoolofComputerEngineeringatthe Universityof Seville, for hosting this event and providing all the necessary facilities. VI Preface Finally, our special thanks go to the local Organizing Committee for their valuable work and to all the participants attending the conference, who made this event a success. March 2013 Rocio Gonzalez-Diaz Maria-JoseJimenez Belen Medrano Organization Organizing Committee Rocio Gonzalez-Diaz University of Seville (Co-chair) Maria-JoseJimenez University of Seville (Co-chair) Javier Carnero FIDETIA, University of Seville Daniel Diaz University of Seville Desamparados Fernandez University of Seville Irene Fondon University of Seville Antonio Gutierrez University of Seville Belen Medrano University of Seville Helena Molina-Abril University of Sheffield Ana Maria Pacheco University of Seville Angel Tenorio University of Pablo Olavide Lidia de la Torre University of Seville Jose Antonio Vilches University of Seville Steering Committee Annick Montanvert (President) University of Grenoble, France Eric Andres University of Poitiers,France Gunilla Borgefors University of Uppsala, Sweden Sreˇcko Brlek University of Quebec, Canada Jean-Marc Chassery CNRS, University of Grenoble, France David Coeurjolly CNRS, University of Lyon, France Isabelle Debled-Rennesson LORIA, University of Nancy, France Ullrich K¨othe University of Heidelberg, Germany Kalman Palagyi University of Szeged, Hungary Gabriella Sanniti di Baja Institute of Cybernetics Eduardo Caianiello, CNR, Italy Program Committee Reneta Barneva SUNY Fredonia (NY), USA K. Joost Batenburg Centrum Wiskunde & Informatica, Scientific Computing Group, The Netherlands Isabelle Bloch Telecom ParisTech-CNRSLTCI, France Sara Brunetti University of Siena, Italy VIII Organization Michel Couprie ESIEE/LIGM, France Guillaume Damiand LIRIS, CNRS, University of Lyon, France Laurent Fuchs SIC, University of Poitiers, France Atsushi Imiya University of Chiba, Japan Christer Kiselman Uppsala University, Sweden Walter Kropatsch TU Vienna, Austria Jacques-OlivierLachaud University of Savoie, France R´emy Malgouyres LIMOS, University of Auvergne, Italy Peer Stelldinger University of Hamburg, Germany Robin Strand Centre for Image Analysis, Sweden Edouard Thiel LIF, Aix-Marseille University, France Peter Veelaert University College of Ghent, Belgium Reviewing Committee Sylvie Alayrangues Jean Philippe Domenger Pascal Lienhardt Andreas Alpers Eric Domenjoud Joakim Lindblad Eric Andres Ulrich Albert Eckhardt Laurent Lucas Dominique Attali Philippe Even Gr´egoire Malandain Peter Attila Balazs Thomas Fernique R´emy Malgouyres Antonio Bandera Massimo Ferri Jean-Luc Mari Reneta Barneva Fabien Feschet Robert A. Melter Nicolas Bedaride Angel R. Frances Roman Christian Mercat Valerie Berthe Patrizio Frosini Serge Miguet Gilles Bertrand Laurent Fuchs Annick Montanvert Isabelle Bloch Yan Gerard Thierry Monteil Olivier Bodini Antonio Giraldo Benoˆıt Naegel Gunilla Borgefors Rocio Gonzalez-Diaz Thanh Phuong Nguyen Achille Braquelaire Jeanpierre Gu´edon Nicolas Normand Valentin Brimkov Lajos Hajdu Kalman Palagyi Sreˇcko Brlek Yll Haxhimusa Nicolas Passat Luc Brun Atsushi Imiya Samuel Peltier Sara Brunetti Maria Jose Jimenez Christophe Picouleau Sergio Cabello Yukiko Kenmochi Renzo Pinzani Jean-Marc Chassery Bertrand Kerautret Xavier Proven¸cal David Coeurjolly Christer Oscar Kiselman Eric Remy Michel Couprie Reinhard Klette Christian Ronse Jean Cousty Ullrich Koethe Tristan Roussillon Jose Crespo T. Yung Kong GabriellaSannitidiBaja Marie-Andr´ee Da Col Walter G. Kropatsch Isabelle Sivignon Guillaume Damiand Jacques-OlivierLachaud Peer Stelldinger Isabelle Claudia Landi Robin Strand Debled-Rennesson Ga¨elle Largeteau-Skapin Mohamed Tajine PascalDesbarats Bruno Eric Emmanuel Hugues Talbot Olivier Devillers Levy Alexandru Telea Organization IX Edouard Thiel Sebastien Valette Laurent Wendling Laure Tougne Peter Veelaert Jean-Luc Toutant Laurent Vuillon Sponsoring Institutions DGCI 2013 was supported by the following institutions: – Vice-rectorate of Research and Vice-rectorate of Internationalization, University of Seville – European Science Foundation (ACAT program) – Spanish Ministry of Economy and Competitiveness (Project MTM2012- 326706) – Mathematics Institute at the University of Seville (IMUS) – International Association of Pattern Recognition (IAPR) – Applied Math-I Department at University of Seville – The Researchand Teaching Foundation FIDETIA – Spanish Network of Topology (RET) – School of Computer Engineering at University of Seville The Complexity of Discrete Objects Francisco Escolano University of Alicante, Spain [email protected] Abstract. In this paper we explore how to quantify the complexity of discrete objects (images, meshes, networks) which can be encoded in terms of graphs, digraphs or hypergraphs. Herein we present our Heat Flow-Thermodynamic Depth approach which combines ingredients of spectral graph theory, information theory and information projection. We illustrate the approach with several applications: image exploration (image complexity), mesh regularization and selection of optimal map functionsinExtendedReebGraphs(graphanddigraphcomplexity)and structuralcategorization (hypergraphcomplexity). 1 Randomness vs. Statistical Complexity Given a discrete mathematical object (image, mesh, network) which can be en- coded by a graph, digraph or hypergraph, the quantification of its intrinsic complexity playsakeyroleinunderstandingthe underpinningstructuralprinci- plesshapingit.Suchprinciplesinclude:theinformationcontentoftheencoding, the set of constraints over the information flowing through it, and the combi- natorial exploration of the hypothesis that best explain its genesis. Information content may be posed in terms of estimating a given entropy. Information flow constraints may be discovered by probing the structure through heat kernels and wave equations. Generative hypothesis may rely on depth-based represen- tations like logical depth or thermodynamic depth, hierarchical representations like grammars and compositional models, or dynamic rules like preferential at- tachment. The weight of each of the latter principles in the characterization of the encoding defines a computable complexity measure for it. For instance, strategiesconsideringinformationcontentthroughShannonorcrossentropyare referred to as randomness complexity measures for they quantify the degree of disorganization(see a recent survey on graph entropy measures in [1]) . On the other hand, methods relying on spectral measures, like the von Neumann en- tropy [2], or on Dirichlet sums, like Estrada’s heterogeneity index are [3] more focused on quantifying the degree of regularityof the structure. These are good examples of the so called statistical complexity measures that vanished both for completely regular and completely random structures. Thermodynamic depth (TD)isaphysicsbasedapproach[4]alsobelongingtothelattercategory.When dealingwith graphs,termodynamic depthaims to quantify howhardis to build agivengraph(the macroscopicstate)fromscracth(microscopicstates):ifthere