NAVIGATING IN MANHATTAN: 3D ORIENTATION FROM VIDEOWITHOUT CORRESPONDENCES
André T. Martins, Pedro M. Q. Aguiar 1 , Mário A. T. Figueiredo2
Instituto Superior Técnico, Technical University of Lisbon
Institute for Systems and Robotics, 2 Institute for Telecommunications
aftm@mega.ist.utl.pt, aguiar@isr.ist.utl.pt, mtf@lx.it.pt
1

ABSTRACTThe problem of inferring 3D orientation of a camera from video
sequences has been mostly addressed by first computing correspondences of image features. This intermediate step is now seenas the main bottleneck of those approaches. In this paper, we
propose a new 3D orientation estimation method for urban (indoor and outdoor) environments, which avoids correspondences
between frames. The basic scene property exploited by our method
is that many edges are oriented along three orthogonal directions;this is the recently introduced Manhattan world (MW) assumption.
In addition to the novel adoption of the MW assumption forvideo analysis, we introduce the small rotation (SR) assumption,that expresses the fact that the video camera undergoes a smooth
3D motion. Using these two assumptions, we build a probabilistic estimation approach. We demonstrate the performance of our
method using real video sequences.
1. INTRODUCTION
Applications in areas such as digital video, virtual reality, mobile
robotics, and visual aids for blind people, require efficient methods
to estimate the 3D orientation of a video camera from the images
it captures.
Most current approaches rely on an intermediate step that computes 2D displacements on the image plane. This 2D displacements are represented by either a dense map [1] or a set of correspondences between image feature points [2]. Rigidity assumptions are sometimes used to further constraint the solution. Theseassumptions lead to a nonlinear inverse problem relating the 3D
structure with the 2D displacements, which has been addressedby using general non-linear optimization [3, 4, 5, 6], recursive
Kalman-type estimation [4, 7, 8, 9], and matrix factorization [10,11]. Other authors have used correspondences between line segments [12] or surface patches [13], rather than feature points.
While computing correspondences is feasible in simple cases,
it is widely accepted that this is not so when processing real-life
video sequences. This has motivated approaches that estimate the
3D structure directly from the image intensity values [14, 15].
These approaches lead to complex time-consuming algorithms.
The key assumption behind all the methods referred above isthat some property of the scene, either the brightness pattern or
the 3D positions of the features, remains (approximately) constantfrom frame to frame.
In this paper, we propose a new 3D orientation estimation
method for urban (indoor and outdoor) environments, which i) does

without computing the 2D-motion as an intermediate step, and ii)
does not rely on scene constancy assumptions. The basic scene
property exploited by our method is that many edges are oriented
along three orthogonal directions; this is the so-called Manhattan world (MW) assumption recently introduced by Coughlan andYuille [16, 17]. While these authors have used the prior knowledge
captured by the MW assumption to build a Bayesian approach to
3D orientation estimation from a single image, we use it for sequences of images.
The main building blocks of the method herein proposed are:i) recent results in the geometry of 3D pose representation [18],which allow a significant reduction of the computational cost of
the Bayesian estimation algorithm, and ii) a new small rotation(SR) model that expresses the fact that the video camera undergoes
a smooth 3D motion.

2. CAMERA ORIENTATION IN VIDEO SEQUENCES
2.1. 3D Orientation and Vanishing Points
Let (x; y; z) and (a; b; c) be the Cartesian coordinate systems of
the MW and the camera, respectively. We parameterize the camera orientation with three angles (see Fig. 1): , the compass (azimuth) angle, corresponding to rotation about the z axis; , theelevation angle above the xy plane; and , the twist about the principal axis. One thus denotes the camera orientation by O( ; ; ).
z

x
0

y
α

γ

b0 b
a0
a

b0

β
c

P a0

image plane

