warping/morphing algorithm proof of concept
Варпинг - это искажение изображения. Представим себе, что картинка напечатана на резиновой плёнке. Теперь мы берём эту плёнку за какую-то точку и тянем в сторону (оставаясь на той же плоскости). Можно взять несколько точек, тянуть их в разные стороны, и например увеличить грудь или уменьшить талию на фотографии, только нужно понимать, что исказится всё вокруг точки, так что фон за нашей неидеальной моделью должен допускать такие изменения. Это преобразование, которое мы называем warp.
Морфинг - это нечто более сложное. Представим себе две фотографии: морда кошки и морда собаки. Наша цель может быть разной - сделать анимацию, как кошка плавно превращается в собаку, или просто найти что-то среднее. Просто наложить одну картинку с половинной прозрачностью на другую мы не хотим: ведь форма морды у них разная, и нос относительно ушей находится в разном месте. Чтобы это различие скомпенсировать, можно предварительно фотографию исказить с помощью warp. Для этого мы находим на картинках эквивалентные области, например, нос, уши, глаза и т. д., и расставляем на картинках точки - какая точка фотографии кошки соответствует какой точке на фотографии собаки. Для промежуточного кадра мы находим положения точек (промежуточные, с помощью например линейной интерполяции) и варпим каждое изображение в это среднее положение. Затем мы находим взвешенное среднее. Эту процедуру мы называем morphing, и получается, что она состоит из двух warp и смешения.
Идею можно развить: мы можем двигать точки не по прямой; мы можем двигать их неравномерно; мы можем использовать более двух изображений (стадии морфинга) и так далее.
Итак, назовём входное изображение , выходное -
. На вход мы получаем входное изображение, набор координат точек как они были на исходном изображении
, и в какое положение должны стать эти точки в окончательном изображении
.
Пусть x и y - координаты точки в изображении , которую мы хотим получить, а её оригинал, который переходит в точку посредством варпа, на исходном изображении расположен на x', y'. Сформулируем отображение
, аргументами которого являются координаты конечной точки, а значением - координаты начальной точки, т.е.
. Теперь мы можем для каждой точки конечного изображения, например, для каждого пикселя, вычислить значение так:
.
Разумно потребовать, чтобы . Наша задача теперь - найти все остальные значения f, причём так, чтобы на конечном изображении не было очевидных артефактов - разрывов, изломов. Для этого соседние точки должны сдвинуться вдоль того же направления, но чуть меньше, т.е. желательно, чтобы отображение f было "хорошим" (гладким, без разрывов).
По сути дела, задача является задачей интерполяции: как построить "хорошую" аппроксимацию функции по нескольким заданным точкам
? Буквально в такой же форме задача всплывает, например, в геодезии, где по нескольким измерениям нужно построить полную модель поверхности, при этом входных точек "достаточно много": порядка 1000-10000.
Встречал я и программы, в которых разбиение приходилось строить вручную. Это уж совсем грубо.
Разных разбиений можно придумать много, и нужно как-то выбрать из них одно, самое "лучшее", Критерием "хорошести" в данном случае принято считать минимальный угол: чем он больше, тем менее "вытянут" треугольник. Например, так: построить случайное разбиение, потом "перевернуть" некоторое ребро, вдруг такой вариант "лучше"? И так до тех пор, пока переворачивания не перестанут "улучшать" разбиение. Имеется особый случай: в зависимости от исходного набора может существовать несколько "равнозначных" разбиений (так будет, если существует как минимум четыре точки, принадлежащих одной окружности).
Результатом будет разбиение, которое называется триангуляцией Делоне. Указанный способ его построения имеет сложность . Существуют более эффективные алгоритмы его построения, имеющие сложность
, одним из которых является построение диаграммы Вороного (указанную сложность имеет аглоритм Форчуна), из которой мы используем информацию о соседстве сайтов. Оказывается, если соседние сайты в диаграмме Вороного соединить, мы получим как раз триангуляцию Делоне. Существуют и другие способы получения триангуляции Делоне, имеющие ту же эффективность.
Также здесь надо решить, по какому набору точек будем строить треугольники: на первоначальном изображении или на окончательном?
Для некоторых применений данный подход к интерполяции хорош. Однако, для варпа он может дать заметные искажения вида "излом", т.е. плавная линия оказывается как бы "сломанной" на границе между треугольниками, хотя триангуляция Делоне является в этом отношении оптимальным вариантом, т.е. из всех разбиений даёт наименьшие изломы. Изломы, как выясняется, являются следствием недостаточной "хорошести" (недиффeрeнцируемости) получаемого отображения f на границах треугольников. Чтобы избежать изломов, нужно использовать другой подход, не связанный с разбиением на треугольники.
Диаграму Вороного можно использовать и другим способом. Построим её для набора точек . Мы получили набор ячеек, каждой из которых соответствует ячейка. Добавим теперь в набор точку x, y, значение отображения в которой мы хотим получить, и построим новую диаграмму. Она будет отличаться от первоначальной только вблизи новой точки: вокруг неё образуется новая ячейка, площадь которой достанется за счёт площадей соседних ячеек. Составим список ячеек, чью площадь мы позаимствовали, и для каждого из них найдём площадь пересечения новой добавленной ячейки и старой, а затем выясним, какую долю своей площади новая ячейка позаимствовала у каждой из существовавших. Для этих долей выполняется соотношение нормировки:
. Отображение вычислим следующим образом:
.
Такой подход к интерполяции даёт "хорошую" функцию, которая не имеет изломов, т.е. всюду бесконечно дифференцируема, кроме исходных точек.
В зависимости от задачи, может требоваться обрабатывать границы изображения особым образом. Например, хотелось бы добавить их в наборы и
как точки, сдвиг которых равен нулю. Это фактически сделает набор бесконечным.
Диаграмму Вороного можно определить не только для набора точек, но и любых других геометрических фигур. Добавим к набору точек такой объект, как рамку изображения. Тогда ячейки, не соседние с этим новым сайтом, не изменятся - будут по-прежнему с многоугольными границами, а граница ячеек, соседних с сайтом-"рамкой", будет включать одну или несколько параболических дуг.
Вместо этого можно учесть, что рассчёт всё равно будет происходить в дискретном пространстве, и добавить точки на границе с шагом в один пиксель, т.е. фактически задать как не сдвигаемые все пиксели на границе изображения. В сущности, параболические дуги заменятся на аппроксимации отрезками прямых.
В этих случаях принципиально метод похищения площади не меняется.
В алгоритме требуется вычислять диаграмму Вороного в двух случаях: для заданного набора точек, а также для каждого пикселя выходного изображения. Алгорим Форчуна имеет сложность , имеет смысл его применять для первоначального построения диаграммы. Далее, в процессе интерполяции методом похищения площади имеет смысл не строить всю диаграмму заново, а опираться на уже сущетвующую, используя один из алгоритмов инкрементного построения со сложностью
.
Имея функцию, которая для каждой точки готова построить значение отображения, можно выполнять варп. Однако, значительная часть точек будут отображены из точек
с дробными координатами. Для вычисления их значений потребуется использовать какой-то метод фильтрации - билинейный, бикубический, Ланцоша и т. п.
Также на этом этапе требуется учитывать при интерполяции передаточные функции исходного и финального изображения. Ещё это потребуется при смешении результатов варпа в процессе морфинга. Технически может быть проще всего при загрузке исходных изображений сразу выполнить их преобразование согласно передаточным функциям (например, sRGB), выполнить все рассчёты в линейном пространстве в вещественных одинарной или даже половинной точности, а на выходе выполнить обратное преобразование.