Обзор методов распознавания изображений

Размещено на http://www.allbest.ru/

1. ОБЗОР МЕТОДОВ РАСПОЗНАВАНИЯ ИЗОБРАЖЕНИЙ

1.1 Основные понятия

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

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

плоскопараллельному смещению;

повороту вокруг оси объектива;

масштабированию;

перспективным преобразованиям;

деформированию;

плавному или произвольному изменению яркости/цвета/контраста.

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

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

1.2.1 Бинарное представление исходного изображение

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

К достоинствам данного набора признаков:

Простота извлечения

Приемлемая точность распознавания при большой базе изображений

Недостатки данного метода

Медленная скорость работы и большой объем памяти

Отсутствие инвариантности к масштабу, сдвигу наклону изображений

1.2.2 Статистические признаки

Рукописный символ может быть описан с помощью простых статистических характеристик: мат. ожидания, дисперсии, моментов более высокого порядка. Также могут использоваться инвариантные относительно поворота кольцевые признаки (ring features) и признаки Цернике (Zernike features).

Момент порядка (p+q) применительно к изображению определяется как

(1.9)

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

Кольцевые признаки определяются как

(1.10)

где

(1.11)

-толщина кольца

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

Достоинства данных признаков:

Инвариантность относительно сдвига, масштаба, поворота, незначительному шуму.

Недостатки:

Чувствительность к различным стилям написания символов

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

1.2.3 Фурье дескрипторы

Рассмотрим каждую пару координат как комплексное число:

s(k) = x(k)+iy(k)

для k = 0, 1, 2,..., К- 1. Таким образом, х и у рассматриваются как действительная и мнимая оси для последовательности комплексных чисел. Такое представление имеет одно крупное преимущество: оно позволяет свести двумерную задачу к одномерной. Дискретное преобразование Фурье задается уравнением

Комплексные коэффициенты а(u) называются фурье-дескрипторами. Обратное преобразование Фурье, примененное к этим коэффициентам, позволяет восстановить границу:

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

Достоинства:

Высокая помехоустойчивость

Быстрая скорость работы

Недостатки:

Чувствительность к различным стилям написания

Отсутствие инвариантности к геометрическим преобразованиям

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

1.2.4 Геометрические признаки

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

1) отношение вертикального и горизонтального объекта

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

3) Наличие скачков в профиле символа

4) Протяженность линий вдоль одного из направлений в заданном секторе

5) Количество пересечений линий с вертикальными и горизонтальными линиями.

6) Высота и щирина символа.

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

К недостаткам данных методов можно отнести чувствительность к шуму и стилям написания.

1.2.5 Топологические характеристики

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

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

1.2.6 Векторное представление объекта

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

Достоинства:

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

Недостатки:

Зависимость от качества предварительной обработки

2) Чувствительность к нестандартному написанию, случайным штрихам

3)Сложность реализации

1.3Распознание на основе теории решений

1.3.1 Определения теории решений

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

(1.1)

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

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

(1.2)

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

(1.3)

Тогда для образов из класса и для образов из класса .

Далее рассмотрим основные виды классификаторов, применяемых в распознавателях основанных на теории решений.

1.3.2 Классификаторы теории решений

1.3.2.1 Сопоставление

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

1.3.2.2 Корреляционное сопоставление

В самой простой форме корреляция между изображениями f(x, у) и w(x, у) задается выражением

(1.8)

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

1.3.2.3 Классификатор Байеса

Стратегия Байеса используется при наличии полной априорной информации о классах, то есть известны:

Функция правдоподобия для каждого класса

Матрица штрафов

Априорные вероятности для каждого класса

Стратегия строится таким образом, чтобы обеспечить минимум общего риска

где -средняя величина потерь, при отнесении вектора y к классу j,-вероятность появления объекта из класса ,p(y)-безусловная плотность вероятности y,-элемент матрицы потерь, -вероятность того, что классификатор принимает решение отнести объект к классу j, когда он принадлежит к классу l.

1.3.2.4 Нейронные сети

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

1.4 Структурные методы распознавания

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

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

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

1.5 Сравнение подходов применяемых для распознавания рукописных символов

