Содержание к диссертации
Введение
Глава 1. Обзор ассоциативных сред и методов распознавания символов 10
1.1, Ассоциативные среды хранения и обработки информации 10
1.2, Организация ортокоординатных ассоциативных сред 17
1.3. Обзор и классификация методов кластеризации и распознавания 36
1.4. Выводы 45
Глава 2. Предварительная обработка символов в орто координатной ассоциативной среде 47
2.1. Задачи предварительной обработки информации при растровом представлении изображений 47
2.2. Метод стирания бахромы 48
2.3. Метод заполнения пустот 57
2.4. Метод утоньшения линий 70
2.5. Выводы 84
Глава 3. Распознавание символов в ортокоординатной ассоциативной среде методом опроса нормированных кодов символов 86
3.1. Принципы распознавания символов методом опроса нормированных кодов символов 86
3.2. Правила представления символов в матрице ортокоординатной ассоциативной среды 87
3.3. Алгоритм формирования кодов опроса в ортокоординатной ассоциативной среде 91
3.4. Алгоритм формирования библиотеки кодов эталонов символов русского алфавита 94
3.5. Алгоритм распознавания кодов символов, располагающихся в ор-гокоординатной ассоциативной среде 97
3.6. Выводы 104
Глава 4. Распознавание символов в ортокоординатнои ассоциативной среде методом секущих отрезков 105
4.1. Общие принципы метода секущих отрезков 105
4.2. Алгоритм формирования секущих отрезков 107
4.3. Минимизация секущих отрезков 111
4.4. Алгоритм распознавания символов, реализующий метод секущих отрезков 115
4.5. Выводы 124
Глава 5. Распознавание символов в ортокоординатнои ассоциативной среде методом выделения характерных узлов 125
5.1. Принципы распознавания символов методом выделения характерных узлов 125
5.2. Алгоритм формирования библиотеки кодов эталонов символов русского алфавита методом выделения характерных узлов 130
5.3. Алгоритм распознавания символов в ортокоординатой ассоциативной среде, методом выделения характерных узлов 134
5.4. Выводы 143
Заключение 145
Список литературы
- Организация ортокоординатных ассоциативных сред
- Метод заполнения пустот
- Правила представления символов в матрице ортокоординатной ассоциативной среды
- Алгоритм формирования секущих отрезков
Введение к работе
Актуальность темы
Стремительное развитие информационных технологий обусловлено универсальностью функциональных возможностей ЭВМ и проникновением ЭВМ во все сферы человеческой деятельности. При этом постоянно растущие скорость вычислений и объем хранимой в ЭВМ информации не могут в полной мере удовлетворить потребностей практики применения информационных технологий. Тем более, что возможности современной элементной базы и классической архитектуры аппаратных средств ЭВМ по быстродействию и производительности приближаются к физическим пределам. Выход за эти пределы возможен только при реализации новых идей в области аппаратно-программных средств и применения новых технологий, в частности, путем разработки методов и средств искусственного интеллекта, сочетающих в себе формальные подходы с эвристическими приемами, присущими человеку, основанными на принципах адаптации к окружающим условиям. Анализ показывает, что решение интеллектуальных задач основывается на специфических методах обработки огромного объема информации в условиях неполной или нечетко заданной информации. Попытки применения классических методов обработки данных в этих условиях требуют всё большего повышения быстродействия процессора и емкости памяти ЭВМ, Методы ассоциативной организации памяти позволяет в определенной мере решать эти проблемы, так как в этом случае на элемент памяти возлагаются также и некоторые функции обработки информации.
Ассоциативный способ основан на установлении некоторого соответствия, ассоциации между хранимой в ЗУ информации и поисковыми аргументами. Запоминающие устройства, в которых использован такой способ доступа, получили название ассоциативных ЗУ (АЗУ).
АЗУ характеризуются двумя основными признаками:
доступ к хранимой информации в АЗУ осуществляется исходя из её содержания;
при каждом обращении к АЗУ возможен параллельный доступ ко всей хранящейся информации.
Эти два признака определяют свойство «интеллектуальности» АЗУ. Первый из них определяет возможность обработки данных непосредственно в логико-запоминающей среде АЗУ, а второй обеспечивает возможность параллельный обработки информации.
АЗУ, реализующие помимо стандартных операций ассоциативной обработки информации, функции преобразования многомерной информации, называют многокоординатным АЗУ (МКАЗУ). Ассоциативное проецирование, ассоциативный поиск, ассоциативный опрос, комбинированные виды ассоциативных взаимодействий, определяющие концепцию иерархической по размерности многокоординатной ассоциативной памяти, позволяют выделить новый класс АЗУ - ортокоординатные АЗУ (ОКАЗУ) [3]. ОКАЗУ являются перспективным направлением в развитии интеллектуальных ЗУ. Они позволяют производить более эффективное по сравнению с традиционным АЗУ выполнение локальных и глобальных вычислений, линейных и нелинейных вычислений, интенсивное использование логико-запоминающей среды АЗУ, объектно и координатно ориентированных вычислений, символьных вычислений и вычислений на элементах, контекстно свободных и контекстно зависимых вычислений»
Данная работа посвящена исследованию свойств ортокоординатной ассоциативной среды (ОКАС) для обработки информации и разработке на основе результатов исследований методов и алгоритмов распознавания символьной информации. Работа является дальнейшим развитием исследований, проводимых на кафедре Вычислительной техники Московского энергетического института под руководством профессора Огнева И. В-
Цель работы состоит в исследовании свойств ортокоординатноЙ ассоциативной среды и в разработке новых методов распознавания символов в ортокоординатноЙ ассоциативной среде.
Для достижения поставленной цели в диссертации решаются следующие основные задачи:
исследование свойств ортокоординатноЙ ассоциативной среды, обеспечивающей совмещение функций хранения и обработки информации;
разработка методов и алгоритмов предварительной обработки символов в ортокоординатноЙ ассоциативной среде;
разработка метода опроса и алгоритма распознавания символов в ортокоординатноЙ ассоциативной среде;
разработка метода секущих отрезков и алгоритма распознавания символов в ортокоординатноЙ ассоциативной среде;
разработка метода выделения характерных узлов символов и алгоритмов распознавания в ортокоординатноЙ ассоциативной среде. Объектом исследований являются ортокоординатные ассоциативные
среды, применение их для разработки методов и алгоритмов предварительной обработки, кластеризации и распознавания символьной информации.
Методы исследования базируются на теориях арифметических и логических основ вычислительной техники, системного анализа. Экспериментальные исследования, выполненные для подтверждения полученных в ходе диссертационной работы результатов, проводились на основе моделирования на ЭВМ.
Научная новизна работы заключается в следующем:
разработаны и исследованы методы и алгоритмы предварительной обработки символов в ортокоординатноЙ ассоциативной среде;
разработаны методики реализации алгоритмов предварительной обработки символов в ортокоординатноЙ ассоциативной среде для применения их в задачах распознавания;
разработаны методы распознавания символов в ортокоординатной ассоциативной среде;
разработаны алгоритмы распознавания символов на основе предложенных методов;
разработаны методики и программы реализации алгоритмов распознавания символов в ортокоординатной ассоциативной среде. Практическая ценность
Практическая ценность работы состоит в следующем:
разработаны информационные программные модели предварительной обработки символов в ортокоординатной ассоциативной среде;
разработаны программы кластеризации и распознавания символов в ортокоординатной ассоциативной среде;
разработаны библиотеки нормированного представления символов в ортокоординатной ассоциативной среде.
Достоверность научных положений выводов и практических рекомендаций, сформулированных в диссертации, подтверждается вычислительными экспериментами и данными, полученными при моделировании на ЭВМ,
Апробация работы Основные результаты работы докладывались на: международных форумах информатизации МФИ - 2000, МФИ - 2002 и МФИ - 2003 «Информационные средства и технологии», секция «Интеллектуализация современных информационных средств и систем», и на девятой международной научно-технической конференции студентов и аспирантов, Москва-2003,
Публикации Основные результаты диссертации опубликованы в 4-х печатных работах.
1. Огнев И. В., Мд. Абдул Малек. Обработка матриц в ассоциативной среде // Сб. тр. МФИ - 2000, международный форум информатизации 2000. Информационные средства и технологии. - М., 2000. - с. 72 - 75.
Огнев И. В., Мд. Абдул Малек. Методы сортировки в многокоординатном ассоциативном ЗУ (МКАЗУ) // Сб. тр. МФИ - 2002, международный форум информатизации 2002. Информационные средства и технологии, - М, 2002.-с. 78-81.
Огнев И, В,, Мд, Абдул Малек. Особенности выполнения методов сортировки в ассоциативном ЗУ // Сб, тр. Девятая международная научно-техническая конференция студентов и аспирантов. - М,, 2003. - с, 325 - 326.
Огнев И. В., Мд. Абдул Малек. Распознавание символов в ассоциативной среде // Сб. тр. МФИ - 2003, международный форум информатизации 2003. Информационные средства и технологии. - М, 2003. -с. 15 - 19.
Структура и объем диссертационной работы Диссертация состоит из введения, пяти глав, заключения, списка литературы из 71 наименования и четырех приложений. Работа содержит 152 страницы текста, включая 34 рисунка, 22 таблицы, 6 страниц библиографии.
Основные научные положения, выносимые на защиту:
методы и алгоритмы предварительной обработки символов в ортокоординатной ассоциативной среде;
метод и алгоритм распознавания символов с помощью опросов нормализованных кодов символов в ортокоординатной ассоциативной среде;
метод и алгоритм распознавания символов методом выбранных секущих отрезков в ортокоординатной ассоциативной среде;
метод и алгоритм распознавания символов выделением характерных узлов в ортокоординатной ассоциативной среде.
Организация ортокоординатных ассоциативных сред
Существует множество проблем, связанных с уровнем современного производства, существенно ограничивающих емкость БИС АЗУ, которая у промышленно выпускаемых БИС АЗУ составляет на сегодняшний день от 1 до 16 Кбит, Тем не менее, АЗУ с успехом применяются в устройствах проведення операций сверки, учета и буферизации, выполняемых в ходе обмена данными и преобразования их в структуры. Хотя основная память в подобных устройствах не имеет средств адресации по содержанию, устройства на базе АЗУ позволяют существенно повысить их производительность.
Концепция орто координатных ассоциативных сред Построение ортокоординатных ассоциативных сред (ОКАС) базируется на концепции иерархической ассоциативной памяти (ИАП) [6]. В основу предложенной концепции иерархической по мерности многокоординатной ассоциативной памяти положена реализация определяющих принципов построения и функционирования иерархической по мерности модели представления данных, а также особенностей организации ассоциативных иерархическоих информационных взаимодействий в иерархической N - мерной ассоциативной памяти. Это, прежде всего: 1. иерархическая взаимосвязь между массивами ассоциативных элементов различной размерности, где размерность - это признак иерархии. В основе этого принципа лежит предложение о слоистости информационного поля. Причем, каждый уровень иерархически связан с другими и служит кроме банка информации директивным началом для более низких уровней. Выбор размерности в качестве признака иерархии позволяет определить подход к анализу исследуемых объектов, на основе которого можно подойти к вопросу изучения объектов высшей иерархии, анализируя отношения объекта более низкой размерности и их взаимосвязи с объектами более высокой размерности; 2. возможность осуществления ассоциативных взаимодействий по всем реализованным направлениям в каждом массиве ассоциативных элементов; 3. возможность обработки информации в логико-запоминающей среде самого устройства; 4. многопортовый доступ к информации. Доступ к накопителю ОКАС может осуществляться независимо и равноправно по каждой реализованной координате доступа; 5. лрограммируемость запоминающей среды; 6. возможность выполнения ассоциативных иерархических информационных взаимодействий, таких как ассоциативное иерархическое проецирование, ассоциативный иерархический поиск, ассоциативный иерархический опрос, ассоциативное иерархическое контекстное проецирование и комбинированные ассоциативные иерархические взаимодействия. Структуры ОКАС, основанные на принципах реализации ИАП, наиболее эффективны для решения задач анализа и обработки иконически представленной информации. Свойства ОКАС реализуется с наибольшей полнотой в случае соответствия размерности анализируемой информации размерности ассоциативного накопителя ОКАС. Так, ОКАС с двумерным ассоциатвным накопителем эффективны для анализа и обработки плоскостных объектов, а трехмерное ОКАС - трехмерных объектов.
Ортокоордннатные ассоциативные среды для решения задач обработки изображении и распознавания символов Рассмотрим организацию и принцип работы ОКАС с двумя координатами доступа. В структуре ОКАС, представленной на рис. 1.3, используется бинарная система представления информации. Решение о принятии такой системы представления информации продиктовано предже всего соображениями соответствия рассматриваемой структуры современной элементой базе. Также принята следующая нотация координат доступа: координата доступа X параллельна строкам накопителя ОКАС, координата доступа Y параллельна столбцам накопителя ОКАС. В состав ОКАС (см. рис. 1,3) входят следующие функциональные блоки: [AS]mxn - двумерный матричный двухпортовый ассоциативный накопитель. Размер накопителя п столбцов на m строк. Назначение накопителя: запись, хранение, считывание и обработка данных. Каждая ячейка ASjj, где i= i?,..m, j = 1,...п, хранит один бит информации; [С1]п — регистр аргумента поиска по координате X. Количество разрядов регистра равно количеству столбцов матрицы накопителя. Назначение регистра: запись, хранение и сдвиг аргумента поиска [М1]п - регистр маски аргумента поиска по координате X. Количество разрядов регистра равно количеству столбцов матрицы накопителя. Условие маскирования: если Mlj = 0 (или т), то все ячейки накопителя принадлежащие j-му столбцу матрицы накопителя ASij, где j = 1,...п, "замаскированы", то есть они не участвуют в выполнении операции и не влияют на формирование результата назначение регистра: запись, хранение и сдвиг маски аргумента поиска. Регистр управляет активностью столбцов накопителя; [Sl]m - регистр маски результата по координате X. Количество разрядов регистра равно количеству строк накопителя. Условие маскирования: если Slj - 0, то все ячейки накопителя принадлежащие і-ой строке матрицы накопителя ASjj, где і = l,...m, "замаскированы", т.е. они не участвуют в выполнении операции и не влияют на формирование отлика (состояние j-oro разряда регистра R1 не изменяется). Назначение регистра: запись, хранение и сдвиг маски результат- Регистр управляет активностью строк накопителя.
Метод заполнения пустот
К числу отклонений в растровом изображении символа, носящих случайный характер, относятся так называемые пустоты, т.е. группы незачер-ненных элементов внутри линий. В предельном случае, когда размер "пустоты" совпадает с шириной линии, возникает разрыв. Пустоты и разрывы весьма нежелательные явления, поэтому в процессе предварительной обработки они должны заполняться.
При точечном представлении изображения символа значение "1" соответствует принадлежности точки к некоторому символу. Значение "О" соответствует пустоте.
Метод заполнения пустот основан на предположении, что линия должна быть сплошной и, следовательно, обнаруженная пустота на линии должна быть загтолнена, то есть значение "О" соответствующее пустоте, должно быть заменено на "Г\ При этом предлагается, что ширине линии в растре соответствуют не более трех разрядов. Следовательно, понятию "пустоты" соответствует следующее состояния окрестности Мура: а) для центральной "точки пустоты" С (i, j) - окружение из семи и более "1" (рис. 23: 1 -8); б) для "точки пустоты", расположенной от центра окрестности Мура слева L (i, j) или справа R (i, j) или сверху U (i, j) или снизу D (i, j) - окружение из пя ти "Г (рис. 2.3: 9 -12); в) для "точки пустоты", расположенной по диагонали от центра окрестности Мура (обычно это крайние левые верхняя LU(iJ) или нижняя LD (i, j) точки линии и правые верхняя RU (i, j) или нижняя RD (i, j) точки линии) - окру жение из трех "1" (рис. 23: 13 -16).
Ситуации, в которых нулевые точки заменяются на единичные: в вариантах 1 - 8 нулевая точка является центральной; в вариантах 9-12 нулевые точки - крайние на ширине линии; в вариантах 13-16 нулевые точки -угловые точки на линии.
Реализация алгоритма заполнения пустот в ОКАС состоит в следующем: 1. первоначально точку с окрестностью Мура расположить в левом верхнем углу ассоциативного накопителя AS (координаты точки: І = 1, j = 1) (см_ рис. 1.4); 2. найти такие строки накопителя, (j - 1) - й, j - й и (] + 1) - й, разряды которых содержат комбинацию 101; 3. в строках, расположенных непосредственно над строками, обнаруженными в п. 2, проверить наличие в Q - 1) - м, j -MH(J + 1)-M разрядах комбинации 111; 4. в строках, расположенных непосредственно под строками, для которых выполнилась проверка п. 2, проверить наличие в (j - 1)- M,J-MH(J + 1) — М разрядах одной из трех комбинаций- llx, xll, 1x1; 5. в строках, расположенных непосредственно над строками, для которых выполнилась проверка п. 4, заменить "(Г на"1"; 6. в строках, расположенных непосредственно под строками, обнаруженными в п. 2, проверить наличие в (j - 1)-М, j - м и (j + 1)-М разрядах комбинации 111; 7. в строках, расположенных непосредственно над строками, для которых выполнилась проверка п, 2, проверить наличие в (j - 1)-М, J-MH(] + 1)—М разрядах одной из трех комбинаций - Ixl, xll, 1 їх; 8. в строках, расположенных непосредственно над строками, для которых выполнилась проверка п. 6, заменить "0" на "1"; 9. найти такие строки накопителя, B(]-])-M,J-MH(J + 1)-М разрядах которых находится комбинация 10х; 10. в строках, расположенных непосредственно над строками, обнаруженными в п. 9, проверить наличие в (j - 1)-M5J--MH(J + 1) — М разрядах комбинации 111; 11. в строках, расположенных непосредственно под строками, обнаруженными в п. 9, проверить наличие в(]-1)-м, J-MH(J+1)-M разрядах комбинации 111; 12. в строках, расположенных непосредственно над строками, для которых выполнилась проверка п. 11, заменить "0" на 4Ч"; 13. найти строки накопителя, в (j - 1)-м, j - м и (j + 1)-м разрядах которых находится комбинация х01; 14. в строках, расположенных непосредственно над строками, обнаруженными в п. 13, проверить наличие в (j - 1)-M,J-MH(J+ 1) — м разрядах комбинации 111; 15. в строках, расположенных непосредственно под строками, обнаруженными в и, 13, проверить наличие в (j - 1)-MJ-MH(J+ І ) М разрядах комбинации 111; 16. в строках, расположенных непосредственно над строками, для которых выполнилась проверка п. 11, заменить "О" на "1"; 17. найти такие строки накопителя, (j - 1) - й, j - й и (j + 1) - й, разряды которых содержат комбинацию 01х; 18. в строках, расположенных непосредственно над строками, обнаруженными в п. 17, проверить наличие в (j - 1) - м, j -ми(] + 1)-м разрядах комбинации 11х; 19. в строках, расположенных непосредственно под строками, обнаруженными в п. 17, проверить наличие в (j - 1)-м, J-MH(J+ 1)-м разрядах комбинации Их; 20. в строках, расположенных непосредственно над строками, для которых выполнилась проверка п. 19, заменить "0" на "1"; 21. найти такие строки накопителя, (j - 1)-й, j - и и (j + 1)- й, разряды которых содержат комбинацию х10; 22. в строках, расположенных непосредственно над строками, обнаруженными в п. 21, проверить наличие в (j - 1) - м, j MH(J + 1)-М разрядах комбинации xll; 23. в строках, расположенных непосредственно под строками, обнаруженными в п. 21, проверить наличие B(J-1)-M, J-MH(J+1)-M разрядах комбинации х 11.
Правила представления символов в матрице ортокоординатной ассоциативной среды
Представление символов в матрице ОКАС основывается на следующей предпосылке: любой символ алфавита изображается с помощью набора связанных отрезков верти кал ьного, горизонтального, и диагональных направлений с наклоном 45и 135,
Для нормированного представления символов в матрице ОКАС предполагается позиционирование символов, состоящее в следующем: 1. изображение символа в матрице ОКАС располагается, начинаясь с левого столбца и верхней строки матрицы. Тогда большинство изображений символов будет располагаться, начиная с левого верхнего элемента матрицы (А, Б, В, Г, Е, Ж, 3, И, К, М, Н, О, П, Р, С, Т, У, Ф, Ч, X, ц, ч, ш, щ, ы, ь, ээ ю, Я) (см, рис. 3.1); Исключение составляют такие символы, как Ли Д, коды которых не занимают левый верхний элемент матрицы, но начинаются обязательно с первого (левого) столбца, 2- толщина линии символа считается единичной, то есть кодируется только контур символа, следовательно, элементы матрицы ОКАС, соответствующие контуру символа, по горизонтали и по вертикали занимают по одному разряду; 3. исходя из предыдущего допущения (П. 2), коды соседних горизонтальных или вертикальных параллельных отрезков символов (например, вертикаль ные отрезки в символах А, Д, И, Н, П, Ц, Ш, Щ и горизонтальные отрезки в символах Б, В, Е, 3) располагаются соответственно в столбцах или в строках, отстоящих через два столбца или две строки, то есть между разрядами кодов таких параллельных отрезков находятся разряды пробелов ("нулевые" разря ды); Таким образом, пробелы между, соседними параллельными отрезками линий кодируются кодами, содержащими большинство разрядов, равных нулю. 4. исходя из п. 1 - 3 позиционирования, для кодирования любого из символов русского алфавита потребуется всего 7 строк матрицы ОКАС;
Количество столбцов зависит от ширины символа и варьируется от минимального количества в четыре столбца, для большинства символов до девяти столбцов для символа Щ. По пять столбцов требуется для представления кодов символов М и Т, По шесть столбцов требуется для символов Л и Ц. Коды символов Ж, Ф, X, Ш, Щ, Ы, Ю занимают по семь столбцов. По восемь столбцов требуется для единственного символа Д. 5. изображение диагональной линии должно иметь не менее трех элементов матрицы, имеющих единичные значения. Например, код символа М требует матрицы размером 7x5, в которой код прямой диагонали равен 11101, код обратной диагонали равен 10111 (см, рис, ЗЛ); 6. для кодирования вертикальных отрезков контуров символов, занимающих неполный столбец, следует предусматривать четыре разряда, принимающих значение "1", например для символов Б, Р, У, Ф, Ч, Ы, Ь, Я; 7. особенностью кодирования символов Э и 3 является то, что коды средних линий отличаются одним разрядом: для буквы Э - код 0111, для буквы 3 -код 1111. Учитывая сформулированные выше правила, символы русского алфавита будут представлены в матрице ОКАС в виде изображенном на рис, 3.1.
С учетом этих предпосылок для выбора минимального набора кодов опроса МС необходимо было провести исследование по возможности разделения всех кодов символов. В работе предлагается алгоритм, заключающийся в переборе девятиразрядных кодов опроса ОКАС по строкам и семиразрядных кодов по столбцам. Схема алгоритма формирования кодов опроса для распознавания символов приведена на рис. 3.3, Результаты исследования показали, что существует несколько вариантов наборов кодов опроса, обеспечивающих распознавание всех символов за два обращения к ОКАС- При двухкратном обращении к ОКАС существует всего два набора, обеспечивающие полное разделение (кластеризацию) всех символов.
Первый набор состоит из двух пар кодов опроса. При первом обращении к ОКАС код опроса С1 = 111111111 - по строке и код опроса С2 = 1111111 -по столбцу позволяют выделить (распознавать) символы М, Т, X, Щ. Распознавание остальных символов требует второго обращения к ОКАС, на котором кодами опроса являются по строке - код llllmmmmm, а по столбцу - один из трех кодов - код mmmlOOl или код mmmOOOO или код mmmlOOO, где m - замаскированные разряды. Кластеризация символов по этому набору кодов показана в виде дерева решений и в виде списков кодов распознавания всех символов русского алфавита (см. приложение 2).
Второй набор состоит из следующих двух пар кодов опроса. При первом обращении к ОКАС код опроса 100100000 - по строке и код опроса 1001001 - по столбцу позволяют выделить (распознавать) символы А, Б, В, Е, 3, И, К, Н» О, П, Р, Ц, Ь, Э, Я. При втором обращении код опроса 111 lmmmmm - по строке и код опроса mmml 111 - по столбцу обеспечивают разделения всех остальных символов русского алфавита.
Алгоритм формирования секущих отрезков
Суть алгоритма формирования секущих отрезков состоит в последовательном задании и сравнении на равенство (на полное совпадение) кодов отрезков длиной от 2 до 9 разрядов по строкам и от 2 до 7 разрядов по столбцам с соответствующими кодами фрагментов матрицы МС содержащей нормированные коды распознаваемого символа. Количество совпадений этих кодов фиксируется и образует по всем секущим для каждого символа так называемый эталонный код.
Количество непрерывных (связанных) единичных разрядов кода изображения символа, совпадающих с кодом одного из секущих отрезков, определяется за одну операцию ассоциативного поиска в накопителе ОКАС, так как возможна проверка совпадения кода секущего отрезка одновременно со всем кодами строк (или соответственно столбцов) МС.
Алгоритм состоит из двух частей: в первой части алгоритма формируются всевозможные горизонтальные секущие отрезки длиной от 2 до 9 разрядов, во второй части - вертикальные отрезки длиной от 2 до 7 разрядов. Максимальная длина отрезка определяется соответственно размерами матрицы МС, в которой хранится нормализованный код символа русского алфавита.
Далее описывается работа алгоритма, схема которого приведена на рис. 4.1 и 4,2. 1. На регистры опроса О и С2 ОКАС (см. рис. 1.4) подаются начальные значения кодов, определяющие формирования первого секущего отрезка длиной в два разряда, располагающегося в первой (верхней) строке матрицы символа: CI =1 lmmmmmmm; С2 -lmmmmmm, где, m - замаскированные разряды. Задаются текущий номер строки і = 1 и номер формируемого секущего отрезка К - 1. 2. Задается длина секущего отрезка j = 2, 3. Последовательно для каждого символа S (S - меняется от А до Я) русского алфавита подсчитывается количество совпадений N кодов строк матрицы нормированного представления символа с кодом CL Значение числа N зависит от конфигурации символа и секущей. Поэтому можно записать N (S? К). Полученные числа N (S, К) заносятся в разряды библиотеки эталонных кодов соответствующие номеру К секущего отрезка и символу S русского алфавита. Совокупность этих чисел для всех символов русского алфавита и образует библиотеку эталонных кодов символов,
Очевидно, что полный набор секущих отрезков позволяет сформировать коды, по которым обеспечивается надежное распознавание, но такой набор кодов является избыточным. Автором были проведены исследования на предмет поиска минимального набора секущих для решения задачи распознавания символов русского алфавита на ОКАС указанной структуры. В процессе поисков были сформированы основные рекомендации по набору секущих: количество секущих отрезков в наборе должно быть минимальным; набор секущих отрезков должен обеспечивать распознавание символов всего заданного алфавита; конфигурация и сложность секущих отрезков при сравнении кодов секущих отрезков с фрагментами кодов символов должна обеспечивать высокое быстродействие в соответствии о возможностям выбранных аппаратных средств. Например, для трехкоординатных ассоциативных сред вместо секущих отрезков применяются секущие плоскости, то есть матрица 7x9, а для ортокоординатных ассоциативных сред, рассматриваемых в данной работе, только вертикальные и горизонтальные секущие отрезки.
Цель минимизации состоит в определении такого минимального количества секущих отрезков, которое обеспечивает выделение (идентификацию) всего набора символов алфавита. Суть процедуры минимизации заключается в том, что на каждом шаге из всего списка возможных секущих отрезков последовательно выбирается очередной секущий отрезок и с его помощью проводится идентификация кодов символов на всех символах не идентифицируемых к данному шагу. При этом следует рассматривать применение данного отрезка либо к конкретной и единственной сроке (или столбцу) кода матрицы символа, либо одновре 112 менно ко всем строкам (или столбцам) этого кода. Это реализуется с помощью задания маски соответственно по столбцам (или строкам), то есть используются свойства (особенности) режимов работы ОКАС - маскирования строк и столбцов. Так, например, для заданного горизонтального отрезка длиной в семи разрядов проверка совпадения на равенство кодов первой строки символов с кодам этого секушего отрезка выполнится заданием в регистре опроса С1 кода 1И111Ш и в регистре маски Ml кода 1111111mm (см. рис. 1.4), а в С2 кода 1111111 ив М2 кода lmmmmmm, где, m - маскирование соответствующих строк со 2 по 7, Для проверки совпадения на равенство кодов всех строк символов с кодом данного секущего отрезка следует задать в регистре маски М2 = 1111111.
Возможны следующие подходы, отличающиеся способом выбора секущих отрезков. 1. Последовательной перебор - от секущего отрезка с максимальной длиной (9 разрядов - по строке и 7 разрядов - по столбцу) до минимальной длины секущих отрезков в два разряда последовательным уменьшением на один разряд. 2. Случайный выбор секущего отрезка из набора всевозможных отрезков, перечисленных в пункте 1. 3. Эвристический подход: выбор очередного секущего отрезка происходит на основе анализа конфигурации символов русского алфавита, оставшихся нераспознанными к данному шагу алгоритма, и подбора такого секущего отрезка, который, по мнению исследователя, дает некоторое удовлетворительное решение по разделению символов из списка оставшихся (нераспознанных) к данному шагу. Удовлетворительным будем считать решение, которое приводит к максимальному разделению оставшихся символов на подгруппы или к идентификации символов. Результаты исследования показали, что наиболее эффективным является эвристический подход, позволивший получить за приемлемое число попыток восемь секущих отрезков, обеспечивающих полное разделение всех символов русского алфавита по их нормированным кодам.
Примеры таких наборов секущих отрезков приведены на рис. 4.3 и 4.5, содержащих по 8 секущих отрезков. При этом набор, приведенный на рис. 4.5, дает лучший результат распознавания символов по количеству обращений к памяти (см. табл. 5). Пример формирования первого секущего отрезка в ОКАС приведен на рис. 4.4, а формирование остальных секущих отрезков, изображенных на рис. 4.3, приведено в приложении 3.
