Normalized Patch Descriptor
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
This technique is widely used in image matching and object recognition applications.
Example:
image = [[1, 2, 3],
[4, 5, 6],
[7, 8, 9]]
point = (1, 1)
patch_size = 3[0.0596, 0.1191, 0.1787, 0.2382, 0.2978, 0.3573, 0.4169, 0.4764, 0.536]
-
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
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).
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.