基于最近邻域像素梯度的视频背景快速提取

赵树言　路艳雪　韩晓霞

摘要：针对嵌入式设备对视频背景的实时提取问题，提出一种基于最近邻域像素梯度（N2PG）稳定性的视频背景快速提取方法。首先，以视频中任意帧作为初始背景，并计算此背景图像的N2PG矩阵；然后，以背景帧之后若干帧图像作为背景更新图像，同理计算N2PG矩阵；最后，将背景图像N2PG矩阵与更新图像N2PG矩阵进行差分，并通过实时估计的梯度稳定性阈值快速判断背景模型中各像素点是静态背景像素点还是非背景像素点，进而对其更新或替换，以得到视频当前背景。经计算机仿真测试，与常用的卡尔曼滤波法和混合高斯法相比，基于N2PG的视频背景提取方法得到相同质量背景仅需10～50帧图像，并且平均处理速度分别提高36%和75%；和改进的视觉背景提取（ViBe）算法相比，在所需帧数和所得背景质量相近的情况下，该算法背景更新速度提升一倍。实验结果表明，基于N2PG的视频背景提取算法具有很强的自适应性，并且速度快、内存消耗小，背景提取准确度达到90%以上，可满足真实自然环境下嵌入式视觉设备的应用。

关键词：快速背景提取；邻域像素梯度；视频背景；嵌入式系统；机器视觉

中图分类号：TP391.41

文献标志码：A

0引言

随着机器视觉技术的不断发展成熟，以及嵌入式智能视觉设备越来越多的产生和应用，对真实自然环境下视频背景提取的要求也越来越高，尤其需要兼顾背景提取速度和质量[1]，比如智能车载监控系统、无人驾驶图像检测系统、移动机器人视觉系统和无人机视觉系统等。因为统计表明视觉系统的研究对象80%均为运动物体，而背景相减法[2]又是对视频中运动物体检测最简单、最有效的方法。

真实复杂环境下，嵌入式视觉设备对视频背景实时、准确、快速提取和建模的主要困难和挑战在于一方面要求算法复杂度要低、内存消耗要小，另一方面又要求能适应复杂的自然环境变化影响，比如天气、光线和场景、摄像头本身移位、晃动等[3]。而目前已有的背景提取算法多针对于某种特定场景有效，或高度依赖于实验室高性能计算机，或过多依赖于先验知识，相对普适性较低、实时性不强，难以满足嵌入式智能视觉系统的要求。对此，本文提出了一种基于最近邻域像素梯度（Nearest Neighbor Pixel Gradient，N2PG）稳定性的视频背景快速提取方法。

1相关工作

目前比较常用的背景提取方法主要可分为两类：基于像素时间分布特征和基于像素空间分布特征。基于像素时间分布特征的背景建模方法主要有均值法[4]、帧间差分法[5]、基于区间分布的自适应算法[6]等；基于空间分布特征的代表性算法如视觉背景提取（Visual Background Extractor， ViBe）算法[7]。

其中均值法以视频前n帧图像各像素的平均值作为背景图像，该方法简单容易，但过于粗糙，不适合复杂变化环境。后来文献[8]提出了改进的差分均值算法，部分解决了均值法所造成的残影影响，但实用性依然不强。

对于差分法，在实验室等理想环境可以快速准确提取背景，但是对于有光照影响等自然环境明显失效，也不能解决背景有变化的情况。对此，Koller等[9]提出了卡尔曼滤波法解决了背景光线变化问题，再后来Stauffer等[10]提出的混合高斯法也解决了背景变化问题，但这两种方法都需要比较漫长的背景初始化过程，同时也大大增加了算法复杂度，提高了对硬件的要求，这些不足使其难以应用于实时性要求较高的嵌入式系统。

区间分布自适应背景建模算法不需要复杂的初始化过程，相对适合实时系统。但是其区间划分数目对先验知识依赖性高，所以普适性较低；而且区间划分多，背景精度才高，这又会大大增加算法复杂度。

