Алгоритм сравнения двух изображений

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

Знаете ли вы какой-либо алгоритм для выполнения этой работы?

+156
источник поделиться
9 ответов

Это просто идеи, о которых я думал, никогда не пробовал, но мне нравится думать о таких проблемах!

Прежде чем начать

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

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

Matlab - отличный инструмент для тестирования и оценки изображений.

Тестирование алгоритмов

Вы должны протестировать (как минимум) большой анализируемый человеком набор тестовых данных, где совпадения известны заранее. Если, например, в ваших тестовых данных у вас есть 1000 изображений, из которых 5% соответствуют, у вас теперь есть достаточно надежный тест. Алгоритм, который находит 10% позитивов, не так хорош, как алгоритм, который находит 4% позитивов в наших тестовых данных. Тем не менее, один алгоритм может найти все совпадения, но также может иметь большой процент ложных срабатываний в 20%, поэтому есть несколько способов оценить ваши алгоритмы.

Тестовые данные должны быть направлены на то, чтобы охватить как можно больше типов динамики, которые вы ожидаете найти в реальном мире.

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

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

Цветные ведра

С двумя картинками отсканируйте каждый пиксель и посчитайте цвета. Например, у вас могут быть "ведра":

white
red
blue
green
black

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

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

Обнаружение края

Как насчет использования Edge Detection. alt text
(источник: wikimedia.org)

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

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

alt text

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

Интересные регионы

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

alt text
(источник: meetthegimp.org)

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

Если у вас есть более 2 областей интереса, вы можете измерить расстояния между ними. Возьмите этот упрощенный пример:

alt text
(источник: per2000.eu)

У нас есть 3 четких региона интересов. Расстояние между областями 1 и 2 может составлять 200 пикселей, от 1 до 3 400 пикселей и от 2 до 3 200 пикселей.

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

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

морфинг

Превращение двух изображений в - это процесс превращения одного изображения в другое с помощью ряда шагов:

alt text

Обратите внимание, это отличается от перехода одного изображения в другое!

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

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

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

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

Архивирование

Ответ на этот вопрос превосходен, я помню, как читал об этой технике изучения ИИ. Это довольно эффективно при сравнении лексиконов корпуса.

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

Коэффициент сжатия является очень быстрым и достаточно эффективным способом определения того, насколько похожи два набора данных. Читая о принципах сжатия, вы поймете, почему это может быть настолько эффективно. Для быстрого выпуска алгоритма это, вероятно, будет хорошей отправной точкой.

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

Инвертирующие сигналы

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

alt text
(источник: themotorreport.com.au)

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

Однако рассмотрим два одинаковых изображения, за исключением того, что к одному из них применен эффект яркости:

alt text
(источник: mcburrz.com)

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

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

Древовидные структуры данных

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

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

Это, вероятно, не сработает, но это идея. Структура три данных отлично подходит для хранения лексиконов, например словаря. Это префиксное дерево. Возможно, возможно создать образ, эквивалентный лексикону (опять же, я могу думать только о цветах), чтобы построить три. Если вы уменьшите, скажем, изображение 300x300 до 5x5 квадратов, то разбейте каждый квадрат 5x5 на последовательность цветов, из которых вы могли бы построить три из полученных данных. Если квадрат 2х2 содержит:

FFFFFF|000000|FDFD44|FFFFFF

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

Сравнение трех деревьев должно быть достаточно простым и может дать эффективные результаты.

Больше идей

Я наткнулся на интересную статью о классификации спутниковых снимков, там говорится:

Рассматриваются следующие показатели текстуры: матрицы совпадений, различия уровней серого, анализ тонов текстуры, особенности, полученные из спектра Фурье, и фильтры Габора. Некоторые функции Фурье и некоторые фильтры Габора были признаны хорошим выбором, в частности, когда для классификации использовалась одна полоса частот.

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

Другие вещи, которые следует учитывать

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

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

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

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

Будьте осторожны, чтобы не попытаться завершить бесконечный проект, удачи!

+294
источник

Прочтите статью: Порикли, Фатих, Онсель Тузель и Питер Меер. "Ковариационное отслеживание с использованием модели, основанной на версии на средствах на римановых многообразиях "(2006) IEEE Computer Vision и распознавание образов.

Я успешно обнаружил перекрывающиеся области в изображениях, снятых с соседних веб-камер, используя технику, представленную в этой статье. Моя ковариационная матрица была составлена ​​из результатов Sobel, canny и SUSAN aspect/edge detection, а также исходных оттенков серого.

