Содержание к диссертации
Введение
1. Методы поиска изображений по содержанию 14
1.1. Направления исследований в области CBIR 14
1.2. Основные проблемы CBIR 16
1.3. Построение векторов признаков: классификация подходов . 17
1.4. Цвет 18
1.4.1. Цветовые пространства 19
1.4.2. Цветовые гистограммы 20
1.4.3. Цветовые моменты 25
1.4.4. Сравнение цветовых признаков 27
1.5. Текстура 28
1.5.1. Матрицы смежности 30
1.5.2. Признаки Тамуры 33
1.5.3. Использование вейвлет-преобразования 34
1.5.4. Использование фильтров Габора 38
1.5.5. Использование фильтров ICA 39
1.5.6. Сравнение текстурных признаков 39
1.6. Контуры и объекты 41
1.6.1. Дескрипторы границ 43
1.6.1.1. Простые дескрипторы границ 43
1.6.1.2. Цепные коды 44
1.6.1.3. Сигнатуры 46
1.6.1.4. Дескрипторы Фурье 48
1.6.1.5. Другие дескрипторы границ 50
1.6.2. Дескрипторы областей 52
1.6.2.1. Простые дескрипторы областей 52
1.6.2.2. Грид-метод (Grid based method) 52
1.6.2.3. Моменты и их инварианты 54
1.6.2.4. Общие дескрипторы Фурье (GFD) 57
1.6.2.5. Декомпозиция объектов 58
1.6.3. Сравнение признаков формы 59
1.7. Комбинирование различных методов поиска 61
1.8. Обзор существующих систем 64
2. Поиск по цвету 66
2.1. Выбор схемы квантования при построении цветовой гисто граммы 67
2.1.1. Выбор цветового пространства 67
2.1.2. Выбор схемы квантования 70
2.2. Учет пространственного расположения цветов 73
2.3. Эффективность поиска по цветовым гистограммам 76
2.3.1. Описание экспериментов 76
2.3.2. Анализ результатов 79
2.3.2.1. Учет пространственного расположения цветов 80
2.3.2.2. Снижение зависимости от условий освещенности 84
2.3.2.3. Выбор шага квантования 88
2.4. Выводы 96
3. Синтез методов поиска при формировании результатов 99
3.1. Взвешенное среднее с гравитационной функцией 99
3.1.1. Постановка задачи 100
3.1.1.1. Поиск в частично аннотированной коллекции изображений 100
3.1.1.2. Синтез результатов методов поиска по низкоуровневым признакам 101
3.1.1.3. Формализация задачи синтеза методов поиска 101
3.1.2. Функция синтеза WTGF 102
3.1.2.1. Свойства функции синтеза 102
3.1.2.2. Функция стабилизации высокоранговых элементов и правила конусов 105
3.1.2.3. Реализация вычислений 107
3.1.3. Описание экспериментов 109
3.1.3.1. Поиск по частично аннотированной базе . 109
3.1.3.2. Синтез методов поиска по содержанию . 110
3.1.4. Анализ результатов 111
3.1.4.1. Метод оценки алгоритмов синтеза 111
3.1.4.2. Поиск в частично аннотированной коллекции 113
3.1.4.3. Синтез методов поиска по содержанию . 117
3.1.4.4. Обсуждение результатов 120
3.2. Адаптивный синтез методов поиска по цвету и текстуре . 121
3.2.1. Постановка задачи 122
3.2.2. Выбор оптимальных весов для комбинирования результатов поиска по цвету и текстуре в зависимости от запроса-образца 123
3.2.2.1. Описание эксперимента 124
3.2.2.2. Анализ результатов 125
3.2.3. Сравнение методов адаптивного синтеза и CombMNZ 129
3.2.3.1. Описание эксперимента 130
3.2.3.2. Анализ результатов 131
3.2.4. Классификация запроса 133
3.2.4.1. Построение низкоуровневых центроидов для групп визуально подобных изображений . 134
3.2.4.2. Использование классических алгоритмов классификации 139
3.3. Выводы 144
Заключение 146
Библиография 148
- Построение векторов признаков: классификация подходов
- Учет пространственного расположения цветов
- Функция стабилизации высокоранговых элементов и правила конусов
- Выбор оптимальных весов для комбинирования результатов поиска по цвету и текстуре в зависимости от запроса-образца
Введение к работе
Актуальность работы
Исследованию вопросов, связанных с индексированием и поиском изображений, уделяется много внимания на протяжении последних десятилетий. Этому способствуют многие факторы, среди которых рост доступных объемов памяти и широкое распространение цифрової! фотографии, и, как следствие, рост числа и объемов коллекций изображений. Но любые коллекции данных бесполезны без возможности удобного и быстрого поиска по ним.
Можно выделить два подхода к решению задачи поиска графической информации.
Исторически первым является поиск по текстовым аннотациям (Description Based Image Retrieval, DBIR). Данный подход подразумевает наличие у всех изображений коллекции текстовых аннотаций, описывающих их содержание, по которым и производится поиск. Таким образом, задача поиска изображений сводится к классической задаче текстового поиска.
Вторым подходом к поиску изображений является поиск по содержанию (Content Based Image Retrieval, CBIR)1. Методы поиска по содержанию работают на основе анализа численных характеристик составляющих изображение пикселей и не требуют наличия текстовых аннотаций или другой дополнительной информации об изображении. Это позволяет избежать трудоемкости и субъективности составленных вручную аннотаций, неточности аннотаций, полученных автоматически или полуавтоматически.
1В англоязычной литературе по машинному зрению (computet vision) также можно встретить тор-мины Query By Image Content (QBIC) и Content-Based Visual Information Retrieval (CBVIR).
Поиск по содержанию является приоритетным направлением исследований, поскольку данный подход предполагает автоматическое построение индекса и не требует дополнительной информации об изображениях. Однако на сегодняшний день эффективность систем поиска по содержанию значительно уступает эффективности поиска по аннотациям. Основной проблемой поиска по содержанию большинство исследователей признают так называемый „семантический разрыё1. Человек, сравнивая два изображения, в первую очередь сравнивает их смысловое наполнение - семантику, в то время как оценка системы основывается на сравнении низкоуровневых (визуальных) характеристик изображения, таких как цвет, текстура и форма объектов. Задачи уменьшения семантического разрыва и повышения эффективности поиска по содержанию являются актуальными в области поиска изображений и информационного поиска в целом.
При поиске по содержанию каждое изображение коллекции описывается в системе векторами признаков (feature vector) (или просто признаками) - наборами числовых параметров, отражающих свойства низкоуровневых характеристик изображения. Вектора признаков принимают значения в пространстве признаков. Задав метрику на таком пространстве, можно сравнивать изображения друг с другом, вычисляя расстояние между соответствующими им векторами. Алгоритмы построения векторов признаков являются ядром любой системы поиска по содержанию. От выбора признаков и метрик для их сравнения зависит качество поиска системы.
Традиционным подходом для поиска по содержанию является независимый поиск по различным характеристикам изображения, каждая из которых описывается точкой в соответствующем пространстве признаков. Некоторые системы используют несколько пространств признаков для описания одной и той же характеристики с целью повышения точности поиска. В таком случае поиск в каждом из пространств признаков также производится независимо. Для получения общей выдачи - комбинирования промежуточных результатов поиска по каждому из пространств признаков, используются методы синтеза данных (Data Fusion). Под выдачей здесь понимается ранжированный набор объектов поиска, представляющий собой ответ поисковой системы на заданный запрос.
Качество результатов поиска зависит от выбора признаков, а также от используемых методов синтеза. Ежегодно публикуются сотни работ, посвященные задаче построения наиболее эффективных признаков, в то время как проблеме синтеза данных в контексте поиска изображений уделяется недостаточное внимание. Распространенным решением для комбинирования результатов поиска по различным признакам является использование линейной комбинации рангов изображения-ответа в каждой из промежуточных выдач для вычисления его ранга в общей выдаче. Однако на примере текстового поиска известно, что линейная комбинация является не самым эффективным методом синтеза. Это дает основание предположить, что для поиска изображений могут быть также найдены более эффективные методы.
Цели и задачи работы
Основной целью работы является создание высокоэффективных с точки зрения качества результата методов поиска по содержанию для коллекций изображений произвольной тематики, позволяющих уменьшить семантический разрыв. Повышение качества результатов поиска возможно за счет построения более эффективных признаков, а также за счет синтеза различных методов поиска.
Для достижения поставленной цели были выделены следующие задачи:
Разработка эффективного цветового признака в соответствии с особенностями зрительного восприятия человека. Цвет является наиболее значимой характеристикой при поиске по коллекции цветных изображений произвольной тематики. Он играет огромную роль в механизме зрительного восприятия человека. Помимо этого, цвет изображения достаточно просто анализировать, он инвариантен относительно размера изображения и ориентации расположенных на нем объектов.
Формулирование требований к методам синтеза в контексте задачи поиска изображений.
Разработка эффективных методов синтеза для комбинирования результатов поиска по различным пространствам признаков.
Основные результаты, выносимые на защиту
На защиту выносятся:
Новый цветовой признак на основе цветовой гистограммы, учитывающий пространственное расположение цветов, и функция расстояния для соответствующего пространства признаков.
Рекомендации по выбору оптимальной схемы квантования цветового пространства при построении цветовой гистограммы в зависимости от используемой метрики и размеров коллекции, полученные по результатам экспериментального исследования.
Требования к универсальным (не зависящим от изображения-запроса) методам синтеза для комбинирования результатов поиска но различным пространствам признаков. Метод синтеза с использованием среднего взвешенного с гравитационной функцией (WTGF - Weighted Total with Gravitation Function), удовлетворяющий сформулированным требованиям.
Алгоритм поиска в частично аннотированной коллекции изображений по текстовому запросу, не требующий предварительного автоан-нотпрования всей коллекции. В основе алгоритма лежит идея использования методов синтеза.
Адаптивный метод синтеза результатов поиска по цветовым и текстурным признакам в зависимости от изображения-запроса, центро-идный метод классификации запроса.
Научная новизна работы
В работе предложен новый цветовой признак изображений на основе гистограммы, отражающий пространственное расположение цветов, и функция расстояния для соответствующего пространства признаков.
Сформулированы требования к методам синтеза результатов поиска применительно к задаче поиска изображений, а также предложено два новых метода синтеза: взвешенное среднее с гравитационной функцией и адаптивный синтез в зависимости от изображения-запроса. Предложен центроидный метод классификации изображения-запроса в рамках решения задачи адаптивного синтеза.
Предложен алгоритм поиска в частично аннотированной коллекции изображений по текстовому запросу, не требующий предварительного автоаннотирования всей коллекции.
Практическая ценность
Методы сравнения и поиска изображений по содержанию находят широкое применение а различных областях жизнедеятельности человека: в медицине (например, поиск пациента со схожим диагнозом по рентгеновскому снимку), в промышленности (контроль качества продукции по контрольным снимкам), для защиты авторских прав (поиск копий авторской фотографии), и другие. Все больше людей пользуются поиском изображений в Интернете. Крупные поисковые системы, такие как Google, Yandex, Yahoo и другие, предлагают пользователям поиск изображений по ключевым словам, построенным по контексту изображения и не используют анализ содержания изображений. Эффективные методы поиска по содержанию помогут значительно дополнить результаты поиска таких систем и повысить их качество.
В рамках данной работы разработан прототип системы поиска изображений по содержанию. Экспериментально доказана эффективность предложенных методов поиска по цвету и синтеза результатов поиска по различным пространствам признаков. Также практическую ценность имеет
предложенный алгоритм поиска по текстовому запросу в частично аннотированных коллекциях изображений.
Апробация работы и публикации
Основные результаты диссертации докладывались на Между народных Балтийских Конференциях по Базам Данных и Информационным Системам Baltic DBMS 2004, Baltic DB&IS 2008; на Всероссийских Научных Конференциях по Электронным Библиотекам RCDL 2005, RCDL 2007; на семинаре по итогам конкурса Интернет-Математика 2007; на семинаре Московской Секции ACM SIGMOD; на Международной Конференции по Обработке Изображений и Сигналов ICISP 2008; на Российском семинаре по Оценке Методов Информационного Поиска РОМИП 2008; на семинарах группы исследования методов организации информации при лаборатории исследования операций НИММ и опубликованы в работах [1-5,8,84-86,139].
Структура диссертации
Диссертация состоит из введения, трех глав и заключения.
Первая глава содержит обзор методов поиска изображений по содержанию.
Описываются направления и задачи данной области. Представлены основные алгоритмы построения векторов признаков и метрики для соответствующих пространств, обсуждаются их достоинства и ограничения. Приводится подробная классификация известных на сегодняшний день признаков, а также результаты экспериментальных сравнений эффективности различных методов представления и сравнения содержания изображений применительно к задачам поиска и классификации.
В главе также обсуждаются известные на сегодняшний день подходы к комбинированию различных признаков с целью повышения качества результатов поиска.
Наиболее эффективные и широко используемые признаки и методы синтеза из числа рассмотренных используются в дальнейшем исследовании для сравнения и в качестве отправной точки для разработки более эффективных решений.
Вторая глава посвящена вопросам поиска изображений по цветовым признакам.
Построение векторов признаков: классификация подходов
Алгоритмы построения векторов признаков и метрики, используемые для их сравнения, составляют основу любой системы CBIR. Все алгоритмы поиска по содержанию можно разделить на классы в зависимости от ха рактеристики, которую использует тот или иной алгоритм: поиск по цвету, по текстуре, по форме (рис. 1.2). Каждый из этих классов в свою очередь делится на подклассы по типу алгоритма построения вектора признака. Некоторые исследователи выделяют в отдельный класс пространственные признаки изображений [46,103]. Под пространственными признаками понимают признаки, отражающие пространственное расположение на изображении областей, однородных по какой-либо характеристике: одного цвета, с однородной текстурой, распознанный объект. Можно сказать, что это признаки одного из классов (цвет, текстура, форма) с дополнительной информацией о пространственном расположении. Поэтому по мнению автора выделение в отдельный класс пространственных признаков на данном уровне не совсем правомерно. Ниже будут рассмотрены основные алгоритмы построения векторов признаков для цвета, текстуры и формы объектов. Для каждого из этих классов будет приведена более подробная классификация в соответствующем разделе.
При поиске по коллекции цветных изображений произвольной тематики цвет наиболее значимая характеристика. Он играет огромную роль в механизме зрительного восприятия человека. Кроме того, цвет изображения достаточно просто анализировать, он инвариантен относительно размера изображения и ориентации расположенных на нем объектов. Этим можно объяснить тот факт, что цветовая характеристика является самой используемой при поиске изображений, а также то, что существует сравнительно небольшое количество принципиально различающихся подходов. Все методы представления цветовой характеристики изображения можно разделить на два класса: цветовые гистограммы [27,126,127] и статистическая модель представления цвета [122-124] (рис. 1.3).
Качество векторов признаков, представляющих цвет изображения, во многом зависит от выбора цветового пространства. Хорошими признаками являются такие, сравнение которых позволяет сделать правильный вывод о схожести изображений, по которым они были построены.
Цветовое пространство (называемое также цветовой моделью или системой цветов) [6,30] определяет систему координат и подпространство в этой системе, в котором каждый цвет представляется единственной точкой. Таким образом каждый цвет в определенном цветовом пространстве имеет свои цветовые координаты.
Наиболее известными и широко используемыми на практике цветовыми пространствами являются: RGB: Red - красный, Green - зеленый, Blue - синий (цветные мониторы и видеокамеры); CMY и CMYK: Cyan - голубой, Magenta - пурпурный, Yellow - желтый, ЫасК - черный (цветные принтеры);
HSV: Hue - оттенок, Saturation - насыщенность, Value - значение; цветности, от зеленого до красного и от синего до желтого.
Пространство Lab основано на разработке международной комиссии по освещению CIE (Commission International de l Eclairage) международного стандарта измерения цветов. Близкими к пространству HSV являются пространства HSI (Intensity - интенсивность), HSL (Lightness - светлота), HSB (Brightness - яркость) (будем далее их называть пространствами семейства HSV). Большинство пространств для представления полноцветных изображений трехмерны.
Традиционным пространством для представления цифровых изображений является RGB. Однако это пространство не является зрительно однородным: равноудаленность точек А и В от точки О в пространстве RGB не означает, что для человека цвета, соответствующие точкам А и В, будут одинаково похожи (или не похожи) на цвет, соответствующий точке О. Лучше соответствуют цветовосприятию человека пространство Lab и пространства семейства HSV. Эти пространства также обладают тем преимуществом, что они позволяют разделить цветовую и яркостную информацию, что удобно при обработке изображений. Поэтому большинство исследователей строят вектора признаков для цвета в одном из этих пространств. Использование пространства HSV более распространено из-за того, что перевод RGB -» HSV вычислительно проще, чем перевод RGB -» Lab. Также при построении цветовых признаков иногда используют нормированное пространство RGB (normalized RGB, nRGB) [87]. Преимущество этого пространства в независимости координат цветовых точек от уровня освещенности.
Учет пространственного расположения цветов
Пирамида гауссиа-нов представляет собой набор изображений в уменьшающемся масштабе, к которым был применен низкочастотный гауссов фильтр для сглаживания ступенчатости контуров изображений небольших разрешений. Пирамида лаплассианов содержит изображение минимального разрешения и разности для каждого последующего уровня между изображением, восстановленным по изображению меньшего разрешения, и исходным изображением данного уровня.
На сегодняшний день вейвлет-анализ широко используется в области анализа и обработки изображений. В первую очередь это задачи сжатия изображений. Но также данный метод широко используется для решения задач классификации и анализа текстур изображений. Вейвлет-анализ представляет собой разложение сигнала по специальному базису. Базисные функции (вейвлеты) строятся на основе одной функции - порождающего вейвлета при помощи сдвига и масштабирования. Для анализа текстуры изображения сначала строится первая проекция сигнала (вычисляется свертка с первой базисной функцией). Далее для разности исходного сигнала и полученной проекции вычисляется свертка со следующей базисной функцией. На каждом следующем шаге берется разность двух предыдущих проекций для проецирования на следующую базисную функцию. При этом каждая следующая базисная функция является сдвигом предыдущей, растянутой в 2" раз, где п характеризует масштаб. Иными словами, задача состоит в том, чтобы разложить сигнал на его "грубую" крупномасштабную версию и набор "деталей", отличающих версии промежуточных масштабов друг от друга. Проекции сигнала на каждом уровне можно рассматривать как его поддиапазоны (subbands). Текстура изображения характеризуется набором энергий полученных поддиапазонов. Базисные функции, используемые для разложения сигнала, часто называют фильтрами.
Smith и Chang использовали в качестве текстурных признаков статистические показатели (математическое ожидание и дисперсию), вычисленные для каждого из поддиапазонов [116]. В своей работе они сравнили эффективность классификации текстур для признаков, построенных с помощью вейвлет-подхода, однородного разложения на поддиапазоны (без масштабирования, каждый поддиапазон содержит часть сигнала определенной частоты), дискретного косинусного преобразования и пространственного разбиения. Эксперимент проводился на коллекции текстур Brodatz3. Наилучший результат был получен для вейвлет-подхода и однородного разложения: точность результата по данным авторов превышает 90%.
Однако у такого вейвлет-преобразования (его называют пирамидальным - Pyramidal Wavelet Transform, PWT) есть недостаток: величины полученного ряда частотных диапазонов находятся в логарифмическом отношении. В результате только низкие частоты представляются с достаточной степенью детализации. В то же время, для естественных текстур характерно преобладание средних частот. Эта проблема может быть решена при использовании обобщения - вейвлет-пакетов (их таже называют вейвлет-деревьями - Tree Wavelet Transform, TIFT), предложенных в 1992 году Coifman и Wickerhauser [29]. В [24] Chang и Kuo Jay приводят результаты экспериментов по сравнению эффективности различных преобразований для получения текстурной характеристики, включая вейвлет-деревья, пирамидальное вейвлет-нреобразование, DCT, DST, DHT, в контексте задачи классификации текстур. Набор экспериментов показал, что вейвлет-деревья в целом выигрывают у остальных подходов.
Для достижения лучших результатов в решении задач классификации и распознавания текстур предпринимались попытки комбинировать вейвлет-подход с другими известными методами. В работе [132] Thyagarajan и соавторы добились точности в 99.7% при классификации текстур, комбинируя вейвлет-подход с матрицами смежности - матрицы смежности строились по результатам вейвлет-преобразования. Balmelli и Mojsilovic построили признаки по данным, полученным в результате вейвлет-преобразований сигнала, соответсвующие важным для восприятия человеком свойствам текстуры [14]. Эта работа объединила вейвлет-подход и основные идеи признаков Тамуры. Эксперименты показали успешность данного метода: доля неправильно классифицированых текстур не превышала 1%; доля текстур, не отнесенных к нужному классу варьировалась от менее 1% до 5% для различных классов. Еще одной модификацией классического вейвлет-подхода можно считать рассматриваемое в [67] комплексное вейвлет-преобразование. Данный метод решает такие проблемы, присущие классическому преобразованию, как чувствительность результата к небольшим сдвигам сигнала (в силу масштабируемости) и недостаточная чувствительность к направленности диагональных элементов (в силу вещественности и сепарабельности классических веивлет-фильтров).
Помимо преобразования, применяемого для разложения сигнала, и способов параметризовать его результаты, на качество классификации и распознавания текстур также влияет выбранная функция подобия для сравнения признаков различных текстур. Поиску лучших функций для сравнения текстурных признаков уделено внимание в работах [36,110,132]. В [110,132] предлагается воспользоваться методом максимального правдоподобия для вывода оптимальной функции подобия, исходя из предположений о характере распределения текстурных признаков. В [132] авторы исходят из предположения о гауссовом распределении, в [110] рассматриваются гипотезы гауссова, экспоненциального и распределения Коши. Эксперименты в [110] показали, что метрика, соответствующая распределению Коши, дает более высокую точность при классификации текстур. Авторы [36] предлагают использовать модификацию расстояния Кульбака — Лейблера (Kullback-Leibler divergence) для оценки подобия текстурных характеристик в задаче поиска, что значительно улучшает результат по сравнению с часто используемым евклидовым расстоянием.
Функция стабилизации высокоранговых элементов и правила конусов
Свойства (1)-(4) функции синтеза, рассмотренные в разделе 3.1.2.1, не учитывают весов списков. Введем дополнительное свойство, устраняющее этот недостаток. Назовем его свойством взвешенной стабилизации высокоранговых элементов. Введем следующие правила (мы назвали их "правилами конусов"). Выполнение граничных условий. — Если есть список с весом, близким к единице, и в нем есть объект с рангом, почти равным единице, то вероятность того, что ранг изменится после синтеза, очень мала. — При синтезе двух списков, один из которых обладает весом, близким к нулю, таковой почти не вносит вклада в результат (за исключением добавления новых элементов). При этом высока вероятность того, что, его элементы изменят свой ранг. Влияние весов списков. Если есть два элемента (х Є а.\ и у Є а2) из списков с различными весами (wi W2), но с одинаковыми рангами (ri(x) — Г2(у)), то в результирующем списке их ранги должны быть различны, причем 7(ж) г0(у). Степень свободы низкоранговых элементов. Чем меньше ранг элемента, тем больше степень свободы изменения его ранга в результирующем списке. Степень свободы высокоранговых элементов в списках с высоким весом. Чем больше ранг элемента и выше вес списка, в котором он встречается с высоким рангом, тем меньше степень свободы изменения его ранга в результирующем списке. Согласованность. Незначительные изменения веса списка или ранга элемента не должны повлечь значительных изменений результирующего ранга элемента. Теперь мы можем добавить новое условие к списку свойств функции синтеза - свойство взвешенной стабилизации высокоранговых элементов. Свойство 5 Для функции синтеза должны выполняться "правила конусов".
Рассмотрим функцию взвешенного среднего для вектора: где Rx = (ГІ(ГЕ),Г2(Ж), ..., грі(х)), Wi - вес списка оц. Данная функция удовлетворяет свойствам (1)-(4) и учитывает веса списков, но не удовлетворяет свойству (5). Пусть имеется некоторый список а с весом w. Для каждого элемента х : Чг(х) (х,г(х)) Є а\ г(х) 0 можно рассмотреть функцию, зависящую от веса списка w и от ранга элемента в списке r(x): g(r(x),w). Эту функцию мы назвали функцией стабилизации высокоранговых элементов или гравитационной функцией. Она определена в области [0 ... 1,0 ... 1], непрерывна и монотонна, убывает по обоим параметрам. Ее задача заключается в выработке компромисса между мнениями различных источников с учетом как рангов элементов, так и весов самих источников. Для выполнения свойства (5) заменим в формуле 3.1 вес списка wi на функцию стабилизации высокоранговых элементов. g(ri(x),Wi): В качестве функции д возьмем следующую функцию: Такой вид функции объясняется условиями нашей задачи: зависимость ранга и веса должна быть мультипликативной; мы не должны учитывать мнение списка с нулевым весом, элемент сколь высокого ранга в нем бы не содержался; ситуация, когда Эг : п(#) = 0 то есть объект х не присутствует в списке «г, должна уменьшать значение результирующего ранга объекта х, если вес списка аг- не равен нулю; функция должна быть монотонна и непрерывна по обоим параметрам. Константы степеней (2, 4) и сдвига ранга (1/12) были определены экспериментальным образом, с учетом особенностей данных и использовавшихся методов поиска.
Получившейся функции 3.2 была присвоена аббревиатура WTGF (Weighted Total with Gravitation Function) - взвешенное среднее с гравитационной функцией. Синтез при помощи функции WTGF можно осуществлять двумя способами. 1) Последовательно использовать формулу 3.2 для одинаковых элементов из всех исходных списков. 2) Комбинировать списки попарно, затем повторять ту же процедуру для получившихся результатов и т. д. У обоих вариантов есть свои плюсы и минусы, оба поддаются распараллеливанию. Основной минус первого варианта заключается в вычислительной сложности поиска одинаковых объектов в разных списках. Основной минус второго - использование дополнительной памяти для хранения промежуточных результатов. При реализации экспериментов в рамках данной работы была использована схема на основе попарного синтеза отсортированных списков (вариант 2). Основные шаги алгоритма следующие: 1) производится сортировка элементов списков по идентификатору; 2) в конец, каждого списка добавляется специальный граничный элемент; 3) производится сортировка слиянием путем попарного синтеза двух списков с вычислением нового ранга для элементов по формуле 3.2. 4) производится сортировка элементов результирующего списка по их рангам. Такая реализация добавляет к методу WTGF суффикс МТ (Merge by Two).
При попарном смешивании списков вес результирующего списка вычисляется по формуле: Описанные выше алгоритмы были реализованы с использованием продуктов Microsoft: база данных была размещена на MSSQL Server 2005, алгоритмы написаны на языке С#. Для интеграции с MSSQL Server 2005 использовались возможности среды .NET. Код разрабатывался на тестовой версии Visual Studio 2005. 3.1.3. Описание экспериментов 3.1.3.1. Поиск по частично аннотированной базе В эксперименте по оценке эффективности функций синтеза применительно к решению задачи поиска в частично аннотированной базе по схеме, описанной в разделе 3.1.1.1, использовалась база из 14407 изображений, полученных с сайта фотогалереи Flickr1. В ней присутствуют как изображения, аннотированные ключевыми словами, так и изображения без аннотаций. Аннотирование производилось пользователями, загружающими изображения на сайт. Поиск по содержанию производился по цветовым гистограммам с учетом пространственного расположения цветов HistSP (см. раздел 2.2). Для реализации полнотекстового поиска использовался компонент MSFTS корпорации Microsoft, включенный в поставку СУБД MSSQL Server 2005. Для проведения эксперимента была создана тестовая база односложных запросов. В качестве тестовых запросов было выбрано 100 наиболее часто встречающихся в базе ключевых слов. Оценка производилась для следующих функций синтеза.
Выбор оптимальных весов для комбинирования результатов поиска по цвету и текстуре в зависимости от запроса-образца
Проверим гипотезу о том, что можно определить оптимальные коэффициенты для комбинирования оценок по цвету и текстуре в зависимости от признаков запроса. Для проверки сформулированной гипотезы проведем следующий эксперимент.
В качестве экспериментальной базы изображений возьмем подмножество из 285 фотографий Corel Photo Set различной тематики: природа, городские пейзажи, фотографии людей и животных. Отобранные изображения могут рассматриваться как обучающее множество для построения классов семантически близких изображений. Для каждого изображения вычислим цветовые и текстурные признаки, и для каждой пары вычислим расстояния в обоих пространствах признаков с использованием соответствующих метрик. Для нормировки цветовых и текстурных расстояний будем использовать следующее преобразование. где di - расстояние между изображениями -ой пары в заданном пространстве признаков, d - среднее расстояние для всех пар изображений в заданном пространстве признаков, а - дисперсия расстояний в заданном пространстве признаков, d[ - нормированное значение расстояния между изображениями г-ой пары.
После применения данного преобразования значения цветовой и текстурной метрик будут иметь одинаковые среднее и дисперсию. В этом случае основная масса данных будет иметь единичный масштаб, то есть типичные значения обеих метрик будут сравнимы.
Для эксперимента было отобрано пять значений параметра а : О, 0.25, 0.5, 0.75 и 1, что дает пять различных смешанных метрик (первая и последняя совпадают с текстурной и цветовой, соответственно).
Экспериментальный стенд представляет собой интерактивную систему, цель работы которой — выяснить субъективное мнение людей о подобии изображений. Внешний вид основного окна стенда представлен на рис. 3.6.
Слева отображается случайным образом выбранное изображение-образец, а основную часть экрана занимает результат поиска, полученный с применением смешанной метрики со случайно выбранным параметром а (из пяти возможных значений). Участнику эксперимента (асессору) предлагается оценить похожесть образца и каждого из полученных изображений по трехбалльной шкале: "совсем не похожи", "немного похожи", "похожи". В качестве результата оценки сохраняется пара сравниваемых изображений и сама оценка (соответственно, 0, 0.5, 1).
Для разделения результатов, полученных от разных асессоров, введена предварительная регистрация. Каждый участник может пройти любое количество итераций сравнения, на каждой из которых случайным образом выбирается изображение-образец и смешанная метрика для поиска похожих изображений.
Статистика, собранная в результате участия в эксперименте порядка 160 добровольцев, была обработана следующим образом. Для каждой пары изображений была вычислена средняя оценка по всем участникам экспе где Su(Ii, Ij) Є {О,0.5,1} - оценка подобия пары изображений Д и Ij, данная участником и, users - множество всех участников эксперимента.
На основании полученной информации изображения были разбиты на кластеры близких изображений. В процессе кластеризации участвовали только те пары, которые получили оценку от не менее thuser участников. Каждый кластер формировался таким образом, чтобы для любого изображения, входящего в него, существовало хотя бы одно изображение из того же кластера такое, что средняя пользовательская оценка для этой пары (Savg(Ii)Ij)) была не меньше заданного порогового значения кластеризации thduster Среди полученных кластеров рассматривались только те, размер которых не меньше thSize. При анализе результатов использовались следующие значения параметров:
В ходе предварительного анализа кластеров, полученных при различных значениях параметра thuser, было принято решение в дальнейшем рассматривать только кластеры, полученные npnthuser = 4. Для значительной части кластеров, полученных при thuser = 3 и thuser = 5, имелись идентичные кластеры, полученные при thuser — 4. Большинство из оставшихся кластеров при thnser = 3 оказались неоднородными, и по этой причине не представляли ценности для дальнейшего изучения.
