Algorithms for Image Processing and Computer Vision, 2nd Edition

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

Color Edges 53

Source Code for the Marr-Hildreth Edge Detector 58

Source Code for the Canny Edge Detector 62

Source Code for the Shen-Castan Edge Detector 70

Website Files 80

References 82

Chapter 3 Digital Morphology 85

Morphology Defined 85

Connectedness 86

Elements of Digital Morphology—Binary Operations 87

Binary Dilation 88

Implementing Binary Dilation 92

Binary Erosion 94

Implementation of Binary Erosion 100

Opening and Closing 101

MAX—A High-Level Programming Language for Morphology 107

The ‘‘Hit-and-Miss’’ Transform 113

Identifying Region Boundaries 116

Conditional Dilation 116

Counting Regions 119

Grey-Level Morphology 121

Opening and Closing 123

Smoothing 126

Gradient 128

Segmentation of Textures 129

Size Distribution of Objects 130

Color Morphology 131

Website Files 132

References 135

Chapter 4 Grey-Level Segmentation 137

Basics of Grey-Level Segmentation 137

Using Edge Pixels 139

Iterative Selection 140

The Method of Grey-Level Histograms 141

Using Entropy 142

Fuzzy Sets 146

Minimum Error Thresholding 148

Sample Results From Single Threshold Selection 149

The Use of Regional Thresholds 151

Chow and Kaneko 152

Modeling Illumination Using Edges 156

Implementation and Results 159

Comparisons 160

Relaxation Methods 161

Moving Averages 167

Cluster-Based Thresholds 170

Multiple Thresholds 171

Website Files 172

References 173

Chapter 5 Texture and Color 177

Texture and Segmentation 177

A Simple Analysis of Texture in Grey-Level Images 179

Grey-Level Co-Occurrence 182

Maximum Probability 185

Moments 185

Contrast 185

Homogeneity 185

Entropy 186

Results from the GLCM Descriptors 186

Speeding Up the Texture Operators 186

Edges and Texture 188

Energy and Texture 191

Surfaces and Texture 193

Vector Dispersion 193

Surface Curvature 195

Fractal Dimension 198

Color Segmentation 201

Color Textures 205

Website Files 205

References 206

Chapter 6 Thinning 209

What Is a Skeleton? 209

The Medial Axis Transform 210

Iterative Morphological Methods 212

The Use of Contours 221

Choi/Lam/Siu Algorithm 224

Treating the Object as a Polygon 226

Triangulation Methods 227

Force-Based Thinning 228

Definitions 229

Use of a Force Field 230

Subpixel Skeletons 234

Source Code for Zhang-Suen/Stentiford/Holt Combined Algorithm 235

Website Files 246

References 247

Chapter 7 Image Restoration 251

Image Degradations—The RealWorld 251

The Frequency Domain 253

The Fourier Transform 254

The Fast Fourier Transform 256

The Inverse Fourier Transform 260

Two-Dimensional Fourier Transforms 260

Fourier Transforms in OpenCV 262

Creating Artificial Blur 264

The Inverse Filter 270

The Wiener Filter 271

Structured Noise 273

Motion Blur—A Special Case 276

The Homomorphic Filter—Illumination 277

Frequency Filters in General 278

Isolating Illumination Effects 280

Website Files 281

References 283

Chapter 8 Classification 285

Objects, Patterns, and Statistics 285

Features and Regions 288

Training and Testing 292

Variation: In-Class and Out-Class 295

Minimum Distance Classifiers 299

Distance Metrics 300

Distances Between Features 302

Cross Validation 304

Support Vector Machines 306

Multiple Classifiers—Ensembles 309

Merging Multiple Methods 309

Merging Type 1 Responses 310

Evaluation 311

Converting Between Response Types 312

Merging Type 2 Responses 313

Merging Type 3 Responses 315

Bagging and Boosting 315

Bagging 315

Boosting 316

Website Files 317

References 318

Chapter 9 Symbol Recognition 321

The Problem 321

OCR on Simple Perfect Images 322

OCR on Scanned Images—Segmentation 326

Noise 327

Isolating Individual Glyphs 329

Matching Templates 333

Statistical Recognition 337

OCR on Fax Images—Printed Characters 339

Orientation—Skew Detection 340

The Use of Edges 345

Handprinted Characters 348

Properties of the Character Outline 349

Convex Deficiencies 353

Vector Templates 357

Neural Nets 363

A Simple Neural Net 364

A Backpropagation Net for Digit Recognition 368

The Use of Multiple Classifiers 372

Merging Multiple Methods 372

Results From the Multiple Classifier 375

Printed Music Recognition—A Study 375

Staff Lines 376

Segmentation 378

Music Symbol Recognition 381

Source Code for Neural Net Recognition System 383

Website Files 390

References 392

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

Searching Images 395

Maintaining Collections of Images 396

Features for Query by Example 399

Color Image Features 399

Mean Color 400

Color Quad Tree 400

Hue and Intensity Histograms 401

Comparing Histograms 402

Requantization 403

Results from Simple Color Features 404

Other Color-Based Methods 407

Grey-Level Image Features 408

Grey Histograms 409

Grey Sigma—Moments 409

Edge Density—Boundaries Between Objects 409

Edge Direction 410

Boolean Edge Density 410

Spatial Considerations 411

Overall Regions 411

Rectangular Regions 412

Angular Regions 412

Circular Regions 414

Hybrid Regions 414

Test of Spatial Sampling 414

Additional Considerations 417

Texture 418

Objects, Contours, Boundaries 418

Data Sets 418

Website Files 419

References 420

Systems 424

Chapter 11 High-Performance Computing for Vision and Image Processing 425

Paradigms for Multiple-Processor Computation 426

Shared Memory 426

Message Passing 427

Execution Timing 427

Using clock() 428

Using QueryPerformanceCounter 430

The Message-Passing Interface System 432

Installing MPI 432

Using MPI 433

Inter-Process Communication 434

Running MPI Programs 436

Real Image Computations 437

Using a Computer Network—Cluster Computing 440

A Shared Memory System—Using the PC Graphics Processor 444

GLSL 444

OpenGL Fundamentals 445

Practical Textures in OpenGL 448

Shader Programming Basics 451

Vertex and Fragment Shaders 452

Required GLSL Initializations 453

Reading and Converting the Image 454

Passing Parameters to Shader Programs 456

Putting It All Together 457

Speedup Using the GPU 459

Developing and Testing Shader Code 459

Finding the Needed Software 460

Website Files 461

References 461

Index 465