Solutions for Lecture 5 Problems

Problem 1

1. In terms of uniqueness and invariance, discuss why single pixels, described using their RGB values, do not make good features for image matching.

Solution

They are not unique because many different points in a scene may share an RGB value

They are not invariant because change from one image to another may change the RGB value of the same point.

Problem 2

2. For each of the following (linearized) error function shapes, describe the image patch that gave rise to it:
   1. Flat in all directions
   2. Steep in one direction, flat in the orthogonal direction
   3. Steep in all directions

Solution

1. The image patch is flat (i.e., one color)
2. The image patch has an edge but not a corner
3. The image patch has a corner

Problem 3

Let’s investigate the behavior of the Harris corner detector on the three image patches shown below. $$\begin{bmatrix} 2 & 2 & 2\\ 2 & 2 & 2\\ 0 & 0 & 0 \end{bmatrix} \begin{bmatrix} 0 & 2 & 2\\ 0 & 2 & 2\\ 0 & 0 & 0 \end{bmatrix} \begin{bmatrix} 2 & 2 & 2\\ 0 & 2 & 2\\ 0 & 0 & 2 \end{bmatrix}$$ Compute the structure tensor for each of the above patches. I have it on good authority that these images are noise-free, so we can safely skip the Sobel filter and compute gradients using 3x1 and 1x3 centered finite difference filters and repeat padding.

Solution

1. Gradients: $$X: \begin{bmatrix} 0 & 0 & 0\\ 0 & 0 & 0\\ 0 & 0 & 0 \end{bmatrix} \begin{bmatrix} 2 & 2 & 0\\ 2 & 2 & 0\\ 0 & 0 & 0 \end{bmatrix} \begin{bmatrix} 0 & 0 & 0\\ 2 & 2 & 0\\ 0 & 2 & 2 \end{bmatrix} \\ Y: \begin{bmatrix} 0 & 0 & 0\\ 2 & 2 & 2\\ 2 & 2 & 2 \end{bmatrix} \begin{bmatrix} 0 & 0 & 0\\ 0 & 2 & 2\\ 0 & 2 & 2 \end{bmatrix} \begin{bmatrix} 2 & 0 & 0\\ 2 & 2 & 0\\ 0 & 2 & 0 \end{bmatrix}$$ Structure tensor: $$\begin{bmatrix} 0 & 0 \\ 0 & 24 \end{bmatrix} \begin{bmatrix} 16 & 4 \\ 4 & 16 \end{bmatrix} \begin{bmatrix} 16 & 12 \\ 12 & 16 \end{bmatrix}$$

Problem 4

4. Using software of your choice (e.g., np.linalg.eigvals, or use the formula described here), compute the smallest eigenvalue of each of the structure tensors you computed in the prior problem.

Solution

0, 12, 4

Problem 5

5. Write psudeocode (or working Python code if you like, based on our lecture repository codebase) for Harris scores (i.e., smallest eigenvalue of the structure tensor for each pixel). You should make (exact or pseudocody) use of filtering and other routines that already exist in the lecture codebase.

Solution

def harris_score(img):
  """ Returns the smaller eigenvalue of the structure tensor for each pixel in img.
  Pre: img is grayscale, float, [0,1]. """
    dx = convolve(img, sobel_x)
    dy = convolve(img, sobel_y)
    A = separable_filter(dx * dx, gauss1d5)
    B = separable_filter(dx * dy, gauss1d5)
    C = separable_filter(dy * dy, gauss1d5)

    det = A*C - B*B
    tr = A+C
    
    m = tr / 2
    p = det
    sqrtm2mp = np.sqrt(m**2 - p)
    eig1 = m - sqrtm2mp
    eig2 = m + sqrtm2mp
    return np.minimum(eig1, eig2)

Problem 6

6. Consider the following harris corner detection result, computed using the code we saw in class:

Some of these points would be better characterized as edge patches, rather than corner patches. Why did our code pick them up, and what would we need to change in order to get only things that really do look like corners in the image?

Solution

Our convolution does zero padding, so there’s an implicit edge around the border where the intensity drops to zero. So horizontal edges coming out of that look like corners; also the corners of the image itself look like corners. We’d need to do repeat or reflect padding to prevent this.

Poor threshold choice is one reason, but the points around the edges will get picked up even with a high threshold.