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

Разбить на страницы

Показывать лекцию целиком

Современные роботы, снабженные телевизионными камерами, способны достаточно хорошо видеть, чтобы работать с реальным миром. Они могут делать заключения о том, какого типа объекты присутствуют, в каких они находятся отношениях между собой, какие группы образуют, какой текст содержат и т. д. Однако сложные задачи распознавания, например, распознавание похожих трехмерных быстродвижущихся объектов или неразборчивого рукописного текста требуют совершенствования методов и средств для своего решения. В этой лекции мы рассмотрим основы некоторых традиционных методов распознавания. Наше рассмотрение мы начнем с наиболее часто применяемого признакового метода распознавания , .

Общая характеристика задач распознавания образов и их типы.

Под образом понимается структурированное описание изучаемого объекта или явления, представленное вектором признаков, каждый элемент которого представляет числовое значение одного из признаков, характеризующих соответствующий объект. Общая структура системы распознавания и этапы в процессе ее разработки показаны на рис 4.1.(рис 4.1) Структура системы распознавания

Суть задачи распознавания - установить, обладают ли изучаемые объекты фиксированным конечным набором признаков, позволяющим отнести их к определенному классу.

Задачи распознавания имеют следующие характерные черты.

Это информационные задачи, состоящие из двух этапов: а) приведение исходных данных к виду, удобному для распознавания ; б) собственно распознавание (указание принадлежности объекта определенному классу).

В этих задачах можно вводить понятие аналогии или подобия объектов и формулировать понятие близости объектов в качестве основания для зачисления объектов в один и тот же класс или разные классы.

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

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

В этих задачах возможна "плохая" информация (информация с пропусками, разнородная, косвенная, нечеткая, неоднозначная, вероятностная).

Целесообразно выделить следующие типы задач распознавания.

Задача распознавания - отнесение предъявленного объекта по его описанию к одному из заданных классов (обучение с учителем).

Задача автоматической классификации - разбиение множества объектов (ситуаций) по их описаниям на систему непересекающихся классов (таксономия, кластерный анализ, обучение без учителя).

Задача выбора информативного набора признаков при распознавании.

Задача приведения исходных данных к виду, удобному для распознавания.

Динамическое распознавание и динамическая классификация - задачи 1 и 2 для динамических объектов.

Задача прогнозирования - это задачи 5, в которых решение должно относиться к некоторому моменту в будущем.

Основы теории анализа и распознавания изображений.

Пусть дано множество ; на этом множестве существует разбиение на конечное число подмножеств (классов) $$\Omega,$$ i = {1,m}, $$M = \cup \Omega _{i} (i = 1..m).$$ Объекты $$\omega$$ задаются значениями некоторых признаков x_j, j= {1,N}. Описание объекта $$I(\omega )=(x_{1}(\omega ), \dots , x_{N}(\omega ))$$ называют стандартным, если $$x_{j}(\omega )$$ принимает значение из множества допустимых значений.

Пусть задана таблица обучения (таблица 4.1). Задача распознавания состоит в том, чтобы для заданного объекта $$\omega$$ и набора классов $$\Omega _{1}$$, ..., $$\Omega _{m}$$ по обучающей информации в таблице обучения $$I_{0}(\Omega _{1}\dots \Omega _{m})$$ о классах и описанию $$I(\omega )$$ вычислить предикаты:

$$P_{i}(\omega \in \Omega _{i})=\{ 1(\omega \in \Omega _{i}), 0(\omega \in \Omega _{i}), (\omega \in \Omega _{i})\} ,$$

где i= {1,m}, $$\Delta$$ - неизвестно.

Таблица обучения
Объект	Признаки и их значения			Класс
Объект	`x₁`	`x_j`	`x_n`	Класс
$$_{\omega 1}$$	$$\alpha _{11}$$	$$\alpha _{1j}$$	$$\alpha _{1n}$$	$$\Omega _{1}$$
...
$$\omega _{r_1}$$	`_r11`	$$\alpha _{r_1j}$$	$$\alpha _{r_1n}$$
...
$$\omega _{r_k}$$	$$\alpha _{r_k 1}$$	$$\alpha _{r_k j}$$	$$\alpha _{r_k n}$$	$$\Omega _{m}$$
...
$$\omega _{r_m}$$	$$\alpha _{r_m 1}$$	$$\alpha _{r_m j}$$	$$\alpha _{r_m n}$$

