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

Семинар Московской Секции ACM SIGMOD, 29.11.2007
План
Основные направления исследований
Уровни содержания изображения
Цвет
Текстура
Форма объектов
I. Обзор методов поиска изображений
II. Синтез данных в контексте CBIR
Существующие решения и их недостатки
Альретнативные подходы
Поиск в частично-аннотированной базе
WTGF: Weighted Total with Gravitation Function
Адаптивный поиск

Семинар Московской Секции ACM SIGMOD, 29.11.2007
CBIR: направления исследований
Традиционная архитектура систем CBIR
Выделение признаков изображений
Многомерное индексирование
Проектирование систем поиска
Поиск по содержанию – Content Based Image Retrieval (CBIR)

Семинар Московской Секции ACM SIGMOD, 29.11.2007
Уровни содержания изображения
уровни содержания изображения
Семантика
Объекты (форма)
Текстура
Цвет, яркость
низкоуровневые характеристики
Текстовые аннотации

Семинар Московской Секции ACM SIGMOD, 29.11.2007
Поиск по содержанию

Семинар Московской Секции ACM SIGMOD, 29.11.2007
Цвет
F(I) = (h1I, h2I, …, hNI)
Метрики: L1, L2, L∞
F(I) = (E1I,E2I,E3I,
σ1I,σ2I,σ3I,
s1I,s2I,s3I)
Мат. ожидание, дисперсия, 3-ий момент: для каждого цветового канала
Метрики: ~L1
Stricker M., Orengo M. Similarity of Color Images. Proceedings of the SPIE Conference, vol. 2420, p. 381-392, 1995

Семинар Московской Секции ACM SIGMOD, 29.11.2007
Цветовые гистограммы – недостатки
1. Не учитывается схожесть цветов:
d(H1, H2) > d(H1, H3)
Кумулятивные гистограммы
Niblack W., Barber R., et al. The QBIC project: Querying images by content using color, texture and shape. In IS&T/SPIE International Symposium on Electronic Imaging: Science & Technology, Conference 1908, Storage and Retrieval for Image and Video Databases, Feb. 1993
А – матрица с коэффициентами «схожести» цветов

Семинар Московской Секции ACM SIGMOD, 29.11.2007
Цветовые гистограммы – недостатки
2. Не учитывается пространственное расположение цветов:
HA= HB = HC
Васильева Н., Новиков Б. Построение соответствий между низкоуровневыми характеристиками и семантикой статических изображений. Труды RCDL’2005.
i = 1..N – число цветов;
(ai, bi, ci) – параметры цвета i;
weighti – количество цвета i на изображении А;
(xi, yi) – координаты центра цветового пятна.

Семинар Московской Секции ACM SIGMOD, 29.11.2007
Пространственное расположение цветов
Stricker M., Dimai A. Spectral Covariance and Fuzzy Regions for Image Indexing. Machine Vision and Applications, vol. 10., p. 66-73, 1997
Разбиение изображения на фиксированные блоки
«Нечеткие области»
Сегментация

Семинар Московской Секции ACM SIGMOD, 29.11.2007
Гистограммы или моменты? (1)
Stricker M., Orengo M. Similarity of Color Images. ... (3000 изображений)

Семинар Московской Секции ACM SIGMOD, 29.11.2007
Гистограммы или моменты? (2)
База Corel Photo Set (285 изображений)
эксперимент в рамках дипломной работы М. Теплых

Семинар Московской Секции ACM SIGMOD, 29.11.2007
Поиск по содержанию: текстура

Семинар Московской Секции ACM SIGMOD, 29.11.2007
Текстура: статистические
Матрицы смежности – Haralik’s co-occurrence matrices
Признаки Tamura – Tamura features (Tamura image)

Семинар Московской Секции ACM SIGMOD, 29.11.2007
Матрицы смежности
Grey Level Co-occurrence Matrices (GLCM):
Матрица частот пар пикселей определенной яркости, расположенных на изображении определенным образом относительно друг друга.
– параметр сдвига, задающий взаимное расположение пикселей;
I(p,q) – уровень яркости пикселя изображения, расположенного в точке (p, q).

