CN104574442A - Self-adaptation particle swarm optimization particle filter moving target tracking method - Google Patents

Abstract

The invention discloses an adaptive particle swarm optimization particle filter moving target tracking method, which belongs to the technical field of image processing and intelligent video monitoring. The method of the present invention uses the particle swarm optimization method to optimize the position of the particle during the tracking process of the moving target by the particle filter method; The situation adjusts the number of particles adaptively. Compared with the prior art, the present invention can not only effectively alleviate the local optimal phenomenon in particle swarm optimization, improve the accuracy of target tracking, but also has the advantages of low algorithm complexity and good real-time performance.

Description

Adaptive Particle Swarm Optimization Particle Filter Moving Target Tracking Method

technical field

The invention relates to a moving target tracking method, in particular to an adaptive particle swarm optimization particle filter moving target tracking method, which belongs to the technical field of image processing and intelligent video monitoring.

Background technique

Moving target tracking is a hotspot in the field of image processing and intelligent video surveillance technology, and it is also a key technology in the fields of robot navigation and precision guidance, and has a wide range of applications. For example: capture the trajectory and attitude of the target movement in the experiment, detect the flow of traffic roads, monitor and analyze video on important occasions, etc. Therefore, the tracking of moving objects has very important research significance. The tracking of moving target includes several technical components such as target detection, feature extraction and matching tracking. Among them, the detection of the target and the feature extraction of the target require certain prior knowledge, and then according to a certain algorithm, the previously known information is used to predict the target motion information (position, speed, etc.) at the next moment to realize the tracking of the moving target. A good tracking algorithm should have the characteristics of high reliability, good real-time performance, and precise accuracy.

Many effective algorithms have been proposed for the tracking of moving targets, among which, the target tracking technology based on Kalman filter theory has received great attention. However, Kalman filtering is only suitable for linear systems. For this reason, Sunahara, Buey and others further applied Kalman filtering to the nonlinear field and proposed Extended Kalman filtering (EKF), but this method greatly increases the computational complexity, so It has not been widely used in practice. Another commonly used method is the mean shift algorithm - the Mean-shift algorithm [D.Comaniciu, V.Ramesh and P.Meer, "Real-time tracking of non-rigid objects using Mean Shift", Proceedings of IEEE Computer Society Conference on Computer Vision and Pattern Recognition,2:142-149,2000], it is a kind of parameter-free estimation algorithm based on kernel function, which does not require prior knowledge, and the convergence speed is relatively fast, but for fast motion and non-Gaussian noise environment There are limitations. Particle Filtering (PF: Particle Filtering) algorithm has received more and more attention in the field of target tracking in recent years. It is not limited to linear systems, nor does it require noise to obey Gaussian distribution, and it can also achieve reliable tracking when the target is occluded. However, the problem of particle depletion and large amount of calculation in particle filter is an important obstacle to practical application.

In order to solve the problem of particle impoverishment in particle filter moving target tracking, many scholars choose to apply particle swarm optimization algorithm (Particle Swarm optimization, PSO for short) to particle filter to form particle swarm optimization particle filter algorithm (PSOPF for short), Thus, the diversity of particles can be guaranteed, but the particle swarm optimization algorithm in the existing PSOPF algorithm tends to make the particles fall into the local optimum, which leads to inaccurate location information of the target.

In response to this problem, some adaptive particle swarm optimization particle filter algorithms have been proposed. For example, some researchers proposed a new dynamic particle swarm optimization particle filter algorithm with neighborhood adaptive adjustment. This algorithm considers the neighborhood information of particles, and uses The diversity factor, the neighborhood expansion factor and the neighborhood restriction factor jointly adjust the number of particles in the neighborhood of particles, control the influence of particles on the neighborhood, reduce the local optimum phenomenon, and achieve the best convergence speed and optimization ability. Balance; some researchers also propose to assign different weights to each particle, and to adjust the particle weights adaptively during the iterative process. Although these methods can solve the problem that the particle swarm optimization algorithm in the PSOPF algorithm is easy to make the particles fall into the local optimum to varying degrees, they all have the disadvantages of complex algorithms and large amount of calculation, and the real-time performance of moving target tracking is not satisfactory.

