Wavelet transformacija: definicija, primjena, primjer

Pojavom jeftinih digitalnih fotoaparata je značilo da je veliki dio stanovnika planete, bez obzira na dob i spol, stekao naviku do njegovog uhićenja svaki korak i staviti svoje slike na javno izlaganje u društvenim mrežama. Nadalje, ako je ranije obitelj foto arhiva stavljen u istom albumu, a danas se sastoji od nekoliko stotina fotografija. Kako bi se olakšala za pohranu i prijenos preko mreže zahtijeva digitalnu sliku smanjenje težine. U tu svrhu, metode se koriste da se temelje na različitim algoritmima, uključujući i wavelet transformacija. Što je to, naš će članak reći.

Što je digitalna slika?

Vizualne informacije na računalu predstavljaju brojeve. Jednostavno rečeno, fotografija snimljena digitalnom kamerom jest tablica u kojoj se upisuju vrijednosti boje svakog njegovog piksela. Ako govorimo o jednobojnoj slici, zamjenjuju se vrijednosti svjetline iz intervala [0, 1], pri čemu se 0 označava crnom bojom, a 1 je bijela. Preostale nijanse se daju u frakcijskim brojevima, ali s njima je i nezgodno raditi, pa se raspon proširuje i vrijednosti se biraju između intervala između 0 i 255. Zašto od toga? Jednostavno! Uz ovaj izbor, u binarnom prikazu, točno 1 bajt je potrebno za kodiranje osvjetljenja svakog piksela. Očito, pohranjivanje čak i male slike zahtijeva dosta memorije. Na primjer, veličina fotografije od 256 x 256 piksela će trajati 8 kB.

Nekoliko riječi o metodama kompresije slike

Sigurno su svi vidjeli slike slabe kvalitete, gdje postoje izobličenja u obliku pravokutnika iste boje, koji se obično nazivaju artefakti. Pojavljuju se kao posljedica takozvane gubitke kompresije. Može znatno smanjiti težinu slike, ali neizbježno utječe na njegovu kvalitetu.

Algoritmi sažimanja kompresije uključuju:

• JPEG. Trenutno je to jedan od najpopularnijih algoritama. Temelji se na primjeni diskretne kosinusne transformacije. U pravičnosti treba napomenuti da postoje varijante JPEG-a koji izvode komprimiranje bez gubitaka. To uključuje Lossless JPEG i JPEG-LS.
• JPEG 2000. Algoritam se koristi na mobilnim platformama i temelji se na primjeni diskretne wavelet transformacije.
• Fractal Compression Algorithm. U nekim slučajevima omogućuje vam dobivanje slika odlične kvalitete čak i kod jakog kompresije. Međutim, zbog problema s patentiranjem, ova metoda i dalje je egzotična.

Bez gubitka, kompresija se provodi pomoću algoritama:

• RLE (koristi se kao glavna metoda u formatima TIFF, BMP, TGA).
• LZW (koristi se u GIF formatu).
• LZ-Huffman (koristi se za PNG format).

Fourierova transformacija

Prije nego što se pretvara u wavelet, ima smisla istraživati ​​srodne funkcije, opisujući koeficijenata širenja početne informacija u osnovnim komponentama, tj. E. Harmonic vibracije različitih frekvencija. Drugim riječima, Fourierova transformacija - jedinstveni alat koji povezuje diskretne i kontinuirane svjetove.

Izgleda ovako:

Inverzna formula napisana je kako slijedi:

Što je to wavelet

Iza ovog naziva krije neku matematičku funkciju, koja vam omogućuje da analizira različite frekvencijske komponente test podaci. Njegov grafikon prikazuje valne oscilacije čija se amplituda smanjuje na 0 daleko od podrijetla. U općem interesu su wavelet koeficijenti određuju sastavni signal.

Waveletovi spektrogrami se razlikuju od običnih Fourierovih spektara, budući da povezuju spektar različitih signala sa svojom vremenskom komponentom.

