动态背景下基于帧间差分与模板匹配相结合的运动目标检测

高玉鹏，何明一

（西北工业大学 电子信息学院，陕西 西安 710072）

动态背景下基于帧间差分与模板匹配相结合的运动目标检测

高玉鹏，何明一

（西北工业大学 电子信息学院，陕西 西安 710072）

基于图形处理器单元（GPU）提出了一种帧间差分与模板匹配相结合的运动目标检测算法。在CUDA-SIFT（基于统一计算设备架构的尺度不变特征变换）算法提取图像匹配特征点的基础上，优化随机采样一致性算法（RANSAC）剔除图像中由于目标运动部分产生的误匹配点，运用背景补偿的方法将静态背景下的帧间差分目标检测算法应用于动态情况，实现了动态背景下的运动目标检测，通过提取目标特征与后续多帧图像进行特征匹配的方法最终实现自动目标检测。实验表明该方法对运动目标较小、有噪声、有部分遮挡的图像序列具有良好的目标检测效果。

信号与信息处理；CUDA-SIFT；目标检测；图像配准

目标检测是将感兴趣区域从背景中分离出来，它将目标的分割和识别合二为一，是运动图像分析、智能监控、月球探测中巡游导航、军事目标检测、人机交互技术中的一个重要环节。国内外对目标检测的研究已经取得了一定的成果。但对于动态背景、目标部分遮挡及光照变化较大的图像序列的检测效果还有待于提高。

按照目标和背景的相对运动差异，可以将目标识别分为静态背景和动态背景两种基本情况。目前研究相对成熟的方法是针对静态背景下的背景模型法、光流法和多帧差分法。以上方法能够有效地分割出运动目标，但多适用于静态背景[1]。背景模型方法将多帧图像与背景模型进行比较，通过判定灰度等特征的变化或用直方图等统计信息的变化分割出运动目标，因此首先要求背景不变。光流法给图像中每一个像素点赋予一个速度矢量，图像上的点与三维物体上的点一一对应，根据各个像素点的速度矢量特征对图像进行动态分析。这种方法计算量大、易受噪声影响。

文中利用在通用并行计算架构CUDA平台上开发的SIFT算法 （下文简称CUDA-SIFT）[2]，来提取两帧图像特征点，实现图像的准确配准。改进的RANSAC算法滤除目标运动带来的误匹配点，用过滤后的点来提取两图像中背景匹配部分，对其进行差分提取得到含有部分噪声的差值图像。通过背景补偿改进的两帧差分方法能够将研究相对成熟的静态背景目标检测应用于动态，该方法不仅计算量小、目标检测效果好而且通过对差分图像进行适当的处理能够达到比较理想的鲁棒性。再采用形态学方法剔除噪声提取出运动目标部分。在目标特征已知的基础上对余下多图像序列通过目标特征模板匹配来寻找目标，从而大大节省检测时间。因目标可能发生变化，故采用每20帧通过两帧差分的方法更新一次目标实现模板的自动更新，进而实现动态背景下的全自动目标检测。

1 序列图像动态背景下运动目标检测流程

文中算法采用CUDA-SIFT算法对两帧相邻图像进行特征提取，构建特征向量描述特征点信息，采用优先K-D树算法对特征向量进行搜索以进行特征点间的匹配，保证了特征点位置的精确性与匹配的准确性；然后采用改进的RANSAC算法去除因目标运动导致的误匹配，确保了图像配准的准确性，使图像配准的达到了亚像素精度，提高图像差分的鲁棒性；随后对精确配准的两幅图像进行差分，由于两帧图像中存在亮度变换以及采用线性放射变换处理非线性问题使得某些非目标区域像素点仍存在于差分图像中，致使差分图像中存在较大噪声，使用图像二值化和形态学的滤波处理方法滤除这些非目标像素点以解决差分图像噪声大的问题，处理后的图像中只存在前景的运动目标，至此完成了运动目标的检测。通过保留的目标特征模板与余下的帧图像进行特征匹配，从而实现剩余多帧图像中目标检测的目的，每20帧更新一次目标以达到运动目标自动检测。采用此方法避免了连续帧间差分需要不断配准导致检测效率低的问题，同时客服了特征匹配方法需要预先给定目标的缺点。流程如图1所示。

