特征匹配已广泛应用于计算机视觉和模式识别等诸多领域，常用方法是将其分为两阶段：
第一阶段，显著的明显的特征，即从每幅图像中提取关键点及其局部描述子（descriptor），基于描述子的相似度约束建立一组假定的特征对应。
第二阶段，通过额外的局部或全局几何约束来排除错误匹配或异常值。
手工特征匹配
两阶段特征匹配流水线的第一步是建立一组初始对应关系。经典方法包括scale invariant feature transform (SIFT)、speed up robust features (SURF)、oriented FAST and rotated BRIEF (ORB)。这些经典的特征匹配器在效率和鲁棒性方面都表现出了良好的性能，并被广泛应用于各个领域。
SIFT(1999)
检测兴趣点
SIFT框架首先需要检测兴趣点，称为：keypoints。利用高斯滤波器对图像进行不同尺度的卷积，然后获取连续高斯模糊图像的差分（图像差分：把两幅图像的对应像素值相减，以削弱图像的相似部分，突出显示图像的变化部分）。在多个尺度在高斯差分（Difference of Gaussians, DoG）的最大/最小值取为Keypoints。具体的，一个DoG图$D(x,y,\sigma)$定义为： $$ D(x,y,\sigma)= L(x,y,k_i\sigma)-L(x,y,k_j\sigma) $$ 此处的$L(x,y,k\sigma)$指的是原始图像$I(x,y)$经过尺度为$k\sigma$的高斯模糊$G(x,y,k\sigma)$卷积过的结果。即： $$ L(x,y,k\sigma)=G(x,y,k\sigma)*I(x,y) $$
也就是说一个在尺度$k_i\sigma,k_j\sigma$间的DoG图就是在尺度$k_i\sigma,k_j\sigma$间高斯模糊图像的差分。
获取DoG图后，将DoG图像中的每个像素与同一尺度下的8个相邻像素以及每个相邻尺度下的9个对应相邻像素进行比较，如果该像素值是所有比较像素中最大或最小的，则将其作为候选关键点。
舍弃不必要的点
仅使用上面的方法会产生太多的候选关键点如下图所示，而且其中一些是不稳定的。算法的下一步是对附近的数据进行细节拟合，以获得精确位置、尺度和主曲率比值（ratio of principal curvatures），这种方式排除了低对比度(因此对噪声敏感)或沿边缘局部较差的点。
首先，对每个候选keypoints，利用附近数据的插值来精确确定其位置。插值计算使用二项式泰勒展开式在差值高斯尺度空间函数（Difference-of-Gaussian scale-space function）上，即$D(x,y,\sigma)$，以候选keypoint为原点。泰勒展开式为： $$ D(x)=D+\frac{\partial D^T}{\partial x}x+\frac{1}{2}x^T\frac{\partial ^2 D}{\partial x^2}x $$
其中，$D$及其导数在候选keypoint处计算，$x=(x,y,\sigma)^T$表示该点的偏移量。
为了剔除对比度低的keypoints，对二阶泰勒展开$D(x)$在偏移$\hat{x}$的值进行了计算，若小于0.03则抛弃该点。
DoG函数沿着边缘会有很强的响应，导致候选关键点对少量噪声没有鲁棒性。因此，为了增加鲁棒性需要消除那些位置不确定但边缘响应高的关键点。对于DoG函数中定义较差的峰，沿边缘的主曲率将比沿边缘的主曲率大得多，找到这些主曲率等于求解二阶Hessian矩阵$H$的特征值：
$$ H=\left[ \begin{matrix} D{xx}&D{xy}\ D{xy}& D{yy} \end{matrix} \right] $$
$H$的特征值与$D$的主曲率成正比，$R=Tr(H)^2/Det(H)$，两个特征值的绝对差越大，相当于$D$的两个主曲率的绝对差越大，$R$的值越大。对于阈值特征值比$r{th}$，一个keypoint的$R$若大于$(r{th}+1)^2/r_{th}$，该点被认为是位置不确定的点并剔除。
为关键点标定方向
在此步骤中，每个关键点根据局部图像的梯度方向分配一个或多个方向。这是实现旋转不变性的关键步骤，因为关键点描述器可以相对于这个方向表示，实现图像旋转不变性。
对于高斯模糊图像$L(x,y,\sigma)$，keypoint的尺度$\sigma$使所有计算都以尺度不变的方式执行。对于一个图像样本$L(x,y)$在尺度$\sigma$上，梯度梯度幅值（gradient magnitude ：梯度幅值是描述标量场局部变化率的标量）$m(x,y)$和方向$\theta(x,y)$，使用像素差值预先计算： $$ m(x,y)=\sqrt{(L(x+1,y)-L(x-1,y)^2+L(x,y+1)-L(x,y-1))^2} \ \theta(x,y)=atan2(L(x,y+1)-L(x,y-1),L(x+1,y)-L(x-1,y)) $$
对高斯模糊图像l中关键点附近区域的每个像素进行梯度大小和方向计算，形成36个bin的方向直方图，每个bin覆盖10度。
缺点
SIFT算法的缺点
SURF
SIFT算法的速度较慢，SURF是其加速版。
SIFT中使用高斯差分寻找尺度空间来近似拉普拉斯算子（Laplacian of Gaussian,LoG），SURF使用积分图像的概念按照积分图，图像与高斯二阶微分模板的滤波转换为了对积分图像的加减运算，降低特征点检测搜索时间。图像点的二阶微分Hessian矩阵的行列式（determinant of Hessian,DoH），可用于图像斑点检测（斑点检测意义和原理）
SURF的介绍
ORB
ORB是oriented FAST and rotated BRIEF的简称，ORB的诞生主要是因为SIFT和SURF当时是专利算法。而ORB是免费使用的。在特征检测方面，ORB的表现与SIFT一样好(优于SURF)，而且几乎快了两个数量级，ORB基于FAST关键点检测器和BRIEF描述器。
FAST（feature from accelerated segment test）关键点检测
选择图像中的一个像素$p$，确定其是否为兴趣点，其强度为$Ip$。
选择合适的阈值$t$
考虑一个围绕被测试像素的16像素的圆。（这是一个半径为3的Bresenham Circle）
若圆上$n$个连续像素（此处的n=16）的值都亮于或都暗于$Ip+t$，像素$p$则被认为是一个角点。
为了让算法更快，首先对于圆上的1、5、9、13个像素，从上图中可以明显看出，这四个像素中至少有三个应该满足阈值标准，这样才可能存在兴趣点。
重复上述步骤直到算法完成。
然而FAST特征没有方向组件和多尺度特征，ORB算法使用多尺度图像金字塔，图像金字塔是单一图像的多尺度表示，它由图像序列组成，所有这些图像都是不同分辨率的图像版本。金字塔中的每一层都包含比前一层低采样的图像。通过检测每一层的关键点，ORB算法可以有效地定位不同尺度的关键点，从而就具有局部尺度不变性。
定位关键点后需要给每个关键点分配一个方向，比如朝左还是朝右，这取决于关键点周围强度的变化程度。为了检测强度变化，ORB算法使用强度中心，强度中心假设一个角点的强度从它的中心偏移，该向量可以用来估算方向。定义一个patch的moments为： $$ m{pq}=\sum{x,y}x^py^PI(x,y) $$
有了这些moments，我们就可以找到patch的center of mass，即
$$ C=(\frac{m{10}}{m{00}},\frac{m{01}}{m{00}}) $$
我们可以构造一个从角的中心$O$到质心(center of mass)$-OC$的向量，则该patch的方向定义为: $$ \theta=atan2(m{01},m{10}) $$
$atan=tan^{-1}$，下图为一个方向计算的例子：
一旦我们计算出patch的方向，我们就可以将其旋转到正则旋转，然后计算描述器，从而得到一定的旋转不变性。
# Brief(Binary robust independent elementary feature)
Brief采通过FAST算法找到的所有关键点，并将其转换为二进制特征向量，从而共同表示一个对象。二进制特征向量又称二进制特征描述器，是只包含1和0的特征向量。简单地说，每个关键点由一个128-512位字符串组成的特征向量来描述。
首先，使用高斯核平滑图像，以防止描述器对高频噪声敏感。在像素周围定义的邻域称为patch，它是某个像素的宽度和高度的正方形。随机对中的第一个像素来自于一个以关键点为中心的高斯分布，该分布的偏差和范围同Sigma一致。随机对中的第二个像素来自于以第一个像素为中心的高斯分布，其标准差或标准差为2。现在，如果第一个像素比第二个像素亮，它将赋给相应的位值1，否则为0。
再次简短地选择一个随机对，并为它们赋值。对于一个128位向量，对一个关键点简单地重复这个过程128次。然而，BRIEF也不是旋转不变的，因此orb使用rBRIEF(Rotation-aware BRIEF)。
对于一个平滑图像patch p。一个二进制测试$\tau$定义为：
$p(x)$表示图像$p$在点$x$处的强度，特征定义为$n$个二进制测试值的向量：
$$ f(n)=\sum_{1<i<n}2^{i-1}\tau(p;x_i,y_i) $$
当平面内旋转超过几度时，BRIEF的匹配性能急剧下降。ORB提出了一种根据关键点方向控制BRIEF的方法。对于某个特征的$n$个二进制测试值在位置$(x_i,y_i)$处，我们需要一个2Xn矩阵：
使用patch方向$\theta$及其对应的旋转矩阵$R\theta$，并构建一个$S_\theta$：
$S\theta=R\theta S$
则BRIEF操作器变为：
然后将角度离散为2π/30(12度)，并构造一个预计算的BRIEF图形查找表。
原文：https://juejin.cn/post/7096826597449138207