3D Dynamic Scene Analysis: A Stereo Based Approach (Springer Series in Information Sciences)

he problem of analyzing sequences of images to extract three-dimensional T motion and structure has been at the heart of the research in computer vi sion for many years. It is very important since its success or failure will determine whether or not vision can be used as a sensory process in reactive systems. The considerable research interest in this field has been motivated at least by the following two points: 1. The redundancy of information contained in time-varying images can over come several difficulties encountered in interpreting a single image. 2. There are a lot of important applications including automatic vehicle driv ing, traffic control, aerial surveillance, medical inspection and global model construction. However, there are many new problems which should be solved: how to effi ciently process the abundant information contained in time-varying images, how to model the change between images, how to model the uncertainty inherently associated with the imaging system and how to solve inverse problems which are generally ill-posed. There are of course many possibilities for attacking these problems and many more remain to be explored. We discuss a few of them in this book based on work carried out during the last five years in the Computer Vision and Robotics Group at INRIA (Institut National de Recherche en Informatique et en Automatique). 1. Introduction.- 1.1 Brief Overview of Motion Analysis.- 1.2 Statement of the “Motion from Stereo” Problem.- 1.3 Organization of The Book.- 2. Uncertainty Manipulation and Parameter Estimation.- 2.1 Probability Theory and Geometric Probability.- 2.2 Parameter Estimation.- 2.2.1 Standard Kalman filter.- 2.2.2 Extended Kalman filter.- 2.2.3 Discussion.- 2.2.4 Iterated ExtendKalman Filter.- 2.2.5 Robustness and Confidence Procedure.- 2.3 Summary.- 2.4 Appendix: Least-Squares Techniques.- 3. Reconstruction of 3D Line Segments.- 3.1 Why 3D Line Segments.- 3.2 Stereo Calibration.- 3.2.1 Camera Calibration.- 3.2.2 Epipolar Constraint.- 3.3 Algorithm of the Trinocular Stereovision.- 3.4 Reconstruction of 3D Segments.- 3.5 Summary.- 4. Representations of Geometric Objects.- 4.1 Rigid Motion.- 4.1.1 Definition.- 4.1.2 Representations.- 4.2 3D Line Segments.- 4.2.1 Previous Representations and Deficiencies.- 4.2.2 A New Representation.- 4.3 Summary.- 4.4 Appendix: Visualizing Uncertainty.- 5. A Comparative Study of 3D Motion Estimation.- 5.1 Problem Statement.- 5.1.1 Line Segment Representations.- 5.1.2 3D Line Segment Transformation.- 5.2 Extended Kalman Filter Approaches.- 5.2.1 Linearization of the Equations.- 5.2.2 Derivation of Rotation Matrix.- 5.3 Minimization Techniques.- 5.4 Analytical Solution.- 5.4.1 Determining the Rotation.- 5.4.2 Determining the Translation.- 5.5 Kim and Aggarwal’s method.- 5.5.1 Determining the Rotation.- 5.5.2 Determining the Translation.- 5.6 Experimental Results.- 5.6.1 Results with Synthetic Data.- 5.6.2 Results with Real Data.- 5.7 Summary.- 5.8 Appendix: Motion putation Using the New Line Segment Representation.- 6. Matching and Rigidity Constraints.- 6.1 Matching as a Search.- 6.2 Rigidity Constraint.- 6.3 Completeness of the Rigidity Constraints.- 6.4 Error Measurements inn the Constraints.- 6.4.1 Norm Constraint.- 6.4.2 Dot-Product Constraint.- 6.4.3 Triple-Product Constraint.- 6.5 Other Formalisms Rigidity Constraints.- 6.6 Summary.- 7. Hypothesize-and-Verify Method for Two 3D View Motion Analysis.- 7.1 General Presentation.- 7.1.1 Search in the Transformation Space.- 7.1.2 Hypothesize-and-Verify Method.- 7.2 Generating Hypotheses.- 7.2.1 Definition and Primary Algorithm.- 7.2.2 Control Strates in Hypothesis Generation.- 7.2.3 Additional Constraints.- 7.2.4 Algorithm of Hypothesis Generation.- 7.3 Verifying Hypothesis.- 7.3.1 Estimating the Initial Rigid Motion.- 7.3.2 Propagating Hyphoteses.- 7.3.3 Choosing the Best Hypothesis.- 7.3.4 Algorithm of Hypothesis Verification.- 7.4 Matching Noisy Segments.- 7.4.1 Version 1.- 7.4.2 Version 2.- 7.4.3 Version 3.- 7.5 Experimental Results.- 7.5.1 Indoor Scenes with a Large Common Part.- 7.5.2 Indoor Scenes with a Small Common Part.- 7.5.3 Rock Scenes.- 7.6 Summary.- 7.7 Appendix: Transforming a 3D Line Segment.- 8. Further Considerations on Reducing Complexity.- 8.1 Sorting Data Features.- 8.2 “Good-Enough” Method.- 8.3 Speeding Up the Hypothesis Generation Process Through Grouping.- 8.4 Finding Clusters Based on Proximity.- 8.5 Finding Planes.- 8.6 Experimental Results.- 8.6.1 Grouping Results.- 8.6.2 Motion Results.- 8.7 Conclusion.- 9. Multiple Object Motions.- 9.1 Multiple Object Motions.- 9.2 Influence of Egomotion on Observed Object Motion.- 9.3 Experimental Results.- 9.3.1 Real Scene with Synthetic Moving Objects.- 9.3.2 Real Scene with a Real Moving Object.- 9.4 Summary.- 10. Object Recognition and Localization.- 10.1 Model-Based Object Recognition.- 10.2 Adapting the Motion-Determination Algorithm.- 10.3 Experimental Result.- 10.4 Summary.- 11. Calibrating a Mobile Robot and Visual Navigation.- 11.1 The INRIA Mobile Robot.- 11.2 Calibration Problem.- 11.3 Navigation Problem.- 11.4 Experimental Results.- 11.5 Integrating Motion Information from Odometry.- 11.6 Summary.- 12. Fusing Multiple 3D Frames.- 12.1 System Description.- 12.2 Fusing Segments from Multiple Views.- 12.2.1 Fusing General Primitives.- 12.2.2 Fusing Line Segments.- 12.2.3 Example.- 12.2.4 Summary of the Fusion Algorithm.- 12.3 Experimental Results.- 12.3.1 Example 1: Integration of Two Views.- 12.3.2 Example 2: Integration of a Long Sequence.- 12.4 Summary.- 13. Solving the Motion Tracking Problem: A Framework.- 13.1 Previous Work.- 13.2 Position of the Problem and Primary Ideas.- 13.3 Solving the Motion Tracking Problem: A Framework.- 13.3.1 Outline of the Framework.- 13.3.2 A Pedagogical Example.- 13.4 Splitting or Merging.- 13.5 Handling Abrupt Changes of Motion.- 13.6 Discussion.- 13.7 Summary.- 14. Modeling and Estimating Motion Kinematics.- 14.1 The Classical Kinematic Model.- 14.2 Closed-Form Solutions for Some Special Motions.- 14.2.1 Motion with Constant Angular and Translational Velocities.- 14.2.2 Motion with Constant Angular Velocity and Constant Translational Acceleration.- 14.2.3 Motion with Constant Angular Velocity and General Translational Velocity.- 14.2.4 Discussions.- 14.3 Relation with Two-View Motion Analysis.- 14.4 Formulation for the EKF Approach.- 14.4.1 State Transition Equation.- 14.4.2 Measurement Equations.- 14.5 Linearized Kinematic Model.- 14.5.1 Linear Approximation.- 14.5.2 State Transition Equation.- 14.5.3 Measurement Equations.- 14.5.4 Discussions.- 14.6 Summary.- 15. Implementation Details and Experimental Results.- 15.1 Matching Segments.- 15.1.1 Prediction of a Token.- 15.1.2 Matching Criterion.- 15.1.3 Reducing the Complexity by Bucketing Techniques.- 15.2 Support of Existence.- 15.3 Algorithm of the Token Tracking Process.- 15.4 Grouping Tokens into Objects.- 15.5 Experimental Results.- 15.5.1 Synthetic Data.- 15.5.2 Real Data with Controlled Motion.- 15.5.3 Real Data with Uncontrolled Motion.- 15.6 Summary.- 16. Conclusions and Perspectives.- 16.1 Summary.- 16.2 Perspectives.- Appendix: Vector Manipulation and Differentiation.- A.1 Manipulation of Vectors.- A.2 Differentiation of Vectors.- References.