張忠民，劉金鑫，席志紅

哈爾濱工程大學(xué) 信息與通信工程學(xué)院，哈爾濱150001

近年來(lái)，隨著計(jì)算機(jī)視覺與機(jī)器視覺領(lǐng)域的迅速發(fā)展，立體匹配算法作為其重要組成部分也在被眾多學(xué)者不斷優(yōu)化更新。立體匹配算法的目的是尋找同一場(chǎng)景下兩幅或者多幅圖片中的對(duì)應(yīng)點(diǎn)，從而進(jìn)行深度信息估計(jì)，此算法廣泛應(yīng)用于三維重建、目標(biāo)跟蹤以及VR等領(lǐng)域。2002年，Scharstein和Szeliski[1]提出了一種適用于立體視覺領(lǐng)域的分類方法，將立體匹配過程總結(jié)為以下四個(gè)步驟：（1）匹配代價(jià)計(jì)算；（2）代價(jià)聚合；（3）視差計(jì)算；（4）視差精化。全局立體匹配算法需要進(jìn)行（1）、（3）、（4）三個(gè)步驟，跳過了代價(jià)聚合階段，通過最小化能量函數(shù)來(lái)選擇最佳視差值，這種方法常?？梢缘玫骄植烤_的視差圖，但是計(jì)算的復(fù)雜度也更高，消耗時(shí)間更長(zhǎng)。常見的全局立體匹配算法有圖割法（GC）[2]、置信傳播（BP）[3]、最小生成樹法（MST）[4]、分割樹法（ST）[5]。局部立體匹配算法需要進(jìn)行全部四個(gè)步驟，結(jié)構(gòu)簡(jiǎn)單，但結(jié)果準(zhǔn)確率較低。局部立體匹配算法是現(xiàn)如今學(xué)者們的研究熱點(diǎn)與重點(diǎn)。

現(xiàn)如今，很多學(xué)者通過優(yōu)化匹配代價(jià)來(lái)提高視差精度，包括灰度差絕對(duì)值和（SAD）與灰度差平方和（SSD）[6]，這兩種方法對(duì)光照與噪聲比較敏感，以及基于梯度的度量（GBM）[7]，魯棒性較高的是Census變換[8]匹配算法。周旺尉等[9]在傳統(tǒng)Census變換匹配算法的基礎(chǔ)上引入了自適應(yīng)權(quán)重，此算法有效改善了匹配效果但實(shí)時(shí)性不盡如人意。王云峰等[10]提出了一種自適應(yīng)權(quán)重AD-Census算法，此算法雖準(zhǔn)確率較高，但運(yùn)行時(shí)間過長(zhǎng)，在實(shí)際應(yīng)用中受到一定限制。郭鑫等[11]提出了將傳統(tǒng)的Census變換、互信息、梯度信息這三種測(cè)度融合作為匹配代價(jià)，有效地提高了視差精度。在聚合窗口的選擇方面同樣涌現(xiàn)了大批算法，Yoon等[12]提出了自適應(yīng)權(quán)重的立體匹配算法，根據(jù)鄰域像素和中心像素的顏色和幾何相似性調(diào)整權(quán)重。2013年，Hosni等[13]將引導(dǎo)濾波應(yīng)用在窗口聚合上，引導(dǎo)濾波算法[14]能夠提高物體邊緣特征的匹配準(zhǔn)確率。張華等[15]提出跨尺度變窗口代價(jià)聚合匹配方法，采取互尺度正則化方法跨尺度聚合匹配代價(jià)。同樣的，也有學(xué)者在視差精化方面做文章，傳統(tǒng)的視差精化方法有左右一致性檢測(cè)（LRC）、中值濾波等等。Vieira等[16]提出了一種分割一致性檢驗(yàn)的視差精化算法，將圖像分割成塊，采用統(tǒng)計(jì)分析方式選取每個(gè)分割塊中可信值與不可信值，然后進(jìn)行視差填充，該方法可以有效地細(xì)化視差，提高精度。

本文基于文獻(xiàn)[16]中提出的分割一致性檢驗(yàn)算法，提出了基于熵率超像素分割的分割一致性檢驗(yàn)算法。本文算法將傳統(tǒng)分割一致性檢驗(yàn)算法中的均值漂移分割算法改進(jìn)為熵率超像素分割算法，熵率超像素分割算法可以將圖片分割成緊湊，具有區(qū)域一致性的區(qū)域，可以有效降低分割錯(cuò)誤率及提高分割后區(qū)域整體性進(jìn)而提高后續(xù)匹配精度。本文算法在保持原算法在復(fù)雜紋理區(qū)域細(xì)化精度的基礎(chǔ)上，優(yōu)化了其在低紋理區(qū)域的細(xì)化精度。

