基于視差和幀差的圖割優(yōu)化運(yùn)動(dòng)目標(biāo)分割算法

朱秋煜，李琦銘，陳岳川

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

近年來(lái)，運(yùn)動(dòng)目標(biāo)的分割得到了廣泛的研究，目標(biāo)分割是運(yùn)動(dòng)人體信息采集的基礎(chǔ)。目前所提出的檢測(cè)運(yùn)動(dòng)目標(biāo)的算法按照其原理主要可分為光流計(jì)算法、幀差分法和背景差分法。

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

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

1 區(qū)域視差匹配

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

1.1 圖像初始分割

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

1.2 初始視差估計(jì)

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

1.3 模板視差計(jì)算

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

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

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

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

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

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

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

平滑項(xiàng)為當(dāng)?shù)趇塊區(qū)域與第j塊區(qū)域?yàn)橄噜弲^(qū)域時(shí)的邊界長(zhǎng)度

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

2 三幀差分法

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

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

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

3 基于圖割理論的目標(biāo)分割算法

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

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

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

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

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

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

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

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

3.2 目標(biāo)分割

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

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

4 實(shí)驗(yàn)結(jié)果

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

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

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

圖2 幀差結(jié)果圖

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

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

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

5 小結(jié)

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

圖4 實(shí)驗(yàn)組2的分割結(jié)果

圖5 實(shí)驗(yàn)組3的分割結(jié)果

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

［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］趙亮亮.雙目立體視覺(jué)中的圖像匹配技術(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］.計(jì)算機(jī)研究與發(fā)展，2008，45(10):1724-1730.