Kurvekompresjon

Den kurve for kompresjons ( kurvetilpasnings-komprimering ) er en metode for datakomprimering som brukes for lagring eller overføring av data. Det utføres ved å erstatte et analytisk uttrykk ( kurvetilpasning) for kurven . Parametrene til det analytiske uttrykket brukes deretter til å representere kurven.

Dekompresjon er den omvendte funksjonen som gjør det mulig å rekonstruere kurven fra parametrene.

Kurvekomprimering kan gjøres mot flere mål:

erstatte kurven med et sett med rette linjesegmenter hver representert av et punkt, en skråning og en lengde;
bruk av et matematisk uttrykk, for eksempel en polynomfunksjon. Kurven er representert av koeffisientene til polynomet.

Generelle prinsipper

Begrepet kurve refererer til begrepet en plan kurve . Dette er for eksempel tilfelle med kurver som representerer tidsserier .

For å kunne brukes numerisk, må kurven være representert med et sett med diskrete verdier ( sampling ). Valget av antall verdier avhenger av informasjonsvolumet som skal behandles og ønsket presisjon.

Den trykket er da å erstatte alle de verdier som er registrert av alle parametere. Det er definert av et kompresjonsforhold og en kompresjonsfeil (målt ved å sammenligne de opprinnelige verdiene med verdiene som er oppnådd på slutten av en kompresjons / dekompresjonssyklus). Valget av kompresjonsmetode er et kompromiss mellom kompresjonsforholdet og kompresjonsfeilen.

Kompresjon utføres langs to akser:

en reduksjon i mengden informasjon (overføring fra et antall punkter til et redusert antall parametere);
en forringelse av kvaliteten på informasjonen (koding av parametrene på et redusert antall biter).

I begge tilfeller ledsages det vanligvis av tap av informasjon (ikke-komprimeringsfeil).

Kompresjonsmetodene som reduserer antall punkter på kurven er hovedsakelig regresjonsmetoder . Den mest kjente metoden er lineær regresjon som kan reduseres til en linje som best nærmer seg punktene ( affinjustering ) i tilfelle en lineær regresjon med to parametere.

Kompresjonen kan også integrere et utjevningstrinn i tilfelle der parasittiske variasjoner er lagt på kurven (eksempel på støyende målinger) . Utjevning kan gjøres før komprimering ( digitalt filter ) eller etter komprimering.

De vanligste teknikkene er enkel filtrering før komprimering ( eksponentiell utjevning , glidende gjennomsnitt osv.). Andre teknikker som glatting av splines kan brukes etter komprimering.

Den koding blir brukt til å representere parametrene med en minimal mengde med informasjon. Det oppnås ved hjelp av datakomprimeringsteknikker som kan være "lossy" eller "lossless".

Tapsfri koding kan oppnås ved hjelp av "bitpakking" -teknikker som består i ikke lenger å lagre tallene med faste lengder (byte som inneholder sekvenser på 0), men med variable størrelser avhengig av antallet som skal vises.

Den skalære kvantiseringen er en enkel kodingsmetode med tap. Hvis amplituden er 20, vil verdien 15 kodet på 3 biter (8 mulige verdier) være 110. Maksimal kodefeil eller forvrengning vil da være 20/8, dvs. 2,5.

applikasjoner

Kurvekompresjon brukes i områder der:

dataene uttrykkes i form av kurver ( f.eks. tidsserie av målinger );
lagringsvolumet reduseres ( f.eks. bruk av mikrokontrollere );
overføringskapasitet er begrenset ( f.eks. LPWAN- nettverk : LoraWan , Sigfox ).

De to siste begrensningene er ofte assosiert med begrenset behandlingskapasitet, noe som fører til å favorisere komprimeringsmetoder med lavt algoritmisk kompleksitet.

