Click on the above“Visual Learning for Beginners” to selectStar or “Pin”
Important content delivered first time.1. Scene Requirements
In the field of computer vision, we often need to perform some special tasks, and line detection algorithms are frequently used in tasks such as lane detection, length measurement, etc. Although line detection tasks seem relatively simple, you will find that there is still significant room for optimization during specific applications. This article summarizes some commonly used classic line detection algorithms.
2. Hough_line Line Detection Algorithm
The Hough transform is a well-known computer vision processing algorithm that can be used for many tasks, commonly including line detection, circle detection, ellipse detection, etc. Below we will perform a brief analysis of this algorithm and provide practical code examples.
2.1 Hough_line Implementation Steps
Step 1 – First, it creates a two-dimensional array or accumulator (to save the values of the two parameters) and initializes it to zero;
Step 2 – Use r to represent rows and θ to represent columns;
Step 3 – The size of the array depends on the precision you need. Assuming you want an angle precision of 1 degree, you will need 180 columns (the maximum degree of a line is 180);
Step 4 – For r, the maximum possible distance is the diagonal length of the image. Therefore, taking pixel precision, the number of rows can be the diagonal length of the image.
2.2 Hough_line Code Implementation
2.3 Effect Display and Analysis
The above images show some of the line detection effects of the Hough_line algorithm. To verify the effectiveness of this algorithm, I selected three different challenging scenes: buildings, answer sheets, and doors. By observing the results above, we can see that the algorithm can basically detect the lines in the images, but the detection results are not very good, with many duplications and omissions. In addition, the biggest drawback of this algorithm is that it requires adjusting parameters based on the image. The key parameter is lines = cv2.HoughLines(edges,1,np.pi/180, 200); the larger the value set, the fewer lines will be detected in the image. You need to adjust according to your testing scenarios.
2.4 HoughP_line Code Implementation
HoughP_line is an improved version of the Hough_line algorithm, which has faster speed and better results.
2.5 Effect Display and Analysis
The above images show some of the line detection effects of the HoughP_line algorithm. The above results were calculated using the fixed parameter lines = cv2.HoughLinesP(edges,1,np.pi/180, 80, 30, 10). By observation, we can see that HoughLinesP is not only convenient to use but also requires little parameter adjustment; moreover, this algorithm can achieve better line detection results. Therefore, when you want to use the Hough line detection algorithm, it is recommended to prioritize using the HoughP_line algorithm.
3. LSD Line Detection Algorithm
LSD is an integrated line detection algorithm in OpenCV, which performs better than the Hough algorithm and has good detection speed, recommended for use.
3.1 Introduction to LSD Algorithm
The LSD fast line detection algorithm was proposed by Rafael Grompone, Jeremie Jackbowicz, and Jean-Michel Morel in the 2010 paper titled “LSD: a Line Segment Detector” published in PAMI. The time complexity of the LSD algorithm is lower than that of the Hough transform. The LSD algorithm detects line pixel sets through local analysis of the image, and then verifies and solves them using assumed parameters, merging the pixel sets with error control sets, thereby adaptively controlling the number of false detections. Generally, to detect lines in an image, the basic idea is to detect pixel sets with significant gradient changes, and the LSD algorithm utilizes gradient information and level lines for line detection.
3.2 LSD Code Implementation
3.3 Effect Display and Analysis
The above images show some of the line detection effects of the LSD algorithm. By observing the results above, we can see that this algorithm’s detection results far exceed those of the Hough and HoughP algorithms; furthermore, the above detection results were executed using the default parameters of the LSD algorithm. If specific parameters are adjusted, even better results can be achieved, which often leads to unexpected outcomes when the default parameters are fine-tuned based on specific requirements.
The above image displays some hyperparameters of the LSD line detection algorithm. For specific details, please refer to the link. It should be noted that this algorithm has three different modes, as shown in the figure below. By default, mode 2 (i.e., 1) is used, but through testing, I found that mode 1 (i.e., 0) usually outputs better results. Specific situations need to be analyzed based on your scene.
4. FLD Line Detection Algorithm
4.1 Introduction to FLD Algorithm
The FLD line detection algorithm was introduced in this paper, which attempts to use line features to replace the original SURF point features for building recognition. Compared to point features, line features are easier to discover and have better robustness, and are generally unaffected by lighting, occlusion, or perspective changes. The following shows the line detection effects of this algorithm, from which we can see that line features perform better than point features.
4.2 FLD Algorithm Code Implementation
The above images show the detection effects of the FLD line detection algorithm. By observation, we can see that this algorithm has very good detection effects and can basically detect all the lines in the images, similar to the performance of LSD. The specific algorithm to use should be chosen based on your application scenario.
5. EDlines Line Detection Algorithm
5.1 Introduction to EDlines Algorithm
The EDlines line detection algorithm was proposed in this paper. This paper presents a fast, parameter-free line segment detector named EDLines (Akinlar and Topal, 2011), which produces powerful and accurate results, faster than the fastest known line segment detectors by up to 11 times; in other words, it is faster than the LSD by Grompone von Gioi et al. (2008a,b, 2010). Our detector also includes a line verification step based on the Helmholtz principle (Desolneux et al., 2008), which helps control the number of false detections. The results obtained by EDLines are very similar to those of LSD, capturing all major line segments with very few false positives. Furthermore, EDLines runs in real-time at a dazzling speed of 9.45 milliseconds, about 10 times faster than LSD for a given image.
5.2 EDlines Algorithm Implementation Steps
Step 1 – First, given a grayscale image, run the new edge detection and edge drawing (ED) algorithm to produce a clean set of pixel-adjacent chains, referred to as edges. Edge line segments intuitively reflect the boundaries of objects.
Step 2 – Then, utilize the line degree criterion, i.e., the least squares line fitting method, to extract line segments from the generated pixel chains.
Step 3 – Finally, the line verification step based on the Helmholtz principle (Desolneux et al., 2008; Grompone von Gioi et al., 2008a) is used to eliminate false line segment detections.
The above images show the detection effects of the EDlines line detection algorithm. By observing the above, we can conclude: 1) This algorithm can achieve detection results similar to LSD; 2) This algorithm suppresses some small false detections; 3) This algorithm has a faster running speed, about 10 times that of LSD.
6. LSWMS Line Detection Algorithm
6.1 Introduction to LSWMS Algorithm
LSWMS is a line detection algorithm. This paper introduces an accurate and real-time line detection method. Previous line detection methods did not utilize prior knowledge of the image scene, thus not requiring fine-tuning of input parameters. This algorithm strikes a balance between detection accuracy and speed, employing an efficient sampling method for accelerated processing. Then, it uses a fast line growth algorithm based on the Bresenham algorithm to provide accurate line segments while remaining robust against noise. The performance of this strategy was tested on a variety of images, and the results were compared with popular state-of-the-art line segment detection methods. The results indicate that our proposal outperforms these works while considering both results and processing speed.
The above image shows the results from the LSWMS paper. Since the code provided by the authors needs to be compiled under Ubuntu, I did not perform this work. If you are interested, you can run it on the three test images in this article.
7. CannyLines Line Detection Algorithm
7.1 Introduction to CannyLines Algorithm
The CannyLines algorithm was proposed in this paper. This paper presents a robust line segment detection algorithm that effectively detects line segments in the input image. First, a parameter-free Canny operator (cannypf) is proposed, which adaptively sets the low and high thresholds of the traditional Canny operator to robustly extract edge maps from the input image. Secondly, effective pixel connection and segmentation techniques are proposed to extract collinear point clusters directly from the edge map, and initial line segments are fitted based on the least squares method. Thirdly, longer and more complete line segments are generated through effective expansion and merging. Finally, all detected line segments are verified based on the Helmholtz principle, which considers both gradient direction and magnitude information. Experimental results on a representative set of images show that compared to two commonly used line segment detectors (LSD and EDline), our proposed CannyLine segment detector can extract more meaningful line segments, especially in artificial scenes.
The above images show the detection effects of the CannyLines line detection algorithm. By observing the above, we can see that this algorithm can achieve more accurate detection results with fewer false detections. This algorithm mainly improves the effectiveness of edge detection, and the specific effects are as follows:
8. MCMLSD Line Detection Algorithm
8.1 Introduction to MCMLSD Algorithm
The MCMLSD algorithm comes from this paper. The paper proposes a probabilistic algorithm that integrates the advantages of both. In the first stage, a global probabilistic Hough method is used. In the second stage, each detected line in the image domain is analyzed to locate the line segments that generate peaks in the Hough space. By limiting the search to a straight line, the distribution of points along the line segments can be modeled as a Markov chain, and the probability-optimal labeling of points correctly marked on the line segments is accurately computed using standard dynamic programming algorithms in linear time. The Markov assumption also produces an intuitive ranking method that uses the estimated expected value of the marginal posterior probability of points correctly labeled on the line segments. We developed and applied a new quantitative method to evaluate the resulting Markov chain edge line segment detector (mcmlsd) to control under-segmentation and over-segmentation. Evaluation results on the YorkUrbanDB dataset indicate that the proposed MCMLSD method significantly outperforms the state-of-the-art.
The above images show the detection effects of the MCMLSD algorithm. By observing the results above, we can see that this algorithm achieves good detection results; however, the downside is that the running speed of this algorithm is relatively slow, which may also be related to the MATLAB code.
9. LSM Line Detection Algorithm
9.1 Introduction to LSM Algorithm
The LSM algorithm is not only a line detection algorithm but also a line merging algorithm. The paper proposes an algorithm for merging these broken line segments to recover the originally perceived accurate segments. This algorithm groups line segments based on angle and spatial proximity. Then, line segments in each group that meet new adaptive merging criteria are sequentially merged into one line segment. This process is repeated until no line segments can be merged. We also propose a method for quantitatively comparing line segment detection algorithms. Results on the York-urban dataset indicate that our merging line segments are closer to human-labeled ground truth line segments compared to the latest line segment detection algorithms.
The above images show the detection effects of the LSM line detection algorithm. The left column represents the detection results of LSD, while the right column represents the optimization effects of the LSM algorithm. Different colors indicate different lines. By observing the above, we can see that LSM can merge some discontinuous lines into a longer line, which is very useful in real-world scenarios; however, we also find that the LSM algorithm may incorrectly merge some lines, leading to some errors.
10. Summary
This article summarizes and analyzes several classic line detection algorithms. For the task of line detection, it has many applications in real-world scenarios. Depending on your specific scene, you can choose a suitable line detection algorithm from this article according to your needs. If your scene is relatively simple, the HoughP_line algorithm may meet your requirements; if you have requirements for both speed and accuracy, you can choose to use EDlines; if you need to obtain the longest possible line, it is recommended to use the LSM line detection algorithm. In summary, the algorithm that best fits your scenario is the best algorithm.
Download 1: OpenCV-Contrib Extension Module Chinese Tutorial
Reply "Extension Module Chinese Tutorial" in the "Visual Learning for Beginners" public account to download the first Chinese version of the OpenCV extension module tutorial available online, covering installation of extension modules, SFM algorithms, stereo vision, target tracking, biological vision, super-resolution processing, and more than twenty chapters of content.
Download 2: 52 Lectures on Python Visual Practical Projects
Reply "Python Visual Practical Projects" in the "Visual Learning for Beginners" public account to download 31 visual practical projects including image segmentation, mask detection, lane line detection, vehicle counting, eyeliner application, license plate recognition, character recognition, emotion detection, text content extraction, facial recognition, etc., to help quickly learn computer vision.
Download 3: 20 Lectures on OpenCV Practical Projects
Reply "20 Lectures on OpenCV Practical Projects" in the "Visual Learning for Beginners" public account to download 20 practical projects based on OpenCV for advanced learning of OpenCV.
Group Chat
Welcome to join the reader group of the public account to exchange ideas with peers. Currently, there are WeChat groups for SLAM, 3D vision, sensors, autonomous driving, computational photography, detection, segmentation, recognition, medical imaging, GAN, algorithm competitions, etc. (will gradually be subdivided in the future). Please scan the WeChat ID below to join the group, with a note: "Nickname + School/Company + Research Direction", for example: "Zhang San + Shanghai Jiao Tong University + Visual SLAM". Please follow the format for the note; otherwise, you will not be approved. After successful addition, you will be invited into the relevant WeChat group based on your research direction. Please do not send advertisements in the group; otherwise, you will be removed from the group. Thank you for your understanding~