Dense 3-D Reconstruction of an Outdoor Scene
by Hundreds-baseline Stereo Using a Hand-held Video Camera
Tomokazu Sato, Masayuki Kanbara, Naokazu Yokoya and Haruo TakemuraGraduate School of Information Science, Nara Institute of Science and Technology

8916-5 Takayama, Ikoma, Nara 630-0101, Japantomoka-s, masay-ka, yokoya@is.aist-nara.ac.jp
Cybermedia Center, Osaka University

Abstract

However, when the underlying scene is not suitable for theaffine camera model, estimated camera parameters are notreliable. Therefore, this method is not suitable for reconstructing a dense 3-D model by stereo method. Although
there exists another reconstruction method [3] that estimatescamera parameters and a dense 3-D model from an image
sequence, the method uses only a small number of images.
Additionally, it seems to be difficult to reconstruct a complex outdoor scene because it uses the constraint of surface
continuity in dense depth estimation.
In order to reconstruct an outdoor scene densely and stably, we propose a new 3-D reconstruction method that firstestimates extrinsic camera parameters of an input image sequence, and then reconstructs a dense model of a scene.
In the first process, we use a camera parameter estimation
method [4] that is based on tracking both markers and natural features. Next, dense depth maps are computed by using
a multi-baseline stereo method from hundreds images. Finally, depth maps are combined together in a voxel space.
The proposed method can reconstruct a complex outdoor
scene densely and accurately by combining several hundreds images of a long sequence without the constraint ofsurface continuity.
This paper is structured as follows. Section 2 describes
a method of estimating camera parameters of a hand-heldvideo camera by tracking markers and natural features. In
Section 3, we describe a method of dense depth estimationand integration of these dense data in a voxel space. Then,
we demonstrate experimental results of 3-D reconstruction
from real image sequences to show the feasibility of the
proposed method in Section 4. Finally, Section 5 describes
conclusion and future work.

Three-dimensional (3-D) models of outdoor scenes arewidely used for object recognition, navigation, mixed reality, and so on. Because such models are often made manually with high costs, automatic and dense 3-D reconstruction is widely investigated. In related work, a dense 3-Dmodel is generated by using a stereo method. However,these methods cannot use several hundreds images together
for dense depth estimation because it is difficult to accurately calibrate a large number of cameras. In this paper, we propose a dense 3-D reconstruction method thatfirst estimates extrinsic camera parameters of a hand-heldvideo camera, and then reconstructs a dense 3-D model ofa scene. We can acquire a model of the scene accurately byusing several hundreds input images.

1. Introduction
Three-dimensional (3-D) models of outdoor scenes arewidely used for object recognition, navigation, mixed reality, and so on. Because such models are often made manually with high costs, automatic and dense 3-D reconstruction is desired. In the field of computer vision, there aremany researches that reconstruct 3-D models from multiple
images [1].
One of the major approaches to 3-D reconstruction is touse static stereo. However, the methods cannot use a large
number of images because it is difficult to calibrate a large
number of cameras accurately. Therefore, these methods
become sensitive to noise. Although many researchers often
use a constraint of surface continuity to reduce noises, suchan approach limits a target scene and may sometimes reduce
accuracy of reconstruction.
One of other approaches is to use an image sequence.
The methods that use an image sequence can automaticallyestimate camera parameters and 3-D positions of naturalfeatures by tracking features in captured images. Factorization algorithm [2] is one of the well known methods thatcan estimate a rough 3-D scene stably and efficiently froman image sequence by assuming an affine camera model.

2. Camera parameter estimation bytracking features
This section describes an extrinsic camera parameter estimation method which is based on tracking features (markers and natural features). Figure 1 shows the flow diagramof our algorithm. First, we must specify the positions of six1

where  is a weighting coefficient for the feature  at the -th frame and is computed by considering the confidence

marker specification at the first frame(A) initial camera parameter estimationof the feature.

(c) 3-D Position estimation of natural features The position   of the natural feature  in real world is estimatedfrom  and  that have already been determined. Theposition   is computed by minimizing a sum of squared
distances between  and straight lines that connect the center of projection in the  -th frame and the position   .

(a) marker and natural feature tracking(b) extrinsic camera parameter estimation(c) 3-D position estimation of natural features(c) 3-D Position estimation of natural features The position   of the natural feature  in real world is estimatedfrom  and  that have already been determined. Theposition   is computed by minimizing a sum of squared
distances between  and straight lines that connect the center of projection in the  -th frame and the position   offeature .

(d) computing confidence of features(e) adding and deleting natural features(B) error minimization in the whole input

Figure 1: Flow diagram of camera parameter estimation.

