Что такое интерполяция в компьютерной графике
Обучение переводу статей англоязычной документации, статьи про алгоритмы, а также LifeHacks, статьи по Компьютеру и Программированию, Журнал для Детей, Математику и смежные науки Инженерии.
Поиск по этому блогу
Алгоритмы - Интерполяция. Начальная концепция
Данная стать посвящена алгоритмам интерполяции на примере увеличения и уменьшения изображений. В статье описываются алгоритмы про интерполяцию в общем и интерполяцию на примере изменения размера изображений. Главное выделить смысл заполнения промежутков (включая значащие точки) при увеличении и уменьшении.
1. Введение
Интерполяция — это определение промежутков дискретной функции при потере её значения (к примеру, из-за качества сигнала датчика) или её масштабирование с помощью интерполянтов.
Интерполяция позволяет получить необходимые значения для промежутков или разрывов между значащими точками. Значащие точки — это уже известные точки функции, к примеру, точки изначального изображения, показания с датчиков, имеемые точки функции и т.п.
Не путайте данные методы интерполяции с математеческими методами интерполяции (линейная интерполяция с продолжением, полином Лагранжа, т.п.).
2. Виды интерполяции
В статье приведено несколько видов интерполяции. Это позволит узнать возможности интерполяции на базовом, хотя можно сказать, на продвинутом уровне и придумать более сложные способы интерполяции(интерполянты). Хотя достаточно и этих способов для всех случаев, хотя и не обязательно — решайте сами, но я предлагаю для всего линейную, билёнейную интерполяцию и развитие её смысла для других базисов.
Далее рассматриваются способы интерполяции, приведённые примеры интерполирования решаются системой линейных алгебраических уравнений, подстановкой значащих точек в уравнение интерполянта.
2.1. Интерполяция в одномерном пространстве
Интеполирование в одномерном пространстве представляет нахождение собой значение функции y(t), где известны значащие точки y1(t1), y2(t2), y3(t3), y4(t4) и т.д., но нужно найти значение между ними. Значение находится на промежутках [t1;t2],[t2;t3];[t3;t4] и т.д.
2.2. Дублирование до следующего/предыдущего
Смысл этого способа интерполяции заключается в том, что значение функции дублируется до следующего или предыдущего значения, но однозначно для последующих точек.
Далее рассмотрим рисунок этой концепции:
- Значение функции слева
- Значение функции справа
- Восстановленное (интерполированное) значение функции
- Восстановленное (интерполированное) значение функции, одно из
- Альтернативное восстановленное (интерполированное) значение функции
- Альтернативное восстановленное (интерполированное) значение функции, одно из
Рис. 1. Концепция Интерполяции способом дублирования значения (для способа дублирования до правого/левого).
2.3. Интерполяция способом дублирования до ближайшего соседа
Смысл этого способа интерполяции заключается в том, что значение функции берётся то, как у ближайшего соседа. Этот вид интерполяции по результату равен 1-ому способу (2.1. Дублирование до следующего).
Интерполяция дублированием до ближайшего соседа
- Значение функции слева
- Значение функции справа
- Восстановленное (интерполированное) значение функции
- Восстановленное (интерполированное) значение функции, одно из
Рис. 2. Концепция Интерполяции способом дублирования до ближайшего соседа.
2.4. Линейная интерполяция
Смысл этого способа интерполяции заключается в том, что значение функции берётся линией, соединяющей две точки.
Значение левой точки
Значение правой точки
Viewer does not support full SVG 1.1
Рис. 3.1. Концепция Линейной интерполяции.
- Значение функции слева
- Значение функции справа
- Восстановленное (интерполированное) значение функции
- Восстановленное (интерполированное) значение функции, одно из
Рис. 3.2. Концепция Линейной интерполяции.
2.5. Квадратическая интерполяция
Смысл интерполяции заключается в том, что значения точек соединяются кривыми второго порядка (квадратичными или они также называются параболами).
Квадратичная кривая проходит через три точки, которые не являются корнями уравнения параболы, но она через них проходит не симметрично. Парабола геометрически однозначно задаётся тремя точками. Просьба не путать с корнями параболы, корня у параболы максимум два, и они означают координаты точек(и) пересечения с осью абсцисс. Попробуйте написовать параболы и вы увидите, что через три случайные точки однозначно проходит только одна парабола и интервалы не одинаковы.
Viewer does not support full SVG 1.1
Рис. 4. Концепция Квадратической интерполяции.
2.6. Кубическая интерполяция
Интерполяция заключается в том, чтобы провести кубическую кривую, через 4 точки.
Viewer does not support full SVG 1.1
Рис. 5. Концепция Кубической интерполяции.
2.7. Радиальная интерполяция
На рисунке далее две значащие точки соединяются кругом:
Значение левой точки
Значение правой точки
Viewer does not support full SVG 1.1
Рис. 6.1. Концепция Радиальной интерполяции.
На Рис. 6.1. показана концепция Радиальной интерполяции, если между точками равные промежутки. Представьте себе уровни значений значащих точек на круге: если считать, что между точками не равные промежутки, а они просто должны попадать на круг последовательно, то можно интерполировать сразу три значащие точки:
Viewer does not support full SVG 1.1
Рис. 6.2. Концепция Радиальной интерполяции.
Это свойство можно использовать для всех интерполянтов и оно представлено на всех примерах инетрполянтов выше и ниже.
2.8. Эллиптическая интерполяция
Эллиптическая интерполяция производится по аналогии с радиальной, но кривой берётся эллипс.
Viewer does not support full SVG 1.1
Рис. 7. Концепция Эллиптической интерполяции.
2.9. Интерполяция Кривыми Безье
Интерполяция может проводиться любыми Кривыми Безье. На Рисунке 8 приведён пример интерполяции Кривыми Безье второго порядка.
Кривыми Безье 2-го порядка
Viewer does not support full SVG 1.1
Рис. 8. Концепция интерполяции Кривыми Безье.
2.10. Двумерная интерполяция
Интеполирование в двумерном (трёхмерном, если учитывать для базиса ещё один вектор для значения функции) пространстве представляет нахождение собой значение функции z(x,y), где известны значащие точки z1(x1, y1), z2(x2, y2), z3(x3, y3), z4(x4, y4) и т.д., но нужно найти значение между ними. Интерполяция происходит для промежутком значащих координат функции.
2.11. Двумерная интерполяция Дублированием до следующего/предыдущего
Пусть у нас есть значащие точки функции z(x,y) и нужно интерполировать точку между четырмя значащими точкима дублированием. Для этого точки нумеруются однозначно и интерполирование идёт повторением одно определённой точки с одинаковым номером (позицией).
Двумерная интерполяция Дублированием до следующего/предыдущегоДвумерная интерполяция Дублированием до следующего/предыдущего
Viewer does not support full SVG 1.1
Рис. 9. Концепция Двумерной интерполяции Дублированием до следующего/предыдущего.
На Рис. 9 показана интерполяция повторением точки 1.
2.12. Двумерная интерполяция по ближайшему соседу
Пусть у нас есть функция z(x,y) и есть четыре значащих точки, между которыми требуется интерполировать значение. Для этого вычисляем расстояние до каждой точки на плоскости XY и выбираем минимальное расстояние. При равных расстояниях, можно выбрать точку до которой происходит округление.
Двумерная интерполяция по ближайшему соседу
Viewer does not support full SVG 1.1
Рис. 10. Концепция Двумерной интерполяции по ближайшему соседу.
2.13. Билинейная интерполяция
На координатах задаются проекции на ось, на которых сами точки соеденены линиями. Проецирование заданных координат для интерполяции происходит на линию, соединяющие заданные точки. Потом пересечения в свою очередь соединяются линиями, как понятно, они проходят над начальными коодинатами. От начальных координат до них (их пересечения) строится интерполированное значение. Аналагично строятся точки в примерах далее.
Viewer does not support full SVG 1.1
Рис. 11. Концепция Билинейной интерполяции.
2.14. Биквадратическая интерполяция
Биквадратическая происходит также, как и биленейная, но уже точки и интерполируемая точка соединяются не линиями, а квадратическими кривыми.
Viewer does not support full SVG 1.1
Рис. 12. Концепция Биквадратической интерполяции.
2.15. Бикубическая интерполяция
Бикубическая схожа остальным типам двумерной интерполяции, только требует больше значащих точек, и соединять уже нужно искомые точки кубическими кривыми.
Viewer does not support full SVG 1.1
Рис. 13. Концепция Бикубической интерполяции.
2.16. Бирадиальная интерполяция, Биэллиптическая интерполяция, Би-интерполяция Кривыми Безье.
Бирадиальная интерполяция, Биэллиптическая интерполяция, Би-интерполяция Кривыми Безье по смыслу и количеству точек схожа с Биквадратической интерполяцией, только отличие в том, что находимые и значащие точки соединяются не квадратическими кривыми, а соответствующие виду интерполяции. Их концепцию можно понять по картинке Биквадратической интерполяции.
Концепция Бирадиальной интерполяции, Биэллиптической интерполяции, Би-интерполяции Кривыми Безье на примере БиквадратическойКонцепция Бирадиальной интерполяции, Биэллиптической интерполяции, Би-интерполяции Кривыми Безье на примере Биквадратической
Viewer does not support full SVG 1.1
Рис. 14. Концепция Бирадиальной интерполяции, Биэллиптической интерполяции, Би-интерполяции Кривыми Безье.
2.17. Трипл-интерполяция и более
Интерполянт задаётся в базисе уравнением от переменных (n-1), где n — это размер базиса. Значение функции от этих переменных — это интерполируемое значение.
Т.е. к примеру 3D-интерполянт задаётся функцией f(x,y,z) для 4-х мерного базиса. Как представлено ранее, би-интерполяция — это задание интерполянта функцией z(x,y).
2.18. Интерполянт
Значение левой точки
Значение правой точки
Viewer does not support full SVG 1.1
Рис. 15. Интерполянт.
Значение, соединяющее точки, генерируемое по функции, параметрическому уравнению, ряду и т.п. называется интерполянтом. Придумывайте свои для каждого случая или довольствуйтесь линейным. Интерполянт можно использовать для заполнения промежутков, для поиска неизвесных точек. Так же, аналогично интерполянт можно использовать для увеличения или уменьшения. Значение увеличеное (или уменьшенное) определяется только по интерполянтам. Иными словами, если нам нужно заполнить промежутки между точками, вызванные масштабированием или потерей значения, то эти промежутки заполняются специальным правилом, называемым интерполянтом.
К примеру, интерполянт может быть другой для Вашего случая, но более чем достаточно приведённных способов интерполяции.
2.18.1. Требования к интерполянту
К примеру, требованием может быть то, что набор значений и интреполянт имеют равный уровень дискретизации, или он представляет собой усилитель резкости, или предназначен для уменьшения дефектов сжатия, или др.
Другой интерполянт и требования к нему
- Значение функции слева
- Значение функции справа
Рис. 16. Другой интерполянт.
Основное свойство для проектируемого интерполянта — он должен однозначно заполнять промежутки для заданных настроек/конфигурации.
2.19. Интерполяция функций (сводка)
В данном разделе статьи приведена сводная картина для интерполирования функций с множеством значений. Рисунки выше показывают только определённые частоприменяемые концепции, далее приведина их сводная картина.
Рисунок очень большой по размеру, так что просмотреть его можно только у себя на компьютере или плакате: Сводная картина интерполянтов.
3. Интеполирование изображений в GIMP
В данном разделе приведены примеры интерполяции при увеличении изображения в программе GIMP 2.10.8.
Если будете писать свой графический редактор, то запрограммируйте интеполянт так, чтобы он однозначно заполнял промежутки для заданных настроек/конфигурации.
Далее приведём пример работы программы, на примере следующего изображения:
Рис. 17. Исходное изображение.
- Cпособом дублирования до ближайшего соседа
- Линейная интерполяция
- Бикубическая интерполяция
И в конце сравним эти четыре типа по результатам.
Рассмотрим только увеличение на части Рис. 17:
Рис. 18. Исходное изображение. Увеличивываемая часть.
3.1. Одномерная способом дублирования до ближайшего соседа
Рис. 19. Увеличение дублированием.
3.2. Линейная
Рис. 20. Линейное увеличение.
3.3. Бикубическая
Рис. 21. Кубическое увеличение.
3.4. Сравнение результатов
Посмотрим на рисунок далее и сравним результаты:
Рис. 22. Сравнение увеличений.
Как видно, кубическая интерполяция дала самый лучший результат. Если Вам требуется увеличить изображение без потери значащих точек, то интерполяция дублированием подойдёт Вам. Линейная интерполяция изображений оказалась менее точной, по сравнению с кубической, но она требует меньше процессорного времени.
4. Заключение
В заключение могу пожелать Вам написание своего графического редактора, развивать другой или смелее пользоваться готовыми. Можно также написать консольную утилиту для интерполяции изображений.
Не путайте данные методы интерполяции с математеческими методами интерполяции (линейная интерполяция с продолжением, полином Лагранжа, т.п.).
Как построить график по n точкам? Самое простое — отметить их маркерами на координатной сетке. Однако для наглядности их хочется соединить, чтобы получить легко читаемую линию. Соединять точки проще всего отрезками прямых. Но график-ломаная читается довольно тяжело: взгляд цепляется за углы, а не скользит вдоль линии. Да и выглядят изломы не очень красиво. Получается, что кроме ломаных нужно уметь строить и кривые. Однако тут нужно быть осторожным, чтобы не получилось вот такого:
Немного матчасти
Восстановление промежуточных значений функции, которая в данном случае задана таблично в виде точек P1 .  Pn, называется интерполяцией. Есть множество способов интерполяции, но все они могут быть сведены к тому, что надо найти n – 1 функцию для расчёта промежуточных точек на соответствующих сегментах. При этом заданные точки обязательно должны быть вычислимы через соответствующие функции. На основе этого и может быть построен график:
Функции fi могут быть самыми разными, но чаще всего используют полиномы некоторой степени. В этом случае итоговая интерполирующая функция (кусочно заданная на промежутках, ограниченных точками Pi) называется сплайном.
В разных инструментах для построения графиков — редакторах и библиотеках — задача «красивой интерполяции» решена по-разному. В конце статьи будет небольшой обзор существующих вариантов. Почему в конце? Чтобы после ряда приведённых выкладок и размышлений можно было поугадывать, кто из «серьёзных ребят» какие методы использует.
Ставим опыты
Самый простой пример — линейная интерполяция, в которой используются полиномы первой степени, а в итоге получается ломаная, соединяющая заданные точки.
Давайте добавим немного конкретики. Вот набор точек (взяты почти с потолка):
Результат линейной интерполяции этих точек выглядит так:
Однако, как отмечалось выше, иногда хочется получить в итоге гладкую кривую.
Что есть гладкость? Бытовой ответ: отсутствие острых углов. Математический: непрерывность производных. При этом в математике гладкость имеет порядок, равный номеру последней непрерывной производной, и область, на которой эта непрерывность сохраняется. То есть, если функция имеет гладкость порядка 1 на отрезке [a; b], это означает, что на [a; b] она имеет непрерывную первую производную, а вот вторая производная уже терпит разрыв в каких-то точках.
У сплайна в контексте гладкости есть понятие дефекта. Дефект сплайна — это разность между его степенью и его гладкостью. Степень сплайна — это максимальная степень использованных в нём полиномов.
Важно отметить, что «опасными» точками у сплайна (в которых может нарушиться гладкость) являются как раз Pi, то есть точки сочленения сегментов, в которых происходит переход от одного полинома к другому. Все остальные точки «безопасны», ведь у полинома на области его определения нет проблем с непрерывностью производных.
Чтобы добиться гладкой интерполяции, нужно повысить степень полиномов и подобрать их коэффициенты так, чтобы в граничных точках сохранялась непрерывность производных.
Традиционно для решения такой задачи используют полиномы третьей степени и добиваются непрерывности первой и второй производной. То, что получается, называют кубическим сплайном дефекта 1. Вот как он выглядит для наших данных:
Кривая, действительно, гладкая. Но если предположить, что это график некоторого процесса или явления, который нужно показать заинтересованному лицу, то такой метод, скорее всего, не подходит. Проблема в ложных экстремумах. Появились они из-за слишком сильного искривления, которое было призвано обеспечить гладкость интерполяционной функции. Но зрителю такое поведение совсем не кстати, ведь он оказывается обманут относительно пиковых значений функции. А ради наглядной визуализации этих значений, собственно, всё и затевалось.
Так что надо искать другие решения.
Другое традиционное решение, кроме кубических сплайнов дефекта 1 — полиномы Лагранжа. Это полиномы степени n – 1, принимающие заданные значения в заданных точках. То есть членения на сегменты здесь не происходит, вся последовательность описывается одним полиномом.
Но вот что получается:
Гладкость, конечно, присутствует, но наглядность пострадала так сильно, что… пожалуй, стоит поискать другие методы. На некоторых наборах данных результат выходит нормальный, но в общем случае ошибка относительно линейной интерполяции (и, соответственно, ложные экстремумы) может получаться слишком большой — из-за того, что тут всего один полином на все сегменты.
В компьютерной графике очень широко применяются кривые Безье, представленные полиномами k-й степени.
Они не являются интерполирующими, так как из k + 1 точек, участвующих в построении, итоговая кривая проходит лишь через первую и последнюю. Остальные k – 1 точек играют роль своего рода «гравитационных центров», притягивающих к себе кривую.
Вот пример кубической кривой Безье:
Как это можно использовать для интерполяции? На основе этих кривых тоже можно построить сплайн. То есть на каждом сегменте сплайна будет своя кривая Безье k-й степени (кстати, k = 1 даёт линейную интерполяцию). И вопрос только в том, какое k взять и как найти k – 1 промежуточную точку.
Здесь бесконечно много вариантов (поскольку k ничем не ограничено), однако мы рассмотрим классический: k = 3.
Чтобы итоговая кривая была гладкой, нужно добиться дефекта 1 для составляемого сплайна, то есть сохранения непрерывности первой и второй производных в точках сочленения сегментов (Pi), как это делается в классическом варианте кубического сплайна.
Решение этой задачи подробно (с исходным кодом) рассмотрено здесь.
Вот что получится на нашем тестовом наборе:
Стало лучше: ложные экстремумы всё ещё есть, но хотя бы не так сильно отличаются от реальных.
Думаем и экспериментируем
Можно попробовать ослабить условие гладкости: потребовать дефект 2, а не 1, то есть сохранить непрерывность одной только первой производной.
Достаточное условие достижения дефекта 2 в том, что промежуточные контрольные точки кубической кривой Безье, смежные с заданной точкой интерполируемой последовательности, лежат с этой точкой на одной прямой и на одинаковом расстоянии:
В качестве прямых, на которых лежат точки Ci – 1 (2) , Pi и Ci (1) , целесообразно взять касательные к графику интерполируемой функции в точках Pi. Это гарантирует отсутствие ложных экстремумов, так как кривая Безье оказывается ограниченной ломаной, построенной на её контрольных точках (если эта ломаная не имеет самопересечений).
Методом проб и ошибок эвристика для расчёта расстояния от точки интерполируемой последовательности до промежуточной контрольной получилась такой:
Первая и последняя промежуточные контрольные точки равны первой и последней точке графика соответственно (точки C1 (1) и Cn – 1 (2) совпадают с точками P1 и Pn соответственно).
В этом случае получается вот такая кривая:
Как видно, ложных экстремумов уже нет. Однако если сравнивать с линейной интерполяцией, местами ошибка очень большая. Можно сделать её ещё меньше, но тут в ход пойдут ещё более хитрые эвристики.
К текущему варианту мы пришли, уменьшив гладкость на один порядок. Можно сделать это ещё раз: пусть сплайн будет иметь дефект 3. По факту, тем самым формально функция не будет гладкой вообще: даже первая производная может терпеть разрывы. Но если рвать её аккуратно, визуально ничего страшного не произойдёт.
Отказываемся от требования равенства расстояний от точки Pi до точек Ci – 1 (2) и Ci (1) , но при этом сохраняем их все лежащими на одной прямой:
Эвристика для вычисления расстояний будет такой:
При этом, однако, стоит ещё проверять, не совпали ли точки Pi и Pi + 1 по ординате, и, если совпали, полагать l1 = l2 = 0. Это защитит от «вспухания» графика на плоских отрезках (что тоже немаловажно с точки зрения правдивого отображения данных).
Результат получается такой:
Результат следующий:
На этом было принято решение признать цель достигнутой.
Может быть, кому-то пригодится код.
А как люди-то делают?
Обещанный обзор. Конечно, перед решением задачи мы посмотрели, кто чем может похвастаться, а уже потом начали разбираться, как сделать самим и по возможности лучше. Но вот как только сделали, не без удовольствия ещё раз прошлись по доступным инструментам и сравнили их результаты с плодами наших экспериментов. Итак, поехали.
MS Excel
Это очень похоже на рассмотренный выше сплайн дефекта 1, основанный на кривых Безье. Правда, в отличие от него в чистом виде, тут всего два ложных экстремума — первый и второй сегменты (у нас было четыре). Видимо, к классическому поиску промежуточных контрольных точек тут добавляются ещё какие-то эвристики. Но ото всех ложных экстремумов они не спасли.
LibreOffice Calc
В настройках это названо кубическим сплайном. Очевидно, он тоже основан на Безье, и вот тут уже точная копия нашего результата: все четыре ложных экстремума на месте.
Есть там ещё один тип интерполяции, который мы тут не рассматривали: B-сплайн. Но для нашей задачи он явно не подходит, так как даёт вот такой результат :)
Highcharts, одна из самых популярных JS-библиотек для построения диаграмм
Тут налицо «метод касательных» в варианте равенства расстояний от точки интерполируемой последовательности до промежуточных контрольных. Ложных экстремумов нет, зато есть сравнительно большая ошибка относительно линейной интерполяции (седьмой сегмент).
amCharts, ещё одна популярная JS-библиотека
Картина очень похожа на экселевскую, те же два ложных экстремума в тех же местах.
Coreplot, самая популярная библиотека построения графиков для iOS и OS X
Есть ложные экстремумы и видно, что используется сплайн дефекта 1 на основе Безье.
Библиотека открытая, так что можно посмотреть в код и убедиться в этом.
aChartEngine, вроде как самая популярная библиотека построения графиков для Android
Больше всего похоже на кривую Безье степени n – 1, хотя в самой библиотеке график называется «cubic line». Странно! Как бы то ни было, тут не только присутствуют ложные экстремумы, но и в принципе не выполняются условия интерполяции.
Привет, Хабр! Сегодня мы очень подробно расскажем о неочевидных моментах в такой, казалось бы, простой операции: исправлении проективных искажений на изображении. Как это часто оказывается в жизни, нам пришлось выбирать, что важнее: качество или скорость. И чтобы достичь некого баланса мы вспомнили об алгоритмах, которые активно исследовали еще в 80-90-е годы в рамках задачи рендеринга структур, и с тех пор редко вспоминали в контексте обработки изображений. Если интересно, заглядывайте под кат!
Модель камеры обскуры, которая на практике неплохо приближает и короткофокусные камеры мобильных телефонов, подсказывает нам что при поворотах камеры изображения плоского объекта связаны между собой проективным преобразованием. Общий вид проективного преобразования такой:
где матрица проективного преобразования, и координаты на исходном и преобразованном изображениях.
Геометрическое преобразование изображений
Проективное преобразование изображения — это одно из возможных геометрических преобразований изображений (таких преобразований, при которых точки исходного изображения переходят в точки конечного изображения согласно определенному закону).
Чтобы разобраться в том, как именно следует решать задачу геометрического преобразования цифрового изображения, нужно учитывать модель его формирования из оптического изображения на матрице камеры. Согласно Г. Уолбергу [1] наш алгоритм должен аппроксимировать следующий процесс:
- Восстановление оптического изображения из цифрового.
- Геометрическое преобразование оптического изображения.
- Дискретизация (англ. sampling) преобразованного изображения.
- На плоскости конечного изображения выбирается сетка отсчетов (англ. sampling grid) — точек, по которым мы будем оценивать значения пикселей конечного изображения (это может быть центр каждого пикселя, а может быть несколько точек на пиксель).
- С помощью обратного геометрического преобразования эта сетка переносится в пространство исходного изображения.
- Для каждого отсчета сетки оценивается его значение. Поскольку он не обязательно окажется в точке с целыми координатами, нам потребуется некоторая интерполяция значения изображения, например, интерполяция по соседним пикселям.
- По отчетам сетки оцениваем значения пикселей конечного изображения.
Интерполяция
Здесь мы рассмотрим только простые виды интерполяции — те, которые можно представить в виде свертки изображения с интерполяционным ядром. В контексте обработки изображений лучше бы подошли алгоритмы адаптивной интерполяции, которые сохраняют четкие границы объектов, однако их вычислительная сложность существенно выше и потому нам не интересна.
Будем рассматривать следующие методы интерполяции:
- по ближайшему пикселю,
- билинейную,
- бикубическую,
- кубическим b-сплайном,
- кубическим эрмитовым сплайном, по 36 точкам.
Поэтому сравним Фурье-спектры наших ядер интерполяции с фильтром низких частот (на рисунках представлены для одномерного случая).
И что, можно просто взять ядро с достаточно хорошим спектром и получить относительно точные результаты? На самом деле нет, потому что выше мы сделали два допущения: о том что есть значение пикселя изображения и о непрерывности этого изображения. При этом ни то ни другое не является частью хорошей модели формирования изображения, ведь датчики на матрице камеры не точечные, а на изображении очень много информации несут границы объектов — разрывы. Поэтому, увы, следует понимать, что результат интерполяции всегда будет отличаться от оригинального оптического изображения.
Но делать что-то все-таки нужно, поэтому коротко опишем достоинства и недостатки каждого из рассматриваемых методов с практической точки зрения. Проще всего это увидеть при увеличении масштаба изображения (в данном примере — в 10 раз).
Интерполяция по ближайшему пикселю
Самая простая и самая быстрая, однако она приводит к сильным артефактам.
Билинейная интерполяция
Лучше по качеству, но требует больше вычислений и вдобавок размывает границы объектов.
Бикубическая интерполяция
Еще лучше в непрерывных областях, но на границе возникает эффект гало (более темная полоса вдоль темного края границы и светлая вдоль светлого). Чтобы избежать такого эффекта нужно использовать неотрицательное ядро свертки например кубический b-сплайн.
Интерполяция B-сплайном
У b-сплайна очень узкий спектр, что означает сильное “размытие” изображение (но и хорошее шумоподавление, что может быть полезно).
Итерполяция на основе кубического Эрмитового сплайна
Такой сплайн требует оценки частных производных в каждом пикселе изображения. Если для приближения мы выберем 2-точечную разностную схему то мы получим ядро бикубической интерполяции, поэтому тут мы используем 4-точечную.
Сравним эти методы также по числу обращений в память (числу пикселей исходного изображения для интерполяции в одной точке) и по числу операций умножения на точку.
| Интерполяция | Число пикселей | Число умножений |
| По ближайшему | 1 | 0 |
| Билинейная | 4 | 8 |
| Бикубическая | 16 | 68 |
| B-сплайн | 16 | 68 |
| Эрмитов сплайн | 36 | 76 |
Видно, что последние 3 способа существенно более вычислительно затратные, чем первые 2.
Дискретизация
Это тот самый шаг, которому совершенно незаслуженно уделяется очень мало внимания в последнее время. Самый простой способ произвести проективное преобразование изображения — оценить значение каждого пикселя конечного изображения по значению, которое получается при обратном преобразовании его центра на плоскость исходного изображения (с учетом выбранного метода интерполяции). Такой подход назовем попиксельной дискретизацией. Однако в областях, где изображение сжимается, это может привести к существенным артефактам, вызванным проблемой наложения спектров при недостаточной частоте дискретизации.
Наглядно продемонстрируем артефакты сжатия на образце паспорта РФ и отдельном его поле — место рождения (гор. Архангельск), сжатым с помощью попиксельной дискретизации или алгоритма FAST, который мы рассмотрим ниже.
Видно, что текст на левом изображении стал нечитаемым. Правильно, ведь мы берем всего одну точку из целого региона исходного изображения!
Раз нам не удалось выполнить оценку по одному пикселю, то почему бы не выбрать больше отсчетов на пиксель, а полученные значения усреднить? Такой подход называется суперсемплинг. Он действительно увеличивает качество, но вместе с тем и вычислительная сложность возрастает пропорционально числу отсчетов на пиксель.
Более вычислительно эффективные методы были придуманы в конце прошлого века, когда в компьютерной графике решалась задача рендеринга текстур, наложенных на плоские объекты. Одним из таких методов является преобразование с помощью mip-map структуры. Mip-map это пирамида изображений состоящая из самого исходного изображения, а также его копий уменьшенных в 2, 4, 8 и так далее раз. Для каждого пикселя мы оцениваем, какая степень сжатия для него характерна, и в соответствие с этой степенью выбираем нужный уровень из пирамиды, в качестве исходного изображения. Есть разные способы оценивать подходящий уровень mip-map (см. подробнее [2]). Здесь мы воспользуемся методом, на основе оценки частных производных по известной матрице проективного преобразования. Однако чтобы избежать артефактов в тех областях конечного изображения, где один уровень mip-map структуры переходит в другой, обычно используют линейную интерполяцию между двумя соседними уровнями пирамиды (это не сильно увеличивает вычислительную сложность, ведь координаты точек на соседних уровнях однозначно связаны).
Однако mip-map никак не учитывает тот факт, что сжатие изображения может быть анизотропным (вытянутым вдоль какого-то направления). Частично эту проблему позволяет решить rip-map. Структура в которой независимо хранятся изображения сжатые в раз по горизонтали и раз по вертикали. В этом случае, после определения коэффициентов сжатия по горизонтали и по вертикали в данной точке конечного изображения, производится интерполяция между результатами с 4, сжатых в нужное число раз, копий исходного изображения. Но и этот метод не идеален, ведь он не учитывает, что направление анизотропии отличаться от направлений, параллельных границам исходного изображения.
Частично эту проблему позволяет решить алгоритм FAST (Footprint Area Sampled Texturing) [3]. Он объединяет идеи mip-map-а и суперсэмплинга. Мы оцениваем степень сжатия исходя из оси наименьшей анизотропии и выбираем число отсчетов пропорционально отношению длин наименьшей оси к наибольшей.
Прежде чем сравнивать эти подходы по вычислительной сложности, оговоримся, что в целях ускорения подсчета обратного проективного преобразования, рационально сделать следующую замену:
где , — матрица обратного проективного преобразования. Так как и функции одного аргумента мы можем их пред-подсчитать за пропорциональное линейному размеру изображения время. Тогда для вычисления координат прообраза одной точки конечного изображения , потребуется только 1 деление и 2 умножения. Аналогичный трюк можно провернуть с частными производными, которые используются для определения уровня в mip-map или rip-map структуре.
Теперь мы готовы сравнить результаты по вычислительной сложности.
| Метод | Число отсчетов на пиксель | Число умножений на отсчет | Дополнительная память для структур (в долях исходного изображения) |
| Попиксельная дискретизация | 1 | 2 | 0 |
| Суперсемплинг | n | 2 | 0 |
| Mip-map | 2 | 7 | 1/3 |
| Rip-map | 4 | 7 | 3 |
| Fast | <= n | 7 | 1/3 |
И сравнить визуально (слева направо попиксельная дискретизация, суперсемплиг по 49 отсчетам, mip-map, rip-map, FAST).
Эксперимент
А теперь, давайте сравним наши результаты экспериментально. Составим алгоритм проективного преобразования сочетающий каждый из 5 методов интерполяции и 5 методов дискретизации (всего 25 вариантов). Возьмем 20 изображений документов обрезанных до размера 512x512 пикселей, сгенерируем 10 наборов из 3-х матриц проективного преобразования, таких что каждый набор в целом эквивалентен тождественному преобразованию и будем сравнивать PSNR между исходным изображением и преобразованным. Напомним что PSNR это , где это максимум по исходному изображению а — среднеквадратичное отклонение конечного от исходного. Чем больше PSNR тем лучше. Так же будем замерять время работы проективного преобразования на ODROID-XU4 с процессором ARM Cortex-A15 (2000 MHz и 2GB RAM).
Интерполяция изображений происходит во всех цифровых фотографиях на определённом этапе, будь то дематризация или масштабирование. Она происходит всякий раз, когда вы изменяете размер или развёртку изображения из одной сетки пикселей в другую. Изменение размера изображения необходимо,когда вам нужно увеличить или уменьшить число пикселей, тогда как изменение положения может происходить в самых различных случаях: исправление искажений объектива, смена перспективы или поворот изображения.
 |  |  |
 | ||
