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 transform is a probabilistic variant to the classical Hough transform, and is commonly used to detect curves (straight line, circle, ellipse, etc.) 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 curve detection, it has two major drawbacks: First, for each nonzero pixel in the image, the parameters for the existing curve and redundant ones are both accumulated during the voting procedure. Second, the accumulator array (or Hough space) is predefined in a heuristic way. The more accuracy needed, 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 analytical curves can be fully determined by a certain number of points on the curve. For example, a straight line can be determined by two points, and an ellipse (or a circle) can be determined by three points. The case of ellipse detection can be used to illustrate the basic idea of RHT. The whole process generally consists of three steps:
Fit ellipses with randomly selected points. Update the accumulator array and corresponding scores. Output the ellipses with scores higher than some predefined threshold.
Ellipse fitting One general equation for defining ellipses is:
a ( x − p ) 2 + 2 b ( x − p ) ( y − q ) + c ( y − q ) 2 = 1 {\displaystyle a(x-p)^{2}+2b(x-p)(y-q)+c(y-q)^{2}=1}
with restriction: a c − b 2 > 0 {\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 X 1 {\displaystyle X_{1}} , X 2 {\displaystyle X_{2}} and X 3 {\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 T 12 {\displaystyle T_{12}} and T 23 {\displaystyle T_{23}} , the midpoints of line segments X 1 X 2 {\displaystyle X_{1}X_{2}} and X 2 X 3 {\displaystyle X_{2}X_{3}} be M 12 {\displaystyle M_{12}} and M 23 {\displaystyle M_{23}} . Then the center of the ellipse will lie in the intersection of T 12 M 12 {\displaystyle T_{12}M_{12}} and T 23 M 23 {\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 ( x 0 , y 0 ) {\displaystyle (x_{0},y_{0})} . Then the center can be translated to the origin with x ′ = x − x 0 {\displaystyle x'=x-x_{0}} and y ′ = y − y 0 {\displaystyle y'=y-y_{0}} so that the ellipse equation can be simplified to:
… excerpt ends here. Continue reading the full article.
