Вэйвлетаў-пераўтварэнне: вызначэнне, прымяненне, прыклад

З'яўленне недарагіх лічбавых фотаапаратаў прывяло да таго, што значная частка жыхароў нашай планеты, па-за залежнасці ад узросту і полу, набыла звычку захоўваць кожны свой крок і выстаўляць атрыманыя выявы на ўсеагульны агляд у сацыяльных сетках. Акрамя таго, калі раней сямейны фотаархіў змяшчаўся ў адным альбоме, то сёння ён складаецца з сотняў здымкаў. Для таго каб палегчыць іх захоўванне і перадачу па сетках, патрабуецца памяншэнне вагі лічбавага малюнка. З гэтай мэтай прымяняюцца метады, заснаваныя на розных алгарытмах, уключаючы вэйвлетаў-пераўтварэнне. Што гэта такое, раскажа наш артыкул.

Што такое лічбавы малюнак

Візуальная інфармацыя ў кампутары уяўляецца ў выглядзе лікаў. Кажучы простай мовай, фота, зробленае лічбавым апаратам, уяўляе сабой табліцу, у вочкі якой ўпісаны значэння колеру кожнага з яго пікселяў. Калі гаворка ідзе пра манахромным малюнку, то іх замяняюць значэннямі яркасці з адрэзка [0, 1], дзе 0 выкарыстоўваюць для абазначэння чорнага колеру, а 1 - белага. Астатнія адценні задаюцца дробавымі лікамі, але з імі нязручна працаваць, таму дыяпазон пашыраюць і значэння выбіраюць з адрэзка паміж 0 і 255. Чаму менавіта з гэтага? Усё проста! Пры такім выбары ў двайковым прадстаўленні для кадавання яркасці кожнага пікселя патрабуецца роўна 1 байт. Відавочна, што для захоўвання нават невялікага малюнка патрабуецца даволі шмат памяці. Напрыклад, фатаграфія памерам 256 х 256 пікселяў зойме 8 Кбайт.

Некалькі слоў аб метадах сціску малюнкаў

Напэўна кожны бачыў здымкі дрэннай якасці, дзе прысутнічаюць скажэнні ў выглядзе прастакутнікаў аднаго колеру, якія прынята называць артэфактамі. Яны ўзнікаюць у выніку так званага сціску з стратамі. Яно дазваляе значна паменшыць вагу малюнка, аднак непазбежна адбіваецца на яго якасці.

Да алгарытмах сціску з стратамі адносяцца:

• JPEG. На дадзены момант гэта адзін з найбольш папулярных алгарытмаў. Ён заснаваны на ўжыванні дыскрэтнай косінуснай пераўтварэнні. Дзеля справядлівасці трэба адзначыць, што існуюць варыянты JPEG, якія ажыццяўляюць сціск без страт. Да іх ставяцца Lossless JPEG і JPEG-LS.
• JPEG 2000. Алгарытм выкарыстоўваецца на мабільных платформах і заснаваны на ўжыванні дыскрэтнай вэйвлетаў-пераўтварэнні.
• Алгарытм фрактальнай сціску. У некаторых выпадках ён дазваляе атрымліваць малюнкі цудоўнага якасці нават пры моцным сціску. Аднак з-за праблем з патэнтаваннем гэты метад працягвае заставацца экзотыкай.

Без страт сціск ажыццяўляюць з дапамогай алгарытмаў:

• RLE (выкарыстоўваецца ў якасці асноўнага метаду ў фарматах TIFF, BMP, TGA).
• LZW (ўжываецца ў фармаце GIF).
• LZ-Huffman (выкарыстоўваецца для фармату PNG).

пераўтварэнне Фур'е

Перш чым перайсці да разгляду вэйвлетаў, мае сэнс вывучыць звязаную з імі функцыю, якая апісвае каэфіцыенты пры раскладанні зыходнай інфармацыі на элементарныя складнікі, т. Е. Гарманічныя ваганні з рознымі частотамі. Іншымі словамі, пераўтварэнне Фур'е - унікальны інструмент, які злучае дыскрэтныя і бесперапынныя светы.

Яно выглядае так:

Формула звароту запісваецца наступным чынам:

Што такое вэйвлетаў

За гэтай назвай хаваецца матэматычная функцыя, якая дазваляе прааналізаваць розныя частотныя кампаненты доследных даных. Яе графік ўяўляе сабой хвалепадобныя ваганні, амплітуда якіх памяншаецца да 0 удалечыні ад пачатку каардынатаў. У агульным выпадку цікавасць уяўляюць вэйвлетаў-каэфіцыенты, якія вызначаюцца інтэгральным пераўтварэннем сігналу.

