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

РГБ ОД

/ЛПП

ИНСТИТУТ СИСТЕМНОГО АНАЛИЗА РОССИЙСКОЙ АКАДЕМИЯ НАУК

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

СЛАВИН Олег Анатольевич

УДК 681.3.001.25

КОМБИНИРОВАННЫЕ АЛГОРИТМЫ В ЗАДАЧАХ РАСПОЗНАВАНИЯ ТЕКСТОВ

Специальность 05.13.01 — Управление в технических системах

АВТОРЕФЕРАТ

диссертации на соискание ученой степени

кандидата технических наук

МОСКВА 2000

Работа выполнена в Институте Системного Анализа РАН.

Научный руководитель докг. техн. наук, профессор Арлазаров B.JI.

Официальные оппоненты:

докг. техн. наук, профессор Петровский А.Б.,

канд. физ.-мат. наук, доцент Логинов A.C.

Ведущая организация: Факультет Вычислительной Математики и Кибернетики Московского государственного университета.

Защита диссертации состоится 24 апреля 2000 года, в 10-00 на заседании диссертационного совета К003.63.01 при Институте Системного Анализа РАН. Отзывы в двух экземплярах, заверенные печатью, просим направлять по адресу: 117312, Москва, проспект 60-лет октября, д. 9.

С диссертацией можно ознакомиться в библиотеке Институте Системного Анализа РАН.

Автореферат разослан 24 марта, 2000 г.

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

докт. техн. наук

Хомяков П.М.

j m.Mf-oJf, ь

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

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

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

В процессе работы получены следующие новые результаты.

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

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

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

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

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

Реализованные алгоритмы входят в состав программного продукта OCR Cognitive Cuneiform®, предназначенного для распознавания печатных текстов и реализованного в сотнях тысяч экземпляров (в частности, распространяемого в России в комплекте со сканерами фирмы Hewlett-Packard). Также распознающие библиотеки входят в состав комплекса автоматизированного массового ввода пенсионных анкет, созданного на основе ICR Cognitive Forms® и внедренного в Московском пенсионном фонде.

Публикации. По теме диссертации опубликовано 6 работ.

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

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

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

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

Глава 3 посвящена комбинированным алгоритмам распознавания символов

печатного и рукопечатного типа в ситуациях автономного распознавания и в процессе сегментации границ символов.

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

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

СОДЕРЖАНИЕ РАБОТЫ

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

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

{ (8,ЛУ,).....(виЖ) }

или пустой коллекции { 0 }

где - код символа, также называемый кодом альтернативы, 1 5 I < п

\У| - оценка символа, также называемая оценкой альтернативы п - объем коллекции, п^О. Альтернативы упорядочены по убыванию оценок, то есть \У1>\Уц-1. Альтернатива ^ДУО называется ведущей альтернативой. Оценки

являются дискретными и ограниченными степенью двойки, то есть УУ, 6 {0,1,...,2К-1}

