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

шскоеекий государственный институт .электронной те-згск:

' (теэдпесюй уюеерситет}

РГБ ОД

-5 ДЕН

¡Уад На правах .'рукописи

Экз.М

УДК.661.3.053:528.721

ПОНОМАРЕВ

ДШТРИЙ АЛЕКСЕЕВ!« ^^^

Раеработка алгоритмов цифровой обработки сигналов для программного обеспечения многопроцессорных систем

05.13.Ql - управление в технических системах-

Автореферат диссертации на соискание ученой степени кандидата технических наук

Москва 199-1

Работа выполнена в Московском Государственном институте электронной техники (Техишг-ский Университет),

Научный руководитель - доктор ф-м. наук ■''-.;

/профессор Ефимов A.B.

Официальные оппоненты .,

- доктор технич. наук

. Широ Г.Э.

- кандидат теннич.наук

' ; Кочнев А.О. /

Ведуад организация : . HIß!" Научный Центр "

, Защита состоится " " " 199-i на . заседании

специаливпрсванного совета Д053.02.0.1 Московского Государственного иетститута электронной тбхники(Моск2а, 103428, МГИЗТ) . ■-■•;•

С диссертацией мунно: ознакомится. в библиотеке .МГИЭТ..

Автореферат раьоолйи. " . ". " 1ЭЭ4Г. Ученый* секретарь- .•'■'■."'■

fcnatvjajaiSKpobSHKaro совбта.:'.. t к.т.н. профессор L /.Н.В.БорсСьвв

Введение

Актуальность проблемы.. В связи с-бурным развитием вычислительной техники точных технологии, необходимостью обработки -больших числовых массивов , • .значительно.аоерос интерес к проблема».! обработки цифровой янферцЭДт.' 0 этой целью создаются системы обработки изображений,которые -используют для решения "айьх задач ,как: распознавание образов, обнаружения цели .медицинскогодиагноза,анализа различных. биомедицинских сигналов изображений, опознавание на расстоянии, идентификация человеческих лиц к отпечатков пальцев,обработка аэрофотоснимков и т.п. % Особый интерес- к таким системам возник в связи с развитием персональных ЭВМ, увеличения их,быстродействия и сбьема -памяти и -сшие'ния • рхрпмоспг что и послужило основной• прхгкшой.создан;« на' их базе систем обработки изображения. Для систем работавши в .'реальном '.масштабе времени особенно важны .таю» характеристики, как сбьем памяти:и быстродействие вычислительной среды. Термин "реальный масштаб времени" в зависимости от решаемых- задач обработки. изображений понимается по разис-иу. ' Скажем, если, такая'система установлена на произЕсдстЕеннсм «знвёйере.то-здесь реальный масштаб :-времени." ассоциируется :о" скоростью движения данного конвейера. Однако-если- брать »едовеч'еския глаз , то'реальный масштаб■времени будет равен 24'" кадрам в секунду. Если задачи конвейера-уже более,«ли <енее решаются в настоящий момент,то задачи человеческого ■лаза в основном рассматриваются -в перспективе, так как для шх • необходим - качественный скачок в развитии -.те'хнолспэт фоизводстБЭ'ЩС, что должно увеличить '• быстродействие' не-', на >диницы ,а на-несколько порядков. ■■ Поэтому .'задачу 'обработки : 180бражений в реальном масштабе: времени. Я на:тоящщ момент гытаютоя решать в двух.направлениях:::

- аппаратная реализация .алгоритмов обработка изображений..

- использование параллельных -л-чйслителышк процессоров. ••

4 л '

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

Параллельный процессор '.если -рассматривать . грубо, состоит из процессорных элементов и блока управления. Дсбой на параллельних, процессоров имеет как правила некоторую архитектуру. Архитектура параллельного процессора.определяется лрамиами связи между соответствующими процессорными элементами ., а такие правилами поступления данных в процессорные элементы иввне.Процессорные элементу с системой коммуникации :. образуют параллельную среду вычислений .которая подразделяется на однородную и неоднородную. Если процессорные элементы .входяище в состав параллельного процессора, имеют одинаковую структуру и мощность , то соот-ьествуюад параллельная среда является однородной и неоднородной е противном случае.' Обилие архитектур говорит само эа себя о ''сложности программирования , а также • об отсутствии универсальности. /• Поэтому для.решения определение. гадач обработки игоСраженка' подбирается оптимальным образом Определенная -архитектура. Следовательно , более универсальный вариант для систем обработки йесбраженил Судет находиться в гибридных архитектура?.. Однако вв^зду сложности и, соотьетсвенно,,.-'больше, материальных еатратах , о .такой архитектуре, .приходится ■¿¡па./мечтать. Данную же проблему" пи-■ таьтсл реанть пока путем создания уникальных архитектур ,' таких как: систолическая, матричная, нейронная, гиперкуб и т.п. ..;';., ?.'■/ '■.:: ' ' ■:.

В дакяой диссертационной работе рассматривается система обработки изсбрахений с архитектурой гипвркубз с однородной параллельной вычислительной средой .ЕыСор такой архитектуры был сделан исходя из следувзпх соображений: в отличи- от матричной и систолической , архитектура гиперкуба имев?' больше связей ,что позволяет перестраивать' архитектуру з процессе решения задач обработки изображений. Дале* путем пересилю! данных можно олучить матричную, сферическую, то-рообразную иерархичную структуру. Однородная-вычислительная среда была выбрана в силу специфики данных о1»!$реванных изображений,- которые обрабатываются в системе. Кроме того, гиперкуб более изучен теорией градов ,что позволяет использовать ее потенциал!ные возможности в _ программировании.Обрабатывая данные >• которыми в частности являются цифровые изображения, на любом параллельном процессоре приходится решать,по крайней мере дге категории задач: так.зто задачи "транспорта",т.е. пересылки данных между процессорными элементами, ' и задачи распараллеливания алгоритмов обработки этих данных.Обе зти задачи взаимосвязаны ««жду собой , та:« как имеют общую цель: наиболее, эффективно использовать ей-" ■ числительные'ресурсы , а следовательно , и увеличить быстродействие всей системы обработки изображении.

