CHAPTER 1 Vision,the Challenge 1
1.1 Introduction―Man and His Senses 1
1.2 The Nature of Vision 2
1.2.1 The Process of Recognition 2
1.2.2 Tackling the Recognition Problem 4
1.2.3 Object Location 6
1.2.4 Scene Analysis 8
1.2.5 Vision as Inverse Graphics 9
1.3 From Automated Visual Inspection to Surveillance 10
1.4 What This Book is About 12
1.5 The Following Chapters 13
1.6 Bibliographical Notes 14
PART 1 LOW-LEVEL VISION 15
CHAPTER 2 Images and Imaging Operations 17
2.1 Introduction 18
2.1.1 Gray Scale Versus Color 19
2.2 Image Processing Operations 23
2.2.1 Some Basic Operations on Grayscale Images 24
2.2.2 Basic Operations on Binary Images 28
2.3 Convolutions and Point Spread Functions 32
2.4 Sequential Versus Parallel Operations 34
2.5 Concluding Remarks 36
2.6 Bibliographical and Historical Notes 36
2.7 Problems 36
CHAPTER 3 Basic Image Filtering Operations 38
3.1 Introduction 38
3.2 Noise Suppression by Gaussian Smoothing 40
3.3 Median Filters 43
3.4 Mode Filters 45
3.5 Rank Order Filters 52
3.6 Reducing Computational Load 54
3.7 Sharp-Unsharp Masking 55
3.8 Shifts Introduced by Median Filters 56
3.8.1 Continuum Model of Median Shifts 57
3.8.2 Generalization to Grayscale Images 59
3.8.3 Problems with Statistics 60
3.9 Discrete Model of Median Shifts 62
3.10 Shifts Introduced by Mode Filters 65
3.11 Shifts Introduced by Mean and Gaussian Filters 67
3.12 Shifts Introduced by Rank Order Filters 68
3.12.1 Shifts in Rectangular Neighborhoods 69
3.13 The Role of Filters in Industrial Applications of Vision 74
3.14 Color in Image Filtering 74
3.15 Concluding Remarks 76
3.16 Bibliographical and Historical Notes 77
3.16.1 More Recent Developments 78
3.17 Problems 79
CHAPTER 4 Thresholding Techniques 82
4.1 Introduction 83
4.2 Region-Growing Methods 83
4.3 Thresholding 84
4.3.1 Finding a Suitable Threshold 85
4.3.2 Tackling the Problem of Bias in Threshold Selection 86
4.3.3 Summary 88
4.4 Adaptive Thresholding 88
4.4.1 The Chow and Kaneko Approach 91
4.4.2 Local Thresholding Methods 92
4.5 More Thoroughgoing Approaches to Threshold Selection 93
4.5.1 Variance-Based Thresholding 95
4.5.2 Entropy-Based Thresholding 96
4.5.3 Maximum Likelihood Thresholding 97
4.6 The Global Valley Approach to Thresholding 98
4.7 Practical Results Obtained Using the Global ValleyMethod 101
4.8 Histogram Concavity Analysis 106
4.9 Concluding Remarks 107
4.10 Bibliographical and Historical Notes 108
4.10.1 More Recent Developments 109
4.11 Problems 110
CHAPTER 5 Edge Detection 111
5.1 Introduction 112
5.2 Basic Theory of Edge Detection 113
5.3 The Template Matching Approach 115
5.4 Theory of 3×3 Template Operators 116
5.5 The Design of Differential Gradient Operators 117
5.6 The Concept of a Circular Operator 118
5.7 Detailed Implementation of Circular Operators 120
5.8 The Systematic Design of Differential Edge Operators 122
5.9 Problems with the Above Approach―Some Alternative Schemes 123
5.10 Hysteresis Thresholding 126
5.11 The Canny Operator 128
5.12 The Laplacian Operator 131
5.13 Active Contours 134
5.14 Practical Results Obtained Using Active Contours 137
5.15 The Level Set Approach to Object Segmentation 140
5.16 The Graph Cut Approach to Object Segmentation 141
5.17 Concluding Remarks 145
5.18 Bibliographical and Historical Notes 146
5.18.1 More Recent Developments 147
5.19 Problems 148
CHAPTER 6 Corner and Interest Point Detection 149
6.1 Introduction 150
6.2 Template Matching 150
6.3 Second-Order Derivative Schemes 151
6.4 A Median Filter-Based Corner Detector 153
6.4.1 Analyzing the Operation of the Median Detector 154
6.4.2 Practical Results 156
6.5 The Harris Interest Point Operator 158
6.5.1 Corner Signals and Shifts for Various Geometric Configurations 161
6.5.2 Performance with Crossing Points and Junctions 162
6.5.3 Different Forms of the Harris Operator 165
6.6 Corner Orientation 166
6.7 Local Invariant Feature Detectors and Descriptors 168
6.7.1 Harris Scale and Affine-Invariant Detectors and Descriptors 171
6.7.2 Hessian Scale and Affine-Invariant Detectors and Descriptors 173
6.7.3 The SIFT Operator 173
6.7.4 The SURF Operator 174
6.7.5 Maximally Stable Extremal Regions 176
6.7.6 Comparison of the Various Invariant Feature Detectors 177
6.8 Concluding Remarks 180
6.9 Bibliographical and Historical Notes 181
6.9.1 More Recent Developments 184
6.10 Problems 184
CHAPTER 7 Mathematical Morphology 185
7.1 Introduction 185
7.2 Dilation and Erosion in Binary Images 186
7.2.1 Dilation and Erosion 186
7.2.2 Cancellation Effects 186
7.2.3 Modified Dilation and Erosion Operators 187
7.3 Mathematical Morphology 187
7.3.1 Generalized Morphological Dilation 187
7.3.2 Generalized Morphological Erosion 188
7.3.3 Duality Between Dilation and Erosion 189
7.3.4 Properties of Dilation and Erosion Operators 190
7.3.5 Closing and Opening 193
7.3.6 Summary of Basic Morphological Operations 195
7.4 Grayscale Processing 197
7.4.1 Morphological Edge Enhancement 198
7.4.2 Further Remarks on the Generalization to Grayscale Processing 199
7.5 Effect of Noise on Morphological Grouping Operations 201
7.5.1 Detailed Analysis 203
7.5.2 Discussion 205
7.6 Concluding Remarks 205
7.7 Bibliographical and Historical Notes 206
7.7.1 More Recent Developments 207
7.8 Problem 208
CHAPTER 8 Texture 209
8.1 Introduction 209
8.2 Some Basic Approaches to Texture Analysis 213
8.3 Graylevel Co-occurrence Matrices 213
8.4 Laws'Texture Energy Approach 217
8.5 Ade's Eigenfilter Approach 220
8.6 Appraisal of the Laws and Ade Approaches 221
8.7 Concluding Remarks 223
8.8 Bibliographical and Historical Notes 223
8.8.1 More Recent Developments 224
PART 2 INTERMEDIATE-LEVEL VISION 227
CHAPTER 9 Binary Shape Analysis 229
9.1 Introduction 230
9.2 Connectedness in Binary Images 230
9.3 Object Labeling and Counting 231
9.3.1 Solving the Labeling Problem in a More Complex Case 235
9.4 Size Filtering 238
9.5 Distance Functions and Their Uses 240
9.5.1 Local Maxima and Data Compression 243
9.6 Skeletons and Thinning 244
9.6.1 Crossing Number 247
9.6.2 Parallel and Sequential Implementations of Thinning 248
9.6.3 Guided Thinning 251
9.6.4 A Comment on the Nature of the Skeleton 251
9.6.5 Skeleton Node Analysis 251
9.6.6 Application of Skeletons for Shape Recognition 253
9.7 Other Measures for Shape Recognition 254
9.8 Boundary Tracking Procedures 257
9.9 Concluding Remarks 257
9.10 Bibliographical and Historical Notes 259
9.10.1 More Recent Developments 260
9.11 Problems 261
CHAPTER 10 Boundary Pattern Analysis 266
10.1 Introduction 266
10.2 Boundary Tracking Procedures 269
10.3 Centroidal Profiles 269
10.4 Problems with the Centroidal Profile Approach 270
10.4.1 Some Solutions 271
10.5 The(s,ψ)Plot 274
10.6 Tackling the Problems of Occlusion 276
10.7 Accuracy of Boundary Length Measures 279
10.8 Concluding Remarks 280
10.9 Bibliographical and Historical Notes 281
10.9.1 More Recent Developments 282
10.10 Problems 282
CHAPTER 11 Line Detection 284
11.1 Introduction 284
11.2 Application of the Hough Transform to Line Detection 285
11.3 The Foot-of-Normal Method 288
11.3.1 Application of the Foot-of-Normal Method 290
11.4 Longitudinal Line Localization 290
11.5 Final Line Fitting 292
11.6 Using RANSAC for Straight Line Detection 293
11.7 Location of Laparoscopic Tools 297
11.8 Concluding Remarks 299
11.9 Bibliographical and Historical Notes 300
11.9.1 More Recent Developments 301
11.10 Problems 301
CHAPTER 12 Circle and Ellipse Detection 303
12.1 Introduction 304
12.2 Hough-Based Schemes for Circular Object Detection 305
12.3 The Problem of Unknown Circle Radius 308
12.3.1 Some Practical Results 310
12.4 The Problem ofAccurate Center Location 311
12.4.1 A Solution Requiring Minimal Computation 313
12.5 Overcoming the Speed Problem 314
12.5.1 More Detailed Estimates of Speed 314
12.5.2 Robustness 315
12.5.3 Practical Results 316
12.5.4 Summary 317
12.6 Ellipse Detection 320
12.6.1 The Diameter Bisection Method 320
12.6.2 The Chord-Tangent Method 322
12.6.3 Finding the Remaining Ellipse Parameters 323
12.7 Human Iris Location 325
12.8 Hole Detection 327
12.9 Concluding Remarks 327
12.10 Bibliographical and Historical Notes 328
12.10.1 More Recent Developments 330
12.11 Problems 331
CHAPTER 13 The Hough Transform and Its Nature 333
13.1 Introduction 333
13.2 The Generalized Hough Transform 334
13.3 Setting Up the Generalized Hough Transform—Some Relevant Questions 336
13.4 Spatial Matched Filtering in Images 336
13.5 From Spatial Matched Filters to Generalized Hough Transforms 337
13.6 Gradient Weighting Versus Uniform Weighting 339
13.6.1 Calculation of Sensitivity and Computational Load 339
13.7 Summary 342
13.8 Use of the GHT for Ellipse Detection 343
13.8.1 Practical Details 347
13.9 Comparing the Various Methods 349
13.10 Fast Implementations of the Hough Transform 350
13.11 The Approach of Gerig and Klein 352
13.12 Concluding Remarks 353
13.13 Bibliographical and Historical Notes 354
13.13.1 More Recent Developments 356
13.14 Problems 357
CHAPTER 14 Pattern Matching Techniques 358
14.1 Introduction 359
14.2 A Graph-Theoretic Approach to Object Location 359
14.2.1 A Practical Example―Locating Cream Biscuits 363
14.3 Possibilities for Saving Computation 366
14.4 Using the Generalized Hough Transform for Feature Collation 369
14.4.1 Computational Load 370
14.5 Generalizing the Maximal Clique and Other Approaches 371
14.6 Relational Descriptors 373
14.7 Search 376
14.8 Concluding Remarks 377
14.9 Bibliographical and Historical Notes 378
14.9.1 More Recent Developments 380
14.10 Problems 381
PART 3 3-D VISION AND MOTION 387
CHAPTER 15 The Three-Dimensional World 389
15.1 Introduction 389
15.2 3-D Vision—the Variety of Methods 390
15.3 Projection Schemes for Three-Dimensional Vision 392
15.3.1 Binocular Images 393
15.3.2 The Correspondence Problem 396
15.4 Shape from Shading 398
15.5 Photometric Stereo 402
15.6 The Assumption of Surface Smoothness 405
15.7 Shape from Texture 407
15.8 Use of Structured Lighting 408
15.9 Three-Dimensional Object Recognition Schemes 410
15.10 Horaud's Junction Orientation Technique 411
15.11 An Important Paradigm―Location of Industrial Parts 415
15.12 Concluding Remarks 417
15.13 Bibliographical and Historical Notes 419
15.13.1 More Recent Developments 420
15.14 Problems 421
CHAPTER 16 Tackling the Perspective n-point Problem 424
16.1 Introduction 424
16.2 The Phenomenon of Perspective Inversion 425
16.3 Ambiguity of Pose under Weak Perspective Projection 427
16.4 Obtaining Unique Solutions to the Pose Problem 430
16.4.1 Solution of the Three-Point Problem 433
16.4.2 Using Symmetric Trapezia for Estimating Pose 434
16.5 Concluding Remarks 434
16.6 Bibliographical and Historical Notes 436
16.6.1 More Recent Developments 437
16.7 Problems 438
CHAPTER 17 Invariants and Perspective 439
17.1 Introduction 440
17.2 Cross-ratios:the“Ratio of Ratios”Concept 441
17.3 Invariants for Noncollinear Points 445
17.3.1 Further Remarks About the Five-Point Configuration 447
17.4 Invariants for Points on Conics 449
17.5 Differential and Semi-difierential Invariants 452
17.6 Symmetric Cross-ratio Functions 454
17.7 Vanishing Point Detection 456
17.8 More on Vanishing Points 458
17.9 Apparent Centers of Circles and Ellipses 460
17.10 The Route to Face Recognition 462
17.10.1 The Face as Part of a 3-D Object 464
17.11 Perspective Effects in Art and Photography 466
17.12 Concluding Remarks 472
17.13 Bibliographical and Historical Notes 474
17.13.1 More Recent Developments 475
17.14 Problems 475
CHAPTER 18 Image Transformations and Camera Calibration 478
18.1 Introduction 479
18.2 Image Transformations 479
18.3 Camera Calibration 483
18.4 Intfinsic and Extrinsic Parameters 486
18.5 Correcting for Radial Distortions 488
18.6 Multiple View Vision 490
18.7 Generalized Epipolar Geometry 491
18.8 The Essential Matrix 492
18.9 The Fundamental Matrix 495
18.10 Properties of the Essential and Fundamental Matrices 496
18.11 Estimating the Fundamental Matrix 497
18.12 An Update on the Eight-Point Algorithm 497
18.13 Image Rectification 498
18.14 3-D Reconstruction 499
18.15 Concluding Remarks 501
18.16 Bibliographical and Historical Notes 502
18.16.1 More Recent Developments 503
18.17 Problems 504
CHAPTER 19 Motion 505
19.1 Introduction 505
19.2 Optical Flow 506
19.3 Interpretation of Optical Flow Fields 509
19.4 Using Focus of Expansion to Avoid Collision 511
19.5 Time-to-Adjacency Analysis 513
19.6 Basic Difficulties with the Optical Flow Model 514
19.7 Stereo from Motion 515
19.8 The Kalman Filter 517
19.9 Wide Baseline Matching 519
19.10 Concluding Remarks 521
19.11 Bibliographical and Historical Notes 522
19.12 Problem 522
PART 4 TOWARD REAL-TIME PATTERN RECOGN ITION SYSTEMS 523
CHAPTER 20 Automated Visual Inspection 525
20.1 Introduction 525
20.2 The Process of Inspection 527
20.3 The Types of Object to be Inspected 527
20.3.1 Food Products 528
20.3.2 Precision Components 528
20.3.3 Differing Requirements for Size Measurement 529
20.3.4 Three-Dimensional Objects 530
20.3.5 Other Products and Materials for Inspection 530
20.4 Summary:The Main Categories of Inspection 530
20.5 Shape Deviations Relative to a Standard Template 532
20.6 Inspection of Circular Products 533
20.7 Inspection of Printed Circuits 537
20.8 Steel Strip and Wood Inspection 538
20.9 Inspection of Products with High Levels of Variability 539
20.10 X-Ray Inspection 542
20.10.1 The Dual-Energy Approach to X-Ray Inspection 546
20.11 The Importance of Color in Inspection 546
20.12 Bringing Inspection to the Factory 548
20.13 Concluding Remarks 549
20.14 Bibliographical and Historical Notes 550
20.14.1 More Recent Developments 552
CHAPTER 21 Inspection of Cereal Grains 553
21.1 Introduction 553
21.2 Case Study:Location of Dark Contaminants in Cereals 554
21.2.1 Application of Morphological and Nonlinear Filters to Locate Rodent Droppings 555
21.2.2 Problems with Closing 558
21.2.3 Ergot Detection Using the Global Valley Method 558
21.3 Case Study:Location of Insects 560
21.3.1 The Vectorial Strategy for Linear Feature Detection 560
21.3.2 Designing Linear Feature Detection Masks for Larger Windows 563
21.3.3 Application to Cereal Inspection 564
21.3.4 Experimental Resuits 564
21.4 Case Study:High-Speed Grain Location 566
21.4.1 Extending an Earlier Sampling Approach 566
21.4.2 Application to Grain Inspection 567
21.4.3 Summary 571
21.5 Optimizing the Output for Sets of Directional Template Masks 572
21.5.1 Application of the Formulae 573
21.5.2 Discussion 574
21.6 Concluding Remarks 575
21.7 Bibliographical and Historical Notes 575
21.7.1 More Recent Developments 576
CHAPTER 22 Surveillance 578
22.1 Introduction 579
22.2 Surveillance—The Basic Geometry 580
22.3 Foreground―Background Separation 584
22.3.1 Background Modeling 585
22.3.2 Practical Examples of Background Modeling 591
22.3.3 Direct Detection of the Foreground 593
22.4 Particle Filters 594
22.5 Use of Color Histograms for Tracking 600
22.6 Implementation of Particle Filters 604
22.7 Chamfer Matching,Tracking,and Occlusion 607
22.8 Combining Views from Multiple Cameras 609
22.8.1 The Case of Nonoverlapping Fields of View 613
22.9 Applications to the Monitoring of Traffic Flow 614
22.9.1 The System of Bascle et al 614
22.9.2 The System of Koller et al 616
22.10 License Plate Location 619
22.11 Occlusion Classification for Tracking 621
22.12 Distinguishing Pedestrians by Their Gait 623
22.13 Human Gait Analysis 627
22.14 Model-Based Tracking of Animals 629
22.15 Concluding Remarks 631
22.16 Bibliographical and Historical Notes 632
22.16.1 More Recent Developments 634
22.17 Problem 635
CHAPTER 23 In-Vehicle Vision Systems 636
23.1 Introduction 637
23.2 Locating the Roadway 638
23.3 Location of Road Markings 640
23.4 Location of Road Signs 641
23.5 Location of Vehicles 645
23.6 Information Obtained by Viewing License Plates and Other Structural Features 647
23.7 Locating Pedestrians 651
23.8 Guidance and Egomotion 653
23.8.1 A Simple Path Planning Algorithm 656
23.9 Vehicle Guidance in Agriculture 656
23.9.1 3-D Aspects of the Task 660
23.9.2 Real-Time Implementation 661
23.10 Concluding Remarks 662
23.11 More Detailed Developments and Bibliographies Relating to Advanced Driver Assistance Systems 663
23.11.1 Developments in Vehicle Detection 664
23.11.2 Developments in Pedestrian Detection 666
23.11.3 Developments in Road and Lane Detection 668
23.11.4 Developments in Road Sign Detection 669
23.11.5 Developments in Path Planning,Navigation, and Egomotion 671
23.12 Problem 671
CHAPTER 24 Statistical Pattern Recognition 672
24.1 Introduction 673
24.2 The Nearest Neighbor Algorithm 674
24.3 Bayes'Decision Theory 676
24.3.1 The Naive Bayes'Classifier 678
24.4 Relation of the Nearest Neighbor and Bayes' Approaches 679
24.4.1 Mathematical Statement of the Problem 679
24.4.2 The Importance of the Nearest Neighbor Classifier 681
24.5 The Optimum Number of Features 681
24.6 Cost Functions and Error-Reject Tradeoff 682
24.7 The Receiver Operating Characteristic 684
24.7.1 On the Variety of Performance Measures Relating to Error Rates 686
24.8 Multiple Classifiers 688
24.9 Cluster Analysis 691
24.9.1 Supervised and Unsupervised Learning 691
24.9.2 Clustering Procedures 692
24.10 Principal Components Analysis 695
24.11 The Relevance of Probability in Image Analysis 699
24.12 Another Look at Statistical Pattern Recognition:The Support Vector Machine 700
24.13 Artificial Neural Networks 701
24.14 The Back-Propagation Algorithm 705
24.15 MLP Architectures 708
24.16 Overfitting to the Training Data 709
24.17 Concluding Remarks 712
24.18 Bibliographical and Historical Notes 713
24.18.1 More Recent Developments 715
24.19 Problems 717
CHAPTER 25 Image Acquisition 718
25.1 Introduction 718
25.2 Illumination Schemes 719
25.2.1 Eliminating Shadows 721
25.2.2 Principles for Producing Regions of Uniform Illumination 724
25.2.3 Case of Two Infinite Parallel Strip Lights 726
25.2.4 Overview of the Uniform Illumination Scenario 729
25.2.5 Use of Line-Scan Cameras 730
25.2.6 Light Emitting Diode(LED)Sources 731
25.3 Cameras and Digitization 732
25.3.1 Digitization 734
25.4 The Sampling Theorem 735
25.5 Hyperspectral Imaging 738
25.6 Concluding Remarks 739
25.7 Bibliographical and Historical Notes 740
25.7.1 More Recent Developments 741
CHAPTER 26 Real-Time Hardware and Systems Design Considerations 742
26.1 Introduction 743
26.2 Parallel Processing 744
26.3 SIMD Systems 745
26.4 The Gain in Speed Attainable with N Processors 747
26.5 Flynn's Classification 748
26.6 Optimal Implementation of Image Analysis Algorithms 750
26.6.1 Hardware Specification and Design 751
26.6.2 Basic Ideas on Optimal Hardware Implementation 752
26.7 Some Useful Real-Time Hardware Options 754
26.8 Systems Design Considerations 755
26.9 Design of Inspection Systems―the Status Quo 757
26.10 System Optimization 760
26.11 Concluding Remarks 761
26.12 Bibliographical and Historical Notes 763
26.12.1 General Background 763
26.12.2 Developments Since 2000 764
26.12.3 More Recent Developments 765
CHAPTER 27 Epilogue―Perspectivesin Vision 767
27.1 Introduction 767
27.2 Parameters of Importance in Machine Vision 768
27.3 Tradeoffs 770
27.3.1 Some Important Tradeoffs 770
27.3.2 Tradeoffs for Two-Stage Template Matching 771
27.4 Moore's Law in Action 772
27.5 Hardware,Algorithms,and Processes 773
27.6 The Importance of Choice of Representation 774
27.7 Past,Present,and Future 775
27.8 Bibliographical and Historical Notes 777
Appendix A Robust Statistics 778
References 796
Author Index 845
Subject Index 861