Oriented BRIEF Descriptor

hardPROFeature Detection and MatchingComputer Vision 1

Compute an oriented BRIEF (Binary Robust Independent Elementary Features) descriptor from a binary image patch.

Given a 2D binary patch (grid of 0s and 1s), a list of point pairs for comparison, and a rotation angle $\theta$ , compute a binary descriptor by:

Rotate the sampling pattern by angle $\theta$ : For each point pair $[(r_1, c_1, r_2, c_2)]$ , rotate both points around the patch center using: $r' = \cos\theta \cdot (r - r_c) - \sin\theta \cdot (c - c_c) + r_c$ $c' = \sin\theta \cdot (r - r_c) + \cos\theta \cdot (c - c_c) + c_c$ where $(r_c, c_c)$ is the patch center.
Round rotated coordinates to nearest integer.
Compare patch values: for each pair, output 1 if $\text{patch}[r_1'][c_1'] < \text{patch}[r_2'][c_2']$ , else 0.
If rotated coordinates are out of bounds, treat the value as 0.

Return the binary descriptor as a list of 0s and 1s.

Example

Input

patch = [[0, 1, 0],
        [1, 0, 1],
        [0, 1, 0]]
pairs = [[0, 1, 1, 0], [1, 2, 2, 1]]
theta = 0.0

Output

[0, 0]

Reasoning

The patch center $(r_c, c_c)$ is calculated as the middle point of the patch, which is $(1, 1)$ since the patch is a $3 \times 3$ grid.
The rotation angle $\theta = 0.0$ means no rotation is applied, so the point pairs remain the same: $[(0, 1, 1, 0), (1, 2, 2, 1)]$ .
For each pair, we compare the patch values: for the first pair, $\text{patch}[0][1] = 1$ and $\text{patch}[1][0] = 1$ , so the output is $0$ since $1 \not< 1$ ; for the second pair, $\text{patch}[1][2] = 1$ and $\text{patch}[2][1] = 1$ , so the output is $0$ since $1 \not< 1$ .
The final output is a list of these comparison results: $[0, 0]$ .

Constraints

patch: 2D list of 0s and 1s (square patch, odd size)
pairs: List of [r1, c1, r2, c2] tuples
theta: Rotation angle in radians
Return: List of 0s and 1s (binary descriptor)
Use math for cos/sin
Round rotated coordinates to nearest integer

More from Computer Vision 1

Semi-Global Matching Cost Aggregationhard Compute Depth Map from Disparitymedium Stereo Rectification Checkeasy Gaussian Scale Spacemedium Non-Maximum Suppression (NMS)easy

Concept primerPREVIEW

Background Knowledge

The Oriented BRIEF (Binary Robust Independent Elementary Features) descriptor is a feature detection and description algorithm used in computer vision. It is an extension of the BRIEF descriptor, which is a binary descriptor that compares the intensity of two points in an image patch. The key concept behind BRIEF is to generate a binary string by comparing the intensity of point pairs in the patch. This binary string serves as a descriptor for the patch.

In the context of the Oriented BRIEF descriptor, the algorithm is modified to account for rotation. This is achieved by rotating the sampling pattern (point pairs) by a given angle $\theta$ before comparing the patch values. The rotation is performed around the center of the patch, and the rotated coordinates are rounded to the nearest integer. The comparison step remains the same as in the original BRIEF algorithm.

The mathematical equations provided in the problem description represent the rotation transformation. The equations $r' = \cos\theta \cdot (r - r_c) - \sin\theta \cdot (c - c_c) + r_c$ and $c' = \sin\theta \cdot (r - r_c) + \cos\theta \cdot (c - c_c) + c_c$ describe how to rotate a point $(r, c)$ around the patch center $(r_c, c_c)$ by an angle $\theta$ . Understanding these equations is crucial to implementing the Oriented BRIEF descriptor.

Algorithm/Approach

The general approach to solving this problem involves the following steps:

Rotate the point pairs by the given angle $\theta$ using the provided rotation equations.
Round the rotated coordinates to the nearest integer.
Compare the patch values at the rotated coordinates and generate a binary descriptor.
Handle out-of-bounds cases by treating the value as 0.

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