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

Фан Нгок Хоанг

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

АЛГОРИТМЫ ОБРАБОТКИ И АНАЛИЗА СИМВОЛОВ ВЕИВЛЕТ-ПРЕОБРАЗОВАНИЕМ, МЕТОДОМ ГЛАВНЫХ КОМПОНЕНТ И НЕЙРОННЫМИ СЕТЯМИ

05.13.01 - Системный анализ, управление и обработка информации (в отраслях информатики, вычислительной техники и автоматизации)

АВТОРЕФЕРАТ

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

г э МАИ 2014

005549193

Томск-2014

005549193

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

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

Спицын Владимир Григорьевич

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

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

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

Ведущая организация: Федеральное государственное бюджетное

образовательное учреждение высшего

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

Защита состоится 25 июня 2014 г. в 10:30 на заседании диссертационного совета Д 212.267.12, созданного на базе федерального государственного бюджетного образовательного учреждения высшего профессионального образования «Национальный исследовательский Томский государственный университет», по адресу: 634050, г. Томск, пр. Ленина, 36 (учебный корпус № 2, аудитория 2126).

С диссертацией можно ознакомиться в Научной библиотеке и на официальном сайте федерального государственного бюджетного образовательного учреждения высшего профессионального образования «Национальный исследовательский Томский государственный университет» www.tsu.ru.

Материалы по защите диссертации размещены на официальном сайте 11У http://tsu.ru/content/news/announcement_of_the_dissertations_in_the_tsu.php.

Автореферат разослан в «_» мая 2014 г.

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

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

В настоящее время существует ряд программных средств и систем, использующих алгоритмы распознавания символов для решения задачи распознавания текстов. Широкое распространение получили такие программные средства как ABBY FineReader, Tesseract OCR, CuneiForm, OmniPage, Readiris и др. В каждом из перечисленных программных продуктов предложены свои алгоритмы и методы для распознавания символов и текстов. Однако большинство указанных программных средств являются коммерческими, поэтому алгоритмы и методы, применяемые в них для решения задач, известны только разработчикам.

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

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

Вейвлет-преобразование является эффективным методом для выделения признаков объектов при решении задач распознавания образов. При разложении изображения вейвлет-преобразование содержит в себе необходимую информацию об этом изображении. Например, субдиапазоны в пространственных и частотных доменах, в различных разрешениях, в горизонтальном, вертикальном и диагональном направлениях. Вейвлет-преобразование также достаточно быстро вычисляется. В алгоритмах ряда авторов Mehdi L., Weibao Z., Chang T., Daniel M.R.S., Park S.B. и Gonzalez A.C. используются вейвлет-преобразования

для решения задачи классификации изображений. В указанных работах показано, что при использовании вейвлет-преобразования для выделения признаков изображения точность классификации изображений составляет 76-99,7%.

Кроме того, в области распознавания образов вейвлет-преобразования используются в алгоритмах ряда авторов Lai J.H., Kakarwal S., Zhang В., Gumus E., Wadkar P.D., Kumar S.V.P. и Mazloom M. В указанных работах показано, что вейвлет-преобразования эффективно используются при решении задач распознавания образов, в особенности, задачи распознавания лиц. Точность распознавания лиц при этом составляет 90-98,5%.

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

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

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

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

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

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

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

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

Научную новизну полученных в диссертации результатов определяют следующие положения.

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

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

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

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

системах OCR, системах распознавания номеров автомобилей, при обработке изображений.

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

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

Реализация полученных результатов работы. Способ, алгоритмы и программы, разработанные в диссертационной работе, использовались при выполнении работ по гранту РФФИ № 09-08-00309 «Создание программного комплекса автоматизированной обработки изображений и распознавания образов на основе применения искусственных нейронных сетей, регуляторных сетей и эволюционных алгоритмов» (2009-2011 гг.); в проекте «Создание комплексных технологий распознавания объектов на изображении на основе применения моделей зрительного восприятия и методов вычислительного интеллекта», поддержанном грантом РФФИ № 12-08-00296 (2012-2014 гг.).

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

Внедрение работы. Результаты работы внедрены в Томском политехническом университете на кафедре вычислительной техники при подготовке специалистов по магистерской программе «Компьютерный анализ и интерпретация данных» по курсу «Методы интеллектуальной обработки и анализа изображений»; при проведении работ по НИР «Разработка алгоритмов и программ восстановления текста из графической информации», выполнявшейся по хоздоговору № 4-311/2013У.

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

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

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

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

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

Апробация работы. Результаты диссертационной работы докладывались и обсуждались на следующих симпозиумах, конференциях и семинарах: VIII, IX Всероссийские научно-практические конференции студентов, аспирантов и молодых ученых «Молодежь и современные информационные технологии» (Томск, 2010, 2011); XVI, XVII Международные научно-практические конференции студентов, аспирантов и молодых ученых «Современные техника и технологии» (Томск, 2010, 2011); III Всероссийская научно-практическая конфе-

ренция «Научная инициатива иностранных студентов и аспирантов российских вузов» (Томск, 2010); VI Международная научно-практическая конференция «Электронные средства и системы управления» (Томск, 2010); XIX Всероссийский семинар «Нейроинформатика, ее приложения и анализ данных» (Красноярск, 2011); XIV Всероссийский с международным участием научный симпозиум по теории и приложениям непараметрических и робастных статистических методов «НЕПАРАМЕТРИКА-XIV» (Томск, 2012); The 7th International Forum on Strategie Technology IFOST (Томск, 2012).

