Normalized Patch Descriptor

easyPROFeature DescriptorsFeaturesCV: Feature Detection and Matching

Implement a feature descriptor known as a Normalized Patch Descriptor, which is crucial for feature matching in computer vision. You are given an image and a keypoint location, and need to extract a normalized patch descriptor for feature matching.

The concept of a patch descriptor is rooted in capturing the local appearance around a keypoint, which is essential for tasks like object recognition and tracking. This involves extracting a square patch centered at the keypoint, flattening it into a 1D vector, and then normalizing it to unit length using L2 normalization, making the descriptor invariant to linear intensity changes such as brightness and contrast.

Here are the steps to achieve this:

Extract a square patch centered at the keypoint
Flatten the 2D patch into a 1D vector
Normalize to unit length

\text{normalized} = \frac{v}{\|v\|_2} = \frac{v}{\sqrt{\sum_i v_i^2}}

This technique is widely used in image matching and object recognition applications.

Example

Input

image = [[1, 2, 3],
        [4, 5, 6],
        [7, 8, 9]]
point = (1, 1)
patch_size = 3

Output

[0.0596, 0.1191, 0.1787, 0.2382, 0.2978, 0.3573, 0.4169, 0.4764, 0.536]

Reasoning

Extract 3×3 patch centered at (1,1): [[1,2,3], [4,5,6], [7,8,9]]
Flatten to 1D: [1, 2, 3, 4, 5, 6, 7, 8, 9]
Calculate L2 norm: ||v|| = √(1² + 2² + 3² + 4² + 5² + 6² + 7² + 8² + 9²) = √(1 + 4 + 9 + 16 + 25 + 36 + 49 + 64 + 81) = √285 ≈ 16.882
Normalize each element: [1/16.882, 2/16.882, ..., 9/16.882] = [0.0592, 0.1185, 0.1777, 0.2369, 0.2962, 0.3554, 0.4146, 0.4739, 0.5331]

Rounded to 4 decimals.

Constraints

image is a 2D grayscale image
point is (row, col) center of the patch
patch_size is an odd number (the patch is patch_size × patch_size)
Assume the point has enough padding for the full patch
Return flattened, normalized descriptor with values rounded to 4 decimals

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

You are constructing a very simple local feature descriptor: a numeric vector that summarizes the appearance of a small neighborhood around a keypoint so that it can be compared (e.g., with dot product or Euclidean distance) across images. Unlike more complex descriptors (SIFT, ORB, etc.), this one just uses raw pixel intensities from a patch, then normalizes the resulting vector so changes in overall brightness/contrast affect it less. The core math idea is L2 normalization: dividing a vector by its Euclidean norm so it has length 1.

In image matching, local descriptors should be comparable and robust. Taking a fixed-size patch around the keypoint ensures each descriptor describes the same spatial support; flattening into a 1D vector gives a standard representation for distance computations; and L2 normalization makes the descriptor invariant to linear intensity scaling: if all pixel values are multiplied by a constant (brightness/contrast change), the direction of the vector stays the same, and after normalization the descriptor is unchanged.

2. Algorithm / Approach Pattern

The general pattern for this kind of descriptor:

Extract local data around a keypoint (here: a fixed-size square patch).
Convert to a feature vector (flattening, or some transformation like gradients, histograms, etc.).
Normalize the vector (L2 norm here) to improve robustness and make distances meaningful.

This pattern appears in many feature descriptors; in your problem it is instantiated in the simplest possible way: raw intensities + L2 normalization.

3. Step-by-Step Strategy

Assume:

Input image img (grayscale or specific channel).
Keypoint coordinates (x, y) (often x is column, y is row).
Patch size patch_size (odd, e.g., 9, 11, 16, so there is a clear center).

Steps:

Compute patch half-size

half = patch_size // 2

Determine patch bounds Rows (or y):

y_min = y - half
y_max = y + half

Columns (or x):

x_min = x - half
x_max = x + half

Handle border conditions Decide what to do if the patch would go outside the image:

Simplest: only process keypoints where the full patch lies inside.
Or: clamp/crop/pad (depending on problem instructions).

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