Abstract: Road detection is one of the most important technologies in the vision-based intelligent navigation system. In this study, a fast and robust unstructured road detection method is proposed. In order to ensure the robustness of the algorithm, BP (Back Propagation) Neural Network is employed to learn the color features from a set of sample of both road region and off-road region and then to classify a new pixel. And a heuristic fitting approach based on Conditional Destiny Propagation is employed to fit the boundaries of the lanes with the Least Square Method. Taking the advantages of these properties, the proposed implementation works out with high performance of detection in various environments. Meanwhile it is robust against noise, shadows and illumination variations.
INTRODUCTION
Road detection is one of the most important technologies in the vision-based intelligent navigation system (Alvarez and Lopez, 2011). A robust road detection algorithm should provide accurate road position and direction information for the navigation system (Tian et al., 2010). However, conventional detection methods are of high computational costing and cannot adapt to various environments. Therefore, it is a critical issue to search for a real-time and robust road detection approach, to improve the vision-based intelligent navigation system for a practical application.
Conventional unstructured road detection algorithms could be divided into two groups, the model-based and the feature-based.
The model-based method begins with the hypothesis of the road model and then matches the road edge with the road model. AB-Spline based lane detection and tracking algorithm, proposed by (Wang et al., 2004), is a representative of this kind of methods. The algorithm is robust against noise and shadows. Moreover, it can work without any cameras’ parameters. Still, the result of such method is dependent on the hypothesis of the road model, so they cannot fit to the situation that the shape of road changes greatly.
The feature-based method divides the image into the road region and the off-road region based on the differences of gradient, color or texture between them. Compared with the model-based method, the feature-based method is not sensitive to the shape of the road. Kong et al. (2010) have presented a method based on the texture feature of a single image. Another typical example of this kind of methods is an adaptive road detection algorithm based on BP neural network presented by (Foedisch and Takeuchi, 2004). The approach extracts the features of a number of road images and trains the neural network based on the feature vectors and then computes the result of classification. The algorithm has the advantage that can adapt to various environments, but it still has the defect that it is not robust enough against to shadows. Moreover, in order to achieve real-time processing, it processes every other pixel in the image which has reduced the processing accuracy. In conclusion, it is a huge challenge to meet the real-time constraints while ensuring the robustness for the high computational costing of feature-based methods.
Beside these disadvantages, conventional unstructured road detection algorithms rarely consider about the continuity of the road scene in a video stream. That is to say every scene in the video stream need to be processed in the same way independently. Consequently, the algorithm cannot keep stable in some complex scenes.
In order to solve the disadvantages mentioned above, in this study, a heuristic approach based on BP Neural Network and quadratic curve model is proposed. Taking the advantages of the model-based and the feature-based methods, the approach is robust against shadows, illumination variations and the changing road shapes in various environments.
In the rest of the article, firstly, the detail of the algorithm is presented is introduced in Section 2. Secondly, the experimental results are described in Section 3. Finally, the conclusion is presented in Section 4.
CONDITIONAL DESTINY PROPAGATION
The Kalman filter is wildly used in target tracking and spatio-temporal estimation. However, the Kalman filter is a recursive linear estimator that applies only to Gaussian Densities. As a result, Kalman filtering is inadequate in non-Gaussian systems.
The Conditional Density Propagation algorithm (Isard and Blake, 1998) is based on factored sampling, it combines random sampling with learned dynamical models to propagate an entire probability distribution. The algorithm mainly consist of 3 steps:
| Step 1: | Select: Suppose the posterior probability density p(Xt-1|Zt-1) of time t-1 is given, where Xt-1 is the system state vector at time t-1, Zt-1 is the observation at time t-1. Then sample N times from the posterior probability density and mark the sample set as {st(n)} |
| Step 2: | Predict: Compute p(xt|xt-1 = st(n)) for each sample. The samples are the effective priori probability density p(Xt|Zt-1) for time t |
| Step 3: | Measure: Weight the samples {st(n)} from the observation density p(Zt|Xt) and compute the posterior probability density p(Xt|Zt) of time t |
The Conditional Density Propagation algorithm, updating the probability density after using each observation data, maintains the probability density reality. As a result, the method is highly robust in various environments.
ROAD DETECTION APPROACH
Color appearance information has been widely used as the main cue for road detection, since color provides powerful information of the road to be detected in the absence of reliable shape information. In addition, color imposes less physical restrictions, leading to more versatile systems (Alvarez et al., 2010).
Neural network is a way to learn the nonlinearity at the same time as the linear discriminant. Such multilayer networks can provide the optimal solution to an arbitrary classification problem. The key power provided by such networks is that they admit fairly simple algorithms where the form of the nonlinearity can be learned from training data (Duda et al., 2001).
| Fig. 1: | Algorithm block diagram |
Therefore, in this study, neural network is used to segment road and off-road regions after learning the color features of the image. Then the road boundaries are extracted and fitted with quadratic curve road model and the vanishing point is computed and estimated using conditional destiny propagation.
As a result, the proposed algorithm can accurately divide the image into road region and off-road region and fit the road boundary quickly through the result of classification. This method is robust against shadows, illumination variations and the changing road shapes in complex scenes.
The block diagram of the algorithm can be expressed as Fig. 1.
Block segment: Generally, the pixel in road and off-road region are continuous and similar, so the image can be divided into blocks and then be classified by its four corner regions pixels. In actuality, the influence of noises can be reduced by the approach. The method is described as follows.
Suppose a pixel x belongs to either road area R or off-road area NR that is xε{R, NR}. And the corner region C belongs to road area or off-road area which is represented as: Cε{R, NR}. The probabilities of a corner region belonging to the road area or off-road area can be computed as: p(CεR) = Σif(xiεR)/N and p(CεNR) = Σif (xiεNR)/N, where N is the number of pixel in a corner.
If four corner regions in the block all belong to road area or off-road area, mark this block as road block or off-road block. The membership probability is defined as: p(blockεR) = Σp(CiεR)/4 and p(blockεNR) = Σp(CiεNR)/4.
If some corner regions in a block belong to road area while others belong to off-road area, mark the block as mixed block and the membership probability p(blockεMIX) is defined as the mean of the probabilities of four corners belong to the corresponding areas.
| Fig. 2(a-c): | Samples of the result of classification and block segment (a) Origin image, (b) Prime result of segment and (c) Final result of segment after error fix |
Now, the image can be regarded as a matrix of blocks, with each block marked as Road, Off-road or Mix. In some case, the blocks might be misjudged by the influence of noise. To deal with such error, scan the blocks row by row. When meets a Mix block and the left block and the right block are marked as the same, then test the probability of these three blocks. A block with a probability lower than a threshold will be reconfigured.
Figure 2(a-c) shows the results of classification (a) Original image, (b) Primary classifying result in which the thick-black blocks are mixed block and (c) Final result of classification which is modified by error fix based on the membership probability.
Classification: In the step, every pixel in the corner regions is classified using a BP Neural Network which has been trained by samples of road region’s and off-road region’s color features.
The neural network presented consists of three layers, an input layer, a hidden layer and an output layer. They are interconnected by links which contain modifiable weights, between layers.
The image is converted to HSV (Hue, Saturation, Value) color space and use H and S value as an input vector of the network. The input vector is presented to the input layer, each hidden unit performs the weighted sum of its inputs to form its net activation, the net activation can be written as:
| (1) |
where, the subscript i indexes units on the input layer, j for the hidden, ωij denotes the input-to-hidden layer weights at the hidden unit j. Each hidden unit emits an output that is a non-linear function of its activation: yj = f(netj).
The net activation and emits of the output layer units netk and zk is computed similarly based on the hidden unit signals. Then zk is used to classify the input pixel as road or off-road.
Edge extraction: It can be sure that the current road boundaries exist only in the Mix blocks. Then the road boundaries are extracted from these blocks using an approach as follows:
| • | Scan the blocks from the bottom to the top. For each row, classify the midline pixels of Mix blocks from left to right. Take the continuous road pixels set in the scan line to be a candidate sub-segment line |
| • | Merge the close candidate road sub-segment line. Deal with all scan line’s candidate road’s sub-segment and get the road line set |
| • | Finally, for the road segments on each scan line, extract the line segment’s left and right boundary points and then obtain the boundary points set of the road |
Fitting: The quadratic curve road model is a commonly used model in the road detection. The quadratic curve is an efficient model that can fit various road boundaries, including straight road boundaries, bending road boundaries in the vast majority of circumstances. The equation of quadratic curve road model can be expressed as:
| (2) |
where, the LL and LR are the left and right boundaries of the road, x and y are the horizontal and vertical coordinates of the image, aL, bL, cL and aR, bR, cR are the parameters of the road boundaries that need to be fit for.
After the edge extraction phase, the boundary points of the road are extracted. And then, in order to compute the parameters, aL, bL, cL and aR, bR, cR, the coordinate of the points are used to fit the equation of quadratic curve with the least square method.
The fitting process is fast and robust in the vast majority of circumstances. However, in some complex scenes, some parts of the off-road area are very similar to the road area. Thus, if these parts are misclassified, the boundaries points extracted are also influenced.
To avoid these influence, in this study, a heuristic road model fitting method based on vanishing point estimation is proposed. The definition of the vanishing point can be understandably expressed in Fig. 3.
The method is based on the condition that the direction mutation of road will not occur in a video stream. Thus, the direction of road and the vanishing point can be estimated using the information in previous frame.
| Fig. 3: | Definition of vanishing point in road scene |
The fitting method can be expressed as follows:
| • | In the nth frame of the video, the coordinate of vanishing point Z(Vn) can be computed as the point of intersection of LLn and LRn and the priori probability density of the vanishing point in the n+1th frame p(X(Vn+1)|Z(Vn)) can be estimated using conditional density propagation algorithm: p(X(Vn+1)|Z(V)) = Ip(X(Vn+1)|X(Vn)p(X(Vn)|Z(V1:n)) dX(Vn) |
| • | In the n+1th frame, fit the road boundaries LLn+1 and LRn+1 using the boundary points and coordinate of vanishing point X(Vn+1) with the least square method. The weight of the coordinate of the vanishing point is higher than ordinary boundary points |
| • | Compute the distance between each boundary points and LLn+1 or LRn+1, the points whose distance is larger than a given threshold will be removed and then fit the boundaries again with the remained points. Then compute the coordinate of vanishing point Z(Vn+1) as the point of intersection of LLn+1 and LRn+1 |
| • | Compute the posterior probability density p(X(Vn+1)|Z(V1n+1)) using conditional density propagation algorithm: |
The fitting method can work recursively, the vanishing points of every frame in the video will be estimated and the fitting results are much stable and robust even in complex scenes.
Updating: To adapt to the changing environment, it is necessary to update the network weights. After the B-spline fitting phase, the image had been divided into road region and off-road region. Then choose one block in road region and one block in the off-road region as samples for updating. In order to keep the network from the influence of noise, the membership probability p(blockεR) or p(blockεNR) of the block chosen as sample is higher than a threshold.
Similar to the training phase of the network, the update rule for the hidden-to-output weights can be presented as follows:
| (3) |
where, η is the learning rate, δk is the sensitivity of unit k: δk = -∂J/∂netk.
The learning rule for the input-to-hidden weights is:
| (4) |
where, δj is defined as the sensitivity of unit j: δj = f’(netj) Σck = 1ωkjδk.
EXPERIMENTS
Here, the result of the algorithm will demonstrated. The algorithm is performed on a personal computer. And the proposed approach was realized using the lib of Open source Computer Vision library.
In order to show the effectiveness of the proposed algorithm, two groups of experiments are designed, one group is in the case of shadows and illumination variations while the other is with various environments. Due to the limitations of the experiment environment, a variety of simulation experiments is carried out on video images provided by the Vision and Automation System Center in Carnegie Mellon University instead of field tests. These sets of road pictures can be downloaded from http://vasc.ri.cmu.edu/idb/road/.
Figure 4 demonstrates a part of results in the experiments. The first row shows the results of Group One where the experiments are carried out in the environment of shadows and illumination variations and the second row is the results of Group Two where the experiments are carried out in different environments, such as snowy, rainy and fallen leaves. In the Fig. 4a is a scene with shadows, the trees on the two sides project shadows on the road surface, (b) Noon scene where there is great strong sunlight, (c) Dusk scene where it is some kind of dark, (d) Snow scene, the road surface is covered with snow, (e) Scene after the rain, the boundaries between road and off-road regions are very fuzzy and (f) Fall scene, both sides of the road is covered with fallen leaves. Clearly, the algorithm can accurately extract the boundary of the road. In scene (a), the road is covered by shadow, the block-classifying method used in the algorithm can exclude the interference of noise and accurately accomplish the fitting.
| Fig. 4(a-f): | Examples of the final detection result (a) Scene with shadows, (b) Scene of strong sunligh, (c) Scene of darkness, (d) Scene of snow, (e) Scene after rain and (f) Scene of fall |
| Table 1: | Pixel-wise measures definition |
| TN: Tru non-road, FN: Flase non-road, FR: False road and TR: True road | |
| Table 2: | Evaluation for the performance of detection results |
| Table 3: | Comparison of the detection performance between the proposed algorithm and kernel density estimation |
In scene (e), it is difficult to distinguish between road and off-road regions even by eyes. However, the algorithm can still do perfect classification and accurately find the boundary of the road.
In order to evaluate the performance of the approach, a pixel-wise measures is employed. In the measures, three error measures are computed: Quality, detection rate and detection accuracy (Alvarez et al., 2010), Table 1 and 2. Five group of images advantage different environment are manually segmented to generate the ground-truth.
The performance of the proposed method is validated and compared to the algorithm based on kernel density estimation introduced in (Tian et al., 2010).
The method can keep high and stable performance in various environments. Especially, the method is little interfered by shadows and illumination variations which can be seen clearly from Table 3. The Detection Accuracy of the proposed method can even reach 98.5% which is about 20% higher than traditional algorithm, the Detection Rate and quality of the proposed method has also been improved significantly. Thus, we can get a conclusion that comparing with traditional algorithm, the proposed method enhanced the robustness and detection performance greatly.
Only in the case of night that there is little difference between the hue and saturation of road and off-road regions, detection rate of the method might descend.
CONCLUSION
In this study, a fast and robust heuristic road detection algorithm is presented. The algorithm is robust against noise, shadows, illumination variations and can adapt to complex environments. The experiments verify that the algorithm is effective and real-time. The method can be used as reference for real-time system in intelligent navigation system.
ACKNOWLEDGMENTS
This study is supported by National Natural Science Foundation of China under Grant No.61272062, Fundamental Research Funds for the Central Universities of Hunan University under Grant No.531107040421 and Hunan Provincial Innovation Foundation for Postgraduate (CX2011B138).