Analysis and Interpretation of Range Images

Computer vision researchers have been frustrated in their attempts to automatically derive depth information from conventional two-dimensional intensity images. Research on "shape from texture", "shape from shading", and "shape from focus" is still in a laboratory stage and had not seen much use in commercial machine vision systems. A range image or a depth map contains explicit information about the distance from the sensor to the object surfaces within the field of view in the scene. Information about "surface geometry" which is important for, say, three-dimensional object recognition is more easily extracted from "2 1/2 D" range images than from "2D" intensity images. As a result, both active sensors such as laser range finders and passive techniques such as multi-camera stereo vision are being increasingly utilized by vision researchers to solve a variety of problems. This book contains chapters written by distinguished computer vision researchers covering the following areas: Overview of 3D Vision Range Sensing Geometric Processing Object Recognition Navigation Inspection Multisensor Fusion A workshop report, written by the editors, also appears in the book. It summarizes the state of the art and proposes future research directions in range image sensing, processing, interpretation, and applications. The book also contains an extensive, up-to-date bibliography on the above topics. This book provides a unique perspective on the problem of three-dimensional sensing and processing; it is the only comprehensive collection of papers devoted to range images. Both academic researchers interested in research issues in 3D vision and industrial engineers in search of solutions to particular problems will find this a useful reference book.

