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

Ульяновский государственный технический университет

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

Гордиан Александр Владимирович

РАЗРАБОТКА И ИССЛЕДОВАНИЕ АЛГОРИТМОВ МОДЕЛИРОВАНИЯ И ОЦЕНИВАНИЯ ПАРАМЕТРОВ МНОГОМЕРНЫХ ИЗОБРАЖЕНИЙ НА БАЗЕ ПАРАЛЛЕЛЬНЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ

Специальность 05.13Л6. «Применение средств вычислительной техники, математического моделирования и математических методов в научных исследованиях»

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

Ульяновск, 1997

Работа выполнена на кафедре «Системы автоматизированного проектирования» Ульяновского государственного технического университета

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

Васильев К.К.

Официальные оппоненты: д.т.н., профессор Соснин П.И.

к.т.н., доцент Соломин Б.А.

Ведущее предприятие: ОАО "Комета" (г.Ульяновск)

Защита состоится «с^ » г&Зслд/Си? \ 997г в -/3 час. На заседании диссертационного Совета К064.21.03 в Ульяновском государственном техническом университете по адресу: 432027, г.Ульяновск, ул. Северный Венец, 32.

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

Автореферат разослан «о^» I

997г.

Ученый секретарь диссертационного Совета

д.т.н., профессор

Крашенинников В.Р.

Общая характеристика работы

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

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

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

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

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

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

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

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

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

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

5. Разработка параллельных алгоритмов фильтрации многомерных изображений.

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

7. Разработка системы моделирования параллельных ВС на базе последовательных ВС общего назначения.

8. Исследование вычислительных характеристик разработанных алгоритмов с помощью системы моделирования параллельных ВС.

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

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

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

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

4. Показано, что применение предложенной методики моделирования параллельных ВС с использованием ВС общего назначения (Windows

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

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

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

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

4. Разработанная программная система моделирования параллельных ВС на персональных компьютерах позволяет разработчикам значительно ускорить и упростить процесс моделирования параллельных алгоритмов.

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

Реализация результатов диссертации. Научные и практические результаты диссертации нашли применение в хоздоговорных НИР «Модели многозональных пространственно-временных сигналов и методов их обработки параллельными вычислительными системами» (грант), НИР «Разработка адаптивных методов и прикладных программ для обработки динамических изображений применительно к задачам медицины и экологического мониторинга» № 170/93 БСТ. НИР «Разработка программного обеспечения для систем контроля радиоаппаратуры» № С-23-УСО-2, НИР «Статистическое моделирование алгоршмов сопровождения объектов» № С25-УСО-2, выполненных при участии автора в Ульяновском государственном техническом университете. Алгоритмы и программы, разработанные в

диссертации, внедрены в НИИРИ (г.Харьков) и в НИЦ «Потенциал» (г.Санкт-Петербург), что подтверждается соответствующими документами о внедрении (Приложение 1).

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

1) Вторая Всероссийская научно-техническая конференция «Распознавание образов и анализ изображений» (г.Ульяновск, 1995);

2) Пятый международный семинар «Распределенная обработка информации» (г.Новосибирск, 1995);

3) Международная научно-техническая конференция «Проблемы промышленных электромеханических систем и перспективы их развития» (г.Ульяновск, 1996);

4) Международная конференция «100-летие начала использования электромагнитных воли для передачи сообщений и зарождения радиотехники» (г.Москва, 1995);

5) Международная научно-техническая конференция «Непрерывно-логические и нейронные сети и модели» (г.Ульяновск, 1995);

6) 50 Всероссийская научно-техническая конференция, посвященная 100-летию изобретения радио (г.Санкт-Петербург, 1996);

7) 51 Всероссийская научно-техническая конференция, посвященная Дню Радио (г.Санкт-Петербург, 1996);

Результаты диссертации докладывались также на конференциях профессорско-преподавательского состава Ульяновского государственного технического университета (1993-1997).

