Wavelet transform: bestämning applikationsexempel

Tillkomsten av billiga digitalkameror har inneburit att en stor del av invånarna i planeten, oavsett ålder och kön, har förvärvat vana att fånga hans varje steg och lägga sina bilder på offentlig visning i sociala nätverk. Dessutom, om arkivet tidigare familjefoto placerades i samma album, idag består av hundratals bilder. För att underlätta lagring och överföring över nätverk kräver en digital bild av viktminskning. För detta ändamål är metoder som används som är baserade på olika algoritmer, däribland en wavelet transform. Vad är det, berättar vår artikel.

Vad är en digital bild

Visuell information i datorn är representerad i form av siffror. Enkelt uttryckt, ett foto taget med en digital enhet, är en tabell där cellerna in värdena för var och en av dess pixel färg. När det kommer till en monokrom bild, då de har ersatts av luminansvärden från intervallet [0, 1], där 0 används för att hänvisa till svart, och en - vit. Andra färger ges bråktal, men med dem besvärliga att använda, så intervallet förlängs och den valda från intervallet mellan 0 och 255. värde Varför är detta? Det är enkelt! Med detta val i den binära representationen för kodning av luminans för varje pixel kräver exakt ett byte. Det är uppenbart att mycket minne som krävs för att lagra ännu en liten bild. Till exempel bildstorlek på 256 x 256 bildpunkter tar 8 kbyte.

Några ord om bildkomprimeringsmetoder

Visst alla har sett den dåliga kvaliteten på bilderna där det finns störningar i form av rektanglar av samma färg, som kallas artefakter. De uppstår som en följd av den så kallade förstörande komprimering. Det kan avsevärt minska vikten på bilden, men kommer det oundvikligen att påverka dess kvalitet.

För förstörande komprimeringsalgoritmer inkluderar:

• JPEG. Detta är utan tvekan en av de mest populära algoritmer. Den är baserad på användningen av diskret cosinustransform. I rättvisans namn bör det noteras att det finns alternativ för JPEG utföra förlustfri komprimering. Dessa inkluderar Lossless JPEG och JPEG-LS.
• JPEG 2000. Algoritmen används på mobila plattformar, och bygger på tillämpningen av en diskret wavelet transform.
• fraktal kompression. I vissa fall, och hjälper dig att få bilder av hög kvalitet även med stark kompression. Men på grund av problem med patentering av denna metod fortsätter att vara exotiskt.

Förlustfria komprimeringsalgoritmer som utförs av:

• RLE (används som den primära metoden i TIFF-format, BMP, TGA).
• LZW (används i GIF-format).
• LZ-Huffman (används för PNG-format).

Fouriertransform

För roterande till wavelet, är det vettigt att utforska de relaterade funktioner, som beskriver koefficienterna i utvidgningen av den initiala informationen till elementära komponenter, dvs. E. harmoniska vibrationer med olika frekvenser. Med andra ord, Fouriertransformen - ett unikt verktyg som förbinder diskreta och kontinuerliga världar.

Det ser ut så här:

Inversions formeln skrivs på följande sätt:

Vad är en wavelet

Bakom detta namn döljer en matematisk funktion, som gör det möjligt att analysera de olika frekvenskomponenterna i testdata. Dess graf är en vågrörelse vars amplitud minskar till 0 bort från origo. I allmänhet intresse är de wavelet koefficienter bestämdes gralsignal.

Wavelet spektrogram skiljer sig från konventionella Fourier-spektra, eftersom olika funktioner associerade spektrumsignaler med deras temporala komponenten.

wavelet transformation

Denna metod för signalomvandling (funktioner) gör det möjligt att översätta från en tidpunkt i tid-frekvensrepresentation.

Att wavelet transformation var möjligt, för motsvarande wavelet funktion måste följande villkor vara uppfyllda:

• Om du av någon funktion ψ (t) -Fourier omvandla har formen

detta villkor måste vara uppfyllda:

Dessutom:

• Wavelet måste ha en ändlig energi;
• det borde vara integrerbar kontinuerligt och har kompakt stöd,
• vågkomponenten skall vara lokaliserad både i frekvens och i tid (utrymme).

typer

En kontinuerlig wavelet transform används för de respektive signalerna. Mycket mer intressant är dess diskret analog. När allt kommer omkring, kan den användas för behandling av information i datorer. Emellertid uppstår ett problem i det att formeln för en diskret fiberboard inte kan erhållas genom enkel lämplig diskretisering lerna DNP.

Lösningen på detta problem hittades av Daubechies, som var i stånd att välja en metod för att bygga en serie ortogonala wavelets, vilka var och en definieras av ett ändligt antal koefficienter. Senare snabba algoritmer skapades, såsom algoritmen Malla. I ansökan för att sönderdela eller för att återställa den erforderliga för att utföra operationer cN, där N - provlängd, och med - antalet koefficienter.

Vayvlet Haar

Att komprimera en bild är det nödvändigt att hitta en viss regelbundenhet bland sina uppgifter, och ännu bättre om det blir långa kedjor av nollor. Det är där det kan vara till nytta för wavelet omvandla algoritmen. Men vi fortsätter att granska de arbetsmetoder ordning.

