Polygonal object recognition with the use of the Hough transform
Dimitrios Ioannou · University of Florida Digital Collections (University of Florida) · 1998
The most popular method for the recognition of straight lines in a digital image is the Hough transform. In this work we study the effects of the digitization errors on the Hough transform with the tools provided by the Digital Topology Theory. We derive a corrected formula for the worst case spreading of a digital straight line segment of a given length. We also show that even in the perfect case (no noise, perfect digital straight line segments) the peak cell may not best represent the parameters of the digital straight line segment. We also study the performance prediction problem and prove that if the noise in the image is uniform the number of votes in the parameter space follows a binomial distribution. We use the theory presented to propose an algorithm for the estimation of the length of a digital straight line segment from its Hough transform. The algorithm is extended to cases where noise and other objects exist. Based on the length estimation algorithm, we propose a new algorithm for the detection of convex polygons in a digital image. The method is tested in both synthetic and real images and gives very satisfactory results. We also prove the uniqueness of the representation of a convex polygon from the peaks it gives in the Hough (parameter) space. Finally, we propose an efficient algorithm for the construction of a convex polygon from the parameters of its edges.