Dedication

Topics Covered in Application Case Studies

Influences Impinging upon Integrated Vision System Design

Foreword

Preface

About the Author

Acknowledgements

Glossary of Acronyms and Abbreviations

Chapter 1. Vision, the Challenge

1.1 Introduction—Man and His Senses

1.2 The Nature of Vision

1.3 From Automated Visual Inspection to Surveillance

1.4 What This Book is About

1.5 The Following Chapters

1.6 Bibliographical Notes

PART 1. Low-level Vision

Chapter 2. Images and Imaging Operations

2.1 Introduction

2.2 Image Processing Operations

2.3 Convolutions and Point Spread Functions

2.4 Sequential Versus Parallel Operations

2.5 Concluding Remarks

2.6 Bibliographical and Historical Notes

2.7 Problems

Chapter 3. Basic Image Filtering Operations

3.1 Introduction

3.2 Noise Suppression by Gaussian Smoothing

3.3 Median Filters

3.4 Mode Filters

3.5 Rank Order Filters

3.6 Reducing Computational Load

3.7 Sharp–Unsharp Masking

3.8 Shifts Introduced by Median Filters

3.9 Discrete Model of Median Shifts

3.10 Shifts Introduced by Mode Filters

3.11 Shifts Introduced by Mean and Gaussian Filters

3.12 Shifts Introduced by Rank Order Filters

3.13 The Role of Filters in Industrial Applications of Vision

3.14 Color in Image Filtering

3.15 Concluding Remarks

3.16 Bibliographical and Historical Notes

3.17 Problems

Chapter 4. Thresholding Techniques

4.1 Introduction

4.2 Region-Growing Methods

4.3 Thresholding

4.4 Adaptive Thresholding

4.5 More Thoroughgoing Approaches to Threshold Selection

4.6 The Global Valley Approach to Thresholding

4.7 Practical Results Obtained Using the Global Valley Method

4.8 Histogram Concavity Analysis

4.9 Concluding Remarks

4.10 Bibliographical and Historical Notes

4.11 Problems

Chapter 5. Edge Detection

5.1 Introduction

5.2 Basic Theory of Edge Detection

5.3 The Template Matching Approach

5.4 Theory of 3×3 Template Operators

5.5 The Design of Differential Gradient Operators

5.6 The Concept of a Circular Operator

5.7 Detailed Implementation of Circular Operators

5.8 The Systematic Design of Differential Edge Operators

5.9 Problems with the Above Approach—Some Alternative Schemes

5.10 Hysteresis Thresholding

5.11 The Canny Operator

5.12 The Laplacian Operator

5.13 Active Contours

5.14 Practical Results Obtained Using Active Contours

5.15 The Level Set Approach to Object Segmentation

5.16 The Graph Cut Approach to Object Segmentation

5.17 Concluding Remarks

5.18 Bibliographical and Historical Notes

5.19 Problems

Chapter 6. Corner and Interest Point Detection

6.1 Introduction

6.2 Template Matching

6.3 Second-Order Derivative Schemes

6.4 A Median Filter-Based Corner Detector

6.5 The Harris Interest Point Operator

6.6 Corner Orientation

6.7 Local Invariant Feature Detectors and Descriptors

6.8 Concluding Remarks

6.9 Bibliographical and Historical Notes

6.10 Problems

Chapter 7. Mathematical Morphology

7.1 Introduction

7.2 Dilation and Erosion in Binary Images

7.3 Mathematical Morphology

7.4 Grayscale Processing

7.5 Effect of Noise on Morphological Grouping Operations

7.6 Concluding Remarks

7.7 Bibliographical and Historical Notes

7.8 Problem

Chapter 8. Texture

8.1 Introduction

8.2 Some Basic Approaches to Texture Analysis

8.3 Graylevel Co-Occurrence Matrices

8.4 Laws’ Texture Energy Approach

8.5 Ade’s Eigenfilter Approach

8.6 Appraisal of the Laws and Ade Approaches

8.7 Concluding Remarks

8.8 Bibliographical and Historical Notes

PART 2. Intermediate-level Vision

Chapter 9. Binary Shape Analysis

9.1 Introduction

9.2 Connectedness in Binary Images

9.3 Object Labeling and Counting

9.4 Size Filtering

9.5 Distance Functions and their Uses

9.6 Skeletons and Thinning

9.7 Other Measures for Shape Recognition

9.8 Boundary Tracking Procedures

9.9 Concluding Remarks

9.10 Bibliographical and Historical Notes

9.11 Problems

Chapter 10. Boundary Pattern Analysis

10.1 Introduction

10.2 Boundary Tracking Procedures

10.3 Centroidal Profiles

10.4 Problems with the Centroidal Profile Approach

10.5 The (s, ψ) Plot

10.6 Tackling the Problems of Occlusion

10.7 Accuracy of Boundary Length Measures

10.8 Concluding Remarks

