Undergraduate Topics in Computer Science Forfurthervolumes: http://www.springer.com/series/7592 UndergraduateTopicsinComputerScience(UTiCS)delivershigh-qualityinstructionalcontent forundergraduatesstudyinginallareasofcomputingandinformationscience.Fromcorefoun- dationalandtheoreticalmaterialtofinal-yeartopicsandapplications,UTiCSbookstakeafresh, concise,andmodernapproachandareidealforself-studyorforaone-ortwo-semestercourse. The texts are all authored by established experts in their fields, reviewed by an international advisory board, and contain numerous examples and problems. Many include fully worked solutions. Wilhelm Burger Mark J. Burge • Principles of Digital Image Processing Core Algorithms 123 WilhelmBurger MarkJ.Burge UniversityofAppliedSciences noblis.org Hagenberg Washington,D.C. Austria [email protected] [email protected] Serieseditor IanMackie,E´colePolytechnique,FranceandUniversityofSussex,UK Advisoryboard SamsonAbramsky,UniversityofOxford,UK ChrisHankin,ImperialCollegeLondon,UK DexterKozen,CornellUniversity,USA AndrewPitts,UniversityofCambridge,UK HanneRiisNielson,TechnicalUniversityofDenmark,Denmark StevenSkiena,StonyBrookUniversity,USA IainStewart,UniversityofDurham,UK DavidZhang,TheHongKongPolytechnicUniversity,HongKong UndergraduateTopicsinComputerScienceISSN1863-7310 ISBN978-1-84800-194-7 e-ISBN978-1-84800-195-4 DOI10.1007/978-1-84800-195-4 BritishLibraryCataloguinginPublicationData AcataloguerecordforthisbookisavailablefromtheBritishLibrary LibraryofCongressControlNumber:2008942518 (cid:2)c Springer-VerlagLondonLimited2009 Apartfromanyfairdealingforthepurposesofresearchorprivatestudy,orcriticismorreview,aspermitted undertheCopyright,DesignsandPatentsAct1988,thispublicationmayonlybereproduced,storedor transmitted,inanyformorbyanymeans,withthepriorpermissioninwritingofthepublishers,orin thecaseofreprographicreproductioninaccordancewiththetermsoflicencesissuedbytheCopyright LicensingAgency.Enquiriesconcerningreproductionoutsidethosetermsshouldbesenttothepublishers. Theuseofregisterednames,trademarks,etc.,inthispublicationdoesnotimply,evenintheabsenceofa specificstatement,thatsuchnamesareexemptfromtherelevantlawsandregulationsandthereforefreefor generaluse. Thepublishermakesnorepresentation,expressorimplied,withregardtotheaccuracyoftheinformation containedinthisbookandcannotacceptanylegalresponsibilityorliabilityforanyerrorsoromissionsthat maybemade. Printedonacid-freepaper SpringerScience+BusinessMedia springer.com Preface This is the second volume of a book series that provides a modern, algorith- mic introduction to digital image processing. It is designed to be used both by learners desiring a firm foundation on which to build and practitioners in search of critical analysis and modern implementations of the most important techniques. This updated and enhanced paperback edition of our comprehen- sive textbook Digital Image Processing: An Algorithmic Approach Using Java packages the original material into a series of compact volumes, thereby sup- portingaflexible sequenceofcoursesindigitalimageprocessing. Tailoringthe contents to the scope of individual semester courses is also an attempt to pro- vide affordable (and “backpack-compatible”) textbooks without comprimising the quality and depth of content. This second volume, titled Core Algorithms, extends the introductory ma- terial presented in the first volume (Fundamental Techniques) with additional techniques that are, nevertheless, part of the standard image processing tool- box. Aforthcomingthirdvolume(Advanced Techniques)willextendthisseries and add important material beyond the elementary level, suitable for an ad- vanced undergraduate or even graduate course. Math, Algorithms, and “Real” Code Ithasbeenourexperienceinteachinginthisfieldthatmasteringthecoretakes more than just reading about the techniques—it requires active construction and experimentation with the algorithms to acquire a feeling for how to use these methods in the real world. Internet search engines have made finding someone’s code for almost any imaging problem as simple as coming up with a succinct enough set of keywords. However, the problem is not to find a solution,butdevelopingone’sownandunderstandinghowitworks—orwhy it vi Preface eventuallydoesnot. Whereaswefeelthattherealvalueofthisseriesisnotinits code,butratherinthecriticalselectionofalgorithms,illustratedexplanations, and concise mathematical derivations, we continue to augment our algorithms withcompleteimplementations,aseventhe bestdescriptionofamethodoften omits some essential element necessary for the actual implementation, which only the unambiguous semantics of a real programming language can provide. Online Resources The authors maintain a Website for this text that provides supplementary materials, including the complete Java source code for the examples, the test images used in the examples, and corrections. Visit this site at www.imagingbook.com Additionalmaterialsareavailableforeducators,includingacompletesetoffig- ures,tables,andmathematicalelementsshowninthetext,inaformatsuitable foreasyinclusioninpresentationsandcoursenotes. Comments,questions,and corrections are welcome and should be addressed to [email protected] Acknowledgements As with its predecessors, this book would not have been possible without the understanding and steady support of our families. Thanks go to Wayne Ras- band (NIH) for developing and refining ImageJ and for his truly outstanding support of the community. We appreciate the contribution from many careful readerswhohavecontactedustosuggestnewtopics,recommendalternativeso- lutions,ortosuggestcorrections. Finally,wearegratefultoWayneWheelerfor initiating this bookseriesandCatherineBrettandhercolleaguesatSpringer’s UK and New York offices for their professional support. Hagenberg, Austria/Washington DC, USA June 2008 Contents Preface ......................................................... v 1. Introduction................................................ 1 1.1 Programming with Images................................. 2 1.2 Image Analysis........................................... 3 2. Regions in Binary Images................................... 5 2.1 Finding Image Regions.................................... 6 2.1.1 Region Labeling with Flood Filling ................... 6 2.1.2 Sequential Region Labeling .......................... 11 2.1.3 Region Labeling—Summary ......................... 17 2.2 Region Contours ......................................... 17 2.2.1 External and Internal Contours ...................... 18 2.2.2 Combining Region Labeling and Contour Finding ...... 20 2.2.3 Implementation .................................... 22 2.2.4 Example .......................................... 25 2.3 Representing Image Regions ............................... 26 2.3.1 Matrix Representation .............................. 26 2.3.2 Run Length Encoding............................... 27 2.3.3 Chain Codes....................................... 28 2.4 Properties of Binary Regions............................... 32 2.4.1 Shape Features..................................... 32 2.4.2 Geometric Features................................. 33 2.4.3 Statistical Shape Properties.......................... 36 2.4.4 Moment-Based Geometrical Properties ................ 38 2.4.5 Projections ........................................ 44 viii Contents 2.4.6 Topological Properties .............................. 45 2.5 Exercises ................................................ 46 3. Detecting Simple Curves ................................... 49 3.1 Salient Structures ........................................ 49 3.2 Hough Transform......................................... 50 3.2.1 Parameter Space ................................... 51 3.2.2 Accumulator Array ................................. 54 3.2.3 A Better Line Representation ........................ 54 3.3 Implementing the Hough Transform ........................ 55 3.3.1 Filling the Accumulator Array ....................... 56 3.3.2 Analyzing the Accumulator Array .................... 56 3.3.3 Hough Transform Extensions ........................ 60 3.4 Hough Transform for Circles and Ellipses.................... 63 3.4.1 Circles and Arcs ................................... 64 3.4.2 Ellipses ........................................... 66 3.5 Exercises ................................................ 67 4. Corner Detection ........................................... 69 4.1 Points of Interest......................................... 69 4.2 Harris Corner Detector.................................... 70 4.2.1 Local Structure Matrix.............................. 70 4.2.2 Corner Response Function (CRF) .................... 71 4.2.3 Determining Corner Points .......................... 72 4.2.4 Example .......................................... 72 4.3 Implementation .......................................... 72 4.3.1 Step 1: Computing the Corner Response Function...... 76 4.3.2 Step 2: Selecting “Good” Corner Points ............... 79 4.3.3 Displaying the Corner Points ........................ 83 4.3.4 Summary.......................................... 83 4.4 Exercises ................................................ 84 5. Color Quantization ......................................... 85 5.1 Scalar Color Quantization ................................. 86 5.2 Vector Quantization ...................................... 88 5.2.1 Populosity algorithm................................ 88 5.2.2 Median-cut algorithm............................... 88 5.2.3 Octree algorithm ................................... 89 5.2.4 Other methods for vector quantization ................ 94 5.3 Exercises ................................................ 95 Contents ix 6. Colorimetric Color Spaces .................................. 97 6.1 CIE Color Spaces......................................... 98 6.1.1 CIE XYZ color space ............................... 98 6.1.2 CIE x,y chromaticity ............................... 99 6.1.3 Standard illuminants ...............................101 6.1.4 Gamut............................................102 6.1.5 Variants of the CIE color space ......................103 6.2 CIE L∗a∗b∗...............................................104 6.2.1 Transformation CIEXYZ → L∗a∗b∗ ...................104 6.2.2 Transformation L∗a∗b∗ → CIEXYZ ...................105 6.2.3 Measuring color differences ..........................105 6.3 sRGB...................................................106 6.3.1 Linear vs. nonlinear color components.................107 6.3.2 Transformation CIEXYZ→sRGB ....................108 6.3.3 Transformation sRGB→CIEXYZ ....................108 6.3.4 Calculating with sRGB values........................109 6.4 Adobe RGB .............................................111 6.5 Chromatic Adaptation ....................................111 6.5.1 XYZ scaling .......................................112 6.5.2 Bradford adaptation ................................113 6.6 Colorimetric Support in Java ..............................114 6.6.1 sRGB colors in Java ................................114 6.6.2 Profile connection space (PCS).......................115 6.6.3 Color-relatedJava classes ...........................118 6.6.4 A L∗a∗b∗ color space implementation ..................120 6.6.5 ICC profiles .......................................121 6.7 Exercises ................................................124 7. Introduction to Spectral Techniques ........................125 7.1 The Fourier Transform ....................................126 7.1.1 Sine and Cosine Functions...........................126 7.1.2 Fourier Series of Periodic Functions...................130 7.1.3 Fourier Integral ....................................130 7.1.4 Fourier Spectrum and Transformation.................131 7.1.5 Fourier Transform Pairs.............................132 7.1.6 Important Properties of the Fourier Transform .........136 7.2 Working with Discrete Signals .............................137 7.2.1 Sampling..........................................137 7.2.2 Discrete and Periodic Functions ......................144 7.3 The Discrete Fourier Transform (DFT)......................144 7.3.1 Definition of the DFT...............................144