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

САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

На правах рукописи

Васильева Наталья Сергеевна

004693833

ПОСТРОЕНИЕ И КОМБИНИРОВАНИЕ ПРИЗНАКОВ В ЗАДАЧЕ ПОИСКА ИЗОБРАЖЕНИЙ ПО СОДЕРЖАНИЮ

05.13.11 — Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

1 о июн 2010

Санкт-Петербург 2010

004603833

Работа выполнена на кафедре системного программирования матема-тико-механического факультета Санкт-Петербургского государственного университета.

Научный руководитель: доктор физико-математических наук,

проф. НОВИКОВ Борис Асенович

Официальные оппоненты: доктор физико-математических наук,

проф. КАРКИЩЕНКО Александр Николаевич (ОАО "НИИАС", Москва)

кандидат физико-математических наук, ОКРУГИН Михаил Борисович (Quest Software, Inc., Санкт-Петербург)

Ведущая организация: Институт системного программирования РАН

(Москва)

Защита диссертации состоится "/у " 2010 года в -

часов на

заседании совета Д212.232.51 по защите докторских и кандидатских диссертаций при Санкт-Петербургском государственном университете по адресу: 198504, Санкт-Петербург, Петродворец, Университетский пр., д. 28, математико-механический факультет, ауд. 405.

С диссертацией можно ознакомиться в Научной библиотеке Санкт-Петербургского государственного университета по адресу: 199034, Санкт-Петербург, Университетская наб., д. 7/9.

Автореферат разослан 2010 года.

Ученый секретарь

диссертационного совета

доктор физико-математических наук,

профессор Даугавет И. К.

Общая характеристика работы

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

Поиск по содержанию (Content Based Image Retrieval, CBIR) является приоритетным подходом к решению задачи поиска изображений. Методы поиска по содержанию работают на основе анализа численных характеристик составляющих изображение пикселей и не требуют наличия текстовых аннотаций или другой дополнительной информации об изображении. Это позволяет избежать трудоемкости и субъективности составленных вручную аннотаций, неточности аннотаций, полученных автоматически или полуавтоматически. Однако на сегодняшний день эффективность систем поиска по содержанию значительно уступает эффективности поиска по аннотациям. Основной проблемой поиска по содержанию большинство исследователей признают так называемый "семантический разрыё'. Человек, сравнивая два изображения, в первую очередь сравнивает их смысловое наполнение - семантику, в то время как оценка системы основывается на сравнении низкоуровневых признаков, описывающих визуальные характеристики изображения (цвет, текстуру, форму объектов). Задачи уменьшения семантического разрыва и повышения качества результатов поиска по содержанию являются актуальными в области поиска изображений и информационного поиска в целом.

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

Для достижения поставленной цели были решены следующие задачи.

• Разработка эффективного цветового признака в соответствии с особенностями зрительного восприятия человека.

• Формулирование требований к методам синтеза в контексте задачи поиска изображений.

• Разработка эффективных методов синтеза для комбинирования результатов поиска по различным пространствам признаков.

Основные результаты. В работе получены следующие основные результаты.

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

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

3. Требования к универсальным (не зависящим от изображения-запроса) методам синтеза для комбинирования результатов поиска по различным пространствам признаков. Метод синтеза с использованием среднего взвешенного с гравитационной функцией (WTGF - Weighted Total with Gravitation Function), удовлетворяющий сформулированным требованиям.

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

5. Адаптивный метод синтеза результатов поиска по цветовым и текстурным признакам в зависимости от изображения-запроса, центро-идный метод классификации запроса.

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

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

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

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

Апробация работы. Основные результаты диссертации докладывались на Российском семинаре по Оценке Методов Информационного Поиска, РОМИП 2008 (Дубна, Россия, октябрь 2008); на Второй Российской летней школе по информационному поиску "Russian Summer School in Information Retrieval" (Таганрог, сентябрь 2008); на Международной Конференции по Обработке Изображений и Сигналов "International Conference on Image and Signal Processing" (Шербург-Октевиль, Франция, июль 2008); на Шестой и Восьмой Международных Балтийских Конференциях по Базам Данных и Информационным Системам "Baltic Conference on Databases and Information Systems" (Рига, Латвия, июнь 2004 и Таллинн, Эстония, июнь 2008 ); на семинаре Московской Секции ACM SIGMOD (Москва, Россия, ноябрь 2007); на семинаре победителей конкурса научных проектов "Интернет-Математика 2007" (Переславль-Залесский, октябрь 2007); на Седьмой и Девятой Всероссийских научных конференциях "Электронные библиотеки: перспективные методы и технологии, электронные коллекции" (Ярославль, Россия, октябрь 2005 и Переславль-Залесский, Россия, октябрь 2007); на семинарах группы исследования методов организации информации при лаборатории исследования операций НИММ.

Результаты диссертации были частично использованы в работах по гранту РФФИ 07-07-00268а, по гранту компании "Яндекс" для победителей конкурса научных проектов "Интернет-Математика 2007", во внутренних проектах лаборатории Hewllett-Packard.

Публикации. Основные результаты представлены в работах [1-10]. Статьи [1-2] опубликованы в журнале, входящем в перечень ВАК. Статьи [3-10] написаны в соавторстве. В работах [3-6] автору принадлежат метод центроидной классификации запроса, включая алгоритм нахожде-

ния центроидов, общая постановка экспериментов, реализация цветовых и текстурных признаков, анализ результатов экспериментов, Маркову И. Е.

- реализация описываемых методов, создание экспериментальных стендов, сбор результатов экспериментов. В статье [7] автору принадлежат схема поиска по текстовому запросу в частично-аннотированной коллекции, требования к универсальной функции синтеза, анализ результатов экспериментов и анализ применимости предложенных методов синтеза, соавторам

- определение функции WTGF, создание экспериментальных стендов, сбор результатов экспериментов. В статье [8] автору принадлежит гипотеза о существовании единой оптимальной смешанной метрики для групп семантически и визуально подобных изображений, определение метода адаптивного синтеза, реализация цветовых и текстурных признаков, соавторам -реализация метода адаптивного синтеза, постановка и сбор результатов экспериментов. В работах [9-10] автору принадлежат алгоритм поиска по подобию с использованием текстового запроса, алгоритм построения соответствий между низкоуровневыми признаками и семантикой изображений, определение цветовой гистограммы, учитывающей пространственное расположение цветов, реализация цветовых и текстурных признаков, постановка и анализ результатов экспериментов, Новиков Б. А. оказывал помощь в формулировании задач и при редактировании текста статей.

Структура и объем диссертации. Диссертация состоит из введения, 3 глав, заключения и списка литературы. Общий объем диссертации составляет 164 страницы машинописного текста. Библиография содержит 149 наименований. Рисунки и таблицы нумеруются по главам.

Содержание работы

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

В первой главе "Методы поиска изображений по содержанию" представлены направления и задачи области исследования (Content-Based Image Retrieval, CBIR), рассматриваются основные алгоритмы построения векторов признаков и метрики для соответствующих пространств, обсуждаются известные на сегодняшний день подходы к комбинированию различных признаков.

В п. 1.1 представлена традиционная архитектура систем поиска изображений по содержанию и выделены основные направления исследований в области CBIR: построение пространств признаков, многомерное индексирование и проектирование систем поиска. Диссертация решает задачи первого из направлений.

