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

Четыре красных точки показывают точки данных, а зеленая точка - это точка, в которой мы хотим выполнить интерполяцию.

Пример билинейной интерполяции на единичном квадрате с указанными значениями z 0, 1, 1 и 0,5. Интерполированные значения между ними представлены цветом.

В математике , билинейная интерполяция является расширением линейной интерполяции для интерполирования функции двух переменных (например, х и у ) на прямолинейном 2D сетки .

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

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

Алгоритм [ править ]

Предположим, что мы хотим найти значение неизвестной функции f в точке ( x , y ). Предполагается, что мы знаем значение f в четырех точках: Q ₁₁ = ( x ₁ ,  y ₁ ), Q ₁₂ = ( x ₁ ,  y ₂ ), Q ₂₁ = ( x ₂ ,  y ₁ ) и Q _22. = ( х ₂ ,  у ₂ ).

Сначала мы выполняем линейную интерполяцию по оси x . Это дает

${\ displaystyle {\ begin {align} f (x, y_ {1}) & \ приблизительно {\ frac {x_ {2} -x} {x_ {2} -x_ {1}}} f (Q_ {11} ) + {\ frac {x-x_ {1}} {x_ {2} -x_ {1}}} f (Q_ {21}), \\ f (x, y_ {2}) & \ приблизительно {\ frac {x_ {2} -x} {x_ {2} -x_ {1}}} f (Q_ {12}) + {\ frac {x-x_ {1}} {x_ {2} -x_ {1}} } f (Q_ {22}). \ end {align}}}$

Продолжим интерполяцию по оси y, чтобы получить желаемую оценку:

${\displaystyle {\begin{aligned}f(x,y)&\approx {\frac {y_{2}-y}{y_{2}-y_{1}}}f(x,y_{1})+{\frac {y-y_{1}}{y_{2}-y_{1}}}f(x,y_{2})\\&={\frac {y_{2}-y}{y_{2}-y_{1}}}\left({\frac {x_{2}-x}{x_{2}-x_{1}}}f(Q_{11})+{\frac {x-x_{1}}{x_{2}-x_{1}}}f(Q_{21})\right)+{\frac {y-y_{1}}{y_{2}-y_{1}}}\left({\frac {x_{2}-x}{x_{2}-x_{1}}}f(Q_{12})+{\frac {x-x_{1}}{x_{2}-x_{1}}}f(Q_{22})\right)\\&={\frac {1}{(x_{2}-x_{1})(y_{2}-y_{1})}}\left(f(Q_{11})(x_{2}-x)(y_{2}-y)+f(Q_{21})(x-x_{1})(y_{2}-y)+f(Q_{12})(x_{2}-x)(y-y_{1})+f(Q_{22})(x-x_{1})(y-y_{1})\right)\\&={\frac {1}{(x_{2}-x_{1})(y_{2}-y_{1})}}{\begin{bmatrix}x_{2}-x&x-x_{1}\end{bmatrix}}{\begin{bmatrix}f(Q_{11})&f(Q_{12})\\f(Q_{21})&f(Q_{22})\end{bmatrix}}{\begin{bmatrix}y_{2}-y\\y-y_{1}\end{bmatrix}}.\end{aligned}}}$

Обратите внимание, что мы получим тот же результат, если интерполяция выполняется сначала по направлению y, а затем по направлению x . ^[1]

Альтернативный алгоритм [ править ]

Альтернативный способ написать решение задачи интерполяции:

${\displaystyle f(x,y)\approx a_{0}+a_{1}x+a_{2}y+a_{3}xy,}$

где коэффициенты находятся из решения линейной системы

${\displaystyle {\begin{aligned}{\begin{bmatrix}1&x_{1}&y_{1}&x_{1}y_{1}\\1&x_{1}&y_{2}&x_{1}y_{2}\\1&x_{2}&y_{1}&x_{2}y_{1}\\1&x_{2}&y_{2}&x_{2}y_{2}\end{bmatrix}}{\begin{bmatrix}a_{0}\\a_{1}\\a_{2}\\a_{3}\end{bmatrix}}={\begin{bmatrix}f(Q_{11})\\f(Q_{12})\\f(Q_{21})\\f(Q_{22})\end{bmatrix}},\end{aligned}}}$

дающий результат

${\displaystyle {\begin{aligned}a_{0}&={\frac {f(Q_{11})x_{2}y_{2}}{(x_{1}-x_{2})(y_{1}-y_{2})}}+{\frac {f(Q_{12})x_{2}y_{1}}{(x_{1}-x_{2})(y_{2}-y_{1})}}+{\frac {f(Q_{21})x_{1}y_{2}}{(x_{1}-x_{2})(y_{2}-y_{1})}}+{\frac {f(Q_{22})x_{1}y_{1}}{(x_{1}-x_{2})(y_{1}-y_{2})}},\\a_{1}&={\frac {f(Q_{11})y_{2}}{(x_{1}-x_{2})(y_{2}-y_{1})}}+{\frac {f(Q_{12})y_{1}}{(x_{1}-x_{2})(y_{1}-y_{2})}}+{\frac {f(Q_{21})y_{2}}{(x_{1}-x_{2})(y_{1}-y_{2})}}+{\frac {f(Q_{22})y_{1}}{(x_{1}-x_{2})(y_{2}-y_{1})}},\\a_{2}&={\frac {f(Q_{11})x_{2}}{(x_{1}-x_{2})(y_{2}-y_{1})}}+{\frac {f(Q_{12})x_{2}}{(x_{1}-x_{2})(y_{1}-y_{2})}}+{\frac {f(Q_{21})x_{1}}{(x_{1}-x_{2})(y_{1}-y_{2})}}+{\frac {f(Q_{22})x_{1}}{(x_{1}-x_{2})(y_{2}-y_{1})}},\\a_{3}&={\frac {f(Q_{11})}{(x_{1}-x_{2})(y_{1}-y_{2})}}+{\frac {f(Q_{12})}{(x_{1}-x_{2})(y_{2}-y_{1})}}+{\frac {f(Q_{21})}{(x_{1}-x_{2})(y_{2}-y_{1})}}+{\frac {f(Q_{22})}{(x_{1}-x_{2})(y_{1}-y_{2})}}.\end{aligned}}}$

