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



п г -1

, J на правах рукописи

МАКАРОВ ВЛАДИМИР АЛЕКСЕЕВИЧ

УДК 681.513

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

Специальности: 05.12.17 - радиотехнические и телсвкаиокные

системы и устройства; 05.13.13 - вмчжлителыше машины, комплексы, системы и сети.

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

Нгхтргя -

Работа выгЕХЯЕЭнз а Новгородской государстЕэнвок унизсрсствта

Кзучаыа руководакш» -диктор тезшшасхшх на?::, профзссор Екагьшов Г.й.

Офшгаазыаз ошювэшг:: доктор техитеасгш: каук, прзрссор -Нишряо А.П. кгвдещат -гагыгезсщг: наук, дгщзнт Еастггфьзв Е.Н.

Вадудай организация -Новгородские наугао-йсождовательскиз иастапут

госудэрствзяного университета ш адрэсу: 173001, г. Новгоро, уя. Большая С-Пзтербургскэя, 41.

С диссертацией кохсно ознакогакгься в бмЗдиотакз згннззрсигатз

Автореферат разослал **_" ноября 1983 г.

/

сакрэтард

ппог&шгэнЕого тэлэшдапкя 'РАСТР"

Зацитз диссертации состоятся 24 дэкабря 193Э года з 15 чаа на ьаседааш сжадашзкроаанвого совета K-iB4.32.QI Новгородскт

ОШМ HáPAHXEPKCTKKA РАБОТЫ

Актуальность теш. Смстош цвфровоя сбрзбопш изобргйиниа (COI©) образуат особый развивающейся иласо койпьзггарноа тэтакки. Интзрэс. npoaasi8f.!K3 к цкфровоа обработке чзсбравэша» ойьясяязтся там» что npzi cscasísi г.шо'.етстгз пржладап: ?здач в различных областях зпзнка такдазя 'лэфоряацйя шзтупгзт а зцеэ шобраганиз. В нгстолг,зэ зрзмя с^^тгвугат гзогочнслзяннэ возяохшосп! для разработан как ашаратаэго, так я программного ос'гсгтэтония СОйЗ.

Как празита» основу -лсбой ССй'З образует два фуЕЕцаояаяьныз б-изза: процэсеор,, срша-шргн-ЗЕхшя на ойргбатку нзс5ра*ен:в!, и спзцйазггаграз2Л1Хи& 3J . хщЕ^пзобрашпкй - пажш> кадров (Ш), котсрыэ в знзчшвльнсЗ кзрэ опрздг-ггпгг ттргйггэ.2ьс1суа цэнзость всвз сясгге?.(Ы. Пзглять кедров большшетаа COI23 рзгйкаготся на ssaspsrco газзшажжз блояк - (гграэз^А.

Аппаратура и )фограяш!та с&гагзчкнга» дадг^лпдэго числа СОЙЗ шдцэргзгет ps«c3v5 кэгда сбрабзтнзге»сз х-ззобрякэЕкэ rsssr формат в авскожнз раз кзцыта )з?йкзр2 стрг^-а™,, т.з„ адяа стрг£и*э тгзт хранить г^.скашю Езсфйй&ша Ьдаовргйзгэо. Б атаа cxriza яш реализация выпгкз.гэтзлнг-г: сро^зссоп обргботгн шеЯргкэнгта ргегта^з задачи распрздодгзяия пгяггга кадров кгззт ассДзгиость, которая ззгшгсаатсл в нэобгоданостя оярэдоэнкя еэ толыйз страница, ко , 8 ео фратвэкта дяя зраизветия кзебрагэЕвя,

В иастопщеэ врэня задача ^стгоэдадзния пзкггга кадров, с учетом прмвэдэнвоз особенности, не назлз до.ашого теорэти?есхшго ксаюдозазгпя. Дат. отэтвствэвЕых ССКЗ реизнкэ

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

