Discrete wavelet-transformaties.

12.3 Discreet wavelettransformatie-algoritme

Om een ​​discreet wavelet-transformatie-algoritme te construeren, introduceren we enkele lineaire transformaties. Laten we eerst en vooral de modulosom van getallen weergeven S als volgt: , en neem ook aan dat er een vector is waarin S zelfs. Vervolgens stellen we de geïntroduceerde transformaties als volgt:

,

voor iedereen. Het is duidelijk dat deze uitdrukkingen analogen zijn van hoogfrequente en laagfrequente filters (12.1), (12.2), waarbij rekening wordt gehouden met de periodieke optelling van gegevens met behulp van modulo-sommatie. Het is duidelijk dat transformaties de verdeling van de oorspronkelijke vector met lengte uitvoeren S in twee vectoren van halve lengte.

Het wavelettransformatie-algoritme komt dus neer op de implementatie van een iteratieve procedure van - en - transformaties die op de vector worden toegepast. Het resultaat van dergelijke transformaties zijn vectoren , benadering en detailcoëfficiënten.

Met andere woorden, recursief dit algoritme ziet er zo uit:

Merk op dat de geïntroduceerde notaties voor de expansiecoëfficiënten sterk lijken op de notaties voor de coëfficiënten, terwijl recursies (12.12), (12.13) vergelijkbaar zijn met het cascade-algoritme. Feit is dat de constructie van een discreet transformatiealgoritme volledig gebaseerd is op de theorie van discrete transformatie op de basis van waveletfuncties (zie de vorige paragraaf). Het belangrijkste verschil hier is het feit dat in statistische toepassingen de coëfficiënten slechts bij benadering overeenkomen met de uitzettingscoëfficiënten.

Merk op dat recursies (12.12), (12.13) met succes kunnen worden toegepast op de berekening van benaderings- en detailleringscoëfficiënten, ook voor gevallen: het feit is dat de uitgebreide reeksen periodiek zijn, en

,

.

Het inverse floppy-conversiealgoritme beperkt zich tot de implementatie van expressie (12.11), eveneens onderworpen aan periodisering van de gegevens. Het algoritme begint met vectorherstel

,

en gaat door totdat de vector is hersteld totdat dat niet het geval is. De recursieve uitdrukking voor gegevensherstel ziet er in dit geval als volgt uit:

12.4 Statistisch discrete waveletanalyse

Gegevenspartitionering

De berekening van waveletschattingen is dus gebaseerd op de hierboven beschreven discrete wavelettransformatie. Zoals is aangetoond, impliceert een dergelijke analyse het werken met gegevens waarvan de lengte gelijk is aan , waar NAAR- sommige geheel. In de praktijk blijkt de lengte van de onderzochte gegevens echter vaak niet gelijk te zijn aan een macht van 2, en daarom is het nodig om dergelijke gegevens uit te rekken naar een raster met gelijke afstanden met het aantal knooppunten. Het bovenstaande geldt zowel voor problemen bij het schatten van de distributiedichtheid als voor problemen bij het afvlakken van regressiegegevens.

Procedures voor het verdelen van gegevens in intervallen om de dichtheid te schatten regressie analyse geïntroduceerd in respectievelijk paragrafen 10.2 en 10.8. IN deze plek Het effect dat een dergelijke verdeling heeft op de kwaliteit van gesynthetiseerde schattingen wordt besproken. De voorbeelden die worden gebruikt om het effect te bespreken, zijn ontleend aan hoofdstuk. 10, afb. 10.1 - 10.11.

Bijvoorbeeld gegevens over lengte, het effect van het opdelen in intervallen bestaande uit punten wordt onderzocht. De integrale wortel-gemiddelde-kwadraatfouten bij het construeren van schattingen worden gegeven in Tabel 12.1.

Tabel 12.1

Integrale gemiddelde kwadratische fouten

voor gesplitste intervallen van verschillende lengtes

Zoals uit de tabel blijkt, bereikt de integrale standaardafwijking zijn minimum bij . De grafiek van deze fout wordt getoond in Fig. 12.1.

Ondanks het feit dat het voor dergelijke schattingen mogelijk is om te definiëren optimale maat interval moet men zeer voorzichtig zijn bij de statistische interpretatie ervan. Feit is dat het verdelen van gegevens in intervallen een soort voorlopige afvlakking is, waarmee in theorie vaak geen rekening wordt gehouden. Het is duidelijk dat naarmate het aantal partitie-intervallen toeneemt, de meest computationele efficiëntie van een snel algoritme. De punten die de RMSD-waarden tonen in Fig. 12.1 vormen een compromis tussen de snelheid van de schattingsberekening en de kwaliteit van de voorlopige afvlakking.

Geschatte constructie van waveletschattingen

Algoritme voor het implementeren van de discrete wavelettransformatie voor constructiedoeleinden statistische schattingen(12.6) - (12.8) ziet er als volgt uit:

Integrale standaardafwijking geconstrueerd voor het S8-symmlet

Laten we op dit punt een paar opmerkingen maken over het bovenstaande algoritme. Ten eerste omvat de definitie van een discrete transformatie het gebruik van gegevens die periodiek worden aangevuld bij elke stap van het algoritme. Met andere woorden: de gegevens zijn het resultaat van dyadische sommatie, waarbij de oorspronkelijke gegevens periodiek worden aangevuld Z zodat voor.

In de tweede plaats, zoals eerder benadrukt, hoogste niveau decompositie is niet betrokken bij het gegeven algoritme: in de praktijk wordt ervan uitgegaan, en worden drempelprocedures toegepast op de decompositiecoëfficiënten van alle niveaus, met uitzondering van het niveau K, die alleen benaderingscoëfficiënten bevat. Als echter wordt aangenomen dat uitzettingscoëfficiënten van niveaus hoger dan , zoals in het voorbeeld gebeurt met een lineaire waveletschatting, worden uitgesloten, wordt definitie (12.6) aangevuld met de voorwaarde:

.

Net als (12.3) kunnen acties 1 - 3 van het algoritme in matrixvorm worden weergegeven. Voor dit doel duiden we de vector van gegevens aan die worden bestudeerd door . Dan zal de directe transformatie de vorm aannemen:

waarin een operator van dimensie is. Dat is gemakkelijk aan te tonen deze exploitant is orthogonaal omdat het producten bevat van een eindig aantal orthogonale operatormatrices die overeenkomen met de verschillende stappen van het algoritme van Mull.

Laat de operator de vector-dorswerkprocedure aanduiden:

terwijl de inverse transformatie-operator , of is vanwege orthogonaliteit. Daarom is het resultaat van de opeenvolgende toepassing van acties 1 - 3, uitgedrukt door de vector , kan als volgt worden verkregen:

In het geval dat het probleem dat wordt opgelost de constructie is van een lineaire golfschatting en het niveau als niveau wordt genomen, wordt het geselen gereduceerd tot een identiteitstransformatie die uiteindelijk zorgt voor . Het punt is dat het behoud van de uitzettingscoëfficiënten op elk niveau in in dit geval maakt het mogelijk dat de uiteindelijke beoordeling louter de originele gegevens repliceert.

