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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

Четыре красные точки представляют собой известные значения функции. Значение в зеленой точке должно быть интерполировано.
Пример билинейной интерполяции в единичном квадрате. Значения вершин составляют 0, 1, 1 и 0.5. Интерполированные значения в каждой точке представлены цветом.

Алгоритм[править | править вики-текст]

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

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

Теперь проводится линейная интерполяция между вспомогательными точками и .

Это и есть интерполируемое (экстраполируемое) значение функции , причём значения интерполирующей функции равны значениям интерполируемой функции в исходных точках :

В частном случае, когда известные точки являются вершинами единичного квадрата с координатами (0, 0), (0, 1), (1, 0), и (1, 1), формула билинейной интерполяции упрощается до

Или же с помощью умножения векторов на матрицу:

Обратите внимание, что сам интерполянт не линеен, а билинеен:

где

.

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

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

Билинейная интерполяция в компьютерной графике[править | править вики-текст]

Пример увеличения части изображения — простым масштабированием и с применением билинейной интерполяции

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

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

Недостаток метода[править | править вики-текст]

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

Связано это с тем, что в исходном изображении, например, по горизонтали имеется точек, то есть смежных пар. При увеличении изображения в раз между каждой парой основных точек вставляется по дополнительных точек (то есть при увеличении вдвое между основными точками вставляется ещё по одной, при увеличении втрое — по две и т. д.). Итого в результате ширина результирующего изображения будет равна сумме количества основных и дополнительных точек:

.

Проще говоря, для пикселей по границам изображения (в каждой строке и столбце) исходного изображения не находится пары, с которой можно было бы провести интерполирование.

Для обхода данного ограничения, во-первых, обычно принимается, что в исходном и полученном изображениях цветовые значения пикселей семплированы из их центров, нежели из углов, то есть например, если принять абсолютную длину и ширину изображения равными 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) и т. д.). Затем, так как значения в этих точках не могут быть интерполированы, то нужно расширить исходное изображение одним из способов (выбор которого зависит от способа дальнейшего использования изображения):

  • Экстраполяция значений краевых пикселей;
  • Зеркальное отражение исходного изображения относительно каждого края, и центральное по углам. В качестве значений отсутствующих пикселей используются копии значений пикселей с того же края; таким образом, пиксели, выпадающие за исходные координаты, являются интерполянтами лишь в одном измерении, а в другом копиями краевых значений;
  • Тесселяция исходного изображения: копии исходного изображения «приклеиваются» встык с каждого края и из углов. В качестве цветовых значений отсутствующих пикселей, таким образом, используются значения пикселей с противоположного края. Метод подходит, если интерполированное изображение само будет использоваться для тесселяции (например, для заполнения многоугольников при текстурировании).

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

См. также[править | править вики-текст]