Билинейное ресэмплирование сеточной функции (билинейная интерполяция)

Иногда требуется решить следующую задачу - есть у нас сетка размером M₁ *N₁ . В узлах этой сетки нам известны значения некоторой функции f(x, y). И по какой-то причине требуется перейти от сетки размером M₁ *N₁  к сетке размером M₂ *N₂ . В качестве примера можно привести изменение размера растровой картинки (здесь функцией, определенной на сетке, являются цвета пикселей). Впрочем, бывают и другие применения.

Это задача интерполяции - по известным значениям в одних точках получить значения функции в других точках. Но данный случай является особым - нам требуется вычислять значение функции не в произвольных точках, а в узлах сетки, и вычисления проводятся только один раз, после чего мы получаем новую сетку и больше не возвращаемся к ресурсоемкой интерполяции. Поэтому для решения данной задачи имеет смысл разработать специализированную процедуру.

Во многих случаях оказывается достаточно той точности, которую обеспечивает билинейная интерполяция. Скажем, для изменения размера изображений этого часто хватает. Тем не менее, следует отметить, что данный способ не обеспечивает непрерывности даже первых производных интерполируемой функции. В задачах, требующих непрерывности производных, лучше использовать другие методы.

Сам алгоритм крайне прост - мы обходим точки новой сетки. Для каждой точки смотрим, в какой квадрат старой сетки она попадает. Пусть точка попала в квадрат, образованный узлами (x_L , y_C ), (x_L+1 , y_C ), (x_L , y_C+1 ), (x_L+1 , y_C+1 ). Применяем к координатам точки (x, y) преобразование t = (x-x_L )/(x_L+1 -x_L ), u = (y-y_C )/(y_C+1 -y_C ). Полученные координаты лежат в диапазоне [0, 1]. Значение функции в новом узле расчитывается, как f_new  = (1-t)(1-u)*f_L,C +t(1-u)*f_L,C+1 +tu*f_L+1,C+1 +(1-t)u*f_L+1,C .

Если нашли ошибку в алгоритме - сообщите!

Реализации алгоритма на различных языках:

Реализация алгоритма на AlgoPascal:

unit ResampleUnit;

interface BilinearResample;

implementation

(************************************************************
Билинейное ресэмплирование.

    Процедура   получает   значения   функции    на     сетке
OldWidth*OldHeight и путем билинейной интерполяции  вычисляет
значения функции в узлах  сетки  размером NewWidth*NewHeight.
Новая  сетка  может  быть как более, так и менее плотная, чем
старая.

procedure BilinearResample(
    OldWidth    - старый размер сетки
    OldHeight   - старый размер сетки
    NewWidth    - новый размер сетки
    NewHeight   - новый размер сетки
    const A     : array [0..OldHeight, 0..OldWidth] of Real
                - старые значения функции
    out B       : array [0..NewHeight, 0..NewWidth] of Real
                - новые значения функции
************************************************************)
procedure BilinearResample(
    OldWidth    :   Integer;
    OldHeight   :   Integer;
    NewWidth    :   Integer;
    NewHeight   :   Integer;
    const A     :   array of array of Real;
    out B       :   array of array of Real);
var
    I   :   Integer;
    J   :   Integer;
    L   :   Integer;
    C   :   Integer;
    T   :   Real;
    U   :   Real;
    Tmp :   Real;
begin
    SetBounds(B, [0,NewHeight], [0,NewWidth]);
    for I:=0 to NewHeight do
        for J:=0 to NewWidth do
        begin
            Tmp:=I/NewHeight*OldHeight;
            L:=Floor(Tmp);
            if L<0 then
                L:=0
            else if L>=OldHeight then
                L:=OldHeight-1;
            U:=Tmp-L;

            Tmp:=J/NewWidth*OldWidth;
            C:=Floor(Tmp);
            if C<0 then
                C:=0
            else if C>=OldWidth then
                C:=OldWidth-1;
            T:=Tmp-C;
            
            B[I,J]:=(1-T)*(1-U)*A[L,C]+T*(1-U)*A[L,C+1]+T*U*A[L+1,C+1]+
                (1-T)*U*A[L+1,C];
        end;
end;

end.

Бочканов Сергей, Быстрицкий Владимир
Copyright © 1999-2004
При поддержке проекта MANUAL.RU