一、SAD算法

1.算法原理
        SAD(Sum of absolute differences)是一种图像匹配算法。基本思想：差的绝对值之和。此算法常用于图像块匹配，将每个像素对应数值之差的绝对值求和，据此评估两个图像块的相似度。该算法快速、但并不精确，通常用于多级处理的初步筛选。

2.基本流程

输入：两幅图像，一幅Left-Image，一幅Right-Image

对左图，依次扫描，选定一个锚点：

（1）构造一个小窗口,类似于卷积核；
（2）用窗口覆盖左边的图像,选择出窗口覆盖区域内的所有像素点；
（3）同样用窗口覆盖右边的图像并选择出覆盖区域的像素点；
（4）左边覆盖区域减去右边覆盖区域，并求出所有像素点灰度差的绝对值之和；
（5）移动右边图像的窗口，重复（3）-（4）的处理（这里有个搜索范围,超过这个范围跳出）；
（6）找到这个范围内SAD值最小的窗口,即找到了左图锚点的最佳匹配的像素块。

3、代码

#include<iostream>
#include<opencv2/opencv.hpp>

using namespace std;
using namespace cv;


class SAD
{
private:
	int winSize;//卷积核尺寸
	int DSR;//视差搜索范围
public:
	SAD() :winSize(7), DSR(30){}
	SAD(int _winSize, int _DSR) :winSize(_winSize), DSR(_DSR){}
	Mat computerSAD(Mat&L, Mat&R);//计算SAD
};

Mat SAD::computerSAD(Mat&L, Mat&R)
{
	int Height = L.rows;
	int Width = L.cols;
	Mat Kernel_L(Size(winSize, winSize), CV_8U, Scalar::all(0));
	//CV_8U:0~255的值，大多数图像/视频的格式，该段设置全0矩阵
	Mat Kernel_R(Size(winSize, winSize), CV_8U, Scalar::all(0));
	Mat Disparity(Height, Width, CV_8U, Scalar(0));


	for (int i = 0; i < Width - winSize; ++i){
		for (int j = 0; j < Height - winSize; ++j){
			Kernel_L = L(Rect(i, j, winSize, winSize));//L为做图像，Kernel为这个范围内的左图
			Mat MM(1, DSR, CV_32F, Scalar(0));//定义匹配范围

			for (int k = 0; k < DSR; ++k){
				int x = i - k;
				if (x >= 0){
					Kernel_R = R(Rect(x, j, winSize, winSize));
					Mat Dif;
					absdiff(Kernel_L, Kernel_R, Dif);
					Scalar ADD = sum(Dif);
					float a = ADD[0];
					MM.at<float>(k) = a;
				}
				Point minLoc;
				minMaxLoc(MM, NULL, NULL, &minLoc, NULL);

				int loc = minLoc.x;
				Disparity.at<char>(j, i) = loc * 16;
			}
			double rate = double(i) / (Width);
			cout << "已完成" << setprecision(2) << rate * 100 << "%" << endl;
		}
	}
	return Disparity;
}

int main()
{
	Mat left = imread("Left.png");
	Mat right = imread("Right.png");
	//-------图像显示-----------
	namedWindow("leftimag");
	imshow("leftimag", left);

	namedWindow("rightimag");
	imshow("rightimag", right);
	//--------由SAD求取视差图-----
	Mat Disparity;

	SAD mySAD(7, 30);
	Disparity = mySAD.computerSAD(left, right);
	//-------结果显示------
	namedWindow("Disparity");
	imshow("Disparity", Disparity);
	//-------收尾------
	waitKey(0);
	return 0;
}

4、结果

左图：

右图：

视差图结果：

二、SGBM算法

1、SGBM算法作为一种全局匹配算法，立体匹配的效果明显好于局部匹配算法，但是同时复杂度上也要远远大于局部匹配算法。算法主要是参考Stereo Processing by Semiglobal Matching and Mutual Information。

