曹之樂，嚴(yán)中紅，王 洪

(重慶理工大學(xué)藥學(xué)與生物工程學(xué)院，重慶 400054)

立體視覺技術(shù)廣泛應(yīng)用于探測車導(dǎo)航、機(jī)器人導(dǎo)航、3D場景圖繪制、3D場景重建、汽車預(yù)警系統(tǒng)、大型機(jī)械位姿感知等領(lǐng)域。自20世紀(jì)70年代Marr首次提出完整的機(jī)器視覺系統(tǒng)計(jì)算理論框架［1］以來，三維視覺信號備受人們的關(guān)注。早期的立體匹配是基于小窗口的區(qū)域匹配，提取的特征值大多為灰度、顏色等信息。后來開發(fā)出自適應(yīng)窗口技術(shù)，針對特征值也開發(fā)出對光照魯棒性的變換值，如Census變換等。近年來，基于全局的立體匹配技術(shù)成為人們研究的熱點(diǎn)，其大致思路為:提取特征值光流場特征、邊緣特征、Harris角點(diǎn)特征、SIFT特征向量、SURF特征等可靠特征，計(jì)算出初步視差圖，再由全局優(yōu)化函數(shù)(動態(tài)規(guī)劃、圖像分割、置信傳播等)對整幅圖像的視差值進(jìn)行迭代優(yōu)化分配計(jì)算。目前，主流的立體視覺匹配技術(shù)分為2種:基于區(qū)域的立體匹配和基于全局的立體匹配。本文主要就以上2種技術(shù)的一些經(jīng)典立體匹配方法和近年來發(fā)展起來的立體匹配新方法進(jìn)行較深入的討論和評述。

1 雙目立體視覺系統(tǒng)

最常見的立體視覺系統(tǒng)是雙目立體視覺系統(tǒng)，也可以是多目視覺系統(tǒng)，但雙目視覺系統(tǒng)是其基礎(chǔ)。因此，本文首先簡要闡述雙目視覺系統(tǒng)，其幾何原理如圖1所示。

圖1 雙目視覺系統(tǒng)幾何原理

在三維空間坐標(biāo)系OaXaYaZa中，左攝像頭Ol和右攝像頭Or處于理想位置關(guān)系。其中，左攝像頭光軸Zl和右攝像頭光軸Zr平行，且直線ZlZr與三維空間坐標(biāo)系中的Xa軸垂直。2個成像中心Ol、Or的連線為基線b。三維空間中的一點(diǎn)P與兩成像中心點(diǎn)Ol、Or以及映射點(diǎn)pl和pr處于同一平面，平面與兩成像平面的交線被稱為極線。根據(jù)立體視覺的幾何成像原理，雙目立體視覺系統(tǒng)中對第三維(即深度)的測量由式(1)得出。其中:f為焦距，d為視差，即點(diǎn)pl和pr兩圖像在X軸方向上的差值，深度為Z?；€b和焦距f可在雙目標(biāo)定時計(jì)算得出，因此雙目立體視覺定位的核心內(nèi)容是對視差d的計(jì)算。視差d由立體匹配得出，故對立體匹配的研究和討論成為雙目視覺系統(tǒng)研究的核心內(nèi)容。

1.1 立體匹配約束

1)唯一性約束:三維空間中的點(diǎn)映射到左右攝像頭時，只會在圖像上映射出唯一的對應(yīng)點(diǎn)。在匹配時左右圖像只有唯一一點(diǎn)相匹配。

2)連續(xù)性約束:三維空間中的物體一般是連續(xù)光滑的，在映射到左右攝像頭時這種特性也被保留下來。在連續(xù)的圖像上，其視差也一般是連續(xù)的。

3)極線約束:如圖1所示，對于一個圖像上的映射點(diǎn)來說，其匹配點(diǎn)必定落在另一圖像的極線上。而對雙目視覺系統(tǒng)來說，通常將其校正為上文原理中的假設(shè)情況，在這種情況下匹配點(diǎn)對處于同一水平線，即點(diǎn)在圖像中的坐標(biāo)y值相等。

