Исследование методов распознавания текстов

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Курсовая работа

Исследование методов распознавания текстов

Содержание

Введение

1) Задачи распознания текста

2) Оптическое распознание символов

3) История

4) Текущее состояние технологий оптического текста

Выводы

Заключение

Список использованной литературы

Введение

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

Актуальность такой работы подтверждается последними публикациями. Даже общепризнанные лидеры среди пакетов оптического распознавания символов (optical character recognition, OCR), как раз и предназначенные для решения задач подобного рода, не справляются с распознаванием обычного факсимильного сообщения, несмотря на то, что текст можно легко прочесть визуально [1].

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

Существует несколько причин, обуславливающих низкое качество факсимильных документов. Среди них -- низкое разрешение факс-аппарата. В то время как распознаваемые документы обычно сканируются с разрешением не ниже 300 dpi, факсимильный документ обычно имеет разрешение 200x100 dpi (режим «Standard»), и лишь при улучшенном качестве передачи (режим «Fine») 200x200 dpi. Разное разрешение по вертикали и по горизонтали приводит к тому, что высота изображения документа в пикселях оказывается в два раза меньше ожидаемой, а символы оказываются «сплюснутыми» и в таком виде практически не распознаются. При низком разрешении символы имеют У малую высоту в пикселях, поэтому случайные изменения нескольких пикселей приводят не только к значительным изменениям формы символа, но часто меняют его топологию. Значительные искажения изображений документов возникают вследствие низкого качества исходной твердой копии, причиной которого является старение, копирование, использование морально устаревших печатающих устройств. Все эти дефекты не позволяют применять для распознавания символов многие известные методы, в частности метод сравнения с эталоном, структурные методы. Не являются информативными топологические признаки, признаки формы и многие другие признаки, традиционно считающиеся эффективными при распознавании изображений. Низкое разрешение и плохое качество приводят к ошибкам на этапе предварительной обработки, в частности, к пропуску строк. Обычной является ситуация, когда вполне читаемый текст распознается с ошибками почти в каждом слове вследствие неэффективности процедур распознавания и орфографической коррекции.

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

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

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

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

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

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

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

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

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

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

В связи с поставленной целью в диссертации решаются следующие основные задачи:

* разработка методов и алгоритмов сегментации строк и слов текста по растровому изображению документа;

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

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

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

* оценка трудоемкости и определение возможности распараллеливания разработанных алгоритмов.

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

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

Научная новизна. В результате проведенных в работе исследований

* разработан новый метод сегментации объектов бинарного изображения, работающий «сверху вниз», основанный на комбинации операций фильтрации и заливки, сегментирующий строки в условиях помех, характерных для факсимильных сообщений, таких как слипание символов и появление на тексте сплошной вертикальной полосы;

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

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

* разработан комбинированный метод классификации изображений символов, учитывающий высоту и вертикальное положение символа относительно базовой линии строки текста и использующий нейросетевой подход к распознаванию, обеспечивающий высокое (9599%) качество распознавания изолированных символов и пар;

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

* разработан метод орфографической коррекции результатов нейросетевого распознавания слов, отличающийся от существующего метода на основе алгоритма Витерби тем, что на каждом временном шаге ищутся N наиболее вероятных корректных слов среди всех, которые могут быть порождены на этом шаге, что повышает правильность контекстного распознавания на 10-25% слов по сравнению с известным методом;

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

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

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

распознавание текст оптический

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

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

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

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



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



Рисунок 1. Объединение нескольких букв в одну компоненту связанности.

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

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

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

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

Рисунок 3. Архитектура классификатора

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



Рисунок 4. Простой классификатор

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

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

