分享一份作业：Harris角点检测，RANSAC以及HOG描述符

本次作业包含了Harris角点检测，RANSAC以及HOG描述符，最终将会利用这些工具来完成全景拼接。
当然，你可以通过增加新的内容，例如可以通过SIFT算法来进行特征的检测和描述、利用透视变换来增加对out of plane图像的支持。同时，也鼓励大家自己拍摄照片来实现全景的拼接，这样才能获取额外的分数。
提示：如果你要实现360°的拼接，可能需要把affine变换改为透视变换才能有比较好的结果。求解透视变换时候可能会遇到求解Ax=0的问题，这时候可以参考下DLT算法，即direct linear transform算法。简单而言，就是对矩阵A做一把SVD，找出V中最小的奇异值所对应的特征向量就是其中的一个解（参见PPT）。
除了代码之外，你还需要完成提交一份文档，对你的算法流程以及代码进行原理说明和注释。
本作业中给大家留了几张测试图片供大家参考,不过还是鼓励大家自己拍摄照片来实现算法。
最终的期末成绩会参照你工作的完成情况进行打分。

全景拼接简介
全景拼接技术是计算机视觉的一项早期实践。早在2007年，Matthew Brown 以及 David G. Lowe两人就发表了一篇著名的全景拼接文章panoramic image stitching paper.自那之后，自动全景拼接技术便被广泛地应用开来。这期中包括了Google街景，手机里面的全景模式，以及各类的全景拼接软件（例如Photosynth 以及 AutoStitch）。
在本次作业中，我们将会从多张照片中检测并且匹配关键点，从而构建一张全景图片。这其中包含了以下几个任务：
利用Harris角点检测算子来寻找关键点
建构用于描述每个关键点的算子（descriptor） 比较来自两幅不同图片的两组关键点，并且将它们匹配起来。
给定一组匹配的关键点，利用最小二乘法找到仿射变换矩阵（affine transformation matrix）将一幅图片上的点映射到另一幅图片上。
利用RANSAC算法估计一个更加准确、稳定的仿射变换矩阵。 给定变换矩阵，利用它来变换图片并且拼接到另一幅图片上来，从而形成全景图片。
利用另一组描述算子（HOG）得到另一组拼接结果。
模块 1 Harris 角点检测 (20 points)
模块 1：Harris角点检测算子（20分）
在本节中，你将会利用Harris角点检测算子来定位图片的关键点。Harris角点检测算法包括了如下几个步骤：
利用sobel算子计算图片在 和 方向上的的偏导数(以及 )。
对于每个像素点，计算偏导数的乘积(, 以及)，并用高斯算子进行平滑。
对于每个像素点，计算矩阵M，其中

对于每个像素点，计算角点响应值
先用阈值过滤掉一部分的角点，然后再用非极大值抑制进行细化
输出角点响应的图片
此处的非极大值抑制可以简单地比较下测试像素点与它八邻域的大小关系。如果比它八邻域都大，则保留下来。
如果你正确地计算了Harris角点响应值, 你会发现，在棋盘格的角落以及字体的角点附近会有一些亮点输出。
由于不同人所采用的阈值和窗口大小会有所不同，因此最终输出结果可能存在一定的差异。
例如，一个可能的结果是：

img = imread('sudoku.png');
img = rgb2gray(double(img)/255);
response = harris_corners(img);
imshow(response);
模块 2 关键点的描述及其匹配 (20 points)
我们已经能够利用Harris角点检测算法来定位两张图片中的关键点。接下来我们需要对检测到的关键点进行匹配，确定好两张图片中哪些点是一一对应的。这就需要我们先对关键点进行描述。那如何进行关键点描述呢？一个简单的方法是，选取关键点周围的一个固定区域，并利用该区域的信息生成一组描述向量descriptors.
模块 2.1 生成描述向量
首先，利用前面的代码完成图像特征点的选取（补充完成）：
img1 = imread('uttower1.jpg');
img2 = imread('uttower2.jpg');

你得到的结果可能和下图类似：

然后，你需要完成 describe_keypoints 函数，从而对每个特征点生成对应的描述符。由于用于测试的两张图片并没有发生过多的几何变化，因此我们可以简单地认为它们的scale都相同。所以在进行描述的时候，我们可以简单地在特征点周围框定一个固定大小的window来进行特征点描述(比如，选择一个16*16大小的窗口，从而截出一个patch image)。
由于该实例比较简单，我们也可以直接用像素值来进行来当描述好的向量（即展开成一维向量）。当然，为了增加光照稳定性，我们可以将这个向量进行标准正态化。
%用describe_keypoints函数实现特征点描述算法

Part 2.2 匹配描述子 (10 points)
接着, 完成 match_descriptors 函数并找到两组描述子集合中相匹配的向量。首先，从两张图片中各取一个描述子（也就是关键点生成的向量），计算它们的欧氏距离。利用欧氏距离来判定它们是不是对应的一组描述子: 如果这一对描述子的距离显著小于其他的距离，那么我们认为它们是一组对应的特征点。我们将对应的特征点连接到一起，并将匹配的点连接到一起。
matches = match_descriptors();
你得到的结果可能是类似于下面这种的：

