FAST Corner Detection

This example shows how to perform corner detection using the features-from-accelerated-segment test (FAST) algorithm. The algorithm is suitable for FPGAs.

Corner detection is used in computer vision systems to find features in an image. It is often one of the first steps in applications like motion detection, tracking, image registration and object recognition.

The FAST algorithm determines if a corner is present by testing a circular area around the potential center of the corner. The test detects a corner if a contiguous section of pixels are either brighter than the center plus a threshold or darker than the center minus a threshold. For another corner detection algorithm for FPGAs, see the Harris Corner Detection example.

In a software implementation the FAST algorithm allows for a quick test to rule out potential corners by only testing the four pixels along the axes. Software algorithms only perform the full test if the quick test passes. A hardware implementation can easily perform all the tests in parallel so a quick test is not particularly advantageous and is not included in this example.

The FAST algorithm can be used at many sizes or scales. This example detects corners using a sixteen-pixel circle. In these sixteen pixels, if any nine contiguous pixel meet the brighter or darker limit then a corner is detected.

MATLAB FAST Corner Detection

The Computer Vision Toolbox™ includes a software FAST corner detection algorithm in the detectFASTFeatures function. This example uses this function as the behavioral model to compare against the FAST algorithm design for hardware in Simulink®. The function has parameters for setting the minimum contrast and the minimum quality.

The minimum contrast parameter is the threshold value that is added or subtracted from the center pixel value before comparing to the ring of pixels.

The minimum quality parameter controls which detected corners are "strong" enough to be marked as actual corners. The strength metric in the original FAST paper is based on summing the differences of the pixels in the circular area to the central pixel [2]. Later versions of this algorithm use a different strength metric based on the smallest change in pixel value that would make the detection no longer a corner. detectFastFeatures uses the smallest-change metric.

This code reads the first frame of video, converts it to gray scale, and calls detectFASTFeatures. The result is a vector of corner locations. To display the corner locations, use the vector to draw bright green dots over the corner pixels in the output frame.

v = VideoReader('rhinos.avi');
I = rgb2gray(readFrame(v));
% create output RGB frame
Y = repmat(I,[1 1 3]);
corners = detectFASTFeatures(I,'minContrast',15/255,'minQuality',1/255);
locs = corners.Location;
for ii = 1:size(locs,1)
    Y(floor(locs(ii,2)),floor(locs(ii,1)),2) = 255; % green dot
end
imshow(Y)

Limitations of the FAST Algorithm

Other corner detection methods work very differently from the FAST method and a surprising result is that FAST does not detect corners on computer generated images that are perfectly aligned to the x and y axes. Since the detected corner must have a ring of darker or lighter pixel values around the center that includes both edges of the corner, crisp images do not work well. For example, try the FAST algorithm on the input image used in the Harris Harris Corner Detection example.

I = imread('cornerboxes.png');
Ig = rgb2gray(I);
corners = detectFASTFeatures(Ig,'minContrast',15/255,'minQuality',1/255)

corners = 

  0x1 cornerPoints array with properties:

    Location: [0x2 single]
      Metric: [0x1 single]
       Count: 0

You can see that the function detected zero corners. This because the FAST algorithm requires a ring of contrasting pixels more than halfway around the center of corner. In the computer generated image, both edges of a box at a corner are in the ring of pixel used, so the test for a corner fails. A work-around to this problem is to add blur (by applying a Gaussian filter) to the image so that the corners are less precise but can be detected. After blurring, the FAST algorithm now detects over 100 corners.

h = fspecial('gauss',5);
Ig = imfilter(Ig,h);
corners = detectFASTFeatures(Ig,'minContrast',15/255,'minQuality',1/255)
locs = corners.Location;
for ii = 1:size(locs,1)
    I(floor(locs(ii,2)),floor(locs(ii,1)),2) = 255; % green dot
end
imshow(I)

corners = 

  136x1 cornerPoints array with properties:

    Location: [136x2 single]
      Metric: [136x1 single]
       Count: 136

Behavioral Model for Verification

The Simulink model uses the detectFASTFeatures function as a behavioral model to verify the results of the hardware algorithm. You can use a MATLAB Function block to run MATLAB code in Simulink.

modelname = 'FASTCornerHDL';
open_system(modelname);
set_param(modelname,'SampleTimeColors','on');
set_param(modelname,'SimulationCommand','Update');
set_param(modelname,'Open','on');
set(allchild(0),'Visible','off');

The code in a MATLAB Function block must either generate C code or be declared extrinsic. An extrinsic declaration allows the specified function to run in MATLAB while the rest of the MATLAB Function block runs in Simulink. The detectFASTFeatures function does not support code generation, so the MATLAB Function block must use an extrinsic helper function.

