Homework #2 Solution

Description

1    A  feature  tracker (50pt)

 

For this problem, you will track features from the image sequence hotel.seq0.png … hotel.seq50.png. Since this is a two part problem,  we have included  precomputed intermediate results in the supple- mental material in case you’re unable  to complete any portion.

Please also  include pseudocode in your report. Furthermore, do not use existing keypoint detectors, trackers, or structure from motion  code, such as found in OpenCV.

 

1.1     Keypoint Selection (15pt)

 

For  the first  frame,  use the second  moment  matrix  to locate  strong  corners  to use as keypoints. These points will be tracked throughout the sequence.

You can either use the Harris  criteria (1), or  the Shi-Tomasi/Kanade-Tomasi criteria (2).  Here M is the second moment matrix,   1 ,   2  are the eigenvalues of M , and ⌧   is the threshold for selecting keypoints:

 

det(M )     ↵ · trace(M )2	⌧	(1)
min(  1 ,   2 )	⌧	(2)

If using the Harris criteria, it is good to choose ↵ 2 [0.01, 0.06]. Choose ⌧   so that edges and noisy patches  are ignored.  Do local non-maxima suppression  over a 5×5 window centered at  each point. This should give several hundred  good points to track.

Required output:

 

1. Display the first frame of the sequence overlaid with the detected keypoints. Ensure  that they are clearly visible (try plot(…, ‘g.’, ‘linewidth’,3)).

 

Suggested  Structure:

 

Write this as a function such as [keyXs, keyYs] = getKeypoints(im, tau); Be sure to smooth the gradients when constructing the second moment matrix.

 

Useful functions:

imfilter.m

References:

 

1. Harris and M. Stephens. A Combined Corner  and Edge Detector. 1988

 

1. Shi and C. Tomasi. Good Features to Track. 1993

 

1.2     Tracking (35pt)

 

Apply  the Kanade-Lucas-Tomasi tracking procedure  to track the keypoints found in part 1.1.  For each keypoint k, compute the expected translation from (x, y) ! (x0 , y0 ):

 

I (x0 , y0 ,t + 1) = I (x, y, t)

 

(3) This  can  be  done  by  iteratively  applying  (4):   Given  the ith   estimate  of (xi , yi ),  we want  to

i   i

 

update our estimate (x0

 

i+1

 

, y0

) = (x0 , y0 )+ (u, v).  Here, W is a 15×15 pixel window surrounding

 

the keypoint, Ix , Iy are the x, y gradients of image I (x, y, t), computed at each element of W at time

1. It = I (x0 , y0 ,t + 1) I (x, y, t) is the “temporal” gradient.

 

 

(x0 , y0 ) = (x, y)

0     0

It = I (x0 , y0 ,t + 1)  – I (x, y, t)

i   i

 

 

EW  Ix Ix        PW  Ix Iy        v

EW  Ix It

 

EW  Ix Iy        PW  Iy Iy        v

W  Iy It

(4)

 

(Xi +1, yi+ 1) = (xi, yi) + (u, v)

 

This  should  be applied  iteratively,  that is, begin  with  (x0 , y0 )T   = (x, y)T , which  is needed  to

0     0

compute  It .   Use this  It  to estimate  (u, v)T ,  which  can  in  turn be  used  to compute  (x0 , y0 )  =

1     1

(x0 , y0 )+ (u, v), and  so on.  Note that (x0 , y0 )T   (and  (x, y)T ) need not  be integer, so you will need

0     0

to interpolate I (x0 , y0 ,t + 1) (Ix , Iy , …, etc.)  at these non-integer values.

Some keypoints will move out of the image frame over the course of the sequence.  Discard  any

track if the predicted translation falls outside the image frame.

Required Output:

 

1. For 20 random  keypoints, draw  the 2D path  over the sequence  of frames.   That is, plot  the progression  of image coordinates  for each of the 20 keypoints.  Plot  each of the paths  on the same figure, overlaid on the first frame of the sequence.

 

2. On top of the first frame, plot the points which have moved out of frame at some point along the sequence.

 

Useful functions:

 

interp2 – For computing Ix , Iy and I (x0 , y0 ,t + 1) when x, y, u, v are not integers.

 

meshgrid – For computing the indices for interp2

 

Suggested  Structure:

 

[newXs newYs] = predictTranslationAll(startXs, startYs, im0, im1); – Compute new X,Y locations for all starting locations.  Precompute gradients Ix,Iy here, then compute translation for each keypoint independently:

 

[newX newY] = predictTranslation(startX, startY, Ix, Iy, im0, im1); – For a single X,Y location,  use the gradients Ix, Iy, and images im0, im1 to compute the new location.  Here it may be necessary to interpolate Ix,Iy,im0,im1 if the corresponding  locations are not integer.

 

References:

 

Carlo Tomasi  and Takeo Kanade.  Detection  and Tracking  of Point  Features. 1992

 

2 Shape alignment  (30pt)

 

Write a function that aligns two sets of points:

 

T = align shape(im1, im2)

 

where T is a transformation that maps  non-zero  points in im1  to non-zero  points in im2.  You may choose the alignment algorithm and the type of (global)  transformation (e.g., rigid Euclidean, a   ne, perspective).

Test your function by mapping:  object2 to object2t, object1, object3.  For example,

 

 

T 2t = align shape(imread(‘object2.png’)>0, imread(‘object2t.png’)>0);

 

should  align  the points in ‘object2’ to the points in ‘object2t’, display  all three sets of points (original  and  aligned)  and  compute the alignment error.   Weve included  functions evalAlignment and displayAlignment to help with evaluation and display.

Required output:

 

1. A brief explanation of your algorithm, initialization, and model of the transformation

 

2. For each result:

The alignment display; The final error;

The runtime (e.g., use tic, toc).

 

Grading:

 

Your algorithm can align object2 to object2t.  (10pt)

 

Your algorithm can align object2 to object1 and object3.  (10pt) Your writeup.  (10pt)

The speed of your algorithm.  (5pt extra credit)

 

 

Figure 1 Object instance detection from keypoint matching

 

 

 

3    Ob ject instance  recognition  (20pt)

 

For this problem,  you will explore Lowe-style object instance recognition problem.

 

3.1     Keypoint matching (5 pt)

 

Given  a keypoint  descriptor  g from one image  and  a set  of keypoint  descriptors  f1 .. . fn from a second image,  write  the algorithm  and  equations  to determine  which keypoint  in f1 .. . fn (if any) matches  g.

 

3.2     Keypoint matching (15 pt)

 

Suppose  that you have  matched  a keypoint  in the object  region  to a keypoint  in a second  image (see Figure 1 above).  Given the object bounding  box center (x, y), width, and height (x1 , y1 , w1 , h1 ) and  the position,  scale, and  orientation  of each  keypoint  (u1 , v1 , s1 , ✓1 ; u2 , v2 , s2 , ✓2 ), show how to compute the predicted center position, width, height, and  relative  orientation of the object in the second image.