Lane Recognition Algorithm Using the Hough Transform Based on Complicated Conditions

Zhicheng Zhang¹, Xin Ma^1,2

¹School of Information Science and Engineering, Shandong University, Qingdao, China.
²Shenzhen Research Institute, Shandong University, Shenzhen, China.

DOI: 10.4236/jcc.2019.711005                

Abstract

At present, most lane line detection methods are aimed at simple road surface. There is still no good solution for the situation that the lane line contains arrow, text and other signs. The edge left by markers such as arrow and text will interfere with the detection of lane lines. In view of the situation of arrow mark and text mark interference between lane lines, the paper proposes a new processing algorithm. The algorithm consists of four parts, Gaussian blur, image graying processing, DLD-threshold (Dark-Light-Dark-threshold) algorithm, correlation filter edge extraction and Hough transform. Among them, the DLD-threshold algorithm and related filters are mainly used to remove the identification interference between lane lines. The test results on the Caltech Lanes dataset are given at the end of the article. The result of verification of this algorithm showed a max recognition rate of 97.2%.

Keywords

Lane Detection, DLD-Threshold Algorithm, Correlation Filter Edge Extraction, Hough Transform

1. Introduction

In recent years, traffic accidents caused by improper driving of drivers or fatigue driving have made the field of safe driving [1] and automatic driving [2] a hot field of research.

Computer vision is the key technology for safe driving, automatic driving and lane detection. The main task is to complete the detection and tracking of the lane line. It can provide safety for the vehicle and a more comfortable ride for passengers.

At this stage, many researchers and research centers have done a lot of research on lane line detection. For the case of lane mark detection, many approaches have been made until now. As proposed in [3],HSV color features and Hough transform are used to achieve lane detection. The techniques used for this task varied from using multi-channel ROI (Region of Interest) combined with Hough transform [4],using a combination of multi-point classification and Hough transform [5]. And reference [6] uses an algorithm that combines automatic marker-assisted recognition with Hough transform to detect and mark lane lines. Other approaches used Mid-lane Estimation (MLE) [7] with Hough transform to detect and mark lane lines.

In the case of no other sign interference in the middle of the lane line, the conventional preprocessing method combined with the Hough transform can detect and identify the lane line very well. However, if there is an arrow mark or a text mark in the middle of the lane line, the common preprocessing method will leave some noise information to interfere with the Hough transform [8] [9]. The Hough transform will produce unstable results under complicated conditions. The detection result of the lane line will be inaccurate.

In this paper, we propose a simple algorithm to eliminate inter-line marker interference. The method is divided into four parts. First, it uses Gaussian blur to remove the noise points, and then convert it to grayscale. After, DLD-threshold algorithm and correlation filter are used to remove the interference area in the middle of the lane line and extract the edge of the lane line. After, by the use of Hough transform, a linear cluster is obtained to determine the lane line distribution. The test results on the Caltech-lane dataset are provided at the end of the article and can be found to perform well in complicated conditions.

2. Details of Algorithm

2.1. Gaussian Blur

Gaussian blur [10],also known as Gaussian smoothing, often used in the preprocessing stage of image processing and computer vision algorithms. In this paper, it is used to preprocess road images, smooth out sharp noise points, and prevent noise points from affecting the judgment of the Hough transform line in the following text.

$G\left(x,y,\sigma \right)=\frac{1}{2\pi {\sigma }^2}{\text{e}}^{\frac{-\left(x^2+y^2\right)}{2{\sigma }^2}}$ (1)

where G is the two-dimensional Gaussian function. In the image, Gaussian functions can be represented in the form of convolution.

$L\left(x,y,\sigma \right)=G\left(x,y,\sigma \right)\ast I\left(x,y\right)$ (2)

$\left(x,y\right)$ represents the pixel coordinates in the image, $\sigma$ is the standard deviation of the normal distribution, $I\left(x,y\right)$ represents the input image, $G\left(x,y,\sigma \right)$ is the Gaussian convolution kernel, $L\left(x,y,\sigma \right)$ is the image filtered by Gaussian convolution.

The simulation results are as follow: Including the original image, the blurred image after the Gaussian blurring, where sigma is 5.

Figure 1 shows the original input map, and Figure 2 shows the output map after Gaussian convolution filtering.

2.2. Color Image Gray Processing

When the camera captures a color image, it contains three components of R, G, and B, which takes up a large space and is easily interfered by external brightness. The grayscale image has only one component and takes up little space, at the same time, considering that the human eye responds differently to different color bands. We assign different weight values to the original three channels to obtain the gray image in Figure 3.

