автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.05, диссертация на тему:Распознавание изображений в ассоциативной осцилляторной среде

На правах рукописи

604603994

Сидорова Надежда Андреевна

РАСПОЗНАВАНИЕ ИЗОБРАЖЕНИЙ В АССОЦИАТИВНОЙ ОСЦИЛЛЯТОРНОЙ СРЕДЕ

Специальность 05.13.05 - Элементы и устройства вычислительной техники и

систем управления

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

Москва - 2010

1 о ИЮН 2010

004603994

Работа выполнена на кафедре Вычислительной техники Московского энергетического института (технического университета).

Научный руководитель: доктор технических наук, профессор

Защита состоится 24 июня 2010 г. в 14 ч. 00 мин. на заседании диссертационного совета Д 212.157.16 при Московском энергетическом институте (техническом университете) по адресу. 111250, г. Москва, ул. Красноказарменная, д. 13, аудитория М-510.

С диссертацией можно ознакомиться в библиотеке Московского энергетического института (технического университета).

Отзывы в двух экземплярах, заверенные печатью организации, просьба направлять по адресу: 111250, г. Москва, Красноказарменная ул., д. 14, Ученый совет МЭИ(ТУ).

Автореферат разослан 21 мая 2010 г.

Ученый секретарь

диссертационного совета Д 212.157.16

Огнев Иван Васильевич

Официальные оппоненты: доктор технических наук, профессор

Парамонов Николай Борисович

кандидат технических наук, доцент Ладыгин Игорь Иванович

Ведущая организация ОАО «Концерн «Моринформсистема-Агат»,

г. Москва

кандидат технических наук, доцент

Чернов С. А.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

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

Аг>умтр1гг\тя гпгтрмрииыу ^ТЧМ пгтпрпрпартглг ттпрттттлжрнными гЬои

^т""*'——Jf—---г-------------- —I—1---------- —~' '----------------- 1 —

Нейманом принципами двоичной системы исчисления, программного управления, совместного хранения программ и данных в одной памяти, иерархической организации памяти, наличия команд условного перехода. Такая архитектура приводит к возникновению разрыва между быстродействием процессора и памяти. Это явление зафиксировано в законе Мура, который гласит: «в то время, как быстродействие процессоров возрастает на 60% ежегодно, время доступа к памяти сокращается менее, чем на 7% в год».

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

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

Ассоциативный способ доступа основан на установлении соответствия, ассоциации между хранимой в среде информацией и поисковыми аргументами. Ассоциативный способ доступа к информации обеспечивает:

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

• относительную независимость времени поиска информации от емкости памяти;

• внесение элементов обработки информации непосредственно в процесс

РИ « ГТ/-»<->ТМ ГГТП •

^шии! ни,

• обработку информации непосредственно в среде ее хранения.

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

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

На кафедре Вычислительной техники Московского энергетического института под руководством д.т.н., профессора Огнева И.В. более 25 лет ведутся исследование и разработка новых ассоциативных сред и методов ассоциативной обработки информации.

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

Распознавание изображений - научное направление, связанное с разработкой принципов и построением систем, предназначенных для определения принадлежности данного объекта к одному из заранее выделенных классов

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

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

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

• выбор ассоциативной среды для решения задач предварительной обра-

50ТКИ К раСПОЗНаоаНПЯ ЯЗОбраЖСНИП,

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

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

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

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

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

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

• выбор ПЛИС для аппаратной реализации ассоциативной осцилляторной среды предварительной обработки и распознавания изображений;

• оценка эффективности аппаратной реализации предварительной обработки и распознавания изображений в ассоциативной осцилляторной среде.

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

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

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

И р£С1ТС311£1Е2НКЯ ИЗОбр£Ж£НИЙ В £г>СОИ,ИЗТТД1зиЧХ СрСДс1Х",

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

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

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

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

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

• рассмотрено практическое применение ассоциативной осцилляторной среды предварительной обработки и распознавания изображений на примерах решения задач распознавания (случайных массивов, слов из словаря Брокгауза и Ефрона, китайских иероглифов, рукописных символов);

• разработана реализация базовых клеточных ансамблей ассоциативной ос-цилляторной среды на ПЛИС, которая может быть использована для исследования и разработки новых ассоциативных сред.

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

