Mean shift based clustering of Hough domain for fast line segment detection

This paper proposes a new algorithm for extracting line segments from edge images. Basically, the method performs two consecutive stages. In the first stage, the algorithm follows a line segment random window randomized Hough transform (RWRHT) based approach. This approach provides a mechanism for finding more favorable line segments from a global point of view. In our case, the RWRHT based approach is used to actualise an accurate Hough parameter space. In the second stage, items of this parameter space are unsupervisedly clustered in a set of classes using a variable bandwidth mean shift algorithm. Cluster modes provided by this algorithm constitute a set of base lines. Thus, clustering process allows using accurate Hough parameters and, however, detecting only one line when pixels along it are not exactly collinear. Edge pixels lying on the lines grouped to generate each base line are projected onto this base line. A fast and purely local grouping algorithm is employed to merge points along each base line into line segments. We have performed several experiments to compare the performance of our method with that of other methods. Experimental results show that the performance of the proposed method is very high in terms of line segment detection ability and execution time. (c) 2005 Elsevier B.V. All rights reserved.