MVA2002

IAPR Workshop on Machine Vision Applications, Dec. 11- 13,2002, Nara- ken New Public Hall, Nara, Japan

8-8
Entire Building Shape Recovery from Near Distance Images
MIGITA Tsuyoshi*
Department of Intelligent Systems
Hiroshima City University

AMANO Akirat
Graduate School of Informatics
Kyoto University

ASADA Naokit
Department of Intelligent Systems
Hiroshima City University

Abstract
This paper describes a method to recover entire
3D shape of a building from an image sequence.
This is a kind of "Shape and Motion recovery" problem, whereas conventional methods do not work wellwith images taken around a large object in near distance. Since such image sequence is a set of partial
observations, 3D recovery becomes unstable. We
first discuss the property of local minima of thenonlinear optimization function, and then describe
a procedure t o find the global minimum by avoiding pseudo solutions. Experiments using real images
have shown that the proposed method successfully
recovered 3D shapes from eleven sets of image sequence.

1Introduction

This paper presents a method for recovering entire 3D building shape from an image sequence,
based on the Shape and Motion recovery techniques.
Images are taken a t sufficient points to cover entire
building, and are assumed t o be taken a t near distance from the building located in crowded urban
area. In such a situation, each image contains partial observations of the building and the 3D shaperecovery becomes difficult problem because there aremany local minima in solving nonlinear equation.
Such difficulty is not considered and discussed
fully in prior researches. Many conventional shapeand motion recovery methods are proposed and they
avoid this difficulty by assuming some restrictions tothe images, implicitly or explicitly. In the Factorization met hod proposed by Tomasi and Kanade[l],images are assumed to be well approximated by linear projection, i.e. images are taken from far distance compared to the object size. Also in thebuilding shape recovery method by Koch et.a1.[2],camera trajectories are assumed t o be relatively far
from the objective buildings compared with its size,and hence each image contains almost all part of thebuilding with relatively small perspective distortion.
'Address:
3-4-1
Ozuka-higashi, Asaminani-ku, Hiroshima, 731-3194 Japan.
E-mail: rnigitaQcv.its.hiroshima-cu.ac.jp'Address: Yoshidahonmachi, Sakyoku, Kyoto, 606-8501
Japan. E m a i l : amanoQi .kyoto-u. a c . jp
% E m a i l :asadaQits .hiroshima-cu.ac .jp

In the urban situation, however, buildings are
so densely located that their images inevitably becomes close-ups, where each image contains limitedpart of the building. Thus the feature point correspondences become very sparse with the consequence that the objective equation has many local
minima. To recover 3D shape and camera position
from such image sequence, we need t o deal with such
local minima in the optimization process.
To recover entire shape of a building in realisticsituation, we should deal with close-up images whichhave sparse feature point correspondences and havelarge perspective distortion. To cope with this problem, we propose incremental 3D shape recovery procedure. The key idea of our procedure is that we introduced trial-and-error search for our optimization
process in order to find the optimal solution, insteadof deterministic procedure. Note that, although ourprocedure automatically recovers 3D shapes withmany image sets, some human controls are necessary to recover correct shape for difficult image sets.
In the following sections, we first formulate theproblem, then propose procedure to avoid local minima. Finally, we present experimental results forseveral real image sets to show effectiveness of ourmethod.

22.1

Entire Building Recovery
Formulation

Shape and motion recovery from an image sequence, is formulated as nonlinear least-squares
problem[3] which minimizes the sun1 of squared reprojection errors. Specifically,arg min

S t RIufp- P [ R f s p(f,P)ES+ tf]I2(1)where s, is the unknown 3D coordinates of p'th feature point, R f , t f are the unknown rotation andtranslation of f'th camera, ufP is given 2D coordinates of p'th feature point in f'th image, S is theset of indices (f, p) over which the summation is calculated, and P denotes perspective projection.
Given initial value of the shape s, and thecamera position R f , t f , optimal solution is calculated by nonlinear least-squares algorithm[3] suchas Levenberg-Marquardt method or Preconditioned
Conjugate Gradient method [4].