Для оценки эффективности разработанного алгоритма было проведено сравнение с двумя существующими системами OCR. Это бесплатная open-source система CuneiForm v12 и коммерческая система ABBYY FineReader 10 Professional Edition. К сожалению, для оценки эффективности работы систем распознавания, обычно используются наборы символов, подготовленных иностранными специалистами, либо наборы, собранные авторами и не опубликованные в открытом доступе. Так, например, оценивая эффективность работы алгоритмов ABBYY FineReader автор использовал базы данных CEDAR, NIST, CENPARMI а также сканированные анкеты ЕГЭ. Поскольку данные базы содержат английские и/или рукописные символы, они не могут быть использованы для оценки эффективности выполнения НИР по теме «разработка алгоритма распознавания печатных кириллических символов». Сравнение производилось на образцах с разрешением 96 dpi и 180 dpi. В сравнении участвовал текст, состоящий из 300 слов, набранных шрифтами Arial 14pt и Times New Roman 14pt. Текст разрешением 96 dpi был создан на компьютере непосредственно в виде графического файла. Для теста с разрешением 180 dpi текст был распечатан на лазерном принтере, а затем сканирован с указанным разрешением. Фрагмент использованного текста приведен на рис. 5.

Рисунок 5. Фрагмент текста, использованного для тестирования систем распознавания.

Результаты сравнения для 96 dpi представлены в таблице 1.



Таблица 1. Результаты распознавания текста разрешением 96 dpi. Результаты сравнения для текста с разрешением 180 dpi представлены в таблице 2.

Таблица 2. Результаты распознавания текста разрешением 180 dpi.

Лучшие результаты распознавания для 96 dpi можно объяснить тем, что текущая конфигурация системы была обучена на шрифтах Times New Roman 14pt и Arial 14pt при разрешающей способности 96 dpi. Можно ожидать улучшения результатов для этого текста при добавлении в систему простых классификаторов, обученных распознавать шрифты такого размеа.Суммарно, из 1200 слов было распознано:

* разработанным алгоритмом: 1180 слов (98,33%);

* системой с открытыми кодами CuneiForm: 597 слов (49,75%);

* коммерческой системой ABBYY FineReader: 1200 слов (100%).

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

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

Оптическое распознавание символов

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

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

История

В 1929 году Густав Таушек получил патент на метод оптического распознавания текста в Германии, после чего за ним последовал Гендель, получив патент на свой метод в США в 1933. В 1935 году Таушек также получил патент США на свой метод. Машина Таушека представляла собой механическое устройство, которое использовало шаблоны и фотодетектор.

В 1950 году Дэвид Х. Шепард, криптоаналитик из агентства безопасности вооружённых сил Соединённых Штатов, проанализировав задачу преобразования печатных сообщений в машинный язык для обработки компьютером, построил машину, решающую данную задачу. После того как он получил патент США, он сообщил об этом в «Вашингтон Дэйли Ньюз» (27 апреля 1951) и в «Нью-Йорк Таймс» (26 декабря 1953). Затем Шепард основал компанию, разрабатывающую интеллектуальные машины, которая вскоре выпустила первые в мире коммерческие системы оптического распознавания символов.

Первая коммерческая система была установлена на «Ридерс Дайджест» в 1955 году. Вторая система была продана компании «Стэндарт Ойл» для чтения кредитных карт для работы с чеками. Другие системы, поставляемые компанией Шепарда, были проданы в конце 1950-х годов, в том числе сканер страниц для национальных воздушных сил США, предназначенный для чтения и передачи по телетайпу машинописных сообщений. IBM позже получила лицензию на использование патентов Шепарда.

Примерно в 1965 году «Ридерс Дайджест» и «Ар-Си-Эй» начали сотрудничество с целью создать машину для чтения документов, использующую оптическое распознавание текста, предназначенную для оцифровки серийных номеров купонов «Ридерс Дайджест», вернувшихся из рекламных объявлений. Для печати на документах барабанным принтером «Ар-Си-Эй» был использован специальный шрифт OCR-A. Машина для чтения документов работала непосредственно с компьютером RCA 301 (один из первых массивных компьютеров). Скорость работы машины была 1500 документов в минуту: она проверяла каждый документ, исключая те, которые она не смогла обработать правильно.

Почтовая служба Соединённых Штатов с 1965 года для сортировки почты использует машины, работающие по принципу оптического распознавания текста, созданные на основе технологий, разработанных исследователем Яковом Рабиновым. В Европе первой организацией, использующей машины с оптическим распознаванием текста, был британский почтамт. Почта Канады использует системы оптического распознавания символов с 1971 года. На первом этапе в центре сортировки системы оптического распознавания символов считывают имя и адрес получателя и печатают на конверте штрих-код. Он наносится специальными чернилами, которые отчётливо видимы в ультрафиолетовом свете. Это делается, чтобы избежать путаницы с полем адреса, заполненным человеком, которое может быть в любом месте на конверте.

В 1974 году Рэй Курцвейл создал компанию «Курцвейл Компьютер Продактс», и начал работать над развитием первой системы оптического распознавания символов, способной распознать текст, напечатанный любым шрифтом. Курцвейл считал, что лучшее применение этой технологии -- создание машины чтения для слепых, которая позволила бы слепым людям иметь компьютер, умеющий читать текст вслух. Данное устройство требовало изобретения сразу двух технологий -- ПЗС планшетного сканера и синтезатора, преобразующего текст в речь. Конечный продукт был представлен 13 января 1976 во время пресс-конференции, возглавляемой Курцвейлом и руководителями национальной федерации слепых.

В 1978 году компания «Курцвейл Компьютер Продактс» начала продажи коммерческой версии компьютерной программы оптического распознавания символов. Два года спустя Курцвейл продал свою компанию корпорации «Ксерокс», которая были заинтересована в дальнейшей коммерциализации систем распознавания текста. «Курцвейл Компьютер Продактс» стала дочерней компанией «Ксерокс», известной как «Скансофт».

Текущее состояние технологии оптического распознавания текста

Точное распознавание латинских символов в печатном тексте в настоящее время возможно только если доступны чёткие изображения, такие как сканированные печатные документы. Точность при такой постановке задачи превышает 99%, абсолютная точность может быть достигнута только путем последующего редактирования человеком. Проблемы распознавания рукописного «печатного» и стандартного рукописного текста, а также печатных текстов других форматов (особенно с очень большим числом символов) в настоящее время являются предметом активных исследований.

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

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

Он-лайн системы для распознавания рукописного текста «на лету» в последнее время стали широко известны в качестве коммерческих продуктов. Алгоритмы таких устройств используют тот факт, что порядок, скорость и направление отдельных участков линий ввода известны. Кроме того, пользователь научится использовать только конкретные формы письма. Эти методы не могут быть использованы в программном обеспечении, которое использует сканированные бумажные документы, поэтому проблема распознавания рукописного «печатного» текста по-прежнему остается открытой. На изображениях с рукописным «печатным» текстом без артефактов может быть достигнута точность в 80 % -- 90 %, но с такой точностью изображение будет преобразовано с десятками ошибок на странице. Такая технология может быть полезна лишь в очень ограниченном числе приложений.

Ещё одной широко исследуемой проблемой является распознавание рукописного текста. На данный момент достигнутая точность даже ниже, чем для рукописного «печатного» текста. Более высокие показатели могут быть достигнуты только с использованием контекстной и грамматической информации. Например, в процессе распознания искать целые слова в словаре легче, чем пытаться проанализировать отдельные символы из текста. Знание грамматики языка может также помочь определить, является ли слово глаголом или существительным. Формы отдельных рукописных символов иногда могут не содержать достаточно информации, чтобы точно (более 98 %) распознать весь рукописный текст.

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

Выводы

