## Project: Shape and motion from image streams: A factorization method

Table of Contents |

## Introduction

The structure from motion - recovering scene geometry and camera motion from a sequence of images - is an important task and has wide applicability in many tasks, such as navigation and robot manipulation. Tomasi and Kanade [1] first developed a factorization method to recover shape and motion under an orthographic projection model, and obtained robust and accurate results. Poelman and Kanade [2] have extended the factorization method to paraperspective projection. Triggs [3] further extended the factorization method to fully perspective projection. This method recovers a consistent set of projective depths (projective scale factors) for the image points.

In this project, we implemented these three factorization methods, and comparisons are shown.

**The report is available at Factorization.pdf**

1st frame | 50th | 100th |

Tag: Scientific ComputerVision SfM Matlab

## Factorization Method

### Orthographic Case [1]

Given an image stream, suppose that we have tracked feature points over frames. We then trajectories of image coordinates We write the horizontal feature coordinates into an matrix Similarly, an matrix is built from the vertical coordinates

Define the *measurement matrix* of size

Compute the translation vector whose each entry is the mean of the entries in the same row of the measurement matrix

Define the *registered measument matrix*

The can be expressed in a matrix form:

where the matrix of size

represents the camera rotation, and the matrix of size

is the shape matrix. The rows of represent the orientations of the horizontal and vertical camera reference axes throughout the stream, while the colums of are the coordinates of the feature points with respect to their centroid. The goal of the factorization method is to compute the matrices and

#### Step 1

Compute the singular-value decomposition

#### Step 2

Define which is the first three columns of , which is the first submatrix of , and which is the first three rows of

Define and

#### Step 3 - Metric Constraints

Impose the metric constraints,

where is a matrix, and , are elements of

To solve , we can

- use Newton's method, or
- define and solve the linear system of equations for and use Cholesky decomposition to get

**Step 3.1 - Solving the linear system**

We used the 2nd way. Morita and Kanade [4] explains the steps to compute Q. By denoting

the quadratic system can be rewritten as

where the matrix , the vector and the vector are defined by

where has ones and zeros, and

The simplest solution of the system is given by the pseudo inverse method, such that

The vector determines the symmetric matrix The Cholesky decomposition or eigen decomposition or square root of a matrix of gives as long as the is positive definite.

**Step 3.2- Enforcing positive definiteness**

We might obtain a matrix that is not positive definite when we estimeated using the linear method. Higham [5] introduced a method computing a 'nearest' symmetric positive semidefinite matrix from a matrix. The lecture note [6] gives the easy notation.

First, we compute the symmetrix matrix as

In our case, the matrix is already a symmetric matrix. Now we eigen decompose :

and form the matrix by setting any negative eigenvalues to zero. The positive semidefinite matrix that is closed to is then given by

However, we want a positive definite matrix. In this case, we set any nagative eigenvalues to The reason is apparent from the definition of the positive definite matrix. Furthermore, we want the matrix it can be simply obtained as without computing

As a result,

- Eigen decompose
- Form a matrix by setting any negative values to
- Compute

#### Step 4

Compute the rotation matrix and the shape matrix as

#### Step 5

Align the first camera reference system with world reference system by forming the products

where the orthonomal matrix rotates the first camera reference system into the indentity matrix.

### Paraperspective case [2]

Only the Step 3 - Metric Constraints - is different with the orthographic case.

Let be the estimated motion matrix

Let be the translation vector

The metric constraints are as followings:

We impose

where is a matrix, and are elements of the estimated motion matrix The matrix is solvable by the same way with the orthographic case.

### Projective case [3]

See the report Factorization.pdf

## Source Codes

### Orthographic and Paraperspective

option 'orthographic' and 'paraperspective'

### Projective

For projective case, a matlab codes set is provided by Bill Triggs - Software. Furthermore, you may find normalise2dpts.m which is provided by Peter Kovesi is useful.

## Data Preparation - KLT Feature Tracker