(d) Computing confidence of features We assume thatthe distribution of tracking error can be approximated bya Gaussian probability density function. Then the confidence of feature,  , is defined by the inverse of varianceof re-projection error   in the frames where feature  hasalready been tracked.

or more markers in the first frame of input sequence to estimate extrinsic camera parameters in the first frame. Theninitial extrinsic camera parameters in all the frames are determined by iterating the processes at each frame (A). However, the accumulation of estimation error exists. Therefore, extrinsic camera parameters are refined by minimizing the accumulation of estimation errors over the whole
input (B). Using this approach, we can estimate extrinsic
camera parameters efficiently and accurately with automatically adding and deleting features regardless of the visibilityof initial markers. It should be noted that intrinsic camera
parameters must be estimated in advance.

2.1(e) Adding and deleting natural features Feature candidates that satisfy all the following conditions are added tothe set of natural features at every frame.
 The confidence is over a given threshold.
 The matching error is less than a given threshold.
 The output value of Harris’s operator is more than agiven threshold.
 The maximum angle between lines that connect thecenter of projection and estimated 3-D position of thefeature candidate is more than a given threshold.
On the other hand, natural features that satisfy at least oneof the following conditions are deleted at every frame.
 The confidence is under a given threshold.
 The matching error is more than a given threshold.

Initial camera parameter estimationBy iterating the following processes from the first frame tothe last frame, initial extrinsic camera parameters and 3-Dpositions of natural features are determined.
(a) Marker and natural feature tracking Markers aretracked by using color and shape information. Natural features are tracked using a robust estimation approach by projecting the 3-D positions of natural features that are estimated until the previous frame. Harris’s interest operator isused for robust tracking of natural features.

2.2

In the final step, the accumulation of estimation error isminimized over the whole input. The accumulated estimation error is given by the sum of re-projection errors as inEq.(2) and is minimized with respect to the camera parameter  and natural feature position   .

(b) Extrinsic camera parameter estimation In this   is usedmethod, the re-projection error      
as a measure for estimation error, where  is the tracked
 is the re-projected posi2-D position of feature  and tion of estimated 3-D position   of feature  onto the image at the  -th frame using camera parameter  . Thencamera parameter  at the  -th frame is estimated byminimizing the estimation error   defined as follows:   

Optimization in the whole input      







(2)

The camera parameters and feature positions that have already been estimated by earlier process for each frame areused for initial values in the minimization.   is a weighting coefficient for the feature  in the final frame of the image sequence.

(1)

2

Note that images from the  -th frame to the -thframe are not used for computing SSSD, because baselines
in these frames are not long enough to estimate depth stably. Multiple centered windows approach [6] is also used toreduce estimation error around occlusion boundaries. ThenSSSD is extended to SSSDM as follows:

3. Dense 3-D reconstruction of scene
In this section, we describe a dense 3-D reconstruction
method using camera parameters estimated by the method
described in Section 2. First, a dense depth map for each
image is computed by using a multi-baseline stereo method,then a dense 3-D model is reconstructed by combining obtained dense depth maps in a voxel space.

          

3.1. Depth mapping by multi-baseline stereo

We can estimate the depth value  correctly by minimizing SSSDM unless pixel    is occluded in more thanframes. Additionally, we avoid a local minimum problem
and achieve stable depth estimation using a multiscale approach [7]. Note that we use the linear interpolation to compute  in the regions without informative textures because
the confidence of estimated  is low in such regions.

A depth map is computed for each frame by using a multibaseline stereo technique [5]. Depth value  of pixel   at the  -th frame is estimated by using the images from the  -th frame to the   -th frame. In the following expression, we assume the focal length as 1 for simplicity. Then, the 3-D position of the pixel    can be
expressed by    , and we can define the projected
position      of the 3-D position     onto the th frame as follows:           3.2. 3-D reconstruction in voxel space
In this paper, a 3-D model is reconstructed in a voxel spaceby combining several hundreds dense depth maps. In thevoxel space, each voxel has two values A and B which are
voted by estimated depth data and camera parameters. Both
A and B are voted when the voxel is projected onto a pixel   in a frame. Value A is voted if depth of the voxel incamera coordinate system equals  of   . On the otherhands, value B is voted when depth of the voxel is equal toor less than  of   . The 3-D model is reconstructed by
selecting the voxel whose  is more than a given threshold. Note that the color of the voxel is decided by mean
color of pixels that has voted to the value A of the voxel.







1

(3)

1

where is a parameter. In the multi-baseline method, SSD(Sum of Squared Differences) is employed as an error function, that is computed as the sum of squared differences between the window  in the  -th frame centered at   and that in the -th frame centered at     . We define the SSD function in Eq.(4) using RGB components(     ).

                 

