Поиск дубликатов изображений

Поразмышляв как можно было бы реализовать поиск дубликатов изображений, а ля то что сделали в Яндекс, просуммирую мои мысли как это можно реализовать.

Заранее предупрежу что никакой строгой логики или формального изложения тут нет.

Какие шаги необходимо предпринять:

1. Создание «профилей изображений» — базы метаданных по каждому на основе которой можно было бы делать дальнейшие расчёты.

2. Для наполнения базы метаданных собрать базовые параметры: размер изображения в байтах, формат, crc32, md5, высоту, длину, отношение длины изображения к высоте.

3. Для каждого изображения сделать дополнительный расчёт следующих данных:

— таблицу цветоделения (с рядом упрощений);

— таблицу особенностей по результатам ridge и edge detection (как их рассчитывать отдельная тема).

— расчёт дополнительных особенностей (специалисты по компьютерному зрению знают)

Что характерно именно для изображений, мы относительно легко определить что некоторые изображения несхожи промеж собой, а также оценить сходство изображений при сравнении к 1 к 1.

Далее выберем наши критерии оценки и ограничений на выявление дубликатов:

1. Не рассматриваются как дубликаты изображения перевёрнутые на 90, 180 градусов.

2. Изображения полные дубликаты можно выявить по crc32 с доп. проверкой выявленных через md5

3. Изображение дубликат должно обладать близкими к оригинальному изображению пропорциями. Это отношение длины изображения к его высоте, которое у двух потенциальных дубликатов должно быть идентичным или же находится в пределах заданного отклонения.

4. Таблица цветоделения изображения дубликата должна соответствовать или же должна быть приближена в пределах заданного отклонения.

5. Таблица особенностей включая относительное расположение особенности, характер и размерность должны соответствовать у сравниваемых изображений.

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

Технически под эту задачу просятся HBase, Hypertable, Hadoop.

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

Большой недостаток вышеописанного лежит в области объёмов метаданных — они огромны. Плюс в возможности дальнейшей группировки по множеству различных критериев.

В дополнение добавлю что можно вспомнить решение задачки с расстоянием Левенштейна которую я приводил ранее. Если мы попарно сравниваем изображение A и B, а потом изображение B и C и в обоих случаях мы можем замерить численным образом разницу между ними, то вопрос в том как организовать последующее сравнение изображений так чтобы учитывать предыдущие результаты.

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

Сейчас же, в эпоху Amazon EC2 решить эту задачку можно даже за относительно скромные деньги и время. Вот распознавание информации в изображениях от IBM iMars мне интересно куда больше, будущее именно за этим.

About This Author

Яндекс.Метрика