Проективное преобразование - PullRequest
12 голосов
/ 04 октября 2008

Учитывая два буфера изображения (предположим, что это массив значений ширины * высоты, где каждый элемент имеет значение цвета), как я могу отобразить область, определенную четырехугольником, из одного буфера изображения в другое (всегда квадратное) изображение буфер? Я понял, что это называется «проективным преобразованием».

Я также ищу общий (не зависящий от языка или библиотеки) способ сделать это так, чтобы его можно было разумно применять на любом языке, не полагаясь на «магическую функцию X, которая выполняет всю работу за меня» .

Пример: я написал короткую программу на Java с использованием библиотеки Processing (processing.org), которая захватывает видео с камеры. На начальном этапе «калибровки» захваченное видео выводится прямо в окно. Затем пользователь нажимает на четыре точки, чтобы определить область видео, которая будет преобразована, а затем отображена в квадратное окно во время последующей работы программы. Если бы пользователь щелкнул четыре точки, определяющие углы двери, видимые под углом на выходе камеры, то это преобразование заставило бы последующее видео отобразить преобразованное изображение двери на всю область окна, хотя несколько искажен.

Ответы [ 6 ]

8 голосов
/ 31 марта 2010

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

То, что вы хотите, - это отображение ваших старых (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  ]

Вам нужно знать сквозную 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 (горизонтальный, вертикальный). Вы непременно сделаете что-то не так в первый раз.
5 голосов
/ 04 октября 2008

EDIT

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

  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.

alt text

Вычислить длины 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))
    
  • Отношение тэта P1 к тэтаD должно быть отношением тэта Q1 к 90. Поэтому рассчитайте тэта Q1:

    thetaQ1 = thetaP1 * 90 / thetaD
    
  • Аналогично, рассчитаем thetaQ2:

    thetaQ2 = thetaP2 * 90 / thetaC
    
  • Найти расстояние HQ:

    HQ = m * sin(thetaQ2) / sin(180-thetaQ1-thetaQ2)
    
  • Наконец, x и y позиция Q относительно нижнего левого угла EFGH:

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

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

4 голосов
/ 04 октября 2008

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

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

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

2 голосов
/ 04 октября 2008

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

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

2 голосов
/ 04 октября 2008

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

0 голосов
/ 04 октября 2008

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

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

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

...