Discrete wavelet-transformatie. K.A

Golfjes(uit het Engels golfje), barst- Dit wiskundige functies, waardoor u verschillende frequentiecomponenten van de gegevens kunt analyseren. Waveletcoëfficiënten worden bepaald door de integrale transformatie van het signaal. De resulterende waveletspectrogrammen verschillen fundamenteel van conventionele Fourier-spectra in die zin dat ze een duidelijke referentie bieden naar het spectrum verschillende functies tijd signalen.

Voor verwerking discrete signalen Er wordt gebruik gemaakt van de discrete wavelettransformatie (DWT).

De eerste DVP werd voorgesteld door de Hongaarse wiskundige Alfred Haar. Voor een ingangssignaal dat wordt weergegeven door een reeks van 2 n getallen, groepeert de Haar-wavelettransformatie eenvoudigweg de elementen door 2 en vormt er sommen en verschillen van. Het groeperen van sommen wordt recursief uitgevoerd om het volgende ontbindingsniveau te vormen. Het resultaat is 2 n −1 verschil en 1 totale som. We beginnen met een eendimensionale gegevensarray bestaande uit N elementen. In principe kunnen deze elementen aangrenzende beeldpixels of opeenvolgende geluidsfragmenten zijn. Een voorbeeld is een reeks getallen (2,9,12,10,9,8, 8,7). Laten we eerst de vier gemiddelde waarden berekenen (Fig. 40)

Het is duidelijk dat kennis van deze vier halve sommen niet voldoende is om de hele array te herstellen, dus zullen we ook vier halve verschillen berekenen

(2 - 9)/2 = - 4,5,

(12 - 10)/2 = 1,

(9 – 8)/2 = 0,5,

(8 – 7)/2 = 0,5,

die we detailcoëfficiënten zullen noemen. Gemiddelde getallen kunnen worden gezien als de grootschalige resolutie van het originele beeld, en er zijn details nodig om fijne details of correcties te reconstrueren. Als de brongegevens gecorreleerd zijn, zal de grootschalige resolutie de originele afbeelding herhalen en zullen de details klein zijn.

Voor de reconstructie kan een array bestaande uit vier halve sommen en vier halve verschillen worden gebruikt bronarray cijfers. Nieuwe array bestaat ook uit acht cijfers, maar de laatste vier componenten, de halve verschillen, hebben de neiging kleiner te worden, wat goed is voor de compressie.

Laten we onze procedure herhalen voor de eerste vier (grote) componenten van onze nieuwe array. Ze worden omgezet in twee gemiddelden en twee halve verschillen. De overige vier componenten laten we ongewijzigd. De volgende en laatste iteratie van ons proces converteert de eerste twee componenten van deze array naar één gemiddelde (wat feitelijk gelijk is aan het gemiddelde van alle acht elementen van de oorspronkelijke array) en één halfverschil.

Figuur 3.18. Illustratie van de werking van een eendimensionale wavelettransformatie.

Als gevolg hiervan krijgen we een reeks nummers die worden gebeld wavelet Haar transformatie originele data-array.

De eendimensionale Haar-golftransformatie kan eenvoudig worden overgebracht naar het tweedimensionale geval. De standaarddecompositie (Fig. 3.19) begint met het berekenen van de wavelettransformaties van alle rijen van het beeld. Alle iteraties van het proces worden op elke rij toegepast totdat het meest linkse element van elke rij gelijk is aan het gemiddelde van de getallen in die rij en alle andere elementen gelijk zijn aan de gewogen verschillen. Het resultaat is een afbeelding waarvan de eerste kolom het gemiddelde bevat van de kolommen van de originele afbeelding. Hierna voert het standaardalgoritme een wavelettransformatie uit op elke kolom. Het resultaat zal zijn tweedimensionale array, waarbij het element in de linkerbovenhoek gelijk is aan het gemiddelde van de gehele originele array. Andere elementen bovenste regel zal gelijk zijn aan de gemiddeld gewogen verschillen, hieronder staan ​​de verschillen van de gemiddelden, en alle andere pixels worden omgezet naar de overeenkomstige verschillen.

De piramidale ontbinding berekent de wavelettransformatie door afwisselend iteraties toe te passen op rijen en kolommen. In de eerste stap worden halve sommen en halve verschillen berekend voor alle rijen (slechts één iteratie, niet de hele wavelettransformatie). Deze actie produceert gemiddelden in de linkerhelft van de matrix en halve verschillen in de rechterhelft. Bij de tweede stap worden halve sommen en halve verschillen berekend voor alle kolommen van de resulterende matrix.

Figuur 3.19. Standaard tweedimensionale wavelettransformatie

Figuur 3.20. Piramidale 2D-golftransformatie

Het resultaat van de tweedimensionale wavelettransformatie is een reeks matrices die overeenkomen met verschillende spectrale componenten van het originele beeld. Tegelijkertijd links bovenste hoek er is een laagfrequente component LL4 (Fig. 3.21), die alleen op basis van halve bedragen is gemaakt en een verkleinde kopie is van het originele beeld.

Figuur 3.21. Componenten van de tweedimensionale wavelettransformatie

De overige componenten van de transformatie kunnen worden gebruikt om de originele afbeelding te herstellen. Tegelijkertijd lenen hoogfrequente componenten zich goed voor compressie RLE-algoritmen en Huffman. Er moet ook worden opgemerkt dat het bij compressie met verlies van informatie ook mogelijk is om kwantisering te gebruiken, evenals het direct weggooien van een deel van de componenten. Het resultaat van dergelijke operaties is goede graad compressie. In afb. Figuur 3.22 toont een voorbeeld van beeldcodering met behulp van de wavelettransformatie.

Opgemerkt moet worden dat de tweedimensionale wavelet-transformatie aanzienlijke hoeveelheden vereist computerbronnen wanneer geïmplementeerd door gewone gebruik van softwaremethoden. Het wavelet-transformatie-algoritme bestaat echter uit: grote hoeveelheid eenvoudige transformaties die zich goed lenen voor parallellisatie. Als gevolg hiervan wordt deze conversie goed uitgevoerd in hardware met behulp van gespecialiseerde hardware.

Figuur 3.22. Een voorbeeld van wavelettransformatie van een afbeelding.

De wavelettransformatie wordt gebruikt in de JPEG2000-beeldcompressiestandaard en wordt ook als hulpmiddel aangeboden in het MPEG-4-formaat.

In de praktijk moet DTWS worden toegepast op signalen met een eindige lengte. Het moet dus worden gewijzigd om uit een signaal van enige lengte een reeks coëfficiënten van dezelfde lengte te verkrijgen. De resulterende transformatie wordt de discrete wavelettransformatie (DWT) genoemd.

