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