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

SURF дескрипторы и их сравнение

Recommended Posts

Изучаю surf алгоритм. Написал код, который находит дескрипторы на двух снимках с камеры и сранивает их. В примерах на си используется функция сравнения из библиотеки flann, которой нет на питоне.

Не найдя подходящей функции я написал свою, которая возвращает скалярное произведение двух вектордескрипторов. Экспериментальное значение 0,85 для произведения векторов позволяет показать схожесть дескрипторов.

Есть ли более корректный алгоритм сравнения двух дескрипторов? может есть соответствующая функция в opencv?

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


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

можно поподробней?

и еще не очень понятно вы все таки сравниваете наборы точек или вектора дескрипторов двух пар точек?

и какую задачу пытаетесь изначально решить?

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


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

Задача поиска соответствующих точек на двух изображениях. Нахожу surf дескрипторы на каждом изображении и сравниваю их. Функция сравнивает вектора дескрипторов двух точек.

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


Ссылка на сообщение
Поделиться на других сайтах
Задача поиска соответствующих точек на двух изображениях. Нахожу surf дескрипторы на каждом изображении и сравниваю их. Функция сравнивает вектора дескрипторов двух точек.

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

надо учитывать пространственное положение точек относительно друг друга.

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

а скалярное произведение я так понимаю использовалось в смысле того, что если произведение близко к 0 то вектора ортогональны значит не похожи?

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

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


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

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

скалярное произведение именно так и использовалось. Чем ближе оно к единице(вектора нормированы) тем более схожи дескрипторы.

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

есть ли идеи по улучшению?

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


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

не помню как там в оригинале RANSAC, но на вскидку берем рэндомно m точек(скажем по 4 с каждого множества точек)

2 метода. можно применять сразу 2 или только второй метод.

1. строим между этими 4 точками расстояния, т.е. как бы объединяем все со всеми, и получаем 2 графа чтоли, которые потом можно сравнить.(и таким образом можем получить пары точек между этими группами по 4 точки) хотя тут наверно сложно надо знать примерное преобразование.

graph0.png?w=639&h=238

2. просто сравниваем дескрипторы групп точек.

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

делаем много итераций и в итоге берем лучшую.

парами считаем те точки, которые отстоят на какое то малое расстояние, остальное считаем шумом.

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

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

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


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

все функции сишные из пакета opencv. На питоне написана только моя собственная функция сравнения дескрипторов.

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


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

ну и дергайте сишный flann (как это делать не знаю, но наверно можно посмотреть как реализованы другие функции).

как flann точно работает я не знаю, но помоему там что то тоже связано с рандомными выборками и еще деревьями.

The feature points are detected with SURF detectors and represented in SURF-128 descriptors. The program by default set up 4 Randomized KDTrees and search for 2-nearest-neighbors. The matched key-point is only counted when the second of the nearest-neighbors is doubly farther than the first.

The 'naive' NN search simply do the search linearly of each object key-point (~593) from the image key-points (782). It does however, keep track of the nearest 2 neighbors and made sure the nearest is indeed dominant before being accepted. The 'naive' distance is simply a sum of squared- differences between the SURF descriptor tuples.

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


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

можно сравнить очень просто - по расстоянию Евклида ;)

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


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

можно сравнить очень просто - по расстоянию Евклида ;)

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

метрика должна быть нормированная.

или вы имеете ввиду геометрические расстояния между точками?

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


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

возможно, но и такое сравнение векторов дескрипторов вполне работает ;)

в find_obj.cpp, в варианте без flann так и делают:

double

compareSURFDescriptors( const float* d1, const float* d2, double best, int length )

{

	double total_cost = 0;

	assert( length % 4 == 0 );

	for( int i = 0; i < length; i += 4 )

	{

		double t0 = d1[i] - d2[i];

		double t1 = d1[i+1] - d2[i+1];

		double t2 = d1[i+2] - d2[i+2];

		double t3 = d1[i+3] - d2[i+3];

		total_cost += t0*t0 + t1*t1 + t2*t2 + t3*t3;

		if( total_cost > best )

			break;

	}

	return total_cost;

}

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


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

да там вообще какой то стрём в коде, используется вшитый параметр 0.6.

возможно это работает из-за специфики SURF дескриптора его вектор дескрипторов состоит всего из 4-х значений и они похожи между собой.

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


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

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

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

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

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

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

Войти

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

Войти сейчас


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

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

×