Поиск дубликатов изображений публикуемых Вконтакте

Хочу поделиться с вами способом нахождения дубликатов изображений, который я использовал в своем проекте. Речь пойдет об агрегаторе популярных изображений из социальной сети Вконтакте. Основной источник постов — это топовые публичные страницы (паблики).

В первую же очередь после добавления для агрегации нескольких пабликов, я столкнулся с проблемой дублей картинок. Каждая из топовых страниц, что-то, да сопрет у ближнего своего. От чего же ленивые, по идее 9gag ^[1] на всех должно хватит :).

В агрегаторе посты сортируются в зависимости от лайков и(или) количества репостов, в результате чего на верхушке встречались дубликаты из-за того что они пользуются примерно одинаковой популярностью в разных пабликах. Но кто-то же является первоисточником? Благо, Вконтакте API предоставляет возможность узнать, кто опубликовал пост раньше, остается только определить какие из постов одинаковые. Дальше речь пойдет о том, как же мне удалось истребить 80% дубликатов, так что бы из ~1700 публикуемых постов, убрать ~500-600 дублей.

Так как все изображения выкачиваю к себе на сервер, первое, что пришло в голову, занести в бд параметры, а именно высоту, ширину и вес изображения. На большой выборке я заметил одну замечательную особенность — ширина и высота, а именно из 130 000 на данный момент имеющихся изображений в базе, существует всего ~500 вариаций ширины и высоты изображений. Заметив эту особенность, возникла идея группирования изображений по этим параметрам.

Нахождение дубликатов с одинаковой шириной и высотой

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

SELECT * FROM ...
WHERE width={$width} AND height={$height} AND weight LIKE '".$weight."%' AND date > {$date} 
ORDER by date DESC

В результате каждого из запросов по группам я получаю выборку из 1-4 изображений. Далее дело за малым, используя класс сравнения изображений, взятый с этого поста ^[2], я сравниваю изображения между собой попарно. Если значение схожести выше 40% значит это дубликат. Порог в 40% был выбран не случайно, а в результате тестов, на множестве групп дубликатов, так же этот порог вместе с двумя первыми цифрами размера помогает избежать вотермарки на изображениях. Далее, проверяется у какого изображения дата публикации раньше тот и оригинал, остальные привязываю к оригиналу как дубликаты

Нахождение дубликатов с одинаковой шириной и разной высотой и наоборот

Принцип нахождения дубликатов тот же, только все происходит на меньшей выборке, чем во время первого этапа. Группы формируются также, только берется первая цифра высоты, в итоге получается группа, состоящая из ширины, первая цифра высоты, первая цифра размера. Данный этап нахождения дубликатов более русурсоемкий, потому как группы состоят из 10-20 изображений, и поэтому запускается реже.

Заключение

Ввиду экономии ресурсов, поиск дубликатов осуществляется в выборке за текущие сутки. Результат работы этого алгоритма можно посмотреть, собственно на агрегаторе Likez.ru ^[3]

Автор: WuWu