雙目立體視覺匹配技術綜述

曹之樂，嚴中紅，王 洪

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

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

1 雙目立體視覺系統

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

圖1 雙目視覺系統幾何原理

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

1.1 立體匹配約束

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

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

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

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

1.2 立體匹配的匹配基元

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

2 立體匹配算法

在立體匹配視覺系統的原理基礎上，根據匹配的約束條件就可以對選定的匹配基元進行匹配。匹配算法是立體匹配技術的核心。

2.1 基于區域的立體匹配算法

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

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

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

區域匹配由于匹配的特征為獨立的像素或像素塊，因此在噪聲和誤匹配的影響下，匹配出的圖像很不平滑，更重要的是圖像中的無紋理區域因為像素的亮度相似會產生大量的誤匹配。然而區域匹配因其計算復雜度低，運算速度快，故在大量的實時系統中獲得應用。為克服區域匹配算法的缺點，通常采用的特征也由簡單的亮度轉變為更為豐富的特征，如多尺度對頻段上的特征［4－5］，基于梯度的加權特征［3］等。

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

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

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

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

2.2.1 動態規劃全局優化算法

動態規劃是一種常用的算法，是解決問題的一種思路。其基本思路是將給出的問題分為一個個的小問題，通過解決這些小問題從而得出問題的解。一般這些子問題很相似，為了減小計算量，動態規劃試圖對每個子問題只計算一次。當得到一個子問題的解時，可將該結果直接保存，當再次需要相同子問題解時可直接查找此結果。

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

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

經典的動態規劃算法步驟如下:

1)初始化。初始化是對圖像的視差值進行初始的設定。這個初始設定可以全部為0，也可以預先簡單匹配出來的視差值。后者在動態規劃優化運算時迭代速度更快。

2)循環求解。在一條掃描線上逐點計算，在視差范圍內循環取值，得出前一點的全局能量函數值和前一點的路徑參數值。循環在掃描線的末尾前一點結束。

3)返回視差值。每一點的視差值都為其路徑參數值。具體步驟詳見文獻［7］。

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

2.2.2 圖像分割全局優化算法

圖像分割是根據圖像的自身結構特性，將圖像分為不同的區域，而后將這些區域的立體匹配問題轉化為能量函數最小化問題［11］。這種做法既可以達到全局算法的精確匹配，又可以保持原圖像中的結構信息。基于全局的立體匹配算法一般都會根據算法及約束的原理構造一個全局能量函數。同樣的，圖像分割法也有這樣的全局能量函數來實現迭代優化。

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

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

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

2.2.3 置信傳播

置信傳播算法建立在馬爾科夫隨機場模型的基礎上，更復雜的模型可以是一個或者幾個馬爾科夫隨機場構成的馬爾科夫網絡［16］。像素點與馬爾科夫隨機場模型中的節點一一對應。置信傳播算法采用消息傳輸機制實現節點之間置信度的最大化，同時實現馬爾科夫隨機場最大概率分布，等同于實現全局能量函數最小化［17］。

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

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

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

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

3 總結

總體來說，計算視差的過程是一個提取特征并進行特征匹配的過程。基于局部的立體匹配算法在匹配過程中只是簡單計算左右圖像的特征差異最小化，或者是計算左右圖像的特征相似性?；谌值牧Ⅲw匹配算法在匹配過程中使用優化算法，同時考慮平滑性和精確性，使全局能量函數最小化。上文中的動態規劃和置信傳播都是優化視差的算法，圖像分割則是重要的保留圖像結構的算法，因此對于高精度的視差計算，可以結合兩者一起使用。本文算法技術總結見表1。

表1 算法技術總結

4 結束語

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

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

［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］.計算機應用，2011，31(1):175-178.

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

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

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

［15］張娟.基于彩色圖像分割的立體匹配算法研究［D］.濟南:山東大學，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］.數字技術與應用，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.