# A Real-Time Lane Detection Algorithm Based on Intelligent CCD Parameters Regulation

Authors: Ping-shu Ge; Lie Guo; Guo-kai Xu; Rong-hui Zhang; Tao Zhang
Journal: Discrete Dynamics in Nature and Society
 (2012)

---

## Abstract

Lane departure warning system (LDWS) has been regarded as an efficient method to lessen the damages of road traffic accident resulting from driver fatigue or inattention. Lane detection is one of the key techniques for LDWS. To overcome the contradiction between complexity of algorithm and the real-time requirement for vehicle onboard system, this paper introduces a new lane detection method based on intelligent CCD parameters regulation. In order to improve the real-time capability of the system, a CCD parameters regulating method is proposed which enhances the contrast between lane line and road surfaces and reduces image noise, so it lays a good foundation for the following lane detection. Hough transform algorithm is improved by selection and classification of seed points. Finally the lane line is extracted through some restrictions. Experimental results verify the effectiveness of the proposed method, which improves not only real-time capability but also the accuracy of the system.


---

## Body

## 1. Introduction

With the rapid development of expressway and the growth of motor vehicle quantities, the traffic accidents, especially mass traffic accidents, are increasing and become one of the most serious problems around the world [1–4]. For low-income and middle-income countries, this situation is much worse. A report from World Health Organization (WHO) points out that over 90% of the world’s fatalities on the roads occur in low-income and middle-income countries, which have only 48% of the world’s registered vehicles. It has been estimated that, unless immediate action is taken, road traffic deaths will rise to the fifth leading cause of death by the year 2030, resulting in an estimated 2.4 million fatalities per year [5]. The global status report on road safety clearly shows that significantly more action is needed to make the world’s roads safer. At present, the increase trend of traffic accidents and causalities in China has been slowed down to some extent and shows a declining tendency, but the situation is far away from being optimistic [6].To lessen the damages resulting from the road traffic accidents and save more lives, the reasons and factors should be analyzed and summarized. There are a number of factors which cause the traffic accidents, ranging from driver behavior to mechanical failure, environmental conditions, and roads design [7–9]. Many works have been done to investigate ways of developing a vehicle driving assistance system to improve its safety. Among those factors resulting in serious accidents, driver fatigue or inattention contribute a considerable portion [10, 11]. Driving is a complex process which involves eye-hand-foot coordination. In many cases, the driver falls asleep making the vehicle to leave its designated lane and possibly causing an accident. NHTSA estimated that running off the road caused about 28% of fatal vehicle accidents in the US in 2005. Moreover, drowsy, sleeping, or fatigued and inattentive drivers caused about 2.6% and 5.8% of the fatal crashes, respectively [12, 13]. Further research is needed to improve driver’s behavior and driving activities with the help of other advanced techniques.In order to prevent this type of accident, researchers have proposed a variety of solutions and technologies to predict and detect unintended lane departure events to warn drivers about such events. Lane departure warning system (LDWS) has been proposed for this purpose, to warn the driver as soon as a vehicle begins to inadvertently drift out of its driving lane or to automatically take steps to ensure that the vehicle stays in correct lane [14]. The currently available LDWSs on the markets are forward-looking vision-based systems and are mainly applied to prestige car, such as BMW, Mercedes-Benz, and so on. In order to reduce the traffic accidents, the LDWS needs to adapt all types of vehicle rather than some certain kinds of vehicles. Although many researchers have proposed several advanced algorithms to improve the system performance [15, 16], there still exist the following bottleneck problems:(1)
Lane detection should adapt to various conditions. Lane detection is a main task of LDWS, and the accuracy of detection is foundation and prerequisite to realize its warning function. Several algorithms have been proposed and their differences are mainly consisting in image preprocessing, lane model, selected model fitting method, and tracking strategy [17, 18]. However, it is difficult to be performed with a high detection rate in complex situations involving shadows, varying illumination conditions, bad conditions of road paintings and kinds of lane marks such as solid lines, segment lines, double yellow lines, pavement or physical barriers. Therefore, how to make the detection algorithm accommodate the complex environment is an important issue.(2)
The LDWS has to meet the requirements such as robust, low cost, compact, low dissipation, and real time. Some of these requirements need to be accomplished by algorithm, while the other can be achieved from the hardware device. In [19], an adaptive DSP-based LDWS was introduced with its operating frequency of 600 MHz and the lane marking detection speed of 35 f/s. The system function is compact but the price is slightly high. In addition, researchers use FPGA devices or other low-cost and low-power consumption architectures to develop the systems [20, 21]. However, the contradiction between complexity of algorithm and the memory of hardware is very outstanding.To overcome the above difficulty, some strategies should be developed to make the system real time and robust, which can adapt to real road environments. This paper aims to develop a real-time lane detection algorithm based on intelligent regulated CCD parameters, which can effectively solve the conflicts between real time and robustness of the LDWS. The contents of this paper are organized as follows. Section2 introduces an intelligent regulated CCD parameters algorithm. After analyzing the advantages and disadvantages of traditional Hough transform, an improved Hough transform algorithm is proposed in Section 3. Section 4 verifies the effectiveness of the proposed algorithm through road experiments, and some conclusions are given in Section 5.


