New Multi-baseline Stereo by Counting Interest Points
Tomokazu Sato and Naokazu Yokoya
Graduate School of Information Science, Nara Institute of Science and Technology
8916-5 Takayama, Ikoma, Nara 630-0192, Japan
E-mail:{tomoka-s, yokoya}@is.naist.jp

Abstract

for a moving video camera;

This paper proposes a novel method for estimating depth
from a long image sequence captured by a moving camera. Our idea for estimating a depth map is very simple;
only counting interest points in images is integrated withthe framework of multi-baseline stereo. Even by a simple
algorithm, depth can be determined without computing similarity measures such as SSD and NCC that have been used
for traditional stereo matching. Our method realizes robust
depth estimation against image distortions and occlusions
that are caused by camera motion. Note that, in this paper, intrinsic and extrinsic parameters of video camera are
assumed to be calibrated in advance.

(1) Changing patterns in video images: Free motion ofvideo camera causes significant changes of looks forcorresponding points in video frames. Traditional similarity measure such as SSD (Sum of Squared Differences), that has been used for the multi-baseline stereo,
is weak for this effect.

1. Introduction(3) Computational cost: A large number of images consume the large amount of memory and computational
resources. Some patches for problem (1) and (2) may
also increase computational time.

Depth map estimation from stereo images is one of themost important problems in computer vision, because depth
information is used in a number of different fields such as
3-D reconstruction, object recognition, and mixed reality. A
large number of stereo depth estimation methods have still
been investigated by many researchers. In this paper, we
focus on the framework of multi-baseline stereo that cantreat a large number of images simultaneously.
The original multi-baseline stereo method was proposedby Okutomi and Kanade [1] for multiple image input. The
multi-baseline stereo has such a very good feature that arbitrary number of images can be simultaneously used for
depth estimation. This increases the accuracy of depth estimation and decreases the ambiguity in stereo matching.
After their work, several researchers utilize and also extend
the original multi-baseline stereo [2, 3, 4, 5, 6].
Recently, some researchers have employed the multibaseline stereo framework for a freely moving camera[3, 4, 5]. A freely moving video camera is suitable for 3-D
modeling of a large scale environment because that easily
makes a long distance baseline between cameras. However,there exist some problems in multi-baseline stereo method(2) Occlusions: When a point on an object where depth
should be estimated is occluded by other objects in apart of input video sequence, the occluder gives a negative score to the score function of the multi-baseline
stereo: SSSD (Sum of SSD). This negative score prevents the algorithm from obtaining correct estimationof depth map around occlusions.

To avoid these problems, we use interest points such as
corners and cross points of edges in video images as shownin Figure 1. The framework of our depth estimation is basically the same as the original multi-baseline stereo except
for a newly employed score function: TNIP (Total Numberof Interest Points). The idea is based on the assumptionthat the corners and cross points of edges in the 3-D space(3-D interest points) will appear in video images as 2-D interest points at the projected positions of the 3-D interest
points. By searching a depth that maximizes total numberof 2-D interest points under epipolar constraint, the depth
can be determined as a position of a 3-D interest point. A
flow diagram of our depth estimation is shown in Figure 2.
First, interest points are detected for all the video images(A). Next, depths are estimated by multi-baseline stereo using TNIP (B). Outliers of estimated depths are rejected byconfidences (C). Finally, dense depth maps are generated byinterpolating sparse depth data (D).
By our method, the problems pointed out earlier can besolved; (1) interest points are strong for the effect of chang-( xz, yz, z )
W

W

W

W

k-th frame

j-th frame( x, y )Figure 1. Example of interest points.

f-th framei-th frame( xˆi , yˆ i )Figure 3. 3-D position of (x, y) with depth z
and its projected line to each frame.

(A) Detection of interest points

2.1. Definition of coordinates for moving camera(B) Depth estimation for interest points(C) Elimination of outliers(D) Depth map interpolation

Figure 2. Flow diagram of dense depth map
estimation.

