[link]
Summary by Desiana Nurchalifah 4 years ago
**Introduction :**
Corners, as feature cues in an image, is defined by two edge intersections. This definition has benefit in allowing precise location of the cue, although it is only valid when locality is maintained and the result is similar to the real corner location
**Related work:**
* Corner detector method present are SIFT global tracker that is using Difference of Gaussians and SURF that is using Haar wavelet to approximate Hessian determinat. These methods have drawback in high computation
* FAST method is a corner detector that performs better than conventional corner detectors such as Harris corner detection. Drawbacks of this method is that it depends on the environment, therefore decision tree needs to be always constructed from scratch (ID3 greedy algorithm)
**Approach:**
* In detecting corners, discretized circle pixels are used to be compared with the center area. A circle with 3.4 diameter is used as test mask
* Based on accelerated segment test, pixel is identified to be a corner when there are a number of pixel that has different value, either darker or lighter, than threshold of center pixel
* The number of pixel that is used in this paper is the same as FAST-9 method, which nine size segment as it has the best performance
* This number has the property to detect corners with some standard such that when different viewpoints are applied, it has the highest number of repeatability to detect corners correctly
* FAST algorithm is building ternary tree which has three possible states that are darker, lighter, or similar, added by unknown state that leads to $4^N$ configuration space, while FAST-9 has dissimilarity in the circle's thickness which is increased to 3 pixels
* Proposed corner detection describes the algorithm by testing one of the pixel with one question to pose. If a scenario of a pixel is given and question is evaluated, the next pixel and question in query is determined by the response
* This algorithm expands the configuration space by adding not lighter and not darker which produces a binary tree representation in which evaluation can be done in each of the nodes, therefore the configuration space has the size of $6^N$
* Memory is accessed by three types of cost which are second pixel comparison, same row pixel test, and other pixel test
* To make decision tree optimal, a method that has resemblance with backward induction is formulated. Configuration space is explored using Depth First Search algorithm where each leaf is described whether it has satisfy corner criteria by accelerated segment test
* Cost of each node is calculated by summation of minimum cost in each pair of child that has the positive or negative value with probability of pixel nodes both parent and child
* The algorithm calculates the probability of an image whether it has homogeneous and structured areas then proceed to make a decision tree according to it. The distribution of probability contains three probabilities that are mirror state probability and similar state probability
https://i.imgur.com/lIHh7gL.png
* Algorithm is improved to make it generic by jumping from one optimized tree to another based on the configuration of the respected leaf once it has termination condition based on the corner criteria
* This switching method has no cost as it happens in a leaf. However, it affects the time by one test delay. Thus, AGAST can only perform worse than FAST once it needs to jump between either homogeneous or heterogeneous pixels consecutively
* Corner detection is compared using three pixel mask sizes that are 4, 12 and 16. Comparison is done by applying Gaussian noise and blur to database of variety viewpoints of checkerboard database
* As limited computation using conventional computers are present, four state configuration space is used using three different arc lengths that are 9, 10 and 11
* As the mask and arc length enlarged, the more features found. Small arc defines the location of the real corner
* Large pattern leads to slower computation as it has more process to be done in order to detect the corner or evaluating features and it needs more advanced computing memory
* Smaller pattern can also lead to elimination of feature detection as the features located near to each other, therefore in smaller feature, post processing technique is removed
* When database is added by Gaussian blur and noise, the combination of pixel mask of 16 and arc length of 9 is more robust against the disturbance, therefore, repeatability is controlled by arc
* Decision tree is also evaluated by computing the response time of corner detection. This is done by calculating the tests number that has possible pixel arrangement in a mask
* Pixels arrangements that have close similarities are grouped. By observing the standard deviation, the group with large number of pixels that are alike has unbalanced decision tree. This happens as possible pixel arrangements are limited. Observed as follows:
https://i.imgur.com/DLqCXhy.png
* However, when one tree is used, adaptive tree has better performance than the conventional method
* In comparison for trees that has different weight, the algorithm that jumps between trees or AGAST is optimized when the value of the weights are 0.1 and 1/3
* Performance of AGAST is also tested by comparison with FAST-9 where uniform probability distribution are used to make the trees
* Both algorithm are tested on five scenes, which are laboratory, outdoor, indoor, aerial, and medical. The optimized tree can speed the corner detection up for 13$\%$ while AGAST can speed up in the range of 23$\%$ to over 30$\%$
**Paper contributions**
* Paper provides an improved FAST corner detector that is able to dynamically adapt with its environment while also processing an image input
* AGAST method is improving its predecessors method in saving time spent to process the image and also memory that is being used
* It is also able to find more keypoints in corner detection

more
less