ZX Review #7-8-9-10 08 ноября 1997

Форум - Алгоритм распознавания символов.

(c) Группа 'Light', г.Серпухов

     Алгоритм распознавания
            символов

   В последнее  время  все  чаще
встает  проблема   распознавания
текста с помощью компьютера.  Не
скроем, что сложность этой проб-
лемы не позволяет 100%  реализо-
вать ее даже на мощных компьюте-
рах, не говоря уже о  ZX-Speccy.
Однако  сама  проблема  является
настолько интересной, что  обхо-
дить ее стороной не стоит.
   В качестве  примера  разберем
алгоритм  распознавания  заранее
известных букв, составленных  из
символа '*'.
   Для удобства  представим, что
все поле состоит из точек. Итак,
пусть на прямоугольном поле раз-
мерами X строк и Y столбцов зна-
ками '*' изображены буквы П,Т,О,
С,Г.  Буквы  имеют  произвольные
размеры, форма букв  прямоуголь-
ная, толщина  линии - 1  символ.
Также допустим, что буквы  имеют
только прямую ориентацию (накло-
ны букв исключены). Буквы  между
собой не соприкасаются, а  мини-
мальная ширина и  высота  букв -
три символа.

   Таким образом, лист с данными
буквами будет выглядеть  следую-
щим образом:

  ┌───────────────────────────┐
  │...........................│
  │.*****..***.****.****.***..│
  │...*....*.*.*....*..*.*....│
  │...*....*.*.*....*..*.*....│
  │........*.*.*....****......│
  │............****...........│
  │...........................│
  └───────────────────────────┘
             рис. 1

   На этом листе изображены бук-
вы: Т, П, С, О, Г.

   Как  мы  видим, каждая  буква
занимает  некоторый  прямоуголь-
ник. Логичнее всего сделать так,
чтобы  программа   распознавания
сначала  считала  картинку, сос-
тавленную из символов, в двумер-
ный массив, а затем уже занялась
распознаванием символа. Т.е. бу-
ква 'С', изображенная на рис. 1,
запишется  в  массиве  следующим
образом:

             ┌────┐
             │1111│
             │1000│
             │1000│
             │1000│
             │1111│
             └────┘

   Теперь перейдем  к  алгоритму
распознавания символов. Рассмот-
рим угловые точки каждой из букв.

1. Левый верхний угол:

   .            .
  .** - т      .** - п,с,о,г
   .            *

2. Правый верхний угол:

   .            .
  **. - т,с,г  **. - п,о
   .            *

3. Левый нижний угол:

   *            *
  .** - с,о    .*. - т,г,п
   .            .

   Т.е., если левый верхний угол
буквы имеет форму

              .
             .**
              .

   то это значит, что на рисунке 
изображена буква "Т".

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

  ┌──────────────────────────┐
  │         S[Y-1,X]         │
  │S[Y,X-1]  S[Y,X]  S[Y,X+1]│
  │         S[Y+1,X]         │
  └──────────────────────────┘

S[Y,X] - центральный символ угла

   Отсюда видно, что  необходимо
найти  углы  нарисованных  букв.
Для начала найдем левый  верхний
угол.  Он  характеризуется  тем,
что для него  выполняются  одно-
временно три равенства:

S[Y,X]=1, S[Y,X-1]=0, S[Y-1,X]=0

   На данном этапе уже однознач-
но идентифицируется буква 'Т'. В
этом случае поиск  других  углов
буквы  уже  не  производится.  В
противном случае обнаружена  од-
на из букв: П,С,О,Г, и надо про-
должать  анализ  далее.   Правый
верхний угол мы  обнаружим, если
будем  двигаться  по   найденной
строке вправо до  тех  пор, пока
вместо '1' не встретим '0'.  Ле-
вый нижний угол можно найти сим-
метричным  способом.  Необходимо
только обратить внимание на  то,
что левый нижний угол для  буквы
'Т' - это ее ножка.

   Приведенный  здесь   алгоритм
распознавания можно  представить
в следующем виде:

           ┌──────────────────────────────────────────┐
           │        "идентифицируемый символ"         │
           │                    v                     │
           │            ┌────────────────┐            │
           │            │идентификация по│ "П С О Г"  │
           │ "Т"<───────┤левому верхнему ├──┐         │
           │            │    углу.       │  │         │
           │            └────────────────┘  │         │
           │                     ┌──────────┘         │
           │           ┌─────────v──────┐             │
           │     "С Г" │идентификация по│"П О"        │
           │    ┌──────┤правому верхнему├──────┐      │
           │    │      │    углу.       │      │      │
           │    v      └────────────────┘      v      │
           │ ┌────────────────────────────────────┐   │
           │ │идентификация по левому нижнему углу│   │
           │ └────────────────────────────────────┘   │
           │    v         v         v         v       │
           │   "С"       "Г"       "П"       "О"      │
           └──────────────────────────────────────────┘

   Естественно, данный  алгоритм
является  простейшим, однако  он
иллюстрирует один  из  возможных
методов распознавания  символов.
Ясно, что при идентификации всех
букв алфавита  алгоритм  распоз-
навания по трем углам не  сможет
однозначно идентифицировать сим-
вол. В  качестве  примера  можно
привести буквы "Л" и "А". Поэто-
му придется вводить дополнитель-
ные критерии распознавания.  Од-
нако для данного  примера, чтобы
его не усложнять и не  затумани-
вать принцип, мы не стали  этого
делать.
   В  принципе, данный  алгоритм
более подходит  для  распознава-
ния печатного текста, нежели ру-
кописного. Приведенный  алгоритм
заметно усложнится, если  допус-
тить, что на изображении  имеют-
ся дефекты, такие как пропадание
одного из символов, изображающих
букву, или  наоборот,  появление
лишнего  символа  в  изображении
буквы.
   Ну что, программисты! Сможете
решить эту задачу на Speccy?