Variants for the Hough transform for line detection

This paper deals with the problem of detecting every line component, a set of edge points close enough to some line, in an N x N digital image. For this purpose, the Hough transform, which is based on voting in the dual plane, is widely used. However, there have been few theoretical studies on the relationship between its computational complexity and ability of detecting straight line components. In this paper we present two different algorithms for detecting every line component contained in a digital image. The one, which is effective in the case of a dense digital image, is based on a new transformation named L(1)-dual transform defined by the L(1)-distance between points and lines. Using concepts from number theory we can show that this algorithm finds every line component in O(N-4) time, where the size of the image is O(N-2). The other, which is effective when the edge density is low, attains efficiency by using the plane sweep technique common in computational geometry. Furthermore, we present an efficient approximation algorithm which can detect at least alpha x 100% of any line component and show that its computational complexity depends on the value of alpha. Choosing alpha = 0.5, for example, the time complexity of the algorithm is reduced from O(N-4) to O(N-3 log N). In practical-applications it is sometimes required to detect line components of width greater than one. We also present an algorithm for detecting such bold lines of specified width in the same computational complexity as above.