Населенный пункт Чувствительный хэш или pHash?

Question

Я пытаюсь реализовать общий отпечаток пальца memoizator: у нас есть файл, который может быть выражен через интеллектуальный отпечаток пальца (например, pHash для изображений или chromaprint для аудио), и если наша запрошенная (дорогая) функция уже была рассчитана на аналогичный файл, тогда мы возвращаем тот же результат (избегая дорогостоящих вычислений).

Locality Sensitive Hash (LSH) является популярным и хорошо выполненным решением для проблемы Approximate nearest neighbor в дорогом многомерном пространстве.

pHash - хорошая библиотека, которая реализует перцептуальное хеширование изображений.

Таким образом, pHash преобразует многомерный вход (изображение) в одномерный объект (хэш-код), который отличается от LSH (опять же, многомерными объектами в LSH).

Так что мне интересно, как мы могли бы реализовать мономерный размер LSH для значений хэша pHash? Или в нескольких словах: как мы можем группировать в бункерах аналогичные значения pHash? Может ли это быть альтернативой классическому подходу LSH (а если не почему)?

Answer 1

Вы можете использовать nrandom projections, чтобы разделить пространство pHash на 2^n ведра, то похожие изображения, скорее всего, найдены из того же ведра. Вы можете даже XOR хеш со всеми 64 возможными целыми числами с весом Хэмминга 1, чтобы проверить соседние ведра и убедиться, что вы найдете все приблизительные совпадения.

Это эффективно, только если вас интересуют изображения с почти идентичными хэшами (небольшое расстояние Хэмминга). Если вы хотите терпеть большие расстояния для хамминга (например, 8), становится сложно найти все матчи эффективно и точно. Я получил очень хорошую производительность от scanning through всей таблицы на GPU, даже мой трехлетний ноутбук GT 650M смог проверить 700 миллионов хэшей в секунду!

Edit 1: Вы можете думать 64-битный хэш в качестве одного угла на 64-мерного куба, математике легче, если ваш нормализуют угол координаты -1 и 1 (этот путь его центр находится в начале координат). Вы можете выразить m изображения в виде матрицы M размера m x 64 (одна строка/изображение, один бит хэша/столбец).

Простейший способ разделить это 2^n различных групп является создание n 64-мерных векторов v_0, v_1, ..., v_n (выбрать каждый вектор элемент из нормального распределения N (0,1)), это может быть выражено в виде матрицы V размера 64 x n (один столбец/вектор). Возможно, может быть применение ортогональности, как указано в случайной проекции, но я пропущу ее здесь.

Теперь, вычислив A = (M * V) > 0, вы получите m x n матрицу (одно изображение/строка, одна проекция/столбец). Затем преобразуйте двоичное представление каждой строки в число, вы получите 2^n различные возможности, и подобные хэши, скорее всего, окажутся в одном и том же ведре.

Этот алгоритм работает для любого ортогонального представления данных (например, SURF), а не только двоичных строк. Я уверен, что для бинарных хэшей существуют более простые (и вычислительно более эффективные) алгоритмы, но это один из способов реализации случайных прогнозов.

Я предложил XORring, потому что, если изображения не имеют одинаковых хэшей, то они не гарантируются в том же ковше.Проверяя все возможные небольшие отклонения от исходного хеша, вы можете увидеть, какие другие бункеры возможны для вероятных совпадений.

В некотором роде это похоже на то, как механизм компьютерной игры может разбить 2D-карту на сетку ячеек размером x, а затем, чтобы найти все юниты в радиусе x с точки, вам нужно всего лишь проверить 9 ячеек (один, содержащий точку + 8 окружающих ячеек), чтобы получить 100% точный ответ.