Lab 7 (Interest Points and Optical Flow)

Computer Vision I (CSCI 3240U)

Faisal Z. Qureshi

Faculty of Science, Ontario Tech University

http://vclab.science.ontariotechu.ca

Check Canvas for Due Date


Introduction

The goal of this lab is to find the points in an image that are worth paying attention to, and then to follow them through time.

The unifying object is the structure tensor \(M\). You will use it in Part 1 to decide whether a point is a corner, and then discover in Part 2 that the same matrix, with the same eigenvalues, decides whether optical flow can be estimated there at all. Corner detection and the aperture problem are two readings of one statement, which is why Shi and Tomasi called their paper Good Features to Track.

Parts 1 and 2 are required. Part 3 is optional and is not marked. The lab is sized for one two-hour session; budget up to two more hours at home if you need them.

All the code for this lab goes in one notebook, corner-detection-starter.ipynb [html]. It has a section for each task below, with the plumbing (loading images and video frames, drawing, template matching) already written.

Reading

Computer Vision: Algorithms and Applications (2nd ed.), Szeliski, Sec. 7.1.1–7.1.3, 7.1.5, 9.3.

Feature detectors, descriptors, matching and tracking; optical flow. The Week 8 slides cover everything this lab needs.

Data

Part 1: Corner detection

Recall that both detectors are built from the structure tensor \[ M = \sum_{(x,y) \in W} w(x,y) \left[ \begin{array}{cc} I_x^2 & I_x I_y \\ I_x I_y & I_y^2 \end{array} \right], \] and differ only in how they turn its eigenvalues \(\lambda_1 \ge \lambda_2\) into a corner score: Harris uses \(R = \det(M) - k\,\mathrm{tr}(M)^2\), Shi-Tomasi uses \(R = \lambda_2\).

Task 1. Find interest points with the Harris corner detector (cv2.cornerHarris). Threshold the response and apply non-maximum suppression, so that each corner gives one detection rather than a blob. The starter explains how to do this with cv2.dilate.

Task 2. Find interest points with the Shi-Tomasi detector (cv2.goodFeaturesToTrack), with the same point budget as Task 1 and minDistance set to the size of your Harris suppression window. Draw both sets on one image and say, in a few sentences, where they agree and where they differ.

Part 2: Optical flow and tracking

You have just used \(M\) to answer “is this a corner?”. Now you will use it to answer a different question: “can I tell how this point moved?”

The camera in traffic-short.mp4 is static, so anything that moves in the image moved in the world. The starter loads frames 2999 and 3000 as greyscale images I0 and I1.

Task 3: derive it. Assume brightness constancy, \(I(x,y,t) = I(x+u,\; y+v,\; t+1)\). Take the first-order Taylor expansion and show that each pixel gives \[ I_x u + I_y v + I_t = 0 , \] where \(I_t\) is the temporal derivative. One equation, two unknowns: say what this means for a single pixel (the aperture problem). Then assume the flow is constant over a window \(W\), and show that the least-squares solution satisfies \[ M \mathbf{u} = -\mathbf{b}, \qquad \mathbf{u} = \left[\begin{array}{c} u \\ v \end{array}\right], \qquad \mathbf{b} = \left[\begin{array}{c} \sum_W I_x I_t \\ \sum_W I_y I_t \end{array}\right], \] where \(M\) is the structure tensor from Part 1 (with \(w = 1\)). Write the derivation in a markdown cell.

Task 4: Lucas-Kanade at one point. Write lk_point(I0, I1, x, y, win=21), which returns the flow \((u, v)\) and the matrix \(M\) at the pixel \((x, y)\). Use \(I_t = I_1 - I_0\), and gradients in intensity per pixel: np.gradient, or cv2.Sobel with ksize=3 divided by 8. Solve with np.linalg.lstsq, which copes when \(M\) is singular. Test it on the distant vehicle at \((x, y) = (660, 385)\), and compare your answer with cv2.calcOpticalFlowPyrLK. This vehicle moves about half a pixel, and the two should agree to within about 0.1 pixel. If yours is several times smaller than OpenCV’s, check the scale of your gradients.

Task 5: the aperture problem, measured. Use your \(M\) at three patches in frame 2999: a corner on the bridge, \((1336, 358)\); an edge on the median barrier, \((462, 961)\); and the sky, \((598, 66)\). Report \(\lambda_1\), \(\lambda_2\), the Shi-Tomasi score and the Harris score (\(k = 0.04\)) for each, in a table. Then answer:

Task 6: track. Detect 400 Shi-Tomasi corners in frame 2999 and follow them into frame 3000 with cv2.calcOpticalFlowPyrLK (21 x 21 window, maxLevel=3). Draw the flow vectors. Most corners sit on the road, the barriers and the bridge, which do not move. Use a threshold of 1 pixel on the flow magnitude to separate the moving vehicles from the static background, show the result, and report the fraction of corners that move. The threshold does not catch every vehicle: say which ones it misses, and why. (Task 4 is a hint.)

Task 7: large motion. The truck close to the camera moves a long way between the two frames. At \((x, y) = (1431, 716)\), on the side of the truck:

  1. measure the true displacement with the starter’s template_shift, which uses template matching over a generous search region;
  2. run cv2.calcOpticalFlowPyrLK with maxLevel=0, which is Lucas-Kanade at a single scale;
  3. run it again with maxLevel=3, which works coarse to fine on a Gaussian pyramid.

Report the three displacements. Explain, in one paragraph, why single-scale Lucas-Kanade underestimates large motion and why the pyramid fixes it, in terms of how far the truck moves in pixels at each level of the pyramid.

Part 3 (optional)

None of these is marked.

Deliverables

Your notebook must contain the following.

Submission

Via Canvas. Please submit a single executed Jupyter notebook, one that has been run top to bottom, so that every figure and number listed above is visible in the submitted file. Code that has not been executed cannot be marked.

Parting thoughts