Основные подходы в решении задач на распознавание Антон Масалович

Распознавание образов Задача распознавания Множество объектов Система распознавания Множество классов 2

Распознавание образов Примеры задач распознавания Face Detection Фотографии Области с лицами людей Face Recognition Изображение лица Имя человека из базы данных Биометрия Сетчатка глаза, отпечатки пальцев, силуэт ладони Подтверждение идентификации Computer-aided diagnosis Рентгеновские снимки Подтверждение диагноза Распознавание речи Звуки голоса Набор команд для компьютера 3

Распознавание образов Примеры задач распознавания Анти-Спам Электронные письма Спам не-Спам Поиск в интернете Пары запрос-сайт Оценка релевантности сайта запросу Распознавание логотипов Ролики на YouTube Наличие логотипов известных каналов Поиск текста Область изображения Наличие в нем текста Распознавание текста Изображения символов Текст 4

Распознавание образов ACM ICPC 2011 Final, задача C The image contains only hieroglyphs shown in Figure C.1. Each image contains at least one valid hieroglyph. Each black pixel in the image is part of a valid hieroglyph. Each hieroglyph consists of a connected set of black pixels and each black pixel has at least one other black pixel on its top, bottom, left, or right side. The hieroglyphs do not touch and no hieroglyph is inside another hieroglyph. Two black pixels that touch diagonally will always have a common touching black pixel. The hieroglyphs may be distorted but each has a shape that is topologically equivalent to one of the symbols in Figure C.11. 5

Распознавание образов Усложенение The hieroglyphs may be distorted but each has a shape that is topologically equivalent to one of the symbols in Figure C.11. The hieroglyphs may be distorted but each has a shape that most people can recognize as one of the symbols in Figure C.11. 6

Распознавание образов Поиск текста на изображении 7

Распознавание образов Уточнение задачи 8 ТекстФон

Распознавание образов Уточнение задачи На входе системы распознавания – изображение фиксированного размера (n*n пикселей). Ответ системы распознавания – переданное изображение принадлежит области текста или области фона. 9

Распознавание образов Расширение системы распознавания 10 Множество объектов Выделение признаков Множество признаков Система распознавания Результаты классификации Решающее правило Итоговое решение

Распознавание образов Пространство признаков Соответствие классам Расстояние между объектами Избыточность Наиболее частый пример пространства признаков – числовой вектор признаков фиксированной длины. Много «слабых» признаков и «сильный» классификатор VS немного «сильных» признаков и «слабый» классификатор. 11

Распознавание образов ABBYY Cup 2.0, задача Е Дано монохромное изображение, то есть изображение, состоящее из двух цветов (черного и белого). Белый цвет на заданном изображении соответствует фону. Также на изображении присутствуют геометрические фигуры. Они имеют черный цвет. Известно, что изображение может содержать только два типа фигур: квадраты и круги. Вам требуется посчитать число кругов и число квадратов, которые содержатся на заданном изображении. Квадраты на изображении могут быть повернуты произвольным образом. Кроме этого, в изображении возможен шум, устроенный следующим образом: каждый пиксель исходного изображения может с вероятностью 20% поменять свой цвет на противоположный. 12

Распознавание образов Обработка изображения Размытие Бинаризация Выделение связанных областей 13

Распознавание образов Выделение признаков Самый простой признак – отношение квадрата периметра фигуры к ее площади. Минимальное значение у круга – 4 * Pi У квадрата – 16 Достаточно, чтобы отличать круг от квадрата на хорошем изображении. Проблема с мелкими изображениями и с дефектами границы. 14

Распознавание образов Преобразование Хафа Уравнение прямой на плоскости (x,y): Преобразование Хафа – переход из пространства (x,y) в пространство (theta,r) Для каждой черной точки на изображении мы отмечаем в пространстве (theta,r) все возможные прямые, которые проходят через эту точку. Если на исходном изображении есть прямая линия – в преобразованном пространстве координата этой линии будет иметь большой вес. Для квадрата на преобразованном изображении будет 4 ярко выраженные точки. Для круга преобразованное изображение будет более-менее равномерным. 15

Распознавание образов Преобразование Хафа 16

Распознавание образов Преобразование Хафа 17

Распознавание образов Этап Открытого кубка России 2011–2012, задача H На плоскости нарисовано несколько прямых сегментов. В качестве входных данных дана очень грубая растеризация этой плоскости. Задача – найти число сегментов на изображении. 18

Распознавание образов Нормализация изображения Есть много разных вариантов Найти на изображении серединную ось, привести ее к вертикали. Найти на изображении центр масс, максимально далекую от него точку, полученный отрезок привести к вертикали. … 19

Распознавание образов Растровое распознавание В задаче с иероглифами можно использовать растровое распознавание. Создаем процедуру приведения изображения к эталонному виду. Исходные изображения все приводим к стандартному виду и запоминаем как эталоны. Распознаваемый объект сравниваем со всеми эталонами (изображения сравниваются попиксельно простым наложением). В качестве ответа выбираем то, изображение, которое больше всего похоже на эталон. Растровое распознавание плохо работает в реальных задачах! 20

