A Factorization Method Using 3-D Linear Combinationfor Shape and Motion Recovery
Kuo-chang Hwang
Japan Systems Co., Ltd.
2-31-24 Ikejiri, Setagaya, Tokyo, Japankouk@japan-systems.co.jp

Naokazu Yokoya, Haruo. Takemura, Kazumasa Yamazawa
Nara Institute of Science and Technology
8916-5 Takayama, Ikoma, Nara, Japanfyokoya, takemura, yamazawag@is.aist-nara.ac.jp

Abstract
This study proposes a new factorization method forshape and motion recovery. In past, the fourth greatest singular value of the measurement matrix was ignored. But
when noise is larger enough so that the fourth greatest
singular value can not be ignored, it would be difficult
to get reliable results by using the traditional factorization method. In order to acquire reliable results, We startwith adopting an orthogonalization method to find a matrix
which be composed of three mutually orthogonal vectors.
By using this matrix another matrix can be obtained. Then,the two expected matrices which represent shape of object
and motion of camera/object, can be obtained through normalization. This study also conducts several experiments todiscuss the feasibility of the proposed method.

1. Introduction
Much attention has been put on computing the 3-D shapeand motion from a long sequence of images during the last
few years. Previous approaches for solving this problem
usually consider: 1) whether the camera is calibrated or not,2) whether a projective or an affine model is used [8][10][2].
Among them, Tomasi and Kanade [8] developed a robustand efficient method for accurately recovering the shapeof object and motion of camera/object from a sequenceof images under orthographic projection, called factorization method. The factorization method has been believed
to be possible under linear approximations of imaging system and without camera calibration. Lately, the original
factorization method have been extended to scaled orthographic, paraperspective projection [4] and perspective projection [9]. However, in most cases they all start with thethree greatest singular values acquired by the Singular Value
Decomposition (SVD) technique [5] to factor the measurement matrix into two matrices. Then, by normalizing thetwo matrices the expected two matrices which represent object shape and camera motion is obtained.
Unfortunately, when the image noise is larger enough sothat the fourth greatest singular value can not be ignored,
the traditional factorization method might fail to reach theaccurate solution. Another problem remains in the normalization procedure of the factorization method. It is becausethat sometimes the unknown invertible matrix might be difficult to get [6][1].
This study concentrates on factorization method fromthe Rank-Theorem perspective, and improves the step offactoring by the SVD technique. According to the RankTheorem, it would be possible to get three mutually orthogonal vectors from a measurement matrix [3]. Once the threemutually orthogonal vectors were identified as one matrix,
it would be easy to take a form of 3-D linear combination
equation for obtaining another matrix whose elements are
three coefficients of 2F sets (F represents the number offrames). Then the normalization of the two matrices canhelp this study to recover object shape and camera motion,and by using the proposed method the problem of normalization can be easily solved (described in Section 4).
This paper presents a form of factorization under orthographic projection, although the form of factorization also
can be easily extend to other projective models. This study
also provides the field of structure-from-motion with threeadvantages as follows: 1) It can robustly recover object
shape and camera motion even if the emergence of image
noise; 2) It can effectively solve the problem of normalization; 3) Its computation is very fast due to a simple algorithm. In addition, this paper also presents a series ofexperiment to show the feasibility of the proposed method.

2. A Summary of Traditional Factorization
Method and Problems Description
This section presents a summary of the traditional factorization method under orthographic projection, and points

out two problems: one is on the fourth greatest singularvalue (described in Section 2.3), and the other is on the nomalization (described in Section 2.4).

and the fourth and its following singular values almost ap~,
proaches to zero. Equation (5) displays this process. W^^
factoring it into a product of two matrices M and S .

W~

U1 1 V1T + U2 2 V2T
U1 1 V1T
^ S
^
(5)
= M
From Equation (5), motion matrix M and shape matrix S

2.1. Orthographic Projection='

Under orthographic projection model, the projection

