Распознавание изображений. Выделение признаков

1.  Распознавание изображений: Выделение признаков

Нижегородский государственный университет им. Н.И. Лобачевского
Физический факультет
Кафедра информационных технологий в физических исследованиях
 Распознавание изображений:
Выделение признаков
подготовил: аспирант 1 года
Чуманкин Юрий Евгеньевич
 
1

2. Распознавание изображений

Распознавание изображений
• ~ 90% информации человек получает через 
зрение
• Это очень информативный источник
• Множество рутинной работы людей связано с 
распознаванием изображений
– Гаишник высматривает нарушителей
– Работник завода ищет бракованные детали
– Охранник сверяет фото на пропуске с лицом человека
• Было бы здорово автоматизировать эту работу
2

3. Распознавание изображений

Распознавание изображений
• В XXI веке появились большие 
вычислительные мощности
• Получать цифровые изображения стало 
очень просто
3

4. Распознавание изображений

Распознавание изображений
• За последние 10 лет произошел 
огромный толчок
• КЗ нашло свое применение:
– Распознавание людей
(отпечаток пальца, лицо, сетчатка)
– Контроль подлинности 
(банкнот, документов)
– Распознавание текста (ABBY)
– Интеллектуальное видеонаблюдение 
(системы безопасности, письма 
счастья)
– Контроль качества 
(подсчет длины очереди, поиск течи в 
трубе)
4

5. Задача распознавания

Задача распознавания
• Сужаем класс задач
• Наши условия:
– Есть изображение
– На нем есть объект
– Необходимо отнести его к 
одному из известных классов, т.е. 
решить задачу классификации
Пример: 
• Распознать букву
• Распознать чей отпечаток
5

6. Общий алгоритм

Общий алгоритм
Предварительная 
обработка
• Положение и 
размеры 
объекта
Выделение 
признаков
• Нечто, по 
которому можно 
судить об объекте
Принятие 
решения
• Класс 
объекта
6

7. Фильтрация от шума

Фильтрация от шума
• На всех реальных изображениях присутствует шум
• Шум распределен 
в широкой полосе
частот
• Не понятно как 
отделить его от
изображения
7

8. Фильтры низких частот

Фильтры низких частот
– Фильтр низких частот
• Свертка с прямоугольным окном
• Свертка с гауссовым окном
x2 y2
1
g ( x, y )
exp
2
2
8

9. Медианный фильтр

Медианный фильтр
• Выбор окрестности
• Сортировка
• Выбор значения из середины
9

10. Фильтрация от шума

Фильтрация от шума
10

11. Метод наращивания и соединения областей

Метод наращивания и соединения 
областей
Исходное изображение
Смежные области объединяются
Наращивание 
Промежуточных областей
Сегментированное изображение
11

12. Результат сегментации

Результат сегментации
12

13. Есть картинка, и что?

Есть картинка, и что?
• Компьютер понимает только
формальное описание
• Например классификацию точек на 
плоскости он бы провести смог
13

14. Что отличает изображение от точки в пространстве?

Что отличает изображение от точки в 
пространстве?
• Очень много информации
– На обычном hd снимке 1280 * 720 ~ 1 млн. 
пикселей
• Сложно обрабатывать такие большие 
массивы данных
• Не вся информация является полезной для 
распознавания
• Есть информация которая сбивает с толку
14

15. Проблемы освещенности

Проблемы освещенности
15

16. Искажения перспективы

Искажения перспективы
16

17. Аберрации линзы (рыбий глаз)

Аберрации линзы 
(рыбий глаз)
17

18. Вариация формы

Вариация формы
18

19. Встречаются почти всегда

Встречаются почти всегда
Эталон
Сдвиг
Масштабное
преобразование
19
Поворот

20. Выделение признаков для изображений символов