4)順序一致性約束:三維空間中點(diǎn)的位置關(guān)系會在映射到成像平面時保留下來，即原物體的位置順序在兩幅圖像中不會改變。

1.2 立體匹配的匹配基元

匹配基元是立體匹配中的單位匹配對象，也就是立體匹配中的匹配特征對象。一般有以下幾種:①點(diǎn):在雙目立體匹配中最常用的特征就是點(diǎn)特征，例如像素點(diǎn)的灰度、顏色值、Harris角點(diǎn)、SIFT特征點(diǎn)、SURF特征點(diǎn)等;② 塊:圖像塊也可以認(rèn)為是圖像區(qū)域，塊的特征提取可以是直觀的塊內(nèi)所有像素點(diǎn)的灰度或顏色值，也可以是對塊內(nèi)像素點(diǎn)的統(tǒng)計(jì)特征，還可以是對塊內(nèi)像素點(diǎn)的變換特征;③線:線一般只是邊緣線，是最能體現(xiàn)圖像的紋理區(qū)域特征。在有些方法中將角點(diǎn)或特征點(diǎn)之間的連線作為特征線來提取。

2 立體匹配算法

在立體匹配視覺系統(tǒng)的原理基礎(chǔ)上，根據(jù)匹配的約束條件就可以對選定的匹配基元進(jìn)行匹配。匹配算法是立體匹配技術(shù)的核心。

2.1 基于區(qū)域的立體匹配算法

基于區(qū)域的立體匹配通常是在一個設(shè)定的窗口基礎(chǔ)上來完成，以窗口中提取的特征向量為基礎(chǔ)進(jìn)行匹配。這種匹配可以是逐像素的匹配，也可以是成塊的匹配，更進(jìn)一步的，有根據(jù)圖像自適應(yīng)調(diào)節(jié)窗口大小的區(qū)域匹配算法。經(jīng)典的有Lazaros Nalpantidi等［2］以灰度、顏色為特征，通過對窗口內(nèi)的點(diǎn)的空間距離加權(quán)、顏色加權(quán)以及邊緣加權(quán)來提高匹配精度。對于窗口來說，窗口越大信息量越多，匹配精度越高，但會帶來大量的復(fù)雜計(jì)算，影響整體算法的運(yùn)行速度［3］。

在計(jì)算出的視差層面上通常采用贏者通吃(winner-takes-all，WTA)的方法來聚合匹配像素或塊。以亮度特征為例，在立體匹配過程中可以選取絕對差值和SAD、差值平方和SSD、歸一化相關(guān)系數(shù)NCC、零均值絕對差值和ZSAD等匹配函數(shù)，詳見公式(2)。

上述函數(shù)中:I1，I2為左右圖像對;u，v為像素的坐標(biāo)點(diǎn);n，m為窗口的長和寬為窗口中像素亮度的平均值。這些匹配函數(shù)可以對窗口中的亮度等特征進(jìn)行匹配。

區(qū)域匹配由于匹配的特征為獨(dú)立的像素或像素塊，因此在噪聲和誤匹配的影響下，匹配出的圖像很不平滑，更重要的是圖像中的無紋理區(qū)域因?yàn)橄袼氐牧炼认嗨茣a(chǎn)生大量的誤匹配。然而區(qū)域匹配因其計(jì)算復(fù)雜度低，運(yùn)算速度快，故在大量的實(shí)時系統(tǒng)中獲得應(yīng)用。為克服區(qū)域匹配算法的缺點(diǎn)，通常采用的特征也由簡單的亮度轉(zhuǎn)變?yōu)楦鼮樨S富的特征，如多尺度對頻段上的特征［4－5］，基于梯度的加權(quán)特征［3］等。

另外，對于受光照變化影響嚴(yán)重的圖像，一般采用變換的方法進(jìn)行處理。例如，Census變換可以將窗口中的亮度值變換為一個序列，匹配時只需計(jì)算兩幅圖像中窗口特征序列的漢明距離(Hamming distance);Rank變換則是統(tǒng)計(jì)0或1的個數(shù)作為特征值，因而可以使用上文中的匹配函數(shù)。

