# Smart City Moving Target Tracking Algorithm Based on Quantum Genetic and Particle Filter

Authors: Zhigang Liu; Jin Shang; Xufen Hua
Journal: Wireless Communications and Mobile Computing
 (2020)

---

## Abstract

In the application of moving target tracking in smart city, particle filter technology has the advantages of dealing with nonlinear and non-Gaussian problems, but when the standard particle filter uses resampling method to solve the degradation phenomenon, simply copying the particles will cause local optimization difficulties, resulting in unstable filtering accuracy. In this paper, a particle filter algorithm combined with quantum genetic algorithm (QGA) is proposed to solve the above problems. Aiming at the problem of particle exhaustion in particle filter, the algorithm adopts the method of combining evolutionary algorithm. Each particle in particle filter is regarded as a chromosome in genetic algorithm, and the fitness of each chromosome corresponds to the weight of particle. For each particle state with weight, the particle is first binary coded with qubit and quantum superposition state, and then quantum rotation gate is used for selection, crossing, mutation, and other operations, after a set number of iterations, the final particle set with accuracy and better diversity. In this paper, the filter state estimation and RMSF ofN=50 and N=100 for nonlinear target tracking and the comparison of real state and state estimation trajectory in time-constant model under nonlinear target tracking are given. It can be seen that in nonlinear state, the quantum genetic and particle filter (QGPF) algorithm can achieve a higher accuracy of state estimation, and the filtering error of QGPF algorithm at each time is relatively uniform, which shows that the algorithm in this paper has better algorithm stability. Under the time-constant model, the algorithm fits the real state and realizes stable and accurate tracking.


---

## Body

## 1. Introduction

