zbMATH — the first resource for mathematics

Fast line detection algorithms based on combinatorial optimization. (English) Zbl 0986.68538
Arcelli, Carlo (ed.) et al., Visual form 2001. 4th international workshop, IWVF4, Capri, Italy, May 28-30, 2001. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 2059, 410-419 (2001).
Summary: In this paper we present a new class of algorithms for detecting lines in digital images. The approach is based on a general formulation of a combinatorial optimization problem. It aims at estimating piecewise linear models. A linear system is constructed with the coordinates of all contour points in the image as coefficients and the line parameters 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. A comparison with the standard Hough Transform and the Randomized Hough Transform shows the considerable advantages of our combinatorial optimization approach in terms of memory requirements, time complexity, robustness with respect to noise, possibility of introducing “a priori” knowledge, and quality of the solutions regardless of the algorithm parameter settings.
For the entire collection see [Zbl 0967.00074].

68T45 Machine vision and scene understanding
90C27 Combinatorial optimization