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

pre НАЦИОНАЛЬНА АКАДЕМ1Я НАУК УКРАГНИ 1 Ф1§ИК№№ЕХАН1ЧНИЙ 1НСТИТУТ ¡м. Г. В. КАРПЕНКА

1 п OUT /or>/i

1 ' uni '■ ? На правах рукопису

ПЕЛЕНСЬКИЙ Олександр Любомирович

ВИСОКОЕФЕКТИВН1АЛГОРИТМИ I ЗАСОБИ ПАРАЛЕЛЬНОТ Д1Т ДЛЯ ОБРОБКИ ШВИДКОПОСТУПАЮЧИХ СИГНАЛ IB

Спец1альнкть 05.13.14 — системи обробки шформаци

га управлпшя

Автореферат дисертацм на здобуття наукового ступеня кандидата техшчних наук

Льв1в— 1994

Дисертащею е рукопис.

Робота виконана у «Язико-мехашчному шституп ¡м. Г. В. Карпенка HAH Украшн

Науковий KepißiinK: член-кореспондент HAH УкраТни, доктор техщчних наук, професор ГРИЦИК Володимир Володимирович

Оф'щйт опоненти: доктор ф1з.-мат. наук, професор

СЛОНЬОВСЬКИИ Роман Володимирович

кандидат техщчних наук, ст. н. с. ВОРОБЕЛЬ Роман Антонович

Проводка устачова: Ужгороцськии державиий ун/версигет

Захист вшбудеться 31.10.94 р. о 16 годиш на засщанш спещал1'зо-вано! ради К 04.01.01 при Ф1зико-мехашчному ¡нститут1 ¡м. Г. В. Карпенка HAH УкраТни за адресою: 290601, м. Льв1в, вул. Наукова, 5.

3 дисертащею можна ознайомитися в б1блттещ шституту. Автореферат розкланий «_»_______199_р.

Вчений секретар спещал1зовано1 ради

БУНЬ Р. А.

ЗАГАЛЬКЛ ХЛРЛКТЕРИСТИЛ РОБОТИ

АкгудлыМсть томи. Цн$рова обробка, розп!знавання 1 анал!з аобрадонь анаходнть иироке замгосуваиня в багатьох автоиатнзоваиих техники* системах угтрлллдшш.ти вииористо-вують да))1 у пигляд! зобралень. Це систем« техничного аору в робототехник 1 снладтшх тсхн!чюм системах, дистанц!йне зондуваиня , автоматично р03П13навання друиованих пипка в п читакчих автоматах, неруЛн^ниЯ контроль якостх промислоеих вироСцв, роап1знапання ренттсн1Еських зн^м'Лв для потреб дично! л»агностики та 1 па. Цк$р°ва обробка асбражеиь доаво-ляе'автоматизувати влро'бннч! процеси,п1 дауг^яти продуктивность прац! £ ефсктийНсть наукових досл1дяень. Однак ун!-версальн! КОМ нссконом1чн1 при "виконанн! в!диоспо простих локальних операций,а ци}рора обробка зобратюнь, припускаючи подания зображень у яиг ляд! двом^рннх матриць дзних,призводить до необх!дноет! створення для цих даних пам'ят! Великого рбсягу. В цьому випадку затрачусться багато «аяашного чару для передач! даних аобраяень м!ж основною пам'ятт» I до-пом5жним запам'ятопумчш пристросм.

Алзратн! аасоби специального призначення, оптнм!зован! для обробкя зображень, реал!зувть висок! поте«ц!йн! можли-вост! сучасно! м!кроелектроШки, яка дозволяв. створити за-пак'ятовуичиЯ пристр!й великого обсягу на «ристала*, а пара-лельна арх!тектура спец!ал1зованих обчисл» вальинх аасобдв доаволяег розв'язувати задач 1 обробки , розп!знавзння 1 ала- •' Л1зу аобраиень в реальному масштаб! часу. При розробц! висо-копродуктивних засоб!в вимагавться насамперед визначяти ое-

нови! властивоет! виутргшиього паралел1зму алгоритм»в та за-коном!рлост!, яким лхдпорядковуеться структура паралолышх процесав оброСки !мформацП. Тому визначення клас!в алгорит-М1В о6роб!(и зобра*ень, цо допуснають розларалелишалня на задан ому р!внг 1 доэволяють реал1зувати 1х в реальному чае!, е актуальном задачей роэроОки сметйал1зоиа)шх високолродумтив-инх обчиелкшалышх засоСИв паралельнох дП.

Нста роботи та задача досл!джешш- Мето» робота с роа-робка 1 дослхдчоиня високоефективюгх алгоритмов 1 спецпроце-сор1В паралельно! дН для обробки швидкопоступаичих аображень об'ектдв а реальному масштаб! часу. При цьому розв'язу-нться наступи! задача:

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

- роав'зок задач! в!дображення паралельних алгоритм!в в обчислквальи! системи ларалелмш! д! а;

- розробка узагальнених паралельних 1 маНстральни* алгоритмов и!дновленнн ! ф!льтрад!1 аображень об'екта;

