基于視差和幀差的圖割優化運動目標分割算法

朱秋煜，李琦銘，陳岳川

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

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

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

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

1 區域視差匹配

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

1.1 圖像初始分割

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

1.2 初始視差估計

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

1.3 模板視差計算

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

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

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

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

1.4 模板視差最優分配

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

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

平滑項為當第i塊區域與第j塊區域為相鄰區域時的邊界長度

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

2 三幀差分法

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

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

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

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

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

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

3.1 構造能量函數

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

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

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

式中，平滑項Edsmooth表示用于約束鄰接區域內像素的一致性程度。本文采用的是Sobel梯度算子來計算當前像素與鄰接區域內的其他像素的平滑程度，數據項表示對應像素匹配一致性程度

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

3.2 目標分割

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

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

4 實驗結果

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

圖1 視差計算及優化

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

圖2 幀差結果圖

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

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

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

5 小結

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

圖4 實驗組2的分割結果

圖5 實驗組3的分割結果

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

［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］黃洋文，王紅亮.基于量子粒子群優化算法的圖像分割方法［J］.電視技術，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］趙亮亮.雙目立體視覺中的圖像匹配技術研究［D］.南京:南京航空航天大學，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］.計算機研究與發展，2008，45(10):1724-1730.