基于视差和帧差的图割优化运动目标分割算法

朱秋煜，李琦铭，陈岳川

(上海大学 通信与信息工程学院，上海200072)

近年来，运动目标的分割得到了广泛的研究，目标分割是运动人体信息采集的基础。目前所提出的检测运动目标的算法按照其原理主要可分为光流计算法、帧差分法和背景差分法。

对于单目视觉系统，背景实际上就是场景的灰度或色彩，当前景和背景色彩灰度接近时将很难分割前景。与色彩灰度相比，场景的深度通常较少受外部环境的影响，如果能通过立体视觉的原理得到深度信息，则前景目标的检测将容易得多，可惜的是场景的精确致密视差常常难以获得。为此，在以往的研究中利用能量函数最小化的优化方法以得到较为准确的区域视差，但由于在某些场景下背景和前景的灰度信息过于相近仍不能达到很理想的视差优化结果。所以本文研究在此基础上将视差和帧差采用图割优化算法进行融合，以此提高前景目标分割的准确性。

利用立体视觉进行图像检测与分割的基础是致密视差的计算。近年来，基于图理论的算法在计算机视觉中得到了成功的应用［1］，如图像匹配与视差计算［2-5］、图像分割［6-7］等。在视差计算方面，将原来的图像匹配问题转化为在搜索范围空间内寻找最优匹配点这样一个典型的寻优问题。而在目标分割方面，本文采用将视差和帧差作为图割算法里的能量函数的数据项，利用能量最小化算法确定运动目标的最佳分割。

1 区域视差匹配

区域视差的匹配可以分为以下4个步骤:1)把图像分割成相似的视差平滑的区域;2)计算分割区域可靠点的初始视差;3)根据初始视差得到模板集合;4)构造匹配代价函数并进行区域模板优化以得到精确的区域视差。

1.1 图像初始分割

图像初始分割效果的好与坏会直接影响到后续工作中视差模板的估计，所以选用适当的分割算法使图像分成多个平滑的区域具有重要意义。在图像分割算法中常用的有分水岭算法、聚类算法等，这些传统的算法的特点是具有较高的效率和实时性，但精确度有待提高且不太适用本文视差模板的计算。Comaniciu和Meer［8］在基于mean-shift的基础上提出了一种新的图像分割算法，该方法不仅具有效率高和实时性好的优点，同时适用范围广且分割的结果具有较大的精确度，因此本文采用了该算法进行图像的区域分割。

1.2 初始视差估计

视差估计匹配算法的相似度测量函数主要可归纳为三大类［9］:NCC(归一化互相关函数)、SSD(差值平方和函数)和SAD(差值绝对值和函数)。本文采用NCC算法［10］获取图像像素在不同视差情况时的匹配代价。匹配窗口的大小也能影响视差匹配的效果，较大的窗口在纹理信息少的区域能得到好的匹配效果，但在图像边缘等颜色梯度变化较大的区域则可能增强前景膨胀效应，选取3×3较小的窗口能得到较准确的匹配点。

1.3 模板视差计算

本文引用TAO［11］提出的一种立体匹配算法，方法中提到如果能把图像分割成多个视差平滑的区域，那这些区域中各个像素的视差可用一个平面模板公式来描述

式中:c1，c2，c3为模板参数;(x，y)是图像像素坐标;d为像素(x，y)对应的视差值。

选取模板集合中的某一个模板计算视差，通过所得视差计算该区域内的所有可靠点的匹配代价，那么匹配代价公式为

式中:CSEG(S，P)为平面模板P相对初始分割区域S的相似匹配代价;d为模板P在像素点(x，y)得到的模板视差;C(x，y，d)为当像素点(x，y)的对应视差为d时的匹配代价。

1.4 模板视差最优分配

本节的目的是通过选取最优化的模板来提高视差计算的精度，对模板集合中的每个模板构造能量函数，利用能量函数最小化［12］算法的思维解决模板视差的最优分配问题。计算分割区域的能量函数表达式如下

式中:f表示当前区域使用相邻区域的模块参数的匹配关系。数据项为式(2)所定义的匹配代价

平滑项为当第i块区域与第j块区域为相邻区域时的边界长度

计算数据项时，将前面所得的初始视差利用最小二乘法计算出模板参数，由于图像的分割区域的视差模板主要与其相邻区域的模板相关，所以本文选择了相邻区域的模板作为该区域的模板集合以计算平滑项，有限的模板集合个数大大提高了模板优化的计算速度。然后通过计算分割区域的每一个模板集合的能量函数，选取最小能量函数的模板作为该区域的最优化模板。最后根据得到的最优化模板参数代入公式便可得到修正后较准确的视差值。

