Билинейная интерполяция

Билинейная интерполяция

Билинейная интерполяция — в вычислительной математике расширение линейной интерполяции для функций двух переменных. Ключевая идея заключается в том, чтобы провести обычную линейную интерполяцию сначала в одном направлении, затем в другом.

Четыре красные точки представляют собой известные значения функции. Значение в зеленой точке должно быть интерполировано.
Пример билинейной интерполяции в единичном квадрате. Значения вершин составляют 0, 1, 1 и 0.5. Интерполированные значения в каждой точке представлены цветом.

Допустим, что необходимо интерполировать значение функции f в точке P = (x, y). Для этого необходимо знать значения функций в (окружающих P) точках Q11 = (x1y1), Q12 = (x1y2), Q21 = (x2y1), и Q22 = (x2y2).

Первым шагом интерполируется (линейно) значение вспомогательных точек R_1 и R_2 вдоль оси абсцисс, где

R_1 = (x,y_1)
R_2 = (x,y_2)
 f(R_1) \approx \frac{x_2-x}{x_2-x_1} f(Q_{11}) + \frac{x-x_1}{x_2-x_1} f(Q_{21})

 

 f(R_2) \approx \frac{x_2-x}{x_2-x_1} f(Q_{12}) + \frac{x-x_1}{x_2-x_1} f(Q_{22})

Теперь проводится линейная интерполяция между вспомогательными точками R_1 и R_2.

 f(P) \approx \frac{y_2-y}{y_2-y_1} f(R_1) + \frac{y-y_1}{y_2-y_1} f(R_2).

Это и есть приблизительное значение функции в точке P, то есть f(x, y).

 
\begin{align}
f(x,y) &\approx \frac{f(Q_{11})}{(x_2-x_1)(y_2-y_1)} (x_2-x)(y_2-y) \\
& + \frac{f(Q_{21})}{(x_2-x_1)(y_2-y_1)} (x-x_1)(y_2-y) \\
& + \frac{f(Q_{12})}{(x_2-x_1)(y_2-y_1)} (x_2-x)(y-y_1) \\
& + \frac{f(Q_{22})}{(x_2-x_1)(y_2-y_1)} (x-x_1)(y-y_1). 
\end{align}

В особом случае, когда известные точки находятся на вершинах единичного квадрата, то есть имеют координаты (0, 0), (0, 1), (1, 0), и (1, 1), формула билинейной интерполяции упрощается до

 f(x,y) \approx f(0,0) \, (1-x)(1-y) + f(1,0) \, x(1-y) + f(0,1) \, (1-x)y + f(1,1) xy.

Или же с помощью умножения векторов с матрицей:

 f(x,y) \approx \begin{bmatrix}
1-x & x \end{bmatrix} \begin{bmatrix}
f(0,0) & f(0,1) \\
f(1,0) & f(1,1) \end{bmatrix} \begin{bmatrix}
1-y \\
y \end{bmatrix}

Обратите внимание: сам интерполянт нелинеен:

 (a_1 x + a_2)(a_3 y + a_4), \,

так как является произведением двух линейных функций. Альтернативное написание:

 b_1 + b_2 x + b_3 y + b_4 x y \,

где

 b_1 = f(0,0) \,
 b_2 = f(1,0)-f(0,0) \,
 b_3 = f(0,1)-f(0,0) \,
 b_4 = f(0,0)-f(1,0)-f(0,1)+f(1,1) \,.

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

Очевидное расширение билинейной интерполяции на функции трех переменных — трилинейная интерполяция.

Содержание

Билинейная интерполяция в компьютерной графике

Пример увеличения части изображения — простым масштабированием и с применением билинейной интерполяции

В компьютерной графике билинейная интерполяция получила широкое распространение в процессе ресемплинга (или, проще говоря, масштабирования) изображений.

При увеличении цифровых изображений наблюдается сильная пикселизация картинки. Билинейная интерполяция используется для расчета цветов дополнительных пикселей (P) относительно основных, исходных (Q), что позволяет сглаживать переходы. Значением функции f в данном случае выступает цвет пикселя (его составляющие). При этом квадрат, образованный четырьмя рассматриваемыми основными точками принимается единичным.

Недостаток метода

