Здраствуйте!

Нужен алгоритм наложения картинки на карту смещений.

Имеется произвольная картинка:


Для нее создается карта смещений. Это сетка с определнным шагом, например 10, где каждый узел сетки задает смещение по двум координатам X и Y. В прямоугольном виде каждый из узлов имеет нулевые смещения по обоим координатам.


Узел можно представить в виде структуры типа Point, где X и Y определяют велечину смещения отностительно положения узла в прямоугольной сетке.

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


После на эту катру накладывается картинка и исходя из значений смещений узлов девормируется.


Вот так у меня представляется работа с узлами:




Ну и вопрос... Как теперь можно наложить картинку на такую карту деформаций чтобы она таким же образом исказилась? Можно даже с какой-нить простейшим сглаживанием...

Заранее спасибо всем!

можно попробовать локальные аффинные преобразования (не думаю, что термин общепринятый - придумал только что  )

1. делим картинку на треугольники (можно просто взять вышеописанную прямоугольную сетку и каждую ячейку разделить на два треугольника)
2. искажаем каждый треугольник (т.е. его вершины как-то двигаем)
3. накладываем картинку, исходя из предположения, что внутри треугольника искажения были аффинные

детали:
аффинное преобразование - умножение на матрицу и сдвиг: y=Ax+b
оно задаётся 6-ю коэффициентами (4 для матрицы и 2 для вектора сдвига)
их мы подбираем так, чтобы точки исходного треугольника переходили в точки сдвинутого
т.к. у треугольника 3 точки, то получаем 6 линейных уравнений, которые, по идее, должны решаться и выдавать единственный набор коэффициентов для преобразования (хотя тут ещё нужно будет поисследовать, когда система будет вырождена, на всякий случай)
именно поэтому нужно делить на треугольники - для прямоугольника целиком в общем случае подходящего аффиного преобразования может и не быть

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

Спасибо большое! Это очень интерестный вариант. Но мне кажется, что такое наложение картинки может занять долгое время.
Есть вриант простого преобразования: u,v -> x,y. Т.е. проходим по каждому пикселю деформированного прямоугольничка и вычисляем цвет пикселя (x,y) в соответствии с его же положением без смещений (u,v). Смещения всех вершин нам известны.

Вот нашел обратное преобразование:

 -> 



Только не могу в него врубиться :( И получить обратное преобразование, т.е. из прямого в деформированное. И оно к сожалению без сглаживания...

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

Вычисляй координаты с плавающей точкой, а дальше используй интерполяцию.

maxim1000 предложил нормальный вариант: афинное преобразование - одно из самых простых (и быстрых). С интерполяцией, конечно, будет дольше.

Термин "локальное афинное преобразование" есть...

Добавлено через 8 минут и 38 секунд
Можно еще использовать билинейное преобразование, поскольку оно определяется 4 точками.
       u = A0 * x + A1 * y + A2 * x * y + A3;
       v = A4 * x + A5 * y + A6 * x * y + A7;
Фактически, оно эквивалентно выполнению афинных преобразований для соответствующих треугольников.
Естественно, все преобразования (для ячеек) нужно посчитать заранее и естественно обратные.
Дальше, поскольку растр обычно обрабатывается по строкам, перед обработкой каждой строки нового растра вычисляем ее разбиение искаженными 4-угольниками (точки разбиения). Все должно работать вполне быстро.

maxim1000
Earnest

Спасибо вам большое  Видимо я поторопился с выводами на счет аффинных преобразований  В действительности все так и делается:
http://michus.narod.ru/articles/img_warp/index.html
http://www.kgraph.narod.ru/lectures/16_4.htm

Это сообщение отредактировал(а) cs137 - 17.1.2008, 08:45

У меня еще пара вопрсов 

1. При использовании разбиения на треугольники на некоторых границах возникают пробелы.



На приведенной картинке видно эти артефакты в областях искажения. С начало я во всех циклах использовал только целые числа. При таком подходе возникали горизонтальные искажения. Не пробелы, а именно искажения, т.е. рисовались не те цвета. Когда же я заменил все циклы на вещественные, то получил разрывы текстур на некоторых границах. В чем может быть загвоздка?
Вообще пишут, что "При реализации алгоритма удобно рассчитывать границы по какому-либо алгоритму растеризации отрезка". Если это может исправить данную ситуацию, то можно пример, пожалуйста 

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

Вот код, который я накатал (заранее извиняюсь ):

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

Добавлено через 4 минуты и 34 секунды
короче, есть два способа:
1. для каждой точки на исходном изображении определить, куда она передвинется, и нарисовать её там
2. для каждой точки результирующего изображения определить, из какой точки исходного она появилась, и нарисовать соответствующий цвет
из-за округления координат до целых эти два метода отличаются
первый приведёт к тому, что все точки исходного изображения будут нарисованы (хотя, возможно, какие-то будут поверх других)
второй - что все точки результирующего будут заполнены
ИМХО, второй логичнее
хотя определение, какому треугольнику принадлежит точка, становится сложнее

Внешний цикл идет по узлам сетки... берется 4 точки (сначала 3 для первого треугольника, потом 3 для второго). При отрисовке треугольников цикл идет по точкам полученного изображения, в котором определяются точки исходного изображения (2-ой способ). Проблему с разрывом изображения вроде бы удалось решить... в циклах по x2 округляю нижнюю и верхнюю границу, причем нижнюю до меньшего значения, а верхнюю до большего... Теперь только иногда некоторые пиксели проваливаются, т.е. точечный разрыв, но думаю, что это-то сглаживанием можно устранить... не поможете с вариантами на эту тему? Заранее огромное спасибо!!!

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

Конечно это совсем не быстро, но без швов.

Sardar, большое спасибо за такое решение...
Ориентируясь на Ваш пример, я сделал так:



и все разрывы исчезли  Хватило и этого  Еще раз спасибо!


Теперь вопрос по поводу сглаживания... Хотелось бы узнать какой фильтр можно уту применить по сочетанию скорость/качество (если можно с примером)...
У меня при достаточно больших деформациях сетки получаются вот так:



Заранее спасибо!

Это сообщение отредактировал(а) cs137 - 20.1.2008, 13:39

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

У меня конечное обратное преобразование имеет вид:
,
где x1,y1 - точки исходного изображения, а x2,y2 - точки получаемого.

здесь мы имеем 8 коэффициентов вместо 6 для каждого узла сетки.



т.е. я так понимаю, что мы каждое значение элемента вектора вычисляем из соответствующих значений соседних векторов?

да

maxim1000, спасибо Вам большое за помощь. Буду пробовать