Features from accelerated segment test: Difference between revisions

Revision as of 13:47, 23 July 2023

Latest revision as of 21:34, 25 June 2024

(3 intermediate revisions by 2 users not shown)

Line 18:

[[File:FAST Corner Detector.jpg|thumb|The pixels used by the FAST corner detector]]

FAST corner detector uses a circle of 16 pixels (a [[Midpoint circle algorithm|Bresenham circle]] of radius 3) to classify whether a candidate point p is actually a corner. Each pixel in the circle is labeled from integer number 1 to 16 clockwise. If a set of N contiguous pixels in the circle are all brighter than the intensity of candidate pixel p (denoted by I_p) plus a threshold value t or all darker than the intensity of candidate pixel p minus threshold value t, then p is classified as corner. The conditions can be written as:

*Condition 1: A set of N contiguous pixels S, <math>\forall x \in S</math>, the intensity of x > I_p + threshold, or <math>I_x > I_p + t</math> (a dark corner on a bright background)

*Condition 2: A set of N contiguous pixels S, <math>\forall x \in S</math>, <math>I_x < I_p - t</math> (a bright corner on a dark background)

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 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. A high-speed test method could be applied to exclude non-corner points.

Line 55:

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 (programming language)|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 compliedcompiled 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.

Line 168:

* {{cite journal | last=Rosten | first=Edward |author2=Reid Porter |author3=Tom Drummond | title=FASTER and better: A machine learning approach to corner detection | journal=IEEE Transactions on Pattern Analysis and Machine Intelligence

| arxiv=0810.2434| year=2010 | doi=10.1109/TPAMI.2008.275 | pmid=19926902 | volume=32| issue=1 | pages=105–119| s2cid=206764370 }}

* {{cite book | last=Rosten | first=Edward |author2=Tom Drummond | title=Computer Vision – ECCV 2006 | chapter=Machine learningLearning for highHigh-speedSpeed cornerCorner detectionDetection | journal=European Conference on Computer Vision

| url=http://edwardrosten.com/work/rosten_2006_machine.pdf

| year=2006 | doi=10.1007/11744023_34 | volume=1| pages=430–443| series=Lecture Notes in Computer Science | isbn=978-3-540-33832-1 | citeseerx=10.1.1.64.8513 | s2cid=1388140 }}