## 2. CCD Parameters Regulation Based on Feature Regions

The LDWS system needs a great demand on the CCD image grabbing speed. To achieve this, CCD employs a kind of parameter control technique, that is to say, the gain, bright, and shutter of CCD can be programmed. Therefore, the CCD parameters can be regulated by programmed in real time, which is helpful to image segmentation, reducing noise as well as improving the reliability and instantaneity of lane detection algorithms. Moreover, it can heighten the contrast between road surfaces and lane marks.The CCD model used in our LDWS is BaslerA602f and its parameters can be regulated through IEEE1394 video capture board connected to an imbedded computer [22]. The purpose of CCD parameters regulation can be realized by defining some feature regions and calculating the eigenvalues of those regions.


### 2.1. Feature Regions Division and Eigenvalues Computation

As showed in Figure1, the image to be processed is divided into six feature regions from region A to F. The size of image is 320 × 240 pixels.Schematic of feature regions division in detection status.
(a)
(b)RegionA is the upper center 1/4 region of the image. The gray mean value μa and variance σa of this region indicate the brightness of sky. While region B is the bottom center 1/4 region of the image, whose gray mean value μb and variance σb indicate the darkness of the road surface. They can be calculated using
(2.1)μa=323×w×h×∑f(x,y)σa=32×∑[f(x,y)-μa]23×w×h-3w16≤x≤3w16,34h≤y≤h,μb=323×w×h×∑f(x,y)σb=32×∑[f(x,y)-μb]23×w×h-3w16≤x≤3w16,0≤y≤h4,
where w and h are the width and height of image, respectively; f(x,y) is the gray value of pixel (x,y).Usually, the lane mark is included in regionsC, D, E, and F. To a certain extent, their gray mean values and variances can indicate the light and shade condition of images around the lane marks. The positions of the lane marks are not changeless as the vehicle moving. So the regions C, D, E, and F, which called the lane marks feature regions, will change their position and information when the vehicle is moving. The sizes of those regions can be divided in accordance with the detection and tracking status of the lane marks [23].If the lane is during the detecting status, that is to say, we have no idea about the lane marks position and its gray information. The size and position of those feature regions are uncertain and can be determined on the basis of practical experimental data. As shown in Figure1, they are defined as follows. The width QS is 160 pixels and QS is in the center of the image. Points Q and S are symmetric with respect to y-axis. The angle between PQ and x-axis is 45° and PQ is parallel to MN. The left lane marks may line in the region of PMQN. Region of PMQN is divided into regions C and D by line of IG, which may contain the detail line mark information and the macroscopic view of the lane, respectively. In the coordinate system xoy displayed in Figure 1, the coordinates for points Q, N, and S are (−80, 120), (0, 120), (80, 120) respectively. The function for PQ can be expressed by y=x+120. Then the eigenvalues of regions C and D are calculated as
(2.2)uc=∑y=0h/6∑x=-w/2y-120f(x,y)s1+∑y=h/6h/4∑x=y-200y-120f(x,y)s2,σc=∑y=0h/6∑x=-w/2y-120[f(x,y)-uc]2s1+∑y=h/6h/4∑x=y-200y-120[f(x,y)-uc]2s2,(2.3)ud=∑y=h/4h/2∑x=y-200y-120f(x,y)sd,σd=∑y=h/4h/2∑x=y-200y-120[f(x,y)-ud]2sd,
where s1 and s2 are pixel numbers in regions PHM and PIGH, respectively; sd is the pixel number in region D.The angle betweenST and x-axis is 135° and ST is parallel to NL. The gray mean values and variances of regions E and F can be calculated by the same means.If the lane is during the tracking status, that is to say, we have gotten prior parameters of the lane to be detected. In this condition, the instantaneity of the system is improved by building some dynamic trapezoid feature regions. Due to the effect of projection, there are some differences in deflected distance between the bottom and the centre of the image. Therefore, we build the dynamic trapezoid feature areas taking advantage of 6 specialized feature points [24]. As shown in Figure 2, point O is taken as the previous lane vanishing point, with its coordinate is (Ox,Oy). Points L(Lx,Ly) and R(Rx,Ry) are the endpoint of the left lane and the right lane, respectively. Then offset point O with 20 pixels to the left and right, respectively, we can get points L1(Ox-20,Oy) and R1(Ox+20,Oy). Offset point L with 30 pixels up and connect this point to L1, the crosspoint for this line with the image margin is L2. Offset point L with 30 pixels down and connect this point to R1, the crosspoint for this line with the image margin is L3. At the same way, we will get points R2 and R3. In the tracking condition, a moving vehicle will change the lane position, which leads to the changing of these 6 feature points. As a result, the feature regions determined by these points are dynamic.Schematic of feature regions division in tracking status.
(a)
(b)


### 2.2. CCD Parameters Regulation

