История подходов к распознаванию

1. История подходов к распознаванию

• 1960-е – ранние 1990-е: геометрическая эра
• 1990-е: модели, основанные на внешнем
виде
• Середина 1990-х: скользящее окно
• Поздние 1990-е: локальные признаки
• Ранние 2000-е: модели частей и формы
• Середина 2000-х: мешки признаков
• Наше время: комбинация локальных и
глобальных методов, методы, управляемые
данными, контекст
Svetlana Lazebnik

2. Глобальные дескрипторы сцены

Что важно в распознавании?
• Методы машинного обучения
– Например, выбор классификатора
• Представление
– Низкий уровень: SIFT, HoG, gist, контуры
– Средний уровень: Bag of words, скользящее
окно, деформируемая модель
– Верхний уровень: Контекстная зависимость
• Данные
– Больше – лучше
– Самое трудоемкое – разметка

3. Методы, управляемые данными

Базовый процесс распознавания
объектов
Выбор модели объекта
Генерация гипотез
Оценка гипотез
Принятие решения

4. Методы, управляемые данными

Базовый процесс распознавания
объектов
Выбор модели объекта
Пример: Распознавание на
основе особых точек
Генерация гипотез
A1
Оценка гипотез
Принятие решения
A2
A3

5. Геометрический контекст

Вспоминаем как сопоставить точки
1. Find a set of
distinctive keypoints
A1
A2
2. Define a region
around each
keypoint
A3
fA
N pixels
fB
e.g. color
e.g. color
N pixels
d( f A, fB ) T
3. Extract and
normalize the
region content
4. Compute a local
descriptor from the
normalized region
5. Match local
descriptors
K. Grauman, B. Leibe

6. Что важно в распознавании?

Базовый процесс распознавания
объектов
Пример: Распознавание
на основе особых точек
Выбор модели объекта
A1
A2
Генерация гипотез
A3
Affine-variant
point locations
Аффинное
преобразование
Оценка гипотез
# Inliers
Принятие решения
Выбрать гипотезу с самой
большой оценкой выше порога

7. What Matters in Scene Recognition?

Поиск объектов (обзор)
Входной
кадр
Сохраненный
кадр
1. Сопоставить особые точки между входным изображением и
базовым
2. Сопоставленные точки голосуют за грубое
положение/ориентацию/масштаб объекта
3. Найти тройки положение/ориентацию/масштаб с хотя бы
тремя голосами
4. Вычислить аффинное преобразование с использованием
итеративных наименьших квадратов с проверкой вылетов
5. Сообщить об объекте, если есть хотя бы T сопоставленные
точки

8. Базовый процесс распознавания объектов

Сопоставление особых точек
• Хотим сопоставить точки между:
1. Входным кадром (запросом)
2. Сохраненным изображением с объектом
• Дан дескриптор x0, найти два ближайших
соседа x1, x2 с расстояниями d1, d2
• x1 соответствует x0 если d1/d2 < 0.8
– Это убирает 90% ложных сопоставлений и 5%
истинных (Lowe)

9. Базовый процесс распознавания объектов

Применение
• Sony Aibo
(Evolution Robotics)
• SIFT
– Распознавание
док-станции
– Общение с
визуальными
карточками
• Другое применение
– Распознавание места
– Замыкание кругов
в SLAM
K. Grauman, B. Leibe
16
Slide credit: David Lowe

10. Вспоминаем как сопоставить точки

Как быстро найти изображения в большой
базе, которые соответствуют данному кадру?

11. Базовый процесс распознавания объектов

Video Google System
пределах области
запроса
2. Инвертированный
файловый индекс для
поиска соответствующих
кадров
3. Сравнение счетчика слов
4. Пространственная
проверка
Sivic & Zisserman, ICCV 2003
• Demo online at :
Найденные кадры
Sensory Augmented
andRecognition
Perceptual
Tutorial Computing
Object
Visual
1. Собрать все слова в
Область
запроса
http://www.robots.ox.ac.uk/~vgg/re
search/vgoogle/index.html
Kristen Grauman

12. Поиск объектов (обзор)

Sensory Augmented
andRecognition
Perceptual
Tutorial Computing
Object
Visual
Пример применения
Мобильный гид
• Самолокализация
• Распознавание объектов/зданий
• Дополнение фото/видео
B. Leibe
[Quack, Leibe, Van Gool, CIVR’08]

