基于FPGA的Lucas?Kanade算法优化

　　摘要： 在FPGA平台上实现基于光流法的视频运动目标跟踪系统,采用Lucas?Kanade算法进行光流场的计算,在图像预处理阶段提出使用三维高斯滤波代替传统二维高斯滤波,引入相邻像素点在时间轴方向的相关性,增强图像的滤波效果。在3D导数计算阶段提出在求导方向的正交面上进行平滑滤波,并采用匹配的导数和平滑参数,提高光流场计算精度。在FPGA平台上设计多级主流水线加子流水线结构,设计了四端口RAM进行图像缓存,优化了最小二乘矩阵单元和浮点数运算单元,实现了实时视频运动目标跟踪。

　　关键词： Lucas?Kanade算法; 平滑滤波器; FPGA; 四端口RAM

　　中图分类号： TN 253; TP 212.14文献标志码： Adoi： 10.3969/j.issn.1005?5630.2014.03.005

　　The optimization of the Lucas?Kanade algorithm based on FPGA

　　LIU Dongming, LIU Chao, MU Haiwei

　　(College of Electronic Science, Northeast Petroleum University, Daqing 163318, China)

　　Abstract： Video motion tracking based on optical flow is implemented on the FPGA, and we calculate the optical flow taking advantage of the Lucas?Kanade algorithm. In the stage of the image preprocessing, we propose that three?dimensional Gaussian filter is used to replace the conventional two?dimensional Gaussian filter and the correlation of the adjacent pixels is introduced, which improves the effect of the image filter. In the stage of 3D derivative calculation, we implement the smoothing filter on the orthogonal plane of derivative directional, and use the matching derivative parameter and smoothing parameter, so the accuracy of the optical flow is improved. Based on the FPGA platform, we design multistage pipelined architecture that includes several sub?pipeline, the four?port RAM unit that can achieve images cache, and optimize the least?square matrices and the float unit, which achieves the real?time video motion tracking.

　　Key words： Lucas?Kanade algorithm; smoothing filter; FPGA; four?ports RAM

　　引言光流法是实现运动目标跟踪的一种有效方法,光流法的优势在于没有图像背景的历史信息情况下,可以对独立运动目标进行跟踪,而且在动态背景情况下同样适用。但光流法易受噪声影响,而且运算量大,因此在硬件实现上,存在着计算精度和系统资源占用之间的矛盾。FPGA是一种资源配置灵活,不限制流水线级数,可实现全并行处理的一种器件,非常适合作为视频运动目标跟踪系统的硬件平台［1?2］。本文采用LK(Lucas?Kanade)算法在FPGA平台上实现光流场的计算,提出了三维高斯平滑滤波方法,改善图像噪声抑制效果,改进了传统3D导数计算方法,采用非高斯匹配导数滤波器,提高了光流场的计算精度。硬件方面,在FPGA平台上设计了超级流水线结构和四端口图像缓存单元,实现了对30帧/s速度下640×480分辨率视频的实时运动目标跟踪。1LK算法优化LK算法是一种计算光流场的差分方法,也就是计算图像在空间和时间坐标上的偏导数。假设I(x,y,t)为(x,y)点在t时刻的灰度值,像素点的对应速度为v=［vx,vy］,为满足光流约束方程,需使下式最小［3］:ε=∑x∈ΩW2(x)［I(x,y,t)?v+It(x,y,t)］2(1)其中,W(x)代表一个窗函数。上式的结果为v=［ATW2A］－1ATW2b,其中,A=［I(x1),…,I(xn)］T,W=diag［W(x1),…,W(xn)］,b=－［It(x1),…,It(xn)］T进一步推导得:ATW2A=∑W2I2x∑W2IxIy

　　∑W2IxIy∑W2I2y(2)

　　ATW2b=－∑W2IxIt

　　∑W2IyIt(3)光学仪器第36卷

　　第3期刘东明，等：基于FPGA的Lucas?Kanade算法优化

