Обработка и распознавание изображений. Поиск и прослеживание границ объектов на изображениях

1. ОБРАБОТКА И РАСПОЗНАВАНИЕ ИЗОБРАЖЕНИЙ

Леонид Моисеевич Местецкий
профессор
кафедра математических методов
прогнозирования ВМК МГУ
кафедра интеллектуальных систем МФТИ
1

2.

Поиск и прослеживание границ
объектов на изображениях
Граничное представление формы объектов,
отслеживание и аппроксимация границ
цифрового изображения
2

3. Генерация признаков формы на основе анализа границ

• Исходное описание образа в виде бинарного
изображения
• Выделение границ образа
• Построение признакового описания на основе
анализа границ
3

4. Форма объекта

Термин форма обычно используется для
обозначения внешности объекта или его
внешней границы (контур, внешняя
поверхность), в отличие от других
свойств, таких как цвет, текстура, состав
материала.
4

5. Распознавание формы

5

6. Распознавание формы

6

7. Распознавание формы

7

8. Пример управления компьютером жестами на основе анализа формы

GestureDemo-2
8

9. Бинарные изображения ладони

9

10. Проблема построения границ объекта

Что считается границей объекта на цифровом
изображении?
Demo - Tracer
10

11. Построение границы на основе трассировки границ объекта

Трассировка границы объекта может быть
представлено как прогулка вокруг лужи.
11

12. Поиск начальной пары разноцветных пикселей

12

13. Обход методом ползущего жука

В чёрных точках поворот направо, в белых - налево
52 шага = 28 налево + 24 направо
13

14. Обход катящимся треугольником (симлекс-прослеживание)

На каждом шаге – переворот треугольника
51 шаг
14

15. Симплексное прослеживание

Прослеживание катящимся треугольником (симплексом)
15

16. Начальный треугольник

16

17. Переворот треугольника

17

18. Новое положение треугольника

18

19. Условие завершения обхода

19

20. Обход подвижным мостом

Каждая итерация – сначала шаг правой ногой, а
затем, возможно, шаг левой ногой
55 шагов
20

21. Получение граничного коридора

Ползущий жук
Катящийся
симплекс
Подвижный
мост
Белая и черная границы коридора могут
рассматриваться как граница объекта
21

22. Аппроксимация границы многоугольником

(b)
(d)
(a)
(c)
• аппроксимация внутренней (b) или внешней (c) стенок граничного
коридора
• аппроксимация средней линией граничного коридора (d)
22

23. Кратчайший путь в коридоре

Кратчайший путь – резиновая замкнутая нить,
лежащая внутри коридора, обозначенного черными
и белыми гвоздями
23

24. Аппроксимация многоугольником минимального периметра

(а)
(b)
(c)
Геодезический маршрут внутри граничного коридора
24

25. Угловые точки и секторы обзора

Последовательный выбор
угловых точек
A
L
R
25

26. Положение точки относительно сектора обзора

1
2
Точка лежит внутри, слева или справа относительно
3 сектора обзора
26

27. Правило коррекции сектора обзора

Изменение границ
сектора
(a)
(b)
Новая угловая
точка
(c)
(d)
Нет коррекции и
новой угловой
точки
(e)
(f)
27

28. Алгоритм вытягивания нити

и т.д.
28

29. Алгоритм вытягивания нити - результат

29

30. Как построить все контура границы?

30

31. Последовательный поиск и прослеживание контуров границы

При трассировке контура необходимо пометить все горизонтальные
разноцветные граничные пары
Поиск нового контура - это поиск разноцветной пары, в которой хотя бы один
пиксель не помечен
31

32. Основные свойства минимальных разделяющих многоугольников

• Математическая корректность
• Возможность настройки на заданные
требования по точности аппроксимации
• Высокая вычислительная эффективность
32

33. Преимущества метода

• В результате отслеживания мы получаем
последовательность граничных точек, которые
перечислены в порядке обхода
• Полученная последовательность точек может быть
аппроксимирована многоугольником
• Аппроксимация границы разделяющими
многоугольниками минимального периметра гарантирует
отсутствие пересечений и самопересечений
многоугольников
Demo - Tracer
33

34. Генерация признаков формы по многоугольной границе

–Длина границы (периметр)
–Площадь фигуры
–Округлость фигуры
–Энергия изгиба
–Количество углов
–Количество отверстий
–Дескриптор Фурье
34

35. Геометрические признаки

35

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

36

37. Свойства дескриптора Фурье

37

38. Свойства дескриптора Фурье

38

39. Восстановление границы по дескриптору Фурье

Слева – исходное изображение
Справа – результат восстановления границы по дескриптору Фурье
В окошке – количество использованных коэффициентов Фурье
39

40. Зависимость точности восстановления от количества коэффициентов Фурье

40