计算机视觉方向简介 | 半全局匹配SGM
点击上方“小白学视觉”，选择加"星标"或“置顶”
重磅干货，第一时间送达
前言
目标读者：对密集匹配，三维重建等有基本概念并感兴趣的人群。 文章及代码资源：
导读：
SGM虽然名字上称为半全局匹配，但实际上还是采用的全局匹配算法中最优化能量函数的思想，即寻找每个像素的最优视差来使得整张影像的全局能量函数最小，下式为SGM所采用的能量函数：
struct path {
short rowDiff;
short colDiff;
short index;
};
在视差计算之前，首先需要定义大小为W×H×D（W为影像宽度，H为影像高度，D则为事先给定的视差范围）的三维矩阵C来存储每个像素在视差范围内每个视差下的匹配代价值。矩阵C通常称为DSI（Disparity Space Image），这个长方块也是我们常说的视差空间。下图为DSI的示意图：
感性上来讲，SGM能够扬名的一个很重要的点就是它将一个NP的全局优化问题简化成了一个多方向的代价问题，即用多个一维路径代价聚合的方式来近似二维的最优。虽然还是在全局的框架下，但是整体的计算效率已相较于全局算法有了很大提升。
for (int row = 0; row < rows; ++row)
{
for (int col = 0; col < cols; ++col)
{
for (unsigned int path = 0; path < firstScanPaths.size(); ++path)
{
for (int d = 0; d < disparityRange; ++d)
{
S[row][col][d] += aggregateCost(row, col, d, firstScanPaths[path], rows, cols, disparityRange, C, A[path]);
}
}
}
lastProgressPrinted = printProgress(row, rows - 1, lastProgressPrinted);
}
aggregateCost(row, col, d, firstScanPaths[path], rows, cols, disparityRange, C, A[path])。输入的参数中（row，col，d）相当于确定了视差空间中三维点的位置，firstScanPaths[path]则确定了是哪条路径，或者可以更直观的理解为是像素领域内哪个相邻像素，（rows，cols，disparityRange）则确定了视差空间的范围，C为上一步代价计算得到的三维代价矩阵，最后的A[path]也是一个三维矩阵，用来存储对应方向的聚集代价，返回值则是A[row][col][d]。以下为该函数的实现：unsigned short aggregateCost(int row, int col, int d, path &p, int rows, int cols, int disparityRange, unsigned short ***C, unsigned short ***A)
{
unsigned short aggregatedCost = 0;
aggregatedCost += C[row][col][d]; //像素匹配的 cost 值
// 1. 边界条件，直接为C
if (row + p.rowDiff < 0 || row + p.rowDiff >= rows || col + p.colDiff < 0 || col + p.colDiff >= cols)
{
A[row][col][d] += aggregatedCost;
return A[row][col][d];
}
// 2. 若未超出边界 ，则进行相应方向的代价聚合
unsigned short minPrev, minPrevOther, prev, prevPlus, prevMinus;
prev = minPrev = minPrevOther = prevPlus = prevMinus = MAX_SHORT;
//设置初始代价为最大值
//minPrev: 对应路径的视差代价最小值
// 对于该路径方向上，上一个像素，在其视差范围内进行循环
for (int disp = 0; disp < disparityRange; ++disp)
{
unsigned short tmp = A[row + p.rowDiff][col + p.colDiff][disp];
//找到这个路径下，前一个像素取不同视差值时最小的A，即为最后减去的那一项，minPrev
if(minPrev > tmp){minPrev = tmp;}
//前一个像素视差取值为d时，即和当前像素的视差相等时，最小的A.
if(disp == d)
{ prev = tmp;}
//前一个像素视差取值为d+1时，即和当前像素的视差相差1时，最小的A，最后将加惩罚系数P1.
else if(disp == d + 1)
{ prevPlus = tmp;}
//前一个像素视差取值为d-1时，即和当前像素的视差相差1时，最小的A，最后将加惩罚系数P1.
else if (disp == d - 1)
{ prevMinus = tmp;}
//前一个像素视差与当前像素的视差相差大于等于2时，最小的A，最后将加惩罚系数P2.
else
{ minPrevOther = tmp;}
}
/* 计算四种情况下的代价最小值 */
aggregatedCost += std::min(std::min((int)prevPlus + SMALL_PENALTY, (int)prevMinus + SMALL_PENALTY), std::min((int)prev, (int)minPrevOther + LARGE_PENALTY));
aggregatedCost -= minPrev; //避免值过大,减小内存
A[row][col][d] += aggregatedCost;
return A[row][col][d];
}
视差计算步骤其实非常简单，通常直接利用赢家通吃（WTA）算法，即选择某一个像素在所有视差值中最小的那一个即可，这也间接说明上一步，也即代价聚集步骤后所得到的视差空间中的代价值需要非常准确，那将直接决定算法的准确度。视差优化则是对计算得到的视差图进行进一步的优化，包括剔除粗差，亚像素插值，平滑等等。比如经常使用的左右一致性检查，可用来剔除遮挡点所产生的错误匹配，对视差图的改进比较大，有时候甚至可以成为许多算法的“遮羞布”。亚像素插值是对WTA得到的整像素进行精化，通常使用二次曲线拟合来获得子像素的视差。平滑则是使用一些平滑算子对视差图进行平滑处理。
本文简要介绍了SGM的思想，并辅以部分代码以助于理解。近年来深度学习大热，SGM与深度学习的结合逐渐成为趋势，网盘中所提供的文章与开源代码可供读者参考，若有错漏，欢迎批评与不吝赐教。
交流群
欢迎加入公众号读者群一起和同行交流，目前有SLAM、三维视觉、传感器、自动驾驶、计算摄影、检测、分割、识别、医学影像、GAN、算法竞赛等微信群（以后会逐渐细分），请扫描下面微信号加群，备注：”昵称+学校/公司+研究方向“，例如：”张三 + 上海交大 + 视觉SLAM“。请按照格式备注，否则不予通过。添加成功后会根据研究方向邀请进入相关微信群。请勿在群内发送广告，否则会请出群，谢谢理解~
评论