Simple BRIEF Descriptor

mediumPROFeature DescriptorsFeaturesCV: Feature Detection and Matching

Implement a simplified BRIEF (Binary Robust Independent Elementary Features) descriptor, a type of feature descriptor used in computer vision to describe the appearance of an image patch. This descriptor is essential for tasks like image matching and object recognition.

The BRIEF descriptor creates binary strings by comparing pixel intensities at predefined point pairs. This process involves computing a series of binary tests, where each test compares the intensity of two pixels. The result of each comparison is a single binary digit.

Here are the steps to compute the BRIEF descriptor:

Select a set of predefined point pairs $(p_i, q_i)$ .
Compare the pixel intensities at each pair of points.
Record the result of each comparison as a binary digit.

b_i = \begin{cases} 1 & \text{if } I(p_i) < I(q_i) \\ 0 & \text{otherwise} \end{cases}

This technique is widely used in image processing and object detection applications.

Example

Input

patch = 31×31 grayscale patch
pairs = [((15,10), (15,20)), ((10,15), (20,15)), ...]

Output

[1, 0, 1, 1, 0, ...]

Reasoning

Inputs: patch is a $31 \times 31$ grid of grayscale intensities around a keypoint; pairs is a list of point pairs $(p_i, q_i)$ , each point written as (row, column). The sample patch isn't a concrete array, so the intensities below are illustrative.
Pair 0, $p_0 = (15, 10)$ and $q_0 = (15, 20)$ : same row, columns 10 and 20. With $I(p_0) = 100$ and $I(q_0) = 150$ , we have $100 < 150$ , so $b_0 = 1$ .
Pair 1, $p_1 = (10, 15)$ and $q_1 = (20, 15)$ : same column, rows 10 and 20. With $I(p_1) = 120$ and $I(q_1) = 80$ , the test $120 < 80$ fails, so $b_1 = 0$ .
The remaining pairs give $b_2 = 1$ , $b_3 = 1$ , $b_4 = 0$ the same way, and the bits in pair order form [1, 0, 1, 1, 0, ...]: one bit per pair, so 256 pairs give a 256-bit descriptor.
Notice the test is strict: if $I(p_i) = I(q_i)$ the bit is 0, so a perfectly flat patch produces all zeros.

Constraints

patch: Image patch centered on keypoint (31×31)
pairs: List of ((y1,x1), (y2,x2)) point pairs, each point as (row, col)
Return: Binary descriptor as list of 0/1

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 Point to Hough Spaceeasy Edge Non-Maximum Suppressionmedium

Concept primerPREVIEW

Background Knowledge

Feature descriptors convert a small image patch around a keypoint into a vector that captures its local appearance, so that the same physical point can be recognized across different images. Traditional descriptors like SIFT or SURF use real-valued gradients; binary descriptors like BRIEF instead use simple intensity comparisons, which makes them much faster and more compact.

BRIEF (Binary Robust Independent Elementary Features) works by sampling pairs of pixel locations inside a patch and comparing their intensities: each comparison gives one bit of the descriptor. Collecting many such comparisons (e.g., 256) yields a binary string that can be matched efficiently using Hamming distance (counting differing bits). BRIEF is not inherently scale- or rotation-invariant, which is why algorithms like ORB wrap BRIEF with an oriented, scale-aware keypoint detector.

Algorithm / General Approach

The general pattern for a (simplified) BRIEF descriptor:

For each keypoint, extract a fixed-size patch around it (e.g., 31×31).
Use a predefined list of point pairs $(p_i, q_i)$ inside that patch.
For each pair, compare the intensity at those two positions:
if $I(p_i) < I(q_i)$ , set bit $i$ to 1, else 0.
Pack all bits into a compact binary (or integer/byte) representation to form the descriptor.
Matching between descriptors uses Hamming distance instead of Euclidean.

In coding-challenge form, you are usually given:

the image (or patch),
keypoint coordinates,
and the list of point pairs (relative offsets), and you must output descriptors for all keypoints.

Step‑by‑Step Strategy
Understand coordinate frames

Point pairs $(p_i, q_i)$ are usually given as offsets $(\Delta x, \Delta y)$ relative to the keypoint or patch center.
Clarify whether your image indexing is (row, col) = (y, x).

Loop over keypoints

For each keypoint $(x_k, y_k)$ :
Option A: conceptually define a patch centered at the keypoint.
Verify all sampled points for this keypoint stay inside image bounds.

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.

Example

Constraints

Learn this in

More from CV: Feature Detection and Matching

Continue the full explanation

Editor locked