10.9 Bibliographical and Historical Notes

10.10 Problems

Chapter 11. Line Detection

11.1 Introduction

11.2 Application of the Hough Transform to Line Detection

11.3 The Foot-of-Normal Method

11.4 Longitudinal Line Localization

11.5 Final Line Fitting

11.6 Using RANSAC for Straight Line Detection

11.7 Location of Laparoscopic Tools

11.8 Concluding Remarks

11.9 Bibliographical and Historical Notes

11.10 Problems

Chapter 12. Circle and Ellipse Detection

12.1 Introduction

12.2 Hough-Based Schemes for Circular Object Detection

12.3 The Problem of Unknown Circle Radius

12.4 The Problem of Accurate Center Location

12.5 Overcoming the Speed Problem

12.6 Ellipse Detection

12.7 Human Iris Location

12.8 Hole Detection

12.9 Concluding Remarks

12.10 Bibliographical and Historical Notes

12.11 Problems

Chapter 13. The Hough Transform and Its Nature

13.1 Introduction

13.2 The Generalized Hough Transform

13.3 Setting Up the Generalized Hough Transform—Some Relevant Questions

13.4 Spatial Matched Filtering in Images

13.5 From Spatial Matched Filters to Generalized Hough Transforms

13.6 Gradient Weighting Versus Uniform Weighting

13.7 Summary

13.8 Use of the GHT for Ellipse Detection

13.9 Comparing the Various Methods

13.10 Fast Implementations of the Hough Transform

13.11 The Approach of Gerig and Klein

13.12 Concluding Remarks

13.13 Bibliographical and Historical Notes

13.14 Problems

Chapter 14. Pattern Matching Techniques

14.1 Introduction

14.2 A Graph-Theoretic Approach to Object Location

14.3 Possibilities for Saving Computation

14.4 Using the Generalized Hough Transform for Feature Collation

14.5 Generalizing the Maximal Clique and Other Approaches

14.6 Relational Descriptors

14.7 Search

14.8 Concluding Remarks

14.9 Bibliographical and Historical Notes

14.10 Problems

PART 3. 3-D Vision and Motion

Chapter 15. The Three-Dimensional World

3-D vision

15.1 Introduction

15.2 3-D Vision—The Variety of Methods

15.3 Projection Schemes for Three-Dimensional Vision

15.4 Shape from Shading

15.5 Photometric Stereo

15.6 The Assumption of Surface Smoothness

15.7 Shape from Texture

15.8 Use of Structured Lighting

15.9 Three-Dimensional Object Recognition Schemes

15.10 Horaud’s Junction Orientation Technique4

15.11 An Important Paradigm—Location of Industrial Parts

15.12 Concluding Remarks

15.13 Bibliographical and Historical Notes

15.14 Problems

Chapter 16. Tackling the Perspective -point Problem

16.1 Introduction

16.2 The Phenomenon of Perspective Inversion

16.3 Ambiguity of Pose Under Weak Perspective Projection

16.4 Obtaining Unique Solutions to the Pose Problem

16.5 Concluding Remarks

16.6 Bibliographical and Historical Notes

16.7 Problems

Chapter 17. Invariants and Perspective

17.1 Introduction

17.2 Cross-Ratios: The “Ratio of Ratios” Concept

17.3 Invariants for Noncollinear Points

17.4 Invariants for Points on Conics

17.5 Differential and Semi-Differential Invariants

17.6 Symmetric Cross-Ratio Functions

17.7 Vanishing Point Detection

17.8 More on Vanishing Points

17.9 Apparent Centers of Circles and Ellipses

17.10 The Route to Face Recognition

17.11 Perspective Effects in Art and Photography*

17.12 Concluding Remarks

17.13 Bibliographical and Historical Notes

17.14 Problems

Chapter 18. Image Transformations and Camera Calibration

18.1 Introduction

18.2 Image Transformations

18.3 Camera Calibration

18.4 Intrinsic and Extrinsic Parameters

18.5 Correcting for Radial Distortions

18.6 Multiple View Vision

18.7 Generalized Epipolar Geometry

18.8 The Essential Matrix

18.9 The Fundamental Matrix

18.10 Properties of the Essential and Fundamental Matrices

18.11 Estimating the Fundamental Matrix

18.12 An Update on the Eight-Point Algorithm

18.13 Image Rectification

18.14 3-D Reconstruction

18.15 Concluding Remarks

18.16 Bibliographical and Historical Notes

18.17 Problems

Chapter 19. Motion

19.1 Introduction

19.2 Optical Flow

19.3 Interpretation of Optical Flow Fields

19.4 Using Focus of Expansion to Avoid Collision

19.5 Time-To-Adjacency Analysis

19.6 Basic Difficulties with the Optical Flow Model

19.7 Stereo from Motion

19.8 The Kalman Filter

19.9 Wide Baseline Matching

19.10 Concluding Remarks

19.11 Bibliographical and Historical Notes