Апробация работы Основные результаты работы докладывались на международных научно-технических конференциях «Информационные средства и технологии» 2005, 2007 гг., на 8-ой международной научно-технической конференции «Информационные технологии и системы» 2008 г.; на 16 международной научно-технической конференции студентов и аспирантов «Радиоэлектроника, электротехника и энергетика» в 2010 г.

Публикации Основные результаты диссертации опубликованы в 6 печатных работах, 2 из которых опубликованы в издании, рекомендованном ВАК.

Структура и объем диссертационной работы Диссертационная работа изложена на 188 страницах, из них 153 страницы основного текста, 65 рисунков, 10 таблиц и состоит из введения, четырех глав, заключения, списка литературы из 70 наименований на 8 страницах и приложений на 35 страницах.

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

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

2. Система распознавания изображений методом секущих функций в ассоциативной осцилляторной среде. Реализация дерева распознавания в ассоциативной осцилляторной среде.

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

4. Аппаратная реализация ассоциативной осцилляторной среды предварительной обработки и распознавания изображений на ПЛИС.

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ

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

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

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

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

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

Из базовых клеточных ансамблей АОС (табл. 1) в диссертации разработаны ассоциативные осцилляторные среды и методы обработки информации в этих средах.

Табл. 1. Базовые клеточные ансамбли АОС

Название клеточного ансамбля АОС

Условное графическое обозначение

Таблица переходов

проводник

Вх Вых

0 0

1 1

узел

Вх Вых| Вых2

0 0 0

1 1 1

сумматор

+

Вх, Вх2 Вых

0 0 0

0 1 1

Вх, Вх2 Вых

1 0 1

1 1 1

умножитель

Вх, Вх2 Вых

0 0 0

0

Вх, Вх2 Вых

1 0 0

] 1 !

инвертор

Вх Вых

0 1

1 0

Блок Осн Вых Блок Осн Вых

0 0 0 1 0 0

0 1 1 1 1 0

блок

Ра Рг Р; Р,ых

0 0 0 0

0 0 1 1

0 1 0 1

0 1 1 1

Ро Рг Р, Рвых

1 0 0 0

1 0 1 0

1 1 0 0

1 1 1 1

дифференциальный блок

р,

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

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

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

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

1) метод не содержит вычислений, которые потребовали бы внесения изменений в базовые клеточные ансамбли среды и увеличения тем самым аппаратных затрат;

2) основная операция метода - сравнение, которое является также базовой ОПсрацйсИ обработки ДаНКЫл Б аСССцКаТИБНЫХ СрСДах;

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

Основные морфологические операции: объединение, пересечение, вычитание, дилатация, эрозия, замыкание, размыкание, «Успех/Неудача» выполняются над обрабатываемым изображением и примитивом - специальным изображением существенно меньшего, нежели обрабатываемое изображение размера.

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

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

Для сравнения методов математической морфологии с другими методами на примере алгоритмов определения контура изображений в работе предложено

маскируемое ассоциативное р сравнение

Б

Рис. 1. Схема универсального элемента АОС (начало)

Outline CC Delete Unite

Zap Dilate intersect Erode

WD R/S RF

хранение одного пикселя изображе ния на базе клето1

Т\

хранение результата морфологической обработки на базе клеточного ансамбля «накапливающий осциллятор»

Рис. 1. Схема универсального элемента АОС (окончание)

два коэффициента:

Коэффициент эффективности А'3 - это величина, характеризующая во

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

К,

мот .морфчАОС

Т

где Т

время нахождения контура для каждого метода, ТштмрфвЛ(К. -время нахождения контура в ассоциативной осцилляторной среде.

Коэффициент отличия К0 - это отношение числа пикселей контура каждого метода к числу пикселей, принадлежащих эталонному контуру;

1

Ц

россм.ммнк)

'мат.морф.I

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

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

Предложена структура системы предварительной обработки и распознавания изображений в ассоциативной осцилляторной среде (рис. 2).

Массив изображений (обучающая выборка)

Распознаваемое изображение

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

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

Реализован в ассоциативной осцилляторной среде метод секущих функций, предложенный Огневым А.И. в работе «Метод секущих функций в задачах теории информации».

