# Hough Transform It is an algorithm to fit multiple lines. Given a binary edge image, find the lines (or curves) that explain the data points best in the parameter space. This parameter space is called a Hough space. A point $\left(x_{1}, y_{1}\right)$ is mapped to a line in the Hough space. ![[Houghspace.jpg]] Accumulator: - For each pixel, draw a line in the discretised Hough space, assigning a value of one. - Process all image pixels and find local maximum, convert it back to point space. ![[houghdiscreet.jpg]] ## Properties - Can detect multiple lines in an image (from multiple local maxima) - Can be easily extended for circles and ellipses - Computationally efficient. ## Using Polar Form Problem: $(m, b)$ are unbounded. For example, the slope parameter $m$ can have an infinite value. How do we solve it? ![[polarformHoughspace.jpg]] ![[dataHoughspace.jpg]] ## Pipeline Use [[Edge Detection#Canny Edge Detector]] to detect edge, apply Hough transform: ![[edgeToHough.jpg]] Find the peaks and post-process: ![[finalHough.jpg]] ## Advantages - All points are processed independently, so can cope with occlusion - Some robustness to noise: noise points unlikely to contribute consistently to any single bin - Can detect multiple instances of a model in a single pass ## Disadvantages - Complexity of search time increases exponentially with the number of model parameters - Non-target shapes can produce spurious peaks in parameter space - Quantization: hard to pick a good grid size --- ## References