Wavelet transformation: bestemmelse ansøgning eksempel

Fremkomsten af billige digitale kameraer har betydet, at en stor del af indbyggerne i planeten, uanset alder og køn, har erhvervet den vane at fange hans hvert skridt og lægge deres billeder på offentlig udstilling på de sociale netværk. Desuden, hvis den tidligere familie foto arkiv blev placeret i samme album, i dag består af hundredvis af billeder. For at lette lagring og transmission på tværs af netværk kræver et digitalt billede af vægttab. Til dette formål anvendes metoder, der er baseret på forskellige algoritmer, herunder en wavelet transformation. Hvad er det, fortæller vores artikel.

Hvad er et digitalt billede

Visuel information i computeren er repræsenteret i form af tal. I enkle vendinger, et foto taget med en digital enhed, er en tabel, hvor cellerne er indtastet værdierne for hver af dens pixel farve. Når det kommer til et monokromt billede, så de er erstattet af luminansværdier fra intervallet [0, 1], hvor 0 bruges til at henvise til sort, og 1 - hvid. Andre farver får fraktioneret numre, men med dem akavet at betjene, så området er udvidet, og den vælges fra intervallet mellem 0 og 255. Værdien Hvorfor er dette? Det er simpelt! Med dette valg i den binære repræsentation for kodning af luminansen af hver pixel kræver præcis én byte. Det er indlysende, at en masse hukommelse er nødvendig for at gemme endnu et lille billede. For eksempel billedstørrelse på 256 x 256 pixels tager 8 Kbytes.

Et par ord om billedet kompression metoder

Sikkert alle har set den dårlige kvalitet af billederne, hvor der er skævheder i form af rektangler af samme farve, som kaldes artefakter. De opstår som følge af den såkaldte kvalitetsforringende komprimering. Det kan reducere vægten af billedet, dog vil det uundgåeligt påvirke dets kvalitet.

For lossy komprimeringsalgoritmer omfatter:

• JPEG. Dette er langt en af de mest populære algoritmer. Den er baseret på brugen af diskret cosinustransformation. Retfærdigvis skal det bemærkes, at der er muligheder for JPEG udfører tabsfri komprimering. Disse omfatter Lossless JPEG og JPEG-LS.
• JPEG 2000. algoritme bruges på mobile platforme, og er baseret på anvendelsen af en diskret wavelet transformere.
• fraktal kompression. I nogle tilfælde er det muligt at få billeder af fremragende kvalitet selv med stærk kompression. Men på grund af problemer med patentering af denne metode fortsætter med at være eksotiske.

Tabsfri komprimering algoritmer udføres af:

• RLE (anvendt som den primære metode i TIFF-format, BMP, TGA).
• LZW (bruges i GIF-format).
• LZ-Huffman (bruges til PNG-format).

Fourier transformation

Inden jeg går til wavelet, giver det mening at udforske de relaterede funktioner, der beskriver koefficienterne i udvidelsen af de første oplysninger i elementære komponenter, dvs.. E. harmoniske svingninger med forskellige frekvenser. Med andre ord, Fourier transformationen - et unikt værktøj, der forbinder diskrete og kontinuerte verdener.

Det ser således ud:

Inversionen formel skrives som følger:

Hvad er en wavelet

Bag dette navn gemmer sig en matematisk funktion, som gør det muligt at analysere de forskellige frekvens komponenter af testdata. Dens graf er en bølgebevægelse hvis amplitude aftager til 0 væk fra oprindelsen. I almen interesse er de wavelet koefficienter bestemmes integreret signal.

Wavelet-spektrogrammer er forskellige fra konventionelle Fourier spektre, da forskellige træk associeret spectrum-signaler med deres tidsmæssige komponent.

wavelet transformation

Denne metode til signal konvertering (funktioner) gør det muligt at oversætte fra en gang i den tid-frekvens repræsentation.

At wavelet transformation var muligt for den tilsvarende wavelet funktion, skal følgende betingelser være opfyldt:

• Hvis en eller anden funktion ψ (t) -Fourier transformation har form

denne betingelse skal være opfyldt:

Desuden:

• Wavelet skal have en begrænset energi;
• det skal være integrable kontinuerlig og har kompakt støtte;
• wavelet skal være lokaliseret både i hyppighed og i tid (mellemrum).

typer

En kontinuerlig wavelet transformation anvendes til de respektive signaler. Meget mere interessant er dens diskrete analog. Efter alt, kan det bruges til informationsbehandling i computere. Imidlertid opstår der et problem, idet der ikke kan opnås formlen for en diskret fiberplade ved simpel passende diskretisering formler DNP.

Løsningen på dette problem blev fundet ved Daubechies, som var i stand til at vælge en metode til at bygge en serie af ortogonale wavelets, som hver især er defineret ved et endeligt antal koefficienter. Senere hurtige algoritmer blev skabt, såsom algoritmen Malla. I sin anvendelse til dekomponere eller at genoprette den nødvendige for at udføre operationer cN, hvor N - prøvelængde, og med - antallet af koefficienter.

Vayvlet Haar

For at komprimere et billede, er det nødvendigt at finde en vis regelmæssighed blandt sine data, og endnu bedre, hvis det vil være lange kæder af nuller. Det er her, det kan være nyttigt at wavelet transformere algoritme. Men vi fortsætter med at gennemgå de arbejdsmetoder i orden.