Fig. 1. Parameterization of the camera orientation. Left: compass< =2).
angle and elevation angle (with Px 0, we have
Right: twist angle represented on the image plane.

j jFor a radial-distortion-free pinhole camera, the three vanishingpoints, corresponding to the x, y, and z axes, project on the image

2.3. Small Rotations Model

plane at, respectively,Fx = f R

tan

Fy = f R

cos
cot

Fz = f R (0;

T

; tan

(1)

T

; tan

cos

cot )

(2)

T;

(3)

where ()T denotes transpose, f is the focal length, and R is thetwist matrix,

R =



cos
sin



sin
cos

:

(4)

O

Estimating the orientation ( ; ; ) can thus be achieved by locating the vanishing points on the image plane [2].

Let us now assume that the camera is moving and acquiring a sequence of frames I1 ; : : : ; IN . It is clear that the variation of thecamera orientation only depends on the rotational component of
the motion. Let k ( k ; k ; k ) denote the orientation at the k-th
frame. In typical video sequences, the camera orientation evolves
in a smooth continuous way. We formalize this property by introducing the small rotations (SR) model, next described.
Let k (k ; ek ) be the rotational component of the camera
motion between the k-th and (k + 1)-th frames, where k and ek
denote the angle and the axis of rotation, respectively. The SR
model states, independently of ek , that there exists a small fixed
angle  such that k . Here, we take  = 5Æ , which implies
that for a sampling rate of 12:5 Hz the rotation angle is less thanÆ
62:5 in each second; this is an intuitively reasonable assumption.
As a consequence of the SR assumption, we can show thatthe variations of the compass, elevation and twist angles between
consecutive frames are bounded as follows:

f
O

R

j j

2.2. Equiprojective Orientations

F fg

Let = Fx ; Fy ; Fz be the set of vanishing points. Since thesevanishing points are mutually indistinguishable, it is the set ,rather than each element per se, which provides the solution to theorientation estimation problem.
In [18], we have introduced the concept of equiprojective orientations: two orientations are termed equiprojective if and only
if they lead to the same set of vanishing points. We have provedthat equiprojectivity is an equivalence relation and that each corresponding equivalence class F contains 12 elements, except for
singular cases. The general solution to the orientation estimation
problem is thus a 12-element set F of possible camera orientations. We have also provided closed-form expressions for the solution set given any particular element; this turns out to be very
important in reducing the space to be searched for a solution. Finally, we have proved that any equivalence class F contains atleast one orientation ( ; ; ) verifying

E

E

O

2
where

i  i
4

;

4

2

;

'= 
2

j k+1
j k+1
j k+1

F

E

i  i
4

;

4

; and

p
arctan2 ] '; '] ;(5) 54:7Æ :2

2This means that, for any camera orientation, it is always possible
to find one vanishing point inside the shaded area shown in Fig. 2.

ϕ ∼ 54.7
0
f

g

where

 = arccos


1

kj
kj
kj
cos

 
 
 ;

j k+1
cos

kj

Fig. 2. Area of the image plane where it is guaranteed that there
exists at least one vanishing point.

cos

k cos k+1



 ;j k + k+1 j   , and  = =2, otherwise.
For an orientation Ok in the region defined by (5), it is guaranteed that j k + k+1 j  =4 + =4 +     . In particular,
with  = 5Æ , we have   arccos(2 cos 5Æ 1)  7:1Æ . This
enables a significant reduction of the search space for the estimateof Ok+1 , given the previous orientation Ok .
if

3. ORIENTATION ESTIMATION

fO
g

O g

Our goal is to estimate the sequence of orientations 1 ; : : : ; Nfrom the observed sequence of images I1 ; : : : ; IN . This is donein a probabilistic estimation framework using the MW and SR assumptions.

f3.1. Probabilistic Formulation
The MW assumption states that all images contain many edges
consistent with the x, y and z axes [16, 17]. Hence, we use thestatistics of the image intensity gradient Ik to extract this information. Non-relevant pixels are previously excluded by nonmaxima suppression followed by thresholding of the gradient magnitude. Finally, the gradient magnitude is quantized, which allows
building a discrete probabilistic model for edge strength. These
pre-processing yields, for each image, a set of pairs Eu = (Eu ; u ),where Eu is the quantized edge strength, and u the gradient direction, for each relevant pixel u = (u1 ; u2 ) . The probabilistic formulation is built from the following elements:

r

f g f

film

(6)
(7)
(8)

g

2f

g

1; :::; 5 which
Pixel classes: each pixel u has a label mu
indicates that u belongs to: (1) an edge consistent with the x axis;(2) an edge consistent with the y axis; (3) an edge consistent withthe z axis; (4) an edge not consistent with either the x, y or zaxes; (5) the set of non-edge pixels. These classes have a priori
probabilities Pm (mu ); mu = 1; :::; 5 .

fgFactorization assumption: at each pixel, the gradient magnitude
and direction are independent. Moreover, the gradient magnitude
is independent of the orientation and of the pixel location, given
the class label. Thus,

P (Eu jmu ; O; u) = P (Eu jmu )P (u jmu ; O; u);

j

6

(9)

j

