# CVRS Lab

项目

# CannyLines: A Parameter-Free Line Segment Detector

CannyLines: A Parameter-Free Line Segment Detector,,2015-2016

**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** **http://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.**

*CannyPF*

*CannyLines*

**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.**

*CannyLines*

*Edge map extraction*

*CannyPF*

*Edge linking and splitting*

*Line segments extending and merging*

*Line validation*

*CannyPF*

**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***.**

*CannyLines*

*λv*

*λv*

*λv*

*λv*

*λv*

*θs*

*lmin*

*θs*

*= lmin/2*

*lmin/4*

*lmin*

*θm*

*θm=2 × tan(2/lmin)*

*lmin*

*θm*

*θv*

*θv*

*θ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.OriginalCannyPFCannySR-EdgeMapCannySRPF-EdgeMapED-EdgeMapEDPF-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%**

*CannyPF*

*YorkUrbanDB*

*p =Σk*

*N(Lk)/Σk|Lk|*

*|Lk|*

*Lk*

*N(Lk)*

*Lk*

*CannyPF*

*CannyPF*

**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.**

*CannyLines*

*L*

*L/N*

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

Image InfoLSDEDLinesCannyLinesSceneNLL/NNLL/NNLL/NIn

Door186430614.9**35.4**74827631.2**36.9**64226589.3**41.4**253021545.4**40.7**44419647.3**44.3**39719965.5**50.3**346916539.6**35.3**40715869.3**39.0**44317738.3**40.0**421512302.2**57.2**17012027.1**70.7**20314351.4**70.7**562719500.9**31.1**57718271.4**31.7**48518063.2**37.2**Out

Door182322023.8**26.8**59118464.2**31.2**63321181.7**33.5**256214753.8**26.3**49915680.7**31.4**48415590.7**32.2**32668981.9**33.8**2578928.0**34.7**2709251.7**34.3**447112900.4**27.4**41610610.9**25.5**32711819.3**36.1**534812425.9**35.7**32211180.7**34.7**31312228.3**39.1**

**Original**

**EDLines**

**LSD**

**CannyLines**

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