2.2 基于全局的立體匹配算法

基于全局的立體匹配通常是先找出圖像中顯著的特征點(diǎn)、特征線或者掃描線，初步匹配得出一個初始的視差值，然后使用全局能量函數(shù)進(jìn)行約束，通過匹配算法不斷地對分配的視差值迭代優(yōu)化，直到最優(yōu)。此迭代優(yōu)化的過程以全局能量函數(shù)最小化為目的。

全局能量函數(shù)一般包括2項(xiàng)，數(shù)據(jù)項(xiàng)和平滑項(xiàng)，見式(3)。數(shù)據(jù)項(xiàng)用來表示該匹配基元的視差值，平滑項(xiàng)用來約束鄰域基元之間的差值［6］。近年來，硬件技術(shù)的飛速發(fā)展使得這種復(fù)雜匹配方法的實(shí)時性成為可能，未來的立體匹配方法也必將以基于全局的匹配方法為主流。

2.2.1 動態(tài)規(guī)劃全局優(yōu)化算法

動態(tài)規(guī)劃是一種常用的算法，是解決問題的一種思路。其基本思路是將給出的問題分為一個個的小問題，通過解決這些小問題從而得出問題的解。一般這些子問題很相似，為了減小計(jì)算量，動態(tài)規(guī)劃試圖對每個子問題只計(jì)算一次。當(dāng)?shù)玫揭粋€子問題的解時，可將該結(jié)果直接保存，當(dāng)再次需要相同子問題解時可直接查找此結(jié)果。

在動態(tài)規(guī)劃的使用方面，2010年，J.Cal在文獻(xiàn)［7］中結(jié)合光流法和動態(tài)規(guī)劃，以光流法計(jì)算視差圖，再基于此視差圖使用動態(tài)規(guī)劃進(jìn)行優(yōu)化。2011 年，Mohamed El Ansari等［8］依據(jù)提取出的邊緣線上的點(diǎn)做動態(tài)規(guī)劃，以邊緣點(diǎn)的梯度幅值和方向作為引導(dǎo)動態(tài)規(guī)劃的全局能量函數(shù)。2013年，Minh Nguyen，Yuk Hin Chan在文獻(xiàn)［9］中使用圖像塊進(jìn)行動態(tài)規(guī)劃匹配，并進(jìn)行雙向匹配以降低誤差。

應(yīng)用立體匹配時，一般先匹配出一個初始的視差圖，然后使用動態(tài)規(guī)劃算法，在一條掃描線上(通常為極線)尋找使立體匹配能量函數(shù)值最小的路徑(視差值)。掃描線上的每一點(diǎn)的視差為得到的最小路徑值(視差值)［7］。

經(jīng)典的動態(tài)規(guī)劃算法步驟如下:

1)初始化。初始化是對圖像的視差值進(jìn)行初始的設(shè)定。這個初始設(shè)定可以全部為0，也可以預(yù)先簡單匹配出來的視差值。后者在動態(tài)規(guī)劃優(yōu)化運(yùn)算時迭代速度更快。

2)循環(huán)求解。在一條掃描線上逐點(diǎn)計(jì)算，在視差范圍內(nèi)循環(huán)取值，得出前一點(diǎn)的全局能量函數(shù)值和前一點(diǎn)的路徑參數(shù)值。循環(huán)在掃描線的末尾前一點(diǎn)結(jié)束。

3)返回視差值。每一點(diǎn)的視差值都為其路徑參數(shù)值。具體步驟詳見文獻(xiàn)［7］。

