Resize Image (Nearest Neighbor)

mediumFREEBook OverviewImage ProcessingCV: Introduction to Computer Vision

Implement an image resizing algorithm using the nearest neighbor interpolation technique. This task involves increasing or decreasing the dimensions of a given image while maintaining its visual content.

The concept of image resizing is fundamental in computer vision, as it enables images to be adapted for various applications, such as display on different devices or use in specific algorithms. Nearest neighbor interpolation is a simple, yet effective method for resizing images, which works by mapping each pixel in the output image to the nearest pixel in the input image. This process can be mathematically represented as finding the corresponding position in the input image for each output pixel position.

Here are the steps to achieve this:

Calculate the source x and y coordinates for each output pixel.
Use these coordinates to find the nearest source pixel. The calculation of source coordinates can be expressed as $src_x = \lfloor x \cdot \frac{W_{src}}{W_{dst}} \rfloor, \quad src_y = \lfloor y \cdot \frac{H_{src}}{H_{dst}} \rfloor$ .

src_x = \lfloor x \cdot \frac{W_{src}}{W_{dst}} \rfloor, \quad src_y = \lfloor y \cdot \frac{H_{src}}{H_{dst}} \rfloor

This technique is widely used in image processing applications.

Example

Input

resize_nn([[1,2],[3,4]], 4, 4)

Output

[[1,1,2,2],[1,1,2,2],[3,3,4,4],[3,3,4,4]]

Reasoning

Input: image is a $2 \times 2$ grayscale grid with rows [1,2] and [3,4], so $H_{src} = W_{src} = 2$ . The target size is new_h $= 4$ , new_w $= 4$ .
Scale factors: $\frac{H_{src}}{H_{dst}} = \frac{W_{src}}{W_{dst}} = \frac{2}{4} = 0.5$ . Each output step moves only half a pixel in the source.
Rows: for output rows $y = 0, 1, 2, 3$ we get $y \cdot 0.5 = 0, 0.5, 1, 1.5$ , and the floors are $0, 0, 1, 1$ . Columns $x = 0..3$ map to $0, 0, 1, 1$ the same way.
Example pixel: output $(y=2, x=3)$ reads source row $\lfloor 1 \rfloor = 1$ , column $\lfloor 1.5 \rfloor = 1$ , which holds the value $4$ .
Output: a $4 \times 4$ grid [[1,1,2,2],[1,1,2,2],[3,3,4,4],[3,3,4,4]]. Every source pixel becomes a $2 \times 2$ block of identical values, and no new values are invented.
Notice: when shrinking, the factor is above 1 and pixels get skipped. With the single row $1, 2, 3, 4$ resized to width 2, $x = 0, 1$ map to columns $0, 2$ , giving [[1, 3]]. Nothing is averaged.

Constraints

Output dimensions new_h, new_w are positive integers
Input is a 2D grayscale image

More from CV: Introduction to Computer Vision

Sparse Matrix Operations for Imagesmedium Multi-Scale Feature Pyramidhard Implement Prewitt Edge Detectorhard Connected Components Labelinghard K-Means Color Quantizationmedium

Concept primer

Background Knowledge

Image resizing is an example of image interpolation: you want to create a new image with different width/height, and for each pixel in the new (destination) image you must decide what value it should take based on the original (source) image. Nearest neighbor interpolation is the simplest method: instead of computing a weighted average of surrounding pixels (like bilinear or bicubic), you just copy the value of the single closest source pixel. This makes it fast but can produce blocky or jagged results compared to more advanced methods.

Conceptually, you can think of the source image as a continuous function sampled on a grid. Resizing involves resampling that function on a new grid. The formulas $src_x = \lfloor x \cdot \frac{W_{src}}{W_{dst}} \rfloor,\quad src_y = \lfloor y \cdot \frac{H_{src}}{H_{dst}} \rfloor$ tell you how to map a destination pixel coordinate $(x, y)$ back to the corresponding source coordinate by scaling with the ratio of sizes, then taking the floor to choose the nearest pixel index on the left/top.

Algorithm/Approach

The general pattern is:

Loop over all pixels in the destination image (height × width).
For each destination pixel $(x, y)$ , compute the corresponding source coordinates using the given scaling formula.
Clamp these source coordinates to valid integer indices (0 to $W_{src}-1$ , 0 to $H_{src}-1$ ) if needed.
Copy the pixel value from src[src_y][src_x] (and all channels, if color) into dst[y][x].

This is a forward-mapping from destination to source: each destination pixel pulls its value from the source (often called “backward warping” in vision).

Step-by-Step Strategy
Get dimensions

Let H_src, W_src be the source height and width.
Let H_dst, W_dst be the desired destination height and width.

Precompute scale factors (optional but useful)

scale_x = W_src / W_dst
scale_y = H_src / H_dst

Create an empty destination image

Shape: [H_dst][W_dst] for grayscale or [H_dst][W_dst][C] for color.

Loop over destination pixels

for y in range(H_dst):
for x in range(W_dst):
src_x = int(x * scale_x) # floor implicitly
src_y = int(y * scale_y)

Clamp indices (if needed)

Ensure 0 <= src_x < W_src and 0 <= src_y < H_src.
Often the floor formula guarantees this, but clamping is a safe guard.

Copy pixel value

dst[y][x] = src[src_y][src_x] # copy all channels if color

Return the resized image

Common Pitfalls

Off-by-one errors:
If you accidentally use $\frac{W_{dst}}{W_{src}}$ instead of $\frac{W_{src}}{W_{dst}}$ , or mix up src/dst width/height, you’ll sample from wrong positions.
Using wrong rounding:
The formula specifies floor. Using round() can shift sampling and create artifacts or index errors at the borders.
Out-of-bounds indices:
For the last pixel (e.g., x = W_dst - 1), make sure src_x never becomes W_src (must be at most W_src - 1).
Channel handling:
For RGB images, ensure you copy all channels from the same source coordinate; don’t treat channels as separate images with mismatched indexing.
Integer division in some languages:
In languages where / between integers truncates, precompute scale as float to avoid division mistakes.

Time & Space Complexity

Time complexity:
You visit each destination pixel exactly once and do O(1) work per pixel.
$O(W_{dst} \cdot H_{dst})$ .
Space complexity:
You need space for the output image plus the input image.
Extra working memory is $O(W_{dst} \cdot H_{dst})$ for the destination (input is given).

solution.py

Python 3.13

Test results