возник вопрос насчёт нахождения аффинного преобразования по точкам.
допустим имеем пары точек.


ну как высчитывается сдвиг понятно, а вот как вычисляется матрица [math]$A$[/math] непонятно.
точнее как составляется матрицы из гомогенных координат.

Вот кусок кода, к-й рассчитывает афинное преобразование по набору точек.
Входные параметры - массив опорных точек (просто пары точек scr-dst)
Вычисляется 6 афинных коэффициентов; там есть комментарий откуда видно куда какой

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

может быть система переопределена и содержать шум?

а для перспективного искажения как будет выглядеть? 

Да это просто МНК. Т.е. минимизация среднеквадратичной ошибки. Составляем сумму квадратов разностей, дифференцируем, приравниваем к нулю и вот оно. 
Что значит - переопределена? Точек больше чем 3, определяющих афинное преобразование? Так в этом и смысл - ошибка "разбрасывается".
Конечно, выбросы влияют сильно и нехорошо - но это вообще беда МНК. 
Перспективное искажение афинным преобразованием не устраняется, естественно. Афинное - это прямоугольник в параллелограмм. А если у нас трапеция, то получится такой усредненный параллелограмм. От точек зависит, конечно.
У тебя на первой картинке (с буквой А) никакое не афинное изображено, конечно (если отрезки - это вектора переноса точек).

не очень понимаю как тут применяется МНК, может напишете как поставлена задача?

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

мы знаем (x,y)->(u,v) и хотим найти матрицу перехода M, т.к. афинные это частный случай перспективных, то можно сразу говорить о перспективных.
получается переопредеденная линейная система, вроде она решается как раз через МНК, только я не знаю как.

еще вопрос-рассуждение.

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

вообщем тут написано, что можно решить переопределенную систему уравнений через вычисление определителей(только причем тут МНК?)
http://helpstat.ru/2012/01/metod-naimenshix-kvadratov/
и опять же у вас в коде в конце какие то странныеформулы.


а вообще кажется понял, попробую переписать для 9 неизвестных.

Это сообщение отредактировал(а) mrgloom - 29.8.2012, 14:03

 Стандартно: задача МНК - это минимизация суммы квадратов ошибок. Параметры (коэффициенты) преобразования являются в данном случае переменными, по которым производится минимизация. Т.е. выражение для ошибки Sum (X - U)^2 дифференцируем по каждому параметру, приравниваем к нулю и получаем 6 линейных уравнений. Метод работает для любых преобразований, линейных по параметрам. Как получились формулы, которые у меня в коде, я уже не помню, дело давно было. Очевидно, там не прямое решение линейной системы из 6 уравнений. Видимо, система за счет преобразований и выражений через моменты была разделена и решена аналитически.

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

mrgloom, 
Для решение переопределенной системы применяют метод МНК. 

http://helpstat.ru/2012/01/metod-naimenshix-kvadratov/
В этой статье МНК описан для не переопределённого случая. 
Для решения системы уравнений используется метод Метод Крамера он основан на нахождение определителя.

Для переопределённой системы он не годится.  Для неё надо делать псевдообращение матрицы. 
Достаточно популярный метод нахождения псевдообращение через SVD.  

Но как по мне он плохо работает. 
Лучше взять алгоритм Earnest'а или что-то близкое.  

Про решение переопределенных систем при помощи МНК можно прочитать в 
Каханер,_Моулер,_Наш.-Численные_методы_и_программное_обеспечение-Мир(1998)


Так как процесс итерационный, то приблизится. Единственное что в конце мы можем попасть в устойчивую точку. А их может быть несколько.  Так что я бы попробовал 4 или 8   начальных положения. Т.е проверил бы варианты предварительно повернув на 45, 90,135,180,225,270,315. 

К примеру возьми контуры карандашей. Они могут оказаться как коллинеарны, так и сонаправлены.

помоему там система тоже переопределена, т.к. для нахождения линии надо 2 точки, а там их больше.


ну попробовал я через псевдообратную матрицу(только тут помоему без SVD)
http://opencv.willowgarage.com/documentati...operations.html
по формуле

и у меня получилось, что все нули, что это означает, что нет решения?
хотя может я сами уравнения не правильно составил?
т.е. я взял просто СЛАУ которая получается от перспективных преобразований, а надо было производные от суммы квадратов приравнять нулю и из этого получить СЛАУ?




про нахождение пар.
есть вариант использовать shape context  и потом там получается assigment problem которая решается через hungarian algorithm.
(но я еще это не пробовал)
собственно говоря, если мы у каждой точки имеем соответствие, то нам и не надо решать систему-определять перспективное преобразование, а можно варпнуть просто используя точки. 

кажется понял.



для affine  m31=m32=0 m33=1