| Исходное изображение | После интерполяции |
|---|
Даже если изменению размера или развёртки подвергается одно и то же изображение, результаты могут значительно отличаться в зависимости от алгоритма интерполяции. Поскольку любая интерполяция является всего лишь приближением, изображение будет несколько терять в качестве всякий раз, когда подвергается интерполяции. Данная глава призвана обеспечить лучшее понимание того, что оказывает влияние на результат, — и тем самым помочь вам минимизировать любые потери качества изображения, вызванные интерполяцией.
Концепция
Суть интерполяции заключается в использовании имеющихся данных для получения ожидаемых значений в неизвестных точках. Например, если вам захотелось знать, какова была температура в полдень, но измеряли её в 11 и в час, можно предположить её значение, применив линейную интерполяцию:
Если бы у вас имелось дополнительное измерение в половине двенадцатого, вы могли бы заметить, что до полудня температура росла быстрее, и использовать это дополнительное измерение для квадратической интерполяции:
Чем больше измерений температуры вы будете иметь около полудня,тем более комплексным (и ожидаемо более точным) может быть ваш алгоритм интерполяции.
Пример изменения размера изображения
Интерполяция изображений работает в двух измерениях и пытается достичь наилучшего приближения в цвете и яркости пикселя, основываясь на значениях окружающих пикселей. Следующий пример иллюстрирует работу масштабирования:
плоскостная интерполяция | ||||
|---|---|---|---|---|
 |  |  |  |  |