Once the feature regions are determined and their eigenvalues are calculated, the CCD parameters can be regulated according to those values. The detailed CCD parameters regulation is as follows.(1)
Computing the eigenvalues of those feature regions according to the lane detection and tracking status.(2)
Previous experiments in different illumination conditions indicate that it is easy to make a decision between lane marks and road surfaces when the mean values of regionsC, D, E, and F are in range of [60,100] and their variances in [11, 27]. So we will not change the CCD parameters and continuous capturing images when the gray level mean values gotten are in range [60, 100] and their variances in [11, 27]. If all of the mean values are below 60 or higher than 100, we will change the CCD gain, brightness, and shutter by a certain step size till their eigenvalues are in proper range.(3)
Saving the current parameters and capture the next frame images.Figure3 shows the image and its segmentation results after the CCD parameters regulation in the condition of strong illumination. In these images showed below, the left one is the image based on CCD parameters regulation and the right one is the corresponding segmentation result.Image captured after the CCD parameters regulation and its segmentation result.
(a)
(b)
(c)
(d)Above images show that the contrast between lane marks and the road surfaces has been enhanced after the CCD parameters regulation. The segmentation of the image is pretty well and there is little background noise.


## 2.1. Feature Regions Division and Eigenvalues Computation

As showed in Figure1, the image to be processed is divided into six feature regions from region A to F. The size of image is 320 × 240 pixels.Schematic of feature regions division in detection status.
(a)
(b)RegionA is the upper center 1/4 region of the image. The gray mean value μa and variance σa of this region indicate the brightness of sky. While region B is the bottom center 1/4 region of the image, whose gray mean value μb and variance σb indicate the darkness of the road surface. They can be calculated using
(2.1)μa=323×w×h×∑f(x,y)σa=32×∑[f(x,y)-μa]23×w×h-3w16≤x≤3w16,34h≤y≤h,μb=323×w×h×∑f(x,y)σb=32×∑[f(x,y)-μb]23×w×h-3w16≤x≤3w16,0≤y≤h4,
where w and h are the width and height of image, respectively; f(x,y) is the gray value of pixel (x,y).Usually, the lane mark is included in regionsC, D, E, and F. To a certain extent, their gray mean values and variances can indicate the light and shade condition of images around the lane marks. The positions of the lane marks are not changeless as the vehicle moving. So the regions C, D, E, and F, which called the lane marks feature regions, will change their position and information when the vehicle is moving. The sizes of those regions can be divided in accordance with the detection and tracking status of the lane marks [23].If the lane is during the detecting status, that is to say, we have no idea about the lane marks position and its gray information. The size and position of those feature regions are uncertain and can be determined on the basis of practical experimental data. As shown in Figure1, they are defined as follows. The width QS is 160 pixels and QS is in the center of the image. Points Q and S are symmetric with respect to y-axis. The angle between PQ and x-axis is 45° and PQ is parallel to MN. The left lane marks may line in the region of PMQN. Region of PMQN is divided into regions C and D by line of IG, which may contain the detail line mark information and the macroscopic view of the lane, respectively. In the coordinate system xoy displayed in Figure 1, the coordinates for points Q, N, and S are (−80, 120), (0, 120), (80, 120) respectively. The function for PQ can be expressed by y=x+120. Then the eigenvalues of regions C and D are calculated as
(2.2)uc=∑y=0h/6∑x=-w/2y-120f(x,y)s1+∑y=h/6h/4∑x=y-200y-120f(x,y)s2,σc=∑y=0h/6∑x=-w/2y-120[f(x,y)-uc]2s1+∑y=h/6h/4∑x=y-200y-120[f(x,y)-uc]2s2,(2.3)ud=∑y=h/4h/2∑x=y-200y-120f(x,y)sd,σd=∑y=h/4h/2∑x=y-200y-120[f(x,y)-ud]2sd,
where s1 and s2 are pixel numbers in regions PHM and PIGH, respectively; sd is the pixel number in region D.The angle betweenST and x-axis is 135° and ST is parallel to NL. The gray mean values and variances of regions E and F can be calculated by the same means.If the lane is during the tracking status, that is to say, we have gotten prior parameters of the lane to be detected. In this condition, the instantaneity of the system is improved by building some dynamic trapezoid feature regions. Due to the effect of projection, there are some differences in deflected distance between the bottom and the centre of the image. Therefore, we build the dynamic trapezoid feature areas taking advantage of 6 specialized feature points [24]. As shown in Figure 2, point O is taken as the previous lane vanishing point, with its coordinate is (Ox,Oy). Points L(Lx,Ly) and R(Rx,Ry) are the endpoint of the left lane and the right lane, respectively. Then offset point O with 20 pixels to the left and right, respectively, we can get points L1(Ox-20,Oy) and R1(Ox+20,Oy). Offset point L with 30 pixels up and connect this point to L1, the crosspoint for this line with the image margin is L2. Offset point L with 30 pixels down and connect this point to R1, the crosspoint for this line with the image margin is L3. At the same way, we will get points R2 and R3. In the tracking condition, a moving vehicle will change the lane position, which leads to the changing of these 6 feature points. As a result, the feature regions determined by these points are dynamic.Schematic of feature regions division in tracking status.
(a)
(b)


