Resize Image (Nearest Neighbor)

1. 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.

2. 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).

3. Step-by-Step Strategy

4. 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.

2. Precompute scale factors (optional but useful)

• scale_x = W_src / W_dst
• scale_y = H_src / H_dst

3. Create an empty destination image

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

4. 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)

5. 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.

6. Copy pixel value

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

7. Return the resized image

4. 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.

5. 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).