Eerst zullen we DWT in matrixvorm beschrijven, en vervolgens op basis van filterbanken, die het vaakst worden gebruikt bij signaalverwerking.

In beide gevallen gaan we ervan uit dat de basis functioneert en
compact gedefinieerd. Dit garandeert automatisch de eindigheid van de reeksen En . Laten we verder aannemen dat het signaal dat wordt omgezet een lengte heeft
.

1. Matrixbeschrijving dwt

Laten we aangeven met vector eindige lengtereeks voor sommigen . Deze vector wordt omgezet in een vector
, met reeksen
En
, die elk de halve lengte hebben. De transformatie kan worden geschreven als een matrixvermenigvuldiging
, waarbij matrix
- vierkant en bestaat uit nullen en elementen , vermenigvuldigd met
. Vanwege eigenschappen , verkregen in paragraaf 2.3, matrix
is orthonormaal en de inverse matrix is ​​gelijk aan de getransponeerde matrix. Beschouw ter illustratie het volgende voorbeeld. Laten we een lengtefilter nemen
, een reeks van lengte
, en als beginwaarde -
. Vervolg wij komen vandaan volgens formule (2.35), waarbij
. Vervolgens wordt de werking van matrix-vectorvermenigvuldiging in het formulier weergegeven

. (2.52)

De inverse transformatie is vermenigvuldiging
op omgekeerde matrix
:

. (2.53)

Expressie (2.51) is dus één stap van de DWT. De volledige DWT bestaat uit het iteratief vermenigvuldigen van de bovenste helft van de vector
per vierkante matrix
, waarvan de omvang
. Deze procedure kan worden herhaald D keer totdat de vectorlengte 1 is.

In de vierde en achtste rij van matrix (2.51) de reeks circulair verschoven: coëfficiënten die voorbij de matrix aan de rechterkant reiken, worden in dezelfde rij aan de linkerkant geplaatst. Dit betekent dat DWT precies één periode lang is N DTWS-signaal , verkregen door oneindige periodieke voortzetting . Dus DWT gebruikt, wanneer het op deze manier wordt gedefinieerd, de periodiciteit van het signaal, net als DFT.

De matrixbeschrijving van DWT is kort en duidelijk. Bij signaalverwerking wordt DWT echter meestal beschreven door een blokdiagram dat lijkt op het diagram van een analyse-synthesesysteem (zie figuur 1.1).

1. Beschrijving van dwt met behulp van filterblokken

Bij het beschouwen van subbandtransformaties in Hoofdstuk 1 hebben we gelijkheden vergelijkbaar met (2.45) en (2.46) geïnterpreteerd als filtering gevolgd door decimering met een factor twee. Sinds in in dit geval er zijn twee filters En , dan is de filterbank tweebands en kan worden weergegeven zoals weergegeven in figuur 2.5.

Filters F En E betekent filteren door filters En
respectievelijk. Laagdoorlaatfiltering wordt uitgevoerd in de onderste tak van het circuit. Het resultaat is een benadering van het signaal, een laagfrequente (LF) subband zonder details. Aan de bovenkant van het circuit is een hoogfrequente (HF) subband toegewezen. Merk op dat bij het verwerken van signalen de constante
wordt altijd uit de filterbank gehaald en het signaal wordt met 2 vermenigvuldigd (zie figuur 3.2, hoofdstuk 3).

Het circuit in figuur 2.5 verdeelt dus het niveausignaal
voor signalen op twee niveaus
. Vervolgens wordt de wavelettransformatie verkregen door dit schema recursief toe te passen op het LF-deel. Bij het implementeren van de wavelettransformatie van een afbeelding wordt elke iteratie van het algoritme eerst op de rijen en vervolgens op de kolommen van de afbeelding uitgevoerd (de zogenaamde Mallat-piramide wordt gebouwd). De ADV6xx-videocodecs gebruiken een aangepaste Mallat-piramide, waarbij het bij elke iteratie niet nodig is om zowel rij- als kolomconversie uit te voeren. Dit wordt gedaan om beter rekening te houden met de menselijke visuele perceptie.

De resulterende transformatie is vergelijkbaar met (2.51). Er zijn echter enkele verschillen. Bij het filteren van een signaal van eindige lengte worden we geconfronteerd met het probleem van de voortzetting ervan op de grens. Matrixuitvoering van DWT komt overeen met het periodiek voortzetten van het signaal op de grens. Dit voortzettingstype is vereist voor orthogonale filters. In het geval van het gebruik van biorthogonale filters ontstaan ​​er enkele andere mogelijkheden vanwege de symmetrie van hun kenmerken. Dit onderwerp zal in hoofdstuk 3 in meer detail worden besproken.

Het circuit dat DWT uitvoert, kan ook worden weergegeven zoals weergegeven in figuur 2.6. Hier worden recursieve filtering en decimering vervangen door één filteroperatie en één decimatieoperatie per subband. Iteratieve filters definiëren En het is het gemakkelijkst te geven in het frequentiedomein.

Onderwerp Wavelet-transformaties.

Lezingen 6-8

Schaalfuncties. Orthogonale, continue en discrete wavelettransformatie.

Schattings- en benaderingsproblemen. Tweedimensionale en multidimensionale wavelet-transformaties en beeldverwerking (ruisverwijdering, rasterbeeldverwerking).

Oppervlakterepresentatie op meerdere schaal voor waveletanalyse. Wavelet-compressie van signalen, afbeeldingen, videobeelden.

Wavelet-transformatie van signalen is een generalisatie van spectrale analyse, waarvan de klassieke Fourier-transformatie een typische vertegenwoordiger is. De term 'wavelet', vertaald uit het Engels, betekent 'kleine (korte) golf'. Wavelets zijn een algemene naam voor families van wiskundige functies van een bepaalde vorm, die lokaal zijn in tijd en frequentie, en waarin alle functies worden verkregen vanuit één basis (genererend) door middel van verschuivingen en rekkingen langs de tijdas. Wavelet-transformaties beschouwen de geanalyseerde tijdfuncties in termen van oscillaties gelokaliseerd in tijd en frequentie. Meestal worden wavelettransformaties (WT) onderverdeeld in discreet (DWT) en continu (CWT).

