## Announce

Puki contents have been moved into SONOTS Plugin (20070703)

## 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

## 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,

1. Eigen decompose
2. Form a matrix by setting any negative values to
3. 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

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

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)
 1st frame 50th 100th

### 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