Выделение признаков для изображений 
символов
• Предположения:
– Изображение полутоновое
– Символ на картинке один
• Задача:
– Сопоставить изображению набор чисел, 
достаточный для классификации
– Учесть смещение символа
– Учесть символы разных масштабов
– Учесть символы повернутые на разный угол
20

21. Математическое представление изображения

Математическое представление 
изображения
• Это функция двух переменных (непрерывный случай)
• Это матрица (дискретный случай)
21

22. Математическое представление изображения

Математическое представление 
изображения
Справедливы:
• Сложение
• Вычитание
• Умножение
• Деление
• Возведение в 
степень
• И т.д.
 
…
22

23. Физическое представление изображения

Физическое представление изображения
Это плоская фигура (непрерывный случай)
Это система материальных точек (дискретный случай)
• Чем светлее фрагмент, тем больше он весит
• Интенсивность (I) выступает в роли плотности
• Здесь и далее рассматриваем буквы
23

24. Инвариантность относительно сдвига

Инвариантность относительно сдвига
• Буква – это твердое тело
• С каждой  точкой ТТ можно связать 
систему координат
 
24

25. Выбор начала отсчета

Выбор начала отсчета
• Нормальный выбор – центр буквы
• Очень просто вычислить
• Но что происходит при слабом изменении 
формы?
 
25

26. Центр масс изображения

Центр масс изображения
•• Если высота буквы выросла на , то начало отсчета 
 
сместился на /2
• Можно ли добиться того, чтобы начало отсчета смещалось 
меньше?
• Вспоминая физическое представление изображения 
можно вычислить центр масс 
N 1 M 1
I 0 I (i, j )
i 0 j 0
1
xc
I0
1
yc
I0
I 0 I ( x, y )dxdy
N 1 M 1
jI (i, j )
i 0 j 0
N 1 M 1
iI (i, j )
i 0 j 0
xc
1
I0
x I ( x, y)dxdy
yc
1
I0
y I ( x, y)dxdy
26

27. Центр масс изображения

Центр масс изображения
•• Если I=const,
то смещение становится 
 
пропорционально не а  
•      =>      центр масс сменится не сильно
• Центр масс – это статистическая характеристика 
(среднее), она устойчива к слабым изменениям 
формы
 
 
27

28. Инвариантность относительно масштаба

Инвариантность относительно масштаба
• Надо изменить масштаб 
распознаваемого изображения
• Какую область масштабировать?
• Во сколько раз?
28

29. Какую область масштабировать?

Какую область масштабировать?
29

30. Какую область масштабировать?

Какую область масштабировать?
• Она должна быть связана с размерами 
символа
• Можно выбрать описанный квадрат или 
круг
• Недостатки все те же, что и раньше
• Выгоднее опираться на статистические 
характеристики
30

31. Статистические характеристики

Статистические характеристики
• Удобно рассмотреть распределение 
пикселей по удаленности от центра масс
• Это функция ρ(r)
– По горизонтальной оси – удаление от центра масс
– По вертикальной оси количество пикселей, которые 
находятся на таком расстоянии от центра масс
 
31
 

32. Статистические характеристики

Статистические характеристики
• Область точно не надо брать уже, чем 
математическое ожидание расстояния
• Насколько велик разброс пикселей вокруг 
среднего показывает дисперсия
 
 
 
32
 

33. Статистические характеристики

Статистические характеристики
•  
•   подбирается экспериментально
• Исследования для символов латинского 
алфавита дают  =2,5 (по теории должно 
быть не больше 3)
33

34. Во сколько раз масштабировать?

Во сколько раз масштабировать?
• Под размер шаблона с которым будет делаться 
сравнение
Шаблон должен быть 
• не слишком маленьким
– Теряются детали
• Не слишком большим
– Долго обрабатывать
• Исследования
показали что
оптимальный размер 
30 пикселей
34

35. Не случится ли беды?

Не случится ли беды?
 
