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

На правах рукописи 004Ы

Сорокин Андрей Игоревич

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

05.13.17 - теоретические основы информатики

Автореферат

диссертации на соискание ученой степени кандидата физико-математических наук

- 2 ЛЕН 2010

Воронеж-2010

004615034

Работа выполнена в Воронежском государственном университете

Научный руководитель: доктор физико-математических наук

профессор Запрягаев Сергей Александрович

Официальные оппоненты: доктор физико-математических наук,

профессор Горбунов Вячеслав Алексеевич.

доктор физико-математических наук, профессор Нечаев Юрий Борисович.

Ведущая организация: Воронежский государственный технический

университет

Защита состоится «24» ноября 2010 г. в 15— часов на заседании диссертационного совета Д 212.038.20 при Воронежском государственном университете по адресу: 394006, Воронеж, Университетская пл. д. 1, ВГУ, ауд. 335.

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

Автореферат разослан «22» октября 2010 г.

Ученый секретарь

диссертационного совета Д 212.038.20

Общая характеристика работы

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

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

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

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

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

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

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

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

1. Разработка алгоритмов распознавания изображения на основе синтеза символов из простейших геометрических объектов.

2. Построение алгоритмов распознавания рукописных символов и текстов на основе методов, развитых для машинописных текстов.

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

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

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

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

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

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

1 В работе впервые разработаны:

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

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

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

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

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

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

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

3 Доказана лемма о структурных элементах, используемых для фильтрации «скелета» изображения.

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

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

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

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

Соответствие диссертации паспорту научной специальности Указанная область исследования соответствует формуле специальности 05.13.17 - «Теоретические основы информатики» (физико-математические науки), а именно:

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

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

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

По результатам проведённых исследований и практических разработок опубликовано 10 работ. Из них 1 в журнале Вестник Воронежского госуниверситета серия «Системный анализ и информационные технологии», рекомендованном ВАК для публикации материалов диссертации. Диссертационная работа содержит результаты, полученные соискателем, опубликованные в совместных статьях.

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

Результаты исследований докладывались на: VII-й Международной научно-методической конференции «Информатика: проблемы, методология, технологии» (г. Воронеж, 8-9 февраля 2007 г.), VTII-й Международной научно-методической конференции «Информатика: проблемы, методология, технологии» (г. Воронеж, 7-8 февраля 2008 г.), XVI-й Международной конференции «Математика. Компьютер. Образование - 2009» (г. Пущино, 19-24 января 2009), IX-й Международной научно-методической конференции «Информатика: проблемы, методология, технологии» (г. Воронеж, 12-13 февраля 2009 г.), Х-й Международной научно-методической конференции «Информатика: проблемы, методология, технологии» (г. Воронеж, 11-12 февраля 2010 г.)

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

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

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

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

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

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

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

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

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

Содержание диссертации

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

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

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

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

Цифровое полутоновое изображение, полученное оптическим сканированием, задаётся дискретными значениями уровней яркости (обычно от 0 до 255) каждого из пикселей, так называемыми «уровнями серого». Так как для идентификации объекта требуется точное соотнесение пикселя объекту или фону, полутоновое изображение предварительно преобразуется в чёрно-белое для однозначной классификации пикселей. Для осуществления данной процедуры в диссертационной работе исследованы следующие методы пороговой классификации:

• метод глобальный пороговой классификации (ГПК)

• метод локальной пороговой классификации первого типа (ЛПК1)2;

• метод локальной пороговой классификации второго типа (ЛПК2)3.

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

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

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

1 Kittler J. Minimum Error Thresholding Pattern Recognition / J. Kittler, J. Illingworth // Pattern Recogn. - 1986. -Vol. 19.-P. 41-47

2 Niblack W. An Introduction to Digital Image Processing / W. Niblack. - Prentice Hall, 1986. - P. 115-116

3 Sauvola J. Adaptive Document Image Binarization / J. Sauvola, M. Pietikakinen // Pattern Recognition. - 2000. -Vol. 33.-P. 225-236

Изображение, полученное в результате пороговой классификации, содержит в общем случае различного рода помехи. Один из самых распространённых типов помех - «salt and pepper», заключается в ошибке классификации «чёрных» и «белых» пикселей. Ошибки данного типа в настоящей работе устраняются применением к полученному чёрно-белому изображению группы операций бинарной морфологии.