ing distortion, (2) the new score function TNIP is not significantly affected by occluders, (3) computational cost is
drastically decreased because depth can be determined byonly counting interest points. However there exists one restriction that we cannot estimate depths for positions of noninterest points by using TNIP, that is not a critical problem
for 3-D modeling and some other applications because usually 3-D interest points coincide with corners of the 3-Dmodel. In most cases, depth interpolation may be sufficient.
The rest of this paper is structured as follows. First, theoriginal multi-baseline stereo method for a moving video
camera is briefly described in Section 2. In Section 3, the
new score function TNIP for multi-baseline stereo is proposed. Stages (A) to (D) for estimating a dense depth map
are detailed in Section 4. Experimental results with simulation and a real scene then show the validity and feasibilityof the proposed method in Section 5. Finally, Section 6 describes conclusion and future work.

2. Multi-baseline stereo by using SSSD
In this section, firstly, coordinate systems of moving
camera are defined. The principle of multi-baseline stereo[1] using SSSD is then briefly summarized.

In multi-baseline stereo, as shown in Figure 3, a depth
z of a pixel (x, y) in the f-th frame is estimated by using
images from the j-th to k-th frame (j ≤ f ≤ k). In thefollowing, for simplicity, we assume that the focal length is
1 and lens distortion effect has already been corrected by
known intrinsic parameters. In this case, a 3-D position of(x, y) with depth z is represented as (xz, yz, z) in the camera coordinate system of the f-th frame. The 3-D position(xz, yz, z) is projected to the position (x̂ i , yˆi ) in the imageof the i-th frame by the following expression.
⎞
⎞
⎛
xz
ax̂i
⎜ yz ⎟⎜ ayˆi ⎟⎟⎟⎜⎜⎝ a ⎠ = Mf i ⎝ z ⎠ ,
1
1
⎛

(1)

where a is a parameter, Mf i denotes a 4 × 4 transformation matrix from the camera coordinate system of the f-th
frame to the camera coordinate system of the i-th frame. In
the multi-baseline stereo, as shown in Figure 3, the point(x̂i , yˆi ) is constrained on the epipolar line, which is the projection of the 3-D line connecting the position (xz, yz, z)
and the center of projection in the f-th frame onto the i-thframe.

2.2. Depth estimation using SSSD
In the traditional multi-baseline stereo, depth z of pixel(x, y) is determined by using the similarity measure: SSD.
The SSD is computed as the sum of squared differences between two image patterns that have a certain size W . The
SSD for (x, y) in the f-th frame and (xˆi , yˆi ) in the i-th

frame is defined using image intensity I as follows.
SSDf i (x, y, z) = 
(If (x + u, y + v) − Ii (xˆi + u, yˆi + v))2 . (2)(u,v)⊆W

To evaluate the error of the depth z for all the input images,
the SSD is summed up as follows:
SSSDf (x, y, z) =kSSDf i (x, y, z).

(3)

i=j

The depth z is determined for each frame so as to minimize
the SSSD function. Generally, to find a global minimumof the SSSD, depth z should be searched for all the depth
range along a 3-D line from a reference pixel (x, y).
If the pixel (x, y) in the f-th frame is occluded by otherobjects in the i-th frame, SSSDf (x, y, z) for the true depth
z is increased by the occluder because SSDf i (x, y, z) givesa large error. Thus, to obtain a correct depth at such an occluded part, some other computationally expensive extensions should be added to the original multi-baseline stereo.
For example, a modified SSSD can be computed by summing up only lower halves of SSDs [5]. However, there
still remains the computational cost problem and the image
distortion problem.

3. Multi-baseline stereo by counting interest
pointsIn this section, a new score function TNIP is definedto estimate depth z of pixel (x, y) using the multi-baseline
stereo framework. Generally, feature points in a 3-D space,such as corners of objects and cross points of texture edges,
appear as 2-D feature points in images at projected positionsof the 3-D feature points. Such a 2-D feature points can beeasily detected by interest operators such as Harris’s [7] andMoravec’s [8].
In this research, depth z is determined so as to maximize
the TNIP score function that is defined as follows.
T N IPf (x, y, z) =kHi (x̂i + u, ŷi + v).

