Перейти к содержимому
Compvision.ru
ProgRoman

shape context algorithm

Recommended Posts

Всем привет, вот разбираюсь с алгоритмом Shape context ниже ссылки на него

Shape context Wiki

Matching with Shape Contexts

Shape context

как я понял действует он следующим образом

1. сперва надо получить контуры изображений, затем из изображения(контура) берутся N точек pi где i = 1 до N

2. для каждой точки строится n-1 вектор

3. для каждой точки pi получить соответствующую гистограмму hi

мне единственно пока не очень понятно как строится эта гистограмма

  • Like 1

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

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

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

т.е. для каждой точки вы например проверяете по расстоянию(радиусу)попала ли она в какую то область и по попаданию в сектор (например у нас 8 секторов линии идут под 45 град.) попадание точки в сектор можно получить, посчитав в какой из 4-х секторов она попадает, а потом в какой под-сектор. либо определить с какой стороны отрезка она находится можно через векторные произведения вроде.

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

т.е. я правильно понимаю пусть у нас есть два изображения, даже лучше контуры с уже выделенными точками одно это Pi а второе это Qj i и j изменяются по количеству точек т.е. от 1 до N для построения Shape context надо для каждой точки первого изображения строить эти окружности и считать количество попавших в сектора точек первого же изображения т.е. это потом разворачивается в матрицу число строк это log( r ) а число столбцов Q условно(обозначения из википедии)) и каждый элемент этой матрицы это и есть количество точек попавших в тот или иной сектор. т.е правильно ли при построении диаграммы для одного изображения второе при этом не используется так

в самой формуле стоит так q-pi или (q )тут просто начальная точка и таким образом получается вектор...

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

для каждой точки контура 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/

хотя может легче взять из другого места.

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

h(i) что мы строим для каждой точки контура и называется как я понял shape context и мы в конце имеем N(пусть 100) этих дескрипторов, которые описывают контур формы дальше если по алгоритму я понял строится весовая матрица и уже находится полное паросочетание с наименьшей стоимостью..

а можно ли как-то использовать эти дескрипторы для сравнения двух форм с помощью к примеру обычных метрик грубо говоря без переупорядочивания элементов гистограмм h(i)

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

с двудольным графом я пока не разбирался(но вроде он позволяет решить задачу быстрее), но если есть два контура размером n и m точек, у каждой точки посчитаны дескрипторы, то можно наверно и полным перебором сравнивать каждую точку из n с m точками и находить минимум по какой нибудь метрике, т.е. мы берем меньшее кол-во точек и ищем им пары во втором наборе по критерию минимум метрики, а как критерий похожи ли у нас 2 фигуры мы берем сумму метрик деленных на кол-во точек.

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

хотя если так делать, то не учитывается порядок точек в контуре.

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах
хотя если так делать, то не учитывается порядок точек в контуре.

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

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

минимизируем оценку совмещения двух контуров.

Это полный перебор по всем точкам для выяснения какой дескриптор первой формы лежит ближе ко второй.. вроде бы это n2 n(количество точек на 1-ой и второй форме)без учёта (подсчёта близости самих дескрипторов этих гистограмм) затем по этим совмещённым точкам подсчитывается (энергия) стоимость чем меньше она тем лучше т.е. образы формы очень близки вроде как то так можно...

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

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

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

написал просчитывание 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;

}

  • Like 1

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

читаю этот документ

http://www.cs.berkeley.edu/~malik/papers/BMP-shape.pdf

похоже я всё такие неправильно вычисляю по r сектора(там все таки не линейно), хотя может и так будет работать.

для того чтобы матчить контуры состоящие из разного кол-ва точек там предлагают ввести фиктивные точки.

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

point_corespondence.png

transform_estimation.png

ну как высчитывается сдвиг понятно, а вот как вычисляется матрица А непонятно.

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

По поводу A с крышкой, это метод наименьших квадратов в чистом виде.

Псевдоинверсия это SVD-шная инверсия, а остальное думаю понятно.

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

как раз непонятно что за матрицы с гомогенными координатами P,Q.

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

тут больше про реализацию

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

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

гомогенные координаты это обычные координаты только добавлена 1 и все. Вот например p=(25,34) в гомогенных будет p=(25,34,1).

P и Q - это, видимо два набора точек, между которыми ищется преобразование.

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

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

два столбца наверно обозначают координаты x,y. n- кол-во точек.

и какую мы матрицу А потом получим тоже не очень понятно, опять же с единицами добавленными наверно.

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

тем более что допустим для аффинных преобразований получается линейная система, а для перспективных нелинейная.

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

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

Я думаю какую бы матрицу мы не получили, для преобразования по ней, нужно будет точки приводить к виду (1,x,y).

а результат (x/z,y/z) , где z- это число, стоящее там, где была единица.

В Opncv, кстати есть функция для перевода в однородные (гомогенные) координаты и обратно.

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

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

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах
// Определяем преобразование по множеству точек совмещения:

// если точек < 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;

}

еще вот такой код говорят работает для аффинных искажений.

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

откуда следуют конечные формулы я не смог понять.

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

попробовал алгоритм, даже не сделав инвариантности к повороту и скейлу не так плохо находит и так.

и не делав общую опимизацию через hungarian algorithm, а просто находя наилучшее соответствие.

dumb_comparision.png

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

пытаюсь добить вычисления дескриптора

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, а как формулировать для поинт клауда?

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

http://www.umiacs.umd.edu/~zhengyf/PointMatching.htm

еще варианты

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

но возможно там проблема именно в hungarian алгоритме.

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

Создайте учётную запись или войдите для комментирования

Вы должны быть пользователем, чтобы оставить комментарий

Создать учётную запись

Зарегистрируйтесь для создания учётной записи. Это просто!

Зарегистрировать учётную запись

Войти

Уже зарегистрированы? Войдите здесь.

Войти сейчас


  • Сейчас на странице   0 пользователей

    Нет пользователей, просматривающих эту страницу

×