ӘӨЖ 004. 92 Бейнені вейвлет-сығУ Әдістерін тиімділеу



Дата03.05.2016
өлшемі65.3 Kb.
ӘӨЖ 004.92

БЕЙНЕНІ ВЕЙВЛЕТ-СЫҒУ ӘДІСТЕРІН ТИІМДІЛЕУ


Ташенова Д.К., Атейбекова Ш.Е.


Әл-Фараби атындағы Қазақ Ұлттық Университеті, Алматы
Ғылыми жетекші – Мансурова Мадина Есімхановна
Кіріспе

Қазіргі кезде есептеу техникасының, сандық байланыс құралдарының, Интернеттің дамуымен, қуаты мол компьютерлерінің кең таралуымен байланысты сандық бейнелер кеңінен қолданысқа еніп, әлемдегі ақпарат қорының үлкен бөлігін құрауда. Бейнелер негізгі үш ерекшелігімен сипатталады: мәтіндерге қарағанда сақтау үшін жадының барынша көп бөлігін қажет етеді; адамдардың көру қабілетіне бағытталған мәліметтің ерекше типі; текстік ақпараттарға қарағанда екі өлшемді болып келеді. Бейне сандық түрде көп бит санымен берілетіндіктен оның сақталуына көп орын қажет және жолдау кезінде жылдамдығы аз болады. Бұдан бейнелерді сығуға деген қызығушылық тұрақты түрде қарқынды дамып отыр.

Бейнені сығу дегеніміз – сандық түрде сақталатын бейнеге мәліметтерді сығу алгоритмін қолдану [3]. Сығу нәтижесінде бейненің өлшемі кішірейеді, сәйкесінше оны жолдау уақыты да азаяды, сақтауға қажетті жады көлемі үнемделеді. Бейнені сығудың екі түрін анықтайды: бейне толығымен қалпына келетін және қалпына келмейтін. Біріншісінің сығу коэффициенті өте аз, ол телевидениеде, медицинада, аэрофототүсірілімдерде қолданылады. Ал екіншісінің сығу коэффициенті бірнеше жүз есе болуы мүмкін. Вейвлет сығу әдісінің қолданыста өзекті болуы жоғарыда аталған екі түрінде де сәтті қолданылуымен байланысты. Алайда, тізбекті жүзеге асу кезінде вейвлеттік талдау алгоритмі қажетті жылдамдыққа ие бола алмай отыр, бұл өз кезегінде бұл алгоритмнің деректерді нақты уақытта тізбекті өңдеуде қолданылуын қиындатады. Бұл мәселені шешудің негізгі жолы алгоритмді параллельдеу болып табылады. Параллельдеу әдісінің даму өзектілігі көпядролы және көпағынды технологияларды жүзеге асырушы микропроцессорлардың ауқымды және қарқынды дамуымен негізделеді [4].

Зерттелген жұмыстың мақсаты бейнені сығу барысында уақытты және ресурстарды үнемдеу қажеттілігінен туындайтын бейнені сығу алгоритмін тиімділеу, яғни тиімді, әрі сапалы параллельді алгоритмді ұсыну, жүзеге асыру.



Бейнені сығуда вейвлеттік әдістерді қолдану

Вейвлет дегеніміз – айнымалы сигнал мен бейне функциясын өңдейтін жаңа математикалық және практикалық аппарат [2]. Математикалық тұрғыда бейнені x және y айнымалылары бар f функциясы ретінде қарастыруға болады. Осы f(x, y) функциясы жазықтықтың тіктөртбұрышты облысында анықталған делік. Сұр түстің градациясындағы суреттер екі өлшемді массив түрінде беріледі. Массивтің әрбір элементі осы суреттің пикселдеріне сәйкес келеді. Осылайша бейнені сығу процесі ендігі кезекте осы массив элементтеріне вейвлеттік түрлендіру және ықшамдау, кодтау амалдарымен анықталады.



