Проективное преобразование

Существует Проект C++ на CodeProject, который включает источник для проективных преобразований растровых изображений. Математика находится в Википедии здесь. Обратите внимание, что, насколько мне известно, проективное преобразование не будет отображать один произвольный четырехугольник на другой, но будет делать это для треугольников, вы также можете найти преобразования с перекосом.

Я думаю, что вам нужна плоская гомография, взгляните на эти лекции:

http://www.cs.utoronto.ca/~strider/vis-notes/tutHomography04.pdf

Если вы прокрутите вниз до конца, вы увидите пример того, что вы описываете. Я ожидаю, что в библиотеке Intel OpenCV есть функция, которая сделает именно это.

Вот как бы это сделать в принципе:

• сопоставьте происхождение A с началом B с помощью вектора трансляции t.
• возьмите единичные векторы A (1,0) и (0,1) и вычислите, как они будут отображаться на единичные векторы B.
• это дает вам матрицу преобразования M, так что каждый вектор a в A отображается на Ma + t
• инвертируйте матрицу и инвертируйте вектор трансляции, чтобы для каждого вектора b в B у вас было обратное отображение b -> M^-1 (b - t)
• как только у вас есть это преобразование, для каждой точки целевой области в B найдите соответствующую точку в A и скопируйте.

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

РЕДАКТИРОВАТЬ

Приведенное ниже предположение об инвариантности угловых соотношений неверно. Вместо этого проективные преобразования сохраняют перекрестные отношения и инцидентность. Тогда решение:

1. Найдите точку C 'на пересечении прямых, определенных отрезками AD и CP.
2. Найдите точку B 'на пересечении прямых, определенных отрезками AD и BP.
3. Определите перекрестное соотношение B'DAC ', то есть r = (BA' * DC ') / (DA * B'C').
4. Постройте проектируемую линию F'HEG '. Отношение этих точек равно r, то есть r = (F'E * HG ') / (HE * F'G').
5. F'F и G'G будут пересекаться в проецируемой точке Q, поэтому, приравняв перекрестные отношения и зная длину стороны квадрата, вы можете определить положение Q с помощью некоторой арифметической гимнастики.

Хмммм .... Я возьму на себя этот удар. Это решение основывается на предположении, что соотношение углов сохраняется при преобразовании. См. Изображение для руководства (извините за низкое качество изображения ... ДЕЙСТВИТЕЛЬНО поздно). Алгоритм обеспечивает отображение только точки четырехугольника в точку квадрата. Вам все равно придется реализовать работу с несколькими точками четырехугольника, сопоставленными с одной и той же квадратной точкой.

Пусть ABCD будет четырехугольником, где A - верхняя левая вершина, B - верхняя правая вершина, C - нижняя правая вершина, а D - нижняя левая вершина. Пара (xA, yA) представляет координаты x и y вершины A. Мы отображаем точки в этом четырехугольнике на квадрат EFGH, сторона которого имеет длину, равную m.

Вычислите длины AD, CD, AC, BD и BC:

AD = sqrt((xA-xD)^2 + (yA-yD)^2)
CD = sqrt((xC-xD)^2 + (yC-yD)^2)
AC = sqrt((xA-xC)^2 + (yA-yC)^2)
BD = sqrt((xB-xD)^2 + (yB-yD)^2)
BC = sqrt((xB-xC)^2 + (yB-yC)^2)

Пусть thetaD - угол при вершине D, а thetaC - угол при вершине C. Вычислите эти углы, используя закон косинуса:

thetaD = arccos((AD^2 + CD^2 - AC^2) / (2*AD*CD))
thetaC = arccos((BC^2 + CD^2 - BD^2) / (2*BC*CD))

Сопоставляем каждую точку P четырехугольника с точкой Q квадрата. Для каждой точки P четырехугольника выполните следующие действия:

• Найдите расстояние DP:

  DP = sqrt((xP-xD)^2 + (yP-yD)^2)
  

• Найдите расстояние CP:

  CP = sqrt((xP-xC)^2 + (yP-yC)^2)
  

