Three-Dimensional Object Recognition from Range Images

1 Introduction.- 1.1 Computer Vision.- 1.2 Three-Dimensional Object Recognition.- 1.2.1 Representation.- 1.2.2 Indexing.- 1.2.3 Constraint Propagation and Constraint Satisfaction.- 1.3 Common Goals of Three-Dimensional Object Recognition Systems.- 1.4 Qualitative Features.- 1.4.1 Study of Qualitative Properties in Low-level Vision Processes.- 1.4.2 Qualitative Features in Object Recognition.- 1.5 The Scope and Outline of the Book.- I Fundamentals of Range Image Processing and Three-Dimensional Object Recognition.- 2 Range Image Sensors and Sensing Techniques.- 2.1 Range Image Forms.- 2.2 Classification of Range Sensors.- 2.2.1 Radar Sensors.- 2.2.2 Triangulation Sensors.- 2.2.3 Sensors based on Optical Interferometry.- 2.2.4 Sensors Based on Focusing Techniques.- 2.2.5 Sensors Based on Fresnel Diffraction.- 2.2.6 Tactile Range Sensors.- 3 Range Image Segmentation.- 3.1 Mathematical Formulation of Range Image Segmentation.- 3.2 Fundamentals of Surface Differential Geometry.- 3.3 Surface Curvatures.- 3.4 Range Image Segmentation Techniques.- 3.4.1 Edge-based Segmentation Techniques.- 3.4.2 Region-based Segmentation Techniques.- 3.4.3 Hybrid Segmentation Techniques.- 3.5 Summary.- 4 Representation.- 4.1 Formal Properties of Geometric Representations.- 4.2 Wire-Frame Representation.- 4.3 Constructive Solid Geometry (CSG) Representation.- 4.4 Qualitative Representation using Geons.- 4.5 Aspect Graph Representation.- 4.6 EGI Representation.- 4.7 Representation Using Generalized Cylinders.- 4.8 Superquadric Representation.- 4.9 Octree Representation.- 4.10 Summary.- 5 Recognition and Localization Techniques.- 5.1 Recognition and Localization Techniques-An Overview.- 5.2 Interpretation Tree Search.- 5.3 Hough Clustering.- 5.4 Matching of Relational Structures.- 5.5 Geometric Hashing.- 5.6 Iterative Model Fitting.- 5.7 Indexing and Qualitative Features.- 5.8 Vision Systems as Coupled Systems.- 5.8.1 Object-Oriented Representation for Coupled Systems.- 5.8.2 Object-Oriented Representation for 3-D Object Recognition.- 5.8.3 Embedding Parallelism in an Object-Oriented Coupled System.- 5.9 Summary.- II Three-Dimensional Object Recognition Using Qualitative Features.- 6 Polyhedral Object Recognition.- 6.1 Preprocessing and Segmentation.- 6.1.1 Plane Fitting to Pixel Data.- 6.1.2 Clustering in Parameter Space.- 6.1.3 Post Processing of Clustering Results.- 6.1.4 Contour Extraction and Classification.- 6.1.5 Computation of Edge Parameters.- 6.2 Feature Extraction.- 6.3 Interpretation Tree Search.- 6.3.1 Pose Determination.- 6.3.2 Scene Interpretation Hypothesis Verification.- 6.4 Generalized Hough Transform.- 6.4.1 Feature Matching.- 6.4.2 Computation of the Transform.- 6.4.3 Pose Clustering.- 6.4.4 Verification of the Pose Hypothesis.- 6.5 Experimental Results.- 6.6 Summary.- 7 Recognition of Curved Objects.- 7.1 Representation of Curved Surfaces.- 7.1.1 Extraction of Surface Curvature Features from Range Images.- 7.2 Recognition Using a Point-Wise Curvature Description.- 7.2.1 Object Recognition Using Point-Wise Surface Matching.- 7.3 Recognition Using Qualitative Features.- 7.3.1 Cylindrical and Conical Surfaces.- 7.3.2 The Recognition Process Using Qualitative Features.- 7.3.3 Localization of a Cylindrical Surface.- 7.3.4 Localization of a Conical Surface.- 7.3.5 Localization of a Spherical Surface.- 7.3.6 An Experimental Comparison.- 7.4 Recognition of Complex Curved Objects.- 7.5 Dihedral Feature Junctions.- 7.5.1 Types of Dihedral Feature Junctions.- 7.5.2 Matching of Dihedral Feature Junctions.- 7.5.3 Pose Determination.- 7.5.4 Pose Clustering.- 7.6 Experimental Results.- 7.7 Summary.- III Sensitivity Analysis and Parallel Implementation.- 8 Sensitivity Analysis.- 8.1 Junction Matching and Pose Determination.- 8.2 Sensitivity Analysis.- 8.3 Qualitative Features.- 8.4 The Generalized Hough Transform.- 8.4.1 The Generalized Hough Transform in the Absence of Occlusion and Sensor Error.- 8.4.2 The Generalized Hough Transform in Presence of Occlusion and Sensor Error.- 8.4.3 Probability of Spurious Peaks in the Generalized Hough Transform.- 8.5 The Use of Qualitative Features in the Generalized Hough Transform.- 8.5.1 Reduction in the Search Space of Scene Interpretations due to Qualitative Features.- 8.5.2 Reducing the Effect of Smearing in Parameter Space using Qualitative Features.- 8.5.3 The Probability of Random Peaks in the Weighted Generalized Hough Transform.- 8.5.4 Determination of ?k(x), pk(x) and P(k).- 8.6 Weighted Generalized Hough Transform.- 9 Parallel Implementations of Recognition Techniques.- 9.1 Parallel Processing in Computer Vision.- 9.1.1 Parallel Architectures.- 9.1.2 Parallel Algorithms.- 9.2 The Connection Machine.- 9.2.1 System Organization.- 9.2.2 Performance Specifications.- 9.3 Object Recognition on the Connection Machine.- 9.3.1 Feature Extraction.- 9.3.2 Localization of Curved Surfaces.- 9.3.3 Computation of Dihedral Feature Junctions.- 9.3.4 Matching and Pose Computation.- 9.3.5 Pose Clustering.- 9.4 Object Recognition on the Hypercube.- 9.4.1 Scene Description.- 9.4.2 Model Data.- 9.4.3 Scene Feature Data.- 9.4.4 Pruning Constraints.- 9.4.5 Localization.- 9.5 Mapping the Interpretation Tree on the Hypercube.- 9.5.1 Breadth-First Mapping of the Interpretation Tree.- 9.5.2 Depth-First Mapping of the Interpretation Tree.- 9.5.3 Depth-First Mapping of the Interpretation Tree with Load Sharing.- 9.5.4 Experimental Results.