# Moving Vehicle Tracking Optimization Method Based on SPF

Authors: Caixia Lv; Xuejing Zhang
Journal: Complexity
 (2020)

---

## Abstract

In the intelligent transportation system, the license information can be automatically recognized by the computer and the vehicle can be tracked. Red light running, illegal change of lanes, vehicle retrograde, and other illegal driving events are reasonably recorded. This is undoubtedly an effective help for the traffic police to relieve the huge work pressure. However, in China, a considerable number of vehicle tracking methods have certain limitations in resisting complex external environmental influences. The external environmental factors include but not limited to variable factors such as camera movement, jitter, and severe rain and snow. These factors cannot be controlled well, so the tracking accuracy is greatly reduced. In regard to this, this paper proposes an optimization method for moving vehicle tracking based on SPF. First, according to the size of the overlapping area of the motion area between the two images, the researcher can construct and simplify the vertex adjacency matrix that reflects the characteristics of the undirected bipartite graph. Then according to the corresponding relationship between the vertex adjacency matrix and the regional behavior and vehicle behavior, the researcher completes the regional behavior analysis and vehicle behavior analysis. On this basis, a particle filter vehicle tracking algorithm based on segmentation compensation is introduced, and the vector sum of the tracked segmentation area is used as the final position of the target vehicle. In this way, as many scattered particles fall on the target area as possible, which will greatly improve the efficiency of particle utilization, enhance tracking accuracy, and avoid the problem of tracking failure caused by too fast vehicle movement. Through experimental simulation, it can be seen that the method proposed in this paper can greatly enhance the vehicle tracking ability when tracking vehicles in “complex environments.”


---

## Body

## 1. Introduction

In the application of target tracking that involves getting close to people’s livelihood, one of the most critical areas is vehicle tracking. Vehicles on the roads in China have gradually transitioned from being dominated by bicycles to being dominated by automobiles with the continuous improvement of related technologies in the industry and the great optimization of residents’ quality of life. Family ownership of cars is about to leap forward, and more and more families own their own cars, making road traffic more and more burdensome. On the other hand, urban construction has been finalized, and roads in the city have nowhere to be repaired. The limited number of roads corresponds to the increasing number of cars, causing frequent traffic accidents. These problems put forward more stringent requirements on road traffic management and gradually formed the concept of an intelligent transportation system. Intelligent transportation can use the sensitivity of the computer to identify the information of passing vehicles and record the route of the vehicle in real time. In this way, any traffic violations such as running a red light, illegally changing lanes, and vehicles going backward will be recorded. It will greatly reduce the work pressure of traffic police, improve driving safety, and reduce traffic accidents.Academic research in the field of vehicle tracking is very complicated. With the rapid development of information technology, video surveillance has penetrated into all areas of people’s production and life and naturally attracted the attention of scholars from all over the world. There are many countries that have invested a lot of manpower, material, and financial resources to in-depth research and solved problems in the field of vehicle tracking, which better promotes the rapid development of the transportation field. The 8th literature introduced the Kalman filter algorithm and related mathematical theories into the target tracking algorithm, which promoted the development of vehicle tracking technology during this period. However, this method is difficult to adapt to the weather, environment, and external light factors, which will lead to the problem of low vehicle tracking accuracy. The 9th literature made outstanding contributions in several aspects such as mean shift theory, probabilistic multihypothesis tracking, variable structure multimodel, and distributed target fusion, which had pushed the field of vehicle tracking forward. But this method was subject to fall into the optimal solution. The 10th literature proposed a vehicle tracking method based on feature extraction of vehicle edges. In this method, the target edge information was obtained by detecting the changing gray value, then the vehicle characteristics were proposed, and the tracking of the vehicle was completed on this basis. This method had high stability to external factors such as light. But there is a problem that tracking takes a long time.For this reason, an SPF-based optimization method for moving vehicle tracking is proposed in this paper. Particularly for the background failure due to the influence of weather interference, changing the optical fiber and other dynamic factors on the background, according to the size of the overlapping area of the moving area between the two frames of images, this paper constructs and simplifies the vertex adjacency matrix reflecting the characteristics of the undirected bipartite graph. Then, according to the corresponding relationship between the vertex adjacency matrix and the regional behavior and vehicle behavior, a particle filter algorithm (SPF) based on segmentation compensation is proposed for the problem that the vehicle tracking model is easy to fall into the optimal solution [1]. During the process of tracking the target vehicle, this algorithm divides the target into multiple regions. Based on the local features of the selected target in these regions, if the tracked target is partially occluded or the shape changes, other regions of the target can be used instead of tracking, which can make the particle filter more accurate and applicable. Regarding the time-consuming problem of the vehicle tracking process, this paper adds the resampling calculation after calculating the weight of the particles. The particles are resampled according to the weight of the particles, and particles with small weights are deleted, which reduces the amount of calculation time.


## 2. Behavior Analysis of Moving Vehicles Based on Directionless Two-Part Graph

### 2.1. Principles of Vehicle Behavior Analysis

The directionless two-part graph is a very useful mathematical model, which has important applications in many scientific fields. The directionless two-part graph can be used to describe many problems, for example, “data allocation,” “work arrangement,” “time allocation,” and “personnel selection.” This paper combines the directionless two-part graph with the behavior analysis of the vehicle in the video and uses the vertex adjacency matrix representing the directionless two-part graph to determine the behavior of the moving area. Besides, by combining the relationship between regional behavior and vehicle behavior, this paper completes vehicle behavior analysis. The overall flowchart of the algorithm is shown in Figure1.Figure 1
Flowchart of vehicle behavior analysis.The biggest advantage of applying the directionless two-part graph to vehicle behavior analysis is that the method does not require high accuracy for moving target extraction. Even if the extracted moving regions are not continuous, vehicle behavior analysis can be performed.


### 2.2. Vehicle Analysis Model Based on Directionless Two-Part Graph

The directionless two-part graph is expressed by the vertex adjacency matrix, the essential meaning and function of the two are the same, but the vertex adjacency matrix can better reflect the association relationship of each area and is more suitable for programming. The following paper will introduce the basic principles and implementation of vertex adjacency matrix construction. The flowchart of vertex adjacency matrix construction can be seen in Figure2.Figure 2
Flowchart of the construction of the vertex adjacency matrix.On the basis of extracting the moving vehicle area, the researcher can transform the behavior analysis of the vehicle into the behavior analysis of the area. The behavior analysis of the region is obtained by analyzing the vertex adjacency matrix constructed below.This paper extracts the moving area in each frame of the traffic surveillance video and replaces the original moving area with the smallest bounding rectangle of each area [2]. The change of the motion area between two adjacent frames of images can be defined as four behaviors: appearance, disappearance, merging, and decomposition, as shown in Figure 3. Figure 3(a) describes the three motion regions extracted in the frame as R1, R2, and R3; Figure 3(b) describes the three motion regions extracted in the first frame, denoted as R4, R5, and R6. From Figures 3(a) and 3(b), the relationship between the motion areas in two adjacent frames can be obtained intuitively, as shown in Figure 3(c). In Figure 3(a), part of R1 is decomposed into R5, and the other part is merged with R2 to form R4. R3 disappears because there is no associated motion area, and R6 is the newly appeared area in Figure 3(b).Figure 3
Four kinds of transformation in the region. (a) The area in framek−1. (b). The area in frame K (c). Correspondence between regions.
(a)(b)(c)The directionless two-part graph can describe the relationship between the motion areas in adjacent frames. Within the framek−1 and k in the image, this paper takes the upper left vertex of each motion area as the vertex sets U=U1,U2,…,Um and V=V1,V2,…,Vn, respectively. Each vertex represents a motion area; that is, the vertex set U=U1,U2,…,Um corresponds to the motion area set Ru=Ru1,Ru2,…,Rum in the frame k−1; the vertex set V=V1,V2,…,Vn corresponds to the motion area set Rv=Rv1,Rv2,…,Rvn in the frame k.Each edge represents the association relationshipi=1,2,…,m;j=1,2,…,n between the motion regions Rui and Rvj of adjacent frames, and E is the set of all edges in G. The vertex adjacency matrix An×m, which is equivalent to the directionless two-part graph GU,V,E, can clearly describe the edge set E. In vertex adjacency matrix An×m, row m correspond to m vertices in vertex set U=U1,U2,…,Um, that is, the m motion regions contained in the frame k−1; the n columns correspond to the n vertices in the vertex set V=V1,V2,…,Vn, that is, the n motion regions contained in the frame k. Then the meaning of the element aij of the vertex adjacency matrix can be expressed as follows:Ifaij=1, it means that there is an edge between the vertices Ui and Vj; that is, there is a correlation between the motion areas Rui and Rvj.Ifaij=0, it means that there is no edge between the vertices Ui and Vj; that is, there is no correlation between the motion regions Rui and Rvj.It can be seen from the above definition that whether or not there is a correlation between each motion area in the two images before and after determines the value of the vertex adjacency matrix elementaij. The literature gives a method to determine the relationship between motion areas; that is, it is determined by calculating the overlap area between the motion areas Rui and Rvj. The specific algorithm is shown in formula (1).(1)Sui,vj=minSui,Svj2.In formula (1), Sui represents the area of the motion area Rui in the frame k−1, Svj represents the area of the motion area Rvj in the frame k, Sui,vj represents the overlapping area of Rui and Rvj in the motion area, and the relationship between Sui,vj, Sui, and Svj is shown in Figure 4.Figure 4
Calculation of the regions’ relation.If equation (1) is satisfied between the movement areas Rui and Rvj, Rui and Rvj are considered to be related, aij=1.If equation (1) is not satisfied between the movement areas Rui and Rvj, then Rui and Rvj are considered unrelated, aij=0.After constructing the vertex adjacency matrix according to the above algorithm, the behavior of the moving area can be analyzed through the simplification of the vertex adjacency matrix, and then the behavior analysis of the vehicle can be completed according to the conversion relationship between the area behavior and the vehicle behavior.


### 2.3. Optimization Analysis of Vehicle Behavior Based on Directionless Two-Part Graph

#### 2.3.1. Improvement of Directionless Two-Part Graph