Target tracking is widely used in many fields of smart city. Tasks such as video surveillance, human-computer interaction, automatic vehicle control, and human behavior analysis make great use of target tracking [1]. The moving state of the target is usually a nonlinear, non-Gaussian problem with mobility. The development of target tracking algorithm can be divided into four categories: the first category is mainly based on particle filter correlation algorithm; the second category is based on sparse representation theory; and the third category is based on correlation filter tracking algorithm. With the outstanding performance of deep-learning method in feature modeling, the fourth category is mainly based on deep-learning tracking method. Particle filter is a sequential Monte Carlo method proposed by Ulam. The main idea of this method is to fit the distribution of actual samples as much as possible by using the method of weighted sampling in a sequence, so as to calculate the state distribution probability of the target at the current time through the previous sequence state distribution, and take the state corresponding to the maximum probability value as the result of the target state prediction [2, 3]. Particle filter is widely used in the actual target tracking because it does not need to assume the linear and Gaussian state transfer equation and observation equation. In the process of practical application, particle filter has the problem of particle weight degradation. In order to solve this problem, resampling technology is introduced into the particle filter. The purpose of particle resampling is to solve the degradation of particles in the classical Monte Carlo method. The main idea is to resample the probability density function of particles and their corresponding weights. It is realized by increasing the particles with larger weight and reducing the particles with smaller weight. But directly copying high weight particles and discarding low weight particles will lead to particle dilution. On the other hand, in order to achieve high-precision state estimation, more particles are usually needed to participate, and the number of particles affects the efficiency of the algorithm. In view of the above problems, scholars at home and abroad have conducted a lot of research. The extended Kalman filter [4] and the unscented Kalman filter [5] integrate the latest observation information to provide the density function for particle filter. Although the accuracy of particle filter is improved to a certain extent, the amount of calculation is also greatly increased. The adaptive partial resampling method, which only resamples a part of the particle set, makes a moderate compromise between the weight degradation and particle dilution [6]. The sensitive resampling algorithm keeps the particles with the largest weight and propagates them by the quasi-Monte Carlo method, which restrains the lack of samples but increases the calculation time [7]. The deterministic resampling algorithm should consider both the particle weight and the particle state value when sampling, avoiding the nondetection discard of low weight particles and avoiding the sample dilution to some extent [8]. After the resampling of the PF algorithm by using the GA algorithm, Kao and Zahara updated the particles by cross-mutation to alleviate sample degradation, which improved the accuracy of PF algorithm to a certain extent, but made the calculation efficiency of PF algorithm lower [9]. In reference [10], a robust regularization particle filtering (RPF) method is proposed to reduce multimodal loss by mixing local RPF. In reference [11], an improved method of spherical simple unscented particle diversity (ssupf) is proposed and applied to high-precision astronomical navigation in deep-space environment. It is worth noting that the number of sampled particles has a great impact on PF performance. Reference [12] shows that too few sampling particles will lead to divergence, while too many particles will increase the computational burden and limit the real-time performance of navigation. In order to improve the efficiency of PF, a novel adaptive PF method based on the Kullback Leibler distance (KLD) is proposed in [13, 14] and applied to mobile robot positioning. In reference [15], many PF techniques for adaptive sampling particle number are reviewed. The above research shows that it is feasible to control the number of particles to ensure the estimation quality and reduce the calculation cost. In reference [16], a resampling step is introduced, and an algorithm of sampling importance resampling (SIR) is proposed. The particles with high weight are resampled, and the particles with low weight are discarded, and then a new set of particles is generated by state space model and measurement model. Li et al. proposed a lightweight particle filter tracking method [17], introduced the response graph of correlation filter into the calculation of particle weight, and used fewer particles to reduce the calculation burden in the sampling process. Firouznia et al. introduced the chaos theory into the particle filter framework, effectively reducing the number of particles and search space [18]. Jenkins et al. introduced the multibag subspace recovery mechanism to solve the problem of updating the appearance model in particle filter tracking and resetting in case of tracking drift, so as to improve the robustness of the model [19]. Although the tracking algorithm based on particle filter framework is constantly improving [20–22], there are still some problems in the existing algorithm, such as poor universality in complex scenes, and the tracking accuracy needs to be further improved. In [23], based on the PF algorithm, the principle of the mean-shift algorithm is integrated to realize the target tracking model of the fusion algorithm. This kind of algorithm can improve the calculation efficiency and real-time performance of the PF algorithm, but how to choose the appropriate fusion strategy of the mean-shift algorithm is also one of the difficulties; In addition, how to prevent tracking drift should be considered in this algorithm. In [24], the relevant knowledge expressed by sparse theory is applied to the PF algorithm to solve the target tracking task. The experiment shows that the improved method can improve the accuracy of the target tracking model to a certain extent, but the real-time performance of the algorithm is usually affected by too much calculation when solving the problem. With the rapid development of depth learning technology and the outstanding performance of depth model in image feature representation, the fusion target tracking algorithm based on depth learning method has been proposed one after another. In [25, 26], the combination of the depth model algorithm and PF principle is applied to the target tracking task, which has achieved quite good results. However, the depth learning model usually needs a large number of training samples with supervision information to train the model, so how to design a suitable structure to improve the calculation speed to meet the real-time requirements of the algorithm is also an urgent problem to be solved [27–29]. In this paper, a particle filter method combined with quantum genetic algorithm is proposed to solve the above problems. Aiming at the problem of particle exhaustion in particle filter, the algorithm adopts the method of combining evolutionary algorithm to carry out cross and mutation operation on particles. The particles with high posterior probability have high adaptability, so as to improve the accuracy of filter results. Compared with the classical genetic algorithm, the advantage of quantum genetic algorithm lies in the selection of population coding mode and evolution strategy. The core of the population coding method of quantum genetic algorithm is to code individuals by using qubits and quantum superposition states, so that each individual can represent information of multiple states, which greatly enriches the diversity of the population; at the same time, the population is updated by using quantum rotation gate, and the individual adaptability is improved to guide evolution. In the iterative process, the superposition state of each qubit will collapse to a certain state, which tends to be stable and converge, and finally achieve the purpose of optimization. Because of the unique coding and updating method, the quantum genetic algorithm has more diversity, faster convergence speed, and higher convergence accuracy than the classical genetic algorithm. The genetic mechanism can not only select excellent individuals by selection operator but also generate new individuals by cross operator and mutation operator. Therefore, properly adjusting the selection probability, crossover probability and mutation probability can ensure the effectiveness of particles and take into account the diversity of particles. The specific combination process of quantum genetic algorithm and particle filter is as follows: each particle of the particle filter is regarded as the chromosome in genetic algorithm, and the fitness of each chromosome corresponds to the weight of particle; for each particle state with weight, firstly, the particle is binary coded with qubit and quantum superposition state, and then it is selected, crossed, and selected by quantum revolving gate After the set number of iterations, the final particle set is more accurate and diverse. In this paper, the QGPF algorithm is proposed by combining QGA with PF; the algorithm synthesizes the local search ability and calculation efficiency of QGA and the nonlinear filtering principle of PF algorithm. The simulation experiments of nonlinear target tracking model and time-constant model show that the algorithm has high precision and good numerical stability and can complete the accurate tracking of smart city moving targets.


