12991

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

Лекция

Информатика, кибернетика и программирование

Лекция 11: Системы машинного зрения Введение Основные принципы или целостность восприятия Распознавание символов Шаблонные системы Структурные системы Признаковые системы Структурнопятенный эталон Уроки машинного чтения от Cognitive Technologies Распо

Русский

2013-05-07

30.22 KB

4 чел.

Лекция 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, и технологии, используемые при реализации крупных проектов, продолжают линию компании, направленную на расширение применения систем ввода информации и разработку технологий автоматизации работы с документами.


 

А также другие работы, которые могут Вас заинтересовать

40794. Методы определения коэффициента облученности 1.08 MB
  Методы определения коэффициента облученности При расчете потоков результирующего излучения необходимо располагать данными о коэффициентах облученности. Используя свойства замыкаемости потоков излучения 1471 можно записать . Вычитая из 14122 почленно 1411914121 найдем соотношение для определения взаимных поверхностей излучения 14123 14124 14125 Анализируя 1412314125 сформулируем такое правило: В замкнутой системе состоящей из трех невогнутых тел средняя взаимная...
40795. Явление резонанса. Частотные характеристики 65.71 KB
  Частотные характеристики Резонансом называется такой режим работы цепи включающей в себя индуктивные и емкостные элементы при котором ее входное сопротивление входная проводимость вещественно. Следствием этого является совпадение по фазе тока на входе цепи с входным напряжением. Резонанс в цепи с последовательно соединенными элементамирезонанс напряжений Для цепи на рис. В цепи преобладает индуктивность т.
40796. Характеристическое сопротивление и коэффициент распространения симметричного четырехполюсника 96.65 KB
  Для записи уравнений четырехполюсника выделим в произвольной схеме ветвь с единственным источником энергии и любую другую ветвь с некоторым сопротивлением см. Учитывая что в соответствии с принципом взаимности видно что коэффициенты четырехполюсника связаны между собой соотношением Уравнения 3 и 4 представляют собой основные уравнения четырехполюсника;...
40797. Электрические фильтры 65.69 KB
  Качество фильтра считается тем выше чем ярче выражены его фильтрующие свойства т. Классификация фильтров Название фильтра Диапазон пропускаемых частот Низкочастотный фильтр фильтр нижних частот Высокочастотный фильтр фильтр верхних частот Полосовой фильтр полоснопропускающий фильтр Режекторный фильтр полоснозадерживающий фильтр и где В соответствии с материалом изложенным в предыдущей лекции если фильтр имеет нагрузку сопротивление которой при всех частотах равно характеристическому то напряжения и соответственно токи на...
40798. Линейные электрические цепи при несинусоидальных периодических токах 64.74 KB
  Линейные электрические цепи при несинусоидальных периодических токах. Причины возникновения несинусоидальных напряжений и токов могут быть обусловлены или несинусоидальностью источника питания или и наличием в цепи хотя бы одного нелинейного элемента. Кроме того в основе появления несинусоидальных токов могут лежать элементы с периодически изменяющимися параметрами. Характеристики несинусоидальных величин Для характеристики несинусоидальных периодических переменных служат следующие величины и коэффициенты приведены на примере...
40799. Переходные процессы в линейных электрических цепях с сосредоточенными параметрами 66.4 KB
  Для цепей с заданными постоянными или периодическими напряжениями токами источников принужденная составляющая определяется путем расчета стационарного режима работы схемы после коммутации любым из рассмотренных ранее методов расчета линейных электрических цепей. общее решение уравнения 2 имеет вид 4 Соотношение 4 показывает что при классическом методе расчета послекоммутационный процесс рассматривается как наложение друг на друга двух режимов – принужденного наступающего как бы сразу после коммутации и свободного имеющего...
40800. Способы составления характеристического уравнения 81.02 KB
  Характеристическое уравнение составляется для цепи после коммутации. путем исключения из системы уравнений описывающих электромагнитное состояние цепи на основании первого и второго законов Кирхгофа всех неизвестных величин кроме одной относительно которой и записывается уравнение 2; путем использования выражения для входного сопротивления цепи на синусоидальном токе; на основе выражения главного определителя. Согласно первому способу в предыдущей лекции было получено дифференциальное уравнение относительно напряжения на...
40801. Переходные процессы в цепи с одним накопителем энергии и произвольным числом резисторов 81.22 KB
  Переходные процессы в цепи с одним накопителем энергии и произвольным числом резисторов. Общий подход к расчету переходных процессов в таких цепях основан на применении теоремы об активном двухполюснике: ветвь содержащую накопитель выделяют из цепи а оставшуюся часть схемы рассматривают как активный двухполюсник А эквивалентный генератор см. Совершенно очевидно что постоянная времени здесь для цепей с индуктивным элементом определяется как: и с емкостным как: где входное сопротивление цепи по отношению к зажимам 12 подключения...
40802. Расчет переходных процессов с использованием интеграла Дюамеля 64.54 KB
  Метод переменных состояния Уравнения элекромагнитного состояния – это система уравнений определяющих режим работы состояние электрической цепи. Метод переменных состояния основывается на упорядоченном составлении и решении системы дифференциальных уравнений первого порядка которые разрешены относительно производных т. Количество переменных состояния а следовательно число уравнений состояния равно числу независимых накопителей энергии. К уравнениям состояния выдвигаются два основных требования: независимость уравнений; возможность...