对于基于像素的非参数化随机样本模型算法，即ViBe算法，以及其后的多种改进ViBe算法，如文献[11-12]所述，虽然都具有较好的鲁棒性，尤其对动态背景中的前景检测均有较好的效果，但是ViBe算法是假设相邻像素点具有相似的时空分布，所以对前景与背景的交界处不能较好地作出判断，常常因为误判而导致所得前景轮廓有残缺或拖影现象，这对后续的深度测量和识别等操作都不利。同时，ViBe算法所得背景是一种近似背景，对相似度阈值、邻域半径等参数依赖性大，若采用固定的相似度阈值，通常会降低算法鲁棒性；若采用变化的相似度阈值，又会大大增加运算量。

2最小邻域像素梯度分析

2.1相关定义

若将视频看作是多帧图像的顺序组合，则可以用集合表示为{Ik（x，y）}，其中：k表示帧序号，I表示视频的单帧图像。现将单帧图像各像素点的灰度值用坐标表示为v（x，y），则N2PG算法中相关定义如下：

最近邻域像素：规定某像素点上、下、左、右四个方向最近相邻的n个像素点为该像素的最近邻域像素。依次用该中心像素点坐标表示为vi（x，y）（i=1，2，…，n，习惯以中心像素点邻域由内向外第一层左像素为起点，逆时针顺序编号，默认i取值1～4），以后将该中心像素点称作核像素点。对于每帧图像边缘的像素，为计算方便，默认其所缺失的所有最近邻域像素灰度值等于其核像素值。

范值矩阵：为计算和描述方便，文中将与视频像素大小相同且只有0和1两种元素的矩阵称为范值矩阵。其中0值元素所对应像素值无效，1值元素所对应像素有效，并且在不同情况会有不同的具体含义。

2.2最近邻域像素梯度值特征分析

为了明显地观察视频中各像素点的N2PG值在不同帧间的分布特征，现利用室外自然环境下所拍摄的一段视频前800帧，以各像素点分别为核，对其N2PG值进行统计分析。实验中随机确定核像素点，共统计200个样本。以样本点（99，151）为例（在图1所示两帧抽样图像中均以字母P标出），首先，测量每帧中P像素点灰度值v及其四个最近邻域像素的灰度值v1～v4（本实验中为彩色视频，故以各像素红（R）、绿（G）、蓝（B）三个颜色分量的算数平均值作为该像素灰度值）。再按照式（1）计算P点在各帧的N2PG值；然后对相邻帧的N2PG值作差运算并取绝对值；最后以2维离散点统计图表示出来，如图2所示。通过所有样本点的统计图分析可以得到如下结论：自然场景下的视频图像，其静态背景像素点的最近邻域像素梯度值在邻近帧间有一定的稳定性。

图2中第345帧图像如图1（a）所示，第759帧图像如图1（b）所示，可以看到除了第345帧到第356帧之间和756帧到763帧之间的N2PG值有较大跳变之外（临界点分别以A、B、C、D示出），其余N2PG值在邻近帧间变化很小，甚至为零。而从A点所对应第345帧的图像中可以看到一行人正好到达P点（此时称P点为动态进入点）；并且，从B所对应第356帧图像中可以观察到该行人恰好完全离开P点（此时称P点为动态退出点）。同样，从图2中C点所对应第756帧图像可以看到正好有一辆汽车要通过P点，在第763帧图像中该汽车正好离开P点。

通过上述实验很容易得出，N2PG（x，y）值的稳定程度很好地代表了其核像素点的状态特征，可以据此判断出此核像素点在当前帧属于背景像素点还是动态像素点。若图2中以水平实线表示稳定性阈值，则很容易区分出P作为动态像素点所在帧和作为静态背景像素点所在帧，如P作为运动物体轮廓像素时的A、B、C、D点，并且可以很好地容忍自然光照变化等。

综上实验可知N2PG值具有很好的时空代表性，在空间分布上它代表了核像素点与其邻域像素的相关程度，在时间分布上间接反映了其核像素点的稳定性。

2.3二值图像模型算法分析

为了更形象、更直观地分析N2PG算法，此时简化视频模型，假设像素为4×4，并且只有黑白两色（黑色像素值为1，白色像素值为0）。如图3（a）所示，A、B、C为从该视频中依次抽取的三帧原始图像，图像中每个小方格代表一个像素点，黑色像素点表示运动物体，背景像素均为白色。

首先指定A图像作为背景初始图像，B和C作为背景更新图像。再根据式（1）分别以每帧各像素点为核，求取A、B和C的N2PG矩阵。各N2PG矩阵图像分别如图3（b）中A′、B′和C′所示，图中白色方框表示该像素的N2PG值为0，斜线阴影表示N2PG值为1，黑色方框表示N2PG值为2。

然后对N2PG矩阵A′和B′作差分运算，并对结果按照非零元素置1的规则处理可得准范值矩阵WA-B，若1值元素用阴影表示，0值元素用白色表示，则如图3（c）中A-B所示。很显然此矩阵图像中1值元素所构成的所有闭合连通区域边缘正好是运动物体在背景图像A和背景更新图像B上像素点并集的外边缘。因此可以去掉各连通区域每行和每列的第一个和最后一个1值元素（即元素值由1变为0），得到黑色矩形框所表示的动态像素区域，此时所得范值矩阵记为W1。同理，对N2PG矩阵A′和C′作差分得WA-C，归一化、去阴影得到运动物体在A和C中的像素点并集的范值矩阵W2，如图3（c）中A-C所示。同理，求得运动物体在图像B和C中像素点并集的范值矩阵W3，如图3（c）中B-C所示。因为简化模型的特殊性，导致WA-C求取过程中产生边缘梯度正好相消的情况，如图中两个灰色方框所表示的像素点，但实际图像中此情况几乎不存在，并且影响可以忽略，所以人为填补了图中的两个灰色像素点，将其值由0变成1。

分析上述规则所得W1、W2和W3，以非零元素表示动态有效像素点，可知：W1与W2的交集，再去除与W3重叠的部分，则得到原始背景图像A中绝对动态像素点（理论上为部分黑色像素点），该像素区域用δ1表示，就可以用B或C中的相同像素区域替换；而W1和W2并集在I中的补集，则一定为原始背景图像A中静态背景像素点（理论上为部分白色像素点），该像素区域用δ2表示，就可以用B或C中的相同区域加权更新。

3基于N2PG的算法实现

基于N2PG的背景提取算法可以从视频任意帧开始，先以开始帧作为初始背景，并计算背景N2PG矩阵；再以其后至少两帧图像作为背景更新图像，计算出参考N2PG矩阵；最后，将背景N2PG矩阵与参考N2PG矩阵进行差分运算，通过运动物体边缘像素的N2PG变化，确定背景模型中的静态背景像素点，对其加权更新，同时锁定背景模型中的动态像素点区域，并对其进行替换。

3.1N2PG算法实现步骤

步骤1任意抽取视频中的一帧图像I作为背景初始化图像，存储并记为B（x，y），再按照式（1）计算各像素点的N2PG值，以各N2PG值为元素，构建背景图像N2PG矩阵，记为WB（x，y）。

3.2稳定性阈值动态估计

通过分析可知，稳定性阈值η的选择对基于N2PG的视频背景提取方法结果至关重要，而且在实际应用中背景N2PG矩阵和参考N2PG矩阵间的帧序号间隔并不确定，也就是说不宜采用固定参数。因此，假设视频中任意时刻运动物体像素分布所占比例远小于背景像素比例，则可以设计了一个计算比较简单的稳定性阈值动态估计方法，具体操作如下：

在3.1节所述算法步骤3中，当每次按式（2）计算得到中间矩阵DISN2PG时，随机生成N个不同自然数（N一般取值10～100），然后将这N个数排序并按视频像素大小分别沿X轴方向和Y轴方向对N个自然数进行放缩，组成遍布图像I的N×N个随机坐标。读取所有相应坐标的DISN2PG（x，y）值，计算其平均值，最后以该平均值的3～5倍作为本次式（3）标准范值矩阵计算的稳定性阈值，估算公式为：

4实验结果及分析

为测试基于N2PG的视频背景提取方法的实用性，并对该算法与目前常用算法在速度和效果方面进行对比，本文对一室外自然环境下固定摄像头所拍摄的视频进行背景提取实验，视频共2890帧，像素为320×240，所对比的背景建模方法分别为均值法、卡尔曼滤波法、混合高斯法和文献[11]提供的改进ViBe算法，所比较参数为建立可用背景图像所需要视频帧数、平均每帧所需时间和背景准确度。仿真测试实验中所用计算机CPU为Intel Core i3，内存2GB，VS2010搭建OpenCV2.49开发环境。分别用各算法对该视频进行多次背景提取实验，实验测试结果统计如表1所示。

从表1可以明显看到，除了均值法所得背景准确度较低，基于N2PG算法、卡尔曼滤波法、混合高斯法和ViBe算法均可以提取较好的视频背景，并且通常情况下所得背景质量区别不大，相对ViBe算法所得背景准确度更高些。而从背景建模周期来看，基于N2PG算法和ViBe算法又具有明显优势，并且基于N2PG的算法周期最短，少于50帧，原因是这两种算法均不需要像卡尔曼滤波法和混合高斯法那样较为复杂的背景初始化操作。最后从算法处理速度的角度，基于N2PG算法较ViBe算法相比，优势更明显，完全可以满足实时性要求较高的系统。

图4所示为用基于N2PG算法在视频第528帧和第876帧所提取背景图像。直观来看，所得背景均很好地消除了当前画面的运动物体，保留了纯净的静态背景。并且在第876帧的背景中也很好地融入了已经驻停在路口拐角处的一辆汽车，即接受了该汽车所投射像素点由动态到静态的变化。为了更明显地观察基于N2PG的算法所提取背景在运动物体检测中的效果，选择提取背景准确度最高的ViBe算法作比较，两种算法在528帧和876帧中运动物体检测效果如图5所示。观察图5可以看到，虽然ViBe算法对噪声抑制能力相对较好，但再观察所得二值图像中运动物体的轮廓，很明显基于N2PG的算法所得物体轮廓完整性、连通性更好，而ViBe算法所得物体轮廓残缺严重，甚至检测结果为光斑状，这对后续的深度测量、识别等操作均造成不利影响，从此角度出发，基于N2PG的视频背景提取方法更具研究价值。

综上分析，从应用的角度，基于N2PG的视频背景提取算法和ViBe算法较适合嵌入式系统应用，但是综合考虑速度和质量，基于N2PG的算法更适合应用于嵌入式视觉设备，因为该算法在保证提取视频背景质量的同时，内存需求压力更小，背景提取速度更快，背景实时更新周期更短。

5结语

为了满足真实自然环境下对视频背景快速度提取和高质量跟踪的要求，本文提出的基于N2PG的视频背景提取算法兼顾各像素点的时空分布特点，空间分布上用各像素最近邻域梯度值替代像素值，提高鲁棒性，时间分布上，通过邻近帧N2PG稳定性准确判断静态背景像素点和动态非背景像素点。对N2PG稳定性阈值的实时估计，保证了算法的自适应性。实验证明了基于N2PG快速背景提取算法具有较高的鲁棒性、实时性、高效性，满足嵌入式视觉系统的应用要求。

不过基于N2PG的快速背景提取算法的稳定性阈值估计方法是建立在静态背景像素点分布比例远大于运动物体像素点所占比例的假设前提下，虽然此假设符合普遍情况，但忽略此假设条件而设计更具一般意义的N2PG稳定性阈值估计方法依然具有现实意义。

参考文献：

[1]胡琼，秦磊，黄庆明.基于视觉的人体动作识别综述[J].计算机学报，2013，36（12）：2513-2515. （HU Q， QIN L， HUANG Q M. A survey on visual action recognition [J]. Chinese Journal of Computers， 2013， 36（12）： 2513-2515.）

[2]付文秀，李冰，温翔.基于自适应耦合模型的运动目标跟踪方法[J].北京交通大学学报，2014，38（2）：50-55. （FU W X， LI B， WEN X. A moving object tracking method based on adaptive coupled model [J]. Journal of Beijing Jiaotong University， 2014， 38（2）： 50-55.）

[3]吕嘉卿，刘立程，郝禄国，等.基于视觉背景提取的自适应运动目标提取算法[J].计算机应用，2015，35（7）：2029-2032. （LYU J Q， LIU L C， HAO L G， et al. Adaptive moving object extraction algorithm based on visual background extractor [J]. Journal of Computer Applications， 2015， 35（7）： 2029-2032.）

[4]HULL J J. Incorporating language syntax in visual text recognition with a statistical model [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence， 1996， 18（12）： 1251-1256.

[5]李刚，曾锐利，林凌，等.基于帧间颜色梯度的背景建模[J].光学精密工程，2007，15（8）：1257-1262. （LI G， ZENG R L， LIN L， et al. A novel background modeling method based on color grade of different frames [J]. Optics and Precision Engineering， 2007， 15（8）： 1257-1262.）

[6]刘勃，魏铭旭，周荷琴.一种基于区间分布的自适应背景提取算法[J].模式识别与人工智能，2005，18（3）：317-321. （LIU B， WEI M X， ZHOU H Q. A Zone-Distribution based adaptive back ground abstraction algorithm [J]. Pattern Recognition and Artificial Intelligence， 2005， 18（3）： 317-321.）

[7]BARNICH O， VAN DROOGENBROECK M. ViBe： a universal back-ground subtraction algorithm for video sequences [J]. IEEE Transactions on Image Processing， 2011， 20（6）： 1709-1724

[8]韩超，邓甲昊，邹金慧，等.基于差分均值背景提取和矩阵分区目标检测算法的研究[J].北京理工大学学报，2012，32（12）：1247-1251，1257. （HAN C， DENG J H， ZOU J H， et al. Background extraction based on differential mean method and shadow detection using matrix sub-region partition[J]. Transactions of Beijing Institute of Technology， 2012， 32（12）： 1247-1251，1257.）

[9]KOLLER D， WEBER J， HUANG T， et al. Towards robust automatic traffic scene analysis in real-time [C]// Proceedings of the 12th IAPR International Conference on Pattern Recognition. Piscataway， NJ： IEEE， 1994： 126-131.

[10]STAUFFER C， GRIMSON W E L. Adaptive background mixture models for real-time tracking [C]// Proceedings of the 1999 IEEE Computer Society Conference on Computer Vision and Pattern Recognition. Washington， DC： IEEE Computer Society， 1999： 246-252.

[11]陈星明，廖娟，李勃，等.动态背景下基于改进视觉背景提取的前景检测[J].光学精密工程，2014，22（9）：2545-2549. （CHEN X M， LIAO J， LI B， et al. Foreground detection based on modified ViBe in dynamic background [J]. Optics and Precision Engineering， 2014， 22（9）： 2545-2549.）

[12]DROOGENBROECK M V， PAQUOT O. Background subtraction： experiments and improvements for ViBe [C]// CVPRW 2012： Proceedings of the 2012 IEEE Computer Vision and Pattern Recognition Workshops. Washington， DC： IEEE Computer Society， 2012： 32-37.