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

(Перенаправлено из билинейной фильтрации ) Четыре красных точки показывают точки данных, а зеленая точка - точка, в которой мы хотим выполнить интерполяцию. Пример билинейной интерполяции на единичном квадрате с указанными значениями z 0, 1, 1 и 0,5. Интерполированные значения между ними представлены цветом.

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

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

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

• 1 Алгоритм
  • 1.1 Альтернативный алгоритм
  • 1.2 Единичный квадрат
  • 1.3 Нелинейный
• 2 Применение в обработке изображений
• 3 См. Также
• 4 ссылки

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

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

${\ displaystyle {\ begin {align} f (x, y_ {1}) amp; \ приблизительно {\ 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}) amp; \ приблизительно {\ 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 {align} f (x, y) amp; \ приблизительно {\ frac {y_ {2} -y} {y_ {2} -y_ {1}}} f (x, y_ {1}) + {\ frac {y-y_ {1}} {y_ {2} -y_ {1}}} f (x, y_ {2}) \\ amp; = {\ 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) \\ amp; = {\ 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) \\ amp; = {\ frac {1} {(x_ {2} -x_ {1}) (y_ {2} -y_ {1})}} {\ begin {bmatrix} x_ {2} - x amp; x-x_ {1} \ end {bmatrix}} {\ begin {bmatrix} f (Q_ {11}) amp; f (Q_ {12}) \\ f (Q_ {21}) amp; f (Q_ {22}) \ end {bmatrix}} {\ begin {bmatrix} y_ {2} -y \\ y-y_ {1} \ end {bmatrix}}. \ end {align}}}$

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

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

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

${\ displaystyle f (x, y) \ приблизительно a_ {0} + a_ {1} x + a_ {2} y + a_ {3} xy,}$

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

${\ displaystyle {\ begin {align} {\ begin {bmatrix} 1 amp; x_ {1} amp; y_ {1} amp; x_ {1} y_ {1} \\ 1 amp; x_ {1} amp; y_ {2} amp; x_ {1} y_ {2} \ \ 1 amp; x_ {2} amp; y_ {1} amp; x_ {2} y_ {1} \\ 1 amp; x_ {2} amp; y_ {2} amp; 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 {выравнивается}}}$

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

${\ displaystyle {\ begin {align} a_ {0} amp; = {\ 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} amp; = {\ 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} amp; = {\ 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} amp; = {\ 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 {align}}}$

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

${\ displaystyle f (x, y) \ приблизительно 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 amp; x_ {1 } amp; y_ {1} amp; x_ {1} y_ {1} \\ 1 amp; x_ {1} amp; y_ {2} amp; x_ {1} y_ {2} \\ 1 amp; x_ {2} amp; y_ {1} amp; x_ {2} y_ {1} \ \ 1 amp; x_ {2} amp; y_ {2} amp; 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) \ приблизительно 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) \ приблизительно {\ begin {bmatrix} 1-x amp; x \ end {bmatrix}} {\ begin {bmatrix} f (0,0) amp; f (0,1) \\ f (1, 0) amp; 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} y ^ {j} = a_ {11} + a_ {21} x + a_ {12} y + a_ {22} xy,}$

где

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

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

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

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

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

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

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

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

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

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

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

${\ displaystyle {\ begin {align} I_ {20,14.5} amp; = {\ frac {15-14.5} {15-14}} \ cdot 91 + {\ frac {14.5-14} {15-14}} \ cdot 210 = 150,5, \\ I_ {21,14,5} amp; = {\ frac {15-14,5} {15-14}} \ cdot 162 + {\ frac {14.5-14} {15-14}} \ cdot 95 = 128,5, \ end {выровнено}}}$

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

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

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

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

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