王 鵬，朱 姝，胡古月，楊容浩,2

（1.成都理工大學(xué)，四川 成都 610059；2.四川省應(yīng)急測繪與防災(zāi)減災(zāi)工程技術(shù)研究中心，四川 成都 610041）

HBP立體匹配算法性能分析與仿真實驗

王 鵬1，朱 姝1，胡古月1，楊容浩1,2

（1.成都理工大學(xué)，四川 成都 610059；2.四川省應(yīng)急測繪與防災(zāi)減災(zāi)工程技術(shù)研究中心，四川 成都 610041）

多層次置信度傳播（HBP）立體匹配算法是傳統(tǒng)置信度傳播算法通過距離變換優(yōu)化、奇偶場優(yōu)化、金字塔優(yōu)化算法改進后的高性能算法。介紹了HBP算法的原理及相關(guān)理論模型，分析了HBP算法的參數(shù)多且設(shè)置困難、實用性不高等問題。運用窮舉最佳組合的方式求取了3組圖像的最佳組合參數(shù)，發(fā)現(xiàn)不同數(shù)據(jù)的最佳組合參數(shù)不一致，并對參數(shù)設(shè)置規(guī)律進行了分析總結(jié)。

立體匹配；置信度傳播；馬爾科夫隨機場；吉布斯分布

立體匹配不僅是計算機視覺領(lǐng)域中的研究熱點與難點，還是約束立體視覺發(fā)展的重要組成部分[1]。當真實場景中的物體被投影到二維平面上的時候，包含了真實場景的形狀、特征、亮度等多種信息，并通過像素灰度值來表示。但是由于投影過程中儀器自身的缺陷，如畸變、角度、光線的影響造成了圖像匹配錯誤，使立體匹配成為了一個典型的病態(tài)問題[2]。立體匹配難點有遮擋、光照變化、弱紋理和紋理區(qū)域的誤匹配等。

本世紀初，立體匹配的研究熱點已從局部優(yōu)化問題轉(zhuǎn)到全局最優(yōu)化問題，即構(gòu)建全局能量函數(shù)不僅需要局部最優(yōu)，還要對局部最優(yōu)問題進行全局約束，從而提高立體匹配的精度[3]。這樣全局優(yōu)化問題就轉(zhuǎn)到能量函數(shù)的構(gòu)建以及如何讓能量函數(shù)最小最優(yōu)的問題上來。基于馬爾科夫隨機場理論的HBP立體匹配算法是目前解決這一問題很有效的方案[4]。

1 HBP算法基本原理

立體匹配算法就是解決全局能量最小化的問題[5]，定義全局能量函數(shù)的公式為：式中，X表示圖像在像素點i處可能的視差值；N表示圖像中所有像素的四鄰域像素點集；Xi表示i點所分配的視差值；不連續(xù)代價V（Xi-Xj）表示兩相鄰像素點i和j分配視差Xi和Xj時視差不連續(xù)代價集合；數(shù)據(jù)項Di（Xi）表示像素點i在視差為Xi時的相似度。

HBP算法的理論基礎(chǔ)是馬爾科夫隨機場，其數(shù)學(xué)定義如下：假設(shè)隨機場X是定義在鄰域系統(tǒng)N上的馬爾科夫隨機場，并滿足以下2個條件：

條件二中的概率稱為馬爾科夫隨機場的局部特征，所有能滿足條件一的概率都通過條件二來進行唯一性約束[6]。在實際應(yīng)用中，要確定這2個條件概率是一件很困難的事情。20世紀80年代，Hammersley Clifford驗證了馬爾科夫隨機場與吉布斯分布的等價關(guān)系[7-9]，并使用吉布斯分布來求解馬爾科夫隨機場中的概率分布。吉布斯分布一般定義形式為：

式中，Z 表示歸一化參數(shù)；U（x）表示能量函數(shù)；T表示一個溫度常數(shù)。