xfp  yfp) of the p-th point sp = (sxp  syp  szp )T in 3D
space onto image frame f is given as follows:(

xfp = iTf (sp tf )


yfp = jTf (sp tf )

;

t



;

can be defined as follows:1

where f = (txf  tyf  tzf
origin to the origin of image frame f . f and f are a pairof unit vectors which represent x-axis and y-axis. Theseequations can be rewritten as:)T is the vector from the worldi

xfp = mTf sp + txf jyfp = nTf sp + tyf :





1

M^ = U1 12 

(1)S^ = 12 V1T :(6)First Problem: When noise corrupts the images, the~ will no longer be three. Consider a problem
rank of W
when the fourth greatest singular value is not so small that
4 ' 3 . Therefore, adopting the SVD algorithm cannot
accurately or completely reconstruct the shape and motion.
The solution of this problem will be shown in Section 3.

(2)

2.2. Measurement Matrix^ and S^2.4. Normalization of M

Suppose that P feature points were tracked over F
frames of an image sequence were tracked, and their image coordinates f(xfp  yfp )jf = 1 : : :  F p = 1 : : :  P g
were collected into a single 2F  P measurement matrixW.
x11 : : : x1P

The decomposition of Equation (5) is determined as alinear transformation. Any non-singular 3  3 matrix A^ and S^. Theirand its inverse could be inserted between M~
product should still equal to W . Thus the actual motion andshape are provided as follows:2
3
66 : : : : : : : : : 77
6
7
W = 66 xyF 1 :: :: :: xyF P 77 :64 : 11: : : : : :1:P: 75^^
M = MAS = A;1 S:(7)
The correct A can be determined by using two geometry(3)

constraints that can be defined as follows :yF 1 : : : yF P

mf 2 = 1 nf 2 = 1mf nf = 0:jEquations (2) and (3) of all points and frames can now be
combined into a single matrix equation W = MS + T Tp ,where M is the 2F  3 motion matrix whose rows are Tf
and Tf , S is the 3  P shape matrix whose columns consist of p points, and T is the 2F  1 translation vector thatcollects the projections of camera translation along the image plane and p = (1 : : :  1)T . Then a “registered” measurement matrix can be developed for which the translation
vector is subtracted from W as follow:

n

j

(8)

Second Problem: In the original papers [8][4], no details of the normalization procedure or criterion to be optimized were presented, and in [6][1] pointed out that many
choices are possible for this normalization and a variety of
results have been obtained depending on the choice. Indeed,at our knowledge, matrix A might not be obtained. The
more detailed description of the reason and the solution canbe found in Section 4.

s

e

;

j



e
m

W~ = W T eTp = MS:j(4)

3. Decomposition of Measurement Matrix Using 3-D Linear Combination

According to Rank-Theorem, the maximum rank of M and
S is three. Thus, the maximum rank of W~ is also three.

~ be three was inIn Section 2.2, maximum rank of W
troduced. Let us consider the Rank-Theorem again. The
rank of three means that there are three independent vec~ is projected into a space which istors. Each row of W
constructed by the three mutually orthogonal vectors. This
study attempts to find the three mutually orthogonal vectors
S^, and then to solve M^ by using the S^ and W~ .

2.3. Decomposition of Measurement Matrix withSVD~ )  3 is proved. Here,As previously discussed, rank (W~ ) = 3. Hence, the three greatest sinassume that rank (Wgular values can be determined through the SVD technique,23.1. Orthogonalization

4. Solving the Problems of Normalization

First, three orthogonal vectors must be found or built~ . A good method, the Gram-Schmidt orthogonalfrom W
ization method, can straightforwardly and efficiently find
three mutually orthogonal vectors. Rewrite the elements of
W~ to be f = ( f 1  f 2  : : :  fp )T , and suppose thatthe rank of 3  P matrix S~ = ( k1  k2  k3 ) is three.
For getting the three orthogonal vectors i  i = 1 2 3, theGram-Schmid orthogonaliation method is extended as follows:

In Section 2.4, a summary of the solution of normalization has been described. However, Equation (8) is not sufficient enough for obtaining the invertible matrix A. Here,
how to find A with geometry constraints will be redescribed.
Geometry Constraint: The matrix A can be solved by
two geometry constrains, one is the length of unit vector f
and f , and the other is the inner product of orthonormalityof axes. Here, Let B be a symmetric matrix, then the following equations can be developed to satisfy these constraints.

w~

w~ w~

^s1 = w~ k1 
^sj = w~ kj;

w~
w~ w~ w~^s

X ^sTi;1 w~ kjm^ Tf Bm^ f = 1 m^ Tf+F Bm^ f +F = 1m^ Tf Bm^ f +F = 0:(9)^si;1 2 ^si;1  j = 2 3: (10)


k

i=2

j

k

T

k

kk

B = L LT :

0 2F
X T
G(B ) = 1 @ (m^ f Bm^ f

(11)

2

~

w~ f = m^ f 1^s1 + m^ f 2^s2 + m^ f 3^s3

f =1

; 1)

2

+

1
(m
^ Tf Bm^ f +F )2 A :

F
X
f =1

(15)
Then A can be determined as :A = L 21 R RRT = I:

(12)

(16)

According to Equation (16), the diagonal elements  i ,must be positive, Indeed,  i might not benecessarily positive so that A cannot be solved. The reason is why a problem described in Section 2.4 was pointed
out. Of course, the iterative process can be terminated, or B
can be redefined to develop an approximate symmetric matrix by using non-linear algorithm. However it seems nota good idea. By using the proposed method, because thefirst vector 1 has 2F selection so this problem can be easily
solved that all i are positive. The solution of this problem
is demonstrated as the following procedures:

and as previously described, by using the proposed algo~ can be also separated into M^ and S^, asrithm (3DLC) W
good as Equation (5) obtained by the SVD technique.
In Section 2.3 a problem was pointed out that the fourth
greatest singular value which is very close to the third greatest singular value (4 ' 3 ). Let us consider again, in this~ will be over three. The solution ofsituation the rank of W~
the problem is that even if the 4 ' 3 , the elements of W
can be also projected into a space which is constructed byS^ through the proposed method.

i = 1 2 3 of^s

3.2. Determination of ^s1

1. Let j = 1.

^s

So far, how to determine the first independent vector 1
was not described. The determination of 1 has many approaches. In general, there are three alternative ways forsolving this problem as follows: 1) Based on the generalrule, the feature points of the first frame are the most accurate with respect to all other frames. The first vector could
be chosen. 2) Anyone of the exact vector i could be cho~ . 3) Choosing a new vector which is obtained
sen from W~ also could be considered. In our exby the average of W
periment, the first approach is employed.

