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?



Другие статьи номера:

TR-DOS для начинающих - Окончание.

Компьютерная новелла - Prince of Persia.

Компьютерная новелла - Лазерная бригада (по игре Laser Squad).

Перекресток драконов - Игра Rapscallion.

Перекресток драконов - Игра The Runes of Zendos.

Перекресток драконов - Игра The Saga.

Перекресток драконов - Игра Witch's Cauldron.

Перекресток драконов - Создаём Адвентюру. Обзор редакторов.

Перекресток драконов - Создаём словарь к Адвентюрной игре.

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

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

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

Программы, которые мы выбираем - Несколько предложений по усовершенствованию ассемблера.

Программы, которые мы выбираем - Предложения по доработке ZX Word v2.5.

Программы, которые мы выбираем - Программа "Эмулятор Спектрума" v1.2.

Программы, которые мы выбираем - Что хотелось бы иметь в идеальном ассемблере.

Ретро - 40 лучших процедур: Копирование данных в памяти.

Ретро - 40 лучших процедур: Обмен токена.

Ретро - 40 лучших процедур: Определение адреса БЕЙСИК-строки.

Ретро - 40 лучших процедур: Определение длины БЕЙСИК-программы.

Ретро - 40 лучших процедур: Определение размера свободной памяти.

Ретро - 40 лучших процедур: Поиск и замещение строки.

Ретро - 40 лучших процедур: Поиск подстроки.

Ретро - 40 лучших процедур: Поиск строки.

Ретро - 40 лучших процедур: Составление списка переменных.

Ретро - 40 лучших процедур: увеличение и копирование экрана.

Ретро - 40 лучших процедур: Удаление REM-строк.

Ретро - 40 лучших процедур: Удаление блока программы.

Советы экспертов - Игра Fredloader.

Советы экспертов - Игра Robin of Sherwood: The Touchstones of Rhianon.

Советы экспертов - Игра Scorpions: Die Machines.

Советы экспертов - Игра Terropods.

Страничка iS-DOS - Описание рестартов системы IS DOS.

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

Форум - Время выполнения недокументированных команд процессора Z80.

Форум - Концепция экрана высокого цветового разрешения.

Форум - Несколько Pokes к играм. Программа Hacman96.

Форум - По поводу новых DOS и BIOS для Спектрума.

Форум - Программа Multicolor на любой модели компьютера. Использование 2-го экрана для Multicolor'а. Демонстрация текста. Электронные журналы.

Форум - Проект ZX Config.

Форум - Усовершенствование Art Studio. Идеи относительно компрессии файлов.

Форум - Эмулятор ZX Spectrum на IBM. По поводу шестнадцатеричной системы счисления. Программа ZX-Stars. Странности в Elita

Форум - Эффекты на бордюре и Multicolor.

Читатель-читателю - ZX Spectrum 128 - новые возможности, новые проблемы.

Читатель-читателю - Группа 'Light'. Спектрум и экспертная система.

Читатель-читателю - Драйвер принтера для Scorpion'а.

Читатель-читателю - Печать чисел в различных системах счисления.

Читатель-читателю - Программирование аркадной игры со скроллингом экрана.

Читатель-читателю - Процедура печати меток ассемблера XAS для монитора-отладчика STS 4.3.

Этюды - Атрибутная бегущая строка. "Гасилка" экрана. Упрощенный вариант процедуры "Занавес". Процедура гащения картинки. Процедура проявления картинки по точкам.

Этюды - Графический эффект "цветные полосы".

Этюды - Драйвер экрана для печати по 64 символа в строке.

Этюды - Комплект защит загрузчиков.

Этюды - Обращение к диску в режиме IM 2. Работа с диском нестандартного формата.

Этюды - Печать символа, увеличенного в 8 раз. Программа "наливания" экрана. Процедура гашения экрана по точкам. Очистка экрана как в Terminator'е. Поиск последовательности символов в памяти. Система перекодировки символьного набора.

Этюды - Программа - каталогизатор дисков.

Этюды - Программа вывода значений амплитуды каналов муз. сопроцессора на бордюр.

Этюды - Программа вывода картинки.

Этюды - Программа зажигания спрайта.

Этюды - Программа очистки заданного окна экрана.

Этюды - Программа сортировки массива по возрастанию. Процедура заполнения экрана заданным атрибутом. Процедура проявления картинки. Эффект летящих навстречу звезд. "Душ", идущий из верхнего левого угла экрана. Процедура "осыпания" картинки по пиксельным линиям. Программа "вытягивания" картинки под углом в 45 градусов. Три процедуры "Scroll".

Этюды - Процедура печати чисел.

Этюды - Процедура прорисовки символа с помощью атрибутов.

Этюды - Процедура проявления картинки. Fade-OUT эффект (картинка уходит за края экрана). Графический эффект "Фонтан". Fade-OUT эффект, имитирующий выключение телевизора. Процедура "зажигания" картинки. Программа плавной прорисовки картинки.

Этюды - Процедура рисования линии.

Этюды - Процедура составления оптимальной таблицы символов.

Этюды - Скроллинг строк текста в заданном окне. Атрибутный скроллер. Диагональный скроллинг.

Этюды - Спрайтовый скроллер. Процедуры проявления экрана.

Этюды - Укороченная процедура индикации амплитуды каналов муз. сопроцессора. Способ вычитания константы из регистровой пары HL.

Этюды - Формула для вычисления дня недели.


Темы: Игры, Программное обеспечение, Пресса, Аппаратное обеспечение, Сеть, Демосцена, Люди, Программирование

Похожие статьи:
Юмор - That is true.
От авторов - традиционное вступление.
Список BBS - Список ныне действующих BBS в городе С.-Петербурге.

В этот день...   18 июня