ORB特征笔记

简介  

      ORB = Oriented FAST  + Rotated BRIEF

        前面的Oriented FAST说明的是它的关键点的选取是一种改良过的FAST，在FAST的基础上加了方向信息；后面的Rotated BRIEF是指特征描述符使用BRIEF描述子（Binary Robust Independent Elementary Feature)，是一种速度极快的二进制描述子。

改良的FAST角点检测

        在前面笔记中已经记录了FAST角点检测的基本原理。oFAST主要改良的点是增加了关键点的方向描述，还有就是增加了图像金字塔。

        1. 构造高斯金字塔

            ORB中的图像金字塔和SIFT中的多尺度高斯金字塔不同，每层只有一副图。金字塔共有n层，第s层的尺度为：。

        是初始尺度，默认值1.2。原图在第0层。第s层的图片尺寸为：。

        2. 特征点检测

            在不同尺度的图像上使用FAST算法检测特征点 。FAST在边缘上有较大的响应，ORB中利用了Harris角点响应度量来排序FAST的关键点。对于目标为N个关键点的情况，首先将阈值设置得足够低以获取比N多的关键点，然后根据Harris角点响应值排序，选取前N个关键点。

        3. 计算特征点主方向

             使用灰度质心法计算出以特征点中心O为圆心，半径为r的圆形区域内的质心点C。 特征点的主方向是从O到C的向量的方向。

                灰度质心的位置点C为：

                其中，的计算方法为：

                因此：

                特征点的主方向角度为：

 

构建rBRIEF描述符

        经过oFAST得到了关键点和其主方向后，接下来就要构建出关键点的特征描述符了。ORB有旋转不变性，在构建BRIEF描述符之前，会将特征点的邻域旋转到特征点的主方向上。

BRIEF特征描述符

        BRIEF的核心思想是在关键点P的周围选取N个点对，然后把这N个点对的边角结果组合起来作为该关键点的描述子。Brief算法生成的是一种二值化的描述子，匹配的时候只需要使用简单的汉明距离比对即可，使用bits之间的异或操作就能完成。因此它的时间空间代价都比较低，效果也还不错。

         1. 滤波：对原图滤波，去除部分噪声。

         2. 选取点对：以关键点为中心，选取一定大小的图像窗口p，在窗口内选择一对点，比较两者像素值的大小，进行赋值，二值测试函数定义如下：

        

                其中，表示像素x在窗口p内的像素值。

         3. 在窗口p中随机选取N（128,256,512，默认为256） 对随机点对，重复第2步进行二进制赋值，最后得到一个N维的二进制描述子，这个结果向量被定义为：

         这个式子其实直白理解就是，每一个bit表示了一个点对的对比结果。

Brief算法中点对的选取方法

        对于SxS的区域内选取点对，原始Brief论文中做了5种方法：

        1.(X,Y) ~ i.i.d（独立同分布）。服从均匀分布：位置均匀分布在块内。

        2. (X,Y) ~ i.i.d（独立同分布）。服从高斯分布:采样带内服从各向同性的高斯分布。

        3. X ~ i.i.d（独立同分布），服从高斯分布；Y~ i.i.d（独立同分布），服从高斯分布。 采样分两步，第一步以原点为中心的高斯分布中采样出,然后再以为中心，采样得到第二个位置。超出块的范围的位置会被钳在块的边缘处。

        4. 在空间量化极坐标下的离散位置随机采样；

        5.  。固定为原点，采样自粗粒度的极坐标网格的离散位置上。

        上述5种采样方式的示意图如下：

         在旋转不是非常厉害的图像里，用BRIEF生成的描述子的匹配质量非常高。

Steered BRIEF

           原始的BRIEF算法，不具有旋转不变性，当平面发生非常小角度的旋转后，其匹配质量会大幅下降。下图是各种描述子在平面旋转角度和算法对应的正常有效点（inliers）的百分比示意图：

         Steered BRIEF会根据关键点的方向进行旋转，然后再计算Biref描述符。对于特征点邻域内的n个点对的集合：

        通过一个旋转角度为对应的旋转矩阵做变换，定义出旋转后的点对集合:

         因此steered BRIEF算子变成了：

         这个函数定义实际就是对旋转后的点对儿进行对比生成Biref描述符的计算过程。

