📘

Bilinear Interpolation

MediumGeometric Transformations 📚 Computer 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:

The coordinates $(x, y) = (0.5, 0.5)$ are clamped to the valid range, yielding $(x, y) = (0.5, 0.5)$ since they are already within the bounds.
The four nearest integer coordinates are found: $(x_0, y_0) = (0, 0)$ , $(x_1, y_0) = (1, 0)$ , $(x_0, y_1) = (0, 1)$ , $(x_1, y_1) = (1, 1)$ , with fractional parts $dx = 0.5$ and $dy = 0.5$ .
The bilinear interpolation formula is applied: $f(x,y) = f(0,0)(1-0.5)(1-0.5) + f(1,0) \cdot 0.5(1-0.5) + f(0,1)(1-0.5) \cdot 0.5 + f(1,1) \cdot 0.5 \cdot 0.5 = 10 \cdot 0.25 + 20 \cdot 0.25 + 40 \cdot 0.25 + 50 \cdot 0.25 = 2.5 + 5 + 10 + 12.5 = 30.0$ .
The result is rounded to 4 decimal places, yielding $30.0$ .

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

More from Computer Vision 2

1D Bilateral FilterHard Image Sharpening with Unsharp MaskMedium Gaussian BlurMedium Gaussian Kernel GenerationEasy 2D Image ConvolutionEasy

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.

👑

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.

solution.py

Python 3.13

Test Results

0/0

Run code to see test results.