﻿ 基于DE蝙蝠算法优化粒子滤波的目标跟踪
 计算机系统应用  2019, Vol. 28 Issue (2): 24-32 PDF

Target Tracking Based on DE Bat Algorithm for Particle Filter Optimization
LI Long-Long, ZHOU Wu-Neng, LYU Si-Yao
School of Information Science and Technology, Donghua University, Shanghai 201620, China
Foundation item: National Natural Science Foundation of China (61573095)
Abstract: In the field of target tracking, particle filter technology has the advantage of dealing with nonlinear non-Gaussian problems. However, when the standard particle filter solves the degradation phenomenon by using the resampling method, the particle depletion problem will occur, resulting in unstable filter precision. To solve this problem, the algorithm uses the differential evolution bat algorithm to improve the particle filter. In this study, the particle is characterized as a bat individual. The bat population adjusts the frequency, loudness, and pulse emissivity, and the current optimal bat individual searches in the target image area, and can dynamically decide whether to use global search or local search to improve the particle. The overall quality and reasonable distribution; the introduction of differential evolution strategies can enhance the ability of bat individuals to jump out of local optimum. In order to verify the optimization performance of the proposed algorithm, the performances of the proposed algorithm and the standard particle filter algorithm are compared. Experimental results show that the filter performance of the proposed algorithm is better than the standard particle filter algorithm.
Key words: particle filter     particle depletion     bat algorithm     differential evolution     target tracking

1 引言

2 基本的粒子滤波算法

 $w_t^i = w_{t - 1}^i\frac{{{p} \left( {\left. {{z_t}} \right|x_t^i} \right){p} \left( {\left. {x_t^i} \right|x_{t - 1}^i} \right)}}{{{q} \left( {\left. {x_t^i} \right|x_{t - 1}^i,{z_t}} \right)}}$ (1)

3 蝙蝠算法

(1)蝙蝠种群都通过回声定位来获得距离, 并使用某种特殊的方法“明白”目标和非目标两者之间存在的不同特征点;

(2)蝙蝠在位置xi处伴随着速度vi以一定的速度飞行频率和响度来搜寻目标. 他们可以自动调节发射脉冲的波长(或频率), 并根据目标的接近程度调节脉冲发射速率.

(3)虽然响度可以按照多种方式变化, 但是通常是假设响度从大(正)A0变化到最小设定数Amin.

4 蝙蝠算法融合差分进化算法DEBA

Step 1. 初始化DEBA算法各个参数;

Step 2. 根据蝙蝠个体适应度函数得到各个蝙蝠权重和初始种群当前最优解;

Step 3. 模拟蝙蝠种群的全局搜索寻优行为, 根据本文中的等式(4)–(6)更新各个蝙蝠个体的对应的位置和速度;

Step 4. 模拟蝙蝠个体的局部搜索行为, 以及对应生成一个均匀分布的随机数 $rand$ , 如果存在 $rand > {r_i}$ 的情况, 则下一步将进行式(7);

Step 5. 生成另外一个独立的随机数, 若 $rand < A_i^g$ $I\left( {x_i^g} \right) > I\left( {x_i^{g + 1}} \right)$ , 则蝙蝠当前的位置为 $x_i^g$ , 否则蝙蝠的当前位置为 ${x_{\rm{new}}}$ ;

Step 6. 对蝙蝠的局部搜索能力进行调整, 利用式(9)更新脉冲频率和响度;

Step 7. 利用差分进化算法以每一个蝙蝠位置为初始点进行变异、交叉、选择操作, 得到新的蝙蝠位置;

Step 8. 计算并对比适应度函数值, 更新全局最优值;

Step 9. 当算法符合设定的精度阈值 $\varepsilon$ 时, 或者迭代次数达到设定值时, 这个时候就停止算法优化过程, 否则就要进入Step 3.

5 本文算法目标灰度描述和目标函数设计

 ${p} _x^u = \frac{{\displaystyle\sum\nolimits_{i = 1}^M {{k} \left( {\left\| {\frac{{X - {X_i}}}{h}} \right\|} \right)} \delta \left( {{b} \left( {{X_i}} \right) - u} \right)}}{{\displaystyle\sum\nolimits_{i = 1}^M {{k} \left( {\left\| {\frac{{X - {X_i}}}{h}} \right\|} \right)} }}$ (2)

 ${I} = \exp \left[ { - \frac{1}{{2{R_g}}}\left( {{z_{\rm{New}}} - {z_{\rm{Pred}}}\left( i \right)} \right)} \right]$ (3)
