一种基于帧差分法与快速图分割相结合的运动目标检测方法

陈　佳，朱长仁，钱智明

（1.国防科学技术大学 电子科学与工程学院 ATR重点实验室，湖南 长沙　410073；2.武警福建总队直属支队，福建 福州　350001）



一种基于帧差分法与快速图分割相结合的运动目标检测方法

陈佳1，2，朱长仁1，钱智明1

（1.国防科学技术大学 电子科学与工程学院 ATR重点实验室，湖南 长沙410073；2.武警福建总队直属支队，福建 福州350001）

摘要：针对在处理复杂场景情况时，帧差分法在预处理后获取的目标区域往往会空洞化或者分裂成多个互不相连的部分，计算机难以实时判断多个部分是否同属于一个目标，为此，提出一种基于三帧差分法与快速图分割相结合的运动目标检测方法。首先对序列图像做三帧差分运算及基于图的快速分割；然后通过定义融合判定规则，将帧差分结果同图像分割的区域块进行互相补充和约束；再对符合判定规则的子区域块进行合并，最终精确提取出运动目标的位置及轮廓。实验结果表明该方法能够有效提高目标检测的完整性。

关键词：目标检测；帧差分；图像分割；最小生成树；视频监控

0　引言

运动目标检测一直是视觉应用视觉领域一个重要的研究课题，无论在军用还是民用领域都有着广泛的应用[1]，尽管不同的运动目标检测算法已经广泛地应用于多个行业，但其仍然存在各种不足，其精确性和有效性还在不断改进和完善之中。常用的运动目标检测方法有光流法、背景减除法、帧差分法等[2]。光流法的检测效果比较好，但计算复杂度高，对系统硬件要求比较高，常用于对录制后的视频进行分析。背景减除法通过对视频背景预先建模，在对运动目标进行检测时，采用预存的背景模版减去当前帧的方法，从而提取出运动目标，但该方法对背景更新算法提出了较高的要求，如背景变化较大则难以达到预期效果。帧差分法计算简单、实时性高，在实际应用中实现起来最为便捷，但是其往往提取出的目标轮廓精确性及稳定性不够，难以达到目标检测要求。

早在2004年，文献[3]就针对道路上的车辆识别提出了把帧差分同彩色图像分割相结合的运动目标提取方法，该方法采用聚类分割并通过设立一个阈值对分割后的子区域进行合并，最终形成完整的目标轮廓，但是该方法无法确保子分割区域能够刚好合并成完整的目标图像，且计算量大、稳定性不高。文献[4]提出了把三帧差分法同图像边缘检测相结合来提取运动目标的方法，但是边缘检测往往得到的是不连续的边缘，甚至出现虚假边缘，给最终检测结果带来不确定性。文献[5]提出了基于帧差法与不变矩特征相结合的运动目标检测方法，但是该方法要求首先定义拟跟踪的目标类型并提取其不变矩特征，在复杂情况下难以对未知目标进行检测。文献[6]提出了帧差分法同光流法相结合的运动目标检测算法，但是对于重叠目标处理能力不足。文献[7]通过设定一个融合规则，度量帧差分图上每个目标区域之间的距离、运动方向、速度等参数，进而判定多个分裂区域是否同属于一个独立目标，但是该方法计算复杂且建立在长时域分析的基础上。

尽管有各种方法试图解决上述问题，然而，迄今为止，基于帧差分同区域分割相结合的运动目标检测方法及其研究论述一直比较少见，主要原因有两点：一是图像区域分割方法理论及研究虽然丰富，但是绝大部分方法都是针对特定情况下解决特定的问题，没有一个通用的准则，分割精度越高，硬件系统的计算开销越大；二是大多数分割方法仅仅从图像的颜色、纹理相似性出发，或者结合局部区域特征来考虑问题，缺少基于人的视觉、理解、心理认知等因素，导致机器判断的分割区域往往同人的肉眼判断有较大的差异。

针对帧差分法的不足之处，本文提出了一种基于三帧差分法与基于图的快速分割相结合的运动目标检测方法。在对目标进行检测时，可以有效地提高检测结果的完整性。

