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

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

（1.成都理工大學，四川 成都 610059；2.四川省應急測繪與防災減災工程技術研究中心，四川 成都 610041）

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

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

（1.成都理工大學，四川 成都 610059；2.四川省應急測繪與防災減災工程技術研究中心，四川 成都 610041）

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

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

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

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

1 HBP算法基本原理

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

HBP算法的理論基礎是馬爾科夫隨機場，其數學定義如下：假設隨機場X是定義在鄰域系統N上的馬爾科夫隨機場，并滿足以下2個條件：

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

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

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

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

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

圖1 金字塔模型

經過變換有：

令：

則消息函數可以改寫為：

將標簽量化，然后將量化后的每一級標簽對應到相應的標記網格中。式（8）可以看作是k個傾斜45°的三角錐，在網格中的每一個Xi都能對應一個在（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）

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

圖2 二分圖

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

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

2 算法仿真實驗

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

2.1 精度評定

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

均方根誤差：

誤匹配率：

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

表1 3組圖片的4種參數的參考值

2.2 實驗結果分析

分別以數據項權重系數為例，固定其他3個變量預設參數值，得到關于數據項權重系數變化情況下的均方根誤差變化趨勢圖（圖3）。

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

圖3 權重系數λ均方根誤差變化趨勢圖

表2 實驗結果

3 結 語

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

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

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

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

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

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

[6] 李旭超,朱善安.圖像分割中的馬爾可夫隨機場方法綜述[J].中國圖像圖形學報,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] 萬成凱.無標記人體運動捕捉及姿態估計的研究[D].北京：北京交通大學,2009

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

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

P237

B

1672-4623（2016）08-0020-03

10.3969/j.issn.1672-4623.2016.08.007

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

2015-12-01。

項目來源：國家級大學生創新創業訓練計劃資助項目（201410616005）；四川省應急測繪與防災減災工程技術研究中心開放基金資助項目（K2014B001）；四川省教育廳科研資助項目（15ZA0060）。