- синтез однор!днга обчислмцалышх еередовищ (00С), оптик^аованих для створення спсц!ал!аова>ип обчислювальних аасоб!в обробки аображень;

- реал!аац!я на 00С алгоритму $!льтрацИ аобратешю 1'а збереюжня* контура.

Цетодя допЛдоюння. Для роав'язакия поставлена задач застоеовузались метода теорП розтанаааяня образ!в, гсор! 1 Аков!рнаст! 1 натенагнчно! статистики, тсор!! {нформац!* та иодукшня.методи 1м1тщ1Янаго модолквання.

Наукова новизна днеертацИЬю! робота.полагав в наступ-

всму:

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

2. Сиитезовзно «роблемно-ор^ситонан! паролевым обчис-лсаальн! етруктури та кмескоирадукпнш 1 спецпроцесори пзра-лольно! дд1 для систем лолередньо! обробии г анализу зобра-йинй .

3. Запропоновано та догаИд^ено матесапгшп молол! аоб-ра^онь об'с«т1п при умов» дм заз*ад а разними законами роз-под1лу, 1нтенсиян1стю 1 $ункц1ем 5Х дН на зображення об'егк-та. Виаиачено ио^ливоет! розпарзлелювання обробки 1Н$ормзцИ .три реаЛзацИ аалроиоиоплти алгоритм ¿в покрй'.прння якост! при $ормува)Ш1 аобрат.ень об'скта яа основ! 1терацШ1их ысто-

д1в.

4. Реал1аоваяо на ООС злгормтмм {НльтрацП забрлження ¡а зберешениям контура, баауються на вид1лзнн1 "в1кон" (п1дматриць ).

Автор захкцав : " 1. Запропонован! узагальнен! ларалвльн! I маг1стралы11 елгорнтан в1дновлеиия та ф»дьтрац1$ зобрадень об'екта в до-я!лы<ому напрямку поля спостсреиення, наведен! схеми I* реа-дгзгцН.

. 2. Результате досл^джшшя алгоритм1п вхдноалення та ¡гЬтьтрацН аображень для ряду важливих частного« вдпад>ив просторового дк^ерекцнтаишя, просторового та лог!чного зглздяування, порхвняиня а еталоиом 1 вид1леиня неав'язаяия'' зобралень о5'гат1й.

3. Способ опису, розпдзнаваши 1 клася^МкацП об*ект!в, агядно иного складн! зображення опнсуються аз допомогсл

- е -

cjiiB, фраз i т.д. ia аастосуванням грамагнки i ал$ав1ту, який складасться ia букв, 140 визначають прост! об'екти (або утпоримчх об'екти). Шдх!д дас можлив!сть в ряд! випадк^в роагяядати склады i об'екти а врахуванням bcix at&iiiHMX перет-вореиь: паралельнкй перенос, обещания, под!6н!сть. BiH базу еться на принципах рекурсивност! та iepapxiuiioï структури об'екта, ар дозволяв проводите глибоне розпаралелншання об-робкм 1н$ормацИ на ааданому piKiii при oimci, poaniaisaBaitHi ■га класиф^кацН складки* зображень в реальному waciraaôi чаСУ;

4. CnociC синтезу та иалаштувалня паралельюм алгоритма для ООС 1 реал^аацН i у ниц id до давания, avtirot знаку числа, в1дн!мання, видЦлення модуля числа, «ноженн» восьмироэ-рядних чисел в мсда$1кованому додатковому код! (МДК) без роапаралелмваяня, видения и1н1ыально1 1з дао* дисп&рс1Й i в!двов!дного дй середнього.

5.3апролоновану обчиелнзальну систему на Саз! ООС, що' npaiycs за принципом конвейБра.

Практична ц!нн!сть. Робота виконувалася в рамках планово! тематики ®!зико-механ!чного ¡нституту !ы.Г.В. Карпеика HAH ynpaïioi ( Постанови Преаид! 1 АН УРСР M 535 в!д 25.11. 1983р. 1 H 474 в!д 27.12.1985р. )„ а танож в рамках- госпо-дарських угод.

Реал!зац1я р»?аул»тат)в робоуя. На основ!' запропонова-ккх уаатальиених ларалельиих та иаг!етралытх алгоритм!и в!дноме»ия f ф! льграц! i аображень створено слец!ал!зоваа! процесори ив1льтр-3", и«1льтр-4" 1 Н41льтр-Б", як! виготов-лек! на Досл1дному завод! fiil HAH Украсил. Вони ма»ть швид-код!я, достатки для обробки *елев!а!йних зображень в реаяь-

ному масштаб! часу i вдаористовуют&ся в cneqianiaoBaimx системах реального часу.

Роэроблено nporpanni ааеоби i структур» i схеми елемен-tíb для рсал1зац!1 00с, в яких потони in$opmauh обробляють-ся зНдно программ, проходячи посл!довно в!д homípkm до ко-м!рки в матриц! 00С. Вони молить застосовуватися як для цнф-pcBOi обробки реальних аображень, так i lia отап! розробкм í тестуваиня нових метод!и на модельних аображеннях.

