Введение
Актуальность темы. Развитие вычислительной техники в наше время ведется, в основном, экстенсивными методами: увеличивается частота работы процессора, объем оперативной памяти, размер кэш-памяти, скорость обмена и число процессоров в многопроцессорных системах.
Одним из «узких мест» при повышении производительности ЭВМ классической архитектуры является обмен данными между процессором и оперативной памятью. Тактовая частота работы процессора в несколько раз превосходит частоту работы памяти, и этот разрыв постоянно растет.
Существует несколько путей сокращения разрыва, например, применение кэш-памяти, работающей на частоте процессора, однако, остается неизменным классический принцип обработки информации, заключающийся в последовательном чтении данных из памяти, обработке в центральном процессоре и помещении в память результатов обработки.
Вместе с тем, становится все более очевидным, что возможности современной элементной базы, аппаратных средств и ЭВМ классической архитектуры по производительности и быстродействию приближаются к физическим пределам, выход за которые возможен только при реализации новых идей, как в архитектуре ЭВМ, так и в области аппаратных и программных средств.
Искусственный интеллект, как наука, развивается уже более 30-ти лет, однако качественный скачок в исследованиях произошел в 80-е годы, когда сформировалась новая отрасль индустрии — производство интеллектуальных систем. Имеется обширный класс задач, эффективное решение которых возможно только при использовании интеллектуальных систем. К ним, в первую очередь, относятся: обработка символьной
информации, решение логических задач, в том числе нечеткого логического вывода; работа с базами данных и знаний; распознавание и синтез речи; анализ, обработка и распознавание изображений.
Отличительной особенностью задач искусственного интеллекта является огромный объем данных для обработки. Время обработки этих данных растет с ростом их объема, и зависит от числа обращений к памяти, поэтому одним из важнейших вопросов при разработке интеллектуальных систем является способ доступа к данным и возможность обработки информации без изъятия ее из памяти.
Существуют два основных способа доступа к информации в запоминающих устройствах (ЗУ) ЭВМ: адресный и ассоциативный. При адресном способе искомая информация жестко задана адресом - местом ее расположения в запоминающей среде, и в каждый момент времени возможно обращение только к одной ячейке ЗУ, независимо от информационной емкости ЗУ. Ассоциативный способ основан на установлении некоторого соответствия, ассоциации между хранимой в ЗУ информации и поисковыми аргументами. Запоминающие устройства, в которых использован такой способ доступа, получили название ассоциативных ЗУ (АЗУ).
АЗУ характеризуются двумя основными признаками:
• доступ к хранимой информации в АЗУ осуществляется исходя из ее содержания;
• при каждом обращении к АЗУ возможен одновременный и параллельный доступ ко всей хранящейся информации.
Эти два признака обосновывают свойства «интеллектуальности» АЗУ. Первый из них определяет возможность обработки данных непосредственно в логико-запоминающей среде АЗУ, а второй обеспечивает возможность коллективной обработки информации.
АЗУ, реализующие помимо стандартных операций ассоциативной
обработки информации функции преобразования многомерной информации, называют многокоординатным АЗУ (МКАЗУ) [1]. МКАЗУ являются перспективным направлением в развитии интеллектуальных ЗУ. Они позволяют производить более эффективное, по сравнению с традиционными АЗУ, выполнение локальных и глобальных вычислений, линейных и нелинейных вычислений, интенсивное использование логико-запоминающей среды АЗУ, объекно- и координатно- ориентированных вычислений, символьных вычислений и вычислений на элементах, контекстно свободных и контекстно зависимых вычислений.
Дальнейшее развитие идей, реализованных в МКАЗУ, воплощено в ассоциативных средах (АС), отличительными особенностями которых является возможность обмена информацией между ячейками [2]. АС широко представлены разнообразием форм обмена-информацией, организацией накопителей и ячеек в них .однако, алгоритмы обработки информации, способы их представления и записи исследованы недостаточно. Можно сказать, что число видов и типов АС значительно превосходит число конкретных реализаций алгоритмов и программ для них. Таким образом, существует разрыв между возможностями АС умноженными на число их видов и числом алгоритмов обработки информации. Наличие данного разрыва объясняется в основном отсутствием аппарата, позволяющего описывать алгоритмы и программы для АС, недостаточной проработкой вопроса о месте АС в вычислительной системе и сравнительной новизной самих АС.
Данная работа предназначена для сокращения этого разрыва путем разработки общих направлений и методов обработки информации в ассоциативных средах, разработки алгоритмов обработки информации на примерах базовых алгоритмов обработки изображений и служит дальнейшим развитием работ, проводимых на кафедре Вычислительной Техники Московского Энергетического Института под руководством профессора Огнева И. В.
8
Цель работы состоит в разработке и исследовании новых типов ассоциативных сред, методов и алгоритмов обработки информации на их основе.
Для достижения поставленной цели в диссертации решаются следующие основные задачи:
• разработка концепции построения вычислителя на основе ассоциативной среды;
• разработка и исследование ассоциативных сред для обработки информации методами клеточной логики;
• разработка методов и алгоритмов обработки информации на примере обработки изображений;
• разработка методов и алгоритмов обработки нечеткой информации в АС на примере нечеткого ассоциативного поиска.
Объектом исследований являются многокоординатные ассоциативные среды, средства описания таких сред, а также алгоритмы обработки информации, построенные на их основе.
Методы исследования базируются на теориях арифметических и логических основ вычислительной техники, системного анализа, теории оптимальных ассоциативных преобразований, функционального анализа, математического анализа, методах клеточной логики. Экспериментальные исследования, для подтверждения полученных в ходе диссертационной работы результатов, проводились на основе имитационного моделирования на ЭВМ.
Научная новизна работы заключается в следующем:
• разработаны и исследованы ассоциативные среды нового типа - с локальными связями между ячейками в пределах одного накопителя для обработки информации методами клеточной логики;
• разработан метод конвейерной обработки изображений методами клеточной логики, который реализован на многомерной ассоциативной среде для быстрой потоковой обработки больших объемов данных;
• разработан метод командного управления ассоциативными накопителями, построенный на концепции представления ассоциативной среды, как операционного устройства, для повышения функциональности и гибкости управления ассоциативными ячейками;
• разработаны методики реализации алгоритмов обработки изображений в ассоциативных средах для применения их в задачах распознавания образов;
• разработана методика вычисления коэффициентов разложения в ряд Фурье и Уолша для рализации алгоритмов распознавания изображений, инвариантно к сдвигам в ассоциативных средах;
• разработан и исследован потоково-осцилляторный метод для обработки информации в ассоциативных средах;
• разработаны и исследованы ассоциативные среды с фиксацией в ячейках кода микрооперации для реализации потоково-осцилляторного метода;
• разработаны и исследованы типовые клеточные ансамбли неоднородной клеточной логики для применения их в схемах обработки информации потоково-осцилляторным методом;
• разработаны и исследованы методы представления нечеткой информации и нечеткий ассоциативный поиск в ассоциативных средах.
Практическая ценность.
Работа выполнялась в соответствии с планами Российского фонда фундаментальных исследований и гранта Президента Российской Феде-
10
рации №01-15-99556 ( проект «Ассоциативные системы и среды хранения и обработки информации: теория и прикладные разработки»). Практическая ценность работы состоит в следующем:
• разработана схема ассоциативной ячейки и структурная схема ас-социативнои среды с локальными связями для проектирования и создания СБИС на их основе;
• разработаны схемы ассоциативной среды и схемы ассоциативных ячеек с командным управлением для проектирования и создания СБИС на их основе;
• разработана схема ассоциативной среды с фиксацией кода микрооперации для проектирования и создания СБИС на их основе;
• предложенные схемы, алгоритмы и информационные модели являются основой для построения различных устройств обработки, хра-
#' нения и передачи информации.
Достоверность научных положений, выводов и практических рекомендаций, сформулированных в диссертации, подтверждается вычислительными экспериментами и данными, полученными при имитационном моделировании, апробацией работы в международных и региональных конференциях.
Апробация работы. Основные результаты работы докладывались на: Международном форуме информатизации МФИ-2001 «Информационные средства и технологии» ( Москва 2001 ); Международной конференции «Системы компьютерной математики и их приложения» ( Смо-ленск 2001 ) ; Международной научной конференции «Математические методы в интеллектуальных информационных системах - 2002» ( Смоленск 2002 ).
Публикации. Основные результаты диссертации опубликованы в 5-ти печатных работах.
11
Структура и объем диссертационной работы. Диссертация состоит из введения, четырех глав, заключения, списка литературы из наименований и приложения. Работа содержит страниц текста, рисунков, таблиц,1 страниц библиографии.
Основные научные положения, выносимые на защиту:
• ассоциативные среды с локальными связями для проведения операций клеточной логики;
• метод конвейерных вычислений для реализации операций клеточной логики с использованием ассоциативных сред;
• алгоритмы вычисления коэффициентов разложения в ряд Фурье и Уолша с использованием базовых операций сравнения и сдвига в ассоциативных средах;
• потоково-осцилляторный метод обработки информации в ассоциативных средах;
• ассоциативные среды с фиксацией в ячейках кода микрооперации;
• методы представления информации и клеточные ансамбли для обработки информации в АС потоково-осцилляторным методом.
12
1. Ассоциативные среды для реализации операций
клеточной логики
Возможность обработки информации без изъятия ее из памяти является одним из наиболее важных свойств ассоциативной памяти [2]. Для использования этого свойства необходима методика такой обработки. В данной главе рассматриваются аспекты применения логики клеточных автоматов, как методики обработки информации в ассоциативных средах (АС). В частности, рассматриваются вопросы обработки графической информации, представленной в виде бинарного растра.
Цифровая обработка изображений является быстроразвивающейся областью науки и техники, характеризующаяся многообразием задач по составу, вычислительной мощности, виду и объему исходной информации и результатов, по необходимой скорости и точности вычислений [3]. В настоящее время для решения подобных задач широко применяются персональные ЭВМ (ПЭВМ). Это объясняется следующими причинами:
• процессы обработки видеоинформации не могут быть полностью и однозначно формализированы, поэтому данные процессы являются интерактивными;
• изображение может быть не только объектом изучения, но и выступать в роли универсального интеллектуального интерфейса между человеком и ПЭВМ;
• задачи обработки изображений разнообразны по составу, вычислительной сложности, виду исходной и результирующей информации, по необходимой скорости и точности вычислений, по объему хранимой информации;
13
• надежность и доступность ПЭВМ [4].
Создание персональных систем обработки изображений на базе ассоциативных сред позволяет повысить их производительность при работе со стандартными и вновь создаваемыми пакетами прикладных программ
[3].
В данной главе предложено два аспекта применения АС:
• в качестве устройства предварительной обработки изображений в канале передачи растровой графической информации, работающего в темпе этой передачи;
• в качестве устройства хранения и обработки изображений на этапах классификации и идентификации объектов.
В данной работе предложены и исследованы алгоритмы операций обработки изображений в АС и структуры АС, разработанные для этих алгоритмов. Набор приведенных операций предназначен для предварительной обработки изображений и не включает фазу распознавания.
1.1. Предпосылки выбора логики клеточных автоматов как метода обработки информации в ассоциативных средах
Обработка информации без изъятия из памяти накладывает определенные требования на алгоритм обработки. Будем понимать под термином «обработка», выполнение некоторой функции, переводящей определенную ячейку АС из одного состояния в другое в зависимости от неких аргументов этой функции. При обработке «внутри» значения аргументов тоже могут находится «внутри», т.е. храниться в ячейках памяти. Для вычисления функции обработки необходимо «доставить» аргументы обрабатывающей ячейке памяти, т.е. должны существовать связи, позволяющие получать значения аргументов функции. Если принять во внимание, что в один и тот же момент времени каждой ячейке требуются
14
аргументы для выполнения ее функции, то получается, что для выполнения обработки «внутри» требуется огромное число связей. В общем случае, если ассоциативная память разрабатывается как универсальное устройство, может потребоваться, чтобы каждая ячейка была связана с каждой. Однако, существует целый класс функций, не имеющих таких «аппетитов» на число связей, например логика клеточных автоматов.
Клеточная логика (КЛ) представляет собой алгебру бинарных изображений, заданную на матрицах бинарных чисел [5]. Каждый оператор КЛ реализует некоторую функцию от многих переменных и преобразует некоторый массив данных Д;- в новый массив //+1, значение каждого элемента которого в момент времени ?+1 определяется только значением этого элемента и ближайших его соседей в момент времени t.
В большинстве работ по клеточной логике рассматривается квадратная мозаика со связностью элемента, равной четырем (окрестность фон Неймана), или со связностью, равной восьми (окрестность Мура) [7, 8, 10]. В квадратной мозаике обычно рассматривается матрица клеток 3 х 3 с восьмью связанными элементами. Из общего числа 28 = 256 конфигураций окрестностей можно выделить 51 различный тип конфигураций. Остальные конфигурации получают путем вращения или зеркального отражения выделенных типов конфигураций.
Операции клеточной логики можно рассматривать как подкласс класса операций, известных под названием линейных и нелинейных двумерных пространственных фильтров [6, 3]. Двумерная дискретная система может быть описана как оператор L, отображающий входной массив f(n,m) в выходной массив д(п,т) = L{f(n,m)}, где п и т принимают целочисленные значения. Система называется линейной, если для произвольной константы С справедливо равенство:
, где д\ = L{fl}, д2 = L{f2} [11]. Операцию фильтрации можно записать
15
ОО
ОО
в виде:
f \ V л <ь "Ч I* / 1 1 \ 1 / Т 14 / • * \
У\1Ь) IIIJ — / _, / J l/v, ь I Л IL\ll /v, III — I ) yl. I)
k=-ool=—oo
Импульсная характеристика системы /г(га,т) определяется через единичный импульс U0(n1m) (1.3).
h(n,m) = L{Uo(n,m)},
[/о (га, т) = <
1, если п = 0, m = О,
О, еСЛИ П ф 0,772 ф 0.
(1.2) (1.3)
Поскольку операции клеточной логики представляют собой операции локальной обработки, то функция h(n,m) тождественно равна нулю за пределами некоторой ограниченной области. Соответствующий фильтр называют нерекурсивным, и бесконечные пределы суммирования в (1.1) заменяют конечными. При этом каждый отсчет массива на выходе нерекурсивного фильтра представляет собой взвешенную сумму отсчетов входного массива. В результате операцию клеточной логики можно записать следующим образом:
д(п,т)= ? f(k,l)xh
k,leN(n,m)
kl пт
(1.4)
где N(n,m) - окрестность, в которой h(n,m) Ф 0. Матрица Н = \\h^lrn\\ называется матрицей весовых коэффициентов. Она определяет конкретный вид операции клеточной логики. Например, операции сглаживания и обнаружения краев задаются матрицами:
Я =
1 1 1
1 1 1
1 1 1
16
1 -2 1 Я = _2 4-2
1 -2 1
Таким образом, операции клеточной логики определяются целочисленными коэффициентами [3].
В данной главе предлагается ряд методов, позволяющих ускорить выполнение операций клеточной логики с использованием АС. Для облегчения их описания дадим несколько определений.
1.2. Основные понятия и определения
Одним из главных достоинств АС для обработки информации является совмещение функций хранения и обработки данных в них [2]. Ассоциативная среда в этой концепции является операционным устройством, так как она осуществляет непосредственную обработку данных. Обработка осуществляется под воздействием управляющего автомата, который в соответствии с алгоритмом обработки данных формирует последовательность управляющих сигналов и анализирует состояние сигналов обратной связи, формирующихся в АС.
Элементарное действие, производимое ассоциативной средой под воздействием определенного набора сигналов, будем называть микрооперацией. Время выполнения микрооперации будем называть тактом, в течение которого значение всех управляющих сигналов в АС остается постоянным. Обработка информации в АС связана с изменением состо-яни ассоциативных ячеек и выходных сигналов обратной связи. Будем считать, что подобное изменение происходит по границе тактов. Таким образом, микрооперация характеризуется определенным набором управляющих сигналов, под воздействием которых ассоциативная ячейка (АЯ)
17
производит обработку данных и по окончании такта изменяет свое состояние и формирует набор выходных сигналов.
Множество микроопераций, производимых ассоциативной средой, определяет ее функциональность. Функциональность АС зависит от функциональности ассоциативных ячеек, от связей ячеек друг с другом и с внешней средой, от размерности и конфигурации ассоциативных накопителей.
Последовательность микроопераций, составляющая логически законченное действие над данными, назовем операцией. Операция состоит из одной и более микроопераций, число и порядок следования которых определяется логикой операции. Формат и способ задания операции и операндов в управляющем автомате определяют его интерфейс, который в данной работе затрагивается лишь в отдельных случаях. Основное внимание уделяется операционному автомату, наборам микроопераций и их реализации с помощью ассоциативных сред.
Предлагаемое определение АС как операционного автомата позволяет обозначить ее место в вычислительной системе, описать структурную схему подобной системы, ввести понятия: микрооперация, операция, алгоритм.
Закон изменения состояния одной, отдельно взятой АЯ в зависимости от состояния соседних АЯ будем называть функцией клеточной логики (ФКЛ). Изменение состояний элементов (вычисление ФКЛ) происходит одновременно для всего массива данных [5].
Под операцией клеточной логики (ОКЛ) в АС будем понимать процесс вычисления определенной ФКЛ для всего массива данных. Операндом для вычисления ОКЛ служит ортогональный ассоциативный накопитель, состояние множества ячеек которого образует массив данных.

Получить работу