Цель работы. Настояедя робота посвящена■вопросам разработки алгоритмов для 'программного обеспечения систем обработки цифровых изображений на базе вычислительной системы параллельной обработки (ЕСШ), параллельный процессор которой имеет архитектуру гиперкуба., .

В свази с этим в работе проводятся следукдпе- исследования:

• 1)Дается анализ « оценка систем обработки изображений с точки зрения их программного: обеспечения. С этой целью рассмотрены аспекты, кзсаоздеся выбора языков-прсграмкиро- -вания, представления данных, об изображении, режимов работ, взаимодействия с . аппаратный« средствами).: -яольгсЕат-аен и анализируются функций обработки 'цифровых изображений в су-'¡цествущих соогветствукиак ВГОО . '-■

' -.6;

•' 2). '.классифицируются системы обработки' иас£ра*«ний на

основе параллельных вычислительных средств с SIMP, MIMÖ и . конвейерными архитектурами,.

. 4} разрабатывается и вводятся определения идеального QA> и реального QR„-,мерного пространства гиперкуба .учитывавшие правилами соседства ПЗ в . параллельном процессоре. Используя 'определенную теорией графов вершинную связность мы определяем связность изображении.

S разрабатывается и оптимизируется алгоритм для получения ллачарной карты загрузки элементов цифровых изображений •.в локальною память соответствующих ПЭ ЕСЛО "ПАРС", имеющей •• QR^-мерное пространство гивёркуба.

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

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

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

.1). метод создания в QJ*-мерномпространстве гипер-. куба тривиальных плоскостей (тор, сфера, плоскость).необходимых при рещекии задач при решении задач обработки изображений £ ЕСПО с архитектурой гиперкуба. ...

•:. 2)-оригинальный метод 'создания, карт''загрузки,-Позволявши: решать задачи транспорта для алгоритмов обработки изоб- . ; ражеюяг ,испсжз-дапх'. в- качестве -'данных кексторую скрест- ■ ность-'.--Проведена оптимизация данных карт загрузи! ка пред: мет. -ишкмалыаж временных затрат.

3).разра0отана методика распараллеливания алгоритмов об- v; : ;райоткя-цифровых, изображений, вкаочавдзя обобщенную схему -распараллеливания, алгоритмов, спирающаяся на алгоритш создания карт'загрузки,-.

' Практическая ценность' результатов проведенных исследований. аакличзет.ся.': в разработке; .' алгоритмов создания опти-

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

Реализация и внедре-':е' результатов исследований. Теори-тические и практические результаты диссерташ:онной работы использованы при проведении двух хоздоговорных научно-исследовательски::, работ ,( с номерами государственной регистрации 0:830080834,01840037373.)

Результаты опробованы на эммуляторе реального пространства гиперкуба на 1ВМ РС'\ХТ.

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

-всесоюзная конференция " Микропроцессоры-35 ", г.Москва 1985,

- научно-техническая конференция "Проблемы создания систем, анализа и понимания изсбр&жений ".Ташкент 1991.

.Публикации', ¡.¡атерналь! по теме диссертационной работы опубликованы в 4-х статьях, отчетах по НИР,

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

' - 5 - : СОДЕРЖАНИЕ РАБОТЫ

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

■ В пергой глаге диссертационной работы анализируется га- . дача обработки .к&сбраженйй для соответствующих систем., Вводится терминология параллельных вычислений. Даются характеристики и классификация систем параллельной обработки. Определится требования к соответствую^ .программным' продук- ; та.;. Термин обработка: изображений включает обычно расповна-ваниё образов-, кодирована*, и непосредственную обработку, как правило, двумерного': изображения. ■ .

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

■ Обработку 'изображений можно -подразделить на 4 части

- на корревдк геометрических искрений (ёгЛайсеибГЛ. );'•-.'