2 三帧差分法

三帧差分法是选取视频序列中连续的3帧图像进行两两相减，即分别对第1帧和第2帧以及第2帧和第3帧的图像进行差分，这样得到的2幅帧差图像都含有运动目标，最后把2幅帧差图像进行与运算，便可得到基于运动目标本身的特征图像。对三帧差分的结果选取适当的阈值进行二值化分割可得到运动目标。三帧差分法的公式如下

式中:It-1(x，y)，It(x，y)和It+1(x，y)为图像序列当中连续3帧图像。那么选取阈值λ，则差分图像DΔt(x，y)经过阈值分割得到的二值化图像BΔt(x，y)为

三帧差分法充分利用了运动目标在视频序列中的时间相关性，融合了前后帧图像的像素信息，对于运动目标具有较高的灵敏度，可抑制随机噪声对于检测的影响，同时也可以有效地适应光线的变化，减少前景背景颜色灰度相近时的干扰。但其也存在着一定的缺陷，通过差值图像检测出运动目标比实际的要大，容易出现“双影”现象，同时由于检测出来的物体是前后帧相对变化的部分，无法检测到重叠部分，导致检测到的目标发生“空洞”现象，同时差分图像对于不同的背景选取阈值上需要一定的工作量，以上因素导致了三帧差分法检测结果不太理想。

3 基于图割理论的目标分割算法

图割是著名的最优化问题算法。利用图割算法进行图像分割，首先需要建立一个与图像对应的加权无向图。图的顶点与图像的像素对应，边与图像各个像素之间的相关信息对应，顶点属性与图像的像素信息(如颜色、视差、帧差等)对应，边的权值与像素间的一致性程度对应，图中还包括2个特殊的终端顶点——源点和汇点，可根据分割标准构造源点和汇点。图构建完成之后，求解能量函数最小化从而实现图像分割。

本文提出的基于图割理论的目标分割算法可分为2个主要部分:1)结合视差和帧差特征构造能量函数;2)使用图割算法最小化能量函数实现前景目标分割。

3.1 构造能量函数

实际场景中的目标分割仅仅依靠视差特征很容易受到亮度的影响，所以本文结合视差和帧差特征来构造能量函数解决这个问题。能量函数形式如下

式中:Ef和Ed分别是基于帧差和视差特征的图像能量;ωf和ωd是加权因子，可以根据图像的自身特征选择帧差和视差特征在能量函数中所在的比重实现更好的分割效果。

视差特征的能量函数的基本形式包括一个数据项和一个平滑项，具体公式如下

式中，平滑项Edsmooth表示用于约束邻接区域内像素的一致性程度。本文采用的是Sobel梯度算子来计算当前像素与邻接区域内的其他像素的平滑程度，数据项表示对应像素匹配一致性程度

式中:Dp用于表示当前像素的视差D(p)与背景视差或前景视差均值的不相似性。同理，帧差特征的能量函数的基本形式与视差特征的相类似

3.2 目标分割

根据图割思想，对于图像I进行背景和目标的分割过程，其实就是最小化函数Ed(f)的过程。使用图割算法最小化能量函数，首先要构造有向图G=(V，E)［13］

G中有2个特殊的终端:前景端F和背景端B。本文选取前景和背景的特征均值作为其具体值。G中边的集合E包括所有像素与它的邻接像素相连的边，以及所有像素和F，B相连的边。最后，当求得图G上对应的最小化的能量函数时，可把图像分为与前景端和背景端相连的2个部分，即判定与F相连的像素为前景目标，与B相连的像素则为背景。

4 实验结果

为了验证算法的有效性，本文对双目灰度视频序列进行了测试，所有图片大小都是360×240。首先是利用能量最小化算法优化图像的致密视差。从图1中双目图像可以看出背景中同时存在人和计算机等复杂信息，选取3×3小窗口计算的初始视差的值，在图像区域初始分割后，利用能量函数优化每一个分割区域的视差。可以看到，通过能量最小化的方法优化后的视差，在同一特征区域内都比较平滑，且去除了一些细小区域的干扰，得到了更为准确的区域视差。

图1 视差计算及优化

其次，利用三帧差分法同样可以获得图像中的运动目标，图2分别获取同一视频序列中的连续3帧图片，同时对第1帧和第2帧、第2帧和第3帧进行图像差分，最后把2幅帧差图像进行与运算，便可得到基于运动目标本身的特征图像。

图2 帧差结果图

最后，通过设定权值，结合帧和视差特征进行前景运动目标的分割，同时对比单独使用视差和帧差分割图像的结果进行分析。图3能量函数的权值ωf和ωd根据实验结果的经验取值分别为0.37和0.63，可以根据不同的场景进行适当的调整，当前景和背景灰度相近时，视差特征的作用减弱，可以多考虑帧差的贡献，而当帧差结果“空洞”现象较严重，可增加视差的比重。从实验结果可以明显地看出区域视差的优化受到灰度因素的影响，有些背景视差优化不够理想，但运动目标整体的视差都较为平滑，而帧差分割的结果对于运动目标具有较好的边缘信息，同时也存在许多的“空洞”，利用图割结合视差和帧差特征能够有效地整合二者的优点，减少视差优化不够准确的区域被检测为前景目标的可能性，同时也能填补大多数帧差分割的“空洞”。

图3 本文算法与视差和帧差分割结果对比图

为了进一步证明算法的有效性，同时给出了2组其他场景和亮度下的实验结果，图4中ωf和ωd分别为0.3和0.7，图5中ωf和ωd分别为0.6和0.4。实验组2中当帧差的结果受到运动目标灰度的影响比较大时，运用本文方法同样可以填补较大的“空洞”。实验组3是在夜晚灯光环境亮度不是很充足的情况下拍摄的，前景和背景灰度相近，增加帧差特征的比重，同样也有效证明了算法的适应性。此外，3组的 运算时间分别为12.58 s，8.80 s，10.05 s，可以看出并不十分高效，仍有改进之处。

5 小结

运动目标检测一直是视频跟踪和分析的基础，但是由于各种因素的影响一直没得到很好的解决，因此，本文在以往通过视差优化研究的基础上，提出了根据视差和帧差特征的信息采用图割优化的能量函数融合分割出运动目标的方法。实验结果表明，该方法相比于单独的视差和帧差特征的分割具有了更高的稳定性。

图4 实验组2的分割结果

图5 实验组3的分割结果

该算法仍有几处改进之处，未来的工作可以考虑利用图割算法结合更多的图像特征结合，同时重点在于如何缩短运算时间，在提高分割准确性的同时提高算法的效率。

［1］ARORA C，BANERJEE S，KALRA P，et al.An efficient graph cut algorithm for computer vision problems［C］//Proc.11th European Conference on Computer Vision.Berlin Heidelberg:Springer Verlag Press，2010:552-565.

［2］KIM J，KOLMOGOROV V.Visual correspondence using energy minimization and mutual information［C］//Proc.IEEE International Conference on Computer Vision.［S.l.］:IEEE Press，2003:1033-1040.

［3］GAO Hongwei，CHEN Liang，LIU Xiaoyang，et al.Research of an improved dense matching algorithm based on graph cuts［C］//Proc.the 8th World Congress on Intelligent Control and Automation.Jinan，China:［s.n.］，2010:6053-6059.

［4］PAPADAKIS N，CASELLES V.Multi-label depth estimation for graph cuts stereo problems［J］.Journal of Mathematical Imaging and Vision，2010，38(1):70-82.

［5］WANG Daolei，KAH B L.A new segment-based stereo matching using graph cuts［C］//Proc.2010 3rd IEEE International Conference on Computer Science and Information Technology.Chengdu，China:IEEE Press，2010:410-416.

［6］MORENO R，GARCIA M A，PUIG D.Graph-based perceptual segmentation of stereo vision 3D images at multiple abstraction levels［EB/OL］.［2011-10-20］.http://www.mendeley.com/research/graphbased-perceptual-segmentation-stereo-vision-3d-images-multiple-abstraction-levels/.

［7］黄洋文，王红亮.基于量子粒子群优化算法的图像分割方法［J］.电视技术，2010，34(4):16-18.

［8］COMANICIU D，MEER P.Mean shift:a robust approach toward feature space analysis［J］.IEEE Trans.Pattern Analysis and Machine Interlligence，2002，24(5):603-619.

［9］赵亮亮.双目立体视觉中的图像匹配技术研究［D］.南京:南京航空航天大学，2007.

［10］FUA P.A parallel stereo algorithm that produces dense depth maps and preserves image features［J］.Machine Vision and Applications，1993，6(1):35-49.

［11］TAO H，SAWHNEY H S，KUMAR R.A global matching framework for stereo computation［C］//Proc.the 8th International Conference on Computer Vision.Vancouver，Canada:［s.n.］，2001:532-539.

［12］BLEYER M，GELANTZ M.Graph-cut-based stereo matching using image segmentation with symmetrical treatment of occlusions［J］.Signal Proceedings:Image Communication，Special Issue on Three-Dimensional Video and Television，2007，22(2):127-149.

［13］邓宇，李华.多特征组合和图切割支持的物体/背景分割方法［J］.计算机研究与发展，2008，45(10):1724-1730.