�ݺ�ߣ

Классификация изображений Many slides adapted from Fei-Fei Li, Rob Fergus, Antonio Torralba and Svetlana Lazebnik CSEDays-2010

Сколько всего классов объектов ? ~10,000 to 30,000 Biederman 1987 1500-3000 основных существительных, ~10 подкатегорий

Миллионы крошечных картинок (« Tiny images ») http:// people.csail.mit.edu/torralba/tinyimages /

Миллионы крошечных картинок (« Tiny images »)

Классификация текстов Представление документа без порядка : частоты слов из словаря («мешок слов») Salton & McGill (1983) US Presidential Speeches Tag Cloud http://chir.ag/phernalia/preztags/

Представление документа без порядка : частоты слов из словаря («мешок слов») Salton & McGill (1983) Классификация текстов US Presidential Speeches Tag Cloud http://chir.ag/phernalia/preztags/

Слова и словари Что такое «слово» в контексте изображений? Как составить «словарь» для коллекции изображений?

Моделирование текстур Текстура является повторением набора базовых элементов («текстонов») Для стохастических текстур важны сами текстоны, а не их пространственное расположение

Распознавание текстур Universal texton dictionary histogram

«Визуальные слова» face, flowers, building «Визуальное слово» – часто повторяющийся фрагмент изображения В отличие от текстур – не в одном изображении, а в коллекции В изображении визуальное слово может встречаться только один раз!

«Визуальный словарь» Словарь – набор фрагментов, часто повторяющихся в коллекции изображений Как составить словарь? Составить большой список всех фрагментов по всей коллекции Разделить весь список на похожие группы Типичная задача «кластеризации» Будем считать все фрагменты в одной группе – «экземплярами» одного и того же слова

«Мешок визуальных слов»

Регулярная сетка Vogel & Schiele, 2003 Fei-Fei & Perona, 2005 1. Сбор фрагментов

Регулярная сетка Vogel & Schiele, 2003 Fei-Fei & Perona, 2005 Характерные точки Csurka et al. 2004 Fei-Fei & Perona, 2005 Sivic et al. 2005 1. Сбор фрагментов

Характерная точка изображения - это точка с характерной (отличающейся) окрестностью Характерные точки Пример особой точки Пример точки, не являющейся особой Названия: Особенность ( feature) Характеристическая / интересная точка ( interest point)

Свойства характерных точек Локальность ( Locality ) Особенность занимаем маленькую область изображения, поэтому работа с ней нечувствительна к перекрытиям Повторяемость ( Repeatability ) Особенность ( feature) должна находится в том же месте не смотря на изменения точки обзора и освещения Значимость ( Saliency ) Каждая особенность должна иметь уникальное ( distinctive) описание Компактность и эффективность Особенностей гораздо меньше .чем пикселей в изображении

Детекторы характерных точек Harris Difference of Gaussian Harris-Laplacian

Как два небольших изображения! Те же метрики, что и при прямом сравнении изображений: SAD = Squared absolute difference SSD = Squared of square difference Cross-correlation Неустойчиво к изменениям! Освещения Малые сдвиги приводят к большим изменениям Как сравнивать фрагменты?

SIFT S cale- I nvariant F eature T ransform DoG или Harris-Laplacian Характерный размер области R Характерная ориентация Дескриптор на основе гистограммы направлений градиентов Один из самых эффективных дескрипторов David G. Lowe. "Distinctive image features from scale-invariant keypoints .” IJCV 60 (2), pp. 91-110, 2004.

Ориентация Пример: найти локальное направление градиента вокруг интересной точки Повернуть фрагмент(ы) так, чтобы средний градиент был направлен вверх 0 2 

Дескрипторы Ориентация = размытый градиент Рамка, независимая от поворота ( Rotation Invariant Frame )

Гистограммы градиентов SIFT Вычисляем градиент в каждой точке Строим гистограммы по окрестностям Обычно – сетка 4 x4 , в каждой гистограмма с 8ю ячейками Стандартная длина вектора-дескриптора – 128 (4*4*8) Устойчив к изменениям освещенности и небольшим сдвигам

1. Извлечение фрагментов Выбрали фрагменты Вычислили для каждого дескриптор Составили большой список всех дескрипторов …

2. Обучение словаря …

2. Обучение словаря Кластеризация �ݺ�ߣ credit: Josef Sivic …

2. Обучение словаря Кластеризация �ݺ�ߣ credit: Josef Sivic Визуальный словарь …

Кластеризации Кластеризация является обычным методов обучения визуального словаря или «кодовой книги» ( codebook ) Обучение без учителя Центр каждого кластера становится кодовым вектором Словарь можно обучить на отдельной выборке Если обучающая выборка достаточно представительна, тогда словарь может стать «универсальным»

Кластеризация K-c редними Минимизируем сумму квадратов Евклидовых расстояний между точками x i и ближайшими центрами кластеров m k Алгоритм : Случайно инициализируем K центров кластеров Повторяем до сходимости : Назначаем каждую точку ближайшему центру Пересчитываем центр каждого кластера как среднее всх назначенных точек

Пример словаря Fei-Fei et al. 2005

Визуальные словари Как выбрать размер словаря ? Маленький : слова не могут описать все особенности Большой : переобучение Вычислительная сложность Деревья словарей (Nister & Stewenius, 2006) Approximate nearest-neighbour Хеширование

3. От кластеризации к квантизации Квантуем особенности с помощью словаря Сопоставляем каждый дескриптор ближайшему слову из словаря Sivic et al. 2005 Примеры визуальных слова

