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

На правах рукописи

Поцепаев Роман Валерьевич

ВОССТАНОВЛЕНИЕ ТРАЕКТОРИИ ДВИЖЕНИЯ ПЕРА ПО ИЗОБРАЖЕНИЮ СИМВОЛА ДЛЯ РАСПОЗНАВАНИЯ РУКОПИСНОГО ТЕКСТА

Специальность 05.13.18 - Математическое моделирование, численные методы и комплексы программ.

АВТОРЕФЕРАТ диссертации на соискание учёной степени кандидата физико-математических наук

Москва - 2004

Работа выполнена на кафедре информатики Московского физико-технического института (государственного университета)

Научный руководитель:

доктор физико-математических наук,

профессор

Петров

Игорь Борисович

Научный консультант:

кандидат физико-математических наук,

старший научный сотрудник

Савин

Анатолий Анатольевич

Официальные оппоненты: доктор физико-математических наук ведущий научный; сотрудник

Рязанов

Владимир Васильевич

кандидат физико-математических наук

Кадощук Игорь Тарасович

Ведущая организация

Институт Автоматизации Проектирования Российской академии наук

2004 г. в

/я час.

Защита состоится

на заседании диссертационного'совета К 212.156.02 при Московском физико-техническом институте по адресу Московская обл., г. Долгопрудный, Институтский пер., д.9

Автореферат разослан,«

Учёный секретарь диссертационного совета

2004 г.

Федько О.С.

Общая характеристика работы

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

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

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

Существ\ ют две различные постановки задачи распознавания символов, различие которых связано со способом получения изображения. Изображение символа может быть получено при сканировании документа, содержащего рукописный текст. В этом случае входными данными для задачи распознавания являются матрицы точек, соответствующие изображениям букв, и возникает задача «офф-лайн1» распознавания. Другой способ получения изображения - это использование специальных устройств, таких, как графический планшет. При этом изображение записывается в память компьютера в процессе написания символов; входными данными для задачи являются траектории движения пера, представляющие собой последовательности координат пера. Такая 'задача называется задачей «он-лайн» распознавания. В работе рассматривается задача «офф-лайн» распознавания.

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

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

' Термины «офф-ястн» и «ок-таин» распознавание заимствованы из англоязычной литературы которые в оригинале заучат как off-line handwritten recognition и on-line handwritten recognition

контура и тем более бинарные матрицы. Этот факт накладывает ограничение на использование вышеуказанного подхода к распознаванию произвольных рукописных символов.

В то же время, анализ существующих технологий свидетельствует о следующем факте: на сегодняшний день точность «он-лайн» методов выше точности «офф-лайн» методов.

Восстановление траектории движения пера по бинарному изображению символа сделало бы возможным применение «он-лайн» методов к «офф-лайн» задаче.

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

Обзор и анализ опубликованных работ показывает, что до сих пор не создана технология восстановления траектории, способная восстановить траекторию написания символов с высокой точность и сделать возможным применение «он-лайн» алгоритмов к «офф-лайн» задаче.

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

скоростью восстановления и способностью выявлять изображения, для

которых восстановление траекторию невозможно.

Основные задачи исследования:

1. Анализ существующих методов и систем восстановления траектории пера;

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

3. Интегрирование высокоточных методов «он-лайн» распознавания с модулем восстановления траектории;

4. Создание программного комплекса, реализующего разработанную технологию и проведение экспериментов на тестовой базе изображений и траекторий рукописных символов.

Научная новизна работы заключается в следующем:

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

2. На основе разработанных алгоритмов построен блок предобработки изображений символов и блок восстановления траектории пера. Выполнены эксперименты по тестированию созданной системы на базе, состоящей из 10000 изображений.

3. Разработаны прототип системы распознавания символов, включающий блок восстановления динамической информации и блок «он-лайн» распознавания.

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

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

Основные результаты работы докладывались на научных конференциях МФТИ (Долгопрудный, 2002-2003 г.г.), на 11-й Всероссийской конференции «Математический методы распознавания образов» (ММРО-2003), на научных семинарах Института Автоматизации Проектирования РАН, Вычислительного Центра РАН, - кафедры информатики МФТИ, компаний Крок, Abbyy Software House, Istari Technologies LLC.

По теме диссертации опубликовано 7 печатных работ.

Диссертационная работа состоит из введения, шести глав и заключения.

Основное содержание работы

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

обзор этапов и существующих направлений распознавания рукописного текста.

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

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

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

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

Во второй главе собраны, кратко изложены и проанализированы более 15 работ различных авторов посвященные задаче восстановления движения пера.

В таблице представлены преимущества и недостатки всех рассмотренных подходов. Из таблицы следует вывод: большинство методов обладают низкой точностью восстановления траектории в

окрестности пересечения штрихов, что не позволяет использовать их при создании систем распознавания рукописных символов. Исключение составляют подход О'Ломера и подход Я. Като, М. Яшухара. Однако метод О'Ломера требует трудоемких вычислений для каждого пересечения штрихов, а метод Я. Като, М. Яшухара ограничен частным случаем отсутствия отрывов пера от бумаги. Кроме того, абсолютно все методы выдают приемлем!Де результаты для изображений созданных пишущим инструментом с большой толщиной штриха. Для эффективного внедрения технологии восстановления пера в системы распознавания сложных рукописных символов необходимо создание метода, обладающего высокой точностью и высокой скоростью восстановления всей траектории. Этой проблеме и посвящена настоящая диссертация.

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

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

Несмотря на большую эффективность использования «скелетизации» в других методах распознавания, восстановление траектории по скелету изображения имеет существенный недостаток: критически важной информацией при восстановлении траектории является форма граничного конура в окрестности областей пересечения штрихов. Из скелета изображения эта информация недоступна. Поэтому методы восстановления траектории, основанные на получении скелета, приводят к ошибкам при обработке изображений с достаточно сложной траекторией.

Авторы Что и как восстанавливается Преимущества Недостатки

Ооегшапп Вся траектория, Использование Низкая точность

О.Б., Rosenfeld регулярные регулярных восстановления

А области областей. узлов.

Boccignone G. Узлы, скелет Эффективная Низкая точность

и др. коррекция скелета. восстановления

узлов.

L'Homer Е. Узлы, регулярные Высокая точность Вычислительная

области восстановления трудоемкость.

узлов.

Использование

регулярных