Публикации. Основные результаты диссертационного исследования изложены в 17 печатных работах, в том числе в 7 статьях в изданиях из перечня ВАК РФ [1-7].

Личный вклад автора. Постановка задач исследования по теме диссертации выполнена автором совместно с научным руководителем, д.т.н., профессором В.Г. Спицыным. Основные теоретические результаты, представленные в диссертации, получены лично автором.

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

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

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

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

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

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

Шаг 1. Обучение нейронных сетей.

Шаг 1.1. Выделение характерных признаков символов из обучающей выборки на основе применения вейвлет-преобразования. Шаг 1.2. Уменьшение размерности векторов выделенных признаков методом главных компонент.

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

Шаг 2. Распознавание символа.

Шаг 2.1. Выделение характерных признаков распознаваемого символа из тестовой выборки на основе применения вейвлет-преобразования. Шаг 2.2. Уменьшение размерности вектора выделенных признаков методом главных компонент.

Шаг 2.3. Распознавание символа обученными нейронными сетями.

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

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

Для того чтобы выделить локальные характерные признаки символа, его изображение делится на 12 частей с одинаковым размером 32x32 пикселя (рис. 1). Затем к каждой части применяется вейвлет-преобразование и извлекаются низкочастотные вейвлет-коэффициенты. В результате получаются 12 матриц, каждая из которых состоит из 16х 1

После этого составляется вектор характерных признаков символа, элементами которого являются все низкочастотные вейвлет-коэффициенты, полученные на предыдущих шагах. В результате получается вектор характерных признаков символа 1, состоящий из 32x32 + 12x16x16 = 4096 элементов (рис. 1).

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

К каждому из М изображений применяется разработанный способ выделения характерных признаков. В результате получается набор векторов признаков /,,...,/м. Затем составляется средний вектор, значение каждого элемента которого по всем Мвекторам признаков вычисляется по формуле:

1 м ..

т п=\

Далее из каждого вектора признаков вычитается средний вектор Ф =1 -I п = 1 М

