立體視覺是計算機視覺領域的一個重要課題，它的目的在于重構場景的三維幾何信息。立體視覺的研究具有重要的應用價值，其應用包括移動機器人的自主導航系統，航空及遙感測量，工業自動化系統等。

1. 引言
立體視覺是計算機視覺領域的一個重要課題，它的目的在于重構場景的三維幾何信息。立體視覺的研究具有重要的應用價值，其應用包括移動機器人的自主導航系統，航空及遙感測量，工業自動化系統等。

一般而言，立體視覺的研究有如下三類方法:
(1) 直接利用測距器（如激光測距儀）獲得程距（range data）信息，建立三維描述的方法;
(2) 僅利用一幅圖象所提供的信息推斷三維形狀的方法;
(3) 利用不同視點上的，也許是不同時間拍攝的，兩幅或更多幅圖象提供的信息重構三維結構的方法。

第一類方法，也就是程距法 (range data method)，根據已知的深度圖，用數值逼近的方法重建表面信息，根據模型建立場景中的物體描述，實現圖象理解功能。這是一種主動方式的立體視覺方法，其深度圖是由測距器(range finders)獲得的，如結構光(structured light)、激光測距器(laser range finders) 等其他主動傳感技術 (active sensing techniques)。這類方法適用于嚴格控制下的環境(tightly controlled domains)，如工業自動化的應用方面。

第二類方法，依據光學成象的透視原理及統計假設，根據場景中灰度變化導出物體輪廓及表面，由影到形(shape from shading)，從而推斷場景中的物體。線條圖的理解就是這樣的一個典型問題，曾經引起了普遍的重視而成為計算機視覺研究領域的一個焦點，由此產生了各種各樣的線條標注法。這種方法的結果是定性的，不能確定位置等定量信息，該方法由于受到單一圖象所能提供信息的局限性，存在難以克服的困難。

第三類方法，利用多幅圖象來恢復三維信息的方法，它是被動方式的。根據圖象獲取方式的區別又可以劃分成普通立體視覺和通常所稱的光流(optical flow)兩大類。普通立體視覺研究的是由兩攝像機同時拍攝下的兩幅圖象，而光流法中研究的是單個攝像機沿任一軌道運動時順序拍下的兩幅或更多幅圖象。前者可以看作后者的一個特例，它們具有相同的幾何構形，研究方法具有共同點。雙目立體視覺是它的一個特例。

立體視覺的研究由如下幾部分組成:
(1) 圖象獲取 (image acquisition),
用作立體視覺研究的圖象的獲取方法是多種多樣的，在時間、視點、方向上有很大的變動范圍，直接受所應用領域的影響。立體視覺的研究主要集中在三個應用領域中，即自動測繪中的航空圖片的解釋，自主車的導引及避障，人類立體視覺的功能模擬。不同的應用領域涉及不同類的景物，就場景特征的區別來分，可以劃分成兩大類，一類是含有文明特征(cultural features)的景物，如建筑、道路等; 另一類是含有自然特征的景物和表面(natural objects and surfaces)， 如山、水、平原及樹木等。不同類的景物的圖象處理方法大不相同，各有其特殊性。
總之，與圖象獲取相關的主要因素可歸納如下:
(a) 場景領域 (scene domain)，
(b) 計時 (timing)，
(c) 時間（照明和陰影）(time of day (lighting and presence ofshadows))，
(d) 成像形態（包括特殊的遮蓋）(photometry (including special coverage)),
(e) 分辨率 (resolution),
(f) 視野 (field of view),
(g) 攝像機的相對位置 (relative camera positioning).

場景的復雜程度受如下因素的影響:
(a) 遮掩 (occlusion),
(b) 人工物體（直的邊界,平的表面) (man-made objects (straight edge, flat surfaces)),
(c) 均勻的紋理區域 (smoothly textured areas),
(d) 含有重復結構的區域 (areas containing repetitive structure)。

(2) 攝像機模型 (camera modeling),
攝像機模型就是對立體攝像機組的重要的幾何與物理特征的表示形式，它作為一個計算模型，根據對應點的視差信息，用于計算對應點所代表的空間點的位置。攝像機模型除了提供圖象上對應點空間與實際場景空間之間的映射關系外，還可以用于約束尋找對應點時的搜索空間，從而降低匹配算法的復雜性，減小誤匹配率。