- улучренпе 'визуального 'качества (гесШ'ЮаНс-п); . ' '--.' восстановление ■ (гезЬсгаНоп);

- реконструкцж .(гесспаи исисг.). .

. Е система", обработки' ; ивсбралекий обдего назначения копольауитсл рагнообрагиые методы обработки. 'При решении одной коккреткой задачи,- • например восстановления игображе- .' нкя," приходится •.привлекать'"многие кг них.

Это, объясняется .следующие:-факторами ;': ■ . - изображение,.которое' требуется восстановить, несбхо- ' .''двмо, предварительно ' проа}[аД1:гировать для-' определения ' соот- -.

- 9 -

ветствующих параметров восстановления;

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

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

Возможны различные способы такого разделения. Например, программы можно разделить по,их функциям ( восстановление,' улучаение визуального качества, геометрическая коррекция и т.д.), по типу обрабатываемого иогС-ражешм (с микроскопа, с систем №33, "СНСйТ","Ландсзт"), по чи-лу бит кз один элемент входного изображения и по языку програмиирсвя-ния.

Также существует классификация алгоритмов с учетом аппаратуры и размерностей С81:

1. Алгоритмы, реализуемые о помощи спещвдигнрз&акпсй аппаратуры.

2. Эффективные алгоритмы обработки изображений больгаа размеров.

3. Алгоритмы обработки трехмерных изображений.

4. Алгоритмы, разработанные на основе вычислитель к;й геометрии.

В заЕиоимости от обгектоз и целей обработки шг-бря*.* • нии, как уже выве упоминаюсь, 'выбирается и еозтветгтг-л яи? методы , процедуры обработки изображении.

Можно выделить основные этапы обработки изображений: . 1. Ввод информации. Евод в ЗЕМ цифровых дя..ных, пел-/- * ченных в результате оцифровки точек -изображен"!'!.

2. Предварительная обработка изображении. Исключение шумов и размытости изображений. Коррекция пскаленкй внеси

шх. системой передачи изображений.. Нормализация изображений.

3. Еыделение информативных признаков. Выделение основных информационных признаков изображения, например, выделение характерных графиков или линий границ, разбиение изображения на области, формирование линейчатого графического изображения, '..-"'•.■

4. Измерение 'квантования. Численное представление информативных признаков изображения,-:

5. Распознавание образов и восстановление изображения. Разделение.изображений на классы . (имеется ввиду кластерный анализ). Еосстановдение содержания изображений и их описание.-

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

•Алгоритмы задач, -решаемых в вычислительных системах па- , р&лдельной обработки представляются в виде .набора последовательных процессов,некоторые из которых могут быть. распараллелены. Поэтому в терминологии'параллельных вычислений присутствует к некоторые :слределекгм из.последовательной' обработки., без которых »однако, трудно представить -парал-дельные вычисления

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

. Каедуинезависимую ветвь, задачи называют процессом. . Некоторая.' независимая.'часть одного дмбс-го процесса называется/ секцией прогршш.

- il -

Теп», ь дадим описание вычислительной среды параллельного процессора. Для удобного представления данного'пространства введем понятия идеального и реального гиперкуба. 'Идеальный гиперкуб реализовать достаточно слодно ввиду большого количества связей, тем не менее разработчики смогли реализовать БСПО с архитектурой гиперкуба, частично удалив при этом некоторые связи.сохратт его подобие . .

Пространством или . ■вн"иалительиым пространством п-мерного идеального гиперкуба назовем вычислительную среду параллельного процессора с архитектурой . мерного куба .вершинами которого являются процессорны!; элементы- (ГО).

В результате для того,чтобы упроиеино представить вычислительную среду Ш с архитектуре» гиперкуба, достаточно вспомнить описанный ранее Qw-меркый куб (см.рис.3 )

1-1

а)'

Рис.3 Оп-меркый куб а) двумерный куб 6} Зх-мерный куб б) 4х-мерный куб Таким,образом можно распространить теоремы теорий графов на п-мерное. идеальное простргшстзо гипергуба. Для этого постараемся дать .определение прсстран'гтггз гиперкуба. .' Идеальным пространством гиперкуба назовем шедезхео ПЭ, обгедпненных между- собой в С^-керны:'; куб. Кдеазьное'• пространство гиперкуба будем обозначать Тогда .соответственно, граф .СУ* - называется п-мерным' идеаяьккм прост-

. - 12 -

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

Две вершины ф^-ыерного идеального пространства гиперкуба емелны,тогда и только тогда, когда их уникальные двоичные вдр^са различаются в- одной разряде согласно кода Грея. ОЯ -мерное реальное пространство гиперкуба (ОКу) будет отличаться от графа СЦц, как отличалось еш>$, отсутствием некоторых связей,

Граф ¡У?*- назовем п-мерным реальным пространством гиперкуб;., если он имеет ьервин или Ю, каждая из которых имеет се ой уникальны'" здрес. Для определения смежности вершин или ПЭ графа необходимо вгести понятия локального и глобального адреса . Таким оСравои, пусть, уникальный адрес вершина грг4а . пространства гиперкуба содержит в себе локальную и глобальную сост&вдясаую. Так как наза реальная БСПО имеет минимум 4х-мерную структуру гиперкуба,то мы будем в дальнейшем рассматривать граф С^-мерного реального пространства' для п>=4.

Пусть К младиим разрядам -мерного реального пространства гиперкуба,где п>«к , будут отвечать за лекальную составляй^"», тогда остальные (п-к) разрядов соответственно о& гвебааьную составляющую адреса.

Две вершины графа где п>»к, имеюви* един и тот же • глобальный адрес, смежны если их двоичное ек&чекпе локадь-пл и «дрвса отлкчастса с одно:.', разряде, что аналогично графу 03г> - идеального пространства гиперкуба. Тогда как глобальные составляющи* адресов имевт некоторые отличия (БСПО"ПАРСи к»4).

Быделнм'ь блоки 'вергашы графа 0,!т. имевшие одинаковый глобальный, адрес и обозначим их II, где 1»0,1,Е...(п-к) номер блока, соответствующий глобальней составляющей вершины графа

Два-блока в графе С^-мерного реального пространства гиперкуба смежны если их значения двоичных-адресов.отличается

в одном разряде, что соответствует коду Грея.

Причем, все смежные блоки 11, где 1-0,1...(п-к) соединены в ОЯп-мерном пространстве гиперкуба двумя связями, образуя таким образом псевдограф.

Рис.4 Псевдогриф блоков 21, а) 1-3 б) 1-4 .

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

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

Две вершины .псевдографа Срп-мерного реального пространства гиперкуба смежны, если значение двоичных адресов соответствующих ПЭ отличны в одном 1-м разряде глобального адреса, а локальные адреса равны между собой и равны (1*2) и (1*2+1).

Таким образом, введенными правилами определен порядок построения и ЦК мерных пространств гиперкуба.

Следует отметить также, что для графа ОХ,-мерного идеального пространства,гиперкуба верны топологические инварианты £}ч-мерного куба, тогда как для мерного реального пространства гиперкуба инварианты С^-мерного куба сохраняются в

б

О

1

б"

- 14 -

пределах локальней адресации. '

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

