# A Lane Extraction Algorithm Based on Fuzzy Set

Authors: Yuxiu Bai; Huanhuan Zheng; Jian Zhou; Dongmei Zhou
Journal: Mathematical Problems in Engineering
 (2021)

---

## Abstract

Lanes are difficult to be extracted completely. A lane extraction algorithm is proposed according to vehicle driving rules. Vehicles are moving constantly, so the foreground area and background area cannot be defined effectively in the image. Therefore, based on the theory of fuzzy set, multidimensional degree is used to judge the membership degree of target and foreground in order to extract the moving area accurately. Then, the logistic regression model is established to determine the moving vehicles. Finally, based on the vehicle track, the lane extraction is realized by regional growth. The results show that the proposed algorithm can extract the road effectively.


---

## Body

## 1. Introduction

With the rapid development of video processing technology, it promotes the development of transportation towards the direction of intelligence and automation [1,2]. Among them, road extraction is an important research direction. Niu [3] analyzed the vehicle operation by marking the road. Pongpaipool et al. [4] studied road congestion. Grote et al. [5] established a model based on the prior knowledge of road and extracted the road area. Grote and Heipke [6] established a regional model to extract roads. Lin et al. [7] constructed a semiautomatic tracker to realize lane line extraction. Grote et al. [8] constructed a model based on connectivity to realize the continuity of road extraction. Senthilnath et al. [9] comprehensively considered the structural, spectral, and geometric characteristics of the highway to establish a model to realize road extraction. Guan et al. [10] improved the Hough model to extract road centerline and estimate road width. Zhao and Wang [11] implemented road extraction based on mathematical morphology and snake model. Rajeswari et al. [12] integrated level set, normalized cuts, and mean shift methods to extract the road. Kirthika and Mookambiga [13] constructed a neural network model to extract roads. Karaman et al. [14] established a model from the perspective of multispectral to realize road extraction. Grote et al. [15] identified road supporting facilities and extracted road information. Miao et al. [16] established a model according to the road shape to determine the road centerline. Wegner et al. [17] built a higher-order CRF model to solve the problem that it is difficult to extract complex roads. Shi et al. [18] considered the road extraction problem as a binary classification problem to distinguish the road and nonroad parts. Singh and Garg [19] extracted trees to reduce the impact of shadow on road extraction results. Maboudi and Amini [20] established a multiresolution model to extract roads. Saati et al. [21] obtained SAR images and extracted road information. Li et al. [22] established a hierarchical model to extract road regions step by step. Saba et al. [23] established a cost function to optimize the genetic algorithm to obtain the best segmentation parameters. Wei et al. [24] improved CNN to realize road extraction from aerial images. Zang et al. [22] built joint enhancing filtering to achieve road enhancement. Sameen and Pradhan [25] established a segmentation and classification model to realize road extraction. Xu et al. [26] analyzed the road composition and extracted the road from the perspective of deep learning. Gao et al. [27] established a multifeature pyramid model to extract suburban roads. Bastani et al. [28] established a model based on road connectivity to predict the road extension direction. Hong et al. [29] established a novel FMH model to extract urban roads. Li et al. [30] fused multiple features into CNN to segment roads accurately. Qiu and Li [31] proposed moving target extraction and background reconstruction algorithm.Generally, the main difficulties of road extraction are as follows: (1) it is difficult to establish a unified road segmentation model because of the limited features of the road in the image, and (2) due to the disorder of road extension, it is easy to be affected by shadow and other factors, which can result in incomplete segmentation. Therefore, we propose a complete road extraction process: (1) from the perspective of the image sequence, the driving direction of moving vehicles is analyzed to determine the road area indirectly, and (2) according to the trajectory of moving vehicles, the road is extracted completely.


## 2. Road Extraction Algorithm

