  Traditional approaches to line segment detection typically involve perceptual
grouping in the image domain and/or global accumulation in the Hough domain.
Here we propose a probabilistic algorithm that merges the advantages of both
approaches. In a first stage lines are detected using a global probabilistic
Hough approach. In the second stage each detected line is analyzed in the image
domain to localize the line segments that generated the peak in the Hough map.
By limiting search to a line, the distribution of segments over the sequence of
points on the line can be modeled as a Markov chain, and a probabilistically
optimal labelling can be computed exactly using a standard dynamic programming
algorithm, in linear time. The Markov assumption also leads to an intuitive
ranking method that uses the local marginal posterior probabilities to estimate
the expected number of correctly labelled points on a segment. To assess the
resulting Markov Chain Marginal Line Segment Detector (MCMLSD) we develop and
apply a novel quantitative evaluation methodology that controls for under- and
over-segmentation. Evaluation on the YorkUrbanDB and Wireframe datasets shows
that the proposed MCMLSD method outperforms prior traditional approaches, as
well as more recent deep learning methods.
