DUMP-2013 Наука и жизнь - Современная математика компьютерного зрения - Перевалов Денис, Костоусов Виктор
Download as PPT, PDF0 likes1,307 views
![> Отсутствие геометрических трансформаций
Малые локальные сдвиги
Большие горизонтальные сдвиги
Большой однородный сдвиг в любом направлении
Большой однородный сдвиг, поворот, масштабирование
A[x,y] ↔ B[x,y]
Задача поиска существенных изменений между изображениями
Задача сопоставления двух
изображений](https://image.slidesharecdn.com/sovrmatemcompzrenia-18-130528163841-phpapp01/85/DUMP-2013-22-320.jpg)
![Отсутствие геометрических трансформаций
> Малые локальные сдвиги
Большие горизонтальные сдвиги
Большой однородный сдвиг в любом направлении
Большой однородный сдвиг, поворот, масштабирование
A[x,y] ↔ B[x + epsX, y + epsY]
Оптический поток
Задача сопоставления двух
изображений](https://image.slidesharecdn.com/sovrmatemcompzrenia-18-130528163841-phpapp01/85/DUMP-2013-23-320.jpg)
![Отсутствие геометрических трансформаций
Малые локальные сдвиги
> Большие горизонтальные сдвиги
Большой однородный сдвиг в любом направлении
Большой однородный сдвиг, поворот, масштабирование
A[x,y] ↔ B[x + X, y]
Стереозрение
Задача сопоставления двух
изображений](https://image.slidesharecdn.com/sovrmatemcompzrenia-18-130528163841-phpapp01/85/DUMP-2013-24-320.jpg)
![Отсутствие геометрических трансформаций
Малые локальные сдвиги
Большие горизонтальные сдвиги
> Большой однородный сдвиг в любом направлении
Большой однородный сдвиг, поворот, масштабирование
A[x,y] ↔ B[x + U, y +V] где U,V – одинаковы для всех (x,y)
Сшивка изображений
Задача сопоставления двух
изображений
http://queue.acm.org/detail.cfm?id=2206309](https://image.slidesharecdn.com/sovrmatemcompzrenia-18-130528163841-phpapp01/85/DUMP-2013-25-320.jpg)
![Отсутствие геометрических трансформаций
Малые локальные сдвиги
Большие горизонтальные сдвиги
Большой однородный сдвиг в любом направлении
> Большой однородный сдвиг, поворот, масштабирование
A[x,y] ↔ B[ T(x,y) ] где T – афинный оператор
Поиск объектов на изображении
Задача сопоставления двух
изображений](https://image.slidesharecdn.com/sovrmatemcompzrenia-18-130528163841-phpapp01/85/DUMP-2013-26-320.jpg)
More Related Content
Viewers also liked (7)
Similar to DUMP-2013 Наука и жизнь - Современная математика компьютерного зрения - Перевалов Денис, Костоусов Виктор (20)
More from it-people (20)
DUMP-2013 Наука и жизнь - Современная математика компьютерного зрения - Перевалов Денис, Костоусов Виктор
- 1. Современная математика компьютерного зрения Виктор Костоусов Денис Перевалов Институт математики и механики им. Н.Н.Красовского Конференция DUMP-2013
- 2. План 1. Что такое компьютерное зрение 2. Успехи 3. Математика 4. Проблемы 5. Методы
- 3. Нас интересуют методы извлечения и анализа цветовых и геометрических структур на изображении. Определение Компьютерное зрение - теория и технология создания машин, которые могут видеть. http://the-gadgeteer.com/wp-content/uploads/2009/12/mr-robot-head-game.jpg
- 4. Высший уровень Классификация и идентификация объектов, построение описания сцены Низкоуровневая обработка фильтрация и выделение точечных особенностей Задачи компьютерного зрения Средний уровень Обнаружение линий, контуров, простых геометрических фигур, построение скелета, сегментация
- 6. Решены конкретные задачи > Обнаружение лиц Обнаружение объектов: пешеходы, автомобили, животные и пр. Мониторинг людей в помещении Распознавание жестов Автоматическое наведение на цель Номера автомобилей Поиск деталей на конвейере Автоматический контроль в производстве Автомобили без водителя
- 7. Решены конкретные задачи Обнаружение лиц > Обнаружение объектов: пешеходы, автомобили, животные и пр. Мониторинг людей в помещении Распознавание жестов Автоматическое наведение на цель Номера автомобилей Поиск деталей на конвейере Автоматический контроль в производстве Автомобили без водителя
- 8. Решены конкретные задачи Обнаружение лиц Обнаружение объектов: пешеходы, автомобили, животные и пр. > Мониторинг людей в помещении Распознавание жестов Автоматическое наведение на цель Номера автомобилей Поиск деталей на конвейере Автоматический контроль в производстве Автомобили без водителя
- 9. Решены конкретные задачи Обнаружение лиц Обнаружение объектов: пешеходы, автомобили, животные и пр. Мониторинг людей в помещении > Распознавание жестов Автоматическое наведение на цель Номера автомобилей Поиск деталей на конвейере Автоматический контроль в производстве Автомобили без водителя
- 10. Решены конкретные задачи Обнаружение лиц Обнаружение объектов: пешеходы, автомобили, животные и пр. Мониторинг людей в помещении Распознавание жестов > Автоматическое наведение на цель Номера автомобилей Поиск деталей на конвейере Автоматический контроль в производстве Автомобили без водителя
- 11. Решены конкретные задачи Обнаружение лиц Обнаружение объектов: пешеходы, автомобили, животные и пр. Мониторинг людей в помещении Распознавание жестов Автоматическое наведение на цель Номера автомобилей Поиск деталей на конвейере Автоматический контроль в производстве Автомобили без водителя
- 12. Разработаны общие методы > Сегментация (GrabCut) Оптический поток (Farneback) Стереозрение (SGM) Трекинг (Particle filter) Поиск объектов на изображении (Виола-Джонс, HOG, GHT) Сопоставление с эталоном в условиях загораживания по ключевым точкам (SIFT) по контурам (MRF) Сшивка изображений (SIFT) http://www.cis.upenn.edu/~jshi/GraphTutorial/Tutorial-ImageSegmentationGraph-cut4-Sharon.pdf
- 13. Разработаны общие методы Сегментация (GrabCut) > Оптический поток (Farneback) Стереозрение (SGM) Трекинг (Particle filter) Поиск объектов на изображении (Виола-Джонс, HOG, GHT) Сопоставление с эталоном в условиях загораживания по ключевым точкам (SIFT) по контурам (MRF) Сшивка изображений (SIFT)
- 14. Разработаны общие методы Сегментация (GrabCut) Оптический поток (Farneback) > Стереозрение (SGM) Трекинг (Particle filter) Поиск объектов на изображении (Виола-Джонс, HOG, GHT) Сопоставление с эталоном в условиях загораживания по ключевым точкам (SIFT) по контурам (MRF) Сшивка изображений (SIFT) http://opencv.willowgarage.com/documentation/c/_images/disparity.png
- 15. Разработаны общие методы Сегментация (GrabCut) Оптический поток (Farneback) Стереозрение (SGM) > Трекинг (Particle filter) Поиск объектов на изображении (Виола-Джонс, HOG, GHT) Сопоставление с эталоном в условиях загораживания по ключевым точкам (SIFT) по контурам (MRF) Сшивка изображений (SIFT) http://www.merl.com/projects/images/particle.jpg
- 16. Разработаны общие методы Сегментация (GrabCut) Оптический поток (Farneback) Стереозрение (SGM) Трекинг (Particle filter) > Поиск объектов на изображении (Виола-Джонс, HOG, GHT) Сопоставление с эталоном в условиях загораживания по ключевым точкам (SIFT) по контурам (MRF) Сшивка изображений (SIFT) http://ericbenhaim.free.fr/images/hog_process.png
- 17. Разработаны общие методы Сегментация (GrabCut) Оптический поток (Farneback) Стереозрение (SGM) Трекинг (Particle filter) Поиск объектов на изображении (Виола-Джонс, HOG, GHT) > Сопоставление с эталоном в условиях загораживания по ключевым точкам (SIFT) по контурам (MRF) Сшивка изображений (SIFT) http://robwhess.github.io/opensift/
- 18. Разработаны общие методы Сегментация (GrabCut) Оптический поток (Farneback) Стереозрение (SGM) Трекинг (Particle filter) Поиск объектов на изображении (Виола-Джонс, HOG, GHT) Сопоставление с эталоном в условиях загораживания по ключевым точкам (SIFT) > по контурам (MRF) Сшивка изображений (SIFT) Li 1994a, из книги Li по MRF
- 19. Разработаны общие методы Сегментация (GrabCut) Оптический поток (Farneback) Стереозрение (SGM) Трекинг (Particle filter) Поиск объектов на изображении (Виола-Джонс, HOG, GHT) Сопоставление с эталоном в условиях загораживания по ключевым точкам (SIFT) по контурам (MRF) > Сшивка изображений (SIFT) http://queue.acm.org/detail.cfm?id=2206309
- 21. Задача сопоставления двух изображений • Многие задачи компьютерного зрения являются конкретизацией следующей задачи: ----------------------------------------------------------------------------- Дано два изображения A и B. Требуется их сопоставить между собой, и выдать параметры сопоставления: геометрические, цветовые, показатель надежности. -----------------------------------------------------------------------------
- 22. > Отсутствие геометрических трансформаций Малые локальные сдвиги Большие горизонтальные сдвиги Большой однородный сдвиг в любом направлении Большой однородный сдвиг, поворот, масштабирование A[x,y] ↔ B[x,y] Задача поиска существенных изменений между изображениями Задача сопоставления двух изображений
- 23. Отсутствие геометрических трансформаций > Малые локальные сдвиги Большие горизонтальные сдвиги Большой однородный сдвиг в любом направлении Большой однородный сдвиг, поворот, масштабирование A[x,y] ↔ B[x + epsX, y + epsY] Оптический поток Задача сопоставления двух изображений
- 24. Отсутствие геометрических трансформаций Малые локальные сдвиги > Большие горизонтальные сдвиги Большой однородный сдвиг в любом направлении Большой однородный сдвиг, поворот, масштабирование A[x,y] ↔ B[x + X, y] Стереозрение Задача сопоставления двух изображений
- 25. Отсутствие геометрических трансформаций Малые локальные сдвиги Большие горизонтальные сдвиги > Большой однородный сдвиг в любом направлении Большой однородный сдвиг, поворот, масштабирование A[x,y] ↔ B[x + U, y +V] где U,V – одинаковы для всех (x,y) Сшивка изображений Задача сопоставления двух изображений http://queue.acm.org/detail.cfm?id=2206309
- 26. Отсутствие геометрических трансформаций Малые локальные сдвиги Большие горизонтальные сдвиги Большой однородный сдвиг в любом направлении > Большой однородный сдвиг, поворот, масштабирование A[x,y] ↔ B[ T(x,y) ] где T – афинный оператор Поиск объектов на изображении Задача сопоставления двух изображений
- 28. Комбинаторный взрыв • Количество бинарных изображений размером NxN пикселей – 2N*N . • 1x1 2 изображения • 2x2 16 изображений • 3x3 512 изображений • 5x5 33 554 432 изображений • 10x10 1267650600228229401496703205376 • 100x100 ~103000 (3000 знаков в числе). Это - комбинаторный взрыв: Перебрать всё множество изображений трудно. Приходится сокращать пространство возможных изображений.
- 29. Трудоемкость Число возможных расположений объекта на изображении велико (положение, поворот, размер, искажения). Например, равнобедренный треугольник с шириной и высотой 1..100 пикселей, на изображении 1000x1000 пикселей, 100 углов поворота: 100 * 100 * 1000 * 1000 * 100 = ~1 000 000 000 000 возможных положений для поиска по эталону. Решение этой проблемы: Двухуровневый поиск (грубый – точный масштаб). Поиск объекта по частям (отрезки, углы объекта).
- 31. Проблема слабовыраженных границ http://flogiston.ru/img/invisible_flounder_fish.jpg Как найти камбалу?
- 32. Проблема сегментации сильно-текстурированных объектов http://dangerouswildlife.com/images/zebra-herd.jpg Сколько зебр на снимке?
- 34. Ретроспектива развития методов > 50-е Перцептрон, линейные фильтры 60-е Корреляционные методы, Хаф, Фурье 70-е Математическая морфология • Линейная фильтрация с помощью оптических и аналоговых средств. • Перцептрон Розенблатта – надежда использовать простую модель нейронов мозга для распознавания изображений. Фрэнк Розенблатт со своим компьютером — «Марк-1».
- 35. Ретроспектива развития методов 50-е Перцептрон, линейные фильтры > 60-е Корреляционные методы, Хаф, Фурье 70-е Математическая морфология • Сопоставления с эталоном с помощью корреляции. • Преобразование Хафа для поиска линий – аккумулирование в пространстве параметров модели. • Быстрое преобразование Фурье – надежда на получение устойчивого метода сопоставления с эталоном. • Фильтры границ Собела, Превитта.
- 36. Ретроспектива развития методов 50-е Перцептрон, линейные фильтры 60-е Корреляционные методы, Хаф, Фурье > 70-е Математическая морфология • Морфология Серра – характеризация пористых изображений. • Морфологический анализ Ю.П. Пытьева – оператор морфологического проектирования, инвариантный к изменениям яркостей объектов. http://bme.med.upatras.gr/improc/Morphological%20operators.htm Результат работы морфологического замыкания
- 37. Ретроспектива развития методов > 80-е Дифференциальные и интегральные методы, обобщенный Хаф 90-е Комбинаторные методы и анализ многообразий изображений 2000-е - н.в. Три направления • Метод Канни для поиска контуров. • Методы Люкаса-Канаде и Хорна для вычисления оптического потока. • Метод активных контуров • Обобщенный метод Хафа. • Многомасштабный анализ – надежда на вейвлеты. • RANSAC – стабильный метод оценки параметров модели на основе случайных выборок. http://www.roborealm.com/help/Canny.php
- 38. Ретроспектива развития методов 80-е Дифференциальные и интегральные методы, обобщенный Хаф > 90-е Комбинаторные методы и анализ многообразий изображений 2000-е - н.в. Три направления • Использование множества частиц для трекинга объектов (Particle filter). • Методы анализа изображений как многообразий, PCA (principal component analysis) – построение опорных векторов многообразий, для поиска лиц.
- 39. Ретроспектива развития методов 80-е Дифференциальные и интегральные методы, обобщенный Хаф 90-е Комбинаторные методы и анализ многообразий изображений > 2000-е - н.в. Три направления 1. Общий подход (MRF) для решения многих задач компьютерного зрения. Позволяет формулировать задачу в общей математической формулировке, описанной выше. Модель задачи в виде марковских случайных полей () + наложение модели на изображение с помощью глобальной оптимизации. 2. Сильные признаки (SIFT) Построены признаки, инвариантные к повороту и изменению масштаба, которые можно применять для сопоставления объектов и пр. 3. Простой признак + “сильный” метод принятия решения (HOG, Виола- Джонс) Использование достаточно простых признаков вместе с мощным аппаратом распознавания образов типа SVM и бустинга.
- 40. Заключение 1. Все упомянутые методы, классические и новейшие, используются в различных задачах. 2. Многие алгоритмы реализованы в библиотеке OpenCV и могут быть использованы для «разведки» задачи. 3. Для серъезных приложений необходимы собственные реализации методов, учитывающих специфику задачи.
- 41. Литература Этот доклад будет опубликован тут: www.uralvision.blogspot.com Компьютерное зрение • E. R. Davies, Computer and Machine Vision, 2012. • Гонсалес Р., Вудс Р. Цифровая Обработка Изображений, 2012. • Шапиро Л., Стокман Дж. Компьютерное зрение, 2009. • Форсайт Д., Понс Ж. - Компьютерное зрение. Современный подход, 2004. Список книг по OpenCV http://opencv.willowgarage.com/wiki/OpenCVBooks
Editor's Notes
- #3: Что такое комп. зрение – напомним, что же изучает компьютерное зрение Успехи – пройдемся по задачам, какие в настоящее время считаются успешно решенными. Математика – рассмотрим ретроспективу методов. Проблемы – то, что вызывает трудности в настоящее время.
- #4: Основной объект, над которым ведется работа – это изображение, заданное в виде прямоугольной матрицы чисел. … . Этим компьютерное зрение отличается от линейной алгебры и математической физики, которые также изучают прямоугольные матрицы, но в других целях.
- #5: Низкоуровневая: Фильтрация – операция типа «изображение -> изображение» типа сглаживания и дифференцирования. Выделение точечных особенностей включает обнаружение границ, углов, ярких точек. Вычисление текстурных характеристик в окрестности пикселя. Средства среднего уровня: преобразование Хафа, метод скелетизации, метод активных контуров, RANSAC. Высший уровень: сопоставление с эталоном (контурным и пиксельным, обобщенное преобразование Хафа), распознавание образов ( SVM – метод опорных векторов, и бустинг – каскадное усиление слабых классификаторов). Области пересекаются. Системы реального времени часто используют “ad hoc” – методы, нацеленные на решение конкретной задачи.
- #8: Обнаружение скрытой в траве противопехотной прыгающей мины.
- #11: Авиабомба с оптической головкой
- #13: HOG – гистограмма градиентов. GHT – обобщенное преобразование Хафа. SGM – полуглобальное сопоставление.
- #14: HOG – гистограмма градиентов. GHT – обобщенное преобразование Хафа. SGM – полуглобальное сопоставление.
- #15: HOG – гистограмма градиентов. GHT – обобщенное преобразование Хафа. SGM – полуглобальное сопоставление.
- #16: HOG – гистограмма градиентов. GHT – обобщенное преобразование Хафа. SGM – полуглобальное сопоставление.
- #17: HOG – гистограмма градиентов. GHT – обобщенное преобразование Хафа. SGM – полуглобальное сопоставление.
- #18: HOG – гистограмма градиентов. GHT – обобщенное преобразование Хафа. SGM – полуглобальное сопоставление.
- #19: HOG – гистограмма градиентов. GHT – обобщенное преобразование Хафа. SGM – полуглобальное сопоставление.
- #20: HOG – гистограмма градиентов. GHT – обобщенное преобразование Хафа. SGM – полуглобальное сопоставление.
- #21: Поговорим об общей математической модели, которая используется в основных задачах компьютерного зрения.
- #22: В зависимости от класса допустимых геометрических трансформаций, используемых при сопоставлении, получаются разные известные задачи.
- #27: Хотя формулировка задач компьютерного зрения простая, при практической реализации возникают трудности, которые сейчас рассмотрим.
- #29: Приходится сокращать пространство возможных изображений, которые поступают на вход алгоритма: нормализация, фильтрация шумов, и способы удаления лишней информации – скелетизация при распознавании символов, многомасштабный анализ.
- #30: Является следствием комбинаторного взрыва. Триллион
- #31: Изменение формы вызвано изменчивостью объектов вследствие поворота в 3D и изгибания. Загораживание вызвано трехмерностью мира, из-за чего ближние объекты загораживают дальние.
- #32: Вызывает некоторую трудность построение формальной модели для поиска объекта, когда объект слабо отделим от окружающего фона по границе и текстуре.
- #33: Поэтому, наличие неких трудностей привело к появлению большого спектра методов компьютерного зрения, решающих те или иные задачи. Рассмотрим ретроспективу методов.
- #34: Ретроспектива
- #35: Цифровые компьютеры только появлялись, и поэтому строились аналоговые и оптические вычислители.
- #36: Быстрое преоб. Фурье: позволял быстро осуществлять сопоставление с эталоном (известные свойства инвариантности пр. Фурье к сдвигу давала надежду что это будет устойчивый метод, но он работал только когда объект был один на изображении).
- #37: Морфологическое замыкание = дилатация + эрозия. Видно что в результате замыкания мелкие дырки и тонкая черная линия были устранены. Остались только крупные отверстия. То есть, аппроксимация формы.
- #39: - В компьютерное зрение внедряются мощные методы статистики и распознавания образов.
- #40: В настоящее время найден общий подход, с помощью которого решаются все основные задачи компьютерного зрения. MRF: (имитация отжига, graph cuts). Правда, медленно работает и специализированные методы обгоняют его по качеству и значительно обгоняют по скорости работы. Виола-Джонс - поиск лиц: признаки типа Хаара (разность значений сумм яркостей двух прямоугольных областей) + бустинг. Обучение на основе большой базы примеров. HOG - поиск пешеходов, животных, велосипедов. разбиение изображения на прямоугольные фрагменты и построение статистики направлений границ в них. + SVM (support vector machines - построение разделяющей функции с помощью гауссовой суммы положительных и отрицательных примеров). Обучение на основе большой базы примеров.