19.12 Problem

PART 4. Toward Real-time Pattern Recognition Systems

Chapter 20. Automated Visual Inspection

20.1 Introduction

20.2 The Process of Inspection

20.3 The Types of Object to be Inspected

20.4 Summary: The Main Categories of Inspection

20.5 Shape Deviations Relative to a Standard Template

20.6 Inspection of Circular Products

20.7 Inspection of Printed Circuits

20.8 Steel Strip and Wood Inspection

20.9 Inspection of Products with High Levels of Variability

20.10 X-Ray Inspection

20.11 The Importance of Color in Inspection

20.12 Bringing Inspection to the Factory

20.13 Concluding Remarks

20.14 Bibliographical and Historical Notes

Chapter 21. Inspection of Cereal Grains

21.1 Introduction

21.2 Case Study: Location of Dark Contaminants in Cereals

21.3 Case Study: Location of Insects

21.4 Case Study: High-Speed Grain Location

21.5 Optimizing the Output for Sets of Directional Template Masks

21.6 Concluding Remarks

21.7 Bibliographical and Historical Notes

Chapter 22. Surveillance

22.1 Introduction

22.2 Surveillance—The Basic Geometry

22.3 Foreground–Background Separation

22.4 Particle Filters

22.5 Use of Color Histograms for Tracking

22.6 Implementation of Particle Filters

22.7 Chamfer Matching, Tracking, and Occlusion

22.8 Combining Views from Multiple Cameras

22.9 Applications to the Monitoring of Traffic Flow

22.10 License Plate Location

22.11 Occlusion Classification for Tracking

22.12 Distinguishing Pedestrians by their Gait

22.13 Human Gait Analysis

22.14 Model-Based Tracking of Animals

22.15 Concluding Remarks

22.16 Bibliographical and Historical Notes

22.17 Problem

Chapter 23. In-Vehicle Vision Systems

23.1 Introduction

23.2 Locating the Roadway

23.3 Location of Road Markings

23.4 Location of Road Signs

23.5 Location of Vehicles

23.6 Information Obtained by Viewing Licence Plates and Other Structural Features

23.7 Locating Pedestrians

23.8 Guidance and Egomotion

23.9 Vehicle Guidance in Agriculture

23.10 Concluding Remarks

23.11 More Detailed Developments and Bibliographies Relating to Advanced Driver Assistance Systems

23.12 Problem

Chapter 24. Statistical Pattern Recognition

24.1 Introduction

24.2 The Nearest Neighbor Algorithm

24.3 Bayes’ Decision Theory

24.4 Relation of the Nearest Neighbor and Bayes’ Approaches

24.5 The Optimum Number of Features

24.6 Cost Functions and Error–Reject Tradeoff

24.7 The Receiver Operating Characteristic

24.8 Multiple Classifiers

24.9 Cluster Analysis

24.10 Principal Components Analysis

24.11 The Relevance of Probability in Image Analysis

24.12 Another Look at Statistical Pattern Recognition: The Support Vector Machine

24.13 Artificial Neural Networks

24.14 The Back-Propagation Algorithm

24.15 MLP Architectures

24.16 Overfitting to the Training Data

24.17 Concluding Remarks

24.18 Bibliographical and Historical Notes

24.19 Problems

Chapter 25. Image Acquisition

25.1 Introduction

25.2 Illumination Schemes

25.3 Cameras and Digitization

25.4 The Sampling Theorem

25.5 Hyperspectral Imaging

25.6 Concluding Remarks

25.7 Bibliographical and Historical Notes

Chapter 26. Real-Time Hardware and Systems Design Considerations

26.1 Introduction

26.2 Parallel Processing

26.3 SIMD Systems

26.4 The Gain in Speed Attainable with N Processors

26.5 Flynn’s Classification

26.6 Optimal Implementation of Image Analysis Algorithms

26.7 Some Useful Real-Time Hardware Options

26.8 Systems Design Considerations

26.9 Design of Inspection Systems—the Status Quo

26.10 System Optimization

26.11 Concluding Remarks

26.12 Bibliographical and Historical Notes7

Chapter 27. Epilogue—Perspectives in Vision

27.1 Introduction

27.2 Parameters of Importance in Machine Vision

27.3 Tradeoffs

27.4 Moore’s Law in Action

27.5 Hardware, Algorithms, and Processes

27.6 The Importance of Choice of Representation

27.7 Past, Present, and Future

27.8 Bibliographical and Historical Notes

APPENDIX A. Robust Statistics

A.1 Introduction

A.2 Preliminary Definitions and Analysis

A.3 The M-Estimator (Influence Function) Approach

A.4 The Least Median of Squares Approach to Regression

A.5 Overview of the Robustness Problem

A.6 The RANSAC Approach

A.7 Concluding Remarks

A.8 Bibliographical and Historical Notes

A.9 Problem

References

Author Index

Subject Index