## 2. Particle Filter Algorithm

Particle filter is a kind of filter algorithm based on the Bayesian theory and Monte Carlo simulation. Its core idea is to use a group of random samples to approximate the posterior conditional probability density of state variables. It is assumed that the nonlinear dynamic process is expressed as follows:(1)xk=fxk−1,vk−1zk=hxk,wk,in which, x is the state value of the system, f⋅ is the state transfer equation, z is the state observation value, h⋅ is the system observation equation, w is the system noise, and v is the observation noise.The recursive Bayesian filtering includes two processes: prediction and update.Prediction process: the posterior probability densitypxk−1z1:k−1 of k−1 time is used to predict the predicted probability density pxz1:k−1 of k time.
(2)pxkz1:k−1=∫pxkxk−1pxk−1z1:k−1dxk−1.Update process: update the posterior probability densitypxkz1:k of k time by the observation information zk of k time.
(3)pxkz1:k=pzkxkpxkz1:k−1∫pzkxkpxkz1:k−1dxk.Because of the integral operation in the Bayesian filtering algorithm, it is difficult to obtain closed analytical solutions for the nonlinear and non-Gaussian systems. By using the Monte Carlo method, the integral operation is transformed into the sample weighted sum operation. The posterior probability density can be approximated by the sample particlexki and its weight wki.
(4)pxkzk=∑i=1Nwkiδxk−xki,in which δ⋅ is the Dirac function.However, it is very difficult to get samples from the posterior probability density under normal circumstances. In this paper, an importance distribution functionqx0:kz1:k, which is easy to sample, is introduced. In order to simplify the calculation and make the weight calculation of particles recursive, the importance distribution function satisfies the following decomposition:
(5)qx0:kz1:k=qx0:kx0:k−1,z1:kqx0:k−1z1:k−1.Then, the weight update formula is(6)wki=wk−1ipzkxkipxkixk−1iqxkix0:k−1i,z1:k.The status output is(7)xk=∑i=1Nwkixki.Particle filter initializes the sample at the initial time and extracts the initialization state from the prior distribution. At the next moment, the particles transfer state according to the transfer equation and assign the weight of particles according to the actual system observation. Finally, all particles are weighted sum to get the state estimation at this time. After resampling the particles, the filtering process of the next period is continued [30, 31].


## 3. Quantum Genetic Algorithm