[6 низкочастотных вейвлет-коэффициентов.

Исходное изображение /

Вейвлег преобразование

□СЕК ЯЕИН

Вейвлет преобразование

Вектор признаков /

12 локальных частей

Рис. 1. Выделение признаков символа «А»

После этого создается пространство, состоящее из К собственных векторов йк ковариационной матрицы С, которые наилучшим образом описывают распределение значений М векторов признаков (К<М)

1 м

С = 77 ^пФ1 = ЛАт, А = {ФХ,...,ФМ).

М„=1

При этом каждый к-ъш вектор йк удовлетворяет условию максимизации следующего выражения:

, м

1 ^Г/г.Т^ ^

и условию ортогональности:

и1 ик

[1, [ = к [О, иначе

Векторы йк и величины Як представляют собственные векторы и собственные значения ковариационной матрицы С.

Для создания этого пространства вначале нужно вычислить М собственных векторов й[ матрицы С с использованием векторов являющихся собственными векторами матрицы ¿ = АГЛ. Каждый вектор щ вычисляется по следующей формуле:

2 м

Затем из М полученных векторов выбираются К собственных векторов, имеющих наибольшие собственные значения. Пространством собственных символов является набор выбранных К собственных векторов (рис. 2). Значение К определяется эмпирическим способом.

ИИ-и

МЫ

М изображений символов

Выделение признаков

Вычисление собственных векторов

М векторов признаков

Рис. 2. Создание пространства собственных символов

Пространство К собственных векторов

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

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

-Т -

жения, определяющиеся по формуле: w¡ =м; (/вх -/ср), / =

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

={\\>\,...,\\>к}. В результате уменьшения размерности получается новый

вектор признаков символа сс меньше 4096 (рис. 3).

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

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

:тоящий из К элементов. При этом К намного

Выделение признаков

1

з£>

!

( 1

/ Пространство К собственных векторов

Рис. 3. Уменьшение размерности вектора признаков

Выделение признаков

I /г

гЧ

-1 V!

4

К собственных векторов

>$>0,017

«г»

^>0,78818— первое

предположение

«2»

т^>0Д7611 — второе

предположение

Рис. 4. Распознавание символа нейронными сетями

Кроме того, использование специальной нейронной сети для каждого символа обучающей выборки обеспечивает возможность рассмотрения второго варианта результата распознавания. Вторым предположением является символ обучающей выборки, нейронная сеть которого возвращает второе наибольшее значение. Преимущество рассмотрения двух вариантов распознавания проявляется в случае распознавания похожих по написанию символов, таких как {с, С}, {о, О), {р, Р}, {э, Б}, {и, У}, {V, V}, {ч/, \¥), {х, X} и (г, г} (рис. 4).

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

Шаг 1. Выделение символов из фрагмента текста.

Шаг 1.1. Поворот наклонного изображения фрагмента текста. Шаг 1.2. Выделение строк из фрагмента текста. Шаг 1.3. Выделение слов из строк. Шаг 1.4. Выделение символов из слов.

Шаг 2. Распознавание выделенных символов.

Шаг 2.1. Извлечение характерных признаков выделенных символов на основе применения вейвлет-преобразования.

Шаг 2.2. Уменьшение размерности векторов извлеченных признаков методом главных компонент.

Шаг 2.3. Распознавание символов обученными нейронными сетями.

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

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

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

5ЙРе: Creatfng a Text HTML Editor

Although Apple officially removed HTML rcm™5 hiddc" "> Лс UiKit framework. A

Recipe: Creating a Text HTML Editor

Although Appk officially removed HTML remains hidden iii the UIKit framework A

Рис. 5. Результат поворота наклонного текста: а, 6) исходное изображение текста и его проекция на ось У; в, г) повернутое изображение и его проекция на ось У

Recipe: Creating a Text ШМГЕШШ

"Although Apple ulliLKilly removed H I ML remains hidden in the UIKit framework^

Puc. 6. Результат выделения строк проекцией на ось У

Чтобы выделить слова каждой из строк, полученных на шаге выделения строк, используется проекция этой строки на ось X. Вводятся следующие термины для проекции строки на ось X: «белый столбец» - столбец, на котором нет ни одной черной точки; «черный столбец» - столбец, на котором расположена хотя бы одна черная точка. На основе результатов эмпирического способа «пробел» в строке определяется последовательностью только «белых столбцов», количество которых больше чем 8. Области слов выделяются на основе информации о полученных пробелах. Левая и правая границы слов определяются в соответствии с этими областями. Пример результата выделения слов в строке представлен на рис. 7.

Для выделения символов каждого из слов, полученных на шаге выделения слов, вводится следующий термин: «соединяющийся столбец». На этом столбце расположена последовательность черных точек, соединяющаяся с черными точками соседних столбцов. Выделение символов из слова осуществляется следующим образом. Вначале слово сканируется слева-направо и обнаруживается первая последовательность «соединяющихся столбцов». Затем определяются левая и правая границы возможной области первого символа. Полученная возможная область сканируется сверху-вниз и Y-координата первой черной точки является верхней границей области символа. Затем полученная область сканируется снизу-вверх и Y-координата первой черной точки является нижней границей области символа. Сканирование слова слева-направо продолжается, пока все содержащиеся в нем символы не будут выделены. Пример выделения символов слова «Recipe:» представлен на рис. 8.

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

Существуют похожие по написанию символы, такие как {с, С}, {о, О}, {р, Р}, {s, S}, {u, U}, {v, V}, {w, W}, {х, X} и {z, Z}. Эти символы зачастую неправильно распознаются. Таким образом, при распознавании фрагмента печатного текста необходимо выполнить дополнительный процесс отдельного распознавания похожих по написанию символов.

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

Recipe: Creating a Text UátátIUMi üimmíIuH m 1**1

Recipe; Creating g Text

Рис. 7. Результат выделения слов строки проекцией на ось X

_ Сканирование

слева-направо

i Сканирование сверху-вниз

i Сканирование ' снизу-вверх

Рис. 8. Выделение символов из слова «Recipe:»

нижнего свободного пространства. Примеры четырех типов областей символов представлены на рис. 9.

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

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

В третьей главе рассматриваются средства для разработки программного обеспечения. Проведен анализ инструментальных библиотек по обработке изображений, по результатам которого сделан выбор объектно-ориентированного языка программирования С#, библиотек Emgu CV и OpenCV для дальнейшей разработки. В главе содержится описание библиотеки, предназначенной для реализации предложенного способа построения классификатора для распознавания символов, предложенных алгоритмов распознавания символов и фрагментов печатных текстов.

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

В четвертой главе приводятся результаты апробации разработанных алгоритмов на разных тестовых задачах распознавания. Все численные эксперименты проводились на ноутбуке с процессом Intel Core Duo Р7350 2.0 ГГц с 2.0 ГБ оперативной памяти.

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

1-ый тип: Ш8 R [а-Верхнее

UUP LJ UJ пространство

2-ой тип: S0S0B0 Нижнее

ILJ пространство

3-ий тип: ЭВВВ 00

4-ый тип: Зшвнеи

Рис. 9. Примеры четырех типов обла-

стей символов

Первым экспериментом является тестирование разработанного алгоритма на задаче распознавания рукописных цифр. Для проведения этого тестирования использовалась известная база рукописных цифр МЫКТ. Данная база состоит из 60000 изображений для обучения и 10000 изображений для тестирования. Все изображения имеют одинаковый размер 28*28 пикселей и все цифры центрированы внутри изображения.

Для тестирования созданы дополнительные тестовые выборки путем добавления к изображениям исходной тестовой выборки базы М№8Т шума «соли и перца» с уровнем 5, 10, 15, 20, 25 и 30%. Примеры изображений тестовых выборок приведены на рис. 10. Слева-направо на рис. 10 представлены исходные изображения цифр и изображения с уровнем шума 10, 20 и 30%.

Результаты распознавания разработанным алгоритмом рукописных цифр из базы МГЖТ в зависимости от размерное: представлены на рис. 11. По вертикальной оси отсчитывается точность распознавания в процентах (д, %), а по горизонтальной оси - количество использованных признаков (К). Показано, что точность распознавания разработанным алгоритмом зависит от размерности вектора признаков символов. При использовании вектора из 5 признаков точность распознавания составляет только 70,3%. При увеличении количества использованных признаков точность распознавания увеличивается. Когда количество использованных признаков равно 37, точность распознавания составляет 97%. Результаты проведенных экспериментов показывают более устойчивую работу алгоритма при увеличении количества использованных признаков. При количестве признаков больше 37 точность распознавания находится в пределах от 97% до 97,5%. При использовании вектора из 49 признаков точность распознавания достигает 97,5%.

В случае использования результатов распознавания с учетом второго предположения точность распознавания разработанным алгоритмом существенно увеличивается. При использовании вектора из 5 признаков точность распознавания уже составляет 84,7%. Для количества использованных признаков равного 37 получен результат распознавания 98,8%. При использовании количества признаков больше 37 точность распознавания устойчиво находится в пределах от 98,8% до 99%. При размере вектора признаков равном 49 также как и в предыдущем случае получен наилучший результат распознавания - 99%.

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

В работе Болотовой Ю.А. предложена сеть иерархической временной па-

м ЕЯ шш

шш шш

и шш

Рис. 10. Примеры изображений рукописных цифр

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

- Результаты без учета второго предположения

- Результаты с учетом второго предположения

5 20 35 50 65 80 95 К

Рис. 11. Результаты распознавания рукописных цифр

мяти (ИВП), также протестированная на задаче распознавания рукописных цифр из базы MNIST. При этом обучение сети ИВП проводилось различными алгоритмами, такими как Жадный алгоритм кластеризации (Greedy), Aglomerative Hierarchical Clustering (АНС) и Maximum Temporal Connection (МТС). Результаты сопоставления разработанного алгоритма и сети ИВП по распознаванию рукописных цифр из базы MNIST приведены в табл. 1.

Таблица 1. Результаты распознавания выборки MNIST разработанным алгоритмом и сетью ИВП____

Процессор Алгоритм Точность, % В ремя

обучения тестирования

Intel Core™ 3.47ГГц Сеть ИВП (Greedy) 97,3 05:34:12 01:38:43

Сеть ИВП (АНС) 97,6 05:15:17 01:30:56

Сеть ИВП (МТС) 98,5 05:21:47 01:32:35

Intel Core Duo P7350 2.0 ГГц Разработанный алгоритм 97,5 00:24:36 00:06:08

Разработанный алгоритм (с учетом второго предположения) 99,0 00:24:36 00:06:08

В результате сопоставления показано, что разработанный алгоритм обучается в 13 раз быстрее и распознает цифры в 15 раз быстрее, чем сеть ИВП. Результат распознавания цифр разработанным алгоритмом составляет 97,5% и он сопоставим с результатом их распознавания сетью ИВП, обученной алгоритмами Greedy и АНС. Точность распознавания разработанным алгоритмом с учетом второго предположения является наилучшей и составляет 99%.

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

Таблица 2. Сравнение различных алгоритмов распознавания на базе MNIST

Алгоритм Минимальная ошибка, % Максимальная ошибка, %

Линейный классификатор 7,6 12

Нелинейный классификатор 3,3 3,6

Сети ИВП 1,5 1,5

Boosted stumps 0,87 7,7

K-Nearest Neighbors 0,63 5

SVM 0,56 1,4

Нейронные сети 0,35 4,7

Сверточные сети 0,23 1,7

Разработанный алгоритм 2,5 3

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

В этом эксперименте также проводилось тестирование разработанного алгоритма на созданных зашумленных выборках рукописных цифр базы МШБТ.

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

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

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

обучения алгоритма создана обучающая выборка, состоящая из 1488 изображений 10 цифр (0-9) и 52 английских букв (a-z, A-Z). Каждый символ представлен двумя распространенными шрифтами Times New Roman и Arial в обычном и полужирном начертаниях с размерами шрифта: 16, 18, 20, 22, 24 и 26. Каждый символ обучающей выборки представлен 24 изображениями.

Для тестирования использовались изображения символов 8 популярных шрифтов: 4 шрифта с засечками - Times New Roman, Garamond, Courier New и Bookman Old Style; 4 шрифта без засечек - Arial, Lucida Sans, Tahoma и Verdana. Для каждого шрифта подготовлена тестовая выборка, содержащая 2480 изображений 10 цифр (0-9) и 52 английских букв (a-z, A-Z). Каждый символ представлен в разных размерах шрифта: 12, 14, 16, 18, 20, 22, 24, 26, 28 и 36 в обычном и полужирном начертаниях.

На рис. 13 приведены результаты распознавания печатных символов разных шрифтов в зависимости от размерности вектора признаков символа. По вертикальной оси отсчитывается точность распознавания в процентах (<5, %), а по горизонтальной оси - количество использованных признаков (/Q.

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

предположения 100

0 5 10 15 20 25 30 Уровень шума, %

Рис. 12. Результаты распознавания зашумленных рукописных цифр

100

80 60 40 20

5 30

55 К

100

80 ^60 40 20

5 30

55 К

80

Times New Roman

Garamond

Courier New

100 80 60 ч» 40

20

p-

30 55 К

Bookman Old Style

100

Arial

Lucida Sans

Tahoma Verdana

-Результаты без учета второго предположения

-Результаты с учетом второго предположения

Рис. 13. Результаты распознавания печатных символов разных шрифтов

Экспериментальные результаты показывают, что разработанный алгоритм, обученный только символами двух шрифтов, может распознавать символы других шрифтов. Показано, что кроме шрифта Bookman Old Style, для всех остальных шрифтов, когда количество использованных признаков символа находится в пределах от 20 до 60, точность распознавания разработанным алгоритмом является приемлемой. Результаты распознавания символов, представленных шрифтами без засечек, лучше и устойчивее, чем результаты распознавания шрифтов с засечками.

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

Для каждого шрифта созданы дополнительные тестовые выборки путем добавления 5, 10, 15, 20, 25 и 30% шума типа «соли и перца» к изображениям существующей тестовой выборки. Примеры зашумленных изображений буквы «А» и цифры «0» приведены на рис. 14. Слева-направо на рис. 14 представлены исходные изображения символов и изображения с уровнем шума 10, 20 и 30%.

Результаты тестирования разработанного алгоритма на зашумленных выборках представлены на рис. 15. На рис. 15(a) представлены результаты распознавания без учета второго предположения, а на рис. 15(6) - результаты распознавания с его учетом.

00®

Рис. 14. Примеры изображений печатных символов

0 5 10 15 20 25 30 Уровень шума, %

100 а

0 5 10 15 20 25 30 Уровень шума, %

-Times New Roman

-Garamond

-Courier

- Bookman Old Style

- Arial

-Lucida Sans

-Tahoma

-Verdana

а б

Рис. 15. Результаты распознавания печатных символов на зашумленных выборках

Показано, что разработанный алгоритм способен эффективно распознавать печатные символы разных шрифтов в присутствии шума на изображениях. Точность распознавания зависит от уровня шума на изображениях. Чем больше уровень шума на изображениях, тем меньше точность распознавания. В присутствии 5% шума на изображениях, точность распознавания разработанным алгоритмом больше 75% для 7 шрифтов, а в присутствии 30% - только для 3 шрифтов. При использовании результатов распознавания с учетом второго

предположения точность распознавания существенно увеличивается.

Результаты сопоставления разработанного алгоритма и систем распознавания текста ABBY FineReader 11 и Tesseract OCR по распознаванию символов двух шрифтов Times New Roman и Arial на зашумленных выборках представлены на рис. 16.

О 5 10 15 20 25 30 Уровень шума, %

0 5 10 15 20 25 30 Уровень шума, %

-FineReader - Tesseract

-Разработанный алгоритм

-Разработанный алгоритм (с учетом второго предположения)

Times New Roman Arial

Рис. 16. Сравнение результатов распознавания зашумленных печатных символов

Показано, что при увеличении уровня шума на изображениях точность распознавания системами ABBY FineReader 11 и Tesseract OCR существенно уменьшается, а точность распознавания разработанным алгоритмом падает медленнее. Разработанный алгоритм распознает печатные символы в присутствии шума на изображениях эффективнее, чем системы ABBY FineReader 11 и Tesseract OCR. При уровне шума больше 15% разница между их результатами распознавания становится более заметной.

В данной главе также проведены эксперименты по распознаванию фрагментов печатных текстов. Для тестирования разработанного алгоритма распознавания фрагментов текста использовались отсканированные документы. Фрагменты текстов имеют одинаковое содержание. Каждый фрагмент включает 1581 символ, набранный в текстовом редакторе Microsoft Office Word 2007. При наборе текста фрагментов использовались два популярных шрифта: Times New Roman и Arial с размерами шрифта: 14, 16, 18, 20, 22, 24, 26, 28 и 36 в обычном и полужирном начертаниях. Эти фрагменты текстов распечатывались, затем полученные документы сканировались с разрешением 300dpi и сохранялись в файлах в формате «Ьтр». Таким образом, тестовая выборка имеет всего 36 фрагментов печатных текстов.

Тестирование разработанного алгоритма распознавания фрагментов печатных текстов и систем распознавания текста ABBY FineReader 11 и Tesseract OCR осуществлялось на подготовленных 36 фрагментах текстов. На основе сопоставления результатов распознавания фрагментов печатных текстов, набранных шрифтом Arial, показано, что точность распознавания, достигнутая системой ABBY FineReader 11, является наилучшей и составляет 99,94-100%, точность распознавания системой Tesseract OCR составляет 99,87-100% и точность распознавания разработанным алгоритмом составляет 97,66-99,62%.

Наибольшее количество ошибок, возникающих при распознавании разработанным алгоритмом фрагментов печатных текстов шрифта Arial, наблюдает-

ся для таких пар символов, как i и j, i и 1, е и о, I и 1 и неразделенных букв rt, rf, ff и ry.

На основе сопоставления результатов распознавания фрагментов печатных текстов, набранных шрифтом Times New Roman, показано, что точность распознавания, достигнутая системой ABBY FineReader 11, также является наилучшей и составляет 99,87-100%, точность распознавания системой Tesseract OCR составляет 99,43-99,62% и точность распознавания разработанным алгоритмом составляет 90,89-98,17%.

Наибольшее количество ошибок, возникающих при распознавании разработанным алгоритмом фрагментов печатных текстов шрифта Times New Roman, наблюдается для таких пар символов, как 1 и 1, t и f, г и f, h и b, п и Н и неразделенных букв rn, rm, rt, ry, fi, fo, fa, fu и ffi.

Следует отметить, что для шрифта Arial результаты распознавания разработанным алгоритмом лучше, чем для шрифта Times New Roman. Это объясняется тем, что шрифт Times New Roman является шрифтом с засечками, из-за которых количество неразделенных букв (rn, rm, rt, ry, fi, fo, fa, fa и ffi) для шрифта Times New Roman больше, чем количество неразделенных букв (rt, rf, ff и ry) для шрифта Arial.

Установлено, что средняя точность распознавания фрагментов текста, представленных шрифтами Arial и Times New Roman, составляет: ABBY FineReader 11 - 99,95-100 %, Tesseract OCR - 99,51-99,99 % и разработанным алгоритмом - 93,65-99,21 %.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

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

2. Разработан оригинальный алгоритм распознавания символов, основанный на вейвлет-преобразовании, методе главных компонент и нейронных сетях.

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

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

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

Статьи в журналах, включенных в Перечень рецензируемых научных изданий, рекомендованных Высшей аттестационной комиссией при Министерстве образования и науки Российской Федерации для опубликования основных научных результатов диссертаций:

1. Фан, Н.Х. Анализ алгоритмов обнаружения импульсного шума на цифровых изображениях / Н.Х. Фан, В.Г. Спицын // Известия Томского политехнического университета. - 2011. - Т. 318. - № 5. - С. 70-73. - 0,21/0,15 п.л.

2. Буй, Т.Т.Ч. Алгоритмическое и программное обеспечение для классификации цифровых изображений с помощью вейвлет-пребразования Хаара и нейронных сетей / Т.Т.Ч. Буй, Н.Х. Фан, В.Г. Спицын // Известия Томского политехнического университета. - 2011. - Т. 319. - № 5. - С. 103-106. -0,37/0,12 п.л.

3. Фан, Н.Х. Алгоритмы для классификации отпечатков пальцев на основе применения фильтра Габора, вейвлет-преобразования и многослойной нейронной сети / Н.Х. Фан, В.Г. Спицын // Известия Томского политехнического университета. - 2012. - Т. 320. - № 5. - С. 60-64. - 0,31/0,2 п.л.

4. Буй, Т.Т.Ч. Распознавание лиц на основе применения метода Виолы-Джонса, вейвлет-преобразования и метода главных компонент / Т.Т.Ч. Буй, Н.Х. Фан, В.Г. Спицын // Известия Томского политехнического университета. -2012. - Т. 320. - № 5. - С. 54-59. - 0,45/0,15 п.л.

5. Буй, Т.Т.Ч. Распознавание лиц и жестов на основе применения вейвлет-преобразования и метода главных компонент / Т.Т.Ч. Буй, Н.Х. Фан, В.Г. Спицын // Нелинейный мир. - 2012. - Т. 10 - № 6. - С. 371-379. -0,79/0,3 п.л.

6. Фан, Н.Х. Распознавание печатных текстов на основе применения вейвлет-преобразования и метода главных компонент / Н.Х. Фан, Т.Т.Ч. Буй, В.Г. Спицын // Известия Томского политехнического университета. - 2012. -Т. 321. - № 5. - С. 154-158.-0,41/0,25 п.л.

7. Фан, Н.Х. Распознавание жестов на видеопоследовательности в режиме реального времени на основе применения метода Виолы-Джонса, алгоритма CAMShift, вейвлет-преобразования и метода главных компонент. / Н.Х. Фан, Т.Т.Ч. Буй, В.Г. Спицын // Вестник Томского государственного университета. Управление, вычислительная техника и информатика. - 2013. -Т. 23. - № 2. - С. 102-111. - 0,65/0,3 п.л.

Публикации в других научных изданиях:

8. Фан, Н.Х. Удаление шумов на изображениях на основе применения искусственных нейронных сетей / Н.Х. Фан, В.Г. Спицын // Молодежь и современные информационные технологии: сборник трудов VIII Всероссийской научно-практической конференции студентов, аспирантов и молодых ученых: в 2 ч. - Томск, 3-5 марта 2010. - Томск: СПБ Графике, 2010. - Ч. 2. - С. 227-228.-0,21/0,15 п.л.

9. Фан, Н.Х. Методы удаления шумов на изображениях на основе применения искусственных нейронных сетей / Н.Х. Фан, В.Г. Спицын // Современные техника и технологии: Сборник трудов XVI Международной научно-практической конференции студентов, аспирантов и молодых ученых: в 3 т. -Томск, 12-16 апреля 2010. - Томск: ТПУ, 2010. - Т.2.- С. 399^101. -0,19/0,11 п.л.

10. Фан, Н.Х. Снижение шумов на цифровых изображениях / Н.Х. Фан, В.Г. Спицын // Научная инициатива иностранных студентов и аспирантов российских вузов: Сборник докладов III Всероссийской научно-практической конференции. - Томск, 19-21 мая 2010. - Томск: ТПУ, 2010. - С. 190-194. -

0,21/0,15 п.л.

11. Фан, Н.Х Модифицированный медианный фильтр подавления импульсного шума на изображениях / Н.Х. Фан, В.Г. Спицын // Электронные средства и системы управления: Материалы докладов VI Международной научно-практической конференции: в 2 ч. - Томск, 13-16 октября 2010. -Томск: В-Спектр, 2011.-Ч. 1.-С. 118-121.-0,16/0,1 п.л.

12. Буй, Т.Т.Ч. Подавление шумов и реконструкция изображений на основе применения ядра регрессии / Т.Т.Ч. Буй, Н.Х. Фан // Современные техника и технологии: Сборник трудов XVII Международной научно-практической конференции студентов, аспирантов и молодых ученых: в 3 т. - Томск, 18-22 апреля 2011. - Томск: ТПУ, 2011. - Т. 2,- С. 299-300. -0,17/0,7 п.л.

13. Фан, Н.Х. Анализ алгоритмов обнаружения импульсного шума на изображениях / Н.Х. Фан, В.Г. Спицын // Молодежь и современные информационные технологии: Сборник трудов IX Всероссийской научно-практической конференции студентов, аспирантов и молодых ученых: в 2 ч. - Томск, 11-13 мая 2011. - Томск: СПБ Графике, 2011. -Ч. 1. - С. 126-127. - 0,2/0,13 п.л.

14. Фан, Н.Х. Анализ алгоритмов обнаружения импульсного шума на изображениях / Н.Х. Фан, В.Г. Спицын // Проблемы информатики. - 2011. -№ 2(10). - С. 26-30. - 0,21/0,13 п.л.

15. Буй, Т.Т.Ч. Классификация изображений на основе применения цветовой информации, вейвлет-преобразования Хаара и многослойной нейронной сети / Т.Т.Ч. Буй, Н.Х. Фан, В.Г. Спицын // Проблемы информатики. - 2011. -Спецвыпуск. С. 81-86. - 0,38/0,15 п.л.

16. Буй, Т.Т.Ч. Способ классификации изображений на основе применения вейвлет-преобразования Хаара и нейронных сетей / Т.Т.Ч. Буй, Н.Х. Фан, В.Г. Спицын // Нейроинформатика, ее приложения и анализ данных: материалы XIX Всероссийского семинара. - Красноярск, 1-3 октября 2011. - Красноярск: СФУ, 2011. - С. 159-164. - 0,31/0,12 п.л.

17. Bui, Т.Т.Т. Face and Hand Gesture Recognition based on Wavelet Transforms and Principal Component Analysis / T.T.T. Bui, N.H. Phan, V.G. Spitsyn // 7th International Forum on Strategic Technology IFOST: Proceedings of IFOST. -Tomsk: TPU Press, 2012. - V. 1. - P. 588-591. - 0,4/0,15 п.л.

Подписано к печати 06.05.2014. Формат 60x84/16. Бумага «Снегурочка». Печать XEROX. Усл. печ. л. 1,16. Уч.-изд. л. 1,05.

_Заказ 381-14. Тираж 120 экз._

Национальный исследовательский Томский политехнический университет Система менеджмента качества Издательства Томского политехнического университета сертифицирована в соответствии с требованиями ISO 9001:2008 КЩТЕЛЬСШЖШ. 634050, г. Томск, пр. Ленина, 30 Тел./факс: 8(3822)56-35-35, www.tpu.ru

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

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

04201459814

Фан Нгок Хоанг АЛГОРИТМЫ ОБРАБОТКИ И АНАЛИЗА СИМВОЛОВ ВЕЙВЛЕТ-ПРЕОБРАЗОВАНИЕМ, МЕТОДОМ ГЛАВНЫХ КОМПОНЕНТ И НЕЙРОННЫМИ СЕТЯМИ

05.13.01 - Системный анализ, управление и обработка информации (в отраслях информатики, вычислительной техники и автоматизации)

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

Научный руководитель -доктор технических наук, профессор В.Г. Спицын

Томск 2014

ОГЛАВЛЕНИЕ

ВВЕДЕНИЕ..............................................................................................................5

Глава 1. Аналитический обзор подходов к распознаванию символов.........12

1.1 Основные задачи обработки изображений.......................................12

1.2 Подходы и системы распознавания символов и текстов................14

1.2.1 Системы распознавания текста..............................................14

1.2.2 Подходы к распознаванию символов.....................................16

1.2.3 Выделение признаков..............................................................19

1.3 Методы обработки изображений и распознавания образов с использованием вейвлет-преобразования..................................................31

1.3.1 Построение дескриптора фигуры...........................................31

1.3.2 Классификация изображений.................................................32

1.3.3 Распознавание лиц...................................................................35

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

1.5 Основные результаты и выводы по главе 1......................................41

Глава 2. Применение вейвлет-преобразования, метода главных компонент и нейронных сетей для распознавания символов и фрагментов печатных текстов ...............................................................................................................42

2.1 Предложенный алгоритм распознавания символов........................42

2.1.1 Выделение признаков изображений символов.....................43

2.1.2 Уменьшение размерности вектора признаков......................48

2.1.3 Распознавание символов нейронными сетями......................51

2.2 Предложенный алгоритм распознавания фрагментов печатных текстов............................................................................................................52

2.2.1 Выделение символов из фрагмента текста............................53

2.2.2 Распознавание фрагмента текста............................................57

2

2.2.3 Распознавание похожих по написанию символов................58

2.3 Основные результаты и выводы по главе 2......................................61

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

3.1 Выбор средств разработки.................................................................62

3.2 Реализованные классы для распознавания символов и фрагментов текстов............................................................................................................66

3.2.1 Классы для распознавания символов.....................................66

3.2.2 Классы для распознавания фрагментов печатных текстов . 77

3.3 Разработанные программные средства.............................................87

3.3.1 Приложение для исследователей...........................................87

3.3.2 Приложение для обычных пользователей...........................100

3.4 Основные результаты и выводы по главе 3....................................102

Глава 4. Численные эксперименты и анализ результатов распознавания разработанными алгоритмами...........................................................................103

4.1 Тестирование на задаче распознавания рукописных цифр..........103

4.1.1 Обучающая выборка..............................................................103

4.1.2 Описание тестирования.........................................................104

4.1.3 Результаты тестирования......................................................105

4.2 Тестирование на задаче распознавания печатных символов.......108

4.2.1 Обучающая выборка..............................................................108

4.2.2 Описание тестирования.........................................................110

4.2.3 Результаты тестирования......................................................111

4.3 Тестирование на задаче распознавания фрагментов печатных текстов..........................................................................................................113

4.3.1

Описание тестирования

113

4.3.2 Результаты тестирования......................................................115

4.4 Основные результаты и выводы по главе 4....................................118

ЗАКЛЮЧЕНИЕ....................................................................................................119

ОБОЗНАЧЕНИЯ..................................................................................................120

СПИСОК СОКРАЩЕНИЙ.................................................................................121

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ И ЛИТЕРАТУРЫ..........122

ПРИЛОЖЕНИЕ...................................................................................................138

ВВЕДЕНИЕ

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

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

В настоящее время существует ряд программных средств и систем, использующих алгоритмы распознавания символов для решения задачи распознавания текстов. Широкое распространение получили такие программные средства как ABBY FineReader, Tesseract OCR, CuneiForm, OmniPage, Readiris и др. В каждом из перечисленных программных продуктов предложены свои алгоритмы и методы для распознавания символов и текстов. Однако большинство указанных программных средств являются коммерческими, поэтому алгоритмы и методы, применяемые в них для решения задач, известны только разработчикам.

Хотя перечисленные программы показывают высокую точность распознавания символов и текстов, но они не могут обеспечивать 100% точность распознавания для всех вариантов символов и текстов, а также в присутствии шума на изображениях. Указанные программные средства и системы продолжают развиваться в направлении повышения точности и скорости распознавания. Таким образом, можно сделать вывод, что разработка новых алгоритмов для распознавания символов и текстов

5

является актуальной задачей.

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

Вейвлет-преобразование является эффективным методом для выделения признаков объектов при решении задач распознавания образов. При разложении изображения вейвлет-преобразование содержит в себе необходимую информацию об этом изображении. Например, субдиапазоны в пространственных и частотных доменах, в различных разрешениях, в горизонтальном, вертикальном и диагональном направлениях. Вейвлет-преобразование также достаточно быстро вычисляется. В алгоритмах ряда авторов Mehdi L., Weibao Z., Chang T., Daniel M.R.S., Park S.B. и Gonzalez A.C. используются вейвлет-преобразования для решения задачи классификации изображений. В указанных работах показано, что при использовании вейвлет-преобразования для выделения признаков изображения точность классификации изображений составляет 76-99,7%.

Кроме того, в области распознавания образов вейвлет-преобразования используются в алгоритмах ряда авторов Lai J.H., Kakarwal S., Zhang В., Gumus E., Wadkar P.D., Kumar S.V.P. и Mazloom M. В указанных работах показано, что вейвлет-преобразования эффективно используются при решении задач распознавания образов, в особенности, задачи распознавания лиц. Точность распознавания лиц при этом составляет 90-98,5%.

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

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

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

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

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

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

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

Апробация работы. Результаты диссертационной работы докладывались и обсуждались на следующих симпозиумах, конференциях и семинарах: VIII, IX Всероссийские научно-практические конференции студентов, аспирантов и молодых ученых «Молодежь и современные информационные технологии» (Томск, 2010, 2011); XVI, XVII Международные научно-практические конференции студентов, аспирантов и молодых ученых «Современные техника и технологии» (Томск, 2010, 2011); III Всероссийская научно-практическая конференция «Научная инициатива иностранных студентов и аспирантов российских вузов» (Томск, 2010); VI Международная научно-практическая конференция «Электронные средства и системы управления» (Томск, 2010); XIX Всероссийский семинар «Нейроинформатика, ее приложения и анализ данных» (Красноярск, 2011); XIV Всероссийский с международным участием научный симпозиум по теории и приложениям непараметрических и робастных статистических методов «НЕПАРАМЕТРИКА-XIV» (Томск, 2012); The 7th International Forum

on Strategic Technology IFOST (Томск, 2012).

Кратно изложим основное содержание работы.

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

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

В третьей главе рассматриваются средства для разработки программного обеспечения. Проведен анализ инструментальных библиотек по обработке изображений, по результатам которого сделан выбор объектно-ориентированного языка программирования С#, библиотек Emgu CV и OpenCV для дальнейшей разработки. В главе содержится описание библиотеки, предназначенной для реализации предложенного способа построения классификатора для распознавания символов, предложенных алгоритмов распознавания символов и фрагментов печатных текстов.

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

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

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

Научную новизну полученных в диссертации результатов определяют следующие положения.

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

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

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

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

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

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

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

Личный вклад автора. Постановка задач исследования по теме диссертации выполнена автором совместно с научным руководителем, д.т.н., профессором В.Г. Спицыным. Основные теоретические результаты, представленные в диссертации, получены лично автором.

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

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

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

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

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

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

за ценные замечания и обсуждение работы. Автор также благодарит за обсуждение работы доцентов Томского политехнического университета, кандидата технических наук Е.А. Мирошниченко и кандидата физико-математических наук Ю.Б. Буркатовскую.

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

Внедрение работы. Результаты работы внедрены в Томском политехническом университете на кафедре вычислительной техники при подготовке специалистов по магистерской программе «Компьютерный анализ и интерпретация данных» по курсу «Методы интеллектуальной обработки и анализа изображений»; при проведении работ по НИР «Разработка алгоритмов и программ восстановления текста из графической информации», выполнявшейся по хоздоговору № 4-311/2013У.

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

Глава 1. Аналитический обзор подходов к распознаванию символов

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