·558. 智能系统学报 第5卷 此，考虑引入图切割算法，根据由YUV检测得到的阴 点，并给定2个终端，源S和汇T,分别代表视频 影和目标种子点集建立相应的统计模型，利用图切割 帧中的目标和阴影.定义相邻像素之间的特征绝对 的最小切割算法获得阴影与目标的优化分割，从而得 差值为边的容量w,如对于2个节点P、q所连接的 到相对精确、干净、平滑的目标信息. 边的权重为 1.2图论分割去除阴影 0g=|F(P)-F(q)I. 1.2.1图论分割基本原理 基于文献[10]选择像素的亮度信息为其特征 基于图论的图像分割技术是近年来图像分割领 来计算边权重值，则F(P)、F(9)分别为像素点p和 域的一个新的研究热点，该方法基本思想为 q的亮度值函数.定义c(S,T)为一个(S,T)切割的 1)建立与欲解决问题相适应的网络图， 容量，其等价于从S到T的边权值之和.即 2)确定该网络图图中边的权值函数，使图像分 c(S,T)=∑g 割目标（能量最小化）对应图的最小割. 假设f(S,T)为流网络中所有流出S(或是流进T)的 3)寻求一种算法来求解最小割问题， 总流量值，则有 图1给出了一个3×3的网络图G=(V,E)[] 的图切割示例，其中V表示图中的所有结点的集合 fS,T)=∑fS,),w∈V, (一般情况下，结点对应于图像的像素、体素或是其 （或fS,T)=∑fu,T). 他特征)，E表示图中所有连接结点的边的集合（像 网络G的一个割就是将V划分为S和T=V-S 素之间的关系)，每条边具有相应的权值，边的粗细 两部分，使s∈S,t∈T.Ford和Fulkerson于1956年 代表了其权值的大小，运用图割算法最终将图像像 提出了最大流最小切割定理，即任一个网络图中，最 素按其特征分割成了两大部分（图1(d)所示）. 大流的流量等于最小割的容量，公式表示为 max(f(S,T))=min(c(S,T)). 基于以上思想，本文在由1.1中YUV阴影检测 得到的前景目标点和阴影点的基础上，对输入视频帧 进一步检测并去除阴影，以克服YUV空间阴影检测 的不足，从而得到理想的分割效果.即将由YUV颜色 空间初步检测到的结果映射成网络图，即得到目标和 阴影种子像素点集合O和S,初始化k。簇和k,簇目 (a)输入图像 (D分割结果 标和阴影，通过K-means对O和S对应的图像像素进 行聚类，得到每一簇目标和阴影的平均色彩值U和 U(均包含R、G、B3个分量，i∈k。j∈k,),然后根据 前茶终端 图像能量值式(3)计算每个点是属于目标还是阴影， 即某个点的标签f=1则为目标，f=0则为阴影，则该 问题转化为最小化能量函数的问题， E)=∑Df)+,∑Gf). (3) pe (p,q)EN 式中：D(f)是定义像素点卫为标签f,代价，∫，代表 背京终端 背景终端 数据项.N为4邻域系统的网格图像，V(f,∫)是定 b)网络图 (c)图切割 义2个相邻像素点P、9为标签∫，、∫，的代价，代表平 图1图切割示例 滑项. Fig.1 An example of graph cut 设p点的RGB色彩为C(p),则p点的数据项 1.2.2。图论分割去阴影 容量D(f)可以定义如下： 首先通过YUV检测得到的运动区域中前景和 D(f=1)=0,D(f=0)=∞，p∈0， 阴影像素信息值的集合，然后将其映射成带有结点 D(f=1)=∞，D(f=0)=0,P∈S, 和权重的信息网络图，对该网络图进行最大流最小 D(f=1)= min obj min shdpv-oUS, min_obj 分割得到前景目标(O)与阴影(B)的优化分割. 图像上位置为(i,)的像素点P:对应图上的节 D(=0)= min shd min_obj min_shd