Features from accelerated segment test

lastmod 2019-12-06created 2019-12-066 edits

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 2006. 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.

About

FAST (Features from Accelerated Segment Test) is another algorithm for finding corners. As the name suggests, it is known for fast computation.

1. Draw a circle with a radius of 3 pixels centered on a pixel 𝑝,
2. look at the values of the 16 pixels on that circle to find corners.
3. If there are 𝑛 or more consecutive pixels that are brighter or darker than 𝑝 by at least the threshold, 𝑝 is judged to be a Corner.

Depending on 𝑛, several versions such as FAST-9, FAST-10, FAST-11, and FAST-12 are possible, and the FAST paper reports that FAST-9 performs best. However, this counting approach judged too many pixels to be corners, and the extracted corners could also change depending on how the 16 pixels are ordered, among other reasons. So instead of simply counting to judge corners, FAST uses a Decision Tree to decide whether a pixel is a corner. Here, each of the 16 pixels is converted to brighter than 𝑝 by more than the threshold, darker than 𝑝 by more than the threshold, or similar in brightness to 𝑝, and represented as a 16-dimensional vector; the vectors for all pixels in all images are stacked to train the tree. The target value is whether the point is a keypoint or not, and this must be labeled. Another problem is that when one point is judged to be a corner, the surrounding pixels are also recognized as corners; this was solved with a post-processing step called non-maximal suppression. It computes a value representing cornerness and, based on it, selects as a corner only the pixel with the highest cornerness value among neighboring pixels.

Example

The following code is an example of finding the corners of a checkerboard image with FAST.

fast = cv2.FastFeatureDetector_create()
kps = fast.detect(img, None)
img2 = cv2.drawKeypoints(img, kps, img, color=(255, 255, 255))

print("기준값: ", fast.getThreshold())
print("nonmaxSuppression: ", fast.getNonmaxSuppression())
print("nonmaxSuppression 후처리 후, 추출된 전체 특징점: ", len(kps))
plt.figure(figsize=(7,7))
plt.imshow(img2, cmap='gray')
plt.title("FAST 로 찾은 Corner")
plt.axis("off")
plt.show()

See also

• Feature detection
• Oriented FAST and rotated BRIEF (ORB)
• Binary Robust Independent Elementary Features (BRIEF)
• Harris corner detection

Favorite site

• Wikipedia (en) Features from accelerated segment test
• [Recommended] Data Science School - Image feature extraction ¹

References