К оценке эффективности поиска изображений с использованием 2D-цветовых гистограмм
В загальному вигляді сформульовано задачу пошуку в базі даних зображень за зразком, розглянуто характеристики, що описують колірний вміст зображення, введено нову характеристику колірного вмісту зображення — 2D-колірну гістограму, проаналізовано якість пошуку при використанні запропонованої характе...
Збережено в:
| Дата: | 2006 |
|---|---|
| Автори: | , |
| Формат: | Стаття |
| Мова: | Russian |
| Опубліковано: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2006
|
| Назва видання: | Проблемы управления и информатики |
| Теми: | |
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/206936 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | К оценке эффективности поиска изображений с использованием 2D-цветовых гистограмм / Е.А. Башков, Н.С. Костюкова // Проблемы управления и информатики. — 2006. — № 6. — С. 84-89. — Бібліогр.: 11 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-206936 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-2069362025-09-27T00:08:11Z К оценке эффективности поиска изображений с использованием 2D-цветовых гистограмм До оцінки ефективності пошуку зображень з використанням 2D-колірних гістограм On the estimation of image retrieval effectiveness using 2D-color histogramms Башков, Е.А. Костюкова, Н.С. Методы обработки и защиты информации В загальному вигляді сформульовано задачу пошуку в базі даних зображень за зразком, розглянуто характеристики, що описують колірний вміст зображення, введено нову характеристику колірного вмісту зображення — 2D-колірну гістограму, проаналізовано якість пошуку при використанні запропонованої характеристики. The problem of image retrieval in image data base by pattern is formulated in general. Color features of image are analyzed. Also a new characteristic of image color content, is introduced what is termed 2D color histogram. 2006 Article К оценке эффективности поиска изображений с использованием 2D-цветовых гистограмм / Е.А. Башков, Н.С. Костюкова // Проблемы управления и информатики. — 2006. — № 6. — С. 84-89. — Бібліогр.: 11 назв. — рос. 0572-2691 https://nasplib.isofts.kiev.ua/handle/123456789/206936 681.3 ru Проблемы управления и информатики application/pdf Інститут кібернетики ім. В.М. Глушкова НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
Russian |
| topic |
Методы обработки и защиты информации Методы обработки и защиты информации |
| spellingShingle |
Методы обработки и защиты информации Методы обработки и защиты информации Башков, Е.А. Костюкова, Н.С. К оценке эффективности поиска изображений с использованием 2D-цветовых гистограмм Проблемы управления и информатики |
| description |
В загальному вигляді сформульовано задачу пошуку в базі даних зображень за зразком, розглянуто характеристики, що описують колірний вміст зображення, введено нову характеристику колірного вмісту зображення — 2D-колірну гістограму, проаналізовано якість пошуку при використанні запропонованої характеристики. |
| format |
Article |
| author |
Башков, Е.А. Костюкова, Н.С. |
| author_facet |
Башков, Е.А. Костюкова, Н.С. |
| author_sort |
Башков, Е.А. |
| title |
К оценке эффективности поиска изображений с использованием 2D-цветовых гистограмм |
| title_short |
К оценке эффективности поиска изображений с использованием 2D-цветовых гистограмм |
| title_full |
К оценке эффективности поиска изображений с использованием 2D-цветовых гистограмм |
| title_fullStr |
К оценке эффективности поиска изображений с использованием 2D-цветовых гистограмм |
| title_full_unstemmed |
К оценке эффективности поиска изображений с использованием 2D-цветовых гистограмм |
| title_sort |
к оценке эффективности поиска изображений с использованием 2d-цветовых гистограмм |
| publisher |
Інститут кібернетики ім. В.М. Глушкова НАН України |
| publishDate |
2006 |
| topic_facet |
Методы обработки и защиты информации |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/206936 |
| citation_txt |
К оценке эффективности поиска изображений с использованием 2D-цветовых гистограмм / Е.А. Башков, Н.С. Костюкова // Проблемы управления и информатики. — 2006. — № 6. — С. 84-89. — Бібліогр.: 11 назв. — рос. |
| series |
Проблемы управления и информатики |
| work_keys_str_mv |
AT baškovea kocenkeéffektivnostipoiskaizobraženijsispolʹzovaniem2dcvetovyhgistogramm AT kostûkovans kocenkeéffektivnostipoiskaizobraženijsispolʹzovaniem2dcvetovyhgistogramm AT baškovea doocínkiefektivnostípošukuzobraženʹzvikoristannâm2dkolírnihgístogram AT kostûkovans doocínkiefektivnostípošukuzobraženʹzvikoristannâm2dkolírnihgístogram AT baškovea ontheestimationofimageretrievaleffectivenessusing2dcolorhistogramms AT kostûkovans ontheestimationofimageretrievaleffectivenessusing2dcolorhistogramms |
| first_indexed |
2025-09-27T01:17:50Z |
| last_indexed |
2025-09-28T01:13:54Z |
| _version_ |
1844468288438927360 |
| fulltext |
© Е.А. БАШКОВ, Н.С. КОСТЮКОВА, 2006
84 ISSN 0572-2691
УДК 681.3
Е.А. Башков, Н.С. Костюкова
К ОЦЕНКЕ ЭФФЕКТИВНОСТИ ПОИСКА
ИЗОБРАЖЕНИЙ С ИСПОЛЬЗОВАНИЕМ
2D-ЦВЕТОВЫХ ГИСТОГРАММ
Введение. Развитие информационных технологий, компьютерных сетей и в
особенности Интернета привело к накоплению большого количества оцифрован-
ных изображений произвольного содержания. Для таких коллекций, особенно со-
стоящих из изображений произвольного содержания, актуальна задача поиска по
образцу, когда необходимо сформировать набор изображений из коллекции, визу-
ально подобных заданному. Поиск изображений представляет собой отдельный
сегмент поискового рынка в Интернете. По данным Интернет-публикаций [1], за
последний год количество поисковых запросов, связанных с поиском изображе-
ний, увеличилось на 91 % и составило 6,8 % общего количества поисковых запро-
сов. Существует ряд практически реализованных программных комплексов, вы-
полняющих поиск по содержимому изображений (т.е. контекстный поиск).
Наиболее удачны система QBIC (разработка фирмы IBM) [2] и системы WebSeek
и VisualSeek (разработка Колумбийского университета, США) [3, 4]. Поиск изоб-
ражений по их содержимому с использованием технологии IBM реализован также
на сайте Государственного Эрмитажа (Россия) [5]. Главный недостаток всех прак-
тических реализаций этого подхода заключается в замене поиска сортировкой
всей базы данных (БД) по убыванию сходства с образцом и, как следствие, в низ-
ком быстродействии и невозможности получения ответа на запрос в реальном
масштабе времени. Поэтому необходима разработка усовершенствованных алго-
ритмов для сокращения времени и улучшения качества поиска.
1. Задача поиска изображений на основе их цветового содержимого .
В общем виде задача поиска в базе данных изображений, похожих на заданное,
формулируется следующим образом [6–8].
Пусть имеется база данных, содержащая информацию о V несжатых изобра-
жениях
},,{ FPS =
где }...,,2,1,{ VkPP k == — множество изображений (матриц ,NM элементы
которых хранят цвета пикселов изображения; M и N — ширина и высота изобра-
жения соответственно); }...,,2,1,{ VkFF k == — множество характеристик со-
держимого изображений kF( — скаляр или вектор).
Задан образец поиска specP — изображение, содержимое котрого описывает-
ся характеристикой .specF Для образца поиска specP и любого изображения kP
может быть вычислена степень сходства их содержимого:
....,,2,1),,( spec VkFFfd kk ==
Требуется определить множество изображений Q, сходных с образцом и рас-
положенных в порядке убывания этого сходства:
}.:...,2,1,{
2121 iii ddiiiPQ ==
Таким образом, задача контекстного поиска сводится к вычислению значений
,...,,2,1, Vkdk = и их последующей сортировке. При этом вычисление характе-
ристик F содержимого изображений выполняется при занесении этих изображе-
ний в базу данных, где они и сохраняются.
Проблемы управления и информатики, 2006, № 6 85
2. Поиск изображений на основе их содержимого в графических базах
данных. Применяемые в современных поисковых системах характеристики со-
держимого изображений могут быть разделены на две группы. К первой из этих
групп относятся точечные оценки, например средний цвет точки, наиболее яркий
цвет, преобладающий цвет. Характеристики, образующие вторую группу, можно
назвать характеристиками распределений; их примером служат цветовые и тек-
стурные гистограммы [9], кумулятивные гистограммы [10], цветовые коррело-
граммы [11]. Цветовая гистограмма отражает распределение цветов внутри изоб-
ражения, текстурная характеризует распределение соотношений яркости в
окрестности точки. При использовании гистограммных признаков их построению
предшествует этап квантования цветов или уровней яркости (иначе говоря, их
приведение к некоторому заранее определенному базовому набору цветов либо
яркостей). Данный этап обязателен, без него сравнение характеристик содержи-
мого изображений бессмысленно. Для вычисления степени сходства изображе-
ний, как правило, используют евклидово расстояние, конъюнкцию гистограмм,
косинусное либо квадратичное расстояние [9]. Показано [6], что любая из этих
величин сама по себе не отражает степень сходства двух изображений и имеет
смысл только при сравнении с другими аналогичными величинами. Именно по
этой причине все практические реализации контекстного поиска изображений
выполняют сортировку всех изображений из базы данных, что представляет собой
главный недостаток этих реализаций.
В процессе контекстного поиска изображений последовательно выполняется
ряд этапов:
1) Q — квантование цветов либо уровней яркости (quantization);
2) H — построение гистограммного признака содержимого изображения
(histogram);
3) C — сравнение изображений (comparison);
4) S — сортировка изображений (sorting).
Последовательность их выполнения при различных режимах работы поиско-
вой системы изображена на рис. 1. Для преодоления недостатков, свойственных
существующим алгоритмам, в вычислительный процесс поиска изображений вне-
сены некоторые модификации на этапах Н и С [6, 7]. В частности, для представ-
ления цветового содержимого изображения предлагается [7, 8] строить гисто-
грамму, аналогичную текстурной, но
учитывать соотношение цветов пар пик-
селов (а не только яркостную составля-
ющую). Построенную таким образом
характеристику содержимого изображе-
ния будем называть двумерной цвето-
вой гистограммой (2D-цветовой гисто-
граммой). Можно ожидать, что исполь-
зование такой характеристики будет
особенно эффективным для цветных
изображений, обладающих следующи-
ми свойствами: с одной стороны, их со-
держимое произвольно, а с другой —
рисунок характеризуется определенной повторяемостью. Примеры таких изобра-
жений — образцы тканей, обоев и т.п., а также изображения цветных текстур.
Очевидно, что для сравнения таких изображений следует в равной мере учиты-
вать как пространственное распределение цветов, так и информацию о локальном
распределении цветов пикселов.
Q, H
БД
характеристик
БД
изображений
S Визуализация
Занесение изображений в БД
Поиск по образцу
C
Рис. 1
86 ISSN 0572-2691
С учетом пространственной природы содержимого рассматриваемых изобра-
жений 2D-цветовая гистограмма строится как двумерный массив ,maxmax CC
где maxC — количество цветов базового набора, используемого на этапе кванто-
вания цветов. Каждый элемент такой гистограммы равен количеству пар пикселов
с заданным соотношением цветов в окрестности точки (для заданного шаблона).
Рассмотрим более подробно алгоритм построения 2D-цветовой гистограммы.
Каждая из NM точек изображения сравнивается с k точками шаблона, и в про-
цессе этого сравнения увеличиваются на единицу k элементов 2D-цветовой гисто-
граммы. Таким образом, после обработки всего изображения сумма элементов
2D-цветовой гистограммы равна ,NMk а каждый ее элемент равен количеству
пар точек с заданным соотношением цветов. Далее выполним нормирование эле-
ментов, разделив значение каждого на количество пар точек изображения, что
позволит нам сравнивать 2D-цветовые гистограммы, построенные для изображе-
ний различных размеров. Построение 2D-цветовой гистограммы по такому алго-
ритму означает, что каждый ее элемент ],[ jiH представляет собой вероятность
присутствия в изображении пары точек с цветами ][ic и ].[ jc Если цветовое про-
странство, для которого выполнялось построение базового набора цветов
]),...1[( maxCc обладает свойством полноты, то очевидно, что .1],[
max max
1 1
= =
=
C
i
C
j
jiH
Данная характеристика представляет собой матрицу, каждый элемент которой
хранит нормированное количество пар пикселов с цветами, соответствующими ин-
дексам элемента, в окрестности каждой точки. Для сравнения 2D-цветовых гисто-
грамм изображений предлагается вычислять коэффициент их корреляции [7], так
как 2D-цветовая гистограмма, построенная по описанному алгоритму, — случай-
ный вектор размерности 2
maxC (или, другими словами, многомерная случайная
величина). Учитывая свойства коэффициента корреляции, при формировании
набора результирующих изображений их следует размещать в порядке убывания
коэффициента.
3. Оценка качества поиска изображений. Для проверки работоспособности
алгоритма использована БД, содержащая разнообразные изображения: образцы
обоев, пейзажи, изображения цветов, животных и т.п. Состав этой БД показан в
виде диаграммы на рис. 2. В ходе экспериментов выполнялся поиск с использова-
нием как традиционных цветовых гистограмм, так и 2D-цветовых гистограмм.
48
47
34
25
11
6 3
98
Образцы обоев
Контрастные рисунки
Изображения животных
Изображения цветов и фруктов
Пейзажи
Подводные фото
Абстракции
Изображения автомобилей
47
48
98
Рис. 2
Проблемы управления и информатики, 2006, № 6 87
Для сравнения характеристик содержимого изображения использовались и
общепринятые величины (евклидово, косинусное расстояние, конъюнкция цвето-
вых гистограмм), и коэффициент корреляции 2D-цветовых гистограмм. Во всех
случаях при построении цветовых гистограмм выполнялось равномерное кванто-
вание в RGB-пространстве до 64 цветов. Качество поиска оценивалось путем вы-
числения величин, предложенных в [9], которые определяют долю изображений,
похожих на образец, среди всех найденных (P), и долю найденных изображений,
похожих на образец, среди всех изображений в БД, которые похожи на этот же
образец:
,,
ca
a
R
ba
a
P
+
=
+
=
где R — образец; a — количество найденных подходящих изображений; b — ко-
личество найденных неподходящих изображений; c — количество ненайденных
подходящих изображений.
Очевидно, что для эффективного алгоритма значения этих характеристик
должны быть как можно ближе к единице и из двух алгоритмов при прочих рав-
ных условиях следует выбирать тот, для которого указанные характеристики
имеют бóльшие значения.
Экспериментам по оценке предложенного алгоритма предшествовал предва-
рительный анализ всех изображений в БД. В ходе этого анализа каждое изобра-
жение сравнивалось с остальными с целью установления визуального сходства
между ними. Таким образом, была выполнена предварительная разметка всей БД
изображений и сформирована матрица подобия ,][ VVM значения элементов ко-
торой определяются следующим образом:
−−
=
иначе.0
;е-напохожееизображение-если,1
],[
ij
jiM
Следует отметить, что указанная разметка не имеет отношения к процессу
поиска изображения и использована нами только для получения значений число-
вых характеристик качества поиска при сравнении алгоритмов.
Каждое из изображений, содержащихся в БД, поочередно использовалось как
образец поиска; после каждого такого цикла поиска рассчитывались значения ха-
рактеристик качества поиска. Для анализа эффективности алгоритма используют-
ся средние значения указанных характеристик, вычисляемые после того, как все
изображения, содержащиеся в БД, были использованы в качестве образца.
В БД, на которой тестировался алгоритм, целенаправленно включены группы
изображений, визуально схожих между собой. Далее каждую такую группу изоб-
ражений будем называть семейством. Результирующий набор изображений огра-
ничен мощностью наибольшего семейства базы данных, а не произвольной кон-
стантой (5, 10, 20 и т.п.), как в других публикациях (например, [9]). В результате
получены характеристики качества поиска, представленные на рис. 3. Из этого
рисунка видно, что использование 2D-цветовых гистограмм позволяет получить
результаты, более близкие к идеальному значению, чем при использовании тра-
диционных цветовых гистограмм, т.е. качество поиска за счет предложенной мо-
дификации алгоритма улучшается.
Во второй серии экспериментов результирующий набор ограничен опреде-
ленным значением коэффициента корреляции, начиная с единицы, с шагом 0,1.
Полученные таким образом кривые представлены на рис. 4 и 5, где по горизон-
тальной оси откладывалось ограничивающее результаты значение коэффициента
корреляции. Анализ кривых показывает преимущество использования 2D-цве-
товых гистограмм. При тестировании на рассмотренном наборе изображений
88 ISSN 0572-2691
максимальное преимущество характеристики P составило 3,44 раза, а среднее
преимущество той же характеристики — 2,33 раза. Для характеристики R эти зна-
чения равны соответственно 1,17 и 1,1.
0
0,1
0,2
0,3
0,4
0,5
0,6
0,7
0,8
0,9
1
0 0,1 0,2 0,3 0,4 0,5 0,6 0,7 0,8 0,9 1
2D-цветовые гистограммы Традиционные цветовые гистограммы
P
R
Рис. 3
0
0,1
0,2
0,3
0,4
0,5
0,6
0,7
0,8
0,9
1
1 0,8 0,6 0,4 0,2 0 – 0,2 – 0,4 – 0,6 – 0,8 – 1
2D-цветовые гистограммы Традиционные цветовые гистограммы
P
Рис. 4
0,5
0,6
0,7
0,8
0,9
1
1 0,8 0,6 0,4 0,2 0 – 0,2 – 0,4 – 0,6 – 0,8 – 1
2D-цветовые гистограммы Традиционные цветовые гистограммы
R
Рис. 5
Проблемы управления и информатики, 2006, № 6 89
Таким образом, анализ результатов поиска при использовании 2D-цветовой
гистограммы свидетельствует о более высоком его качестве по сравнению с при-
менением традиционных цветовых гистограмм.
Є.О. Башков, Н.С. Костюкова
ДО ОЦІНКИ ЕФЕКТИВНОСТІ ПОШУКУ
ЗОБРАЖЕНЬ З ВИКОРИСТАННЯМ
2D-КОЛІРНИХ ГІСТОГРАМ
В загальному вигляді сформульовано задачу пошуку в базі даних зображень за
зразком, розглянуто характеристики, що описують колірний вміст зображення,
введено нову характеристику колірного вмісту зображення — 2D-колірну гіс-
тограму, проаналізовано якість пошуку при використанні запропонованої ха-
рактеристики.
E.A. Bashkov, N.S. Kostyukova
ON THE ESTIMATION OF IMAGE RETRIEVAL
EFFECTIVENESS USING 2D-COLOR HISTOGRAMS
The problem of image retrieval in image data base by pattern is formulated in gen-
eral. Color features of image are analyzed. Also a new characteristic of image color
content, is introduced what is termed 2D-color histogram.
1. Ализар А. Google и «Яндекс» контролируют поиск изображений. — http://www.izcity.com
izone21.htm.
2. IBM Almaden research center. query by image and video content: the QBIC system // IEEE
Computer. — 1995. — N 9. — P. 23–31.
3. Smith R., Chang S.-F. 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. Smith J.R., Chang S.-F. 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. Башков Е.А., Шозда Н.С. Поиск изображений в больших БД с использованием коэффици-
ента корреляции цветовых гистограмм // Тр. 12-й Международной конференции Гра-
фиКон’2002. Нижний Новгород (Россия), 16–21 сентября 2002 г. — Нижний Новгород, 2002.
— C. 358–361.
7. Костюкова Н.С. Использование 2D-цветовых гистограмм для представления цветового со-
держимого изображений // Мат-лы Всероссийской научно-технической конференции с меж-
дународным участием «Компьютерные и информационные технологии в науке, инженерии и
управлении». Изв. ТРТУ. Тематический выпуск «Компьютерные и информационные техно-
логии в науке, инженерии и управлении». — Таганрог : ТРТУ. — 2005. — С. 74–78.
8. Костюкова Н.С. Оценка эффективности поиска изображений // Наук. пр. Донецького
національного технічного університету. Сер. Інформатика, кібернетика та обчислювальна
техніка. — 2005. — Вип. 93. — С. 22–32.
9. Smith J.R. 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).
10. Striker M., Orengo M. Similarity of color images // SPIE. — 1995. — 2420, N 1. — P. 381–392.
11. Image indexing using color correlograms / J. Huang, S.R. Kumar, M. Mitra, Zhu Wei-Jing,
R. Zabih // Proc. of IEEE Computer Society Conference on Computer Vision and Pattern Recog-
nition. — 1997. — P. 762–768.
Получено 11.09.2006
http://www.izcity.com/
http://www.ctr.columbia.edu/webseek
http://www.hermitagemuseum.org/
|