Спектрограммы Wavelet адрозніваюцца ад звычайных спектраў Фур'е, так як звязваюць спектр розных асаблівасцяў сігналаў з іх часовай кампанентай.

Вэйвлетаў-пераўтварэнне

Такі спосаб пераўтварэння сігналу (функцыі) дазваляе перакладаць яго з часовага ў частотна-часовае ўяўленне.

Для таго каб вэйвлетаў-пераўтварэнне было магчыма, для адпаведнай вэйвлетаў-функцыі павінны выконвацца наступныя ўмовы:

• Калі для нейкай функцыі ψ (t) Фур'е-пераўтварэнне мае выгляд

то павінна выконвацца ўмова:

Акрамя таго:

• вэйвлетаў павінен валодаць канчатковай энергіяй;
• ён павінен быць інтэграваныя, бесперапынным і мець кампактны носьбіт;
• вэйвлетаў павінен быць лакалізаваным як па частаце, так і ў часе (у прасторы).

віды

Бесперапыннае вэйвлетаў-пераўтварэнне выкарыстоўваецца для адпаведных сігналаў. Значна большы цікавасць уяўляе яго дыскрэтны аналаг. Бо ён можа выкарыстоўвацца для апрацоўкі інфармацыі ў кампутарах. Аднак пры гэтым узнікае праблема, звязаная з тым, што формулы для дыскрэтнай ДВП нельга атрымаць шляхам простай дыскрэтызацыі адпаведных формул ДНП.

Рашэнне дадзенай задачы было знойдзена І. Добеши, які змог падабраць метад, які дазваляе пабудаваць серыю такіх артаганальных вэйвлетаў, з якіх кожны вызначаецца канчатковым лікам каэфіцыентаў. Пазней былі створаны хуткія алгарытмы, напрыклад алгарытм Малах. Пры яго ўжыванні для разлажэння або для аднаўлення патрабуецца здзейсніць парадку cN аперацый, дзе N - даўжыня выбаркі, а с - лік каэфіцыентаў.

Вайвлет Хаара

Для таго каб сціснуць малюнак, варта знайсці пэўную заканамернасць сярод яго дадзеных, а яшчэ лепш, калі гэта будуць доўгія ланцужкі нулёў. Вось тут-то можа спатрэбіцца алгарытм вэйвлетаў-пераўтварэнні. Аднак працягнем разгляд метаду па парадку.

Спачатку трэба ўспомніць, што ў фотаздымкаў яркасць суседніх пікселяў, як правіла, адрозніваецца на невялікую велічыню. Калі нават на рэальных малюнках прысутнічаюць ўчасткі з рэзкімі, кантраснымі перападамі яркасці, то яны займаюць толькі малую частку малюнка. У якасці прыкладу возьмем усім вядомае тэставае выява Lenna ў градацыях шэрага. Калі ўзяць матрыцу яркасці яго пікселяў, то частка першага радка будзе выглядаць як паслядоўнасць лікаў 154, 155, 156, 157, 157, 157, 158, 156.

Для атрымання нулёў да яе можна ўжыць так званы дэльта-метад. Для гэтага захоўваюць толькі першае чысло, а для астатніх бяруць толькі адрозненні кожнага лікі ад папярэдняга са знакам «+» або «-».

У выніку атрымаецца паслядоўнасць: 154,1,1,1,0,0,1, -2.

Недахопам дэльта-кадзіравання з'яўляецца яго нелокальность. Іншымі словамі, немагчыма браць толькі кавалачак паслядоўнасці і высветліць, якія яркасці ў ім закадаваныя, калі не дэкадаваць ўсе значэння перад ім.

Для пераадолення гэтага недахопу колькасці дзеляць на пары і для кожнай знаходзяць полусумму (аб. A) і полуразность (аб. D), т. Е. Для (154,155), (156,157), (157,157), (158,156) маем (154.5, 0.5), (156.5,0.5), (157,0.0), (157, -1.0). У такім выпадку ў любы момант можна знайсці значэнне абодвух лікаў у пары.

У агульным выпадку для дыскрэтнай вэйвлетаў-пераўтварэння сігналу S маем:

Такі дыскрэтны метад выцякае з бесперапыннага выпадку вэйвлетаў-пераўтварэнні-Хаара і шырока выкарыстоўваецца ў розных галінах апрацоўкі і сціску інфармацыі.

сціск

Як ужо было сказана, адной з сфер прымянення вэйвлетаў-пераўтварэнні з'яўляецца алгарытм JPEG 2000. Сціск з выкарыстаннем метаду Хаара заснавана на перакладзе вектара з двух пікселяў X і Y ў вектар (X + Y) / 2 і (X - Y) / 2. Для гэтага дастаткова памножыць зыходны вектар на матрыцу, прадстаўленую ніжэй.