$Gray=R\left(x,y\right)\times 0.299+G\left(x,y\right)\times 0.587+B\left(x,y\right)\times 0.114$ (3)

2.3. DLD-Threshold Algorithm

In order to eliminate the interference of road signs and other signs on lane line detection, we use the DLD-threshold algorithm here.

Here, we define m as the number of rows of the image, n is the number of columns of the image, $span$ is the average Manhattan distance between the pixels at the two edges of the lane line, $threshold$ is the difference between the lane line and the local background gray value near it, $I\left(i,j\right)$ is the gray value of input

Figure 1. Original map.

Figure 2. Blurred image.

Figure 3. Grey-scale map.

image at $\left(i,j\right)$, $OUT\left(i,j\right)$ is the gray value of the input image at $\left(i,j\right)$. Figure 4 shows a schematic diagram of a pixel of a local lane line.

The set of pixels on both sides of the lane line are as follows:

$P=\left\{p_0,p_1,p_2,\cdots ,p_N\right\}$ (4)

$Q=\left\{q_0,q_1,q_2,\cdots ,q_M\right\}$ (5)

$\left(X_{p_i},Y_{p_j}\right)$, $\left(X_{q_j},Y_{q_j}\right)$ respectively represent the pixel coordinates of $p_i$, $q_j$. $d\left(p_i,q_j\right)$ represents the Manhattan distance between pixel $p_i$ and pixel $q_j$,S represents the number of elements in $spa{n}_{ij}$.

$d\left(p_i,q_j\right)=\left|X_{p_i}-X_{q_j}\right|+\left|Y_{p_i}-Y_{q_j}\right|$ (6)

$spa{n}_{ij}=\left\{d\left(p_i,q_j\right)\right\},i=0,1,2,\cdots ,N;j=0,1,2,\cdots ,M;\left|i-j\right|\le 1$ (7)

$span=\frac{{\displaystyle \underset{S}{\sum }spa{n}_{ij}}}{S}$ (8)

As shown in Figure 5 and Figure 6, DLD-threshold algorithm process pseudo code and flow chart are as follow.

Figure 7 show the result of the grayscale image passing through the DLD-Threshold algorithm.

2.4. Edge Extraction

In order to reduce the computational complexity, the conventional Canny edge extraction operator [11] [12] and the Sobel edge extraction operator [13] [14] are not used here, this paper use the correlation filter for unilateral extraction.

The correlation filtering algorithm [15] can be expressed as follows

$g=f\otimes h$ (9)

where f is the input image, h is the filter template and g is the corresponding output image.

Figure 4. Lane line local pixel diagram.

Figure 5. Algorithm chart.

Figure 6. Flow chart.

Figure 7. Result maps after DLD-threshold.

$f\otimes h\left(\tau \right)={\displaystyle {\int }_{\infty }^{-\infty }{f}^{*}}\left(\tau \right)h\left(t+\tau \right)\text{d}t$ (10)

Intuitive expression in the image is as follows

$g\left(i,j\right)={\displaystyle \underset{k,l}{\sum }f\left(i+k,j+l\right)\cdot h\left(k,l\right)}$ (11)

Here, we use the 3 * 3 correlation filter to process image.

$h=\left[\begin{array}{ccc}-3& 0& 3\\ -3& 0& 3\\ -3& 0& 3\end{array}\right]$ (12)

We use a correlation filter to extract the image at a single edge, where the amplitudes are taken as −3 and 3 respectively to enhance the edge strength. The result is shown in Figure 8.

Figure 8 represents the edge extraction map of Figure 7 after the correlation filter.

Generally speaking, the lane line and the identification information are located in the middle part of the image, and a template is set to match the image with the template, leaving only valid information such as lane lines and identifiers. The result is shown in Figure 9.

2.5. Hough Transform

In 1962, Paul Hough proposed the concept of Hough transform [16] [17]. The Hough transform is a parameter estimation method that uses voting to obtain a desired detection object, and is suitable for lane detection. The essence is to map the coordinate space in the image into the Hough parameter space [18],and analyze the Hough space data by point-line duality to detect the geometry. The Hough transform can be used to detect curves, circles, lines, etc. The most widely used of Hough transform is to detect straight lines in a picture.

Figure 8. Result maps after correlation filter.

Figure 9. Result maps after mask.

In the Cartesian coordinate system, the linear equation is generally expressed as the following form

$y=kx+b$ (13)

