CS 143 Project 5

Tracking and Structure From Motion

Will Allen (weallen)

Methods


For this project, we implemented a Lucas-Kanade feature tracker, which computes the optical flow over a series of images, and then used the tracked features from a particular series of images to reconstruct the structure of an item in the images from its motion over time. The structure from motion was based on "Shape and Motion from Image Streams under Orthography: a Factorization Method" (Tomasi and Kanade 1992.)

Algorithm

Keypoint Selection

We used a Harris corner detector to find features. We took the top 500 "strongest" features.

Lucas-Kanade Tracker

Our Lucas-Kanade tracker computes optical flow between successive video frames by computing the x, y, and temporal gradients of each images, then finding the per pixel optical flow values u,v by solving the final equation in:

which involves inverting the 2x2 matrix on the left and multiplying it by the matrix on the right, and the sums are over a 15x15 window centered around the pixel under consideration. We then find the u,v corresponding to the current location of each feature, add the u,v to update the feature's position, and interpolate that updated position to an integral location in the image. We discard any features that go outside of the image frame.

Structure From Motion

We recovered the structure from motion by first centering the each feature's coordinates, constructing a measurement matrix D of the x and y coordinates for each feature over time stacked into one large matrix, then computed the SVD of D to get the matrices U, W, and V, where D = U W V'. We took the first 3 columns of U, the first 3 columns of V, and the upper left 3x3 block of W, and created motion and shape matrices. We then eliminated affine ambiguity in these matrices by solving the linear algebraic equations from Section 2.3 of A Sequential Factorization Method for Recovering Shape and Motion from Image Streams, Morita and Kanade, 1997. We used a cholesky decomposition to factor the G matrix into A^T A = G (described in Section 2.3 of the paper). The

Results

The Lucas-Kanade algorithm was quite good at tracking features over time. The structure from motion algorithm, however, did not really recover a box shape; instead, it gave some sort of lumpy plane shaped object. This lumpy object did have sharp corners reminiscent of the box in the image, though.
Features to be tracked:
Movement of 20 random points over series of images:
Features that moved off camera:
3 views of reconstructed structure:
Predicted camera motion: X-axis Predicted camera motion: Y-axis Predicted camera motion: Z-axis