ML для поиска дубликатов

[aeifn]

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

[paul-k-pastvu]

Да! я уверен, что даже писал это в одной из задач, в списке пожеланий к новому модулю загрузки
На Wikimedia Commons эта функция есть, значит существует открытая библиотека и открытый код для имплементации.

[yuriy-zhilovets2]

Посмотрел код. Там просто проверяется хэш sha1, что в общем бессмысленно. Изменение одного байта радикально меняет хэш.

[mkgrgis]

Для начала бы просто блокировать по sha-256 загрузку уже имеющихся изображений. Редко, но видел такие случаи, после которых был отзыв или удаление дубликата.

[paul-k-pastvu]

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

[mkgrgis]

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

[paul-k-pastvu]

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

[paul-k-pastvu]

Продолжение темы - #473

[yuriy-zhilovets2]

Изучил тему.

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

Алгоритм дифференциального хэша: https://dhashpy.readthedocs.io/en/latest/
Готовая библиотека: https://www.npmjs.com/package/dhash (требует наличия ImageMagick)

Хэш дает 64-битовую двоичную строку. Для сопоставления с хэшами других картинок используется расстояние Хэмминга.
Библиотека: https://www.npmjs.com/package/hamming-distance

Сложность представляет поиск похожих картинок среди имеющихся хэшей. При миллионе изображений в базе сравнение с каждой неприемлемо.

Для ускорения поиска используются деревья k-d-tree или vp-tree. Последние более специализированны и поэтому предпочтительнее.
http://stevehanov.ca/blog/index.php?id=130

Хранение индекса хэшей в виде деревьев в базе Монго, их построение и поиск по ним представляет собой отдельную достаточно сложную задачу. Возможно, стоит использовать какую-то графовую БД.

Для уменьшения количества ложных срабатываний пользуются еще таким методом: сначала ищут по dhash, потом еще раз по phash среди оставшихся кандидатов. Думаю, это пока излишне.

[yuriy-zhilovets2]

Я провел изыскания и эксперименты на эту тему. Задача решаемая.

Использовал dhash + simhash (2,8). Отпечаток фото занимает в базе 8 байтов, создание отпечатка требует 1-2 сек, основное время уходит на редактирование изображения с помощью ImageMagick.

Поиск по базе в 30.000 отпечатков фото занимает примерно 3 секунды. База mysql, таблицы без индексов, машина 10-летней давности.

Еще одним запросом можно найти зеркальные фото.

Если эта тема интересна, я продолжу опыты в следующих направлениях:

1. использование в качестве базы MongoDB
2. масштабирование до миллиона отпечатков (потребуется помощь, потому что у меня столько разных фото нет)
3. ускорение путем переписывания части кода на низкоуровневый язык

[kabalin]

Если эта тема интересна, я продолжу опыты в следующих направлениях:

1. использование в качестве базы MongoDB
2. масштабирование до миллиона отпечатков (потребуется помощь, потому что у меня столько разных фото нет)
3. ускорение путем переписывания части кода на низкоуровневый язык

Мне кажется, целесообразно это реализовать в виде сервиса, который можно добавить в стек и использовать через API. Не принципиально какая база, выбирайте что лучше подходит для такого рода данных и поиска. Можно оформить в отдельный open source проект.

В плане спецификации (по минимуму):

1. Возможность передать картинку и ее внешний идентификатор для добавления в базу.
2. Возможность передать картинку и получить по ней список идентификаторов визуально схожих картинок (в качестве дополнительных параметров могут быть ограничения по степени схожести и количеству записей в ответе сервиса).
3. Возможность передать внешний идентификатор и получить по нему список идентификаторов визуально схожих картинок (в качестве дополнительных параметров могут быть ограничения по степени схожести и количеству записей в ответе сервиса).
4. Возможность по внешнему идентификатору проверить его существование в базе.
5. Возможность удалить картинку (ее хэш) из базы по внешнему идентификатору.

В перспективе:

1. Возможность получить группы идентификаторов визуально схожих картинок для поиска дублей в существующей базе (может помочь при группировке снимков в "варианты фото" чтобы легко находить идентичные снимки и связывать их).

Кстати, интересно, не существует ли готового опенсорсного решения под такие требования?

[yuriy-zhilovets2]

Набросал прототип. Из вашего списка там не хватает только работы с базой (пункты 3, 4, 5), но это несложно добавить. Поиск дублей в уже готовой базе провести можно (после индексирования всех фото), вопрос только во времени и машинных ресурсах.

https://github.com/yuriy-zhilovets2/dupfinder

Работает на базе MySQL (MariaDB). C MongoDB не получилось, очень медленная скорость поиска даже с индексами. Есть подозрения, что и формат хранения у нее не оптимальный. Это в общем-то документная база и такую задачу она не тянет.

Нашел следующие опенсорсные решения (Python):

