Frame-based geometric reasoning for construction and maintenance of three-dimensional world models

Abstract

Applications such as aerial image interpretation and robot navigation require the construction and maintenance of three-dimensional (3D) geometric models of the scenes being interpreted. Domain knowledge about the scene allows interpretation of image data that is often incomplete and errorful. Geometric relationships between object parts are a rich source of knowledge and constraint for such analysis. Geometric reasoning combines the knowledge and the image data to construct and maintain 3D geometric models of the world. A practical framework for geometric representation and reasoning must incorporate projections between a 2D image and a 3D scene, geometric object definitions, and geometric relationships between objects. This framework should allow the domain knowledge to be easily modified and extended. Reasoning should be controlled to take advantage of the current available knowledge. Frame-based programming has been used to implement such a framework for geometric representation and reasoning--the 3D Frame-based Object Recognition and Modeling (3D FORM) System. The 3D FORM system represents objects and the relationships between them in a structured network of frames. Active procedures attached to these frames dynamically compute object attributes as needed, combining constraints and ensuring consistency. These procedures allow the system to perform both top-down and bottom-up reasoning, depending on the currently available knowledge. 3D FORM provides four geometric reasoning capabilities: grouping, computation, specialization, and matching. Grouping collects simple data objects into more complex objects. Computation applies constraints from the model to the given data to hypothesize missing parts of an object or system. Specialization chooses an appropriate interpretation of an object from the possible objects in the domain, and assigns the object's parts to appropriate slots of the new interpretation. Finally, matching combines a pair of objects to derive a single, more complete object. Matching can be used to verify a hypothesis with new data, to reconcile two hypotheses, or to combine data from different points of view. The 3D FORM system has been demonstrated on three realistic image understanding problems: understanding shadows, deriving a composite interpretation from three views of a scene, and hypothesizing missing and occluded edges in wire frame data derived from stereo edges.