图1 目标检测流程图Fig.1 Target detection flow diagram

2 图像间单应性矩阵的鲁棒性求解及匹配

2.1 CUDA-SIFT算法的特征提取及描述

CUDA是一种通过使用并行编程模型，充分利用GPU硬件架构来对可并行化处理的数据及任务进行并行处理的软件环境，通过并行计算大大提高处理速度[3]。本文通过对特征提取中经典的SIFT算法进行并行化设计，并对算法进行改进从而达到快速目标检测的目的。CUDA执行流程如图2所示。首先将图像从内存中传入到GPU的Global Memory中，将图像分成的block块，通过设定并行处理函数将每个图像块并行的转化为灰度图像进行图像的预处理。使用唯一的线性高斯核对图像进行并行的卷积处理，由以下两个公式可知可以将高斯滤波进行X方向和Y方向的分块并行处理，进而得到图像大小的尺度空间。

图2 GPU-SIFT特征点提取流程图Fig.2 GPU-SIFT feature point extraction flow diagram

通过公式进行差分得到DOG图像层：

其中（x，y）代表图像的像素位置；σ为尺度空间因子，大尺度对应于图像的盖帽特征；小尺度对应于图像的细节特征。L表示图像的尺度空间；G（x，y，σ）为尺度变换唯一变换核的二维高斯函数[4-5]。

将图像的尺度空间存储到纹理存储器内，并通过快速的图像缩放来完成高斯金字塔的建立 （纹理内存能够享受GPU[6]内部针对二维数据访问优化的纹理缓存，从而在随机存取的环境下保持较高的性能，另外，纹理内存还能享受硬件的双线性插值，从而完成需要的图像缩放操作[7]。）并行检测差分金字塔的每一个像素，通过检测局部极值点近似确定关键点，通过一个的Hessian矩阵计算特征值的比率，检测关键点主曲率是否超过阈值，从而确定关键点为特征点并记录关键点的位置及尺度，传回Host端进行进一步处理。为了提高运算速度同时尽量减少匹配误差，利用文献 的方法提取更有效的特征点从而减少不必要的冗余特征点的计算，节省运算时间。

采用优先K-D树进行特征点的匹配，对于某一特征向量，比较最近邻到它距离与次近邻到它的距离，如果距离之比小于预先设定的阈值，认为该最近邻是较好的匹配。将阈值设为0.7时匹配的正确率较高保证了特征点位置的精确性与匹配的准确性。

2.2 RANSAC方法剔除运动目标引起的误匹配点

动态背景下的运动目标检测难点在于问题中含有多种运动，由于相机的移动使得背景发生变化，背景变化的同时运动目标也在相对于背景运动，这是问题的难点所在。单纯的特征点匹配只是解决了背景区域的匹配问题，但由于背景区域内也同时存在物体移动，因此传统的目标匹配方法无法实现图像的配。因此本文针对这个问题采用比较典型的具有鲁棒性估算的RANSAC算法对匹配点对进行提纯，剔除匹配区域内运动目标带来的误匹配点，从而实现良好的图像匹配效果，为接下来的工作奠定基础。RANSAC算法首先给定N个数据点组成的数据集合P，其中大多数是由一个参数未知的特定模型产生的，该模型的参数至少需要n个数据点求出（N>n）。算法的目的就是求出这个模型的参数。将下述过程运行k次：

1）从P中随机选取含有n个数据点的子集S1。

2）由所选取的n个数据点计算出一个模型H1。

3）对数据集合中其余的N-n个数据点，计算出它们与模型H1之间的距离，记录在H1的某个误差允许范围内的P中数据点的个数c。

重复上述步骤直到对应最大c值的模型即为所求模型，数据集合P中的这个数据即为内点 （所谓内点就是在RANSAC算法下认为是正确匹配的点），其余的N-c个数据点即为外点（所谓内点就是在RANSAC算法下认为是没有正确匹配的点包括：背景不重叠的部分及运动物体部分）[7]。至此完成了对特征点对的提纯。

从RANSAC提取的稳定的特征点对中任意从内点中选取两个特征点对（x，y）与（x′，y′）利用公式：

