Computer vision: Harris corner response

Corners are the keypoints that panoramas and 3-D reconstruction are built on. Compute the Harris response by hand.

What to build

A program that computes the Harris corner response at given pixels and classifies each one.

Requirements

  • Use central-difference gradients and a 3 × 3 window centred on the query pixel, with k = 0.05. Query pixels are at least 2 pixels from every border.
  • Classify: corner if R > T, edge if R < −T, otherwise flat.
  • For each query print row R, column C: R = value, class, with the value to two decimal places.

Input

Line 1: H, W and T. Then H rows of W values. Then N and N lines row column.

Output

N lines.

Constraints

5 ≤ H, W ≤ 40; N ≤ 50; T ≥ 0.

Example

Input:

8 8 100
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 4 4 4 4 4
0 0 0 4 4 4 4 4
0 0 0 4 4 4 4 4
0 0 0 4 4 4 4 4
0 0 0 4 4 4 4 4
3
3 3
3 5
5 5

Output:

row 3, column 3: R = 3020.80, corner
row 3, column 5: R = -460.80, edge
row 5, column 5: R = 0.00, flat

Why it works

The determinant is large only when brightness changes in two directions, while the trace counts all change; subtracting k × trace² makes edges negative, corners positive and flat areas zero.

Examples

Example 1 · Input
8 8 100
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 4 4 4 4 4
0 0 0 4 4 4 4 4
0 0 0 4 4 4 4 4
0 0 0 4 4 4 4 4
0 0 0 4 4 4 4 4
3
3 3
3 5
5 5
Expected output
row 3, column 3: R = 3020.80, corner
row 3, column 5: R = -460.80, edge
row 5, column 5: R = 0.00, flat
Example 2 · Input
5 5 10
0 0 0 0 0
0 0 0 0 0
0 0 2 0 0
0 0 0 0 0
0 0 0 0 0
1
2 2
Expected output
row 2, column 2: R = 51.20, corner

Prompts inside input() are ignored when checking, so input("n: ") is fine.

Hints

Hint 1

For each of the nine pixels (y, x) around the query, Ix = I[y][x + 1] − I[y][x − 1] and Iy = I[y + 1][x] − I[y − 1][x].

Hint 2

Sum Ix², Iy² and Ix·Iy, then R = Sxx·Syy − Sxy² − 0.05 × (Sxx + Syy)².

Solution

Show one correct solution (try it yourself first)
h, w, T = map(int, input().split())
img = [list(map(int, input().split())) for _ in range(h)]
for _ in range(int(input())):
    r, c = map(int, input().split())
    sxx = syy = sxy = 0
    for y in range(r - 1, r + 2):
        for x in range(c - 1, c + 2):
            ix = img[y][x + 1] - img[y][x - 1]
            iy = img[y + 1][x] - img[y - 1][x]
            sxx += ix * ix
            syy += iy * iy
            sxy += ix * iy
    R = sxx * syy - sxy * sxy - 0.05 * (sxx + syy) ** 2
    kind = "corner" if R > T else "edge" if R < -T else "flat"
    print(f"row {r}, column {c}: R = {R:.2f}, {kind}")

Lesson: Template matching and corner features →