DWT wordt gebruikt voor signaalconversie en codering, CWT wordt gebruikt voor signaalanalyse. Wavelet-transformaties worden nu toegepast voor een grote verscheidenheid aan toepassingen, waarbij ze vaak de conventionele Fourier-transformatie vervangen. Dit wordt op veel gebieden waargenomen, waaronder moleculaire dynamica, kwantummechanica, astrofysica, geofysica, optica, computergraphics en beeldverwerking, DNA-analyse, eiwitonderzoek, klimaatonderzoek, algemene signaalverwerking en spraakherkenning.

Waveletanalyse is een speciaal type lineaire transformatie van signalen en fysieke gegevens. Basis eigenfuncties, dat wordt gebruikt voor de ontleding van signalen, heeft veel specifieke eigenschappen en mogelijkheden. Wavelet-basisfuncties maken het mogelijk om de aandacht te concentreren op bepaalde lokale kenmerken van de geanalyseerde processen die niet kunnen worden geïdentificeerd met behulp van traditionele Fourier- en Laplace-transformaties. Dergelijke processen in de geofysica omvatten gebieden van verschillende fysieke parameters van natuurlijke omgevingen. In de eerste plaats gaat het hier om velden van temperatuur, druk, seismische spoorprofielen en andere fysieke grootheden.

Wavelets hebben de vorm van kortegolfpakketten met een gemiddelde waarde van nul, gelokaliseerd langs de as van argumenten (onafhankelijke variabelen), onveranderlijk wat betreft verschuiving en lineair ten opzichte van de schaalbewerking (compressie/uitrekken). 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 Wavelet-theorie is geen fundamentele natuurkundige theorie, maar biedt een handig en effectief hulpmiddel voor het oplossen van veel praktische problemen. Het belangrijkste toepassingsgebied van wavelet-transformaties is de analyse en verwerking van signalen en functies die niet-stationair zijn in de tijd of niet-uniform in de ruimte, wanneer de resultaten van de analyse niet alleen de frequentierespons van het signaal moeten bevatten ( verdeling van signaalenergie over frequentiecomponenten), maar ook informatie over de lokale coördinaten waarop ze zich in bepaalde groepen frequentiecomponenten manifesteren of waarop snelle veranderingen frequentiecomponenten van het signaal. Vergeleken met de ontleding van signalen in Fourierreeksen zijn wavelets in staat lokale kenmerken van signalen met een veel grotere nauwkeurigheid weer te geven, tot aan discontinuïteiten van de eerste soort (sprongen). In tegenstelling tot Fourier-transformaties zorgt de wavelet-transformatie van eendimensionale signalen voor een tweedimensionale zwaai, terwijl frequentie en coördinaat als onafhankelijke variabelen worden beschouwd, wat het mogelijk maakt om signalen in twee ruimtes tegelijk te analyseren.

Een van de belangrijkste en vooral vruchtbare ideeën van de golfrepresentatie van signalen op verschillende ontbindingsniveaus (decompositie) is om de functies van benadering van het signaal in twee groepen te verdelen: benaderen - ruw, met een vrij langzame tijdsdynamiek van veranderingen, en detaillering - met lokale en snelle dynamiek van veranderingen in de vloeiende dynamiek van de achtergrond, gevolgd door hun fragmentatie en detaillering op andere niveaus van signaalontbinding. Dit is mogelijk zowel in de tijd- als frequentiedomeinen van golfrepresentatie van signalen.

De geschiedenis van de spectrale analyse gaat terug tot I. Bernoulli, Euler en Fourier, die voor het eerst de theorie van de uitbreiding van functies in trigonometrische reeksen ontwikkelden. Deze uitbreiding werd echter lange tijd gebruikt als wiskundige techniek en was niet geassocieerd met fysieke concepten. Spectrale concepten werden gebruikt en ontwikkeld door een relatief kleine kring van theoretische natuurkundigen. Vanaf de jaren twintig van de vorige eeuw kregen spectrale decomposities, als gevolg van de snelle ontwikkeling van radiotechniek en akoestiek, echter een fysieke betekenis en praktische toepassing. Het belangrijkste middel om echte fysieke processen te analyseren is harmonische analyse geworden, en de wiskundige basis van analyse is de Fourier-transformatie. De Fourier-transformatie ontleedt een willekeurig proces in elementaire harmonische oscillaties met verschillende frequenties, en alle noodzakelijke eigenschappen en formules worden uitgedrukt met behulp van één basisfunctie exp(jt) of twee reële functies sin(t) en cos(t). Harmonische oscillaties zijn wijdverspreid van aard en daarom is de betekenis van de Fourier-transformatie intuïtief duidelijk, ongeacht wiskundige analyses.

De Fouriertransformatie heeft een aantal opmerkelijke eigenschappen. Het domein van de definitie van de transformatie is de ruimte L 2 van vierkant-integreerbare functies, en veel fysieke processen in de natuur kunnen worden beschouwd als functies die tot deze ruimte behoren. Om de transformatie toe te passen, zijn efficiënte computerprocedures zoals snelle conversie Fourier-transformatie (FFT). Deze procedures zijn opgenomen in alle pakketten van toegepaste wiskundige programma's en zijn geïmplementeerd in hardware in signaalprocessors.

Er werd ook ontdekt dat functies niet alleen kunnen worden uitgebreid in termen van sinussen en cosinussen, maar ook in andere orthogonale basissystemen, bijvoorbeeld de Legendre- en Chebyshev-polynomen, Laguerre- en Hermite-functies. Ze kregen echter pas in de laatste decennia van de twintigste eeuw praktische toepassing dankzij de ontwikkeling van computertechnologie en methoden voor de synthese van digitale lineaire gegevensverwerkingssystemen. Direct voor doeleinden van spectraalanalyse hebben dergelijke orthogonale functies geen brede toepassing gevonden vanwege moeilijkheden bij het interpreteren van de verkregen resultaten. Om dezelfde redenen werden functies van het “rechthoekige golf”-type van Walsh, Rademacher, enz. niet ontwikkeld in de spectraalanalyse.

Theoretische studies van basissystemen leidden tot de creatie van de theorie van gegeneraliseerde spectraalanalyse, die het mogelijk maakte om de grenzen van de praktische toepassing van Fourier-spectraalanalyse te beoordelen en methoden en criteria creëerde voor de synthese van orthogonale basissystemen. Een illustratie hiervan is de theorie van basisfuncties van het wavelet-type, die zich sinds het begin van de jaren 80 van de vorige eeuw actief heeft ontwikkeld. Vanwege de transparantie van de fysieke interpretatie van de analyseresultaten, vergelijkbaar met de "frequentie" -benadering in de Fourier-transformatie, is de orthogonale waveletbasis een populair en effectief middel geworden voor het analyseren van signalen en beelden op het gebied van akoestiek, seismiek, geneeskunde en andere gebieden. van wetenschap en technologie.