1　基于帧差分法的运动目标检测方法

帧差分法（Frame⁃difference）是一种最简单的运动目标检测方法，它能快速地发现并提取出运动目标所在区域，其原理介绍如下。

1.1两帧差分法

两帧差分法的原理如下：在视频图像序列中任选取连续的两帧图像，将当前帧图像表示为Fk(x,y)，(x,y)表示图像上点的横坐标与纵坐标，前一帧图像表示为Fk-1(x,y)。首先计算当前帧与前一帧的差分图像，其公式为：

式中FD(x,y)为得到的目标区域的变化量，再通过简单的数学形态学开闭运算使得运动目标区域连续，同时去掉背景中的噪声，最后选取合适的阈值T，对结果图像进行二值化，其公式为：

1.2三帧差分法

三帧差分算法（Three Frame Difference）是一种在两帧差分方法上改进的算法，其原理是利用连续三帧图像前后两两相减，再把所得的两幅帧差分结果做逻辑与运算，最后再通过形态学运算去噪并进行二值化。下面分别用Fk-1(x,y),Fk(x,y),Fk+1(x,y)表示连续的三帧图像，其原理用公式表示如下：

1.3帧差分法的不足之处

三帧差分法得到的目标检测区域图，如图1所示。可以看到，在三帧差分法中，预处理后的图片目标区域被分成了多个互不连通的区域，在进行实时目标检测时，计算机难以判断多个区域是否同属于一个目标。

图1　序列图像三帧差分结果

无论是两帧差分法还是三帧差分法，在实际应用中都存在不足之处：两帧差分法得到的目标轮廓往往大于目标的真实轮廓，运动目标速度过快或过慢时，会存在重影或空洞现象；三帧差分法通常能够比二帧差分法更精确地得到运动目标的位置，但是在目标速度过慢或目标内部颜色纹理比较平均的情况下，其提取出来的轮廓区域仍然会空洞化并割裂为多个互不相连的部分，为图像的后续处理增加了难度。针对此，提出了基于图像区域分割与帧差分结果相结合的办法（详见第4节内容），进行目标完整性的有效判断。

2　基于图理论的图像快速分割方法

2.1图像分割介绍

图像分割[1]是图像处理领域和计算机视觉中的一个基本而关键的问题，它是将图像分成各具特性的区域并将人们感兴趣的目标（或运动目标）提取出来的过程，可为后续的分析、理解、分类、跟踪、识别、处理等提供依据。

图像分割的形式多种多样，有时需要将一幅图像分割成一个个可识别的目标，类似于人对图像的感觉一样，而有时需要将它划分成若干具有某种一致性的区域，如色彩的一致性，纹理的一致性等，作为底层视觉处理的一部分。实际对图像分割时，图像的哪些部分重要，人们又对哪些部分感兴趣，需要根据具体的应用而定。

图像分割方法[8]大致可以划分为三个类别：基于特征空间（Feature⁃space based）的方法、基于图像空间（Im⁃age⁃domainbased）的方法以及基于物理特征（Physics based）的方法，每个类别可以继续细分。本文主要介绍基于图理论的快速图像分割方法。

2.2基于图划分理论的图像分割方法

基于图理论的分割算法近年来发展很快[9]，特别在实际应用中，无论在灵活性上还是计算复杂度上都不断改善，显示出越来越大的适应性。基于图划分理论的图像分割方法使用加权图G(V,E)，其中V为图的有限节点Vi的集合，E为有限边Ei的集合，Eij表示具体连接两个节点的边，Wij表示边的属性（边上的权重），即对应像素之间的差别或相似性（颜色、强度等）。图像到图的映射，如图2所示。

图2　图像到图的映射

在把图像映射到图之后，可以把图论中很多成熟的理论和数学工具应用在图像分割上，比如基于最小生成树（MST⁃based）、最小割/最大流（MinimumCut/Maximum Flow）、归一化切割（Normalized Cut）、图谱（Spectral Graph）以及能量最小化的理论。单从使用理论方法的角度看，可以将基于图划分理论的分割方法分为基于最小生成树方法、最小割/最大流方法、谱方法等。

2.2.1最小生成树方法

