Features from accelerated segment test: Difference between revisions

Revision as of 17:19, 1 June 2013

Revision as of 18:00, 1 June 2013

Line 1:

{{abbreviations|date=April 2012}}

'''Features from Accelerated Segment Test (FAST)''' is a corner detection method, which could be used to extract feature points and later used to track and map objects in many [[computer vision]] tasks. FAST corner detector was originally developed by Edward Rosten and Tom Drummond. The most promising advantage of FAST [[corner detector]] is its computational efficiency. Referring to its name, it is fast and indeed it is faster than many other well-known feature extraction methods, such as [[Differencedifference of GaussianGaussians]] (DoG) used by [[Scale-invariant feature transform|SIFT]], [[SUSAN]] and [[Harris affine region detector|Harris]]. Moreover when machine learning method is applied, a better performance could be achieved which takes less time and computational resources. FAST corner detector is very suitable for real-time video processing application because of high-speed performance.

== Segment test detector ==

Line 7:

*Condition 1: A set of N contiguous pixels S, ∀ x ∈ S, the intensity of x (I_x) > I_p + threshold t

*Condition 2: A set of N contiguous pixels S, ∀ x ∈ S, I_x < I_p - t

So when either of the two conditions is met, candidate p can be classified as a corner. There is a tradeoff of choosing N, the number of contiguous pixels and the threshold value t. On the one hand, the number of detected corner points should not be too many; on the other hand, the high performance should not be achieved by sacrificing computational efficiency. Without the improvement of [[machine learning]], N is usually chosen as 12. Since that aA high -speed test method could be applied to exclude non-corner points.

== High -speed test ==

The high -speed test for rejecting non-corner points is operated by examining 4 example pixels, namely pixel 1, 9, 5 and 13. Because there should be at least 12 contiguous pixels that are whether all brighter or darker than the candidate corner, so there should be at least 3 pixels out of these 4 example pixels that are all brighter or darker than the candidate corner. Firstly pixels 1 and 9 are examined, if both I₁ and I₉ are within [I_p - t, I_p + t], then condidate p is not a corner. Otherwise pixels 5 and 13 are further examined to check whether three of them are brighter than I_p + t or darker than I_p - t. If there exists 3 of them that are either brighter or darker, the rest pixels are then examined for final conclusion. And according to the inventor in his first paper,<ref>Edward Rosten, [http://edwardrosten.com/work/rosten_2005_annotations.pdf Real-time Video Annotations for Augmented Reality]</ref> on average 3.8 pixels are needed to check for candidate corner pixel. Compared with 16 pixels for each candidate corner, 3.8 is really a great reduction which could highly improve the performance.

However, there are several weaknesses for this test method: