Распознавание образов (на примере цифр)
Факультет математики и компьютерных наук
Кафедра информационной безопасности
Курсовая работа
по дисциплине «Языки программирования»
на тему «Распознавание образов (на примере цифр)»
Т 2009 г.
Оглавление
Введение
Глава 1. Принципы распознавания образов
1.1 Система распознавание образов
1.2 Нейронные сети
1.2.1 Распознавание образов
Глава 2. Описание программного средства
2.1 Алгоритм
2.2 Техническая реализация
2.3 Описание пользовательского интерфейса
Заключение
Приложение 1
Список литературы
Введение
Программа предназначена для распознавания цифр .
Основой программы является нейросеть, имитирующая искусственный интеллект, тем самым, позволяя обучать программу и запоминать образы цифр, для верного распознавания их при последующем использовании программы.
Актуальность программы обусловлена популярностью на рынке программных продуктов подобного типа (для распознавания образов) и их широкого применения в КПК, смартфонах, ноутбуках, т.д.. Программное обеспечение для распознавания образов разрабатывается многими компаниями и является одним из инновационных продуктов на современном рынке.
Глава 1
Принципы распознавания образов
Система распознавания образов
Задача распознавания (точнее, классификации) объекта ставится следующим образом. Имеется некоторый способ кодирования объектов (например, рукописных букв), принадлежащих заранее известному конечному множеству классов C={C>1> ,...,C>q>}, и некоторое конечное множество объектов (обучающее множество), про каждый из которых известно, какому классу он принадлежит. Нужно построить алгоритм, который по любому входному объекту, не обязательно принадлежащему обучающему множеству, решает, какому классу этот объект принадлежит, и делает это достаточно хорошо. Качество распознавания оценивается как вероятность (т.е.частота) ошибки классификации на другом конечном множестве объектов с заранее известными ответами (тестовом множестве).
Типичная система распознавания состоит из трех частей: извлечение признаков, собственно распознавание и принятие решения.
Извлечение признаков - это преобразование входных объектов к единообразному, компактному и удобному виду с потерей подавляющей части содержащейся в объекте информации, слабо влияющей на классификацию. Удобным оказывается представление объекта точкой стандартного евклидова пространства Rd, принадлежащей некоторому фиксированному компакту (кубу, шару, сфере, ...). Размерность d должна быть достаточно большой для успешного (в смысле качества) распознавания и достаточно малой для успешного (в смысле скорости) распознавания - реально это порядка нескольких десятков. Способ извлечения признаков зависит от природы и исходной кодировки объектов и подбирается вручную. Например, траекторию мыши или пера, исходно закодированную последовательностью произвольной длины (порядка сотни), состоящей из пар координат точки, удобно кодировать последовательностью фиксированной длины пар коэффициентов аппроксимирующих траекторию полиномов небольшой степени (порядка десятка), да еще и свободные члены можно отбросить, как не влияющие на классификацию. Желаемые значения F в точках пространства признаков, соответствующих обучающему множеству, известны, так что остается только построить в некотором смысле аппроксимирующее отображение. Качество аппроксимации будет проверяться не на всей области определения, а только на тестовом множестве. Интерпретацией вычисленных вероятностей занимается отдельная от распознавания процедура принятия решений, которая строится вручную и не зависит ни от природы входных объектов, ни от пространства признаков, ни от обучающих данных. Она зависит только от того, для чего эта система распознавания предназначена. Например, если она используется как безответственная гадалка, то она просто выдает номер наиболее вероятного класса. Если она используется как ответственная гадалка, то она выдает номер наиболее вероятного класса, если его вероятность существенно больше вероятностей других классов, и отвечает ``не знаю'' в противном случае. Если она используется для генерации гипотез, то она выдает номера нескольких (например, пяти) наиболее вероятных классов и их вероятности.
В прошлом веке на уроках чистописания первоклассников сначала долго заставляли рисовать палочки, крючочки и кружочки, и только потом учили складывать из них буквы. В реальной жизни люди тоже пишут (и распознают!) буквы как последовательности небольших типовых элементов, но не столь единообразных, как в прописях. Например, две вертикальные палочки, перечеркнутые горизонтальной, - это, вероятно, буква `Н'. И если вертикальные палочки - не совсем палочки или не совсем вертикальные, то все равно `Н'. Но если они сверху сближаются, то больше похоже на `А', а если горизонтальная палочка находится высоко, то на `П'.
При машинном распознавании удобнее выделять не только и не столько палочки и крючочки, сколько способы их стыковки друг с другом: направленные в разные стороны галочки, петельки, Т-образные ветвления и т.п. Предположим, что эта черновая работа проделана, и изучаемый фрагмент рукописного текста закодирован в виде последовательности таких характеристических элементов, упорядоченных как-то слева направо сверху вниз. Вопрос: насколько эта последовательность похожа на букву `А'? Тот же вопрос для всех остальных распознаваемых символов.
Попробуем смоделировать построение одной буквы в виде последовательности элементов. Во-первых, буква может иметь несколько существенно различных написаний (например, `А' треугольное, `А' треугольное с завитушками, `А' круглое, ...) и их нужно моделировать отдельно. Во-вторых, даже одно написание одной буквы в зависимости от почерка порождает разные последовательности характеристических элементов. В-третьих, кроме правильных написаний бывают неправильные (рука дрогнула, клякса, ручка плохо пишет, ...). Всех возможностей не предусмотришь, поэтому будем моделировать только несколько наиболее часто встречающихся вариантов и то, что получается из них небольшими возмущениями.
Выписывание последовательности Q>i1>,...,Q>iL> из L характеристических элементов поручим детерминированному конечному автомату с L+1 состояниями с>1>,...,с>L+1>, который в каждом l-м, l L, состоянии C>l> порождает элемент Q>il> и переходит в следующее состояние. А для порождения возможных ``небольших возмущений'' последовательности превратим автомат в стохастический: в i-м состоянии он может порождать любой элемент Q>j> с вероятностью b>ij> и с вероятностью a>ij>
переходить в близкое к i+1-му j-е состояние. Как правило, a>ij> > 0 только при i j i+2, т.е. кроме перехода в следующее состояние допускаются проскакивание его и задержка в текущем состоянии. Существенно, что a>ij>=0 при i > j. Такие модели называются LR-моделями (left-right, слева направо). Вероятности b>i,ij> и a>i,i+1> унаследованных от детерминированного автомата действий естественно полагать близкими к 1, а остальные положительные вероятности - близкими к 0, хотя это и не обязательно. Заметим, что каждое состояние детерминированного автомата имело точный смысл (``выписано столько-то элементов такой-то последовательности''), а у стохастического автомата этот точный смысл уже утерян.
Автоматы для нескольких вариантов написания символа объединяются в один автомат, моделирующий символ: к их несвязному объединению добавляется общее начальное состояние C>0>, которое не порождает никакого характеристического элемента и из которого возможны переходы в начальные и вторые состояния всех вариантов, а их конечные состояния склеиваются.
Такая модель символа позволяет ответить на вопрос, насколько какая-то последовательность характеристических элементов похожа на этот символ: настолько, какова вероятность порождения ее моделью символа. Эти вероятности можно вычислить для всех символов и проанализировав их решить, на какой символ эта последовательность более всего похожа, т.е. классифицировать ее.
Распознавание последовательности объектов (например, слов) существенно отличается от распознавания отдельных объектов (например, букв) тем, что разных длинных последовательностей настолько много, что для обучения узнаванию каждой последовательности в лицо требуется абсолютно неприемлемое время. Еще более наглядный пример - распознавание молекул ДНК, являющихся очень длинными словами в алфавите из четырех букв. Поэтому для распознавания последовательностей применяется следующая схема.
- Последовательность более или менее успешно сегментируется на индивидуальные объекты или на кусочки объектов. Алгоритмы сегментации существенно зависят от природы объектов.
- Каждый объект (или набор смежных кусочков) более или менее успешно распознается, например, одним из методов, описанных в разделе
- Из ответов распознавателя объектов склеивается результат распознавания последовательности в целом. Алгоритмы склеивания могут быть специфичны для данных объектов (например, для распознавания слов на известном языке можно пользоваться словарем, а для распознавания слов на никому не известном языке, а могут быть и универсальны.
Тривиальный алгоритм распознавания - сегментировать, распознать каждый кусочек и в качестве общего ответа выдать последовательность наиболее вероятных ответов - работает плохо. Он не исправляет ошибок сегментации и адекватен только распознаванию случайной последовательности независимых хорошо разделенных объектов. Но во всех интересных задачах распознавания последовательности не случайны, а в случае рукописного текста - еще и плохо разделимы.
Нейронные сети
Теория нейронных сетей возникла в 40-60-х годах в результате совместных попыток физиологов и кибернетиков понять и смоделировать работу мозга. Получилась следующая модель. Мозг состоит из очень большого числа (порядка 1011) клеток (нейронов), каждая из которых имеет длинный хвост (аксон) и большое число (порядка 104) ответвлений (дендритов), касающихся аксонов других нейронов и/или входных рецепторов. Через эти зоны касания (синапсы) может передаваться информация (электрохимический потенциал).
Каждый нейрон является простеньким компьютером: потенциал нейрона (и его аксона, играющего роль выхода) является функцией от потенциалов синапсов его дендритов (входов), причем функцией вполне определенного вида. А именно, каждый нейрон имеет два устойчивых состояния (возбужденное и невозбужденное) и соответствующие им значения потенциала, одинаковые для всех нейронов. Каждый нейрон вычисляет линейную комбинацию потенциалов входных синапсов, сравнивает ее с пороговым значением и переходит в возбужденное (невозбужденное) состояние если эта линейная комбинация больше (соответственно, меньше) порогового значения.
В совокупности мозг вычисляет некоторую вектор-функцию: зависимость потенциалов нейронов (достаточно рассматривать не все нейроны, а только связанные своими аксонами с исполнителями) от потенциалов входных рецепторов. А вся нетривиальность работы мозга состоит в том, что пороговые значения (по одному на нейрон, итого порядка 1011) и коэффициенты линейных комбинаций (по одному на дендрит, итого порядка 1015), вообще говоря, различны и могут изменяться со временем. Это изменение коэффициентов называется обучением. Нейронная сеть прямого распространения - это ориентированный ациклический граф с множеством вершин V и ребер E, вершины которого разбиты на слои следующим образом:
- нулевой слой состоит из вершин-истоков (входных рецепторов) v> 0,1>,...,v>0,d>;
- ребра (синапсы), входящие в вершины (нейроны) (k+1)-го слоя, выходят из вершин (рецепторов или нейронов) k-го слоя;
- все стоки (выходные нейроны) v>L,1>,...,y>L,q> принадлежат одному и тому же L-му слою.
Существует классификация нейронных сетей.
1. Многослойные нейронные сети
Архитектура многослойной нейронной сети (МНС) состоит из последовательно соединённых слоёв, где нейрон каждого слоя своими входами связан со всеми нейронами предыдущего слоя, а выходами - следующего. НС с двумя решающими слоями может с любой точностью аппроксимировать любую многомерную функцию. НС с одним решающим слоем способна формировать линейные разделяющие поверхности, что сильно сужает круг задач ими решаемых, в частности такая сеть не сможет решить задачу типа "исключающее или". НС с нелинейной функцией активации и двумя решающими слоями позволяет формировать любые выпуклые области в пространстве решений, а с тремя решающими слоями - области любой сложности, в том числе и невыпуклой.
При этом МНС не теряет своей обобщающей способности. Обучаются МНС при помощи алгоритма обратного распространения ошибки, являющегося методом градиентного спуска в пространстве весов с целью минимизации суммарной ошибки сети. При этом ошибки (точнее величины коррекции весов) распространяется в обратном направлении от входов к выходам, сквозь веса, соединяющие нейроны.
2.Нейронные сети высокого порядка
Нейронные сети высокого порядка (НСВП) отличаются от МНС тем, что у них только один слой, но на входы нейронов поступают так же термы высокого порядка, являющиеся произведением двух или более компонент входного вектора. Такие сети так же могут формировать сложные разделяющие поверхности. Особенность такой сети заключаются в том, что для обучения некоторому классу достаточно предъявить его образ без вариаций масштабов и поворотов - после обучения сеть будет распознавать известные классы инвариантно к масштабу и поворотам. Такая сеть не является полносвязной, быстро обучается и работает. Отмечено существенное повышение точности классификации такой сетью повёрнутых и масштабированных изображений по сравнению с МНС.
3.Нейронные сети Хопфилда
НС Хопфилда (НСХ) является однослойной и полносвязной (связи нейронов на самих себя отсутствуют), её выходы связаны со входами. В отличие от МНС, НСХ является релаксационной - т.е. будучи установленной в начальное состояние, функционирует до тех пор, пока не достигнет стабильного состояния, которое и будет являться её выходным значением. НСХ применяются в качестве ассоциативной памяти и для решения оптимизационных задач. В первом случае НСХ обучается без учителя (например, по правилу Хебба), во втором случае веса между нейронами изначально кодируют решаемую задачу. НСХ бывают синхронными, когда одновременно пересчитываются все нейроны и асинхронными, когда пересчитывается случайно выбранный нейрон. Для исследования динамики функционирования НСХ используются методы Ляпунова.
Показано, что асинхронная НСХ всегда сходится к устойчивым точкам, а аттракторами синхронной НСХ являются устойчивые стационарные точки и предельные циклы длины два. Таким образом НСХ из начального состояния сходится к ближайшему локальному минимуму энергии сети, состояние нейронов в котором и будет восстановленным образом для задач распознавания, и решением - для оптимизационных задач. Для поиска глобального минимума применительно к оптимизационным задачам используют стохастические модификации НСХ.
4.Самоорганизующиеся нейронные сети Кохонена
Самоорганизующиеся нейронные сети Кохонена (СНСК) обеспечивают топологическое упорядочивание входного пространства образов. Они позволяют топологически непрерывно отображать входное n-мерное пространство в выходное m-мерное.
Нейронная сеть с радиально-базисной функцией (НСРБФ) является дальнейшим развитием НС Кохонена, в которой после конкурентного слоя добавлен ещё один слой, обучаемый по методу обратного распространения. В отличие от НС Кохонена в НСРБФ выходами нейронов конкурентного слоя являются значения функции Гаусса с нормальным законом распределения, и обнуление не победивших нейронов не требуется. Ширина радиально-базисной функции характеризует расстояние между центром кластера, который образуется каждым нейронным элементом и его ближайшими соседями.
5.Когнитрон
Когнитрон своей архитектурой похож на строение зрительной коры, имеет иерархическую многослойную организацию, в которой нейроны между слоями связаны только локально. Обучается конкурентным обучением (без учителя). Каждый слой мозга реализует различные уровни обобщения; входной слой чувствителен к простым образам, таким, как линии, и их ориентации в определенных областях визуальной области, в то время как реакция других слоев является более сложной, абстрактной и независимой от позиции образа. Аналогичные функции реализованы в когнитроне путем моделирования организации зрительной коры.
Неокогнитрон является дальнейшим развитием идеи когнитрона и более точно отражает строение зрительной системы, позволяет распознавать образы независимо от их преобразований, вращений, искажений и изменений масштаба. Неокогнитрон может, как самообучаться, так и обучаться с учителем. Неокогнитрон получает на входе двумерные образы, аналогичные изображениям на сетчатой оболочке глаза, и обрабатывает их в последующих слоях аналогично тому, как это было обнаружено в зрительной коре человека. Конечно, в неокогнитроне нет ничего, ограничивающего его использование только для обработки визуальных данных, он достаточно универсален и может найти широкое применение как обобщенная система распознавания образов.
В зрительной коре были обнаружены узлы, реагирующие на такие элементы, как линии и углы определенной ориентации. На более высоких уровнях узлы реагируют на более сложные и абстрактные образы такие, как окружности, треугольники и прямоугольники. На еще более высоких уровнях степень абстракции возрастает до тех пор, пока не определятся узлы, реагирующие на лица и сложные формы. В общем случае узлы на более высоких уровнях получают вход от группы низкоуровневых узлов и, следовательно, реагируют на более широкую область визуального поля. Реакции узлов более высокого уровня менее зависят от позиции и более устойчивы к искажениям.
Когнитрон является мощным средством распознавания изображений, однако требует высоких вычислительных затрат, которые на сегодняшний день недостижимы.
В искусственных нейронных сетях, как и в мозгу, все вычисления происходят параллельно, и тем самым, очень быстро. В реальности нейронные сети моделируются на обычных последовательных компьютерах и работают довольно медленно, поэтому на количестве вершин и ребер сети приходится экономить. В 80-е годы на волне повышенного интереса к параллельным вычислениям были созданы и вполне действующие аппаратные реализации нейронных сетей.
Распознавание образов
Нейронные сети не программируются в привычном смысле этого слова, они обучаются. Возможность обучения — одно из главных преимуществ нейронных сетей перед традиционными алгоритмами. Технически обучение заключается в нахождении коэффициентов связей между нейронами. В процессе обучения нейронная сеть способна выявлять сложные зависимости между входными данными и выходными, а также выполнять обобщение. Это значит, что, в случае успешного обучения, сеть сможет вернуть верный результат на основании данных, которые отсутствовали в обучающей выборке.
Подготовка и нормализация данных
Исходные данные преобразуются к виду, в котором их можно подать на входы сети. Каждая запись в файле данных называется обучающей парой или обучающим вектором. Обучающий вектор содержит по одному значению на каждый вход сети и, в зависимости от типа обучения (с учителем или без), по одному значению для каждого выхода сети. Обучение сети на «сыром» наборе, как правило, не дает качественных результатов. Существует ряд способов улучшить «восприятие» сети.
Нормировка выполняется, когда на различные входы подаются данные разной размерности. Например, на первый вход сети подается величины со значениями от нуля до единицы, а на второй — от ста до тысячи. При отсутствии нормировки значения на втором входе будут всегда оказывать существенно большее влияние на выход сети, чем значения на первом входе. При нормировке размерности всех входных и выходных данных сводятся воедино.
Глава 2
Описание программного средства
2.1 Алгоритм
Программа основана на наборе матриц (9 матриц – по одной на каждую цифру [1..9]), содержащих набор координат. Совокупность координат матрицы формирует образ цифры.
Считывание координат происходит по пикселям, начиная с верхнего левого угла.
Программа переносит координаты пикселей в резервную матрицу опять же по координатам. Далее в цикле программа по каждой координате сравнивает полученную матрицу с девятью матрицами, хранящимися в файле Bank.bnk, при этом учитывая коэффициент схожести. При наибольшем совпадении программа вычисляет, что нарисована именно эта цифра, и выводит результат на экран.
При использовании функции запоминания в работу вступает нейросеть. Первоначально нейросеть нормализует входящие данные, а далее в файле Bank.bnk производит перезапись координат в эталонных матрицах, допуская бесконечно малую погрешность, для того, чтобы при распознавании последующих образов устанавливалось не 100% соответствие, по которому нельзя распознавать различные образы. Тем самым, погрешность соответствия в программе допускает написание разными людьми абсолютно разных по характеру написания цифр.
2.2 Техническая реализация
Программа реализована на языке программирования Borland Delphi 2003, с помощью классов. 4 прилагающихся к программе шаблона (подложки к рабочему окну) разработаны в программе Adobe Photoshop. Шаблоны находятся в одной папке с исходным кодом программы, и в данной реализации подложка под главное окно программы выбирается самим программистом-разработчиком. В дальнейшем, возможно, предусмотреть выбор подложки пользователем программы.
Шаблоны исходных матриц находятся в одной папке с исходным кодом программы в файле Bank.bnk.
2.3 Описание пользовательского интерфейса
При запуске файла Neuro_40.exe пользователь видит главное окно программы. Подложкой главного окна программы является один из шаблонов, прилагающихся к программе. В центре окна находится окно для рисования цифр. Внизу этого окна располагаются три кнопки: Запомнить, Распознать, Очистить. С помощью кнопки Распознать пользователь может обучить свою программу, т.е. научить распознавать её данный образ цифры. С помощью кнопки Распознать пользователь может распознать нарисованный им образ, а с помощью кнопки Очистить пользователь может очистить окно для рисования.
Рис. 1 Главное окно программы
Пользователь может рисовать цифры в окне для рисования с помощью мыши или графического планшета.
Рис. 2 Результат распознавания цифры
Рис. 3 Различные подложки для программы
Так же пользователь может обучать программу. При обучении программы процент ошибочного распознавания будет минимизироваться.
Рис. 4 Процесс запоминания цифры
Заключение
Безусловно, существует множество направлений по развитию данной программы. Возможно, осуществить распознавание не только цифр, но и других символов, причём следующих подряд (т.е. распознавание чисел или текста), по аналогичному алгоритму, так же существует потенциал по изменению способов ввода символов, например, имитируя написание на бумаге или вырезания их на дереве, т.е. возможно имитировать различные текстуры и написание символов на данных текстурах различными предметами. Следовательно, программа станет ещё более привлекательной для пользователя и конкурентоспособной на современном рынке.
Программа может быть полезна и при обучении студентов, и при разработке различного программного обеспечения для персональных компьютеров.
Приложение 1
Техническое описание программы
1). Класс T8Bit - восьмибитная картинка
Методы:
Pixels – считывание попиксельно параметров картинки
Init – инициализация
Clear – удаление информации о пикселях картинки
Свойства:
Pixels – параметры картинки
2). TNeuro – резервная матрица, в которую считываются координаты
пикселей картинки из главного окна программы
Методы:
Clear – очистка матрицы
Normalize – нормализация
MemoryFrom – считывание значений
CompareWith – проверка на совместимость с шаблонами
GetFromBitmap – получение данных о картинке
3). TNeuroBank - совокупность матриц-шаблонов
ClearAll – удаление всех значений
SaveToFile – сохранение в файл
LoadFromFile – загрузка из файла
Список литературы
http://www.recognition.mccme.ru/pub/RecognitionLab.html/methods.html
http://daily.sec.ru/dailypblshow.cfm?rid=18&pid=4326