Department of Computer Science and Engineering
University of Washington

A Domain-Model Approach to Reconstruction of 3D Environments for Virtual Reality

This reseach is funded by the National Science Foundation under grant nr. IRI-9520434, an exploratory research grant.

Project Summary

Reconstruction of 3D environments from sensed data is a computer vision problem with important application to the area of virtual reality. Low-level techniques for acquiring, registering, and fitting 3D data have been thoroughly explored in the last few years. Prior work has, for the most part, been limited to single objects and has merely produced a surface description of the object as a whole. This research addresses the task of reconstructing entire 3D environments, which requires scene segmentation and image understanding techniques. In this work, we explore a domain-model approach to this problem. This is a knowledge-driven approach that attempts to understand the physical structure of the environment and the individual objects in the environment through models that define the physical properties and constraints of a particular domain. In this research, we explore the problem and develop the scientific questions that must be answered and the approach we will take to answering them.

Project Description

Introduction
Low-level techniques for acquiring, registering, and fitting 3D data have been thoroughly explored in the last few years. The typical 3D reconstruction system uses range data, generally from a laser scanner or light striping system, to acquire data from a single object and then produces a 3D computer model of the object. Because the data are limited to a single object and the model is a surface model of the object as a whole, problems of scene segmentation and image understanding have been avoided. The relatively new research area of virtual reality requires 3D models of entire environments, not only single objects. This is a much harder problem that we believe is ripe for attacking.

Background
A domain model is a collection of structural information describing the properties of and constraints of a domain. The concept of a domain model is common in artificial intelligence. Domain models have been used, for example, in natural language understanding systems where knowledge of the subject matter can improve the performance of the parser/analyzer. In computer vision, McKeown's SPAM system is an excellent example of the use of a domain model (of the airport domain). Domain knowledge improved the performance of both segmentation and interpretation in SPAM.

The 3D Environment Reconstruction Problem
Reverse engineering of a 3D object is the process of constructing a computer model of the object from sensed data. The general procedure consists of scanning an object, usually with a range sensor, merging multiple views into a single registered data set, and representing the data set in a compact computer representation, such as a mesh or a set of surfaces. The final result should be an accurate model of the object that can be used in manufacturing or design modification.

Reconstruction of 3D environments is the process of constructing a computer model of a full 3D environment including multiple objects. It is related to reverse engineering, but there are several major differences:

A 3D environment has multiple objects, some fixed and some movable. Thus the problem of image segmentation must be solved in environment reconstruction. Reverse engineering systems have worked with single objects.
Color and texture are important in a 3D environment model. They have not been important and have generally been omitted in most reverse engineering work.
Measurement accuracy is important in reverse engineering. In 3D environment reconstruction, measurement accuracy may be less important, but domain constraints of the environment must be satisfied. Rather than making reconstruction more difficult, domain constraints can be used to improve the reconstruction. This will be discussed in more detail.

Up until now, 3D reconstruction has been a data-driven, bottom-up process consisting of range data acquisition, registration, segmentation (in some work), and mesh or surface fitting. There has been no attempt to understand the physical structure of the acquired objects.

The new approach that we advocate is to use domain knowledge to simplify and improve the model-acquisition process. This approach is knowledge-driven and attempts to understand the physical structure of the environment and of the individual objects in the environment. We proposed to develop physical domain models that would define the physical constraints of a particular domain. Such models would include such information as possible 3D surface classes, possible materials, surface relationships, common 3D primitive solids, functional relationships among the 3D primitives, and fixed or constrained lighting and sensor information. For example, in the domain of meeting rooms, most of the surfaces will be planar and of a homogeneous color or texture. The most common 3D primitive solids will be flat rectangular or circular pieces and long, thin pieces. If a solid-colored, mostly planar surface has a sudden irregular bump in it, the bump is likely to be a reconstruction error. Horizontal solids that are not sitting on the floor must be supported by an acceptable support structure, such as a set of four vertical solids that do touch the floor. If a horizontal, rectangular solid is supported by long, thin vertical solids at three of its four corners, there should probably be another similar support at the fourth corner. If a vertical, rectangular object on the wall has long, thin pieces framing most of its perimeter, it should probably have the frame around all of its perimeter. If the missing part of the frame is explanable by its material, shape, and orientation plus the known position of a light source, then it is even more likely that the frame should be completed. The physical domain model is a new concept; its exact definition and use will be an important part of the research.