高速角点检测的机器学习

1、Machine learning for high-speed corner detection高速角点检测的机器学习Edward Rosten and Tom DrummondDepartment of Engineering, Cambridge University, UKAbstract Where feature points are used in real-time frame-rate applications, a high-speed feature detector is necessary. Feature detectors such as SIFT (DoG), H

2、arris and SUSAN are good methods which yield high quality features, however they are too computationally intensive for use in real-time applications of any complexity. Here we show that machine learning can be used to derive a feature detector which can fully process live PAL video using less than 7

3、% of the available processing time. Bycomparison neither the Harris detector (120%) nor the detection stage of SIFT (300%) can operate at full frame rate.摘要当实时帧速率应用中检测特征点时，我们必须采用一种高速特征探测器。当探测高质量特征时，使用特征探测器例如SIFT (DoG)（尺度不变特征转换），Harris（角点检测），SUSAN（SUSAN角点检测算法）是好的方法，然而他们在实时处理复杂图形的应用中，数据量计算量太大。我们在这篇文章中

4、展示的机器学习能够驱动一种特征探测器，这种方法可以完全处理实时PAL制式视频，比起现可行的方法可以减少7%的处理时间。通过比较，Harris探测（120%的时间）或者SIFT（300%的时间）都不能以全帧速率运行。Clearly a high-speed detector is of limited use if the features produced are unsuitable for downstream processing. In particular, the same scene viewed from two different positions should yield

5、 features which correspond to the same real-world 3D locations1. Hence the second contribution of this paper is a comparison corner detectors based on this criterion applied to 3D scenes. This comparison supports a number of claims made elsewhere concerning existing corner detectors. Further, contra

6、ry to our initial expectations, we show that despite being principally constructed for speed, our detector significantly outperforms existing feature detectors according to this criterion.明显地，一个高速探测器的使用是会受限制的如果特征的产生与下一步处理不匹配。特别的，从俩个不同的位置看相同的场景得到的特征应该与真实世界三维实物相吻合。因此这篇文章的第二个贡献是，提出了一个基于上述准则的3D场景角比较探测器。

7、这种比较支持许多其他现有角点探测器的功能。此外，与我们最初的期望相反，我们发现，尽管我们创造这种探测器主要是为了提高运算速度，然而就针对上述准则，我们的探测器明显优于其他现存特征检测器。1 Introduction Corner detection is used as the first step of many vision tasks such as tracking,SLAM (simultaneous localisation and mapping), localisation, image matching and recognition. Hence, a large numb

8、er of corner detectors exist in the literature. With so many already available it may appear unnecessary to present yet another detector to the community; however, we have a strong interest in real-time frame rate applications such as SLAM in which computational resources are at a premium. In partic

9、ular, it is still true that when processing live video streams at full frame rate, existing feature detectors leave little if any time for further processing, even despite the consequences of Moores Law.引言角点检测是许多视觉工作的第一步，例如跟踪、SLAM（同步定位与测图）、定位、图像匹配和识别。因此文献中大量介绍角点检测器。已经有如此多的角点探测存在，我们也许没有必要把另一个探测器呈现给社会

10、。然而，我们有强烈的兴趣针对实时帧速率应用，例如SLAM，在这里面计算资源是非常珍贵的。特别地，尽管摩尔定律的结果证明可以，但当我们在以全帧速率处理视频直播流时，现有的特征检测器几乎没有留出时间来进行深沉次的处理。 Section 2 of this paper demonstrates how a feature detector described in earlier work can be redesigned employing a machine learning algorithm to yield a large speed increase. In addition, the

11、 approach allows the detector to be generalised, producing a suite of high-speed detectors which we currently use for real-time tracking 2 and AR label placement 3.在文章的第二部分证明了，通过使用机器学习算法，在早期的工作中应用的特征检测器可以被重新设计，从而达到一个速度的提升。此外，这种方法允许检测器被广泛推广，生成一系列高速探测器，我们目前将他们用于实时跟踪和AR标签位置To show that speed can been o

12、btained without necessarily sacrificing the quality of the feature detector we compare our detector, to a variety of well-known detectors. In Section 3 this is done using Schmids criterion 1, that when presented with different views of a 3D scene, a detector should yield (as far as possible) corners