Гак в процессе вычисления алгоритмов обработки цифровьи изображений требуются, некоторый его фрагмент. Что приводи! к задаче восполнения данных. Данную задачу можно решить пс крайней мере двумя путями: во-первых, восполнения недостающих данных ва счет дублирования ряда элементов в ОЗУ данного ПЗ при загруек элементов изображений; .во-вторых, восполнения недостающие данных, за счет решения, так называемых, вадач "транспортизации" элементов цифровых изображений внутри вычислительной среды ЕСП0"ПАРС". Реально, достаточно сложно осуществить задачу "транспорта" в реальной ВСПО с архитектурой гиперкуба без оптимального размещения элементов цифровых изображений в памяти каждого-.. ПЭ, БСЛО'ШРС" является 21М0 машиной, значит все ПО выполняют одновременно одну и ту же операцию.Используя аппарат блокировок, конечно может быть решена задача "транспорта", но временные затраты при этом будут значительны, что, недопустимо. Поэтому и возникает задача оптимального размещения элементов цифровых изображений в памяти ГО ВОПО"КАРС".

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

Назовем картон загрузки элементов цифровых изображений в память ПЭ БСПО"ПАРС"-матрицу1 котсрая ставит в однозначное соответствие каждом/ элементу цифрового изображения адрес процессорного-'элемента ЕСПО"ПАРО".

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

обработки, окажутся в строго определенном соседстве в вычислительно» среде гиперкуба, .что облегчит и ускорит решение задачи воа лнения данных, а следовательно повысит эффективность вычислительного процесса параллельного процессора. Поэтому ¿1меет смысл разбить алгоритмы обработки цифровых изображений на группы по признаку размещения элементов изображений. Хотя меже', получиться, что многие такие группы представляют по одному алгоритму со своей оригинальной картой загрузки. Остановимся на трех группах:

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

2. Унитарные преобразования (Фурье, Адамара, Мультипликативные) ,

3. Получение.некоторых характеристик для классов изображения.

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

Для второй и третьей группы нельзя сказать однозначно, что необходимо соседство соответствующих ГО, так как потребуется некоторый диагональный, доступ, что Позволяет осуществлять архитектура гиперкуба. Могут также и потребоваться .некоторые циклические перемещения элементов цифровых изображений внутри блоков ¿1, а также в пределах глобального гиперкуба. ■

При решении; задач кластеризации необходшо, гобы соответствующая карта загрузки обеспечивала быстр1 "1 поиск соответствующих классов, а также возможности создания некоторой

>■ le -

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

а), размещением элементов цифрового изображения;

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

в) способом дублирования элементов цифрового изображения в памяти КЗ гиперкуба;

г) поиском конкретного ресекия задачи "транспорта" разного рода (циклические сдвиги, передачи соседних элементов и т.п.).

Таким образом, наша задача оптимизации может быть представлена в виде функции, зависящей от, ряда вышеперечисленных параметров. VR( R, Р, D, F).->t, Ыегп min,которую можно оптимизировать в зависимости от необходимого конечного результата, по увеличению быстродействия, по затратам памяти или двум параметрам одновременно.

Следовательно,задача оптимального размещения элементов цифрового изображения в памяти ПЗ БСПО оптимизирована с точки зрения уменьшения времени вычисления алгоритмов обработки цифровых изображений при оптимальном расходе памяти ОБУ ПЭ ВСШ "ПАРС". Другими словами , ату задачу необходимо рассматривать не с точки зрения уменьшения услуг пересылки данных между ПЗ вычислительной среды гиперкуба, а с точки зрения уменьшения временных затрат связанных с блокировками вычислений ПЭ при передаче данных. Поэтому для начала необходимо создать,некоторые "Карты загрузки", представляющие из себя тривиальные структуры: плоскость,сферу,тор,дерево 'и ,т.п., чтобы затем воспользоваться ими при реализации алгоритмов обработки цифровых изображений..

Зная, правила построения идеального QJ* и QR* п-мерного пространства гиперкуба, а также определив связность RR»,не-

обходимо разработать алгоритмы размещения элементов цифрового изображения. Или, как уже отмечалось, данная задача сводится к разк ¡дению двумерного цифрового изображения в Н-мерном пространстве гиперкуба. Т.о. , необходимо создать карту загрузки элементов цп^овых иэобравений для Ш1Э "ПАРС" размером 64x64, значения элементов которой соответствуют адресам в М-мерном пространстве гиперкуба. Решать данные задачи будем для'идеального ЧЛ^и затем С*^--мерного пространства гиперкуба..

Дадим построение алгоритма получения манерной "карты еагрузки" для мерного идеального пространства гиперкуба [22].Другими словами,построим алгоритм получения структур» 4-х связной области в ВСГО, двоичные адреса, элементов которой отличаются в одном разряде..Возьмем фрагмент размером 4x4 и попытаемся из него создать структуру 4-х связной области, удовлетворяющей нашим требованиям. Для этого сформируем матрицу (см.рис. Б).

|о а е П |с 4 ( е| |в 9 Ь а|

|8 9 а Ь| |8 9 Ь а| е|

|4 5 В ?| [4 5 Г 6| 14 5 V 61

10 1 3 21 |0 1 3 2| 10 1 3 21

Рис 5 Формирование матриц, . '

. Проведем над ней некоторые преобразования:

- поменяем местами 3 и 4.'столбцы матрицу; '■-■

- поменяем местами 3 и 4 строки матрицу, у

В результате преобразований получим матрицу размером 4x4, элементы которой отличаются в соседстве друг, от друга в пределах 4-х связной области в одном разряде, : что соот ветствует ко,4у Грея, Обозначим полученную матрицу.через И (см.; рис.6). Сформируем матрицу Мл. пэ .элементов матргадо

- 18 -

М путем "зеркального отражения" относительно ее столбцов.

|а 9 Ь э| |а Ь 9 81 . а - Ь - 9 - 8

М- |о с! Г е| М* - |е I д о| в - Г - а - о

Ц Б 7. е| |е 7 6 4| 6 - ? - Б - 4

10 1 3 2| |2 3 1 0| 2-3-1-0

а) б) .