For eksempel autoriserer Sigfox-nettverksprotokollen sending av 140 meldinger på 12 byte per dag. Uten komprimering kan 12 byte lagre 3 flytpunktsverdier. Vi kan derfor sende 420 verdier per dag, dvs. tilsvarer en verdi hvert 4. minutt. Med et kompresjonsforhold på 10 kan en sendt melding inneholde tilsvarende 30 verdier. 4200 verdier kan deretter sendes per dag, dvs. tilsvarer en verdi hvert 21. sekund.

Gjennomføring

Implementeringen av en kurvekomprimering krever å definere på forhånd:

parametrene som deles i kompresjons- og dekompresjonsfasen (kompresjonshastighet, antall kodende biter, etc.)
informasjonen som sendes etter komprimering (parametere, feilrate)

Deretter følger kompresjonen flere påfølgende faser. Kompresjon blir fremstilt oppstrøms med en normalisering av kurven, det vil si en skalering av den, ledsaget av andre operasjoner som klipping eller filtrering. Deretter blir kurven effektivt komprimert av komprimeringsalgoritmen, og resultatdataene blir transformert til binære data klare for sending.

Den omvendte operasjonen utføres etter samme logikk, det vil si først ved å dekode den binære kurven, deretter ved å dekomprimere den, og til slutt ved å denormalisere den.

Algoritmer

Dette kapittelet presenterer eksempler på algoritmer som reagerer på ovennevnte brukssaker.

Kompresjon ved polynomisk regresjon

En sekvens av n poeng er representert av et polynom der graden p er fast (komprimeringsmål).

Parametrene til polynomet oppnås ved å minimere den kvadratiske forskjellen mellom verdiene som skal komprimeres og verdiene beregnet av polynomet.

Når p = 1 er polynomkurven konstant, og sekvensen representeres av middelverdien
Når p = 2 er polynomkurven en rett linje, som utgjør en lineær regresjon
Når p = n, passerer polynomkurven gjennom alle punktene; kompresjon utføres da bare på kodingen.

Flere scenarier for å implementere en polynomial regresjon kan vurderes:

bruk av en enkelt regresjon (ikke aktuelt når graden av polynom er viktig);
dele kurven i seksjoner med en regresjon for hver av dem (kompenserer for grensene for en enkelt regresjon);
bruk av blandede løsninger (enkelt regresjon etterfulgt av flere regresjoner på kurven for restavvik).

Algoritme for beregning av kompresjon ved polynomregresjon

Rangeringer:

Kurve: sett med koordinatpunkter $(x_i, y_i)$
Polynomkurve: sett med koordinatparameterpunkter ${\ displaystyle (xp_ {i}, yp_ {i})}$
Polynom av ligningsgrad: $s$ ${\ displaystyle y = a_ {0} + a_ {1} * x ^ {1} + \ cdots + a_ {p-1} * x ^ {p-1}}$
Verdier å komprimere: ${\ displaystyle Y = (y_ {0}, y_ {1}, \ cdots, y_ {n-1})}$
Anslåtte verdier: ${\ displaystyle {\ hat {Y}} = ({\ hat {y_ {0}}}, {\ hat {y_ {1}}}, \ cdots, {\ hat {y_ {n-1}}}) }$
Innstillinger: ${\ displaystyle P = (a_ {0}, a_ {1}, \ cdots, a_ {p-1})}$
Parameterverdier: ${\ displaystyle YP = (yp_ {0}, yp_ {1}, \ cdots, yp_ {p-1})}$

Kompresjonsberegninger:

Matrise med ${\ displaystyle S (p \ times p)}$ ${\ displaystyle S_ {i, j} = \ sum _ {k = 0} ^ {n-1} x_ {k} ^ {i + j}}$
Matrise med $T (p)$ ${\ displaystyle T_ {j} = \ sum _ {i = 0} ^ {n-1} y_ {i} * x_ {i} ^ {j}}$
Matrise med ${\ displaystyle XP (p \ ganger p)}$ ${\ displaystyle XP_ {i, j} = xp_ {i} ^ {j}}$