^s

(14)

Because W is not accurate, Equation (13) can not provide us with a solution of B. Instead, the conjugate gradient method [5] is adopted to reach a minimum value of theEquation (15) through iterations of acquiring B value.

As a consequence, the rows of W are the product of theelements of i multiplied by m
^ fi in each equation (frame)
as following expression,

^s

(13)

From Equation (13), the matrix B can be developed as :When the three mutually orthogonal vectors were identified as one matrix, it would be easy to take a form of 3D
linear combination equation for obtaining another matrix
whose elements are three coefficients of 2F sets (shown inEquation (12)).

m^ fk = ^sk^s w~2f  k = 1 2 3:ij

2. Let^s1 = w~ j .

3. By using Equation (10),^s2 and ^s3 can be solved.

^ , Equation (15) can help
4. For getting another matrix M
us to check i is positive or not.

w~

5. If 9i  0 then goto (2) until all i are positive.
In our experiment, the positive  i can be successfully obtained only through one or twice selection.
35. Experimental Results

are evaluated by Equation (17).

 = L15.1. Evaluation of Recovered Shape

d3
d4
d5
5

0

d6
d7

3

d8
d9
d10

d11

k

k

(17)

k

In relation to motion recovery, this experiment only focuses on y-axial rotation because my laboratory does nothave much equipments for measuring other motion. Figure
3 was acquired by a static digital camera, and the target isrotated 10 degrees on each frame. The whole sequence is 6
frames. The result is shown in Figure 4 which illustrates thecomparison between the measured rotation and computed
y-axial rotation of object with the proposed method.

d2

4

Real

k

Estimationi :Estimation

5.2. Evaluation of Recovered Motion

d1

2

i=1

;

Through the normalization of (d1     dL), L = 11  2sides ;1 = 21, Using the proposed 3DLC method,  =0:045 can be obtained, and Using the traditional SVD
method  = 0:042 can be obtained. As a result, the errorof estimated size was within the limit of 4.5 percent.

The proposed factorization method is first performed
with a real image sequence for shape recovery. Experimental target is acquired by hand-held video camera. For feature
tracking, an algorithm is adopted based on [7]. At the beginning, 16 points are selected in the first frame, and thesefeature points are automatically tracked and kept throughout a sequence of 16 frames shown in Figure 1. The reconstructed shape is shown in Figure 2. The recovered shape isvery similar to real object for visual comparison.

1

L
X
Reali

60

measuredcomputed

50

Figure 2. Reconstructed shape.

40(degrees)

Figure 1. The 16 feature points selected
on 1st frame.

30

20

10

0

To evaluate the shape recovery performance quantitatively, the orientations of facets in relation to one another are
shown in Table 1 which illustrates the comparison of the results of the three ways: measured angles on the actual model(real), estimated angles with traditional method (SVD) andestimated angles with the proposed method (3DLC).

Figure 3. The 6 feature points selected
on 1st frame.

real bestimation(SVD)

estimation(3DLC)

45

46 47

44 21


45
80
80
90
90
85
0
0

: 
47:54
82:08
80:91
88:68:
101:71
91:77
3:88
4:04

2

3
4
(frame number)

5

6

Figure 4. Measured
and computed yaxial rotation.

