Системы машинного зрения

Курс лекций по дисциплине "Системы искусственного интеллекта"

Лекция 11: Системы машинного зрения

Введение

Основные принципы или целостность восприятия

Распознавание символов

Шаблонные системы

Структурные системы

Признаковые системы

Структурно-пятенный эталон

Уроки машинного чтения от Cognitive Technologies

Распознавание рукописных текстов

Резюме

Введение

О существовании специальных систем, которые "автоматически вводят в компьютер текст", знают даже начинающие пользователи. Со стороны все выглядит довольно просто и логично. На отсканированном изображении система находит фрагменты, в которых "узнает" буквы, а затем заменяет эти изображения настоящими буквами, или, по-другому, их машинными кодами. Так осуществляется переход от изображения текста к "настоящему" тексту, с которым можно работать в текстовом редакторе. Как этого добиться?

Компанией "Бит" была разработана специальная технология распознавания символов, которая получила название "Фонтанного преобразования" , а на ее основе - коммерческий продукт, получивший высокую оценку. Это система оптического распознавания Fine Reader. Сегодня на рынке представлена уже третья версия продукта, которая работает не только с текстом, но и с формами, таблицами, а разработчики уже колдуют над новой четвертой версией Fine Reader, которая будет распознавать не только печатный но и рукописный текст.

Основные принципы или целостность восприятия

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

Для выделения целого требуется определить его части. Части же, в свою очередь, можно рассматривать только в составе целого. Поэтому целостный процесс восприятия может происходить только в рамках гипотезы о воспринимаемом объекте - целом. После того как выдвинуто предположение о воспринимаемом объекте, выделяются и интерпретируются его части. Затем предпринимается попытка "собрать" из них целое, чтобы проверить правильность исходной гипотезы. Разумеется, воспринимаемый объект может интерпретироваться в рамках более крупного целого.

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

В технических системах любое решение при распознавании текста принимается неоднозначно, а путем последовательного выдвижения и проверки гипотез и привлечения как знаний о самом исследуемом объекте, так и общего контекста. Целостное описание класса объектов восприятия отвечает двум условиям: во - первых, все объекты данного класса удовлетворяют этому описанию, а во- вторых, ни один объект другого класса не удовлетворяют ему. Например, класс изображений буквы "К" должен быть описан так, чтобы любое изображение буквы "К" в него попадало, а изображение всех других букв - нет. Такое описание обладает свойством отображаемости, то есть обеспечивает воспроизведение описываемых объектов: эталон буквы для системы OCR позволяет визуально воспроизвести букву, эталон слова для распознавания речи позволяет произнести слово, а описание структуры предложения в синтаксическом анализаторе позволяет синтезировать правильное предложение. С практической точки зрения отображаемость играет огромную роль, поскольку позволяет эффективно контролировать качество описаний.

Существует два вида целостного описания: шаблонное и структурное.

В первом случае описание представляет собой изображение в растровом или векторном представлении, и задан класс преобразований (например, повтор, масштабирование и пр.).

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

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

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

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

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

Ныне одним из лидеров в области генетического программирования является группа исследователей из Стэндфордского университета (Stanford University), работающая под руководством профессора Джона Коза. Генетическое программирование вдохнуло новую жизнь в хорошенько уже подзабытый язык LISP (List Processing), который создавался группой Джона Маккарти (того самого, кто в 60-е годы ввел в наш обиход термин "искусственный интеллект") как раз для обработки списков и функционального программирования. Кстати, именно этот язык в США был и остается одним из наиболее распространенных языков программирования для задач искусственного интеллекта.

Распознавание символов

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

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

Шаблонные системы

Такие системы преобразуют изображение отдельного символа в растровое, сравнивают его со всеми шаблонами, имеющимися в базе и выбирают шаблон с наименьшим количеством точек, отличных от входного изображения. Шаблонные системы довольно устойчивы к дефектам изображения и имеют высокую скорость обработки входных донных, но надежно распознают только те шрифты, шаблоны которых им "известны". И если распознаваемый шрифт хоть немного отличается от эталонного, шаблонные системы могут делать ошибки даже при обработке очень качественных изображений!

