Gradient Orientation Histogram

You are building a histogram of gradient orientations for a small image patch, which is a core idea behind descriptors like SIFT and HOG.

---

1. Background Knowledge

A grayscale image patch can be seen as a 2D function $I(x, y)$ where the value at each pixel represents intensity. The gradient at a pixel is a 2D vector $\nabla I = (G_x, G_y)$ that points in the direction of the greatest rate of increase of intensity and whose magnitude tells you how strong that change is. Finite differences (like $G_x = I(x, y+1) - I(x, y-1)$) approximate the continuous derivative using neighboring pixels.

The orientation of the gradient, $\theta =$\text{atan2}$(G_y, G_x)$, tells you the dominant edge direction at that pixel (e.g., vertical, horizontal, diagonal). Feature descriptors such as SIFT and HOG aggregate these local orientations into histograms over patches or cells, capturing the dominant edge directions while being robust to small geometric and photometric changes. In your problem, you are implementing the core piece: turning per-pixel gradient orientations into a histogram over $[0, 2$\pi$)$.

---

2. Algorithm / General Approach

The general pattern:

1. Compute gradients at interior pixels using finite differences.
2. Convert gradients to polar form: magnitude and orientation.
3. Filter out trivial gradients (zero magnitude).
4. Quantize orientations into discrete bins over $[0, 2$\pi$)$.
5. Accumulate a histogram: increment the right bin for each pixel.
6. Optionally, normalize the histogram (common in descriptors like SIFT/HOG, though your problem may or may not require this).

Conceptually: you are mapping each pixel from image space to orientation space, then counting how many pixels fall into each orientation interval.

---

3. Step-by-Step Strategy

Assume:

• patch is an H × W 2D array (list of lists).
• num_bins is given.
• You must ignore the outer border for gradient computation (because finite differences need neighbors on both sides).

Step 1: Initialize Histogram

hist = [0.0] * num_bins

Step 2: Loop Over Interior Pixels

Indices for valid interior pixels:

• i in [1, H-2]
• j in [1, W-2]

for i in range(1, H-1):
 for j in range(1, W-1):
 Gx = patch[i][j+1] - patch[i][j-1]
 Gy = patch[i+1][j] - patch[i-1][j]

Step 3: Skip Zero Gradient

 if Gx == 0 and Gy == 0:
 continue

(Optionally, you could use a small epsilon threshold instead of exact zero if values are floats.)

Step 4: Compute Orientation and Wrap to $[0, 2$\pi$)$

import math

 theta = math.atan2(Gy, Gx) # in (-pi, pi]
 if theta < 0:
 theta += 2 * math.pi # now in [0, 2pi)

Step 5: Map Angle to Bin Index

Bin width:

bin_width = 2 * math.pi / num_bins

Bin computation:

 bin_idx = int(theta / bin_width)
 # handle boundary theta == 2*pi (just in case)
 if bin_idx == num_bins:
 bin_idx = num_bins - 1

Step 6: Accumulate Histogram

 hist[bin_idx] += 1.0 # or use gradient magnitude as weight if required

At the end, hist is your gradient orientation histogram.

---

4. Common Pitfalls

• Indexing errors at the image border: Computing patch[i][j+1] or patch[i+1][j] at the border will go out of bounds. Always restrict i and j to interior indices.
• Forgetting angle wrapping: atan2 returns angles in $(-$\pi$,$\pi$]$; you must convert negative angles by adding $2\pi$ to get $[0, 2$\pi$)$.
• Bin edge handling: When theta is very close to $2\pi$ due to floating-point precision, theta / bin_width might equal num_bins, which is out of range. Clamp it back to num_bins - 1.
• Using equality checks with floats: Checking Gx == 0 and Gy == 0 is fine if values are integers; for floats, consider a tiny threshold.
• Ignoring gradient magnitude (if the original task wants magnitude-weighted histograms, as SIFT typically does): then you should compute mag = math.hypot(Gx, Gy) and add mag to the bin instead of 1.0.

---

5. Time & Space Complexity

Let the patch size be $H \times W$ and the number of bins be $B$.

• Time complexity:

• You visit each interior pixel once and do $O(1)$ work per pixel.

• Complexity: $O(H \times W)$. The dependency on $B$ is constant, as binning is just an index computation.

• Space complexity:

• You store the original patch: $O(H \times W)$ (given).

• The histogram uses $O(B)$ extra space.

• Additional variables are constant-size.

• Extra space: $O(B)$.