Похожие презентации:
Системы компьютерного зрения. Лекция 2
1. Системы компьютерного зрения
Лекция 2На основе лекций «Введение в компьютерное зрение»
в МГУ, авторы - В.Вежневец, А.Конушин, В.Вежневец
1
2. Анализ изображений
Темы этой лекцииВыделение краев
Градиент изображения
Алгоритм Canny
Работа с контурами
Цепные коды
Полигональная аппроксимация
-s представление
Дескрипторы контуров
Как проводить прикладное исследование?
Slide 2
3. Выделение краев
Цель – преобразовать изображение в набор кривых для:выделения существенных характеристик
сокращения объема информации для анализа
Slide 3
4. Выделение краев
Slide 45. Откуда берутся края?
Край – резкий переход яркости.Различные причины возникновения:
Резкое изменение нормали поверхности
Резкое изменение глубины сцены
Резкое изменение цвета поверхности
Резкое изменение освещенности
Slide 5
6. Как найти резкое изменение яркости?
Нас интересуют области резкогоизменения яркости – нахождение
таких областей можно
организовать на основе анализа
первой и второй производной
изображения.
График
функции
График
производной
Рассмотрим одномерный
случай…
График 2ой
производной
Slide 6
7. Как найти резкое изменение яркости?
Известно, что наибольшее изменение функции происходитв направлении ее градиента. Величина изменения
измеряется абсолютной величиной градиента.
I
I
I ( x, y ) ( x, y ), ( x, y ) ;
y
x
I
I
I ( x, y ) ( x, y ) ( x, y )
x
y
2
2
Slide 7
8. Градиент яркости изображения
Известно, что наибольшее изменение функциипроисходит в направлении ее градиента
Приведем примеры…
f
f ,0
x
f
f 0,
y
f
arctan
y
f f
f ,
x y
f
x
Slide 8
9. Градиент яркости изображения
Направление градиента задается:f f
y
x
«Направление края» задается перпендикулярным градиенту
arctan
«Сила края» задается абсолютной величиной градиента:
I
I
I ( x, y ) ( x, y ) ( x, y )
x
y
2
2
Иногда используется приближенное вычисление градиента:
I
I
I ( x, y )
( x, y )
( x, y )
x
y
Slide 9
10. Вычисление градиента яркости изображения
Семейство методов основано на приближенномвычисление градиента, анализе его направления и
абсолютной величины. Свертка по функциям:
1
0
0
1
0
1
Робертса
1
0
- 1 1 1
0 0 0
1 1 1
-1
1
1
Превитт
0
0
0
1
1
1
-1
0
1
2
0
2
1
0
1
-1
2
1
0
0
0
1
2
1
Собеля
Математический смысл – приближенное вычисление
производных по направлению
Slide 10
11. Карта силы краев
Примеры:Робертса
Превитт
Собеля
Slide 11
12. Выделение краев
Вычисление градиента – это еще не всё…Исходное изображение
Карта силы краев
Чего не хватает?
Точности – края «толстые» и размытые
Информации о связности
Slide 12
13. Выделение краев
Нужно:Убрать слабые края и шум
Сделать края тонкими
Объединить пиксели краев в связные кривые
Slide 13
14. Алгоритм Canny
Давно придуман, однако до сих пор широкоиспользуется
Шаги:
Убрать шум и лишние детали из изображения
Рассчитать градиент изображения
Сделать края тонкими (edge thinning )
Связать края в контура (edge linking)
Slide 14
15. Начало…
Размыть изображение с помощью фильтра ГауссаУбрать шум, лишние детали текстуры
Рассчитать градиент изображения
Одним из операторов – например, Собеля
Исходное изображение
Размытое изображение
Карта силы краев
Slide 15
16. …середина…
Все пиксели где сила краев < T убрать израссмотрения
Slide 16
17. …середина…
Поиск локальных максимумовПроверяя – является ли пиксель локальным
максимумом вдоль направления градиента
Приходится интерполировать «нецелые» пиксели p и r
Slide 17
18. … финал
1.2.
Выбираем еще не обработанную точку локального
максимума p в которой сила края I ( p) T1
Прослеживание края выбранного локального
максимума p:
a)
Предсказание следующей точки края q;
b)
Проверка – I (q) T2 ? (T1 T2 )
c)
d)
Если да – p = q, переход на начало шага 2;
Если нет - переход на шаг 1;
Slide 18
19. Пояснения
Как предсказать следующую точку края?От текущей точки шаг в сторону перпендикулярную
градиенту
В данном случае – в точку r или s
Slide 19
20. Пояснения
Для чего используются два порога? (T1 T2 )1.
1.
2.
Чтобы уменьшить влияние шума для инициализации
кривой используем больший порог
Чтобы «не потерять хвост» используем меньший порог при
прослеживании
T1
T2
Slide 20
21. Алгоритм Canny
Размыть изображение фильтром Гаусса c некоторым σУбрать шум, лишние детали текстуры
Рассчитать градиент изображения
Одним из операторов – например, Собеля
Все пиксели где сила краев < T убрать из рассмотрения
Поиск локальных максимумов
Прослеживание краев из точек локальных максимумов
Slide 21
22. Canny - результат
Slide 2223. Влияние (параметр фильтра Гаусса)
Влияние (параметр фильтра Гаусса)исходное
Canny с
Canny с
Slide 23
24. Вопрос
? Получив контур объекта (связный наборпикселей) – как его дальше
анализировать?
!
Вариант - нужно преобразовать контур
в некоторое численное представление
Один из способов – использование цепных
кодов
Slide 24
25. Работа с контурами
Полигональная аппроксимацияЦепные коды
Дескрипторы контуров
Slide 25
26. Полигональная аппроксимация
Постановка:Аппроксимация точечной кривой ломаной линией
Цель:
Сжатие информации
Борьба с дискретностью и шумом
Облегчение дальнейшего анализа
Slide 26
27. Полигональная аппроксимация
Постановка:Аппроксимация точечной кривой ломаной линией
Цель:
Сжатие информации
Борьба с дискретностью и шумом
Облегчение дальнейшего анализа
Slide 27
28. Алгоритм Дугласа-Пекера (рекурсивное подразбиение)
Инициализация – начнем с прямой, идущейот начальной точки к конечной
Если контур замкнутый – выберем точки
максимально удаленные друг от друга
Slide 28
29. Алгоритм Дугласа-Пекера (рекурсивное подразбиение)
Шаг №1 – найти точку контура максимальноудаленную от прямой
Если расстояние от нее до прямой d < ε –
разбиение завершено, если нет – к шагу 2
d
Slide 29
30. Алгоритм Дугласа-Пекера (рекурсивное подразбиение)
Шаг №2 – добавить узел к ломаной линииЗатем рекурсивно вызвать Шаг №1 для каждой из
половинок ломаной
Slide 30
31. Алгоритм Дугласа-Пекера (рекурсивное подразбиение)
Результат:Slide 31
32. Цепной код – 8-ми связные контура
76
0
1
5
4
2
3
Кодирование контура как последовательности перемещений
Код: 12232445466601760
Slide 32
33. Цепной код – 4-х связные контура
30
2
1
Кодирование контура как последовательности перемещений
Код: 1122322333010033010112
Slide 33
34. Цепной код - свойства
СвойстваЦепной код – представление контура, независимое к его
перемещению
При замене в 8-ми связном кода любого n но (n mod 8) + 1 контур
будет повернут по часовой стрелке на 45 градусов
Некоторые особенности контуров, такие как уголки, например могут
быть сразу рассчитаны по анализу цепных кодов
Сложности
В цепном коде важна начальная точка – при ее изменении
меняется и код
Небольшие вариации границы (шум) серьезно меняют код.
Сравнение двух шумных контуров по цепному коды – сложно
Цепной код не инвариантен к повороту
Slide 34
35. Разностный код
Это «производная» цепного кодаФормула
yi = (xi+1- xi ) mod 8 – восьмисвязный
yi = (xi+1- xi) mod 4 – четырехсвязный
Slide 35
36. Разностный код
Свойства:Инвариантен к повороту кратному 45
градусам (восьмисвязный)
Проблемы:
Также чувствителен к шуму
Не инвариантен к повороту на
произвольный угол
Slide 36
37. -s представление
-s представлениеАналогично считаем направление контура в
каждой точке, но:
Направление не ограничиваем точностью в 45
градусов – считаем точную касательную (угол ψ)
Slide 37
38. -s представление
-s представлениеОбратите внимание:
Результирующая функция ψ(s) зависит от длины
дуги s (при движении «наискосок» она
увеличивается быстрее)
√2
1
1
√2
√2
1
1
√2
Расстояние между соседними пикселами
Slide 38
39. -s представление
-s представлениеNB на данном графике ось абсцисс – не длина дуги,
а ее горизонтальная проекция (для наглядности)
Slide 39
40. -s представление
-s представлениеСвойства:
Если нормировать полную длину к 1 – инвариантно к
масштабу
Несложным преобразованием можно свести к
практически инвариантной к повороту мере
Как быстро сравнить между собой две функции ψ(s)?
Использовать функцию плотности наклона
(slope density function)
Это гистограмма распределения углов наклона
касательной контура
Slide 40
41. Кривизна
Кривизна (curvature) – производная ψ(s)Аналогично разностному цепному коду, но со знаком
K (s) (s) ( s 1)
Представление, инвариантное к повороту
и переносу
Функция плотности кривизны
Гистограмма распределения значений кривизны
Slide 41
42. Дескрипторы Фурье
Контур задается набором точек:( xi , yi ), i 1,2,..., L
( xc , yc ) ( L1 xi , L1 yi )
i
2
i
ri [ xi xc ] [ yi yc ]2
Кол-во точек нормализуется к некоторому числу N
Вычисляем коэффициенты дискретного ПФ:
2 N 1
N
2 n i
An ri cos
, n 1,2,..., 1
N i 0
2
N
1 N 1
N
2 n i
An ri cos
, n 0,
N i 0
2
N
2 N 1
N
2 n i
Bn ri sin
, n 0,2,...,
N i 0
2
N
Slide 42
43. Дескрипторы Фурье
Вычисляем амплитуды коэффициентов:Cn An2 Bn2
Дескрипторы:
| C1 | | C2 |
| CN / 2 |
f
,
,...,
|
C
|
|
C
|
|
C
|
0
0
0
Свойства:
Инвариантны к переносу (вычли среднюю точку)
Инвариантны к повороту (берем модули коэффициентов)
Инвариантны к масштабу (нормировали на нулевой коэффициент)
Общая форма – первые по порядку дескрипторы,
детали и шум – в конце
Нельзя характеризовать локальные особенности кривой
Slide 43
44. Признаки для распознавания контуров
Цепной код (разностный код)-s представление
Функция плотности наклона
(slope density function)
Функция плотности кривизны
(curvature density function)
Дескрипторы Фурье
Slide 44
45. Как вести прикладное исследование?
Подготовительный этап1.
Уяснить постановку задачи
2.
Собрать данные для проверки работы методов
3.
Провести обзор литературы
4.
Уяснить отличия, сильные/слабые стороны методов,
трудоемкость реализации
Фиксировать критерии сравнения до начала обзора
Выбрать потенциально подходящие методы
Slide 45
46. Как вести прикладное исследование?
Экспериментальный этап1.
Составить план экспериментов
Какие характеристики и как именно будет проверяться
(скорость, точность, устойчивость и т.д.)
2.
Провести проверку методов на собранных данных
3.
Если один из методов работает приемлемо
4.
выбираем его
Если ни один метод приемлемо не работает
Анализируем проблемы и причины ошибок
Делаем предположения – что именно может помочь
Создаем свой метод или комбинируем несколько методов,
основываясь на сделанных предположениях
Переходим на шаг 2 для проверки предположений
Slide 46