ProgRoman 9 Жалоба Опубликовано February 9, 2012 Всем привет, вот разбираюсь с алгоритмом Shape context ниже ссылки на него Shape context Wiki Matching with Shape Contexts Shape context как я понял действует он следующим образом 1. сперва надо получить контуры изображений, затем из изображения(контура) берутся N точек pi где i = 1 до N 2. для каждой точки строится n-1 вектор 3. для каждой точки pi получить соответствующую гистограмму hi мне единственно пока не очень понятно как строится эта гистограмма 1 Поделиться сообщением Ссылка на сообщение Поделиться на других сайтах
mrgloom 242 Жалоба Опубликовано February 9, 2012 надой пройтись по каждой точке в контуре и построить у каждой точки круг с секторами(на самом деле не знаю как они там такой ровный круг в дискретном пространстве строят и какого радиуса её необходимо строить(исходя из размера контура или каких то его других параметров), но скорее всего можно заменить просто на квадратную сетку или на линии идущие из центра по кругу с опред. градусом). насчет как это сделать-всё просто составляется вектор, каждый элемент вектора это область, в него записывается число- кол-во точек которые попали в область. т.е. для каждой точки вы например проверяете по расстоянию(радиусу)попала ли она в какую то область и по попаданию в сектор (например у нас 8 секторов линии идут под 45 град.) попадание точки в сектор можно получить, посчитав в какой из 4-х секторов она попадает, а потом в какой под-сектор. либо определить с какой стороны отрезка она находится можно через векторные произведения вроде. Поделиться сообщением Ссылка на сообщение Поделиться на других сайтах
ProgRoman 9 Жалоба Опубликовано February 10, 2012 т.е. я правильно понимаю пусть у нас есть два изображения, даже лучше контуры с уже выделенными точками одно это Pi а второе это Qj i и j изменяются по количеству точек т.е. от 1 до N для построения Shape context надо для каждой точки первого изображения строить эти окружности и считать количество попавших в сектора точек первого же изображения т.е. это потом разворачивается в матрицу число строк это log( r ) а число столбцов Q условно(обозначения из википедии)) и каждый элемент этой матрицы это и есть количество точек попавших в тот или иной сектор. т.е правильно ли при построении диаграммы для одного изображения второе при этом не используется так в самой формуле стоит так q-pi или (q )тут просто начальная точка и таким образом получается вектор... Поделиться сообщением Ссылка на сообщение Поделиться на других сайтах
mrgloom 242 Жалоба Опубликовано February 13, 2012 для каждой точки контура N секторов. число строк это log( r ) а число столбцов Q это я чо то не понял, видимо они просто показывают график в логарифмическом масштабе. а вот как быть если хочется сравнить 2 контура у которого разное кол-во точек?(видимо надо каким то образом упрощать контур у которого больше точек) потому как там для каждой точки ищут лучшую пару. хотя наверно можно найти лишь лучшие пары, а остальное отбросить. http://www.cs.washington.edu/homes/lachesis/images/classes/vision_final/report.html а матчинг пар потом идет через двудольный граф. тут еще есть Hungarian Method for perfect pairing http://code.google.com/p/shape-matching/ хотя может легче взять из другого места. Поделиться сообщением Ссылка на сообщение Поделиться на других сайтах
ProgRoman 9 Жалоба Опубликовано February 13, 2012 h(i) что мы строим для каждой точки контура и называется как я понял shape context и мы в конце имеем N(пусть 100) этих дескрипторов, которые описывают контур формы дальше если по алгоритму я понял строится весовая матрица и уже находится полное паросочетание с наименьшей стоимостью.. а можно ли как-то использовать эти дескрипторы для сравнения двух форм с помощью к примеру обычных метрик грубо говоря без переупорядочивания элементов гистограмм h(i) Поделиться сообщением Ссылка на сообщение Поделиться на других сайтах
mrgloom 242 Жалоба Опубликовано February 14, 2012 с двудольным графом я пока не разбирался(но вроде он позволяет решить задачу быстрее), но если есть два контура размером n и m точек, у каждой точки посчитаны дескрипторы, то можно наверно и полным перебором сравнивать каждую точку из n с m точками и находить минимум по какой нибудь метрике, т.е. мы берем меньшее кол-во точек и ищем им пары во втором наборе по критерию минимум метрики, а как критерий похожи ли у нас 2 фигуры мы берем сумму метрик деленных на кол-во точек. Поделиться сообщением Ссылка на сообщение Поделиться на других сайтах
mrgloom 242 Жалоба Опубликовано February 14, 2012 хотя если так делать, то не учитывается порядок точек в контуре. Поделиться сообщением Ссылка на сообщение Поделиться на других сайтах
quosego 5 Жалоба Опубликовано February 19, 2012 хотя если так делать, то не учитывается порядок точек в контуре. Я думаю порядок в данном случае не важен, вернее важен, но данная проблема решиться сама собой, когда мы минимизируем оценку совмещения двух контуров. Поделиться сообщением Ссылка на сообщение Поделиться на других сайтах
ProgRoman 9 Жалоба Опубликовано February 20, 2012 минимизируем оценку совмещения двух контуров. Это полный перебор по всем точкам для выяснения какой дескриптор первой формы лежит ближе ко второй.. вроде бы это n2 n(количество точек на 1-ой и второй форме)без учёта (подсчёта близости самих дескрипторов этих гистограмм) затем по этим совмещённым точкам подсчитывается (энергия) стоимость чем меньше она тем лучше т.е. образы формы очень близки вроде как то так можно... Поделиться сообщением Ссылка на сообщение Поделиться на других сайтах
mrgloom 242 Жалоба Опубликовано February 22, 2012 The shape context can be created easily, For matching operation a bipartite based graph matching algorithm can be used. It can be done using Hungarian algorithm with complexity is less than the brute force method( O(n^2) ). But after implementing Hungarian algorithm i am not able to find enough match point pairs between shapes. The problem with Hungarian method is that it can't give you the answer in fixed amount of time. It tries to optimize, sometimes never ending optimizations. A nice lecture about Hungarian Algorithm can be found at Поделиться сообщением Ссылка на сообщение Поделиться на других сайтах
mrgloom 242 Жалоба Опубликовано April 3, 2012 http://en.wikipedia.org/wiki/Midpoint_circle_algorithm полезно если область брать круглой Поделиться сообщением Ссылка на сообщение Поделиться на других сайтах
mrgloom 242 Жалоба Опубликовано June 29, 2012 написал просчитывание shape context дескриптора. для матчинга или классификации пока не проверял, но вроде работает, не уверен только с размером секторов по радиусу ,в оригинальном алгоритме похоже по радиусу они сдвигаются не линейно. + возможно кто то скажет, где что можно оптимизировать. кол-во секторов = сложность просчёта можно менять. // shape_context.cpp : Defines the entry point for the console application. #include "stdafx.h" #include "opencv2/highgui/highgui.hpp" #include "opencv2/imgproc/imgproc_c.h" #include "opencv2/core/core_c.h" #include "opencv2/imgproc/imgproc.hpp" #include <math.h> const double pi = atan(1.0f)*4; using namespace cv; int radius_step=2; //pix // по радиусу расстояние может и не линейное, тогда как считается? int n_radius_sectors=5; //определяем кол-во секторов по углу int n_angle_sectors=8; void get_contours(Mat src, vector<vector<Point>>& contours) { Mat dst; threshold(src,dst,100,255,THRESH_OTSU); findContours(dst,contours,CV_RETR_EXTERNAL,CV_CHAIN_APPROX_NONE); } int in_radius_sector(Point& pt1, Point& pt2) { //вычисляем расстояние от точки до точки int r= sqrt((double)(pt1.x-pt2.x)*(pt1.x-pt2.x)+(pt1.y-pt2.y)*(pt1.y-pt2.y));// может корень не надо? //смотрим в какой интервал попало if(r>radius_step*n_radius_sectors) //за пределами { return -1; } else { int r_sector= r/radius_step; return r_sector; } } int in_angle_sector(Point& pt1, Point& pt2) { double angle= atan((double)(pt2.y-pt1.y)/(pt2.x-pt1.x))*(180/pi); while(angle<0) angle+=360; return angle/(360/n_angle_sectors); } //возвращает значение в каком секторе находится точка, -1 значит что вне int get_sector(Point& pt1, Point& pt2) { //pt1 -от которого считается //pt2- тестируемая точка //секторы нумеруются от 0 до макс по радиусу, потом переходим в новый сектор //int res= angle_sector*n_radius_sectors+radius_sector; int radius_sector= in_radius_sector(pt1,pt2); if(radius_sector==-1) return -1; else { int angle_sector= in_angle_sector(pt1,pt2); return angle_sector*n_radius_sectors+radius_sector; } } int _tmain(int argc, _TCHAR* argv[]) { //получаем контур как вектор Mat src=imread("test.png",0); vector<vector<Point>> contours; //вообще то должны получить все точки, а не только внешний контур //можно канни и вытащить все точки или получить иерархию контуров, а потом всё слить в 1. get_contours(src, contours);//получаем только 1 внешний контур //теперь для каждой точки контура вычисляем его дескриптор //у каждой точки получается вектор n_radius_sectors*n_angle_sectors vector<vector<int>> feature_vector; for(int i=0;i<contours.size();++i) for(int j=0;j<contours[i].size();++j) { //берём точку Point pt1= contours[i][j]; //копирование убрать? vector<int> point_descriptor(n_radius_sectors*n_angle_sectors+1); //далее вычисляем дескрипторы для каждой точки for(int k=0;k<contours[i].size();++k) { if(k!=j)//дешевле просто не проверять=получим просто еще 1 точку в центре { Point pt2= contours[i][k]; //копирование убрать? int sector= get_sector(pt1, pt2); //должно быть в пределах [0,n_radius_sector*n_angle_sectors] if(sector!=-1) point_descriptor[sector]++; } } feature_vector.push_back(point_descriptor); } return 0; } 1 Поделиться сообщением Ссылка на сообщение Поделиться на других сайтах
mrgloom 242 Жалоба Опубликовано August 24, 2012 читаю этот документ http://www.cs.berkeley.edu/~malik/papers/BMP-shape.pdf похоже я всё такие неправильно вычисляю по r сектора(там все таки не линейно), хотя может и так будет работать. для того чтобы матчить контуры состоящие из разного кол-ва точек там предлагают ввести фиктивные точки. еще возник вопрос насчёт нахождения аффинного преобразования по точкам. ну как высчитывается сдвиг понятно, а вот как вычисляется матрица А непонятно. Поделиться сообщением Ссылка на сообщение Поделиться на других сайтах
Smorodov 579 Жалоба Опубликовано August 24, 2012 По поводу A с крышкой, это метод наименьших квадратов в чистом виде. Псевдоинверсия это SVD-шная инверсия, а остальное думаю понятно. Поделиться сообщением Ссылка на сообщение Поделиться на других сайтах
mrgloom 242 Жалоба Опубликовано August 24, 2012 как раз непонятно что за матрицы с гомогенными координатами P,Q. Поделиться сообщением Ссылка на сообщение Поделиться на других сайтах
mrgloom 242 Жалоба Опубликовано August 24, 2012 тут больше про реализацию http://www4.ncsu.edu/~wes/ShapeContextSlides.pdf еще расказанно как считать нормаль к точке контура и тут еще http://www.cs.utexas.edu/~grauman/courses/spring2008/slides/ShapeContexts425.pdf а еще есть такое, чем то похоже на PCA http://en.wikipedia.org/wiki/Geometric_hashing Поделиться сообщением Ссылка на сообщение Поделиться на других сайтах
Smorodov 579 Жалоба Опубликовано August 24, 2012 гомогенные координаты это обычные координаты только добавлена 1 и все. Вот например p=(25,34) в гомогенных будет p=(25,34,1). P и Q - это, видимо два набора точек, между которыми ищется преобразование. Поделиться сообщением Ссылка на сообщение Поделиться на других сайтах
mrgloom 242 Жалоба Опубликовано August 24, 2012 только там почему то добавлено спереди. два столбца наверно обозначают координаты x,y. n- кол-во точек. и какую мы матрицу А потом получим тоже не очень понятно, опять же с единицами добавленными наверно. Поделиться сообщением Ссылка на сообщение Поделиться на других сайтах
mrgloom 242 Жалоба Опубликовано August 24, 2012 тем более что допустим для аффинных преобразований получается линейная система, а для перспективных нелинейная. http://mathematica.stackexchange.com/questions/9244/solve-system-of-equations-related-to-perspective-projection но например в ImageJ можно найти пары точек с помощью SIFT, а потом там есть опять же LeastSquares, но там можно выбрать перспективное искажение. причем я попробовал сделать перспективное искажение в гимпе и записал матрицу , а потом загрузил нормальное и искаженное изображение в имаджи и она выдала уже совсем другую матрицу, возможно проблема в том, что в гимпе 9 элемент всегда =1, а в имаджи нет, т.е. возможно матрица не пронормирована или не сдвинута(не знаю как это правильно называется) http://fiji.sc/wiki/index.php?title=Landmark_Correspondences&oldid=6773 Поделиться сообщением Ссылка на сообщение Поделиться на других сайтах
Smorodov 579 Жалоба Опубликовано August 24, 2012 Я думаю какую бы матрицу мы не получили, для преобразования по ней, нужно будет точки приводить к виду (1,x,y). а результат (x/z,y/z) , где z- это число, стоящее там, где была единица. В Opncv, кстати есть функция для перевода в однородные (гомогенные) координаты и обратно. Поделиться сообщением Ссылка на сообщение Поделиться на других сайтах
mrgloom 242 Жалоба Опубликовано August 27, 2012 да я забыл, что в опенцв уже есть функции, которые восстанавливают матрицу по точкам, единственное, что там вроде нельзя делать переопределенную систему, т.е. не допускается шум, хотя надо проверить. Поделиться сообщением Ссылка на сообщение Поделиться на других сайтах
mrgloom 242 Жалоба Опубликовано August 27, 2012 // Определяем преобразование по множеству точек совмещения: // если точек < 3 или точки коллинеарны, то false, иначе афинное; bool CAffineParams::Define (const CRefPoint* pRp, size_t nCnt) { if (nCnt < 3) return false; m_bInvOk = false; ASSERT (AfxIsValidAddress (pRp, sizeof(*pRp)*nCnt)); // обозначаем: (x,y)<=>Src, (u,v)<=>Dst // вычисление средних значений double Sx=0,Sy=0,Sv=0,Su=0; for (size_t i=0; i < nCnt; ++i) { Sx += pRp.m_ptSrc.x; Sy += pRp.m_ptSrc.y; Su += pRp.m_ptDst.x; Sv += pRp.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.m_ptSrc.x-Sx, dy = pRp.m_ptSrc.y-Sy, du = pRp.m_ptDst.x-Su, dv = pRp.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; } // вычисляем знаменатель 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]; RecalcDistTrns (m_D); return true; } еще вот такой код говорят работает для аффинных искажений. по коду походу там вычисляется сначала мат.ожидание, потом дисперсия,потом походу определитель матрицы ковариации. откуда следуют конечные формулы я не смог понять. Поделиться сообщением Ссылка на сообщение Поделиться на других сайтах
mrgloom 242 Жалоба Опубликовано August 28, 2012 попробовал алгоритм, даже не сделав инвариантности к повороту и скейлу не так плохо находит и так. и не делав общую опимизацию через hungarian algorithm, а просто находя наилучшее соответствие. Поделиться сообщением Ссылка на сообщение Поделиться на других сайтах
mrgloom 242 Жалоба Опубликовано September 3, 2012 пытаюсь добить вычисления дескриптора http://www4.ncsu.edu/~wes/ShapeContextSlides.pdf инвариантность к скейлу слайд 6, я так и не понял что там Median of pairwise point distances is used as scale factor http://www.cs.utexas.edu/~grauman/courses/spring2007/395T/slides/JONGTAEKLEE.pdf тут более понятно инвариантность к скейлу формулируется только для контура? как Median of pairwise point distances, а как формулировать для поинт клауда? Поделиться сообщением Ссылка на сообщение Поделиться на других сайтах
mrgloom 242 Жалоба Опубликовано October 12, 2012 http://www.umiacs.umd.edu/~zhengyf/PointMatching.htm еще варианты попробовал кстати матлабовский код и он оказался непригодным для практической работы, слишком много ест памяти и в итоге падает на больших задачах. но возможно там проблема именно в hungarian алгоритме. Поделиться сообщением Ссылка на сообщение Поделиться на других сайтах