Discussion :

[pseudocode]

Merci bien

de rien...

Jamais je n'aurais cru que ce petit bout de code java engendrerait une discussion aussi longue.

[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.

[pseudocode]

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.

[adrien34]

Salut à tous,

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

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.

Merci par avance ...

[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)

[adrien34]

Merci pour la rapidité de la réponse.

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

[pseudocode]

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)

briqueabrac est officiellement nommé responsable de ce thread.

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

[adrien34]

@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

[millie]

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

[pseudocode]

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)

[millie]

Par rapport à notre discussion de tout à l'heure :

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

[pseudocode]

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

[millie]

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

[millie]

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