Improved Curve Detection Through Decomposition of the Hough Transform
Clark F. Olson · eCommons (Cornell University) · 1995
This paper describes techniques to perform fast and accurate curve detection using a variant of the Hough transform. It is shown that the Hough transform can be decomposed into many small subproblems, where each subproblem considers only curves that pass through some subset of the points. These curves correspond to a manifold in the parameter space. This property allows the effects of localization error to be modeled more accurately than previous systems. The additional use of randomization techniques leads to efficient algorithms. The time required by this method is O(n), where n is the number of edge points in the image, if we are only required to find curves that are significant with respect to the complexity of the image. Results are given showing the detection of lines and circles in real images. 1 Introduction The Hough transform is a method to detect parameterized curves in images by mapping image edge points into manifolds in parameter space and then finding peaks in the par...