$30.00

Category: 16720A

Description

5/5 - (7 votes)

1 Lucas-Kanade Tracking

In this section you will be implementing a simple Lucas & Kanade tracker with one single

template. In the scenario of two-dimensional tracking with a pure translation warp function,

W(x; p) = x + p . (1)

The problem can be described as follows: starting with a rectangular neighborhood of

pixels N ∈ {xd}

D

d=1 on frame It, the Lucas-Kanade tracker aims to move it by an offset

1

p = [px, py]

T

to obtain another rectangle on frame It+1, so that the pixel squared difference

in the two rectangles is minimized:

p

∗ = arg minp =

X

x∈N

||It+1(x + p) − It(x)||2

2

(2)

=

It+1(x1 + p)

.

.

.

It+1(xD + p)

−

It(x1)

.

.

.

It(xD)

2

2

(3)

Q1.1 (5 points) (Talha) Starting with an initial guess of p (for instance, p = [0, 0]T

), we

can compute the optimal p

∗

iteratively. In each iteration, the objective function is locally

linearized by first-order Taylor expansion,

It+1(x

0 + ∆p) ≈ It+1(x

0

) + ∂It+1(x

0

)

∂x0T

∂W(x; p)

∂pT ∆p (4)

where ∆p = [∆px, ∆py]

T

, is the template offset. Further, x

0 = W(x; p) = x + p and ∂I(x

0

)

∂x0T

is a vector of the x− and y− image gradients at pixel coordinate x

0

. In a similar manner to

Equation 3 one can incorporate these linearized approximations into a vectorized form such

that,

arg min

∆p

||A∆p − b||2

2

(5)

such that p ← p + ∆p at each iteration.

• What is ∂W(x;p)

∂pT ?

• What is A and b?

• What conditions must AT A meet so that a unique solution to ∆p can be found?

Q1.2 (15 points) (Rishi) Implement a function with the following signature

LucasKanade(It, It1, rect, p0 = np.zeros(2))

that computes the optimal local motion from frame It to frame It+1 that minimizes Equation 3. Here It is the image frame It, It1 is the image frame It+1, rect is the 4-by-1

vector that represents a rectangle describing all the pixel coordinates within N within the

image frame It, and p0 is the initial parameter guess (δx, δy). The four components of

the rectangle are [x1, y1, x2, y2]

T

, where [x1, y1]

T

is the top-left corner and [x2, y2]

T

is the

bottom-right corner. The rectangle is inclusive, i.e., it includes all the four corners. To

deal with fractional movement of the template, you will need to interpolate the image using

the Scipy module ndimage.shift or something similar. You will also need to iterate the

estimation until the change in ||∆p||2

2

is below a threshold. In order to perform interpolation you might find RectBivariateSpline from the scipy.interpolate package. Read

the documentation of defining the spline ( RectBivariateSpline) as well as evaluating the

spline using RectBivariateSpline.ev carefully.

Q1.3 (10 points) (Rishi) Write a script testCarSequence.py that loads the video frames

from carseq.npy, and runs the Lucas-Kanade tracker that you have implemented in the

2

previous task to track the car. carseq.npy can be located in the data directory and it

contains one single three-dimensional matrix: the first two dimensions correspond to the

height and width of the frames respectively, and the third dimension contain the indices of

the frames (that is, the first frame can be visualized with imshow(frames[:, :, 0])). The

rectangle in the first frame is [x1, y1, x2, y2]

T = [59, 116, 145, 151]T

. Report your tracking

performance (image + bounding rectangle) at frames 1, 100, 200, 300 and 400 in a format

similar to Figure 1. Also, create a file called carseqrects.npy, which contains one single

n × 4 matrix, where each row stores the rect that you have obtained for each frame, and n

is the total number of frames.

Figure 1: Lucas-Kanade Tracking with One Single Template

Q1.4 (20 points) (Talha) As you might have noticed, the image content we are tracking

in the first frame differs from the one in the last frame. This is understandable since we are

updating the template after processing each frame and the error can be accumulating. This

problem is known as template drifting. There are several ways to mitigate this problem.

Iain Matthews et al. (2003, https://www.ri.cmu.edu/publication_view.html?pub_id=

4433) suggested one possible approach. Write a script with a similar functionality to Q1.3

named testCarSequenceWithTemplateCorrection.py, but with a template correction routine incorporated. Save the resulting rects as carseqrects-wcrt.npy, and also report the

performance at those frames. An example is given in Figure 2.

Figure 2: Lucas-Kanade Tracking with Template Correction

Here the blue rectangles are created with the baseline tracker in Q1.3, the red ones with

the tracker in Q1.4. The tracking performance has been improved non-trivially. Note that

you do not necessarily have to draw two rectangles in each frame, but make sure that the

performance improvement can be easily visually inspected.

2 Affine Motion Subtraction

In this section, you will implement a tracker for estimating dominant affine motion in a

sequence of images and subsequently identify pixels corresponding to moving objects in the