雙目視覺立體匹配中，在上文假設(shè)前提下，極線處于兩張圖像的同一水平線上，即上圖中左圖極線和右圖極線的y軸坐標(biāo)值相等。因此，經(jīng)常使用的掃描線就是極線，可以進(jìn)行單向匹配，即由一圖作為基準(zhǔn)去和另一張圖匹配;也可以進(jìn)行雙向匹配，即從左向右匹配，而后再從右向左匹配，取匹配較高的視差值作為最終視差值，以提高匹配精度。但是用極線作掃描線時，動態(tài)規(guī)劃僅是對單獨(dú)的橫向極線匹配，忽略了平行極線之間的關(guān)系，使得圖像的匹配結(jié)果呈現(xiàn)水平的條紋狀，因此動態(tài)規(guī)劃法在使用中常以消除此條紋作為提高視差圖質(zhì)量的核心。同時，由于動態(tài)規(guī)劃僅是一種優(yōu)化算法，直接使用其進(jìn)行匹配會耗費(fèi)大量的運(yùn)行時間，其迭代要達(dá)到一定次數(shù)才會有較好的效果，因此這種算法一般和其他匹配算法聯(lián)合使用［10］。

2.2.2 圖像分割全局優(yōu)化算法

圖像分割是根據(jù)圖像的自身結(jié)構(gòu)特性，將圖像分為不同的區(qū)域，而后將這些區(qū)域的立體匹配問題轉(zhuǎn)化為能量函數(shù)最小化問題［11］。這種做法既可以達(dá)到全局算法的精確匹配，又可以保持原圖像中的結(jié)構(gòu)信息?；谌值牧Ⅲw匹配算法一般都會根據(jù)算法及約束的原理構(gòu)造一個全局能量函數(shù)。同樣的，圖像分割法也有這樣的全局能量函數(shù)來實(shí)現(xiàn)迭代優(yōu)化。

2006 年，Andreas Klaus等［12］基于顏色特征進(jìn)行圖像分割，對劃分出來的圖像區(qū)域使用自適應(yīng)相似性度量函數(shù)計(jì)算最優(yōu)視差。2007年，張娟［13］對圖像的特征空間做均值漂移計(jì)算，使用分水嶺分割模型得出分割的圖像塊。2010年，Bleyer等［10］提出了一種圖像分割的基本算法框架，首先將圖像分割為不同的區(qū)域，根據(jù)不同區(qū)域的最小匹配函數(shù)計(jì)算出分割區(qū)域的視差，然后拼合視差相同的區(qū)域，最終獲取區(qū)域視差的最優(yōu)化匹配。2011年，顏軻等［11］對基于 MRF(Markov隨機(jī)場)的圖像分割算法進(jìn)行了改進(jìn)，先對圖像進(jìn)行分割，在此基礎(chǔ)上建立立體匹配的MRF模型，以充分保留圖像的構(gòu)架信息，進(jìn)而得到平滑的視差圖像。

圖像分割法的目的是根據(jù)圖像特征劃分得到一個分割的塊集合，而后對這些塊分別進(jìn)行優(yōu)化計(jì)算視差，最大限度地保留圖像的結(jié)構(gòu)信息［12－14］。為實(shí)現(xiàn)這一目標(biāo)，目前的算法大致分為以下幾類:①以像素為基準(zhǔn)的分割法，不考慮圖像的空間構(gòu)架，只以像素點(diǎn)的顏色特征等來劃分圖像;②以區(qū)域?yàn)榛鶞?zhǔn)的分割法，以圖像中區(qū)域塊的連通特性為約束，使用區(qū)域生長、分裂和聚合技術(shù)實(shí)現(xiàn);③以邊界為基準(zhǔn)，依靠測定出的邊緣劃分圖像;④以模型為基準(zhǔn)，大多為馬爾科夫(Markov)隨機(jī)場或吉布斯(Gibbs)隨機(jī)場等空間交互模型來對圖像建模［15］。近年來多采用圖像分割算法方法。

圖像分割在大部分領(lǐng)域中都有很好的應(yīng)用，其原理是基于顏色、邊緣等信息進(jìn)行分割，而當(dāng)這些信息與深度信息不能統(tǒng)一時(即深度信息與顏色、邊緣等無關(guān)時)，匹配就會產(chǎn)生許多誤差。

2.2.3 置信傳播

