﻿ 用于目标跟踪的智能群体优化滤波算法
«上一篇
 文章快速检索 高级检索

 智能系统学报  2019, Vol. 14 Issue (4): 697-707  DOI: 10.11992/tis.201805049 0

### 引用本文

XU Qi, WANG Huabin, ZHOU Jian, et al. Swarm intelligence filtering for robust object tracking[J]. CAAI Transactions on Intelligent Systems, 2019, 14(4): 697-707. DOI: 10.11992/tis.201805049.

### 文章历史

Swarm intelligence filtering for robust object tracking
XU Qi , WANG Huabin , ZHOU Jian , TAO Liang
Key Laboratory of Intelligent Computing and Signal Processing of Ministry of Education, Anhui University, Hefei 230031, China
Abstract: To estimate the state of target in object tracking, a novel algorithm named swarm intelligence filter (SIF) is proposed in this paper. Based on the Bayesian filter, the algorithm could estimate the posterior state using three movements of swarms. The cohesion movement could add the weight by maintaining the diversity of the sample, and the coordination of separation and permutation movements could more accurately predict the state of the next moment compared with the conventional algorithm. The experimental results show that compared with the conventional particle filter, our algorithm could more accurately predict the posterior state in nonlinear systems and more accurately estimate the state of the object in complex environment.
Key words: object tracking    visual tracking    filtering algorithm    Bayesian filter    particle filter    motion model    posterior state    swarm intelligence optimization

