基于圖割理論的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方法結合的性能.由于