WikiSort.ru - Не сортированное

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

Обобщение основано на применении обычной линейной интерполяции сначала в направлении одной из координат, а затем в перпендикулярном направлении.

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

Принцип построения билинейной интерполяции

Допустим, что необходимо интерполировать значение функции ${\displaystyle f(x,y)}$ в точке ${\displaystyle P=(x,y)}$ . Значения функции в окружающих точку ${\displaystyle P}$ точках ${\displaystyle Q_{11}=(x_{1},y_{1}),}$ ${\displaystyle Q_{12}=(x_{1},y_{2}),}$ ${\displaystyle Q_{21}=(x_{2},y_{1})}$ и ${\displaystyle Q_{22}=(x_{2},y_{2})}$ известны (рис. 1).

Первым шагом линейно интерполируется значение вспомогательных точек ${\displaystyle R_{1}}$ и ${\displaystyle R_{2}}$ вдоль оси абсцисс, где

${\displaystyle R_{1}=(x,y_{1})}$

${\displaystyle R_{2}=(x,y_{2})}$

${\displaystyle 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})}$

${\displaystyle 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})}$

Теперь проводится линейная интерполяция между вспомогательными точками ${\displaystyle R_{1}}$ и ${\displaystyle R_{2}}$ .

${\displaystyle 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}).}$

Это и есть интерполируемое (экстраполируемое) значение функции ${\displaystyle f(x,y)}$ , причём значения интерполирующей функции ${\displaystyle F(x,y)}$ равны значениям интерполируемой функции в исходных точках ${\displaystyle (x_{1},y_{1});(x_{1},y_{2});(x_{2},y_{1});(x_{2},y_{2})}$ :

${\displaystyle {\begin{aligned}f(x,y)&\approx F(x,y)={\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{aligned}}}$

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

${\displaystyle f(x,y)\approx F(x,y)=f(0,0)\,(1-x)(1-y)+f(1,0)\,x(1-y)+f(0,1)\,(1-x)y+f(1,1)xy.}$

Или же в обозначениях умножения векторов на матрицу:

${\displaystyle 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}}}$

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

${\displaystyle F(x,y)=b_{1}+b_{2}x+b_{3}y+b_{4}xy,}$

где

${\displaystyle b_{1}=f(0,0)}$

${\displaystyle b_{2}=f(1,0)-f(0,0)}$

${\displaystyle b_{3}=f(0,1)-f(0,0)}$

${\displaystyle b_{4}=f(0,0)-f(1,0)-f(0,1)+f(1,1)}$ .

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

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

Использование билинейной интерполяции

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

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

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

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

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

Главный недостаток метода билинейной интерполяции при масштабировании изображений — при увеличении в ${\displaystyle N}$ раз исходного изображения размером ${\displaystyle W}$ на ${\displaystyle H}$ пикселей в результате будет получено изображение размером не ${\displaystyle N\cdot W}$ на ${\displaystyle N\cdot H}$ пикселей, а ${\displaystyle (N(W-1)+1)}$ на ${\displaystyle (N(H-1)+1)}$ пикселей.

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

${\displaystyle 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) и т. д.). Затем, так как значения в этих точках не могут быть интерполированы, то нужно расширить исходное изображение одним из способов (выбор которого зависит от способа дальнейшего использования изображения):

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

После подобной предварительной обработки процедура билинейной интерполяции применяется в исходном виде, с получением изображения ожидаемого размера (${\displaystyle N\cdot W}$ на ${\displaystyle N\cdot H}$ ).

См. также

Имеется викиучебник по теме
«Билинейная интерполяция»

• Интерполяция

Примечания

В этой статье не хватает ссылок на источники информации. Информация должна быть проверяема, иначе она может быть поставлена под сомнение и удалена. Вы можете отредактировать эту статью, добавив ссылки на авторитетные источники. Эта отметка установлена 19 января 2015 года.