1. Быстрое развитие многопроцессорных вычислительных машин и параллельного программирования обусловлено принятием абстрактной модели параллельной машины, такой же удобной и общей, как модель последовательной машины фон Неймана. Такой идеализированной моделью параллельной машины является мультикомпьютер, состоящий из нескольких компьютеров фон Неймана, связанных друг с другом с помощью коммуникационной среды. В рамках этой модели возможны различные архитектуры параллельных компьютеров, например, MIMD архитектура с распределенной памятью и мультипроцессор с разделяемой памятью. При программировании сложных задач для выполнения на параллельной машине необходима абстрактная модель программирования. Возможны модели программирования на основе понятий «задачи» и «каналы», принципа передачи сообщений, принципа разделяемой памяти и параллелизма данных. Взаимосвязь элементов данных на этапе коррекции способствуют формализации процесса разработки параллельных программ и позволяют придерживаться определенной методики, согласно которой процесс разработки параллельного алгоритма состоит из четырех стадий: декомпозиция (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. Произведены оценки трудоемкости основных этапов обработки факсимильных сообщений, определены пути распараллеливания этих этапов в части декомпозиции соответствующих алгоритмов и установления взаимосвязей элементов соответствующих данных. Это является определяющей стадией разработки параллельных алгоритмов распознавания текста и позволяет на этой основе строить модели параллельных вычислений для постановки задач по обработке факсимильных сообщений на многопроцессорных системах, в том числе специализированных.

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

Список использованной литературы

1. Богданов В., Ахметов К. Системы распознавания текстов в офисе. // Компьютер-пресс -- 1999 №3, с.40-42.

2. Павлидис Т. Алгоритмы машинной графики и обработки изображений. М:, Радио и связь, 1986

3. Shani U. Filling Regions in Binary Raster Images -- a Graph-theoretic Approach. // SIGGRAPH'80, pp 321-327.

4. Merrill R.D. Representation of Contours and Regions for Efficient Computer Search. // CACM, 16 (1973), pp. 69-82.

5. Pavlidis T. Filling Algorithms for Raster Graphics. // CGIP, 10 (1979), pp. 126141.

6. Lieberman H. How to Color in a Coloring Book. // SIGGRAPH'78, Atlanta, Georgia, (August, 1978), pp. 111-116. Published by ACM.

7. Smith A.R. Tint Fill. // SIGGRAPH'79, Chicago, Illinois, (August, 1979), pp. 276-283. Published by ACM.

8. Abramatic J. F., Silverman L.M. Non-Stationary Linear Restoration of Noisy Images. // Proc. 18th IEEE Decision and Control Conference, vol. 1, (December 1979) pp. 92-99.

9. Nagao M., Matsuyama T. Edge Preserving Smoothing. // Proc. Fourth Intern. Joint Conf. on Pattern Recognition (November, 1978), pp. 518-520.

10. Abdou I.E., Pratt W.K. Quantitative Design and Evaluation of Enhancement/Thresholding Edge Detectors. // IEEE Proceedings, 67 (1979), pp 753-763.

11. Квасников В.П., Дзюбаненко А.В. Улучшение визуального качества цифрового изображения путем поэлементного преобразования // Авиационно-космическая техника и технология 2009 г., 8, стр. 200-204

12. Арлазаров В.Л., Куратов П.А., Славин О.А. Распознавание строк печатных текстов // Сб. трудов ИСА РАН «Методы и средства работы с документами». -- М.: Эдиториал УРСС, 2000. -- С. 31-51.

13. Проект СПбГУ Открытый код: распознавание текстовых изображений [Электронный ресурс] -- Режим доступа: ocr.apmath.spbu.ru/

14. Багрова И. А., Грицай А. А., Сорокин С. В., Пономарев С. А., Сытник Д. А. Выбор признаков для распознавания печатных кириллических символов // Вестник Тверского Государственного Университета 2010 г., 28, стр. 59-73

15. The concept of a linguistic variable and its application to approximate reasoning, Information Sciences, 8, 199-249; 9, 43-80.

16. Melin P., Urias J., Solano D., Soto M., Lopez M., Castillo O., Voice Recognition with Neural Networks, Type-2 Fuzzy Logic and Genetic Algorithms. Engineering Letters, 13:2, 2006.

17. Панфилов С. А. Методы и программный комплекс моделирования алгоритмов управления нелинейными динамическими системами на основе мягких вычислений. Диссертация на соискание ученой степени кандидата технических наук. Тверь, 2005.

Размещено на Allbest.ru