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

005006147

КУРУШИН Даниил Сергеевич

МОДЕЛИРОВАНИЕ ПРОЦЕССА ИДЕНТИФИКАЦИИ ГРАФИЧЕСКИХ ОБЪЕКТОВ

Специальность 05.13.18 — Математическое моделирование, численные методы п комплексы программ

АВТОРЕФЕРАТ

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

1 5 ДЕК 2011

Пермь - 2011

005006147

Работа выполнена на кафедре информационных технологий и автоматизированных систем ФГБОУ ВПО «Пермский национальный исследовательский политехнический университет».

Научный руководитель:

доктор экономических наук, профессор Долгова Елена Владимировна

Официальные оппоненты:

доктор физико-математических наук, профессор Шатров Анатолий Викторович

кандидат техшгческнх наук Скляренко Максим Сергеевич

Ведущая организация:

ФГБОУ ВПО «Пермский государственный национальный исследовательский университет»

Зашита диссертации состоится 20 декабря 2011 г. в 14:00 на заседании диссертационного совета Д 212.188.08 при Пермском национальном исследовательском политехническом университете по адресу: 614990, г. Пермь, Комсомольский проспект, д. 29, ауд. 423.

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

Автореферат разослан « 18 » ноября 2011 г.

Ученый секретарь диссертационного совета, доктор физико-математических наук, доцент

Л.Н. Кротов

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

Актуальность темы. Первые работы по распознаванию рукописного текста относятся к концу 1970-х — началу 1980-х годов (History of Pen and Gesture Computing: Annotated Bibliography in On-line Character Recognition, Pen Computing, Gesture User Interfaces and Tablet and Touch Computers). С тех пор был достигнут определенный прогресс в части распознавания отдельных символов, вводимых стилусом (реже мышью) в специальные поля. Также с приемлемым качеством решается задача распознавания т.н. рукопечатных символов, вводимых в поля анкет (т.н. блоклеттерсы). Существенно большую сложность представляет распознавание неограниченного слитного рукописного текста, причем ряд исследователей вообще полагает эту задачу неразрешимой на современном уровне развития технологи: «Решить задачу распознавания слитного текста с высоким результатом можно будет, только когда компьютер сможет понимать смысл предлагаемого текста» (А. Абраменко).

Задача распознавания оцифрованной рукописи может быть решена несколькими методами. Так, выделяют модели, основанные на идентификации отдельных объектов и их частично упорядоченных наборов. В 1998 г. Larry S. Yaeger, Brandyn J. Webb и Richard F. Lyon для компьютера Apple NEWTON разработали модель, комбинирующую нейронные сети и контекстно-зависимый поиск для распознавания символов, вводимых стилусом в специальное поле на экране.

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

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

Современные системы, поддерживающие распознавание рукописного текста, такие как:

- Chinese Handwriting for Linux — приложение для распознавания китайских символов (2001);

- Stylus Handwriting Input Panel — система ввода рукописного текста, основанная на распознавании штрихов для планшетных ПК (2008);

- HaRe — система рукописного ввода для иврита (2006);

- Тотое — приложение для распознавания рукописного ввода на японском языке (2004);

- CellWriter — панель рукописного ввода, поддерживающая большинство современных языков (после обучения), (2011);

- Kadmos OCR/ICR — API поддержки рукописного ввода для С, С++, VB, .NET, Delphi и Java (2006), -

преимущественно ориентированы на работу с отдельными символами. Исключение составляет Stylus Handwriting Input Panel, однако эта система допускает только ввод текста «на лету» и не способна к распознаванию растровых изображений. Другим исключением является служба Evernote, предлагающая услугу индексирования рукописных документов на большинстве языков. Однако Evernote распознает лишь отдельные слова в тексте и тратит на индексировав ние одного документа до 24-х часов. Как можно видеть, в современных комплексах программ проблема распознавания слитного рукописного текста решена лишь частично.

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