где N=8, за исключением специально оговоренных случаев. При этом предполагается, что максимальная оценка (г1"-!) достижима методом и что завершен процесс обучения метода на обучающей последовательности образов из ГБД, отличной от тестовой ГБД.

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

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

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

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

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

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

{0, Wr, W«.....W,.„2"-l),

разбивающих множество возможных значений оценок на интервалы, надежность распознавания в каждом из которых превосходит надежность на предыдущем интервале. Монотонность оценивается двумя показателями; пороговой монотонностью, равной ГЧ'.ггО^г^О^г) ■

где N„r(WT) - число неправильно распознанных образов с оценкой W^ у» Wmax N(WT) - общее число образов, распознанных с оценкой Wi^ у Wmax Wmai - максимально возможная оценка и монотонностью максимальной оценки, получаемой из пороговой монотонности при значении у=1.

Вероятностный смысл оценок состоит в выполнении следующих соотношений Wi»(2N-l)»N*(Wi)/N(W,), где N*(W|) - число правильно распознанных образов с оценкой Wi образов на достаточно большой тестовой ГБД

N(VVi) - число образов ГБД, распознанных с оценкой Wi а также

W,+W2+... +Wn=2N-J то есть сумма оценок альтернатив коллекция, масштабированных на (2N-1), равняется единице.

Легкость обучения зависит от соотношения объема обучающей последовательности образов и времени, необходимого для достижения цели обучения. В простейшем случае легкость обучения может быть определена как N/T, где N - число образов в обучающей ГБД, а Т - время обучения. Эта характеристика связана с возможностью динамического обучения в многопроходной системе распознавания текстов и мощностью вычислительной системы, на которой осуществляется обучение . Первичное обучение метода на базах графических образов большого объема может быть сколь угодно долгим, но дообучение возможно лишь в методах, допускающих коррекцию без обучения на первичной последовательности символов.

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

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

■ ■2

Рис.1 Пример символа различных типов: печатного, рукопечатного и почтового

индекса

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

Данные определения точности, полноты коллекции, скорости, способности к отказам и устойчивости к вариациям зависят от тестовых ГБД. Стабильность этих характеристик на различных ГБД большого объема (порядка 106) позволяет говорить об этих свойствах базовых методов безотносительно баз данных.

Часть определенных выше характеристик (точность, полнота коллекции, монотонность оценок) используется как важные показатели эффективности использования распознающего алгоритма. Другая часть (алфавит, представление, тип) существенна с точки зрения пригодности метода для комбинирования с другими механизмами распознавания. Перечислим несколько реализованных алгоритмов распознавания символов в сочетании с их характеристиками и особенностями. Примеры базовых методов распознавания символов. Событийный метод опирается на топологическую структуру объекта, не изменяющуюся при малых деформациях образа. Событием называется часть образа, в каждом сечении которого имеется всего один интервал. Набор событий, огрубленных на некоторой сетке, определяет эталонный класс образов. Обучение метода сводится к составлению списка эталонов на достаточно большой ГБД; при этом целесообразно одновременное обучение поворотным событиям, получаемым из поверяутого на 90° образа. При распознавании для исходного растра определяются прямое и поворотное событийные представления, каждому из которых сопоставляется эталонный класс, пересечением прямого и поворотного классов определяется результат. Метод не порождает оценок. Достоинствами метода являются способность к отказам, полнота коллекции, высочайшее быстродействие. Также отметим устойчивость обучения, заключающуюся в улучшении полноты при пополнении эталонных наборов.

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

сетки обеспечивается простотой начертаний многих букв кириллицы и латиницы («ИНПТЕБС»), более сложные образы («ЖШЩХУМ») лучше распознаются эталонами конфигурации 5x3. Достоинствами метода являются монотонность оценок, устойчивость к разрывам образов, быстродействие и легкость дообучения, недостатками - малая точность. Над представлением 3x5 возможно построение нейронной сети 3x5. Возможно создание бинарных нейронных сетей с одним единственным выходом, порождающим оценку сходства с некоторым символом из алфавита. По отношению к методу 3x5 точность распознавания повышается, но монотонность оценок снижается.

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

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

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

Характеристики базовых алгоритмов распознавания позволяют упорядочение методов, приведенное в таблицах I и 2 для печатных и рукопечатных типов символов.

Таблица 1 Методы распознавания печатных букв

1 место 2 место 3 место

Точность Нейронная сеть Наложение 3x5

Полнота коллекции Нейронная сеть Наложение 3x5

Способность к отказам Событийный метод "

Быстродействие Событийный метод 3x5 Нейронная сеть

Монотонность 3x5 Наложение Нейронная сеть

Таблица 2 Методы распознавания рукопечатных букв

1 место 2 место 3 место

Точность Нейронная сеть Скелетон Наложение

Полнота коллекции Нейронная сеть Наложение Скелетон

Б ыстро действие Нейронная сеть Скелетон Наложение

Монотонность 3x5 Наложение Нейронная сеть

Данные таблиц показывают различия характеристик различных базовых методов. Обращают на себя внимание простые методы, использующие грубые представления, но обладающие конкурентоспособными характеристиками. Абсолютным лидером среди базовых методов является нейронная сеть, но монотонность ее оценок уступает методам наложения, а быстродействие -событийному методу, способному к отказам. Отметим, что возможность динамического дообучения свойственна из перечисленных методов только методам наложения. Эти различия, то есть преимущества различных методов распознавания, делают возможным синтез комбинированных методов распознавания с улучшенными и оптимизированными характеристиками, чему посвящена третья глава. Комбинированные методы распознавания. Для рукопечатных образов с ориентировочными границами в документах, предназначенных для массового ввода с последующим редактированием, предлагается несколько схем комбинирования. Простейшей из них является голосующая схема, в которой оценкой символа является количество базовых методов, породивших этот символ в качестве одной из своих альтернатив. Показано, что такая схема пригодна для почтовых цифровых индексов, для которых несколько базовых методов (событийный, нейронная сеть, 3x5 и древовидный) дают сходные по точности (около 99.5%) результаты. Голосующая схема для почтовых индексов характеризуется как высочайшими точностью (доля ошибок - 10"6) и монотонностью, так и приемлемым быстродействием.

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

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

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

NOUi - число неотмеченных полей, содержащих ошибки Nco„h - число отмеченных полей, требующих проверки оператора N - общее число полей Тогда качество Q вычисляется следующим образом

N

где к| и kj - коэффициенты, связанные со стоимостью ошибки и стоимостью работы операторов. Для построенных комбинированных методов Q я 0.99xki+0.1xk2. Сегментация символов. Распознавание печатных символов в отсутствии знания ориентировочных границ символов происходит в условиях значительно большего, чем для рукопечатных образов, процесса комбинирования компонент связности и их частей. Предложенная сегментация печатных символов базируется на заранее найденном наборе хо, Xi,...,Xn отрезков разрезания и построении оптимального пути на основе динамического программирования. В точку ведут п путей a„n=(0,n), a„i=(ai,n), ... .яц.гп !)=(яп,п),

причем для каждого из возможных путей, ведущих в промежуточную точку xi, нам уже известен оптимальный путь ai. Из всех путей а„0, a„i, ... ,3n,(n-i>выберем путь а„ с наибольшей оценкой: ц(а„) = max(p(0,n), max( n(ai,n)) ), l<i<n,

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

Приемлемое комбинирование состоит в сочетании полезных свойств быстрого, точного и монотонного алгоритмов. В диссертации подробно рассматривается один из таких методов, названный 9?о и состоящий из трех этапов. На первом из них происходит генерация коллекции {(Si,\VGi), ... ,(S„,WG„)} быстрым алгоритмом (событийным или древовидным методом), с немонотонными оценками WGi, но с достаточной полнотой коллекции. Далее работает монотонный метод (наложение, 3x5), использующий множество сгенерированных символов {Si, ... ,S„} в качестве суженного алфавита. В сформированном результате {(Ci.WEi),... ,(СП,\УЕ„)} коды Ci символов порождены быстрым методом-генератором, а оценки WE| - монотонным

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

Метод 5Яо обладает точностью и полнотой коллекции, превосходящими соответствующие характеристики составляющих методов, но его монотонность недостаточна для выявления несимволов, появляющихся во время сегментации символов. Мощным средством снижения оценок несимволов являются дискриминаторы - штрафные функции, использующие априорные модели идеальных символов. Простейшими дискриминаторами являются штрафы за пропорции букв и размеры символов. Более сложные дискриминаторы базируются на структурных описаниях символов различных начертаний, сопоставляемых со структурой исследуемого образа. Дискриминаторы рассматриваются не как отдельный базовый метод, а как механизм компенсации ошибок определенного базового или комбинированного алгоритма. Дискриминатор, примененный к коллекции {фЛУО,... ,(8„,\У„)}, приводит ее к виду

{(81,тах(0ДУ1-Р(81,1))), ... .(в« тах(0,\У,-Р(8„,1)))}, где Р(Б„1) - штраф образу I, рассматриваемому как символ . Дополнив комбинированный метод 5йо набором дискриминаторов, выполняемых всегда, мы получим метод Ль пригодный для использования в схеме сегментации печатных символов. Алгоритм обладает следующими характеристиками: точность распознавания - 99.8%, монотонность -менее 0.1% ошибок с оценкой более 0.94 от максимально возможной оценки, полнота коллекции - 99.98%.

Метод с дискриминацией обладает двумя большими недостатками. Во-первых, образы символов, не удовлетворяющие модели идеального символа, используемой дискриминаторами, например, символов из декоративных шрифтов исключаются из числа старших альтернатив. Во-вторых, символы, в общем, удовлетворяющие модели идеального символа, но оштрафованные за различные дефекты, получают невысокие оценки, даже будучи верно распознанными. Эти недостатки алгоритма устраняются использованием более точных базовых методов, таких как общая нейронная сеть и методы наложений. Надежность результатов обеспечивается монотонностью оценок указанных методов, усиленной пересечением результатов нескольких механизмов. Комбинированный метод ЗЪ, полученный введением в 311 точных методов, устраняет проблемы дискриминаторов и включающий в себя операции подтверждения, состоящие в следующем. Если код ведущей альтернативы коллекции, порожденной некоторым базовым методом или парой генератор-эксперт, совпадает с кодом альтернативы (81^1) конкурирующего распознающего алгоритма, а оценка \У1 достаточно высока, то код символа подтверждается. Подтверждение несколькими монотонными методами является достаточным для отмены дискриминации и перераспознавания, а также основой

формирования вероятностных оценок. Метод 3^2 обладает очень высокими характеристиками распознавания, а именно, на ГБД объемом порядка 104, содержащих образы, отобрашше человеком, допускает единичные ошибки по любой из используемых характеристик; точность отделения символов от несимволов во время сегментации также надежна Недостатком 9?г является снижение быстродействия по отношению к более чем в 2 раза.

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

Для оценки качества схем сегментации пригодны те же самые характеристики, что и для оценки свойств базовых и комбинаторных методов распознавания, а именно, точность распознавания, полнота коллекции, быстродействие и монотонность оценок. Они дополняются точностью сегментации, определяемой как процент правильно найденных границ символов, и полнотой сегментации, то есть наличия правильного варианта разрезания среди нескольких хранимых. Характеристики схемы подсчитываются на тестовом наборе изображений с разнородной текстовой информацией, отсканированных с различными значениями яркостей. Полнота коллекций схем сегментации, базирующихся на методах 5Hi и ЭЯг, совпадает с полнотой комбинаторных методов распознавания символов, а точности распознавания равняются 99.1 (для SRi) и 99.6 (для И?)-

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

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

« ¡у»

РЬ2(1Ч) = У -—-Р2"'(1-Р2) ' +

V У-—-Р1п1Р2°2(1-Р1-Р2)Н п'—

где Р1 (Р2) - вероятность того, что символ начинается с первой (второй) линии в строке из N символов. Надежное определение второй базовой линии (с вероятностью ошибки, равной 0.999) возможно уже при 6 символах в строке. Частные случаи формирования строк, наличие коротких строк и дефекты сканирования уменьшают надежность определения базовых линий с помощью гистограмм границ символов. Для компенсации этого разумно воспользоваться результатами алгоритмов распознавания символов, в особенности умеющих различать прописные и строчные буквы. Комбинирование распознавания и статистики улучшает надежность определения базовых линий. Найденные базовые линии могут использоваться в качестве дискриминирующего механизма в распознавании символов и отделения знаков препинания от малых компонент связности, являющихся случайным шумом.

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

- скелетное подмножество, содержащее значения растра кластеров в границах скелетного образа вКЕЦв, а)

- расширенное подмножество, содержащее нули в границах расширенного образа СОУЕЩв, Р) 2 ЯКЕЦв, а)

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

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