областей.

Kato Y., Вся траектория. Восстановление Частный случай

Yasuhara М. скелет сложных траекторий.

траекторий без

отрыва пера.

Nishida Н. Вся траектория. Восстанавливается Низкая точность

скелет порядок штрихов. восстановления

узлов.

Рап .1.С., Ьее Б. Вся траектория. Восстанавливается Низкая точность

скелет порядок штрихов. восстановления

узлов.

La lican Р.М и Вся траектория. Восстанавливается Низкая точность

др скелет порядок штрихов. восста новления

узлов. NP-

полно- а

ал горитма.

S. Jaeger Вся траектория. Восстанавливаются Низкая точность

скелет траектории с восстановления

отрезками узлов.

многократного полнота

прохода пера. алгоритма.

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

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

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

регулярной области восстанавливается соответствующий ей отрезок траектории.

Основными особенностями предлагаемого метода предобработки являются:

• качество восстановления отрезков траектории, которое существенно выше, чем в алгоритмах скелетизации;

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

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

В четвертой главе излагаются алгоритмы восстановления траектории в окрестности узлов и восстановления разрывов траектории

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

Для подавляющего большинства символов достаточно ограничиться

рассмотрением случая, для которого

выполнено следующее

Условие 1 Перо проходит по одному отрезку траектории не более двух раз

Регулярную область, по траектории которой перо прошло два раза назовем йуппвтох1.

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

Рис. 2. Изображение на каждом этапе обработки а) начальное изображение, б) набор регулярных областей и узел, в) восстановлен!! 1я траектория

двух, что следует из условия 1. Например, правильным решением для узла

на рисунке 2 будет матрица: Су =

Для нахождения правильной конфигурации используется байесовское решающее правило. Если узел X имеет конфигурацию С, то математическое ожидание потерь связанное с выбором неверной конфигурации есть r(-(.V)= Х)ЦС,С),, где р{С\Х) - апостериорная

вероятность конфигурации С"; ЦС.С) - стандартная функция потерь выбора конфигурации С при верной конфигурации С.

В качестве решения выберем конфигурацию С* минимизирующую математическое ожидание общих потерь: (f) = argminrefA") = arg max р(С\Х)

' ' I ml. l et.

Согласно формуле Байеса выражение (1) можно представить в следующем виде:

С' = arg max ^ ^(C^.^argmaxln(X|C) + ln р{С)~ const , (2)

где - функция правдоподобия для конфигурации -

априорная вероятность возникновения конфигурации С; const = In £ р(Х I С)р(С).

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

Класс 3.1

Класс 3.2

Класс 33

\

1

V

Класс 3.4 ^у^*

РисЗ Всевозможные конфигурации для узла кратности /77=3. Конфигурации разбиты на классы эквивалентности

\ каждого класса

I

экспериментально определяется априорная вероятность р(С).

Величина РС^Ю

вычисляется на основе трех признаков, первые два признака к,,, определяются для каждой пары регулярных областей Ип Лу входящих в узел, третий признак й, определяется для каждой регулярной области/?,,г=\.лг.

Информацию об окрестности узла представим в виде ^ = с Учетом »,/61..«. Метод

восстановления штрихов в узле основывается на следующих предположениях: траектория и границы внутри узла имеют малую кривизну (признак к,); кривизна внутри узла примерно равна кривизне в

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

Рассмотрим признак к, более подробно. Возможную траекторию, соединяющую регулярные области внутри узла представим в виде

полинома третьей степени для которого выполнены следующие

условия (рис. 4):

Я,-®«. Л(0) = 0: Р3Щ = 0, Я3'(0)=Д,; ОД-Д,; (ЗУ

Значения коэффициентов полинома определяются единственным

(4)

Значение признака ку определяется как

11

кщ =-|(Р3"(/))2<й. В нашем

случае, значение интеграла может быть найдено аналитически:

^-р-^+лл+Ф; (5)

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

Для нахождения р(Х[С) < воспользуемся следующими предположениями. Будем считать, признаки кв,&к^ статистически коррелированны, но каждый из них не коррелирован с признаком т.е.

р(х\С)=4-«'.|&=Нкики1ЭД»'.|^ (6)

Рис. 4. Восстановление траектории в уме

Также, будем считать, что плотность распределения признаков Jt^.M, зависит только от факта, образует ли штрих пара R„ Rj, т.е. зависит только от значения с. Таким образом

rfWL-KL io-п к> (7)

Будем предполагать, что ширина штриха зависит только от того, является ли штрих дуплетом:

№.....dJC^n^Kb (8)

- дуплет, иначе

Окончательно, подставляя (7), (8) в (6) имеем

р{Х 10 = П Ры, 5 s,) n^t, .М„ | с,) (9)

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

распределения Оценка

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

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

В пятой главе излагается метод построения окончательного набора

траекторий по известным конфигурациям узлов и разрывам.

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

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

Пусть на изображении имеется р узлов. Выберем конфигурации узлов

С'.....С. Из формулы (2) следует, что вероятность возникновения

траектории равна

где Т- траектория, /- информация об изображении.

Очевидно, что принимает максимальное значение для

конфигураций, имеющих максимальную меру

На рисунке 5 представлены примеры работы алгоритма построения набора траекторий по известной набору который имеет

максимальную меру ¡\ТМ), Линией двойной толщины отмечены дуплеты, которые затем расщепляются на два отрезка траектории. Дуплеты делятся на две группы: первая группа - один конец дуплета соединен с двумя

регулярными ооластями, второй конец не соединен ни с одной из регулярных областей (рис. 5 а) б)/?ь г)/?(); вторая группа - каждый из двух концов соединены с двумя регулярными областями (рис. 5 в)/?|, г)./?2, д)/?|). Возможен иноке случаи, когда один конец дуплета соединен с двумя областями, др\гой - юлько с одной областью, в этом случае, эта область также объявляется дуплетом, возникает цепочка дуплетов, которая обрабатывается как единый дуплет (рис. 5 б) Т^). Дуплеты первой группы расщепляются однозначным образом, для1 дуплетов второй группы генерируется два варианта траектории (рис. 5 в), д)).

а)

а

д)

