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

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

005531318 а

Мищенко Вадим Анатольевич

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

Специальность 05.13.17 - Теоретические осноиы информатики

АВТОРЕФЕРАТ

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

Воронеж - 2013

005531318

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

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

профессор Астахова Ирина Федоровна.

Официальные оппоненты: Вишняков Юрий Муссович - доктор технических наук, профессор, декан факультета автоматики и вычислительной техники Таганрогского технологического института Южного Федерального университета

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

Ведущая организация: факультет вычислительной математики и

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

Защита состоится мая 2013 г. в часов 00 минут на заседании

диссертационного совета Д 212.038.24 при Воронежском государственном университете ^ л^з

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

Автореферат разослан « РУ» 2013 г.

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

Чеботарев А.С.

з

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

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

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

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

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

Работа выполнялась на кафедре Информатики и методики преподавания математики Воронежского государственного педагогического университета в рамках Договора № ELSP/B1/C/016/10-06 от 27 апреля 2006 г. «Разработка программ и учебно-методических материалов для подготовки студентов педагогических вузов в области использования цифровых образовательных ресурсов»(2005-2008 гг.).

\

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

В рамках реализации поставленной цели необходимо решить следующие задачи:

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

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

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

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

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

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

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

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

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

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

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

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

почтовой связи Воронежской области - филиал Федерального государственного унитарного предприятия «Почта России». Программа «Сортировочный участок» зарегистрирована в Федеральном институте промышленной собственности (ФИПС) (свидетельство №2012610838 от 19 01.12г.).

Основные результаты, нмносиммс на защиту. На защиту выносятся следующие результаты, полученные в процессе исследований:

1) модифицированный алгоритм предварительной обработки изображений;

2) генетический алгоритм с использованием особого оператора мутации;

3) модифицированная модель сети Ванга - Менделя;

4) программный комплекс, реализующий нейро-нечетко-генетическую систему распознавания.

Апробация работы. Основные результаты, представленные в диссертационной работе, докладывались и обсуждались на Математической конференции молодых преподавателей и студентов Лискинского филиала ВГУ (Воронеж, 2007);на научных сессиях Федерального государственного бюджетного образовательного учреждения высшего профессионального образования «Воронежский государственный педагогический университет» 20082009г. г .; на Международной конференции «Современные проблемы механики и прикладной математики» (Воронеж, 2007); на Всероссийской конференции «Современные методы теории краевых задач» (школа «Понтрягинские чтения», 2010); на XVIII Всероссийской Школе-Коллоквиуме по стохастическим методам и XII Всероссийском симпозиуме по прикладной и промышленной математике (Весенняя сессия) (Казань, 2011).

Публикации. Результаты диссертации опубликованы в 11 работах. Списку ВАК соответствуют работы [1-4]. Получено одно свидетельство государственной регистрации программы [II].

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

Структура и объем диссертации. Диссертация состоит из введения, 4 глав, разбитых на пункты, заключения, списка используемой литературы из 107 наименований и приложения:. Общий объем диссертации - 134 страницы, приложение на 31 стр. Работа содержит 40 рисунков.

Область исследовании. Диссертационная работа соответствует следующим пунктам паспорта специальности 05.13.17 - Теоретические основы информатики:

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

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

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

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

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

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

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

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

- преобразование полученного цветного изображения в изображение в градациях серого цвета;

-бинаризация изображения;

- сегментация.

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

У = 0.255 R + 0.255 G + 0.255 В, (1)

где Y - новое значение цвета, R - интенсивность красной составляющей, G - интенсивность зеленой составляющей, В- интенсивность синей составляющей.

Суть бинаризации растровых изображений заключается в сравнительном анализе яркости текущего пикселя Р(х,у) с неким пороговым значением /' (х,у): если яркость текущего пикселя превышает пороговое значение, т.е. Р[х,у)> Рг(х,у), то цвет пикселя на бинарном изображении будет белым; в противном случае - черным. Далее выбирается один из методов сегментации изображения, основанный на диаграммах Вороного. Суть данного процесса сводится к нахождению отдельных символов индекса на всей плоскости изображения. Диаграмма Вороного представляет собой набор конечного множества точек на плоскости, при котором образуется такое разбиение точек па плоскости, при котором каждая область разбиения находится ближе к одному из элементов множества, чем к другому. Если S - конечное множество точек на плоскости, a d(p,q) - метрика, то диаграмма Вороного V(S) будет выглядеть как разбиение множества S на следующие подмножества:

V(s,) = {p:yij*i^(d(p.s,)<d(p,sj))}, s,eS; (2)

причем

= V/*1(У(5,)пУ(Б1) = 0 . (3)

Множества называются ячейками Вороного, точки

я. 6 5 0 = ¡..И) - генераторами.

а) множество генераторов б) диаграмма Вороного

Рис. I. Множество генераторов и диаграмма Вороного

Для сравнения эффективности распознавания рассматриваются различные способы организации нейронных сетей: многослойный персептрон, сеть Кохонена, сеть Хэмминга, нечеткая нейронная сеть Ванга - Менделя. На основе проведенного вычислительного эксперимента было установлено, что нечеткая нейронная сеть Ваш а - Менделя имеет более высокую, по сравнению с остальными, оценку точности распознавания, поэтому именно она была выбрана для реализации алгоритма распознавания (рис. 2).

0.99 0.90 0,97 0,96 0,95 0,94

0,967

0,958 0,95

_

_ — —

Многослойный ларсептрон

Сеть Кохонена

Сеть Хемминга

Сеть Ванга-Мондогя

Рис. 2. Оценка точности работы различных сетей

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

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

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

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

Выходной сигнал модифицированной сети Ванга - Менделя рассчитывается по формуле

V, = Б1 [I] /Б2[1], (4)

где 51/7у = £(аЛц/х,), ,'72//7 = £Г1 Ц.(х,) (1 = 1..К), И- количество

м 7=1 •' 1=1 М ''

входов в сеть, М~ количество элементов второго слоя, К - количество вы-

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

Содержательная постановка задачи обучения нейронной сети выглядит так: заданы векторы: X , который соответствует закодированному изображению распознаваемого символа; У, который отражает результат распознавания, указывающий на принадлежность символа к эталонному образцу. Необходимо найти весовую матрицу И'с элементами, состоящими из вещественных чисел из отрезка [0,1], такую, для которой ошибка аппроксимации по методу наименьших квадратов была бы минимальной. Для нахождения весовой матрицы IV используется генетический алгоритм (ГА), который позволяет найти решение, как угодно близкое к оптимальному за счет настройки параметров.

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

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

0Н7-П=|£(;>\-/,) (5)

Функция пригодности определяется на основе вычисленного расстояния и имеет вид:

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

Я(0,) = Р(01)-100%, (7)

где Р(0)) - вероятность выбора /'-й особи, которая вычисляется по формуле

р(°1>--я---■ (8)

¡=1

где Рр(0¡) - значение функции пригодности ¡-ой особи.

где О - евклидово расстояние. (6)

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

родители

Vw2

>.QlJo.44

3,6 0.7

наполнение

0.67

0,21

0.03

0,2 0.5f-

ГД

New Vw1

0,1 0,8 0,98 0,S

0,01 0.44

New Vw2

0,83

0,8

0.7

0,7

S 0,21 0,03 0

jt

5 0,32 С

I 0.7 і

Гены, отмененные маркером не вошли в хромосомы-потомков и так как левая часть

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

Рис. 4. Принцип работы упорядоченного кроссинговера

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

Count р = round (SizeК„,)-2 , (9)

где Sizep- размер популяции, County- количество получаемых потомков, round — операция округления.

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

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

Хромосома до мутации

1©346© (4?) 46 47 ,18 49

0 23 0 81 0.05 0.09 0 1 0 9 @ © « 0,01 0.00 0.65 с .зз 0.22 • • •

Пусть случайным обрЕзом выбрана интенсивность мутации указывающая количество мутирующих генов равное 3 Также случайным образом зыбраны номера этих [енов 2,6 Приращений сигма получила случаное значение 0 13 Тогда хромосома после мутации будет иыглядеи> следующим образом

Хромосома после мутации

1 © 3 4 5 (§) @ 46 47 <16 49

о.гз 0 94 0.05 009 0.1 0.9 ее» 0.14 0.08 0.65 033 0 22 «•в

Ген N86 не изменил своего значения, так как его величине стала равна 1,12, что противоречит постановке задачи. В таком случае говорнт о "ненужной мутации"

Рис. 5. Случайная мутация на основе приращения

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

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

I 35

. 3

I 2,5

I 2

? 1,5

? 1

9Ю -їтгт—

- - --------- - 1.33 ........._

Алгоритм с применениям мутации на основе приращония

Алгоритм с применением классического многоточечного оператора мутации

Гибридный алгоритм

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

Оператор мутации применяется к потомкам особей, получаемых после операции скрещивания. Особи с мутациями остаются в популяции до начала этапа «формирование новой популяции». Количество мутирующих особей определяется формулой

Count т = round (Count р-К''п) + round (Countр 'Кьт), Крт + К°т = Кт<\, (10) где К„'; - коэффициент классической мутации; К?„ ~ коэффициент мутации на основе приращения; Кт - общий коэффициент мутации; Соип1т - количество особей, претерпевших мутацию; Count - количество потомков, round -

операция округления.

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

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

Sizep = Size р+Count+ Count т, (II)

где Count ~ количество полученного потомства, Countm~ количество особей, полученных в результате мутаций, a Sizep - численность популяции.

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

Count d = Count + County, (12)

где Countj - количество «отмерших» особей, Count - количество полученных потомков, Countт- количество особей, полученных с помощью оператора мутации.

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

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

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

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

Рис. 7. Основное окно программы

В верхнем левом углу расположен блок работы с \УЕВ-камерой. На прямоугольник транслируется изображение с камеры, выбранной из списка Источник видео.

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

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

В структуре программного комплекса можно выделить четыре основных функциональных блока (рис. 8):

- модуль работы с \¥еЬ-камерой;

- модуль распознавания символов;

- модуль работы с весовой матрицей;

- модуль работы с базой данных.

И:кшнсс приложение

МапуСам \Ъ'1иа1 Н'еЬсюи

ф|й.1 эффекта Ramka.gif

[Основной модуль программы

I : I Модуль работы 1 I с \veb-камер ой Г

1

Модуль 1 распознавания I символов

Модуль работы | I с весовой млтрнпей Г~

I Модуль работы: | -| с базой данных

Фдйл БД

IudexLB.mdb

Файл настроек урЬ-камеры

СопАй-сат

Файл настроек весовой МВТРН11Ы

Ма/ггх. «•

Рис.8 Схема взаимодействия функциональных блоков

Модуль работы с м>еЬ-камерой. В основу устройства для считывания почтовых индексов с конвертов, как наиболее доступное решение, была выбрана обычная \уеЬ-камера.

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

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

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

После этапа распознавания, управление работой программы передается в модуль работы с базой данных. Дос туп к данным в этом модуле реализован с помощью технологии Microsoft ActiveX Data Objects (ADO).

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

Основные результаты работы

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

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

2) разработана модификация модели нечеткой нейронной сети Ваш а -Менделя с несколькими выходами, что повысило точность работы сети с за-шумленными изображениями;

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

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

5) с помощью нейро-нечетко-генетической системы распознавания образов решена важная практическая задача сортировки почтовой корресион-денциии.

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

Публикации в изданиях, рекомендованных ВАК РФ

1. Мищенко В.А. Алгоритм распознавания графических образов / В.А.Мищенко II Вестник Воронежского гос. техн. ун-та. - 2009. - Т. 5. - № 12-С. 103-105.

2. Мищенко В.А. Принципы нечеткой логики на примере нечетких нейронных сетей / В.А.Мищенко, А.А.Коробкин // Современные проблемы науки и образования. -2012. - № 1 - (URL: www.science-education.ru/10l-5321)

3. Мищенко В.А. Использование генетических алгоритмов в обучении нейронных сетей / В.А.Мищенко, А.А.Коробкин //'Современные проблемы науки и образования. -2011. - № 6 - (URL: www.science-education.ru/100-5138)

4. Мищенко В.А. Алгоритм обучения нечеткой нейронной сети Ванга-Менделя для распознавания рукопечатных символов в работе почтовой службы/ В.А.Мищенко, И.Ф.Астахова, А.А.Краснояров// Вестник Воронежского государственного университета. Серия: Системный анализ и информационные технологии - 2011. - № 2 - С. 144-147.

Прочие публикации

5. Астахова И.Ф. Автоматизированное рабочее место секретаря Лис-кипского почтамта / И.Ф. Астахова, В.А. Мищенко // Современные проблемы механики и прикладной математики труды: межд. конф. - Воронеж: ВГУ , 2007. - Вып. 3,- С. 22-25.

6. Астахова И.Ф. Современные проблемы искусственного интеллекта / И.Ф. Астахова, К.В. Петров, В.А. Мищенко //Современные методы теории краевых задач: Мат-льг Воронежской мат. школы «Понтрягинские чтения». -Воронеж: ВГУ, 2010. - С. 10-11.

7. Мищенко В.А. Автоматизация работы Лискинского почтамта / В.А. Мищенко, Т.А. Емельянова // Труды молодых ученых ВГУ, 2007. - Вып. 1-2. -С. 24-31.

8. Мищенко В.А. Обучение искусственных нейронных сетей / В.А. Мищенко // Современные проблемы науки и образования. - Воронеж: ВГПУ, 2009. - № 6 ~ С. 9-10.

9. Мищенко В.А. Персептрон - как средство распознавания образов / В.А. Мищенко // Новые технологии в образовании. - Воронеж: ВГПУ, 2009. - №4.-С. 101-102.

10. Мищенхо В.А. Предварительная обработка изображений в задачах распознавания образов / В.А.Мищенко // Актуальные проблемы прикладной математики, информатики и механики. Дополнительная секция: Сб. трудов межд. конф. - Воронеж: Издательско-полиграфический центр ВГУ, 2011.-С. 30-34.

Свидетельства о государственной регистрации программ для ЭВМ

11. Мищенко В.А. Сортировочный участок: свидетельство о регистрации программы для ЭВМ / И.Ф.Астахова, В.А.Мищенко// Внесено в Реестр программ для ЭВМ 19.01.12; per. №2012610838.

Личный вклад автора в работах, наннсаппых в соавторстве:

[2] - организация нечетких нейронных сетей; [3,4] - организация обучения нейронных сетей; [5,7] - разработка информационной системы; [6] - рассмотрение проблем обучения нейронных сетей.

Подписано » печать J.(И. 13. Формат 60*84 '/Hl. Усл. псч. л. 0,93 Тираж 100 экч. Заказ 312.

Огпечатанс с готового оригинал-макета в типографии Иэдательско-полиграфического центра Воронежского государственного университета.

394000, Воронеж, ул. Пушкинская, 3

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

«ВОРОНЕЖСКИЙ ГОСУДАРСТВЕННЫЙ ПЕДАГОГИЧЕСКИЙ

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

Специальность 05.13.17 — Теоретические основы информатики

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

УНИВЕРСИТЕТ»

04201356855

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

Мищенко Вадим Анатольевич

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

доктор технических наук, профессор И.Ф. Астахова

Воронеж - 2013

Оглавление

Введение...................................................................................................................4

Глава I. Современные модели, методы и алгоритмы распознавания образов..4

1.1 Интеллектуальные системы распознавания образов.................................9

1.2. Обзор существующих моделей, методов и алгоритмов компьютерного зрения..................................................................................................................10

1.3 Нейронные сети - как инструмент в задачах распознавания..................11

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

1.5 Эволюционное моделирование для настройки нейронной нечеткой сети

в задачах распознавания образов.....................................................................19

Выводы................................................................................................................21

Глава II. Распознавание символов с помощью нейронных сетей....................23

2.1 Алгоритм предварительной обработки изображения..............................23

2.2 Бинаризация..................................................................................................24

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

2.4 Нейросетевые технологии...........................................................................34

2.4.1 Многослойный персептрон......................................................................34

2.4.2 Сеть Кохонена...........................................................................................37

2.4.3 Сеть Хемминга..........................................................................................41

2.4.4 Нечеткие нейронные сети. Сеть Ванга-Менделя..................................44

2.4.5 Оценка эффективности работы нейронных сетей.................................51

Выводы................................................................................................................52

Глава III. Настройка весовых коэффициентов, с помощью модифицированного генетического алгоритма..................................................53

3.1 Понятие генетического алгоритма.............................................................53

3.2 Адаптация алгоритма к решаемой задаче.................................................54

Выводы................................................................................................................70

Глава IV. Описание программного продукта.....................................................71

4.1 Интерфейс пользователя.............................................................................71

4.2 Взаимодействие функциональных блоков................................................79

4.3 Технологический процесс..........................................................................89

Выводы................................................................................................................90

Заключение.............................................................................................................91

Список используемой литературы.......................................................................92

Приложения.........................................................................................................103

Введение

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

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

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

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

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

Работа выполнялась на кафедре Информатики и методики преподавания математики Воронежского государственного педагогического университета в рамках Договора № ELSP/B1/С/016/10-06 от 27 апреля 2006 г. «Разработка программ и учебно-методических материалов для подготовки студентов педагогических вузов в области использования цифровых образовательных ресурсов» (2005-2008 гг.).

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

В рамках реализации поставленной цели необходимо решить следующие задачи:

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

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

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

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

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

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

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

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

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

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

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

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

работу оператора почтовой службы по сортировке письменной корреспонденции. Результаты работы внедрены и используются в Обособленном структурном подразделении Лискинский почтамт Управления Федеральной почтовой связи Воронежской области - филиал Федерального государственного унитарного предприятия «Почта России». Программа «Сортировочный участок» зарегистрирована в Федеральном институте промышленной собственности (ФИПС) (свидетельство №2012610838 от 19.01.12г.).

Основные результаты, выносимые на защиту. На защиту выносятся следующие результаты, полученные в процессе исследований:

1) модифицированный алгоритм предварительной обработки изображений;

2) генетический алгоритм с использованием особого оператора мутации;

3) модифицированная модель сети Ванга - Менделя;

4) программный комплекс, реализующий нейро-нечетко-генетическую систему распознавания.

Апробация работы. Основные результаты, представленные в диссертационной работе, докладывались и обсуждались на Математической конференции молодых преподавателей и студентов Лискинского филиала ВГУ (Воронеж, 2007);на научных сессиях Федерального государственного бюджетного образовательного учреждения высшего профессионального образования «Воронежский государственный педагогический университет» 2008-2009г.г.; на Международной конференции «Современные проблемы механики и прикладной математики» (Воронеж, 2007); на Всероссийской конференции «Современные методы теории краевых задач» (школа «Понтрягинские чтения», 2010); на XVIII Всероссийской Школе-Коллоквиуме по стохастическим методам и XII Всероссийском симпозиуме по прикладной и промышленной математике (Весенняя сессия) (Казань, 2011).

Публикации. Результаты диссертации опубликованы в 11 работах. Списку ВАК соответствуют работы [98-101]. Получено одно свидетельство государственной регистрации программы [108].

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

Структура и объем диссертации. Диссертация состоит из введения, 4 глав, разбитых на пункты, заключения, списка используемой литературы из 107 наименований и приложения. Общий объем диссертации - 134 страницы, приложение на 31 стр. Работа содержит 40 рисунков.

Область исследования. Диссертационная работа соответствует следующим пунктам паспорта специальности 05.13.17 - Теоретические основы информатики:

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

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

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

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

Глава I. Современные модели, методы и алгоритмы распознавания образов

1.1 Интеллектуальные системы распознавания образов

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

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

объема) [69]. Слабоинтеллектуальные системы тесно связаны с деятельностью человека, поэтому для каждого органа чувств разрабатываются искусственные аналоги (сенсоры, камеры, системы распознавания рукописного ввода и речи). Применительно к слабому ИИ, моделями человеческого зрения можно считать системы, построенные с использованием камер [69]. К интеллектуальной составляющей компьютерного зрения можно отнести алгоритмы, связанные с подготовкой изображения и получающие новую информацию

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

При построении систем распознавания образов используются следующие принципы: принцип общности свойств и принцип кластеризации. Для реализации основных принципов построения интеллектуальных распознающих систем существуют три основных метода: эвристический, математический и лингвистический (синтаксический). Примеры этих систем подробно описаны в [59].

1.2. Обзор существующих моделей, методов и алгоритмов компьютерного зрения

В настоящий момент существует много бесплатных программ в области компьютерного зрения, таких как библиотека 7кшск-Капас1е [6, 69]. Адаптация подобных библиотек к новым задачам является очень сложной

проблемой, иногда просто не решаемой, поэтому разработчики принимают решение о самостоятельной реализации известных и своих алгоритмов. Библиотека ОрепСУ является сейчас стандартом систем компьютерного зрения. В книгах по компьютерному зрению Д.Форсайт и Ж.Понс, а также Л.Шапиро и Дж.Стокман [1] рассматривают актуальные на настоящий момент модели камер. Искажения характерны для любой оптической системы, к ним относится дисторсия, яркость и другие геометрические искажения. Особенность устройства ПЗС (прибор с зарядовой связью)-матрицы, которая является проекционной поверхностью для снимаемой сцены, приводит к дополнительным искажениям. При моделировании камер ограничиваются моделями оптической системы.

Попытки формализовать понятие цифрового зрения сделаны в книгах Л.Шапиро и Дж. Стокмана [1, 93]. Разрабатываются модели последовательности изображений, получаемых с камеры. В.Крашенинников последовательность изображений трактует как дискретную размерность случайного поля, у него одно измерение соответствует номеру изображения в последовательности, а два измерения совпадают с измерениями изображения. В качестве модели последовательности изображений можно считать поток событий, который опи