Исследование и разработка методов распознавания символов в ортокоординатной ассоциативной среде тема диссертации и автореферата по ВАК РФ 05.13.05, кандидат технических наук Мд. Абдул Малек

• Мд. Абдул Малек
• кандидат технических наук
• 2004

Оглавление диссертации кандидат технических наук Мд. Абдул Малек

ВВЕДЕНИЕ.

ГЛАВА 1. ОБЗОР АССОЦИАТИВНЫХ СРЕД И МЕТОДОВ РАСПОЗНАВАНИЯ СИМВОЛОВ.

1.1. Ассоциативные среды хранения и обработки информации

1.2. Организация ортокоординатных ассоциативных сред.

1.3. Обзор и классификация методов кластеризации и распознавания

1.4. Выводы.

ГЛАВА 2. ПРЕДВАРИТЕЛЬНАЯ ОБРАБОТКА СИМВОЛОВ В ОРТО-КООРДИНАТНОЙ АССОЦИАТИВНОЙ СРЕДЕ.

2.1. Задачи предварительной обработки информации при растровом представлении изображений.

2.2. Метод стирания бахромы.

2.3. Метод заполнения пустот.

2.4. Метод утоньшения линий.

2.5. Выводы.

ГЛАВА 3. РАСПОЗНАВАНИЕ СИМВОЛОВ В ОРТОКООРДИНАТНОЙ АССОЦИАТИВНОЙ СРЕДЕ МЕТОДОМ ОПРОСА НОРМИРОВАННЫХ КОДОВ СИМВОЛОВ.

3.1. Принципы распознавания символов методом опроса нормированных кодов символов.

3.2. Правила представления символов в матрице ортокоординатной ассоциативной среды.

3.3. Алгоритм формирования кодов опроса в ортокоординатной ассоциативной среде.

3.4. Алгоритм формирования библиотеки кодов эталонов символов русского алфавита.

3.5. Алгоритм распознавания кодов символов, располагающихся в ор-токоординатной ассоциативной среде.

3.6. Выводы.

ГЛАВА 4. РАСПОЗНАВАНИЕ СИМВОЛОВ В ОРТОКООРДИНАТНОЙ АССОЦИАТИВНОЙ СРЕДЕ МЕТОДОМ СЕКУЩИХ ОТРЕЗКОВ

4.1. Общие принципы метода секущих отрезков.

4.2. Алгоритм формирования секущих отрезков.

4.3. Минимизация секущих отрезков.

4.4. Алгоритм распознавания символов, реализующий метод секущих отрезков.

4.5. Выводы.

ГЛАВА 5. РАСПОЗНАВАНИЕ СИМВОЛОВ В ОРТОКООРДИНАТНОЙ АССОЦИАТИВНОЙ СРЕДЕ МЕТОДОМ ВЫДЕЛЕНИЯ ХАРАКТЕРНЫХ УЗЛОВ.

5.1. Принципы распознавания символов методом выделения характерных узлов.

5.2. Алгоритм формирования библиотеки кодов эталонов символов русского алфавита методом выделения характерных узлов.

5.3. Алгоритм распознавания символов в ортокоординатой ассоциативной среде, методом выделения характерных узлов.

5.4. Выводы.

Введение диссертации (часть автореферата) на тему «Исследование и разработка методов распознавания символов в ортокоординатной ассоциативной среде»

Актуальность темы

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

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

АЗУ характеризуются двумя основными признаками:

• доступ к хранимой информации в АЗУ осуществляется исходя из её содержания;

• при каждом обращении к АЗУ возможен параллельный доступ ко всей хранящейся информации.

Эти два признака определяют свойство «интеллектуальности» АЗУ. Первый из них определяет возможность обработки данных непосредственно в логико-запоминающей среде АЗУ, а второй обеспечивает возможность параллельный обработки информации.

АЗУ, реализующие помимо стандартных операций ассоциативной обработки информации, функции преобразования многомерной информации, называют многокоординатным АЗУ (МКАЗУ). Ассоциативное проецирование, ассоциативный поиск, ассоциативный опрос, комбинированные виды ассоциативных взаимодействий, определяющие концепцию иерархической по размерности многокоординатной ассоциативной памяти, позволяют выделить новый класс АЗУ - ортокоординатные АЗУ (ОКАЗУ) [3]. ОКАЗУ являются перспективным направлением в развитии интеллектуальных ЗУ. Они позволяют производить более эффективное по сравнению с традиционным АЗУ выполнение локальных и глобальных вычислений, линейных и нелинейных вычислений, интенсивное использование логико-запоминающей среды АЗУ, объектно и координатно ориентированных вычислений, символьных вычислений и вычислений на элементах, контекстно свободных и контекстно зависимых вычислений.