Алгоритмы большинства коммерческих продуктов, использующих off-line распознавание рукописных символов, как правило не раскрываются. Тем не менее, анализ публикаций позволяет сделать некоторые выводы. В системе распознавания рукописных символов от фирмы КРОК, которая применялась во время всероссийской переписи населения 2002 года и при проведении Единого гос. экзамена, используются структурные методы распознавания. Что касается точности данной системы, то утверждается, что одна ошибка приходилась на несколько тысяч правильно распознанных символов. В реальности ошибка гораздо выше, так как здесь же утверждается, что использования формально-логических и орфографических правил позволило снизить ошибку в несколько раз. В другом известном продукте ABBY FormReader используются как традиционные растровые методы(зарекомендовавшие себя при работе с печатными символами) так и структурные. Присутствует лингвистическая проверка. Разработчиками утверждается, что в некоторых проектах точность достигает 98%.

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

Стоит также отметить, что при использовании численных характеристик в распознавании образов, нейронные сети значительно выигрывают у статистических классификаторов, таких как Байесовский. Об этом, в частности, могут свидельствовать приведенные в цифры: при распознании 10 рукописных цифр, на основе геометрических характеристик, на проверочной выборки из 210000 символов, нейро-сетевой классификатор 97.3% правильно распознанных символов, байесовский -92.7%.

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

2. НЕЙРОННЫЕ СЕТИ

2.1 Основные положения

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

Модели нейронной сети (НС) могут быть программного и аппаратного исполнения. В дальнейшем речь пойдет о первом типе.

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

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

Рисунок 2.1- Искусственный нейрон

Текущее состояние нейрона определяется, как взвешенная сумма его входов:

(2.1)

Выход нейрона есть функция его состояния:

y = f(s) (2.2)

2.2 Виды активационных функций

Нелинейная функция f называется активационной и может иметь различный вид, как показано на рисунке 2.2. Одной из наиболее распространенных является нелинейная функция с насыщением, так называемая логистическая функция или сигмоид (т.е. функция S-образного вида):

(2.3)

Рисунок 2.2-Виды активационных функций

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

в) сигмоид - гиперболический тангенс; г) сигмоид - формула (2.3)

При уменьшении сигмоид становится более пологим, в пределе при =0 вырождаясь в горизонтальную линию на уровне 0.5, при увеличении сигмоид приближается по внешнему виду к функции единичного скачка с порогом T в точке x=0. Из выражения для сигмоида очевидно, что выходное значение нейрона лежит в диапазоне [0,1]. Одно из ценных свойств сигмоидной функции - простое выражение для ее производной, применение которого будет рассмотрено в дальнейшем.

(2.4)

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

2.3 Принцип работы, нейронной сети вида перцептрона

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

символ рукописный распознавание

, k=1...m (2.5)

Каждая полученная область является областью определения отдельного класса. Число таких классов для одной НС перцептронного типа не превышает 2m, где m - число выходов сети. Однако не все из них могут быть разделимы данной НС.

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

Рисунок 2.3-Пример линейно-неразделимого множества

Уравнение сети для этого случая

(2.6)

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

Рисунок 2.5-Пример результата работы нейронной сети

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

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

2.4 Радиально-базисные функции

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

(2.7)

(2.8)

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

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

(2.9)

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

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

2.5 Алгоритм обратного распространения

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

Согласно методу наименьших квадратов, минимизируемой целевой функцией ошибки НС является величина:

(2.10)

где - реальное выходное состояние нейрона j выходного слоя N нейронной сети при подаче на ее входы p-го образа; djp - идеальное (желаемое) выходное состояние этого нейрона.

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

(2.11)

Здесь wij - весовой коэффициент синаптической связи, соединяющей i-ый нейрон слоя n-1 с j-ым нейроном слоя n, - коэффициент скорости обучения, 0<<1.

Как показано в

(2.12)

Здесь под yj, как и раньше, подразумевается выход нейрона j, а под sj - взвешенная сумма его входных сигналов, то есть аргумент активационной функции. Так как множитель dyj/dsj является производной этой функции по ее аргументу, из этого следует, что производная активационной функция должна быть определена на всей оси абсцисс. В связи с этим функция единичного скачка и прочие активационные функции с неоднородностями не подходят для рассматриваемых НС. В них применяются такие гладкие функции, как гиперболический тангенс или классический сигмоид с экспонентой. В случае гиперболического тангенса

(2.13)

Третий множитель sj/wij, очевидно, равен выходу нейрона предыдущего слоя yi(n-1).

Что касается первого множителя в (2.12), он легко раскладывается следующим образом