(3) 特征抽取 (feature acquisition),
幾乎是同一灰度的沒有特征的區域是難以找到可靠匹配的，因而，絕大部分計算機視覺中的工作都包括某種形式的特征抽取過程，而且特征抽取的具體形式與匹配策略緊密相關。在立體視覺的研究中，特征抽取過程就是提取匹配基元的過程。

(4) 圖象匹配 (image matching),
圖象匹配是立體視覺系統的核心，是建立圖象間的對應從而計算視差的過程，是極為重要的。

(5) 深度計算 (distance(depth) determination),
立體視覺的關鍵在于圖象匹配，一旦精確的對應點建立起來，距離的計算相對而言只是一個簡單的三角計算而已。然而，深度計算過程也遇到了顯著的困難，尤其是當對應點具有某種程度的非精確性或不可靠性時。粗略地說，距離計算的誤差與匹配的偏差成正比，而與攝像機組的基線長成反比。加大基線長可以減少誤差，但是這又增大了視差范圍和待匹配特征間的差別，從而使匹配問題復雜化了。為了解決這一問題出現了各種匹配策略，如由粗到精策略，松馳法等。

在很多情況下，匹配精度通常是一個象素。但是，實際上區域相關法和特征匹配法都可以獲得更好的精度。區域相關法要達到半個象素的精度需要對相關面進行內插。盡管有些特征抽取方法可以得到比一個象素精度更好的特征，但這直接依賴于所使用的算子類型，不存在普遍可用的方法。

另一種提高精度的方法是采用一個象素精度的算法，但是利用多幅圖象的匹配，通過多組匹配的統計平均結果獲得較高精度的估計。每組匹配結果對于最后深度估計的貢獻可以根據該匹配結果的可靠性或精度加權處理。

總之，提高深度計算精度的途徑有三條，各自涉及了一些附加的計算量:
(a) 半象素精度估計 (subpixel estimation),
(b) 加長基線長 (increased stereo baseline),
(c) 幾幅圖的統計平均 (statistical averaging over several views)。
(6) 內插 (interpolation).

在立體視覺的應用領域中，一般都需要一個稠密的深度圖。基于特征匹配的算法得到的僅是一個稀疏而且分布并不均勻的深度圖。在這種意義下，基于區域相關匹配的算法更適合于獲得稠密的深度圖，但是該方法在那些幾乎沒有信息（灰度均勻）的區域上的匹配往往不可靠。因此，兩類方法都離不開某種意義的內插過程。最為直接的將稀疏深度圖內插成稠密的深度圖的方法是將稀疏深度圖看作為連續深度圖的一個采樣，用一般的內插方法（如樣條逼近）來近似該連續深度圖。當稀疏深度圖足以反映深度的重要變化時，該方法可能是合適的。如起伏地貌的航空立體照片的處理中用這種方式的內插也許是比較合適的。但是這種方法在許多應用領域中，尤其是在有遮掩邊界的圖象的領域中，就不適用了。

Grimson 指出可匹配特征的遺漏程度反映了待內插表面變化程度的相應限度，在這種基礎上，他提出了一個內插過程[2]。換一角度來看，根據單幅圖象的“由影到形”的技術，用已經匹配上的特征來建立輪廓條件和光滑的交接表面可以確保內插的有效性。這些方法結合起來，可以使內插過程達到合乎要求的目標。內插的另一種途徑是在已有的幾何模型與稀疏深度圖之間建立映射關系，這是模型匹配過程。一般而言，要進行模型匹配，預先應將稀疏深度圖進行聚類，形成若干子集，各自相應于一種特殊結構。然后找每一類的最佳對應模型，該模型為這種特殊結構(物體)提供參數和內插函數。如 Gennery用這種方法來發現立體對圖片中的橢園結構，Moravec 用于為自主車探測地面。

2. 雙目立體視覺(Binocular Stereo Vision)

2.1 雙目立體視覺模型
雙目立體視覺理論建立在對人類視覺系統研究的基礎上，通過雙目立體圖象的處理，獲取場景的三維信息，其結果表現為深度圖，再經過進一步處理就可得到三維空間中的景物，實現二維圖象到三維空間的重構。Marr-Poggio-Grimson [1] 最早提出并實現了一種基于人類視覺系統的計算視覺模型及算法。雙目立體視覺系統中，獲取深度信息的方法比其它方式（如由影到形方法）較為直接，它是被動方式的，因而較主動方式（如程距法）適用面寬，這是它的突出特點。

雙目立體視覺系統中，深度信息的獲得是分如下兩步進行的:
(1) 在雙目立體圖象間建立點點對應,
(2) 根據對應點的視差計算出深度。