Vervolgens wordt het algoritme weergegeven door de stappen 1 - 3 algemene regel het maken van waveletschattingen. Merk op dat dit algoritme sneller is dan FFT, omdat het alleen bewerkingen vereist. Over het algemeen stelt het algoritme ons in staat gegevens te benaderen in plaats van te schatten. De uitzondering hierop is de ontleding van gegevens in een Haar-basis. Helaas wordt dit feit in de literatuur niet besproken.

Laten we even stilstaan deze kwestie iets meer details. Laten we voor dit doel eens nadenken lineaire schatting, zetten voor elke en k. Laten we er ook van uitgaan dat de brongegevens aan de eis voldoen:

.

(12.18)

Het is bekend dat recursie (12.9), (12.10) het mogelijk maakt schattingen van de coëfficiënten te berekenen, terwijl recursie-uitdrukkingen (12.12), (12.13) ongeveer dezelfde coëfficiënten zijn, ervan uitgaande dat de initiële gegevens voor de recursie absoluut de zelfde zijn. dezelfde. Als echter aan vereiste (12.18) wordt voldaan, verschillen de initiële gegevens voor (12.12), (12.13) in stap 3 van het algoritme met een bepaalde factor van de vergelijkbare omgekeerde recursiegegevens (12.9), (12.10). Bijgevolg brengt de lineariteit van het algoritme de noodzaak met zich mee om een ​​correctie in de directe transformatie te introduceren:

,

.

Bovendien is de belangrijkste uitdrukking voor directe conversie:

en de operator heeft de vorm:

Door uitdrukkingen (12.17) en (12.19) te combineren, kunnen we dat nu schrijven

De opkomst van goedkoop digitale camera's heeft ertoe geleid dat een aanzienlijk deel van de bewoners van onze planeet, ongeacht leeftijd en geslacht, de gewoonte heeft verworven om elke stap van hen vast te leggen en de resulterende beelden aan het publiek te tonen in sociale netwerken. Bovendien, als het familiefotoarchief voorheen in één album werd geplaatst, bestaat het tegenwoordig uit honderden foto's. Om de opslag en verzending ervan via netwerken te vergemakkelijken, is het noodzakelijk om het gewicht van het digitale beeld te verminderen. Voor dit doel zijn methoden gebaseerd op verschillende algoritmen, inclusief wavelettransformatie. Ons artikel zal u vertellen wat het is.

Wat is een digitaal beeld

Visuele informatie in een computer wordt weergegeven in de vorm van getallen. Spreken in eenvoudige taal, een foto gemaakt met een digitale camera is een tabel waarin de kleurwaarden van elk van de pixels worden ingevoerd. Als waar we het over hebben over een monochrome afbeelding, dan worden ze vervangen door helderheidswaarden uit het segment, waarbij 0 wordt gebruikt om zwart aan te geven, en 1 - wit. Andere tinten zijn gespecificeerd fractionele getallen, maar ze zijn onhandig om mee te werken, dus het bereik wordt uitgebreid en de waarden worden geselecteerd uit het interval tussen 0 en 255. Waarom precies hieruit? Het is eenvoudig! Met deze keuze erin binaire representatie Er is precies 1 byte nodig om de helderheid van elke pixel te coderen. Het is duidelijk dat het opslaan van zelfs een kleine afbeelding behoorlijk veel geheugen vereist. Een foto van 256 x 256 pixels neemt bijvoorbeeld 8 kB in beslag.

Een paar woorden over beeldcompressiemethoden

Iedereen heeft vast wel de foto’s gezien slechte kwaliteit, waar er vervormingen zijn in de vorm van rechthoeken van dezelfde kleur, die gewoonlijk artefacten worden genoemd. Ze ontstaan ​​als gevolg van zogenaamde lossy compressie. Hiermee kunt u het gewicht van de afbeelding aanzienlijk verminderen, maar dit heeft onvermijdelijk invloed op de kwaliteit ervan.

Verliezen zijn onder meer:

• JPEG. Op op dit moment dit is een van de meest populaire algoritmen. Het is gebaseerd op de toepassing van de discrete cosinustransformatie. Om eerlijk te zijn moet worden opgemerkt dat er JPEG-varianten zijn die verliesloze compressie bieden. Deze omvatten Lossless JPEG en JPEG-LS.
• JPEG 2000. Het algoritme wordt gebruikt mobiele platforms en is gebaseerd op het gebruik van discrete wavelettransformatie.
• Fractaal compressie-algoritme. In sommige gevallen produceert het afbeeldingen van uitstekende kwaliteit, zelfs met hoge compressie. Door patentproblemen blijft deze methode echter exotisch.

Lossless compressie wordt uitgevoerd met behulp van algoritmen:

• RLE (gebruikt als de belangrijkste methode in TIFF-formaten, BMP, TGA).
• LZW (gebruikt in GIF-formaat).
• LZ-Huffman (gebruikt voor PNG-indeling).

Fourier-transformatie

Voordat we verder gaan met het beschouwen van wavelets, is het zinvol om de bijbehorende functie te bestuderen, die de coëfficiënten beschrijft bij het ontbinden van de oorspronkelijke informatie in elementaire componenten, dat wil zeggen harmonische oscillaties met verschillende frequenties. Met andere woorden: de Fourier-transformatie is een uniek hulpmiddel dat discrete en continue werelden met elkaar verbindt.

Het ziet er zo uit:

De inversieformule wordt als volgt geschreven:

Wat is wavelet

Achter deze naam schuilt wiskundige functie, waarmee u de verschillende frequentiecomponenten van de onderzochte gegevens kunt analyseren. De grafiek geeft golfachtige oscillaties weer, waarvan de amplitude afneemt tot 0 weg van de oorsprong. IN algemeen geval Van belang zijn de waveletcoëfficiënten die worden bepaald door de integrale transformatie van het signaal.

Wavelet-spectrogrammen verschillen van conventionele Fourier-spectra omdat ze het spectrum met elkaar in verband brengen verschillende functies signalen met hun tijdscomponent.

Wavelet-transformatie

Deze methode voor het converteren van een signaal (functie) maakt het mogelijk om het te converteren van een tijdrepresentatie naar een tijdfrequentierepresentatie.

Om de wavelettransformatie mogelijk te maken, moet aan de volgende voorwaarden worden voldaan voor de overeenkomstige waveletfunctie:

• Als voor een bepaalde functie ψ (t) de Fourier-transformatie de vorm heeft

dan moet aan de volgende voorwaarde worden voldaan:

Daarnaast:

• de golf moet eindige energie hebben;
• het moet integreerbaar en continu zijn en een compacte drager hebben;
• De golf moet zowel in frequentie als in tijd (in de ruimte) gelokaliseerd zijn.

Soort

Voor de overeenkomstige signalen wordt een continue wavelettransformatie gebruikt. Zijn discrete analoog is van veel groter belang. Het kan immers worden gebruikt om informatie in computers te verwerken. Dit roept echter het probleem op dat formules voor discrete DWT niet kunnen worden verkregen door eenvoudigweg de overeenkomstige DWT-formules te discretiseren.

