Pull to refresh

Comments 26

Накидали бы ссылок на статьи которые неоднократно на эту тему на Хабре были. Вот одна сходу — habrahabr.ru/post/120562/
Ещё была одна или две.
А то вроде как боретесь с репостами… ;)
Как-то странно «прецептивный» в начале текста перетекло в «перцептивный» :-)
Мне вот интересно, какой хэш будет находить картинки с измененным кадрированием (как в плюс, так и в минус).
Классические примеры:
— демотиватор и картинка из него
— картинка, которую подрезали снизу, чтобы убрать копирайт сайта
— групповое фото, обрезанное сбоку, чтобы убрать одного человека
— фрагмент карты/схема и она же целиком
Ну и так далее.
Хеш вполне справляется с картинками, которые подрезали снизу. Я описывал в статье такие случаи.
Что касается более глобальных изменений, вроде демотиватора или фрагмента изображения, то ответ скорее нет чем да. Перцептивный хеш не позволяет сделать выводы о фрагментах данных. Т.е. мы не можем ответить на вопрос где именно данные различаются? Мы получаем ответ на вопрос насколько они похожи.
Для таких случаев больше подходит SURF.
Любой алгоритм который считает интегральный хеш на все изображение, хеши по регулярной сетке(пирамиду коэффициентов по регулярной сетке) не найдут такие изображения.
А еще в этих хешах нет инварианта к изменению освещения, баланса белого и т.п.
Спасибо за статью, узнал кое-что новое. Кому интересно вот моя реализация (полу)игрушечного дублятора изображений на основе pHash (но без гистограмм): github.com/thekvs/imgdupl
Как думаете, можно ли построить такой хэш для текста?
UFO landed and left these words here
Можно, такие решения существуют. Сходу приходит в голову Simhash или Cognitive Hash.
Круто. Я нашёл упоминание cognitive hash всего в одной научной работе, китайского авторства.
Есть еще классический алгоритм rolling хеша. Хотя меня всегда больше волновала задача, как обеспечить быстрый лукап по нечетким хешам, потому как считать расстояние Хемминга крайне затратно. Вариант с сортировкой был бы неплох, но там есть свои проблемы, особенно когда база хешей быстро меняется.
Какой процент коллизий на 64-битном хэше Вы получили?
И на каком объеме базы?
Строите ли Вы гистограммы в реальном времени или считаете заранее и храните?
Объем базы был 6 тысяч популярных картинок собранных на просторах интернета. Процент коллизий составляет примерно 10%.
Гистограммы считаем заранее и храним. В реальном времени рассчитывается только расстояние Хэмминга и взаимная корреляция гистограмм.
Для такой базы процент коллизий очень высокий.
С ростом базы, он, естественно, будет повышаться. Для многих реальных баз в миллионы и сотни миллионов объектов такой хэш не слишком подойдет.
Как Вы считаете?
Сказать трудно, я начинал разработку с базой в 3к картинок, коллизий тоже было около 10%. В общем случае, пространство картинок счетно и бесконечно, а 64 битный хэш конечен. Исходя из этого, с ростом базы количество коллизий будет расти. Но ведь в реальном мире мы имеем дело с изображениями людей, машин, котиков, а это накладывает определенные ограничения на пространство картинок. Ведь мы не будем смотреть на случайный набор пикселей. Так что говорить о зависимости кол-ва коллизий от кол-ва картинок я не берусь.
В целом, если такая проблема имеет место быть, выходов из этих ситуаций можно рассмотреть много, увеличение хэша, использование дополнительных алгоритмов, для уточнения результата (SURF например).
Пространство любого хэша намного меньше определяемого его длиной.
А количество коллизий, вообще говоря, подчиняется обычной теории вероятностей. Кроме, конечно, случаев, связанных с особенностями работы хэша.
Ведь получается, что, если процент коллизий постоянен при удвоении базы (как у Вас), то тогда коллизии между старыми и новыми картинками отсутствуют напрочь.
Такой эффект может иметь место только если хэш на новых картинках работает совершенно иначе, чем на старых. Например, были кошки, стали машины, и хэш это «понимает» и дает разные значения.
А в каком формате удобнее хранить гистограмму, для последующей работы с ней?
Стандартно: как набор относительных частот.
Можно, конечно, и абсолютные частоты использовать, но это только в случае, если суммарная частота одна.
Статья хороша — есть над чем поразмышлять :)
+1
А есть ли пример реализации сравнения гистограмм (один DCT дает много коллизий)? В виде какой-нибудь консольной утилиты или перл-модуля (в идеале).
Only those users with full accounts are able to leave comments. Log in, please.