# River Flow Lane Detection and Kalman Filtering-Based B-Spline Lane Tracking

Authors: King Hann Lim; Kah Phooi Seng; Li-Minn Ang
Journal: International Journal of Vehicular Technology
 (2012)

---

## Abstract

A novel lane detection technique using adaptive line segment and river flow method is proposed in this paper to estimate driving lane edges. A Kalman filtering-based B-spline tracking model is also presented to quickly predict lane boundaries in consecutive frames. Firstly, sky region and road shadows are removed by applying a regional dividing method and road region analysis, respectively. Next, the change of lane orientation is monitored in order to define an adaptive line segment separating the region into near and far fields. In the near field, a 1D Hough transform is used to approximate a pair of lane boundaries. Subsequently, river flow method is applied to obtain lane curvature in the far field. Once the lane boundaries are detected, a B-spline mathematical model is updated using a Kalman filter to continuously track the road edges. Simulation results show that the proposed lane detection and tracking method has good performance with low complexity.


---

## Body

## 1. Introduction

Automation of vehicle driving is being developed rapidly nowadays due to the vast growth of driver assistance systems (DASs) [1]. In conjunction with the development of low-cost optical sensors and high-speed microprocessors, vision-based DASs become popular in the vehicular area to detect apparent imaging cues from various road scenes for visual analysis and therefore warn a driver of an approaching danger and simultaneously perform autonomous control to the vehicle’s driving. Of all fatal errors happened, driver’s inattention and wrong driving decisions making are the main factors of severe crashes and casualties on road [2]. The deviation of a vehicle from its path without a signal indication has threatened the nearby moving vehicles. As a consequence, vision-based lane detection and tracking system becomes an important mechanism in vehicular autonomous technology to alert a driver about road physical geometry, the position of the vehicle on the road, and the direction in which the vehicle is heading [3].In the last few decades, a lot of vision-based lane detection and tracking techniques [4–8] have been developed in order to automatically allocate the lane boundaries in a variety of environmental conditions. It can broadly be divided into three major categories, that is, region-based method, feature-driven method, and model-driven method. Region-based method [9–14] basically classifies the road and nonroad pixels using color or texture information. Although it has simple algorithm, it may suffer from color inconstancy and illumination problem. Feature-driven method [15–18] extracts the significant features such as lane markings from road pixels to identify the lane edges. This method is highly dependent on feature detection methods such as edge detection which are sensitive to occlusion, shadow, or other noises. On the other hand, model-driven method builds a mathematical function such as linear-parabolic [19, 20], hyperbola [21, 22], or spline-based [23, 24] methods to mimic the lane geometry. Due to its comprehensive learning and curvature flexibility, this method has been widely used in the lane detection and tracking system.As stated in [19], Jung and Kelber manually cropped the effective road region to obtain the possible lane edges detection. At the same time, they applied a fixed threshold to split near- and far-field segment for the lines prediction using linear-parabolic model. On the other hand, Wang et al. [24] have proposed a lane detection and tracking technique using B-snake lane model, which measures dual external forces for generic lane boundary or marking. Initially, lane boundaries are detected using Canny/Hough estimation of vanishing points (CHEVPs). It is followed by constructing B-snake external force field for lane detection iteratively based on gradient vector flow (GVF) [25]. Nevertheless, the above-mentioned methods have encountered some flaws in the process. Manual cropping to obtain the effective lane region may not be an efficient way in the automation. In addition, fixed near-far-field threshold or segmented lines are not always applicable to all on-road conditions to determine the edges. Moreover, edge detector and Hough transform (HT) may easily be affected by shadow cast or weather change. The lane boundaries in the far-field range would be gradually undetectable using HT. Furthermore, CHEVP method is sensitive to numerous thresholding parameters initialization. Significant numbers of iterations are required to obtain GVF in the lane-tracking process.Motivated by the above-mentioned problems, a new system composed of lane detection and tracking is presented in Figure1. Horizon localization is first applied to a set of traffic scene image sequence to automatically segment the sky and the road region. Road region is then analyzed to further separate nonroad and road pixels. Subsequently, an adaptive line segment is computed using multiple edge distribution functions to monitor the change of road geometry. The portion below the adaptive line threshold is estimated with 1D HT method, while the upper part is determined using a low-processing method with the concept of river flow topology. After the lane edges are successfully located, they are passed over to lane tracking for reducing the computational time. Possible edge scanning is applied to seek for the nearby lane edges with respect to the estimated lane line. Control points are determined in order to construct a B-spline lane model. In assistance with Kalman filtering, B-spline control points are updated and predicted for the following frame’s lane curve.Figure 1
Block diagram of the proposed lane detection and tracking system.The proposed lane detection and tracking method has offered some advantages over the method [19, 24]. The performance of edge detection and HT are always distorted by shadow effect. Therefore, a regional dividing line is first applied to discard disturbance from sky region. The elimination of shadow effect is achieved by using an adaptive statistical method. Instead of using fix line to segment near and far-field, an adaptive line segment is proposed to monitor the change of angles along the lane boundaries. The concept of river flow is proposed for the lane detection system to follow the road in the far-field region. Furthermore, Kalman filter plays a twofold-role: (i) to correct B-spline control points for the current image frame and (ii) to predict the lane model for the consecutive frames. Unlike [24], less parameter tuning or thresholding values are required in the proposed system. Moreover, it has no camera parameters involved in the system determination. Overall, it gives a better performance with promising computational speed. This paper is organized as follows. Section 2 discusses the proposed lane detection, and Section 3 explains the Kalman filtering-based B-spline lane tracking technique. Some simulation results are shown in Section 4 and followed by conclusion and future works.