## 2.2. CCD Parameters Regulation

Once the feature regions are determined and their eigenvalues are calculated, the CCD parameters can be regulated according to those values. The detailed CCD parameters regulation is as follows.(1)
Computing the eigenvalues of those feature regions according to the lane detection and tracking status.(2)
Previous experiments in different illumination conditions indicate that it is easy to make a decision between lane marks and road surfaces when the mean values of regionsC, D, E, and F are in range of [60,100] and their variances in [11, 27]. So we will not change the CCD parameters and continuous capturing images when the gray level mean values gotten are in range [60, 100] and their variances in [11, 27]. If all of the mean values are below 60 or higher than 100, we will change the CCD gain, brightness, and shutter by a certain step size till their eigenvalues are in proper range.(3)
Saving the current parameters and capture the next frame images.Figure3 shows the image and its segmentation results after the CCD parameters regulation in the condition of strong illumination. In these images showed below, the left one is the image based on CCD parameters regulation and the right one is the corresponding segmentation result.Image captured after the CCD parameters regulation and its segmentation result.
(a)
(b)
(c)
(d)Above images show that the contrast between lane marks and the road surfaces has been enhanced after the CCD parameters regulation. The segmentation of the image is pretty well and there is little background noise.


## 3. Lane Detection Using Improved Hough Transform

### 3.1. Analysis of Traditional Hough Transform

As the images collected on the highway are very complicated, there will be great error if we use linear fitting method to detect the lane. On the contrary, Hough transform is robust to small change of the image noise, and it is good at handling over the conditions that the object is partly occluded and covered [25]. In the image space, the straight line can be described as y=mx+b and can be graphically plotted for each pair of image points (x,y). The main idea of Hough transform is to consider the characteristics of the straight line not as image points (x1,y1), (x2,y2), etc.) but instead, in terms of its parameters, that is, the slope parameter m and the intercept parameter b. For computational reasons, a different pair of parameters in polar coordinates, denoted by ρ and θ, is used for the line in the Hough transform. ρ is the length of a normal from the origin to this line and θ is the orientation of ρ with respect to the x-axis. The implementation procedure using traditional Hough transform to extract a straight line is as follows.(1)
Quantizeρ and θ, build a two-dimensional accumulate array M(ρ,θ) in the parameter map of (ρ,θ), as shown in Figure 4. The span for parameter (ρ,θ) are separately [ρmin,ρmax] and [θmin,θmax].(2)
Initialize the two-dimensional arrayM(ρ,θ), search the white edge in the image in sequence. To every white edge in the binarization image, let θ can be any value in the axis θ. Then calculate the value ρ according to the equation ρ=xcosθ+ysinθ. Accumulate the array M on the basis of the value of θ and ρ:M(ρ,θ)=M(ρ,θ)+1.(3)
Figure out the maximum value in the transform domain and record it.(4)
Clear the maximum value and their values of its neighborhood points.(5)
Figure out all the maximum points successively and record them.(6)
Seek for the recent lane line according to some certain constraints.Figure 4
Accumulate arrayM(ρ,θ)in the parameter map of (ρ,θ).According to this procedure, the traditional Hough transform has some disadvantages as follows when detecting the road lane.(1)
As every white point should be involved in the computing of space transform, the calculated amount increases, and it is time consuming. We can overcome this by adjusting the CCD parameters, as shown in the Figure5. We compare the lane detection using the binarization images collected at the same place. The left images in Figure 5 show the situation without and with adjusting CCD parameters, respectively. Through comparing these two figures, we discover that after the use of CCD parameter adjusting algorithm, the points involving in the Hough transform decrease clearly, which verifies the effectiveness of CCD parameter adjusting algorithm.(2)
Due to the quantizing of parametersρ and θ, the peak value near one straight line is always very large after finding the peak value; we should clear the neighborhood values and look for next line. But it is not easy to perfectly define the neighborhood range, if the neighborhood is too small, the line detected next time will be overlapped on the already existed line, if the neighborhood is too large, the nearby waiting to be detected points will be clear up, and next time, you will not find any point. It is more obvious when there exist several similar lines at the same time and they are close to each other, as shown in the middle and right column of Figure 5.Peak value distributions for traditional Hough transform.
(a)
Results for image without adjusting CCD parameters
(b)
Results for image with adjusting CCD parameters


### 3.2. Improved Hough Transform for Lane Detection

Facing the disadvantages, many researchers have proposed some improved methods. Those methods can be summarized to two kinds [26, 27]. The one is to classify the points in the image before conducting Hough transform, such as using the gradient direction to reduce the number of votes. This kind can reduce the computation time and has the interesting effect of reducing the number of useless votes, thus enhancing the visibility of the spikes corresponding to real lines in the image. The key technique is to select proper point classifying method. The other is to improve the transform voting scheme, such as Kernel-based Hough transform [28]. This approach can significantly improve the performance of the voting scheme and makes the transform more robust to the detection of spurious lines. But the computation time is huge, which is improper to the LDWS.After analyzing the traditional Hough transform, this paper proposes a new lane identification method. Specifically, seed points of lane are selected firstly and then utilize Hough transform for seed points of every group. Figure6 shows the pictures after threshold and noise filtering, represents three typical situations, the normal, existing similar interference and some deviation happens.Road images after threshold and noise filtering. (a) Normal condition, (b) existing interference, (c) Deviation happens.
(a)
(b)
(c)


