Информационное письмо
Образец оформления статьи
Анкета автора
19.06.2015

Методы на основе цветовых гистограмм в задачах обработки изображений

Парасич Андрей Викторович
аспирант кафедры «Электронные вычислительные машины», факультет «Компьютерные технологии, управление и радиоэлектроника», Южно-Уральский государственный университет г. Челябинск, Россия
Парасич Виктор Александрович
к.т.н., доцент кафедры «Электронные вычислительные машины», факультет «Компьютерные технологии, управление и радиоэлектроника», Южно-Уральский государственный университет г. Челябинск, Россия
Аннотация: Данная статья посвящена вопросам применения цветовых гистограмм в задачах обработки изображений. Приводится обзор методов сравнения гистограмм, даётся анализ преимуществ и недостатков методов на основе гистограмм, описаны методы, помогающие в устранении рассмотренных недостатков. Особое внимание уделяется задаче определения сходства изображений на основе сравнения гистограмм.
Ключевые слова: компьютерное зрение, гистограммы, обработка изображений
Электронная версия
Скачать (586.4 Kb)

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

Цветовая гистограмма — это вектор, в каждой ячейке которого содержится число пикселей изображения или участка изображения, имеющих соответствующий цвет. Часто при построении гистограммы используется цветовое пространство RGB, однако программное обеспечение ряду причин предпочтительнее использовать цветовое пространство HSV. В цветовом пространстве HSV координатами цвета являются: hue ­– цветовой тон (например, красный, зелёный или синий), saturation – насыщенность (чистота цвета), и value – яркость. Данная цветовая модель обладает рядом принципиальных преимуществ. В модели HSV информация о цвете и обработчик освещённости хранится в разных цветовых компонентах, что позволяет повысить инвариантность к освещению. Гистограммы в цветовом пространстве HSV более удобны в использовании. Например, при эквализации гистограммы (преобразовании изображения, после которого его гистограмма содержит все возможные значения яркости, равномерно распределённые на всём диапазоне) требуется скорректировать только яркость пикселей изображения, оставив их цвет без изменений. Использование цветового пространства HSV позволяет добиться устойчивости к затенению изображения, так как затенение не оказывает влияния на компоненту hue.

Методы сравнения гистограмм

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

Корреляционный метод. Похожесть гистограмм рассчитывается по формуле:

Парасич_формула_1.PNG

Возвращаемое значение лежит в интервале [-1; 1], -1 означает максимальное соответствие, 1 – максимальное соответствие, 0 – отсутствие корреляции.

Метрика хи-квадрат. Похожесть гистограмм рассчитывается по формуле:

Метрика хи-квадрат

Возвращаемое значение лежит в интервале [0; неограниченно), 0 означает максимальное соответствие. Значение метрики для случая максимального несоответствия зависит от количества ячеек гистограммы.

Пересечение гистограмм. Сходство гистограмм рассчитывается по формуле:

Пересечение гистограмм

Возвращаемое значение лежит в интервале [0; 1], 1 означает максимальное соответствие, 0 – максимальное соответствие.

Расстояние Бхатачария. Похожесть гистограмм рассчитывается по формуле:

Расстояние Бхатачария

Возвращаемое значение лежит в интервале [0; 1], 0 означает максимальное соответствие, 1 – максимальное соответствие.

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

Недостатки методов на основе сравнения гистограмм

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

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

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

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

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

Ряд методов был предложен для устранения этих недостатков.

EMD(Earth Mover’s Distance) [1]. При изменениях освещенности сцены или интенсивности цветов координаты ячеек гистограммы для одинаковых цветов могут сдвигаться друг относительно друга. В таком случае простое сравнение гистограмм приведёт к некорректным результатам. Для преодоления подобных проблем был разработан алгоритм сравнения гистограмм Earth Mover’s Distance. В данном методе гистограмма (или любое другое вероятностное распределение) представляется в виде набора кластеров {sj = (mj, wj)}. Кластер задаётся средним цветом mj и дисперсией wj. Подобное представление называется сигнатурой распределения. Для определения расстояния между распределениями решается транспортная задача. Для каждой пары кластеров из разных распределений вычисляется стоимость их совмещения, которая зависит от расстояния между кластерами (кластера, соответствующие похожим цветам, будут иметь низкую стоимость совмещения). Требуется найти такое сопоставление пар кластеров, при котором сумма стоимостей совмещения будет минимальна.