最小生成树法是通过计算图像中的最小生成树来寻找差异最小的连通区域的分割算法。该算法将整幅图像按相邻边的像素差生成一棵MST，再用动态规划的方法将MST划分成像素值较为均一的几部分。最小生成树的实现算法通常有Kruskal算法、Prim算法、Boruv⁃ka算法以及混合算法等。

2.2.2基于图理论的快速分割方法

基于图的快速分割方法（Efficient Graphic based Segment）是Felzenszwalb P F于2004年提出的[10]，属于最小生成树方法之一。该算法优点在于既具有超像素分割的精确性，分割时不仅能够区分同质区域，比如颜色、纹理等，又能够依据人的视觉感官原理，对中间拥有平缓过渡部分的两种颜色作出归一化划分的判断。该算法的原理为：设带权图G(V,E)，图G中生成树T上的权重和为ω(T)，公式如下：

式中：ω(T)最小生成树为图G的最小生成树。若C是分类集森林中的任一集合，其对应的最小生成树记为MST（C，E），则集合C的内部差异（Internal Difference，Int）被定义为最小生成树中最大的权值，即：

集合C1,C2之间的差异（Difference，Dif）为连接这两个集合边的最小权重，即：

为了定量描述且评价两个邻域间是否存在边界，该算法定义了区域比较谓词D（Region Comparison Predi⁃cate，D）这个概念。D通过对区域内部差异和区域间差异进行比较，使得最终的分割结果能够自适应图像数据的局部特征。若Dif（C1，C2）大于Int（C1），Int（C2）中的任何一个，则认为C1,C2之间差异较大，应将C1,C2对应的图像区域视为不同区域；否则，应将C1,C2对应的图像区域合并。

为控制判决门限，即Dif（C1，C2）与Int（C1），Int（C2）到底差别在多大量时，才认为是区域间存在着明显的差异，该方法引入了一个阈值函数r（C），定义的分割判决式为：

其中：MInt(C1,C2)=min[Int(C1)+τ(C1),Int(C2)+τ(C2)],τ(C)=;阈值函数τ(C)是一个关于连通分量大小的函数；表示连通分量的大小，也可以认为是C集合中的元素数目；K是一个供输入的参数（常数）。阈值函数τ(C)是用来控制该算法可能会引起过分割产生的小区域。常数K越大，则抑制小区域的效果越明显，也即分割后的区域面积较大；反之，则分割后的小区域较多。

运动目标场景分割效果，如图3所示。可以看出，基于图的快速分割算法（Efficient Graph⁃based Segment）能够把自然场景中各种物体的区域块及相似部分很好地提取出来，在分割精度和计算效率上都能够达到令人满意的要求。虽然计算机无法直接从分割结果中独立判断出运动目标，但是其清晰的区域划分及完整的局部轮廓为结合其他方法进行更高层次机器视觉分析工作提供了一个良好的基础。

图3　运动目标场景图分割效果，分割区域随机上色

3　图像分割与三帧差分相结合的运动目标检测方法

帧差分法容易确定运动目标的精确位置，但是往往得到断裂的目标区域轮廓，无法有效判定目标的完整性或数量，图像分割的方法虽能够精确地标示出图像中的同质区域，但是无法独立从中提取出拟观察的目标，针对它们各自的优点和不足之处，本文提出一种基于两者相结合的运动目标检测方法。

3.1图像分割与三帧差分相结合的运动目标检测方法

本文提出的方法是结合图像分割和帧差分信息，对割裂的目标进行有效的完整性识别，步骤具体如下：

（1）对原视频序列中间一帧的原始图像采用图割方法做区域分割，分割的区域标记为An（A1，A2，A3，…），如图4所示。

图4　图分割区域标注及帧差分区域标注

（2）用三帧差分法求得的所有目标变化区域，区域标记为Bn（B1，B2，B3，…）

（3）求出An中所有包含Bn的相交区域（即任取Bn，它所对应的从属于An的区域）用Cn来表示。公式表示为Cn=An（当且仅当Bi∈Ai时），如图5所示。

