Содержание к диссертации
ВВЕДЕНИЕ 5
ГЛАВА 1. АНАЛИЗ ПРОБЛЕМЫ 18
Структуризация задачи автоматизированного ввода рукописных документов. 18
Роль распознавания одиночного символа в задаче ввода рукописных документов 20
1.3 Выводы , 22
ГЛАВА 2. ОБЗОР ЛИТЕРАТУРЫ 23
Предварительная обработка изображения символа 24
Вычисление признаков 28
Построение классификатора 31
Структурное распознавание 48
Комбинирование распознавателей 49
Выводы 51
ГЛАВА 3. РЕШЕНИЕ ПОСТАВЛЕННОЙ ЗАДАЧИ 54
Постановка задачи 54
Принцип целостности, целенаправленности и использования контекста 55
Метод целостного, целенаправленного многоуровневого применения растрового, признаковых и структурного классификаторов 58
Векторное изображение 63
Приведение изображений для классификаторов 72
3.6 Выводы 76
ГЛАВА 4. ПРИЗНАКОВЫЕ МОДЕЛИ РАСПОЗНАВАЕМОГО ОБЪЕКТА 78
Признаки на растровом изображении 78
Признаки на векторном изображении 80
Описание признакового классификатора 83
Дифференциальные признаковые эталоны 86
Выводы 89
ГЛАВА 5. СТРУКТУРНАЯ МОДЕЛЬ РАСПОЗНАВАЕМОГО ОБЪЕКТА 91
Общая схема работы структурного классификатора 91
Описание структурных элементов 93
Выделение структурных элементов 102
Сопоставление структурного эталона с изображением 107
Методика разработки структурных описаний 111
Построение структурных описаний 112
Базы изображений 121
Выводы 123
ГЛАВА 6. РЕЗУЛЬТАТЫ ИСПЫТАНИЙ 125
Испытания простого растрового классификатора 126
Испытания признакового классификатора на растре 130
Испытания признакового классификатора на векторе 134
Испытания полной процедуры распознавания 139
Сравнение полученных результатов с результатами аналогичных систем 143
Выводы 144
ГЛАВА 7. РЕАЛИЗОВАННЫЕ ПРОГРАММНЫЕ СИСТЕМЫ И ВНЕДРЕНИЯ .146
Обзор реализованных программных систем 146
Министерство образования. Единый государственный экзамен 149
Центр тестирования Министерства образования РФ 152
Пенсионный фонд России 153
Министерство по Налогам и Сборам России 154
Федеральная Служба Налоговой Полиции России 156
Правительство Москвы 157
Национальная Служба Новостей (НСН) 158
Банковский сектор 158
Маркетинговое агентство СканМаркет 159
АО "Kauno energija" 160
АДИДАС 161
Выводы .....162
ЗАКЛЮЧЕНИЕ .....163
СПИСОК ЛИТЕРАТУРЫ 169
Введение к работе
В связи с повсеместным распространением технологий обработки и хранения информации в электронном виде, перед создателями программного обеспечения возник широкий комплекс задач, связанных с распознаванием образов: от распознавания рисунка радужной оболочки человеческого глаза, дактилоскопических линий и лиц, автомобильных номеров до распознавания речи и печатных или рукописных документов.
По методам решения и актуальности задачи распознавания образов можно разделить на несколько групп:
1. Распознавание символов - задача ввода текстовой информации в компьютер с
последующим выявлением и классификацией отдельных символов.
Распознавание сцен - задача выделения на представленном электронном изображении отдельных объектов и отнесение их к тому или иному классу.
Распознавание речи - задача ввода речевой информации в информационные системы.
Распознавание биометрических данных - распознавание человеческих лиц, радужной оболочки глаза, дактилоскопических линий, тепловой карты ладони и пр.
Другие задачи распознавания.
Следует заметить, что проблема распознавания образов, возникшая первоначально в связи с необходимостью решать задачи зрительного анализа, сегодня поставила перед создателями автоматизированных систем новую крупномасштабную задачу - ввод огромных объемов информации с бумажных документов в компьютер. Концепция «безбумажного предприятия», получившая широкую известность уже во второй половине XX века и давшая импульс для создания и развития особых технологий обработки и распознавания текстовой информации, до сих пор не
реализована на сто процентов даже в рамках одного предприятия - часть информации все равно остается в бумажном виде, и для этого есть весьма серьезные причины:
Коммуникативный аспект. Предприятие не существует изолированно, оно взаимодействует со своими клиентами, партнерами, подрядчиками, государством и т. д.
Законодательный аспект. На сегодняшний день в правовом регулировании деятельности предприятий во многих странах признаются только бумажные документы, что неизбежно увеличивает их поток.
Технологический аспект. В учреждениях, работающих с населением, бумага пока остается единственным общедоступным средством передачи информации, поскольку далеко не у всех учреждений, предприятий, организаций (и уж тем более у физических лиц) есть персональные компьютеры и соответствующие средства связи.
Исторический аспект. Задача ввода в компьютер ранее созданных бумажных документов остается нерешенной для предприятия даже при высоком уровне автоматизации документооборота. Архивы размером в десятки миллионов страниц не являются редкостью для средних и крупных предприятий. Информация, хранящаяся в этих архивах, часто необходима для анализа и прогнозирования будущей деятельности. В последнее время стали активно внедряться технологии многомерного анализа и так называемой «информационной проходки» (data-mining), позволяющие глубоко исследовать скрытые зависимости путем анализа огромных массивов данных [1].
Культурный аспект. Особенности менталитета руководства и многолетние деловые традиции часто оказываются серьезным препятствием на пути к полному переходу на безбумажные технологии. Весьма распространена и такая ситуация: документ изначально подготавливается с помощью компьютера, а затем распечатывается и существует уже в бумажном виде.
Комплекс задач по распознаванию символов можно разделить на два больших класса - распознавание машинопечатных символов и распознавание рукописных символов. В свою очередь распознавание рукописных символов также делится на два класса задач:
Распознавание рукописной информации, введенной с помощью специальных сенсорных площадок или с сенсорного экрана (touch screen).
Распознавание рукописной информации с бумажных носителей.
Первый класс задач, так называемая проблема «on-line recognition», отличается от второго тем, что помимо собственно двумерной графической информации позволяет использовать важную дополнительную информацию в процессе распознавания в виде временной координаты и информации о силе нажима в процессе письма.
Второй класс задач, так называемая проблема «off-line recognition», существенно сложнее в решении, так как использует только двумерную графическую информацию, получаемую со сканера. Кроме того, в отличие от изображений первого класса задач, рукописные символы на бумажных носителях имеют большое количество систематических и несистематических дефектов, таких как: меняющаяся яркость штриха, заливки, склейки, разрывы, возникающие из-за неоднородности бумаги, чернил и дефектов пишущих инструментов.
Если технологии ввода машинопечатных документов (распознавания машинопечатных символов) и технологии on-line recognition достигли серьезных успехов, то задача ввода рукописных символов с бумажных носителей находится в процессе активной разработки.
Среди основных практических задач, требующих ввода рукописных документов с бумажных носителей в информационные системы, можно выделить следующие: перепись населения, ежегодные налоговые декларации и пенсионные формы, голосование с помощью бумажных бюллетеней, Единый Государственный экзамен, платежные документы, статистические отчеты предприятий, анкетирование населения и т.д.
Одной из актуальнейших практических проблем остается задача распознавания адреса на почтовых конвертах. Почтовые системы во многих странах мира до сих пор используют ручную сортировку корреспонденции. По самым скромным оценкам, количество почтовых отправлений измеряется десятками миллиардов в год. Хотя многие страны частично решают задачу компьютеризации почтовых операций, вводя написание почтового индекса по направляющим линиям или стимулируя отправителей использовать маркировку с помощью штриховых кодов, объем корреспонденции, обрабатываемой вручную, остается очень большим. Поэтому в настоящее время почтовые ведомства многих развитых стран активно финансируют исследования в области распознавания образов [2,3].
Весьма важны также результаты распознавания квитанций и чеков в банках. В связи с тем, что количество владельцев электронных карточек и чековых книжек во всем мире исчисляется сотнями миллионов, порождается очень большой объем рукописных документов и возникает задача автоматического ввода данных с квитанции в информационные системы [4,5]. Во многих странах распространенной практикой является оплата товаров и услуг с помощью чековых книжек и кредитных карточек. При совершении покупки или иного платежа оформляется квитанция (slip), в которой указываются сумма, имя клиента, номер карточки и т. д. Затем эти квитанции передаются в банки, которые перечисляют по ним деньги со счета покупателя карточки на счет соответствующего предприятия. Соответственно, возникает задача ввода данных с квитанции в компьютер.
Несмотря на большую востребованность технологий рукописного распознавания с бумажных носителей нельзя сказать, что в настоящее время эти технологии используются повсеместно. Это связано с требованием высокой точности распознавания в условиях колоссальной вариабельности объектов. Под высокой точностью распознавания понимается точность, сравнимая или превосходящая точность альтернативных способов ввода информации, к примеру, точность работы человека. Что касается вариабельности рукописных символов, то достаточно сказать, что количество различных почерков людей может превышать сотни миллионов. Более того, задача усложняется за счет: а) чрезвычайной вариабельности символов в рамках почерка отдельного человека, б) наличия систематических и несистематических
дефектов распознаваемого изображения, в) отсутствия возможности обучения конкретному почерку в процессе использования системы.
Подводя итог вышесказанному можно заключить, что на современном этапе развития технологии автоматизированного ввода машиночитаемых документов в компьютер чрезвычайно актуальной является задача создания классификатора рукописных символов, превосходящего по точности альтернативные способы ввода информации с бумажных носителей, а также малочувствительного к вариабельности символов и к дефектам изображения.
Цель работы
Целью настоящей диссертационной работы является разработка новых методов построения классификаторов и создание новой структурной модели эталонов распознаваемых объектов, позволяющих решать более широкий класс задач в области распознавания символов, чем известно в литературе. В отличие от известных методов распознавания, разрабатываемый метод должен обеспечивать высокую точность распознавания (преодолевающую порог применимости) при распознавании таких объектов, как рукописные символы в двумерном графическом представлении (без информации о траектории написания), без предварительной настройки на почерк пишущего, при наличии естественных дефектов изображения (разрывы, склейки, заливки).
Новизна работы
1. Разработан новый метод распознавания рукописных символов, основанный на
целостном, целенаправленном многоуровневом применении растровых,
признаковых с признаками на растре, признаковых с признаками на векторе,
структурных классификаторов и парных дифференциальных классификаторов.
2. Предложена структурная модель представления рукописных символов,
допускающая применение нового метода построения структурного
классификатора, основанного на принципах целостности, целенаправленности и
использования контекста.
Разработаны новые признаковые модели рукописных символов, которые могут быть использованы в методе целостного, целенаправленного многоуровневого применения растрового, признаковых и структурного классификаторов.
Разработаны и реализованы алгоритмы поиска на изображении объектов, удовлетворяющих структурному описанию; разработаны методы составления и настройки структурных описаний символов.
Создана основа для дальнейших исследований в области поиска наиболее эффективных средств описания структурных эталонов, развития методов построения дифференциальных классификаторов, разработки процедур автоматического создания структурных эталонов, формирования репрезентативных баз символов в различных предметных областях.
Положения, выносимые на защиту
1. Разработанный метод распознавания изображений основывается на
целостном, целенаправленном многоуровневом применении классификаторов, в
число которых входят: растровый классификатор, дифференциальный
растровый классификатор, признаковый классификатор с признаками на растре,
признаковый классификатор с признаками на векторе, дифференциальный
признаковый классификатор и структурный классификатор.
2. Предложенный метод целостного, целенаправленного поэтапного применения
растрового, признаковых и структурного классификаторов позволяет добиться
более высокой точности, чем точность известных признаковых и структурных
классификаторов и вариантов их комбинаций. В частности, сравнение точности
ввода рукописных цифр с использованием этого метода, с аналогичными
данными классификаторов, разработанных двумя ведущими
исследовательскими центрами США и Канады, показывает значительное
преимущество первого: 99,8% по сравнению с 98,09% у лучшего из описанных в
литературе классификатора «GSC» (центр CEDAR, США).
Разработанный структурный классификатор осуществляет сопоставление эталона непосредственно с исходным изображением, а не с заранее просчитанными признаками.
Разработанная модель структурных описаний эталонов распознаваемых объектов, в отличие от классических моделей представления знаний о распознаваемых объектах, позволяет задавать произвольные отношения между объектами через функции нечетких оценок и обладает достаточным быстродействием, чтобы использоваться для распознавания символов в реальном времени.
Разработанные новые алгоритмы поиска структурных элементов на изображении позволяют путем целенаправленного поиска выделять их с высокой надежностью даже при наличии таких дефектов изображения, как склейки, разрывы, заливки.
Предложенная новая схема решающего правила уточняет результаты основного классификатора с помощью специализированных дифференциальных парных классификаторов.
7. Разработанная программная система «FormReader», в которой был реализован
метод целостного, целенаправленного поэтапного применения растрового,
признаковых и структурного классификаторов, по результатам внедрения в
нескольких десятках российских и зарубежных организаций показала
преимущества данного метода по сравнению с альтернативными способами
ввода рукописных документов.
Личный вклад соискателя
Все приводимые в диссертации результаты, относящиеся к разработке методов распознавания символов, разработке моделей изучаемых объектов, проведении численных расчетов и экспериментов, получены лично соискателем или при его непосредственном участии.
На этапе теоретических исследований вклад соискателя заключается в выдвижении принципиально новых идей, в частности: в предложении комбинировать в одной системе распознавания более одного полного признакового классификатора, в формулировании в общем виде метода целостного, целенаправленного, многоуровневого поэтапного применения растрового, признаковых и структурного классификаторов, в создании новых наборов признаков для признакового и структурного классификаторов. На этапе разработки и реализации системы вклад соискателя - в разработке нового алгоритма поиска структурных элементов; в проведении численных расчетов; в разработке и участии в создании программной системы FormReader. На этапе апробации - в проведении экспериментов, в анализе и обсуждении результатов.
Научная и практическая значимость результатов
Разработанный и реализованный метод целостного, целенаправленного многоуровневого применения растрового, признаковых и структурного классификаторов не только позволил добиться высокой точности распознавания при большой вариабельности таких объектов, как латинские и кириллические рукописные символы, но и создал теоретическую и практическую основу для применения этого метода к проблеме распознавания таких объектов, как китайские и японские иероглифы, арабская вязь и прочие рукописные символы, обладающие колоссальной вариабельностью и большим количеством классов.
В настоящей работе получила развитие важная концепция целостности и целенаправленности в теории распознавания.
Так, в разработанной модели структурного классификатора структурные элементы на изображении не выделяются заранее. Вместо этого, поиск элементов делается целенаправленно, прямо в процессе сопоставления эталона с изображением, с использованием априорной информации о символе и атрибутов уже выделенных элементов символа. Это позволяет устойчиво выделять элементы на разорванных и
искаженных рукописных символах - объектах, относящихся к наиболее сложной области проблемы распознавания рукописных символов.
В свою очередь, разработанная целостная модель структурных описаний эталонов распознаваемых объектов открывает новое поле для исследований методов комбинирования классификаторов и в других областях распознавания. В частности, показано, что данная модель применима не только к рукописным символам, но и к печатным символам, что сильно расширяет круг решаемых задач.
Благодаря своей фундаментальности, концепция целостности и целенаправленности применима не только в области распознавания символов, но и во многих других актуальных задачах распознавания.
Предложенный метод целостного, целенаправленного многоуровневого применения растрового, признаковых и структурного классификаторов для распознавания рукописных символов реализован в рамках программной системы «FormReader» и доведен до уровня промышленного использования в Министерстве образования РФ, в Центре тестирования Министерства образования РФ, Пенсионном фонде РФ, Министерстве по налогам и сборам России, Федеральной Службе налоговой полиции России, Правительстве Москвы, Сбербанке РФ, Национальной регистрационной компании, а также в ряде других государственных и коммерческих организаций.
За данный цикл работ по исследованию, разработке и внедрению в отрасли экономики компьютерных технологий постановлением Правительства Российской Федерации от 21 марта 2002 г. N 175 соискателю была присуждена премия Правительства Российской Федерации 2001 года в области науки и техники.
Структура и объем работы
Диссертация состоит из введения, семи глав, заключения и списка цитируемой литературы, включающего 91 наименование. Диссертация изложена на 179 страницах машинописного текста, содержит 17 рисунков и 25 таблиц.
Во введении обоснована актуальность темы диссертации, сформулированы ее цели, научная новизна и основные положения, выносимые на защиту.
В первой главе дается общее описание проблемы автоматизированного ввода рукописных документов в компьютер. Показывается, что основным фактором, влияющим на эффективность и количество ошибок при распознавании всего документа, является точность распознавания одиночных символов. Таким образом, формулируется основная задача исследования: создание высокоточного «интеллектуального» классификатора одиночных рукописных символов, существенно превосходящего по скорости и точности распознавания существующие классификаторы и представляющего результаты в виде, пригодном для использования современными методами контекстной обработки.
Во второй главе представлен обзор литературы по изучаемой проблеме, упорядоченный по основным направлениям исследований в области распознавания рукописных символов. Целенаправленно отобраны наиболее удачные предшествующие результаты и выявлены те направления исследований, в которых возможно добиться качественных улучшений за счет усовершенствования существующих и применения новых методов построения системы распознавания символов.
Выделены пять основных подзадач для построения системы распознавания: выбор способа предварительной обработки изображения, выбор набора признаков для работы простого растрового и признаковых распознавателей, построение классификаторов, структурное распознавание и комбинирование распознавателей.
В первом параграфе подробно излагается задача предобработки изображения, которая обычно выполняется до начала классификации. Задача предобработки ставится в диссертации в строгую зависимость от используемого классификатора, поскольку не существует оптимального метода предобработки вообще и, следовательно, оптимальность должна определяться по результатам работы классификатора. С другой стороны, необходимо учесть, что предобработка изображения всегда приводит к необратимой потере информации.
Во втором параграфе описывается задача выбора признаков для работы растрового и признаковых классификаторов, а также обосновывается необходимость приведения набора признаков к оптимальному виду.
В третьем параграфе дается представление о процедуре классификации, вводятся понятия «обучения» и «тестирования» классификатора, описываются наиболее часто используемые классификаторы, такие как: Байесовский классификатор, полиномиальный классификатор, многоуровневый персептрон, радиальные функции, классификация по ближайшему соседу, кластерный анализ.
Четвертый параграф посвящен описанию структурного распознавания. Выделены два существенно разных подхода к построению структурных классификаторов.
В пятом параграфе рассматривается комбинирование распознавателей разного типа. Такой подход хорошо зарекомендовал себя в решении классической задачи объединения результатов небольшого числа параллельно работающих классификаторов. Однако более сложные схемы объединения (последовательная, последовательно-параллельная) исследованы в значительно меньшей степени. Именно эти схемы и рассматриваются в последующих главах диссертации.
В третьей главе дается содержательная постановка задачи распознавания одиночного символа, и излагаются новые подходы к решению проблемы классификации рукописных символов. Приводится развернутое описание разработанного метода распознавания, который базируется на целостном, целенаправленном поэтапном применении ряда классификаторов, в числе которых полные классификаторы (растровый, признаковый с признаками на растре, признаковый с признаками на векторе, структурный), и парные дифференциальные классификаторы.
В первом и втором параграфах описана постановка задачи и фундаментальный принцип построения структурного классификатора - принцип целостности, целенаправленности и использования контекста.
В третьем параграфе описывается метод целостного, целенаправленного многоуровневого применения растрового, признаковых и структурного классификаторов.
В четвертом параграфе представлен процесс перехода к векторному изображению, называемый векторизацией, осуществляемый для вычисления признаков и обеспечения работы структурного классификатора. Векторное представление изображения моделирует символ в виде статической (без информации о направлении и скорости) траектории движения пишущего инструмента. Алгоритм векторизации заключается в построении векторного изображения на основе растрового, которое задается в RLE-представлении. Приведены три метода векторизации растрового изображения, один из которых (наиболее эффективный) рассмотрен подробно.
В пятом параграфе описывается способ улучшения эффективности системы распознавания методом приведения изображения для простого растрового и признаковых классификаторов. Использование алгоритма приведения для структурного изображения приводит к потере информации о дефектах исходного изображения и поэтому не используется.
В четвертой главе рассказывается о применяемых признаковых моделях распознаваемого объекта.
В первом и втором параграфах дается представление о вычислении наборов признаков, используемых в признаковых классификаторах. Разработана новая система из 232 признаков, которые вычисляются, в отличие от известных подходов, не на растровом, а на векторном изображении символа. Она показала улучшенные результаты по сравнению с другими системами признаков.
Третий и четвертый параграфы дают представление о структуре классификаторов: основной эталон, дифференциальный эталон, решающее правило и механизм обучения. Установлено, что применение нелинейного преобразования ослабляет влияние шумов при обучении эталонов.
В пятой главе описывается разработанная структурная модель распознаваемого объекта. Особое внимание уделено работе структурного классификатора как ключевого классификатора всей предложенной системы распознавания, описанию структурных элементов, разработке языка структурных описаний. В ней описаны разработанные и реализованные алгоритмы поиска на изображении объектов, удовлетворяющих структурному описанию, и программная система, позволяющая составлять и настраивать структурные описания символов и отображать результаты их сопоставления.
Шестая глава содержит информацию об экспериментальных результатах испытания разработанного классификатора (полной процедуры распознавания) и его составляющих частей. Доказано, что созданный классификатор существенно превосходит по точности существующие классификаторы и представляет результаты в виде, пригодном для использования современными методами контекстной обработки.
В седьмой главе описывается, как предложенные подходы к построению классификатора были реализованы в виде программной системы и доведены до уровня промышленного использования. Разработанный модуль распознавания одиночного символа вошел в состав полной системы ввода документов, который был внедрен в эксплуатацию в нескольких десятках организаций.
В заключении подведены итоги диссертационной работы.
