Informatica 41 (2017) 283–288 283 Improved Lane Departure Warning Method Based on Hough Transformation and Kalman Filter Minjian Liang1,2, Zhou Zhou1 and Qingsong Song1 1 School of Information Engineering, Chang’an University, Nan Er Huan Zhong Duan, Xi’an, 710064, China Email: qssong@chd.edu.cn 2 Guangdong Special Equipment Inspection and Research Institute: Branch of Zhuhai, West Renmin Street, Zhuhai, 519002, China Keywords: automobile active safety, lane departure warning, Hough transform, Kalman filter Received: June 24, 2016 Abstract: Lane departure warning is the key issues of automobile active safety problems. In this paper, an improved lane departure warning method is proposed based on Hough transformation and Kalman filter, noted as HK-LDWS. At first, the captured colour lane videos are decomposed into frames which are transformed and truncated into binary images subsequently. Secondly, Hough transformation is explored to detect lane lines in the truncated binary images, and Kalman filter is used to predict and track the detected lines. Finally, lane departure warnings are delivered out regarding as the predetermined safe distance based on the lateral distances. The actual road test results show that HK-LDWS can track lanes and make all departure warning correctly besides that it costs less than 35 milliseconds for per frame processing. HK-LDWS is an efficient solution for the lane departure warning problem. Povzetek: S pomočjo Houghove transformacije in Kalmanovega filtra je razvita nova metoda za povečano avtomobilsko varnost. 1 Introduction Lane departure is actually a kind of response distortion of sensors, and lane departure warning system, as one kind of key technologies for intelligent vehicles, can at least reduce 24% of traffic accidents which happened due to lane departure [1]. It has an important practical significance to develop lane departure warning system for driver safety alert, traffic accident avoidance, and even for ambient intelligence [2]. Lane departure warning system mainly consists of a HUD (head up display), camera, controller and sensor; when the lane departure system is running, camera (usually placed in the side of the body or the mirror position) will always collect driving lane marking line, through image processing parameters obtained in the current position of the car in the driveway. When the detected vehicle deviation lane, the sensor will collect data and the operating state of vehicle driver, and then the controller sends out the alarm signal; the whole process is about 0.5 seconds that will provide more time for the driver; and if the driver turn on the lights, the normal line change, then lane departure warning system will not make any tips. road and vehicle state perception, lane departure evaluation algorithm and signal display interface are composed he three basic modules of lane departure warning system. Chen et al. propose a hyperbolic road model based lane recognition and departure warning algorithm, which at first searches out edge points of lane marks, and then identifies marks’ parameters by exploring least squares fitting method, tracks identified lanes by particle filter algorithm, and finally judges the departure via spatial- temporal model [3]. Liu et al. propose another lane recognition algorithm based on deformable template and genetic algorithm, which to obtain the best assignments of the template parameters use a genetic algorithm to search the maximum value of likelihood function [4]. Wang et al. propose a B-Snake model based lane detecting and tracking method which use CHEVP (Canny/ Hough Estimation of Vanishing Point) to determine the initial position of lines, and then use minimum mean square error to update the control points of lines [5]. Lin et al propose a fuzzy algorithm for lane detection and tracking [6]. Spline curve model is also verified for lane departure warning system [7]. Although most of the algorithms are demonstrated to be with good alarm performance, there are still improvement requirements as far as noise-robustness and time-consuming are concerned, however. In view of those two concerned, here a lane departure warning method based on Kalman filter-based matching and tracking is proposed, which is noted as HK-LDWS. Firstly, the captured lane video is by frame transformed into binary images and cut by an assigned proportion coefficient. Secondly Hough transformation is explored to detect lines in the images, and HK-LDWS is designed to match and track the detected lines. And finally, a lane departure warning algorithm based on lateral distance is realized to deliver one alarms. The experiments show that HK- LDWS is can make early-warning accurately and efficiently. 2 HK-LDWS HK-LDWS consists of four modules, i.e., video image pre-processing, lane detection, tracking and departure warning, as shown in Figure 1. The pre-processing module carries out lane image binarization and truncation. The 284 Informatica 41 (2017) 283–288 M. Liang et al. detection module use Hough transformation to extract lines in the images. The following tracking module explores Kalman filter to track the extracted lines based on the assumption that the lines are moving linearly and continuously. The last module provides departure alarms based on the calculated deviated distances from the right lanes. Video image Image preprocessing Lane detection Matching and Tracking Departure warning Figure 1: HK-LDWS modules. 2.1 Image pre-processing This module executes two calculations--binarization and truncation. In order to improve the noise robustness of HK-LDWS, the input video images are at first transformed by frame into grey level images, and then converted into 0-1 binary images. Although lots of pre-processing methods have been proposed for image segmentation such as edge or corner detection, fuzzy logic [8-9], since being as one classic non-parametric and unsupervised adaptive threshold selection method here the Otsu method is exploited, where “0” points correspond to the pixels not or maybe not on the lines, “1” to the pixels on or maybe on the lines within the images [10]. The Otsu method is a global dynamic binarization method, also known as Otsu method, is a kind of grey image value of two commonly used algorithms. The basic idea of the algorithm is: use a grey image per the grey target size, divided into two parts part and the background, in this two within class variance minimum and maximum variance when the threshold value is the optimal binarization threshold. Further the binary images are truncated by an assigned proportion coefficient to reduce the detection area and avoid noise interferences ahead of vehicle. Notes the original size of the images as m n , m , n represents image height and width respectively. Notes the assigned proportion coefficient as a， [0,1]a . The images are truncated from top to bottom with the proportion a , i.e., the top a are cut off, the bottom (1 )a are remained. The remaining (1 )a is taken as the region of interest (ROI), which is to be explored in the following modules. 2.2 Lane detection In this module, Hough transformation is used to extract lines contained in the ROIs. The lanes are regarded as straight lines since almost all the expressways are designed with the least curvatures [11]. Note one line is described as the Equation *cos( ) *sin( )x y    . It can be said that those collinear ( , )x y pixels in the Cartesian coordinate are mapped to the same one ( , )  point in the polar coordinate. Being one of the most typical line detection algorithms Hough transformation executes accumulation calculation in the ( , )  coordinate space where the maximum accumulation values correspond to the assignments to the extracted lines’ parameters. The detailed lane detection process is as follows and shown in Fig. 2. (i) Uniformly divide the ( , )  space into small districts. Each district has an accumulator ( , )acc   , of which the initial value is set zero. And in addition, all the “1” pixels within ROI makes up of the initial point set; (ii) If the point set is empty, the detection process ends; otherwise randomly pick up a pixel from the set to calculate out value of  corresponding to all  , and then add up by one to the ( , )acc   , to which the district corresponds having the largest  ; (iii) Delete the picked-up point from the set; (iv) Judge whether there is an accumulator of which the value exceeds to some threshold thr or not. Figure 2: Lane detection process based on Hough transformation. Improved Lane Departure Warning Method Based... Informatica 41 (2017) 283–288 285 If no, back to step(ii); if yes, determine a line based on the accumulator value, and then reset the accumulator to be zero, and delete all the pixels on this line from the set; (v) Back to step(ii). 2.3 Matching and tracking Since most expressways are designed to be structured, and the consideration that the lane model should be with cheap computational consumption, it is assumed that the lanes within the two consecutive frames are straight and continuous, and the vehicle is moving at the same one speed. Therefore, the motion model of the lanes relative to vehicles can be supposed to be uniform and linear [12]. Based on this supposition, Kalman filter is explored here for line matching and tracking. Assume that in the ROIs of each frames it can be extracted out at most 20 lines, all of which make up of a line repository, i.e., {( , )}ik ik  , 1,2,...,20i  , 0k  . Note [ , , , ] T k k k k kX     as the detected line status, /k kd dk  , /k kd dk  represent radial velocity and angular velocity respectively, k is time step. Lane update equation is supposed, 1 1k k kX AX W   (1) Observation equation, k k kZ HX V  (2) Where A is the state transition matrix (STM), 1 0 1 0 0 1 0 1 0 0 1 0 0 0 0 1 A             . STM is used to find the solution of linear system which represented by state-space and in the time-variant case, there are many different functions satisfying these requirements that related to the structure of system. STM need to be determined before analysis on the time-varying solution can continue. 1 0 0 0 0 1 0 0 H        is the measurement matrix, kW and kV are system noise and observation noise respectively. Kalman filter is executed via two phases--time update and measurement update. Time update calculates the estimations of the state vectors through the prediction of current state vectors and their covariance matrix. Measurement update obtains the corrections of the state vectors through residuals computation based on the state vectors’ estimations and the latest measurements. It is just via the prediction-correction cycle for Kalman filter to complete the recursive estimation of the state vectors. Time update equation, 1 ˆ ˆ k kX AX    (3) 1 T k kP AP A Q    (4) Measurement update equation, 1[ ]T Tk k kK P H HP H R     (5)  ˆ ˆ ˆk k k k kX X K Z HX    (6) ( )k k kP I K H P   (7) where ˆ kX  , kK , ˆ kX , kZ are the prediction value, the gain, the estimation value, and the observation value at time step k respectively. The covariance matrix for the system noise and the observation noise is noted as Q and R respectively, which are initialized as follows, 0.05 0 0 0 0 0.05 0 0 0 0 0.05 0 0 0 0 0.05 Q             , 1 0 0 1 R        Specifically, the proposed HK-LDWS is as follows, the procedure is shown with Fig.3. (i) Initialize the line repository to be zero, i.e. {( , )}ik ik  all elements are zero, 1,2,...,20i  , 0k  , and initialize another 20 matching counters iN , 1,2,...,20i  , to be zeros also. One line in the repository has a counter. (ii) Input the extracted lines which being outputted from the lane detection module at time step k . (iii) Match the extracted lines with the already existing lines in the repository at time step ( 1)k  one by one, calculate the distance iD between each of them, i.e., ( 1) ( 1)| | | | *i ik j k ik j k imageD Size        ， imageSize is the width of the ROIs, , 1,2,...,20i j  ; (iv) Update the values of those matching counters iN , 1,2,...,20i  . if * miniD D , the match is successful, the extracted line {( , )}ik ik  is replaced by the estimated line ( 1) ( 1)( , )j k j k   which is generated by Kalman filter, and in addition, the corresponding counter iN is updated as 1i iN N  ; If the match fails, the repository remains as it was at time step ( 1)k  , but iN is updated 1i iN N  . Here * minD is 286 Informatica 41 (2017) 283–288 M. Liang et al. noted as a predetermined threshold for the matching distances. (v) Track the lines in the repository by Kalman filter formulated by Equation (3) ~ (7). Only those lines of which the value iN exceed to some threshold are being tracked. Under the consideration of noise-robustness and computational efficiency, the threshold is set to be ten, i.e., only those lines which have been uninterruptedly detected in no less than ten consecutive ROIs are to be tracked by Kalman filter; those lines ( 10iN  ) are not to be tracked at all. (vi) Update the line repository with the estimated lines by Kalman filter. (vii) Iterate until the end. Figure 3: Kalman filter-based matching and tracking procedure. 2.4 Departure warning The lane departure warning algorithm based on lateral distance is realized here [13]. At first, the polar coordinates of the lines obtained from the matching and tracking module are transformed into Cartesian coordinates. And further, the intersection positions that the tracked lines pass through the bottom boundary of the ROIs are calculated out. Therefore, the minimum distance among the intersections and the central point at the bottom boundary of the ROI can be obtained. If the minimum is less than some predetermined safe distance threshold, the module delivers sound alarms. 3 Experiments The performances of HK-LDWS especially computational efficiency and warning accuracy are evaluated with the situations that the proportion coefficient a is assigned different values. It is defined three performance indices, i.e., effective detection rate ( e dr ), time consumption per frame ( ft ), and number of missing alarms ( an ). It is calculated per frame for the distances ( d ) between the extracted lines from Hough transformation and the estimated lines generated by Kalman filter as the same way as the distance iD during matching are calculated. If the value of d is more than five pixels, the extracted lines are considered invalid, otherwise the extracted are effective. Note the number of frames within which the extracted are effective as e fN , the total number of frames in the test video as v fN . There is / e e v d f fr N N . Note the total consumption time for one whole video as vt . There is / v f v ft t N . Missing alarm happens once, i.e., 1a an n  , when the departure occurs it should be delivered out an alarm but no alarm. The value of the truncated proportion coefficient a is assigned 0.3, 0.4, 0.5, 0.6, and 0.7 respectively. The test result is shown in Table 1. According to Table 1, while a is assigned 0.3, 0.4, 0.5, the means of the distance d are usually less than five pixels, and it has no missing alarms. However, by contrast while a is chosen 0.6 and 0.7, d reach 7.8635 and 13.6823 respectively, and in addition the corresponding number of missing alarms an gets to 12 and 27 respectively. When a is set 0.5, the time consumption per frame vt is just 33.92ms. When a are set 0.3 and 0.4, vt rise up to 44.39ms and 45.13ms respectively. By contrast while a increases up to 0.6, vt decreases to 30.86ms. Compared with the situation that 0.5a  , it is reduced by 9% in time consumption, however, the number of effective extracted frames is only 262, the effective detection rate ( e dr ) is only 77.74%, and in addition the number of missing alarms reaches to 12. The computational efficiency for the situation that 0.7a  is also improved where the time consumption per frame is less than 30ms, the warning accuracy gets even worse, the effective detection rate is just a bit more than 50%, the number of missing alarms is up to 20 times, however. It can be said that the situation that 0.5a  corresponds to the best performances as far as computational efficiency and warning accuracy are Improved Lane Departure Warning Method Based... Informatica 41 (2017) 283–288 287 concerned, where the effective detection rate reaches up to 96.14%, the time consumption per frame is about 33.92ms, and there are no missing alarms. The computational efficiency for the situations that 0.5a  is better than that for the situation 0.5a  , the warning accuracy is worse, however. The warning accuracy for the situations that 0.5a  is as the same good as that for the situation 0.5a  , but their computational efficiency is slightly worse. The performances corresponding to the situation 0.5a  are fully fit for practical requirements, therefore it is chosen for the HK-LDWS. It is shown in Fig.4 for the extracted lines from Hough transformation and the estimated lines generated by Kalman filter under three different situations (left 0.4a  , middle 0.5a  , right 0.6a  ) where the extracted lines are denoted blue solid, the estimated are red dashed. For the situations are 0.4 and 0.5, the extracted are almost coincided with the estimated, for 0.6a  , there are obvious deviations between the extracted and the estimated, however. The calculated concreted values of  and  with the situation 0.5a  are demonstrated with Fig.5, where the curves obtained from Kalman filter are more smoothly than that from Hough transformation. Therefore, it can be said that HK-LDWS is more noise-robust than the method purely based on Hough transformation. During tracking the residuals of Kalman filter are recorded based on Equation (6). Note the residual of  and  as  and  respectively, which are illustrated with Fig.6. As being marked via the rectangular frames there are four regions where obvious abrupt changes happen, and correspondingly the lane departure is being occurred indeed, the hypothesis that the motion model of the lanes is uniform and linear does not hold at this point. After delivering out an alarm the HK-LDWS reset itself. a (a) (b) (c) Figure 4: The extracted lines and the estimated lines with different a assignments. a effective detection rate ( e dr ) time consumption per frame ( ft ) /ms number of missing alarms ( an ) mean standard deviation 0.3 3.2537 2.0784 337 327 97.03% 45.13 0 0.4 3.4178 2.1891 337 322 95.55% 44.39 0 0.5 3.2701 2.3588 337 324 96.14% 33.92 0 0.6 7.8635 11.5493 337 262 77.74% 30.86 12 0.7 13.6823 50.2165 337 187 55.49% 29.05 27 Table 1: Test results for different truncated proportion coefficient assignments. d v fN e fN (a) the curves of  (b) the curves of  Figure 5: The curve of lines parameter. 288 Informatica 41 (2017) 283–288 M. Liang et al. 4 Conclusion HK-LDWS is proposed as a method of lane departure warning based on Kalman filter-based matching and tracking. The pre-processing module gives out the truncated binary images for the subsequent detection module, which extract the lane lines by Hough transformation. And then Kalman filter is explored to track the extracted lines based on the assumption that the lines are moving linearly and continuously. Finally, the lane departure warning algorithm based on lateral distance is realized to deliver out deviation alarms. The actual road test results show that HK-LDWS takes less than 35 milliseconds for per frame processing, can accurately and quickly track lanes and make all departure warning correctly. Its performance of time consumption and tracking accuracy fit for the actual requirements. It’s concluded that the proposed HK-LDWS is an efficient solution for the lane departure warning problems. Time series based image analysis using different pre-processing algorithms need to be studied in future work. 5 Acknowledgement This work was supported in part by the Fundamental Research Funds for the Central Universities (Grant No. 310824162022) and National Natural Science Foundation of China (Grant No. 61201406). 6 References [1] J. M. Clanton, D. M. Bevly and A. S. Hodel. A Low- Cost Solution for an Integrated Multisensor Lane Departure Warning System, IEEE Transactions on Intelligent Transportation Systems, 10(1): 47 – 59, 2009. [2] Marcello Cinque, Antonio Coronato, Alessandro Testa. On Dependability Issues in Ambient Intelligence Systems, International Journal of Ambient Computing and Intelligence, 3(3): 18-27, 2011. [3] B. Chen, Lane recognition and departure warning based on hyperbolic model, Journal of Computer Applications, 33(9): 2562-2565, 2013. [4] T. Liu, N. Zheng and H. Cheng. A novel approach of road recognition based on deformable template and genetic algorithm, in Proceedings Of the 2003 IEEE International Conference on Intelligent Transportation Systems, Piscataway, NJ, USA, Vol.2, pp. 1251-1256, 2003. [5] Y. Wang, E. K. Teoh and D. Shen. Lane detection and tracking using B-Snake, Image & Vision Computing, 22(4): 269–280, 2004. [6] J. Wang, C. Lin and S. Chen. Applying fuzzy method to vision-based lane detection and departure warning system, Expert systems with applications, 37(7): 113-126, 2010. [7] S. Mammar, S. Glaser and M. Netto. Time to line crossing for lane departure avoidance: a theoretical study and an experimental setting, IEEE Transactions on Intelligent Transportation Systems, 7(7): 226-241, 2006. [8] Sudipta Ghosh, Debasish Kundu, and Gopal Paul. A Fuzzy Logic Approach in Emotion Detection and Recognition and Formulation of an Odor-Based Emotional Fitness Assistive System, International Journal of Synthetic Emotions (IJSE), 6(2): 14-34, 2015. [9] Nilanjan Dey, Moumita Pal, Achintya Das. A Session Based Blind Watermarking Technique Within the NROI of Retinal Fundus Images for Authencation Using DWT, Spread Spectrum and Harris Corner Detection, International Journal of Modern Engineering Research (IJMER), 3(3): 749- 757, 2012. [10] H. Tian, S. K. Lam and T. Srikanthan. Implementing Otsu's thresholding process using area-time efficient logarithmic approximation unit, in Proceedings of 2003 International Symposium on Circuits & Systems, vol.4, IV-21-IV-24, 2003. [11] S. K. Lee, W. Kwon and J. W. Lee. A vision based lane departure warning system, Proc. Of the 1999 IEEE/RSJ International Conference on Intelligent Robots & Systems, pp.160-165, 1999. [12] C. Mei, J. Todd and P. Dean. AURORA: A Vision Based Roadway Departure Warning System, Carnegie Mellon University technical report, 1997. [13] P. Hsiao, K. Hung, S. Huang, W. Kao, C. Hsu and Y. Yu. An embedded lane Departure Warning System, Proc. IEEE 15th International Symposium on Consumer Electronics (ISCE), Singapore, pp.162- 165, 2011. (a) (b) Figure 6: The residuals of Kalman filter during tracking with the situation 0.5a  .  