ЫЫс1с(с(

Рис. 5. Восстановление траектории по изображению

Шестая глава посвящена улучшению точности восстановления

траектории за счет использования информации об эталонах.

Пусть имеется набор эталонных траекторий написания символа М„ / = предназначенных для «он-лайн» распознавания траектории. В классической схеме «офф-лайн» распознавания символов с использованием восстановленного следа пера траектория Т единожды восстанавливается по изображению I. после чего сравнивается к каждым из

эталонов для выбора максимально схожего с ней . В этой схеме

информацией для построения траектории является только изображение. Рассмотрим альтернативный вариант, состоящий из следующих этапов:

• Восстановление траектории 7} по изображению 7 ив

• предположении о том, что символ написан по эталонуЛ/,;

• Сравнение построенной траектории 7} с эталоном М, с помощью блока «он-лайн» распознавания;

• Выбор максимально схожей пары Т' и М';

• Выбор кода символа, соответствующего эталону М' в качестве решения.

Информацией для построения траектории служит не только изображение, но также и эталон. В этом случае возникает задача восстановления траектории при априорно известном эталоне, т.е. вместо вероятности Р(Т\1) вычисляется Р(Т,\1.М,), где М, - известный эталон. Вместо формулы (10) возникает следующее равенство

Будем считать, что от M статистически зависимы только значения С, следовательно:

Априорные вероятности классов конфигураций р(С\М) входящие в и раннее вычисляемые по всей базе символов как могут быть существенно скорректированы для каждого отдельного узла. На всей базе символов по всем узлам соберем следующую статистику: кратность узла; класс узла; верный эталон, соответствующий изображению; координаты центра узла на изображении.

Для вычисляемой конфигхрации узла X значение Р'(С\Щ будем вычислять по всем известным узлам той же кратности, принадлежащим эталону М и расстояние от которых до центра X не превышает заданной константы Отп. Как и раньше, конфигурации, принадлежащие одному классу, имеют равные вероятности.

Иногда для рассматриваемого узла не удается собрать достаточную статистику, в этом случае будем считать либо выберем

среднее между

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

Метод проведения эксперимента и результаты восстановления траектории приведены в седьмой главе. Для исследований использовалась

база, состоящая из 10400 изображений рукописных символов - 400

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

В системе реализован полуавтоматический процесс создания верной траектории по изображению из базы. Полученная информация о траектории записывается и хранится вместе с базой изображений.

На этом этапе создания эталонов были выявлены изображения, для которых регулярные области построены некорректно, и, следовательно, для них не может быть построена верная траектория. Относительное количество этих изображений - 2.6%

В таблице 1 представлены результаты распознавания узлов, основанные на формулах (2), (10). Гипотезы о конфигурации упорядочены по убыванию апостериорной вероятности возникновения. В первой строке указан размер усеченного списка гипотез, во второй - доля попавших в этот список правильных конфигураций. Эксперимент проводился на всех узлах тестовой выборки базы символов. Отдельно приведены результаты для узлов кратностЛй 3 и 4. В скобках указано улучшение точности по сравнению с использованием формулы (11).

Получены данные восстановления траекторий по всем изображения тестовой выборки базы символов (таблица 2).

Таблица 1. Результат распознавания конфигураций узлов

Длина списка кандидатов Доля правильно распознанных конфигураций, % Доля правильно распознанных конфигураций кратности 3, %

Доля

правильно распознанных

конфигураций кратности 4. %

I

90.1 (4.5) 90 (4 9) 85.5 (0.9)

2 96.8 (1.7)

97.1 (1.3)

95.2 (3.9)

3 98.8

99.1

97.1

4 99.2

99.5

97.4

5

99.5 99.9 97.7

Таблица 2. Результат распознавания траекторий

Длина списка кандидатов 1 2 3 >10 ошибка

Доля 1 восстановленных 89.3 94.0 95.7 9 6.6 3.4

траекторий, %

Основные результаты работы

1. Разработан метод предобработки изображений, обладающий высокой скоростью по сравнению с существующими методами, а также способностью выявлять изображения, для которых восстановление траекторию невозможно.

2. Создана статистическая модель и алгоритм восстановления окрестностей узлов с высокой точностью (96.8%).

3. Предложен алгоритм поиска и восстановления случайных разрывов.

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

5. Создан метод построения всей траектории написания. Учитываются случаи, в которых перо проходит по одному отрезку траектории два раза.

6. Предложен метод автоматического сбора статистических данных из базы символов. необходимых для тестирования алгоритмов восстановления траектории.

7. Разработан программный модуль восстановления траектории и распознавания рукописных символов по полученной траектории с помощью блока «он-лайн» распознавания.

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

Список работ, опубликованных по теме диссертации:

1. Поцепаев Р. В. Распознавание рукописных символов на основе восстановления траектории движения пера // Сборник научных трудов "Обработка информации и моделирование" - М, 2002. - С. 90-97.

2. Поцепаев Р.В. Распознавание рукописных символов на основе восстановления траектории движения пера // Труды XLV научной конференции МФТИ(ГУ) «Современные проблемы фундаментальных и прикладных наук» - М.:МФТИ, 2002. - С. 48.

3. Поцепаев Р.В., Петров И.Б Эффективный алгоритм предобработки изображений для структурных методов распознавания рукописных символов // Электронный журнал "Исследовано в России" - 2003, №. 19, С. 181-190. http://zhumal.ape.relam.ru/artides/2003/019.pdf

4. Поцепаев Р. В. Восстановление траекторий написания символов по их изображениям // Электронный журнал "Исследовано в России" — 2003, №. 120, С 1437-1450, Imp ///hurnal ape relarn ru/aiiicles/2003/120.pdf

5. Поцепаев Р. В. Восстановление траектории написания в задаче распознавания рукописных символов // Организационное управление и искусственный интеллект. Труды ИСА РАН. - М., 2003. С. 427-445.

6. Поцепаев Р.В. Петров И Б Восстановление траекторий движения пера по изображениям символов // Доклады 11-й Всероссийской конференции «Математический методы распознавания образов» (ММРО-П).-М., 2003. - С. 412-415.

7. Поцепаев Р.В. Восстановление динамической информации о написании по статическому изображению символа // Труды XLVI научной конференции МФТИ(ГУ) «Современные проблемы фундаментальных и прикладных наук» - М.:МФТИ, 2003. -С. 55.

Поцепаев Роман Валерьевич

Восстановление траектории движения пера по изображению символа в проблеме распознавания рукописного текста

Автореферат

Подписано в печать (27.01.2004. Формат 60x90/16 Усл. печ. л. 1.0. Тираж 100 экз. Заказ № 334 Московский физико-технический институт (государственный университет)

141700, г. Долгопрудный Московской обл., Институтский пер., д. 9

»-3097

1. Введение.

2. Обзор и анализ существующих работ.

2.1 Алгоритм построения скелета изображения.

2.2. Регулярные и сингулярные (узловые) области.

2.3. Обзор отдельных работ и направлений.

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

3.3. Выделение прямолинейных участков траектории.41

3.4. Критерий регулярности узловых областей.44

3.5. Основной алгоритм построения регулярных областей.46

3.6 Экспериментальные результаты.49

3.7 Заключение.^^

4. Восстановление траектории в окрестностях узловых областей.51

4.1. Введение.51

4.2. Общая модель.53

4.3. Определение значения априорной вероятности р(С).55

4.4. Определение функции правдоподобия р(Х | С).56

4.5. Восстановление разрывов.64

5. Восстановление набора траекторий.66

5.1. Введение.66

5.2. Предобработка.67

5.3. Алгоритм построения траекторий.73

6. Восстановление траектории при известном эталоне символа.79

7. Проведение эксперимента и результаты.84

7.1. Метод проведения эксперимента.84

7.2. Априорная вероятность конфигурации узла р(С).87

7.3. Качество вероятностной классификации (7.88

7.4. Вычисление распределений для признаков и значений качества признаков.89

7.5. Восстановление узлов.91

7.6. Восстановление разрывов.92

7.7. Восстановление траекторий.92

7.8. Использование эталона.93

7.9. Примеры корректного восстановления и ошибок.95

Заключение.97

Список литературы.100

1. Введение

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

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

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

Основными практическими задачами, требующими автоматическую обработку рукописных документов, являются:

• Обработка банковских чеков. В задаче чаще всего требуется распознать денежную сумму на изображении чека, записанную цифрами и прописью.

• Обработка почтовых конвертов. В задаче требуется распознать адрес на изображении конверта или бандероли.

• Обработка анкет. Среди широкого разнообразия форм можно выделить такие примеры как бюллетени для голосования, налоговые декларации, социологические анкеты, экзаменационные листы и т.д.

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

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

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

1 Термины «офф-лайн» и «он-лайн» распознавание заимствованы из англоязычной литературы, которые в оригинале звучат как off-line handwritten recognition и on-line handwritten recognition

Рис. 1.1. Основные задачи обработки документов

Можно выделить два основных критерия сложности, по которым делятся задачи РРТ: качество рукописного текста и объем словаря.

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

Также важную роль играет объем словаря, т.е. количество возможных различных слов в тексте. Большинство РРТ систем работает с ограниченным словарем малого или среднего объема (100-2000 слов).

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

• Сканирование исходной информации. На этом этапе осуществляется запись изображения документа в цифровой форме в компьютер. Образ документа на экране компьютера представляется черно-белым или цветным изображением с числом градаций серого от 2 до 256.

• Предобработка изображений документа осуществляется с целью устранения различного рода помех, неоднородностей фона на образе документа и выделение зон текста, подлежащего прочтению. Чтобы найти текст среди рисунков, граф, разделительных линий, на фоне рисунков и сеток разрабатываются сложные и трудоемкие алгоритмы [23], [50], [85], [96].

• Сегментация текста выполняется для разделения текста на отдельные строки, а строк на слова и символы. Последняя из этих задач особенно трудна, поскольку в рукописном тексте интервалы между буквами очень часто превышают по длине интервалы между словами, слова могут соединяться друг с другом, а могут иметь разрывы в середине. К операции сегментации приходиться возвращаться, если возникают противоречивые ситуации в интерпретации результатов на последующих этапах анализа [31], [50], [43], [74].

• Распознавание символов. На том этапе производиться попытка выделить в тексте отдельные символы (буквы, цифры, знаки) и идентифицировать их [21], [94]. Если символы конструируются как различные комбинации графем, то возникает множество вариантов интерпретации каждого из них [98], [101].

• Распознавание слов реализуется на основе результатов сегментации текста и распознавания символов. Это также многовариантный процесс, в результате которого формируются варианты интерпретации возможных слов. При этом словарь задачи играет роль фильтра, с помощью которого отбрасываются интерпретации слов, невозможные для данного текста [22], [32], [45], [52].

• Распознавание и интерпретации предложений является обычно заключительным этапом распознавания текста в существующих системах. На нем из множества допустимых слов конструируется синтаксически и семантически корректные фразы. Они и являются основным результатом - образом «прочтенного» текста в памяти компьютера. Как правило, в реальных приложениях набор возможных интерпретаций каждого текста конечен, поэтому в зависимости от его содержания могут также приминаться те или иные решения, например: зачисление указанной в чеке суммы на счет клиента, выполнение машиной требуемой команды после ее написания и т.п. [40], [41], [44], [63], [65].

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

Кратко рассмотрим теперь основные методы, применяемые при распознавании рукописного текста в режиме «офф-лайн».

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

Для сегментации выделенного образа текста на элементы (строки, слова, символы) разработано довольно большое число разнообразных методов [19], [43], [62], [71], [72], [98]. Сегментация текста на строки обычно выполняется на основе анализа горизонтальных гистограмм изображения текста. Для сегментации строки на слова чаще всего используют вертикальную гистограмму строки, на которой находят потенциальные разделители слов - точки сегментации. Различные комбинации этих точек определяют различные варианты сегментации, среди которых определяется один или несколько наиболее правдоподобных. При сегментации слов на символы также часто используют вертикальные гистограммы с привлечением дополнительной информации о направлении линий и форме верхнего и нижнего контура слова в районе потенциальной точки сегментации. Другой подход основан на получении символов как объединения нескольких элементарных штрихов или графем.

На уровне распознавания символов наиболее популярны три группы методов. Условно их можно назвать признаковыми, структурными и эталонными [76], [77], [101]. В первом случае процесс распознавания основан на анализе набора признаков, характеризующих символ, таких, например, как размер символа, число петель, положение относительно строки и т.п. Вторая группа методов использует информацию о структурных взаимоотношениях графем или элементарных частей символа: вертикальных и горизонтальных штрихов, петель и их частей. Наконец, эталонные методы основаны на сравнении распознаваемого символа с набором прототипов <- образов эталонных символов. Трудно сказать, методы какой группы лучше других, т.к. все они имеют свои преимущества на текстах или символах определенных типов. В реальных системах чаще всего используются комбинированные методы, обладающие чертами всех групп. Результатом их применения является оценка правдоподобия появления того или иного символа на данном знакоместе.

На уровне распознавания слов применяются преимущественно два типа методов: аналитические и глобальные [22], [56], [63]. Аналитические методы предполагают наличие результатов распознавания отдельных символов, когда по каждому знакоместу предлагается список символов-кандидатов со своими весами. Слово распознается как наиболее правдоподобная комбинация символов. Для поиска такой комбинации используется динамическое программирование, различные способы оценивания апостериорных вероятностей слов, скрытые марковские модели и др.

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

На уровне предложений используются различные подходы, среди которых можно выделить те, что близки по своей сути к аналитическим методам распознавания слов, только роль букв играют слова, а роль слов - предложения. На вход алгоритма распознавания предложений поступают списки слов-кандидатов для каждого словоместа. Каждому кандидату приписан некоторый вес. Задача алгоритма состоит в определении одной или нескольких наиболее правдоподобных фраз. В различных вариантах алгоритмов известно применение для этих целей марковских моделей, байесовских оценок, динамического программирования [46], [57], [92], [93], [99]. Синтаксические и семантические ограничения на допустимые фразы используются как фильтры для отсева некорректных предложений.

Следует отметить, что методы оценивания апостериорных вероятностей классов получили за последнее время широкое распространение в задачах распознавания рукописного текста. Они применяются при распознавании элементов текста различного уровня. Такие оценки можно получать разными способами, например, на основе байесовского оценивания [48], [64], [65], [73], [98], с применением скрытых марковских моделей [25], [33], [45], [46], [66], [92], [93], с использованием нейронных сетей [53], [58], [65], [71]. Затруднительно сказать, какой их них обеспечивает наилучшие результаты; эксперименты показывают, что они примерно одинаковы по качеству распознавания, имеют различия по требуемому объему обучающей информации и времени работы. В целом же можно отметить, что вероятностный «язык» становиться все более популярным формализмом при решении задач распознавания рукописного текста.

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

Большинство существующих методов решения «офф-лайн» задачи распознавания символов включает три основных этапа: предобработка, формирование набора признаков или структурного представления и классификация. Набор признаков формируется по следующим видам информации, полученным на этапе предобработки [101]: бинарная матрица, сглаженный граничный контур и скелет изображения. Такой подход позволил достичь высокой точности распознавания печатных и аккуратно написанных' символов.

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

В то же время, анализ литературы свидетельствует о, в общем, очевидном факте: на сегодняшний день точность «он-лайн» методов выше точности «офф-лайн» методов [30], [75], [91], [95].

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

Среди существующих методов решения «офф-лайн» задачи РРС метод, основанный на восстановлении траектории написания символа по его бинарному изображению занимает важное место. В последнее время этому подходу посвящено большое количество публикаций [5], [26], [39], [54], [59], [67], [69], [83], [86]. Данный подход можно рассматривать как попытку сведения задачи «офф-лайн» распознавания к «он-лайн» задаче с последующим применением существующих методов «он-лайн» распознавания. Обычно траектория символа имеет разрывы, соответствующие отрыву пера от бумаги. В дальнейшем будем говорить, что символу соответствует набор траекторий движения пера. Начальная и конечная точки каждой траектории - это точки касания и отрыва пера от бумаги. Хотя в «офф-лайн» задаче распознавания в большинстве случаев удается восстановить каждую из траекторий символа, все же невозможно точно определить последовательность возникновения траекторий на изображении, а также для каждой траектории отличить начальную точку от конечной. Поэтому применяемый метод «онлайн» распознавания не должен зависеть от порядка и направления траекторий. Такие методы существуют и успешно применяются. Преимуществом рассматриваемого подхода к решению «офф-лайн» задачи является высокая точность распознавания и малое число эталонов - качества, соответствующие «он-лайн» методам, инвариантным к порядку и направлению траекторий.

Обзор и анализ опубликованных работ показывает (см. главу 2), что до сих пор не создана технология восстановления траектории, способная восстановить траекторию написания символов с высокой точность и сделать возможным применение «он-лайн» алгоритмов к «офф-лайн» задаче.

Цель диссертационной работы и основные задачи исследования:

1. Анализ существующих методов и систем восстановления траектории пера;

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

3. Интегрирование высокоточных методов «он-лайн» распознавания с модулем восстановления траектории;

4. Создание программного комплекса, реализующего разработанную технологию и проведение экспериментов на тестовой базе изображений и траекторий рукописных символов.

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

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

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

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

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

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

Глава 5 содержит алгоритм восстановления траектории по известным регулярным областям и конфигурациям узлов. Строится не одна, а целый набор гипотез о траектории символа упорядоченных по вероятности.

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

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

Заключение

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

Отметим следующие результаты, которые получены в работе:

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

• Предложен критерий определения изображений, для которых невозможно восстановить траекторию на этапе предобработки. Такой подход позволяет определить границы применения разработанной модели восстановления;

• Создана статистическая модель восстановление окрестностей узлов с очень высокой точностью (96.8%);

• Осуществляется поиск и восстановление случайных разрывов на основе математической модели, которая аналогична модели узлов;

• Полное построение траектории написания на основе предыдущих этапов. Учитываются случаи, в которых перо проходит по одному отрезку траектории два раза;

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

• Предложен метод автоматического сбора статистических данных из базы символов необходимых для вероятностных моделей распознавания;

• Проведен эксперимент на базе, состоящей из 10000 изображений рукописных символов, по восстановлению траектории каждого изображения.

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

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

Следующий этап развития модели и технологии - это, очевидно, восстановление траектории слов в задаче распознавания рукописных слов с малым и средним словарем. Кроме того, планируется создание полномасштабной системы распознавания на основе разработанной системы, для этого будут проведены эксперименты с различными системами «он-лайн» распознавания.

Описанная технология в совокупности с методами «он-лайн» распознавания позволит в дальнейшем сделать существенный шаг вперед в такой важной области искусственного интеллекта, как распознавания рукописного текста. Ее внедрение в существующие системы может существенно улучшить качество распознавания рукописных форм.

За пределами работы осталось много интересных и важных вопросов, относящихся к распознаванию в режиме «он-лайн», распознаванию слов, подписей и т.д. Практически не коснулись мы становящихся все более популярными методов распознавания рукописного текста на основе скрытых марковских моделей. Наиболее полную информацию по распознаванию рукописного текста можно получить по трудам двух международных конференций: International Conference on Document Analysis and Recognition, проводимые каждые два года и International Workshop on Frontiers in Handwriting Recognition. Можно рекомендовать также следить за публикациями и разработками ведущих центров исследования по автоматическому чтению документов и распознаванию рукописного текста, таких как Center of Excellence for Document Analysis and Recognition, State University of New York at Buffalo, Баффало, США; Center for Pattern Recognition & Machine Intelligence, Concordia University, Монреаль, Канада.

1. Вентцелъ Е.С. Теория вероятностей М.: Наука, 1985.

2. Гнеденко Б.В. Курс теории вероятностей М.: Наука, 1969.

3. Горский Н., Анисимов В., Горская Л. Распознавание рукописного текста: от теории к практике СПб.: Политехника, 1997.

4. Котович Н.В., Славин О.А. Распознавание скелетных образов // сборник трудов Института системного анализа РАН Методы и средства работы с документами — 2000.

5. Местецкий Л.М., Нефедов А.Г. Восстановление следа пера при анализе сканированных рукописных документов // Доклады 11-й Всероссийской конференции «Математический методы распознавания образов» (ММРО-11). Москва 2003. С. 364-376.

6. Поцепаев Р.В. Распознавание рукописных символов на основе восстановления траектории движения пера // Сборник научных трудов "Обработка информации и моделирование" М., 2002. - стр. 90-97.

7. Поцепаев Р. В. Распознавание рукописных символов на основе восстановления траектории движения пера // Труды XLV научной конференции МФТИ(ГУ) «Современные проблемы фундаментальных и прикладных наук» М.:МФТИ, 2002. - стр. 48.

8. Поцепаев Р.В. "Восстановление траекторий написания символов по их изображениям ". Электронный журнал "Исследовано в России", 120, стр. 1437-1450, 2003 г. http://zhurnal.ape.relarn.ru/articles/2003/120.pdf

9. Поцепаев Р. В. Восстановление траектории написания в задаче распознавания рукописных символов // Организационное управление и искусственный интеллект. Труды ИСА РАН. Москва 2003. С. 427-445.

10. Поцепаев Р.В., Петров И.Б. Восстановление траекторий движения пера по изображениям символов // Доклады 11-й Всероссийской конференции «Математический методы распознавания образов» (ММРО-11). Москва 2003. С. 412-415.

11. Терещенко В., Рыбкин В., ШамисА., Ян Д. Принципы распознавания рукописных символов в системе FineReader // материалы конф. РОАИ-Ш, Нижний Новгород, 1997.

12. Терещенко В.В. Разработка и реализация новых принципов автоматического распознавания рукописных документов в компьютерных системах обработки данных // Диссертация на соискание ученой степени кандидата технических наук — Москва — 1999

13. ТуДж., Гонсалес Р. Принципы распознавания образов. Пер. с англ. М.: Мир, 1978.

14. Фукунага К. Введение в статистическую теорию распознавания образов. Пер с англ. -М.: Наука, 1979.

15. Abuhaiba I.S.I., Holt M.J. J., Datta S. Processing of off-line handwritten text: polygonal approximation and Enforcement of temporal information // Computer Vision, Graphics and Image Processing — 1994. — V. 56. — N 4. — P. 324-335.

16. Abuhaiba I.S.I., Holt M.J.J., Datta S. Processing of binary images of handwritten text documents // Pattern Recognition — 1996. — V. 29. — N 7. — P. 1161-1177.

17. Abuhaiba I.S.I., Holt M.J.J., Datta S. Recognition of off-line cursive handwritten // Computer Vision and Image Understanding— 1998. —V. 71. —N 1. —P. 19-38.28.

18. Anisimov V., Gorski N. Price D., Baret O., KnerrS. Bank Check Reading: Recognizing the Courtesy Amount. // Proc. of the 3d Int. Computer Science Conference, Hong Kong, 1995.

19. Baret O., Loclinet E. Cursive Word Recognition. Fundamentals in Handwriting Recognition, — NATO ASI serie F, Vol. 124, Springer Verlag, 1994.

20. BartenekN. The Role of Handwriting Recognition in Future Reading Systems. // Proc. of the Fifth Int. Workshop on Frontiers in Handwriting Recognition, Univ. of Essex, England, 1996, pp. 147-165.

21. Bartenek N. Off-line Handwritten word recognition using Hidden Marko Model type Stochastic Network. // IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 16, No. 5, pp. 481-496, 1994.

22. Bengio Y., LeCun Y., Nohl C., Burges C. LeRec: A NN/HMM Hybrid for On-line Handwriting Recognition //Neural Computation, Vol. 7, No. 6, pp. 1289-1303, 1995.

23. Boccignone G., ChaineseA., Cordelia L.P., MarcelliA. Recovering Dynamic Information from Static Handwriting // Pattern Recognition — 1993. — V. 26. — N 3. — P. 409-418.

24. Boccignone G„ Chianese A., Cordelia L.P., MarcelliA., Using skeletons for OCR, in: V. Cantoni, L.P. Cordelia, S. Levialdi, G. Sanniti di Baja (Eds.), Image Analysis and Processing, World Scientific, Singapore, 1990, pp. 275-282.

25. Boccignone G., ChaineseA., Cordelia L.P., MarcelliA. Recovering Dynamic Information from Static Handwriting // Pattern Recognition — 1993. — V. 26. — N 3. — P. 409-418.

26. Casey R.G., Lecolinet E. Strategies in Character Segmentation: A Survey. I I Proc. of the 3d Int. Conf. On Document Analysis and Recognition, Montreal, 1995, pp. 1028-1033.

27. Chen M. Y., KunduA. An Alternative to variable duration HMM in Handwritten word recognition. // Proc. of Int. Workshop on Frontiers in Handwriting Recognition III, Buffalo, 1993.

28. Chen M.Y., KunduA., Zhou J. Off-line Handwritten word recognition using Hidden Marko Model type Stochastic Network. // IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 16, No. 5, pp. 481-496,1994.

29. Cornell S.D., Jain A.K. Template-based online character recognition // Pattern Recognition — 2000, — V. 34.—N 1, —P. 1-14.

30. Doermann D.S., RosenfeldA. Recovery of temporal information from static images of handwriting // Proc. Computer Soc. Conf. Computer Vision and Pattern Recognition — 1992.—P. 162-168.

31. Doermann D.S., RosenfeldA. Temporal clues in handwriting // Proc. 11th International Conference on Pattern Recognition — 1992. — Vol. 2 P. — 317-320.

32. Doermann D.S. Document Image Understanding: Integrating Recovery and Recognition. PhD thesis, University of Maryland, Collage Park, 1993.

33. Doermann D. S„ RosenfeldA. The interpretation and reconstruction of inferring stokes // International Workshop on Frontiers in Handwriting Recognition — 1993. — P. 29^0.

34. Doermann D.S., RosenfeldA. Recovery of temporal information from static images of handwriting // International Journal of Computer Vision — 1995. — V. 15. — P. 150154.

35. Fan K.ChWu W.H. A run-length-coding-based approach to stroke extraction of Chinese //Pattern Recognition, 2000,V.33,N. 11, pp. 1881-1895

36. Fujisawa H., Nakano Y, Kurino K. Segmentation Methods for Character Recogni-tion:from Segmentation to Document Structure Analysis. // Proc. Of the 2nd Internat. Conf. on Document Analysis and Recognition, Tsukuba, 1993, pp.1079-1092.

37. Gilloux M., Leroux M. Recognition of Cursive Script Amounts on Postal Cheques. // Proc. Of the 5th USPS Advanced Technology Conf., 1992. pp. 557-562.

38. Gilloux M., Leroux M, Bertille J-M. Strategies for Handwritten Words Recognition Using Hidden Markov Models. // Proc. Of the 2nd Interan. Conf. on Document Analysis and Recognition, Tsukuba 1993, pp. 299-304.

39. Gilloux M. Hidden Markov Models in Handwritten Recognition. Fundamentals in Handwriting Recognition, — NATO AS I serie F, Vol. 124, Springer Verlag, 1994, pp. 264288.

40. Gorsky N.D. Experiments with Handwriting Recognition Using Holographic Representation of Lime Images. // Pattern Recognition Letters, Vol. 15, pp. 853-859, 1995.

41. Gorsky N.D., Gorskaya L. Estimation of Prior Probabilities for the Recognition of Numerals. // Pattern Recognition Letters, Vol. 18,1997.

42. Govindan V.K., Shivaprasad A.P. Character recognition a review // Pattern Recognition1990. — V. 23. — N 7. — P. 671-683.

43. Govindaraju V., Srihari S.N., Separating handwritten text from interfering strokes. — in Simon J.-C., Impedovo S.(Ed.) From pixels to features III: Frontiers in handwriting recognition — Elsevier — Amsterdam — 1992 — P. 17-28.

44. Govindaraju V., Krishnamurthy R.K. Holistic handwritten word recognition using temporal features derived from off-line line images // Pattern Recognition Letters — 1996. — V. 17. —P. 537-540.

45. Ho T.K., Hull J.J., Srihari S.N. Word Recognition with Multi-level Contextual Knowledge. // Proc. Int. Conf. on Document Analysis and Recognition, Saint Malo, France, 1991.

46. Huang Y.S., Lui K., Suen C. FA Neural Network Approach for Multi-classifier Recognition Systems. // Proc pf the Fourth Int. Workshop on Frontiers in Handwritten recognition, Taipei, Taiwan, 1994.

47. Huang T., Yasuhara M. Recovery of information on the drawing order of single-stroke cursive handwritten characters from their 2D images // IPSJ Trans. — 1995. — V. 36. — N9. —P. 2132-2143.

48. Huang T., Yasuhara M. A total stroke SLALOM method for searching for the optimal drawing order of off-line handwriting // Proc. IEEE Systems, Man and Cybernetics Soc.1995.—P. 2789-2794.

49. Impedovo S. Frontiers in Handwriting Recognition. Fundamentals in Handwriting Recognition, — NATO ASI serie F, Vol. 124, Springer Verlag, 1994, pp. 7-39.

50. Jacobs R.A. Methods for Combining Expert's Probability Assessments. // Neural Computation. 1995., No. 7, pp. 867-888.

51. Jaeger S. Recovering writing traces in off-line handwriting recognition: using a global optimization technique // Proc. 13th International Conference on Pattern Recognition — 1996. —P. 150-154.

52. Kato Y, Yasuhara M. Recovery of drawing order from scanned images of multi-stroke handwriting // Proc. Fifth International Conference on Document Analysis and Recognition — 1999. —P. 261-264.

53. Kato Y., Yasuhara M. Recovery of drawing order from single-stroke handwriting images // IEEE Trans. Pattern Anal. Mach. Intell. — 2000. — V. 22. — N 9. — P. 938-949.

54. Kimura F., ShridarM. Segmentation-Recognition Algorithm for ZIP Code Field Recognition. // Machine Vision and Application, 1992, No.5, pp 199-210.

55. Kimura F., Shridar M„ Chen Z. Improvement of a Lexicon Directed Algorithm for Recognition of Unconstrained Handwritten Words. // Proc. Of the 2nd Int. Conf. on Document Analysis and Recognition, Tsukuba, Japa, 1993, pp.18-22.

56. KittlerJ. Improving Recognition Rates by Classifier Combination. // Proc. Of the Fifth Int. Workshop on Frontiers in Handwriting Recognition, Univ. of Essex, England, 1996, pp. 81-103.

57. KnerrS., Anisimov V., Baret O., Gorski N. Price D., Simon J.-C. The A2iA Recognition System for Handwritten Bank Checks. // Proc. Of Document Analysis Systems'96, Malvern, USA, 1996.

58. KunduA., He Y, Bahl P. Recognition of Handwritten Words: First and Second Order Hidden Markov Model Based Approach. // Pattern Recognition, Vol. 22, No. 3, 1989.

59. L 'Homer E. Extraction of strokes in handwritten characters // Pattern Recognition — 2000. —V. 33, —N 10. —P. 1147-1160.

60. Lallican P.M., Viard-Gaudin C. A Kalman Approach for stroke order recovering from off-line handwriting // Proc. Fourth International Conference on Document Analysis and Recognition — 1997. — P. 519-522.

61. Lallican P.M., Viard-Gaudin C., KnerrS. From Off-line to On-line Handwriting Recognition // Seventh International Workshop on Frontiers in Handwriting Recognition. 2000, pp. 303-312.

62. Lam L., Lee S.-W., Suen C. Y. Thinning methodologies a comprehensive survey // IEEE Trans. Pattern Anal. Mach. Intell. — 1992. — V. 14. — N 9. — P. 869-885.

63. Lecolinet E. A Grapheme Based Segmentation Technique for Cursive Script Recognition. // Proc. Of the lsl Int. Conf. on Document Analysis and Recognition, St. Malo, France, 1991, pp. 740-748.

64. LiX., Yeung D.-Y. On-line handwritten alphanumeric character recognition using dominant points in strokes // Pattern Recognition — 1997. — V. 30. — N 1. — P. 31-44.

65. Lippmann R.P., Richard M.D. Neural Network Classifiers Estimate Bayesian A posteriori Probabilities. //Neural Computation, Vol. 3, pp461-483,1991.

66. Lu Y., Shridar M. Character Segmentation in Handwritten Words an Overview. // Pattern Recognition, Vol. 29, No. 1, pp. 77-96, 1996.

67. Mandler E„ Oed R„ Doster W. Experiments in on-line script recognition. // Proc. 4th Scandinavian Conf. on Image Analysis, volume 1, pages 75-86, Champaign, IL, 1985.

68. Matsui T., Noumi T., Yamashita /., Wakahara T., Yoshmuro M. State of Art of Handwritten Numeral Recognition in Japan. // Proc. Of the 2nd Int. Conf. on Document Analysis and Recognition, Tsukuba, 1994, pp. 391-396.

69. Mori S. et al. Historical review of OCR research and development. // Proc. Of the IEEE, Vol. 80., No. 7, pp. 1029-1058,1992.

70. Nishida //., Mori S. Algebraic description of curve structure // IEEE Trans. Pattern Anal. Mach. Intell. — 1992, 14(5), 516-533.

71. Nishida H. Structural feature extraction on multiple bases with application to handwritten character recognition systems // Proc. 2nd Internat. Conf. Document Analysis and Recognition, Tsukuba, Japan, Oct. 1993,27-30

72. Nishida H. Structural feature extraction using multiple bases // Computer Vision and Image Understanding 1995, 62(1).

73. Nishida H. Curve description based on directional features and quasi-convexity / concavity // Pattern Recognition, 1995,28 (5)

74. Nishida H. An approach to integration of off-line and on-line recognition of handwriting // Pattern Recognition Letters— 1995. —V. 16.— P. 1213-1219.

75. Nishida H. Model-based shape matching with structural feature grouping // IEEE Trans. Pattern Anal. Mach. Intell. — 1998, 17(3), 315-320.

76. Document Image Analysis. Eds. O'Gorman L., KasturiR. -N.Y.: IEEE Computer Society Press, 1995.

77. PanJ.C., Lee S. Offline tracing and representation of signatures // Proc. Computer Vision and Pattern Recognition — 1991. — P. 679-680.

78. Pan J.C., Lee S. Offline tracing and representation of signatures // IEEE Trans. Systems, Man and Cybernetics — 1992. — V. 22. — N 4. — P. 755-771.

79. Pavlidis T. Algorithms for Graphics and Image Processing, pp 199-201, Rockville, Md.: Computer Science Press, 1982.

80. Privitera C.M., Plamondon R. A system for scanning and segmenting cursively handwritten words into basic strokes // Proc. Third International Conference on Document Analysis and Recognition — 1995. — P. 1047-1050.

81. Plamondon R., Privitera C.M. The segmentation of cursive handwriting: and approach based on off-line recovery of the motor-temporal information // IEEE Trans. Image Processing— 1991. —V. 8. —N 1. —P. 80-91.

82. Plamondon R„ Srihari S. N. On-line and off-line handwriting recognition: A comprehensive survey // IEEE Transactions on Pattern Analysis and Machine Intelligence, 22(1), pp. 63-84,2000.

83. Rabiner L. R. A Tutorial on Hidden Markov Models and Selected Applications in Speech Recognition. // Proceedings of the IEEE, 77(2): 257- 286,1989.

84. Rabiner L.R., Juang B.H. An introduction to Hidden Markov Models. // IEEE ASSP Magazine, 1986, N. 6, pp 4-16.

85. Sakai K., Asami H., Tanabe Y. Advanced Application Systems for Handwritten Character Recognition. — From Pixels to Features III. Eds. S. Impedovo and J.C.-Simon. Amsterdam: North-Holland, 1992, pp. 201-213.

86. Seiler R., SchenkelM, Eggimann F. Off-line Cursive Handwriting Recognition Compared with On-line Recognition // International Conference of Pattern Recognition, p. 505-509, 1996.

87. Shurmann J. et al Document Analysis from Pixels to Contents. // Proc. Of the IEEE, Vol. 80, No. 7, pp. 1101-1119, 1992.

88. Simon J.-C., Baret O., Gorsky N. Cursive Handwriting Recognition. C. R. Acad. Sci. Paris, t.318, serie II, 1994, pp. 745-752.

89. Simon J.-C., Baret O., Gorsky N. A system for the Recognition of Handwritten Literal Amounts of Checkes. Proc of Document Analysis Systems'94, Kaiserslautern, Germany, 1994.

90. Srihari S. Recent Advances in Off-line Handwriting Recognition at CEDAR. Proc. Of the Fifth Int. Workshop on Frontiers in Handwriting Recognition, Univ. of Essax, England, 1996, pp. 1-15.

91. Tappert C.C., Suen C.Y., Wakahara T. The state of art in on-line handwriting recognition // IEEE Trans. Pattern Anal. Mach. Intell. — 1990. — V. 12. — N 8. — P. 787-808.

92. Trier O. D., Jain A. K., Taxt T. Feature extraction methods for character recognition -a survey I I Pattern Recognition — 1996. — V. 29. — N. 4. — P. 641 -662.

93. Wall K., Danialsson P.-E. A fast sequential method for polygonal approximation of digitized curves // Computer Graphics and Image Processing — 1984. — V. 28. — P. 220-227.

94. YuD., YanH. An efficient algorithm for smoothing, linearization and detection of structural feature points of binary image contours // Pattern Recognition — 1997. — V. 30. —N 1, —P. 57-69.