Разработка и реализация новых принципов автоматического распознавания рукописных документов в компьютерных системах обработки данных тема диссертации и автореферата по ВАК РФ 05.13.06, кандидат технических наук Терещенко, Вадим Владиславович

• Терещенко, Вадим Владиславович
• кандидат технических наук
• 2000

Оглавление диссертации кандидат технических наук Терещенко, Вадим Владиславович

ВВЕДЕНИЕ

1 ОБЩЕЕ ОПИСАНИЕ ПРОБЛЕМЫ

2 АНАЛИЗ ЛИТЕРАТУРЫ

2.1 Предобработка изображения

2.2 Растровый классификатор

2.3 Признаковые классификаторы

2.4 Структурные классификаторы

2.5 Комбинирование классификаторов

2.6 Выводы

3 МЕТОДЫ РЕШЕНИЯ ПОСТАВЛЕННОЙ ЗАДАЧИ

3.1 Содержательная постановка задачи

3.2 Структура системы распознавания

3.3 Векторное изображение

3.4 Признаковый классификатор

3.5 Растровый классификатор

3.6 Базы изображений

3.7 Описание структурных элементов

3.8 Выделение структурных элементов

3.9 Сопоставление структурного эталона с изображением

3.10 Структурный .дифференциальный классификатор

3.11 Методика разработки структурных описаний

4 ЭКСПЕРИМЕНТАЛЬНЫЕ РЕЗУЛЬТАТЫ

4.1 Результаты испытаний признакового классификатора

4.2 Результаты испытаний растрового классификатора

4.3 Результаты испытаний полной процедуры распознавания

4.4 Сравнение результатов с аналогичными системами

4.5 Анализ результатов

5 ПРАКТИЧЕСКОЕ ПРИМЕНЕНИЕ

5.1 Обзор реализованных программных систем

5.2 Госналогслужба Российской Федерации.

5.3 Пенсионный Фонд России

5.4 Правительство Москвы

5.5 Центр Тестирования (Министерство Образования РФ)

5.6 Национальная регистрационная компания

5.7 Национальная Служба Новостей (НСН)

Введение диссертации (часть автореферата) на тему «Разработка и реализация новых принципов автоматического распознавания рукописных документов в компьютерных системах обработки данных»

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

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

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

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

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

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

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

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

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

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

Заключение диссертации по теме «Автоматизация и управление технологическими процессами и производствами (по отраслям)», Терещенко, Вадим Владиславович

2.6 Выводы

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

2.19) bel(i) = Р(х е Q \ ei(x) =ji,. ек(х) =jK)

2.20)

2.21)

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

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

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

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

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

3 Методы решения поставленной задачи

3.1 Содержательная постановка задачи

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

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

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

Создание структурного классификатора представляет собой наиболее сложную задачу. Описанные в литературе структурные классификаторы не отвечают трем фундаментальным принципам построения структурной системы восприятия -целостности, целенаправленности и использования контекста, которые применительно к общей задаче распознавания образов впервые были сформулированы в [65], и применительно в задаче распознавания рукописных символов описаны в [66, 67, 68, 69, 70,71].

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

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

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

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

Хорошо известно, что с ростом числа классов сложность классификатора растет, в то время как его точность падает. С этой точки зрения наиболее простым случаем является выбор одного их двух возможных классов. Однако такой классификатор на первый взгляд не применим к задаче распознавания символов, т.к. число классов в реальных задачах может достигать 100 и более. Тем не менее можно создать гибридную систему, которая будет объединять обычный классификатор на полное число классов и большое количество парных классификаторов, призванных различать часто путающиеся пары символов. Практическая реализация этой идеи применительно к распознаванию рукописных символов требует решения следующих задач: а) разработать язык описания парных классификаторов, который позволяет программировать индивидуальные признаки для каждой пары путающихся символов; б) разработать и реализовать программную систему, позволяющую создавать значительное количество (>1000) специализированных парных классификаторов за приемлемое время; в) разработать и реализовать процедуру комбинирования классификаторов, которая способна объединить несколько полных классификаторов и очень большое количество парных классификаторов.