(2.14)

Здесь суммирование по k выполняется среди нейронов слоя n+1.

Введя новую переменную

(2.15)

мы получим рекурсивную формулу для расчетов величин j(n) слоя n из величин k(n+1) более старшего слоя n+1.

(2.16)

Для выходного же слоя

(2.17)

Теперь мы можем записать (2.11) в раскрытом виде:

(2.18)

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

(2.19)

где - коэффициент инерционности, t - номер текущей итерации.

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

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

(2.20)

где M - число нейронов в слое n-1 с учетом нейрона с постоянным выходным состоянием +1, задающего смещение; yi(n-1)=xij(n) - i-ый вход нейрона j слоя n.

yj(n) = f(sj(n)), где f() - сигмоид (2.21)

yq(0)=Iq, (2.22)

где Iq - q-ая компонента вектора входного образа.

2. Рассчитать (N) для выходного слоя по формуле (8).

Рассчитать по формуле (2.18) или (2.19) изменения весов w(N) слоя N.

3. Рассчитать по формулам (2.14) и (2.16) (или (2.15) и (2.17)) соответственно (n) и w(n) для всех остальных слоев, n=N-1,...1.

4. Скорректировать все веса в НС

(2.23)

5. Если ошибка сети существенна, перейти на шаг 1. В противном случае - конец.

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

Теперь коснемся вопроса емкости НС, то есть числа образов, предъявляемых на ее входы, которые она способна научиться распознавать. Для сетей с числом слоев больше двух, он остается открытым. Как показано в для НС с двумя слоями, то есть выходным и одним скрытым слоем, детерминистская емкость сети Cd оценивается так:

(2.24)

где Nw - число подстраиваемых весов, Ny - число нейронов в выходном слое.

Следует отметить, что данное выражение получено с учетом некоторых ограничений. Во-первых, число входов Nx и нейронов в скрытом слое Nh должно удовлетворять неравенству Nx+Nh>Ny. Во-вторых, Nw/Ny>1000. Однако вышеприведенная оценка выполнялась для сетей с активационными функциями нейронов в виде порога, а емкость сетей с гладкими активационными функциями, обычно больше. Кроме того, фигурирующее в названии емкости прилагательное "детерминистский" означает, что полученная оценка емкости подходит абсолютно для всех возможных входных образов, которые могут быть представлены Nx входами. В действительности распределение входных образов, как правило, обладает некоторой регулярностью, что позволяет НС проводить обобщение и, таким образом, увеличивать реальную емкость. Так как распределение образов, в общем случае, заранее не известно, мы можем говорить о такой емкости только предположительно, но обычно она раза в два превышает емкость детерминистскую.

В продолжение разговора о емкости НС логично затронуть вопрос о требуемой мощности выходного слоя сети, выполняющего окончательную классификацию образов. Дело в том, что для разделения множества входных образов, например, по двум классам достаточно всего одного выхода. При этом каждый логический уровень - "1" и "0" - будет обозначать отдельный класс. На двух выходах можно закодировать уже 4 класса и так далее. Однако результаты работы сети, организованной таким образом, можно сказать - "под завязку", - не очень надежны. Для повышения достоверности классификации желательно ввести избыточность путем выделения каждому классу одного нейрона в выходном слое или, что еще лучше, нескольких, каждый из которых обучается определять принадлежность образа к классу со своей степенью достоверности, например: высокой, средней и низкой. Такие НС позволяют проводить классификацию входных образов, объединенных в нечеткие (размытые или пересекающиеся) множества. Это свойство приближает подобные НС к условиям реальной жизни.

Рассматриваемая НС имеет несколько "узких мест". Во-первых, в процессе обучения может возникнуть ситуация, когда большие положительные или отрицательные значения весовых коэффициентов сместят рабочую точку на сигмоидах многих нейронов в область насыщения. Малые величины производной от логистической функции приведут в соответствие с (2.16) и (2.17) к остановке обучения, что парализует НС. Во-вторых, применение метода градиентного спуска не гарантирует, что будет найден глобальный, а не локальный минимум целевой функции. Эта проблема связана еще с одной, а именно - с выбором величины скорости обучения. Доказательство сходимости обучения в процессе обратного распространения основано на производных, то есть приращения весов и, следовательно, скорость обучения должны быть бесконечно малыми, однако в этом случае обучение будет происходить неприемлемо медленно. С другой стороны, слишком большие коррекции весов могут привести к постоянной неустойчивости процесса обучения. Поэтому в качестве обычно выбирается число меньше 1, но не очень маленькое, например, 0.1, и оно, вообще говоря, может постепенно уменьшаться в процессе обучения. Кроме того, для исключения случайных попаданий в локальные минимумы иногда, после того как значения весовых коэффициентов застабилизируются, кратковременно сильно увеличивают, чтобы начать градиентный спуск из новой точки. Если повторение этой процедуры несколько раз приведет алгоритм в одно и то же состояние НС, можно более или менее уверенно сказать, что найден глобальный максимум, а не какой-то другой.

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