1 贝叶斯滤波理论

 $\left\{ {\begin{array}{*{20}{l}} {{x_k} = f\left( {{x_{k - 1}}, {v_{k - 1}}} \right)} \\ {{{\textit{z}}_k} = h\left( {{x_k}, {n_k}} \right)} \end{array}} \right.$ (1)

1.1 预测过程

$p({x_{k - 1}}|{{\textit{z}}_{1:k - 1}})$ 得到系统在k时刻状态的先验滤波概率密度 $p({x_k}|{{\textit{z}}_{1:k}})$

 $\begin{gathered} p({x_k}, {x_{k - 1}}|{{\textit{z}}_{1:k - 1}}) = p({x_k}|{x_{k - 1}}, {{\textit{z}}_{1:k - 1}})p({x_{k - 1}}|{{\textit{z}}_{1:k - 1}})= \\ p({x_k}|{x_{k - 1}})p({x_{k - 1}}|{{\textit{z}}_{1:k - 1}}) \end{gathered}$ (2)

 $p({x_k}|{{\textit{z}}_{1:k - 1}}) = \int {p({x_k}|{x_{k - 1}})p({x_{k - 1}}|{{\textit{z}}_{1:k - 1}}){\rm{d}}{x_{k - 1}}}$ (3)

1.2 更新过程

 $\begin{gathered} p({x_k}|{{\textit{z}}_{1:k}}) = \frac{{p({{\textit{z}}_{1:k}}|{x_k})p({x_k})}}{{p({{\textit{z}}_{1:k}})}} {\frac{{p({{\textit{z}}_k}, {{\textit{z}}_{1:k}}|{x_k})p({x_k})}}{{p({{\textit{z}}_k}, {{\textit{z}}_{1:k - 1}})}}} = \\ {\frac{{p({{\textit{z}}_k}|{{\textit{z}}_{1:k - 1}}, {x_k})p({x_k}|{{\textit{z}}_{1:k - 1}})}}{{p({{\textit{z}}_k}|{{\textit{z}}_{1:k - 1}})}}} \\ \end{gathered}$ (4)

 $p({x_k}|{{\textit{z}}_{1:k}}) = \frac{{p({{\textit{z}}_k}|{x_k})p({x_k}|{{\textit{z}}_{1:k - 1}})}}{{p({{\textit{z}}_k}|{{\textit{z}}_{1:k - 1}})}}$ (5)

 $p({{\textit{z}}_k}|{{\textit{z}}_{1:k - 1}}) = \int {p({{\textit{z}}_k}|{x_k})p({x_k}|{{\textit{z}}_{1:k - 1}}){\rm{d}}{x_k}}$ (6)
2 智能群体优化滤波算法

 $p({x_k}|{{\textit{z}}_{1:k}}) \approx \frac{1}{N}\sum\limits_{i = 1}^N {\delta ({x_k} - x_k^i)}$ (7)

 $q({x_k}|{{\textit{z}}_{1:k}}) \approx \sum\limits_{i = 1}^N {\delta ({x_k} - x_k^i)w_k^*\left( {x_k^i} \right)}$ (8)

 $w_k^*(x_k^i) = \frac{{p({{\textit{z}}_{1:k}}|x_k^i)p(x_k^i)}}{{q(x_k^i|{{\textit{z}}_{1:k}})}}$ (9)

k时刻第i个粒子所对应的权值，由相应的观测模型[15]求出。则后验滤波概率密度：

 $p({x_k}|{{\textit{z}}_{1:k}}) = \frac{{q({x_k}|{{\textit{z}}_{1:k}})p({x_k}|{{\textit{z}}_{1:k}})}}{{q({x_k}|{{\textit{z}}_{1:k}})}}= { \frac{{q({x_k}|{{\textit{z}}_{1:k}})w_k^*({x_k})}}{{p({{\textit{z}}_{1:k}})}}}$ (10)

 $\begin{gathered} p({{\textit{z}}_{1:k}}) = \int {p({{\textit{z}}_{1:k}}, {x_k}){\rm{d}}{x_k}} =\\ { \int {\frac{{p({{\textit{z}}_{1:k}}|{x_k})p({x_k})q({x_k}|{{\textit{z}}_{1:k}})}}{{q({x_k}|{{\textit{z}}_{1:k}})}}} } {\rm{d}}{x_k}\approx \\ w_k^*({x_k})\sum\limits_{i = 1}^N {\int {w_k^*(x_k^i)} \delta ({x_k} - x_k^i){\rm{d}}{x_k}} = \\ w_k^*(x_k^i)\sum\limits_{i = 1}^N {w_k^*(x_k^i)} \end{gathered}$ (11)

 $\begin{gathered} p({x_k}|{{\textit{z}}_{1:k}}) = \frac{{w_k^*({x_k})\displaystyle\sum\limits_{i = 1}^N {w_k^*(x_k^i)\delta ({x_k} - x_k^i)} }}{{w_k^*(x_k^i)\displaystyle\sum\limits_{i = 1}^N {w_k^*(x_k^i)} }} =\\ \sum\limits_{i = 1}^N {\delta ({x_k} - x_k^i){w_k}(x_k^i)} \end{gathered}$ (12)

2.1 粒子分层

 ${\rm{layer}}({x_k}):\left\{ {\begin{array}{*{20}{l}} {x_k^i \in {\psi _h}, \quad{w_k^*(x_k^i) \geqslant {\tau _h}} } \\ {x_k^i \in {\psi _m}, \quad{{\tau _h} > w_k^*(x_k^i) \geqslant {\tau _l}}} \\ {x_k^i \in {\psi _l}, \quad {{\tau _l} > w_k^*(x_k^i)} } \end{array}} \right.$ (13)
2.2 粒子运动

2.2.1 内聚运动

 ${\rm{coh}}({x_k}):{x_k} = {x_{k - 1}} + \left( {a + (b - a) \times {\rm{rand}}} \right) \times ({x_{k - 1}} - {x_c})$ (14)

2.2.2 分离运动

 ${\rm{spa}}({x_k}):{x_k} = {x_{k - 1}} +{\textit{λ}} \times \bar v \times {\rm{rand}} \times ({x_c} - {x_{k - 1}})$ (15)

2.2.3 排列运动

 ${x_k}\sim p({x_k}|{x_{k - 1}})$ (16)

 ${x_k} = {x_{k - 1}} + {\textit{λ}} \times {\rm{rand}} \times \bar v$ (17)
2.3 状态估计

 $\hat x_k^{{\rm{MAP}}} = \mathop {\arg \max }\limits_{{x_k}} p({x_k}|{{\textit{z}}_{1:k}}) = \mathop {\arg \max }\limits_{{x_k}} {w_k}({x_k})$ (18)

1)局部最小均方误差(local minimum mean squared error，LMMSE)准则。

 $\hat x_k^{{\rm{LMMSE}}} = \int {{x_k}} p({x_k}|{{\textit{z}}_{1:k}}){\rm{d}}{x_k} = \sum\limits_{i = 1}^M {\left( {x_k^i{w_k}(x_k^i)} \right)} \in {\rm{R}}$ (19)

2)全局最小均方误差(global minimum mean squared error，GMMSE)准则。

 $\hat x_k^{{\rm{GMMSE}}} = \int {{x_k}} p({x_k}|{{\textit{z}}_{1:k}}){\rm{d}}{x_k} = \sum\limits_{i = 1}^N {x_k^i{w_k}(x_k^i)}$ (20)

