Seam Carving for Content-Aware Image Resizing

[PiFou86]

J'ai fait une implantation bourrin en Java du début de l'article sur le redimensionnement intelligent. Voici le code si ca interesse quelqu'un !

http://pierrefrancois.leon.free.fr/smart-resizing/

Vous pouvez soit prendre le fichier jar (sous windows faire un double clique dessus, sous linux java -jar smart-resizing.jar). Une fois le programme lancé, il demande un fichier image...

(je sais que je l'ai posté dans la section Blabla, mais vu les réactions, j'ai du me trompé de section )

(suggestions, commentaires bien venus)

[PiFou86]

Une image pour tester :

http://www.bretagne.feroc.com/IMG/jpg/plage1.jpg

[windu.2b]

Je suis au taff, mais ce soir je regarde ça et je teste

[PiFou86]

Je viens de faire une petite maj. Maintenant on peut voir la fonction energy. (si ya des volontaires pour en coder d'autre fonction d'énergie..)

donc dernière version :

smart-resising2007090316.tgz

ps: bien sur, c'est toujours aussi bourrin, c'est pas pour de la prod... juste pour du test !

[PiFou86]

Mise à jour de l'archive :

- changement de la fonction de recherche de chemin (plus optimal !)

- ajout d'images dans le message original

[lorinc]

Hello, j'ai fait un patch sur ton code qui change l'algo de calcul de chemin de min energie. Il s'agit d'un algo dégradé parce qu'il ne donne pas le plus court chemin absolu. Je fais un parcours profondeur d'abord avec une aproche gloutonne. Le chemin retenu est donc celui qui possède la plus petite énergie parmis ceux qui garantissent que la transition d'un pixel à un autre est de moindre énergie. La complexité est vachement moindre et l'INpact mémoire est quasi négligeable (pas de double tableau pour stocker les sommes intermédiaires).

voici le patch :

--- SmartResizing.java	2007-09-04 23:39:32.000000000 +0200
+++ SmartResizing.java	2007-09-09 21:02:03.000000000 +0200
@@ -13,6 +13,8 @@ import javax.imageio.*;

import java.io.*;

