Hough Accumulator

The task is to implement the Hough line transform accumulator: for each edge point, vote in a 2D array over angle $$\theta$$ and distance $\rho$, counting how many points support each possible line.

---

1. Background Knowledge (Concepts & Theory)

• A straight line in image (Cartesian) coordinates $(x, y)$ can be written in Hough form:

$$\rho = x \cos\theta + y \sin\theta$$

where:

• $\rho$ is the perpendicular distance from the origin to the line.

• $$\theta$$ is the angle of the line’s normal vector with the x-axis.

• The Hough transform maps points in image space to curves in parameter space $($\theta$, \rho)$.

• One image point lies on infinitely many lines → in $($\theta$, \rho)$ space this is represented as a sinusoidal curve.

• If many points lie on the same geometric line, their curves intersect at a common $($\theta$, \rho)$. Counting votes in a 2D accumulator lets you find peaks that correspond to actual lines in the image.

• Because images are discrete and bounded, you:

• Discretize $$\theta$$ into bins in $[0^\circ, 180^\circ)$.

• Discretize $\rho$ into bins in $[-\rho_{\max}, \rho_{\max}]$, where

$$\rho_{\max} = \sqrt{\text{width}^2 + \text{height}^2}$$

• Use a 2D array acc[theta_idx][rho_idx] to count votes.

---

2. Algorithm / General Approach

Pattern for this problem:

1. Precompute discretization:

• Choose number of $$\theta$$ bins (numTheta).
• Derive number of $\rho$ bins (numRho) from image size and desired resolution.

2. Precompute trigonometry:

• For each $$\theta$$-bin, precompute cos(theta) and sin(theta).

3. Iterate over all edge points:

• For each point $(x, y)$ and for every $$\theta$$-bin:
• Compute continuous $\rho$.
• Map $\rho$ to a discrete bin index.
• Increment the corresponding accumulator cell.

4. Optionally, peak detection on the accumulator gives detected lines (not required for just building the accumulator).

This is a nested-loop voting algorithm: outer loop over points, inner loop over parameter bins, updating a shared 2D histogram.

---

3. Step-by-Step Strategy (Implementation Outline)

Assume you’re given:

• Image width, height
• List of edge points edges = [(x1, y1), (x2, y2),...]
• numTheta and numRho (or at least numTheta and you derive numRho)

1) Define parameter ranges

import math

max_rho = math.sqrt(width**2 + height**2)

# theta in [0, 180)
num_theta = N_theta # e.g. 180 or 360 depending on resolution
theta_step = math.pi / num_theta # radians per bin

# rho in [-max_rho, max_rho]
num_rho = N_rho # choose resolution; e.g. int(2 * max_rho) or so
rho_step = (2 * max_rho) / num_rho

2) Precompute sin/cos for each θ-bin

cos_t = [math.cos(i * theta_step) for i in range(num_theta)]
sin_t = [math.sin(i * theta_step) for i in range(num_theta)]

3) Initialize the accumulator

# 2D array: theta index × rho index
acc = [[0 for _ in range(num_rho)] for _ in range(num_theta)]

4) Voting loop

Core idea: map continuous $\rho$ to an integer bin:

$$\text{rho\_idx} = \left\lfloor \frac{\rho + \rho_{\max}}{\text{rho\_step}} \right\rfloor$$

for (x, y) in edges:
 for t_idx in range(num_theta):
 rho = x * cos_t[t_idx] + y * sin_t[t_idx] # continuous
 rho_idx = int((rho + max_rho) / rho_step) # shift to [0, 2*max_rho]
 if 0 <= rho_idx < num_rho:
 acc[t_idx][rho_idx] += 1

At the end, acc is your Hough accumulator.

---

4. Common Pitfalls

• Wrong coordinate origin:

• Make sure $(x, y)$ are defined consistently with your Hough equation.

• Many implementations use origin at the image center instead of top-left; if the problem assumes one, stick to that consistently.

• Incorrect ρ indexing / negative ρ:

• $\rho$ can be negative. You must shift by +max_rho before dividing by rho_step to get a non-negative index.

• Check boundary conditions so rho_idx never goes outside [0, num_rho-1].

• Angle units:

• Use radians for sin/cos in code, even if conceptual description uses degrees.

• Ensure the mapping from theta_idx to actual angle is correct:

theta = theta_idx * theta_step # theta_step in radians

• Too coarse or too fine bin sizes:

• Very coarse bins → accumulator too “blurry”, peaks are weak or merged.

• Extremely fine bins → accumulator huge and sparse, expensive and noisy.

• Performance issues:

• Complexity is O(N_\text{points} \times N_\theta$)$. With many points and large numTheta, this is expensive; precomputing sin/cos helps, and sometimes you limit theta range using gradient orientation (not required here but common in practice).

---

5. Time & Space Complexity

Let:

• $P$ = number of edge points

• $T$ = number of $$\theta$$-bins (numTheta)

• $R$ = number of $\rho$-bins (numRho)

• Time Complexity:

• Outer loop over all points: $P$

• Inner loop over all angles: $T$

• Constant work inside (a few arithmetic ops, one array increment).

• Overall:

$$O(P \times T)$$

• Space Complexity:
• Accumulator is a 2D array of size $T \times R$.
• Auxiliary arrays for sin/cos are size $T$.
• Overall dominated by accumulator:

$$O(T \times R)$$