Compression de courbe

Notations :

• Courbe : ensemble de points de coordonnées ${\displaystyle (x_{i},y_{i})}$
• Courbe polynomiale : ensemble de points paramètres de coordonnées ${\displaystyle (xp_{i},yp_{i})}$
• Polynôme de degré ${\displaystyle p}$ d'équation : ${\displaystyle y=a_{0}+a_{1}*x^{1}+\cdots +a_{p-1}*x^{p-1}}$
• Valeurs à compresser : ${\displaystyle Y=(y_{0},y_{1},\cdots ,y_{n-1})}$
• Valeurs estimées : ${\displaystyle {\hat {Y}}=({\hat {y_{0}}},{\hat {y_{1}}},\cdots ,{\hat {y_{n-1}}})}$
• Paramètres :${\displaystyle P=(a_{0},a_{1},\cdots ,a_{p-1})}$
• Valeurs paramètres :${\displaystyle YP=(yp_{0},yp_{1},\cdots ,yp_{p-1})}$

Exemple de paramètres pour une compression sur 6 points

Calculs pour la compression :

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

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

Calculs pour la décompression :

• Matrice ${\displaystyle X(n\times p)}$ avec ${\displaystyle X_{i,j}=x_{i}^{j}}$

Les valeurs estimées vérifient l'équation : ${\displaystyle {\hat {Y}}=X\times XP^{-1}\times YP}$

Remarques :

• Plutôt que d'utiliser pour la compression le paramètre ${\displaystyle P}$, on utilise le paramètre ${\displaystyle YP}$(avec une équi-répartition des valeurs ${\displaystyle xp}$) pour faciliter le codage ultérieur (plage de valeur connue)
• Exemples d'implémentation sur ce lien

notations :

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

codage :

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

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

• Elles sont ensuite converties en suite de bits

${\displaystyle 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

${\displaystyle {\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 ${\displaystyle {\frac {M-m}{2^{b}}}}$

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