Wavelet transformacija

Ovakav način pretvorbe signala (funkcije) omogućuje vam da ga prevodite od vremena do prikazivanja vremena i frekvencije.

Da bi se transformacija wavelet mogla omogućiti, za odgovarajuću funkciju wavelet moraju biti zadovoljeni sljedeći uvjeti:

• Ako je za neku funkciju psi- (t) Fourierova transformacija ima oblik

tada mora zadovoljavati sljedeće uvjete:

Osim toga:

• wavelet mora imati konačnu energiju;
• mora biti integriran, kontinuiran i ima kompaktni nosač;
• Wavelet mora biti lokaliziran kako u frekvenciji tako iu vremenu (u prostoru).

vrste

Kontinuirana valovita transformacija koristi se za odgovarajuće signale. Mnogo veći interes predstavlja njegov diskretni analog. Uostalom, može se koristiti za obradu informacija na računalima. Međutim, to uzrokuje problem da formule za diskretni DVP ne mogu dobiti jednostavno uzorkovanje odgovarajućih DNP formula.

Rješenje ovog problema pronašao je I. Dobesi koji je bio u mogućnosti odabrati metodu koja omogućava izgradnju niza takvih ortogonalnih valova, od kojih je svaki određen konačnim brojem koeficijenata. Kasnije su stvoreni brzi algoritmi, na primjer Mallov algoritam. Kada se koristi za dekompoziciju ili za oporavak, potrebno je izvršiti redoslijed operacija cN, gdje je N duljina uzorka, a c je broj koeficijenata.

Vaivlet Haar

Kako bi komprimirati sliku, potrebno je pronaći neki uzorak među svojim podacima, ili čak i bolje, ako je dug niz nula. Ovo je mjesto gdje algoritam wavelet transformi može doći u ruci. Međutim, nastavljamo razmatranje metode u cilju.

Prvo se morate sjetiti da se fotografije osvjetljenja susjednih piksela, u pravilu, razlikuju malom količinom. Čak i ako postoje područja s oštrim, kontrastnim razlikama svjetline na stvarnim slikama, oni zauzimaju samo mali dio slike. Kao primjer, uzmimo Lenninu dobro poznatu testnu sliku u sivim tonovima. Ako uzmemo matricu osvjetljenja njegovih piksela, dio prvog retka izgledat će kao niz brojeva 154, 155, 156, 157, 157, 157, 158, 156.

Da bi se dobili nula, na nju se može primijeniti takozvana delta metoda. Da biste to učinili, zadržava se samo prvi broj, a za ostale samo uzimaju se razlike u broju iz prethodnog broja s znakom "+" ili ";".

Rezultat je slijed: 154,1,1,1,0,0,1, -2.

Nedostatak delta kodiranja je njegov ne-lokalitet. Drugim riječima, nemoguće je uzeti samo dio sekvence i saznati koje su svjetlosti kodirane u njemu, ako sve vrijednosti koje se do njega ne dekodiraju.

Da se premoste mane, broj je podijeljen u parovima i svaki od polovica zbroj (v.) I pola razlike (v, D), m. F. Za (154.155) (156.157) (157.157) (158.156) imaju (154,5, 0,5) (156.5,0.5) (157,0.0), (157, -1.0). U ovom slučaju, to je uvijek moguće pronaći vrijednost dva broja u paru.

U općem slučaju, za diskretnu wavelet transformaciju signala S, imamo:

Ova diskretna metoda slijedi iz kontinuiranog slučaja Haar wavelet transformacije i široko se koristi u različitim područjima obrade informacija i kompresije.

kompresija

Kao što je već spomenuto, jedna od primjena wavelet transformirati algoritam je postupak kompresije JPEG 2000 koristeći Haar temelju prevođenja vektorom dva piksela u X i Y vektor (X + Y) / 2 i (X - Y) / 2. Dovoljno je da se početni vektor umnožiti u shemi koja slijedi.

