基于視差和幀差的圖割優(yōu)化運動目標分割算法

朱秋煜，李琦銘，陳岳川

(上海大學(xué) 通信與信息工程學(xué)院，上海200072)

近年來，運動目標的分割得到了廣泛的研究，目標分割是運動人體信息采集的基礎(chǔ)。目前所提出的檢測運動目標的算法按照其原理主要可分為光流計算法、幀差分法和背景差分法。

對于單目視覺系統(tǒng)，背景實際上就是場景的灰度或色彩，當前景和背景色彩灰度接近時將很難分割前景。與色彩灰度相比，場景的深度通常較少受外部環(huán)境的影響，如果能通過立體視覺的原理得到深度信息，則前景目標的檢測將容易得多，可惜的是場景的精確致密視差常常難以獲得。為此，在以往的研究中利用能量函數(shù)最小化的優(yōu)化方法以得到較為準確的區(qū)域視差，但由于在某些場景下背景和前景的灰度信息過于相近仍不能達到很理想的視差優(yōu)化結(jié)果。所以本文研究在此基礎(chǔ)上將視差和幀差采用圖割優(yōu)化算法進行融合，以此提高前景目標分割的準確性。

利用立體視覺進行圖像檢測與分割的基礎(chǔ)是致密視差的計算。近年來，基于圖理論的算法在計算機視覺中得到了成功的應(yīng)用［1］，如圖像匹配與視差計算［2-5］、圖像分割［6-7］等。在視差計算方面，將原來的圖像匹配問題轉(zhuǎn)化為在搜索范圍空間內(nèi)尋找最優(yōu)匹配點這樣一個典型的尋優(yōu)問題。而在目標分割方面，本文采用將視差和幀差作為圖割算法里的能量函數(shù)的數(shù)據(jù)項，利用能量最小化算法確定運動目標的最佳分割。

1 區(qū)域視差匹配

區(qū)域視差的匹配可以分為以下4個步驟:1)把圖像分割成相似的視差平滑的區(qū)域;2)計算分割區(qū)域可靠點的初始視差;3)根據(jù)初始視差得到模板集合;4)構(gòu)造匹配代價函數(shù)并進行區(qū)域模板優(yōu)化以得到精確的區(qū)域視差。

1.1 圖像初始分割

圖像初始分割效果的好與壞會直接影響到后續(xù)工作中視差模板的估計，所以選用適當?shù)姆指钏惴ㄊ箞D像分成多個平滑的區(qū)域具有重要意義。在圖像分割算法中常用的有分水嶺算法、聚類算法等，這些傳統(tǒng)的算法的特點是具有較高的效率和實時性，但精確度有待提高且不太適用本文視差模板的計算。Comaniciu和Meer［8］在基于mean-shift的基礎(chǔ)上提出了一種新的圖像分割算法，該方法不僅具有效率高和實時性好的優(yōu)點，同時適用范圍廣且分割的結(jié)果具有較大的精確度，因此本文采用了該算法進行圖像的區(qū)域分割。

1.2 初始視差估計

視差估計匹配算法的相似度測量函數(shù)主要可歸納為三大類［9］:NCC(歸一化互相關(guān)函數(shù))、SSD(差值平方和函數(shù))和SAD(差值絕對值和函數(shù))。本文采用NCC算法［10］獲取圖像像素在不同視差情況時的匹配代價。匹配窗口的大小也能影響視差匹配的效果，較大的窗口在紋理信息少的區(qū)域能得到好的匹配效果，但在圖像邊緣等顏色梯度變化較大的區(qū)域則可能增強前景膨脹效應(yīng)，選取3×3較小的窗口能得到較準確的匹配點。

1.3 模板視差計算

本文引用TAO［11］提出的一種立體匹配算法，方法中提到如果能把圖像分割成多個視差平滑的區(qū)域，那這些區(qū)域中各個像素的視差可用一個平面模板公式來描述

式中:c1，c2，c3為模板參數(shù);(x，y)是圖像像素坐標;d為像素(x，y)對應(yīng)的視差值。

選取模板集合中的某一個模板計算視差，通過所得視差計算該區(qū)域內(nèi)的所有可靠點的匹配代價，那么匹配代價公式為

