Real-time line detection through an improved Hough transform voting scheme

• Published in: Pattern recognition 2008, Vol.41 (1), p.299-314
• Main Authors: Fernandes, Leandro A.F., Oliveira, Manuel M.
• Format: Article
• Language: English
• Subjects: Applied sciences; Collinear points; Exact sciences and technology; Hough transformation; Image processing; Information, signal and communications theory; Pattern recognition; Real-time line detection; Signal processing; Telecommunications and information theory
• ISSN: 0031-3203; 1873-5142
• DOI: 10.1016/j.patcog.2007.04.003

The Hough transform (HT) is a popular tool for line detection due to its robustness to noise and missing data. However, the computational cost associated to its voting scheme has prevented software implementations to achieve real-time performance, except for very small images. Many dedicated hardware designs have been proposed, but such architectures restrict the image sizes they can handle. We present an improved voting scheme for the HT that allows a software implementation to achieve real-time performance even on relatively large images. Our approach operates on clusters of approximately collinear pixels. For each cluster, votes are cast using an oriented elliptical-Gaussian kernel that models the uncertainty associated with the best-fitting line with respect to the corresponding cluster. The proposed approach not only significantly improves the performance of the voting scheme, but also produces a much cleaner voting map and makes the transform more robust to the detection of spurious lines.