（4）计算Cn内所有区域两两之间的邻接性，对存在任一邻接关系的区域进行区域合并，最终得到的独立区域的数量为目标存在的数量，如图6所示。至此，目标判定结束，通过完整性识别，最终无法合并的独立区域的个数即为目标的个数。

该算法主要是针对三帧差分法和图像分割方法各自的优势和不足，通过将两者结合起来，在信息上互相补充及约束，以实现对运动目标的完整性识别。下面选择三帧差分法进行算法实验比对，图6（a）为三帧差分法目标检测结果，图6（b）为采用本文判定规则后得到的目标检测结果，从中容易看出三帧差分法把一个目标分割成多个子块，而提出的算法能够提取完整目标。

图5　计算交集区域及区域合并

图6　三帧差分同本文算法目标检测对比

3.2运动目标检测系统流程

图7为目标检测系统的流程图。

图7　目标检测系统流程图

该流程如下：

（1）进行图像预处理，包括帧差分运算及第二帧图像的分割运算；

（2）运用本文给出的算法进行完整性判断，求出目标的轮廓区域；

（3）输出结果，并根据程序运行需要决定是否结束检测或继续进行循环检测。

4　实　验

本实验旨在证明一种帧差分同区域分割方法相结合的目标检测方法的有效性，为此随机选取了30组基于固定摄像头的运动目标场景视频进行测试（部分数据集选自changing detection国际会议2014年公开数据集，部分选自视频网站），包括室内环境，室外环境，近景，远景，夜间红外条件，对象包括大型机械，动物，人等。实验环境为 Dell PC，intel i7⁃3770处理器，8 GB内存，Windows XP操作系统，VC 2008平台，其中4组视频实验流程及结果展示如下。

图8（a）为原视频图像序列中第二帧图像，图8（b）为原视频图像序列三帧差分结果，图8（c）为第二帧图像进行快速图分割的结果，图8（d）为用本文提出的方法求得的相交区域，图8（e）为最终区域合并的结果，图8（f）为Matlab中用连通区域检测函数确定的目标（用外接矩形框表示）。

图8　4组随机视频序列图实验

为了评估检测效果[11]，图9（a）中定义目标真实区域为S，本文算法检测到的区域为T，真实有效检测区域为R（R=S∩T），单个目标检测有效率表示为，30组序列图像评估结果如图9（b）所示，平均检测有效率大于90%。对所有测试视频，本文提出的算法均能对运动目标进行良好识别，但是也存在一些不足之处：在进行完整性判定时，运动目标的阴影部分无法自动排除在外，当背景颜色同运动目标过于接近时，有可能把部分背景区域误判为运动目标轮廓区域，导致检测到的面积大于运动目标的实际面积。此外，帧差分的结果中，如果运动目标断裂的区域面积显示不足或分布不均匀，会导致最终检测到的目标区域小于目标的真实区域。

不同尺寸序列图像用本文算法的平均处理时间，如图10所示，图像越大所需计算时间越多，但是对于450× 375的视频图像，处理速度在2 s左右，这就为接近实时的智能应用系统的开发提供了可能，限于实验条件，本文仅给出将来进一步改进本算法可采取的方案：提升现有硬件配置；对算法进行改造，采用多核或分布式运算[12]；根据特定场合的需求在检测运算中缩小视频图像尺寸以检测速度。

对于图像分割来说，K,M等参数的选取对本文算法效率也有直接影响，首先对分割运算时间有直接影响，但是这种影响是非线性的，选取不同K,M参数对图像分割时间影响的波动范围通常小于图像分割总时间的10%，其次，因K,M取值导致过细或过粗的分割会影响到最终检测区域面积小于或大于目标的真实面积，但是对于特定场景，特定的视角，特定焦距的监控视频，一般能够通过实地测试筛选合适的K,M参数，使得在该参数下分割能取得最适宜的效果，以便于后续进行目标完整性识别的计算。

图9　目标检测有效率评估

图10　算法平均运行时间统计

5　结　语

本文主要探讨了利用帧差分方法与图像分割相结合的一种运动目标检测方法，该方法针对帧差分法的不足，能够较好地对运动目标轮廓进行完整提取。但是目前该算法在使用效率及在不同场合下的自适应性有待进一步加强，这是下一步研究工作的重点。