Waveletanalyse is een soort spectrale analyse waarbij de rol van eenvoudige oscillaties wordt gespeeld door functies van een speciaal soort, genaamd wavelets. De basisfunctie van een golfje is een ‘korte’ oscillatie, maar niet alleen dat. Het concept van frequentie van spectrale analyse wordt hier vervangen door een schaal, en om de hele tijdas met “korte golven” te bestrijken, wordt een verschuiving van functies in de tijd geïntroduceerd. De waveletbasis is een functie van het type ((t-b)/a), waarbij b de verschuiving is en de schaal. De functie (t) moet een oppervlakte nul hebben en, nog beter, het eerste, tweede en andere momenten gelijk aan nul. De Fourier-transformatie van dergelijke functies is gelijk aan nul bij =0 en heeft de vorm van een banddoorlaatfilter. Voor verschillende waarden van de schaalparameter "a" zal dit een set banddoorlaatfilters zijn. 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.

De eerste vermelding van dergelijke functies (die geen wavelets werden genoemd) verscheen aan het begin van de vorige eeuw in de werken van Haar. De Haar-golf is een korte rechthoekige oscillatie op het interval getoond in Fig. 1.1.1. Theoretisch gezien is het echter interessanter, omdat het geen continu differentieerbare functie is en lange “staarten” heeft in het frequentiedomein. In de jaren dertig ontdekte natuurkundige Paul Levy tijdens zijn studie van de Brownse beweging dat de Haar-basis beter was dan de Fourier-basis voor het bestuderen van de details van de Brownse beweging.

De term 'wavelet' zelf, als concept, werd geïntroduceerd in hun artikel van J. Morlet en A. Grossman, gepubliceerd in 1984. Ze bestudeerden seismische signalen met behulp van een basis, die ze een wavelet noemden. Belangrijke bijdragen aan de wavelettheorie werden geleverd door Guppilaud, Grossman en Morlet, die de fundamenten van CWT formuleerden, Ingrid Daubechies, die orthogonale wavelets ontwikkelde (1988), Nathalie Delpraz, die de tijdfrequentie-interpretatie van CWT creëerde (1991), en vele anderen. anderen. De wiskundige formalisering van wavelets in de werken van deze en andere auteurs leidde tot de creatie van de theoretische grondslagen van waveletanalyse, genaamd multi-resolutie (multiple-scale) analyse.

Momenteel zijn er speciale uitbreidingspakketten voor wavelets aanwezig in de belangrijkste systemen van de computerwiskunde (Matlab, Mathematica, Mathcad, enz.), en wavelet-transformaties en wavelet-analyse worden in veel wetenschaps- en technologiegebieden gebruikt voor een breed scala aan problemen. Veel onderzoekers noemen waveletanalyse een "wiskundige microscoop" voor het nauwkeurig bestuderen van de interne samenstelling en structuren van heterogene signalen en functies.

Wavelet-methoden voor signaalverwerking en -analyse mogen niet worden beschouwd als een nieuwe universele technologie voor het oplossen van problemen. De mogelijkheden van wavelets zijn nog niet volledig onthuld, maar dit betekent niet dat hun ontwikkeling zal leiden tot een volledige vervanging van traditionele middelen voor informatieverwerking en -analyse, die goed ontwikkeld en beproefd zijn. Wavelets maken het mogelijk om de instrumentele basis van informatietechnologieën voor gegevensverwerking uit te breiden.

De analyse van wavelet-transformaties van signalen wordt bepaald door de wiskundige basis van signaalontleding, die vergelijkbaar is met Fourier-transformaties. Het belangrijkste onderscheidende kenmerk van wavelet-transformaties is een nieuwe basis voor signaalontbinding: wavelet-functies. De eigenschappen van wavelets zijn van fundamenteel belang, zowel voor de mogelijkheid om signalen te ontbinden in afzonderlijke waveletfuncties, als voor gerichte acties op de waveletspectra van signalen, inclusief de daaropvolgende reconstructie van signalen met behulp van verwerkte waveletspectra.

Wavelets kunnen orthogonaal, semi-orthogonaal of biorthogonaal zijn. Wavelet-functies kunnen symmetrisch, asymmetrisch en asymmetrisch zijn, met of zonder een compact definitiedomein, en hebben ook een verschillende mate van vloeiendheid. Sommige functies hebben een analytische uitdrukking, andere hebben een snel algoritme voor het berekenen van de wavelettransformatie. Voor de praktijk zou het wenselijk zijn om orthogonaal symmetrische en asymmetrische golfjes te hebben, maar zulke ideale golfjes bestaan ​​niet. Biorthogonale golfjes worden het meest gebruikt.

De basisfuncties van wavelettransformaties kunnen een verscheidenheid aan functies zijn met een compacte draaggolf - pulsgemoduleerde sinusoïden, functies met niveausprongen, enz. Ze zorgen voor een goede weergave en analyse van signalen met lokale kenmerken, waaronder sprongen, pauzes en waardeverschillen met een grote steilheid.

Het zou wenselijk zijn om een ​​wavelet-transformatie van signalen te hebben die volledige informatie-equivalentie van het wavelet-spectrum van signalen met de tijdrepresentatie en de ondubbelzinnigheid van decompositie-reconstructie van signalen zou garanderen. Dit is echter alleen mogelijk bij gebruik van orthogonale en biorthogonale wavelets. Voor een kwalitatieve analyse van signalen en lokale kenmerken in signalen kan een uitgebreider scala aan wavelet-functies worden gebruikt, die, hoewel ze geen signaalreconstructie bieden, het mogelijk maken de informatie-inhoud van signalen en de dynamiek van veranderingen in deze informatie te evalueren. .

Wavelet-definitie. Wavelets omvatten gelokaliseerde functies die zijn opgebouwd uit één moederwavelet (t) (of een andere onafhankelijke variabele) door de bewerkingen van verschuiving langs het argument (b) en schaalverandering (a):

 ab (t) = (1/) ((t-b)/a), (a, b)R, (t)L 2 (R).

waarbij de factor (1/) de onafhankelijkheid van de norm van functies van het schaalnummer “a” garandeert.

De continue wavelet-transformatie van het signaal s(t)L 2 (R), dat wordt gebruikt voor kwalitatieve tijd-frequentieanalyse, komt in betekenis overeen met de Fourier-transformatie met de vervanging van de harmonische basis exp(-jt) door de waveletbasis ((t-b)/a ):

