# Generalized Hough transform

Two possible difficulties may occur in the above Hough transform method: (a) the shape has to be described by an equation, and (b) the number of parameters (dimensions of the parameter space) may be high. Given the two equations:

we still have to search the remaining dimensions of the parameter space. These two difficulties can be avoided by the generalized Hough transform shown below.

1. Preparation: build a table for the given shape

• Prepare a table with entries each indexed by an angle ( ) which increases from 0 to 180 degrees with increment , where is the resolution of the gradient orientation (see below).

• Define a reference point somewhere inside the 2D shape (e.g., the gravitational center). For each point on the boundary of the shape, find two parameters

and the gradient direction . Add the pair to the table entry with its closest to .

• Prepare a 2D Hough array initialized to 0.

2. Detection of the shape and its locations in image

For each image point with , find the table entry with its corresponding angle closest to . Then for each of the pairs ( ) in this table entry, find

and increment the corresponding element in the H array by 1:

All elements in the H table satisfying represent the locations of the shape in the image.

It is desirable to detect a certain 2D shape independent of its orientation and scale, as well as its location. To do so, two additional parameters, a scaling factor and a rotational angle , are needed to describe the shape. Now the Hough space becomes 4-dimensional . The detection algorithm becomes the following:

For each image point with , find the proper table entry with . Then for each of the pairs ( ) in this table entry, do the following for all and : find

and increment the corresponding element in the 4D H array by 1:

All elements in the H table satisfying represent the scaling factor , rotation angle of the shape, as well as its reference point location in the image.