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

Метод интерполяции функций на двумерной сетке

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

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

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

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

Вычисление

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

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

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

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

${\displaystyle {\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, чтобы получить желаемую оценку:

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

Полиномиальная подгонка

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

${\displaystyle f(x,y)\approx a_{00}+a_{10}x+a_{01}y+a_{11}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_{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}}}$

давая результат

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

${\displaystyle 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 и удовлетворяет транспонированной линейной системе

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

давая результат

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

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

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

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

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

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

${\displaystyle {\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), то формула интерполяции упрощается до

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

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

${\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 {\begin{aligned}w_{11}&=(1-x)(1-y),\\w_{12}&=(1-x)y,\\w_{21}&=x(1-y),\\w_{22}&=xy.\end{aligned}}}$

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

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

где

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Пример

Как видно из примера справа, значение интенсивности в пикселе, вычисленное как находящееся в строке 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.}$

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

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

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

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

${\displaystyle {\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 отдельных операций;

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

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

${\displaystyle (P_{2}-P_{x}),(P_{x}-P_{1}).}$

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

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

Смотрите также

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

Ссылки

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