3. СВЕРТОЧНЫЕ НЕЙРОННЫЕ СЕТИ

3.1 Основные понятия

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

1) Локальное извлечение признаков.

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

Рисунок 3.1-Локальное извлечение признаков

2) Совместное использование весов

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

3) Подвыборка (subsampling)

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

Рисунок 3.2-Слой подвыборки

3.2. Сверточная нейронная сеть для распознания рукописных символов

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

Рисунок 3.2-Сверточная нейронная сеть для распознания рукописных символов

Данная сеть имеет 7 слоев, не считая входного. Все слои содержат обучаемые параметры. На вход 1 слоя поступает изображение размером 32x32 пикселя. Это больше, чем исходное изображения, размеры которых 28x28 пискеля. Исходное изображение централизуется. Это делается для того, чтобы характерные признаки изображения, такие как концевые точки, углы, находились в центре изображения для ускорения сходимости. Значения пискселей исходного изображения принимаются для фоновых пикселей(белого цвета) -0.1, а для черных 1.175.

Первый уровень содержит 6 карт признаков, каждый нейрон карты соединен с областью размером 5x5. Размер каждой карты 28x28. Данный слой содержит 156 обучаемых параметров и 122 304 связи.

Слой 2 является слоем подвыборки. Он состоит из 6 карт признаков размером 14х14, причем каждый из элементов карт этого слоя соединен с областью 2х2 в соответствующей карте признаков предыдущего слоя. Четыре входа обучающей выборки, умноженных на 1 коэффициент плюс обучаемый сдвиг являются аргументом каждого нейрона. Стоит отметить, что рецептивные области данного слоя не пересекаются, поэтому ширина и высота каждой карты данного слоя в 2 раза меньше предыдущего. Таким образом, второй скрытый слой содержит 5,880 связей и 12 обучаемых параметров.

Слой 3 является сверточным и содержит 16 карт признаков. Каждый нейрон соединен с областью размером 5x5 сразу нескольких карт предыдущего слоя. На рисунке 3.4 показано с какими именно картами предыдущего слоя осуществлена связь

Рисунок 3.4-Связь карт 3-го слоя с картами 2 слоя.

По горизонтали номер карты 3-го слоя, по вертикали номер карты 2 -го слоя

Данный вид соединения имеет ряд объяснений. Во-первых, соединение каждого нейрона со всеми картами предыдущего слоя привело бы к резкому увеличению числа соединений и, соответственно, к увеличению времени вычисления, а также привело бы к вычислению одинаковых признаков. Данная же схема нарушает симметрию сети и позволяет извлекать различные признаки. Первые 6 карт соединены с 3 различными картами предыдущего слоя, следующие 8 карт имеют связи с 4 различными картами, и наконец, последняя карта со всеми картами предыдущего слоя. В общем, третий слой содержит 151,600 связей и 1,516 обучаемых параметров.

Слой 4 является слоем подвыборки, и по своей структуре мало чем отличается от 2-го слоя. Он имеет 16 карт, размерностью 5x5, нейрон каждой карты соединен с областью 2x2 одной из карт предыдущего слоя. Слой 4 имеет 2000 связи и 32 обучаемых параметра.

Пятый сверточный слой содержит 120 карт, которые соединены со всеми картами предыдущего слоя. Поскольку размер карт 4 слоя 5x5, размер карт 5 слоя 1x1. Таким образом, данный слой является, по сути, полносвязным слоем, классической нейронной сети. Он содержит 48 120 обучаемых параметров.

Шестой слой также является полносвязным и состоит из 84 нейрона. Данный слой содержит 10 164 обучаемых параметра.

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

(3.1)

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