1 算法描述

本文算法基于傳統(tǒng)分割一致性檢驗(yàn)方法進(jìn)行有效改進(jìn)。首先利用基于熵率的超像素分割算法將參考圖像進(jìn)行分割，然后將分割塊按統(tǒng)計(jì)分析閾值分成可信值與不可信值，保留可信值剔除不可信值，最后通過顏色與空間的約束信息進(jìn)行視差填充，最終獲得精確的視差圖，具體算法流程圖如圖1所示。

1.1 熵率超像素分割算法

Liu等[17]經(jīng)過對(duì)超像素分割問題的研究，提出了基于熵率的超像素分割算法（Entropy Rate Super-pixel Segmentation Algorithm）。此算法采用一個(gè)帶權(quán)的無(wú)向圖代替源圖像，將源圖像中每個(gè)像素當(dāng)作無(wú)向圖的一個(gè)結(jié)點(diǎn)，利用兩個(gè)結(jié)點(diǎn)的相似性作為結(jié)點(diǎn)之間的權(quán)重，采用了一種圖上隨機(jī)游走的熵率和平衡項(xiàng)相結(jié)合的目標(biāo)函數(shù)，通過迭代最大化該目標(biāo)函數(shù)獲得分割結(jié)果。通過熵率分割可以獲得更均勻緊湊的區(qū)域，使得分割后的區(qū)域符合人眼感知，且分割后得到的各個(gè)區(qū)域具有較高的相似度。

圖1 算法流程圖

無(wú)向圖G=(V,E)，其中V代表圖的頂點(diǎn)集，E代表邊集，這樣就把圖像的分割問題轉(zhuǎn)化為圖的劃分問題。即將V劃分為一系列不相交的集合，其中任意兩個(gè)子集的交集為空集，所有子集的并集為V。選取E的子集A，得到無(wú)向圖G′=(V,A)。故學(xué)者們提出了一種新型聚類目標(biāo)函數(shù)，公式如下：

其中，H′(A)為圖上隨機(jī)游動(dòng)的熵率，B(A)表示平衡項(xiàng)，A為邊集，λ為平衡系數(shù)，此平衡系數(shù)為非負(fù)值。

1.1.1 熵率

其中，A為邊集，i和j表示圖的頂點(diǎn)，ei,j表示連接頂點(diǎn)的邊。所以，圖G′=(V,A)上隨機(jī)游動(dòng)的熵率可以用如下公式表示：

其中，μ為隨機(jī)過程的平穩(wěn)分布|V|表示圖的頂點(diǎn)個(gè)數(shù)。

1.1.2 平衡函數(shù)

平衡函數(shù)即平衡項(xiàng)為一個(gè)判決準(zhǔn)則，若邊集A的分割結(jié)果為集群成員的分布可用如下公式表示：

其中，NA表示劃分后的子集個(gè)數(shù)，ZA表示集群成員的分布，pZA(i)為第i個(gè)子集頂點(diǎn)數(shù)所占比例，i=1,2,…,NA，||Si表示第i個(gè)子集的頂點(diǎn)個(gè)數(shù)。

平衡函數(shù)定義由如下公式表示：

熵H(ZA)使得生產(chǎn)的集群具有相似的大小，NA使得聚類的數(shù)目盡可能少。對(duì)于給定的聚類數(shù)目，傾向于使平衡函數(shù)盡可能大的劃分方法，圖2可以解釋上述描述。

圖2 熵率對(duì)集群相似性作用描述

接著，學(xué)者使用算法分割圖像。學(xué)者們首先將圖G=(V,E)中每個(gè)頂點(diǎn)當(dāng)成單獨(dú)集群，將不同的標(biāo)志賦予每個(gè)集群，初始化A=?。使用前文已經(jīng)定義的目標(biāo)函數(shù)來(lái)計(jì)算E中各條邊的函數(shù)值，從這些函數(shù)值中選出最大值的邊加入A中，A中增加一條邊，E中就減少一條邊，同時(shí)進(jìn)行合并集群的操作。不斷重復(fù)此操作直到E為空。迭代完成后，可以得到K個(gè)集群，每個(gè)集群就是一個(gè)超像素?；陟芈实某袼胤指罘椒ㄖ校芈视欣谛纬山Y(jié)構(gòu)均勻、緊湊的集群，促進(jìn)獲得的超像素僅覆蓋圖像中的單一目標(biāo)對(duì)象，使得圖像分割為符合人眼感知的區(qū)域。平衡項(xiàng)促使各集群具有相似的尺寸，降低不平衡超像素個(gè)數(shù)。

1.2 統(tǒng)計(jì)分析算法

經(jīng)過第一步驟得到了參考圖像的分割圖，將參考圖像分割成了若干分割塊。接著，此方法通過統(tǒng)計(jì)分析為每一個(gè)分割塊計(jì)算出一個(gè)統(tǒng)計(jì)值，將此統(tǒng)計(jì)值作為集中趨勢(shì)值，公式如下：

根據(jù)計(jì)算出的集中趨勢(shì)值，將每一個(gè)分割塊中的每個(gè)視差點(diǎn)進(jìn)行求值，篩選可信值與不可信值，若求得的值在此范圍內(nèi)，則賦值為m并保留，反之若不在此范圍內(nèi)，則賦值為0，將其當(dāng)作未知視差點(diǎn)處理。公式如下：

對(duì)于視差圖D中分割塊表示為Si(Si∈D)。計(jì)算全部n個(gè)分割塊的集中趨勢(shì)值并表示為m。閾值t的值可以自定，設(shè)置此閾值的目的是接近分割塊中的集中趨勢(shì)值，并且每一個(gè)視差值D(x,y)都應(yīng)該在Si中。

1.3 自適應(yīng)加權(quán)窗口視差填充算法

由于上一步驟中存在被賦值為0當(dāng)作未知視差值的點(diǎn)，所以需要填充這些點(diǎn)來(lái)保證視差圖的完整精確性。Yoon和Kweon[18]提出了一種支持加權(quán)窗口算法來(lái)進(jìn)行立體匹配，他們的方法考慮了點(diǎn)與點(diǎn)之間的顏色相似性和點(diǎn)與點(diǎn)之間的空間距離關(guān)系。作者在論文中定義了一個(gè)窗口，并且定義窗口的中心點(diǎn)為主點(diǎn)。計(jì)算每個(gè)鄰近點(diǎn)與主點(diǎn)的顏色差異與空間幾何關(guān)系可以作為約束條件來(lái)進(jìn)行視差填充。主點(diǎn)p與鄰近點(diǎn)n的顏色鄰近約束公式如下：

其中，Δcpn表示圖像I中主點(diǎn)p與鄰近點(diǎn)n的顏色間的歐式距離。Δcpn可以由如下公式表示：

同樣的，空間鄰近約束公式為：

其中，Δspn表示圖像I主點(diǎn)p與鄰近點(diǎn)n的坐標(biāo)(x,y)間的歐式距離。Δspn可以由如下公式表示：

其中，γc與γs分別表示顏色相似性常數(shù)及用于調(diào)整空間距離項(xiàng)的常數(shù)。

將顏色與空間兩種約束相結(jié)合，就可以得到支持加權(quán)窗口的公式：

本文使用自適應(yīng)支持加權(quán)窗口算法處理未知視差，窗口內(nèi)的主點(diǎn)就是想要的視差點(diǎn)。權(quán)值是根據(jù)上述顏色相似度與幾何距離來(lái)調(diào)整的，即像素顏色越相近，所分配到的權(quán)值越大；像素幾何距離越近，所分配到的權(quán)值也就越大。通過此方法得到的權(quán)值是具有準(zhǔn)確性的。在相同視差點(diǎn)處的每個(gè)像素的權(quán)值都會(huì)累加。將窗口內(nèi)的每個(gè)點(diǎn)的權(quán)值設(shè)為w。如下公式表示了權(quán)值累加的過程：其中，dmin與dmax表示最小與最大的視差值，Ω表示累加值。

因此，如下公式可以代表視差優(yōu)化的過程，以此來(lái)求出最佳視差：

其中，(x,y)為視差圖D中各個(gè)位置視差處的坐標(biāo)，將計(jì)算出的最佳視差值Ω賦值給D，即可達(dá)到有效填充視差的作用。

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

本實(shí)驗(yàn)在Matlab R2016b平臺(tái)完成。為驗(yàn)證算法有效性，采用立體匹配領(lǐng)域公認(rèn)的Middlebury[1]數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)，其中包括Tsukuba、Venus、Teddy和Cones等15組標(biāo)準(zhǔn)測(cè)試圖。按照Middlebury統(tǒng)一評(píng)價(jià)標(biāo)準(zhǔn)，設(shè)置誤差參數(shù)閾值為1。實(shí)驗(yàn)中部分參數(shù)設(shè)置與文獻(xiàn)[16]中相同，15組立體圖像對(duì)的視差搜索范圍參數(shù)與縮放倍數(shù)參數(shù)如表1所示。

表1 視察搜索范圍與縮放倍數(shù)參數(shù)

2.1 算法綜合性能測(cè)試結(jié)果

2.1.1 統(tǒng)計(jì)分析方法適配性實(shí)驗(yàn)

本文使用眾數(shù)（Mode）作為集中趨勢(shì)值的求取方法。為驗(yàn)證本文統(tǒng)計(jì)分析方法的適配性，本文對(duì)比了另外兩種集中趨勢(shì)值的測(cè)量方法：均值法（Mean）、中值法（Median）。針對(duì)Tsukuba、Venus、Teddy和Cones四組標(biāo)準(zhǔn)測(cè)試圖分別用三種集中趨勢(shì)值測(cè)量方法得到最終的視差圖誤匹配率。對(duì)比數(shù)據(jù)如表2所示。

表2 統(tǒng)計(jì)分析方法適配性對(duì)比%

可以看出，本文使用的統(tǒng)計(jì)分析方法最終得到四組測(cè)試圖的視差圖誤匹配率均低于均值與中值兩種算法。實(shí)驗(yàn)結(jié)果表明，本文所使用的統(tǒng)計(jì)分析方法與分割塊較傳統(tǒng)均值中值兩種方法具有更好的適配性。

2.1.2 算法綜合性能對(duì)比實(shí)驗(yàn)

本實(shí)驗(yàn)分別使用立體匹配效果較好的文獻(xiàn)[13]算法及立體匹配效果較差的SAD算法[19]進(jìn)行1、2、3步，第4步視差精化則分別運(yùn)用傳統(tǒng)分割一致性檢驗(yàn)算法與本文算法，然后將四組誤匹配率結(jié)果進(jìn)行比較，最終得到量化對(duì)比結(jié)果。算法綜合性能測(cè)試結(jié)果如表3所示。

表3 算法量化對(duì)比結(jié)果 %

從表3可以看出，文獻(xiàn)[13]由于立體匹配效果較好，所以總體誤匹配率較低，SAD立體匹配算法匹配誤差較大導(dǎo)致總體誤匹配率較高。但是總體來(lái)說在經(jīng)過兩種視差細(xì)化方式后，誤匹配率均呈現(xiàn)明顯下降趨勢(shì)。對(duì)比上述數(shù)據(jù)，平均誤差匹配率最多提高了5.88個(gè)百分點(diǎn)。表3可以看出，在綜合性能上，本文算法要優(yōu)于傳統(tǒng)算法。其原因在于熵率超像素分割算法可以將參考圖像分割成緊湊的，具有區(qū)域一致性的若干區(qū)域，因此可以有效避免圖像中的信息缺失情況，這樣在細(xì)化后可以保持物體的形狀基本不變。在對(duì)這些區(qū)域進(jìn)行篩選時(shí)首先遍歷每個(gè)區(qū)域進(jìn)行視差求取，并與集中趨勢(shì)值進(jìn)行比較篩選。這樣可以保證每個(gè)區(qū)域信息的均勻性，進(jìn)而保持均勻區(qū)域視差的規(guī)律性，這樣進(jìn)行有效視差填充后視差細(xì)化效果會(huì)優(yōu)于傳統(tǒng)算法。

2.2 低紋理圖片算法對(duì)比結(jié)果

選取文獻(xiàn)[13]中的立體匹配算法分別進(jìn)行兩種視差細(xì)化算法，然后分別對(duì)于初始視差圖及兩種視差細(xì)化后得到的視差圖進(jìn)行誤匹配率檢測(cè)，圖片選擇Venus、Baby1、Rock1、Wood1四組低紋理圖片，測(cè)試結(jié)果如表4所示。

表4 可以看出傳統(tǒng)算法與改進(jìn)算法在低紋理圖片中的細(xì)化精度對(duì)比。例如，Venus圖中紋理信息較少，使用傳統(tǒng)算法得到的細(xì)化精度為2.30%，但是本文改進(jìn)算法得到的細(xì)化精度為0.57%，較傳統(tǒng)算法精度提升了

表4 低紋理圖片測(cè)試結(jié)果對(duì)比 %

1.73個(gè)百分點(diǎn)，其余三張低紋理圖片細(xì)化精度均有不同程度提高，最多提升14.01個(gè)百分點(diǎn)。圖3為算法對(duì)比圖。

