Rambler's Top100
"Knowledge itself is power"
F.Bacon
Поиск | Карта сайта | Помощь | О проекте | ТТХ  
 Подземелье Магов
  
 

Фильтр по датам

 
 К н и г и
 
Книжная полка
 
 
Библиотека
 
  
  
 


Поиск
 
Поиск по КС
Поиск в статьях
Яndex© + Google©
Поиск книг

 
  
Тематический каталог
Все манускрипты

 
  
Карта VCL
ОШИБКИ
Сообщения системы

 
Форумы
 
Круглый стол
Новые вопросы

 
  
Базарная площадь
Городская площадь

 
   
С Л С

 
Летопись
 
Королевские Хроники
Рыцарский Зал
Глас народа!

 
  
ТТХ
Конкурсы
Королевская клюква

 
Разделы
 
Hello, World!
Лицей

Квинтана

 
  
Сокровищница
Подземелье Магов
Подводные камни
Свитки

 
  
Школа ОБЕРОНА

 
  
Арсенальная башня
Фолианты
Полигон

 
  
Книга Песка
Дальние земли

 
  
АРХИВЫ

 
 

Сейчас на сайте присутствуют:
 
  
 
Во Флориде и в Королевстве сейчас  07:10[Войти] | [Зарегистрироваться]

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

Юрий Кисляков
дата публикации 02-03-2006 06:11

На написание данного материала меня подвигла одна, нередко встречающаяся в ответах на вопросы круглого стола, фраза:
"Если задумал написать свой … - даже не берись. Дело безнадежное. Это не для одиночек, и тем более не для начинающих (нужна команда серьезных математиков и программистов). Что касается различных "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.

Что дальше?

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

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

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

Юрий Кисляков


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


Смотрите также материалы по темам:
[Распознавание образов]

 Обсуждение материала [ 22-05-2010 08:03 ] 17 сообщений
  
Время на сайте: GMT минус 5 часов

Если вы заметили орфографическую ошибку на этой странице, просто выделите ошибку мышью и нажмите Ctrl+Enter.
Функция может не работать в некоторых версиях броузеров.

Web hosting for this web site provided by DotNetPark (ASP.NET, SharePoint, MS SQL hosting)  
Software for IIS, Hyper-V, MS SQL. Tools for Windows server administrators. Server migration utilities  

 
© При использовании любых материалов «Королевства Delphi» необходимо указывать источник информации. Перепечатка авторских статей возможна только при согласии всех авторов и администрации сайта.
Все используемые на сайте торговые марки являются собственностью их производителей.

Яндекс цитирования