1 1New camera(a) True shape

1 11New

Figure 2: Point reversal.

'- I-

New camera

New pointNew point(b) Recovered shape with naive optimization
Figure 3: Camera reversal.
Figure 1: Local minima of the problem.

2.3
2.2

Analysis of Local Minima

Avoiding Local Minima

Since, there exist many local minima for thisproblem, occasionally, final estimation becomes oneof them according to the initial value. Especially inthe case of near-distance images, many local minima exists. For the feature points and camera positions which are illustrated in fig.l(a), recovered 3D
shape and camera positions become as fig.1(b) when
we use straight forward optimization to the wholedataset a t once.
Problem difficulty can be characterized byamount of overlapping feature points among eachimage. This is evaluated by the ratio of size of S tof x p. Hereafter, we refer this amount as appearance
ratio. Experimentally, many local minima appears
in optimization process if this ratio is low.
To avoid such local minima, we propose an incremental 3D shape recovery procedure. Denoting Si
as i'th subset of S, the procedure can be summarized as a searching process of Si where optimal solution can be obtained for every Si by using R(Si-l)
as initial value, where R(Si-1) represents resulting
solution of Si-1. We start with some small set Sowith which the associated shape and motion can bestably obtained without a priori initialization[3, 41.
Then gradually expand Si until it gets to whole setS.
Occasionally, in the searching step, the situationthat no suitable S, can be found occurs. In suchsituation, we need to backtrack to prior step, andchoose different Si- 1. This set expansion procedure
is simiIar to Tomasi and Kanade's strategy(l1, butthe procedure of backtracking which is key part oflocal minima avoidance, is not considered in their
method, and this is very important in nonlinear optimization process. Our goal is to find the path
{So,S1, ..., S,) such that the resulting optimal values R(Si) can be obtained by using R(Si-l) as initial value. Hence obtained result R(S,) is globalminimum of the underlying equation.

In the optimization process, if resulting residueof equation(1) becomes relatively high, we can easily say that the considering set Si is inappropriate
and choose another set. However, in some situation, it is very difficult to choose another set withwhich the resulting shape becomes global optimal.
In most case, they are classified into two following
categories.
1. point reversal
In fig. 2, the position of newly estimated point
differs between left and right images. Featurepoint positions in the left are optimal, while positions in the right are local minimum. This ispartial depth reversal problem. In prior Shapefrom Motion research, non-partial depth reversal problem is mentioned[3], where recovered depth of each point is coherently reversed.
However, in our near-distance case, partial feature point reversal is observed.

2. camera reversal
In fig. 3, the position of newly estimated camera
differs. Camera positions in the left are optimal, while the right ones are local minimum.
This is also connected t o depth reversal problem. This happens due to low appearance ratio.
If the appearance ratio is loo%, this situation
will not occur.
In such case, reselection of Si is necessary, whileoridinary expansion is just used in usual case. In thenext section, reselection procedures are described.

2.4Optimization Procedure
OPHere, we describe the operations LSL-1 4 Si
which indicates the selection or reselection processof Si from Si-1. Although the selection of Si is arbitrary, we used following selection scheme. Si is'characterized by 3 variables, (s,e, L). The indices( f ,p) in the set S, satisfies following 2 conditions.
(a) The image number f should be in the ranges L f <e.
(b) The point number p should appear a t least L
times in the set.
Mathematically, L in condition (b), must belarger than or equals to 2, because 3D position ofa feature point observed in single image cannot berecovered by triangulation. Moreover, it is known
that the 3D position calculated from only 2 images
are unstable. To avoid these unstability, one should
first recover with relatively large L which yields reliable estimation. Afterwards, decrease L graduallyto 2 so that 3D position of every feature point isrecovered. This control of L is also useful for local
minima avoidance. If the estimation is considered
to be a local minimum, increase of L might remove
unstable feature points and/or camera.
Operations of Si-l 3 Si which we used is listed
as follows.
1. Expand the set by increasing e.
2. Expand the set by decreasing s.
3. Expand the set by decreasing L.
On the other hand, to avoid local minima, operation for reselecting Si is needed. Operations which
we used is as follows.
1. Shrink the set by increasing L.
Our goal is to find the path Si which yields true
final estimation. For this purpose, a heuristic searchmethod is employed which selects one operation ateach step. Starting with SiPl,first one of expansion operation is selected to make a candidate of Si.
If associated residue becomes larger than a threshold, another operation is selected to produce another candidate that gives better residue. If no improvement is made or no other operation is available, backtracking is performed to reselect Si-1.
In the procedure, a local minima is detected bysimple thresholding. However, this thresholding
sometimes fails. In such case, manual control is necessary.
Also, selection of initial set So is very importantto achieve optimal solution. We used following criterion~for selection of initial set.
Appearance ratio is high.
Relatively large L.
If camera positions are roughly known, use images which have long baseline.
Optimal solution can be calculated with the set.

Figure 4: Two images of The Hiroshima Atomic
Bomb Dome.

3Experiments

We have applied our algorithm to 11 real image
sets and successfully obtained 3D shapes and camera positions. Here, we show the results of two ofthese experiments: relatively easy one and relatively
difficult one.
Fig. 4 shows 2 out of 29 images of the Hiroshima
Atomic Bomb Dome, in which 2D coordinates offeature points are also shown. There are 469 feature points to represent the building shape, which
are selected and matched manually. No image contains whole view of the building as shown in thesepictures. Appearance ratio is 17%, which means
it is relatively easy to recover 3D geometry. We
start with 5 images and finally obtained 3D shapeand camera positions shown in Fig.5. Four imagesets including this set were able to recover their 3D
shape and camera positions automatically.
Fig. 6 shows 4 out of 198 images of a gymnasium.
There are 300 manually selected feature points t orepresent the building shape. Some images just contain limited part of the building as shown in figure.
Appearance ratio is 5.1%. Thus, it is very difficult
to recover 3D geometry. Left side of Fig. 7 shows
initial estimation associated with the set So whichcontains 20 images and 28 feature points. Right sideof the Fig. 7 shows 3D shape and camera positionsof intermediate step in search process. Many trial
and backtracking were performed to produce final
estimation shown in fig. 8,9. This is t,he entire building shape with positions and orientations of cameras
displayed around it. From the recovered shape, we
can say that rectangular shape and connecting an-(a) Recovered 3D shape and camera positions.

(b) Side view of the dome with texture image.
Figure 5: Reconstructed Dome

Figure 7: Initial(1eft) and intermediate(right) estimation.

gles of each building edges are well recovered. In thisexperiment, human decision of backtracking was occasionally needed as the problem is very difficult.

4Conclusions

We proposed a method to recover entire 3D building shape from near-distance images which uses
searching technique with backtrack to find optimalsolution.
While this recovery problem is directly formulated as nonlinear optimization problem, we employed searching technique for finding optimal solution. The optimization process is formulated as pathfinding problem. Each node of path is the subset ofindices over which the cost function is calculated.
We employ heuristic search method to find path toavoid the local minima of the associated nonlinear
cost function. When this heuristic search fails, one
can manually control to search another path.
Experimental results on building image sets show
the efficiency of our proposed method.

References[I] C. Tomasi and T. Kanade: "Shape and Motion from Image Streams under Orthography:
a Factorization Method," IJCV, Vol. 9, No. 2,
pp. 137-154, 1992.
[2] R. Koch, M. Pollefeys and L. V. Gool: "Multi
Viewpoint Stereo from Uncalibrated Video Sequences," ECCV '98, pp. 1-55-71.
[3] R. Szeliski and S. B. Kang: "Recovering 3D
Shape and Motion from Image Streams using
Non-Linear Least Squares," CVPR, 1993,752753.
[4] A. Amano, T. Migita and N. Asada: "Stable Recovery of Shape and Motion from Par-Figure 8: Recovered gymnasium and the cameras.

Figure 9: The recovered gymnasium with texture
mapped.
tially Tracked Feature Points with Fast Nonlinear Optimization," Vision Interface 2002, pp.
244-251.