Parameterpunktene til kurven bekrefter ligningen: ${\ displaystyle YP = XP \ times S ^ {- 1} \ times T}$

Beregninger for dekompresjon:

Matrise med ${\ displaystyle X (n \ ganger p)}$ ${\ displaystyle X_ {i, j} = x_ {i} ^ {j}}$

De estimerte verdiene verifiserer ligningen: ${\ displaystyle {\ hat {Y}} = X \ ganger XP ^ {- 1} \ ganger YP}$

Merknader:

I stedet for å bruke parameteren for komprimering , bruker vi parameteren (med en likeverdifordeling av verdier ) for å lette påfølgende koding (kjent verdiområde) $P$ ${\ displaystyle YP}$ ${\ displaystyle xp}$
Eksempler på implementering på denne lenken

Skalar kvantisering koding

Den skalære kvantiseringen skal representere et verdiområde for en enkelt verdi (å miste informasjon). I sammenheng med en komprimeringsalgoritme, søkes det å representere en digital verdi av et verdiområde som er fiksert av en binær koding med et definert antall biter.

Skalarkvantiseringskodingsalgoritme

notasjoner:

Verdiene som skal kodes er parametrene som varierer i samme amplitude som verdiene som skal komprimeres ${\ displaystyle YP}$
Kodingen av verdiene gjøres på et antall biter $b$
Amplituden til verdiene som skal kodes er definert av en minimumsverdi og en maksimumsverdi $m$ $M$
Kodede verdier: ${\ displaystyle YB = (yb_ {0}, yb_ {1}, \ cdots, yb_ {p-1})}$

koding:

Kodede verdier varierer mellom og ${\ displaystyle 0}$ ${\ displaystyle 2 ^ {b} -1}$

${\ displaystyle yb_ {i} = Int {\ biggl (} {\ frac {yp_ {i} -m} {Mm}} \ times 2 ^ {b} {\ biggr)}}$ med ${\ displaystyle yb_ {i} \ in [0,2 ^ {b} -1]}$

De blir deretter konvertert til en serie biter

${\ displaystyle yb_ {i} = bit_ {p-1} 2 ^ {p-1} + \ cdots + bit_ {1} 2 ^ {1} + bit_ {0}}$

dekoding:

Dekodede verdier tilnærmes med midten av hvert kvantiseringsintervall

${\ displaystyle {\ hat {yp}} _ {i} = m + (Mm) {\ frac {yb_ {i} +0.5} {2 ^ {b}}}}$

Merk :

Den maksimale kodings- / dekodingsfeilen for hver verdi er ${\ displaystyle {\ frac {Mm} {2 ^ {b}}}}$

Denne typen koding er egnet når verdiene som skal kodes utforske hele det definerte området. Men i tilfelle hvor variasjonsområdet for verdiene er mye mindre enn det faste verdiområdet, vil kodingen ikke gjøre det mulig å representere variasjonene av verdiene som skal kodes korrekt. I dette tilfellet må vi bruke ikke-ensartede eller adaptive skalare kvantifiserere.

Splineutjevning

Den glatting spline benyttes etter komprimeringen av polynom regresjon. Det gjelder punktene som definerer polynomet og ikke koeffisientene til polynomet.

Spline-utjevningsalgoritme

Algoritmen er beskrevet på siden dedikert til spline.

Merknader og referanser

(no-US) “ kurvetilpasning - Ordliste ” (åpnet 6. desember 2019 )

Se også

Bibliografi

E. Moulines, " Casestudie for ikke-parametrisk regresjon ".
Numeriske metoder for kurvetilpasning. Av PG Guest, Philip George Guest.
Regresjonsanalyse av Rudolf J. Freund, William J. Wilson, Ping Sa
Ahn, Sung-Joon (desember 2008), "Geometric Fitting of Parametric Curves and Surfaces" (PDF), Journal of Information Processing Systems
Ahlberg & Nilson (1967) Teorien om splines og deres applikasjoner, Academic Press

Relaterte artikler