Theoretically, four behaviors such as merging, decomposing, appearing, and disappearing may occur in the motion area of adjacent frames. However, in a video stream with a sampling frequency of 25–30 frames/sec, the probability of simultaneous decomposition and merging of the same motion area is very small. This actual experience is reflected in the region relationship graph and vertex adjacency matrix and can be expressed as follows: the degree of the two vertices connected by each edge ofG (i.e., the number of edges derived from each vertex) is at most one greater than or equal to 2. The sum of the number of “1” in the row and column where element aij is located cannot be greater than or equal to 2. So, in this paper, the edge with the degree of both vertices greater than or equal to 2 is called the interference edge, which will cause errors in regional behavior analysis. Therefore, before the regional behavior analysis, these interference edges must be removed by simplification of the directionless two-part graph.In the actual surveillance video, there are noise interference and changes in the external environment. These factors will inevitably cause interference edges inG. And there may be multiple interference edges connected to a vertex, as for which one to delete, researchers need to follow the principle of simplification of the directionless two-part graph described below [3].The improved logic of directionless two-part graph can be expressed as follows. First, by scanning the vertex adjacency matrixAm×n, the researcher records all interference edges, assuming that there are interference edges in M vertices. Then, for a certain vertex aij that has N interference edges connected to it, the researcher deletes ll=1,2,…,N−1 interference edges in turn to obtain CN1CN2,…,CNN−1 different subgraphs. In order to find the subgraph that is most consistent with the actual situation and define the matching function C, see the following formula (2); the researcher takes the subgraph with the smallest function value as the result of the vertex aij; that is, deletes its interference edges according to the subgraph with the smallest function value and simultaneously updates the element values in the rows and columns of aij in the vertex adjacency matrix. In the same way, other vertices M−1 with interference edges also delete their interference edges and update the vertex adjacency matrix according to the same algorithm. When all M vertices are processed, the behavior of the motion area can be obtained according to the vertex adjacency matrix obtained by the simplification.(2)CG=∑u∈pkSui−AuimaxAui,Sui.As for the directionless two-part graph, first, all vertices can be divided into “father vertices” and “subvertices.” The “father vertices” include all vertices with degree greater than 1 and degree equal to 0 in framek−1 (the previous frame), and other vertices are “subvertices.” Assuming that the set of “father vertices” is Pk, Sui represents the area of the region Rui represented by the vertex Ui in the set Pk, and Aui represents the sum of the areas of the motion regions represented by all vertices connected to the vertex Ui. Calculate the CG value of each subpicture, and take the subpicture with the smallest function value to describe the behavior of the motion area of the two adjacent frames [4].Based on the above basic principles, the flowchart of the algorithm is shown in Figure5.Figure 5
Flowchart of the simplification of the directionless two-part graph.


#### 2.3.2. Vehicle Behavior Analysis

Because there is a corresponding relationship between the vehicle and the moving area, the behavior analysis of the vehicle can be transformed into the behavior analysis of the moving area. However, there is not a simple one-to-one relationship between sports areas and vehicles. One car can correspond to multiple sports areas, and the same area may be shared by multiple vehicles. Table1 summarizes the relationship between the features of the vertex adjacency matrix and the regional behavior and vehicle behavior.Table 1
Relation between the vertex adjacency matrix and the behaviors of region and vehicle.
Vertex adjacency matrix featuresRegional behaviorVehicle behavioraij=1, all aih≠1h≠jRui and Rvj one-to-one correspondenceDrive normallyaij=1, exists ahj≠1h≠iRui and Ruh merge into RvjObstructed entry (area in framek, both Rui and Ruh are single vehicles)aij=1, exists aih=1h>jDecomposeRui into Rvj and RvhSplit (areaRui in frame k is a single vehicle)Occlusion separation (occlusion exists in area Rui in the frame k)From the vertex adjacency matrix, the logic of regional behavior and vehicle behavior can be expressed as follows. In the image of framek−1, assuming that the corresponding relationship between the vehicle and the moving region Rui is known, the final vertex obtained by simplification in the adjacency matrix An×m, look for elements that meet the conditions in the first column of Table 1, then follow the rules in Table 1 to obtain the region behavior from frame k−1 to frame k, and then summarize the two-vehicle behavior between frames [5].


## 2.1. Principles of Vehicle Behavior Analysis

The directionless two-part graph is a very useful mathematical model, which has important applications in many scientific fields. The directionless two-part graph can be used to describe many problems, for example, “data allocation,” “work arrangement,” “time allocation,” and “personnel selection.” This paper combines the directionless two-part graph with the behavior analysis of the vehicle in the video and uses the vertex adjacency matrix representing the directionless two-part graph to determine the behavior of the moving area. Besides, by combining the relationship between regional behavior and vehicle behavior, this paper completes vehicle behavior analysis. The overall flowchart of the algorithm is shown in Figure1.Figure 1
Flowchart of vehicle behavior analysis.The biggest advantage of applying the directionless two-part graph to vehicle behavior analysis is that the method does not require high accuracy for moving target extraction. Even if the extracted moving regions are not continuous, vehicle behavior analysis can be performed.


## 2.2. Vehicle Analysis Model Based on Directionless Two-Part Graph

The directionless two-part graph is expressed by the vertex adjacency matrix, the essential meaning and function of the two are the same, but the vertex adjacency matrix can better reflect the association relationship of each area and is more suitable for programming. The following paper will introduce the basic principles and implementation of vertex adjacency matrix construction. The flowchart of vertex adjacency matrix construction can be seen in Figure2.Figure 2
Flowchart of the construction of the vertex adjacency matrix.On the basis of extracting the moving vehicle area, the researcher can transform the behavior analysis of the vehicle into the behavior analysis of the area. The behavior analysis of the region is obtained by analyzing the vertex adjacency matrix constructed below.This paper extracts the moving area in each frame of the traffic surveillance video and replaces the original moving area with the smallest bounding rectangle of each area [2]. The change of the motion area between two adjacent frames of images can be defined as four behaviors: appearance, disappearance, merging, and decomposition, as shown in Figure 3. Figure 3(a) describes the three motion regions extracted in the frame as R1, R2, and R3; Figure 3(b) describes the three motion regions extracted in the first frame, denoted as R4, R5, and R6. From Figures 3(a) and 3(b), the relationship between the motion areas in two adjacent frames can be obtained intuitively, as shown in Figure 3(c). In Figure 3(a), part of R1 is decomposed into R5, and the other part is merged with R2 to form R4. R3 disappears because there is no associated motion area, and R6 is the newly appeared area in Figure 3(b).Figure 3
Four kinds of transformation in the region. (a) The area in framek−1. (b). The area in frame K (c). Correspondence between regions.
(a)(b)(c)The directionless two-part graph can describe the relationship between the motion areas in adjacent frames. Within the framek−1 and k in the image, this paper takes the upper left vertex of each motion area as the vertex sets U=U1,U2,…,Um and V=V1,V2,…,Vn, respectively. Each vertex represents a motion area; that is, the vertex set U=U1,U2,…,Um corresponds to the motion area set Ru=Ru1,Ru2,…,Rum in the frame k−1; the vertex set V=V1,V2,…,Vn corresponds to the motion area set Rv=Rv1,Rv2,…,Rvn in the frame k.Each edge represents the association relationshipi=1,2,…,m;j=1,2,…,n between the motion regions Rui and Rvj of adjacent frames, and E is the set of all edges in G. The vertex adjacency matrix An×m, which is equivalent to the directionless two-part graph GU,V,E, can clearly describe the edge set E. In vertex adjacency matrix An×m, row m correspond to m vertices in vertex set U=U1,U2,…,Um, that is, the m motion regions contained in the frame k−1; the n columns correspond to the n vertices in the vertex set V=V1,V2,…,Vn, that is, the n motion regions contained in the frame k. Then the meaning of the element aij of the vertex adjacency matrix can be expressed as follows:Ifaij=1, it means that there is an edge between the vertices Ui and Vj; that is, there is a correlation between the motion areas Rui and Rvj.Ifaij=0, it means that there is no edge between the vertices Ui and Vj; that is, there is no correlation between the motion regions Rui and Rvj.It can be seen from the above definition that whether or not there is a correlation between each motion area in the two images before and after determines the value of the vertex adjacency matrix elementaij. The literature gives a method to determine the relationship between motion areas; that is, it is determined by calculating the overlap area between the motion areas Rui and Rvj. The specific algorithm is shown in formula (1).(1)Sui,vj=minSui,Svj2.In formula (1), Sui represents the area of the motion area Rui in the frame k−1, Svj represents the area of the motion area Rvj in the frame k, Sui,vj represents the overlapping area of Rui and Rvj in the motion area, and the relationship between Sui,vj, Sui, and Svj is shown in Figure 4.Figure 4
Calculation of the regions’ relation.If equation (1) is satisfied between the movement areas Rui and Rvj, Rui and Rvj are considered to be related, aij=1.If equation (1) is not satisfied between the movement areas Rui and Rvj, then Rui and Rvj are considered unrelated, aij=0.After constructing the vertex adjacency matrix according to the above algorithm, the behavior of the moving area can be analyzed through the simplification of the vertex adjacency matrix, and then the behavior analysis of the vehicle can be completed according to the conversion relationship between the area behavior and the vehicle behavior.


## 2.3. Optimization Analysis of Vehicle Behavior Based on Directionless Two-Part Graph

### 2.3.1. Improvement of Directionless Two-Part Graph

Theoretically, four behaviors such as merging, decomposing, appearing, and disappearing may occur in the motion area of adjacent frames. However, in a video stream with a sampling frequency of 25–30 frames/sec, the probability of simultaneous decomposition and merging of the same motion area is very small. This actual experience is reflected in the region relationship graph and vertex adjacency matrix and can be expressed as follows: the degree of the two vertices connected by each edge ofG (i.e., the number of edges derived from each vertex) is at most one greater than or equal to 2. The sum of the number of “1” in the row and column where element aij is located cannot be greater than or equal to 2. So, in this paper, the edge with the degree of both vertices greater than or equal to 2 is called the interference edge, which will cause errors in regional behavior analysis. Therefore, before the regional behavior analysis, these interference edges must be removed by simplification of the directionless two-part graph.In the actual surveillance video, there are noise interference and changes in the external environment. These factors will inevitably cause interference edges inG. And there may be multiple interference edges connected to a vertex, as for which one to delete, researchers need to follow the principle of simplification of the directionless two-part graph described below [3].The improved logic of directionless two-part graph can be expressed as follows. First, by scanning the vertex adjacency matrixAm×n, the researcher records all interference edges, assuming that there are interference edges in M vertices. Then, for a certain vertex aij that has N interference edges connected to it, the researcher deletes ll=1,2,…,N−1 interference edges in turn to obtain CN1CN2,…,CNN−1 different subgraphs. In order to find the subgraph that is most consistent with the actual situation and define the matching function C, see the following formula (2); the researcher takes the subgraph with the smallest function value as the result of the vertex aij; that is, deletes its interference edges according to the subgraph with the smallest function value and simultaneously updates the element values in the rows and columns of aij in the vertex adjacency matrix. In the same way, other vertices M−1 with interference edges also delete their interference edges and update the vertex adjacency matrix according to the same algorithm. When all M vertices are processed, the behavior of the motion area can be obtained according to the vertex adjacency matrix obtained by the simplification.(2)CG=∑u∈pkSui−AuimaxAui,Sui.As for the directionless two-part graph, first, all vertices can be divided into “father vertices” and “subvertices.” The “father vertices” include all vertices with degree greater than 1 and degree equal to 0 in framek−1 (the previous frame), and other vertices are “subvertices.” Assuming that the set of “father vertices” is Pk, Sui represents the area of the region Rui represented by the vertex Ui in the set Pk, and Aui represents the sum of the areas of the motion regions represented by all vertices connected to the vertex Ui. Calculate the CG value of each subpicture, and take the subpicture with the smallest function value to describe the behavior of the motion area of the two adjacent frames [4].Based on the above basic principles, the flowchart of the algorithm is shown in Figure5.Figure 5
Flowchart of the simplification of the directionless two-part graph.


### 2.3.2. Vehicle Behavior Analysis