С(a, b) = s(t),  ab (t) = (1/)s(t)((t-b)/a) dt, (a, b)R, a 0.

Het waveletschaal-tijdspectrum C(a,b) is, in tegenstelling tot het Fourierspectrum, een functie van twee argumenten: de waveletschaal “a” (in eenheden van inverse frequentie), en de wavelettijdverschuiving langs het signaal “ b” (in tijdseenheden), in dit geval kunnen de parameters “a” en “b” elke waarde aannemen die binnen het bereik van hun definitie valt.

Rijst. 24.1.1. Wavelets Mhat en Wave.

Voor kwantitatieve analysemethoden kunnen alle gelokaliseerde functies (t) worden gebruikt als waveletbases, als er voor hen tweelingfuncties  # (t) zijn, zodat de families ( ab (t)) en (  ab ( t) ) kunnen gepaarde basen vormen van de functieruimte L 2 (R). Op deze manier gedefinieerde golfjes maken het mogelijk om elke willekeurige functie in de ruimte L 2 (R) als een reeks weer te geven:

s(t) = С(a,b)  ab (t), (a, b)I,

waarbij coëfficiënten C(a,b) de projectie zijn van het signaal op de golfbasis van de ruimte:

С(a,b) = s(t),  ab (t) =s(t) ab (t) dt.

Als de wavelet (t) de eigenschap orthogonaliteit heeft, dan is   (t) ≡ (t) en is de waveletbasis orthogonaal. Een wavelet kan echter niet-orthogonaal zijn als hij een tweeling heeft, en het paar ((t),   (t)) het mogelijk maakt families te vormen ( mk (t)) en (  zp ( t)), die voldoet aan de voorwaarde van biorthogonaliteit op gehele getallen I:

 mk (t),   zp (t) =  mz · kp , m,k,z,p О I,

dan is het mogelijk om signalen te ontbinden in waveletreeksen met de inverse reconstructieformule.

Wavelet-eigenschappen ,

Lokalisatie. De golf moet continu zijn, integreerbaar, een compacte drager hebben en zowel in tijd (in ruimte) als in frequentie gelokaliseerd zijn. Als een golfje in de ruimte smaller wordt, neemt de ‘gemiddelde’ frequentie toe, het spectrum van de golf beweegt naar een gebied met een grotere hoge frequenties en breidt zich uit.

Dit proces zou lineair moeten zijn - door de golf met de helft te verkleinen zou de “gemiddelde” frequentie en spectrale breedte ervan moeten verdubbelen. Nul gemiddeld

, d.w.z. vervulling van de voorwaarde voor nulmoment:

wat zorgt voor een nulversterking van de constante component van de signalen, een nulwaarde van het waveletfrequentiespectrum bij =0, en lokalisatie van het waveletspectrum in de vorm van een banddoorlaatfilter gecentreerd op een bepaalde (dominante) frequentie  0. Beperking.

Noodzakelijke en voldoende voorwaarde:< 

||(t)|| 2 =|(t)| 2 dt of zelfgelijkenis. De vorm van alle basisgolfjes  ab (t) moet vergelijkbaar zijn met de moedergolf (t), d.w.z. moet hetzelfde blijven tijdens verschuivingen en schaling (uitrekken/compressie), hetzelfde aantal oscillaties hebben.

Transformatie weergave . Het resultaat van de wavelettransformatie van een eendimensionale getalreeks (signaal) is een tweedimensionale reeks coëfficiëntwaarden C(a,b). De verdeling van deze waarden in de ruimte (a, b) - tijdschaal, tijdlokalisatie, geeft informatie over de verandering in de tijd van de relatieve bijdrage van waveletcomponenten van verschillende schalen in het signaal en wordt het spectrum van wavelettransformatiecoëfficiënten genoemd , schaal-tijd (tijd-frequentie) spectrum of eenvoudigweg waveletspectrum.

Het spectrum C(a,b) van een eendimensionaal signaal vertegenwoordigt een oppervlak in een driedimensionale ruimte. Spectrumvisualisatiemethoden kunnen heel verschillend zijn. De meest gebruikelijke methode is projectie op een vlak ab met isolijnen (isoniveaus), wat het mogelijk maakt om veranderingen in coëfficiënten op verschillende tijdschalen te traceren, en om een ​​beeld te identificeren van lokale extrema van deze oppervlakken (“heuvels” en “valleien”), het zogenaamde “skelet” van de structuur van het geanalyseerde proces. Voor een breed scala aan schalen kunnen logaritmische coördinaten (log A, B). Een voorbeeld van het waveletspectrum van het eenvoudigste signaal wanneer het wordt ontleed door de Mhat-wavelet, wordt getoond in Fig. 24.1.2.

Rijst. 24.1.2. Signaal, wavelet Mhat - spectrum- en schaaldelen van het spectrum.

Langs verticale secties (afschuifsecties B) waveletspectrum weerspiegelt de componentsamenstelling van het signaal (van een gegeven reeks wavelets) bij elk huidige moment. In de zin van de transformatie als een scalair product van een signaal met een wavelet, is het duidelijk dat de waarden van de coëfficiënten op elk huidig ​​tijdstip langs schaalsecties groter zijn, hoe sterker de correlatie tussen de wavelet van een bepaalde schaal en het gedrag van het signaal in de buurt van dit punt. Dienovereenkomstig laten dwarsdoorsneden voor de parameter “a” veranderingen zien in het signaal van een component van een bepaalde schaal “a” in de loop van de tijd.

De waveletcomponenten van het signaal in delen van zijn spectrum hebben niets gemeen met sinusoïden en worden in de regel weergegeven door signalen met een nogal complexe en niet altijd begrijpelijke vorm, wat hun visuele representatie en begrip kan bemoeilijken.

Wavelet-functies . De keuze voor het analyseren van wavelet wordt bepaald door welke informatie uit het signaal moet worden gehaald. Door rekening te houden met de karakteristieke kenmerken van verschillende golfjes in tijd en frequentieruimte, is het mogelijk om bepaalde eigenschappen en kenmerken in de geanalyseerde signalen te identificeren die onzichtbaar zijn in signaalgrafieken, vooral in de aanwezigheid van ruis. In dit geval hoeft het probleem van de signaalreconstructie mogelijk niet te worden gesteld, waardoor de familie van gebruikte reguliere waveletfuncties wordt uitgebreid, inclusief niet-orthogonale functies. Bovendien kan een golfje rechtstreeks worden ontworpen voor dat lokale kenmerk in het signaal dat moet worden geïsoleerd of gedetecteerd, als de vorm ervan a priori bekend is.