АпробадИя робота.Осиobhí результата дисертацШю! робота допов]дались та обговорювались на Всосокганих конференциях i семинарах: "Розпаралелявання обробки 1н$орма-4iírt(m.j!bbib, 1985 р.,1986р.), "Автоматизован! системы обробки аображень (АСОЗ-Бб)" (м.ЛьВ^в,1986р.)."Математичн! ме-тоди розп!знавалия аображень"(м.Дьв1в, 1987р.) í И1жнародн1й яонференцП а 1нфоряац1Йюя технолоПЯ 1 систем (XTIC - 93) ( m.jibbib, 1993 р.).

Публ1наци. Основннй aniCT робота воображений в деа' -ять ох гтубл}кац1ях.

Структура i обсяг дисертацдйноЗ робота. Дисер-кщ1йиа робота складасться ia встугту.п'яти роздШв та bhchobkíb, зшкладених на 114 CTopíimax la 17 рисунками,, ,м1стить список Лтератури на 108 яаЯменувань 1 три додагки. Загальиий обсяг дисертацП - 149 пора л ок.

SMICT РОЕОТИ

У Bcryni обгрунговуеться актуаленiсть теми дисер-таЦ1Йно! робота, Я1дзначаиться вгдом! результата та нёроав'-язап! проблеки, а таяож вианачаеться мета робота i напряики досл!дтень для досягнекня поставлено! маги.

В першому роздал! робота викладено принципи в i добра-

жмшя паралельних алгорит>ЛЕ в п&ралельн! системи обробю: аиформацП. Бюйдним с хмзначення обчяслюЕальмо! системи па-рдлсльно! обробки 1Н$ормацП для высокопродуктивного aiianiay i оСробки.зПдно якох'о системой) S обробки i njopvaxji i нази-васться BiSHOüüiuüi на непустих мполошах 14 , причому

Sex {Vi :i.6Ja}, 3 метою досл1даеи)!Я Mowamocri налашувакня проблсшш-opieii-топэних паралельнлх обчиелкшалышх систем обробяи i анализу аображеиь на peaniaaniw конкретннх алгоритмов, такий доа1ЛЬ-нкЯ алгоритм предетавлясться у виг ляд! noMiflOEHocri $ункц1-оналышх oncpaTopip, Oi ^ i--ftrrt - На nift посл1довност» Суду сться функциональна граф-схема алгоритму, в я«!й кожному функциональному оператору ставиться у П1Длов1Д!псть вершина графа, а вершияи гра$1В,цо вгдпов»дають операторам Oit ¿-¿т j з'еднуються и!ж собой тЬтьки в тому шпаДну, кк-

що результат, отриманий в!д реал!аацН оператора Oi с одним 1з aprynoiiTia оператора Oj . Побудовада таким чином гра$-схоиа noBiiicT» воображав BiiyTpiwn» структуру алгоритму j вкзначае множииу його nporpawimx роав'язк^в.

Одная, через nUcyTiiicxb правил формуванвя £уккц1о-надьнлх onopaTopiB i трудной иадэшно! реал1зацИ, прмЯнятлипкн с П1дх1д, при яному умова для паралельного ви-конання оператор in i у випадку AiHiftHOi программ формулпяться г

Oi iOj ПфорыацШш-кезалежи , ящо :

Зп а noutQs** ouoinchi

ЯрУпО - вг1дн! иайори оператора О ;

Оч-t О - вмх1дн! наборп оператора О . Ия yvosa в!до0ражае 1кформац1йн1 ав'язки у фунхц1окаиноыу

rpaji , а такоя аа'яаки по naM'nxi . У вкладку программ i;i роэл1знавачамя ni» ii опер,порами палии! зв'яэки третьего талу - угранлявч! (лсг!чн!) , цо в аагальному вмлпдиу пород-кус р!зн! данцкжни у £,уннц!оналыпй гра{»-схем! при piairax дзнмх. Тод> оператор« 0¿ i Oj, вважакться паралелышин, як-fío вони ларалельн! в будь-яному лаицгагиу функционально! ехе-им. , ■

Па основí вицесказаного про представления программ л ярусио-парзлсльиМ Jopwi i застосовувчи тсоретпна-спстсинкЛ П1дх»д розг.Чядаст&ся одна !з кодглой розпаралелюЕання алго-; ритму Л обробкв 1»$ормацН, яюй представляетъся у виглядi скстски: S'{K Сс>У] , де X ~ в*¡дна мнолииа, що Еизначас г. х i дм i дал! (слова); - У - вих)диа множима, цо вязначаз видан! (слава); Са ~ капал, в якону адШснюеться пере-тгсрення (ари|метачя! i лег i 411 i операцП).

НаЯ65льЕмЯ прантнчнмЯ j»тсpee вмклжая випадол.кали сястеиа S не и!стить управлявши п!дсистеа, цо внаначагать порядок рсботи решти подсистем. Тод!, представлявчи иотеи раз систему S у вигляд! посл!дааност! !и$орыац!йн0-взаемо-иезалекгои п!дсистс& <5^2, , приходимо Сез-