圖3 算法對(duì)比圖

在分別對(duì)初始視差圖使用傳統(tǒng)算法與本文算法進(jìn)行視差精化后。首先求出初始視差圖的誤匹配率及其誤匹配標(biāo)記圖，然后分別求出通過兩種精化算法后的誤匹配率及誤匹配標(biāo)記圖。對(duì)比圖3中各組圖片，可以得到以下結(jié)論：（1）對(duì)比圖3（d）與（f）兩組圖片，可以看出對(duì)于低紋理圖片傳統(tǒng)算法會(huì)出現(xiàn)負(fù)優(yōu)化的情況。這說明傳統(tǒng)算法對(duì)低紋理圖片的精化處理是存在局限性的。（2）對(duì)比圖3（b）、（e）、（g）三組視差圖中的Baby1圖，從圖中紅圈部分可以看出傳統(tǒng)算法視差圖中視差信息存在缺失的情況。（3）對(duì)比圖3（f）與（h）兩組誤匹配標(biāo)記圖，紅色誤匹配部分本文算法明顯少于傳統(tǒng)算法；對(duì)比Venus圖中藍(lán)圈部分可以看出在紋理信息較少的位置，本文算法優(yōu)化效果優(yōu)于傳統(tǒng)算法。針對(duì)以上三點(diǎn)結(jié)論，結(jié)合本文算法與傳統(tǒng)算法的機(jī)制，可以看出：（1）傳統(tǒng)算法運(yùn)用的均值漂移分割方法雖然可以有效保持視差圖邊緣特征，但是由于窗口選擇及迭代過程造成了信息的缺失。然而，熵率超像素分割算法則會(huì)將圖像均勻分割，可以有效避免這一情況。（2）圖像紋理信息越少，傳統(tǒng)算法的局限性就越明顯，相反本文算法得到的分割塊與后續(xù)統(tǒng)計(jì)分析方法的適配性更高，在低紋理區(qū)域更容易發(fā)揮算法精度優(yōu)勢(shì)，同樣在復(fù)雜紋理區(qū)域也不輸于傳統(tǒng)算法。對(duì)比圖3（g）本文算法求得的最終視差圖的效果，可以看出在邊緣處還存在散點(diǎn)較多的現(xiàn)象，由于熵率超像素分割算法會(huì)將參考圖像分割成若干塊，相鄰邊緣信息部分很可能存在于不同塊中，一旦有些邊緣信息被置零處理，就會(huì)出現(xiàn)邊緣信息散點(diǎn)情況。因此導(dǎo)致匹配效果不是很好，可見本文算法在邊緣處的魯棒性還有待提高。未來(lái)可以深入研究的方法可能有以下三種：（1）首先將初始視差圖進(jìn)行邊緣檢測(cè)，將邊緣信息單獨(dú)提取出來(lái)進(jìn)行細(xì)化處理，然后將這些邊緣信息加入到細(xì)化后的視差圖中，這樣可以避免信息缺失。（2）同樣先進(jìn)行邊緣檢測(cè)，細(xì)化處理時(shí)將邊緣信息閾值提高，分割時(shí)盡量保留邊緣信息，避免散點(diǎn)及誤分割情況出現(xiàn)。（3）未來(lái)可以研究對(duì)邊緣特征收斂性更高同時(shí)兼顧其他特征信息的分割方法。

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

本文提出了一種改進(jìn)熵率超像素分割的分割一致性檢驗(yàn)算法，使用基于熵率的超像素分割算法將參考圖像分割，然后按照統(tǒng)計(jì)分析的方法計(jì)算出集中趨勢(shì)值以區(qū)分保留值與剔除值，最后進(jìn)行視差填充，得到優(yōu)化后的視差圖。通過對(duì)15組立體圖像對(duì)進(jìn)行誤匹配率測(cè)試，驗(yàn)證本文算法的有效性及優(yōu)越性。本文算法改進(jìn)了傳統(tǒng)分割一致性檢驗(yàn)算法在處理低紋理圖片時(shí)可能出現(xiàn)的負(fù)優(yōu)化問題，并進(jìn)一步優(yōu)化了視差精化步驟的視差圖效果，但最終得到的視差圖仍然在邊緣處存在魯棒性不高的問題。究其原因主要在于超像素分割算法的局限性。未來(lái)可以將效果更好的分割算法應(yīng)用到分割一致性檢驗(yàn)算法中，在后續(xù)研究中可以針對(duì)此問題進(jìn)行深入研究。