Распознавание образов Выделение признаков Нормализуем изображение каким-нибудь образом. Разобьем изображение на несколько зон. В каждой зоне посчитаем простые признаки, к примеру количество черного или периметр черного. Существуют признаки инвариантные к поворотам и растяжениям. К примеру центральные моменты. 21

Распознавание образов Выборка Выборка – набор распознаваемых объектов, для которых проставлена правильная классификация. Выборки используются для создания и тестирования систем распознавания. 22

Распознавание образов Пример выборки для поиска текста ФонТекст 23

Распознавание образов Выборка – обучающая и тестовая Обучающая выборка нужна для подбора параметров системы распознавания. Параметры системы распознавания подбираются так, чтобы повысить качество распознавания на обучающей выборке. Тестовая выборка нужна, чтобы определить насколько хорошо наша система будет работать на реальных данных. Тестовая выборка не должна входить в обучающую выборку. 24

Распознавание образов Обучение системы распознавания Обучение – использование обучающей выборки для подбора параметров системы распознавания. Стандартная задача обучения – подобрать параметры системы распознавания так, чтобы ошибка распознавания по всей обучающей выборке была минимальна. 25

Распознавание образов Метод k-ближайших соседей Выбираем нечетное небольшое число k. При обучении мы сохраняем всю обучающую выборку целиком. При распознавании объекта находим в сохраненной обучающей выборке k объектов, лежащих ближе всего к распознаваемому. Для выбранных объектов смотрим, объектов первого или второго класса там больше. Тот класс у которого преимущество и считаем результатом распознавания. На удивление нормальная точность, очень низкая скорость. Хорошо для начальных экспериментов и оценки качества выбранных признаков. 26

Распознавание образов Метод одного ближайшего соседа 27

Распознавание образов Байесовский классификатор Наблюдаемый нами объект – это случайная величина. Мы должны классифицировать наши объекты на два класса. Объекты каждого класса имеют свое распределение (которое мы можем оценить). Для наблюдаемого нами объекта нам нужно посчитать вероятность, что он принадлежит первому или второму классу. 28

Распознавание образов Распределение параметров Бинарные признаки. Нормальное распределение. 29

Распознавание образов Нормальное распределение (общий случай) 30

Распознавание образов Поверхность решения 31

Распознавание образов Поверхность решения 32 Общая формула Независимые признаки

Распознавание образов Поверхность решения 33

Распознавание образов Линейный классификатор 34

Распознавание образов Функция оценки 35

Распознавание образов Оценка одного прецедента 36

Распознавание образов Оценка одного прецедента 37

Распознавание образов Оценка одного прецедента 38

Распознавание образов Функция оценки 39

Распознавание образов Линейная поверхность решения 40

Распознавание образов Линейный классификатор Из линейного классификатора можно сделать нелинейный, если мы добавим к пространству признаков дополнительные функции от исходных признаков, к примеру полиномы. 41

Распознавание образов Сложность системы распознавания

Распознавание образов Сложность системы распознавания Высокая точность на обучающей выборке, низкая на тестовой выборке – понизить сложность системы распознавания, сократить число признаков. Низкая точность на обучающей выборке, низкая точность на тестовой выборке – повысить сложность системы распознавания, добавить дополнительные признаки. 43

Распознавание образов Многоклассовая классификация Все-к-одному Строится p классификаторов, i-ый классификатор отделяет объекты i-ого класса от всех остальных. При распознавании выбирается тот класс чей классификатор единственный дал положительный результат. Все-ко-всем Строится p*(p-1)/2 классификаторов. Каждый классификатор разделяет два конкретных класса. При распознавании каждый классификатор отдает свой голос одному из классов. Выбирается класс с наибольшим количеством голосов. 44

Распознавание образов Многоклассовая классификация

Распознавание образов Оценка системы распознавания Реальный класс PositiveNegative Результат распознавания Positive Правильно распознанные положительные примеры TP Неверно распознанные отрицательные примеры FP Negative Неверно распознанные положительные примеры FN Правильно распознанные отрицательные примеры TN 46

Распознавание образов Оценка системы распознавания 47 Наивная оценка ошибки. Не учитывает, что в тестовой выборке элементов одного класса может быть сильно больше, чем элементов другого. Как пример – в выборке может быть 1000 негативных примеров и 10 позитивных примеров. И если мы будем распознавать все элементы как негативные – мы все равно получим аккуратность = 1000/1010 = 99%.

Распознавание образов Оценка системы распознавания 48

Распознавание образов Кластеризация У нас есть выборка объектов. В выборке не проставлено классов, но мы знаем, что в выборке может быть несколько разных типов объектов с различающимися признаками. Метод K-средних: Заранее выбираем K – число кластеров. Выбираем произвольные K точек в пространстве признаков – начальные центры кластеров. На каждом шаге Приписываем каждый объект из выборки к тому кластеру, чей центр ближе всего к объекту. Пересчитываем цетры кластеров как среднее всех объектов, принадлежащих кластеру. Повторяем шаги пока центры кластеров не стабилизируются. 49

Распознавание образов Метод K-средних 50

Спасибо за внимание 51