Description

Harris Corner Detector and Optical Flow
1 Harris Corner Detector
In this section, a derivation of the Harris Corner Detector is presented:
Given a shift (∆x,∆y) at a point (x,y), the auto-correlation function is defined as,
(1)
where W(x,y) is a window centered at point (x,y) and w(u,v) is a Gaussian function. For simplicity, from now on, ” will be referred to as ”
(u,v)∈W(x,y) W
Approximating the shifted function by the first-order Taylor expansion we get:
I(u + ∆x,v + ∆y) ≈ I(u,v) + Ix(u,v)∆x + Iy(u,v)∆y (2)
(3)
where Ix and Iy are partial derivatives of I(x,y). Therefore, the auto-correlation function can be written as:

where Q(x,y) is given by: (6)
I (x,y)2 I (x,y)I (x,y)
Q(x,y) = !# x x y 2 x y y $
W I (x,y)I (x,y) I (x,y)2 = ⎡⎣””Wx y “W ” y ⎦⎤
Ix(x,y) Ix(x,y)Iy(x,y)
I (x,y)I (x,y) I (x,y)2
W W = # $
A BB C (7)
(8)
(9)
c(x,y) = !(I(u,v) − I(u + ∆x,v + ∆y))2 (4)
W
≈([Ix(u,v) Iy(u,v)]#∆x$)2 (5)
∆y W
The ‘cornerness’ H(x,y) is defined by the two eigenvalues of Q(x,y), λ1 and
λ2:
H =
=
= λ1λ2 − 0.04(λ1 + λ2)2 det(Q) − 0.04(trace(Q))2 (AC − B2) − 0.04(A + C)2 (10)
(11)
(12)
In this section, you are going to implement the last equation to measure H and use it to get the corners in an image. For that purpose, you need to compute the elements of Q, i.e. A,B and C. To do that, you need to know that Ix is the smoothed derivative of the image, it can be obtained by convolving the first order Gaussian derivative, Gd , with the image I along the x-direction. Later, A = “Ix(x,y)2, can be obtained by squaring Ix then convolving it with
W
a Gaussian, G. Similarly, B and C can be obtained. For example, to get C, you need to convolve the image with Gd along the y-direction (to obtain Iy), raise it to the square, then convolve it with G. At this point, you can compute H. The corners points are the local maxima of H. Therefore, in your function you should check for every point in H, if it is greater than all its neighbours (in an n × n window centered around this point) and if it is greater than the user-defined threshold, then it is a corner point. Your function should return the H matrix, the rows of the detected corner points r, and the columns of those points c – so the first corner is given by (r(1),c(1)). Your function should also plot three figures, the computed image derivatives Ix and Iy, and the original image with the corner points plotted on it.
2 Introduction: Optical Flow
I(x,y,t) = I(x + δx,y + δy,t + δt). (13)
Assuming the movement to be small, the image constraint at I(x, y, t) with Taylor series can be developed to get:

As we assume the image values remain constant over time, we will get:
(15)
or
IxVx + IyVy = −It, (16)
where Vx, Vy are the x and y components of the velocity or optical flow of I(x,y,t), and Ix, Iy and It are the derivatives of the image at (x,y,t) in the corresponding directions. This is the main equation of the optical flow.
3 Lucas-Kanade Algorithm
We will be implementing the Lucas-Kanade method for Optical Flow estimation. This method assumes that the optical flow is essentially constant in a local neighborhood of the pixel under consideration. Therefore, the main equation of the optical flow can be assumed to hold for all pixels within a window centered at the pixel under consideration. Lets consider pixel p then for all pixels around p the local image flow vector (Vx,Vy) must satisfy
Ix(q1)Vx + Iy(q1)Vy = −It(q1)
Ix(q2)Vx + Iy(q2)Vy = −It(q2) … (17)
Ix(qn)Vx + Iy(qn)Vy = −It(qn),
where q1, q2, …qn are the pixels inside the window around p, and Ix(qi), Iy(qi), It(qi) are the partial derivatives of the image I with respect to position x, y and time t, evaluated at the point qi and at the current time.
These equations can be written in matrix form Av = b, where
. (18)
This system has more equations than unknowns and thus it is usually overdetermined. The Lucas-Kanade method obtains a compromise solution by the weighted least squares principle. Namely, it solves the 2 × 2 system as
ATAv = ATb (19)
or
v = (ATA)−1ATb. (20)
For this assignment, you will be given two pairs of images: synth1.pgm, synth2.pgm; and sphere1.ppm, sphere2.ppm. You should estimate the optical flow between these two pairs, it means you will get optical flow for sphere images, and for synth images separately.
You can use regions that are 15 × 15 pixels, and non-overlapping. That is, if input images are 256 × 256, you should have an array of 17 × 17 optical flow vectors at the end of your procedure. As we consider 15 × 15 regions, your matrix A will have the following size 225 × 2, and the vector b will be 225 × 1. The algorithm can be summarized as follows:
1. Divide input images on non-overlapping regions, each region being 15×15 pixels.
2. For each region compute A, AT and b; then estimate optical flow as given in equation (20).
3. When you have estimation for optical flow (Vx,Vy) of each region, you should display the results. There is a matlab function quiver which plots a set of two-dimensional vectors as arrows on the screen. Try to figure out how to use this to plot your optical flow results.
4 Tracking
In this part you will implement a simple tracking algorithm as follows:
1. Locate feature points on the first frame by using Harris Corner Detector which you implemented in previous section. Then, track these points with Lucas-Kanade method for optical flow estimation.
2. Prepare a video for each sample image sequences. These videos should visualize the initial feature points and the flow.
Test your implementation and prepare visualization videos for pingpong and person toy samples.
5 Deliverables
1. [6 pts] For section 1:
• [3 pts] A demo function should return the H matrix, the rows of the detected corner points r, and the columns of those points c – so the first corner is given by (r(1),c(1)).
• [3 pts] For visualization, the function should also plot three figures, the computed image derivatives Ix and Iy, and the original image with the corner points plotted on it. (Note: please show your results on example images “person toy/00000001.jpg” and “pingpong/0000.jpeg” in your report separately.)
2. [6 pts] For section 3:
• [3 pts] A demo function which runs the whole routine with all other functions you have implemented.
• [3 pts] Visualizations of two optical flows for sphere and synth images should be submitted.
3. [8 pts] For section 4:
• [3 pts] Demo functions which run the trackers (Harris Corner Detector and the combination with Lucas-Kanade algorithm) with all other supporting functions you have implemented.
• [5 pts] Visualization videos of two implemented trackers for pingpong and person toy should be submitted.