Форма пиксельного изображения объекта имеет в общем случае набор линий некоторой толщины. В то время как для идентификации формы достаточно однопиксельного представления таких дискретных линий, формирующих «скелет» изображения. Принято считать, что «скелет» обладает «толщиной линий» в 1 пиксель, проходит через «середину» исходного изображения, равноудалён от точек границы и сохраняет связность объекта. В настоящей работе для получения однопиксельного «скелета» монохромного изображения используется метод утонынения линии Холта4. В настоящей работе установлено, что в результате применения алгоритма утоныпения возможно появление «паразитных» элементов на скелете изображения, что приводит к уменьшению точности классификации объекта. С целью устранения такого рода помех из «скелета» изображения в работе использована фильтрация, заключающаяся в удалении «паразитных» точек применением операций бинарной морфологии «успех/неудача» с парами структурных элементов (Ai,A2) и (ВЬВ2) (рис 1а, 16). В результате проведённого в диссертационной работе исследования установлено неудовлетворительное качества обработки изображения указанным методом. Для устранения данного недостатка в диссертации набор структурных элементов (А|,А2) и (ВЬВ2) дополнен структурными элементами (С,,С2) (рис. 1,в) и доказана лемма, обосновывающая допустимость применения структурных элементов (СРС2) в процедуре фильтрации скелета для удаления помех на изображении скелета объекта.

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

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

4 Couprie M. Note on Fifteen 2D Parallel Thinning Algorithms / M. Couprie; Institut Gaspard-Monge. - Paris, France, 2006. - Technical Report IGM 2006-01. - 21 P.

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

Структурный элемент {АЛ) Структурный элемент Л) Стр) /ктурный эле (смс2) мент

*!!........ м х х х Щ X

а) б) в)

Рис. 1 Структурные элементы, используемые для фильтрации помех на изображении «скелета»

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

Лемма

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

X = 5, и ... 11 5„, где N > 1, причём

О N =

2) 5,. Л5;. = 0, если г*./;

3) 5, - сильносвязное множество.«

Таким образом, если X - связное множество, а его дополнение допускает представление в виде X = 5, и ■•■ и 5у > причём 15,1 = 00. Множество точек Э ЕХ = {х е X : М, (х) П 5, = 0], где М4 (х) - множество

сильносмежных точек с точкой х, будем называть «внешней» границей множества X. Если N >\, то множество точек Э ,Х = {х е X : Ы4 (х1 П 5,. = 0} называется «внутренней» границей

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

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

метод представления символов в виде набора простейших структурных элементов, который используется для «компактного» хранения образцов символов, а также как дополнительный метод коррекции результатов распознавания, используемый наряду с методом алгебраических кривых, представленным в главе 4. Кроме того, задача распознавания простейших элементов на изображении имеет и самостоятельный интерес с многочисленными приложениями. Хорошо известными примерами решения задачи о нахождении прямых на изображении являются многочисленные варианты алгоритмов, использующие или основанные на преобразовании Радона5. В настоящей главе преобразование Радона использовано для разработки алгоритмов поиска прямых и окружностей, обладающих пониженными требованиями к используемой памяти при сохранении производительности распознавания. Предложены новые алгоритмы распознавания прямых и окружностей на изображении, не использующие «аккумулятор» для решения задачи. Предложенный алгоритм распознавания прямых обладает временем работы порядка О^2) для изображения, содержащего N «чёрных» точек, а алгоритм распознавания окружностей -О(^).

Кроме того, на основе операции инверсии изображения развит новый быстрый алгоритм распознавания окружностей. Показано, что метод инверсии является эффективным для определения аналитических параметров окружностей, заданных на изображении. Если координаты центра окружности в системе координат {и,у) есть {а,Ь), то операция инверсии

1 = \/со преобразует окружность (и - а)2 + (у - Ь)2 = а2 + Ьг (а,Ь < <*>) плоскости о) = (м,у), проходящую через начало координат, в прямую 1 - 2ах + 2Ьу = 0 плоскости г = (х,у). Дальнейшее применение алгоритмов на основе преобразования Радона определяет параметры линии, что позволяет провести распознавание окружности. Метод инверсии изображения в настоящей работе используется для разработки новых алгоритмов, позволяющих свести задачу отыскания параметров окружности к задаче нахождения параметров прямой. Оценка производительности разработанных алгоритмов имеет порядок О(Ы), где N - число черных точек на изображении.

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

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