13、 that correspond to the same features in the scene. Here we show how this can be applied to 3D scenes for which an approximate surface model is known.为了说明我们的探测器在获得速度的提升的同时，没有牺牲特征探测器的质量，我们将我们的探测器和一系列知名的探测器做了比较。在第三部分，我们通过使用施密德的标准来完成对比，当展现三维场景的不同角度，探测器应该服从（尽可能）角，这些角符合场景中相同的特征。这里我们展示这种探测器如何被应用于3D场景中，模型表

14、面是近似已知的。1.1 Previous workThe majority of feature detection algorithms work by computing a corner response function (C) across the image. Pixels which exceed a threshold cornerness value (and are locally maximal) are then retained.Moravec 4 computes the sum-of-squared-differences (SSD) between a patc

15、h around a candidate corner and patches shifted a small distance in a number of directions. C is then the smallest SSD so obtained, thus ensuring that extracted corners are those locations which change maximally under translations.Harris5 builds on this by computing an approximation to the second de

16、rivative of the SSD with respect to the shift .The approximation is: （1）先前的工作大多数特征检测算法在检测图像时，是计算一个角响应函数（C）。像素点超过一个角点门限值（是局部最大值）就被保存下来。Moravec 在候补角点和周围的小块像素值之间计算平方差之和（SSD），这些小的像素块在不同方向上都有，且只移动一点点距离(灰度方差)。C取SSD算法最小值，从而保证提取的角点是那些沿着各个方向改变最大的点。Harris算法是计算一个相对于移位的SSD的二阶导数的近似值。近似值是 （1）where denotes averagi

17、ng performed over the image patch (a smooth circular window can be used instead of a rectangle to perform the averaging resulting in a less noisy, isotropic response). Harris then defines the corner response to be （2）上述公式中表示像斑的平均值，一个光滑的圆形窗口可以代替一个矩形，从而来执行平均值，导致小的噪声产生。然后Harris定义角响应为： （2）This is large

18、if both eigenvalues of H are large, and it avoids explicit computation of the eigenvalues. It has been shown6 that the eigenvalues are an approximate measure of the image curvature.C值是大的如果俩个H的特征值是大的，并且避免了直接计算特征值。已经证明特征值可以大约测试出图像曲率Based on the assumption of affine image deformation, a mathematical an

19、alysis led Shi and Tomasi7 conclude that it is better to use the smallest eigen value of H as the corner strength function: （3）A number of suggestion have 5,7,8,9 been made for how to compute the corner strength from H and these have been all shown 10 to be equivalent to various matrix norms of H 基于

20、图像仿射变换的假设，经过数学的推导分析，Shi and Tomasi证明最好是使用H的最小特征值做为角强度函数： （3）关于怎样使用H计算角强度，许多建议已经被提出，这些结果都和H不同的矩阵范数相等。 Zheng et al.11 perform an analysis of the computation of H, and find some suitable approximations which allow them to obtain a speed increase by computing only two smoothed images, instead of the thr

21、ee previously required.Lowe 12 obtains scale invariance by convolving the image with a Difference of Gaussians (DoG) kernel at multiple scales, retaining locations which are optima in scale as well as space. DoG is used because it is good approximation for the Laplacian of a Gaussian (LoG) and much

22、faster to compute. An approximation to DoG has been proposed which, provided that scales are apart,speeds up computation by a factor of about two, compared to the striaght forward implementation of Gaussian convolution 13. Zheng et al.分析了H的计算结果，并且找到了一些合适的近似值，这些值允许我们只计算俩个平滑像素，因为取代了之前的三个数据，所以计算速度上获得了提

23、升。Lowe得到了尺度不变性通过使用多级高斯差分来卷积像素，保留的位置既是尺度上的最优化，又是空间的最优解。DoG（高斯差分）被使用因为它能很好的近似计算出LoG（高斯拉普拉斯算子）并且计算的更快。DoG的一个近似值已经被提出，证明尺度是分离，计算速度得到提升是通过俩个因素实现的，相比于直接用高斯卷积来计算。It is noted in 14 that the LoG is a particularly stable scale-space kernel.Scale-space techniques have also been combined with the Harris approac

24、h in 15 which computes Harris corners at multiple scales and retains only those which are also optima of the LoG response across scales.在14这篇文章中指出LoG（高斯拉普拉斯算子）是一个特别稳定的多级空间的核。 在15中多级空间技术已经结合了Harris算法，文章在多级计算Harris角并且保留LoG多级间响应的最优值。 Recently, scale invariance has been extended to consider features whi