Рис. 2. Схема системы распознавания

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

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

в работе рассматриваются средства распознавания других атрибутов текста: серифности, жирности.

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

ЗАКЛЮЧЕНИЕ

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

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

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

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

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

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

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

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

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

8. Все приведенные в работе алгоритмы реализованы в виде набора библиотек, входящего в программу распознавания текстов OCR Cognitive Cuneiform® и систему массового ввода структурированных документов ICR Cognitive Forms® различных версий. В этих системах достигается оптимальное соотношение между характеристиками точности распознавания, быстродействия и надежности результатов.

ОСНОВНЫЕ ПОЛОЖЕНИЯ ДИССЕРТАЦИИ ИЗЛОЖЕНЫ В СЛЕДУЮЩИХ РАБОТАХ

1. Арлазаров В.Л., Славин O.A. Алгоритмы распознавания и технологии ввода текстов в ЭВМ. - Информационные технологии и вычислительные системы N 1, 1996, 6 стр. 48-54

2. Богданов К.Е., Славин O.A. Объединение последовательностей объектов распознавания В сб. "Интеллектуальные технологии ввода и обработки информации", 1998, с. 86-96

3. Славин O.A., Подрабинович A.A. Древовидное распознавание нормализованных символов. В сб. "Интеллектуальные технологии ввода и обработки информации", 1998, с. 137-157