13. Сопоставление особых точек

Sensory Augmented
andRecognition
Perceptual
Tutorial Computing
Object
Visual
Применение: Крупномасштабный поиск
Запрос
Результаты по 5000 изображениям Flickr (есть демо для 100 000)
[Philbin CVPR’07]

14. Affine Object Model

Применение: Автоматическая аннотация
изображений
Moulin Rouge
Tour Montparnasse
Old Town Square (Prague)
Colosseum
Viktualienmarkt
Maypole
Слева: Wikipedia
Справа: ближайшее из Flickr
[Quack CIVR’08]
K. Grauman, B. Leibe
24

15. Affine Object Model

Простая идея
Сколько ключевых точек
близки к ключевым
точкам в каждом кадре
из базы данных
Много
похожих
Мало или
нет совсем
Но это очень, ОЧЕНЬ МЕДЛЕННО!

16. Применение

Индексация локальных
признаков
• Каждый патч/регион имеет дескриптор,
являющийся точкой в некотором
многомерном пространстве (например, SIFT)
Пространство
точек дескриптора
Kristen Grauman

17. Location Recognition

Индексация локальных
признаков
• Если точки близки в пространстве признаков, то
это – похожие дескрипторы, что означает
похожее содержание кадра
Пространство
признаков
Изображения
базы данных
Входной
кадр
Easily can have millions of
features to search! Kristen Grau

18. Многоракурсное сопоставление

Индексация локальных признаков:
обратный индекс
• Для текстов есть
эффективный способ
найти все страницы
на которых
встречается слово –
использовать
индекс…
• Мы хотим найти все
изображения на
которых встречается
признак.
• Нам нужно
превратить наши
признаки в
“визуальные слова”.
Kristen Grauman

19.

Визуальные слова
• Отображение многомерных дескрипторов в
токены/слова путем квантования пространства
признаков
• Квантование путем
кластеризации –
пусть центры
кластеров будут
прототипами “слов”
Слово #2
Пространство
признаков
дескриптора
• Определим, какое
слово сопоставить
новой области кадра,
находя центр
ближайшего кластера
Kristen Grauman

20. Video Google System

Визуальные слова
• Пример: каждая
группа патчей
принадлежит
одному
визуальному слову
Figure from Sivic & Zisserman, ICCV 2003 Kristen Grauman

21. Пример применения

Создание словаря
Вопросы:
• Размер словаря, число слов
• Стратегия выборки: где извлекать признаки?
• Алгоритм кластеризации/квантизации
Kristen Grauman

22. Применение: Крупномасштабный поиск

Обратный индекс
• По изображениям базы построим индекс,
сопоставляющий слова с номерами кадров
Kristen Grauman

23. Web Demo: Movie Poster Recognition

Инвертированный индекс
• Новое изображение сопоставляется с индексами
изображений с общими словами
Kristen Grauman

24. Применение: Автоматическая аннотация изображений

Распознавание мест:
оставшиеся вопросы
• Как сделать выводы по всему изображению?
И оценить общее сходство?
• Насколько большим должен быть словарь?
Как осуществить квантизацию эффективно?
• Достаточно ли иметь один набор визуальных
слов, чтобы идентифицировать
сцену/объект? Как проверить
пространственную схожесть?
• Как оценить результаты запроса?
Kristen Grauman

25.