6 DEBA-PF算法设计 6.1 DEBA-PF全局搜索最优过程

 ${f_i} = {f_{\min }} + \left( {{f_{\max }} - {f_{\min }}} \right){\bf{\beta }}$ (4)
 $v_i^{g + 1} = v_i^g + \left( {x_i^g - {x^*}} \right){f_i}$ (5)
 $x_i^{g + 1} = x_i^g + v_i^{g + 1}$ (6)

6.2 DEBA-PF局部搜索最优过程

$rand > {r_i}$ , 则

 ${x_{\rm{new}}} = {x_{\rm{old}}} + \varepsilon {A^g}$ (7)

$rand < {r_i}$ , 则

 ${x_{\rm{new}}} = x_i^{g + 1}$ (8)

6.3 DEBA-PF全局和局部搜索寻优调整过程

 $A_i^{g + 1} = \omega A_i^g{\rm{,r}}_i^{g + 1} = r_i^0\left[ {1 - \exp \left( { - \gamma t} \right)} \right]$ (9)

 $A_i^g \to 0,r_i^g = r_i^0,{\text{当}}g \to \infty$ (10)

 ${v_{ij}}\left( t \right) = x_a^g\left( t \right){\text{ + }}F\left( {x_b^g\left( t \right) + x_c^g\left( t \right)} \right)$ (11)

 $u_{ij}^{g + 1}\left( t \right) = \left\{ {\begin{array}{l} {v_{ij}^g\left( t \right),\;\; {\rm{if}}\;\;\left( {rand\left( {0,1} \right)} \right) \leqslant CR} \\ \quad\quad\quad{{\rm{or}} \;\;j = rand\left( {1,n} \right)} \\ {x_{ij}^g\left( t \right),\;\;{\rm{if}}\;\;\left( {rand\left( {0,1} \right)} \right) > CR} \\ \quad\quad\quad{{\rm{or}}\;\; j \ne rand\left( {1,n} \right)} \end{array}} \right.$ (12)

 $x_i^{g + 1}\left( t \right)= \left\{ {\begin{array}{l} {u_{ij}^{g + 1}\left( t \right),\;\;{\rm{if}}\;\;\left( {f\left( {u_{ij}^{g + 1}\left( t \right)} \right) < f\left( {x_i^g\left( t \right)} \right)} \right)} \\ {x_i^g\left( t \right),\;\;{\rm else}} \end{array}} \right.$ (13)
7 本文算法步骤

Step 1. 输入初始的测试图像, 并设定所要进行跟踪的目标对象;

Step 2. 随机生成N个蝙蝠个体 $\left\{ {{x_i}\left( 0 \right),i = 1,\cdots,N} \right\}$ 作为算法的初始蝙蝠个体, 初始化DEBA-PF算法参数. ${x_i}\left( t \right)$ 服从重要性密度函数:

 ${x_i}\left( t \right) \sim {q} \left[ {\left. {{x_i}\left( t \right)} \right|{x_i}\left( {t - 1} \right),z\left( t \right)} \right]$ (14)

Step 3. 计算蝙蝠个体的灰度直方图特征;

Step 4. DEBA算法操作;

Step 5. 计算重要性权值:

 $w_i^t \approx w_i^{t - 1}p\left( {\left. {{z^g}} \right|x_i^g} \right)$ (15)

Step 6. 进行归一化:

 $w_i^t = {{w_i^t}/{\sum\nolimits_{i = 1}^N {w_i^t} }}$ (16)

Step 7. 根据蝙蝠权值大小重采样, 得到N个新样本;

Step 8. 状态输出, 对新样本求平均确定跟踪点:

 ${\tilde x_t} = \sum\nolimits_{i = 1}^N {w_i^tx_i^g}$ (17)

8 仿真实验和结果分析 8.1 性能测试分析

 $\begin{split} {{x}}\left( t \right) = & 0.5{{x}}\left( {t - 1} \right) + \frac{{25{{x}}\left( {t - 1} \right)}}{{1 + {{\left[ {{{x}}\left( {t - 1} \right)} \right]}^2}}} \\ &+ 8\cos \left[ {1.2\left( {t - 1} \right)} \right] + {n_{et}}\left( t \right) \end{split}$ (18)

 ${{z}}\left( t \right) = \frac{{{{x}}{{\left( t \right)}^2}}}{{20}} + {w_{et}}\left( t \right)$ (19)

 ${R_{\rm{MSE}}} = {\left[ {\frac{1}{T}{{\sum\nolimits_{T - 1}^T {\left( {{{{x}}_t} - {{{{\hat x}}}_t}} \right)} }^2}} \right]^{\frac{1}{2}}}$ (20)

(1)当蝙蝠数为N=20、Q=10时, 仿真结果如图1所示.

(2)当蝙蝠数为N=50、Q=10时, 仿真结果如图2所示.

(3)当蝙蝠数为N=100、Q=10时, 仿真结果如图3所示.

(4)当蝙蝠数为N=20、Q=1时, 仿真结果如图4所示.

(5)当蝙蝠数为N=50、Q=1时, 仿真结果如图5所示.

(6)当蝙蝠数为N=100、Q=1时, 仿真结果如图6所示.

 图 1 N=20、Q=10时滤波状态估计图和误差绝对值

 图 2 N=50、Q=10时滤波状态估计图和误差绝对值

 图 3 N=100、Q=10时滤波状态估计图和误差绝对值

 图 4 N=20、Q=1时滤波状态估计图和误差绝对值

 图 5 N=50、Q=1时滤波状态估计图和误差绝对值

 图 6 N=100、Q=1时滤波状态估计图和误差绝对值

8.2 目标跟踪测试

 图 7 标准粒子滤波跟踪结果1(第50、60、70、80、90、100帧)

 图 8 差分进化蝙蝠算法跟踪结果1(第50、60、70、80、90、100帧)

 图 9 标准粒子滤波算法跟踪结果2(第20、30、40、50、60、70帧)

 图 10 差分进化蝙蝠算法跟踪结果2(第20、30、40、50、60、70帧)

 图 11 标准粒子滤波跟踪结果3(第50、60、70、80、90、100帧)

 图 12 差分进化蝙蝠算法跟踪结果3(第50、60、70、80、90、100帧)

9 结语

 [1] Yilmaz A, Javed O, Shah M. Object tracking: A survey. ACM Computing Surveys, 2006, 38(4): 13. DOI:10.1145/1177352 [2] Mekonnen AA, Lerasle F, Herbulot A. Cooperative passers-by tracking with a mobile robot and external cameras. Computer Vision and Image Understanding, 2013, 117(10): 1229-1244. DOI:10.1016/j.cviu.2012.12.004 [3] Xu BL, Lu ML. An ant-based stochastic searching behavior parameter estimate algorithm for multiple cells tracking. Engineering Applications of Artificial Intelligence, 2014, 30: 155-167. DOI:10.1016/j.engappai.2013.11.010 [4] Tian CN, Gao XB, Wei W, et al. Visual tracking based on the adaptive color attention tuned sparse generative object model. IEEE Transactions on Image Processing, 2015, 24(12): 5236-5248. DOI:10.1109/TIP.2015.2479409 [5] Ait Abdelali H, Essannouni F, Essannouni L, et al. Fast and robust object tracking via accept–reject color histogram-based method. Journal of Visual Communication and Image Representation, 2016, 34: 219-229. DOI:10.1016/j.jvcir.2015.11.010 [6] Comaniciu D, Ramesh V, Meer P. Kernel-based object tracking. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2003, 25(5): 564-577. DOI:10.1109/TPAMI.2003.1195991 [7] Sun X, Yao HX, Lu XS. Dynamic multi-cue tracking using particle filter. Signal, Image and Video Processing, 2014, 8(S1): 95-101. DOI:10.1007/s11760-014-0674-z [8] Mazinan AH, Amir-Latifi A. Applying mean shift, motion information and Kalman filtering approaches to object tracking. ISA Transactions, 2012, 51(3): 485-497. DOI:10.1016/j.isatra.2012.02.002 [9] Ait Abdelali H, Essannouni F, Essannouni L, et al. An adaptive object tracking using Kalman filter and probability product kernel. Modelling and Simulation in Engineering, 2016, 2016: 2592368. [10] Yi SY, He ZY, You XG, et al. Single object tracking via robust combination of particle filter and sparse representation. Signal Processing, 2015, 110: 178-187. DOI:10.1016/j.sigpro.2014.09.020 [11] 张琪, 胡昌华, 乔玉坤. 基于权值选择的粒子滤波算法研究. 控制与决策, 2008, 23(1): 117-120. Zhang Q, Hu CH, Qiao YK. Particle filter algorithm based on weight selected. Control and Decision, 2008, 23(1): 117-120. DOI:10.3321/j.issn:1001-0920.2008.01.026 [12] Li TC, Sattar TP, Sun SD. Deterministic resampling: Unbiased sampling to avoid sample impoverishment in particle filters. Signal Processing, 2012, 92(7): 1637-1645. DOI:10.1016/j.sigpro.2011.12.019 [13] Stano PM, Lendek Z, Babuška R. Saturated particle filter: Almost sure convergence and improved resampling. Automatica, 2013, 49(1): 147-159. DOI:10.1016/j.automatica.2012.10.006 [14] Yu YH, Zheng XY. Particle filter with ant colony optimization for frequency offset estimation in OFDM systems with unknown noise distribution. Signal Processing, 2011, 91(5): 1339-1342. DOI:10.1016/j.sigpro.2010.12.009 [15] Zhong J, Fung YF. Case study and proofs of ant colony optimisation improved particle filter algorithm. IET Control Theory & Applications, 2012, 6(5): 689-697. [16] Xian WM, Long B, Li M, et al. Prognostics of lithium-ion batteries based on the verhulst model, particle swarm optimization and particle filter. IEEE Transactions on Instrumentation and Measurement, 2014, 63(1): 2-17. DOI:10.1109/TIM.2013.2276473 [17] Leinonen M, Codreanu M, Juntti M. Distributed joint resource and routing optimization in wireless sensor networks via alternating direction method of multipliers. IEEE Transactions on Wireless Communications, 2013, 12(11): 5454-5467. DOI:10.1109/TWC.2013.100213.121227 [18] 邱雪娜, 刘士荣, 吕强. 基于信息分享机制的粒子滤波算法及其在视觉跟踪中的应用. 控制理论与应用, 2010, 27(12): 1724-1730. Qiu XN, Liu SR, Lü Q. Particle filter algorithm based on information-shared mechanism and its application to visual tracking. Control Theory & Applications, 2010, 27(12): 1724-1730. [19] 田梦楚, 薄煜明, 陈志敏, 等. 萤火虫算法智能优化粒子滤波. 自动化学报, 2016, 42(1): 89-97. Tian MC, Bo YM, Chen ZM, et al. Firefly algorithm intelligence optimized particle filter. Acta Automatica Sinica, 2016, 42(1): 89-97. [20] Yang XS. A new metaheuristic bat-inspired algorithm. González JR, Pelta DA, Cruz C, et al. Nature Inspired Cooperative Strategies For Optimization. Berlin, Heidelberg: Springer, 2010. 65–74. [21] 陈志敏, 田梦楚, 吴盘龙, 等. 基于蝙蝠算法的粒子滤波法研究. 物理学报, 2017, 66(5): 050502. Chen ZM, Tian MC, Wu PL, et al. Intelligent particle filter based on bat algorithm. Acta Physica Sinica, 2017, 66(5): 050502. [22] Neuimin OS, Zhuk SY. Sequential detection of target trajectory tracking loss using the decision statistics of pips. Radioelectronics and Communications Systems, 2014, 57(8): 352-361. DOI:10.3103/S0735272714080032 [23] Son HS, Park JB, Joo YH. Segmentalized FCM-based tracking algorithm for zigzag maneuvering target. International Journal of Control, Automation and Systems, 2015, 13(1): 231-237. DOI:10.1007/s12555-013-0406-0 [24] Storn R, Price K. Differential evolution–a simple and efficient heuristic for global optimization over continuous spaces. Journal of Global Optimization, 1997, 11(4): 341-359. DOI:10.1023/A:1008202821328