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

Актуальность исследования.

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

Общая задача обработки изображений распадается в связи с её широким применением на весьма широкий класс задач. Одной из таких задач является задача распознавания текста. За последние 10 лет достигнут существенный прогресс в распознавании стандартизированного (машинописного) текста. Разработаны технологии и программные продукты, позволяющие достаточно уверенно (с высокой степенью точности) распознавать машинописный текст., наиболее известными из которых являются ABBYY FineReader OCR [1], OmniPage [2], Readlris [3], CuneiForm [4]. Иначе обстоит дело с методами, технологиями и программными комплексами для распознавания рукописного текста. Так, существующие программные продукты (например, ABBYY FormReader [5]) предназначены, в основном, для ввода специальных форм или анкет, заполненных от руки.

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

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

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

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

Цели и задачи диссертации.

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

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

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

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

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

Цели и задачи исследования.

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

1. Разработка общей схемы распознавания рукописных и машинописных текстов на изображении.

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

3. Развитие и разработка методов распознавания изображения простейших геометрических объектов (прямых, окружностей и, т.п.).

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

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

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

Методы исследования.

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

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

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

1.1 алгоритмы распознавания прямых и окружностей без использования пространства «аккумулятора» для хранения параметров двойственного исходному изображению;

1.2 быстрый алгоритм поиска окружностей на изображении на основе метода инверсий;

1.3 алгоритм моделирования и распознавания рукописных символов алгебраическими кривыми;

1.4 алгоритм выделения и классификации алгебраических кривых на изображении;

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

1.6 алгоритм сегментации рукописных и печатных текстов на основе анализа диаграмм Вороного;

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

2 Для разработанных алгоритмов приведены теоретические обоснования.

3 Доказана лемма о структуре обобщённой диаграммы Вороного.

4 Разработанные алгоритмы объединены в пакет прикладных программ для распознавания рукописных и печатных текстов.

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

Получены свидетельства об официальной регистрации программ: «распознавание примитивов на изображении» [8], «определение параметров центральных кривых второго порядка на изображении» [9].

Публикации.

— По. результатам проведённых исследований ипрактических разработок опубликовано 10 работ.

Апробация работы.

Результаты исследований докладывались на: УП-й Международной научно-методической конференции «Информатика: проблемы, методология, технологии» (г. Воронеж, 8−9 февраля 2007 г.), УШ-й Международной научно-методической конференции «Информатика: проблемы, методология, технологии» (г. Воронеж, 7−8 февраля 2008 г.), ХУ1-Й Международной конференции «Математика. Компьютер. Образование — 2009» (г. Пущино, 1924 января 2009), ЕХ-й Международной научно-методической конференции «Информатика: проблемы, методология, технологии» (г. Воронеж, 12−13 февраля 2009 г.), Х-й Международной научно-методической конференции «Информатика: проблемы, методология, технологии» (г. Воронеж, 11−12 февраля 2010 г.).

Личный вклад автора.

Все основные работы, выносимые на защиту, получены автором самостоятельно.

Структура и объём диссертации.

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

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

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

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

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

В главе 5 разработаны алгоритмы выделения строк, слов и символов рукописных и печатных текстов, использующие диаграмму Вороного. Развит новый алгоритм определения угла наклона рукописных и печатных текстов. Доказана лемма о связи точечной и обобщённой диаграмм Вороного.

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

Положёния, выносимые на защиту.

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

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

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

4. Реализован алгоритм выделения и классификации алгебраических кривых на изображении.

5. Исследовано прменение дескрипторов функций длины хорды к распознаванию рукописных символов русского языка.

6. Разработан алгоритм сегментации рукописных и печатных текстов на основе анализа диаграмм Вороного.

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

8. Алгоритмы объединены в пакет программных оболочек.

Выводы.

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

2. В § 6.4 предложен алгоритм коррекции результатов распознавания изображения по словарю на основе оценки величины ошибки распознавания символов слова.

Заключение

.

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

1) предварительная обработка изображения;