Аналогия с документами
Of all the sensory impressions proceeding to
the brain, the visual experiences are the
dominant ones. Our perception of the world
around us is based essentially on the
messages that reach the brain from our eyes.
For a long time it was thought that the retinal
sensory,
image was transmitted
pointbrain,
by point to visual
centers in the brain; the cerebral cortex was a
visual, perception,
movie screen, so to speak, upon which the
cerebral
cortex,
image inretinal,
the eye was
projected. Through
the
discoveries ofeye,
Hubelcell,
and Wiesel
we now
optical
know that behind the origin of the visual
image
perception in thenerve,
brain there
is a considerably
more complicated
course of
events. By
Hubel,
Wiesel
following the visual impulses along their path
to the various cell layers of the optical cortex,
Hubel and Wiesel have been able to
demonstrate that the message about the
image falling on the retina undergoes a stepwise analysis in a system of nerve cells
stored in columns. In this system each cell
has its specific function and is responsible for
a specific detail in the pattern of the retinal
image.
China is forecasting a trade surplus of $90bn
(£51bn) to $100bn this year, a threefold
increase on 2004's $32bn. The Commerce
Ministry said the surplus would be created by
a predicted 30% jump in exports to $750bn,
compared with a 18% rise in imports to
China,
trade,
$660bn. The figures
are likely
to further
annoy the US, which has long argued that
surplus, commerce,
China's exports are unfairly helped by a
exports,
imports,
US,
deliberately
undervalued
yuan. Beijing
agrees the
surplus
is too high,
but says the
yuan,
bank,
domestic,
yuan is only one factor. Bank of China
foreign,
increase,
governor Zhou
Xiaochuan
said the country
also needed to do
more tovalue
boost domestic
trade,
demand so more goods stayed within the
country. China increased the value of the
yuan against the dollar by 2.1% in July and
permitted it to trade within a narrow band, but
the US wants the yuan to be allowed to trade
freely. However, Beijing has made it clear that
it will take its time and tread carefully before
allowing the yuan to rise further in value.
ICCV 2005 short course, L. Fei-Fei

26. Простая идея

27.

Мешки визуальных слов
• Описать всё изображение
распределением
(гистограммой)
встречающихся слов
• Аналогично «мешку слов»,
часто используемому для
документов

28. Индексация локальных признаков

Сравнение мешков слов
• Упорядочить кадры по нормализованному скалярному
произведению между их гистограммами (возможно
взвешенными) – метод ближайших соседей
[1 8 1
dj
4]
[5 1 1
q
0]
для словаря из V слов
Kristen Grauman

29. Индексация локальных признаков: обратный индекс

Обратный индекс
w91
1. Найти слова в запросе
2. Обратный индекс для
поиска соответствующих
кадров
3. Сравнить счетчики слов
Kristen Grauman

30. Визуальные слова

Распознавание мест:
оставшиеся вопросы
• Как сделать выводы по всему изображению?
И оценить общее сходство?
• Насколько большим должен быть словарь?
Как осуществить квантизацию эффективно?
• Достаточно ли иметь один набор визуальных
слов, чтобы идентифицировать
сцену/объект? Как проверить
пространственную схожесть?
• Как оценить результаты запроса?
Kristen Grauman

31. Визуальные слова

Распознавание по К-дереву
Following slides by David Nister (CVPR 2006)

32. Создание словаря

33. Обратный индекс

34.

35. Распознавание мест: оставшиеся вопросы

36. Аналогия с документами

37.

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

39. Сравнение мешков слов

40.

41. Распознавание мест: оставшиеся вопросы

42. Распознавание по К-дереву

43.

44.

45.

46.

47.

48.

49.

50.

51.

52.

53.

54.

55.

110,000,000
кадров за
5.8 с
Slide
Slide Credit: Nister

56.

Slide
Slide Credit: Nister

57.

Slide
Slide Credit: Nister

58.

Slide
Slide Credit: Nister

59.

Словарные деревья:
сложность
Число слов определяется параметрами дерева:
коэффициент ветвления и количество уровней

60.

Размер словаря
Результаты по 6347 кадрам
К-т
ветвления
Influence on performance, sparsity
Nister & Stewenius, CVPR 2006
Kristen Grauman

61.

Больший коэффициент ветвления
работает лучше (но медленней)

62.

Стратегии выборки
Разреженно, в
особых точках
Плотно, равномерно
Случайно
• Для поиска конкретных текстурированных
объектов надежнее работают разреженные
выборки.
• Много дополняющих друг друга детекторов
дают лучшее покрытие изображения.
• Для категоризации объектов лучшее
покрытие даёт плотная выборка.
Множественные
операторы
74
Image credits: F-F. Li, E. Nowak, J. Sivic
[See Nowak, Jurie & Triggs, ECCV 2006]
K. Grauman, B. Leibe

63.

Распознавание мест:
оставшиеся вопросы
• Как сделать выводы по всему изображению?
И оценить общее сходство?
• Насколько большим должен быть словарь?
Как осуществить квантизацию эффективно?
• Достаточно ли иметь только набор
визуальных слов, чтобы
идентифицировать сцену/объект? Как
проверить пространственную схожесть?
• Как оценить результаты запроса?
Kristen Grauman

64.