#### 3.2.1. Selection and Classification of the Seed Points

As indicated in Figure6, the lane has two main features for each scan line, because the lane has width and gray value of each side has mutation. These two features can be the criterion for selecting the lane seed points and any one possesses the features can be seen as the lane seed points. The seed points between two scanning lines can be put into one seed points group, if their pixel difference is less than a certain threshold value, otherwise they will be put into a new group. The specific steps are as follows.Firstly, take a two-dimensional arraySeedGroup[g×r] represents the x-coordinate of the seed points. Among which, g is the amount of the seed points arrays, which is also the maximum lane line numbers. According to the CCD equipment view and the highway scenario, the maximum value of g is set 4. r represents the amount of the scan lines and also the seed points y-coordinate. As the lane marks are always in the lower half of the picture, we set the value of r to a half of image height, that is, r=120. This array is initialized to be 0.Secondly, scan the image from left to right and bottom to top. When the scanning encounters a white point(xj,yj), goes on with the scanning, and starts to count numbers, ends when encounters a point is not a white one. Then number of the white points is s, take the middle value of it as the seed point
(3.1)xs=xj+s2siseven,xs=xj+(s+1)2sisodd.Therefore, the seed point’s coordinate is(xs,yj). Considering the case that the lane is discontinuous which may lead to seed points separated by several scanning lines, we classify them by taking the strategy as follows. According to the CCD perspective principle, when yj is much larger, the actual distance each pixel represents is much farther. so yj is divided into two parts: If yj<30, we should compare the SeedGroup values of all lane arrays before yj with xs. If it is less than a certain threshold value (when the CCD is mounted on the vehicle basically horizontal, through test the threshold is set to be 20), it classifies the seed point to this lane array. If it is larger than a certain threshold value, it indicates that a new lane is appearing. We can classify the seed point to the new lane array. Else if yj<30, we should compare the SeedGroup values of the first 30 lane arrays before yj with xs. Classify principle is same as above.Suppose that the lane array which the seed points are classified to isgi. We should retain the data of lane array (SeedGroup[gi×yj], yj). And then continue scan starts from the 0 pixel downward, until to finish the current scanning.Finally, continue to scan up until to complete all seed points’ choice and classification. Figure7 displays the nonzero seed points arrays SeedGroup([gi×yj],yj)(i∈(0,g),j∈(0,r)) for the image in Figure 6. Each array represents a lane. As can be seen, this method can accurately obtain the points of center lanes, and classify the points accurately.Seed points classification results for images in Figure6.
(a)
Results for Figure6(a)
(b)
Results for Figure6(b)
(c)
Results for Figure6(c)


#### 3.2.2. Utilizing Hough Transform for the Seed Points of Each Group

Once the seed points have been selected and classified, and each lane can be determined utilizing Hough transform according those seed points of each group. Quantify the parameter space(ρ,θ) and build a two-dimensional accumulate array, then initialize the two-dimensional array at first and utilize Hough transform for the seed points of each group. We should let each point take all value on the θ axis and calculate the value of the ρ. Compare the size of the array element to get maximum value. (ρi,θj) corresponding with maximum value is the parameter corresponded with the required straight line. So we just find out the parameter (ρi,θj) of each lane.


#### 3.2.3. Current Lane Detection with Angle Constraints

Commonly, there may exist more than one lane in the image therefore, we need to define a certain constraint to extract the current lane accurately. Because of the CCD projection transformation, the lane disappeared in a point in the image. Figure8 displays the angular relationship diagram for multilane in the image. As shown in this figure, the angle for the left lane is θl∈(π/2,π) and for the right lane is θr∈(0,π/2). The farther away from the centerline of the image, the smaller is θl and the larger is θr. Therefore, we can extract the current lane in accordance with this method.Figure 8
Diagram of angular relationship for multilane.When exploiting the improved Hough transform acquiring the parameters of each straight lane, the minimum in the angle of(0,π/2) and the maximum in (π/2,π) can be determined. Then the current lane can be detected according to the parameter map (ρ,θ). Figure 9 displays the current lane detection results.Detection results with angle constraints.
(a)
(b)
(c)


## 3.1. Analysis of Traditional Hough Transform

