[image] seam carving

[pseudocode]

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:

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)

[progfou]

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 ?

[pseudocode]

Envoyé par progfou

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.

[FrenchFrogger]

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)

[PRomu@ld]

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

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

[pseudocode]

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

[FrenchFrogger]

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

[pseudocode]

Envoyé par FrenchFrogger

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.