25、ch are invariant to affine transformations 14,16,17.An edge (usually a step change in intensity) in an image corresponds to the boundary between two regions. At corners of regions, this boundary changes direction rapidly. Several techniques were developed which involved detecting and chaining edges

26、with a view to finding corners in the chained edge by analysing the chain code18, finding maxima of curvature 19,20,21, change in direction 22or change in appearance23. Others avoid chaining edges and instead look for maxima of curvature24 or change in direction 25 at places where the gradient is la

27、rge.最近，尺度不变性已经扩展到考虑一些特性，这些特性对仿射转换不会发生改变的。图像的边缘（通常会有一个阶跃性的强度改变）是和俩个区域的边界相融合的。在区域的角落里，边沿方向改变非常的快。有几种技术已经被开发，这些技术包括探测和链接边缘，通过分析链码，在被链接的边缘用寻找角，找到曲率最大值，改变方向，或者改变外表。其他避免链接边缘和取而代之寻找曲率的最大值或者在梯度大的地方改变方向。Another class of corner detectors work by examining a small patch of an image to see if it “looks” like a

28、corner. Since second derivatives are not computed, a noise reduction step (such as Gaussian smoothing) is not required. Consequently, these corner detectors are computationally efficient since only a small number of pixels are examined for each corner detected. A corollary（推论） of this is that they t

29、end to perform poorly on images with only large-scale features such as blurred images（模糊图像）. The corner detector presented in this work belongs to this category.另一类角探测器工作时，检测图像的一小块，来验证它是否像一个角。因为二阶导数没有被计算出来，降噪这一步（例如高斯平滑）就是不需要的。结果这些角探测器计算特别有效率因为每个角探测器仅仅只需检测小数量的像素。一个推论是这些角探测器运行效果很差当这些图片仅有大数量级的特征例如模糊图像。

30、在这篇文章中展示的角探测器就是属于这个领域的。 The method presented in 26 assumes that a corner resembles a blurred wedge, and finds the characteristics of the wedge (the amplitude, angle and blur) by fitting it to the local image. The idea of the wedge is generalised in 27, where a method for calculating the corner stren

31、gth is proposed which computes self similarity by looking at the proportion of pixels inside a disc whose intensity is within some threshold of the centre (nucleus) value. Pixels closer in value to the nucleus receive a higher weighting. This measure is known as the USAN (the Univalue Segment Assimi

32、lating Nucleus). A low value for the USAN indicates a corner since the centre pixel is very different from most of its surroundings. A set of rules is used to suppress（抑制） qualitatively（质量上） “bad” features, and then local minima of the, SUSANs, (Smallest USAN) are selected from the remaining candida

33、tes.在26中展示的方法假设角像一个模糊的楔形，并且通过局部图像拟合来寻找楔形的特征（幅度，角度，和模糊度）。楔形的概念在27中有所概括，在这篇文章中提出一种计算角强度的方法，这种方法是通过计算光盘中像素的比例来计算自相似性地，他们的强度是在中心值阈值内的。像素值离中心值更接近的占更高的权值。这种测量就是著名的USAN（同值收缩核区）算法。USAN的值低能证明是一个角因为中心像素是与周围环境非常不同的。一系列的规则被用来抑制质量上差的点，并且标出SUSANs,最小的值，最小的USAN被选出来从剩下的候选者。Trajkovic and Hedley28 use a similar idea:

34、a patch is not self-similar if pixels generally look different from the centre of the patch. This is measured by considering a circle. is the pixel value at the centre of the circle, and and are the pixel values at either end of a diameter line across the circle. The response function is defined as

35、(4)Trajkovic and Hedley使用了相似的观点，如果像素是大体上与中心图像块不同的,小块图像就是不自相似的。这个可以通过一个圆进行测量。就是圆中心像素值，并且和是圆直径俩个端点的像素值。响应函数被定义为 (4)This can only be large in the case where there corner. The test is performed on a Bresenham circle. Since the circle is discretized（离散）, linear or circular interpolation is used in betwee

36、n discrete orientations in order to give the detector a more isotropic （各向同性的）response. To this end, the authors present a method whereby the minimum response function at all interpolated（插值） positions between two pixels can be efficiently computed. Computing the response function requires performin

37、g a search over all orientations, but any single measurement provides an upper bound（上限） on the response. To speed up matching, the response in the horizontal and vertical directions only is checked. If the upper bound on the response is too low, then the potential corner is rejected. To speed up th

