用于單視加深度視頻編碼的快速立體匹配算法

趙 巖，劉 靜，陳賀新，劉伯軒

（吉林大學(xué)通信工程學(xué)院，長(zhǎng)春130012）

近些年來(lái)，立體視頻的應(yīng)用已融入我們的日常生活，如三維立體電視、機(jī)器人的視覺(jué)系統(tǒng)等［1］。與普通的單通道視頻相比，立體視頻要處理的數(shù)據(jù)量相當(dāng)大，因此解決立體視頻數(shù)據(jù)的壓縮傳輸問(wèn)題成為了當(dāng)今的研究熱點(diǎn)。單視加深度的立體視頻編碼方法，只編碼參考視點(diǎn)（如左視點(diǎn)）和左右視點(diǎn)的視差／深度圖，這樣可以大大減少傳輸?shù)臄?shù)據(jù)量，被廣泛認(rèn)為是很有前景的立體視頻編碼方法。立體匹配的任務(wù)是在左右圖像上使同名像點(diǎn)得到匹配，并通過(guò)計(jì)算位置偏差，從而生成視差圖［2］。當(dāng)前的一些算法已經(jīng)能獲得較好質(zhì)量的視差圖，但其算法大都過(guò)于復(fù)雜，效率較低［3－4］。

本文算法參考了文獻(xiàn)［4］基于分塊的置信傳播立體匹配的算法構(gòu)架，借鑒了近來(lái)比較熱點(diǎn)的基于分塊的方法［5－7］，并在此基礎(chǔ)上，針對(duì)算法效率不高的問(wèn)題，利用H.264對(duì)參考圖像編碼過(guò)程中產(chǎn)生的運(yùn)動(dòng)信息作為輔助信息，通過(guò)利用立體視頻前后兩幀之間的相關(guān)性，改變P幀立體匹配給每塊分配的視差片的初值，提高立體視頻P幀的匹配效率。

1 基于分塊的置信傳播立體匹配

算法的應(yīng)用基于假設(shè)視差的變化只發(fā)生在分塊區(qū)域的邊緣。分塊算法對(duì)不連續(xù)和大塊的無(wú)紋理區(qū)有很好的處理效果，而且可以較精確地定位深度邊界。具體算法按照以下4個(gè)步驟執(zhí)行。

1.1 幀參考圖像的分割

對(duì)參考圖像進(jìn)行分割，假設(shè)每個(gè)分割區(qū)域內(nèi)的視差變化平滑。算法采用均值平移（meanshift）高效圖像分割算法［8］。該算法能將圖像中每一個(gè)像素歸類到相應(yīng)的密度模式下。從而實(shí)現(xiàn)聚類并得到一系列互不交叉的區(qū)域，具有分割精度高的特點(diǎn)。

1.2 初始化匹配代價(jià)

算法采用基于窗口的局部匹配算法計(jì)算稀疏的初始視差圖。絕對(duì)亮度差（SAD）算法是計(jì)算各像素在不同視差時(shí)的匹配代價(jià)的常用算法［9］。算法采用SAD和基于梯度相結(jié)合的算法，定義如下：

式中：N（x，y）是（x，y）處的一個(gè)3×3窗口；Nx（x，y）代表除去最右列后的窗口；Ny（x，y）代表除去最下行后的窗口；▽x代表正向向右梯度；▽y代表正向向下梯度。

式中：C（x，y，d）即為點(diǎn)（x，y）的匹配代價(jià)；ω為最優(yōu)權(quán)重。

此處采用交叉校驗(yàn)，令（x＇，y＇）為參考圖中像素（x，y）基于初始視差d（x，y）在目標(biāo)圖中的對(duì)應(yīng)點(diǎn)，令d（x＇，y＇）為目標(biāo)圖像像素點(diǎn)（x＇，y＇）的初始視差，如果d（x，y）＝d（x＇，y＇），則?。▁，y）為可靠點(diǎn)。令兩幅視差圖中可靠對(duì)應(yīng)點(diǎn)最多的ω即為CSAD（x，y，d）和CGRAD（x，y，d）之間的最優(yōu)權(quán)重。

1.3 視差片估計(jì)

該步的目的是給每個(gè)參考圖像中的分割塊在視差圖中匹配一個(gè)視差片。算法利用一系列二維視差片來(lái)表征圖像結(jié)構(gòu)，每個(gè)視差片有3個(gè)參數(shù)c1、c2、c3，確定了參考圖像每個(gè)像素（x，y）的視差d＝c1x＋c2y＋c3。

此步驟通過(guò)下面兩個(gè)步實(shí)現(xiàn)。

平面擬合：由于離群點(diǎn)（outlier）的存在將影響視差片估計(jì)，該步的主要目的就是估計(jì)離群點(diǎn)的視差。首先對(duì)每塊中所有位于同一水平線上的可靠視差點(diǎn)求導(dǎo)，將所求的導(dǎo)數(shù)δd／δx插入到一個(gè)表中并排列，應(yīng)用高斯內(nèi)核卷積得到一個(gè)最佳水平斜率c1。針對(duì)豎直方向重復(fù)上述方法可得豎直斜率c2，繼而便可以得到c3。確定了視差片參數(shù)即可估計(jì)塊中各點(diǎn)的視差值。

視差片細(xì)化：該步把那些經(jīng)計(jì)算具有相同視差值的相鄰區(qū)域組合，并對(duì)其進(jìn)行重復(fù)的平面擬合以確定更加精確的視差片。把每塊的所有像素的匹配代價(jià)求和得到相應(yīng)視差片的匹配代價(jià)：

式中：S代表所分塊；P代表相應(yīng)的視差定義為d的視差片。

分別把上步擬合中求得的各像素的視差變化范圍（dmin，dmax）中的視差代入式（4）中，得到具有最小匹配代價(jià)的視差片分配給相應(yīng)的塊。然后把具有相同視差片的相鄰區(qū)域組合。最后對(duì)所有重組視差片進(jìn)行重復(fù)平面擬合使其更加精確。

1.4 用優(yōu)化算法求精確視差

這步的目的是使每一個(gè)分割擬合后的塊找到最優(yōu)對(duì)應(yīng)的視差片。令R為參考圖像分割擬合后的塊空間，D為視差片的估計(jì)值空間，f是分配給每塊s的視差片f（s）∈D，匹配的目的就是找到標(biāo)記f，使得每一個(gè)像元集s∈R都能得到相應(yīng)的標(biāo)記f（s）∈D，應(yīng)與觀察數(shù)據(jù)相吻合。這個(gè)問(wèn)題可以看作為分割擬合后的塊的一個(gè)能量最小化問(wèn)題［10］來(lái)求解，置信傳播實(shí)現(xiàn)能量最小化時(shí)，消息傳遞發(fā)生在相鄰塊之間：

2 算法實(shí)現(xiàn)

把參考幀編碼過(guò)程中產(chǎn)生的運(yùn)動(dòng)矢量信息作為輔助信息，用于下一幀的立體匹配過(guò)程中，以提高立體匹配的效率。設(shè)參考幀編碼產(chǎn)生的運(yùn)動(dòng)信息水平分量矩陣為Vx，豎直分量矩陣為Vy。

2.1 單視編碼中的運(yùn)動(dòng)信息

本文算法基于H.264平臺(tái)，在H.264中，運(yùn)動(dòng)估計(jì)是視頻編碼最關(guān)鍵的技術(shù)之一，能有效去除視頻時(shí)間冗余［11］。在運(yùn)動(dòng)估計(jì)的各種方法（梯度方法、像素遞歸方法、塊匹配運(yùn)動(dòng)估計(jì)方法等）中，塊匹配運(yùn)動(dòng)估計(jì)算法簡(jiǎn)單有效且易于硬件實(shí)現(xiàn)，被當(dāng)今視頻編碼標(biāo)準(zhǔn)廣泛采用。本算法采用的H.264平臺(tái)亦采用此運(yùn)動(dòng)估計(jì)法，其基本原理是：在給定搜索窗口內(nèi)，在參考幀中，搜索當(dāng)前塊的最優(yōu)匹配塊，以尋找其最優(yōu)運(yùn)動(dòng)信息Vx、Vy。

2.2 基于運(yùn)動(dòng)信息的快速立體匹配

在對(duì)I幀立體匹配的過(guò)程中，視差片估計(jì)會(huì)得到一個(gè)視差片的估計(jì)值CSEG（SI，PI），并把該圖像矩陣的坐標(biāo)與視頻編碼中I幀到P幀的最優(yōu)矢量Vx、Vy相加，尋找到運(yùn)動(dòng)點(diǎn)在P幀中的位置，以I幀中相對(duì)應(yīng)點(diǎn)的視差估計(jì)值作為P幀的視差估計(jì)值，重新組合成新的視差片。

最后把CSEG（SP，PP）代入式（5），得到

重復(fù)立體匹配的第四步用全局的置信傳播算法迭代求得E（f）min，以得到最優(yōu)視差。

3 實(shí)驗(yàn)結(jié)果及分析

實(shí)驗(yàn)選擇Breakdancer立體視頻測(cè)試序列的2、3視點(diǎn)和Book-sale立體視頻測(cè)試序列對(duì)的前三幀作為測(cè)試圖像。通過(guò)記錄改進(jìn)前后的每一幀視差圖生成需要的時(shí)間來(lái)比較算法效率，如圖1、圖2所示。并利用兩種算法生成的視差圖與參考圖像生成右視圖，通過(guò)測(cè)試視差圖繪制右視圖的峰值信噪比PSNR來(lái)評(píng)價(jià)算法質(zhì)量，如表1所示。本文實(shí)驗(yàn)序列的各幀圖像均為320×240（寬×高）像素。