式中:CSEG(S，P)為平面模板P相對初始分割區(qū)域S的相似匹配代價;d為模板P在像素點(x，y)得到的模板視差;C(x，y，d)為當像素點(x，y)的對應(yīng)視差為d時的匹配代價。

1.4 模板視差最優(yōu)分配

本節(jié)的目的是通過選取最優(yōu)化的模板來提高視差計算的精度，對模板集合中的每個模板構(gòu)造能量函數(shù)，利用能量函數(shù)最小化［12］算法的思維解決模板視差的最優(yōu)分配問題。計算分割區(qū)域的能量函數(shù)表達式如下

式中:f表示當前區(qū)域使用相鄰區(qū)域的模塊參數(shù)的匹配關(guān)系。數(shù)據(jù)項為式(2)所定義的匹配代價

平滑項為當?shù)趇塊區(qū)域與第j塊區(qū)域為相鄰區(qū)域時的邊界長度

計算數(shù)據(jù)項時，將前面所得的初始視差利用最小二乘法計算出模板參數(shù)，由于圖像的分割區(qū)域的視差模板主要與其相鄰區(qū)域的模板相關(guān)，所以本文選擇了相鄰區(qū)域的模板作為該區(qū)域的模板集合以計算平滑項，有限的模板集合個數(shù)大大提高了模板優(yōu)化的計算速度。然后通過計算分割區(qū)域的每一個模板集合的能量函數(shù)，選取最小能量函數(shù)的模板作為該區(qū)域的最優(yōu)化模板。最后根據(jù)得到的最優(yōu)化模板參數(shù)代入公式便可得到修正后較準確的視差值。

2 三幀差分法

三幀差分法是選取視頻序列中連續(xù)的3幀圖像進行兩兩相減，即分別對第1幀和第2幀以及第2幀和第3幀的圖像進行差分，這樣得到的2幅幀差圖像都含有運動目標，最后把2幅幀差圖像進行與運算，便可得到基于運動目標本身的特征圖像。對三幀差分的結(jié)果選取適當?shù)拈撝颠M行二值化分割可得到運動目標。三幀差分法的公式如下

式中:It-1(x，y)，It(x，y)和It+1(x，y)為圖像序列當中連續(xù)3幀圖像。那么選取閾值λ，則差分圖像DΔt(x，y)經(jīng)過閾值分割得到的二值化圖像BΔt(x，y)為

三幀差分法充分利用了運動目標在視頻序列中的時間相關(guān)性，融合了前后幀圖像的像素信息，對于運動目標具有較高的靈敏度，可抑制隨機噪聲對于檢測的影響，同時也可以有效地適應(yīng)光線的變化，減少前景背景顏色灰度相近時的干擾。但其也存在著一定的缺陷，通過差值圖像檢測出運動目標比實際的要大，容易出現(xiàn)“雙影”現(xiàn)象，同時由于檢測出來的物體是前后幀相對變化的部分，無法檢測到重疊部分，導(dǎo)致檢測到的目標發(fā)生“空洞”現(xiàn)象，同時差分圖像對于不同的背景選取閾值上需要一定的工作量，以上因素導(dǎo)致了三幀差分法檢測結(jié)果不太理想。

3 基于圖割理論的目標分割算法

圖割是著名的最優(yōu)化問題算法。利用圖割算法進行圖像分割，首先需要建立一個與圖像對應(yīng)的加權(quán)無向圖。圖的頂點與圖像的像素對應(yīng)，邊與圖像各個像素之間的相關(guān)信息對應(yīng)，頂點屬性與圖像的像素信息(如顏色、視差、幀差等)對應(yīng)，邊的權(quán)值與像素間的一致性程度對應(yīng)，圖中還包括2個特殊的終端頂點——源點和匯點，可根據(jù)分割標準構(gòu)造源點和匯點。圖構(gòu)建完成之后，求解能量函數(shù)最小化從而實現(xiàn)圖像分割。

本文提出的基于圖割理論的目標分割算法可分為2個主要部分:1)結(jié)合視差和幀差特征構(gòu)造能量函數(shù);2)使用圖割算法最小化能量函數(shù)實現(xiàn)前景目標分割。

3.1 構(gòu)造能量函數(shù)

