Three-Dimensional Object Recognition from Range Images

Computer Science Workbench is a monograph series which will provide you with an in-depth working knowledge of current developments in computer technology. Every volume in this series will deal with a topic of importance in computer science and elaborate on how you yourself can build systems related to the main theme. You will be able to develop a variety of systems, including computer software tools, computer graphics, computer animation, database management systems, and computer-aided design and manufacturing systems. Computer Science Workbench represents an important new contribution in the field of practical computer technology. T08iyasu L. Kunii PREFACE The primary aim of this book is to present a coherent and self-contained de­ scription of recent advances in three-dimensional object recognition from range images. Three-dimensional object recognition concerns recognition and localiza­ tion of objects of interest in a scene from input images. This problem is one of both theoretical and practical importance. On the theoretical side, it is an ideal vehicle for the study of the general area of computer vision since it deals with several important issues encountered in computer vision-for example, issues such as feature extraction, acquisition, representation and proper use of knowl­ edge, employment of efficient control strategies, coupling numerical and symbolic computations, and parallel implementation of algorithms. On the practical side, it has a wide range of applications in areas such as robot vision, autonomous navigation, automated inspection of industrial parts, and automated assembly.

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.