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

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

    Informations forums :
    Inscription : décembre 2006
    Messages : 10 027
    Points : 15 578
    Points
    15 578

    Par défaut [image] Interpolation spline cubique

    Un petit bout de code pour faire une Interpolation par spline cubique.

    Par exemple pour avoir une estimation de la valeur d'un pixel de coordonnées non entiere. Utile, entre autres, dans les algos de redimensionnement


    L'oeil de Lena (Agrandissement x 10)
    A gauche: Interpolation plus proche pixel
    A droite: Interpolation spline cubique

    Code : 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
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    /**
     * Interpolation par Spline Cubique
     * 
     * @author Xavier Philippeau
     *
     */
    public class Interpolate {
    
    	// spline factor in the range [-1,0]
    	private double a = -0.5;
    	
    	// original image
    	private Channel channel = null;
    	
    	public Interpolate(Channel c) {
    		this.channel = c;
    	}
    	
    	// --- Spline coefficients ----------------------------------------------------
    	
    	// C0(t) = -at3 + at2 
    	private double C0(double t) {
    		return -a*t*t*t + a*t*t;
    	}
    	
    	// C1(t) = -(a+2)t3 + (2a+3)t2 - at 
    	private double C1(double t) {
    		return -(a+2)*t*t*t + (2*a+3)*t*t - a*t;
    	}
    	
    	// C2(t) = (a+2)t3 - (a+3)t2 + 1 
    	private double C2(double t) {
    		return (a+2)*t*t*t - (a+3)*t*t + 1;
    	}
    	
    	// C3(t) = at3 - 2at2 + at 
    	private double C3(double t) {
    		return a*t*t*t - 2*a*t*t + a*t;
    	}
    
    	// --- Continous interpolation from discrete values ---------------------------
    	
    	// discret value for pixel of coordinates: i (integer) , j (integer)
    	private double f(int i, int j) {
    		return this.channel.getValue(i, j);
    	}
    	
    	// compute interpolated value for pixel of coordinates: x (real) , j (integer)
    	private double H(int j, double x) {
    		int i = (int)x;
    		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);
    	}
    
    	// compute interpolated value for pixel of coordinates: x (real) , y (real)
    	public double value(double x, double y) {
    		int j = (int)y;
    		return H(j-1,x)*C3(y-j) + H(j,x)*C2(y-j) + H(j+1,x)*C1(y-j) + H(j+2,x)*C0(y-j);
    	}
    }
    NB: Comme toujours, ce code est volontairement non optimisé. Pour info, on peut diviser par deux le nombre de multiplications, et egalement précalculer les valeurs des coefficients...
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

  2. #2
    Membre à l'essai
    Profil pro
    Inscrit en
    juin 2007
    Messages
    19
    Détails du profil
    Informations personnelles :
    Âge : 32
    Localisation : France, Gironde (Aquitaine)

    Informations forums :
    Inscription : juin 2007
    Messages : 19
    Points : 18
    Points
    18

    Par défaut

    Est ce que tu connaitrais une façon d'utiliser les splines cubiques mais pas dans un cas de redimensionnement mais pour interpoler des pixels manquant? En gros il s'agirait de faire une sorte d'inpainting mais sans réutiliser les pixels interpolés. Tu penses que c'est faisable?

  3. #3
    Expert éminent
    Avatar de PRomu@ld
    Homme Profil pro
    Ingénieur de Recherche
    Inscrit en
    avril 2005
    Messages
    4 154
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 31
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur de Recherche
    Secteur : Enseignement

    Informations forums :
    Inscription : avril 2005
    Messages : 4 154
    Points : 6 240
    Points
    6 240

    Par défaut

    Interpolation par spline cubique.
    Oui, j'ai regardé ton code vite fait, il y aurait moyen d'optimiser un peu (au niveau du calcul de t, t*t , t*t*t ).

    Tu pourras nous mettre la matrice associée, stp

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

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

    Informations forums :
    Inscription : décembre 2006
    Messages : 10 027
    Points : 15 578
    Points
    15 578

    Par défaut

    Citation Envoyé par PRomu@ld
    Tu pourras nous mettre la matrice associée, stp
    Les fonctions etaient deja indiquées sous forme de commentaire dans le code, mais pour te faire plaisir:

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    Fonctions de base:
    
    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
    
    
    Forme matricielle
    
                  |  a  ,   a+2  , -(a+2) , -a |   | P(i-1) |
    |t3 t2 t 1| x | -2a , -(a+3) ,  2a+3  ,  a | x | P(i)   |
                  |  a  ,    0   ,   -a   ,  0 |   | P(i+1) |
                  |  0  ,    1   ,    0   ,  0 |   | P(i+2) |
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

  5. #5
    Expert éminent
    Avatar de PRomu@ld
    Homme Profil pro
    Ingénieur de Recherche
    Inscrit en
    avril 2005
    Messages
    4 154
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 31
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur de Recherche
    Secteur : Enseignement

    Informations forums :
    Inscription : avril 2005
    Messages : 4 154
    Points : 6 240
    Points
    6 240

    Par défaut

    Merci beaucoup.

    Les fonctions etaient deja indiquées sous forme de commentaire dans le code,
    C'était pour ne pas forcément avoir à mettre le nez dans le code.

  6. #6
    Membre à l'essai
    Profil pro
    Inscrit en
    juin 2007
    Messages
    19
    Détails du profil
    Informations personnelles :
    Âge : 32
    Localisation : France, Gironde (Aquitaine)

    Informations forums :
    Inscription : juin 2007
    Messages : 19
    Points : 18
    Points
    18

    Par défaut

    Et pour ma question vous auriez une réponse?

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

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

    Informations forums :
    Inscription : décembre 2006
    Messages : 10 027
    Points : 15 578
    Points
    15 578

    Par défaut

    Citation Envoyé par SpaGrave
    Et pour ma question vous auriez une réponse?
    Citation Envoyé par SpaGrave
    Est ce que tu connaitrais une façon d'utiliser les splines cubiques mais pas dans un cas de redimensionnement mais pour interpoler des pixels manquant? En gros il s'agirait de faire une sorte d'inpainting mais sans réutiliser les pixels interpolés. Tu penses que c'est faisable?
    Il suffit de "sauter" le(s) pixel(s) manquant(s). Par exemple, sauter le pixel "i" et utiliser les 4 pixels P(i-2), P(i-1), P(i+1), et P(i+2) puis evaluer la spline en "0.5"

    Mais je ne suis pas certain du résultat... L'inpainting me parrait plus sûr
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

  8. #8
    Membre à l'essai
    Profil pro
    Inscrit en
    juin 2007
    Messages
    19
    Détails du profil
    Informations personnelles :
    Âge : 32
    Localisation : France, Gironde (Aquitaine)

    Informations forums :
    Inscription : juin 2007
    Messages : 19
    Points : 18
    Points
    18

    Par défaut

    Oui l'inpainting est bien quand tu peux te permettre d'inventer le remplissage ce qui n'est pas mon cas. La seule possibilité que j'ai, c'est vraiment de faire la meilleure interpolation possible et de ne pas réutiliser les pixels que j'aurais interpolés.

    Ensuite, je suis déja parti sur cette piste de sauter les pixels mais c'est au niveau de la pondération que je bloque. Tu me dis d'évaluer la spline à 0.5, ça correspond au "a" dans ton code? Comment tu l'adaptes cette valeur justement?

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

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

    Informations forums :
    Inscription : décembre 2006
    Messages : 10 027
    Points : 15 578
    Points
    15 578

    Par défaut

    Citation Envoyé par SpaGrave
    Ensuite, je suis déja parti sur cette piste de sauter les pixels mais c'est au niveau de la pondération que je bloque. Tu me dis d'évaluer la spline à 0.5, ça correspond au "a" dans ton code? Comment tu l'adaptes cette valeur justement?
    Non. Le 'a' dans le code c'est une constante pour le calcul du spline, il faut laisser -0.5 (confiance... confiance...)

    Le but de l'interpolation c'est d'evaluer un pixel a une coordonnée "non entiere", par exemple P(4.75) ou d'une maniere generale P(x+dx) avec x un entier et dx un réel dans [0,1[.

    Donc dans ton cas, pour estimer P(x) on calcule la Spline a partir des points P1=P(x-2) P2=P(x-1) P3=P(x+1) et P4=P(x+2) et on l'evalue P(x+0.5)ce qui donne la valeur du pixel au milieu de P2 et P3 ( donc P(x) )
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

  10. #10
    Membre à l'essai
    Profil pro
    Inscrit en
    juin 2007
    Messages
    19
    Détails du profil
    Informations personnelles :
    Âge : 32
    Localisation : France, Gironde (Aquitaine)

    Informations forums :
    Inscription : juin 2007
    Messages : 19
    Points : 18
    Points
    18

    Par défaut

    Citation Envoyé par pseudocode
    Non. Le 'a' dans le code c'est une constante pour le calcul du spline, il faut laisser -0.5 (confiance... confiance...)
    J'ai une confiance aveugle je te rassure

    En tout cas je pense avoir compris, je vais programmer tout ça et on verra le résultat.

    Merci bien en tout cas

  11. #11
    Membre à l'essai
    Profil pro
    Inscrit en
    juin 2007
    Messages
    19
    Détails du profil
    Informations personnelles :
    Âge : 32
    Localisation : France, Gironde (Aquitaine)

    Informations forums :
    Inscription : juin 2007
    Messages : 19
    Points : 18
    Points
    18

    Par défaut

    Mouai c'est loin d'être concluant au final. Mais à mon avis ça vient du fait que je ne suis pas dans le cas que tu as expliqué. Je suis plus sur quelque chose du genre P1=P(x-9) P2=P(x-8) P3=P(x+8) et P4=P(x+9) dans la le dx du coup ne peut pas être entre [0,1[ et ça marche po.

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

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

    Informations forums :
    Inscription : décembre 2006
    Messages : 10 027
    Points : 15 578
    Points
    15 578

    Par défaut

    Citation Envoyé par SpaGrave
    Je suis plus sur quelque chose du genre P1=P(x-9) P2=P(x-8) P3=P(x+8) et P4=P(x+9) dans la le dx du coup ne peut pas être entre [0,1[ et ça marche po.
    dx=0 -> Spline = P2
    dx=1 -> Spline = P3
    0<dx<1 -> Spline = interpolation continue entre P2 et P3
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

  13. #13
    Membre à l'essai
    Profil pro
    Inscrit en
    juin 2007
    Messages
    19
    Détails du profil
    Informations personnelles :
    Âge : 32
    Localisation : France, Gironde (Aquitaine)

    Informations forums :
    Inscription : juin 2007
    Messages : 19
    Points : 18
    Points
    18

    Par défaut

    Ah donc j'avais bien compris, c'est juste que ça ne marche pas comme je le souhaiterais.

    Merci pour ces explications en tout cas
    ++

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

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

    Informations forums :
    Inscription : décembre 2006
    Messages : 10 027
    Points : 15 578
    Points
    15 578

    Par défaut

    C'est sur que l'interpolation n'est pas spécialement fait pour l'inpainting...

    Il reste ca:

    http://www.developpez.net/forums/sho...d.php?t=365026
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

  15. #15
    Membre à l'essai
    Profil pro
    Inscrit en
    juin 2007
    Messages
    19
    Détails du profil
    Informations personnelles :
    Âge : 32
    Localisation : France, Gironde (Aquitaine)

    Informations forums :
    Inscription : juin 2007
    Messages : 19
    Points : 18
    Points
    18

    Par défaut

    je suis déjà tombé sur ce lien en effet. Je vais faire une tentative de portage en C++. D'ailleur la MilieLib est faite en C non? Tu sais si on peut recupérer les sources et où?

    Ah et une autre question. Au niveau temps de calcul, l'inpainting il donne quoi à peu près? On va dire pour une image en 128*128.

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

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

    Informations forums :
    Inscription : décembre 2006
    Messages : 10 027
    Points : 15 578
    Points
    15 578

    Par défaut

    Citation Envoyé par SpaGrave
    je suis déjà tombé sur ce lien en effet. Je vais faire une tentative de portage en C++. D'ailleur la MilieLib est faite en C non? Tu sais si on peut recupérer les sources et où?

    Ah et une autre question. Au niveau temps de calcul, l'inpainting il donne quoi à peu près? On va dire pour une image en 128*128.
    heu... c'est quasi instantané...
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

  17. #17
    Membre régulier
    Profil pro
    Inscrit en
    juin 2007
    Messages
    243
    Détails du profil
    Informations personnelles :
    Localisation : Canada

    Informations forums :
    Inscription : juin 2007
    Messages : 243
    Points : 110
    Points
    110

    Par défaut mise en place de l'algorithme

    Salut,

    J'ai essaye de mettre en pratique l'algorithme que tu proposes, dans le cas d'une utilisation sous idl mais je rencontre quelque probleme.

    plutot que de galerer a les expliques, je vous les montre :
    Images attachées Images attachées   
    Fichiers attachés Fichiers attachés

  18. #18
    Membre régulier
    Profil pro
    Inscrit en
    juin 2007
    Messages
    243
    Détails du profil
    Informations personnelles :
    Localisation : Canada

    Informations forums :
    Inscription : juin 2007
    Messages : 243
    Points : 110
    Points
    110

    Par défaut

    Je peux pas mettre d'autre piece jointe, le programme me dit que j'ai depasse mon quota de place prise par les pieces jointes.


    quoiqu'il en soit, j'ai un probleme de "cadrillage" des mes images,
    de valeur globale de l'image augmenter, certaines sont plus clairs, et je ne sais pas pourquoi,
    et j'ai aussi un probleme avec une zone qui est plus fonce, mais ca ne ce voit que sur une image que j'ai pas pu mettre en piece jointe

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

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

    Informations forums :
    Inscription : décembre 2006
    Messages : 10 027
    Points : 15 578
    Points
    15 578

    Par défaut

    Citation Envoyé par svagrim
    Je peux pas mettre d'autre piece jointe, le programme me dit que j'ai depasse mon quota de place prise par les pieces jointes.


    quoiqu'il en soit, j'ai un probleme de "cadrillage" des mes images,
    de valeur globale de l'image augmenter, certaines sont plus clairs, et je ne sais pas pourquoi,
    et j'ai aussi un probleme avec une zone qui est plus fonce, mais ca ne ce voit que sur une image que j'ai pas pu mettre en piece jointe
    Tout cela n'est pas normal. Je ne connais pas matlab, mais je te conseille de debugguer en partant du code "de base" et en ajoutant progressivement l'interpolation:

    1. Dans la fonction "interpol3d", renvoyer une valeur constante. Normalement tu devrais obtenir une image uniforme.

    2. Dans la fonction "direct2", renvoyer une valeur constante. Normalement tu devrais aussi obtenir une image uniforme comme precedement.

    3. Dans la fonction "direct2", renvoyer le plus proche pixel = matdepart[i,j,k]. Normalement tu devrais obtenir une image avec un effet mosaique.

    4. Mettre le coefficient "a" à 0. Normalement tu devrais obtenir une image avec une interpolation "lineaire".

    5. Mettre le coefficient "a" à -0.5. Normalement tu devrais obtenir une image avec une interpolation B-Spline cubique.
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

  20. #20
    Membre régulier
    Profil pro
    Inscrit en
    juin 2007
    Messages
    243
    Détails du profil
    Informations personnelles :
    Localisation : Canada

    Informations forums :
    Inscription : juin 2007
    Messages : 243
    Points : 110
    Points
    110

    Par défaut

    Citation Envoyé par pseudocode
    Tout cela n'est pas normal. Je ne connais pas matlab
    matlab ?, tout ce que je sais de ce logiciel c'est que je ne l'utiliserai plus jamais, moi je travaille sous idl

    Citation Envoyé par pseudocode
    1. Dans la fonction "interpol3d", renvoyer une valeur constante. Normalement tu devrais obtenir une image uniforme.
    ca ca marche

    Citation Envoyé par pseudocode
    2. Dans la fonction "direct2", renvoyer une valeur constante. Normalement tu devrais aussi obtenir une image uniforme comme precedement.
    ca je comprend pas pourquoi ca devrait donner une image uniforme
    d'ailleurs ce n'est pas ce que j'ai.

    en fait j'ait l'impression que ce qui ne va pas c'est quand il tombe sur un point qui existe deja dans l'image de depart, quand c'est un point qu'il n'est pas cense interpole, normalement, les polynomes d'interpolation devrait ce resume a 1 pour C2 et 0 pour les autres, et donc le point devrait etre le point de l'image initiale.

    Mais je ne sais pas pourquoi, j'ai un probleme a ce niveau.

    C'est ce qui me cree le quadrillage et le fait que des coupes soient de niveau de gris plus eleve (c'est toutes les coupes correspondant aux coupes originels qui ont ce probleme)

Discussions similaires

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

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