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

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

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

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

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

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

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

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

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

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

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

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

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

white
red
blue
green
black

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

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

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

Как насчет использования функции обнаружения краев ? alt text http://upload.wikimedia.org/wikipedia/en/thumb/8/8e/EdgeDetectionMathematica.png/500px-EdgeDetectionMathematica.png

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

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

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

область интереса

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

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 пикселей.

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

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

Трансформация

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

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

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

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

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

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

Сжатие

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

FFFFFF|000000|FDFD44|FFFFFF

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

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

Новые идеи

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

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

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

Другие вещи для рассмотрения

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

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

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

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

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

Читайте газету: Порикли, Фатих, Онсель Тузель и Питер Меер. “Covariance Tracking Using Model Update Based on Means on Riemannian Manifolds”. (2006) IEEE Computer Vision and Pattern Recognition.

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

Идея:

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

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

Варианты:

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

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

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


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

http://en.wikipedia.org/wiki/RGB_color_space
http://upvector.com/index.php?раздел=tutorials&subsection=учебники/цветовое пространство

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

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