Table of Contents:
1 Report: 1988 NSF Range Image Understanding Workshop.- 1.1 Introduction.- 1.2 Issues in Sensing and Sensors.- 1.2.1 General Background.- 1.2.2 Popular 3D Range Sensors.- 1.2.3 Other 3D Sensing Techniques.- 1.2.4 Needs of Five Major Application Areas.- 1.2.5 Example: ERIM Range Sensor Specs..- 1.2.6 Status of Moire Technology..- 1.2.7 Commonly Cited Problems in Range Sensing.- 1.2.8 Future Efforts.- 1.3 Early Processing.- 1.3.1 Issues in Early Processing of Range Images.- 1.3.2 Definition of "Early" Processing.- 1.3.3 Surface Geometry.- 1.3.4 Early Processing Algorithms.- 1.3.5 Summary.- 1.4 Obejct Recognition.- 1.4.1 Matching.- 1.4.2 Modeling.- 1.5 Sensor Integration.- 1.6 Range Sensing for Navigation.- 1.6.1 System Parameters, and Navigational Tasks, and Representation.- 1.6.2 Case 1: An Underwater Surveyor.- 1.6.3 Case 2: Surveying an Urban Environment.- 1.7 Applications Group Report.- 1.8 Appendix.- 1.8.1 Overview Speakers.- 1.8.2 List of Participants.- 1.8.3 Workshop Groups and Group Chairs.- 2 A Rule-Based Approach to Binocular Stereopsis.- 2.1 Introduction..- 2.2 The MPG Approach to Binocular Fusion.- 2.2.1 Brief Review of the Coarse-to-Fine Matching Strategy.- 2.2.2 Some Computational Aspects of the MPG Algorithm.- 2.2.3 Problems With The MPG Approach.- 2.3 Review of Procedures for Stereo Matching Under High-level Constraints.- 2.3.1 Matching Using Geometrical Constraints.- 2.3.2 The Constraint on the Ordering of Features.- 2.3.3 Looser Ordering Constraint.- 2.3.4 Some Other Approaches.- 2.4 Matching Methods Included in the Rule-based Program.- 2.4.1 Dominant Feature Matching.- 2.4.2 Geometrically Constrained Matching.- 2.4.3 Matching of Zero-Crossing Contours.- 2.4.4 The Default Matcher.- 2.5 A Review of Some Important Rules.- 2.5.1 Overview of the Rule-Based Procedure.- 2.5.2 Some GROUP-1 Rules.- 2.6 Experimental Results.- 2.6.1 Experimental Setup.- 2.6.2 Stereo Images and Depth Maps.- 2.6.3 Comparison with the MPG Algorithm.- 2.7 Conclusions.- 3 Geometric Signal Processing.- 3.1 Introduction.- 3.2 Machine Perception.- 3.3 Geometric Representations.- 3.4 Geometric Sensors.- 3.5 Geometric Signal Modeling.- 3.5.1 Geometric Noise Modeling.- 3.6 Geometric Descriptions.- 3.6.1 Planar Curves.- 3.6.2 Space Curves.- 3.6.3 Surfaces.- 3.6.4 Volumes.- 3.6.5 Summary of Geometric Descriptions.- 3.7 Geometric Approximation.- 3.7.1 Local Approximation Methods.- 3.7.2 Global Approximation Methods.- 3.7.3 Function Approximation Comparisons.- 3.7.4 Other Methods of Interest.- 3.8 Robust Approximation.- 3.8.1 Robust M-Estimation.- 3.8.2 Basic Examples.- 3.9 Emerging Themes.- 4 Segmentation versus object representation - are they separable?.- 4.1 Introduction.- 4.2 The Role of Shape Primitives.- 4.3 Segmentation Process.- 4.3.1 Segmentation using volumetric representation.- 4.3.2 Segmentation using boundary information.- 4.3.3 Segmentation using surface primitives.- 4.4 Control Structure.- 4.5 Results.- 4.6 Summary.- 5 Object Recognition.- 5.1 Introduction.- 5.2 Aspects of the Object Recognition Problem.- 5.3 Recognition via Matching Sensed Data to Models.- 5.4 The Statistical Pattern Recognition Approach.- 5.4.1 Object as Feature Vector.- 5.4.2 The Pattern Recognition Paradigm.- 5.4.3 Piecewise Linear Decision Surfaces.- 5.4.4 k-Nearest Neighbors.- 5.4.5 Prototype matching.- 5.4.6 Sequential Decision-making.- 5.5 Object Represented as Geometric Aggregate.- 5.5.1 The Registration Paradigm.- 5.5.2 Pose Clustering Algorithm.- 5.5.3 Sequential Hypothesize and Test.- 5.5.4 Comparison of PC and H&T.- 5.6 Object as an Articulated Set of Parts.- 5.7 Concluding Discussion.- 6 Applications of Range Image Sensing and Processing.- 6.1 Introduction.- 6.2 Major Industrial Application Areas.- 6.2.1 Integrity and Placement Verification.- 6.2.2 Surface Inspection.- 6.2.3 Metrology.- 6.2.4 Guidance and Control.- 6.2.5 Modeling.- 6.3 Obstacles to Practical Application.- 6.3.1 Reflectance Dynamic Range.- 6.3.2 Surface Reflectance Artifacts.- 6.3.3 Secondary Reflections.- 6.3.4 Shadowing and Occlusion.- 6.3.5 Sensor Scanning and Transport.- 6.3.6 Surface Feature Extraction.- 6.4 Conclusion.- 7 3-D Vision Techniques for Autonomous Vehicles.- 7.1 Introduction.- 7.2 Active range and reflectance sensing.- 7.2.1 From range pixels to points in space.- 7.2.2 Reflectance images.- 7.2.3 Resolution and noise.- 7.3 Terrain representations.- 7.3.1 The elevation map as the data structure for terrain representation.- 7.3.2 Terrain representations and path planners.- 7.3.3 Low resolution: Obstacle map.- 7.3.4 Medium resolution: Polygonal terrain map.- 7.3.5 High resolution: Elevation maps for rough terrain.- 7.4 Combining multiple terrain maps.- 7.4.1 The terrain matching problem: iconic vs. feature-based.- 7.4.2 Feature-based matching.- 7.4.3 Iconic matching from elevation maps.- 7.5 Combining range and intensity data.- 7.5.1 The geometry of video cameras.- 7.5.2 The registration problem.- 7.5.3 Application to outdoor scene analysis.- 7.6 Conclusion.- 8 Multisensor Fusion for Automatic Scene Interpretation.- 8.1 Introduction.- 8.2 Image Models.- 8.2.1 Classes of Models.- 8.2.2 Some Examples of Image Models.- 8.3 Intersensory Verification of Image Features.- 8.3.1 Issues.- 8.3.2 Examples of Intersensory Verification of Image Features.- 8.4 Intersensory Verification from Physical Principles.- 8.4.1 Issues.- 8.4.2 Recent Work in Intersensory Analysis Using Physical Principles.- 8.5 Multisensory Vision - An Illustrative Example.- 8.6 Conclusions.