Клуб о поиске Яндекса

Выявление дубликатов картинок.

leon1010
30 сентября 2010, 12:35

Процесс и выявления дубликатов картинок, для меня, как для владельца сайта с обоями для рабочего стола (в котором пользователи сами так-же публикуют обои) - очень интересен.


Я написал свой скрипт выявления дубликатов картинок на PHP+MySQL.


Принцип его работы таков:

Он определяет цвет каждого пикселя картинки (из 216 возможных). И высчитывает % присутствия каждого цвета на картинке ( до тысячных долей % ) и сохраняет эту информацию в БД. - этот процесс оказался настолько ресурсоемким, что мне пришлось отказаться от его моментального выполнения во время добавления картинки.


Далее на основе данных в БД составляются графики, которые сравниваются друг с другом с определенной допустимой погрешностью (процесс тоже довольно требователен к ресурсам).

И вот тут возникает дилемма: Если процент погрешности высокий, то  процесс выявляет множество картинок, которые на самом деле не являются дубликатами (они просто схожи по палитре). Если процент погрешности наоборот уменьшить, то скрипт не считает за дубликаты ту-же самую картинку, но в другом разрешении или немного обрезанную или с нанесенным водяным знаком. Поэтому процесс погрешности приходиться увеличивать и из-за этого у некоторых картинок получается выявлено по 50-60 псевдо-дубликатов, с учетом, что во всей базе сайта всего около 6000 картинок - это очень много.


По этому, я хочу спросить:

Ваш алгоритм позволяет с высокой точностью выявить дубликаты картинок, либо вы испытываете те-же самые сложности и просто отрубаете найденные псевдо-дубликаты при поиске?

Можно ли как-то позаимствовать, хотя-бы частично, ваш алгоритм выявления дублей? И если можно, то где я могу найти о нем информацию?

 

Буду благодарен за любые подсказки и советы,

Спасибо.
 

С уважением,

Леонид. 
3 комментария
Подписаться на комментарии к посту
Посмотрите вот эти доклады: http://romip.ru/romip2008/index.html там есть долее интеллектуальные и менее ресурсоёмкие методики
Здравствуйте, Леонид.
Мы сравниваем картинки совсем по-другому.
На первом этапе мы анализируем изображения, выявляя особые точки. Для этого мы используем метод DoG (Difference of Gaussian). После первого этапа мы получаем набор кандидатов в дубликаты,  отобранный по сходству взаиморасположения этих ключевых точек. При этом не важно, в каком месте изображения находятся эти точки у каждого из кандидатов.
Далее среди отобранных кандидатов  в дубликаты производится сравнение областей, содержащих эти точки.
Сравнение происходит попиксельно. Но, разумеется, перед сравнением интересующие нас области изображения проходят предварительную обработку: мы приводим их к одному размеру, нормируем по яркости и т.д.
Кстати, цвет имеет очень маленькое значение для нашего алгоритма поиска дубликатов: мы без проблем определяем как дубликаты одинаковые изображения, в разной цветовой гамме.

Воспроизвести наши алгоритмы довольно тяжело, да и, наверное, для вашей задачи не нужно, т.к. они ориентированы на работу с огромными массивами данных.
Наиболее рациональным, с нашей точки зрения, было бы применение одного из готовых решений. Несмотря на то, что их производительность, скорее всего, будет уступать нашей, её будет вполне достаточно для решения ваших задач.

Большое спасибо за ответ.


Я понял, что сложные алгоритмы (в том числе, как у яндекса) мне на PHP не воспроизвести, а какой-то сторонний софт подключить к серверу - нет возможности.


Остается искать решения, которые можно воспроизвести на PHP и что-бы работали в несколько этапов - от менее ресурсоемких к более точным.