Ako postoji više bodova, onda uzmite veću matricu s dijagonalnim matriksima H. ​​Dakle, izvorni vektor, bez obzira na duljinu, obrađuje se u paru.

filteri

Dobiveni "polumjeseci" su prosječne vrijednosti svjetline u pikselima piksela. To jest, vrijednosti prilikom pretvaranja na sliku trebaju dati njezinu kopiju, smanjenu za faktor 2. U tom slučaju pola suma prosječno osvjetljava, tj. "Filtrira" slučajne eksplozije njihovih vrijednosti i igraju ulogu filtara frekvencije.

Pogledajmo sada razlike. Oni "izdvajaju" interpeleskne "bursts", eliminirajući konstantnu komponentu, to jest "filtrira" vrijednosti s niskim frekvencijama.

Čak i iz gore navedenog Waveletove transformacije za "lutke" postaje očito da je to par filteri koji dijele signal u dvije komponente: visoku frekvenciju i nisku frekvenciju. Da bi se dobio izvorni signal, dovoljno je jednostavno kombinirati ove komponente.

primjer

Želimo komprimirati fotografski portret (testna slika Lenna). Razmislite o primjeru valne transformacije njezine matrice svjetline piksela. Visokofrekventna komponenta slike je odgovorna za prikaz malih detalja i opisuje buku. Što se tiče niske frekvencije, ona nosi informacije o obliku lica i glatkim promjenama svjetline.

Osobitosti ljudske percepcije fotografija su takve da je potonja komponenta važnija. To znači da se tijekom kompresije određeni dio visokofrekventnih podataka može odbaciti. Štoviše, ima manje vrijednosti i kodiran je kompaktnijim.

Da biste povećali omjer kompresije, možete primijeniti Haar transformaciju nekoliko puta na niskofrekventne podatke.

Primjena na dvodimenzionalne polja

Kao što je već spomenuto, digitalna slika u računalu predstavljena je kao matrica vrijednosti intenziteta njegovih piksela. Zato bi trebali biti zainteresirani za dvodimenzionalnu Wavelet transformaciju Haara. Da biste ga implementirali, jednostavno trebate izvršiti jednodimenzionalnu konverziju za svaki redak i svaki stupac matrice piksela piksela slike.

Vrijednosti blizu nule mogu se odbaciti bez značajne štete na dekodiranoj slici. Takav proces poznat je kao kvantizacija. I u ovom se stadiju neke informacije izgube. Usput, broj nulte čimbenika može promijeniti, čime podešavanje stupanj kompresije.

Sve opisane radnje rezultiraju matricom koja sadrži veliki broj 0. Treba ga napisati redak po redak u tekstualnu datoteku i komprimirati bilo koji arhiver.

dešifriranje

Obratna transformacija na sliku izrađuje se prema sljedećem algoritmu:

• arhiva je raspakirana;
• primjenjuje se inverzna Haarova transformacija;
• Dekodirana matrica se pretvara u sliku.

Prednosti nad JPEG

Prilikom razmatranja algoritma Zajednička skupina fotografskih stručnjaka rečeno je da se temelji na DCT-u. Ova se transformacija provodi blok-wise (8 x 8 piksela). Kao rezultat toga, ako je kompresija jaka, struktura blokova postaje vidljiva na obnovljenoj slici. Kada se komprimira pomoću waveleta, ovaj problem je odsutan. Međutim, mogu se pojaviti i druge vrste iskrivljenja, koje izgledaju kao valovi blizu oštrih rubova. Vjeruje se da su takvi artefakti u prosjeku manje primjetni od "kvadrata" koji se stvaraju pri primjeni JPEG algoritma.

Sada znate koji su waveletovi, što jesu, i koja je praktična aplikacija za njih pronađena u obradi i kompresiji digitalnih slika.