Generalised Hough transform

[1] The Hough transform was initially developed to detect analytically defined shapes (e.g., line, circle, ellipse etc.).

This modification enables the Hough transform to be used to detect an arbitrary object described with its model.

This maximum can be found by scanning the Hough space or by solving a relaxed set of equations, each of them corresponding to a black pixel.

[2] Merlin and Farber[3] showed how to use a Hough algorithm when the desired curves could not be described analytically.

It was a precursor to Ballard's algorithm that was restricted to translation and did not account for rotation and scale changes.

To generalize the Hough algorithm to non-analytic curves, Ballard defines the following parameters for a generalized shape: a={y,s,θ} where y is a reference origin for the shape, θ is its orientation, and s = (sx, sy) describes two orthogonal scale factors.

Given any shape and a fixed reference point on it, instead of a parametric curve, the information provided by the boundary pixels is stored in the form of the R-table in the transform stage.

The cell with maximum 'votes' in the Accumulator matrix can be a possible point of existence of fixed reference of the object in the test image.

Notice that each index of ɸ may have many values of r. One can either store the co-ordinate differences between the fixed reference and the edge point ((xc – xij), (yc – yij)) or as the radial distance and the angle between them (rij, αij).

The R-table can also be used to increment this larger dimensional space since different orientations and scales correspond to easily computed transformations of the table.

Another property which will be useful in describing the composition of generalized Hough transforms is the change of reference point.

If we want to choose a new reference point ỹ such that y-ỹ = z then the modification to the R-table is given by R(ɸ)+ z, i.e. z is added to each vector in the table.

Using the R-table and the properties as described above, each edge pixel defines a surface in the four-dimensional accumulator space of a = (y, s, θ).

Two edge pixels at different orientations describe the same surface rotated by the same amount with respect to θ.

However, the difficulties of finding the intersection points of the two surfaces in parameter space will make this approach unfeasible for most cases.

Observing that the global Hough transform can be obtained by the summation of local Hough transforms of disjoint sub-region, Heather and Yang[5] proposed a method which involves the recursive subdivision of the image into sub-images, each with their own parameter space, and organized in a quadtree structure.

The implementation uses the following equations:[6] Combining the above equations we have: Constructing the R-table Detection: General case: Suppose the object has undergone some rotation Θ and uniform scaling s: Ballard suggested using orientation information of the edge decreasing the cost of the computation.