2) выделение строк, слов и символов текста;

3) распознавание символов;

5) коррекция результатов распознавания.

Изображение текста, подлежащее распознаванию, как правило, получают путём оптического сканирования некоторого носителя. Результатом данной операции является полутоновое или цветное изображение. Применяемые в настоящей работе алгоритмы распознавания текста используют чёрно-белое изображение, где чёрным цветом кодируются объекты, а белым — фон изображения, что делает необходимым этап предварительной обработки изображения. Для решения данной проблемы используются методы Киттлера и Сауволы пороговой классификации, описанные в разделе § 2.1, позволяющие преобразовать полутоновое изображение в чёрно-белое. Метод локальной пороговой классификации Сауволы неявно использует так называемую «медианную фильтрацию», заключающуюся в усреднении значений ••яркости^' соседних точек, что позволяет устранить с изображения помехи, связанные с дискретизацией сигнала в устройствах оптического сканирования. Чёрно-белое изображение, полученное методом пороговой классификации, может содержать специфические помехи типа «соль-перец», характеризуещиеся появлением изолированных белых или чёрных точек. Устранение шума «соль-перец» на изображении осуществляется посредством последовательного применения операций бинарной морфологии.

Важным этапом процесса распознавания текста является сегментация, заключающаяся в выделении на изображении отдельных строк, слов и символов текста. В настоящей работе сегментация текста осуществляется на основе анализа диаграммы Вороного центров масс связных компонентов чёрно-белого изображения, соответствующих символам текста. Диаграмма Вороного используется для осуществления быстрого поиска «смежных» символов. Так, сложность алгоритма построения данной диаграммы составляет 0(NlogN), а для произвольного компонента вычислительная сложность алгоритма поиска смежных с ним компонентов — 0(1). В разделе § 5.5 предложен собственный алгоритм сегментации текста, основанный на анализе диаграмм Вороного. Выделение строк, символов и слов текста позволяет решить задачу форматирования результатов распознавания, т. е. добавления переноса строк и пробелов в выходном тексте. Кроме того, информация о структуре слов используется для коррекции результатов распознавания по словарю.

Распознавание символов осуществляется путём анализа их внешних и внутренних замкнутых границ, способы выделения и кодирования которых описаны в разделе § 2.5. Полученные границы символа используются для построения вектора признаков, инвариантных к аффинным преобразованиям. В качестве векторов признаков используются дескрипторы Фурье и дескрипторы функций длины хорды, описание которых дано соответственно в разделах § 4.3 и § 4.4. С целью уменьшения размерности векторов признаков символов и повышения надёжности распознавания текста, в настоящей работе применяются метод главных компонент и метод линейного дискриминантного анализа (раздел § 4.5), позволяющие получить проекцию вектора признаков на пространство меньшей размерности, причём линейный' оператор проектирования задаётся на основе данных обучающего-набора: Применение,^ данных методов позволяет классифицировать символ поиском минимального евклидова расстояния между проекциями вектора признаков распознаваемого символа и проекцией вектора признаков символа из обучающего набора.

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

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

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

Потенциальная область применения полученных в настоящей работе алгоритмов и программной оболочки достаточно широка, вследствие применения методов распознавания символов на основе выделения векторов признаков, устойчивых к аффинным преобразованиям изображения, что является шагом вперёд по сравнению с существующими программными продуктам распознавания текстов, использующих методы распознавания на основе шаблонов. Стоит отметить, что на момент написания настоящей работы существует единственная коммерческая система с закрытым кодом распознавания изолированных рукописных символов и печатных текстов на основе выделения признаков — Kadmos OCR/ICR [92].

Положения, выносимые на защиту.

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

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

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

4. Реализован алгоритм выделения и классификации алгебраических кривых на изображении.

5. Исследовано прменение дескрипторов функций длины хорды к распознаванию рукописных символов русского языка.

6. Разработан алгоритм сегментации рукописных и печатных текстов на основе анализа диаграмм Вороного.

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

8. Алгоритмы объединены в пакет программных оболочек.