Computer and Machine Vision: Theory, Algorithms, Practicalities

Front Cover......Page 1
Computer and Machine Vision: Theory, Algorithms, Practicalities......Page 4
Copyright Page......Page 5
Contents......Page 6
Foreword......Page 22
Preface......Page 24
About the Author......Page 28
Acknowledgements......Page 30
Glossary of Acronyms and Abbreviations......Page 34
1.1 Introduction—Man and His Senses......Page 38
1.2.1 The Process of Recognition......Page 39
1.2.2 Tackling the Recognition Problem......Page 41
1.2.3 Object Location......Page 43
1.2.4 Scene Analysis......Page 45
1.2.5 Vision as Inverse Graphics......Page 46
1.3 From Automated Visual Inspection to Surveillance......Page 47
1.4 What This Book is About......Page 49
1.5 The Following Chapters......Page 50
1.6 Bibliographical Notes......Page 51
1. Low-Level Vision......Page 52
2 Images and Imaging Operations......Page 54
2.1 Introduction......Page 55
2.1.1 Gray Scale Versus Color......Page 56
2.2 Image Processing Operations......Page 60
2.2.1 Some Basic Operations on Grayscale Images......Page 61
2.2.2 Basic Operations on Binary Images......Page 65
2.3 Convolutions and Point Spread Functions......Page 69
2.4 Sequential Versus Parallel Operations......Page 71
2.7 Problems......Page 73
3.1 Introduction......Page 75
3.2 Noise Suppression by Gaussian Smoothing......Page 77
3.3 Median Filters......Page 80
3.4 Mode Filters......Page 82
3.5 Rank Order Filters......Page 89
3.6 Reducing Computational Load......Page 91
3.7 Sharp–Unsharp Masking......Page 92
3.8 Shifts Introduced by Median Filters......Page 93
3.8.1 Continuum Model of Median Shifts......Page 94
3.8.2 Generalization to Grayscale Images......Page 96
3.8.3 Problems with Statistics......Page 97
3.9 Discrete Model of Median Shifts......Page 99
3.10 Shifts Introduced by Mode Filters......Page 102
3.11 Shifts Introduced by Mean and Gaussian Filters......Page 104
3.12 Shifts Introduced by Rank Order Filters......Page 105
3.12.1 Shifts in Rectangular Neighborhoods......Page 106
3.14 Color in Image Filtering......Page 111
3.15 Concluding Remarks......Page 113
3.16 Bibliographical and Historical Notes......Page 114
3.16.1 More Recent Developments......Page 115
3.17 Problems......Page 116
4 Thresholding Techniques......Page 119
4.2 Region-Growing Methods......Page 120
4.3 Thresholding......Page 121
4.3.1 Finding a Suitable Threshold......Page 122
4.3.2 Tackling the Problem of Bias in Threshold Selection......Page 123
4.3.2.1 Methods Based on Finding a Valley in the Intensity Distribution......Page 124
4.4 Adaptive Thresholding......Page 125
4.4.1 The Chow and Kaneko Approach......Page 128
4.4.2 Local Thresholding Methods......Page 129
4.5 More Thoroughgoing Approaches to Threshold Selection......Page 130
4.5.1 Variance-Based Thresholding......Page 132
4.5.2 Entropy-Based Thresholding......Page 133
4.5.3 Maximum Likelihood Thresholding......Page 134
4.6 The Global Valley Approach to Thresholding......Page 135
4.7 Practical Results Obtained Using the Global Valley Method......Page 138
4.8 Histogram Concavity Analysis......Page 143
4.9 Concluding Remarks......Page 144
4.10 Bibliographical and Historical Notes......Page 145
4.10.1 More Recent Developments......Page 146
4.11 Problems......Page 147
5 Edge Detection......Page 148
5.1 Introduction......Page 149
5.2 Basic Theory of Edge Detection......Page 150
5.3 The Template Matching Approach......Page 152
5.4 Theory of 3×3 Template Operators......Page 153
5.5 The Design of Differential Gradient Operators......Page 154
5.6 The Concept of a Circular Operators......Page 155
5.7 Detailed Implementation of Circular Operators......Page 157
5.8 The Systematic Design of Differential Edge Operators......Page 159
5.9 Problems with the Above Approach—Some Alternative Schemes......Page 160
5.10 Hysteresis Thresholding......Page 163
5.11 The Canny Operator......Page 165
5.12 The Laplacian Operator......Page 168
5.13 Active Contours......Page 171
5.14 Practical Results Obtained Using Active Contours......Page 174
5.15 The Level Set Approach to Object Segmentation......Page 177
5.16 The Graph Cut Approach to Object Segmentation......Page 178
5.17 Concluding Remarks......Page 182
5.18 Bibliographical and Historical Notes......Page 183
5.18.1 More Recent Developments......Page 184
5.19 Problems......Page 185
6 Corner and Interest Point Detection......Page 186
6.2 Template Matching......Page 187
6.3 Second-Order Derivative Schemes......Page 188
6.4 A Median Filter-Based Corner Detector......Page 190
6.4.1 Analyzing the Operation of the Median Detector......Page 191
6.4.2 Practical Results......Page 193
6.5 The Harris Interest Point Operator......Page 195
6.5.1 Corner Signals and Shifts for Various Geometric Configurations......Page 198
6.5.2 Performance with Crossing Points and Junctions......Page 199
6.5.3 Different Forms of the Harris Operator......Page 202
6.6 Corner Orientation......Page 203
6.7 Local Invariant Feature Detectors and Descriptors......Page 205
6.7.1 Harris Scale and Affine-Invariant Detectors and Descriptors......Page 208
6.7.3 The SIFT Operator......Page 210
6.7.4 The SURF Operator......Page 211
6.7.5 Maximally Stable Extremal Regions......Page 213
6.7.6 Comparison of the Various Invariant Feature Detectors......Page 214
6.8 Concluding Remarks......Page 217
6.9 Bibliographical and Historical Notes......Page 218
6.10 Problems......Page 221
7.1 Introduction......Page 222
7.2.2 Cancellation Effects......Page 223
7.3.1 Generalized Morphological Dilation......Page 224
7.3.2 Generalized Morphological Erosion......Page 225
7.3.3 Duality Between Dilation and Erosion......Page 226
7.3.4 Properties of Dilation and Erosion Operators......Page 227
7.3.5 Closing and Opening......Page 230
7.3.6 Summary of Basic Morphological Operations......Page 232
7.4 Grayscale Processing......Page 234
7.4.1 Morphological Edge Enhancement......Page 235
7.4.2 Further Remarks on the Generalization to Grayscale Processing......Page 236
7.5 Effect of Noise on Morphological Grouping Operations......Page 238
7.5.1 Detailed Analysis......Page 240
7.6 Concluding Remarks......Page 242
7.7 Bibliographical and Historical Notes......Page 243
7.7.1 More Recent Developments......Page 244
7.8 Problem......Page 245
8.1 Introduction......Page 246
8.3 Graylevel Co-occurrence Matrices......Page 250
8.4 Laws’ Texture Energy Approach......Page 254
8.5 Ade’s Eigenfilter Approach......Page 257
8.6 Appraisal of the Laws and Ade Approaches......Page 258
8.8 Bibliographical and Historical Notes......Page 260
8.8.1 More Recent Developments......Page 261
2. Intermediate-Level Vision......Page 264
9 Binary Shape Analysis......Page 266
9.2 Connectedness in Binary Images......Page 267
9.3 Object Labeling and Counting......Page 268
9.3.1 Solving the Labeling Problem in a More Complex Case......Page 272
9.4 Size Filtering......Page 275
9.5 Distance Functions and Their Uses......Page 277
9.5.1 Local Maxima and Data Compression......Page 280
9.6 Skeletons and Thinning......Page 281
9.6.1 Crossing Number......Page 284
9.6.2 Parallel and Sequential Implementations of Thinning......Page 285
9.6.5 Skeleton Node Analysis......Page 288
9.6.6 Application of Skeletons for Shape Recognition......Page 290
9.7 Other Measures for Shape Recognition......Page 291
9.9 Concluding Remarks......Page 294
9.10 Bibliographical and Historical Notes......Page 296
9.10.1 More Recent Developments......Page 297
9.11 Problems......Page 298
10.1 Introduction......Page 303
10.3 Centroidal Profiles......Page 306
10.4 Problems with the Centroidal Profile Approach......Page 307
10.4.1 Some Solutions......Page 308
10.5 The (s, ψ) Plot......Page 311
10.6 Tackling the Problems of Occlusion......Page 313
10.7 Accuracy of Boundary Length Measures......Page 316
10.8 Concluding Remarks......Page 317
10.9 Bibliographical and Historical Notes......Page 318
10.10 Problems......Page 319
11.1 Introduction......Page 321
11.2 Application of the Hough Transform to Line Detection......Page 322
11.3 The Foot-of-Normal Method......Page 325
11.4 Longitudinal Line Localization......Page 327
11.5 Final Line Fitting......Page 329
11.6 Using RANSAC for Straight Line Detection......Page 330
11.7 Location of Laparoscopic Tools......Page 334
11.8 Concluding Remarks......Page 336
11.9 Bibliographical and Historical Notes......Page 337
11.10 Problems......Page 338
12 Circle and Ellipse Detection......Page 340
12.1 Introduction......Page 341
12.2 Hough-Based Schemes for Circular Object Detection......Page 342
12.3 The Problem of Unknown Circle Radius......Page 345
12.3.1 Some Practical Results......Page 347
12.4 The Problem of Accurate Center Location......Page 348
12.4.1 A Solution Requiring Minimal Computation......Page 350
12.5.1 More Detailed Estimates of Speed......Page 351
12.5.2 Robustness......Page 352
12.5.3 Practical Results......Page 353
12.5.4 Summary......Page 354
12.6.1 The Diameter Bisection Method......Page 357
12.6.2 The Chord–Tangent Method......Page 359
12.6.3 Finding the Remaining Ellipse Parameters......Page 360
12.7 Human Iris Location......Page 362
12.9 Concluding Remarks......Page 364
12.10 Bibliographical and Historical Notes......Page 365
12.10.1 More Recent Developments......Page 367
12.11 Problems......Page 368
13.1 Introduction......Page 370
13.2 The Generalized Hough Transform......Page 371
13.4 Spatial Matched Filtering in Images......Page 373
13.5 From Spatial Matched Filters to Generalized Hough Transforms......Page 374
13.6.1 Calculation of Sensitivity and Computational Load......Page 376
13.7 Summary......Page 379
13.8 Use of the GHT for Ellipse Detection......Page 380
13.8.1 Practical Details......Page 384
13.9 Comparing the Various Methods......Page 386
13.10 Fast Implementations of the Hough Transform......Page 387
13.11 The Approach of Gerig and Klein......Page 389
13.12 Concluding Remarks......Page 390
13.13 Bibliographical and Historical Notes......Page 391
13.13.1 More Recent Developments......Page 393
13.14 Problems......Page 394
14 Pattern Matching Techniques......Page 395
14.2 A Graph-Theoretic Approach to Object Location......Page 396
14.2.1 A Practical Example—Locating Cream Biscuits......Page 400
14.3 Possibilities for Saving Computation......Page 403
14.4 Using the Generalized Hough Transform for Feature Collation......Page 406
14.4.1 Computational Load......Page 407
14.5 Generalizing the Maximal Clique and Other Approaches......Page 408
14.6 Relational Descriptors......Page 410
14.7 Search......Page 413
14.8 Concluding Remarks......Page 414
14.9 Bibliographical and Historical Notes......Page 415
14.9.1 More Recent Developments......Page 417
14.10 Problems......Page 418
3. 3-D Vision and Motion......Page 424
15.1 Introduction......Page 426
15.2 3-D Vision—the Variety of Methods......Page 427
15.3 Projection Schemes for Three-Dimensional Vision......Page 429
15.3.1 Binocular Images......Page 430
15.3.2 The Correspondence Problem......Page 433
15.4 Shape from Shading......Page 435
15.5 Photometric Stereo......Page 439
15.6 The Assumption of Surface Smoothness......Page 442
15.7 Shape from Texture......Page 444
15.8 Use of Structured Lighting......Page 445
15.9 Three-Dimensional Object Recognition Schemes......Page 447
15.10 Horaud’s Junction Orientation Technique......Page 448
15.11 An Important Paradigm—Location of Industrial Parts......Page 452
15.12 Concluding Remarks......Page 454
15.13 Bibliographical and Historical Notes......Page 456
15.13.1 More Recent Developments......Page 457
15.14 Problems......Page 458
16.1 Introduction......Page 461
16.2 The Phenomenon of Perspective Inversion......Page 462
16.3 Ambiguity of Pose under Weak Perspective Projection......Page 464
16.4 Obtaining Unique Solutions to the Pose Problem......Page 467
16.4.1 Solution of the Three-Point Problem......Page 470
16.5 Concluding Remarks......Page 471
16.6 Bibliographical and Historical Notes......Page 473
16.6.1 More Recent Developments......Page 474
16.7 Problems......Page 475
17 Invariants and Perspective......Page 476
17.1 Introduction......Page 477
17.2 Cross-ratios: the “Ratio of Ratios” Concept......Page 478
17.3 Invariants for Noncollinear Points......Page 482
17.3.1 Further Remarks About the Five-Point Configuration......Page 484
17.4 Invariants for Points on Conics......Page 486
17.5 Differential and Semi-differential Invariants......Page 489
17.6 Symmetric Cross-ratio Functions......Page 491
17.7 Vanishing Point Detection......Page 493
17.8 More on Vanishing Points......Page 495
17.9 Apparent Centers of Circles and Ellipses......Page 497
17.10 The Route to Face Recognition......Page 499
17.10.1 The Face as Part of a 3-D Object......Page 501
17.11 Perspective Effects in Art and Photography......Page 503
17.12 Concluding Remarks......Page 509
17.13 Bibliographical and Historical Notes......Page 511
17.14 Problems......Page 512
18 Image Transformations and Camera Calibration......Page 515
18.2 Image Transformations......Page 516
18.3 Camera Calibration......Page 520
18.4 Intrinsic and Extrinsic Parameters......Page 523
18.5 Correcting for Radial Distortions......Page 525
18.6 Multiple View Vision......Page 527
18.7 Generalized Epipolar Geometry......Page 528
18.8 The Essential Matrix......Page 529
18.9 The Fundamental Matrix......Page 532
18.10 Properties of the Essential and Fundamental Matrices......Page 533
18.12 An Update on the Eight-Point Algorithm......Page 534
18.13 Image Rectification......Page 535
18.14 3-D Reconstruction......Page 536
18.15 Concluding Remarks......Page 538
18.16 Bibliographical and Historical Notes......Page 539
18.16.1 More Recent Developments......Page 540
18.17 Problems......Page 541
19.1 Introduction......Page 542
19.2 Optical Flow......Page 543
19.3 Interpretation of Optical Flow Fields......Page 546
19.4 Using Focus of Expansion to Avoid Collision......Page 548
19.5 Time-to-Adjacency Analysis......Page 550
19.6 Basic Difficulties with the Optical Flow Model......Page 551
19.7 Stereo from Motion......Page 552
19.8 The Kalman Filter......Page 554
19.9 Wide Baseline Matching......Page 556
19.10 Concluding Remarks......Page 558
19.12 Problem......Page 559
4. Toward Real-Time Pattern Recognition Systems......Page 560
20.1 Introduction......Page 562
20.3 The Types of Object to be Inspected......Page 564
20.3.2 Precision Components......Page 565
20.3.3 Differing Requirements for Size Measurement......Page 566
20.4 Summary: The Main Categories of Inspection......Page 567
20.5 Shape Deviations Relative to a Standard Template......Page 569
20.6 Inspection of Circular Products......Page 570
20.7 Inspection of Printed Circuits......Page 574
20.8 Steel Strip and Wood Inspection......Page 575
20.9 Inspection of Products with High Levels of Variability......Page 576
20.10 X-Ray Inspection......Page 579
20.11 The Importance of Color in Inspection......Page 583
20.12 Bringing Inspection to the Factory......Page 585
20.13 Concluding Remarks......Page 586
20.14 Bibliographical and Historical Notes......Page 587
20.14.1 More Recent Developments......Page 589
21.1 Introduction......Page 590
21.2 Case Study: Location of Dark Contaminants in Cereals......Page 591
21.2.1 Application of Morphological and Nonlinear Filters to Locate Rodent Droppings......Page 592
21.2.3 Ergot Detection Using the Global Valley Method......Page 595
21.3.1 The Vectorial Strategy for Linear Feature Detection......Page 597
21.3.2 Designing Linear Feature Detection Masks for Larger Windows......Page 600
21.3.4 Experimental Results......Page 601
21.4.1 Extending an Earlier Sampling Approach......Page 603
21.4.2 Application to Grain Inspection......Page 604
21.4.3 Summary......Page 608
21.5 Optimizing the Output for Sets of Directional Template Masks......Page 609
21.5.1 Application of the Formulae......Page 610
21.5.2 Discussion......Page 611
21.7 Bibliographical and Historical Notes......Page 612
21.7.1 More Recent Developments......Page 613
22 Surveillance......Page 615
22.1 Introduction......Page 616
22.2 Surveillance—The Basic Geometry......Page 617
22.3 Foreground–Background Separation......Page 621
22.3.1 Background Modeling......Page 622
22.3.2 Practical Examples of Background Modeling......Page 628
22.3.3 Direct Detection of the Foreground......Page 630
22.4 Particle Filters......Page 631
22.5 Use of Color Histograms for Tracking......Page 637
22.6 Implementation of Particle Filters......Page 641
22.7 Chamfer Matching, Tracking, and Occlusion......Page 644
22.8 Combining Views from Multiple Cameras......Page 646
22.8.1 The Case of Nonoverlapping Fields of View......Page 650
22.9.1 The System of Bascle et al.......Page 651
22.9.2 The System of Koller et al.......Page 653
22.10 License Plate Location......Page 656
22.11 Occlusion Classification for Tracking......Page 658
22.12 Distinguishing Pedestrians by Their Gait......Page 660
22.13 Human Gait Analysis......Page 664
22.14 Model-Based Tracking of Animals......Page 666
22.15 Concluding Remarks......Page 668
22.16 Bibliographical and Historical Notes......Page 669
22.16.1 More Recent Developments......Page 671
22.17 Problem......Page 672
23 In-Vehicle Vision Systems......Page 673
23.1 Introduction......Page 674
23.2 Locating the Roadway......Page 675
23.3 Location of Road Markings......Page 677
23.4 Location of Road Signs......Page 678
23.5 Location of Vehicles......Page 682
23.6 Information Obtained by Viewing Licence Plates and Other Structural Features......Page 684
23.7 Locating Pedestrians......Page 688
23.8 Guidance and Egomotion......Page 690
23.9 Vehicle Guidance in Agriculture......Page 693
23.9.1 3-D Aspects of the Task......Page 697
23.9.2 Real-Time Implementation......Page 698
23.10 Concluding Remarks......Page 699
23.11 More Detailed Developments and Bibliographies Relating to Advanced Driver Assistance Systems......Page 700
23.11.1 Developments in Vehicle Detection......Page 701
23.11.2 Developments in Pedestrian Detection......Page 703
23.11.3 Developments in Road and Lane Detection......Page 705
23.11.4 Developments in Road Sign Detection......Page 706
23.12 Problem......Page 708
24 Statistical Pattern Recognition......Page 709
24.1 Introduction......Page 710
24.2 The Nearest Neighbor Algorithm......Page 711
24.3 Bayes’ Decision Theory......Page 713
24.3.1 The Naive Bayes’ Classifier......Page 715
24.4.1 Mathematical Statement of the Problem......Page 716
24.5 The Optimum Number of Features......Page 718
24.6 Cost Functions and Error–Reject Tradeoff......Page 719
24.7 The Receiver Operating Characteristic......Page 721
24.7.1 On the Variety of Performance Measures Relating to Error Rates......Page 723
24.8 Multiple Classifiers......Page 725
24.9.1 Supervised and Unsupervised Learning......Page 728
24.9.2 Clustering Procedures......Page 729
24.10 Principal Components Analysis......Page 732
24.11 The Relevance of Probability in Image Analysis......Page 736
24.12 Another Look at Statistical Pattern Recognition: The Support Vector Machine......Page 737
24.13 Artificial Neural Networks......Page 738
24.14 The Back-Propagation Algorithm......Page 742
24.15 MLP Architectures......Page 745
24.16 Overfitting to the Training Data......Page 746
24.17 Concluding Remarks......Page 749
24.18 Bibliographical and Historical Notes......Page 750
24.18.1 More Recent Developments......Page 752
24.19 Problems......Page 754
25.1 Introduction......Page 755
25.2 Illumination Schemes......Page 756
25.2.1 Eliminating Shadows......Page 758
25.2.2 Principles for Producing Regions of Uniform Illumination......Page 761
25.2.3 Case of Two Infinite Parallel Strip Lights......Page 763
25.2.4 Overview of the Uniform Illumination Scenario......Page 766
25.2.5 Use of Line-Scan Cameras......Page 767
25.2.6 Light Emitting Diode (LED) Sources......Page 768
25.3 Cameras and Digitization......Page 769
25.3.1 Digitization......Page 771
25.4 The Sampling Theorem......Page 772
25.5 Hyperspectral Imaging......Page 775
25.6 Concluding Remarks......Page 776
25.7 Bibliographical and Historical Notes......Page 777
25.7.1 More Recent Developments......Page 778
26 Real-Time Hardware and Systems Design Considerations......Page 779
26.1 Introduction......Page 780
26.2 Parallel Processing......Page 781
26.3 SIMD Systems......Page 782
26.4 The Gain in Speed Attainable with N Processors......Page 784
26.5 Flynn’s Classification......Page 785
26.6 Optimal Implementation of Image Analysis Algorithms......Page 787
26.6.1 Hardware Specification and Design......Page 788
26.6.2 Basic Ideas on Optimal Hardware Implementation......Page 789
26.7 Some Useful Real-Time Hardware Options......Page 791
26.8 Systems Design Considerations......Page 792
26.9 Design of Inspection Systems—the Status Quo......Page 794
26.10 System Optimization......Page 797
26.11 Concluding Remarks......Page 798
26.12.1 General Background......Page 800
26.12.2 Developments Since 2000......Page 801
26.12.3 More Recent Developments......Page 802
27.1 Introduction......Page 804
27.2 Parameters of Importance in Machine Vision......Page 805
27.3.1 Some Important Tradeoffs......Page 807
27.3.2 Tradeoffs for Two-Stage Template Matching......Page 808
27.4 Moore’s Law in Action......Page 809
27.5 Hardware, Algorithms, and Processes......Page 810
27.6 The Importance of Choice of Representation......Page 811
27.7 Past, Present, and Future......Page 812
27.8 Bibliographical and Historical Notes......Page 814
A.1 Introduction......Page 815
A.2 Preliminary Definitions and Analysis......Page 817
A.3 The M-Estimator (Influence Function) Approach......Page 820
A.4 The Least Median of Squares Approach to Regression......Page 824
A.5 Overview of the Robustness Problem......Page 827
A.6 The RANSAC Approach......Page 828
A.7 Concluding Remarks......Page 829
A.8 Bibliographical and Historical Notes......Page 830
A.8.1 More Recent Developments......Page 831
A.9 Problem......Page 832
References......Page 833
Author Index......Page 882
Subject Index......Page 898
Color Plates......Page 909