Because there is a corresponding relationship between the vehicle and the moving area, the behavior analysis of the vehicle can be transformed into the behavior analysis of the moving area. However, there is not a simple one-to-one relationship between sports areas and vehicles. One car can correspond to multiple sports areas, and the same area may be shared by multiple vehicles. Table1 summarizes the relationship between the features of the vertex adjacency matrix and the regional behavior and vehicle behavior.Table 1
Relation between the vertex adjacency matrix and the behaviors of region and vehicle.
Vertex adjacency matrix featuresRegional behaviorVehicle behavioraij=1, all aih≠1h≠jRui and Rvj one-to-one correspondenceDrive normallyaij=1, exists ahj≠1h≠iRui and Ruh merge into RvjObstructed entry (area in framek, both Rui and Ruh are single vehicles)aij=1, exists aih=1h>jDecomposeRui into Rvj and RvhSplit (areaRui in frame k is a single vehicle)Occlusion separation (occlusion exists in area Rui in the frame k)From the vertex adjacency matrix, the logic of regional behavior and vehicle behavior can be expressed as follows. In the image of framek−1, assuming that the corresponding relationship between the vehicle and the moving region Rui is known, the final vertex obtained by simplification in the adjacency matrix An×m, look for elements that meet the conditions in the first column of Table 1, then follow the rules in Table 1 to obtain the region behavior from frame k−1 to frame k, and then summarize the two-vehicle behavior between frames [5].


## 2.3.1. Improvement of Directionless Two-Part Graph

Theoretically, four behaviors such as merging, decomposing, appearing, and disappearing may occur in the motion area of adjacent frames. However, in a video stream with a sampling frequency of 25–30 frames/sec, the probability of simultaneous decomposition and merging of the same motion area is very small. This actual experience is reflected in the region relationship graph and vertex adjacency matrix and can be expressed as follows: the degree of the two vertices connected by each edge ofG (i.e., the number of edges derived from each vertex) is at most one greater than or equal to 2. The sum of the number of “1” in the row and column where element aij is located cannot be greater than or equal to 2. So, in this paper, the edge with the degree of both vertices greater than or equal to 2 is called the interference edge, which will cause errors in regional behavior analysis. Therefore, before the regional behavior analysis, these interference edges must be removed by simplification of the directionless two-part graph.In the actual surveillance video, there are noise interference and changes in the external environment. These factors will inevitably cause interference edges inG. And there may be multiple interference edges connected to a vertex, as for which one to delete, researchers need to follow the principle of simplification of the directionless two-part graph described below [3].The improved logic of directionless two-part graph can be expressed as follows. First, by scanning the vertex adjacency matrixAm×n, the researcher records all interference edges, assuming that there are interference edges in M vertices. Then, for a certain vertex aij that has N interference edges connected to it, the researcher deletes ll=1,2,…,N−1 interference edges in turn to obtain CN1CN2,…,CNN−1 different subgraphs. In order to find the subgraph that is most consistent with the actual situation and define the matching function C, see the following formula (2); the researcher takes the subgraph with the smallest function value as the result of the vertex aij; that is, deletes its interference edges according to the subgraph with the smallest function value and simultaneously updates the element values in the rows and columns of aij in the vertex adjacency matrix. In the same way, other vertices M−1 with interference edges also delete their interference edges and update the vertex adjacency matrix according to the same algorithm. When all M vertices are processed, the behavior of the motion area can be obtained according to the vertex adjacency matrix obtained by the simplification.(2)CG=∑u∈pkSui−AuimaxAui,Sui.As for the directionless two-part graph, first, all vertices can be divided into “father vertices” and “subvertices.” The “father vertices” include all vertices with degree greater than 1 and degree equal to 0 in framek−1 (the previous frame), and other vertices are “subvertices.” Assuming that the set of “father vertices” is Pk, Sui represents the area of the region Rui represented by the vertex Ui in the set Pk, and Aui represents the sum of the areas of the motion regions represented by all vertices connected to the vertex Ui. Calculate the CG value of each subpicture, and take the subpicture with the smallest function value to describe the behavior of the motion area of the two adjacent frames [4].Based on the above basic principles, the flowchart of the algorithm is shown in Figure5.Figure 5
Flowchart of the simplification of the directionless two-part graph.


## 2.3.2. Vehicle Behavior Analysis

Because there is a corresponding relationship between the vehicle and the moving area, the behavior analysis of the vehicle can be transformed into the behavior analysis of the moving area. However, there is not a simple one-to-one relationship between sports areas and vehicles. One car can correspond to multiple sports areas, and the same area may be shared by multiple vehicles. Table1 summarizes the relationship between the features of the vertex adjacency matrix and the regional behavior and vehicle behavior.Table 1
Relation between the vertex adjacency matrix and the behaviors of region and vehicle.
Vertex adjacency matrix featuresRegional behaviorVehicle behavioraij=1, all aih≠1h≠jRui and Rvj one-to-one correspondenceDrive normallyaij=1, exists ahj≠1h≠iRui and Ruh merge into RvjObstructed entry (area in framek, both Rui and Ruh are single vehicles)aij=1, exists aih=1h>jDecomposeRui into Rvj and RvhSplit (areaRui in frame k is a single vehicle)Occlusion separation (occlusion exists in area Rui in the frame k)From the vertex adjacency matrix, the logic of regional behavior and vehicle behavior can be expressed as follows. In the image of framek−1, assuming that the corresponding relationship between the vehicle and the moving region Rui is known, the final vertex obtained by simplification in the adjacency matrix An×m, look for elements that meet the conditions in the first column of Table 1, then follow the rules in Table 1 to obtain the region behavior from frame k−1 to frame k, and then summarize the two-vehicle behavior between frames [5].


## 3. SPF-Based Vehicle Optimization Tracking

In the process of tracking a moving vehicle, because the vehicle is in constant motion, in addition to analyzing the behavior of the vehicle, it is also necessary to track it in real time. On the basis of understanding the relationship between the vertex adjacency matrix and the regional behavior and vehicle behavior, if the target is occluded during the movement of the vehicle, it is necessary to grasp some unique characteristics of the vehicle itself. Tracking these features will achieve better tracking results.


### 3.1. Moving Vehicle Tracking Based on SPF

#### 3.1.1. Principle of Particle Filter Algorithm

As far as SPF and IPPF are concerned, they mainly extract effective tracking schemes by improving the correlation distribution on the standard particle filter. MC-JPDAF is the particle filter technology applied to the standard JPDAF, so as to effectively overcome the dimensionality problem by dividing the state space [6].Based on Monte Carlo methods, the concept of standard particle filtering is proposed. It mainly uses particle sets to represent probability, which can be used in any form of state-space model. Its core idea is to express its distribution through random state particles drawn from the posterior probability, which is a kind of sequential importance sampling. To put it simply, the particle filter method refers to the process of approximating the probability density function by finding a set of random samples propagating in the state space and replacing the integral operation with the sample mean to obtain the state minimum variance distribution. The sample here refers to the particle. When the number of samples is N⟶∝, any probability density distribution can be approximated.The basic principle of Monte Carlo method is as follows.In a high-dimensional space, it is required to solve the following integral:(3)If=∫xfXpXdX.In the above formula,pX is a probability distribution, f⋅ is any integrable function of pX and satisfies f:X⟶Rnf, N independently distributed random sample functions pX are drawn from the probability distribution Xii=1N, and then the probability distribution function pX can be approximated by the sample functions of these independent distributions as(4)pNX=1N∑i=1NδX−Xi.Among them,δX−Xi is the Dirac-Delta function, so the integral formula to be solved can become the following summation problem:(5)INf=1N∑i=1NfXiN⟶∞⟶If=∫XfXpXdX.This transformation from integration to addition is the Monte Carlo method. It is not difficult to conclude from the theorem of large numbers thatINf is unbiased, and the Monte Carlo method converges to If.Definition.
σf2≜EpXf2X−I2f, so the variance of INf is σf2/N, and the following formula can be obtained from the central limit theorem:(6)NINf−If⟶N⟶∞NO,σf2.
If the probability distribution functionpX obeys the Gaussian distribution, the random sample pX can be obtained directly through the sampling of Xii=1N. However, in practical applications, in many cases pX does not satisfy the Gaussian distribution, so the Monte Carlo method can be used to solve this problem.
For discrete-time stochastic systems, in the known prior state distributionpX0, the solution of pX0:k|Z1:k can be obtained according to the Bayesian estimation method:(7)pX0:k|Z1:k=pZk|XkpXk|Xk−1pZk|Z1:k−1pX0:k−1|Z1:k−1.
The posterior distributionpX0:k|Z1:k can be solved by Monte Carlo method. In the case that the random process does not satisfy the Gaussian distribution, the mathematical expression of the posterior distribution is difficult to give intuitively, so it is difficult to directly obtain the posterior distribution. Defining qX0:k|X1:k is a conditional probability distribution that satisfies the non-Gaussian state, and it has a larger support set than the posterior distribution. Select N random samples from the recommended distribution to get a sample set X0:kii=1N, which can get the following formula:(8)qX0:k|Z1:k=1N∑i=0NδX0:k−X0:ki.
Similarly, the expression of the posterior distribution can be written as(9)pX0:k|Z1:k=pX0:k|Z1:kqX0:k|Z1:kqX0:k|Z1:k=∑i=1NwkiδX0:k−X0:ki.
Among them,wki=w˜ki/∑i=1Nw˜ki is the normalized sample, which meets(10)w˜ki∝pX0:ki|Z1:kqX0:ki|Z1:k.
From the above mathematical reasoning, it can be seen that, in the non-Gaussian case, the posterior probabilitypX0:ki|Z1:k can be approximated by a set of random samples X0:ki,Wkii=1N. These random samples are called particles. The method of obtaining the posterior probability distribution through particle sampling is called importance sampling method.
When calculating the Bayesian state estimation, the above proposal distribution can be converted into a recursive form, with the following formula:(11)qX0:k|Z1:k=qXk|X0:k−1,Z1:kqX0:k−1|Z1:k−1.
According to the Bayesian state estimation equation, the following formula can be obtained:(12)pX0:k|Z1:k∝pZk|XkpXk|Xk−1pX0:k−1|Z1:k−1.
Put these two expressions into equation (12), it is not difficult to get(13)w˜ki∝pZki|XkipXki|Xk−1ipX0:k−1i|Z1:k−1qXki|X0:k−1i,Z1:kqX0:k−1i|Z1:k−1=w˜kipZki|XkipXki|Xk−1iqXki|X0:k−1i,Z1:k.
Adding a normalization factor to formula (13) can normalize w˜ki, so that, for the recursive Bayesian filtering problem, w˜ki can be rewritten as(14)w˜ki∝w˜k−1ipZki|XkipXki|Xk−1iqXki|Xk−1i,Zk.
In this way, the posterior probabilitypXk|Z1:k can be approximately written as(15)pXk|Z1:k=∑i=1NwkiδXk−Xki.
At this time, if the proposed distribution function is a state prior distribution, it can be derived as(16)qXki|Xk−1i,Zk=pXki|Xk−1i.
Bring the above formula into (15) is(17)w˜ki∝w˜k−1ipZki|Xki.
The process described above is the process of particle filtering. The entire process of particle filtering can be described as follows:(1)
Initialization: atk=0, according to the prior distribution pX0, the initial particle set X0i,w0ii=1N is obtained, where w0i=1/N.(2)
Sampling: fork=1,2,…, sample from the state transition probability relationship pXki|Xk−1i to calculate a new particle set X˜kii=1N.(3)
Calculate the weight: calculate the weightw˜kiof the particle X˜ki according to w˜ki∝w˜k−1ipZki|Xki, and normalize the weight to obtain a new weight X˜kii=1N.(4)
Calculate the estimated state: according to the particle setpXk|Z1:k=∑i=1NwkiδXk−Xki obtained in (17), the estimated state posterior distribution can be calculated, and the state estimate is(18)X^k=EXk=∑i=1NwkiX˜ki.(5)
Resampling: according to the particle weightwki, N particles Xkii=1Nare retrieved from the particle set X˜ki,wkii=1N, and the new particle weight is 1/N, thereby establishing a new particle set Xki,1/Ni=1N.