В п. 1.2 перечислены основные проблемы области СВШ: семантический разрыв, неудобство запроса-образца, необходимость обеспечения высокой скорости работы систем поиска на больших объемах данных.

В п. 1.3 приведена общая классификация подходов к построению векторов признаков. Выделены классы цветовых, текстурных и признаков формы. В пп. 1.4 - 1.6 описаны основные алгоритмы построения векторов признаков для цвета, текстуры и формы объектов. Для каждого из классов приведена более подробная классификация в соответствующем разделе.

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

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

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

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

П. 2.1 описывает рассмотренные в работе палитры - наборы цветовых диапазонов, полученных путем равномерного квантования некоторого цветового пространства с определенными шагами для каждой из координатных осей. Для обозначения палитры будем использовать запись вида Со1огЗрасе{К х Ь х М), где ColorSpa.ee - обозначение цветового пространства; К, Ь, М - число уровней квантования для трех координатных осей пространства.

Формально палитра определяется следующим образом:

Со1огЗрасе(К х Ь х М> = {&к,1,т}к=1..к,1=1..ь,т=1..м, (1)

Ак,1,т = е Со1огБрасе\х £ (хк,хк+1],у £ (у1,у[+х], ^ € (гт,гт+1]},

Щ = Уз = А, Zj = ]5г.

Здесь 6Х, 6у, Sz - шаги квантования по осям пространства Color Space.

В работе использовались цветовые пространства HSI*, nHSI*, HCL (Hue, Chroma and Luminance), nHCL, CIELab, nCIELab и nRGB. Описание пространств и формальные правила преобразования RGB —► HSI*, RGB —> HCL, RGB —> CIELab, RGB —> nRGB приведены в п. 2.1.1. Пространства nHSI*, nHCL, nCIELab были получены из пространства nRGB с помощью тех же преобразований, что и пространства HSI*, HCL, CIELab из RGB соответственно.

В п. 2.1.2 обосновывается выбор шагов при равномерном квантовании для перечисленных выше пространств. Однако равномерное квантование пространств HSI* и HCL не учитывает такие особенности системы зрительного восприятия человека, как меньшая чувствительность к изменению оттенка цвета при недостаточной или чрезмерной яркости, недостаточной насыщенности цвета. Чтобы учесть эти особенности, введем для пространств семейства HSV еще одну схему квантования ColorSpace{K х L х M)th -равномерное квантование с граничными условиями

Ав = {(х, у, z) 6 ColorSpace\z < IB}, Aw = {(x,y,z) G ColorSpace\z > Iw}, дт = {(s, У>z) e ColorSpace\y < SG,z G (zm, zm+1}}, &k,l,m = {{x,y,z) G ColorSpace\x G (xk,xk+i],y G (y{,yl+i],z G (zm,zm+1]},

Здесь 1В - пороговое значение яркости, такое что все цвета с меньшей яркостью не отличимы от черного; 7й' - пороговое значение яркости, такое что все цвета с большей яркостью не отличимы от белого; Ба - пороговое значение насыщенности, такое что все цвета с меньшей насыщенностью не отличимы от серого; 5Х, ¿у, Зг - шаги квантования по осям пространства Со1огЗрасе.

Полный перечень палитр, рассмотренных в работе, представлен в п. 2.3.1, в таблице 2.1.

В п. 2.2. вводится новый цветовой признак на основе цветовой гистограммы. Для каждого ненулевого элемента гистограммы предлагается вычислять центр масс пикселей соответствующего цвета. Таким образом цветовой признак изображения I представляет собой набор векторов

ColorSpace(K х L х M)th = Ав U AWU

{^m}m=l..M Ц{Ak,l,m}k=l..K,l=l..L,m=l..M,

(2)

X, = jöx, Vj = SG + jSy, Zj =IB + jS:

HistSP(I) = {cj|ci = (pi,Xi,yi)}i=i...N,

(3)

где N - число цветовых диапазонов; pi - отношение количества пиксе-

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

Для определения расстояния между изображенный и по соответствующим им признакам

N

HistSP(lW) = {cf'lcP' = (Pf\zf> мы предлагаем использовать следующую функцию:

ZWp(/(1), /(2)) = £ ((А>(с!1}, с!2)) + а) (pxy{cf\с|2)) + ß) - aß), 1=1

(4)

где

= (5)

m m f v5E35!±ZEZ)! о(Ч>0ЛоМ>0

U, p\ = 0 V p\ = 0 maxXy - максимальное возможное расстояние между центрами масс цветовых пятен в нормированных координатах (длина диагонали изображения), а и ß - параметры.

Функция (4) не является метрикой, так как не удовлетворяет неравенству треугольника. Выбор данной функции расстояния обосновывается в п. 2.2.

П. 2.3 содержит описание и анализ результатов экспериментов по оценке эффективности поиска по классическим цветовым гистограммам и признакам HistSP в цветовых пространствах HSI*, nHSI*, HCL, nHCL, CIELab, nCIELab, nRGB с использованием равномерного квантования и равномерного квантования с граничными условиями с различными шагами.

Согласно полученным результатам, добавление информации о пространственном расположении цветов в гистограмму позволило существенно повысить точность (до 28%) и полноту (до 15%) результатов поиска вне зависимости от выбора цветового пространства и схемы квантования. Экспериментальное исследование зависимости эффективности поиска по цветовым гистограммам от выбора шага квантования цветового пространства доказало существование пороговых значений, таких что выбор меньших шагов квантования (увеличение числа цветовых диапазонов) не приводит к улучшению результатов поиска. При равномерном квантовании для всех цветовых пространств и функций подобия, участвоваших в экспериментах,

оптимальным оказалось использование порядка 500 цветовых диапазонов. Добавление граничных условий позволило повысить показатели точности и полноты для схем с небольшим числом цветовых диапазонов. По данным показателям схема квантования (6,2,3)(;1 (41 цветовой диапазон) для пространств семейства HSV в большинстве случаев превзошла схемы равномерного квантования со значительно большим числом диапазонов или лишь незначительно уступила им.

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

В п. 3.1 рассматривается общая задача синтеза взвешенных ранжированных списков.

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

Ранжированный г-ый список будем обозначать символом а,-. Ранжированный список состоит из пар вида (x,ri(x)), где х - объект, а г\(х) - его ранг в списке щ. Обозначим набор всех рангов объекта х из различных ранжированных списков как вектор Rx = (ri(x), ^(я),..., гд?(х)), где N -число ранжированных списков. В контексте задачи информационного поиска ранг объекта является значением функции подобия, определенной на некотором пространстве признаков, и отражает степень близости данного объекта запросу в этом пространстве признаков.

Будем рассматривать вес Wi ранжированного списка щ как показатель уверенности в том, насколько ранги объектов в данном списке соответствуют их степени подобия запросу. Обозначим набор весов всех ранжированных списков как вектор W = (tui, и>2,..., гик).

Обозначим как ао результирующий ранжированный список, tq(x) -ранг объекта х в результирующем списке. Задача синтеза сводится к поиску подходящей функции синтеза f(Rx,W), с помощью которой можно вычислить ранг в результирующем списке каждого из элементов исходных списков:

Ух, г: (х, п(х)) € а,- rQ(x) = f(Rx, W).

П. 3.1.1 содержит описание практических задач, которые сводятся к задаче синтеза взвешенных ранжированных списков. В п. 3.1.2 определены основные свойства функции синтеза, подходящей для решения поставленных задач.

Свойство 1 Симметричность.

Ri = (ri(x),r2{x),...,rN(x)), Wi = (wi,w2,...,wN), R2, W2 ~ перестановки Ri и Wi соответственно, тогда f(Ri,Wi) = f(R2,W2).

Свойство 2 Монотонность по каждому из аргументов.

R\ = (n(x), r2(x),..., rN(x)), R2 = (п(у), r2(y),..., rN(y)), Wi = (wn,wi2,...,w1N), W2 = (w2Uw22,...,w2N), тогда n(x) < n{y) Vie{l,...,N}=> f{Ru Wj < f(R2, Wx), wu < w2i Vi € {1,..., tf} =» f(Rь W) < f(Ri, W2).

Свойство 3 Суперпозиция.

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

Свойство 4 Ограниченность (MinMax условие).

Пусть имеется N списков: сц, а2,..., адг. Элементу х в них сопоставляется следующий набор рангов: Rx = (r\(x),r2(x),..., г^(х)). Тогда после синтеза ранг tq{x) должен удовлетворять условию: min (ri(x),r2(x),... ,г^(х)) < ro(x) < max(ri(x),r2(x),г^(х)).

Свойство 5 Для функции синтеза должны выполняться следующие "правила конусов":

• Выполнение граничных условий.

— Вероятность изменения ранга объекта, присутствующего с высоким рангом в списке с большим весом, мала.

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

• Влияние весов списков. Если есть два элемента (х G а\ и у € а2) из списков с различными весами (wi > w2), но с одинаковыми рангами ('1(2:) = г2{у) > 0), то в результирующем списке их ранги должны быть различны, причем го(х) > го(у).

• Степень свободы низкоранговых элементов. Чем меньше ранг элемента, тем больше степень свободы изменения его ранга в результирующем списке.

• Степень свободы высокоранговых элементов в списках с высоким весом. Чем больше ранг элемента и выше вес списка, в котором он встречается с высоким рангом, тем меньше степень свободы изменения его ранга в результирующем списке.

• Согласованность. Незначительные изменения веса списка или ранга элемента не должны повлечь значительных изменений результирующего ранга элемента.

В п. 3.1.2 определяется новая функция синтеза WTGF (Weighted Total with Gravitation Function) - взвешенное среднее с гравитационной функцией, удовлетворяющая сформулированным требованиям. Данная функция задана следующим образом:

fifí нл - ЕМх) ■ g{ri(x),Wj)

где g - функция стабилизации высокоранговых элементов или гравитационная функция

g(rf(x), Wi) = w¡ ■ ^ф) + .

(8)

П. 3.1.2 содержит обоснование выбора вида функции \VTGF, а также описание реализации вычислений данной функции. В п. 3.1.3 и п. 3.1.4 приводятся описание и результаты экспериментального сравнения функции WTGF с известными функциями синтеза СотЬМ^ и взвешенным средним при решении поставленных выше практических задач.

Согласно полученным результатам, функция \VTGF более эффективна при условии достоверности информации о весах источников синтеза и их небольшом пересечении. Использование СотЬМЖ дает лучший результат при достаточном пересечении источников синтеза. В целом, использование методов синтеза для решения поставленных нами задач оправдало себя -это позволило улучшить результаты поиска.

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

В п. 3.2.1 вводится понятие смешанных метрик Дтхе^> которые являются линейной комбинацией цветовой и текстурной метрик с определенными весами.

а ■ Бсо1ог{1, О) + (1 ~ а) • Дех4иге(Л О), (9)

где I и - изображения, И^аг — цветовая метрика, ВьехЫге ~~ текстурная метрика, а - параметр из отрезка [0,1]. Метод адаптивного синтеза заклю-

чается в применении на этапе поиска смешанной метрики с оптимальным значением параметра а для заданного запроса.

В п. 3.2.2 приводятся описание и результаты эксперимента, подтверждающего сформулированную гипотезу, в п. 3.2.3 - эксперимента по сравнению эффективности метода адаптивного синтеза с известным методом синтеза СотЬМ^. Согласно полученным результатам, средняя точность поиска по всем изображениям тестового множества для оптимальных смешанных метрик составила 42.76%, для метода СотЬМ^ - 39.68%, что говорит о превосходстве метода адаптивного синтеза.

В п. 3.2.4 исследуется применимость известных методов классификации (методы Байеса и опорных векторов, БУМ) для классификации запроса в контексте метода адаптивного синтеза, предлагается центроидный классификатор. Согласно результатам эксперимента, классификаторы Байеса и БУМ не вполне подходят для решения поставленной задачи. Основные ограничения данных методов связаны с недостаточной представительностью и несбалансированностью обучающего множества. Такие условия обучения классификаторов приводят к их ненадежной работе на этапе классификации. В то же время, центроидный классификатор, будучи крайне простым в обучении и быстрым в принятии решения, дает приемлемые результаты классификации в сравнении с методами Байеса и опорных векторов в контексте решаемой нами задачи.

П. 3.3 содержит основные выводы по исследованию методов синтеза применительно к комбинированию независимых признаков в задаче поиска изображений.

Заключение содержит список основных результатов, полученных в работе.

Работы автора по теме диссертации

Статьи в журналах, рекомендованных ВАК:

[1] Васильева Н.С. Выбор шага квантования при построении цветовой гистограммы в задаче поиска изображений // Вестник СПбГУ. Сер. 10: Прикладная математика, информатика, процессы управления. -Изд-во СПбГУ, 2009. - Вып. 2. - С. 155-164.

¡2] Васильева Н.С. Методы поиска изображений по содержанию // Программирование. - 2009. - № 3. - С. 1-30.

Другие публикации:

[3] Васильева Н.С., Марков И.Е. СПбГУ на РОМИП'2008: Синтез цветовых и текстурных признаков при поиске изображений по содержанию // Труды Российского семинара по Оценке Методов Информационного Поиска РОМИП 2007-2008. - 2008. - С. 135-144.

[4] Markov I., Vassilieva N. Building up low-level centroids for groups of perceptually similar images // Proceedings of the 8th International Baltic Conference on Databases and Information Systems. - Tallinn, Estonia, 2008. - P. 341-348.

[5] Markov I., Vassilieva N. Image retrieval. Color and texture combining based on query-image // Proceedings of the International Conference on Image and Signal Processing. - Cherbourg-Octeville, France, 2008. - P. 430-438.

[6] Markov I., Vassilieva N. Query classification in content-based image retrieval // Databases and Information Systems V - Selected Papers from the Eighth International Baltic Conference, DB&IS 2008 / Ed. by H.-M. Haav, A. Kalja. - IOS Press, 2008. - Vol. 187 of Frontiers in Artificial Intelligence and Applications. - P. 281—288.

[7] Васильева H.C., Дольник A.C., Марков И.Е. Поиск изображений. Синтез различных методов поиска при формировании результатов // Интернет-Математика 2007: Сборник работ участников конкурса / Под ред. П. Браславского. - Екатеринбург: Изд-во Урал, ун-та, 2007. - С. 46-55.

[8] Марков И.Е., Васильева Н.С., Яремчук А.. Поиск изображений. Выбор оптимальных весов для слияния метрик по цвету и текстуре в зависимости от запроса-образца // Труды 9-ой Всероссийской научной конференции "Электронные библиотеки: перспективные методы и технологии, электронные коллекции". - 2007. - С. 195-200.

[9] Васильева Н.С., Новиков Б.А. Построение соответствий между низкоуровневыми характеристиками и семантикой статических изображений // Труды 7-ой Всероссийской научной конференции "Электронные библиотеки: перспективные методы и технологии, электронные коллекции". - 2005. - С. 236-240.

[10] Vassilieva N., Novikov В. A similarity retrieval algorithm for natural images // Proceedings of the6th International Baltic Conference on Databases and Information Systems (Doctoral Consortium), Vol. 673. - Riga, Latvia, 2004. -P. 151-154.

Подписано к печати 09.04.10. Формат 60 »84 1/16. Бумага офсетная. Гарнитура Тайме. Печать цифровая. Печ. л. 1,0. Тираж 100 экз. Заказ 4701. Отпечатано в Отделе оперативной полиграфии Химического факультета СПбГУ 198504, Санкт-Петербург, Старый Петергоф, Университетский пр., 26 Тел.: (812) 428-40-43,428-69-19

Введение

1. Методы поиска изображений по содержанию

1.1. Направления исследований в области CBIR.

1.2. Основные проблемы CBIR.

1.3. Построение векторов признаков: классификация подходов

1.4. Цвет.

1.4.1. Цветовые пространства.

1.4.2. Цветовые гистограммы

1.4.3. Цветовые моменты.

1.4.4. Сравнение цветовых признаков.

1.5. Текстура.

1.5.1. Матрицы смежности.

1.5.2. Признаки Тамуры.

1.5.3. Использование вейвлет-преобразования.

1.5.4. Использование фильтров Габора.

1.5.5. Использование фильтров ICA.

1.5.6. Сравнение текстурных признаков

1.6. Контуры и объекты.

1.6.1. Дескрипторы границ.

1.6.1.1. Простые дескрипторы границ.

1.6.1.2. Цепные коды.

1.6.1.3. Сигнатуры

1.6.1.4. Дескрипторы Фурье.

1.6.1.5. Другие дескрипторы границ.

1.6.2. Дескрипторы областей.

1.6.2.1. Простые дескрипторы областей.

1.6.2.2. Грид-метод (Grid based method).

1.6.2.3. Моменты и их инварианты.

1.6.2.4. Общие дескрипторы Фурье (GFD).

1.6.2.5. Декомпозиция объектов.

1.6.3. Сравнение признаков формы.

1.7. Комбинирование различных методов поиска.

1.8. Обзор существующих систем.

2. Поиск по цвету

2.1. Выбор схемы квантования при построении цветовой гистограммы

2.1.1. Выбор цветового пространства.

2.1.2. Выбор схемы квантования.

2.2. Учет пространственного расположения цветов.

2.3. Эффективность поиска по цветовым гистограммам.

2.3.1. Описание экспериментов.

2.3.2. Анализ результатов

2.3.2.1. Учет пространственного расположения цветов

2.3.2.2. Снижение зависимости от условий освещенности

2.3.2.3. Выбор шага квантования.

2.4. Выводы.

3. Синтез методов поиска при формировании результатов 99 3.1. Взвешенное среднее с гравитационной функцией.

3.1.1. Постановка задачи.

3.1.1.1. Поиск в частично аннотированной коллекции изображений.

3.1.1.2. Синтез результатов методов поиска по низкоуровневым признакам.

3.1.1.3. Формализация задачи синтеза методов поиска

3.1.2. Функция синтеза WTGF.

3.1.2.1. Свойства функции синтеза.

3.1.2.2. Функция стабилизации высокоранговых элементов и правила конусов.

3.1.2.3. Реализация вычислений.

3.1.3. Описание экспериментов.

3.1.3.1. Поиск по частично аннотированной базе

3.1.3.2. Синтез методов поиска по содержанию

3.1.4. Анализ результатов

3.1.4.1. Метод оценки алгоритмов синтеза.

3.1.4.2. Поиск в частично аннотированной коллекции

3.1.4.3. Синтез методов поиска по содержанию

3.1.4.4. Обсуждение результатов

3.2. Адаптивный синтез методов поиска по цвету и текстуре

3.2.1. Постановка задачи.

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

3.2.2.1. Описание эксперимента.

3.2.2.2. Анализ результатов

3.2.3. Сравнение методов адаптивного синтеза и CombMNZ

3.2.3.1. Описание эксперимента.

3.2.3.2. Анализ результатов

3.2.4. Классификация запроса.

3.2.4.1. Построение низкоуровневых центроидов для групп визуально подобных изображений

3.2.4.2. Использование классических алгоритмов классификации.

3.3. Выводы.

Актуальность работы

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

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

Исторически первым является поиск по текстовым аннотациям (Description Based Image Retrieval, DBIR). Данный подход подразумевает наличие у всех изображений коллекции текстовых аннотаций, описывающих их содержание, по которым и производится поиск. Таким образом, задача поиска изображений сводится к классической задаче текстового поиска.

Вторым подходом к поиску изображений является поиск по содержанию (Content Based Image Retrieval, CBIR)1. Методы поиска по содержанию работают на основе анализа численных характеристик составляющих изображение пикселей и не требуют наличия текстовых аннотаций или другой дополнительной информации об изображении. Это позволяет избежать трудоемкости и субъективности составленных вручную аннотаций, неточности аннотаций, полученных автоматически или полуавтоматически.

В англоязычной литературе по машинному зрению (computet vision) также можно встретить тор-мины Query By Image Content (QBIC) и Content-Based Visual Information Retrieval (CBVIR).

Поиск по содержанию является приоритетным направлением исследований, поскольку данный подход предполагает автоматическое построение индекса и не требует дополнительной информации об изображениях. Однако на сегодняшний день эффективность систем поиска по содержанию значительно уступает эффективности поиска по аннотациям. Основной проблемой поиска по содержанию большинство исследователей признают так называемый „семантический разрыв. Человек, сравнивая два изображения, в первую очередь сравнивает их смысловое наполнение - семантику, в то время как оценка системы основывается на сравнении низкоуровневых (визуальных) характеристик изображения, таких как цвет, текстура и форма объектов. Задачи уменьшения семантического разрыва и повышения эффективности поиска по содержанию являются актуальными в области поиска изображений и информационного поиска в целом.

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

Традиционным подходом для поиска по содержанию является независимый поиск по различным характеристикам изображения, каждая из которых описывается точкой в соответствующем пространстве признаков. Некоторые системы используют несколько пространств признаков для описания одной и той же характеристики с целью повышения точности поиска. В таком случае поиск в каждом из пространств признаков также производится независимо. Для получения общей выдачи - комбинирования промежуточных результатов поиска по каждому из пространств признаков, используются методы синтеза данных (Data Fusion). Под выдачей здесь понимается ранжированный набор объектов поиска, представляющий собой ответ поисковой системы на заданный запрос.

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

Цели и задачи работы

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

Для достижения поставленной цели были выделены следующие задачи:

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

• Формулирование требований к методам синтеза в контексте задачи поиска изображений.

• Разработка эффективных методов синтеза для комбинирования результатов поиска по различным пространствам признаков.

Основные результаты, выносимые на защиту

На защиту выносятся:

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

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

3) Требования к универсальным (не зависящим от изображения-запроса) методам синтеза для комбинирования результатов поиска по различным пространствам признаков. Метод синтеза с использованием среднего взвешенного с гравитационной функцией (WTGF - Weighted Total with Gravitation Function), удовлетворяющий сформулированным требованиям.