5.3. Analysis of Synthetic Data with Noise

Table 1. Quantitative evaluation of shape recovery.
Facets
0–1
3–4
0–2
3–5
1–2
4–5
0–3
1–4
2–5

1

This study also demonstrates the robustness of the proposed method in the presence of noise. A situation is simulated that 4 = 3 . For attempting to solve the first problem
by using the proposed method, a comparison between the
proposed 3LDC method and traditional SVD method will
be displayed on two synthetic image sequences shown in
Figure 5. One (a) is 16 feature points and whole sequenceis 70 frames, and the other (b) is 80 feature points and whole
sequence is 100 frames, and their the fourth greatest singular value are equal to the third.
In Figure 6, the results in left side were obtained with
the SVD technique and the results in right side were obtained with the proposed 3DLC method. From Figure 6,
it is observed that (a) could not recover shape completely,but (c) could recover, because that (c) has more points and: 
45:58
80:97
81:96
89:68
97:02
89:08
5:78
1:38

The distance of the d1     d11 (shown in Figure 2) arealso measured. The error between real and estimated data
4

5000

frames than (a). Although (c) could recover, several points
were not observed on the same plane. By comparison, it isclearly shown that (b) and (d) could accurately recover theobject shape.

SVD
3DLC

4500

( msec )

4000
3500
3000
2500
2000
1500
1000

40

500

20

16 points, 70 frames

80 points, 100 frames

0
20

40

60

30

40

50

60

70

80

90

100

( points )

60
80
80
100

Figure 7. Comparison of computational cost.

(pixel)(pixel)

100
120

120

140

140

6. Conclusions

160
160
180
180

200

200
80 100 120 140 160 180 200 220 240 260 280(pixel)

(a)

220
50

100

150

200
(pixel)250

In this paper, a new factorization method which uses 3-D
linear combination to decompose the measurement matrix
for shape and motion recovery was proposed.
From good point correspondences, the proposed method
can not only recover the object shape accurately comparably to those by SVD technique, but also recover robust camera/object motion. It is also demonstrated that when noiseis larger enough so that the fourth greatest singular value
can not be ignored, the proposed method can still recover
the shape robustly. Furthermore, the proposed algorithm isvery simply and fast. As a consequence, the present work
expands the application of the shape and motion recovery
from unreliable data.
Future works include: (1) extension of the method toother projective models; (2) application of the method to
3D model construction of real complex scenes.

300

(b)

Figure 5. Trajectories of two synthetic data inwhich 4 = 3 .

(a)

(b)

References(c)[1] K. Deguchi. 3-d shape reconstruction from endoscpoe image
sequences by the factorization method. IEICE Trans. Inf. &Syst., E79-D(9):1329–1336, 1996.
[2] O. D. Faugeras. Three-Dimensional Computer Vision. The
MIT Press, 1993.
[3] K. Hwang. A new factorization method based on 3d linear
combination for shape and motion recovery. The 55th General Conf. of IPSJ, 2(5AB-3), Sept. 1997.
[4] C. J. Poelman and T. Kanade. A paraperspective factorization method for shape and motion recovery. Tech. Rep.
CMU-CS-93-219, Dec. 1993.
[5] W. H. Press. Numerical Recipes in C. Cambridge University
Press, 1988.
[6] T. Sasano and K. Deguchi. On the factorization method forshape from image streams. IEICE Tech. Rep., Jan. 1994.
[7] J. Shi and C. Tomasi. Good features to track. IEEE CVPR,
pages 593–600, June 1994.
[8] C. Tomasi and T. Kanade. The factorization method for therecovery of shape and motion from image streams. Proc.
Image Understanding Workshop, pages 459–472, Jan. 1992.
[9] B. Triggs. Factorization methods for projective structure andmotion. Proc. Computer Vision and Pattern Recognition,
pages 845–851, 1996.
[10] S. Ullman. The Interpretation of Viusal Motion. The MIT
Press, Cambridge, MA, 1979.

(d)Figure 6. Reconstruction of object shape fromsynthetic data shown in Figure 5: (a) and (c)are with traditional method, and (b) and (d)are with the proposed method.

5.4. Computational Cost
We also show a comparison of efficiency between the
proposed 3DLC algorithm and the SVD technique. For
measuring computational cost, 20 30     and 100 feature points are automatically selected in a sequence of 100
frames (the first frame is also shown in Figure 1). The measured computational costs are shown in Figure 7. Here, thefeature tracking time is excluded. In result, the proposed
3DLC algorithm is more efficient than SVD. Especially,
when points increase, the difference between the SVD technique and the proposed algorithm becomes obvious.
5