Публикации. По теме диссертации опубликовано 15 печатных работ. Структура и объем работы. Диссертация состоит из введения, четырех глав, заключения, списка использованных источников (105 наименований) и трех приложений. Общий объем диссертационной работы 142 страницы.

Содержание работы

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

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

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

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

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

к = Ь.. (1)

'р

где Т8 - время решения тестовой задачи последовательным алгоритмом; Тр -

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

Проведенный анализ показал следующее.

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

Для ускорения процедуры пространственной линейной фильтрации, основанной на выражении вида свертки, существуют программно-аппаратные

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

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

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

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

Таким образом, необходимо синтезировать на основе последовательных аналогов параллельные алгоритмы, имеющие более высокое быстродействие.

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

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

предыдущими (но развертке) элементами. Для подобных моделей необходимо правило линейного упорядочивания, на основе которого можно сказать, что элемент (.¡сП) предшествует элементу Ху (1еП), где О- п-мерная

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

Подобным условиям отвечает линейная авторегрессионная тензорная модель:

¡ей 1сУ

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

Уравнение (2) описывает алгоритм формирования случайного поля (СП) {X,} в точке }. При этом считаем, что уже существуют значения {Х]_|}, ' еСЗ,

вычисленные или заданные на границах изображения. Поскольку {¡;у} - поле

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

Введем векторные СП х- -(Х1-Х2]-..Х^)Т. Любую каузальную,

допускающую рекуррентные пересчеты область С можно снести к простейшему виду путем подбора соответствующей траектории обхода и пересчета координат. Тогда, выбирая {х^|,1еС} в качестве компонент вектора х^, можно привести уравнение (2) к виду:

*5 = ¿Ак*]-|к + ¿Вк1р-Тк ■ Ы, (3)

к--1 к=1

где Тк = (0..010..0) - единичный вектор к-й координатной оси; Ак, Вк - N х N матрицы, элементами которых являются соответствующие коэффициенты {а^} И {р]}.

Алгоритм, построенный на основе выражения (3), может быть разделен на следующие этапы (без учета операций ввода/вывода):

Этап 1. Вычисление Х^1 = и Х^" для каждого к;

П I П II

Этап 2. Вычисление х^ = ^х^ + Х^к ■

к=1 кМ

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

Т5еч = гпЫ3^ + (2пГМ3 + 2пМ + Ы)1+ « 4пЫ31х/т, (4)

где П - число измерений кадра, N - размер кадра по каждому измерению, \у -время единичной операции умножения, - время единичной операции сложения.

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

Рекуррентный по данным характер алгоритма моделирования обусловливает параллельную реализацию в виде конвейера. Структура конвейерной параллельной ВС моделирования изображений, приведенная на рис.1, представляет собой замкнутую цепочку линейно связанных процессорных блоков (ПБ). На каждом шаге вычислений процессорному блоку передаются результаты моделирования элементов, определенных как «прошлое». С помощью ПБ генерируется группа элементов по алгоритму, описываемому выражением (3), и результаты передаются следующему ПБ и на устройство вывода.

Время моделирования одного кадра, разбитого на N векторов, ВС, содержащей 1_ ПБ, составляет

где Траг - время работы одного Г1Б.

Рис.1

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

Предлагается использовать ПБ параллельно-последовательной архитектуры, общая структура которого показана на ркс.2. Процессорный блок состоит из двух субблоков, выполняющих операции первого и второго этапов соответственно. Субблок 1 представляет собой набор из 2п процессорных элементов (ПЭ). Структура типичного ПЭ показана на рис.3. В его основе лежит использование К спецпроцессоров быстрой свертки. Субблок 2 состоит из К ПЭ. Данный ПЭ построен на базе одного спецпроцессора. Субблоки 1 и 2 работают последовательно. В этом случае общее время работы одного ПБ составляет

Траг=Т'

TII = 2N\

KV

где ts - длительность единичной операции свертки; N/V - отношение длины моделируемого вектора к длине регистра спецпроцессора.

С учетом (5) общее время моделирования одного кадра Т.

раг

