# Traffic Flow Detection at Road Intersections Based onK-Means and NURBS Trajectory Clustering

Authors: Jun-fang Song; Shu-yu Wang; Hai-li Zhao
Journal: Mathematical Problems in Engineering
 (2020)

---

## Abstract

In view of the variety and occlusion of vehicle target motion on the urban intersection, it is difficult to accurately detect the traffic flow parameters in all directions and categories of the intersection, so an improvedk-means trajectory clustering method based on NURBS curve fitting is designed to obtain the traffic flow parameters. Firstly, the B-spline quadratic interpolation function is used to fit the smooth NURBS curve of vehicle trajectory; secondly, K-means clustering is used to measure the minimum distance, and the location of the first and last end points of the vehicle trajectory is used to realize the automatic division of the intersection area; finally, according to the intersection area where the start and end points of vehicle trajectory belong, respectively, the moving mode of a vehicle is determined, and the traffic flow parameters are classified and counted. Experiments show that the method has high accuracy and simple algorithm, which can meet the application requirements of intelligent transportation. It can provide effective data for traffic congestion analysis and lane occupancy estimation, and it is an important parameter for dynamic time setting of intersection information lights.


---

## Body

## 1. Introduction

The perception and prediction of traffic scene mainly includes the acquisition of vehicle flow parameters, the identification of traffic abnormal behavior, and the prediction of traffic congestion status, which is one of the hot areas of traffic scholars in various countries. It is an important task in the traffic scene perception system to obtain the traffic flow parameters in the video sequence. Real-time and accurate vehicle flow parameters can provide important data support for urban traffic control and management organizations. In addition, vehicle flow parameters on urban roads also reflect the current traffic conditions to a certain extent, for example, road traffic congestion status, lane occupancy rate, and road status; these information are conducive to traffic accident early warning, road congestion prediction and automatic planning of travel path [1]. Statistics of the traffic flow information of urban road intersections in different periods and in all directions can also be used as an important basis for the setting of dynamic timing parameters of intersection signal lights. It can effectively improve the traffic efficiency of the road, improve the traffic condition of the urban road network, and bring significant economic benefits to the society [2]. The traffic scene of urban intersection is complex, the vehicle motion mode is changeable, and the occlusion is serious, which make it difficult to detect and track the moving target accurately and continuously. In order to obtain the traffic flow parameters of urban intersections, it is very important to accurately identify the vehicle target and determine its moving direction.According to the different calculation methods and principles, there are currently four categories of traffic flow statistics: the target detection method [3–6], feature point motion trajectory clustering method [7–9], regional regression method [10, 11] and density estimation method [12–14]. Seenouvong et al. [3] completed the vehicle count in the set area by combining background subtraction with morphological filtering, with an accuracy of 96%; Memon et al. [4] introduced the Gaussian mixture model (GMM) to quickly detect and count vehicles in the field of view and realized the self-classification of moving targets by contour comparison; Chen [5] proposed to use the B-spline curve method to obtain the vehicle area, so as to realize the vehicle count; Leonel et al. [6] proposed a video sequence vehicle counting method based on augmented quantum space learning. The accuracy rate of counting vehicles at an average speed of 26 frames per second is 96.6%, and it can well deal with camera shake and sudden illumination changes caused by the environment and automatic camera exposure. Rabbouch et al. [7] designed a pattern recognition system based on unsupervised clustering of tracks, which realized intelligent detection, counting, and recognition of traffic targets; Mehboob et al. [8] built a real-time system through analyzing the temporal and spatial characteristics of vehicle trajectory, which it can deduce and track the target behavior online, and joint Hungarian tracking algorithm to count the number of vehicles; in terms of vehicle flow statistics by different types, Rauf et al. [9] proposed a method based on target tracking and convolutional neural network transfer learning; the regional regression method is well reflected in the literature [10, 11]. Liang et al. [10] constructed a regression model by extracting the edge features and gradient features of vehicles on the highway to obtain the vehicle flow parameters; Chen [11] suggested a hierarchical classification-based regression model for accurate vehicle counting in view of the complex and changeable characteristics of the actual traffic scene; Lempitsky and Zisserman [12] proposed the target counting algorithm framework based on density estimation in 2010, which is the most common and concerned counting framework at present. The method first generates the truth value image set of the target density distribution by using the target center graph manually annotated. Zhang et al. [13] introduced a vehicle density estimation method based on rank constraint regression and Fully Convolutional Networks (FCN), so as to realize accurate statistics of the number of vehicles. Based on the convolutional neural network (CNN), Sindagi and Patel [14] used deep learning to estimate vehicle density in crowded situations.In a word, in order to obtain accurate traffic flow parameters, in addition to establishing a reasonable mathematical model, it is particularly important to generate features that can truly reflect the running status of vehicle targets. However, the scene of urban intersection is complex, the moving state of the target is changeable, there are many occlusions, and rich target feature information is needed. The target trajectory can provide a wealth of spatiotemporal data such as direction and speed, and it has good stability in all-weather operation. This manuscript takes the trajectory of vehicle as an important feature, firstly, NURBS is used to fit the trajectory curve; then,k-means algorithm is used to complete the clustering of the trajectory curve; finally, based on the clustering results, the short-term traffic flow in each region and direction of the intersection is predicted.


