粒子滤波的重采样方法
V o l . 34, N o. 10
O ct, 2009
火力与指挥控制
F ire Contro l &Comm and Contro l
第34卷 第10期2009年10月
文章编号:100220640(2009) 1020018203
粒子滤波的重采样方法3
张 淼, 胡建旺, 周云锋, 童 俊
(军械工程学院, 河北 石家庄 050003)
摘 要:粒子滤波是基于递推的M onte Carlo 仿真方法的总称, 原则上可用于任意非线性、非高斯随机系统的状态估计。但粒子的退化现象是粒子滤波器的最大缺陷, 减轻这一现象影响的方法之一就是对粒子进行重采样。阐述了几种重要的重采样算法及其改进策略, 并对其进行总结与展望。
关键词:粒子滤波, 粒子退化, 重采样中图分类号:T P 14 文献标识码:A
Overv iew of Resam pli ng A lgor ith m
ZHAN G M iao , HU J ian 2w ang , ZHOU Yun 2feng , TON G Jun
(O rd nance E ng ineering Colleg e , S h ij iaz huang 050003, Ch ina )
Abstract :Particle filtering is a sequen tial M on te si m lati , rinci p le , it can be
u sed in esti m ating the state of any non linear o r non 21t defect in the p resen t p article filtering is p article degeneracy , in o , the resam p le strategy is adop ted 1T h is article in troduces their m odified strategy and m akes a conclu si on and p ro spect 1
Key words :, te si m u lati on , resam p le
引 言
在现代信号处理、图像处理、计算机视觉及自动控制领域存在着大量的非线性非高斯随机情况。系统的概率分布函数不再具有高斯特征, 而且其真正的概率分布函数的解析形式也不易得到, 即使知道它的解析解, 但求其统计量仍面临高维积分问题, 不便于计算[1]。因此传统的卡尔曼滤波器已不能完成滤波任务, 自从1979年由A nderson 和M oo re [2]提出EKF (扩展的卡尔曼滤波) 后, 它便成为解决非线性问题的一个最普遍的次优滤波方法。然而EKF 仅仅是利用非线性函数的泰勒展开的一阶项, 当系统的非线性度较高或泰勒展开的高阶项对系统影响较大时, EKF 的性能变得很差甚至会导致滤波发散。为减少近似带来的误差, Ju lier , et al 提出了
[3]
U KF , 用确定的样本点获得高斯随机变量完全的
收稿日期:2008210227 修回日期:[1**********]基金项目:国家自然科学基金资助项目
作者简介:张 淼(19832 ) , 女, 山西太原人, 在读硕士研
究生, 研究方向:多传感器数据融合。
统计特性, 其精度相当于二阶EKF , 同时也避免了对雅各比矩阵的计算, 但在非高斯情况下, 这种基于高斯假设的方法在估计系统状态和方差时的误差仍然很大, 并有可能引起发散。
为解决非线性、非高斯环境下的滤波问题, 其实在20世纪50年代, 就出现了一种被称为“序贯重要
[4]
性采样(S IS ) ”的M on te Carlo 方法, 然而由于高度的计算复杂性和退化问题, 相当长一段时间内S IS 算法没有多大进展, 直到1993年Go rdon 提出了重采样概念[5], 克服了早期算法的退化问题, 这才出现了第一个可操作的M on te Carlo 滤波器。之后随着计算技术的迅速发展, M on te Carlo 滤波方法也迅速发展起来并被通称为粒子滤波(PF ) , 其基本思想是:通过对一组随机采样的加权粒子演化与传播来递推近似状态的后验概率密度函数, 从而获得其他关于状态的统计量, 原则上可用于任意非线性、非高斯随机系统的状态估计[6]。
由此可见, 粒子的退化现象是粒子滤波器的最大缺陷, 制约着粒子滤波器的发展, 解决粒子退化问题的有效方法之一就是对粒子进行重采样, 本文将对现有的各种重采样方法及其改进算法进行阐述,
张 淼, 等:粒子滤波的重采样方法
(总第34-1553) ・19・
并对其发展作进一步的展望。
112 残差重采样
1 重采样算法
111 重要性重采样
重要性重采样的主要思想:一旦退化现象明显
发生(比如说N δef f =N 低于某个阈值) , 在重
∑(Κk i ) 2
i =1
残差重采样是在1998年由L iu 等人提出的[8], 是在重要性重采样基础上提出的。算法步骤如下[9]:
θ1, …, Ξθn ) 得到:Step 1:由M u lt (n -R ; Ξ
{i }1≤i ≤n , 其中{N
i i
i θR =∑[n Ξ],Ξ=i =1n -R
i =1, …, n , []表示取整
i i {i
Step 2:令N =[n Ξ]+N
i
Step 3:Ξ=1 n , i =1, …, n
最近, 由王[10]等人提出了一种粒子滤波硬件实现时的快速残差采样策略, 引入动态基准位置和动
[11, 12]
态阈值位置, 将“粒子—标签”残差采样的高效定点实现方法进行扩展, 使其可以直接对非归一化的权值进行采样, 从而免去了需进行大量除法运算的权值归一化操作, 提高了粒子的实时性。113 分层重采样算法
年由Carpen ter 等, 将无序的随:
将(0, 1]分成n 个连续互不重合的区间, (0, 1]=(0, 1 n ) ∪…∪({n -1} n , 1) ]
i
Step 2:对每个子区间独立同分布采样得到U s , 即U i =U ([{i -1} n , i n ])
i
n
要性采样的基础上加入重采样, 以淘汰权值低的粒
子, 而集中于权值高的粒子, 从而抑制退化现象。其过程是:对于给定的概率密度函数的近似离散表示
N
k
p (x k Z ) ≈
∑Κ
i =1
k i
(i )
(i ) k ) ∆(x k -x
()
(1)
i
重采样方法是对每个粒子x 按其权值生成k
N i 个副样本, 并使得
∑N
=N , 若有N i =0, 则该
粒子被淘汰。简单地说就是复制权值大的样本, 淘汰权值小的样本。通过重采样, 最后产生一个新的样本
() (j ) δ(i ) (i )
集合{x δk i }N 事实上, 产生i =1, 于是P (x k =x k ) =Κk 。的样本是一个独立、同分布的样本集, 而且每个粒子的权值均置为1 N 。
性重采样粒子滤波算法, i
p (x k x k -1) [7]:
Step 1:对于t =i , 根据标准粒子滤波算法从重要性概率密度函数q (X k Z k ) 中采样得到支撑点集i i i x 0:k , 计算权值Ξk =p (z k x k ) ;
N s
i i i
k ; Step 2:计算归一化权值:Ξk =Ξk Ξi =1
Step 3:按重要性重采样法进行。
δ(j ) δk (j ) , i (j ) }N
Step 3:重采样:[{x k , Κj =1]=
[1]i N i
R ESAM PL E [{x k , Κk }i =1]
()
()
∑
①初始化。累积分布函数cdf :c 0=0
(i )
②FOR i =1, 2, 3, …, N ; C i =c i -l +Κk END FOR
③由cdf 的底部开始启动:i =1抽取起始点:u 0~U [0, 1 N ]。FOR j =1, 2, …, N
沿cdf 移动:u j =u l +(j -1) N W H I L E u j >c i , i =i +1 END W H I L E ;
(i )
设定样本x δk (j ) =x k ;
δk (j ) =1 设定权值ΚN ; (j )
设定父代i =i 。END FOR
Step 4:返回到第一步。
分层重采样法由于把粒子限定在不同区间内, 保证了粒子的多样性, 改善了重要性重采样方法中引起的粒子匮乏的现象。114 优化组合重采样
优化组合重采样法是由邹[13]等人, 主要是针对粒子多样性减少而引起的粒子匮乏现象而提出的。其主要思想是充分利用小权值的粒子, 在需要复制某个采样点的时候, 通过采样点和被抛弃的采样点进行适当的线性组合而产生出一个新的采样点。线性组合方式为:
(2) ςn =ςs +KL (ςa -ςs ) 其中:ςn 为产生的新样本点; ςs 为被复制的点;
ςa 为被抛弃的点; K 为步长系数; L 为步长。
该算法的优点:不存在重复的粒子, 增加了粒子的多样性; 使得被抛弃的小权值粒子仍然以一定的概率存在对状态的估计中; 选择合适的K 值, 可以提高PF 算法精度。
2 结束语
重采样算法是解决粒子滤波中粒子退化现象的可行方法之一, 许多改进的重采样方法也相继被提
(总第34-・20・
1554) 火力与指挥控制2009年 第10期
出, 并且在滤波过程中改善了PF 的性能, 文中介绍的重采样方法的计算量都为O (N ) , 分层重采样算法的性能略优于重要性重采样和残差重采样。经典的重采样方法在克服粒子匮乏方面取得了良好的效果, 但是以牺牲计算量和鲁棒性换来的, 使粒子滤波这一新算法的可实现性成为主要问题。当然, 粒子滤波作为近年来新涌现的算法, 虽然算法本身还不成熟, 但它在解决非线性、非高斯问题的参数估计和状态滤波方面有着独到的优势, 因此有很大的发展空间, 可以将成熟的多种不同的寻优方法引入重采样过程, 以便更快地提取到反映系统概率特征的典型“粒子”, 逐渐成为重采样方法的研究重点[14], 当然, 要针对硬件的实现这一至关重要的实际问题, 发展一些“快速”的重采样算法, 减轻电路的负荷以提高实时性。参考文献:
[1][2][3]
M onte Carlo [J ]. J of the Royal Statistical Society B , 1954, 16(1) :232381. [5]
Go rdon N , Sal mond D . N ovel A pp roach to N on 2lineal and N on 2Gaussian Bayesian State E sti m ati ons [J ]. P roc of Institute E lectric Engineering , 1993, 140(2) :1072113.
[6][7]
夏克寒, 许化龙. 粒子滤波的关键技术及应用[J ]. 电光与控制, 2005, 25(6) :124.
刘维亭, 戴晓强. 基于重要性采样粒子滤波器的机动目标跟踪方法[J ]. 江苏科技大学学报, 2007, 21(1) :
37241.
L iu J S , Chen R . Sequential M onte 2Carlo M ethods fo r D ynam ic System s [J ]. J of theAm erican Statistical A ssociati on . 1998, 93(443) :103221044.
[8]
[9]
王来雄, 陈养平. 粒子滤波硬件实现的快速残差再采样策略[J ]. 信号处理, 2007, 30(1) :972100.
of Particle F ilters [D ]. Ph . D . D issertati on , Stste . U niversity of N ew Yo rk B rook , 2004
[10]Bo lic M . A rch itectures fo r Efficient I mp lem entati on
韩崇昭, 朱洪艳. 多源信息融合[M ]. 北京:清华大学出版社, 2006.
A nderson B D , M oo re J B . Op ti m al F iltering [M ]. . N ew Jersey :P rentice 2H all , 1999
Julier S J , U h l m ann J K . A General M r A pp roxi m ating
N onlinear
T ons
P robability D G of . , U of O rd , 1996
[11]S , n Efficient F ixed 2po int
I mp of ling Schene fo r igh F ilters [J ]. IEEE Signal P rocess
, 11(5) :4822485. ][13]
邹国辉, 敬忠良. 基于优化组合重采样的粒子滤波算法[J ]. 上海交通大学学报, 2006, 50(7) :113521139. 胡士强, 敬忠良. 粒子滤波算法综述[J ]. 控制与决策, 2005, 19(4) :3612365.
[4]H amm E rsl E , M o K W . Poo r m anp ’s
(上接第17页)
5 结 论
本文针对红外序列图像中运动弱小点目标的检测跟踪问题提出了一种分组序贯的思想, 并形成了一种点目标检测跟踪方法——多组独立检测法。实验结果证明分组序贯的思想可以有效地检测跟踪信噪比较低的点目标, 具有较高的检测概率。参考文献:
[1]
R eed I S , Gagliardi R M , Sto tts L B . Op ticalM oving T arget D etecti on w ith 32D M atched F iltering [J ]. IEEE T ransacti ons on A ES , 1988, 24(4) :3272336.
[2]
Cox I J , H ingo rani S L . A n Efficient I mp lem entati on of R eid’sM ulti p le H ypo thesis T rack ing A lgo rithm and its Evaluati on fo r the Purpo se of V isual T rack ing .
Pattern
A nalysis
and
M ach ine
Intelligence [J ]. IEEE T ransacti ons on , 1996, 18(2) :1382150.
[3]
Chu P L . Op ti m al P ro jecti on fo r M ultidi m ensi onal
[4]
Signal P rocessing , I CA SSP 288, 1988, 5:279722800.
B lackm an S S . M ulti p le H ypo thesis T rack ing fo r M ulti p le T arget T rack ing [J ]. IEEE A ero space and E lectronic System s M agazine , 2004, 19(1) :5218.
[5]O bata Y , Ito M , Ko suge Y . Perfo r m ance Evaluati on of T rack O riented M H T
in
Sp litting T arget
T rack ing [C ] P roceedings of the 41st S I CE
[6]
A nnual Conference , 2002:6192624.
de W aard H W . A n I mp roved C lustering Concep t fo r
M H T
A pp licati ons .
T arget
T rack ing :
A lgo rithm s and A pp licati ons [J ]. IEEE , 2001, 1(10) :16217. [7]
李红艳, 吴成柯. 一种快速序列图像低信噪比点目标的检测与跟踪方法[J ]. 西安电子科技大学学报, 1999, 44(6) :225.
张天序, 戴可荣, 彭嘉雄. 复杂图像序列的自适应目标提取和跟踪方法[J ]. 电子学报, 1994, 24(10) :222
24.
彭嘉雄, 周文琳. 红外背景抑制与小目标分割检测[J ]. 电子学报, 1999, 27(12) :17218.
[8]
[9][10]
张 弘, 赵保军, 史彩成. 对低信噪比下的红外点目标高检测率的研究[J ]. 系统工程与电子技术, 2001, 23(3) :58260.
Signal D etecti on [C ] A coustics , Speech , and