Randomized Hough transform

One general equation for defining ellipses is: ${\displaystyle a(x-p)^{2}+2b(x-p)(y-q)+c(y-q)^{2}=1}$

with restriction: ${\displaystyle ac-b^{2}>0}$

However, an ellipse can be fully determined if one knows three points on it and the tangents in these points.

RHT starts by randomly selecting three points on the ellipse. Let them be ${\displaystyle X_{1}}$, ${\displaystyle X_{2}}$ and ${\displaystyle X_{3}}$. The first step is to find the tangents of these three points. They can be found by fitting a straight line using least squares technique for a small window of neighboring pixels.

The next step is to find the intersection points of the tangent lines. This can be easily done by solving the line equations found in the previous step. Then let the intersection points be ${\displaystyle T_{12}}$ and T${\displaystyle T_{23}}$, the midpoints of line segments ${\displaystyle X_{1}X_{2}}$ and ${\displaystyle X_{2}X_{3}}$ be ${\displaystyle M_{12}}$ and ${\displaystyle M_{23}}$. Then the center of the ellipse will lie in the intersection of ${\displaystyle T_{12}M_{12}}$ and ${\displaystyle T_{23}M_{23}}$. Again, the coordinates of the intersected point can be determined by solving line equations and the detailed process is skipped here for conciseness.

Let the coordinates of ellipse center found in previous step be ${\displaystyle (x_{0},y_{0})}$. Then the center can be translated to the origin with ${\displaystyle x'=x-x_{0}}$ and ${\displaystyle y'=y-y_{0}}$ so that the ellipse equation can be simplified to:

${\displaystyle ax'^{2}+2bx'y'+cy'^{2}=1}$

Now we can solve for the rest of ellipse parameters: ${\displaystyle a}$, ${\displaystyle b}$ and ${\displaystyle c}$ by substituting the coordinates of ${\displaystyle X_{1}}$, ${\displaystyle X_{2}}$ and ${\displaystyle X_{3}}$ into the equation above.

With the ellipse parameters determined from previous stage, the accumulator array can be updated correspondingly. Different from classical Hough transform, RHT does not keep "grid of buckets" as the accumulator array. Rather, it first calculates the similarities between the newly detected ellipse and the ones already stored in accumulator array. Different metrics can be used to calculate the similarity. As long as the similarity exceeds some predefined threshold, replace the one in the accumulator with the average of both ellipses and add 1 to its score. Otherwise, initialize this ellipse to an empty position in the accumulator and assign a score of 1.

Once the score of one candidate ellipse exceeds the threshold, it is determined as existing in the image (in other words, this ellipse is detected), and should be removed from the image and accumulator array so that the algorithm can detect other potential ellipses faster. The algorithm terminates when the number of iterations reaches a maximum limit or all the ellipses have been detected.

Pseudo code for RHT:[3]

while (we find ellipses AND not reached the maximum epoch) {
    for (a fixed number of iterations) {
        Find a potential ellipse.
        if (the ellipse is similar to an ellipse in the accumulator) then
            Replace the one in the accumulator with the average of two ellipses and add 1 to the score;
        else
            Insert the ellipse into an empty position in the accumulator with a score of 1;
    }
    Select the ellipse with the best score and save it in a best ellipse table;
    Eliminate the pixels of the best ellipse from the image;
    Empty the accumulator;
}