(4)i=j (u,v)⊆W⎧⎨ 1 ; interest point exists
at (u, v) in i-th frame.
Hi (u, v) =⎩0 ; otherwise(5)

TNIP means the total number of interest points that exist in(x̂i , ŷi ) centered windows W for all the frames. Note thatthe size of W should be small such as 3 × 3 pixels becauseinterest points are not detected at positions far from projected positions of (xz, yz, z) when there exists a featurepoint in 3-D space. It should be noted that the new scorefunction TNIP is originated assuming the use of large number of images. It shows its real ability when used for a long
image sequence.
By using the TNIP instead of the SSSD function in multibaseline stereo, computational time can be drastically decreased because the time consuming process of comparing
intensity patterns can be removed from the depth estimation. Moreover, maximizing the TNIP can obtain a correct depth even if projected image patterns of 3-D objects
are much distorted by the motion of camera because positions of interest points are not affected by such a geometrictransformation. The TNIP has another good feature that theTNIP is not significantly influenced by occluders because it
counts only positive scores. These claims will be justified
by experiments later.

4. Dense depth map estimation from an image
sequence
This section details each stage of dense depth map estimation shown in Figure 2. In our method, first, interest
points in all the input images are detected by Harris interest operator (A). Next, depth of each detected interest point
is determined by the multi-baseline stereo framework with
TNIP score function (B). Outliers of estimated depths are
eliminated by using its confidence defined by considering
the consistency among the results in multiple frames (C).
Finally, dense depth maps are generated by interpolating
sparse depth data (D).

4.1. Detection of interest points
In the first stage, interest points such as corners and crosspoints of edges are detected in input images by Harris interest operator [7]. Harris operator has been evaluated by
Schmid as one of the best operators with respect to the repeatability rate of detected position under different geometric transformation [9].
Input images are first smoothed by a Gaussian operator.
After that, deviations I x and Iy of pixel intensity are computed for all the pixels in x and y directions, respectively.
Feature quantity F (x) of the pixel x = (x, y) is then computed as a minimum eigenvalue of the matrix A that is defined as below.
Ix (x)Iy (x)Ix (x)2A=.
(6)
Ix (x)Iy (x)Iy (x)2x∈WF (x) = min(λ1 , λ2 ),(7)where λ1 and λ2 are eigenvalues of the matrix A. Aftercomputing the feature quantity F (x) for all the pixels, local maxima of F (x) are detected as interest points. In thisstage, interest points are detected for all the frames in animage sequence.

4.2. Depth estimation for interest points