Först är det nödvändigt att erinra om att bilder ljusstyrkan hos närliggande pixlar kännetecknas vanligtvis av en liten mängd. Även om det finns bilder på verkliga platser med skarp, kontrasterande skillnader i ljusstyrka, de upptar bara en liten del av bilden. Som ett exempel, ta över kända testet Lenna gråskalebild. Om vi tar en matris av luminans dess pixlar, sedan den del av den första raden kommer att visas som en sekvens av siffror 154, 155, 156, 157, 157, 157, 158, 156.

du kan använda den så kallade delta metod för att få nollor till den. För att göra detta, håller endast det första numret, och för de andra tar endast skillnaderna i var och en av den föregående med tecknet "+" eller "-".

Resultatet är en sekvens 154,1,1,1,0,0,1, -2.

En nackdel med delta-kodning är dess icke-ort. Med andra ord är det omöjligt att ta endast en del av sekvensen och ta reda på vad ljusstyrka den kodas, avkodas, om inte alla värden i framför honom.

För att övervinna denna nackdel, är antalet uppdelade i par och varje är halv av summan av (v. A) och halv skillnaden (v. D), m. F. För (154,155) (156,157) (157,157) (158,156) har (154,5, 0,5) (156.5,0.5) (157,0.0), (157, -1,0). I det här fallet är det alltid möjligt att hitta värdet av de två talen i ett par.

I allmänhet, den diskreta wavelet transform av signalen S, har vi:

Denna metod följer av det diskreta fallet med kontinuerlig wavelet transform, Haar och ofta används i olika områden av databehandling och komprimering.

kompression

Såsom redan nämnts, en av de tillämpningar av wavelet-trans algoritm är JPEG 2000 komprimeringsmetod med användning av Haar baserat på translationsvektorn av två bildpunkter i X- och Y-vektor (X + Y) / 2 och (X - Y) / 2. Är det tillräckligt att multiplicera den initiala vektorn i matrisen nedan.

Om punkterna mer, ta mer matris, som är anordnade på en diagonal matris H. Därför är den initiala vektorn oberoende av sin längd bearbetas parvis.

filter

Den resulterande "halv-sum" - är den genomsnittliga luminansvärden pixlar i par. Det är värdet vid omräkning till bilden ska ge honom en kopia, reduceras i 2 gånger. I denna halv-sum medelvärdes ljusstyrka, t. E. "Filtrerad" stickprovs skurar av deras värden och fungerar som frekvensfilter.

Låt oss nu ta itu med dem som visar skillnaden. De är "isolerad" interpixel "skurar", avlägsnande av konstant komponent, dvs. E. "Filtrerad" värden vid låga frekvenser.

Även från ovanstående Haar wavelet transform för de "attrapper" blir det uppenbart att det är ett par av filter som delar en signal i två komponenter: den höga frekvensen och låg frekvens. helt enkelt återförenas dessa element för att erhålla den ursprungliga signalen.

exempel

Antag att vi vill komprimera fotografiet (testbilden Lenna). Tänk till exempel på krusningstrans matrisen av pixelljusstyrkor. Den högfrekventa komponenten av bilden är ansvarig för visning av fina detaljer och beskriver bullret. Som för den lågfrekventa, den innehåller information om formen på ansiktet och släta gradienter av ljusstyrka.

Funktioner foton av mänsklig perception är sådana att den senare är viktigare komponent. Detta innebär att när komprimerad en viss del av de data som högfrekventa kan kasseras. Ju mer så eftersom det har mindre värde och kodas mer kompakt.

För att öka graden av komprimering kan appliceras flera gånger Haar transformation till en låg frekvensdata.

Användningen av tvådimensionella arrayer

Som redan nämnts, den digitala bilden i datorn är i form av en matris av intensiteter värden av dess pixlar. Därför bör vi vara intresserade av en tvådimensionell Haar wavelet transform. Att genomföra det är nödvändigt att helt enkelt att utföra sin dimensionsomvandling för varje rad och varje kolumn av matrisen av intensitet av pixlar i bilden.

Värden nära noll, kan kasseras utan nämnvärd skada på den avkodade bilden. Denna process är känd som kvantisering. Och i detta skede av den information går förlorad. Förresten, kan antalet nullable faktorer förändras, därigenom justera graden av komprimering.

Alla dessa steg resulterar i att matrisen erhålls som innehåller stora mängder av 0. Det ska skrivas rad för rad i en textfil och komprimera alla arkivet.

avkodning

Den inversa transformationen i bilden på följande algoritm:

• Det packar ett arkiv;
• applicerar invers Haar-trans;
• Den avkodade bilden omvandlas till en matris.

Fördelar jämfört med JPEG

было сказано, что он основан на ДКП. När man överväger algoritmen Joint Photographic Experts Group fick veta att den är baserad på DCT. Denna omvandling utförs i block (8 x 8 bildpunkter). Som ett resultat, om en stark kompression på den reducerade bilden blir märkbar blockstruktur. Under kompression med användning av wavelets sådant problem är frånvarande. Dock kan brus visas olika typer som ser ut som ringar runt kanterna. Man tror att liknande artefakter i genomsnitt mindre märkbar än "torg" som skapas när du använder JPEG-algoritmen.

Nu när du vet vad wavelets är vad de är och vad praktisk användning för dem återfanns inom bearbetning och komprimera digitala bilder.