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

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

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

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

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

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

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

1. 
   Бейнені таңдау және жүктеу;
   
2. 
   Таңдалған бейнені екі өлшемді массив түріне ауыстыру;
   
3. 
   Декомпозиция: алынған екі өлшемді массивтің алдымен жолының, содан соң бағанының элементтеріне вейвлеттік түрлендіруіді жүргізу, вейвлеттік түрлендіруді бастапқыда берілген декомпозиция деңгейіне (сығу коэффициенті) дейін қайталау керек;
   
4. 
   Децимация: вейвлеттік түрлендіруге ұшыраған екі өлшемді массив элементтерін қандай да бір ε мәнімен салыстырып, одан кішілерін 0-ге теңестіру;
   
5. 
   Кодтау;
   
6. 
   Сығылған бейнені көру;
   
7. 
   Декодтау;
   
8. 
   Кері вейвлет-түрлендірулерін орындау;
   
9. 
   Декодталған бейнені алу;
   

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

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

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

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

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

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

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

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

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

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

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

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

1. 
   Уэлстид С. Фракталы и вейвлеты для сжатия изображений в действии. – Москва, 2003.
   
2. 
   Дьяконов В.П. Вейвлеты. От теории к практике. Москва, 2002.
   
3. 
   Воробьев В.И., Грибунин В.Г. Теория и практика вейвлет-преобразования. СПб., 1999.
   
4. 
   Акжалова А.Ж. Параллельные вычисления (учебное пособие). Алматы, 2004.
   
5. 
   Немнюгин С.А., Стесик О.Л. Параллельное программирование для высоко-производительных многопроцессорных систем. СПб., 2002.
   
6. 
   www.parallel.ru