3-D Modeling of an Outdoor Scene by Multi-baseline Stereo
Using a Long Sequence of Images
Tomokazu Sato†, Masayuki Kanbara†, Naokazu Yokoya† and Haruo Takemura‡†Graduate School of Information Science, Nara Institute of Science and Technology
8916-5 Takayama, Ikoma, Nara 630-0101, Japan{tomoka-s, kanbara, yokoya}@is.aist-nara.ac.jp‡Cybermedia Center, Osaka University
Abstract
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 3-D modeling has been investigated. A 3-D model is usually generated by using astereo method. However, such approaches cannot use several hundreds images together for dense depth estimation
because it is diﬃcult to accurately calibrate a large number of cameras. In this paper, we propose a 3-D modelingmethod that first estimates extrinsic camera parameters ofa monocular image sequence captured by a moving video
camera, and then reconstructs a 3-D model of a scene. We
can acquire a 3-D model of an outdoor 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 3-D modeling is desired.
One of approaches to the problem is to use an image sequence that is called shape-from-motion [1, 4, 5, 7]. The
method can automatically recover camera parameters and
3-D positions of feature points by tracking natural featuresin captured images. Factorization algorithm [7] is one ofthe well known shape from motion methods that can estimate a rough 3-D scene stably and eﬃciently by assuming
an aﬃne camera model. However, when the 3-D scene is
not suitable for the aﬃne camera model, estimated camera
parameters are not reliable. Although there exist other reconstruction methods [1, 4, 5], most of the methods reconstruct only a limited scene from a small number of images
and are not designed to obtain a dense model. A method [4]which recovers camera parameters and a dense scene canreconstruct only a simple outdoor scene without occlusionfrom a small number of images.

In order to reconstruct a complex outdoor scene densely
and stably, we propose a new 3-D reconstruction methodthat first recovers extrinsic camera parameters of an input
image sequence that consists of several hundreds images,
and then generates a 3-D model of a scene by combining several hundreds depth maps together in a voxel space.
In the first process, we use a camera parameter estimation
method [6]. This method uses a small number of predefinedmarkers of known 3-D positions and many natural features
for stable and eﬃcient estimation of extrinsic camera parameters. Dense depth maps are then computed by using
an extended multi-baseline stereo method. The proposed
method can reconstruct a complex outdoor scene densely
and accurately by using several hundreds images of a longsequence.

2. Camera parameter estimation by trackingfeatures
This section describes an extrinsic camera parameter estimation method which is based on tracking features (markers and natural features). Figure 1 illustrates the flow diagram of our algorithm. First, we must specify the positionsof six or more markers in the first frame of input sequence,and extrinsic camera parameters in the first frame are estimated. Then extrinsic camera parameters in all the frames
are sequentially determined by iterating the processes at
each frame (A). Finally, 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 eﬃciently and accurately
regardless of the visibility of initial markers.

2.1

Initial camera parameter estimation

By iterating the following processes from the first frameto the last frame, initial extrinsic camera parameters and 3D positions of natural features are determined.
(a) Marker and natural feature tracking. Markers aretimated 3-D position of the feature candidate and centers of projection is more than a given threshold.

marker specification at the first frame(A) initial camera parameter estimation(a) marker and natural feature tracking(b) extrinsic camera parameter estimation

On the other hand, natural features that satisfy at least oneof the following conditions are deleted at every frame.
• The confidence W f p is under a given threshold.
• The matching error is more than a given threshold.

(c) 3-D position estimation of natural features

2.2

Error minimization in the whole input(d) computing confidence of features(e) updating natural features(B) error minimization in the whole input

Figure 1. Flow diagram of camera parameter
estimation.
tracked based on 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 [6]. Harris’s interest operator is employed for robust tracking of natural features.
(b) Extrinsic camera parameter estimation. The reprojection error R f p = |x f p − x̂ f p |2 is used as a measureof estimation error, where x f p is the tracked 2-D position offeature p and x̂ f p is the re-projected position of estimated 3D position S p of feature p onto the image at the f -th frameby camera parameter M f . Then camera parameter Mf at thef -th frame is estimated by minimizing the estimation error
E f = p W f p R f p , where W f p is a weighting coeﬃcient representing the confidence of the feature p at the f -th frame.
(c) 3-D Position estimation of natural features. The position S p of the natural feature p in real world is estimatedfrom multiple x f p and M f that have already been determined until the current frame. The position S p is computedby minimizing the sum of squared distances between S p andstraight lines in 3-D that connect the centers of projection
and the positions x f p of feature p in previous frames f .
(d) Computing confidence of features. We assume thatthe distribution of tracking errors can be approximated by aGaussian probability density function. Then the confidenceof feature, W f p , is computed by the inverse of variance of
re-projection error R f p .
(e) Updating natural features. Feature candidates that satisfy all the following conditions are added to the set of natural features at every frame.
• The confidence W f p 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 the es-

