Lane Detection Method of Statistical Hough Transform Based on Gradient Constraint
Peng Yan-zhou, Gao Hong-feng^{*}
College of Information Engineering, Henan University of Science and Technology, Luoyang, China
Email address:
To cite this article:
Peng Yan-zhou, Gao Hong-feng. Lane Detection Method of Statistical Hough Transform Based on Gradient Constraint. International Journal of Intelligent Information Systems. Vol. 4, No. 2, 2015, pp. 40-45. doi: 10.11648/j.ijiis.20150402.12
Abstract: A lane detection method of statistical Hough transform based on gradient constraint is proposed to solve the problem of computational cost and grid quantization precision of classical Hough transform. Statistical Hough transform uses the Gaussian kernel function to model each pixel in the image .The size of initial data set is limited by using the method of gradient constraint. Eventually lane parameters’ continuous probability density function is given. The results of the experimentation show that under highway circumstance the provided method can rapidly and robustly detect the lane.
Keywords: Statistical Hough Transform, Gaussian Kernel Function, Gradient Constraint
1. Introduction
With the increase in the number of vehicles, the number of car accident on highway has increased annually. Many accidents are caused by a lack of awareness about driving conditions due to driver carelessness or visual interference. Lane detection and tracking technology based on visual are the key technology on the applications of driver assistance systems for automobiles [1]. Many researchers have done a lot of work on that [2-8]. Road standard in our country formulates that the highway minimum plane curve radius is 650m.Taking the lane line curvature radius of 650m, 40m bending lane line in front of the vehicle can be approximate to straight lines. The approximation in most cases can be established from the experiment image, and near-field vision can ensure the vehicle’s safety driving. So the linear model is suitable for the standardization highway road detection and near-field vision in the lane line can be obtained by straight lines model fitting.
Lane detection is still a fertile area of machine vision research[9-11]; variations of the Hough transform are still among the most popular and commonly used methods [8]. It transforms the straight line in the image space to corresponding position of a point in the parameter space, and then the position of the point in the parameter space is formed in the peak after cumulative voting. Through the extraction of the peak, the parameters of the line are obtained. In these approaches, the input images are first preprocessed to find edges using a Canny edge detector or steer able filters, followed by a threshold. The classical Hough transform is then used to find straight lines in the binary image.
Classical Hough transformation works well for line finding when the roads are mostly straight; however, it also has shortcomings as the probability density function of the parameters in classical Hough transform is estimated using a discrete two-dimensional histogram [2], Here are two of them: First, in the classical Hough transform, every pixel in the original image space participate in the transformation from image space to parameter space. At the same time, the voting of the parameter point do not always come from the same line in the image space, also may be caused by the chance to arrange of lane marking points which are not in the same straight line. This not only makes the algorithm increased in computational complexity and time-consuming, also lead to the subsequent lower accuracy. Second, for the grid quantization precision in parameter space, classical Hough transform is very difficult to achieve the optimal. If the grid is quantitative too much, that would be result in double counting in a same straight line, thus increasing the computational complexity. If the grid is not quantitative too much, that would be result in a bad space gathering and not getting the right line parameters.
Base on this, the paper models the classical Hough transform parameters by statistical kernel function, and put each pixel’s position and gradient orientation in the image as the observation data. The probability density function of the parameters is continuous and contains more useful information. This also solves the problem of the grid quantitative accuracy effectively. For processing and modeling on every pixel in the image, computational cost is larger. Using the method of gradient threshold limits the size of initial data set. Only keep large gradient pixels modeling by Gaussian kernel function.
This paper is organized as follows. Section 2 introduces the principle of statistical Hough transform. In section 3, the lane detection method of statistical Hough transforms based on gradient constraint is presented. Results and analyses are given in section 4, which introduce experimental results on different road situations. Finally, this paper is concluded in section 5.
2. The principle of Statistical Hough Transform
First rewriting the classical Hough transform equation:
(1)
The variables 、、、 are continuous random variables .Some of them may be available in different observation space. In particular, we define the following observation space:
1, .This is the observation space of variableswhich used in the classical Hough Transform.
2, .This is the observation space of. Indeed, when considering images, the gradient orientation can locally be computed and used as an observation.
3, .when knowing, the measurecan be computed using (1) and also used as an observation.
In addition to the observations, we attached a prior(,)to each observation。The statistical framework completely generalizes the classical Hough Transform and also takes advantage of the relation (1) between the random variables. This allows us to propose three different estimates offor each observation space (,and).
Let be the gray image of, its first order derivatives are, .The gradient magnitude and gradient orientation for each pixel at locationare getting from the following formula:
(2)
(3)
Variance of is defined as:
(4)
Where is the noise variance, generally defined as 1.
2.1. The Probability Density Function Under Different Observation Space
We propose three estimates of the probability density function for observation space ,, using kernel modeling.
First, kernel function model is used to give the probability density function in the observation space.
(5)
Where and are the variable bandwidths. Their estimations are explained in next section. The kernels andhave been chosen Gaussians so that (5) gives a continuous and smooth estimate of the density.
For the observation space, using the Bayes formula, we can write:
(6)
Under the observation space,the variable ,,are known, the variable is deterministic by formula (1). Therefore, we propose to model the conditional probability as follows:
(7)
Where is the Dirac distribution. As a consequence, onlyis to estimate using kernels with the observation space:
(8)
Note that we have assumed the variables ,,independent given their observation space.The estimate can be computed:
(9)
with:
In the observation spacewhich is the classical Hough transform observation space, the only available thing is the position. No prior information is available on the variable, therefore, its kernel can be replaced in (9) by the uniform distribution as:
Then, expression (9) becomes:
(10)
with,
(11)
And,
(12)
Equation (10) gives a kernel estimate for the classical Hough transform.
2.2. Kernels and Bandwidths
It is usually acknowledged that the choice of the kernelis very important, we have chosen the kernels andas Gaussian and now we discuss the choice of kernels and .Various kernels and can be used such as:
1. The Dirac kernels are defined as:
(13)
In this case, no bandwidths are needed. The corresponding kernel in the Hough space is then also a Dirac:
(14)
2. The Gaussian kernels are defined as:
(15)
The corresponding kernel in the Hough space is:
(16)
In this paper, we have chosen the kernels as Gaussian. The Dirac kernel is then just a special case of the Gaussian kernel when the bandwidth goes toward 0.
For the variables and , we naturally set the bandwidths , .The bandwidthsare estimated in a similar fashion as the variable bandwidth for. reflect the uncertainty attached to the observation space of the variables. Because of the digitalization process, the observation spaces of the variableshave a precision. Then, we set
(17)
3. Lane Detection Method of Statistical Hough Transform Based on Gradient Constraint
Based on the statistical Hough transform method described in the previous section, we implement a robust lane detection method based on gradient constraint. The proposed method starts from an inverse perspective mapping algorithm, then each pixel gradient magnitude and gradient orientation are calculated. The gradient constraint method is performed as a selection step, when the pixel gradient magnitude is greater than the threshold; this pixel is selected to model by Gaussian kernel function .Then build a 3D histogram based on the probability density function. The peaks in the histogram are the desired lane parameters. The flow chart of lane detection algorithm is shown in Fig.1.
3.1. IPM
Based on the flat ground hypothesis with known extrinsic and intrinsic parameters of the camera, IPM can remove the perspective effect. It remaps pixels from the original image to the other image that has a different coordinate system. This remapping procedure can be done by a fast lookup table with distortion compensation. As the resolution for near and further object is different in the original image, an interpolation process is needed in the IPM algorithm [3][4]. The resulting image is shown in Fig. 2.We can see from Fig 2 that IPM creates a somewhat cleaned up and less complex image where distracters (sky, objects, etc.,) are downplayed.
3.2. Gradient Constraint
The probability density function of lane parameters is estimated by multiple kernel density, and the uncertain variables are modeled by Gaussian kernels. Statistical Hough transform can directly work on the gray image and it is more robust than the classical Hough transform against noise. But computing the Statistical Hough Transform on an image is more computationally expensive than the classical Hough transform because all pixels of the image are used. The gradient constraint method used to decrease the number of the pixel, in addition, would not cause histogram sparse.
Here, we analysis gradient magnitude of the image and get the distribution figure of it, as shown in fig.3.We can get the minimum and maximum gradient magnitude is 0 and 126,respectively. Most of the pixels’ gradient magnitudes in the image are relatively small. The number of pixel with gradient magnitude varies from 0 to 20 is the most. These pixels not only increase the complexity of modeling, but also have little chance on the lane line. So, we take those pixels as the basis pixels and get rid of the pixel whose gradient magnitude is zero to calculate the gradient magnitude threshold. Pixels whose gradient magnitude is greater than the threshold is to participate in statistics Hough transform. The threshold is obtained as:
(18)
Where is the minimum gradient magnitude, is the maximum gradient magnitude. Here, we define, value can decide by the actual gradient magnitude range.
Introducing the gradient constraint method to statistical Hough transform on the one hand keeps the on lane line pixels modeled by Gaussian as far as possible, on the other hand reduces the amount of calculation of building histogram.
3.3. Build Histogram
This section we applied the kernels function to lane detection. Distribution of lane parameters is determined by the position of each pixel in the image given by and the orientation of the pixel, giving the observation space, the lane parameters probability density function can be represented as.It can be written according to Bayes rule [3]:
(19)
In (19), the first probability is determined by (1), and the second probability can be modeled by a Gaussian kernel function, thus (19) becomes:
(20)
Where is the Dirac function, ,, are Gaussian kernels. The distribution can be obtained by integrating (20) over (x, y):
(21)
Where
Let,, where ,And w and h are the width and height of the IPM image. Then compute the probability for selected pixels according to (21). The variance of , , are defined as,, 。Fig.4 shows the histogram of fig.2-c.
4. Results and Analyses
Test images on our experiments are captured using on-board system. To demonstrate the performance of the algorithm, we apply it on various situations on the highway under the environment of laboratory. This paper selected 3000 frames of images under various scenarios for testing, a total of 2780 frames correctly detect the lane line, and the correct detection probability is up to 92.7%.
Figure 5 contains two groups’ lane detection results, each group consists two parts, the upper part is the original image, and the lower part is the test results. Group (a) is the detection result of no obstacle in the vision field; Group (b) is the detection result of cars or other obstacles occlude in the lane. As can be seen from the test results, under different highway situations, the proposed method detects the lane location in the real range, in case of a small amount of vehicles or obstacle; the robust algorithm can still detect the lane line correctly.
Using the gradient constraint method limits the size of initial data set. Only keep large gradient magnitude pixels modeling by Gaussian kernel function to reducing the amount of calculation. Tab.1 shows the processing speed and the total number of pixels participates in the histogram before and after gradient constraint for Fig.2-c. Before gradient constraint, the processing speed is 1.1s per frame, after gradient constraint, the processing speed is 0.64s per frame. The detection results in Fig 5 reveal the gradient constraint method does not affect the validity of the results.
total number | processing speed | |
Before gradient constraint After gradient constraint | 127600 53208 | 1.10second/per frame 0.64 second/per frame |
5. Conclude
A lane detection method of Statistical Hough transform based on gradient constraint is proposed on analyzes the advantages and disadvantages of classical Hough transform. Statistical Hough transform uses the Gaussian kernel function to model each pixel in the image solving the problem of the classical Hough transform grid quantization accuracy. Using the method of gradient constraint limits the size of initial data set for reducing the amount of calculation and improving the follow-up detecting accuracy. Eventually lane parameters of continuous probability density function are given. The results of the experimentation show that under highway circumstance the provided method can rapidly and robustly detect the lane.
References