Object Recognition

Automatie object recognition is a multidisciplinary research area using con­ cepts and tools from mathematics, computing, optics, psychology, pattern recognition, artificial intelligence and various other disciplines. The purpose of this research is to provide a set of coherent paradigms and algorithms for the purpose of designing systems that will ultimately emulate the functions performed by the Human Visual System (HVS). Hence, such systems should have the ability to recognise objects in two or three dimensions independently of their positions, orientations or scales in the image. The HVS is employed for tens of thousands of recognition events each day, ranging from navigation (through the recognition of landmarks or signs), right through to communication (through the recognition of characters or people themselves). Hence, the motivations behind the construction of recognition systems, which have the ability to function in the real world, is unquestionable and would serve industrial (e.g. quality control), military (e.g. automatie target recognition) and community needs (e.g. aiding the visually impaired). Scope, Content and Organisation of this Book This book provides a comprehensive, yet readable foundation to the field of object recognition from which research may be initiated or guided. It repre­ sents the culmination of research topics that I have either covered personally or in conjunction with my PhD students. These areas include image acqui­ sition, 3-D object reconstruction, object modelling, and the matching of ob­ jects, all of which are essential in the construction of an object recognition system.

A — Introduction and Acquisition Systems.- 1. Introduction.- 1.1 What Is Computer Vision?.- 1.2 Background and History.- 1.3 Classification of Existing Vision Systems.- 1.3.1 Marr’s Theory.- 1.3.2 Model-based Object Recognition.- 1.4 Problem Formulation.- 1.4.1 Mathematical Formulation.- 1.5 Why Is Automatic Object Recognition a Difficult Problem?.- 1.6 Motivations and Significance.- 1.6.1 Industry.- 1.6.2 Community.- 1.7 A 2-D System or a 3-D System?.- 1.8 Specifications / Themes of Interest in Object Recognition.- 1.9 Acquisition Systems.- 1.9.1 Intensity Images.- 1.9.2 Range Imaging Technologies.- 1.9.3 Miscellaneous Modalities.- 1.10 Taxonomy.- 2. Stereo Matching and Reconstruction of a Depth Map.- 2.1 Fundamentals of Stereo Vision.- 2.1.1 Stereo Vision Paradigm.- 2.1.2 Image Matching.- 2.1.3 Matching Problems.- 2.2 Review of Existing Techniques.- 2.3 Area-based Techniques.- 2.3.1 Simple Matching Measures.- 2.3.2 Validation Techniques.- 2.3.3 Hierarchical Methods.- 2.3.4 Adaptive Window Techniques.- 2.3.5 Sparse Point Matching.- 2.3.6 Dense Matching.- 2.3.7 Symmetric Multi-Window Technique.- 2.3.8 Unmanned Ground Vehicle Implementation.- 2.3.9 Multiple Baseline Techniques.- 2.3.10 Least Squares Matching.- 2.4 Transform-based Techniques.- 2.4.1 Sign Representation.- 2.4.2 Non-parametric Techniques.- 2.5 Symbolic Feature-based Techniques.- 2.5.1 Zero Crossing Matching.- 2.5.2 Edge Matching.- 2.5.3 Patch Matching.- 2.5.4 Relational Matching.- 2.6 Hybrid Techniques.- 2.6.1 Cross Correlation Combined with Edge Information.- 2.7 Phase-based Techniques.- 2.8 Combining Independent Measurements.- 2.9 Relaxation Techniques.- 2.9.1 Cooperative Algorithm.- 2.9.2 Relaxation Labelling.- 2.10 Dynamic Programming.- 2.10.1 Viterbi Algorithm.- 2.10.2 Intra- and Inter-Scanline Search.- 2.10.3 Disparity Space Image.- 2.11 Object Space Techniques.- 2.11.1 Combining Matching and Surface Reconstruction.- 2.11.2 Object Space Models.- 2.12 Existing Matching Constraints and Diagnostics.- 2.12.1 Matching Constraints.- 2.12.2 Matching Diagnostics.- 2.12.3 Discussion.- 2.13 Conclusions.- A — Summary.- B — Database Creation and Modelling for 3-D Object Recognition.- 3. 3-D Object Creation for Recognition.- 3.1 Preliminaries of 3-D Registration.- 3.2 Registration Paradigm.- 3.2.1 General Specifications.- 3.3 Chronological Literature Review.- 3.4 Fundamental Techniques.- 3.4.1 Registration with Point Correspondences.- 3.4.2 Registration Without Correspondences.- 3.5 Uncertainty in 3-D Registration.- 3.5.1 Weighted Correspondences.- 3.5.2 A Better Approach.- 3.6 Simultaneous Multiple View Registration.- 3.6.1 Simple Approaches.- 3.6.2 Rigid Body Modelling.- 3.6.3 Multiple View Chen and Medioni.- 3.7 View Integration and Surface Reconstruction.- 3.7.1 Integration versus Reconstruction.- 3.7.2 Volumetric Integration Methods.- 3.7.3 Volumetric Reconstruction.- 3.7.4 Geometric Integration Methods.- 3.7.5 Geometric Reconstruction.- 3.8 Registration — Case Study.- 3.8.1 Notation and Terminology.- 3.8.2 Problem Reformulation.- 3.8.3 Iterative Algorithm to Solve for R.- 3.8.4 Results.- 3.8.5 Conclusions.- 3.9 Surface Reconstruction Summary.- 4. Object Representation and Feature Matching.- 4.1 Preliminaries.- 4.2 Object-centred Representations.- 4.2.1 Boundary and Curve-based Representations.- 4.2.2 Axial Descriptions.- 4.2.3 Surface Descriptions.- 4.2.4 Volumetric Descriptions.- 4.3 Viewer-centred Representations.- 4.3.1 Aspect Graphs.- 4.3.2 Silhouettes.- 4.3.3 Principal Component Analysis.- 4.3.4 Miscellaneous Techniques.- 4.4 Representation Conclusions.- 4.5 Matching.- 4.5.1 Hypothesise and Test.- 4.5.2 Relational Structures.- 4.5.3 Pose Clustering.- 4.5.4 Geometric Hashing.- 4.5.5 Interpretation Trees.- 4.5.6 Registration and Distance Transforms.- 4.6 Matching Conclusions.- B — Summary.- C — Vision Systems — Case Studies.- 5. Optical Character Recognition.- 5.1 Examples of Existing Systems.- 5.1.1 Prototype Extraction and Adaptive OCR.- 5.1.2 Direct Grayscale Extraction of Features for Character Recognition.- 5.2 Optical Character Recognition System for Cursive Scripts — A Case Study.- 5.2.1 Background.- 5.2.2 An Overview of the Case Study System.- 5.2.3 The Document Image Analysis Step.- 5.2.4 The Recognition-based Segmentation Step.- 5.2.5 The Feature Extraction Stage.- 5.2.6 Results.- 5.2.7 Conclusions.- 6. Recognition by Parts and Part Segmentation Techniques.- 6.1 Examples of Existing Vision Systems.- 6.1.1 HYPER.- 6.1.2 The Logarithmic Complexity Matching Technique.- 6.2 Recognition by Parts and Part Segmentation — A Case Study.- 6.2.1 The Edge Detection Stage.- 6.2.2 The Part Segmentation Stage.- 6.2.3 Part Isolation.- 6.2.4 The Part Identification Stage.- 6.2.5 The Structural Description and Recognition Stage.- 6.2.6 Results.- 6.2.7 Discussion.- 6.2.8 Conclusions.- 7. 3-D Object Recognition Systems.- 7.1 Examples of Existing Systems.- 7.1.1 ACRONYM.- 7.1.2 SCERPO.- 7.1.3 3DPO.- 7.1.4 PREMIO.- 7.1.5 Recognition of MSTAR Targets.- 7.1.6 Bayesian Recognition by Parts in FLIR.- 7.2 3-D Free-form Object Recognition Using Bayesian Splines A Case Study.- 7.2.1 Preliminaries.- 7.2.2 Bayesian Formulation.- 7.2.3 The RJMCMC Algorithm for Splines.- 7.2.4 Simulated Annealing RJMCMC.- 7.2.5 Matching Splines.- 7.2.6 Results.- 7.2.7 Conclusions.- C — Summary.- Appendices.- A. Vector and Matrix Analysis.- A.1 Preliminaries.- A.1.1 Determinant.- A.1.2 Inversion.- A.2 Derivatives and Integrals of Matrices.- A.3 Vectors and Vector Analysis.- A.4 Eigenvalues and Eigenvectors.- A.5 Quadratic Forms.- B. Principal Component Analysis.- C. Optimisation Fundamentals.- C.1 Fundamental Concepts.- C.2 Linear Least Squares.- C.3 Non-linear Optimisation.- C.4 Direct Search Techniques.- C.4.1 Simplex Method.- C.5 Gradient Methods.- C.5.1 Newton-Raphson Technique.- C.5.2 Davidon-Fletcher-Powell.- C.6 Simulated Annealing.- D. Differential Geometry — Basic Principles.- E. Spline Theory.- E.1 Spline Definitions.- F. Detailed Derivation of Registration Equations.- References.