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
3 4 4 0 9 0 0 0 9 0 0 0 9 0 0
cell 0 0: raw 9.00 0.00 0.00 0.00 -> 1.000 0.000 0.000 0.000
4 3 4 0 0 0 0 0 0 5 5 5 5 5 5
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 →