Рио 6 а) Матрицы связи М и М*.

б) Граф связи соответствующих ПЭ.

Иатреда М* тоже удовлетворяет условию 4-х связности иат-рицы М, двоичные значения соседних элементов матрицы М* отличаются также в одном разряде.

Аналогичным образом сформируем матрицы Н и Н*, из элементов матрицы М, путем "зеркального отражения" только теперь относительно строк (см.рио. 7).

(0 13 2| 12 3 1

, Н - |4 5 7 6| Н* - 18 7 5 4!

|с с! Г в| (е Г <3 с|

|8 9 Ь а| {а Ь 9 81

Рио 7 Матрицы связи Н и Н*.

Нетрудно заметить, что полученные матрицы Н и II* также удовлетворяют условию соседства в пределах 4-х связности. .Теперь иа полученных матриц связи м, мя. К, ¡¡а «сжю получить матрицу М1 размерностью 16х1в, элементы которой будут удовлетворять в смысле соседства в пределах 4-х связной области (см.рис. 6).

I 8Н* 9М* ЬН* аМ* | М1 « | ЙМ сН ГМ еН | I 4Н* Ш* 7Н* 6М* | | ОМ 1Н ЗМ 2Н | Рис 8 Матрица свяэи М1.

Далее для подученной матрицы М1, можно сформировать, по выше изложенному алгоритму, соответствующие матрица свг.эи М1*,Н1*,Н1, которые также удовлетворяют условию соседства в пределах 4-х связности и т. д.

Нетрудно построить с учетом выше наложенного алгоритма матрицы связей для !)-ой размерности матрицы Мп, которые будут состоять из линейных комбинаций соответствующих матриц связи Мп-1, Мп-1*, Нп-1, Нп-1* (см.рис. 9)

| 8Нп-1* 9Мп-1* ЬНп-1* аМп-1* I

| сМп-1 ¿Нп-1 еНп-1 |

| 4Нп-1* ?Нг>-1* 8Ш-1* |

| ОМп-1 1НП-1 ЗМп-1 2Нп-1 |

Рис 9 Матрица связи Ып.

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

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

Далее рассмотрим свойства матрицы М размером 4x4. Нетрудно заметить, что соседство не нарушится, если производить над матрицей М следующие действия:

- циклический сдвиг а) относительно строк;

б) относительно столбцов;

- различные зеркальные.отражения;

Если учесть первое свойство, то количество карт загрузки элементов цифровых изображений в пространство гиперкуба равно 16 х 15 х 16 » 40Э6.

№\ -

- 20 -

31а данного количества карт' загрузки оче вдно оптимальным оорззом может быть выбрана хотя бы одна, которая наилучшим, образом удовлетворяет всем требованиям реальной. ЕСПО. Рассмотрим также'свойства матрицы М с учетом известных инвариантов соответствующего СЦ-меркого гиперкуба.

■ Для того, чтобы рассмотреть действия данного алгоритма на ОР. -мерное реальное пространство гиперкуба, необходимо более подробно ознакомиться с системой коммуникации между. ПЭ в БСПО. Таблица соответствий адресов и направлений обмена представлена на рисЛО.

,-—-р.—р-........... .....с ■ " ■ "1 i; !■■■'........ ...... " ■——»

(локальный) | :'.. | имя | 8

i навиг. | d | 02 01 DO (канала) комментарий

I код | . | I ( . ' , |

5—-1' I . .--Н-—I-:-■-1

S I I I Г 8

J 0000 ¡010 О О | Н It {

Ц || | | I- обмен с внешним (

J 0000 111 00 1 | TH | J . соседом 8

8 I I I I .'■'■,.; S t 0000 I 2 | 0 l 0 | h . |обман самого с собой!

г • i i . i .

S I 3 i О l l | h4 | резервное значение J

S . I . i ■ . I I . «

1 0001. | 4 | 1 0 0 | hO l л Г

» - 1 ! . .! ! ! i

j 0010 |5|10l | hi | | обмен с внутрен. i

9 I I » I . | I (принадлежащими ( I 0100 Г 6 | 1 .1 О Г h2 | Г одному ПП0) . S

i : ' 1 I ; . I II соседями 8

J 1000 I 7 |. 1: 1 1 j ha | J. ■': s

i I I - ' : : l ■ §

; t-- • , .„.;_ ' ' ' • '•' ' • »

Рис. 10. Таблица соответствий адресов и направлений обмена.

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

Чтобы лучше понять наши рассуждения на этот счет, рассмотрим планарную карту загрузки, полученную по выше изложенному алгоритму с направлениями обмена ( см. рис.11 )•

I

-ЬЗ -:-:-———|

м о но 1 ы аи 2

Ь2

4 5 ? 8

ЬЗ

с <3 Г е Ь2

8 9 Ь а

Рис. 11 Направления обмена в 4-х мерном гиперкубе

Так, при .; многократном выполнении операции обмена данными между ПЭ'с чередованием направлений ЬО и мы тем самым будем циклически сдвигаться по плоскости вправо (влево).. При чередовании направлений Ъ2 и ЬЗ, как видно из рисунка, сдвиг будет происходить вверх (вниз). Не сложно теперь составить комбинацию' из чередования направлений обмена, чтобы осуществить сдвиг, скажем, по диагонали или более сложной траектории, . Однако вся сложность заключается в

транспортных задачах между блоками 21. Ведь в мерном реальном, пространстве,по сравнению с СУ -идеальным, отсутствует некоторая часть связей, что безусловно сказывается в основном на вадачак транспорта. На рис. 12 изображена карта загрузки Ойг-мернсго реального пространства гиперкуба для блоков 21, где 1-16.

^Рис. 12 Структура коммуникаций блоков 21, 1=16, Теперь для того чтобы полностью охватить все наше сра-мерное реальное пространство гиперкуба, необходимо еще изобразить., и последний уровень блоков 21, для 1»16х16 (см.рис.13).

(с0>ж4 со ей Рис.13. Веркиий уровень связей глобальной адресации.

- 23 -

В результате анализа направлений для определенной карты загрузки можно однозначно указать, какие связи осуществляют сдвиг в определенную сторону. Однако при этом придется анализировать множество параметров каждому конкретному ПЭ. Так для нашей выбранной карты загрузки за напразление "право" ( лево ) отвечают связи ЬО, М на логическом уровне, а на

глобальном |4|

соответственно, за направления верх (низ) отвечают связи М, ЬЗ на локальном и [61 |с1 [Л на глобальном уровнях.

ьшыы

Нужно еще раз отметить также, что состав связей для определенного направления сохраняется лишь для конкретной карты загрузки. Так как в системе коммуникаций участвуют лишь сами ПЭ, то узким местом для ЦКп-мерного реального пространства гиперкуба является переход между ПЭ различных блоков. Поэтому количество карт загрузки, из которых следует выбрать оптимальную, снизится с 16x16x16 до 16 - числу перестановок элементарного одного блока 21 внутри себя. Однако с учетом выбранного правила уменьшения связей СУ -мерного , идеального пространства гиперкуба и выбранного алго-

*

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

Действительно, если рассмотреть реальную планарную карту загрузки для 16 ПЭ, и рассмотреть пары ПЭ, участвующие в обмене на глобальном уровне, то можно обнаружить, что эти пары окажутся одинаково ориентированы (см.рис. 14).

т ш шз шп

[32] Ш

ша шх

Рис. 14 Пары ПЭ, участвующие в связи

... на глобальном уровне.

Следовательно можно утверждать, что для данной карты загрузки аффективное, использование ПЭ между блоками 21 вверх/вниа будет равно 2, а вправо/влево равно 1.

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

Действительно, при указанных перестановках у нас сохраняется правило соседства ПЭ, следовательно,мы можем поменять местами количество ПЭ, аффективно участвующих в связях между 21, тогда направление вверх/вниз будет равно 1, а вправо/влево - 2 (см. рио. 15.).

0 4 с 8

1 5 с1 9

0 4 О я

3 7 Г Ь 1 5 а 9

2 6 е а

1 ¡3 '14

Рис.15. Пары ПЭ, участвующие в связях между блоками 21.

Т£: Максимальное число операций при транспортировке данных между'соседними блоками равно 9. Данное утверждение доказывается.довольно просто. Максимальное расстояние в Ч -мерном кубе, : как было показание выше, равно его размерности п. . В данном случае, для:любого блока 21- оно равно 4 ( 16). Таким образом, максимальное расстояние определяется как удвоенное значение . размерности и одной внешней связи, т.е. равно 9. : '' : . ' ■

При использовании перестановок внутри блоков 21, мы можем выбрать карту загрузки с максимальным числом операций при обмене между ПЭ равным 9. Действительно, если число ПЭ между соседними блоками Ъ\ равно 1, то можно сосчитать количество операций внутри блока 11, оно равно 9 ,т.е. 4 операции по доставке бита к передатчику .одна передача соседнему блоку и 4 по доставке на место ( см. рис.1в ).

Рис. 16. Карта загрузка ЦК,.

Теперь постараемся определить минимальное расстояние между соседними ПЭ соседних блоков.. Для этого рассмотрим транспортиэацию значений элементов изображения, размещенных согласно выбранной карты загрузки в памяти ПЭ. Так как из выше описанных утверждений следует что, по одному из направлений эффективно используется две пары ПЭ, а по другому-одна пара ПЭ, -выберем заведомо худший второй случай. Как было показано выше, для данного направления вправо/ влево-передачи на глобальном уровне отвечают следующие пары 0/1, 2/3, с/<1, <Г/е. На рис. 17 показаны непосредственные соседи и соседи о расстоянием в один элемент соответственно для ПЭ с локальными адресами 0 и 1.

- гь ~

(£5)? 6 4 вСмр

шже) ОШ

ШЩъ сШЩ) (Он е с с1{£~е) [ОО) (р)|?~е1

Ь© (Щ)Е1 ^ШЕЗ кЩЩя

а) . б) . в) г) д) е)

Рно. 1?. Анализ расстояний в карте загрузки ГО в ВСПО гиперкуба. Расстояния для ЛЭ о локальными адресами: а) 0;б) 1 ;в) 0,1;г) 3,2;д) (8,9); Г,е. (Ь,а),.

Ив ранее описанного соседства ПЭ на глобальном уровне, можно рассматривать передачу элементов из Двух пар по одно-, му, так как для других двух связей действия будут аналогичны. Другими словами, можно рассматривать передачу 4-х крайних _ элементов соседнему блоку £1. В нашем случае -соседний блок состоит из двух пар 0/1, 3/2 и сЛЗ, С/е ¡возьмем соответственно 3/2 и Из расположения ПЭ в блоке 21 можно сосчитать количество шагов необходимое для передачи всех 4-х крайних элементов,.циклически сдвигая их вдоль границы, таких, шагов окажется 4 ( см.рис. 18 )., а с учетом локаль-1 них передач, значение будет равно 5. . '

Уменьшить число шагов при передаче между глобальными соседними блоками 2\ за счет, скажем, передачи через два ПЭ,не уменьшит число шагов,так как увеличит на 4 количество внутренних пересылок, что явно нежелательно. Однако приведем ни*«? оба алгоритма по шагам (см.рис. 19).

г