置信傳播算法建立在馬爾科夫隨機(jī)場模型的基礎(chǔ)上，更復(fù)雜的模型可以是一個或者幾個馬爾科夫隨機(jī)場構(gòu)成的馬爾科夫網(wǎng)絡(luò)［16］。像素點(diǎn)與馬爾科夫隨機(jī)場模型中的節(jié)點(diǎn)一一對應(yīng)。置信傳播算法采用消息傳輸機(jī)制實(shí)現(xiàn)節(jié)點(diǎn)之間置信度的最大化，同時實(shí)現(xiàn)馬爾科夫隨機(jī)場最大概率分布，等同于實(shí)現(xiàn)全局能量函數(shù)最小化［17］。

2003年，Jian Sun等［16］使用 3個馬爾科夫隨機(jī)場構(gòu)建出一個馬爾科夫隨機(jī)網(wǎng)絡(luò)，3個場中平滑場保持視差的連續(xù)性，線性場保留視差的斷層，二元場保持視差層的閉塞。2013年，Armin Ahmadzadeh等［18］在多個平臺(包括 FPGA，GPU，多核GPU)上實(shí)驗(yàn)置信傳播算法，并選定多核GPU得出一個性能和效率俱佳的置信傳播立體匹配算法。

置信傳播算法的思路如下:①構(gòu)建全局能量函數(shù)，以此約束節(jié)點(diǎn)的更新，式子構(gòu)建如上文所說包括數(shù)據(jù)項(xiàng)和平滑項(xiàng);②構(gòu)建圖像對的馬爾科夫隨機(jī)場模型，并確定節(jié)點(diǎn)之間的消息傳播方式和傳播信息;③循環(huán)迭代直至節(jié)點(diǎn)上的信息最優(yōu)化，根據(jù)節(jié)點(diǎn)信息算出視差值。具體算法步驟詳見文獻(xiàn)［19］。

馬爾科夫隨機(jī)場模型是將圖像對的像素點(diǎn)看作節(jié)點(diǎn)，而每個節(jié)點(diǎn)包含兩方面信息:數(shù)據(jù)信息和消息信息。數(shù)據(jù)信息是每一個像素點(diǎn)的視差值，消息信息則是每個節(jié)點(diǎn)的信息值(初始為零)。

置信算法在每一次迭代過程中都會對節(jié)點(diǎn)的信息進(jìn)行更新，節(jié)點(diǎn)間的消息傳播一般為BP-M和BP-S。在BP-M中，每一次的傳播都在鄰域4個方向(上下左右)點(diǎn)上進(jìn)行。而在BP-S中的傳播分為2種:一種向前，即消息向下和向右傳播直至達(dá)到最后一個節(jié);另一種是向后，即消息向上和向左傳播直至達(dá)到第一個節(jié)點(diǎn)［18］。與動態(tài)規(guī)劃類似，該算法也是一種強(qiáng)大的優(yōu)化算法，在應(yīng)用中通常與其他匹配算法聯(lián)合使用。本算法的復(fù)雜性在于模型的建立、全局能量函數(shù)的構(gòu)建，以及信息傳遞的設(shè)定。

3 總結(jié)

總體來說，計(jì)算視差的過程是一個提取特征并進(jìn)行特征匹配的過程。基于局部的立體匹配算法在匹配過程中只是簡單計(jì)算左右圖像的特征差異最小化，或者是計(jì)算左右圖像的特征相似性。基于全局的立體匹配算法在匹配過程中使用優(yōu)化算法，同時考慮平滑性和精確性，使全局能量函數(shù)最小化。上文中的動態(tài)規(guī)劃和置信傳播都是優(yōu)化視差的算法，圖像分割則是重要的保留圖像結(jié)構(gòu)的算法，因此對于高精度的視差計(jì)算，可以結(jié)合兩者一起使用。本文算法技術(shù)總結(jié)見表1。

表1 算法技術(shù)總結(jié)

4 結(jié)束語

近年來，新的方法不斷被引入立體匹配領(lǐng)域，立體視覺技術(shù)也不斷應(yīng)用于新領(lǐng)域。Kajal Sharma等在2012年提出用SIFT特征作為輸入，使用自組織特征映射模型這種人工神經(jīng)網(wǎng)絡(luò)進(jìn)行立體匹配。Li-Heng Lin等在2013年提出一種使用harrs角點(diǎn)群進(jìn)行立體匹配以獲取大型器械的位姿算法。