QGA is a newly developed probability evolution algorithm based on the quantum computing principle. It uses the concept and theory of quantum computing to integrate the characteristics of genetic algorithm (GA) which can maintain good population diversity. It applies the probability amplitude representation of quantum bits to chromosome coding, so that a chromosome can express the superposition of multiple states and use quantum rotation gate and quantum nongate to realize chromosome update operation, so as to achieve population optimization.The population of QGA consists of quantum chromosomes encoded by quantum bits. Quantum bit is the smallest information unit in QGA, which is different from the classical bit in that can not only be in state 0 or 1 but also represent any superposition state of the two, so QGA has more diversity than GA. The population withN individuals and M-length quantum chromosome is expressed as
(8)Pt=p1t,p2t,p3t,⋯pnt,pjt=α1tβ1tα2tβ2t⋯⋯αmtβmtj=1,2,3,⋯,nwhere pjt is an individual of the t generation, αi and βi are complex numbers, which are called probability amplitude pairs, satisfying the normalization condition α2+β2=1, and t is genetic algebra.Quantum gate is the executive mechanism of QGA to realize evolutionary operation. One of the key points of quantum genetic algorithm is to construct a proper quantum gate. According to the characteristics of QGA, it is more suitable to choose quantum revolving gate. The update of quantum bit is realized by quantum rotating gate as follows:(9)αi′βi′=cosθi−sinθisinθicosθiαiβi,in which the quantum revolving gate is
(10)Ui=cosθi−sinθisinθicosθi,αi,βiTαi′,βi′Tare the ith quantum bit in the chromosome before and after renewal, and θi is the rotation angle of the quantum gate.


## 4. The Particle Filter Algorithm Combined with the Quantum Genetic Algorithm

The particle at a certain time is regarded as a possible state of the target’s position, and the weight of the particle represents its possibility. The particle set can be regarded as the population of quantum genetic algorithm at a certain time, that is, each particle at that time is regarded as an individual in the population. A nondegenerate particle filter algorithm is implemented by combining quantum genetic algorithm and particle filter algorithm. The whole algorithm is divided into three stages: presampling, genetic operation, and particle individual selection: In the presampling stage, the presampled particle set at timeK is extracted from the particle set at time K−1 through the importance distribution, and its weight is determined by measuring its consistency with the road sign observation. The weight of the particle represents the likelihood of the particle representing the environment, which can also be regarded as the fitness of the particle.The fitness function is related to the function to be realized. In this paper, we study the tracking of moving objects in smart city and make the particles correspond to the candidate solutions of tracking objects. The fitness function is used to evaluate the quality of the candidate solutions (particles) given.zk represents the observed output. The larger the probability of observing zk is, the better the particle can represent the real position of the object, namely
(11)fitnessxki=Pzkxki,in which fitnessxki represents the fitness of i particles at K time, zk represents the observation result of the target at K time, and Pzkxki represents the probability of observing zk at the position of i particles at K time. Therefore, the higher the probability is, the more representative the particle is of the real position of the target, and the greater its weight.Quantum genetics is applied to the resampling stage of particles to expand the diversity of particle sets. In the initialization stage of genetic algorithm, in order to set more genetic opportunities for particles with high fitness, the weights of all particles are sorted and normalized. In the stage of genetic generation of new particles, the quantum cross-mutation operation is used to generate new particles, and the algorithm is set to achieve high degree of freedom particles that have a higher probability to continue the offspring particles. This setting can effectively avoid particle degradation, because the cross-operation increases the diversity of particles, and the distribution of these new particles is wider than that before the cross, which is conducive to the improvement of particle positioning ability. In order to avoid too much error caused by particle dispersion, the project plans to carry out mutation operation according to the weight of particles: for particles whose weight is less than the average level, we can generate new particles with greater weight through mutation operation, while larger particles with better performance need to avoid the impact of mutation on them. After mutation, the particle set can be transferred to the real distribution of state.The specific flowchart is shown in Figure1. The input of the flowchart is the state of particles at K‐1 time (each particle represents the position of the target), and the output is the state of particles at K time. Firstly, according to the state of particles and the visual perception information of the target at K‐1 time, the state of each particle is initialized and the weight is updated, and the particles with high weight are inherited preferentially through the weight sequencing. Secondly, in the process of resampling, combined with the quantum genetic algorithm, we set the number of genetic iterations (expressed by K). In each generation, the quantum bits and superposition states are used to encode the particles, and then the quantum rotating gate is used to carry out genetic and mutation operations on the particles in the population, so as to get the new generation of particles. If the set number of times has been reached, the iteration is over. If not, a new cycle will be carried out, and finally, the diverse particles after crossing and mutation will be obtained, which can effectively solve the problem of particle depletion caused by the long-term running of the target.Figure 1
Flowchart of quantum genetic algorithm combined with particle filter.


