ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.
J'ai bien une autre question
Si l'interpolation par spline est un point critique de l'algorithme que l'on developpe, aussi bien en precision d'interpolation qu'en temps de calcul.
Est ce qu'une spline est mieux adaptée pour interpoler toutes sortes d'images, ou est ce que théoriquement chaque image aurait sa spline avec ses fonctions de bases qui vont bien, et est ce qu'on peut les trouver.
Pour l'instant j'utilise des B-splines d'ordre 3 ou 5.
Non, il n' y a pas de formule magique qui permet d'interpoler "au mieux" n'importe quelle image. Mais il est vrai que les splines cubiques donnent des resultats "visuellement" convenables. Maintenant, des splines cubiques, il y en a plein. Celle que j'ai donné en exemple (1er post) n'est pas une B-Spline, mais une spline issue de ce document.
Sinon, on peut toujours construire ses propres fonctions de base: il suffit de poser l'equation "s(t) = a.t^3 + b.t^2 + c.t + d" et d'ajouter progressivement des contraintes (passage par les sommets, continuité des derivées, ...) jusqu'a ce que les coefficients a,b,c,d soient calculables.
ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.
Salut à tous,
j'ai une petite question concernant l'interpolation spline cubique pour la 2D.
J'ai lu l'article que tu cites ... mais je ne comprends toujours pas le principe pour passer du 1D au 2D.
Dans l'article, pour le cas général "spline cubique" on a les équations générales suivantes:
f(x) = a.x3 + b.x2 + c.x + d sur l'intervalle (0,1)
et
f(x) = e.x3 + f.x2 + g.x + h sur l'intervalle (1,2)
avec les contraintes (continuités en 0 et 1, reproduction exactes des
valeurs pour les points d'origine, etc...) on arrive à :
f(x) = (a+2).x3 - (a+3).x2 + 1 sur l'intervalle (0,1)
et
f(x) = a.x3 - 5a.x2 + 8a.x - 4a sur l'intervalle (1,2)
après je ne vois aucune explication dans l'article pour la méthodo en 2D si ce n'est qu'ils disent que la décomposition 2D est décomposée en 2 étapes 1D.
Je ne vois pas comment on est passé du 1D à la méthode que tu décris avec les 4 bases (C1(t), C2(t), C3(t), C4(t)) et surtout pourquoi les 4 bases sont différentes.
Dans les bases que tu indiques, C2(t) correspond au f(x) sur l'intervalle (0,1) mais après je ne sais pas d'où sortent les autres bases C1, C3 et C4.
Perso j'aurais pris 4 bases identiques que j'aurais appliqué sur 4 lignes puis je j'aurais fait comme tu indiques pour obtenir S(u,t) en appliquant la même base sur les colonnes.
bref là je suis largué donc j'attends vos réponses avec impatience.
Merci par avance ...
Au début de la page (schéma) les Ci(t) représentent des courbes alors que quelques posts plus loin les Ci(t) représentent des fonctions de base formant une courbe.
Dans la méthode décrite par pseudocode, il y a bien un ensemble de 4 fonctions de base identique pour chaque courbe dans un sens. Et on utilise ce même ensemble dans l'autre sens pour calculer S(u,t)
Merci pour la rapidité de la réponse.
ok ...
mais alors dans ce cas là je modifie un peu ma question. Si on utilise bien la même spline pour toutes les lignes, puis colonnes (par paquet de 4) comment les 4 fonctions de base formant la spline ont été calculées (pas d'explication dans le document cité par pseudocode)
C3(t) = at3 - 2at2 + at
C2(t) = (a+2)t3 - (a+3)t2 + 1
C1(t) = -(a+2)t3 + (2a+3)t2 - at
C0(t) = -at3 + at2
?
Merci encore
et par avance ...![]()
ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.
Je précise que Java propose directement cela dans sa bibliothèque standard en utilisant des BufferedImage/RenderingHints/Graphics2 :
Code java : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28 public BufferedImage filter() throws Exception { //type d'interpolation String type = getStringValue("type"); //nouvelle largeur int width = (int) (((double) getIntValue("h"))/100.0 * (double) getInputImage().getWidth()); //nouvelle hauteur int height = (int) (((double) getIntValue("v"))/100.0 * (double) getInputImage().getHeight()); /* création de l'image de sortie */ BufferedImage out = new BufferedImage(width, height, getInputImage().getType()); /* On dessine sur le Graphics */ Graphics2D g = out.createGraphics(); Object typeInterpolation = RenderingHints.VALUE_INTERPOLATION_NEAREST_NEIGHBOR; if(type.equals("bilinear")) typeInterpolation = RenderingHints.VALUE_INTERPOLATION_BILINEAR; if(type.equals("bicubic")) typeInterpolation = RenderingHints.VALUE_INTERPOLATION_BICUBIC; g.setRenderingHint(RenderingHints.KEY_INTERPOLATION, typeInterpolation); g.drawImage(getInputImage(), 0, 0, width, height, null); g.dispose(); return out; }
ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.
Par rapport à notre discussion de tout à l'heure :
Dans mon cas, j'ai des points séparés (du genre je ne connais que f(i-3,j), f(i,j), f(i+5, j) et f(i+6,j) et je souhaite interpoler entre f(i,j) et f(i+5,j). Comment ça marche dans ce cas ?
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2 return f(i-1,j)*C3(x-i) + f(i,j)*C2(x-i) + f(i+1,j)* C1(x-i) + f(i+2,j)*C0(x-i); }
Dans ton cas la methode donnée dans le PO ne fonctionne pas, car la matrice est calculée pour un espacement fixe. I faut donc calculer explicitement les 4 courbes de bases pour chaque intervalle.
Une methode plus simple (rapide) consiste a évaluer le polynome d'une spline cubique. Pour cela on a besoin de connaitre la derivée seconde de la spline pour chaque point de passage.
On repart de l'équation de la spline, et on résout le système d'équations. Fort heureusement, ce système d'équations est sympathique car linéaire (par rapport à y") et tri-diagonal:
E(i) : a.y"(i-1) + b.y"(i) + c.y"(i+1) = d
avec
a = (x(i)-x(i-1))/6
b = (x(i+1)-x(i-1))/3
c = (x(i+1)-x(i))/6
d = (y(i+1)-y(i))/(x(i+1)-x(i)) - (y(i)-y(i-1))/(x(i)-x(i-1))
Voila un exemple de résolution (pas le plus optimal).
Code java : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39 public static double[] secondDerivative(Point... P) { int n = P.length; double yp1=0.0; double ypn=0.0; // build the tridiagonal system // (assume 0 boundary conditions: y2[0]=y2[-1]=0) double[][] matrix = new double[n][3]; double[] result = new double[n]; matrix[0][1]=1; for(int i=1;i<n-1;i++) { matrix[i][0]=(double)(P[i].x-P[i-1].x)/6; matrix[i][1]=(double)(P[i+1].x-P[i-1].x)/3; matrix[i][2]=(double)(P[i+1].x-P[i].x)/6; result[i]=(double)(P[i+1].y-P[i].y)/(P[i+1].x-P[i].x) - (double)(P[i].y-P[i-1].y)/(P[i].x-P[i-1].x); } matrix[n-1][1]=1; // solving pass1 (up->down) for(int i=1;i<n;i++) { double k = matrix[i][0]/matrix[i-1][1]; matrix[i][1] -= k*matrix[i-1][2]; matrix[i][0] = 0; result[i] -= k*result[i-1]; } // solving pass2 (down->up) for(int i=n-2;i>=0;i--) { double k = matrix[i][2]/matrix[i+1][1]; matrix[i][1] -= k*matrix[i+1][0]; matrix[i][2] = 0; result[i] -= k*result[i+1]; } // return second derivative value for each point P double[] y2 = new double[n]; for(int i=0;i<n;i++) y2[i]=result[i]/matrix[i][1]; return y2; }
On peut alors calculer la valeur de P.y pour tout point P tel que P1.x <= P.x <= P2.x en évaluant le polynome de la spline
Code java : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21 Point[] points = /* liste de points, triés par "x" croissants */ double[] sd = secondDerivative(points); for(int i=0;i<points.length-1;i++) { Point cur = points[i]; Point next = points[i+1]; for(int x=cur.x;x<next.x;x++) { double t = (double)(x-cur.x)/(next.x-cur.x); double a = 1-t; double b = t; double h = next.x-cur.x; double y= a*cur.y + b*next.y + (h*h/6)*( (a*a*a-a)*sd[i]+ (b*b*b-b)*sd[i+1] ); draw(x,y); /* ou tout autre utilisation */ } }
(exemple de spline passant par 8 points)
ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.
Merci beaucoup, j'ai maintenant le droit à une courbe plus courbe dans ma fonction "Curves" :
![]()
Partager