Lecture Notes in Computer Science 7655 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 Reneta P. Barneva Valentin E. Brimkov Jake K. Aggarwal (Eds.) Combinatorial Image Analysis 15th International Workshop, IWCIA 2012 Austin, TX, USA, November 28-30, 2012 Proceedings 1 3 VolumeEditors RenetaP.Barneva StateUniversityofNewYorkatFredonia DepartmentofComputerandInformationSciences 280CentralAve. Fredonia,NY14063,USA E-mail:[email protected] ValentinE.Brimkov SUNYBuffaloStateCollege MathematicsDepartment 1300ElmwoodAve. Buffalo,NY14222,USA E-mail:[email protected] JakeK.Aggarwal UniversityofTexasatAustin DepartmentofElectricalandComputerEngineering 1UniversityStationC0803 Austin,TX78712-0240,USA E-mail:[email protected] ISSN0302-9743 e-ISSN1611-3349 ISBN978-3-642-34731-3 e-ISBN978-3-642-34732-0 DOI10.1007/978-3-642-34732-0 SpringerHeidelbergDordrechtLondonNewYork LibraryofCongressControlNumber:2012951153 CR Subject Classification (1998): I.4.5-6, I.4.9-10, I.3.5, I.3.7, I.5.4, F.2.2, G.2.1, G.1.6,I.4 LNCSSublibrary:SL6–ImageProcessing,ComputerVision,PatternRecognition, andGraphics ©Springer-VerlagBerlinHeidelberg2012 Thisworkissubjecttocopyright.Allrightsarereserved,whetherthewholeorpartofthematerialis concerned,specificallytherightsoftranslation,reprinting,re-useofillustrations,recitation,broadcasting, reproductiononmicrofilmsorinanyotherway,andstorageindatabanks.Duplicationofthispublication orpartsthereofispermittedonlyundertheprovisionsoftheGermanCopyrightLawofSeptember9,1965, initscurrentversion,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 This volume contains the articles presentedat the 15thInternationalWorkshop onCombinatorialImageAnalysis,IWCIA2012,whichwasheldinAustin(TX), November 28–30, 2012. The 14 previous meetings were held in Paris (France) 1991, Ube (Japan) 1992, Washington DC (USA) 1994, Lyon (France) 1995, Hi- roshima (Japan) 1997, Madras (India) 1999, Caen (France) 2000, Philadelphia (USA) 2001, Palermo (Italy) 2003, Auckland (New Zealand) 2004, Berlin (Ger- many)2006,Buffalo (USA) 2008,PlayadelCarmen(Mexico)2009,andMadrid (Spain) 2011. Combinatorial image analysis provides theoretical foundations and methods for solving problems from various areas of human practice. In contrast to tradi- tional approaches to image analysis which implement continuous models, float arithmetic and rounding, combinatorial image analysis features discrete models using integer arithmetic. The developed algorithms are based on studying com- binatorial properties of classes of digital images, and often appear to be more efficient and accurate than those based on continuous models. IWCIA is an exciting opportunity for scholars, graduate students, and edu- catorsacrosstheworldtomeetandshareinformationabouttheirlatestfindings in the field of combinatorial image analysis, be enriched with new ideas, reflect on some open problems, learn about new applications, and reconnect with col- leagues. All papers submitted to the conference were carefully reviewed as each manuscript was sent for a double-blind review to at least three highly qualified members of the international Program Committee. The submission and review process of the workshop was carried out through the professional OpenConf conference management system. After a rigorous review process, 23 papers au- thoredby51researchersfrom11countrieswereacceptedforpresentationatthe workshop and for inclusion in this volume. IWCIA 2012 featured keynote talks delivered by three outstanding scholars, whose excellent presentations inspired the audience with new ideas. An opening talk given by Ja´nos Pach (EPEL, Lausanne and Alfr´ed R´enyi Institute of Mathematics, Budapest) was devoted to geometric graph theory. Thelatterstudiesgeometric(topological)graphsthatcanbedrawnintheplane bystraight-lineorcurvilinearedgessatisfyingcertainconditions.Inhistalk,the speakerdiscussedfundamentalextremalquestionsingeometricgraphtheoryand surveyed various results and unsolved problems. David A. Eppstein (Donald Bren School of Information and Computer Sci- ences, University of California, Irvine) presented an approach based on three- dimensional hyperbolic geometry to forming a novel type of Voronoi diagram for circles in the plane. The proposed method provides a discrete combinatorial representation for a class of objects which may be applicable to visualization VI Preface of broader classes of low-degree planar graphs via “Lombardi drawings” with circular-arc edges. Gerhard X. Ritter (University of Florida, Gainesville) presented a lattice al- gebraapproachtocomputationalintelligenceandimageprocessing.Heprovided an overview of lattice theory-based models and techniques in the field of com- putational intelligence and discussed the specific applications to hyperspectral image segmentation and pattern recognition. The contributed papers included in the volume are grouped into two parts. The first one includes 11 papers devoted to diverse problems of digital geom- etry and topology, in particular studies on geometry and topology of digital curves and surfaces, the design of space-efficient algorithms, and others. The secondpartincludespaperspresentingarraygrammarsandlanguagesforimage analysis, research on picture transformations, morphological operations, image segmentation, discrete tomography,and applications. We believe that all presented works were of high quality and the attendees benefited from the scientific program. We would like to express our gratitude to everyone who contributed to the success of IWCIA 2012 – from the Steering to the Program and Organizing Committees. We are indebted to our sponsors SUNY Buffalo State College and SUNY Fredonia, and in particular to the Interim Provost Kevin P. Kearns of SUNY Fredonia, who endorsed the publication of this volume. We wishto expressour specialthanks to the invited speakersDavidA.Epp- stein, Ja´nos Pach, and Gerhard X. Ritter for their remarkable talks and overall contribution to the workshop program. We thank all authors for their valuable worksandhopethatthereaderwillfindtheminterestinganduseful.Wewishto thank the participants and everyone who made this workshop an enjoyable and fruitfulscientificevent.WehadagreattimeattheJoeC.ThompsonConference Center of the University of Texas at Austin thanks to Elisabel Bordallo, Con- ferenceServicesManager,andBaileyAnne Dermanci;weappreciatetheirwork. Finally,weexpressourgratitudetoSpringer’sComputerScienceEditorialteam, andespecially toAlfredHofmannandAnnaKramer,for theirefficientandkind cooperation in the timely production of this book. November 2012 Reneta P. Barneva Valentin E. Brimkov Jake K. Aggarwal Organization IWCIA2012washeldattheUniversityofTexasatAustin,TX,USA,November 28–30,2012 General Chairs Jake K. Aggarwal University of Texas at Austin, USA Valentin E. Brimkov SUNY Buffalo State College, USA Program and Publication Chair Reneta P. Barneva SUNY Fredonia, USA Steering Committee Valentin E. Brimkov SUNY Buffalo State College, USA Gabor T. Herman CUNY Graduate Center, USA Kostadin Koroutchev Universidad Autonoma de Madrid, Spain Petra Wiederhold CINVESTAV-IPN, Mexico Invited Speakers David A. Eppstein University of California, Irvine, USA Ja´nos Pach EPFL, Lausanne, Switzerland and R´enyi Institute, Budapest, Hungary Gerhard X. Ritter University of Florida, USA Program Committee Til Aach RWTH Aachen University, Germany Lyuba Alboul Sheffield Hallam University, UK Eric Andres University of Poitiers, France Arrate Mun˜oz Universidad de Navarra, Spain Akira Asano Hiroshima University, Japan Jacky Baltes University of Manitoba, Canada P´eter Bal´azs University of Szeged, Hungary George Bebis University of Nevada at Reno, USA Bedrich Benes Purdue University, USA Gilles Bertrand ESIEE, France Bhargab B. Bhattacharya Indian Statistical Institute, India Peter Brass CityCollege,CityUniversityofNewYork,USA VIII Organization Alfred M. Bruckstein Technion, I.I.T, Israel Jean-Marc Chassery University of Grenoble, France Li Chen University of the District of Columbia, USA Marco Cristani University of Verona, Italy Guillaume Damiand LIRIS-CNRS,Universit´e de Lyon, France Leila De Floriani University of Genova, Italy and University of Maryland, USA Isabelle Debled-Rennesson Nancy University, LORIA, France Eduardo Destefanis Universidad Tecnologica Nacional Co´rdoba, Argentina Chiou-Shann Fuh National Taiwan University, Taiwan Ju¨rgen Gall ETH Zu¨rich, Switzerland Edgar Gardun˜o IIMAS-UNAM, Mexico Roc´ıo Gonz´alez D´ıaz University of Seville, Spain Jordi Gonza`lez i Sabat´e UAB, Spain Concettina Guerra Universita` di Padova, Italy Edwin Hancock University of York, UK Atsushi Imiya IMIT, Chiba University, Japan Damien Jamet University of Nancy, France Mar´ıa Jos´e Jim´enez University of Seville, Spain Ramakrishna Kakarala NTU, Singapore Andreas Koschan University of Tennessee, USA Walter G. Kropatsch Vienna University of Technology, Austria Longin Jan Latecki Temple University, USA Jerome Liang SUNY Stony Brook, USA PascalLienhardt University of Poitiers, France Shih-Schon Lin University of Pennsylvania, USA Joakim Lindblad Swedish University of Agricultural Sciences, Sweden Hongbing Lu Fourth Military Medical University, China Avner Magen University of Toronto, Canada R´emy Malgouyres Universit´e d’Auvergne, France Ramon Mas Sans´o Universitat de les Illes Balears, Spain Erik Melin Uppsala University, Sweden Christian Mercat Universit´e Montpellier, France Vittorio Murino University of Verona, Italy Benedek Nagy University of Debrecen, Hungary Akira Nakamura Hiroshima University, Japan Renato M. Natal Jorge University of Porto, Portugal Gregory M. Nielson Arizona State University, USA Ja´nos Pach City College and Courant Institute, USA Kalman Palagyi University of Szeged, Hungary Petra Perner Institute of Computer Vision and Applied Computer Sciences, Germany Hemerson Pistori Dom Bosco Catholic University, Brazil Organization IX Ioannis Pitas University of Thessaloniki, Greece Konrad Polthier Freie Universita˝t Berlin, Germany Hong Qin SUNY Stony Brook, USA Paolo Remagnino Kingston University, UK Ralf Reulke Humboldt University, Germany Gerhard Ritter University of Florida, USA Mariano Rivera CIMAT, Mexico Xavier Roca Marv`a UAB, Spain Bodo Rosenhahn MPI Informatik, Germany Arun Ross West Virginia University, USA Angel Sappa Computer Vision Center, Spain Henrik Schulz ForschungszentrumDresden, Germany Nikolay Sirakov Texas A&M University, USA Rani Siromoney Madras Christian College, India Isabelle Sivignon LIRIS-CNRS, University of Lyon, France Wladyslaw Skarbek Warsaw University of Technology, Poland Ali Shokoufandeh Drexel University, USA Alberto Soria CINVESTAV, Mexico K.G. Subramanian Universiti Sains Malaysia, Malaysia Akihiro Sugimoto National Institute of Informatics, Japan Mohamed Tajine Louis Pasteur University, Strasbourg, France Joao Manuel R.S. Tavares University of Porto, Portugal Antonio Turiel ICM, CSIC, Spain Peter Veelaert Ghent University, Belgium Young Woon Woo Dong-Eui University Busan, Korea Jinhui Xu SUNY University at Buffalo, USA Yasushi Yagi Osaka University, Japan Jason You Cubic Imaging LLC, USA Richard Zanibbi Rochester Institute of Technology, USA Larry Zeng University of Utah, USA Organizing Committee Reneta P. Barneva SUNY Fredonia, USA Michael Szocki SUNY Fredonia, USA Boris Brimkov SUNY Fredonia, USA Sponsoring Institutions SUNY Buffalo State College, Buffalo, NY SUNY Fredonia, Fredonia, NY The Interim Provostof SUNY Fredonia, Dr. Kevin P. Kearns, sponsored the conference proceedings Table of Contents Part I: Geometry and Topology Digital Geometry, Combinatorics in Digital Spaces. Digital Curves and Surfaces On Finding Shortest Isothetic Path Inside a Digital Object............ 1 Mousumi Dutt, Arindam Biswas, Partha Bhowmick, and Bhargab B. Bhattacharya Fast Slicing of Orthogonal Covers Using DCEL ...................... 16 Nilanjana Karmakar, Arindam Biswas, and Partha Bhowmick Fast Combinatorial Algorithm for Tightly Separating Hyperplanes ..... 31 Peter Veelaert Digital Curvatures Applied to 3D Object Analysis and Recognition: A Case Study ................................................... 45 Li Chen and Soma Biswas Discrete Polynomial Curve Fitting to Noisy Data .................... 59 Fumiki Sekiya and Akihiro Sugimoto A Probabilistic Measure of Circularity.............................. 75 Ana Marcela Herrera-Navarro, Hugo Jim´enez-Hern´andez, and Iva´n Ram´on Terol-Villalobos Digital Topology A New Framework for Connected Components Labeling of Binary Images ......................................................... 90 Tetsuo Asano and Sergey Bereg Small Work Space Algorithms for Some Basic Problems on Binary Images ......................................................... 103 Tetsuo Asano, Sergey Bereg, and Lilian Buzer Adjacencies for Structuring the Digital Plane........................ 115 Josef Sˇlapal On Topology Preservation for Triangular Thinning Algorithms......... 128 P´eter Kardos and Ka´lma´n Pala´gyi Cellular Topology on the Triangular Grid ........................... 143 Benedek Nagy XII Table of Contents Part II: Grammars, Transformations, Applications Grammars and Models in Image Analysis A P System Model for Contextual Array Languages .................. 154 K.G. Subramanian, Ibrahim Venkat, and Petra Wiederhold Rectangular Arrays and Petri Nets ................................. 166 D. Lalitha, K. Rangarajan, and Durairaj Gnanaraj Thomas Regional Hexagonal Tile Rewriting Grammars....................... 181 Thangasamy Kamaraj and Durairaj Gnanaraj Thomas Partial Commutation on Array Languages .......................... 196 Thangasamy Kamaraj, Durairaj Gnanaraj Thomas, H. Geetha, and T. Kalyani Picture Transformations, Morphologic Operations, Image Segmentation Incremental Learning of the Model for Watershed-Based Image Segmentation.................................................... 209 Anja Attig and Petra Perner Fast Level-Wise Convolution ...................................... 223 Damien Gonzalez, R´emy Malgouyres, Henri-Alex Esbelin, and Chafik Samir Combinatorial Properties of 2D Discrete Rigid Transformations under Pixel-Invariance Constraints....................................... 234 Phuc Ngo, Yukiko Kenmochi, Nicolas Passat, and Hugues Talbot Novel Morphological Algorithms for Dominating Sets on Graphs with Applications to Image Analysis .................................... 249 Anupama Potluri and Chakravarthy Bhagvati Discrete Tomography, Applications Binary Image Reconstruction from Two Projections and Skeletal Information ..................................................... 263 Norbert Hantos, P´eter Bala´zs, and Ka´lma´n Pala´gyi Energy-Minimization Based Discrete Tomography Reconstruction Method for Images on Triangular Grid.............................. 274 Tibor Luki´c and Benedek Nagy