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

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

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

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

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

Вычисление

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

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

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

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

{\begin{aligned}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{aligned}}

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

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

Полиномиальная аппроксимация

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

f(x,y)\approx a_{00}+a_{10}x+a_{01}y+a_{11}xy,

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

{\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_{00}\\a_{10}\\a_{01}\\a_{11}\end{bmatrix}}={\begin{bmatrix}f(Q_{11})\\f(Q_{12})\\f(Q_{21})\\f(Q_{22})\end{bmatrix}},\end{aligned}}

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

{\begin{aligned}{\begin{bmatrix}a_{00}\\a_{10}\\a_{01}\\a_{11}\end{bmatrix}}={\frac {1}{(x_{2}-x_{1})(y_{2}-y_{1})}}{\begin{bmatrix}x_{2}y_{2}&-x_{2}y_{1}&-x_{1}y_{2}&x_{1}y_{1}\\-y_{2}&y_{1}&y_{2}&-y_{1}\\-x_{2}&x_{2}&x_{1}&-x_{1}\\1&-1&-1&1\end{bmatrix}}{\begin{bmatrix}f(Q_{11})\\f(Q_{12})\\f(Q_{21})\\f(Q_{22})\end{bmatrix}}.\end{aligned}}

Взвешенное среднее

Решение также можно записать как значение f средневзвешенное ( Q ):

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

где сумма весов равна 1 и удовлетворяет транспонированной линейной системе

{\begin{bmatrix}1&1&1&1\\x_{1}&x_{1}&x_{2}&x_{2}\\y_{1}&y_{2}&y_{1}&y_{2}\\x_{1}y_{1}&x_{1}y_{2}&x_{2}y_{1}&x_{2}y_{2}\end{bmatrix}}{\begin{bmatrix}w_{11}\\w_{12}\\w_{21}\\w_{22}\end{bmatrix}}={\begin{bmatrix}1\\x\\y\\xy\end{bmatrix}},

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

{\begin{aligned}{\begin{bmatrix}w_{11}\\w_{21}\\w_{12}\\w_{22}\end{bmatrix}}={\frac {1}{(x_{2}-x_{1})(y_{2}-y_{1})}}{\begin{bmatrix}x_{2}y_{2}&-y_{2}&-x_{2}&1\\-x_{2}y_{1}&y_{1}&x_{2}&-1\\-x_{1}y_{2}&y_{2}&x_{1}&-1\\x_{1}y_{1}&-y_{1}&-x_{1}&1\end{bmatrix}}{\begin{bmatrix}1\\x\\y\\xy\end{bmatrix}},\end{aligned}}

что упрощается до

{\begin{aligned}w_{11}&=(x_{2}-x)(y_{2}-y)/((x_{2}-x_{1})(y_{2}-y_{1})),\\w_{12}&=(x_{2}-x)(y-y_{1})/((x_{2}-x_{1})(y_{2}-y_{1})),\\w_{21}&=(x-x_{1})(y_{2}-y)/((x_{2}-x_{1})(y_{2}-y_{1})),\\w_{22}&=(x-x_{1})(y-y_{1})/((x_{2}-x_{1})(y_{2}-y_{1})),\end{aligned}}

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

Альтернативная форма матрицы

Объединив вышесказанное, мы имеем

{\begin{aligned}f(x,y)\approx {\frac {1}{(x_{2}-x_{1})(y_{2}-y_{1})}}{\begin{bmatrix}f(Q_{11})&f(Q_{12})&f(Q_{21})&f(Q_{22})\end{bmatrix}}{\begin{bmatrix}x_{2}y_{2}&-y_{2}&-x_{2}&1\\-x_{2}y_{1}&y_{1}&x_{2}&-1\\-x_{1}y_{2}&y_{2}&x_{1}&-1\\x_{1}y_{1}&-y_{1}&-x_{1}&1\end{bmatrix}}{\begin{bmatrix}1\\x\\y\\xy\end{bmatrix}}.\end{aligned}}

На единичной площади

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

f(x,y)\approx f(0,0)(1-x)(1-y)+f(0,1)(1-x)y+f(1,0)x(1-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}}.

Здесь мы также узнаем веса:

