第5卷第6期 智能系统学报 Vol.5 No.6 2010年12月 CAAI Transactions on Intelligent Systems Dec.2010 doi:10.3969/j.issn.16734785.2010.06.015 YUV颜色空间和图论切割的阴影去除算法 刘清，秦秀丽，文松柏，郭建明 (武汉理工大学自动化学院，湖北武汉430063) 摘要：针对智能视频监控系统中阴影常由于其自身的属性而被错误地检测成前景目标的问题，提出了一种YUV颜 色空间和图切割算法相结合检测阴影的新方法.首先，在获取的前景运动区域中综合考虑UV颜色空间的亮度和色 度信息来检测阴影区域并融合形态学滤波等操作得到确定的阴影和目标种子点，然后进一步通过图切割算法获得 阴影与目标的优化分割，以提高阴影区域的检测精度.实验证明，该方法能有效地检测并去除视频监控场景中运动 物体所携带的阴影. 关键词：前景分割；阴影去除；UV颜色空间；图切割 中图分类号：TP391.41文献标志码：A文章编号：16734785(2010)06055605 The algorithm of shadow-elimination based on YUV color space and graph theory LIU Qing,QIN Xiu-li,WEN Song-bai,GUO Jian-ming (School of Automation,Wuhan University of Technology,Wuhan 430063,China) Abstract:In intelligent video surveillance systems,the moving cast shadows are often mistaken as the object due to its own properties.Consequently,a YUV color space-based theory and a graph-theory-based shadow detection method were proposed to improve the quality of detection.First,the precise seeds of the foreground and shadow were obtained by the YUV color space based on the comprehensive consideration of luminance and chrominance in- formation and morphological filtering.Then the maximum flow minimum cut graph theory algorithm was employed to obtain the optimized segmentation of the shadow and target.Experimental results show that the proposed method can detect and eliminate the cast shadow effectively. Keywords:foreground segmentation;shadow elimination;YUV color space;graph-theory 视频序列图像的分析主要是针对图像序列中人过跟踪车辆运动轨迹来判断消失点，确定用哪类模型 们所感兴趣的部分进行的，也就是前景目标，比如运 对图像平面得到的运动前景进行匹配[21.Collado等 动的人和车辆等，而阴影的存在严重影响了运动目 则定义了车辆的几何模型3]，并利用该模型的能量函 标提取的准确性，所以，为了获取更好的分割结果， 数在图像中搜索匹配的车辆.此类方法虽然在模型建 必须检测并去除阴影.这也使得阴影检测成为近年 立准确的前提下可以取得相对较好的检测效果，但模 来智能视频监控技术中研究的一个热点.目前针对 型建立的复杂度和计算时间与监控场景背景复杂度 阴影检测消除的方法主要可以分为2大类：基于模 有很大的关系，一般只在一些特定的场景中采用该方 型和基于阴影特征的方法， 法进行阴影的检测与去除 基于模型的方法需要根据对象的形状、场景以及 基于特征的方法则是先提取出包含阴影的运动 光照等先验条件建立相应的模型，通过统计分析来判 区域，然后通过颜色、纹理、梯度等特征来检测阴影 别每个像素点是否属于阴影区域.比如，Yoneyama等 区，最终将阴影和目标分开.比如，在颜色方面，Cuc 设计了关于2-D车辆阴影联合模型的6种模式)，通 chiara等采用HSV颜色空间只对运动区域进行阴 影检测与去除3)，由于HSV颜色空间无法准确鉴别 收稿日期：2010-0305. 黑色车辆及其阴影，实验中对于黑色车辆及小型目 基金项目：湖北省自然科学基金资助项目(2009CDB403). 标会发生丢失现象，需要通过合理设置阈值来改善 通信作者：刘清.E-mail:gli2000@163.com. 检测效果.Horprasert等在RGB颜色空间，利用归一
第6期 刘清，等：UV颜色空间和图论切割的阴影去除算法 ·557· 化的亮度变化和色度偏移来识别阴影4].运用基于 U=(B-Y)*0.565, (2) 颜色的方法对监控场景的光照变化较为敏感，如果 V=(R-Y)*0.713. 物体的部分像素和阴影具有相似的颜色特征，以上 很显然，式(2)较式(1)在计算上少了4次乘 方法极有可能会将这些物体像素误判为阴影3].利 法，2次加法，有效地提高了转换运算速率.在对转 用梯度特征进检测，Chien等人先假定监控场景中 换速率有特殊要求的场合，还可以选择文献[8]中 阴影部分的亮度值是缓慢变化的，然后采用梯度滤 提到的查表法，该方法不需要乘法运算，其方法相较 波器将输入图像中的阴影去除3，).该方法对背景 于式(1)极大地提高了转换效率. 单一、阴影较弱的室内场景有效，但对阴影边缘去除 根据已有的视觉经验可知，在YUV颜色空间检 的效果不好.在纹理方面，Leone等用基于纹理的方 测阴影的规则可以归纳如下： 法进行阴影检测[6]，首先利用阴影比其覆盖的背景 规则1阴影区域中像素的亮度低于背景像素 灰度值小的特性，得到候选的阴影像素，然后采用优 和前景像素的亮度； 化的Gabor核函数提取候选点附近和相应背景点附 规则侧2阴影区域中像素的色度与背景像素色 近的Gbor特征值，如果这2个特征值相近，则认为 度相比几乎相等. 纹理相似，判定为阴影像素.该方法选取的核函数越 假设输入视频序列中的某一帧图像上的某一个 多，检测性能越好，但计算也更复杂.同时该方法适 位置(i处)对应的像素点为X:,令IC=（Yc(X:), 合运动物体和背景纹理差别比较大的情况] Uc(X:),Vc(X:))为该像素点所对应的当前帧中的 近年来有学者提出基于2类方法的融合来实现 YUV颜色空间各分量信息值；B=(Y:(X:), 阴影的检测，如Qi等人利用阴影的粗模型与HSV Ua(X:),Va(X:))为该像素点所对应的背景帧中的 颜色空间结合的方法，但这只是对提高检测速率有一 YUV颜色空间各分量信息值.检测中间结果用二值 定成效.本文考虑到基于模型方法的模型复杂度和计 图表示，1代表是前景像素点，0代表是阴影像素点. 算时间都随着场景的复杂度而增加，选泽基于YUV 根据规则1有如下判断函数： 颜色空间的特征方法，同时为简化YUV检测阴影的 阈值选取及后处理问题，在基于颜色空间检测的基础 PoutImgl(X:)= 上引入了图切割算法方法以提高目标分割的鲁棒性. 1, if I Yc(X;)-Ya(X:)I>Ty; 即在前景运动区域中通过YUV阴影检测的约束条件 10,otherwise. 得到确切的目标和阴影种子点后，再利用图论中的最 式中：PoutImgl(X:)是根据亮度信息得到的带有前 大流最小切割算法在该运动区域上进一步分割，从而 景和阴影分区的输出图像；T,为对应的亮度阈值. 得到相对精确、平滑的前景目标图像， 根据规则2有如下判断函数： PoutImg2(X:)= 1阴影检测 [o,if I Uc(X)-Ug(X)I+Vc(X:)-Ve(X:)I>Tiv; 1.1YUV颜色空间阴影检测 10,otherwise. 目前大多数视频采集设备所采集的图像都是基 式中：PoutImg2(X:)是根据色度信息得到的带有前 于RGB颜色空间，但该空间各分量之间相关性高、 景和阴影分区的输出图像；Tw为对应色度阈值. 冗余信息多、计算量大.考虑到RGB空间到YUV空 通过调整亮度阈值和色度阈值得到检测结果 间的转换过程是线性的，且YUV空间亮度信号Y和 PoutImgl(X:)和PoutImg2(X:),并进行与操作得到 色度信号U、V是相互独立的.本文选择在YUV颜 最终检测结果；但由于场景中各种因素的影响，检测 色空间上结合形态学操作来获得置信度很高的阴影 结果中往往会存在噪声或空洞现象，不利于后续的 像素点集和前景目标像素点集， 处理分析，故利用形态学操作中的开、闭等运算，合 RGB颜色空间到YUV颜色空间的线性转换公 理选取腐蚀膨胀因子得到置信度很高的目标和阴影 式为 像素点， Y=0.299R+0.587G+0.114B, YUV颜色空间检测方法为获得相对精确的目标 U=-0.147R-0.289G+0.437B, (1) 信息，在后处理操作上必须综合考虑腐蚀、膨胀结构 V=0.615R-0.515G-0.100B. 元素大小以及连通性判断面积阈值的选取等问题，虽 对式(1)进行方程组近似变换得 然可以得到比较接近运动目标轮廓的结果，但往往存 Y=0.299R+0.587G+0.114B, 在部分轮廓信息丢失或是多个目标合并的现象.因
·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
第6期 刘清，等：UV颜色空间和图论切割的阴影去除算法 ·559. 式中：min_obj和min_shd分别是k。类目标迭代和 飞，类阴影迭代的最小的类，计算公式如下： R.G.B min=m名(cp）-u,)月， R.G.B min_shd=min∑(c(p）-Vg). 假设2个像素p、q的色彩差值为Cg,则有 (a)当前帧 )彩色背景图像 Cm=&。(C(p)-C(q),那么有 vff )=Cm+1 入 式中：入为二元能量系数，用于平衡数据项和平滑项 之间的关系，采用Y.Boykov和V.Kolmogorov算 (c运动分割 dYUV检测结果(e)本文检测结果 法来最小化式(3)中的能量E(),即：分别以0 图2前景分割实验一结果 和S2个终端建立搜索树来寻找增广路径，反复进 Fig.2 Foreground segmentation results of experiment I 行以下3个算法步骤： 1)“growth'”:生长树S、T到两者相接，即找到s t路径； 2)“augmentation”:扩张路径； 3)“adoption”:修改重建树S、T. 直至搜索树S和T中不再存在活动节点且被已 (a)当前帧 ()彩色背景图像 饱和的边独立分开即可等价求取最小切割，完成运 动目标及阴影的优化分割. 2实验结果及分析 为了验证本文算法，选取多种室内外场景视频 ()运动分别 (d)YUV检测结果(e)本文检测结果 图像序列进行了前景目标提取实验.本文给出了在 图3前景分割实验二结果 强光及环境复杂度相对适中的室外情况（如图2实 Fig.3 Foreground segmentation results of experiment II 验一)以及正常光照室内环境（如图3实验二）的阴 影检测去除的实验效果，从实验结果可以看出，目标 3结束语 与阴影可以被平滑、完整地检测区分开来， 针对摄像头固定的监控场景，研究了基于YUV 实验中，图2(d)和图3(d)是采用文献[14]中 颜色空间和图切割相结合的阴影检测方法.采用 YUV色度和亮度结合检测去除阴影的算法得到的 YUV颜色空间进行阴影检测，在一定程度上可以满 结果，可以看出，该方法可以检测出前景目标，保证 足视频监控系统实时处理的需求.检测过程中，由于 结果的基本正确，但检测结果依然可能存在目标合 各种因素的影响，前景可能会存在空洞或是边缘损 并（如图2(d)中右侧上下2个目标合并为一个目标 失或是噪音现象，此时，可以反复采用不对称的腐蚀 体)、目标不完整（如图3(d)中目标脖子部分未被 膨胀形态学操作来进行处理，本文主要利用3*3的 十字腐蚀因子来滤除独立噪音，同时采用3*3的矩 检出)以及噪声点等现象，必须通过形态学操作以 型膨胀因子来对前景区域膨胀，以保证目标的完整 及选取合适的面积阈值进行连通性区域标识法分析 性.而图论算法的引入，弱化了YUV颜色空间阴影 等后处理操作得到相对较好的结果.而本文方法对 检测阈值难以选取的问题，同时，又在一定程度上保 于YUV颜色空间亮度阈值和色度阈值的选取要求 证了目标分割的平滑性以及完整性.实验表明，利用 相对较低，只需得到确定为阴影和前景的种子点即 YUV颜色空间以及图论分割算法相结合的方法可 可，同时，最小切割得到的检测结果干净、平滑，后处 有效地去除视频监控场景中运动物体所携带的阴 理操作相对简单，效果较为理想， 影.后续的工作则将侧重于运动目标的跟踪以及行
·560 智能系统学报 第5卷 为识别等方面. [10]WANG Song SISKIND J M.Image segmentation with ra- tio cut[J].IEEE Transactions on Pattem Analysis and 参考文献： Machine Intelligence,2003,25(6):675-690. [1]YONETAMA A,YEH C H,KUO CC J.Moving cast shad- [11]于丹，汤井田，徐大宏，等.基于最大流的交互式目标提 ow elimination for robust vehicle extraction based on 2D 取算法[J].计算机工程与应用，2007,43(5)：246- joint vehicle/shadow models[C]//Proceedings of the IEEE 250. Conference on Advanced Video and Signal Based Surveil- YU Dan,TANG Jingtian,XU Dahong.Interactive object lance.Washington,DC,USA:IEEE Computer Society, extraction based on Max-flow[J].Computer Engineering 2003:229-236. and Applications3,2007,43(5):246-250. [2]刘宏，李锦涛，刘群，等.融合颜色和梯度特征的运动阴 [12]BOYKOV Y,FUNKA-LEA G.Graph cuts and efficient 影消除方法[J].计算机辅助设计与图形学学报，2007， N-D image segmentation J ]International Journal of 19(10):1279-1285. Computer Vision,2006,70(2):109-131. LIU Hong,LI Jintao,LIU Qun,et al.Moving cast shadow [13]CUCCHIARA R,GRANA C,PICCARDI M,et al.Impro- elimination based on color and gradient features[J].Journal ving shadow suppression in moving object detection with of Computer-Aided Design Computer Graphics,2007,19 HSV color information[C]//Proceedings of 2001 IEEE In- (10):1279-1285, telligent Transportation Systems Conference.Oakland, [3]COLLADO J M,HILARIO C,ARMINGOL J M,et al. USA,2001:334-339. Model based vehicle detection for intelligent vehicles[C]/ [14]马国峰，杨俊红，周兵.基于YUV颜色空间的视频运动 Proceedings of IEEE Intelligent Vehicles Symposium.Par- 检测[J].计算机工程与设计，2008,29(4)：3700 ma,Italy,2004:572-577. 3708. [4]HORPRASERT T,HARWOOD D,DAVIS L S.A statisti- MA Guofeng,YANG Junhong,ZHOU Bing.Motion detec- cal approach for real-time robust background subtraction and tion in video based on YUV color space[J].Computer En- shadow detection[C]//Proceedings of the 7th IEEE Interna- gineering and Design,2008,9(4):3700-3708. tional Conference on Computer Vision:Frame Rate Work- 作者简介： shop.Kerkyra,Greece,1999:1-19. 刘清，女，1966年生，教授，博士 [5]CHIEN S Y,MA S Y,CHEN L G.Efficient moving object 生导师，中国人工智能学会理事，湖北 segmentation algorithm using background registration tech- 省自动化学会常务理事.主要研究方向 nique[J].IEEE Transactions on Circuits and Systems for 为智能控制技术、智能移动机器人、智 Video Technology,2002,12(7):577-586. 能视频监控、计算机实时控制和信息系 [6 LEONE A,DISTANTE C.A texture-based approach for 统集成。 shadow detection[C]//Proceedings of the IEEE Conference on Advanced Video and Signal Based Surveillance.Como, 秦秀丽，女，1984年生，硕士研究 1taly,2005:371-376. 生，主要研究方向为计算机图像处理、 [7]WANG Shengke,QIN Bo,FANG Zhenghua,et al.Fast 视频分析. shadow detection according to the moving region[C]//2007 Interational Conference on Machine Learning and Cyber- netics.Hong Kong,China,2007:1590-1595. [8]冯永超，罗敏，贺贵明.一种快速YUV-RGB彩色空间变 换方法[J刀.微型机与应用，2002(7)：5960. 郭建明，男，1962年生，副教授，主要 [9]BOYKOV Y,KOLMOGOROV V.An experimental compar- 研究方向为智能控制技术、计算机实时 ison of min-cut/max-flow algorithms for energy minimization 控制与信息系统集成、智能视频分析. in vision[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2004,26(9):1124-1137