Главная страница
Контакты

    Басты бет


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

жүктеу 65.28 Kb.



жүктеу 65.28 Kb.
Дата22.04.2017
өлшемі65.28 Kb.

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



ӘӨЖ 004.92

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


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


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

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

Құрал (Инструмент; лат. instrumentum - құрал, қару) - 1)адам еңбегінің құралы немесе өнеркөсіптік кәсіпорын жағдайындағы жұмысқа арналған машинаның атқарушы механизмі.
Интернет (оқылуы [интэрнэ́т]; ағылш. Internet - International Network) - компьютерлік серверлердің бүкіләлемдік желісі.
Ақпарат (лат. informatio - түсіндіру, мазмұндау) ұғымы күнделікті өмірден бастап техникалық салада пайдаланылатын көп мағыналы ұғым. Жалпы алғанда бұл ұғым шектеу, байланыс, бақылау, форма, инструкция, білiм, мағына, құрылым, бейнелеу, сезіну тағы басқа ұғымдармен тығыз байланысты.
Бейнелер негізгі үш ерекшелігімен сипатталады: мәтіндерге қарағанда сақтау үшін жадының барынша көп бөлігін қажет етеді; адамдардың көру қабілетіне бағытталған мәліметтің ерекше типі; текстік ақпараттарға қарағанда екі өлшемді болып келеді. Бейне сандық түрде көп бит санымен берілетіндіктен оның сақталуына көп орын қажет және жолдау кезінде жылдамдығы аз болады. Бұдан бейнелерді сығуға деген қызығушылық тұрақты түрде қарқынды дамып отыр.

Бейнені сығу дегеніміз – сандық түрде сақталатын бейнеге мәліметтерді сығу алгоритмін қолдану [3].

Бағыттау (орыс. наведение) - күштерге (сүңгуір қайықтарға, авиациялык ұшу аппараттарына) немесе қаруға (ракеталарға) козғалыс параметрлері (бағыт, жылдамдық, биіктік жөне т.б.) арқылы берілетін басқару тәсілі.
Алгоритм, алгорифм (ағылшынша: algorіthm, algorіsmus - Әл-Хорезмидің атынан шыққан) - бастапқы берілген мәліметтермен бір мәнде анықталатын нәтиже алу үшін қай амалды (жұмысты) қандай ретпен орындау қажеттігін белгілейтін есептерді (мәселелерді) шешу (математикалық есеп-қисаптар орындау, техникалық объектілерді жобалау, ғылыми-зерттеу жұмысын жүргізу т.б.)
Мәліметтер (данные; data) - автоматты құралдардың көмегімен, кей жағдайда адамның қатысуымен, өңдеуге I ыңғайлы түрде берілген мағлұмат. Мәліметтердің кірістік, шығыстық, басқару, проблемалық, сандық, мәтіндік, графикалық және т.б.
Сығу нәтижесінде бейненің өлшемі кішірейеді, сәйкесінше оны жолдау уақыты да азаяды, сақтауға қажетті жады көлемі үнемделеді. Бейнені сығудың екі түрін анықтайды: бейне толығымен қалпына келетін және қалпына келмейтін. Біріншісінің сығу коэффициенті өте аз, ол телевидениеде, медицинада, аэрофототүсірілімдерде қолданылады.
Медицина (лат. medicina: medicus - дәрігерлік, емдік) - адамдардың денсаулығын сақтау мен нығайту, сырқаттарды емдеу мен аурудың алдын алу, денсаулық және жұмысқа қабілеттілік жағдайында, адамзат қоғамында ұзақ өмір сүруге жетуді көздейтін тәжірибелік іс-әрекеттің және ғылыми білімдердің жүйесі.
Ал екіншісінің сығу коэффициенті бірнеше жүз есе болуы мүмкін. Вейвлет сығу әдісінің қолданыста өзекті болуы жоғарыда аталған екі түрінде де сәтті қолданылуымен байланысты.
Әдіс , метод (гр. 'μέθοδος',methodes зерттеу не тану жолы, бір нәрсеге жетудің жолы) - көздеген мақсатқа жетудің тәсілі, тәртіпке келтірген қызмет жүйесі. Әдіс философияда зерттелетін нәрсенің ойша нұсқасын жасау үшін қажетті таным құралы болып табылады.
Алайда, тізбекті жүзеге асу кезінде вейвлеттік талдау алгоритмі қажетті жылдамдыққа ие бола алмай отыр, бұл өз кезегінде бұл алгоритмнің деректерді нақты уақытта тізбекті өңдеуде қолданылуын қиындатады. Бұл мәселені шешудің негізгі жолы алгоритмді параллельдеу болып табылады. Параллельдеу әдісінің даму өзектілігі көпядролы және көпағынды технологияларды жүзеге асырушы микропроцессорлардың ауқымды және қарқынды дамуымен негізделеді [4].

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



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

Вейвлет дегеніміз – айнымалы сигнал мен бейне функциясын өңдейтін жаңа математикалық және практикалық аппарат [2].

Ресурстар (французша ressourse - құрал-жабдық, мүмкіндік), босалқы қорлар - табыс, ақшалай және басқа қаражат, құндылықтар мен олардың көздері.
Математика (гр. μάθημα - ғылым, білім, оқу; μαθηματικός - білуге құштарлық) - әлдебір әлемнің сандық қатынастары мен кеңістіктік формаларын, пішіндерін өлшейтін, оның ішінде - структуралар, өзгерістер, белгісіздік жөніндегі ғылым.
Математикалық тұрғыда бейнені x және y айнымалылары бар f функциясы ретінде қарастыруға болады. Осы f(x, y) функциясы жазықтықтың тіктөртбұрышты облысында анықталған делік. Сұр түстің градациясындағы суреттер екі өлшемді массив түрінде беріледі. Массивтің әрбір элементі осы суреттің пикселдеріне сәйкес келеді. Осылайша бейнені сығу процесі ендігі кезекте осы массив элементтеріне вейвлеттік түрлендіру және ықшамдау, кодтау амалдарымен анықталады.



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

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

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

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

  3. Декомпозиция: алынған екі өлшемді массивтің алдымен жолының, содан соң бағанының элементтеріне вейвлеттік түрлендіруіді жүргізу, вейвлеттік түрлендіруді бастапқыда берілген декомпозиция деңгейіне (сығу коэффициенті) дейін қайталау керек;
    ДЕҢГЕЙ (Уровень; layer, level) - абстракциялы дерексіздік дәреже; иерархиялық құрылым қабаты; осы желімен орындалатын белгілі бір мәселелер кешенін сипаттайтын есептеуіш желі қүрылымының логикалық қабаты,


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

  5. Кодтау;

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

  7. Декодтау;

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

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

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

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


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

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

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

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

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

Жинақ (Набор; set) - белгілі бір ақпараттық мазмұны бар логикалық байланыстағы объектілер жиыны.
Формула (Formula) - электрондық кестедегі (Excel) математикалық өрнек, оның жұмыс нәтижесі торлардағы мәндерге байланысты болады. Мысалы, D5 торына енгізілген мынадай формула =а5+b5+с5 A5, В5, С5 торындағы сандардың қосындысын D5 торына орналастырады.

Осылайша бастапқы бейненің өлшемі болатын аппроксимациясы келесі 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

  • Кіріспе
  • Бейнені сығуда вейвлеттік әдістерді қолдану
  • Бейнені вейвлет-сығудың параллельді әдісі
  • Қолданылған әдебиеттер

  • жүктеу 65.28 Kb.