Здравствуйте.
Построение SIFT-дескриптора, действительно, непростая вещь. В оригинальной статье суть данного процесса описана достаточно скудно и оставляет больше вопросов, нежели понимания. Ниже я постараюсь изложить свое видение данного процесса.
Направление ключевой точки вычисляется исходя из направлений градиентов точек окрестности. Вычисления градиентов производится на изображении из пирамиды гауссиан с масштабом, наиболее близким к масштабу особой точки. Таким образом, для каждой точки из окрестности ключевой точки необходимо рассчитать модуль и направление градиента.
Окрестность ключевой точки делится на регионы, как описано в оригинальной статье. Для каждого региона строится гистограмма направлений. Количество таких регионов и количество направлений в гистограмме определяет, насколько точно дескриптор описывает окрестность точки. Наиболее оптимальную конфигурацию можно узнать только экспериментально, однако автор указывает, что для него оптимальной оказалась конфигурация 4x4x8, то есть 16 регионов по 8 направлений в каждом.
Теперь переходим к вопросу о том, как построить гистограмму для определенного региона ключевой точки. Каждая точка региона вносит вклад, равный
, в ту компоненту гистограммы сегмента, которая покрывает промежуток, содержащий направление градиента (где
- значение модуля градиента в точке).
На этом можно было бы и закончить, однако этого не достаточно, поскольку возможны краевые эффекты, при которых резко изменяется дескриптор. Иначе говоря, в окрестности ключевой точки переходы от одного столбика гистограммы к другому и от одной ориентации к другой должны быть плавными. Для этого предлагается использовать трилинейную интерполяцию.
Исходные данные: значения модулей градиента в окрестности ключевой точки,
; значения направлений градиента в окрестности ключевой точки,
. По этим данным мы рассчитываем значение
для очередной точки, которое обозначим за
.
Далее суть происходящего проще описать программно, учитывая, что теория вам известна.
/* Гистограмма направлений ключевой точки - трехмерный массив:
* - координата X региона;
* - координата Y региона;
* - индекс направления.
*
*/
float histogram[][][];
/* Модуль градиента в текущей точке (уже вычислен) */
float pointMagnitudeWeight;
/* Координаты текущего региона */
float xRegion, yRegion;
/* Индекс направления в гистограмме направлений для текущей точки (уже определен) */
int currentDirectionIndex;
/* Координаты текущего/следующего региона по оси X и Y */
int xIndex[] = { (int)xRegion, (int)(xRegion + 1.0) };
int yIndex[] = { (int)yRegion, (int)(yRegion + 1.0) };
/* Вес для модуля градиента, который вносит точка по оси X и Y:
*
* xWeigth[0] - больше, если точка ближе к текущему региону по оси X,
* меньше, если точка ближе к следующему региону по оси X;
*
* xWeigth[1] - меньше, если точка ближе к текущему региону по оси X,
* больше, если точка ближе к следующему региону по оси X;
*
* yWeigth[0], yWeigth[1] - аналогично, но по оси Y.
*
*/
float xWeigth = { 1.0 - (xRegion - xIndex[0]), 1.0 + (xRegion - xIndex[1]) };
float yWeigth = { 1.0 - (yRegion - yIndex[0]), 1.0 + (yRegion - yIndex[1]) };
/* Индекс текущего и следующего направления в гистограмме направлений */
int directionIndex[] = { currentDirectionIndex, nextDirectionIndex };
/* Вес для направления градиента, который вносит точка по отношению
* к текущему и следующему направленияю:
*
* directionWeight[0] - больше, если направление ближе к текущему,
* меньше, если направление ближе к следующему;
*
* directionWeight[1] - меньше, если направление ближе к текущему,
* больше, если направление ближе к следующему.
*
*/
float directionWeight[] = { 1.0 - (currentDirectionIndex - directionIndex[0]),
currentDirectionIndex - directionIndex[0] };
/* Процесс интерполяции: */
for (int iy = 0; iy < 2; ++iy)
{
for (int ix = 0; ix < 2; ++ix)
{
for (int id = 0; id < 2; ++id)
{
/* Корректировка столбца диаграммы */
float correction = xWeight[ix] * yWeight[iy] * directionWeight[id] * pointMagnitudeWeight;
histogram[ xIndex[ix] ][ yIndex[iy] ][ directionIndex[id] ] += correction;
}
}
}
Массивы xWeight, yWeight, directionWeight содержат те самые точки, необходимые для интерполяции - их как раз 8 (см. последний цикл). Также в оригинальной статье дается указание по поводу странного веса
:
Цитата:
In other words, each entry into a bin is multiplied by a weight of (1-d) for each dimension, where d is the distance of the sample from the central value of the bin as measured in units of the histogram bin spacing.
Если посмотреть на приведенную выше реализацию, то становится ясно, что имелось ввиду. Для каждого измерения (координата X региона, координата Y региона, индекс направления) вычисляется вес (xWeight, yWeight, directionWeight), который определяет долю, которую вносит данная точка в соответствующий столбец гистограммы направлений. Например, вот так мы рассчитали вес для модуля градиента по оси X:
float xWeigth = { 1.0 - (xRegion - xIndex[0]), 1.0 - (xIndex[1] - xRegion) };
Для остальных измерений делали тоже самое.
Надеюсь, я смог донести смысл :)