As the images collected on the highway are very complicated, there will be great error if we use linear fitting method to detect the lane. On the contrary, Hough transform is robust to small change of the image noise, and it is good at handling over the conditions that the object is partly occluded and covered [25]. In the image space, the straight line can be described as y=mx+b and can be graphically plotted for each pair of image points (x,y). The main idea of Hough transform is to consider the characteristics of the straight line not as image points (x1,y1), (x2,y2), etc.) but instead, in terms of its parameters, that is, the slope parameter m and the intercept parameter b. For computational reasons, a different pair of parameters in polar coordinates, denoted by ρ and θ, is used for the line in the Hough transform. ρ is the length of a normal from the origin to this line and θ is the orientation of ρ with respect to the x-axis. The implementation procedure using traditional Hough transform to extract a straight line is as follows.(1)
Quantizeρ and θ, build a two-dimensional accumulate array M(ρ,θ) in the parameter map of (ρ,θ), as shown in Figure 4. The span for parameter (ρ,θ) are separately [ρmin,ρmax] and [θmin,θmax].(2)
Initialize the two-dimensional arrayM(ρ,θ), search the white edge in the image in sequence. To every white edge in the binarization image, let θ can be any value in the axis θ. Then calculate the value ρ according to the equation ρ=xcosθ+ysinθ. Accumulate the array M on the basis of the value of θ and ρ:M(ρ,θ)=M(ρ,θ)+1.(3)
Figure out the maximum value in the transform domain and record it.(4)
Clear the maximum value and their values of its neighborhood points.(5)
Figure out all the maximum points successively and record them.(6)
Seek for the recent lane line according to some certain constraints.Figure 4
Accumulate arrayM(ρ,θ)in the parameter map of (ρ,θ).According to this procedure, the traditional Hough transform has some disadvantages as follows when detecting the road lane.(1)
As every white point should be involved in the computing of space transform, the calculated amount increases, and it is time consuming. We can overcome this by adjusting the CCD parameters, as shown in the Figure5. We compare the lane detection using the binarization images collected at the same place. The left images in Figure 5 show the situation without and with adjusting CCD parameters, respectively. Through comparing these two figures, we discover that after the use of CCD parameter adjusting algorithm, the points involving in the Hough transform decrease clearly, which verifies the effectiveness of CCD parameter adjusting algorithm.(2)
Due to the quantizing of parametersρ and θ, the peak value near one straight line is always very large after finding the peak value; we should clear the neighborhood values and look for next line. But it is not easy to perfectly define the neighborhood range, if the neighborhood is too small, the line detected next time will be overlapped on the already existed line, if the neighborhood is too large, the nearby waiting to be detected points will be clear up, and next time, you will not find any point. It is more obvious when there exist several similar lines at the same time and they are close to each other, as shown in the middle and right column of Figure 5.Peak value distributions for traditional Hough transform.
(a)
Results for image without adjusting CCD parameters
(b)
Results for image with adjusting CCD parameters


## 3.2. Improved Hough Transform for Lane Detection

Facing the disadvantages, many researchers have proposed some improved methods. Those methods can be summarized to two kinds [26, 27]. The one is to classify the points in the image before conducting Hough transform, such as using the gradient direction to reduce the number of votes. This kind can reduce the computation time and has the interesting effect of reducing the number of useless votes, thus enhancing the visibility of the spikes corresponding to real lines in the image. The key technique is to select proper point classifying method. The other is to improve the transform voting scheme, such as Kernel-based Hough transform [28]. This approach can significantly improve the performance of the voting scheme and makes the transform more robust to the detection of spurious lines. But the computation time is huge, which is improper to the LDWS.After analyzing the traditional Hough transform, this paper proposes a new lane identification method. Specifically, seed points of lane are selected firstly and then utilize Hough transform for seed points of every group. Figure6 shows the pictures after threshold and noise filtering, represents three typical situations, the normal, existing similar interference and some deviation happens.Road images after threshold and noise filtering. (a) Normal condition, (b) existing interference, (c) Deviation happens.
(a)
(b)
(c)


### 3.2.1. Selection and Classification of the Seed Points

As indicated in Figure6, the lane has two main features for each scan line, because the lane has width and gray value of each side has mutation. These two features can be the criterion for selecting the lane seed points and any one possesses the features can be seen as the lane seed points. The seed points between two scanning lines can be put into one seed points group, if their pixel difference is less than a certain threshold value, otherwise they will be put into a new group. The specific steps are as follows.Firstly, take a two-dimensional arraySeedGroup[g×r] represents the x-coordinate of the seed points. Among which, g is the amount of the seed points arrays, which is also the maximum lane line numbers. According to the CCD equipment view and the highway scenario, the maximum value of g is set 4. r represents the amount of the scan lines and also the seed points y-coordinate. As the lane marks are always in the lower half of the picture, we set the value of r to a half of image height, that is, r=120. This array is initialized to be 0.Secondly, scan the image from left to right and bottom to top. When the scanning encounters a white point(xj,yj), goes on with the scanning, and starts to count numbers, ends when encounters a point is not a white one. Then number of the white points is s, take the middle value of it as the seed point
(3.1)xs=xj+s2siseven,xs=xj+(s+1)2sisodd.Therefore, the seed point’s coordinate is(xs,yj). Considering the case that the lane is discontinuous which may lead to seed points separated by several scanning lines, we classify them by taking the strategy as follows. According to the CCD perspective principle, when yj is much larger, the actual distance each pixel represents is much farther. so yj is divided into two parts: If yj<30, we should compare the SeedGroup values of all lane arrays before yj with xs. If it is less than a certain threshold value (when the CCD is mounted on the vehicle basically horizontal, through test the threshold is set to be 20), it classifies the seed point to this lane array. If it is larger than a certain threshold value, it indicates that a new lane is appearing. We can classify the seed point to the new lane array. Else if yj<30, we should compare the SeedGroup values of the first 30 lane arrays before yj with xs. Classify principle is same as above.Suppose that the lane array which the seed points are classified to isgi. We should retain the data of lane array (SeedGroup[gi×yj], yj). And then continue scan starts from the 0 pixel downward, until to finish the current scanning.Finally, continue to scan up until to complete all seed points’ choice and classification. Figure7 displays the nonzero seed points arrays SeedGroup([gi×yj],yj)(i∈(0,g),j∈(0,r)) for the image in Figure 6. Each array represents a lane. As can be seen, this method can accurately obtain the points of center lanes, and classify the points accurately.Seed points classification results for images in Figure6.
(a)
Results for Figure6(a)
(b)
Results for Figure6(b)
(c)
Results for Figure6(c)


