均值漂移算法的收敛性
均值漂移跟踪算法
在无人驾驶车辆测试平台上利用均值漂移跟踪算法实现移 动图像的实时跟踪 Benjamin Gorry, Zezhi Chen, Kevin Hammond, Andy Wallace, and Greg Michaelson 摘要：本文描述了一种用来跟踪移动目标的新型计算机视觉算法，该算法是作为 无人驾驶车辆长期研究的一部分而被发展的。我们将介绍在视频序列中利用变量核 进行跟踪的研究结果。其中，均值漂移目标跟踪算法是我们工作的基础；对于一个 移动目标，该算法通常用来在初始帧中确定一个矩形目标窗口，然后利用均值漂移 分离算法处理该窗口中的数据，将跟踪目标从背景环境中分离出来。我们并没有使 用标准的Epanechnikov内核，而是利用一个倒角距离变换加权内核来提升目标表 示和定位的精度，利用Bhattacharyya系数使RGB色彩空间中两个分布之间的距离 最小化。实验结果表明，相对于标准算法，本算法在跟踪能力和通用性上有一定的 提升。这些算法已经运用在机器人试验平台的组成部分中，并证明了这些算法的有 效性。 关键词：Hume，函数程序设计，无人驾驶车辆，先驱者机器人，视觉 I.引言 本文比较和对比了在视觉序列中跟踪移动目标的三种计算机视觉算法。对于很多无人驾驶车辆（A V）来说，在复杂背景中检测和跟随移动目标的应用是至关重要的。例如，这可以让一个全尺寸无人驾驶车辆跟踪行人或者移动车辆并避免与之相撞。同时对于机器人而言，这项技术也可以提升导航性能和增强安全性。对单个移动目标的良好隔离，将便于我们针对感兴趣的目标进行应用开发。而所有的这些应用都要求我们能够实时的处理全彩色的视频序列。 我们的工作是在基于先驱者P3-AT全地形机器人的无人驾驶车辆测试平台上进行的，它是一个英国项目的一部分。这个庞大的项目是由国防科学技术中心（DTC）下辖的无人系统工程（SEAS）为了开发新型无人驾驶车辆传感器技术而建立的。国防科学技术中心的无人系统工程是由英国工业联盟操作管理，旨在通过采取系统工程的方法在整个系统和子系统
opencv实现分水岭,金字塔,均值漂移算法进行分割
using System; using System.Collections.Generic; using https://www.wendangku.net/doc/d42623404.html,ponentModel; using System.Data; using System.Drawing; using System.Linq; using System.Text; using System.Windows.Forms; using System.Diagnostics; using System.Runtime.InteropServices; using Emgu.CV; using Emgu.CV.CvEnum; using Emgu.CV.Structure; using Emgu.CV.UI; namespace ImageProcessLearn { public partial class FormImageSegment : Form { //成员变量 private string sourceImageFileName = "wky_tms_2272x1704.jpg";//源图像文件名 private Image
基于均值漂移的视觉目标跟踪方法综述
基于均值漂移的视觉目标跟踪方法综述 齐 飞，罗予频，胡东成 (清华大学自动化系，北京 100084) 摘 要：基于均值漂移的视觉目标跟踪方法具有模型简洁实用、能够处理目标形变及部分遮挡等复杂情形的优点，算法高效且易于模块化实现。各种改进的模型及方法针对目标的尺度变化、特征分布等核心问题进行了系统研究，跟踪性能得到了进一步提高。该文从基本的均值漂移跟踪方法出发，系统介绍了此类方法的发展过程与最新成果。 关键词：均值漂移；视觉目标跟踪；核函数；相似性度量 Overview on Visual Target Tracking Based on Mean Shift QI Fei, LUO Yu-pin, HU Dong-cheng (Department of Automation, Tsinghua University, Beijing 100084) 【Abstract 】Mean-shift-based visual target tracking is one of the hotspots in the field of computer vision. The model of the algorithm is simple,efficient and easy-to-implement, and it can handle the complex cases such as deformations and partial occlusions. Recent researches on scale adaptation of the tracking window and distributions of features improve the performance of such trackers. This paper introduces the development and the state of such kind of the algorithms. 【Key words 】mean shift; visual target tracking; kernel functions; similarity measurement 计 算 机 工 程Computer Engineering 第33卷 第21期 Vol.33 No.21 2007年11月 November 2007 ·博士论文· 文章编号：1000—3428(2007)21—0024—04 文献标识码：A 中图分类号：TP311 视觉目标跟踪在安全监控、汽车辅助驾驶、人体运动分析以及视频压缩等领域有着广泛应用。由于视觉目标本身及周边环境复杂多变，因此获得鲁棒而高效的跟踪算法目前仍旧是计算机视觉中一个极具挑战性的研究课题。 典型的视觉跟踪算法通常包括2个核心模块：数据关联和目标定位。前者根据先验知识如目标的动力学特征，将检测结果与目标状态关联起来，并对跟踪轨迹进行滤波。这方面的研究已经比较成熟，常用方法有卡尔曼滤波器、粒子滤波器及概率数据关联。后者是对被跟踪目标建模并据此在图像序列各帧中定位目标。在视觉目标跟踪中，目标建模及定位更为重要，常用的方法有色块模型和活动轮廓模型。均值漂移方法[1~2]提供了一种新的目标描述与定位的框架，将目标特征与空间信息有效地结合起来，避免了使用复杂模型描述目标的形状、外观及其运动。 1 均值漂移方法介绍 均值漂移(mean shift)是Fukunaga 等人提出的一种非参 数概率密度梯度估计算法[1]，在统计相似性计算与连续优化方法之间建立了一座桥梁。该方法直到Cheng 的研究成果[2]发表之后，才受到较多的关注。此后均值漂移被广泛应用到诸多相关领域，如模式分类、图像分割以及目标跟踪等方面。 核函数在均值漂移方法中起了非常重要的作用，核函数的概念、构造方法及常用形态如下文所述。 1.1 核函数 考虑d 维实欧氏空间d R ，向量,d R ∈x y 的内积定义为 T ,=i i i x y ??=∑x y x y ，向量的模可由内积导出1/2=,??x x x 。 对给定的函数:d K R R →，若存在一元函数:[0,)k R ∞→使得 2 ()=()K k x x 成立，其中，()k r 在区间[0,)∞上非负、有界、 单调减、分段连续并且积分0 ()d k r r ∞ ∫有界，则称函数() K x 为核函数，)(r k 为相应的剖面函数。因为函数)(r k 分段连续，不可导点集的Lebesgue 测度为0，所以在不可导点集上补充定义后，函数)(r k 在其定义域内处处可导，即)(r k ′存在。常见的剖面函数见表1。 表1 常见的剖面函数 给定核函数()K ?和()H ?，对应的剖面函数为)(r k 和 ()h r ，若存在常数c ，使得()=()k r ch r ′?，则称()H ?为()K ?的 影子核。 给定核函数()K x 和()K x 及正实数σ，由下列各式定义的函数也是核函数： 1()(/)()()()()() ()()()K K P K K K K S K K σσ?====+?x x x x x x ?x x x x 其中，矩阵?是d d ×维实正定对称矩阵。若记单位矩阵为 I ，当取=σ?I 时，()=()K K σ?x x 。通常称σ为核函数 ()K σx 的窗宽，称?为核函数()K ?x 的窗宽矩阵。 作者简介：齐 飞(1977－)，男，博士研究生，主研方向：模式识别，计算机视觉；罗予频、胡东成，教授、博士生导师 收稿日期：2006-11-20 E-mail ：qfei00@https://www.wendangku.net/doc/d42623404.html,
蚁群算法
蚁群算法 学号：1101500449 姓名：赵亮民 摘要：蚁群算法是优化领域中新出现的一种仿生进化算法。该算法采用分布式并行计算机制，具有较强的鲁棒性；但有搜索时间较长，易陷入局部最优解的缺点。本文首先讲述蚁群算法的来源和基本原理，然后讨论蚁群算法的几种改进策略，并简单介绍近年来蚁群算法在许多新领域中的发展应用，最后对今后进一步研究的方向作了展望。 关键词：蚁群算法；蚂蚁；信息素；优化 Abstract：Ant colony algorithm is a novel category of bionic algorithm for optim ization problems．Parallel computation mechanism is adopted in this algorithm．It has strong robustness and is easy to combinewith other methods in optimization，but it has the limitation of stagnation，and is easy to fall into local optimums．Firstly，the basic principle of ant colony algorithm is introduced．Then。a series of schemes on improving the ant colony algorithm are discussed，and the new applications are also provided．Finally，somerem arks on the further research and directions are presented． Key words：ant colony algorithm ；ant；pheromone；optimization 概念 各个蚂蚁在没有事先告诉他们食物在什么地方的前提下开始寻找食物。当一只找到食物以后，它会向环境释放一种挥发性分泌物pheromone (称为信息素,该物质随着时间的推移会逐渐挥发消失，信息素浓度的大小表征路径的远近)来实现的，吸引其他的蚂蚁过来，这样越来越多的蚂蚁会找到食物。有些蚂蚁并没有象其它蚂蚁一样总重复同样的路，他们会另辟蹊径，如果另开辟的道路比原来的其他道路更短，那么，渐渐地，更多的蚂蚁被吸引到这条较短的路上来。最后，经过一段时间运行，可能会出现一条最短的路径被大多数蚂蚁重复着。原理 设想，如果我们要为蚂蚁设计一个人工智能的程序，那么这个程序要多么复杂呢？首先，你要让蚂蚁能够避开障碍物，就必须根据适当的地形给它编进指令让他们能够巧妙的避开障碍物，其次，要让蚂蚁找到食物，就需要让他们遍历空间上的所有点；再次，如果要让蚂蚁找到最短的路径，那么需要计算所有可能的路径并且比较它们的大小，而且更重要的是，你要小心翼翼地编程，因为程序的错误也许会让你前功尽弃。这是多么不可思议的程序！太复杂了，恐怕没人能够完成这样繁琐冗余的程序。 然而，事实并没有你想得那么复杂，上面这个程序每个蚂蚁的核心程序编码不过100多行！为什么这么简单的程序会让蚂蚁干这样复杂的事情？答案是：简单规则的涌现。事实上，每只蚂蚁并不是像我们想象的需要知道整个世界的信息，他们其实只关心很小范围内的眼前信息，而且根据这些局部信息利用几条简单的规则进行决策，这样，在蚁群这个集体里，复杂性的行为就会凸现出来。这就是人工生命、复杂性科学解释的规律！那么，这些简单规则是什么呢？ 现今有哪些关于蚁群算法的应用呢？ 1大规模集成电路的线网布局 在大规模集成电路的线网布局中，需要根据电路和工艺的要求完成芯片上单元或功能模块的布局，然后实现它们之间的互连。此问题可看作是寻找一个网格平面上两端点之间绕过障碍的最短路径问题。线网上的每个Agent根据启发策略．像蚂蚁一样在开关盒网格上爬行，所经之处便设置一条金属线．历经一个线网的所有引脚之后．线网便布通了。应用蚁群算法，可以找到成本最低、最合理的线网布局．而且由于其本身的并行性。比较适合于解决此类问题。 2通信网络路由
粒子群算法的收敛性研究综述
粒子群优化算法的收敛性研究综述 摘要:给出了粒子群与改进算法的分类及其进展，指出了粒子群算法收敛性理论分类及其进展，最后对各粒子群算法的收敛条件进行了对比。 关键词：粒子群算法粒子群算法分类收敛条件 粒子群优化算法(PSO:Particle Swarm Optimization)是一种优化计算技术。起源于对鸟群和鱼群群体运动行为的研究，是一种基于迭代的优化工具，是一种基于群只能方法的演化计算技术。PSO算法概念简单容易实现，并且没有许多参数需要调整，短短十几年里，PSO 算法已经取得了很大的发展，目前已广泛应用于函数优化、神经网络的训练、模糊系统的控制、以及其他遗传算法的应用领域。。但是它由于容易陷入局部极小点，搜索精度不高，科研工作者对其作了各种各样的改进。目前已提出了多种PSO改进算法[1]。如自适应PSO算法,混合PSO算法，协同PSO算法，离散PSO算法。一些学者从数学的角度对算法的收敛性进行了初步分析[13] 。 本文以下部分的组织是：第1节介绍粒子群算法的分类及其当前研究进展；第2节介绍粒子群算法收敛性理论分类及其进展；最后对比各粒子群算法的收敛条件。 1 粒子群与改进算法的分类及其进展 1.1 自适应PSO(Adaptive Particle Swarm Optimization,APSO) 由于较大的惯性因子W值有利于跳出局部极小点，而较小的W值有利于算法收敛，于是科研工作者就提出了自适应调整W的方法，即随着迭代的进行，线性地减小W值。这种方法的进一步发展就是采用模糊规则动态地修改W的值[4]。即构造2个输入，一个输出的模糊推理机来动态修改惯性因子W。模糊推理机的两个输入分别是当前W值，输出为W的增量。通过自适应调整全局系数，兼顾搜索效率和搜索精度，是一类有效的算法。但是对许多复杂的非线性优化问题，试图通过自适应调整一个全局系数提高搜索精度的余地是有限的。 1.2 混合PSO(Hybrid Particle Swarm Optimization,HPSO) 受到遗传算法的启示，文献[5,6]最早提出了混合PSO算法。混合PSO算法是将基本PSO 算法和选择机制相结合而得到的，基本的PSO算法的搜索过程很大程度说那上依赖pbest 和gbest,它的搜索区域受到gbest和gbest的限制。在一般的进化算法中，选择机制用来选择相对较好的区域和淘汰较差的区域。可以更合理地分配有限的资源。
蚁群算法综述
《智能计算—蚁群算法基本综述》 班级：研1102班 专业：计算数学 姓名：刘鑫 学号： 1107010036 2012年
蚁群算法基本综述 刘鑫 （西安理工大学理学院，研1102班，西安市，710054） 摘要:蚁群算法( ACA)是一种广泛应用于优化领域的仿生进化算法。ACA发展背景着手，分析比较国内外ACA研究团队与发展情况立足于基本原理,分析其数学模型,介绍了六种经典的改进模型，对其优缺点进行分析，简要总结其应用领域并对其今后的发展、应用做出展望。 关键词:蚁群；算法；优化；改进；应用 0引言 专家发现单个蚂蚁只具有一些简单的行为能力。但整个蚁群却能完成一系列复杂的任务。这种现象是通过高度组织协调完成的1991年。意大利学者M.Dorigo 首次提出一种新型仿生算法ACA。研究了蚂蚁的行为。提出其基本原理及数学模型。并将之应用于寻求旅行商问题(TSP)的解。 通过实验及相关理论证明,ACA有着有着优化的选择机制的本质。而这种适应和协作机制使之具有良好的发现能力及其它算法所没有的优点。如较强的鲁棒性、分布式计算、易与其他方法结合等；但同时也不应忽略其不足。如搜索时间较长，若每步进行信息素更新，计算仿真时所占用CPU时间过长：若当前最优路径不是全局最优路径，但其信息素浓度过高时。靠公式对信息素浓度的调整不能缓解这种现象。会陷人局部收敛无法寻找到全局最优解：转移概率过大时，虽有较快的收敛速度，但会导致早熟收敛。所以正反馈原理所引起的自催化现象意在强化性能好的解，却容易出现停滞现象。笔者综述性地介绍了ACA对一些已有的提出自己的想法，并对其应用及发展前景提出了展望。 1 蚁群算法概述 ACA源自于蚁群的觅食行为。S.Goss的“双桥”实验说明蚂蚁总会选择距食物源较短的分支蚂蚁之间通过信息素进行信息的传递,捷径上的信息素越多,吸引的蚂蚁越多。形成正反馈机制,达到一种协调化的高组织状态该行为称集体自催化目前研究的多为大规模征兵，即仅靠化学追踪的征兵。 1 .1 蚁群算法的基本原理
RLS算法的收敛性分析
RLS 与 LMS 算 法 的 收 敛 性 比 较 分 析 学号：S120101057 姓名：贾雪婷
摘要：介绍了自适应滤波器的基本原理，对最小均方(LMS, Least Mean Squares)和递归最小二乘(RLS, RecursiveL east Squares)自适应算法进行仿真分析及对比研究。仿真结果及实例均表明，两种算法都能有效抑制和抵消各种干扰，但相比之下，RLS算法具有更好的收敛性能及稳定性，除收敛速度快于LMS算法和NLMS 算法以及稳定性强外，而且具有更高的起始收敛速率、更小的权噪声和更大的抑噪能力。 关键词：自适应滤波；最小均方；递归最小二乘；收敛性；对比研究Abstract: Introducing the basic principle of adaptive filter,as for the minimum mean square(LMS, Least Mean Squares)and Recursive Least Squares(RLS, RecursiveL east Squares) adaptive algorithm is applied to the simulation analysis and comparative study. The simulation results and examples indicate that the, two kinds of algorithm can effectively restrain and offset all kinds of interference, but in contrast, RLS algorithm has better convergence performance and stability, In addition to convergence speed faster than LMS algorithm and NLMS algorithm and the stability, but also have higher initial rate of convergence、smaller right noise and more noise suppression ability. Key words: adaptive filtering;LMS;RLS; astringency; Comparative study
蚁群算法与粒子群算法优缺点个人精华篇
蚁群算法与粒子群算法优缺点 蚁群算法(ACO)是受自然界中蚂蚁搜索食物行为的启发，是一种群智能优化算法。它基于对自然界真实蚁群的集体觅食行为的研究，模拟真实的蚁群协作过程。算法由若干个蚂蚁共同构造解路径，通过在解路径上遗留并交换信息素提高解的质量，进而达到优化的目的。蚁群算法作为通用随机优化方法，已经成功的应用于TSP等一系列组合优化问题中，并取得了较好的结果。但由于该算法是典型的概率算法，算法中的参数设定通常由实验方法确定，导致方法的优化性能与人的经验密切相关，很难使算法性能最优化。 蚁群算法中每只蚂蚁要选择下一步所要走的地方，在选路过程中，蚂蚁依据概率函数选择将要去的地方，这个概率取决于地点间距离和信息素的强度。 (ｔ+ｎ) = (t)+ Δ(ｔ+ｎ) 上述方程表示信息素的保留率，1－表示信息素的挥发率，为了防止信息的无限积累，取值范围限定在0～1。Δij 表示蚂蚁k在时间段t到(t +n)的过程中，在i到j的路径上留下的残留信息浓度。 在上述概率方程中，参数α和β:是通过实验确定的。它们对算法性能同样有很大的影响。α值的大小表明留在每个节点上信息量受重视的程度，其值越大，蚂蚁选择被选过的地点的可能性越大。β值的大小表明启发式信息受重视的程度。 这两个参数对蚁群算法性能的影响和作用是相互配合，密切相关的。但是这两个参数只能依靠经验或重复调试来选择。 在采用蚁群－粒子群混合算法时，我们可以利用PSO对蚁群系统参数α和β的进行训练。具体训练过程：假设有n个粒子组成一个群落，其中第i个粒子表示为一个二维的向量xi = ( xi1 , xi2 ) , i = 1, 2, ?,n，即第i个粒子在搜索空间的中的位置是xi。换言之，每个粒子的位置就是一个潜在的解。将xi带入反馈到蚁群系统并按目标函数就可以计算出其适应值，根据适应值的大小衡量解的优劣。 蚁群算法的优点： 蚁群算法与其他启发式算法相比，在求解性能上，具有很强的鲁棒性（对基本蚁群算法模型稍加修改，便可以应用于其他问题）和搜索较好解的能力。 蚁群算法是一种基于种群的进化算法，具有本质并行性，易于并行实现。 蚁群算法很容易与多种启发式算法结合，以改善算法性能。 蚁群算法存在的问题： TSP问题是一类经典的组合优化问题，即在给定城市个数和各城市之间距离的条件下，找到一条遍历所有城市且每个城市只能访问一次的总路程最短的路线。蚁群算法在TSP问题应用中取得了良好的效果，但是也存在一些不足： （1），如果参数α和β设置不当，导致求解速度很慢且所得解的质量特别差。 （2），基本蚁群算法计算量大，求解所需时间较长。 （3），基本蚁群算法中理论上要求所有的蚂蚁选择同一路线，该线路即为所求的最优线路；但在实际计算中，在给定一定循环数的条件下很难达到这种情况。 另一方面，在其它的实际应用中，如图像处理中寻求最优模板问题，我们并不要求所有的蚂蚁都找到最优模板，而只需要一只找到最优模板即可。如果要求所有的蚂蚁都找到最优模板，反而影响了计算效率。 蚁群算法收敛速度慢、易陷入局部最优。蚁群算法中初始信息素匮乏。蚁群算法一般需要较长的搜索时间，其复杂度可以反映这一点；而且该方法容易出现停滞现象，即搜索进行到一定程度后，所有个体发现的解完全一致，不能对解空间进一步进行搜索，不利于发现更好的解。
基于均值漂移与卡尔曼滤波的目标跟踪算法
２００７，４３（１２）ＣｏｍｐｕｔｅｒＥｎｇｉｎｅｅｒｉｎｇａｎｄＡｐｐｌｉｃａｔｉｏｎｓ计算机工程与应用 １引言 视频图像序列中运动目标跟踪是智能监控系统中的重要一部分，是计算机视觉、目标识别与跟踪、安全监控等视频分析和处理应用的关键技术。均值漂移算法作为一种高效的模式匹配算法，已经被成功的应用在目标跟踪领域［１－４］。该算法利用梯度优化方法实现快速目标定位，能够对非刚性目标实时跟踪，对目标的变形、旋转等运动有较好的适用性，但是均值漂移算法在目标跟踪过程中没有利用目标在空间中的运动方向和运动速度信息，当周围环境存在干扰时，仅使用均值漂移算法容易丢失目标。Ｋａｌｍａｎ滤波器是一个对动态系统的状态序列进行线性最小方差估计的算法，具有计算量小，可实时计算的特点，可以准确的预测目标的位置和速度［５］。 考虑到目标运动过程中可能会受到场景中诸如遮挡、光照变化等因素的影响，本文在采用基于颜色直方图的均值漂移跟踪算法的同时，合理结合了Ｋａｌｍａｎ滤波对目标空间运动位置的预测，保证了目标运动的一致性和连贯性。每一帧图像分别采用这两种方法进行跟踪，根据干扰的不同情况，采用不同的比例因子将两个跟踪结果线性加权，从而得到目标的最终位置。在干扰较小情况下，均值漂移算法可以得到良好的跟踪效果，其跟踪结果占较大的比重，强干扰情况下，加大Ｋａｌｍａｎ预测结果的比重，克服干扰。 ２均值漂移跟踪算法 目标的直方图不受目标形状变化的影响，因此采用直方图作为目标的模式，依据颜色分布进行匹配具有较好的稳定性。假设被跟踪的目标是中心为ｙ０，窗宽为ｈ的矩形。目标外围的像素可能被遮挡或者受到背景的影响是相对不可靠的，为此对目标内不同位置的像素赋予不同的权重，位置与目标中心的距离越近其权重越大。 目标的加权颜色直方图［２］为 ｑｕ（ｙ）＝Ｃｈ ｎ ｉ＝１ !ｋ（‖ｙ０－ｘｉ ｈ ‖２）δ［ｂ（ｘｉ）－ｕ］（１）其中Ｃｈ为归一化系数，Ｃｈ＝ １ ｎ ｉ＝１ !ｋ（‖ｙ０－ｘｉ ｈ ‖２） 。 当前图像帧中以图像空间点ｙ为中心的候选图像区域内，象素点的加权直方图表示为： 基于均值漂移与卡尔曼滤波的目标跟踪算法 常发亮，刘雪，王华杰 ＣＨＡＮＧＦａ－ｌｉａｎｇ，ＬＩＵＸｕｅ，ＷＡＮＧＨｕａ－ｊｉｅ 山东大学控制科学与工程学院，济南２５００６１ ＳｃｈｏｏｌｏｆＣｏｎｔｒｏｌＳｃｉｅｎｃｅａｎｄＥｎｇｉｎｅｅｒｉｎｇ，ＳｈａｎｄｏｎｇＵｎｉｖｅｒｓｉｔｙ，Ｊｉ’ｎａｎ２５００６１，Ｃｈｉｎａ Ｅ－ｍａｉｌ：ｌｉｕｘｕｅ９３＠１６３．ｃｏｍ ＣＨＡＮＧＦａ－ｌｉａｎｇ，ＬＩＵＸｕｅ，ＷＡＮＧＨｕａ－ｊｉｅ．ＴａｒｇｅｔｔｒａｃｋｉｎｇａｌｇｏｒｉｔｈｍｂａｓｅｄｏｎｍｅａｎｓｈｉｆｔａｎｄＫａｌｍａｎｆｉｌｔｅｒ．ＣｏｍｐｕｔｅｒＥｎｇｉｎｅｅｒｉｎｇａｎｄＡｐｐｌｉｃａｔｉｏｎｓ，２００７，４３（１２）：５０－５２． Ａｂｓｔｒａｃｔ：Ｍｅａｎｓｈｉｆｔａｌｇｏｒｉｔｈｍｄｏｅｓｎ’ｔｕｓｅｔｈｅｔａｒｇｅｔ’ｓｍｏｔｉｏｎｄｉｒｅｃｔｉｏｎａｎｄｓｐｅｅｄｉｎｆｏｒｍａｔｉｏｎｉｎｐｒｏｃｅｓｓｏｆｔａｒｇｅｔｔｒａｃｋｉｎｇ．Ｗｈｅｎａｆｆｅｃｔｅｄｂｙｄｉｓｔｕｒｂａｎｃｅｉｔｅａｓｉｌｙｆａｉｌｓｔｏｔｒａｃｋｔｈｅｔａｒｇｅｔ．Ｋａｌｍａｎｆｉｌｔｅｒｉｎｇｃａｎｐｒｅｄｉｃｔｔｈｅｐｏｓｉｔｉｏｎａｎｄｖｅｌｏｃｉｔｙｏｆｔｈｅｔａｒｇｅｔｅｘａｃｔｌｙ．ＡｎａｌｇｏｒｉｔｈｍｃｏｍｂｉｎｅｄＫａｌｍａｎｆｉｌｔｅｒｉｎｇｗｉｔｈｍｅａｎｓｈｉｆｔａｌｇｏｒｉｔｈｍｉｓｐｒｏｐｏｓｅｄｉｎｔｈｉｓｐａｐｅｒ．Ｋａｌｍａｎｆｉｌｔｅｒｉｎｇｉｓｕｓｅｄｔｏｐｒｅｄｉｃｔｔｈｅｐｏｓｉｔｉｏｎａｎｄｖｅｌｏｃｉｔｙｏｆｔｈｅｔａｒｇｅｔ．Ａｃｃｏｒｄｉｎｇｔｏｄｉｆｆｅｒｅｎｔｄｉｓｔｕｒｂａｎｃｅｃｉｒｃｕｍｓｔａｎｃｅｓ，ｔｈｅｔｗｏａｌｇｏｒｉｔｈｍｓｔｒａｃｋｉｎｇｒｅｓｕｌｔｓａｒｅｄｏｎｅｗｉｔｈｌｉｎｅｒｗｅｉｇｈｔｍｅｔｈｏｄｂｙｕｓｉｎｇｄｉｆｆｅｒｅｎｔｓｃａｌｅｆａｃｔｏｒｓｔｏｇｅｔｔｈｅｆｉｎａｌｐｏｓｉｔｉｏｎｏｆｔｈｅｔａｒｇｅｔ．Ｅｘｐｅｒｉｍｅｎｔａｌｒｅｓｕｌｔｓｓｈｏｗｔｈｅｇｏｏｄｐｅｒｆｏｒｍａｎｃｅｓｏｆｔｈｅｐｒｏｐｏｓｅｄａｌｇｏｒｉｔｈｍ． Ｋｅｙｗｏｒｄｓ：ｔａｒｇｅｔｔｒａｃｋｉｎｇ；ｏｃｃｌｕｓｉｏｎ；ｍｅａｎｓｈｉｆｔ；Ｋａｌｍａｎｆｉｌｔｅｒ 摘要：均值漂移算法在目标跟踪过程中没有利用目标的运动方向和速度信息，在目标受到干扰时容易跟踪失败，而Ｋａｌｍａｎ滤波能够较为准确地预测目标的速度和位置。因此，提出了一种结合均值漂移与Ｋａｌｍａｎ滤波的跟踪算法，使用Ｋａｌｍａｎ滤波对目标运动速度和空间位置进行预测。根据干扰的不同情况，使用不同的比例因子将两算法的跟踪结果线性加权得到目标的最终位置。实验结果表明该算法是可行有效的。 关键词：目标跟踪；遮挡；均值漂移；Ｋａｌｍａｎ滤波 文章编号：１００２－８３３１（２００７）１２－００５０－０３文献标识码：Ａ中图分类号：ＴＰ３９１．４ 基金项目：山东省自然科学基金（ｔｈｅＮａｔｕｒａｌＳｃｉｅｎｃｅＦｏｕｎｄａｔｉｏｎｏｆＳｈａｎｄｏｎｇＰｒｏｖｉｎｃｅｏｆＣｈｉｎａｕｎｄｅｒＧｒａｎｔＮｏ．Ｚ２００５Ｇ０３）。 作者简介：常发亮（１９６５－），男，教授，主要从事模式识别、机器视觉与智能控制的理论及应用研究；刘雪（１９８２－），女，硕士研究生，主要从事计算机视觉、图像处理与分析研究；王华杰（１９８０－），男，硕士研究生，主要从事机器视觉方面的研究。 ５０
LMS算法的稳定性分析和算法收敛条件
LMS 算法的稳定性分析和算法收敛条件 1最小均方法LMS 简介 LMS （Least Mean Square ）算法是Widrow 和Hoff 于1960年首次提出的，目前仍然是实际中使用的最广泛的一种算法。 LMS 算法是在最陡下降法的基础上实现的，它是维纳滤波和最速下降算法互相结合而生成的一种新的算法。通过维纳滤波所求解的维纳解,.必须在已知输入信号与期望信号的先验统计信息,以及再对输入信号的自相关矩阵进行求逆运算的情况下才能得以确定。因此,这个维纳解仅仅是理论上的一种最优解。但是通过借助于最速下降算法,LMS 算法以递归的方式来逼近这个维纳解,从而避免了矩阵求逆运算。 2LMS 算法的导出 在LMS 算法中用瞬时误差的平方来代替均方误差是LMS 算法最主要的思想,以瞬时误差信号平方的梯度作为均方误差函数梯度的估计。 在最陡下降法中其维纳解方程如下 (1)()k k k μξ +=-?w w （1-1） 其中ξk ?为梯度矢量，此时的 2[()]E e n ξ=, 此时取性能函数()n e 2=ξ来代替之前的性能函数， 则新的维纳方程变为如下形式 2(1)()()n n e n μ+=-?w w （1-2） 同时又可以求得 22 ()()()2()2()()e n e n e n e n e n n ???===-??x w w （1-3） 所以LMS 算法的权值更新方程可写成下式 (1)()()()n n e n n μ+=+w w x （1-4） 为了了解LMS 算法与最速下降法所得到的权矢量之间的关系,需要重写LMS 算法的递推公式，
因为)()()()(n w n x n d n e T -=代入LMS 算法的权值更新方程可得 )())()()()(()()1(n x n w n x n d n u n w n w T -+=+ 即)()()())()(()1(n d n ux n w n x n ux I n w T +-=+ 对上式求均值，又因为w （n ）和x （n ）不相关，所以 )] ()([)]([)])()([()]1([n d n x uE n w E n x n x uE I n w E T +-=+ （1-5） 其中互相关矢量 T L p p p n d n E ],...,,[)]()([121-==x p 自相关矩阵 ()()T E n n ??=??R x x 把P 和R 代入1-5式可得 uP n w E uR I n w E +-=+)]([)()]1([ （1-6） 由式1-6可知LMS 算法的权矢量的平均值E[w(n)]的变化规律和最速下降法的权矢量w(n)完全一样。最速下降法根据确定性轨迹沿着误差性能曲面计算权向量w(n),最后终止于维纳解w0。而在LMS 算法中,由于每步迭代过程中梯度估值是带噪的,因而权值运动轨迹并不是严格的与真正梯度方向一致。因此LMS 算法的解不是终止于维纳解。 3 LMS 算法的性能指标及性能分析 收敛性 收敛性,即当n 趋于无穷大时,让滤波器权矢量处于某个最优值或者在它的一个邻域范围内而不是越来越远,也就是让w(n)趋于w0所需满足的收敛条件。对任意自适应滤波系统,收敛性是实现其自适应功能的根本保证。 类似于最速下降法,定义权值误差矢量v(n)=w0-w(n),并利用 P=Rwo 。,则将式(1-6)写成v(n)的表达式为 )]([)()]1([n v E uR I n v E -=+ （2-1） 当R 为实数阵时有T =R Q ΛQ ,代入上式可得 )]([)()]1([n v E Q u I Q n v E T Λ-=+ (2-2)