113 112 (117 116 | Ш Не |

^ 32 33 -■■■.'. | 312 313 ; | . 36 ;37 ' | ' 316 317 I Се 31" | 31е 31Г

11Ь 11а Ь—1 | 2а ЗЬ (—I 31а 31Ь

Рис. 18, Оби*н данными между глобальными средними ПЭ

Г - Г 1 1 1 1 г\ | 1 - 22 1 231 |

1 1 11.1 1 г -> 23, а -> гз1 1 23 -> 2 231 »> а |

1 1 ( внутренние пересылки соседям )

|2. | циклический сдвиг | нет операции нет операции!

Г 1 а - е. - б - 2 |

|Э.| 2 -> , а -> | -> 2 -> а I

1 1 Ц;икл. сдвиг ае62)| ( цикл, сдвиг) (цикл.сдвиг) |

14.1 '2 -> , а -> ■ .1 "> 2 -> а I

1 1 (цикл, сдвиг аеб2)| (цикл.олвиг) (цикл.сдвиг) |

|Б.| 2 -> , а'-> | -> 2 -> а 1

1 1 1 1 (цикл, сдвиг ае62)| ...................... ,,, 1 (цикл.сдвиг) ' (цикл, сдвиг)| 1

1. ->' 2 -> а 2. 2(6) -> а(2) 3. 2(е) -> а(в)

-> 6 в 6(е) ■е 6 (а) е(2)

' -> е е е(а) 6 е(2) 6

'> а 2 а(2) 2 а (в) 2

4. 2 (а) -> а(е) 5. 2 -> а(а)

6(2) в (в) 6 ■в(в)

8(6) 6(2) е 6(6)

а(е) о а 2(2)

Рис. 13. Алгоритм передачи данных с помощью циклического сдвига.

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

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

Для начала необходимо определить ряд параметров, речь о которых шла выше: уровень распараллеливания алгоритмов, объем используемой памяти, карта блокировок и т.п., при атом как и ранее мы исходили из того, 'что каждый ПЭ должен содержать свой элемент изображения. Условимся также, что обрабатываемые нами изображения относятся к классу полутоновых, т.е. значение любого элемента цифровых изображений занимает ровно один байт или 8 бит. Нами предложена следующая обобщенная блок-схема реализации алгоритмов обработки изображений в ВСПО с архитектурой гиперкуба (см.рис.20).

I . 1 ■ "■ ■ ■ 1 ■ ц ■

|1 Инициализация ПЭ и задача транспорта | 1 . • * ^^^^^ н ^^^^^

. I- : ■ . ■' , '-Д----»

|2 Ввод данных согласно карты загрузки | I ....... ...... ц ...... . »

I ....-'--—Ч ; .

|3 Восполнение данных 8 .«—-г—--'

Г-----■'■. "-----—-»

14 вычисление алгоритмов обработки 5 «__- »'■'■.----

, н .

I

¡¡5 Бывод данных 1 * «

Рис.20 Обобщенная структурная схема, алгоритма обработки изображений.

- 29 - '

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

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

Таким образом, компас будет состоять из 4-х участков ОЗУ ПЭ, каждый из которых будет иметь информации о трех или пяти пересылках в зависимости от направления в выбранной карте загрузки. _В таблицах 1, 2 на рис. 3.2 показаны карты направлений а) на локальном и б) на глобальном уровнях, причем в последней таблице показана лишь 1/16 часть, оставшиеся части можно восстановить, изменяя старшую составляющую, начиная с восьмого номера, на соответствующий номеру младший ряд. Так следующая строка таблицы будет иметь вид 1 2 4 8 0 0 3 0 5 0 9 0 и т.д.

Данные карты помогут нам в создании соответствующих "компасов" для каждого ПЭ. Понятно, что для каждой карты загрузки изменяются логические соседи (согласно направлениям) , поэтому и необходим компас в памяти каждого ПЭ, чтобы твердо гнать количество шагов до соседа соответствующего направления приема. Так на рис. 3.3 показан компас для некоторых элементов.

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

На этапе ввода данных в ОЗУ ПЭ необходимо учитывать свой ряд параметров:

1) Количество свободной памяти.

2) Размер необходимого для обработки окна изображений.

3) Порядок загрузки согласно выбранной карты загрузки.

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

Постараемся немного пояснить выбранные парше три. На таком параметре, как количество свободной памяти вряд ли нужно останавливаться подробно, т.к. при оптимизации систем по времени ымислекий, алгоритмы тем самым требуют увеличения затрат памяти под буферные данные. Однако, если окно, небходшого для обработки изображения, довольно велико, то е памяти кавдого ПЭ может храниться .несколько в.осьмибитовых. элементов. Данное' расположение можно представить как фрагмент изображения,- . сложённый в несколько раз, скажем в вгде квадратов размером 54x54. Что в свою очередь'-также зависит

зт количества свободной памяти, которой может и не хватать, :кажем ,для изображения большого размера. Тогда можно раэ-5нть в свою очередь все изображения на фрагменты и загру-«ать оверлейно, хота -это не совсем хороший вариант.■

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

1. Транспортная часть (Компас).

2. Буферная часть.

3. Данные. . • , .

г г < )

1 1 0123)4 [

1 1 |0| 1 1 1248(10 I

|1| 0359|11 |

1 I 121 1 1 30ба|22 !

131. 217Ь|23 |

) ! 1'4| 1. 1 563с|44 I

15! 471сЦ45 |

1 1 16! ! I 742е|55 (

т 1 . 1 653Г|87 I

( 1 )в| ■ 1 1 9ас011031

¡9) 8М11109|

1 ! '|а| 1 ■ 1 ЬЗе2!Е0а|

|Ь| н- а9ге|£0Ь| -■ . Г !

|<1| еГЭ5|40с1||

н-—-+-

|е| {"сай^ОеП ! е Г •гс!Ь'? I аог (

и_1_:_I . ... I

а).

г 1 1 1 101 II 11 11 1 23)45|б7|39!аЪЫ!еП