## 2.K-Means Trajectory Clustering Based on NURBS Curve Fitting

Trajectory clustering is to use the appropriate similarity measurement method to complete the best classification of the obtained trajectory features. To explore suitable similarity measurement criteria to ensure the best clustering results, we chooseK-means clustering algorithm, which has fast calculation speed and high efficiency and is suitable for finding convex shape clusters. Aiming at the defects of the randomness of initial mean and the sensitivity of noise outliers, this manuscript introduces NURBS curve fitting to solve the problem of noise points when the target pairs to form a trajectory. The NURBS curve can be regarded as the sum of the product of a series of control points Vii=0,1,2,…,n and the base function Ni,ku determined by the known node sequence ui,i=0,1,2,…,n. Combined with a series of weight factors that can affect the shape of the curve, the mathematical expression of the vector function is as follows:(1)Pu=∑i=0nωidiNi,ku∑i=0nωiNi,ku=∑i=0ndiBi,ku,Bi,ku=ωiNi,ku∑j=0nωjNj,ku.In the formula,Bi,ku is the basis function of the k-th normal B-spline; di is the control vertex, also known as the De Boor point; ωi is the weight factor; and u is the parameter value.The weight factor introduced by the NURBS function can realize the local correction of curve flexibly. Before thek-means algorithm clusters the trajectory, first, our method fits the NURBS curve through B-spline quadratic interpolation and, then, calculates the first-order guide vector of all the trajectory points, which is equal to the tangent slope passing through the point in 2D plane. If the curve is smooth and continuous, then the tangent slopes of all trace points on the curve will change between the slopes of the two control points; otherwise, it indicates that there are irregular points on the curve. According to the nearest point search algorithm of k-d Tree [15], all irregular points can be found by traversing the whole trajectory, and the best trajectory can be obtained by NURBS curve fitting again.


### 2.1. NURBS Curve Fitting of Track Points