посорадньо до перетворення структури поач1Доя:ю1 оброСки 1а-бориацН в паралельно - посл!довпу структуру обробки, тобто в ярусно-паралал8 ну форму (ЯЛ 5). В процес! лзраяельша под!-л!а важливо, щоб характеримти перетворкжчих иаиал!в .

пядЗлено! мноитш i 1 >i ормац i йло-взасмо лмплеямд ¡пдеистем

скстсни 5 буди аднакавши. При цьому алгоритм обробта Зи$ормацН представляеться у виг ляд i однор1дао! скс-темя, яка мае аначн! переваги у вартост! технично» реал!за-цП над неофюрддяом.в компактност! побудови i забезпеченн!

високо! иад!йност!.

Розглядаеться синтез систем обробки ан^ормадП для проведения ярусно-паралелыюа реал!вацП алгоритма , а таи ом наг!стральних методов реал^аадП процесу обробки !нформа-цН.який дае ножлив!сть побудим одаорхдних структур 1 сере-доигец на реал1аац1И задач! в аадансиу режим! обробки посту-па»чо1 !н$ормацП х зд1йснюеться за допохогою оператор!в каскадного з'еднання, паралелыюго а'еднання ! замикання аворотнього зв'язку, я«! практично внчерпують б^льиНсть нок-ливих а'едиань.

Показано,що при маг!стральному роапаралелкшаин! обробки ¡!1$ормацН, яка поступая у вигляд! телевхахйного зобра-иення.дан! вображення обробляються г.оыЦдозпо в прсщес! роз-гортки аображення,наприклад, стр!чково!. Тут виконуеться па-ралельне обчисяення значена задано! локально* фунАцП вдд Бначснь в!дл!к1в аображення , роаташваюк в окалнцях обчис-лжваиого в!дл1ку . Значения в!дл1К!в аображення а буферно! пам'ят! поступав на конвейер етаШв обробки !и$ормацН. На кожному етаП1 обробки виконусться одна ! та « сама опершЦя посл5довно для кожного елемента даних.

У другому роздШ доел1 допело задач! розяаралелювання алгоритм 1 в обробки 1нформацН в системах попередньо! обробга; аображеш». Зображення об'екта роаглядасться у вигля-

й! 4уикцН {(£,1) роапод5лу енергИ, яка> випроа1нюетьса об'-еттоы. Допускаться, цо инстска обробки а'обралень л1н!йно впливае на сигналя ! вон« нагромадауються в пшцин! аобра-яокня об'екта талол л!н!Лно. В ц&ому випадку процес форну-ааиня а обращения об'екта иожна записати аа допоногоя сп!е-в!дноисиня -0~(*,Ч)-Р[Ь(*>ф 1а(*,У) ,до - оргяЧ-

- 11 -

нал; £> - спотвортачуЛ оператор; ¡¿0(Х,У) -аавада.

Визначення 1/(*,Ч)\а даного сп^шНднощення моина зд!йс-нити за допомого» 1терацШюго методу проекцП. який полягае я тому.що для А -1 1терац11 наближенкЯ розв'язок & (*>У) визначлэться через наближишй розп'язсн для попередньо! 1 терли! 1 б*,У) 1 рхЗНИЦИ) Як початкове набли-ження можна вибрати . Однзл а точки зору реалЬ аац1 I такий алгоритм молопркйнятний в системах реального часу, оск5льки вимагае г.елико1 к!лькост1 сбчислеиь. Показано, 40 даного недоливу позбавлена моди}акаЦ1Я цього алгоритму, яка грунтусться на принципах маНстрально! обробки 1пформа-цП 1з застосуваниян опораторгв реиурсЛ 1 суперпоэицП при реал1зацП двом^риого (Ярового рекурсивного ^льтра.що до-яускае розпаралелквання обробки П^ормацП на ззданому р1вН1 за допоиогом одгюрздцих обчнслкхальнт середовищ.

Якщо на пол! спостереження !Р розм1рн1сти п*п задано спатворене аавадои зобрагення

що

гидпот'дзе аображншо деякого ой'екта, то в!дновлеи-

ая 1 яорекц!» такого спотвореного завадаяи аобрашния мот-ва ад£Ясняти за допомого» запропонованого конструктивного алгоритму в!дновлення 1 корекцН Да.к.. я кий грунтуеться яа структурному п!дход1 1 в паралельюш алгоритмом .

В цьоиу кипадку зображення оО'екта представляйте ся за допомогоя словак .довжином п1 : 6 Е-,

. Кате слово1/ складаеться ¡а п1дсл1в виду#а • То-д1 слово & , що Шдпов¡дае спотвореному аобратаяш ,

представлятиыеться словом *0- , що ¡31дп0в!дае оригинальному зобратнни {/(*,Ч) 1 похибно»^ , внесено» в ориНнал завадами

/V

$(*>У) У вмглядд^-^*^ - ПриЯмагеЧл за г* -иратну похкОку в .

сдоВ1 тзку, при в иьону типтло поел¡ль t похибок, похибку в слов1& наавеыо ^-кратною, йк-

що в ньому виникли ¿з.) -крапп похкбки -к), цизнача; 1зться лочергово кон'кнкд51 Л, п-Ь^г. по б ,

