CannyLines: A Parameter-Free Line Segment Detector


Xiaohu Lu, Jian Yao*, Kai Li, and Li Li

School of Remote Sensing and Information Engineering, Wuhan University, Wuhan, Hubei, P.R.China

*EMail: jian.yao@whu.edu.cn

*Web: http://www.scholat.com/jianyao https://cvrs.whu.edu.cn


[] The source codes are released.download (13/4/2016).

[] The executable files are released.download (15/1/2015).

[] The test dataset is added.download (15/1/2015).


1. Abstract

In this paper, we present a robust line segment detection algorithm to efficiently detect the line segments from an input image. Firstly a parameter-free Canny operator, named as CannyPF, is proposed to robustly extract the edge map from an input image by adaptively setting the low and high thresholds for the traditional Canny operator. Secondly, both efficient pixels linking and splitting techniques are proposed to collect collinear point clusters directly from the edge map, which are used to fit the initial line segments based on the least-square fitting method. Thirdly, longer and more complete line segments are produced via efficient extending and merging. Finally, all the detected line segments are validated due to the Helmholtz principle in which both the gradient orientation and magnitude information are considered. Experimental results on a set of representative images illustrate that our proposed line segment detector, named as CannyLines, can extract more meaningful line segments than two popularly used line segment detectors, LSD and EDLines, especially on the man-made scenes.

2. Algorithm

Given a grayscale image, the proposed CannyLines algorithm detects line segments via the following four steps: (1) Edge map extraction. A parameter-free Canny edge detector, named as CannyPF, is proposed to extract the edge map from an input image, which can self-adaptively adjust the low and high thresholds of the Canny operator based on the gradient magnitude of the input image, and which can ensure the completeness of the image's structure information. (2) Edge linking and splitting. Starting from the edge pixel with the greatest gradient magnitude, the linking process collects pixels on the edge map with a direction control. Therefore, an efficient splitting process is conducted to get short initial line segments. (3) Line segments extending and merging. The line segments are extended in both directions to collect more edge pixels and merged with other collinear line segments around. (4) Line validation. A novel line validation method based on the Helmholtz principle combining both gradient orientation and magnitude information is proposed to verify each line segment.

The proposed line segment detector (CannyLine) which extracts line segments based on an edge map obtained by applying a parameterfree Canny operator with the following contributions:

  • A parameter-free Canny operator, named as CannyPF, which adaptively chooses the low and high thresholds of the Canny operator for the input image by applying the Helmholtz Principle on the edge detection;
  • A line segment detector, which extracts the line segments directly based on edge map instead of edge segments;
  • A more reasonable validation step, which uses both the gradient orientation and magnitude information to verify each line segment.

3. Experimental Results

3.1. Internal Parameters

The proposed line segment detector CannyLines is parameter-free because all the parameters related to the input image are determined by the image itself, while other parameters can be set the same for all the images, which are discussed as follows:

(1) λv for edge detection, which denotes the lower limit of a gradient magnitude that is sufficient enough to be noticed in vision. Actually, it is difficult to give an accurate value of λv directly, so we tested different values of λv on a large amount of images captured from different scenes, and found that λv=70 is a good balance of completeness and cleanliness. Without the use of λv, the line segments detection result represents the image directly in probability, which may lead to false positives (see the up-right picture in Fig.1) in the high contrast image and false negatives (see the down-right figure in Fig.1) in the low contrast image.

(2) θs for edge segment splitting, which represents the minimal length of an edge segment to be considered for splitting and equals twice of the possibly shortest edge segment. For an image with a certain size, the minimal meaningful length lmin is decided in probability, so we set θs = lmin/2 which means that the length of the shortest edge segment splitting is lmin/4. For most images the value of lmin approximately equals 12, thus the length of the shortest edge segment is 3.

(3) θm for line segment merging, which is the maximal direction deviation tolerance of two close-direction line segments to be considered for merging. We simply set θm=2 × tan(2/lmin), which can be explained based on the fact that the two close-direction line segments with the length lmin and with 1-pixel deviation of all their endpoints will be considered for merging. The θm is used to quickly exclude the line segments that can't be merged.

   
   

Fig. 1. False detection without θv. First column: line detection result with θv; Second column: false line detection result without θv.

3.2. Evaluation on CannyPF

the good edge detection map extracted from the input image. To quantitatively evaluate the effectiveness of the proposed parameterfree Canny edge detector CannyPF , we tested it on the YorkUrbanDB database , which contains a series of images of man-made buildings and the corresponding ground-truth line segments of each image. Ten indoor images and ten outdoor images were chosen to evaluate the precisions of CannyPF and the following four edge detection methods: CannySR, CannySRPF, ED, and EDPF, the codes of which are obtained from the Edge Drawing library. Let E is the binary edge map obtained by applying an edge detector on the input image I. Based on the assumption that one pixel of a ground-truth line segment of I can be identified when there exists edge point(s) of E in its eight neighborhood, the precision p of an edge detector on an input image I was defined as p =Σk N(Lk)/Σk|Lk| where |Lk| denotes the length or size of the ground-truth line segment Lk in I and N(Lk) denotes the number of edge points in Lk successfully identified in E. Fig. 2 shows the edge detection results on the indoor and outdoor scene images, from which we can observe that CannyPF extracted more ground-truth edge pixels than other edge detectors either in indoor or in outdoor scene images, over which the average precision of the proposed CannyPF edge detector is 90.9%, which is obviously higher than 86.7% of ED and 85.9% of EDPF.

The edge detection results of those five detectors is shown in Fig. 3. For better interpreting of these results, please click the figures to view the original figures.


Fig. 2. Different edge detector’s precisions: (a) Indoor scenes result;(b) Outdoor scenes result.

Original CannyPF CannySR-EdgeMap CannySRPF-EdgeMap ED-EdgeMap EDPF-EdgeMap
image CannyPF CannySR-EdgeMap CannySRPF-EdgeMap ED-EdgeMap EDPF-EdgeMap
P=89.6% P=79.4% P=86.8% P=85.9% P=87.3%
P=90.8% P=74.9% P=88.0% P=84.9% P=87.2%
P=86.6% P=80.2% P=82.8% P=83.0% P=83.2%
P=88.0% P=82.1% P=87.2% P=86.5% P=86.7%
P=91.2% P=70.7% P=90.8% P=86.6% P=91.1%
P=94.2% P=85.3% P=88.3% P=89.2% P=87.7%
P=96.2% P=67.4% P=86.9% P=77.8% P=83.5%
P=93.0% P=69.4% P=87.1% P=85.4% P=87.1%
P=92.0% P=87.5% P=83.7% P=91.0% P=82.8%
P=94.2% P=84.7% P=88.0% P=87.7% P=88.5%

Fig. 3. Edge detection results of different edge detectors.

3.3. Evaluation on CannyLines

To evaluate the performance of the proposed line segment detector CannyLines, 5 indoor images and 5 outdoor ones were chosen from the tested images used in Section 3.2. Table 1 shows the statistical results of LSD, EDLines and CannyLines. As the amount of detected line segments can not reflect the effectiveness of a line segment detector very well, we use the average length of line segments to indicate the ability of different detectors. From Table 1, we can observe that on most images, the total line length L of the proposed CannyLines detector is longer than those of EDLines and close to those of LSD, and the average line length L/N is longer than those of LSD and EDLines, which means that the proposed CannyLines detector generated more meaningful line segments than LSD and EDLines generally.

The line detection results of those three line segment detectors is shown in Fig. 4. For better interpreting of these results, please click the figures to view the original figures.

Table 1. Line segments detection results of LSD, EDLines and the proposed method.
 

Image Info LSD EDLines CannyLines
Scene N L L/N N L L/N N L L/N
In
Door
1 864 30614.9 35.4 748 27631.2 36.9 642 26589.3 41.4
2 530 21545.4 40.7 444 19647.3 44.3 397 19965.5 50.3
3 469 16539.6 35.3 407 15869.3 39.0 443 17738.3 40.0
4 215 12302.2 57.2 170 12027.1 70.7 203 14351.4 70.7
5 627 19500.9 31.1 577 18271.4 31.7 485 18063.2 37.2
Out
Door
1 823 22023.8 26.8 591 18464.2 31.2 633 21181.7 33.5
2 562 14753.8 26.3 499 15680.7 31.4 484 15590.7 32.2
3 266 8981.9 33.8 257 8928.0 34.7 270 9251.7 34.3
4 471 12900.4 27.4 416 10610.9 25.5 327 11819.3 36.1
5 348 12425.9 35.7 322 11180.7 34.7 313 12228.3 39.1

Original

EDLines

LSD

CannyLines

Lines:482, Average Line Length:29.0 Lines:462, Average Line Length:29.7 Lines:336, Average Line Length:36.6
Lines:152, Average Line Length:17.3 Lines:119, Average Line Length:22.9 Lines:89, Average Line Length:31.7
Lines:401, Average Line Length:22.6 Lines:371, Average Line Length:25.6 Lines:296, Average Line Length:26.3
Lines:257, Average Line Length:49.3 Lines:219, Average Line Length:52.8 Lines:230, Average Line Length:56.2
Lines:530, Average Line Length:40.7 Lines:444, Average Line Length:44.3 Lines:397, Average Line Length:50.3
Lines:469, Average Line Length:35.3 Lines:407, Average Line Length:39.0 Lines:443, Average Line Length:40.0
Lines:726, Average Line Length:34.4 Lines:687, Average Line Length:33.9 Lines:459, Average Line Length:45.6
Lines:471, Average Line Length:27.4 Lines:416, Average Line Length:25.5 Lines:327, Average Line Length:36.1
Lines:883, Average Line Length:33.4 Lines:786, Average Line Length:35.9 Lines:619, Average Line Length:41.8
Lines:348, Average Line Length:35.7 Lines:322, Average Line Length:34.7 Lines:313, Average Line Length:39.1

Fig. 4. Line segments detection results of different line segment detectors.

Dataset and Codes

1. CannyPF:     [Win64][Win32]
    CannyLines: [Win64][Win32]

2. Source codes:  [CannyPF][CannyLines]

3. Test dataset: [Indoor Dataset][Outdoor Dataset]

Citation

Xiaohu Lu, Jian Yao*, Kai Li, and Li Li. CannyLines: A Parameter-Free Line Segment Detector, IEEE International Conference on Image Processing (ICIP), 2015.