Отобразить один четырехугольник в другой

Какие чему соответствуют известно?

Если искомое аффинное - то будет 6 переменных, здесь 8 условий, хотя может 2 для проверки правильности соотвествия.

Ну это и есть координаты углов соответствующих. Через x записал так как запятые - десятичный разделитель. Там все сложно, но можно приближенно считать что да - ищем аффинное преобразование - на практике устроит.

Ну это и есть координаты углов соответствующих

Тогда аффинным не получится, вероятно это подойдет:

http://www.imagemagick.org/Usage/distorts/#perspective_projection

(в гимпе perspective tool вроде так работает)

По сути похоже. Если побъекты вывернуть в реальные четырехугльники, потом исходный отразить вокруг вертикальной оси и совместить в какой-то точке, пусть в А. То будет:
269 310
272,57 470,16
296,37 410,62
297,46 327,67

Второй, к которому надо прийти будет:
269 310
72 1785
1061 1544
991 107

И вот теперь надо сделать то что делает гимповская перспектива - растянуть и деформировать первый во второй.

И как бы что-то таке и должно выйти:

i = ( 1.430099*x +0.246650*y +3 )/( 0.006757*x + 0.009448*y +1 )  
   j = ( 0.147296*x +1.434591*y +0 )/( 0.006757*x + 0.009448*y +1 )

Координаты (вектор) любой точки внутри исходного четырехугольника можно представить как сумму координат вершин с какими то весами. Если заменить вершины на вершины целевого четырехугольника то с-но и получим новые координаты точки.

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

Проверка принадлежности к треугольнику через векторные произведения.

И как найти эти коэффициенты?

Уравнения же линейны относительно коэффициентов матрицы, что еще надо? ^_^

В первом приближении:

convert -verbose xc: -distort Perspective '269,310 696.6,301.2 72,1785 660.9,1902.8 991,107 412,477.9 1061,1544 422.9,1307.4' /dev/null

(может можно сдвиг на 0.5 лучше обработать, просто ii = x_src, jj = y_src, довольно близко)

Еще здесь можно глянуть: http://stackoverflow.com/questions/12276098/understanding-perspective-project...

я бы разбил исходный четырехугольник на 4 треугольника (общая вершина в центре), и делал бы эту процедуру внутри треугольника

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

Фишка в том, что попробовав я получил ахинею какую-то. А вот сейчас когда ты сказал про сдвиг и я забил на него... Вобщем это win! Спасибо!!!

Видимо в первом случае была где-то ошибка.

Простейшая задача

ЛiЛ! Ну да ее можно назвать простой, если только афинное преобразование и если известно сопаставление точек. И то простой, но не простейшей.

Я советую решать эту задачи в смысли минимизации среднеквадратичной ошибки \sum (T(x_i) - y_i).^2. То есть надо найти такое преобразованаие T чтобы перевести x_i в y_i. Если у тебя афинные преобразования, то матрица преобразований для однородных координат имеет следущий вид:

|1+a00  a01    tx|
|a10    1+a11  ty|

как видишь, 6 степеней свободы. Вот ее якобиан:

    |1 0 x y 0 0|
J = |0 1 0 0 x y|

Обозначь за p вектор параметров p=(tx, ty, a00, a01, a10, a11). Тогда минимизировать тебе нужно следующую квадратичную невязку: \sum_i ||J(x_i)p - deltaX_i||^2_2

Ну а решение записывается почти как closed form solution, тебе всего лишь нужно решить относительно p СЛАУ с положительноопределенной симметричной матрицей A:

Ap = b
где A = \sum_{i=1}^{Npts} J^T(x_i)J(x_i),
b = \sum_{i=1}^{Npts} J^T(x_i) * deltaX_i

J^T — транспонирование якобиана, deltaX_i = x_i-y_i.

Короче, по сути, это тот же МНК от Гаусса) Советую сначала запрогать все это в матлабе или октаве и протестировать. Кстати, если у тебя преобразования ограничиваются только смещением и вращением(те матрица преобразований ортогональна), то это все сводится просто к SVD разложению http://en.wikipedia.org/wiki/Orthogonal_Procrustes_problem

Как-то я с трудом понимаю, как получить ii и jj. Что вообще такое page.x и page.y? Точности не хватает...

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

Вообще говоря для четырехугольника не существует афинного преобразования, поскольку он может быть не выпуклым (кажется это так называется). Ну вот скажем есть у тебя квадрат. Хватаешь ты его за правый верхний угол и тащишь к левому нижнему, что в пределе даст фигуру типа L. Или меняешь порядок для двух вершин типа: из [] в |><|. А в трехмерном пространстве еще хуже.

Можно ли исходный четырехугольник разбить на два треугольника?

По большому счету это даже не четырехугольники, это я эту хрень «апроксимировал» четырехугольником. Можно разбить на что угодно. Там внутри фигуры несколько зон и мне надо чтобы центры этих зон попали в аналогичные зоны на другой фигуре, пусть даже не в центры, но не мимо. Зоны сами по себе тоже весьма бесформенные :(

Вообще говоря для четырехугольника не существует афинного преобразования, поскольку он может быть не выпуклым (кажется это так называется). Ну вот скажем есть у тебя квадрат. Хватаешь ты его за правый верхний угол и тащишь к левому нижнему

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

Нифига не понял. Какие зоны? Можно картинку или план какой хоть примерно как это выглядит.

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

Не - картинки нет. Надо писать что-то чтобы ее нарисовать. Я рисовал для себя в инкскейпе, но уже непосредственно сами четырехугольники руками - просто чтобы видеть их. Зоны - бог с ними. Если привести сами четырехугольники там все будет нормально - начать сейчас это вытаскивать - будет только хуже. На самом деле они двумерны, но первый на поверхности шара, а второй на поверхности тора - на это тоже плевать. Я их считаю плоскими. Точнее на первый кинул сетку от глобуса (как это называется по умному?), а второй вообще плоским считаю, благо тор разворачивается на плоскость гораздо проще...

А зоны... ну пусть для простоты это будут квадраты координатной сетки - вот. Точнее четырехугольники тоже.

Но как я говорю - это фигня пусть фигуры плоские.

Точнее на первый кинул сетку от глобуса (как это называется по умному?), а второй вообще плоским считаю, благо тор разворачивается на плоскость гораздо проще...

Ну эт как сказать. У тора дырка в середине. См смишные картинки тут: http://habrahabr.ru/post/168133/ далее гугль: топология.

Что вообще такое page.x и page.y?

Не скажу точно, скорее всего связано virtual-canvas (вероятно для padding-а, гибкости наложения изображений и пр.)

Точности не хватает...

Никто не говорил, что convert в данном случае будет точен - он преобразует _пиксели_, чтобы перейти к координатам нужно правильно сплясать.

Формулы для xd / yd есть? Относительно «матричных» коэффициентов восемь уравнений будут линейны? Берешь gsl / whatever и решаешь.

Имплементация не моя, но делают они так же как я описывал, на http://elonen.iki.fi/code/misc-notes/affine-fit/