Данный метод включает в себя два этапа: обучение и распознавание. На этапе обучения используется обучающая выборка, которая состоит из эталонных. изображений объектов тех классов, которые необходимо р~спгг51711''71 г -1-кущая - это множество пар: номер элемента изображения и его значение. Каждая секущая разделяет изображения на совпадающие с ней и несовпадающие. Одна итерация процесса обучения состоит из выбора секущей и разделения изображений обучающей выборки на две части. Разделение продолжается до тех пор, пока в каждой части не останется по одному изображению. В методе секущих функций формируется дерево, содержащее набор секущих, разделяющий обучающую выборку и сопоставляющее каждому изображению его сжатый код - путь по дереву от корня до листа с этим изображением. Этап распознавания заключается в прохождении распознаваемым изображением пути по дереву. В каждой вершине дерева распознаваемое изображение сравнивается с секущей. Распознаваемое изображение будет отнесено к тому классу, путь эталона которого оно повторило.

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

Вй

Входы liMXHyibK I

Рис. 3 Реализация узла дерева распознавания в АОС

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

В четвертой главе приведен обзор программируемых логических интегральных схем (ПЛИС) производства ALTERA как элементной базы для аппаратной реализации разработанных ассоциативных осцилляторных сред предварительной обработки и распознавания изображений.

Для каждого базового клеточного ансамбля АОС составлено описание на языке описания аппаратуры VHDL.

WMM

\

Ш ni Ьк Щ.

Ш (И

^ тт\

X

т

ж

■ шшш

____ IMF MÜ4 'М

^ if .I «Я fr

Г) Co4"t-C SW'M'fO У ((XJIUU)

n áí X !

mm

\

Искажение Максимальный % распознавания

Эталонное изображение, искажения отсутствуют (рис. Зл); 100

Точечные изображения (рис. За); 73

Точечные изображения с добавлением случайного шума (рис. 36); 65

50% буквы (рис. Зв); 65

Многократное ксерокопирование (рис. Зг); 96

Случайный шум (рис. Зд): 73

Водные искажения 1 (отражение) (рис. Зе); 87

Водные искажения 2 (волна) (рис. Зж); S5

Ошибки сканирования (т.н. «ветер») (рис. Зз); 91 |

Распыление 30% (рис. Зи); 60

Распыление 70% (рис. Зк); 45

Рис. 4 Результаты распознавания изображений иероглифов в АОС

В САПР Quartus II 8.1 Web Edition проведено моделирование, получены временные диаграммы работы клеточных ансамблей и разработанных на их основе ассоциативных сред. По результатам моделирования выполнены оценки быстродействия аппаратной реализации системы предварительной обработки и распознавания изображений в ассоциативной осцилляторяой среде на ПЛИС.

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

Проведено моделирование аппаратной реализации системы предварительной обработки и распознавания изображений в ассоциативной осциллятор-ной среде, получены оценки аппаратных затрат (табл. 2).

Табл. 2. Оценки аппаратных затрат на реализацию деревьев в ассоциативной осцилляторной среде

Семейство плис Кол-во логических элементов Объем встроенного ОЗУ, Кб Количество узлов дерева

Startix IV 72600-681100 6462 - 22977 5212-22977

Startix III 47500-338000 1836- 16232 1836- 16232

Startix II 15600- 179400 409-9163 409-9163

Startix 105/0-79040 898-7253 654-7253

Cyclone - III 5136 - 198464 414-8019 300-8019

В заключении приведены основные результаты работы. Основные результаты работы заключаются в следующем:

1. Проведен анализ ассоциативных сред и обоснован выбор ассоциативной осцилляторной среды для решения задачи предварительной обработки и распознавания изображений.

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

3. Разработан универсальный элемент ассоциативной осцилляторной среды, обрабатывающий один пиксель черно-белого изображения. Разработан универсальный элемент ассоциативной осцилляторной среды для обработки полутоновых изображений. Проведено моделирование универсальных элементов в системе Quartus II 8.1 Web Edition. Составлены таблицы входных, выходных, управляющих сигналов для универсального элемента. Построены временные диаграммы режимов его работы.

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

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

6. Разработана ассоциативная осцилляторная среда распознавания изображений методом секущих функций. Предложена реализация узла дерева распознавания в ассоциативной осггиллятооной среде.

7. Разработан программный комплекс для моделирования распознавания изображений; промоделирован ряд примеров (случайные массивы, словарь Брокгауза и Ефрона, китайские иероглифы, рукописные символы), проведена оценка скорости работы и точности метода распознавания изображений в ассоциативной осцилляторной среде.

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

