У нас есть коллекция фотоизображений размером несколько сотен концертов. Большое количество фотографий визуально дублируется, но с различными размерами файлов, разрешением, сжатием и т.д.
Можно ли использовать какие-либо конкретные методы обработки изображений для поиска и удаления этих повторяющихся изображений?
Недавно я хотел выполнить эту задачу для галереи изображений PHP. Я хотел иметь возможность генерировать "нечеткий" отпечаток пальца для загруженного изображения и проверять базу данных для любых изображений, имеющих один и тот же отпечаток пальца, что свидетельствует о том, что они были похожими, а затем более точно сравнить их, чтобы определить, насколько они похожи.
Я выполнил его, изменив размер загруженного изображения до 150 пикселей в ширину, уменьшив его до оттенков серого, округляя значение каждого цвета до ближайшего кратного 16 (давая 17 возможных оттенков серого от 0 до 255), нормализуйте их и сохраните их в массиве, создав тем самым "нечеткую" цветовую гистограмму, а затем создав md5sum гистограммы, которую я смог бы найти в своей базе данных. Это было чрезвычайно эффективно для сужения изображений, которые были очень визуально похожи на загруженный файл.
Затем, чтобы сравнить загруженный файл с каждым "похожим" изображением в базе данных, я взял оба изображения, изменил их размер до 16x16 и проанализировал их по пикселям и взял значение RGB каждого пикселя в сторону от значения соответствующего пиксель в другом изображении, добавляя все значения вместе и делясь на количество пикселей, что дает мне среднее отклонение цвета. Было определено, что значение меньше определенного значения является дубликатом.
Все это написано на PHP с использованием модуля GD, а сравнение с тысячами изображений занимает всего несколько сотен миллисекунд за каждый загруженный файл.
Мой код и методология здесь: http://www.catpa.ws/php-duplicate-image-finder/
Попробуйте PerceptualDiff для сравнения двух изображений с одинаковыми размерами. Позволяет создавать такие объекты, как просмотр изображений только с X числом пикселей, отличающихся визуально неотличимыми.
Если визуальные дубликаты могут иметь разные размеры из-за масштабирования или разных типов файлов, вы можете сделать стандартный формат для сравнения. Например, я могу использовать ImageMagick для масштабирования всех изображений до 100x100 и сохранения их в виде файлов PNG.
Очень простой подход заключается в следующем:
Преобразуйте изображение в оттенки серого в памяти, так что каждый пиксель будет только числом от 0 (черный) до 255 (белый).
Увеличьте изображение до фиксированного размера. Найти правильный размер важно, вы должны поиграть с разными размерами. Например. вы можете масштабировать каждое изображение до 64x64 пикселей, но вы можете получить лучшие или худшие результаты с меньшими или большими изображениями.
Как только вы сделали это для всех изображений (да, это займет некоторое время), всегда загружайте два изображения в память и вычитайте их друг из друга. Это вычитает значение пикселя (0,0) на изображении A ob значение пикселя (0,0) в изображении B, теперь делает то же самое для (0,1) в обоих и так далее. Полученное значение может быть положительным или отрицательным, вы должны всегда сохранять абсолютное значение (поэтому 5 результатов в 5, -8, однако, приводят к 8).
Теперь у вас есть третье изображение, являющееся "разностным изображением" (дельта-изображение) изображений A и B. Если они были идентичны, дельта-изображение все черное (все значения будут вычтены на ноль). "Чем меньше черного", тем менее идентичны изображения. Вам нужно найти хороший порог, так как даже если изображения на самом деле идентичны (для ваших глаз), масштабируя, изменяя яркость и т.д., Дельта-изображение не будет полностью черным, оно, однако, будет иметь только очень темные оттенки серого. Таким образом, вам нужен порог, который говорит: "Если средняя ошибка (яркость дельта-изображения) ниже определенного значения, все же есть хорошие шансы, что они могут быть идентичными, однако если это выше этого значения, скорее всего, нет. порог так же сложно, как найти правильный размер масштабирования. У вас всегда будут ложные срабатывания (изображения считаются идентичными, хотя их совсем нет) и ложные негативы (изображения считаются не идентичными, хотя они и есть).
Этот алгоритм очень медленный. Фактически только создание изображений в оттенках серого требует много времени. Затем вам нужно сравнить каждое изображение GS друг с другом, опять же, с большим количеством времени. Кроме того, хранение всех изображений GS занимает много места на диске. Таким образом, этот алгоритм очень плох, но результаты не так уж плохи, хотя это и так просто. Хотя результаты не удивительны, они лучше, чем я думал изначально.
Единственный способ получить еще лучшие результаты - использовать расширенную обработку изображений, и здесь он начинает очень усложняться. Это связано с большим количеством математики (это очень много); есть хорошие приложения (искатели обломоков) для многих систем, которые реализованы, поэтому, если вы не запрограммируете его самостоятельно, вам, вероятно, лучше использовать одно из этих решений. Я читал много статей по этой теме, но я боюсь, что большинство из них выходит за мой горизонт. Даже алгоритмы, которые я мог бы реализовать в соответствии с этими документами, находятся за его пределами; это означает, что я понимаю, что нужно сделать, но я понятия не имею, почему это работает или как это работает, это просто магия; -)
Я действительно написал приложение которое делает именно это.
Я начал с предыдущего приложения, которое использовало базовый алгоритм Levenshtein Distance для вычисления сходства изображений, но этот метод нежелателен по ряду причин, Без сомнения, самый быстрый алгоритм, который вы собираетесь найти для определения сходства изображений, - это средняя квадратическая ошибка или означает абсолютную ошибку (обе имеют время работы O (n), где n - количество пикселей на изображении, и также было бы тривиально нить реализации алгоритм несколькими способами). Сообщение Mecki на самом деле - это просто реализация Mean Absolute Error, которую может выполнять мое приложение (код также доступен для вашего удовольствия от просмотра, если вы этого желаете).
В любом случае, в нашем приложении мы сначала сбрасываем образцы изображений (например, все масштабируется до, скажем, 32 * 32 пикселя), затем преобразуется в шкалу серого, а затем запускает полученные изображения через наши алгоритмы сравнения. Мы также работаем над некоторыми более продвинутыми алгоритмами предварительной обработки, чтобы еще больше нормализовать изображения, но... еще не совсем там.
Есть, безусловно, лучшие алгоритмы, чем MSE/MAE (на самом деле проблемы с этими двумя алгоритмами применительно к визуальной информации хорошо документированы), например SSIM, но это стоит дорого. Другие люди пытаются сравнить другие визуальные качества изображения, такие как яркость, контрастность, цветные гистограммы и т.д., Но все это дорого по сравнению с простым измерением сигнала ошибки.
Мое приложение может работать, в зависимости от количества изображений в этих папках. Он многопоточный (я видел, что он полностью загружает восемь процессорных ядер, выполняющих сравнения), но я никогда не тестировал базу данных изображений, содержащую более нескольких сотен изображений. Несколько сотен гигов изображений звучат непомерно большими. (просто считывая их с диска, понижая дискретизацию, конвертируя в шкалу серого и сохраняя в памяти - при условии, что у вас достаточно памяти для хранения всего, что вы, вероятно, не можете, может занимать пару часов).
Это все еще область исследований, я считаю. Если у вас есть какое-то время в ваших руках, некоторые релевантные ключевые слова:
В принципе, каждое изображение обрабатывается (индексируется) для создания "сигнатуры изображения". Аналогичные изображения имеют похожие подписи. Если ваши изображения просто перемасштабированы, то, вероятно, их подпись почти идентична, поэтому они хорошо группируются. Некоторые популярные подписи являются дескрипторами MPEG-7. Чтобы сгруппировать, я думаю, что K-Means или любой из его вариантов может быть достаточно. Однако вам, вероятно, придется иметь дело с миллионами изображений, это может быть проблемой.
Вот ссылка на главную запись в Википедии:
http://en.wikipedia.org/wiki/CBIR
Надеюсь, что это поможет.
Быстрый взломать это - написать программу, которая будет вычислять значение среднего пикселя в каждом изображении, в оттенках серого, сортировать по этому значению и затем сравнивать их визуально. Очень похожие изображения должны встречаться рядом друг с другом в отсортированном порядке.
Сходство с изображениями, вероятно, является под-полем обработки изображений /AI.
Будьте готовы реализовать алгоритмы/формулы из документов, если вы ищете отличное (то есть эффективное и масштабируемое) решение.
Если вы хотите что-то быстрое n грязное, найдите google для сходство с изображениями
Вот приложение схожести изображений С#, которое может делать то, что вы хотите.
В принципе, все алгоритмы извлекают и сравнивают функции. Как они определяют "функцию", зависит от математической модели, на которой они основаны.
Вам понадобится инструмент командной строки для обработки большого количества данных.
Сравнение всех возможных пар изображений не будет масштабироваться для такого большого набора изображений. Вам необходимо отсортировать весь набор изображений в соответствии с некоторой метрикой, чтобы сравнения необходимы только для соседних изображений.
Примером простой метрики является среднее значение всех пикселей в изображении, выраженное как одно значение оттенка серого. Это должно работать только в том случае, если дубликаты не имеют каких-либо визуальных изменений. Использование формата файла с потерями также может привести к визуальным изменениям.
Мышление вне поля, вы можете использовать метаданные изображения, чтобы сузить набор данных. Например, ваши изображения могут иметь поля, показывающие дату и время, когда изображение было снято, вплоть до ближайшей секунды. Дубликаты, вероятно, будут иметь одинаковые значения. Инструмент, такой как exiv2, может использоваться для выгрузки этих данных в более удобный и отсортированный текстовый формат (с небольшим знанием партии /shell scripting).
Даже такие поля, как производитель и модель камеры, могут использоваться для уменьшения набора из 1 000 000 изображений сказать 100 наборов из 10 000 изображений, значительное улучшение.
В программе gqview есть возможность поиска дубликатов, поэтому вы можете попробовать посмотреть там. Тем не менее, он не является надежным, поэтому он подходит только для эвристики, чтобы представить дубликаты для человека, для подтверждения вручную.
Самая важная часть - сделать файлы сопоставимыми.
Общим решением может быть масштабирование всех изображений до определенного фиксированного размера и шкалы серого. Затем сохраните полученные изображения в отдельном каталоге с тем же именем для последующей ссылки. Затем можно было бы отсортировать файлы и визуально сравнить соседние записи.
Результирующие снимки могут быть количественно определены определенными способами для программного обнаружения сходств (усреднение блоков, строк и т.д.).
Я бы предположил, что наиболее масштабным методом будет хранение отпечатка пальца с каждым изображением. Затем, когда добавляется новое изображение, это простой случай SELECT id FROM photos where id='uploaded_image_id' для проверки дубликатов (или отпечатки пальцев всех изображений, а затем выполнения запроса для дублирования
Очевидно, что простой файловый хэш не будет работать, поскольку фактический контент отличается.
Акустическая отпечатка пальца/этот документ может быть хорошее начало в концепции, поскольку есть много реализаций этого. Здесь - документ, посвященный фингерпринтингу изображений.
Тем не менее, вы можете уйти с чем-то более простым. Что-то столь же базовое, как изменение размера изображения на равную ширину или высоту, вычитание image_a из image_b и суммирование разницы. Если общая разница ниже порога, изображение является дубликатом.
Проблема заключается в том, что вам нужно сравнивать каждое изображение со всеми остальными. Требуемое время будет экспоненциально увеличиваться.
Если вы можете найти способ сравнения изображений, которые подчиняются неравенству треугольника (например, если 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) времени для каждого изображения.
Если ваши совпадения ограничены одним и тем же изображением после изменения количества сжатия/изменения размера /etc, то преобразование в некоторый канонический размер/цветовой баланс /etc и просто суммирование квадратов различий каждого пикселя может быть хорошей метрикой, и это подчиняется неравенству треугольника, поэтому вы можете использовать BK-дерево для эффективного доступа.
Если у вас есть немного денег, чтобы потратить, и, возможно, после того, как вы запустите первый проход, чтобы определить, какие изображения, возможно, совпадают, вы можете написать тест для Amazon Mechanical Turk.
https://www.mturk.com/mturk/welcome
По существу, вы бы создали небольшой виджет, который AMT продемонстрировал бы реальным пользователям, которые в таком случае просто должны были бы ответить на вопрос "Эти два изображения одинаковы?". Или вы можете показать им сетку из 5x5 изображений и спросить их: "Какое из этих изображений соответствует?". Затем вы должны собрать данные.
Другим подходом было бы использование принципов Человеческих вычислений, которые наиболее широко поддерживались Луисом Фонном (http://www.cs.cmu.edu/~biglou/) с reCaptcha, который использует ответы Captcha для определения нечитаемых слов, которые выполнялись через распознавание оптического символа, что помогает оцифровывать книги. Вы можете сделать капчу, которая попросила пользователей помочь улучшить изображения.
Это звучит как процедурная проблема, а не проблема программирования. Кто загружает фотографии? Вы или клиенты? Если вы загружаете фотографию, стандартизируйте размеры до фиксированного масштаба и формата файла. Таким образом, сравнение будет проще. Однако, поскольку это означает, что если у вас нет дней или даже недель свободного времени, я предлагаю вам вручную удалять дубликаты изображений самостоятельно или вашей командой, визуально сравнивая изображения.
Возможно, вам следует сгруппировать изображения по местоположению, так как это туристические образы.