яого в слов! еипрлеляюгься ес! похибки кратно-с-г1 ^ , ДсагПдтаю конструктквшй алгоретм для бхдное-дгашя 1 корокцН аобралеиня ой'екта в умовах. ргзшх $ункц!# дП зааэд.яиий при продставленн! процесс почоргозого ип-качения коя'юккц^й за допомого» оператора супор<7оз»щ! I дспускас розпаралодюБання обробки 1н$ормац11 »а заданоку Р1Вн1 корекцН 1 час його рзал58ацГ1 дор1Еиюе часу реал!за-' цП оперлцг Я порсяцИ цього р^вкя, с;о забезг.очуг масштаб реального часу. При поодннчоыу г,отоц1 елекснт^в'.для формулами зоОралжкня об'плта (поал!донному фсрмувлшП аобрал»»ня об'скта) 1 при застосумнн! оператора рекурсП /? ¡¿тгорита Аа.к. допусказ кагЧстрдллну обробну 1нформацН ¡и аадалоыу р1вн1 корскц! \ цьсго р1в11я, що аабезпзчуо масштаб резаного часу. ■ •

■ Трет!Я роздал присвячдкнЛ досл1доешшузггавькелж па-'рзлолышх 1 маг1стральккх г.лгоркти1в в!диоилйння га фьгьтра-ц|з аображень об'скта". В нг>ому розглкнуто пршцигаз розпара-лглввакня 1 маг!стрально$ обробки !и$ормацН,а таяоя запро-поногаио мат1стралаиий'алгоритм вид!ленкя ьезЕ'язаних'зебрами» об'скта. 3 ц1ем уетои спотворене аобраления об'еета на. под! спостеренсння ^ розм1рн1ст»л^л аадасться словом & у ентляд!: ^

ал а4Л .:.а<я

.а* а«...

«„л

¡;> V- настулипч члион пиД1.м?£ггг>ся слово г".

яке ¿-пдпогидая деяк!й частая! асбра^енпя -¿-Ч втиачля но" дов1--5но1 форнм, яотрэ вгсксуеться п прямоч'утния разворует) ¿ха. на под» споствр€,*эн)!я ^ . Таятся щмо'м, койне сло-го киадгсться !з с.ив -у*. пркчоиу иож прогляддтося,

