Русская Википедия:Билинейная интерполяция
Билине́йная интерполя́ция — в вычислительной математике — обобщение линейной интерполяции одной переменной для функций двух переменных.
Обобщение основано на применении обычной линейной интерполяции сначала в направлении одной из координат, а затем в перпендикулярном направлении.
Функция билинейной интерполяции имеет вид:
- <math>F(x,y) = b_1 + b_2 \cdot x + b_3 \cdot y + b_4 \cdot x \cdot y</math>
и интерполирует значения исходной функции двух переменных в произвольном прямоугольнике по четырём её значениям в вершинах прямоугольника и экстраполирует функцию на всю остальную поверхность.
Принцип построения билинейной интерполяции
Допустим, что необходимо интерполировать значение функции <math>f(x, y)</math> в точке <math>P = (x, y)</math>. Значения функции в окружающих точку <math>P</math> точках <math>Q_{11} = (x_1, y_1),</math> <math>Q_{12} = (x_1, y_2),</math> <math> Q_{21} = (x_2, y_1)</math> и <math>Q_{22} = (x_2, y_2)</math> известны (рис. 1).
Первым шагом линейно интерполируется значение вспомогательных точек <math>R_1</math> и <math>R_2</math> вдоль оси абсцисс, где
- <math>R_1 = (x,y_1)</math>
- <math>R_2 = (x,y_2)</math>
- <math> 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})</math>
- <math> 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})</math>
Теперь проводится линейная интерполяция между вспомогательными точками <math>R_1</math> и <math>R_2</math>.
- <math> 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). </math>
Это и есть интерполируемое (экстраполируемое) значение функции <math>f(x, y)</math>, причём значения интерполирующей функции <math>F(x, y)</math> равны значениям интерполируемой функции в исходных точках <math>(x_1, y_1); (x_1, y_2); (x_2, y_1); (x_2, y_2)</math>:
- <math>
\begin{align} 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{align} </math>
Другим эквивалентным способом неизвестные коэффициенты <math>b_1,\ b_2,\ b_3,\ b_4</math> интерполирующей функции (интерполянта) можно найти из решения системы линейных уравнений относительно коэффициентов интерполянта <math>F(x,y) = b_1 + b_2 \cdot x + b_3 \cdot y + b_4 \cdot x \cdot y</math>:
- <math>f(Q_{11}) = b_1 + b_2 \cdot x_1 + b_3 \cdot y_1 + b_4 \cdot x_1 \cdot y_1,</math>
- <math>f(Q_{12}) = b_1 + b_2 \cdot x_1 + b_3 \cdot y_2 + b_4 \cdot x_1 \cdot y_2,</math>
- <math>f(Q_{21}) = b_1 + b_2 \cdot x_2 + b_3 \cdot y_1 + b_4 \cdot x_2 \cdot y_1,</math>
- <math>f(Q_{22}) = b_1 + b_2 \cdot x_2 + b_3 \cdot y_2 + b_4 \cdot x_2 \cdot y_2.</math>
В частном случае, когда известны значения интерполируемой функции в точках, являющихся вершинами единичного квадрата с координатами вершин (0, 0), (0, 1), (1, 0), и (1, 1), формула билинейной интерполяции упрощается до:
- <math> 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. </math>
Или же в обозначениях умножения векторов на матрицу:
- <math> 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}</math>
Обратите внимание, что сам интерполянт не линеен, а билинеен:
- <math> F(x,y) = b_1 + b_2 x + b_3 y + b_4 x y,</math>
где
- <math> b_1 = f(0,0)</math>
- <math> b_2 = f(1,0)-f(0,0)</math>
- <math> b_3 = f(0,1)-f(0,0)</math>
- <math> b_4 = f(0,0)-f(1,0)-f(0,1)+f(1,1)</math>.
Результат билинейной интерполяции не зависит от порядка шагов по координатам. Возможно сначала интерполировать между заданными точками вдоль оси ординат и затем, получив два вспомогательных значения, интерполировать между ними вдоль оси абсцисс.
Обобщение билинейной интерполяции на функции трёх и более переменных
Интерполянт билинейной интерполяции можно записать в виде:
- <math> F(x,y) = \sum_{i=0}^1 \sum_{j=0}^1 a_{ij} x^i y^j = a_{00} + a_{10} x + a_{01} y + a_{11} x y,</math>
соответственно, интерполянт трилинейной интерполяции функции трёх переменных <math> f(x,y,z)</math> записывается как:
- <math> F(x,y,z) = \sum_{i=0}^1 \sum_{j=0}^1 \sum_{k=0}^1 a_{ijk} x^i y^j z^k =</math>
- <math> = a_{000} + a_{100} x + a_{010} y + a_{001} z + a_{110} x y + a_{101} x z + a_{011} y z + a_{111} x y z.</math>
Неизвестные коэффициенты <math>a_{ijk}</math> находятся из решения системы 8-ми линейных уравнений по известным значениям интерполируемой функции <math>f(x,y,z)</math> в 8-ми точках, принадлежащих вершинам прямоугольного параллелепипеда в координатах <math>x,y,z</math>:
- <math>f(x_0, y_0, z_0) = a_{000} + a_{100} x_0 + a_{010} y_0 + a_{001} z_0 + a_{110} x_0 y_0 + a_{101} x_0 z_0 + a_{011} y_0 z_0 + a_{111} x_0 y_0 z_0,</math>
- <math>f(x_1, y_0, z_0) = a_{000} + a_{100} x_1 + a_{010} y_0 + a_{001} z_0 + a_{110} x_1 y_0 + a_{101} x_1 z_0 + a_{011} y_0 z_0 + a_{111} x_1 y_0 z_0,</math>
- <math>f(x_0, y_1, z_0) = a_{000} + a_{100} x_0 + a_{010} y_1 + a_{001} z_0 + a_{110} x_0 y_1 + a_{101} x_0 z_0 + a_{011} y_1 z_0 + a_{111} x_0 y_1 z_0,</math>
- <math>f(x_0, y_0, z_1) = a_{000} + a_{100} x_0 + a_{010} y_0 + a_{001} z_1 + a_{110} x_0 y_0 + a_{101} x_0 z_1 + a_{011} y_0 z_1 + a_{111} x_0 y_0 z_1,</math>
- <math>f(x_1, y_1, z_0) = a_{000} + a_{100} x_1 + a_{010} y_1 + a_{001} z_0 + a_{110} x_1 y_1 + a_{101} x_1 z_0 + a_{011} y_1 z_0 + a_{111} x_1 y_1 z_0,</math>
- <math>f(x_1, y_0, z_1) = a_{000} + a_{100} x_1 + a_{010} y_0 + a_{001} z_1 + a_{110} x_1 y_0 + a_{101} x_1 z_1 + a_{011} y_0 z_1 + a_{111} x_1 y_0 z_1,</math>
- <math>f(x_0, y_1, z_1) = a_{000} + a_{100} x_0 + a_{010} y_1 + a_{001} z_1 + a_{110} x_0 y_1 + a_{101} x_0 z_1 + a_{011} y_1 z_1 + a_{111} x_0 y_1 z_1,</math>
- <math>f(x_1, y_1, z_1) = a_{000} + a_{100} x_1 + a_{010} y_1 + a_{001} z_1 + a_{110} x_1 y_1 + a_{101} x_1 z_1 + a_{011} y_1 z_1 + a_{111} x_1 y_1 z_1.</math>
В случае линейной интерполяции функции <math>N</math> переменных <math>f(u_1, u_2, ... u_N)</math> линейный интерполянт будет:
- <math> F(u_1, u_2, ... u_N) = \sum_{i_1=0}^1 \sum_{i_2=0}^1...\sum_{i_N=0}^1 a_{i_1i_2...i_N} u_1^{i_1}u_2^{i_2}...u_N^{i_N}.</math>
<math>2^N</math> коэффициентов интерполянта <math>a_{i_1i_2...i_N}</math> находятся из решения системы <math>2^N</math> линейных уравнений по известным значениям интерполируемой функции <math>f(u_1, u_2, ... u_N)</math> в вершинах прямоугольного гиперпараллелепипеда.
Использование билинейной интерполяции
Билинейная интерполяция применяется при обработке числовых данных, в метеорологии и гидродинамике, сопротивлении материалов, в компьютерной графике, для компенсации ошибок перемещения инструмента по координатам в станках с ЧПУ и др.
Билинейная интерполяция двумерных векторных полей
Помимо интерполяции скалярного двумерного поля, — то есть функции двух переменных (координат), билинейная интерполяция также применяется для интерполяции двумерных векторных полей. При такой интерполяции интерполируются обе компоненты векторного поля — проекции вектора в точках на оси координат. Результат интерполяции двух скалярных функций — компонентов вектора, порождает интерполированный вектор.
Этот подход применяется в метеорологии для построения интерполированной карты ветров в прямоугольной области по измеренным данным значений векторов ветра в опорных точках, принадлежащих вершинам прямоугольника[1].
Билинейная интерполяция в компьютерной графике
Заданные значения функции изображены цветными точками, значение функции в интерполируемой точке — черными точками.
Изображены одномерная и двумерная интерполяции к ближайшему соседу, линейная, квадратическая, кубическая билинейная, биквадратная и бикубическая интерполяции.
В компьютерной графике билинейная интерполяция наряду с другими методами интерполяций получила широкое распространение в процессе ресемплинга (или, проще говоря, масштабирования) изображений. Билинейную интерполяцию в приложениях обработки изображений обычно называют «билинейной фильтрацией». Применение этого метода обусловлено относительно низкой вычислительной ресурсоёмкости, что снижает время на ресемплинг при удовлетворительном качестве обработки изображений.
Необходимость интерполяции цветов в обработке цифровых изображений обусловлена тем, что при простом увеличении изображений без обработки происходит сильная пикселизация картинки.
Билинейная интерполяция — один из методов интерполяции и используется для вычисления цветов дополнительных пикселей (<math>P</math>) относительно основных, исходных, заданных в оригинальном изображении с известными цветовыми координатами <math>Q</math>, причем цветовые координаты пикселей, лежащих внутри прямоугольника с заданными цветовыми координатами в вершинах его, или одна цветовая координата в случае полутоновых изображений, вычисляются во всех точках между опорными точками, что позволяет сглаживать резкие границы между пикселями исходного изображения. Значения функций <math>f</math> в данном случае вычисляется по цветовым координатам опорных точек. При этом сторона квадрата, образованного четырьмя смежными рассматриваемыми основными точками обычно принимается за единицу.
Недостаток метода билинейной интерполяции при масштабировании изображений
Главный недостаток метода билинейной интерполяции при масштабировании изображений — при увеличении в <math>N</math> раз исходного изображения размером <math>W</math> на <math>H</math> пикселей в результате будет получено изображение размером не <math>N \cdot W</math> на <math>N \cdot H</math> пикселей, а <math>(N(W-1)+1)</math> на <math>(N(H-1)+1)</math> пикселей.
Связано это с тем, что в исходном изображении, например, по горизонтали имеется <math>W</math> точек, то есть <math>(W-1)</math> смежных пар. При увеличении изображения в <math>N</math> раз между каждой парой основных точек вставляется по <math>(N-1)</math> дополнительных точек (то есть при увеличении вдвое между основными точками вставляется ещё по одной, при увеличении втрое — по две и т. д.). Итого в результате ширина результирующего изображения будет равна сумме количества основных и дополнительных точек:
- <math>W + (W-1)(N-1) = N(W-1)+1</math>.
Проще говоря, для пикселей по границам изображения (в каждой строке и столбце) исходного изображения не находится пары, с которой можно было бы провести интерполирование.
Для обхода данного ограничения, во-первых, обычно принимается, что в исходном и полученном изображениях цветовые значения пикселей семплированы из их центров, нежели из углов, то есть например, если принять абсолютную длину и ширину изображения равными 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) и т. д.). Затем, так как значения в этих точках не могут быть интерполированы, то нужно расширить исходное изображение одним из способов (выбор которого зависит от способа дальнейшего использования изображения):
- Экстраполяция значений краевых пикселей;
- Зеркальное отражение исходного изображения относительно каждого края, и центральное по углам. В качестве значений отсутствующих пикселей используются копии значений пикселей с того же края; таким образом, пиксели, выпадающие за исходные координаты, являются интерполянтами лишь в одном измерении, а в другом копиями краевых значений;
- Тесселяция исходного изображения: копии исходного изображения «приклеиваются» встык с каждого края и из углов. В качестве цветовых значений отсутствующих пикселей, таким образом, используются значения пикселей с противоположного края. Метод подходит, если интерполированное изображение само будет использоваться для тесселяции (например, для заполнения многоугольников при текстурировании).
После подобной предварительной обработки процедура билинейной интерполяции применяется в исходном виде, с получением изображения ожидаемого размера (<math>N \cdot W</math> на <math>N \cdot H</math>).
См. также
Примечания
