Удаление дубликатов изображений [закрыто]

Question

У нас есть коллекция фотоизображений размером в несколько сотен гигабайт.Большое количество фотографий визуально дублируют друг друга, но с разными размерами файлов, разрешением, сжатием и т.д.

Можно ли использовать какие-либо конкретные методы обработки изображений для поиска и удаления этих дубликатов изображений?

Answer 1

Недавно я хотел выполнить эту задачу для галереи изображений PHP. Я хотел иметь возможность генерировать & Quot; fuzzy & Quot; Отпечаток пальца для загруженного изображения и проверьте базу данных на наличие изображений с одинаковыми отпечатками, указав, что они были похожи, а затем сравните их более тщательно, чтобы определить, насколько они похожи.

Я выполнил это, изменив размер загруженного изображения до 150 пикселей в ширину, уменьшив его до оттенков серого, округлив значение каждого цвета до ближайшего кратного 16 (давая 17 возможных оттенков серого между 0 и 255), нормализовав их и хранить их в массиве, создавая тем самым " fuzzy " Цветная гистограмма, затем создание md5sum гистограммы, которую я мог затем искать в моей базе данных. Это было чрезвычайно эффективно при сужении изображений, которые были очень визуально похожи на загруженный файл.

Затем сравните загруженный файл с каждым & аналогичным " Изображение в базе данных. Я взял оба изображения, изменил их размер до 16x16, проанализировал их попиксельно и вывел значение RGB каждого пикселя из значения соответствующего пикселя в другом изображении, сложив все значения вместе и разделив на количество пикселей дает мне среднее отклонение цвета. Все, что меньше определенного значения, было определено как дубликат.

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

Мой код и методология здесь: http://www.catpa.ws / PHP-дубликат-изображения видоискатель /

Answer 2

Попробуйте PerceptualDiff , чтобы сравнить 2 изображения с одинаковыми размерами. Позволяет использовать такие пороговые значения, как рассмотрение изображений с разным количеством пикселей только по X, чтобы они были визуально неразличимы.

Если визуальные дубликаты могут иметь разные размеры из-за масштабирования или разные типы файлов, Вы можете сделать стандартный формат для сравнения. Например, я мог бы использовать ImageMagick масштабировать все изображения до 100x100 и сохранять их в формате PNG.

Answer 3

Очень простой подход заключается в следующем:

• Преобразуйте изображение в оттенки серого в памяти, чтобы каждый пиксель представлял собой только число от 0 (черный) до 255 (белый).

• Масштабируйте изображение до фиксированного размера.Важно подобрать правильный размер, вам следует поиграть с разными размерами.Например.вы можете масштабировать каждое изображение до 64x64 пикселей, но вы можете получить лучшие или худшие результаты с меньшими или большими изображениями.

• Как только вы сделаете это для всех изображений (да, это займет некоторое время), всегда загружайте два изображения в память и вычитайте их друг из друга.То есть вычтите значение пикселя (0,0) на изображении A из значения пикселя (0,0) на изображении B, теперь сделайте то же самое для (0,1) в обоих случаях и так далее.Результирующее значение может быть положительным или отрицательным, вы всегда должны сохранять абсолютное значение (таким образом, 5 приводит к 5, -8, однако, приводит к 8).

• Теперь у вас есть третье изображение, являющееся "разностным изображением" (дельта-изображением) изображений A и B.Если бы они были идентичны, то дельта-изображение было бы полностью черным (все значения будут равны нулю).Чем "менее черным" оно является, тем менее идентичными получаются изображения.Вам нужно найти хороший порог, поскольку даже если изображения на самом деле идентичны (для ваших глаз), при масштабировании, изменении яркости и так Далее дельта-изображение не будет полностью черным, однако оно будет иметь только очень темные оттенки серого.Итак, вам нужен порог, который гласит: "Если средняя ошибка (дельта-яркость изображения) ниже определенного значения, все еще есть большая вероятность, что они могут быть идентичными, однако, если она выше этого значения, скорее всего, это не так.Найти правильный порог так же сложно, как и найти правильный размер масштабирования.У вас всегда будут ложноположительные результаты (изображения считаются идентичными, хотя это совсем не так) и ложноотрицательные результаты (изображения считаются неидентичными, хотя это так).

Этот алгоритм работает очень медленно.На самом деле только создание изображений в оттенках серого занимает массу времени.Затем вам нужно сравнить каждое изображение GS друг с другом, опять же, уйму времени.Кроме того, хранение всех изображений GS занимает много места на диске.Итак, этот алгоритм очень плох, но результаты не так уж плохи, хотя он и так прост.Хотя результаты не впечатляют, они лучше, чем я думал вначале.

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

