Compression de courbe

Compression de courbe (15 → 6 points)

La compression de courbe (curve-fitting compaction)est une méthode de compression de données utilisée pour le stockage ou la transmission de données. Elle est réalisée en substituant à la courbe une expression analytique (ajustement de courbe). Les paramètres de l'expression analytique sont alors utilisés pour représenter la courbe.

La décompression est la fonction inverse qui permet de reconstruire la courbe à partir des paramètres.

La compression de courbe peut se faire vers plusieurs objectifs :

• remplacement de la courbe par un ensemble de segments de droites représentés chacun par un point, une pente et une longueur ;
• utilisation d'une expression mathématique, comme une fonction polynomiale. La courbe est représentée par les coefficients du polynôme.

Principes généraux

Le concept de courbe fait référence à la notion de courbe plane. C'est le cas par exemple des courbes représentant des séries temporelles.

Pour être exploitée de façon numérique la courbe doit être représentée par un ensemble de valeurs discrètes (échantillonnage). Le choix du nombre de valeurs dépend du volume d'information à traiter et de la précision souhaitée.

Régression polynomiale (degré polynôme)

La compression consiste alors à remplacer l'ensemble des valeurs échantillonnées par l'ensemble des paramètres. Elle est définie par un taux de compression et une erreur de compression (mesurée en comparant les valeurs initiales aux valeurs obtenues à l'issue d'un cycle de compression/décompression). Le choix de la méthode de compression est un compromis entre le taux de compression et l'erreur de compression.

La compression s'effectue suivant deux axes :

• une réduction de la quantité d'informations (passage d'un nombre de points à un nombre de paramètres réduit) ;
• une dégradation de la qualité de l'information (codage des paramètres sur un nombre de bits réduit).

Dans les deux cas, elle s'accompagne généralement d'une perte d'information (erreur de compression non nulle).

Lissage de paramètres

Les méthodes de compression qui permettent de réduire le nombre de points de la courbe sont principalement les méthodes de régression. La méthode la plus connue est la régression linéaire qui peut se réduire à une droite approchant au mieux les points (ajustement affine) dans le cas d'une régression linéaire à deux paramètres.

La compression peut également intégrer une étape de lissage dans le cas où des variations parasites se superposent à la courbe (exemple de mesures bruitées). Le lissage peut s'effectuer avant compression (filtre numérique) ou après compression.

Codage (nombre de bits utilisés)

Les techniques les plus courantes sont le filtrage simple avant compression (lissage exponentiel, moyenne mobile…). D'autres techniques comme les splines de lissage peuvent être utilisées après compression.

Le codage est utilisé pour représenter les paramètres avec un volume minimal d'information. Il est réalisé par des techniques de compression de données qui peuvent être "avec perte" ou "sans perte".

Un codage sans perte peut être obtenu par des techniques de "bit-packing" qui consistent à ne plus stocker les nombres avec des longueurs fixes (octets comportant des séquences de 0) mais avec des tailles variables en fonction du nombre à représenter.

La quantification scalaire est une méthode de codage simple avec perte. Si l'amplitude est de 20, la valeur de 15 codée sur 3 bits (8 valeurs possibles) sera 110. L'erreur de codage maximale ou distorsion sera alors de 20 / 8 soit 2,5.

Applications

La compression de courbe est utilisée dans les domaines pour lesquels :

• les données s'expriment sous forme de courbes (ex. : séries temporelles de mesures);
• le volume de stockage est réduit (ex. : utilisation de microcontroleurs);
• les capacités de transmission sont limitées (ex. : réseaux LPWAN : LoraWan, Sigfox).

Les deux dernières contraintes sont souvent associées à des capacités de traitement limitées, ce qui conduit à privilégier des méthodes de compression avec un niveau de complexité algorithmique faible.

Par exemple, le protocole du réseau Sigfox autorise un envoi de 140 messages de 12 octets par jour. Sans compression, 12 octets permettent de stocker 3 valeurs en virgule flottante. On peut donc envoyer 420 valeurs par jour soit l'équivalent d'une valeur toutes les 4 minutes. Avec un taux de compression de 10, un message envoyé peut contenir l'équivalent de 30 valeurs. On peut alors envoyer 4 200 valeurs par jour soit l'équivalent d'une valeur toutes les 21 secondes.

Mise en œuvre

La mise en œuvre d'une compression de courbe nécessite de définir au préalable :

• les paramètres partagés en phase de compression et de décompression (taux de compression, nombre de bits de codage…)
• les informations émises à l'issue de la compression (paramètres, taux d'erreur)

Par la suite, la compression suit plusieurs phases successives. La compression est préparée en amont avec une normalisation de la courbe, c'est-à-dire une mise à l'échelle de celle-ci, accompagnée d'autres opérations comme un écrêtage ou un filtrage. Ensuite, la courbe est effectivement compressée par l'algorithme de compression, et les données résultats sont transformées en données binaires prêtes à l'envoi.

L'opération inverse s'effectue selon la même logique, c'est-à-dire d'abord en décodant la courbe binaire, puis en la décompressant, et finalement en la dénormalisant.

Mise en oeuvre des méthodes de compression de courbe

Algorithmes

Ce chapitre présente des exemples d'algorithmes répondant aux cas d'usage ci-dessus.

Compression par régression polynomiale

Une séquence de n points est représentée par un polynôme caractérisé par p points (donc de degré p-1) avec p fixé (objectif de la compression).

Les paramètres du polynôme sont obtenus en minimisant l'écart quadratique entre les valeurs à compresser et les valeurs calculées par le polynôme.