Contents of the invention

The technical problem to be solved by the present invention is to overcome the deficiencies of inaccurate positioning and large amount of calculation existing in the existing particle swarm optimization particle filter moving target tracking technology, and provide an adaptive particle swarm optimization particle filter moving target tracking method. While accurately improving the accuracy of moving target tracking, its computational complexity is lower, and the real-time performance of target tracking is better.

The present invention specifically adopts the following technical solutions:

The adaptive particle swarm optimization particle filter moving target tracking method uses the particle swarm optimization method to optimize the particle position during the tracking process of the moving target with the particle filter method; when using the particle swarm optimization method to optimize the particle position , the number of particles is adaptively adjusted according to the position change of the global optimal particle, as follows: if the position of the global optimal particle always changes in consecutive M1 iterations, the number of particles is reduced; for example, the position of the global optimal particle If it remains unchanged in consecutive M2 iterations, then increase the number of particles; M1 and M2 are preset integers greater than or equal to 3.

M1 and M2 can be equal or not.

Compared with the prior art, the present invention has the following beneficial effects:

The present invention combines Adaptive Particle Swarm Optimization (APSO) technology with Particle Filter (PF) to track the moving target, which can effectively overcome the phenomenon of particle depletion, and further optimize the position of particles by using the particle swarm optimization method , according to the position change of the global optimal particle, the number of particles is adaptively adjusted, which can effectively reduce the local optimal phenomenon in particle swarm optimization and improve the accuracy of target tracking. At the same time, it has low algorithm complexity and real-time performance. good points.

Description of drawings

Figure 1 is a schematic diagram of the basic flow of the particle filter algorithm;

Fig. 2 is the basic flowchart diagram of particle swarm optimization algorithm;

Fig. 3 is a schematic flow chart of the adaptive particle swarm optimization particle filter moving target tracking method of the present invention;

FIG. 4 is a comparison of the effects of moving target tracking on the Browse1 video sequence using the method of the present invention and the traditional particle filter method respectively.

Detailed ways

The technical scheme of the present invention is described in detail below in conjunction with accompanying drawing:

The idea of the present invention is to improve the existing particle swarm optimization particle filter moving target tracking technology, which is not accurate enough in positioning and has a large amount of calculation. , the number of particles is adaptively adjusted according to the position change of the global optimal particle: in the process of particle iterative update, if the global optimal point is updated many times in a row, it means that the current particle swarm is in the process of constantly developing a new state , reduce the number of particles appropriately at this time; on the contrary, if the global optimal point has not been updated for many times in a row, the particle swarm is in a convergent state at this time, and may fall into the local optimal point and cannot jump out, that is, the target position may not be tracked properly. To be precise, the number of particles needs to be increased at this time, so as to help the particle swarm jump out of this point and expand the search range.

In order to facilitate the public's understanding of the technical solutions of the present invention, the particle filter and particle swarm optimization technologies involved in the present invention will be briefly introduced below.

Figure 1 shows the basic flow of the particle filter algorithm. The idea of particle filtering (PF: Particle Filtering) is based on the Monte Carlo method, which uses particle sets to represent probability problems, and can be used in any form of space model. Its core idea is to express its distribution by sampling random state particles from the posterior probability, which is a sequential importance sampling method. To put it simply, it is to approximate the probability density function by finding a group of random samples propagated in the state space, and replace the integral operation with the sample mean value, so as to obtain the process of making the state realize the minimum variance distribution.

In general, the state space model of particle filter can be described as:

x _k ＝f(x _k-1 )+u _k-1

y _k ＝h(x _k )+w _k

x _k is the state value of the system at time k, y _k is the measurement value of the system state x _k , u _k-1 , w _k are the process noise and measurement noise values of the nonlinear system, respectively.

The basic steps of particle filter target tracking are as follows:

1. Initialization: initially track frame k, and then sample the initial particle set according to the prior distribution p(x _k )

2. For k=1,2,...

a) Importance sampling: sampling particle sets from a proposal distribution,

b) Importance weighting:

The importance weighting formula is:

${\mathrm{<span\; class="notranslate">\; w</span>}}_{\mathrm{<span\; class="notranslate">\; t</span>}}^{\mathrm{<span\; class="notranslate">\; i</span>}}<span\; class="notranslate">\; =</span>{\mathrm{<span\; class="notranslate">\; w</span>}}_{\mathrm{<span\; class="notranslate">\; t</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; 1</span>}}^{\mathrm{<span\; class="notranslate">\; i</span>}}\frac{\mathrm{<span\; class="notranslate">\; p</span>}<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; the\; y</span>}}_{\mathrm{<span\; class="notranslate">\; t</span>}}<span\; class="notranslate">\; |</span>{\mathrm{<span\; class="notranslate">\; x</span>}}_{\mathrm{<span\; class="notranslate">\; t</span>}}^{\mathrm{<span\; class="notranslate">\; i</span>}}<span\; class="notranslate">\; )</span>\mathrm{<span\; class="notranslate">\; p</span>}<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; x</span>}}_{\mathrm{<span\; class="notranslate">\; t</span>}}^{\mathrm{<span\; class="notranslate">\; i</span>}}<span\; class="notranslate">\; |</span>{\mathrm{<span\; class="notranslate">\; x</span>}}_{\mathrm{<span\; class="notranslate">\; t</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; 1</span>}}^{\mathrm{<span\; class="notranslate">\; i</span>}}<span\; class="notranslate">\; )</span>}{\mathrm{<span\; class="notranslate">\; q</span>}<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; x</span>}}_{\mathrm{<span\; class="notranslate">\; t</span>}}^{\mathrm{<span\; class="notranslate">\; i</span>}}<span\; class="notranslate">\; |</span>{\mathrm{<span\; class="notranslate">\; x</span>}}_{\mathrm{<span\; class="notranslate">\; t</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; 1</span>}}^{\mathrm{<span\; class="notranslate">\; i</span>}}<span\; class="notranslate">\; ,</span>{\mathrm{<span\; class="notranslate">\; the\; y</span>}}_{\mathrm{<span\; class="notranslate">\; t</span>}}<span\; class="notranslate">\; )</span>}<span\; class="notranslate">\; ,</span>$

Then normalize the weights of the particles:

${\mathrm{<span\; class="notranslate">\; w</span>}}_{\mathrm{<span\; class="notranslate">\; t</span>}}^{\mathrm{<span\; class="notranslate">\; i</span>}}<span\; class="notranslate">\; =</span>\frac{{\mathrm{<span\; class="notranslate">\; w</span>}}_{\mathrm{<span\; class="notranslate">\; t</span>}}^{\mathrm{<span\; class="notranslate">\; i</span>}}}{\underset{\mathrm{<span\; class="notranslate">\; j</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; 1</span>}}{\overset{\mathrm{<span\; class="notranslate">\; N</span>}}{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}}{\mathrm{<span\; class="notranslate">\; w</span>}}_{\mathrm{<span\; class="notranslate">\; t</span>}}^{\mathrm{<span\; class="notranslate">\; j</span>}}}$

c) Resampling: If N _eff < N _th then resample for Thus a new set of particles is obtained: If the condition is not met then no resampling step is required.

3. Estimation of the state: With the position and weight of the particle, the position of the target can be estimated.

4. Next, judge whether it is the end frame, if yes, the tracking ends, if not, enter the tracking process of the next state, and go to step 2.