4. Славин O.A., Корольков Г.В., Болотин П.В. Методы распознавания грубых объектов. В сб. "Развитие безбумажных технологий в организациях", 1999, с. 290-311

5. Славин O.A. Средства управления базами графических образов символов и их место в системе распознавания. В сб. " Развитие безбумажных технологий в организациях ", 1999, с. 277-289

6. Арлазаров В.Л., Корольков Г.В., Славин O.A. Линейный критерий в задачах OCR. - В сб. " Развитие безбумажных технологий в организациях "1999, с. 17-23

ВВЕДЕНИЕ

ГЛАВА 1. ЗАДАЧИ РАСПОЗНАВАНИЯ. ОБЗОР ИЗВЕСТНЫХ АЛГОРИТМОВ

1.1. Задачи программ распознавания текстов.

1.2. Анализ изображений.

1.3. Методы распознавания отдельных символов

1.4. Распознавание текстов как многокритериальная задача.

1.5. Выводы.

ГЛАВА 2. БАЗОВЫЕ МЕТОДЫ РАСПОЗНАВАНИЯ СИМВОЛОВ

2.1. Характеристики методов распознавания.

2.2. Метод 3x

2.3. Событийный метод.

2.4. Методы наложения.

2.5. Древовидные методы.:.

2.6 Нейронная сеть над образом 16x16.

2.7. Выводы.

ГЛАВА 3. КОМБИНИРОВАННЫЕ МЕТОДЫ РАСПОЗНАВАНИЯ

ПЕЧАТНЫХ И РУКОПЕЧАТНЫХ СИМВОЛОВ

3.1. Распознавание полей рукопечатных почтовых индексов.

3.2 Распознавание рукопечатных полей.

3.3. Распознавание строк печатных текстов.

3.4. Дополнительные алгоритмы сегментации символов.

3.5. Выводы.

ГЛАВА 4. АДАПТИВНЫЕ АЛГОРИТМЫ РАСПОЗНАВАНИЯ СТРОК И СТРАНИЦ.

4.1. Базовые линии и линейный критерий.

4.2. Многопроходная схема с обучением.

4.3. Распознавание атрибутов текста.

4.4. Выводы.

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

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

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