4) Алгоритм поиска в частично аннотированной коллекции изображений по текстовому запросу, не требующий предварительного автоан-нотпрования всей коллекции. В основе алгоритма лежит идея использования методов синтеза.

5) Адаптивный метод синтеза результатов поиска по цветовым и текстурным признакам в зависимости от изображения-запроса, центро-ндный метод классификации запроса.

Научная новизна работы

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

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

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

Практическая ценность

Методы сравнения и поиска изображений по содержанию находят широкое применение а различных областях жизнедеятельности человека: в медицине (например, поиск пациента со схожим диагнозом по рентгеновскому снимку), в промышленности (контроль качества продукции по контрольным снимкам), для защиты авторских прав (поиск копий авторской фотографии), и другие. Все больше людей пользуются поиском изображений в Интернете. Крупные поисковые системы, такие как Google, Yandex, Yahoo и другие, предлагают пользователям поиск изображений по ключевым словам, построенным по контексту изображения и не используют анализ содержания изображений. Эффективные методы поиска по содержанию помогут значительно дополнить результаты поиска таких систем и повысить их качество.

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

Апробация работы и публикации

Основные результаты диссертации докладывались на Международных Балтийских Конференциях по Базам Данных и Информационным Системам Baltic DB&IS 2004, Baltic DB&IS 2008; на Всероссийских Научных Конференциях по Электронным Библиотекам RCDL 2005, RCDL 2007; на семинаре по итогам конкурса Интернет-Математика 2007; на семинаре Московской Секции ACM SIGMOD; на Международной Конференции по Обработке Изображений и Сигналов ICISP 2008; на Российском семинаре по Оценке Методов Информационного Поиска РОМИП 2008; на семинарах группы исследования методов организации информации при лаборатории исследования операций НИММ и опубликованы в работах [1-5,8,84-86,139].