Одним из параметров алгоритма является метрика различия кластеров, вместо которой может быть задана матрица стоимости совмещения кластеров. Наилучшую метрику обычно подбирают вручную. В работе [4] был предложен алгоритм обучения метрики совмещения кластеров наподобие SVM. Для некоторых пар гистограмм {p, q} известно, что они относятся к похожим объектам, а для некоторых пар {p, w} известно, что они относятся к различным объектам. Для определения оптимальной метрики решается задача квадратичного программирования, при этом оптимизируемый функционал содержит штрафы за нарушение заданных ограничений похожести гистограмм.

Color constant color indexing [2]. Данный метод был создан для повышения инвариантности методов на основе сравнения гистограмм к изменениям освещённости. Для каждого пикселя вычисляется Лапласиан Гауссиана в окрестности 3 на 3, берутся 4 частные производные по направлениям, каждой из комбинаций значений частных производных соответствует своя ячейка гистограммы. Данный алгоритм более устойчив к изменениям освещения и формы объектов на изображении.

Joint histograms [3].Наряду с цветом используется набор локальных признаков для построения многомерной гистограммы. Каждая ячейка гистограммы содержит число пикселей изображения, описываемых соответствующим набором признаков. В качестве признаков могут использоваться цвет, плотность границ, магнитуда градиента, текстурированность (число пикселей в окрестности, яркость которых отличается от яркости данного пикселя больше, чем на определённую величину) и другие. Преимущество данного подхода состоит в том, что используется е только информация о цветах, но и другая важная информация (о форме, контурах, наличии текстуры).

Histogrambackprojection. Метод для поиска заданного объекта T на изображении Ir. На этапе инициализации строится нормализованная цветовая гистограмма H по изображению It искомого объекта T. На этапе распознавания для каждого пикселя p изображения Ir, на котором мы пытаемся найти интересующий нас объект T, определяется ячейка i гистограммы, соответствующая цвету данного пикселя. Затем значение цвета пикселяp исследуемого изображения Irзаменяется на значение Hi, содержащееся в найденной ячейке гистограммы i. После обработки всех пикселей изображения Irдля поиска заданного объекта T можно воспользоваться алгоритмом кластеризации (например, CamShift), или обнулить те значения пикселей обработанного изображения Ir, которые меньше заданного порога, и затем найти максимальную компоненту связности на полученном изображении. Найденный максимум соответствует наиболее вероятной позиции искомого объекта T на изображении Ir. Также известна версия данного алгоритма под названием patch-based backprojection, в которой с гистограммой искомого объекта сравнивается не отдельный пиксель, а окрестность пикселя в виде прямоугольника (используется метод «скользящего окна»).

Список литературы:

  1. Rubner Y. A metric for distributions with applications to image databases / Y. Rubner, C. Tomasi; L.J. Guibas // Proceedings ICCV – 1998. - Vol. 1– P. 59–66.
  2. Funt B.V. Color constant color indexing / B.V. Funt, G.D. Finlayson // Journal IEEE Transactions on pattern analysis and machine intelligence – 1995. – Vol. 17 – P. 522–529.
  3. Pass G. Comparing images using joint histograms / G. Pass, R. Zabih // Journal Multimedia systems - special issue on video content based retrieval 1999. – Vol. 7 – P. 234 – 240.
  4. Wang F. Supervised Earth Mover's Distance learning and its computer vision applications / F. Wang, L. Guibas // Proceedings ECCV – 2012. - Vol. 1– P. 442-455.