A Novel Density Peak Fuzzy Clustering Algorithm for Moving Vehicles Using Traffic Radar

Abstract

The detection of adjacent vehicles in highway scenes has the problem of inaccurate clustering results. In order to solve this problem, this paper proposes a new clustering algorithm, namely Spindle-based Density Peak Fuzzy Clustering (SDPFC) algorithm. Its main feature is to use the density peak clustering algorithm to perform initial clustering to obtain the number of clusters and the cluster center of each cluster. The final clustering result is obtained by a fuzzy clustering algorithm based on the spindle update. The experimental data are the radar echo signal collected in the real highway scenes. Compared with the DBSCAN, FCM, and K-Means algorithms, the algorithm has higher clustering accuracy in certain scenes. The average clustering accuracy of SDPFC can reach more than 95%. It is also proved that the proposed algorithm has strong robustness in certain highway scenes.

1. Introduction

Radar is an important part of the contemporary intelligent transportation system [1,2,3]. Multi-target tracking with radar is also a hot issue in intelligent transportation research [4,5,6]. By tracking passing vehicles, risky driving behavior can be predicted and an early warning signal can be issued [7,8]. Vehicle tracking helps to reduce the occurrence of traffic accidents, and also helps the development of intelligent transportation [9]. Currently, there are many image-based multi-target tracking algorithms [10]. However, these methods do not show good adaptability in the actual traffic scenes. Because they cannot adapt to the effects of weather, environment, and light [11,12]. Since radar signals can be well adapted to complex scenes [13], more and more researchers are beginning to use millimeter-wave radar to solve multi-target tracking problems [14,15] in traffic.

The sampling points collected by the radar are scattered, and doped with noise [16]. Therefore, clustering sampling points before the target tracking can promote better tracking of the targets [17]. The experimental scene of this paper is a straight four-lane highway. In this scene, vehicles in the adjacent lanes may be close to each other during driving. At this time, the sampling points of the vehicles may be close together and cover each other. Current clustering algorithms cannot distinguish adjacent targets and covered targets well, and real-time performance is not good as well. Therefore, the purpose of this paper is to improve the cluster accuracy of adjacent vehicle sampling points in highway scenes.

There are a lot of clustering algorithms at present. For example, partition-based clustering algorithms [18], hybrid density clustering algorithms, graph clustering algorithms, fuzzy clustering algorithms, and so on. The classic one in the partition-based clustering algorithm is the K-Means clustering algorithm [19,20]. This algorithm has a wider application and higher efficiency, but it also has obvious limitations. The algorithm must determine a cluster center of each cluster in advance. The choice of this cluster center determines the quality of the clustering results. The algorithm is sensitive to abnormal sample points and can only process numerical data sets. The FCM (Fuzzy C-Means) algorithm [21,22,23] is a widely used clustering algorithm applied to the field of image segmentation. The algorithm uses a membership degree to determine the similarity of sample points. It is a fuzzy clustering method based on the objective function [24,25,26]. The DBSCAN (Density-Based Spatial Clustering of Applications with Noise) algorithm is a density-based partitioning clustering method. It treats the data set as a collection of several high-density clusters separated by low-density regions. The main feature of this method is that clusters of any shape can be identified [27].

Many researchers have made many improvements to existing algorithms. The K-MODES algorithm proposed by Nguyen [28] overcomes the shortcomings of the K-Means algorithm that can only process numerical data. The K-MEDOIDS algorithm does not calculate the cluster center but directly represents a cluster to represent the cluster, which can effectively handle abnormal data [29,30]. Bezdek’s research team improved the FCM algorithm and they globally optimized the fuzzy objective function [31]. Birant et al. improved the DBSCAN algorithm and proposed a new ST-DBSCAN (Spatial-Temporal DBSCAN) algorithm. The algorithm can find clusters of clusters in non-spatial values, spatial values, and temporal values [32]. In 2014, density peak fast clustering was a new efficient clustering algorithm proposed by Italian researcher Rodriguez et al. [33]. The main idea of the algorithm is that the cluster center has a higher density than the neighborhood, and the cluster center has a relatively large distance from the high-density point.

For the inaccurate clustering results of adjacent vehicles in the highway scenes, this paper constructs a spindle-based density peak fuzzy clustering (SDPFC) system using traffic radar. Our optimization goal is to increase the clustering accuracy of adjacent vehicles in highway scenes. In order to increase the clustering accuracy, the cluster centers and the number of clusters are calculated by the initial clustering algorithm based on density peak. The final clustering result is calculated by the fuzzy clustering algorithm based on spindle update. The main diagram of the spindle-based density peak fuzzy clustering system using traffic radar is shown in Figure 1. The experimental results show that the SDPFC algorithm has advantages in clustering accuracy. In summary, the contributions of this paper can be summarized as follows:

• This paper proposes a spindle-based density peak fuzzy clustering (SDPFC) algorithm. The algorithm is divided into two parts: initial clustering and quadratic correction clustering. The initial clustering is to determine the cluster center and the number of clusters by finding the density peak. The quadratic correction clustering is to correct the clustering results by iterative updating of the fuzzy matrix and the spindle. In this way, the problem of inaccurate clustering of adjacent vehicles is solved.
• SDPFC overcomes the defect that the traditional fuzzy algorithm is not ideal for non-spherical sample set clustering. To improve the accuracy of the clustering algorithm, this paper changes the concept of iteratively updating the cluster center to the update of the spindle. In actual traffic scenes, SDPFC is more reasonable than other commonly used algorithms.
• In order to accelerate the clustering algorithm, the randomly generated initial cluster center is no longer used in this paper. Instead, the ideal initial cluster center is calculated by finding the density peak. In this way, the structure of the SDPFC algorithm is optimized. Since the ideal initial cluster center is close to the real target cluster center, the optimization algorithm greatly reduces the number of iterations.

