基于SAD的立體匹配算法研究

于春和，張 靜

(沈陽(yáng)航空航天大學(xué) 電子信息工程學(xué)院，沈陽(yáng) 110136)

立體匹配是二維圖像對(duì)三維場(chǎng)景結(jié)構(gòu)信息獲取的主要技術(shù)手段，一直是人們的研究熱點(diǎn)之一[1]。立體匹配作為計(jì)算機(jī)雙目立體視覺(jué)中最關(guān)鍵的一個(gè)步驟，其后面進(jìn)行的三維重建的精度與匹配結(jié)果準(zhǔn)確與否息息相關(guān)。所謂立體匹配就是從不同視點(diǎn)獲得的兩幅圖像中找到匹配的對(duì)應(yīng)點(diǎn)，再由匹配代價(jià)函數(shù)來(lái)估算匹配點(diǎn)的視差值。

20世紀(jì)80年代的研究人員提出層次處理立體匹配的概念，通過(guò)立體匹配約束條件來(lái)提高立體匹配的精確度。隨著科技的發(fā)展，雙目立體視覺(jué)技術(shù)漸漸走向成熟，不少研究人員把立體匹配技術(shù)與人們的實(shí)際應(yīng)用相結(jié)合，比如深度的計(jì)算，場(chǎng)景的三維重建，虛擬現(xiàn)實(shí)等。雙目立體匹配技術(shù)雖已經(jīng)過(guò)幾十年的研究且已經(jīng)取得了一定的研究成果，立體匹配的準(zhǔn)確率還是會(huì)受到圖像無(wú)紋理區(qū)、物體之間的相互遮擋、鏡頭畸變、光照變化及相機(jī)特性等各方面因素的影響，這些因素都被綜合到了圖像的灰度值中。因此，想要精準(zhǔn)地對(duì)存在這么多不利因素的圖像來(lái)進(jìn)行無(wú)歧義的匹配是一個(gè)困難的過(guò)程[2]。為了使立體匹配的有效性得到提高有三個(gè)問(wèn)題需要解決，即匹配特征的選擇要正確，找出特征間的匹配屬性并且建立能夠準(zhǔn)確的匹配所選特征的穩(wěn)定算法[3]。目前，圍繞以上所提到的三個(gè)方面展開(kāi)研究的匹配方法有許多種，最具代表性的有區(qū)域相關(guān)法[4]、動(dòng)態(tài)規(guī)劃法[5]、和基于圖論的最小切割方法[6]。但是還有好多立體匹配所涉及的問(wèn)題沒(méi)有得到妥善解決，尤其需要進(jìn)一步深入研究在復(fù)雜場(chǎng)景中如何去提高匹配算法的準(zhǔn)確率。

局部立體匹配算法以及全局立體匹配算法是現(xiàn)階段應(yīng)用最廣泛的兩類匹配算法[7]。在局部算法中，灰度差累積(Sum of absolute differences，SAD)算法是常用的匹配算法，該算法匹配速度快、計(jì)算效率高，得到的視差圖更適合密集型的三維重構(gòu)。

1 極線校正

極線校正實(shí)質(zhì)上就是圖像進(jìn)行匹配過(guò)程之前對(duì)圖像預(yù)處理的一部分。為進(jìn)一步提高匹配效率，在匹配時(shí)往往采用在同一極線上搜索兩幅圖中最相似點(diǎn)對(duì)的方法，在同一水平線上進(jìn)行匹配可以達(dá)到降低搜索范圍的目的。但從實(shí)際角度出發(fā)，無(wú)論如何擺放兩臺(tái)攝像機(jī)都不可能使光軸做到完全平行。為滿足上述情況就需要兩臺(tái)攝像機(jī)的成像平面必須共面且完全行對(duì)準(zhǔn)。校正后的圖片使立體匹配的結(jié)果更加精準(zhǔn)，所以要在立體匹配之前對(duì)雙目圖像進(jìn)行校正[8]。