5 Хелгасон С. Преобразование Радона / С. Хелгасон. - М.: Мир, 1983.-152 с.

информации о символе и использованы для его дальнейшего анализа и распознавания.

Общее уравнение алгебраической кривой и-го порядка имеет вид:

/Д*,у) = £Ха,х'-у =0, (1)

1=0 о

в соответствии с (1), алгебраическая кривая порядка п представляет собой функцию переменных х и у с (и+1)(и+2)/2 коэффициентами ац.

Для нахождения коэффициентов уравнения a:j алгебраической

кривой (1) используется ЗЬ-метод, позволяющий получить численно-стабильное решение задачи в случае, если граница объекта Г представляет собой замкнутую кривую, разделяющую всё пространство на «внешнюю» и «внутреннюю» области.

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

границу символа Sk ={(xi1,>'t,)J, к = 1,31.

Для оценки «качества» приближения символа, заданного множеством

координат F = {р, = алгебраической кривой /п и-го порядка

введена метрику S(F,fn), позволяющая оценить «близость» множества F к

модели символа, представленной алгебраической кривой fn (q) = 0.

4FJ„)=YT^{pi-Jn), (2)

JV i = I, Л'

где S{p,f) ~ евклидово расстояние от точки р до кривой f„(q) = 0-

HPJ)= (3)

Приближения первого порядка для выражений (2) и (3) имеют вид, соответственно:

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

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

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

Определение дескрипторов Фурье основано на общих соотношениях, известных из теории преобразований Фурье. Параметрически заданная кривая /(/): х = x(t),y = y(t), f (?) = {x(t),y(t)} с Л2, где / -переменный параметр имеет в случае замкнутой кривой периодические функции x(t) и y(t), с периодом Т. Разложение в ряд Фурье для которых есть:

x(t) = — + cos (toi) + bxk sin (kcot)),

2 t=i

y it) = — + ¿(a,* cos (kmí) + byk sin(fauí)), 2 ы\

Коэффициенты разложения ахк, Ьхк, агк, Ьл в теории цифровой обработки

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

, ал + а\ + Ь]к + Ь]к . .

d к=—-2-П-7Г- к = 2'3'4'-' (5)

Таким образом, в случае задания кривой /(/) m дискретными значениями, определим вектор D{f}, составленный из инвариантных

дескрипторов плоской кривой (5): £>{/} = {d2,—,dm/2) с R"1'1"', где Т обозначает операцию транспонирования. Векторы вида £>{/} применяются в настоящей работе для описания замкнутых границ изображений символов, не зависящий от аффинных преобразований этих изображений.