| Оригинал | до | после | без интерполяции | |
В отличие от колебаний температуры воздуха и вышеприведенного идеального градиента, значения пикселей могут меняться намного более резко от точки к точке. Как и в примере с температурой, чем больше вы знаете об окружающих пикселях, тем лучше сработает интерполяция. Вот почему результаты быстро ухудшаются по мере растягивания изображения, а кроме того, интерполяция никогда не сможет добавить изображению детальности, которой в нём нет.
Пример вращения изображения
Интерполяция происходит также каждый раз, когда вы поворачиваете или изменяете перспективу изображения. Предыдущий пример был обманчив, поскольку это частный случай, в котором интерполяторы обычно работают неплохо. Следующий пример показывает, как быстро может быть потеряна детальность изображения:
| Деградация изображения | |||||
 |  |  |  | ||
| Оригинал | поворот на 45° | поворот на 90° (без потерь) | 2 поворота на 45° | 6 поворотов на 15° | |
Поворот на 90° не вносит потерь, поскольку ни один пиксель не требуется поместить на границу между двумя (и как следствие разделить). Заметьте, как большая часть деталей теряется при первом же повороте, и как качество продолжает падать при последующих. Это означает, что следует избегать вращений, насколько возможно; если неровно выставленный кадр требует поворота, не следует вращать его более одного раза.
Вышеприведенные результаты используют так называемый «бикубический» алгоритм и показывают существенное ухудшение качества. Обратите внимание, как снижается общий контраст в связи со снижением интенсивности цвета, как вокруг светло-синего возникают тёмные гало. Результаты могут быть значительно лучше в зависимости от алгоритма интерполяции и изображаемого предмета.
Типы алгоритмов интерполяции
Общепринятые алгоритмы интерполяции можно поделить на две категории: адаптивные и неадаптивные. Адаптивные методы изменяются в зависимости от предмета интерполяции (резкие границы, гладкая текстура), тогда как неадаптивные методы обрабатывают все пиксели одинаково.
Неадаптивные алгоритмы включают: метод ближайшего соседа, билинейный, бикубический, сплайны, функция кардинального синуса (sinc), метод Ла́нцоша и другие. В зависимости от сложности, они используют от 0 до 256 (или более) смежных пикселей для интерполяции. Чем более смежных пикселей они включают, тем более точными могут оказаться, но это достигается за счёт значительного прироста времени обработки. Эти алгоритмы могут использоваться как для развёртки, так и для масштабирования изображения.
Адаптивные алгоритмы включают в себя многие коммерческие алгоритмы в лицензированных программах, таких как Qimage, PhotoZoom Pro, Genuine Fractals и другие. Многие из них применяют различные версии своих алгоритмов (на основе попиксельного анализа), когда обнаруживают наличие границы — с целью минимизировать неприглядные дефекты интерполяции в местах, где они наиболее видны. Эти алгоритмы в первую очередь разработаны для максимизации бездефектной детальности увеличенных изображений, так что некоторые из них для вращения или изменения перспективы изображения непригодны.
Метод ближайшего соседа
Это наиболее базовый из всех алгоритмов интерполяции, который требует наименьшего времени обработки, поскольку учитывает только один пиксель — ближайший к точке интерполяции. В результате каждый пиксель просто становится больше.
Билинейная интерполяция
Билинейная интерполяция рассматривает квадрат 2x2 известных пикселя, окружающих неизвестный. В качестве интерполированного значения используется взвешенное усреднение этих четырёх пикселей. В результате изображения выглядят значительно более гладко, чем результат работы метода ближайшего соседа.
Диаграмма слева относится к случаю, когда все известные пиксели равны, так что интерполированное значение просто является их суммой, поделенной на 4.
Бикубическая интерполяция
Бикубическая интерполяция идёт на один шаг дальше билинейной, рассматривая массив из 4x4 окружающих пикселей — всего 16. Поскольку они находятся на разных расстояниях от неизвестногопикселя, ближайшие пиксели получают при расчёте больший вес. Бикубическая интерполяция производит значительно более резкие изображения, чем предыдущие два метода, и возможно, является оптимальной по соотношению времени обработки и качества на выходе. По этой причине она стала стандартной для многих программ редактирования изображений (включая Adobe Photoshop), драйверов принтеров и встроенной интерполяции камер.
Интерполяция высшего порядка: сплайны и sinc
Есть много других интерполяторов, которые принимают во внимание больше окружающих пикселей и таким образом требуют более интенсивных вычислений. Эти алгоритмы включают в себя сплайны и кардинальный синус (sinc), и они сохраняют большинство информации об изображении после интерполяции. Как следствие, они являются исключительно полезными, когда изображение требует нескольких поворотов или изменений перспективы за отдельные шаги. Однако, для однократных увеличений или поворотов такие алгоритмы высшего порядка дают незначительное визуальное улучшение при существенном увеличении времени обработки. Более того, в некоторых случаях алгоритм кардинального синуса на гладком участке отрабатывает хуже, чем бикубическая интерполяция.
Наблюдаемые дефекты интерполяции
Все неадаптивные интерполяторы пытаются подобрать оптимальный баланс между тремя нежелательными дефектами: граничными гало, размытием и ступенчатостью.
Даже наиболее развитые неадаптивные интерполяторы всегда вынуждены увеличивать или уменьшать один из вышеприведенных дефектов за счёт двух других — как следствие, как минимум один из них будет заметен. Заметьте, насколько граничное гало похоже на дефект, порождаемый повышением резкости с помощью нерезкой маски, и как оно повышает кажущуюся резкость посредством усиления чёткости.
Адаптивные интерполяторы могут создавать или не создавать вышеописанные дефекты, но они тоже могут породить несвойственные исходному изображению текстуры или одиночные пиксели на крупных масштабах:
  |  | |
