Content deleted Content added
Flameturtle (talk | contribs) m added some links |
Vegaswikian (talk | contribs) Help needed: Analytical, Accumulator |
||
Line 4:
==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> 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]]{{dn|date=February 2014}} 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:▼
▲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 [[ellipse]]s is:
<math>a (x - p)^2+ 2b (x-p) (y-q) + c (y-q)^2 + 1 = 0 </math>
Line 33 ⟶ 31:
===Accumulating===
With the ellipse parameters determined from previous stage, the [[accumulator]]{{dn|date=February 2014}} 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.
Line 59 ⟶ 55:
==References==
{{reflist}}
[[Category:Image processing]]
| |||