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

Прочитайте газету: Porikli, Fatih, Oncel Tuzel и Peter Meer. Отслеживание “Covariance Используя Образцовое Обновление На основе Средств на Риманновом Manifolds”. (2006) Машинное зрение IEEE и Распознавание образов.

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

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

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


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

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

Другой пример включает что-то позвонившее, которое Преобразовывает Hough. Это преобразование по существу разлагает изображение на ряд строк. Можно тогда проводить некоторые 'самые сильные' строки в каждом изображении и видеть, выстраиваются ли они в линию. Можно сделать, некоторая дополнительная работа, чтобы попытаться компенсировать вращение и масштабирующийся также - и в этом случае, начиная со сравнения нескольких строк является НАМНОГО меньшим количеством вычислительной работы, чем выполнение того же ко всем изображениям - это не будет настолько плохо.

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

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

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

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

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

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

Это функция, которую иногда запрашивают.

Как я люблю отмечать, ВСЕ функции не реализованы, пока кто-то не разработает, не разработает спецификации, не реализует, не протестирует, не задокументирует и не отправит эту функцию. Пока этого никто не сделал. Нет ничего необычного, почему бы и нет; у нас есть много других дел, ограниченные бюджеты, а этот никогда не обходился без ответа "разве это не было бы хорошо?" обсуждение в группе разработчиков языка.

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

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

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

Идея:

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

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

Варианты:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Цветовые сегменты

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

white
red
blue
green
black

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

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

Обнаружение кромок

Как насчет использования Обнаружение кромок .
_{(источник: wikimedia.org )}

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

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

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

Области интереса

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

_{(источник: meetthegimp.org )}

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

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

_{(источник: per2000.eu )}

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

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

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

Морфинг

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

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

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

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

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

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

Zipping

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

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

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

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

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

Инвертирование сигналов

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

_{(источник: themotorreport.com.au )}

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

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

_{(источник: mcburrz.com )}

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

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

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

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

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

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

FFFFFF|000000|FDFD44|FFFFFF

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

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

Другие идеи

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

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

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

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

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

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

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

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

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