| Оригинал с малоразмерной текстурой | Участок при увеличении 220% | |
С другой стороны, некоторые «дефекты» адаптивных интерполяторов тоже могут рассматриваться как преимущества. Поскольку глаз ожидает увидеть в областях с мелкой текстурой, таких как листва, детали вплоть до мельчайших подробностей, подобные рисунки могут обмануть глаз на расстоянии (для определённых видов материала).
Сглаживание
Сглаживание или анти-алиасинг является процессом, который пытается минимизировать появление ступенчатых или зубчатых диагональных границ, которые придают тексту или изображениям грубый цифровой вид:
 |  300% |  |
 | |
Сглаживание удаляет эти ступеньки и создаёт впечатление более мягких границ и высокого разрешения. Оно принимает во внимание, насколько идеальная граница перекрывает смежные пиксели. Ступенчатая граница просто округлена вверх или вниз без промежуточного значения, тогда как сглаженная граница выдаёт значение, пропорциональное тому, насколько много от границы попало в каждый пиксель:
 |  |  | ||
| Идеальная граница в мелком масштабе | Выберите: | ступенчатая | сглаженная | |
Важным соображением при увеличении изображений является предотвращение чрезмерной ступенчатости в результате интерполяции. Многие адаптивные интерполяторы определяют наличие границ и корректируются с целью минимизировать ступенчатость, сохранив при этом резкость границы. Поскольку сглаженная граница содержит информацию о своём положении при более высоком разрешении, вполне возможно, мощный адаптивный (определяющий границы) интерполятор сможет хотя бы частично реконструировать границу при увеличении.
Оптический и цифровой зум
Многие компактные цифровые камеры могут осуществлять как оптическое, так и цифровое увеличение (зум). Оптический зум осуществляется движением вариобъектива, так чтобы свет усиливался до попадания на цифровой сенсор. На контрасте, цифровой зум понижает качество, поскольку осуществляет простую интерполяцию изображения — уже после получения его сенсором.
 | ||