9. Разработана аппаратная реализация предложенной системы предварительной обработки и распознавания изображений в ассоциативной осцилляторной среде на ПЛИС фирмы ALTERA с использованием САПР QU ARTUS II 8.1 Web Edition. Проведена оценка скорости распознавания и сложности реализации.

Основные положения диссертационной работы изложены в следующих публикациях:

1. Огнев И. В., Сидорова Н. А. Реализация генетического алгоритма формирования нечетких логических правил в ассоциативной осцилляторной среде // Информационные средства и технологии: труды Международной

научно-технической конференции (18-20 октября 2005 г.): в З-ч т. - М.: Янус-К, 2005. - 1 т. - С. 55 - 58.

2. Огнев И.В., Сидорова Н. А. Обработка изображений методами математической морфологии в ассоциативной осцилляторной среде // Известия высших учебных заведений. Поволжский регион. - 2007. - Вып. 4. - С. 87 - 97. - (Технические науки).

3. Огнев И. В., Сидорова Н. А. Реализация методов математической морфологии в ассоциативной осцилляторной среде // Информационные средства и технологии: труды Международной научно-технической конференции (16-18 октября 2007 г.): в З-ч т. -М.: МЭИ, 2007. - 1 т. - С. 25 - 29.

4. Огнев И.В., Сидорова H.A. Реализация древовидных структур в ассоциативной осцилляторной среде (тезисы доклада) // Труды 8-ой международной научно-технической конференции «Информационные технологии и системы». Часть 1. - 2008 г. - издательство Пензенского гос. университета.-с. 165-171.

5. Огнев И.В., Сидорова H.A. Реализация системы обработки и распознавания образов в ассоциативной осцилляторной среде // Известия высших учебных заведений. Поволжский регион. - 2008. - Спец. вып. 2. - с. 98 -104. - (Технические науки).

6. Огнев И.В., Сидорова H.A. Реализация деревьев с использованием ресурсов памяти ПЛИС // РАДИОЭЛЕКТРОНИКА, ЭЛЕКТРОТЕХНИКА И ЭНЕРГЕТИКА: Шестнадцатая Междунар. научн.-техн. конф. Студентов и аспирантов: Тез. докл. В 3 т. Т. 1. - М: Издательский дом МЭИ, 2010. -с. 394-395.