38、e method further,this fast check is first applied at a coarse scale.仅当这个地方是角点的情况下C值是大的。这个测试是可以执行在一个Bresenham圆上。因为圆是离散的，线性，或者圆差值被用在不同的方向是为了给探测器一个各向同性的响应。为此，作者提出了一个方法可以有效地计算出俩个像素间插值位置响应函数的最小值。计算响应函数需要对不同方向进行计算，但是任何角度的测量结果都能为响应提供一个上限值。为了加快匹配速度，我们仅仅检查水平方向和竖直方向上响应的值。如果响应的上限值太低，那么潜在的角点是会被拒绝的。为了加快方法的速度，快速检

39、查先在粗略的尺度上运行一下。图1.12是对一个图像的角点测试，高亮度的正方形就是角点检测中的像素。像素P是候选角点的中心，虚线标出的弧穿过12个连续的像素，比p更亮的，都超过的门限值。A fast radial（径向） symmetry transform is developed in 29 to detect points. Points have a high score when the gradient（梯度） is both radially symmetric, strong, and of a uniform sign along the radius（半径）. The sca

40、le can be varied by changing the size of the area which is examined for radial symmetry.为了检测角点，在29中介绍了一个快速径向同步变换的方法。当这些点梯度值是径向对称的，值高的并且沿着半径是不统一的，那这些点分就会很高。通过改变镜像面积，规模可以是可变的。An alternative method of examining a small patch of an image to see if it looks like a corner is to use machine learning to cla

41、ssify patches of the image as corners or non-corners. The examples used in the training set determine the type of features detected. In 30, a three layer neural（神经） network is trained to recognise corners where edges meet at a multiple of 45, near to the centre of an 8 8 window. This is applied to i

42、mages after edge detection and thinning. It is shown how the neural net learned a more general representation and was able to detect corners at a variety of angles.检查一小块图像是否像一个角，一个可行的方法是使用机器学习的方法，把图像分类，分成是角点和非角点。在训练集中使用的例子决定了特征检测的类型。在文章30中，一个三层的神经网络被训练来识别角，这些角有许多45度的角，在88窗口中心的附近。在边缘检测和变稀少完成后，图像中就会应用

43、这个神经网络。这个方法也证明了神经单元是怎样学习一个更广泛的表像，并且能在各个角度探测角度。2 High-speed corner detection高速角探测2.1 FAST: Features from Accelerated Segment TestFAST：加速段检测的特征The segment test criterion operates by considering a circle of sixteen pixels around the corner candidate p. The original detector 2,3 classifies p as a corner

44、 if there exists a set of n contiguous pixels in the circle which are all brighter than the intensity of the candidate pixel Ip plus a threshold t, or all darker than Ip t, as illustrated in Figure 1. n was chosen to be twelve because it admits a high-speed test which can be used to exclude a very l

45、arge number of non-corners: the test examines only the four pixels at 1, 5, 9 and 13 (the four compass directions). If p is a corner then at least three of these must all be brighter than Ip + t or darker than Ip t. If neither of these is the case, then p cannot be a corner. The full segment test cr

46、iterion can then be applied to the remaining candidates by examining all pixels in the circle. This detector in itself exhibits high performance, but there are several weaknesses:段检测标准运行通过检测圆上16个像素点，这些点都是在候选角点p的附近。在23中介绍的原始探测器划分p点做为角的标准是：如果在圆中存在n个连续的像素点，这n个点的亮度全部比Ip+t大或者是都比Ip-t暗，图1中证明的就是这种检测方法。n取值是1

47、2因为它可以允许一个高速的测试，这可以被用来排除许多数量的非角点：测试时仅仅测4个像素点，1,5,9和13（4个垂直方向）。如果p是一个角点，那么这4个值中至少3个亮度值必须大于Ip + t或者小于Ip t。如果不符合这些要求，那么p就不能是一个角。完整的分段测试可以被用于接受的所有候选点，通过检测圆上的所有点。这种检测有很好的性能，但是有一些缺点： 1. The high-speed test does not generalise well for n 12.2. The choice and ordering of the fast test pixels contains implic

48、it assumptionsabout the distribution of feature appearance.3. Knowledge from the first 4 tests is discarded.4. Multiple features are detected adjacent to one another.1. 当n 12时不能拒绝许多候选点。检测出来的角点不是最优的，这是因为它的效率是依靠角点外形的排列和分布的。前4次的检测信息被遗弃了相邻的多个特征点会被检测到2.2 Machine learning a corner detector机器学习的角探测器Here we