According to the above analysis, the algorithm flowchart is established, as shown in Figure1, and the images are input sequentially. (1) A multidimensional moving object detection method based on a fuzzy set is proposed to realize the accurate extraction of moving objects. (2) The vehicle detection module is established to detect and track the vehicle. (3) According to the vehicle trajectory, road extraction is realized.Figure 1
Algorithm flowchart.


### 2.1. Multidimensional Degree Moving Object Detection Based on Fuzzy Set

In the complex background, it is difficult to distinguish the moving object from the background. For this reason, scholars put forward the theory of fuzzy set to study the data with ambiguous types. Firstly, we define the fuzzy subset asA, and μA (x) is called the membership of x to A. In moving object detection, every attribute is a fuzzy set, and the selection of its membership function is very important. According to the difference between the intraclass similarity and the interclass similarity, we design the membership function:(1)μx,a,b,c=0,x∈0,a,0.5−x−bc−a2,x∈a,b,0.5+x−bc−a2,x∈b,c,1,x∈c,+∞,where a < c, b = (a + c)/2. The slope of this function is small near the boundary of 0.5, but large far away from the boundary. Because of the fuzziness of the features, the middle part cannot judge the foreground and background clearly, so it needs to be determined by combining with other membership relations. Therefore, we carry out the research from the dimensions of color (C), time (T), and space (S). The process is as shown in Figure 2.Figure 2
Object detection flowchart.The pyramid model is constructed to solve the membership functions under different resolutions and form the fuzzy vector set cluster. The upsampling is used to generate the foreground membershipμc0, μc1, and μc2 (RGB three channels) of the same dimension as the original resolution. According to the membership principle of fuzzy vector set cluster, the membership degree of each point to the foreground is calculated from the color vector C, which is μc = (μc0 + μc1 + μc2)/3. Similarly, the membership of T and S is calculated.The object motion will not produce mutation because of the continuity of the video. If a certain point is foreground in the current frame, it is more likely to be foreground in the next frame, and its probability is recorded asPF. Similarly, if the current frame is background, the possibility of the next frame as the background is also greatly recorded as PB. The background and foreground will be switched because of the uncertainty of object motion. Given that the number of foreground pixels and background pixels in T−n frame is nFT−2 and nBT−2, when nFT−1=nFT−2>0 and nBT−1=nBT−2>0, then PF and PB can be represented by fuzzy set. For the point in frame T−1, the membership degree of the vector to foreground and background is μnFT−1/nFT−2;0,0.5,1 and 1−μnBT−1/nBT−2;0.5,0.75,1 within the time of T frames.Spatial feature refers to the concentration of points. In a small area, the attributes of points should be consistent. Most of the outliers are noise, which should be removed. Based on the preliminary results of color membership, the number of foreground pixels with membership greater than 0.5 in the 5 × 5 pixel area is counted which is expressed asn. The membership degree of the space vector of the point to the foreground can be expressed as μn/25;0,0.5,1.As the real moving object should have the following characteristics: the color difference between the object and the background point is large, the position of the object changes continuously, and the concentration is strong, then the final membership function is as follows:(2)μ=minμc,μT,μS.


### 2.2. Lane Extraction Algorithm Based on Vehicle Trajectory

According to the characteristics of vehicles only driving in the lane, we will extract vehicles from all moving objects and then indirectly determine the lane. LRM (logistic region model) [32] is a classical classification algorithm in statistics, whose process includes the following: the cost function is established, and then the optimal model parameters are obtained. Finally, the model effect is verified. The conditional probability distribution of the traditional binomial regression model is as follows:(3)PY=1|x=expω·x1+expω·xPY=0|x=11+expω·xx∈Rn,Y∈0,1,where ω is the parameter of the weight vector and · is the inner product. At this time,(4)logPY=1|x1−PY=1|x=ω·x.The maximum likelihood estimation method is used to estimate the parameters(5)Lω=∑i=1Nyiω·xi−log1+expω·xi.On the basis ofL (ω), in order to avoid overfitting, the cost function is defined as(6)Jω=−1nLω+λ∑j=1nωj2,where λ is the regularization coefficient. When J (ω) is minimum, the corresponding ω is the optimal parameter. The gradient descent method is used to get the minimum value of the cost function.(7)∂Jω∂ω=−1n∑i=1Nyi−expω·xi1+expω·xixi+λnωj.The update process is as follows:(8)ω¯j=ωj+αn∑i=1Nexpω·xi1+expω·xi−yixij−λnωj.According to the above algorithm, the vehicle area is extracted, and the vehicle trajectory set is determined by taking the vehicle gravity center as the center. Taking the trajectory set point as the seed point, the region growth method is used to realize the complete extraction of lanes.