實際場景中的目標分割僅僅依靠視差特征很容易受到亮度的影響，所以本文結(jié)合視差和幀差特征來構(gòu)造能量函數(shù)解決這個問題。能量函數(shù)形式如下

式中:Ef和Ed分別是基于幀差和視差特征的圖像能量;ωf和ωd是加權(quán)因子，可以根據(jù)圖像的自身特征選擇幀差和視差特征在能量函數(shù)中所在的比重實現(xiàn)更好的分割效果。

視差特征的能量函數(shù)的基本形式包括一個數(shù)據(jù)項和一個平滑項，具體公式如下

式中，平滑項Edsmooth表示用于約束鄰接區(qū)域內(nèi)像素的一致性程度。本文采用的是Sobel梯度算子來計算當前像素與鄰接區(qū)域內(nèi)的其他像素的平滑程度，數(shù)據(jù)項表示對應(yīng)像素匹配一致性程度

式中:Dp用于表示當前像素的視差D(p)與背景視差或前景視差均值的不相似性。同理，幀差特征的能量函數(shù)的基本形式與視差特征的相類似

3.2 目標分割

根據(jù)圖割思想，對于圖像I進行背景和目標的分割過程，其實就是最小化函數(shù)Ed(f)的過程。使用圖割算法最小化能量函數(shù)，首先要構(gòu)造有向圖G=(V，E)［13］

G中有2個特殊的終端:前景端F和背景端B。本文選取前景和背景的特征均值作為其具體值。G中邊的集合E包括所有像素與它的鄰接像素相連的邊，以及所有像素和F，B相連的邊。最后，當求得圖G上對應(yīng)的最小化的能量函數(shù)時，可把圖像分為與前景端和背景端相連的2個部分，即判定與F相連的像素為前景目標，與B相連的像素則為背景。

4 實驗結(jié)果

為了驗證算法的有效性，本文對雙目灰度視頻序列進行了測試，所有圖片大小都是360×240。首先是利用能量最小化算法優(yōu)化圖像的致密視差。從圖1中雙目圖像可以看出背景中同時存在人和計算機等復(fù)雜信息，選取3×3小窗口計算的初始視差的值，在圖像區(qū)域初始分割后，利用能量函數(shù)優(yōu)化每一個分割區(qū)域的視差。可以看到，通過能量最小化的方法優(yōu)化后的視差，在同一特征區(qū)域內(nèi)都比較平滑，且去除了一些細小區(qū)域的干擾，得到了更為準確的區(qū)域視差。

圖1 視差計算及優(yōu)化

其次，利用三幀差分法同樣可以獲得圖像中的運動目標，圖2分別獲取同一視頻序列中的連續(xù)3幀圖片，同時對第1幀和第2幀、第2幀和第3幀進行圖像差分，最后把2幅幀差圖像進行與運算，便可得到基于運動目標本身的特征圖像。

圖2 幀差結(jié)果圖