3.2 Структура системы распознавания

Входные и выходные данные системы распознавания

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

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

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

Следует отметить, что требования к выходным данным классификатора отличаются от тех, которые выдвигались в первых системах распознавания [72]. Изначально от классификатора требовалось лишь определить наиболее вероятного кандидата, т. е. список состоял всего из одной позиции. При этом никакого ранжирования результатов распознавания по доверительной вероятности не производилось. Такая постановка задачи годится только для применявшейся ранее линейной схемы распознавания текста, когда текст сначала разделяется на строки, потом строки разделяются на символы, а результат распознавания символа является окончательным результатом работы системы. Линейная схема обработки подразумевает, что предыдущий этап полностью завершается до начала следующего. Она обладает одним принципиальным недостатком: решение на каждом этапе принимается в условиях отсутствия информации от последующих этапов. Тем не менее, если есть несколько возможных вариантов деления слова на символы, то для выбора правильного варианта полезно использовать результаты распознавания символов, так как при неверном делении на символы классификатор обычно выдает результат с малой степенью достоверности. Также очень полезными для выбора варианта деления на символы являются результаты проверки распознанного слова по словарю. Преимущественная тенденция, используемая при разработке современных схем распознавания, состоит в том, чтобы откладывать окончательное решение на максимально поздний этап. Это реализуется путем разнообразных схем перебора и обработки с возвратами [73].

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

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

Характеристики используемых классификаторов

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

• Признаковый классификатор. Использует 224 бинарных признака. Решающее правило основано на функции расстояния. При обучении производится кластеризация.

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

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

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

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

Структурный классификатор

Структурный классификатор был разработан в соответствии с принципами целостности, целенаправленности и использования контекста, которые применительно к общей задаче распознавания образов впервые были сформулированы в [65], и применительно к задаче распознавания рукописных символов описаны в [66,67, 68, 69, 70,71].

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

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

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

Структурный эталон

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

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

Отношения задаются как нечеткие логические высказывания. В качестве переменных используются различные атрибуты элементов - длины, описывающие рамки, углы, координаты характерных точек элементов. Большинство отношений сводится к проверке того, что некоторая величина принадлежит диапазону с нечеткими границами. В результате проверки отношения получается оценка в диапазоне [0.1]. Оценка О обозначает что отношение не выполняется, оценка 1 - что отношение выполняется идеально. Оценки всех отношений перемножаются, что соответствует нечеткой логической операции AND. Ниже приведен для примера фрагмент описания символа "Н", переписанный на упрощенном варианте языка структурных описаний. Элементы:

1) Отрезок 01 (обязательный). Отклонения от вертикали от -30° до +45°. Расположен в левой половине описывающей рамки.

2) Отрезок 02 (обязательный). Отклонения от вертикали от -30° до +4 5°. Расположен в правой половине описывающей рамки.

3) Отрезок 03 (обязательный). Отклонения от горизонтали от -30° до +30°. Расположен между отрезками 01 и 02. Нечеткие отношения:

1) Верхний конец 01 левее верхнего конца 02 на величину "ширина рамки"* (0, 7.1) . Оба конца находятся на одной высоте с точностью до "высота рамки"* (0.0, 2) .

2) Длины 01 и 02 равны с точностью до "высота рамки"* (0.0, 2) .

3) .

Отыскание символа на изображении

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

1. В ыделить отрезок 01.

2. Проверить отношения, ссылающиеся на отрезок 01.

3. Выделить отрезок 02.

4. Проверить отношения, ссылающиеся на отрезки 01 и 02.

5. Выделить отрезок 03.

6. Проверить все оставшиеся отношения.

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

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

Рис. 3.1. Поиск структурных элементов на изображении.

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

