Forming a three-dimensional environment model for autonomous navigation using a sequence of images.

Abstract

For an autonomous agent to navigate from one point to another in an unknown domain, it must form a model of its environment. Although many different sensors may be used, it is assumed that vision is the primary sensor. A novel algorithm is presented which produces a dense voxel based model of the environment directly from a sequence of images. The agent, equipped with a camera and an inertial navigation system, is permitted to make any translation and rotation while acquiring a sequence of images of a given scene. These images are backprojected into a three-dimensional space of voxels and intensities on the image plane are assigned as observations to the voxels. At each voxel, the variance of these observations is computed. If a voxel is full, it will be observed to have the same intensity in all the images. If a voxel is empty it will be transparent and background object(s) can be seen through it. Full voxels will have consistent observations, while empty voxels may have inconsistent observations (based on the background objects). The computed variance is used as a measure of the consistency of the observations and is used to separate full and empty voxels. Bayesian hypothesis testing is applied to find an optimal threshold for labeling voxels as full or empty. A region growing algorithm is applied to the voxel space to form three dimensional regions. A priori knowledge about the environment and information from other sensors may be applied directly to label these regions as full or empty. The reconstruction is a dense, volumetric description of the environment, excellent for navigation. An attractive feature is that there is no need to solve the correspondence problem. Furthermore, the algorithm undergoes graceful degradation when there is insufficient contrast or inadequate information. Experimental results using synthetic, indoor and outdoor image sequences are shown. The algorithm correctly labels voxels as full or empty using the images and a priori knowledge. Labeling errors which could result in a collision occur only in the vicinity of voxels labeled as full. By maintaining a safe distance from the full voxels, the agent will avoid all hazards.