Огрызков С.А. Курсовая работа по дисциплине «Обработка изображений, распознавание образов и мультимедиа»

Оригинал материала находится здесь: http://www.stanislaw.ru/rus/studies/imagine.asp

Библиотека

Курсовая работа по дисциплине «Обработка изображений, распознавание образов и мультимедиа»


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

Сначала я постарался обобщить в виде списка всё то, что нам нужно реализовать в данной курсовой работе. Ещё раз подчеркну: курсовая работа, а не проект, что означает отсутствие необходимости делать пояснительную записку невероятных размеров и сопровождать её безумными плакатами. Итак, список…

  I. Общие методы работы с изображениями:
 
Лабораторная
работа
№ 1
 
  • вывод изображения на экран;

  • построение гистограммы;

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

  • преобразование контрастности;

  • изменение цветности:
    • бинаризация (переход к чёрно-белому);
    • переход к оттенкам серого;
    • получение негатива;
Лабораторная
работа
№ 2
 
  • восстанавливающая фильтрация:
    • искусственное наложение шума;
    • фильтры шумоподавления:
      • одномерный и двумерный сглаживающие;
      • одномерный и двумерный медианные;

  • выделение границ:
    • метод Кирша;
    • метод Лапласа;
    • метод Робертса;
    • метод Собела;
    • метод Уоллеса;
    • статистический метод.
 
  II. Распознавание образов (например, букв).
 
  III. Цифровая обработка сигналов:
 
Лабораторная
работа
№ 3
 
  • преобразование Фурье:
    • непрерывное преобразование Фурье;
    • дискретное преобразование Фурье:
      • быстрое одномерное (прямое и обратное);
      • быстрое двумерное (прямое и обратное);
Лабораторная
работа
№ 4
 
  • преобразование Уолша-Адамара:
    • быстрое одномерное дискретное (прямое и обратное);
    • быстрое двумерное дискретное (прямое и обратное).


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