第一部分，也就是對應點問題，是雙目立體視覺的關鍵; 第二部分是攝像機模型問題。雙目立體視覺模型中，雙攝像機彼此參數一致，光軸平行且垂直于基線，構成一共極性 (epipolar) 結構，這樣做是為了縮小對應的搜索空間，只有水平方向的視差，簡化了對應過程，如下圖所示。

如上圖所示，設空間一點P(X,Y,Z)在兩個平行放置的完全相同的攝象機中像點分別是(x1,y1).(x2,y2),則在知道基線長B和焦距f的情況下，可以計算出深度

這是雙目立體視覺的基本原理，即根據視差來恢復立體信息。

2.2 匹配基元
匹配基元是指匹配算法的最小匹配對象，它是由特征抽取算法產生的。在建立立體視覺系統時，必須根據環境的特點和應用的領域選擇適當的匹配基元。匹配基元可以是：
(1) 過零點 (zero-crossings),
(2) 邊界與線片段 (edge and line fragments),
(3) 線性特征 (linear features),
(4) 邊緣輪廓 (object boundaries),
(5) 興趣算子抽取的特征點（如角點等）

基元作為匹配算法處理的基本單位，是局部特征，應包含以下一些信息:
(1) 維量（點、線、邊界等） (dimensionality),
(2) 尺度（空間頻度，長短、大小、方向等）(size (spatial frequency)),
(3) 亮度（對比度） (contrast),
(4) 語義量 (semantic content),
(5) 稠密度 (density of occurrence),
(6) 簡單可量度的分布特征 (easily measurable attributes),
(7) 唯一性／突出性 (uniqueness/distinguishability)

2.3 匹配算法
匹配算法就是在兩幅圖象的匹配基元之間建立對應關系的過程，它是雙目立體視覺系統的關鍵。實際上，任何計算機視覺系統中都包含一個作為其核心的匹配算法，因而對于匹配算法的研究是極為重要的。

為了比較全面地考察匹配算法，這里不妨將雙目立體視覺的匹配算法擴展到更一般的情況來分析：假設給定兩幅同一環境的圖象，這兩幅圖象可能由于攝取的時間、方位或方式的不同而有差別，如雙目立體視覺系統所攝取的兩幅圖象、地圖與遙感或航測圖象等，如何找到彼此對應的部分? 對于這個問題，一般有兩種考慮途徑:
(1) 灰度分布的相關性，
(2) 特征分布的相似性。

因而就有兩類算法:
(1) 基于灰度的算法 (intensity based)，
(2) 基于特征的算法 (feature based)。

如果按照控制策略分，有如下幾種:
(1) 粗到精多層次結構 (coarse-to-fine,hierarchical),
(2) 引入約束條件的松馳法 (constraints, relaxation),
(3) 多級表示的決策結構 (multilevel representation)。

2.3.1 基于灰度的匹配算法
基于灰度的算法是指圖象處理中所稱的區域相關方法 (area-correlation technique)，它是解決對應問題的一個最直觀最簡單的方法。在一幅圖象中以一點為中心選定一區域（窗口），在另一幅圖象中尋找與該區域相關系數最大的區域，把該找到的區域的中心認為是原來那區域中心的對應點。這里所說的圖象包括經過某種特殊處理如Gauss濾波后的圖象。

這種算法計算量大，但可以得到整幅圖象的視差圖。該算法對噪音很敏感，考慮到計算量，窗口不宜開得過大，因而可能匹配的選擇較大，誤對應可能性大，不適于灰度分布均勻的圖象，較適于灰度分布很復雜的圖象，如自然景物等。采用該方法的關鍵在于排除或減輕噪音的影響。通常采用多層次相關對應及多幅圖象的統計平均處理方式來實現。如 D. B. Gennery [2]采用九幅圖象多級處理方式來實現對應求解。

2.3.2 基于特征的匹配算法
鑒于灰度區域相關方法的局限性，現在大部分研究集中在這方面。在許多環境（如有線條輪廓特征可尋的人工環境 (man-made structured world)）中，圖象的特征是很有規律地分布的，反映了場景的核心，數量少，處理方便。基于特征的匹配算法特別適用于特殊的比較簡單的環境如室內環境，具有速度快、精度高的特點，但對于自然環境，由于缺少顯著的主導特征，該方法也遇到了很大困難。

