Features from accelerated segment test
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.
≈ 3 min read
Names in other languages
No names in other languages are held for this entry yet.
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
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. The FAST corner detector was originally developed by Edward Rosten and Tom Drummond, and was published in 20061.
The most promising advantage of the FAST corner detector is its computational efficiency. Referring to its name, it is indeed faster than many other well-known feature extraction methods, such as difference of Gaussians (DoG) used by the SIFT, SUSAN and Harris detectors.
Moreover, when machine learning techniques are applied, superior performance in terms of computation time and resources can be realised. The FAST corner detector is very suitable for real-time video processing application because of this high-speed performance.
P d = {p ∈ P : S p→x = d } P s = {p ∈ P : S p→x = s } P b = {p ∈ P : S p→x = b } Secondly, a decision tree algorithm, the ID3 algorithm is applied to the 16 locations in order to achieve the maximum information gain. Let K p be a boolean variable which indicates whether p is a corner, then the entropy of K p is used to measure the information of p being a corner.
For a set of pixels Q, the total entropy of K Q (not normalized) is: H(Q) = ( c + n ) log 2 ( c + n ) - clog 2 c - nlog 2 n where c = |{ i ∈ Q: K i is true}| (number of corners) where n = |{ i ∈ Q: K i is false}| (number of non-corners) The information gain can then be represented as: H g = H(P) - H(P b ) - H(P s ) - H(P d ) A recursive process is applied to each subsets in order to select each x that could maximize the information gain. For example, at first an x is selected to partition P into P d , P s , P b with the most information; then for each subset P d , P s , P b , another y is selected to yield the most information gain (notice that the y could be the same as x ). This recursive process ends when the entropy is zero so that either all pixels in that subset are corners or non-corners.
This generated decision tree can then be converted into programming code, such as C and C++, which is just a bunch of nested if-else statements. For optimization purpose, profile-guided optimization is used to compile the code. The compiled code is used as corner detector later for other images.
Notice that the corners detected using this decision tree algorithm should be slightly different from the results using segment test detector. This is because that decision tree model depends on the training data, which could not cover all possible corners.
Text derived from https://en.wikipedia.org/w/index.php?oldid=1373743894 under CC BY-SA 4.0; modifications have been made.
References
- ↩Wikipedia “Features from accelerated segment test” publication date (×1) · confidence 0.95 revision URL