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

Привет, Вы узнаете о том , что такое геометрическое хеширование, Разберем основные их виды и особенности использования. Еще будет много подробных примеров и описаний. Для того чтобы лучше понимать что такое геометрическое хеширование , настоятельно рекомендую прочитать все из категории Криптография и криптоанализ, Стеганография и Стегоанализ.

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

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

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

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

Пример

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

Фаза обучения

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

1. Найдите характерные точки модели. Об этом говорит сайт https://intellect.icu . Предположим, что на изображении модели обнаружено 5 характерных точек с координатами(12,17); (45,13); (40,46); (20,35); (35,25) , см. картинку.
2. Введите основу для описания расположения характерных точек. Для двумерного пространства и преобразования подобия базис определяется парой точек. Исходная точка помещается в середину отрезка, соединяющего две точки (P2, P4 в нашем примере). ось направлена ​​в сторону одного из них, ортогональна и проходит через начало координат. Масштаб выбран таким, чтобы абсолютное значение для обоих базисных пунктов равен 1.
3. Опишите расположение объектов относительно этого базиса, т.е. вычислите проекции на новые оси координат. Координаты должны быть дискретизированы, чтобы распознавание было устойчивым к шуму, мы принимаем размер интервала 0,25. Таким образом, мы получаем координаты(−0,75,−1,25); (1.00,0,00); (−0,50,1,25); (−1.00,0,00); (0,00,0,25)
4. Сохраните основу в хеш-таблице , индексированной по объектам (в данном случае только преобразованным координатам). Если бы было больше объектов для сопоставления, мы также должны были бы сохранить номер объекта вместе с базисной парой.
5. Повторите процесс для другой базисной пары (шаг 2). Это необходимо для обработки окклюзий . В идеале должны быть пронумерованы все неколлинеарные пары . Предоставляем хеш-таблицу после двух итераций, для второй выбирается пара (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 перпендикулярна созданной оси по правилу правой руки. Обратите внимание, что порядок точек влияет на результирующий базис.

Вау!! 😲 Ты еще не читал? Это зря!

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

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