[ главная ]   [ рейтинг статей ]   [ справочник радиолюбителя ]   [ новости мира ИТ ]



Ответов: 0
25-02-12 07:01







   Web - программирование
PHP


ASP






XML



CSS

SSI





   Программирование под ОС











   Web - технологии








   Базы Данных









   Графика






Данные




Программирование под ОС / Pascal - Delphi /

Реализация простейшего алгоритма распознавания графических образов

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

"Если задумал написать свой … - даже не берись. Дело безнадежное. Это не для одиночек, и тем более не для начинающих (нужна команда серьезных математиков и программистов). Что касается различных "know how", то вряд ли владеющий ими поделится с кем-либо. Такая информация стоит бооольших денег..."
На реализацию предлагаемого алгоритма у меня ушло примерно 15 часов.

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

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

Ниже приведены основные моменты реализации предлагаемого алгоритма.

Шаг 1. Создание канвы для рисования и формирование ее образа в памяти.

В качестве канвы используем класс TBitmap (для простоты работы с битмапом используем режим 1 байт на пиксель, т.е. TBitmap.PixelFormat := pf8bit), визуализируем его на TPaintBox, отображаем в памяти при помощи структуры:

type
  MasX = PByteArray;
var
  MasY : array of MasX // массив пикселей,
  {
  где MasY[y-коорд][x-коорд] = номер цвета в палитре цветов (при 8 бит/пиксель).
  Отображение осуществляем с использованием TBitmap.ScanLine (быстро и просто):
  SetLength(MasY, TBitmap.Height);
  for j := 0 to TBitmap.Height - 1 do
    MasY[j] := TBitmap.ScanLine[j];
}
Теперь с картинкой в виде матрицы XxY можно делать все что угодно…

Шаг 2. Формирование массива эталонных образцов символов.

Эталонные образцы будем формировать на основе матрицы размером 16х16. Для этого разработаем процедуру генерации такой матрицы по произвольному изображению эталона.

Процедура function Create_16x16(Img : TBitmap) : TMas16x16 получает в качестве параметра ссылку на картинку, на которой нарисован эталон символа (в нашем случае - программно), возвращает приведенную матрицу размером 16х16.

Кратко поясним работу процедуры (более полно см. комментарии в программе).

  1. Получаем ссылку на битмап и осуществляем его отображение в памяти (см. выше).

  2. Вычисляем координаты границ (описанного прямоугольника) образа (эталонного или распознаваемого) путем сканирования строк/столбцов. При этом здесь и при дальнейшем анализе изображения предполагается, что символ нарисован черным цветом (№0 в палитре цветов) и соответственно все значащие пиксели имеют значение 0.
    for j := 0 to Img.Height - 1 do                   // Top
      begin
        for i := 0 to Img.Width - 1 do
          if MasY[j][i] = 0 then
          begin yTop := j; break; end;
        if yTop = j then break;
      end;
    
      for j := Img.Height - 1 downto 0 do               // Bottom
      begin
        for i := 0 to Img.Width - 1 do
          if MasY[j][i] = 0 then
          begin yBottom := j + 1; break; end;
        if yBottom = j + 1 then break;
      end;
    
      for i := 0 to Img.Width - 1 do                    // Left
      begin
        for j := 0 to Img.Height - 1 do
          if MasY[j][i] = 0 then begin xLeft := i; break; end;
        if xLeft = i then break;
      end;
    
      for i := Img.Width - 1 downto 0 do                // Right
      begin
        for j := 0 to Img.Height - 1 do
          if MasY[j][i] = 0 then begin xRight := i + 1; break; end;
        if xRight = i + 1 then break;
      end;
    
  3. Для дальнейшего анализа потребуется некий критерий, по которому будет производиться свертка исходного изображения символа в матрицу 16х16. Таким критерием был выбран общий процент заполнения - отношение количества значимых пикселей (из которых состоит символ) к общему количеству пикселей в описанном вокруг исходного изображения прямоугольнике. Данный параметр может влиять на качество распознавания, причем если он больше 1 для распознаваемого символа будет соответствовать меньшее количество возможных альтернатив, при значении меньшем 1 - наоборот. В нашем случае коэффициент поправки принят равным 0,99.
    nSymbol := 0;
    for j := yTop to yBottom do
    for i := xLeft to xRight do
      if MasY[j][i] = 0 then inc(nSymbol);
    Percent := nSymbol / ((yBottom - yTop)*(xRight - xLeft));
    Percent := 0.99*Percent;
    
  4. Далее разбиваем прямоугольник с изображением символа на 16х16 ячеек путем деления сторон новой ячейки на 2. Запоминаем относительные координаты кождой ячейки и приступаем к заполнению матрицы 16х16. Принимаем в качестве критерия общий процент заполнения. Если в анализируемой ячейке процент заполнения больше, чем общий процент - соответствующий элемент матрицы 16х16 устанавливается в 1, в противном случае - в 0.

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

Шаг 3. Распознавание рисованных (от руки) символов.

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

Параметр (1 - Result[i]/256)*100%, где Result[i] - кол-во несовпадений для i - го символа, показывает "вероятность" соответствия образа конкретному символу.

Демонстрационная программа.

Пример работы демонстрационной программы

  1. Сгенерируйте массив шаблонов для букв или цифр, используя конкретный шрифт
  2. Нарисуйте от руки произвольную букву (русскую, прописную) или цифру
  3. Нажмите на кнопку анализ
  4. Исследуйте результат
  5. Очистите окно и повторите пп. 2-4.

Что дальше?

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

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

Буду рад, если этот материал кому-то пригодится.

К материалу прилагаются файлы:

Автор: Юрий Кисляков
Источник: www.delphikingdom.com




Комментарии

 Ваш комментарий к данному материалу будет интересен нам и нашим читателям!



Последние статьи: Программирование под ОС / Pascal - Delphi /

Работа со шрифтами на Win API
06-06-2010   

Сегодня поговорим о шрифтах, и о том, каким образом работать с ними на Win API. Нам потребуется переменная типа HFONT. Изменить стиль шрифта можно у любого компонента, я покажу это на примере кнопки... подробнее

Кол. просмотров: общее - 3397 сегодня - 0

Работа с таймером на Win API
06-06-2010   

Таймер - вещь в хозяйстве очень полезная. Если некое действие нужно повторять с определенной периодичностью, то таймер, это как раз то, что нужно... подробнее

Кол. просмотров: общее - 3416 сегодня - 0

Работа с мультимедийным таймером на Win API
06-06-2010   

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

Кол. просмотров: общее - 3541 сегодня - 1

Создание CheckBoxов средствами Win API
06-06-2010   

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

Кол. просмотров: общее - 3650 сегодня - 0

Создание группы RadioButton средствами Win API
06-06-2010   

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

Кол. просмотров: общее - 3464 сегодня - 0



  WWW.COMPROG.RU - 2009-2012 | Designed and Powered by Zaipov Renat | Projects