where P (Eu mu ) = Pon (Eu ), if mu = 5, and P (Eu mu ) =Poff (Eu ), if mu = 5. Here, Pon (Eu ) and Poff (Eu ) are theprobability mass functions of the quantized gradient magnitudeconditioned on whether pixel u is on or off an edge, respectively.

Decoupling: from (3), it is clear that the vanishing point Fz does
not depend on the compass angle . Thus, any estimation procedure can be decoupled into two stages: the first ignores information from the edges consistent with the x and y axes, and uses theremaining edges to estimate and , a problem with 2 degrees of
freedom (dof); the second stage estimates , given the estimatesof and , which is a 1-dof problem. This decoupling avoids the
3-dof joint estimation of the three angles.

Gradient direction pdf: let U ( ) be a uniform pdf on ] 2 ; 2 ].
In the first stage (estimation of and ) we only consider edges
consistent with the z axis (mu = 3), thus

P (u jmu ; ; ; u) =
where





Pang (u )U (u )

if mu = 3otherwise;(10))=(2 ) if t 2 [ ;  ]2 )if t 2 ] =2;  [ [ ]; =2];
with  = 0:1, and  = 4Æ . In (10), u = u z ( ; ; u) (mod ) is the difference between the measured gradient direction andPang (t) =

(1

=(

that that would be ideally observed at pixel u, given and .
In the second stage (estimating with fixed b and b),

2 f1; 2; 3g (11)2 f4; 5g ;where u has a similar meaning as in (10), now for mu 2 f1; 2; 3g.

(u )P (u jmu ; ; b; b; u) = PUang
(u )

if mu
if mu

Joint likelihood: the joint likelihood for the relevant data of thek-th frame, Eu (we omit the index k, for economy) is obtainedby marginalizing (summing) over all possible models at each relevant pixel, and assuming independence among data from different
pixels:f g

P (fEu g jOk ) =5
Y X
P (Eu jmu ) P (u jmu ; Ok ; u) PM (mu ) :u mu =1

j

O

O

(12)

where P (u mu ; k ; u) represents (10) and k stands for ( ; ),in the first stage, while P (u mu ; k ; u) represents (11), and k
stands for ( ; b; b), in the second stage.

j

O

O

where P ( ; ) is a prior. In the first frame, this prior is flat over theÆ ÆÆÆ] 45 ; 45 ] and] 54:7 ; 54:7 ], where
entire domain(5) guarantees the existence of a solution. For the other frames,k > 1, the prior expresses two assumptions: i) small rotations(see (7) and (8)), and ii) smoothness of the motion. These assumptions are formalized by taking P ( ; ) as a truncated bivariate Gaussian with mean [ bk 1 ; bk 1 ]T , defined over the region] bk 1 ; bk 1 +  ] and]bk 1 ; bk 1 +  ]. The variance of this Gaussian allows controlling the tradeoff between thesmoothness of the estimated sequence of angles and the accuracyof this estimates.
Given bk and bk , we then estimate the compass angle k :

2

2

2

2

bk = arg max log P (fEu g j ; bk ; bk ) + log P ( ):For the first frame, the prior P ( ) is flat over ] 45Æ ; 45Æ ]. For
k > 1, as above, the prior is a truncated Gaussian with mean bk 1 ,defined over ] bk 1  ; bk 1 +  ].
If a given estimate bk ( bk ; bk ; bk ) is located outside of theminimal region defined in (5), we replace it by an equiprojectiveorientation inside that region. As explained in the last paragraph ofsubsection 2.3, this allows  to be less than 7:1Æ , hence keeping
a small search space.
A consequence of the fact that we sometimes replace an estimate bk by an element of its equiprojective equivalence class( bk ), is that the resulting sequence of estimates may not verify
the SR assumption. Thus, as a final step, we pick an orientationfrom each equivalence class ( bk ) , such that the resulting sequence satisfies the SR model.

O

j j

EO

O

fE O g4. EXPERIMENTS
We tested our algorithm with outdoor MPEG-4 compressed video
sequences, acquired with a hand-held camera. The sequences areof low quality due to some radial distortion and several over andunderexposed frames. Our algorithm estimated successfully theorientations for the vast majority of the sequences tested. Typicalrunning time for each (288 360)-pixels frame is less than 10
seconds, on a 1.5 GHz Pentium IV, using a straightforward nonoptimized MATLAB implementation.
Figs. 3 and 4 show some frames of two sequences with superimposed cubes indicating the estimated orientations of the MW
axes. Notice that the algorithm is able to estimate the correct orientation, despite the presence of many edges not aligned with the
MW axes (e.g., people in Fig. 4).
Fig. 5 plots the estimates of the orientation angles, for these
two sequences. Note that the estimates on the right hand plot areslightly noisier than those on the left, due to the worse quality of
the image sequence. Obviously, we can control the smoothness ofthese estimates by adjusting the prior variances referred in Subsection 3.2; here, these variances are the same for both sequences andall the three angles. Of course, there is a tradeoff between smoothness and the ability to accurately follow fast camera rotations.



