Machinelearingforhighspeedcornerdetection

基于机器学习的高速角点检测爱德华Rosten和汤姆·德拉蒙德英国剑桥大学工程部,{er258,twd20}@cam.ac.uk摘要特征点在实时帧频应用中使用时，利用高速特征检测器是很有必要的。像SIFT、Harris、SUSAN等特征检测器，他们使用好的方法可以检测出高质量特征点，然后他们的计算过于集中复杂以至于难以在任何复杂度的实时应用中使用。在这里，我们展示基于机器学习的特征检测器，它可以用不到7%的有效处理时间来跑完整个PAL视频。通过比较发现，在满帧频时，SIFT检测器（120%）既不能实现，SIFT（300%）检测器也不能实现。很明显，如果产生的特征点不适合向下加工处理，那么高速检测器就会被限制使用。特别的，从两个不同位置观察的同一处场景应该产生反应相同3D世界的位置特征。因此，本文的第二个贡献是基于此标准下3D场景的角点探测器的比较。这种比较支持现有其它角点检测器得到的理论。此外，与我们最出的预期相反，尽管主要优势来自于速度，但是根据这一标准，我们的检测器明显优于现有的特征检测器。1引言角点检测作为许多视觉等任务的第一步,如SLMA（即时定位与地图构建）、定位、图像匹配和识别。因此，在文献中存在着大量的角点检测器。既然有了如此多的可用检测器，似乎没有必要提出其它的检测器加入这个群体；然而，我们对SLMA在实时帧频应用中计算资源达到了饱和状态非常感兴趣。特别地，当以满帧率处理视频直播流时，现存的特征检测器几乎没有时间剩下去做更深入的处理，甚至不顾摩根定律。本文的第2部分展示了先前文献描述的特征检测器如何重新被设计并使用机器学习算法以达到速度的提升。此外，这种方法允许检测器可以被推广，产生一系列我们目前用来实时跟踪和AR标签布置的高速检测器。为了展示不需要降低特征检测器的检测质量就可以达到该检测速度，我们将自己的检测器与大量有名的检测器相比较。在第三部分中，我们采用史密德标准[1]，当展现同一3D场景的不同视图，一个检测器要（尽可能）检测出该场景中对应相同特征的转角（角）。下面我们将展示如何在3D场景中一个近似平面模型已知的条件下，将该技术应用于几个3D场景中。1.1前期工作大部分的特征检测算法是通过计算整个图像的角点响应函数。超过阈值像素角点值（和局部最大值）是保留的。Moravec计算参考角点邻域和平移一小段距离周围其它邻域的平方差和（SSD），函数取最小的SSD值保留，确保提取的角点是平移时改变最大的地方。Harris计算在上面的基础上计算SSD的近似二阶导数值，这个近似值是：H=(𝐼𝑥2̂𝐼𝑥𝐼𝑦̂𝐼𝑥𝐼𝑦̂𝐼𝑦2̂)在这里‘^’符号表示求取整个图像像素点邻域的平均值（用一个平滑的圆形窗口代替矩形窗口可以降低平均值噪音和方向的影响）。Harris定义了角点响应函数为：C=|𝐻|−𝑘(𝑡𝑟𝑎𝑐𝑒𝐻)2如果H的特征值大，这个值也是大的，它避开了对特征值的直接计算。这表明了特征值是图像曲率的一个近似测量。基于仿射图像变形的假设,Shi和Tomasi引导的一个数学分析得出了结论，使用H的最小特征值作为角点强度函数是更好的：C=min(𝜆1,𝜆2)如何从H矩阵中计算角点强度有很多参考[5,6,7,8],这些已经相当于各种H矩阵的矩阵范数[10]。郑以及其它人[11]对H矩阵进行了计算分析，他们发现一些合适的近似值允许他们通过计算仅仅两张平滑的图片来获得速度上的提高，代替之前三张的要求。Lowe通过多尺度高斯差分核对图像做卷积获得标度不变性，保留尺度以及空间上最合适的点。高斯差分被使用因为它充分逼近高斯型拉普拉斯算子并且计算速度更快。高斯差分的近似已经被拟建，相比较直接高斯卷积实行而言，倘若尺度相距√2，那么计算速度提升大约两倍。在文献[14]中提及高斯差分是特别稳定的尺度空间核。尺度空间技术在文献[15]中也已经联合Harris方法，在此以多尺度计算Harris角点，仅仅保高斯差分响应中的最佳响应点。最近，标度不变性已经得到延伸，考虑对于仿射变换特征不变的问题[14,16,17]。图像中的边缘（通常是亮度上的一个阶跃变化）相当于两个区域间的边界。在区域的角点上，这个边界迅速改变方向。一些技术已经发展了，包括检测和链接边缘，通过分析链式码，着眼于在链接的边缘中找到角点，找到曲率最大值[19,20,21]，改变方向[22]或者改变外观[23]。其它方式是避免边缘连接，而是寻找曲率最大值[24]或者在梯度大的地方改变方向[25]。另一类的角点检测器通过检测图片的一小块邻域来看是否‘看’起来像角点。因为不计算二阶导数，像高斯平滑的降噪步骤就不是必需的。对于每一个角点检测而言，仅仅检测其周围一小块像素，因此，这些角点检测器计算效率高。由此得出推论，这些检测器检测那些仅有大范围特征的图像，例如模糊图像时往往表现不佳。在本文中提出的角点检测器属于这一范畴。在文献[26]提出的方法中，假设角点类似于一个模糊的楔，通过拟合局部图像再找到楔的特征（振幅、角度和模糊度）。文献[27]中对楔的概念进行了延伸，提出了计算角点强度的一种方法，这是通过圆盘内像素的比例计算自相似度，圆盘的亮度不超过中心核值的某个阈值。离核越近的像素点获得更高的权重。这种方法被叫做USAN（核值相似区）。对USAN的较小值表明角点是很不同于周围像素点的。有一套规则用来抑制品质不好的特征，从保留的候选像素里面选择局部最小值，就是最小USAN。Trajkovic和Hedley[28]用类似的想法:如果像素点看起来同邻域重心不同，那么这个邻域就不是自相似的。这是通过圆形模板来测量的。𝑓𝐶是圆形模板中心像素值，𝑓𝑃和𝑓𝑃′是穿过圆径任意一头的像素值。响应函数被定义为：C=min𝑃(𝑓𝑃−𝑓𝐶)2+(𝑓𝑃′−𝑓𝐶)2有角点的地方这个值就会很大。下面的测试时基于Bresenham圆进行的。这是因为圆是离散的、线性的，环形内插法是用在离散方向上为了提供检测器更好的各向同性反映。为此，作者们提出了一个方法，凭借最小响应函数，在两个像素点间插值能够有效地进行计算。计算响应函数要求要求对全方向进行搜索，但是任何单次测量都会得出一个响应上限。为了加速匹配，只检测水平和垂直方向的响应。如果反应的上限太小了，那么潜在的角点就会检测不出来。为了使这个方法进一步加速，快速检测得以应用。在检测角点上，快速径向对称变换已经发展成熟。当梯度既是径向对称且沿着半径有一致的信号时，该点就会有很高的值。通过改变检测径向对称区域的大小，数值范围也能够被改变。检测图像一小块邻域来观察是否是角点的一种替代方法是利用机器学习给图像的邻域分类为角点或者非角点。被用在训练集里的数据决定了要检测特征的类型。在文献[30]中，训练了三层的神经网络去识别角点，这些角点靠近8×8窗口的中心，边缘有多个45度的角。这是在对图像进行边缘检测和稀释后进行的应用。即将展示神经网络如何学习到更多的一般表示并且能够检测各种各样角度的角点。2高速角点检测2.1FAST:来自加速段测试的特征测试阶段按照候选角点p周围一圈16个像素进行操作。如果在圈内存在一组连续的像素都点比候选点像素𝐼𝑝和阈值t的像素和还大或者比候选点像素𝐼𝑝与阈值t的差还小，那么原始的检测器就把p分类为角点。如图1所示，选择n为12是因为它允许在能够排除大量非角点的情况下做高速测试：这个测试仅仅检测在1、5、9、13四个罗盘方向上的像素值。如果p是角点，4个像素值中至少有3个是比𝐼𝑝和阈值t的像素和还大或者比𝐼𝑝与阈值t的差还小。若两种情况都不是，则p点就不是角点。通过检测圈内所有的像素，这种检测标准能够应用于剩下的候选点，做出完整的测试。这个检测器本事具有高性能，但也存在一些缺点:1.对于n小于12的高速检测效果不好；2.检测出来的角点不是最优的，这是因为它的效率取决于问题的排序与角点的分布；3.对于角点分析的结果被丢弃了；4.多个特征点容易挤在一起。2.2机器学习的角点检测器这里我们提出一个使用机器学习的方法来处理前三个点（第四个点在2.3节中被处理）。处理过程分为两个阶段。为了给给定的n值建一个角点检测器，首先，从一系列图片（最好从目标应用域获得）中使用对应n的检测规则和适合的阈值检测出角点。这时候使用比较慢的算法即每个像素点都要测试其周围一圈16个位置上的点。对于一圈上每一个位置点x∈{1…16}，像素相对点p的位置有以下三种状态：𝑆𝑝→𝑥={𝑑，𝐼𝑝→𝑥≤𝐼𝑝−𝑡(𝑑𝑎𝑟𝑘𝑒𝑟)𝑠，𝐼𝑝−𝑡𝐼𝑝→𝑥𝐼𝑝+𝑡(𝑠𝑖𝑚𝑖𝑙𝑎𝑟)𝑏，𝐼𝑝+𝑡≤𝐼𝑝→𝑥(𝑏𝑟𝑖𝑔ℎ𝑡𝑒𝑟)选择一个x并计算所有p∈P（所有训练图像的像素集）的𝑆𝑝→𝑥，划分P为三个子集：𝑃𝑑,𝑃𝑠,𝑃𝑏，在这里，每一个p都分配了𝑃𝑆𝑝→𝑥。定义一个布尔型变量𝐾𝑝，如果p是角点，那么𝐾𝑝就是真，否则𝐾𝑝为假。第二个阶段使用ID3算法选择能产生最多判断候选像素点是否为角点信息的x值，这是通过𝐾𝑝的熵来判断。对于点集P，K的熵表示为：H(𝑃)=(𝑐+𝑐̅)log2(𝑐+𝑐̅)−𝑐log2𝑐−𝑐̅log2𝑐̅在这里，c=|{𝑝|𝐾𝑝𝑖𝑠𝑡𝑟𝑢𝑒}|（角点的数量）𝑐̅=|{𝑝|𝐾𝑝𝑖𝑠𝑓𝑎𝑙𝑠𝑒}|（非角点的数量）然后x的选择产生信息增益：H(𝑃)−𝐻(𝑃𝑑)−𝐻(𝑃𝑠)−𝐻(𝑃𝑏)选择产生最多信息的x值，这个过程是在三个子集上不断递归地，也就是选择𝑥𝑏分割𝑃𝑏为：𝑃𝑏,𝑑、𝑃𝑏,𝑠、𝑃𝑏,𝑏，选择𝑥𝑠分割𝑃𝑠为：𝑃𝑠,𝑑、𝑃𝑠,𝑠、𝑃𝑠,𝑏，诸如此类，被选中的每一个x都产生最多关于点集的信息。当一个子集的熵为零时，这个过程就会终止。这就意味着在子集中所有的p都有相同的，也就是他们要么都是角点要么都不是角点，这就能保证K是一个学习数据的精确函数。这叫创建了一个能够正确分类训练集中所有角点的决策树，因此能精确地使FAST角点检测器的实现得以具体化，把这个决策树转化为C代码，创建一个长的内嵌if-then-else语句，用来编译作为角点检测器使用。为了得以最优化，代码是被编译两次的，一次是获得测试图片的剖面数据，一次是为了最优化重新排序。在某些情况下，三个决策树中的两个可能是一样的，这时，分离他们的布尔型测试是被取消了。既然数据并不是包含所有有可能的角点，那么学习检测器是不如段测试检测器那么精确，可以相对直接的修改决策树以确保和段测试算法有相同的结果，然而，在某种程度上，所有的特征检测器都是启发式的，在这方面，学习检测器同段测试检测器比较是有点点不同的。2.3非极大值抑制由于阶段测试并没有计算角点响应函数，非极大值抑制不能够直接应用到结果特征值上。因此，就会为每一个检测出来的角点计算分值函数V，非极大值抑制就会利用这个V值，移除其临近角点有较高V值的角点，这里对V有三个定义：1.n最大时p仍为角点的n值2.t最大时p仍为角点的t值3.弧周围连续像素与中心像素差值的绝对值和定义1和定义2是明显的量化方式，并且许多像素点会得到相同的结果。为了加快计算速度，对定义3做了点小小的修改。V是被定义为：V=max(∑|𝐼𝑝→𝑥−𝐼𝑝|−𝑡𝑥∈𝑆𝑏𝑟𝑖𝑔ℎ𝑡,∑|𝐼𝑝−𝐼𝑝→𝑥|−𝑡𝑥∈𝑆𝑑𝑎𝑟𝑘)其中𝑆𝑏𝑟𝑖𝑔ℎ𝑡={𝑥|𝐼𝑝→𝑥≥𝐼𝑝+𝑡}𝑆𝑑𝑎𝑟𝑘={𝑥|𝐼𝑝→𝑥≤𝐼𝑝−𝑡}2.4用时结果用时测试是在2.6GHz皓龙和850MHz奔腾III处理器上运行的。定时数据采用PAL视频资源（分辨率为768×288）的1500个黑白段。当n值取9和12时，学习FAST检测器已经比较了原始的FAST检测器、Harris、DoG（高斯差-使用SIFT的检测器）和SUSAN检测