基于OpenCV的雙目立體匹配方法

孫道輝　孫麗君　陳天飛

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

關(guān)鍵詞：計(jì)算機(jī)視覺；雙目立體匹配； OpenCV；匹配誤差；時(shí)間復(fù)雜度

DOIDOI：10.11907/rjdk.181985

中圖分類號(hào)：TP312

文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)文章編號(hào)：16727800（2018）009009203

英文標(biāo)題Binocular Stereo Matching Approach Based on OpenCV

——副標(biāo)題

英文作者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.

英文關(guān)鍵詞Key Words：computer vision；binocular stereo matching；OpenCV；matching error；temporal complexity

0引言

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

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

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

1雙目立體視覺模型

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

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

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

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

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

d=Pl-Pr=BfZ（2）

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

2立體匹配算法

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

2.1基于局部的匹配算法

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

灰度差的絕對(duì)值和（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）

歸一化交叉相關(guān)（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]是將對(duì)應(yīng)點(diǎn)的匹配問題轉(zhuǎn)化為尋找某一能量函數(shù)的全局最優(yōu)問題，能量函數(shù)由數(shù)據(jù)項(xiàng)和平滑項(xiàng)組成，見公式（6）。基于全局的匹配算法包括：動(dòng)態(tài)規(guī)劃算法[1213]（Dynamic Programming， DP）、圖割算法[14]（Graph Cuts， GC）、置信傳播算法[15]（Belief Propagation， BP）及群智能算法，如遺傳算法、神經(jīng)網(wǎng)絡(luò)算法、協(xié)作算法[16]等。

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

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

2.3基于半全局的匹配算法

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

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

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

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

3實(shí)驗(yàn)結(jié)果與分析

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

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

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

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

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

4結(jié)語

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

參考文獻(xiàn)參考文獻(xiàn)：

[1]馬頌德，張正友.計(jì)算機(jī)視覺—計(jì)算理論與算法基礎(chǔ)[M].北京：科學(xué)出版社，1997.