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

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

По методам решения и актуальности задачи распознавания образов можно разделить на несколько групп:

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

2. Распознавание сцен — задача выделения на представленном электронном изображении отдельных объектов и отнесение их к тому или иному классу.

3. Распознавание речи — задача ввода речевой информации в информационные системы.

4. Распознавание биометрических данных — распознавание человеческих лиц, радужной оболочки глаза, дактилоскопических линий, тепловой карты ладони и пр.

5. Другие задачи распознавания.

Следует заметить, что проблема распознавания образов, возникшая первоначально в связи с необходимостью решать задачи зрительного анализа, сегодня поставила перед создателями автоматизированных систем новую крупномасштабную задачу — ввод огромных объемов информации с бумажных документов в компьютер. Концепция «безбумажного предприятия», получившая широкую известность уже во второй половине XX века и давшая импульс для создания и развития особых технологий обработки и распознавания текстовой информации, до сих пор не реализована на сто процентов даже в рамках одного предприятия — часть информации все равно остается в бумажном виде, и для этого есть весьма серьезные причины:

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

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

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

4. Исторический аспект. Задача ввода в компьютер ранее созданных бумажных документов остается нерешенной для предприятия даже при высоком уровне автоматизации документооборота. Архивы размером в десятки миллионов страниц не являются редкостью для средних и крупных предприятий. Информация, хранящаяся в этих архивах, часто необходима для анализа и прогнозирования будущей деятельности. В последнее время стали активно внедряться технологии многомерного анализа и так называемой «информационной проходки» (data-mining), позволяющие глубоко исследовать скрытые зависимости путем анализа огромных массивов данных [1].

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

Комплекс задач по распознаванию символов можно разделить на два больших класса — распознавание машинопечатных символов и распознавание рукописных символов. В свою очередь распознавание рукописных символов также делится на два класса задач:

1. Распознавание рукописной информации, введенной с помощью специальных сенсорных площадок или с сенсорного экрана (touch screen).

2. Распознавание рукописной информации с бумажных носителей.

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

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

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

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

Одной из актуальнейших практических проблем остается задача распознавания адреса на почтовых конвертах. Почтовые системы во многих странах мира до сих пор используют ручную сортировку корреспонденции. По самым скромным оценкам, количество почтовых отправлений измеряется десятками миллиардов в год. Хотя многие страны частично решают задачу компьютеризации почтовых операций, вводя написание почтового индекса по направляющим линиям или стимулируя отправителей использовать маркировку с помощью штриховых кодов, объем корреспонденции, обрабатываемой вручную, остается очень большим. Поэтому в настоящее время почтовые ведомства многих развитых стран активно финансируют исследования в области распознавания образов [2,3].

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

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

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

Цель работы.

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

Новизна работы.

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

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

3. Разработаны новые признаковые модели рукописных символов, которые могут быть использованы в методе целостного, целенаправленного многоуровневого применения растрового, признаковых и структурного классификаторов.

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

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

Положения, выносимые на защиту.

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

2. Предложенный метод целостного, целенаправленного поэтапного применения растрового, признаковых и структурного классификаторов позволяет добиться более высокой точности, чем точность известных признаковых и структурных классификаторов и вариантов их комбинаций. В частности, сравнение точности ввода рукописных цифр с использованием этого метода, с аналогичными данными классификаторов, разработанных двумя ведущими исследовательскими центрами США и Канады, показывает значительное преимущество первого: 99,8% по сравнению с 98,09% у лучшего из описанных в литературе классификатора «GSC» (центр CEDAR, США).

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

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

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

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

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

Личный вклад соискателя.

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

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

Научная и практическая значимость результатов.

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

В настоящей работе получила развитие важная концепция целостности и целенаправленности в теории распознавания.

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

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

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

Предложенный метод целостного, целенаправленного многоуровневого применения растрового, признаковых и структурного классификаторов для распознавания рукописных символов реализован в рамках программной системы «FormReader» и доведен до уровня промышленного использования в Министерстве образования РФ, в Центре тестирования Министерства образования РФ, Пенсионном фонде РФ, Министерстве по налогам и сборам России, Федеральной Службе налоговой полиции России, Правительстве Москвы, Сбербанке РФ, Национальной регистрационной компании, а также в ряде других государственных и коммерческих организаций.

За данный цикл работ по исследованию, разработке и внедрению в отрасли экономики компьютерных технологий постановлением Правительства Российской Федерации от 21 марта 2002 г. N 175 соискателю была присуждена премия Правительства Российской Федерации 2001 года в области науки и техники.

Структура и объем работы.

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

7.13 Выводы.

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

Заключение

.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Установлено, что применение нелинейного преобразования ослабляет влияние шумов при обучении эталонов.

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

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

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

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

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

Как следует из приведенных экспериментальных данных, свойства классификаторов полностью соответствуют ранее приведенным качественным характеристикам. Особо следует отметить повышение точности, даваемое структурным уровнем. Хотя оно проявляется во всех множествах, участвовавших в измерениях, ярче всего это явное улучшение проявилось при распознавании цифр, где растровый классификатор имеет точность 96.85%, признаковый на растре — 90.60%, признаковый на векторе — 97.67%, а добавление структурного классификатора позволяет поднять точность до 99.84%.

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

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

Важной характеристикой классификатора является точность по первым трем вариантам, т. е. процент символов, для которых правильная гипотеза оказалась не ниже третьего места. Это обусловлено тем, что информация о контексте, т. е. словарь и языковые модели, могут исправить ошибку распознавания только в том случае, если правильный вариант располагается не очень глубоко. Например, применительно к английским заглавным буквам точность первого варианта равна всего лишь 98.93%, тогда как по первым трем вариантам она возросла до 99,9%.

После контекстной обработки, точность распознавания английских заглавных букв повышается более чем в 10 раз. Для русских заглавных букв ситуация аналогичная — достигается повышение точности распознавания с 99.09% до 99.9%, т. е. в 9 раз. Таким образом, при наличии полноценной контекстной обработки символов распознаваемого текста можно сократить число ошибок до уровня 0.1% и ниже.

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

За данный цикл работ по исследованию, разработке и внедрению в отрасли экономики компьютерных технологий постановлением Правительства Российской Федерации от 21 марта 2002 г. N 175 автору была присуждена премия Правительства Российской Федерации 2001 года в области науки и техники.

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