новости  материалы  справочник  форум  гостевая  ссылки Поиск с Яндексом  
Новости
Материалы
  Логические подходы
  Нейронные сети
  Генетические алгоритмы
  Разное
  Публикации
  Алгоритмы
  Применение
Справочник
Форум
Гостевая книга
Ссылки
О сайте
 

Создание приложения для оптического распознавания
символов на основе Нейронной Сети


Автор: Alex Cherkasov
Дата: 05.04.2003
Перевод:
Алексей Бревнов,
Владимир Любителев,
Источник: http://www.codeproject.com/dotnet/simple_ocr.asp


Введение

В наше время множество разработчиков трудится над созданием систем оптического распознавания (Optical Character Recognition, OCR System) либо над улучшением работы уже существующих систем.

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

Предыстория

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

Что ж, искусственная нейронная сеть (Artificial Neural Network - ANN) является замечательным инструментом, который может помочь в решении такого рода задач. Искусственная нейронная сеть (НС) - это научный подход обработки информации, созданный по аналогии с процессами работы головного мозга человека. Искусственные нейронные сети - это набор математических моделей, которые заключают в себе некоторые из наблюдаемых особенностей биологических нервных систем и построены по принципу адаптивного биологического обучения. Ключевым элементом НС является топология. НС состоит из большого числа обрабатывающих элементов (ячеек - nodes), соединенных между собой огромным количеством связей (links), обладающих весовой характеристикой. Обучение в биологических системах состоит из корректирования синоптических связей, существующих между нейронами. По такому же принципу работают и искусственные НС. Их обучение обычно проходит двумя способами:

  • тренировки на примерах,
  • прокрутка входных/выходных данных (pattern).

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

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

Использование кода

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

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

Создание нейронной сети

В приведенном примере используется нейронная сеть с обратной связью (Backpropagation neural network). НС с обратной связью является многоуровневой перцептронной моделью с входным уровнем, одним или несколькими скрытыми промежуточными уровнями и выходным уровнем:

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

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

//Inherit form Backpropagation neural network
public class OCRNetwork: BackPropagationRPROPNetwork
{
    //Override method of the base class in order to implement our 
    //own training method
    public override void Train(PatternsCollection patterns) 
    {    
        ...
    }
}

Перепишем метод Train (обучение) базового класса, для того чтобы реализовать собственный алгоритм обучения. Для чего это нужно? Очень просто, - процесс тренировки нейронной сети измеряется качеством достигнутого результата и скоростью обучения. Необходимо четко определить критерии, когда качество выходных результатов процесса обучения можно считать удовлетворительными и тренировка может быть прекращена. Реализация, предложенная здесь, доказала на практике (основываясь на опыте автора) свою способность быстро приводить к точным результатам. Здесь предположим, что процесс обучения может быть прекращен тогда, когда сеть смогла распознать все наборы без единой ошибки. Итак, ниже приведен код реализации алгоритма тренировки:

public override void Train(PatternsCollection patterns) 
{
    //Current iteration number 
    if (patterns != null) 
    {
        double error = 0;
        int good = 0;
        // Train until all patterns are correct
        while (good < patterns.Count)
        {
            good = 0;
            for (int i = 0; i < patterns.Count; i++)
            {
                //Set the input values of the network 
                for (int k = 0; k < NodesInLayer(0); k++)
                    nodes[k].Value = patterns[i].Input[k];
                //Run the network
                this.Run();
                //Set the expected result
                for (int k = 0; k < this.OutputNodesCount; k++)
                    this.OutputNode(k).Error = patterns[i].Output[k];
                //Make the network to remember corresponding output 
                //values. (Teach the network)
                this.Learn();
                //See if network did produced correct result during 
                //this iteration
                if (BestNodeIndex == OutputPatternIndex(patterns[i]))
                    good++;
            }
            //Adjust weights of the links in the network to their
            //average value. (An epoch training technique)
            foreach (NeuroLink link in links) 
                ((EpochBackPropagationLink)link).Epoch(patterns.Count);
        }
    }
}

Также создадим и реализуем свойство BestNodeIndex, которое возвращает индекс узла, обладающего максимальным значением результата и минимальным значением ошибки. Метод OutputPatternIndex возвращает указатель на выходной элемент со значение 1 для текущего набора входных значений. Если эти индексы равны - это значит, что сеть выдала правильный результат (ответ). Ниже приведен код свойства BestNodeIndex:

public int BestNodeIndex
{
    get
    {
        int result = -1;
        double aMaxNodeValue = 0;
        double aMinError = double.PositiveInfinity;
        for (int i = 0; i < this.OutputNodesCount; i++)
        {
            NeuroNode node = OutputNode(i);
            //Look for a node with maximum value or lesser error
            if ((node.Value > aMaxNodeValue) || 
                ((node.Value >= aMaxNodeValue) && (node.Error <aMinError)))
            {
                aMaxNodeValue = node.Value;
                aMinError = node.Error;
                result = i;
            }
        }
        return result;
    }
}

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

NodesNumber = (InputsCount + OutputsCount) / 2;

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

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

//Create an instance of the network
backpropNetwork = new OCRNetwork(new int[3] {aMatrixDim * aMatrixDim, 
    (aMatrixDim * aMatrixDim + aCharsCount) / 2, aCharsCount});

Создание наборов для обучения

Теперь поговорим о наборах значений для тренировки сети. Эти наборы будут использоваться в обучении нейронной сети распознаванию изображений. По сути, каждый такой набор состоит из двух одномерных массивов действительных чисел (float) - Inputs (входной) и Outputs (выходной) массивы.