Bij het analyseren van signalen met golven van het even type (symmetrisch of bijna symmetrisch), komen harmonische signalen gewoonlijk overeen met heldere horizontale banden van golfpieken en dalen op de dominante golffrequenties, die samenvallen met de frequentie van de harmonischen van de signalen. Overtredingen van de signaalgladheid worden geregistreerd door verticale strepen, pieken in de signalen worden gemarkeerd door maxima, en dalen door minima van golfcoëfficiënten. Integendeel, golfjes van het vreemde type reageren scherper op sprongen en snelle veranderingen in signalen, en markeren ze met maxima of minima, afhankelijk van het teken van de verschillen. Hoe duidelijker de signaalkenmerken zijn, hoe meer ze opvallen in de spectrogrammen.

Om dergelijke golfjes te construeren, worden vaak afgeleiden van Gaussische functies gebruikt, die de beste lokalisatie hebben in zowel het tijd- als het frequentiedomein. IN algemene vorm fundamentele waveletvergelijking:

 n (x) = (-1) n +1 d n /dx n , n ≥ 1, (24.1.1)

GOLF golfje wordt berekend met behulp van de eerste afgeleide (n=1) en wordt getoond in Fig. 24.1.3 in het tijd- en frequentiedomein voor drie waarden van schaalfactoren "a". De golfvorm verwijst naar vreemde functies en dienovereenkomstig is het golfspectrum denkbeeldig. Waveletvergelijking volgens (24.1.1) met eenheidsnorm:

Rijst. 24.1.3. Golfje Golf.

MNAT-golfje (Mexicaanse hoed) wordt berekend met behulp van de tweede afgeleide (n=2) en wordt getoond in Fig. 24.1.5. De wavelet is symmetrisch, het spectrum van de wavelet wordt alleen weergegeven door het reële deel en is goed gelokaliseerd in frequentie, de nul- en eerste momenten van de wavelet zijn gelijk aan nul. Wordt gebruikt om complexe signalen te analyseren. Waveletvergelijking volgens (24.1.1):

Rijst. 24.1.5. Wavelet MHAT.

In afb. 24.1.6 toont een voorbeeld van het gebruik van een wavelet om een ​​complex signaal y(t) te analyseren. Het signaalmodel wordt gevormd door de som van signalen van verschillende structuren. Signalen y1-y2 vertegenwoordigen Gaussische functies van verschillende schaalniveaus, signaal y3 is een rechthoekige puls, signaal y4 wordt gespecificeerd als een trend met een constante differentiële waarde. Op de contourplot van waveletcoëfficiënten kunt u de identificatie van alle drie de belangrijkste signaalstructuren zien, met volledige uitsluiting van de trend. Vooral de grenzen van de sprongen van de rechthoekige structuur zijn duidelijk zichtbaar. Rechts in de figuur ziet u een volledig driedimensionaal beeld van de wavelettransformatie.

Wavelet wordt veel gebruikt in tweedimensionale vorm voor de analyse van isotrope velden. Op basis hiervan is het ook mogelijk om een ​​tweedimensionale niet-isotrope basis met goede hoekselectiviteit te construeren door de rotatie ervan toe te voegen aan de verschuivingen en schaling van de golf.

Rijst. 24.1.7.

Het praktische gevolg van het vergroten van de mate van lokalisatie van golfjes in het frequentiedomein is duidelijk zichtbaar in figuur 2. 24.1.8 met behulp van het voorbeeld van het transformeren van dezelfde functie als in Fig. 24.1.6. Vergelijking van de figuren laat een significante toename zien in de gevoeligheid van de golven voor hoogfrequente signaalcomponenten bij kleinschalige factoren.

Eigenschappen van de wavelettransformatie

De resultaten van de wavelet-transformatie bevatten, als scalair product van de wavelet en de signaalfunctie, gecombineerde informatie over het geanalyseerde signaal en de wavelet zelf. 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 s(t) aan te duiden, zullen we de index TW gebruiken.

Lineariteit .

