LSM: Perceptually Accurate Line Segment Merging

Naila Hamid, Nazar Khan {naila.hamid,nazarkhan}@pucit.edu.pk

Computer Vision & Machine Learning Group,

Punjab University College of Information Technology (PUCIT),

Old Campus, The Mall Road, Lahore, Pakistan

Abstract

Existing line segment detectors tend to break up perceptually distinct line segments into multiple segments. We propose an algorithm for merging such broken segments to recover the original perceptually accurate line segments. The algorithm proceeds by grouping line segments on the basis of angular and spatial proximity. Then those line segment pairs within each group that satisfy novel, adaptive mergeability criteria are successively merged to form a single line segment. This process is repeated until no more line segments can be merged. We also propose a method for quantitative comparison of line segment detection algorithms. Results on the York Urban dataset show that our merged line segments are closer to human-marked ground-truth line segments compared to state-of-the-art line segment detection algorithms.

Keywords: line segments, line segment detection, line detection, grouping, merging, spatial proximity, angular proximity, perception, Gestalt, perceptually accurate line segments, quantitative evaluation

Methodology:

Our algorithm takes as input an image and line segments detected by an off-the-shelf line segment detector. The merging pipeline has two main steps. In the first step, we group line segments based on traditional measures of spatial and angular proximity:

1.      Spatial proximity: Line segments must be spatially close enough to be grouped.

2.      Angular proximity: Orientation of line segments should not be much different from each other.

 

 

 

This demonstrates visual inspection and some of the weaknesses of a line segment detector on {Top Left}: a real world fence image. {Top Right}: The fence image contains 24 straight line segments that can be identified via visual inspection. {Middle Left}: Line segment detectors will detect 48 segments for 24 visual line segments due to gradient change on both sides of each segment. {Middle Right}: Similarly the 7 intersections in the fence can be represented by 14 curved segments (2 curved segments per intersection). {Bottom Left}: 14 curved segments yield 28 straight line segments (2 segments per curved segment). {Bottom Right}: Therefore, a good line segment detector should detect 76 line segments on the fence image.

 

Visualization of the merging steps of LSM Algorithm. {Top Left}: Line segments detected by LSD on the fence image. {Top Right}: A selected line segment (thick blue). {Middle Left}: Angular proximal line segments w.r.t selected blue line (thick green). {Middle Right}: Angular as well as spatial proximal line segments (thick green). {Bottom Left}: A segment selected from angular and spatial proximal group of line segments (thick green). {Bottom Right}: A line segment obtained by merging two segments (thick blue).

 

In the second step, we consider pairs of line segments within every group and merge them into a single line segment if they satisfy our mergeability criteria. These two steps are repeated until no more line segments can be merged. The process is explained in the figures below:

 

 

Perception of mergeability. Each case has two merging scenarios -- one is closer to perception and the other is not. Longer line segment is in blue. Potential candidates for merging with blue are the red and green segments (both dashed and solid). Merged segments are transparent -- red is closer to perception than green. {Top}: Despite having the same spatial and angular proximity as the green segment, the red dashed segment is perceptually closer to the blue one. Due to the shorter length of the red segment, the eventual merged segment is closer to the blue one. {Middle}: Despite having the same length and spatial proximity as the green segment, the red dashed segment is perceptually closer to the blue one. Due to greater angular proximity of the red segment, the eventual merged segment is closer to the blue segment. {Bottom}: Despite having the same spatial and angular proximity as the dashed pair, the solid pair is perceptually closer. The perceptual difference is due to the relative lengths of the longer segments in the two pairs. Therefore, perceptual mergeability is inversely proportional to length of shorter segment, angular difference and relative spatial distance and proportional to length of the longer segment.

 

The four possible merging scenarios for a pair of line segments and their merged results. All line pair configurations can be modeled as one of these 4 scenarios. The plus and minus signs indicate on which side of the origin does a projection fall. They indicate overlap between the two line segments. The end points of the merged line are marked with black circles.

 

Quantitative Evaluation Criterion:

Due to the human brain's ability to fill gaps and insert missing information, qualitative evaluation of line detection algorithms is not sufficient. The output of line segment detectors appears better than it actually is because our brain automatically introduces order where there is little or no order. It connects together or fills in the broken line segments. This can be evidenced by looking at line segments detected by the LSD and EDLines algorithms whose weaknesses can often be observed only by zooming into the image. Due to the absence of a standard benchmark dataset with ground-truth line segments, many line segment extractors analyse their results on synthetic images while results on real images are open to subjective, visual evaluation. Therefore, we propose a method for quantitative comparison of line segment detection algorithms. Details can be seen in the paper.

Results:

We have already demonstrated before that a good line segment detector should detect 76 line segments on the fence image. The state-of-the-art LSD algorithm detects 97 line segments instead of 76 line segments shown in figure below. It detects more line segments because it tends to break up perceptually coherent segments. Our merging process applied on the LSD output merges these segments to obtain the original 76 perceptually accurate line segments.

Another comparison is shown with a synthetic image of a checkerboard. LSD and EDLines break line segments at each intersection and our algorithm merges all the broken intersections thus yielding 14 perceptually accurate line segments.

 

 

 

Merging LSD output. {Top}: 97 line segments detected by the LSD algorithm on the fence image. Bottom: After merging LSD segments by our algorithm, only 76 perceptually accurate segments remain.

Merging LSD and EDLines output. {Top Left}: A synthetic image of a checkerboard containing 14 line segments that can be identified via visual inspection. Line segment detectors that break segments at intersections should detect 68 segments that can also be identified via visual inspection. {Top Right}: LSD detects 68 and {Bottom Left}: EDLines detects 62 line segments. {Bottom Right}: After merging LSD result by our algorithm, the original 14 line segments are recovered. Merging EDLines result also yields the same 14 line segments.

 

LSD and merged LSD results. {Top row}: York Urban dataset images. {Middle row}: LSD results. The red rectangles highlight the weakness of LSD that it breaks perceptually contiguous linear structures. {Bottom row}: Merging applied on LSD results. Areas corresponding to the red rectangles demonstrate merged segments that are more consistent with human perception.

 

Downloadables:

Naila Hamid, Nazar Khan, “LSM: perceptually accurate line segment merging,” J. Electron. Imaging 25(6), 061620 (2016), doi: 10.1117/1.JEI.25.6.061620.

Copyright 2016 Society of Photo-Optical Instrumentation Engineers. One print or electronic copy may be made for personal use only. Systematic reproduction and distribution, duplication of any material in this paper for a fee or for commercial purposes, or modification of the content of the paper are prohibited. 

Paper PDF, Code