熵率超像素分割一致性檢驗視差細化算法

張忠民，劉金鑫，席志紅

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

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

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

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

1 算法描述

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

1.1 熵率超像素分割算法

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

圖1 算法流程圖

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

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

1.1.1 熵率

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

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

1.1.2 平衡函數(shù)

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

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

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

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

圖2 熵率對集群相似性作用描述

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2 實驗結(jié)果與分析

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

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

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

2.1.1 統(tǒng)計分析方法適配性實驗

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

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

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

2.1.2 算法綜合性能對比實驗

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

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

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

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

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

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

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

1.73個百分點，其余三張低紋理圖片細化精度均有不同程度提高，最多提升14.01個百分點。圖3為算法對比圖。

圖3 算法對比圖

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

3 結(jié)束語

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