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

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

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

23.08.2008 03:46:57
Как вы определяете, какой из них является оригиналом?
jfs 23.08.2008 03:50:21
Я предполагаю, что он имеет оригинал и должен проверить, является ли иностранный файл преобразованной копией или не связан с оригиналом.
unfa 21.12.2016 08:19:22
9 ОТВЕТОВ

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

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

36
5.04.2013 10:57:29
@Satoru Logic: поиск в Google показывает попадания на бумаге: google.com/… .
Nick 10.08.2010 03:40:33

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

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


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

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
17.09.2008 03:22:28

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

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

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

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

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

1
3.04.2009 14:10:43
Любая дополнительная информация о том, как водяные знаки сохраняются после интенсивного редактирования? Звучит очень интересно.
Tom Gullen 10.08.2010 09:06:04

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

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

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

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

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

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

5
26.08.2009 01:00:00
Мне очень нравится это решение, его легко внедрить, и я верю, что оно даст лучшую, чем случайная скорость идентификации
Tom Gullen 10.08.2010 01:34:18
Это вопрос: работает ли он, если копия была сохранена с другим разрешением?
Dr. belisarius 13.08.2010 02:54:54

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

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

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

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

4
10.08.2010 15:07:36
Хорошая идея, но только если в данных присутствуют лица. Также он идентифицирует людей, а не ситуации. Поэтому профессиональный актер, фигурирующий в нескольких публикациях, может вызвать много ложных срабатываний.
Tom Gullen 10.08.2010 01:37:18
Если только я неправильно понимаю ваше намерение использовать
Tom Gullen 10.08.2010 01:39:48
На самом деле я считаю, что алгоритм работает независимо от предмета, поэтому, если вы сравниваете деревья, он также будет полезен. Его просто называют Eigenfaces, потому что он классически связан с распознаванием лиц. Пока предмет для поиска обладает теми же общими характеристиками, что и предмет, который вы сравниваете с ним, он должен работать.
Nick Udell 10.08.2010 15:03:15
Слишком долго, чтобы добавить к предыдущему комментарию: Также: Eigenfaces сравнивают все изображение, а не только лица на экране. В примерах из Википедии используются только обрезанные лица, потому что традиционным приложением является распознавание лиц, для которых полезно только лицо. Если ваш актер появился в разных позициях, он будет помечен как другой.
Nick Udell 10.08.2010 15:11:38
Я сомневаюсь, что применение KNN непосредственно к необработанным значениям пикселей также очень поможет. Небольшие сдвиги / повороты обычно приводят к огромным различиям в необработанных значениях пикселей, особенно если изображение содержит резкие контрасты или тонкие линии. Таким образом, произвольно преобразованные версии одной и той же картинки не очень близки друг к другу в этом пространстве (они не распадаются на кластеры), и KNN не будет работать очень хорошо. Я предполагаю, что это могло бы хорошо работать на гистограммах изображения или некотором другом преобразовательно-инвариантном представлении изображения, все же.
Niki 13.08.2010 00:24:37

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

Прежде чем вы начнете

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

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

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

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

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

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

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

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

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

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

white
red
blue
green
black

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

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

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

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

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

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

альтернативный текст

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

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

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

альтернативный текст
(источник: meetthegimp.org )

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

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

альтернативный текст
(источник: per2000.eu )

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

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

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

морфинг

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

альтернативный текст

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

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

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

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

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

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

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

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

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

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

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

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

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

альтернативный текст
(источник: themotorreport.com.au )

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

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

альтернативный текст
(источник: mcburrz.com )

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

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

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

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

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

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

FFFFFF|000000|FDFD44|FFFFFF

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

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

Больше идей

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

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

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

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

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

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

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

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

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

299
5.08.2019 15:09:42
Потрясающий ответ. Слава за хорошо продуманный и поучительный ответ.
Andrew Hubbs 10.08.2010 00:24:17
Спасибо! Я надеюсь расширить это завтра, у меня есть еще несколько идей, о которых я хотел бы подумать и посмотреть.
Tom Gullen 10.08.2010 01:30:38
Привет, Том. Знаете ли вы о каких-либо библиотеках обнаружения краев с открытым исходным кодом?
Richard H 10.08.2010 09:27:45
Привет, Ричард, не извиняйся, но я уверен, что там есть. Поищите в Google «Java Gabor Filters» или «Java Edge Detection», и я уверен, что вы встретите один или два.
Tom Gullen 10.08.2010 09:35:34
Ссылка на изображение ( blog.meetthegimp.orgwp-content / uploads / 2009/04 / 97.jpg ) испортилась. Обратите внимание, что stackoverflow теперь имеет сервис хостинга изображений.
ThomasW 17.11.2011 00:49:35

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

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

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

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

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

8
22.08.2019 23:39:02

Идея:

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

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

Варианты:

  • Обнаружение краев или других объектов вместо точек.
34
12.08.2010 12:42:26
Я думаю, что это тоже правильный подход. Просто деталь: SIFT, SURF, GLOH не являются детекторами ключевых точек. Они являются ключевыми дескрипторами. Обычными детекторами ключевых точек являются (масштабно инвариантные) детекторы DoG, Harris или Eigenvalue.
Niki 12.08.2010 12:29:29
На шаге 2 вы можете использовать ближайших соседей, которые используют евклидово расстояние между дескрипторами
MobileCushion 6.05.2011 14:37:04

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

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

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

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

0
21.12.2016 08:45:45