HBP立體匹配算法性能分析與仿真實(shí)驗(yàn)

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

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

HBP立體匹配算法性能分析與仿真實(shí)驗(yàn)

王 鵬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)化算法改進(jìn)后的高性能算法。介紹了HBP算法的原理及相關(guān)理論模型，分析了HBP算法的參數(shù)多且設(shè)置困難、實(shí)用性不高等問題。運(yùn)用窮舉最佳組合的方式求取了3組圖像的最佳組合參數(shù)，發(fā)現(xiàn)不同數(shù)據(jù)的最佳組合參數(shù)不一致，并對參數(shù)設(shè)置規(guī)律進(jìn)行了分析總結(jié)。

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

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

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

1 HBP算法基本原理

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

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

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

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

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

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

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

圖1 金字塔模型

經(jīng)過變換有：

令：

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

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

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é)點(diǎn)，此時(shí)的網(wǎng)格圖就是二分圖，如圖2所示（圖中黑色方格為A，白色方格為B，這樣二分圖可以表示為A∪B）。用表示在第t次迭代時(shí)，節(jié)點(diǎn)i向節(jié)點(diǎn)j傳遞的消息。當(dāng)t為奇數(shù)，只對A節(jié)點(diǎn)中的消息進(jìn)行更新而不改變B節(jié)點(diǎn)中的消息。當(dāng)t為偶數(shù)恰好相反，保持A節(jié)點(diǎn)中的消息而更新B節(jié)點(diǎn)中的消息。

圖2 二分圖

T次迭代以后可以計(jì)算每一個(gè)節(jié)點(diǎn)的置信度向量。

然后通過計(jì)算置信度最小時(shí)對應(yīng)的標(biāo)簽值，得到該節(jié)點(diǎn)的最佳視差值：

2 算法仿真實(shí)驗(yàn)

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

2.1 精度評(píng)定

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

均方根誤差：

誤匹配率：

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

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

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

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

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

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

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

3 結(jié) 語

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

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

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

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

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

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

[6] 李旭超,朱善安.圖像分割中的馬爾可夫隨機(jī)場方法綜述[J].中國圖像圖形學(xué)報(bào),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] 萬成凱.無標(biāo)記人體運(yùn)動(dòng)捕捉及姿態(tài)估計(jì)的研究[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

王鵬，碩士研究生，研究方向?yàn)閿z影測量與計(jì)機(jī)視覺。

2015-12-01。

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