• Lorsque p = 1, la courbe polynomiale est constante, et la séquence est représentée par sa moyenne
• Lorsque p = 2, la courbe polynomiale est une droite, ce qui revient à une régression linéaire
• Lorsque p = n, la courbe polynomiale passe par tous les points (on revient au cas d'interpolation lagrangienne) ; la compression s'effectue alors uniquement sur le codage.

Plusieurs scénarios de mise en œuvre d'une régression polynomiale peuvent être envisagés :

• utilisation d'une régression unique (non applicable lorsque le degré du polynôme est important) ;
• découpage de la courbe en tronçons avec une régression pour chacun d'eux (permet de compenser les limites d'une régression unique) ;
• utilisation de solutions mixtes (régression unique suivi de régressions multiples sur la courbe des écarts résiduels).

Algorithme de calcul d'une compression par régression polynomiale

On note :

• l'ensemble de points de coordonnées $(x_{i},y_{i})$
• l'ensemble de points paramètres de coordonnées $(x_{i}^{P},y_{i}^{P})$

On cherche donc un polynôme de degré p-1 d'équation : $y=a_{0} a_{1}x^{1} \cdots a_{p-1}x^{p-1}$

• Valeurs à compresser : $Y=(y_{0},y_{1},\cdots ,y_{n-1})$
• Valeurs estimées : ${\hat {Y}}=({\hat {y_{0}}},{\hat {y_{1}}},\cdots ,{\hat {y_{n-1}}})$
• Paramètres :$P=(a_{0},a_{1},\cdots ,a_{p-1})$
• Valeurs paramètres :$Y^{P}=(y_{0}^{P},y_{1}^{P},\cdots ,y_{p-1}^{P})$

Exemple de paramètres pour une compression sur 6 points

En écrivant le système d'équations à résoudre, il apparait :

• la matrice $S$ de taille $p\times p$ avec $S_{i,j}=\sum _{k=0}^{n-1}x_{k}^{i j}$
• le vecteur $T$ de taille p avec $T_{j}=\sum _{i=0}^{n-1}y_{i}x_{i}^{j}$
• la matrice $X^{P}$ de taille $p\times p$ avec $X_{i,j}^{P}=(x_{i}^{P})^{j}$

Les points paramètres de la courbe vérifient l'équation : $Y^{P}=X^{P}\times S^{-1}\times T$

Le calculs pour la décompression fait intervenir une matrice de Vandermonde $X$ de taille $n\times p$ avec $X_{i,j}=x_{i}^{j}$

Les valeurs estimées vérifient l'équation : ${\hat {Y}}=X\times (X^{P})^{-1}\times Y^{P}$

Remarques :

• Plutôt que d'utiliser pour la compression le paramètre $P$, on utilise le paramètre $YP$(avec une équirépartition des valeurs $x^{P}$) pour faciliter le codage ultérieur (plage de valeur connue)

 

Codage par quantification scalaire

La quantification scalaire consiste à représenter un intervalle de valeurs par une valeur unique (perte d'information). Dans le cadre d'un algorithme de compression on cherche à représenter une valeur numérique d'une plage de valeurs fixée par un codage binaire avec un nombre de bits défini.

Algorithme de codage par quantification scalaire

notations :

• Les valeurs à coder sont les paramètres $YP$ qui varient dans la même amplitude que les valeurs à compresser
• Le codage des valeurs se fait sur un nombre de bits $b$
• L'amplitude des valeurs à coder est définie par une valeur minimale $m$ et une valeur maximale $M$
• Valeurs codées : $YB=(yb_{0},yb_{1},\cdots ,yb_{p-1})$

codage :

• Les valeurs codées varient entre $0$ et $2^{b}-1$

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

• Elles sont ensuite converties en suite de bits

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

décodage :

• Les valeurs décodées sont approximées par le milieu de chaque intervalle de quantification

${\hat {yp}}_{i}=m (M-m){\frac {yb_{i} 0.5}{2^{b}}}$

remarque :

• L'erreur de codage/décodage maximale de chaque valeur est de ${\frac {M-m}{2^{b}}}$

 

Ce type de codage est adapté lorsque les valeurs à coder explorent toute la plage définie. Mais dans le cas où la plage de variation des valeurs est beaucoup plus faible que la plage de valeurs fixée, le codage ne permettra pas de représenter correctement les variations des valeurs à coder. On doit alors dans ce cas utiliser des quantificateurs scalaires non uniformes ou adaptatifs.

Lissage par spline

Le lissage par spline est utilisé après compression par régression polynomiale. Il s'applique sur les points définissant le polynôme et non sur les coefficients du polynôme.

Algorithme de lissage par spline

L'algorithme est décrit sur la page dédiée au spline.

 

Voir aussi

Bibliographie

• E. Moulines, «Étude de cas de régression non paramétrique».
• Numerical Methods of Curve Fitting. By P. G. Guest, Philip George Guest.
• Regression Analysis By Rudolf J. Freund, William J. Wilson, Ping Sa
• Ahn, Sung-Joon (December 2008), "Geometric Fitting of Parametric Curves and Surfaces" (PDF), Journal of Information Processing Systems
• Ahlberg & Nilson (1967) The theory of splines and their applications, Academic Press

Articles connexes

• compression de données
• ajustement de courbe
• échantillonage
• régression
• régression linéaire
• régression polynomiale
• filtre numérique
• lissage exponentiel
• moyenne mobile
• Spline de lissage
• codage
• quantification scalaire