【理解】ORB特征提取

ORB特征提取

优势：

ORB：Orinted FAST+Rotated BRIEF
顾名思义：ORB特征是基于FAST特征的一个改进算法，它改进了FAST检测子不具有方向性的问题，在FAST特征提取的基础上加入了特征点的主方向。从而为后续的BRIEF描述子增添旋转不变的特征，同时构建图像金字塔实现尺度不变性。这样一来，图像帧与帧之间的特征匹配就变得容易许多，减少了特征点丢失，不匹配或误匹配的现象。

ORB特征提取采用速度极快的二进制描述子BRIEF，使得图像特征提取的速度大大提升。由原论文的测试数据可知（图1），每检测同一帧图像，ORB约要花费15.3ms，而SURF要花费217.3ms，SIFT特征提取则要花费5228.7ms，三者的差距是数量级的。因此基于其速度快的优势，ORB非常适合运用在如SLAM这样的实时系统。

图一：
【理解】ORB特征提取

ORB特征提取总体分为两个步骤：

FAST特征点提取，找出图像中的角点，并在FAST基础上计算了特征点的主方向。
BRIEF(Binary Robust Independent Elementary Feature)描述子：对前一步提取出的特征点周围图像区域进行描述并记录。由于前一步的特征提取计算了特征点的方向，因此为BRIEF描述子增加了旋转不变性。

经典FAST特征提取：

提取思想：如果一个像素与邻域的像素灰度差别较大(过亮或过暗)，那么它更可能是角点。

检测过程：

在图像中提取像素p,设其灰度值为I_p
设定一个阈值T(假设为20%I_p)
以像素p为圆心，选取半径为三的圆边上的16个像素点。
假如选取的的圆上有连续N个点灰度值大于I_p+T或小于I_p-T,那么p可以被认为是特征点。(N通常取12，即FAST-12，常见的还有FAST-9和FAST-11)
循环以上四步，对图像中的每一个像素点执行相同的操作。

值得一提的是，图像中绝大多数像素点并不是角点，为了更高效的排除它们，我们可以添加一项预操作来优化检测算法。
具体操作为：对于每个像素，直接检测邻域圆上第1，5，9，13个像素点的灰度（如图2），只有当其中三个像素满足I_p+T或小于I_p-T时，当前像素才可能是一个角点。否则直接排除（这样一来对于每个像素的平均检测数便由6减少到了2）。

图二：
【理解】ORB特征提取
此外，原始的FAST角点经常出现扎堆现象，所以在第一遍检测之后，还需要用非极大值抑制（Non-maximal suppression，NMS），在一定区域内仅保留响应极大值的角点（这里具体细节到时候再细看），避免角点集中的问题。

经典的BRIEF描述子：

BRIEF是一种二进制描述子，其N维描述向量仅由0和1组成，这里的0和1则描述了关键点周围随机选取的各像素对的灰度值的大小关系。

描述过程：

以特征点P为中心，取一个S×S大小的Patch邻域；
在这个邻域内随机取N对点（原论文建议采用高斯分布取点），然后对这2N个点分别做高斯平滑【降低噪声，使得描述子更加稳定，原论文建议采用9×9的kernal，但实际上一个滤波显然是不够的。因此ORB提出，利用积分图像来解决：在31x31的窗口中，产生一对随机点后，以随机点为中心，取5x5的子窗口，比较两个子窗口内的像素和的大小进行二进制编码，而非仅仅由两个随机点决定二进制编码。（这一步可由积分图像完成）】。比较N对像素点的灰度值的大小：（设一对点p1，p2，灰度I_p）：
最后把步骤2得到的N个二进制码串组成一个N维向量即可；

最后在进行特征匹配时，例如特征点A、B的描述子如下：
A: 10101011
B: 10101010
我们设定一个阈值，比如80%。当A和B的描述子的相似度大于90%时，我们判断A, B是相同的特征点，即这2个点匹配成功。在这个例子中A, B只有最后- -位不同,相似度为87.5%，大于80%。则A和B是匹配的。

我们将A和B进行异或操作就可以轻松计算出A和B的相似度。而异或操作可以借组硬件完成，具有很高的效率，加快了匹配的速度。

注：由于在计算比较的两个特征点的BRIEF特征点时，需要保持用同一组高斯随机点对（所以需要提前定义好,作为模板），所以假如图像发生旋转，BRIEF描述子就会改变，原来的特征点和旋转后的特征点就有极大可能匹配不上。因此说经典的BRIEF描述子不具备旋转不变性。
【理解】ORB特征提取

