[image] Interpolation spline cubique

Version imprimable

Voir 40 message(s) de cette discussion en une page

30/08/2007, 16h44
pseudocode

Citation:

Envoyé par briqueabrac

Merci bien :)

de rien...

Jamais je n'aurais cru que ce petit bout de code java engendrerait une discussion aussi longue. :aie:
30/08/2007, 23h10
briqueabrac

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.
31/08/2007, 09h54
pseudocode

Citation:

Envoyé par briqueabrac

J'ai bien une autre question :)
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.

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.
20/11/2007, 19h00
adrien34

encore une question

Salut à tous,

j'ai une petite question concernant l'interpolation spline cubique pour la 2D.

Citation:

Envoyé par pseudocode

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.

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. 8O

Merci par avance ...
20/11/2007, 19h33
briqueabrac

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)
20/11/2007, 20h04
adrien34

Merci pour la rapidité de la réponse.

Citation:

Envoyé par briqueabrac

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)

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 ... ;)
21/11/2007, 09h54
pseudocode

Citation:

Envoyé par briqueabrac

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)

:king: briqueabrac est officiellement nommé responsable de ce thread. :P

@adrien34: C'est expliqué page 6 au milieu de la colonne de gauche. Par contre il n'y a pas les calculs.
21/11/2007, 16h27
adrien34

Citation:

Envoyé par pseudocode

@adrien34: C'est expliqué page 6 au milieu de la colonne de gauche. Par contre il n'y a pas les calculs.

Ok! j'avais lu un peu trop rapidement l'article! j'ai refait les calculs et je retrouve les mêmes resultats donc tout va bien et tout est logique!

Merci encore

Je précise que Java propose directement cela dans sa bibliothèque standard en utilisant des BufferedImage/RenderingHints/Graphics2 :

Code:

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;
	}

29/07/2008, 16h00
pseudocode

Citation:

Envoyé par millie

Je précise que Java propose directement cela dans sa bibliothèque standard en utilisant des BufferedImage/RenderingHints/Graphics2

Pour info, la matrice utilisée par Java (1.5 et +) est la même que celle du post #4 avec a=-0.5

(cf native\sun\awt\medialib\mlib_ImageFilters.c du jdk5/6)
30/07/2008, 21h22
millie
Par rapport à notre discussion de tout à l'heure :
Code:

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 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 ?

Citation:

Envoyé par millie

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 ?

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:

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:

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 */ } }
http://xphilipp.developpez.com/contribuez/spline1d.png
(exemple de spline passant par 8 points)

31/07/2008, 19h37
millie

Citation:

Envoyé par pseudocode

Voila un exemple de résolution (pas le plus optimal).

De toute façon pour mes besoins, il y a rarement plus de 5 points (10 grand max) donc je pense que ça ira. Merci beaucoup :D
31/07/2008, 22h09
millie

Merci beaucoup :hola:, j'ai maintenant le droit à une courbe plus courbe dans ma fonction "Curves" :

http://humbert-florent.developpez.co...lliecurves.png

Voir 40 message(s) de cette discussion en une page