Interpolation bicubique

Illustration de l'interpolation bicubique sur un ensemble de données aléatoires

En mathématiques, l'interpolation bicubique est une extension de l'interpolation cubique pour interpoler un ensemble de points distribués sur une grille régulière bidimensionnelle. La surface interpolée est plus lisse que les surfaces correspondantes obtenues par interpolation bilinéaire ou par sélection du plus proche voisin. L'interpolation bicubique peut être accomplie en utilisant soit des polynômes de Lagrange, soit des splines cubiques, soit un algorithme de convolution cubique.

Dans le domaine du traitement d'images numériques, l'interpolation bicubique est souvent préférée à une interpolation bilinéaire ou à la technique du plus proche voisin pour le ré-échantillonnage d'images, lorsque le temps de traitement n'est pas critique. Contrairement à une interpolation bilinéaire, qui ne prend que 4 pixels (2 × 2) en compte, l'interpolation bicubique considère un voisinage de 16 pixels (4 × 4). Les images ré-échantillonnées par une interpolation bicubique sont donc plus lisses et ont moins d'artefacts d'interpolation.

Développement

Supposons que les valeurs de la fonction ${\displaystyle f}$ et les dérivés ${\displaystyle f_{x}}$, ${\displaystyle f_{y}}$ et ${\displaystyle f_{xy}}$ sont connues aux quatre coins ${\displaystyle (0,0),(1,0),(0,1)}$ et ${\displaystyle (1,1)}$ d'un carré unitaire. La surface interpolée peut alors être écrite :

${\displaystyle p(x,y)=\sum _{i=0}^{3}\sum _{j=0}^{3}a_{ij}x^{i}y^{j}.}$

Le problème de l'interpolation consiste à déterminer les seize coefficients ${\displaystyle a_{ij}}$. La fonction ${\displaystyle f}$ évaluée en ces quatre points, nous donne ces quatre équations :

1. ${\displaystyle f(0,0)=p(0,0)=a_{00}}$
2. ${\displaystyle f(1,0)=p(1,0)=a_{00}+a_{10}+a_{20}+a_{30}}$
3. ${\displaystyle f(0,1)=p(0,1)=a_{00}+a_{01}+a_{02}+a_{03}}$
4. ${\displaystyle f(1,1)=p(1,1)=\textstyle \sum _{i=0}^{3}\sum _{j=0}^{3}a_{ij}}$

De même, en évaluant les dérivées partielles ${\displaystyle f_{x}}$ et ${\displaystyle f_{y}}$ à ces quatre points, on obtient les huit équations :

1. ${\displaystyle f_{x}(0,0)=p_{x}(0,0)=a_{10}}$
2. ${\displaystyle f_{x}(1,0)=p_{x}(1,0)=a_{10}+2a_{20}+3a_{30}}$
3. ${\displaystyle f_{x}(0,1)=p_{x}(0,1)=a_{10}+a_{11}+a_{12}+a_{13}}$
4. ${\displaystyle f_{x}(1,1)=p_{x}(1,1)=\textstyle \sum _{i=1}^{3}\sum _{j=0}^{3}a_{ij}i}$
5. ${\displaystyle f_{y}(0,0)=p_{y}(0,0)=a_{01}}$
6. ${\displaystyle f_{y}(1,0)=p_{y}(1,0)=a_{01}+a_{11}+a_{21}+a_{31}}$
7. ${\displaystyle f_{y}(0,1)=p_{y}(0,1)=a_{01}+2a_{02}+3a_{03}}$
8. ${\displaystyle f_{y}(1,1)=p_{y}(1,1)=\textstyle \sum _{i=0}^{3}\sum _{j=1}^{3}a_{ij}j}$

Finalement, les quatre équations suivantes sont obtenues en évaluant la dérivée partielle ${\displaystyle f_{xy}}$

1. ${\displaystyle f_{xy}(0,0)=p_{xy}(0,0)=a_{11}}$
2. ${\displaystyle f_{xy}(1,0)=p_{xy}(1,0)=a_{11}+2a_{21}+3a_{31}}$
3. ${\displaystyle f_{xy}(0,1)=p_{xy}(0,1)=a_{11}+2a_{12}+3a_{13}}$
4. ${\displaystyle f_{xy}(1,1)=p_{xy}(1,1)=\textstyle \sum _{i=1}^{3}\sum _{j=1}^{3}a_{ij}ij}$

Dans les expressions ci-dessus,

${\displaystyle p_{x}(x,y)=\textstyle \sum _{i=1}^{3}\sum _{j=0}^{3}a_{ij}ix^{i-1}y^{j}}$

${\displaystyle p_{y}(x,y)=\textstyle \sum _{i=0}^{3}\sum _{j=1}^{3}a_{ij}x^{i}jy^{j-1}}$

${\displaystyle p_{xy}(x,y)=\textstyle \sum _{i=1}^{3}\sum _{j=1}^{3}a_{ij}ix^{i-1}jy^{j-1}}$.

Cette procédure donne une surface ${\displaystyle p(x,y)}$ sur le carré unitaire ${\displaystyle [0,1]\times [0,1]}$ qui est continue et a des dérivées continues. L'interpolation bicubique sur une grille régulière de taille quelconque peut donc être réalisée en recollant des surfaces unitaires interpolées bicubiques, en s'assurant que les dérivées aux limites correspondent.

Trouver les dérivées à partir des valeurs de la fonction

Si les dérivées sont inconnues, elles sont généralement estimées à partir des valeurs de la fonction au voisinage des coins du carré unitaire à interpoler, par exemple en utilisant les différences finies.

Pour trouver l'une des dérivées simples, ${\displaystyle f_{x}}$ ou ${\displaystyle f_{y}}$, en utilisant cette méthode, trouver la pente entre les deux points environnants selon l'axe approprié. Par exemple, pour calculer ${\displaystyle f_{x}}$ pour un point cible, trouver ${\displaystyle f(x,y)}$ pour les points à gauche et à droite du point cible et calculer la pente. De même pour calculer ${\displaystyle f_{y}}$ en un point cible, il faut calculer ${\displaystyle f(x,y)}$ pour les points au-dessus et en-dessous du point cible, et calculer la pente.

Pour trouver la dérivée croisée, ${\displaystyle f_{xy}}$, prendre les dérivées selon les deux axes, une par une. Par exemple, on peut utiliser d'abord la procédure pour calculer ${\displaystyle f_{x}}$, la dérivée selon ${\displaystyle X}$, pour les points au-dessus et en dessous du point cible, et ensuite utiliser la procédure pour calculer ${\displaystyle f_{y}}$, la dérivée selon ${\displaystyle Y}$, sur ces dérivées selon ${\displaystyle X}$ (plutôt que de calculer ${\displaystyle f_{y}}$ sur les valeurs de ${\displaystyle f}$ pour ces points). On obtient la valeur de ${\displaystyle f_{xy}(x,y)}$ pour le point cible. (On peut également le faire dans la direction opposée, calculer en premier ${\displaystyle f_{y}}$ et ensuite ${\displaystyle f_{x}}$ sur ces valeurs. Les deux résultats sont équivalents.)

Aux frontières de l'ensemble de points à traiter, il manque certains des points environnants pour calculer les dérivées. Les points manquants peuvent être estimés par un certain nombre de méthodes. Une méthode simple et courante consiste à supposer que la pente du point existant au point cible inexistant est constante, et d'utiliser cela pour calculer une valeur hypothétique pour le point manquant.

Algorithme de convolution bicubique

L'interpolation par spline bicubique nécessite la résolution du système linéaire décrit ci-dessus pour chaque case de la grille de valeurs connues. On peut obtenir un interpolateur avec des propriétés similaires, en appliquant une convolution avec le noyau suivant dans chaque dimension :

${\displaystyle W(x)={\begin{cases}(a+2)|x|^{3}-(a+3)|x|^{2}+1&{\text{si }}|x|\leq 1\\a|x|^{3}-5a|x|^{2}+8a|x|-4a&{\text{si }}1<|x|<2\\0&{\text{sinon}}\end{cases}}}$

où ${\displaystyle a}$ est généralement fixé à -0,5 ou -0,75. Notez que ${\displaystyle W(0)=1}$ et ${\displaystyle W(n)=0}$ pour tous les entiers non nuls ${\displaystyle n}$.

Cette approche a été proposée par Keys, qui a montré que ${\displaystyle a=-0,5}$ (ce qui correspond une spline cubique d'Hermite) produit une convergence du troisième ordre par rapport à la fonction d'origine[1].

Si nous utilisons la notation matricielle pour le cas commun ${\displaystyle a=-0,5}$, nous pouvons exprimer l'équation d'une manière plus conviviale : ${\displaystyle p(t)={\tfrac {1}{2}}{\begin{bmatrix}1&t&t^{2}&t^{3}\\\end{bmatrix}}{\begin{bmatrix}0&2&0&0\\-1&0&1&0\\2&-5&4&-1\\-1&3&-3&1\\\end{bmatrix}}{\begin{bmatrix}a_{-1}\\a_{0}\\a_{1}\\a_{2}\\\end{bmatrix}}}$

pour ${\displaystyle t}$ entre ${\displaystyle 0}$ et ${\displaystyle 1}$ pour une dimension.

Pour deux dimensions, appliqué d'abord en ${\displaystyle X}$ puis en ${\displaystyle Y}$ :

${\displaystyle \textstyle b_{-1}=p(t_{x},a_{(-1,-1)},a_{(0,-1)},a_{(1,-1)},a_{(2,-1)})}$

${\displaystyle \textstyle b_{0}=p(t_{x},a_{(-1,0)},a_{(0,0)},a_{(1,0)},a_{(2,0)})}$

${\displaystyle \textstyle b_{1}=p(t_{x},a_{(-1,1)},a_{(0,1)},a_{(1,1)},a_{(2,1)})}$

${\displaystyle \textstyle b_{2}=p(t_{x},a_{(-1,2)},a_{(0,2)},a_{(1,2)},a_{(2,2)})}$

${\displaystyle \textstyle p(x,y)=p(t_{y},b_{-1},b_{0},b_{1},b_{2})}$

Utilisation en infographie

L'algorithme bicubique est fréquemment utilisé pour la mise à l'échelle d'images et de vidéos pour l'affichage (voir Redimensionnement d'image). Il préserve les détails fins mieux que l'algorithme bilinéaire.

Toutefois, en raison des lobes négatifs sur le noyau de convolution, l'algorithme provoque un dépassement (halo). Cela peut causer la saturation du signal, c'est donc un artefact (voir également les effets d'anneau), mais cela augmente le piqué d'image (la netteté apparente), et peut être souhaitable.

Notes et références

1. (en) R.Keys, « Cubic convolution interpolation for digital image processing », IEEE transactions on acoustics, speech, and signal processing, vol. 29, n^o 6,‎ 1981, p. 1153-1160.