ORB特征提取的改进：

如何在FAST检测的基础上维持特征点的尺度不变性？

ORB通过构建图像金字塔，在金字塔每一层图像上进行特征点检测，这样一来便涵盖了不同尺度的特征点。

具体实现：
在ORB_SLAM2中，对原始图形（第0层）依次进行1/1.2缩放比例进行下采样得到共计8张图片（包括原始图像）然后分别对得到的图像进行特征提取，并记录特征所在金字塔的第几层，这样就得到一帧图像不同尺度的特征点：

【理解】ORB特征提取
在特征点匹配时，两幅不同尺度下的图像便可以通过匹配相近尺度图像金字塔的特征点来维持尺度不变性（仅个人理解），

参考博客：https://blog.****.net/RobotLife/article/details/87194017

如何在FAST检测的基础上维持特征点的旋转不变性？

灰度质心法(Intensity Centroid):
假设我们选取图2这样的图像块，我们可以把图像块当作是平面上质量分布不均的扁平物体，它的质量分布就对应图像块上每一像素的灰度值，所以灰度质心法本质上就是求解图像块”灰度重心”的过程。

求解过程（对于单通道图像）：
1.在一小的图像块B中，定义图像块的矩m为：
【理解】ORB特征提取
I(x,y)为像素灰度值，
当p=1，q=0时，m10为图像块x方向的加权和，权重为对应像素的灰度值，
当p=0，q=1时，m01为图像块y方向的加权和，权重为对应像素的灰度值，
当p=0，q=0时，m00为图像块的权值之和。

2.通过矩，可以找到图像的灰度质心坐标：
【理解】ORB特征提取
个人理解：灰度质心公式可以理解为求数学期望，只不过期望的对象成了坐标：即

对于B内每一个像素来说：
概率P：
【理解】ORB特征提取
概率P就是当前像素的灰度值占B所有灰度值总和的几分之几，假如B内所有像素点的灰度值相等，则每个像素点的概率都相等，求得的灰度质心也变为图像块的形心。

3.连接图像块的几何中心O与质心C，得到一个方向向量OC，于是特征点的方向可以定义为

【理解】ORB特征提取
参考博客：https://blog.****.net/Edgar_U/article/details/78483505

在提取了Orinted FAST关键点后，我们对每个点计算其描述子，由于我们计算了关键点的主方向向量，因此在计算描述子的过程中，我们将主方向设为x轴正方向，将旋转后的图像通过坐标变换变换为与主方向坐标系一致，这样一来最初的关键点和旋转后的关键点便建在了相同的坐标系上。再通过原始的BRIEF描述，得到的BRIEF描述子便具有了旋转不变性。

坐标变换：
θ是主方向角，S表示随机点位置（2xn的矩阵），Sθ表示旋转后的随机点的位置（2xn的矩阵），x1=(u1,v1)是一个坐标向量，其余类同，Rθ为旋转矩阵。
【理解】ORB特征提取

参考https://mp.weixin.qq.com/s/u5gSCwQ3XahF0fe19biAyQ
参考https://blog.****.net/gaotihong/article/details/78712017

对特征点数量与分布进行优化：

前面提到FAST特征对角点数目的优化，ORB算法在这方面也做了改进：即指定要提取的角点数量N，对原始FAST角点分别计算Harris响应值，然后选取N个具有最大响应值的角点作为最终的角点集合，若图像中的特征点不足N个，则将响应值降低为原来的1/2。

具体操作：

假定N=32，采用四叉树结构对图像进行分解，四叉树初始化为M个节点，即最开始把图像分割的个数。N=round(width/height)，即若宽高比为16/9，则M=2。
先对第一个节点一分为4，把各区域的关键点分配到对应四叉树子节点中（对第二个节点同样的操作，以此类推）：
当区域内没有关键点时，则该区域对应节点为空，节点不再分割；或当区域内仅有一个关键点时，节点也不再分割。
上图我们观察到图像中的有效区域为30，此时我们估计如果再对每一个区域细分，将大约产生30+17*3=81个有效区域，由于最终每个区域都将产生一个特征点，81>32,所以这时候我们改变策略，仅取关键点最多的区域分解，此时正好有32个节点，于是对那些特征点数>1的区域采取NMS，保留响应值最大的一个角点。