孫道輝　孫麗君　陳天飛

摘要：雙目立體匹配是三維重建、多視點視頻編碼、目標跟蹤等研究領域的研究熱點。首先介紹平行相機模型，分析歸納雙目立體匹配原理、規(guī)律及一般步驟，然后對現(xiàn)有經(jīng)典立體匹配算法進行分類，并對不同類型的算法進行剖析，最后基于OpenCV實現(xiàn)10種典型的雙目立體匹配算法，在匹配誤差和時間復雜度上進行比較，分析相關算法優(yōu)缺點，總結立體匹配算法未來研究方向。

關鍵詞：計算機視覺；雙目立體匹配； OpenCV；匹配誤差；時間復雜度

DOIDOI：10.11907/rjdk.181985

中圖分類號：TP312

文獻標識碼：A文章編號文章編號：16727800（2018）009009203

英文標題Binocular Stereo Matching Approach Based on OpenCV

——副標題

英文作者SUN Daohui，SUN Lijun，CHEN Tianfei

英文作者單位（School of Electrical Engineering， Henan University of Technology， Zhengzhou 450001， China）

英文摘要Abstract：Binocular stereo matching is a hot topic in the 3D reconstruction research， multi-view video coding， and target tracking. Firstly， the parallel camera model is introduced， and the principle， law and general steps of binocular stereo matching are summarized. Then the existing classical stereo matching algorithms are classified， and different types of algorithms are analyzed. Finally， based on OpenCV， 10 algorithms are implemented. A typical binocular stereo matching algorithm is compared in the matching error and time complexity. The advantages and disadvantages of the related algorithms are analyzed， and the further research directions of the stereo matching algorithm are summarized.

英文關鍵詞Key Words：computer vision；binocular stereo matching；OpenCV；matching error；temporal complexity

0引言

人類對周圍信息約80%是通過視覺感知得到的[1]。隨著數(shù)字技術和機器人技術的發(fā)展，迫切需要計算機和機器人具有圖像獲取、圖像處理及視覺理解能力。20世紀四五十年代，以計算機視覺的方法進行二維圖像處理與研究為計算機視覺理論的發(fā)展奠定了基礎。20世紀60年代Roberts[2]使用積木世界理論開創(chuàng)了以三維場景計算為目的的實驗研究。1982年Marr提出計算機視覺理論，詳細介紹了視覺計算理論與方法，論述了計算機視覺的主要研究內容是使計算機具有從二維圖像認知三維環(huán)境信息的能力，目的是利用二維信息實現(xiàn)三維重建，標志計算機視覺成為一門新的學科。立體匹配是計算機視覺的一個重要領域和方向，其基本原理是從兩個視點中觀察同一場景以獲取立體圖像對，匹配對應點像素，計算出視差圖及對應深度[3]。

由于雙目立體匹配是二維平面圖像恢復三維深度信息的逆問題，存在很多影響恢復深度信息的不確定因素。目前國內外對雙目立體匹配積累了大量研究，Barnard[4]介紹了立體匹配原理及主要立體匹配算法，并制定了算法性能評價標準，后續(xù)算法大都采用該標準。Scharstein等[5]提出對雙目圖像產(chǎn)生稠密視差的立體匹配算法分類，提供了算法測試實驗平臺及算法性能評估方法，為立體匹配研究創(chuàng)造了良好的條件。大連理工大學白明等[6]對當前雙目立體匹配算法進行了歸納總結，分析了立體匹配存在的難題，并論述了可能的解決方案。南京理工大學郭龍源等[7]在理論研究基礎上對計算機視覺與立體匹配算法進行了試驗驗證。但是面對立體匹配的病態(tài)問題，國內外還沒有統(tǒng)一、高性能的解決算法。

立體匹配是計算機視覺的一個重要領域和方向，其基本原理是從兩個視點中觀察同一場景獲取立體圖像對，匹配對應點的像素，計算出視差圖以及對應深度[8]。通過雙目攝像頭獲取立體匹配圖像對，實現(xiàn)基于OpenCV的雙目立體匹配算法，對雙目立體匹配技術具有重要意義。

1雙目立體視覺模型

在雙目視覺中，因視向不同，左眼看到物體左邊物點，右眼看到物體右邊物點，同一物體在在兩個視網(wǎng)膜上得到不同的兩個視像，兩者之差稱為視差[9]。雙目立體匹配原理即通過對人眼成像的模擬進而獲取深度信息。

根據(jù)人眼成像獲得視差與深度信息的原理，雙目立體匹配通常采用平行相機模型，原理示意如圖1所示。

根據(jù)三角形相似原理，可以得到：

PlB2+x=fZPrB2-x=fZ （1）

通過公式（1）可以得到視差：

d=Pl-Pr=BfZ（2）

其中d為視差，Pl、Pr分別為空間中物體在左右投影平面上的點，B為基線即兩攝像機光心之間的距離，f為攝像機焦距，x為空間點P的橫坐標。

2立體匹配算法

根據(jù)立體匹配的幾何約束和場景約束，匹配算法可以分為基于局部、全局、半全局的匹配算法。

2.1基于局部的匹配算法