#### 3.1.2. Particle Filter Sampling Method

In the process of particle filtering, the sampling method of particles will greatly affect the performance of the algorithm. Therefore, choosing a good sampling method is the key to the success of the overall algorithm. The Markov chain-Monte Carlo sampling (MCMC) method is to sample a specific sampleXi from the proposed distribution qX and obtain the state probability in the state space of X Markov chain of distribution pX so that high-dimensional distribution, invariant distribution, and Gibbs distribution are sampled through Markov chain samples, and the method of random simulation of sampled samples is Markov chain-Monte Carlo Sampling method. This sampling method is widely used in many aspects of random simulation evaluation [7]. The more important and outstanding sampling method is the Metropolis-Hastings (MH) algorithm, which was first proposed by Metropolis and later improved and improved by Hastings on its basis. It becomes the current MH algorithm. Its sampling method is(19)paX,X˜=min1,pX˜qX|X˜pXqX˜|X.X is the current system state, X˜ is the sample value obtained by sampling, pX is the invariant distribution of the Markov chain, qX˜|X is the recommended distribution, and paX,X˜ is the acceptance probability of the required Markov chain to transfer to X˜.The flow of the M-H algorithm is briefly described as follows:(1)
Initialization: give the initial stateX0 of the system.(2)
Sample extraction: according to the previous system statusXi−1, candidate samples are sampled from the recommended distribution.(3)
Acceptance probability: calculate the acceptance probabilitypaX,X˜ according to paX,X˜=min1,pX˜qX|X˜/pXqX˜|X.(4)
Calculating the state transition: generate a uniform random numberu on the distribution of 0,1, compare the acceptance probability with u, if it is greater than u, and complete the state transition, namely, Xi=X˜; otherwise, do not transfer, namely, Xi=Xi−1.


#### 3.1.3. Solution to the Problem of Particle Degradation

In the particle filter algorithm described above, after multiple recursive operations, it is likely that only a few particles have large weights, while the rest of the particles have small weights. There are many particles with these small weights, and they have very little impact on the overall particle filter. In the calculation process, they take up a lot of time and greatly increase unnecessary computing time. In extreme cases, there may be only a few particles with very large weights left, while the weights of a large number of other particles are close to 0. Scholars call this phenomenon the degradation of particles [8].The phenomenon of particle degradation is due to the narrow support set of the particle's proposed distributionqXk|X0,k−1,Z1:k and the particle’s posterior distribution qXk|Z1:k, and there is only a small amount of overlap. In the sampling calculation, only a small number of particles are concentrated in the support. In this way, after Bayesian estimation, the weight of these particles becomes very small. After many times of this process, the weight of the particles gets smaller and smaller and finally approaches 0. Since its calculations have not changed, it still takes a lot of time. In order to solve the problem of particle degradation, Liu et al. proposed the concept of effective particle number and defined a relation:(20)Ts≈∑i=1kwkρk.Since the above formula is more complicated to calculate, the following simple formula is often used instead of the above formula:(21)N^eff=1∑i=1Nwki2.The degradation phenomenon of particles makes the weight of only a few particles larger, and the accuracy of using a few particles to express the probability distribution is low. Therefore, the degradation phenomenon of particles greatly compromises the reliability of particle filtering. How to avoid particle degradation or how to improve particle degradation had become the focus of research by many scholars. The more effective and efficient algorithm is the resampling method. This method is to add the resampling calculation after calculating the particle weight and resample the particles according to the particle weight. Particles with small weights are deleted to avoid taking up a lot of calculation time, and particles with large weights remain. At the same time, in order to ensure the number of particles, the particles with large weights are divided, and multiple sampling algorithms are used. The sampling variance isVarNi=Nwki1−wki. In order to improve the effectiveness of sampling, the sampling variance must be reduced. At this time, system sampling can be used. It is a sampling method with a very small sampling variance.The process diagram of particle resampling is shown in Figure6 as follows.Figure 6
Schematic diagram of particle resampling.Figure6 clearly illustrates the whole process from particle generation to weight change and resampling, that is, the overall implementation process from the posterior probability pxk−1|z1:k−1 at time k−1 to the posterior probability density pxk|z1:k at time k. The black solid dots represent the particles in the particle filter, and its size reflects the relationship between the particle weights. The particle weight represented by the large black dot is greater than the particle weight represented by the small black dot. The researcher initially assumed that there are ten particles, and the weights of these ten particles are all equal to 1/N. The curve in the figure above represents the distribution state of all particles. The particles passing through the peak have a greater weight than those passing through the trough.(1)
After ten particles with equal weights have passed the first curve, the weights of the ten particles have changed correspondingly due to the different positions of the crests and troughs of the passing curves. The weight of the particle passing through the wave crest is larger, and the weight of the particle passing through the trough is relatively smaller. The schematic diagram of the particle weight atk−1 shown in the figure above is obtained.(2)
After step 1, the weights of ten particles have changed. At this time, the resampling algorithm is used to keep the particles with larger weights. Particles with small weights are discarded and no longer participate in calculations, reducing the amount of subsequent calculations and leaving the number of effective particles.(3)
After step 2, the particles with larger weights are retained, and they are repeatedly sampled to ensure that the number of particles does not decrease after sampling, and it is still ten particles. And the weights of ten particles are the same as the initial ones, and the prior probability density of particlek is obtained.(4)
The number of resampled particles and the weight of each particle are exactly the same as the momentk−1. At this time, ten particles are observed to obtain the posterior probability density of the particles, and the entire process of particle resampling is completed.Through the above calculation, the influence of small weight particles on the filtering algorithm is well eliminated. On the premise of ensuring the diversity of particles, the researchers remove particles with smaller weights, which greatly improves the utilization of calculations and the accuracy of filtering.The aforementioned algorithm to avoid particle degradation can be briefly described as follows:(1)
Weight calculation: for the sampled particle setX˜ki,wkii=1N, set the initial weight c1=wk1, and use this to calculate the cumulative weight ci=ci−1+wki.(2)
Calculating the random number: calculate the uniformly distributed random number on0,N−1, namely, u−U0,N−1.(3)
Resampling: for the range ofj=1:N, u1=u+N−1j−1, if u1>c, then calculate the next weight; otherwise Xkj=X˜ki and wkj=N−1.The flowchart of particle filtering is shown in Figure7.Figure 7
Particle filter target tracking flowchart.


### 3.2. Vehicle Tracking Algorithm Based on Improved SPF

#### 3.2.1. Segmentation of Moving Vehicles

Particle filter algorithm (SPF) is based on segmentation compensation [9]. In the process of tracking the target vehicle, this algorithm divides the target into multiple regions and selects the local features of the target from these regions. If the tracked target is partially occluded or morphologically changed during the tracking process, other areas of the target can be used instead of tracking, which can make the particle filter more accurate and applicable. After the target is located, the target to be tracked needs to be segmented, and the tracking frame is equally divided into the following nine regions as shown in Figure 8.Figure 8
Schematic diagram of target segmentation.Similarly, segmentation methods such as2×2 or 4×4 can also be selected, but 2×2 segmentation has less effect on the segmentation of the target frame and loses the meaning of tracking frame segmentation. When the video resolution is not high, dense segmentation such as 4×4 or even 5×5 makes the resolution of the segmented area too small and fewer features are extracted from it, which is not conducive to the continuous tracking. The segmentation of the 3×3 region selected in this paper is more practical and has no emphasis on the global average distribution. It can be applied to most target tracking situations, and the region with the best local features can be selected from these nine segments for vehicle track.After the segmentation area is obtained, it is necessary to select a suitable segmentation area for tracking during the tracking process. For the 1-9 segmented regions defined in the above figure, the researcher defines the concept of segmentation adjacent. The adjacent bits of segment 1 are segment 2 and segment 4, and the adjacent bits of segment 5 are segment 2, segment 4, segment 6, and segment 8, and so on. After obtaining the relationship of adjacent bits, the selection rule for segmentation is defined as follows: the feature histogram of the segmented block and the feature histogram of adjacent bits are better if the Bhattacharyya coefficient is smaller. The Bhattacharyya coefficient is the similarity coefficient, which is defined as(22)ρp^y^0,q^=∑u=1mp^uy^0,q^u.The value range of its value is between 0 and 1, and the value ofρ reflects the similarity of the calculated two models. The larger the ρ value is, the higher the similarity of the two models. For the segmented region, the larger the ρ value of the adjacent bits, the higher the similarity between the two adjacent bits. In other words, the correlation is large and can be replaced by adjacent bits. Therefore, we take the segmentation area with a small ρ value, that is, the segmentation area with low similarity to the neighboring bits, and discard the segmentation area with a large ρ value.After obtaining the segmentation area with small correlation, find the mean value of the Bhattacharyya coefficients of all the adjacent positions of the segmentation area; that is,(23)ρmean=∑ikρik.For example, for segment 5, it is to find the Bhattacharyya coefficients of segment 2, segment 4, segment 6, and segment 8 and then add the sum and average.After calculating theρ values of all 9 segments, select the smaller segmentation area, and perform target tracking on the selected area.


#### 3.2.2. Motion Compensation for Segmented Areas

Figure9 is the particle distribution map formed by the segmented area at a certain time t during the vehicle tracking process. It can be clearly seen that the particles are distributed around the center of the segmented area.Figure 9
Particle distribution diagram at timet.The following figure shows the position A where the segmented area A moves att+1 during the target tracking process. The particle distribution shown in the figure is still the particle distribution at time t.Figure10 shows the position where the segmented area A moves at t+2 during the target tracking process. The particle distribution shown in the figure is the particle distribution at t+2.Figure 10
Particle distribution diagram at timet+1The situation in Figure10 is exactly the same as that in Figure 11. Due to the faster movement of the segmented area, there are fewer particles at the location of the segmented area at t+1, and the target is located at the position of the small red dot in Figure 11. At this time, if the researcher adds an offset to these particles to make the position of the particles shift to the direction of the target movement, the particles at t+1 can be shown in Figure 10, and the particle distribution at t+1 can be obtained. It is not the distribution centered on the position of the small red dot, but there is some deviation in the direction of the target movement, which is closer to the true position of the target in Figure 11. In this way, the segmented area tracked at t+2 after offset compensation is shown in (D).Figure 11
Particle distribution diagram at timet+2.Comparing the tracking frames in Figures11 and 12, we can see that the target position is closer to the real one. The problem of tracking failure in Figure 10 does not occur.Figure 12
Particle distribution diagram at timet+2.The particle center is represented by the following formula:(24)Pp=Pp+θTs.Pp represents the current position of the particle, Ts represents the movement displacement of the vehicle in the previous frame, and θ represents the weighted value. The value of θ is generally between 0.3 and 0.7 according to the movement form of the tracking target. In this paper, the median value is 0.5. In the application process, the particles scattered in the segmented area are added with an offset to improve the problem of large target positioning deviation caused by rapid target movement.


