Hough Transform

Figure: Example of the Hough Transform for detecting lines in polar coordinates: accumulator map (top right) for a single point (top left), and accumulator map (bottom right) for a set of collinear points together with outliers (bottom left).

Let $g(\mathbf{x}, \boldsymbol\beta)=0$ be a continuous manifold in $\mathbf {x}$ whose parameters $\boldsymbol\beta \in \mathbb{R}^m$ are to be estimated. To recover these parameters and completely define the function, a set of coordinates $S = \left\{ \mathbf{x}_1, \ldots, \mathbf{x}_n \right\}$ belonging to the locus of the function is available; these coordinates may be noisy and, above all, may contain outliers.

The Hough Transform (Hough Transform) is a technique that makes it possible to group a “highly probable” set of points satisfying certain parametric constraints (PIK92).

For each possible point $\boldsymbol\beta^{*}$ in parameter space, it is possible to assign a vote $H(\boldsymbol\beta)$ of the form

$$H(\boldsymbol\beta^{*}) = \left\{ \mathbf{x} : g(\mathbf{x}, \boldsymbol\beta^{*}) = 0, \mathbf{x} \in S \right\}$$ (4.124)

that is, the number of elements of $S$ satisfying the constraint expressed by $g$. The parameter $\boldsymbol\beta^{*}$ that maximizes this vote is the statistically most probable solution to the problem.

Now let the function $p(\mathbf{x}, \boldsymbol\beta)$ be a likelihood measure between the pair $(\mathbf{x}, \boldsymbol\beta)$ and the constraint expressed by $g(\mathbf{x}, \boldsymbol\beta)=0$. The function $p$ is normally binary, but can readily represent a probability in the general case. Using the function $p$, the Hough transform $H(\boldsymbol\beta)$ can be constructed incrementally through

$$H(\boldsymbol\beta) = \sum_{i=1}^{n} p(\mathbf{x}_i, \boldsymbol\beta)$$ (4.125)

The Hough transform is the sum of all these functions.

For particular constraints, this approach can be simplified further to reduce computational and memory costs.

Let $\beta_1 \ldots \beta_m$ therefore be bounded, quantizable parameters to be estimated, and let $f$ and $\beta_1$ be a function and a parameter such that the function $g(\mathbf{x}, \boldsymbol\beta)=0$ can be written as

$$\beta_1 = f(\mathbf{x}, \beta_2 \ldots \beta_m)$$ (4.126)

If the function $g$ can be expressed as in equation (4.126), the discrete Hough transform can be used to estimate the parameters $\boldsymbol\beta$ representing the most “probable” model among all the supplied points $\mathbf {x}$. For each element $\mathbf {x}$, the parameters $\beta_2 \ldots \beta_m$ can be varied over their range, and the values of $\beta_1$ returned by function (4.126) can be inserted into the accumulator image $H(\boldsymbol\beta)$.

This makes it possible to generate an n-dimensional probability map using observations $\mathbf {x}$ affected by noise and potentially containing outliers. Similarly, the Hough method makes it possible to estimate a model in the presence of a mixture of models with different parameters.

The performance of the Hough method improves as the number of constraints increases, dynamically restricting, for example, the range of the parameters associated with sample $\mathbf {x}$. The Hough algorithm can be viewed as a degenerate form of template matching.

The use of Hough is generally most interesting when the model has only two parameters, since it can then be easily plotted on a two-dimensional map.

A very common example of the Hough transform is the case in which $g$ (the model) is a line, expressed in polar form as in equation (1.82), where the parameters to be determined are $\theta$ and $\rho$: it is clear that, for every pair of points $(x,y)$ and for every possible quantized and bounded angle $\theta$ (since the angle is a bounded parameter), there is one and only one $\rho$ satisfying equation (1.82).

It is therefore possible to create map $H(\theta,\rho)$ in which, for every point $(x,y) \in S$ and every $\theta \in [\theta_{min}, \theta_{max}]$, the element associated with $(\theta, \cos \theta x + \sin \theta y )$ is incremented in the accumulator map; this relationship satisfies equation (1.82) for the line expressed in polar coordinates.