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

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

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

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

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


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

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

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

...inserts copyright information into the digital object without the loss of quality. Whenever the copyright of a digital object is in question, this information is extracted to identify the rightful owner. It is also possible to encode the identity of the original buyer along with the identity of the copyright holder, which allows tracing of any unauthorized copies.

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

... any signal transform of reasonable strength cannot remove the watermark. Hence a pirate willing to remove the watermark will not succeed unless they debase the document too much to be of commercial interest.

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

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

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

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

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

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

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

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

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

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

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

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

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

Идея:

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

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

Варианты:

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

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