ко в одному нэдрямку полл спостереяеикп, а п!д доз!дыш>1 ку-том е- («що с^ ="2" ; то називасться , трайспояохимлО. 51ч-до делка _{уящ1я /(¿'"^К Лц \

■ I = : жявачаз 2!дяоллешгя ! $1<кьтрзц!п

деяяо! частккк #><■!?> зобракекил об'екта, лка Шдпозддаз слову V , то з ргаул»тгт1 отрнхуеио початаове значения

^г-ац. Пр;1 №оиу = а^ . ,

Таким чином, гм1шжчя 5+-5, 1 к + к< .яомка сщяиати початаове зображиня об'етта ,пркпускакчи,а,о отрицания ко залогат» в!дЙ;^.Тод! загролоноваякй рая!па инструтаквшй алгоритм А/. а!дноалоиня ! корекцН зобратакия перетворпв-ться а узагалм'тн"'ТЯ паравел&нкЛ алгоритм в!дноалояия ! $1 ла-трзц! 5 зо5ра"м>!шя об'екта, цо допуская розпгралелйаання об-робяи !н$ор«ац!1 па задашму р!пн! корекцН , щ>тоыу час роал!азцП алгоритму' р1вга(Я часу реал5ззц!д функцП

коре«ц!1 I дозволяв аайеапечкти «асятаб реального часу.

При $ормувани! зображэння об'екта на пол! слосуережен-

ня la онремих слскент1в постр1чково алгоритм /j^.n.допускав wariCTpaльну обробку in$op«anii на задансму piimi корокцН, а ггрч аастосуваннi оператора рекурсй Я в¡и перетворюетбся в узагальнеюй маг1стралйний алгоритм J\cвздновлення i льтрацН зобраяення, цо допускае маГ1<лральну обробку in-форхзцИ ка заданому pisni корекцП, яка Еизначас час реа-Jiaaíji i алгоритму Д,i забелпочук масштаб реального часу.

Досл1д1т.гн1 частков! иппадки узагальнених паралелытх i üarlcTpajsbHK* алгорнты1в в!диовлення i фЗльтрацП аображень об "сита, а сама: паралельн! i маг1стральн1 алгоритми просто-рового Д)4ере»щ1кпаиня, просторового згладигувалня, nop¡ваяния з ©талоном i иореляцШН опсратори. Ц1 адгоритми aiflpia-

нянтъся -в1д розгдянутих p.ui i во олгориппв j¡c л i й0 м. функциями J-t як i вккоркстовуються i як i вланачадагъ в!дноалення i $ijo>tpaqík> зобраяеиь об'ехта. Вкзначено кдас Ал.н. паралель-ю« 1 ыаг1стралышх алгоритма для в»дновлення i ^¡льграцП вобралось oO'gutíb иа под» спостерелення.як! допусках^ ен-сокопрадуктивну обробку 1н$ор«ацЛ за допомого» паралельких 1 ыаг1стрдльких систеы.

Наведено'иаг1стральш1й алгоритм вид1лоння незв'язанних зображень об'бкта, в якоху в1добралена сучасна кокцепц1я об-роблм i рсзгНаьавашш слладния зобраяень o6'gktíij, котра полетав в току , чо складне аобралення под1ляеться на простí-и1, а оп1сдя анал1аусться взавмие.розгаауваяня окреиих об'-cxtíb. Анал1э взаеыорозтааувань дозволяе скластк Tpmtipmifl оияс скхуацН, представлений двомхрним складнлы зображен-еяы. Цей опкс стиидаеться з npoqecy ана»од*ения cnij&moc понтурнла Jiulft олреюк oó'gktíb, роанхтки вершин i aiHií , сб'едваты об'скт1в за принципом сп!лыоя оанал постр1чкаао5

грздацП якравост! РЯ^(к) для кожио! к -о! посл!довност! елемент!в -01 градацП якравост! на ¿-¡Л стр!чц! складного зображення об'ектчв, продстаменого ла пол! спосторсженач ¿р розПрн^стю П*1 деяюи ал$ав!том (р!вняни якравост!).Коя-на строчка зображения розбнвлеться на сегмент» РщООз посл!-довн1Сти р1В111В яскравост! 5 кожноиу з 15« сегментов стоиться у в!дпов!дн!сть список ознак РЯ^Ск) , утвориючн паря ?Лл елементами спискав ознак 1 посуНдоеност! р1зн!В ясиравост!. ТаК1 пари утворюмта из ко.таИЯ стр1чц1 зображення класи градаций якравост! ц!с1 строчки, як! в сукупност! |>орыутать мае ц!б1 стр!чкя. В свою черту, класи стр!чок утворюють сп!льшй. ялас поля спостерег-енкя. Сукупност! однаяовиж озная грздацП япфавсст! неаалеино в!д сегмента ! стр!чкл його акаходкеиня ^ормують списки уаагальнених оэнзк. Зд!#снки>чи посд1доеко пор!вияния озная и!л сегментами, стр1чяами за «ласами езнак 1 зам1нюйчм на основ! таиого пор!вкпяня списки озная уза-гальиеними ознакамд !з ал|>ав!т!в увагальнеюа озвая, отркму-емо маНстралыгий алгоритм внд!леиня нвзз'язшшзта аоСраиекв об'екта, в результат! обробяи поля спостереиэиия екни по кояному 13 об'ект!в розповсюдлуеться своя узагаланека самка, причому це розповсюдження в!дбуваеться одпочгено по ес!я ов'еятах. Таякй п1дя!д иояэ ефентнвно аастосовувазиса дга поперадньо! оСробяи зобравэкь сб'сят1п в системах розп1зна-ванна 1 шшжЗ!иаии. _

В четвертому роздШ представлено елементнй аайезпе-чеыня ООС, ей! по сут1 представляйте собой геоыетрично пра-вильну реш!тиу а ив иенш н!я двоыа в!сямн шшетрН.-у вузла$ яотро! розтаЕован! однотшш! даПркн.що валоя!я1ТЬ функц!о-жкьш 1 а'еднувальноя повиотоя.

- 16 -

. ОптммальнioTb аастоеуваяня ООС для створення спиц¡алi~ аогаддаы оЛчислм'гальних аасоб!», л тому чнсл! i для обробки зоОражскь, оОуксилена паролслыист» влнсишшя ' операций, nporp.-iWQC.1HiCTK! структури i К0НСГРУКЦ1Я1!0В ОДНОр1ДН1СТЮ, 40 в cykynnocrl аа£ч?апечу<7 виссхсу ее-чдпод!!« i ei'.nHoui'micn аларатурко! ретиПззцП цих aaccöiE.

В процес! створення елсмснтного забсзпечення ООС вра-яогувалгся загадай! в!докост! lipo структуру ООС га Ii осноз-нкх блолiв ; блоку додавала», блоку auiioi зиму числа, блоку п1дц!мЛ1ШЯ ,• блоку виД1Л0Ш!я модуля числа, блоку нноженна еосьмлротряд)на чисел в ИДЯ без розпаралалжзляия, блоку видения ы!н!магыю1 з дво* дксперсШ i в!дпои1дного $й. серо днь ого на ООС. ПршцилопиЯ г1дх1д до структур« ООО полягаз

■ . * в тому, к;э псггогш !н£ориацИ, яя! пода;уться на !н$ормац!Ян!

шсадм обчкслгаально! «owi'proi, оброблЗисться аг!дно з програ-иои^просупа»ч)!Сь п6сл1Доспо'п(д poxjpMi до ком!рки с ыатрмц! СОС. Эалди/ятоаукч! Koiiipioi забетпечусть абер!гаякя прои1я-кхсг результат!!! обчкеяень 1 погодтания тлдэгоа часовж !н-TtpaaiiB при обробц! валкая штж!в !к$орыацН.

Обадгушилыя огггоиа прац»с за принципом конвейера, ¿пай «я одному к1яц! а кояаюы тадтом аагаяталусться Цфэрыа-ц1си,а ßa Iimouy - п1дбуюсться розвантажуванпя отримаиогс результату обробки iinJopKauii.

В Ьскоау аяггсыя зандаден1 даа тили кои!рол: -обчнелвдилава , яка скзадасться а арифметика^-дог!чног< еркстроа (АНТ) ! кзпаду грагалтюп аз'язя!в для передач! in-{ормац!i без auiu;

- sanau'ятонукча у елгдяд! регистра а рогульовалоа догдашоа ЕР и! стать канал транзктюсс зв'гаШв.

• - 17 -

Обчислювальна ион ¡рил адатна гтриЯиати дан! а дпох 1а чотмрьох л ход i тс а<-ач, обробляти ix л АЛП i результат пере-даслти па один !з чотирьох виход!в é, ~ &ч . При неоОх¡дно-ctí мохтипл додаткова затрдаиа на один таит.

При розв'язку задач велико! розн!рност! для íctotiioto сксрочюшя числа вииористовувамих ком¡рок в програму вкличо-па оперт i ¡i "розштрешй транзит", виконання siw¡ пнлучае об-робку данях в МП 5 його вход» Еикористовуються в рол! до-даткових входiв транзита.

В п'яточу розд!л! досл!джсна рсаЛ!зац!я на 00С алгоритму ($5льтрац13 зобра»вння 1з збереженням контура. В цьому, алгоритм, як I в бпгатьох 1йши алгоритмах покращения якос-Ti зобраяень, иеобХ1Дно вид!ляти ~BiK«a" (п!дматриц1)' ia де-яко! 0CH0BII01 числовое матриц! зобраяення. Сл!д в!дм!тяти, що одночаска подача на плату ООО bcíx стр!чои матриц! зобра-ження призводить до суттбвнх , а на даному этапi розвнтку елементно! бази ООО, Ч до нездолашшх труднощ!в в рзал!ззцН деякнх алгоритм!в обробки зображень на ООО. Тому, в розгля-нутому випадку обробки ($!льтрацИ) аобраиен'ь !з абереяенняы контура натрнця зображення подаеться на входи плати 00€ пословно стр!чка за стр!чкон».

Алгоритм обробки зобращения паредбачае вид!лення а ей-х!д!Ю1 матриц! А зобратання розы!рц!ст>э 236x255 посл!довно-ст! Шдаатркць розм!рн!стм Бх5 аг!дно наступного принципу: для чергово! сукупност! п'ити стр!чои "bíkho" проглядае вс! стовпц! в!д першого по 256-й i на полному черговоку кроц! обробки асуваэться на одни стовпсць вправо. СунушИста 5-тн стр!чок, по закiнченкю обробки по стоящих, асуваеться на одну стр!чяу вниз'. 5 подальшоку, для коиного "в!кна" необ-

xiAiio шшонати наступи! Д1i .а) вийрати шмдко в!домого принципу 9 областей;

б) для кожно! облает! визначити середне значения i дисперсий;

в) вибрати найменшу д>;сперс1ю i в^дяоюдие для даио! дкс(юрс11 соредне значения iiOMicnmi на иiсцп- елемента, якиЯ стот на перелилi диагоналей матриц!.

Талям чином, ООО повинно бути'налаштоватм на виконан-ня д!й а) -- в) по' обробц» "nimia". "В£кна" почоргово вхо-дять в 00С 1 оОроблясться. Якщо елементи матриц! Я поступают* на плату (ХНУ одним основним потоком (ОП) поол!довно по crpi'iKax i представлен! в 16-гч розрядному модиф|кованому код! (ИВД, то для внд!леиня "в!нЬн" рвды]ptiicTio 5x5 над основного потоку при поступленн! в!дгалу»(увться 4 потоки: 0П2, 0(1 i, ОПv, Ofli ! затримуються в однор!дноху залам'ятоиувчому середошщ! в!дпов1дно на 2S6xlGx(^-l) такта, да (у =2,3,4,5)-ноыер потоку. ^

ОСИОВЯ1 РВЗУЛЬТАГИ РОБОТН

1. Досл!джена i влан^чена високопродуктивна обчиелн-вадьна система ларалельно! oöpoOroi !н$орыацН в реальному час! . та досл!джен! класи алгоритмов, як! грунтумться на ярусно-паралельному 1 наг1стральному принципах обробки !н-формац!i 1 допускать розпаралелюванпя па заданоку piBiü.

2. На ßaai !терац!Янмх методов розробдено алгоритм еконоиного i достав¡рнаго опису та обробки в реальному час! аоОражекь piatioi складност!, до реал!зуэтъся на 00С у виг ля-д! двом!рного рекурсивного $1Льтра.

- 19 -

3. Запропоновано та доиНдтсно иаг1СтральинЛ алгоритм вндЗлення.незв'яэанних зобрллень, що базуяться на подШ складного аобралення на прост! иi i aiiaJiiai рааеморопташувань окремих зобраиень в довольному напрямку; залропоновано уза-гальнений паралельний алгоритм i показана иожлшйсть його реал13ацП при обробц! зображень в сальному час!.

4. Реализовано на ООС алгоритм ^¡лбтрад!! аобраг-ення 13 збереженням контура.

Основн! положения дисертац1Яно1 робота опубликован! я' наступнях роботах:

1.Ватюк А.К.,1 Луцьт А;Ю., Пеленский А.Л. Конвейерная роалгаация пеевдомедианной обработки изображений / Пятая Всесокя.шк.-семинар " Распараллеливание обработки информации": Тез.докл. я сообщ. - Львов: Ста;-мех. им'. Г1. В'.Карпенко АЯ УССР,1985.- Ч.З. -С. 17-18.

2. Луцыя А. Ю.,'ПеленскиЯ А.Л, Настройка алгоритмов обработки иаображеккй на ОВС / Таи та. - С. 1Б-16.

3. Луцьи A'j».. Батвк A.B., Пеленсккй А.Л. Обработка изображений на базе мультиконвейерных вычислительных структур / Вторая Всесоюз.яонф. "Автоматизированные система обра-Сотки изображений (АСОИз-86)": Tea.докл. - Москва: Наука, 1936. - С. 276-277.

4. Батик t е., Луцын A.D., Пеленский А.Л.-Вычислителл-иая система для обработки телевизионных изображений на базе однородных вычислительных сред / Шестая Всесоюз. пк.-семинар " Распараллеливание обработки информации " : Tea.докл. и со-общ. - Львов: виз.-мех, ин-х им. Г.В.Карпенко АН УССР, 1987. - 4.2. - С. 4. '

- 20 -

I). ."yi;>>.h Д. Bl, Дуцьи O.A., Ислсис.мП А. Л. Параллельный подход к предварительпой обработке гасбрамниЯ /Там яе. - С.

fj. ПелсискиП А.Л., Луци( A.B., Дуцш O.A. Выделение фрагмента нлтрнцы изображенья пп Сапе однородны;; вычисли-•¡глым.'х сред / Третьи Всоеокз. ko»í . " Математические методы ралпознавалня обрплои (ÍÍJÍFO-III)" : Тез. докл.- Львои: £ю.~ иях. >пi-i т. Г.L\Карпенко ЛИ УССР,1ШГ7. - С.130-1Я7.

7. ПелепсмЛ Л.Л. Euctjií.Ií алгоритм выделения минимальной на двух дисперсий н соответствующего еЛ среднего /Там *о. - С. UV -11Ю.

В. ПвлпнсышП О.Д. Маг!стралы1иЯ алгоритм вид^лення нсав/ялалнх зоЯраяонь об'епта /Перса и!»лароднп конференция a iiiíopMrj(im»ix технологий i свстом (ITIC-93).- Т.1.- ЛьЕ1В: «i3.-Mex.in-t ¡м.Г.В.ГГарппнна ЛИ Уираiiw, 1G93.-С.Б5-БВ.

9. Пелонський 0.Л. УзагальнениЯ паралслмшЯ алгоритм в!дновлшшя 1 ф!льтрацП зобра'хень об'опта/Тая »e. - C.D9-G0.

ОгоГшспгЯ пнегок автора в отрицали i осношгах результата у прзцях, написания у сп1вгвторств1 :

- постановка задач! та роз робка алгоритму коквейерно! реал!зацП псевдоыед!ално! обробки аображень ti];

- розробка axropjrruiB обробки зобрлжень на ООС С23;

- постановка задач! побудови обчнелквально! систем« для обробки толев!з!йних зображень ! визначення piamix д!д-ход!в до розв'язку поставлено! аадач! t4]-,

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

метод!в С5];

- в роботах [3,6J авторн прийнили piBiiy таорчу участь.

ПеленскиЛ А. Л. Высокозйективныо алгоритмы и средства параллельного действия для обработки быстроноступамцих сигналов. Диссертация на соискание ученой степени кандидата технических наук по специальности 05.13.14 - системы обработки информации и управления, Фвико-механический ин-т ПАН Украины, Львов, 1934.

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

Pelen3kyj A.L. High-effective parallel algorithms and means for highspeed signal processing.

Thesi3 for recei"tne of scientific degree of candidate of engineering sciences at speciality 05.13.14- data processing and control systems, Physice-Mechanical Institute of

national Ukrainian Academy of Sciences, Lvlv, 1994..

* *

The high-effective algorithms and parallel specialized processors for image processing in real time haye been

deaicned and examined. The possibility of implementation of filtering alnorithW3 •»itli edco preserving on homogeneous computing structures have been investigated. The softvare and structural schemes for digital imago processing on honoccncous со input inn structures have been developed. The parallel specialized processors for TV signal processing based on the suncested alcorithra and structural schemes, which are used in real tire systems, have been designed.

'Ключов! слова ; оОробка снгнал1в, алгоритм, роапаралелквапня обчислень, ре-