In this equation, k is the slope and b is the intercept. Tacking into consideration this aspect, other parameters are proposed, denoted as $\rho$ and $\theta$,which are polar coordinates.

$\rho =x\cos \theta +y\sin \theta ,\theta \in \left[-\pi ,\pi \right)$ (14)

As shown in Figure 10, the $\rho$ parameter represents the distance between the line and the origin, and the $\theta$ parameter represents the angle of the vector from the origin to the closest point on the line. This representation can map any line in the image space to a point $\left(\rho ,\theta \right)$ in the Hough space.

As shown in Figure 11, in the image space xy, straight lines passing through point $\left(x_1,y_1\right)$ are mapped into Hough parameter space $\rho \theta$ to obtain curve $l_1$,straight lines passing $\left(x_2,y_2\right)$ are mapped onto the Hough parameter space $\rho \theta$ to obtain curve $l_2$. The intersection of the two curves is $\left({\rho }_0,{\theta }_0\right)$,corresponding to the spatial line L. From this, the equation of the straight line in the image space can be obtained, which can be expressed by the following equation.

Figure 10. Schematic diagram.

Figure 11. Schematic diagram of Cartesian coordinate system and Hough space.

${\rho }_0=x\cos {\theta }_0+y\sin {\theta }_0$ (15)

We do the same operation described above for points of interest in the ROI area from the image. If there are multiple curves corresponding to different points intersecting in the coordinate system $\rho \theta$,it means that there is a straight line that can connect the multiple points. We can get the main lane line in the image by selecting the line with the intersection number in the Hough space. Also, the number of intersections must be greater than zero and greater than a predetermined threshold.

In addition, we may encounter some frame pictures without any mark but noise interference. We can also use the information of the previous frame in the Hough space to predict the lane line information of the next frame. The mark line detected from the current frame picture will not generate a large offset and the accuracy of the lane line detection of the consecutive frame picture can be improved.

Figure 12 shows the line cluster generated by connecting the points of interest obtained in the Hough transform. And final results are shown in Figure 13.

This paper uses the Canny edge extraction operator and combine the Hough transform for comparison experiments. The experimental results are shown in Figure 14.

Figure 14 shows the results of the sample image directly combined with the Canny operator.

3. Experiment Result

We use the Caltech Lanes dataset [19],the image of 640 × 480 and approx, 1120 frames to validate the proposed algorithm. The algorithm was implemented by using MATLAB R2015b Intel (R) Core (TM) i5-6500 CPU@3.20 GHz, 8GB RAM, the Windows 7 Ultimate PC.

The following pictures in Figure 15 are the experimental results of complex signs in the middle of the lane line. It can be seen that during the detection, the lane line is interspersed with other marking lines, crosswalk lines, text reminder signs, etc., but the algorithm lane line detection shows a higher precision. The recognition accuracy is shown in Table 1.

Figure 12. Line clusters.

Figure 13. Final results.

Figure 14. Results without DLD-Threshold algorithm.

Figure 15. Partial results in dataset.

Table 1. The accury of the result.

4. Conclusion

This paper presents a lane line detection algorithm under the complicated conditions. The algorithm uses Gaussian blur, image graying, DLD-threshold algorithm, correlation filter and Hough transform to determine the distribution of lane lines. The experimental results show that the method can work effectively and accurately, and obtain good results, both in the case of complicated road information and simple road information. Of course, this paper doesn’t consider the impact of strong light and unclear road markings on the road environment. In the future, we can combine various conditions to continue to improve lane detection.

Acknowledgements

Our research is supported by the Shandong Provincial Key R&D Program 2017GGX10113, Shenzhen Science and Technology Research and Development Funds (No. JCYJ20170818104011781).

Conflicts of Interest

The authors declare no conflicts of interest regarding the publication of this paper.

References