2.4 状态更新

2.5 状态预测

2.6 算法流程

1) 初始化：设定粒子数N，阈值为mpts，threshold，threshold； ${x^i}\sim p\left( {{x_0}} \right) , {i = 1, 2,\cdots , N}$

2) for ${k = 1, 2, \cdots , T}$

3) 由观测函数计算每个粒子的权值 ${w_k}({x_k})$ 并分层： ${x_k}\sim {\rm{layer}}({x_k})$

4) 状态更新

 $\!\!\!\!\!\!\!\! \begin{array}{l} {\rm{if}}\left( {{\rm{length}}\left( {{\psi _h}} \right) > {\rm{threshold}}} \right)\\ \qquad {{\hat x}_k} =\displaystyle \sum\limits_{i = 1}^N {x_k^i} {w_k}\left( {x_k^i} \right)\\ {{\rm{elseif(length}}({\psi _h}) > {\rm{mpts}}}\\ \qquad {\& \& {\rm{length}}({\psi _m}) > {\rm{threshold}})}\\ \qquad {{\hat x}_k} = \displaystyle\sum\limits_{i = 1}^M {\left( {x_k^i{w_k}\left( {x_k^i} \right)} \right)} {x_k^i}, \in {\psi _h}\\ {{\rm{elseif(length}}({\psi _h}) > {\rm{mpts}}}\\ \qquad {\& \& {\rm{length}}({\psi _m}) < {\rm{threshold}})}\\ \qquad {{\hat x}_k} = \displaystyle\sum\limits_{i = 1}^M {\left( {x_k^i{w_k}\left( {x_k^i} \right)} \right)} {x_k^i}, \in {\psi _h}\\ \qquad {\psi _m}\sim {\rm{coh}}\left( {{{\hat x}_k}} \right)\\ {\rm{else}}\\ \qquad {{\hat x}_k} = \displaystyle\sum\limits_{i = 1}^M {\left( {x_k^i{w_k}\left( {x_k^i} \right)} \right)} , {x_k^i \in {\psi _m}}\\ {\rm{endif}}\\ {\psi _l}\sim {\rm{coh}}\left( {{{\hat x}_k}} \right) \end{array}$

5) 重新计算粒子的权值 ${w_k}\left( {{x_k}} \right)$ 并估计后验状态：

 ${\tilde x_k} = \sum\limits_{i = 1}^N {x_k^i} {w_k}\left( {x_k^i} \right)$

6) 状态预测

 $\begin{array}{l} {if({\rm{length}}({\psi _h}) < {\rm{mpts}}} \\ \qquad {\& \& {\rm{length}}({\psi _m}) < {\rm{threshold}})} \\ \qquad{x_k}\sim {\rm{spa}}\left( {{{\tilde x}_k}} \right) \\ {\rm{else}} \\ \qquad{x_k}\sim p({x_k}\left| {{x_{k - 1}}} \right.) \\ {\rm{endif}} \end{array}$

