亚当学院网站视频建设教程,浦东做网站公司,泉州做 php 网站,档案网站建设的原则首先#xff0c;ORB算法来自于OpenCV Labs#xff0c;相比于SIFT和SURF#xff0c;ORB在使用中不必担心专利的问题。但同时ORB在保证了一定性能的条件下做到了高效。在论文《ORB: An efficient alternative to SIFT or SURF》2011中#xff0c;ORB在特征点检测和描述子生成…
首先ORB算法来自于OpenCV Labs相比于SIFT和SURFORB在使用中不必担心专利的问题。但同时ORB在保证了一定性能的条件下做到了高效。在论文《ORB: An efficient alternative to SIFT or SURF》2011中ORB在特征点检测和描述子生成方面都做了改进结果是ORB is at two orders of magnitude faster than SIFT, an order of magnitude faster than SURF,即可以比SIFT的速度快100倍比SURF快10倍。这样就不必借助GPU就可以实现算法的加速。作者还在智能手机上借助OpenCV port for Android进行了实验。
ORB之所以快是因为站在了巨人的肩膀上。ORB的特征点检测和特征点的描述子分别使用了速度最快的FAST算法和BRIEF算法但是又都针对他们的缺点进行了改善。对于FAST使用图像金字塔方法实现了尺度不变性使用Harris角点滤波器剔除检测到的边缘并对检测到的特征点评级FAST算法对边缘敏感Large responses可以挑出表现最好的特征点。FAST的一大缺陷是没有旋转不变性在SIFT中通过特征点邻域的梯度直方图的统计得到方向信息SURF则是利用Haar小波在邻域内进行近似计算。ORB的作者在Rosin分析各种角点方向的方法的基础上选择了质心的方法。特征点的邻域是一个patch那么patch一定会有一个质心(intensity weighted centroid),特征点和质心一般不会重叠即有一个offset特征点到质心的连线构成的矢量就是该特征点的方向向量。至于patch到底是多大文中没有明说但我个人理解应该是和FAST算法时使用的半径大小是一致的。ORB作者在使用FAST算法时使用的是FAST-9即半径大小是9个像素。
质心是由矩计算得到的质心
矩的计算公式
为了使得方向不变性鲁棒性更好作者在计算矩的公式中x,y不是取相对于图像原点的坐标而是相对于特征点的坐标xy的范围是[-r,r]。当质心C的模趋于0即质心逼近与特征点这种求特征点的方法变得不稳定但是这种情况很少出现。这里的理解不知道是否正确。
在描述子上ORB主要使用的是BRIEF但是BRIEF对于旋转缺乏不变性即在旋转前后特征点的描述子是不同的。文中首先提出的方法和SIFT一样是借助于之前得到的主方向将特征点周围的邻域旋转到主方向的方向上这样在其中统计梯度方向直方图就会和旋转之前一致。文中把这种方法叫steer BRIEF但是BRIEF中需要注意的是即便旋转到了主方向BRIEF前后在特征点周围的patch按照分布函数选择的tests还是会不一样所以steer BRIEF直接使用旋转之前选择的tests坐标构成的矩阵与旋转矩阵相乘得到旋转之后的tests。为了加快速度steer ORB将角度离散化间隔为12degrees提前计算出了一个查找表。 这样只要视角角度与theta一致就可以直接得到tests进而得到二进制描述子。
但是steer BRIEF改变了BRIEF原有的几个优良特性1.BRIEF的二进制描述子方差大。2. BRIEF的二进制描述子的均值为0.5。先来解释一下为什么方差和均值有这样的特性并且为什么这样的特性是优良的。首先这些对于一个特征点的长度为n的二进制01比特串比特之间可以看作是独立同分布的二项分布。那么它的方差np(1-p)n(-p^2p),这是一个凸函数p0.5时取最大值对于单个bit方差最大可以达0.25均值np但既然作者说均值是0.5应该指的是每一位比特的均值。方差大意味着01更分散01的位数是差不多的也就是tests更加随机。原文的话是High variance makes a feature more discriminative, since it responds differentially to inputs.我理解的inputs是由tests得到的点对比较大小进而由判断条件得到0或者1因为方差大每一位bit的输出的0,1可能性是一样的所以最终的二进制串更加独特。方差的特性与均值相关论文中就均值做了统计画出了几种描述子方法的直方图 对100k个特征点基本的BRIEF方法采取了典型的高斯分布得到256bits的描述子。对每一个特征点bit meannumber of 1/256.可以看到BRIEF算法的均值更接近于0.5Steered BRIEF失去了均值为0.5的特性而接近于均匀分布。rBRIEF是对Steered BRIEF的改进在保留了旋转不变的同时也保留均值接近0.5的特性。文中作者提到了另外一种理解的角度有了方向信息的描述子因为更加归一化(more uniform appearance)而均值才更加分散。
描述子还应该有的一个重要的特性就是它的tests之间是无关的。这个特性使得不同位的比特之间是独立的互不影响的每个点对都对描述子做出了贡献我理解这样构成的描述子才更稳定因为描述子包含了更多的邻域信息。为了比较三种描述子方法的这一特性论文中借助了PCA主成分分析 图中画出了100k个特征点的描述子构成的矩阵的前40个最大的特征值由这40个特征值的大小连成了曲线。特征值越大说明描述子的信息越集中在少数的主成分中。Steered BRIEF的特征值更小意味着方差更小不太懂这个关系所以特征点之间的区分度更低。 Steered BRIEF中特征点的与outliers的距离的均值更小但是与inliers的重叠也更大。
于是继续改进我们的目标不仅是使得描述子对旋转不变还要有大方差0.5的均值在tests之间还要保证低相关性这就是rBRIEF方法。一个思路是继续使用PCA这也在SIFT基础上被使用过可以从高维向量中提取出互不相关的特征向量从而减少了冗余的信息。但是二进制tests的空间过大不便使用PCA且为了得到256bits大小的无关的描述子我们就必须在最初找到更高维的描述子这就反而降低了效率。所以我们最好可以直接找到不相关的tests。文献21,27使用offline clustering找到不相关的examplars。在ORB论文中在所有可能的二进制tests中贪婪查找找到满足三个条件的tests。
初始的tests有205590个先按照其均值接近于0.5的程度进行排序保证均值进而保证高方差挑选均值最接近于0.5的放入集合R中再挑选下一个均值最接近0.5的test并且求与R中的test的相关性如相关性小于阈值才将其加入R中这样就保证了低相关性。文章将这种由贪婪算法获得的tests称为learned tests将改进之前的算法称为unlearned tests下图是二者的对比。 左图是改进之前的算法首先左图有很多接近竖直的点对构成的连线表明了tests之间有很多相关性。颜色表示了每一个test与其余tests的最大相关值在右图中紫色更多也表明改进之后的算法中tests的相关性更低。
oFAST和rBRIEF算法组合构成了ORB算法。使用了两种数据集进行测试。一种是添加了高斯噪声的in-Plane旋转图像一种是真实世界中从不同视角获得的Highly-textured图像。对reference image和test image都提取500个特征点然后使用暴力匹配brute-force matching寻找最佳对应点。比较rBRIEF、SIFT、SURF的Percentage of inliersBRIEF在10度就开始急剧下降SIFT优于SURFSURF由于haar小波分解以45度为周期呈现规律性的起伏。ORB抗噪性也优于SIFT。对于real-world images又分别使用了作者自己的indoor数据集和outdoor在outdoor dataset中ORB优于SIFT和SURFindoor set中也近似这样。文献6表明SIFT在graffititype images中表现更好。
在寻找最近邻NN点的时候作者使用了multi-probe LSH局部哈希来提高效率。哈希方法分为离线建立索引和在线查找两部分。传统哈希方法是将相同的数据映射到相同的bucket中局部哈希是近似最近邻查找ANN的一种它将两个距离相近的数据也以很大的概率映射到相同的bucket中根据距离的度量方式的不同又可以选取对应的映射函数。实验表明LSH比通过FLANN构建的特征点的kd树还要快。
使用Python3和OpenCV库实现ORB算法。参考的是链接7简书中的代码需要注释的是Python的缩进。之前没怎么接触Python在学习的过程中顺便对代码做了一些注释。
#!/usr/bin/env.python
# codinggbk 支持中文注释
import numpy as np
import cv2
img1cv2.imread(beaver.png,0)
img2cv2.imread(beaver_xform.png,0)#定义函数
def drawMatches(img1, kp1, img2, kp2, matches):rows1img1.shape[0]#height(rows) of imagecols1img1.shape[1]#width(colums) of image#shape[2]#the pixels value is made up of three primary colorsrows2img2.shape[0]cols2img2.shape[1]#初始化输出的新图像将两幅实验图像拼接在一起便于画出特征点匹配对outnp.zeros((max([rows1,rows2]),cols1cols2,3),dtypeuint8)out[:rows1,:cols1] np.dstack([img1, img1, img1])#Python切片特性初始化out中img1img2的部分out[:rows2,cols1:] np.dstack([img2, img2, img2])#dstack,对array的depth方向加深for mat in matches:img1_idxmat.queryIdximg2_idxmat.trainIdx(x1,y1)kp1[img1_idx].pt(x2,y2)kp2[img2_idx].ptcv2.circle(out,(int(x1),int(y1)),4,(255,255,0),1)#蓝绿色点半径是4cv2.circle(out, (int(x2) cols1, int(y2)), 4, (0, 255, 255), 1)#绿加红得黄色点cv2.line(out, (int(x1), int(y1)), (int(x2) cols1, int(y2)), (255, 0, 0), 1)#蓝色连线return out# 检测器。ORB 直接换成AKAZE也可以KAZE需要将BFMatcher中汉明距离换成cv2.NORM_L2
detector cv2.ORB_create()kp1 detector.detect(img1, None)
kp2 detector.detect(img2, None)
kp1, des1 detector.compute(img1, kp1)#计算出描述子
kp2, des2 detector.compute(img2, kp2)bf cv2.BFMatcher(cv2.NORM_HAMMING, crossCheckTrue)#暴力匹配
matches bf.match(des1, des2)
img3 drawMatches(img1, kp1, img2, kp2, matches[:50])#找到50个匹配对cv2.imwrite(orbTest.jpg, img3)
cv2.imshow(orbTest, img3)
cv2.waitKey(0)Reference
见过的介绍ORB最清楚的博文https://blog.csdn.net/yirant7/article/details/51332881大神一步步教你读懂ORB算法https://blog.csdn.net/fsfengqingyangheihei/article/details/73572856OpenCV-Python Tutorialshttps://opencv-python-tutroals.readthedocs.io/en/latest/py_tutorials/py_feature2d/py_orb/py_orb.html源码解析https://www.cnblogs.com/wyuzl/p/7856863.htmlORB算法介绍图四https://blog.csdn.net/lhanchao/article/details/52612954https://opencv-python-tutroals.readthedocs.io/en/latest/py_tutorials/py_feature2d/py_orb/py_orb.html简书https://www.jianshu.com/p/5083f8d75439