基于局部的匹配方法分為基于區(qū)域、基于特征、基于相位3類[10]。基于區(qū)域的匹配算法按照一定的相似度測度函數(shù)進行局部代價聚合計算?；谔卣鞯钠ヅ渌惴ㄍǔ２捎脠D像特征點、線等匹配基元進行特征匹配?；谙辔坏钠ヅ渌惴ㄊ菍D像空域信息經(jīng)過傅里葉平移變換后的頻域相位信息進行處理、計算出視差。在實際工程精度要求不高的場合中，通常采用基于區(qū)域的匹配算法進行硬件實現(xiàn)。公式（3）-（5）列出了3種常見的相似度測量函數(shù)。Il和Ir分別為參考圖和匹配圖，d為視差搜索范圍，S為匹配區(qū)域。

灰度差的絕對值和（Sum of Absolute Differences，SAD）：

C（x，y，d）=∑x∈S|Il（x，y）-Ir（x+d，y）|（3）

灰度差的平方和（Sum of Squared Differences，SSD）：

C（x，y，d）=∑x∈S（Il（x，y）-Ir（x+d，y））2（4）

歸一化交叉相關（Normalized Cross Correlation，NCC）：

C（x，y，d）=∑x∈S（Il（x，y）-l）·（r（x，y）-r）∑x∈SIl（x，y）2·∑x∈SIr（x+d，y）2（5）

2.2基于全局的匹配算法

基于全局的匹配算法[11]是將對應點的匹配問題轉化為尋找某一能量函數(shù)的全局最優(yōu)問題，能量函數(shù)由數(shù)據(jù)項和平滑項組成，見公式（6）?；谌值钠ヅ渌惴òǎ簞討B(tài)規(guī)劃算法[1213]（Dynamic Programming， DP）、圖割算法[14]（Graph Cuts， GC）、置信傳播算法[15]（Belief Propagation， BP）及群智能算法，如遺傳算法、神經(jīng)網(wǎng)絡算法、協(xié)作算法[16]等。

E（d）=Edata（d）+λEsmooth（d）（6）

其中，E表示能量函數(shù)，Edata是數(shù)據(jù)項，Esmooth是平滑項，λ是懲罰因子，d為視差。全局匹配算法在能量E最小的情況下求得視差d。

2.3基于半全局的匹配算法

局部匹配算法快速簡單，但是得到的視差圖粗糙，易造成匹配且對噪聲敏感；全局匹配算法精度高，計算復雜。半全局匹配算法[1718]（Semiglobal Matching，SGBM）試圖結合二者的優(yōu)點，使算法性能在視差精度和計算復雜度上達到一個折中的、可接受的效果，其基本思想是利用多個一維搜索路徑的局部尋優(yōu)過程，近似二維圖像的全局尋優(yōu)過程。半全局是在全局能量函數(shù)基礎上加入額外的平滑約束[19]，見公式（7）。

E（d）=∑pC（p，dp）+∑q∈NpP1T[|dp-dq|=1]+

∑q∈NpP2T[|dp-dq|>1]（7）

式中，右側第一項為基于視差d的所有像素匹配代價和，表示數(shù)據(jù)項；后兩項為平滑項，P1、P2為像素點p在鄰域Np的懲罰系數(shù)。

3實驗結果與分析

實驗使用Microsoft Visual Studio 2010軟件調用OpenCV，采用C++語言編程實現(xiàn)基于SAD、SSD、ZSSD、NCC、Census變換的區(qū)域匹配算法、半全局SGBM算法及基于全局的的DP、GC算法。測試圖像采用Middlebury大學提供的測試集中的Tsukuba圖像。圖2為實驗所用的兩幅雙目立體匹配測試灰度圖像以及參考視差。

從視覺效果上看，GC算法視差圖清晰、準確，效果最佳，5種區(qū)域匹配算法的視差圖都有殘缺破損、不完整的情況，DP算法視差圖像出現(xiàn)了垂直方向的模糊條紋，半全局算法視差圖像效果不及GC算法，但是明顯好于區(qū)域匹配算法。

根據(jù)算法運行時間，比較各算法計算深度圖的快慢，進行定量分析，從參考視差圖對比計算的總誤匹配像素比和計算時間兩方面比較各算法性能，見表1和表2。

從表1可看出，BM算法運行速度快，但總誤匹配像素比最大。GC算法總誤匹配像素比非常小，與真實視差圖幾乎相同，但計算復雜度太高，難以在實際硬件中實現(xiàn)。SGBM在算法時間、復雜度和計算結果精度方面處于折中，為立體匹配提供了新的算法思想。

表2數(shù)據(jù)表明，基于局部的立體匹配算法總誤匹配像素比相近，該類算法有較多誤匹配像素，總誤匹配像素較高，在算法運行時間上Census變換算法最快。另外，與OpenCV自封裝算法相比，調用OpenCV庫函數(shù)實現(xiàn)的算法運行時間更長。

4結語

立體匹配是計算機視覺領域中的難點。本文首先利用攝像機成像原理，分析了雙目立體匹配的平行相機模型，推導出深度值與攝像機參數(shù)之間的數(shù)學關系；然后介紹了開源計算機視覺庫OpenCV接口及其功能，并重點介紹了視覺模塊；最后利用OpenCV實現(xiàn)了經(jīng)典立體匹配算法，并對算法性能進行分析比較，指出了各類算法優(yōu)缺點，對雙目立體匹配在實際應用以及算法理論的進一步研究具有重要意義。

參考文獻參考文獻：

[1]馬頌德，張正友.計算機視覺—計算理論與算法基礎[M].北京：科學出版社，1997.