3.3 Распознание рукописных букв русского алфавита

Для создания системы распознавания русского алфавита были выбраны 44 прописных и строчных буквы, принципиально отличающиеся стилем написания. Была собрана база изображений, содержащая 9979 вариантов написания различных букв, различными людьми (В нее частично вошли символы, размещенные на сайте http://www.brain-lab.org). Выяснилось, что система применявшиеся для распознавания цифр не способна добиться приемлимых результатов распознавания. Причиной этому может быть как большее колтчество образов, так и наличие символов, таких как `г' и `ч', `в' и `д', `а' и `о'.

Для повышения точности распознавания было рассмотрено несколько вариантов:

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

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

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

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

Результаты показали, что наибольший процент распознания достигается при 3-м варианте.(Таблица 3.1). Рассмотрим его более подробно.

Таблица 3.1.-Сравнение алгоритмов распознавания

Алгоритм	Величина ошибки на проверочной выборки,%
Исходная нейронная сеть	25.4
Сверточная сеть с удвоенным числом нейронов	16.7
Разделение на 4 группы с различными символами	17.3
Разделение на 13 кластеров со схожими символами	11.9

Исходное множество символов было разбито на 13 кластеров, в каждый из которых вошло от 2 до 6 символов(см. Таблицу 3.2). Для разбиения символов на кластеры использовался метод k -средних(k-means). На первом этапе сверточная нейронная сеть определяет кластер, к которому принадлежит данный символ.

Таблица 3.2-Разбиение символов на кластеры

Номер кластера

0

1

2

3

4

5

6

7

8

9

10

11

12

М

д

и

Г

Ю

Л

ч

З

ь

к

е

Ч

а

м

В

й

Т

Д

А

г

Э

ъ

х

с

У

о

ш

Е

ц

Р

Ф

з

Б

я

щ

у

н

р

б

ж

П

ы

т

На втором этапе сеть в выбранном кластере осуществляет распознавание символа внутри кластера. Учитывая большую ошибку на первом этапе, кластеры были расширены для распознания на этапе 2(см. таблицу 3.3).

Таблица 3.3- Расширенный состав кластеров

Номер кластера

0

1

2

3

4

5

6

7

8

9

10

11

12

М

д

и

Г

Ю

Л

ч

З

ь

к

е

Ч

а

м

В

й

Т

Д

А

г

Э

ъ

х

с

У

о

ш

Е

ц

Р

Ф

Я

ъ

з

Б

ж

г

ч

я

щ

д

н

р

У

б

н

в

м

ж

б

м

П

У

ы

т

Б

т

з

к

Е

Н

Е

П

а

ы

л

д

Й

ы

н

з

А

Д

Окончательное решение по выбору класса принимается, согласно формуле

(3.2)

где -выход i-нейрона сети верхнего уровня, -выход j выходного нейрона i кластера. Общая схема продемонстрирована на рисунке 3.5

Рисунок 3.5 Схема распознавания рукописного символа

Невысокая точность распознавания, в сравнении, например, с алгоритмами на рукописных цифрах, может быть объяснена не только увеличением числа образов, наличием значительного числа похожих, но и небольшими размерами базы изображений. В процессе обучения на 1 класс приходилось 115-280 изображений, в то время, в то время как при тестировании цифр около 6000 на каждый класс. Для сравнения на рисунке 3.6 приведен график ошибки распознавания для цифр при различных размерах базы изображений

4. ПРОГРАММНАЯ РЕАЛИЗАЦИЯ РАСПОЗНАВАНИЯ РУКОПИСНЫХ СИМВОЛОВ

4.1 Общие сведения

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

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

Программа для обучение нейронных сетей NeuronLearn (см. рисунок 4.1), позволяет запускать процедуру обучения для выбранной нейронной сети. Язык реализации C#.

Рисунок 4.1-Программа для обучение нейронных сетей

Программа для демонстрации результатов распознавания DemoRecognize.

Позволяет распознать написанный в окне или загруженный из файла символ. Язык реализации С#.

Рисунок 4.2-Программа демонстрации результатов распознавания

Библиотека для первичной обработки изображений. Находит охватывающий прямоугольник, приводит изображение к бинарному виду. Язык реализации С#.

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

Язык реализации С#.

Экспериментальная программа для распознавания слов. Осуществляет распознавание слов с коррекцией результата по словарю. Язык реализации С#. (см. рисунок 4.3)

Рисунок 4.3-Программа распознавания слов

Все программы созданы в среде Microsoft Visual Studio 2008. Для работы графических приложений реализованных на языке C# требуется Microsoft Framework 3.5.

4.2. Описание логической структуры программы

Отметим наиболее важные части библиотеки- реализации сверточной нейронной сети.

Neuron -Абстрактный класс, реализущий понятие нейрон любой нейронной сети.

В числе прочих содержит следующие члены:

double get_out()- Возвращает выходное значение нейрона

double sigmoid()-Чисто виртуальная функция, определяющие вид активационной функции нейрона.

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

LearnConvolutionalNeuron . Класс- реализация обучаемого нейрона . Содержит функции, для осуществления процесса обучения методом обратного распространения ошибки. diff_sigmoid() - вычисляет производную сигмоидной функции. learning(vector<vector<ConvolutionalNeuron>>&last_level,vector<double> &dif_weights) -осущесвтляет коррекцию синапсных весов, в соответствии с алгоритмом обучения.

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

ConvolutionalLayer -Реализация необучаемого слоя сверточной нейронной сети. Содержит массив указателей на ConvolutionalNeuron,значение весов всех карт слоя. Функция solve() осуществляет запуск данной функции у всех нейронов данного слоя. load(string filename) поддерживает загрузку весов из файла.

LearnConvolutionalLayer -реализация обучаемого слоя сверточной нейронной сети. learn(vector<vector<ConvolutionalNeuron *>> &last_layer)-осуществляет алгоритм обратного распространения. Кроме этого функция save(string filename)-осуществляет сохранение весов в файл. Функция generate_weights() осуществляет начальную генерацию весов нейронной сети случайным образом.

SubSamplingLayer -реализация слоя подвыборки. Отличными являются реализации алгоритма обучения и генерации весов.

Классы FirstLearnConvolutionalLayer, LastLearnConvolutionalLayer, RBFLastLearnConvolutionalLayer являются реализацией, первого,последнего и слоя с РБФ связью, соответсвенно.

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

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

learning(int n) -запускает алгоритм обучения для n образов, выбор класса образа и его номера осуществляется случайно. Менее подвержен попаданию в локальные минимумы, но не гарантирует обучение сети для всех образов. learning2()-запускает алгоритм обучения для всех образов,обучающей выборки. learn(int reaction)-запускает алгоритм обучения для одного образа, с заданной реакцией.

get_result(int &num,double &res)-получает единственный результат работы нейронной сети.

gen_weights()-генератор новых весов.

check()-проверка сети на проверочной выборки. load(),save() -загрузка и сохранение текущих данных,

backup_save()-резервное сохранение, запускается из full_learning() перед началом работы.

check_this(double *image,int n,int neurons_[],double outs[])-осуществляет распознование текущего образа, с выводом n лучших результатов.

Классы N1LearnLayerX и N2LearnLayerX -являются реализацией слоев нейронной сети описанной в главе 3 без и с использовнаием РБФ связи, а классы ConvolutionalNeuronNet1 и ConvolutionalNeuronNet2 являются реализацией соответсвующих сетей для распознования цифр.

Класс SegmLetterNet нейронная сеть, для оперделения сегмента для рукописных букв, а классы SegmLetterNetX - классы для соответствующего сегмента, где X-его номер.

Экспортируемые функции:

init_neuron_nets()-создает все нейронные сети

set_cur_net_numeric(),set_cur_net_segmentator(),set_cur_net_segment(int segment) делают текущей сеть для цифр, для сегментации букв, и выбранный кластер букв, сооответсвенно.

learn_cur_net(int n)-обучает текущую сеть, заданное чмсло эпох

check_cur_net_mem(double *image,int n,int neuros[],double outs[])-осуществляет распознавание текущей сетью, образа переданного в памяти.

check_letter_mem(double *image,int n,int neuros[],double outs[])-осуществляет распознавание буквы.

set_etta(double etta)-устанавливает скорость сходимости для текущей сети

generate_weights()-запускает генерацию весов для заданной сети

double cur_progress()-возвращает текущее состояние процесса обучения,0-обучение не начато, 1 -закончено.

save_cur_net()-сохраняет данные для текущей сети.

load_all_nets()-загружают веса уровней для всех сетей.

Размещено на Allbest.ru

...