+import java.util.*;
+
class SmartResizing extends JPanel {
 String m_filename;
 BufferedImage m_img;
@@ -23,25 +25,25 @@ class SmartResizing extends JPanel {
 boolean m_mustShowEnergy;

 public SmartResizing(String filename, EnergyFunction ef) {
-	m_filename = filename;
-	try {
-		m_img = ImageIO.read(new FileInputStream(filename));
-	} catch (Exception e) {
-		JOptionPane.showMessageDialog(null, e.toString(), "Error", JOptionPane.ERROR_MESSAGE);
-		System.err.println(e);
-		System.exit(1);
-	}
+		m_filename = filename;
+		try {
+			m_img = ImageIO.read(new FileInputStream(filename));
+		} catch (Exception e) {
+			JOptionPane.showMessageDialog(null, e.toString(), "Error", JOptionPane.ERROR_MESSAGE);
+			System.err.println(e);
+			System.exit(1);
+		}

-	addComponentListener(new defaultComponentAdapter());
+		addComponentListener(new defaultComponentAdapter());

-	setPreferredSize(new Dimension(m_img.getWidth(),
-					   m_img.getHeight()));
+		setPreferredSize(new Dimension(m_img.getWidth(),
+						   m_img.getHeight()));

-	m_ef = ef;
+		m_ef = ef;

-	update();
+		update();

-	m_mustShowEnergy = false;
+		m_mustShowEnergy = false;
 }

 public void setEnergyFunction(EnergyFunction ef) {
@@ -76,209 +78,138 @@ class SmartResizing extends JPanel {
	update(false, true);
 }

-	/// res[x][y][0] = prevy
-	/// res[x][y][1] = seanenergy
-	public int[][][] computeHSeanCost() {
-	int h = m_img.getHeight() - 2;
-	int w = m_img.getWidth() - 2;
-
-	int res[][][] = new int[w][h][2];
-
-	for (int j = 0; j < h; ++j)
-		res[0][j][1] = m_energy[0][j];
-
-	for (int i = 1; i < w; ++i) {
-		for (int j = 0; j < h; ++j) {
-		int curEnergy = m_energy[i][j];
-
-		int prevY;
-		if (j != 0 && j != h - 1) {
-			int a = res[i - 1][j - 1][1];
-			int b = res[i - 1][j	][1];
-			int c = res[i - 1][j + 1][1];
-
-			if (a < b && a < c) { /// min = a
-			res[i][j][0] = j - 1;
-			res[i][j][1] = a + curEnergy;
-			} else if (c < a && c < b) { /// min = c
-			res[i][j][0] = j + 1;
-			res[i][j][1] = c + curEnergy;
-			} else {  /// min = b
-			res[i][j][0] = j;
-			res[i][j][1] = b + curEnergy;
-			}
-		} else if (j == 0) {
-			int b = res[i - 1][j	][1];
-			int c = res[i - 1][j + 1][1];
-			if (c < b) { /// min = c
-			res[i][j][0] = j + 1;
-			res[i][j][1] = c + curEnergy;
-			} else {  /// min = b
-			res[i][j][0] = j;
-			res[i][j][1] = b + curEnergy;
-			}
-		} else { // j == j - 1
-			int a = res[i - 1][j - 1][1];
-			int b = res[i - 1][j	][1];
-
-			if (a < b) { /// min = a
-			res[i][j][0] = j - 1;
-			res[i][j][1] = a + curEnergy;
-			} else {  /// min = b
-			res[i][j][0] = j;
-			res[i][j][1] = b + curEnergy;
-			}
-		}
-		}
-	}
-
-	return res;
-	}
-
-	public int[] findHSeanWithLowerCost() {
-	int h = m_img.getHeight() - 2;
-	int w = m_img.getWidth() - 2;
-	int sean[][][] = computeHSeanCost();
-
-	int l = 0;
-	for (int j = 0; j < h; ++j) {
-		if (sean[w - 1][j][1] < sean[w - 1][l][1])
-		l = j;
-	}
-
-	int res[] = new int[w + 2];
-
-	res[w + 1] = l;
-	for (int i = w; i > 0; --i) {
-		res[i] = l + 1;
-		l = sean[i - 1][l][0];
-	}
-	res[0] = l;
-
-	return res;
-	}
-
-	public void removeh() {
-	BufferedImage in = new BufferedImage(m_img.getWidth(), 
-						 m_img.getHeight() - 1, 
-						 m_img.getType());
-	
-	int sean[] = findHSeanWithLowerCost();
-
-	Graphics g = getGraphics();
-	g.setColor(Color.RED);
-	for (int i = 0; i < m_img.getWidth(); ++i) {
-		g.drawLine(i, sean[i], i, sean[i]);
-	}
-
-	// suppression de la ligne...
-	for (int i = 0; i < m_img.getWidth(); ++i) {
-		for (int j = 0; j < m_img.getHeight(); ++j) {
-		if (j > sean[i])
-			in.setRGB(i, j - 1, m_img.getRGB(i, j));
-		else if (j < sean[i])
-			in.setRGB(i, j, m_img.getRGB(i, j));
-		}
-	}

-	m_img = in;
-
-	setPreferredSize(new Dimension(m_img.getWidth(),
-					   m_img.getHeight()));

+	public int[] findLowestLine() {
+		int h = m_img.getHeight() - 2;
+		int w = m_img.getWidth() - 2;
+		int res[] = null;
+		int e_min = Integer.MAX_VALUE;
+		
+		//algo approximé rapide
+		for(int i = 0; i < h; i++)
+		{
+			int min_prev = i, min, e_temp=0;
+			int temp[] = new int[w+2];
+			e_temp = 0;
+			
+			for(int j = 1; j < w; j++)
+			{
+
+				min = min_prev;
+				//line précédante ?
+				if( min_prev > 0 && m_energy[j][min_prev-1] < m_energy[j][min_prev])
+					min = min_prev -1;
+				//line suivante ?
+				if( min_prev < h -2 && m_energy[j][min_prev+1] < m_energy[j][min])
+					min = min_prev +1;
+					
+				temp[j] = min;
+				e_temp +=  m_energy[j][min];
+				min_prev = min;
+				
+				//stoppe le calcul si non min
+				if(e_temp > e_min)
+					break;
+			}
+			
+			//sauvegarde du chemin si min
+			if(e_temp < e_min)
+			{
+				e_min = e_temp;
+				res = (int[]) temp.clone();				
+				res[w+1] = res[0];
+			}
+		}

-	update(true, false);
+		return res;
+				  
 }

-	/// res[x][y][0] = prevx
-	/// res[x][y][1] = seanenergy
-	public int[][][] computeVSeanCost() {
-	int h = m_img.getHeight() - 2;
-	int w = m_img.getWidth() - 2;
+	public int[] findLowestCol() {
+		int h = m_img.getHeight() - 2;
+		int w = m_img.getWidth() - 2;
+		int res[] = null;
+		
+		//algo approximé rapide
+		int  e_min = Integer.MAX_VALUE;
+		for(int i = 0; i < w; i++)
+		{
+			int min_prev = i, min, e_temp=0;
+			int temp[] = new int[h+2];
+			
+			for(int j = 0; j < h; j++)
+			{
+				min = min_prev;
+				//col précédante ?
+				if( min_prev > 0 && m_energy[min_prev-1][j] < m_energy[min_prev][j])
+					min = min_prev -1;
+				//col suivante ?
+				if( min_prev < w -2 && m_energy[min_prev+1][j] < m_energy[min][j])
+					min = min_prev +1;
+					
+				temp[j] = min;
+				e_temp += m_energy[min][j];
+				min_prev = min;
+				
+				//stoppe le calcul si non min
+				if(e_temp > e_min)
+					break;
+			}
+			
+			//sauvegarde du chemin si min
+			if(e_temp < e_min)
+			{
+				e_min = e_temp;
+				res = (int[]) temp.clone();
+				res[h+1] = res[0];
+			}
+		}
+		

-	int res[][][] = new int[w][h][2];
-
-	for (int i = 0; i < w; ++i)
-		res[i][0][1] = m_energy[i][0];
+		return res;
+				  
+	}
+		

-	
-	for (int j = 1; j < h; ++j) {
-		for (int i = 0; i < w; ++i) {
-		int curEnergy = m_energy[i][j];
-
-		int prevY;
-		if (i != 0 && i != w - 1) {
-			int a = res[i - 1][j - 1][1];
-			int b = res[i	][j - 1][1];
-			int c = res[i + 1][j - 1][1];
-
-			if (a < b && a < c) { /// min = a
-			res[i][j][0] = i - 1;
-			res[i][j][1] = a + curEnergy;
-			} else if (c < a && c < b) { /// min = c
-			res[i][j][0] = i + 1;
-			res[i][j][1] = c + curEnergy;
-			} else {  /// min = b
-			res[i][j][0] = i;
-			res[i][j][1] = b + curEnergy;
-			}
-		} else if (i == 0) {
-			int b = res[i	][j - 1][1];
-			int c = res[i + 1][j - 1][1];
-			if (c < b) { /// min = c
-			res[i][j][0] = i + 1;
-			res[i][j][1] = c + curEnergy;
-			} else {  /// min = b
-			res[i][j][0] = i;
-			res[i][j][1] = b + curEnergy;
-			}
-		} else { // j == j - 1
-			int a = res[i - 1][j - 1][1];
-			int b = res[i	][j - 1][1];
-
-			if (a < b) { /// min = a
-			res[i][j][0] = i - 1;
-			res[i][j][1] = a + curEnergy;
-			} else {  /// min = b
-			res[i][j][0] = i;
-			res[i][j][1] = b + curEnergy;
-			}
+	public void removeh() {
+		BufferedImage in = new BufferedImage(m_img.getWidth(), 
+							 m_img.getHeight() - 1, 
+							 m_img.getType());
+		
+		int sean[] = findLowestLine();
+
+		Graphics g = getGraphics();
+		g.setColor(Color.RED);
+		for (int i = 0; i < m_img.getWidth(); ++i) {
+			g.drawLine(i, sean[i], i, sean[i]);
		}
-		}
-	}

-	return res;
-	}
+		// suppression de la ligne...
+		for (int i = 0; i < m_img.getWidth(); ++i) {
+			for (int j = 0; j < m_img.getHeight(); ++j) {
+			if (j > sean[i])
+				in.setRGB(i, j - 1, m_img.getRGB(i, j));
+			else if (j < sean[i])
+				in.setRGB(i, j, m_img.getRGB(i, j));
+			}
+		}

-	public int[] findVSeanWithLowerCost() {
-	int h = m_img.getHeight() - 2;
-	int w = m_img.getWidth() - 2;
-	int sean[][][] = computeVSeanCost();
-
-	int l = 0;
-	for (int i = 0; i < w; ++i) {
-		if (sean[i][h - 1][1] < sean[l][h - 1][1])
-		l = i;
-	}
+		m_img = in;

-	int res[] = new int[h + 2];
+		setPreferredSize(new Dimension(m_img.getWidth(),
+						   m_img.getHeight()));

-	res[h + 1] = l;
-	for (int j = h; j > 0; --j) {
-		res[j] = l + 1;
-		l = sean[l][j - 1][0];
-	}
-	res[0] = l;

-	return res;
+		update(true, false);
 }
-
+	
 public void removev() {
	BufferedImage in = new BufferedImage(m_img.getWidth() - 1, 
						 m_img.getHeight(), 
						 m_img.getType());

-	int sean[] = findVSeanWithLowerCost();
+	int sean[] = findLowestCol();

	Graphics g = getGraphics();
	g.setColor(Color.RED);
@@ -379,7 +310,8 @@ class SmartResizing extends JPanel {
	JButton m = new JButton("h-");
	m.addActionListener(new ActionListener() {
		public void actionPerformed(ActionEvent e) {
-			sr.removev();
+			for(int i = 0; i < 10; i++)
+				sr.removev();
			sr.update(false, true);
		}
		});
@@ -388,7 +320,8 @@ class SmartResizing extends JPanel {
	m = new JButton("v-");
	m.addActionListener(new ActionListener() {
		public void actionPerformed(ActionEvent e) {
-			sr.removeh();
+			for(int i = 0; i < 10; i++)
+				sr.removeh();
			sr.update(false, true);
		}
		});

et voici un exemple de ce que ça donne (sur une des images que tu as mise en lien) en comparaison avec un resize classique (faut cliquer pour avoir en grand):

l'original :

la version smart resized :

la version cubic-resized de gimp :

sympatoche

[PiFou86]

Ca c'est le premier algo que j'avais pondu . J'ai changé pour utiliser un algo dit dynamique. Le chemin "se construit tout seul" et ce sans réel surcout. En effet, l'algo est aussi rapide (la complexité est du meme ordre), nous perdons seulement un peu de place (par exemple pour rechercher en colonne : premier algo : (2 * nbligne + 2) * 4 octets, le dynamique (2 * nbligne * nbcol) * 4 octets).

J'ai remarqué que le programme perd beaucoup de temps dans cette partie (symétriquement dans l'autre sens) :

for (int i = 0; i < m_img.getWidth(); ++i) {
for (int j = 0; j < m_img.getHeight(); ++j) {
  if (j > sean[i])
	 in.setRGB(i, j - 1, m_img.getRGB(i, j));
  else if (j < sean[i])
	 in.setRGB(i, j, m_img.getRGB(i, j));
  }
}

Au départ j'ai cru que c'était le calcul d'énergie (deux convolutions + parcours). Il faudrait surement passer par une autre classe que des BufferedImage.