С точки зрения пользователя персонального компьютера распознавание текстов представляет собой процесс, симметричный распечатке документа, уравнивающий электронные документы и их твердые копии. Произвольный документ, содержащий текстовую информацию, может быть преобразован после сканирования и распознавания в электронный документ, подлежащий дальнейшей обработке в текстовых процессорах точно так же, как и вновь созданный документ. Преимуществом для пользователя является выигрыш времени по сравнению с ручной набивкой документа и его версткой для документа сложной структуры. Типами распознаваемых документов могут служить машинописные страницы, страницы книг, журналов и газет, твердые копии электронных документов, произведенные печатающими устройствами различных систем, распечатки факсов. Также могут быть распознаны цифровые изображения, такие как принятые компьютером факсы и копии экрана. Другими словами, распознавание необходимо всем пользователям персональных компьютеров, которые сталкиваются с текстовой информацией на бумажных носителях. Учитывая неуклонное возрастание числа персональных компьютеров и сканирующих устройств [39,81,83,85], становится очевидной потребность в программах распознавания текстов.

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

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

Задачи распознавания образов широко и давно известны. В 1932 году инженером В.Е.Агаповым была разработана машина, предназначенная для ввода цифр в счетное устройство [37] методам наложений на систему эталонов. В работе [38] автор ссылается на Jacob Rabinow, начавшего исследования по оптическому распознаванию в 1940 году. Большое число известных работ [8-11,31,35] исследуют решения задачи распознавания как задачи классификации. Этот этап накопления большого числа подходов к распознаванию изображений, включающих вопросы оптимального обучения и классификации, характеризуется автономностью исследований по отношению к общей проблеме ввода текстового документа в компьютер.

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

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

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

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

Задачей диссертации является выработка критериев качества распознавания, разработка методов построения целостной и полнофункциональной системы ввода документов и системном рассмотрении всего возникающего цикла проблем. Задача качественного распознавания в системах ввода документов различна в зависимости от предназначения системы. В программах распознавания отсканированных текстов (OCR) главной целевой функцией является минимизация общего числа ошибок, быстродействие имеет важное, но не первостепенное значение. Системы массового ввода большого числа печатных и рукопечатных документов (ICR) 6 имеют следующий критерий оптимальности: надежность распознавания, понимаемая как умение разбивать распознанные результаты на подмножества, не требующие вмешательства человека, и подмножества, нуждающиеся в проверке операторами, причем вероятность ошибки в первом подмножестве близка к нулю, а доля второго подмножества минимальна. Иногда скорость функционирования комплексов ввода большого числа структурированных документов также является предметом оптимизации для обеспечения прохождения отсканированного и распознанного текста в общей системе документооборота. Разумеется, есть различия и в содержимом текстов, предназначенных для систем ICR и OCR. Структурированные документы могут содержать рукописный текст более сложный для распознавания, но, в то же время, такие документы обладают достаточно стандартизованным геометрическим устройством, облегчающим нахождение границ символов, алфавит рукописных символов, как правило, ограничен (например, не требуется различение заглавных и строчных букв), поля структурированных документов часто могут быть сопоставлены со словарями ограниченного объема. Отсканированные страницы, распознаваемые программами OCR, не предполагают известных заранее ограничений структуры страницы, наличия или отсутствия иллюстраций или таблиц, размеров и типов шрифтов, алфавита символов. От программ OCR ожидается не только качественное распознавание символов, но и сохранение типов шрифтов и структуры страницы. В то же время, в силу структурных сложностей программы распознавания текстов OCR не распознают рукописные символы.

Если потребности в адаптации к устройству отсканированной страницы у OCR и систем массового ввода структурированных документов существенно различны, то адаптивность в распознавании символов весьма сходна. Как печатные, так и рукописные символы после оцифровки с различными характеристиками сканирования могут искажаться. Естественными деформациями сканирования являются случайное зашумление образов, перекос изображения, изменение толщин линий в символах и, в меньшей степени, масштабирование. Не менее естественным искажением, приводящим к значительно большим трудностям, является нарушение топологической структуры образов, приводящее к рассыпанию и склеиванию символов, что затрудняет сегментацию символов, то есть нахождение их границ. Сегментация рассыпанных и склеенных символов, имеющих окружением случайный фоновый шум, является неизбежным этапом любой системы распознавания отсканированных документов. Комбинаторные алгоритмы сегментации символов предполагают появление 7 несимволов [40], то есть случайно сформированных образов, начертание которых не совпадает с начертанием допустимых символов, что приводит к потребности механизма отделения символов от несимволов.

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

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

Теоретические и алгоритмические исследования механизмов распознавания различного уровня позволили добиться существенного улучшения качества ввода документов в известных системах OCR Cognitive Tiger®, OCR Cognitive Cuneiform® и ICR Cognitive Forms®.

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

OCR Cognitive Cuneiform® является омнифонтовой независимой от шрифта программой распознавания печатных текстов, не имеющей обучения. 8

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