De oplossing voor dit probleem werd gevonden door I. Daubechies, die een methode kon selecteren waarmee men een reeks van dergelijke orthogonale golfjes kan construeren, die elk worden bepaald door een eindig aantal coëfficiënten. Later werden er snelle algoritmen gemaakt, zoals het algoritme van Mull. Wanneer het wordt gebruikt voor ontleding of reconstructie, is het noodzakelijk om ongeveer cN-bewerkingen uit te voeren, waarbij N de monsterlengte is en c het aantal coëfficiënten.

Wavelet Haara

Om een ​​bepaald patroon tussen zijn gegevens te vinden, en nog beter, als dit lange reeksen nullen zijn. Dit is waar het wavelet-transformatie-algoritme van pas kan komen. We zullen de methode echter op orde blijven houden.

Eerst moet je onthouden dat op foto's de helderheid van aangrenzende pixels in de regel een klein beetje verschilt. Zelfs als echte afbeeldingen gebieden bevatten met scherpe, contrasterende veranderingen in helderheid, nemen deze slechts een klein deel van het beeld in beslag. Laten we als voorbeeld de bekende Lenna-testafbeelding in grijstinten nemen. Als we de helderheidsmatrix van de pixels nemen, ziet een deel van de eerste rij eruit als een reeks getallen 154, 155, 156, 157, 157, 157, 158, 156.

Om nullen te verkrijgen, kun je er de zogenaamde deltamethode op toepassen. Om dit te doen, wordt alleen het eerste nummer opgeslagen en voor de rest worden alleen de verschillen van elk nummer met het vorige met een "+" of "-" teken genomen.

Het resultaat is de reeks: 154,1,1,1,0,0,1,-2.

Het nadeel van delta-codering is de niet-lokaliteit ervan. Met andere woorden: het is onmogelijk om slechts een deel van de reeks te nemen en erachter te komen welke helderheid daarin is gecodeerd, tenzij alle waarden ervoor zijn gedecodeerd.

Om dit nadeel te ondervangen, worden de getallen in paren verdeeld en voor elk vinden ze de halve som (vol. a) en het halve verschil (vol. d), d.w.z. voor (154.155), (156.157), (157.157), ( 158.156) hebben we (154,5, 0,5),(156,5,0,5),(157,0,0),(157,-1,0). In dit geval kunt u op elk moment de waarde van beide getallen in een paar vinden.

In het algemene geval geldt voor een discrete golftransformatie van een signaal S:

Zo een discrete methode vloeit voort uit het continue geval van de wavelet-Haar-transformatie en wordt veel gebruikt in verschillende gebieden verwerking en compressie van informatie.

Compressie

Zoals reeds vermeld is een van de toepassingsgebieden van de wavelettransformatie het JPEG 2000-algoritme. Compressie met behulp van de Haar-methode is gebaseerd op het omzetten van een vector van twee pixels X en Y in een vector (X + Y)/2 en (X). - Y)/2. Om dit te doen, volstaat het om de originele vector te vermenigvuldigen met de onderstaande matrix.

Als er meer punten zijn, nemen ze een grotere matrix, langs de diagonaal waarvan de H-matrices zich bevinden. De originele vector wordt dus, ongeacht de lengte, in paren verwerkt.

Filters

De resulterende “halve sommen” zijn de gemiddelde helderheidswaarden in paren pixels. Dat wil zeggen dat de waarde bij conversie naar een afbeelding een kopie ervan moet opleveren, verkleind met 2 keer. In dit geval middelen de halve sommen de helderheid, dat wil zeggen dat ze willekeurige pieken in hun waarden "uitfilteren" en de rol van frequentiefilters spelen.

Laten we nu eens kijken naar wat de verschillen laten zien. Ze ‘markeren’ interpixel ‘bursts’, waardoor de constante component wordt geëlimineerd, dat wil zeggen ze ‘filteren’ waarden met lage frequenties.

Zelfs uit de bovenstaande Haar-wavelet-transformatie voor dummies wordt het duidelijk dat het een paar filters zijn die het signaal in twee componenten verdelen: hoge frequentie en lage frequentie. Om het originele signaal te verkrijgen, volstaat het om deze componenten eenvoudigweg opnieuw te combineren.

Voorbeeld

Stel dat we een foto willen comprimeren (Lenna-testafbeelding). Laten we een voorbeeld bekijken van de wavelettransformatie van de pixelhelderheidsmatrix. De hoogfrequente component van het beeld is verantwoordelijk voor de weergave kleine onderdelen en beschrijft het geluid. Wat de lage frequentie betreft, deze bevat informatie over de vorm van het gezicht en vloeiende veranderingen in helderheid.

De eigenaardigheden van de menselijke perceptie van foto's zijn zodanig dat het laatste onderdeel belangrijker is. Dit betekent dat sommige hoogfrequente gegevens tijdens de compressie kunnen worden weggegooid. Bovendien heeft het kleinere waarden en is het compacter gecodeerd.

Om de compressieverhouding te vergroten, kunt u de Haar-transformatie meerdere keren toepassen op laagfrequente gegevens.

Toepassing op tweedimensionale arrays

Zoals al gezegd, digitaal beeld weergegeven in een computer als een matrix van de intensiteitswaarden van de pixels. We zouden dus geïnteresseerd moeten zijn in de tweedimensionale wavelet-transformatie van Haar. Om dit te implementeren hoeft u alleen maar een eendimensionale transformatie uit te voeren voor elke rij en elke kolom van de beeldpixelintensiteitsmatrix.

Waarden dichtbij nul kunnen worden weggegooid zonder noemenswaardige schade aan het gedecodeerde patroon. Dit proces staat bekend als kwantisering. En het is in dit stadium dat er wat informatie verloren gaat. Overigens kan het aantal resetcoëfficiënten worden gewijzigd, waardoor de compressieverhouding wordt aangepast.

Alle beschreven acties resulteren in een matrix die bevat groot aantal 0. Het moet regel voor regel worden geschreven tekstbestand en comprimeer het met een willekeurig archiveringsprogramma.

Decodering

De omgekeerde conversie naar een afbeelding wordt uitgevoerd met behulp van het volgende algoritme:

• het archief is uitgepakt;
• de inverse Haar-transformatie wordt toegepast;
• de gedecodeerde matrix wordt omgezet in een afbeelding.

Voordelen ten opzichte van JPEG

Bij het overwegen van het algoritme Gezamenlijke groep fotografische experts er werd gezegd dat het gebaseerd was op PrEP. Deze conversie gebeurt blok voor blok (8 x 8 pixels). Als gevolg hiervan, als de compressie sterk is, wordt de blokstructuur merkbaar in het gereconstrueerde beeld. Bij het comprimeren met behulp van wavelets bestaat dit probleem niet. Er kan echter een ander type vervorming optreden, namelijk als rimpelingen nabij scherpe grenzen. Er wordt aangenomen dat dergelijke artefacten gemiddeld minder opvallen dan de “vierkantjes” die ontstaan ​​bij het gebruik van het JPEG-algoritme.

Nu weet je wat wavelets zijn, wat ze zijn en welke praktische toepassing ze hebben gevonden op het gebied van digitale beeldverwerking en compressie.

Discrete wavelet-transformaties.

6.3.3.1. Algemene informatie over wavelettransformaties.

