machine learning for high-speed Corner detection

所需积分/C币:17 2015-08-12 06:49:23 1.78MB PDF
收藏 收藏
举报

FAST检测器论文英文版,对各种角点检测算法进行了详细的比较
Machine learning for speed corner detection speeds up computation by a factor of about two, Compared to the striaghtforward implementation of Gaussian convolution 13 It is noted in [14] that the LoG is a particularly stablc scalc-spacc kcrncl Scalc-spacc techniques have also bccn combined with the Harris approach in [15 which computes Harris corners at multiple scales and retains only those which are also optima of the LoG response across scales Recently, scale invariance has been extended to consider features which 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 di rection rapidly. Several techniques were developed which involved detecting and chaining edges with a view to finding corners in the chained edge by analysing the 18],fn xima of curvature [19, 20, 21, change or change in appearance 23]. Others avoid chaining edges and instead look for maxima of curvature[24] or change in direction (25 at places where the gradient 1s lar Another class of corner detectors work by examining a small patch of an im age to see if it "looks"like a corner. Since second derivatives are not computed,a noisc rcduction stcp(such as Gaussian smoothing) is not rcquircd Conscquently these corner detectors are computationally efficient since only a small number pixels are examined for each corner detected. A corollary of this is that they tend 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 The Illethod presented in 26 assumes that d 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 in27 where a method for calculating the corner strength 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) va lue. Pixels closer in value to the nucleus receive a higher weighting. This measure is known as the USAN (the Univalue Segment Assimilating 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) arc sclcctcd from thc remaining candidates Trajkovic and Hedley 2S use a similar idea: a patch is not self-similar if pixels generally look different from the centre of the patch. This is measured by considering a circle. fc is the pixel value at the centre of the circle, and fp and fp, are the pixel values at either end of a diameter line across the circle. The response fullction is defined as min fp-fc)-+(p-fc This can only be large in the case where there corner. The test is performed on a Brcscnham circlc Since the circle is discretized, lincar or circular interpo- lation is used in between discrete orientations in order to give the detector a more isot ropic response. To this end, the aut hors present a. met hod whereby the Edward Rosten and Tom Drummond E 1. 12 point t test detect ic tch. The highlighted squares are the pixels used in the corner detection. The pixel at p is the centre of a candidate corner. The arc is indicated by the dashed line passes through 12 contiguous els which are brighter than p by more than the threshold minimum response function at all interpolated positions between two pixels can be efficiently coMputed. CuIllputing the response function requires performing 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 the method furthe this fast, check is first applied at a. coarse scale 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 scale can be varied by changing the size of the area which is examined for radial symmetry. An alternative method of examining a small patch of an image to see if it looks like a corner is to usc machinc learning to classify 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 8x 8 window. This is applied to images after edge detection and thinning. It is shown how the neural nlet learned a inore general representation and was able to detect corners at a variety of angle 2 High-speed corner detection 2.1 FAST: Features from Accelerated Segment Test The segment test criterion operates by considering a circle of sixteen pixels round the corner candidate p. The origina l detector[ 2, 3 classifies p as acorner Machine learning for speed corner detection 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 In-t. as illustratcd in Figurc 1. n was chosen to bc twelve bccausc it admits a high-spccd tost which can bc uscd to cxcludc a vcry largc numbcr 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 lp-t. If neither of these is the case, then p cannot be a corner. The full seginent test criteriOn can tlien 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 1. The high-speed test does not generalise well for n 12 2. The choice and ordering of the fast test pixels contains implicit assumptions about the distribution of feature appearance 3. Knowledge from the first 4 tests is discarded 4. Multiple fcaturcs arc dctcctcd adjacent to onc anothcr 2.2 Machine learning a corner detector Here we 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 domain) usIn segiment test criterion for T and a cOnvenient threshold. This uses a slow algorithm which for each pixel simply tests all 16 locations on the circle d it For each location on the circle E [1.16), the pixel at that position relative to p(denoted by p-7 )can have one of three states d, 1p→a≤ln-t( darker Sp-a=s, Ip-t<Ip-a<Ip+t(sir b,p+t≤lp Choosing an a and computing Sp- for all pe P(the set of all pixels in all train- ing images) partitions P into three subsets, Pa, Ps, Pb, where each p is assigned to ps Let Ko be a boolean variable which is true if p is a corner and false otherwise age 2 employs the algorithIn used in ID3 31 alld begins by selecting the at which yields the most information about whether the candidate pixel is a corner measured by thc entropy of Kp The entropy of K for the set P H(P)=(c+clog(c+c)-clog2c-clo where c=plkp is true) (number of corners) c=lplkp is falsc) (numbcr of non corners) Edward Rosten and Tom Drummond The choice of then yields the inforillation gain H(P)-H(Pd)-H(Ps)-H(Po Having selected the a which yields the most information, the process is applied recursively on all three subsets i.e. rb is selected to partition P6 in to Pt. d, Pbs P6. b, s is selected to partition Ps in to Pss, Psb and so on, where each wE is chosen to yield maxilnuIn inforlllation about the set it is applied to. The 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 This creates a decision tree which can correctly classify all corners seen in the training set and therefore(to a close approximation) correctly 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-theIl-else statements which is compiled and used as a corner detector. For full optimisation, the code is compiled twice once to obtain profiling data on the test images and a second time with arc profiling enabled in ordcr to allow rcordcring optimisations. In somc cascs, two of the three subtrees may be the same. In this case, the boolean test which separates them is removed Note that since the data contains incomplete coverage of all possible corners, the learned detector is not precisely the saille as the seginent test 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 arc hcuristic to somc dcgrcc, and thc lcarncd detector is mcrcly a vcry slightly different heuristic to the segment test detector. 2.3 Non-maximal suppression Since the segment test does not compute a corner rcsponsc function, non max imal suppression can not be applied directly to the resulting features. Conse- quently, a score function, V must be computed for each detected corner, and non-maximal suppression applied to this to remove corners which have an adja cent corner with higher v. There are several intuitive definitions for v: 1. The maximum value of n for which p is still a corner. 2. The maximum value of t for which p is still a corner 3. The sum of the absolute difference between the pixels in the contiguous arc and the centre pixel Dcfinitions 1 and 2 arc vcry highly quantised mcasurcs, and many pixels sharc the same value of these. For speed of computation, a slightly modified version 3 is used. V is given by V=max 门→→x Machine learning for high-speed corner detection Detector Opteron 2.6GHz Pentium III 850MHz % Fast n-9(non-max suppression) 6655.29 26.5 9 1.08 5.404.34 21.7 Fast n= 12(non-max suppression) 1.34 6.70 4.60 23 Fast n= 12(raw) 585431 Original FAST n= 12(non-max suppression ) 1.59 7.95 9.60 18.0 Original FAST n= 12 (raw) 1.49745925 48.5 arrIs 24.0120 166 830 DoG 60.1 45 1280 SUSAN 758379275 137.5 Table 1. Timing results for a selection of feature detectors run on fields(768 x 288 of a video sequence in milliseconds, and as a percentage of the processing budget er frame. Note that since PAL and NTSC, DV and 30|Iz vGa (common for web- cams) have approximately the same pixel rate, the percentages are widely applicable Approximately 500 fcatures per ficld are dctccted ith biht={x|lp→x≥L+t dark =II 2.4 Timing results Timing tests were performed on a 2.6GHz Opteron and an 850MHz Pentium Ill processor. The timing data is taken over 1500 monochrome fields from a PAL video source(with a resolution of 768 x 288 pixels). The learned FaSt detectors for n=9 and 12 have been compared to the original fast detector, to our implementation of the harris and dog(difference of Ga.ussians-the detector used by SIFT) and to the reference implementation of SUSAN32 As can be seen in Table 1, FAST in general offers considerably higher perfor mance than the other tested feature detectors, and the learned Fast performs up to twice as fast as the handwritten version. Importantly, it is able to gen erate an efficient detector for n= 9, which(as will be shown in Section 3) is thc most rcliablc of thc fast dctcctors. on modcrn hardware Fast consumes only a fraction of the time available during video processing, and on low power hardware, it is the only one of the detectors tested which is capable of video rate processing at all Exaininilg the decision tree shows that on average, 2.26(for n=9)and 2.39 or n= 12) questions are asked per pixel to determine whether or not it is a feature. By contrast, the handwritten detector asks on average 2.8 questions Intcrcstingly, the diffcrencc in spccd bctwcen the learned detector and the original FAST are considerably less marked on the Opteron processor compared to the Pentium TIL. We believe that this is in part due to the Opteron having Edward Rosten and Tom Drummond a dininishing cost per pixel queried that is less well Modelled by our systeIll (which assumes equal cost for all pixel accesses), compared to the Pentium III 3 A conparison of detector repeatability Although there is a vast body of work On corner detection, there is Inuch less on the subject of comparing detectors. Mohannah and Mokhtarian 33 evaluate performance by warping test images in an affine manncr by a known amount They define the ' consistency of corner numbers'as CCN=100×1.1-nn-n where nw is the number of features in the warped image and no is the number of features inl the original iImage. They also define accuracy as ACU=100× where Ty are the munber of ground truth'corners(marked by humans)and To is the number of matched corners compared to the ground truth. This unfortu- nately relies on subjectively made devisions Trajkovic and Hedley 28 define stability to be the number of strong'matches matches detected over three frames in their tracking algorithm divided by the tota.I number of corners. This measurement is clea rly d ependent on both the tracking and matching methods used, but has the advantage that it can be tested on the date used by the systein When measuring reliability, what is important is if the same real- world fea turcs arc dctccted from multiple vicws [1 This is the dcfinition which will bo uscd horc. For an imagc pair, a fcaturc is 'dctccted if isis cxtracted in onc image and appears in the second. It is '? if it is also detected nearby in the second. The repeatability is the ratio of repeated features detected features 1, the test is performed on images of planar scenes so that the relationship Detween point positiOns is a homography. Fiducial markers are projected on to che planar scene to allow accurate computation of this. By modelling the surfacc as planar and using flat textures. this tcchniquc tests the fcaturc dctcctors'ability to dcal with mostly affine warps(sincc image features are small)under realistic conditions. This test is not so well matched to our intended applica tion domain, so instead. we use a 3D surface model to compute where detected features should appear in other views (illustrated in Figure 2). This allows the repeatability of the detectors to be analysed on features caused by geometry such as corners of polyhedra, occlusions and T-junctions We also allow bas-relief textures to be modelled with a flat plane so that the repeatability can be tested under non-affine warping A margin of error must be allowed b ent Machine learning for high-speed corner detection F 2. Repeatability is tested by checking if th I-world feat d tected in different. views. a geometric model is used to compute where the features reproject to 2. The model is not perfect 3. The camera model(especially regarding radial distortion) is not perfect 4. The detector may find a maximum on a slightly different part of the corner This becomes more likely as the change in viewpoint and hence change in shape of the corner beconme large Instead of using fiducial markers, the 3D model is aligned to the scene by hand and this is then optimised using a blend of simulated annealing and gradient descent to minimise the SsD between all pairs of frames and repro jections To compute the Ssd between frame i and reprojected frame j, the position of all points in fraile i are found in fraine i. The iimlages are then bandpass filtered. High frequencies are removed to reduce noise, while low frequencies are removed to reduce the impact of lighting changes. To improve the speed of the system, the SSD is only computed using 1000 random points (as opposed to cvcry point The datasets used are shown in Figure 3, Figure 4 and Figure 5. With these datasets, we have tried to capture a wide range of corner types(geometric and L1) The repeatability is computed as the nuinber of cormers per fraine is varied For comparison we also include a scattering of random points as a baseline mea- sure, since in the limit if every pixel is detected as a corner, then the repeatability is100%. To test robustness to image noise, increasing amounts of Gaussian noise were .dded to the bas-relief dataset, it should be noted that, the noise added is in 10 Edward Rosten and Tom Drummond 黑型包段盟 Figure 3. Box dataset: photographs taken of a test rig (consisting of photographs pasted to the inside of a cuboid)with strong changes of perspective, changes in scale and large amounts of radial distortion. This tests the corner detectors on planar textures Figure 4. Maze dataset: photographs taken of a prop used in an augmented reality application. This set consists of textural features undergoing projective warps as well as geometric features. There are also significant changes of scale addition to thc significant amounts of camera noisc alrcady prescnt(from thcrmal noise. electrical interference. and etc) 4 Results and discussion Shi and Tomasi 7, derive their result for better feature detection on the as- sumption that the deformation of the features is affine. In the box and maze datasets, this assumption holds and can be seen in Figure 6B and Figure 6C the detector outperforms the harris detector. In the bas-relief dataset, this assump tion does not hold, and interestingly, the Harris detector outperforms Shi and Tomasi detector in this case Mikolajczyk and Schmid 15 evaluate the repeatability of the Harris-Laplace detector evaluated using the method in 34, where planar scenes are examined The results show that Harris-Laplace points outperform both Dog points and Harris points in repeatability. For the box dataset, our results verify that this is correct for up to about 1000 points pcr framc (typical numbers, probably commonly used); the results are somewhat less convincing in the other datasets, where points undergo non-projective changes In the sample implementation of SIFT351, approximately 1000 points are generated on the iIllages friLl the test sets. We concur that this a good choice for the number of features since this appears to be roughly where the repeatability curve for DoG features starts to fatten off Smith and Brady 27 claim that the Susan cornor dctcctor performs well in the presence of noise since it does not compute image derivatives, and hence, does not a.mplify noise. We support this claim: a l though the noise results show

...展开详情
试读 14P machine learning for high-speed Corner detection
立即下载 低至0.43元/次 身份认证VIP会员低至7折
    抢沙发
    一个资源只可评论一次,评论内容不能少于5个字
    关注 私信 TA的资源
    上传资源赚积分,得勋章
    最新推荐
    machine learning for high-speed Corner detection 17积分/C币 立即下载
    1/14
    machine learning for high-speed Corner detection第1页
    machine learning for high-speed Corner detection第2页
    machine learning for high-speed Corner detection第3页
    machine learning for high-speed Corner detection第4页
    machine learning for high-speed Corner detection第5页

    试读已结束,剩余9页未读...

    17积分/C币 立即下载 >