ICR Cognitive Forms® представляет собой систему массового ввода структурированных документов, содержащих как печатную (платежные поручения), так и рукописную (пенсионные анкеты) информацию. Используется в подсистемах ввода бумажных документов в проектах архивации и финансового документооборота. Призвана ускорить ввод с бумажных носителей и повысить надежность вводимой текстовой информации. Содержит компоненты распознавания рукописных и печатных символов с различными схемами сегментации и средства самообучения.

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

4.4. Выводы

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

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

125

ЗАКЛЮЧЕНИЕ

В работе получены следующие результаты.

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

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

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

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

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

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

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

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

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

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

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

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

Все приведенные в работе алгоритмы реализованы в виде набора библиотек, входящего в программу распознавания текстов OCR Cognitive Cuneiform® и систему массового ввода структурированных документов ICR Cognitive Forms® различных версий. В этих системах достигается оптимальное соотношение между потребностями точности распознавания, быстродействия и надежности результатов.

128

Автор выражает глубокую благодарность своему руководителю B.JI. Арлазарову и своим коллегам и специалистам в области распознавания A.A. Леману, А.Б. Талалаю, И.А.Фараджеву, М.А. Кронроду, В.В. Постникову, A.B. Мисюреву, Н.Е. Бузикашвили, В.В. Троянкеру, И.Б. Чернышовой, П.А. Куратову, A.A. Михайлову, Б.А. Шахвердиеву, Н.В. Котовичу, А.Я. Подрабиновичу, A.A. Подрабиновичу и A.C. Логинову, без которых эта работа не состоялась бы.

1. Анисимов Б.В., Курганов В.Д., Злобин В.К. Распознавание и цифровая обработка информации. М.: Высшая школа, 1983 -295 с.

2. Шеннон К. Работы по теории информации и кибернетике. М.:ИЛ, 1963, 829 с.

3. Загоруйко Н.Г. Методы распознавания и их применение. М.: Сов. Радио, 1972,-206 с.

4. Фу К. Последовательные методы в распознавании образов и обучения машин. М.: Наука, 1971 с. 256

5. Калеватых А.В., Павлов Б.А. Обзор современных методов автоматизированного анализа изображений // Автоматика и телемеханика. 1995. Вып. 9, с. 3-21.

6. Дуда Р., Харт П. Распознавание образов и анализ сцен. М.: Мир, 1976. 511 с.

7. Террайен Ч.У., Куатъери Т.Ф., Даджон Д.Е. Алгоритмы анализа изображений, основанные на статистических моделях // ТИИЭР. 1986. Т. 74. № 4. с. 4-25.

8. Себастиан Г. Процессы принятия решения при распознавании образов. Киев., 1965 151 с.

9. Промахова И.М., Коростелев А.П. Об одном классе вероятностных рекуррентных алгоритмов распознавания. ВНИИСИ, препринт. М.: 1984,-45 с.

10. McCulloch W.S. and Pitts W., "A logical Calculus of Ideas Immanent in Nervous Activity", Bull. Mathematical Biophysics, Vol. 5, 1943, pp. 115133.

11. Розенблатт Ф. Принципы нейр о динамики. Перцептроны и теория механизмов мозга. М.: Мир. 1965, 480 с.

12. Минский М, Пейперт С. Перцептроны. М.: Мир, 1971 - 264 с.

13. Hopfield J.J., "Neural Networks and Physical Systems with Emergent Collective Computational Abilities", in Proc. National Academy of Sciences, USA 79, 1982, pp. 2554-2558.

14. Lippmann R.P., "An Introduction to Computing with Neural Nets", IEEE ASSP Magazine, Vol.4, No.2, Apr. 1987, pp. 4-22.

15. Haykin S., Neural Networks: A Comprehensive Foundation, MacMillan College Publishing Co., New York, 1994.

16. Mohiuddin К., Mao J., "A Comparative Study of Different Classifiers for Handprinted Character Recognition", in Pattern Recognition in Practice1301., E.S. Gelsema and L.N. Kanal, eds. Elsevier Science, 1994, pp. 437448.

17. Сип Y. Le et al., "Back-Propagation Applied to Handwritten Zip Code Recognition", Neural Computation, Vol. 1, 1989, pp. 541-551.

18. Westall J.M., Narasimha M.S. Vertex directed segmentation of handwritten numerals. Pattern Recognition Vol. 26, 10 (1993), pp. 14731486

19. Wang J., Jean J. Segmentation of merged characters by neural networks shortest path. Pattern Recognition 27,Vol. 5 (1994), pp. 649-658

20. Кохонен Т. Ассоциативная память. М.: Мир, 1980, 239 с.

21. Нильсон Н., Обучающиеся машины. М.: Мир, 1967, 180 с.

22. Ларичев О.И., Мошкович Е.М. Качественные методы принятия решений. М.: Наука, 1996, 208 с.