+36
источник
другие ответы

Связанные вопросы


Похожие вопросы

Идея:

  • использовать детекторы ключевых точек для поиска дескрипторов, определяющих масштаб и преобразование некоторых точек изображения (например, SIFT, SURF, GLOH или LESH).
  • попытайтесь выровнять ключевые точки с похожими дескрипторами с обоих изображений (например, при панораме), при необходимости, при необходимости, сделать некоторые преобразования изображений (например, масштабирование и поворот или растяжение эластичности).
  • если многие ключевые точки хорошо выравниваются (существует такое преобразование, что ошибка выравнивания ключевой точки низкая, или трансформация "энергия" низка и т.д.), у вас, вероятно, есть похожие изображения.

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

Варианты:

  • Обнаружение ребер или других объектов вместо точек.
+33
источник

Это действительно намного менее просто, чем кажется:-) Предложение Nick - хорошее.

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


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

http://en.wikipedia.org/wiki/RGB_color_space
http://upvector.com/index.php?section=tutorials&subsection=tutorials/colorspace


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

http://homepages.inf.ed.ac.uk/amos/hough.html
http://rkb.home.cern.ch/rkb/AN16pp/node122.html
http://en.wikipedia.org/wiki/Hough_transform

+15
источник

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

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

Устойчив к атакам обработки сигналов ► Усиление сигнала - повышение резкости, контрастности и т.д. ► Фильтрация - средний, низкий, высокий и т.д. ► Аддитивный шум - гауссовский, равномерный и т.д. ► Сжатие с потерями - JPEG, MPEG и т.д.

Устойчив к геометрическим атакам ► Аффинные преобразования ► Сокращение данных - обрезка, вырезка и т.д. ► Случайные локальные искажения ► Деформация

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

+8
источник

Это всего лишь предложение, оно может не сработать, и я готов к этому.

Это создаст ложные срабатывания, но, надеюсь, не будет ложных негативов.

  • Измените размер обоих изображений так, чтобы они были одного размера (я предполагаю, что отношения между ширинами и длинами на обоих изображениях одинаковы).

  • Сжатие растрового изображения обоих изображений с помощью алгоритма сжатия без потерь (например, gzip).

  • Найдите пары файлов с одинаковыми размерами файлов. Например, вы можете просто отсортировать каждую пару файлов, которые у вас есть, насколько похожи размеры файлов и получить верхний X.

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

+5
источник

Я считаю, что если вы готовы применить подход к любой возможной ориентации и к отрицательным версиям, хорошим началом распознавания изображений (с хорошей надежностью) является использование собственных интерфейсов: http://en.wikipedia.org/wiki/Eigenface

Еще одна идея - преобразовать оба изображения в векторы их компонентов. Хороший способ сделать это - создать вектор, который работает в размерах x * y (x - ширина вашего изображения, а y - высота) со значением для каждого измерения, применяемого к значению пикселя (x, y). Затем запустите вариант K-Nearest Neighbors с двумя категориями: match и no match. Если он достаточно близок к исходному изображению, он будет вписываться в категорию соответствия, если нет, то он не будет.

K Ближайшие соседи (KNN) можно найти здесь, есть и другие хорошие объяснения этого в Интернете: http://en.wikipedia.org/wiki/K-nearest_neighbor_algorithm

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

+4
источник

Если вы хотите вообще рассмотреть другой подход к обнаружению незаконных копий ваших изображений, вы можете рассмотреть watermarking. (от 1.4)

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

В то время как это также сложное поле, существуют методы, позволяющие сохранять информацию о водяных знаках через грубое изменение изображения: (с 1.9)

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

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

+1
источник

Если вы используете Linux, я бы предложил два инструмента:

align_image_stack из пакета hugin-tools - это программа командной строки, которая может автоматически корректировать поворот, масштабирование и другие искажения (в основном это предназначено для компоновки снимков HDR, но также работает для видеокадров и других документов). Дополнительная информация: http://hugin.sourceforge.net/docs/manual/Align_image_stack.html

сравнить с пакетом imagemagick - программа, которая может находить и подсчитывать количество разных пикселей в двух изображениях. Здесь аккуратный учебник: http://www.imagemagick.org/Usage/compare/ uising -fuzz N% вы можете увеличить допустимость ошибок. Чем выше значение N, тем выше допустимое отклонение от ошибок, чтобы по-прежнему считать два пиксела одинаковыми.

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

0
источник

Посмотрите другие вопросы по меткам или Задайте вопрос