This is machine translation

Translated by Microsoft
Mouseover text to see original. Click the button below to return to the English version of the page.

Note: This page has been translated by MathWorks. Click here to see
To view all translated materials including this page, select Country from the country navigator on the bottom of this page.

FAST Corner Detection

This example shows how to perform corner detection using the features-from-accelerated-segment test (FAST) algorithm. This algorithm is an alternative to the Harris Corner Detection example. 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.

In a software implementation this 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 twelve contiguous pixel meet the brighter or darker limit then a corner is detected.

MATLAB FAST Corner Detection

The Computer Vision System 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 three-quarters 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 this model tests 12 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');

To extract the 7x7 kernel, use the Line Buffer block with the neighborhood size set to 7x7. The Line Buffer block returns a seven-pixel column, and a control signal that you connect to a shift register to build the 7x7 area. Use the Tapped Delay block to implement the shift register. The Tapped Delay block does not accept vector input, so the model uses a For Each subsystem. The For Each subsystem builds a single channel of tapped delay and allows for automatic vector expansion. The output of the shift register is a vector of 49 pixels representing the 7x7 kernel area.

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

Computation Kernel

The FASTKernel subsystem selects the center pixel and the 16-pixel ring from the vector of 49 pixels produced by the KernelExtraction subsystem. The selector blocks use the pixel indices noted above.

Because of the indices selected, there are a few kernel registers that are not needed in the hardware implementation. These registers are the stored pixels after the ring pixels on the first, second, sixth, and seventh lines of the kernel. Since their outputs are not used later on in the design, HDL synthesis tools will prune these registers from the hardware implementation.

Next, the minimum contrast threshold value is both added to and subtracted from the center pixel value. This creates a "dead band" or hysteresis region around the center pixel value and is a key feature of the FAST algorithm. For better hardware performance, the design uses pipeline registers after addition and subtraction.

The subsystem then checks the ring pixels for the corner conditions, which is described in more detail in the next section.

The FASTKernel subsystem also calculates a corner strength metric using the sum-of-absolute-difference (SAD) value of all the pixels in the test ring, as suggested in [2]. This metric is used for the example because it is easy to implement in hardware. Later work calculates the corner metric as the smallest change to any value in the ring that would make the center point not be a corner. The hardware algorithm in the model uses SAD metric and the detectFASTFeatures function uses the smallest-change metric, so there will be differences between the two results.

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

Corner Detection

The next step to determine the presence of a corner is to look for all possible 12-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.

The AnyCorner blocks select and test regions of twelve contiguous bits. There are sixteen ways to select twelve contiguous bits on the ring: one section that starts at each of the ring pixels. Each section can represent a corner. For each section, the AnyCorner block ANDs the bits together and then ORs those results to determine if there is a corner present.

The model does this check for both the greater-than-or-equal-to path and the less-than-or-equal-to path. The blocks in each path are identical. There are pipeline registers at the output of the AnyCorner blocks.

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

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 minQuality parameter is not used in this model, but could easily be passed to both the software and hardware versions as a parameter. The corner metric could be changed from SAD to the minimal-change algorithm used by detectFASTFeatures, but it would be less efficient for FPGA implementation. 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 includes a test of the ring around the central pixel in a kernel, and a corner strength metric. The algorithm 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.