49、 present an approach which uses machine learning to address the first three points (the fourth is addressed in Section 2.3). The process operates in two stages. In order to build a corner detector for a given n, first, corners are detected from a set of images (preferably from the target application

50、 domain) using the segment test criterion for n and a convenient threshold. This uses a slow algorithm which for each pixel simply tests all 16 locations on the circle around it.For each location on the circle , the pixel at that position relative to p (denoted by ) can have one of three states: （5）

51、这里我们想出一个方法，使用机器学习语言来来处理前三点，（第四点将在2.3部分来阐述）。处理操作分俩部，为了建立一个角探测器,在n值给定的情况下，第一步检测一系列图片的角（最好是来至目标应用的区域）为了n使用段检测标准并且一个合适的门限。使用一个慢速的算法使得每个像素简单的检测圆附近的所有16个位子。这16个像素中的每一个像素（假设为），可以有下面三种状态中的一种 （5）Choosing an x and computing for all (the set of all pixels in all training images) partitions P into three subsets

52、, Pd, Ps, Pb, where each p is assigned to。Let Kp be a boolean variable which is true if p is a corner and false otherwise.Stage 2 employs the algorithm used in ID331 and begins by selecting the x which yields the most information about whether the candidate pixel is a corner,measured by the entropy

53、（熵）of Kp.选择一个x并且计算P中所有p点的值（所有图像的像素的集合），将所有的P分成三个子集：Pd, Ps, Pb, ，每一个p是被分配到中。定义Kp为布尔变量，如果p是角，Kp是真的，否则是假的。第二步是使用了ID3算法并且开始选择x，x服从大多数信息关于候选的像素是否是一个角点，测量的标准就是Kp的熵值。 The entropy of K for the set P is:集合P的K的熵值如下计算 （6）The choice of x then yields the information gain:选择X然后服从信息增益 （7）Having selected the x whic

54、h yields the most information, the process is applied recursively（递归） on all three subsets i.e. xb is selected to partition Pb in to Pb,d, Pb,s,Pb,b, xs is selected to partition Ps in to Ps,d, Ps,s, Ps,b and so on, where each x is chosen to yield maximum information about the set it is applied to. T

55、he process terminates when the entropy of a subset is zero. This means that all p in this subset have the same value of Kp, i.e. they are either all corners or all non-corners. This is guaranteed to occur since K is an exact function of the learning data.已经选出了服从大多素信息的x，处理过程中对三个子集应用递归，也就是说xb是被选出来的，为了

56、将Pb分割到Pb,d, Pb,s,Pb,b, xs是被选来将Ps分成Ps,d, Ps,s, Ps,b等等。那里每个x是被选来服从应用的集合的最大信息量。当子集的熵值是零时，处理结束。这就意味着子集中的所有p有相同的Kp值，也就是它们要么全是角点，或者全部不是。这就保证了角点的出现，因为K是一个额外的功能函数关于学习资料。This creates a decision tree which can correctly classify all corners seen in the training set and therefore (to a close approximation) cor

57、rectly embodies（表现;象征;包括;包含） the rules of the chosen FAST corner detector. This decision tree is then converted into C-code, creating a long string of（一长串的） nested（嵌套） if-then-else statements which is compiled and used as a corner detector. For full optimisation（优化）, the code is compiled twice, once

58、 to obtain profiling data on the test images and a second time with arcprofiling enabled in order to allow reordering optimisations. In some cases, two of the three subtrees may be the same. In this case, the boolean test which separates them is removed.可以创造一个决策树，决策树可以正确的将训练集中的所有角进行分类，因此能够正确的表示FAST角

59、点探测器的规则。然后决策树转换为C代码，创造一长串的嵌套if-then-else的算法，然后编译和并用做角探测器。为了更加优化，代码会被编译俩次，一次是为了获得分析测试图像后得到的数据，而第二次编译允许重新将最优化值重新排序。在一些例子中，三分之二的子树将是一样的。在这种特例中，分离子树的布尔测试将会被移除。Note that since the data contains incomplete coverage of all possible corners,the learned detector is not precisely the same as the segment test

60、detector. It would be relatively straightforward to modify（修改） the decision tree to ensure that it has the same results as the segment test algorithm, however, all feature detectors are heuristic（启发式） to some degree, and the learned detector is merely a very slightly different heuristic to the segme