An efficient line detection algorithm based on a new combinational optimization formulation

In this paper we present a new algorithm for detecting lines in digital images. The algorithm is based on a general combinatorial optimization approach for estimating piecewise linear models that we introduced in Mattavelli and Amaldi. A linear system is constructed with the coordinates of all contour points in the image as coefficients and the parameters of the line as unknowns. The resulting linear system is then partitioned into a close-to-minimum number of consistent subsystems using a greedy strategy based on a thermal variant of the perceptron algorithm. While the partition into consistent subsystems yields the classification of the corresponding image points into a close-to-minimum number of lines, the solution of each subsystem provides the parameters of the line. An extensive comparison with the standard Hough transform and the randomized Hough transform shows the consistent advantages of our combinatorial optimization approach in terms of memory requirements, computational complexity, robustness with respect to noise, and quality of the solution independently from parameter settings