極線校正過(guò)程如圖1所示，極線校正將雙目立體視覺(jué)的幾何結(jié)構(gòu)校正為平視雙目標(biāo)準(zhǔn)幾何結(jié)構(gòu)。該校正過(guò)程可分兩步完成。第一步，將左右兩個(gè)成像平面拉到同一平面上；第二步，左右成像平面通過(guò)繞光軸旋轉(zhuǎn)使兩攝像機(jī)主點(diǎn)連線與像素坐標(biāo)的連線平行[9]，兩個(gè)極點(diǎn)被映射到無(wú)窮遠(yuǎn)，校正后的左右成像平面水平對(duì)齊且在同一個(gè)平面上。平面上的成像點(diǎn)距離保持不變，類似于剛體變換。根據(jù)已經(jīng)標(biāo)定的兩攝像機(jī)內(nèi)部參數(shù)矩陣Kl和Kr以及左右兩個(gè)攝像機(jī)之間的旋轉(zhuǎn)矩陣R和平移向量T，那么可以將攝像機(jī)的基本矩陣F用如下公式表示為

(1)

其中，S為平移矢量的反對(duì)稱矩陣，表示為

(2)

圖1 極線校正過(guò)程

左右極點(diǎn)經(jīng)過(guò)極線校正被映射到無(wú)窮遠(yuǎn)處，校正后的圖像對(duì)極線方程為

(3)

其中，pl和pr分別表示空間中的一點(diǎn)P在左右攝像機(jī)成像平面上的成像點(diǎn)的坐標(biāo)。

2 基于SAD算法的立體匹配

2.1 立體匹配約束準(zhǔn)則

通過(guò)二維圖像來(lái)獲取空間物體的三維信息，立體匹配的本身就存在一些不確定性，為了使得到的匹配結(jié)果能夠相對(duì)準(zhǔn)確，需要借助各種約束條件來(lái)縮小匹配的搜索程序任務(wù)量，同時(shí)提高匹配的精確度。約束準(zhǔn)則常用的有以下幾種。

(1)極線約束

極線約束就是指同一空間中的實(shí)物點(diǎn)在左、右兩幅成像平面上的映射。三維場(chǎng)景中的一點(diǎn)P投影到兩個(gè)不同攝像機(jī)成像平面，投影點(diǎn)分別為Pl、Pr。定義左、右攝像機(jī)的光心分別為Ol、Or。由P、Ol和Or三點(diǎn)構(gòu)成的極平面與攝像機(jī)成像平面的交線為極線。由此可以確定與左圖映射點(diǎn)Pl對(duì)應(yīng)的右圖映射點(diǎn)Pr一定在右極線上，二維搜索降為一維搜索，這樣降低了匹配的復(fù)雜程度[10]。

(2)圖像一致性約束

由于左右兩攝像機(jī)的位置和成像條件不同，景物被拍攝過(guò)程中所得圖像中的對(duì)應(yīng)點(diǎn)可能存在一定的差異。但若兩幅圖像中的點(diǎn)是來(lái)自同一空間實(shí)物點(diǎn)的影像，則圖像區(qū)域的灰度變化情況以及幾何結(jié)構(gòu)都是相同的，由此可以確定對(duì)應(yīng)的匹配點(diǎn)。

(3)唯一性約束

由成像原理可知，空間中的任意一點(diǎn)在成像平面上只有唯一的點(diǎn)對(duì)應(yīng)。唯一性約束對(duì)匹配過(guò)程起到簡(jiǎn)化的作用。即在匹配圖像上的任意一個(gè)匹配基元在待匹配圖像上有且僅有一個(gè)匹配基元與其相對(duì)應(yīng)[11]，這樣每個(gè)匹配基元至多得到一個(gè)視差值。

(4)連續(xù)性約束