### 3.2.2. Utilizing Hough Transform for the Seed Points of Each Group

Once the seed points have been selected and classified, and each lane can be determined utilizing Hough transform according those seed points of each group. Quantify the parameter space(ρ,θ) and build a two-dimensional accumulate array, then initialize the two-dimensional array at first and utilize Hough transform for the seed points of each group. We should let each point take all value on the θ axis and calculate the value of the ρ. Compare the size of the array element to get maximum value. (ρi,θj) corresponding with maximum value is the parameter corresponded with the required straight line. So we just find out the parameter (ρi,θj) of each lane.


### 3.2.3. Current Lane Detection with Angle Constraints

Commonly, there may exist more than one lane in the image therefore, we need to define a certain constraint to extract the current lane accurately. Because of the CCD projection transformation, the lane disappeared in a point in the image. Figure8 displays the angular relationship diagram for multilane in the image. As shown in this figure, the angle for the left lane is θl∈(π/2,π) and for the right lane is θr∈(0,π/2). The farther away from the centerline of the image, the smaller is θl and the larger is θr. Therefore, we can extract the current lane in accordance with this method.Figure 8
Diagram of angular relationship for multilane.When exploiting the improved Hough transform acquiring the parameters of each straight lane, the minimum in the angle of(0,π/2) and the maximum in (π/2,π) can be determined. Then the current lane can be detected according to the parameter map (ρ,θ). Figure 9 displays the current lane detection results.Detection results with angle constraints.
(a)
(b)
(c)


## 3.2.1. Selection and Classification of the Seed Points

As indicated in Figure6, the lane has two main features for each scan line, because the lane has width and gray value of each side has mutation. These two features can be the criterion for selecting the lane seed points and any one possesses the features can be seen as the lane seed points. The seed points between two scanning lines can be put into one seed points group, if their pixel difference is less than a certain threshold value, otherwise they will be put into a new group. The specific steps are as follows.Firstly, take a two-dimensional arraySeedGroup[g×r] represents the x-coordinate of the seed points. Among which, g is the amount of the seed points arrays, which is also the maximum lane line numbers. According to the CCD equipment view and the highway scenario, the maximum value of g is set 4. r represents the amount of the scan lines and also the seed points y-coordinate. As the lane marks are always in the lower half of the picture, we set the value of r to a half of image height, that is, r=120. This array is initialized to be 0.Secondly, scan the image from left to right and bottom to top. When the scanning encounters a white point(xj,yj), goes on with the scanning, and starts to count numbers, ends when encounters a point is not a white one. Then number of the white points is s, take the middle value of it as the seed point
(3.1)xs=xj+s2siseven,xs=xj+(s+1)2sisodd.Therefore, the seed point’s coordinate is(xs,yj). Considering the case that the lane is discontinuous which may lead to seed points separated by several scanning lines, we classify them by taking the strategy as follows. According to the CCD perspective principle, when yj is much larger, the actual distance each pixel represents is much farther. so yj is divided into two parts: If yj<30, we should compare the SeedGroup values of all lane arrays before yj with xs. If it is less than a certain threshold value (when the CCD is mounted on the vehicle basically horizontal, through test the threshold is set to be 20), it classifies the seed point to this lane array. If it is larger than a certain threshold value, it indicates that a new lane is appearing. We can classify the seed point to the new lane array. Else if yj<30, we should compare the SeedGroup values of the first 30 lane arrays before yj with xs. Classify principle is same as above.Suppose that the lane array which the seed points are classified to isgi. We should retain the data of lane array (SeedGroup[gi×yj], yj). And then continue scan starts from the 0 pixel downward, until to finish the current scanning.Finally, continue to scan up until to complete all seed points’ choice and classification. Figure7 displays the nonzero seed points arrays SeedGroup([gi×yj],yj)(i∈(0,g),j∈(0,r)) for the image in Figure 6. Each array represents a lane. As can be seen, this method can accurately obtain the points of center lanes, and classify the points accurately.Seed points classification results for images in Figure6.
(a)
Results for Figure6(a)
(b)
Results for Figure6(b)
(c)
Results for Figure6(c)