Рассмотрим алгоритмы распознавания, основанные на вычислении оценок. В их основе лежит принцип прецедентности (в аналогичных ситуациях следует действовать аналогично).

Пусть задан полный набор признаков x₁, ..., x_N. Выделим систему подмножеств множества признаков S₁, ..., S_k. Удалим произвольный набор признаков из строк $$\omega _{1}$$, $$\omega _{2}$$, ..., $$\omega _{rm}$$ и обозначим полученные строки через $$S\omega _{1}$$, $$S\omega _{2}$$, ..., $$S\omega _{rm}$$, $$S\omega '$$.

Правило близости, позволяющее оценить похожесть строк $$S\omega '$$ и $$S\omega _{r}$$ состоит в следующем. Пусть "усеченные" строки содержат q первых символов, то есть $$S\omega _{r}=(a_{1}, \dots , a_{q})$$ и $$S\omega '=(b_{1}, \dots , b_{q}).$$ Заданы пороги $$\varepsilon _{1}$$... $$\varepsilon _{q}$$, $$\delta.$$ Строки $$S\omega _{r}$$ и $$S\omega '$$ считаются похожими, если выполняется не менее чем $$\delta$$ неравенств вида

$$|a_{j}-b_{j}| \le \varepsilon _{j}, j=1,2,\dots , q.$$

Величины $$\varepsilon _{1}$$... $$\varepsilon _{q}$$, $$\delta$$ входят в качестве параметров в модель класса алгоритмов на основе оценок.

