Discussion :

[b_reda31]

Bonjour,
Je voudrai à partir d'une fonction discrète I(k) défini pour 0<=k<=N, déterminer la valeur de I(x) pour un x réel dans [0,N] , et ce par interpolation B-Spline.
Pour le moment, voici la formule que j'utilise pour l'interpolation :

où:
Bn(.) : Fonction BSpline d'ordre n.
S(x) représente le support de x, càd les voisins de x qui seront pris en considération pour le calcul de I(x). La taille du support dépend ainsi de l'ordre d'interpolation n.

Petite application numérique:
Pour calculer I(5.8) avec une interpolation cubique n=3


Le support de 5.8 représente ainsi l'ensemble des points "discrets" ayant une distance inférieur ou égal 2 par rapport à x=5.8, soit :
S(x) = {4,5,6,7}.
ainsi I(5.8) = I(4).B(5.8-4) + I(5).B(5.8-5) + I(6).B(5.8-6)+ I(7).B(5.8-7).
Est-ce correct selon vous?

En lisant un document je suis tombé sur une formule différente que je n'arrive pas à comprendre :

Dans cette équation (n) est le degré du spline, ou l'ordre de l'interpolation, et les c(k) sont des coéficients donnés par les points discrets I(k) du signal en fonction de Bn. Ils peuvent être calculés par filtres récursif

Source : Recalage multimodal et plate-forme d'imagerie médicale à accès distant-Page 62.

I(x) n'est donc pas calculé directement à partir des I(k) mais à partir des c(k). Cependant je ne vois pas comment calculer les c(k) dans mon cas

[pseudocode]

Je n'ai pas tout compris à ton problème (), mais j'avais posté des exemples de code concernant le calcul de B-Spline d'ordre "n" dans cette discussion.

Il y aura peut-être une piste intéressante dedans.

[b_reda31]

Je n'ai pas tout compris à ton problème (), mais j'avais posté des exemples de code concernant le calcul de B-Spline d'ordre "n" dans cette discussion.

Il y aura peut-être une piste intéressante dedans.

Je pense alors que je suis complètement à coté de la plaque.
Je vais revoir ces codes. Merci.

[b_reda31]

Re,
Il me semble que la discussion où vous m'avez orienté ne traite pas vraiment le problème que je rencontre. Je vais tenter de le reformuler à travers un exemple:
Ayant une fonction 1-D discrète f , où seules les valeurs suivantes sont connues :
f(0),f(1),f(2),f(3),f(4),f(5).
à partir de cet échantillon , je voudrai avoir une approximation de f(2.8) par exemple.

J'ai cru comprendre que l'idée consiste à associer un poids à chacune des valeurs de cet échantillon. Ainsi f(2.8) vaut la moyenne pondérée de cet échantillon.
Le poids de chaque point est inversement proportionnel à sa distance par rapport au point 2.8. De manière à favoriser les points les plus proches. J'ai utilisé les fonctions bspline suivante afin de déterminer ce poids.

Le paramètre donnée à la fonction Bspline est donc la distance.
Voici donc comment j'ai procédé pour avoir l'approximation de f(2.8) selon les différents ordres d'interpolation, pensez vous que les formules suivantes sont correctes?

1. Pour une interpolation d'ordre 0 :
b0(t)=1 si -1/2<t<1/2. 0 sinon.
Le poids du point f(0) vaut b0(2.8-0)=b0(2.8) =0.
Le poids du point f(1) vaut b0(2.8-1)=b0(1.8) =0.
Le poids du point f(2) vaut b0(2.8-2)=b0(0.8) =0.
Le poids du point f(3) vaut b0(2.8-3)=b0(-0.2) =1.
Les poids des points f(4) et f(5) valent 0.
Ainsi I(2.8) = I(3) (Ce qui correspond à une interpolation au plus proche voisin)

2. Pour une interpolation d'ordre 1:
b1(t)=1-abs(t) si -1<t<1 , 0 sinon
Les des poids f(0),f(1),f(4),f(5) valent 0.
Le poids de f(2) vaut 1-abs(2.8-2)=0.2
Le poids de f(3)=1-abs(2.8-3)=0.8.
I(2.8)=0.2*I(2)+0.8*I(3). (Interpolation linéaire)

