基于gpu的粒子滤波并行算法

基于gpu的粒子滤波并行算法

贝叶斯估计目标跟踪问题被抽象为系统状态估计问题。当系统的状态方程是线性的，噪声是高噪声的时，根据卡尔曼滤波方法可以获得目标状态概率分布的分析解。然而，在实践中，许多非常复杂的状态估计问题包括非线性因素，而不是高斯噪声，因此很难获得分析形式的解。颗粒滤波算法是一种基于蒙特卡罗模拟的波叶斯滤波算法。它不受系统线性和高噪声的限制，广泛应用于定位导航、目标跟踪、建模等领域。近年来，我国对粒子滤波算法进行了多方面的改进，文献改进了粒子过滤的表观模型、运动模型和重新采样步骤，并在复杂场景（如累积涂层）下获得了更好的跟踪效果。采用自行时间分布模型，在目标处表达颜色分布，并使用gpu算法快速计算叠加图像以获得更好的性能。在文献中，我们提出了一种将各种特征整合到粒子滤波框架中的算法。一些文献提出了一种高速高斯颗粒滤波算法。目前，nb和nb是一个通用的计算结构，单个颗粒可以同时执行多个线程。运行过的程序称为ktl（内核函数）。cuda和gpu的组合可以分为电池和gpu。其中，cpu端程序是1946年接收头，负责调用和控制gpu的计算。gpu是真正的并行计算部分，是刀片的端。本文基于GPU的粒子滤波并行算法,将传统粒子滤波算法与GPU有效结合起来,充分利用GPU并行运算的性能,加快粒子滤波算法的计算速度.1实行并行算法粒子滤波就是采用一组加权采样来表示状态的后验概率密度函数.在实际应用中,一般采用目标的梯度直方图描述目标,采用Bhattacharyya距离计算候选区域颜色分布与目标模板颜色分布的相似性.为了避免序贯重要性采样后出现粒子退化问题,粒子滤波算法中加入了重采样(Resample)的过程.粒子滤波算法对图像每一帧处理的流程大致可以分为重要性采样、计算候选区域的颜色梯度直方图并给粒子赋权值、重采样以及最终目标的状态估计等步骤.纵观整个算法流程,粒子滤波算法并行化最大的基础是采样Ns个粒子,并对每个粒子进行相似的数据处理,因此重要性采样以及状态估计采用并行算法执行;由于粒子赋权值、重采样中存在数据相关,因此串行执行.基于GPU的粒子滤波并行算法流程如图1所示.建立4个Kernel函数分别实现粒子滤波的4个步骤.a.Prediction-Kernel该线程执行重要性采样步骤,其Kernel线程数与粒子数Ns相同,每个线程采样一个粒子.每个线程读入粒子数据,然后依据选取的重要性密度函数(这里采取随机游走模型),各自独立更改每个粒子的状态,完成对粒子的采样.随机游走模型中随机数的产生采用平方取中法,各个粒子之间不会存在数据干扰,可以得到最大化的并行性.b.Weight-Kernel该线程计算Ns个粒子的权值,由2个步骤串行实现:计算每个粒子所对应区域的梯度直方图;将每个粒子的梯度直方图与初始化时建立的模板直方图比较,求取巴特沃斯距离作为每个粒子的权值.这个步骤中的计算存在并行访问数据冲突,所以串行执行.实验发现,若将这部分放在CPU上运行,则会大大增加内存访问开销,运行速度比在GPU上直接计算要慢.c.Resample-Kernel该线程执行重采样步骤.依据上面的算法,对Ns个粒子进行重采样时,不可避免地会产生粒子间的数据关联,因此采用一个线程处理Ns个粒子的重采样,此方法的实现速度也比在CPU上要快.d.Calc-Kernel该线程执行目标运动状态估计,即对重采样后的粒子进行加权平均作为目标状态的最后结果.这里采用经典的并行规约求和算法,以充分发挥GPU的并行计算性能.相比其他串行求和算法,并行规约算法能够最大程度并行执行,从而有效加快运算速度,很容易移植到CUDA平台.该步骤有Ns个线程,每个线程处理一个粒子.算法的其他部分则由CPU来完成.算法开始时,CPU将每一帧的图像数据拷贝到GPU显存中,而GPU完成计算后,将计算出来的状态反馈给CPU,再由CPU在视频中显示出来并绘制该图像.程序实现中,采用纹理存储器存储每一帧图像数据,加快运算速度.2传统串归系滤波算法跟踪结果实验平台采用酷睿E2160,2GB内存,GPU采用NvidaGeForce8600GT,软件平台为VisualStdio2005.视频测试序列来源于PETS标准测试序列,分别为车辆跟踪(序列1,517帧)和人体跟踪(序列2,217帧),图像格式为CIF格式.对于视频跟踪而言,不同格式的图像序列,会因为图像尺寸的不同,而导致算法执行时间发生变化.图像尺寸越大,算法执行时间越长,因此这里只选用CIF格式的图像序列进行试验.图像颜色采用红蓝绿(RGB)空间,在第60帧手工完成初始化,真值由手工标注得到.图2和图3分别是粒子数为512时,传统串行粒子滤波算法分别对序列1和序列2中运动物体的跟踪结果.表1列出了当粒子数分别为256和512时,传统串行粒子滤波算法对序列1的跟踪误差与跟踪时间.表中:ex和ey分别为x和y轴坐标的跟踪误差;t¯t¯为平均每帧跟踪时间.从实验结果可以看出:增加粒子滤波的采样粒子数可以明显提高跟踪准确率,但增加了计算量,导致每帧处理时间大大增加.图4和图5为粒子数为512时,基于GPU的并行粒子滤波算法分别对序列1和序列2中运动物体的跟踪结果.表2列出了当粒子数分别为256和512时基于GPU的并行粒子滤波算法对序列1的跟踪误差与跟踪时间.对比表1和表2可以看出:2种粒子滤波算法在跟踪的准确性上差别不大,但是基于GPU的并行粒子滤波算法极大减少了每一帧的处理时间,加速比达到2.5.从表2还可以看出:采样粒子数对基于GPU的并行粒子滤波算法的跟踪准确性以及算法复杂度也有较大影响.进一步分析2种平台上粒子滤波算法每一步所用时间,结果见表3(测试序列为序列1).从表3可以看出:GPU上加速最明显的是并行实现的重要性采样和状态估计2个步骤.虽然权值更新和重采样步骤在GPU上串行实现,但由于GPU强大的运算能力,速度还是明显快于在CPU上串行实现.这2步也成为基于GPU的并行粒子滤波算法进一步加快的瓶颈.充分利用GPU的并行处理能力,在GPU上实现了粒子滤波跟踪并行算法,计算速度得到了明显提升.但在GPU上执行粒子滤波算法过程中,赋权