TW[·s 1 (t)+·s 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 = C(a, b-t o).

(24.2.2) . Schaalinvariantie

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

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

(24.2.3)

Differentiatie

d n (TW)/dt n = TW.

(24.2.4) TW = (-1) n s(t) dt. (24.2.5)

Als de analyserende wavelet wordt gegeven door een formule, kan dit erg handig zijn voor signaalanalyse. Kenmerken van hoge orde of kleinschalige variaties van het signaal s(t) kunnen worden geanalyseerd door de golf of het signaal zelf het vereiste aantal keren te differentiëren.

Analoog aan de stelling van Parseval

voor orthogonale en biorthogonale golfjes.

s 1 (t) s 2 *(t) = C   a -2 С(a,b) С*(a,b) da db. (24.2.6)

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

De definities en eigenschappen van de eendimensionale continue wavelettransformatie worden gegeneraliseerd naar de multidimensionale en discrete gevallen.

24.3. Wavelet-transformatie van eenvoudige signalen.

De wavelet-transformatie, uitgevoerd bij het analyseren van signalen om eventuele kenmerken daarin en de locatie van hun lokalisatie te identificeren zonder omgekeerde reconstructie, maakt het gebruik van elk type wavelet mogelijk, zowel orthogonaal als niet-orthogonaal. Meestal worden voor deze doeleinden symmetrische golven gebruikt. Hieronder staan ​​de resultaten van het gebruik van de Mhat-wavelet om eenvoudige golfvormen te analyseren. Berekeningen worden uitgevoerd met wavelet (24.1.3) volgens de formule:

с(a,b) =s(t)(t,a,b), (24.3.1)

De secties van het spectrum laten zien dat de convolutie van enkele pulsen met golfjes van verschillende schalen de vorm van de golfjes herhaalt, zoals verwacht wordt tijdens de convolutieoperatie. Dienovereenkomstig bepalen de lijnen van maximale extrema op de secties ("ruggen" en "valleien", afhankelijk van de polariteit) de temporele positie van de pulsen, en vormen de laterale extrema van de tegenovergestelde polariteit karakteristieke lobben in de kegel van de invloedshoek , wat goed gedefinieerd is.

Rijst. 24.3.2. Transformatie van Laplace-functies.

Een vergelijkbare aard van het spectrum blijft behouden voor eventuele lokale inhomogeniteiten in signalen in de vorm van pieken (Fig. 24.3.2) met een verschuiving van de maxima (minimum) van de coëfficiënten c(a,b) van waarden a = 1 tot het gebied met grote waarden van "a" (afhankelijk van de effectieve piekbreedte).

Rijst. 24.3.3. Transformatie van Gaussische functies.

In afb. 24.3.3 toont het spectrum van Gaussische functies. Bij het gladstrijken van de toppen van piekinhomogeniteiten wordt ook de vorm van de kleurkegels gladgestreken, maar de “ridge” (“dal”) lijnen registreren vrij nauwkeurig de positie van de centra van lokale inhomogeniteiten op de tijdas.

Rijst. 24.3.4. Transformatie van differentiële constante waarde van functies.

In afb. Figuur 24.3.4 toont de spectra van twee verschillende steilheidsverschillen in de constante waarden van de functie. De middelpunten van de druppels liggen vast wanneer de waarden van de coëfficiënten c(a,b) door nul gaan, en de steilheid van de druppels wordt voornamelijk weerspiegeld in de waarden van de functie c(a,b) voor kleine waarden van de parameter “a”.

Wanneer de functies breken, registreren de spectrogrammen op betrouwbare wijze de locatie van de breuken met de maximale (minimale) waarden van de coëfficiënten c(a,b), zoals weergegeven in figuur 1. 24.3.5. Wanneer ruis op dergelijke functies wordt toegepast, wordt een nauwkeurige bepaling van de locatie van knikken met behulp van schaalsecties bij kleine waarden van de parameter "a" onmogelijk, maar bij grote waarden van de parameter "a" blijft deze mogelijkheid uiteraard bestaan, met een afname van de lokalisatienauwkeurigheid.

Rijst. 24.3.5. Transformatie van functiepauzes.

De invloed van ruis op andere lokale signalen is vergelijkbaar (Fig. 24.3.1-24.3.4). Als de spectrale kenmerken van de signalen zich uitstrekken tot het waardenbereik van de parameter “a”, dan is het mogelijk om deze signalen en hun plaats op de tijdas te identificeren.

Rijst. 24.3.6. Transformatie van harmonische functies.

De scheiding van harmonische functies op de schaalas van de spectra, inclusief de superpositie van sterke ruisprocessen, wordt getoond in de voorbeelden in Fig. 24.3.6. Het gegeven voorbeeld is louter illustratief, aangezien het raadzaam is om spectrale analyse en frequentiebanddoorlaatfilters te gebruiken om harmonische processen met een constante frequentie in de loop van de tijd te isoleren. Echter, voor lokale signalen, zoals gemoduleerde harmonischen, laten waveletspectra vrij goed de locatie van hun lokalisatie op de tijdas zien.

Rijst. 24.3.7. Het veranderen van de fase van een harmonisch signaal.

In afb. 24.3.7 toont een voorbeeld van een ander karakteristiek kenmerk van een harmonisch signaal: een faseverandering van 180 o, die goed wordt geregistreerd op alle golfschalen, en daarom vrij gemakkelijk kan worden bepaald, zelfs in de aanwezigheid van sterke ruissignalen.

Wanneer sinusoïdale signalen op een trend worden gesuperponeerd, maakt de wavelettransformatie op grote schaal het mogelijk om met vertrouwen de karakteristieke kenmerken van de trend te identificeren. Een voorbeeld van het identificeren van trendbreuken wordt getoond in Fig. 24.3.8.

Rijst. 24.3.8. Het omzetten van de som van drie signalen.

De vorm van de wavelet (even of oneven), de dominante frequentie en de mate van lokalisatie ervan beïnvloeden aanzienlijk de waveletspectra van de geanalyseerde signalen en de mogelijkheid om de lokale kenmerken ervan te identificeren. De volgende figuren tonen vergelijkende spectra van eenvoudige signalen met behulp van wavelets Wave (oneven, Fig. 24.1.3), Mhat (even, Fig. 24.1.5) en een wavelet gebaseerd op de 8e afgeleide van Gauss (Fig. 24.3.9-24.3 .16), die ook even is, en een vier keer hogere dominante frequentie heeft dan de Mhat-golf.

Rijst. 24.3.9. Kronecker-impulsen.

Rijst. 24.3.10. Pieken van Laplace.

Rijst. 24.3.11. Gaussische functies.

Rijst. 24.3.12. Coole sprongen.

Rijst. 24.3.13. Gladde sprongen.

Rijst. 24.3.14. Functie knikt

Rijst. 24.3.15. Fasesprongen van harmonischen.

Rijst. 24.3.16. De som van twee gemoduleerde sinusoïden.

Bij het analyseren van willekeurige signalen maakt het gebruik van verschillende soorten wavelets het mogelijk om de betrouwbaarheid van het identificeren van lokale signaalkenmerken te vergroten.

Wavelet-transformatieprincipe. De harmonische basisfuncties van de Fourier-transformatie zijn extreem gelokaliseerd in het frequentiedomein (tot aan de Dirac-impulsfuncties op T) en zijn niet gelokaliseerd in de tijd (gedefinieerd in het gehele tijdsinterval van - tot). Het tegenovergestelde zijn impulsbasisfuncties zoals Kronecker-impulsen, die extreem gelokaliseerd zijn in het tijdsdomein en ‘wazig’ zijn over het hele frequentiebereik. Lokalisatiegolfjes in deze twee representaties kunnen worden beschouwd als functies die een tussenpositie innemen tussen harmonische en impulsfuncties. Ze moeten gelokaliseerd zijn in zowel het tijd- als het frequentiedomein van representatie. Bij het ontwerpen van dergelijke functies zullen we echter onvermijdelijk het onzekerheidsprincipe tegenkomen, dat de effectieve waarden van de duur van functies en de breedte van hun spectrum met elkaar in verband brengt. Hoe nauwkeuriger we de temporele positie van een functie lokaliseren, hoe breder het spectrum ervan zal worden, en vice versa, wat duidelijk te zien is in figuur 2. 1.1.5.

Een onderscheidend kenmerk van waveletanalyse 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 is raadzaam om de waveletbasis van de ruimte L 2 (R), R(-,) te construeren uit eindige functies die tot dezelfde ruimte behoren en die in het oneindige naar nul zouden moeten neigen. Hoe sneller deze functies naar nul neigen, des te handiger is het om ze te gebruiken als transformatiebasis bij het analyseren van echte signalen. Laten we aannemen dat zo'n functie psi is - een functie t die buiten een bepaald eindig interval gelijk is aan nul en een gemiddelde nulwaarde heeft over het gespecificeerde interval. Dit laatste is nodig om de lokalisatie van het waveletspectrum in het frequentiedomein te specificeren. Op basis van deze functie construeren we een basis in de ruimte L 2 (R) met behulp van schaaltransformaties van de onafhankelijke variabele.

De functie van het veranderen van de frequentie-onafhankelijke variabele in de spectrale weergave van signalen wordt weergegeven in de tijdweergave door het signaal uit te rekken/comprimeren. Voor een waveletbasis kan dit worden gedaan met een functie als (t) =>(a m t), a = const, m = 0, 1, …, M, d.w.z. door een lineaire uitrek-/krimpoperatie die gelijkheid van de functie op verschillende representatieschalen garandeert. De locatie van de functie(t) op de tijdas vereist echter een extra onafhankelijke variabele van opeenvolgende verschuivingen van de functie(t) langs de as, zoals(t) =>(t+k), om bestrijk de gehele numerieke as van ruimte R(-, ). Wanneer beide voorwaarden tegelijkertijd in aanmerking worden genomen, kan de structuur van de basisfunctie als volgt worden aangenomen:

(t) => (a m t+k).

(1.1.10)

Om verdere berekeningen te vereenvoudigen, nemen we de waarden van de variabelen m en k als geheel getal. Wanneer we de functie (1.1.10) terugbrengen tot de eenheidsnorm, verkrijgen we:

 mk (t) = a m/2 (a m t+k).

(1.1.11)

Als voor een familie van functies  mk (t) aan de orthogonaliteitsvoorwaarde is voldaan:

 nk (t), lm (t)= nk (t)·* lm (t) dt = nl · km , (1.1.12)

dan kan de familie  mk (t) gebruikt worden als orthonormale basis van de ruimte L 2 (R). Een willekeurige functie van deze ruimte kan worden uitgebreid tot een reeks ten opzichte van de basis mk (t):

s(t) =S mk  mk (t), (1.1.13)

waarbij de coëfficiënten S m k de projecties zijn van het signaal op een nieuwe orthogonale basis van functies, zoals bij de Fourier-transformatie, worden ze bepaald door het scalaire product

S mk = s(t),  mk (t) =s(t) mk (t) dt, (1.1.14)

in dit geval convergeert de reeks uniform:

||s(t) –S mk  mk (t),|| = 0.

Wanneer aan deze voorwaarden is voldaan, wordt de basistransformatiefunctie (t) een orthogonale wavelet genoemd. (1.1.15)

Het eenvoudigste voorbeeld van een orthogonaal systeem van functies van dit type zijn de Haar-functies. De Haar-basisfunctie wordt gedefinieerd door de relatie

(t) =

Het is gemakkelijk om te controleren dat voor a = 2, m = 0, 1, 2, ..., k = 0, 1,2, ... elke twee functies verkregen met behulp van deze basiswavelet door het schalen van transformaties en overdrachten een eenheidsnorm hebben en orthogonaal. In afb. 1.1.6 toont voorbeelden van functies voor de eerste drie waarden van m en b voor hun verschillende combinaties, waarbij de orthogonaliteit van de functies duidelijk zichtbaar is. , in tegenstelling tot de Fourier-transformatie, is tweedimensionaal en definieert een tweedimensionaal oppervlak in de ruimte van variabelen m en k. In een grafische weergave is de spectrumuitbreidings-/compressieparameter m uitgezet langs de abscis-as, en de lokalisatieparameter k langs de ordinaat-as - de as van de onafhankelijke variabele van het signaal. Laten we de wiskunde van het proces van wavelet-ontbinding van een signaal in vereenvoudigde vorm bekijken met behulp van het voorbeeld van de ontleding van een signaal s(t) door een Haar-wavelet met drie opeenvolgende schaal m-waveletfuncties met parameter a=2, terwijl de signaal s(t) zelf wordt gevormd door het optellen van dezelfde waveletfuncties met dezelfde amplitude met verschillende verschuivingen vanaf nul, zoals weergegeven in figuur 2. 1.1.7.

Rijst. 1.1.7. Scalaire producten van een signaal met golfjes.

Voor de initiële waarde van de compressieschaalfactor m wordt de waveletfunctie bepaald (1(t) in figuur 1.1.7), en het scalaire product van het signaal met de wavelet1(t), s(t). +k)met het shift-argument wordt k berekend. Voor de duidelijkheid: de resultaten van het berekenen van scalaire producten in Fig. 1.1.7 zijn geconstrueerd op basis van de middelpunten van waveletfuncties (dat wil zeggen gebaseerd op het argument k vanaf nul met een verschuiving van de helft van de lengte van de waveletfunctie). Zoals je zou verwachten, worden de maximale waarden van het scalaire product genoteerd waar dezelfde waveletfunctie is gelokaliseerd.