opencv中实现的SGBM算法计算匹配代价没有按照原始论文的互信息作为代价，而是按照块匹配的代价。

对该算法的具体讲解可以参考：https://www.cnblogs.com/hrlnw/p/4746170.html。

参考：http://www.opencv.org.cn/forum.php?mod=viewthread&tid=23854。

2、代码

#include<iostream>
#include<opencv2/opencv.hpp>

using namespace std;
using namespace cv;


class SGBM
{
private:
	enum mode_view { LEFT, RIGHT };
	mode_view view;	//输出左视差图or右视差图

public:
	SGBM() {};
	SGBM(mode_view _mode_view) :view(_mode_view) {};
	~SGBM() {};
	Mat computersgbm(Mat &L, Mat &R);	//计算SGBM
};

Mat SGBM::computersgbm(Mat &L, Mat &R)
/*SGBM_matching SGBM算法
*@param Mat &left_image :左图像
*@param Mat &right_image:右图像
*/
{
	Mat disp;

	int numberOfDisparities = ((L.size().width / 8) + 15)&-16;
	Ptr<StereoSGBM> sgbm = StereoSGBM::create(0, 16, 3);
	sgbm->setPreFilterCap(32);

	int SADWindowSize = 5;
	int sgbmWinSize = SADWindowSize > 0 ? SADWindowSize : 3;
	sgbm->setBlockSize(sgbmWinSize);
	int cn = L.channels();

	sgbm->setP1(8 * cn*sgbmWinSize*sgbmWinSize);
	sgbm->setP2(32 * cn*sgbmWinSize*sgbmWinSize);
	sgbm->setMinDisparity(0);
	sgbm->setNumDisparities(numberOfDisparities);
	sgbm->setUniquenessRatio(10);
	sgbm->setSpeckleWindowSize(100);
	sgbm->setSpeckleRange(32);
	sgbm->setDisp12MaxDiff(1);


	Mat left_gray, right_gray;
	cvtColor(L, left_gray, CV_BGR2GRAY);
	cvtColor(R, right_gray, CV_BGR2GRAY);

	view = LEFT;
	if (view == LEFT)	//计算左视差图
	{
		sgbm->compute(left_gray, right_gray, disp);

		disp.convertTo(disp, CV_32F, 1.0 / 16);			//除以16得到真实视差值

		Mat disp8U = Mat(disp.rows, disp.cols, CV_8UC1);
		normalize(disp, disp8U, 0, 255, NORM_MINMAX, CV_8UC1);
		imwrite("results/SGBM.jpg", disp8U);

		return disp8U;
	}
	else if (view == RIGHT)	//计算右视差图
	{
		sgbm->setMinDisparity(-numberOfDisparities);
		sgbm->setNumDisparities(numberOfDisparities);
		sgbm->compute(left_gray, right_gray, disp);

		disp.convertTo(disp, CV_32F, 1.0 / 16);			//除以16得到真实视差值

		Mat disp8U = Mat(disp.rows, disp.cols, CV_8UC1);
		normalize(disp, disp8U, 0, 255, NORM_MINMAX, CV_8UC1);
		imwrite("results/SGBM.jpg", disp8U);

		return disp8U;
	}
	else
	{
		return Mat();
	}
}


int main()
{
	Mat left = imread("Left.png");
	Mat right = imread("Right.png");
	//-------图像显示-----------
	namedWindow("leftimag");
	imshow("leftimag", left);

	namedWindow("rightimag");
	imshow("rightimag", right);
	//--------由SAD求取视差图-----
	Mat Disparity;

	SGBM mySGBM;
	Disparity = mySGBM.computersgbm(left, right);

	//-------结果显示------
	namedWindow("Disparity");
	imshow("Disparity", Disparity);
	//-------收尾------
	waitKey(0);
	return 0;
}

3、结果

所用的左右图同上，所得结果为：

 

 

 

NB：对于使用的其他算法本次没有实验，故没有介绍，可以参考：https://blog.csdn.net/liulina603/article/details/53302168