scene. You will be using the images in the file aerialseq.npy, which consists of aerial views

of moving vehicles from a non-stationary camera.

3

2.1 Dominant Motion Estimation

In the first section of this homework we assumed the the motion is limited to pure translation.

In this section you shall implement a tracker for affine motion using a planar affine warp

function. To estimate dominant motion, the entire image It will serve as the template to

be tracked in image It+1, that is, It+1 is assumed to be approximately an affine warped

version of It. This approach is reasonable under the assumption that a majority of the pixels

correspond to the stationary objects in the scene whose depth variation is small relative to

their distance from the camera.

Using a planar affine warp function you can recover the vector ∆p = [p1, . . . , p6]

T

,

x

0 = W(x; p) =

1 + p1 p2

p4 1 + p5

x

y

+

p3

p6

. (6)

One can represent this affine warp in homogeneous coordinates as,

x˜

0 = Mx˜ (7)

where,

M =

1 + p1 p2 p3

p4 1 + p5 p6

0 0 1

. (8)

Here M represents W(x; p) in homogeneous coordinates as described in [1]. Also note

that M will differ between successive image pairs. Starting with an initial guess of p = 0

(i.e. M = I) you will need to solve a sequence of least-squares problem to determine ∆p

such that p → p + ∆p at each iteration. Note that unlike previous examples where the

template to be tracked is usually small in comparison with the size of the image, image

It will almost always not be contained fully in the warped version It+1. Hence, one must

only consider pixels lying in the region common to It and the warped version of It+1 when

forming the linear system at each iteration.

Q2.1 (15 points) (Harsh) Write a function with the following signature

LucasKanadeAffine(It, It1)

which returns the affine transformation matrix M, and It and It1 are It and It+1 respectively.

LucasKanadeAffine should be relatively similar to LucasKanade from the first section (you

will probably also find scipy.ndimage.affine transform helpful).

2.2 Moving Object Detection

Once you are able to compute the transformation matrix M relating an image pair It and

It+1, a naive way for determining pixels lying on moving objects is as follows: warp the

image It using M so that it is registered to It+1 and subtract it from It+1; the locations

where the absolute difference exceeds a threshold can then be declared as corresponding

to locations of moving objects. To obtain better results, you can check out the following

scipy.morphology functions: binary erosion, and binary dilation.

Q2.2 (10 points) (Harsh) Using the function you have developed for dominant motion

estimation, write a function with the following signature

4

SubtractDominantMotion(image1, image2)

where image1 and image2 form the input image pair, and the return value mask is a binary image of the same size that dictates which pixels are considered to be corresponding

to moving objects. You should invoke LucasKanadeAffine in this function to derive the

transformation matrix M, and produce the aforementioned binary mask accordingly.

Q2.3 (10 points) (Shumian) Write a script testAerialSequence.py that loads the

image sequence from aerialseq.npy and run the motion detection routine you have developed to detect the moving objects. Report the performance at frames 30, 60, 90 and 120

with the corresponding binary masks superimposed, as exemplified in Figure 3. Feel free

to visualize the motion detection performance in a way that you would prefer, but please

make sure it can be visually inspected without undue effort.

Figure 3: Lucas-Kanade Tracking with Motion Detection

3 Efficient Tracking

3.1 Inverse Composition

The inverse compositional extension of the Lucas-Kanade algorithm (see [1]) has been used

in literature to great effect for the task of efficient tracking. When utilized within tracking

it attempts to linearize the current frame as,

It(W(x; 0 + ∆p) ≈ It(x) + ∂It(x)

∂xT

∂W(x; 0)

∂pT ∆p . (9)

In a similar manner to the conventional Lucas-Kanade algorithm one can incorporate these

linearized approximations into a vectorized form such that,

arg min

∆p

||A0∆p − b

0

||2

2

(10)

for the specific case of an affine warp where p ← M and ∆p ← ∆M this results in

the update M = M(∆M)

−1

. Just to clarify, the notation M(∆M)

−1

corresponds to

W(W(x; ∆p)

−1

; p) in Section 2.2 from [2].

Q3.1 (15 points) (Shumian) Reimplement the function LucasKanadeAffine(It,It1)

as

InverseCompositionAffine(It,It1) using the inverse compositional method. In your

own words please describe why the inverse compositional approach is more computationally

efficient than the classical approach?

5

4 Deliverables

The assignment (code and writeup) should be submitted to canvas. The writeup should also

be submitted to Gradescope named hw6.pdf. The code should be submitted

as a zip named .zip. The zip when uncompressed should produce the following

files.

• LucasKanade.py

• LucasKanadeAffine.py

• SubtractDominantMotion.py

• InverseCompositionAffine.py

• testCarSequence.py

• testCarSequenceWithTemplateCorrection.py

• testAerialSequence.py

• carseqrects.npy

• carseqrects-wcrt.npy

Do not include the data directory in your submission.

6

WhatsApp us