Foundations
Hough Transform
how casting the problem into a parameter space turns line detection into a voting problem: every point that could lie on a given line votes for it, and the lines with the most votes are the ones that are actually there.
Stage 1 of 4: Image space
Sweep angle 45°: 2 points agree at rho 7.1.
Sweep angle 45°: 2 points agree at rho 7.1.
- Image point
- Point’s candidate line at θ
- Points currently agreeing
- Detected line
Six points, forming three lines: a diagonal, a horizontal, and a vertical. To an algorithm this is six disconnected pixels — nothing here says which point belongs with which.
Check your understanding
Discover how computer vision translates the difficult problem of finding lines in an image into the simple problem of finding intersecting curves in a parameter space.
Finding lines in an image seems trivial to a human, but it is notoriously difficult for an algorithm. In an edge-detected image, you simply have a sea of disconnected pixels. How do you group them into mathematical lines?
The Hough Transform solves this by turning the search for lines into a voting system. Instead of asking "which line connects these pixels?", it asks every pixel to draw all the possible lines that could pass through it in a new mathematical realm called Hough Space.
When multiple pixels belong to the same straight line in the original image, their curves perfectly intersect at a single point in Hough space. The brightest points in the accumulator thus reveal the dominant lines in the image.
Sweep the angle by hand in the second stage and watch three of the six points' curves cross at once — that crossing is the vote. The accumulator in the third stage is that same vote, counted over every angle at once and drawn as a heatmap. The last stage puts a number on "how many votes is enough": push the threshold past the strongest cell in this image and every detected line disappears, real or not.
Reference
- Rho (ρ)
- Perpendicular distance from the origin to the line
- Theta (θ)
- Angle of that perpendicular from the x-axis
- Line equation
- ρ = x·cos(θ) + y·sin(θ)
- Accumulator
- A count of votes for every (θ, ρ) pair, over every point and every angle
- Detection rule
- Keep (θ, ρ) where votes ≥ threshold, then draw that line back onto the image
Break it on purpose
Raise the voting threshold above 3 and every detected line vanishes — the strongest line in this image only ever collects 3 votes, so a threshold set higher than the true peak rejects every line, real or not. Lower it to 1 and even two points that merely happen to agree at one angle register as a line, though nothing in the image actually forms one.