Данная работа посвящена исследованию свойств ортокоординатной ассоциативной среды (ОКАС) для обработки информации и разработке на основе результатов исследований методов и алгоритмов распознавания символьной информации. Работа является дальнейшим развитием исследований, проводимых на кафедре Вычислительной техники Московского энергетического института под руководством профессора Огнева И. В.

Цель работы состоит в исследовании свойств ортокоординатной ассоциативной среды и в разработке новых методов распознавания символов в ортокоординатной ассоциативной среде.

Для достижения поставленной цели в диссертации решаются следующие основные задачи:

• исследование свойств ортокоординатной ассоциативной среды, обеспечивающей совмещение функций хранения и обработки информации;

• разработка методов и алгоритмов предварительной обработки символов в ортокоординатной ассоциативной среде;

• разработка метода опроса и алгоритма распознавания символов в ортокоординатной ассоциативной среде;

• разработка метода секущих отрезков и алгоритма распознавания символов в ортокоординатной ассоциативной среде;

• разработка метода выделения характерных узлов символов и алгоритмов распознавания в ортокоординатной ассоциативной среде. Объектом исследований являются ортокоординатные ассоциативные среды, применение их для разработки методов и алгоритмов предварительной обработки, кластеризации и распознавания символьной информации.

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

Научная новизна работы заключается в следующем:

• разработаны и исследованы методы и алгоритмы предварительной обработки символов в ортокоординатной ассоциативной среде;

• разработаны методики реализации алгоритмов предварительной обработки символов в ортокоординатной ассоциативной среде для применения их в задачах распознавания;

• разработаны методы распознавания символов в ортокоординатной ассоциативной среде;

• разработаны алгоритмы распознавания символов на основе предложенных методов;

• разработаны методики и программы реализации алгоритмов распознавания символов в ортокоординатной ассоциативной среде. Практическая ценность

Практическая ценность работы состоит в следующем:

• разработаны информационные программные модели предварительной обработки символов в ортокоординатной ассоциативной среде;

• разработаны программы кластеризации и распознавания символов в ортокоординатной ассоциативной среде;

• разработаны библиотеки нормированного представления символов в ортокоординатной ассоциативной среде.

Достоверность научных положений выводов и практических рекомендаций, сформулированных в диссертации, подтверждается вычислительными экспериментами и данными, полученными при моделировании на ЭВМ.

Апробация работы Основные результаты работы докладывались на: международных форумах информатизации МФИ - 2000, МФИ - 2002 и МФИ - 2003 «Информационные средства и технологии», секция «Интеллектуализация современных информационных средств и систем», и на девятой международной научно-технической конференции студентов и аспирантов, Москва-2003.

Публикации Основные результаты диссертации опубликованы в 4-х печатных работах.

1. Огнев И. В., Мд. Абдул Малек. Обработка матриц в ассоциативной среде // Сб. тр. МФИ - 2000, международный форум информатизации 2000. Информационные средства и технологии. - М., 2000. - с. 72 - 75.

2. Огнев И. В., Мд. Абдул Малек. Методы сортировки в многокоординатном ассоциативном ЗУ (МКАЗУ) // Сб. тр. МФИ - 2002, международный форум информатизации 2002. Информационные средства и технологии. - М.,

2002.-с. 78-81.

3. Огнев И. В., Мд. Абдул Малек. Особенности выполнения методов сортировки в ассоциативном ЗУ // Сб. тр. Девятая международная научно-техническая конференция студентов и аспирантов. - М., 2003. - с. 325 - 326.

4. Огнев И. В., Мд. Абдул Малек. Распознавание символов в ассоциативной среде // Сб. тр. МФИ - 2003, международный форум информатизации

2003. Информационные средства и технологии. - М., 2003. - с. 15 - 19. Структура и объем диссертационной работы Диссертация состоит из введения, пяти глав, заключения, списка литературы из 71 наименования и четырех приложений. Работа содержит 152 страницы текста, включая 34 рисунка, 22 таблицы, 6 страниц библиографии.

