|
[[Файл:Bilinear interpolation.png|right|thumb|Четыре красные точки представляют собой известные значения функции. Значение в зеленой точке должно быть интерполировано.]]
[[Файл:Bilininterp.png|right|thumb|Пример билинейной интерполяции в единичном квадрате. Значения вершин составляют 0, 1, 1 и 0.5. Интерполированные значения в каждой точке представлены цветом.]]
== Алгоритм ==
Допустим, что необходимо интерполировать значение функции <math>f</math> в точке <math>P = (x, y)</math>. Для этого необходимо знать значения функций в окружающих <math>P</math> точках <math>Q_{11} = (x_1, y_1),</math> <math>Q_{12} = (x_1, y_2),</math> <math> Q_{21} = (x_2, y_1)</math> и <math>Q_{22} = (x_2, y_2)</math>.
: <math> 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})</math>
: <math> 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})</math>
</math>
В частном случае, когда известные точки являются вершинами [[Единичный квадрат|единичного квадрата]] с [[координаты|координатами]] (0, 0), (0, 1), (1, 0), и (1, 1), формула билинейной интерполяции упрощается до
: <math> 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. </math>
Проще говоря, для последнего пикселя (в каждой строке и столбце) исходного изображения не находится пары, с которой можно было бы провести интерполирование.
Для обхода данного ограничения, во-первых, обычно принимается, что в исходном и полученном изображениях цветовые значения пикселей семплированы из их ''центров'', нежели из углов, т.е.то есть например, если принять абсолютную длину и ширину изображения равными 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) и т. д.). Затем, т.к.так как значения в этих точках не могут быть интерполированы, то нужно расширить исходное изображение одним из способов (выбор которого зависит от способа дальнейшего использования изображения):
* [[Экстраполяция]] значений краевых пикселей;
* Зеркальное отражение исходного изображения относительно каждого края, и центральное по углам. В качестве значений отсутствующих пикселей используются копии значений пикселей с того же края; таким образом, пиксели, выпадающие за исходные координаты, являются интерполянтами лишь в одном измерении, а в другом копиями краевых значений;
* [[Тесселяция]] исходного изображения; копии исходного изображения "«приклеиваются"» встык с каждого края и из углов. В качестве цветовых значений отсутствующих пикселей, таким образом, используются значения пикселей с противоположного края. Метод подходит, если интерполированное изображение само будет использоваться для тесселяции (например, для заполнения многоугольников при [[Текстура (трёхмерная графика)|текстурировании]]).
После подобной предварительной обработки процедура билинейной интерполяции применяется в исходном виде, с получением изображения ожидаемого размера (<math>NW</math> на <math>NH</math>).
== Пример программы ==
Ниже приведен пример программы билинейной интерполяции изображения, написанный на [[C99]] (на C89 компилироваться не будет!)
Входные параметры:
a - указатель на массив пикселей изображения, которое необходимо увеличить (уменьшить)
Нумерация элементов [0..old_h-1, 0..old_w-1]
oldw - старая ширина изображения
oldh - старая высота изображения
Выходные параметры:
b - указатель на массив пикселей ресемплированного изображения
Нумерация элементов [0..new_h-1, 0..new_w-1]
neww - новая ширина изображения
newh - новая высота изображения
<source lang='c'>
#include <stdio.h>
#include <math.h>
#include <sys/types.h>
void resample(int oldw, int oldh, int neww, int newh, u_int a[oldh][oldw], u_int b[newh][neww])
{
int i, j;
int h, w;
float t;
float u;
float tmp;
float d1, d2, d3, d4;
u_int p1, p2, p3, p4; /* Окрестные пикселы */
u_char red, green, blue;
for (j = 0; j < newh; j++) {
tmp = (float) (j) / (float) (newh - 1) * (oldh - 1);
h = (int) floor(tmp);
if (h < 0) {
h = 0;
} else {
if (h >= oldh - 1) {
h = oldh - 2;
}
}
u = tmp - h;
for (i = 0; i < neww; i++) {
tmp = (float) (i) / (float) (neww - 1) * (oldw - 1);
w = (int) floor(tmp);
if (w < 0) {
w = 0;
} else {
if (w >= oldw - 1) {
w = oldw - 2;
}
}
t = tmp - w;
/* Коэффициенты */
d1 = (1 - t) * (1 - u);
d2 = t * (1 - u);
d3 = t * u;
d4 = (1 - t) * u;
/* Окрестные пиксели: a[i][j] */
p1 = a[h][w];
p2 = a[h][w + 1];
p3 = a[h + 1][w + 1];
p4 = a[h + 1][w];
/* Компоненты */
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 */
b[j][i] = ((u_int32_t) red << 16) | ((u_int32_t) green << 8) | (blue);
}
}
}
</source>
== См. также ==
{{wikibooks|Реализации алгоритмов/Билинейная интерполяция|Билинейная интерполяция}}
* [[Интерполяция]]
{{нет источников}}
[[Категория:Вычислительная математика]]
[[Категория:Интерполяция]]
| 