Целью работы является разработка и исследование модели идентификации графических объектов — примитивов, составляющих рукописный текст неограниченной формы и объема, обеспечивающей повышение точности распознавания слитного рукописного текста, создание-''

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

Задачи исследования. Для достижения поставленной цели были решены следуюие задачи:

1. Анализ существующих методов распознавания рукописного текста, изучение применяемых моделей выделения и идентификации графических примитивов — элементов рукописи.

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

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

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

5. Доказательство персептронной представимости структурных представлений графических объектов.

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

7. Проверка модели путем сравнения результатов идентификации с известными моделями и результатми, полученными экспертами.

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

Методы исследования. Для решения задач, сформулированных в работе, использованы методы нейросетевого анализа, обработки изображений, вычислительного эксперимента, искусственного интеллекта, технологии объектно-ориентированного программирования. При разработке проблемно-ориентированного программного комплекса использовались АЯП Python а java, среда разработки Netbeans 6.9.

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

Научная новизна работы состоит в следующем:

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

2. Впервые разработан адаптационный слой нейросетевой модели, что позволило понизить размерность нейронной сети на 1 — 2 порядка;

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

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

Практическая ценность:

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

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

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

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

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

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

2. Научный семинар кафедры Математического моделирования систем и процессов, Пермского государственного технического университета, 2011, Пермь, рук. д.ф.-м.н., профессор Трусов П.В.

3. Научно-практический семинар кафедры информационных технологий и автоматизированных систем Пермского государственного технического университета, 2010, Пермь, рук. д.э.н., профессор Файзрахманов P.A.

4. Международная интернет-конференция «Инновационные технологии: теория, инструменты, практика», 2010, Пермь.

5. Краевая дистанционная научно-практическая конференция «Молодежная наука Прикаг мья», 2009, Пермь.

6. Всероссийская конференция «Теория и практика речевых исследований», 2001, Москва.

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

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

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

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

Публикации. Соискатель имеет 11 опубликованных работ по теме диссертации в центральных (5 работ) и местных (6 работ) изданиях, в которых отражены основные положения диссертации. Список работ приводится в конце автореферата.

Объем и структура работы. Диссертация состоит из введения, трех глав, заключения, списка литературы; изложена на 87 страницах, содержит 15 рисунков; библиографический список включает 67 наименований, 4 приложения, 14 таблиц.

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

5.

Все предложенные математические модели алгоритмизированы с использованием АЯП Python и Java.

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

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

2 СОДЕРЖАНИЕ РАБОТЫ

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

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

На рис. 1 представлена классификация методов распознавания, составленная на основании исследования «Основные методы, применяемые для распознавания рукописного текста» (Мерков A.B., 2005). Как можно видеть, существует два глобальных подхода: распознавание отдельных объектов (символов) и их упорядоченных наборов (кортежей). Для распознавания слитного письма методы, работающие с отдельными объектами или неприменимы вообще, или требуют предварительного разделения слитного текста на символы. Как показано в статье «Алгоритмы сегментации рукопечатных символов» (A.A. Михайлов, В.В. Постников, 2003), разделение слитного рукописного текста на отдельные символы сопряжено с рядом трудностей и зачастую не имеет однозначного решения.

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

Ряд исследователей (G.L. Martin, Y. Le Сип, О. Matan) для распознавания рукописных символов предлагают метод, основанный на выделении из растрового изображения первичных признаков (цвет, яркость, наличие границы) и использовании нейроподобной модели для оценки близости входного изображения известным символам. Отметим, что данная модель требует преобразования исходных данных к единому размеру 16x16 пикселов, т.е. к кортежу {xi,..., X2se), X £ [0,256], что приводит к возникновению нелинейных искажений и ряда других проблем, понижающих качество распознавания текста.

