Research on 9-Point FAST Corner Detection in MATLAB

Click the blue text above to follow us

👨💻 Conducting research involves a deep-seated system of thought. Researchers must be logically rigorous and diligent, but effort alone is not enough. Often, leveraging resources is more important than hard work, and one must also have innovative ideas and inspirations. It is recommended that readers browse in order to avoid suddenly falling into a dark maze without finding their way back. The article may not reveal all the answers to your questions, but if it can resolve some of the doubts rising in your mind, it may just create a beautiful sunset view. If it brings you a spiritual downpour, then take the opportunity to brush off the dust that has been lying there.

Perhaps, after the rain, the world will be clearer…🔎🔎🔎

1. Introduction

The FAST (Features from Accelerated Segment Test) corner detection algorithm is an efficient feature point extraction method proposed by Edward Rosten and Tom Drummond in 2006. Compared to traditional feature point extraction methods such as SIFT, Harris, or SUSAN, the FAST algorithm has significant advantages in computational speed and real-time performance, making it very suitable for resource-constrained environments like SLAM (Simultaneous Localization and Mapping) mobile robots.

2. Basic Principles of the FAST Algorithm

The basic principle of the FAST algorithm is to use a circle with a perimeter of N pixels (usually N=16, a Bresenham circle with a radius of 3) to determine whether the center pixel P is a corner point. The determination rule is as follows:

• If there are M consecutive pixels on the circle’s circumference that are brighter (or darker) than the center pixel and the brightness difference is greater than the set threshold T, then the center pixel is determined to be a corner point.

• In the FAST-9 algorithm, M is usually set to 9, meaning that 9 consecutive pixels on the circumference must meet the above conditions.

3. Steps of the FAST-9 Algorithm

1. Pre-test: To speed up corner detection, the FAST-9 algorithm first conducts a pre-test. For each pixel, the brightness of the 1st, 5th, 9th, and 13th numbered pixels in the neighborhood circle is directly checked. Only when 3 of these 4 pixels are simultaneously greater than Ip+T or less than Ip-T, can the current pixel possibly be a corner point; otherwise, it is directly excluded.

2. Complete test: For pixels that pass the pre-test, a complete test is further conducted. This involves checking all pixels on the circumference to see if there are 9 consecutive pixels that meet the brightness condition.

3. Non-maximum suppression: To eliminate multiple adjacent feature points, non-maximum suppression is used. A score function V is calculated for each detected feature point, where V is the sum of the absolute deviations of point P and its surrounding 16 pixels. The V values of adjacent feature points are compared, and the point with the lower V value will be eliminated.

4. FAST Implementation in OpenCV

In OpenCV, the FAST algorithm is encapsulated in the <span>FastFeatureDetector</span> class. This class provides various parameter settings, including threshold T and non-maximum suppression options. Additionally, OpenCV offers three different detection modes:

• <span>TYPE_9_16</span>: 16 pixels on the circumference, with 9 consecutive pixels meeting the condition.

• <span>TYPE_7_12</span>: 12 pixels on the circumference, with 7 consecutive pixels meeting the condition.

• <span>TYPE_5_8</span>: 8 pixels on the circumference, with 5 consecutive pixels meeting the condition.

5. Advantages and Limitations of the FAST-9 Algorithm

Advantages:

• Fast speed: The FAST-9 algorithm significantly accelerates the corner detection process through pre-testing and non-maximum suppression.

• Good real-time performance: Suitable for real-time applications such as SLAM mobile robots.

Limitations:

• Sensitive to noise: The robustness of the FAST-9 algorithm may be affected when there is a lot of noise in the image.

• Lacks rotation and scale invariance: The FAST-9 algorithm is only used for rapid corner extraction and does not describe the corners, thus lacking rotation and scale invariance. This can be partially resolved through image pyramids and subsequent feature descriptors (such as ORB).

6. Conclusion

The FAST-9 corner detection algorithm, with its efficiency and real-time characteristics, has a broad application prospect in the fields of image processing and computer vision. However, to achieve better results in practical applications, parameter adjustments and subsequent processing should be combined with specific scenarios. In the future, with the continuous improvement of computational capabilities and ongoing optimization of algorithms, the performance and application range of the FAST-9 algorithm are expected to expand further.

02

Running Results

%Make image greyscale
if length(size(i)) == 3
    im =  double(i(:,:,2));
else
    im = double(i);
end

cs = fast_corner_detect_9(im, 30);
c = fast_nonmax(im, 30, cs);

image(im/4)
axis image
colormap(gray)
hold on
plot(cs(:,1), cs(:,2), 'r.')
plot(c(:,1), c(:,2), 'g.')
legend('9 point FAST corners', 'nonmax-suppressed corners')
title('9 point FAST corner detection on an image')

03

References

[1] Chang Xingzhi, Gao Liqun. Research on Morphological Corner Detection of Real Scene Images [J]. Journal of Northeast University (Natural Science Edition), 2007, 28(11):1536-1539.

[2] Wang Jinsong, Yang Shujuan, Liu Hong, et al. Research on Visible Near-Infrared Laser Beam Scattering Angle Detection System [J]. Science and Technology and Engineering, 2012, 20(6):3.

[3] Hou Lina. Research on Detection Methods and Devices for Corner Position Sensors [J]. Knowledge Output of Changchun Institute of Optics and Mechanics, Chinese Academy of Sciences, 2008.

For more resources and benefits for followers, MATLAB | Simulink | Python resources available