3.7. ПОСТРОЕНИЕ ТАБЛИЦ ПЕРЕХОДОВ

Ниже будет рассмотрен процесс построения таблиц переходов и выходов синхронного автомата Мили, представляющего каждое из заданного ограниченного множества событий определенным

выходным сигналом. Как мы выяснили, события являются конечными и задаются на специальном языке, фактически перечисляющем все входящие в него цепочки (слова). Как показывает анализ таблицы описаний, в основной входной алфавит автомата для распознавания заглавных букв необходимо включить символы 1, 2, 3, 4, 1, причем символ 4 входит лишь в одно событие, представляемое в автомате сигналом М. Для упрощения физической реализации автомата целесообразно ввести еще один основной входной сигнал 0, который будет подаваться на вход автомата через тактов — в моменты окончания вертикального» и горизонтального просмотров. Условимся сопоставлять строки-таблиц переходов и выходов входным сигналам автомата, а столбцы — состояниям. Таким образом, в таблицах переходов — выходов основным сигналам 1, 2, 3, 4, 1, 0 соответствуют шесть строк

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

В выходной алфавит автомата включены: символы распознаваемого алфавита В; символы, соответствующие направлению-просмотра; символы, определяющие дополнительный сигнал при данном просмотре; отказ от распознавания символа — символ

Как уже отмечалось, анализ изображения начинается с последовательного просмотра слева направо, сверху вниз. Направления последующих просмотров зависят от результатов первого; целях ускорения процесса распознавания следующий просмотр может начинаться сверху, снизу, справа. Поэтому в число выходных сигналов автомата включены символы («верх», «низ», «лево», «право»).

Сигнал символа выдается в том случае, когда входная последовательность не входит ни в одно из представляемых сигналами событий.

Известно несколько алгоритмов получения таблиц переходов» и выходов по множествам входных последовательностей. В [14] наиболее подробно рассмотрена общая задача синтеза автомата по регулярным выражениям. В [25] наряду с вышеуказанными вопросами самостоятельно рассматривается задача построения таблиц переходов — выходов автомата, заданного соответствиями между входными и выходными последовательностями. Поскольку в [14, 25] рассматривается общая постановка задачи и даются общие алгоритмы ее решения, то изложенные в них результаты могут быть, очевидно, применены и в данном случае Однако необходимо учесть следующие факторы:

1. Язык изображений является специализированным языком, ориентированным на представление частного класса событий.

2. Описание события в этом языке учитывает лишь наиболее существенные части (подцепочки) входных слов. Тем не менее при получении описания учитывается, что между любыми двумя существенными элементами, определяемыми стандартным описанием, могут пошляться помехи — подцепочки, возникающие случайным и труднопредсказуемым образом. Поэтому при построении таблиц переходов — выходов должны быть приняты меры по фильтрации подцепочек, описывающих помехи. Ясно, что такая особенность накладывает свои требования на алгоритм получения таблиц

3. Алгоритмы, учитывающие специфику задачи, позволяют, как правило, достичь большого быстродействия и получить лучшее решение (в данном случае, получить таблицы с меньшим числом состояний), чем общие методы.

Как мы уже подчеркивали, одной из особенностей приведенных в табл. 3.1 описаний являются не заданные явным образом помехи, возникающие между подцепочками, входящими в описание.

Определение. Будем говорить, что некоторая буква алфавита стоит в описании событий, представляемых в автомате, на месте если среди описаний, приведенных в табл. 3.1, найдется хотя бы одно, в котором эта буква является Места нумеруются слева направо.

Пример. В описании символ 1 стоит на первом месте, 2 на втором, на третьем, четвертом.

Место описка помех определяется номером буквы, следующей за ним.

Пусть есть нижняя граница диапазонов длин подцепочек, соответствующих букве на месте.

Обозначим через длину наибольшей подцепочки из одинаковых бунв входящей в любой элемент списка помех, занимающей место между буквами и и не

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

Алгоритм построения таблицы переходов — выходов автомата Мили по заданным описаниям состоит в следующем:

0. Перед началом работы алгоритма по приведенным в табл. 3.1 описаниям строятся все вытекающие из них допустимые для каждого символа последовательности подцепочек. Эта задача решается довольно просто: каждый символ, заключенный в фигурные скобки, порождает две последовательности подцепочек — в одну из них соответствующая этому символу подцепочка не входит, в

Таблица 3.1. Стандартные описания машинописных прописных букв русского алфавита

(см. скан)

Окончание табл. 3.1

(см. скан)

другую — входит. Например (описание буквы Б), расписывается в восемь последовательностей подцепочек:

I. Если автомат находится в начальном состоянии (обозначим его через ), то под действием входного сигнала 4 он не должен? менять своего состояния. Это объясняется тем, что ни одна буква алфавита В не имеет в верхней части четырех пересечений.

II. Под действием сигналов 1, 2, 3, 1 автомат совершает переход из начального состояния в состояния соответственно. Эти состояния будем называть опорными. Процесс-перехода в опорные состояния осуществляется следующим образом: в состояние переход происходит через последовательность из промежуточных состояний, так что сначала из состояния совершается переход в промежуточные состояния из которых под действием сигнала автомат переходит в состояние и так далее до тех пор, пока не попадает в опорное состояние Опорное состояние не меняется под воздействием входного сигнала k. Если в промежуточных состояниях на вход автомата приходит сигнал то автомат переходит в состояние

III. Для состояний — повторяется второй этап с той лишь разницей, что входные сигналы для них определяются сим волами, стоящими на вторых местах в эталонных последовательностях. Под действием этих входных сигналов осуществляются переходы в следующие опорные состояния через ряды из промежуточных состояний. Остальные входные сигналы не меняют состояния автомата, если он находится в одном из опорных состояний Далее назначаются переходы в опорные состояния под действием подцепочек, определяемых символами, стоящими на третьих местах в последовательностях — эталонах, и т. д., когда требуется различить описания и подцепочки рассматриваются вместе с их диапазонами, назначается последовательность промежуточных переходов с числом состояний, равным общему диапазону длины данной подцепочки во всех описаниях. Переход под действием следующего за такой подцепочкой сигнала назначается из группы состояний, определяемой диапазоном конкретной подцепочки.

IV. После серии переходов в опорные состояния должна наступить одна из следующих ситуаций.

1. В опорное состояние автомат приходит под воздействием последовательности подцепочек, которая входит в описание лишь одного символа распознаваемого алфавита В. Такое состояние назовем конечным. Этот факт интерпретируется как завершение процесса распознавания. Автомат должен вернуться в исходное

состояние , а на его выходе должен быть выдан символ и сигнал перехода к распознаванию следующего символа.

2. В опорное состояние автомат приходит по окончании последовательности подцепочек соответствующих описаниям нескольких символов при просмотре изображения в горизонтальном направлении. Такое состояние назовем концевым. Для того чтобы обеспечить разделение горизонтального и вертикального описаний, будем переводить автомат из состояния в некоторое состояние под действием входного сигнала 0; при этом на выходе должен подаваться сигнал — верх, определяющий просмотр сверху вниз. Состояние рассматривается как начальное для последовательностей подцепочек входящих в описания тех образов, для которых оказалось концевым состоянием (для них выполняются этапы I—III).

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

В том случае, если эта ситуация обнаружится при горизонтальном просмотре, автомат переводится в некоторое состояние и совершается переход к вертикальному просмотру. Возникновение же такой ситуации при вертикальном просмотре свидетельствует о том, что в терминах основного алфавита соответствующие символы не будут различены. ЭВМ выдает на АЦПУ цепочки, переведшие автомат в состояние и соответствующие им изображения. Конструктор должен выбрать направление следующего просмотра и дополнительный сигнал, позволяющий распознать соответствующие классы при этом просмотре.

Весьма полезными являются следующие дополнительные входные сигналы:

1. Сигнал вырабатывается дискриминатором при следующих условиях, аналогичных где 0 — средняя ширина линии в символе

2. Сигнал Наличие этого сигнала на выходе дискриминатора свидетельствует о том, что в нижней (правой) половине символа имеется одно пересечение, т. е. где — -мерный вектор маска, в котором первые разрядов — нули, а остальные — единицы; — высота символа при горизонтальном просмотре и ширина — при вертикальном (3.15).

3. Сигнал появляется при следующих условиях:

4. Сигнал вырабатывается при

Пусть — инверсия вектора , т. е. значения двоичных компонент вектора обратны значениям соответствующих компонент вектора

5. Сигнал вырабатывается при Иначе говоря, этот сигнал появляется при наличии одного пересечения, расположенного в верхней левой половине символа.

6. Сигнал появится на выходе дискриминатора, если

7. Сигнал вырабатывается дискриминатором при условиях

8. Сигнал 10 выдается дискриминатором, если Здесь Н — средня» высота букв заданного шрифта. Этот параметр может задаватьси автомату перед началом чтении либо определяться в ходе процесса чтения. Отметим, что» сигнал используется только для различении букв .

9. Сигнал 11 вырабатываетси в том случае, если существует одно пересечение в середине изображения (например, при просмотре буквы Н в горизонтальном направлении весьма вероятно поивление такого сигнала).

10. Сигнал 12 появляется, если в изображении присутствуют два пересечения, т. е. удаленных друг от друга не более, чем на два» элемента растра.

V. Процесс построения таблиц будет закончен, когда для всех последовательностей-эталонов будут найдены конечные состояния и назначены выходные символы алфавита В.

Пример. Для иллюстрации алгоритма построим таблицы переходов — выходов для автомата, распознающего четыре заглавные буквы А, Б, В, Г. Будем рассматривать только описания, полученные при вертикальном просмотре. Как мы убедимся, этого достаточно распознавания указанных четырех, букв.

0. Расписываем описания выбранных букв (табл. 3.1), раскрывая фигурные скобки:

1. Сигналы 3, 4 не входит в описании (3.23), поэтому целесообразно исключить их из числа входных сигналов автомата, оставив лишь 1, 2, 1 и 0. Ясно, что сигналы 3, 4 могут возникнуть, как помехи, но в данном случае автомат такие помехи просто не воспринимает.

2. Анализ списков помех для этих букв дает следующие значения:

где v — номер последнего места в цепочке.

Таким образом, под воздействием сигнала 1 через промежуточные состоялся 2, 3, 4, 5 автомат переходит из начального состояния I в опорное состояние 6 (табл. 3.2), которое к тому же оказывается конечным (см. шаг 4 ситуация I), поскольку ни одна на рассматриваемых букв, кроме А, не начинается с подцепочки I.

Далее под воздействием входного сигнала 2 через промежуточные состояния 7—16 автомат переходит в опорное состояние 17, которое тоже является конечным по двум причинам. Во-первых, поскольку цепочка, состоищая полностью из сигналов 2, входит только в описание буквы В, то при отсутствия лосле сигнала 2 других входных сигналов автомат по сигналу 0 должен в этом состоянии выдать В. Во-вторых, если за подцепочкой придет сигнал I, то это тоже свидетельствует о том, что растре — символ В. Поэтому из состояния 17 под действием входного сигнала 1 автомат перейдет в исходное состояние I и выдаст символ В. С другой стороны, еслн вслед за подцепочкой, состоящей трех—восьми сигналов 2 поступит сигнал 1, то это будет говорить о том, что на растре находится буква Б. Поэтому элементы таблицы переходов, соответствующие состояниям 11—16 и входному сигналу 1, отмечаем переходом в состояние 1 и выходным сигналом Б.

Под действием входного сигнала 1 автомат непосредственно переходит в состояние , из которого под действием подцепочки из сигналов 2 через промежуточное состояние 21 в состояния 22—27. Из состояния 22—26 автомат вод действием подцепочки из единиц совершает серию последовательных переходов в состояния 30—34. При этом в зависимости от длины подцепочки осуществлиется разделение букв Б и Г: если подцепочка содержит больше четырех

Таблица 3.2. Построение таблиц Переходов — выходов (см. скан)

сигналов 1, то на растре — буква Г. Если же в состояниях 22—27 на входе автомата не появится иной сигнал, кроме 2, то при приходе сигнала 1 автомат распознает букву В То же самое он сделает, находясь в состоянии 27 при приходе 0. В состояниях 30—33 автомат должен выдать символ Б и вернуться состояние 1. Сигнал формируется автоматом при отказе от распознавания.

Рассмотренный пример показывает, что выбранные четыре заглавные буквы распознаются довольно просто, несмотря на возможные существенные отклонения: достаточно вертикального просмотра и автомат-координатор будет обладать лишь 34 состояниями. В общем случае, когда нужно распознать несколько десятков букв, задача усложняется настолько, что для построения координатора по описаниям целесообразно использовать ЭВМ. Число состояний резко возрастает с числом распознаваемых символов, что в свою очередь, увеличивает объем памяти, необходимый для реализации координатора. Поэтому необходимо производить сокращение количества состояний.