2N3ts LKV

пэ

Ап ХН„

ПЭ

х"л

■ X 01

0п

-»х'01

X Ог

ПЭ - процессорный

элемент НБ - накопительный

буфер УВВ - устройство вывода

УВВ

Ж-1п|

X N-10

X N-111

пэ2п к=1 Ех'^-АС к=1

х3 — (х0'х1>х2'--'ХЫ-1}

Рис. 2

а0

СП —

*Х| @ а"о

«1

«N-1

|УВВ

1 Х^Ац^

!с_п

-^Х] ® си

СП - спецпроцессор свертки

Рис. 3

в

Для рассмотренной параллельной ВС коэффициент ускорения вычислений составляет

Т5еЯ + )

к =

Траг

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

Строго оптимальное по критерию минимума дисперсии ошибки решение задачи оценивания двумерного изображения известно В этом случае задача фильтрации изображения приводится к задаче рекуррентной калмановской фильтрации многомерной случайной последовательности. При этом класс оцениваемых изображений ограничивается полями, описываемыми стохастическим разностным уравнением вида (2). (3), и принимается аддитивная модель наблюдений.

Алгоритм тензорной калмановской фильтрации описывается выражением, х/ - РХ]*"1 + РП'(Уо15<Г1(25' - р^1-1), (6)

где X- оценка элемента X ; - результат наблюдения элемента; Р^', и

\Zfjj1 - известные тензоры ранга 2(1 с групповыми индексами ¿Д.Б^еС; I -

индекс, по которому производится рекуррентный пересчет, р - коэффициент корреляции.

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

Т8еч=(ЗМп + 2М?п)1х/+,

где I- время выполнения элементарной операции.

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

Перепишем (6) с учетом правил тензорного умножения: N1-1

{|>=0

где Хз-' Л^-г,4 — рХу4-1; - элементы тензора

Многомерная свертка путем пересчета координат элементов преобразуется в одномерную:

Э

У

где Л д1 - преобразованные операнды, Б - N° -1.

Окончательно к процедуре свертки приводим (7) внесением под знак суммы операнда Хэ-(. Для этого необходимо дополнить множество единичным

элементом, г Д^1 элементом хэ|1. Тогда выражение (7) принимает вид: в = 0

где ДЁ* - расширенные векторы Л^1.

Таким образом, алгоритм тензорной калмановской фильтрации (8) включает п себя следующие операции

1) вычисление операнда Р-|' на этане подготовки,

2) вычисление прогноза {х = {рх-'~1},

^ }

3) вычисление операнда {А]'} - {гу* - Хэу4-1} и приведение его к виду {Д^^Л^Хз]1};

4) оценка каждого элемента текущего кадра по формуле (8)

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

Рис.4

Наиболее трудоемкими в вычислительном плане являются операции четвертого этапа (ПЭЗ). При использовании в составе ПЭЗ К спецпроцессоров

свертки время выполнения этапа составляет Т

IV

П/мП-1

N (N

1)ts

К

, где ts - время

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

Общее время обработки одного п-мерного кадра последовательности определяегея соотно шеи нем.

Т Т 'par * 1

.v Nn(Nn~1 -1)

К

Tseq 2LK(Vtx/J

U

'par ls

где L - число ПБ в составе ВС (рис.1), V - длина регистра спецпроцессора свертки, К - число спецпроцессоров свертки в составе ПЭЗ

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

И)

Третий раздел «Параллельная вычислительная система обработки изображений» посвящен синтезу аппаратного обеспечения параллельной ВС обработки изображений

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