最后，通過設(shè)定權(quán)值，結(jié)合幀和視差特征進行前景運動目標的分割，同時對比單獨使用視差和幀差分割圖像的結(jié)果進行分析。圖3能量函數(shù)的權(quán)值ωf和ωd根據(jù)實驗結(jié)果的經(jīng)驗取值分別為0.37和0.63，可以根據(jù)不同的場景進行適當?shù)恼{(diào)整，當前景和背景灰度相近時，視差特征的作用減弱，可以多考慮幀差的貢獻，而當幀差結(jié)果“空洞”現(xiàn)象較嚴重，可增加視差的比重。從實驗結(jié)果可以明顯地看出區(qū)域視差的優(yōu)化受到灰度因素的影響，有些背景視差優(yōu)化不夠理想，但運動目標整體的視差都較為平滑，而幀差分割的結(jié)果對于運動目標具有較好的邊緣信息，同時也存在許多的“空洞”，利用圖割結(jié)合視差和幀差特征能夠有效地整合二者的優(yōu)點，減少視差優(yōu)化不夠準確的區(qū)域被檢測為前景目標的可能性，同時也能填補大多數(shù)幀差分割的“空洞”。

圖3 本文算法與視差和幀差分割結(jié)果對比圖

為了進一步證明算法的有效性，同時給出了2組其他場景和亮度下的實驗結(jié)果，圖4中ωf和ωd分別為0.3和0.7，圖5中ωf和ωd分別為0.6和0.4。實驗組2中當幀差的結(jié)果受到運動目標灰度的影響比較大時，運用本文方法同樣可以填補較大的“空洞”。實驗組3是在夜晚燈光環(huán)境亮度不是很充足的情況下拍攝的，前景和背景灰度相近，增加幀差特征的比重，同樣也有效證明了算法的適應(yīng)性。此外，3組的 運算時間分別為12.58 s，8.80 s，10.05 s，可以看出并不十分高效，仍有改進之處。

5 小結(jié)

運動目標檢測一直是視頻跟蹤和分析的基礎(chǔ)，但是由于各種因素的影響一直沒得到很好的解決，因此，本文在以往通過視差優(yōu)化研究的基礎(chǔ)上，提出了根據(jù)視差和幀差特征的信息采用圖割優(yōu)化的能量函數(shù)融合分割出運動目標的方法。實驗結(jié)果表明，該方法相比于單獨的視差和幀差特征的分割具有了更高的穩(wěn)定性。

圖4 實驗組2的分割結(jié)果

圖5 實驗組3的分割結(jié)果

該算法仍有幾處改進之處，未來的工作可以考慮利用圖割算法結(jié)合更多的圖像特征結(jié)合，同時重點在于如何縮短運算時間，在提高分割準確性的同時提高算法的效率。

［1］ARORA C，BANERJEE S，KALRA P，et al.An efficient graph cut algorithm for computer vision problems［C］//Proc.11th European Conference on Computer Vision.Berlin Heidelberg:Springer Verlag Press，2010:552-565.

［2］KIM J，KOLMOGOROV V.Visual correspondence using energy minimization and mutual information［C］//Proc.IEEE International Conference on Computer Vision.［S.l.］:IEEE Press，2003:1033-1040.

［3］GAO Hongwei，CHEN Liang，LIU Xiaoyang，et al.Research of an improved dense matching algorithm based on graph cuts［C］//Proc.the 8th World Congress on Intelligent Control and Automation.Jinan，China:［s.n.］，2010:6053-6059.

［4］PAPADAKIS N，CASELLES V.Multi-label depth estimation for graph cuts stereo problems［J］.Journal of Mathematical Imaging and Vision，2010，38(1):70-82.

［5］WANG Daolei，KAH B L.A new segment-based stereo matching using graph cuts［C］//Proc.2010 3rd IEEE International Conference on Computer Science and Information Technology.Chengdu，China:IEEE Press，2010:410-416.

［6］MORENO R，GARCIA M A，PUIG D.Graph-based perceptual segmentation of stereo vision 3D images at multiple abstraction levels［EB/OL］.［2011-10-20］.http://www.mendeley.com/research/graphbased-perceptual-segmentation-stereo-vision-3d-images-multiple-abstraction-levels/.

［7］黃洋文，王紅亮.基于量子粒子群優(yōu)化算法的圖像分割方法［J］.電視技術(shù)，2010，34(4):16-18.

［8］COMANICIU D，MEER P.Mean shift:a robust approach toward feature space analysis［J］.IEEE Trans.Pattern Analysis and Machine Interlligence，2002，24(5):603-619.

［9］趙亮亮.雙目立體視覺中的圖像匹配技術(shù)研究［D］.南京:南京航空航天大學(xué)，2007.

［10］FUA P.A parallel stereo algorithm that produces dense depth maps and preserves image features［J］.Machine Vision and Applications，1993，6(1):35-49.

［11］TAO H，SAWHNEY H S，KUMAR R.A global matching framework for stereo computation［C］//Proc.the 8th International Conference on Computer Vision.Vancouver，Canada:［s.n.］，2001:532-539.

［12］BLEYER M，GELANTZ M.Graph-cut-based stereo matching using image segmentation with symmetrical treatment of occlusions［J］.Signal Proceedings:Image Communication，Special Issue on Three-Dimensional Video and Television，2007，22(2):127-149.

［13］鄧宇，李華.多特征組合和圖切割支持的物體/背景分割方法［J］.計算機研究與發(fā)展，2008，45(10):1724-1730.