Основные научные положения, выносимые на защиту:

1. методы и алгоритмы предварительной обработки символов в ортокоорди-натной ассоциативной среде;

2. метод и алгоритм распознавания символов с помощью опросов нормализованных кодов символов в ортокоординатной ассоциативной среде;

3. метод и алгоритм распознавания символов методом выбранных секущих отрезков в ортокоординатной ассоциативной среде;

4. метод и алгоритм распознавания символов выделением характерных узлов в ортокоординатной ассоциативной среде.

Заключение диссертации по теме «Элементы и устройства вычислительной техники и систем управления», Мд. Абдул Малек

ЗАКЛЮЧЕНИЕ

В диссертационной работе решена научно-техническая задача исследования и разработки методов и средств распознавания символов в ортокоординатной ассоциативной среде с учетом особенностей и принципов функционирования среды.

Список литературы диссертационного исследования кандидат технических наук Мд. Абдул Малек, 2004 год

1. Кохонен Т. Ассоциативные запоминающие устройства. - М.: Мир, 1982, -384 с.

2. Крайзмер Л. П., Бородаев Д. А., Гутенмахер Л. И. и др. Ассоциативные запоминающие устройства. - Л.: Энергия, 1967, - 183 с.

3. Огнев И. В., Борисов В. В., Интеллектуальные системы ассоциативной памяти М.: Радио и связь, 1996. -176 с : ил.

4. Огнев И. В., Сарычев К. Ф. Надежность запоминающих устройств. - М.: Радио и связь, 1988. - 224 с : ил.

5. Огнев И. В., Шамаев Ю. М. Проектирование запоминающих устройств: Учеб. Пособие. - М.: Высш. Школа, 1979. -320 с , ил.

6. Огнев И. В., Борисов В. В. Ассоциативные среды. - М.: Радио и связь, 2000.-312 с.

7. Огнев И. В., Борисов В. В. Проектирование систем ассоциативной памяти современных ЭВМ. - М.: Изд-во МЭИ, 1997. - 70 с.

8. Пат. № 2037892 РФ, МКИ G11C 15/00. Ассоциативные запоминающие устройство/ В. В. Борисов, И. В. Огнев. - Опубл. 1995, Бюл. № 17.

9. Фролов А. Б., Фролов Д. А. Алгоритмы распознавания упорядоченных объектов в системах принятия решений функционального типа. Вестник МЭИ, 1996. N6.

10. Фролов А. Б., Яко Э. Алгоритм распознавания частично упорядоченных объектов и их применение. Изд. АН СССР. Техническая кибернетика, 1990, N5.

11. Фролов А. Б., Фролов Д. А., Яко Э. Программируемые функциональные систем для распознавания упорядоченных объектов. Известия РАН, серия Теория и системы управления, 1997, N5.

12. СБИС для распознавания образов и обработки изображений. - М.: Мир, 1988.

13. Денисов В. М., Матвеев Ю. Н., Очин Е. Ф. Принципы организации систем обработки изображений на базе клеточной логики // зарубежная радиоэлектроника. - 1984. - N1.

14. Троффили Т., Марголус Н. Машины клеточных автоматов. Пер. с анг. - М.: Мир, 1991.

15. Фу К. структурные методы в распознавании образов. - М.: Мир. 1977.

16. Ярославский Л. П. Введение в цифровую обработку изображений, М.: Сов. Радио, 1969, 312 стр.

17. Стандартные прерывания BIOS, DOS и специализированных драйверов. Книга 1/ перевод с англ. Г. В. Зюзина. - М.: ЭНПО "Комплекс", 1992 - 96 с.

18. Романцев Ю. В., Тимофеев П. А, Шаньгин В. Ф. Защита информации м компьютерных системах и сетях/ Под ред. В. Ф. Шаньгина. - М.: Радио и связь, 1999.-328 с.

19. Огнев И. В., Мд. Абдул Малек. Обработка матриц в ассоциативной среде // Сб. тр. МФИ - 2000, международный форум информатизации 2000. Информационные средства и технологии. - М., 2000. - с. 72 - 75.