Сисдозатагьно, очоээдвш дггеи шаыгэвкя гффэктависсга праязЕэиия СОйЗ кьештся разрагйпжз срэдств автояатазации распределения иааяти кздрэв, что позволит, Ео-пзраых, освободить погъзоват&хаа от шобжодаюсти поникать аппаратпаа тонкости рассжатривзешг систем. Во-аторыв, автойатизагрвя процэсса распрэдеаапЕЯ памяти кадров позвонит сукрственно снизкгь врзкя подготовки и отладь программного обзотэчония» освзбоадая при ътт пагьзо&зтгэг от функций дасдатч «фования пваята, с учэтса рэтавоз, когда обрабатавйэшэ йзобрззвэяия йяэнгг фаравт в ш сколько раз кеаьша разшра страницы.

Б постановке задачи, реагжоа в райках иастощза работа, ость ей© один важный асдакт свяганкна с непаяьзованша С05© прм проектировании систем тахшчэского зрзнкя (СТЗ) на зташ выбора алгоритмов. »Как пратнио, число алгоратюв рэ авизуемых коакрэтиой СТЗ фиксировано, позтоцу в процзссз е© создания, существует ■ реальная возможность рэшять вопрос о иннкаальноа чнота страниц ш&ятг кадцяв, трэбуеггл для рвзкэсгзкия обрабатываниях гообрашвка. Разработка програшаого обегазчання дасготчирования азгжгв СОйЗ, способного гашкжзЕраэать требуемую память кадров для хранения вгобратавагя, позволит ответить вг поставдэнЕШ вопрос.

Даль работы. Повьгшэнга эффективности использования СШЗ (в

«¡racraosra» в задэтаж прознгщювтая 013) за счаг разработка

средств готтггагппэщя распрэдэ.Еэкня шгктгя.

I

D качэетлэ осношого йрагорая зффэктпвяоетз выбрана врзшнная 0E33KS дакяштараяашя ГЕМпта гкдроз, зкзвьшгэкая за с^зт зэтспзтетжгй! гоакэдаа, в иэтаствэ' дотлшпяьаого критерия -

сто:"*зсть СГЗ, спеегэгзя за стгот кпнклезцкя числа страшщ nSîîîrnït дап гоггош'п изобразит®. Cczosaa езд:;Т' кссхэдозання. Для доспгзгил посташзнкоз в ^ссэртгкгзгесз petín-ni рзпзл-зь иэдзтт:

- гозтрзсзггэ формагьпой етдопз пют*:с.гйТольнсгй провеса

сйрьботкп кгсфкзака, орстзпфокнтсз на ргзребсггау еэтодся

рзспрэяэа>зЕЯ сшщггжз^рссггаоа пкита COIS;

- . paapriîcmta кзтодцэп угорпдотошк прзобрззовзшп

процессов обработки гасбр^-зшгч;

- GÎÎST3C што^лш спащ:агьной рзскрзатг-х Бэрэик гргфоз» всйвагпх^ои Езлучзть рпезшз гадзт:! тежяти тащроз С0;'3 с у^зтсм фрзггяиггпого рз:хгг:з;

разрешала црзцрацзссорз oäpaöaraa игсСрагэзка, -ппздагпсп^згагз лат сггск-этхззаорз працэсса создзкпя прясадаш: nporpsœ' CCD.

Е-этсщз В рнбото кспальзовапы кэтода тзории

гр~фсв„ теории сээп прогрела, тоорэтктоского програгзяфованкя, етста?лного прпгр^пгроваттл,гатода цифровой обработки изобрагэша.

Ноею нзупгьз рэз.удьтзта.. В проирссэ тсорзтэтосют пссыэдованкз падучаяи сгэдущо осЕаввкэ тучваз рэзультзты:

- прэдаггэпа кате:£стхгозская шдаль процэсса рзспрэдалэяич пейятя яэдроз» от&кйвсцаяся, во-гаршх, налгчкэа графа

шсокй8сгиности, что гоззаяяэт рзалкзозэть дцгсграуа' раскрась Ео-втарьп:, отсутстаг-о;: преойрзвовззЕН ' тша альтернйтсвз к ограничаназй числа декад, гчаотезет^я в ирэобрззованшс, что праводаг к ежегсзше) етспз , пзр^о/плгзгцгз: и построэкш пнфорнащютюго графа;

- усггалсзлЗЕН свамтэз щ^'.! ^славаэ' дэиустгаадстл гарэстааозки прзобраБОзаяЕЯ; достаточна условия спрзг2„-з^а;л ткаа ирзобр.аооБглг.л; усл)Бкк, пктюсть хргфа

