EP07_05 — 🔴 Histogram of Orientations for an HOG Cell

7.18.5.1 📋 Implementation Guidelines

1. Dimensions: Read the integers \(n\) (the cell has \(n \times n\) pixels) and \(B\) (number of histogram bins).
2. Magnitudes: Read \(n\) lines with \(n\) real values each, representing \(|\nabla f(x,y)|\) for each pixel in the cell.
3. Orientations: Read \(n\) more lines with \(n\) real values each, representing \(\theta(x,y)\) in degrees, already converted to the unsigned interval \([0^\circ, 180^\circ)\), as conventionally used by HOG.
4. Bins: The \(B\) bins cover \([0^\circ, 180^\circ)\) in equal bands of width \(180/B\) degrees. A pixel with orientation \(\theta\) belongs to bin \(\lfloor \theta / (180/B) \rfloor\); if this index equals \(B\) (possible only when \(\theta\) is exactly \(180^\circ\), which should not occur according to the guideline in item 3), use bin \(B-1\).
5. Raw histogram: For each pixel, accumulate its magnitude (not its count) in the corresponding bin: \[ H[b] = \sum_{(x,y)\, :\, \text{bin}(\theta(x,y)) = b} |\nabla f(x,y)|. \]
6. L2 normalization: After constructing \(H\), normalize it to obtain \(\hat H\): \[ \hat H[b] = \frac{H[b]}{\sqrt{\sum_{j=0}^{B-1} H[j]^2 + \epsilon}}, \qquad \epsilon = 10^{-6}. \]
7. Output: Print the raw histogram \(H\) (rounded to 2 decimal places) on one line, followed by the normalized histogram \(\hat H\) (rounded to 4 decimal places) on another line, both with the \(B\) values separated by spaces, in bin order.

7.18.5.2 📌 Computational Constraints

• Unsigned binning: the orientation interval is \([0,180)\), not \([0,360)\) — gradients in opposite directions (differing by \(180^\circ\)) contribute to the same bin, the standard HOG convention for object detection.
• Accumulation by magnitude, not by count: the histogram weights each pixel by its gradient magnitude, rather than simply counting how many pixels fall into each bin.
• Stabilization constant: the \(\epsilon = 10^{-6}\) in the normalization denominator avoids division by zero when the cell is completely homogeneous (all magnitudes zero).

7.18.5.3 📐 Where the Input Matrices Come From

Before this assignment, each pixel \((x,y)\) of the image undergoes:

\[ G_x = f(x+1,y)-f(x-1,y), \qquad G_y = f(x,y+1)-f(x,y-1) \]

\[ |\nabla f| = \sqrt{G_x^2+G_y^2}, \qquad \theta_{\text{signed}} = \operatorname{atan2}(G_y,G_x) \]

Since HOG disregards contrast polarity, the angle is folded into the unsigned interval:

\[ \theta = \theta_{\text{signed}} \bmod 180° \]

Repeating this for all pixels in an \(n\times n\) cell yields the two input matrices for this exercise: magnitudes \(|\nabla f|\) and orientations \(\theta \in [0°,180°)\).

7.18.5.4 🧠 Theoretical Background

The concatenation of the normalized histograms from all cells in the image — not implemented in this exercise — forms the complete HOG feature vector, used as input to the k-NN classifier in the chapter’s project.

7.18.5.5 📦 Input and Output Specification (VPL)

Input:

• Line 1: Integers \(n\) and \(B\).
• Next \(n\) lines: \(n\) real magnitudes each.
• Next \(n\) lines: \(n\) real orientations (degrees, \([0,180)\)) each.

Output:

• Line 1: the \(B\) values of the raw histogram, rounded to 2 decimal places.
• Line 2: the \(B\) values of the normalized histogram, rounded to 4 decimal places.

7.18.5.6 📌 Examples

%%writefile EP07_05.py
# Python code

Overwriting EP07_05.py

TestSuite("EP07_05.py").run()

✔️ EP07_05.cases already exists in casos/
📋 5 case(s) loaded from casos/EP07_05.cases

🔍 Testing Python: EP07_05.py
⚠️ EP07_05.py: Empty file (fewer than 3 lines). Tests skipped.