Дифференциальные классификаторы

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

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

МССИЙС1" "

СУДА*СТВ s ЧБЛИСТ f фСУДА человеком и записываются как выражения на языке структурных описаний. В выражениях используются атрибуты выделенных структурных элементов. Например, для различения цифр 1 и 7 признаком служит угол между двумя отрезками. Для каждого классификатора подбирается индивидуальный набор признаков. Структурное описание символа полностью определяет положение и свойства его частей, т. е. эффективно размечает символ, позволяя получить координаты всех характерных точек. Наличие полной информации о структуре символа дает возможность очень просто запрограммировать индивидуальный набор признаков с отличной различающей способностью. В описываемой системе признаки записываются как выражения на специальном языке, который допускает вычисление широкого спектра характеристик изображения и дает полный доступ к структуре символа. Использование дифференциальных классификаторов, которые основываются на информации о структуре символа, позволяет добиться очень высокой точности распознавания.

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

Векторное изображение

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

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

Признаковый классификатор

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

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

Растровый классификатор

Растровый классификатор работает с изображением размером 14x14 точек. Точки уменьшенного изображения рассматриваются как координаты вектора в 196-мерном пространстве. Белые и черные точки изображения представляются координатами -1 и +1, соответственно, точки эталона представляются целыми числами в диапазоне от -127 до + 127.

Во время обучения вычисляется средний вектор р по всем изображениям одного класса. Расстояние w вычисляется по косинусу угла между вектором входного изображения х и средним вектором класса;?.