4.3. Elimination of outliers
In this stage, unreliable depths are rejected by using theconfidences of estimated depths. As shown in Figure 3, thedepth z estimated by using TNIP relates interest points at
projected positions of the 3-D feature point (xz, yz, z) inneighboring frames with one another. In this paper, the confidence Cp of an interest point p is defined by using thisrelation as follows.
/ L i , 1; p ∈ L i }i∈Lp {0; p ∈
Cp =
,
(8)
|Lp |

(a) plane 1(b) plane 2

Figure 4. Textures of planes.
10m

plane 15m
10m

plane 2first frame

last frame

2 5m

In this stage, depths of all the interest points detected in
the stage (A) are computed by maximizing the TNIP scorefunction defined in Section 3. The depth z is searched tofind a maximum TNIP in a given range of depth along a
3-D line from a reference pixel. By repeating the estimation of depth z for all the interest points in the input image
sequence, sparse depth data can be acquired.
Note that, in this stage, any intensity images are notneeded for depth estimation. Only 2-D positions of interest points and camera parameters should be stored to compute TNIP. It means that our method needs only 1/8 memory space to compute depth by compared with SSSD, if 8
bit grayscale images are assumed to be used for SSSD.

middle frame
camera path
Figure 5. Layout of planes and camera path insimulation.

where Lp denotes a set of interest points in neighboring
frames related by the depth z of the interest point p. C pmeans the consistency among depth data obtained in theneighboring frames, and is computed as a ratio that an interest point i(i ∈ L p ) is mutually related with the interest point
p. If all the depths are correctly estimated, Li (∀i ∈ Lp )should equal to L p . Only in this case, Cp becomes maximum value 1. In this stage, depth of the interest point p
whose confidence Cp is lower a than given threshold is regarded as outliers, and is deleted.

5. Experiments

4.4. Depth map interpolation

This experiment is carried out to show the validity of theuse of the TNIP score function for multi-baseline stereo bycomparing it with the traditional score function SSSD. In
the experiment, two textured planes are located in a virtualenvironment, and a virtual camera takes a movie by moving
the camera around these planes. To observe characteristics
of TNIP and SSSD, two kinds of texture patterns are used
for the planes. As shown in Figure 4, one is a natural grass
texture (plane 1), the other is a texture of artificial tile (plane2). The layout of the planes and motion path of virtual camera are illustrated in Figure 5.

Depth interpolation is necessary to generate dense depth
maps because the TNIP-based multi-baseline stereo cannot
estimate a depth at non-interest points. In this paper, we
simply assume that the space among interest points is expected to be planar because interest points are corners of
3-D objects. First, input images are divided into triangle
regions using interest points with Delaunay’s triangulation
method [10]. Next, depth data are linearly interpolated forthese triangles.

We have carried out two kinds of experiments. One isconcerned with the accuracy comparison between SSSD
and TNIP in computer simulation. The other is conducted
for estimating a dense depth map for a real outdoor environment.

5.1. Comparison between SSSD and TNIP in computer simulation

(b) middle frame(c) last frame

Figure 6. Sampled frames from 91 input images.

average error of depth [mm](a) first frame

12000

SSSD (plane 1)
SSSD (plane 2)
TNIP (plane 1)
TNIP (plane 2)

10000
8000
6000
4000
2000
0
1x1

3x3

7x7

15x15

size of window W [pixel]

In this setup, depth of each interest point is estimatedusing all the input images and evaluated for varying two parameters; the size of window W in Eqs. (2) and (5), andthe noise level σ for projected position of 3-D point. To
take into account camera calibration errors about intrinsic
and extrinsic camera parameters, the Gaussian noise withstandard deviation σ is added to projected positions of 3-D
points. To observe raw characteristic of both score functions, outliers are not deleted in this experiment.
Figure 7 denotes average errors of estimated depth values that are computed by comparing them with the groundtruth with respect to varying window sizes and noise levels.
Figure 7 shows that average errors of depth by TNIP are totally lower than SSSD’s except for the case of 15 × 15 window. This experiment has given us an conclusion that 3 × 3
window is the best for TNIP and larger size windows havenever give good scores because too large size windows cannot distinguish interest points in an image. Note that TNIP’s
results for plane 1 and 2 have approximately the same accuracy regardless of existence of occluded part in plane 1 incontrast with SSSD’s. This means that depths by TNIP are
not affected by occlusions and the difference of texture patterns. Even when the Gaussian noise is added to projected
positions, the average accuracy for TNIP has never jumped
up in constant with SSSD’s.
Table 1 indicates the average time to estimate adepth of a single pixel with respect to different window
sizes. The computation time is measured by using a PC
(CPU: Pentium-4 Xeon 3.20GHz dual, Memory: 2GB).
Now, we can confirm that the computational cost of TNIP
is much cheaper than SSSD’s.

SSSD (plane 1)
SSSD (plane 2)
TNIP (plane 1)
TNIP (plane 2)

10000
8000
6000
4000
2000
0
1x1

3x3

7x7

15x15

size of window W [pixel](b) σ=1.0 pixel
average error of depth [mm]Totally 91 input images, some of which are shown in Figure 6, are taken by the moving camera whose motion draws
a quarter circle as illustrated in Figure 5. By the motion of
the camera, the plane 1 is occluded by the plane 2 in after
half of the input images, and both textures are apparently
distorted by the camera motion.

average error of depth [mm](a) σ=0.0 pixel
12000

12000

SSSD (plane 1)
SSSD (plane 2)
TNIP (plane 1)
TNIP (plane 2)

10000
8000
6000
4000
2000
0
1x1

3x3

7x7

15x15

size of window W [pixel](c) σ=2.0 pixels
Figure 7. Average errors in depth estimation.

Table 1. Average computational time for estimating a depth of a single pixel [milliseconds].
window size W 1 × 1 3 × 3 7 × 7 15 × 15
time for SSSD
10.9
24.2
80.3
335.6
time for TNIP
7.2
8.2
9.2
10.7

(a) appearance(b) view volume

Figure 8. Omni-directional multi-camera system: Ladybug.

5.2. Dense depth map estimation in an outdoor environment
In this experiment, an outdoor environment is capturedby an Omni-directional Multi-camera System (OMS): Ladybug [11]. Figure 8 shows an appearance and view volumeof Ladybug. This camera system has six radially locatedcamera units and takes synchronized six image sequencesat 15fps (resolution of each camera: 768 × 1024 pixels).
First, the outdoor environment was captured by the OMS
as 3,000 images (500 frames). Figure 9 shows sampled
frame of six input image sequences. Intrinsic camera parameters including geometric relations of fixed camera units
are calibrated in advance by using a marker board and a 3-D
laser measure [12]. Extrinsic camera parameters of the input image sequences are estimated by tracking both a small
number of feature landmarks of known 3-D positions and alarge number of natural features of unknown 3-D positionsin input images [13]. Figure 10 illustrates the recovered
camera path that is used as an input for depth estimation.
The curved line and pyramids denote the motion path of acamera unit and its posture at every 20 frames, respectively.
The length of the camera path is approximately 29m. The
accuracy of estimated camera path is evaluated as 50mm
about camera position and 0.07degree about camera posture(see [13] for more details).
Next, omni-directional depth maps are actually estimated by the method described in Section 4. In the stage(A), interest points are detected in all the frames of six input image sequences by Harris operator. In this experiment,
1,750 interest points are detected on average in a single input image (10,500 points per frame).
In the stage (B), depths of all the interest points detectedin the stage (A) are estimated using the TNIP score function. In this stage, interest points in the (f − 100)-th to

Figure 9. Sampled frame of input image sequences.

(a) top view(b) side view
Figure 10. Camera path of OMS used for input(29m).

120

100

100

80

80

80

60
40
20

TNIP

120

100

TNIP

TNIP

120

60
40
20

0
20000

40000

60000

80000

0
0

depth [mm]

20000

40000

60000

80000

0

depth [mm](a) point 1(b) point 2

100

100

100

80

80

80

60
40

20

20

0

0
0

20000

40000

60000

depth [mm](d) point 4

80000

TNIP

120

40

40000

60000

80000

(c) point 3

120

60

20000

depth [mm]

120

TNIP

TNIP

40
20

0
0

60

60
40
20
0

0

20000

40000

60000

depth [mm](e) point 5

80000

0

20000

40000

60000

80000

depth [mm](f) point 6

Figure 12. TNIP scores for searching depth.

Figure 11. Result of depth estimation for interest points in Figure 9.

the (f + 100)-th frames at every 2 frames (606 images,101
frames) are used to estimate depth data of the f-th frame.
The size of window W was set as 3 × 3 pixels according to
the result of the computer simulation described in the previous section. The searching range to find a maximum TNIP
in this stage is 1,000mm (near) to 80,000mm (far).
In the stage (C), low confidence depths are eliminated.
The threshold of C p defined in Eq. (8) was set as 0.5 in thisexperiment. Figure 11 shows the results of depth estimation for the images in Figure 9. In this figure, depth values
are corded in intensity. Figure 12 indicates TNIP values ofrandomly selected six interest points in Figure 11. We canconfirm from Figure 12 that each TNIP plot has a single apparent peak at a certain depth value and there are no othercomparable peaks. This means depth estimation can be easily achieved for these interest points.
Finally, omni-directional dense depth maps are generated in the stage (D). Figure 13 shows a panoramic image
that is generated from six input images shown in Figure 9.
Figure 14 shows corresponding dense depth map. By comparing these figures, we can confirm that dense depth map iscorrectly computed for most parts of the input image. However, some incorrect depths are also observed around theboundaries between the buildings and the sky. These incorrect results are caused by depth interpolation over different
objects. To improve the result, region information in input
images should be considered in the triangulation stage (D).

6. Conclusion
In this paper, a novel multi-baseline stereo for a moving
camera has been proposed, where depth can be determinedby only counting number of interest points. The proposed
method shows its real ability when used for long image
sequences and is congenial with omni-directional images.
Our method is robust against occlusions and image distortion problem that are caused by camera motion. Additionally, the computational cost is also cheaper than the method
based on the traditional SSSD function. In the future work,
estimated depth maps will be integrated to reconstruct a 3-D
model of a large outdoor environment.

References[1] M. Okutomi and T. Kanade: “A Multiple-baseline
Stereo,” IEEE Trans. Pattern Analysis and MachineIntelligence, Vol. 15, No. 4, pp. 353–363, 1993.
[2] S. B. Kang, J. A. Webb, C. Zitnick and T. Kanade: “A
multibaseline stereo system with active illumination
and real-time image acquisition,” Proc. Int. Conf. on
Computer Vision, pp. 88–93, 1995.
[3] S. B. Kang and R. Szeliski: “3-D Scene Data Recovery using Omnidirectional Multibaseline Stereo,” Int.
Journal of Computer Vision, Vol. 25, No. 2, pp. 167–
183, 1997.
[4] W. Zheng, Y. Kanatsugu, Y. Shishikui and Y.
Tanaka: “Robust Depth-map Estimation from Image
Sequences with Precise Camera Operation Parameters,” Proc. Int. Conf. on Image Processing, Vol. II,
pp. 764–767, 2000.
[5] T. Sato, M. Kanbara, N. Yokoya and H. Takemura:“Dense 3-D Reconstruction of an Outdoor Scene by

Figure 13. Panoramic image generated from six images acquired by OMS.

Figure 14. Generated dense depth map.

Hundreds-baseline Stereo Using a Hand-held Video
Camera,” Int. Journal of Computer Vision, Vol. 47,
No. 1-3, pp. 119–129, 2002.
[6] M. Okutomi, Y. Katayama and S. Oka: “A Simple
Stereo Algorithm to Recover Precise Object Boundaries and Smooth Surface,” Int. Journal of Computer
Vision, Vol. 47, No. 1-3, pp. 261–273, 2002.
[7] C. Harris and M. Stephens: “A Combined Corner andEdge Detector,” Proc. Alvey Vision Conf., pp. 147–
151, 1988.
[8] H. Moravec: “Towards automatic visual obstacle
avoidance,” Proc. Int. Joint Conf. on Artificial Intelligence, p. 584, 1977.
[9] C. Schmid, R. Mohr and C. Bauckhage: “Evaluationof Interest Point Detectors,” Int. Journal of Computer
Vision, Vol. 37, No. 2, pp. 151–172, 2000.

[10] P. Heckbert Ed.: Graphics Gems IV, pp. 47–59, Academic Press, 1994.
[11] Point Grey Research Inc.: “Ladybug,”
http://www.ptgrey.com/[12] S. Ikeda, T. Sato and N. Yokoya: “High-resolution
Panoramic Movie Generation from Video Streams Acquired by an Omnidirectional Multi-camera System,”
Proc. IEEE Int. Conf. on Multisensor Fusion and Integration for Intelligent System, pp. 155–160, 2003.
[13] T. Sato, S. Ikeda and N. Yokoya: “Extrinsic Camera
Parameter Recovery from Multiple Image Sequences
Captured by an Omni-directional Multi-camera System,” Proc. European Conf. on Computer Vision, Vol.
2, pp. 326–340, 2004.