Если решение является предпочтительным с точки зрения f ( Q ), то мы можем написать

${\displaystyle f(x,y)\approx b_{11}f(Q_{11})+b_{12}f(Q_{12})+b_{21}f(Q_{21})+b_{22}f(Q_{22}),}$

где коэффициенты находятся путем вычисления

${\displaystyle {\begin{bmatrix}b_{11}\\b_{12}\\b_{21}\\b_{22}\end{bmatrix}}=\left({\begin{bmatrix}1&x_{1}&y_{1}&x_{1}y_{1}\\1&x_{1}&y_{2}&x_{1}y_{2}\\1&x_{2}&y_{1}&x_{2}y_{1}\\1&x_{2}&y_{2}&x_{2}y_{2}\end{bmatrix}}^{-1}\right)^{\rm {T}}{\begin{bmatrix}1\\x\\y\\xy\end{bmatrix}}.}$

Единичный квадрат [ править ]

Если мы выберем систему координат, в которой четыре точки, в которых известно f, это (0, 0), (1, 0), (0, 1) и (1, 1), то формула интерполяции упрощается до

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

или, что то же самое, в матричных операциях:

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

В качестве альтернативы интерполянт на единичном квадрате можно записать как

${\displaystyle f(x,y)=\sum _{i=1}^{2}\sum _{j=1}^{2}a_{ij}x^{i-1}y^{j-1}=a_{11}+a_{21}x+a_{12}y+a_{22}xy,}$

куда

${\displaystyle {\begin{aligned}a_{11}&=f(1,1),\\a_{21}&=f(2,1)-f(1,1),\\a_{12}&=f(1,2)-f(1,1),\\a_{22}&=f(2,2)+f(1,1)-{\big (}f(2,1)+f(1,2){\big )}.\end{aligned}}}$

В обоих случаях количество констант (четыре) соответствует количеству точек данных, где задано f . Интерполянт является линейным по линиям, параллельным направлению x или y , что эквивалентно, если x или y заданы постоянными. Вдоль любой другой прямой интерполянт квадратичный . Тем не менее, даже если интерполяция не линейная в положении ( х и у ), оно является линейным по амплитуде, как это видно из уравнений выше: все коэффициенты _J , J= 1–4, пропорциональны значению функции f .

Результат билинейной интерполяции не зависит от того, какая ось интерполируется первой, а какая - второй. Если бы мы сначала выполнили линейную интерполяцию в направлении y, а затем в направлении x , результирующее приближение было бы таким же.

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

Применение в обработке изображений [ править ]

Сравнение билинейной интерполяции с некоторыми 1- и 2-мерными интерполяциями. Черные и красные / желтые / зеленые / синие точки соответствуют интерполированной точке и соседним отсчетам соответственно. Их высота над землей соответствует их значениям.

В компьютерном зрении и обработке изображений билинейная интерполяция используется для передискретизации изображений и текстур. Алгоритм используется для сопоставления местоположения пикселя экрана с соответствующей точкой на карте текстуры . Средневзвешенное значение атрибутов (цвет, прозрачность и т. Д.) Четырех окружающих текселей вычисляется и применяется к пикселю экрана. Этот процесс повторяется для каждого пикселя, образующего текстурированный объект. ^[2]

Когда изображение необходимо увеличить, каждый пиксель исходного изображения необходимо переместить в определенном направлении на основе постоянной масштаба. Однако при увеличении масштаба изображения с помощью нецелого масштабного коэффициента есть пиксели (т. Е. Дыры ), которым не присвоены соответствующие значения пикселей. В этом случае этим отверстиям должны быть назначены соответствующие значения RGB или оттенков серого, чтобы в выходном изображении не было пикселей без значений.

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

Билинейная интерполяция рассматривает ближайшую окрестность 2 × 2 известных значений пикселей, окружающую вычисленное местоположение неизвестного пикселя. Затем требуется средневзвешенное значение этих 4 пикселей, чтобы получить окончательное интерполированное значение. ^[3]

Пример билинейной интерполяции в оттенках серого

Как видно из примера справа, значение интенсивности в пикселе, вычисленном как строка 20.2, столбец 14.5, может быть вычислено сначала путем линейной интерполяции между значениями в столбцах 14 и 15 в каждой строке 20 и 21, давая

${\displaystyle {\begin{aligned}I_{20,14.5}&={\frac {15-14.5}{15-14}}\cdot 91+{\frac {14.5-14}{15-14}}\cdot 210=150.5,\\I_{21,14.5}&={\frac {15-14.5}{15-14}}\cdot 162+{\frac {14.5-14}{15-14}}\cdot 95=128.5,\end{aligned}}}$

а затем линейно интерполируя эти значения, давая

${\displaystyle I_{20.2,14.5}={\frac {21-20.2}{21-20}}\cdot 150.5+{\frac {20.2-20}{21-20}}\cdot 128.5=146.1.}$

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

См. Также [ править ]

• Бикубическая интерполяция
• Трилинейная интерполяция
• Сплайн-интерполяция
• Передискретизация Ланцоша
• Интерполяция ступенек
• Барицентрические координаты - для интерполяции внутри треугольника или тетраэдра.

Ссылки [ править ]