В одном из контент-проектов встала задача оптимизировать базу изображений, убрав дубли.
Исходные параметры базы:
- размер базы — 32 000 изображений, 38 Гб.
- формы — JPG, PNG, TIFF, GIF.
- характер дублей — полные дубли, изменённый цвет, яркость и контрастность, размеры и соотношение сторон, поворот.
Выбор приложений для поиска дублей
Рассматривал программы:
- AllDup (Windows)
- AntiDupl.NET (Windows)
- Anti-Twin (Windows)
- Auslogics Duplicate File Finder (Windows)
- Awesome Duplicate Photo Finder (Windows)
- CCleaner (Windows, MacOS)
- CloneSpy (Windows)
- d’peg! (Windows)
- DupDetector (Windows, MacOS, Linux)
- dupeGuru (Windows, MacOS, Linux)
- DupKiller (Windows)
- Duplicate Cleaner (Windows)
- Duplicate Photo Finder (Windows)
- Duplicate File Remover (Windows)
- Duplicate Photo Cleaner (Windows, MacOS)
- FirmTools Duplicate Photo Finder (Windows)
- Webminds Duplicate Photo Finder (Windows, MacOS)
- Duplicate Remover Free (Windows)
- Image Comparer (Windows)
- SearchMyFiles (Windows)
- Similar Images Finder (Windows)
- Similar Image Search (Windows, MacOS)
- Total Commander (Windows)
- VisiPics (Windows)
- XnView (Windows, MacOS)
- Duplicate File Detector (Windows)
- ImageDupeless (Windows)
Выбрал AllDub за возможность выбирать алгоритм сравнения, настраивать возможность включать и отключать сравнение изображений, имеющих разное соотношение сторон и размеры, а также повернутых изображений. Кроме того, приложение имеет достаточно удобный интерфейс для сравнения большого количества похожих изображений и позволяет сохранять результаты поиска, чтобы продолжить работу позднее.
Запустить AllDub на MacOS можно с помощью программ виртуализации VMware Fusion, Parallels Desktop, Crossover for Mac или Wine.
Процесс
Шаг 1. Поиск полных дубликатов
Сначала удаляем полные дубли (одинаковая длина, ширина, ориентация и др.) изображений. Это позволит быстро удалить изображения, которые не нужно сравнивать. Для сравнения используем самый быстрый алгоритм dHash.
По результатам поиска найдено более 8000 групп полных дублей, но есть проблемы:
- Поиск не различает цветные и черно-белые изображения. Это не зависит от выбранного алгоритма поиска.
- Многокадровые изображения в формате GIF сравниваются по первому кадру. Это приводит к большому количеству ошибок, так как многие GIF-изображения начинаются с белого или чёрного кадра.
Если у вас такая же проблема, то сначала используйте побайтовое сравнение файлов. Оно только частично решает проблему, так как не позволяет найти дубли изображений с разным сжатием файлов.
После удаления полных дублей осталось 21790 изображений размером 31 Гб.
Шаг 2. Поиск похожих изображений
На этом шаге ищем неточные дубли изображений (разный размер, ориентация, разное сжатие и прочее). Для этого выбираем долгий алгоритм pHash и точность совспадения 91%.
Это позволяет нам найти ещё 455 групп похожих изображений (всего изображений — 990 штук).
Итог
Осталось 21000 файлов суммарным размером 30,5 Гб.
Что почитать по теме алгоритмов сравнения изображений
- Сравнение изображений
- «Выглядит похоже». Как работает перцептивный хэш
- Поиск кропнутых дубликатов изображений с помощью перцептуальных хешей
- Кластеризация дубликатов в Яндекс.Картинках
- Поиск изображений по фрагменту
- Алгоритм быстрого нахождения похожих изображений
- Использование каскада Хаара для сравнения изображений
- Поиск дубликатов изображений на примере Instagram (также работа доступна в «Научном корреспонденте»)
- О методе повышения точности аннотирования изображений в краудсорсинге