7) ${\rm{endfor}}$

3 实验结果与分析

3.1 仿真模拟实验

 \left\{ {\begin{aligned} & {{x_k} = {f_k}({x_{k - 1}}, k) + {v_{k - 1}}} \\ & {{{\textit{z}}_k} = \frac{{x_k^2}}{{20}} + {n_k}} \end{aligned}} \right. (21)

 ${f_k}({x_{k - 1}}, k) = \frac{{{x_{k - 1}}}}{2} + \frac{{25{x_{k - 1}}}}{{1 + x_{k - 1}^2}} + 8\cos (1.2k)$ (22)

 Download: 图 3 Monte Carlo仿真结果 Fig. 3 Results of Monte Carlo simulations

 ${\rm{RMSE}} = \sqrt {\frac{1}{T}\sum\limits_{k = 1}^T {{{({x_k} - {{\hat x}_k})}^2}} }$ (23)

3.2 智能群体优化滤波算法用于目标跟踪

 ${\tau _h} = \frac{1}{5}\sum\limits_{m = k - 5}^k {(\max w_m^*({x_m}) - \frac{1}{N}\sum\limits_{i = 1}^N {w_m^*(x_m^i)} )}$ (24)
 ${\tau _l} = \frac{1}{5}\sum\limits_{m = k - 5}^k {(\frac{1}{N}\sum\limits_{i = 1}^N {w_m^*(x_m^i)} - \min w_m^*({x_m}))}$ (25)

 $e = \sqrt {{{({x_t} - {x_s})}^2} + {{({y_t} - {y_s})}^2}}$ (26)

9种算法在各视频集中逐帧的中心误差如图4所示，其左上角标签栏为平均中心误差。定义重叠率(Overlap rate)为

 Download: 图 4 9种算法在各视频集上的中心误差 Fig. 4 Center error of 9 algorithms in each sequences
 ${\rm{score}} = \frac{{{\rm{area}}({R_t} \cap {R_s})}}{{{\rm{area}}({R_t} \cup {R_s})}}$ (27)

 Download: 图 5 9种算法在部分视频集中的实验结果截图 Fig. 5 Sampling tracking results of 9 trackers in some sequences
4 结束语

 [1] LGUENSAT R, TANDEO P, FABLET R, et al. Non-parametric Ensemble Kalman methods for the inpainting of noisy dynamic textures[C]//Proceedings of 2015 IEEE International Conference on Image Processing. Quebec City, Canada, 2016: 4288–4292. (0) [2] 王法胜, 鲁明羽, 赵清杰, 等. 粒子滤波算法[J]. 计算机学报, 2014, 37(8): 1679-1694. WANG Fasheng, LU Mingyu, ZHAO Qingjie, et al. Partilce filtering algorithm[J]. Chinese journal of computers, 2014, 37(8): 1679-1694. (0) [3] BAO Chenglong, WU Yi, LING Haibin, et al. Real time robust L1 tracker using accelerated proximal gradient approach[C]//Proceedings of 2012 IEEE Conference on Computer Vision and Pattern Recognition. Providence, USA, 2012: 1830–1837. (0) [4] ZHANG Kaihua, LIU Qingshan, WU Yi, et al. Robust visual tracking via convolutional networks without training[J]. IEEE transactions on image processing, 2016, 25(4): 1779-1792. (0) [5] WANG Dong, LU Huchuan. On-line learning parts-based representation via incremental orthogonal projective non-negative matrix factorization[J]. Signal processing, 2013, 93(6): 1608-1623. DOI:10.1016/j.sigpro.2012.07.015 (0) [6] 吴昊, 孙晓燕, 郭玉堂, 等. 保持粒子多样性的非退化粒子滤波方法研究[J]. 电子学报, 2016, 44(7): 1734-1741. WU Hao, SUN Xiaoyan, GUO Yutang, et al. Non-degeneracy particle filtering method research for particle diversity preserving[J]. Acta electronica sinica, 2016, 44(7): 1734-1741. DOI:10.3969/j.issn.0372-2112.2016.07.031 (0) [7] 常天庆, 李勇, 刘忠仁, 等. 一种改进重采样的粒子滤波算法[J]. 计算机应用研究, 2013, 30(3): 748-750. CHANG Tianqing, LI Yong, LIU Zhongren, et al. Particle filter algorithm based on improved resampling[J]. Application research of computers, 2013, 30(3): 748-750. DOI:10.3969/j.issn.1001-3695.2013.03.026 (0) [8] CAO Bei, MA Caiwen, LIU Zhentao. Particle filter with fine resampling for bearings-only tracking[J]. Procedia engineering, 2012, 29: 3685-3690. DOI:10.1016/j.proeng.2012.01.553 (0) [9] DU Kelin, SWAMY M N S. Swarm intelligence[M]//DU Kelin, SWAMY M N S. Search and Optimization by Metaheuristics. Cham: Birkhäuser, 2016. (0) [10] 彭喜元, 彭宇, 戴毓丰. 群智能理论及应用[J]. 电子学报, 2003, 31(S1): 1982-1988. PENG Xiyuan, PENG Yu, DAI Yufeng. Swarm intelligence theory and applications[J]. Acta electronica sinica, 2003, 31(S1): 1982-1988. (0) [11] CHENG Shi, ZHANG Qingyu, QIN Quande. Big data analytics with swarm intelligence[J]. Industrial management and data systems, 2016, 116(4): 646-666. DOI:10.1108/IMDS-06-2015-0222 (0) [12] XIA Junbo. Coverage optimization strategy of wireless sensor network based on swarm intelligence algorithm[C]//Proceedings of 2016 International Conference on Smart City and Systems Engineering. Hunan, China, 2016: 179–182. (0) [13] DEVI K U, SARMA D, LAISHRAM R. Swarm intelligence based computing techniques in speech enhancement[C]//Proceedings of 2015 International Conference on Green Computing and Internet of Things. Noida, India, 2015: 1199–1203. (0) [14] KRONANDER J, SCHÖN T B. Robust auxiliary particle filters using multiple importance sampling[C]//Proceedings of 2014 IEEE Workshop on Statistical Signal Processing. Gold Coast, Australia, 2014: 268–271. (0) [15] WANG Naiyan, SHI Jianping, YEUNG D Y, et al. Understanding and diagnosing visual tracking systems[C]//Proceedings of 2015 IEEE International Conference on Computer Vision. Santiago, Chile, 2015: 3101–3109. (0) [16] ARULAMPALAM M S, MASKELL S, GORDON N, et al. A tutorial on particle filters for online nonlinear/non-Gaussian Bayesian tracking[J]. IEEE Transactions on signal processing, 2002, 50(2): 174-188. DOI:10.1109/78.978374 (0) [17] ROSS D A, LIM J, Lin R S, et al. Incremental learning for robust visual tracking[J]. International journal of computer vision, 2008, 77(1/2/3): 125-141. (0) [18] WU Yi, LIM J, YANG M H. Online object tracking: a Benchmark[C]//Proceedings of 2013 IEEE Conference on Computer Vision and Pattern Recognition. Portland, USA, 2013: 2411–2418. (0) [19] JIA Xu, LU Huchuan, YANG M H. Visual tracking via adaptive structural local sparse appearance model[C]//Proceedings of 2012 IEEE Conference on Computer Vision and Pattern Recognition. Providence, USA, 2012: 1822–1829. (0) [20] ORON S, BAR-HILLEL A, LEVI D, et al. Locally orderless tracking[J]. International journal of computer vision, 2015, 111(2): 213-228. DOI:10.1007/s11263-014-0740-6 (0) [21] ZHANG Tianzhu, GHANEM B, LIU Si, et al. Robust visual tracking via multi-task sparse learning[C]//Proceedings of 2012 IEEE Conference on Computer Vision and Pattern Recognition. Providence, USA, 2012: 2042–2049. (0)