Wavelet-transformatie van signalen is een generalisatie van spectrale analyse, waarvan de klassieke Fourier-transformatie een typische vertegenwoordiger is.

Wavelet-transformaties (WT) zijn onderverdeeld in discreet (DWT) en continu (CWT). DWT wordt gebruikt voor signaalconversie en codering, CWT wordt gebruikt voor signaalanalyse.

Bij waveletanalyse wordt de rol van basisfuncties gespeeld door functies van een speciaal soort, genaamd wavelets. De term ‘wavelet’, vertaald uit het Engels, betekent ‘kleine (korte) golf’. Wavelets zijn een algemene naam voor families van thematische functies van een bepaalde vorm, die lokaal zijn in tijd en frequentie, en waarin alle functies worden verkregen uit één basis (genererende) functie door middel van verschuivingen en rekkingen langs de tijdas.

Wavelet-transformaties beschouwen de geanalyseerde tijdfuncties in termen van oscillaties gelokaliseerd in tijd en frequentie.

Onderscheidend kenmerk Wavelet-analyse is dat het functiesfamilies kan gebruiken die verschillende versies van de onzekerheidsrelatie implementeren. Dienovereenkomstig heeft de onderzoeker de mogelijkheid om flexibel tussen deze functies te kiezen en die wavelet-functies te gebruiken die de problemen het meest effectief oplossen.

Het belangrijkste toepassingsgebied van wavelet-transformaties is de analyse en verwerking van signalen en functies die niet-stationair zijn in de tijd, waarbij de resultaten van de analyse niet alleen moeten bevatten frequentierespons signaal (verdeling van signaalenergie over frequentiecomponenten), maar ook informatie over de lokale coördinaten waarop bepaalde groepen frequentiecomponenten zich manifesteren of waarop snelle veranderingen in de frequentiecomponenten van het signaal optreden.

In figuur 3.1 bestaat het geanalyseerde signaal uit twee gemoduleerde deesianen. De Morlet-golftransformatie laat duidelijk hun ruimtelijke en frequentielokalisatie zien, terwijl het Fourier-spectrum alleen frequentielokalisatie geeft.

Een van de belangrijkste en vooral vruchtbare ideeën van de wavelet-representatie van signalen is om de functies van benadering van het signaal in twee groepen te verdelen: benaderen - ruw, met een tamelijk langzame tijdsdynamiek van veranderingen, en detaillering - met lokale en snelle dynamiek van veranderingen. veranderingen tegen de achtergrond van vloeiende dynamiek, met de daaropvolgende fragmentatie en detaillering op andere niveaus van signaalontbinding. Dit is mogelijk zowel in de tijd- als frequentiedomeinen van golfrepresentatie van signalen.

Figuur 3.1 – wavelettransformatie van een signaal

6.3.3.2. Basisfuncties van wavelettransformaties.

Wavelets hebben de vorm van kortegolfpakketten met een gemiddelde waarde van nul, gelokaliseerd langs de argumentas, onveranderlijk wat betreft verschuiving en lineair ten opzichte van de schaalbewerking. In termen van lokalisatie in tijd- en frequentierepresentatie nemen wavelets een tussenpositie in tussen harmonische functies gelokaliseerd in frequentie en de Dirac-functie gelokaliseerd in de tijd.

De waveletbasisfunctie vertegenwoordigt een “korte” oscillatie. Bovendien is het concept van frequentie van spectrale analyse vervangen door een schaal, en is er een verschuiving van functies in de tijd geïntroduceerd om de hele tijdas met ‘korte golven’ te bestrijken. De basis van wavelets zijn tijdfuncties van het type:

, (3.1)

waarbij b de verschuiving is;

een – schaal.

De functie moet een oppervlakte nul hebben. De Fourier-transformatie van dergelijke functies is nul bij nulfrequentie en heeft de vorm van een banddoorlaatfilter. Verschillende betekenissen De schaalparameter "a" komt overeen met een set banddoorlaatfilters. Families van golfjes in het tijd- of frequentiedomein worden gebruikt om signalen weer te geven en functioneren als superposities van golfjes op verschillende schaalniveaus van signaalontbinding.

Volgende functie

is niet afhankelijk van parameters en . Vector, gegeven door de functie, heeft een constante lengte in de ruimte:

.

In de praktijk wordt de functie vaak als basisfunctie gebruikt

zogenaamde Mexicaanse hoed.

6.3.3.3. Continue wavelet-transformatie.

Laat er een functie zijn en een functie - een basisfunctie. De continue wavelettransformatie wordt beschreven door een uitdrukking van de vorm:

. (3.2)

Als de basisfunctie wordt beschreven door de uitdrukking:

,

dan is het resultaat de gebruikelijke Fourier-transformatie (in dit geval wordt de parameter niet gebruikt).

Om de gehele tijdas van de ruimte te bestrijken met een waveletfunctie, wordt de verschuivingsoperatie (verplaatsing langs de tijdas) gebruikt: , waarbij de waarde b voor NVP een continue waarde is. Om alles te bedekken frequentiebereik De wavelet-tijdschalingsbewerking wordt gebruikt met een continue verandering in de onafhankelijke variabele: . Door langs de onafhankelijke variabele (t-b) te verschuiven, heeft de wavelet dus het vermogen om langs de gehele getallenas te bewegen willekeurig signaal, en door de schaalvariabele “a” (op een vast punt (t-b)-as) te veranderen, “bekijkt” u het frequentiespectrum van het signaal over een bepaald interval in de buurt van dit punt.

De continue golftransformatie is dus de ontbinding van het signaal in alle mogelijke verschuivingen en compressies/uitbreidingen van een gelokaliseerde eindige functie: de golf. In dit geval bepaalt de variabele “a” de schaal van de golf en is equivalent aan de frequentie in de Fourier-transformatie, en de variabele “b” is de verschuiving van de golf langs het signaal vanaf het beginpunt in het gebied van zijn definitie, waarvan de schaal de tijdschaal van het geanalyseerde signaal herhaalt.

Het concept van VP-schaal heeft een analogie met de schaal geografische kaarten. Grote zoomwaarden komen overeen met een globale weergave van het signaal, terwijl lage zoomwaarden het mogelijk maken details te onderscheiden. In termen van frequentie komen lage frequenties overeen met globale informatie over het signaal, en hoge frequenties komen overeen met gedetailleerde informatie en kenmerken die van korte duur zijn, d.w.z. De waveletschaal, als eenheid van de schaal van tijd-frequentieweergave van signalen, is het omgekeerde van frequentie. Schalen zoals wiskundige bewerking, breidt of comprimeert het signaal. Grote schaalwaarden komen overeen met uitbreidingen van het signaal, en kleine waarden komen overeen met gecomprimeerde versies. In de waveletdefinitie de schaalfactor A staat in de noemer. Respectievelijk, A> 1 breidt het signaal uit, A < 1 сжимает его.

6.3.3.4. Discrete wavelet-transformatie.

In principe kan bij het verwerken van gegevens op een pc een gediscretiseerde versie van de continue wavelettransformatie worden uitgevoerd door discrete waarden van de waveletparameters (a, b) te specificeren met willekeurige stappen a en b. Het resultaat is een buitensporig aantal coëfficiënten, dat veel groter is dan het aantal monsters van het oorspronkelijke signaal, wat niet nodig is voor signaalreconstructie.