{\begin{aligned}w_{11}&=(1-x)(1-y),\\w_{12}&=(1-x)y,\\w_{21}&=x(1-y),\\w_{22}&=xy.\end{aligned}}

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

f(x,y)=a_{00}+a_{10}x+a_{01}y+a_{11}xy,

где

{\begin{aligned}a_{00}&=f(0,0),\\a_{10}&=f(1,0)-f(0,0),\\a_{01}&=f(0,1)-f(0,0),\\a_{11}&=f(1,1)-f(1,0)-f(0,1)+f(0,0).\end{aligned}}

В обоих случаях количество констант (четыре) соответствует количеству точек данных, в которых f задано .

Характеристики

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

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

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

Обратное и обобщение

В общем, интерполянт принимает любое значение (в выпуклой оболочке значений вершин) в бесконечном количестве точек (образуя ветви гипербол ^[2]), поэтому интерполяция необратима.

Однако когда билинейная интерполяция применяется к двум функциям одновременно, например, при интерполяции векторного поля , тогда интерполяция обратима (при определенных условиях). В частности, это обратное можно использовать для нахождения «единичных квадратных координат» точки внутри любого выпуклого четырехугольника (путем рассмотрения координат четырехугольника как векторного поля, которое билинейно интерполируется на единичном квадрате). С помощью этой процедуры билинейную интерполяцию можно распространить на любой выпуклый четырехугольник, хотя вычисление значительно усложняется, если он не является параллелограммом. ^[3] Результирующая карта между четырехугольниками известна как билинейное преобразование , билинейная деформация или билинейное искажение .

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

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

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

Обратные вычисления

Let ${\textstyle F}$ be a vector field that is bilinearly interpolated on the unit square parameterized by ${\textstyle \mu ,\lambda \in [0,1]}$ . Inverting the interpolation requires solving a system of two bilinear polynomial equations: $A+B\lambda +C\mu +D\lambda \mu =0$ where ${\begin{aligned}A&=F_{00}-F\\B&=F_{10}-F_{00}\\C&=F_{01}-F_{00}\\D&=F_{11}-F_{01}-F_{10}+F_{00}\end{aligned}}$ Taking a 2-d cross product (see Grassman product) of the system with a carefully chosen vectors allows us to eliminate terms: ${\begin{aligned}(A+B\lambda +C\mu )&\times D&=0\\(A+B\lambda )&\times (C+D\lambda )&=0\\(A+C\mu )&\times (B+D\mu )&=0\\\end{aligned}}$ which expands to ${\begin{aligned}c+e\lambda +f\mu &=0\\b+(c+d)\lambda +e\lambda ^{2}&=0\\a+(c-d)\mu +f\mu ^{2}&=0\\\end{aligned}}$ where ${\begin{aligned}a&=A\times B\\b&=A\times C\qquad d=B\times C\\c&=A\times D\qquad e=B\times D\qquad f=C\times D\end{aligned}}$ The quadratic equations can be solved using the quadratic formula. We have the equivalent determinants $\mathbb {D} =(c+d)^{2}-4eb=(c-d)^{2}-4fa$ and the solutions $\lambda ={\frac {-c-d\pm {\sqrt {\mathbb {D} }}}{2e}}\qquad \mu ={\frac {-c+d\mp {\sqrt {\mathbb {D} }}}{2f}}$ (opposite signs are enforced by the linear relation). The cases when $e=0$ or $f=0$ must be handled separately. Given the right conditions, one of the two solutions should be in the unit square.

Применение в обработке изображений

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

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

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

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

Пример

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

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

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

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.

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

Упрощение терминов

В этом примере представлены табличные данные о давлении (столбцы) и температуре (строки) как поиск по некоторой переменной.

Т\П	П_{1}	П_{х}	П_{2}
Т_{1}	V_{11}	В_{1x}	V_{12}
Т_{х}		В_{хх}
Т_{2}	V_{21}	V_{2x}	V_{22}

Следующий стандартный расчет по деталям имеет 18 обязательных операций.

