Семинар Московской Секции ACM SIGMOD, Методы поиска изображений по содержанию Наталья Васильева HP Labs, Russia; СПбГУ 29 ноября 2007

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

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

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

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

Семинар Московской Секции ACM SIGMOD, Цвет F(I) = (h 1 I, h 2 I, …, h N I ) Метрики: L 1, L 2, L F(I) = (E 1 I,E 2 I,E 3 I, σ 1 I,σ 2 I,σ 3 I, s 1 I,s 2 I,s 3 I ) Мат. ожидание, дисперсия, 3-ий момент: для каждого цветового канала Метрики: ~L 1 Stricker M., Orengo M. Similarity of Color Images. Proceedings of the SPIE Conference, vol. 2420, p , 1995

Семинар Московской Секции ACM SIGMOD, Цветовые гистограммы – недостатки 1. Не учитывается схожесть цветов: d(H 1, H 2 ) > d(H 1, H 3 ) Кумулятивные гистограммы 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 А – матрица с коэффициентами «схожести» цветов

Семинар Московской Секции ACM SIGMOD, Цветовые гистограммы – недостатки 2. Не учитывается пространственное расположение цветов: H A = H B = H C AB C Васильева Н., Новиков Б. Построение соответствий между низкоуровневыми характеристиками и семантикой статических изображений. Труды RCDL2005. i = 1..N – число цветов; (a i, b i, c i ) – параметры цвета i; weight i – количество цвета i на изображении А; (x i, y i ) – координаты центра цветового пятна.

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

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

Семинар Московской Секции ACM SIGMOD, Гистограммы или моменты? (2) ColorHist ColorMoment Полнота Точность 56,77 % 55,98 % 23,02 % 25,06 % База Corel Photo Set (285 изображений) эксперимент в рамках дипломной работы М. Теплых

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

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

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

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

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

Семинар Московской Секции ACM SIGMOD, Признаки Tamura Характеристики, существенные для зрительного восприятия: Зернистость (coarseness) Контрастность (contrast) Направленность (directionality) Линейность (line-likeness) Регулярность (regularity) Грубость (roughness) Coarseness-coNtrast-Directionality – точки в трехмерном пространстве CND Tamura image: Евклидово расстояние в 3D (QBIC) 3D гистограмма (Mars) Признаки:

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

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

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

Семинар Московской Секции ACM SIGMOD, Фильтры ICA H. Borgne, A. Guerin-Dugue, A. Antoniadis. Representation of images for classification with independent features. Pattern Recognition Letters, vol. 25, p , 2004 I1I1 I2I2 … N фильтров dist(I 1,I 2 ) = KL H (H 1i, H 2i ) Σ i=1 N Фильтры получены при помощи анализа независимых компонент

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

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

Семинар Московской Секции ACM SIGMOD, Форма объектов Спектральные дескрипторы (spectral descriptors)

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

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

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

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

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

Семинар Московской Секции ACM SIGMOD, Грид-метод А: Б: А Б Инвариантность: Нормализация по главной оси: направление; размер; позиционирование на гриде.

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

Семинар Московской Секции ACM SIGMOD, Сравнение признаков формы 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 , 1997.

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

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

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

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

Семинар Московской Секции ACM SIGMOD, Синтез ранжированных списков с весами (x 1 1, r 1 1 ), (x 1 2, r 1 2 ), …, (x 1 n, r 1 n ) ω1ω1 (x 2 1, r 2 1 ), (x 2 2, r 2 2 ), …, (x 2 n, r 2 n ) ω2ω2 (x m 1, r m 1 ), (x m 2, r m 2 ), …, (x m n, r m n ) ωmωm … ω i – вес i-го списка; r i k - ранг k-го элемента в списке i r 0 k = f(Ω, R k ), где Ω – множество весов всех списков, R k - множество рангов элемента k Существующие решения: CombMax, CombMin, CombSum CombAVG CombMNZ = CombSUM * number of nonzero similarities ProbFuse HSC3D

Семинар Московской Секции ACM SIGMOD, Поиск в частично аннотированной базе Текстовый запрос TextResult 1, textrank 1 TR 2, tr 2,... … tr 1 … tr 2 … поиск по аннотациям по содержанию Результат

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

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

Семинар Московской Секции ACM SIGMOD, Эксперименты: метод оценки Параметры R overlap, N overlap : 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 , 1997.

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

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

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

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

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

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

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

Семинар Московской Секции ACM SIGMOD, Результаты: кластеры ОписаниеРазмерМетрика Небо7 Животные10 Облака8 Озера9 Поля, луга10 Листва5 Небоскребы6 Группы людей5

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

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

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

Семинар Московской Секции ACM SIGMOD, Заключение Большой выбор различных алгоритмов поиска по каждой из характеристик в отдельности Цвет: гистограммы или статистическая модель? Текстура: фильтры Габора, фильтры ICA Форма: дескрипторы Фурье, инвариантные моменты Необходимо комбинировать методы поиска по различным характеристикам Выбор метода синтеза зависит от конкретной задачи (что с чем смешиваем) Важно учитывать веса источников Адаптивный подход?