Introduction

Look at a photograph. Somewhere in it there are lines — the edge of a road, a shelf on a wall, a lane marking on a motorway. The pixels that form those lines are noisy: they are slightly off-position, some are missing, some extra ones appear by chance. How does a computer find the line hidden behind all that noise?

A naive answer is to try every possible pair of pixels and see if many others fall on the same line. That works but costs O(n2)O(n^2) pairs and O(n3)O(n^3) checks — far too slow for a real image.

In 1959 Paul Hough filed a patent on a cleverer idea. Instead of searching over pixel pairs, let every single edge point vote for all the lines that pass through it. A real line in the image will be the only place where many points all vote for the same candidate. Find the peak in the vote tally and you have found the line.

This idea — casting a hard search over many objects into a vote accumulation in a purpose-built parameter space — became one of the most influential tricks in computer vision, and it works even when much of the line is hidden by noise or occlusion.

Try It

Click anywhere on the left canvas to place edge points. Each point you add casts a vote for every line through it — drawn as a sinusoidal curve in the right accumulator panel. Where many curves cross, votes pile up into a bright peak. That peak is the line the algorithm detects.

<!-- Hough Transform demo: left canvas = image space, right canvas = Hough accumulator -->
<div class="hint-bar">Click the left canvas to place edge points. Each point casts votes for all lines through it — shown as a sinusoidal curve in the right accumulator. Lines with many votes glow red.</div>
<div class="panels">
  <div class="panel-wrap">
    <div class="panel-label">Image space</div>
    <canvas id="imgCanvas" width="200" height="200"></canvas>
  </div>
  <div class="panel-wrap">
    <div class="panel-label">Hough accumulator</div>
    <canvas id="accumCanvas" width="200" height="200"></canvas>
    <div class="accum-axes">
      <span class="axis-x">θ →</span>
      <span class="axis-y">↑ ρ</span>
    </div>
  </div>
</div>
<div class="status" id="status">Click the canvas or add random points.</div>
<div class="btns">
  <button id="btnRandom" type="button">Add random points</button>
  <button id="btnReset" type="button" class="ghost">Reset</button>
</div>