Один из возможных подходов рассмотрен в работе «Распознавание скелетных образов» (Н.В. Котович, O.A. Славин, 2003). Этот подход основан на поиске концевых точек и точек ветвления в растровом скелете изображения символа. JI.M. Местецкий в работе «Непрерывный скелет бинарного изображения» предлагает метод и алгоритм выделения примитива из растрового изображения (в т.ч. применимый для анализа рукописи), основанный на получении обводящего контура. Также интерес представляет метод квантилей, предложенный W. Doyle в работе «Operations useful for similarity invariant pattern recognition» (1962) и алгоритмизированный в статье «Сегментация изображений методом квантилей» (2011). Исследования Пла-модон Р. и Шринари С. показывают меньшую чуствительность таких моделей к искажениям символов, возникающим при письме и сканировании.

По материалам первой главы формулируются следующие выводы:

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

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

Рис. 1. Обзор методов распознавания рукописного текста

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

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

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

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

Процесс распознавания рукописного текста состоит из следующих фаз:

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

7

- распознавание элементов рукописи — сегментированное изображение анализируется классификатором на основе нейронной сети и решаются две задачи:

— определения класса элемента;

- определения взаимного расположения элемента;

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

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

В общем виде этот процесс можно описать отображением:

р = ад, (1)

где I' — сегментированное изображение, I — исходное изображение, а 5 — отображение исходного изображения в сегментированное.

Информация о цвете и яркости с точки зрения сегментации изображения не представляет интереса, поэтому первой операцией будет бинаризация — приведение изображения к черно-белому формату. Традиционно эта задача решается с использованием сг-функции, такой что:

_ ] 0, х <х0 [1, х>х0'

(2)

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

0, х<х0^ха = ЕМЙ + ь, (3)

1, Х>Хо «

где 1„ последовательность пикселей изображения I длиной вп, 7 вектор координат текущей точки изображения (х,у), Ь смещение, подбираемое экспериментально.

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

'п = 0, (г1,х2)

П=1, (11 + 1,12) до

71 = 2, (11,12 + 1) .71 = 3, (х! + 1,Х2 + 1)

где п — порядковый номер соседа обрабатываемого пикселя. Обрабатываемым является пиксель п = 0. Далее считается суммарная яркость 93 выделенных пикселей:

(5)

¿=0

и, если она больше единицы, то пиксель помечается белым:

= \ 1. (6) к ' \о, вф)< Г 1;

где яркость в точке с координатами ~з!.

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

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

луг?) = ¿^(23(3)), (7)

1, х = 1 (белый) О, 1 = 0 (черный)'

JVa-tltf)=:¿V^_tl<8tf), (9)

>=1

'1, В(^) - В(гй) =-1, г е [1,3] ( = I О, ВЙ) - В{х£) Ф -1, » 6 [1,3] 11, В(3) - В(51) = -1, г = 4 .0 В(3)-В(г1)^-1,г = 4

Таким образом, с учетом (7), (8), (9), (10) функция сегментации (для указанной точки) примет вид:

(10)

/•С*) = (11)

где:

!0, 0 < АГШ < 2, ТУо-я = 1

1, N„>2 (12)

1, ЛГ0_ц ф 1

Пример изображения до и после обработки по формулам ((11), (12)) показан на рис. 3. Как можно видеть, из символов успешно выделены наборы однотипных сегментов, которые можно легко отделить друг от друга и распознать.

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

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

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

Векторное представление примитива — это направленный граф, построенный следующим образом: пусть р — точка с целочисленными координатами (соответствует 4-м пикселям изображения), такую точку будем считать вершиной (vertex) и обозначать как v (или w), если эти четыре пикселя имеют различия по цвету. Также будем считать, что между вершинами v и w существует грань (edge, е), если

= (13)

где Е — Евклидово расстояние и если отрезок VW отделяет пиксель черного цвета от пикселя белого цвета таким образом, что черный пиксель остается слева от условного направления движения. Продолжая двигаться таким образом от вершины к вершине, мы получаем направленный граф G. Граф представляет собой путь (path, Р) {i>,...,ип}, такой что:

