FAST Corner Detector (Simplified)
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:
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[(3, 3)]
Checking pixel (3,3) with intensity 200:
Circle pixels around (3,3) all have intensity 50.
- Checking for N=12 contiguous darker pixels:
- Each circle pixel (50) is 50 - 200 = -150 less than center
- Since 50 < 200 - 40 = 160, all 16 pixels are "darker"
- We need 12 contiguous darker pixels
- All 16 are darker, so we have 16 ≥ 12 contiguous darker pixels ✓
Result: (3,3) is a corner because the center is much brighter than its surroundings.
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)
More from CV: Feature Detection and Matching
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
Continue the full explanation
You're reading the free preview. Unlock the complete walkthrough, the code editor, test runner and reference solution with Premium.
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.