Computer vision: A histogram of gradient orientations

HOG features describe shape by which way the edges run. Build the core of HOG.

What to build

A program that builds a 4-bin gradient-orientation histogram for each cell of an image and normalises it.

Requirements

  • For every pixel with all four side neighbours, compute gx and gy by central differences. Pixels with gx = gy = 0 add nothing.
  • The orientation is atan2(gy, gx) in degrees, taken modulo 180, and goes to the nearest of four bins centred on 0°, 45°, 90° and 135°. Add the magnitude √(gx² + gy²) to that bin of the pixel's cell; the cell of pixel (r, c) is (r // s, c // s).
  • For each cell in reading order print cell I J: raw a b c d -> p q r t: the raw bins with two decimal places, then the bins divided by the histogram's length √(a² + b² + c² + d²) with three decimal places (all zeros if the length is 0).

Input

Line 1: H, W and the cell size s. Then H rows of W values.

Output

One line per cell; there are ⌈H / s⌉ × ⌈W / s⌉ cells.

Constraints

3 ≤ H, W ≤ 40; 1 ≤ s ≤ 20.

Example

Input:

3 4 4
0 9 0 0
0 9 0 0
0 9 0 0

Output:

cell 0 0: raw 9.00 0.00 0.00 0.00 -> 1.000 0.000 0.000 0.000

Why it works

Edges in one direction produce gradients in one bin wherever they are inside the cell, so the histogram describes shape while tolerating small shifts, and normalising removes the effect of contrast.

Examples

Example 1 · Input
3 4 4
0 9 0 0
0 9 0 0
0 9 0 0
Expected output
cell 0 0: raw 9.00 0.00 0.00 0.00 -> 1.000 0.000 0.000 0.000
Example 2 · Input
4 3 4
0 0 0
0 0 0
5 5 5
5 5 5
Expected output
cell 0 0: raw 0.00 0.00 10.00 0.00 -> 0.000 0.000 1.000 0.000

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

Hints

Hint 1

For an inner pixel, gx = I[r][c + 1] − I[r][c − 1] and gy = I[r + 1][c] − I[r − 1][c]; skip it when both are 0.

Hint 2

angle = degrees(atan2(gy, gx)) % 180 and bin = int((angle + 22.5) // 45) % 4; add √(gx² + gy²) to bin `bin` of cell (r // s, c // s).

Solution

Show one correct solution (try it yourself first)
import math

h, w, s = map(int, input().split())
img = [list(map(int, input().split())) for _ in range(h)]
rows, cols = (h + s - 1) // s, (w + s - 1) // s
hist = [[[0.0] * 4 for _ in range(cols)] for _ in range(rows)]
for r in range(1, h - 1):
    for c in range(1, w - 1):
        gx = img[r][c + 1] - img[r][c - 1]
        gy = img[r + 1][c] - img[r - 1][c]
        if gx == 0 and gy == 0:
            continue
        angle = math.degrees(math.atan2(gy, gx)) % 180
        hist[r // s][c // s][int((angle + 22.5) // 45) % 4] += math.sqrt(gx * gx + gy * gy)
for i in range(rows):
    for j in range(cols):
        raw = hist[i][j]
        size = math.sqrt(sum(v * v for v in raw))
        norm = [v / size if size else 0.0 for v in raw]
        print(f"cell {i} {j}: raw " + " ".join(f"{v:.2f}" for v in raw) + " -> " + " ".join(f"{v:.3f}" for v in norm))

Lesson: Classifying images with features and nearest neighbours →