аряЗразозаикй;

снзте&щэовакй изтодгсз упзргдочгЕкя преобразован:®»

0т-згс2шзяся учзтоы - трэе тепов пр&ойразовааз к шзболязщ5£и

есяшшггь ев процедуры упфадотаздия ЕрзаЗрззоззгня кзгзвпязщкз число зааятыг фрэикзв;

- разаЗотана католика дщуетрвог раскрзгкск. Практачэскзл цэшасть. На основа провздэнш! в работе нсотэдовг^га разработан прглродзссор обработки изображений дал сгздааисзврооагвоп) кокплзкса О'Л 1650, глзеесэ назначвнга которого состоих б автоматизации процэсеа рзспродагакия пзмятл кадров СОЮ и всзцо&ессти саздаш'л жш>зоьзта.яьс1си: прографи на языкз наксимашго приЗда&гэгноку к язьп;у Пгскаль.

■ Сгзггса^вал и практакзслк иссигэдэвгк алгоритм упорядочения прзоЗраэоБаЕИЕ Ш обработки: тсора.из^^*.

Вэаяазоьаш даа аагоригаг да^аэрзоа рзскрасии -вэршш графов. Разработано новее -¿-{ггрогстЕО ввода гр^япеског игфораадв;, обьэдангкщзз фукадз: якоестшй и сезтсааго шраг отдггсгззззея йозко^йсстьз удрзвлэннл ¡;ар:зрсг: ез гкрагз стгвдзртаого т&ззвкзиоеного цонш-ора баз гзнзрзцки ¡шгшрасгтрз в зоне огвзвшт

и гозволлэдээ опэративно опрздэлять размеры фрэзма.

Внедрэнта рэаультатов работы. Теорзткчвсккэ и практически результаты дассерггзцшнноа работы жпользукггся в НИ? "ВИДЕО", выполнкзгюа в ражках государстБвявого заказа НИИ П1 "РАСТР" г. Новгйрод, напраавэЕвоз на провктяраваниз и подготовку к серийному выпуску кокшгакса обработки ввдзосжзтов. .

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

- Координационное совещание ИСК "ййЗзрнонкка" РАН, секция ^Инфор^аткса4', г. Вадцаа, ишь 1993 г;

-Копфзрошдм стран СНГ "Рзспознзззшэ образов л анализ ИЗОбраЕЗНйЯи Г,!ЙЗКЖ, ЯОйбрЬ 1993 г.

- XV - XVIII область© научпо-твхшкэсхээ конференции, г.Новгород, 1330-1583 г.г.

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

Структура а объэз работы. Днссертацчсннзя работа содержит 142 страяадл капашспясного токста и вялгачззт введзнш, 5 глаз, заключение, списоц литература из 53 изккеновашш, 38 рисунков и 4 таблицы.

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

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

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

* л

Описанкакодали начкЕгзтся с толкования базисных гоеятнй, в терминах которых предполагается ваття рэшнш вадзчи нссдэдозавия.

Часть страницу, отводкиу» для ' хргшэтзя одного Езобраакзшгя, предлошво называть 4рейааа. ФрэШ! рассматривается сак элэиэнт памяти кадров, единица хранения игобрзЕЗЕШ.

Вычкйоггальныа протее (БП> . рассйатриваэтся • как послэдовапальность прэ образованна изображений, составдящкх едкяую задачу. ВП представляя орвэнтнрованнш графой: с = г/, л. . Здесь / - енойзетво ввришн-изобраюнт; а - инокйство дуг, обладающих тен свойством, что дуга ^ * J соединяет дав вершины в той, и только в ток случав, если одна из них соответствует исходному изобраявнио, а другая изображению - результату. Причем, ^ исходит из пэрзов и. ааходугг во вторую вераину. Граф С(1,л, вершины которого пронумерованы в соответствии с порядком выполнения преобразований, тфедидаэво называть графом преовразоваюЛ <ГП).

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

ДЖЯ V ^ т I , «ох {Й * 5 2 •

гдз а'о^) - тяустепень захода вераошы ^ ;

г"1 (г.) - неошство начал всех дуг, заходящих в.*. .

Каядая вэртина-изобрзжэниэ имеет своа интервал хранения ТХ^). Очевидно, что некоторая Берлина ¡г ноют принадлежать одноврэвэнйо нескольким интервалам хранения г в и .х «

2?(гр), т.е. интервалы хранения хч и хр пересекаются. Они не могут храниться а одной и том.к» фрейме ПК. Такиэ изображения принято называть еацвпленннт.

Графол аацегизний (ГЗ) назван неориентированный граф з= а, Н). Множество вершин I соответствует множеству объектов преобразований, а множество рзбэр В задает отношение зацепленности.

Аппаратные особенности реализации СОИЗ накладывают ограничения на доступ к памяти кадров: изображения одного и того яэ преобразования должны хранится в различных страницах ПК. Такие изображения предложено называть несовлестшши.

Граф тсобтстшюсш - шоркентираваныа ^ граф и^(Т.Е). Множество вершин I соответствует множеству объектов преобразований» а" любая, дуга б. передает отношение

несовместимости изображений одного преобразования.

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

В терминах модели основная задача настоящей работы - задача экономного распределения памяти кадров СОИЗ формулируется следующим образом. Наши такое допустимое отображен» « -. г -* ■ г

s

авгаззства йзобрзетнна l на нноеэстш, фрэгмэв р, при котором кодаость кноЕэства ¡у била ийеей&ешой.

На прааззрз доказано, что различные варианты парадка выползания преобразований одаого и того ¡аз БП, трзбуют раздачноэ кашязсггвй франков ПК для раззгзаэния вкдзодаЕЕкг, т.е. воЕМсана -етшкнггщя чксла фроакоз ©а счэт угорадошнгу? щ&обраговазяа.

Д&вээ показано, что в раккгж щаднотанног мода®!, рэазггз задачи распродавання такятк кадров, в конечной ктсгэ» сводятся к нахождэвмз специальной соглассванног раскрасхк графов ОСТ, К) а S( I. Н)ь заданных на постояебон нссеш-зэ .