Сразу оговорюсь, что речь пойдёт об особенностях реализации алгоритмов обработки изображений под Windows, а именно в среде разработки Borland/Inprise Delphi; исходные тексты при этом в виде, готовом для компиляции, не предоставляются, скачать можно только сам исполнимый файл и примеры изображений. А вот для любителей языка C (в частности, Microsoft Visual C++) доступна альтернативная реализация, вместе с полными исходными текстами – благодаря Артёму Петрову.

  1. Многодокументный интерфейс Документный интерфейс. Приложение можно сделать как однодокументным (Single Document Interface, SDI), так и многодокументным (Multi-Document Interface, MDI). В нашем случае предпочтительнее первое, так как, во-первых, это проще в плане реализации (чего студенту и надо :-), а во-вторых, это теперь признаётся стандартом. Если раньше все кричали об MDI-приложениях, то теперь даже сама Microsoft рекомендует от них отказаться (см. их Office 2000), так как общеизвестно, что в ядре Windows заложено много «недоделок», касающихся технологии MDI.


  2. Открытие изображения Открытие изображения. Его удобно выполнять с помощью диалогового окна «Открытие изображения» (класс TOpenDialog или TOpenPictureDialog), а само изображение хранить и отображать в компоненте класса TImage. При этом, помимо «классических» типов графических файлов (в частности, *.bmp) удобно было бы иметь возможность загружать полноцветные фотографические изображения в формате JPEG (так как на полноцветных картинках лучше всего наблюдаются некоторые эффекты). Это легко осуществимо примерно так:
    uses JPEG;
    
    var
      JPEGImage: TJPEGImage;
      Image: TImage;
    
    begin
      JPEGImage := TJPEGImage.Create;
      JPEGImage.LoadFromFile (OpenDialog.FileName);
      Image.Picture.Assign (JPEGImage);
      JPEGImage.Free;
    end;
                  
  3. Компонент TImage Работа с изображением и его отображение. Желательно иметь несколько компонентов, хранящих изображения. Это нужно, во-первых, для более быстрой работы (если работать с изображением, которое невидно пользователю, то система не затрачивает времени на постоянную прорисовку каждого изменения; гораздо быстрее один раз предъявить конечный результат), а во-вторых, для возможности отката/повтора действия. Кроме того, это может пригодиться для каких-либо алгоритмов, формирующих результирующее изображение отдельно от исходного и на его основе. Здесь используются визуальные компоненты-контейнеры класса TImage, а также их невизуальные «составляющие» вроде TBitmap; при этом копирование (именно копирование, а не ссылка) содержимого осуществляется так:
    var
      Bitmap: TBitmap;
      Image: TImage;
    
    begin
      Bitmap := TBitmap.Create;
      Bitmap.Assign (Image.Picture); //из Image – в Bitmap
      
      Image.Picture.Assign (Bitmap); //из Bitmap – в Image
      Bitmap.Free;
    end;
                  
    Дополнительно может понадобиться создание пустого изображения с необходимыми размерами и копирование в него какой-либо части исходного. Это делается так:
    var
      Bitmap: TBitmap;
      BitmapArea: TRect;
      Image: TImage;
    
    begin
      Bitmap := TBitmap.Create;
      with BitmapArea do
        begin
          Left := 0;
          Top := 0;
          Right := Image.Width – 1;
          Bottom := Image.Height – 1;
        end;
      with Bitmap do
        begin
          Height := Image.Height;
          Width := Image.Width;
          Canvas.CopyMode := CMSrcCopy;
          Canvas.CopyRect (BitmapArea, Image.Canvas, BitmapArea);
        end;
      Image.Picture.Assign (Bitmap);
      Bitmap.Free;
    end;
                  
    Использование всяких линеек процесса (классы TProgressBar или TGauge) – это, конечно, красиво, но может существенно замедлить работу алгоритмов. Но вот использовать метод Application.ProcessMessages в долгих цикличных процедурах было бы не лишним, так как это создаёт «эффект независшего приложения» (выполняется его периодическое обновление, а также обработка системных событий).


  4. Цвета точек Работа с точками и цветами. Для работы с элементами изображения – пикселями – удобнее всего использовать массив Bitmap.Canvas.Pixels[X,Y], так как он представляет собой двумерный массив всех точек изображения, каждый элемент которого – это цвет (класс TColor) точки. TColor – это 4-байтовый цвет, где самый старший (самый левый) байт – служебный, а остальные, слева направо, – байты значений цветовых каналов B (голубой), G (зелёный) и R (красный) – именно в такой последовательности. Очевидно, что ввиду отсутствия в языке Object Pascal явных средств доступа к отдельным битам приходится использовать логические операции and и or и операции сдвига shl и shr для выделения нужных байтов из 4-байтового значения (тип LongInt):
    var
      B, G, R: Byte;
      Image: TImage;
      Pixel: TColor;
    
    begin
      Pixel := Image.Canvas.Pixels [0, 0];
      R := Pixel and $000000FF;          //или R := GetRValue (Pixel);
      G := (Pixel and $0000FF00) shr 8;  //или G := GetGValue (Pixel);
      B := (Pixel and $00FF0000) shr 16; //или B := GetBValue (Pixel);
      
      Pixel := B shl 8;
      Pixel := (Pixel or G) shl 8;
      Pixel := Pixel or R;
      Image.Canvas.Pixels [0, 0] := Pixel;
    end;
                  
    Однако за удобство приходится платить временем: работа через массив Pixels[X,Y] требует огромных ресурсов (из-за индексации по массиву), и на слабых машинах можно просто недождаться результата. Поэтому есть замечательный метод Bitmap.ScanLine, который возвращает указатель на целую строку пикселей. Но элементы строки, на которую указывает ScanLine, – это уже не 4-байтовый цвет, а реальные единицы информации, соответствующие цветности картинки (для чёрно-белого изображения – 1 бит, для 4-цветного – 2 бита и т.д., для полноцветного – 3 или 4 байта). Поэтому здесь могут возникнуть свои трудности, вызванные всё теми же побитовыми операциями и выделением значений цветовых каналов в малоцветных (от 256 цветов и меньше) изображениях. На этот случай предлагается следующее: принудительно приводить цветность любой картинки к 65 тысячам цветов (3-байтовый цвет, где каналы идут всё в той же последовательности (B, G и R), по байту на канал), и работать так:
    var
      B, G, R: Byte;
      Image: TImage;
      P: PByteArray;
    
    begin
      Image.Picture.Bitmap.PixelFormat := PF24Bit;
      P := Image.Picture.Bitmap.ScanLine [0];
      X := 0;
      repeat
        R := P [X + 2];
        G := P [X + 1];
        B := P [X];
        X := X + 3;
      until X > 3 * Image.Width – 1;
    end;
                  
  5. Гистограммы Яркость точки и гистограммы изображения. Яркость точки находится по формуле, коэффициенты которой определяются свойствами человеческого зрения:
    Y:=0.3*R+0.59*G+0.11*B
    Гистограммой в данном случае называется так или иначе представленная (например, в виде столбчатой диаграммы) зависимость числа повторений того/иного значения яркости на всём изображении от этого самого значения (то есть сколько раз встречается абсолютно чёрная точка, абсолютно белая и др.); при этом можно рассматривать 4 гистограммы: по 3 каналам и по вычисленной яркости.


  6. Баланс изображения Изменения яркости и контрастности. Эти изменения можно обобщить выражением «изменение баланса изображения», так как оба понятия – и яркость, и контрастность, – схожи и относятся к сфере восприятия изображения человеком.

    Повышение/снижение яркости – это, соответственно, сложение/вычитание значения каждого канала с некоторым фиксированным значением (также в пределах от 0 до 255); при этом обязательно необходимо контролировать выход нового значения канала за пределы диапазона 0..255, например, так:
    var
      TempValue: Real;
      Value: Byte;
    
    begin
      TempValue := Round ();
      if TempValue < 0 
        then Value := 0
        else if TempValue > 255 
          then Value := 255
          else Value := Round (TempValue);
    end;
                  
    Повышение/снижение контрастности – это, соответственно, умножение/деление значения каждого канала на некоторое фиксированное значение (в том числе действительное), что приводит к изменению соотношений между цветами и, соответственно, к более чётким цветовым границам. На практике же существует такой принцип: изменение контрастности не должно приводить к изменению средней яркости по изображению, поэтому пользуются следующей формулой:
    NewY:=K*(OldY-AveY)+AveY,
    где NewY – новое значение одного из каналов, K – коэффициент контрастности (K=(0..1) – снижение, K<1 – повышение контрастности), OldY – текущее значение того же канала, AveY – среднее значение того же канала по изображению (таким образом, алгоритм фактически является двухпроходовым). Обязательна всё та же коррекция нового значения при выходе его за границы 0..255.


  7. Цветность изображения Изменение цветности (бинаризация, оттенки серого, негатив). Под изменением цветности здесь понимается изменение спектра цветов, используемых в изображении. Минимальное, что нужно сделать в курсовой работе, – бинаризация, оттенки серого и негатив, поэтому о них и поговорим.

    Бинаризация – это преобразование изображения, в общем случае, к одноцветному (чаще всего к черно-белому). В терминах Photoshop это ещё называется «по уровню 50%», так как при этом выбирается некий порог (например, посередине), все значения ниже которого превращаются в цвет фона, а выше – в основной цвет. Само преобразование можно осуществлять по каналам, но в этом случае результирующее изображение не будет в прямом смысле бинарным (чёрно-белым), а будет содержать 8 чистых цветов, представляющих собой комбинации чистых красного, зелёного и голубого цветов, то есть будет бинарным по каналам. Поэтому лучше проводить преобразование над «полным» цветом точки, например, так:
    var
      Image: TImage;
      MidColor, Pixel: TColor;
    
    begin
      MidColor := (High (TColor) – Low (TColor)) div 2;
      Pixel := Image.Canvas.Pixels [0, 0];
      if Pixel < MidColor 
        then Pixel := Low (TColor)
        else Pixel := High (TColor);
      Image.Canvas.Pixels [0, 0] := Pixel;
    end;
                  
    Преобразование к оттенкам серого заключается в получении яркости каждой точки по известной формуле (Y:=0.3*R+0.59*G+0.11*B) и последующем копировании полученного значения по все три канала (R=G=B:=Y).

    И, наконец, негатив получается простой заменой значения каждого канала на его дополнение до 255 (например, R:=255-R).


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

    Зашумление можно выполнять любым способом, изменяющим каким-либо образом значения каких-то точек изображения. Например, так:
    var
      Image: TImage;
      I, X, Y: Integer;
    
    begin
      for I := 1 to 100 do
        begin
          X := Random (Image.Width);
          Y := Random (Image.Height);
          Image.Canvas.Pixels [X, Y] := ClBlack; //случайные точки становятся чёрными
        end;
    end;
                  
    Для начала введём один специальный термин: апертура фильтра – это размер окна (части изображения), с которым фильтр работает непосредственно в данный момент времени; окно это постепенно передвигается по изображению слева направо и сверху вниз на один пиксель (то есть на следующем шаге фильтр работает с окном, состоящим не только из элементов исходного изображения, но и из элементов, ранее подвергнувшихся преобразованию, – своего рода «принцип снежного кома»). Кроме того, заметим, что если речь идёт об окне, представляющем собой строку элементов изображения ([X][X][X]), то такое преобразование называется одномерным; соответственно, существует и двумерное преобразование.

    Сглаживающий фильтр основывается на следующем принципе: находится среднее арифметическое значение всех элементов рабочего окна изображения (отдельно по каждому из каналов), после чего это среднее значение становится значением среднего элемента (речь идёт о нечётной апертуре фильтра; для двумерного случая средним элементом будет средний элемент по горизонтали и вертикали, то есть центр квадрата). Выглядит это примерно так:
    var
      Image: TImage;
      X, Y: Integer;
    
    begin
      for X := 1 to Image.Width – 2 do
        for Y := 1 to Image.Height – 2 do with Image.Canvas do
          Pixels [X, Y] := (
            Pixels [X – 1, Y – 1] + Pixels [X – 1, Y] + Pixels [X – 1, Y + 1] +
            Pixels [X,     Y – 1] + Pixels [X,     Y] + Pixels [X,     Y + 1]+
            Pixels [X + 1, Y – 1] + Pixels [X + 1, Y] + Pixels [X + 1, Y + 1]) div 9;
    end;
                  
    Внимание! Под действие фильтра могут не попадать крайние элементы изображения (так получается в приведённом примере), поэтому при искусственном зашумлении их лучше преднамеренно не зашумлять, либо обрабатывать каким-то образом частный случай крайних точек (например, для угла изображения при апертуре 3 суммировать не 9 точек, а 4, и результат отправлять в этот самый угол).

    Медианный фильтр основывается на нахождении медианы – среднего элемента (но не среднего арифметического) последовательности в результате её упорядочения по возрастанию/убыванию и присваиванию найденного значения только среднему элементу (речь снова о нечётной апертуре). Например, для той же апертуры 3 и двумерного фильтра (как в примере выше) мы должны упорядочить 9 точек (например, по возрастанию), после чего значение 5й точки упорядоченной последовательности отправить в центр окна фильтра (3х3). Для упорядочения можно использовать любой из известных методов сортировки, например, быструю сортировку Хоара:
    procedure SortBytes (var Bytes: array of Byte; Left, Right: Integer);
      var
        I, J: Integer;
        W, X: Byte;
      begin
        I := Left;
        J := Right;
        X := Bytes [(Left + Right) div 2];
        repeat
          while Bytes [I] < X do I := I + 1;
          while X < Bytes [J] do J := J – 1;
          if I lt;= J then
            begin
              W := Bytes [I];
              Bytes [I] := Bytes [J];
              Bytes [J] := W;
              I := I + 1;
              J := J – 1;
            end;
        until I > J;
        if Left < J
          then SortBytes (Bytes, Left, J);
        if I < Right
          then SortBytes (Bytes, I, Right);
      end;
                  
    Для фиксированной малой апертуры можно использовать какой-либо вырожденный (частный) вариант сортировки, построенный на операторах условия.


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

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

    Метод Кирша работает с двумерной апертурой 3х3 следующего вида:
    A0 A1 A2
    A7 F A3
    A6 A5 A4
       Si = Ai + Ai(+)1 + Ai(+)2

    Ti = Ai(+)3 + Ai(+)4 + Ai(+)5 + Ai(+)6 + Ai(+)7
    Сначала в цикле находятся все значения переменных Si и Ti, где i изменяется от 0 до 7, по приведённым выше формулам, в которых «(+)» означает сложение по модулю 8, для которого может быть использована следующая функция:
    function AddMod8 (X, Y: Integer): Integer;
      var Sum: Integer;
      begin
        Sum := X + Y;
        if Sum > 7 then Sum := Sum – 8;
        Result := Sum;
      end;
                  
    После находятся значения модуля разности | 5*Si – 3*Ti | для каждого i от 0 до 7 и значение максимума среди этих модулей:
    Формула метода Кирша
    Возможно, для обеспечения наблюдаемости потребуется повышение порога яркости сложением эдак с числом 100. Окончательное значение F' заносится в элемент F, после чего рабочее окно сдвигается на один элемент влево (далее – слева направо и сверху вниз).

    Метод Лапласа осуществляет домножение каждого элемента двумерной апертуры 3х3 на соответствующий элемент так называемой матрицы Лапласа:
    A B C
    D E F
    G H I
     
    x
    x
    x
     
    -1 -2 -1
    -2 12 -2
    -1 -2 -1
      =  
    -1*A -2*B -1*C
    -2*D 12*E -2*F
    -1*G -2*H -1*I
    Внимание! Здесь речь идёт именно о простом умножении каждого элемента исходной матрицы на соответствующий элемент матрицы коэффициентов, и это не надо путать с перемножением матриц.

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

    Существуют и другие матрицы Лапласа:
    0 -1 0
    -1 4 -1
    0 -1 0
    1 1 1
    1 -2 1
    -1 -1 -1
    -1 1 1
    -1 -2 1
    -1 1 1
    1 1 1
    -1 -2 1
    -1 -1 1
      и так далее…

    Метод Робертса, как показывает практика, является самым простым, самым быстрым и эффективным (поистине, всё гениальное – просто). Работает он с двумерной апертурой 2х2 следующего вида:
    A C
    B D
       Формула метода Робертса
    Здесь вторая форма записи (с квадратным корнем) работает медленнее, но точнее. Возможно, для обеспечения наблюдаемости потребуется повышение порога яркости сложением эдак с числом 100. Окончательное значение A' заносится в элемент A, после чего рабочее окно сдвигается на один элемент влево (далее – слева направо и сверху вниз).

    Метод Собела работает с двумерной апертурой 3х3 следующего вида:
    A1 A2 A3
    A8 F A4
    A7 A6 A5
       X = ( A3 + 2 * A4 + A5 ) – ( A1 + 2 * A8 + A7 )

    Y = ( A1 + 2 * A2 + A3 ) – ( A7 + 2 * A6 + A5 )
    Сначала находятся значения переменных X и Y по приведённым выше формулам. После находится новое значение центрального элемента:
    Формула метода Собела
    Возможно, для обеспечения наблюдаемости потребуется повышение порога яркости сложением эдак с числом 100. Окончательное значение F' помещается вместо элемента F, после чего рабочее окно сдвигается на один элемент влево (далее – слева направо и сверху вниз).

    Метод Уоллеса работает с двумерной апертурой 3х3 следующего вида:
    A0 A1 A2
    A7 F A3
    A6 A5 A4
       Формула метода Уоллеса
    Сразу находится новое значение центрального элемента по приведённой выше формуле; при этом, если знаменатель (Ai с нечётными значениями i) равен нулю, то к нему и к числителю добавляется единица (проще добавлять эту единицу всегда). Возможно, для обеспечения наблюдаемости потребуется домножение результата на очень большое число (эдак на 500) и повышение порога яркости сложением эдак с числом 100. Окончательное значение F' помещается вместо элемента F, после чего рабочее окно сдвигается на один элемент влево (далее – слева направо и сверху вниз).

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

    Внимание! Статистический метод – единственный из здесь рассмотренных, у которого изменяются значения сразу всех элементов.


  10. Распознавание текста Распознавание текста. Процесс распознавания текста делится на отдельные этапы, поэтому его удобно реализовать в виде мастера (аналогично мастеру установки Setup.exe). Некоторые этапы необязательны, некоторые здесь вообще не рассматриваются (например, не учитывается возможный перекос текста).

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

    Бинаризация. Это преобразование изображения, в результате которого значение каждого его элемента становится равным 0 или 1, то есть бинарным; в общем случае преобразование осуществляется отдельно по каждому каналу, в данном же случае – над общим значением яркости изображения, то есть результирующее изображение будет полностью чёрно-белым. Этап необязательный.

    Выделение строк Выделение строк. Оно необходимо для последующего выделения символов и их распознавания и осуществляется посредством выполнения вертикальной проекции (построения гистограммы) строк пикселей, на которой находятся области резкого перепада числа значимых (чёрных) пикселей в строке; если число чёрных точек в предыдущей строке пикселей было значительно меньше их числа в текущей строке, то это говорит о начале строки текста, и наоборот. Основная проблема здесь – в выборе порога (понятия «значительно» больше/меньше), так как изображение может быть зашумлено. Кроме того, если отдельные верхние/нижние элементы символов на соседних строках заходят друг за друга, то такие строки могут быть неразделимы.

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

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

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

    Для хранения описаний изображений символов можно использовать невизуальный объект TStringList, позволяющий легко работать со списком значений произвольной длины. Принятый формат хранения значений координат при этом может выглядеть так:
    StringList [I] := IntToStr (Top)  + ',' + IntToStr (Bottom) + ',' +
                      IntToStr (Left) + ',' + IntToStr (Right);
                  
    То есть каждая строка списка – это координаты верхней, нижней, левой и правой границы изображения символа, разделённые запятой. После выделения символов из списка удаляются описания ранее выделенных строк.

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

    Для получения результирующего изображения как сложения по модулю 2 используется режим TCanvas.CopyMode:=CMSrcInvert; и метод TCanvas.CopyRect(CurrentRect, AlphabetBitmap.Canvas, StandardRect). Степень соответствия определяется по формуле:
    CharFill := BlackPixels / (ScannedHeight * ScannedWidth);
                  
    где CharFill – заполненность результата сравнения нулями, BlackPixels – число чёрных (нулевых) пикселей на совмещённом изображении таким же размером, что и распознаваемое изображение (ScannedHeight x ScannedWidth).


  11. Непрерывное преобразование Фурье Непрерывное преобразование Фурье. Ряд вида

    Ряд Фурье

    где a0, an, bn (n є N) – коэффициенты ряда, называется рядом Фурье, или тригонометрическим рядом; возможно искусственное усложнение записи ряда с целью упрощения инженерных расчётов. Ряд Фурье используется для разложения непрерывных функций с целью дискретизации.

    Известны формулы Эйлера – Фурье для вычисления коэффициентов ряда Фурье:
    Коэффициенты ряда Фурье
    Эти формулы имеют место, если тригонометрический ряд для всех значений x сходится к функции f(x) (предполагается, что эта функция периодическая, с периодом 2Пи), и для этой функции существует интеграл
    Интеграл функции
    Функция f(x) может быть разрывной; при этом указанный интеграл становится несобственным. Непериодические функции, определённые в промежутке (-Пи; Пи) тоже можно разлагать в ряд Фурье, но со следующей оговоркой: за пределами указанного промежутка и на его концах ряд Фурье может иметь сумму, отличную от соответствующего значения самой функции.

    Теорема. Пусть функция непрерывна на промежутке (-Пи; Пи) и либо не имеет здесь разрывов, либо имеет их конечное число. Тогда для этой функции ряд Фурье сходится всюду; сумма его равна значению функции f(x) для всякого значения x є (-Пи; Пи), на обоих же концах промежутка сумма ряда равна [f(-Пи)+f(Пи)]/2.

    Интегралы
    Интегралы функции
    для чётной функции равны между собой, а для нечётной – разнятся знаками, поэтому имеем:
    Интеграл (не)чётной функции
    соответственно.

    Ряд Фурье для чётной функции не содержит синусов, а его коэффициенты равны:
    Коэффициенты чётной функции
    для нечётной функции – не содержит косинусов и имеет коэффициенты:
    Коэффициенты нечётной функции
    Очевидно, что для работы с произвольными функциями необходимо реализовать универсальную функцию численного интегрирования.

    Непрерывное преобразование Фурье выполняется над фиксированным сигналом, не зависящим от загруженного в программу изображения. Этот сигнал описывается функцией вида:
    function Signal (X: Real): Real;
      begin
        if Abs (X) > 1
          then X := X – 2 * Round (X / 2);
        if X < – 0.4
          then Result := 0.25;
        if (X >= – 0.4) and (X < 0.4)
          then Result := 0.5;
        if (X >= 0.4) and (X < 0.8)
          then Result := 0.75;
        if X >= 0.8
          then Result := 0.25;
      end;
                  
    Его интегрирование можно осуществлять численным методом трапеций:
    function Integral (F: TFunction; A, B, H: Real): Real;
      var Square, X: Real;
      begin
        Square := 0;
        X := A;
        while X < B – H do
          begin
            Square := Square + 0.5 * (F (X) + F (X + H)) * H;
            X := X + H;
          end;
        Result := Square;
      end;
                  
  12. Дискретное преобразование Фурье Дискретное преобразование Фурье. Дискретным преобразованием Фурье (ДПФ) над исходной последовательностью чисел {x0, x1, …, xn-1} мощностью n є N, n>1, где xi є Z, i=(0,n-1), называется такое преобразование, в результате которого получается последовательность {x-0, x-1, …, x-n-1} комплексных чисел x-k той же мощности, каждый элемент которой рассчитывается по правилу:
    Коэффициенты ДПФ
    где k=(0,n-1), W=e-j*Пи/n, где j – мнимая единица.

    Существуют такие Wik, у которых (ik) равны. Нетрудно заметить, что для выполнения n-точечного преобразования Фурье необходимо выполнить n(n-1) комплексных сложений и (n-1)(n-1) комплексных умножений (с учётом W0=1). При этом множитель Wik будет использован столько раз, сколько делителей из диапазона (0,n-1) у показателя степени (ik).

    Имеем:
    Тригонометрическое представление
    Поскольку sin Альфа = – sin (Альфа+Пи), cos Альфа = – cos (Альфа+Пи), то
    Связность по знакам (1)
    откуда следует, что
    Связность по индексам (2)
    Таким образом, диапазон степеней (ik) с помощью формулы (1) мы сокращаем с (0,(n-1)(n-1)) до (0,n-1), а с помощью формулы (2) – до (0,n/2-1).

    Пусть n – длина исходной последовательности чисел {x0, x1, …, xn-1} чётна, тогда преобразование Фурье для такой последовательности можно записать в виде:
    Разложение на подсуммы (3)
    С учётом формулы (1), а также выражения
    Связность по индексам
    формулу (3) часто записывают в виде:
    Разложение на подсуммы (4)
    Рассмотрим первую сумму формулы (3). Положив n / 2 = m, получим:
    1) n=2m;
    2) Связность по индексам;
    3) Связность подсумм.
    Аналогичные рассуждения можно провести и в отношении второй суммы формулы (3). Таким образом, ДПФ исходной последовательности размерностью n=2m свелось к двум ДПФ последовательностей размерностью m чисел каждая, составленных из чётных и нечётных элементов исходной последовательности.

    Формулы (3) и (4) являются основой для построения алгоритма быстрого преобразования Фурье (БПФ). Этот алгоритм за счёт рекурсивного применения формулы (3) сводит ДПФ исходной последовательности размерности n=2l, где l є N, к набору 2-точечных преобразований Фурье.

    По определению имеем:
    Коэффициенты ДПФ
    Умножим x-k на Wn-jk и просуммируем по k=0..(n-1):
    Вывод формулы обратного ДПФ
    Можно доказать, что
    Равенство суммы нулю
    где a є Z, a>0, поэтому
    Значение суммы
    имеем:
    Вывод формулы обратного ДПФ
    – мы получили формулу для обратного ДПФ (ОДПФ):
    Формула ОДПФ
    откуда видно, что ОДПФ есть прямое ДПФ (ПДПФ) результата предыдущего ПДПФ, делённое на n.

    Двумерное ДПФ – это ДПФ над матрицей:
    Формула двумерного ДПФ
    где k,i=(0,n-1), l,j=(0,m-1), то есть это есть последовательное одномерное ДПФ сначала над строками, а потом над строками.

    Общий вид обратного двумерного ДПФ:
    Формула обратного двумерного ДПФ
    При практической реализации в качестве исходных данных для демонстрации работы алгоритмов ДПФ удобно использовать значения точек изображения, подвергающегося обработке другими алгоритмами. При этом под «значениями» точек понимается либо значения каждого из цветовых каналов, либо значение яркости (найденное по известной формуле), либо значение типа TColor элемента массива Pixels[], – это неважно. Важно то, что всё выполняется примерно по следующий схеме:
    1. Значения точек заносятся в область памяти, выделенную для действительных частей дискретов (речь ведь идёт о работе с комплексными числами).
    2. Область памяти, выделенная для мнимых частей дискретов, заполняется нулями (так как значения точек изображения – чисто действительные числа).
    3. Вызывается процедура необходимого преобразования Фурье (одномерное или двумерное БПФ), которой передаются указатели на выделенные области памяти и их размеры, а также направление преобразования (в данном случае прямое).
    4. В качестве наглядного представления коэффициентов, полученных после преобразования (в тех же областях памяти) используются модули комплексных чисел, которые делаются значениями соответствующих точек изображения.
    5. Сами области памяти сохраняются до выполнения обратного преобразования, так как они хранят комплексные значения коэффициентов (после прямого БПФ мнимые части отличны от нуля).
    6. При выполнении обратного преобразования той же универсальной процедуре передаются указатели на хранимые области памяти, их размеры и направление преобразования (обратное).
    7. Модули комплексных чисел, полученных после обратного БПФ, являются исходными значениями точек изображения, так как их мнимые части равны нулю.
    8. Освобождаются выделенные области памяти.

    Пример процедуры для выполнения одномерного БПФ приведён ниже:
    //© 1999 Головинов И.А.
    procedure LinearFDFT (Re, Im: PReal; Count: Word; Direct: ShortInt);
      var
        I: Word;
        K: Real;
        PIm, PRe: PReal;
      procedure LFDFT (SrcRe, SrcIm: PReal; Cnt: Word);
        var
          EvenRe, OddRe, PEvenRe, POddRe, PRe, PSrcRe: PReal; ; //то же – для мнимых
          Factor: Real;
          HalfCnt, I, Size: Word;
          HEvenIm, HEvenRe, HOddIm, HOddRe: THandle;
          X, Y, WIm, WRe: Real;
        begin
          PSrcRe := SrcRe; ;
          if Cnt = 2 then
            begin //тривиальная операция «бабочка»
              Inc (PSrcRe); ;
              X := SrcRe^; Y := PSrcRe^;
              SrcRe^ := X + Y; PSrcRe^ := X – Y;
              X := SrcIm^; Y := PSrcIm^;
              SrcIm^ := X + Y; PSrcIm^ := X – Y;
            end      else
            begin //переупорядочение и рекурсивный вызов для полпоследовательностей
              Factor := K / Cnt;
              HalfCnt := Cnt div 2;
              Size := HalfCnt * SizeOfReal + 1;
              HEvenRe := GlobalAlloc (GMem_Fixed, Size); ;
              HOddRe := GlobalAlloc (GMem_Fixed, Size); ;
              EvenRe := GlobalLock (HEvenRe); ;
              OddRe := GlobalLock (HOddRe); ;
              PEvenRe := EvenRe; ;
              POddRe := OddRe; ;
              //Разбивка на (не)чётные подпоследовательности
              for I := 0 to Cnt – 1 do
                begin
                  if Odd (I) then
                    begin
                      POddRe^ := PSrcRe^; ;
                      Inc (POddRe); ;
                    end      else
                    begin
                      PEvenRe^ := PSrcRe^; ;
                      Inc (PEvenRe); ;
                    end;
                  Inc (PSrcRe); ;
                end;
              //Рекурсивная обработка (не)чётных подпоследовательностей
              LFDFT (EvenRe, EvenIm, HalfCnt);
              LFDFT (OddRe, OddIm, HalfCnt);
              //Сборка обработанных подпоследовательностей
              PSrcRe := SrcRe; ;
              PRe := SrcRe; ;
              Inc (pRe, HalfCnt); ;
              PEvenRe := EvenRe; ;
              POddRe := OddRe; ;
              for I := 0 to HalfCnt – 1 do
                begin
                  WRe := Cos (Factor * I); WIm := – Sin (Factor * I);
                  PSrcRe^ := POddRe^ * WRe – POddIm^ * WIm;
                  PSrcIm^ := POddRe^ * WIm + POddIm^ * WRe;
                  PRe^ := pSrcRe^; ;
                  PSrcRe^ := pEvenRe^ + PSrcRe^; ;
                  PRe^ := PEvenRe^ – PRe^; ;
                  Inc (PSrcRe); ;
                  Inc (PRe); ;
                  Inc (PEvenRe); ;
                  Inc (POddRe); ;
                end;
              GlobalUnlock (HEvenRe); ;
              GlobalUnlock (HOddRe); ;
              GlobalFree (HEvenRe); ;
              GlobalFree (HOddRe); ;
            end;
        end;
      begin
        K := 2 * Pi * Direct;
        LFDFT (Re, Im, Count);
        if Direct < 0 then
          begin //Дополнительное деление на n для обратного преобразования
            PRe := Re; ;
            for I := 1 to Count do
              begin
                PRe^ := PRe^ / Count; ;
                Inc (PRe); ;
              end;
          end;
      end;
                  
    Оптимизация здесь может заключаться в использовании другого типа данных (константа SizeOfReal может быть заменена на выхов оператора SizeOf(Type) для конкретного типа Type), других способов выделения и освобождения памяти (например, с использованием функций GetMem и FreeMem) и т.п. В случае двумерного преобразования используется та же функция, но последовательно, сначала для строк, потом для столбцов (или наоборот).


  13. Преобразование Уолша-Адамара Преобразование Уолша-Адамара. Существуют различные способы определения функций Уолша. Рассмотрим способ, основанный на взаимосвязи функций Уолша с функциями Радемахера. Последние определяются так:
    Функции Радемахера
    где Эта – безразмерное время (Диапазон значений Эта), k є N – порядок (номер) функции,
    Функция sign
    Система функций Радемахера ортонормированна на интервале (0,1), то есть
    Ортонормированность системы функций
    однако неполна.

    Функции Уолша, образующие полную ортонормированную систему, теперь можно определить так:
    Функции Уолша (5)
    где «(+)» – сложение по модулю 2; w – порядок (номер) функции; n=log2 N, где N=2n – количество функций системы; wii-тый разряд двоичного представления порядка функции w (отсчёт слева, начиная с 0).

    Функции Уолша могут служить базисом для спектрального представления сигнала, то есть любую интегрируемую на интервале Диапазон значений Эта функцию можно представить рядом по системе функций Уолша:
    Ряд Уолша
    с коэффициентами
    Коэффициенты ряда Уолша
    Способ нумерации функций в системе называется упорядочением. Функции Уолша, сформированные в соответствии с выражением (5), упорядочены по Уолшу. На практике также применяется упорядочение по Адамару (had(h,Эта)) и по Пэли (pal(p,Эта)).

    Функции had(h,Эта) можно сформировать с помощью матрицы Адамара. Матрицей Адамара HN порядка N=2n, n є N называется квадратная матрица размера N x N с элементами +1 такая, что
    HN x HNT = N x E,
    где HNT – транспонированная матрица, E – единичная матрица; при этом H1=1.

    Матрицу Адамара легко построить рекурсивно, так как:
    Рекурсивность матрица Адамара
    Функция Уолша, упорядоченная по Адамару (had(h,Эта)) с номером h, является последовательностью прямоугольных импульсов длительностью 1/N от интервала (0,1) с единичными амплитудами и полярностями, соответствующими знакам элементов h-той строки матрицы Адамара.

    Для цифрового анализа сигнала используются дискретные функции Уолша, которые являются отсчётами соответствующих непрерывных функций. Каждый отсчёт расположен в середине связанного с ним элемента непрерывной функции длительностью 1/N от интервала (0,1). Дискретные функции Уолша, упорядоченные по Уолшу, можно определить так:
    Дискретные функции Уолша
    где xkk-тый разряд в представлении номера отсчёта x в двоичной системе счисления:
    № отсчёта в двоичной системе
    Другой формой представления дискретных функций Уолша является матрица Адамара, номера столбцов которой соответствуют номерам дискретных значений (отсчётов) функций Уолша, а номера строк – номерам функций Уолша.

    Дискретное преобразование Уолша (ДПУ) определяется так:
    Дискретное преобразование Уолша
    что в матричном виде (дискретное преобразование Уолша – Адамара, ДПУ) выглядит так:
    Прямое ДПУ
    Соответственно, обратное ДПУ:
    Обратное ДПУ
    так как
    Матричное умножение
    где Обратная матрица – обратная матрица Адамара, а Hn*Hn-1=E – единичная матрица, при домножении на которую никакая матрица не изменяется.

    Схема быстрого преобразования Уолша – Адамара (БПУ) полностью аналогична схеме БПФ. Отличие в следующем:

    Двумерное БПУ определяется так:
    Двумерное БПУ
    где X – матрица N x N, где N=2n, n є N. Соответственно, обратное двумерное БПУ:
    Обратное двумерное БПУ
    На практике БПУ строится на основе ранее написанных процедур БПФ, в которых удаляется работа с мнимыми частями, переупорядочение перед рекурсивным вызовом и домножение на W при сборке.

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

© 2000-03 Mr. StingRay