23. Roy В. Methodologie Multycritere d'Aide a la Decision. Paris: Economoica, 1985

24. Saieki H. Allocation of Importance. An axiom system // Journal of Mathematical Psychology. 1972, №9 - p. 55-65

25. Подиновский В.В. Об относительной важности критериев в многокритериальных задачах принятия решений//Проблемы и процедуры принятия решений при многих критериях. М.: ВНИИСИ, 1982.- с.21-42

26. Ладензон А.Б., Литвак Б.Г. Принцип упорядоченных критериев для многокритериальных альтернатив// Известия АН СССР. Техн. Кибернетика. 1988. - №6 - с. 49-54

27. Ларичев О.И., Зуев Ю.А., Гнеденко Л.С. Метод построения классификации проектов прикладных научных исследований и разработок/Шерспективное планирование проектов прикладных научных исследований и разработок. М.: Наука, 1974.-с.28-57

28. Журавлев Ю. И. Корректные алгебры над множествами некорректных (эвристических) алгоритмов I, II, III.- Кибернетика, 1977, № 4, с. 14 21, № 6, с. 21 - 27; 191 ., № 2, с. 35 - 43.

29. Журавлев Ю. И. Непараметрические задачи распознавания образов. Кибернетика, 1976, № 6. с. 93 - 103.131

30. Журавлев Ю. Н. Об алгебраическом подходе к решению задач распознавания или классификации,- Пробл. кибернетики, 1978, № 33, 1978, с. 5-67.

31. Журавлев Ю. И. Экстремальные алгоритмы в математических моделях для задач распознавания и классификации,- Докл. АН СССР, 1976, 231, №3, с. 212-214.

32. Журавлев Ю. И., Камилов М. М., Туляганов Ш. Э. Алгоритмы вычисления оценок и их применения,-Ташкент: Фан, 1974, 114 с.

33. Журавлев Ю. И., Никифоров А. В. Алгоритмы распознавания, основанные на вычислении оценок,- Кибернетика, № 3, 1972. с. 1 -11.

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

35. Васильев В.И. Распознающие системы. Киев: Наукова думка, 1983, 422 с.

36. Саплин М.С. Фотоэлектрическое устройство, воспринимающее цифровые печатные знаки. Электрон. Вычисл. Машины, 1960, № 1, с. 110-123

37. Braun E.W. Applying Neural Networks to Character Recognition. http://www.ccs.neu.edu/home/feneric/charrecnn.html

38. Громов Г.P. Национальные информационные ресурсы: проблемы промышленной эксплуатации. М.: Наука, 1984, 240 с.

39. Арлазаров В.Л., Славин O.A. Алгоритмы распознавания и технологии ввода текстов в ЭВМ. Информационные технологии и вычислительные системы № 1, 1996, 6, стр. 48-54

40. Гоппа В. Д. Введение в алгебраическую теорию информации. М.: Наука, 1995, 112 с.

41. Браверман Э.М., Мучник И.Б. Структурные методы обработки эмпирических данных. М.: Наука, 1983, 464 с.

42. Мисюрёв A.B. Использование искусственных нейронных сетей для распознавания рукопечатных символов. В сб. "Интеллектуальные технологии ввода и обработки информации", 1998, с.122-127

43. Арлазаров В.Л., Астахов А.Д., Троянкер В.В., Котович Н. В. Адаптивное распознавание символов. В сб. "Интеллектуальные технологии ввода и обработки информации", 1998, с. 39-56

44. Pao Y-H, Adaptive pattern recognition and neural network, Addison-Wesley, 1989132

45. Бахвалов H.С. Численные методы. Т.1. Анализ, алгебра, обыкновенные дифференциальные уравнения. М.: Наука, 1975, 623 с.

46. Классификация и кластер // Сборник. М.: Мир, 1980, 390 с.

47. БеллманР. Динамическое программирование. М.: ИЛ, 1960, 400 с.

48. Постников М.М. Аналитическая геометрия. М.: Наука, 1973, 752 с.

49. Постников В.В. Разработка методов наложения формы на графическое изображение документа. В сб. "Интеллектуальные технологии ввода и обработки информации", 1998, с. 157-163

50. Haigh S. Optical Character Recognition (OCR) as a Digitization Technology, Network Notes #37 ISSN 1201-4338, Information Technologiy Services national Library of Canada, 1996 http://www.nlc-bnc.ca/publications/netnotes/notes37.htm

51. Portegys Т.Е. A Search Technique for pattern Recognition Using Relative Distances. // IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 17, № 9, 1995, pp. 910-912

52. Kazem T., Borsack J., Condit A. Evaluation of Model-Based Retrieval Effectiveness with OCR Text // ACM Transactions on Information System, Vol. 14, № 1, 1996, pp. 64-93

53. Li Y., Lopresti D., Nagy G., TomkinsA. Validation of Image Defect Models for Optical Character Recognition // IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 18, № 2, 1996, pp. 99-108