Answer 4

Я действительно написал приложение , которое делает именно это.

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

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

Есть определенно лучшие алгоритмы, чем MSE / MAE (на самом деле, проблемы с этими двумя алгоритмами применительно к визуальной информации хорошо документированы), например, SSIM , но это обходится дорого. Другие люди пытаются сравнить другие визуальные качества в изображении, такие как яркость, контрастность, цветовые гистограммы и т. Д., Но это дорого по сравнению с простым измерением сигнала ошибки.

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

Answer 5

Я полагаю, что это все еще область исследований.Если у вас есть немного времени в запасе, вот несколько релевантных ключевых слов:

• Обнаружение копирования изображения
• Поиск изображений на основе контента
• Индексирование изображений
• Удаление дубликатов изображений

По сути, каждое изображение обрабатывается (индексируется) для создания "подписи изображения".Похожие изображения имеют похожие подписи.Если ваши изображения просто масштабированы, то, вероятно, их сигнатуры почти идентичны, поэтому они хорошо группируются.Некоторыми популярными сигнатурами являются дескрипторы MPEG-7.Я думаю, что для кластеризации может быть достаточно K-Means или любого из его вариантов.Однако вам, вероятно, придется иметь дело с миллионами изображений, это может быть проблемой.

Вот ссылка на основную статью в Википедии:
http://en.wikipedia.org/wiki/CBIR

Надеюсь, это поможет.

Answer 6

Сходство изображений - это, вероятно, подполе обработки изображений / AI.

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

Если вы хотите что-то быстрое и грязное, поищите в Google Сходство изображений

Вот приложение схожести изображений C #, которое может ты хочешь.

По сути, все алгоритмы извлекают и сравнивают функции. Как они определяют & Quot; feature & Quot; зависит от математической модели, на которой они основаны.

Answer 7

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

Answer 8

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

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

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

Answer 9

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

Даже такие поля, как производитель камеры и модель, могут быть использованы для уменьшения набора в 1 000 000 изображений. скажем, 100 наборов из 10000 изображений, значительное улучшение.

Answer 10

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

Answer 11

Самая важная часть - сделать файлы сопоставимыми.

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

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

Answer 12

Я бы предположил, что самый масштабируемый способ - хранить отпечатки пальцев с каждым изображением. Затем, когда добавляется новое изображение, это простой случай SELECT id FROM photos where id='uploaded_image_id', чтобы проверить наличие дубликатов (или снять отпечатки пальцев со всех изображений, а затем выполнить запрос на наличие дубликатов

Очевидно, что простой хэш-файл не будет работать, поскольку фактический контент отличается.

Акустическая дактилоскопия / этот документ может стать хорошим началом концепции, поскольку существует множество реализаций этого. Здесь - документ о снятии отпечатков пальцев с изображения.

Тем не менее, вы можете избежать неприятностей с чем-то более простым. Что-то такое простое, как изменение размера изображения до равной ширины или высоты, вычитание image_a из image_b и суммирование разницы. Если общая разница ниже порогового значения, изображение является дубликатом.

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

Answer 13

Если вы можете придумать способ сравнения изображений, который подчиняется неравенству треугольника (например, если d (a, b) является разницей между изображениями a и b, то d (a, b) < d (a, c) + d (b, c) для всех a, b, c), затем a BK-Tree было бы эффективным способом индексации изображений, так что вы можете найти совпадения по времени O (log n) вместо времени O (n) для каждого изображения.

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

Answer 14

Если у вас есть немного денег, чтобы потратить, и, возможно, когда вы выполните первый проход, чтобы определить, какие изображения соответствуют , может быть, , вы можете написать тест для Amazon Mechanical Turk.

https://www.mturk.com/mturk/welcome

По сути, вы бы создали небольшой виджет, который AMT показывал бы реальным пользователям, которые тогда просто должны были бы ответить на вопрос "!" Являются ли эти два изображения одинаковыми? " ;. Или вы можете показать им сетку, скажем, 5х5 изображений и спросить их & Quot; Какое из этих изображений соответствует? & Quot ;. Затем вы собираете данные.

Другой подход заключается в использовании принципов человеческого вычисления, наиболее известной из которых был Луис фон Ан ( http://www.cs.cmu.edu/~biglou/ ) с reCaptcha, который использует ответы Captcha для определения нечитаемых слов, которые были пропущены через оптическое распознавание символов, что помогает оцифровывать книги. Вы можете сделать капчу, которая попросит пользователей помочь уточнить изображения.

Answer 15

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

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