计算出ai共7个自由度，就可以确定一个变换矩阵H。求得的变换矩阵H，通过公式：

就把第二幅图像通过放射变换矩阵一一对应地映射到一幅新图像上。从而去除了由相机平移和旋转等给图像带来的几何变换，最后通过特征区域的计算提取出两幅图像上包含运动物体的相同背景区域，至此完成了图像匹配。

2.3 运动目标模板提取

对上一节中提取包含运动目标区域的背景重叠部分两幅图像采用公式：

进行差分，D（X，Y）为差分后的图像， f1（x，y）和 f2（x，y）分别为从两幅原始图像中提取出来的匹配部分。通常经过差分后会得到比较明显的运动目标区域，然后再通过公式：

对图像进行二值化，其中T为给定阈值，差分图像D（X，Y）经过阈值分割得到二值化后的图像D′（X，Y）。由于二值图像中含有噪声点干扰目标提取，因此对图像进行核大小为的中值滤波从而消除小噪声，达到对图像平滑的目的。再使用正方形的结构元素通过公式：

扫描二值图像中的每一个像素，用结构元素与其覆盖的二值图像做“与”操作，如果都为0结果图像的该像素为0，否则为1。对二值图像进行膨胀操作，其中为的结构元素，为图像元素，使结构元素沿着图像移动，若有交集则为白色像素，用以清除目标中不连续的空洞，使运动目标区域更加明显。随后对二值图像中像素为的点进行轮廓提取并记录轮廓的大小和位置，由于在二值图像中可能还会存在小区域的噪声，因此在运动目标标示的时候选择大于16的区域进行标示。至此完成了动态背景下的运动目标检测。将检测到的运动目标作为模板一一保存起来，应用到后续帧中的目标进行检测，从而大大提高图像序列运动目标检测速度，降低算法复杂度。

2.4 模板匹配提取运动目标

模板匹配是在一幅尺寸比较大的实时图像中寻找一幅尺寸较小的参考图像的过程，实现在图像中实时定位目标的目的。

本文通过保存经过背景差分提取的目标的SIFT特征向量与在图像序列中提取的SIFT特征向量进行匹配来提取运动目标，经过RANSAC[8]误匹配点的剔除提高匹配精度。通过权值平均法进行中心点定位、标示运动目标。如果剩余的图像中匹配点少于3个直接对特征点坐标求均值得到近似目标中心；对于匹配点较多的情况时，从第一个点开始进行聚类，在其的邻域内查找是否有其他特征点，有几个特征点则权值设为几求出横、纵坐标均值，对剩下的点依此类推进行计算，通过权值平均最终求得中心。此方法有效克服了由于个别匹配点离中心较远而造成的标示不准确问题。下表为对最典型的3种特征匹配方法进行的研究，分别使用这3种方法对同样两幅图片进行特征匹配，得到其运行时间及提取的特征点数目，分析比较最适合于本系统的方法。

表1 各算法进行特征匹配的时间Tab.1 Time of various feature matching algorithms cost

本实验在曙光W580I服务器上调试运行，对的图像进行特征检测与匹配。由实验可知，CUDA-SIFT算法特征匹配速度最快、特征点稳定，而且目标提取算法过程中以对目标部分特征进行提取并保存，因此本部分同样采用CUDA-SIFT算法进行模板匹配从而达到良好的系统一致性及实时性。

3 实验结果

为了验证本文提出的基于特征点的动态背景下序列图像运动目标提取的有效性，在Microsoft VS2008开发平台下通过CUDA、OPENCV及C语言的混合编程实现了本文中的相关算法。我们也用真实的图像序列验证了系统的可行性。

图3 两帧差分目标提取部分的检测结果Fig.3 Results of object extraction from two differential frames

实验1与2均为相机水平方向拍摄，实验1为摄像机只有平移变换情况下的运动目标检测，检测效果比较理想。实验2为摄像机同时具有平移和旋转变换而且运动目标有部分遮挡情况下的识别，对目标有部分遮挡及摄像机各种运动鲁棒性较高。由实验1和2的结果可知该算法可应用于车载摄像设备也可应用于反坦克导弹等武器装备中的运动目标检测。实验3为高空拍摄的图像。该实验表明本方法可应用于高空监视中地物目标锁定，在武器装备中的精确制导领域具有较强的实用价值。

