Назад в библиотеку

---

К оценке эффективности поиска изображений с использованием 2d-цветовых гистограмм

Автор: Башков Е.А., Костюкова Н.С.
Источник: Проблемы управления и информатики //№6, 2006. с.84-89

Аннотация

Є.О.Башков, Н.С.Костюкова. До оцінки ефективності пошуку зображень з використанням 2D-колірних гістограм. В роботі в загальному вигляді формулюється задача пошуку в базі даних зображень за зразком, розглядаються характеристики, що описують колірний вміст зображення, вводиться нова характеристика колірного вмісту зображення – 2D-колірна гістограма, аналізується якість пошуку при використанні запропонованої характеристики.

E.A. Bashkov, N.S. Kostyukova. For the estimation of image retrieval used 2D-color histogram effectiveness. This article deals with content-based image retrieval. The task of image retrieval by pattern is described, color features of image are analized. Also a new characteristic of image color content, named 2D-color histogram, is proposed.

Введение

Развитие информационных технологий, компьютерных сетей и в особенности Интернет привели к накоплению большого количества оцифрованных изображений произвольного содержания. Для таких коллекций, особенно состоящих из изображений произвольного содержимого, актуальна задача поиска по образцу, когда необходимо сформировать набор изображений из коллекции, визуально подобных заданному. Поиск изображений является отдельным сегментом поискового рынка в Интернет. По данным Интернет-публикаций [1], за последний год количество поисковых запросов, связанных с поиском изображений, увеличилось на 91% и составило 6,8% от всего количества поисковых запросов. Существует ряд практически реализованных программных комплексов, выполняющих поиск по содержимому изображений (иначе называемый контекстным поиском). Наиболее удачными являются система QBIC (разработка фирмы IBM) [2], и системы WebSeek и VisualSeek (разработка Колумбийского университета, США) [3, 4]. Поиск изображений по их содержимому с использованием технологии IBM реализован также на сайте Государственного Эрмитажа (Россия) [5]. Главным недостатком всех практических реализаций этого подхода является замена поиска сортировкой всей БД по убыванию сходства с образцом, и, как следствие, низкое быстродействие и невозможность получения ответа на запрос в реальном масштабе времени. Поэтому необходима разработка усовершенствованных алгоритмов для сокращения времени и улучшения качества поиска. В статье в общем виде формулируется задача поиска по образцу, рассматриваются характеристики, описывающие цветовое содержимое изображения, вводится новая характеристика цветового содержимого – 2D-цветовая гистограмма, анализируется качество поиска при использовании данной характеристики.

1. Задача поиска изображений на основе их цветового содержимого

В общем виде задача поиска в базе данных изображений, похожих на заданное, формулируется следующим образом [9, 10, 11].

Пусть имеется база данных, содержащая информацию о V не сжатых изображениях

где P={Pk, k=1, 2,..V} – множество изображений (матриц M*N, элементы которых хранят цвета пикселей изображения; M и N – ширина и высота изображения соответственно), F={Fk, k=1, 2,..V} – множество характеристик содержимого изображений (Fk – скаляр либо вектор).

Задан образец поиска P_ОБР – изображение, содержимое котрого описывается характеристикой F_ОБР. Для образца поиска Р_ОБР и любого изображения Р_k может быть вычислена степень сходства их содержимого:

Требуется определить множество изображений Q, сходных с образцом и расположенных в порядке убывания этого сходства:

Таким образом, задача контекстного поиска сводится к вычислению значений d_k, k=1,2,..V, и их последующей сортировке. При этом вычисление характеристик F содержимого изображений выполняется при занесении этих изображений в базу данных, где они и сохраняются.

2. Поиск изображений на основе их содержимого в графических базах данных

Применяемые в современных поисковых системах характеристики содержимого изображений могут быть разделены на две группы. К первой из этих групп относятся точечные оценки, например, средний цвет точки, наиболее яркий цвет, преобладающий цвет. Характеристики, образующие вторую группу, можно назвать характеристиками распределений; их примерами являются цветовые и текстурные гистограммы [6], кумулятивные гистограммы [7], цветовые коррелограммы [8]. Цветовая гистограмма отражает распределение цветов внутри изображения, текстурная характеризует распределение соотношений яркости в окрестности точки. При использовании гистограммных признаков их построению предшествует этап квантования цветов или уровней яркости (иначе говоря, их приведение к некоторому заранее определенному базовому набору цветов либо яркостей). Данный этап является обязательным, при его отсутствии сравнение характеристик содержимого изображений бессмысленно. Для вычисления степени сходства изображений, как правило, используют евклидово расстояние, конъюнкцию гистограмм, косинусное либо квадратичное расстояния [6]. Показано [9], что любая из этих величин сама по себе не отражает степень сходства двух изображений и имеет смысл только при сравнении с другими аналогичными величинами. Именно по этой причине все практические реализации контекстного поиска изображений выполняют сортировку всех изображений из базы данных, что является главным недостатком этих реализаций.

В процессе контекстного поиска изображений последовательно выполняется ряд этапов:

• Q – квантование цветов либо уровней яркости (quantization);
• H – построение гистограммного признака содержимого изображения (histogram);
• C – сравнение изображений (comparison);
• S – сортировка изображений (sorting).

Последовательность их выполнения при различных режимах работы поисковой системы изображена на рисунке 1. Для преодоления недостатков, присущих имеющимся алгоритмам, в вычислительный процесс поиска изображений внесены некоторые модификации на этапах Н и С [9, 10]. В частности, для представления цветового содержимого изображения предлагается [10, 11] строить гистограмму, аналогичную текстурной, но учитывать соотношение цветов пар пикселей (а не только яркостную составляющую). Построенную таким образом характеристику содержимого изображения будем называть двумерной цветовой гистограммой (2D-цветовой гистограммой). Можно ожидать, что использование такой характеристики будет особенно эффективным для цветных изображений, обладающих следующими свойствами: с одной стороны, их содержимое можно назвать произвольным, с другой стороны, рисунок характеризуется определенной повторяемостью. Примером таких изображений являются образцы тканей, обоев и т.п., а также изображения цветных текстур. Очевидно, что для сравнения таких изображений следует в равной мере учитывать как пространственное распределение цветов, так и информацию о локальном распределении цветов пикселей.

С учетом пространственной природы содержимого рассматриваемых изображений 2D-цветовая гистограмма строится как двумерный массив Cmax*Cmax, где Cmax – число цветов базового набора, использовавшегося на этапе квантования цветов. Каждый элемент такой гистограммы равен количеству пар пикселей с заданным соотношением цветов в окрестности точки (для заданного шаблона).

Рассмотрим более подробно алгоритм построения 2D-цветовой гистограммы. Каждая из M*N точек изображения сравнивается с k точками шаблона, и в процессе этого сравнения увеличиваются на единицу k элементов 2D-цветовой гистограммы. Таким образом, после обработки всего изображения сумма элементов 2D-цветовой гистограммы будет равна k*M*N, а каждый ее элемент будет равен количеству пар точек с заданным соотношением цветов. Далее, выполним нормирование элементов, разделив значение каждого на количество пар точек изображения, что позволит нам сравнивать 2D-цветовые гистограммы, построенные для изображений различных размеров. Построение 2D-цветовой гистограммы по такому алгоритму означает, что каждый ее элемент H[i,j] представляет собой вероятность присутствия в изображении пары точек с цветами c[i] и c[j]. Если цветовое пространство, для которого выполнялось построение базового набора цветов c [1..Cmax], обладает свойством полноты, то, очевидно,

Данная характеристика представляет собой матрицу, каждый элемент которой хранит нормированное количество пар пикселей с цветами, соответствующими индексам элемента, в окрестности каждой точки. Для сравнения 2D-цветовых гистограмм изображений предлагается вычислять коэффициент их корреляции [10], так как 2D-цветовая гистограмма, построенная по алгоритму, описанному выше, является случайным вектором размерности Cmax² (или, другими словами, многомерной случайной величиной). Учитывая свойства коэффициента корреляции, при формировании набора результирующих изображений их следует размещать в порядке убывания коэффициента.

3. Оценка качества поиска изображений.

Для проверки работоспособности алгоритма использовалась база данных, содержащая разнообразные изображения: пейзажи, цветы, животные, образцы обоев и т.п. Состав этой базы данных показан в виде диаграммы на рис.2. В ходе экспериментов выполнялся поиск как с использованием традиционных цветовых гистограмм, так и 2D-цветовых гистограмм.