参考文献

[1]孙即祥.数字图像处理[M].石家庄：河北教育出版社，1993.

[2]伏思华，张小虎.基于序列图像的运动目标实时检测方法[J].光学技术，2004（2）：215⁃218.

[3]DUBUISSON M P，JAIN A K.Object contour extraction using color and motion[C]//Proceedings of 1993 IEEE Computer So⁃ciety Conference on Computer Vision and Pattern Recognition. New York：IEEE，1993：471⁃476.

[4]LIU Gang，NING Shangkun，YOU Yugan，et al.An improved moving objects detection algorithm[C]//Proceedings of 2013 In⁃ternational Conference on Wavelet Analysis and Pattern Recog⁃nition.Tianjin，China：IEEE，2013：96⁃102.

[5]肖本贤，陆诚，陈昊，等.基于帧间差分法和不变矩特征的运动目标检测与识别[C]//第二十七届中国控制会议论文集.昆明：中国自动化学会控制理论专业委员会，2008：578⁃581.

[6]李建，蓝金辉，李杰.一种新型快速运动目标检测算法[J].中南大学学报（自然科学版），2013（3）：978⁃984.

[7]TU Jilin，DEL AMO A，XU Yi，et al.A fuzzy bounding box merging technique for moving object detection[C]//Procee⁃dings of 2012 Annual Meeting of the North America on Fuzzy Information Processing Society.Berkeley：IEEE，2012：1⁃6.

[8]章毓晋.图像分割[M].北京：科学出版社，2001.

[9]许新征，丁世飞，史忠植，等.图像分割的新理论和新方法[J].电子学报，2010（1）：76⁃82.

[10]FELZENSZWALB P F，HUTTENLOCHER D P.Efficient graph⁃based image segmentation[J].International Journal of Computer Vision，2004，59（2）：167⁃181.

[11]李鹏飞，陈朝武，李晓峰.智能视频算法评估综述[J].计算机辅助设计与图形学学报，2010（2）：352⁃360.

[12]WASSENBERG J，MIDDELMANN W，SANDERS P.An effi⁃cient parallel algorithm for graph⁃based image segmentation [C]//Proceedings of 2009 13th International Conference on Computer Analysis of Images and Patterns.[S.l.]：Springer，2009：1003⁃1010.

朱长仁（1968—），男，浙江淳安人，副教授，硕士生导师，博士。主要研究方向为图像分析与理解、遥感图像智能解译、信息融合。

钱智明（1986—），男，江苏南通人，在读博士。主要研究方向为图像理解与目标识别。

中图分类号：TN911.73⁃34

文献标识码：A

文章编号：1004⁃373X（2016）03⁃0013⁃05

doi：10.16652/j.issn.1004⁃373x.2016.03.004

收稿日期：2015⁃07⁃22

基金项目：国防科大ATR重点实验室项目资助；国防科大创新论文资助

作者简介：陈佳（1983—），男，福建福州人，在读硕士。主要研究方向为图像分析与理解。

A moving target detection method based on integration of frame difference method and fast image segmentation

CHEN Jia1，2，ZHU Changren1，QIAN Zhiming1
（1.Key Laboratory of ATR，College of Electronic Science and Engineering，National University of Defense Technology，Changsha 410073，China；2.Directly Under Detachment，The Fujian Province Armed Police Corps，Fuzhou 350001，China）

Abstract：The target area acquired by the frame difference method after pretreatment becomes hollowing or is split into several disconnected parts，and it is difficult for computer to judge whether the multiple parts belong to one object，so a moving target detection method based on integration of three⁃frame difference method and fast image segmentation is proposed.The three⁃frame difference operation and image⁃based fast segmentation for sequential images are conducted，and then the decision rule is fused by definition to carry out mutual supplementation and restraint of the difference results and image segmentation region block，after that，the sub⁃region blocks corresponding to the decision rule are combined，and the position and outline of the moving target are extracted precisely.The experimental results show this method can effectively improve the integrity of the moving target detection.

Keywords:：target detection;；frame difference;；image segmentation;；minimum spanning tree;；video surveillance