• Найдите угол thetaP1 между CD и DP:

  thetaP1 = arccos((DP^2 + CD^2 - CP^2) / (2*DP*CD))
  

• Найдите угол thetaP2 между CD и CP:

  thetaP2 = arccos((CP^2 + CD^2 - DP^2) / (2*CP*CD))
  

• Отношение thetaP1 к thetaD должно быть отношением thetaQ1 к 90. Следовательно, вычислите thetaQ1:

  thetaQ1 = thetaP1 * 90 / thetaD
  

• Аналогичным образом рассчитайте thetaQ2:

  thetaQ2 = thetaP2 * 90 / thetaC
  

• Найдите расстояние HQ:

  HQ = m * sin(thetaQ2) / sin(180-thetaQ1-thetaQ2)
  

• Наконец, координаты Q по осям x и y относительно нижнего левого угла EFGH:

  x = HQ * cos(thetaQ1)
  y = HQ * sin(thetaQ1)
  

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

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

Так что, если вы не хотите вдаваться в сложное кодирование, использовать чужую магическую функцию, как предложили smacl и Ян.

Использовать линейную алгебру намного проще, чем всю эту геометрию! Кроме того, вам не нужно использовать синус, косинус и т. д., Поэтому вы можете сохранить каждое число как рациональную дробь и получить точный числовой результат, если он вам нужен.

Вам нужно сопоставить ваши старые координаты (x, y) с новыми координатами (x ', y'). Вы можете сделать это с помощью матриц. Вам нужно найти матрицу проекции P размером 2 на 4 так, чтобы P, умноженное на старые координаты, равнялось новым координатам. Предположим, что вы сопоставляете линии с линиями (а не, например, прямые линии с параболами). Поскольку у вас есть проекция (параллельные линии не остаются параллельными) и перенос (скольжение), вам также нужен коэффициент (xy) и (1). В виде матриц:

          [x  ]
[a b c d]*[y  ] = [x']
[e f g h] [x*y]   [y']
          [1  ]

Вам нужно знать от a до h, поэтому решите эти уравнения:

a*x_0 + b*y_0 + c*x_0*y_0 + d = i_0
a*x_1 + b*y_1 + c*x_1*y_1 + d = i_1
a*x_2 + b*y_2 + c*x_2*y_2 + d = i_2
a*x_3 + b*y_3 + c*x_3*y_3 + d = i_3

e*x_0 + f*y_0 + g*x_0*y_0 + h = j_0
e*x_1 + f*y_1 + g*x_1*y_1 + h = j_1
e*x_2 + f*y_2 + g*x_2*y_2 + h = j_2
e*x_3 + f*y_3 + g*x_3*y_3 + h = j_3

Опять же, вы можете использовать линейную алгебру:

[x_0 y_0 x_0*y_0 1]   [a e]   [i_0 j_0]
[x_1 y_1 x_1*y_1 1] * [b f] = [i_1 j_1]
[x_2 y_2 x_2*y_2 1]   [c g]   [i_2 j_2]
[x_3 y_3 x_3*y_3 1]   [d h]   [i_3 j_3]

Вставьте углы для x_n, y_n, i_n, j_n. (Углы работают лучше всего, потому что они находятся далеко друг от друга, чтобы уменьшить ошибку, если вы выбираете точки, скажем, по щелчкам пользователя.) Возьмите обратную матрицу 4x4 и умножьте ее на правую часть уравнения. Транспонирование этой матрицы - P. Вы должны быть в состоянии найти функции для вычисления обратной матрицы и умножения в режиме онлайн.

Где могут быть ошибки:

• При вычислении не забывайте проверять деление на ноль. Это признак того, что ваша матрица необратима. Это может произойти, если вы попытаетесь сопоставить одну координату (x, y) с двумя разными точками.
• Если вы пишете свою собственную математику матриц, помните, что матрицы обычно представляют собой строку, столбец (вертикальный, горизонтальный), а экранная графика - это x, y (горизонтальный, вертикальный). Вы обязательно ошибетесь в первый раз.