valbok
хотелось бы обсудить некоторые пункты в алгоритме...
1. Получаем ключевые точки и дескрипторы ORB, выбираем количество требуемых точек на изображении.
Как определиться с количеством требуемых точек?
2. Полученные дескрипторы по 32 байта представляем в виде битовой матрицы 16x16.
Мой код используя ORB выдает неизменно 500 ключевых точек, но после получения их дескрипторов и перевода их в phash получается порядка 200 совпадающих хэшей и я подумываю из них оставлять только один из них.
3. Конвертируем матрицу в 64битное число с помощью PHash.
Нужен ли нам phash для такого преобразования? Подумалось, что имея на руках битовую матрицу 16x16 мы можем разделить матрицу на блоки 2x2, после чего преобразовать его в 1 или 0 по сравнению со средним значением.
4. Сохраняем 64битные отпечатки в MySQL.
Как лучше хранить отпечатки в базе? В виде строк или BIGINT?
5. Выбираем требуемое расстояние Хэмминга и запускаем демон HEngine, который будет выполнять поиск.
Если имеется 50000 картинок, то использование оперативной памяти для хранения массивов хэшей становится слегка проблематично (в условиях в её ограниченного количества), т.е. прийдется использовать таблицы mysql для хранения сигнатур. Опять же интересно обсудить их формат, индексы и т.п.
Здравствуйте.
- Как определиться с количеством требуемых точек?
После некоторых тестов, выяснил, что больше совпадений у изображений, если количество точек пропорционально размеру. Например ( img.width + img.height ) / 2
Это позволило находить совпадения с большим и небольшим размером.
- Мой код используя ORB выдает неизменно 500 ключевых точек, но после получения их дескрипторов и перевода их в phash получается порядка 200 совпадающих хэшей и я подумываю из них оставлять только один из них.
Ну так базовая идея в том, что чем больше совпадений, тем ближе к оригиналу.
- Нужен ли нам phash для такого преобразования? Подумалось, что имея на руках битовую матрицу 16x16 мы можем разделить матрицу на блоки 2x2, после чего преобразовать его в 1 или 0 по сравнению со средним значением.
Первая идея была в том, что phash можно не использовать, но, к сожалению, выяснилось, что усреднения, сравнения и пр выдают худшие результаты. А смысл перцептивных хешей именно в том, чтобы при небольших изменениях оригинальных данных результирующий хеш так же менялся ненамного. Усреднения, например с этим тоже справляются, но дают слишком много неактуальных совпадений.
- Как лучше хранить отпечатки в базе? В виде строк или BIGINT?
Не вижу преимуществ перед BIGINT. Т.к. это число и надо будет работать с битовыми операциями.
- Если имеется 50000 картинок, то использование оперативной памяти для хранения массивов хэшей становится слегка проблематично (в условиях в её ограниченного количества), т.е. прийдется использовать таблицы mysql для хранения сигнатур. Опять же интересно обсудить их формат, индексы и т.п.
Если сильно грубо, то на 50к картинок с 500 хешами на одну и используется 4 таблицы хешей 50к * 500 * 4 * 8 байт = 800Мб оперативки. Что не совсем плохо.
Изначально хотелось использовать MySQL, но его бинарные операции и линейная сложность не позволили работать даже с 1к картинками. Перенести таблицы сигнатур в базу, а не оперативную память, думаю возможно, но с существенными жертвами производительности.
Если коротко, получится несколько таблиц, или одная большая таблица со значением и номером сигнатуры. На клиенте потребуется разбить запрошенный инт на подстроки, потом сгенерировать все возможные комбинации в переделах 1 дистанции Хэмминга. И сделать один большой запрос. Потом линейно пройтись и выкинуть хеши, которые за пределами необходимой дистанции.
Насколько хуже такое будет работать, не знаю. Но было бы интересно проверить.
Во-первых, хочу поблагодарить за предыдущие ответы.
Во-вторых, я после небольшой паузы вернулся к экспериментам и хотел бы продолжить разговор ;-)
Я реализовал получение хэша из дескриптора путём усреднения. Предварительно могу сказать, что это работает, но качественно оценить результаты пока не могу... жду помощи от своих скажем так зказчиков, а пока они молчат интересуюсь вопросом k-means кластеризации
Вот в коде (в частности core/hash/extractor.py) она используется. Мне не совсем понятно, что именно нам дает эта кластеризация? Как я думал - несколько близко находящихся дескрипторов можно сгруппировать и получить одну область, которая описывается одним дескриптором. Или вот такая мысль крутится в голове - нам нужно не приводить дескрипторы к phash (потому как происходит потеря данных за счёт преобразования 32 байт в 8, да и сам дескриптор - это всё таки не картинка), а получив область дескриптора - именно координаты и размеры - мы вырезаем область в картинку, для которой собственно и вычисляем phash...
Если нетрудно, можно ещё раз для таких как я рассказать что и зачем?
Здравствуйте, прошу прощения за долгие паузы.
Я реализовал получение хэша из дескриптора путём усреднения. Предварительно могу сказать, что это работает, но качественно оценить результаты пока не могу
ORB дескрипторы хешируются не perceptual hash, а обычным усреднением?
После многочисленных тестов, мне показалось, что именно phash дает наименьшее количество ложных срабатываний, хотя медленнее. После того, как хеши полученны, появится задача как настроить или придумать систему проверки, чтобы исключить явно неадекватные результаты.
Вот в коде (в частности core/hash/extractor.py) она используется. Мне не совсем понятно, что именно нам дает эта кластеризация?
Про это подробно написано тут http://habrahabr.ru/post/205398/. И, к сожалению, после тестов выяснелось, что подобный подход достаточно ущербен, т.к. использует закрытый и медленный SURF, и теряет сильно в точности/очень много false positive.
Коротко кластеризация используется потому-что:
- Получаем ключевые точки с помощью SURF, которые не должны меняться при изменении картинки.
- Кластеризируем ключевые точки. Всмысле находим группы ключевых точек. Я делал это для разного количества кластеров. Главная идея в том, что центройнды кластеров могут совпадать, главное подобрать параметры так, чтобы при изменения картинки, найденные кластера примерно совпадали. Количество требуемых кластеров задается заранее. Работает так:
- нахожу один кластер
- делаю кроп картинки по крайним точкам кластера
- потом делаю phash/dhash/ahash этого куска
- далее нахожу уже два кластера на картинке
- и тд.
- В итоге имею на одной картинке куча вырезанных кусков и их хешей. Хеши в базу. И можно уже искать по ним.
Как я думал - несколько близко находящихся дескрипторов можно сгруппировать и получить одну область, которая описывается одним дескриптором.
Тут стоило бы пояснить, что дескриптор это закодированные ключевые точки. Созданные для того, чтобы можно было сопоставлять/сравнивать их между собой.
Дескрипторы, их формат, как сопоставлять и тд, зависят от используемых алгоритмов.
И они описывают точки, а не группы точек.
нам нужно не приводить дескрипторы к phash (потому как происходит потеря данных за счёт преобразования 32 байт в 8, да и сам дескриптор - это всё таки не картинка), а получив область дескриптора - именно координаты и размеры - мы вырезаем область в картинку, для которой собственно и вычисляем phash...
Это как бы первое что пришло вообще в голову, и примерно это было реализовано в Extractor.subImages()
Но огорчило по скорости, удобности и по точности.
(потому как происходит потеря данных за счёт преобразования 32 байт в 8, да и сам дескриптор - это всё таки не картинка)
Для перцептуального хеширования абсолютно не важна семантика данных, всмысле это все равно двухмерная матрица байт.
Я сознательно ужимал в 8 байт, для того чтобы одна точка описывалась одним 8 байтным числом. Но по сути ORB алгоритм описывает одну точку 32 байтами, и ничего не мешает в базе хранить не одно число для точки, а 4. И сравнивать уже 4 числа, это потребует усложнения системы сравнения, в 4 раза больше памяти и тд. Тогда никакого падения точности не будет.
Если делать вот так, то в принципе ничто не нужно, кроме openCV, питона/с++, и ORB реализации.
Что касается как подобное решается в гуглах/яндексах. То, насколько я понял, обычно в продакшн мире кластеризация дубликатов (или поиск по кропу) решается архитектурно и серьезными вычислительными ресурсами.
Если есть еще вопросы, всегда готов помочь.