3. Описание изображения – «мешок слов» частоты слова … ..

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

Классификация Обучим решающее правило (классификатор), назначающий «мешкам» соответствующий класс Любое решающее правило делит пространство на решающие регионы разделенные решающими границами Decision

Классификатор – ближайший сосед Назначаем объекту метку ближайшего прецедента из обучающей выборки Диаграмма вороного для разбиения пространства признаков на 2 класса from Duda et al. Source: D. Lowe

Для каждой точки найти k ближайших точек из обучающей выборки Метки k точек голосуют за метку Работает неплохо при наличии большой обучающей выборки и хорошей функции близости К ближайших соседей k = 5 Source: D. Lowe

Решающее дерево 1 2 3 4 5 6 7 1 4 5 2 3 7 6 �ݺ�ߣ by V.Lempitsky

«Оверфиттинг» и «Прунинг» A B C D �ݺ�ߣ by V.Lempitsky

От дерева к лесу Yali Amit, Donald Geman: Shape quantization and recognition with randomized trees. Neural Computation, 1997 . Leo Breiman: Random forests. Machine Learning, 2001. �ݺ�ߣ by V.Lempitsky

Решающий лес - обучение function Node = Обучение_Вершины( {(x,y)}, Level) { if {y} одинаковые или Level == maxLevel return Создать_Лист(Распределение y); {tests} = Создать_ N _Случайных_Разбиений( {(x,y)} , N ) ; test = Выбрать_лучшее_разбиение _ из( {tests}); {(x0,y0)} = {(x,y) | test(x) = 0}; {(x1,y1)} = {(x,y) | test(x) = 1}; LeftChild = Обучение_Вершины( {(x0,y0)}, Level+1); RightChild = Обучение_Вершины( {(x1,y1)}, Level+1); return Создать_Вершину( test, LeftChild, RightChild); } // Обучение леса function main() { {X,Y} = Прочитать_Обучающие_Данные() ; for i = 1 to N {Xi,Yi} = Случайное_Подмнжество( {X,Y})); TreeRoot_i = Обучение_Вершины( {Xi,Yi}); end } �ݺ�ߣ by V.Lempitsky

Решающий лес - применение �ݺ�ߣ by V.Lempitsky

Решающий лес – свойства Один из самых эффективных алгоритмов классификации Вероятностное распределение на выходе Применим для высоких размерностей пространства признаков Высокая скорость обучения и тестирования Относительная простота реализации Caruana, R., Niculescu-Mizil, A.: An empirical comparison of supervised learning algorithms , 2006 �ݺ�ߣ by V.Lempitsky

Случайные окна для классификации Raphaël Marée, Pierre Geurts, Justus H. Piater, Louis Wehenkel: Random Subwindows for Robust Image Classification. CVPR 2005 - случайные окна - нормализация Признаки – интенсивности пикселей (цвета)

Возможные тесты I(p) ≷ τ I(p) ≷ I(q) + τ p p q Σ p∊A I(p) ≷ τ A A B Σ p∊A I(p) ≷ Σ p∊B I(p) + τ Интегральные изображения для быстрого подсчета �ݺ�ߣ by V.Lempitsky

Устойчивость к повороту Случайным образом поворачиваем каждое окно перед нормализацией размера

Результат работы Размер выборки = 100.000 Глубина = максимум Количество тестов = 1 ( “extremely-randomized decision trees”) 10 деревьев в лесу всего 6 минут на обучение!!!! 100 окон (2000 тестов) на классификацию картинки – realtime Сравнимая с другими методами точность работы! �ݺ�ߣ by V.Lempitsky

Caltech 101 & 256 Griffin, Holub, Perona, 2007 Fei-Fei, Fergus, Perona, 2004 http://www.vision.caltech.edu/Image_Datasets/Caltech101/ http://www.vision.caltech.edu/Image_Datasets/Caltech256 /

The PASCAL Visual Object Classes Challenge (2005-2009) Основные конкурсы Классификация : Для каждого из 20 классов, определить присутствие/отсутствие объекта этого класса в изображении Поиск : Определить рамку и метку каждого объекта из 20 классов в изображении http://pascallin.ecs.soton.ac.uk/challenges/VOC/

PASCAL (2005-2009) Классы 2008 : Человек : человек Животные : птица, кошка, корова, собака, лошадь, оцва Транспорт : самолет, велосипед, лодка, автобус, машина, мотоцикл, поезд Помещения : бутылка, кресло, стол, растение в горшке, монитор, диван http://pascallin.ecs.soton.ac.uk/challenges/VOC/

The PASCAL Visual Object Classes Challenge (2005-2009) Новые конкурсы Семантическая сегментация : попиксельная аннотация области объектов и фона Человек : Пометить рамкой и меткой каждую часть тела (голову, руки, ступни)

Как реализовать? OpenCV 2.0 Работа с изображениями, классификаторы VLFeat Детекторы точек, дескрипторы, кластеризация http:// www.vlfeat.org / ColorDescriptor Ряд разнообразных дескрипторов точек http:// staff.science.uva.nl/~ksande/research/colordescriptors /

Резюме метода «мешок слов» Извлечение особенностей Обучить “ визуальный словарь ” Квантуем особенности по словарю Описываем картинку частотами «визуальных слов» Варианты: Поиск ближайшего Многоклассовая классификация

Завтра… Поиск объектов Семантическая сегментация

�ݺ�ߣ

Классификация изображений

Recommended

More Related Content

What's hot (10)

Viewers also liked (19)

Similar to Классификация изображений (20)

More from LiloSEA (18)

Классификация изображений

Editor's Notes