Ellipse Detection Using 1D Hough Transform

An efficient ellipse detector based on Hough voting

Overview:

Fits an ellipse by examining all possible major axes (all pairs of points) and getting the minor axis using Hough transform. The algorithm complexity depends on the number of valid non-zero points, therefore it is beneficial to provide as many restrictions in the "params" input arguments as possible if there is any prior knowledge about the problem.

The code is reasonably fast due to (optional) randomization and full code vectorization. However, as the algorithm needs to compute pairwise point distances, it can be quite memory intensive. If you get out of memory errors, either downsample the input image or somehow decrease the number of non-zero points in it. It can deal with big amount of noise but can have severe problem with occlusions (major axis end points need to be visible)

Input arguments:

img

- One-channel input image (greyscale or binary).

params

- Parameters of the algorithm:

* minMajorAxis: Minimal length of major axis accepted.

* maxMajorAxis: Maximal length of major axis accepted.

* rotation, rotationSpan: Specification of restriction on the angle of the major axis in degrees. If rotationSpan is in (0,90), only angles within [rotation-rotationSpan, rotation+rotationSpan] are accepted.

* minAspectRatio: Minimal aspect ratio of an ellipse (in (0,1))

* randomize: Subsampling of all possible point pairs. Instead of examining all N*N pairs, runs only on N*randomize pairs. If 0, randomization is turned off.

* numBest: Top numBest to return

* uniformWeights: Used to prefer some points over others. If false, accumulator points are weighted by their grey intensity in the image. If true, the input image is regarded as binary.

* smoothStddev: In order to provide more stability of the solution, the accumulator is convolved with a gaussian kernel. This parameter specifies its standard deviation in pixels.

verbose

- Whether to print intermediate log messages

Return value:

Returns a matrix of best fits. Each row (there are params.numBest of them) contains six elements: [x0 y0 a b alpha score] being the center of the ellipse, its major and minor semiaxis, its angle in degrees and score.

Based on:

- "A New Efficient Ellipse Detection Method" (Yonghong Xie Qiang , Qiang Ji / 2002)

- random subsampling inspired by "Randomized Hough Transform for Ellipse Detection with Result Clustering" (CA Basca, M Talos, R Brad / 2005)

Update log:

1.3: Minor performance improvements, add verbosity parameter, fix crashes with certain parameter values (kudos to Brett Shoelson, PhD)

1.2: Fixed broken formatting (tabs x spaces)

1.1: More memory efficient code, better documentation, more parameters, more solutions possible, example code.

1.0: Initial version