Структура диссертации

Диссертация состоит из введения, трех глав и заключения.

Основные результаты диссертации состоят в следующем:

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

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

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

4) Предложен адаптивный метод синтеза результатов поиска по цветовым и текстурным признакам в зависимости от изображений-запроса и центроидный метод классификации запроса.

5) Проведен анализ применимости предложенных методов синтеза.

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

Заключение

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

1. Васильева. Н. Выбор шага квантования при построении цветовой гистограммы в задаче поиска изображений // Вестник Санкт-Петербургского Университета, — 2009. — № 2. — С. 155-164.

2. Васильева Н. А4етоды поиска изображений по содержанию // Программирование. — 2009. — № 3. — С. 1-30.

3. Васильева П., Марков И. СПбГУ на РОМИП'2008: Синтез цветовых и текстурных признаков при поиске изображений по содержанию // Труды Российского семинара по Оценке Методов Информационного Поиска РОМИП 2007-2008. 2008. - С. 135-144.

4. Гонсалес Р., Вудс Р. Цифровая обработка изображений. Мир цифровой обработки.^ М.: Техносфера, 2005.— 1072 е. — (R. Gonzalez, R. Woods. Digital Image Processing).

5. Ковтун И. В. Текстурная сегментация изображений на основании марковских случайных полей // УСиМ. — 2003. — № 4. — С. 46-55.

6. Adaptive filtering and indexing for image databases / A. D. Alexandrov, W. Y. Ma, A. E. Abbadi, B. S. Manjunath // SPIE: Storage and Retrieval for Image and Video Databases III.— Vol. 2420.— 1995. — March. — Pp. 12-23.

7. Askoy SHaralick R. M. Content-based image database retrieval using variances of gray level spatial dependencies // IAPR International Workshop on Multimedia Information Analysis and Retrieval. — Vol. 1464,- 1998.-August. Pp. 3-19.

8. Askoy S., Haralick R. M. Textural features for image database retrieval // IEEE Workshop on Content-Based Access of Image and Video Libraries. 1998. — June. — Pp. 45-49.

9. Avrithis Y. S., Xirouhakis У. Kollias S. D. Affine invariant representation and classification of object contours for image and video retrieval // Computational Intelligence and Applications. — 1999. — Pp. 342-347.

10. Balmelli L., Mojsilovic A. Wavelet domain features for texture description, classification and replicability analysis // IEEE International Conference 011 Image Processing (ICIP-99). — Vol. 4. — 1999. — Pp. 440444.

11. Battiato S., Gallo G., Nicotra S. Perceptive visual texture classification and retrieval // 12th International Conference on Image Analysis and Processing. 2003. - September. — Pp. 524-529.

12. The bayesian image retrieval system, pichunter: Theory, implementation and psychophysical experiments / I. J. Cox, M. L. Miller, T. P. Minka et al. // IEEE Transactions on Image Processing. — 2000. — Vol. 9, no. 1.- Pp. 20-37.

13. Belkasim S., Shridhar M., Ahmadi M. Pattern recognition with moment invariants: a comparative study and new results // Pattern Recognition. — 1991.-Vol. 24, no. 12.-Pp. 1117-1138.

14. Bell A. J., Sejnowsky T. J. The "independent components" of natural scenes are edge filters // Vision Research. — 1997. — no. 37. — Pp. 33273338.

15. Blum H. A transformation for extracting new descriptors of shape // Models for the Perception of Speech and Visual Forms / Ed. by Whaten-Dunn. MIT Press, 1967. - Pp. 362-380.

16. Borgefors G. Hierarchical chamfer matching: A parametric edge matching algorithm // IEEE Transactions on Pattern Analysis and Machine Intelligence. 1988. - Vol. 10, no. 6. - Pp. 849-865.

17. Borgne H. Gucrin-Dugue A., Antoniadis A. Representation of images for classification with independent features // Pattern Recognition Letters. — 2004. Vol. 25. - Pp. 141-154.

18. Burges C. J. A tutorial on support vector machines for pattern recognition // Data Mining and Knowledge Discovery. — 1998. — Vol. 2, no. 2,- Pp. 121-167.

19. Burt P. J., Adelson E. H. The laplasian pyramid as a compact image code // IEEE Transactions on Communications. — 1983.— Vol. COM-31, no. 4. — Pp. 532-540.

20. Chang Т., Jay C.-C. K. Texture analysis and classification with tree-structured wavelet transform // IEEE Transactions on Image Processing.- 1993. — Vol. 2, no. 4, — Pp. 429-441.

21. Chapelle 0., Vapnik P. II. V. Svms for histogram based image classification // IEEE Transactions on Neural Net-works.— 1999.— Vol. 10,- Pp. 1055-1064.

22. Chen Y., Zhou X. S., Huang T. S. One-class svm for learning in image retrieval // IEEE International Conference on Image Processing (ICIP 2001).- 2001.- Pp. 34-37.

23. Chitkara V. Color-based image retrieval using compact binary signatures: Tech. Rep. TR 01-08: University of Alberta Edmonton, 2001. May.

24. Chuang G. C.-H. Kuo C.-C. J. Wavelet descriptor of planar curves: theory and applications // IEEE Transactions on Image Processing.— 1996. January. - Vol. 5, no. 1. - Pp. 56-70.

25. Coifman R. R., Wickerhauser M. V. Entropy-based algorithms for best basis selection // IEEE Transactions on Information Theory. — 1992. — March. Vol. 38, no. 2. - Pp. 713-718.

26. Color space. — Wikipedia, the free encyclopedia, http: / / en.wikipedia.org/wiki/Colorspace.

27. Content-based image retrieval. — Wikipedia, the free encyclopedia.http://en.wikipedia.org/wiki/Content-basedimageretrieval.

28. Cover T. M.; Hart P. E. Nearest neighbor pattern classification // EEE Transactions on Information Theory. — 1967. — Vol. 13, no. 1. — Pp. 2127.

29. Cross G. R., Lain A. K. Markov random field texture models // IEEE Transactions on Pattern Analysis and Machine Intelligence.— 1983.— Vol. PAMI-5. Pp. 25-39.

30. Deer P., Eklund P. On the fusion of image features. — Electronic resource. http://citeseer.ist.psu.edu/162546.html.

31. Dennis T. J., Dessipris N. G. Fractal modelling in image texture analysis // IEEE Proc. of Radar and Signal Processing. — Vol. 136. — 1989. Pp. 227-235.

32. Do M. N., Vetterli M. Texture similarity measurement using kullback-leibler distance on wavelet subbands // IEEE International Conference on Image Processing (ICIP-2000). Vol. 3. - 2000. - Pp. 730-733.

33. Efficient and effective querying by image content: Tech. rep. / C. Faloutsos, W. Equitz, M. Flickner et al.: IBM Research, 1993.— August.

34. An efficiently computable metric for comparing polygonal shapes / E. M. Arkin, L. Chew, D. Huttenlocher et al. // IEEE Transactions on Pattern Analysis and Machine Intelligence. — 1991. — Vol. 13. — Pp. 209216.

35. Fan S. Shape representation and retrieval using distance histograms: Tech. Rep. 01-14: Department of Computing Science, University of Alberta, 2001, —October.

36. Fast algorithm for the computation of moment invariants / M. F. Zakaria, L. Л. Vroomen, P. J. A. Zsombor-Murray, J. M. H. M. van Kessel // Pattern Recognition. — 1987. Vol. 20, no. 6. - Pp. 639-643.

37. Field D. J. Relations between the statistics of natural images and the response properties of cortical cells // Journal of the Optical Society of America. — 1987. Vol. 4, no. 12. - Pp. 2370-2393.

38. Fox E. A., Shaw J. A. Combination of multiple searches // 2nd Text REtrieval Conference (TREC-2).— National Institute of Standards and Technology Special Publication 500-215, 1994.- Pp. 243-252.

39. Freeman H. In computer processing of line-drawing images //A CM Computing Surveys (CSUR). 1974. - March. — Vol. 6. - Pp. 57-97.

40. Ghafoor A., Iqbal R. N., Khan S. A. Modified chamfer matching algorithm // Lecture Notes in Computer Science. — 2003. — Vol. 2690. — Pp. 1102-1106.

41. Gotlieb С. C., Kreyszig H. E. Texture descriptors based on co-occurrcnce matrices // Computer Vision, Graphics and Image Processing. — 1990.-— July. Vol. 51, no. 1. - Pp. 70-86.

42. Grosky W., Stanchev P. An image data model //In Proceedings of Advances in Visual Information Systems: 4th International Conference. — 2000. Pp. 227-243.

43. Guerin-Dugue A., Ayachc S., Berrut C. Image retrieval: a first step for a human centered approach // Joint Conference of ICI, CSP and PRCM. — 2003. Pp. 21-25.

44. Guironnet M., Pellerin D., Ladret P. Combinaison de descripteurs flous de couleur et d'activite pour le rc%ume de videos // 14eme congres de Reconnaissance des Formes et Intelligence Artificielle RFIA. — 2004.

45. Haddadnia J., Ahmadi M., Faez K. An efficient feature extraction method with pseudo-zernike moment in RBF neural network-based human face recognition system // EURASIP Journal on Applied Signal Processing. — 2003. — Pp. 890-901.

46. Ilaralick R. M., Shanmugam K., Dienstein I. Textural features for image classification // IEEE Transactions on Systems, Man and Cybernetics. — 1973. — November. Vol. 3, no. 6. - Pp. 610-621.

47. Hateren J. H. V., der Schaaf A. V. Independent component filters of natural images compared with simple cells in visual cortex // Transactions of Royal Society of London.— 1998.— Vol. В265,— Pp. 359-366.

48. Heller K. A., Ghahramani Z. A simple bayesian framework for content-based image retrieval // IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR 2006).- 2006.-Pp. 2110-2117.

49. Hew P. Geometric and zernike moments. — Diary, Department of Mathematics, The University of Western Australia. — 1996. — October. http://citeseer.ist.psu.cdu/hew96geometric.html.

50. Howarth P., Riiger S. Evaluation of texture features for content-based image retrieval // Proceedings of CIVR'04. 2004. - Pp. 326-334.

51. Howarth P., Riiger S. Robust texture features for still image retrieval // IEE Proceedings of Vision, Image and Signal Processing. — Vol. 152. — 2005. December. - Pp. 868-874.

52. Ни M.-K. Visual pattern recognition by moment invariants // IEEE Transactions on Information Theory.— 1962. — February.— Vol. 8.— Pp. 179-187.

53. Huang C.-L., Huang D.-H. A content-based image retrieval system // Image and Vision Computing. — 1998. — Vol. 16. — Pp. 149-163.

54. Huang T. S., Mehrotra S., Ramchandran K. Multimedia analysis and retrieval system (MARS) project // Proceedings of 33rd Annual Clinicon Library Application of Data Processing Digital Image Access and Retrieval. - 1996.

55. Iivarinen J., Visa A. Shape recognition of irregular objects // SPIE 2904 on Intelligent Robots and Computer Vision XV: Algorithms, Techniques, Active Vision, and Materials Handling. — 1996. — Pp. 25-32.

56. Image classification for content-based indexing / A. Vailaya, M. A. T. Figueiredo, A. K. Jain, H.-J. Zhang // IEEE Transactions on Image Processing.— 2001,- Vol. 10, no. 1.— Pp. 117-130.

57. Ioka M. A method of defining the similarity of images on the basis of color information: Tech. Rep. RT-0030: IBM Tokyo Research Lab, 1989.

58. Jack K. Video Demystified: A Handbook for the Digital Engineer, Fourth Edition. — Newnes, 2004. — 966 pp.

59. Jagadish H. V. A retrieval technique for similar shapes // ACM SIGMOD International Conference on Management of Data. — 1991. —May. — Pp. 208-217.

60. Jeong S., Won C. S., Gray R. M. Image retrieval using color histograms generated by gauss mixture vector quantization // Computer Vision and Image Understanding. — 2004. — Vol. 94. — Pp. 44-66.

61. Khotanzad A., Hong Y. H. Invariant image recognition by zernike moments // IEEE Transactions on Pattern Analysis and Machine Intelligence. 1990. - May. - Vol. 12. - Pp. 489-497.

62. Kingsbury N. Image processing with complex wavelets // Philosophical Transactions of Royal Society of London, Series A: Mathematical, Physical and Engineering Sciences. — 1999. — Vol. 357. — Pp. 2543-2560.

63. Krishnamachari S., Chellappa R. Multiresolution gauss-markov random field models for texture segmentation // IEEE Transactions on Image Processing. 1997. - Vol. 6, no. 2. — Pp. 251-267.

64. Learning similarity measure for natural image retrieval with relevance feedback / G.-D. Guo, A. K. Jain, W.-Y. Ma, H.-J. Zhang // IEEE Transactions on Neural Networks. 2002, — Vol. 13. — Pp. 811-820.