3Р, 3ei...n(v{,vw) = 1, Ле{ ф V», j < п. (14)

Путь Р называется замкнутым, если и„ = щ. Учитывая (11), замкнутый путь Р, соответствует некоторому элементу, обозначим его Wj. Индексы отличаются, т.к. некоторые пути могут соответствовать незначимым элементам или оставшемуся после фильтрации шуму.

Т.о. задача классификации путей Pi в элементы Wj может быть сформулирована следующим образом: найти такую классифицирующую функцию F, что:

где — множество известных рукописных элементов (задача определения такого множества является задачей лингвистического исследования и не включена в настоящую работу, хотя и выполнена автором). Будем считать, что Р — многослойная нейронная сеть, тогда нам необходимо дополнительно преобразовать замкнутый путь Р таким образом, чтобы каждый его элемент ад принадлежал диапазону [—1,1].

Элементы пути Р представляют собой вершины, т.е. вектора координат Эта форма

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

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

Для этого (для каждого пути Р;) выполняем:

ргп = (16)

где /т — функция скелетизации контура. Определим ее:

Г(Р) = Г ({%,..., уп}) = К,..., и™}, т)

= VI, 1<п,Чк, к = { '

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

рт

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

Рис. 2. Выделение сегментов и определение углов поворота

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

^ (18)

1 + е

Осталось рассчитать значения

Как сказано выше, путь Р"1 необходимо разбить на конечное постоянное число сегментов р™. Для этого определяем суммарную длину пути Р"1 как:

= (19)

1=0

определяем длину сегмента как:

' = (20)

где N — необходимое число сегментов и одновременно размерность входного вектора нейронной сети.

Для разбиения пути Рт на сегменты воспользуемся следующим способом: начиная с произвольно выбранного конца пути /""строится ряд окружностей радиуса /, так что центром первой является вершина г>ц далее и>1. Точка ш2 определяется методом поиска точки пересечения окружности и отрезка, с центром в этой точке строится новая окружность того же радиуса, определяющая вершину ги3, и так далее, пока не будет достигнуто такое состояние, что все необработанные вершины лежат внутри очередной окружности. Тогда угол а< есть угол между отрезками ¡¿»¡и)(+1.

Таким образом, входной вектор нейронной сети рассчитывается:

11

= /»(Р™) = /»(К ...,vn}) = {xu..., зд},

Xj = cr{aj), (21)

ц = f(wj^w^wj+i), j 6 [2 ,N- 1].

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

Настройка модели на работу с текстами определенного содержания и графического качества ведется путем подбора следующих параметров:

1. Смещения b — выражение (3);

2. Количества входов нейронной сети N — (20).

По материалам второй главы формулируются следующие выводы:

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

2. Полученные примитивы можно преобразовать к векторной форме и скелетизировать.

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

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

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

В проблемно-ориентированный комплекс программ входят реализации следующих моделей:

1. Модели сегментации рукописного текста;

2. Модели скелетизации векторных представлений рукописных элементов;

3. Модели нейронной сети (на базе сети Кохонена), настроенной на классификацию рукописных элементов;

4. Словаря рукописных элементов для массива текстов, полученных из ответов студентов специальности АСУ;

5. Модели нейронной сети, настроенной на распознавание рукописных элементов;

6. Модели оптимального представления набора рукописных элементов текстом на естественном языке.

Алгоритм сегментации растрового изображения реализован на АЯП Java и протестирован на массиве оцифрованных рукописных текстов. По результатам экспериментов подготовлена и опубликована работа [1].

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

Как можно видеть, из символов успешно выделены наборы однотипных сегментов, которые можно легко отделить друг от друга. Результаты сегментации были обработаны алгоритмом potrace.