De discrete wavelettransformatie (DWT) biedt voldoende informatie voor zowel de signaalanalyse als de synthese ervan, terwijl hij zuinig is in het aantal bewerkingen en het vereiste geheugen. DVP werkt met discrete parameterwaarden A En B, die in de regel worden gespecificeerd in de vorm van machtsfuncties:

,

,

Waar ;

gehele getallen;

Schaalparameter;

Shift-parameter.

Basis van ruimte in discrete representatie:

Wavelet directe transformatiecoëfficiënten:

. (3.5)

De waarde van "a" kan willekeurig zijn, maar wordt meestal ingesteld op 2, en de conversie wordt aangeroepen dyadische wavelettransformatie. Ontworpen voor dyadische conversie snel algoritme computergebruik, vergelijkbaar snelle transformatie Fourier, die hem vooraf bepaalde wijdverbreid gebruik bij het analyseren van digitale data-arrays.

Achteruit discrete transformatie Voor continue signalen met een genormaliseerde orthogonale golfbasis van de ruimte:

. (3.6)

Het aantal golfjes dat door de schaalfactor m wordt gebruikt, specificeert het niveau ontleding signaal, terwijl het nulniveau (m = 0) gewoonlijk wordt beschouwd als het niveau van de maximale tijdresolutie van het signaal, d.w.z. het signaal zelf, en daaropvolgende niveaus (m< 0) образуют ниспадающее golfvormige boom. IN software Om het gebruik van negatieve nummering over m te vermijden, wordt het minteken gewoonlijk rechtstreeks overgebracht naar de volgende weergave van de basisfuncties:

6.3.3.5. Tijd-frequentielokalisatie van waveletanalyse.

Echte signalen zijn meestal eindig. Het frequentiespectrum van signalen is omgekeerd evenredig met hun duur. Dienovereenkomstig moet een redelijk nauwkeurige laagfrequente analyse van het signaal worden uitgevoerd met grote intervallen van zijn toewijzing, en hoogfrequente analyse met kleine intervallen. Als de frequentiesamenstelling van een signaal significante veranderingen ondergaat gedurende het interval van zijn toewijzing, levert de Fourier-transformatie alleen gemiddelde gegevens over de frequentiesamenstelling van het signaal met een constante frequentieresolutie. Een specifieke tijd-frequentielokalisatie van de analyse wordt gecreëerd door de werking van een gevensterde Fourier-transformatie, die families van frequentiespectra oplevert die in de tijd zijn gelokaliseerd, maar binnen een constante breedte van het venster van de vensterfunctie, en daarom ook met een constante waarde van zowel frequentie als tijdresolutie.

In tegenstelling tot de Fourier-transformatie met vensters, geeft de wavelet-transformatie, met vergelijkbare discrete waarden van verschuivingen b, families van spectra van schaalfactoren A compressie-spanning:

. (3.8)

Als we aannemen dat elke wavelet een bepaalde “breedte” van zijn tijdvenster heeft, wat overeenkomt met een bepaalde “gemiddelde” frequentie van het spectrale beeld van de wavelet, omgekeerd aan zijn schaalfactor A, dan kunnen de families van schaalcoëfficiënten van de wavelettransformatie worden beschouwd als vergelijkbaar met de families van frequentiespectra van de windowed Fourier-transformatie, maar met één fundamenteel verschil. Schaalfactoren veranderen de ‘breedte’ van wavelets en dienovereenkomstig de ‘gemiddelde’ frequentie van hun Fourier-beelden, en daarom heeft elke frequentie zijn eigen duur van het analysetijdvenster, en omgekeerd. Kleine parameterwaarden dus A, die snelle componenten in signalen karakteriseren, komen overeen met hoge frequenties en grote waarden – lage frequenties. Door de schaal te veranderen, kunnen wavelets verschillen detecteren verschillende frequenties, en vanwege de verschuiving (parameter B) analyseer de eigenschappen van het signaal op verschillende punten gedurende het gehele onderzochte tijdsinterval. Het multidimensionale tijdvenster van de wavelettransformatie is aangepast om zowel laag- als hoogfrequente kenmerken van signalen optimaal te identificeren.

Dus op hoge frequenties betere resolutie in de tijd, en bij lage frequenties - in frequentie. Voor de hoogfrequente component van het signaal kunnen we de tijdpositie ervan nauwkeuriger aangeven, en voor de laagfrequente component de frequentiewaarde ervan.

Hoogfrequente (kleinschalige) informatie wordt berekend op basis van lange signaalintervallen, en laagfrequente informatie wordt berekend op basis van lange signaalintervallen. Omdat de geanalyseerde signalen altijd eindig zijn, gaat het betrouwbaarheidsgebied bij het berekenen van de coëfficiënten aan de grenzen van de signaalspecificatie verder dan het signaal, en om de rekenfout te verminderen wordt het signaal aangevuld door de begin- en eindvoorwaarden te specificeren.

6.3.3.6. Voor- en nadelen van waveletanalyse.

De voordelen van waveletanalyse zijn onder meer:

Wavelet-transformaties hebben alle voordelen van Fourier-transformaties;

Waveletbases kunnen zowel qua frequentie als qua tijd goed gelokaliseerd worden;

Bij het identificeren van goed gelokaliseerde processen op meerdere schaalniveaus in signalen kan men alleen rekening houden met de schaalniveaus van decompositie die van belang zijn;

Wavelet-bases hebben, in tegenstelling tot de Fourier-transformatie, veel verschillende basisfuncties, waarvan de eigenschappen gericht zijn op het oplossen van verschillende problemen.

Het nadeel van wavelettransformaties is hun relatieve complexiteit.

6.3.3.7. Eigenschappen van waveletanalyse.

Het verkrijgen van objectieve informatie over het signaal is gebaseerd op de eigenschappen van de wavelettransformatie, die gebruikelijk is voor alle soorten wavelets. Laten we de belangrijkste van deze eigenschappen eens bekijken. Om de werking van de wavelettransformatie van willekeurige functies x(t) aan te duiden, zullen we de index TW gebruiken.

Lineariteit.

TW[α x 1 (t)+β x 2 (t)] = α TW+β TW.

Verschuivingsinvariantie. Een tijdverschuiving van het signaal met t 0 leidt ook tot een verschuiving van het golfspectrum met t 0:

TW = X(a, b-t o).

Schaalinvariantie. Het uitrekken (compressie) van het signaal leidt tot compressie (uitrekken) van het waveletspectrum van het signaal:

TW = (1/a o)·X(a/a o,b/a o).

Differentiatie.

D n (TW)/dt n = TW.

TW = (-1) n x(t) dt.

Het maakt geen verschil of er onderscheid wordt gemaakt tussen de functie of de analyserende wavelet. Als de verwijderingswavelet wordt gegeven door een formule, kan dit zeer nuttig zijn voor het verwijderen van signalen. Kenmerken van hoge orde of kleinschalige variaties van het signaal x(t) kunnen worden geanalyseerd terwijl grootschalige polynomiale componenten (trend en regionale achtergrond) worden genegeerd door het vereiste aantal keren de golf of het signaal zelf te differentiëren. Deze eigenschap is vooral handig wanneer het signaal is gespecificeerd als een discrete serie.

