В настоящее время вместе с расширяющимся применением Internet и электронной почты остается широко распространенной такая форма обмена документами, как факсимильная связь. Она будет использоваться во всем мире еще долгое время, поскольку обладает следующими достоинствами: простота использования, очевидность, дешевизна, использование при передаче твердой копии (электронная версия документа не всегда есть в наличии). Однако отличительной чертой такого способа связи является передача изображения документа, сформированного с помощью сканирующего устройства факс-аппарата. Вследствие этого, применение факсимильной связи создает большие неудобства при учете, хранении и обработке входящей корреспонденции, особенно если велик ее объем. Очевидны также неудобства хранения электронных версий документа в виде изображений из-за большого объема файла и недоступности содержимого для автоматической обработки. Обработка документов может включать отбор документов по ключевым словам, определение тематики документа путем нахождения слов, характерных для какой-либо предметной области, автоматическое индексирование и перевод, а также классификацию документов согласно принадлежности организации-отправителю. Для решения всех этих задач необходим доступный текст документа.
Актуальность такой работы подтверждается последними публикациями. Даже общепризнанные лидеры среди пакетов оптического распознавания символов (optical character recognition, OCR), как раз и предназначенные для решения задач подобного рода, не справляются с распознаванием обычного факсимильного сообщения, несмотря на то, что текст можно легко прочесть визуально [1]. Существующие в настоящее время системы распознавания не всегда позволяют эффективно распознавать изображения печатных текстов низкого качества, характерные для документов, полученных по факсу.
Существует несколько причин, обуславливающих низкое качество факсимильных документов. Среди них — низкое разрешение факс-аппарата. В то время как распознаваемые документы обычно сканируются с разрешением не ниже 300 dpi, факсимильный документ обычно имеет разрешение 200×100 dpi (режим «Standard»), и лишь при улучшенном качестве передачи (режим «Fine») 200×200 dpi. Разное разрешение по вертикали и по горизонтали приводит к тому, что высота изображения документа в пикселях оказывается в два раза меньше ожидаемой, а символы оказываются «сплюснутыми» и в таком виде практически не распознаются. При низком разрешении символы имеют У малую высоту в пикселях, поэтому случайные изменения нескольких пикселей приводят не только к значительным изменениям формы символа, но часто меняют его топологию. Значительные искажения изображений документов возникают вследствие низкого качества исходной твердой копии, причиной которого является старение, копирование, использование морально устаревших печатающих устройств. Все эти дефекты не позволяют применять для распознавания символов многие известные методы, в частности метод сравнения с эталоном, структурные методы. Не являются информативными топологические признаки, признаки формы и многие другие признаки, традиционно считающиеся эффективными при распознавании изображений. Низкое разрешение и плохое качество приводят к ошибкам на этапе предварительной обработки, в частности, к пропуску строк. Обычной является ситуация, когда вполне читаемый текст распознается с ошибками почти в каждом слове вследствие неэффективности процедур распознавания и орфографической коррекции.
Характерными при факсимильной передаче являются такие помехи, как перекос документа, а также появление тонкой вертикальной линии, вызванное дефектом факс-аппарата и приводящее к соединению символов соседних строк. Это делает не эффективными описанные в последних публикациях методы сегментации строк и вызывает необходимость их усовершенствования или разработки новых.
Другим источником плохого качества документа являются помехи в линии связи. Для передачи через коммутируемую телефонную сеть графическая информация кодируется по строкам пикселей. Это приводит к тому, что кратковременная помеха искажает всю строку.
Для определения организации-отправителя система обработки и распознавания факсимильных документов должна использовать алгоритмы распознавания, адаптированные для обнаружения и идентификации уникальных для каждой организации признаков документа, а для обработки текста необходимы алгоритмы распознавания печатных символов низкого качества, что характерно для документов, полученных по факсу, а также алгоритмы определения тематики документа, использующие поиск по словарям. Кроме того, в условиях плохого качества электронной копии, для правильного распознавания слов не достаточно только лишь посимвольного распознавания, поскольку в этом случае ошибки неизбежны, не зависимо от алгоритма распознавания. Необходима подсистема проверки орфографии слов, взаимодействующая с распознающей системой с целью подбора наиболее близкого слова. Однако при анализе текста, полученного программой.
FineReader, видно, что в результате ошибок распознавания текст состоит из слов, представляющих собой бессмысленные наборы букв, хотя на изображении данного документа присутствуют разрешенные в языке слова.
Кроме того, в современных комплексных системах мониторинга и обработки информации возникает задача высокоскоростной обработки интенсивных информационных потоков и отбора конкретных факсимильных сообщений, что требует построения специализированных многопроцессорных вычислительных систем.
Одним из способов повышения производительности обработки может быть отбор факсимильных документов с помощью распознавания типа бланка по эмблеме или логотипу, без распознавания текстового содержимого. Однако эта функция, как правило, вообще не поддерживается существующими средствами обработки изображений документов.
Существующие коммерческие пакеты оптического распознавания символов предназначены исключительно для работы на персональной ЭВМ. Они не доступны для усовершенствования, разработки новых систем и новых реализаций.
С учетом вышесказанного, имеется необходимость разработки методов и средств распознавания, пригодных для построения перспективных современных средств обработки факсимильных сообщений, используемых при создании новых программных пакетов, которые могут быть реализованы на различных платформах, и при построении специализированных комплексных систем мониторинга и обработки информации.
Разработке и исследованию методов и средств качественного распознавания факсимильных сообщений для современных систем обработки информации посвящена данная диссертационная работа.
Целью работы является разработка и исследование методов, алгоритмов и программ распознавания текста факсимильных сообщений, обеспечивающих высокое качество распознавания и возможность использования их при построении современных специализированных систем обработки потоков факсимильных сообщений.
В связи с поставленной целью в диссертации решаются следующие основные задачи:
— разработка методов и алгоритмов сегментации строк и слов текста по растровому изображению документа;
— автоматизированное создание баз данных реальных изображений символов для обучения и оценки систем распознавания;
— разработка и исследование алгоритмов вычисления признаков изолированных печатных символов и методов распознавания с помощью искусственных нейронных сетей;
— разработка и исследование метода орфографической коррекции результатов распознавания символов в словах на примере английского языка;
— оценка трудоемкости и определение возможности распараллеливания разработанных алгоритмов.
Предмет исследования. В работе исследуются особенности изображений печатных текстов и символов латинского алфавита на примере базы данных реальных факсимильных сообщений (более 400), исследуется эффективность использования нейросетевого подхода к распознаванию изолированных символов, а также применимость теории скрытых Марковских моделей для поиска наиболее правдоподобного орфографически-корректного слова. Кроме того, исследуется возможность распараллеливания разработанных алгоритмов на этапах декомпозиции и установления взаимосвязей элементов данных.
В рамках исследования используются методы теории распознавания образов, обработки изображений, нейросетевые методы распознавания, основы теории скрытых Марковских моделей, теории вычислительных систем.
Научная новизна. В результате проведенных в диссертации исследований.
— разработан новый метод сегментации объектов бинарного изображения, работающий «сверху вниз», основанный на комбинации операций фильтрации и заливки, сегментирующий строки в условиях помех, характерных для факсимильных сообщений, таких как слипание символов и появление на тексте сплошной вертикальной полосы;
— разработан метод идентификации типов бланков факсимильных сообщений, позволяющий производить на его основе предварительную классификацию входящих документов в системах обработки потоков факсимильных сообщений;
— разработана система накопления обучающих данных, обучения и оценки достигнутого качества распознавания на различных наборах данных, упрощающая разработку новых систем распознавания;
— разработан комбинированный метод классификации изображений символов, учитывающий высоту и вертикальное положение символа относительно базовой линии строки текста и использующий нейросетевой подход к распознаванию, обеспечивающий высокое (9599%) качество распознавания изолированных символов и пар;
— получен способ извлечения полной информации, содержащейся в выходном векторе персептрона за счет использования не только максимального его элемента, но и близких к нему по значению, в качестве набора классификационных решений с разной степенью достоверности, повышающий качество последующего контекстного распознавания символов;
— разработан метод орфографической коррекции результатов нейросетевого распознавания слов, отличающийся от существующего метода на основе алгоритма Витерби тем, что на каждом временном шаге ищутся N наиболее вероятных корректных слов среди всех, которые могут быть порождены на этом шаге, что повышает правильность контекстного распознавания на 10−25% слов по сравнению с известным методом;
— намечены пути параллельной обработки и распознавания изображения текста в части декомпозиции и установления взаимосвязей элементов данных наиболее трудоемких алгоритмов распознавания, что раскрывает возможности для распараллеливания и позволяет на этой основе создавать высокопроизводительные системы обработки потоков факсимильных сообщений.
Практическая ценность. На основе теоретических результатов, полученных в данной работе, была создана действующая комплексная система обработки и распознавания факсимильных сообщений, позволяющая распознавать изображения текстовых документов низкого качества, что является практически полезным при использовании факсимильной связи. Кроме этого, показанная возможность распараллеливания разработанных алгоритмов позволяет строить специализированные системы, обрабатывающие большие объемы изображений текстовых документов, что обеспечивает возможность автоматической обработки содержимого, решает проблемы их учета, хранения и распечатки. Разработанная система обучения и оценки классификаторов обеспечивает простоту накопления и организации обучающих данных, минимизирует время разработки новых алгоритмов вычисления признаков и методов распознавания и может быть использована при проектировании нейросетевых систем, а также в учебном процессе в рамках курсов по искусственному интеллекту и распознаванию образов.
Достоверность основных положений работы и применимость предложенных методов подтверждается теоретически и результатами экспериментов по распознаванию текстов.
В работе получены и выносятся на защиту следующие новые основные результаты:
1) метод сегментации объектов бинарных изображений в условиях помех, характерных для факсимильных сообщений, таких как тонкая вертикальная полоса, слипания и перекрытия символов;
2) способ извлечения полной информации, содержащейся в выходном векторе персептрона, повышающий качество последующего контекстного распознавания символов.
3) метод орфографической коррекции, повышающий количество правильно распознанных слов.
Использование результатов работы. Результаты диссертации использованы в хоздоговорной НИР № 16 105 «Исследование путей программной реализации системы предварительной обработки и распознавания печатных символов факсимильных сообщений», выполненной по заказу в/ч 11 135, а также в учебном процессе на кафедре БИТ.
Апробация работы. Основные результаты работы докладывались на XXXIII региональной молодежной школе-конференции «Проблемы теоретической и прикладной математики» (Екатеринбург: ИММ УРО РАН, 2002 г.), на всероссийских научно-технических конференциях с международным участием «Компьютерные технологии в инженерной и управленческой деятельности» (Таганрог, 1997, 1998 гг.), на трех научно-практических семинарах «Информационная безопасность — юг России», на международной научно-практической конференции «Компьютерные технологии в науке, производстве, социальных и экономических процессах» (Новочеркасск, 2000 г.), а также на всероссийских научных конференциях студентов и аспирантов «Техническая кибернетика, радиоэлектроника и системы управления», проводившихся в ТРТУ в 1997, 1998 и 2000 гг.
Публикации. По теме диссертации опубликовано 13 печатных работ, в которых отражены основные результаты диссертации.
Структура и объем работы. Диссертация включает введение, обзорную главу, четыре тематических раздела, заключение, список литературы и приложение.
Выводы.
1. Быстрое развитие многопроцессорных вычислительных машин и параллельного программирования обусловлено принятием абстрактной модели параллельной машины, такой же удобной и общей, как модель последовательной машины фон Неймана. Такой идеализированной моделью параллельной машины является мультикомпьютер, состоящий из нескольких компьютеров фон Неймана, связанных друг с другом с помощью коммуникационной среды. В рамках этой модели возможны различные архитектуры параллельных компьютеров, например, MIMD архитектура с распределенной памятью и мультипроцессор с разделяемой памятью. При программировании сложных задач для выполнения на параллельной машине необходима абстрактная модель программирования. Возможны модели программирования на основе понятий «задачи» и «каналы», принципа передачи сообщений, принципа разделяемой памяти и параллелизма данных. Все они.
Рис. 5.14. Взаимосвязь элементов данных на этапе коррекции способствуют формализации процесса разработки параллельных программ и позволяют придерживаться определенной методики, согласно которой процесс разработки параллельного алгоритма состоит из четырех стадий: декомпозиция (partitioning), взаимосвязь (communication), агломерация (agglomeration), отображение (mapping). На первых двух этапах этой методики раскрываются присущие задаче потенциальные возможности для распараллеливания, определяются простейшие элементы данных и схема их взаимодействия, без привязки к какой-либо конкретной архитектуре, что позволяет в дальнейшем разработать наиболее эффективный алгоритм для любой конкретной системы. В соответствии с вышеизложенным, определение возможности распараллеливания разработанных алгоритмов целесообразно производить согласно этой методике, а именно, в части определяющих стадий декомпозиции и установления взаимосвязей.
2. Как показано в предыдущих разделах, обработка изображения документа производится в три этапа: сегментация (с применением операций фильтрации и заливки), распознавание и орфографическая коррекция. Выделение этих этапов является функциональной декомпозицией и позволяет проектировать три разных подсистемы, оптимизированные под алгоритмы каждого этапа. Произведены оценки трудоемкости алгоритмов, выполняющихся на различных этапах обработки, и даны рекомендации по машинно-зависимым аспектам разработки параллельных алгоритмов.
Экспериментально установлено, что наиболее трудоемким этапом является орфографическая коррекция. Трудоемкость этой операции пропорциональна М log М (М — число одновременно сохраняемых лучших цепочек на каждом шаге). Для достижения достоверности распознавания 98% необходимо установить М= 100, при этом время орфографической коррекции 1 страницы документа составило 24 секунды, а доля этой операции во времени общей обработки составила 66%. Таким образом, данный этап является критичным по времени и нуждается в распараллеливании прежде остальных. Выделено два уровня его распараллеливания. Элементами данных в операции орфографической коррекции могут выступать слова документа, при этом каждое слово обрабатывается независимо, взаимосвязи отсутствуют. При более детальной декомпозиции, в каждой позиции слова элементами данных являются цепочки текущего набора и варианты распознавания текущего символа, между которыми установлены взаимосвязи «каждый с каждым». Для исключения взаимосвязей между задачами на этапе агломерации, рекомендуется дублирование набора цепочек, а варианты распознавания символа из набора распределяются между задачами.
3. Этап нейросетевого распознавания символов занимает 29% общего времени распознавания документа. При нейросетевом распознавании основное время занимают матричные операции, которые наиболее эффективно могут быть реализованы аппаратно. Такие специализированные вычислительные блоки, необходимые для моделирования работы нейросетей, присутствуют в архитектуре многих специализированных процессоров и нейропроцессоров. Таким образом, для ускорения этого этапа рекомендовано включение в систему вспомогательных вычислительных блоков, например, специализированных нейропроцессоров, содержащих аппаратный блок матричных вычислений. Примером нейровычислителя может выступать процессор SYNAPSE фирмы SIEMENSE NIXDORF, отечественный нейропроцессора NeuroMatrix NM6403 и другие.
4. Длительность этапа сегментации составляет 5% общего времени распознавания документа. Раскрыты возможности для распараллеливания основных операций этого этапа — заливки и составления строк. Элементарными единицами данных в операции заливки являются пиксели объекта, а взаимосвязи устанавливаются с 8-ю соседними пикселями. Подчеркнуто, что такие взаимосвязи вызывают необходимость обменов между задачами лишь при обработке пикселей на границах областей. Рассмотрена декомпозиция операции составления строк из упорядоченного набора изображений символов. Показано, что в результате агломерации каждая задача будет независимо формировать элементы строк, а взаимодействия возникнут лишь при объединении фрагментов строки.
ЗАКЛЮЧЕНИЕ
.
В соответствии с поставленными целями, в итоге проведенных исследований и разработок были получены следующие основные научные результаты.
1. Разработан метод сегментации объектов изображений, позволяющий выявить структуру сложных изображений за счет использования подхода «сверху вниз» и комбинации операций фильтрации и заливки, позволяющий правильно сегментировать строки в случаях слипания и перекрытия по вертикали символов соседних строк, а также при появлении на факсимильном документе тонкой вертикальной полосы. При работе с изображениями текстов, изменяя параметры фильтрации, можно сегментировать текстовые блоки на странице, строки внутри текстового блока или слова в строке. При этом данный метод сегментации лишен недостатка коммерческой программы Fine Reader, обнаруживающей две текстовых строки на изображении одной.
2. Реализован метод сегментации строк на изображении документа, использующий подход «снизу вверх» и формирующий строки из набора сегментированных символов текстового блока, упорядоченных по возрастанию их координаты х, менее трудоемкий, и в то же время, позволяющий правильно находить строки в условиях перекоса страницы.
3. Разработан метод идентификации типов бланков факсимильных сообщений по характерному графическому фрагменту (логотипу), позволяющий производить быструю сортировку документов в системах обработки потоков факсимильных сообщений.
4. Разработан комбинированный нейросетевой метод распознавания, включающий предварительную классификацию символов по высоте и положению в строке и окончательное распознавание одиночных символов и слипшихся пар производящееся различными нейросетями, что обеспечивает распознавание строчных и прописных букв сходного начертания, позволяет выбирать оптимальный набор различаемых пар соединенных символов без переобучения соответствующей сети одиночных символов упрощает структуру сетей и обеспечивает качество распознавания до 99,4%.
5. Предложен способ извлечения полной информации, содержащейся в выходном векторе персептрона за счет использования не только максимального его элемента, но и близких к нему по значению, в качестве набора классификационных решений с разной степенью достоверности, что повышает качество последующего контекстного распознавания символов.
6. Разработан метод орфографической коррекции результатов нейросетевого распознавания символов. В отличие от метода на основе алгоритма Витерби, в данном методе при переборе вариантов распознавания текущего символа ищется N лучших цепочек символов среди всех, которые могут быть порождены этими вариантами, что повышает качество контекстного распознавания символов.
7. Произведены оценки трудоемкости основных этапов обработки факсимильных сообщений, определены пути распараллеливания этих этапов в части декомпозиции соответствующих алгоритмов и установления взаимосвязей элементов соответствующих данных. Это является определяющей стадией разработки параллельных алгоритмов распознавания текста и позволяет на этой основе строить модели параллельных вычислений для постановки задач по обработке факсимильных сообщений на многопроцессорных системах, в том числе специализированных.
В результате проведенных практических разработок была создана действующая комплексная система обработки и распознавания факсимильных документов, сравнимая по качеству распознавания с известными коммерческими системами оптического распознавания текста. Модули системы выполняют специализированные функции, такие как распознавание типа бланка, сегментация строк и слов изображения текста, распознавание символов, орфографическая коррекция.
