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

（吉林大學通信工程學院，長春130012）

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

本文算法參考了文獻［4］基于分塊的置信傳播立體匹配的算法構架，借鑒了近來比較熱點的基于分塊的方法［5－7］，并在此基礎上，針對算法效率不高的問題，利用H.264對參考圖像編碼過程中產生的運動信息作為輔助信息，通過利用立體視頻前后兩幀之間的相關性，改變P幀立體匹配給每塊分配的視差片的初值，提高立體視頻P幀的匹配效率。

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

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

1.1 幀參考圖像的分割

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

1.2 初始化匹配代價

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

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

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

此處采用交叉校驗，令（x＇，y＇）為參考圖中像素（x，y）基于初始視差d（x，y）在目標圖中的對應點，令d（x＇，y＇）為目標圖像像素點（x＇，y＇）的初始視差，如果d（x，y）＝d（x＇，y＇），則取（x，y）為可靠點。令兩幅視差圖中可靠對應點最多的ω即為CSAD（x，y，d）和CGRAD（x，y，d）之間的最優(yōu)權重。

1.3 視差片估計

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

此步驟通過下面兩個步實現(xiàn)。

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

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

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

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

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

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

2 算法實現(xiàn)

把參考幀編碼過程中產生的運動矢量信息作為輔助信息，用于下一幀的立體匹配過程中，以提高立體匹配的效率。設參考幀編碼產生的運動信息水平分量矩陣為Vx，豎直分量矩陣為Vy。

2.1 單視編碼中的運動信息

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

2.2 基于運動信息的快速立體匹配

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

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

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

3 實驗結果及分析

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

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

圖2 Book-sale序列兩種算法生成前三幀視差圖所需時間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幀的視差圖時可節(jié)省大約50%的時間，效率大大提高。表1對兩種算法在重構右視圖的PSNR進行了比較，可以看出，本文算法重構的右視圖的PSNR值大都有所提高，雖然Book-sale第二幀的PSNR值有所下降，但其下降幅度也較小，由圖3、圖4實驗結果主觀圖也可以看出，由本文算法生成的視差圖在重構右視圖的視覺效果上并沒有下降。這個實驗結果表明，本文算法可以在保證質量的前提下提高算法效率。

圖3 Breakdancer序列的實驗結果圖Fig.3 Experimental results of Breakdancer

圖4 Book-sale序列的實驗結果圖Fig.4 Experimental results of Book-sale

4 結束語

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

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

［2］耿英楠，趙巖，陳賀新.基于運動估計的置信度傳播立體視頻匹配算法［J］.吉林大學學報：信息科學版，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］.吉林大學學報：工學版，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］.紅外技術，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］周秀芝，王潤生.基于像元集的置信傳遞立體匹配［J］.中國圖像圖形學報，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］.北京：清華大學出版社，2006.