Геометрическое хеширование

В информатике , геометрическая хеширование представляет собой способ эффективного обнаружения двумерных объектов , представленных дискретных точек , которые претерпели аффинное преобразование , хотя расширений существуют для других представлений объектов и преобразований. В автономном режиме объекты кодируются, рассматривая каждую пару точек как геометрическую основу . Остальные точки можно представить инвариантно относительно этого базиса с помощью двух параметров. Для каждой точки ее квантованные преобразованные координаты хранятся в хэш-таблице.в качестве ключа, а индексы базисных точек - в качестве значения. Затем выбирается новая пара базисных точек, и процесс повторяется. На этапе онлайн (распознавания) случайно выбранные пары точек данных рассматриваются как базы-кандидаты. Для каждой основы-кандидата оставшиеся точки данных кодируются в соответствии с основанием, а возможные соответствия объекта находятся в ранее созданной таблице. Основа-кандидат принимается, если достаточно большое количество точек данных указывает на непротиворечивую основу объекта.

Геометрическая хеширование первоначально была предложено в области компьютерного зрения для распознавания объектов в 2D и 3D, ^[1] , но позже было применен к различным проблемам , таким , как структурное выравнивание из белков . ^{[2] [3]}

Геометрическое хеширование в компьютерном зрении [ править ]

Геометрическое хеширование - это метод, используемый для распознавания объектов. Допустим, мы хотим проверить, можно ли увидеть изображение модели во входном изображении. Этого можно добиться с помощью геометрического хеширования. Метод может использоваться для распознавания одного из нескольких объектов в базе, в этом случае хеш-таблица должна хранить не только информацию о позе, но и индекс объектной модели в базе.

Пример [ править ]

Для простоты в этом примере не будет использоваться слишком много точечных объектов и предполагается, что их дескрипторы задаются только их координатами (на практике для индексации могут использоваться локальные дескрипторы, такие как SIFT ).

Фаза обучения [ править ]

Точки объекта в системе координат изображения и оси для системы координат за основу (P2, P4)

1. Найдите характерные черты модели. Предположим, что на изображении модели обнаружены 5 характерных точек с координатами , см. Рисунок.${\ Displaystyle (12,17);}$${\ Displaystyle (45,13);}$${\ displaystyle (40,46);}$${\ displaystyle (20,35);}$${\ displaystyle (35,25)}$
2. Введите основу для описания местоположения характерных точек. Для двумерного пространства и преобразования подобия базис определяется парой точек. Исходная точка находится в середине отрезка, соединяющего две точки (P2, P4 в нашем примере), ось направлена ​​к одной из них, ортогональна и проходит через начало координат. Масштаб выбран таким образом, чтобы абсолютное значение для обеих базисных точек было равно 1.${\ displaystyle x '}$${\ displaystyle y '}$${\ displaystyle x '}$
3. Опишите расположение объектов относительно этого базиса, т.е. вычислите проекции на новые оси координат. Чтобы сделать распознавание устойчивым к шуму, координаты должны быть дискретизированы , мы берем размер бина 0,25. Таким образом, мы получаем координаты${\displaystyle (-0.75,-1.25);}$${\displaystyle (1.00,0.00);}$${\displaystyle (-0.50,1.25);}$${\displaystyle (-1.00,0.00);}$${\displaystyle (0.00,0.25)}$
4. Сохраните основу в хеш-таблице, проиндексированной по функциям (в данном случае только преобразованные координаты). Если бы было больше объектов для сопоставления, мы также должны сохранить номер объекта вместе с базисной парой.
5. Повторите процесс для другой пары базисов (шаг 2). Это необходимо для обработки окклюзий . В идеале все неколлинеарные пары должны быть пронумерованы. Предоставляем хеш-таблицу после двух итераций, для второй выбирается пара (P1, P3).

Хеш-таблица:

Вектор ( , )${\displaystyle x'}$${\displaystyle y'}$	основа
${\displaystyle (-0.75,-1.25);}$	(P2, P4)
${\displaystyle (1.00,0.00);}$	(P2, P4)
${\displaystyle (-0.50,1.25);}$	(P2, P4)
${\displaystyle (-1.00,0.00);}$	(P2, P4)
${\displaystyle (0.00,0.25)}$	(P2, P4)
${\displaystyle (1.00,0.00);}$	(P1, P3)
${\displaystyle (0.00,1.25);}$	(P1, P3)
${\displaystyle (-1.00,0.00);}$	(P1, P3)
${\displaystyle (0.00,-0.25);}$	(P1, P3)
${\displaystyle (0.00,0.50)}$	(P1, P3)

В большинстве хэш-таблиц не может быть одинаковых ключей, сопоставленных с разными значениями. Таким образом, в реальной жизни нельзя кодировать базовые ключи (1.0, 0.0) и (-1.0, 0.0) в хеш-таблице.

Фаза признания [ править ]

1. Найдите интересные особенности на входном изображении.
2. Выбираем произвольную основу. Если подходящей произвольной основы нет, то вполне вероятно, что входное изображение не содержит целевой объект.
3. Опишите координаты характерных точек в новом базисе. Квантовать полученные координаты, как это делалось ранее.
4. Сравните все преобразованные точечные объекты на входном изображении с хеш-таблицей. Если точечные объекты идентичны или похожи, увеличьте счетчик для соответствующего базиса (и типа объекта, если таковой имеется).
5. Для каждого базиса, в котором счет превышает определенный порог, проверьте гипотезу о том, что он соответствует базису изображения, выбранному на шаге 2. Перенесите систему координат изображения в модельную (для предполагаемого объекта) и попробуйте сопоставить их. В случае успеха объект найден. В противном случае вернитесь к шагу 2.

Поиск зеркального рисунка [ править ]

Кажется, что этот метод способен обрабатывать только масштабирование, перемещение и вращение. Однако входное изображение может содержать объект в зеркальном преобразовании. Следовательно, геометрическое хеширование также должно иметь возможность найти объект. Есть два способа обнаружить зеркальные объекты.

1. Для векторного графика сделайте левую часть положительной, а правую - отрицательной. Умножение позиции x на -1 даст тот же результат.
2. За основу возьмите 3 точки. Это позволяет обнаруживать зеркальные изображения (или объекты). Собственно, использование трех точек за основу - это еще один подход к геометрическому хешированию.

Геометрическое хеширование в более высоких измерениях [ править ]

Как и в примере выше, хеширование применяется к многомерным данным. Для трехмерных точек данных также необходимы три точки в качестве основы. Первые две точки определяют ось x, а третья точка определяет ось y (с первой точкой). Ось z перпендикулярна созданной оси с использованием правила правой руки. Обратите внимание, что порядок точек влияет на итоговую основу.

См. Также [ править ]

• Перцептивное хеширование

Ссылки [ править ]

• Вольфсон, HJ и Rigoutsos, I. (1997). Геометрическое хеширование: обзор. IEEE Computational Science and Engineering, 4 (4), 10-21.