Как реализовать поиск похожих фото на сервере?

Question

[Silm]

Есть сервис, где пользователи могут загружать фотографии на сервер. Требуется при загрузке фото проверять, нет ли уже на сервере такой же или очень похожей фотографии.

С высокой вероятностью должны находиться дубликаты изображений с легкими изменениями: ресайз, наклон, изменения цвета, добавление/удаление небольших элементов.

Известно про библиотеку https://github.com/jedisct1/libpuzzle не понятно, можно ли и как с ее помощью создать индекс и осуществлять поиск. Разыскиваются и другие библиотеки/готовые инструменты, не обязательно на/для php. Главное, нужна сама методика индексации и последующего поиска по базе.

Answer 1

[SharuPoNemnogu]

вот из этой статьи писал класс на основе дискретных косинусных преобразований, который высчитывал хэш, его хранил в базе и высчитывал расстояние Хемминга, на основе которого определялась степень похожести. Алгоритм не быстрый правда, зато изменение цвета, ресайз и небольшой наклон в принципе не помеха. Для пыха вроде есть расширение pHash

Answer 2

[xmoonlight]

Поиск делается с помощью уникальных частей (искривление прямой с углом: 15-165 градусов внутри одной такой части, не нашли - расширяем радиус, нашли - отрезаем эту зону из дальнейшего поиска) на общем изображении и их расположении относительно друг друга.
Все контурные кусочки поворачиваются по одному алгоритму: например, максимальное кол-во точек по линии-радиусу (от центра до края) - всегда вниз. Если они повторяются - максимальный угол между такими повторами - всегда слева.
Каждый такой кусок - это отдельный хэш. Связка таких кусков - "дерево" хешей.
При поиске - сравниваем хэши искомого и куска из базы с другим через расстояние Хэмминга и ищем зависимости по дереву наиболее совпавшей их последовательности.

Answer 3

[un1t]

blog.iconfinder.com/detecting-duplicate-images-usi...

Есть готовые алгоритмы для любых языков такие как dhash, например.

Answer 4

[Dimonchik]

phash - просто, но, увы, не канает при обрезке

там рулят сети , обученные в т.ч. ImageNet, но оно затратнее в разы, сервер уж точно не один, или один, но ядер на 40

Comments

[Silm]

Пока что под наши требования удовлетворительно подходит алгоритм dhash. Он уверено определяет дубликаты с водными знаками, небольшими рамками, обрезанные, обрезанные с ресайзом, фото с изменением цвета и контраста. Единственное, не определяет дубль при повороте изображения, даже на небольшой угол. Дает приемлемый уровень ложных срабатываний для решения задачи.