HBP算法的2個關(guān)鍵是：①通過加權(quán)乘積計算所有的局部消息；②節(jié)點之間概率消息在隨機場中的傳遞[10]。首先將整個節(jié)點空間進行分層處理，這樣就可以使遠距離的像素間相互作用在粗圖像中通過短路徑獲取。令L0=L，L表示節(jié)點空間。Lk表示第k層的節(jié)點空間。在整個金字塔模型中，上一層的每個節(jié)點都可以向下映射到下一層的2×2個節(jié)點，因此，第k層的每一個節(jié)點就可以映射到L0上的ε×ε（ε=2k）個節(jié)點，如圖1所示。

將節(jié)點空間進行分層以后，就要在每一層的節(jié)點間進行消息的傳遞，因此，定義消息傳遞函數(shù)：

為了將立體匹配能量與置信度傳播聯(lián)系起來，定義以下變換：

圖1 金字塔模型

經(jīng)過變換有：

令：

則消息函數(shù)可以改寫為：

將標簽量化，然后將量化后的每一級標簽對應(yīng)到相應(yīng)的標記網(wǎng)格中。式（8）可以看作是k個傾斜45°的三角錐，在網(wǎng)格中的每一個Xi都能對應(yīng)一個在（Xi，h（Xi））上的三角錐[10]。然后通過向前向后算法進行距離變換，對更新的消息進行計算。向前向后處理算法為：

1）初始化：m（Xj）=h（Xj）

2）向前處理：for Xjfrom 1 to k-1

m（Xj）←min（m（Xj），m（Xj，m（Xj-1）+c）

3）向后處理：for Xjfrom k-2 to 0

m（Xj）←min（m（Xj），m（Xj,m（Xj+1）+c）

多層次置信度傳播立體匹配算法主要研究基于四鄰域系統(tǒng)的圖像模型，如果著色網(wǎng)格圖形為棋盤圖案，每邊連接不同顏色的節(jié)點，此時的網(wǎng)格圖就是二分圖，如圖2所示（圖中黑色方格為A，白色方格為B，這樣二分圖可以表示為A∪B）。用表示在第t次迭代時，節(jié)點i向節(jié)點j傳遞的消息。當t為奇數(shù)，只對A節(jié)點中的消息進行更新而不改變B節(jié)點中的消息。當t為偶數(shù)恰好相反，保持A節(jié)點中的消息而更新B節(jié)點中的消息。

圖2 二分圖

T次迭代以后可以計算每一個節(jié)點的置信度向量。

然后通過計算置信度最小時對應(yīng)的標簽值，得到該節(jié)點的最佳視差值：

2 算法仿真實驗

HBP算法的難點是需要設(shè)置的參數(shù)很多，而且沒有規(guī)律可循。此節(jié)分析了不同參數(shù)影響算法結(jié)果的變化趨勢。本次實驗測試的參數(shù)包括迭代次數(shù)T、數(shù)據(jù)項閥值K1、不連續(xù)代價閥值K2、數(shù)據(jù)項權(quán)重系數(shù)λ。每次實驗固定其中3個參數(shù)，變化1個參數(shù)，然后通過窮舉最優(yōu)組合的方法得到每一組圖像的最優(yōu)參數(shù)組合。

2.1 精度評定

本次實驗數(shù)據(jù)來自美國Middle學(xué)院的立體匹配公共測試平臺數(shù)據(jù)庫中名為Tsukuba、Vensus、Teddy的3幅圖片。對于立體匹配算法精度的評價標準有均方根誤差和誤匹配率。

均方根誤差：

誤匹配率：

兩式中，N表示圖像中的像素總數(shù)；dc表示計算得到的視差值；dT是標準視差值；δd表示允許誤差閥值，一般取值為1。實驗數(shù)據(jù)各參數(shù)參考值如表1。

表1 3組圖片的4種參數(shù)的參考值