65. Lee D. J., Antani A., Long L. R. Similarity measurement using polygon curve representation and fourier descriptors for shape-based vertebral image retrieval // SPIE, Medical Imaging 2003: Image Processing. — Vol. 5032.- 2003,- Pp. 1283-1291.

66. Lee J. H. Analyses of multiple evidence combination // 20th annual international ACM SIGIR conference on Research and development in information retrieval. — ACM Press, 1997. — Pp. 267-276.

67. Lillis D. Probfuse: a probabilistic approach to data fusion // 29th annual international ACM SIGIR conference on Research and development in information retrieval. — ACM Press, 2006. — Pp. 139-146.

68. Lillis D., Toolan F., et a,I. A. M. Probability-based fusion of information retrieval result sets // 16th Irish Conference on Artificial Intelligence and Cognitive Science. 2005,- Pp. 147-156.

69. Lin T.-W., Chou Y.-F. A comparative study of zernike moments // IEEE/WIC International Conference on Web Intelligence (WI'03).-2003.- Pp. 516-519.

70. Lin T.-W., Chou Y.-F. A comparative study of zernike moments for image retrieval // 16th IPPR Conference on Computer Vision, Graphics and Image Processing (CVGIP 2003). 2003. - Pp. 621-629.

71. Loncaric S. A survey of shape analysis techniques // Pattern Recognition. 1998. - Vol. 31, no. 8.- Pp. 983-1001.

72. Luren Y., Fritz A. Fast computation of invariant geometric moments: A new method giving correct results // IEEE International Conference on Image Processing. — 1994.

73. Ma W. Y., Manjunath B. S. Texture features and learning similarity // IEEE International Conference on Computer Vision and Pattern Recognition (CVPR-1996). 1996. - June. - Pp. 425-430.

74. Ma W. Y., Manjunath B. S. Netra: a toolbox for navigating large image databases // IEEE International Conference on Image Processing (ICIP-1997). Vol. 1. - 1997. - Pp. 568-571.

75. Ma,Hat S. G. A theory for multiresolution signal decomposition: the wavelet representation // Transactions on Pattern Analysis and Machine Intelligence. 1989. - July. - Vol. 11, no. 7. - Pp. 674-693.

76. Manjunath B. S. Image processing in the alexandria digital library project // IEEE International Forum on Research and Technology Advances in Digital Libraries. — 1998. — Pp. 180-187.

77. Manjunath B. S., Ma W. Y. Texture features for browsing and retrieval of image data // IEEE Transactions on Pattern Analysis and Machine Intelligence. 1996. - Vol. 18, no. 8. - Pp. 837-842.

78. Markov I., Vassilieva N. Building up low-level centroids for groups of perceptually similar images // 8th International Baltic Conference on Databases and Information Systems (Baltic DB&IS 2008).— 2008.-June. Pp. 341-348.

79. Markov I., Vassilieva N. Image retrieval, color and texture combining based on query-image // International Conference on Image and Signal Processing (ICISP 2008). 2008. - July. - Pp. 430-438.

80. Marshall S., Sicuranza G. L. Advances in nonlinear signal and image processing. EURASIP Book Series on Signal Processing and Communications. — New York, NY, USA: Hindawi Publishing Corporation, 2006. — 361 pp.