#### 3.2.3. Optimized Vehicle Tracking Based on SPF Algorithm

Assume that the segmentation area with a smallerρ value obtained in the previous section is segment 1, segment 5, and segment 9 and the center of the tracking frame is the black spot position, as shown in Figure 13.Figure 13
Schematic diagram of selecting partition area.Then, this paper uses the target tracking results of these three segmented regions to locate the overall target motion and obtains segment 1, segment 5, and segment 9 target tracking results as shown in Figure14.Figure 14
Schematic diagram of tracking results of segmented regions.The final motion position of the target is the vector sum of segment 1, segment 5, and segment 9, which can be expressed by the following formula:(25)Ts≈∑i=1kwkρk.Ts represents the motion displacement of the overall target, ρk represents the motion displacement of the segmentation, and wk is the weight of each segmentation. If there is no special target tracking situation, wk can be set to the same value and the researcher only normalize the motion of all segmented regions. The final target tracking and positioning result is shown in Figure 15.Figure 15
Schematic diagram of target tracking results.The advantage of such segmentation tracking is that, firstly, the segmented areas with greater correlation are eliminated, and they can be replaced with segmented areas related to them, which reduces the amount of calculation accordingly. On the other hand, each small segmented area is equivalent to the target tracking of a small object, and the particle filter method is used to track it to ensure the accuracy of its tracking. In this way, the positive and negative errors of the target tracking result of the entire tracking frame obtained from the vector sum of the vehicle tracking results in a plurality of small segmented regions are offset, the tracking error is reduced, and the tracking accuracy is improved.


## 3.1. Moving Vehicle Tracking Based on SPF

### 3.1.1. Principle of Particle Filter Algorithm

As far as SPF and IPPF are concerned, they mainly extract effective tracking schemes by improving the correlation distribution on the standard particle filter. MC-JPDAF is the particle filter technology applied to the standard JPDAF, so as to effectively overcome the dimensionality problem by dividing the state space [6].Based on Monte Carlo methods, the concept of standard particle filtering is proposed. It mainly uses particle sets to represent probability, which can be used in any form of state-space model. Its core idea is to express its distribution through random state particles drawn from the posterior probability, which is a kind of sequential importance sampling. To put it simply, the particle filter method refers to the process of approximating the probability density function by finding a set of random samples propagating in the state space and replacing the integral operation with the sample mean to obtain the state minimum variance distribution. The sample here refers to the particle. When the number of samples is N⟶∝, any probability density distribution can be approximated.The basic principle of Monte Carlo method is as follows.In a high-dimensional space, it is required to solve the following integral:(3)If=∫xfXpXdX.In the above formula,pX is a probability distribution, f⋅ is any integrable function of pX and satisfies f:X⟶Rnf, N independently distributed random sample functions pX are drawn from the probability distribution Xii=1N, and then the probability distribution function pX can be approximated by the sample functions of these independent distributions as(4)pNX=1N∑i=1NδX−Xi.Among them,δX−Xi is the Dirac-Delta function, so the integral formula to be solved can become the following summation problem:(5)INf=1N∑i=1NfXiN⟶∞⟶If=∫XfXpXdX.This transformation from integration to addition is the Monte Carlo method. It is not difficult to conclude from the theorem of large numbers thatINf is unbiased, and the Monte Carlo method converges to If.Definition.
σf2≜EpXf2X−I2f, so the variance of INf is σf2/N, and the following formula can be obtained from the central limit theorem:(6)NINf−If⟶N⟶∞NO,σf2.
If the probability distribution functionpX obeys the Gaussian distribution, the random sample pX can be obtained directly through the sampling of Xii=1N. However, in practical applications, in many cases pX does not satisfy the Gaussian distribution, so the Monte Carlo method can be used to solve this problem.
For discrete-time stochastic systems, in the known prior state distributionpX0, the solution of pX0:k|Z1:k can be obtained according to the Bayesian estimation method:(7)pX0:k|Z1:k=pZk|XkpXk|Xk−1pZk|Z1:k−1pX0:k−1|Z1:k−1.
The posterior distributionpX0:k|Z1:k can be solved by Monte Carlo method. In the case that the random process does not satisfy the Gaussian distribution, the mathematical expression of the posterior distribution is difficult to give intuitively, so it is difficult to directly obtain the posterior distribution. Defining qX0:k|X1:k is a conditional probability distribution that satisfies the non-Gaussian state, and it has a larger support set than the posterior distribution. Select N random samples from the recommended distribution to get a sample set X0:kii=1N, which can get the following formula:(8)qX0:k|Z1:k=1N∑i=0NδX0:k−X0:ki.
Similarly, the expression of the posterior distribution can be written as(9)pX0:k|Z1:k=pX0:k|Z1:kqX0:k|Z1:kqX0:k|Z1:k=∑i=1NwkiδX0:k−X0:ki.
Among them,wki=w˜ki/∑i=1Nw˜ki is the normalized sample, which meets(10)w˜ki∝pX0:ki|Z1:kqX0:ki|Z1:k.
From the above mathematical reasoning, it can be seen that, in the non-Gaussian case, the posterior probabilitypX0:ki|Z1:k can be approximated by a set of random samples X0:ki,Wkii=1N. These random samples are called particles. The method of obtaining the posterior probability distribution through particle sampling is called importance sampling method.
When calculating the Bayesian state estimation, the above proposal distribution can be converted into a recursive form, with the following formula:(11)qX0:k|Z1:k=qXk|X0:k−1,Z1:kqX0:k−1|Z1:k−1.
According to the Bayesian state estimation equation, the following formula can be obtained:(12)pX0:k|Z1:k∝pZk|XkpXk|Xk−1pX0:k−1|Z1:k−1.
Put these two expressions into equation (12), it is not difficult to get(13)w˜ki∝pZki|XkipXki|Xk−1ipX0:k−1i|Z1:k−1qXki|X0:k−1i,Z1:kqX0:k−1i|Z1:k−1=w˜kipZki|XkipXki|Xk−1iqXki|X0:k−1i,Z1:k.
Adding a normalization factor to formula (13) can normalize w˜ki, so that, for the recursive Bayesian filtering problem, w˜ki can be rewritten as(14)w˜ki∝w˜k−1ipZki|XkipXki|Xk−1iqXki|Xk−1i,Zk.
In this way, the posterior probabilitypXk|Z1:k can be approximately written as(15)pXk|Z1:k=∑i=1NwkiδXk−Xki.
At this time, if the proposed distribution function is a state prior distribution, it can be derived as(16)qXki|Xk−1i,Zk=pXki|Xk−1i.
Bring the above formula into (15) is(17)w˜ki∝w˜k−1ipZki|Xki.
The process described above is the process of particle filtering. The entire process of particle filtering can be described as follows:(1)
Initialization: atk=0, according to the prior distribution pX0, the initial particle set X0i,w0ii=1N is obtained, where w0i=1/N.(2)
Sampling: fork=1,2,…, sample from the state transition probability relationship pXki|Xk−1i to calculate a new particle set X˜kii=1N.(3)
Calculate the weight: calculate the weightw˜kiof the particle X˜ki according to w˜ki∝w˜k−1ipZki|Xki, and normalize the weight to obtain a new weight X˜kii=1N.(4)
Calculate the estimated state: according to the particle setpXk|Z1:k=∑i=1NwkiδXk−Xki obtained in (17), the estimated state posterior distribution can be calculated, and the state estimate is(18)X^k=EXk=∑i=1NwkiX˜ki.(5)
Resampling: according to the particle weightwki, N particles Xkii=1Nare retrieved from the particle set X˜ki,wkii=1N, and the new particle weight is 1/N, thereby establishing a new particle set Xki,1/Ni=1N.


### 3.1.2. Particle Filter Sampling Method

In the process of particle filtering, the sampling method of particles will greatly affect the performance of the algorithm. Therefore, choosing a good sampling method is the key to the success of the overall algorithm. The Markov chain-Monte Carlo sampling (MCMC) method is to sample a specific sampleXi from the proposed distribution qX and obtain the state probability in the state space of X Markov chain of distribution pX so that high-dimensional distribution, invariant distribution, and Gibbs distribution are sampled through Markov chain samples, and the method of random simulation of sampled samples is Markov chain-Monte Carlo Sampling method. This sampling method is widely used in many aspects of random simulation evaluation [7]. The more important and outstanding sampling method is the Metropolis-Hastings (MH) algorithm, which was first proposed by Metropolis and later improved and improved by Hastings on its basis. It becomes the current MH algorithm. Its sampling method is(19)paX,X˜=min1,pX˜qX|X˜pXqX˜|X.X is the current system state, X˜ is the sample value obtained by sampling, pX is the invariant distribution of the Markov chain, qX˜|X is the recommended distribution, and paX,X˜ is the acceptance probability of the required Markov chain to transfer to X˜.The flow of the M-H algorithm is briefly described as follows:(1)
Initialization: give the initial stateX0 of the system.(2)
Sample extraction: according to the previous system statusXi−1, candidate samples are sampled from the recommended distribution.(3)
Acceptance probability: calculate the acceptance probabilitypaX,X˜ according to paX,X˜=min1,pX˜qX|X˜/pXqX˜|X.(4)
Calculating the state transition: generate a uniform random numberu on the distribution of 0,1, compare the acceptance probability with u, if it is greater than u, and complete the state transition, namely, Xi=X˜; otherwise, do not transfer, namely, Xi=Xi−1.


### 3.1.3. Solution to the Problem of Particle Degradation