I used klt library [1] version 1.3.2. Extraction of Feature Tracking Points.

### Dataset

Download [2].

The klt library supports pgm files, thus convert png files into pgm. You can do it as

mogrify -format pgm *.png

if you have Linux-like environments (I worked with cygwin on windows).

### Source codes

- cvpr:project/Factorization/others/klt/kltrun.c Output file is formatted so that matlab can reasily read by 'load'.
- cvpr:project/Factorization/cvuKltRead.m
- cvpr:project/Factorization/cvuKltPlot.m

Compile kltrun.c as Makefile does.

make # compile klt library if not yet gcc -O3 -DNDEBUG -o kltrun kltrun.c -L. -lklt -L/usr/local/lib -L/usr/lib -lm

How to use

Usage: ./kltrun <basename_of_pgm_files> [-fmt <pgm_sequence_format = %d>] [-ef <index_of_end_frame = 0>] [-np <#_of_tracking_points = 430>] [-sf <index_of_start_frame = 0>] Ex) ./kltrun ../hotel/hotel.seq -fmt %d -ef 100 -np 430 -sf 0 Ex) ./kltrun ../castle/castle. -fmt %03d -ef 27 -np 110 -sf 0 Ex) ./kltrun ../medusa/medusa -fmt %03d -sf 110 -ef 180 -np 830

Example of cvuKltPlot.m

## Experiments and Results

### Orthographic case

>> cvFactorizationDemo(1)

### Paraperspective case

Unfortunately, the paraperspective project method failed for this particular image sequence. The G = Q*Qt matrix in equation (3) (see the Factorization method section) turned out to be non-positive definite and thus we could not simply calculate the Jacobi Transformation and take the square root. One can solve the problem by means of an iterative method called Newton's method [4]. For time constrained reasons, we did not explore this option in the project. Moreover, we also encountered that the image sequence does not contain enough translation along the optical axis or it contains too much measurement noise.

>> cvFactorizationDemo(3)

See report Factorization.pdf

### Projective case

>> cvProjectiveFactorizationDemo

See report Factorization.pdf

## References

- [1] C. Tomasi and T. Kanade, "Shape and motion from image streams -- a factorization method," International Journal of Computer Vision, 9(2):137--154, 1992. http://www.pnas.org/cgi/reprint/90/21/9795.pdf http://www.hpl.hp.com/personal/Donald_Tanguay/cvrg/tomasiTr92Text.pdf
- [2] C. J. Poelman and T. Kanade, "A paraperspective factorization method for shape and motion recovery," Pattern Analysis and Machine Intelligence, IEEE Transactions on , vol.19, no.3, pp.206-218, Mar 1997
- [3] Bill Triggs, Factorization methods for projective structure and motion. In Proceeding of 1996 Computer Society Conference on Computer Vision and Pattern Recognition, pages 845--51, San Francisco, CA, USA, 1996. IEEE Comput. Soc. Press. http://citeseer.ist.psu.edu/article/triggs96factorization.html
- [4] T. Morita and T. Kanade, "A Sequential Factorization Method for Recovering Shape and Motion from Image Streams, " Pattern Analysis and Machine Intelligence, IEEE Transactions on, vol. 19, no.8, pp.858-867, Aug 1997
- [5] Nicholas J. Higham (1988) Computing a nearest symmetric positive semidefinite matrix. Linear Algebra and its Applications, 103. pp. 103-118. http://www.maths.man.ac.uk/~nareports/narep126.pdf
- [6] CSE 252B: Computer Vision II Lecture 16 Structure from Motion from Tracked Points, UCSD, pp.7. http://www-cse.ucsd.edu/classes/sp04/cse252b/notes/lec16/lec16.pdf

- KLT: An Implementation of the Kanade-Lucas-Tomasi Feature Tracker http://www.ces.clemson.edu/~stb/klt/
- CMU VASC Image Database: hotel http://vasc.ri.cmu.edu//idb/html/motion/hotel/index.html