Randomized Hough transform: Difference between revisions

Revision as of 08:24, 30 June 2014

Latest revision as of 09:27, 21 January 2025

(4 intermediate revisions by 4 users not shown)

Line 12:

===Ellipse fitting===

One general equation for defining [[ellipse]]s is:

<math>a (x - p)^2+ 2b (x-p) (y-q) + c (y-q)^2 += 1 = 0 </math>

with restriction: <math>ac-b^2>0</math>

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

RHT starts by randomly selecting three points on the ellipse. Let them be X<submath>1X_1</submath>, X<submath>2X_2</submath> and X<submath>3X_3</submath>. 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 T<submath>T_{12}</submath> and T<submath>T_{23}</submath>, the midpoints of line segments <math>X_1X_2</math> and <math>X_2X_3</math> be M<submath>M_{12}</submath> and M<submath>M_{23}</submath>. Then the center of the ellipse will lie in the intersection of <math>T_{12}M_{12}</math> and <math>T_{23}M_{23}</math>. 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 (x<sub>0</submath>(x_0, y<sub>0y_0)</submath>). Then the center can be translated to the origin with <math>x' = x-x_0</math> and <math>y' = y-y_0</math> so that the ellipse equation can be simplified to:

<math>ax'^2+2bx'y'+cy'^2=1</math>

Now we can solve for the rest of ellipse parameters: <math>a</math>, <math>b</math> and <math>c</math> by substituting the coordinates of X<submath>1X_1</submath>, X<submath>2X_2</submath> and X<submath>3X_3</submath> into the equation above.

===Accumulating===

Line 36:

Pseudo code for RHT:<ref>S. Inverso, “Ellipse Detection Using Randomized Hough Transform”, www.saminverso.com/res/vision/EllipseDetectionOld.pdf, May 20, 2002</ref>

'''while''' (we find ellipses ORAND not reached the maximum epoch) {

<source lang="cpp">

'''for''' (a fixed number of iterations) {

while (we find ellipses OR not reached the maximum epoch) {

Find a potential ellipse.

for(a fixed number of iterations) {

'''if''' (the ellipse is similar to an ellipse in the accumulator) '''then'''

Find a potential ellipse.

if(the ellipse is similar to anReplace ellipsethe one in the accumulator) with the average of two ellipses and add 1 to the score;

'''else'''

Replace the one in the accumulator with the average of two ellipses and add 1 to the score;

Insert the ellipse into an empty position in the accumulator with a score of 1;

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;

}

Select Eliminate the ellipsepixels withof the best scoreellipse andfrom save it in a best ellipsethe tableimage;

Empty the accumulator;

Eliminate the pixels of the best ellipse from the image;

}

Empty the accumulator;

}

</source>

==References==