Wavelet transform: bestemmelse av anvendelseseksempel

Ankomsten av rimelige digitale kameraer har ført til at en stor del av innbyggerne i planeten, uavhengig av alder og kjønn, har kjøpt en vane å fange hans hvert trinn og sette sine bilder på offentlig visning i sosiale nettverk. Videre, hvis den tidligere familien bildearkiv ble plassert i det samme albumet, i dag består det av hundrevis av bilder. For å lette lagring og overføring over nettverk krever et digitalt bilde av vektreduksjon. For dette formål er fremgangsmåter anvendt som er basert på ulike algoritmer, inkludert en wavelet transform. Hva er det, forteller vår artikkel.

Hva er et digitalt bilde

Visuell informasjon i datamaskinen er representert i form av tall. Enkelt sagt, et bilde tatt med en digital enhet, er en tabell der cellene er angitt verdier for hver av sine pixel farge. Når det gjelder en monokrom bilde, da de er erstattet av lystetthetsverdiene fra intervallet [0, 1], der 0 er brukt for å referere til svart, og 1 - hvit. Andre farger er gitt brøk tall, men med dem vanskelig å betjene, slik at serien er utvidet og det velges fra intervallet mellom 0 og 255. verdi Hvorfor er dette? Det er enkelt! Med dette valg i den binære representasjon for koding av luminans for hvert bildeelement krever nøyaktig en byte. Det er åpenbart at mye minne er nødvendig for å lagre enda et lite bilde. For eksempel bildestørrelse på 256 x 256 piksler tar 8 Kbytes.

Noen ord om bildekompresjonsmetoder

Sikkert alle har sett den dårlige kvaliteten på bildene der det er skjevheter i form av rektangler av samme farge, som kalles gjenstander. De oppstår som et resultat av den såkalte lossy komprimering. Det kan redusere vekten av bildet, men det vil uunngåelig påvirke kvaliteten.

For lossy komprimering algoritmer inkluderer:

• JPEG. Dette er uten tvil en av de mest populære algoritmer. Den er basert på bruk av diskret cosinus transform. I rettferdighetens navn bør det bemerkes at det finnes alternativer for JPEG resultater tapsfri komprimering. Disse inkluderer Lossless JPEG og JPEG-LS.
• JPEG 2000. Algoritmen anvendes på mobile plattformer, og basert på anvendelse av en diskret wavelet transform.
• fraktal kompresjon. I noen tilfeller, det kan du få bilder av utmerket kvalitet selv med sterk kompresjon. Men på grunn av problemer med patentering av denne metoden fortsetter å være eksotisk.

Tapsfri kompresjonsalgoritmer som utføres av:

• RLE (brukt som den primære metoden i TIFF-format, BMP, TGA).
• LZW (brukt i GIF-format).
• LZ-Huffman (brukes for PNG-format).

Fourier transform

Før sin krusningen, er det fornuftig å utforske de beslektede funksjoner, som beskriver koeffisientene for utvidelse av den første informasjonen inn i elementær komponenter, det vil si. E. harmoniske svingninger med forskjellige frekvenser. Med andre ord, den Fourier transform - et unikt verktøyforbindelses diskrete og kontinuerlige verdener.

Det ser ut som dette:

Inverteringen formel skrives som følger:

Hva er en wavelet

Bak dette navnet skjuler det seg en matematisk funksjon, som lar deg analysere de ulike frekvenskomponentene i testdata. Grafen er en bølgeform hvis amplitude avtar til 0 bort fra origo. I generell interesse er de bølgeformkoeffisienter bestemt integral signal.

Wavelet-spektrogram er forskjellig fra konvensjonell Fourier-spektra, ettersom forskjellige trekk forbundet spektrumsignaler med sine tidsbestemte komponenten.

Wavelet transformasjon

Denne metoden for signalkonvertering (funksjoner) gjør det mulig å oversette fra en tid i tidsfrekvensrepresentasjon.

For å wavelettransformasjonen var mulig, for den tilsvarende wavelet-funksjonen, må følgende betingelser være oppfylt:

• Hvis en eller annen funksjon ψ (t) -Fourier omdanne har form

at tilstanden må være oppfylt:

I tillegg:

• Wavelet må ha en endelig energi;
• Det bør være integrable sammenhengende og har kompakt støtte;
• småbølge må være lokalisert både i frekvens og i tid (plass).

typer

En kontinuerlig wavelet transform blir brukt for de respektive signaler. Mye mer interessant er dens diskrete analoge. Tross alt, kan den brukes for informasjonsbehandling i datamaskiner. Imidlertid oppstår et problem ved at formelen for en diskret fiberplate ikke kan oppnås ved en enkel passende diskretiseringsintervaller formler DNP.

Løsningen på dette problemet ble funnet av Daubechies, som var i stand til å velge en metode for å bygge en serie ortogonale småbølger, som hver er definert av et endelig antall koeffisienter. Senere raske algoritmer ble skapt, som algoritmen Malla. I sin anvendelse til å dekomponere eller for å gjenopprette den nødvendige for å kunne utføre operasjoner N, der N - prøvelengde, og med - antallet koeffisienter.

Vayvlet Haar

Å komprimere et bilde, er det nødvendig å finne en viss regularitet blant sine data, og enda bedre hvis det blir lange kjeder av nuller. Det er der det kan være nyttig å småbølgetransformasjonen algoritmen. Men fortsetter vi å gjennomgå arbeidsmåter i orden.

