Abstract: Lane boundary detection plays a key role in the driver assistance system. This study proposed a robust method for detecting lane boundary in challenging scenes. First, a horizontal line is detected from the original image using improved Vertical Mean Distribution Method (iVMD) and the sub-region image which is under the horizontal line, is determined. Second, we extracted the lane marking from the sub-region image using Canny edge detector. Finally, K-means clustering algorithm classified left and right lane cluster before using RANSAC algorithm which fits a line model to each cluster. The proposed algorithm demonstrates the accuracy with respect to variant illumination, cracked road, complex lane marking and passing traffic. Experimental results show that the proposed method satisfies the real-time and efficient requirement of the intelligent transportation systems.
INTRODUCTION
According to Traffic Accident Analysis Center (http://eng.koroad.or.kr/Eng/Code/RotaStatistic/RotaStatistic10.jsp), there were 231,990 traffic accidents in 2009 across South Korea, killed 5,525 people and injured 226,465 people. The number of accidents rose 2.5% from 2008, with traffic injuries increasing 3.1%. A remarkable number of this statistical information was due to not only the inattention of drivers but also the low road condition. Lane boundary detection helps reduce this huge number of human fatalities. Therefore, lane boundary detection is an important component of many intelligent transportation systems and is used for vehicle navigation, lateral control, collision prevention or lane departure warning system.
Nowadays, many researchers have been researching on lane detection and lane following. Some systems (McCall and Trivedi, 2006; Ma et al., 2000) detected lane boundary by multisensor fusion (RADAR, LASER and Global-positioning System (GPS) but these systems worked with high cost and required updated data frequently in Geographic Information System (GIS) or Route Network Definition File (RNDF). Other researchers applied vision-based systems for lane detection and lane following. However, most of them demonstrated limitations with shadow, variant illumination and artificial symbols on the road surface. For example, several lane detection methods based on top-view image converted from 2D images (Mallot et al., 1991; Aly, 2008). These methods eliminated the perspective effect in the image and focus attention on the sub-region image. Nonetheless, online computation, camera calibration and parallel lane assumption was indispensable and time-consuming process. Recently, some researchers have attempted to implement some methods that are much more robust against noise and missing data (Wang et al., 2004; Jung and Kelber, 2005; Zhou et al., 2006; Cheng et al., 2006; ZuWhan, 2008). These techniques utilized mathematical models to fit data considered as lane boundaries. Nevertheless, they took much computation time and demanded some prerequisite constraints (parallel lane, fixed width and flat ground).
Motivated by the above problems, we proposed a robust method for detecting lane boundary in challenging scenes. The main properties of our method are described as the following.
| • | This method utilizes a novel method which detects horizontal line from grayscale image. This stage reduces computation time in comparison with processing whole image and is more useful than other methods (Aly, 2008; Wang et al., 2004; Jung and Kelber, 2005; Zhou et al., 2006; Cheng et al., 2006; ZuWhan, 2008) which used top-view image for same goal. Because the proposed method focuses attention only on a sub-region image and not requires camera calibration, flat ground assumption. Moreover, we apply tracking for horizontal line detection to improve the accuracy of this stage |
| • | Almost accidents often happen in the near field in front of vehicle on
highways and urban streets Therefore, linear model which is robust to various road conditions, is utilized for expressing lane boundaries. This linear model is simpler and faster than complex model used in (Aly, 2008; Wang et al., 2004; Jung and Kelber, 2005; Zhou et al., 2006; Cheng et al., 2006) |
| Fig. 1: | Block diagram of the proposed algorithm |
| • | A combined approach of K-means clustering and Random Sample Consensus (RANSAC) algorithm is applied to determine lane boundaries. This method detects left and right lanes, respectively while some previous approaches (Wang et al., 2004; Jung and Kelber, 2005; Zhou et al., 2006) supposed a fixed-width lane shape |
A block diagram of the propose algorithm is shown in Fig. 1. Each block of the diagram will be described later.
HORIZONTAL LINE DETECTION
A typical camera is installed with the resolution of 240x320 pixels. This stage will determine the sub-region image which is under the horizontal line. This has two benefits. First, the computation time for whole process decrease remarkably because only the sub-region image is considered. Second, this stage eliminates the bad influence of upper part of image (blue sky in day-time, artificial light in night-time) on lane markings. The previous method (Lim et al., 2009) utilized Vertical Mean Distribution method to determine the first minimum that occurs from the upper curve. That minimum position was considered as the horizontal line position. Vertical Mean Distribution (VMD) is defined as the following equation.
where, VMD(i) is the average of the gray values of the row ith. H is the height of original image. W is the width of original image. Gr(i,j) is the intensity of the pixel at the row ith and the column jth in grayscale image converted from original image.
Although, the previous method (Lim et al., 2009) worked well in day-time scenes, it was failed in night-time scenes. In this study, improved Vertical Mean Distribution method (iVMD) is proposed and used for detecting the horizontal line in day-time and night-time scenes.
With day-time scenes, the minimum position, where the first minimum occurs from the upper curve, is considered as the position of horizontal line (red star) shown in Fig. 2b. This is because sky region usually possesses higher intensity than road pixel and it may have a big transition of intensity difference as sky approaches ground.
With night-time scenes, conversely, the maximum search along the vertical mean curve is considered as the position of horizontal line (green star) shown in Fig. 2d. This is because the upper part of the image often lack of illumination and the intensity of horizontal line is highest. The results are shown in Fig. 2a-c.
However, this stage only applies to first frame of frame sequence or lane boundary detection failed. For next frames, the position of the intersection between two lane boundaries can be considered as a horizontal line position. This is the time-saving and fiducial property of our proposed algorithm.
LANE BOUNDARY DETECTION ALGORITHM
Lane marking extraction: In this stage, we ascertain where the lane markings are from the grayscale sub-region image which is cropped from horizontal line position to the bottom of original image and is shown in Fig. 3a. The intensity of lane markings is usually higher than the ones of the road surface. Based on this characteristic, Canny edge detector (Canny, 1986) is applied to detect edge points in the grayscale sub-region image.
In complex road, it is difficult to choose a suitable threshold value that eliminates edge points without removing many edge points of lane markings. A low threshold value can be insured the existence of true edge points corresponding to the lane marking or lane boundaries. Therefore, we extracted the edge points with a low threshold value of Canny edge detector. These edge points include lane marking candidates and noise factors of the complex road scene shown in Fig. 3b.
| Fig. 2(a-d): | Horizontal line detection algorithm |
| Fig. 3(a-d): | (a) Grayscale sub-region image, (b) Canny edge Image, (c) Improved edge image. (d) K-means clustering |
The lane marking contains the edge points which are continuity, so we utilized this feature to eliminate some wrong edge points made by noise factors shown in Fig. 3c.
K-means and RANSAC algorithm for detecting lane boundary: The proposed method detects left lane and right lane independently. That an edge point belongs to whether left lane or right lane is unknown, so K-means clustering algorithm is used to classify the edge points into two groups: left lane and right lane.
| Fig. 4: | K-means Clustering Algorithm |
K-means clustering (Kanungo et al., 2002) is a very simple and effective clustering algorithm which requires the number of sought clusters before classifying. K-means clustering aims at minimizing an objective function which is defined as the following.
where, ||xi(j)-cj ||2 is a chosen distance measure between a data point xi(j) and the cluster centre cj is an indicator of the distance of the n data points from their respective cluster centres. Figure 4 condenses the main stages of K-means clustering algorithm.
In present study, we choose k = 2 as the number of clusters. First, 2 edge points are selected randomly as initial cluster centers of each lane. The other edge points are assigned to their closest cluster center according to the distance measured by distance, orientation. In the following step, the means of each cluster are calculated and these means are taken as the new cluster center. Finally, the whole process is repeated with new cluster centers until no change in cluster center. Consequently, we get the left lane set and right lane set, as shown in Fig. 3d.
How we can fit a line model to each K-means clustering data set which contains so many outliers shown in Fig. 3d. Both Hough Transform and Least square fitting are failed in this situation. Therefore, we use Random Sample Consensus Algorithm (Fischler and Bolles, 1987; Lopez et al., 2005) (RANSAC) which is often used in computer vision when there are a lot of outliers, to determine the parameters of line model. The RANSAC algorithm is briefly described in Fig. 5.
The number of iterations, N, is chosen high enough to ensure that the probability (set to 0.99) that at least one of the sets of random samples does not include an outlier. In this study, N = 300 and the final result of proposed algorithm is shown in Fig. 6.
| Fig. 5: | RANSAC Algorithm |
| Fig. 6: | The final result of proposed method |
After left and right lane boundaries are detected, the intersection point between them is determined. And then this point is considered as a horizontal line position for next frame of sequence. This work helps to improve the robustness of whole process and reduce computation time because of skipping horizontal line detection stage.
EXPERIMENTAL RESULTS
This section shows some experimental results of the proposed algorithm. We applied this proposed algorithm for several single frames and frame sequences to test the performance. Some limitations are exhibited in certain situation.
Single frame results: We collected some images in challenging scenes: cracked road, night scene, rainy road with solid lane or dashed lane. The three first road images (Fig. 7a-c) contain cracked road and complex lane marking. The bad qualification of lane marking makes lane detection difficult. The next two images (Fig. 7d, e) describe the overtaking of another vehicle or the following of another vehicle. Other vehicles sometimes occlude a part of lane marking or the colors of other vehicles are same as lane marking. The four images (Fig. 7f, g, h, i) present some bridges in upper part of the image, or a vehicle run on night scenes.
| Fig. 7(a-l): | Some results of proposed method in challenging scenes |
The lack of light in highway makes the lane detection impossible; the artificial lamp, traffic light and tail-light are bad influence to lane marking. The three final images (Fig. 7j, k, l) is recorded in rainy, fog scenes. The watermark on the windshield or on road surface is the factor which makes lane marking wrong. Nevertheless, the proposed algorithm still gets accurate results in difficult scenes.
Frame sequence results: Above part, we only tested the proposed algorithm with single frame. To demonstrate the effect of the proposed algorithm, we test it on some frame sequences. Therefore, we recorded a number of clips on highway and Metropolitan Ulsan city in day-time and night-time. The system was prototyped using MATLAB R2010a with the Intel Core Quad processor at 2.67 GHz 2GB RAM. The resolution of these clips is (240x320) pixels and the frame rate is 30 FPS.
Clip .1 is collected under day-time condition on highway. This clip consists of different types and colors of lane marking: solid or dashed, yellow or white. Moreover, it contains some difficult scenarios: including overtaking (frame 307), incoming vehicle (frame 964, 1099) and lane changing (frame 380, 421). The detection results are displayed in Fig. 8. We observe that the lane boundaries are extracted successfully, regardless of complex scenes.
Clip .2 is captured under day-time on Metropolitan Ulsan city. Almost lane markings are dashed line and white color but there are many complex symbols and writing characters (frame 28,420,443). Sometimes, the lane boundaries are affected by other vehicles (bus, frame 170; incoming vehicle in other lanes, frame 317) and the traffic light, building block. What Fig. 9 exhibit the boundary lines of the lane are all correctly determined.
The proposed algorithm also is tested with video clip recorded at night time. The lane boundary detection is not only fatigued task but also more and more difficult during nighttime. Almost lane markings are affected by symbols, tail light and artificial light. Again, Fig. 10 shows the precise results of the algorithm.
Some previous methods (Aly, 2008; Wang et al., 2004; Jung and Kelber, 2005; Zhou et al., 2006; Cheng et al., 2006; ZuWhan, 2008) only worked under 10 frames/s speed but our proposed algorithm works with high speed at least 27 frame/s and can correspond to real-time requirement. Moreover, this method demonstrates its high performance over 90%, as shown in Table 1.
Limitations: In the current algorithm, we only focus on current lane which the vehicle is running on and straight line. Although, this algorithm gets surpassing results in difficult scenes, it still has some limitations.
| Fig. 8: | The results from video clip .1 |
| Fig. 9: | The results from video clip .2 |
| Fig. 10: | The results from video clip .3 |
| Fig. 11: | Some erroneous results of each video clip |
| Table 1: | Results of proposed algorithm |
Cases like there are so many symbols on road (frame 1405), the lane marking does not exist (frame 313) and the car encounters the crossing (frame 654), the proposed algorithm may give erroneous results shown in Fig. 11.
CONCLUSION
In this study, a robust and real-time method for lane boundary detection is proposed. This method takes horizontal line using improved Vertical Mean Distribution to reduce computation time and to improve the method accuracy. The lane markings are extracted by Canny edge detector with low threshold value which guarantee that all lane markings are detected. After that, K-means clustering and RANSAC fitting technique are utilized to detect lane boundaries. The left and right lane is ascertained separately without some assumptions (parallel and fixed-width lane) and pre-settings (camera calibration). Our proposed algorithm not only gets accurate results but also can correspond to real-time requirement of the intelligent transportation systems.
Further work will extend other models to describe arbitrary shape of the lane boundary. Lane tracking, estimation orientation of the vehicle and lane departure warning system will be implemented. The system would become more robust and safe.