Compression de courbe

La compression de courbe (curve-fitting compaction)[1]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.

Compression de courbe (15 -> 6 points)

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érauxModifier

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.

ApplicationsModifier

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

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 œuvreModifier

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.

AlgorithmesModifier

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

Compression par régression polynomialeModifier

Une séquence de n points est représentée par un polynôme dont le degré p est 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 ; 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).

Codage par quantification scalaireModifier

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.

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 splineModifier

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.

Notes et référencesModifier

  1. (en-US) « curve-fitting compaction – Glossary » (consulté le )

Voir aussiModifier

BibliographieModifier

  • 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 connexesModifier