## 5. Simulation Experiment and Result Analysis

In order to detect the performance of QGPF tracking algorithm, the standard particle filter algorithm (PF), the particle swarm optimization filter algorithm (PSOPF), and the algorithm in this paper (QGPF) are simulated and compared. The three algorithms are simulated and tested by two kinds of target models: nonlinear target tracking model and time-constant value model.


### 5.1. Nonlinear Target Tracking Model

Next, a nonlinear, non-Gaussian target tracking problem is simulated, and the motion state equation and measurement equation of the system are as follows:(12)xk=1+sin0.03πk+0.5xk−1+wk−1yk=0.2x2k+νk,k≤30−2+0.4xk+νk,k>30.The output results are represented by the mean value of the particle set of each particle filter algorithm:(13)xk∧=1S∑i=1Sxki.The evaluation standard of filtering error is(14)RMSE=1T∑k=1Txk−xk∧2,in which wk−1 and νk, the system noise and measurement noise, are all zero mean Gaussian white noise. The choice of population size requires a trade-off between accuracy, stability, and running time, sometimes taking into account the dimensions of the problem. Generally speaking, if we focus on reducing operation time, the population size can be set at about 40; if we prefer high precision and high stability, it can be set at 50 to 80. When the population size is greater than 100, the improvement of its precision is not obvious [32, 33]. Therefore, in terms of population size, we choose 50 and 100.Figures2–5 shows the filtering state estimation and filtering error statistics when the number of filtering particles is 50 and 100, respectively.Figure 2
Filter state estimation (N=50).Figure 3
RMSF mean curve (N=50).Figure 4
Filter state estimation (N=100).Figure 5
RMSF mean curve (N=50).It can be seen from Figures2–5 that compared with the standard PF and PSOPF algorithm, the QGPF algorithm proposed in this paper can achieve higher precision state estimation, and the filtering error of QGPF algorithm at each time is relatively uniform, which shows that the algorithm in this paper has better algorithm stability. This is because the QGP algorithm applies quantum genetics to the resampling phase of particles, expands the diversity of particle set, uses quantum cross-mutation operation to generate new particles, and sets a higher probability to realize the high degree of freedom particles in the algorithm to continue the offspring particles, effectively avoiding particle degradation. At the same time, in order to avoid excessive error caused by particle dispersion, it advances according to the weight of particles, line mutation operation, so that the particles set to the real distribution of the state around the transfer.QGA is integrated into PF, and the particles are binary coded with quantum bits and quantum superposition states. The stability and accuracy of the algorithm are guaranteed by selecting the appropriate selection probability, crossover probability, and mutation probability. In the results of Figures2–5, this conclusion has been verified.


### 5.2. Time-Constant Model

The traditional PF algorithm has insufficient tracking ability due to sample degradation, especially in the time-constant model. Next, the improved particle filter algorithm is simulated in the time-constant model to test its tracking ability. The system state equation and observation equation of the time-constant model are shown in formula (15).
(15)xk=5k≤301030<k≤60yk=xk+νk.Figure6 shows the comparison of real state and state estimation trajectory. The results show that the optimization of PF with QG can keep the diversity of particles, prevent the degradation of particles, and achieve stable and accurate target tracking.Figure 6
Comparison of time-constant target tracking track.PF algorithm has good performance in dealing with the system state problems of nonlinear and non-Gaussian distribution, but the effect of conventional particle filter algorithm is not robust under complex conditions, mainly including how to design and select the importance sampling density function and how to solve the problem of particle degradation along with the iteration process and the increase of the calculation amount caused by a large number of particle sampling. The simulation results show that the algorithm proposed in this paper has solved the above problems well and has satisfactory stability and accuracy.


## 5.1. Nonlinear Target Tracking Model