Зачастую с помощью спецпроцессора реализуется алгоритм вычисления свертки по разрядным срезам изображения В этом случае выражение для свсргки можно записать в виде: М-1(Э-1(3-1

*■= X I 128гЬ8ч2ЧНГ,

5-0г=0я=0

где О - число разрядов при цифровом представлении данных, г5Г - значение Г-го

разряда числа с номером Б в исходной последовательности, - значение Ч-го

разряда числа с номером Б в массиве весовых коэффициентов Перешпием последнее выражение следующим образом: (3-1(1-1

Х|= I Х2Чг2ч+г, (9)

г-0р=0

М-1

Зсг=1>5г115ч (10)

й-о

2

Процедура свертки сводится к выполнению О тривиальных сверток (10) последовательностей М одноразрядных данных и выполнению результирующей свертки (9) Процесс вычисления свертки в данном случае можно представить

о

следующим образом О тривиальных сверток вида (10) выполняются

одновременно, результаты их затем суммируются с учетом коэффициентов

Достоинством выражения (10) является отсутствие нетривиальных умножении Вместе с тем процедура суммирования по индексу Б результатов произведений не является тривиальной. Процедура логического суммирования предполагает

образование переносов, и на каждом шаге разрядность промежуточных результатов возрастает Применение древовидной сети сумматоров позволяет снизить число шагов вычислений до 1од2 М . С учетом возрастания разрядности данных на каждом шаге вычислений общее время свертки составит:

ТЕ = Т2(10)+Т£<9> = (1,51од22 М)1|+(1од2а2)1+, где - время выполнения элементарной логической операции; 1+ - время суммирования авух 1од2 М -разрядных чисел.

Предлагается заменить операцию суммирования последовательности однобитных данных операцией пересчета числа значащих разрядов в последовательности. Для этой цели используется операция быстрой параллельной сортировки двоичных данных. Результатом сортировки является упорядоченная последовательность, такая, что для множества а - {а0 ,а-| ,а2,...,а^_1} существует индекс к (0<к<М-1), разделяющий его на два подмножества а0 = {а0,а1,а2,--ак} и э1 ={ак+1,а|(+2,...,ац11_1}, содержащие единичные и нулевые элементы соответственно. Индекс к последнего значащего элемента представляет собой искомую сумму в заполняющем коде. В связи с этим после процедуры сортировки необходимо произвести шифрацию результата в двоично-десятичный код

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

п Т 1од2 М(Юд2 М + 1)

Процедура сортировки производится за время. Т3 =---1|;

процедура параллельной шифрации. Тш = 31| и не зависит от размера последовательности

С учетом этого коэффициент ускорения вычисления свертки (10) составляет

тэ ' Тш Т5

Общее время свертки последовательности М О-разрядных элементов с помощью описанного алгоритма составляет:

Т5ог^Тх +т5+Тш+Тг<9).

1од2 !У1(1од? IV! + I) Т5оП = ^-=-^—■—' 31, + Т£|.

о

Описанная процедура эффективна, если м»сг при условии, что свертки

2

вила (10) будут выполнены за время значительно меньшее, чем время свертки О результатов (Тд^"^ «Т^®'), можно считать, что свертка большой последовательности сводится к свертке последовательности меньшей длины.

Проведено моделирование предлагаемого алгоритма вычисления свертки с помощью пакета программ РСАО и сравнительный анализ предлагаемого и известных алгоритмов вычисления свертки. На рис.5, показан график зависимости числа операций п, необходимых параллельному алгоритму, от размера последовательности М (при 0 = 8). Штриховой линией показана аналогичная зависимость для алгоритма, основанного на применении древовидного сумматора. Как видно, выигрыш предлагаемого алгоритма составляет 50%-100% для различной длины последовательности при аналогичных аппаратурных затратах и может достигать 200%. Анализ показывает, что на настоящем этапе развития микроэлектроники возможна реализация в виде программно-аппаратная реализация

„10 112

процедур свертки размерностью до I ...I элементов.

м

3000 т

I

2500 ■

1000 |

500 |

О 5 10 15 20 25 30 35

Рис.5

1од2 М

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

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

Четвертый раздел «Моделирование параллельных вычислительных систем обработки изображений». В разделе производится описание разработанной системы моделирования параллельных ВС (СМПС) и моделирование с ее помощью предложенных параллельных алгоритмов.

Концептуальной основой СМПС является абстрактная модель языка OCCAM. В соответствии с этой моделью параллельная ВС описывается набором конкурентных процессов, взаимодействующих между собой через каналы. Каждый процесс располагает локальным ОЗУ и имеет доступ к глобальному ОЗУ.

Проведенный анализ показал, что требованию минимальной стоимости при приемлемом быстродействии отвечает применение в качестве программно-аппаратной базы СМПС Intel-совместимого персонального компьютера и операционной среды Windows В основе программной реализации СМПС лежит принцип псевдопараллельного выполнения задач в режиме разделения времени процессора. СМПС позволяет использовать для разработки параллельных программ компилятор, совместимый со стандартом ANSI, что делает разрабатываемые программы е высокой степени переносимыми.

СМПС обеспечивает выполнение следующих требований:

1) имитируется работа ВС, состоящей из произвольного числа процессорных элементов, скоммутированных произвольным образом,

2) обеспечивается гибкое управление и защита памяти, разделенной на локальное ОЗУ каждого ПО и глобальное ОЗУ, доступное всем ПЭ;

3) предоставляется программное обеспечение разработки параллельных программ,

4) предоставляются программные средства исследования эффективности разработанных программ,

5) обеспечивается переносимость разрабатываемых программ на моделируемую ВС с минимальными перс-работками.

