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

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

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

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

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

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

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

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

Точки объекта в системе координат изображения и оси системы координат основы (П2,П4)

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

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

Вектор ( $x'$ , $y'$ )	основа
$(-0.75,-1.25);$	(П2,П4)
$(1.00,0.00);$	(П2,П4)
$(-0.50,1.25);$	(П2,П4)
$(-1.00,0.00);$	(П2,П4)
$(0.00,0.25)$	(П2,П4)
$(1.00,0.00);$	(П1,П3)
$(0.00,1.25);$	(П1,П3)
$(-1.00,0.00);$	(П1,П3)
$(0.00,-0.25);$	(П1,П3)
$(0.00,0.50)$	(П1,П3)

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

Фаза признания

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

Нахождение зеркального узора [ править ]

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

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

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

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

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

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

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

^ А.С. Миан, М. Беннамун и Р. Оуэнс, Распознавание и сегментация объектов на основе трехмерных моделей в загроможденных сценах ., Транзакции IEEE по анализу шаблонов и машинному интеллекту, том. 28 октября 2006 г., стр. 1584–601.
^ Молл, Марк; Брайант, Дрю Х.; Кавраки, Лидия Э. (11 ноября 2010 г.). «Алгоритм LabelHash для сопоставления подструктур» . БМК Биоинформатика . 11 :555. дои : 10.1186/1471-2105-11-555 . ISSN 1471-2105 . ПМК 2996407 . ПМИД 21070651 .
^ Нусинов Р.; Вольфсон, HJ (1 декабря 1991 г.). «Эффективное обнаружение трехмерных структурных мотивов в биологических макромолекулах методами компьютерного зрения» . Труды Национальной академии наук Соединенных Штатов Америки . 88 (23): 10495–10499. дои : 10.1073/pnas.88.23.10495 . ISSN 0027-8424 . ПМК 52955 . ПМИД 1961713 .

Вольфсон, Х.Дж. и Ригуцос, я (1997). Геометрическое хеширование: обзор. IEEE Вычислительная наука и инженерия, 4(4), 10-21.

[Mian2006-1] А.С. Миан, М. Беннамун и Р. Оуэнс, Распознавание и сегментация объектов на основе трехмерных моделей в загроможденных сценах ., Транзакции IEEE по анализу шаблонов и машинному интеллекту, том. 28 октября 2006 г., стр. 1584–601.

[2] Молл, Марк; Брайант, Дрю Х.; Кавраки, Лидия Э. (11 ноября 2010 г.). «Алгоритм LabelHash для сопоставления подструктур» . БМК Биоинформатика . 11 :555. дои : 10.1186/1471-2105-11-555 . ISSN 1471-2105 . ПМК 2996407 . ПМИД 21070651 .

[3] Нусинов Р.; Вольфсон, HJ (1 декабря 1991 г.). «Эффективное обнаружение трехмерных структурных мотивов в биологических макромолекулах методами компьютерного зрения» . Труды Национальной академии наук Соединенных Штатов Америки . 88 (23): 10495–10499. дои : 10.1073/pnas.88.23.10495 . ISSN 0027-8424 . ПМК 52955 . ПМИД 1961713 .

[1]

[2]

[3]