粒子滤波算法及其应用
本书系统介绍粒子滤波算法的基本原理和关键技术，针对标准粒子滤波算法存在的粒子退化、计算量大的缺点介绍了多种改进的粒子滤波算法，包括基于重要性密度函数选择的粒子滤波算法、基于重采样技术的粒子滤波算法、基于智能优化思想的粒子滤波算法、自适应粒子滤波算法、流形粒子滤波算法等，并将粒子滤波算法应用于机动目标跟踪、语音增强、传感器故障诊断、人脸跟踪等领域，最后探讨了粒子滤波算法的硬件实现问题，给出了基于DSP和FPCA的粒子滤波算法实现方法。内容简介本书系统介绍粒子滤波算法的基本原理和关键技术,针对标准粒子滤波算法存在的粒子退化、计算量大的缺点介绍了多种改进的粒子滤波算法,包括基于重要性密度函数选择的粒子滤波算法、基于重采样技术的粒子滤波算法、基于智能优化思想的粒子滤波算法、自适应粒子滤波算法流形粒子滤波算法等,并将粒子滤波算法应用于机动目标跟踪、语音增强、传感器故障诊断、人脸跟踪等领域最后探讨了粒子滤波算法的硬件实现问题,给出了基于DsP和FPGA的粒子滤波算法实现方法。本书可供高等院校电子信息、自动化、计算机应用、应用数学等有关专业高年级本科生和研究生,以及从事控制科学与工程、信号与信息处理领域的工程技术人员和研究人员参考阅读。图书在版编目(CIP)数据粒子滤波算法及其应用/朱志宇著.一北京:科学出版社,2010.6ISBN978-7-03-027611-7I.①粒…Ⅱ.①朱…Ⅲ.①非线性控制系统Ⅳ,①O231.2中国版本图书馆CIP数据核字(2010)第08821号责任編辑:孙芳王志欣/责任校对:陈玉责任印制;赵博/封面设计:耕者设计工作室學☆出版北京东黄城根北街|6号邮攻编码:100717http://www.sciencep400酉卹剩厂印刷科学出版社发行各地新华书店经销2010年6月第版开本;B5(720×10002010年6月第一次印刷印张:163/4印数:1-3000字数:324000定价:48.00元(如有印装质量问题,我社负责调换)前言粒子滤波又称序贯蒙特卡罗方法,是一种基于蒙特卡罗方法和递推贝叶斯估计的统计滤波方法,它依据大数定理,采用蒙特卡罗方法来求解贝叶斯估计中的积分运算。粒子滤波算法首先依据系统状态向量的经验条件分布在状态空间产生组随机样本的集合,然后根据观测量不断地调整粒子的权重和位置,通过调整后粒子的信息修正最初的经验条件分布。当样本容量很大时,这种蒙特卡罗描述就近似于状态变量真实的后验概率密度函数。粒子滤波适用于任何能用状态空间模型表示的非高斯背景的非线性随机系统,它完全突破了传统的 Kalman滤波理论框架,对系统的过程噪声和量测噪声没有任何限制,可适用于任何非线性系统,精度可以逼近最优估计,是一种很有效的非线性滤波技术,可广泛应用于数字通信、金融领域数据分析、统计学、图像处理、计算机视觉、自适应估计、语音信号处理、机器学习等方面。粒子滤波算法是现代信号与信息处理学科和统计模拟理论之间的交叉学科,其研究有着重要的理论意义和现实价值,随着计算机性能的迅速提高,这方法日益受到人们的关注。近年来,从解决粒子退化和粒子多样性丧失、提高算法实时性和鲁棒性、降低计算复杂度等角度考虑,国内外学者广泛开展了粒子滤波研究。本书系统总结了近年来粒子滤波的研究成果,针对粒子滤波算法的缺点提出了若干种改进算法,包括基于微分流形的粒子滤波算法、基于人工鱼群的粒子滤波算法、基于神经网络的粒子滤波算法、自适应粒子滤波算法等;广泛探讨了粒子滤波算法的各种应用,给出了粒子滤波算法的硬件实现方法在本书编撰过程中,作者研读了大量文献,参考融合了国内外专家、学者们在相关领域的硏究成果,在此,对他们表示衷心谢意!王建华教授、姜长生教授、张冰教授对本书的编写工作提供了很多宝贵意见,杨官校、李冀、皇丰辉、刘炜、薄超等同学编制了书中的仿真程序,赵成、苏岭东、姜威威等同学绘制了书中的部分图表。在此,向参与和关心本书编写工作的各位同事和同学表示真诚的感谢本书的出版得到了江苏省高校自然科学基金(项目编号:06KJB510030)和中国船舶行业预研基金(项目编号:3.1.5)的资助。由于作者学术水平有限,书中难免存在不妥之处,殷切期望广大读者批评指正。作者2010年3月目录前言第一篇粒子滤波算法第1章绪论1粒子滤波的发展和应用……··d·············.41.2粒子滤波的缺点和现有的解决方法4第2章 Kalman滤波理论2.1标准 Kalman滤波算法R-y滤波器102.3EKF滤波算法24 MVEKF算法142.5UKF算法D春看曲。·鲁b·····。音·看自。··非自b。非…………15第3章从贝叶斯理论到粒子滤波…193.1动态空间模型3.2贝叶斯估计理论203.3蒙特卡罗积分………·.·日···↓..··":·.·“.···香。·。着非●自·223.4序贯蒙特卡罗信号处理2435粒子滤波27第4章基于重要密度函数选择的改进粒子滤波算法334.1GHPF…………………………………………………334.2 EKPF354.3 UPF374.4 IMMPF算法…………384.5二阶中心差分粒子滤波…………404.6基于 Stiefel流形的粒子滤波器研究434.7混合退火粒子滤波器研究45IV粒子滤波算法及其应用第5章基于重采样技术的改进粒子滤波算法最自自自485.1重要性重采样粒子滤波器………485.2基于MCMC的粒子滤波……495、3AVPF……………525.4 RPF∴…545.5核K-粒子滤波算法(KPF)5.6基于权值选择的粒子滤波算法…575.7线性优化重采样粒子滤波算法5.8基于 Stiefel流形和权值优选的粒子滤波器( SM-WSPF)研究605.9基于 Stiefel流形和线性优化重采样的粒子滤波器( SM-LOCR-PF)研究615.10其他常用的重采样方法621仿真分析第6章基于智能优化思想的粒子滤波算法6.1GPF算法…………………736.2 PSO-PF算法p·普·日···曹·。昏鲁··甲啊·。··中日中··串自自·事6.3 AFSA-PF算法6.4AIPF算法鲁音·鲁甲··鲁曹·自·即………906.5仿真分析97第7章基于神经网络的粒子滤波算法……1027.1基于神经网络的重要性权值调整粒子滤波( NNWA-PF)算法…1027.2基于神经网络的重要性样本调整粒子滤波( NNISA-PF)算法1057.3仿真分析……109第8章APF算法音·自·普自自自非●·P,自自··自··非鲁自单最自自音自自自·4非鲁备自音。非·鲁音。··音鲁1148.1似然分布自适应调整1148.2样本数APF8.3改进APF…1188.4APF的仿真分析…119第9章其他粒子滤波算法1269.1免重采样粒子滤波1269.2MPF……………………………………………………132目录9.3分布式粒子滤波134第二篇粒子滤波算法的应用第10章粒子滤波算法在机动目标跟踪中的应用……1390.1基于贝叶斯理论的目标跟踪技术…………………13910.2机动目标的运动模型……14010.3多目标跟踪中的联合概率数据关联方法14210.4非线性、非高斯条件(闪烁噪声)下的机动目标跟踪14510.5基于粒子滤波和JPDA的多目标跟踪数据关联算法10.6仿真实验…150第11章粒子滤波应用于语音信号增强………16111.1语音增强技术………………………………………16111.2TVAR模型11.3基于GPF的语音增强算法11.4语音信号增强仿真实验…I68第12章粒子滤波应用于传感器故障诊断e早看值·看…………17212.1故障诊断的方法…17212.2传感器故障诊断的基本原理…17412.3应用粒子滤波进行故障诊断鲁番“·.····.;·4···17712.4仿真实例分析180第13章粒子滤波算法在人脸跟踪中的应用19013.1人脸跟踪介绍…………………19013.2跟踪算法相关理论基础·19313.3基于直方图的坞值偏移人脸跟踪算法·19613.4基于直方图的粒子滤波人脸跟踪算法20113.5基于椭圆拟合的人脸跟踪算法…20613.6基于流形的人脸跟踪算法p音直最看·鲁鲁··息·翟·唱备售暴4鲁售聊鲁20713.7人脸跟踪仿真…………鲁电210第14章粒子滤波在倒立摆控制系统中的应用21614.1引言21614.2倒立摆控制系统模型216粒子滤波算法及其应用14.3基于神经网络的倒立摆控制系统研究∴21914.4粒子滤波优化神经网络倒立摆控制仿真…22第15章基于DSP实现的粒子滤波算法……22515.1FBPF算法鲁t·息鲁鲁∴22515.2基于硬件实现的改进FBPF算法…22715.3实现改进FBPF算法的DSP···→·········:·..··.·;····..·········22815.4改进FBPF算法DSP实现的软件环境…23015.5改进FBPF算法的软件仿真与DSP实现…23115.6基于改进FBPF算法的GPS导航系统设计237第16章基于FPGA的粒子滤波算法实现∴24116.1基于FPGA的改进FBPF算法的总体设计∴…241l16.2FPGA简介…24216.3改进FBPF算法的软件仿真与FPGA实现245参考文献…:a4a....············.··.··········253第一箭粒子滤波算法
- 2020-06-21下载
- 积分：1
浙江大学计算理论复习总结
计算理论复习总结,但是考试快要结束了，估计大家也没有什么需要了。28.文法是CFG的推广,任何CFG都是文法。G=(V,∑,R,S)29.语言被文法生成ⅲ它是re的。30.所有数值函数都是原始递归的31.原始递归函数集是递归可枚举的。32.特殊语言/问题H={"M"w":M在w上停机}lH={"M"w":M是一台在"w"上不停机的TM}H1={"M":M在“M”上停机}H1={w:要么w不是一台TM的编码,要么w是M的编码,M是一台在"M"上不停机的TM}H:re.;H1:re.;-H,-H1:非r.e.;2-SAT∈P;SAT∈NPThe world as We Dont Know itreAsumming P≠APCo『eHrecursiveSATSATCO-A伊II Asumming P=Npr, eCo-r.erecursiveNP= cO-Np= p33没有算法的问题称作不可判定的or不可解的,如TM的停机问题34.证明不可判定通用图灵机U通过递归函数归约到L如果L是递归的则U是递归的ic若L1非递归,并存在L1到L2的归约,则L2也非递归。递归函数是 Turing Computable的35.语言是图灵可枚举的,证存在枚举它的图灵机。(M通过空格代开始,周期性的经过特殊状态q来枚举L,任意顺序且可重复)6.不可判定语言与递归语言互为补集,与rc语言有交集。37语言是re.,if它是图灵可枚举的;语言是递归的,i它是以字典序 turing可枚举的。8.P在并交连接和补运算下封闭NP在并、连接运算下封闭。若NP在补下封闭则NP=P39.H={M"wM在最多2w步后停机}唾P40.所有正则语言和所有CFL都属于P41.NPA.机器角度去定义:被多项式界限非确定型图灵机判定的所有语言的类。B.基于 verifier的定义:NP问题上建立的非确定机包含两步1)非确定地猜一个解2〕用一个确定的算法判定该解是否为可行解判定一个给定猜测值是否满足该问题(可满足性)的算法称作 verifier,一个问题称作NP问题当且仅当存在一个多项式时间的 verifier这两个定义是不矛盾的,因为如果一台非确定TM在多项式时间内可以判定一个非确定选择的翰入是否满足,就是基于 verifier的定义。P和NP的区别a problem is in P if we can decide them in polynomial time. It is in NP if we candecide them in polynomial time, if we are given the right certificate42.若存在计算函数f的多项式界限的图灵机M,则f称为多项式时间可计算的43.若τ1是L1->l2的多项式归约,τ2是L2->I3的多项式归约,则τ1τ2是L1->l3的多项式归约44.证明NP完全法一、按定义:LΣ*,若(a)L∈NP,且(b)对每个语言L∈NP,存在从L到L的多项式归约则L称为NP完全的。法二、归约,对于语言L,(a)若L∈NP(b)一个NP完全问题可以在多项式时间规约到L,ie. SAT 0 is context-free but not regular49.L=L1L2,L是CFL,则L1一定是CFL(x50. Regular-CFL不一定是CFL,如a*b*c*-anbn包含 anben51. 2-way PDalie PDa whose input heads can move both left and right] are more powerfulthan 1-way pda52. Given a PDa M1 and an fa M2, the problem l(M1)cl(M2)is decidable53.DFA/NFA识别的是 exactly正则语言54.Re.只在补和差下不封闭,CFL在交下也不封闭55.非正则语言的可能是正则语言。比如A:[W=w}及所有回文,A=*,为正则语言56.典型非正则:w=wR57.正则语言的子集可能非正则,如 anben是a*b*c*的子集;又如Σ*是正则语言,H≌Σ*58.归约:X到Y的归约可以理解为X到Y问题的映射, reduction可以解释为 at least asdifficult as….比如ⅹ可以被Y的算法解决,则 X is no more difficult than yⅩ可以约到Y,记X≤Y。e.gx2可以归约到任意两数的乘积。若有A≤B,A是不可判定问题>B不可判定A不递归->B不递归B可判定>A可判定B是递归的->A是递归的59.若X多项式时间归约到Y,Y多项式时间可解,则X多项式时间可解若X多项式时间归约到Y,Ⅹ多项式时间不可解,则Y多项式时间不可解60.X多项式时间归约到Y,Y多项式时间归约到Z,则X多项式时间归约到Z61.PRME( COMPOSITE)多项式时间归约到 Factor,但是 Factor多项式时间不能归约到PRIME COMPOSITE )o62.若A≤PB,B∈NP,则A∈NP。证明A≤PB→存在确定图灵机X,可将A归约到B。B∈NP→存在一个非确定图灵机N可判定B。我们希望构造一个新的TM(ⅹN)是的ⅹ*N非确定多项式时间求解A,则A∈NPRunning time of X*N≤1+p(mB>+qp(m)(B多项式时间非确定判定是多项式时间所以A∈NP63若AsPB,B∈P,则A∈P64.若X是NPC的,则X在多项式时间内可解ifP=NP65.SAT多项式时间归约到3SA(3AT是NPC的)66.证明语言L是R/Re, Non rea) Intuitively想想有没有半判定(判定)的TM,有则Rc、(R)。若非R执行下一步。b)用能否由Re.( Non re.)语言归约到该语言,能则Re而非R( Non re)严格用归约函数定义f:A≤B,r1∈A当且仅当r1∈Beg1∈H,M∈L证明Recg2∈非H,iM∈L证明 Non rc注意方向:是从A的实例经过递归函数推向B的实例。详细介绍http://www.cs.rice.edu/nakhleh/comp481/finalreviewsp06sol.pdf67.递归与μ递归等价68.PDA中,若每一个格局至多有一个格局接在它后面,则为确定型的。确定型CF在补下封闭69.M半判定L:w∈L,ifM在w上停机,注意半判定图灵机中不存在“拒绝”状态。只要不接受w,就不停机。70. Chomsky hierarchyElements of the Chomsky HierarchyRecursively enumerable languagesRecursive languageContext sensitive languagesContext ee languageseterministccontext free languagesRegularanguages71.俩证明7.6证明P在并、交、 Kleene*连接和补运算下封闭(1)并:对任意L,LEP,遴n时间图灵机M1和nb时间图灵机M2判定它们且c=max{ab}对L1L2构造判定器MM=“对于输入字符串w1)在W上运行M1,在w上运行M22)若有一个接受则接受,否则拒绝。时间复杂度:设M1为0(n)M2为0(m)。令c=max{ab}第一步用时0(n+n),因此总时间为Oma+n)=0(n9所以L1L2属于P类,即P在并的运算下封闭。(2)连接对任意L1,L2属于P类,设有n时间图灵机M1和m时间图灵机M2判定它们,且c=max{ab}。对L1l2构造判定器MM=“对于输入字符串w=w2灬,Wn对k=0,1,21…,n重复下列步骤。在wW2…wk上运行M1,在wk1wk+2…n上运行M若都接受,则接受。否则继续。若对所有分法都不接受则拒绝。时间复杂度:(n+1x0(n+0m-0(m+4)+0(nb+4=0(nc+),F以L1oL2属于P类,即P在连接的运算下封闭。对任意L属于P类,设有时间0(n)判定器M判定它,对构造判定器MM=“对于输入字符串〔1)在w上运行M12)若M1接受则拒绝,若M1拒绝则接受。时间复杂度为:0(m)。所以属于P类,即P在补的运算下封闭。77证明NP在并和连接运算下封闭。1)并对任意L1,L2∈NP,设分别有n时间非确定图灵机M1和n时间非确定图灵机M2判定它们,且c=max{a,b}。构造判定LL2的非确定图灵机M:M=“对于输入字符串w1)在W上运行M1,在w上运行M2。2)若有一个接受则接受,否则拒绝。对于每一个非确定计算分支,第一步用时为O(n-)+O(n),因此总时间为On+n)=0(n。所以LLz∈NP,即NP在并的运算下封闭2)连接对任意L,L2∈NP设分别有na时间非确定图灵机M1和m时间非确定图灵机M2判定它们,且c=max{ab}。构造判定L1oL2的非确定图灵机M:M=“对于输入字符串w:1〕非确定地将分成两段xy,使得w=xy。2)在x上运行M1,在y上运行M23)若都接受则接受,否则拒绝。对于每一个非确定计算分支,第一步用时O(n,第二步用时为0(n)+0(m),因此总时间为o(n+m)=0(n。所以L1oL2∈NP,即NP在连接运算下封闭。专题一一图灵机可判定性问题判定以下问题是否可判定:声明:思路—想证明B问题不可解,1.从一个不可解问题A入手(如停机问题)2.创建B的—个实例,从中推出如果能解决B,A也就可以解决了3.所以B是不可解的1.一个图灵机有至少481个状态。我们可以给出这样一个TMN进行cnc(M)a)数M中状态数,直到481b)如果达到了481,N就接受,否则拒绝2.给定图灵机在空串上走了481步还没停机。构造2带图灵机N,a)2a带:写481个0b)1s带在空串上模拟M,每走一步,第2带就删掉一个0c)如果M在所有0都删掉之后停机,则N接受,否则不接受给定图灵机,判定它是否在一些输入上经过481步还没停机?a)按字典序找出所有 length
- 2020-12-01下载
- 积分：1