СМПС имеет следующие вычислительные характеристики

1) объем ОЗУ для моделирования одного ПЭ - 1Мб,

2) число моделируемых каналов связи - не более 216 для каждого ПЭ;

3) объем локального ОЗУ - не более 640Кб для каждого ПЭ;

4) объем глобального ОЗУ параллельной ВС - ограничено объемом свободной дисковой памяти ПК.

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

В процессе моделирования работы параллельной ВС средствами СМПС измеряются следующие основные характеристики

1) время выполнения расчетов на каждом ПЭ,

2) время простоя каждого ПЭ в ожидании сеанса связи;

3) количество байт информации, переданных по каналам связи каждым ПЭ,

4) количество операций свертки, произведенных каждым ПЭ.

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

Заключение

В диссертационной работе на основе теоретических и экспериментальных исследований найдены и проанализированы параллельные алгоритмы моделирования и фильтрации многомерных изображений, а также разработаны структуры параллельных ВС, предназначенных для их реализации. Основные результаты диссертации заключаются в следующем: 1. Синтезирован параллельный алгоритм моделирования многомерных изображений с использованием каузальных моделей. Использование алгоритма позволяет ускорить процесс моделирования многомерных кадров изображения в 2п + 1 раз относительно последовательного аналога, где п - число измерений кадра При этом программно-аппаратная реализация алгоритма предполагает использование 2|1 + 1 ПЭ. Значительное увеличение производительности

обеспечивает применение в составе ПЭ специализированного процессора быстрой свертки В этом случае рост производительности определяется отношением времени выполнения свертки процессором общего назначения ко времени выполнения подобной операции спецпроцессором

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

процессоров свертки. Максимальную производительность, равную logy Nn

log У Nn

операций свертки, обеспечивает применение ^Г i спецпроцессоров, где V -

i=1

длина регистра спецпроцессора, N - длина стороны кадра, П - размерность кадра.

3. Разработан и исследован параллельный алгоритм быстрого вычисления больших сверток В его основе лежит модификация известного принципа параллельной обработки разрядных срезов изображения с использованием алгоритма параллельной бимонотонной сортировки. Исследования алгоритма показали, что по быстродействию алгоритм превосходит аналога па 50-200% (в зависимости от длины сворачиваемой последовательности) при одинаковых аппаратурных затратах. При этом выигрыш в производительности относительно других алгоритмов свертки возрастает при увеличении размерности свертки

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

5 Разработана система моделирования параллельных ВС на базе Intel-совместимого персонального компьютера Система моделирования использует возможность параллельного выполнения нескольких программ в режиме разделения времени центрального процессора, предоставляемую операционными средами семейства Windows Система позволяет моделировать параллельные ВС произвольной архитектуры, содержащей множество взаимосвязанных процессорных элементов Число моделируемых ПЭ ограничено объемом доступного ОЗУ, а скорость моделирования определяется быстродействием центрального процессора

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

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