Подписано в печать /бзак. 1Ю Тир. (00 П.л. Ш Полиграфический центр МЭИ(ТУ) Красноказарменная ул., д. 13

Введение.

1. Ассоциативные среды. Выбор типа ассоциативной среды для решения задачи предварительной обработки и распознавания изображений

1.1. Однородные среды.

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

1.3. Обзор ассоциативных сред.

1.3.1. Многокоординатные ассоциативные среды.

1.3.2. Ассоциативная среда с локальными связями.

1.3.3. Ассоциативная среда с командным управлением.

1.3.4. Ассоциативная осцилляторная среда.

1.4. Выбор типа ассоциативной среды для решения задач предварительной обработки и распознавания изображений.

1.5. Выводы.

2. Предварительная обработка изображений в ассоциативной осцилляторной среде.

2.1. Выбор метода предварительной обработки изображений.

2.2. Виды предварительной обработки изображений.

2.3. Математическая морфология.

2.3.1. Морфологические операции.

2.4. Использование механизма ассоциации.

2.5. Морфологическая обработка одного пикселя изображения в АОС.

2.6. Морфологическая обработка полутоновых изображений в АОС.

2.7. Алгоритмы морфологической обработки изображений в АОС.

2.8. Выводы.

3. Распознавание изображений в ассоциативной осцилляторной среде.

3.1. Обзор методов распознавания в ассоциативных средах.

3.2. Метод секущих функций в теории распознавания изображе

3.3. Построение дерева в ассоциативной осцилляторной среде.

3.4. Система распознавания изображений в ассоциативной осцилляторной среде.

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

3.5.1. Массивы с заданным законом распределения.

3.5.2. Энциклопедический словарь Брокгауза и Ефрона.

3.5.3. Китайские иероглифы.

3.5.4. Рукописные символы.

3.6. Выводы.

4. Аппаратная реализация на ПЛИС ассоциативной осцилляторной среды предварительной обработки и распознавания изображений

4.1. Обзор ПЛИС. Выбор ПЛИС для моделирования.

4.2. Методика аппаратной реализации дерева секущих с использованием встроенной памяти ПЛИС.

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

4.4. Аппаратная реализация на ПЛИС ассоциативной осцилляторной среды предварительной морфологической обработки изображений

4.5. Аппаратная реализация на ПЛИС ассоциативной осцилляторной среды распознавания изображений методом секущих функций.

4.6. Выводы.

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

Темп прогресса вычислительной техники много выше, нежели в других технических областях. Однако, повышению производительности вычислительных устройств препятствует несколько проблем [1,2].

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

Архитектура современных ЭВМ определяется предложенными фон Нейманом принципами двоичной системы исчисления, программного управления, совместного хранения программ и данных в одной памяти, иерархической организации памяти, наличия команд условного перехода. Такая архитектура приводит к возникновению разрыва между быстродействием процессора и памяти. Это явление зафиксировано в законе Мура, который гласит: «в то время, как быстродействие процессоров возрастает на 60% ежегодно, время доступа к памяти сокращается менее, чем на 7% в год».

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

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

Ассоциативный способ доступа основан на установлении соответствия, ассоциации между хранимой в среде информацией и поисковыми аргументами. Ассоциативный способ доступа к информации обеспечивает:

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

• относительную независимость времени поиска информации от емкости памяти;

• внесение элементов обработки информации непосредственно в процесс самого доступа;

• обработку информации непосредственно в среде ее хранения.

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

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

На кафедре Вычислительной техники Московского энергетического института под руководством д.т.н., профессора Огнева И.В. более 25 лет ведутся исследования и разработка новых ассоциативных сред и методов ассоциативной обработки информации [2, 5, 6, 7].

Разработка новых ассоциативных осцилляторных сред (АОС) [3, 4], успехи электронных технологий открыли принципиально новые возможности для решения интеллектуальных задач. Одной из важнейших задач в области искусственного интеллекта является задача распознавания изображений.

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

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

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

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

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

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

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

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

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

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

• выбор ПЛИС для аппаратной реализации ассоциативной осцилляторной среды предварительной обработки и распознавания изображений;

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

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

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

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

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

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

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

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

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

• рассмотрено практическое применение ассоциативной осцилляторной среды предварительной обработки и распознавания изображений на примерах решения задач распознавания (случайных массивов, слов из словаря Брокгауза и Ефрона, китайских иероглифов, рукописных символов);

• разработана реализация базовых клеточных ансамблей ассоциативной осцилляторной среды на ПЛИС, которая может быть использована для исследования и разработки новых ассоциативных сред.

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

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

Реализация результатов работы

Разработанная программная модель ассоциативной осцилляторной среды предварительной обработки и распознавания изображений использована при создании модельного и алгоритмического обеспечения ассоциативных сетей обработки знаний в рамках МИР ООО «НПП «Этна - Информационные технологии».

Научные и практические результаты работы включены в курс лекций «Организация ЭВМ и систем» на кафедре вычислительной техники ГОУ ВПО «МЭИ(ТУ)», используются в лабораторной работе «Ассоциативные запоминающие устройства», в дипломном проектировании студентов.

Апробация работы. Основные результаты работы докладывались на международных научно-технических конференциях «Информационные средства и технологии» 2005, 2007 гг., на 8-ой международной научно-технической конференции «Информационные технологии и системы» 2008 г.; на 16 международной научно-технической конференции студентов и аспирантов «Радиоэлектроника, электротехника и энергетика» в 2010 г.

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

Структура и объем диссертационной работы. Диссертационная работа изложена на 188 страницах, из них 152 страницы основного текста, 65 рисунков, 10 таблиц и состоит из введения, четырех глав, заключения, списка литературы из 70 наименований на 8 страницах и приложений на 36 страницах. Основные положения, выносимые на защиту

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

1. Проведен анализ ассоциативных сред и обоснован выбор ассоциативной осцилляторной среды для решения задачи предварительной обработки и распознавания изображений.

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

3. Разработан универсальный элемент ассоциативной осцилляторной среды, обрабатывающий один пиксель черно-белого изображения. Разработан универсальный элемент ассоциативной осцилляторной среды для обработки полутоновых изображений. Проведено моделирование универсальных элементов в системе Quartus II 8.1 Web Edition. Составлены таблицы входных, выходных, управляющих сигналов для универсального элемента. Построены временные диаграммы режимов его работы.

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

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

6. Разработана ассоциативная осцилляторная среда распознавания изображений методом секущих функций. Предложена реализация узла дерева распознавания в ассоциативной осцилляторной среде.

7. Разработан программный комплекс для моделирования распознавания изображений; промоделирован ряд примеров (случайные массивы, словарь Брокгауза и Ефрона, китайские иероглифы, рукописные символы), проведена оценка скорости работы и точности метода распознавания изображений в ассоциативной осцилляторной среде.

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

9. Разработана аппаратная реализация предложенной системы предварительной обработки и распознавания изображений в ассоциативной осцилляторной среде на ПЛИС фирмы ALTERA с использованием САПР QUARTUS II 8.1 Web Edition. Проведена оценка скорости распознавания и сложности реализации.

Заключение.

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

1. Ревизия первооснов конец застоя?/ Черняк Л. //Открытые системы. -2003 г.-№5.-с. 39-41.

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

3. Комаров А. Н. Исследование и разработка ассоциативных сред и методов обработки информации. Диссертация на соискание учёной степени кандидата технических наук. М.: МЭИ(ТУ), 2002. - 194 с.

4. Подолин П. Б. Исследование ассоциативных осцилляторных сред на примере задачи распознавания образов. Магистерская диссертация. М.: МЭИ(ТУ), 2005,- 117 с.

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

6. Огнев И. В., Подолин П. Б. Распознавание символов в ассоциативной ос-цилляторной среде. М: Известия высших учебных заведений Поволжского региона. Технические науки №6/27, 2006. - с. 55-67.

7. А. с. № 1718274, МКИ G11С 15/00. Ассоциативное запоминающее устройство / И.В. Огнев, О. В. Исаев, В.В. Борисов и Консташтиювский В.М. — Опубл. 1992, Бюл. № 9.

8. А. с. № 1793475, МКИ G11С 15/00. Ассоциативное запоминающее устройство / И.В. Огнев, В.В. Борисов, О.В. Исаев. Опубл. 1993, Бюл. № 5.

9. А. с. № 1805499, МКИ G11C 15/00. Ассоциативное запоминающее устройство / И.В. Огнев, В.В. Борисов. Опубл. 1993, Бюл. № 12.

10. А. с. № 1824650, МКИ в1 1С 15/00. Ассоциативное запоминающее устройство / И.В. Огнев, В.В. Борисов. Опубл. 1993, Бюл. № 24.

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

12. Пат. № 2025795 РФ, МКИ вПС 15/00. Иерархическая система ассоциативной памяти/ В.В. Борисов, И.В. Огнев. Опубл. 1994, Бюл. № 24.

13. А. с. № 1718275, МКИ вПС 15/00. Ячейка ассоциативной памяти/И.В. Огнев, О.В. Исаев, В.В. Борисов и др. Опубл. 1992, Бюл. № 9.

14. Пат. № 2107995 РФ, МКИ вПС 15/00. Ассоциативная запоминающая матрица/ В.В. Борисов. Опубл. 1998, Бюл. № 9.

15. Пат. № 2025797 РФ, МКИ вПС 15/00. Ассоциативная запоминающая матрица/ И.В. Огнев, В.В. Борисов. Опубл. 1994, Бюл. № 24.

16. Пат. № 2065207 РФ, МКИ СПС 15/00. Ассоциативная запоминающая матрица/ И.В. Огнев, В.В. Борисов. Опубл. 1996, Бюл. № 22.

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

18. Мд. Абдул Малек. Исследование и разработка методов распознавания в ортокоординатной ассоциативной среде. Диссертация на соискание учёной степени кандидата технических наук. - М.: МЭИ(ТУ), 2004. - 152 с.

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

20. Матвеев П. С. Исследование и разработка ассоциативной среды с локальными связями, реализующей полный набор операций клеточной логики для связности элемента равной восьми. Магистерская диссертация. М.: МЭИ(ТУ), 2006.- 117 с.

21. Гонсалес Р., Вудс Р. Цифровая обработка изображений: Пер. с англ. М.: Техносфера, 2005. - 1072 с.

22. Потапов A.C. Распознавание образов и машинное восприятие: общий подход на основе принципа минимальной длины описания. СПб.: Политехника, 2007. - 548 с.

23. Шкурский Б. И. Цифровые методы обработки изображений. М: Издательство МЭИ, 2005. - 152 с.

24. Young N. Mathematical Morphology. Graphics&Media Lab Digest December 21,2001 Issue 5.

25. Коневский О. Jl. Адаптивная морфологическая обработка бинарных контуров. / Исследовано в России, том 4. 1722-1731 с.

26. И. В. Огнев, Н. А. Сидорова Обработка изображений методами математической морфологии в ассоциативной осцилляторной среде / Известия высших учебных заведений. Поволжский регион. 2007. - Вып. 4, - С. 87 - 97. -(Технические науки).

27. Дьяконов В. П. MATLAB 6.5 SP 1/7/7 SP1 Simukink 5/6. М.: СОЛОН-Пресс, 2005.-400 с.

28. Пенроуз Р. Новый ум короля. О компьютерах, мышлении и законах физики.: Пер. с англ./ Общ. ред. В.О. Малышенко. Предисл. Г.Г. Малинецкого.

29. Изд. 2-е, испр. M.: Едиториал УРСС, 2005. - 400 с.

30. Клорене Д. Распознавание образов. Исследование живых и автоматических распознающих систем.: Пер. с англ. М.: Мир, 1970. - 288 с.

31. Рассел С., Норвиг П. Искусственный интеллект. Современный подход.: Пер. с англ. М.: Вильяме, 2006. - 1408 с.

32. Барский А.Б. Нейронные сети: распознавание, управление, принятие решений. — М.: Финансы и статистика, 2004. -— 176 с.

33. В. С. Симанков, Е. В. Луценко. Адаптивное управление сложными системами на основе теории распознавания образов. Краснодар: Техн. ун-т Ку-бан. гос. технол. ун-та, 1999. — 318 с.

34. Ричардсон Дж. М. Распознавание образов и теория групп.: Пер. с англ. -М.: Мир, 1981. -25 с.

35. Болотов A.A. О метрической кластеризации. / Дискретная математика. Т. 8. Вып. 4, 1996.-62-78 с.

36. Закревский Д.А. Логика распознавания. Минск: Наука и техника, 1988. -119 с.

37. Брусенцов И.П., Владимирова Ю.С. Конструктная компьютеризация силлогистики / Математические методы распознавания образов // 13-я Всероссийская конференция: Сб. докл. М.: МАКС Пресс, 2007. - 10-13 с.

38. Вайнцвайг М.Н. Об ускорении процессов обучения и принятия решений / Математические методы распознавания образов // 13-я Всероссийская конференция: Сб. докл. М.: МАКС Пресс, 2007. - 13- 15с.

39. Гуров СЛ., Потепалов Д.Н., Фатхутдинов Д.Н. Решение задач распознавания с невыполненной гипотезой компактности / Математические методыраспознавания образов // 13-я Всероссийская конференция: Сб. докл. М.: МАКС Пресс, 2007. - 27 - 29с.

40. Зубюк A.B. Алгоритмы идентификации изображений в случайной и нечеткой морфологии / Математические методы распознавания образов // 13-я Всероссийская конференция: Сб. докл. М.: МАКС Пресс, 2007. - 30 - 32с.

41. Капустий Б.Е., Русын Б.П., Таянов В. А. Способы построения оптимальной вероятностной модели систем распознавания / Математические методы распознавания образов // 13-я Всероссийская конференция: Сб. докл. М.: МАКС Пресс, 2007. - 37 - 39с.

42. Неделько В.И. Об эффективности эмпирических функционалов качества решающей функции / Математические методы распознавания образов // 13-я Всероссийская конференция: Сб. докл. М.: МАКС Пресс, 2007. - 47 - 49с.

43. Романов Л.Ю. О согласованных оценках сложности задач и алгоритмов классификации / Математические методы распознавания образов // 13-я Всероссийская конференция: Сб. докл. М.: МАКС Пресс, 2007. - 56 - 59с.

44. Огнев И.В., Сидорова H.A. Реализация системы обработки и распознавания образов в ассоциативной осцилляторной среде / Известия высших учебных заведений. Поволжский регион. 2008. - Спец. вып. 2. - с. 98 - 104. -(Технические науки).

45. Фукунага К. Введение в статистическую теорию распознавания образов.: Пер. с англ. М.: Наука, главная редакция физико-математической литературы, 1979. - 368 с.49 .Дуда Р., Харт П. Распознавание образов и анализ сцен.: Пер. с англ. М.: Мир, 1976.- 507 с.

46. Вагин В.Н., Головина Е.Ю., Загорянская A.A., Фомина М.В. Достоверный и правдоподобный вывод в интеллектуальных системах. / Под ред. В.Н. Вагина, Д.А. Поспелова. М.: Физматлит, 2004. - 704 с.

47. Анисимов Б.В., Курганов В.Д., Злобин В.К. Распознавание и цифровая обработка изображений: Учебное пособие для студентов вузов. М.: Высшаяшкола, 1983. 295 с.

48. Ю.И.Журавлев, В.В.Рязанов. О.В.Сеиько Распознавание. Математические методы. Практические применения. Программная система. М.: ФАЗИС, 2005. - 125 с.

49. Ю.И.Журавлев Распознавание. Классификация. Прогноз. // Академия наук СССР / Отделение информатики, вычислительной техники и оптимизации / Мат. методы и их применение. Выпуск 2. М.: Наука, 1989. - 70 с.

50. У LeCun, L. Bottou, Y. Bengio, and P. Haffner. Gradient-based learning applied to document récognition // Proceedings of the IEEE, 86(1l):2278-2324, November 1998.

51. Нейман Дж. Теория самовоспроизводящихся автоматов: Пер. с англ. -М.: Мир, 1971.-384 с.

52. Кохонен Т. Ассоциативная память: Пер. с англ. М.: Мир, 1980. - 240 с.

53. Борисов В.В., Полячков А.В. Модель многоуровнего сетевого контроллера на основе ассоциативной среды / Сб. науч. тр. № 6 ВУ ВПВО ВС РФ. Смоленск: Изд-во ВУ ВПВО ВС РФ, 2001. - с. 41 - 44.

54. Чжао Цзюньцай, Шарапов А. П. ИССЛЕДОВАНИЕ И РАЗРАБОТКА АЛГОРИТМОВ ЗАПОЛНЕНИЯ ПУСТОТ ДЛЯ ПОСТРОЕНИЯ ТРЕХМЕРНОГО ИЗОБРАЖЕНИЯ ПО СЕЧЕНИЯМ. Вычислительные сети: теория и практика. №1 (10). - 2007

55. Тарасов И. Е. Разработка цифровых устройств на основе ПЛИС XILINX® с применением языка VHDL. М.: Горячая линия - Телеком, 2005. - 252 с.

56. Угрюмое Е.П., Грушвицкий Р.И., Мурсаев А.Х. Проектирование систем на микросхемах с программируемой структурой. 2-е изд., перераб. и доп. -СПб.: БХВ-Петербург, 2006. - 736 с.

57. Рыжиков Ю.И. Работа над диссертацией по техническим наукам. 2-еизд., перераб. и доп. СПб.: БХВ-Петербург, 2007. - 512 с.

58. Глушков В.М. Синтез цифровых автоматов. М.: Физматгиз, 1962. - 476 с.

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

60. Стешенко В.Б. ПЛИС фирмы Altera: проектирование устройств обработки сигналов. М.: ДОДЭКА, 2000. - 128 с.

61. Белое A.B. Создаем устройства на микроконтроллерах. Спб.: Наука и техника, 2007. - 307 с.

62. Бродин В.Б., Калинин A.B. Системы на микроконтроллерах и БИС программируемой логики. М: Издательство ЭКОМ, 2002. - 400 с.

63. Комолое Д.А., Мячьк P.A., Зобенко A.A. Филиппов A.C. Системы автоматизированного проектирования фирмы Altera: MAX+plus II и Quartus 11. М.: ИП Радиософт, 2002. - 352 с.

64. Kleene S.C. Representation of events in nerve sets and finite automata / Гп C.E. Shannon and J. McCarthy editors. Automata studies, Princeton University Press, 1956, pp. 3-41.

65. Бутаев M.M., Вашкевич И.П., Гурии Е.И., Конное H.H. Проектирование цифровых устройств на программируемых логических интегральных схемах. Пенза: Изд-во Пенз. гос. техн. ун-та, 1996. - 65 с.