【理论恒叨】【立体匹配系列】经典AD-Census: （3）扫描线优化（Scanline Optimization）

下载AD-Census完整源码，点击进入: https://github.com/ethan-li-coding/AD-Census
欢迎同学们在Github项目里讨论，如果觉得博主代码质量不错，右上角star一下！感谢！

AD-Census算法来自于中国学者Xing Mei等在ICCV2011发表的论文《On Building an Accurate Stereo Matching System on Graphics Hardware》¹。算法效率高、效果出色，Intel RealSense D400就是基于该算法实现的立体匹配 ²。

本系列将带大家深入了解AD-Census的理论，希望能够对同学们的立体匹配算法研究有所帮助。

AD-Census是一个将局部算法和半全局算法相结合的算法，它包含四个步骤：1 初始代价计算、2 代价聚合、3 扫描线优化、4 视差优化。本篇的内容是扫描线优化部分。

Step 1. AD-Census Cost Initialization
Step 2. Cross-based Cost Aggregation
Step 3. Scanline Optimization
Step 4. Multi-step Disparity Refinement

【理论恒叨】【立体匹配系列】经典SGM：（3）代价聚合（Cost Aggregation）

SGM的代价聚合就是使用的扫描线优化思路，而AD-Census的扫描线优化思路正是借鉴于SGM，思路具有高度一致性。

We employ a multi-direction scanline optimizer based on Hirschmuller’s semi-global matching method

做扫描线优化的目的是要进一步提高代价的准确性，减少匹配错误。优化思路和SGM的代价聚合思路一模一样（注意SGM的扫描线优化叫代价聚合，而AD-Census就叫扫描线优化，实际上本质是一样的操作，只是叫法不同而已）。优化的方向数为4，分别是左、右、上、下。

像素 $p$ 某一方向$r$的优化公式为：

和SGM的公式一样的，如果大家想了解详细，请查看下面贴出的博客地址，这里就不细说了。

【理论恒叨】【立体匹配系列】经典SGM：（3）代价聚合（Cost Aggregation）

AD-Census所做的修改在于$P_1$和$P_2$值的设定方式，在SGM中，$P_1$、$P_2^{\prime }$是预设的固定值，实际使用的$P_2$是根据左视图相邻两个像素的亮度差值而实时调整的，调整公式为$P_2=P_2^{\prime }/(I_p?I_q)$。

而在Ad-Census中，$P_1$、$P_2$不只是和左视图的相邻像素颜色差$D_1=D_c(p,p?r)$有关，而且和右视图对应同名点的相邻像素颜色差$D_2=D_c(pd,pd?r)$有关。

（注1：AD-Census算法默认输入彩色图，所以是算颜色差，如果是输入灰度图，则是亮度差，颜色差的定义是$D_c(p_l,p)=ma{x}_{i=R,G,B}|I_i(p_l)?I_i(p)|$，即三个颜色分量差值的最大值）
（注2：$pd$ 实际就是像素 $p$ 通过视差 $d$ 找到的右视图上的同名点 $q=p?d$）
（注3：$p?r$代表聚合方向上的上一个像素，比如从左到右聚合，则$p?r$就是$p?1$；从右到左聚合，则$p?r$就是$p+1$）

具体设定规则如下：

1. $P_1={\Pi }_1,P_2={\Pi }_2,if{D}_1<{\tau }_{SO},D_2<{\tau }_{SO}$
2. $P_1={\Pi }_1/4,P_2={\Pi }_2/4,if{D}_1<{\tau }_{SO},D_2>{\tau }_{SO}$
3. $P_1={\Pi }_1/4,P_2={\Pi }_2/4,if{D}_1>{\tau }_{SO},D_2<{\tau }_{SO}$
4. $P_1={\Pi }_1/10,P_2={\Pi }_2/10,if{D}_1>{\tau }_{SO},D_2>{\tau }_{SO}$

${\Pi }_1,{\Pi }_2$是设定的固定阈值，${\tau }_{SO}$是设定的颜色差阈值。

我们首先要搞清楚$P_1$和$P_2$到底是在惩罚什么，在SGM的理论介绍博文中，我说的比较详细，总的来说，它们是在惩罚相邻的像素视差相差很大这种表现，$P_1$惩罚的是相差1个像素，$P_2$惩罚的是相差1个像素以上，而理论依据就是一个假设：颜色相近的像素具有相近的视差值。因此通常会判断两个像素颜色是否相近，如果颜色相近，那么就认为俩像素应该要有相近的视差，如果俩视差相差很大，那么就要给其一个较大的惩罚值，也就是让$P_1$及$P_2$更大些。

上面这段话理清之后，你就能理解为什么SGM要根据亮度的差值来调整$P_2$，也能理解AD-Census的这个规则的含义。它无非就是在SGM的基础上，把情况考虑的更加精细一些，把左右图像的亮度差都考虑进来，会更加鲁棒。我分条给大家做个解读：

1. 规则1的意思是，如果左右图像相邻的像素颜色差都很小，那么这俩像素大概率就是视差相同或相近了，视差差1个像素以上都要被大力度惩罚，所以这里$P_1$和$P_2$是最大的。
2. 规则2的意思是，如果左图像相邻像素颜色差很小，而右视图相邻像素颜色差略大，那么俩像素视差相同或相近的概率较第一种情况稍稍降低，相比第一种情况，减少$P_1$和$P_2$的值。
3. 规则3和规则2是一个意思，左右相反，右图像颜色差小，左图像颜色差略大。$P_1$和$P_2$的值和规则2一样。
4. 规则4的意思是，如果左右图像相邻的像素颜色差都很大，那么这两像素的视差大概率是一定差别的，很可能是视差非连续区，差1个像素以上。所以惩罚力度应该最小，$P_1$和$P_2$此时就是最小的。

最后，4个方向的优化代价，取平均值赋给像素 $p$ ：

本篇的内容就到这里，咱们一篇一个大步骤，不多好消化。下一篇带来的是AD-Census最后一步：视差优化。

博主简介：
Ethan Li 李迎松（知乎：李迎松）
武汉大学 摄影测量与遥感专业博士

主方向立体匹配、三维重建

2019年获测绘科技进步一等奖（省部级）

爱三维，爱分享，爱开源
GitHub： https://github.com/ethan-li-coding
邮箱：ethan.li.whu@gmail.com

个人微信：

欢迎交流！

关注博主不迷路，感谢！
博客主页：https://ethanli.blog.csdn.net