A*算法_算法导论电子版

《增强现实：原理、算法与应用》读书笔记（4）特征匹配主流算法

主流的特征匹配算法可分为两种，一种是基于特征点周围像素分布相似度的模板匹配，另一种是通过构造合适的描述子进行匹配。

模板匹配

在特征匹配中，模板一般是指特征周围的图像块，而模板匹配是在另一图像的特征中查找与模板图像最为相似的图块。

模板匹配算法的一般流程：
（1）遍历另一图像的所有特征；
（2）将这些图像块与模板图像进行对比；
（3）计算并记录两者的相似度；
（4）得到与模板图像相似度最高的特征。

如何定义相似度是模板匹配准确率的重中之重，一种方法是：

直接采取两个图像块中各个对应位置像素点的平方差之和或相关系数作为两者的相似度。

这种方法比较直观，但是容易受到亮度等因素影响，所以一般需要先进行归一化操作。

另外这种方法需要遍历窗口中的每个像素点，模板越大时，匹配速度越慢，于是有人提出了二次匹配算法：

第一次匹配时取隔行隔列的数据进行粗略匹配；第二次匹配基于第一次匹配的结果，选取相似度较高的窗口进行匹配。

为了进一步加速，Barnea等人(1972）提出序贯相似性检验，在窗口计算过程中，若差异度已经超过给定阈值，则认为该窗口不存在和模板相似的图案，直接跳转到下一窗口。由于大部分窗口和模板不相似，所以多数计算过程都会在中途跳转，从而节省计算时间。

描述子

模板匹配处理物体平移时效果较好，但是当物体发生了旋转或尺度变化时就难以匹配成功。另一方面，用特征或图像块来表示图像信息消耗内存较大。

SIFT描述子

SIFT是一种典型的具有视觉不变性的特征。该方法既能很好的描述局部图像的特点，保证一定的视觉不变性，又能很好地对抗噪声。该方法检测的特征点比较稳定，但其计算复杂度较高。

（1）SIFT特征在高斯金字塔中提取关键点后，会取关键点周围$16\times 16$像素点的窗口，计算每个像素梯度的大小和方向，然后计算特征的主方向；

（2）将坐标轴旋转到主方向后，再将$16\times 16$的窗口分成16个$4\times 4$的小窗口，并把所有方向都离散到8个方向，在每个小窗口上统计8个方向上的梯度加权（越靠近关键点的像素权值越高），这样每个小窗口将会有8个值，从而得到128（16*8）维的特征向量；

（3）最后，对该向量进行归一化处理，去除图像亮度的影响，生成SIFT描述子。

SURF描述子

SURF描述子在SIFT特征的基础上进行了改进，提高了提取和匹配的计算速度。SURF特征生成描述子使用的并不是像素梯度，而是Haar小波特征。

（1）统计固定大小的扇形（60°）内所有像素点的Haar小波特征和，并旋转扇形；
（2）选取Haar小波特征和最大的方向作为特征点的主方向；
（3）计算描述子过程中，SURF特征取一个$20\times 20$的大窗口，并分成16个$5\times 5$的小窗口，对每个窗口统计水平方向和竖直方向的Haar小波特征，得到水平方向值之和、竖直方向值之和、水平方向绝对值之和、竖直方向绝对值之和等共64($16\times 4$)维特征向量。

Haar-like特征

插个话题，这本书之前好像没讲过啥是Haar小波特征，我去查了也没太弄清楚，不过我认为这里说的应该是Haar-like特征。最早的Haar特征在2002年提出，它定义了四个基本结构：

这四个特征分别对应竖直边缘、水平边缘、线、对角线特征，可以理解成一个窗口，这个窗口在整张图像上做步长为1的滑动，遍历整张图像；每次遍历结束后，窗口在长度或宽度上成比例放大，再重复之前遍历的步骤，直到放大到某个极限比例后结束。
进一步的，有扩展Haar特征，将原来的4个特征扩展到了14个，主要增加了旋转性：

Haar特征就是用窗口中黑色矩形所有像素值的和减去白色矩形所有像素值的和，Rainer Lienhart在《An extended set of Haar-like features for rapid object detection》中给出了计算特定图像面积内Haar特征个数的公式：
$$XY\left(W+1-w\frac{X+1}{2}\right)\left(H+1-h\frac{Y+1}{2}\right)$$
其中，$W\times H$是图片大小，$w\times h$是矩形特征大小，$X=\frac{W}{w}$和$Y=\frac{H}{h}$表示矩形特征在水平和竖直方向能放大的最大比例系数。而对于45°的rotated特征，$w,h$表示的含义如下所示：

其计算公式为：
$$XY\left(W+1-z\frac{X+1}{2}\right)\left(H+1-z\frac{Y+1}{2}\right),z=w+h$$

ORB描述子

ORB是一种轻量级的描述子，在BREIF的基础上进行了改进，解决了旋转不变性和噪声敏感的问题。

与BRIEF算法不同的是，为了减少噪声干扰，ORB算法比较的像素点邻域的平均灰度值而不是单像素的灰度值，并且直接由周围像素灰度的质心位置来计算特征主方向以保证描述子的旋转不变性。

相较于SIFT算法，ORB算法比较的是像素点对的大小关系，计算速度快很多，但由于仅采用256位二进制数来描述图像块使得大部分信息被丢失，因此关键在于如何选取具有描述能力的像素点对。

ORB算法的核心就是提出了一种选取关键点对的方法，也就是如何在训练集上离线学习出应该从相对于关键点的哪些位置来挑选像素点对。

对于一个描述能力强的像素点对，其二进制数在不同关键点下的均值应该接近0.5，并且与其他二进制数的相关性低。ORB算法建立了一个包含大量关键点的训练集，对每个关键点，考虑它邻域内的所有像素点对，对于每个点对，首先计算训练集中所有关键点对下该点对的二进制数的均值，根据该均值与0.5差值的绝对值，从小到大依次加入到结果集合，直到结果集合中含有足够多的点对。每个像素点对在加入结果集合前，还要测试其二进制数与结果集合中二进制数的相关性，舍弃相关度过高的二进制数。

这个策略可以很好的避免各个点对之间的相关性，有效强化描述子的描述能力。

BRIEF特征描述符

BRIEF是为了降低SIFT或SURF特征描述子的内存占用而采取的算法：首先平滑图像，然后在特征点周围选取一个Patch，在这个Patch内通过一种选定的方法来选择$n_d$个点对，对于每一个点对$(p,q)$，比较两个点的亮度值，如果$I(p)>I(q)$，则这个点对生成了二值串中一个的值为1，如果$I(p)<I(q)$，则对应的值为$-1$，否则为0。基于此可生成一个$n_d$长的二进制串。

BRIEF仅仅是一种特征描述符，不提供提取特征点的方法，提取特征点还是要靠SIFT、SURF、FAST等。

描述子匹配

描述子特征的匹配通常根据描述子之间的距离进行匹配。类似SIFT等具有多浮点数形式的描述子一般采用的是欧氏距离，而ORB等二进制形式的描述子采取的则是汉明距离。

欧氏距离和汉明距离

欧氏距离也称欧几里得距离，衡量的是多维空间中两个点之间的绝对距离。也可以理解为m维空间中两个点之间的真实距离，或向量的自然长度，其计算公式如下：

$$dist\left(X,Y\right)=\sqrt{\sum _{i=1}^m{\left(x_i-y_i\right)}^2}$$

汉明距离是常见于二进制数计算距离的概念，简单来说，两个码不同的数的个数就是汉明距离，比如码A为10001001，码B为10110001，不同的字符数为3，汉明距离就是3。

我们认为描述子之间距离越小，两个特征越相似，所以特征匹配的一个朴素做法就是，寻找该特征在另一图像的所有特征的最近邻，并设定一个阈值，去除所有最近邻距离大于该阈值的特征对，但该方法很容易受噪声影响。

另一种做法是，剔除最近邻距离和次近邻距离的比值大于一个给定阈值的特征匹配对。也就是，最近邻距离和次近邻距离很接近时，说明两个特征都与该特征能匹配上，则该匹配对的可信度不高。SIFT中采取的就是该种算法。

此外，还可以使用交叉验证的方法来减少误匹配，也就是，两个特征互为最近邻。

当提取的特征点很多时，基于描述子的匹配方法将会十分耗时，一种常见的优化方法是采用k-d树加速特征匹配过程。k-d树的定义很简明，但是不带图讲起来有点复杂，推荐大家自己去搜搜。link.预先构造k-d树能大幅度加速描述子匹配过程。

连续特征跟踪

下面终于讲到AR专门有关的部分了（写到4了都，前面都是基础机器视觉的知识）

AR获取的不是单张图片而是连续的视频流，通常需要连续两帧图像之间进行特征匹配，这个过程也叫作连续特征跟踪。

与普通的特征匹配不同，连续帧之间往往视角变化较小，利用这个特性可以大大提升特征匹配的质量与速度。

一种常见的连续特征点跟踪方法是KLT算法。其主要思想是利用相邻两帧图像中的特征点，通过比较特征点邻域窗口的灰度平方差来求解对应关系。

KLT算法的优势是简单，实时计算速度快，但是需要连续帧之间满足亮度变化小，运动幅度较小且临近像素点的运动相似才能达到较好的匹配效果。

对于利用描述子的特征匹配也可以根据连续帧之间的运动平滑性进行加速，简单的做法是，对于上一帧的每一个特征点，在其邻域窗口内进行特征匹配。在一个SfM系统中，对于已知三维信息的特征点，可以将其投影到下一帧图像中，并且在投影点的邻域窗口内进行匹配。

ENFT算法

描述子匹配在连续跟踪时，如果视角过大，很容易出现特征跟踪丢失，Zhang等人提出了一种ENFT算法，采取基于单应性的特征点跟踪方法来有效缓解特征丢失。

其采用两遍匹配来获取精准的连续帧匹配关系，第一遍基于SIFT特征的普通匹配，通过极线约束去除错误匹配；第二遍则是通过单应性矩阵估计特征点在下一帧出现的位置，并进行透视变换矫正，从而缓解特征点丢失的情况。

ENFT算法的基本思想为：由于特征匹配失败主要是因为两张图像之间的视角变化较大，所以如果能通过图像对齐矫正视角变化，就能有效缓解特征匹配失败的问题。在没有深度信息的情况下，对于单个平面的场景可以采用估计单应性矩阵来对齐图像，因为真实场景中往往存在数个平面，所以ENFT算法提取了多个单应性矩阵，每个单应性矩阵用于对齐一个平面。

具体而言，ENFT算法的匹配过程如下：

（1）第一遍是标准的SIFT匹配，得到的匹配点对为$M=\left\{(x_1^i,x_2^i)|i=1,2,\cdots \right\}$

（2）首先，根据第一遍匹配得到的匹配点对估计出一个内点（inlier）最多的单应性矩阵。

（3）求解出一个单应性矩阵之后，在剩余的匹配中继续估计内点最多的单应性矩阵，重复该步骤直到达到预设的单应性矩阵数目或没有足够多的剩余匹配点为止。估计得到的单应性矩阵集合记为 χ = { H 1 , H 2 , ⋯   } \chi =\left \{ H_1,H_2,\cdots \right \} χ={
H1​,H2​,⋯}

（4）使用这些单应性矩阵大致确定上一帧的特征点在当前帧的位置，还可以进一步矫正由于视角不同导致的透视形变。

（5）除了矫正视角变化外，还可以根据特征匹配点的亮度比例的中值来矫正两帧之间的光照变化。

对于每个$H_k$，使用$H_k$将图像$I_1$对齐到$I_2$，将对齐后的图像标记为$I_1^k$：
$$I_1^k(\pi (H_k\hat{x}))=a{I}_1(x)$$

式中，参数$a$用于矫正光照变化，可以根据如下公式估计：
$$a=\underset{(x_1^i,x_2^i)\in M)}{\mathrm{median}}{I}_2(x_2^i)/I_1(x_1^i)$$