Для сравнения характеристик содержимого изображения использовались как общепринятые величины (евклидово, косинусное расстояние, конъюнкция цветовых гистограмм), так и коэффициент корреляции 2D-цветовых гистограмм. Во всех случаях при построении цветовых гистограмм выполнялось равномерное квантование в RGB-пространстве до 64 цветов. Оценка качества поиска осуществлялась путем вычисления величин, предложенных в [6], характеризующих долю изображений, похожих на образец, среди всех найденных (P), и долю найденных изображений, похожих на образец, среди всех изображений в базе данных, которые похожи на этот же образец (R):

где
a – количество найденных подходящих изображений;
b – количество найденных неподходящих изображений;
c – количество ненайденных подходящих изображений.

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

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

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

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

В базу данных, на которой тестировался алгоритм, целенаправленно включены группы изображений, визуально схожих между собой. Далее каждую такую группу изображений будем называть семейством. Результирующий набор изображений ограничивался мощностью наибольшего семейства базы данных, а не произвольной константой (5, 10, 20 и т.п.), как в других публикациях, например, [6]. В результате были получены характеристики качества поиска, представленные на рисунке 3. Из рисунка видно, что использование 2D-цветовых гистограмм позволяет получить результаты, более близкие к идеальному значению, чем при использовании традиционных цветовых гистограмм, то есть качество поиска за счет данной модификации алгоритма улучшается

Вторая серия экспериментов выполнялась при ограничении результирующего набора определенным значением коэффициента корреляции, начиная с единицы с шагом 0,1. Полученные таким образом кривые представлены на рисунках 4 и 5, где по горизонтальной оси откладывалось ограничивающее результаты значение коэффициента корреляции. Анализ кривых показывает преимущество использования 2D-цветовых гистограмм. При тестировании на рассмотренном наборе изображений максимальное преимущество характеристики P составило 3,44 раза, а среднее преимущество той же характеристики – 2, 33 раза. Для характеристики R эти значения равны соответственно 1, 17 и 1,1.

Выводы.

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

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

1. Ализар А. Google и «Яндекс» контролируют поиск изображений. http://www.izcity.com/ izone21.htm
2. IBM Almaden Research Center. Query by Image and Video Content: the QBIC System// IEEE Computer. – September, 1995. – Pp.23-31.
3. R. Smith and S.-F. Chang, "Searching for Images and Videos on the World-Wide Web," to appear in IEEE Multimedia Magazine, Summer, 1997. (also Columbia University CU/CTR Technical Report #459-96-25). Demo: http://www.ctr.columbia.edu/webseek
4. J. R. Smith and S.-F. Chang, "VisualSEEk: A Fully Automated Content-Based Image Query System,"// ACM Multimedia Conference, Boston, MA. – Nov., 1996. Demo: http://www.ctr.columbia.edu/VisualSEEk
5. Цифровая коллекция Эрмитажа: http://www.hermitagemuseum.org
6. John R. Smith Integrated Spatial and Feature Image Systems: Retrieval, Analysis and Compression. Submitted in partial fulfillment of the requirements for the degree of Doctor of Philosophy in the Graduate School of Arts and Sciences, Columbia University, 1997. http://disney.ctr.columbia.edu/jrsthesis/node1.html
7. M.Striker, M. Orengo. Similarity of Color Images. SPIE vol.2420, N1, pp.381-392, 1995.
8. J. Huang. Color Spatial Image Indexing and Application. a Dissertation Presented to the Faculty of the Graduate School of Cornell University to Partial Fulfillment of the Requirements for the Degree of Doctor of Philosophy, 1998.
9. Башков Е.А., Шозда Н.С. Поиск изображений в больших БД с использованием коэффициента корреляции цветовых гистограмм.// Труды 12-й Международной конференции ГрафиКон’2002. – Нижний Новгород, 2002. – стр. 358–361 12-я Международная конференция по компьютерной графике и машинному зрению ГрафиКон’2002. Нижний Новгород (Россия), 16-21 сентября 2002г.
10. Костюкова Н.С. Использование 2D- цветовых гистограмм для представления цветового содержимого изображений. // Материалы всероссийской научно- технической конференции с международным участием «Компьютерные и информационные технологии в науке, инженерии и управлении». Известия ТРТУ №1. Тематический выпуск «Компьютерные и информационные технологии в науке, инженерии и управлении». – Таганрог: ТРТУ, – 2005. – С.74-78.
11. Костюкова Н.С. Оценка эффективности поиска изображений. Наукові праці Донецького національного технічного університету. Серія: "Інформатика, кібернетика та обчислювальна техніка". Випуск 93. Донецьк, 2005.С. 22-32