Главным минусом билинейной интерполяции при масштабировании изображений является тот факт, что при увеличении в N раз изображения размером W на H пикселей в результате будет получено изображение размером не NW на NH пикселей, а (N(W-1)+1) на (N(H-1)+1) пикселей.

Связано это с тем, что в исходном изображении, например, по горизонтали имеется W точек, то есть (W-1) смежных пар. При увеличении изображения в N раз между каждой парой основных точек вставляется по (N-1) дополнительных точек (то есть при увеличении вдвое между основными точками вставляется еще по одной, при увеличении втрое — по две и т. д.). Итого в результате ширина результирующего изображения будет равна сумме количества основных и дополнительных точек:

W + (W-1)(N-1) = N(W-1)+1.

Проще говоря, для последнего пикселя (в каждой строке и столбце) исходного изображения не находится пары, с которой можно было бы провести интерполирование.

Для обхода данного ограничения, во-первых, обычно принимается, что в исходном и полученном изображениях цветовые значения пикселей сэмплированы из их центров, нежели из углов, т.е. например, если принять абсолютную длину и ширину изображения равными 1, в изображении размером 2 на 2 координатами исходных точек являются (0.25;0.25), (0.25;0.75), (0.75;0.25), и (0.75;0.75), нежели (0;0), (0;0.5), (0.5;0), и (0.5;0.5) (поправка на дискретизацию). Таким образом обеспечивается правильная центровка изображения при масштабировании, но проблемными оказываются не только последняя строка и последний столбец, а все пограничные пиксели получаемого изображения в равной степени, ибо их координаты выпадают за пределы прямоугольника, очерчивающего точки сэмплирования исходного изображения (например, при масштабировании в 4 на 4 нужно вычислить значения в точках (0.125;0.125), (0.125;0.875) и т.д.). Затем, т.к. значения в этих точках не могут быть интерполированы, то нужно расширить исходное изображение одним из способов (выбор которого зависит от способа дальнейшего использования изображения):

  • Экстраполяция значений краевых пикселей;
  • Зеркальное отражение исходного изображения относительно каждого края, и центральное по углам. В качестве значений отсутствующих пикселей используются копии значений пикселей с того же края; таким образом, пиксели, выпадающие за исходные координаты, являются интерполянтами лишь в одном измерении, а в другом копиями краевых значений;
  • Тесселяция исходного изображения; копии исходного изображения "приклеиваются" встык с каждого края и из углов. В качестве цветовых значений отсутствующих пикселей, таким образом, используются значения пикселей с противоположного края. Метод подходит, если интерполированное изображение само будет использоваться для тесселяции (например, для заполнения многоугольников при текстурировании).

После подобной предварительной обработки процедура билинейной интерполяции применяется в исходном виде, с получением изображения ожидаемого размера (NW на NH).

Пример программы

Ниже приведен пример программы билинейной интерполяции изображения, написанный на C

Входные параметры:

  a       - указатель на массив пикселей изображения, которое необходимо увеличить (уменьшить)
            Нумерация элементов [0..old_h-1, 0..old_w-1]
  oldw   - старая ширина изображения
  oldh   - старая высота изображения

Выходные параметры:

   b      - указатель на массив пикселей ресемплированного изображения
            Нумерация элементов [0..new_h-1, 0..new_w-1]
   neww  - новая ширина изображения
   newh  - новая высота изображения


#include <stdio.h>
#include <math.h>
#include <sys/types.h>
 
void resample(void *a, void *b, int oldw, int oldh, int neww,  int newh)
{
    int i;
    int j;
    int l;
    int c;
    float t;
    float u;
    float tmp;
    float d1, d2, d3, d4;
    u_int p1, p2, p3, p4; /* Окрестные пикселы */
    u_char red, green, blue;
 
    for (i = 0; i < newh; i++) {
        for (j = 0; j < neww; j++) {
 
            tmp = (float) (i) / (float) (newh - 1) * (oldh - 1);
            l = (int) floor(tmp);
            if (l < 0) {
                l = 0;
            } else {
                if (l >= oldh - 1) {
                    l = oldh - 2;
                }
            }
            u = tmp - l;
 
            tmp = (float) (j) / (float) (neww - 1) * (oldw - 1);
            c = (int) floor(tmp);
            if (c < 0) {
                c = 0;
            } else {
                if (c >= oldw - 1) {
                    c = oldw - 2;
                }
            }
            t = tmp - c;
 
            /* Коэффициенты */
            d1 = (1 - t) * (1 - u);
            d2 = t * (1 - u);
            d3 = t * u;
            d4 = (1 - t) * u;
 
            /* Окрестные пиксели: a[i][j] */
            p1 = *((u_int*)a + (l * oldw) + c);
            p2 = *((u_int*)a + (l * oldw) + c + 1);
            p3 = *((u_int*)a + ((l + 1)* oldw) + c + 1);
            p4 = *((u_int*)a + ((l + 1)* oldw) + c);
 
            /* Компоненты */
            blue = (u_char)p1 * d1 + (u_char)p2 * d2 + (u_char)p3 * d3 + (u_char)p4 * d4;
            green = (u_char)(p1 >> 8) * d1 + (u_char)(p2 >> 8) * d2 + (u_char)(p3 >> 8) * d3 + (u_char)(p4 >> 8) * d4;
            red = (u_char)(p1 >> 16) * d1 + (u_char)(p2 >> 16) * d2 + (u_char)(p3 >> 16) * d3 + (u_char)(p4 >> 16) * d4;
 
            /* Новый пиксел из R G B  */
            *((u_int*)b + (i * neww) + j) = (red << 16) | (green << 8) | (blue);            
        }
    }
}

См. также


Wikimedia Foundation. 2010.

Смотреть что такое "Билинейная интерполяция" в других словарях:

  • Билинейная фильтрация — Билинейная фильтрация  процесс извлечения нескольких пикселей исходной текстуры с последующим усреднением их значений для получения окончательного значения пикселя. Понятие «билинейная фильтрация», точно так же, как и сходное понятие… …   Википедия

  • Интерполяция — О функции, см.: Интерполянт. Интерполяция, интерполирование  в вычислительной математике способ нахождения промежуточных значений величины по имеющемуся дискретному набору известных значений. Многим из тех, кто сталкивается с научными и… …   Википедия

  • Интерполяция (матем.) — О функции, см.: Интерполянт. Интерполяция  в вычислительной математике способ нахождения промежуточных значений величины по имеющемуся дискретному набору известных значений. Многим из тех, кто сталкивается с научными и инженерными расчётами часто …   Википедия

  • Бикубическая интерполяция — Результат бикубической интерполяции функции заданной на сетке . Данную сетку можно рассматривать как состоящую из 9 е …   Википедия

  • Линейная интерполяция — Линейная интерполяция  интерполяция алгебраическим двучленом P1(x) = ax + b функции f, заданной в двух точках x0 и x1 отрезка [a, b]. В случае, если заданы значения в нескольких точках, функция заменяется кусочно линейной функцией.… …   Википедия

  • Интерполирование — О функции, см.: Интерполянт. Интерполяция  в вычислительной математике способ нахождения промежуточных значений величины по имеющемуся дискретному набору известных значений. Многим из тех, кто сталкивается с научными и инженерными расчётами часто …   Википедия

  • Масштабирование — Масштабирование  изменение размера изображения с сохранением пропорций. Под масштабированием подразумевается как увеличение, так и уменьшение размеров изображения. В настоящее время масштабирование выполняется с помощью компьютерной техники …   Википедия

  • Массив цветных фильтров — Основная статья: Матрица (фото) Массив цветных фильтров, Мозаика цветных фильтров  часть светочувствительной матрицы, осуществляющая пространственное цветоделение изображения при помощи фотодатчиков  пикселей матрицы, расположенных за… …   Википедия

  • Мозаика цветных фильтров — Основная статья: Матрица (фото) Массив цветных фильтров, Мозаика цветных фильтров  часть светочувствительной матрицы, осуществляющий пространственное разделение цветных компонентов изображения по фотодатчикам  пикселам матрицы, расположенный в… …   Википедия

  • Реконструкционный фильтр — (восстанавливающий фильтр, англ. reconstruction filter, anti imaging filter) используется в смешанных аналогово цифровых системах для вывода гладкого (smooth) аналогового сигнала c цифрового входа. В частности, он применяется в устройствах… …   Википедия


Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»