　　根据LK算法公式,光流场的计算包括三个步骤:一是图像预处理,即通过高斯平滑滤波来降低图像噪声,并使相邻像素之间产生较高的相关性;二是3D导数计算,即通过合适的核(滤波模板)进行3D导数滤波,计算3D导数;三是计算最小二乘矩阵,得到各个像素点在x轴和y轴的速度分量。(1)图像预处理算法优化传统的图像预处理一般是对图像进行二维高斯平滑滤波,但是视频是一系列时间上连续的图像,各个像素点之间除了空间关系外还存在时间上的关联性。因此,本文提出在传统二维高斯滤波基础上增加时间轴滤波,构成了三维高斯滤波。根据高斯滤波模板的旋转对称性,这种扩展是可行的。以宽度为5的高斯滤波模板［1，4，6，4，1］/16为例,为了减少计算量,首先对连续5帧图像进行一维时间轴滤波,得到一帧图像,再进行传统二维5×5空间滤波。图1(a)为使用5×5二维高斯滤波模板的滤波效果,作为对比图1(b)为使用5×5×5三维高斯滤波模板的滤波效果,可看出后者的模糊效果明显好于前者。三维高斯滤波有效地降低了噪声,提高了相邻像素之间的相关性。

　　图1图像滤波效果

　　Fig.1The effect of image filter

　　(2)3D导数算法优化3D导数的计算关系到光流场的计算精度,3D导数就是通过导数滤波器分别计算图像在x轴、y轴和t轴的导数Ix、Iy和It。传统图像求导方法比较简单,即导数核直接与图像进行卷积,例如可使用导数核［-1 1］,分别在求导方向上与图像进行卷积。这种对图像求导的传统方法导致光流场计算结果不准确,图2(a)是这种方法下光流场的计算效果,可以看出速度的方向错误率较高,另外像素点速度大小也出现了较多的错误。为改善光流计算精度,本文提出将Sobel算子思想应用到3D导数计算中。Sobel算子垂直卷积核［4］表达式为－101

　　－202

　　－101=121T?－101(4)根据式(4)可知Sobel算子的核心是在x轴方向求导的同时在y轴方向平滑滤波,将这种思想扩展到3D导数计算中,即在某一方向上求导时,在其他两个方向上进行与之匹配的平滑滤波。例如求x轴方向的导数Ix,需要在y轴和t轴进行平滑滤波。另外滤波模板并没有选择高斯模板,而是采用了Simoncelli提出的非高斯匹配滤波模板［5］,其中:导数滤波核 ［-0.109 604,-0.276 691,0,0.276 691,0.109 604］平滑滤波核 ［0.037 659,0.249 153,0.426 375,0.249 153,0.037 659］图2(b)是经过优化的非高斯匹配3D滤波下光流场的计算结果,与传统方法相比,光流场速度大小的精确度和速度方向的一致性得到了明显改善。

　　图2光流场计算结果

　　Fig.2The results of optical flow

　　2FPGA流水线结构设计FPGA不限制流水线级数,可实现全并行计算,非常适合做高速实时视频处理。在FPGA平台(DE2)上实现LK算法的视频实时处理的关键在于流水线结构的合理设计,LK算法流水线结构如图3所示。

　　图3LK算法流水线结构框图

　　Fig.3The pipelined architecture of LK algorithm

　　FPGA平台上,LK算法分为五个步骤:(1)三维高斯平滑滤波,摄像头输出的视频图像中经常伴有噪声,经过前面仿真可知,采用三维高斯滤波能起到良好的滤波效果,经试验采用3×3×3高斯模板即可满足后续计算光流场的精度要求。(2)时间FIR滤波,3D导数计算中有两个步骤需要进行时间轴FIR滤波:一是计算时间轴导数It,二是计算空间导数Ix和Iy时,需要在时间轴进行平滑滤波。将这两个步骤结合起来,可一步完成,降低了FPGA资源占用率。(3)空间FIR滤波,同样分为两种情况:一是计算It时在xy平面上进行平滑滤波,二是计算导数Ix和Iy。(4)最小二乘矩阵,用于计算光流速度公式中的Ix?Ix、Iy?Iy、Ix?Iy、Ix?It和Iy?It。(5)浮点运算单元,通过上述结果求得光流场。整体上LK算法的流水线结构分为五级,每级流水线内部也包含了优化的子流水线结构,图中标出了各级中包含的子流水线数量。图像在时间轴方向的滤波需要帧间处理,因此采用SDRAM作为图像缓存。步骤(1)中时间轴的平滑滤波与步骤(2)中时间轴FIR滤波结构相同,只是滤波核不同。由于时间轴滤波后图像数据量大大减少,仅一帧数据,因此在这两个步骤中均采用了先时间后空间的滤波顺序。图4四端口RAM实现框图