Analoog aan de stelling van Parseval voor orthogonale en biorthogonale golfjes.

X 1 (t) x 2 *(t) = X ψ -1 a -2 X(a,b) X*(a,b) da db.

Hieruit volgt dat de signaalenergie kan worden berekend via de wavelettransformatiecoëfficiënten.

Basisprincipes digitale verwerking signalen: leerboek / Yu.A. Brjoechanov, A.A. Priorov, V.I. Dzhigan, V.V. Chryasjtsjov; Yarosl. Staat Universiteit vernoemd naar P.G. Demidova. – Yaroslavl: YarSU, 2013. – 344 p. (pag. 270)

• Handleiding

Wavelets zijn nu populair. Zelfs mensen die onervaren zijn in de wiskunde hebben waarschijnlijk gehoord dat het met hun hulp mogelijk is om afbeeldingen en video's te comprimeren tijdens het opslaan aanvaardbare kwaliteit. Maar wat is een golfje? Wikipedia beantwoordt deze vraag met een hele reeks formules waarachter de essentie niet zo eenvoudig te zien is.

Laten we het proberen eenvoudige voorbeelden begrijpen waar wavelets vandaan komen en hoe ze kunnen worden gebruikt bij compressie. Er wordt aangenomen dat de lezer bekend is met de basisprincipes lineaire algebra, is niet bang voor de woorden vector en matrix, en weet deze ook te vermenigvuldigen. (En we zullen zelfs proberen iets te programmeren.)

Beeldcompressie

Simpel gezegd: een afbeelding is een tabel waarvan de cellen de kleuren van elke pixel opslaan. Als we met een zwart-wit (of beter gezegd grijs) beeld werken, worden in plaats van kleur de helderheidswaarden van het segment in de cellen geplaatst. In dit geval komt 0 overeen met zwart en 1 met wit. Maar het is lastig om met breuken te werken, dus helderheidswaarden worden vaak genomen als gehele getallen in het bereik van 0 tot 255. Dan zal elke waarde precies 1 byte in beslag nemen.

Zelfs kleine afbeeldingen vereisen veel geheugen om op te slaan. Dus als we de helderheid van elke pixel met één byte coderen, zal het beeld van één FullHD (1920x1080) frame bijna twee megabytes in beslag nemen. Stel je voor hoeveel geheugen er nodig zou zijn om een ​​film van anderhalf uur op te slaan!

Daarom zijn afbeeldingen vaak gecomprimeerd. Dat wil zeggen, codeer het op een zodanige manier dat er minder geheugen nodig is voor opslag. En tijdens het bekijken decoderen we de gegevens die in het geheugen zijn vastgelegd en krijgen we het originele frame. Maar dit is alleen maar ideaal.

Er zijn veel algoritmen voor datacompressie. Hun aantal kan worden beoordeeld aan de hand van de formaten die worden ondersteund door moderne archiveringsprogramma's: ZIP, 7Z, RAR, ACE, GZIP, HA, BZ2 enzovoort. Het is niet verrassend dat dankzij het actieve werk van wetenschappers en programmeurs de mate van datacompressie nu dicht bij de theoretische limiet is gekomen.

Het slechte nieuws is dat deze theoretische limiet voor beeldvorming niet zo groot is. Probeer de foto op te slaan (vooral met een groot aantal kleine onderdelen) erin PNG-formaat- de grootte van het resulterende bestand kan u van streek maken.