相应的，对于特征点$x_1$将被映射为${\tilde{x}}_1^k=\pi (H_k{\hat{x}}_1)$。寻找它在$I_2$上的匹配点，可以通过求解如下这个目标函数来实现：

$$x_2^k=\underset{x}{\mathrm{argmin}}({\omega }_1\sum _{y\in W(x)}||I_1^k({\tilde{x}}_1^k+y)-I_2(x+y)|{|}^2+{\omega }_2{d}^2(x,F{\hat{x}}_1)+{\omega }_3||{\tilde{x}}_1^k-x|{|}^2)$$

式中，$W(x)$为以$x$为中心的局部图像窗口，然后再选择出一个最佳的单应性矩阵$H_j$：
$$j=\underset{k}{\mathrm{argmin}}(\sum _{y\in W(x)}||I_1^k({\tilde{x}}_1^k+y)-I_2(x_2^k+y)||)$$

那么对于一个特征点$x_1$就得到了它的最佳匹配点$x_2^j$。相较于描述子匹配算法，ENFT算法更有效地利用了全部的局部像素信息，而且比KLT算法在视角变化和光照变化上有更高的容忍度。

此外，为了获得更多的特征点匹配，还可以将关键帧与当前帧之间也进行特征点匹配，从而进一步补充丢失的特征点匹配，提高特征点跟踪的稳定性。

