hough transform

The Hough transform finds shapes — lines, circles, ellipses, or arbitrary templates — by letting edge points vote for the shapes they could belong to, and then looking for shapes that collect many votes. The intuition flips the usual question. Instead of asking, for each candidate line, which edge pixels lie on it (slow, and you would have to try every line), you ask, for each edge pixel, which lines could pass through it, and have it cast a vote for all of them. A real line in the image is one that many edge pixels independently vote for, so it shows up as a bright peak in a tally.

Made precise for lines, every line is described by two parameters; the robust choice is its perpendicular distance from the origin (rho) and the angle of that perpendicular (theta), which avoids the infinite slope of vertical lines. A single edge pixel at (x,y) is consistent with a whole family of lines — all the (rho, theta) pairs satisfying rho = x·cos(theta) + y·sin(theta) — which traces a sinusoid in the rho-theta parameter space, called the accumulator. Each edge pixel adds one to every accumulator cell along its sinusoid. Where many sinusoids cross, the corresponding (rho, theta) cell accumulates many votes, marking a line that many pixels agree on. You detect lines by finding local maxima in the accumulator above a vote threshold. Circles work the same way with a three-parameter accumulator (center x, center y, radius), and the generalized Hough transform votes for the reference point of an arbitrary shape stored in a lookup table.

The Hough transform's great strength is robustness: because detection is a global vote, it tolerates gaps in lines (occlusion), noise, and outliers — a partly hidden line still wins if enough of it is visible, and stray edge pixels just scatter harmless votes. Its costs are the curse of dimensionality (the accumulator grows exponentially with the number of shape parameters, so it is practical for lines and circles but expensive beyond) and sensitivity to the bin resolution and threshold. It remains a staple for detecting man-made structure — lane lines in driver assistance, document and table borders, industrial alignment, the circular Hough for pupils and coins — and its core idea, accumulating evidence by voting in a parameter space, reappears in generalized Hough matching, the implicit shape model, and the Hough-voting heads used in some modern 3D and pose networks.