FAST Corner Detector (Simplified)

hardPROFeature DetectorsFeaturesCV: Feature Detection and Matching

Implement a simplified version of the FAST (Features from Accelerated Segment Test) corner detector.

FAST detects corners by examining pixels on a circle around each candidate point. A point is a corner if a sufficient number of contiguous pixels on the circle are all brighter (or all darker) than the center by at least a threshold.

The algorithm uses a circle of 16 pixels at radius 3:

Positions: (-3,0), (-3,1), (-2,2), (-1,3), (0,3), (1,3), (2,2), (3,1), (3,0), (3,-1), (2,-2), (1,-3), (0,-3), (-1,-3), (-2,-2), (-3,-1)

For each pixel:

Get the intensity of all 16 circle pixels
Check if N or more contiguous pixels are all brighter than center + threshold
OR check if N or more contiguous pixels are all darker than center - threshold
If either condition is met, it's a corner

Note: The circle wraps around (position 15 is contiguous with position 0).

Example

Input

image = [[50,50,50,50,50,50,50],
        [50,50,50,50,50,50,50],
        [50,50,50,50,50,50,50],
        [50,50,50,200,50,50,50],
        [50,50,50,50,50,50,50],
        [50,50,50,50,50,50,50],
        [50,50,50,50,50,50,50]]
threshold = 40
n = 12

Output

[(3, 3)]

Reasoning

Inputs: image is a $7 \times 7$ grid, all $50$ except one pixel of $200$ at row $3$ , column $3$ . threshold $= 40$ is the required gap, and n $= 12$ is the run length needed.
Which centres qualify: a radius-3 circle only fits when both row and column lie in $[3, 7-3)$ , so $(3, 3)$ is the one and only candidate in this image.
Bright and dark bands: with centre $I_c = 200$ , a circle pixel counts as brighter if $I_p > 200 + 40 = 240$ and darker if $I_p < 200 - 40 = 160$ .
The circle: all 16 offsets land on pixels of value $50$ . None exceed $240$ , but every one satisfies $50 < 160$ , so the darker run has length $16 \ge 12$ . The centre is a corner.
Output: [(3, 3)], a list of (row, col) pairs.
Notice: both inequalities are strict. With threshold $= 150$ the dark band would need $I_p < 50$ , and $50 < 50$ is false, so the same image would return [].

Constraints

image is a 2D grayscale image (integer values)
threshold is the intensity difference required
n is the number of contiguous pixels required (default 12)
Return list of (row, col) corner coordinates
Only check pixels where a full circle fits (row and col >= 3 and < size-3)

Learn this in

Feature Detection and MatchingCV Study Plan

More from CV: Feature Detection and Matching

Circle Hough Transformhard Canny Edge Detection Pipelinehard Hamming Distance Matcherhard Simple BRIEF Descriptormedium Point to Hough Spaceeasy

Concept primerPREVIEW

FAST (Features from Accelerated Segment Test) is a corner detector: it decides, for each pixel, whether the local intensity pattern looks like a “corner.” Instead of computing gradients like Harris, FAST uses a simple intensity comparison test on pixels arranged on a circle of radius 3 around the candidate pixel. The idea: at a true corner, some arc of pixels on this circle will all be significantly brighter (or darker) than the center, forming a high-contrast “segment.”

The “accelerated” part comes from two design choices:

Use only 16 discrete positions on the circle.
Use simple integer comparisons (brighter than center + threshold, or darker than center – threshold), which are cheap to compute. In full FAST, there are additional speedups (like checking a subset of pixels first and using machine-learned decision trees), but your problem is a simplified, straightforward version of the test.

Conceptually, this is a local, binary decision problem on a fixed-size neighborhood: for each pixel you consider a constant number of surrounding pixels, classify each as bright/dark/similar relative to the center, and then check for a long enough contiguous run (with circular wrap-around) of bright or dark pixels. It’s similar in spirit to run-length checks in 1D arrays, but applied to a fixed circular ordering.

1. Background Knowledge (Key Concepts)

Corner vs edge vs flat region
Flat region: all nearby pixels have similar intensity.
Edge: intensities change strongly in one direction but not the orthogonal one.
Corner: intensities change in both directions; if you look around a circle, at some arc the pixels will be consistently brighter or darker than the center.
Thresholding and contrast The threshold controls how much brighter/darker a circle pixel must be compared to the center to “count.” A larger threshold yields fewer, stronger corners; a smaller threshold yields more, noisier corners.
Contiguous segment on a circle The 16 circle pixels are in a fixed order. A candidate is a corner if there is a run of N or more adjacent pixels in that circular order that all satisfy the bright condition or all satisfy the dark condition. “Circular” means index 15 and 0 are neighbors.

2. Algorithm / Approach Pattern

At a high level:

Iterate over candidate pixels in the image (skip borders where the radius-3 circle would go out of bounds).
For each candidate:

Sample the 16 circle pixels at the given offsets.
Compare their intensities to the center pixel with the given threshold.
Produce a small 1D array of 16 “labels” (e.g., -1 = darker enough, 0 = similar, +1 = brighter enough).

Check for runs:

Is there any contiguous run of length ≥ N of +1 (bright) in the circular sequence?
Or any contiguous run of length ≥ N of -1 (dark)?

If yes, mark the center as a corner; otherwise, not a corner.

Algorithmically, this is:

A fixed-neighborhood scan (common in image processing).
A run-length / sliding-window check on a small circular array of size 16.
Optionally, a boolean corner map or a list of corner coordinates as output.

3. Step-by-Step Strategy to Implement

Assume:

Grayscale image img[h][w] (e.g., 8-bit).
Threshold t.
Segment length N (often 9 or so in FAST variants, but problem will define it).

Step 1: Define circle offsets

PRO

Continue the full explanation

You're reading the free preview. Unlock the complete walkthrough, the code editor, test runner and reference solution with Premium.

PRO

Editor locked

The code editor is locked for Pro problems. It is only available for free problems. Please upgrade to gain access to the code editor for all problems.

solution.py

Python 3.13

Test results