Семинар Московской Секции ACM SIGMOD, 29.11.2007
Матрицы смежности: пример

Семинар Московской Секции ACM SIGMOD, 29.11.2007
Матрицы смежности: характеристики
Статистические параметры, вычисленные по матрицам:
- минимален, когда все элементы равны
- мера хаотичности, максимален, когда все элементы равны
- мал, когда большие элементы
вблизи главной диагонали
- мал, когда большие элементы далеки от главной диагонали

Семинар Московской Секции ACM SIGMOD, 29.11.2007
Признаки Tamura
Характеристики, существенные для зрительного восприятия:
Зернистость (coarseness)
Контрастность (contrast)
Направленность (directionality)
Линейность (line-likeness)
Регулярность (regularity)
Грубость (roughness)

Семинар Московской Секции ACM SIGMOD, 29.11.2007
Текстура: спектральные
Вейвлет-признаки, фильтры Габора
Фильтры ICA

Семинар Московской Секции ACM SIGMOD, 29.11.2007
Вейвлет-признаки
Вейвлет-анализ – разложение сигнала по специальному базису:
Базисные функции:
- масштабирующая функция
- порождающий вейвлет
Набор базисных функций – банк фильтров

Семинар Московской Секции ACM SIGMOD, 29.11.2007
Фильтры Габора
Порождающий вейвлет: функция Габора
Набор фильтров:
К – общее число направлений,
S – число масштабов,
Uh, Ul – максимум и минимум рассматриваемых частот.

Семинар Московской Секции ACM SIGMOD, 29.11.2007
Фильтры ICA
H. Borgne, A. Guerin-Dugue, A. Antoniadis. Representation of images for classification with independent features. Pattern Recognition Letters, vol. 25, p. 141-154, 2004
Фильтры получены при помощи анализа независимых компонент

Семинар Московской Секции ACM SIGMOD, 29.11.2007
Сравнение текстурных признаков
P. Howarth, S. Rüger. Robust texture features for still image retrieval.
In Proc. IEE Vis. Image Signal Processing, vol. 152, No. 6, December 2006
В контексте задачи поиска!

Семинар Московской Секции ACM SIGMOD, 29.11.2007
Сравнение текстурных признаков (2)
Snitkowska, E. Kasprzak, W. Independent Component Analysis of Textures in Angiography Images. Computational Imaging and Vision, vol. 32, pages 367-372, 2006.
Фильтры Габора v. s. фильтры ICA
Эксперименты по классификации изображений:
Коллекция ангиографических снимков
Фильтры ICA лучше на 13%
Коллекция текстур Brodatz
Фильтры ICA лучше на 4%

Семинар Московской Секции ACM SIGMOD, 29.11.2007
Поиск по содержанию: форма

Семинар Московской Секции ACM SIGMOD, 29.11.2007
Форма объектов

Семинар Московской Секции ACM SIGMOD, 29.11.2007
Требования к признакам формы
Инвариантность к параллельному переносу
Инвариантность к изменению масштаба
Инвариантность к повороту
Устойчивость к незначительным изменениям формы
Простота вычисления
Простота сравнения

Семинар Московской Секции ACM SIGMOD, 29.11.2007
Форма объектов: границы
Цепные коды (Chain Codes)
Дескрипторы Фурье (Fourier Descriptors)

Семинар Московской Секции ACM SIGMOD, 29.11.2007
Цепные коды
А: 03001033332322121111
Б: 70016665533222
Нумерация направлений для 4-связного и 8-связного цепных кодов:
Пример:
Инвариантность к выбору начальной точки: минимальный код
Инвариатность к повороту: разности цифр кода

Семинар Московской Секции ACM SIGMOD, 29.11.2007
Дескрипторы Фурье
1. Вычисление сигнатуры (2D -> 1D):
Расстояние до центроида до границы
Комплексные координаты: z(t) = x(t) + iy(t)
...
2. Вычисление коэффициентов Фурье (s(t) – сигнатура):
3. Нормализация (NFD – Normalized Fourier Descriptors):
4. Сравнение:

Семинар Московской Секции ACM SIGMOD, 29.11.2007
Форма объектов: области
Грид-метод (Grid-method)
Инвариантные моменты (Moment invariants)

Семинар Московской Секции ACM SIGMOD, 29.11.2007
Грид-метод
А: 001111000 011111111 111111111 111111111 111110111 0111000011
Б: 001100000 011100000 111100000 111101111 111111110 001111000
А
Б
Инвариантность:
Нормализация по главной оси:
направление;
размер;
позиционирование на гриде.

Семинар Московской Секции ACM SIGMOD, 29.11.2007
Инвариантные моменты
Момент порядка (p+q) двумерной непрерывной функций:
Центральные моменты для f(x,y) – дискретного изображения:
С использованием нормированных центральных моментов был выведен набор из 7 инвариантных к параллельному переносу, повороту и изменению масштаба моментов.
Вектор признаков:

Семинар Московской Секции ACM SIGMOD, 29.11.2007
Сравнение признаков формы
Mehtre B. M., Kankanhalli M. S., Lee W. F. Shape measures for content based image retrieval: a comparison. Inf. Processing and Management, vol. 33, No. 3, pages 319-337, 1997.

Семинар Московской Секции ACM SIGMOD, 29.11.2007
Признаки в системах поиска
QBIC
VisualSEEk
Цвет
Текстура
Форма
Netra
Mars
Гистограммы, HSV
Гистограммы (HSV),
Color codebook,
кластеризация
Гистограммы (HSV)
Гистограммы (HSV),
Color Sets,
Location info
Tamura Image, Euclid dist
Фильтры Габора
Tamura Image, 3D Histo
Геометрические для границ + моменты
Fourier-based (Фурье)
MFD (Фурье)

Семинар Московской Секции ACM SIGMOD, 29.11.2007
План
Основные направления исследований
Уровни содержания изображения
Цвет
Текстура
Форма объектов
I. Обзор методов поиска изображений
II. Синтез данных в контексте CBIR
Существующие решения и их недостатки
Альретнативные подходы
Поиск в частично-аннотированной базе
WTGF: Weighted Total with Gravitation Function
Адаптивный поиск

Семинар Московской Секции ACM SIGMOD, 29.11.2007
Синтез данных в контексте CBIR
цвет (2)
текстура
форма
синтез
результат
цвет
Комбинированный поиск (различные характеристики)
Уточнение результатов поиска (разные алгоритмы)
Дополнение результатов поиска (разные множества)
аннотации

Семинар Московской Секции ACM SIGMOD, 29.11.2007
Существующие недостатки
CombMax, CombMin, CombSum
CombAVG
CombMNZ = CombSUM * number of nonzero similarities
ProbFuse
HSC3D
Линейная комбинация (CombSum с весами)
Не учитываются веса источников
Если учитываются:
линейная зависимость итогового ранга элемента от его рангов в различных источниках и весов источников
Не учитываются особенности запроса-образца
Недостатки:

Семинар Московской Секции ACM SIGMOD, 29.11.2007
Альтернативные подходы
ColorMoment
ICAHist
синтез
результат
ColorHist
Учитывать веса источников, нелинейная зависимость результата от весов
аннотации
Учитывать особенности запроса-образца

Семинар Московской Секции ACM SIGMOD, 29.11.2007
Синтез ранжированных списков с весами
(x11, r11), (x12, r12), … , (x1n, r1n)
ω1
(x21, r21), (x22, r22), … , (x2n, r2n)
ω2
(xm1, rm1), (xm2, rm2), … , (xmn, rmn)
ωm
…
ωi – вес i-го списка; rik - ранг k-го элемента в списке i
r0k = f(Ω, Rk), где
Ω – множество весов всех списков,
Rk - множество рангов элемента k
Существующие решения:
CombMax, CombMin, CombSum
CombAVG
CombMNZ = CombSUM * number of nonzero similarities
ProbFuse
HSC3D

Семинар Московской Секции ACM SIGMOD, 29.11.2007
Поиск в частично аннотированной базе
Текстовый запрос
…
поиск по
аннотациям
Результат