20. Огнев И. В., Мд. Абдул Малек. Методы сортировки в многокоординатном ассоциативном ЗУ (МКАЗУ) // Сб. тр. МФИ - 2002, международный форум информатизации 2002. Информационные средства и технологии. - М., 2002.-с. 7 8 - 8 1 .

21. Огнев И. В., Мд. Абдул Малек. Особенности выполнения методов сортировки в ассоциативном ЗУ // Сб. тр. Девятая международная научно-техническая конференция студентов и аспирантов. - М., 2003. - с. 325 - 326.

22. Огнев И. В., Мд. Абдул Малек. Распознавание символов в ассоциативной среде // Сб. тр. МФИ - 2003, международный форум информатизации 2003. Информационные средства и технологии. - М., 2003. - с. 15-19.

23. Амамия М., Танака Ю. Архитектура ЭВМ и искусственной интеллект: Пер. с Японск. - М.: Мир, 1993. - 400 с , ил.

24. Ахо, Альфред, В., Хопкрофт, Джон, Ульман, Джеффри, Д. Структуры данных и алгоритмы.: Пер. с англ.: Уч. Пос. - М.: Издательский дом «Вильяме», 2000. - 384 с. ил. - Парал. Тит. Англ.

25. Авдонин В. Б., Мякотина О. Л., Минина В., Либерман Е. А. Особенности пространственной организации системы, меняющей проницаемость мембраны в ответ на CAMP // Библеотечиские мембраны. 1993. Т. 10, № 6. 598-616.

26. Баклицкий В. К., Колосовская Т. П. Обработка информации комплексных системах наблюдения: Учеб. Пособие. - М.: Изд-во МАИ, 1993. 68 с : ил.

27. Белецкий Я. Энциклопедия языка Си: Пер. с польск.- М.: Мир, 1992. - 687 с , ил.

28. Березин Б. И., Березин Б. Начальный курс С и C++. -М.: ДИАЛОГ - МИФИ, 1996.-288 с.

29. Классификация и распознавание в дискретных системах. А. А. Болотов, А. Б. Фролов / Под ред. В. Н. Вагина. - М.: Изд-во МЭИ, 1997. - 120 с.

30. Бруно Бабэ Просто и ясно о Borland C++: Пер. с англ.- М.: Бином.- 400 с: ил.

31. Вирт Н. Алгоритм и структуры данных: Пер. с англ. - М.: Мир, 1989. - 360 с , ил.

32. Гончарский А. В., Кочиков И. В., Матвиенко А. Н. Реконструктивная обработка и анализ изображений в задачах вычислительной диагностики. -М.: Изд-во Моск. Ун-та, 1993. - 140 с : ил.

33. Закревский А. Д. Логический синтез каскадных схем. М.: Наука 1981.

34. Керниган Б., Ритчи Д. Язык программирования Си: Пер. с англ./ Под ред. И с предисл. Вс. Штаркмана. - 2-е изд., перераб. И доп.- М.: Финансы и статистика, 1992. - 272 с : ил.

35. Л. П. Крайзмер, Д. А. Бородаев, Л. И. Гутенмахер, Б. П. Кузьмин, И. Л. Смелянский, Ассоциативные Запоминающие Устройства. Под общей редакцией Л. П. Крайзмера - «Энергия» Ленинградское Отделение 1967. -182.

36. Т. Кохонен, Ассоциативная память, первод с английского. Издательства «Мир» Москва 1980. - 239 с :

37. Разработка диалоговых систем на языке си. Средства создания интерфейса. Князев А. В. - М.: Изд-во МЭИ, 1995. - 86 с.

38. Крайзмер Л. П., Матюхин А., Майоркин Г. Память кибернетических систем (основы мнемологии). М., Изд-во «Советское радио», 1971, 400 с.

39. Мелихов А. Н., Берштейн Л. С, Коровин Я. Ситуационные советующие системы с нечеткой логикой. - М.: Наука. Гл. ред. Физ. - мат. лит., 1990.-272 с.

40. Полупроводниковые БИС запоминающих устройств: Справочник/ В. В. Баранов, Н. В, Бекин, А. Ю. Гордонова и др.; Под ред. А. Ю. Гордонова и Ю. И. Дьякова. - М.: Радио и связь, 1987. - 360 с : ил.

41. Поиск, Первозванский А. А., Главная редакция физико-математической литературы изд-ва «Наука», М., 1970, 264 стр.

