Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > PHP: Графика > Сравнить изображения, найти дубликаты

Автор: Elfer 7.10.2016, 15:27

Привет. Мне нужен алгоритм, код тут необязательно. Код будет второй задачей для меня и возможно сам с ним справлюсь. Здесь пока что нужна только логика, по каким шагам делать.

Задача следующая:
На сайте имеются тысячи картинок (демотиваторы, карикатуры, комиксы, фотографии с фотика) загружаемые со всего интернета. Нужно найти дубликаты. Задача усложняется тем, что размеры картинок могут быть разные, а также качество сохранения картинок, расширения (например, gif и jpg). Также картинка может быть сбоку чуть обрезана, либо со всех краёв по немногу. Учитывать то, что изображения могут быть перевёрнуты - не нужно (такого не будет).

Какой я вижу алгоритм:

для каждой картинки делаем считывание цветов и кол-ва пикселей построчно;
сверху вниз, снизу вверх, слева направо и справа налево;
вырезаем первые строки из изображение, которые имеют только один цвет, таким образом мы избавляемся от рамок, т.к. рамки могут быть разной ширины и вносить шум в изображения. Например это демотиваторы со своими черными рамками;
цвета могу иметь оттенки либо размытости, поэтому нужно их будет уменьшать диапазон цветов, т.е. приводить их к определённым цветам. Например оттенки зелёного приводить к зелёному цвету. Оттенки белого - к белому;
после того, как обрезали рамки, считывать сверху вниз цвета пикселей, приводить их к цветовому диапазону, как выше писал. В результате в массив записывать процент цветов (красный - 20%, синий - 70%, черный - 10%) всей картинки;
те картинки, которые будут иметь похожий набор цветов сравнивать. Таким образом уже сузили круг картинок. Если нету похожего набора цветов, то с большой вероятностью можно предположить, что дубликатов такой картинки нет;
если есть похожие картинки по набору цветов - тут уже сложнее, как их сравнить? Т.к. картинка может быть немного обрезана, то попиксельное сравнение тут не подойдет. Нужно как-то кусками проверять, брать какие-то куски картинки и сравнивать их с кусками других картинок. Лучше всего с середины, т.к. картинка может быть обрезана по краям, но середина всегда есть и она одинаковая. Берем квадрат картинки, небольшой по размеру, например 100x100 пикселей (можно несколько таких квадратов взять). Квадраты не должны быть однотонные, т.к. может попасться такой квадрат, который будет как фон на картинке. Определяем цветовые диапазоны, как я выше писал. Т.е. процент входящих цветов;
ищем такой квадрат в другой картинке. Причем цикл будет очень большим, т.к. не знаем в каком месте будет этот квадрат + он будет размером не 100x100, а может 85x85 (если уменьшена) или 106x106 (если увеличена). Это скорее всего самая сложная часть будет при написании кода.

Просьба вдуматься глубоко в задачу и подать идеи. Задача очень сложная, но решение имеет, т.к. если в гугл закинуть картинку, она находит дубликаты, значит алгоритм реализовать реально.

Автор: samssrus 8.10.2016, 09:17

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

Этот ответ добавлен с нового Винграда - http://ru.vingrad.com/Sravnit-izobrazheniya-nayti-dublikaty-id57f7954aadbd5f204444e8a2#findElement_E7045_57f88f6086c4c56d5d3f3ec7_0

Автор: samssrus 8.10.2016, 09:17

Автор: Elfer 8.10.2016, 14:03

Да согласен, что для начала хеш сравнить. Храню хеши всех картинок и сравниваю. Это уже сделано, но этого мало. Вот поэтому и пришёл к этой сложной задаче.
Понимаю, что вышеописанный мной механизм - ресурсозатратный. Оптимизация - это уже вторая часть. В качестве оптимизации - хранить результат обработки фотографий в базе. Т.е. центральную часть фотографий, а именно массив приведённых оттенков цветов к определённому цвету. Салатовый и темно-зелёный к зеленому, светло-белый и темно белый - к белому и т.д.
Когда добавляем новую фотографию - обрабатывать ее, результат помещать в базу и затем брать из базы другие центр. части (массив цветовых переходов) и делать сравнение.

На данный момент это самый идеальный вариант, перечитал кучу топиков на хабре и на других форумах.