Based on detection results of vehicles, their track matching was used to eliminate irregular measurement points by the piecewise straight-line fitting method. However, the trajectory fitted by this method is not smooth, and there are many inflexion points; secondly, due to the influence of perspective projection transformation of image, the position of many points has been distorted, so it is unable to predict the macromotion trajectory of the vehicle intuitively. In this paper, the NURBS function in the theory of curve geometry [16], is applied to the fitting of vehicle trajectory. It has good invariance to perspective projection transformation. It can effectively eliminate irregular points, improve the representation ability of trajectory, and ensure that the traffic flow at intersections can be accurately predicted through the processing of the trajectory subregion and subdirection. The essence of NURBS curve fitting based on trajectory points is to interpolate or fit the measurement points into smooth curves.The trajectory curve fitting steps are as follows:(1)
We calculate the parameter values and node vectors in theU or V direction of the curve from the measurement point data of the vehicle target trajectory(2)
The node vector interval of each parameter value is determined, and all basis functions are obtained(3)
A set of equations with curve control point (type value point) as unknown quantity is established, and the coordinates of the curve control point are obtained by solving the equationsWe assume that the measurement point (track point) of the track is(2)Bk,k=0,1,…,n.The NURBS curve is fitted by the interpolation function to the measuring points:(3)Cu=∑i=0nNi,puPi,U=0,…,0︸p+1,up+1,…,um−p−1，1,…,1︸p+1.Among them,Pi is the type value point, the parameter u¯k corresponding to measurement point Bk is calculated by the chord length parameterization method, and the node vector U is determined by the mean value method. In this way, after the basis function is found, it is substituted with the type value point into the following formula for calculation:(4)Bk=Cu¯k=∑i=0nNi,pu¯kPi.After that, a system of equations with the pointPi as an unknown is obtained, and it is composed of n + 1 equations but n + 3 unknowns, belonging to the overdetermined system of equations with no linear solution, so we need to establish other two equations to solve it. Considering the particularity of the first and end points, the mathematical relationship between the first-order derivative vector D0, Dn and the adjacent type value points P0, P1 and Pn−1,Pn is as follows:(5)−P0+P1=up+1pD0,(6)−Pn−1+Pn=um−p−1pDn.Combining equations (5) and (6) with equation (3), a system of linear equations whose coefficient matrix is (n + 3) ∗ (n + 3) is obtained, and then, we can solve this system and get the 2D coordinates of n + 3 control points. Then, the NURBS curve is fitted with a nonrational quadratic B-spline interpolation function, and the derivative of the vector is obtained at any point as follows:(7)C′u=−21−uPj−1+21−2u×−1−u2Pj−1+−u2Pj+12u1−uPj+2uPj+1.Among them,Pj−1, Pj, and Pj+1 are three adjacent measurement points in the NURBS curve, and the parameter u=xj−xj−12+yj−yj−12/xj−xj−12+yj−yj−12+xj+1−xj2+yj+1−yj2.


### 2.2.K-Means Trajectory Clustering

There is a big deviation in thek-means algorithm due to the uncertainty of the initial clustering center. In our manuscript, the minimum distance is proposed as a measurement criterion to select the initial clustering center. In view of the fact that the start and end points of each moving vehicle’s trajectory at the intersection must be clustered in each intersection area, it is accurate and simple to predict the trajectory trend with them. All the vehicle’s movement trajectories obtained by fitting NURBS are represented by sets PstartandPend of start and end points. We calculate the normalized Euclidian distance between any two points in set PstartandPend; find the samples with the shortest distance by the quicksort method and write it as Pd0 and Pdn; calculate the Euclidean distance between them and residual sample points in the set PstartandPend; find out the sample points with the smallest distance from the center of Pd0 and Pdn; increase them to Pd0 and Pdn, and repeat this process until we have k sets of objects. Finally, k object sets are averaged numerically to form a group of clustering centers, which are used as the initial clustering centers when k-means algorithm is used to complete the trajectories clustering, and k clustering centers Jk are obtained. The centroid is taken as the central location of the intersectionJe, and k is equal to the number of intersection areas.


## 2.1. NURBS Curve Fitting of Track Points

Based on detection results of vehicles, their track matching was used to eliminate irregular measurement points by the piecewise straight-line fitting method. However, the trajectory fitted by this method is not smooth, and there are many inflexion points; secondly, due to the influence of perspective projection transformation of image, the position of many points has been distorted, so it is unable to predict the macromotion trajectory of the vehicle intuitively. In this paper, the NURBS function in the theory of curve geometry [16], is applied to the fitting of vehicle trajectory. It has good invariance to perspective projection transformation. It can effectively eliminate irregular points, improve the representation ability of trajectory, and ensure that the traffic flow at intersections can be accurately predicted through the processing of the trajectory subregion and subdirection. The essence of NURBS curve fitting based on trajectory points is to interpolate or fit the measurement points into smooth curves.The trajectory curve fitting steps are as follows:(1)
We calculate the parameter values and node vectors in theU or V direction of the curve from the measurement point data of the vehicle target trajectory(2)
The node vector interval of each parameter value is determined, and all basis functions are obtained(3)
A set of equations with curve control point (type value point) as unknown quantity is established, and the coordinates of the curve control point are obtained by solving the equationsWe assume that the measurement point (track point) of the track is(2)Bk,k=0,1,…,n.The NURBS curve is fitted by the interpolation function to the measuring points:(3)Cu=∑i=0nNi,puPi,U=0,…,0︸p+1,up+1,…,um−p−1，1,…,1︸p+1.Among them,Pi is the type value point, the parameter u¯k corresponding to measurement point Bk is calculated by the chord length parameterization method, and the node vector U is determined by the mean value method. In this way, after the basis function is found, it is substituted with the type value point into the following formula for calculation:(4)Bk=Cu¯k=∑i=0nNi,pu¯kPi.After that, a system of equations with the pointPi as an unknown is obtained, and it is composed of n + 1 equations but n + 3 unknowns, belonging to the overdetermined system of equations with no linear solution, so we need to establish other two equations to solve it. Considering the particularity of the first and end points, the mathematical relationship between the first-order derivative vector D0, Dn and the adjacent type value points P0, P1 and Pn−1,Pn is as follows:(5)−P0+P1=up+1pD0,(6)−Pn−1+Pn=um−p−1pDn.Combining equations (5) and (6) with equation (3), a system of linear equations whose coefficient matrix is (n + 3) ∗ (n + 3) is obtained, and then, we can solve this system and get the 2D coordinates of n + 3 control points. Then, the NURBS curve is fitted with a nonrational quadratic B-spline interpolation function, and the derivative of the vector is obtained at any point as follows:(7)C′u=−21−uPj−1+21−2u×−1−u2Pj−1+−u2Pj+12u1−uPj+2uPj+1.Among them,Pj−1, Pj, and Pj+1 are three adjacent measurement points in the NURBS curve, and the parameter u=xj−xj−12+yj−yj−12/xj−xj−12+yj−yj−12+xj+1−xj2+yj+1−yj2.