Цзлъ рзскраскк 1/(1. ю - ЕазЕгчонкг каздруу жзобрзаэши) страницу, в которое сео будет храниться, шось раскраски zd.B) -опрздздэниэ ещэ нэ занятого фр&ева вазвотакноа страницу, зтвод£&»огс давд гратання зтстс кзобраззЕЕЯ. Прзвиааая ргскрасгш грзфоз Сиг» наползанная с учзтт® указанных особеЕвостаа,". названа ШударнаИ.

В заключении главы определяются этапы рзвення задачи акиноаного распродаж тая паияти кадров:

- гостроанкз .трафа прообразовал!®;

- упорядочена® граобразованна ВП;

- шстрсениэ графа весрзшспиости;

- тгярвэнив графа вацзпшнш;

- датнэраая раскраска;

- рвспрададавае нанята corjsscsa раскраска.

1рз ш праваменшг этапов: упорядочен*» преобразований игдаивггальваго процесса, госгровнш графа зацэпленнз, двукэраэп рэсэфасха, важно рэсскнтркватъ как сзжзстояталъяыэ частвью задачи

зюсаоинн панятн кадров, рэаатт ксторьос требует творэтктасгсгг нсслэдованиа.

Во зтороз главе исслэдузсггся два зтапа решэния задачи гксномии ПК: построение графов аассзкзстаяоста и упаряаэчагвэ преобразования вычислительного процесса. Рассиотрэны свсаетвз графа преобразование, на основе которых разработана *гэтодика упорядочения преобразования сьгетслгтголъзого пропэсса обработки изобракэзиа.

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

J, опрэдзлязгзэа граф зацзплэнка, сводятся к простая опзрадак: для v xk а г а. = 0 « ttni sup D<\)-l3

полошпъ' равными l.

Показано,что число фреанов F(O),которое потребуется для реализации любого БП равно

Г(в) -.«{Jelk} + 1.

i

где к - нокер столбца матрицы скешоеш С(2); ■ гдэ i - нокер стока матриш сгаешости C(Z).

Рассмотрены особенности a{j,j). Аргушнткрованно обосновано, что моделью в задаче упорядочения преобразования является корневой ациклический связный граф a{2.J)t такой что для v х. « I,