{\begin{aligned}I_{T_{1},P_{1}-P_{2}}&={\frac {P_{2}-P_{x}}{P_{2}-P_{1}}}\cdot V_{11}+{\frac {P_{x}-P_{1}}{P_{2}-P_{1}}}\cdot V_{12}=V_{1x},\\I_{T_{2},P_{1}-P_{2}}&={\frac {P_{2}-P_{x}}{P_{2}-P_{1}}}\cdot V_{21}+{\frac {P_{x}-P_{1}}{P_{2}-P_{1}}}\cdot V_{22}=V_{2x},\\I_{P_{x},T_{1}-T_{2}}&={\frac {T_{2}-T_{x}}{T_{2}-T_{1}}}\cdot V_{1x}+{\frac {T_{x}-T_{1}}{T_{2}-T_{1}}}\cdot V_{2x}=V_{xx}\end{aligned}}

Все это можно упростить с первоначальных 18 отдельных операций до 16 отдельных операций как таковых;

V_{xx}={\frac {((P_{2}-P_{x})\cdot V_{11}+(P_{x}-P_{1})\cdot V_{12})\cdot (T_{2}-T_{x})+((P_{2}-P_{x})\cdot V_{21}+(P_{x}-P_{1})\cdot V_{22})\cdot (T_{x}-T_{1})}{(P_{2}-P_{1})\cdot (T_{2}-T_{1})}}.

Вышеупомянутое имеет две повторяющиеся операции.

(P_{2}-P_{x}),(P_{x}-P_{1}).

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

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

См. также

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

Ссылки

^ Пресс, Уильям Х.; Теукольский, Саул А.; Веттерлинг, Уильям Т.; Фланнери, Брайан П. (1992). Численные рецепты на C: искусство научных вычислений (2-е изд.). Нью-Йорк, штат Нью-Йорк, США: Издательство Кембриджского университета. стр. 123-128 . ISBN 0-521-43108-5 .
^ Монасс, Паскаль (10 августа 2019 г.). «Извлечение линий уровня билинейного изображения» . Обработка изображений в режиме онлайн . 9 : 205–219. дои : 10.5201/ipol.2019.269 . ISSN 2105-1232 .
^ Килес, Иниго (2010). «Обратная билинейная интерполяция» . iquilezles.org . Архивировано из оригинала 13 августа 2010 г. Проверено 17 февраля 2024 г.
^ Определение билинейной интерполяции (популярная статья на www.pcmag.com .
^ Хосрави, М.Р. (19 марта 2021 г.). «BL-ALM: слепой масштабируемый фильтр реконструкции с краевым управлением для интеллектуального мониторинга окружающей среды с помощью зеленых сетей IoMT-БПЛА» . Транзакции IEEE по экологически чистым коммуникациям и сетям . 5 (2): 727–736. дои : 10.1109/TGCN.2021.3067555 . S2CID 233669511 .
^ «Веб-руководство: Интерполяция цифровых изображений» .

[1] Пресс, Уильям Х.; Теукольский, Саул А.; Веттерлинг, Уильям Т.; Фланнери, Брайан П. (1992). Численные рецепты на C: искусство научных вычислений (2-е изд.). Нью-Йорк, штат Нью-Йорк, США: Издательство Кембриджского университета. стр. 123-128 . ISBN 0-521-43108-5 .

[2] Монасс, Паскаль (10 августа 2019 г.). «Извлечение линий уровня билинейного изображения» . Обработка изображений в режиме онлайн . 9 : 205–219. дои : 10.5201/ipol.2019.269 . ISSN 2105-1232 .

[3] Килес, Иниго (2010). «Обратная билинейная интерполяция» . iquilezles.org . Архивировано из оригинала 13 августа 2010 г. Проверено 17 февраля 2024 г.

[4] Определение билинейной интерполяции (популярная статья на www.pcmag.com .

[5] Хосрави, М.Р. (19 марта 2021 г.). «BL-ALM: слепой масштабируемый фильтр реконструкции с краевым управлением для интеллектуального мониторинга окружающей среды с помощью зеленых сетей IoMT-БПЛА» . Транзакции IEEE по экологически чистым коммуникациям и сетям . 5 (2): 727–736. дои : 10.1109/TGCN.2021.3067555 . S2CID 233669511 .

[6] «Веб-руководство: Интерполяция цифровых изображений» .

[1]

[2]

[3]

[4]

[5]

[6]