Квантование цветового пространства в контексте решения задачи поиска изображений по содержанию

Введение

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

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

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

Однако во многих случаях, например, при автоматическом получении изображений от автоматизированной системы, ручное аннотирование не представляется возможным. Другим случаем невозможности использования метаданных для решения задачи поиска является их низкое качество: составленное пользователем текстовое описание может не в полной мере отражать характеристики изображенных объектов. В этих случаях применяются методы поиска изображений по содержанию (Content-based image retrieval (CBIR)). Эта группа методов использует непосредственно информацию, закодированную в изображении. Методы поиска по содержанию также могут применяться в смежных областях исследования, таких как автоматизированное аннотирование изображений [1] и их классификация.

Целью работы является:

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

Существующие методы функционирования CBIR-систем

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

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

Методы выделения признаков

Наиболее простым в реализации и распространенным является выделение признаков изображения на основании цветов пикселей [3]. Использование цветов каждого из пикселей в качестве элемента вектора признаков неэффективно: пространство векторов имеет большую размерность, а существующие метрики не будут корректно отражать схожесть исходных изображений. Для снижения размерности применяются гистограммы. Цветовое пространство разбивается на заданное количество областей (происходит его квантование), для каждой из которой определяется процент пикселей изображения, принадлежащих этой области [4].

Квантование цветового пространства может быть фиксировано и осуществлено на этапе разработки метода поиска, или осуществлено алгоритмически, на основании статистики цветов выборки. Сравнительно высокое качество результатов поиска показали методы, использующие квантование, которое принимает во внимание характеристики восприятия цвета человеком, в частности, методы, учитывающие закон Вебера-Фехнера, согласно которому человек воспринимает цвета в виде дискретных значений [2], при этом, если интенсивности цвета x_k и x_{k + 1} определяют границы диапазона различимых цветов, выполняется:

(1)

Кроме вопроса выбора метода квантования встает вопрос выбора самого цветового пространства. Многие исследования показали, что использование пространства цветов RGB является неэффективным в связи с нелинейностью зависимости расстояния между цветами и зрительным восприятием различий. Были разработаны специализированные цветовые пространства, лишенные этого недостатка. Примером такого пространства является CIE L*a*b* (в некоторых источниках — LAB) [3].

Недостатком методов извлечения признаков на основании гистограмм является потеря информации о расположении пикселей или кластеров пикселей заданных цветов.

Другой группой методов, учитывающих локальные зависимости между цветами пикселей являются методы, основанные на текстурных характеристиках изображений. Часто эти методы используются в совокупности с методами на основании цветовых характеристик [5]. Распространен метод на основании локальных бинарных шаблонов [6].

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

Методы поиска в пространстве векторов признаков

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

При решении задачи поиска и классификации изображений используются традиционные функции расстояния, (например, евклидово расстояние, расстояние городских кварталов), функции расстояния, основанные на статистических характеристиках элементов выборки (корреляционный метод, метрика хи-квадрат, расстояния Бхатачария) и функции расстояния, учитывающие специфику алгоритма формирования векторов [8]. Так, например, если в качестве элементов вектора признаков используются значения элементов гистограммы, для сравнения изображений может быть применена метрика EMD (Earth Mover’s Distance), разработанная для обеспечения инвариантности алгоритма к изменению освещенности [9].

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

Результат анализа существующих подходов

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

Поскольку задача поиска изображений должна учитывать особенности восприятия содержимого и оценки схожести изображений человеком, сложна оценка эффективности существующих методов поиска и классификации. Для оценки результатов методов применяются специализированные аннотированные тестовые примеры данных, которые могут не полностью соответствовать предметной области для которой разрабатывается CBIR-система; производится искусственная модификация изображений для тестирования инвариантности алгоритма к перемещению, повороту и другим искажениям, которые могут не соответствовать реальным данным [10]; либо проводится сравнение результатов экспериментов и восприятия путем опроса [3].

Анализ метода k-средних в контексте решения задачи поиска изображений

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

На рисунке 1 показано распределение цветов двух групп изображений в цветовых пространствах RGB, визуализированного в виде куба и HSV, визуализированного в виде конуса (совокупность оттенка и насыщенности была также спроектирована на горизонтальную плоскость для большей наглядности). Распределение было построено на основании оцифрованных копий изображений картин в жанре пейзаж, а также фотографий архитектурных объектов. Для построения были использованы изображения открытой базы данных Web Gallery of Art [12]; было извлечено 5000 точек цветового пространства из 100 изображений этих категорий. Графические файлы, цвета которых являются градациями серого не были включены в выборку.

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

Выбор метода квантования цветового пространства, подразумевает определение такой функции q, которая обращает множество точек цветового пространства U на некоторое конечное множество C — подмножество цветового пространства, заданной длины k:

(2)

При квантовании возникает ошибка, которая зависит от определенной на цветовом пространстве метрики d и плотности распределения p цветов точек изображения [11]:

(3)