## 3.2.2. Utilizing Hough Transform for the Seed Points of Each Group

Once the seed points have been selected and classified, and each lane can be determined utilizing Hough transform according those seed points of each group. Quantify the parameter space(ρ,θ) and build a two-dimensional accumulate array, then initialize the two-dimensional array at first and utilize Hough transform for the seed points of each group. We should let each point take all value on the θ axis and calculate the value of the ρ. Compare the size of the array element to get maximum value. (ρi,θj) corresponding with maximum value is the parameter corresponded with the required straight line. So we just find out the parameter (ρi,θj) of each lane.


## 3.2.3. Current Lane Detection with Angle Constraints

Commonly, there may exist more than one lane in the image therefore, we need to define a certain constraint to extract the current lane accurately. Because of the CCD projection transformation, the lane disappeared in a point in the image. Figure8 displays the angular relationship diagram for multilane in the image. As shown in this figure, the angle for the left lane is θl∈(π/2,π) and for the right lane is θr∈(0,π/2). The farther away from the centerline of the image, the smaller is θl and the larger is θr. Therefore, we can extract the current lane in accordance with this method.Figure 8
Diagram of angular relationship for multilane.When exploiting the improved Hough transform acquiring the parameters of each straight lane, the minimum in the angle of(0,π/2) and the maximum in (π/2,π) can be determined. Then the current lane can be detected according to the parameter map (ρ,θ). Figure 9 displays the current lane detection results.Detection results with angle constraints.
(a)
(b)
(c)


## 4. Experiments and Analysis

To verify the proposed lane detection method, several experiments were conducted on images and sequences on real highway scenarios with the lane departure warning system. During the experiment, the driver drives the vehicle cross the lane intentionally to see the system performance. The driving environment is focused on highway with different light conditions. Some typical experiments results for lane detection are shown in Figure10. The left images are the detection results using traditional Hough transform, while the right images display the results using the improved Hough transform. Those entire images are captured after applying the intelligent regulated CCD parameters.Some typical experimental results.
(a)
Detection result under normal environments
(b)
Detection result under strong brightness environments with interference on road
(c)
Detection result when vehicle lane exchangingAs can be seen from Figure10(a), both methods can realize the lane detection under normal environments. The difference lies in the processing time of each image. The average processing time for an image using the traditional Hough transform is about 45 ms. It decreases to 25 ms when using the improved Hough transform. Moreover, the proposed lane detection method can recognize the lane correctly under abnormal environments, such as strong brightness. Even there are interferences on road. While the traditional method fails in this case, as displayed in Figure 10(b). It is important for the LDWS to achieve correct detection of current lane, especially when the vehicle is in process of lane exchanging. The traditional method usually takes the adjacent boundary as the current lane, which may lead to missing alarm and result in serious accident. Fortunately, the improved Hough transform is able to detection the current lane accurately, even if they are dashed lane marks, as shown in Figure 10(c) that may contribute to the importing of angle restraints.Table1 compares the performance of our lane detection method with traditional method. Statistic analysis also indicates that after the CCD parameters regulating, the performances for both of the traditional and improved Hough transform are enhanced. While the proposed Hough transform presents the best performance. As to the weather conditions, cloudy day shows better than sunny day for the reason that the road surface is more dark, which is helpful to enlarge the contrast between the surface and the white lane marks.Table 1
Statistics of our lane detection method.
Method
CCD parameters
Weather
Frames
Hit
Miss
Hit rate
Traditional Hough transform
unregulated
sunny
480
451
29
93.96%
cloudy
256
242
14
94.53%
regulated
sunny
734
711
23
96.87%
cloudy
675
659
16
97.63%
Improved Hough transform
unregulated
sunny
624
607
17
97.28%
cloudy
485
479
6
98.76%
regulated
sunny
738
727
11
98.51%
cloudy
626
621
5
99.20%


## 5. Conclusions

In this paper, a robust lane detection method based on intelligent CCD parameters regulation by combining the improved Hough transform with certain angle restraints is presented. The main contributions of this paper are as follows.(1)
The CCD parameters, such as the brightness, gain, and exposure time, are regulated based on the information in the specialized feature regions. Test results indicate that the adjusting of CCD parameters can enhance the contrast between the lane marks and road surfaces and reduce background noise, which is helpful to improve the real time of the algorithm.(2)
An improved Hough transform algorithm is proposed after analyzing the advantages and disadvantages of traditional one, which optimizes the selection of seeds and introducing the angle constraints.(3)
Several road experiments were conducted to validate the proposed method. Compared with the traditional Hough transform, results show that the improved method can detect the current lane with lower processing time and higher detection accuracy.In this case, the lane model is taken as straight line and ignoring the curve line model that really existing in real environments. In the future work, this case should be taking into account for the lane departure warning system. Moreover, the vehicle steering controlling is necessary according to the lane detection results.



---

*Source: 273164-2012-12-31.xml*