Пусть $$Г_{i}(\omega ')$$ - оценка объекта $$\omega '$$ по классу $$\Omega _{i}$$.

Описания объектов $$\{ \omega '\}$$, предъявленные для распознавания, переводятся в числовую матрицу оценок. Решение о том, к какому классу отнести объект, выносится на основе вычисления степени сходства распознавания объекта (строки) со строками, принадлежность которых к заданным классам известна.

Проиллюстрируем описанный алгоритм распознавания на примере. Задано 10 классов объектов (рис. 4.2а). Требуется определить признаки таблицы обучения, пороги и построить оценки близости для классов объектов, показанных на рис. 4.2б. Предлагаются следующие признаки таблицы обучения:

x₁ - количество вертикальных линий минимального размера;

x₂ - количество горизонтальных линий;

x₃ - количество наклонных линий;

x₄ - количество горизонтальных линий снизу объекта.

(рис 4.2) Пример задачи по распознаванию

На рис 4.3 приведена таблица обучения и пороги

$$\varepsilon _{1}=1, \varepsilon _{2}=1, \varepsilon _{3}=1, \varepsilon _{4}=1, \delta =1.$$

Из этой таблицы видно, что неразличимость символов 6 и 9 привела к необходимости ввода еще одного признака x₄.

(рис 4.3) Таблица обучения для задачи по распознаванию

Теперь может быть построена таблица распознавания для объектов на рис. 4.2б.

Объект	`x₁`	`x₂`	`x₃`	`x₄`	Результат распознавания
Объект 1	`1`	`2`	`1`		Цифра 2
Объект 2	`3`	`3`	`0`	`1`	Цифра 8 или 5
Объект 3	`4`	`1`	`0`
Объект 4	`4`	`2`	`0`	`1`

Читателю предлагается самостоятельно ответить на вопрос: что будет, если увеличить пороги $$\varepsilon _{1}$$, $$\varepsilon _{2}$$, $$\varepsilon _{3}$$, $$\varepsilon _{4}$$, $$\delta?$$ Как изменится качество распознавания в данной задаче?

Заключая данный раздел лекции, отметим важную мысль, высказанную А. Шамисом в работе : качество распознавания во многом зависит от того, насколько удачно создан алфавит признаков, придуманный разработчиками системы. Поэтому признаки должны быть инвариантны к ориентации, размеру и вариациям формы объектов.

Распознавание по методу аналогий.

Этот метод очень хорошо знаком студентам (знание решения аналогичной задачи помогает в решении текущей задачи).

Рассмотрим этот метод на примере задачи П. Уинстона по поиску геометрических аналогий, представленном на рис 4.4. Среди фигур второго ряда требуется выбрать $$X \in \{ 1, 2, 3, 4, 5\}$$ такое, что A так соотносится с B, как C соотносится с X, и такое, которое лучше всего при этом подходит. Для решения задачи необходимо понять, в чем разница между фигурами A и B (наличие/отсутствие жирной точки), и после этого ясно, что лучше всего для C подходит X=3.

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

(рис 4.4) Задача поиска геометрических аналогий

В качестве примера запишем три правила, показывающие, каким образом одно изображение (исходное) становится результирующим (рис 4.5).

Правило 1 (исходное изображение): k выше m, k выше n, n внутри m

Правило 2 (результир. изображение): n слева m

Правило 3 (масшабирование, повороты):

k исчезло

m изменение масштаба 1:1, вращение 0⁰

n изменение масштаба 1:2, вращение 0⁰

(рис 4.5) Правила преобразования

Отметим важные моменты при таких преобразованиях. В исходном и результирующем изображениях допускаются отношения ВЫШЕ, ВНУТРИ, СЛЕВА, В результате преобразования изображение может стать МЕНЬШЕ, БОЛЬШЕ, испытать ПОВОРОТ или ВРАЩЕНИЕ, ОТРАЖЕНИЕ, УДАЛЕНИЕ, ДОБАВЛЕНИЕ. Написание правил лучше всего начинать с проведения диагональных линий через центры фигур. Лишние отношения (СПРАВА ОТ и СЛЕВА ОТ, ВЫШЕ и НИЖЕ, ИЗНУТРИ и СНАРУЖИ,) использовать не рекомендуется.

Теперь задачи распознавания мы можем решать достаточно просто, записав для отношений правила 1, 2, 3 и проведя сопоставление, например так, как это сделано для следующей задачи: найти X такое, что ).

(рис 4.6) Пример задачи распознавания по аналогии

	Правило 1	Правило 2	Правило 3	Результат
`A => B`	`k` выше `m`	`k` слева `m`	`k`, `m` масштаб 1:1 поворот 0⁰
`C => 1`	`x` выше `y`	`y` выше `x`	`x`, `y` масштаб 1:1 поворот 0⁰
`C => 2`	`x` выше `y`	`y` слева `x`	`x`, `y` масштаб 1:1 поворот 0⁰
`C => 3`	`x` выше `y`	`x` слева `y`	`x`, `y` масштаб 1:1 поворот 0⁰	Сопоставление успешно

Дополнительно следует отметить, что разные виды преобразований могут иметь различные веса, например, исчезновению фигуры целесообразно назначить больший вес, чем преобразованию масштаба; а вращение фигуры может иметь меньший вес, чем отражение. С этими особенностями можно будет познакомиться в упражнениях к данной лекции.

Методы распознавания по аналогии могут быть эффективнее, если используется обучение. Различают обучение с учителем, обучение по образцу (эталону) и др. виды обучения , . Суть идеи такова. Программе распознавания предъявляется объект, например, арка. Программа создает внутреннюю модель:

(арка       
 (компонент1 (назначение (опора))    
      (тип (брусок)))
 (компонент2 (назначение (опора))   
      (тип (брусок)))
   (компонент3 (назначение (перекладина))   
      (тип (брусок))
      (поддерживается (компонент1), (компонент2)))

После этого предъявляется другой объект и говорится, что это тоже арка. Программа вынуждена дополнить свою внутреннюю модель:

(арка       
   (компонент1 (назначение (опора))    
  (тип (брусок)))
   (компонент2 (назначение (опора))    
  (тип (брусок)))
   (компонент3 (назначение (перекладина))    
      (тип (брусок)   или (клин) )
      (поддерживается (компонент1), (компонент2)))

После такого обучения система распознавания будет узнавать в качестве арки как первый, так и второй объект.

Актуальные задачи распознавания.

Среди множества интересных задач по распознаванию (распознавание отпечатков пальцев, распознавание по радужной оболочке глаза, распознавание машиностроительных чертежей и т. д.) следует выделить задачу определения реальных координат заготовки и определения шероховатости обрабатываемой поверхности, рассмотренную в лекции 10. Другой актуальной задачей является распознавание машинописных и рукописных текстов в силу ее повседневной необходимости. Практическое значение задачи машинного чтения печатных и рукописных текстов определяется необходимостью представления, хранения и использования в электронном виде огромного количества накопленной и вновь создающейся текстовой информации. Кроме того, большое значение имеет оперативный ввод в информационные и управляющие системы информации с машиночитаемых бланков, содержащих как напечатанные, так и рукописные тексты. В связи с этим рассмотрим принципы и подход к распознаванию в задаче машинного чтения печатных и рукописных текстов, описанные в работе .

Для решения данной задачи используются следующие основные принципы.

Принцип целостности - распознаваемый объект рассматривается как единое целое, состоящее из структурных частей, связанных между собой пространственными отношениями.

Принцип двунаправленности - создание модели ведется от изображения к модели и от модели к изображению.

Принцип предвидения заключается в формировании гипотезы о содержании изображения. Гипотеза возникает при взаимодействии процесса "сверху-вниз", разворачивающегося на основе модели среды, модели текущей ситуации и текущего результата восприятия, и процесса "снизу-вверх", основанного на непосредственном грубом признаковом восприятии.

Принцип целенаправленности, включающий сегментацию изображения и совместную интерпретацию его частей.

Принцип "не навреди" - ничего не делать до распознавания и вне распознавания, то есть без "понимания".

Принцип максимального использования модели проблемной среды.

Указанные принципы реализованы в пакете программ "Графит" , в программах FineReader-рукопись и FormReader - для распознавания рукописных символов и, частично, в программе FineReader для распознавания печатных текстов . Входящая в FormReader программа чтения рукописных текстов была выпущена в 1998 году одновременно с системой ABBYY FineReader 4.0. Эта программа может читать все рукописные строчные и заглавные символы, допускает ограниченные соприкосновения символов между собой и с графическими линиями и обеспечивает поддержку 10 языков. Основное применение программы - распознавание и ввод информации с машиночитаемых бланков.

В системе ABBYY FormReader при распознавании рукописных текстов используются структурный, растровый, признаковый, дифференциальный и лингвистический уровни распознавания. Для более подробного освоения подходов к распознаванию машинописных и рукописных текстов в системе ABBYY FormReader читателю рекомендуется непосредственно ознакомиться с работой А. Шамиса , при этом знание основ машинной графики на уровне подразумевается.

С другими работами по распознаванию читатель может познакомиться в литературе , .

Завершая этот раздел лекции, отметим особенности задачи зрительного восприятия роботов по сравнению с традиционными задачами распознавания образов и машинной обработки изображений :

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

необходимость анализа трехмерных сцен не только в плане анализа трехмерных объектов по их плоским проекциям, но и в плане определения объемных пространственных отношений;

необходимость анализа изображений, включающих одновременно несколько произвольно расположенных объектов (в общем случае произвольной формы) в отличие от традиционной задачи, когда для распознавания предъявляется, как правило, один объект;

необходимость анализировать реальную динамическую среду, а не статические изображения;

отсутствие постоянной фиксированной задачи и необходимость оперативно решать возникающие по ходу дела задачи;

необходимость следить за изменениями в среде, которые могут порождать новые оперативные задачи;

необходимость организации системного процесса взаимодействия в реальном времени нескольких подсистем робота ("глаз-мозг", "глаз-мозг-рука").

В заключение лекции следует отметить, что методов распознавания много, они опубликованы (см. список литературы к данной лекции). Успеха в создании серьезных программных продуктов по распознаванию и решению задач зрительного восприятия роботов добьются коллективы, упорно и кропотливо создающие и оттачивающие свои инструментальные средства для реальных задач распознавания изображений.

Страницы: