Randomized Hough transform: Difference between revisions

Revision as of 01:57, 1 May 2010

Latest revision as of 09:27, 21 January 2025

(23 intermediate revisions by 20 users not shown)

Line 1:

Hough transforms are techniques for [[object detection]], a critical step in many implementations of [[computer vision]], or [[data mining]] from images. Specifically, the '''Randomized Hough trasformtransform''' is a probabilistic variant to the classical [[Hough transform]], whichand is a commonly used techniqueto for detectingdetect curves (straight line, circle, ellipse, etc.)<ref>D.H. Ballard, "Generalizing the Hough Transform to Detect Arbitrary Shapes", Pattern Recognition, Vol.13, No.2, p.111-122, 1981</ref> The basic idea of Hough transform (HT) is to implement a voting procedure for all potential curves in the image, and at the termination of the [[algorithm]], curves that do exist in the image will have relatively high voting scores. Randomized Hough transform (RHT) is different from HT in that it tries to avoid conducting the computationally expensive voting process for every nonzero pixel in the image by taking advantage of the geometric properties of analytical curves, and thus improve the time efficiency and reduce the storage requirement of the original algorithm.

==Motivation==

Although Hough transform (HT) has been widely used in [[Edge detection|curve detection]], it has two major drawbacks:<ref>L. Xu, E. Oja, and P. Kultanan, "A new curve detection method: Randomized Hough transform (RHT)", ''Pattern Recog. Lett.'' 11, 1990, 331-338.</ref> (1)First, Forfor each nonzero pixel in the image, the parameters for the exsitingexisting curve and redundant ones are both accumulated during the voting procudureprocedure. (2)Second, Thethe accumulator array (or Hough space) is predefined in a heuristic way. The bettermore accuracy we needneeded, the higher parameter resolution should be defined. These two needs usually result in a large storage requirement and low speed for real applications. Therefore, RHT was brought up to tackle this problem.

Although Hough transform (HT) has been widely used in curve detection, it has two major drawbacks:<ref>L. Xu, E. Oja, and P. Kultanan, "A new curve detection method: Randomized Hough transform (RHT)", ''Pattern Recog. Lett.'' 11, 1990, 331-338.</ref> (1) For each nonzero pixel in the image, the parameters for the exsiting curve and redundant ones are both accumulated during the voting procudure. (2) The accumulator array (or Hough space) is predefined in a heuristic way. The better accuracy we need, the higher parameter resolution should be defined. These two needs usually result in a large storage requirement and low speed for real applications. Therefore, RHT was brought up to tackle this problem.

==Implementation==

In comparison with HT, RHT takes advantage of the fact that some [[analytic variety|analytical]] curves can be fully determined by a certain number of points on the curve. For example, a stragitstraight line can be determined by two points, and an [[ellipse]] (or a circle) can be determined by three points. ToThe illustratecase theof basicellipse ideadetection ofcan RHT,be let'sused considerto illustrate the casebasic idea of ellipse detectionRHT. The whole process generally consists of three steps:

1)# Fit ellipses with randomly selected points;.

2)# Update the accumulator array and corresponding scores;.

3)# Output the ellipses with scores higher than some predefined threshold.

===Ellipse Fittingfitting===

In comparison with HT, RHT takes advantage of the fact that some analytical curves can be fully determined by a certain number of points on the curve. For example, a stragit line can be determined by two points, and an ellipse (or a circle) can be determined by three points. To illustrate the basic idea of RHT, let's consider the case of ellipse detection. The whole process generally consists of three steps:

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

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

1) Fit ellipses with randomly selected points;

2) Update the accumulator array and corresponding scores;

3) Output the ellipses with scores higher than some predefined threshold.

===Ellipse Fitting===

One general equation for defining ellipses 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, onlyan ellipse can be fully determined if one knows three points areon neededit toand fullythe determine[[tangent]]s anin ellipse.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 <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 <submath>3X_3</submath> into the equation above.

===Accumulating===

With the ellipse parameters determined from previous stage, the [[accumulator (computing)|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.

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.

===Termination===

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:<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;

Elliminate the pixels of the best ellipse from the image;

}

Empty the accumulator;

}

==References==

</source>

{{reflist}}

[[Category:Image processing]]

[[Category:Computer vision]]

==References==

<references/>