模块 3 转换矩阵的估计 (20 points)
现在，我们已经有一组描述子的对应列表。我们将利用这组对应的像素点计算从图片二映射到图片一的变换矩阵。换句话说，如果图片1中的点 p1=[y1,x1] 与图片2中的点p2=[y2,x2] 相匹配, 我们需要找出一个仿射变换矩阵来进行坐标变换，使得：

其中点 和点 都是点p1和p2的齐次坐标形式.
注意，很有可能矩阵 H 不能使得每一组对应点都完全匹配，但是我们可以利用最小二乘法来进行估计最优的矩阵H. 假设给定了 N 组匹配的特征点, 让 X1 和 X2 为两个 N×3 的矩阵，矩阵的每一行都是对应特征点的齐次坐标（也就是原坐标后面补1）。那么，我们知道矩阵 H 应该满足条件：

完成fit_affine_matrix 函数
-Hint: 如果对于最小二乘法不熟悉的同学可以网上找一下资料
确认了函数 fit_affine_matrix 能够正常运行之后，我们将对实际图片的变换矩阵进行求解。 在这一步之后，图片将会变形，并且图片2将会被映射到图片1的坐标系中。
%计算得到矩阵H，并用它对图片2的坐标进行affine变换
%有时候由于噪声影响，会使得最后一列不是精确的[0, 0, 1]，此时我们可以手动将它置为[0, 0, 1]
你得到的结果可能类似于下面的图像：

现在，我们可以将两幅经过坐标变换的图片拼接成一张。
%将图片二的结果放到图片1的上面
现在拼接的结果还不是很理想，但我们可以利用别的手段来增强这个结果。

模块 4 RANSAC (20 points)
上面直接求解仿射变换矩阵的结果并不是很理想，这是因为在确定对应点时，我们的限制条件并不算精确，导致引入了许多无效数据。我们可以利用 RANSAC ("RANdom SAmple Consensus"，即随机抽样一致) 方法来进一步对数据进行筛选，求解变换矩阵。
RANSAC的主要步骤包括了:

1. 随机选取对应点
2. 计算变换矩阵
3. 在给定的阈值范围内计算有效数据点数(inliers)
4. 重复步骤1-3，记录下最多的有效点数
5. 利用有效的数据点和最小二乘法重新计算变换矩阵
   完成 ransac 函数 , 并重新进行特征点的匹配。你会发现使用RANSAC的结果和直接使用最小二乘法的结果存在差异。

现在，我们可以利用新计算的到的转换矩阵H 来生成一张更稳定的全景图像了。
%生成一张新的全景图
你得到的结果可能类似于下面：

模块 5 梯度方向直方图（Histogram of Oriented Gradients, HOG)
在前面的计算中， 我们利用 simple_descriptor来计算特征点的特征向量。但在这一模块里，我们将会利用HOG来计算特征点的特征。
HOG 指的是梯度方向直方图。在HOG算法中, 我们利用梯度的方向分布来当做特征向量。梯度（x- 和y- 方向）在一幅图片中是很有用的，我们可以利用它的大小来判断点的类型，例如边缘等。
注意：此时patch的大小可以采用16*16的window以方便计算。
HOG的步骤包括:

1. 计算x 和 y 方向的梯度图像
   --sobel滤波器
2. 计算梯度直方图 将图片分成若干个cell，并对每个cell计算梯度直方图 （2*2个cell）
3. 将若干个cell合成一个block，并将里面的梯度直方图转成特征向量 （将4个cell合并成一个block生成特征向量）
4. 将特征向量归一化
   %将特征符描述算子改成HoG算法
   你得到的结果可能类似于下面：

一旦我们使用HOG描述算法完成了对特征点的描述，我们就能通过计算特征点之间的距离完成特征点之间的匹配。随后，我们可以利用RANSAC算法来进一步挑选稳定的匹配对(robust matches)，从而计算出准确的转换方程。
%利用HoG+Ransac完成矩阵H的计算
你得到的结果可能如下图：

更佳的图片融合策略
可以发现，在最终的输出图片里，融合区域存在明显的分界线。这些分界线并不是我们想要的，因此需要把它们去掉，其中有一个非常简单的方法叫做线性融合（linear blending）。
在前面计算融合图片的时候，我们将重合区域的强度值除以了2，其他部分除以1。这其实表示的是左右两张图片的比重相同（equally weighted）。但实际上，重合区域左右两边的比重并不应该相同：靠近左边图片的部分，左边图片的比重应该更大；靠近右边图片的部分，右边图片的比重应该更大。据此，我们可以利用线性融合的方法来提升最终全景图片的质量。
线性融合可以用以下几步进行实现:

1. 确定融合区域的左边界和右边界。
2. 给图片1确定一个权重矩阵: - 从图片1的最左边到融合区域的最左边，weight为1 - 从融合区域的最左边到图片1的最右边，weight从1到0进行分布
3. 给图片2确定一个权重矩阵: - 从融合区域的最右边到图片2的最右边，weight为1 - 从融合区域的最左边到图片1的最右边，weight从0到1进行分布
4. 分别对左右两张图片应用权重矩阵 5. 将两张图相加
   完成 linear_blend 函数，使得最终结果表现得更加自然。
   %利用linear_blend实现亮度的平稳过度
   你最终得到的结果可能如下图：