In the final step, the accumulation of estimation errors defined as E = f p W p |x f p − x̂ f p |2 is minimized over thewhole input with respect to the camera parameter M f andnatural feature positions S p . The camera parameter and feature positions that have already been estimated by earlier
process for each frame are used as initial values. Wp is aweighting coeﬃcient for the feature p in the final frame ofthe image sequence.

3. Dense 3-D reconstruction by hundredsbaseline stereo
In this section, we describe a dense 3-D reconstruction
method using estimated camera parameters. First, a dense
depth map for each image is computed by using a multibaseline stereo method, then a 3-D model is reconstructedby combining obtained dense depth maps in a voxel space.

3.1. Dense depth estimation by multi-baseline stereo
A depth map is computed for each frame by using a
multi-baseline stereo technique [3]. Depth value z of pixel(x, y) in the f -th frame is computed by using the k-th tothe l-th frames (k ≤ f ≤ l) around the f -th frame. In thefollowing expression, we assume the focal length as 1 forsimplicity. Then, the 3-D position of the pixel (x, y) canbe expressed by (xz, yz, z), and we can define the projected
position ( x̂ j , ŷ j ) of the 3-D position (xz, yz, z) onto the j-thframe (k ≤ j ≤ l) as follows:
T(a x̂ j , aŷ j , a, 1)T = M j M−1f (xz, yz, z, 1) ,(1)where a is a parameter. In the multi-baseline method, SSD(Sum of Squared Diﬀerences) is employed as an error function, that is computed as the sum of squared diﬀerences between the window W in the f -th frame centered at (x, y)and that in the j-th frame centered at ( x̂ j , ŷ j ). We define
the SSD function for the j-th frame in Eq. (2) using RGB
components (IR , IG , IB ).
S S D f j (x, y, ox , oy ) =
(IR f (x + u, y + v) − IR j ( x̂ j + u, ŷ j + v))2(u−o x ,v−oy )⊆W+ (IG f (x + u, y + v) − IG j ( x̂ j + u, ŷ j + v))2+ (IB f (x + u, y + v) − IB j ( x̂ j + u, ŷ j + v))2 ,(2)where ox and oy are oﬀsets of the window W for x and yaxes, respectively.
In the multi-baseline stereo method, the depth z of (x, y)
is determined so as to minimize the SSSD (Sum of SSD)
from the k-th frame to the l-th frame. We define a modified
SSSD in Eq. (3) using the median of SSD because the template of window W in the f -th frame may be occluded inother frames.
S S S D f (x, y, ox , oy ) =S S D f j (x, y, ox , oy );
l 


S S D f j (x, y, ox , oy ) ≤ T and | j − f | > D ,

j=k 
0;
otherwise.

(3)

where,T = median(S S D f k (x, y, ox , oy ), · · · ,S S D f ( f −D−1) (x, y, ox , oy ), S S D f ( f +D+1) (x, y, ox , oy ),· · · , S S D f l (x, y, ox , oy )). (4)Note that images from the ( f − D)-th frame to the ( f + D)-thframe are not used for computing SSSD, because baselines
in these frames are not long enough to estimate depth stably.
Multiple centered window approach [2] is also used to reduce estimation errors around occlusion boundaries. SSSD
is now extended to SSSDM as follows:
S S S DM f (x, y) = min (S S S D f (x, y, u, v)).
(u,v)⊆W(5)We can estimate the depth value z(x, y) correctly by minimizing SSSDM unless the pixel (x, y) is occluded in morethan (l − k − 2D)/2 frames. Additionally, we avoid a local minimum problem and achieve stable depth estimation
using a multiscale approach [9].

3.2. 3-D model reconstruction in a voxel space
In this paper, a 3-D model is reconstructed in a voxel
space by combining several hundreds dense depth maps. Inthe voxel space, each voxel has two values A and B which
are voted by already estimated depth values and camera parameters. For each pixel (x, y) in an image, both A and B are
voted when the voxel is projected onto the pixel as follows.
Value A is voted if depth of the voxel in camera coordinate
system is equal to z of (x, y). On the other hand, value B isvoted when depth of the voxel is equal to or less than z of(x, y). We use the ratio A/B as a normalized voting value.
A 3-D model is then reconstructed by selecting the voxel
whose A/B is more than a given threshold. Note that thecolor of the voxel is decided by computing a mean color ofpixels that have been voted to the value A of the voxel.

4. Experiments
We have conducted two experiments: One is a modelreconstruction of a single building and the other is a reconstruction of a street scenery. Both scenes are complex