Для минимизации ошибки предлагается алгоритм, основанный на разбиении цветового пространства на k подмножеств методом k-средних, входными данными которого является совокупность цветов пикселей всех изображений набора или значительно большой выборки. Метод k-средних обеспечивает минимизацию квадратов отклонений точек кластера от центров этого кластера, а следовательно – и минимизацию ошибки (3).

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

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

Псевдокод предлагаемого алгоритма квантования приведен на рисунке 2.

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

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

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

Оценка эффективности метода квантования

Для проверки эффективности предлагаемого метода было проведено сравнение предлагаемого метода и некоторых существующих методов квантования пространства. Для этого были построены две выборки, содержащие 50 000 цветов, извлеченных из 100 изображений базы данных Web Gallery of Art. Первая выборка была использована для квантования цветового пространства, вторая для вычисления ошибки квантования.

Тестирования проводилось как на всех изображениях БД, так и по изображениям одной из ее категории для проверки адаптируемости алгоритма к специфике изображений некоторой предметной области. Тестирование проводилось на нормированном цветовом пространстве RGB и HSV.

Для вычисления ошибки квантования была использована формула, полученная при приведении (3) к дискретному виду:

(4)

В качестве функции расстояния в пространстве RGB была использована евклидова метрика:

(5)

В пространстве HSV была использована метрика, полученная при переводе координат из цилиндрической системы HSV в декартову и представлении пространства в виде конуса:

(6)

На практике также можно использовать следующую метрику на пространстве HSV, требующую меньших вычислительных затрат:

(7)

Результаты тестирования эффективности алгоритма: ошибка, рассчитанная по формуле (4) и дисперсия отклонений цвета и результата квантования приведена в табл. 1. При тестировании значение k принималось равным 64. Приведенный в табл. 1 алгоритм линейного разбиения осуществляет разбиение пространства плоскостями, параллельными осям: в пространстве RGB производится интервала [0; 1] на 4 равные части по каждой из осей; в пространстве HSV интервал [0; 1] насыщенности и значения разбивается на 2 и 4 равные интервала соответственно, диапазон насыщенности [0; 2π) разбивается на 8 равных интервалов. Тестирование алгоритма Median cut в пространстве HSV не производилось из-за специфики работы алгоритма.

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

Заключение

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

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

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

Литература

1. Li J. Real-Time Computerized Annotation of Pictures / J. Li, J. Z. Wang // IEEE Transactions on Pattern Analysis and Machine Intelligence. — 2008. — Т. 30. — № 6. — С. 985–1002.
2. Image retrieval: ideas, influences, and trends of the new age / Datta R. [et al.] // Acm Computing Surveys. — 2008. — № 2 (40).
3. Mojsilovic A. A method for color content matching of images / A. Mojsilovic, J. Hu // 2000 IEEE International Conference on Multimedia and Expo. ICME2000. Proceedings. Latest Advances in the Fast Changing World of Multimedia (Cat. No.00TH8532). — 2000. — Т. 2. — С. 649–652.
4. The QBIC Project: Querying Images by Content Using Color, Texture, and Shape. The QBIC Project / T.J.W.I.R. Center [et al.] — IBM Thomas J. Watson Research Division, 1993. — 20 p.
5. Mäenpää T. Classification with color and texture: jointly or separately? / T. Mäenpää, M. Pietikäinen // Pattern Recognition. — 2004. — Т. 37. — Classification with color and texture. — № 8. — С. 1629–1640.
6. A comparative study of texture measures with classification based on feature distributions / M. Pietikainen [et al.] // Pattern Recognition. — 1996. — Т. 29. — С. 51–59.
7. Vasconcelos N. A unifying view of image similarity / N. Vasconcelos, A. Lippman // Proceedings 15th International Conference on Pattern Recognition. ICPR-2000. — 2000. — Т. 1. — С. 38–41.
8. Парасич А.В. Методы на основе цветовых гистограмм в задачах обработки изображений / А.В. Парасич, В.А. Парасич // Nauka-rastudent.ru. — 2015. — № 06 (18) / [Электронный ресурс] — Режим доступа. — URL: http://nauka-rastudent.ru/18/2742/
9. Rubner Y. A metric for distributions with applications to image databases / Y. Rubner, C. Tomasi, L.J. Guibas // Sixth International Conference on Computer Vision (IEEE Cat. No.98CH36271). — 1998. — С. 59–66.
10. Stricker M. Spectral covariance and fuzzy regions for image indexing / M. Stricker, A. Dimai // Machine Vision and Applications. — 1997. — Vol. 10. — № 2. — P. 66–73.
11. Mota C. Optimal image quantization, perception and the median cut algorithm / C. Mota, J. Gomes, M.I.A. Cavalcante // Anais da Academia Brasileira de Ciências. — 2001. — Т. 73. — № 3. — С. 303–317.
12. Web Gallery of Art, searchable fine arts image database [Электронный ресурс]. — URL: https://www.wga.hu/index.html (дата обращения: 26.10.2018).