Структурные системы

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

К недостаткам структурных систем следует отнести их высокую чувствительность к дефектам изображения, нарушающим составляющие элементы. Также векторизация может добавить дополнительные дефекты. Кроме того, для этих систем, в отличие от шаблонных и признаковых, до сих пор не созданы эффективные автоматизированные процедуры обучения. Поэтому для Fine Reader структурные описания пришлось создать в ручную.

Признаковые системы

В них усредненное изображение каждого символа представляется как объект в n-мерном пространстве признаков. Здесь выбирается алфавит признаков, значения которых вычисляются при распознавании входного изображения. Полученный n-мерный вектор сравнивается с эталонными, и изображение относится к наиболее подходящему из них. Признаковые системы не отвечают принципу целостности. Необходимое, но недостаточное условие целостности описания класса объектов (в нашем случае это класс изображений, представляющих один символ)состоит в том, что описанию должны удовлетворять все объекты данного класса и ни один из объектов других классов. Но по-скольку при вычислении признаков теряется существенная часть информации, трудно гарантировать, что к данному классу удастся отнести только <родные> объекты.

Структурно-пятенный эталон

Фонтанное преобразование совмещает в себе достоинства шаблонной и структурной систем и, по нашему мнению, позволяет избежать недостатков, присущих каждой из них по отдельности. В основе этой технологии лежит использование структурно-пятенного эталона. Он позволяет представить изображения в виде набора пятен, связанных между собой n-арными отношениями, задающими структуру символа. Эти отношения (то есть расположение пятен друг относительно друга) образуют структурные элементы, составляющие символ. Так, например, отрезок - это один тип n-арных отношений между пятнами, эллипс -другой, дуга - третий. Другие отношения задают пространственное расположение образующих символ элементов.

В эталоне задаются:

- имя;

- обязательные, запрещающие и необязательные структурные элементы;

- отношения между структурными элементами;

- отношения, связывающие структурные элементы с описывающим прямоугольником символа;

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

- атрибуты, используемые для проверки отношений между элементами;

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

- позиция, с которой начинается выделение элемента (отношения локализации элементов).

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

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

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

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

<Конкретизирующие параметры используются также для вычисления <качества> конкретного структурного элемента изображения и <качества> выполнения данного отношения./DT>

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

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

<Распознавание с использованием структурно-пятенного эталона происходит следующим образом. Эталон накладывается на изображение, и отношения между выделенными на изображении пятнами сравниваются с отношениями пятен в эталоне. Если выделенные на изо-бражении пятна и отношения между ними удовлетворяют эталону некоторого символа, то данный символ добавляется в список гипотез о результате распознавания входного изображения./DT> Уроки машинного чтения от Cognitive Technologies

Работает система по принципу <одной кнопки>. Это означает, что при нажатии кнопки <Сканируй и Рас-познавай> запускается весь про-цесс обработки документа: скани-рование, фрагментация страницы на текстовые и графические блоки, рас-познавание текста, проверка орфо-графии и формирование выходного файла. Но что за всем этим стоит? Интеллектуальный алгоритм по-зволяет автоматически подобрать оптимальный уровень яркости ска-нера (адаптивное сканирование) в зависимости от фона документа, со-хранить иллюстрации (или, в зави-симости от решаемой задачи, уда-лить ненужные графические элементы для максимального сокращения последующего редактирования).

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

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

В CuneiForm'96 мы впервые применили алгоритмы самообучения (или адаптивного распознавания). Принцип их работы состоит в следующем. В каждом тексте присутствуют чет-ко и нечетко пропечатанные симво-лы. Если после того как система распознала текст (как это делает обычная система, например пре-дыдущая версия OCR CuneiForm 2.95), выясняется, что точность ока-залась ниже пороговой, произво-дится дораспознавание текста на основе шрифта, который генерируется системой по хорошо пропеча-танным символам. Здесь разработ-чики соединили достоинства двух типов систем распознавания: омни-и мультишрифтовые. Напомним, что первые позволяют распознавать любые шрифты без дополнитель-ного обучения, вторые же более устойчивы при распознавании низ-кокачественных текстов. Результаты применения Cunei-Form'96 показали, что использова-ние самообучающихся алгоритмов позволяет поднять точность распо-знавания низкокачественных текстов в четыре-пять раз! Но главное, по-жалуй, в том, что самообучающие-ся системы обладают гораздо боль-шим потенциалом повышения точности распознавания.