圖1 Breakdancer序列兩種算法生成前三幀視差圖所需時(shí)間Fig.1 Time of generating disparity map in two algorithms for Breakdancer

圖2 Book-sale序列兩種算法生成前三幀視差圖所需時(shí)間Fig.2 Time of generating disparity map in two algorithms for Book-sale

表1 兩種算法得到的PSNR值Table 1 Values of PSNR obtained by two algorithms

由圖1、圖2可得，本文算法在生成P幀的視差圖時(shí)可節(jié)省大約50%的時(shí)間，效率大大提高。表1對(duì)兩種算法在重構(gòu)右視圖的PSNR進(jìn)行了比較，可以看出，本文算法重構(gòu)的右視圖的PSNR值大都有所提高，雖然Book-sale第二幀的PSNR值有所下降，但其下降幅度也較小，由圖3、圖4實(shí)驗(yàn)結(jié)果主觀圖也可以看出，由本文算法生成的視差圖在重構(gòu)右視圖的視覺(jué)效果上并沒(méi)有下降。這個(gè)實(shí)驗(yàn)結(jié)果表明，本文算法可以在保證質(zhì)量的前提下提高算法效率。

圖3 Breakdancer序列的實(shí)驗(yàn)結(jié)果圖Fig.3 Experimental results of Breakdancer

圖4 Book-sale序列的實(shí)驗(yàn)結(jié)果圖Fig.4 Experimental results of Book-sale

4 結(jié)束語(yǔ)

本文利用立體視頻相鄰幀之間的相關(guān)性，將單視編碼產(chǎn)生的運(yùn)動(dòng)信息應(yīng)用到深度圖生成的立體匹配過(guò)程中，使立體視頻傳輸中立體匹配的算法效率大大提高，該算法充分利用到了視頻編碼中產(chǎn)生的有用信息，避免了重復(fù)分塊、重復(fù)擬合，從而改善了單視加深度視頻編碼中立體匹配耗時(shí)過(guò)多的問(wèn)題。

［1］Schafer R.Review and future directions for 3D-video［C］∥Proceedings of the Picture Coding.Beijing，China，2006：1-11.

［2］耿英楠，趙巖，陳賀新.基于運(yùn)動(dòng)估計(jì)的置信度傳播立體視頻匹配算法［J］.吉林大學(xué)學(xué)報(bào)：信息科學(xué)版，2010，28（4）：330-333.

Geng Ying-nan，Zhao Yan，Chen He-xin.Stereo video matching algorithm of belief propagation based on motion estimation［J］.Journal of Jilin University（Information Science Edition），2010，28（4）：330-333.

［3］Larsen E S，Mordohai P，Pollefeys M，et al.Temporally consistent reconstruction from multiple video streams using enhanced belief propagation［C］∥IEEE Int Conf on Computer Vision（ICCV）-2007，Rio de Janeiro，Brasil，2007.

［4］Shawn Lankton.3D vison with stereo disparity［EB／OL］.［2010-11］.http：／／www.shawnlankton. com／.

［5］Bleyer M，Gelautz M.A layered stereo matching algorithm using image segmentation and global visibility constraints［J］.ISPRS Journal of Photogrammetry and Remote Sensing，2005，59（3）：128-150.

［6］Lee S，Oh K，Ho Y.Segment-based multi-view depth map estimation using belief propagation from dense multi-view video［C］∥IEEE 3D-TV Conf，Istanbul，Turkey，2008.

［7］葛亮，朱慶生，傅思思，等.改進(jìn)的立體像對(duì)稠密匹配算法［J］.吉林大學(xué)學(xué)報(bào)：工學(xué)版，2010，40（1）：212-217.

Ge Liang，Zhu Qing-sheng，F(xiàn)u Si-si，et al.Improved image dense stereo matching algorithm［J］.Journal of Jilin University（Engineering and Technology Edition），2010，40（1）：212-217.

［8］Comaniciu D，Meer P.Mean shift：a robust approach toward feature space analysis［J］.PAMI，2002，24（5）：603-619.

［9］殷虎，王敬東，李鵬.一種基于彩色圖像分割的立體匹配算法［J］.紅外技術(shù)，2009，31（12）：702-707.

Yin Hu，Wang Jing-dong，Li Peng.A stereo matching algorithm based on color image egmentation［J］.Infrared Technology，2009，31（12）：702-707.

［10］周秀芝，王潤(rùn)生.基于像元集的置信傳遞立體匹配［J］.中國(guó)圖像圖形學(xué)報(bào)，2008，13（3）：506-512.

Zhou Xiu-zhi，Wang Run-sheng.Pixel-set based stereo matching by using belief propagation［J］. Journal of Image and Graphics，2008，13（3）：506-512.

［11］張春田，蘇育挺，張靜.數(shù)字圖像壓縮編碼［M］.北京：清華大學(xué)出版社，2006.