The rest of this paper is organized as follows. In Section 2, we introduce the data acquisition method of multi-target traffic microwave radar and feature data extraction for vehicles. The data collected include distance, velocity, and angle. In Section 3, the clustering algorithms related to this paper will be introduced. In Section 4, the spindle-based density peak fuzzy clustering algorithm is explained. Section 5 describes the experimental results of several real highway scenes, the performance of several algorithms is compared, and the applicability of the algorithm is discussed. Section 6 summarizes this paper.

2. Radar Signal Preprocessing

The traffic scene in this paper is a straight four-lane highway, as shown in Figure 2. On the highway, safe driving is significant. Therefore, not only the driver’s driving experience but also the strict supervision of the relevant departments are required to avoid accidents [34]. On the highway, long-term cross-lane driving is extremely dangerous. However, in practice, it is found that, if two vehicles are driving in parallel when the driving distance is too close, the sampling points will gather and cover each other [35]. At this time, it is usually judged that this is a car driving on the lane line. This will result in erroneous tracking of vehicle targets. At the same time, false alarms will be issued and the vehicle will be photographed, which will cause the owner to accept the penalty. These problems can result in wasted resources. Therefore, the algorithm in this paper is to solve the problem of inaccurate clustering results of the adjacent vehicle in highway scenes.

The radar systems used in this paper mainly include a radar, camera, and alarm. It is mounted on a beam 7 m above the ground on the side of the lane. In addition, it is capable of monitoring vehicle targets in the longitudinal direction between 50 and 300 m and in the lateral 4–5 lanes. The radar has the ability to monitor passing vehicles on the road. The traffic radar used in this paper has high measurement accuracy. In a distance range of about 150 m, the distance measurement error is about 0.15 m, and the angle measurement error is about 0.1 degrees. By processing the data collected by the radar, information such as the position and speed of each vehicle can be obtained, thereby tracking the trajectory of all vehicles in the current monitoring scene.

The raw data received by the radar are a time-domain signal, which needs to be converted by the following steps:

• Step 1: Receive an echo signal from the radar at the current time;
• Step 2: Transform the echo signal from the time domain to the frequency domain by using FFT (Fast Fourier Transform);
• Step 3: Determine the distance between the vehicle target and the radar-based on the spectrum information of the echo signal by Formula (1):

  $$R=\frac{\mathrm{c}T\Delta f}{2B},$$

  (1)

  where R is the distance from the radar to the target vehicle; c is the speed of light; T is the period of the transmitted signal; $\Delta f$ is the difference frequency between the transmitted signal and the received signal; B is the signal bandwidth;
• Step 4: According to the spectrum information of the echo signal, the angle between the target vehicle and the radar is determined by Formula (2):

  $$\theta =arcsin(\frac{\lambda }{6\pi }·\sum _{l=1}^3\frac{\Delta {\phi }_l}{d_l}),$$

  (2)

  where $\theta$ represents the angle between the target and the normal direction of the radar; $\lambda$ represents the wavelength of the electromagnetic wave emitted by the antenna; $\Delta {\phi }_l$ represents the phase difference between the $l-\mathrm{th}$ antenna and the $l+1-\mathrm{th}$ antenna; $d_l$ represents the distance between the $l-\mathrm{th}$ antenna and the $l+1-\mathrm{th}$ antenna;
• Step 5: According to the distance and angle between the target vehicle and the radar, the two- dimensional coordinate position $(x,y)$ of the target vehicle in the plane rectangular coordinate system is determined by Formulas (3) and (4):

  $$x=R·sin\theta ,$$

  (3)

  $$y=\sqrt{{(R·cos\theta )}^2-h^2},$$

  (4)

  where h represents the height of the radar from the road plane.

This paper establishes a plane rectangular coordinate system in the road plane, and the origin of the plane rectangular coordinate system is the projection position of the radar on the road plane. By transforming the coordinate $(R,\theta )$ in the polar coordinate system to the coordinate $(x,y)$ of the plane rectangular coordinate system, the vehicle trajectory can be visually displayed. The algorithm in this paper mainly uses the coordinate $z=(x,y)$ of the sampling point as input information.

3. Previous Works

3.1. DBSCAN Clustering Algorithm

DBSCAN is a density-based spatial clustering algorithm [36]. The algorithm divides a set of sample points with sufficient density into one cluster [37], and finds a class of arbitrary shape in a set of spatial sample points with noise. The algorithm defines the cluster as the largest set of points connected by density [38]. Before describing the algorithm, we first define several related concepts:

• $\sigma$-Neighborhood: The set of sample points within a given object radius $\sigma$ is called the $\sigma$-Neighborhood of the object in dataset D, denote by $N\sigma \left(z_i\right)=\left\{z_j\in D|dist\left(z_i,z_j\right)\le \sigma \right\}$.
• Core object: For any object $z_i\in D$, if there are at least $minpts$ objects in its $\sigma$-Neighborhood that is, if $|N\sigma \left(z_i\right)|\ge minpts$, then $z_i$ is the core object.
• Directly Density-Reachable: An object $z_j$ is said to be directly density-reachable from an object $z_i$ if $z_j$ is within the $\sigma$-Neighborhood of $z_i$, and $z_i$ is a core object.
• Density-Reachable: $z_j$ is density-reachable to $z_i$ if there exists an object chain $p_1,p_2,\cdots p_T$, such that $p_1=z_j$, $p_T=z_i$ and $p_{k+1}$ is directly density-reachable from $p_k$.
• Density-Connected: An object $z_j$ is density-connected to object $z_i$ with respect to $\sigma$ and $minpts$ if there exists a core object $z_k$ such that both $z_j$ and $z_i$ are directly density-reachable from $z_k$ with respect to $\sigma$ and $minpts$.