значит S=SUM[ (u(i)-(m11*x(i) + m12*y(i) + m13))^2+(v(i)-(m21*x(i) + m22*y(i) + m23))^2 ]
потом всё это переписываем в СЛАУ относительно 6 переменных.




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

даже при искусственном примере почему то не работает.

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

Это сообщение отредактировал(а) mrgloom - 30.8.2012, 15:55

Если система переопределена, то ты находишь решение с минимальной нормой невязки (в твоём случае L2 норма, соответственно и выбросы будут влиять сильно, если ничего с этим не делать) и оно единственно, если система недоопределена, то ты находишь одно из возможных решений МНК. 




Чем это плохо? Сингулярное разложение самая робастная процедура.



Это сообщение отредактировал(а) W4FhLF - 31.8.2012, 12:10

еще раз про Least squares, я так понял это всего лишь метод решения, т.е. задать целевую функцию и её потом минимизировать.

еще есть варианты когда не так чувствительны к аутлпайнерам
http://research.microsoft.com/en-us/um/peo...tim/node24.html

и тут возможно 2 исхода, у нас получится линейная система 
http://en.wikipedia.org/wiki/Linear_least_...s_(mathematics)
вот там как раз рассматривается решение через псевдообратную матрицу, только почему и зачем мы домножаем, как бы и так решаемое уравнение на транспонированную матрицу?(нашел объяснение тут на стр 4 http://classes.soe.ucsc.edu/cmps290c/Spring04/paps/lls.pdf )
а слайд 14 меня натолкнул на мысль, почему бы не вписать элипсы в наборы точек, а потом зная диагонали концов осей не найти преобразование?
потом еще и через QR и SVD. вроде еще и LU используют?
а в разделе Limitations еще вроде и альтернативы написаны которые лучше к шумам относятся.
 
или у нас получится нелинейная система
http://en.wikipedia.org/wiki/Non-linear_least_squares
пока не осиливал.(как такой случай должен получится в случае перспективных искажений, только непонятно всё таки можно найти единственное решение?)


и всё таки разбирая предоставленный код, я не понимаю откуда такие формулы расчёта.
может быть кто нибудь объяснит?



// вычисление средних значений  //почему вычисляем среднее? вроде должны просто сумму?
   double Sx=0,Sy=0,Sv=0,Su=0;
   for (size_t i=0; i < nCnt; ++i) 
   {
      Sx += pRp[i].m_ptSrc.x; Sy += pRp[i].m_ptSrc.y;
      Su += pRp[i].m_ptDst.x; Sv += pRp[i].m_ptDst.y;
   }
   Sx /= nCnt; Sy /= nCnt; Su /= nCnt; Sv /= nCnt;
    // вычисляем суммы  // тут опять же должны просто суммы а зачем то вычитаем среднее
    double Sxx=0,Syy=0,Sxy=0,
          Sxu=0,Syu=0,Sxv=0,Syv=0;
    for (i=0; i < nCnt; ++i)
   {
        double dx = pRp[i].m_ptSrc.x-Sx, 
             dy = pRp[i].m_ptSrc.y-Sy,
                 du = pRp[i].m_ptDst.x-Su, 
             dv = pRp[i].m_ptDst.y-Sv;
        Sxx += dx*dx;    Syy += dy*dy;  Sxy += dx*dy;
      Syv += dy*dv;    Sxv += dx*dv;    Syu += dy*du;    Sxu += dx*du;
    }
    // вычисляем знаменатель // далее вообще непонятно что делается, отдаленно похоже на вычисление определителей 2х2.
    double Dxy = Syy*Sxx - Sxy*Sxy; 
    if (fabs(Dxy) < EPSILON)
      return false;
    // коэффициенты прямого преобразования: (x,y)->(u,v) (SrcToDst)
   //      u = m_D[0]*x + m_D[1]*y + m_D[2]
   //      v = m_D[3]*x + m_D[4]*y + m_D[5]
   m_D[0] = (Syy*Sxu - Sxy*Syu)/Dxy;
    m_D[1] = (Syu*Sxx - Sxy*Sxu)/Dxy;
    m_D[2] = Su - Sx*m_D[0] - Sy*m_D[1];
    m_D[3] = (Syy*Sxv - Sxy*Syv)/Dxy;
    m_D[4] = (Syv*Sxx - Sxy*Sxv)/Dxy;
    m_D[5] = Sv - Sx*m_D[3] - Sy*m_D[4];

Это сообщение отредактировал(а) mrgloom - 6.9.2012, 17:25

похоже это называется  Horn's method
http://www.mathworks.com/matlabcentral/fil...ms2D_nobsxfun.m
http://home.hiroshima-u.ac.jp/tamaki/study...micp_on_gpu.pdf
слайд 9

только тут определяется поворот, смещение и увеличение.