## 2.2.K-Means Trajectory Clustering

There is a big deviation in thek-means algorithm due to the uncertainty of the initial clustering center. In our manuscript, the minimum distance is proposed as a measurement criterion to select the initial clustering center. In view of the fact that the start and end points of each moving vehicle’s trajectory at the intersection must be clustered in each intersection area, it is accurate and simple to predict the trajectory trend with them. All the vehicle’s movement trajectories obtained by fitting NURBS are represented by sets PstartandPend of start and end points. We calculate the normalized Euclidian distance between any two points in set PstartandPend; find the samples with the shortest distance by the quicksort method and write it as Pd0 and Pdn; calculate the Euclidean distance between them and residual sample points in the set PstartandPend; find out the sample points with the smallest distance from the center of Pd0 and Pdn; increase them to Pd0 and Pdn, and repeat this process until we have k sets of objects. Finally, k object sets are averaged numerically to form a group of clustering centers, which are used as the initial clustering centers when k-means algorithm is used to complete the trajectories clustering, and k clustering centers Jk are obtained. The centroid is taken as the central location of the intersectionJe, and k is equal to the number of intersection areas.


## 3. Regional Traffic Flow Prediction

In order to facilitate the prediction of partitioned traffic flow, in the polar coordinate system, the motion direction angle (relative toJe) of the trajectory point is introduced, which is as follows:(8)180°π∗arctanyi−ye/xi−xe,if:xi>xe,yi>ye,90°,if:xi=xe,yi>ye,180°+180°π∗arctanyi−ye/xi−xe,if:xi<xe,yi>ye,180°,if:xi<xe,yi=ye,270°+180°π∗arctanyi−ye/xi−xe,if:xi<xe,yi<ye,270°,if:xi=xe,yi<ye,360°+180°π∗arctanyi−ye/xi−xe,if:xi>xe,yi<ye,360°,if:xi>xe,yi=ye,0°,others.Taking the intersection traffic scene as an example, fourθ values can be obtained, and the ascending order is 0°≤θ1<θ2<θ3<θ4≤360°; we calculate θ′=θ1+θ2/2,θ2+θ3/2,θ3+θ4/2,θ4+θ1/2 and arrange it in ascending order as 0°≤θ1′<θ2′<θ3′<θ4′≤360°; then, we call θ1′,θ2′ A-block, θ2′,θ3′ B-block, θ3′,θ4′ C-block, and θ4′,360° and 0,θ1′ the D-block. Other intersection scene intersection area division methods can be analogized.Calculating the direction angleθk and θk′ of motion of the points Pstartand Pend, the vehicle’s movement pattern can be known by judging their respective regions. Assuming that θk belongs to zone A and θk′ belongs to zone C, it is believed that there are vehicles in the direction from A to C. After traversing all the trajectories, traffic flow prediction results in each direction of the classification vehicle can be obtained. Vehicle types can also be obtained based on vehicle target detection technology, so each vehicle trajectory can be marked with category, so that the flow parameters of different types in each region can be counted.


