Bilinear Interpolation

mediumPROGeometric TransformationsComputer Vision 2

Given a 2D image (matrix of values) and a floating-point coordinate $(x, y)$ where $x$ is column and $y$ is row, compute the bilinearly interpolated value.

Algorithm:

Clamp coordinates to valid range: $x \in [0, W-1]$ , $y \in [0, H-1]$
Find the four nearest integer coordinates: $(x_0, y_0)$ $(x_{0}, y_{0})$ , $(x_1, y_0)$ $(x_{1}, y_{0})$ , $(x_0, y_1)$ $(x_{0}, y_{1})$ , $(x_1, y_1)$ $(x_{1}, y_{1})$
- Ensure $x_0 \leq W-2$ and $y_0 \leq H-2$ (so $x_1, y_1$ are valid)
Compute fractional parts: $dx = x - x_0$ , $dy = y - y_0$
Interpolate: $f(x,y) = f(x_0,y_0)(1-dx)(1-dy) + f(x_1,y_0) \cdot dx(1-dy) + f(x_0,y_1)(1-dx) \cdot dy + f(x_1,y_1) \cdot dx \cdot dy$

Round to 4 decimal places.

Example

Input

image = [[10, 20, 30], [40, 50, 60], [70, 80, 90]]
x = 0.5, y = 0.5

Output

30.0

Reasoning

Input: image is a $3 \times 3$ grid, so $W = H = 3$ . The point $(x, y) = (0.5, 0.5)$ is column $0.5$ , row $0.5$ : halfway between the first two columns and the first two rows. It lies inside $[0, 2]$ , so clamping changes nothing.
Surrounding pixels: columns $0, 1$ and rows $0, 1$ box it in. Because $x$ is the column, $f(1, 0)$ is row 0, column 1, i.e. $20$ . The corners are $f(0,0)=10$ , $f(1,0)=20$ , $f(0,1)=40$ , $f(1,1)=50$ , with $dx = dy = 0.5$ .
Weights: each corner gets the area of the opposite sub-rectangle, here $0.5 \times 0.5 = 0.25$ each. The four weights always sum to $1$ .
Math: $10(0.25) + 20(0.25) + 40(0.25) + 50(0.25) = 2.5 + 5 + 10 + 12.5 = 30$ .
Output: a single float, 30.0. Notice that at the centre of four pixels the result is their plain average, while on a pixel itself, e.g. $(1, 1)$ , all the weight lands there and you get $50$ .

Constraints

image is a 2D list (at least 2x2)
x is column coordinate, y is row coordinate
Clamp to valid range before interpolating
Return a single float rounded to 4 decimal places

Learn this in

Introduction to Computer VisionCV Study Plan Image ProcessingCV Study Plan

More from Computer Vision 2

1D Bilateral Filterhard Image Sharpening with Unsharp Maskmedium Gaussian Blurmedium Gaussian Kernel Generationeasy 2D Image Convolutioneasy

Concept primerPREVIEW

Background Knowledge

Bilinear interpolation is a technique used in computer vision and image processing to estimate the value of a pixel at a non-integer coordinate. It is a fundamental concept in geometric transformations, where images are resized, rotated, or distorted. The goal of bilinear interpolation is to compute a weighted average of the four nearest neighboring pixels to determine the value of the pixel at the desired coordinate.

The key concept behind bilinear interpolation is the idea of fractional parts. When a coordinate is not an integer, it can be represented as the sum of an integer part and a fractional part. For example, the coordinate $(x, y)$ can be represented as $(x_0 + dx, y_0 + dy)$ , where $x_0$ and $y_0$ are the integer parts, and $dx$ and $dy$ are the fractional parts. The fractional parts are used to compute the weights for the neighboring pixels.

In the context of image processing, bilinear interpolation is essential for tasks such as image resizing, where the pixel values need to be interpolated to create a new image with a different resolution. It is also used in other applications, such as texture mapping in computer graphics and data interpolation in scientific computing. The formula for bilinear interpolation is based on the concept of linear interpolation, where the value of a pixel is estimated as a weighted average of its neighboring pixels.

Algorithm/Approach

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

Clamp the coordinates to the valid range
Find the four nearest integer coordinates
Compute the fractional parts
Interpolate the value using the formula for bilinear interpolation

This approach can be implemented using a simple and efficient algorithm that involves basic arithmetic operations.

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