3.2. Locating the Estimates
As explained above, the estimation procedure is decoupled into
two stages. In the first stage, we find MAP estimates bk and bk ,bk ; bk= arg max log;

P (fEu gk j ; ) + log P ( ; ) (13)

5. CONCLUSIONS
We have proposed a probabilistic approach to estimating camera
orientation from video sequences of urban scenes. The method
avoids standard intermediate steps such as feature detection andcorrespondence, or edge detection and linking. Experimental results show that the method is able to handle low-quality video sequences, even when many spurious edges are present.
6. REFERENCES[1] B. Horn and B. Schunck. Determining optical flow. Artificial
Intelligence, 17:185–203, 1981.
[2] O. Faugeras. Three-Dimensional Computer Vision. MIT
Press, 1993.
[3] M. Spetsakis and Y. Aloimonos. A multi-frame approach tovisual motion perception. Int. Journal of Computer Vision,
6(3):245–255, 1991.
[4] T. Broida and R. Chellappa. Estimating the kinematics andstructure of a rigid object from a sequence of monocular images. IEEE TPAMI, 13(6), 1991.
[5] J. Weng, N. Ahuja, and T. Huang. Optimal motion and structure estimation. IEEE TPAMI, 15(9):864–884, 1993.
Fig. 3. Frames 20, 30, 40, and 50 of a video sequence with superimposed cubes representing the estimated orientation of the MW
axes.

[6] R. Szeliski and S. Kang. Recovering 3D shape and motion
from image streams using nonlinear least squares. Jounal of
Visual Comm. and Image Representation, 5(1), 1994.
[7] A. Azarbayejani and A. Pentland. Recursive estimation of
motion, structure, and focal length. IEEE TPAMI, 17(6),1995.
[8] S. Soatto, P. Perona, R. Frezza, and G. Picci. Recursive motion and structure estimations with complete error characterization. In Proc. of IEEE CVPR, pages 428–433, 1993.
[9] J. Thomas, A. Hansen, and J. Oliensis. Understanding noise:
The critical role of motion error in scene reconstruction. In
Proc. of IEEE ICCV, pages 325–329, 1993.
[10] C. Tomasi and T. Kanade. Shape and motion from image
streams under orthography: a factorization method. Int. Journal of Computer Vision, 9(2), 1992.
[11] P. Sturm and B. Triggs. A factorization based algorithm for
multi-image projective structure and motion. In European
Conference on Computer Vision, Cambridge, UK, 1996.
[12] L. Quan and T. Kanade. A factorization method for affine
structure from line correspondences. In Proc. of IEEE CVPR,San Francisco, CA, USA, 1996.

Fig. 4. As in Fig. 3, for frames 110, 130, 150, and 170 of anothervide sequence.

[13] P. Aguiar and J. Moura. Three-dimensional modeling fromtwo-dimensional video. IEEE Trans. on Image Processing,10(10):1541–1551, 2001.
[14] B. Horn and E. Weldon Jr. Direct methods for recovering
motion. Int. Journal of Computer Vision, 2(1):51–76, 1988.

0

−20

−60
0

[16] J. Coughlan and A. Yuille. Manhattan world: Compass direction from a single image by Bayesian inference. In IEEE
ICCV, Corfu, Greece, 1999.

−40

−20

−40

[15] G. P. Stein and A. Shashua. Model-based brightness constraints: On direct estimation of structure and motion. IEEE
TPAMI, 22(9):992–1015, 2000.

Degrees0

Degrees

20

−60

α
β
γ

−80
20

40
60
Frame number

80

0

α
β
γ
50

100
150
Frame number

200

250

Fig. 5. Camera angle estimates, for the sequences of Figs. 3 and 4.

[17] J. Coughlan and A. Yuille. The manhattan world assumption: Regularities in scene statistics which enable Bayesianinference. In NIPS, Denver CO, USA, 2000.
[18] A. Martins, P. Aguiar, and M. Figueiredo. Equivalenceclasses for camera orientation. Submitted for publication.