14. Oktober 2010

Nearest-Neighbor-Resampling in Matlab

This article shows the derivation of an algorithm for resizing images in Matlab, using nearest-neighbor interpolation. Scaling an image is mathematically just multiplying image coordinates by a scaling factor. Surprisingly, when dealing with digital images, the scaling process becomes a little bit more complex.

function g = resample(f, sx, sy)
%% Scales an image using nearest neighbor interpolation.
% f     - the input image
% sx    - the scaling factor in x-direction
% sy    - the scaling factor in y-direction
    g = zeros(size(f, 1) * sx, size(f, 2) * sy, class(f));
    for i = 1:size(g, 1)
        for j = 1:size(g, 2)
            fi = 1 + round((i - 0.5) / sx - 0.5);
            fj = 1 + round((j - 0.5) / sy - 0.5);
            g(i, j) = f(fi, fj);
        end
    end
end

How to find this arithmetic expression? Step by step.

Convert a 1-based index i to a 0-based index i’

9e9a9ef0c4c15a4468f21254f821c25237f38fe6

765cc8375c6b51be5e86b39f98c8aea830076e2b

Convert a 0-based index i’ to a Cartesian coordinate

The first pixel has coordinate 0.5, the next pixel 1.5 and so on. This provides
consistent spacing between pixels and follows the standard image representation
on screens and other media.

cbafdf002e32062cf39daf4b6f97d43bb253af07

f0f837db569ab54af132292a044b8b650c5cef01

Scale

cb14f1560483a284e9879bb711484fd396019188

72f1a33146beadcaef86dbb2f50c89dcb2aaad33

Chaining the transformations together

Now, given an 1-based index i_f from the input image, how to calculate the corresponding 1-based index i_g in the output image? By chaining the transformations together.

ac8d2fc0fe649701faa8eb6a8a989454b554df85

By inverting the composite function, we obtain the sought-after function

5a7f0de2d3885b4d242b7b05966eee137488bde5

We can now plug in the function definitions

07404af383a9ebd797753bf6ca8ea9c3326dc1be

Compare this expression with the algorithm.