Jump to content

Seam Carving for Content-Aware Image Resizing


PiFou86

Recommended Posts

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 :p)

01.jpg

02.jpg

03.jpg

04.jpg

(suggestions, commentaires bien venus)

Link to comment
Share on other sites

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 !

Link to comment
Share on other sites

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 : rdh0wgnk.jpg

la version smart resized : 26dllvyp.jpg

la version cubic-resized de gimp : sxib4dop.jpg

sympatoche ;)

Link to comment
Share on other sites

Ca c'est le premier algo que j'avais pondu :ouioui:. 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.

Link to comment
Share on other sites

Archived

This topic is now archived and is closed to further replies.

×
×
  • Create New...