A simple and robust line detection algorithm based on small eigenvalue analysis

In this paper, a simple and robust algorithm is proposed for detecting straight line segments in an edge image. The proposed algorithm is based on small eigenvalue analysis. The statistical and geometrical properties of the small eigenvalue of the covariance matrix of a set of edge pixels over a connected region of support are explored for the purpose of straight line detection. The approach scans an input edge image from the top left corner to the bottom right corner with a moving mask of size k x k for some odd integer k > 1. At every stage, the small eigenvalue of the covariance matrix of the edge pixels covered by the mask and connected to the center pixel of the mask is computed. These pixels are said to be linear edge pixels if the computed small eigenvalue is less than a pre-defined threshold value. Several experiments have been conducted on various images with considerable background noise and also with significant edge point location errors to reveal the efficacy of the proposed model. The results of the experiments emphasize that the proposed model outperforms other models specifically the Hough transform and its variants in addition to being robust to image transformations such as rotation, scaling and translation. (C) 2003 Elsevier B.V. All rights reserved.