2.2 實驗結(jié)果分析

分別以數(shù)據(jù)項權(quán)重系數(shù)為例，固定其他3個變量預(yù)設(shè)參數(shù)值，得到關(guān)于數(shù)據(jù)項權(quán)重系數(shù)變化情況下的均方根誤差變化趨勢圖（圖3）。

從圖3可以看出，3幅圖片的最佳權(quán)重系數(shù)分別為0.06、0.06、0.02。重復(fù)以上計算，可以得到單個參數(shù)最佳值表。然后以第一組為參考值進行第二輪參數(shù)設(shè)置，得到第二輪測試的最佳參數(shù)值。通過反復(fù)實驗，最終得到3組圖片最佳組合參數(shù)，見表2。

圖3 權(quán)重系數(shù)λ均方根誤差變化趨勢圖

表2 實驗結(jié)果

3 結(jié) 語

通過實驗分析了HBP算法中各項參數(shù)對精度的影響，得到的結(jié)論是：①算法基本在3～5次迭代后就能達到收斂值。②在數(shù)據(jù)項權(quán)重系數(shù)、數(shù)據(jù)項閥值、不連續(xù)代價閥值3個參數(shù)中，數(shù)據(jù)項權(quán)重系數(shù)的影響最大，參數(shù)的設(shè)置在很大程度上與原始圖像亮度相關(guān)，對于整體亮度較低或者局部亮度較低的圖像，數(shù)據(jù)項權(quán)重系數(shù)較小，反之較大。③數(shù)據(jù)項閥值、不連續(xù)代價閥值與亮度和場景復(fù)雜度有關(guān)，但影響因素要小于數(shù)據(jù)項權(quán)重系數(shù)。④HBP算法通過消息迭代更新進行視差優(yōu)化，對于場景中的錯誤信息同樣會進行傳播，特別是低紋理或者無紋理區(qū)域，這也是HBP算法的局限性。

[1] 游素亞.立體視覺研究的現(xiàn)狀與進展[J].中國圖像圖形學(xué)報,1997(1)：17-24

[2] 石春琴.隨機光照雙目立體測量系統(tǒng)中的若干關(guān)鍵問題研究[D].南京：南京航空航天大學(xué),2011

[3] 宋長波.基于線特征的立體視覺匹配研究[D].武漢：武漢大學(xué),2004

[4] 陳侃.基于馬爾科夫隨機場圖像恢復(fù)算法研究[D].南京：南京師范大學(xué),2008

[5] 趙笑可.基于全局能量最小化的立體匹配算法研究[D].南京：南京理工大學(xué),2008

[6] 李旭超,朱善安.圖像分割中的馬爾可夫隨機場方法綜述[J].中國圖像圖形學(xué)報,2007(5)：789-798

[7] Besag J.Spatial Interaction and the Statistical Analysis of Lattice Systems[J]. J.R.Statist.Soc.B,1974,36(2)：192-236

[8] 萬成凱.無標記人體運動捕捉及姿態(tài)估計的研究[D].北京：北京交通大學(xué),2009

[9] Moussouris J.Gibbs and Markov Random Systems with Constraints[J].Journal of Statistical Physics,1974,10(1)：11-33

[10] 饒旻驊.基于置信度傳播的立體匹配算法研究[D].武漢：華中科技大學(xué),2010

P237

B

1672-4623（2016）08-0020-03

10.3969/j.issn.1672-4623.2016.08.007

王鵬，碩士研究生，研究方向為攝影測量與計機視覺。

2015-12-01。

項目來源：國家級大學(xué)生創(chuàng)新創(chuàng)業(yè)訓(xùn)練計劃資助項目（201410616005）；四川省應(yīng)急測繪與防災(zāi)減災(zāi)工程技術(shù)研究中心開放基金資助項目（K2014B001）；四川省教育廳科研資助項目（15ZA0060）。