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