For frame-by-frame visual comparison, and the ability to vary the contrast parameter, the helper function takes an input image and the minimum contrast as inputs. It returns an output image with green dots marking the detected corners.

function Y = FASTHelper(I,minContrast)
Y = I;
corners = detectFASTFeatures(I(:,:,1),'minContrast',double(minContrast)/255,'minQuality',1/255);
locs = corners.Location;
for ii = 1:size(locs,1)
    Y(floor(locs(ii,2)),floor(locs(ii,1)),2) = 255; % green dot
end

end

The MATLAB Function block must have a defined size for the output array. A fast way to define the output size is to copy the input to the output before calling the helper function. This is the code inside the MATLAB Function block:

function Y = fcn(I,minContrast)
    coder.extrinsic('FASTHelper');
    Y = I;
    Y = FASTHelper(I,minContrast);
end

Implementation for HDL

The FAST algorithm implemented in the Vision HDL Toolbox Corner Detector block in this model tests 9 contiguous pixels from a ring of 16 pixels, and compares their values to the center pixel value. A kernel of 7x7 pixels around each test pixel includes the 16-pixel ring. The diagram shows the center pixel and the ring of 16 pixels around it that is used for the test. The ring pixels, clockwise from the top-middle, are

  indices = [22 29 37 45 46 47 41 35 28 21 13 5 4 3 9 15];

These pixel indices are used for selection and comparison. The order must be contiguous, but the ring can begin at any point.

After computing corner metrics using these rings of pixels, the algorithm determines the maximum corner metric in each region and suppresses other detected corners. The model then overlays the non-suppressed corner markers onto the original input image.

The hardware algorithm is in the FASTHDLAlgorithm subsystem. This subsystem supports HDL code generation.

open_system([modelname '/FASTHDLAlgorithm'],'force');

Corner Detection

To determine the presence of a corner, look for all possible 9-pixel contiguous segments of the ring that have values either greater than or less than the threshold value.

In hardware, you can perform all these comparisons in parallel. Each comparator block expands to 16 comparators. The output of the block is 16 binary decisions representing each segment of the ring.

Non-Maximal Suppression

The FAST algorithm identifies many, many potential corners. To reduce subsequent processing, all corners except the corners with the maximum corner metric in a particular region can be removed or suppressed. There are many algorithms for non-maximal suppression suitable for software implementation, but few suitable for hardware. In software, a gradient-based approach is used, which can be resource intensive in hardware. In this model a simple but very effective technique is to compare corner metrics in a 5x5 kernel and produce a boolean result. The boolean output is true if the corner metric in the center of the kernel is greater than zero (i.e. it is a corner) and also it is the maximum of all the other corner metrics in the 5x5 region. The greater-than-zero condition matches setting minQuality to 1 for the detectFASTFeatures function.

Since the processing of the pixel stream is from left to right and top to bottom, the results contain some directional effects, such as that the detected corners do not always perfectly align with the objects. The NonMaxSuppress subsystem includes a constant block that allows you to disable suppression and visualize the complete results.

open_system([modelname '/FASTHDLAlgorithm/NonMaxSuppress'],'force');

Align and Overlay

At the output of the NonMaxSuppress subsystem, the pixel stream includes markers for the strongest corner in each 5x5 region. Next, the model realigns the detected corners with the original pixel stream using the Pixel Stream Aligner block. After the original stream and the markers are aligned in time, the model overlays a green dot on the corners. The Overlay subsystem contains an alpha mixer with constants for the color and alpha values.

The output viewers show the overlaid green dots for corners detected. The Behavioral Video Viewer shows the output of the detectFastFeatures function, and the HDL Video Viewer shows the output of the HDL algorithm.

Going Further

The non-maximal suppression algorithm could be improved by following gradients and using a multiple-pass strategy, but that computation would also use more hardware resources.

Conclusion

This example shows how to start using detectFASTFeatures in MATLAB and then move to Simulink for the FPGA portion of the design. The hardware algorithm in the Corner Detector block includes a test of the ring around the central pixel in a kernel, and a corner strength metric. The model uses a non-maximal suppression function to remove all but the strongest detected corners. The design then overlays the corner locations onto the original video input, highlighting the corners in green.

References

[1] Rosten, E., and T. Drummond. "Fusing Points and Lines for High Performance Tracking" Proceedings of the IEEE International Conference on Computer Vision, Vol. 2 (October 2005): pp. 1508-1511.

[2] Rosten, E., and T. Drummond. "Machine Learning for High-Speed Corner Detection" Computer Vision - ECCV 2006 Lecture Notes in Computer Science, 2006, 430-43. doi:10.1007/11744023_34.