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.
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 . 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)
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
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
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
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.
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.
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 . 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.
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.
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
1 for the
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.
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.
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.
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.
 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.
 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.