CannyLines: A Parameter-Free Line Segment Detector

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 l_min is decided in probability, so we set θ_s = l_min/2 which means that the length of the shortest edge segment splitting is l_min/4. For most images the value of l_min 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/l_min), which can be explained based on the fact that the two close-direction line segments with the length l_min 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(L_k)/Σ_k|L_k| where |L_k| denotes the length or size of the ground-truth line segment L_k in I and N(L_k) denotes the number of edge points in L_k 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
	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.
 

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]