最近在做雙目視差估計(jì)算法，在OpenCV里有一些算法鹦聪，其中半全局塊匹配（Semi-Global Block Matching澡匪，SGBM）算法具有視差效果好速度快的特點(diǎn)，因此常常被廣泛應(yīng)用拆融。本文主要討論的就是SGBM算法蠢琳。OpenCV的SGBM算法主要參考了《Stereo Processing by Semiglobal Matching and Mutual Information》這篇論文。
1. 計(jì)算每個(gè)像素點(diǎn)的代價(jià)
原論文使用的方法是利用互信息熵镜豹，而OpenCV使用的是Birchfield和Tomasi的方法（參照《Depth Discontinuities by Pixel-to-Pixel Stereo》）傲须。這里我們分別介紹一下。
1.1 利用互信息熵
所謂的熵趟脂，是用來(lái)表示隨機(jī)變量的不確定性泰讽，熵的值越大，信息的不確定性也越大昔期。熵H和互信息MI的定義分別如下：
其中已卸，PI代表某個(gè)點(diǎn)i的概率分布，也就是灰度直方圖為i的點(diǎn)出現(xiàn)的概率硼一；對(duì)應(yīng)地累澡，PI1,I2就是兩個(gè)圖對(duì)應(yīng)點(diǎn)i1和i2的聯(lián)合概率分布，也就是：
Kim等人將上式做了一個(gè)改進(jìn)：利用泰勒展開(kāi)把HI1,I2的計(jì)算轉(zhuǎn)化為求和問(wèn)題（參見(jiàn)論文《Visual Correspondence Using Energy Minimization and Mutual Information》）欠动。
其中圈中帶叉表示卷積運(yùn)算永乌，g(i,k)為高斯卷積核。
相應(yīng)地具伍，邊緣熵以及邊緣概率的計(jì)算如下：
這樣的話，互信息的定義為：
MI匹配代價(jià)CMI為：
其中q是點(diǎn)p在視差為d的情況下的對(duì)應(yīng)校正點(diǎn)圈驼。
原作者使用分層互信息（HMI）進(jìn)行計(jì)算人芽，每一層尺寸減少一半。單次計(jì)算的時(shí)間復(fù)雜度是O(WHD)绩脆，即width×height×disparity range萤厅，所以上次迭代將會(huì)是當(dāng)前迭代速度的1/8橄抹。
這里1/163要乘3的原因是小尺寸的隨機(jī)視差圖不靠譜，需要迭代3次惕味。我們可以看到楼誓，相比于后文的BT方法僅僅慢了14%
1.2 Birchfield和Tomasi的方法（簡(jiǎn)稱BT方法）
對(duì)于一個(gè)匹配序列M，其代價(jià)函數(shù)γ(M)表示匹配結(jié)果不準(zhǔn)確的程度名挥，其值越小越好疟羹。
其中，κocc表示未匹配的懲罰項(xiàng)(constant occlusion penalty)禀倔，κr表示匹配的獎(jiǎng)勵(lì)項(xiàng)榄融，Nocc和Nr分別表示未匹配和匹配的點(diǎn)數(shù)。
2. 損失聚合
我們?yōu)橐暡钤O(shè)置一個(gè)能量函數(shù)E(D)
其中P1和P2分別表示視差差值為1和視差差值大于1的懲罰系數(shù)救湖，一般P1<P2愧杯。添加兩個(gè)正則化項(xiàng)一是為了保持視差圖平滑，二是為了保持邊緣鞋既。我們要做的是找到D使得能量函數(shù)E(D)最小力九，但是不幸的是，在二維圖像的這個(gè)問(wèn)題是一個(gè)NP-完全問(wèn)題邑闺。為了解決這個(gè)問(wèn)題畏邢，原文選擇沿著一圈8個(gè)或者16個(gè)方向進(jìn)行優(yōu)化。
選取使代價(jià)聚合最小的視差值mindS[emb(q,d),d]即可检吆。
3. OpenCV相關(guān)函數(shù)的使用
我們看一下stereoSGBM類的參數(shù)舒萎。
static Ptr<StereoSGBM> cv::StereoSGBM::create (int minDisparity = 0,
int numDisparities = 16,
int blockSize = 3,
int P1 = 0,
int P2 = 0,
int disp12MaxDiff = 0,
int preFilterCap = 0,
int uniquenessRatio = 0,
int speckleWindowSize = 0,
int speckleRange = 0,
int mode = StereoSGBM::MODE_SGBM
)
- minDisparity：最小的視差值。
- numDisparity：視差范圍蹭沛，即最大視差值和最小視差值之差臂寝，必須是16的倍數(shù)。
- blockSize：匹配塊大刑稹（SADWindowSize）咆贬，必須是大于等于1的奇數(shù)，一般為3~11 帚呼。
- P1掏缎，P2：懲罰系數(shù)，一般：P1=8*通道數(shù)*SADWindowSize*SADWindowSize煤杀，P2=4*P1
- disp12MaxDiff ：左右視差圖的最大容許差異（超過(guò)將被清零）眷蜈，默認(rèn)為 -1，即不執(zhí)行左右視差檢查沈自。
- preFilterCap：預(yù)濾波圖像像素的截?cái)嘀底萌濉Ｔ撍惴ㄊ紫扔?jì)算每個(gè)像素的x導(dǎo)數(shù)，并通過(guò)[-preFilterCap枯途，preFilterCap]間隔剪切其值忌怎。結(jié)果值被傳遞給Birchfield-Tomasi像素成本函數(shù)籍滴。
- uniquenessRatio：視差唯一性百分比， 視差窗口范圍內(nèi)最低代價(jià)是次低代價(jià)的(1 + uniquenessRatio/100)倍時(shí)榴啸，最低代價(jià)對(duì)應(yīng)的視差值才是該像素點(diǎn)的視差孽惰，否則該像素點(diǎn)的視差為 0，通常為5~15.
- speckleRange：視差變化閾值鸥印。
- mode：模式
簡(jiǎn)單地試了一下：
#include "stdafx.h"
#include <opencv2\core\core.hpp>
#include <opencv2\highgui\highgui.hpp>
#include <opencv2\imgproc\imgproc.hpp>
#include <opencv2\calib3d\calib3d.hpp>
#include <iostream>
using namespace cv;
int main(int argc, char** argv) {
//讀入圖像勋功。
Mat left = cv::imread("left.png");
Mat right = cv::imread("right.png");
if (left.empty() || right.empty()) {
std::cout << "could not load image...\n";
return -1;
}
//圖像轉(zhuǎn)灰度
cv::cvtColor(left, left, CV_BGR2GRAY);
cv::cvtColor(right, right, CV_BGR2GRAY);
//設(shè)置參數(shù)
int numberOfDisparities = 48, SADWindowSize = 11;
int uniquenessRatio = 15, speckleWindowSize = 50, speckleRange = 32;
cv::Ptr<cv::StereoSGBM> sgbm = cv::StereoSGBM::create(0, numberOfDisparities, SADWindowSize);
int cn = left.channels();
sgbm->setP1(8 * cn * SADWindowSize * SADWindowSize);
sgbm->setP2(32 * cn * SADWindowSize * SADWindowSize);
sgbm->setPreFilterCap(63);
sgbm->setUniquenessRatio(uniquenessRatio);
sgbm->setSpeckleWindowSize(speckleWindowSize);
sgbm->setSpeckleRange(speckleRange);
sgbm->setDisp12MaxDiff(1);
//計(jì)算并顯示視差
Mat disp;
sgbm->compute(left, right, disp);
disp.convertTo(disp, CV_8U, 255 / (numberOfDisparities*16.)); //將16位符號(hào)整形的視差矩陣轉(zhuǎn)換為8位無(wú)符號(hào)整形矩陣
cv::imshow("disparity", disp);
cv::waitKey();
return 0;
}
參考資料
- Heiko Hirschmuller “Stereo Processing by Semiglobal
Matching and Mutual Information ”[M]．IEEE，2005 - S. Birchfield and C. Tomasi, “Depth Discontinuities by Pixel-toPixel Stereo,” Proc. Sixth IEEE Int’l Conf. Computer Vision, pp. 1073-
1080, Jan. 1998. - cv::StereoSGBM Class Reference
- OpenCV學(xué)習(xí)筆記（18）雙目測(cè)距與三維重建的OpenCV（三）立體匹配與視差計(jì)算
- Stereo Matching文獻(xiàn)筆記之（九）：經(jīng)典算法Semi-Global Matching（SGM）之神奇的HMI代價(jià)計(jì)算~
- Stereo Matching文獻(xiàn)筆記之（十）：經(jīng)典算法Semi-Global Matching（SGM）之碉堡的動(dòng)態(tài)規(guī)劃~
- Semi-Global Matching（SGM）算法原文理解