81. McDonald I(. A., Smeaton A. F. A comparison of score, rank and probability-based fusion methods for video shot retrieval // Conference on Image and Video Retrieval. — 2005. — Pp. 61-70.

82. Mehtre В. M., Kankanhalli M. S.; Lee W. F. Shape measures for content based image retrieval: A comparison // Information Processing arid Management 1997. - May. - Vol. 33. — Pp. 319-337.

83. Mercimek M., Gulez К., Митси Т. V. Real object recognition using moment invariants // SADHANA-Academy, Engineering Sciences. — Vol. 30. 2005. - December. - Pp. 765-775.

84. Missaoui RSarifuddin M., Vaillancourt J. An effective approach towards content-based image retrieval // Image and Video Retrieval. — Vol. LNCS 3115/2004.- Springer Berlin / Heidelberg, 2004. Pp. 335343.

85. Ortega M. — WebMars: A Multimedia Search Engine for the World Wide Web. — Master's thesis, Graduate College of the University of Illinois at Urbana-Champaign, 1999.

86. Parametric correspondence and chamfer matching: Two new techniques for image matching / H. G. Barrow, J. M. Tenenbaum, R. C. Bolles, H. C. Wolf // 5th International Joint Conference on Artificial Intelligence. 1977. - Pp. 659-663.

87. Peltarion synapse documentation. — WWW page. http://www.peltarion.com/WebDoc.

88. Porkaew К., Chakrabarti К., Mehrotra S. Query refinement for content-based multimedia retrieval in mars // ACM Multimedia Conference. — 1999.

89. Pseudo-zernike polynomials. — Wikipedia, the free encyclopedia. http://en.wikipedia.org/wiki/Pseudo-Zernikepolynomials.

90. The QBIC project: Querying images by content, using color, texture, and shape / W. Niblack, R. Barber, W. Equitz et al. // Proceedings of Storage and Retrieval for Image and Video Databases (SPIE). — 1993. — Pp. 173-187.

91. Query by image and video content: the QBIC system / M. Flickner, H. Sawhney, W. Niblack et al. // Intelligent multimedia information retrieval. 1997. - Pp. 7-22.

92. Relevance feedback: A power tool for interactive content-based image retrieval / Y. Rui, T. S. Huang, M. Ortega, S. Mehrotra // IEEE Transactions on Circuits and Systems for Video Technology. — 1998. — Vol. 8, no. 5.

93. Rui Y., Huang T., Chang S.-F. Image retrieval: Past, present and future // International Symposium on Multimedia Information Processing. — 1997.

94. Rui Y., She A. C., Huang T. S. Modified fourier descriptors for shape representation a practical approach // First International Workshop on Image Databases and Multimedia Search. — 1996.

95. Safar M., Shahabi СSun X. Image retrieval by shape: a comparativestudy // IEEE International Conference on Multimedia and Expo. — Vol. 1. 2000,- Pp. 141-144.

96. Sajjanhar A., Lu G. A. A grid based shape indexing and retrieval method // Australian Computer Journal. — 1997. — Vol. 29. — Pp. 131140.

97. Salton G., Fox E. A., Wu H. Extended boolean information retrieval // Communications of the ACM.- 1983.- Vol. 26, no. 11.— Pp. 10221036.

98. Santini S. Exploratory Image Databases.— Academic Press, 2001.— 512 pp.

99. Sarifuddin M., Missaoui R. A new perceptually uniform color space with associated color similarity measure for contentbased image and video retrieval // ACM SIGIR Workshop on Multimedia Information Retrieval. 2005.

100. Sebastian Т. ВKimia В. B. Curves vs. skeletons in object recognition // Signal Processing. 2005. - Vol. 85. - Pp. 247-263.

101. Sebastian Т. В., Klein P. N., Kimia В. B. Shock-based indexing into large shape database // Lecture Notes in Computer Science.— 2002.— Vol. 2352. Pp. 83-98.

102. Sebe N. Lew M. S. Wavelet based texture classification // International Conference on Pattern Recognition. — Vol. 3. — 2000. — Pp. 959-962.

103. Shape characterization with the wavelet transform / J.-P. Antoine, D. Barache, R. M. C. Jr., L. da Fontoura Costa // Signal Processing.— 1997.- Vol. 62,- Pp. 265-290.

104. Shaw J. A., Fox E. A. Combination of multiple searches. — Electronic resource. — 1994. http://citeseer.ist.psu.edu/fox94combination.html.

105. Shi S., Song R., Wen J.-R. Latent additivity: Combining homogeneous evidence: Tech. rep.: Microsoft Research, 2006.— August.

106. Shock graphs and shape matching / K. Siddiqi, A. Shokoufandeh, S. J. Dickinson, S. W. Zucker // International Journal of Computer Vision. 1999. - Vol. 35, no. 1. - Pp. 13-32.

107. Smith J., Chang S. VisualSEEk: a fully automated content-based image query system // Proceedings of the fourth ACM international conference on Multimedia. ACM Press New York, NY, USA, 1997. - Pp. 87-98.

108. Smith J. R., Chang S.-F. Transform features for texture classification and discrimination in large image databases // IEEE International Conference on Image Processing (ICIP-94). — 1994. — November. — Pp. 407-411.

109. Smith J. R., Chang S.-F. Single color extraction and image query // International Conference on Image Processing (ICIP-95).— Vol. 3. — 1995. — Pp. 528-531.

110. Smith J. R., Chang S.-F. Tools and techniques for color image retrieval // Storage and Retrieval for Image and Video Databases (SPIE). — 1996. — Pp. 426-437. citeseer.ist.psu.edu/article/smith96tools.html.

111. Snitkowska E., Kasprzak W. Independent component analysis of textures in angiography images // Computational Imaging and Vision. — 2006. — Vol. 32,-Pp. 367-372.

112. Stanchev P. L. Content-based image retrieval systems // Bulgarian Computer Science Conference CompSysTech'2001.— 2001. —June.— Pp. 1-6.

113. Statistical learning for effective visual information retrieval / E. Chang, В. T. Li, G. Wu, K. S. Goli // IEEE International Conference on Image Processing (ICIP 2003).- 2003,- Pp. 609-612.

114. Strieker M., Dimai A. Color indexing with weak spatial constraint // SPIE Conference on Visual Communications. — Vol. 2670. — 1996. — Pp. 29-40.

115. Strieker M., Dimai A. Spectral covariance and fuzzy regions for image indexing // Mach. Vision Appl.- 1997. Vol. 10, no. 2,- Pp. 66-73.

116. Strieker M., Orengo M. Similarity of color images // Storage and Retrieval for Image and Video Databases (SPIE).— 1995,— Pp. 381392.

117. Supporting similarity queries in MARS / M. Ortega, Y. Rui, K. Chakrabarti et al. // MULTIMEDIA '97: Proceedings of the fifth ACM international conference on Multimedia. — New York, NY, USA: ACM, 1997. Pp. 403-413.

118. Sural SQian G., Pramamk S. A histogram with perceptually smooth color transition for image retrieval // Fourth International Conference on Computer Vision, Pattern Recognition and Image Processing. — 2002.

119. Swain M. J., Ballard D. H. Color indexing // International Journal of Computer Vision. — 1991.— Vol. 7, no. 1.— Pp. 11-32.

120. Szummer M., Pieard R. W. Indoor-outdoor image classification // IEEE International Workshop on Content-Based Access of Image and Video Database (CAIVD 1998). 1998. - Pp. 42-51.

121. Tamura H., Mori S., Yamawaki T. Textural features corresponding to visual perception // IEEE Transactions on Systems, Man and Cybernetics. 1978. — June. - Vol. 8. — Pp. 460-473.

122. Teague M. Image analysis via the general theory of moments // Journal of the Optical Society of America. — 1980. — August. — Vol. 70, no. 8. — Pp. 920-930.

123. A texture descriptor for browsing and similarity retrieval / B. S. Manjunath, P. Wu, S. Newsam, H. D. Shin // Signal Processing Image Communication.— 2000. — September. — Vol. 16, no. 1-2.— Pp. 33-43.

124. Thyagarajan К. S., Nguyen Т., Persons С. E. A maximum likelihood approach to texture classification using wavelet transform // IEEE International Conference on Image Processing (ICIP-94).— Vol. 2,— 1994. November. - Pp. 640-644.

125. Tianhorng C., Jay C.-C. K. Texture analysis and classification with tree-structured wavelet transform // IEEE Transactions on Image Processing. — 1993. Vol. 2, no. 4. - Pp. 429-441.

126. Tuceryan M., Jain A. Texture segmentation using voronoi polygons // IEEE Transactions on Pattern Analysis and, Machine Intelligence. — 1990. Vol. 12, no. 2. - Pp. 211-216.

127. Tuceryan M., Jain A. K. Texture analysis // The Handbook of Pattern Recognition and Computer Vision / Ed. by С. H. Chen, L. F. Pau, P. S. P. Wang.-— 2nd edition edition. — World Scientific Publishing Co., 1998. Pp. 207-248.

128. Vailaya A., Jain A. K., Zhang H.-J. On image classification: City images vs. landscapes // Pattern Recognition.— 1998.— Vol. 31, no. 12.— Pp. 1921-1935.

129. Vapnik V. N. The Nature of Statistical Learning Theory. Statistics for Engineering and Information Science. — 2nd edition. — New York: Springer-Verlag, 2000. — 314 pp.

130. Vasconcelos N., Lippman A. A bayesian framework for content-based indexing and retrieval // Conference on Data Compression Conference (DCC 1998).- 1998.- P. 580.

131. Vassilieva N., Novikov B. A similarity retrieval algorithm for natural images // 6th International Baltic Conference on Databases and Information Systems (Baltic DB&IS 2004).- Vol. 673.- 2004,-Pp. 151-154.

132. Virage image search engine: an open framework for image management /

133. J. R. Bach, C. Fuller, A. Gupta et al. // SPIE Storage and Retrieval for Still Image and Video Databases IV. Vol. 2670. - 1996. - Pp. 77-87.

134. Wan X., Kuo C.-C. Color distribution analysis and quantization for image retrieval // SPIE Storage and Retrieval for Still Image and Video Databases IV / Ed. by I. K. Sethi, R. C. Jain.- Vol. 2670,- 1996.-Pp. 8-16.

135. Wand M. P. Data-based choice of histogram bin width // The American Statistician. — 1997. Vol. 51, no. 1.

136. A weighted distance approach to relevance feedback / S. Aksoy, R. M. Haralick, F. A. Cheikh, M. Gabbouj // IAPR International Conference on Pattern Recognition. — 2000.

137. Zernike polynomials. — Wikipedia, the free encyclopedia. http://en.wikipedia.org/wiki/Zernikepolynomials.

138. Zhang D., Lu G. A comparative study on shape retrieval using fourier descriptors with different shape signatures // International Conference on Multimedia. — 2001.

139. Zhang D., Lu G. Review of shape representation and description techniques // Pattern Recognition. — 2004.— Vol. 37. — Pp. 1-19.

140. Zhang D. S., Lu G. Generic fourier descriptor for shape-based image retrieval // IEEE International Conference on Multimedia and Expo (ICME2002).-Vol. 1,- 2002.-August. Pp. 425-428.

141. Zhang D. S., Lu G. Shape-based image retrieval using generic fourier descriptor // Signal Processing: Image Communication. — 2002. — Vol. 17. Pp. 825-848.

142. Zhou Z.-H., Dai H.-B. Query-sensitive similarity measure for content-based image retrieval // International conference on Data Mining. — 2006. Pp. 1211-1215.