Процесс сравнения двух изображений в идеале должен отвечать на вопрос о сходстве содер-жания изображений. Содержат ли сравниваемые изображения одни и те же объекты с точностью до изменения ракурса съемки и перемещений камеры, изменения освещенности или масштаба объек-тов и т.д.
Важность для человека цветового восприятия изображения объясняет значение методов поис-ка визуальной информации на основании схожести с образцом по цветовым характеристикам.
Метод цветовых гистограмм – наиболее популярный из них. Возможно также использование таких показателей, как средний или основной цвета, а также множества цветов; эти характеристики имеет смысл использовать для локального индексирования областей изображения.
Качественное описание идей метода цветовых гистограмм приведено здесь
Идея метода цветовых гистограмм для индексирования и сравнения изображений сводится к следующему. Все множество цветов разбивается на набор непересекающихся, полностью покры-вающих его подмножеств. Для изображения формируется гистограмма, отражающая долю каждого подмножества цветов в цветовой гамме изображения. Для сравнения гистограмм вводится понятие расстояния между ними.
При разбиении RGB-цветов по яркости вычисляется интенсивность каждого цвета на основа-нии его красной, синей и зеленой составляющих. Полученное значение, заключенное между числа-ми 0 и 255, попадает в один из 16 интервалов, на которые разбивается диапазон возможных значе-ний. В качестве расстояния между гистограммами используется сумма модулей разности соответст-вующих элементов гистограмм; некоторое усовершенствование метода достигается при вычисле-нии расстояния на основании поэлементного сравнения гистограмм с учетом соседних элементов. Этот метод наиболее эффективен для черно-белых полутоновых изображений.
Для цветных RGB-изображений лучшие результаты дает другой способ - разбиение RGB-цветов по прямоугольным параллелепипедам. Цветовое RGB-пространство рассматривается как трехмерный куб, каждая ось которого соответствует одному из трех основных цветов (красному, зеленому или синему), деления на осях пронумерованы от 0 до 255 (большее значение соответству-ет большей интенсивности цвета). При таком рассмотрении любой цвет RGB-изображения может быть представлен точкой куба. Для построения цветовой гистограммы каждая сторона делится на 4 равных интервала, соответственно RGB-куб делится на 64 прямоугольных параллелепипеда. Гистограмма изображения отражает распределение точек RGB-пространства, соответствующих цветам пикселей изображения, по параллелепипедам. В качестве расстояния между гистограммами используется покомпонентная сумма модулей разности между ними. Несмотря на предельную простоту подхода, он показывает довольно стабильные результаты.
Основным недостатком метода цветовых гистограмм является то, что он теряет информацию о пространственном расположении объектов. Абсолютно разные картинки могут иметь сходные цветовые гистограммы. Например, изображение осенней листвы может содержать много небольших пятен красного цвета. Это даст сходную цветовую гистограмму с изображением большого красного объекта.
Дальнейшим развитием метода цветовых диаграмм стал метод когерентных цветовых векторов ( color coherent vectors, CCV). Основная статья, на которую опирался автор, расположена здесь
Я выполнил удачную попытку реализации этого метода. Ниже будут описаны основные идеи метода, являющиеся смысловым переводом основной статьи, опубликованной, естественно, на английском языке.
Когерентность определяется как мера принадлежности пикселей заданного цвета к достаточно крупным областям заданного цвета. Общее представление об этой идее показывает пара изображений, причем второе получено разрезанием и перемещением частей первого. Поэтому цветовые гистограммы этих изображений будут абсолютно идентичными. А вот площадь слитных областей одного цвета будет различной !
Каждый пиксель изображения необходимо классифицировать и определить, относится ли он к когерентной области или к некогерентной. Общая последовательность расчета вектора когерентных цветов для изображения будет следующей.
Шаг 1. Масштабируем изображение до некоторого стандартного размера w*w пикселей.
Шаг 2.Производим усреднение изображения путем нанесения гауссова шума.
Шаг 3. Уменьшаем количество цветов изображения до некоторого значения N.
Шаг 4. Необходимо классифицировать отдельные области изображения, имеющие общий цвет, объединив их в т.н. корзины (buckets). Если у пикселя в любом из восьми доступных направлений (в т.ч. и диагональных направлениях) имеется пиксель того же цвета, то эти пиксели объединяются в общую группу и помечаются общей числовой меткой. Я создал специальный квадратный массив, в котором отмечались уже обработанные пиксели изображения. Вышесказанное демонстрируется следующим рисунком:
На левом рисунке приведен числовой индекс цвета каждого пик села изображения. Цветом выделены участки с цветом 62. Справа приведен фрагмент массива корзин. Три фрагмента одного и того же цвета разнесены в три корзины различной длины. Поэтому количество корзин может быть намного больше, чем количество цветов изображения. Этот шаг алгоритма является наиболее сложным и трудоемким. В его реализации использованы идеи волновых алгоритмов, применяемых, например, для определения путей перемещения по лабиринтам.
Шаг 5. Задаем минимальную длину τ корзины, содержащую когерентную область.
Шаг 6. Для каждого цвета определяем количество пикселей, принадлежащих к когерентным (αi) и некогерентным (βi) корзинам. Таким образом, для заданного изображения мы вычислили вектор значений когерентных цве-тов следующего вида: {Ci, (αi , βi )}, где Ci –цвет пикселей, αi , βi – количество соответственно когерентных и некогерентных пикселей. Очевидно, что теперь в качестве частного случая легко получить и данные для метода цветовых гистограмм, так как αi + βi равняется общему числу пикселей указанного цвета.
Расстояние между двумя изображениями для метода цветовых гистограмм определяется как
, и для метода когерентных цветовых векторов по выражению :
Экспериментальные результаты.
Все приведенные выше рассуждения были реализованы в виде модуля Object Pascal, тестовая программа написана на Delphi 7.0. Общая работоспособность алгоритма была тщательно проверена при работе с отдельными парами изображений. На рисунке ниже приведен фрагмент главного окна программы, демонстрирующий результаты расчета вектора когерентных цветов и вычисления расстояния между заданными изображениями.
Несмотря на общий цветовой фон у следующей пары изображений, отчетливо видна разница в цветовых гистограммах пары изображений.
Была разработана версия программы, реализующая сравнение изображений, размещенных в базе данных Firebird 2.1. Программа вполне успешно справляется с поиском сходных изображений, несмотря на наличие небольших вращений изображения. Существует сложная концептуальная проблема выбора способа хранения в базе данных двухкомпонентных когерентных цветовых векторов, обеспечивающего приемлемую скорость обработки данных и поиска похожих изображений.
Обращает на себя внимание тот факт, что при обилии теоретических материалов и относительной простоте предлагаемых решений, отсутствуют описания алгоритмы и/или исходные коды практически реализующие даже простейшие из предложенных алгоритмов.
Приятным исключением является статья “Простое сравнение изображений с помощью php”.
Приведем авторское описание примененного алгоритма.
• Открываем исходное изображение
• Масштабируем его до размера маски (в моем случае это 20 на 20, большие размеры мне ни к чему – сравнение приблизительное, вполне возможно сделать маску и 10 на 10).
• Вычисляем основной цвет маски.
• Создаем массив, где значением является ключ типа af2 (1,2 — координты, как в морском бою. 2 — расхождение с основной яркостью).
• Генерируем строку – ключ.
• Сравниваем две строки по релевантности.
"Алгоритм возможно не новый, и не является идеалом, но, на удивление, работает. Никаких графов и корелляции".
Выводы.
Первые результаты меня откровенно вдохновили и порадовали !!!
Как оказалось, наибольшую трудность для предложенного алгоритма представляет изменение общего уровня яркости изображения, существенно сдвигающее пики рассчитанных гистограмм.
Необходимо продумывать алгоритмы нормирования яркости изображений.
Публиковать и комментировать исходники в блоге не вижу смысла. Заинтереcовавшиеся могут свободно получить исходники по почте.