Делаем масштабирование в прямом пространстве
Растяжение переходит в сжатие, сжатие в растяжение
– a < 1 – все хорошо
– a > 1 – появились новые высокие частоты
35

36. Не случится ли беды?

Не случится ли беды?
• Появление высоких частот при 
фиксированной частоте дискретизации 
может привести к невыполнению теоремы 
Котельникова
• Это означает потерю информации
• Чтобы этого не произошло надо убрать 
высокие частоты из исходной картинки
36

37. Этапы масштабной нормализации

Этапы масштабной нормализации
Исходный символ
Отмасштабированный
Свертка с 
символ
Гауссовым фильтром
37

38. Линейная алгебра

Линейная алгебра
• Функция это элемент гильбертова 
пространства. Как вектор.
• Скалярное произведение:
f1 | f 2 f1 x, y f 2 x, y dxdy
f | f f i f i
N 1
1
2
i 0
1
2
• Ортонормированный базис:
f j | f i ij
38

39. Разложение векторов

Разложение векторов
• Если размерность базиса (кол-во векторов в 
нем) совпадает с размерностью 
пространства, то по такому базису можно 
делать разложение
• В общем случае:
| f | e
j
j
j
e | e
i
j
j
ei | f
j
• Для ортонормированного базиса
i ei | f
39

40. Моменты

• В функциональном пространстве 
скалярное произведение f(x) на g(x) 
назвали:
– Момент f(x) относительно g(x)
• Базисы есть разные, еще момент 
называют по имени базиса
• Какие базисы используются?
40

41. Базисы

Не ортогональный:
• Регулярный базис
m p ,q
p q
x
y f x, y dxdy
– Регулярные моменты
Ортогональные
• Базис Цернике
Anm Vnm ( x, y ) I ( x, y )dxdy
– Моменты Цернике
• Базис Уолша
– Моменты Уолша
41

42. Полиномы Цернике

Полиномы Цернике
Vnm ( x, y ) Vnm ( , ) Rnm ( ) exp( jm )
n s !
n 1 ( n |m|) / 2
1 s
R
n 2 s
nm
s 0
n | m | n | m |
s!
s !
s !
2
2
• Ортогональность
• Легко восстановить 
изображение
• Коэффициенты слабо 
коррелированы
• Модуль коэффициентов
   инвариантен к повороту
42

43. Восстановление изображения

Восстановление изображения
• Чтобы восстановить изображение надо 
найти коэффициенты
ei | e j j ei | f
j
i ei | f
• Формула для восстановления
| f j | e j
j
43

44. А если изображение повернуто?

А если изображение повернуто?
• Выбираем признаки
• Либо надо исключить информацию о 
повороте
• Либо надо все изображения развернуть в 
исходное положение
44

45. Поворот в исходное положение

Поворот в исходное положение
• Вспомним физическую 
интерпретацию 
изображения
• Как у любого твердого 
тела,
у буквы есть собственная 
система координат
45

46. Определение поворота по собственной системе координат

Определение поворота по собственной 
системе координат
• Рассчитывается тензор инерции
• Определяются собственные 
направления
• Сравниваются направления 
шаблона и изображения
m pq
m20 m11
p q
I ( x, y )x y dxdy J ij m
m02
11
m m m m 2 4m 2
20
02
20
11
02
arctan
2m11
46

47. Модуль моментов

Модуль моментов
• Возьмем модуль от моментов Цернике
1 2
An ,m
R exp jm f , d d
nm
0 0
1 2
1 2
R exp jm f , d d R f , d d
nm
nm
0 0
0 0
• Сделаем сдвиг
1 2
1 2
R f , a d d R f , d d
nm
0 0
nm
0 0
• Очень удобно
47

48. Выбор признаков

Выбор признаков
• Коэффициент с n=0 вносит большую 
ошибку
• Коэффициент с n=1 пропорционален rc
• nmax = 12
• Всего 48 
признаков
• Они будут инвариантны к повороту
48