Next, a nonlinear, non-Gaussian target tracking problem is simulated, and the motion state equation and measurement equation of the system are as follows:(12)xk=1+sin0.03πk+0.5xk−1+wk−1yk=0.2x2k+νk,k≤30−2+0.4xk+νk,k>30.The output results are represented by the mean value of the particle set of each particle filter algorithm:(13)xk∧=1S∑i=1Sxki.The evaluation standard of filtering error is(14)RMSE=1T∑k=1Txk−xk∧2,in which wk−1 and νk, the system noise and measurement noise, are all zero mean Gaussian white noise. The choice of population size requires a trade-off between accuracy, stability, and running time, sometimes taking into account the dimensions of the problem. Generally speaking, if we focus on reducing operation time, the population size can be set at about 40; if we prefer high precision and high stability, it can be set at 50 to 80. When the population size is greater than 100, the improvement of its precision is not obvious [32, 33]. Therefore, in terms of population size, we choose 50 and 100.Figures2–5 shows the filtering state estimation and filtering error statistics when the number of filtering particles is 50 and 100, respectively.Figure 2
Filter state estimation (N=50).Figure 3
RMSF mean curve (N=50).Figure 4
Filter state estimation (N=100).Figure 5
RMSF mean curve (N=50).It can be seen from Figures2–5 that compared with the standard PF and PSOPF algorithm, the QGPF algorithm proposed in this paper can achieve higher precision state estimation, and the filtering error of QGPF algorithm at each time is relatively uniform, which shows that the algorithm in this paper has better algorithm stability. This is because the QGP algorithm applies quantum genetics to the resampling phase of particles, expands the diversity of particle set, uses quantum cross-mutation operation to generate new particles, and sets a higher probability to realize the high degree of freedom particles in the algorithm to continue the offspring particles, effectively avoiding particle degradation. At the same time, in order to avoid excessive error caused by particle dispersion, it advances according to the weight of particles, line mutation operation, so that the particles set to the real distribution of the state around the transfer.QGA is integrated into PF, and the particles are binary coded with quantum bits and quantum superposition states. The stability and accuracy of the algorithm are guaranteed by selecting the appropriate selection probability, crossover probability, and mutation probability. In the results of Figures2–5, this conclusion has been verified.


## 5.2. Time-Constant Model

The traditional PF algorithm has insufficient tracking ability due to sample degradation, especially in the time-constant model. Next, the improved particle filter algorithm is simulated in the time-constant model to test its tracking ability. The system state equation and observation equation of the time-constant model are shown in formula (15).
(15)xk=5k≤301030<k≤60yk=xk+νk.Figure6 shows the comparison of real state and state estimation trajectory. The results show that the optimization of PF with QG can keep the diversity of particles, prevent the degradation of particles, and achieve stable and accurate target tracking.Figure 6
Comparison of time-constant target tracking track.PF algorithm has good performance in dealing with the system state problems of nonlinear and non-Gaussian distribution, but the effect of conventional particle filter algorithm is not robust under complex conditions, mainly including how to design and select the importance sampling density function and how to solve the problem of particle degradation along with the iteration process and the increase of the calculation amount caused by a large number of particle sampling. The simulation results show that the algorithm proposed in this paper has solved the above problems well and has satisfactory stability and accuracy.


## 6. Conclusion

Particle filter, which is commonly used in target tracking, is a method to realize the posterior probability density estimation of target state through the prediction and update of particle state and weight. Particle degradation is an inevitable problem in standard particle filter. After updating the particle state, in order to solve the problem of particle degradation, it is necessary to resample the particle set to remove the unimportant particles. However, such removal often makes the particle set lose its diversity, and quantum genetic algorithm can well maintain the diversity of the population. Therefore, the introduction of quantum genetic algorithm into particle filter can better solve the problem of particle filter degradation. At the same time, the quantum parallel operation also improves the real-time tracking. In the process of target tracking, complex background, partial or total occlusion of target and illumination change will affect the tracking accuracy and real-time performance. In this paper, the particle filtering algorithm combined with the quantum genetic algorithm (QGA) uses binary coding and feature fusion of particles through qubits and quantum superposition states to reduce the degradation of particles and improve the tracking accuracy and real-time performance.



---

*Source: 8865298-2020-06-20.xml*