(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?