Калі кропак больш, то бяруць матрыцу пабольш, па дыяганалі якой размешчаны матрыцы H. Такім чынам, зыходны вектар незалежна ад сваёй даўжыні апрацоўваецца парамі.

фільтры

Атрыманыя «полусуммы» - гэта сярэднія значэння яркасці ў парах пікселяў. Гэта значыць значэння пры канвертаванні ў малюнак павінна даць яго копію, паменшаную ў 2 разы. Пры гэтым полусуммы усредняют яркасці, т. Е. «Адфільтроўваюць» выпадковыя воплескі іх значэнняў і гуляюць ролю частотных фільтраў.

Зараз разбяромся з тым, што паказваюць рознасці. Яны «вылучаюць» межпиксельные «воплескі», ухіляючы канстантнасцю складнік, т. Е. «Адфільтроўваюць» значэння з нізкімі частотамі.

Нават з прыведзенага вышэй хааровского вэйвлетаў-пераўтварэнне для «чайнікаў» становіцца відавочна, што яно ўяўляе сабой пару фільтраў, якія падзяляюць сігнал на дзве складнікі: высокачашчынную і нізкачашчынную. Для атрымання зыходнага сігналу досыць проста зноў аб'яднаць гэтыя складнікі.

прыклад

Хай мы хочам сціснуць фотапартрэт (тэставае выява Lenna). Разгледзім прыклад вэйвлетаў-пераўтварэнні яго матрыцы яркасцяў кропак. Высокачашчынная складнік малюнка адказвае за адлюстраванне дробных дэталяў і апісвае шум. Што тычыцца нізкачашчыннай, то яна нясе ў сабе інфармацыю пра форму асобы і плыўных перападах яркасці.

Асаблівасці чалавечага ўспрымання фотаздымкаў такія, што важней апошняя кампанента. Гэта значыць, што пры сціску пэўная частка высокачастотных дадзеных можа быць адкінутая. Тым больш што яна мае меншыя значэння і кадуецца больш кампактна.

Для павелічэння ступені сціску можна прымяніць пераўтварэнне Хаара некалькі разоў да нізкачашчынным дадзеных.

Прымяненне да двухмерных масіваў

Як ужо было сказана, лічбавы малюнак у кампутары прадстаўляюць у выглядзе матрыцы значэнняў інтэнсіўнасцей яго пікселяў. Такім чынам, нас павінна цікавіць хааровское двухмернае вэйвлетаў-пераўтварэнне. Для яго ажыццяўлення неабходна проста выканаць аднамернай яго пераўтварэнне для кожнага радка і кожнага слупка матрыцы інтэнсіўнасцей кропак малюнка.

Значэння, блізкія да нуля, можна адкінуць без істотнага ўрону для дэкадаваць малюнка. Такі працэс вядомы як квантавання. І менавіта на гэтым этапе губляецца частка інфармацыі. Дарэчы, лік обнулять каэфіцыентаў магчыма змяняць, тым самым рэгулюючы ступень сціску.

Усе апісаныя дзеянні прыводзяць да таго, што атрымліваецца матрыца, якая змяшчае вялікую колькасць 0. Яе варта запісаць парадкова ў тэкставы файл і сціснуць любым архіватарам.

дэкадаванне

Адваротнае пераўтварэнне ў малюнак вырабляецца па наступным алгарытме:

• архіў распакоўваецца;
• ўжываецца адваротнае пераўтварэнне Хаара;
• дэкадаваць матрыца пераўтворыцца ў малюнак.

Перавагі ў параўнанні з JPEG

было сказано, что он основан на ДКП. Пры разглядзе алгарытму Joint Photographic Experts Group было сказана, што ён заснаваны на ДКП. Такое пераўтварэнне ажыццяўляецца поблочно (8 х 8 пікселяў). У выніку, калі сціск моцнае, то на адноўленым малюнку становіцца прыкметнай блочная структура. Пры сціску з выкарыстаннем вэйвлетаў такая праблема адсутнічае. Аднак могуць з'явіцца скажэнні іншага тыпу, якія маюць від рабізны каля рэзкіх межаў. Лічыцца, што падобныя артэфакты ў сярэднім менш прыкметныя, чым «квадрацікі», якія ствараюцца пры ўжыванні алгарытму JPEG.

Цяпер вы ведаеце, што такое вэйвлетаў, якімі яны бываюць і якое практычнае прымяненне для іх знайшлося ў сферы апрацоўкі і сціску лічбавых малюнкаў.