Først er det nødvendigt at huske på, at billeder lysstyrke tilstødende pixel normalt er kendetegnet ved en lille mængde. Selv om der er billeder på virkelige steder med skarp, kontrasterende forskelle i lysstyrke, de optager kun en lille del af billedet. Som et eksempel, overtage den kendte test Lenna gråtonebillede. Hvis vi tager en matrix af luminans af sine pixels, så den del af den første linje vises som en sekvens af tal 154, 155, 156, 157, 157, 157, 158, 156.

du kan anvende den såkaldte delta metode til at få nuller til det. For at gøre dette, holder kun det første nummer, og for de andre tage kun forskellene i hver af de foregående med tegnet "+" eller "-".

Resultatet er en sekvens 154,1,1,1,0,0,1, -2.

En ulempe ved delta-koder er dens ikke-lokalitet. Med andre ord, er det umuligt at tage kun en bid af sekvensen og finde ud af, hvad lysstyrke det er kodet, afkodes, hvis ikke alle af værdierne i foran ham.

At overvinde denne ulempe er antallet opdelt i par, og hver er halvdelen af summen af (v. A) og halvdelen af forskellen (v. D), m. F. For (154,155) (156,157) (157,157) (158,156) har (154,5, 0,5) (156.5,0.5) (157,0.0), (157, -1.0). I dette tilfælde er det altid muligt at finde værdien af de to tal i et par.

Generelt den diskrete wavelet transformationen af signalet S, har vi:

Denne fremgangsmåde følger af det diskrete tilfælde af kontinuerlig wavelet transformation, Haar og almindeligt anvendt i forskellige områder af databehandling og komprimering.

kompression

Som allerede nævnt er en af anvendelserne af wavelet transformation algoritme er JPEG 2000 komprimeringsmetode anvendelse Haar baseret på oversættelse vektor af to pixels i X- og Y-vektor (X + Y) / 2 og (X - Y) / 2. Det er tilstrækkeligt at multiplicere den oprindelige vektor i nedenstående matrice.

Hvis punkterne mere, tage mere matrix, som er anbragt på en diagonal matrix H. Derfor er den indledende vektor uafhængigt af sin længde forarbejdet i par.

filtre

Den resulterende "halv-sum" - er de gennemsnitlige luminansværdier af pixels i par. Det er den værdi, omregnet til billedet skal give ham en kopi, reduceret i 2 gange. I denne halve sum gennemsnit lysstyrke, t. E. "Filtreret" tilfældige byger af deres værdier og fungere som frekvensfiltre.

Lad os beskæftige sig med dem, der viser forskellen. De er "isoleret" interpixel "bursts", fjerne den konstante komponent, dvs.. E. "Filtreret" værdier ved lave frekvenser.

Selv fra ovennævnte Haar wavelet transformation for "dummies" bliver det indlysende, at det er et par filtre der opdeler et signal i to komponenter: den høje frekvens og lav frekvens. simpelthen genforenet disse elementer for at opnå det oprindelige signal.

eksempel

Antag, at vi ønsker at komprimere fotografiet (testbillede Lenna). Overvej eksemplet med wavelet transformation matrix pixel lysstyrke. Den højfrekvente del af billedet er ansvarlig for at vise fine detaljer og beskriver støjen. Som for den lavfrekvente, indeholder information om formen af ansigtet og glatte overgange af lysstyrke.

Funktioner billeder af den menneskelige perception er sådan, at sidstnævnte er mere vigtig komponent. Dette betyder, at når komprimeret kan kasseres en vis del af de højfrekvente data. Jo mere det, fordi det har mindre værdi og er kodet mere kompakt.

At forøge graden af sammentrykning kan anvendes flere gange Haar transformation til en lavfrekvente data.

Anvendelsen af todimensionale arrays

Som allerede nævnt, det digitale billede i computeren er i form af en matrix af intensiteterne værdier af dets billedpunkter. Derfor bør vi være interesseret i en todimensional Haar wavelet transformere. At gennemføre det nødvendigt blot at udføre sin dimensionelle konvertering for hver række og hver søjle i matricen af intensiteten af pixels i billedet.

Værdier tæt på nul, kan kasseres uden væsentlig skade på afkodede billede. Denne proces er kendt som kvantisering. Og i denne fase af oplysningerne går tabt. Af den måde, kan antallet af kan indeholde NULL faktorer ændrer og derved indstiller graden af kompression.

Alle disse trin resulterer i, at der opnås den matrix, der indeholder store mængder af 0. Det bør skriftlige linie for linie i en tekstfil og komprimere enhver arkiveringssystem.

afkodning

Den inverse transformation i billedet på følgende algoritme:

• Det udpakker et arkiv;
• anvender invers Haar transformation;
• De dekodede billede omdannes til en matrix.

Fordele i forhold til JPEG

было сказано, что он основан на ДКП. Når man overvejer algoritmen Joint Photographic Experts Group fik at vide, at den er baseret på DCT. Denne omdannelse udføres i blokke (8 x 8 pixels). Som et resultat, hvis en stærk kompression på det reducerede billede bliver mærkbar blok struktur. Under kompression ved hjælp wavelets sådant problem er fraværende. Dog kan der forekomme støj anden type, som har udseende af krusninger omkring kanterne. Det menes, at lignende artefakter i gennemsnit mindre iøjnefaldende end "firkanter", som er skabt ved brug af JPEG-algoritmen.

Nu hvor du ved, hvad wavelets er, hvad de er, og hvad praktisk brug for dem blev fundet i forbindelse med behandling og komprimere digitale billeder.