相比運(yùn)算速度，近年來更重視對精度和匹配度的要求。在硬件技術(shù)迅速發(fā)展的現(xiàn)狀下，之前許多不能保證實(shí)時性的算法都可以很好地實(shí)現(xiàn)。未來立體匹配的研究重點(diǎn)將集中于如何提高精度，對于算法的應(yīng)用也應(yīng)是多種算法聯(lián)合的多層面多尺度上的匹配。

［1］Marr D C.A Computational Investigation into the Human Representation and Processing of Visual Information［M］.San Francisco:W.H.Freeman and company，1982.

［2］Nalpantidis L，Gasteratos A.Stereo vision for robotic applications in the presence of non-ideal lighting conditions［J］.Image and Vision Computing，2010，28(6):940-951.

［3］Ambrosch K，Kubinger W.Accurate hardware-based stereo vision［J］.Computer Vision and Image Understanding，2010，114:1303-1316.

［4］Nuan Shao，Hui Guang Li，Le Liu，et al.Stereo vision robot obstacle detection based on the SIFT［R］.2010 Second WRI Global Congress on Intelligent Systems，2010.

［5］Sizintsev M，Wildes R P.Coarse-to-fine stereo vision with accurate 3D boundaries［J］.Image and Vision Computing，2010，28:352－366.

［6］Boykov Y，Veksler O，Zabih R.Fast Approximate energy minimization via graph cut［J］.Pattern Analysis and Machine Intelligence，2002，23(11):1222-1239.

［7］Cai J.Integration of optical flow and dynamic programming for stereo matching［J］.IET Image Processing，2012，6(3):205-212.

［8］Mohamed El Ansari，Mazoul A，Bensrhair A，et al.A Realtime Spatio-Temporal Stereo Matching for Road Applications［C］//14th International IEEE Conference on Intelligent Transportation Systems.2011.

［9］Nguyen M，Yuk Hin Chan，Delmas P，et al.Symmetric Dynamic Programming Stereo Using Block Matching Guidance［C］//28t h Internati onal Conference on Image and Vision Computing New Zealand.2013.

［10］Gang Yao，Yong Liu，Bangjun Lei，et al.A Rapid Stereo Matching Algorithm Based on Disparity Interpolation［C］//Proceedings of 2010 Conference on Dependable Compnting.2010.

［11］顏軻，萬國偉，李思昆.基于圖像分割的立體匹配算法［J］.計(jì)算機(jī)應(yīng)用，2011，31(1):175-178.

［12］趙杰，祁永梅，潘正勇.結(jié)合邊界和區(qū)域的水平集超聲圖像分割算法［J］.激光雜志，2013(6):46－48.

［13］叢超.醫(yī)用心臟圖像分割算法的量化評估框架［J］.重慶理工大學(xué)學(xué)報:自然科學(xué)版，2013(7):71－75，112.

［14］易欣，賈振紅，覃錫忠，等.一種基于多相位水平集的圖像分割［J］.激光雜志，2013(6):37－39.

［15］張娟.基于彩色圖像分割的立體匹配算法研究［D］.濟(jì)南:山東大學(xué)，2007.

［16］Jian Sun，Nan Ning Zheng.Senior Member.Stereo matching using belief propagation［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，2003，25(7):787-800.

［17］李鶴喜，孫玲云.基于彩色圖像分割的置信傳播快速立體匹配算法［J］.數(shù)字技術(shù)與應(yīng)用，2013(1):115-117.

［18］Ahmadzadeh A，Madani H，Jafari K，et al.Fast and A-daptive BP-based Multi-core Implementation for Stereo Matching［R］.Formal Methods and Models for Codesign，2013.

［19］Felzenszwalb P F，Huttenlocher D P.Efficient Belief Propagation for Early Vision［J］.International Journal of Computer Vision，2006，70(1):41-54.