非连续特征匹配

对于SfM系统，除了连续特征跟踪部分，还需要进行非连续帧的特征匹配，评估非连续帧之间的相似性，用以回归定位或视角变化较大时跳跃跟踪。

一种常见的加速方法是利用词袋（bag of words）算法对两帧图像进行相似度的度量，然后只对相似的图像进行匹配，但是该方法比较依赖词袋的结果。

ENFT提出一种使用动态更新匹配矩阵的方法，首先对连续帧匹配得到的特征点轨迹进行聚类，描述子相似的特征点轨迹被归到同一个组里，然后根据聚类结果可以粗略估计出两帧图像之间的相似度；

如果某两个特征点被聚类到同一个组里，假设这两个特征点轨迹所分布的帧集分别为$F_1$和$F_2$，那么对于图像对 { ( i , j ) ∣ i ∈ F 1 , j ∈ F 2 } \left \{ (i,j)|i\in F_1,j\in F_2 \right \} {
(i,j)∣i∈F1​,j∈F2​}之间的相似度都要加1。

根据上述计算可以估计出任意两帧之间的相似度，从而构成一个匹配矩阵，矩阵的第$i$行和第$j$列上的元素代表第$i$帧和第$j$帧的相似度。

因为这里只考虑非连续帧之间的相似度，在计算匹配矩阵的时候会将同一个特征点轨迹内的自匹配排除掉，所以计算得到的匹配矩阵的对角线附件的元素几乎都为0。

为了减少对初始匹配矩阵的依赖，以更好地选出具有重合区域的图像对来进行非连续帧的匹配，ENFT算法会先选择相似度较高的图像进行特征匹配，并根据精确的特征匹配结果来更新匹配矩阵。然后再根据更新的图像相似度，更可靠地选取有公共特征点的图像对进行匹配，不断交替迭代从而实现对非连续帧上的同名特征点的高效匹配。

今天的文章A*算法_算法导论电子版分享到此就结束了，感谢您的阅读。