三維空間的某一被拍攝物體在拍攝時(shí)其自身的信息經(jīng)過(guò)透視映射到了成像平面上，且成像過(guò)程不會(huì)影響每個(gè)特征點(diǎn)的位置關(guān)系，也就是說(shuō)物體表面上相鄰的兩點(diǎn)在成像平面上的投影點(diǎn)也是相鄰的關(guān)系。例如：P和Q是相鄰兩點(diǎn)且分別在成像平面上對(duì)應(yīng)的匹配點(diǎn)為P′、Q′。已知P和P′是對(duì)應(yīng)匹配的關(guān)系，則作為相鄰點(diǎn)Q的匹配點(diǎn)Q′與P′一定也是相鄰的關(guān)系。

約束條件可在一定程度上限定對(duì)應(yīng)點(diǎn)的搜索范圍，減少匹配中的歧義性。

2.2 SAD算法原理

在雙目立體視覺(jué)的眾多匹配算法當(dāng)中，灰度差累積(Sum of absolute differences，SAD)算法是基于灰度的模板匹配算法。具有運(yùn)算速度快、實(shí)時(shí)性好等優(yōu)點(diǎn)，可以較好地滿足多數(shù)雙目立體視覺(jué)系統(tǒng)的需求[12]。該算法的中心思想是把左右圖像中匹配點(diǎn)對(duì)應(yīng)灰度值的差取絕對(duì)值再進(jìn)行累積求和，計(jì)算得到的結(jié)果可對(duì)左右兩個(gè)圖像塊的相似度進(jìn)行評(píng)估。

針對(duì)雙目立體視覺(jué)系統(tǒng)同時(shí)采集的圖像對(duì)，經(jīng)過(guò)極線校正處理后是水平的，即圖像對(duì)的外極線平行。同一空間點(diǎn)在左右成像平面上得到的兩個(gè)像點(diǎn)其y軸坐標(biāo)一致。局部立體匹配算法需要建立窗口來(lái)完成匹配，用窗口中的多個(gè)像素灰度值來(lái)表征中心點(diǎn)，逐一選取像素點(diǎn)鄰域內(nèi)的一個(gè)子窗口與參考窗口進(jìn)行比較，用相似性測(cè)度函數(shù)的計(jì)算值來(lái)評(píng)價(jià)兩個(gè)窗口的相似度[13]。當(dāng)某個(gè)子窗口與參考窗口最相似時(shí)，即認(rèn)為這個(gè)窗口的中心點(diǎn)與待匹配點(diǎn)是對(duì)應(yīng)點(diǎn)對(duì)。對(duì)每一個(gè)像素點(diǎn)進(jìn)行處理，即可完成兩幅圖像的匹配。匹配窗口的構(gòu)建如圖2所示。其中，Wl、Wr分別表示所構(gòu)建尺寸大小為M×N的匹配窗口和待匹配窗口，兩窗口的中心點(diǎn)坐標(biāo)分別為(x0,y0)、(x0-d,y0)。Pl、Pr分別表示左攝像機(jī)拍攝的參考圖像以及右攝像機(jī)拍攝的待匹配圖像。SAD窗口匹配算法在匹配窗口Wl與待匹配窗口Wr中分別統(tǒng)計(jì)對(duì)應(yīng)位置窗口內(nèi)的像素灰度值差的絕對(duì)值，在不超出所給定的視差范圍內(nèi)對(duì)所有待匹配點(diǎn)構(gòu)建的匹配窗口進(jìn)行遍歷。

圖2 匹配窗口示意圖

如圖3所示，通過(guò)滑動(dòng)窗口來(lái)完成立體匹配。取dmax為可承受的最大視差值，則搜索范圍為[0,dmax]，也就是只需在橫坐標(biāo)為[x,x+dmax]的范圍內(nèi)進(jìn)行搜索。對(duì)目標(biāo)圖進(jìn)行匹配的過(guò)程為在視差范圍沿著極線依次選取點(diǎn)作為M×N匹配窗口的中心點(diǎn)，在視差范圍內(nèi)對(duì)所有待匹配點(diǎn)構(gòu)建的匹配窗口進(jìn)行搜索，篩選出鄰域灰度信息最相似的點(diǎn)作為最佳匹配點(diǎn)。SAD是其中的一種相似性測(cè)度函數(shù)，表達(dá)式為

