基于图割理论的meansshr尺度自适应算法

基于图割理论的meansshr尺度自适应算法

基于视频序列的目标实时跟踪在计算视觉领域起着非常重要的作用，如视频监控、智能行为分析、人机交互、军事国防等。因此，在当前的跟踪技术中，傅佳纳等人提出的序列跟踪算法是一种非参数估计密度算法，通过迭代快速收敛到概率密度函数的局部最大值。之后，comanciu等人将其应用于视频跟踪和图像分割，并取得了良好的效果，成为重要的视频目标跟踪算法。虽然MeanShift是一种常用的跟踪算法,但还不能很好地解决跟踪过程中窗口尺度自适应问题.在MeanShift算法中,跟踪窗口的大小直接影响着参与计算的像素点的范围和个数,如果跟踪窗口跟不上目标实际尺度的变化,缺乏必要的模板更新造成跟踪结果在目标区域内游荡,陷入局部极值,这种情况可能导致跟踪目标丢失.而跟踪窗口过大则会把一些不相关信息包含进来,致使收敛速度过慢以至不能准确地跟踪目标.由此可知,尺度自适应问题解决的好坏直接影响者MeanShift算法的鲁棒性.针对这个问题,国内外许多研究人员提出了多种调整跟踪窗尺度的算法.经典解决办法是文献中提到的在上一帧跟踪结果的基础上缩减10%的尺度和上一帧尺度这3种窗口下分别执行MeanShift算法,并选出相似度系数最高的窗口作为最佳跟踪窗.这种方法计算量较小,实现简单,所以被多次引用.目标尺度慢慢变小时,尺度自适应效果显著;当日标尺度逐渐变大时,由于基于Bhattacharyya系数的相似性度量经常会在较小的跟踪窗口中达到局部最大,所以核窗宽很难被变大,反而经常越变越小,这样就失去了尺度自适应性,而且不能适应尺度快速变化的情况.还有一些基于这种思想的改进方法,比如Collins提出通过增加一个额外尺度核,在定义的离散尺度空间中进行Mean-Shift迭代以找到最佳核窗宽,由于所采用Epanechnikov核的导数为常数,Mean-Shift迭代过程等效于在空间定位的基础上对尺度空间进行平均操作;还有研究人员提出通过修改最优带宽的判别条件、选用自适应的滤波器参数两项措施对经典算法进行改进,这些都是基于尺度缩放模式进行的改进,不能根本解决尺度自适应问题.另外,有人采用对比图像两类特征点信息量的前后变化来判断目标尺度变化,即根据实际视频中目标尺度变化速度,每隔N帧统计一次被跟踪目标信息量,然后根据信息量的变化对跟踪窗口尺寸作相应更新.这种方法虽然改善了经典算法中目标变大时的跟踪效果,但是会突然变大或变小,即不能稳定、正确地反映目标实际尺度的变化.在图像处理和计算机视觉领域中,图像分割在图像匹配和目标分割领域得到了广泛应用而受到国内外很大重视,Gibbs能量最小化方法是计算机视觉中解决图割的常用方法.Gibbs方法将图像分割看作二值分类问题,构造图如下:顶点表示像素点,边表示像素点的四邻域或八邻域,而二值分类问题就是对图中所有顶点进行0,1划分,即求图像分割中的最小划分问题.由Greig等人首次引入视觉领域用以解决能量最小问题,并经过Boykov和Funka-lea改造的最大割/最小流方法将图的理论成功地应用到图像分割中,二者的有机结合就形成了现在广泛应用的图割理论:首先利用Gibbs方法将一幅图像映射成一个网络图,并建立关于标号的能量函数,然后运用最大流/最小割算法分割图,得到图的最小割,最终分割出目标.由于目标提取问题的复杂性,目前还没有一种方法能够达到准确无误的分割目标.因此,修正提取结果中的局部错误也是一项非常重要的工作.文献通过在目标边界添加硬约束点,约束轮廓线必须经过所添硬约束点来实现修正,但每添加一个硬约束点后整个环状区域都要重新进行切割,甚至可能因为强制通过指定点导致已有正确轮廓曲线段的破坏而造成新的错误.文献通过在错误区域添加目标或背景的种子来实现修正,但是会增大计算量.本文用到的图割理论主要是用来提取目标尺度,无需非常精确地分割出目标,所以为了提高跟踪效率而简单修正提取结果中的局部错误:在计算图割团块时,取目标中心上下和左右N个像素点位置的平均值来减小目标尺度提取的误差.本文在分析和验证其他算法不能很好地解决MeanShift跟踪时尺度自适应的基础上,提出将图割理论引入到MeanShift中协助解决这一问题的方法.首先利用MeanShift找出目标的中心,用K均值聚类算法得到像素的初始标号,然后建立一个关于标号的能量函数并构造相应的图网络,通过计算出图的最大流完成图割.根据图割出的跟踪目标实际大小来调整跟踪窗口,从而完成实时鲁棒精确地跟踪任务.因为图割理论是依据肤色高斯混合模型在跟踪窗口周围搜寻肤色团块,所以图割结果是当前跟踪目标实际大小,这是与经典尺度解决方法完全不同的原理,从而可以避免经典尺度适应策略未能彻底解决的问题,同时也避免了背景中其他目标的干扰,因为图割是在目标周围的局部区域内进行,所以排除了整个背景中其他目标或是别的因素的干扰.经实验验证,本文算法提高了跟踪系统的实时性和鲁棒性.1经典的meanhit算法和离散理论1.1跟踪窗口s设计MeanShift算法并不是完全自动的跟踪算法,在跟踪序列的初始帧或某一合适时刻,需要人工或识别算法确定目标来构建参考目标模板;然后在每一帧对应位置计算候选目标模板;比较两个模板相似度,迭代到相似度最大的位置,即为目标真实位置.其算法简要介绍如下:若用{xi}表示目标窗口中的像素点,首先对被跟踪目标按照式(1)进行参考模板的核直方图建模,即建立目标模板为其中,x0,x1,分别表示目标中心像素坐标和第i个像素坐标;n为目标像素总数目;m为颜色分量u的总数目;K(‖x‖2)是核函数;h表示核函数的带宽,也是跟踪窗口的宽度;δ[b(xi)-u]是Kronecker脉冲函数;函数b(xi)将每个像素点映射到相应的特征空间中;C为归一化常数,使得,即,在后继的跟踪过程中也采用类似的方法,令{xi}表示当前帧候选窗口中的像素点,从而得到被跟踪目标在位置y的候选模板核概率密度为其中,u=1,2,3,…,m;Ck为归一化因子,可以由推导出nk为目标候选窗口中像素点的个数.相似性函数是表示参考模板和候选模板之间的相似性程度.Comaniciu采用Bhattacharyya相似度来描述参考模板和候选目标之间的相似度:参考模板和候选目标之间的距离表示为ρ(y)泰勒展开为其中,显然ρ(y)的值独立于第1项,要使ρ(y)极大,只需极大即可,经推导可得出每次MeanShift的迭代中心为跟踪过程就是按照式(7)进行迭代,其中xi表示像素点在候选目标中的位置,其初始中心位置设为y0,在进行迭代之前,y1初始化为y0,每次迭代完成,用新得到的y1替换,直至y1收敛到一个不变的值,从而找到最佳模式匹配位置,实现目标跟踪.1.2基于能量函数的图像分割图割理论基于图的组合优化思想,将一幅图像映射为一个网络图,并建立关于标号的能量函数,由最大流最小割定理可知:可以通过图像所构造出来的网络最大流来得到图的最小割.因此首先需要把要解决的问题构造成能量函数,然后构造图像网络来得到最大流.设有向图用G=<V,E>表示,其中V表示图的节点集,包括两类节点:普通节点P={Pi|i=1,2,3,…,n};端节点s和t,其中s为入度为0的源点,t为出度为0的汇点,E={<u,v>|u∈P,v∈P}为边集,每条边均有一定的权值ω<u,v>.图割就是通过把图中某些边去掉从而把点集划分为两部分S和T,分割结果需要满足源s∈S,t∈T,S∪T=E,且.这些边组成割集S-T,最小割就是割集S-T中边权值之和最小的割.为了将上述理论应用到图像分割中,假设一幅图像的像素点用集合P={Pi|i=1,2,3,…,n}来表示,集合O和B分别表示P中两个不同集合“目标”和“背景”.二者存在如下关系:且,并且满足.欲要分割出“目标”,需要引入Gibbs能量函数:其中,P表示图像点集,N表示S的邻域系统,而表示像素pi的标号,即若用1来表示属于目标割的标号,那么就用0来表示属于背景割的标号.另外和分别表示将元素和边<pi,pj>标号为目标的代价,当划分结果越符合实际情况能量函数值越小,反之则越大.因此可以通过求能量函数最小值来得出最符合真实情况的目标分割即最小割.由上述分析可知,能量函数是解决图中顶点标号问题的,所以构造能量函数是一个关键步骤.不同能量函数在构造图时对应边所赋权值的方法不同.图像纹理、色彩、边缘等特征都可被用来建模构造能量函数,具体构造图时所使用的信息量要看具体环境以及该信息量的区分度.2图段理论对meanhit的规模控制2.1局部图割+局部图割在视频目标跟踪研究中,由于MeanShift方法具有很多优良特性,比如出色的搜索效率、简单的实现方案等很快成为经典跟踪算法.但是当跟踪目标尺度发生变化时,如果没有合适的尺度变化策略,搜索目标就会受影响.比如目标变大时搜索窗口会在目标区域内漂移,影响了目标实际中心的判断,而每一帧初始窗口位置是是基于上一帧跟踪结果来初始化,所以误差会累计,影响跟踪效果.针对此,在执行MeanShift之后引入尺度自适应策略.即对每一帧图像首先采用MeanShift来进行迭代跟踪出本帧图像中目标的中心坐标点,然后利用图割提取和修正当前目标的尺度变化并实时地显示出此刻目标真实位置和大小.如图1中本文算法流程所示,当视频序列运行到合适位置时,用户可以通过两种方法选择跟踪目标:基于AdaBoost的人脸自动检测方法和利用鼠标选取跟踪区域的手动选择方法.目标选定之后即可开始跟踪程序:MeanShift算法在定位目标中心时表现非常出色,所以对每一帧图像首先进行MeanShift跟踪出目标中心,在跟踪目标左右上扩展若干个像素得到的局部区域内执行图割算法.割出若干个肤色团块,检测出最大团块,判定并调整目标跟踪尺度.这样局部图割可以大大降低计算量,同时还避免了整个背景中其他接近肤色团块物体带来的干扰.比如在对人脸跟踪过程中,若背景中有其他人脸或是手出现时,在整个背景中图割出所有的肤色团块,这时就很难确定出跟踪目标,因为跟踪目标不一定是最大团块,但是在MeanShift迭代结果的周围进行图割,那么最大的肤色团块必然是跟踪目标.2.2局部图割算法首先需要收集上千张不同人的肤色图像,在RGB颜色空间内进行肤色统计.为了求取精确肤色模型来表示肤色的分布,本文采用高斯混合模型来逼近肤色概率分布,公式如下:其中,K代表高斯混合模型中高斯模型个数;Wi表示第i个高斯所占权重值,所有Wi,值之和是1,r表示欲求的肤色概率值;μ表示第i个高斯分布的平均值,Σi示第i个高斯分布的共变异矩阵(covariancematrix),代表参数(ω,μ,Σ)的训练量可借由K-Mean算法来估算参数求得.通过这一步工作得出一组像素点的肤色判定概率值.参考目标模板作为源点S,当前帧候选目标区域内像素点作为图中普通节点,不属于跟踪目标的点作为终点,所以图割结果就是跟踪目标和不属于目标像素的背景两个割,如图2所示:如源点S是肤色值,点集P是跟踪区域内待判定点,此时需要把上一步骤得到的一组概率值赋给从S点到每个普通节点的边W(pi),普通节点之间的边也有一定的权值W(<pi,pj>),因此能量函数可以构造如下:其中,P表示图像点集,N表示S的邻域系统,W(pi)和W(<pi,pj>)分别表示将元素pi和边<pi,pj>划分为目标的代价,本文把图像中像素点判定为肤色点的概率值作为图中边的权重,即把像素点pi为肤色点的概率值赋给W(pi),而为了简化系统,将W((pi,pj>)赋值为一个常数.分割实验如图3所示:3组图像分别是人脸的局部图割、全局图割以及手的全局图割,每组图像包括左边的原始图像和右边的二值化图.原始图像是待分割图像,黑白图是分割出的二值化图,分割出的目标颜色值被标示为255,背景被标示为0,所以在分割结果中,白色团块即为割出的肤色团块.从图3(c)可以看出,本文图割算法不仅可以用于人脸跟踪中,也可以用于手部等其他肤色跟踪之中.局部图割是在跟踪窗左右扩展M个像素点、上下扩展N个像素点的矩形区域进行的,而全局图割是在整幅图像进行的.本文采用局部图割是因为这种方法不仅很大程度上减小了计算量,而且避免跟踪目标周围与肤色相近物体的干扰,如图3(b)可知:人物后面的黄色柜子出于与肤色相近导致图割出的团块中,作为跟踪目标人脸不是最大团块,这就会造成目标尺度发生错误的变化,甚至会导致目标跟踪漂移或丢失.而第1幅图像是在人脸附近的小区域内图割,从图割结果中可知,最大团即为人脸,经过后续尺度修正即可得出更逼近真实尺度的跟踪窗口.在图割算法的时效性能上因采用不同的maxflow/mincut算法而有所不同.文献给出了常用的最大流算法性能比较,本文采用的是Boykov等人在2004年提出的一种基于增广路径的求解naxflow/mincut算法,一般情况下会很快.假设构造的图中像素点个数为n,边数为m,,则一般的maxflow时间复杂度为()(n2m),而Boykov等人提出的改进最大流算法比其他的算法要快2～5倍,若跟踪窗口宽和高分别用h1和h2表示,那么进行图割的图像大小宽为h1+2M,高为h2+2N,则n=(h1+2M)(h2+2N).由此得知图割算法复杂度主要与进行图割的区域大小有关,所以局部图割可以减小计算量,提高跟踪效率.2.3brattacherat:局部图割目前有多种方案解决尺度变化问题,但是还没有一种方案可以稳定地、实时地反应跟踪目标尺度变化.缩放10%窗口经典方法有小窗口趋势,即比实际尺度偏小时,其Bhattacharyya系数达到最大.而最佳窗口的依据就是在这3个尺度下进行MeanShift迭代,取得Bhattacharyya系数最大时所对应尺度大小.所以利用如下实验来验证Bhattacharyya系数的局部极值现象:截取同一视频序列中3幅人脸,分别是原始大小、人脸变大和人脸变小3种情况,如图4(a)所示;首先在原始图像中取出目标模板,然后在放大图像中改变跟踪窗口尺度,令窗口分别向左右以1个像素为单位增大和缩小各10次,所以每幅图像都跟踪20个不同大小的窗口尺度,缩小图像也是如此操作.实际测得原始人脸尺度宽62;人脸变大时尺度宽85;人脸变小时尺度宽45,理论上Bhattcharyya系数应该在放大图像中的85和缩小图像中的45处取得最大值.图4(b)(c)分别表示人脸变大和变小情况下Bhattacharyya系数实验数据.横坐标表示跟踪窗口的宽度,以像素为单位,纵坐标表示Bhattacharyya系数.从图4(b)可以看出Bhattacharyya系数是在宽度69处取得最大,并非宽为85处最大,而且Bhattacharyya系数值在窗口偏小时反而比较大,验证了尺度放缩10%方法所存在的缺陷.而当人脸变小时Bhattacharyya系数实验数据虽然在真实尺度处取得峰值即最大,但周围存在突变现象,只是取得了局部极大值,不一定是最大值.实验中每次跟踪窗口变化时初始中心都是上一帧跟踪结果,所以实验完全符合一般的MeanShift流程,具有参考价值.从实验中得出结论:经典尺度缩放算法所依据的“对象的真实尺度定发生在相似性系数取最大值处”有其局限性,因此凡是基于这个跟踪窗尺度变化模式的改进方法都会存在这个本质问题,而本文改用不同的模式来避免这种问题,图割的引入可以更准确地获得目标实际尺度.在利用图割算法提取的若干肤色团中,需要判断哪个团是真实跟踪目标,然后得出当前目标尺度.由于图割时采用局部图割法,并不是在整个背景内图割,显然可以得出最大肤色团块必定是跟踪目标这一结论.因此,只需在图割结果中检测出最大团即可.检测肤色团块的理论依据是四邻域判断图连通性,即判断一个像素点若是肤色点,则判断像素点的上下左右是否也是肤色点,若有一个方向的像素点是则和该像素点归为一类标签,由此得到了不同标签表示的不同大小团块,然后在这些团块中寻找出像素点最多的团即为最大团块.检测出最大团之后,就可以得到目标团最左和最右边像素点x1和x2,那么目标尺度的宽可以表示为w=x2-x1,之所以选择左右距离之差来判断尺度,是因为脖子也是肤色,此时上下像素点距离之差可能因为受到脖子的干扰而使尺度偏大.但是这样的尺度获取方式存在可修正的误差,比如最大团中最左边和最右边像素点只是个别点,此时得到的尺度仍然会偏大,因此作如下修正:由MeanShift可以得出目标中心表示为(x,y).也就是说根据图割出的最大团,找出中心处(x,y)中y所对应的最左边的像素点为(x1,y),然后取出y+i,y-i(i=1,2,…h)在最大团中所对应的2h个横坐标值,然后求出x1和这2h个横坐标值的均值赋给x1,最右边的x2也是如此方法求出.通过这样得出的w=x2-x1将更能接近目标真实尺度.如图5所示:4幅图像依次是原始图、图割结果、最大团检测结果(最大团赋值为灰色)、跟踪结果.如果不经过左右像素的修正那么跟踪结果应该是虚线框内的人脸,不如实线框内的跟踪效果显著.得出了此时目标的新尺度的宽w之后,按照与上一帧尺度的比例来得出新尺度高h,然后跟踪结果就可以显示给用户.整个跟踪过程如算法1所示.算法1.1)通过上千张肤色图像建立肤色高斯混合模型;2)采用自动检测或手动选择跟踪目标,得到目标区域Rect并计算出目标模板的颜色直方图,通过Rect可知目标的长为h0,宽为w0;3)执行MeanShift,对于后继视频中每一帧,只需计算出候选模板的颜色直方图来求得Bhatta-charyya系数最大时的跟踪中心(x,y);4)在跟踪区域的上下扩展M个、左右扩展N个像素点作为图割区域,即矩形区:左上角点(xw0/2-M,y-h0/2-N)和右下角点(x+w0/2+M,y+h0/2+N);5)对图割得到的肤色团块检测最大团:并计算出w=x2-x1,则h=h0(w/w0);此时即可得出当前跟踪目的区域:左上角点为(xw/2,yh/2)和右下角点为(x+w/2,y+h/2);6)继续读入视频执行步骤3)～5)的运算,若结束则退出.3实验结果与分析实验视频序列是实验室内环境的自拍视频,使用普通USB摄像头,视频图像分辨率为320×240,两段视频分别是人脸跟踪和手部跟踪.人脸视频中图割的区域参数是跟踪窗左右各扩展20个像素,上下各扩展30个像素,即M=20,N=30;在检测出最大团之后提取尺度时,采用的距离中心点上下各5个像素点来求得平均值x1和x2,即H=5;为了减小计算量,实验中并不是每一帧都进行尺度自适应,而是每隔5帧执行一次尺度提取,实验结果表明这种间隔判断法在效率大大提高的情况下还能很好地判断尺度变化.图6(a)(b)分别是第37帧、78帧、137帧、153帧、163帧、202帧时采用2种不同的方法实验出的跟踪结果对比图,视频拍摄的是目标从变大到变小这一过程,所以这6帧对比图可以看出不同尺度适应算法的性能.文献中提出了信息量判定方法来修正跟踪窗口尺度,并和经典的缩放10%方法作出了对比实验,指出了该算法在调整跟踪窗口尺度的性能提高,因此本文选择和改进的信息量判定方法进行对比实验.1图6(a)是采用信息量跟踪尺度变化方法的跟踪结果,图6(b)是本文中尺度自适应得出的跟踪结果,图6(c)是图6(b)所对应的图割区域中判别出跟踪目标的结果,白色和灰色团块都表示是肤色团块,而灰色表示最大肤色团,即跟踪目标.从对比实验中可以看出,图6(a)的尺度适应具有滞后性,而本文中算法却可以实时地调整尺度变化.图6(a)采用的是信息量判定方法,即提取出目标颜色特征的极值点和拐点作为图像第1类和第2类特征点这些特征点个数之和称为图像的信息量.然后将跟踪窗分别乘以1.5和0.5,则这两个跟踪窗包含的信息量分别用I2和I3来表示,每5帧之后的1.5和0.5倍窗口包含的信息量分别用I5和I6来表示,判断依据是I5-I2>0,则判断目标尺度可能增加,否则判断尺度可能变小.这种方法之所以实验出这样的结果是因为大窗口下包含的信息量必然比小窗口中的多,所以跟踪窗口总是趋于偏大.而图割方法则是根据当前目标实际大小割出的肤色团块,因此更能逼近真实值.为了更充分地验证本文算法的跟踪性能,我们又做了关于手部跟踪的实验.视频总共564帧,由于手的特殊形状,图割的区域参数变为跟踪窗左右各扩展20个像素,上下各扩展50个像素,即M=20,N=50;在检测出最大团之后提取后提取尺度时,采用的距离中心点上下各5个像素点像素点来求得平均值x1和x2,即H=5;以下6帧分别是第026,032,082,094,109,373的跟踪结果.图7和图6两组实验原理是一样的,都是和信息量判别法所做的对比实验.从这组实验可以很明显地得出结论:本文的算法尺度自适应性能比较好.不仅可以迅速地定位出目日标位置,而且可以根据实际目标尺度变化实时地调整跟踪窗.本文算法对于目标跟踪的左右边框控制很到位,由于手部指尖的不平整性可能会存在上下并不能完整地跟随其边缘,但是这已经可以比较好地应用到娱乐控制中.图8(a)(b)分别显示了利用MeanShift算法跟踪人脸和手时采用信息量判定方法和图割法来调整跟踪窗尺度的性能图,横坐标表示帧数,纵坐标表示跟踪结果结果与真实位置之间的欧氏距离(用像素计算),真实位置是手动标记的.图8(a)(b)中上方曲线表示信息量判定方法的性能,下方曲线表示图割理论与MeanShift方法结合的性能.由于