[1]	Goshi, K., Hayashi, M. and Matsunaga, K. (2012) Safe Driving Education System ASSIST—Education Anywhere, Anytime. 9th International Conference on Ubiquitous Intelligence and Computing and 9th International Conference on Autonomic and Trusted Computing, Fukuoka, 402-404. https://doi.org/10.1109/UIC-ATC.2012.154
[2]	Ding, Y., Li, Q., Ming, L. and GuoJian, T. (2016) Analysis of the Autopilot Design. 11th International Conference on Computer Science & Education, Nagoya, 426-430. https://doi.org/10.1109/ICCSE.2016.7581618
[3]	Teng, Z., Kim, J. and Kang, D. (2010) Real-Time Lane Detection by Using Multiple Cues. ICCAS, Gyeonggido, 2334-2337.
[4]	Cho, J.H., Jang, Y.M. and Cho, S.B. (2014) Lane Recognition Algorithm Using the Hough Transform with Applied Accumulator Cells in Multi-Channel ROI. IEEE International Symposium on Consumer Electronics, JeJu Island, 22-25 June 2014, 1-3. https://doi.org/10.1109/ISCE.2014.6884348
[5]	Ding, D., Lee, C. and Lee, K. (2013) An Adaptive Road ROI Determination Algorithm for Lane Detection. IEEE International Conference of IEEE Region, Xi’an, 1-4. https://doi.org/10.1109/TENCON.2013.6718807
[6]	Mariut, F., Fosalau, C. and Petrisor, D. (2013) Lane Mark Detection Using Hough Transform. International Conference & Exposition on Electrical & Power Engineering IEEE, Iasi, 25-27 October 2012, 871-875. https://doi.org/10.1109/ICEPE.2012.6463823
[7]	Ozgunalp, U. and Dahnoun, N. (2016) Lane Detection Based on Improved Feature Map and Efficient Region of Interest Extraction. Signal & Information Processing IEEE, Orlando, 14-16 December 2015, 923-927. https://doi.org/10.1109/GlobalSIP.2015.7418332
[8]	Zhu, W.N., Qiang, C. and Hong, W. (2006) Lane Detection in Some Complex Conditions. IEEE/RSJ International Conference on Intelligent Robots & Systems, Beijing, 9-15 October 2006, 117-122. https://doi.org/10.1109/IROS.2006.281858
[9]	Wang, J.F., et al. (2010) Lane Detection Based on Random Hough Transform on Region of Interesting. IEEE International Conference on Information and Automation, Harbin, 20-23 June 2010, 1735-1740. https://doi.org/10.1109/ICINFA.2010.5512220
[10]	Ding, Z.J., et al. (2013) Image Matching of Gaussian Blurred Image Based on SIFT Algorithm. International Conference on Wavelet Active Media Technology & Information Processing, Chengdu, 17-19 December 2012, 121-124.
[11]	Yan, X. and Li, Y. (2017) A Method of Lane Edge Detection Based on Canny Algorithm. Chinese Automation Congress, Jinan, 2120-2124. https://doi.org/10.1109/CAC.2017.8243122
[12]	Marr, D. and Hildreth, E. (1980) Theory of Edge Detection. Proceedings of the Royal Society B: Biological Sciences, 207, 187-217. https://doi.org/10.1098/rspb.1980.0020
[13]	Ozgunalp, U. (2017) Combination of the Symmetrical Local Threshold and the Sobel Edge Detector for Lane Feature Extraction. 9th International Conference on Computational Intelligence and Communication Networks, Girne, 24-28. https://doi.org/10.1109/CICN.2017.8319349
[14]	Zhang, H., Zhu, Q. and Guan, X. (2012) Probe into Image Segmentation Based on Sobel Operator and Maximum Entropy Algorithm. International Conference on Computer Science and Service System, Nanjing, 238-241. https://doi.org/10.1109/CSSS.2012.67
[15]	Zeng, H., Peng, N., Yu, Z., Gu, Z., Liu, H. and Zhang, K. (2015) Visual Tracking using Multi-Channel Correlation Filters. IEEE International Conference on Digital Signal Processing, Singapore, 211-214. https://doi.org/10.1109/ICDSP.2015.7251861
[16]	Mao, H. and Xie, M. (2012) Lane Detection Based on Hough Transform and Endpoints Classification. International Conference on Wavelet Active Media Technology & Information Processing IEEE, Chengdu, 17-19 December 2012, 125-127.
[17]	Low, C.Y., Zamzuri, H. and Mazlan, S.A. (2014) Simple Robust Road Lane Detection Algorithm. International Conference on Intelligent & Advanced Systems, Kuala Lumpur, 3-5 June 2014, 1-4. https://doi.org/10.1109/ICIAS.2014.6869550
[18]	Wei, X.W., et al. (2018) Research on Lane Detection and Tracking Algorithm Based on Improved Hough Transform. IEEE International Conference of Intelligent Robotic and Control Engineering, Lanzhou, 24-27 August 2018, 275-279. https://doi.org/10.1109/IRCE.2018.8492932
[19]	Shirke, S. and Udayakumar, R. (2019) Lane Datasets for Lane Detection. International Conference on Communication and Signal Processing, Chennai, 0792-0796. https://doi.org/10.1109/ICCSP.2019.8698065