淡定的CrazyDog的第一篇博客 双目立体匹配SAD算法
今天早上，我收拾好装备，准备去实验室了，结果拎包的时候不小心弄撒了红酒，碎了满地，我当时心里一万头草泥马呼啸而过！！！！！WTF，没办法，只能去找拖把，找了半天，在寝室找到一个断了的拖把，没办法，只能去别的寝室借，可是我拿着别人寝室的拖把拖了没几下，拖把又TM断了，而且还是同一个位置断的！！！！！WTF!!!!我悄悄把别人寝室的拖把放回原处，装作不知道怎么断的样子。回去拿着自己寝室断掉的拖把，拖地，然后趴在地上（我要清理床下的碎屑），一点点清理碎屑和红酒，开窗通风，撒上洗衣粉。在没有暖气的保护下，在饥寒交迫中支撑了1个半小时，三个字（冻成狗！！）终于没有气味了。阿西巴！！一上午没有了，然后Lee给我双目视觉论文我都没看（其实我看不懂），回头我上了CSDN去给自己普及一下双目的知识，不过，这符合我crazydog的一贯风格，在本应该伤心的时候哈哈大笑，我是觉得这件事情本身很好笑
话题扯的太远了，我来写一下今天的收获和心得吧双目匹配中最基础的算法SAD算法。
SAD 算法：SAD算法是一种最简单的匹配算法，用公式表示为：
SAD(u,v) = Sum{|Left(u,v) - Right(u,v)|} 选择最小值
此 种方法就是以左目图像的源匹配点为中心，定义一个窗口D，其大小为（2m+1） (2n+1)，统计其窗口的灰度值的和，然后在右目图像中逐步计算其左右窗口的灰度和的差值，最后搜索到的差值最小的区域的中心像素即为匹配点。
基本流程：
1.构造一个小窗口，类似与卷积核。
2.用窗口覆盖左边的图像，选择出窗口覆盖区域内的所有像素点。
3.同样用窗口覆盖右边的图像并选择出覆盖区域的像素点。
4.左边覆盖区域减去右边覆盖区域，并求出所有像素点差的绝对值的和。
5.移动右边图像的窗口，重复3，4的动作。（这里有个搜索范围，超过这个范围跳出）
6.找到这个范围内SAD值最小的窗口，即找到了左边图像的最佳匹配的像素块。
算法的流程如上面（抄袭自某CSDN博客）：
上面的算法流程其实已经说的很明白了，下面我把这个算法翻译的更加直白一点
第一步：设定一个窗口D对图像进行邻域求和，然后遍历整个图像，这样，我们就得到了两个计算了邻域值的两个矩阵，里面保存了矩阵的灰度值求和
（输入：两个m*n的灰度图像
输出：两个m*n的灰度矩阵，这两个矩阵分别保存了两个图像在D邻域下的灰度和
算法： 用D窗口实现对每一个像素的滚动操作，最终生成矩阵L1和R1
）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
%%滑动窗口计算
[m,n]=size(imgL1);
Dsize=8; %滑动窗口D的size
S=30 ; %最大的视差
dis=0;
N=Dsize/2; %窗口大小的一半
sumL1=zeros(m,n);
sumR1=zeros(m,n);
for i=N+1:m-N
for j=N+1:n-N
sumL1(i,j)= sum(sum(imgL1((i-N):(i+N),(j-N):(j+N)))); %对D窗口内的数值进行求和
sumR1(i,j)= sum(sum(imgR1((i-N):(i+N),(j-N):(j+N))));
end
end
第二步：搜索和匹配，在用L1的矩阵值剪掉R1的矩阵值，并求取绝对值，在视差偏移量最大的范围内通过比较矩阵L1某个值与范围内R1的值，并记录下最小绝对值与偏移量
这里最小的便宜量对应了偏移量就是对应了视差图的灰度值，这样生成视差图矩阵S1
（输入：L1矩阵，R1矩阵
输出：S1矩阵
算法：在视差偏移量允许范围内，找到最佳匹配点，可以等效于求取最小代价函数scale，找到最小的数值点便确定了偏移量
）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
disparity=zeros(m,n);
for i=N+1:m-N
for j=N+1:n-N-S;
SADsum=6666666; scale=0.0; dis=0;
for k=0:1:S
scale=abs(sumL1(i,j)-sumR1(i,j+k));
if(scale
SADsum=scale; %寻找最小的匹配代价函数
dis=k; %记录最小能量的位置
end
end
disparity(i,j)=dis; %保存
end
end
第三步：后期处理和显示
1
2
3
4
5
disparity=disparity*200/S;
dispMap=uint8(disparity);
imshow(dispMap)
实验结果如下：
效果并不是很好嘛，误差这么大的原因分析：（去看了看别人的代码）因为两个图如果直接求和会造成两个图的数值过分大，数值太大一方面会影响运算的速度，另外一方面影响求和的精度，所以建议先实现图像的相减操作，然后再求和，同时保存记录好偏移量，这样数值就不会很大了（下一篇博客，我会写好改进的算法），同时介绍一下这一思想衍生的其他算法
（咳咳，是我理解错了博客的意思，我的锅，我在第二篇博客里面会改正这个错误的，人都会犯错的，求大神轻喷）