Как повысить точность?
Итак, мы научились представлять изображение
как “мешок слов”, без пространственной
информации
Какое
сопоставление
лучше?
e
h
z
a
f
e
a
h
f
e e

65.

Как повысить точность?
Итак, мы научились представлять изображение
как “мешок слов”, без пространственной
информации
Настоящие объекты имеют консистентную геометрию

66. 110,000,000 кадров за 5.8 с

Пространственная верификация
Запрос
Запрос
Кадр с высокой BoW похожестью
Кадр с высокой BoW похожестью
Обе пары кадров имеют много общих визуальных слов
Slide credit: Ondrej Chum

67.

Пространственная верификация
Запрос
Запрос
Кадр с высокой BoW похожестью
Кадр с высокой BoW похожестью
Лишь некоторые сопоставления взаимосогласованными
Slide credit: Ondrej Chum

68.

Распознавание мест:
оставшиеся вопросы
• Как сделать выводы по всему изображению?
И оценить общее сходство?
• Насколько большим должен быть словарь?
Как осуществить квантизацию эффективно?
• Достаточно ли иметь один набор визуальных
слов, чтобы идентифицировать
сцену/объект? Как проверить
пространственную схожесть?
• Как оценить результаты запроса?
Kristen Grauman

69.

Оценка качества запроса
Results (ordered):
Размер базы: 10 кадров
Соответствуют (всего): 5 кадров
Запрос
precision = #relevant / #returned
recall = #relevant / #total relevant
1
precision
0.8
0.6
0.4
0.2
0
0
0.2
0.4
0.6
0.8
1
recall
Slide credit: Ondrej Chum

70. Словарные деревья: сложность

Что ещё можно
позаимствовать у текстов?
China is forecasting a trade surplus of $90bn
(£51bn) to $100bn this year, a threefold
increase on 2004's $32bn. The Commerce
Ministry said the surplus would be created by
a predicted 30% jump in exports to $750bn,
compared with a 18% rise in imports to
China,
trade,
$660bn. The figures
are likely
to further
annoy the US, which has long argued that
surplus, commerce,
China's exports are unfairly helped by a
exports,
imports,
US,
deliberately
undervalued
yuan. Beijing
agrees the
surplus
is too high,
but says the
yuan,
bank,
domestic,
yuan is only one factor. Bank of China
foreign,
increase,
governor Zhou
Xiaochuan
said the country
also needed to do
more tovalue
boost domestic
trade,
demand so more goods stayed within the
country. China increased the value of the
yuan against the dollar by 2.1% in July and
permitted it to trade within a narrow band, but
the US wants the yuan to be allowed to trade
freely. However, Beijing has made it clear that
it will take its time and tread carefully before
allowing the yuan to rise further in value.

71. Размер словаря

tf-idf взвешивание
• Term frequency – inverse document frequency
• Описать кадр частотой каждого слова, снижая веса
слов, которые часто встречаются в базе данных
• (Стандартное взвешивание при поиске слов)
Количество слова i
в документе d
Число документов в
базе данных
Число слов в
документе d
Число документов, в
которых встречается
слово i
Kristen Grauman

72. Производительность

Расширение запроса
Запрос: golf green
Результаты:
- How can the grass on the greens at a golf course be so perfect?
- For example, a skilled golfer expects to reach the green on a par-four hole in ...
- Manufactures and sells synthetic golf putting greens and mats.
Нерелевантные результаты могут привести к `смещению темы’:
- Volkswagen Golf, 1999, Green, 2000cc, petrol, manual, , hatchback, 94000miles,
2.0 GTi, 2 Registered Keepers, HPI Checked, Air-Conditioning, Front and Rear
Parking Sensors, ABS, Alarm, Alloy
Slide credit: Ondrej Chum

73.

Расширение запроса
Результаты
…
Пространственная верификация
Запрос
Новые результаты
Новые запросы
Chum, Philbin, Sivic, Isard, Zisserman: Total Recall…, ICCV 2007
Slide credit: Ondrej Chum

74. Стратегии выборки

Что запомнить
• Распознавание экземпляров
объектов
– Найти особые точки, вычислить
дескрипторы
– Сопоставить дескрипторы
– Голосовать за аффинные
параметры
– Вернуть объект, если # inliers > T
• Ключи к эффективности
– Визуальные слова
• Много разных применений
– Обратный индекс
• Для поиска масштаба Интернета