## 2. Lane Detection

Lane detection is a crucial task to estimate the left-right edges of driving path on a traffic scene automatically. In this section, four-stage lane boundary detection is proposed, that is, (i) horizon localization, (ii) lane region analysis, (iii) adaptive line segment, and (iv) river flow model. In the traffic scene, road region is the main focus for lane detection. First, horizon localization splits the traffic scene into sky and road region. Then, lane region analysis is applied adaptively based on the surrounding environment in order to remove mostly road pixels and keep the lane mark pixels. Adaptive line segment is therefore used to analyze the road edge curvature and separate the road region into near and far-field. In the near-field, a 1D HT is applied to draw a near-field line. At the same time, a river flow method is applied to obtain far-field edges which are hardly to be estimated using common line detection.


### 2.1. Horizon Localization

To eliminate the disturbances from sky segment, horizon localization [26] is performed to partition an M×N image into sky and road region, whereas M and N are the image row and column, respectively. First, a minimum pixel value filter, with a 3×3 mask, is applied on the image I(x,y) as depicted in Figure 2(a) to enlarge the effect of low intensity around the horizon line. Subsequently, a vertical mean distribution is computed as plotted in Figure 2(b) by averaging every row of gray values on the blurry image. Instead of searching for the first minimum value along the upper curve, the plot curve is then divided into β segments to obtain minima, whereas β represents the number of dividing segments. In this context, β is chosen to be 10 throughout the experiments. All regional minima are recorded to the subset A as follows:
(1)A={(mi,pi):mi∈[0,255]∣pi∈[1,M]∣1≤i≤β},
where mi is the magnitude of row pixel mean, and pi is the row index where the minimum point occurred as shown in Figure 2(c). Naturally, sky region always appears on top of the road image. Therefore, m1 is taken as a reference minimum point for condition comparison to prevent local minima occurred in the sky portion. Additionally, mean value (μ) of the entire image is calculated to determine an overall change in intensity. The regional minimum point search for the horizon localization is written as follows:
(2)Hz={p1,if(m1<mi+1)∩(m1<μ)∩(p1>εHz),pi,elseif[(mi<mi-1)∪|mi-1-mi|<Δm]⋯∩(mi<mi+1)∩(mi<m1),⋯∩(mi<μ)∩|mi+1-mi|>Δm,λ,ifothers,
where εHz is a small integer to prevent a sudden drop from the top of image; Δm is the minor variation of mean value change, whereas Δm=±2 intensity value, and λ is a user-defined value in case the minimum point cannot be found in the plot. As illustrated in Figure 2(d), the adaptive value of regional dividing line is obtained throughout the regional minimum search, whereas Hz∈A is denoted as the horizon line. The notion of getting the horizon line is because the sky usually possesses higher intensity than road pixels, and it might have a big difference of intensity as the sky pixels approach the ground. Nevertheless, the horizon line often happens at neither the global minimum nor the first local minimum appeared from the upper curve. Hence, a regional minimum search by obtaining minimum points from the segments is proposed to ensure the correct localization for the horizon line dividing the sky and road region, accurately. In Figure 2(e), the horizon line threshold is applied to separate the sky and road region and a road image Rroi is generated where all vertical coordinates below the Hz value are discarded.Figure 2
(a) Minimum pixel value filter, (b) vertical means distribution segmentation, (c) regional minima, (d) selection of the horizon line threshold, and (e) separation of the sky and road region.


### 2.2. Lane Region Analysis

Lane region analysis is performed with an adaptive road intensity range to further classify road and nonroad pixels with regards to the variation of surrounding environment. The lane region analysis steps are described as follows.Step 1.
Selectκ rows of pixels for lane region analysis where κ is the number of pixel rows to be selected. The selected rows are started at δ number of rows from the bottom of road image to avoid the likely existence of interior part of a vehicle at the image edge.Step 2.
The intensity voting scheme is carried out on every selected row and each maximum vote of selected row, is defined asvi, while gi is the grey value whereas the maximum vote occurs, assuming that
(3)B={(gi,vi):g∈[0,255]∣v∈ℜ∣1≤i≤κ}.
Subset B contains all maximum votes and gray value pixels for ith selected row. Hence, the vote, noted as vm, and the greatest gray value threshold, noted as gm, are selected as
(4)(gm,vm)=max(B),
where max(B)  is a function to get a maximum value from the set B. In addition, the most frequent gray level of the selected region is recorded as gs, where the global maximum vote occurs for the entire selected pixels. The standard deviation of selected rows is marked as σs.Step 3.
Define the adaptive road intensity range as[gs-σs;gm+σs]. Pixels that fall within the range are denoted as possible road pixels, and a binary map (Rbin) is formed as depicted in Figure 3(a). This region of interest could be further analyzed to investigate the road conditions. However, in our concern, lane marks are main features to identify the direction of lane flow. Only high intensity values are considered as the lane marks, whereas the pixel values being greater than gm+σs are denoted in Rplm as “1”. This processing step may get rid of shadow problem since shadow is usually in low intensity.(a) Extracted road region using the adaptive road intensity range; (b) remaining binary pixels are the possible lane markings.
(a)
(b)Step 4.
By summing up each row ofRplm, the values being greater than a threshold (T1) are discarded to remove the possible high intensity of a vehicle at the frontal view of the image. T1 is obtained by averaging nonzero rows of Rplm.Step 5.
Finally, a difference map (Dmap) is generated by multiplying Rroi and Rplm maps. The remaining binary pixels are possible lane mark pixels as shown in Figure 3(b).


### 2.3. Adaptive Line Segment

Lane markings are the salient features on the road surface, and they are often used to define the boundaries of road region. Initially, the gradient magnitude (∇Dmap) and the orientation (θ) are denoted as
(5)|∇Dmap|≈|Dx|+|Dy|,θ=tan-1(DyDx),
where Dx is the horizontal edge map, and Dy is the vertical edge map. In order to monitor the changes of lane direction, an adaptive line segment is proposed to split the near- and far-field regions using edge distribution functions (EDFs) [19].The edge map is first partitioned into small segments for everyT2 rows, whereas T2 is the number of rows to be grouped for each partition. Multiple EDFs are applied to these partitions to observe the local change of lane orientation based on the strong edges as denoted in Figures 4(a)–4(c). With reference to the gradient map and its corresponding orientation, multiple EDFs are constructed, with its x-axis is the orientation in the range of, [-90°;90°], and its y-axis is the accumulated gradient value of each orientation bin. The maximum peak acquired on the negative and positive angles denotes the right and left boundary angles, respectively. Peak values that go below a certain threshold T3 are discarded, whereas T3 is the mean EDF value of each partition. As shown in Figure 4(c), there is no detection for right angle since it has no significant edge points existed in the image illustrated in Figure 4(d).Figure 4
(a)–(c) Multiple EDFs on segmented regions, (d) results of lane detection after EDF partitions.Subsequently, EDFs’ grouping is done by joining those angles that are approximately equal into the same array. They are grouped from bottom to top based on the difference of each partition to its previous partition within±5°. The observation of orientation variation is that it will have an instant change of lane geometry when it comes to the far field.  Assume that there are nth groups of lane orientation. If n=1, it is a linear lane boundary. If n≥2, (n-1)th of EDF bins are combined to obtain a global lane orientation (θnf) for near field, while the nth group refers to the far-field orientation (θff). Although shadows deviate the lane edges, other partitions of EDF with more frequent angle value may correct the orientation of the road path. However, the angle θff may not be successfully estimated for the far-field edges because the left-right boundaries may deflect into the same direction.Eventually, a 1D-weighted gradient HT [19] is applied to near field to determine the lane’s radius r(θnf) based on r(θnf)=xocosθnf+yosinθnf, with known θnf values. The voting bins for each radius are accumulated with the gradient edge values, and the maximum vote is selected. Figure 5 demonstrates the left-right lane boundaries in the near field constructed by the measured angles and radii.Figure 5
Detected lane boundaries by combining (n-1)th EDF voting bins.


### 2.4. River Flow Edge Detection

At the far-field region, lane edges flow is hard to be estimated using HT because the lane geometry has become unpredictable in the road scene. As noticed in Figure4(d), the circle points out the failure of far-field edges detection using EDF and HT. This is because far-field lane edges may have irregular road curvature, and both lane edges may turn into the same direction. Two peaks of angles may fall onto the same side of EDF plot. Therefore, a river flow method is proposed to handle the far-field edge detection. From another perspective, lane flow detection has the same topology of a river flow. When there is an existing path, river will flow along the path. In this context, the path refers to the strength of edges for the lane boundaries. It starts flowing from the closest edges to the adaptive line segment and continues on to the vanishing point regarding to the connectivity and the strongest edge points as shown in Figure 6. With the 3×2 mask provided in Figure 6(b), the selection of the edge will be based on the surrounded large neighboring edge pixel clockwise.Figure 6
The concept of river flow model applied to edge map to detect the most significant edges in the far-field region.In Figure6(c), white pixels represent the estimated line from near-field region, while grey pixels represent the edge pixels given by the edge operator. It stops when it has no connectivity or flows in reverse direction.Assuming the pixels map shown in Figure7 is an image after edge operator, the river flow is operated in such a manner: check for the nearby high edge pixels and link up all the possible high edge values. The edge pixel having higher value than its neighboring pixels constructs the flow pathway. Initially, the starting flow point has to be allocated in the image before start flowing in the map. In this context, the starting point is allocated by using the previous near-field edge detection technique. As we know, the salient edge points would have higher intensity value than nonsalient pixels. By moving the 3×2 mask upwards as shown in the Figure 7, the maximum neighboring pixel is chosen in a clockwise manner indicating the connected path. The flowing process might halt if two or more same higher pixel values existed in the next flow or there is no connectivity detected in the next pixel. Due to the application of lane detection, reversion of the edge point flow is prohibited. The lane flow is either moving forward or moving in the same row of current detected pixel. Finally, the lane edges for left and right road boundaries are detected for lane tracking system.Figure 7
The example of flowing path on the edge pixels, where the “star” indicates the starting point; the “circle” indicates the ending point.


## 2.1. Horizon Localization

To eliminate the disturbances from sky segment, horizon localization [26] is performed to partition an M×N image into sky and road region, whereas M and N are the image row and column, respectively. First, a minimum pixel value filter, with a 3×3 mask, is applied on the image I(x,y) as depicted in Figure 2(a) to enlarge the effect of low intensity around the horizon line. Subsequently, a vertical mean distribution is computed as plotted in Figure 2(b) by averaging every row of gray values on the blurry image. Instead of searching for the first minimum value along the upper curve, the plot curve is then divided into β segments to obtain minima, whereas β represents the number of dividing segments. In this context, β is chosen to be 10 throughout the experiments. All regional minima are recorded to the subset A as follows:
(1)A={(mi,pi):mi∈[0,255]∣pi∈[1,M]∣1≤i≤β},
where mi is the magnitude of row pixel mean, and pi is the row index where the minimum point occurred as shown in Figure 2(c). Naturally, sky region always appears on top of the road image. Therefore, m1 is taken as a reference minimum point for condition comparison to prevent local minima occurred in the sky portion. Additionally, mean value (μ) of the entire image is calculated to determine an overall change in intensity. The regional minimum point search for the horizon localization is written as follows:
(2)Hz={p1,if(m1<mi+1)∩(m1<μ)∩(p1>εHz),pi,elseif[(mi<mi-1)∪|mi-1-mi|<Δm]⋯∩(mi<mi+1)∩(mi<m1),⋯∩(mi<μ)∩|mi+1-mi|>Δm,λ,ifothers,
where εHz is a small integer to prevent a sudden drop from the top of image; Δm is the minor variation of mean value change, whereas Δm=±2 intensity value, and λ is a user-defined value in case the minimum point cannot be found in the plot. As illustrated in Figure 2(d), the adaptive value of regional dividing line is obtained throughout the regional minimum search, whereas Hz∈A is denoted as the horizon line. The notion of getting the horizon line is because the sky usually possesses higher intensity than road pixels, and it might have a big difference of intensity as the sky pixels approach the ground. Nevertheless, the horizon line often happens at neither the global minimum nor the first local minimum appeared from the upper curve. Hence, a regional minimum search by obtaining minimum points from the segments is proposed to ensure the correct localization for the horizon line dividing the sky and road region, accurately. In Figure 2(e), the horizon line threshold is applied to separate the sky and road region and a road image Rroi is generated where all vertical coordinates below the Hz value are discarded.Figure 2
(a) Minimum pixel value filter, (b) vertical means distribution segmentation, (c) regional minima, (d) selection of the horizon line threshold, and (e) separation of the sky and road region.


## 2.2. Lane Region Analysis

Lane region analysis is performed with an adaptive road intensity range to further classify road and nonroad pixels with regards to the variation of surrounding environment. The lane region analysis steps are described as follows.Step 1.
Selectκ rows of pixels for lane region analysis where κ is the number of pixel rows to be selected. The selected rows are started at δ number of rows from the bottom of road image to avoid the likely existence of interior part of a vehicle at the image edge.Step 2.
The intensity voting scheme is carried out on every selected row and each maximum vote of selected row, is defined asvi, while gi is the grey value whereas the maximum vote occurs, assuming that
(3)B={(gi,vi):g∈[0,255]∣v∈ℜ∣1≤i≤κ}.
Subset B contains all maximum votes and gray value pixels for ith selected row. Hence, the vote, noted as vm, and the greatest gray value threshold, noted as gm, are selected as
(4)(gm,vm)=max(B),
where max(B)  is a function to get a maximum value from the set B. In addition, the most frequent gray level of the selected region is recorded as gs, where the global maximum vote occurs for the entire selected pixels. The standard deviation of selected rows is marked as σs.Step 3.
Define the adaptive road intensity range as[gs-σs;gm+σs]. Pixels that fall within the range are denoted as possible road pixels, and a binary map (Rbin) is formed as depicted in Figure 3(a). This region of interest could be further analyzed to investigate the road conditions. However, in our concern, lane marks are main features to identify the direction of lane flow. Only high intensity values are considered as the lane marks, whereas the pixel values being greater than gm+σs are denoted in Rplm as “1”. This processing step may get rid of shadow problem since shadow is usually in low intensity.(a) Extracted road region using the adaptive road intensity range; (b) remaining binary pixels are the possible lane markings.
(a)
(b)Step 4.
By summing up each row ofRplm, the values being greater than a threshold (T1) are discarded to remove the possible high intensity of a vehicle at the frontal view of the image. T1 is obtained by averaging nonzero rows of Rplm.Step 5.
Finally, a difference map (Dmap) is generated by multiplying Rroi and Rplm maps. The remaining binary pixels are possible lane mark pixels as shown in Figure 3(b).


## 2.3. Adaptive Line Segment

Lane markings are the salient features on the road surface, and they are often used to define the boundaries of road region. Initially, the gradient magnitude (∇Dmap) and the orientation (θ) are denoted as
(5)|∇Dmap|≈|Dx|+|Dy|,θ=tan-1(DyDx),
where Dx is the horizontal edge map, and Dy is the vertical edge map. In order to monitor the changes of lane direction, an adaptive line segment is proposed to split the near- and far-field regions using edge distribution functions (EDFs) [19].The edge map is first partitioned into small segments for everyT2 rows, whereas T2 is the number of rows to be grouped for each partition. Multiple EDFs are applied to these partitions to observe the local change of lane orientation based on the strong edges as denoted in Figures 4(a)–4(c). With reference to the gradient map and its corresponding orientation, multiple EDFs are constructed, with its x-axis is the orientation in the range of, [-90°;90°], and its y-axis is the accumulated gradient value of each orientation bin. The maximum peak acquired on the negative and positive angles denotes the right and left boundary angles, respectively. Peak values that go below a certain threshold T3 are discarded, whereas T3 is the mean EDF value of each partition. As shown in Figure 4(c), there is no detection for right angle since it has no significant edge points existed in the image illustrated in Figure 4(d).Figure 4
(a)–(c) Multiple EDFs on segmented regions, (d) results of lane detection after EDF partitions.Subsequently, EDFs’ grouping is done by joining those angles that are approximately equal into the same array. They are grouped from bottom to top based on the difference of each partition to its previous partition within±5°. The observation of orientation variation is that it will have an instant change of lane geometry when it comes to the far field.  Assume that there are nth groups of lane orientation. If n=1, it is a linear lane boundary. If n≥2, (n-1)th of EDF bins are combined to obtain a global lane orientation (θnf) for near field, while the nth group refers to the far-field orientation (θff). Although shadows deviate the lane edges, other partitions of EDF with more frequent angle value may correct the orientation of the road path. However, the angle θff may not be successfully estimated for the far-field edges because the left-right boundaries may deflect into the same direction.Eventually, a 1D-weighted gradient HT [19] is applied to near field to determine the lane’s radius r(θnf) based on r(θnf)=xocosθnf+yosinθnf, with known θnf values. The voting bins for each radius are accumulated with the gradient edge values, and the maximum vote is selected. Figure 5 demonstrates the left-right lane boundaries in the near field constructed by the measured angles and radii.Figure 5
Detected lane boundaries by combining (n-1)th EDF voting bins.


## 2.4. River Flow Edge Detection

At the far-field region, lane edges flow is hard to be estimated using HT because the lane geometry has become unpredictable in the road scene. As noticed in Figure4(d), the circle points out the failure of far-field edges detection using EDF and HT. This is because far-field lane edges may have irregular road curvature, and both lane edges may turn into the same direction. Two peaks of angles may fall onto the same side of EDF plot. Therefore, a river flow method is proposed to handle the far-field edge detection. From another perspective, lane flow detection has the same topology of a river flow. When there is an existing path, river will flow along the path. In this context, the path refers to the strength of edges for the lane boundaries. It starts flowing from the closest edges to the adaptive line segment and continues on to the vanishing point regarding to the connectivity and the strongest edge points as shown in Figure 6. With the 3×2 mask provided in Figure 6(b), the selection of the edge will be based on the surrounded large neighboring edge pixel clockwise.Figure 6
The concept of river flow model applied to edge map to detect the most significant edges in the far-field region.In Figure6(c), white pixels represent the estimated line from near-field region, while grey pixels represent the edge pixels given by the edge operator. It stops when it has no connectivity or flows in reverse direction.Assuming the pixels map shown in Figure7 is an image after edge operator, the river flow is operated in such a manner: check for the nearby high edge pixels and link up all the possible high edge values. The edge pixel having higher value than its neighboring pixels constructs the flow pathway. Initially, the starting flow point has to be allocated in the image before start flowing in the map. In this context, the starting point is allocated by using the previous near-field edge detection technique. As we know, the salient edge points would have higher intensity value than nonsalient pixels. By moving the 3×2 mask upwards as shown in the Figure 7, the maximum neighboring pixel is chosen in a clockwise manner indicating the connected path. The flowing process might halt if two or more same higher pixel values existed in the next flow or there is no connectivity detected in the next pixel. Due to the application of lane detection, reversion of the edge point flow is prohibited. The lane flow is either moving forward or moving in the same row of current detected pixel. Finally, the lane edges for left and right road boundaries are detected for lane tracking system.Figure 7
The example of flowing path on the edge pixels, where the “star” indicates the starting point; the “circle” indicates the ending point.


## 3. Lane Tracking

After the lane detection is generated in Figure8, lane tracking system is implemented to restrict the edges searching area on the subsequent frames and simultaneously estimate a lane model to follow the road boundaries. Lane tracking system has three stages, that is, possible edge scanning, B-spline lane modeling, and Kalman filtering. The nearest edges to the estimated line are determined with the possible edge scanning. A B-spline lane model is constructed with three control points to estimate lane edges in the current frame. Kalman filter corrects the lane model’s control points and use them to predict the next frame lane edges. These predicted lane edges will be passed to the next frame for edge scanning again, and this will reduce the overall lane detection process.Figure 8
The detected edges after river flow model.


### 3.1. Possible Edge Scanning

The detected lines are used to scan for the nearby edge pixels on the consecutive image after an edge detector, and these lines would be updated iteratively from the previously estimated lane model. The closest pixels to the estimated lane model are considered as the possible lane edges. The detected possible edges are very important for the lane model estimation.


### 3.2. B-Spline Lane Modeling

An open cubic B-spline [28] with t+1 control points {Q0,Q1,…,Qt} consists of (t-2)th connected curve segments, where t≥3. Each curve segment gi(s) is a linear combination of four control points, and it can be expressed as
(6)gi(s)=SiWiQi,i=-1,0,1,2,…,t,Si=[s3s2s1],0≤s≤1,Wi=[w1w2w3w4]=16[-13-313-630-30301410],Qi=[Qi-1QiQi+1Qi+2]T,
where Si is the knot vector which is uniformly distributed from 0 to 1, Wi is the spline basis functions, and Qi is the control points with 4×4 dimension. According to [24], three control points are found to be efficient to describe the lane shapes, that is, Q0, Q1, and Q2. The Q0 and Q2 are the first and last points of the detected edges, while the Q1 is defined as follows
(7)Q1=32P1-14(Q0+Q2),
where P1 is the adaptive line segment point. Next, Q0 and Q2 are tripled to ensure the line completely passing through the control points. For further prediction, control points have to be rearranged into state x and the observation model matrix H:
(8)x=[Q0Q1Q2]T,(9)H=[S-1(w1+w2+w3)S-1w40S0(w1+w2)S0w3S0w4S1w1S1w2S1(w3+w4)0S2w1S2(w2+w3+w4)].


### 3.3. Kalman Filtering

Kalman filtering method [6] can be used to predict the control points for left-right edges in consecutive frames. The linear state and measurement equations are defined as
(10)xk∣k-1=Fk∣k-1xk-1∣k-1+φk,y~k=Hkxk∣k-1+ek,
where the state space x is the control points of B-spline lane model defined in (8); Fk∣k-1 is the transition matrix bringing state x from time k-1 to k; φk is known as process noise; y~k is the measurement output; Hk is the observation model that maps the true state space to the observed space; ekis the measurement noise. In this context, Fk∣k+1=I3×3 with the assumption of zero external forces. The state is then corrected using Kalman filtering as defined in the following
(11)Pk∣k-1=Fk∣k-1Pk-1∣k-1Fk∣k-1T+vk,αk=yk-Hkxk∣k-1,Kk=Pk∣k-1Hk(HkPk∣k-1HkT+zk)-1,xk∣k=xk∣k-1+Kkαk,Pk∣k=(I-KkHk)Pk∣k-1,
where Pk∣k-1 is a priori estimate error covariance; Pk∣k is a posteriori estimate error covariance; αk is the error between the output yk obtained from the possible edge scanning and the lane model; Kk is the Kalman gain. Hence, Figure 9 shows the Kalman filtering-based B-spline lane model which will be used for detecting the possible edges in the next frame.Figure 9
The Kalman filtering-based B-spline lane model with control points indication.


## 3.1. Possible Edge Scanning

The detected lines are used to scan for the nearby edge pixels on the consecutive image after an edge detector, and these lines would be updated iteratively from the previously estimated lane model. The closest pixels to the estimated lane model are considered as the possible lane edges. The detected possible edges are very important for the lane model estimation.


## 3.2. B-Spline Lane Modeling

An open cubic B-spline [28] with t+1 control points {Q0,Q1,…,Qt} consists of (t-2)th connected curve segments, where t≥3. Each curve segment gi(s) is a linear combination of four control points, and it can be expressed as
(6)gi(s)=SiWiQi,i=-1,0,1,2,…,t,Si=[s3s2s1],0≤s≤1,Wi=[w1w2w3w4]=16[-13-313-630-30301410],Qi=[Qi-1QiQi+1Qi+2]T,
where Si is the knot vector which is uniformly distributed from 0 to 1, Wi is the spline basis functions, and Qi is the control points with 4×4 dimension. According to [24], three control points are found to be efficient to describe the lane shapes, that is, Q0, Q1, and Q2. The Q0 and Q2 are the first and last points of the detected edges, while the Q1 is defined as follows
(7)Q1=32P1-14(Q0+Q2),
where P1 is the adaptive line segment point. Next, Q0 and Q2 are tripled to ensure the line completely passing through the control points. For further prediction, control points have to be rearranged into state x and the observation model matrix H:
(8)x=[Q0Q1Q2]T,(9)H=[S-1(w1+w2+w3)S-1w40S0(w1+w2)S0w3S0w4S1w1S1w2S1(w3+w4)0S2w1S2(w2+w3+w4)].


## 3.3. Kalman Filtering

Kalman filtering method [6] can be used to predict the control points for left-right edges in consecutive frames. The linear state and measurement equations are defined as
(10)xk∣k-1=Fk∣k-1xk-1∣k-1+φk,y~k=Hkxk∣k-1+ek,
where the state space x is the control points of B-spline lane model defined in (8); Fk∣k-1 is the transition matrix bringing state x from time k-1 to k; φk is known as process noise; y~k is the measurement output; Hk is the observation model that maps the true state space to the observed space; ekis the measurement noise. In this context, Fk∣k+1=I3×3 with the assumption of zero external forces. The state is then corrected using Kalman filtering as defined in the following
(11)Pk∣k-1=Fk∣k-1Pk-1∣k-1Fk∣k-1T+vk,αk=yk-Hkxk∣k-1,Kk=Pk∣k-1Hk(HkPk∣k-1HkT+zk)-1,xk∣k=xk∣k-1+Kkαk,Pk∣k=(I-KkHk)Pk∣k-1,
where Pk∣k-1 is a priori estimate error covariance; Pk∣k is a posteriori estimate error covariance; αk is the error between the output yk obtained from the possible edge scanning and the lane model; Kk is the Kalman gain. Hence, Figure 9 shows the Kalman filtering-based B-spline lane model which will be used for detecting the possible edges in the next frame.Figure 9
The Kalman filtering-based B-spline lane model with control points indication.


## 4. Simulation Results

All results were generated using Matlab 2007a in a machine with core-2 duo processor at 1.8 GHz with 1 GB RAM. An image sequence was downloaded from [29], and it was used to compare with the proposed method and the method [24] in terms of performance and computational complexity. Additional video sequences were captured for further experimental evaluation on the proposed lane detection and tracking method. The threshold values of proposed system were initialized as εHz=7, λ=κ=30, and T2=10, where all values were obtained throughout the experiment.


### 4.1. Performance Evaluation

The performance of the proposed system was evaluated by comparing the estimated lane model with regard to the nearest edges. To calculate an average pixel error,d=100 random points were picked from the estimated lane model, and hence, the error was measured as follows:
(12)err=∑|x-j-xj|+|y-j-yj|d,j=1,…,d,
where (x-j,y-j) is denoted as the coordinate of nearest edges, and (xj,yj) was the estimated lane model pixel. Figure 10 showed average error plots for left-right edges. The proposed method obtained lower average pixels error rate per frame which were 3.34 and 2.19 for left-right lane tracking than the method [24], which were 7.30 and 6.05, respectively. This was because the performance of method [24] was highly dependent on the CHEVP detection and the threshold value to terminate the measurement of ΔQ and Δk. Examples of using method [19, 24] with its limitations were pointed in Figure 11.The error plots for (a) left lane tracking, (b) right lane tracking.
(a)
(b)Figure 11
Examples of using methods (a) [19] and (b) [24].Some lane detection results were provided in Figure12 where the first line indicated the horizon, and the second line was the near-far-field adaptive line. Figure 12(a) obtained continuous lines on left and right edges, while Figure 12(b) contained dashed lines as the lane marks. The white line was the successfully detected lane edges on the ground using the proposed lane detection method.Figure 12
The results for the proposed lane detection on (a) rural area, (b) highway.Figure13 showed the simulation results for the proposed method where all continuous frames were detected and tracked successfully. Moreover, more tested results using the proposed method were demonstrated in Figure 14 with two on-road videos. Video no. 1 was recorded in the rural area with continuous lines, and it was successfully detected although there was an existing frontal vehicle. Video no. 2 was shot in the highway with dotted dash line as shown in Figure 14(b), and the line was successfully estimated. A demo video has been uploaded to [30] for further understanding. However, the proposed method may still have a failure case in some aspect. When there was an overtaking vehicle which blocks the frontal road edge, it might not detect and predict the lane edges. Massive traffic flow might cause the misdetection too. At the same time, the proposed system may suffer on the scene without lane marks.Continuous images with the proposed tracking method, where “○”s and “□”s are left-right control points. (c)–(e)Q1L is located outside the image.
(a)
(b)
(c)
(d)
(e)
(f)
(g)
(h)
(i)
(j)Random video samples extracted from the UNMC-VIER AutoVision [27] video clips: (a) video no. 1: rural area and (b) video no. 2: highway.
(a)
(b)


### 4.2. Computational Time

Complexity-wise, the proposed method achieved faster computational time than the method [24]. This was because the complexity of method [24] was greatly dependent on the number of detected lines in the HT process for computing the vanishing points and the GVF iterations which was more complex compared to the proposed method. A summary of computational time between the proposed method and the method [24] was presented in Table 1.Table 1
Complexity comparison in average time base (sec.).
Method
Lane detection
Lane tracking
Method [24]
<4
<0.5
Horizon localization
0.19
Proposed method
Lane region analysis
0.34
0.78
Adaptive line segment
0.79
River flow method
0.06


## 4.1. Performance Evaluation

The performance of the proposed system was evaluated by comparing the estimated lane model with regard to the nearest edges. To calculate an average pixel error,d=100 random points were picked from the estimated lane model, and hence, the error was measured as follows:
(12)err=∑|x-j-xj|+|y-j-yj|d,j=1,…,d,
where (x-j,y-j) is denoted as the coordinate of nearest edges, and (xj,yj) was the estimated lane model pixel. Figure 10 showed average error plots for left-right edges. The proposed method obtained lower average pixels error rate per frame which were 3.34 and 2.19 for left-right lane tracking than the method [24], which were 7.30 and 6.05, respectively. This was because the performance of method [24] was highly dependent on the CHEVP detection and the threshold value to terminate the measurement of ΔQ and Δk. Examples of using method [19, 24] with its limitations were pointed in Figure 11.The error plots for (a) left lane tracking, (b) right lane tracking.
(a)
(b)Figure 11
Examples of using methods (a) [19] and (b) [24].Some lane detection results were provided in Figure12 where the first line indicated the horizon, and the second line was the near-far-field adaptive line. Figure 12(a) obtained continuous lines on left and right edges, while Figure 12(b) contained dashed lines as the lane marks. The white line was the successfully detected lane edges on the ground using the proposed lane detection method.Figure 12
The results for the proposed lane detection on (a) rural area, (b) highway.Figure13 showed the simulation results for the proposed method where all continuous frames were detected and tracked successfully. Moreover, more tested results using the proposed method were demonstrated in Figure 14 with two on-road videos. Video no. 1 was recorded in the rural area with continuous lines, and it was successfully detected although there was an existing frontal vehicle. Video no. 2 was shot in the highway with dotted dash line as shown in Figure 14(b), and the line was successfully estimated. A demo video has been uploaded to [30] for further understanding. However, the proposed method may still have a failure case in some aspect. When there was an overtaking vehicle which blocks the frontal road edge, it might not detect and predict the lane edges. Massive traffic flow might cause the misdetection too. At the same time, the proposed system may suffer on the scene without lane marks.Continuous images with the proposed tracking method, where “○”s and “□”s are left-right control points. (c)–(e)Q1L is located outside the image.
(a)
(b)
(c)
(d)
(e)
(f)
(g)
(h)
(i)
(j)Random video samples extracted from the UNMC-VIER AutoVision [27] video clips: (a) video no. 1: rural area and (b) video no. 2: highway.
(a)
(b)


## 4.2. Computational Time

Complexity-wise, the proposed method achieved faster computational time than the method [24]. This was because the complexity of method [24] was greatly dependent on the number of detected lines in the HT process for computing the vanishing points and the GVF iterations which was more complex compared to the proposed method. A summary of computational time between the proposed method and the method [24] was presented in Table 1.Table 1
Complexity comparison in average time base (sec.).
Method
Lane detection
Lane tracking
Method [24]
<4
<0.5
Horizon localization
0.19
Proposed method
Lane region analysis
0.34
0.78
Adaptive line segment
0.79
River flow method
0.06


## 5. Conclusion

A river flow lane detection and Kalman filtering-based B-spline tracking system has been presented to identify lane boundaries in image sequence. The advantages of horizon localization are to limit the searching region on ground and get rid of noises from the sky region. Moreover, lane region analysis eliminates shadow while maintains the lane markings. Meanwhile, an adaptive line segment with multiple EDFs is proposed to monitor the change of lane orientation from near to far-field. A 1D HT is applied to estimate the linear model in the near field. At the same time, river flow model is presented to detect far-field edges, and it could continuously detect and track lane edges for the following frame in future. Finally, B-spline model is predicted with a Kalman filter to follow the lane boundaries continuously. The proposed lane detection and tracking system will be further improved to suit more road scenarios. Further evaluation on river flow method will be investigated in the future. The concept of river flow method could be further extended to attain macroscopic and microscopic optimized mathematical mobility models in the future.



---

*Source: 465819-2012-11-05.xml*