rBRIEF

        steered BRIEF解决了BRIEF不具有旋转不变性的问题，但它在描述符的可区分性上。描述符本身是关键点的特征信息，在匹配的时候可以用来区分不同的关键点。如果描述符的可区分性变差，则不同的关键点相似度会变高，不容易找到对应的关键点，误匹配率会变大。论文中对100K个采样的关键点用不同的方法生成的特征描述符的均值分布：

         图中X轴表示到均值0.5的距离。y轴则是对应BRIEF描述符中的特征bits数量。

        注:网上参考的所有文章几乎都是说y轴是特征点数量，这点我持保留意见，虽然最终要表达的意思是差不多的。论文中描述这个图表的原话是：

        “the spread of means for a typical Gaussian BRIEF pattern of 256 bits over 100k sample keypoints”。

        个人感觉应该是根据100K个采样点统计后按照概率所计算的描述符中某个bit feature列计算均值，然后按照这个均值到0.5的距离进行分段统计。假设距离为0的有140个，表示的是这256个列中，有140 bit feature列的均值就是0.5。如下图所示：

        以上仅为个人理解，大家可以去看看原始论文，或者去参看一下“参考资料”中最后一个链接。

        为什么X轴要用到均值0.5的距离？因为我们得到的描述符都是二值的（0,1），对于多个0和1组成的串。如果计算出的均值是0.5，则表示这个串中0和1的数量是相等的。如果0更多，则均值偏向0；如果1更多，则均值偏向1。后面两种情况计算距离都会偏离0.5，表示这一组数据中的0或1更多，因此对应的特征值就越相似，越难以区分。

        为了解决steered BRIEF的这个问题,ORB中引入了rBRIEF。它不使用BRIEF原始论文中选取点对儿的5种方式的任何一种，而是通过统计学习得到一种比较好的选取点集的方法。

        首先创建一个300K个关键点的训练集。然后在一个31x31大小的块中做二值测试。每个点对儿是块内部两个5x5的子窗口，一个子窗口相当于一个像素，其灰度值是这个子窗口内所有像素灰度值的均值，可以通过积分图像快速求得。我们记块的宽度,子窗口的宽度。

        因此，子窗口总数量为，计算得到不同的选取点对儿的方式为：。

        注：原始论文中，。原始论文中N的值并没有覆盖全子窗口，M的值，论文中是有去除一些重叠的区域，但没有找到重叠区域是如何定义的。如果哪位大神清楚请帮忙说明一下。本文中的N和M来自网上的参考资料，更容易理解一点，N取的是全部子窗口（会加1），M按照组合方式计算（不考虑去掉重叠区域）。

        rBRIEF算法的最终目的是从这M种选取点对儿方式中找出最优的256中选择方法。算法的流程如下：

        1. 在每个样本点的31x31的邻域内，用不同的点对儿选取方式做二值测试，每个样本点对应M个结果。结果是一个300K * M的矩阵，对矩阵每一列计算均值：

        2. 根据每一列的均值到0.5的距离对列进行重新排序，得到T（下图为一种可能出现的示意图）：

         3. 贪心搜索：

                a. 将T的第一列取出放到R中；

                b. 从T中取下一列，将它和R中的所有的列进行比较。如果相关性大于某个阈值则丢弃，否则将这一列放入R中。

                c. 重复b步骤，直到R中选出了256个列。如果最终结果少于256个，则修改阈值再试一次。

        经过这几步，最终就能得到256个点对儿的选取方法，结果就是rBREIF。

 参考资料

https://www.researchgate.net/publication/221111151_ORB_an_efficient_alternative_to_SIFT_or_SURFhttps://www.researchgate.net/publication/221111151_ORB_an_efficient_alternative_to_SIFT_or_SURFhttps://web.stanford.edu/class/cs231m/references/harris-stephens.pdfhttps://web.stanford.edu/class/cs231m/references/harris-stephens.pdfhttps://www.researchgate.net/publication/222485725_Measuring_Corner_Propertieshttps://www.researchgate.net/publication/222485725_Measuring_Corner_Propertieshttps://www.researchgate.net/publication/221304115_BRIEF_Binary_Robust_Independent_Elementary_Featureshttps://www.researchgate.net/publication/221304115_BRIEF_Binary_Robust_Independent_Elementary_Features02-p2-rbrief_哔哩哔哩_bilibili02-p2-rbrief是02-ORB特征提取的第2集视频，该合集共计2集，视频收藏或关注UP主，及时了解更多相关视频内容。https://www.bilibili.com/video/BV1PW411M73t?p=2&vd_source=474bff49614e62744eb84e9f8340d91ahttp://media.ee.ntu.edu.tw/courses/cv/21S/slides/cv2021_lec03.pdfhttp://media.ee.ntu.edu.tw/courses/cv/21S/slides/cv2021_lec03.pdf

特征点匹配——ORB算法介绍_orb匹配算法_lhanchao的博客-CSDN博客《ORB: an efficient alternative to SIFT or SURF》是Rublee等人在2011年的ICCV上发表的一篇有关于特征点提取和匹配的论文，这篇论文介绍的方法跳出了SIFT和SURF算法的专利框架，同时以极快的运行速度赢得了众多青睐。下面我简单介绍一下ORB算法的流程。ORB算法的主要贡献如下： （1）为FAST算法提取的特征点加上了一个特征点方向； （2）使_orb匹配算法https://blog.csdn.net/lhanchao/article/details/52612954