Digital ImageProcessingThird EditionRafael C. GonzalezUniversity of TennesseeRichard E. WoodsMedData InteractiveUpper Saddle River, NJ 07458GONZ_FMv3.qxd 7/26/07 9:05 AM Page iLibrary of Congress Cataloging-in-Publication Data on FileVice President and Editorial Director, ECS: Marcia J. HortonExecutive Editor: Michael McDonaldAssociate Editor: Alice DworkinEditorial Assistant: William OpaluchManaging Editor: Scott DisannoProduction Editor: Rose KernanDirector of Creative Services: Paul BelfantiCreative Director: Juan LopezArt Director: Heather ScottArt Editors: Gregory Dulles and Thomas BenfattiManufacturing Manager: Alexis Heydt-LongManufacturing Buyer: Lisa McDowellSenior Marketing Manager: Tim Galligan© 2008 by Pearson Education, Inc.Pearson Prentice HallPearson Education, Inc.Upper Saddle River, New Jersey 07458All rights reserved. No part of this book may be reproduced, in any form, or by any means, withoutpermission in writing from the publisher.Pearson Prentice Hall®is a trademark of Pearson Education, Inc.The authors and publisher of this book have used their best efforts in preparing this book.These efforts includethe development, research, and testing of the theories and programs to determine their effectiveness. The authorsand publisher make no warranty of any kind, expressed or implied, with regard to these programs or thedocumentation contained in this book.The authors and publisher shall not be liable in any event for incidental orconsequential damages with, or arising out of, the furnishing, performance, or use of these programs.Printed in the United States of America.10987654321ISBN 0-13-168728-x978-0-13-168728-8Pearson Education Ltd., LondonPearson Education Australia Pty. Ltd., SydneyPearson Education Singapore, Pte., Ltd.Pearson Education North Asia Ltd., Hong KongPearson Education Canada, Inc., TorontoPearson Educación de Mexico, S.A. de C.V.Pearson Education—Japan, TokyoPearson Education Malaysia, Pte. Ltd.Pearson Education, Inc., Upper Saddle River, New JerseyGONZ_FMv3.qxd 7/26/07 9:05 AM Page iiPrefaceWhen something can be read without effort, great effort has gone into its writing.Enrique Jardiel PoncelaThis edition of Digital Image Processing is a major revision of the book. As inthe 1977 and 1987 editions by Gonzalez and Wintz, and the 1992 and 2002 edi-tions by Gonzalez and Woods, this fifth-generation edition was prepared withstudents and instructors in mind.The principal objectives of the book continueto be to provide an introduction to basic concepts and methodologies for digi-tal image processing, and to develop a foundation that can be used as the basisfor further study and research in this field. To achieve these objectives, wefocused again on material that we believe is fundamental and whose scope ofapplication is not limited to the solution of specialized problems. The mathe-matical complexity of the book remains at a level well within the grasp ofcollege seniors and first-year graduate students who have introductory prepa-ration in mathematical analysis, vectors, matrices, probability, statistics, linearsystems, and computer programming. The book Web site provides tutorials tosupport readers needing a review of this background material.One of the principal reasons this book has been the world leader in its fieldfor more than 30 years is the level of attention we pay to the changing educa-tional needs of our readers. The present edition is based on the most extensivesurvey we have ever conducted. The survey involved faculty, students, and in-dependent readers of the book in 134 institutions from 32 countries.The majorfindings of the survey indicated a need for:● A more comprehensive introduction early in the book to the mathemati-cal tools used in image processing.● An expanded explanation of histogram processing techniques.● Stating complex algorithms in step-by-step summaries.● An expanded explanation of spatial correlation and convolution.● An introduction to fuzzy set theory and its application to image processing.● A revision of the material dealing with the frequency domain, startingwith basic principles and showing how the discrete Fourier transform fol-lows from data sampling.● Coverage of computed tomography (CT).● Clarification of basic concepts in the wavelets chapter.● A revision of the data compression chapter to include more video com-pression techniques, updated standards, and watermarking.● Expansion of the chapter on morphology to include morphological recon-struction and a revision of gray-scale morphology.xvGONZ_FMv3.qxd 7/26/07 9:05 AM Page xvxvi ■ Preface● Expansion of the coverage on image segmentation to include more ad-vanced edge detection techniques such as Canny’s algorithm, and a morecomprehensive treatment of image thresholding.● An update of the chapter dealing with image representation and description.● Streamlining the material dealing with structural object recognition.The new and reorganized material that resulted in the present edition is ourattempt at providing a reasonable degree of balance between rigor, clarity ofpresentation, and the findings of the market survey, while at the same timekeeping the length of the book at a manageable level. The major changes inthis edition of the book are as follows.Chapter 1: A few figures were updated and part of the text was rewritten tocorrespond to changes in later chapters.Chapter 2: Approximately 50% of this chapter was revised to include newimages and clearer explanations. Major revisions include a new section onimage interpolation and a comprehensive new section summarizing theprincipal mathematical tools used in the book. Instead of presenting “dry”mathematical concepts one after the other, however, we took this opportu-nity to bring into Chapter 2 a number of image processing applications thatwere scattered throughout the book. For example, image averaging andimage subtraction were moved to this chapter to illustrate arithmetic opera-tions.This follows a trend we began in the second edition of the book to moveas many applications as possible early in the discussion not only as illustra-tions, but also as motivation for students. After finishing the newly organizedChapter 2, a reader will have a basic understanding of how digital images aremanipulated and processed.This is a solid platform upon which the rest of thebook is built.Chapter 3: Major revisions of this chapter include a detailed discussion ofspatial