X = {х, = ±1, p = {p,lp,e [-1.+1] (3.1)

Комбинирование классификаторов

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

Классификатор Точность Процент отказов Как работает при сильном изменении формы символа Как работает на разорванных символах Как работает на залитых символах Скорость работы

Признаковый + дифференциальн ый признаковый средняя средний Нормально плохо плохо высокая

Растровый низкая высокий Плохо хорошо хорошо высокая

Структурный + дифференциальн ый структурный очень высокая высокий Хорошо хорошо плохо низкая

Заключение

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

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

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

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

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

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

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

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

Список литературы диссертационного исследования кандидат технических наук Терещенко, Вадим Владиславович, 2000 год

1. Rakesh Agrawal, Data Mining: Crossing the Chasm, Invited talk at the 5th ACMSIGKDD Int'l Conference on Knowledge Discovery and Data Mining (KDD-99), San Diego, California, August 1999.

2. V.Govindaraj, A.Shekhawat, and S.N.Srihari, Interpretation of handwritten address in US mail stream, Proc. of3rdIWFHR, 1993, pp. 197-206.

3. T.Paquet and Y.Lecourtier, Handwriting recognition: Application on bank cheques, Proc. of 1st Intl. Conf on Document Analysis and Recognition, St. Malo, France, Sept. 1991, 749-750.

4. T. Pavlidis, Recognition of printed text under realistic conditions, Pattern Recognition Letters 14 (1993) 317-326.

5. A.Amin and R.Shiu, New Skew Detection and Correction Algorithms, in Progress in Handwriting Recognition, World Scientific, London, 1996.

6. A.Kornai, K.M.Mohiuddin and S.D.Cornell, Recognition of cursive writing on personal checks, in Progress in Handwriting Recognition, World Scientific, London, 1996.

7. G.Shrikantan, D.S.Lam and J.T.Fatava, Comparision of normalizaion methods for character recognition, in Proc. of the Third Int. Conf. on Document Analysis and Recognition, Aug., 1995, 719-722.

8. Q.Huang, B.Dom, N.Megiddo, and W.Niblack, Segmenting and Representing Background in Color Images, in 13th Intl. Conf. on Pattern Recognition, Vienna, Austria, Aug 1996.

9. S.Suzuki, N.Ueda, and J.Sklansky, Graph-based Thinning for Binary Images, in Thinning Methodologies for Pattern Recognition, World Scientific, London, 1994.

10. B.J.H Verwer, L.J. van Viet, and P.W.Verbeek, Binary and Grey Skeletons: Metrics and Algorithms, in Thinning Methodologies for Pattern Recognition, World Scientific, London, 1994.

11. Ковалевский В. А. Методы оптимальных решений в распознавании изображений. -М.: Наука, 1976.-328 с.

12. Журавлев Ю. И., Никифоров В. В. Алгоритмы распознавания, основанные на вычислении оценок. // Кибернетика. -1971.-N3-c.l-ll.

13. Журавлев Ю. И. Об алгебраическом подходе к решению задач распознавания или классификации // Проблемы кибернетики. 1978. - Вып. 33. - с. 5-68.

14. Журавлев Ю. И. Исаев И. В. Построение алгоритмов распознавания корректных для заданной контрольной выборки // Журнал вычислительной математики и мат физики. -1979- 19, N3.-с. 726-738.

15. Вапник В. Н., Червоненкис А. Я. Теория распознавания образов. М.: Наука, 1974. -415 с.

16. T.Cover and P.Hart, Nearest neighbour pattern classification, IEEE Trans, on Inf. Threory 13(1967)21-27.

17. S. German, E. Bienestock and R. Doursat, Neural networks and the bias/variance dilemma, Neural Computations 4, 1 (1992) 1-58.

18. G. Lorentz, Approximation of functions, Chelsea Publishing company, New York, 1986.

19. Вапник В. H. Восстановление зависимостей по эмпирическим данным. Москва, Наука, 1979,447 с.

20. Вапник В. Н., Червоненкис А.Я. Теория распознавания образов, Москва, Наука, 1974, 415 с

21. P. Niyogi and F. Girosi, On the relationship between generalization error, hypothesis complexity, and sample complexity for radial basis functions, A.I. Memo 1467, Massachusetts Institute of Technology, 1994.

22. J. Schiirmann, Polynomklassifikatoren fur die Zeichenerkennung: Ansatz, Adaptation, Anwendung, Oldenbourg Verlag, Miinchen, 1977.

23. D. Rumelhart, J. McClelland, and the PDP Reseach Group, Parallel Distributed Processing, MIT Press, Cambridge, 1986.

24. Y.-H. Pao, Adaptive Pattern Recognition and Neural Networks, Addison-Wesley, New York, 1989.

25. H. White et al., Artificial Neural Networks: Approximation and Learning Theory (Blackwell, Cambridge, 1992).

26. D. Rumelhart, J. McClelland, and the PDP Research Group, Parallel Distributed Processing (MIT Press, Cambridge, 1986).

27. W. Schiffinann, M.Joost, and R.Werner, Optimization of the Backpropagation Algorithms for training multilayer perceptrons, Proc. of the IEEE Int. Conf. от Neural Networks, ed. H Ruspini (San Frncisco, 1993) 586-591.

28. Y.Le Cun et al., Backpropagation applied to handwritten zip code recognition, Neural Computations 1, 1 (1989) 541-551.

29. K. Fukushima and S. Miyake, Neocognition: A new algorithm for pattern recognition tolerant of deformations and shitfs in position, Pattern Recognition 15, 6 (1982) 455-469.

30. S. Fahlman, Faster-learning variations of back-propagation: an empirical study, Proc. of the 1988 Connectionist Models Summer School, eds. D. Touretzky, G.Hinton, and T. Sejnowski (Morgan Kauffman, San Mateo, 1989) 38-51.

31. W. Schiffman, M Joost, and R. Weiner, Optimization of the backpropagation algorithm for training multilayer percepton, Technical Report, University of Koblenz. Institute of Physics, 1992.

32. M. Riedmiller and H. Braun, A direct adaptive method for faster backpropagation learning: The RPROP algorithm, Proc. of the IEEE Int. Conf. of Neural Networks, ed. H. Ruspini, (San Francisco, 1993) 586-591.

33. A. Weigend and N. Gershenfeld, eds., Times Series Prediction: Forecasting the future and Understanding the Past, (Addison-Wesley, Reading, 1993).

34. Y. Le Cun, J. Denker, and S. Solla, Optimal brain damage, Advances in Neural Information Processing Systems 2 (NIPS-89), eds. D. Touretzky (Morgan Kaufmann, San Mateo, 1990) 598-605.

35. B. Hassibi and D. Stork, Second order derivatives for network pruning: optimal brain surgeon, Advances in Neural Information Processing Systems 5 (NIPS-92), eds. S. Hanson, J. Cowan and G. Giles (Morgan Kaufmann, San Mateo, 1993) 164-171.

36. F. Hargert et al., Domain independent testing and performance comparison for neural networks, Artificial Neural Networks 2 (Proc. Int. Conf. on Artificial Neural Networks), eds. I. Aleksander and J. Taylor (North-Holland, Amsterdam, 1992) 1071 -1075.

37. J. Park and I. Sandberg, Universal approximation using radial-basis-function network, Neural Computations 3,2 (1991) 246-257.

38. Y.Linde, A. Buzo, and R. Gray, An algorithm for vector quantizer design, IEEE Trans, on Commun. 28,1 (1980) 84-95.

39. T. Kohonen, Self-Organization and Associative Memory (Springel-Verlag, Berlin, 1989).

40. SOM Programming Team, SOM-PAK: The Self-Organizing Map Program Package, Version 1.2, Copyright: T.Kohonen, J. Kangas, and J.Laaksonen, Helsinki University of Technology, Espoo, 1992.

41. LVQ Programming Team, LVQ-PAK: The Lerning Vector Quantization Program Package, Version 2.1, Copyright: T.Kohonen et al, Helsinki University of Technology, Espoo, 1992.

42. R. Redner and H Walker, Mixture densities, maximum likelihood and the EM algorithm, SLAM Review 26,2 (1984) 195-239.

43. J. Moody and C. Darken, Fast learning in networks of locally-tuned processing units, Neural Computations 1,2 (1989) 281-294.

44. D. Dasarathy, ed., Nearest Neighbor (NN) Norms: NN Pattern Classification Techniques (IEEE Сотр. Soc. Press, Los Alamos, 1990).

45. T. Cover and P. Hart, Nearest neighbor pattern classification, IEEE Trans, on Inf. Theory 13(1967)21-27.

46. U. Kressel, The impact of the learning-set size in the handwritten-digit recognition, Artificial Neural Networks (Proc. Int. Conf on Artificial Neural Networks), eds. T. Kohonen et al. (North-Holland, Amsterdam, 1991) 1685-1689.

47. E.B. Бауман, A.A. Дорофеюк. Классификационный анализ данных. Международная конференция по проблемам управления. Избранные труды, том 1. М: СИНТЕГ 1999. -316 с.

48. Е.В. Бауман. Методы размытой классификации (вариационный подход). -Автоматика и телемеханика, 1988, N 12, с. 143-156.

49. Р. Нерасимхан. Лингвистический подход к распознаванию образов. В сб. "Автоматический анализ сложных изображений", М., изд-во "Мир", 1969.

50. В. П. Романов, А. А. Савин. О структурно-лингвистическом методе распознавания изображений. В сб. "Структурные методы опознавания и автоматическое чтение". М. ВИНИТИ, 1970.

51. В. П. Романов. Локальный анализ изображений при помощи анизотропных локальных фильтров. Докл. АН СССР, 1966, т. 168, N 3.

52. R. Nerasimhan. Buble scan 1 program. Digital Computer lab., Univ. Illinois Aug., 1964, Rept. 167.

53. А. А. Фельдбаум, О некоторых принципах распознавания образов. В. сб. "Самообучающиеся автоматические системы", М., изд-во "Наука", 1966.

54. B.C. Катинский, Т.К. Романычева, С.А. Судаков. Описание изображения с помощью их представления графами. В сб. "Автоматические читающие устройства". М., ВИНИТИ, 1967.

55. C.Y. Suen, С. Nadal, Т.А. Mai, R. Legault, and L.Lam, Recognition of totally unconstrained handwritten numerals based on concept of multiple experts, Proc, Int. Workshop on Frontiers in Handwriting Recognition, Montreal, Canada, April 1990, 131 -143.

56. C.Y. Suen, C. Nadal, R. Legault, T.A. Mai, and L.Lam, Computer recognition of unconstrained handwritten numerals, Proc. IEEE 80 (1992) 1162-1180.

57. P.D. Gader, D. Hepp, B. Forester, and T. Peurach, Pipelined systems for recognition of handwritten digits in USPS ZIP codes, Proc. U.S. Postal Service Advanved Technology Conference, 1990, 539-548.

58. L.Xu, A. Krzyzak, and C.Y. Suen, Methods on combining multiple classifiers and their application to handwriting numerals recognition, IEEE Trans, on Systems, Man and Cybernetics 22(1992)418-435.

59. J.H. Holland, Adaptation in Natural and Artificial Systems (Univ. of Michigan Press, Ann Harbor, 1975).

60. L. Lam and C.Y. Suen, A theoretical analysis of the application of majority voting to pattern recognition, Proc. 12th Int. Conf on Pattern Recognition, Jerusalem, Israel, Oct. 1994, 418-420.

61. L. Lam and C.Y. Suen, Increasing experts for majority vote in OCR: theoretical considerations and strategies, Proc. 4th Int. Workshop on Frontiers in Handwriting Recognition, Taipei, Taiwan, Dec. 1994,245-254.

62. Y. Baikov, E.S. Kuzin, A.L. Shamis, The semantic approach to constructing machine vision systems. IF AC Artificial Intelligence, Leningrad, USSR, 1993.

63. К. Анисимович, В. Терещенко, А. Шамис, Д. Ян, Методы распознавания рукописных текстов, материалы семинара "Динамические Интеллектуальные Системы в Управлении и Моделировании", Москва 1996г.

64. К. Anisimovich, V. Rybkin, A. Shamis, V. Tereschenko, Using combination of structural, feature and raster classifiers for recognition of hand-printed characters, Proc. of the Intl. Conf. on Document Analysis and Recognition, 1997, Ulm, Germany.

65. К. Анисимович, В. Терещенко, А. Шамис, M. Шинкарев, Признаковый уровень системы распознавания рукописных текстов, материалы семинара "Динамические Интеллектуальные Системы в Управлении и Моделировании", Москва 1996г.

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

67. В. Терещенко, Д. Ян, К. Анисимович, Способ построения динамических растровых эталонов компьютерных кодов в процессе распознавания соответствующих им оригиналов, заявка на патент N 99104416, дата поступления 15/03/99.

68. S.Mori, C.Y.Suen, and K.Yamamoto, Historical review of OCR research and development, Proc. of IEEE 80,7, 1992, 1029-1058.

69. D.G.Ellimna, and I.T.Lancaster, A review of segmentation and contextual analysis techniques for text recognition, Pattern Recognition 23, 3/4,1990, 337-346.

70. D.S. Lee, S. N. Srihari Handprinted Digit Recognition: A comparision of Algorithms, Proc. oflWFHR III, New York, 1993, USA.

71. J. Franke On Functional Classifier, Proc. of 1st Int. Conf On Document Analysis and Recognition, St. Malo, 1991, pp. 481-489.

72. J. Franke, L. Ram, R. Legault, C. Nadal, C.Y. Suen, Experiments with the CENPARMI Data Base Combining Different Classification Approaches, Proc. of IWFHR III, New York, 1993, USA.