Основные положения диссертации опубликованы в работах: 1. Васильев К.К., Гордиан A.B. Конвейерный алгоритм фильтрации последовательности изображений // Тез.докл междунар. н/т коиф. «Непрерывно-логические и нейронные сети и модели», Т 3 -Ульяновск: УлГТУ, 1995, с 17-18. 2 Васильев К.К., Гордиан A.B. Оптимальные рекуррентные алгоритмы оценивания случайных полей на фоне помех // Тез. докл. 50 н/т конф., поев. 100-летию изобретения радио -С.-Петербург: СПбНТОРЭС им.A.C.Попова, 1996, с. 14.

3. Васильев К.К., Горднан A.B. Параллельная реализация алгоритмов фильтрации многомерных изображений // Тез. докл. междунар. н/т конф. «100-летие начала использования электромагнитных волн для передачи сообщений и зарождения радиотехники». -М. РНТОРЭС, 1995, с. 149

4. Васильев К.К., Гордиан AB. Параллельная реализация алгоритмов фильтрации последовательностей изображений // Распределенная обработка информации: Тр /Пятый международный семинар. - Новосибирск: ИФП, 1995, с.267-272.

5. Васильев К.К., Гордиан AB. Параллельные алгоритмы обработки изображений // Тез. докл. 51 н/т конф., поев. Дню радио. -С-Петербург. СПб 1ГГОРЭС им.АС Попова, 1996, с.13.

6. Гордиан А В Метод моделирования отжига в задаче планирования топологии транспьютерных сетей // Тез.докл. междунар н/т конф. «Непрерывно-логические и нейронные сети и модели», Т.З. -Ульяновск УлГТУ, 1995, с.27-28.

7. Гордиан A.B. Параллельная реализация алгоритмов оценивания многомерных изображений на базе транспьютерных систем // Методы обработки сигналов и полей' Сб иауч тр. - Ульяновск УлГТУ, 1995, с 84-95

8. 1 ордиан A.B. Параллельная реализация алгоритмов спектрального анализа изображений // Тез.докл. 2-й Всерос конф РОАИ-2-95. - Ульяновск- УлГТУ, 1995, ч 4, с.73-75

9. Горднан А.В Параллельные вычислительные системы в обработке изображений // Тез. докл. 51 н/т конф., поев Дню радио -С.-Петербург. СПб НТОРЭС им.А С.Попова, 1996, с. 14.

Ю.Гордиан А.В. Реализация алгоритмов цифровой фильтрации изображений в режиме реального времени // Тез.докл 2-й Всерос. конф. РОАИ-2-95. - Ульяновск: УлГТУ, 1995, ч.4. с.76-78.

11 Гордиан А В. Транспьютерные системы в обработке изображений // Тез.докл. внутривуз. научно-метод. конф. - Ульяновск: УлГТУ, 1994, с.14-15. 12.Горднан А В . Гордиан К В. Моделирование нейронных сетей на транспьютерных системах применительно к обработке изображений // Тез.докл. н/т конф. «Непрерывно-логические и нейронные сети и модели», Т.З. -Ульяновск: УлГТУ, 1995, с.29-30.

13 Гордиан А В., Яровиков О.С. Применение параллельных вычислений в системах управления /7 Тез докл. междунар н/т конф. "Проблемы промышленных электромеханических систем и перспективы их развития" - Ульяновск: УлГТУ, 1996, ч. 1, с.22-23

!4.Gordian A.V. Implementation of Algorithms of Real-Time Digital Image Filtration // Pattern Recognition and Image Analysis, Vol.6, No.2, 1996, pp.376-377. 15 Gordian A.V. Parallel Implementation of Algorithms for Spectral Analysis of Images // Pattern Recognition and Image Analysis, Vol 6, No.2, 1996, pp.375-376.