Факультетматематики и компьютерных наук
Кафедраинформационной безопасности
Курсоваяработа
подисциплине «Языки программирования»
на тему «Распознаваниеобразов (на примере цифр)»
Т 2009 г.
Оглавление
Введение
Глава 1. Принципы распознавания образов
1.1 Система распознавание образов
1.2 Нейронные сети
1.2.1 Распознавание образов
Глава 2. Описание программного средства
2.1 Алгоритм
2.2 Техническая реализация
2.3 Описание пользовательского интерфейса
Заключение
Приложение 1
Список литературы
Введение
Программа предназначенадля распознавания цифр .
Основой программыявляется нейросеть, имитирующая искусственный интеллект, тем самым, позволяяобучать программу и запоминать образы цифр, для верного распознавания их припоследующем использовании программы.
Актуальность программыобусловлена популярностью на рынке программных продуктов подобного типа (дляраспознавания образов) и их широкого применения в КПК, смартфонах, ноутбуках,т.д… Программное обеспечение для распознавания образов разрабатывается многимикомпаниями и является одним из инновационных продуктов на современном рынке.
Глава 1
Принципыраспознавания образов
1.1 Системараспознавания образов
Задача распознавания(точнее, классификации) объекта ставится следующим образом. Имеется некоторыйспособ кодирования объектов (например, рукописных букв), принадлежащих заранееизвестному конечному множеству классов C={C1 ,...,Cq}, инекоторое конечное множество объектов (обучающее множество), про каждый изкоторых известно, какому классу он принадлежит. Нужно построить алгоритм, которыйпо любому входному объекту, не обязательно принадлежащему обучающему множеству,решает, какому классу этот объект принадлежит, и делает это достаточно хорошо.Качество распознавания оценивается как вероятность (т.е.частота) ошибкиклассификации на другом конечном множестве объектов с заранее известнымиответами (тестовом множестве).
Типичная системараспознавания состоит из трех частей: извлечение признаков, собственнораспознавание и принятие решения.
Извлечение признаков — это преобразование входных объектов к единообразному, компактному и удобномувиду с потерей подавляющей части содержащейся в объекте информации, слабовлияющей на классификацию. Удобным оказывается представление объекта точкойстандартного евклидова пространства Rd, принадлежащей некоторомуфиксированному компакту (кубу, шару, сфере, ...). Размерность d должна бытьдостаточно большой для успешного (в смысле качества) распознавания и достаточномалой для успешного (в смысле скорости) распознавания — реально это порядканескольких десятков. Способ извлечения признаков зависит от природы и исходнойкодировки объектов и подбирается вручную. Например, траекторию мыши или пера,исходно закодированную последовательностью произвольной длины (порядка сотни),состоящей из пар координат точки, удобно кодировать последовательностьюфиксированной длины пар коэффициентов аппроксимирующих траекторию полиномовнебольшой степени (порядка десятка), да еще и свободные члены можно отбросить,как не влияющие на классификацию. Желаемые значения F в точках пространствапризнаков, соответствующих обучающему множеству, известны, так что остаетсятолько построить в некотором смысле аппроксимирующее отображение. Качествоаппроксимации будет проверяться не на всей области определения, а только натестовом множестве. Интерпретацией вычисленных вероятностей занимаетсяотдельная от распознавания процедура принятия решений, которая строится вручнуюи не зависит ни от природы входных объектов, ни от пространства признаков, ниот обучающих данных. Она зависит только от того, для чего эта системараспознавания предназначена. Например, если она используется какбезответственная гадалка, то она просто выдает номер наиболее вероятногокласса. Если она используется как ответственная гадалка, то она выдает номернаиболее вероятного класса, если его вероятность существенно большевероятностей других классов, и отвечает ``не знаю'' в противном случае. Еслиона используется для генерации гипотез, то она выдает номера нескольких(например, пяти) наиболее вероятных классов и их вероятности.
В прошлом веке на урокахчистописания первоклассников сначала долго заставляли рисовать палочки,крючочки и кружочки, и только потом учили складывать из них буквы. В реальнойжизни люди тоже пишут (и распознают!) буквы как последовательности небольшихтиповых элементов, но не столь единообразных, как в прописях. Например, двевертикальные палочки, перечеркнутые горизонтальной, — это, вероятно, буква `Н'.И если вертикальные палочки — не совсем палочки или не совсем вертикальные, товсе равно `Н'. Но если они сверху сближаются, то больше похоже на `А', а еслигоризонтальная палочка находится высоко, то на `П'.
При машинномраспознавании удобнее выделять не только и не столько палочки и крючочки,сколько способы их стыковки друг с другом: направленные в разные стороныгалочки, петельки, Т-образные ветвления и т.п. Предположим, что эта черноваяработа проделана, и изучаемый фрагмент рукописного текста закодирован в видепоследовательности таких характеристических элементов, упорядоченных как-тослева направо сверху вниз. Вопрос: насколько эта последовательность похожа набукву `А'? Тот же вопрос для всех остальных распознаваемых символов.
Попробуем смоделироватьпостроение одной буквы в виде последовательности элементов. Во-первых, букваможет иметь несколько существенно различных написаний (например, `А'треугольное, `А' треугольное с завитушками, `А' круглое, ...) и их нужномоделировать отдельно. Во-вторых, даже одно написание одной буквы в зависимостиот почерка порождает разные последовательности характеристических элементов.В-третьих, кроме правильных написаний бывают неправильные (рука дрогнула,клякса, ручка плохо пишет, ...). Всех возможностей не предусмотришь, поэтомубудем моделировать только несколько наиболее часто встречающихся вариантов и то,что получается из них небольшими возмущениями.
Выписываниепоследовательности Qi1,...,QiL из L характеристическихэлементов поручим детерминированному конечному автомату с L+1 состояниями с1,..., сL+1,который в каждом l-м, l L, состоянии Cl порождает элемент Qilи переходит в следующее состояние. А для порождения возможных ``небольшихвозмущений'' последовательности превратим автомат в стохастический: в i-мсостоянии он может порождать любой элемент Qj с вероятностью bijи с вероятностью aij
переходить в близкое кi+1-му j-е состояние. Как правило, aij > 0 только при i j i+2, т.е. кроме перехода в следующее состояние допускаютсяпроскакивание его и задержка в текущем состоянии. Существенно, что aij=0при i > j. Такие модели называются LR-моделями (left-right, слева направо).Вероятности bi,ij и ai,i+1 унаследованных отдетерминированного автомата действий естественно полагать близкими к 1, аостальные положительные вероятности — близкими к 0, хотя это и не обязательно.Заметим, что каждое состояние детерминированного автомата имело точный смысл(``выписано столько-то элементов такой-то последовательности''), а устохастического автомата этот точный смысл уже утерян.
Автоматы для несколькихвариантов написания символа объединяются в один автомат, моделирующий символ: ких несвязному объединению добавляется общее начальное состояние C0,которое не порождает никакого характеристического элемента и из котороговозможны переходы в начальные и вторые состояния всех вариантов, а их конечныесостояния склеиваются.
Такая модель символапозволяет ответить на вопрос, насколько какая-то последовательностьхарактеристических элементов похожа на этот символ: настолько, каковавероятность порождения ее моделью символа. Эти вероятности можно вычислить длявсех символов и проанализировав их решить, на какой символ этапоследовательность более всего похожа, т.е. классифицировать ее.
Распознаваниепоследовательности объектов (например, слов) существенно отличается отраспознавания отдельных объектов (например, букв) тем, что разных длинныхпоследовательностей настолько много, что для обучения узнаванию каждойпоследовательности в лицо требуется абсолютно неприемлемое время. Еще болеенаглядный пример — распознавание молекул ДНК, являющихся очень длинными словамив алфавите из четырех букв. Поэтому для распознавания последовательностейприменяется следующая схема.
— Последовательностьболее или менее успешно сегментируется на индивидуальные объекты или на кусочкиобъектов. Алгоритмы сегментации существенно зависят от природы объектов.
— Каждый объект (илинабор смежных кусочков) более или менее успешно распознается, например, однимиз методов, описанных в разделе
— Из ответовраспознавателя объектов склеивается результат распознавания последовательностив целом. Алгоритмы склеивания могут быть специфичны для данных объектов(например, для распознавания слов на известном языке можно пользоватьсясловарем, а для распознавания слов на никому не известном языке, а могут быть иуниверсальны.
Тривиальный алгоритмраспознавания — сегментировать, распознать каждый кусочек и в качестве общегоответа выдать последовательность наиболее вероятных ответов — работает плохо.Он не исправляет ошибок сегментации и адекватен только распознаванию случайнойпоследовательности независимых хорошо разделенных объектов. Но во всехинтересных задачах распознавания последовательности не случайны, а в случаерукописного текста — еще и плохо разделимы.
1.2 Нейронныесети
Теория нейронных сетейвозникла в 40-60-х годах в результате совместных попыток физиологов икибернетиков понять и смоделировать работу мозга. Получилась следующая модель.Мозг состоит из очень большого числа (порядка 1011) клеток(нейронов), каждая из которых имеет длинный хвост (аксон) и большое число(порядка 104) ответвлений (дендритов), касающихся аксонов другихнейронов и/или входных рецепторов. Через эти зоны касания (синапсы) можетпередаваться информация (электрохимический потенциал).
Каждый нейрон являетсяпростеньким компьютером: потенциал нейрона (и его аксона, играющего роль выхода)является функцией от потенциалов синапсов его дендритов (входов), причемфункцией вполне определенного вида. А именно, каждый нейрон имеет дваустойчивых состояния (возбужденное и невозбужденное) и соответствующие имзначения потенциала, одинаковые для всех нейронов. Каждый нейрон вычисляетлинейную комбинацию потенциалов входных синапсов, сравнивает ее с пороговымзначением и переходит в возбужденное (невозбужденное) состояние если эталинейная комбинация больше (соответственно, меньше) порогового значения.
В совокупности мозгвычисляет некоторую вектор-функцию: зависимость потенциалов нейронов(достаточно рассматривать не все нейроны, а только связанные своими аксонами сисполнителями) от потенциалов входных рецепторов. А вся нетривиальность работымозга состоит в том, что пороговые значения (по одному на нейрон, итого порядка1011) и коэффициенты линейных комбинаций (по одному на дендрит,итого порядка 1015), вообще говоря, различны и могут изменяться современем. Это изменение коэффициентов называется обучением. Нейронная сетьпрямого распространения — это ориентированный ациклический граф с множествомвершин V и ребер E, вершины которого разбиты на слои следующим образом:
— нулевой слой состоит извершин-истоков (входных рецепторов) v0,1,...,v0,d;
— ребра (синапсы),входящие в вершины (нейроны) (k+1)-го слоя, выходят из вершин (рецепторов илинейронов) k-го слоя;
— все стоки (выходныенейроны) vL,1,...,yL,q принадлежат одному и тому же L-муслою.
Существует классификациянейронных сетей.
1. Многослойные нейронныесети
Архитектура многослойнойнейронной сети (МНС) состоит из последовательно соединённых слоёв, где нейронкаждого слоя своими входами связан со всеми нейронами предыдущего слоя, авыходами — следующего. НС с двумя решающими слоями может с любой точностьюаппроксимировать любую многомерную функцию. НС с одним решающим слоем способнаформировать линейные разделяющие поверхности, что сильно сужает круг задач имирешаемых, в частности такая сеть не сможет решить задачу типа «исключающееили». НС с нелинейной функцией активации и двумя решающими слоямипозволяет формировать любые выпуклые области в пространстве решений, а с тремярешающими слоями — области любой сложности, в том числе и невыпуклой.
При этом МНС не теряетсвоей обобщающей способности. Обучаются МНС при помощи алгоритма обратногораспространения ошибки, являющегося методом градиентного спуска в пространствевесов с целью минимизации суммарной ошибки сети. При этом ошибки (точнеевеличины коррекции весов) распространяется в обратном направлении от входов квыходам, сквозь веса, соединяющие нейроны.
2.Нейронные сети высокогопорядка
Нейронные сети высокогопорядка (НСВП) отличаются от МНС тем, что у них только один слой, но на входынейронов поступают так же термы высокого порядка, являющиеся произведением двухили более компонент входного вектора. Такие сети так же могут формироватьсложные разделяющие поверхности. Особенность такой сети заключаются в том, чтодля обучения некоторому классу достаточно предъявить его образ без вариациймасштабов и поворотов — после обучения сеть будет распознавать известные классыинвариантно к масштабу и поворотам. Такая сеть не является полносвязной, быстрообучается и работает. Отмечено существенное повышение точности классификациитакой сетью повёрнутых и масштабированных изображений по сравнению с МНС.
3.Нейронные сети Хопфилда
НС Хопфилда (НСХ)является однослойной и полносвязной (связи нейронов на самих себя отсутствуют),её выходы связаны со входами. В отличие от МНС, НСХ является релаксационной — т.е. будучи установленной в начальное состояние, функционирует до тех пор, покане достигнет стабильного состояния, которое и будет являться её выходнымзначением. НСХ применяются в качестве ассоциативной памяти и для решенияоптимизационных задач. В первом случае НСХ обучается без учителя (например, поправилу Хебба), во втором случае веса между нейронами изначально кодируютрешаемую задачу. НСХ бывают синхронными, когда одновременно пересчитываются всенейроны и асинхронными, когда пересчитывается случайно выбранный нейрон. Дляисследования динамики функционирования НСХ используются методы Ляпунова.
Показано, что асинхроннаяНСХ всегда сходится к устойчивым точкам, а аттракторами синхронной НСХ являютсяустойчивые стационарные точки и предельные циклы длины два. Таким образом НСХиз начального состояния сходится к ближайшему локальному минимуму энергии сети,состояние нейронов в котором и будет восстановленным образом для задачраспознавания, и решением — для оптимизационных задач. Для поиска глобальногоминимума применительно к оптимизационным задачам используют стохастическиемодификации НСХ.
4.Самоорганизующиесянейронные сети Кохонена
Самоорганизующиесянейронные сети Кохонена (СНСК) обеспечивают топологическое упорядочиваниевходного пространства образов. Они позволяют топологически непрерывноотображать входное n-мерное пространство в выходное m-мерное.
Нейронная сеть срадиально-базисной функцией (НСРБФ) является дальнейшим развитием НС Кохонена,в которой после конкурентного слоя добавлен ещё один слой, обучаемый по методуобратного распространения. В отличие от НС Кохонена в НСРБФ выходами нейроновконкурентного слоя являются значения функции Гаусса с нормальным закономраспределения, и обнуление не победивших нейронов не требуется. Ширина радиально-базиснойфункции характеризует расстояние между центром кластера, который образуетсякаждым нейронным элементом и его ближайшими соседями.
5.Когнитрон
Когнитрон своейархитектурой похож на строение зрительной коры, имеет иерархическуюмногослойную организацию, в которой нейроны между слоями связаны тольколокально. Обучается конкурентным обучением (без учителя). Каждый слой мозгареализует различные уровни обобщения; входной слой чувствителен к простымобразам, таким, как линии, и их ориентации в определенных областях визуальнойобласти, в то время как реакция других слоев является более сложной,абстрактной и независимой от позиции образа. Аналогичные функции реализованы вкогнитроне путем моделирования организации зрительной коры.
Неокогнитрон являетсядальнейшим развитием идеи когнитрона и более точно отражает строение зрительнойсистемы, позволяет распознавать образы независимо от их преобразований,вращений, искажений и изменений масштаба. Неокогнитрон может, каксамообучаться, так и обучаться с учителем. Неокогнитрон получает на входедвумерные образы, аналогичные изображениям на сетчатой оболочке глаза, иобрабатывает их в последующих слоях аналогично тому, как это было обнаружено взрительной коре человека. Конечно, в неокогнитроне нет ничего, ограничивающегоего использование только для обработки визуальных данных, он достаточноуниверсален и может найти широкое применение как обобщенная системараспознавания образов.
В зрительной коре былиобнаружены узлы, реагирующие на такие элементы, как линии и углы определеннойориентации. На более высоких уровнях узлы реагируют на более сложные иабстрактные образы такие, как окружности, треугольники и прямоугольники. На ещеболее высоких уровнях степень абстракции возрастает до тех пор, пока неопределятся узлы, реагирующие на лица и сложные формы. В общем случае узлы наболее высоких уровнях получают вход от группы низкоуровневых узлов и,следовательно, реагируют на более широкую область визуального поля. Реакцииузлов более высокого уровня менее зависят от позиции и более устойчивы кискажениям.
Когнитрон является мощнымсредством распознавания изображений, однако требует высоких вычислительныхзатрат, которые на сегодняшний день недостижимы.
В искусственных нейронныхсетях, как и в мозгу, все вычисления происходят параллельно, и тем самым, оченьбыстро. В реальности нейронные сети моделируются на обычных последовательныхкомпьютерах и работают довольно медленно, поэтому на количестве вершин и реберсети приходится экономить. В 80-е годы на волне повышенного интереса кпараллельным вычислениям были созданы и вполне действующие аппаратныереализации нейронных сетей.
1.2.1 Распознаваниеобразов
Нейронные сети непрограммируются в привычном смысле этого слова, они обучаются. Возможностьобучения — одно из главных преимуществ нейронных сетей перед традиционнымиалгоритмами. Технически обучение заключается в нахождении коэффициентов связеймежду нейронами. В процессе обучения нейронная сеть способна выявлять сложныезависимости между входными данными и выходными, а также выполнять обобщение.Это значит, что, в случае успешного обучения, сеть сможет вернуть верныйрезультат на основании данных, которые отсутствовали в обучающей выборке.
Подготовка и нормализация данных
Исходныеданные преобразуются к виду, в котором их можно подать на входы сети. Каждаязапись в файле данных называется обучающей парой или обучающим вектором.Обучающий вектор содержит по одному значению на каждый вход сети и, в зависимостиот типа обучения (с учителем или без), по одному значению для каждого выходасети. Обучение сети на «сыром» наборе, как правило, не дает качественныхрезультатов. Существует ряд способов улучшить «восприятие» сети.
Нормировкавыполняется, когда на различные входы подаются данные разной размерности.Например, на первый вход сети подается величины со значениями от нуля доединицы, а на второй — от ста до тысячи. При отсутствии нормировки значения навтором входе будут всегда оказывать существенно большее влияние на выход сети,чем значения на первом входе. При нормировке размерности всех входных ивыходных данных сводятся воедино.
Глава 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 – загрузкаиз файла
Списоклитературы
1. http://www.recognition.mccme.ru/pub/RecognitionLab.html/methods.html
2. http://daily.sec.ru/dailypblshow.cfm?rid=18&pid=4326