| оптический зум (10x) | цифровой зум (10x) | |
|---|---|---|
 |  | |
Даже несмотря на то, что фото с использованием цифрового зума содержит то же число пикселей, его детальность отчётливо меньше, чем при использовании оптического зума. Цифровой зум следует практически полностью исключить, за вычетом случаев, когда он помогает отобразить удалённый объект на ЖК-экране вашей камеры. С другой стороны, если вы обычно снимаете в JPEG и хотите впоследствии обрезать и увеличить снимок, цифровой зум имеет преимущество в том, что его интерполяция осуществляется до внесения дефектов компрессии. Если вы обнаруживаете, что цифровой зум вам нужен слишком часто, купите телеконвертор, а ещё лучше объектив с большим фокусным расстоянием.
Начну данную статью с того, что расскажу о том, что в природе не найти графика из учебника. Температура не может изменяться чисто по прямой или синусоиде. У неё будет свой график, и соотнести его с какой-либо ранее известной функцией будет достаточно сложно (невозможно).
Например, реальный график уличной температуры будет выглядеть следующим образом:
График уличной температуры возле одного из объектов. График уличной температуры возле одного из объектов.Различные колебания могут быть связаны с порывами ветра, помехами на линии (тут цифровой датчик, потому маловероятно). Но суть в том, что график уличной температуры мы не можем представить в виде одной или нескольких функций уличной температуры. Как его строит техника? По точкам. То есть, с заданным интервалом времени мы снимаем показания с датчика температуры и просто соединяем их отрезками. Получится вот такая картина (тот же график, но масштаб изменен):
Судя по картинке, можно увидеть, что весь график непрерывен и состоит из разных отрезков, сцепленных воедино. Но при этом функция не гладкая и имеет приличный разброс по точкам. Такой разброс может быть обусловлен несколькими факторами: погрешность измерения, помехи на линии связи, порывы ветра. Поэтому мы его (набор точек) можем аппроксимировать и собрать более гладкую кривую .
То есть, через аппроксимацию я смогу построить более стабильную и гладкую функцию.
Синим выделены точки, красным прямая после аппроксимации. Синим выделены точки, красным прямая после аппроксимации.Вот еще пример аппроксимации :
Аппроксима́ция (от лат. proxima — ближайшая) или приближе́ние — научный метод, состоящий в замене одних объектов другими, в каком-то смысле близкими к исходным, но более простыми. Аппроксимация позволяет исследовать числовые характеристики и качественные свойства объекта, сводя задачу к изучению более простых или более удобных объектов (например, таких, характеристики которых легко вычисляются или свойства которых уже известны).
А теперь идем дальше. Самое главное, что все эти графики интересны только человеку. Машина оперирует с ними совсем по другому. А именно, для неё есть массив данных, который мы рассматриваем в виде графиков - это всего лишь функция, построенная по точкам.
Итак, мы зафиксировали набор показаний и храним их в виде таблицы:
Компьютер будет хранить просто массив этих данных. Но нам удобней представлять их в виде графика. Например такого:
В данном случае мы построили достаточно простой график (отрезки по двум точкам). А бывают еще сплайны, кривые разных порядков и так далее. Зачем нам нужен график? А затем, что мы визуально воспринимаем, как изменяется температура, а кроме того, мы можем по нему рассчитать любые промежуточные значения - интерполировать значения.
Запишем эти уравнения прямых в таблице:
То есть, если нам нужно найти значение между точками по времени 2 и 3, например 2,5, мы используем уравнение прямой на этом отрезке.
На графике это будет выглядеть так:
Интерполя́ция , интерполи́рование ( от лат. inter–polis — « разглаженный, подновлённый, обновлённый; преобразованный ») — в вычислительной математике нахождение неизвестных промежуточных значений некоторой функции по имеющемуся дискретному набору её известных значений.
Как видим, ничего сложного тут нет.
Ну а мы переходим к экстраполяции . Всё отличие её в том, что искомая точка лежит за пределами нашей таблицы. Например, до начала замеров или после их завершения.
Вся сложность будет в выборе формулы, по которой мы будем искать значение точки. Для этого существует масса математических способов. Но это уже другая тема для статьи.
Экстраполя́ция , экстраполи́рование (от лат. extrā — вне, снаружи, за, кроме и лат. polio — выправляю, изменяю[1]) — — приближённое определение значений функции f ( x ) в точках x , лежащих вне отрезка [ x 0 , x n ] по её значениям в точках x 0 > x1
Итак, с помощью аппроксимации мы находим функцию приближенным методом. С помощью интерполяции или экстраполяции находим значение нужных точек внутри таблицы или за её пределами.
Для каждого из методов существует несколько вариантов для решения задачи.
Читайте также: