Texts in Computer Science Wilhelm Burger Mark J. Burge Digital Image Processing An Algorithmic Introduction Using Java Second Edition Texts in Computer Science Series Editors David Gries Fred B. Schneider More information about this series at http://www.springer.com/series/3191 Wilhelm Burger • Mark J. Burge Digital Image Processing An Algorithmic Introduction Using Java Second Edition Wilhelm Burger Mark J. Burge School of Informatics/ Noblis, Inc. Communications/Media Washington, DC, USA Upper Austria University of Applied Sciences Hagenberg, Austria Series Editors David Gries Fred B. Schneider Department of Computer Science Department of Computer Science Cornell University Cornell University I thaca, NY, USA Ithaca, NY, USA ISSN 1868-0941 ISSN 1868-095X (electronic) Texts in Computer Science ISBN 978-1-4471-6683-2 ISBN 978-1-4471-6684-9 (eBook) DOI 10.1007/978-1-4471-6684-9 Library of Congress Control Number: 2016933770 © Springer-Verlag London 2008, 2016 The author(s) has/have asserted their right(s) to be identified as the author(s) of this work in accordance with the Copyright, Design and Patents Act 1988. This work is subject to copyright. All rights are reserved by the Publisher, whether the whole or part of the 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 storage and retrieval, electronic adaptation, computer software, or by similar or dissimilar methodology now known or hereafter developed. The use of general descriptive names, registered names, trademarks, service marks, etc. in this publication does not imply, even in the absence of a specific statement, that such names are exempt from the relevant protective laws and regulations and therefore free for general use. The publisher, the authors and the editors are safe to assume that the advice and information in this book are believed to be true and accurate at the date of publication. Neither the publisher nor the authors or the editors give a warranty, express or implied, with respect to the material contained herein or for any errors or omissions that may have been made. Printed on acid-free paper This Springer imprint is published by Springer Nature The registered company is Springer-Verlag London Ltd. Preface This book provides a modern, self-contained introduction to digital imageprocessing. We designedthe book to be usedboth by learners desiring a firm foundation on which to build as well as practitioners insearchofdetailedanalysisandtransparentimplementationsofthe mostimportanttechniques. This is the secondEnglisheditionofthe original German-language book, which has been widely used by: • Scientists and engineers who use image processing as a tool and wish to develop a deeper understanding and create custom solu- tions to imaging problems in their field. • IT professionals wanting a self-study course featuring easily adaptable code and completely worked out examples, enabling them to be productive right away. • Facultyandstudentsdesiringanexample-richintroductorytext- book suitable for an advanced undergraduate or graduate level course that features exercises, projects, and examples that have beenhonedduringouryearsofexperienceteachingthismaterial. While we concentrate on practical applications and concrete imple- mentations, we do so without glossing over the important formal details andmathematics necessaryfora deeper understandingofthe algorithms. In preparing this text, we started from the premise that simplycreatingarecipebookofimagingsolutionswouldnotprovide the deeper understanding needed to apply these techniques to novel problems,so insteadour solutions aredevelopedstepwise fromthree differentperspectives: inmathematicalform,asabstractpseudocode algorithms, and as complete Java programs. We use a common no- tation to intertwine all three perspectives—providing multiple, but linked, views of the problem and its solution. Prerequisites Insteadofpresentingdigitalimageprocessingasamathematicaldis- cipline, or strictly as signal processing, we present it from a practi- tioner’s and programmer’s perspective and with a view toward re- placing many of the formalisms commonly used in other texts with constructsmorereadilyunderstandablebyouraudience. Totakefull advantageoftheprogramming componentsofthisbook,aknowledge of basic data structures and object-oriented programming,ideally in Java, is required. We selected Java for a number of reasons: it is the first programming language learned by students in a wide vari- ety of engineering curricula, and professionals with knowledge of a related language, especially C# or C++, will find the programming examples easy to follow and extend. V Preface The software in this book is designed to work with ImageJ, a widely used, programmer-extensible, imaging system developed, maintained, and distributed by the National Institutes of Health (NIH).1 ImageJ is implemented completely in Java, and therefore runsonallmajor platforms,andis widely usedbecauseits “plugin”- based architecture enables it to be easily extended. While all exam- ples run in ImageJ, they have been specifically designed to be easily ported to other environments and programming languages. Use in research and development This book has been especially designed for use as a textbook and as such features exercises and carefully constructed examples that sup- plement our detailed presentation of the fundamental concepts and techniques. As both practitioners and developers, we know that the details requiredto successfully understand, apply, and extend classi- cal techniques are often difficult to find, and for this reason we have been very careful to provide the missing details, many gleaned over years of practical application. While this should make the text par- ticularly valuable to those in researchand development, it is not de- signedasacomprehensive,fully-citedscientificresearchtext. Onthe contrary, we have carefully vetted our citations so that they can be obtained from easily accessible sources. While we have only briefly discussed the fundamentals of, or entirely omitted, topics such as hierarchicalmethods, wavelets,or eigenimages because of space lim- itations, other topics have been left out deliberately, including ad- vanced issues such as object recognition, image understanding, and three-dimensional (3D) computer vision. So, while most techniques described in this book could be called “blind and dumb”, it is our experience that straightforward, technically clean implementations of these simpler methods are essential to the success of any further domain-specific, or even “intelligent”, approaches. If you are only in search of a programming handbook for Im- ageJ or Java, there are certainly better sources. While the book includes many code examples, programming in and of itself is not our main focus. Instead Java serves as just one important element for describing each technique in a precise and immediately testable way. Classroom use Whether it is called signal processing, image processing, or media computation,themanipulationofdigitalimageshasbeenanintegral part of most computer science and engineering curricula for many years. Today, with the omnipresence of all-digital work flows, it has become an integral part of the required skill set for professionals in many diverse disciplines. Today the topic has migrated into the early stages of many cur- ricula, where it is often a key foundation course. This migration uncoveredaprobleminthatmanyofthetextsreliedonasstandards 1 http://rsb.info.nih.gov/ij/. VI in the older graduate-level courses were not appropriate for begin- Preface ners. The texts were usually too formal for novices,and at the same time did not provide detailed coverage of many of the most popular methods used in actual practice. The result was that educators had a difficult time selecting a single textbook or even finding a compact collection of literature to recommend to their students. Faced with this dilemma ourselves, we wrote this book in the sincere hope of filling this gap. The contents of the following chapters can be presented in either a one- or two-semester sequence. Where feasible, we have added supporting material in order to make each chapter as independent as possible, providing the instructor with maximum flexibility when designingthecourse. Chapters18–20offeracompleteintroductionto thefundamentalspectraltechniquesusedinimageprocessingandare essentially independent of the other materialin the text. Depending onthegoalsoftheinstructorandthecurriculum,theycanbecovered in as much detail as required or completely omitted. The following road map shows a possible partitioning of topics for a two-semester syllabus. Road Map for a 1/2-Semester Syllabus Sem. 1 2 1. Digital Images ........................................ (cid:2) (cid:3) 2. ImageJ ................................................ (cid:2) (cid:3) 3. Histograms and Image Statistics ...................... (cid:2) (cid:3) 4. Point Operations ...................................... (cid:2) (cid:3) 5. Filters ................................................ (cid:2) (cid:3) 6. Edges and Contours ................................... (cid:2) (cid:3) 7. Corner Detection ...................................... (cid:3) (cid:2) 8. The Hough Transform: Finding Simple Curves ........ (cid:3) (cid:2) 9. Morphological Filters ................................. (cid:2) (cid:3) 10. Regions in Binary Images ............................. (cid:2) (cid:3) 11. Automatic Thresholding .............................. (cid:3) (cid:2) 12. Color Images .......................................... (cid:2) (cid:3) 13. Color Quantization .................................... (cid:3) (cid:2) 14. Colorimetric Color Spaces ............................. (cid:3) (cid:2) 15. Filters for Color Images ............................... (cid:3) (cid:2) 16. Edge Detection in Color Images ....................... (cid:3) (cid:2) 17. Edge-Preserving Smoothing Filters .................... (cid:3) (cid:2) 18. Introduction to Spectral Techniques ................... (cid:3) (cid:2) 19. The Discrete Fourier Transform in 2D ................. (cid:3) (cid:2) 20. The Discrete Cosine Transform (DCT) ................ (cid:3) (cid:2) 21. Geometric Operations ................................. (cid:2) (cid:3) 22. Pixel Interpolation .................................... (cid:2) (cid:3) 23. Image Matching and Registration ..................... (cid:2) (cid:3) 24. Non-Rigid Image Matching ............................ (cid:3) (cid:2) 25. Scale-Invariant Local Features (SIFT) ................. (cid:3) (cid:2) 26. Fourier Shape Descriptors ............................. (cid:3) (cid:2) Addendum to the second edition ThissecondeditionisbasedonourcompletelyrevisedGermanthird edition and contains both additional material and severalnew chap- VII Preface ters including: automatic thresholding (Ch. 11), filters and edge de- tection for color images (Chs. 15 and16), edge-preserving smoothing filters(Ch.17),non-rigidimagematching(Ch.24),andFouriershape descriptors (Ch. 26). Much of this new material is presented for the first time at the level of detail necessary to completely understand and create a working implementation. The two final chapters on SIFT and Fourier shape descriptors are particularly detailed to demonstrate the actual level of granu- larity and the special cases which must be considered when actually implementing complex techniques. Some other chapters have been rearrangedorsplitintomultiple partsformoreclarityandeasieruse inteaching. The mathematical notationandprogrammingexamples were completely revised and almost all illustrations were adapted or created anew for this full-color edition. Forthis edition,theImageJ Short Reference andancillarysource code have been relocated from the Appendix and the most re- centlyversionsarefreelyavailableinelectronicformfromthe book’s website. The complete source code, consisting of the common imagingbooklibrary, sample ImageJ plugins for each book chapter, and extended documentation are available from the book’s Source- Forge site.2 Online resources Visit the website for this book www.imagingbook.com to download supplementary materials, including the complete Java sourcecodeforallexamplesandtheunderlyingsoftwarelibrary,full- size test images, useful references, and other supplements. Com- ments, questions, and corrections are welcome and may be ad- dressed to [email protected] Exercises and solutions Each chapter of this book contains a set of sample exercises, mainly forsupportinginstructorstopreparetheirownassignments. Mostof thesetasksareeasytosolveafterstudyingthecorrespondingchapter, while some others may require more elaborated reasoning or experi- mental work. We assume that scholars know best how to select and adapt individual assignments in order to fit the level and interest of their students. This is the main reason why we have abstained from publishing explicit solutions in the past. However, we are happy to answeranypersonalrequestifanexerciseisunclearorseemstoelude a simple solution. Thank you! This book would not have been possible without the understanding and support of our families. Our thanks go to Wayne Rasband at NIH for developing ImageJ and for his truly outstanding support of 2 http://sourceforge.net/projects/imagingbook/. VIII the community and to all our readers of the previous editions who Preface provided valuable input, suggestions for improvement, and encour- agement. The use of open source software for such a project always carries an element of risk, since the long-term acceptance and conti- nuity is difficult to assess. Retrospectively, choosing ImageJ as the software basis for this work was a good decision, and we would con- sider ourselves happy if our book has indirectly contributed to the success of the ImageJ project itself. Finally, we owe a debt of grati- tude to the professionalsatSpringer,particularlyto WayneWheeler and Simon Reeves who were responsible for the English edition. Hagenberg/Washington D.C. Fall 2015 IX