and have many occlusions. In both experiments, we use ahand-held CCD camera (Sony VCL-HG0758) with a wide
conversion lens (Sony VCL-HG0758). The intrinsic camera
parameters are estimated by Tsai’s method [8] in advance.

4.1. Reconstruction of building
In the first experiment, we captured a single building(Suzaku-mon) shown in Figure 2(a) by walking around thebuilding viewing it at the center of image. This image sequence lasts 40 seconds and has 599 frames (720×480 pixels, progressive scan).
In this experiment, a dense depth map of the f -th frame
is obtained by using every two frames from the ( f − 100)-thto the ( f + 100)-th frames excluding the ( f − 15)-th to the( f +15)-th frames. Figure 2(b) shows computed dense depth
maps in which depth values are coded in intensity. It is confirmed that correct depth values are obtained for most partof the images. Figure 3 shows a reconstructed 3-D modelwith textures 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 space is constructedof 10cm cube voxels. It can be observed that a wall behinda column of the building is reconstructed even if the wallis occluded from time to time. We also observe that somepositions are holed because they are not visible enough forsuﬃcient precision in the image sequence.

4.2. Reconstruction of street scenery
In the second experiment, a street is captured as shown inFigure 4(a) by the CCD camera put on a slowly moving car.
This image sequence lasts 19 seconds and has 284 frames(720×480 pixels, progressive scan).
A dense depth map of the f -th frame is obtained by using 30 frames from the ( f + 6)-th to the ( f + 35)-th frames.
As shown in Figure 4(b), it is confirmed that correct depth
values are obtained for most part of the images even aroundthe occlusion edges. However, there exist some incorrect
depth values at the right of the trees because the areas are
occluded by the trees during over 15 frames. Figure 5 showsa reconstructed 3-D model with textures obtained from 249
dense depth maps. In this experiment, the voxel space isconstructed of 10cm cube voxels. Note that many parts ofwalls are holed around the windows of the buildings. We
confirmed that it is diﬃcult to reconstruct the reflective objects.

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 experiments, the dense 3-D scenereconstruction is successfully accomplished by using a long

first frame

100th frame

249th frame(b) Dense depth maps

499th frame(a) Input images(b) Dense depth maps
Figure 2. Input images and estimated dense
depth maps (Suzaku-mon).

Figure 4. Input images and estimated dense
depth maps (street scenery).

Figure 3. Results of outdoor scene recovery(Suzaku-mon).

Figure 5. Results of outdoor scene recovery(street scenery).

sequence of images captured in complex outdoor environments. However, we observe that some parts of reconstructed models are holed. In future work, integration of3-D models from multiple image sequences should be investigated for obtaining a complete surface model.
Acknowledgments
This work was supported in part by Internet Systems Research Laboratories, NEC Corporation.

[4] M. Pollefeys, R. Koch, M. Vergauwen, A. A. Deknuydt, andL. J. V. Gool. Three-dimentional Scene Reconstruction fromImages. In Proc. SPIE, Vol. 3958, pp. 215–226, 2000.
[5] G. Roth and A. Whitehead. Using Projective Vision to Find
Camera Positions in an Image Sequence. In Proc. 13th Int.
Conf. on Vision Interface, pp. 87–94, 2000.
[6] T. Sato, M. Kanbara, H. Takemura, and N. Yokoya. 3-D Reconstruction from a Monocular Image Sequence by Tracking
Markers and Natural Features. In Proc. 14th Int. Conf. on Vision Interface, pp. 157–164, 2001.
[7] C. Tomasi and T. Kanade. Shape and Motion from Image
Streams under Orthography: A Factorization Method. In Int.
Journal of Computer Vision, Vol. 9, No. 2, pp. 137–154, 1992.
[8] R. Y. Tsai. An Eﬃcient and Accurate Camera Calibration
Technique for 3D Machine Vision. In Proc. IEEE Conf. onComputer Vision and Pattern Recognition, pp. 364–374, 1986.
[9] N. Yokoya. Surface Reconstruction Directly from Binocular Stereo Images by Multiscale-multistage Regularization. InProc. 11th Int. Conf. on Pattern Recognition, Vol. I, pp. 642–646, 1992.

References[1] P. Beardsley, A. Zisserman, and D. Murray. Sequential Updating of Projective and Aﬃne Structure from Motion. In Int.
Jour. of Computer Vision, Vol. 23, No. 3, pp. 235–259, 1997.
[2] R. Kumar, H. S. Sawhney, Y. Guo, S. Hsu, and S. Samarasekera. 3D Manipulation of Motion Imagery. In Proc. Int. Conf.
on Image Processing, pp. 17–20, 2000.
[3] M. Okutomi and T. Kanade. A Multiple-baseline Stereo. In
IEEE Trans. Pattern Analysis and Machine Intelligence, Vol.
15, No. 4, pp. 353–363, 1993.

(a) Input images