https://github.com/idealo/imagededup
https://github.com/elisemercury/Duplicate-Image-Finder

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

[kabalin]

Прототип выглядит как хорошее начало. Расчет hamming distance в MongoDB действительно непростая задача, публикации на эту тему чаще используют реляционные базы. Не совсем понятно, насколько быстрый будет расчет при наличии 1.5 млн записей, мне кажется это можно протестировать, сгенерировав необходимое количество хэшей.

Давайте протестируем как он отличает похожие снимки (в оба направления поиска), я выбрал несколько для примера:

• https://pastvu.com/p/1521538 и https://pastvu.com/p/111112
• https://pastvu.com/p/366790 и https://pastvu.com/p/1008264
• https://pastvu.com/p/95199 и https://pastvu.com/p/1416247
• https://pastvu.com/p/64859 и https://pastvu.com/p/477552
• https://pastvu.com/p/159471 и https://pastvu.com/p/79300
• https://pastvu.com/p/11477 и https://pastvu.com/p/1562146

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

[yuriy-zhilovets2]

Расчет hamming distance в MongoDB действительно непростая задача, публикации на эту тему чаще используют реляционные базы.

Проблема там не в расстоянии Хэмминга. Его на базе можно вообще не считать, а перенести в JS. Это будет чуть-чуть медленней (надо передать примерно 1000 строк), но не критично. Можно расчет и на WebAssembly переписать.

У Монго проблема в самом поиске. То ли индексы их никуда не годятся, то ли сами данные хранятся как-то не слишком эффективно, но запрос занимает раз в 5 больше времени, чем в MySQL.

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

15 сек на базе в 1.200.000 снимков (в основном, фильмы, разложенные на ключевые кадры). Компьютер у меня старый, так что на SSD и современном железе должно быть еще лучше. На Пикабу поиск дубликатов и сейчас идет 10-15 сек.

Давайте протестируем как он отличает похожие снимки (в оба направления поиска), я выбрал несколько для примера:

Проведу опыты и отпишусь.

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

[yuriy-zhilovets2]

Изложил алгоритм поиска, подходящий по моему мнению для pastvu и не требующий слишком больших ресурсов, здесь:
https://habr.com/ru/post/715714/

[yuriy-zhilovets2]

Добавил функции поиска по имени и удаления из базы.

[yuriy-zhilovets2]

Отчет по опытам на конкретных фотографиях:

1. Небольшой наклон в 1-2 градуса практически не влияет на поиск.
2. Дифференциальный хэш (dhash) находит только две схожих фотографии из приведенного выше списка (Внуково и Торговля). Тест в файле samples/test2-dhash
3. Я добавил еще расчет среднего хэша (ahash). Ahash находит все фото из списка кроме "Погодинской улицы" и "Дома крестьянина" (если сделать разбиение хэша на 10 частей, а не на 8). Тест в файл samples/test2-ahash
   Из недостатков, скорее всего, будут ложные срабатывания на большой базе

[yuriy-zhilovets2]

Вторая серия экспериментов: поиск на базе нейросетей
Использовал библиотеку imagedup https://github.com/idealo/imagededup
Тест в cnn/test-cnn-samples2.py
Такой же тест, но с хранением индексов в формате FAISS для быстрого поиска: test-faiss.py

Результаты лучше на порядок, находится все, что нужно, без ограничений.
Скорость поиска приличная (впрочем, на больших данных я не замерял), создание хэша не очень быстрое (секунд 10-20), но это разовая операция.
Однако и требования на порядок выше: хэш - это массив 576 чисел float32, для работы индекса требуется много памяти (порядка пары гигабайт для 2.000.000 индексов)

На практике будет удобно пользоваться не библиотекой FAISS, а специализированной базой данных Milvus. Работает в Докере.
Требования: 32 гб памяти, SSD, процессор Intel, поддерживающий специализированные векторные операции. Возможно использование GPU.

[kabalin]

Извиняюсь что долго не мог вам ответить. Спасибо большое, прочитал немного про Milvus, интересно. Теперь чтобы это можно было использовать как сервис, нужно сделать REST API приложение на основе этой библиотеки. Можете взять готовый фреймворк, к примеру Restlify, Loopback или решение на свое усмотрение. Аутентификация не нужна, так как коммуникация с сервисом будет со стороны сервера. Если в проект добавите docker-compose файл поднимающий сервис и все зависимости (Milvus), будет вообще великолепно!

[yuriy-zhilovets2]

API и Docker в проекте https://github.com/yuriy-zhilovets2/imagesim
Использовал другую базу данных - weaviate https://weaviate.io/developers/weaviate. Милвус работает только на процессорах Intel, что неудобно
Кроме того, в weaviate есть интересный задел - можно хранить текст и проводить потом нечеткий поиск (например, по описаниям фото).

[mkgrgis]

Чем дело закончилось?

[yuriy-zhilovets2]

Ничем. Возможно, мейнтейнер пока занят.