42. Пом А., Агравал О. Быстродействующие системы памяти: Пер. с англ. М.: Мир, 1987. - 264 ел., ил.

43. Потемкин И. Функциональные узлы цифровой автоматики. - М.: Энергоатомиздат, 1988. - 320 с : ил.

44. Прикладные нечеткие системы: Пер. с Японск./ К. Асаи, Д. Ватада, Иван и др.: под редакцией Т. Тэрано, К. Асаи, М. Сугэно. - М.: Мир, 1993. - 368 с , ил.

45. Уинер Р. Язык Турбо Си: Пер. с англ.- М.: 1991. - 384 с , ил.

46. Рыжиков Ю. И. Информатика. Лекции и практикум. - СПБ.: КОРОНА принт, 2000. - 256 с.

47. Радченко А. Н. Аппроксимация и точное формирование булевых функций многих переменных. 4. П. Эффективное построение ассоциативной памяти // Там же 1985. № 2. 98 - 106.

48. Радченко А. Н. Оптимизация распределенной ассоциативной памяти со случайной организацией // Биофизика. 1993 б. Т. 38. вып. 2. 294 - 299.

49. Радченко А. Н. Оптимальная самоорганизация ассоциативной памяти в случайной среде // материалы первой междунар. Конф. По проблемам самоорганизации и управления в сложных коммуникационных пространствах. 19-45 июня 1997, Россия СПБ. 1997. 49-52.

50. Радченко А. Н., Гольдин В. Е. Исследование модели ассоциативного обучения // Автоматики и вычислительная техника. 1969. № 6. 7-12.

51. Радченко А. Н. Ассоциативная память. Нейронные сети. Оптимизация нейропроцессоров. - СПБ.: Наука, 1998.-261 с.

52. Соломатин В. Ф. Теория ассоциативных запоминающих устройств с распределенной записью информации // Автометрия , 1982. № 1. 21-34.

53. Фролов А. А., Муравьев И. П. Нейронные модели ассоциативной памяти. М.: Наука, 1987.

54. Вопросы статической теории распознавания, под ред. Барского Б. В., - М.: Сов. Радио, 1967, 400 стр.

55. Горелик А. Л., Скрипкин В. А. Методы распознавания, - М.: Высшая школа, 1984, 222 стр.

56. Горелик А. Л., Гуревич И. Б., Скрипкин В. А. современное состояние проблемы распознавания, - М.: Радио и связь, 1985.

57. Загоруйко Н. Г. Методы распознавания и их применение, - М.: Сов. Радио, 1972, 206 стр.

58. Патрик Э. Основы теории распознавания образов, М.: Сов. Радио, 1980, 408 стр.

59. Претт У. Цифровая обработка изображений, в двух книгах, М.: Мир, 1982,790 стр.

60. Розенфельд А. Распознавание и обработка изображений с помощью вычислительных машин. М.: Мир, 1972, 230 стр.

61. Ту Дж., Гонзалес Р. Принцип распознавания образов, М.: Мир, 1978.

62. Фомин Я. А., Тарловский Г. Р. Статистическая теория распознавания образов, М.: Радио и связь, 1986, 264 стр.

63. Фор А. Восприятие и распознавание образов, М.: Машиностроение, 1989, 272 стр.

64. Ярославский Л. П. Введение в цифровую обработку изображений, М.: Сов. Радио, 1969,312 стр.

65. Дуда Р., Харт П. Распознавание образов и анализ сцен. - М.: Мир, 1976 511 с.

66. Бойцов В. М., Проценко И. В. Структурные алгоритмы распознавания: Тезисы доклада к конференции по проблемам навигации и управления. - Киев: КВВАИУ, 1986.

67. Валник В. Н.,Червоненкис А. Я. Теория распознавания образов. М.: Наука, 1974.415 с.

68. Ту Дж, Гонсалес Р. Принципы распознавания образов. М.: Мир, 1978. 411 с.

69. Хермен Г. Восстановление изображений по проекциям: Основы реконструктивной томографии. М.: Мир, 1983, 352 с.

70. Фурман Я. А., Юрьев А. Н., Яншин В. В. Цифровые методы обработки и распознавания бинарных изображений. - Красноярск: Изд-во Краснояр. Ун-та, 1992.-248 с.