Важную роль играют методы словарного и синтаксического распознавания и, по сути, служат мощным средством поддержки геометрического распознавания. Но для их эффективного использования необходимо было решить две важные задачи. Во-первых, реализовать быстрый доступ к большому (порядка 100000 слов) словарю. В результате удалось построить систему хранения слов, где на хранение каждого слова уходило не более одного байта, а доступ осуществлялся за минимальное время. С другой стороны, потребовалось построить систему коррекции результатов распознавания, ориентированную на альтернативность событий (подобно системе проверки орфографии). Сама по себе альтернативность результатов распознавания очевидна и обусловлена хранением коллекций букв вместе с <оценками соответствия>. А словарный контроль позволял изменять эти оценки, используя словарную базу. В итоге применение словаря позволило реализовать схему дораспознавания символов.

Сегодня наряду с задачами повышения точности распознавания на передний план выходят вопросы расширения сфер применения OCR-технологий, соединения технологий распознавания с архивными системами. Иными словами, мы переходим от монопрограммы, выполняющей функции ввода текста, к автоматизированным комплексам, решающим задачи клиента в области документооборота. Вот уже около полугода CuneiForm поставляется в комплекте с сервером распознавания CuneiForm OCR Server, предназначенным для коллективного ввода данных в организациях, а электронный архив <Евфрат>, включающий модуль распознавания, за короткое время приобрел большую популярность.

С таким прицелом создавался и комплект CuneiForm'96i Professional, существенно изменивший представления о системах распознавания в целом.

Распознавание рукописных текстов

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

И все же сегодня мы можем признать, что основные этапы разработки технологии распознавания рукописных (отдельные символы, написанные от руки) символов уже пройдены. В арсенале Cognitive Technologies имеются технологии распознавания всех основных типов текстов: стилизованных цифр, печатных символов и <рукопечатных> символов. Но технологии ввода <рукопечатных> символов потребуется еще пройти стадию адаптации, после чего можно будет заявить, что инструментарий для потокового ввода документов в архивы действительно реализован полностью.

Резюме

Динамичное развитие новых ком-пьютерных технологий (сетевые технологии, технологии <клиент-сервер>, и т. д.) нашли свое отра-жение и в состоянии сектора элек-тронного документооборота. Если раньше в продвижении технологий бесклавиатурного ввода делался упор на преимущества их персо-нального использования, то сего-дня на первый план выходят пре-имущества коллективного и рацио-нального использования техноло-гий ввода и обработки документов. Иметь одну, обособленную систе-му распознавания сегодня уже яв-но недостаточно. С распознанны-ми текстовыми файлами (как бы хорошо они распознаны ни были) нужно что-то делать: хранить в ба-зе данных, осуществлять их поиск, передавать по локальной сети, и т. д. Словом, требуется взаимо-действие с архивной или иной сис-темой работы с документами. Та-ким образом, система распозна-вания превращается в утилиту для архивных и иных систем работы с документами.

С появлением сетевых версий систем сканирования (режим потокового сканирования OCR CuneiForm) и распознавания (сервер распознавания CuneiForm OCR Server) документов нашей компании уже удалось реализовать некоторые преимущества коллективного использования таких технологий в организациях разного масштаба. По этой причине, с нашей точки зрения, актуальным был бы разговор о комплексном решении компаниями проблемы автоматизации работы с документами в организациях самого различного ранга. Что касается Cognitive Technologies, то представляемый ею электронный архив <Евфрат> (система включает в себя возможность ввода документов с помощью OCR CuneiForm), новые утилиты, встроенные в OCR CuneiForm'96, и технологии, используемые при реализации крупных проектов, продолжают линию компании, направленную на расширение применения систем ввода информации и разработку технологий автоматизации работы с документами.

Вернуться к списку лекций