(4)

其中d為該點(diǎn)的視差值，W表示支持窗口.使CSAD結(jié)果最小的待匹配窗口視差值d就是投影點(diǎn)(x0,y0)的最佳視差值。

圖3 模板遍歷過(guò)程

匹配計(jì)算必須有合理的相似性測(cè)度指標(biāo)。滿足匹配的準(zhǔn)確性和計(jì)算效率的要求。相似性測(cè)度在不同的算法中具體形式有所不同，但多數(shù)立體匹配算法可將相似性測(cè)度歸納為一種求解匹配代價(jià)函數(shù)形式[14]。常用的匹配代價(jià)函數(shù)還有MAD、SSD、NCC等。

平均絕對(duì)差算法MAD具有匹配精度大的優(yōu)點(diǎn)，但是運(yùn)算量大、對(duì)噪聲比較敏感。其計(jì)算原理如下

(5)

誤差平方和算法SSD與SAD算法步驟大體一致，差別在于SSD將所得的像素差平方運(yùn)算之后再進(jìn)行累加。表達(dá)式為

(6)

歸一化積相關(guān)算法NCC定義了歸一化相關(guān)系數(shù)，計(jì)算公式為

(7)

歸一化相關(guān)系數(shù)R(i,j)的值域范圍為[-1,1],也就是說(shuō)相關(guān)系數(shù)越接近于1，兩幅圖像中對(duì)應(yīng)區(qū)域塊越匹配。以上提到的三種匹配算法在匹配過(guò)程中與本文所研究的SAD匹配算法思路比較類似，主要區(qū)別在于判別函數(shù)。其中，NCC算法公式相對(duì)復(fù)雜，而且計(jì)算量比較大。

3 匹配過(guò)程

立體匹配分為匹配代價(jià)計(jì)算、匹配代價(jià)累積、計(jì)算視差、視差精化四個(gè)步驟。

匹配代價(jià)通常是通過(guò)對(duì)左右兩幅圖像對(duì)應(yīng)像素的灰度值差計(jì)算來(lái)決定的，一般通過(guò)構(gòu)建目標(biāo)函數(shù)或能量函數(shù)，能使目標(biāo)函數(shù)最小化的即為最佳匹配結(jié)果。在匹配代價(jià)計(jì)算得到的三維視差空間圖像內(nèi)搜索到的匹配代價(jià)最小視差值就是理想視差。

匹配代價(jià)積累就是采用窗口卷積對(duì)每一幅代價(jià)圖進(jìn)行聚合以達(dá)到局部濾波的目的。上一步的代價(jià)計(jì)算得到了全部像素對(duì)應(yīng)的視差值，但是這些視差值都是孤立存在的，有大量噪聲被引入。

常用WTA(Winner-take-all)算法對(duì)基于區(qū)域的立體匹配進(jìn)行視差值的計(jì)算[15]。根據(jù)左右兩幅視圖的差異可分為特征點(diǎn)和非特征點(diǎn)，對(duì)視圖中的特征點(diǎn)進(jìn)行WTA計(jì)算，視圖中的非特征點(diǎn)只進(jìn)行簡(jiǎn)單的驗(yàn)證，不僅運(yùn)算量減少了，還能得到致密的視差圖。

所謂視差精化就是對(duì)所得的視差結(jié)果進(jìn)行優(yōu)化的過(guò)程。常用的處理方法有遮擋處理、左右一致性檢測(cè)、中值濾波等。經(jīng)過(guò)此類方法優(yōu)化后基本都能使最后的視差結(jié)果提升約1%。

匹配實(shí)現(xiàn)流程如圖4所示。首先從輸入的圖像中獲取數(shù)據(jù)信息，對(duì)左側(cè)圖像進(jìn)行掃描并選定一個(gè)錨點(diǎn)。接下來(lái)構(gòu)造一個(gè)固定矩形匹配窗口并設(shè)置它的大小，進(jìn)行匹配代價(jià)聚合，即求出所有像素點(diǎn)灰度差絕對(duì)值之和。最后在右側(cè)圖像上進(jìn)行視差篩選，選出相似性最高的匹配點(diǎn)，即找到左視圖錨點(diǎn)的最佳匹配像素塊。

4 實(shí)驗(yàn)結(jié)果與仿真

通過(guò)相機(jī)標(biāo)定得到左右相機(jī)的內(nèi)外參數(shù)信息，將此參數(shù)結(jié)果寫(xiě)入MATLAB校正程序的參數(shù)矩陣中來(lái)對(duì)采集的圖像對(duì)進(jìn)行校正，校正后的結(jié)果圖如圖5，圖6所示。

基于區(qū)域的匹配算法所得視差圖效果與匹配窗口尺寸密切相關(guān)。隨著窗口尺寸的調(diào)整，匹配效果發(fā)生了很大的變化。尺寸過(guò)大會(huì)有更大的幾率包含深度不同的目標(biāo)，但在深度不連續(xù)區(qū)域的表現(xiàn)下降；尺寸過(guò)小的窗口會(huì)因?yàn)椴荒馨銐虻男畔⒁缘挚闺S機(jī)噪聲的干擾而產(chǎn)生較多的錯(cuò)誤匹配點(diǎn)。

為了評(píng)價(jià)本文匹配算法的準(zhǔn)確性，基于VS2010開(kāi)發(fā)環(huán)境，采用OPENCV3.3.0編寫(xiě)程序?qū)崿F(xiàn)傳統(tǒng)SAD 算法對(duì)校正后的圖像對(duì)進(jìn)行立體匹配，并對(duì)不同的窗口大小進(jìn)行試驗(yàn)，得到元素值為視差值的圖像，即視差圖[16]。顯示結(jié)果如圖7所示。

圖5 采集的圖像對(duì)

通過(guò)以上的對(duì)比實(shí)驗(yàn)可直觀觀察到，SAD算法進(jìn)行的立體匹配得到的視差圖效果隨著窗口尺寸的調(diào)整，發(fā)生了很大變化。當(dāng)窗口尺寸小于3時(shí)邊緣區(qū)域很大的程度被模糊了。窗口尺寸為4～6時(shí)，視差圖效果較好。窗口尺寸大于8時(shí)，產(chǎn)生了很多的錯(cuò)誤匹配點(diǎn)。

圖6 校正后的圖像對(duì)

圖7 不同匹配窗口下的視差圖

經(jīng)過(guò)實(shí)驗(yàn)測(cè)試，當(dāng)窗口尺寸設(shè)置為4×4時(shí)，得到的視差圖效果最佳。圖中存在的瑕疵之處是在紋理不豐富的區(qū)域發(fā)生一定的錯(cuò)誤匹配，故本文算法還需要進(jìn)一步的研究和優(yōu)化。

5 結(jié)論

立體匹配的速度和所得結(jié)果的精度受多種因素影響?，F(xiàn)階段，還尚未有能夠完整處理立體匹配的整個(gè)流程的算法[17]。本文所述的SAD(Sum of absolute differences)算法主要針對(duì)立體匹配中圖像塊匹配這一步驟，對(duì)局部有明顯特征的特征點(diǎn)匹配更準(zhǔn)確。用SAD算法進(jìn)行的立體匹配，得到的視差圖具有較好深度感，為下一步的三維重建打下了堅(jiān)實(shí)的基礎(chǔ)。