Abstract
In this paper, a robust and real-time lane detection method is proposed. 
INTRODUCTION
In recent years, many driving assistance systems have been developed. To increase driving safety, the basic but important component is lane detection. With accurate lane information, lane departure warning, lateral control or impact warning can be achieved. In the literature, various lane detection methods have been proposed (Ieng et al., 2003; Kim, 2008; Wang and Shen, 2004; Wu and Lin, 2007; Zhou et al., 2006) . Generally, the lane detection method consists of two steps. The first step is to detect lane-marking features such as edge features (Wang and Shen, 2004; Zhou et al., 2006) , ridgel features (Lopez et al., 2005) or intensity bump features (Ieng et al., 2003) . Then in the next step, for specific lane models, model parameters are estimated using the lane-marking features. In most cases, the appearance of lane on the road image is not straight line but curve. Thus, most popular lane models are using polynomial based models to represent lane curves as (Kim, 2008; Wang and Shen, 2004; Zhou et al., 2006) . A good survey can be found in (McCall and Trivedi, 2006) . The Hough transform is a good estimator working on simple models such as straight line or circle. As an adaptation, in (Wang and Shen, 2004) , the image is divided into several sections so that lane segments in each section are approximated as straight line segments. Then, Hough transform is applied on each section. To estimate spline curves, RANSAC is preferred. The author in (Kim, 2008) used an modified one to detect multiple lanes. They generate a fixed number of hypotheses and then verify using inliers support and constrains. Here we denote this method as substandard RANSAC to differentiate from standard one. It is important to note that the substandard RANSAC neither guarantees to achieve optimal solutions nor to find all possible models. In this paper, we propose a novel lane model fitting algorithm called Guided RANSAC. It searches all possible lanes by an iterative search strategy and achieves optimal solutions with expected confidence. The rest of paper is organized as follows: Section 2 gives the description of lane-marking detection and filtering. Section 3 describes the Guided RANSAC algorithm. In Section 4, theoretical analysis on computational complexity is given. Then, Section 5 shows the experimental results and Section 6 gives conclusion.
LANE-MARKING DETECTION
For lane-marking detection, various algorithms have been proposed. Among the existing techniques, the intensity bump algorithm (Ieng et al., 2003 ) is adopted in the proposed technique. To reduce the false detections, a filter is introduced based on the fact that the two boundaries of the lane are parallel. After intensity bump detection, we calculate first derivative of left and right boundary for each lane-marking candidate: {dx l , dy l , dx r , dy r }. Then directions of left and right boundary are calculated as:
Then the lane-marking candidates are filtered using the rule as: v l T · v r > τ, where R l and R r are 2x2 matrix that to rotate edge orientations to boundary directions, τ is the threshold for the boundary correlation.
LANE DETECTION METHOD
After the lane-marking detection, the detected results are grouped to form meaningful structures such as lines or curves. The popular approaches use polynomial models with RANSAC as model fitting algorithm (Kim, 2008; Wang and Shen, 2004; Lopez et al., 2005) . We follow this framework and present a new model fitting algorithm to achieve lane detection efficiently. To extend the generalization of curve representation, the lane is represented by multiple lane segments. To represent one lane segment, we follow Kim's method (Kim, 2008) to use the cubic spline model.
Guided RANSAC Algorithm
Conventionally, RANSAC method works on whole sample space. For example, Kim's method performs lane fitting on the whole sample space (Kim, 2008) . Here in this paper, a novel method is presented to fit the lane model in an iterative way. This method is inspired by the CHEVP algorithm described in (Wang and Shen, 2004) . The CHEVP algorithm divides the image into several horizontal sections and lane segments are detected section by section. Instead of using explicit sections, we detect lane segments and elongate them recursively. The algorithm is designed hierarchically as a main routine and a core routine. The main routine scans all lane-markings sequentially. Once it finds an unvisited lane marking, the core routine is activated to search a lane from a starting lane-marking then iteratively search forward to elongate the lane (see Figure 1) . The core routine mainly consists of two steps, a start search step and an iterative search step. The start search step is to find an initial lane segment. Once an initial lane segment is found successfully, the iterative search step is activated to elongate the lane segment as long as possible. In the start search step, lane-markings which located near the starting lane-marking are collected as a search space. The initial lane segment is approximated as a straight line. RANSAC is performed to find the initial lane segment. In the iterative search step, the lane-markings that close to the extrapolated lane segment are gathered into a subset as the search space. The idea is that lane markings located near the extrapolated curve are more likely to lie on the lane. It can be considered as a prediction of lane path. To do the elongation, three control points are used during the RANSAC fitting. One control point is randomly sampled from the search space while the other two are directly from the previous lane segment. There are several advantages of this scheme. First, it avoids the unexpected elongation since the curve should pass through two control points of the previous lane segment. Second, the number of iterations during the RANSAC can be reduced since the search space is small and only one sample is drawn randomly. 
Lane Segment Aggregation
The Guided RANSAC algorithm attempts to detect all lane segments. One possible case is that dashed lane segments are detected separately. We try to aggregate lane segments to form lanes. The lane segments are aggregated using a method similar to hierarchical clustering. Iteratively, two lane segments are merged into one using a merging function. The Figure 2 
THEORETICAL ANALYSIS
The standard RANSAC algorithm mainly consists of two steps: 1) hypothesis generation and 2) hypothesis verification. The computational cost of standard RANSAC depends on the number of iterations and the population of the sample space to perform consensus verification which can be expressed as a function linear to k * N, where N is the population, k is the number of iterations which depends on stopping criterions. One typical criterion is the probability of bad model support after k iterations. Let w be the fraction of inliers, m be the number of points needed to generate hypothesis. Then the probability that no correct hypothesis is generated after k iterations will be:
We have the confidence (1 − p) to obtain a good solution. Given p, k can be calculated as: k = log(p)/ log(1 − w m ). In order to find multiple models, a substandard RANSAC is used in (Kim, 2008 ) that a fixed number of hypotheses is generated. The problem is that a fixed number of hypotheses can neither guarantee an optimal solution nor support all models. The Guided RANSAC solves the above problems since it searches all possible lanes. The Guided RANSAC can be considered as a set of standard RANSACs. The computational cost can be roughly expressed as:
where S is the size of subset in a search region and vis stands for the visit state of samples. As described in Equation 3, k depends on the value of p, w and m. p is a predefined parameter. w is the fraction of inliers given by user. m is 1 in Guided RANSAC as given in section 3.2. In contrast, 3 or 4 control points are required using standard RANSAC. In a typical setting that p is 0.05 and w is 0.3, then log(p)/ log(1 − w 4 ) = 368.3 while log(p)/ log(1 − w) = 8.4. It is promising that only few trials are required in our algorithm. Furthermore, in each iterative search step, the search space is restricted, so that S ≪ N and w is generally increased. Finally, T becomes a quite small value. In worst case, T = N * S * log(p)/ log(1 − w) where image is total clutter. The additional computational cost in Guided RANSAC is to generate subset. However, the experimental results show that it is negligible.
EXPERIMENTAL RESULTS
The algorithm has been tested on image sequences captured from real environment. The size of an image is 720x480. First, we give the comparison result of standard RANSAC and proposed algorithm in Figure 3 . In this comparison, the standard RANSAC uses 4 control points and both standard RANSAC and Guided RANSAC use a bad model support criterion with p = 0.05. The result shows that the computational cost of our proposed algorithm is about 3 times less than standard RANSAC. We also found that the real time cost of standard RANSAC and Guided RANSAC are closely proportional to this result. In Figure 4 , the comparison result between substandard RANSAC and Guided RANSAC is given. 100 hypotheses are generated with 4 control points as in (Kim, 2008) . The reason of the peak time cost of substandard RANSAC is that in a complex environment, more outliers will lead to higher probability to generate bad hypothesis. The average time cost of Guided RANSAC is about 6 times less than substandard RANSAC. Finally, we show the results on real road images. In Figure 5 , The lane aggregation connects dashed lane or broken lane while removes false positives. The results in Figure 6 show that the proposed algorithm is robust to complex lane types such as curved lane, dashed lane and crotched lane. 
CONCLUSIONS
We have presented a novel method to detect lanes in real-time. The algorithm requires little assumption and is able to detect lanes in complex road conditions. The experimental result shows that the proposed algorithm is suitable for real-time applications such as lane departure warning system. It can be extended to many model fitting based applications such as curve fitting, shape detection and so on.

{'paper_id': '45857084', 'title': 'LANE DETECTION BASED ON GUIDED RANSAC', 's2_url': 'https://api.semanticscholar.org/CorpusID:45857084', 'source': 'S2ORC'}