Локальный хэш или pHash?
Я пытаюсь реализовать общий отпечаток memoizator: у нас есть файл, который можно выразить с помощью интеллектуального отпечатка пальца (например, pHash для изображений или chromaprint для аудио), и если наша требуемая (дорогая) функция уже была вычислена на аналогичный файл, то мы возвращаем тот же результат (избегая дорогостоящих вычислений).
Локальный хэш (LSH) является популярным и эффективным решением для Примерный ближайший сосед проблема в дорогом многомерном пространстве.
pHash хорошая библиотека, которая реализует перцептивное хеширование изображений.
Таким образом, pHash преобразует многомерный ввод (изображение) в одномерный объект (хэш-код), который отличается от LSH (опять же, многомерных объектов в LSH).
Так что мне интересно, как мы могли бы реализовать одномерный LSH для значений хэша pHash? Или в нескольких словах: как мы можем сгруппировать в бинах одинаковые значения pHash? Может ли это быть альтернативой классическому подходу LSH (и если нет, то почему)?
Решение
Вы могли бы использовать n случайные проекции разделить pHash пространство на 2^n ведра, тогда похожие изображения, скорее всего, найдены из того же ведра. Вы можете даже XOR хеш со всеми 64 возможными целыми числами с весом Хэмминга 1, чтобы удобно проверять соседние сегменты и быть уверенным, что вы найдете все приблизительные совпадения.
Это эффективно только в том случае, если вас интересуют изображения с почти одинаковыми хэшами (небольшое расстояние Хэмминга). Если вы хотите терпеть большие расстояния Хэмминга (например, 8), то будет сложно найти все совпадения эффективно и точно. Я получил очень хорошие результаты по сканирование через вся таблица от GPU, даже мой 3-летний ноутбук GT 650M может проверять 700 миллионов хэшей в секунду!
Редактировать 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% точный ответ.
Другие решения
Других решений пока нет …