Figure 2 shows the basic framework of particle swarm optimization algorithm. In Particle Swarm Optimization (PSO), all particles have an fitness value determined by an optimized function, and each particle has a speed that determines their flying direction and position. Then all particles tend to approach the current optimal particle. PSO initializes a group of random particles, and then iteratively updates itself by tracking the current particle extremum and global extremum points. The specific steps are: first select the population size N, express the i-th particle as an N-dimensional vector _x i =(x _i1 ,x _i2 ,...,x _iN ),i=1,2,... , m, that is, the position of the i-th particle in the N-dimensional search space is _xi, and its fitness value can be calculated by bringing it into the objective function, so as to measure the quality of _xi . The velocity of the i-th particle is also an N-dimensional vector, denoted as v _i =(v _i1 ,v _i2 ,...,v _iN ), and the velocity determines the convergence speed of the self-care in the search space. The optimal position searched by the i-th particle so far is p _i =(p _i1 ,p _i2 ,...,p _iN ), and the optimal point searched so far by the entire particle swarm is p _g =(p _g1 ,p _g2 ,...p _gN ).

Then update the velocity and position of the particle according to the equation:

v _i ＝w*v _i +c1*rand1*(p _i -x _i )+c2*rand2*(p _g -x _i )

x _i+1 = x _i +v _i

After updating the position of the particle, the optimal point and the global optimal point of the current particle are continuously updated. After another iteration, it is necessary to judge whether the most suitable value of the current target state satisfies the condition according to the latest estimated state of the target, and if so, jump out of the iterative process and end the process of finding the optimum point, otherwise continue the iteration.

Although the particle filter algorithm can solve nonlinear and non-Gaussian problems, there are still some problems in this algorithm. The most important of these is that it takes a large number of samples to get close to the posterior probability density of the system, so the amount of calculation is very large, and the resampling stage will cause the loss of sample validity and diversity, resulting in poor samples. phenomenon. For particle swarm optimization, it often encounters the problem that particles fall into the local optimal point and cannot jump out of the multi-peak problem, so the global optimal point cannot be obtained, which affects the tracking effect. Therefore, the present invention combines the two, and at the same time adjusts the number of particles adaptively according to the position change of the global optimal particle during the particle swarm optimization process, thereby on the one hand overcoming the traditional particle filter method with a large amount of calculation and particle depletion. On the other hand, it overcomes the problem of inaccurate tracking results caused by falling into local optimum. At the same time, compared with various existing adaptive particle swarm optimization particle filter algorithms, for example, the existing neighborhood adaptive adjustment dynamic particle swarm optimization particle filter algorithm needs to calculate the diversity factor, neighborhood expansion factor and neighborhood restriction factor To carry out adaptive adjustment to the number of particles in the neighborhood of particles, the method of the present invention only needs to realize the adaptive adjustment of the number of particles according to the continuous update of the global optimal value in the iterative process, which has lower computational complexity and better real-time performance. good.

Fig. 3 is the basic flow schematic diagram of the adaptive particle swarm optimization particle filter moving target tracking method of the present invention, and its specific algorithm flow is as follows:

First read the initial frame k of the video sequence, select the target to be tracked, and establish the color histogram feature p(x _k ) based on the color information for the selected area, initialize the system tracking equation, the number of particles N, during the tracking process The noise R _k , and the initial position of the particle obeys the Gaussian function distribution centered on the geometric center of the initialized target area.

State transition: When the video sequence moves to the next frame, according to the set parameters, the particle moves to a certain position, and then calculates the color information histogram of the current particle according to the position of the i-th particle as The similarity relationship between the two is obtained by calculating the Bhattacharyachian distance between it and the color histogram feature of the initial frame, and then the weight of the current particle is obtained. After counting the N particles, the weight needs to be normalized, and according to the weight and Positional relationship Get the predicted target position.

Then enter the step of adaptive particle swarm optimization:

Initialize the iteration threshold T _m for jumping out of the particle swarm optimization. Afterwards, the speed and position of the particles are continuously updated according to the speed and position equations of particle swarm optimization. Here, whether the extreme value p is updated is determined according to the function result of the Bhattachary distance. If the similarity is high, the corresponding extreme value is to update. p _i is the individual extremum of the current particle i, and p _g is the global extremum of the entire particle group. After each particle is updated, it needs to be re-judged to see if the similarity between the predicted target position and the initial target reaches the set threshold. If it reaches the threshold, it can jump out of the particle swarm optimization process. If the iteration T _m times is not reached, it also jumps out of the particle swarm optimization process. process of optimization.