图4 目标匹配检测结果Fig.4 Target matching results

4 结束语

文中实现了一种基于两帧差分及特征匹配方法的目标检测方法。该方法可以实现动态背景下图像序列的自动目标检测，并且在较短的时间内达到了比较良好的检测效果。SIFT算法保证了提取特征点位置的精确性与匹配的准确性，改进的RANSAC算法保证了图像配准差分的稳健性。采用目标特征匹配的方法大大节省目标检测时间并提高了部分遮挡目标提取的鲁棒性，从而实现了通过两帧差分更新并保存目标，再进行特征匹配提取目标的动态背景下序列图像自动目标检测。该算法采用两帧差分方法与模板匹配相结合的方法进行目标检测，克服了两帧差分法检测效果不稳定图像质量要求高及模板匹配方法对目标先验知识的要求，从而实现动态背景下的运动目标自动检测。

[1]Liao S K，Liu B Y.An edge-based approach to improve optical flow algorithm[C]//The 3rd International Conference on Advanced Computer Theory and Engineering，2010:45-51.

[2]田文，徐帆，王宏远.基于CUDA的尺度不变特征变换快速算法[J].计算机工程，2010，36（8）；219-221.

TIAN Wen，XU Fan，WANG Hong-yuan.Fast algorithm of Scale-invariant feature transform base on CUDA[J].Computer Engineering，2010，36（8）；219-221.

[3]王瑞，梁华，蔡宣平.基于GPU的SIFT特征提取算法研究[J].现代电子技术，2010（15）；41-43.

WANG Rui，LIANG Hua，CAIXuan-ping.SIFT feature extraction algorithm research based on the GPU [J].Modern Electronic Technology，2010（15）：41-43.

[4]Lowe D G.Distinctive image features from scale-invariant key-points[J].International Journal of Computer Vision，2004，60（2）:91-110.

[5]韩龙，郭立，李玉龙.SIFT算法的并行实现及应用[J].计算机工程与应用，2010，46（20）：57-67.

HAN Long，GUO Li，LI Yu-long.SIFT parallel implementation and application of the algorithm[J].Computer Engineering and Application，2010，46（20）：57-67.

[6]张晓东，孔祥辉，张欢阳.利用GPU实现SAR图像的并行处理[J].电子科技，2011（11）：94-95.

ZHANG Xiao-dong，KONG Xiang-hui，ZHANG Huan-yang.Parallel imaging algorithm of synthetic aperture radar based on GPU[J].Electronic Science and Technology，2011（11）：94-95.

[7]NVidia CUDA C Programming Guide 3.2[EB/OL].[2010-10-22].http://developer.download.nvidia.com.

[8]Ondrej C，Jiri M.Optimal randomized RANSAC[J].IEEE Transactions on Pattern Analysis and Machine Intelligence，2008，30（8）:1472.

Moving target detection combined two frame differences with template matching methods under dynamic background

GAO Yu-peng，HE Ming-yi
（College of Electronics andInformation，Northwestern Polytechnical University，Xi’an710072，China）

A moving target detection algorithm is presented which combined frames difference with template matching methods based on Graphic Processing Unit （GPU）.The method firstly utilizes CUDA-sift （a fast SIFT algorithm based on Compute Unified Device）algorithm to extract feature point of the matching image.Then， Random Sample Consensus （RANSAC） is optimized to remove the false matching points due to the part of the moving target.Put frames difference method under static background into dynamic setting using backdrop compensation method.Achieved the moving target detection method under dynamic background，extracting the feature of target to process character mating with the follow-up graphic finally realize automatic target detection.Experiments show that the method has favorable result of target detection for small moving target，little noise，some occlusion of image sequence.

signal and information processing； CUDA-SIFT； target detection； image registration

TP391.4

A

1674－6236（2012）05-0142-04

2012-01-17稿件编号：201201072

高玉鹏（1985—），男，黑龙江绥化人，硕士研究生。研究方向：信号与信息处理。