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

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

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

Создание полотна для рисования и формирование его образа в памяти

В качестве полотна используем класс 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];
  }

Теперь с картинкой в виде матрицы X·Y можно делать все что угодно...

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

Эталонные образцы будем формировать на основе матрицы размером 16·16 пикселей. Для этого разработаем процедуру генерации такой матрицы по произвольному изображению эталона. Функция Create_16x16(Img: TBitmap): TMas16x16 получает в качестве параметра ссылку на картинку, на которой нарисован эталон символа (в нашем случае - программно), возвращает сгенерированную матрицу размером 16·16 пикселей.

Кратко поясним работу функции (более полно смотрите комментарии в исходных кодах программы). Получаем ссылку на растровое изображение и осуществляем формирование его образа в памяти (смотрите выше). Вычисляем координаты границ прямоугольника сформированного образа (эталонного или распознаваемого) путем сканирования строк/столбцов. При этом здесь, а также в дальнейшем анализе изображения, предполагается, что символ нарисован черным цветом (цвет с кодом 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;

Для дальнейшего анализа потребуется некий критерий, по которому будет производиться свертка исходного изображения символа в матрицу 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;

Далее разбиваем прямоугольник с изображением символа на 16·16 ячеек путем деления сторон новой ячейки на 2. Запоминаем относительные координаты каждой ячейки и приступаем к заполнению матрицы 16·16. Принимаем в качестве критерия общий процент заполнения. Если в анализируемой ячейке процент заполнения больше, чем общий процент - соответствующий элемент матрицы 16·16 устанавливается в 1, в противном случае - в 0.

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

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

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

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

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

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

Что дальше?

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

Буду рад, если этот материал кому-то пригодится. К материалу прилагаются файлы: Исходные коды проекта (5,8kb).

Юрий Кисляков, Королевство Delphi, 2 марта 2006 года