а&х S 2.

Формализована задача упорядочения преобразований ВП в терминах теории графов. Среди множества d" различных упорядочения ВП требуется найти такое чтобы fx <?) -- nin, т.е. для v А в [1,*], £ F(ffk>, где - множество всех допустимых

перестановок преобразований.

Показано,что в общем случае указанная задача является np • полное.

На осесвз обобщзния опыта ранения подобных задач, учитааа при этой особенности G( г, J), обоснована необходимость разработка более эффективной методики упорядочения преобразование.

О цвлье ешгеэз последней грздварительно рассмотрены свсзЬтв графа преобразований, вытенавдиа из ого особенностей.

Доказаны дао теореш и следствие покаэываяаркз, что разка иаксикальной клики графа прэобразований не прзвыигет 3, т.е

плотность »>(<?) £ 3 .

Теорема 1. Если d"(*.) для всех вершин графа с ограничена в

ТО ПЛОТНОСТЬ *>(G> í 2atl.

Следствие. Если d'fi^, для любой вершины графа - G( I ограничена в и в максимальной клике I' есть такая вершина ik, чт

r"(ik) « 1то ПЛОТНОСТЬ *><G) - 2га.

Теорема 2. Если дея всех вершт ациклического граф

£( I) ограничена m . то *>(<?) ¿ m+l. • ,

Формализовано условие допустимости ьерэстановк преобразований. Определены причины накопления памяти кадров сформулированы два правила упорядочения преобразований .

Доказаны свойства, тюзволяввэе построить процедуру выделен» на G(l,j) фрагментов максимального последовательного накошэни отнята.

Исследование упорядочения базируется на тон факте, что вс преобразования ВП можно разделить на три типа по их влияние в состояние памяти: преобразования, убехики&жщяэ число аакянь «рейяов (г*>; преобразования, w цзр?нят& ванта фрейме

(г°>; прзсбразсЗ&иА, уетшяагщш число эанятх фрэОлзв (г).

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

Опфаясъ на сфортужроваишгэ свойства ГП, разработана ¿emodtimi упорядочения преобразований ВП обработки изобразила, основные дзаетвия ютороа состоят в авэдуотрн:

1. Удалзшз кз ГП всех варшга-рэзультатов (вместе с зходящтш в них д/гаш) преобразований г°. тип- которых устанавливается одаозвачно, т.о. хшучиа ноша граф <f.

2. Нсхоздзнш в (f фрагмента(цепи) последовательного наясшэшк! к*. содэразщэго нш?болыауп последовательность прэсбразозашй типа г, т.е. приводяпззго к наибольшему сггЕоситэльноау увеличения числа занятых фреиаов.

3. Построен!» дерева преобразования Т((?). В качества корня T(tf) вьзбйргется гсорэнь (f. Среди кношства цетаа, связывавших корень и висячие вершин <f нэходан цэпь , которая содержит к'.Эта цэпь образует ствол T((f). Далэо для всех вэрвшн. соотвэтствуицда результатам бинарных npsобразованна (начиная с корня), находятся все пути до висячих Еэршш <?. Дзрово преобразований T«f) получается посредством удаданйя из каадоа ветви (исключая ствол) повторных рэбзр с еерданаяи, из которых они всходят!

4. Определение го , Tftf) нового порядка реализации преобразован«». Новыа порядок определяется так, чтобы при выполнении прэобразованяа У сбестачивался иинииуи занятости пшгята. ;;

Б. Изменение нумерации версии <f согласно нового порядка.

в. <f преобразуется вв.

Б_трвтьеа глава описала процедура построения графа несозмастиаости Е). Показано, что если все дуга ГП захэнкгь рзбраик а каждаэ две вэршины ^ к 1р в сох бинарных преобразований графа 0(1,-Л соединить ребром (если в <3 отсутствует дуга (х. ,1г)), то граф преобразования трансформируется в граф засовав стшоста.

Введено рЗщгз опрэдэлапга даукарнса раскраски.

ЛЗужрной раскраской графов иа,Е) и га,Н), задззныз. на постоянной Еосига© называется раскраска, прэдползг.ззсщая реализацию двух отобрамэник к: г—» о, : .г-* в'к',причем о = {<3'" }, к = ¡57?; в(к, = {&^}. 1 = 573. гдэ Р - количество красок, 5 -число оттенков каждое краски.

Элэненты иноаэства о называются и£еяали, элэмэнты множества е(к> предлошво называть отвнмаги ц&эта к. Отобралэта # определяет цвет вэршга Г посредством раскраски графа иа,К), отсбрэаенкэ ^ определяет оттенок цвета вершин / посрэдствсгя раскраски графа 2(1,Я), Число ншодихся в распоряжении красок определяется вырааэниэы &>(Р+1)- (5*1) к равно мощности кношства О.

Реализовать даукарнуэ раскраску манко двумя способами. Шрвыа способ - "все вершины - цвет, все вврцины - оттенок" предполагает гаслэдоватальноа шдалнетю отобраизнкй я^и . т.е. сначала раскрашивается все вэрвшы графа 0(1), затем все вершины графа 2(1).

Второа способ "вершина - цвет, оттенок" предполагает следушвэ действия, согласно правила перебора вершин, задаваемого алгоритмом раскраски, выбирается некоторая вершина «к « /.Сначала

спртлаляэтся çg цеот, затеи еэ оттенок и лишь потоя выбирается агедукдая ввретта /» Отображения заполняется параллельно. •

ИсоЕЗдовапы достоинства я недостатки обоет способов. Показано, что лучзшэ способ дзукэраоа распсрааш следует выбирать исходя из прэдваркгольнш: оцэнок зрокатягаеских чисел графов U(l) и га>.

Приводится соотназэниэ дая оценки зронатического числа по числу тарана - и, рзбэр - и, плотности ~ р:

(Ois x(ü) х s «it) Л(^г + i][ •>*> ] .

Доказано» что дая лабого грсфа азцэпяэнна Z(IU построенного для графа преобразований ad) Бэрао: -

t

гда *(Z) - хроватачвсксэ чнсл> Z(î)-. ctk - адазэнты затркоа

СЕЭЗНОСТП Z( I).

$ߣ89 в работе з заданы вэрпшэ грзтппзы оцвехи плотности грэфов г//;, vidi

•msSfr . * 9

TSß я - асетость носятмя хрэфоа иодел», .-каятоство вксячза

—^

* твэреиз su) .

Прздхатзвная Jsn&aSum Обулерной расхрасш сэодатся н *

сгэдушин дегггзяяя:

1. Определен® г (О) a x(Z>.

2. Выбор способа раскраски согласно правила: эсзя jxöo ш х(0)~р. либо x(Z)-k, то

а) набирается способ ""вез эврикны - цвет.вое в&рюшу -

оттенок"; если вах х(0> < р н х(2) < К, то Ь) выбирается способ "вершша - цвэт, оттенок".

За.. Посредством выбранного алгоритма раскрашивается 0(1),пря этой определяется требуемое количество цветов. Затем раскрашивается геи, определяется требуемое количество красок. Алгоритмы раскраски графов 0(1) и га) ногут быть основаны на различных правилах выбора раскрашиваемых вершин. Последнее действие раскраски - распределение красок га цветам и оттенкам, т.е. каждой вершине *к « I назначается цвет и оттенок.

ЗЬ. Исходя из предварительной оценка ж (О) и расчета *(2).выбирается граф, к которому применяется правило выбора вершин для раскраски. Используя выбранный алгоритм, реализуется двумерная раскраска, при этом каждой вершине хк « I одновременно назначается и цвет и оттенок.

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

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

иотрашу скешоста ГП. Бо-вгорьа:, на этапэ определэкия покров вэраин (шаг 7 кэтадззш упорядочения) необходим добавить проварку сеэдвяе^го условия: если достигнута начальная верзшна цвпи, образукп-ей тедэ г^ккла, тогда прэяда упорядочения вершин зтоа пеш веоЗтодано упорядочить все цэш, вершины которых являптся прэдааки вэрзпн рассаатриззекои цэпи. Всэ остальные шаги кетодюш упорядочегия прзобраззаниа остается баз кзменета.

Даны ноше спрэдэлэния ГЗ и ГН, скорректированные с учетом новых трзбоваякЯ дгя рассштриваеного случая Ш. Описаны праЕнла постороення графэ зацэшэнкй и графа не совместимости для случая БП с цшслвяи.

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

Разработан и описан способ расяредолэння пааяти для случая ВП со счэтчякани.

В пятой главе обоснована веобходивоеть создания специализированного программного обеспечения кршмэксов ' обработки изображение. Расснотревы два основных подхода к разработке систеявого програшного обэстаченкя ООО. Первые подход предоолаггат создаата сшщгализярованяото яанка, аторса раснирэниэ о&гшшг алгоршгагасиа: языков ее счет введения ахггтетствуаднх типов данных (иаобрввакга, од»).

Цракпгаата бззоа - для апробирования результатов

теоретических исследований настояаэй работы является ате^стпзнная СОШ СМ 1650. Показано, что в случзэ использования Ш31 Ш 1650 наиболее эффективным средством автшаткзацан програшфовгяия является препроцессор обработки игоСраззшй.

Разработанный препроцессор обработки изобра«»е121 состо;гг из слодухя(йх основных фушсционалышх кодалза: селзкторп, лзкскчзского анализатора, ринтаксичэского ангхззатсрз гг. генератора исходаоз программы для Пгскаль-кошалятора.

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

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

Сштксический анализатор распознает иакроинструкцяи как языковые конструкции, описываемые грашатикоа. Анализ построен по методу рекурсивного спуска. Синтаксический анализатор обеспечивает пдаобрэзовзние инфиксной формы записи в суффиксну».

в

Геащхггор ксзодяоз Шсаагь-прогргжы прэдлаггегяого прзпроцэссорз вугшппзг» гхееншя обрззса, jfo функций: замэнкэт расшзнЕаЕнэ нптогшструкща соотезтствущши .«акроопрэ^^энкгаш a рзогзэугт ргсхрзлрлзжп пгззята кадров.

Особенность какрогвгарэциа состоит в тон, с цэлья ускорэнда

ПрОХРЯура iiEXpOTQIiapSIiKH СфОрЭфОЕаПЫ ПЗЗЛОДЫ МШфООПрЭДЭЛЗНИЗ.

Казуса паШзн ссдэракг веЗср прощцур соотватствущкх дэаствшва по

щягрз^гзфовгглиэ 1Ш1. Пгйлопы ^фоспрэдзгэнпа кз доступна шлъзовзтпз, Cm еезстэ с прзцэдарг^зх гэгярзща таблиц образуют спстэпнуа . В зткз случгэ нот гаобходкяости к&зть тела

иакгроопрэдэ^энка в петэдеоа прогргжз - они выбираются из бшЗлиотзкя тогда, когда это трзбуотсп в процесса работы срзцроцэссорз. В результата ежоеьссегага црэпроцэ ссора становится бохэв ухрбтл;,,

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

сфоргзу-щэоваЕи осноеныэ достоинства прэдогэнноз г'зтодикк зконогзм паиятк: то-сзрвья, автоматизация распрэдз.шикя пзиятя кадров СОШ вомногг.тг Бнз*гпт&гыто согфапггь врзия создашь прикяздаьк прэгргг.-?; во-втср^, за есзт ожсаяиоа прошдури ,зкопожи пзмяти в рздэ сдггзвв удзэтся езкратять врзкя работа програ^п.

З^канчизгэтся глгзз S откесеяа структура я принцква работы спрозкткрованиого нового устройства гаггерзятишого счктывзяия координат, сбъэдшялхзв фушщки деозстяяз п свзтоваго пэра* отличгнззося ст кзвостньос вавжностьа и вогкот-зшетыз кспользо&аяня со стапдзртнъсг тэлавкзлонвы» кохпггорои. Устройство иенягг быть

кетшльзоБзн о дая ошратжЕого опрздзлзнш развэроз фрйгааа.

В ззклзчэнка нзлоигиг осеозннз научаю к йрзктцчзскнз результаты дцссартацлояЕоа рзбгга, еегзчзнн пгрсгактЕЕта налрггюпкя далывЕЕяг исслэдаваниг*

ОСЖЕННЕ РЕЗУЛЬТАТЫ ©!КЕР1АЦЕ0ШЮЗ РАЗОШ

х.Щзздужэеэ сзтвйатЕ'аская едезлъ ироазсса распрэдэлзЕия пзхлтй кадрог» отдичакгаяей, ЕО-горшг» наяичкз:г графа пзсоакэстхглостк, тго пзззелязт рэаизопзть даукэрнуп раскраску, Бо-вгарьк,. отсутсжза. преобразования ньята акьтараоткза п ограЕзгажк;;: чеслз дззныг, учьстьусз®. в преобразований*:, что приводят в искяячзниз зтапа нарзэутЕаедя: и пэетрозпка информационного гргфз.

2. УстзгоглзЕа СЕоастза К0ДЗЛК:

- у СЛОЕК» даОГС!К50СШ пэпзстггшкя ТфЗОбраООБаШЙ;

- достаточна условия спрздд^нкя •ляха прэобргзовгагл

- услэвкг.» огрзян=52згзг^ плотность Грефа пробрззосашЕ.

3.Схштвзкрозаай '»Г-тсда-:-. упорядочения прзебразаваннг, отлкчазоаяси у-гэгел трэз тшон прзебрззозанн: к позволянцаяя ксклшкгь кз процэд/ра упзридэчзщгл преобразования изйэкяяцкэ число занятье фрзейов.

4.Прэд2окзаа гзтодаха даугюрноа раскраски,

5.Рззрзботку црэпрох-зссора обработки кзсЗрааяшй для сизадагазирзвааных кошизксов обргЗатк^ взобреЕзни£, ¡прэдостаалязгэго возиоаность создания пряеппин* програшз на языка йзкешальао щнйазганнощу к языку Паскаль, отлетахщЁгсп егг

известных автоматизацией процэсса экономного распределения памяти

кадров в режиме фравн-обработки.

»

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

7. Разработаны два алгоритма двумерной раскраски верезга графов. Один из которых реализован согласно способу "все вершины -цвет, все - вершины оттенок", другой - согласно способу "вершина -цвзт.отганок*.

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

телевизионного монитора без генерации кихрорастра а зоне слежения

л

а поэволящее оперативно оправлять размеры фрзяяэ.

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

1.Гузсоп С.Л,, Макаров В.Л, Задача распрэдэлэния памяти кадров однопроцессорной системы обработка изображения, работзуялг в фрагсзентном рекию// Математическое иоделировзние и orv прилогэния: Ш>жвуз.сб./ HTM, Новгород, 1693. - 132 .с.

2.Макаров В.А. Модель и этапы рэвэвдя задачи распределения памяти, кадров СОЮ в рвжйо фрзвм-обргботки. / Новгородский политех-ш иа-т.. 1893.-14 с.-Дзп, В ВИШИ 16.04.93, й 1002. Ъ%\.

3. fiakarov V.A, Eoelyanov G.M. Optlalzatlon oi K»aory Distribution Ъу Orderini Coaputatlocal Tr an з f о г пл t ion г //Рл i t« г .-. Becognltioa osd Inoae Analysis. - V.3, n.<, 1893,- P.451-45Ö.

4. Макаров В.А. Задача экономного распределения гшилта кадров систем обработки изображений с архитектурой МИОД.// Распознавать образов и анализ изобрашний: Газ. докл. конфврэншш стран СНГ. -Минск, 1993.- С.77-78.

ь. Макаров В.А. Прзпроцассср обработки иэобрааепка для СМ 1650. // Распознавание образов и анализ изобракятейа: Тез. докл. ковфэрэшши стран СНГ.- Минск, ISÖ3-- С. 80-81,

6. A.C. СССР Я 1425738 . Устройство Для счнтав&шя графической информация с экрзна злоктроиво-лучевоа трубки/ Екзльяков Г.И., Гузеэв С.А., Макаров В.А. Заяалево 14.01.£77; Опубл. 23.09.83, Вал. & 35/ Открытая. Изобретения - КЗв.

7. A.c. СССР & I6I5758 . Устрс^стБЛ для спггаванкг. графической информации с экрзча азшстроняо-дучэвоя трубам/ Емельянов Г.М., Гузаэв С.А., Йакаров В.А., Красовскиа С.Н.Заявлено 03.01.89; Опубл. 23.I3.8C, Бал. й 47/ Открытая. Изэбрзтедкя -1990.