3. Pour une interpolation d'ordre 3:

les poids des points f(0) et f(5) valent 0.
le poids de f(1) vaut b(2.8-1)=b(1.8)=0.0013
le poids de f(2) vaut b(2.8-2)=b(0.8)=0.286
le poids de f(3) vaut b(2.8-3)=b(-0.2)=0.634
le poids de f(4) vaut b(2.8-4)=b(-1.2)=0.085


PS: Je m'excuse pour la longueur de ce message, et je vous remercie si vous en êtes arrivé jusqu'ici en sa lecture. à vrai dire je rédige un rapport dans le cadre de mes études, et je ne voudrai pas prendre le risque d'écrire des formules incorrectes

[pseudocode]

Ta formulation est celle des B-Spline uniformes, ce qui simplifie effectivement la formulation.

La formule d'interpolation est habituellement présentée sous forme matricielle.



pour t variant entre 0 et 1

[b_reda31]

J'ai trouvé mon bonheur dans cet artice de Michael Unser, qui certe est un peu vieux mais toujours d'actualité (très couramment cité).
Splines - A perfect fit for signal and image processing
Dans cet article Unser propose un algo récursif pour calculer les coefficients c(k) à partir le l'échantillon de manière à ce que la fonction continue passe exactement par tous les points de l'échantillon (ni un peu plus haut ni un peu plus bas) ce qui n'est pas vraiment le cas si on utilisait les valeurs de l'échantillon directement (ce que j'avais fais dans mon précédent post.).
Merci quand même pseudocode.

[souviron34]

la fonction continue passe exactement par tous les points de l'échantillon (ni un peu plus haut ni un peu plus bas) ce qui n'est pas vraiment le cas si on utilisait les valeurs de l'échantillon directement

J'avoue rester perplexe sur ton affirmation...

La définition même d'un spline est de créer une fonction continue passant par les points de l'échantillon..... (contrairement par exemple aux interpolations style Béziers, qui ne passent pas par les points de l'échantillon).


Toutes les routines de spline (en tous cas les cubiques, que j'utilise réglièrement - voir par exemple celle de Numerical Recipes, celle de "Algorithms in C" (Sedgewck), celles de comp.graphics.algorithms, etc), calcule le spline en passant par les points de l"échantillon et sont associées à une fonction d'interpolation permettant d'interpoler n'importe où entre ces points...

[FR119492]

Bonjour à tous!
Il ne faudrait pas oublier qu'une approximation et une interpolation, ça n'est pas la même chose.
Jean-Marc Blanc

[b_reda31]

La définition même d'un spline est de créer une fonction continue passant par les points de l'échantillon..... (contrairement par exemple aux interpolations style Béziers, qui ne passent pas par les points de l'échantillon).

L'écart que j'avais entre la valeur f(k) de l'échantillon et la valeur f(k) "interpolé" venait du fait que j'ai appliqué une mauvaise formule d'interpolation :


(elle reste quand même correcte pour n<2 )

[pseudocode]

J'ai trouvé mon bonheur dans cet artice de Michael Unser, qui certe est un peu vieux mais toujours d'actualité (très couramment cité).
Splines - A perfect fit for signal and image processing

Tu peux trouver sur wikipedia l'algo de calcul des coefficients des splines cubiques d'interpolation.

[Nebulix]

From Numerical Recipes
Interpolation, where the number of coefficients and number of tabulated points are equal, takes the tabulated values as perfect. If they ... contain statistical errors, these can be magnified into oscillations ...

Le remède peut être pire que le mal.

[pseudocode]

Le remède peut être pire que le mal.

C'est le problème de TOUTES les interpolations, splines cubiques comprises.

Si tu forces à la fois la forme de la courbe (polynome de degré n) et les points de passage, tu imposes les courbures de ton interpolation. Et ces courbures peuvent être très raides.


PS : L'interpolation la plus simple à calculer avec des splines cubiques est sans doute l'utilisation des splines de Hermite (Cubic Hermite spline).