Dit komt door het feit dat op afbeeldingen uit echte wereld(op foto's bijvoorbeeld) zijn de helderheidswaarden zelden hetzelfde, zelfs niet voor aangrenzende pixels. Er zijn altijd kleine fluctuaties die voor het menselijk oog niet waarneembaar zijn, maar waar het compressie-algoritme eerlijk rekening mee probeert te houden.

Compressie-algoritmen houden ervan als er een patroon in de gegevens zit. Lange reeksen nullen kunnen het beste worden gecomprimeerd (het patroon is hier duidelijk). In plaats van honderd nullen in het geheugen te schrijven, kunt u eenvoudigweg het getal 100 schrijven (uiteraard met de opmerking dat dit precies het aantal nullen is). Het decodeerprogramma zal “begrijpen” dat er nullen bedoeld waren en zal deze reproduceren.

Mocht er echter in onze reeks ineens een eenheid in het midden blijken te zijn, dan kunnen we ons niet beperken tot alleen het getal 100.

Maar waarom zou je absoluut elk detail coderen? Als we naar een foto kijken, is het algemene patroon immers belangrijk voor ons, en kleine schommelingen in de helderheid zullen we niet opmerken. Dit betekent dat we bij het coderen de afbeelding enigszins kunnen wijzigen, zodat deze goed gecodeerd is. In dit geval zal de compressieverhouding onmiddellijk toenemen. Het is waar dat de gedecodeerde afbeelding enigszins zal verschillen van het origineel, maar wie zal het merken?

Haartransformatie

Ons doel is dus om het beeld zo te transformeren dat het goed wordt gecomprimeerd door klassieke algoritmen. Laten we eens nadenken over hoe we dit moeten veranderen om lange reeksen nullen te krijgen.

"Echte" afbeeldingen, zoals foto's, hebben één kenmerk: de helderheid van aangrenzende pixels verschilt meestal een klein beetje. In feite is het zeldzaam om scherpe, contrasterende veranderingen in helderheid in de wereld te zien. En als ze bestaan, nemen ze slechts een klein deel van het beeld in beslag.

Laten we een fragment van de eerste helderheidslijn bekijken van het beroemde beeld "Lenna" (in de figuur).

154, 155, 156, 157, 157, 157, 158, 156

Het is duidelijk dat de aangrenzende nummers heel dichtbij liggen. Om de gewenste nullen te krijgen, of op zijn minst iets dat daar dichtbij komt, kunt u het eerste getal afzonderlijk coderen en vervolgens alleen de verschillen tussen elk getal en het vorige in ogenschouw nemen.

Wij krijgen:

154, 1, 1, 1, 0, 0, 1, -2.

Al beter! Deze methode wordt daadwerkelijk gebruikt en wordt delta-codering genoemd. Maar het heeft een ernstig nadeel: het is niet-lokaal. Dat wil zeggen dat je geen stukje van de reeks kunt nemen en er precies achter kunt komen welke helderheid daarin is gecodeerd zonder alle waarden vóór dit stukje te decoderen.

Laten we proberen het anders te doen. Laten we niet meteen proberen een goede reeks te krijgen, maar proberen deze op zijn minst een beetje te verbeteren.

Om dit te doen, verdelen we alle getallen in paren en vinden we de halve sommen en halve verschillen van de waarden in elk van hen.

(154, 155), (156, 157), (157, 157), (158, 156)
(154.5, 0.5), (156.5, 0.5), (157, 0.0), (157, -1.0)

Waarom halve bedragen en halve verschillen? En alles is heel eenvoudig! De halve som is de gemiddelde helderheidswaarde van een paar pixels. En het halve verschil bevat informatie over de verschillen tussen de waarden in het paar. Als je de halve som a en het halve verschil d kent, kun je de waarden uiteraard zelf vinden:
eerste waarde in paar = a - d,
tweede waarde in het paar = a + d.

Deze transformatie werd in 1909 voorgesteld door Alfred Haar en draagt ​​zijn naam.

Waar is de compressie?

De resulterende getallen kunnen worden gehergroepeerd volgens het principe "vliegt afzonderlijk, koteletten afzonderlijk", waarbij halve bedragen en halve verschillen worden verdeeld:

154.5, 156.5, 157, 157; 0.5, 0.5, 0.0, -1.0.

De getallen in de tweede helft van de reeks zullen meestal klein zijn (het feit dat het geen gehele getallen zijn, stoort je voorlopig niet). Waarom is dit zo?

Zoals we eerder ontdekten, verschillen aangrenzende pixels in echte afbeeldingen zelden significant van elkaar. Als de waarde van de een groot is, dan is de ander ook groot. In dergelijke gevallen wordt gezegd dat aangrenzende pixels gecorreleerd zijn.

Laten we in feite de eerste 2000 paren aangrenzende pixels bekijken en elk paar weergeven als een punt in de grafiek.

Alle punten liggen op één rechte lijn. En dus in bijna alle echte afbeeldingen. De linkerboven- en rechterbenedenhoek van de afbeelding zijn bijna altijd leeg.

Laten we nu eens naar een grafiek kijken waarvan de punten halve sommen en halve verschillen zijn.

Het is duidelijk dat de halve verschillen zich in een veel kleiner bereik van waarden bevinden. Dit betekent dat u er minder dan één byte aan kunt besteden. Een soort compressie.

Laten we wiskunde gebruiken!

Laten we proberen wiskundige uitdrukkingen op te schrijven die de Haar-transformatie beschrijven.

We hadden dus een paar pixels (vector) en we willen een paar krijgen.

Deze transformatie wordt beschreven door de matrix.

Inderdaad , en dat is wat we nodig hadden.

De oplettende lezer zal ongetwijfeld gemerkt hebben dat de stippenpatronen op de laatste twee grafieken hetzelfde zijn. Het enige verschil is de rotatie onder een hoek van 45°.

In de wiskunde worden rotaties en rekoefeningen affiene transformaties genoemd en worden ze nauwkeurig beschreven door een matrix met een vector te vermenigvuldigen. Dat is wat we hierboven hebben gekregen. Dat wil zeggen dat de Haar-transformatie eenvoudigweg de punten roteert, zodat ze gemakkelijk en compact kunnen worden gecodeerd.

Toegegeven, er is hier één nuance. Tijdens affiene transformaties kan de oppervlakte van een figuur veranderen. Niet dat het slecht was, maar ergens slordig. Zoals bekend is de veranderingscoëfficiënt in oppervlakte gelijk aan de determinant van de matrix. Laten we eens kijken wat het is voor de Haar-transformatie.

Om de determinant te worden gelijk aan één het is voldoende om elk element van de matrix met te vermenigvuldigen. Dit heeft geen invloed op de rotatiehoek (en dus op de “drukkracht” van de transformatie).

We eindigen met een matrix

Hoe decoderen?

Zoals bekend is, als een matrix een determinant heeft die niet gelijk is aan nul, dan is er een inverse matrix ervoor die zijn actie ‘annuleert’. Als wij vinden omgekeerde matrix voor H zal het decoderen eenvoudigweg bestaan ​​uit het vermenigvuldigen van vectoren met halve sommen en halve verschillen daarmee.

Over het algemeen is het vinden van de inverse van een matrix niet zo eenvoudig. Maar misschien kunnen we deze taak op de een of andere manier vereenvoudigen?

Laten we onze matrix eens nader bekijken. Het bestaat uit twee rijvectoren: en . Laten we ze v 1 en v 2 noemen.

Ze hebben interessante eigenschappen.

Ten eerste zijn hun lengtes gelijk aan 1, dat wil zeggen. Hier staat de letter T voor transponeren. Het vermenigvuldigen van een rijvector met een getransponeerde rijvector is een puntproduct.

Ten tweede zijn ze orthogonaal.

Een matrix waarvan de rijen de gespecificeerde eigenschappen hebben, wordt orthogonaal genoemd. Een uiterst belangrijke eigenschap van dergelijke matrices is dat hun inverse matrix kan worden verkregen door eenvoudige transpositie.

De geldigheid van deze uitdrukking kan worden geverifieerd door de inverse matrix H te vermenigvuldigen. Op de diagonaal krijgen we scalaire producten van rijvectoren met zichzelf, dat wil zeggen 1. En buiten de diagonalen krijgen we scalaire producten van rijvectoren met elkaar, dat wil zeggen 0. Als resultaat zal het product gelijk zijn aan de identiteitsmatrix.

Wij houden van orthogonale matrices!

Het verhogen van het aantal punten

Al het bovenstaande werkt goed voor twee punten. Maar wat als er meer punten zijn?

In dit geval is het ook mogelijk om de transformatie te beschrijven met een matrix, maar dan groter van formaat. De diagonaal van deze matrix zal bestaan ​​uit matrices H, dus in de vector initiële waarden paren zullen worden geselecteerd waarop de Haar-transformatie onafhankelijk zal worden toegepast.

Dat is. de originele vector wordt eenvoudigweg in paren onafhankelijk verwerkt.

Filters

Dus nu we weten hoe we de Haar-transformatie moeten uitvoeren, laten we proberen erachter te komen wat het ons oplevert.

De resulterende "halve bedragen" (vanwege het feit dat we niet door 2 delen, moeten we aanhalingstekens gebruiken) zijn, zoals we al hebben ontdekt, de gemiddelde waarden in paren pixels. Dat wil zeggen dat de halve somwaarden in feite een verkleinde kopie zijn van de originele afbeelding! Verkleind omdat de halve bedragen twee keer kleiner zijn dan de oorspronkelijke pixels.

Maar wat zijn de verschillen?

Halve bedragen van gemiddelde helderheidswaarden, dat wil zeggen, ze "filteren" willekeurige pieken in waarden. We kunnen dit beschouwen als een soort frequentiefilter.

Op dezelfde manier "markeren" de verschillen interpixel-"pieken" tussen de waarden en elimineren ze de constante component. Dat wil zeggen, ze “filteren” lage frequenties.

De Haar-transformatie bestaat dus uit een paar filters die het signaal scheiden in laagfrequente en hoogfrequente componenten. Om het originele signaal te krijgen, hoeft u deze componenten alleen maar opnieuw te combineren.

Wat levert dit ons op? Laten we een portretfoto maken. De laagfrequente component draagt ​​informatie over algemene vorm gezichten, over vloeiende veranderingen in helderheid. Hoge frequentie is ruis en kleine details.

Als we naar een portret kijken, zijn we doorgaans meer geïnteresseerd in de laagfrequente component, wat betekent dat tijdens de compressie een deel van de hoogfrequente gegevens kan worden weggegooid. Bovendien heeft het, zoals we ontdekten, meestal kleinere waarden, wat betekent dat het compacter gecodeerd is.

De compressieverhouding kan worden verhoogd door de Haar-transformatie herhaaldelijk toe te passen. In feite is de hoogfrequente component slechts de helft van de gehele reeks getallen. Maar wat weerhoudt ons ervan om onze procedure opnieuw toe te passen op laagfrequente gegevens? Na herhaalde toepassing zal hoogfrequente informatie 75% in beslag nemen.

Hoewel we het tot nu toe hebben gehad over eendimensionale getallenreeksen, werkt deze aanpak ook goed voor tweedimensionale gegevens. Om een ​​tweedimensionale Haar-transformatie (of iets dergelijks) uit te voeren, hoeft u deze alleen voor elke rij en voor elke kolom uit te voeren.

Na herhaalde toepassing op bijvoorbeeld een foto van kasteel Liechtenstein krijgen we het volgende beeld.

Zwarte gebieden komen overeen met een lage helderheid, dat wil zeggen waarden dichtbij nul. Zoals de praktijk laat zien, kan de waarde, als deze klein genoeg is, worden afgerond of zelfs op nul worden gezet zonder veel schade aan het gedecodeerde beeld.

Dit proces wordt kwantisering genoemd. En het is in dit stadium dat er wat informatie verloren gaat. (Overigens wordt dezelfde aanpak gebruikt in JPEG, alleen wordt daar, in plaats van de Haar-transformatie, een discrete cosinustransformatie gebruikt.) Door het aantal nulcoëfficiënten te wijzigen, kun je de mate van compressie aanpassen!

Als u te veel op nul zet, wordt de vervorming natuurlijk zichtbaar voor het oog. Alles heeft gematigdheid nodig!

Na al deze acties houden we een matrix over met veel nullen. Het kan regel voor regel in een bestand worden geschreven en met een soort archiveringshulpmiddel worden gecomprimeerd. Bijvoorbeeld dezelfde 7Z. Het resultaat zal goed zijn.

Het decoderen gebeurt in omgekeerde volgorde: pak het archief uit, pas de inverse Haar-transformatie toe en schrijf de gedecodeerde afbeelding naar een bestand. Voila!

Waar is de Haar-transformatie effectief?

Wanneer de Haar-transformatie geeft beste resultaat? Het is duidelijk dat als we veel nullen krijgen, dat wil zeggen als de afbeelding lange delen bevat identieke waarden helderheid Vervolgens worden alle verschillen op nul gezet. Dit kan bijvoorbeeld zijn röntgenfoto, gescand document.

Ze zeggen dat de Haar-transformatie de constante component elimineert (het is ook het moment van de nulde orde), dat wil zeggen dat het constanten omzet in nullen.

Maar nog steeds binnen echte foto's Er zijn niet veel gebieden met dezelfde helderheid. Laten we proberen de transformatie te verbeteren, zodat ook de lineaire component opnieuw wordt ingesteld. Met andere woorden: als de helderheidswaarden lineair worden verhoogd, worden deze ook gereset.

Dit probleem en de complexere problemen (eliminatie van momenten van hogere orde) werden opgelost door Ingrid Daubechies, een van de makers van de wavelet-theorie.

Daubechies-transformatie

Voor onze verbeterde transformatie zullen twee punten niet genoeg zijn. Daarom nemen we vier waarden, waarbij we elke keer twee waarden verschuiven.

Dat wil zeggen, als de initiële reeks 1, 2, 3, 4, 5, 6,…, N-1, N is, dan nemen we de viertallen (1, 2, 3, 4), (3, 4, 5 , 6) enz. De laatste vier “bijten de reeks bij de staart”: (N-1, N, 1, 2).

Laten we op dezelfde manier proberen twee filters te bouwen: hoge frequentie en lage frequentie. We zullen elke vier vervangen door twee cijfers. Omdat de vier elkaar overlappen, zal het aantal waarden na de transformatie niet veranderen.

Laat de helderheidswaarden in de quad gelijk zijn aan x, y, z, t. Vervolgens schrijven we het eerste filter in het formulier

De vier coëfficiënten die de rijvector van de transformatiematrix vormen, zijn ons nog onbekend.

Om de rijvector van de coëfficiënten van het tweede filter orthogonaal te maken ten opzichte van het eerste, neemt u dezelfde coëfficiënten, maar herschikt u ze en verandert u de tekens:

De transformatiematrix ziet er als volgt uit:

Aan de orthogonaliteitseis wordt automatisch voldaan voor de eerste en tweede rij. We vereisen dat lijnen 1 en 3 ook orthogonaal zijn:

Vectoren moeten een eenheidslengte hebben (anders is de determinant geen eenheid):

De transformatie moet een keten van identieke waarden resetten (bijvoorbeeld (1, 1, 1, 1)):

De transformatie moet een keten van lineair toenemende waarden resetten (bijvoorbeeld (1, 2, 3, 4)):

Trouwens, als deze vier op nul wordt gezet, zullen alle andere lineair stijgende of lineair dalende waarden ook worden gereset. Dit kan eenvoudig worden geverifieerd door de overeenkomstige vergelijking te schrijven en alle coëfficiënten te delen door de eerste factor.

We hebben vier vergelijkingen ontvangen die de coëfficiënten met elkaar in verband brengen. Als we ze oplossen, krijgen we:

Door ze in de matrix te vervangen, verkrijgen we de gewenste transformatie. Nadat we het op foto's hebben toegepast, krijgen we meer nullen en kleine coëfficiënten, waardoor we de afbeelding meer kunnen comprimeren.

Een ander leuk kenmerk is dat artefacten na kwantisering niet zo opvallend zullen zijn.

Deze transformatie wordt de D4-wavelet genoemd (de lezer wordt uitgenodigd om zelfstandig het mysterie van deze alfanumerieke naam te ontrafelen).

Andere golfjes

We mogen het daar natuurlijk niet bij laten en de eliminatie van de parabolische component (moment van de 2e orde) eisen, enzovoort. Als gevolg hiervan verkrijgen we golfjes D6, D8 en andere.

Om te voorkomen dat je alles handmatig moet tellen, kun je de coëfficiënten opzoeken op Wikipedia.

Daubechies gingen behoorlijk open interessante manier het verkrijgen van de coëfficiënten van deze transformaties, maar helaas valt dit buiten het bestek van ons artikel.

Huiswerk

Om eindelijk de basisprincipes te begrijpen, stel ik voor om een ​​programma in je favoriete taal te schrijven dat een afbeelding opent, een Haar-transformatie uitvoert (of zelfs D4), het resultaat kwantiseert en het resultaat vervolgens in een bestand opslaat. Probeer dit bestand te comprimeren met uw favoriete archiveringsprogramma. Is het goed te comprimeren?

Probeer de omgekeerde conversie. Hoe verklaar je de aard van de artefacten in de afbeelding?

Conclusie

Natuurlijk omvatte dit artikel niet veel interessante wiskundige details en praktische toepassingen golftransformaties. Maar je kunt de onmetelijkheid niet omarmen. En veel dingen zijn moeilijk uit te leggen zonder het taalniveau te verhogen. Ik hoop dat wat ik schreef nuttig voor iemand was.