title: Compression de courbe
text: # Compression de courbe
  
  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.
  
  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).
  
  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.
  
  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.
  
  ## 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).
  
  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})$
  
  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.
  
  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.
  
  L'algorithme est décrit sur la page dédiée au spline.
  
  