Preset two integers M1 and M2 greater than or equal to 3. If the global optimal point p _g is updated for M1 consecutive iterations during the iterative update process, it means that the current particle swarm is in the process of continuously developing a new state, then Appropriately reduce the number of particles, such as reducing the number of particles by 1; on the contrary, if the global optimal point has not been updated for M2 consecutive iterations, the particle swarm is in a convergent state at this time, and may fall into the local optimal point and cannot jump out, that is, the target The position may not be tracked accurately. At this time, it is necessary to increase the number of particles, such as adding 1 to the number of particles, so as to help the particle swarm jump out of this point and expand the search range. Jump out of the particle swarm optimization process. The values of M1 and M2 can be set according to the actual situation, and they can be the same or different. In this embodiment, the values of both are the same, both being T.

After jumping out of adaptive particle swarm optimization:

It is necessary to recalculate the weight of the particles and normalize the weight.

Estimation of the state: According to the position and weight of the particle, estimate the position of the target. And the estimated target position is displayed for easy identification. Next, it is judged whether it is the end frame, if it is, the tracking ends, if not, it enters the tracking process of the next state, and goes to the state transition step.

According to the above description, it can be seen that in the adaptive particle swarm optimization particle filter algorithm of the present invention, resampling is unnecessary, because after particle swarm optimization, the particles tend to be at the optimal point, and there will be no weight concentration on a certain point. top of several particles.

In order to verify the effect of the present invention, the following verification experiment has been carried out: select three different video sequences (Browse1, Fight_RunAway1 from http://homepages.inf.ed.ac.uk/rbf/CAVIARDATA1, Aircraft is a commonly used aircraft tracking Sequence), adopt the particle filter algorithm of 200 particles and the method of the present invention of 30 particles to track the target respectively, and carry out the time statistics of tracking processing (that is, the time spent on processing one frame on average). The obtained experimental results are shown in Table 1, wherein PF represents the particle filter algorithm, and APSOPF represents the method of the present invention.

Table 1 Comparison of the results of the verification experiment

video sequence PF (200 particles) APSOPF (30 particles) time saver Browse1 0.3284s 0.2120s 35.44% Fight_RunAway1 0.3946s 0.2429s 38.44% Aircraft 0.3735s 0.2264s 39.38%

Figure 4 shows the comparison between the time-varying curve of the tracking target's position coordinates (in pixels) in the Browse1 video sequence estimated by the two methods and the actual state curve. It can be seen from FIG. 4 that the target tracking accuracy of the method of the present invention is obviously better than that of the traditional particle filter target tracking method.

Claims (5)

1. adaptive particle swarm optimization particle filter motion target tracking method, is carrying out in the tracing process of moving target with particle filter method, utilize the position of particle group optimizing method to particle to be optimized; It is characterized in that, when the position utilizing particle group optimizing method to particle is optimized, change in location situation according to global optimum's particle carries out self-adaptative adjustment to the quantity of particle, specific as follows: the position as global optimum's particle changes all the time in continuous N 1 iteration, then reduce number of particles; Position as global optimum's particle is constant all the time in continuous N 2 iteration, then increase number of particles; M1, M2 be default be more than or equal to 3 integer.

2. adaptive particle swarm optimization particle filter motion target tracking method as claimed in claim 1, it is characterized in that, M1 equals M2.

3. adaptive particle swarm optimization particle filter motion target tracking method as claimed in claim 1, is characterized in that, the number of particles that each institute increases or reduces is 1.

4. adaptive particle swarm optimization particle filter motion target tracking method as claimed in claim 1, it is characterized in that, carrying out in the tracing process of moving target with particle filter method, the feature used is color histogram.

5. adaptive particle swarm optimization particle filter motion target tracking method as claimed in claim 4, is characterized in that, uses the similarity of Pasteur's distance metric color histogram.