1 0 1 1 2! 41 8|10[20|40)301

1 1 1 0 3! 5! 9)11|21(41|81!

12 13 01 6! а|12122|421в21

1 з 1. 2 11 71 Ь|13|23|431331

1 4 1 5 61 01 С|14|24|44|84|

1 5 1 4 7| 1! с!|15|25|45|351

16 17 4) 2.1 9)16)26)16)351

1 7 I в 5| ■31 Г|17127|47187|

I 3 1 э а! с! 0|13|£.9|48|83|

1 з 1 8 Ь| Й1 1Ц9|29|491£9!

1 а 1 ь а| е| 2|1а|2а|4а|8а!

! Ь 1 а 91 £"1 ЗЦЫ2Ы4Ь|ЗЫ

1.'с 1 а е) в Г 411с|2с14с|3с!

1 .а 1 С П 91 5!1<1|2'1|4с1|8Л

1 Г с| а| 6!1е12е)4е|8е!

! г 1 .' !.> 1 с!! » Ы ,1 7)1! ¡2; 141' ! 1 III I

Рис.21

•б).

Направления в пространстве гиперкуба а) локальное; : б): глобальное.-'

2 <—> О

а;

2 6 4 0

3 7 5 1 Ь Г с! 9 а е с 8

б)

I—I—1

7: 1Н |ПЭ|

10 |5 |

11 I

12 |3 |

13 |6 |

т—I

Г: 1Ы |ПЭ|

Ю М |

11 |е |

12 |Ь |

13 |7 |

в)

Рис.82 Атрибуты транспортных операций а) выбранный компас;

б) локальная карга загрузки; в) направления связей по компасу для ПЭ одного блока 21.

Важными задачами при реализации алгоритмов обработки данных на ЕСТО с любой архитектурой являются задачи восполнения недостающих данных. Ранее отмечалось, что при решении многих задач обработки цифровых изображений приходится сталкиваться с множеством однотипных операций,производимых в некоторой окрестности. Другими словами,для каждого элемента изображений кеобхомо знать значения яркостей некоторой области а учетом определенной связности. Как уже отмечалось, данную проблему можно решить, по крайней мере, двумя путями: восполнение данных за счет многократной загрузки элементов некоторой окрестности и путем решения задач, транспорта, т.е га счет пересылки данных из'соседних. ПЭ. Однако первый оииооб шл««т ряд ограничений, а глаг-цсо, но

-33 -

зпользует особенности выбранной" архитектуры, поэтому зссмотрим второй случай. Теперь для восполнения данных зжно воспользоваться компасом направлений,который находится памяти каждого ПЗ. Согласно алгоритму'*, разработанному во горой главе, произведем восполнение данных. Таким образом, чя восполнения данных в окрестности, в частности, 3x3,для элутонового изображена необходимо совершить 3*40-220 так-эв.

Так как основные наши усилия были направлены на создала тривиальных плоскостей, то в дальнейшем и реализация игоритмов будет тесно связана с соответствующими алгорптма-:! обработки изображений, а именно с алгоритмами,ислользую-¡ми для своих расчетов некоторую окрестность,к примеру, (3. И после решения задач восполнения данных ,за счет, кап-;шер, операций транспорта .можно приступить непосредствен-э к реализации некоторых алгоритмов обработки изображений. jk каждый ПЭ содержит хотя бы один элемент цифрового изоб-зжения, . поэтому нам достаточно реализовать алгоритм для зного элемента изображений,а остальные обработаются парал-5льяо за один ваг.

0СН0БНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ '.. ■

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

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

Z).Классифицируются системы обработки изображений' на. ■новё. Параллельных вычислительных средств с SIMP) ШШ и твейерными архитектурами. .

- 34 -

2).Проанализированы и классифицированы функции обработга цифровых изображений .необходимые для соответствующих ВСЮ.

4.) Опираясь на теорию графов, разработано определение идеального СЦ„ и реального 0КИ- мерных пространств гиперкуба , учитывающж правила соседства ПЭ . в параллельном процессоре.

Б).Используя определенную теорией, графов вершинную связность, определяется связность изображений.

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

?). Путем некоторой оптимизации удалось снизить максимальное расстояние до соседнего элемента изображения, с 9 до Б. . .' .'■■'

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

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

9). В результате разработанной-методики были реализованы следующие .-алгоритмы обработки изображений: V . алгоритм кругового гардиента;

алгоритм преобразования -Лапласа; -

- алгоритм низкочастотной фильтрации;

- алгоритм медианной фильтрации; ■:..-.;''; '

- 35 -

- алгоритм сглаживания по методу Нагао.

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

ы:

1.Д.А.Пономарев.Размещение цифрового изображения в ространстве ВШО с архитектурой гиперкуба, тезисы н-т.конвенции, Ташкент, 1991. "Проблемы создания систем,анализа и ганимания изображений",с.53.

2.Д.А.Пономарев,Ж.Э.Бенуа.Алгоритм сжатия и инвариант-;ого описания изображения линейчатой структуры.Сборник на-, чных трудов. Под редакцией А.В.Ефимова,МИЭТ,1990.,с.100.

3.Д.А.Пономарев.Алгоритм выделения эталонного объекта ia изображении линейчатой структуры.Сборник научных трудов, !од редакцией A.B.Ефимова,ШЭТ 1990. с 106.

4.Л.Я.Рукавишникова,Д.А.Пономарев.Об одном алгоритме-1ыделения эталонного объекта с помощью инвариантного описа-!ия изображений.,тезисы Всесоюз. кнференции"Микропроцессо-)Ы-85",Москва,ШЭТ,19S5. ,с.85.

Зянал 353. Тираж 100 06?,рм 1.4 уч.издания. Отпечатано в типогрв-*мм МГНЭТ ТУ