Algorithms for Image Processing and Computer Vision

Algorithms for Image

Processing and

Computer Vision

Second Edition

Algorithms for Image

Processing and

Computer Vision

Second Edition

J.R. Parker

Wiley Publishing, Inc.

Algorithms for Image Processing and Computer Vision, Second Edition

Published by

Wiley Publishing, Inc.

10475 Crosspoint Boulevard

Indianapolis, IN 46256

www.wiley.com

Copyright  2011 by J.R. Parker

Published by Wiley Publishing, Inc., Indianapolis, Indiana

Published simultaneously in Canada

ISBN: 978-0-470-64385-3

ISBN: 978-1-118-02188-0 (ebk)

ISBN: 978-1-118-02189-7 (ebk)

ISBN: 978-1-118-01962-7 (ebk)

Manufactured in the United States of America

10 9 8 7 6 5 4 3 2 1

No part of this publication may be reproduced, stored in a retrieval system or transmitted in any form or by any means,

electronic, mechanical, photocopying, recording, scanning or otherwise, except as permitted under Sections 107 or 108

of the 1976 United States Copyright Act, without either the prior written permission of the Publisher, or authorization

through payment of the appropriate per-copy fee to the Copyright Clearance Center, 222 Rosewood Drive, Danvers, MA

01923, (978) 750-8400, fax (978) 646-8600. Requests to the Publisher for permission should be addressed to the Permissions

Department, John Wiley & Sons, Inc., 111 River Street, Hoboken, NJ 07030, (201) 748-6011, fax (201) 748-6008, or online at

http://www.wiley.com/go/permissions.

Limit of Liability/Disclaimer of Warranty: The publisher and the author make no representations or warranties with

respect to the accuracy or completeness of the contents of this work and specifically disclaim all warranties, including

without limitation warranties of fitness for a particular purpose. No warranty may be created or extended by sales or

promotional materials. The advice and strategies contained herein may not be suitable for every situation. This work

is sold with the understanding that the publisher is not engaged in rendering legal, accounting, or other professional

services. If professional assistance is required, the services of a competent professional person should be sought. Neither

the publisher nor the author shall be liable for damages arising herefrom. The fact that an organization or Web site is

referred to in this work as a citation and/or a potential source of further information does not mean that the author or the

publisher endorses the information the organization or website may provide or recommendations it may make. Further,

readers should be aware that Internet websites listed in this work may have changed or disappeared between when this

work was written and when it is read.

For general information on our other products and services please contact our Customer Care Department within the

United States at (877) 762-2974, outside the United States at (317) 572-3993 or fax (317) 572-4002.

Wiley also publishes its books in a variety of electronic formats. Some content that appears in print may not be available

in electronic books.

Library of Congress Control Number: 2010939957

Trademarks: Wiley and the Wiley logo are trademarks or registered trademarks of John Wiley & Sons, Inc. and/or its

affiliates, in the United States and other countries, and may not be used without written permission. All other trademarks

are the property of their respective owners. Wiley Publishing, Inc. is not associated with any product or vendor mentioned

in this book.

‘‘Sin lies only in hurting other people unnecessarily.

All other ‘sins’ are invented nonsense.

(Hurting yourself is not a sin — just stupid.)’’

— Robert A. Heinlein

Thanks, Bob.

Credits

Executive Editor

Carol Long

Project Editor

John Sleeva

Technical Editor

Kostas Terzidis

Production Editor

Daniel Scribner

Copy Editor

Christopher Jones

Editorial Director

Robyn B. Siesky

Editorial Manager

Mary Beth Wakefield

Freelancer Editorial

Manager

Rosemarie Graham

Marketing Manager

Ashley Zurcher

Production Manager

Tim Tate

Vice President and Executive

Group Publisher

Richard Swadley

Vice President and Executive

Publisher

Barry Pruett

Associate Publisher

Jim Minatel

Project Coordinator, Cover

Lynsey Stanford

Proofreaders

Nancy Hanger, Paul Sagan

Indexer

Ron Strauss

Cover Image

Ryan Sneed

Cover Designer

 GYRO PHOTOGRAPHY/

amanaimagesRB/Getty Images

vi

About the Author

J.R. Parker is a computer expert and teacher, with special interests in image

