IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Contribuez Discussion :

[image] Interpolation spline cubique


Sujet :

Contribuez

  1. #41
    Rédacteur
    Avatar de pseudocode
    Homme Profil pro
    Architecte système
    Inscrit en
    décembre 2006
    Messages
    10 061
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 48
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Architecte système
    Secteur : Industrie

    Informations forums :
    Inscription : décembre 2006
    Messages : 10 061
    Points : 15 798
    Points
    15 798
    Par défaut
    Citation Envoyé par briqueabrac Voir le message
    Merci bien
    de rien...

    Jamais je n'aurais cru que ce petit bout de code java engendrerait une discussion aussi longue.
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

  2. #42
    Membre du Club
    Profil pro
    Inscrit en
    août 2007
    Messages
    52
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : août 2007
    Messages : 52
    Points : 62
    Points
    62
    Par défaut
    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.

  3. #43
    Rédacteur
    Avatar de pseudocode
    Homme Profil pro
    Architecte système
    Inscrit en
    décembre 2006
    Messages
    10 061
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 48
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Architecte système
    Secteur : Industrie

    Informations forums :
    Inscription : décembre 2006
    Messages : 10 061
    Points : 15 798
    Points
    15 798
    Par défaut
    Citation Envoyé par briqueabrac Voir le message
    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.
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

  4. #44
    Candidat au Club
    Profil pro
    Inscrit en
    février 2003
    Messages
    3
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : février 2003
    Messages : 3
    Points : 4
    Points
    4
    Par défaut encore une question
    Salut à tous,

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

    Citation Envoyé par pseudocode Voir le message
    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 ...

  5. #45
    Membre du Club
    Profil pro
    Inscrit en
    août 2007
    Messages
    52
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : août 2007
    Messages : 52
    Points : 62
    Points
    62
    Par défaut
    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)

  6. #46
    Candidat au Club
    Profil pro
    Inscrit en
    février 2003
    Messages
    3
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : février 2003
    Messages : 3
    Points : 4
    Points
    4
    Par défaut
    Merci pour la rapidité de la réponse.

    Citation Envoyé par briqueabrac Voir le message
    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 ...

  7. #47
    Rédacteur
    Avatar de pseudocode
    Homme Profil pro
    Architecte système
    Inscrit en
    décembre 2006
    Messages
    10 061
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 48
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Architecte système
    Secteur : Industrie

    Informations forums :
    Inscription : décembre 2006
    Messages : 10 061
    Points : 15 798
    Points
    15 798
    Par défaut
    Citation Envoyé par briqueabrac Voir le message
    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.
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

  8. #48
    Candidat au Club
    Profil pro
    Inscrit en
    février 2003
    Messages
    3
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : février 2003
    Messages : 3
    Points : 4
    Points
    4
    Par défaut
    Citation Envoyé par pseudocode Voir le message
    @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

  9. #49
    Rédacteur

    Avatar de millie
    Profil pro
    Inscrit en
    juin 2006
    Messages
    7 013
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : juin 2006
    Messages : 7 013
    Points : 9 698
    Points
    9 698
    Par défaut
    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;
    	}
    Je ne répondrai à aucune question technique en privé

  10. #50
    Rédacteur
    Avatar de pseudocode
    Homme Profil pro
    Architecte système
    Inscrit en
    décembre 2006
    Messages
    10 061
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 48
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Architecte système
    Secteur : Industrie

    Informations forums :
    Inscription : décembre 2006
    Messages : 10 061
    Points : 15 798
    Points
    15 798
    Par défaut
    Citation Envoyé par millie Voir le message
    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)
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

  11. #51
    Rédacteur

    Avatar de millie
    Profil pro
    Inscrit en
    juin 2006
    Messages
    7 013
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : juin 2006
    Messages : 7 013
    Points : 9 698
    Points
    9 698
    Par défaut
    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 ?
    Je ne répondrai à aucune question technique en privé

  12. #52
    Rédacteur
    Avatar de pseudocode
    Homme Profil pro
    Architecte système
    Inscrit en
    décembre 2006
    Messages
    10 061
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 48
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Architecte système
    Secteur : Industrie

    Informations forums :
    Inscription : décembre 2006
    Messages : 10 061
    Points : 15 798
    Points
    15 798
    Par défaut
    Citation Envoyé par millie Voir le message
    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)
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

  13. #53
    Rédacteur

    Avatar de millie
    Profil pro
    Inscrit en
    juin 2006
    Messages
    7 013
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : juin 2006
    Messages : 7 013
    Points : 9 698
    Points
    9 698
    Par défaut
    Citation Envoyé par pseudocode Voir le message
    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
    Je ne répondrai à aucune question technique en privé

  14. #54
    Rédacteur

    Avatar de millie
    Profil pro
    Inscrit en
    juin 2006
    Messages
    7 013
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : juin 2006
    Messages : 7 013
    Points : 9 698
    Points
    9 698
    Par défaut
    Merci beaucoup , j'ai maintenant le droit à une courbe plus courbe dans ma fonction "Curves" :

    Je ne répondrai à aucune question technique en privé

Discussions similaires

  1. Interpolation spline cubique
    Par black_hole dans le forum Traitement d'images
    Réponses: 1
    Dernier message: 21/02/2011, 11h50
  2. interpolation spline cubique
    Par chamac79 dans le forum C++
    Réponses: 4
    Dernier message: 29/04/2009, 18h20
  3. interpolation spline cubique en c++
    Par mehdinirvana dans le forum C++
    Réponses: 3
    Dernier message: 06/03/2009, 12h52
  4. Interpolation par spline cubique
    Par arm3366 dans le forum MATLAB
    Réponses: 2
    Dernier message: 07/02/2008, 13h59

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo