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] seam carving

    Suite a une discussion ouverte sur le sujet du seamcarving, j'ai écrit un petit bout de code qui permet de diminuer la hauteur d'une image en utilisant la methode du chemin de moindre energie:

    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
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    102
    103
    104
    105
    106
    107
    108
    109
    110
    111
    112
    113
    114
    115
    116
    117
    118
    119
    120
    121
    122
    123
    124
    125
    126
    127
    128
    129
    130
    131
    132
    133
    134
    135
    136
    137
    138
    139
    140
    141
    142
    143
    144
    145
    146
    147
    148
    149
    150
    151
    152
    153
    154
    155
    156
    157
    158
    159
    160
    161
    162
    163
    164
    165
    166
    167
    168
    169
    170
    171
    172
    173
    174
    175
    176
    177
    178
    179
    180
    181
    182
    183
    184
    185
    186
    187
    188
    189
    190
    191
    192
    193
    194
    195
    196
    197
    198
    199
    200
    201
    202
    203
    204
    205
    206
    207
    208
    209
    210
    211
    212
    213
    214
    215
    216
    217
    218
    219
    220
    221
    222
    223
    224
    225
    226
    227
    228
    229
    230
    231
    232
    233
    234
    235
    236
    237
    238
    239
    240
    241
    242
    243
    244
    245
    246
    247
    248
    249
    250
    251
    252
    253
    254
    255
    256
    257
    258
    259
    260
    261
    262
    263
    264
    265
    266
    267
    268
    269
    270
    271
    272
    273
    274
    275
    276
    277
    278
    279
    280
    281
    282
    283
    284
    285
    286
    287
    288
    289
    290
    291
    292
    293
    294
    295
    296
    297
    298
    299
    300
    301
    302
    303
    304
    305
    306
    import java.awt.FileDialog;
    import java.awt.image.BufferedImage;
    import java.io.File;
    import java.io.IOException;
    import javax.imageio.ImageIO;
    import javax.swing.*;
     
    /**
     * Reduce the height of an image, using the minimum energy path method.
     *
     * (cf. "Content Aware Image Resizing" by  Avidan, S. & Shamir, A.)
     * 
     * @author Xavier Philippeau
     */
    public class Carving  {
     
    	// image current dimension
    	private int height=0, width=0;
     
    	// rgb image
    	private int[][] rgbimage = null;
     
    	// energy of each pixel
    	private int[][] energy = null;
     
    	// all possible (horizontal) path
    	private Path[] hpath = null;
     
    	// Path class
    	class Path {
    		// total energy
    		int energy=0;
    		// direction of path (-1,0,+1) for each pixel
    		int[] direction=null;
    		// min, max relative offsets
    		int lowestoffset=0,highestoffset=0;
    	}
     
    	/**
             * Constructor
             * 
             * @param bimg the image to resize
             */
    	public Carving(BufferedImage bimg) {
    		// initialize arrays
     
    		this.width = bimg.getWidth();
    		this.height = bimg.getHeight();
    		this.rgbimage = new int[width][height];
    		this.energy = new int[width][height];
    		this.hpath = new Path[height];
     
    		// convert BufferedImage in a 2d array
    		for (int y=0; y<height; y++)
    			for (int x=0; x<width; x++)
    				this.rgbimage[x][y] = bimg.getRGB(x, y);
    	}
     
    	/**
             * @return the current image
             */
    	public BufferedImage getImage() {
    		BufferedImage bimg = new BufferedImage(this.width,this.height,BufferedImage.TYPE_INT_ARGB);
    		for (int y=0; y<height; y++)
    			for (int x=0; x<width; x++)
    				bimg.setRGB(x, y, this.rgbimage[x][y] );
    		return bimg;
    	}
     
    	/**
             * compute energy array
             * 
             * @param ymin y range start
             * @param ymax y range end
             */
    	private void computeEnergy(int ymin, int ymax) {
    		for (int y=ymin; y<ymax; y++)
    			for (int x=0; x<width; x++)
    				energy[x][y]=gradient(x, y);
    	}
     
    	/**
             * 8 neighbours gradient
             * 
             * @param x x coord
             * @param y y coord
             * @return gradient norme
             */
    	private int gradient(int x, int y) {
    		// Coordinates of 8 neighbours
    		int px = x - 1;  // previous x
    		int nx = x + 1;  // next x
    		int py = y - 1;  // previous y
    		int ny = y + 1;  // next y
     
    		// limit to image dimension (spheric)
    		if (px < 0)	px=this.width-1;
    		if (nx >= this.width) nx=0;
    		if (py < 0)	py=this.height-1;
    		if (ny >= this.height) ny=0;
     
    		// Intensity of the 8 neighbours
    		int Ipp = getLuminance( this.rgbimage[px][py] );
    		int Icp = getLuminance( this.rgbimage[ x][py] );
    		int Inp = getLuminance( this.rgbimage[nx][py] );
    		int Ipc = getLuminance( this.rgbimage[px][ y] );
    		int Inc = getLuminance( this.rgbimage[nx][ y] );
    		int Ipn = getLuminance( this.rgbimage[px][ny] );
    		int Icn = getLuminance( this.rgbimage[ x][ny] );
    		int Inn = getLuminance( this.rgbimage[nx][ny] );
     
    		// Local gradient (sobel)
    		int gradx = (Inc-Ipc)*2 + (Inp-Ipp) + (Inn-Ipn);
    		int grady = (Icn-Icp)*2 + (Ipn-Ipp) + (Inn-Inp);
    		int norme = (int)Math.sqrt(gradx*gradx+grady*grady)/4;
     
    		return norme;  
    	}
     
    	/**
             * return luminance of a rgb value
             * 
             * @param rgb value in ARGB format
             * @return luminance
             */
    	private int getLuminance(int rgb) {
    		int r = (rgb >>16 ) & 0xFF;
    		int g = (rgb >> 8 ) & 0xFF;
    		int b = rgb & 0xFF;
    		int gray = (299*r + 587*g + 114*b)/1000;
    		return gray;
    	}
     
    	/**
             * compute the horizontal path starting from left at y position = ystart
             *
             * @param ystart starting y position
             */
    	private void computeHorizontalPath(int ystart) {
    		// contruct a new path
    		Path path = new Path();
    		path.direction = new int[width];
     
    		// add/replace in the global list
    		this.hpath[ystart]=path;
     
    		// go from letf to right
    		int miny = Integer.MAX_VALUE, maxy = 0;
    		int y=ystart;
    		for (int x=0; x<width-1; x++) {
     
    			// update min/max absolute value
    			if (y<miny) miny=y;
    			if (y>maxy) maxy=y;
     
    			// update total energy of the path
    			int v = this.energy[x][y];
    			path.energy+=v;
     
    			// the 3 next possible positions for the current path
    			int vk_up=Integer.MAX_VALUE;
    			if (y>0) vk_up = this.energy[x+1][y-1];
    			int vk_center=Integer.MAX_VALUE;
    			vk_center = this.energy[x+1][y];
    			int vk_down=Integer.MAX_VALUE;
    			if (y<(height-1)) vk_down = this.energy[x+1][y+1];
     
    			// find the lowest energy for the 3 positions
    			int min = Math.min(vk_up,Math.min(vk_center,vk_down));
     
    			// follow the lowest energy direction
    			int dir=0;
    			if (min==vk_up)  dir=-1;
    			if (min==vk_down) dir=+1;
    			if (min==vk_center) dir=0;
    			y+=dir;
     
    			// update path
    			path.direction[x]=dir;
    		}
    		path.lowestoffset = ystart-miny;
    		path.highestoffset = maxy-ystart;
    	}
     
    	/**
             * @return the path index with minimum energy
             */
    	private int findBestHorizontalPath() {
    		int bestpathnumber=0;
    		int bestpathenergy=Integer.MAX_VALUE;
    		for (int ystart=0; ystart<height; ystart++) {
    			if (this.hpath[ystart].energy<bestpathenergy) {
    				bestpathenergy=this.hpath[ystart].energy;
    				bestpathnumber=ystart;
    				if (bestpathenergy==0) break;
    			}
    		}
    		return bestpathnumber;
    	}	
     
    	/**
             * Reduce the image height
             * 
             * @param newheight new height of the image
             * @param label0 display while computing (may be null)
             */
    	public void reduceHeight(int newheight, JLabel label0) {
     
    		// compute the whole energy
    		computeEnergy(0,this.height);
     
    		// compute all path
    		for (int y=0; y<height; y++)
    			computeHorizontalPath(y);
     
    		// reduce image, line by line
    		int hcount = this.height-newheight;
    		for(int hloop=0;hloop<hcount;hloop++) {
     
    			// find best path
    			int pathid = findBestHorizontalPath(); 
     
    			// construct absolute path
    			int[] bestpath = new int[hpath[pathid].direction.length];
    			int yabs=pathid;
    			for (int x=0; x<hpath[pathid].direction.length; x++) {
    				bestpath[x]=yabs;
    				yabs+=hpath[pathid].direction[x];
    			}
     
    			// optionnal: display current state
    			if (label0!=null && hloop%10 == 0) {
    				for (int x=0; x<hpath[pathid].direction.length; x++)
    					this.rgbimage[x][bestpath[x]]=0xF0F0F0;
    				label0.setIcon( new ImageIcon(this.getImage()) );
    			}
     
    			// construct the new image
    			for (int x=0; x<hpath[pathid].direction.length; x++) {
     
    				int y = bestpath[x];
     
    				// move up all elements of arrays below the path 
    				int length = this.height-y-1;
    				System.arraycopy(this.energy[x], y+1, this.energy[x], y, length);
    				System.arraycopy(this.rgbimage[x], y+1, this.rgbimage[x], y, length);
     
    				// zeroing unused bottom part of arrays (not usefull)
    				this.energy[x][this.height-1]=0;
    			}
    			// highlevel/downlevel watermark of changed region 
    			int ymin_changed=pathid-hpath[pathid].lowestoffset;
    			int ymax_changed=pathid+hpath[pathid].highestoffset;
     
    			// resize hpath array
    			int length = this.height-pathid-1;
    			System.arraycopy(this.hpath, pathid+1, this.hpath, pathid, length);
    			this.hpath[this.height-1]=null;
     
    			// resize the image
    			this.height--;
     
    			// optim: recompute only the energy for the changed region 
    			int region_ymin = Math.max(ymin_changed-1, 0);
    			int region_ymax = Math.min(ymax_changed+1, this.height);
    			computeEnergy(region_ymin,region_ymax);
     
    			// optim: recompute only the path that go through the changed region
    			for (int y=0; y<height; y++) {
    				if ((y-this.hpath[y].lowestoffset)>ymax_changed) continue;
    				if ((y+this.hpath[y].highestoffset)<ymin_changed) continue;
    				computeHorizontalPath(y);
    			}
     
    		}
    	}
     
    	public static void main(String[] args) {
    		Thread.currentThread().setPriority(Thread.MIN_PRIORITY);
     
    		JFrame frame = new JFrame("Demo - Divide height by 4 using minimum energy path");
    		JPanel panneau = new JPanel();
    		JLabel label0 = new JLabel();
    		panneau.add(label0);
    		frame.setDefaultCloseOperation(WindowConstants.DISPOSE_ON_CLOSE);
    		frame.getContentPane().add(new JScrollPane(panneau));
    		frame.pack();
    		frame.setVisible(true);
    		frame.setSize(800, 600);
     
    		FileDialog filedialog = new FileDialog(frame, "Choose an image file");
    		filedialog.setVisible(true);
    		String filename = filedialog.getFile();
    		String directory = filedialog.getDirectory();
    		File file = new File(directory+File.separator+filename);
     
    		try {
    			BufferedImage bimg = ImageIO.read(file);
    			Carving carve = new Carving(bimg);
    			carve.reduceHeight(bimg.getHeight() / 4, label0);
    			label0.setIcon(new ImageIcon(carve.getImage()));
    		} catch (IOException e) {
    			label0.setText(e.getMessage());
    		}
    	}	
    }



    version binaire (jar)

    Promu@ld : sources
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

  2. #2
    Membre éclairé

    Inscrit en
    juin 2004
    Messages
    1 397
    Détails du profil
    Informations forums :
    Inscription : juin 2004
    Messages : 1 397
    Points : 763
    Points
    763

    Par défaut

    Intéressant, et rapide (par rapport à l'autre, donné dans la discussion).
    As-tu profilé ton code ? Sais-tu ce qui consomme le plus ?
    La récupération des valeurs de l'image et la conversion en tableau 2D doit être assez coûteuse, non ?
    Aucune réponse à une question technique par MP.
    Ce qui vous pose problème peut poser problème à un(e) autre

    http://thebrutace.labrute.fr

  3. #3
    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 progfou Voir le message
    Intéressant, et rapide (par rapport à l'autre, donné dans la discussion).
    As-tu profilé ton code ? Sais-tu ce qui consomme le plus ?
    La récupération des valeurs de l'image et la conversion en tableau 2D doit être assez coûteuse, non ?
    Non je n'ai pas profilé le code mais je pense (tres fort) que ce qui est le plus consommateur ce sont les operations de décalage sur les tableaux: l'objectif est de "supprimer" une case d'un tableau et de decaler les cases restantes sur la gauche. Pour faire cela, j'utilise "System.arraycopy" qui copie toute la "fin" du tableau sur lui meme. Nul doute qu'on pourrait accelerer ca en utilisant une liste chainée a la place du tableau: ca ne ferait qu'une seule modification du pointeur suivant/precedant.

    Quand a la conversion image/tableau, meme si elle est couteuse, je ne la fait qu'au début et a la fin de l'algo (et de temps en temps au milieu pour afficher les résultats intermediaires). Mais, au final, le décalage de tableau par System.arraycopy est bcp plus rapide que de decaler un par un tous les pixels de l'image avec un boucle for: c'etait ce que j'avais fait en premier, et pour des raisons de performance je suis passé par les tableau 2D.
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

  4. #4
    Membre du Club
    Inscrit en
    janvier 2008
    Messages
    74
    Détails du profil
    Informations forums :
    Inscription : janvier 2008
    Messages : 74
    Points : 68
    Points
    68

    Par défaut programmation dynamique

    Ce n'est pas de la vrai programmation dynamique que tu fait: les lignes que tu élimine ne sont pas forcèment celles qui ont le moins d'information. Chez moi pour la réduction verticale je rempli la première colonne d'un tableau 2D totalEnergie avec les gradients des pixels correspondants. Puis pour les colonnes suivantes je met dans chaque case totalEnergie[i][j] la valeur gradient(i,j) + min(totalEnergie[i - 1][j], min(totalEnergie[i - 1][j - 1], totalEnergie[i - 1][j + 1]))

    Ensuite je cherche dans la derniere colonne la plus petite energie et à partir de là je vais de la droite vers la gauche construire le chemin.
    C'est plus coûteux que ta méthode (enfin il doit y avoir moyen d'optimiser) et le résultat et un peu différent, plus réaliste je trouve. (j'ai testé avec ton image)

  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

    Tu peux nous poster ton image de résultat (histoire de comparer)

    Dans le papier original, c'est qu'est ce qui est utilisé ?

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

    @FrenchFrogger: Sauf bug dans mon code je fais la meme chose que toi,sauf que mes lignes de basse energie vont de gauche à droite, et toi de droite à gauche. A la vue de l'image de test, c'est peut-etre de là que vient l'amélioration.
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

  7. #7
    Membre du Club
    Inscrit en
    janvier 2008
    Messages
    74
    Détails du profil
    Informations forums :
    Inscription : janvier 2008
    Messages : 74
    Points : 68
    Points
    68

    Par défaut

    Enfin, moi je crée un tableau largeur x hauteur, dans la premiere colonne je met les gradients, dans les colonnes suivantes j'applique la formule du pdf (M(i,j) = e(i,j) + min(M(i−1, j−1),M(i−1, j),M(i−1, j+1))
    J'ai pas l'impression que vous vous y prenez de la même façon, mais peut-être que je me trompe.


    Est-ce que vous savez comment faire un agrandissement "beau"? J'ai beau essayé (gradient Sobel) en ajoutant à chaque fois ligne de basse energie différente des précédentes, ça me donne une image moins moche que l'image B du dauphin dans le pdf officiel, mais pas beaucoup mieux non plus...

  8. #8
    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 FrenchFrogger Voir le message
    Enfin, moi je crée un tableau largeur x hauteur, dans la premiere colonne je met les gradients, dans les colonnes suivantes j'applique la formule du pdf (M(i,j) = e(i,j) + min(M(i−1, j−1),M(i−1, j),M(i−1, j+1))
    J'ai pas l'impression que vous vous y prenez de la même façon, mais peut-être que je me trompe.
    Mon implémentation est différente mais le principe et les formules sont les mêmes. Après avoir testé, il y quelques différences dans l'image finale suivant le sens de calcul gauche/droite. Mais je n'obtient pas quelque chose de beaucoup plus (ou moins) beau. Tu peux poster le résultat de la réduction verticale par 4 sur l'image de test:

    http://xphilipp.developpez.com/contribuez/sea.png

    Est-ce que vous savez comment faire un agrandissement "beau"? J'ai beau essayé (gradient Sobel) en ajoutant à chaque fois ligne de basse energie différente des précédentes, ça me donne une image moins moche que l'image B du dauphin dans le pdf officiel, mais pas beaucoup mieux non plus...
    Je n'ai pas trop testé l'agrandissement. J'ai juste fait implémentation basique et, moi non plus, je n'ai pas trouvé le résultat très "beau". Il faudrait voir si on peut mieux faire en ajoutant un peu de RungeKutta ou de la synthèse.
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

Discussions similaires

  1. Resize d'une image
    Par Anonymous dans le forum C
    Réponses: 6
    Dernier message: 13/07/2008, 22h23
  2. images mobiles avec seam
    Par paolo2002 dans le forum Seam
    Réponses: 4
    Dernier message: 16/06/2008, 16h51
  3. recherche des algorythmes pour images 2d
    Par exxos dans le forum Général Algorithmique
    Réponses: 3
    Dernier message: 24/05/2002, 13h46
  4. lire une image au format RAW
    Par Anonymous dans le forum OpenGL
    Réponses: 5
    Dernier message: 20/05/2002, 00h11
  5. Création image BMP
    Par Anonymous dans le forum C
    Réponses: 2
    Dernier message: 25/04/2002, 16h04

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