/// <summary>
/// A class representing single training pattern and is used to train a 
/// neural network. Contains input data and expected results arrays.
/// </summary>
public class Pattern: NeuroObject
{
    private double[] inputs, outputs;
    ...
}

Массив Inputs содержит набор входных данных. Здесь это оцифрованное представление изображения символа. Под "оцифровыванием" (digitizing) изображения, в данном случае, понимается процесс создания карты зон яркости/освещенности (или абсолютное значение вектора цвета) изображения. Для создания такой карты разделим изображение на квадратные зоны и вычислим среднее значение для каждой из них. Далее сохраним эти значения в массиве.

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

//aSrc – an image of the character
//aArrayDim – dimension of the pattern matrix
//calculate image quotation X step
double xStep = (double)aSrc.Width / (double)aArrayDim;
//calculate image quotation Y step
double yStep = (double)aSrc.Height / (double)aArrayDim;
double[] result = new double[aMatrixDim * aMatrixDim];
for (int i = 0; i < aSrc.Width; i++)
    for (int j = 0; j < aSrc.Height; j++)
    {
        //calculate matrix address 
        int x = (int)(i / xStep);
        int y = (int)(j / yStep);
        //Get the color of the pixel 
        Color c = aSrc.GetPixel(i, j);
        //Absolute value of the color, but I guess, it is possible to
        //use the B component of Alpha color space too...
        result[y * x + y] += Math.Sqrt(c.R * c.R + c.B * c.B + c.G * c.G);
    }
//Scale the matrix to fit values into a range from 0..1 (required by 
//ANN) In this method we look for a maximum value of the element 
//and then divide all elements of the matrix by this maximum value.
return Scale(result);

Массив Outputs из набора описанного классом Pattern представляет собой ожидаемый результат - результат, который сеть будет использовать в процессе обучения. Число элементов в массиве равняется числу распознаваемых символов. Так, например, для обучения нейронной сети распознаванию символов английского алфавита от "A" до "Z" потребуется 26-ти элементный массив Outputs. Расширим его до 52-х элементов, если необходимо распознавать как строчные, так и прописные символы. Каждый элемент этого массива соответствует одной букве алфавита. В массиве Inputs каждого набора (pattern) записана информация об оцифрованном изображении символа, соответствующего элементу из массива Outputs, значение которого установлено в 1. Таким образом, сеть знает, какому из элементов (символов) соответствуют данные из входного набора. Метод CreateTrainingPatterns выполняет рутинную работу по созданию таких наборов.

public PatternsCollection CreateTrainingPatterns(Font font)
{
    // Create pattern collection 
    // As many inputs (examples) as many elements in digitized image matrix 
    // As many outputs as many characters we going to recognize.
    PatternsCollection result = new PatternsCollection(
        aCharsCount, aMatrixDim * aMatrixDim, aCharsCount);
    // generate one pattern for each character
    for (int i = 0; i < aCharsCount; i++)
    {
        //CharToDoubleArray creates an image of the character and digitizes it.
        //You can change this method to pass actual the image of the character 
        double[] aBitMatrix = CharToDoubleArray(
            Convert.ToChar(aFirstChar + i), font, aMatrixDim, 0);
        //Assign matrix value as input to the pattern
        for (int j = 0; j < aMatrixDim * aMatrixDim; j++)
            result[i].Input[j] = aBitMatrix[j];
        //Output value set to 1 for corresponding character.
        //Rest of the outputs are set to 0 by default.
        result[i].Output[i] = 1;
    }
    return result;
}

Теперь работа по созданию наборов для обучения (patterns) завершена, и можно приступать к обучению сети.

Обучение нейронной сети

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

//Train the network 
backpropNetwork.Train(trainingPatterns);

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

Обучение сети никогда не завершится потому что Возможные способы устранения проблемы
1. Топология сети слишком проста для того, чтобы справится с числом предоставленных наборов. Необходимо увеличить размеры сети Добавить больше элементов в средний уровень или увеличить число средних уровней сети
2. Наборы для тренировки нечетки, либо не достаточно точны, либо слишком сложны, для того чтобы сеть могла выявить различия между ними В качестве решения можно упростить и прояснить наборы или изменить алгоритм обучения сети. К тому же надо помнить следующее: не удастся обучить сеть угадывать следующий счастливый номер в лотерее
3. Предположения на счет результатов тренировки слишком завышены и возможно нереалистичны Понизить уровень ожидаемой точности. Сеть никогда не сможет достигнуть уровня 100% "уверенности"
4. Нет причины Проверьте код!

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

Наслаждение результатами

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

//Get your input data
double[] aInput = ... (your digitized image of the character)
//Load the data into the network
for (int i = 0; i < backpropNetwork.InputNodesCount; i++)
    backpropNetwork.InputNode(i).Value = aInput[i];
//Run the network
backpropNetwork.Run();
//Get result from the network and convert it to a character
return Convert.ToChar(aFirstChar + backpropNetwork.BestNodeIndex).ToString();

Для того чтобы использовать сеть, потребуется загрузить данные во входной уровень сети. Далее используя метод Run, позволить сети обработать эти данные. В итоге взять полученный с выходного уровня результат и проанализировать их. Свойство BestNodeIndex, созданное в классе OCRNetwork выполнит эту работу.

Исходный код программы

Исходный код программы, демонстрирует работу алгоритма - (9.78 Кб)
Откомпилированная и готовая для запуска программа - (22.6 Кб)