## 2.1. Multidimensional Degree Moving Object Detection Based on Fuzzy Set

In the complex background, it is difficult to distinguish the moving object from the background. For this reason, scholars put forward the theory of fuzzy set to study the data with ambiguous types. Firstly, we define the fuzzy subset asA, and μA (x) is called the membership of x to A. In moving object detection, every attribute is a fuzzy set, and the selection of its membership function is very important. According to the difference between the intraclass similarity and the interclass similarity, we design the membership function:(1)μx,a,b,c=0,x∈0,a,0.5−x−bc−a2,x∈a,b,0.5+x−bc−a2,x∈b,c,1,x∈c,+∞,where a < c, b = (a + c)/2. The slope of this function is small near the boundary of 0.5, but large far away from the boundary. Because of the fuzziness of the features, the middle part cannot judge the foreground and background clearly, so it needs to be determined by combining with other membership relations. Therefore, we carry out the research from the dimensions of color (C), time (T), and space (S). The process is as shown in Figure 2.Figure 2
Object detection flowchart.The pyramid model is constructed to solve the membership functions under different resolutions and form the fuzzy vector set cluster. The upsampling is used to generate the foreground membershipμc0, μc1, and μc2 (RGB three channels) of the same dimension as the original resolution. According to the membership principle of fuzzy vector set cluster, the membership degree of each point to the foreground is calculated from the color vector C, which is μc = (μc0 + μc1 + μc2)/3. Similarly, the membership of T and S is calculated.The object motion will not produce mutation because of the continuity of the video. If a certain point is foreground in the current frame, it is more likely to be foreground in the next frame, and its probability is recorded asPF. Similarly, if the current frame is background, the possibility of the next frame as the background is also greatly recorded as PB. The background and foreground will be switched because of the uncertainty of object motion. Given that the number of foreground pixels and background pixels in T−n frame is nFT−2 and nBT−2, when nFT−1=nFT−2>0 and nBT−1=nBT−2>0, then PF and PB can be represented by fuzzy set. For the point in frame T−1, the membership degree of the vector to foreground and background is μnFT−1/nFT−2;0,0.5,1 and 1−μnBT−1/nBT−2;0.5,0.75,1 within the time of T frames.Spatial feature refers to the concentration of points. In a small area, the attributes of points should be consistent. Most of the outliers are noise, which should be removed. Based on the preliminary results of color membership, the number of foreground pixels with membership greater than 0.5 in the 5 × 5 pixel area is counted which is expressed asn. The membership degree of the space vector of the point to the foreground can be expressed as μn/25;0,0.5,1.As the real moving object should have the following characteristics: the color difference between the object and the background point is large, the position of the object changes continuously, and the concentration is strong, then the final membership function is as follows:(2)μ=minμc,μT,μS.


## 2.2. Lane Extraction Algorithm Based on Vehicle Trajectory

According to the characteristics of vehicles only driving in the lane, we will extract vehicles from all moving objects and then indirectly determine the lane. LRM (logistic region model) [32] is a classical classification algorithm in statistics, whose process includes the following: the cost function is established, and then the optimal model parameters are obtained. Finally, the model effect is verified. The conditional probability distribution of the traditional binomial regression model is as follows:(3)PY=1|x=expω·x1+expω·xPY=0|x=11+expω·xx∈Rn,Y∈0,1,where ω is the parameter of the weight vector and · is the inner product. At this time,(4)logPY=1|x1−PY=1|x=ω·x.The maximum likelihood estimation method is used to estimate the parameters(5)Lω=∑i=1Nyiω·xi−log1+expω·xi.On the basis ofL (ω), in order to avoid overfitting, the cost function is defined as(6)Jω=−1nLω+λ∑j=1nωj2,where λ is the regularization coefficient. When J (ω) is minimum, the corresponding ω is the optimal parameter. The gradient descent method is used to get the minimum value of the cost function.(7)∂Jω∂ω=−1n∑i=1Nyi−expω·xi1+expω·xixi+λnωj.The update process is as follows:(8)ω¯j=ωj+αn∑i=1Nexpω·xi1+expω·xi−yixij−λnωj.According to the above algorithm, the vehicle area is extracted, and the vehicle trajectory set is determined by taking the vehicle gravity center as the center. Taking the trajectory set point as the seed point, the region growth method is used to realize the complete extraction of lanes.


## 3. Experiment Result and Analysis

20 groups of aerial videos are used in the experiment to form a database. 8 groups of representative data (43109 frames) are selected from it to verify the effectiveness of the proposed algorithm as shown in Table1. The running environment of the program is Win 7. All images are calibrated at the pixel level by a dedicated professional person in the area where the lane is located. We use the trilinear difference to normalize the image resolution. And in this case, the frequency does not need to be normalized.Table 1
Introduction of database.
DataResolutionFrame no.Feature1352 × 2887500Constant moving2480 × 3605210Large size moving target3768 × 5765412The first frame contains the moving object4320 × 2401025Aerial top view5512 × 2887850Contains the shadow6448 × 3366245Aerial strabismus71480 × 13207852Gate of the community83840 × 21602015The crossroads


### 3.1. Comparison of Moving Object Extraction Algorithms

In order to verify the accuracy of moving object extraction, area overlap segmentation (AOM) and combination measure (CM) are introduced [33]:(9)AOM=Rs∩RgRs∪Rg,CM=13AOM+RsRg+RgRs,where Rg is the gold standard, Rs is the segmentation result, and AOM and CM are proportional to the segmentation result.Comparing the segmentation results of different algorithms, as shown in Table2, all algorithms show good performance for the data that the object has been moving. Because the dynamic learning factor of GMM [34] is fixed, the object extraction is incomplete. FD [35] algorithm fixes background frame, which can better extract large moving objects, but the quality of the background frame will directly affect the subsequent detection effect. EFD [36] reduces the influence of the background frame by fusing boundary information. DL [37] integrates prior knowledge, which can better restrain tailing. EGMM [38] simulates the light distribution to establish a model, which has a good inhibition effect on the shadow area. However, on the basis of the traditional GMM, our algorithm updates the learning factor dynamically and introduces the frame difference method to realize the complete extraction of the motion region. Although the effect is slightly lower than that of DL [37] and EGMM [38] when the first frame contains moving object and data with shadow, the proposed algorithm has high performance. Since the algorithm proposed in this paper is based on the area where the vehicle is traveling, when there is no vehicle passing through the shadow area, there will be a risk of missed detection. The follow-up research will continue to strengthen the study in this area.Table 2
Detection results of segmentation algorithms.
AlgorithmAOMData 1Data 2Data 3Data 4Data 5Data 6Data 7Data 8GMM0.830.760.780.800.750.860.790.76FD0.810.790.750.790.760.800.820.83EFD0.860.820.770.830.790.830.850.87DL0.920.890.910.920.870.810.900.89EGMM0.850.800.820.850.930.800.860.85Ours0.930.900.890.930.910.900.920.90CMGMM0.710.690.790.770.750.710.680.71FD0.760.730.810.810.780.730.740.70EFD0.790.750.850.840.810.760.780.76DL0.820.780.880.860.830.810.810.79EGMM0.860.820.870.880.870.850.840.83Ours0.890.860.850.900.860.870.860.85


