Преобразование полученных координат в координаты экрана
Я думаю, что это, вероятно, простой математический вопрос, но я понятия не имею, что происходит сейчас.
Я фиксирую позиции "маркеров" на веб-камере, и у меня есть список маркеров и их координаты. Четыре маркера являются внешними углами рабочей поверхности, а пятый (зеленый) маркер является виджетом. Как это:
http://i37.tinypic.com/308cjtv.jpg
Вот некоторые примеры данных:
- Верхний левый маркер (а =98, б =86)
- Верхний правый маркер (c=119, d=416)
- Нижний левый маркер (e=583, f=80)
- Нижний правый маркер (g=569, h=409)
- Маркер виджета (х =452, у =318)
Я хотел бы каким-то образом преобразовать положение виджета веб-камеры в координату для отображения на экране, где верхний левый угол равен 0,0, а не 98,86, и каким-то образом учитывать искривленные углы от захвата веб-камеры.
С чего бы мне начать? Любая помощь приветствуется
6 ответов
Чтобы вычислить деформацию, вам нужно вычислить гомографию между четырьмя углами входного прямоугольника и экрана.
Так как полигон вашей веб-камеры имеет произвольную форму, для преобразования его в прямоугольник можно использовать полную перспективную гомографию. Это не так сложно, и вы можете решить ее с помощью математической функции (должна быть легко доступна), известной как разложение по сингулярным значениям или SVD.
Исходная информация:
Для таких плоских преобразований вы можете легко описать их с помощью гомографии, которая представляет собой матрицу 3x3 H так что если какая-либо точка на или в полигоне вашей веб-камеры, скажем, x1 были умножены на Hт.е. H*x1мы бы получили точку на экране (прямоугольную), т.е. x2,
Теперь обратите внимание, что эти точки представлены их однородными координатами, которые представляют собой не что иное, как добавление третьей координаты (причина которой выходит за рамки этого поста). Итак, предположим, ваши координаты для X1 мы, (100,100)то однородное представление будет вектором столбца x1 = [100;100;1] (где ; представляет новый ряд).
Итак, теперь у нас есть 8 однородных векторов, представляющих 4 точки на многоугольнике веб-камеры и 4 угла вашего экрана - это все, что нам нужно для вычисления гомографии.
Вычисление гомографии:
Немного математики: я не собираюсь вдаваться в математику, но вкратце вот как мы ее решаем:
Мы знаем, что матрица 3х3 H,
H =
h11 h12 h13
h21 h22 h23
h31 h32 h33
where hij represents the element in H at the ith row and the jth column
может быть использован для получения новых координат экрана x2 = H*x1, Кроме того, результат будет что-то вроде x2 = [12;23;0.1] чтобы получить его в координатах экрана, мы нормализуем его по третьему элементу или X2 = (120,230) который (12/0.1,23/0.1),
Так что это означает, что каждая точка в полигоне вашей веб-камеры (WP) можно умножить на H (и затем нормализовать), чтобы получить ваши координаты экрана (SC), т.е.
SC1 = H*WP1
SC2 = H*WP2
SC3 = H*WP3
SC4 = H*WP4
where SCi refers to the ith point in screen coordinates and
WPi means the same for the webcam polygon
Вычислительная H: (быстрое и безболезненное объяснение)
псевдокод:
for n = 1 to 4
{
// WP_n refers to the 4th point in the webcam polygon
X = WP_n;
// SC_n refers to the nth point in the screen coordinates
// corresponding to the nth point in the webcam polygon
// For example, WP_1 and SC_1 is the top-left point for the webcam
// polygon and the screen coordinates respectively.
x = SC_n(1); y = SC_n(2);
// A is the matrix which we'll solve to get H
// A(i,:) is the ith row of A
// Here we're stacking 2 rows per point correspondence on A
// X(i) is the ith element of the vector X (the webcam polygon coordinates, e.g. (120,230)
A(2*n-1,:) = [0 0 0 -X(1) -X(2) -1 y*X(1) y*X(2) y];
A(2*n,:) = [X(1) X(2) 1 0 0 0 -x*X(1) -x*X(2) -x];
}
Как только у вас есть A, просто вычислите svd(A) что даст разложить его на U, S, VT (так, чтобы A = USVT). Вектор, соответствующий наименьшему единственному значению, равен H (как только вы преобразуете его в матрицу 3х3).
С HВы можете получить "искаженные" координаты местоположения вашего маркера виджета, умножив его на H и нормализуется.
Пример:
В вашем конкретном примере, если мы предположим, что ваш размер экрана составляет 800x600,
WP =
98 119 583 569
86 416 80 409
1 1 1 1
SC =
0 799 0 799
0 0 599 599
1 1 1 1
where each column corresponds to corresponding points.
Тогда мы получим:
H =
-0.0155 -1.2525 109.2306
-0.6854 0.0436 63.4222
0.0000 0.0001 -0.5692
Опять же, я не собираюсь в математику, но если мы нормализуем H от h33разделить каждый элемент на H от -0.5692 в приведенном выше примере
H =
0.0272 2.2004 -191.9061
1.2042 -0.0766 -111.4258
-0.0000 -0.0002 1.0000
Это дает нам много понимания трансформации.
[-191.9061;-111.4258]определяет перевод ваших точек (в пикселях)[0.0272 2.2004;1.2042 -0.0766]определяет аффинное преобразование (которое по сути является масштабированием и вращением).- Последний
1.0000это так, потому что мы масштабировалиHэтим и [-0.0000 -0.0002]обозначает проективное преобразование полигона вашей веб-камеры.
Кроме того, вы можете проверить, если H точно мое умножение SC = H*WP и нормализуем каждый столбец с последним элементом:
SC = H*WP
0.0000 -413.6395 0 -411.8448
-0.0000 0.0000 -332.7016 -308.7547
-0.5580 -0.5177 -0.5554 -0.5155
Разделение каждого столбца по последнему элементу (например, в столбце 2, -413.6395/-0.5177 а также 0/-0.5177):
SC
-0.0000 799.0000 0 799.0000
0.0000 -0.0000 599.0000 599.0000
1.0000 1.0000 1.0000 1.0000
Какой желаемый результат.
Координаты виджета:
Теперь координаты вашего виджета также могут быть преобразованы H*[452;318;1], который (после нормализации (561.4161,440.9433),
Итак, вот как это будет выглядеть после деформации:
Как видите, зеленый + представляет точку виджета после деформации.
Заметки:
- В этой статье есть несколько хороших картинок, объясняющих гомографии.
- Вы можете играть с матрицами преобразования здесь
MATLAB код:
WP =[
98 119 583 569
86 416 80 409
1 1 1 1
];
SC =[
0 799 0 799
0 0 599 599
1 1 1 1
];
A = zeros(8,9);
for i = 1 : 4
X = WP(:,i);
x = SC(1,i); y = SC(2,i);
A(2*i-1,:) = [0 0 0 -X(1) -X(2) -1 y*X(1) y*X(2) y];
A(2*i,:) = [X(1) X(2) 1 0 0 0 -x*X(1) -x*X(2) -x];
end
[U S V] = svd(A);
H = transpose(reshape(V(:,end),[3 3]));
H = H/H(3,3);
0 0 0 -98 -86 -1 0 0 0
98 86 1 0 0 0 0 0 0
0 0 0 -119 -416 -1 0 0 0
119 416 1 0 0 0 -95081 -332384 -799
0 0 0 -583 -80 -1 349217 47920 599
583 80 1 0 0 0 0 0 0
0 0 0 -569 -409 -1 340831 244991 599
569 409 1 0 0 0 -454631 -326791 -799
Из-за эффекта перспективы линейные или даже билинейные преобразования могут быть недостаточно точными. Посмотрите на правильное отображение перспективы и многое другое от Google на эту фразу, может быть, это то, что вам нужно...
Попробуйте следующее: разделите исходный прямоугольник и эту фигуру на 2 диагонали. Их пересечение (к, л). У вас есть 4 искаженных треугольника (ab-cd-kl, cd-ef-kl, ef-gh-kl, gh-ab-kl), и точка xy находится в одном из них.
(4 треугольника лучше, чем 2, так как искажение не зависит от выбранной диагонали)
Вам нужно найти точку треугольника XY. Для этого вам нужно всего 2 проверки:
- Проверьте, находится ли он в ab-cd-ef. Если это правда, продолжайте с ab-cd-ef, (в вашем случае это не так, поэтому мы продолжим с cd-ef-gh).
- Мы не проверяем cd-ef-gh, но уже проверяем половину этого: cd-gh-kl. Дело здесь. (В противном случае это был бы ef-gh-kl)
Вот отличный алгоритм, чтобы проверить, находится ли точка в многоугольнике, используя только его точки.
Теперь вам нужно только сопоставить точку с исходным треугольником cd-gh-kl. Точка xy является линейной комбинацией 3 точек:
x = c * a1 + g * a2 + k * (1 - a1 - a2)
y = d * a1 + h * a2 + l * (1 - a1 - a2)
a1 + a2 <= 1
2 переменные (a1, a2) с 2 уравнениями. Я думаю, вы можете получить формулы решения самостоятельно.
Затем вы просто делаете линейные комбинации a1 и a2 с координатами соответствующих точек в исходном прямоугольнике. В этом случае с W (ширина) и H (высота) это
X = width * a1 + width * a2 + width / 2 * (1 - a1 - a2)
Y = 0 * a1 + height * a2 + height / 2 * (1 - a1 - a2)
"Алгоритм Кабча" делает именно это: он создает матрицу вращения между двумя пробелами, учитывая N согласованных пар позиций.
Подробнее о том, как сделать это в target-c в xcode, связанном с публикацией jacobs, вы можете найти здесь: рассчитать V из A = USVt в target-C с SVD из LAPACK в xcode
Поскольку ваша область ввода не является прямоугольником с тем же соотношением сторон, что и на экране, вам придется применить какое-то преобразование для отображения.
Я бы взял пропорции, где находится внутренняя точка относительно внешних сторон, и сопоставил бы это с теми же пропорциями экрана.
Для этого вычислите количество свободного пространства сверху, снизу, слева и справа от внутренней точки и используйте соотношение, чтобы выяснить, где на экране должна быть точка.
http://img230.imageshack.us/img230/5301/mapkg.png
Как только у вас есть измерения, поместите внутреннюю точку в:
x = left / (left + right)
y = above / (above + below)
Таким образом, независимо от того, насколько искажен кадр веб-камеры, вы все равно можете отобразить полный прямоугольник на экране.