基于图切割的人体运动检测.docx
《基于图切割的人体运动检测.docx》由会员分享，可在线阅读，更多相关《基于图切割的人体运动检测.docx（14页珍藏版）》请在冰点文库上搜索。
基于图切割的人体运动检测
第18卷第6期2007年6月
光电子・激并
JournalofOptoelectronics・LaserV01.18No.6Jun。
2007
基于图切割的人体运动检测*
侯叶一,郭宝龙
（西安电子科技大学机电工程学院自动控制系,陕西西安710071
摘要:
研究利用图切割对人体进行有效检测的方法。
首先在色相、饱和度和亮度（HSV颜色空间建立自适应的背景混合模型快速提取背景;然后计算差分并消除阴影;最后构造8连通网络图,使用最小切割完成目标的分割。
通过实验,对单模型与混合模型背景、4连通与8连通邻域以及基于数学形态学与基于图切割的分割进行了比较。
结果表明,在实际环境下,采用本方法可快速、有效和鲁棒地对人体运动进行检测,并获得干净、光滑的分割结果。
关键词:
全局能量最小化;图切割;运动检测;自适应的背景混合模型;8连通
中图分类号:
TP391文献标识码:
A文章编号:
1005—0086（200706—0725—04
HumanMotionDetectionbyUsingGraphCuts
HOUYe一,GUOBao-long
（AutomationDepartmentofSchoolofMechano-ElectronicEngineering,XidianUniversity,Xi’an710071,China
Abstract:
Amethodofhumanmotiondetectionbyusinggraphcutswasproposed.Firstly,webuiltanadaptivebackgroundmixturemodelsinthehue-saturation-value（HSVcolorspace,andgotthebackgroundquickly.Secondly,wecomputedthedifferenceandeliminatedshadow.Finally,werepresentedtheimagesasan8-connectivitynetworkgraph,andsegmenteditthroughminimumcutting.Basedonseveralexperiments,wecomparedsinglemodelwithmixturemodelbackground,4一con—nectivityneighborwith8-connectivityoneandmorphologicaloperationwithgraphCUt.TheresultshowsthatacleanandsmoothhumansegmentationCanbegottenquickly,effectivelyandrobustlybyusingtheproposedmethodbasedongraphcutsinpractice.
Keywords:
globalenergyminimixzation;graphcut;motiondetection;adaptivebackground
mixturemodels;8-con—nectivity
1引言
人体运动的视觉分析是计算机视觉中最活跃的研究主题之一,其中运动区域的有效分割对于目标分类、跟踪和行为理解等后期处理是非常重要的。
由于运动检测处于视频运动分析的最底层,广泛的应用场合使运动检测算法需要应付各种复杂的情况,然而很难有一种算法能够适合所有的应用场合,所以对运动检测方法的研究一直是研究的重点。
图切割技术是图论中的问题,其引人注目的一个特点是它能找到全局量最小值,近年它被应用解决计算机视觉、计算机图形学和机器学习中的一些问题。
其中,Boykov等人[1]把计算机视觉中的图像恢复、立体视觉、多视点重建和目标分割等问题转化为求解能量最小值,从而使图切割技术有效地解决了这些问题。
其实,上述问题都可归类为标号问题[2],这样就把找寻最可能的标号转化为能量函数优化,再将能量函数优化转换为图切割的方法来解决。
图切割在结构形式上非常适合于图像的分割,在图像分割
收稿日期:
200606—27修订日期:
200611—01
*基金项目:
国家自然科学基金资助项目（60572152
**E-maU:
abcdef4568@163.corn中日益成为精确而有用的工具,而且也获得了成功的应用[35],不过大多是使用图切割进行交互式分割或对静止图像进行分割,对运动目标进行检测和分析还没有太多应用研究。
本文针对固定摄像机下的视频流,研究利用图切割对人体运动进行有效检测的方法。
2能量函数与最小切割
许多计算机视觉问题试图在含有噪声干扰的情况下,为像素安排标号L。
在不确定的情况下,找到最好的L成为一个优化问题。
优化方法由2步组成:
建立能量函数;求解能量函数的最小值。
计算机视觉中,普遍使用的能量函数形式为
E（L一∑Dp（Lp+∑%,q（Lp,k（1这里:
E是能量;p和q是像素;P是图像像素点的集合;N是像素的连通邻域点集合;b一{LpfpEP}是图像P的标号的集合;Dp（・是数据惩罚函数,表示数据约束,用于保证每个像素
万方数据
尽可能地找到其对应关系;%,。
是一近邻交互函数,表示光滑约束,用于约束相邻像素的一致性。
对式（1组合优化问题,找到全局最优值是难以解决的问题。
常用的求解方法有模拟退火、神经网络、动态规划法和遗传算法等,不过这些算法要么难以用于高维数据,要么难以控制收敛,且效率不高。
1956年,Ford等人证明了著名的最大流最小切割定理,即在任何网络中,最大流的值等于最小切割的容量,并给出了求解的具体算法[63。
1989年,Greig等人[7]首先发现最大流/最小切割算法能被用来最优化某些重要的能量函数,根据式（1的能量函数结构,建立了具有2个终点的图,使图的最小切割给出了全局最优的二元标号L。
设V表示整个图中的所有顶点的集合,E表示整个图中所有边的集合,边的权称为边的容量,称G一（V,E是一网络。
在网络图中常常包含一些额外的特殊点,称为终点,其相应于像素的标号集。
图1中具有2个终点:
S称为源;t称为汇。
图1（a是一简单的3×3网络,其顶点常常对应于图像的像素;（b是相应于（a的切割,而最小切割即为优化分割。
可见,这里的分割是一典型的二元标号问题。
◇@
（aAgraphG（bAcutONG
图1一个简单的3X3二维图切割
№1Asimple2-Dcutexamplefora3X3image
经过多年的发展,已经出现了可以在多项式时间内求解最大流/最小切割的算法。
解决最大流问题常用到Ford-Fulker—son方法（较多地是使用Edmonds—Karp算法、Pushrelabel算法和Relabel—to-from算法等。
实现FOrdFulkerson的时间复杂度主要取决于如何寻找增加路径,Fxtmonds-Karp算法采用了广度优先的搜索策略,但这种算法的效率并不很理想;Push-relabel是预流推进算法,很多渐进意义下最优的算法都是采用了此算法的思想,很多相关问题,如最小费用流问题,用这种方法可以得到很好的解决;Relabel-to-front算法是在Push-relabel算法的基础上进一步提升了效率。
关于这3种常用算法的时间复杂度可见表1,其中V表示图的顶点数,E表示边数。
这些求解最大流/最小切割的方法,不仅在网络流如交通运输、电力传输、金融系统和通讯系统等方面广泛应用,而且目前在计算机视觉中也日益得到重视。
表1最大流算法的时间复杂度比较
3hb.1Thecomparisonofcomplexityofnmximum-flowalgofithmsAlgorithmEdmonds-KarpGenericpush-relabelRelabelto-frontC0“:
2蠹罴。
ofth。
O（V”口2o（驴2+Do（驴3
光电子・激光!
塑!
堡箜!
!
鲞
3基于图切割的人体运动检测
本文的方法包括:
色相、饱和度和亮度（HSV转换、建立背景模型、阴影检测和最小切割分割等4部分,流程图如图2所示。
图2算法流程图
n晷2Flowchartofalgorithm
3.1HSV颜色空间转换
大多数视频捕捉设备采用红、绿和蓝（RGB颜色空间[8|。
但是由于R、G和B3个分量存在相关性,所以在面向彩色处理时通常不直接使用RGB颜色空间,而采用其变形或其他颜色空间。
HSV颜色空间把颜色表示成H、S和V3个分量,它们独立感知颜色变化,相互独立,互不影响,从而能够提高算法的稳定性。
另外,在HSV颜色空间便于消除阴影,所以本文采用HSV颜色空问。
3.2建立背景模型
摄像机固定,如果背景完全静止,背景图像的每个像素点可以用高斯分布来描述。
但背景场景往往不是绝对静止的,例如由于树枝的摇摆运动、水面波动等原因,使得固定位置像素的值在不断改变,显示出非单峰分布的特点,所以使用单峰模型的方法去表述背景往往不能准确地模拟背景的变化。
另外,由于这些像素的值变化是较快的,像素的变化并不是由一相对稳定的单峰分布渐渐地过渡到另一单峰分布,所以对于存在着这样变化的背景,使用单模型去模拟背景是不够的。
考虑到背景像素的值在一段时间内的分布是多峰的,实际情况下采用混合模型来模拟场景中像素的变化情况。
本文在HSV颜色空间建立高斯混合分布[9]描述背景模型。
设用来描述每个像素点的高斯分布共K个（通常取3~7,混合模型中每个像素X可表示为
冠一熙]
v
L^o.tJ
（2
则像素的函数可表示为
K
P（Xt一∑嘶,￡×叩（五,肛∽∑Ⅲ（3、]、]
i=1
其中,coi,z是第i个高斯分布的权值州一∑“分别为第i个高斯
菱雾,誓了名
妒 万
方数据
第6期侯叶等:
基于图切割的人体运动检测
分布的均值和协方差矩阵。
埘一∑如可写为
∑。
一diag[（ah,;2（as,。
2（av,t2]（4
背景建模过程为:
1初始化模型,取K一3。
一种简单的做法是当场景中无任何目标时采集多幅图像,对多幅图像进行平均作为初始背景图像,该图像每个像素的高斯分布均值作为3个混合高斯分布均值的初值,高斯分布方差作为3个混合高斯分布方差的初值。
2模型学习。
每一帧t,用新的像素值与混合模型中K个分布进行比较,若满足匹配条件,所匹配的第i个高斯分布的权、均值和方差按照一定的学习律进行更新,若没有找到匹配的高斯分布,用新的高斯分布代替优先级最低的高斯分布。
将K个高斯分布按照优先级高低次序排列,前B个分布作为背景模型,B定义为
B—argrnjn（>:
COi>蚴（5b。
i。
一1
式中,M是预先定义的阈值,表示能真正反映背景的数据占总数据的最小比重。
为了简化模型,这里取wi/仃i最大的高斯分布作为背景模型。
匹配准则为
l五一地。
I<2.陆,r（6均值与方差的更新为
肚“件l一（1一a/ai。
f+乜Xl（70"/,升1一（1一口国,￡+口（五一岸i,￡T（X一川.f（8权的更新为
撕一（1~a‰+口M^（9肌媳一髂罢署
为了提高程序执行效率,快速完成背景的提取,引进了阈值。
如果一像素长时间没有变化,认为它是静止的,所以可以比较当前帧和以前的参考帧;如果像素的差值小于一定的阈值,可以直接认为当前像素为背景的一部分而跳过自适应的过程。
3.3阴影检测
由于光源的原因,视频对象可能在背景中留下阴影,在运动目标检测时常常将阴影错误地理解为前景,产生了一系列与阴影有关的问题,如目标的合并和丢失（阴影覆盖相邻的目标以及形状的扭曲。
而且,由于阴影对目标检测的负面影响,对后续的目标跟踪、识别、分类造成负面影响,导致错误率大大上升,使系统的整体性能下降。
在实际应用系统中,目标总伴有阴影,必须去除阴影,才能正确进行目标检测。
阴影检测的方法有很多种,本文采用在HSV彩色空间消除阴影。
由实际视觉经验可知:
在一定的亮度条件下,同一物体在阴影区和不在阴影区的H是近似一致的,阴影主要使该区域内色彩的明暗发生变化,即y有变化,这对消除阴影提供了方便。
也就是说,有阴影的背景比无阴影的背景的V低,所以可以适当的降低V,有效地确保阴影区域不会属于前景。
3.4最小切割分割
第1步,把图像表示成网络图,如图1所示。
不过本文采
用8连通邻域,每个顶点连接10个点:
s、t、8个8连通近邻点。
S和t连接所有的顶点。
这里把图像表示成8连通的网络图G（V,E,即对应每一像素的顶点口,vEV,与它的8个近邻点有边缘连接。
图3显示了一简单的同类区域的例子,说明为什么8连通比4连通好些[5|。
盟黯隧霆（a4一connectivity（b4一connectivity（c8-cormectivity（d8-connectivity
图3同类区域的4连通与8连通
H舀34-connectivityand8-connectivity
graphsforahomogeneous
a啪
设每一边缘具有容量1,黑色边缘表示割的边缘,虚点表示割。
同类区域下,图3（b、（d中相应割的轮廓比图3（a、（c中相应割的轮廓要好些,因为前者有比较短的路径。
图3（a、（b有相同的容量6,它意味着如果使用4连通,这2个割结果不能区别,而图3（c、3（d有不同的容量15和11,这意味着具有最短路径的割具有小的容量,这是我们所期望的。
第2步:
构造能量函数。
如图l,有2种类型的边:
n_连接和t_连接。
t-连接是顶点与终点的连接,n-连接是顶点与相邻顶点的连接。
本文中,数据约束（m连接取自当前帧与背景图像的差分数据,光滑约束（m连接来自于8连通邻域的形状约束。
最后,求解能量函数的最优值。
本文采用Push-relabeI算法[10]求解最大流,即可等价的求取最小切割,完成运动目标的优化分割。
4实验结果及分析
实验的硬件平台为2.6GHzP4,内存为512MB;算法使用Matlab语言实现。
采用的图像序列源自普通的数码相机所录制的视频。
为了更好地说明问题,测试视频选用不同质量的室内和室外视频流。
用于分割的所有图像序列未作任何预处理,为了比较,分割结果也未作后处理。
重要参考参数为:
r一15,shadow=0.1,hdiff=0.4,sdiff=0.05,wdiff=0.15,a=O.01。
其中,T为分割阈值,T值太小,分割结果包括太多的背景,T值太大,分割结果丢失太多运动目标;Shadow为消除阴影的参数;hdiff、sdiff和vdiff为提取背景时,为提高程序的执行速度所采用的阈值;a为均值与方差更新的学习率。
图4（a是室内视频流,背景较为简单,环境为普通室内环境,地面和墙面有反光和阴影,图像大小为240X360,图像的边缘稍有模糊;图4（e是室外视频流,光照条件较好,光线均匀,图像较为清晰,墙面有反光。
在同样的条件下,分别采用了数学形态学图像分割[11]、混合模型4连通最小切割和混合模型8连通最小切割。
可以看出,采用最小切割的方法具有良好的结果,边缘比较光滑,而且分割结果比较干净,而8连通比4连通有更好的效果。
在同一检测条件下,对I帧图像进行分割,4连通最小切割花费的时间为o.391s,8连通最小切割花费的时间为0.532s。
r=l“I一医一严 万方数据
光电子・激光』07笙箜!
璺鲞
图4几个运动检测结果比较
晦4
comp=isonofseveralresults0fhumanmotiondetection
对背景较为复杂、水面有波动及远处有人晃动的情况下,分别采用单模型背景和混合模型背景对人体运动进行检测,检测结果如图5所示。
由图可见,采用混合模型比单模型效果好,而且有良好的鲁棒性。
图5
8连通下不同背景模型的分割
F喀5
msegmentation
resultsfor
differentbackgroundmodels
由以上的测试视频序列可以看出,利用图切割优化算法,可以得到良好的运动检测结果,所有区域被赋予惟一的属性,不属于“前景区域”就一定会属于“背景区域”,所以它的分割结果很干净,边缘较光滑,但实时性还有待于提高。
5结论
针对摄像机固定的情况,研究了利用图切割对人体运动进
行有效检测的方法。
通过HSV彩色空间转换、建立混合的背景模型、消除阴影和最小切割等步骤完成了对人体运动的检测,获得了干净、边缘光滑的分割结果。
结果表明,本方法可快速、有效和鲁棒地对人体运动进行检测。
精确快速的运动分割是困难的,如何更好地使用图切割技
术进行人体运动检测及运动分析还值得我们进一步研究。
参考文献:
[1]
BO冰OV
Y,KolmogocovV.Anexperimental
Ixm'lDarison
of
rain-cut/
try-flowakjodlllm
for
energy删zation
in
vision
l-J]./EEE
T删iortsOn
Rcf娜At蛳isand
M蜘栅鲫嘞,2004,26
（9:
1124.1137,
[21
KolmogorovV,ZabihR.Whatenergyfunctions
carlbeminimizedvia
graph
cuts?
U].1旺Tronsactions011
Pattern加lysisondMnchine
Intellegenoe,2004,26（2:
47—159.
L3jBoykovY,JollyMP.Interactiveorgansegmentationusing
graphcuts
[Aj.Th『rd
IntemetionalConference017
Medical
In铂ge娜咖and
Computer-AssistedInterventionlC2000,276—286.
[4]BoykovY,KolmogorovV.CornputinggeodesicsandminimaIsurfaces
viagraph
cuts[A].IEEEIntemationcdQ州卧钔∞∞Computer慨加
[c].2003,26—33.
[5]Xu
N,Bansal
R,AhujaN.Objectsegmentationusinggraphcutsbased
active
contours[A]IEEEc∞私玷钟SocietyOonferenoeOnc狮职科一
er
Vision删PettemRecognition[c].2003,46-53.
[胡CookWJ,OamingllamW
H,PulleyblankWR,etQf.Cotrbinatoriel
Optimization[M].NewYork:
John
WileyandSons,1998.355.
[7]Greig
D,PorteousB,SeheultA.Exactmaxirrum
a
posteioriestimation
forbinary
in酬J].Journal
oftheRoyalStatistioalSociety,Series
B.1989,51（2:
271.279.
[8]矾Ming,ZHANGJian-xun,VWl3
Xiang-hui,et
01.Color∞孵n—
tationofnucleiofbloodcellusingsupportvector
machines[J].栅
n田ofOptoelectomics・Loser（光电子・激光,2006,17（4:
479-
483.（inChinese
L9]Harville
M,Gordon
G,WoodfillJ.Foregroundsegmentationusing
a-
dapt№mixturemodelsincolorand
depth[A].IEEEWorkshopon
DetectionandRecognitionofEvents/nVideo[C].2001,3-11.
[10]Cherkassky
BV,GoldbergAV.On
i删ing
thepush-relabel
methodforthe
maxirr硼flow
problem[J].A/godthm/oa.1997,19
（4:
390.410.
[11]WangD,Haese-OoatV,BrunoA,eta『.Somestatistical
propert融of
mathematical
morphologyE出.旧王Transoctiens∞s/gm/Prooess-
/rig,1995,43（8:
1955—1965.
作者简介:
侯叶（1969一,女,陕西人,博士研究生,主要研究方向为人体运动分
析、图像处理和智能系统.
万
方数据
基于图切割的人体运动检测
作者:
侯叶,郭宝龙,HOUYe,GUOBao-long
作者单位:
西安电子科技大学机电工程学院自动控制系,陕西,西安,710071刊名:
光电子·激光
英文刊名:
JOURNALOFOPTOELECTRONICS·LASER年,卷（期:
2007,18（6引用次数:
1次
参考文献（11条
1.BoykovY.KolmogorovVAnexperimentalcomparisonofmin-cut/max-flowalgorithmsforenergyminimizationinvision2004（9
2.KolmogorovV.ZabihRWhatenergyfunctionscanbeminimizedviagraphcuts?
2004（23.BoykovY.JollyMPInteractiveorgansegmentationusinggraphcuts2000
4.BoykovY.KolmogorovVComputinggeodesicsandminimalsurfacesviagraphcuts20035.XuN.BansalR.AhujaNObjectsegmentationusinggraphcutsbasedactivecontours20036.CookWJ.CunninghamWH.PulleyblankWRCombinatorialOptimization1998
7.GreigD.PorteousB.SeheultAExactmaximumaposteioriestimationforbinaryimages1989（28.曾明.张建勋.王湘晖.赵雅静.陈少杰基于支持向量机的血液细胞核彩色图
升级会员 