4. Experiment  Ü  ÝIn experiment, we captured an outdoor scene as shown in
Figure 2(a) by a hand-held CCD camera (Sony DSR-DP150) with a wide conversion lens (Sony VCL-HG0758).
This image sequence lasts 40 seconds and has 599 frames(720480 pixels, progressive scan). The intrinsic camera
parameters are estimated by using the Tsai’s method [8] inadvance, and the extrinsic camera parameters are estimatedby the method described in Section 2. The curved lines in
Figure 3 indicate the camera path and the quadrilateral pyramids indicate the camera postures drawn at every 50 frames.
Dense depth map of the  -th frame is estimated by using odd frames from the   -th to the   -thframes excluding the   -th to the   -th frames.
Figure 2(b) shows dense depth maps in which depth values
are coded in intensity. It is confirmed that correct depth values are obtained for most part of the images as shown inthis figure. However there exist some incorrect depth values between a column and a wall of the building because
there are no textures around the wall of the building. Linear
interpolation is used for determining depth values in theseareas.

                              (4)where  and  are offsets of the window  for andaxes, respectively. We define a modified SSSD (Sum ofSSD) in Eq.(5) using the median of SSD because the template of window  in the  -th frame may be occluded inother frames.

                 

      and    



(7)

(5)

otherwise

where,                                             (6)

3

Figure 3 shows a 3-D model obtained by combining 399
dense depth maps together in the way of voxel voting that is
described in Section 3.2. In this experiment, the voxel spaceconsists of cm cube voxels. A wall behind a column ofthe building is reconstructed even if the wall is occluded
from time to time. We also confirm that some positions
are holed because these pixels are not visible enough forsufficient precision.

100th frame

5. Conclusion
In this paper, a dense 3-D reconstruction method from amonocular image sequence captured by a hand-held video
camera is proposed. In this method, first, extrinsic camera parameters are estimated by tracking markers and natural features. Then, at each frame, a dense depth map iscomputed by using already estimated camera parameters.
Finally, a dense 3-D model is reconstructed by combining
hundreds of dense depth maps in a voxel space.
In the experiments, the dense 3-D scene reconstruction isaccomplished for a long image sequence captured in a complex outdoor scene successfully with stable dense depth estimation. However, some parts of reconstructed model haveholes. In future work, more accurate model reconstruction
will be explored using the confidence of depth value. Integration of dense 3-D models from multiple image sequences
will also be investigated for obtaining a complete model.

180th frame

260th frame

References[1] N. Yokoya, T. Shakunaga and M. Kanbara: “Passive Range
Sensing Techniques: Depth from Images,” IEICE Trans. Inf.
and Syst., Vol. E82-D, No. 3, pp. 523–533, 1999.
[2] C. Tomasi and T. Kanade: “Shape and Motion from Image
Streams under Orthography: A Factorization Method,” Int.
Journal of Computer Vision, Vol. 9, No. 2, pp. 137–154, 1992.
[3] M. Pollefeys, R. Koch, M. Vergauwen, A. A. Deknuydt andL. J. V. Gool: “Three-dimentional Scene Reconstruction fromImages,” Proc. SPIE, Vol. 3958, pp. 215–226, 2000.
[4] T. Sato, M. Kanbara, H. Takemura and N. Yokoya: “3-D Reconstruction from a Monocular Image Sequence by Tracking
Markers and Natural Features,” Proc. 14th Int. Conf. on VisionInterface, pp. 157–164, 2001.
[5] M. Okutomi and T. Kanade: “A Multiple-baseline Stereo,”
IEEE Trans. Pattern Analysis and Machine Intelligence, Vol.
15, No. 4, pp. 353–363, 1993.
[6] R. Kumar, H. S. Sawhney, Y. Guo, S. Hsu and S. Samarasekera: “3D Manipulation of Motion Imagery,” Proc. Int. Conf.
on Image Processing, pp. 17–20, 2000.
[7] N. Yokoya: “Surface Reconstruction Directly from Binocular Stereo Images by Multiscale-multistage Regularization,”
Proc. 11th Int. Conf. on Pattern Recognition, Vol. I, pp. 642–646, 1992.
[8] R. Y. Tsai: “An Efficient and Accurate Camera Calibration
Technique for 3D Machine Vision,” Proc. IEEE Conf. onComputer Vision and Pattern Recognition, pp. 364–374, 1986.

340th frame

420th frame(a) Input images

499th frame(b) Dense depth map

Figure 2: Input images and estimated dense depth maps.

4Figure 3: Results of outdoor scene recovery as well as estimated camera positions and postures.

5