In the particle filter algorithm described above, after multiple recursive operations, it is likely that only a few particles have large weights, while the rest of the particles have small weights. There are many particles with these small weights, and they have very little impact on the overall particle filter. In the calculation process, they take up a lot of time and greatly increase unnecessary computing time. In extreme cases, there may be only a few particles with very large weights left, while the weights of a large number of other particles are close to 0. Scholars call this phenomenon the degradation of particles [8].The phenomenon of particle degradation is due to the narrow support set of the particle's proposed distributionqXk|X0,k−1,Z1:k and the particle’s posterior distribution qXk|Z1:k, and there is only a small amount of overlap. In the sampling calculation, only a small number of particles are concentrated in the support. In this way, after Bayesian estimation, the weight of these particles becomes very small. After many times of this process, the weight of the particles gets smaller and smaller and finally approaches 0. Since its calculations have not changed, it still takes a lot of time. In order to solve the problem of particle degradation, Liu et al. proposed the concept of effective particle number and defined a relation:(20)Ts≈∑i=1kwkρk.Since the above formula is more complicated to calculate, the following simple formula is often used instead of the above formula:(21)N^eff=1∑i=1Nwki2.The degradation phenomenon of particles makes the weight of only a few particles larger, and the accuracy of using a few particles to express the probability distribution is low. Therefore, the degradation phenomenon of particles greatly compromises the reliability of particle filtering. How to avoid particle degradation or how to improve particle degradation had become the focus of research by many scholars. The more effective and efficient algorithm is the resampling method. This method is to add the resampling calculation after calculating the particle weight and resample the particles according to the particle weight. Particles with small weights are deleted to avoid taking up a lot of calculation time, and particles with large weights remain. At the same time, in order to ensure the number of particles, the particles with large weights are divided, and multiple sampling algorithms are used. The sampling variance isVarNi=Nwki1−wki. In order to improve the effectiveness of sampling, the sampling variance must be reduced. At this time, system sampling can be used. It is a sampling method with a very small sampling variance.The process diagram of particle resampling is shown in Figure6 as follows.Figure 6
Schematic diagram of particle resampling.Figure6 clearly illustrates the whole process from particle generation to weight change and resampling, that is, the overall implementation process from the posterior probability pxk−1|z1:k−1 at time k−1 to the posterior probability density pxk|z1:k at time k. The black solid dots represent the particles in the particle filter, and its size reflects the relationship between the particle weights. The particle weight represented by the large black dot is greater than the particle weight represented by the small black dot. The researcher initially assumed that there are ten particles, and the weights of these ten particles are all equal to 1/N. The curve in the figure above represents the distribution state of all particles. The particles passing through the peak have a greater weight than those passing through the trough.(1)
After ten particles with equal weights have passed the first curve, the weights of the ten particles have changed correspondingly due to the different positions of the crests and troughs of the passing curves. The weight of the particle passing through the wave crest is larger, and the weight of the particle passing through the trough is relatively smaller. The schematic diagram of the particle weight atk−1 shown in the figure above is obtained.(2)
After step 1, the weights of ten particles have changed. At this time, the resampling algorithm is used to keep the particles with larger weights. Particles with small weights are discarded and no longer participate in calculations, reducing the amount of subsequent calculations and leaving the number of effective particles.(3)
After step 2, the particles with larger weights are retained, and they are repeatedly sampled to ensure that the number of particles does not decrease after sampling, and it is still ten particles. And the weights of ten particles are the same as the initial ones, and the prior probability density of particlek is obtained.(4)
The number of resampled particles and the weight of each particle are exactly the same as the momentk−1. At this time, ten particles are observed to obtain the posterior probability density of the particles, and the entire process of particle resampling is completed.Through the above calculation, the influence of small weight particles on the filtering algorithm is well eliminated. On the premise of ensuring the diversity of particles, the researchers remove particles with smaller weights, which greatly improves the utilization of calculations and the accuracy of filtering.The aforementioned algorithm to avoid particle degradation can be briefly described as follows:(1)
Weight calculation: for the sampled particle setX˜ki,wkii=1N, set the initial weight c1=wk1, and use this to calculate the cumulative weight ci=ci−1+wki.(2)
Calculating the random number: calculate the uniformly distributed random number on0,N−1, namely, u−U0,N−1.(3)
Resampling: for the range ofj=1:N, u1=u+N−1j−1, if u1>c, then calculate the next weight; otherwise Xkj=X˜ki and wkj=N−1.The flowchart of particle filtering is shown in Figure7.Figure 7
Particle filter target tracking flowchart.


## 3.1.1. Principle of Particle Filter Algorithm

As far as SPF and IPPF are concerned, they mainly extract effective tracking schemes by improving the correlation distribution on the standard particle filter. MC-JPDAF is the particle filter technology applied to the standard JPDAF, so as to effectively overcome the dimensionality problem by dividing the state space [6].Based on Monte Carlo methods, the concept of standard particle filtering is proposed. It mainly uses particle sets to represent probability, which can be used in any form of state-space model. Its core idea is to express its distribution through random state particles drawn from the posterior probability, which is a kind of sequential importance sampling. To put it simply, the particle filter method refers to the process of approximating the probability density function by finding a set of random samples propagating in the state space and replacing the integral operation with the sample mean to obtain the state minimum variance distribution. The sample here refers to the particle. When the number of samples is N⟶∝, any probability density distribution can be approximated.The basic principle of Monte Carlo method is as follows.In a high-dimensional space, it is required to solve the following integral:(3)If=∫xfXpXdX.In the above formula,pX is a probability distribution, f⋅ is any integrable function of pX and satisfies f:X⟶Rnf, N independently distributed random sample functions pX are drawn from the probability distribution Xii=1N, and then the probability distribution function pX can be approximated by the sample functions of these independent distributions as(4)pNX=1N∑i=1NδX−Xi.Among them,δX−Xi is the Dirac-Delta function, so the integral formula to be solved can become the following summation problem:(5)INf=1N∑i=1NfXiN⟶∞⟶If=∫XfXpXdX.This transformation from integration to addition is the Monte Carlo method. It is not difficult to conclude from the theorem of large numbers thatINf is unbiased, and the Monte Carlo method converges to If.Definition.
σf2≜EpXf2X−I2f, so the variance of INf is σf2/N, and the following formula can be obtained from the central limit theorem:(6)NINf−If⟶N⟶∞NO,σf2.
If the probability distribution functionpX obeys the Gaussian distribution, the random sample pX can be obtained directly through the sampling of Xii=1N. However, in practical applications, in many cases pX does not satisfy the Gaussian distribution, so the Monte Carlo method can be used to solve this problem.
For discrete-time stochastic systems, in the known prior state distributionpX0, the solution of pX0:k|Z1:k can be obtained according to the Bayesian estimation method:(7)pX0:k|Z1:k=pZk|XkpXk|Xk−1pZk|Z1:k−1pX0:k−1|Z1:k−1.
The posterior distributionpX0:k|Z1:k can be solved by Monte Carlo method. In the case that the random process does not satisfy the Gaussian distribution, the mathematical expression of the posterior distribution is difficult to give intuitively, so it is difficult to directly obtain the posterior distribution. Defining qX0:k|X1:k is a conditional probability distribution that satisfies the non-Gaussian state, and it has a larger support set than the posterior distribution. Select N random samples from the recommended distribution to get a sample set X0:kii=1N, which can get the following formula:(8)qX0:k|Z1:k=1N∑i=0NδX0:k−X0:ki.
Similarly, the expression of the posterior distribution can be written as(9)pX0:k|Z1:k=pX0:k|Z1:kqX0:k|Z1:kqX0:k|Z1:k=∑i=1NwkiδX0:k−X0:ki.
Among them,wki=w˜ki/∑i=1Nw˜ki is the normalized sample, which meets(10)w˜ki∝pX0:ki|Z1:kqX0:ki|Z1:k.
From the above mathematical reasoning, it can be seen that, in the non-Gaussian case, the posterior probabilitypX0:ki|Z1:k can be approximated by a set of random samples X0:ki,Wkii=1N. These random samples are called particles. The method of obtaining the posterior probability distribution through particle sampling is called importance sampling method.
When calculating the Bayesian state estimation, the above proposal distribution can be converted into a recursive form, with the following formula:(11)qX0:k|Z1:k=qXk|X0:k−1,Z1:kqX0:k−1|Z1:k−1.
According to the Bayesian state estimation equation, the following formula can be obtained:(12)pX0:k|Z1:k∝pZk|XkpXk|Xk−1pX0:k−1|Z1:k−1.
Put these two expressions into equation (12), it is not difficult to get(13)w˜ki∝pZki|XkipXki|Xk−1ipX0:k−1i|Z1:k−1qXki|X0:k−1i,Z1:kqX0:k−1i|Z1:k−1=w˜kipZki|XkipXki|Xk−1iqXki|X0:k−1i,Z1:k.
Adding a normalization factor to formula (13) can normalize w˜ki, so that, for the recursive Bayesian filtering problem, w˜ki can be rewritten as(14)w˜ki∝w˜k−1ipZki|XkipXki|Xk−1iqXki|Xk−1i,Zk.
In this way, the posterior probabilitypXk|Z1:k can be approximately written as(15)pXk|Z1:k=∑i=1NwkiδXk−Xki.
At this time, if the proposed distribution function is a state prior distribution, it can be derived as(16)qXki|Xk−1i,Zk=pXki|Xk−1i.
Bring the above formula into (15) is(17)w˜ki∝w˜k−1ipZki|Xki.
The process described above is the process of particle filtering. The entire process of particle filtering can be described as follows:(1)
Initialization: atk=0, according to the prior distribution pX0, the initial particle set X0i,w0ii=1N is obtained, where w0i=1/N.(2)
Sampling: fork=1,2,…, sample from the state transition probability relationship pXki|Xk−1i to calculate a new particle set X˜kii=1N.(3)
Calculate the weight: calculate the weightw˜kiof the particle X˜ki according to w˜ki∝w˜k−1ipZki|Xki, and normalize the weight to obtain a new weight X˜kii=1N.(4)
Calculate the estimated state: according to the particle setpXk|Z1:k=∑i=1NwkiδXk−Xki obtained in (17), the estimated state posterior distribution can be calculated, and the state estimate is(18)X^k=EXk=∑i=1NwkiX˜ki.(5)
Resampling: according to the particle weightwki, N particles Xkii=1Nare retrieved from the particle set X˜ki,wkii=1N, and the new particle weight is 1/N, thereby establishing a new particle set Xki,1/Ni=1N.


## 3.1.2. Particle Filter Sampling Method

In the process of particle filtering, the sampling method of particles will greatly affect the performance of the algorithm. Therefore, choosing a good sampling method is the key to the success of the overall algorithm. The Markov chain-Monte Carlo sampling (MCMC) method is to sample a specific sampleXi from the proposed distribution qX and obtain the state probability in the state space of X Markov chain of distribution pX so that high-dimensional distribution, invariant distribution, and Gibbs distribution are sampled through Markov chain samples, and the method of random simulation of sampled samples is Markov chain-Monte Carlo Sampling method. This sampling method is widely used in many aspects of random simulation evaluation [7]. The more important and outstanding sampling method is the Metropolis-Hastings (MH) algorithm, which was first proposed by Metropolis and later improved and improved by Hastings on its basis. It becomes the current MH algorithm. Its sampling method is(19)paX,X˜=min1,pX˜qX|X˜pXqX˜|X.X is the current system state, X˜ is the sample value obtained by sampling, pX is the invariant distribution of the Markov chain, qX˜|X is the recommended distribution, and paX,X˜ is the acceptance probability of the required Markov chain to transfer to X˜.The flow of the M-H algorithm is briefly described as follows:(1)
Initialization: give the initial stateX0 of the system.(2)
Sample extraction: according to the previous system statusXi−1, candidate samples are sampled from the recommended distribution.(3)
Acceptance probability: calculate the acceptance probabilitypaX,X˜ according to paX,X˜=min1,pX˜qX|X˜/pXqX˜|X.(4)
Calculating the state transition: generate a uniform random numberu on the distribution of 0,1, compare the acceptance probability with u, if it is greater than u, and complete the state transition, namely, Xi=X˜; otherwise, do not transfer, namely, Xi=Xi−1.


## 3.1.3. Solution to the Problem of Particle Degradation