## 4. Experiment and Result Analysis

The experiment only counts the vehicle flow. Based on the statistical data, more traffic flow parameters such as queue length and road proportion can be calculated. Three different intersection scenes including morning and evening rush hours are selected for experiments about 7 days, and the characteristics of experimental data are shown in Table1.Table 1
Experimental scene data.
FeatureScenarioScenario 1Scenario 2Scenario 3Area number443Direction number12126Time quantumPM 5:00 to 5:45AM 7:00 to 8:00AM 7:00 to 8:00Intersection propertyIntersectionIntersectionT-junctionFor each scene, intersection partitions were obtained by combiningk-means trajectory clustering through NURBS curve fitting, and vehicle trajectories in all directions were statistically analyzed to obtain specific results of vehicle flow prediction of different types.Figure1 is the vehicle statistical results of each intersection scene on a certain day by region using our system. Figure 2 is the traffic flow of the scene separately counted every day. Tables 2–4 are the comparison over 7 days between the average results obtained by our algorithm and the manual statistical results based on the absolute error. Among them, NE is the experimental value and NT is the manual monitoring value.(9)Error=NE−NTNT.Figure 1
Vehicle statistical results of each intersection scene by region. (a) Scenario 1. (b) Scenario 2. (c) Scenario 3.
(a)(b)(c)Figure 2
Vehicle statistical results of each day.Table 2
Error analysis of average flow counting results in scenario 1.
FromToTraffic flowABCDTotalAManual statistics020193123417Detection029290114379Error0%4.9%3.3%7.3%9.1%BManual statistics187045601833Detection179044546762Error4.3%02.2%9.2%8.5%CManual statistics7588043206Detection7183042188Error5.3%5.7%02.3%8.7%DManual statistics78189460313Detection74179450300Error5.1%5.3%2.2%04.2%Table 3
Error analysis of average vehicle flow counting results in scenario 2.
FromToTraffic flowABCDTotalAManual statistics01691653238Detection01541652224Error08.9%0%1.9%5.9%BManual statistics270212977Detection270212877Error0%00%3.4%0%CManual statistics273229039541Detection267208039496Error2.3%4.8%00%8.3%DManual statistics3438370109Detection3437370102Error0%2.6%0%06.4%Table 4
Error analysis of average vehicle flow counting results in scenario 3.
FromToTraffic flowABCTotalAManual statistics049682731Detection049628664Error00%7.9%9.1%BManual statistics313072385Detection303070360Error3.2%03%6.5%CManual statistics535150550Detection512150521Error4.3%0%05.3%The experimental results show that the statistical error of traffic flow is small, no matter for theT-junction or the intersection, and the maximum error is less than 10% and it can meet the needs of intelligent transportation applications. In view of the traffic condition unblocked scene, the target is shielded less, and the relative accuracy is slightly higher. For the scene of intersection, the vehicle target has more occlusion, the trajectory caused by it has fault discontinuity, which is effectively bridged through adoption of NURBS curve fitting to irregular points. Therefore, the vehicle flow error of k-means trajectory clustering statistics is much lower than that of the single-lane or multilane statistical method, and the new idea effectively solves the problems of incomplete tracking trajectory and complex calculations.


## 5. Conclusions

The real-time and accurate parameters of traffic flow at urban road intersections are the important basis for setting dynamic timing parameters of traffic signals at intersections. This paper mainly studies the vehicle flow counting method at urban intersections based on vehicle trajectory analysis. On the basis of the traditional method to obtain the tracking trajectory, the smooth track curve is fitted based on the NURBS algorithm, and a minimum distance measurement criterion is designed to select the initial clustering center for improving thek-means trajectory clustering method, then through subordinating the first and end points of the track to the intersection area, the vehicle movement mode is determined, and the traffic flow statistics of each area at the intersection are realized. Experimental results show that the method effectively solves the changeable mode and severe occlusion of moving vehicle problems, under the complex scene at the intersection, traffic statistical error is less than the classical method, and the algorithm is simple and can provide reliable data automatically for the traffic accident warning, road congestion prediction, and route planning.



---

*Source: 1383198-2020-11-17.xml*