Na het construeren van de eerste schaallijn van de uitbreiding verandert de schaal van de waveletfunctie (2 in figuur 1.1.7) en wordt de tweede schaallijn van het spectrum berekend, enz.

Zoals te zien is in afb. 1.1.7: hoe nauwkeuriger het lokale kenmerk van het signaal samenvalt met de overeenkomstige golffunctie, des te effectiever is de identificatie van dit kenmerk op de overeenkomstige schaallijn van het golfspectrum. Het is duidelijk dat voor een sterk gecomprimeerde Haar-golf een karakteristiek, goed geïdentificeerd lokaal kenmerk een signaalsprong is, en niet alleen de functiesprong wordt onderscheiden, maar ook de richting van de sprong.

In afb. 1.1.8 toont een voorbeeld van een grafische weergave van het golfoppervlak van een echt fysiek proces /4/. Het type oppervlak bepaalt de veranderingen in de tijd van spectrale componenten van verschillende schalen en wordt het tijdfrequentiespectrum genoemd. Het oppervlak wordt weergegeven in tekeningen, meestal in de vorm van isolijnen of conventionele kleuren. Om het scala aan schalen uit te breiden, kan een logaritmische schaal worden gebruikt.

12.3 Discreet wavelettransformatie-algoritme

Om een ​​discreet wavelet-transformatie-algoritme te construeren, introduceren we er 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. Het punt is dat de constructie van het algoritme discrete transformatie is volledig gebaseerd op de theorie van discrete transformatie in de basis van waveletfuncties (zie 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 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 . Feit is dat het in dit geval behouden van de uitzettingscoëfficiënten op elk niveau ervoor zorgt dat de uiteindelijke schatting alleen de oorspronkelijke gegevens herhaalt.

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, dit feit niet besproken in de literatuur.

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

• 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) V 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 we de inverse matrix voor H vinden, zal het decoderen eenvoudigweg bestaan ​​uit het vermenigvuldigen van vectoren met halve sommen en halve verschillen ermee.

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 de algemene vorm van het gezicht en 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.