The flow of DBSCAN clustering algorithm as shown in Algorithm 1:

Algorithm 1 DBSCAN

Require: sample points z.  Ensure: cluster center $z_i$, and $label$. 1: initialization: $\sigma$-Neighborhood, and $minpts$; 2: repeat 3: traverse all sampling points z and determine whether the point is a core object that satisfies the $\sigma$-Neighborhood; 4: until all sample points are traversed, and find all core object sets that satisfy the $\sigma$-Neighborhood; 5: repeat 6: choose a core object, find all the density-Reachable sample points and generate clusters; 7: remove the density-reachable sample points found in the previous step from the remaining core objects; 8: until core objects are traversed or removed; 9: return: cluster center $z_i$ and $label$;

The DBSCAN clustering algorithm can cluster dense sample points of any shape and can be used in traffic scenes. However, the algorithm needs to coordinate the neighborhood radius and the sample number threshold to find the optimal solution in the current scene. This is more complicated for the user. In addition, in the traffic scene solved in this paper, the radar sampling points of adjacent vehicles are close to each other and the density is similar. The DBSCAN clustering algorithm cannot solve the problem of distinguishing adjacent vehicles in traffic scenes.

3.2. FCM Clustering Algorithm

The FCM algorithm is based on a data clustering method optimized for the objective function [39]. The clustering result is the degree of membership of each data point to the cluster center, and the degree of membership is represented by a numerical value [40,41]. The FCM algorithm is an unsupervised fuzzy clustering method, and no human intervention is needed in the algorithm running process after manually determining the initial parameters [42].

Taking the sample points set of this paper as an example, the sampling points are $z=z_j,j=1,2,\cdots ,m_k$. If the sampling points are divided into cluster i, the cluster center is $i_c,i=1,2,\cdots ,I$. Each sample j belongs to the cluster i with a membership of ${\mu }_{ij}$, so the objective function of the FCM is defined as:

$$J=\sum _{i=1}^I\sum _{j=1}^k{\mu }_{ij}^m{∥z_j-i_c∥}^2.$$

(5)

The sum of the membership degrees of each sample j belonging to a certain cluster i shall be 1:

$$\sum _{i=1}^I{\mu }_{ij}=1,j=1,2,\cdots ,k.$$

(6)

The Lagrange Multiplier Method is used to put the constraint into the objective function, and then expand to get Formula (7):

$$\begin{array}{c}J={\displaystyle \sum _{i=1}^I}{\displaystyle \sum _{j=1}^k}{\mu }_{ij}^m{∥z_j-i_c∥}^2+{\lambda }_1({\displaystyle \sum _{i=1}^I}{\mu }_{ij}-1)+\cdots +{\lambda }_j({\displaystyle \sum _{i=1}^I}{\mu }_{ij}-1)+\cdots +{\lambda }_k({\displaystyle \sum _{i=1}^I}{\mu }_{ik}-1).\hfill \end{array}$$

(7)

The extreme value of J is required. In addition, make the partial derivative result of ${\mu }_{ij}$ and $i_c$ be 0:

$$\left\{\begin{array}{c}\frac{\partial J}{\partial {\mu }_{ij}}=m{∥z_j-i_c∥}^2{\mu }_{ij}^{m-1}+{\lambda }_j=0,\hfill \\ \frac{\partial J}{\partial i_c}=\sum _{j=1}^k(-2{\mu }_{ij}^m(z_j-i_c))=0.\hfill \end{array}\right.$$

(8)

Solve Formula (8):

$$\left\{\begin{array}{c}{\mu }_{ij}=\frac{1}{{\displaystyle \sum _{n=1}^I}{\left(\frac{{∥z_j-i_c∥}^2}{{∥z_j-i_n∥}^2}\right)}^{\frac{2}{m-1}}},\hfill \\ i_c={\displaystyle \sum _{j=1}^k}\frac{{\mu }_{ij}^m}{{\displaystyle \sum _{j=1}^k}{\mu }_{ij}^m}{z}_j.\hfill \end{array}\right.$$

(9)

The flow of the FCM clustering algorithm is as shown in Algorithm 2:

Algorithm 2 FCM

Require: sample points z.  Ensure: cluster center $i_c$, and $label$. 1: initialization: Number of clusters i, weighted index m, termination error $\eta$, and membership matrix ${\mu }_{ij}$; 2: repeat 3: calculate the cluster center position $i_c$ according to Formula (9); 4: update membership matrix ${\mu }_{ij}$ according to new cluster center and Formula (9); 5: until the objective function J tends to be stable according to the condition in Formula (10); 6: return: cluster center $i_c$ and $label$;

$$\epsilon =\sum _{i=1}^I\sum _{j=1}^k(\mathrm{new}{\mu }_{ij}-{\mu }_{ij})<\eta .$$

(10)

The FCM clustering algorithm calculates the membership degree of each sample point. If a sample point has an absolute advantage in the membership degree of a certain cluster, it is a very safe practice to assign the sample point to this cluster. The algorithm is highly accurate. However, some parameters need to be set in the algorithm, the number of clusters i, the weighted index m, and the termination error $\eta$. If the initialization of the parameters is not appropriate, it may affect the correctness of the clustering results. Secondly, when the data sample set is large and the number of features is large, the real-time performance of the algorithm is not good. In addition, in the traffic scene of this paper, the radar sampling points of adjacent vehicles are close, and FCM cannot solve the problem of distinguishing adjacent vehicles.

4. The Spindle-Based Density Peak Fuzzy Clustering (SDPFC) Algorithm

The SDPFC algorithm proposed in this paper is characterized by the idea of using quadratic clustering to correct clustering results. The cluster center of each cluster and the number of clusters are obtained by the initial clustering algorithm based on the density peak [43]. Then, the clustering result of the initial cluster is corrected by the fuzzy clustering algorithm based on the spindle update, and the final clustering result is obtained. The combination of these two clustering ideas will be explained in this section.

4.1. Initial Clustering Algorithm Based on Density Peak

Taking the sampling points of the paper as an example, the sample points set $S={\left\{z_i\right\}}_{i=1}^n$ to be clustered. $I_S=\left\{1,2,\cdots ,n\right\}$ is the corresponding indicator set [44]. Calculate the Euclidean distance $d_{ij}$ between all sample points, as shown in Formula (11). Thus, the number of $d_{ij}$ is $\frac{n\left(n-1\right)}{2}$:

$$d_{ij}=dist\left(z_i,z_j\right).$$

(11)

All $d_{ij}$ are sorted in ascending order, and a percentage parameter p is set, then the truncation distance $d_t$ is defined as the $r-\mathrm{th}$$d_{ij}$, where r is calculated by Formula (12) and $round$ represents rounded off. In the experimental environment of this paper, the sampling points are relatively close, so p in this article is chosen to be 2%. Users can modify p according to their own experimental environment. The larger the p that is selected, the more clusters are filtered out. Therefore, p should be determined through the experimental environment:

$$r=round\left(\frac{n\left(n-1\right)}{2}\ast p\right).$$

(12)

The density ${\rho }_i$ of each sample point $z_i$ is calculated by Formula (13):

$${\rho }_i=\sum _{j\in I_S\backslash \left\{i\right\}}{e}^{-{\left(\frac{d_{ij}}{d_c}\right)}^2}.$$

(13)

For each sample point $z_i$, find all sample points $z_j$ that are denser than the sample point $z_i$ and select the smallest $d_{ij}$, denoted as ${\delta }_i$. If the opposite is true, select the largest $d_{ij}$ and record it as ${\delta }_i$. The significance of this is that the characteristics of ${\rho }_i$ and ${\delta }_i$ can be used to determine whether the sample point is the cluster center. The selection method of ${\delta }_i$ is as shown in Formula (14):

$${\delta }_i=\left\{\begin{array}{c}\underset{j\in I_S^i}{min}\left\{d_{ij}\right\},I_S^i\ne \varnothing ,\hfill \\ \underset{j\in I_S}{max}\left\{d_{ij}\right\},I_S^i=\varnothing ,\hfill \end{array}\right.$$

(14)

where ∅ represents the empty set, and the expression of the indicator set is as shown in formula (15):

$$I_S^i=\left\{k\in I_S:{\rho }_k>{\rho }_i\right\}.$$

(15)

You need to set the threshold parameter to find the center point of each type of sample, set the density threshold to ${\rho }_0$, and the distance threshold to ${\delta }_0$. If ${\rho }_i>{\rho }_0$ and ${\delta }_i>{\delta }_0$ of the sample point $z_i$, the sample point $z_i$ is considered to be the cluster center of a certain cluster.

As shown in Figure 3, this diagram is called a decision diagram. It can be clearly seen in the figure that the colored elements in the upper right corner have a larger $\rho$ and $\delta$. This means that they are more likely to be the center of the cluster. With the decision graph, we can easily determine which points qualify as the center point and which points are not qualified by defining the density threshold ${\rho }_0$ and the distance threshold ${\delta }_0$ according to the experimental environment.

Define ${\left\{m_j\right\}}_{j=1}^{n_c}$ as the number of the corresponding sample point of each cluster center that is, $z_{m_j}$ represents the center of the $j-\mathrm{th}$ cluster. In addition, define ${\left\{c_i\right\}}_{i=1}^n$ as the sample point clustering label, that is, $c_i$ indicates that the $i-\mathrm{th}$ sample point in S belongs to the $c_i-\mathrm{th}$ cluster. Thus, $c_i$ satisfies the logic of Formula (16).:

$$c_i=\left\{\begin{array}{c}k,if(z_{i}istheclustercenterandbelongstothek-thcluster),\hfill \\ -1,otherwise.\hfill \end{array}\right.$$

(16)

Define ${\left\{n_i\right\}}_{i=1}^n$ as the number of nearest sample points in the sample points with the local density greater than $z_i$ in the S, as defined by Formula (17):

$$n_i=\left\{\begin{array}{c}\underset{j\in I_S^i}{argmin}\left\{d_{ij}\right\},I_S^i\ne \varnothing ,\hfill \\ 0,I_S^i=\varnothing .\hfill \end{array}\right.$$

(17)

Using the attributes defined by Formula (17), the sample points are processed one by one by local density—the highest density sample point except for the center point. It falls into the cluster to which it is close. This way of processing one by one is much faster than loop iteration.

Define ${\left\{h_i\right\}}_{i=1}^n$ as the identity of the cluster core and cluster halo. The cluster core indicates that the local density is large, corresponding to the core part of the cluster. The cluster halo is denser and corresponds to the edge of the cluster. The value of $h_i$ is as shown in Formula (18):

$$h_i=\left\{\begin{array}{c}0,z_i\in clustercore,\hfill \\ 1,z_i\in clusterhalo.\hfill \end{array}\right.$$

(18)

If $n_c>1$, an average local density upper bound ${\left\{{\rho }_i^b\right\}}_{i=1}^{n_c}$ is generated for each cluster. For a fixed cluster, first determine its boundary area, which consists of sample points: they belong to the cluster itself, but within a range that does not exceed $d_c$; sample points belong to other clusters. Using the cluster in the boundary area, an average local density can be calculated to distinguish between the cluster core and the cluster halo.

The average density is calculated as shown in Formula (19):

$$\overline{\rho }=\frac{{\rho }_i+{\rho }_j}{2}.$$

(19)

The upper bound of the average local density is obtained by Formula (20):

$$\left\{\begin{array}{c}{\rho }_{c_i}^b=\overline{\rho },\overline{\rho }>{\rho }_{c_i}^b,\hfill \\ {\rho }_{c_j}^b=\overline{\rho },\overline{\rho }>{\rho }_{c_j}^b.\hfill \end{array}\right.$$

(20)

The value of $h_i$ is as shown in Formula (21):

$$\left\{\begin{array}{c}{h}_i=1,{\rho }_i<{\rho }_{c_i}^b,\hfill \\ h_i=0,otherwise.\hfill \end{array}\right.$$

(21)

The general calculation process of the initial clustering algorithm based on the density peak is described below. Firstly, after initialization and preprocessing, calculate the Euclidean distance $d_{ij}$ between all sample points and determine the cutoff distance $d_t$ according to Formula (12). Calculate ${\rho }_i$ and ${\delta }_i$ for each sample point. Secondly, determine the cluster center and initialize the label according to Formula (16). The cluster centers and their numbers of the cluster are finally obtained. Thirdly, the sample points that are not cluster centers are categorized until the categorization process for each sample point is completed. Finally, if $n_c>1$, the sample points in each cluster are further divided into cluster core and cluster halo.

The flow of initial clustering algorithm based on density peak as shown in Algorithm 3:

Algorithm 3 Initial clustering algorithm based on density peak

Require: sample points z.  Ensure: cluster center $z_i$, the number of clusters i, and $label$.  1: initialization: cutoff distance $d_t$, cluster center number i, density threshold ${\rho }_0$, and distance threshold ${\delta }_0$;  2:   for $i\leftarrow 1tondo$  3:     for $j\leftarrow 1tondo$  4:       calculate the Euclidean distance $d_{ij}$ between all sample points and calculate ${\rho }_i$ and ${\delta }_i$ for each sample point.  5:     end for  6:   end for  7: repeat  8: get the cluster center $z_i$ and its number i;  9: until classify all sample points that are not cluster centers; 10:   for $i\leftarrow 1tondo$ 11:     if $n_c>1$ then 12:       the sample points in each cluster are further divided into cluster core and cluster halo according to Formula (21); 13:       end if 14:   end for 15: return: cluster center $z_i$, the number of clusters i, and $label$;

Taking a scene on the highway as an example, the clustering result of the initial cluster is shown in Figure 4. The horizontal and vertical coordinates in the figure indicate the distance. Each point in the graph represents each sample point. This graph is an image generated from the distance between sample points. Therefore, the distance between each sampling point in the graph is real, but their coordinate positions are not real positions. This graph is only used to clearly show the cluster centers and the number of clusters.

4.2. Fuzzy Clustering Algorithm Based on Spindle Update

According to the results obtained in the previous section, the correction after initial clustering is performed to obtain the final clustering result. The results of the previous section used in this section are: position coordinate information of all sampling points, cluster centers, and the number of clusters. Define $i=1,2,\cdots ,I$ represents the $i-\mathrm{th}$ cluster, and $z_0^{(i)}$ for the $i-\mathrm{th}$ cluster center.

The radar used in the article is a traffic scene monitoring radar that is mounted above the side of the lane. Therefore, the positional relationship between the radar and the lane is unchanged. The normal driving situation of the vehicle is that the vehicle travels forward between the lane lines. In addition, it is illegal to travel across the lane for a long time. Whether driving normally or across the lane, the vehicle travels in a direction parallel to the centerline of the lane. Therefore, based on the results obtained in the previous section, we use the straight line passing through the cluster center and parallel to the centerline of the lane as an important basis to correct the results of the initial clustering, so as to obtain better clustering results. We traveled on the road in advance through a dedicated calibration vehicle. The collected lane centerline is used as the initial spindle. Record the slope of the initial spindle as $a_0$.

According to the above characteristics, the initial spindle is constructed based on the center of each cluster and the centerline of the lane. The initial spindle is a straight line parallel to the centerline of the lane and passing through the cluster center. Express the spindle of cluster i as $L_c^{(i)}$, and its expression is: $y=a^{(i)}x+b^{(i)}$, where $i=1,2,\cdots ,I$ represents the $i-\mathrm{th}$ cluster and $j=1,2,\cdots ,k$ represents the $j-\mathrm{th}$ sample point, and the value of k is the number of all sample points except the cluster center. The expression with $a_0$ as the slope and the initial spindle passing through the cluster center $z_0^{(i)}=(x_0^{(i)},y_0^{(i)})$ of each cluster is:

$$y=a_0^{(i)}x+b_0^{(i)}.$$

(22)

The position coordinates of the sample points obtained in the plane rectangular coordinate system are defined as:

$$z_j=(x_j,y_j).$$

(23)

In the text, the distance between the $j-\mathrm{th}$ sample and the spindle of the $i-\mathrm{th}$ cluster is expressed by Formula (24), and its value is $D_j^{(i)}$:

$$z_j\sim L_c^{(i)}.$$

(24)

Define the objective function T, and the expression is as shown in Formula (25):

$$T=\sum _{i=1}^I\sum _{j=1}^k{\mathbf{B}}_{ij}^{m}D{{}_j^{(i)}}^2,$$

(25)

where $\mathbf{B}$ represents a fuzzy matrix, indicating the confidence that the sample points belong to a certain cluster. m represents the factor of membership, that is, the weight. This value can be determined by the user. The constraint of $\mathbf{B}$ is:

$$\sum _{i=1}^I{\mathbf{B}}_{ij}=1,j=1,2,\cdots ,k.$$

(26)

In order to achieve the optimal solution of the objective function, it is necessary to make T obtain a minimum value under the constraint condition. The Formula (25) is expanded using the Lagrange method:

$$\begin{array}{c}T={\displaystyle \sum _{i=1}^I}{\displaystyle \sum _{j=1}^k}{\mathbf{B}}_{ij}^{m}D{{}_j^{(i)}}^2+{\lambda }_1({\displaystyle \sum _{i=1}^I}{\mathbf{B}}_{ij}-1)+\cdots +{\lambda }_j({\displaystyle \sum _{i=1}^I}{\mathbf{B}}_{ij}-1)+\cdots +{\lambda }_k({\displaystyle \sum _{i=1}^I}{\mathbf{B}}_{ik}-1).\hfill \end{array}$$

(27)

The proof that Formula (25) is a continuously differentiable function is shown in Appendix A. In addition, the result of the partial derivative of T is:

$$\frac{\partial T}{\partial {\mathbf{B}}_{ij}}=mD{{}_j^{(i)}}^2{\mathbf{B}}_{ij}^{m-1}+{\lambda }_j=0.$$

(28)

Calculate ${\mathbf{B}}_{ij}$:

$$\begin{array}{c}{\mathbf{B}}_{ij}^{m-1}=\frac{-{\lambda }_j}{mD{{}_j^{(i)}}^2}\Rightarrow {\mathbf{B}}_{ij}={\left(\frac{-{\lambda }_j}{m}\right)}^{\frac{1}{m-1}}\left(\frac{1}{{(D{{}_j^{(i)}}^2)}^{\left(\frac{2}{m-1}\right)}}\right),\hfill \end{array}$$

(29)

where ${\mathbf{B}}_{ij}$ represents the membership between the $j-\mathrm{th}$ sampling point and the $i-\mathrm{th}$ clustering center. Substitute ${\mathbf{B}}_{ij}$ into Formula (26):

$${\left(\frac{-{\lambda }_j}{m}\right)}^{\frac{1}{m-1}}\sum _{n=1}^I\left(\frac{1}{{(D{{}_j^{(n)}}^2)}^{\left(\frac{2}{m-1}\right)}}\right)=1,$$

(30)

where n represents the $n-\mathrm{th}$ cluster center. Simplify Formula (30):

$$\begin{array}{c}{\left(\frac{-{\lambda }_j}{m}\right)}^{\frac{1}{m-1}}=\frac{1}{{\displaystyle \sum _{n=1}^I}\left(\frac{1}{{(D{{}_j^{(n)}}^2)}^{\left(\frac{2}{m-1}\right)}}\right)}.\hfill \end{array}$$

(31)

Substitute Formula (31) into Formula (29):

$$\begin{array}{c}{\mathbf{B}}_{ij}=\frac{1}{{\displaystyle \sum _{n=1}^I}\left(\frac{1}{{(D{{}_j^{(n)}}^2)}^{\left(\frac{2}{m-1}\right)}}\right)}\left(\frac{1}{{(D{{}_j^{(i)}}^2)}^{\left(\frac{2}{m-1}\right)}}\right)=\frac{1}{{\displaystyle \sum _{n=1}^I}{\left(\frac{D{{}_j^{(i)}}^2}{D{{}_j^{(n)}}^2}\right)}^{\frac{2}{m-1}}}.\hfill \end{array}$$

(32)

It can be clearly seen from Formula (32) that, if you want to obtain the membership ${\mathbf{B}}_{ij}$ between the $j-\mathrm{th}$ sample point and the $i-\mathrm{th}$ cluster center, you need to calculate the ratio of the distance from the sample point to a cluster center to the sum of the distances from the sample point to all cluster centers. The higher the ratio, the higher the membership. The Formula (32) is the updated formula for ${\mathbf{B}}_{ij}$. While updating the fuzzy matrix $\mathbf{B}$, the spindle needs to be updated.

Spindle update process:

The straight line formula of the spindle is: $y=a^{(i)}x+b^{(i)}$. The sample points are: $z_j:(x_1,y_1),(x_2,y_2),\cdots ,(x_{m_k},y_{m_k})$.

$D_j^{(i)}$ is the distance from the sample point to the spindle of the $i-\mathrm{th}$ cluster:

$$D_j^{(i)}=\left\{\begin{array}{c}\frac{\left|a^{(i)}{x}_j-y_j+b^{(i)}\right|}{\sqrt{a^{(i)2}+1}},\left(y_0^{(i)}-\frac{d_c}{sin\left(arctan\left(a^{(i)}\right)\right)}\right)\le y_j\le \left(y_0^{(i)}+\frac{d_c}{sin\left(arctan\left(a^{(i)}\right)\right)}\right),\hfill \\ \sqrt{\left(x{{}_j^{(i)}}^2-{x_j}^2\right)+\left(y{{}_j^{(i)}}^2-{y_j}^2\right)},otherwise.\hfill \end{array}\right.$$

(33)

Next, we need to reconstruct the clusters of the sample points. If the ordinate of the sample point is within the distance $d_c$ from the ordinate of the cluster center of a certain cluster, calculate the distance from the sample point to the spindle. Otherwise, calculate the Euclidean distance of the sample point to the cluster center. When $D_j^{(i)}$ is the minimum value, it is judged that the sample point is classified into the $i-\mathrm{th}$ cluster.

The following update processes take place within the new clusters of reconstructing. Taking a certain cluster as an example, the spindle is updated in the following ways.

Define $\delta$ as the sum of the squares of the errors. The expression is:

$$\delta =\sum _{j=1}^m{D}_j=\sum _{j=1}^m{(y_j-a{x}_j-b)}^2,$$

(34)

where m represents the number of sample points outside the center of a certain cluster. Calculate the partial derivative of a, b respectively:

$$\begin{array}{c}\left\{\begin{array}{c}\frac{\partial \delta }{\partial a}=-2({\displaystyle \sum _{j=1}^m}{x}_j{y}_j-b{\displaystyle \sum _{j=1}^m}{x}_j-a{\displaystyle \sum _{j=1}^m}{x_j}^2),\hfill \\ \frac{\partial \delta }{\partial b}=-2({\displaystyle \sum _{j=1}^m}{y}_j-{\displaystyle \sum _{j=1}^m}b-a{\displaystyle \sum _{j=1}^m}{x}_j),\hfill \end{array}\right.\hfill \\ \Rightarrow \left\{\begin{array}{c}\frac{\partial \delta }{\partial a}=-2({\displaystyle \sum _{j=1}^m}{x}_j{y}_j-bm\overline{x}-a{\displaystyle \sum _{j=1}^m}{x_j}^2),\hfill \\ \frac{\partial \delta }{\partial b}=-2(m\overline{y}-bm-am\overline{x}).\hfill \end{array}\right.\hfill \end{array}$$

(35)

Let the two formulas of Formula (35) be 0, and get:

$$\left\{\begin{array}{c}a=\frac{{\displaystyle \sum _{j=1}^m}(x_j-\overline{x})(y_j-\overline{y})}{{\displaystyle \sum _{j=1}^m}{(x_j-\overline{x})}^2},\hfill \\ b=\overline{y}-a\overline{x}.\hfill \end{array}\right.$$

(36)

The flow of the fuzzy clustering algorithm based on spindle update as shown in Algorithm 4:

Algorithm 4 Fuzzy clustering algorithm based on spindle update

Require: sample point set $z_j^{(i)}$, the number of clusters i, cluster center $z_0^{(i)}$.  Ensure: cluster center $z_0^{(i)}$, and $label$. 1: initialization: weighted index m, membership matrix $\mathbf{B}$, spindle slope $a_0$, spindle of each cluster $L_c^{(i)}$, and termination error $\eta$; 2: repeat 3: update membership matrix $\mathbf{B}$ according to Formula (32); 4: update the spindle of each cluster according to Formula (36); 5: until the objective function T tends to be stable according to the condition in Formula (37); 6: return: cluster center $z_0^{(i)}$ and $label$;

$$V=\sum _{i=1}^I\sum _{j=1}^k(\mathrm{new}{\mathbf{B}}_{ij}-{\mathbf{B}}_{ij})<\eta .$$

(37)

The initial clustering results of the previous section are subjected to quadratic modified clustering, and the final clustering result is shown in Figure 5.

5. Comparison of Experimental Results

The experimental scene in this paper is a straight four-lane highway scene with the radar mounted above the side of the lane, as shown in Figure 6. The vehicles on the highway are characterized by a fast speed and large distance between front and rear. However, during the driving process, the approach of the vehicle will occur, which will cause the radar sampling points to approach and cover each other. The current commonly used clustering algorithms cannot accurately distinguish between adjacent and covered vehicle targets. The spindle-based density peak fuzzy clustering algorithm proposed in this paper can better solve the clustering problem of adjacent vehicles in this scene.

Scene 1: There are three vehicles with a relatively short distance on the straight four-lane highway. Among them, two large vehicles have a lateral distance that is very close to each other and the other one is farther away from the two cars, as shown in Figure 7. At this time, the radar returns a total of 117 valid sampling points, and the distribution of sampling points is shown in Figure 8.

The comparison of clustering results of various algorithms in this scene is shown in Figure 9.

In this scene, two large cars cover each other, resulting in an uneven distribution of sampling points. The DBSCAN algorithm classifies by density and results in a large number of clusters. The iterative update of the fuzzy matrix and the cluster center by the FCM algorithm cannot solve the problem of distinguishing adjacent targets well. The K-Means algorithm does not classify well for adjacent sample points. The clustering results obtained by the SDPFC algorithm in this paper can correspond well to the real scene. Compared with the results of other algorithms, the conclusion of the new algorithm is better.

Scene 2: There are three vehicles with a close driving distance on the straight four-lane highway. The lateral distance between the two vehicles is very close and the large vehicle covers the small vehicle. The other one is farther away from the two vehicles, as shown in Figure 10. At this time, the radar returns a total of 115 valid sampling points, and their distribution is shown in Figure 11.

The comparison of clustering results of various algorithms in this scene is shown in Figure 12.

In this scene, a large car covers a small car, resulting in fewer sample points for the small car. The DBSCAN algorithm classifies by density and results in a large number of clusters. The iterative update of the fuzzy matrix and the cluster center point by the FCM algorithm cannot solve the problem of distinguishing adjacent targets well. The K-Means algorithm does not classify well for adjacent sample points. The clustering results obtained by the density peak fuzzy clustering algorithm in this paper can correspond well to the real scene. Compared with the results of other algorithms, the conclusion of the new algorithm is better.

Scene 3: There are five vehicles with a relatively short driving distance on the straight four-lane highway. There are many vehicles blocking each other, as shown in Figure 13. At this point, the radar returns a total of 202 valid sampling points, and their distribution is shown in Figure 14.

The comparison of clustering results of various algorithms in this scene is shown in Figure 15.

In this scene, the number of adjacent vehicles is relatively large, and several vehicles are covering each other, resulting in uneven distribution of sampling points and fewer sampling points for small cars. The DBSCAN algorithm classifies by density and results in a large number of clusters. The iterative update of the fuzzy matrix and the cluster center point by the FCM algorithm cannot solve the problem of distinguishing adjacent targets well. The K-Means algorithm does not classify well for adjacent sample points. The clustering results obtained by the density peak fuzzy clustering algorithm in this paper can correspond well to the real scene. Compared with the results of other algorithms, the conclusion of the new algorithm is better.

Next, in order to compare the clustering accuracy of each algorithm, the accuracy of the clustering is defined as:

$$Rate=\frac{K}{N}\times 100\%,$$

(38)

where $Rate$ represents the clustering accuracy rate; K represents the number of sampling points for correct clustering; N represents the total number of sample points participating in the classification. The accuracy comparison of each algorithm is shown in Figure 16.

It can be seen from the figure that, for the three practical experimental scenes in this paper, the SDPFC algorithm proposed in this paper has the best results, and the average accuracy can reach more than 95%.

In order to present the clustering results of the SDPFC algorithm better, in addition to the above three classic scenes, four scenes with adjacent vehicles are selected. The real situation of the four scenes are shown in Figure 17. In addition, the clustering results of the SDPFC algorithm are shown in Figure 18.

In order to visually compare the real-time performance of each algorithm, this paper selects ten different traffic scenes and performs the same experiments on the four algorithms mentioned in this paper to verify the real-time performance of the algorithm. Select all sampling points in about 0.2 s as the input data for the experiment in each scene.

As can be seen from

Table 1. Time-consuming table for each algorithm.

Time Consuming/s	Algorithms
Experiment Number	DBSCAN	FCM	K-Means	SDPFC
1	0.0139	0.0358	0.0270	0.0330
2	0.0128	0.0318	0.0296	0.0298
3	0.0141	0.0337	0.0262	0.0322
4	0.0138	0.0325	0.0265	0.0351
5	0.0129	0.0358	0.0254	0.0325
6	0.0132	0.0334	0.0259	0.0329
7	0.0135	0.0315	0.0249	0.0332
8	0.0139	0.0324	0.0266	0.0336
9	0.0134	0.0349	0.0271	0.0332
10	0.0136	0.0338	0.0256	0.0319
Average time consumption/s	0.0135	0.0336	0.0266	0.0327

, the SDPFC algorithm proposed in this paper is the fastest of the four algorithms, and it is about 2.04 times faster than the slowest algorithm. The K-Means algorithm is ranked second because of its simple calculation method. The slowest running speed is the FCM algorithm, mainly because of the uncertainty of the initial point in the FCM algorithm, resulting in the number of iterative updates that have been maintained at a high level.

After comparing the clustering accuracy and running speed of each algorithm in a certain scene, this paper presents statistical images of the average of the accuracy of various algorithms in several specific scenes. The purpose is to show the stability of the clustering of these algorithms in the given scene. It can be seen from Figure 19 that the SDPFC algorithm proposed in this paper has good adaptability in a certain scene and can maintain high accuracy. In addition, the K-Means algorithm is more adaptable, but the accuracy is not high. The adaptability of DBSCAN and FCM is relatively poor, but the accuracy of DBSCAN is significantly higher than that of FCM.

In order to show the clustering results of the SDPFC algorithm better, a new experiment is performed. Statistics on the accuracy of clustering adjacent vehicles in 1000 scenes. A vehicle sampling point collected every 40 milliseconds is defined as a scene. In each scene, there are 2–5 passing vehicles, and the radar echo signals are processed to obtain 100–300 sampling points. Comparing each scene with the real image and the clustering result graph, calculate the clustering accuracy according to the concept proposed by Formula (38). The specific experimental results are shown in Figure 20, where 1 on the abscissa represents the average clustering accuracy of the scene 1 to the scene 100, 2 represents the average clustering accuracy of the scene 101 to the scene 200, and so on. Finally, according to statistics, 3627 passing vehicles are processed in 1000 scenes, of which 3537 obtained correct clustering results. The correct clustering rate is about 97.52%.

Through the experiments in this section, we can conclude that: under the real highway traffic scene given in this paper, the SDPFC algorithm proposed in this paper can solve the problem of inaccurate clustering results of adjacent vehicles. The algorithm can complete the operation in a short time while maintaining high accuracy and has strong adaptability to scene changes.

6. Conclusions

This paper proposes a new quadratic modified clustering algorithm called a Spindle-based Density Peak Fuzzy Clustering (SDPFC) algorithm, which has several new features. After analyzing the characteristics of the radar sampling points of the vehicles in the experimental scene, it was found that each sampling point cluster of the vehicle would have a density peak. Using this feature, the initial clustering algorithm based on density peak is first used to obtain the number of clusters, that is, the number of vehicles and the cluster center of each cluster. Next, using the two important pieces of information just obtained, the clustering result of the first step is corrected by the iterative updating method of the fuzzy matrix and the spindle, and then the final clustering result is obtained. In this paper, experimental data are collected from real highway scenes. Three typical experimental scenes are listed in the paper. The experimental results show that the proposed algorithm can solve the clustering problem of adjacent vehicles and covered vehicles in some specific scenes of the highway. The algorithm has high accuracy, high real-time, and strong robustness.