Вейвлет-сығу әдісінің негізгі идеясы [1]. Бастапқы бейнеден алынған екі өлшемді массивтің алдымен жолдарына, содан соң бағандарына вейвлеттік түрлендірулер жүргізіледі, осылайша алынған екі өлшемді массив элементтерінен қандай да бір -нан кіші мәндер нөлге теңестіріледі, қалған коэффициенттерге кодтау жүргізілуі мүмкін. Сығылған бейне қажет болған жағдайда коэффициенттерді декодтау немесе алынған нәтижеге кері түрлендірулер жүргізу арқылы қалпына келтіріледі. Түрлендіру кезіндегі коэффициенттердің кейбір бөлігін жойғанда аса көп ақпарат жоғалмайды деп жорамалдаймыз, сондықтан вейвлеттер әдісі өте тиімді болып келеді [3]. Осылайша, жоғарыда аталған сипаттамаларды тиянақты түрде келесі тізбектелген алгоритмге жинақтайық.

Вейвлет-сығу әдісінің негізгі алгоритмі:

  1. Бейнені таңдау және жүктеу;

  2. Таңдалған бейнені екі өлшемді массив түріне ауыстыру;

  3. Декомпозиция: алынған екі өлшемді массивтің алдымен жолының, содан соң бағанының элементтеріне вейвлеттік түрлендіруіді жүргізу, вейвлеттік түрлендіруді бастапқыда берілген декомпозиция деңгейіне (сығу коэффициенті) дейін қайталау керек;

  4. Децимация: вейвлеттік түрлендіруге ұшыраған екі өлшемді массив элементтерін қандай да бір ε мәнімен салыстырып, одан кішілерін 0-ге теңестіру;

  5. Кодтау;

  6. Сығылған бейнені көру;

  7. Декодтау;

  8. Кері вейвлет-түрлендірулерін орындау;

  9. Декодталған бейнені алу;

Бейненің бастапқы түріне келуіне байлансты бейне толықтай қалпына келетін және толықтай қалпына келмейтін алгоритмдер болады. Сондықтан бастапқы және декодталған бейнелерді салыстыру керек. Жоғарыда сипатталған алгоритм көрнекі түрде 1-суретте толықтай бейнеленген.

1-сурет. Бейнені сығу процесінің жалпы сұлбасы.


Бейнені вейвлет-сығудың параллельді әдісі

Параллельді бағдарламалаудың негізгі мәселесі – деректерді процессорлар арасында дұрыс бөлу және оның параллельді бағдарламаның тиіділігіне әсері болып табылады [5]. Сондықтан уақыт бойынша ең жоғары жылдамдыққа жету үшін қарастырылатын ішкі есептерді дұрыс бөліп шығару қажет.

Таңдап алынған бейнені сипаттайтын өлшемі болатын квадрат матрица және і декомпозиция деңгейі берілсін делік. Сонда бастапқы бейнені вейвлеттік сығу алгоритмін процестерге бөліп, параллельді түрде өңдейміз. Бастапқыда әр процессор і деңгейіндегі бейненің вейвлеттік аппроксимациясы, сонымен қатар көлденең, тігінен және диагонал деталдары жөнінде ақпаратқа ие деп тұжырымдаймыз. Ұсынылған параллельді алгоритмнің негізі – квадробұталарды құруда, яғни белгілі бір декомпозиция деңгейінің қандай да бір төрт ішкі бейнелері өзара көршілес процессорлар арасында бөліп алынады. Төмендегі 2-суретте 2 деңгейлі декомпозиция кезіндегі бейненің 16 процессор арасында өзара бөлініп, орындалуы көрсетілген. Суретте көрсетілген нөмірлер әрбір ішкі суреттерді өңдейтін процессорлардың рангісін білдіреді.

2-сурет. Декомпозиция кезіндегі бейнені параллельді процестерге бөлу.

Есептеп келетін болсақ, әрбір процеске сәйкес келетін ішкі суреттің өлшемі болады. i=1 деңгейде әрбір процессор өзіне бөлінген ішкі суретке вейвлеттік түрлендіру жасайды, көршілес төрт процессордағы нәтижелер ранг нөмірі int(i/4)*4 формуласын қанағаттандыратын процессорға жинақталады, содан соң сыртқы көршілес төрт процессордағы нәтижелер ранг нөмірі int(i/16)*16 формуласын қанағаттандыратын процессорға жинақталады.

Осылайша бастапқы бейненің өлшемі болатын аппроксимациясы келесі i=2 деңгейге беріледі де, жоғарыда сипатталған процесс қайталанады. i=2 деңгейдің нәтижесінде бастапқы бейненің өлшемі болатын аппроксимациясы алынады. Нәтижесінде екі деңгейлі декомпозициядан бастапқы өлшемді суреттің өлшемді сығылған аппроксимациясы алынады. Осы идея бойынша децимация, кванттау және кодтау бөлімдерін де параллельдейміз. Жоғарыда сипатталған алгоритмнің жүзеге асуының жалпылама үлгісі:



Procedure Parallelization()

{ For (i=1; i<=; i++)

{ Decompozicia();

For (i=1; i<=; i++)

{ If ((rank mod =0) && (rank mod !=0)) Send_to( (rank/)*);

If (rank mod =0) { Receive rezults; Construct new rezult; }

}

}

If (rank!=0) Decimacia();

Koding();

}

Қарастырылып отырған параллельдеу алгоритмінің орындалуына кететін уақытты есептейтін болсақ, онда алдымен әрбір процессор өзіне бөлінген суреттерді түрлендіруге кеткен уақыт болса, сол сияқты децимация мен кодтауға кеткен уақыт . Егер кодсөздігі L сөзден тұрса, онда кванттауға кететтін уақыт болады. Демек параллельді бағдарламаның тізбекті алгоритмді барынша тиімділеп, уақыт үнемдейтіні анық.



Қорытынды

Қазіргі кезде вейвлет түрлендіру бейнені өңдеу және кодтау мәселелерінде, әр түрлі табиғат көріністерінде, беттік кристалдарды және нанообъектілердің қасиеттерін зерттеудегі көріністі тануда және көптеген басқа да жағдайларда кең қолданылады. Алайда, тізбекті жүзеге асу кезінде вейвлет-талдау алгоритмі қажетті жылдамдыққа ие болмай отыр, бұл өз кезегінде олардың деректерді нақты уақытта өңдеуде қолданылуын қиындатады. Демек, әдістің негізгі кемшілігі бейнені сығу кезінде есептеу ресурстарын және уақытты көп қажет етеді. Бұл мәселені шешудің негізгі жолы алгоритмдерді параллельдеу болып табылады. Ал бейнелерді бірнеше бөліктерге бөліп, параллельді түрде вейвлет түрлендіруін сол бөліктерге қолдану, уақыт пен ресурстарды үнемді пайдаланудың бірден бір жолы.



Қорта келе айтарымыз бейнелерді сығуда вейвлеттік идеялардың маңызы зор болып отыр. Осыған орай бейнені сығу алгоритмдерінің тиімділігін арттыру барысында параллельді есептеуді қолданудың бұл мәселені шешуде басты жол екенін атап өтейік. Бұл бізге ресурстарды үнемді пайдалануға, сығу процестерін жылдамдатуға мүмкіндік береді. Сол себепті де бейнелерді сығуда параллельді есептеуді қолдану кеңінен орын алып отыр.
Қолданылған әдебиеттер

  1. Уэлстид С. Фракталы и вейвлеты для сжатия изображений в действии. – Москва, 2003.

  2. Дьяконов В.П. Вейвлеты. От теории к практике. Москва, 2002.

  3. Воробьев В.И., Грибунин В.Г. Теория и практика вейвлет-преобразования. СПб., 1999.

  4. Акжалова А.Ж. Параллельные вычисления (учебное пособие). Алматы, 2004.

  5. Немнюгин С.А., Стесик О.Л. Параллельное программирование для высоко-производительных многопроцессорных систем. СПб., 2002.

  6. www.parallel.ru

Каталог: repository -> repository2012
repository2012 -> Шындалиева Меңдігүл Бұрханқызы бақ-тағы жарнама технологиясы
repository2012 -> Әож 811. 512. 122 3: 82. 091 Қолжазба құқығында тапанова сәуле есембекқызы қазақ романдарындағы ғашықтық сарын
repository2012 -> Махсат Алпысбес
repository2012 -> Білім саласындағы жаңа ақпараттық технологиялар
repository2012 -> Қаржаубай Сартқожаұлы, тарих ғылымының кандидаты, доцент, түрколог байырғы түркі «Ж» фонемі қАҚында
repository2012 -> Қазақстан республикасының білім және ғылым министірлігі
repository2012 -> Қ. Т. Қозыбаев, М. Н. Иманқұл Wimax технологиясы
repository2012 -> Қазақстан республикасы білім және ғылым министрлігі ministry of education and science of republic of kazakhstan


Достарыңызбен бөлісу:


©netref.ru 2019
әкімшілігінің қараңыз

    Басты бет