В диссертационной работе для описания замкнутых плоских кривых используется так называемый метод функции длины хорды. Суть данного метода состоит в следующем. Пусть /(/) = {х(О.>'(/)} с Л2 - естественно параметризованная замкнутая плоская кривая, Т - её периметр (а следовательно, и период функций x(f), у (О). Функция длины хорды определяется следующим образом6:

Ч {/КО = (/(' + }\]- /с>|, j = 1 1 (6)

где к - некоторая целочисленная константа, а || || - евклидова норма. Из определения (6) следует, что: Ц {/}(/) = Lkk'J {/}(t + jT/к), следовательно, функции (6) ¿i {/}(') являются периодическими, с периодом Т. Следовательно, периодические функции L[{f}{t) и Lk¿' {/} отличаются друг от друга только сдвигом на jT / к и для описания плоской кривой достаточно использовать только к!2 функций L'k {/)(/).

6 Wang B. Shape Matching Using Chord-Length Function / B. Wang, C. Shi // IDEAL. - 2006. - P. 746-753

Дескрипторы Фурье и дескрипторы функций длины хорды заданы сравнительно большим объёмом хранимых данных, используемых для распознавания символов. С целью уменьшения объема хранимых данных в диссертационной работе применяется метод главных компонент7, заключающийся в поиске линейного подпространства с базисом, представленным набором ортонормированных векторов vv...,vp, называемых

главными компонентами. Координаты векторов данных х: е Rp, /' = !..и в этом базисе имеют вид:

= = 8,Л + g;2V2 + - + S,pVp = {givSnv'girj> ' = !■■»' (?)

7 = 1

Исходя из предположения, что первые главные компоненты содержат основную «полезную» информацию, наряду с (7) используется приближённое представление:

"X + ^gqVj, q< р.

j=i

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

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

V{Si)=[p : V/ # i,d(p,s,) < s,eS.

V(S) = {JV(s,),

¡=i

где d{p,q) - евклидова метрика. Множества V() называют «ячейками Вороного», точки s, е S,i = 1..7V - «генераторами». Эффективный алгоритм построения диаграммы Вороного на плоскости предложен в работе9.

7 Прикладная статистика. Классификация и снижение размерности / С. А. Айвазян, В. М. Бухштабер, В. М. Енюков, Л. Д. Мешалкин. - М.: Финансы и статистика, 1989 - Т. 3. - С. 334-344

8 Kise К. Segmentation of Page Images Using the Area Voronoi Diagram. / K. Kise, A. Sato, M. Iwata // Computer Vision and Image Understanding. - 1998. - Vol. 3, No. 70. - P. 370-382

9 Fortune S. A. Sweepline Algorithm for Voronoi Diagrams / S. A. Fortune // Proceedings of the Second Annual Symposium on Computational Geometry. - Yorktown Heights, N.Y. (USA), 1986. - P. 313-322

Рукописный текст, в отличие от стандартного машинописного может быть расположен под некоторым углом к «линии основания» изображения. В связи с этим, для рукописных текстов представляется стандартной задача обнаружения наклона текста для корректной сегментации изображения. В настоящей работе предложен новый алгоритм, позволяющий найти средний угол наклона произвольного рукописного или печатного текста. Основная идея алгоритма определения ориентации текста заключается в том, что центры масс символов, принадлежащих одной строке, лежат с небольшими отклонениями на одной прямой. Таким образом, ребро ячейки Вороного между двумя соседними точками, соответствующими центрам масс символов, представляет собой серединный перпендикуляр к отрезку, концы которого заданы соседними точками. Соответственно, ребро диаграммы Вороного определяет угол наклона строки. В настоящей работе разработан алгоритм нахождения угла наклона текста, время работы которого составляет порядка О (и log«), где п - число символов текста. Большинство существующих алгоритмов определения ориентации текста имеет сложность работы порядка 0{п2). На основе анализа расстояний между ячейками

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

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

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

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

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

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

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

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

Основные результаты диссертации

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

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

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

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

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

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

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

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

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

1. Запрягаев С. А. Сегментация рукописных и машинописных текстов методом диаграмм Вороного / С. А. Запрягаев, А. И. Сорокин // Вестник Воронежского государственного университета. Сер. Системный анализ и информационные технологии. - Воронеж, 2010. -№ 1.-С. 160-165.

2. Распознавание примитивов на изображении : Св-во о государственной регистрации программы для ЭВМ № 2008612938 / А. И. Сорокин, С. А. Запрягаев. - М., 2008. - 57 с. - (Заявка № 2008611720; Заявлено 21.04.08; Зарегистрировано 18.06.08).

3. Определение параметров центральных кривых второго порядка на изображении : Св-во о государственной регистрации программы для ЭВМ № 2009611516 / СЛ. Запрягаев, А.И. Сорокин. - М„ 2009. - 40 с. - (Заявка № 2009610320; Заявлено 4.02.09; Зарегистрировано 18.03.09).

4. Сорокин А. И. Программа обнаружения кривых на монохромном изображении / А. И. Сорокин // Информатика : проблемы, методология, технологии : материалы 8 Междунар. науч.-метод. конф., Воронеж, 7-8 февр. 2008 г. - Воронеж, 2008. - Т. 2. - С. 286289.

5. Запрягаев С. А. Программная оболочка для поиска примитивов на изображении / С. А. Запрягаев, А. И. Сорокин // Вестник Воронежского государственного университета. Сер. Системный анализ и информационные технологии. - Воронеж, 2008. - № 2. - С. 37-47.

6. Запрягаев С. А. Программная оболочка для распознавания примитивов на изображении / С. А. Запрягаев, А. И. Сорокин // Математика. Компьютер. Образование : тез. , Пущино, 19-24 янв. 2009 г. -М.-Ижевск, 2009. - Вып. 16, ч. 1. - С. 107.

7. Запрягаев С. А.. Моделирование рукописных символов алгебраическими кривыми / С. А. Запрягаев, А. И. Сорокин // Информатика : проблемы, методология, технологии : материалы 9-ой междунар. науч.-метод. конф., Воронеж, 12-13 февр, 2009 г. -Воронеж, 2009. - Т. 1. - С. 317-321.

8. Запрягаев С. А. Распознавание простых линий на изображении / С. А. Запрягаев, А. И. Сорокин // Прикладная информатика. - 2009. -№4.-С. 76-86.

9. Запрягаев С. А. Распознавание рукописных символов на основе анализа дескрипторов функций длины хорды / С. А. Запрягаев, А. И. Сорокин // Вестник Воронежского государственного университета. Сер. Системный анализ и информационные технологии. - Воронеж, 2009,-№2.-С. 49-58.

Ю.Сорокин А. И. Определение ориентации текста на основе диаграмм Вороного / А. И. Сорокин // Информатика : проблемы, методология, технологии : материалы X междунар. науч.-метод. конф., Воронеж, 11-12 февр. 2010 г. - Воронеж, 2010. - Т. 2. - С. 232-236.

Подписано в печать 14.10.10. Формат 60*84 Усл. печ. л. 0,93. Тираж 80 экз. Заказ 1284

Отпечатано с готового оригинала-макета в типографии Издательско-полиграфического центра Воронежского государственного университета. 394000, Воронеж, ул. Пушкинская, 3.

Введение.

Глава 1. Обзор существующих методов распознавания.

Глава 2. Предварительная обработка изображения.

§2.1. Пороговая классификация.

§2.2. Бинарная морфология в предварительной обработке изображения.

§2.3. Построение скелета изображения.

§2.4. Обработка «скелета» изображения.

§2.5. Выделение границ объектов. Способы задания границ.

Глава 3. Распознавание простейших объектов на изображении.

§3.1. Преобразование Радона.

§3.2. Поиск прямых на изображении.54 j

§3.3. Нахождение параметров окружностей на основе обобщённого преобразования i

Радона

§3.4. Метод инверсий для обнаружения окружностей.

§3.5. Моделирование символов примитивами.

Глава Распознавание сложных объектов.

§4.1. Метод алгебраических кривых.

§4.2. Моделирование рукописных символов алгебраическими кривыми.

§4.3. Инвариантные дескрипторы Фурье.

§4.4. Представление плоской кривой эллиптическими дескрипторами Фурье.

§4.5. Функция длины хорды для построения характерных признаков объекта.

§4.6. Признаки распознавания объекта.

Глава 5. Сегментация изображения.

§5.1. Диаграммы Вороного.v.

§5.2. Сегментация текста на основе обобщённых диаграмм Вороного .Л.

§5.3. Алгоритм обнаружения угла наклона текста.

§5.4. Алгоритм сегментации простых арифметических выражений.

§5.5. Алгоритм деления текста на строки и слова.

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

§6.1. Блок предварительной обработки изображения.

§6.2. Блок сегментации текста.

§6.3. Блок распознавания символов.

§6.4. Блок окончательной обработки результатов распознавания.

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

Цифровая обработка изображений является современным разделом 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. Алгоритмы объединены в пакет программных оболочек

1. Электронный ресурс. ABBYY FineReader — URL: http://finereader.abbyy.com. Дата обращения: 01.11.2009

2. Электронный ресурс. OmniPage OCR Software — URL: http://www.nuance.com/omnipage/. Дата обращения: 01.11.2009

3. Электронный ресурс. I.R.I.S. OCR software and Document Management solutions - URL: http://www.irislink.com/ Дата обращения: 01.11.2009

4. Электронный ресурс. OCR CuneiForm. Система оптического распознавания текстов. URL: http://www.cuneiform:ru/. Дата обращения: 01.01.2009

5. Электронный ресурс. ABBYY FormReader 6.5 Enterprise Edition — URL: http://www.abbyy.ru/formreader/enterprise. Дата обращения: 01.01.2009

6. Электронный ресурс. Государственный архив РФ URL: http://garf.ru. Дата обращения: 01.01.2009.

7. Дьяконов И. М. Письмо / И. М. Дьяконов // БСЭ. 3-е изд. - М., 1975. -Т. 19.-С. 571-577.

8. Распознавание примитивов на изображении : Св-во о государственной регистрации программы для ЭВМ № 2008612938 / А. И. Сорокин, С. А. Запрягаев. М., 2008. - 57 с. - (Заявка № 2008611720; Заявлено 21.04.08; Зарегистрировано 18.06.08).

9. Прэтт У. Цифровая обработка изображений : в 2 т. / У. Прэтт. — М. : Мир, 1982.-Т. 1.-312 с.

10. Яне Б. Цифровая обработка изображений / Б. Яне. — М. : Техносфера, 2007. 584 с.

11. Patent US 1117184. Handwriting Récognition User Interface with a Stylus / H. E. Goldberg. US Patent ,1915.

12. Plamondon R. Online and off-Line Handwriting Recognition: a Comprehensive Survey / R. Plamondon, S. Srihari // Pattern Analysis and Machine Intelligence, IEEE Transactions. 2000. - Vol. 22, No. 1. - P. 6384.

13. Guerfali W. Normalizing And Restoring On-line Handwriting / W. Guerfali, R. Plamondon //Pattern Recognition. 1993.- Vol. 26, No. 3.-P. 419-431.

14. Tapia E. Understanding Mathematics: A System for the Recognition of Online Handwritten Mathematical Expressions : Dissertation / E. Tapia. — Berlin, 2004. 109 p.

15. Sezgin M. Survey Over Image Thresholding Techniques and Quantitative Performance Evaluation / M. Sezgin, B. Sankur // Journal of Electronic Imaging.-2004.-Vol. 13,No. l.-P. 146-168.

16. Shafait F. Efficient Implementation of Local Adaptive Thresholding Techniques Using Integral Images / F. Shafait, D. Keysers, T. Breuel // Proc. SPIE. -2008. Vol. 6815. - P. 10-15.

17. Shapiro L. Computer Vision / L. Shapiro, G. Stockman // Filtering and Enchancing Images. Prentice Hall, 2002. - P. 145-205

18. Jansen M. Empirical Bayes Approach to-Improve Wavelet.Thresholding.;^ for Image Noise Reduction / M. Jansen, A. Bultheel // Journal of the American Statistical Association. 2001. - Vol. 91, No. 454. - P. 629-639

19. Shafait F. Performance Comparison of Six Algorithms for Page Segmentation / F. Shafait, D. Keysers, T. Breuel // 7th IAPR Workshop on Document Analysis Systems. 2006. - Vol. 3872. - P. 368-379.

20. Kise K. Segmentation of page images using the area voronoi diagram / K. Kise, A. Sato, M. Iwata // Computer Vision and Image Understanding. — 1998. Vol. 3, No. 70. - P. 370-382.

21. Nandini N. Estimation of Skew Angle in Binary Document Images Using Hough Transform / N. Nandini, M. K. Srikanta, G. H. Kumar // PWASET. 2008. - Vol. 32, Issue 2070-3740.

22. Duda R. O. Use of the Hough Transformation to Detect Lines and Curves in Pictures / R. O. Duda, P. E. Hart // ACM. 1972. - Vol.15, No.l. - P. 1115.

23. Huang C. Word Segmentation of Off-Line Handwritten Documents / C. Huang, S. Srihari // CEDAR. Buffalo, NY (USA ), 2008. - 5 p|

24. Cole Luke. Visual Object Recognition using Template Matching Robotic / Luke Cole, Austin D., Lance Cole // Systems Lab, RSISE National ICT, Australia, Australian National University. 2004.

25. Gavrila D. M. Fast Correlation Matching in Large (Edge) Image Databases / D. M. Gavrila, L. S. Davis // Computer Vision Laboratory Center for Automation Research University of Maryland College Park. 1994.

26. Nixon M. Region Descriptors / M. Nixon, A. Aguado // Feature Extraction and Image Processing. Oxford; N.Y., 2002. - P. 278-280.

27. Аминов Ю. А. Дифференциальная геометрия и топология кривых / Ю. А. Аминов. -М. : Наука, 1987. 160 с.

28. Hu М. К. Visual Pattern Recognition by Moment Invariants / M. K. Hu // IRE Trans. Information Theory. 1962. - P. 179-187.

29. Teague M. R. Image Analysis by the General Theory of Moments / M. R. Teague // J. Opt. Soc. Am. 1980. - Vol. 70. - P. 920-930.

30. Cosgriff R. L. Identification of Shape / R. L. Cosgriff; Ohio State University Research Foundation. Columbus, Ohio (USA), 1960. - Report 820-11.

31. Zahn С. Т. .Fourier Descriptors.for-Plane Closed Curves / С. ,T- Zahn, R. Z. -Roskies // IEEE Transactions on Computers. 1972. - Vol. C21. - P. 269- ' ' 281.

32. Jain A.K. Image Transforms / A. K. Jain // Fundamentals of Digital Image Processing. Upper Saddle River; N.J. : Prentice-Hall, 1989. - P. 132-163.

33. Theodoridis S. Feature Generation: Linear Transform / S. Theodoridis, K. Koutroumbas // Pattern Recognition. San-Diego;CA, 2003. - P. 230-239.

34. A Hidden Markov Models combination framework for handwriting recognition / T. Artieres, L. Gauthier, P. Gallinari, B. Dorizzi // IJDAR -2002. Vol. 5. - P. 233-243.

35. Lallican P. M. From off-line to On-Line Handwriting Recognition / P. M. Lallican, C. Viard-Gaudin, S. Knerr // Proceedings of the Seventh International Workshop on Frontiers in Handwriting Recognition. — Amsterdam, 2000; P. 303-312.

36. Kittler J. Minimum Error Thresholding / J. Kittler, J. Illingworth // Pattern Recognition. 1986. - Vol. 19. - P. 41-47.

37. Niblack W. An Introduction to Digital Image Processing / W. Niblack. — Prentice Hall.- 1986.-P. 115-116.

38. Shapiro L. Computer Vision / L. Shapiro, G. Stockman // Binary Image Analysis. Prentice Hall, 2002. - P. 75-86.

39. Ritter G. X. Image Algebra / G. X. Ritter, J. N. Wilson // Handbook of Computer Vision Algorithms in Image Algebra CRC Press, 2001. — P. 450.

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

41. Couprie М. Note on Fifteen 2D Parallel Thinning Algorithms / M. Couprie; Institut Gaspard-Monge. Paris, France, 2006. - Technical Report IGM 2006-01.-21 P.

42. Гонсалес,Р.-Цифровая обработка изображении /.Р. Гонсалес, Р. Вудс //. Морфологическая обработка изображений. М., 2006. - С. 747-811.

43. Freeman Н. On the encoding of arbitrary geometric configurations / H. Freeman // IRE Trans. Electron. Comput. EC-10. 1961. - P. 260-268.

44. Ritter G. X. Image Features and Descriptors / G. X. Ritter, J. N. Wilson // Handbook of Computer Vision Algorithms in Image Algebra. CRC Press, 2001.-P. 278-283.

45. Хелгасон С. Преобразование Радона / С. Хелгасон. М. : Мир, 1983 — 152 с.

46. Patent US 3069654. Method and Means for Recognizing Complex Patterns / P.V.C. Hough. US Patent, 1962.50.3ap P. Теория углового момента :0 пространственных.эффектах в* физике и химии / Р. Зар. М.: Мир, 1993. - 351 с.

47. Котляр В. В. Кольцевое преобразование Радона / В. В. Котляр, А. А. Ковалев / Компьютерная оптика. 2003. — Вып. 25. - С. 126-133.

48. Баранов В. Г. Кольцевое преобразование Радона / В. Г. Баранов, А. Г. Храмов // Компьютерная оптика. 2002. — Вып. 23. - С. 44-47.

49. Ginkel M. A Short Introduction to the Radon and Hough Transforms and How They Relate to Each Other / M. Ginkel, C. L. Hendriks, L. J. Vliet // QI-2004-01.-2004.-llp.

50. Toft P. The Radon Transform Theory and Implementation : — PhD Thesis / P. Toft. - Denmark, 1996. - 192 p.

51. Ballard D. The Hough Method for Curve Detection / D. Ballard // Computer Vision. -Englewood Cliffs; N.J.: Prentice-Hall.-1982. P. 123-126.

52. Tarel J.-P. Covariant Conies Decomposition of Quartics for 2d Object Recognition and Affine Alignment / J.-P. Tarel, W. F. Wolovich, D. B. Cooper // ICIP'98. Chicago, 1998. - P. 818-822.

53. Lei Z. 3L Fitting of Higher Degree Implicit Polynomials / Z. Lei, M. M. Blane, D. B. Cooper // Proceeding 3rd IEEE Workshop on Applications of Computer Vision. Sarasota, 1996. - P. 148-153.

54. Tasdizen T. Improving the Stability of Algebraic Curves for Applications / T. Tasdizen, J.-P. Tarel , D. B. Cooper // Image Processing : IEEE Transactions. 2000. - Vol. 9, No. 3. - P. 405-416.

55. Новейшие методы обработки изображений / А. А. Потапов, А. А. Пахомов, С. А. Никитин, Ю. В. Гуляев // Линия с точки зрения математика. М., 2008. - С. 41-53.

56. Doncel V. R. An Optimal Detector Structure for the Fourier Descriptors Domain Watermarking of 2D Vector Graphics / V. R. Doncel, N. Nikolaidis, I. Pitas // IEEE Transactions on Visualization and Computer Graphics. 2007. - Vol. 13, No. 5. - P. 851-863.

57. Nixon M. Feature Extraction by Shape Matching / M. Nixon, A. Aguado // Feature Extraction and Image Processing. Oxford; N.Y., 2002. - P. 247277.

58. Широкополосные беспроводные сети передачи информации / В. М Вишневский, А. И. Ляхов, С. Л. Портной, И. В. Шахнович. — М. : Техносфера, 2005. 592 с.

59. Wang В. Shape Matching Using Chord-Length Function / В. Wang, С. Shi // IDEAL. 2006. - P. 746-753

60. Wang B. A Novel Fourier Descriptor for Shape Retrieval / B. Wang, C. Shi // FSKD. 2006. - P. 822-825

61. Прикладная статистика / С. А. Айвазян, В. М. Бухштабер, И. С. Енюков, Л. Д. Мешалкин. М., 1989. - Т. 3 : Классификация и снижение размерности. - С. 334-344.

62. Lay D. Linear Algebra and Its Applications / D. Lay. 3rd Updated Edition. - Redwood, 2005. - P. 426-445.x

63. Shlens J. A Tutorial on Principal Component Analysis / J. A. Shlens; Systems Neurobiology Laboratory, Salk Insitute for Biological Studies. -La Jolla, CA(USA), 2007. 13 p.

64. Fukunaga K. Introduction to Statistical Pattern Recognition / K. Fukunaga.- San Diego, 1990. P. 445-466.

65. Препарата Ф. Вычислительная геометрия: Введение / Ф. Препарата, М. Шеймос. М.: Мир, 1989. - 295 с.

66. Fortune S. A Sweepline Algorithm for Voronoi Diagrams / S. Fortune // Proceedings of the Second Annual Symposium on Computational Geometry. Yorktown Heights, N. Y., 1986. - P. 313-322.

67. Berg M. Computational Geometry Algorithms and Applications / M. Berg, O. Cheong, M. Kreveld, M. Overmars. 3rd Edition. — Berlin : SpringerVerlag, 2008.-386 p.

68. Kise K. On the Application of Voronoi Diagrams to Page Segmentation / K. Kise, M. Iwata., M. Keinosuke // Department of Computer and Systems Sciences, Osaka Prefecture University . Osaka, Japan, 1998. — 4 p.

69. Wang Z. Word Extraction Using Area Voronoi Diagram / Z. Wang, Y. Lu, C. Lim С. // CVPRW '03. Madison, 2003. - P. 31-36.

70. Сорокин А. И. Определение ориентации текста на основе диаграмм Вороного / А. И. Сорокин // Информатика : проблемы, методология, технологии : материалы X междунар. науч.-метод. конф., Воронеж, 1112 февр. 2010 г. Воронеж, 2010. - Т. 2. - С. 232-236.

71. Электронный ресурс. Лебедев А. И. Словарь русского языка для ,. ■■ ispell - URL: http://sconl55.phys.msu.su/~swan/orthography.html /. Дата обращения: 01.11.2009

72. Электронный ресурс. International Ispell URL: http://fmg-www.cs.ucla.edu/geoff/ispell.html/. Дата обращения: 01.11.2009

73. Электронный ресурс. KADMOS ICR / OCR Engine URL: http://fmg-www.cs.ucla.edu/geoff/ispell.html /. Дата обращения: 01.11.2009. -http://rerecognition.com/wwwre/htm/english.htm