In the particle filter algorithm described above, after multiple recursive operations, it is likely that only a few particles have large weights, while the rest of the particles have small weights. There are many particles with these small weights, and they have very little impact on the overall particle filter. In the calculation process, they take up a lot of time and greatly increase unnecessary computing time. In extreme cases, there may be only a few particles with very large weights left, while the weights of a large number of other particles are close to 0. Scholars call this phenomenon the degradation of particles [8].The phenomenon of particle degradation is due to the narrow support set of the particle's proposed distributionqXk|X0,k−1,Z1:k and the particle’s posterior distribution qXk|Z1:k, and there is only a small amount of overlap. In the sampling calculation, only a small number of particles are concentrated in the support. In this way, after Bayesian estimation, the weight of these particles becomes very small. After many times of this process, the weight of the particles gets smaller and smaller and finally approaches 0. Since its calculations have not changed, it still takes a lot of time. In order to solve the problem of particle degradation, Liu et al. proposed the concept of effective particle number and defined a relation:(20)Ts≈∑i=1kwkρk.Since the above formula is more complicated to calculate, the following simple formula is often used instead of the above formula:(21)N^eff=1∑i=1Nwki2.The degradation phenomenon of particles makes the weight of only a few particles larger, and the accuracy of using a few particles to express the probability distribution is low. Therefore, the degradation phenomenon of particles greatly compromises the reliability of particle filtering. How to avoid particle degradation or how to improve particle degradation had become the focus of research by many scholars. The more effective and efficient algorithm is the resampling method. This method is to add the resampling calculation after calculating the particle weight and resample the particles according to the particle weight. Particles with small weights are deleted to avoid taking up a lot of calculation time, and particles with large weights remain. At the same time, in order to ensure the number of particles, the particles with large weights are divided, and multiple sampling algorithms are used. The sampling variance isVarNi=Nwki1−wki. In order to improve the effectiveness of sampling, the sampling variance must be reduced. At this time, system sampling can be used. It is a sampling method with a very small sampling variance.The process diagram of particle resampling is shown in Figure6 as follows.Figure 6
Schematic diagram of particle resampling.Figure6 clearly illustrates the whole process from particle generation to weight change and resampling, that is, the overall implementation process from the posterior probability pxk−1|z1:k−1 at time k−1 to the posterior probability density pxk|z1:k at time k. The black solid dots represent the particles in the particle filter, and its size reflects the relationship between the particle weights. The particle weight represented by the large black dot is greater than the particle weight represented by the small black dot. The researcher initially assumed that there are ten particles, and the weights of these ten particles are all equal to 1/N. The curve in the figure above represents the distribution state of all particles. The particles passing through the peak have a greater weight than those passing through the trough.(1)
After ten particles with equal weights have passed the first curve, the weights of the ten particles have changed correspondingly due to the different positions of the crests and troughs of the passing curves. The weight of the particle passing through the wave crest is larger, and the weight of the particle passing through the trough is relatively smaller. The schematic diagram of the particle weight atk−1 shown in the figure above is obtained.(2)
After step 1, the weights of ten particles have changed. At this time, the resampling algorithm is used to keep the particles with larger weights. Particles with small weights are discarded and no longer participate in calculations, reducing the amount of subsequent calculations and leaving the number of effective particles.(3)
After step 2, the particles with larger weights are retained, and they are repeatedly sampled to ensure that the number of particles does not decrease after sampling, and it is still ten particles. And the weights of ten particles are the same as the initial ones, and the prior probability density of particlek is obtained.(4)
The number of resampled particles and the weight of each particle are exactly the same as the momentk−1. At this time, ten particles are observed to obtain the posterior probability density of the particles, and the entire process of particle resampling is completed.Through the above calculation, the influence of small weight particles on the filtering algorithm is well eliminated. On the premise of ensuring the diversity of particles, the researchers remove particles with smaller weights, which greatly improves the utilization of calculations and the accuracy of filtering.The aforementioned algorithm to avoid particle degradation can be briefly described as follows:(1)
Weight calculation: for the sampled particle setX˜ki,wkii=1N, set the initial weight c1=wk1, and use this to calculate the cumulative weight ci=ci−1+wki.(2)
Calculating the random number: calculate the uniformly distributed random number on0,N−1, namely, u−U0,N−1.(3)
Resampling: for the range ofj=1:N, u1=u+N−1j−1, if u1>c, then calculate the next weight; otherwise Xkj=X˜ki and wkj=N−1.The flowchart of particle filtering is shown in Figure7.Figure 7
Particle filter target tracking flowchart.


## 3.2. Vehicle Tracking Algorithm Based on Improved SPF

### 3.2.1. Segmentation of Moving Vehicles

Particle filter algorithm (SPF) is based on segmentation compensation [9]. In the process of tracking the target vehicle, this algorithm divides the target into multiple regions and selects the local features of the target from these regions. If the tracked target is partially occluded or morphologically changed during the tracking process, other areas of the target can be used instead of tracking, which can make the particle filter more accurate and applicable. After the target is located, the target to be tracked needs to be segmented, and the tracking frame is equally divided into the following nine regions as shown in Figure 8.Figure 8
Schematic diagram of target segmentation.Similarly, segmentation methods such as2×2 or 4×4 can also be selected, but 2×2 segmentation has less effect on the segmentation of the target frame and loses the meaning of tracking frame segmentation. When the video resolution is not high, dense segmentation such as 4×4 or even 5×5 makes the resolution of the segmented area too small and fewer features are extracted from it, which is not conducive to the continuous tracking. The segmentation of the 3×3 region selected in this paper is more practical and has no emphasis on the global average distribution. It can be applied to most target tracking situations, and the region with the best local features can be selected from these nine segments for vehicle track.After the segmentation area is obtained, it is necessary to select a suitable segmentation area for tracking during the tracking process. For the 1-9 segmented regions defined in the above figure, the researcher defines the concept of segmentation adjacent. The adjacent bits of segment 1 are segment 2 and segment 4, and the adjacent bits of segment 5 are segment 2, segment 4, segment 6, and segment 8, and so on. After obtaining the relationship of adjacent bits, the selection rule for segmentation is defined as follows: the feature histogram of the segmented block and the feature histogram of adjacent bits are better if the Bhattacharyya coefficient is smaller. The Bhattacharyya coefficient is the similarity coefficient, which is defined as(22)ρp^y^0,q^=∑u=1mp^uy^0,q^u.The value range of its value is between 0 and 1, and the value ofρ reflects the similarity of the calculated two models. The larger the ρ value is, the higher the similarity of the two models. For the segmented region, the larger the ρ value of the adjacent bits, the higher the similarity between the two adjacent bits. In other words, the correlation is large and can be replaced by adjacent bits. Therefore, we take the segmentation area with a small ρ value, that is, the segmentation area with low similarity to the neighboring bits, and discard the segmentation area with a large ρ value.After obtaining the segmentation area with small correlation, find the mean value of the Bhattacharyya coefficients of all the adjacent positions of the segmentation area; that is,(23)ρmean=∑ikρik.For example, for segment 5, it is to find the Bhattacharyya coefficients of segment 2, segment 4, segment 6, and segment 8 and then add the sum and average.After calculating theρ values of all 9 segments, select the smaller segmentation area, and perform target tracking on the selected area.


### 3.2.2. Motion Compensation for Segmented Areas

Figure9 is the particle distribution map formed by the segmented area at a certain time t during the vehicle tracking process. It can be clearly seen that the particles are distributed around the center of the segmented area.Figure 9
Particle distribution diagram at timet.The following figure shows the position A where the segmented area A moves att+1 during the target tracking process. The particle distribution shown in the figure is still the particle distribution at time t.Figure10 shows the position where the segmented area A moves at t+2 during the target tracking process. The particle distribution shown in the figure is the particle distribution at t+2.Figure 10
Particle distribution diagram at timet+1The situation in Figure10 is exactly the same as that in Figure 11. Due to the faster movement of the segmented area, there are fewer particles at the location of the segmented area at t+1, and the target is located at the position of the small red dot in Figure 11. At this time, if the researcher adds an offset to these particles to make the position of the particles shift to the direction of the target movement, the particles at t+1 can be shown in Figure 10, and the particle distribution at t+1 can be obtained. It is not the distribution centered on the position of the small red dot, but there is some deviation in the direction of the target movement, which is closer to the true position of the target in Figure 11. In this way, the segmented area tracked at t+2 after offset compensation is shown in (D).Figure 11
Particle distribution diagram at timet+2.Comparing the tracking frames in Figures11 and 12, we can see that the target position is closer to the real one. The problem of tracking failure in Figure 10 does not occur.Figure 12
Particle distribution diagram at timet+2.The particle center is represented by the following formula:(24)Pp=Pp+θTs.Pp represents the current position of the particle, Ts represents the movement displacement of the vehicle in the previous frame, and θ represents the weighted value. The value of θ is generally between 0.3 and 0.7 according to the movement form of the tracking target. In this paper, the median value is 0.5. In the application process, the particles scattered in the segmented area are added with an offset to improve the problem of large target positioning deviation caused by rapid target movement.


### 3.2.3. Optimized Vehicle Tracking Based on SPF Algorithm

Assume that the segmentation area with a smallerρ value obtained in the previous section is segment 1, segment 5, and segment 9 and the center of the tracking frame is the black spot position, as shown in Figure 13.Figure 13
Schematic diagram of selecting partition area.Then, this paper uses the target tracking results of these three segmented regions to locate the overall target motion and obtains segment 1, segment 5, and segment 9 target tracking results as shown in Figure14.Figure 14
Schematic diagram of tracking results of segmented regions.The final motion position of the target is the vector sum of segment 1, segment 5, and segment 9, which can be expressed by the following formula:(25)Ts≈∑i=1kwkρk.Ts represents the motion displacement of the overall target, ρk represents the motion displacement of the segmentation, and wk is the weight of each segmentation. If there is no special target tracking situation, wk can be set to the same value and the researcher only normalize the motion of all segmented regions. The final target tracking and positioning result is shown in Figure 15.Figure 15
Schematic diagram of target tracking results.The advantage of such segmentation tracking is that, firstly, the segmented areas with greater correlation are eliminated, and they can be replaced with segmented areas related to them, which reduces the amount of calculation accordingly. On the other hand, each small segmented area is equivalent to the target tracking of a small object, and the particle filter method is used to track it to ensure the accuracy of its tracking. In this way, the positive and negative errors of the target tracking result of the entire tracking frame obtained from the vector sum of the vehicle tracking results in a plurality of small segmented regions are offset, the tracking error is reduced, and the tracking accuracy is improved.


## 3.2.1. Segmentation of Moving Vehicles