基于特征的雙目立體視覺的對應算法，通過建立所選基元的對應關系，旨在獲取一稀疏深度圖，如果需要再經過內插等方法可以得到整幅深度圖。這一類算法因各自采用的匹配基元不同而相異。概括而言，該類匹配算法都是建立在匹配基元之間的相似性度量基礎上的。這種相似性度量被稱為親合性 (affinity)[2]， 它是以匹配基元的各項參數信息為依據的局部特征相似程度的度量。這種度量方法與攝像機模型相結合，可以大大減小匹配時的搜索空間。

由于僅利用親合性建立匹配是模糊的，可能匹配的空間仍舊很大（多對一的），因此有必要引入其它約束條件及控制策略來限制搜索空間，減小模糊程度。匹配算法中常引入的兩種約束條件及控制策略是:
(1) 共極性 (epipolar) （雙目立體視覺模型特點）,
(2) 連續性 (continuity),
(3) 分層次的匹配策略（即由粗到精策略）(hierarchical (e.g.,coarse-fine) matching strategy)。
這種引入約束的方法實際上是將有關環境模型的知識融于算法之中。

這種算法的具體實現，可以采用概率度量、松馳法迭代或者聚類等模式識別算法來實現。作為最后結果的1-1 對應，可以利用啟發式搜索方法從已經大大減小了的搜索空間中獲得。這部分可望能利用現代 AI 研究的許多手段如專家系統等研究方法，作為承上啟下，建立更高層次描述的先導。

可以從以下幾個角度來比較各種匹配算法，
(1) 精度 (accuracy),
(2) 可靠性（排除總體分類誤差的程度）(reliability)，
(3) 通用性（適于不同場景的能力）(available of performance models),
(4) 預見性 (predictability),
(5) 復雜性（設備及計算量的代價）(complexity (cost implementation, computational requirements))。

立體視覺的匹配算法有:
(1) Marr-Poggio-Grimson算法，以過零點為基元，采用由粗到精的控制策略，用精度較低層次的匹配來限定精度較高層次匹配的搜索空間，最后利用連續性約束通過迭代方式實現匹配過程。處理對象是自然景物的雙目立體圖象。

(2) R. Nevatia-G.Medioni算法，以線片段 (segments) 為基元，以最小差別視差 (minimum differential disparity) 為基準，建立匹配過程。該基準實際上是連續性約束的一種表現形式，在對應線片段各自鄰域內存在的對應線片段的視差與其視差相近。處理對象是人工環境的雙目立體圖象。

(3) R. Y. Wong算法，旨在建立兩類圖象的對應關系，如航空照片、遙感圖象與灰度圖象之間的對應關系。以邊界特征(edge feature)為依據采用順序的 (sequential)、多層次結構 (hierarchical structure)的搜索策略實現匹配過程。

(4) K. Price-R. Reddy算法，依據場景的線條特征模型，將自頂向下（人工智能）(top-down (artificial intelligence))與自底向上（模式識別）(bottom-up (pattern recognition)) 兩種控制策略有效地結合起來，采用廣義的相關方法進行匹配，旨在建立形態差別較大的兩幅圖象（一幅是參照圖或參考模型，另一幅是待對應的圖象）的對應關系。如機場模型與機場的航空照片之間的對應關系。

(5) C. S. Clark-A. L. Luck-C. A. McNary算法，抽取線條輪廓特征建立模型，在模型間建立對應。適于存在較大差別的圖象的匹配。

(6) K. E. Price算法，用于在圖象間建立區域對應。該算法利用區域間的相互關系，以松馳法為基本思想實現了多層次表示結構下的匹配過程。突出特點是匹配算法考慮了圖象本身區域間的相互關系（如包含、子部分等）的匹配，具有類似于某種語義網絡式的啟發性。

(7) R. Horaud-T. Skorads算法，以線條特征為匹配基元，每個線條特征不僅含有其本身的端點坐標及方向矢量信息，而且含有它同那些與其相鄰的線條特征之間存在的相對位置及結構關系的信息。這些特征將每幅圖象表示成為一個關系圖，根據該關系圖對于每個線條特征確定它在另一幅圖象中的可能對應集合，以每組對應為一結點構造對應圖，依據關系圖的相容性通過利益函數（benefit function）確定最佳對應。它處理的對象是室內環境的雙目立體圖象。

(8) W. Hoff-N. Ahuja算法，以過零點為最小特征，將特征匹配、輪廓檢測以及表面內插這三個過程結合在一起，采用基于多層表示的由粗到精的控制策略，根據對于表面的光滑性約束重構三維表面。這是一種與傳統方法大不相同的算法，適合于有紋理特征的環境如工作臺上的物品，不適合于稀疏特征環境如室內環境。另外 S. I. Olsen提出的算法與此相似，它將表面的重構過程（reconstruction process）結合在對應匹配過程中，基于多重屬性用松弛法進行匹配，逐步提高重構的視差表面與實際的視差數據的一致性。

