Click the "Xiaobai Learns Vision" above, select to add "Star" or "Top"
Heavy content delivered in real time
Editor | Jiang Dabai Author丨Technical Explorer @CSDN
Link丨https://blog.csdn.net/WZZ18191171661/article/details/101116949
1. Scene Requirements
In the field of computer vision, we often need to perform some special tasks, many of which involve line detection algorithms, such as lane line detection and length measurement. Although the task of line detection seems relatively simple, you will find that there is still a lot of room for optimization in the specific application process. This article summarizes some of the more classic line detection algorithms commonly used.
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, and ellipse detection. Below, we will conduct a simple analysis of this algorithm and perform a coding practical.2.1 Hough_line Implementation StepsStep 1 – First, it creates a two-dimensional array or accumulator (to save the values of 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 the line is 180);Step 4 – For r, the maximum possible distance is the length of the diagonal of the image. Therefore, taking a pixel precision, the number of rows can be the length of the diagonal of the image.2.2 Hough_line Code Practical
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 chose three different challenging scenes: buildings, answer sheets, and doors. By observing the above results, we can see that the algorithm can basically detect lines in the image, but the detection results are not very good, with many duplicates and missed detections. 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 this value is, the fewer lines will be detected in the image, and you need to adjust it according to your test scene.2.4 HoughP_line Code PracticalHoughP_line is an improved version of the Hough_line algorithm, with faster speed and better effects.
2.5 Effect Display and Analysis
The above images show some of the line detection effects of the HoughP_line algorithm. The results were calculated using lines = cv2.HoughLinesP(edges,1,np.pi/180, 80, 30, 10), and by observation we can find that HoughLinesP is not only convenient to use but also requires almost no parameter adjustment; in addition, this algorithm can achieve better line detection results. Therefore, when you want to use the Hough line detection algorithm, it is recommended to prioritize the HoughP_line algorithm.
3. LSD Line Detection Algorithm
LSD is a line detection algorithm integrated into OpenCV, which has better line detection effects than the Hough algorithm and has good detection speed, recommended for use.3.1 Introduction to LSD AlgorithmThe LSD fast line detection algorithm was proposed by Rafael Grompone, Jeremie Jackbowicz, and Jean-Michel Morel in a paper published in PAMI in 2010, which has a lower time complexity than the Hough transform. The LSD algorithm analyzes the image locally to obtain a set of pixel points of the line, and then verifies and solves it through assumed parameters, merging the pixel point set with the error control set to adaptively control the number of false detections. Generally speaking, to detect lines in an image, the basic idea is to detect the set of pixel points with significant gradient changes in the image. The LSD algorithm utilizes gradient information and level-line to perform line detection.3.2 LSD Code Practical
3.3 Effect Display and Analysis
The above images show some of the line detection effects of the LSD algorithm. By observing the above results, we can find that the detection results of this algorithm far exceed those of the Hough and HoughP algorithms; in addition, the above detection results were executed using the default parameters of the LSD algorithm, and if specific parameters are adjusted, better results can be achieved. This situation generally occurs when you perform fine-tuning of the default parameters for your specific requirement scenarios, which often yields unexpected results.
The above images show some hyperparameters of the LSD line detection algorithm, for specific details please see 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, and the specific situation needs to be analyzed based on your scenario.
4. FLD Line Detection Algorithm
4.1 Introduction to FLD AlgorithmThe FLD line detection algorithm was introduced in this paper, which attempted 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, as they are generally not affected by lighting, occlusion, or changes in perspective. The following shows the line detection effects of this algorithm, from which we can see that line features are better than point features.
4.2 FLD Algorithm Code Practical
4.3 Effect Display and Analysis
The above images show the detection effects of the FLD line detection algorithm. By observing, we can find that this algorithm has good detection effects, and can basically detect all lines in the image, similar to the performance of LSD. The specific algorithm to use needs to be chosen based on your application scenario.
5. EDlines Line Detection Algorithm
5.1 Introduction to EDlines AlgorithmThe 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 detector 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 from EDLines show that they are very similar to LSD, with all major line segments detected and very few false positives. In addition, 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 StepsStep 1 – First, given a grayscale image, run the new edge detection and edge drawing (ED) algorithm to produce a clean, pixel-adjacent chain, which we call edges. The edge line segments intuitively reflect the boundaries of the object.Step 2 – Then, using the line degree criterion, i.e., the least squares line fitting method, extract line segments from the generated pixel chain.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.
5.3 Effect Display and Analysis
The above images show the detection effects of the EDlines line detection algorithm. From the above observations, we can find: 1) This algorithm can obtain detection results similar to LSD; 2) This algorithm suppresses some small false detections of lines; 3) This algorithm has a faster running speed, about 10 times that of LSD.
6. LSWMS Line Detection Algorithm
6.1 Introduction to LSWMS AlgorithmLSWMS 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 eliminating the need for fine-tuning input parameters. This algorithm strikes a balance between detection accuracy and speed, using an efficient sampling method for accelerated processing and then utilizing a fast line growth algorithm based on the Bresenham algorithm with an improved mean-shift algorithm to provide accurate line segments while maintaining robustness against noise. The performance of this strategy was tested on a variety of images, and its 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 results from the LSWMS paper. Interested readers can run the effects on the three test images in this article.
7. CannyLines Line Detection Algorithm
7.1 Introduction to CannyLines AlgorithmThe 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 robustly extracts edge mapping from the input image by adaptively setting the low and high thresholds of the traditional canny operator. Second, effective pixel connection and segmentation techniques are proposed to directly extract collinear point clusters from the edge map, and the initial line segments are fitted based on the least squares method. Third, longer and more complete line segments are generated through effective expansion and merging. Finally, all detected line segments are verified according to the Helmholtz principle, which simultaneously considers gradient direction and magnitude information. Experimental results on a set of representative images show that our proposed cannyline line segment detector can extract more meaningful line segments compared to two commonly used line segment detectors, LSD and EDline, especially in artificial scenes.7.2 Effect Display and Analysis
The above images show the detection effects of the CannyLines line detection algorithm. By observing the above images, we can find that this algorithm can achieve more accurate detection results with fewer false detections. This algorithm mainly improves the edge detection effect, and the specific effects are shown below:
8. MCMLSD Line Detection Algorithm
8.1 Introduction to MCMLSD AlgorithmThe MCMLSD algorithm originates from this paper. The paper proposes a probabilistic algorithm that combines the advantages of both. In the first phase, a global probabilistic Hough method is used. In the second phase, each detected line is analyzed in the image domain to locate the line segments that generate peaks in the Hough space. By restricting the search to a straight line, the distribution of points on the line segment can be modeled as a Markov chain, and the probability optimal label is accurately calculated using a standard dynamic programming algorithm in linear time. The Markov assumption also produces an intuitive ranking method that uses the estimated expected value of the marginal posterior probability of the points correctly labeled on the line segment. To evaluate the resulting Markov chain edge segment detector (mcmlsd), we developed and applied a new quantitative method to control the evaluation of under-segmentation and over-segmentation. Evaluation results on the YorkUrbanDB dataset indicate that the proposed MCMLSD method outperforms the state-of-the-art methods by a significant margin.8.2 Effect Display and Analysis
The above images show the detection effects of the MCMLSD algorithm. From the above observations, we can find that this algorithm achieves good detection results, but the downside is that the algorithm’s running speed is relatively slow, which may also be related to the MATLAB code.
9. LSM Line Detection Algorithm
9.1 Introduction to LSM AlgorithmThe LSM algorithm is not only a line detection algorithm but also a line merging algorithm. The paper proposes a method for merging these broken line segments to restore the original perceptually accurate segments. The algorithm groups line segments based on angle and spatial proximity. Then, pairs of line segments that meet the new adaptive merging criteria are sequentially merged into a single line segment. This process is repeated until no more 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 merged segments are closer to the human-labeled ground truth segments compared to the latest line segment detection algorithms.9.2 Effect Display and Analysis
The above images show the detection effects of the LSM line detection algorithm. The left column shows the detection results of LSD, while the right column shows the optimization effects of the LSM algorithm, with different colors indicating different lines. From the above observations, we can see that LSM can merge some discontinuous lines into a longer line, which is very useful in real-world scenarios, but we also find that the LSM algorithm may incorrectly merge some lines, causing some errors.
10. Conclusion
This article summarizes and analyzes several classic line detection algorithms. For the task of line detection, it has many applications in real-world scenarios. For a specific scenario, you can choose a suitable line detection algorithm from this article based on your needs. If your scenario 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, etc.; 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 Version Tutorial
Reply "Extension Module Chinese Tutorial" in the "Xiaobai Learns Vision" WeChat public account to download the first OpenCV extension module tutorial in Chinese, 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: Python Vision Practical Project 52 Lectures
Reply "Python Vision Practical Project" in the "Xiaobai Learns Vision" WeChat public account to download 31 vision practical projects including image segmentation, mask detection, lane line detection, vehicle counting, eye line addition, license plate recognition, character recognition, emotion detection, text content extraction, and face recognition, to help quickly learn computer vision.
Download 3: OpenCV Practical Project 20 Lectures
Reply "OpenCV Practical Project 20 Lectures" in the "Xiaobai Learns Vision" WeChat public account to download 20 practical projects based on OpenCV for advancing OpenCV learning.
Group Chat
Welcome to join the reader group of the public account to communicate with peers. There are currently 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, and note: "Nickname + School/Company + Research Direction", for example: "Zhang San + Shanghai Jiao Tong University + Vision SLAM". Please follow the format, otherwise, you will not be approved. After successful addition, you will be invited to join relevant WeChat groups based on your research direction. Please do not send advertisements in the group, otherwise, you will be removed from the group. Thank you for understanding~