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

Question

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

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

Answer 1

Читать статью: Porikli, Fatih, Oncel Tuzel, and Peter Meer. “Covariance Tracking Using Model Update Based on Means on Riemannian Manifolds”. (2006) IEEE Computer Vision and Pattern Recognition.

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

Answer 2

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

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


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

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

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

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

Answer 3

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

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

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

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

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

Answer 4

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

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

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

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

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

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

Answer 5

Я считаю, что если вы готовы применить подход к каждой возможной ориентации и отрицательных версий, хорошее начало распознавания образов (с хорошей надежностью) является использование eigenfaces: 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 является то, что чем больше вариантов вы сравниваете к исходному изображению, тем более точным становится алгоритм. Недостатком является то, что вам нужен каталог изображений для обучения системы в первую очередь.

Answer 6

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

Перед тем, как начать

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

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

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

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

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

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

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

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

Цвет Ковши

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

white 
red 
blue 
green 
black 

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

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

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

Как об использовании Edge Detection. alt text http://upload.wikimedia.org/wikipedia/en/thumb/8/8e/EdgeDetectionMathematica.png/500px-EdgeDetectionMathematica.png

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

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

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

Регионы интересов

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

alt text http://meetthegimp.org/wp-content/uploads/2009/04/97.jpg

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

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

alt text http://www.per2000.eu/assets/images/3_dots_black_03.jpg

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

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

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

морфинг

Morphing два изображения является процесс превращения одного изображения в другое через множество этапов:

Заметим, что это отличается от выцветания одного изображения в другое !

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

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

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

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

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

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

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

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

Прозрачность

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

Инвертирование Сигналы

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

alt text http://www.themotorreport.com.au/wp-content/uploads/2008/07/noise-cancellation.gif

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

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

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

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

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

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

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

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

FFFFFF|000000|FDFD44|FFFFFF 

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

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

Больше идеи

я наткнулся accross интересной статьи Краткой информации о classification of satellite imagery, то контурах:

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

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

Другие вещи, чтобы рассмотреть

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

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

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

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

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

Answer 7

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

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

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

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

Answer 8

Идея:..

1. используют KeyPoint детекторы, чтобы найти всемасштабной и Transform- инвариантные дескрипторы (например, SIFT, SURF, GLOH или LESH).
2. попытайтесь выровнять ключевые точки с похожими дескрипторами с обоих изображений (например, при панораме), при необходимости разрешить некоторые преобразования изображений (например, шкала & вращать , или эластичное растяжение).
3. , если многие ключевые точки хорошо выравниваются (существует такое преобразование, что ошибка выравнивания ключевой точки низкая; или трансформация «энергия» низка и т. д.), у вас, вероятно, есть похожие изображения.

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

Варианты:

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

Answer 9

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

align_image_stack из пакета Хугин-инструментов - это командная строка программы, которая может автоматически корректировать вращение, масштабирование и другие искажения (это в основном предназначен для компоновки снимков 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 должен исправить любое смещение, чтобы команда сравнения действительно имела возможность обнаруживать одинаковые пиксели.