Først er det nødvendig å huske at bildene lysstyrken av tilstøtende bildeelementer er vanligvis karakterisert av en liten mengde. Selv om det er bilder på ekte nettsteder med skarpe, kontrastfarge forskjeller i lysstyrke, opptar de bare en liten del av bildet. Som et eksempel, ta over kjente test Lenna gråtonebilde. Hvis vi tar en matrise av luminans av dens bildeelementer, da den del av den første linjen vil vises som en sekvens av tall 154, 155, 156, 157, 157, 157, 158, 156.

du kan bruke den såkalte delta metode for å få nuller til det. For å gjøre dette, må du bare det første tallet, og for de andre tar bare forskjellene i hver av den forrige med skiltet "+" eller "-".

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

En ulempe med delta-koding er av ikke-lokalitet. Med andre ord, er det umulig å ta bare en bit av sekvensen og finne ut hva lysstyrke det er kodet, dekodet, om ikke alle verdiene foran ham.

For å overvinne denne ulempe, er antallet delt opp i par, og hver er halvparten av summen av (v. A) og halvparten av differansen (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 tilfellet, er det alltid mulig å finne verdien av de to tallene i et par.

Generelt er den diskrete wavelet-transformasjonen av signalet S, har vi:

Denne fremgangsmåten følger av det diskrete tilfellet av kontinuerlig wavelet transform, Haar og mye brukt i ulike felt av databehandling og kompresjon.

kompresjon

Som allerede nevnt, en av de anvendelsesområder av wavelet-transformasjonen er den algoritme av JPEG 2000. Komprimer ved hjelp av en metode basert på Haar vektoren av de to bildeelement X og Y vektor (X + Y) / 2 og (X - Y) / 2. Det er tilstrekkelig å multiplisere den opprinnelige vektoren i matrisen under.

Hvis punktene mer, ta flere matriks, som er anordnet på en diagonal matrise H. Derfor er den opprinnelige vektoren uavhengig av dens lengde som behandles i par.

filtre

Den resulterende "halv-sum" - er den gjennomsnittlige lysstyrkeverdiene for bildeelementer i par. Det er verdien når de konverteres til bildet skal gi ham en kopi, reduseres i 2 ganger. I denne halv-summen gjennomsnittlig lysstyrke, t. E. "filtrert" tilfeldige støt med sine verdier og fungere som frekvensfiltre.

La oss nå forholde seg til de som viser forskjellen. De er "isolert" interpixel "bursts", fjerner den konstante komponenten, dvs. E. "filtrert" verdier ved lave frekvenser.

Selv fra den ovenfor Haar wavelet transform for "dummies" blir det åpenbart at det er et par av filtre som deler et signal i to komponenter: en høy frekvens og lav frekvens. simpelthen gjenforene disse elementer for å oppnå det opprinnelige signal.

eksempel

Anta at vi ønsker å komprimere fotografiet (testbilde Lenna). Tenk på småbølgetransformasjonen matrisen piksel justerer lysstyrken. Den høyfrekvente del av bildet er ansvarlig for å vise fine detaljer og beskriver støy. Som for den lavfrekvente, inneholder den informasjon om formen på den flate og jevne overganger av lysstyrke.

Funksjoner bilder av menneskets oppfatning er slik at sistnevnte er mer viktig komponent. Dette betyr at når den er komprimert en viss del av de høyfrekvente data kan kastes. Enda mer fordi den har mindre verdi er kryptert mer kompakt.

For å øke graden av kompresjon kan anvendes flere ganger Haar transformasjon til en lav-frekvensdata.

Anvendelsen av to-dimensjonale matriser

Som allerede nevnt, det digitale bildet i maskinen er i form av en matrise av intensiteter verdier av dens piksler. Derfor bør vi være interessert i en to-dimensjonal Haar wavelet transform. For å implementere er det nødvendig bare å utføre sin dimensjons konvertering for hver rad og hver rekke i matrisen av intensitetene av piksler i bildet.

Verdier nær null, kan forkastes uten betydelig skade på dekodede bilde. Denne prosessen er kjent som kvantisering. Og på dette stadiet av informasjon går tapt. For øvrig, kan antallet kan ha nullverdier faktorer forandrer seg, for derved å justere graden av kompresjon.

Alle disse trinnene resultere i at matrisen oppnås som inneholder store mengder av 0. Det bør være skrevet linje for linje i en tekstfil og komprimere noen arkivet.

dekoding

Den inverse transformasjon i bildet til følgende algoritme:

• Det pakker ut et arkiv,
• gjelder invers transform Haar;
• Den dekodede bilde omdannes til en matrise.

Fordeler sammenlignet med JPEG

было сказано, что он основан на ДКП. Når du vurderer algoritmen Joint Photographic Experts Group ble fortalt at det er basert på DCT. Denne omdannelse blir utført i blokker (8 x 8 piksler). Som et resultat, dersom en sterk komprimering på grunn av redusert bildet blir vesentlig blokkstruktur. Under komprimeringen ved hjelp av småbølger et slikt problem er fraværende. Imidlertid kan det oppstå støy annen type som har utseendet av krusninger rundt kantene. Det antas at lignende gjenstander i gjennomsnitt mindre merkbart enn "firkanter" som er laget ved bruk av JPEG-algoritmen.

Nå som du vet hva wavelets er hva de er og hva praktisk bruk for dem ble funnet innen behandling og komprimere digitale bilder.