Lane line recognition based on improved 2D-gamma function and variable threshold Canny algorithm under complex environment

Fast guided filtering

Guided filter is a kind of adaptive weight filter, which can smooth the image and keep the boundary at the same time. Due to its fine visual quality, fast speed and easy implementation, pilot filter has been widely used in practical products. ²³ Although it is popular and has a variety of third-party applications, scholars such as He note that a simple but significant acceleration has not been utilized. ²⁴ In this method, the filtering input image and the guidance image are sub sampled to calculate the local linear coefficients, and the up sampling of these coefficients is carried out. The upper sampling coefficient is used to generate the output on the original guidance image. This method reduces the time complexity of subsampling ratio s from O(n) to O(n²), and the actual acceleration is *10. Compared with other filtering methods, FGF can retain the edge details and local features better, and also has a very high speed of operation, so this paper uses FGF instead of Gaussian Filtering or Bilateral Filtering to extract the illumination components of the image.

As a linear filter, guided filter can be simply defined as follows:

q i = a k I i + b k ∀ i ∈ ω k

(1)

where I is the guided image, q is the input image to be filtered, q is the filtered output image, and i is the index of the pixel, ω_k refers to a filtering window in which the output image q is the linear transformation from the guiding image I, which is determined by a_k and b_k. K is the index of the local square window ω, and the radius is r. In order to filter the original image, on the basis of satisfying the above local linearity, it is necessary to make the output image approach the original image as much as possible, and adopt the least square method to minimize the reconstruction error between the output image and the original image:

E ( a k , b k ) = ∑ i ∈ ω k ( ( a k I i + b k − p i ) 2 + ε a k 2 )

(2)

The penalty value ε is the regularization parameter introduced to prevent a_k from excessive. The solution of equation (2) can be given by linear regression:

{ a k = 1 | ω | ∑ i ∈ ω k I i p i − μ k p ¯ k σ k 2 + ε b k = p ¯ k − a k μ k

(3)

where |ω| is the number of pixels in the window, μ, p ¯ k are the mean value of the guide image and the original image in the window respectively, and σ k 2 is the variance of the guide image in the window.

After finding a_k and b_k, the output image can be obtained according to the previous local linear model. However, since the same pixel will be included in many different filtering windows, a_k and b_k in each window are different, so it is necessary to take the average value of a_k and b_k for recalculation.

According to formula 3, it can be seen that the molecule of a_k is actually the covariance of I and P. If the original image is used as a guide image, the molecule becomes 1 | ω | ∑ i ∈ ω k p i 2 − p k 2 , which is the variance, and a_k becomes the following form:

a k = σ k 2 σ k 2 + ε

(4)

when the original image is rich in information (including edges), the variance will be correspondingly large. According to the above formula, a_k will naturally be large, and the gradient information of the original image will be retained. In the flat area of the original image, a_k will be smaller and b_k will be larger. When a_k is reduced to 0, b_k will be u_k, which is equivalent to mean filtering, with the strongest smoothing effect. On this basis, we use image pyramid to accelerate the calculation. First, the sub sampling is used for output, and then the upper sampling is used to output the final image. The main steps are as follows:

Conduct 1/s sub-sampling of the guide image I and the input image P to obtain I' and P' :

I ′ = f subsample ( I , s ) p ′ = f subsample ( p , s ) r ′ = r / s

(5)

Preliminary calculation of coefficients a and b using I′ and P':

I mean = f mean ( I ′ , r ′ ) p mean = f mean ( p ′ , r ′ ) cor r I = f mean ( I ′ . * I ′ , r ′ ) cor r Ip = f mean ( I ′ . * p ′ , r ′ ) var I = cor r I − I mean . * I mean cov Ip = cor r Ip − I mean . * p mean } → { a = cov Ip . / ( var I + ε ) b = p mean − a . * I mean

(6)

Among them, corr stands for correlation coefficient, var stands for variance, and cov stands for covariance.

a mean = f mean ( a , r ′ ) b mean = f mean ( b , r ′ ) } → { a ′ mean = f upsample ( a mean , s ) b ′ mean = f upsample ( b mean , s ) } q = a ′ mean . * I + b ′ mean

(7)

Due to the calculation part is the image of downsampling, the amount of calculation will be greatly reduced without introducing obvious distortion, so it becomes a fast guide image filter.

Improved two-dimensional gamma function

There are many scholars using 2-D gamma function to carry out adaptive image correction at present, while this paper has made some improvements and extensions to improve the adaptability and rationality of the algorithm. In general, gamma correction has the following standard forms:

O ( i , j ) = 255 [ I ( i , j ) 255 ] γ

(8)

Among them, I(i, j) is the input image (original image), O(i, j) is the output image, and γ is the control parameter. When γ is greater than 1, the image becomes dark as a whole, when γ is less than 1 and greater than 0, the image becomes bright as a whole, and when γ is less than 0, the algorithm has no meaning. At present, 2 ( F ( i , j ) - 128 ) / 128 is often used to calculate the value of γ in this paper, the idea of this approach is as Figure 2: due to the gray value of white is 255 and the gray value of black is 0, the average value of 128 is taken as the mean value of the light component, and the reason why the base number is 2 is not clearly explained, which is often determined by experience.

In this paper, some adjustments have been made to the traditional 2-D gamma function in order to establish a relationship with the gray value distribution characteristics of the image to be processed, as shown in the following formula:

γ ′ = α [ ( F ( i , j ) - m ) / m ]

(9)

where m is the mean value of brightness in the light component F(i, j), using m instead of the fixed value 128 can more reasonably represent the mean value of the current light component rather than the absolute mean value in the theoretical sense; Another change is to use variable scale α instead of fixed base number 2. The calculation of α is derived from the following.

Take the expected value of the improved gamma function formula, which should be equal to 128 in theory, and the formula after derivation is as follows:

ln 0 . 5 ln ( I ¯ 255 ) = α [ ( F ( i , j ) - 128 ) / 128 ]

(10)

At this time, there are two extreme cases, the light component F(i, j) is all black or all white, so two values of α can be obtained:

{ α white ≅ ln ( I ¯ 255 ) ln 0 . 5 , when F ( i , j ) = 255 α black ≅ ln ( 0 . 5 ) ln ( I ¯ 255 ) , when F ( i , j ) = 0

(11)

The two equations are represented by curves as shown in the Figure 2. Considering that the actual collected image will not have gray value greater than 220 or less than 30, 25–225 is selected as the interval of independent variable I ¯ . When the average gray value of the original image I is 128, the two curves coincide. In this paper, the curve above the dotted line is taken as the value of α. When the average light value is less than 128, the α_white curve is used for calculation, otherwise the α_black curve is used for calculation. The advantage of this method is that it can establish a relationship with the average gray value of the original image, so that the intensity of image correction changes follow with the content of the original image, the over bright or over dark image will be greatly adjusted, while the more balanced image will almost remain the same.

OPEN IN VIEWER

Figure 2.

α value curve.

In this paper, the image correction algorithm flow for uneven illumination image is shown as Figure 3:

OPEN IN VIEWER

Figure 3.

Flow chart of image correction processing.

Because brightness V in HSV model is still related to color, and Y in YCbCr space is completely independent of color, brightness Y in YCbCr space is selected for adjustment. The comparison between the image processed by the algorithm designed in this paper and the traditional 2-D gamma algorithm using FGF is shown in the following Figure, and the processing time pairs with Gaussian Filtering, Guided Filtering and Bilateral Filtering ²⁵ are shown in Table 1.

OPEN IN VIEWER

Table 1.

Processing time comparison of different filtering methods.

Test group	Gauss filter/ms	Bilateral filtering/ms	Guided filtering/ms	FGF/ms
1	58.31	2879	36.54	18.95
2	60.64	2849	32.88	14.14
3	61.26	2931	33.16	15.21
Average	60.07	2886.3	34.19	16.10

In the Figure 4, the α value calculated by the design method in this paper is 2.41, and the α value calculated by the design method in this paper in the following figure is 4.34. As a contrast, three α values are manually used to represent the processing results of the traditional two-dimensional gamma function (3, 2 and 1.67, respectively). Using traditional gamma function for image enhancement and correction requires manual setting of α value, which is quite different for different images. It is difficult to use the same set of α values to make the image get the best processing and make the lane line more obvious. It should be noted that although the use of this algorithm in the following figure causes a large distortion to the color of the shadow part, considering that the purpose is to better extract the lane line rather than image restoration, so as long as the lane line is clear and obvious under all kinds of uneven light conditions, and has a high degree of discrimination, it can be regarded as achieving the purpose.

OPEN IN VIEWER

Figure 4.

Image correction processing effect comparison.

The Gauss Filter, Bilateral Filter, Guide Filter and Fast Guide Filter are tested three times in total. The average value of each test is recorded and the final average value is taken. It can be seen that FGF always keeps the fastest operation speed, which is useful for engineering applications.

Traditional Canny algorithm

Canny algorithm has three strict edge detection criteria: Signal to Noise Ratio (SNR), location accuracy and single edge response. On the basis of the above indexes and criteria, the canny edge detector is the best approximation operator of the product of SNR and location, and the expression is approximate to the first derivative of Gaussian function. By combining the three criteria of Canny edge detection, the optimal detection operator can be obtained. Canny edge detection algorithm mainly includes the following four steps:

Using Gaussian filter to smooth image:

H ( i , j ) = 1 2 π σ exp ( − i 2 + j 2 2 σ 2 )

(12)

G ( i , j ) = f ( i , j ) * H ( i , j )

(13)

i and j represents the coordinates of the pixel point, and f(i, j) represents the value of the point in the original image.

The gradient amplitude and direction of each point in the smoothed image are calculated by the first-order partial derivative finite difference method and recorded in the gradient amplitude map and gradient direction map. The first-order partial derivative of 2*2 neighborhood is used to calculate the i, j direction partial derivative of the smoothed image G(i, j) according to the following formula.

{ P x [ i , j ] = G ( x , y ) | - 1 - 1 1 1 | = ( G [ i + 1 , j ] − G [ i , j ] + G [ i + 1 , j + 1 ] − G [ i , j + 1 ] ) / 2 P y [ i , j ] = G ( x , y ) | 1 - 1 1 - 1 | = ( G [ i , j + 1 ] − G [ i , j ] + G [ i + 1 , j + 1 ] − G [ i + 1 , j ] ) / 2

(14)

Calculate the amplitude and direction according to the following formula after finding out the deviation of x and y directions:

{ φ ( i , j ) = P x [ i , j ] 2 + P y [ i , j ] 2 θ φ [ i , j ] = arctan ( P y [ i , j ] / P x [ i , j ] )

(15)

The gradient amplitude is suppressed by non maximum value. Only getting global gradient is not enough to determine the edge. In order to determine the edge, the point with the largest local gradient must be kept, while suppressing non maximum value is to set the non local maximum value point to zero to get the refined edge, and finally a series of candidate edge points are obtained.

Double threshold algorithm is used to detect and connect edges. Two thresholds T_L and T_H (T_L < T_H) are used to further process a series of candidate edge points obtained in the previous step. The points whose gradient value is greater than the T_H are retained as edge points, the points whose gradient value is lower than the T_L are eliminated, and the points whose gradient value is between the two thresholds and adjacent to edge points are retained. Finally, it is determined whether there are edge pixels larger than the high threshold in the eight directions of the reserved points, and the qualified pixels will be reserved. In short, the high threshold is used to find the edge scatter points on each line segment, while the low threshold is extended in two directions of these lines to find the edge fracture and connect these edges.

Adaptive threshold calculation based on Otsu

According to the above Canny algorithm, it can be clear that the selection of high and low thresholds is very important for the final lane edge extraction. At present, Otsu algorithm is widely used to determine the threshold automatically. ¹⁸ The basic idea is to divide image pixels into background and target, and get the optimal threshold by searching and calculating the maximum variance between classes.^23,24,26 The best threshold should be the best separation between the two classes, and the best judgment of the separation between classes is based on the maximum of the variance between classes or the minimum of the variance within classes in the sense of mathematical statistics. ²⁶ Therefore, in the selection of threshold value of traditional Canny algorithm, Otsu algorithm can be combined with gradient amplitude to get the high and low thresholds in Canny algorithm.^27,28

If the total number of pixels in the image with gray level i is n_i and the range of gray level is [0, L-1], then the total number of pixels is:

N = ∑ i = 0 L − 1 n i

(16)

The size of L depends on the actual gray value range of the image.

The probability of each gray value is:

P i = n i N

(17)

and P_i satisfies the following characteristics:

∑ i = 0 L − 1 P i = 1

(18)

The pixels in the image are divided into two categories C₀ and C₁ by threshold. The background category C₀ is composed of pixels with gray value [0, T-1], and the target category C₁ is composed of pixels with gray value [T, L-1]. Then the probability of areas C₀ and C₁ are:

{ P 0 = ∑ i = 0 T − 1 p i P 1 = ∑ i = T L − 1 p i = 1 − p 0

(19)

The average gray levels of background class C₀ and target Class C₁ are respectively:

{ μ 0 = 1 p 0 ∑ i = 0 T − 1 i p i = μ ( T ) p 0 μ 1 = 1 p 1 ∑ i = T L − 1 i p i = μ − μ ( T ) 1 − p 0

(20)

where μ is the average gray level of the whole image:

μ = ∑ i = 0 L − 1 i p i = ∑ i = 0 T − 1 i p i + ∑ i = T L − 1 i p i = P 0 μ 0 + P 1 μ 1

(21)

The total variance of background area and target area is:

σ B 2 = P 0 μ 0 - μ 2 + P 1 μ 1 - μ 2 = P 0 P 1 μ 0 - μ 1 2

(22)

Adaptive threshold method considering luminance

Although the above algorithm has been widely used, there are two main disadvantages when it is directly applied to the lane recognition of AGV, one is that this method can not deal with the complex environment such as uneven light; the other is that the traditional Otsu method to determine canny high and low threshold takes a long time, which is difficult to meet the real-time requirements of vehicles. To solve this problem, a Fuzzy-Canny algorithm considering luminance is adopted to adjust the threshold.

The luminance component Y can not only represent the luminance difference between two regions in the same image, but also maximize the luminance difference between different images compared with the chrominance component. Moreover, since the illumination inequality (such as the shade of trees, highlights, etc.) in ROI region has been greatly improved after image correction, Y has little change in the same image, so the average brightness value Y is used as the differentiation index of different images. At the same time, considering that the high threshold T_H can distinguish the contour object from the background, this paper uses fuzzy logic algorithm to adaptively adjust the high threshold T_H with the luminance Y of ROI area as the input, so that the high threshold is more suitable for lane line detection and more useful information can be extracted. The basic value of T_H is determined by Otsu method described in Section 2.2 when the image Y value is 128, while the value of low threshold T_L is determined by 0.4*T_H.

After local image processing, the average value of Y in ROI area is taken as fuzzy input and Δ T_H is taken as output. In this paper, when designing membership function of fuzzy control, Y is reduced by 51 times, which is mapped to the range of 0–5. After repeated experiments, it is determined that the change value of ΔT_H is within |0.02| advisable, the parameters Y and ΔT_H are transformed into the fuzzy sets of [0,5] and [−0.02,0.02] respectively. The fuzzy language variables corresponding to Y and ΔT_H are shown in Figure 5: Y = {DB DM DS ZO LS LM LB}, ΔT_H = {DB DM DS ZO LS LM LB}. Among them, DB, DM, DS, ZO, LS, LM and LB represent rather dark, dark, slightly dark, normal, slightly bright, bright and rather bright respectively. If the value of Y is close to 255, it means that the illumination in ROI area is strong. At this time, the high threshold T_H should be increased to reduce the possibility of small particles being misjudged as edge points; If the value of Y is close to 0, it means that the illumination in ROI area is weak. In order to detect the edge of lane line, the high threshold T_H should be reduced. The size of Y also needs to be considered to prevent excessive changes in high thresholds from counterproductive. After repeated experiments, it is appropriate to determine the change amount ΔT_H within ±0.02. From the above analysis, the fuzzy rules and membership function of fuzzy system can be obtained:

OPEN IN VIEWER

Figure 5.

(a) Membership function of Y (b) Membership function of high threshold variation ΔT_H.

In the design of fuzzy controller, the design of fuzzy rules determines the important part of its performance. In this paper, seven fuzzy rules are given for ΔT_H, as follows:

R1: IF Y is PB THEN ΔT_H is DB;

R2: IF Y is PM THEN ΔT_H is DM;

R3: IF Y is PS THEN ΔT_H is DS;

R4: IF Y is ZO THEN ΔT_H is ZO;

R5: IF Y is NS THEN ΔT_H is LS;

R6: IF Y is NM THEN ΔT_H is LM;

R7: IF Y is NB THEN ΔT_H is LB.

Analysis and verification of algorithm detection effect

Considering the high real-time requirement of vehicles, in order to improve the processing efficiency, this paper only deals with the ROI region of the image in the experiment. For this camera, the original image pixel is 720 * 1280, while only the lower part of the image is selected as ROI area to be processed by this algorithm, which can be obtained from the geometric relationship of projection:^28,29

d = h tan ( θ + α )

(23)

( y i − y c ) * d x = f * tan α

(24)

where h is the installation height of the camera, θ is the inclination angle of the camera, α is the angle between the camera scanning point and its optical axis, d is the transverse distance from the farthest scanning point to the camera, (x_c, y_c) is the projection point of the optical center of the camera on the imaging plane, f is the focal length of the camera, y_i is the ordinate of the projection point of the camera scanning point on the imaging plane, d_x is the size of one pixel in the image pixel coordinate system in the image physical coordinate system.

Assuming that the longitudinal target distance of lane line detection is D, according to formula (23) and formula (24), the vertical coordinates of the upper boundary y_up and the lower boundary y_down of ROI in the image are respectively:

{ y up = f * tan ( arctan ( h / D − θ ) ) d x + y c y down = y veh

(25)

In the formula, y_veh is the vertical coordinate of the vehicle hood in the image, which is the fixed value after the camera is installed, and can be adjusted according to the actual situation.

Considering the motion speed of the AGV, the region in the lower half of the image (the ordinate pixel is 450-710) is selected as the ROI region to be processed with this algorithm after calculation. The edge detection effect comparison between the shadow region and the highlight region is shown in Figure 6.

OPEN IN VIEWER

Figure 6.

(a) Comparison of edge detection algorithms in shadow region; (b) Comparison of edge detection algorithms in highlighted regions.

It can be seen that although the Fuzzy-Canny method extracts more disordered edges when the ROI area is darker, the edge extraction of lane line is more complete, and the subsequent only need to filter out the lane line edge. The Fuzzy-Canny method reduces a considerable part of the disordered lines when the ROI area is bright, while the lane line is only slightly damaged, and then only needs curve fitting to solve the problem of partial missing.

Furthermore, we use Otsu-Canny algorithm and Sobel algorithm to compare with the Fuzzy-Canny algorithm designed in this paper. In order to make the contrast more meaningful, two kinds of test environment are set up: one is normal illumination condition; the other is the illumination uneven condition after image preprocessing designed in this paper. At the same time, the extraction method in reference ³⁰ are introduced to compare the effect under complex illumination environment. The image preprocessing method in reference ³⁰ is completely used in the illumination uneven test environment. In the above two environments, different edge extraction methods are used for experiments, and θ_line (extracted lane line pixel/lane line pixel) is used as the quantitative index, as shown in Table 2:

OPEN IN VIEWER

Table 2.

Comparison of effective edge extraction rate algorithms.

Characteristics	Number	Otsu-Canny	Sobel	Fuzzy-Canny	References 30
Normal illumination	100	0.973	0.377	0.969	0.971
Uneven illumination	100	0.976	0.328	0.965	0.716

First of all, by comparing the edge algorithm, it can be seen that the Fuzzy-Canny designed in this paper can basically maintain the advantages of Otsu-Canny algorithm, and can extract more lane line pixels than Sobel operator; Secondly, through the comprehensive comparison of the overall algorithm, it can be seen that the combination of the preprocessing algorithm and the edge extraction algorithm in this paper can better deal with the complex changes of light and extract more lane line pixels than the method in literature 35.

Inverse perspective transformation

Sheng scans the image line by line directly, and determines which scatter points belong to lane line by width matching. ³¹ This method does not consider that lane line in the image obtained by camera is not vertical, there is a certain angle in the image, so it needs reverse perspective transformation or distance conversion. Therefore, firstly, the image is transformed by inverse perspective in this paper, which makes preparation for the subsequent selection and extraction of lane line feature points.

The plane image with geometric deformation can be transformed into an undistorted top view by using the inverse perspective transformation algorithm. At present, there are two main methods to realize the inverse perspective transformation: the first one is to obtain the camera’s internal and external parameters by camera calibration method, the transformation formula is obtained by the multiplication of the internal and external parameter matrix according to the camera’s imaging model, and finally the top view after inverse perspective transformation is obtained by calculation.^32,33 Although this method can correct the distortion of the camera, it involves many parameters and variables, the algorithm is complex and the operation require long time. The second method is to deduce the geometric relationship of perspective principle, and use the simplified inverse perspective transformation formula to calculate so as to obtain the top view of the image.^29,34 This method is suitable for small angle camera with small distortion. Considering the characteristics and real-time of the camera used in this study, from the point of view of simplifying algorithm and realizing function, this paper makes some simplification to the first inverse perspective transformation method.

As the existing inverse perspective technology is relatively mature, this paper will not discuss its derivation process, and the overall transformation is as follows:

Z c [ u v 1 ] = [ 1 dx 0 u 0 0 1 dx v 0 0 0 1 ] [ f 0 0 0 f 0 0 0 1 ] [ R t 0 T 1 ] [ X Y Z 1 ] w

(26)

where the rotation matrix R is the matrix of 3*3, and t is the offset. From the back to the front, the middle three matrices are camera and world coordinate transformation matrix, projection relation matrix and pixel phase plane relation matrix.

Since the camera is installed inside the vehicle and has no roll angle, it can be simplified for the above type. If the camera is carefully installed and does not rotate relative to the Z axis, and considering that the horizon is actually horizontal, the plane where the road is located is taken as Z_W = 0, then equation (26) can be simplified as equation (27).

Z c [ u v 1 ] = M 1 M 2 [ X Y 0 1 ] w

(27)

Among them, Z_C is the perspective projection coefficient, M₁ is the camera’s internal parameter matrix, which is determined by the camera’s internal parameters fx, fy, u0, v0; M₂ is the external parameter matrix of the camera, where R and T are the coordinate transformation matrix determined by the location of the camera.

According to the above principle, the one-to-one correspondence between the points in the image plane and the points in the world coordinate system can be found, and then it can be transformed into an aerial view. It should be noted that, due to the small number of pixels in the distance, a large number of interpolation and fitting calculations are required when converting to the aerial view. Therefore, the transformation of the aerial view in the area far away from the sensor not only consumes computing power, but also cannot provide a clear lane line. Considering that the research object of this paper is low-speed driverless vehicle, so only the ROI area is transformed (for the same camera, the pixel coordinates of ROI area are fixed), finally make the two edges of lane line parallel, so that further analysis becomes easier.

Selection and extraction of feature points of lane line

After the image collected by the camera is transformed into the aerial view, the Fuzzy-Canny algorithm designed in the second chapter is used to process, and the binary image including the edge points and noise points is preliminarily obtained. Then, the binary image is filtered by progressive scanning method, and the edge points belonging to the lane line are extracted and the rest points are discarded, so as to reduce the impact of interference noise points on curve fitting. ³⁵

This method makes use of the feature that the lane width is basically the same, the lane line with a width of 0.25 m is 4–5 pixels wide in the aerial view image in this paper, and the interior of the lane line is a connected area. The extraction method used in this paper is as follows:

The above process is shown in Figure 7:

OPEN IN VIEWER

Figure 7.

Flow chart of progressive scanning.

The results processed by the Fuzzy-Canny algorithm and the lane line extraction results after progressive scanning are shown in Figure 8. The Fuzzy-Canny algorithm extracts enough lane line edge points under the condition of reducing the number of interference points as much as possible, the progressive scanning method basically extracts the edge points belonging to the lane line from all pixel points successfully. In addition, it can be seen that the dotted lane line is still extracted because it conforms to the extraction rules designed in this paper, while due to AGV follows the solid line, the dotted lane line will be removed in the subsequent processing in this paper.

OPEN IN VIEWER

Figure 8.

Binary graph and lane line filtering results in multi scene.

Curve fitting of feature points based on RANSAC

After preprocessing the image, there are scattered points on multiple lane lines. It is necessary to fit these scattered points to find a curve that can contain enough scattered points, that is, a curve that can contain enough scattered points. In this paper, RANSAC is used to fit the feature points to form the curve that best fits the lane line. Scholar Cao used canny method as the comparison object in his research and got poor lane line detection results. In addition to its lack of improvement on Canny algorithm, another important reason is that it used the least square method instead of RANSAC. The least square method is to find the most suitable curve from all the points. This method without abandoning leads to all the noise points being taken into account, so it is not suitable to use with Canny algorithm. RANSAC is a kind of non deterministic algorithm, it will produce a reasonable result under a certain probability, which allows more iterations to increase its probability. The operation process is as follows:

Step one: Suppose the model is a three degree curve equation, and randomly select 3 sample points to fit the model:

Y = C 1 + C 2 x + C 3 x 2 + C 4 x 3

(28)

Step two: Assuming that the tolerance range is ζ, find out the points within the tolerance range of the distance fitting curve, and count the number of points.

Step three: Select 3 points randomly again, and repeat the operation from the first step to the second step until the end of the iteration.

In short, after each fitting, there are corresponding data points within the tolerance range. Finding out that the number of data points meets the set confidence is the final fitting result. In this paper, the maximum number of iterations is determined by setting the confidence conditions. The number of iterations of steps 1–3 is related to the outliers proportion of the model and how high the confidence we need. It can be expressed by the following formula:

S = log ( 1 − P ) log ( 1 − p k )

(29)

where S is the minimum number of tests required, P is the confidence level, p is the percentage of inliers and k is the number of random samples. The specific confidence level needs to be determined by repeated tests and comprehensive consideration of accuracy and real-time.