Семинар Московской Секции ACM SIGMOD, 29.11.2007
Свойства функции синтеза
Симметричность
Монотонность по каждому из аргументов
Функции для определения ранга объекта
Функция ранга ([0..1], [0..1])N -> [0..1]
Функция веса [0..1]N -> [0..1]
MinMax условие /CombMin, CombMax, CombAVG/:
Дополнительное свойство (аналог HSC3D):
условие взвешенной стабилизации элементов с высоким рангом (правило конусов)

Семинар Московской Секции ACM SIGMOD, 29.11.2007
Weighted Total with Gravitation Function
Модернизация CombAVG, в качестве веса - стабилизационная (гравитационная) функция:
где

Семинар Московской Секции ACM SIGMOD, 29.11.2007
Эксперименты: метод оценки
Параметры Roverlap, Noverlap:
Lee J. H. Analyses of multiple evidence combination. SIGIR '97: Proceedings of the 20th annual international ACM SIGIR conference on Research and development in in­formation retrieval.
New York, NY, USA: ACM Press, p. 267-276, 1997.

Семинар Московской Секции ACM SIGMOD, 29.11.2007
Описание эксперимента I
Данные:
Коллекция Flickr (~15000)
Методы:
Random с условиями MinMax
CombMNZ
WTGF_MT
WeightedTotal

Семинар Московской Секции ACM SIGMOD, 29.11.2007
Результаты эксперимента I: Roverlap
а) Зависимость Roverlap от размера списка при delta=0.03 для 10 входных списков
б) Зависимость Roverlap от размера списка при delta=0.07 для 10 входных списков

Семинар Московской Секции ACM SIGMOD, 29.11.2007
Описание эксперимента II
Участники синтеза (попарное смешивание):
цветовые гистограммы с пространственной информацией (СolorHist )
статистические признаки цвета (СolorMoment )
текстурные признаки на основе фильтров ICA (ICAHist)
Методы:
CombMNZ
WTGF_MT
WTGF_MT_weighted
Данные:
Коллекция Corel Photo Set (285)

Семинар Московской Секции ACM SIGMOD, 29.11.2007
Результаты эксперимента II
Графики зависимости значений Roverlap от размера списков для различных функций синтеза применительно к различным методам поиска по содержанию:
а) ColorHist и ColorMoment; b) ColorHist и ICAHist; c) ColorMoment и ICAHist.

Семинар Московской Секции ACM SIGMOD, 29.11.2007
Адаптивный поиск

Семинар Московской Секции ACM SIGMOD, 29.11.2007
Описание эксперимента III
Характеристики
Цвет – статистическое представление
Текстура – свертки с фильтрами ICA
По оценкам асессоров изображения разбиты на классы
Выбор метрики для класса:
Каждое изображение – запрос для поиска с использованием смешанной метрики
Коэффициенты: 0, 0.25, 0.5, 0.75, 1
Чем больше суммарная (по всем изображениям класса) полнота, тем лучше метрика

Семинар Московской Секции ACM SIGMOD, 29.11.2007
Результаты: зависимость полноты
Кластеры с преобладанием характеристики цвета.
Кластеры со смещением соотношения характеристик в сторону текстуры.

Семинар Московской Секции ACM SIGMOD, 29.11.2007
Результаты: кластеры

Семинар Московской Секции ACM SIGMOD, 29.11.2007
Результаты: примеры

Семинар Московской Секции ACM SIGMOD, 29.11.2007
Методы синтеза: выводы (1)
Методы синтеза применимы к задаче поиска изображений и позволяют существенно улучшить результаты поиска.
WTGF:
большое количество источников;
невысокая степень перекрытия источников;
источники с различными весами.
CombMNZ:
равнозначные источники;
высокая степень перекрытия источников.
Предложенная схема поиска по частично аннотированной базе оправдала себя.

Семинар Московской Секции ACM SIGMOD, 29.11.2007
Методы синтеза: выводы (2)
Возможно выделить классы изображений, для которых большее значение имеет та или иная характеристика.
Можно ли выделить общие признаки для изображений одного класса?
Позволит ли адаптивный подход улучшить результат поиска?