processing and vision, video game technologies, and computer simulations.

With a Ph.D. in Informatics from the State University of Gent, Dr. Parker

has taught computer science, art, and drama at the University of Calgary in

Canada, where he is a full professor. He has more than 150 technical papers

and four books to his credit, as well as video games such as the Booze Cruise,

a simulation of impaired driving designed to demonstrate its folly, and a

number of educational games. Jim lives on a small ranch near Cochrane,

Alberta, Canada with family and a host of legged and winged creatures.

vii

About the Technical Editor

Kostas Terzidis is an Associate Professor at the Harvard Graduate School of

Design. He holds a Ph.D. in Architecture from the University of Michigan

(1994), a Masters of Architecture from Ohio State University (1989), and a

Diploma of Engineering from the Aristotle University of Thessaloniki (1986).

His most recent work is in the development of theories and techniques for

the use of algorithms in architecture. His book Expressive Form: A Concep￾tual Approach to Computational Design, published by London-based Spon Press

(2003), offers a unique perspective on the use of computation as it relates to aes￾thetics, specifically in architecture and design. His book Algorithmic Architecture

(Architectural Press/Elsevier, 2006) provides an ontological investigation into

the terms, concepts, and processes of algorithmic architecture and provides

a theoretical framework for design implementations. His latest book, Algo￾rithms for Visual Design (Wiley, 2009), provides students, programmers, and

researchers the technical, theoretical, and design means to develop computer

code that will allow them to experiment with design problems.

viii

Acknowledgments

Thanks this time to Sonny Chan, for the inspiration for the parallel computing

chapter, to Jeff Boyd, for introducing me repeatedly to OpenCV, and to Ralph

Huntsinger and Ghislain C. Vansteenkiste, for getting me into and successfully

out of my Ph.D. program.

Almost all the images used in this book were created by me, using an IBM

PC with a frame grabber and a Sony CCD camera, an HP scanner, and a Sony

Eyetoy as a webcam. Credits for the few images that were not acquired in this

way are as follows:

Corel Corporation made available the color image of the grasshopper on

a leaf shown in Figure 3.33, and also was the origin of the example search

images in Figure 10.5.

The sample images in Figure 10.1 were a part of the ALOI data set, use of

which was allowed by J. M. Geusebroek.

Thanks to Big Hill Veterinary Clinic in Cochrane, Alberta, Canada, for the

X-ray image shown in Figure 3.10e.

Finally, thanks to Dr. N. Wardlaw, of the University of Calgary Department

of Geology, for the geological micropore image of Figure 3.16.

Most importantly, I need to thank my family: my wife, Katrin, and children,

Bailey and Max. They sacrificed time and energy so that this work could be

completed. I appreciate it and hope that the effort has been worthwhile.

ix

Contents at a Glance

Preface xxi

Chapter 1 Practical Aspects of a Vision System — Image Display,

Input/Output, and Library Calls 1

Chapter 2 Edge-Detection Techniques 21

Chapter 3 Digital Morphology 85

Chapter 4 Grey-Level Segmentation 137

Chapter 5 Texture and Color 177

Chapter 6 Thinning 209

Chapter 7 Image Restoration 251

Chapter 8 Classification 285

Chapter 9 Symbol Recognition 321

Chapter 10 Content-Based Search — Finding Images by Example 395

Chapter 11 High-Performance Computing for Vision and Image

Processing 425

Index 465

xi

Contents

Preface xxi

Chapter 1 Practical Aspects of a Vision System — Image Display,

Input/Output, and Library Calls 1

OpenCV 2

The Basic OpenCV Code 2

The IplImage Data Structure 3

Reading and Writing Images 6

Image Display 7

An Example 7

Image Capture 10

Interfacing with the AIPCV Library 14

Website Files 18

References 18

Chapter 2 Edge-Detection Techniques 21

The Purpose of Edge Detection 21

Traditional Approaches and Theory 23

Models of Edges 24

Noise 26

Derivative Operators 30

Template-Based Edge Detection 36

Edge Models: The Marr-Hildreth Edge Detector 39

The Canny Edge Detector 42

The Shen-Castan (ISEF) Edge Detector 48

A Comparison of Two Optimal Edge Detectors 51

xiii