54. Shi H., Pavlidis T. Font Recognition and Contextual Processing for More Accurate Text Recognition // IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol 17, № gt 1997, pp. 39-44

55. Rosha J., Pavlidis T. Character Recognition Without Segmentation // IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 17, № 9, 1995, pp. 903-909

56. Фу К. Структурные методы в распознавании образов. М.: Наука, 1977, 320 с.

57. Lam L., Suen С.Y. An Evaluation of Parallel Thinning Algorithms for Character Recognition // IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 17, № 9, 1995, pp. 914-919

58. Szmurlo M. Boundary normalization for recognition of non-touching non-degraded characters // The 4th International Conference on Document Analysis and Recognition (ICDAR 97), August 1997, Ulm, Germany, pp. 463-466

59. Wakahaga T., Odaka K. Adaptive Normalization of Handwritten Characters Using Global/Local Affine Transformation // IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 20, № 12, 1998 pp. 28-33133

60. Alimoglu F., Alpaydin E. Combining Multiple representations and Classifiers for Pen-based Digit Recognition // The 4th International Conference on Document Analysis and Recognition (ICDAR 97), August 1997, Ulm, Germany, pp. 637-640

61. Kim J., Seo K, Chung К A Systematic Approach to Classifier Selection on Combining Multiple Classifiers for Handwritten Digit Recognition // IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 20, № 12, 1998, pp. 459-462

62. Славин О.А., Корольков Г.В., Болотин П.В. Методы распознавания грубых объектов. В сб. "Развитие безбумажных технологий в организациях", 1999, с. 290-311

63. Славин О.А., Подрабинович А.А. Древовидное распознавание нормализованных символов. В сб. "Интеллектуальные технологии ввода и обработки информации", 1998, с. 137-157

64. Славин О.А. Средства управления базами графических образов символов и их место в системе распознавания. В сб. " Развитие безбумажных технологий в организациях ", 1999, с. 277-289

65. Krishnamoorthy М., Nagy G., Seth S., Viswanathan M. "Syntactic segmentation and labeling of digitized pages from technical journals," IEEE Journal on Pattern Analysis and Machine Intelligence, Vol. 15, no.7, 1993, p.737-747

66. Плискин E.JI. Контроль и корректировка при распознавании форм. В сб. "Интеллектуальные технологии ввода и обработки информации", 1998, с. 128-136

67. Богданов К.Е., Славин О.А. Объединение последовательностей объектов распознавания В сб. "Интеллектуальные технологии ввода и обработки информации", 1998, с. 86-96

68. Арлазаров B.JJ., Корольков Г.В., Славин О.А. Линейный критерий в задачах OCR. В сб. " Развитие безбумажных технологий в организациях ", 1999, с. 17-23

69. Sneath Р.Н.А., R.R. Sokal. Numerical Taxonomy. W.H. Freeman, 1973. San Francisco.

70. Ward J. H. Hierarchical grouping to optimize an objective function. Journal of the American Statistical Association, 1963 Vol.58, 236.

71. Tryon R.C. Cluster Analysis // Ann. Arb., Edw. Brathers. 1939

72. Горелик А.Л., Гуревич И.Б., Скрипкин В.А. Современное состояние проблемы распознавания. М.: «Радио и связь», 1985, 160 с.

73. Impedovo S., Ottaviano L., Occhinegro S. Optical character recognition a survey. Character and Handprinting Recognition, Expanding Frontiers. Word Scientific Publishing, River Edge, N.J., pp. 1-24134

74. White J.M., Rohrer G.D. Image Thresholding for Optical Character Recognition and Other Applications Requiring Character Image Extraction, IBMRD(27), № 4, 1983, pp. 400-411.

75. Логинов А. С. О некоторой схеме распознавания на основе признакового подобия объектов. Алгоритм построения дерева распознавания. В сб. " Развитие безбумажных технологий в организациях ", 1999, с. 127-136

76. Постников В.В., Михайлов А.А. Алгоритмы сегментации рукопечатных символов. В сб. " Развитие безбумажных технологий в организациях ", 1999, с. 179-188

77. White Н. Learning in artificial networks: A statistical perspective // Neural Computation, № 1, 1989, pp. 425-464

78. RichardM.D., Lippman, R.P. Neural Network Classifiers estimate Bayesian a posteriori probabilities. // Neural Computation, № 3, 1991, pp. 461-483

79. Kickpatrick D.G. Efficient computation of continuous skeletons. In Proceeding of the 20th Annual IEEE Symposium on FOCS, 1979, pp. 18-27

80. Острейковский B.A. Информатика. M.: Высш. Школа, 2000, 511 с.

81. Бербышев Е.М. Технологии ММХ. Новые возможности процессоров Р5 и Р6. М: Диалог-Мифи, 234 с.

82. Джексон Т. Intel: взгляд изнутри. М.: Лори, 1998, 346 с.