Содержание к диссертации
Введение
1. Аналитический обзор методов и средств распознавания изображений факсимильных документов низкого качества 10
1.1 Анализ применимости существующих программных средств для распознавания факсимильных документов низкого качества 10
1.2 Обзор и классификация задач обработки изображений 14
Выводы 37
2. Разработка методов и алгоритмов предобработки и анализа изображений документов 39
2.1 Анализ применимости существующих методов сегментации для решения задачи выделения текстовых строк в условиях помех 39
2.2 Разработка метода сегментации объектов бинарных изображений, устойчивого к помехам 47
2.3 Экспериментальное исследование характеристик разработанного метода. Сравнение с методами «снизу вверх» и комбинированным 54
2.4 Выработка критерия для выделения слов строки 61
2.5 Разработка метода идентификации типов бланков факсимильных сообщений 63
Выводы 67
3. Разработка и исследование метода распознавания символов факсимильных документов 70
3.1 Разработка системы накопления обучающих данных и создание на ее основе наборов изображений символов факсимильных сообщений 70
3.2 Разработка комбинированного нейросетевого метода классификации изображений символов 74
3.2.1 Разработка нейросетевой системы распознавания символов 74
3.2.2 Способ извлечения информации, содержащейся в выходном векторе персептрона : 86
3.2.3 Способ предварительной классификации изображений печатных символов 89
3.2.4 Выбор признакового пространства для классификации изображений символов 91
3.3 Исследование качества распознавания символов с применением разработанного метода 95
Выводы 102
4. Разработка и исследование метода орфографической коррекции результатов посимвольного распознавания 105
4.1 Разработка метода орфографической коррекции 105
4.2 Исследование разработанного метода распознавания и сравнение качества распознавания с методом на основе алгоритма Витерби 116
4.3 Обработка англо-русского словаря и создание базы данных для распознавания англоязычных текстов с применением разработанного метода 120
Выводы 124
5. Анализ трудоемкости основных этапов и раскрытие возможностей для распараллеливания 126
5.1 Модели параллельных машин и методика разработки параллельных программ 126
5.2 Анализ трудоемкости основных этапов задачи распознавания факсимильных документов и раскрытие возможностей их распараллеливания 134
Выводы 144
Заключение 147
Список литературы 149
Приложение
- Разработка метода сегментации объектов бинарных изображений, устойчивого к помехам
- Выработка критерия для выделения слов строки
- Разработка комбинированного нейросетевого метода классификации изображений символов
- Исследование разработанного метода распознавания и сравнение качества распознавания с методом на основе алгоритма Витерби
Введение к работе
В настоящее время вместе с расширяющимся применением Internet и электронной почты остается широко распространенной такая форма обмена документами, как факсимильная связь. Она будет использоваться во всем мире еще долгое время, поскольку обладает следующими достоинствами: простота использования, очевидность, дешевизна, использование при передаче твердой копии (электронная версия документа не всегда есть в наличии). Однако отличительной чертой такого способа связи является передача изображения документа, сформированного с помощью сканирующего устройства факс-аппарата. Вследствие этого, применение факсимильной связи создает большие неудобства при учете, хранении и обработке входящей корреспонденции, особенно если велик ее объем. Очевидны также неудобства хранения электронных версий документа в виде изображений из-за большого объема файла и недоступности содержимого для автоматической обработки. Обработка документов может включать отбор документов по ключевым словам, определение тематики документа путем нахождения слов, характерных для какой-либо предметной области, автоматическое индексирование и перевод, а также классификацию документов согласно принадлежности организации-отправителю. Для решения всех этих задач необходим доступный текст документа.
Актуальность такой работы подтверждается последними публикациями. Даже общепризнанные лидеры среди пакетов оптического распознавания символов (optical character recognition, OCR), как раз и предназначенные для решения задач подобного рода, не справляются с распознаванием обычного факсимильного сообщения, несмотря на то, что текст можно легко прочесть визуально [1]. Существующие в настоящее время системы распознавания не всегда позволяют эффективно распознавать изображения печатных текстов низкого качества, характерные для документов, полученных по факсу.
Существует несколько причин, обуславливающих низкое качество факсимильных документов. Среди них — низкое разрешение факс-аппарата. В то время как распознаваемые документы обычно сканируются с разрешением не ниже 300 dpi, факсимильный документ обычно имеет разрешение 200x100 dpi (режим «Standard»), и лишь при улучшенном качестве передачи (режим «Fine») 200x200 dpi. Разное разрешение по вертикали и по горизонтали приводит к тому, что высота изображения документа в пикселях оказывается в два раза меньше ожидаемой, а символы оказываются «сплюснутыми» и в таком виде практически не распознаются. При низком разрешении символы имеют малую высоту в пикселях, поэтому случайные изменения нескольких пикселей приводят не только к значительным изменениям формы символа, но часто меняют его топологию. Значительные искажения изображений документов возникают вследствие низкого качества исходной твердой копии, причиной которого является старение, копирование, использование морально устаревших печатающих устройств. Все эти дефекты не позволяют применять для распознавания символов многие известные методы, в частности метод сравнения с эталоном, структурные методы. Не являются информативными топологические признаки, признаки формы и многие другие признаки, традиционно считающиеся эффективными при распознавании изображений. Низкое разрешение и плохое качество приводят к ошибкам на этапе предварительной обработки, в частности, к пропуску строк. Обычной является ситуация, когда вполне читаемый текст распознается с ошибками почти в каждом слове вследствие неэффективности процедур распознавания и орфографической коррекции.
Характерными при факсимильной передаче являются такие помехи, как перекос документа, а также появление тонкой вертикальной линии, вызванное дефектом факс-аппарата и приводящее к соединению символов соседних строк. Это делает не эффективными описанные в последних публикациях методы сегментации строк и вызывает необходимость их усовершенствования или разработки новых.
Другим источником плохого качества документа являются помехи в линии связи. Для передачи через коммутируемую телефонную сеть графическая информация кодируется по строкам пикселей. Это приводит к тому, что кратковременная помеха искажает всю строку.
Для определения организации-отправителя система обработки и распознавания факсимильных документов должна использовать алгоритмы распознавания, адаптированные для обнаружения и идентификации уникальных для каждой организации признаков документа, а для обработки текста необходимы алгоритмы распознавания печатных символов низкого качества, что характерно для документов, полученных по факсу, а также алгоритмы определения тематики документа, использующие поиск по словарям. Кроме того, в условиях плохого качества электронной копии, для правильного распознавания слов не достаточно только лишь посимвольного распознавания, поскольку в этом случае ошибки неизбежны, не зависимо от алгоритма распознавания. Необходима подсистема проверки орфографии слов, взаимодействующая с распознающей системой с целью подбора наиболее близкого слова. Однако при анализе текста, полученного программой FineReader, видно, что в результате ошибок распознавания текст состоит из слов, представляющих собой бессмысленные наборы букв, хотя на изображении данного документа присутствуют разрешенные в языке слова.
Кроме того, в современных комплексных системах мониторинга и обработки информации возникает задача высокоскоростной обработки интенсивных информационных потоков и отбора конкретных факсимильных сообщений, что требует построения специализированных многопроцессорных вычислительных систем.
Одним из способов повышения производительности обработки может быть отбор факсимильных документов с помощью распознавания типа бланка по эмблеме или логотипу, без распознавания текстового содержимого. Однако эта функция, как правило, вообще не поддерживается существующими средствами обработки изображений документов.
Существующие коммерческие пакеты оптического распознавания символов предназначены исключительно для работы на персональной ЭВМ. Они не доступны для усовершенствования, разработки новых систем и новых реализаций.
С учетом вышесказанного, имеется необходимость разработки методов и средств распознавания, пригодных для построения перспективных современных средств обработки факсимильных сообщений, используемых при создании новых программных пакетов, которые могут быть реализованы на различных платформах, и при построении специализированных комплексных систем мониторинга и обработки информации.
Разработке и исследованию методов и средств качественного распознавания факсимильных сообщений для современных систем обработки информации посвящена данная диссертационная работа.
Целью работы является разработка и исследование методов, алгоритмов и программ распознавания текста факсимильных сообщений, обеспечивающих высокое качество распознавания и возможность использования их при построении современных специализированных систем обработки потоков факсимильных сообщений.
В связи с поставленной целью в диссертации решаются следующие основные задачи:
- разработка методов и алгоритмов сегментации строк и слов текста по растровому изображению документа;
- автоматизированное создание баз данных реальных изображений символов для обучения и оценки систем распознавания; - разработка и исследование алгоритмов вычисления признаков изолированных печатных символов и методов распознавания с помощью искусственных нейронных сетей;
- разработка и исследование метода орфографической коррекции результатов распознавания символов в словах на примере английского языка;
- оценка трудоемкости и определение возможности распараллеливания разработанных алгоритмов.
Предмет исследования. В работе исследуются особенности изображений печатных текстов и символов латинского алфавита на примере базы данных реальных факсимильных сообщений (более 400), исследуется эффективность использования неиросетевого подхода к распознаванию изолированных символов, а также применимость теории скрытых Марковских моделей для поиска наиболее правдоподобного орфографически-корректного слова. Кроме того, исследуется возможность распараллеливания разработанных алгоритмов на этапах декомпозиции и установления взаимосвязей элементов данных.
В рамках исследования используются методы теории распознавания образов, обработки изображений, нейросетевые методы распознавания, основы теории скрытых Марковских моделей, теории вычислительных систем.
Научная новизна. В результате проведенных в диссертации исследований
- разработан новый метод сегментации объектов бинарного изображения, работающий «сверху вниз», основанный на комбинации операций фильтрации и заливки, сегментирующий строки в условиях помех, характерных для факсимильных сообщений, таких как слипание символов и появление на тексте сплошной вертикальной полосы;
- разработан метод идентификации типов бланков факсимильных сообщений, позволяющий производить на его основе предварительную классификацию входящих документов в системах обработки потоков факсимильных сообщений;
- разработана система накопления обучающих данных, обучения и оценки достигнутого качества распознавания на различных наборах данных, упрощающая разработку новых систем распознавания;
- разработан комбинированный метод классификации изображений символов, учитывающий высоту и вертикальное положение символа относительно базовой линии строки текста и использующий нейросетевой подход к распознаванию, обеспечивающий высокое (95-99%) качество распознавания изолированных символов и пар; - получен способ извлечения полной информации, содержащейся в выходном векторе персептрона за счет использования не только максимального его элемента, но и близких к нему по значению, в качестве набора классификационных решений с разной степенью достоверности, повышающий качество последующего контекстного распознавания символов;
- разработан метод орфографической коррекции результатов нейросетевого распознавания слов, отличающийся от существующего метода на основе алгоритма Витерби тем, что на каждом временном шаге ищутся N наиболее вероятных корректных слов среди всех, которые могут быть порождены на этом шаге, что повышает правильность контекстного распознавания на 10-25% слов по сравнению с известным методом;
- намечены пути параллельной обработки и распознавания изображения текста в части декомпозиции и установления взаимосвязей элементов данных наиболее трудоемких алгоритмов распознавания, что раскрывает возможности для распараллеливания и позволяет на этой основе создавать высокопроизводительные системы обработки потоков факсимильных сообщений.
Практическая ценность. На основе теоретических результатов, полученных в данной работе, была создана действующая комплексная система обработки и распознавания факсимильных сообщений, позволяющая распознавать изображения текстовых документов низкого качества, что является практически полезным при использовании факсимильной связи. Кроме этого, показанная возможность распараллеливания разработанных алгоритмов позволяет строить специализированные системы, обрабатывающие большие объемы изображений текстовых документов, что обеспечивает возможность автоматической обработки содержимого, решает проблемы их учета, хранения и распечатки. Разработанная система обучения и оценки классификаторов обеспечивает простоту накопления и организации обучающих данных, минимизирует время разработки новых алгоритмов вычисления признаков и методов распознавания и может быть использована при проектировании нейросетевых систем, а также в учебном процессе в рамках курсов по искусственному интеллекту и распознаванию образов.
Достоверность основных положений работы и применимость предложенных методов подтверждается теоретически и результатами экспериментов по распознаванию текстов. В работе получены и выносятся на защиту следующие новые основные результаты:
1) метод сегментации объектов бинарных изображений в условиях помех, характерных для факсимильных сообщений, таких как тонкая вертикальная полоса, слипания и перекрытия символов;
2) способ извлечения полной информации, содержащейся в выходном векторе персептрона, повышающий качество последующего контекстного распознавания символов
3) метод орфографической коррекции, повышающий количество правильно распознанных слов.
Использование результатов работы. Результаты диссертации использованы в хоздоговорной НИР №16105 «Исследование путей программной реализации системы предварительной обработки и распознавания печатных символов факсимильных сообщений», выполненной по заказу в/ч 11135, а также в учебном процессе на кафедре БИТ.
Апробация работы. Основные результаты работы докладывались на XXXIII региональной молодежной школе-конференции «Проблемы теоретической и прикладной математики» (Екатеринбург: ИММ УРО РАН, 2002 г.), на всероссийских научно-технических конференциях с международным участием «Компьютерные технологии в инженерной и управленческой деятельности» (Таганрог, 1997, 1998 гг.), на трех научно-практических семинарах «Информационная безопасность - юг России», на международной научно-практической конференции «Компьютерные технологии в науке, производстве, социальных и экономических процессах» (Новочеркасск, 2000 г.), а также на всероссийских научных конференциях студентов и аспирантов «Техническая кибернетика, радиоэлектроника и системы управления», проводившихся в ТРТУ в 1997, 1998 и 2000 гг.
Публикации. По теме диссертации опубликовано 13 печатных работ, в которых отражены основные результаты диссертации.
Структура и объем работы. Диссертация включает введение, обзорную главу, четыре тематических раздела, заключение, список литературы и приложение.
Разработка метода сегментации объектов бинарных изображений, устойчивого к помехам
Рассмотрев существующие методы, приходим к выводу о том, что все они имеют общий недостаток, состоящий в следующем. Методы используют критерий, позволяющий объединять несвязные области пикселей и относить их к одному объекту, однако отсутствуют критерии, разделяющие некоторую связную область на части, принадлежащие соседним объектам.
Разработанный новый метод сегментации лишен этого недостатка и включает в себя способ сегментации, выбор параметров и алгоритм разделения областей.
Новый метод сегментации можно формально представить следующей последовательностью операций: 1. Фильтрация Алгоритм разделения областей вызывается для каждого элемента dt.
Способ сегментации, лишенный недостатка существующих методов (пп. 1-3 последовательности операций метода), может быть получен, если провести аналогию со зрительным процессом, происходящим при рассмотрении страницы документа на увеличенном расстоянии. При этом текст может быть неразличим, однако текстовые блоки, строки и слова будут выделяться как размытые прямоугольники. Особенно отчетливо строки будут видны, если направить взгляд под малым углом (менее 45) к плоскости страницы, вдоль строк, как бы вскользь. При этом возможные помехи, соединяющие строки, будут сливаться с фоном. Предлагается в качестве критерия, позволяющего разделять соединенные области, использовать среднюю яркость окрестности пикселя. Изменения размера и формы окрестности соответствуют степени удаления страницы и углу зрения, а порог яркости позволяет отфильтровать помехи, соединяющие соседние области. Изменяя эти параметры можно локализовать любые области, необходимые при распознавании текста, такие как текстовые блоки, строки и слова. Для этого необходимо получить на основе исходного новое изображение, в котором яркость каждого пикселя равна средней яркости окрестности соответствующего пикселя на исходном изображении. Такой результат может быть получен посредством фильтрации исходного бинарного изображения. Новое изображение будет относиться к классу полутоновых, при этом области, яркость которых превышает порог, могут быть выделены путем применения операции заливки. Выделенные области используются как маска, указывающая расположение искомых объектов на исходном изображении.
При этом важным является выбор параметров, таких как форма окрестности и порог яркости, которые зависят от характера выделяемых областей. В Приложении 2 приведены результаты применения данного метода при различных параметрах, необходимых для сегментации текстовых блоков, строк и слов. Эти параметры были выбраны экспериментально, однако следует показать теоретически, что они существуют и получить приблизительные их значения. Рассмотрим выбор параметров метода на примере выделения строк текста.
Теоретическое обоснование значений параметров состоит в следующем. Величина порога яркости определяется средним количеством черных пикселей в областях документа, где расположены текстовые строки, исключая разделяющий их фон. С помощью построения проекции на вертикальную ось изображения текстового блока без перекоса, можно подсчитать среднее значение гистограммы. Для строки это экспериментально полученное значение составляет 18%. При яркости пикселей объекта 255, соответствующая средняя яркость равна 46. Для получения локальной средней яркости предлагается использовать операцию медианной фильтрации, вычисляющую среднюю яркость внутри прямоугольной окрестности. Ширина прямоугольника W должна быть достаточно большой, чтобы сгладить перепады яркости, вызванные пробелами между словами, но и достаточно малой, чтобы не захватить соседние строки в случае перекоса. При возможном максимальном перекосе 5 и интервале между строками 10 пикселей, расстояние по горизонтали между соседними строками составляет =10/tg5, т.е. =114 пикселей. Очевидно, этого расстояния с запасом достаточно, чтобы сгладить пробелы между словами. При ширине блока 1300 пикселей это составляет 8,7%. По вертикали высокая степень сглаживания не требуется, поэтому высота окрестности Н устанавливается малой (1-5 пикселей). Примем высоту 3 пикселя. Ширина вертикальной полосы как характерной помехи факсимильных сообщений составляет 1-2 пикселя. При слипании символов помехой будут считаться более крупные группы пикселей до 20, окруженные слева и справа белым пространством между строками. При размере окрестности 75x3 средняя яркость такой группы составит 23. Таким образом, порог Р выбирается из диапазона 23-46.
Экспериментальные результаты, полученные с применением фильтрации к изображению текстовых строк с присутствием вертикальных полос, показаны на рис. 2.5. Для выполнения фильтрации использованы параметры, обоснованные теоретически. Установлены ширина и высота прямоугольной окрестности W=\0\ и Н=Ъ, а порог Р=30. Серым цветом показана область, в которой после фильтрации яркость превышала порог. Можно видеть, что в промежутке между строками сплошные вертикальные полосы не покрыты полученными областями. Однако надстрочные и подстрочные элементы некоторых букв также лежат вне этих областей. Это значит, что для получения изображения строки не достаточно взять фрагмент исходного изображения, попадающий в выделенную область, поскольку некоторые буквы окажутся обрезанными (рис. 2.6), что приведет к ошибкам распознавания.
Выработка критерия для выделения слов строки
В этом пункте разрабатываются два критерия нахождения слов на изображении строки. Оба они используют величину белых промежутков между соседними символами. Если расстояние между соседними символами большое, то это место считается пробелом между словами. Основная трудность разработки алгоритма разделения слов состоит в том, чтобы формально определить понятие «большое расстояние».
Самый простой способ — это выбрать некоторую пороговую величину и считать пробелом расстояние между символами, большее этой величины. Чтобы такой формальный критерий работал на шрифтах разного размера, эта величина выбирается пропорциональной высоте строки. Примеры результатов разбиения по такому методу приведены на рис.2.14. а), б). На этом рисунке серым фоном выделены фрагменты строки, принятые алгоритмом за отдельные слова.
В обоих случаях пороговая величина выбиралась в 4 раза меньшей высоты строки. Можно видеть, что для пропорционального шрифта с символами различной ширины (рис.2.14., б) пороговую величину следует выбирать еще меньше, а для шрифта с символами одинаковой ширины (рис.2.14., а) — больше.
Это объясняется тем, что в случае а) ширина пробела по отношению к высоте строки меньше, чем в случае б). Таким образом, по высоте строки в общем случае нельзя определить величину пробела между словами. Если в пределах одной строки интервал между символами слова не меняется, то можно выбрать пороговую величину следующим способом. Для одной строки строится гистограмма расстояний между соседними символами, на которой можно обнаружить два максимума. Первый, в точке более близкой к нулю, соответствует интервалу между символами слова, а второй, меньший по величине, интервалу между словами. Пороговую величину можно выбрать в точке впадины между этими максимумами. Однако такой способ не решает проблемы различного интервала между символами слова в пределах строки, например, если в строке встречается слово, напечатанное «в разрядку». Такое слово не будет обнаружено, его символы будут приняты за отдельные слова.
Можно избежать многих ошибок при сегментации слов, если анализировать не всю строку сразу, а только локальный ее фрагмент. Разработанный по этому принципу оригинальный алгоритм показал хорошие результаты, особенно в комбинации с ранее изложенными критериями. Опишем, в чем состоит сущность нового критерия.
Для обнаружения очередного слова вычисляется текущее среднее расстояние между символами Scp, которое сравнивается с расстоянием между следующей парой символов 54 (см. рис.2.15., а). Если где к 1 — некоторый коэффициент, выбираемый экспериментально в интервале (1,4 - 2), то 5 4 считается пробелом между словами, иначе вычисляется следующее среднее расстояние которое сравнивается с S5.
Возможен также другой случай, показанный на рис.2.15., б), когда Scp S4k. Это значит, что промежутки S\, S2, S3 являются пробелами между словами, а 5 4 — промежуток между первой парой символов следующего слова. Результаты работы алгоритма, работающего на основе этих принципов приведены на рис.2.16.
Такой результат был получен при к=2 и минимально допустимой величине пробела между словами равной высоте строки, деленной на 5.
У государственных учреждений и крупных предприятий очень велик объем деловой переписки. В таких условиях остро встает проблема систематизации входящих документов, прежде всего отбор писем, пришедших от каких-то конкретных организаций. Обычно каждая организация имеет свой бланк письма, содержащий неизменную шапку с эмблемой и названием организации, расположенную на странице неизменным образом. Это позволяет еще на этапе предварительной обработки изображения документа, когда не распознана текстовая часть, определить организацию-отправителя [55]. Для решения этой задачи был предложен и опробован оригинальный подход, излагаемый ниже.
Была создана база данных, содержащая уникальные фрагменты изображений фирменных бланков, которые требуется опознавать. Кроме изображения фрагмента, запись базы хранит его исходные координаты.
Для идентификации отправителя конкретного документа достаточно выбрать запись базы данных, содержащую фрагмент изображения, совпадающий наилучшим образом с соответствующим фрагментом данного документа, т.е. с фрагментом, имеющим те же размеры и те же координаты, что указаны в данной записи. Степень соответствия двух фрагментов можно вычислить как обычное Евклидово расстояние. Пусть Gi и G2 — сравниваемые фрагменты изображений. Тогда квадрат Евклидова расстояния G,,G, можно выразить как
Минимальное расстояние Лв, , вычисленное по всем записям базы данных, показывает наилучшее совпадение.
Однако, в реальных условиях этот метод в таком виде не дал бы хороших результатов, поскольку реальные документы при сканировании или передачи по факсу могут быть сдвинуты относительно оригинала. Это повлечет за собой то, что при наложении соответствующего фрагмента, изображения не совместятся, и вычисленное 4G,,G2 будет велико. Чтобы найти истинную степень соответствия с учетом возможного преобразования сдвига, нужно найти такие координаты сдвига хтах, у max, при которых Г) минимально
Разработка комбинированного нейросетевого метода классификации изображений символов
Предлагаемый метод распознавания символов включает в себя предварительную классификацию и окончательное распознавание символов.
Предварительная классификация осуществляется по высоте символов и их положению в строке (пп. 3.2.3.). Окончательное распознавание производится неиросетевым методом по признакам, алгоритм вычисления которых разрабатывается в пп. 3.2.4.
При окончательном распознавании решается проблема слипшихся букв. При сканировании изображения печатного текста часто возникает ситуация, когда два соседних символа слова соединяются вместе, и их бинарное изображение представляет собой один связный объект. Примеры изображений слов, содержащих такие слипшиеся пары символов, приведены на рис.3.3.
В данном примере оказались соединенными следующие пары символов: «an», «rn», «rt», «fi», «rp», «th». При сегментации эти пары воспринимаются как один символ, поскольку представляют собой один связный объект. Чтобы предусмотреть распознавание такого связного объекта именно как пары букв, а не как одной буквы, предлагается создать и обучить отдельные нейронные сети, классифицирующие изображения пар соединенных символов.
Поскольку без распознавания невозможно точно определить, изображена ли одна буква или две соединенных, целесообразно использовать результат распознавания как гипотезу, имеющую степень достоверности. Кроме того, такой подход позволит предлагать несколько возможных решений по классификации образа как изолированного символа и несколько вариантов пар слипшихся букв. В результате возможные ошибки распознавания будут исправлены по контексту символа на последующем этапе орфографической коррекции. Таким же способом можно учесть ошибки классификации символа по высоте и положению в строке, которые также не исключены. Достоверность гипотез окончательной классификации взвешивается результатами предварительной классификации. Таким образом, процесс распознавания символа можно представить в виде структурной схемы взаимодействующих распознающих блоков (рис.3.3.). Согласно предлагаемому методу, строка символов, представленная набором неизвестных изображений, подается на предварительный классификатор. Предварительный классификатор различает три суперкласса: 0 — высокие строчные и прописные буквы; 1 — подстрочные, выступающие вниз буквы; 2 — средние. При подаче на его вход некоторого неизвестного символа данной строки, на выходе, соответствующем суперклассу данного символа, появляется значение, равное 1. На остальных выходах выдаются близкие к 0 значения. Помимо этого, по изображению символа вычисляется вектор признаков, подающийся на нейросети для окончательной классификации. Каждому из 3 суперклассов соответствует пара нейронных сетей типа персептрон: Isolt для распознавания изолированных символов и Соп І для распознавания комбинаций соединенных символов. В результате перемножения выходов сети и предварительного классификатора, образуются высокие степени достоверности гипотез, выдаваемых парой сетей нужного суперкласса и низкие — остальных гипотез.
Введение блока предварительной классификации позволяет распознавать строчные и прописные буквы, имеющие одинаковое начертание. Кроме того, предварительное разделение символов алфавита на три суперкласса упрощает окончательное распознавание за счет уменьшения числа различаемых классов каждым нейросетевым классификатором. С этой же целью пары слипшихся символов выделены в отдельные суперклассы. Такое решение позволяет формировать наборы распознаваемых слипшихся пар символов независимо от остальных суперклассов и без переобучения соответствующих нейросетей.
Блок слияния преобразует выходные векторы нейросетей в списки пар символ, степень достоверности , объединяет их и упорядочивает общий список по убыванию степени достоверности, как показано на рис. 3.4.
Исследование разработанного метода распознавания и сравнение качества распознавания с методом на основе алгоритма Витерби
Задачи коррекции орфографических ошибок наиболее актуальны при вводе или передаче текстовой информации для точного ее отображения. Большинство офисных программ, работающих с текстовой информацией, имеют встроенные механизмы исправления орфографических ошибок. При работе с текстами (в частности, при вводе текста пользователем) могут возникнуть четыре типа орфографических ошибок: замена одного знака другим на той же позиции; одиночные выпадения и вставки знака, приводящие к сдвигу части слова соответственно влево и вправо; одиночная инверсия соседних знаков. Задачу повышения качества распознавания символов можно ставить и решать в такой же постановке [62]. При этом формируется потенциально ошибочное слово, как цепочка букв, соответствующих выделенным изображениям с наибольшей индивидуальной вероятностью, а другие варианты распознавания каждого символа должны быть отброшены. Такая коррекция приводит к тому, что с учетом возможности ошибки в каждой букве, в результате находится большое количество слов, имеющих одинаковую меру близости с ошибочным. Коррекция двух ошибок и более невозможна по этой же причине. Поэтому в диссертации разрабатывается альтернативный метод коррекции, учитывающий варианты распознавания каждой буквы, основанный на теории скрытых Марковских моделей.
Рассмотрим основные понятия теории скрытых марковских моделей и три фундаментальные задачи, которые она ставит. Дискретной цепью Маркова [63] первого порядка называется система, находящаяся в каждый дискретный момент времени t в одном из N состояний s\, s2, ...,S-H, обозначаемом qh причем вероятности перехода в следующий момент времени t+\ в каждое из N состояний определяются только состоянием qt и не зависят от qt.\, qt.2, ..., q\. Формально такая система полностью описывается матрицей А с элементами аф
Такой случайный процесс можно назвать наблюдаемой марковской моделью, поскольку состояние системы как раз и является ее выходом, т.е. соответствует регистрируемому физическому событию. Эта модель является слишком ограниченной и не подходит для решения многих практических задач, поэтому понятие марковской модели было расширено. В новой модели наблюдаемые события являются некоторой вероятностной функцией текущего состояния, т.о. основной процесс оказывается невидимым, скрытым [64-68, 69]. Приведем пример вероятностного процесса извлечения шаров из урн. Пусть имеется N урн, содержащих большое количество шаров, каждый из которых окрашен в один из М цветов. По некоторому вероятностному закону случайно выбирается урна и из нее произвольно извлекается шар, цвет которого записывается как первое наблюдение. Затем выбирается следующая урна по вероятностному правилу, зависящему от номера первой урны, из нее также извлекается шар, цвет которого - второе наблюдение, и т.д. Такой процесс описывается СММ, состояния которой соответствуют выбираемым урнам, а для каждого состояния определены свои вероятности появления каждого из цветов. Множество наблюдаемых символов (в данном примере — множество цветов) обозначается как V={vh v2, ..., v/V/}, а распределение вероятностей их появления в состоянии sj как В=Щ(к)}, где bJ(k) = P[vk\sj\, j=l,...,N; k=l, ..., М. Начальное распределение вероятностей состояний (закон, по которому выбирается первая урна) обозначается через 7C={7C,}:
Наблюдение в момент времени / обозначается Ot, Ot є V. Для применения теории к решению практических задач должны быть решены три следующие проблемы: 1) Какова вероятность появления последовательности наблюдений 0=[0\, Оі, ..., От] для модели Х=(А, В, л)? 2) При заданных X и О, как выбрать цепочку состояний Q=[q\, qi, ..., qr] которая некоторым наилучшим образом соответствует имеющейся последовательности наблюдений OR 3) Каким образом нужно подстроить параметры модели \=(А, В, тс), чтобы вероятность Р[0\ X] была максимальной? Существуют классические способы решения этих задач, вполне приемлемые по вычислительной сложности. Первая задача решается посредством вычисления так называемой прямой переменной а (алгоритм прямого-обратного хода). Это позволяет определить, насколько хорошо данная модель соответствует наблюдениям О, а если имеется несколько моделей, позволяет выбрать из них ту, которая подходит наилучшим образом. Так, если построены модели речевых сигналов для слов, решение задачи 1 позволяет подобрать ту модель, которая соответствует неизвестному произнесенному слову. Для решения второй задачи в работах [70, 71] применен алгоритм Витерби, использующий динамическое программирование и вычисляющий наилучшую цепочку состояний имеющую максимальную вероятность P[Q, О \ X], однако существуют и другие критерии. В третьей задаче применяется процедура переоценки Баума-Уэлча. Цель состоит в том, чтобы так оптимизировать параметры модели X, чтобы она наилучшим образом соответствовала О, называемой обучающей последовательностью, таким образом, создается модель, наиболее близко описывающая наблюдаемый процесс или явление. Рассмотрим классическую формулировку алгоритма Витерби [70, 71] и как он применяется к задаче поиска оптимальной цепочки символов. Пусть имеется последовательность наблюдений задана модель Х=(А, В, тс). 1 Инициализация. На этом шаге вычисляются вероятности того, что в первый момент времени система находится в состоянии і, с учетом появления символа наблюдения 0\. 2 Индукция. Для каждого из возможных состояний в момент времени t вычисляется, из какого состояния в предыдущий момент времени наиболее вероятен переход, с учетом накопленной вероятности д,.\ предыдущего состояния. Запоминается индекс состояния, из которого наиболее вероятен переход. Вычисляется накопленная вероятность 8t каждого из состояний в момент времени t