2.4 雙目立體視覺系統
雙目立體視覺經過幾十年的研究已經取得了顯著了成果，出現了各種專門的硬件設計和視頻速率（實時）的立體視覺系統，在理論和技術方面都比較成熟了。但是，從普遍的意義來講，由于很難徹底地解決對應點問題，具體的立體視覺系統一般都是有針對性的、不是普遍適用的，還無法與人類的雙目視覺系統相媲美。

下圖是SRI的集成在電路板上的雙目立體視覺系統。CMU設計了Stereo Machine, 可以實時地獲取深度信息。

立體攝象機校準 Stereo Camera Calibration
三維視覺
Milan Sonka, 3D Vision
集成在電路板上的立體攝象機對SRI Stereo Engine, Stereo head onboard
立體幾何模型 SRI Stereo Geometry
雙目立體視覺Introduction to Stereo Imaging -- Theory

3. 結構光方法(Structured Light)

將平面光束照射在物體上可以形成光帶，光帶的偏轉數據反映了物體表面的三維形狀信息，用這種方法可以精確地獲取物體的三維信息。借助于一組平行的平面光，或將物體置于專門的旋轉工作臺上通過一束平面光，都可以利用偏轉數據直接地計算出深度信息，稱這種方法為結構光方法。結構光方法適合于限制條件下，局部范圍內需要精確測量的情況，用于不規則表面的三維建模。

結構光方法在工業上有重要的應用，例如從傳送帶上檢測工件，工件的逆工程（Reverse engineering）；在圖形建模方面也有重要的應用，如人體建模，包括頭部等軀體模型，雕塑造型的數字化。實際上它是三維掃描儀的基本原理。

如下圖所示的裝置，就是結構光方法的典型事例。

詳細可見：Our Active Stereo Vision System

4. 激光雷達與程距數據(Range Data)處理

激光雷達（Laser range finder）與結構光方法不同，它直接利用激光光速掃描物體，通過測量光束從發出到反射回來的時間差來計算深度信息。它提供的數據是深度圖，稱為程距數據（Range data）。激光雷達可以用于比較大范圍的測量，如移動機器人可以用激光雷達信息來建立環境內模型，以實現自主導航、躲避障礙等功能。

程距數據實際上就是深度圖象，結構光方法和激光雷達得到的數據最后都是深度信息。程距數據處理主要是表面擬合，恢復物體的表面結構。

5. 視覺臨場感系統

臨場感（Telepresence）技術是新一代遙操作（Teleoperation）系統的重要組成部分。顧名思義，它的目的就是使人從遠地遙控操作時具有在現場處實地操作式的身臨其境的感覺。在理想情況下，這些感覺應該包括人的各種感官所能感受到的感覺，如視覺、聽覺、觸覺、味覺、體位覺、力感等。

臨場感系統因其面對的任務不同，所需的現場信息有所區別，其中，視覺通常是最重要的信息之一，其次才是聽覺、觸覺等。目前，臨場感技術主要涉及視覺和聽覺。

臨場感遙操作系統的主要優點是：將人與機器人有機地結合起來，能夠恰到好處地發揮出各自的特長。機器代替人去危險或人不可能到達的區域去工作，而人的判斷能力和決策水平又明顯地提高了系統的整體智能水平。

如下圖所示，室外車輛上的立體攝象機將視頻信號傳回基地端，操作員通過立體眼睛觀察環行屏幕，仿佛他親自在車上一樣能夠具有身臨其境的感覺。

（參見：艾海舟、張朋飛、何克忠、江濰、張軍宇，室外移動機器人的視覺臨場感系統，機器人，22（1）：28-32，2000。）

有關立體視覺的前沿工作請參見微軟研究院張正友博士的網頁，他是這方面的著名學者：~zhang/

參考文獻
1.馬松德、張正友，計算機視覺計算理論與算法基礎，科學出版社，1998。
2.艾海舟,關于雙目立體視覺的研究,碩士論文,121頁,1988.4.
3.艾海舟, 關于移動機器人自主式系統的研究, 博士論文, 153頁, 1991.3.

最近一直學習立體視覺，寫了很多的代碼，但是還沒整理具體的算法。使用左右兩張圖片，計算深度圖