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

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

Наталья Васильева
HP Labs, Russia;
СПбГУ
[email protected]
29 ноября 2007
Семинар Московской Секции ACM SIGMOD, 29.11.2007

2. План

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

3. CBIR: направления исследований

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

4. Уровни содержания изображения

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

5. Поиск по содержанию

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

6. Цвет

Мат. ожидание, дисперсия,
3-ий момент: для каждого
цветового канала
F(I) = (h1I, h2I, …, hNI)
F(I) = (E1I,E2I,E3I,
σ1I,σ2I,σ3I,
s1I,s2I,s3I)
Метрики: L1, L2, L∞
Метрики: ~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

7. Цветовые гистограммы – недостатки

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

8. Цветовые гистограммы – недостатки

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

9. Пространственное расположение цветов

Разбиение изображения на фиксированные блоки
«Нечеткие области»
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

10. Гистограммы или моменты? (1)

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

11. Гистограммы или моменты? (2)

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

12. Поиск по содержанию: текстура

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

13. Текстура: статистические

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

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

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

15. Матрицы смежности: пример

( x, y ) (1,0)
Семинар Московской Секции ACM SIGMOD, 29.11.2007

16. Матрицы смежности: характеристики

Статистические параметры, вычисленные по матрицам:
Energy C 2 (i, j )
i
- минимален, когда все элементы равны
j
Entropy C (i, j ) log 2 C (i, j )
i
Contrast
j
i
- мера хаотичности, максимален,
когда все элементы равны
- мал, когда большие элементы
вблизи главной диагонали
(i j ) 2 C (i, j )
j
Inverse Difference Moment
i
j
C (i, j )
1 (i j ) 2
- мал, когда большие элементы
далеки от главной диагонали
Семинар Московской Секции ACM SIGMOD, 29.11.2007

17. Признаки Tamura

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

18. Текстура: спектральные

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

19. Вейвлет-признаки

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

20. Фильтры Габора

Порождающий вейвлет: функция Габора
1
g ( x, y )
2 x y
2
1 x2
y
exp
2 2 jWx
2
2 x y
Набор фильтров:
g mn ( x, y ) a m g ( x , y ), a 1, m, n integer, m 0,1,..., S - 1,
x a m ( x cos y sin ),
y a m ( x sin y cos ),
n / K
a (U h / U l ) 1 /( S 1)
К – общее число направлений,
S – число масштабов,
Uh, Ul – максимум и минимум рассматриваемых частот.
Семинар Московской Секции ACM SIGMOD, 29.11.2007

21. Фильтры ICA

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

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

В контексте задачи
поиска!
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

23. Сравнение текстурных признаков (2)

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

24. Поиск по содержанию: форма

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

25. Форма объектов

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

26. Требования к признакам формы

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

27. Форма объектов: границы

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

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

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

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

1. Вычисление сигнатуры (2D -> 1D):
Расстояние до центроида до границы
Комплексные координаты: z(t) = x(t) + iy(t)
...
2. Вычисление коэффициентов Фурье (s(t) – сигнатура):
1
un
N
N 1
s(t )e
j 2 nt / N
t 0
3. Нормализация (NFD – Normalized Fourier Descriptors):
u1 u 2
u
,
,..., N 1
u0 u0
u0
4. Сравнение:
Nc
d ( f f
n
I
n
J
2
)
1
2
n 0
Семинар Московской Секции ACM SIGMOD, 29.11.2007

30. Форма объектов: области

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

31. Грид-метод

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

32. Инвариантные моменты

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

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

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

34. Признаки в системах поиска

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

35. План

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

36.

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

37. Существующие недостатки

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

38.

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

39. Синтез ранжированных списков с весами

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

40.

Поиск в частично аннотированной базе
поиск по
аннотациям
TextResult1, textrank1
TR2, tr2,
...
по содержанию
Текстовый запрос
tr1
…
tr2
…
…
Семинар Московской Секции ACM SIGMOD, 29.11.2007
Результат

41.

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

42. Weighted Total with Gravitation Function

Модернизация CombAVG, в качестве веса - стабилизационная
(гравитационная) функция:
(0)
x
r
g (r , w ) r
g (r , w )
( i )
x
i
i
( i )
x
( i )
( i )
x
( i )
где
1
g (rx( ) , w ( ) ) ( w ( ) ) 2 rx( )
12
i
i
i
4
i
Семинар Московской Секции ACM SIGMOD, 29.11.2007

43.

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

44.

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

45.

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

46.

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

47.

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

48. Адаптивный поиск

a2
a C (1 a ) T
a1
a3
Семинар Московской Секции ACM SIGMOD, 29.11.2007

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

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

50. Результаты: зависимость полноты

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

51. Результаты: кластеры

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

52. Результаты: примеры

1 C 0 T
0.5 C 0.5 T
0.25 C 0.75 T
Семинар Московской Секции ACM SIGMOD, 29.11.2007

53.

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

54.

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

55.

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