Practical Algorithms for Image Analysis

Review"New to the second edition of this well-designed textbook and reference are sections on Gabor filtering, thresholding by connectivity, and a chapter describing all the programs. The book's focus is on hands-on applications and includes a separate chapter of projects, many of them new to this Contents1 ntroductionage1. 2 Annotated Section Overview1.3A Guided tour2 Global Image Analysis2.1 Intensity Histogram: Global Features232.2 Histogram Transformations: Global enhancement72.3 Combining Images2. 4 Geometric Image Transformati2.5 Color Image Transformations3 Gray-Scale Image Analysis3.1 Local Image Operalions: Convolution593.2 Noisc rcduction3.3 Edge Enhancement and Flat Fielding754 Edge and peak point detectionEdge detecti3.6 Subsampling3.7 Multiresolution analvsis3.8 Template Matching1063.9 Binarization1104 Binary Image Analysis84. 1 Morphological and Cellular Processing2 B4.3 Region electic4.4 Shape Analysis: Gcomctrical Fcaturcs and Momentsl444.5 Advanced Shape Analysis: Fourier Descriptors4.6 Convex Hull of Polygons4.7 Thi1604.8 Linewidth4.9 Global Features and Image Profiles4.10 Hough transformvi Contents5 Analysis of lines and line Patterns1765.1 Chain Coding1785.2 Line Features and Noise Reduction1845.3 Polygonalization5.4 Critical Point detection5.5 Straight-Line Fitting2015.6 Cubic Spline Fitting2065.7 Morphology and Topology of Line Patterns210Analysis of Point Patterns2216. 1 The Voronoi Diagram of Point patterns6.2 Spatial Statistics of Point Patterns: Distribution Functions2286.3 Topology and geometry of cellular patterns2356.4 The k-Nearest-Neighbor (k-NN) Problem2417 Frequency Domain Analysis2467.1 The 2D Discrete Fourier transform7.2 Frequency Domain FilteringAPPENDIX: Synopsis of Important Concepts273A. 1 The Fourier Transform: Spatial Domain Versus Frequency Domain274A2 Linear Systems: Impulse response, Convolution and Transfer Function 278A3 Special-Purpose FiltersA. 4 The whittaker-Shannon Sampling theoremA. 5 Commonly Used Data Structures288Index295Introduction1.1 IntroductionIn this book, we offer guided access to a collection of algorithms for the digital manipulation of images. Our goal is to facilitate the solution of practical problems, addressingusers whose interest is in an informed how-to approach, whether in a technical or ina casual setting. Rather than attempting to be exhaustive, we address salient practicalonsiderations, guiding the selection of a particular approach to commonly encounteredimage processing and analysis tasks, and we present an implementation of our choice ofthe most suitable procedures. This selection of"Practical Algorithms"reflects our ownlong-time users and developers of algorithms and software implementations to process and analyze images in areas as diverse as magnetic domain patternformation and document analysisHOW TO USE THIS BOOKOrganization of Chapters and SectionsThis book contains seven chapters and an appendix. Following this introduction, inSection 1. 2, an annotated section overview is presented, and, in Section 1.3, a guide tothe use of the book and the accompanying collection of algorithms are given. Chapters2-7 present the material of the book in self-contained sections of identical format. Theappendix serves as a review of fundamental concepts to which we refer throughout thetext and provides reference material to the technical literatureEach section contains a header that illustrates the nature of the topic of interest bydescribing typical applications, identifying key words, and providing cross referencesto related topics treated in other sections. Next, the topic of interest is introduced bya description of typical situations requiring a particular processing step or analyticaloperation; the effect of the operation is illustrated by a pictorial example that comprises apair of before and after images Possible strategies of implementation are then discussedand a particular approach is selected for implementation. Annotated references providean introduction to further technical literature. appended to each section is a display ofprogram usage for the code introduced in the sectionSingle-Step ProceduresEach section treats a single primary operation(histogram evaluation, low-pass fil-tering, edge detection, region detection, etc )and introduces requisite algorithms. Each2 ntroductionof the algorithms performs a single transformation on a given input image(ining,)toproduce a modified output image("outing")and, in some cases, output data. Sectionsare self-contained to enable and encourage random access to the most suitable singlestep procedure that solves the particular task of interest. Thus a reader interested in anexposition of simple edge detection techniques would open the book to Section 3.4,while a reader interested in the methodology of Fourier filtering would proceed directlyto section 7.2Multistep ProceduresThe analysis of images usually requires the successive application of multiple trans-formations. These may include simple preprocessing steps(noise removal, flat fielding,feature detection), followed by more complex analytical steps(object shape analysisline pattern analysis, and point pattern analysis ). Multiple individual transformationsmust be concatenated into multistep proceduresTo facilitate the flexible design of multistep procedures, sections are grouped intochapters that bundle common types of analyses(global, local, frequency domain) andcommon types of operations according to the images (gray scale, binary) or classesof patterns within images (lines, points) to which they are applied. Each section provides extensive cross references to enable a reader to construct a logical flow of relatedoperationsI, chapters reflect the order in which procedures are ordinarily applied to any givenage. For example, histogram analysis will precede binarization: filtering and/or flatfielding will precede object shape analysis, line coding will precede line pattern analysis,and Voronoi analysis will precede statistical analysis of point patterns. Spatial frequencyanalysis combines several operations in an alternative approach to the analysis of imagesin the spatial domain, and we choose to present it last. Within chapters, the order ofsections reflects increasing levels of task complexity. This organization suggests anoverall progression from simple and general to complex and specific tasksCodThe book is accompanied by a collection of C programs implementing the algorithms we discuss. All programs operate on existing images; the acquisition of imagesis not discussed here. Versions for two platforms are supplied, as shown belowCode PlatformsPLATFORMC COMPILERMicroSoft DOS(under Windows 95) MicroSoft Visual C++,V.4.0LINUX kernel v 2.0.0GNU gcc, v 2.7.2Code OrganizationSource code is organized in a directory structure such that modules required forbuilding a particular program reside in a subdirectory corresponding to the book sectionin which the program is first invoked For example conv would be stored in a1.1 ntroduction 3subdirectory referring to Section 3. 1. Corresponding LINUX Makefiles and VisualC++ Workspaces are provided to generate executables. Details relating to programcompilation and installation are described in a readme.tXt file contained on thecode distribution disk. In some chapters, additional utilities are provided in a separatesubdirectory to generate test images or to analyze output data filesIn addition, we provide three librariesLIBTIFF, containing functions to handle input and output of imagc files in anuncompressed Tagged Image File(TiF)formaL; LIBTIFF3 4, written by Sam Leflerand madc availablc by Silicon Graphics, Inc, was modified to rcmovc support forLZW compressionLIBIMAGE, containing getopt(), a command linc parser, as wcll as a collectionof higher-level graphics functions to handle drawing, filling, and character generation; portions of LIBIMAGE invoke gd 1.2, written by Tom Boutell and madeavailable by Quest Protein Database Center, Cold Spring Harbor labsLIBIP, containing image analysis functions such as poly-moments()andfind-area-hist()to handle common analytical tasks invoked by multiple pro-gramsAll programs are executed from the command line from which a variety of arguments and options can be supplied to adjust and optimize program performance. Someprograms prompt for additional input during run time. When executed without arguments, each program displays the command with arguments and options definingprogram usage. This usage header also is reproduced at the end of each section forprograms introduced in that sectionNoticesThis sourcc codc is distributed undcr a limitcd-usc liccnsc that onc may vicw byinvoking an appropriate option on the command line ofeach prograrm. Unless otherwiseindicatcd in thc sourcc codc, copyright is jointly hcld by thc authors, as indicatcd bya copyright notice such as Copyright(C)1997, 1998, 1999, M. Seul, L. OGormanM.J. Sammon. In some instances, we use a third-party code in versions available frombublic sources. In those instances, the original authors, as identified in the source coderetain copyrightExcept when otherwise stated in writing, the copyright holders and/or other partiesprovide each program as is without any warranty of any kind, either expressed orimplied, including, but not limited to, the implied warranties of merchantability andfitness for particular purpose. The entire risk as to the quality and performance of theprograms is with the user. Should the program prove defective, the user assumes thecost of all necessary servicing, repair, or correctionIn no event shall any copyright holder be liable for damages including any directindirect, general, special, incidental, or consequential damages arising out of the useor inability to use the programs (including, but not limited to, loss of use or data, databeing rendered inaccurate, losses sustained by the user or third parties, or a failure4 ntroductionof the programs to operate with any other programs), however caused, and under anytheory of liability, whether in contract, strict liability,or tortAcknowledgmentsWe would like to thank those individuals, most notably our editor, Lauren Cowleswho have contributed to this book. This publication includes images from Corel StockPhoto Library, which are protected by the copyright laws of the United States, Canada,and elsewhere and are used under license. Images and other printed materials havebccn rcproduced with permission from the following sources listed in the ordcr of firstappearance and further identified in the referenced sections: [O' Gorman et al 85igs. 2.1.1, 2.2.2, 2.2.5,,, 5.6.1: [CSPL-Corcl Stock Photo L ibrary/CorclGroup]-Figs.2.2.1,2.2.6,2..1,3.6.1,3.7.1.4.9.2,5.5.1,7.1.6,7.1.7;[ Morgan andSeul 95]- Figs. 2.3. 1, 3.3.1; WOodward and Zasadzinski 96]-Fig 2 4.1; [The BellLabs Technical journal-Fig. 2.4.6; Costello]-Figs.3. 1. 1 B, 7.1.1; Gonzalez andWoods 92]-FigS. 3.1.3, 3.1.4, 3.4.2: [Lucent Technologies- Bell Laboratories PhysicalSciences Image library-Figs. 3.2.1, 3.2.4, 4.3.1; Seul et al 921-Figs. 3.3.2, 5.3.2,5.7.2-5; [Canny 86]- Fig. 3.5.2 Boie et al 86]-Figs. 3.5.3, 3.5.4: [Seul et al 91]Figs. 4.3.2, 43.3, 4.5.2, 4.5.3: Attneave 54 -Fig 5.4.2; Seul and Wolfe 92b-Fig5.7.1; [Seul and Wolfe 92A]- Fig 5.7.6: [Preparata and Shamos 85]- Figs. 6.1.26.1.4; Ashcroft and Mermin 76]-Fig. 6.1.2; [ Fortune 87-Fig 6 1. 5; [Sire and Seu951-Figs. 6.3. 1-3, 6.4.1; [Seul and Chen 931-Fig. 7. 1. 8: [Goodman 68]-Figs. 7.2A 3; Bracewell 86- Figs. Al, A 2, [Sessions 89]-Fig. A 4; Kruse et al 911F1g. A.53-s∽Oaug5月s≌×255,5a25它0O>>C28月393=9E353三9T日只月5EcE山zu0可28533∽OaOFau三8员5EE8Qo>>u2OO658四E=99s;5A∠OEOu