(.ли с С о- с ь < ¿¡/Л i ,

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

Пример К-во сегментов Длина сегмента (дат)

1 6 175

2 64 20

3 57 36

4 128 16

В таблице 1 примеры 1 и 2 взяты с рис. 3 (1 — до сегментации, 2 — после), примеры 3 и 4 взяты с рис. 4 (1 — до сегментации, 2 — после, анализировался фрагмент).

Алгоритм скелетизации векторного представления графического примитива реализован на АЯП Python и протестирован на данных, полученных после векторизации результатов работы сегментатора. а также штрихов, подготовленных вручную. По результатам экспериментов подготовлена и опубликована работа [2], в которой доказано, что предложенная модель позволяет сократить размерность нейронных сетей, используемых при распознавании рукописного текста на 1 - 2 порядка (в зависимости от подхода).

Таблица 2. Сравнение результатов распознавания разными нейросетевыми моделями

Тип сети Качество распознавания Время обучения (сек) Циклов обучения

Сеть на базе персептрона 0.81 15 1500

Нейронная сеть Хопфилда 0.98 5 150

Каре Кохонена 7 "А

С помощью АЯП Python и модуля NumPy реализованы:

- Каре Кохонена,

- Многослойная сеть на основе персептрона,

- Нейронная сеть Хопфилда,

- Адаптационный слой, совместимый (после настройки) с любой нейросетевой моделью.

Разработанные алгоритмы протестированы на данных, полученных после скелетизации, а также штрихов, подготовленных вручную, по результатам экспериментов подготовлена и опубликована работа [3]. Сравнение результатов распознавания разными нейросетевыми моделями приведено в табл. 2.

., (/з »г«-г. ^

Ома ^

/

/{¿¿Л, ¿¿¿с-'^г-*^ > У; (У ¿У ^ г/Хг Л/ ^¿д. ¿.¿/¿¿г 6

о*, ^

¡Ы Пии _ .. ,, Л

^ л^ ..........- —" '

¡15*

/953

. у -¿¿г/Г/л Зь

у.

у £

Рис. 4. Текст до и после сегментации

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

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

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

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

Анализ результатов классификации показал, что выделяемое моделью множество примитивов разделимо кусочно-линейной функцией и, следовательно, может быть разделено многослойной нейронной сетью (при условии создания обучающей выборки). Для реализации самоорганизующейся карты Кохонена использован пакет математического моделирования ЭаРу (с пакетом точных вычислений №1тРу).

По материалам третьей главы формулируются следующие выводы:

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

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

3. Качество распознавания текста с использованием данной модели (в зависимости от аккуратности почерка и настройки модели) составляет от 0.81 до 0.98.

В заключении сформулированы основные выводы и результаты работы:

1. Проведен анализ существующих методов распознавания рукописного текста, изучение применяемых моделей выделения и идентификации графических примитивов — элементов рукописи.

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

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

4. Выполнена адаптация нейросетевой модели для идентификации графических объектов — элементов рукописного текста. Показана работоспособность такой модели.

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

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

7. Качество распознавания текста с использованием данной модели (в зависимости от аккуратности почерка и настройки модели) составляет от 0.S1 до 0.98 и более.

Основные публикации по теме диссертации

В журналах, рецензируемых ВАК:

1. Долгова Е.В., Курушин Д.С. Концепция математического моделирования сегментации слитного рукописного текста // Вестник МГОУ. 2011. №1. Серия «Физика и математика». С. 53-57.

2. Долгова Е.В., Курушин Д.С. Адаптация математической модели нейронной сети для системы распознавания слитного рукописного текста // Вестник МГОУ. 2011. №1. Серия «Физика и математика». С. 91-96.

3. Долгова Е.В., Курушин Д.С. Исследование математической модели штрихов рукописного текста. // Вестник МГОУ. 2011. №1. Серия «Физика и математика». С. 97-105.

Другие публикации:

4. Курушин Д.С., Нестерова Н.М., Низамутдинов О.В. Технология «адаптивной эквивалентности» как способ автоматического анализа текста // Формирование гумманитарной среды и внеучебная работа в вузе, техникуме, школе: Материалы III Всерос. науч. — практ. конф. (22-23 апреля 1999г.): Т. IV /ПГТУ. - Пермь, 1999. - С. 699-700.

5. Курушин Д.С., Нестерова Н.М. О проблеме моделирования понимания в автоматизированных обучающих системах // Визуальная культура XX века и проблемы современного образования: Материалы междунар. молодеж. науч.-практ. конф. Пермь, 10-11 дек. 1999 г. / ПГТУ - Пермь, 1999. - С. 76-78.

6. Курушин Д.С., НестероваН.М., Низамутдинов О.Б. Проект обучающей системы с использованием технологий искусственного интеллекта // Теоретические и прикладные аспекты информационных технологий: Сб. науч. тр. — вып. 47 / РосНИИУМС. — Пермь, 1998. — С. 50-54

7. Курушин Д.С., Санникова А.Г., Левченко A.M. О возможности применения эвристических алгоритмов для автоматического распознавания значений счетчиков посещаемости интернет-ресурсов // Вестник ПГТУ. Электротехника, информационные технологии, системы управления. №3/Федер. агенство по образованию, ПГТУ — Пермь: Издательство ПГТУ, 2009. - С. 279-288

8. Курушин Д.С., Баринова И.А., Маркарян A.M., Нестерова Н.М., Серова Т.С. и др. Моделирование процессов понимания. «Семантика текста»: от формализованного представления содержания текста к его автоматическому выделению //С любовью к тексту: [монография]; Восточ. ин-т экономики, гуманитар, наук, управления и права. — Уфа, 2006. - С. 69-74.

9. Курушин ДС., Нестерова Н.М., Новиков А.И. О возможности автоматического распознавания смысловой внутренней формы текста / Новосиб. гос. ун-т. — Новосибирск, 1999. — С. 114-115.

10. Курушин Д.С., Нестерова Н.М., Новиков А.И. Использование ХМЬ-технологий для моделирования процесса понимания текста // 2-ая Всероссийская конференция «Теория и практика речевых исследований»/ РАН Ин-т языкознания, Москва, 6-7 дек. 2001 г. — М., 2001. - С. 76-78.

11. Курушин Д.С. О возможности использования нечетких алгоритмов проверки открытых вопросов в автоматизированных системах контроля знаний // Электротехника, ИТ, системы управления. 2009. №3. - С. 84-88.

Подписано в печать 18.10.2011. Формат 60x90/16. Усл. печ. л. 1,0. Тираж 100 экз. Заказ № 1967/2011.

Издательство Пермского национального исследовательского политехнического университета. Адрес: 614990, г. Пермь, Комсомольский пр., 29, к. 113. Тел.(342)219-80-33.

61 12-5/1149

ФГБОУ ВПО «Пермский национальный исследовательский политехнический университет»

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

КУРУШИН Даниил Сергеевич

МОДЕЛИРОВАНИЕ ПРОЦЕССА ИДЕНТИФИКАЦИИ ГРАФИЧЕСКИХ ОБЪЕКТОВ

Специальность 05.13.18 — Математическое моделирование, численные методы и комплексы программ

ДИССЕРТАЦИЯ на соискание ученой степени кандидата технических наук

Научный руководитель: доктор экономических наук, профессор Долгова Е. В.

Пермь - 2011

Оглавление

Список иллюстраций 4

Список таблиц б

Введение 7

1 Анализ современного состояния исследований в области распознавания текста 14

1.1 Общие вопросы оптического распознавания

текста............................................................14

1.2 Основные принципы OCR......................................15

1.3 Основные методы OCR........................................16

1.4 Подходы к распознаванию рукописного текста..............18

1.5 Программные продукты для распознавания рукописного текста............................................................20

1.5.1 ABBYY FineReader Рукопись..........................20

1.5.2 Система Cognitive Forms................................21

1.5.3 Панель рукописного ввода CellWriter ................24

1.6 Выводы..........................................................25

2 Идентификация графических объектов 27

2.1 Постановка задачи..............................................27

2.2 Анализ известных способов идентификации рукописных символов ..............................................................28

2.3 Сегментация изображения......................................34

2.4 Математическая модель распознавания элементов рукописи 37

2.5 Выводы..........................................................42

3 Разработка проблемно-ориентированного комплекса программ, верификация моделей 47

3.1 Постановка задачи..............................................47

3.2 Используемое математическое и программное обеспечение 48

3.3 Сегментация ....................................................49

3.4 Скелетизация....................................................58

3.5 Экспериментальная проверка..................................73

3.6 Выводы..........................................................75

Заключение 77

Список литературы 78

Приложения 88

Список иллюстраций

1.1 Обзор методов распознавания рукописного текста..........19

1.2 Cell Writer, режимы обучения и распознавания..............24

2.1 Пример рукопечатного текста..................................29

2.2 Отдельные рукопечатные символы............................30

2.3 Пример слитного рукописного текста........................43

2.4 Пример слитного рукописного текста, символы частично разделены..................................................43

2.5 Пример рукописного текста, в результате оцифровки залиты элементы символов «ы», «е», «а»..........................43

2.6 Проведение косого разреза, продемонстрированное в работе [64] ............................................................44

2.7 Использование многослойной нейронной сети для распознавания символов..............................................45

2.8 Текст до и после сегментации..................................45

2.9 Выделение сегментов и определение углов поворота .... 46

3.1 Архитектура программного продукта........................50

3.2 Реализация модуля загрузки изображения ..................51

3.3 Скелетизация контуров........................................52

3.4 Последовательные преобразования в модуле Filter..........54

3.5 Рукописный текст до и после обработки......................55

3.6 Печатный текст с неоднородным шумом до и после обработки 56

3.7 Реализация алгоритма обработки изображения..............57

3.8 Выделение краев, (а) Оригинальная картинка; (Ь) слишком много узловых точек; (с) слишком мало узловых точек; (d) хорошее выделение краёв ............................59

3.9 Обработка искажений, имеющихся в растровом изображении 60

3.10 Варианты контуров для символа «W»........................60

3.11 Слева — оригинальное изображение, в центре изображение после обработки программой AutoTrace, справа — после обработки Potrace ..............................................gl

3.12 Пример SVG-файла, получаемого после векторизации ... 62

3.13 SVG-файл, в котором построена скелетизирующая полилиния................................................................63

3.14 Алгоритм разбора SVG........................................64

3.15 Координаты точек на кривой..................................65

3.16 Анализ слова . .....................................65

3.17 Использование многослойной нейронной сети для распознавания символов..............................................68

3.18 Обработка штриха..............................................69

3.19 Структура сети Хопфилда....................................70

3.20 Алгоритм подстройки весов сети Хопфилда..................71

3.21 Алгоритм расчета состояния сети ............................71

3.22 Генерация выходного вектора..................................72

3.23 Правило преобразования входного вектора для сети Хопфил-

Да .........................................................72

3.24 Создание и использование многослойного персептрона . . 73

Список таблиц

3.1 Сравнение результатов работы рокасе и Ах^оТУасе .... 60 3.3 Сравнение результатов распознавания разными нейросете-

выми моделями....................... 73

Введение

Первые работы по распознаванию рукописного текста относятся к концу 1970-х - началу 1980-х годов (History of Pen and Gesture Computing: Annotated Bibliography in On-line Character Recognition, Pen Computing, Gesture User Interfaces and Tablet and Touch Computers). С тех пор был достигнут определенный прогресс в части распознавания отдельных символов, вводимых стилусом (реже мышью) в специальные поля. Также с приемлемым качеством решается задача распознавания т.н. рукопечат-ных символов, вводимых в поля анкет (т.н. блоклеттерсы). Существенно большую сложность представляет распознавание неограниченного слитного рукописного текста, причем ряд исследователей вообще полагает эту задачу неразрешимой на современном уровне развития технологий «Решить задачу распознавания слитного текста с высоким результатом можно будет, только когда компьютер сможет понимать смысл предлагаемого текста» [56].

Задача распознавания оцифрованной рукописи может быть решена несколькими методами. Так, выделяют модели, основанные на идентификации отдельных объектов и их частично упорядоченных наборов. В 1998 г. Larry S. Yaeger, Brandyn J. Webb и Richard F. Lyon для компьютера Apple NEWTON разработали модель, комбинирующую нейронные сети и контекстно-зависимый поиск для распознавания символов, вводимых стилусом в специальное поле на экране.

A.B. Мисюрёв, исследуя возможности идентификации таких объектов, как символы кириллического алфавита, цифры и иные знаки, ис-

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

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

Современные системы, поддерживающие распознавание рукописного текста преимущественно ориентированы на работу с отдельными символами. Исключение составляет Stylus Handwriting Input Panel, однако эта система допускает только ввод текста «на лету» и не способна к распознаванию растровых изображений. Другим исключением является служба Evernote, предлагающая услугу индексирования рукописных документов на большинстве языков. Однако Evernote распознает лишь отдельные слова в тексте и тратит на индексирование одного документа до 24-х часов. Как можно видеть, в современных комплексах программ проблема распознавания слитного рукописного текста решена лишь частично.

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

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

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

1. Анализ существующих методов распознавания рукописного текста, изучение применяемых моделей выделения и идентификации графических примитивов — элементов рукописи.

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

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

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

5. Доказательство персептронной представимости структурных представлений графических объектов.

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

7. Проверка модели путем сравнения результатов идентификации с известными моделями и результатми, полученными экспертами.

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

Методы исследования. Для решения задач, сформулированных в работе, использованы методы нейросетевого анализа, обработки изображений, вычислительного эксперимента, искусственного интеллекта, технологии объектно-ориентированного программирования. При разработке проблемно-ориентированного программного комплекса использовались АЯП Python и java, среда разработки Netbeans 6.9.

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

Научная новизна работы состоит в следующем:

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

2. Впервые разработан адаптационный слой нейросетевой модели, что позволило понизить размерность нейронной сети на 1 - 2 порядка;

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

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

Практическая ценность:

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

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

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

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

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

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

2. Научный семинар кафедры математического моделирования систем и процессов Пермского государственного технического университета, 2011, Пермь, рук. д.ф.-м.н., профессор Трусов П.В.

3. Научно-практический семинар кафедры информационных технологий и автоматизированных систем Пермского государственного технического университета, 2010, Пермь, рук. д.э.н., профессор Файз-рахманов P.A.

4. Международная интернет-конференция «Инновационные технологии: теория, инструменты, практика», 2010, Пермь.

5. Краевая дистанционная научно-практическая конференция «Молодежная наука Прикамья», 2009, Пермь.

6. Всероссийская конференция «Теория и практика речевых исследований», 2001, Москва.

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

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

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

3. Полученный в ходе работы проблемно-ориентированный комплекс программ позволяет разбивать рукопись на графические примитивы и идентифицировать Pix с вероятностью 0.81-0.98.

Публикации. Соискатель имеет И опубликованных работ по теме диссертации в центральных (5 работ) и местных (6 работ) изданиях, в которых отражены основные положения диссертации.

Личный вклад автора. Постановка задачи осуществлялась совместно с научным руководителем к.т.н., д.э.н., проф. Долговой Е.В. Основные результаты диссертационного исследования получены автором самостоятельно. Автором проведен анализ предметной области, предложена гипотеза о том, что графические примитивы, составляющие слитный рукописный текст, могут быть формально описаны постоянным конечным количеством сегментов, разработано структурное описание графического примитива, предложена и исследована модель идентификации. Все предложенные математические модели алгоритмизированы с использованием АЯП Python и Java.

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

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

Объем и структура работы. Диссертация состоит из введения, трех глав, заключения, списка литературы; изложена на 87 страницах, содержит 15 рисунков; библиографический список включает 67 наименований, 4 приложения, 14 таблиц.

Глава 1

Анализ современного состояния исследований в области распознавания текста

1.1 Общие вопросы оптического распознавания текста

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

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

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

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

1.2 Основные принципы OCR

В 1977 году группой исследователей под руководством А. Шамиса были сформулированы важнейшие принципы распознавания: целостность, целенаправленность и адаптивность [34].

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

Второй принцип — целенаправленность. Распознавание строится как процесс выдвижения и до