/* Layout: two side-by-side canvases with labels and control buttons */
* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; padding: 4px; }
.hint-bar { font-size: .85rem; color: #444; margin: 0 0 .6rem; line-height: 1.45; }
.panels { display: flex; gap: 10px; flex-wrap: wrap; margin-bottom: .5rem; }
.panel-wrap { display: flex; flex-direction: column; align-items: center; }
.panel-label { font-size: .75rem; font-weight: 600; color: #555; margin-bottom: 4px; letter-spacing: .04em; text-transform: uppercase; }
canvas { border: 1px solid #cdd9e3; border-radius: 6px; cursor: crosshair; display: block; }
#accumCanvas { cursor: default; }
.accum-axes { display: flex; justify-content: space-between; width: 200px; font-size: .7rem; color: #888; margin-top: 2px; }
.axis-y { position: relative; right: -192px; top: -218px; }
.status { font-size: .9rem; font-weight: 600; margin: .4rem 0; min-height: 1.4em; }
.status.info { color: #1d3557; }
.status.ok { color: #0a7d33; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 13px system-ui; padding: .4rem .85rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }

const i18nFmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Hough parameter space: theta in [0, pi) mapped to THETA_STEPS columns,
// rho in [-RHO_MAX, RHO_MAX] mapped to RHO_STEPS rows in the accumulator grid.
const W = 200, H = 200;
const THETA_STEPS = 180;
const RHO_MAX = Math.round(Math.sqrt(W * W + H * H));
const RHO_STEPS = 180;

const imgCanvas = document.getElementById('imgCanvas');
const accumCanvas = document.getElementById('accumCanvas');
const imgCtx = imgCanvas.getContext('2d');
const accumCtx = accumCanvas.getContext('2d');

// Global state: list of placed points and the flat 2-D accumulator array.
let points = [];
let accum = new Array(THETA_STEPS * RHO_STEPS).fill(0);
let maxVotes = 0;

// Render the image canvas: white background with blue dots at each point.
function drawImage() {
  imgCtx.clearRect(0, 0, W, H);
  imgCtx.fillStyle = '#f5f8fa';
  imgCtx.fillRect(0, 0, W, H);
  imgCtx.fillStyle = '#1d3557';
  for (const [px, py] of points) {
    imgCtx.beginPath();
    imgCtx.arc(px, py, 3, 0, Math.PI * 2);
    imgCtx.fill();
  }
}

// Render accumulator as a heat-map: blue=0 votes, red=max votes.
function drawAccum() {
  const imgData = accumCtx.createImageData(W, H);
  const d = imgData.data;
  for (let t = 0; t < THETA_STEPS; t++) {
    for (let r = 0; r < RHO_STEPS; r++) {
      const v = maxVotes > 0 ? accum[t * RHO_STEPS + r] / maxVotes : 0;
      const bright = Math.round(v * 255);
      const i = (r * W + t) * 4;
      d[i] = bright;
      d[i + 1] = Math.round(bright * 0.6);
      d[i + 2] = 255 - bright;
      d[i + 3] = 255;
    }
  }
  accumCtx.putImageData(imgData, 0, 0);
  // Highlight the cell with the most votes (the detected line parameters).
  if (maxVotes >= 2) {
    let bestT = 0, bestR = 0;
    for (let t = 0; t < THETA_STEPS; t++) {
      for (let r = 0; r < RHO_STEPS; r++) {
        if (accum[t * RHO_STEPS + r] > accum[bestT * RHO_STEPS + bestR]) {
          bestT = t; bestR = r;
        }
      }
    }
    accumCtx.strokeStyle = '#e63946';
    accumCtx.lineWidth = 1.5;
    accumCtx.strokeRect(bestT - 4, bestR - 4, 9, 9);
  }
}

// For a new point (px,py), increment every accumulator cell it votes for.
function castVotes(px, py) {
  for (let ti = 0; ti < THETA_STEPS; ti++) {
    const theta = (ti * Math.PI) / THETA_STEPS;
    const rho = px * Math.cos(theta) + py * Math.sin(theta);
    const ri = Math.round(((rho + RHO_MAX) / (2 * RHO_MAX)) * (RHO_STEPS - 1));
    if (ri >= 0 && ri < RHO_STEPS) {
      accum[ti * RHO_STEPS + ri]++;
      if (accum[ti * RHO_STEPS + ri] > maxVotes) maxVotes = accum[ti * RHO_STEPS + ri];
    }
  }
}

function addPoint(px, py) {
  points.push([px, py]);
  castVotes(px, py);
  drawImage();
  drawAccum();
  setStatus(i18nFmt('%n% point(s) placed — watch the accumulator.', { n: points.length }), 'info');
}

function setStatus(t, cls) {
  const s = document.getElementById('status');
  s.textContent = t;
  s.className = 'status ' + cls;
}

// Handle clicks on the image canvas: add a point at the clicked pixel.
imgCanvas.addEventListener('click', (e) => {
  const rect = imgCanvas.getBoundingClientRect();
  const px = Math.round((e.clientX - rect.left) * (W / rect.width));
  const py = Math.round((e.clientY - rect.top) * (H / rect.height));
  addPoint(px, py);
});

// Scatter ~12 noisy collinear points along a random line.
document.getElementById('btnRandom').addEventListener('click', () => {
  const cx = 50 + Math.random() * 100;
  const cy = 50 + Math.random() * 100;
  const angle = Math.random() * Math.PI;
  const cos = Math.cos(angle), sin = Math.sin(angle);
  for (let i = 0; i < 12; i++) {
    const t = -80 + i * 14;
    const noise = (Math.random() - 0.5) * 12;
    const px = Math.round(cx + cos * t + (Math.random() - 0.5) * noise);
    const py = Math.round(cy + sin * t + (Math.random() - 0.5) * noise);
    if (px >= 0 && px < W && py >= 0 && py < H) addPoint(px, py);
  }
});

document.getElementById('btnReset').addEventListener('click', () => {
  points = [];
  accum = new Array(THETA_STEPS * RHO_STEPS).fill(0);
  maxVotes = 0;
  drawImage();
  drawAccum();
  setStatus('Click the canvas or add random points.', '');
});

// Initial render: blank image canvas and blank (light) accumulator.
drawImage();
accumCtx.fillStyle = '#f5f8fa';
accumCtx.fillRect(0, 0, W, H);
Result
Console

Hit Add random points to scatter a set of noisy collinear points and watch the accumulator concentrate. The Reset button clears everything. Notice that even when several points are off the true line, the peak remains sharp — the transform is robust to noise precisely because it requires only a majority of points to agree, not unanimity.

The Real Complexity

The elegance of the Hough transform hides a careful trade-off between speed and resolution.

The parameter space for lines. A line in an image can be parameterized as ρ=xcos⁡θ+ysin⁡θ\rho = x \cos\theta + y \sin\theta, where ρ\rho is the perpendicular distance from the origin and θ∈[0°,180°)\theta \in [0°, 180°) is the angle. Every edge point (x,y)(x, y) maps to a sinusoidal curve in the (θ,ρ)(\theta, \rho) accumulator grid. Two points on the same line produce curves that cross at exactly one (θ,ρ)(\theta, \rho) pair — the line's parameters.

Cost. If there are nn edge points and the accumulator has RR cells along each axis, then filling the accumulator costs O(n⋅R)O(n \cdot R) time. Finding the peak costs O(R2)O(R^2). Total: O(n⋅R+R2)O(n \cdot R + R^2). For a 512×512512 \times 512 image with n≈10,000n \approx 10{,}000 edge points and R=360R = 360 cells, that is about 3.63.6 million operations — fast enough for real-time use.

The resolution trade-off. A coarser accumulator (small RR) is faster but merges nearby lines into one peak. A finer accumulator separates close lines but needs more memory and time. In practice R≈180R \approx 180 to 360360 gives a good balance.

Generalized Hough. Dana Ballard extended the idea in 1981 to arbitrary shapes: instead of a sinusoid, each edge point votes along a lookup table of possible orientations. The same voting principle applies. This is known as the Generalized Hough Transform and is the basis of template matching in many vision pipelines. See also dimensionality reduction for related ideas about projecting high-dimensional search spaces into manageable ones.

Where It Matters

The Hough transform is not a museum piece — it drives production systems across many fields:

  • Autonomous vehicles: lane-line detection on motorways is often the first pipeline stage in a self-driving stack, running on every camera frame at 30 Hz.
  • Document scanning: detecting the edges of a page in a photo so the image can be de-skewed and cropped precisely.
  • Medical imaging: finding circular cell boundaries in microscopy images with the circular Hough transform (which votes in (xc,yc,r)(\text{x}_c, \text{y}_c, r) space).
  • Industrial inspection: locating straight welds or panel edges on an assembly line, robust to dirt and lighting variation.
  • Astronomy: detecting linear streaks left by satellites or cosmic rays in telescope images.
  • Robotics: a robot that must align itself with a wall can use the Hough transform to read the dominant line from its depth sensor.

The common thread is robustness to noise and partial occlusion. Any method that required all pixels on a line to be perfect would fail immediately in real environments. The Hough transform asks only that enough points vote for the same candidate, making it a practical tool where classical geometry cannot cope. See also pattern matching for a complementary view on finding structure inside noisy signals.

Conclusion

Paul Hough's insight was surprisingly simple: instead of searching for lines directly, let the lines find themselves through collective voting. Each edge point says "I could be on any of these lines" and casts a ballot for all of them. The true line, supported by many points, accumulates far more votes than any noise-induced phantom.

That shift — from direct search to parameter-space accumulation — made line detection robust, parallelizable, and fast enough for real-time systems. Variants of the same idea now detect circles, ellipses, and arbitrary shapes in everything from autonomous vehicles to cancer screening.

The next time you see a self-driving car hug a lane or a phone app straighten a photo, there is a good chance a descendant of Hough's patent is quietly counting votes in a grid you will never see.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/hough-transform/Content licensed under CC BY-NC 4.0.