Particle filter algorithm (SPF) is based on segmentation compensation [9]. In the process of tracking the target vehicle, this algorithm divides the target into multiple regions and selects the local features of the target from these regions. If the tracked target is partially occluded or morphologically changed during the tracking process, other areas of the target can be used instead of tracking, which can make the particle filter more accurate and applicable. After the target is located, the target to be tracked needs to be segmented, and the tracking frame is equally divided into the following nine regions as shown in Figure 8.Figure 8
Schematic diagram of target segmentation.Similarly, segmentation methods such as2×2 or 4×4 can also be selected, but 2×2 segmentation has less effect on the segmentation of the target frame and loses the meaning of tracking frame segmentation. When the video resolution is not high, dense segmentation such as 4×4 or even 5×5 makes the resolution of the segmented area too small and fewer features are extracted from it, which is not conducive to the continuous tracking. The segmentation of the 3×3 region selected in this paper is more practical and has no emphasis on the global average distribution. It can be applied to most target tracking situations, and the region with the best local features can be selected from these nine segments for vehicle track.After the segmentation area is obtained, it is necessary to select a suitable segmentation area for tracking during the tracking process. For the 1-9 segmented regions defined in the above figure, the researcher defines the concept of segmentation adjacent. The adjacent bits of segment 1 are segment 2 and segment 4, and the adjacent bits of segment 5 are segment 2, segment 4, segment 6, and segment 8, and so on. After obtaining the relationship of adjacent bits, the selection rule for segmentation is defined as follows: the feature histogram of the segmented block and the feature histogram of adjacent bits are better if the Bhattacharyya coefficient is smaller. The Bhattacharyya coefficient is the similarity coefficient, which is defined as(22)ρp^y^0,q^=∑u=1mp^uy^0,q^u.The value range of its value is between 0 and 1, and the value ofρ reflects the similarity of the calculated two models. The larger the ρ value is, the higher the similarity of the two models. For the segmented region, the larger the ρ value of the adjacent bits, the higher the similarity between the two adjacent bits. In other words, the correlation is large and can be replaced by adjacent bits. Therefore, we take the segmentation area with a small ρ value, that is, the segmentation area with low similarity to the neighboring bits, and discard the segmentation area with a large ρ value.After obtaining the segmentation area with small correlation, find the mean value of the Bhattacharyya coefficients of all the adjacent positions of the segmentation area; that is,(23)ρmean=∑ikρik.For example, for segment 5, it is to find the Bhattacharyya coefficients of segment 2, segment 4, segment 6, and segment 8 and then add the sum and average.After calculating theρ values of all 9 segments, select the smaller segmentation area, and perform target tracking on the selected area.


## 3.2.2. Motion Compensation for Segmented Areas

Figure9 is the particle distribution map formed by the segmented area at a certain time t during the vehicle tracking process. It can be clearly seen that the particles are distributed around the center of the segmented area.Figure 9
Particle distribution diagram at timet.The following figure shows the position A where the segmented area A moves att+1 during the target tracking process. The particle distribution shown in the figure is still the particle distribution at time t.Figure10 shows the position where the segmented area A moves at t+2 during the target tracking process. The particle distribution shown in the figure is the particle distribution at t+2.Figure 10
Particle distribution diagram at timet+1The situation in Figure10 is exactly the same as that in Figure 11. Due to the faster movement of the segmented area, there are fewer particles at the location of the segmented area at t+1, and the target is located at the position of the small red dot in Figure 11. At this time, if the researcher adds an offset to these particles to make the position of the particles shift to the direction of the target movement, the particles at t+1 can be shown in Figure 10, and the particle distribution at t+1 can be obtained. It is not the distribution centered on the position of the small red dot, but there is some deviation in the direction of the target movement, which is closer to the true position of the target in Figure 11. In this way, the segmented area tracked at t+2 after offset compensation is shown in (D).Figure 11
Particle distribution diagram at timet+2.Comparing the tracking frames in Figures11 and 12, we can see that the target position is closer to the real one. The problem of tracking failure in Figure 10 does not occur.Figure 12
Particle distribution diagram at timet+2.The particle center is represented by the following formula:(24)Pp=Pp+θTs.Pp represents the current position of the particle, Ts represents the movement displacement of the vehicle in the previous frame, and θ represents the weighted value. The value of θ is generally between 0.3 and 0.7 according to the movement form of the tracking target. In this paper, the median value is 0.5. In the application process, the particles scattered in the segmented area are added with an offset to improve the problem of large target positioning deviation caused by rapid target movement.


## 3.2.3. Optimized Vehicle Tracking Based on SPF Algorithm

Assume that the segmentation area with a smallerρ value obtained in the previous section is segment 1, segment 5, and segment 9 and the center of the tracking frame is the black spot position, as shown in Figure 13.Figure 13
Schematic diagram of selecting partition area.Then, this paper uses the target tracking results of these three segmented regions to locate the overall target motion and obtains segment 1, segment 5, and segment 9 target tracking results as shown in Figure14.Figure 14
Schematic diagram of tracking results of segmented regions.The final motion position of the target is the vector sum of segment 1, segment 5, and segment 9, which can be expressed by the following formula:(25)Ts≈∑i=1kwkρk.Ts represents the motion displacement of the overall target, ρk represents the motion displacement of the segmentation, and wk is the weight of each segmentation. If there is no special target tracking situation, wk can be set to the same value and the researcher only normalize the motion of all segmented regions. The final target tracking and positioning result is shown in Figure 15.Figure 15
Schematic diagram of target tracking results.The advantage of such segmentation tracking is that, firstly, the segmented areas with greater correlation are eliminated, and they can be replaced with segmented areas related to them, which reduces the amount of calculation accordingly. On the other hand, each small segmented area is equivalent to the target tracking of a small object, and the particle filter method is used to track it to ensure the accuracy of its tracking. In this way, the positive and negative errors of the target tracking result of the entire tracking frame obtained from the vector sum of the vehicle tracking results in a plurality of small segmented regions are offset, the tracking error is reduced, and the tracking accuracy is improved.


## 4. Test Analysis of Vehicle Tracking

### 4.1. Comparison of Tracking Performance of Different Algorithms

In order to verify the performance of the improved algorithm proposed in this chapter for vehicle tracking, this article uses the mainstream domestic Monte Carlo and convolutional neural network vehicle tracking algorithms to compare and first process the video 05 accident. The size of the video in Figure16 is 432∗240, and the number of frames is 125. This video is a video of a vehicle driving on a highway shot in a helicopter. In the video, a black car rolls over when it collides with another car while driving at a high speed. The tracking success rate, tracking accuracy, and algorithm time-consuming of the two algorithms are compared by tracking the target vehicle [10].Figure 16
Original video frame.The tracking results of the three algorithms are shown in Figures17–19, the red box represents the real tracking that passed the algorithm, and the blue box represents the false tracking that the algorithm failed to track.Figure 17
The tracking results of the particle filter algorithm for segmentation compensation in this paper.Figure 18
Monte Carlo tracking results.Figure 19
Convolutional neural network vehicle tracking.The comparison results in the above figure can be divided into three sections to analyze:(1)
Vehicle driving at high speed: Both Monte Carlo algorithm and SPF algorithm can accurately track vehicles, but SPF algorithm tracking is more accurate.(2)
Vehicle collision: The tracked vehicle suddenly occludes and rotates, and at the same time, it is accompanied by the appearance of similar objects. The other two algorithms get wrong tracking results, while the SPF algorithm tracks accurately.(3)
Vehicle out of control: Large-scale rotation and deformation of the vehicle. At this time, because similar vehicles leave the screen, the other two algorithms cannot track the target, the tracking frame turns blue, and the SPF algorithm still successfully tracks the target.


### 4.2. Analysis of Tracking Results

(1)
The vehicle is traveling at high speed: Both algorithms in the first segment of the video successfully track the target vehicle, but due to the high-speed movement of the target vehicle, the Monte Carlo algorithm is successful in tracking the target. The targets att+1 are always scattered at the edge of the target area at t, leading to tracking deviation problems. In this case, there will be an error rate of tracking deviation of 4.7204.This video has a total of 28 frames. The method in the previous section is used to compare the deviation between the target tracked by the three algorithms and the real target. The results are shown in Figure20.Figure 20
Comparison of vehicle offset distances with different algorithms.Table2 also shows the advantages of the SPF algorithm proposed in this chapter in tracking high-speed moving vehicles, and the average error is reduced by 16.48%.Table 2
Average error comparison.
Average errorMonte Carlo algorithm4.7204 pixelsSPF algorithm1.7354 pixelsConvolutional neural network algorithm3.6781 pixels


## 4.1. Comparison of Tracking Performance of Different Algorithms

In order to verify the performance of the improved algorithm proposed in this chapter for vehicle tracking, this article uses the mainstream domestic Monte Carlo and convolutional neural network vehicle tracking algorithms to compare and first process the video 05 accident. The size of the video in Figure16 is 432∗240, and the number of frames is 125. This video is a video of a vehicle driving on a highway shot in a helicopter. In the video, a black car rolls over when it collides with another car while driving at a high speed. The tracking success rate, tracking accuracy, and algorithm time-consuming of the two algorithms are compared by tracking the target vehicle [10].Figure 16
Original video frame.The tracking results of the three algorithms are shown in Figures17–19, the red box represents the real tracking that passed the algorithm, and the blue box represents the false tracking that the algorithm failed to track.Figure 17
The tracking results of the particle filter algorithm for segmentation compensation in this paper.Figure 18
Monte Carlo tracking results.Figure 19
Convolutional neural network vehicle tracking.The comparison results in the above figure can be divided into three sections to analyze:(1)
Vehicle driving at high speed: Both Monte Carlo algorithm and SPF algorithm can accurately track vehicles, but SPF algorithm tracking is more accurate.(2)
Vehicle collision: The tracked vehicle suddenly occludes and rotates, and at the same time, it is accompanied by the appearance of similar objects. The other two algorithms get wrong tracking results, while the SPF algorithm tracks accurately.(3)
Vehicle out of control: Large-scale rotation and deformation of the vehicle. At this time, because similar vehicles leave the screen, the other two algorithms cannot track the target, the tracking frame turns blue, and the SPF algorithm still successfully tracks the target.


## 4.2. Analysis of Tracking Results

(1)
The vehicle is traveling at high speed: Both algorithms in the first segment of the video successfully track the target vehicle, but due to the high-speed movement of the target vehicle, the Monte Carlo algorithm is successful in tracking the target. The targets att+1 are always scattered at the edge of the target area at t, leading to tracking deviation problems. In this case, there will be an error rate of tracking deviation of 4.7204.This video has a total of 28 frames. The method in the previous section is used to compare the deviation between the target tracked by the three algorithms and the real target. The results are shown in Figure20.Figure 20
Comparison of vehicle offset distances with different algorithms.Table2 also shows the advantages of the SPF algorithm proposed in this chapter in tracking high-speed moving vehicles, and the average error is reduced by 16.48%.Table 2
Average error comparison.
Average errorMonte Carlo algorithm4.7204 pixelsSPF algorithm1.7354 pixelsConvolutional neural network algorithm3.6781 pixels


## 5. Conclusion

In regard to the road traffic environment, this article focuses on moving vehicle target tracking technology to complete the research. It is the future development trend to flexibly solve road traffic problems through intelligent transportation systems. Among them, the vehicle target tracking algorithm is one of the key technologies, which is also an important research direction of image processing and computer vision. Vehicle tracking technology is a subject that combines many advanced technological achievements such as image processing, pattern recognition, and automatic control.The following innovations are worth noting:(1)
Through the corresponding relationship between the vertex adjacency matrix and the regional behavior and vehicle behavior, this paper constructs the vertex adjacency matrix that reflects the characteristics of the undirected bipartite graph and simplifies the logic to complete the regional behavior analysis and vehicle behavior analysis.(2)
By dividing the target area, this paper selects the local features of each part of the target and draws the conclusion. If the tracked target is partially occluded or changed in shape during the tracking process, other areas of the target can be used instead of tracking, which optimizes the accuracy and applicability of particle filtering.



---

*Source: 8829167-2020-11-12.xml*