MCMLSD: A dynamic programming approach to line segment detection
This project page provides code for line segment detection and evaluation. If you use either, please cite:
Almazen, E.J., Tal, R., Qian, Y. & Elder, J.H. (2017) MCMLSD: A dynamic programming approach to line segment detection. IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2031-2039.
For enquiries, please contact James Elder at jelder@yorku.ca
The MCMLSD Algorithm
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.
Evaluation
We compare against three competing state-of-the-art detectors. Each detector returns a ranked list of segments. Ground truth and detector segments sampled uniformly at 1-pixel resolution. Enforcing bipartite match at segment level ensures appropriate penalty for under- and over-segmentation.
2-Step association between ground truth and detector output:
- Point Match: Greedy bipartite match between ground truth and detector points within 2.8-pixel radius.
- Segment Match: Optimal bipartite match between ground truth and detector segments, maximizing total number of matched points
We assume that the line segment detector under evaluation returns a list of line segments in ranked order. We sample each ground truth and detector segment uniformly with a sample spacing of one pixel and use these point samples to evaluate the detector as a function of the number k of top-ranked segments selected, varying k from 10 to 500. For each value of k we first identify potential point matches as those (ground truth, detector) point pairs lying within a threshold distance of 2.8 pixels of each other. This threshold was selected to associate any pair of lines that could potentially appear in the image with less than a one-pixel intervening gap. We then sort these candidate matches by Euclidean distance and accept matches in greedy fashion starting with the smallest distance, matching each point at most once, and thus arriving at a near-optimal bipartite match. Having associated ground truth and detector points, we employ the Hungarian algorithm [37] to identify the optimal bipartite match between ground truth and detector segments that maximizes the total number of points matched. Now that we have a 1:1 association between ground truth and detector segments, it remains to evaluate the quality of this association. We employ three evaluative measures.
1. Recall as a Function of the Number of Segments
2. Recall as a Function of Total Segment Length
3. Precision-Recall
Quantitative Results on the YorkUrbanDB
Quantitative Results on Wireframe
Quantitative Results on Linelet-YorkUrbanDB
Qualitative Results
