Введение
В информатике геометрическое хеширование — это метод эффективного поиска двухмерных объектов, представленных дискретными точками, подвергшихся аффинному преобразованию, хотя существуют расширения и для других представлений объектов и преобразований. На предварительном этапе объекты кодируются путем рассмотрения каждой пары точек как геометрической базы. Оставшиеся точки могут быть представлены инвариантно относительно этой базы, используя два параметра. Для каждой точки её квантованные преобразованные координаты хранятся в хеш-таблице в качестве ключа, а индексы точек базы – в качестве значения. Затем выбирается новая пара точек базы, и процесс повторяется. На этапе распознавания (в режиме онлайн) случайным образом выбираемые пары точек данных рассматриваются как кандидаты в базы. Для каждой базы-кандидата оставшиеся точки данных кодируются относительно базы, и в предварительно построенной таблице находятся возможные соответствия объекту. База-кандидат принимается, если достаточно большое количество точек данных указывает на согласованную объектную базу. Геометрическое хеширование изначально было предложено в компьютерном зрении для распознавания объектов в 2D и 3D, но впоследствии было применено к различным задачам, таким как структурное выравнивание белков.
Геометрическое хеширование в компьютерном зрении
Геометрический хэшинг — это метод, используемый для распознавания объектов. Допустим, мы хотим проверить, присутствует ли изображение модели на входном изображении. Это можно сделать с помощью геометрического хэширования. Метод может быть использован для распознавания одного из нескольких объектов в базе данных, и в этом случае хеш-таблица должна хранить не только информацию о позе, но и индекс модели объекта в базе данных.
Пример
Для простоты в этом примере не будет использовано большое количество точечных объектов и будем считать, что их дескрипторы задаются только их координатами (на практике для индексации могут использоваться локальные дескрипторы, такие как SIFT).
Фаза признания
Найдите интересные ключевые точки на входном изображении. Выберите произвольный базис. Если подходящего произвольного базиса не найдено, то, вероятно, входное изображение не содержит целевой объект. Опишите координаты ключевых точек в новом базисе. Квантуйте полученные координаты, как это делалось ранее. Сравните все преобразованные признаки точек на входном изображении с хэш-таблицей. Если признаки точек идентичны или схожи, увеличьте счетчик для соответствующего базиса (и типа объекта, если он известен). Для каждого базиса, счетчик которого превышает определенный порог, проверьте гипотезу о том, что он соответствует базису изображения, выбранному на этапе 2. Преобразуйте систему координат изображения в систему координат модели (для предполагаемого объекта) и попытайтесь их сопоставить. Если сопоставление успешно, объект найден. В противном случае вернитесь к этапу 2.
Поиск зеркального рисунка
Похоже, что этот метод способен обрабатывать только масштабирование, сдвиг и вращение. Однако входное изображение может содержать объект, преобразованный зеркально. Поэтому геометрический хешинг также должен уметь находить этот объект. Существует два способа обнаружения зеркальных объектов. Для векторного представления сделайте значения слева положительными, а справа – отрицательными. Умножение координаты x на -1 даст тот же результат. Используйте 3 точки в качестве базиса. Это позволяет обнаруживать зеркальные отражения (или объекты). Фактически, использование 3 точек в качестве базиса – это еще один подход к геометрическому хешированию.
Геометрический хэшинг в более высоких измерениях
Как и в примере выше, хеширование применимо к данным более высокой размерности. Для трехмерных точек данных также требуются три точки для построения базиса. Первые две точки определяют ось x, а третья точка определяет ось y (вместе с первой точкой). Ось z перпендикулярна образованным осям, определяясь по правилу правой руки. Обратите внимание, что порядок точек влияет на результирующий базис.