### 3.2. Lane Extraction Result

A lane extraction algorithm is proposed in this paper. On the premise of moving vehicle detection, the vehicle trajectory graph is constructed to finally realize the lane extraction, as shown in Figure3. Our algorithm can effectively extract the lane and effectively distinguish the pedestrian road and vehicle road.Figure 3
Lane extraction result. (a) School, (b) garden, (c) ordinary community, (d) dense community, (e) one-way highway, (f) highway strabismus, (g) highway crossroads, and (h) highway looking down.
(a)(b)(c)(d)(e)(f)(g)(h)


## 3.1. Comparison of Moving Object Extraction Algorithms

In order to verify the accuracy of moving object extraction, area overlap segmentation (AOM) and combination measure (CM) are introduced [33]:(9)AOM=Rs∩RgRs∪Rg,CM=13AOM+RsRg+RgRs,where Rg is the gold standard, Rs is the segmentation result, and AOM and CM are proportional to the segmentation result.Comparing the segmentation results of different algorithms, as shown in Table2, all algorithms show good performance for the data that the object has been moving. Because the dynamic learning factor of GMM [34] is fixed, the object extraction is incomplete. FD [35] algorithm fixes background frame, which can better extract large moving objects, but the quality of the background frame will directly affect the subsequent detection effect. EFD [36] reduces the influence of the background frame by fusing boundary information. DL [37] integrates prior knowledge, which can better restrain tailing. EGMM [38] simulates the light distribution to establish a model, which has a good inhibition effect on the shadow area. However, on the basis of the traditional GMM, our algorithm updates the learning factor dynamically and introduces the frame difference method to realize the complete extraction of the motion region. Although the effect is slightly lower than that of DL [37] and EGMM [38] when the first frame contains moving object and data with shadow, the proposed algorithm has high performance. Since the algorithm proposed in this paper is based on the area where the vehicle is traveling, when there is no vehicle passing through the shadow area, there will be a risk of missed detection. The follow-up research will continue to strengthen the study in this area.Table 2
Detection results of segmentation algorithms.
AlgorithmAOMData 1Data 2Data 3Data 4Data 5Data 6Data 7Data 8GMM0.830.760.780.800.750.860.790.76FD0.810.790.750.790.760.800.820.83EFD0.860.820.770.830.790.830.850.87DL0.920.890.910.920.870.810.900.89EGMM0.850.800.820.850.930.800.860.85Ours0.930.900.890.930.910.900.920.90CMGMM0.710.690.790.770.750.710.680.71FD0.760.730.810.810.780.730.740.70EFD0.790.750.850.840.810.760.780.76DL0.820.780.880.860.830.810.810.79EGMM0.860.820.870.880.870.850.840.83Ours0.890.860.850.900.860.870.860.85


## 3.2. Lane Extraction Result

A lane extraction algorithm is proposed in this paper. On the premise of moving vehicle detection, the vehicle trajectory graph is constructed to finally realize the lane extraction, as shown in Figure3. Our algorithm can effectively extract the lane and effectively distinguish the pedestrian road and vehicle road.Figure 3
Lane extraction result. (a) School, (b) garden, (c) ordinary community, (d) dense community, (e) one-way highway, (f) highway strabismus, (g) highway crossroads, and (h) highway looking down.
(a)(b)(c)(d)(e)(f)(g)(h)


## 4. Conclusion

As it is difficult to extract the lane completely, a lane extraction model is established based on moving vehicles. Based on the fuzzy set theory, the algorithm is proposed from the color, time, and space dimensions and takes the vehicle route as the benchmark to achieve accurate road extraction. On this basis, road condition analysis and road construction research can be carried out in the future.



---

*Source: 9390778-2021-06-02.xml*