nsa_a1 Sep 18 2014 at 18:41

Как бороться с репостами или пара слов о перцептивных хешах

11 min

30K

Programming*Image processing*

From sandbox

+53

Comments 26

ZlodeiBaal Sep 18 2014 at 19:21

Накидали бы ссылок на статьи которые неоднократно на эту тему на Хабре были. Вот одна сходу — habrahabr.ru/post/120562/
Ещё была одна или две.
А то вроде как боретесь с репостами… ;)

+17

ZlodeiBaal Sep 18 2014 at 19:25

habrahabr.ru/post/205398/
habrahabr.ru/post/211773/
habrahabr.ru/post/143689/
habrahabr.ru/post/122372/

Что-то ещё стопудов было.

+10

Hertz Sep 18 2014 at 20:43

Как-то странно «прецептивный» в начале текста перетекло в «перцептивный» :-)

nsa_a1 Sep 18 2014 at 23:45

Поправил, спасибо :)

dom1n1k Sep 18 2014 at 23:38

Мне вот интересно, какой хэш будет находить картинки с измененным кадрированием (как в плюс, так и в минус).
Классические примеры:
— демотиватор и картинка из него
— картинка, которую подрезали снизу, чтобы убрать копирайт сайта
— групповое фото, обрезанное сбоку, чтобы убрать одного человека
— фрагмент карты/схема и она же целиком
Ну и так далее.

nsa_a1 Sep 19 2014 at 00:04

Хеш вполне справляется с картинками, которые подрезали снизу. Я описывал в статье такие случаи.
Что касается более глобальных изменений, вроде демотиватора или фрагмента изображения, то ответ скорее нет чем да. Перцептивный хеш не позволяет сделать выводы о фрагментах данных. Т.е. мы не можем ответить на вопрос где именно данные различаются? Мы получаем ответ на вопрос насколько они похожи.
Для таких случаев больше подходит SURF.

igor_suhorukov Sep 19 2014 at 13:17

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

thekvs Sep 19 2014 at 08:22

Спасибо за статью, узнал кое-что новое. Кому интересно вот моя реализация (полу)игрушечного дублятора изображений на основе pHash (но без гистограмм): github.com/thekvs/imgdupl

nsa_a1 Sep 19 2014 at 09:47

Вы в свою очередь можете побаловаться моей реализацией: funnycampwebjob.azurewebsites.net/FunnyCampSearch/
Можно попробовать поискать известные мемы вроде img-9gag-lol.9cache.com/photo/aOyv5WN_460s.jpg

father_gorry Sep 19 2014 at 08:35

Как думаете, можно ли построить такой хэш для текста?

UFO just landed and posted this here

nsa_a1 Sep 19 2014 at 09:51

Можно, такие решения существуют. Сходу приходит в голову Simhash или Cognitive Hash.

father_gorry Sep 19 2014 at 12:38

Круто. Я нашёл упоминание cognitive hash всего в одной научной работе, китайского авторства.

cebka Sep 19 2014 at 12:49

Есть еще классический алгоритм rolling хеша. Хотя меня всегда больше волновала задача, как обеспечить быстрый лукап по нечетким хешам, потому как считать расстояние Хемминга крайне затратно. Вариант с сортировкой был бы неплох, но там есть свои проблемы, особенно когда база хешей быстро меняется.

Trept Sep 19 2014 at 11:29

Какой процент коллизий на 64-битном хэше Вы получили?
И на каком объеме базы?
Строите ли Вы гистограммы в реальном времени или считаете заранее и храните?

nsa_a1 Sep 19 2014 at 11:37

Объем базы был 6 тысяч популярных картинок собранных на просторах интернета. Процент коллизий составляет примерно 10%.
Гистограммы считаем заранее и храним. В реальном времени рассчитывается только расстояние Хэмминга и взаимная корреляция гистограмм.

Trept Sep 19 2014 at 11:44

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

nsa_a1 Sep 19 2014 at 12:01

Сказать трудно, я начинал разработку с базой в 3к картинок, коллизий тоже было около 10%. В общем случае, пространство картинок счетно и бесконечно, а 64 битный хэш конечен. Исходя из этого, с ростом базы количество коллизий будет расти. Но ведь в реальном мире мы имеем дело с изображениями людей, машин, котиков, а это накладывает определенные ограничения на пространство картинок. Ведь мы не будем смотреть на случайный набор пикселей. Так что говорить о зависимости кол-ва коллизий от кол-ва картинок я не берусь.
В целом, если такая проблема имеет место быть, выходов из этих ситуаций можно рассмотреть много, увеличение хэша, использование дополнительных алгоритмов, для уточнения результата (SURF например).

Trept Sep 19 2014 at 12:23

Пространство любого хэша намного меньше определяемого его длиной.
А количество коллизий, вообще говоря, подчиняется обычной теории вероятностей. Кроме, конечно, случаев, связанных с особенностями работы хэша.
Ведь получается, что, если процент коллизий постоянен при удвоении базы (как у Вас), то тогда коллизии между старыми и новыми картинками отсутствуют напрочь.
Такой эффект может иметь место только если хэш на новых картинках работает совершенно иначе, чем на старых. Например, были кошки, стали машины, и хэш это «понимает» и дает разные значения.

Trept Sep 19 2014 at 12:39

Попробуйте для оценки близости гистограмм расстояние Дженсен-Шеннона, основанное на дивергенции Кулбак-Лейблера. В своем проекте мы на нем остановились.