Laden...

Seam Carving: zu entfernende Pixel ermitteln

Erstellt von pdelvo vor 15 Jahren Letzter Beitrag vor 15 Jahren 6.832 Views
pdelvo Themenstarter:in
1.346 Beiträge seit 2008
vor 15 Jahren
Seam Carving: zu entfernende Pixel ermitteln

Hallo zusammen,
Ich möchte ein Programm mit Seam Carving schreiben. ICh habe auch schon angefange und habe ein Energiebild berrechnet.
Jetzt komme ich aber nicht sorecht weiter.
Vieleicht hat ja einer eine Idee wie man da machen kann. Noch eine Idee von mir wäre Multithreading(Vieleicht mit den Parallel Extension?) Hier ist mein Code für das Energiebild :


//Das ist das Array für das Energiebild
//Hier wird für jedes Pixel eine Zahl
//gespeichert. Das wird genutzt um nachher die
//Pixel die nicht gebraucht werden
//zu entfernen.
int[,] EnergieBild;
private void ErstelleEnergieBild()
{
//Initialisiere das Energiebild
EnergieBild = new int[pictureBox1.Image.Width, pictureBox1.Image.Height];
Bitmap map = (Bitmap)pictureBox1.Image;
int[,] bw = map.SchwarzWeiß();
int w = map.Width-1;
int h = map.Height - 1;
Parallel.For(0, w, i =>
{
for (int j = 0; j < h; j++)
{
EnergieBild[i, j] = GetEnergie(bw, j, i);
//int ener = EnergieBild[i, j] + 100;
//((Bitmap)pictureBox1.Image).SetPixel(i, j, Color.FromArgb(ener,ener,ener));
}
});

}
private int GetEnergie(int[,] bit, int i, int j)
{
List<int> templist = new List<int> );
templist.Add(bit[j,i]);
if (i != 0)
{
templist.Add(bit[j, i - 1]);
if (j != 0)
{
templist.Add(bit[j - 1, i - 1]);
}
}
if (j != 0)
{
templist.Add(bit[j - 1, i]);
if (i > bit.GetLength(1) - 1)
{
templist.Add(bit[j - 1, i + 1]);
}
}
if (i > bit.GetLength(1) - 1)
{
templist.Add(bit[j, i + 1]);
if (j < bit.GetLength(0) - 1)
{
templist.Add(bit[j + 1, i + 1]);
}
}
if (j < bit.GetLength(0) - 1)
{
templist.Add(bit[j + 1, i]);
if (i > 0)
{
templist.Add(bit[j + 1, i - 1]);
}
}
int u = 0;
int temp = 0;
foreach (int x in templist)
{
temp += x;

}
temp /= templist.Count;
u = Math.Abs(temp - bit[j, i]);
return u;
}

Danke schonmal im vorraus

49.485 Beiträge seit 2005
vor 15 Jahren

Hallo pdelvo,

was genau ist denn dein Problem?

Hallo zusammen,

für alle die es interessiert, ist diese Youtube-Video sehr erhellend:

Image Resizing by Seam Carving

herbivore

pdelvo Themenstarter:in
1.346 Beiträge seit 2008
vor 15 Jahren

Mein Problem ist es diePxel die entfernt werden sollen zu ermitteln.

pdelvo

5.657 Beiträge seit 2006
vor 15 Jahren

Mein Problem ist es diePxel die entfernt werden sollen zu ermitteln

Naja, das ist ja im Grunde der Algorithmus, hast du dich da schon mal belesen? Du mußt schon eine konkrete Frage stellen, ich schätze, daß sich hier noch keiner ausgiebig damit beschäftigt hat.
Hier gibt es übrigens eine c++ Umsetzung: http://www.corsix.org/retargetr.html

Christian

Weeks of programming can save you hours of planning

pdelvo Themenstarter:in
1.346 Beiträge seit 2008
vor 15 Jahren

Ich hab mir das mal angeguckt, aber bei C++ steh ich auf dem Schlauch. Außerdem lässt sich der Code nicht compipieren. Vieleicht hat sich das doch einer schon angeschaut und kann mir einen Tip geben.
trotzdem Danke

pdelvo

5.657 Beiträge seit 2006
vor 15 Jahren

Mich würde das ganze ja auch, aber du machst es und schon sehr schwer, dir zu helfen.
Welche Frage hast du denn eigentlich? Eine Umsetzung in C# wirst du kaum finden, der Algorithmus ist doch erst auf der Siggraph vorgestellt worden, oder? Und eine konkrete Antwort bekommst du wahrscheinlich erst auf eine konkrete Frage.

Hast du denn den Artikel dazu gelesen? Hast du schon versucht, etwas umzusetzen?

Christian

Weeks of programming can save you hours of planning

pdelvo Themenstarter:in
1.346 Beiträge seit 2008
vor 15 Jahren

Ich habe versucht mit dem Energiebild, welches ich mit dem oben geposteten Code erstellt habe, die Pixel zu ermittel die nicht gebraucht werden.Dazu habe ich zuerst in der ersten Spalte von oben von links nach rechts den Pixel mit dem nidrigsten Wert zu ermitteln. Dann gehe ich in einer Schleife jedes mal einmal nach unten und Suche Dort den niedrigsten, der vom x-Wert höchstens eins Abweicht.
Das Problem ist, dass ich das Energiebild wahrscheinlich falsch berrechnet habe, denn ich bekomme bei fast jedem Pixel den Gleichen Wert raus. Und außerdem weiß ich nicht ob ic den mögliche Unterschied bei dem x Wert vergrößern muss(z.B. 2).
Ich hoffe jemand versteht mein Problem.

Gruß pdelvo

5.657 Beiträge seit 2006
vor 15 Jahren

Ich hoffe jemand versteht mein Problem.

Kann ich mir ehrlich gesagt nicht vorstellen. Du schreibst, das als wäre der Algorithmus allen geläufig und man müßte nur mal drüberschauen. Dein Problem mußt du schon genauer eingrenzen. Ich mache es nicht gerne, aber an dieser Stelle muß ich dich einfach auf die Foren-Regeln aufmerksam machen: [Hinweis] Wie poste ich richtig? (Punkt 4, 5 und 9).

Das Problem ist, dass ich das Energiebild wahrscheinlich falsch berrechnet habe, denn ich bekomme bei fast jedem Pixel den Gleichen Wert raus. Und außerdem weiß ich nicht ob ic den mögliche Unterschied bei dem x Wert vergrößern muss(z.B. 2).

Hast du mal versucht, die Energiefunktion ausgeben zu lassen und mit den Beispiel-Bildern oder den Bildern im Video verglichen? Die Energie-Funktion im Beispiel-Projekt sieht so aus:


void Retarget::_image_t::CalculateEnergyData()
{
	unsigned char* pSourcePixel = pData;
	long* pEnergyDataDest = pEnergyData;
	long* pFlexDest = pEnergyDataFlex;
	long iTotalEnergy = 0;
	for(int iY = 0; iY < iHeight; ++iY)
	{
		for(int iX = 0; iX < iWidth; ++iX)
		{
			long iDiffTotal = 0;
			long iDiffCount = 0;
			for(int iYSample = iY - 3; iYSample <= iY + 3; ++iYSample)
			{
				if(iYSample >= 0 && iYSample < iHeight)
				{
					for(int iXSample = iX - 3; iXSample <= iX + 3; ++iXSample)
					{
						if(iXSample >= 0 && iXSample < iWidth && (iXSample != iX || iYSample != iY) )
						{
							for(int iChannel = 0; iChannel < 3; ++iChannel)
							{
								iDiffTotal += abs(pSourcePixel[iChannel] - pData[iYSample * iPitch + (iXSample * 3) + iChannel]);
							}
							++iDiffCount;
						}
					}
				}
			}
			iDiffCount /= 2;
			pEnergyDataDest[0] = (iDiffTotal + iDiffCount / 2) / iDiffCount;
			pFlexDest[0] = 0;
			iTotalEnergy += pEnergyDataDest[0];

			pSourcePixel += 3;
			pEnergyDataDest += 1;
			pFlexDest += 1;
		}
	}

	iAverageEnergy = iTotalEnergy / (iWidth * iHeight * 2);
}

Wenn du mit C++ nix anfangen kannst, laß es dir in C# übersetzen (z.B. mit SharpDevelop oder dem Reflector). Zum Kompilieren brauchst du selberständlich die wx-Bibliothek.

Ansonsten gibs hier noch ein Delphi-Projekt, falls dir das mehr zusagt: http://kleinerfuchs.kl.funpic.de/

Schöne Grüße,
Christian

PS: @all
Der Algorithmus ist einfach genial und für Programmierer und Grafiker sehr interessant. Hier kann man es auch mal online ausprobieren, damit man sieht, worum es geht: http://rsizr.com/

Weeks of programming can save you hours of planning

pdelvo Themenstarter:in
1.346 Beiträge seit 2008
vor 15 Jahren

Ja hab ich. Die ähneln sich aber nicht wirklich. Ich hab aber nochmal gegoogled. Ich hab jetzt eine Bibliothek gefunden die die die Kantenerkennung durchführt(Link).

Nochmal zu dem Algorithmus :
Zuerst wird eine Kantenerkennung durchgeführt.(Siehe oben) Danach werden den Pixeln die nahe der Kanten liegen höhere Werte zugeteilt.(Das nennt man dann Energiebild). Zum Schluss werden dann Pfade durch die Pixel mit den niedrigeren Weten (Seams) gefunden und gelöscht.

Der Algorithmus ist also garnicht so schwer. Ich frag mich nur warum nicht vorher jemand auf die Idee gekommen ist. Ich melde mich nochmal wenn ich nicht mehr weiterweiß.

Gruß pdelvo

pdelvo Themenstarter:in
1.346 Beiträge seit 2008
vor 15 Jahren

Juhu😁 😁 😁 😁 😁
Es geht!
Somit bin ich meinen Recherchen nach der erste der das in C# nachgebildet hat8)
Jetzt muss ich das nur noch perfomanter machen. Und noch ein par Kommentare reinpacken. Dann werde ich das Projekt online stellen.

pdelvo👍

5.657 Beiträge seit 2006
vor 15 Jahren

Hi pdelvo!

Super daß du das hingekriegt hast, kannst du uns ein paar Infos dazu geben, wie's funktioniert?

Ich überlege, ob man den Algorithmus auch auf der GPU implementieren kann, dann könnte man auch große Bilder in Echtzeit äh...retargeten oder wie das auf Deutsch heißt.

Wie schnell läuft das bei dir?

Schöne Grüße,
Christian

Weeks of programming can save you hours of planning

946 Beiträge seit 2008
vor 15 Jahren

Somit bin ich meinen Recherchen nach der erste der das in C# nachgebildet hat8)

Gratuliere, ist sicher eine grosse Leistung... aber du bist nicht der Erste.
Der 3. Treffer unter Google ist Seam Carving: Content-aware image resizing

pdelvo Themenstarter:in
1.346 Beiträge seit 2008
vor 15 Jahren

Schade. Egal.👍

Also von Geschwindigkeit ist gerade noch keine Rede. Enen Seam zu entfernen dauer ca. 15 Sekunden. Aber es funktioniert.Mich wundert es das ich das mit meinen 14 Jahren und ca 3/4 Jahren Erfahrung geschaft habe. Ich habe das Projekt angehangen. Vieleicht kannst du dir das mal Anschauen.
Also der langsame Teil ist in dem Thread die zweite Schleife.

PS : Ich sehe gerade auf der verlinkten Seite das dort steh das ein Teil in Python geschrieben ist8)

Gruß pdelvo

5.657 Beiträge seit 2006
vor 15 Jahren

Naja, sieht doch ganz gut aus!
Hier gibt es auch noch eine Umsetzung in C++: http://sourceforge.net/projects/c-a-i-r/

Auf der Seite, die See Sharp gepostet hat, hab ich einen interessanten Kommentar mit Optimierungstips gefunden, die ich mal zitieren will:

I don't have exact times for determining each individual seam removal, however scaling an image down from 1024x678 to 800x600 takes about 15 seconds.

Some things that can be done to increase speed:

  1. Don't recalculate the edge detection image every time. You can get away with only calculating it every so often and still get good results.
  2. Resize the grayscale of the image along with everything else. Saves one extra step for edge detection.
  3. Minimize the times when you need to do bounds-checking. Optimize your loops so areas that need bounds checking are handled separately.

Attempting to preserve unchanged portions of the energy map may be more costly than actually fully recalculating it. Depending on where a seam was removed, you may only be left with less than 1/3 of the energy map unchanged. (von http://blog.eikke.com/index.php/ikke/2007/09/02/seam_carving_content_aware_image_resizin)

Der Pfadfindungs-Algorithmus ist bei weitem die kostspieligste Berechnung, so daß man mit der Optimierung dort anfangen sollte. Für eine Umsetzung auf der Grafik-Hardware scheint es sich so jedenfalls nicht zu eignen.

Weeks of programming can save you hours of planning

pdelvo Themenstarter:in
1.346 Beiträge seit 2008
vor 15 Jahren

Hast du eine Idee wie man das optimieren könnte. Ich habe gerade keine Idee

5.657 Beiträge seit 2006
vor 15 Jahren

Naja, ich hab mir bisher nur über eine Umsetzung auf der GPU Gedanken gemacht.
Wenn du da optimieren willst, mußt du dich zumindest mit PathFinding-Algorithmen auseinandersetzen. Das Finden der Seams ist ja das aufwändigste an der ganzen Sache. Wenn du einen gut optimierten Algorithmus hast, kannst du da einiges rausholen.

Hier gibs ein paar allgemeine Infos dazu:* http://de.wikipedia.org/wiki/Pathfinding

Den Algorithmus brauchst du nichtmal selbst zu schreiben, es gibt schon einige Umsetzungen z.B. auf CodeProject:

Schöne Grüße,
Christian

Weeks of programming can save you hours of planning

1.361 Beiträge seit 2007
vor 15 Jahren

Hi pdelvo,

ich hab mal kurz in deinen Code reingeschaut.
Erstmal, was zu optimieren ist: Nicht ständig neue und aberneue Bitmaps erzeugen 🙂

Und was den Algorithmus angeht, du hast es genau falsch rum 😉 Du wählst einen Weg aus mit lokal ++maximaler ++Energie.
Also gerade solche Pixel, wo viel im Bild lost ist (Kanten usw) .
Aber man will ja gerade Seams entfernen, wo wenig los ist. (also ++minimalen ++Weg finden)

Du musst also bei

EnergiePoints[xw, yw] >= klpoints

immer das Vorzeichen umdrehen.

Zweites großes Problem ist, dass du bei der Pfadsuche **greedy **vorgehst.

Greedy-Algorithmen [...] zeichnen sich dadurch aus, dass sie schrittweise denjenigen Folgezustand auswählen, der zum Zeitpunkt der Wahl den größten Gewinn bzw. das beste Ergebnis verspricht [...]
Greedy-Algorithmen sind meist schnell, lösen viele Probleme aber nicht optimal.

Und hier bedarf es aber eines global optimalen Pfades.
Du wählst dir minimale Energie in oberster Zeile: Das ist der Start von Pfad. Und dann gehst du von dort aus immer nach (links-/rechts-)unten, je nachdem wo wieder die minimale Energie ist.
Vielleicht ist es aber schlauer, ruhig mal etwas mehr Energie aufzunehmen, wenn dafür man in Bereiche kommt, wo dann wieder besonders wenig Energie ist. (halt typisches Problem der globalen Optimierungsfindung.

Jedenfalls musst du hier alle möglichen Pfade durchgehen. Und da der native BruteForce-Algo zu langsam dafür wäre, gilt es des Prinzip der dynamischen Programmierung zu nutzen. (Bekannt von Lösungen zum Rucksackproblem, oder der Berechnung der Levenshtein-Distanz von Strings, oder oder oder)

Ob A* oder sonstige Graphen-Algorithmen sich hier besser schlagen, weiß ich nicht. Ich könnte mir vorstellen dass durch die zusätzlichen Datenstrukturen der Gesamtoverhead bei denen größer ist (auch wenn nur weniger Knoten zu besuchen sind), als bei der Methode mit dynamischer Programmierung.

beste Grüße
zommi

5.657 Beiträge seit 2006
vor 15 Jahren

Hi zommi!
Endlich mal einer, der sich auskennt 😉
Von der Dynamischen Programmierung hab ich schonmal gehört, aber ich hab noch nie richtig verstanden, wie es eigentlich funktionert. Dafür hab ich ein Problem, für daß sich die Dynamische Programmierung gut eignen würde: Dynamische Programmierung

Schöne Grüße,
Christian

Weeks of programming can save you hours of planning

1.361 Beiträge seit 2007
vor 15 Jahren

Hallo,

ich wecke mal diesen alten Thread auf, weil mich auch letztens die Lust gepackt hatte als ich mal wieder auf das Seam-Carving gestoßen bin.

Anbei also ein kleines C#-Progrämmchen mit 4 Beispielbildern.

Und es geht relativ flott.
Also im Vergleich zu anderen Implementationen im Netz 😁
Wobei ich momentan für die Bild-Operationen auch mit Pointern (also unsafe) arbeite.
Ein Seam wird so in wenigen Millisekunden entfernt.

So kann man (bei nicht all zu großen Bildern) fast live vergrößern und verkleinern.

Demnächst kommt dann noch SourceCode und Erläuterungen.

beste Grüße
zommi

5.657 Beiträge seit 2006
vor 15 Jahren

Hi zommi!

Das ist ja wirklich genial, du bist mein Held 👍

Ist schon erstaunlich wie schnell das geht und wie gut die Qualität der Bilder ist. Selbst die Bilder mit den Gebäuden kann man ziemlich weit skalieren, bis die Linien sich verkrümmen. Allerdings geht es (bisher?) nur horizontal zu skalieren, nicht vertikal. Und auch nur zu verkleinern, irgendwo hatte ich mal darüber gelesen, daß man nach dem gleichen Prinzip auch Pixel einfügen kann, um das Bild zu vergrößern.

Das ganze als Plugin für den Fotoshop wäre Klasse, aber ich hab keine Ahnung wie man sowas macht 🙂

Schöne Grüße,
Christian

Weeks of programming can save you hours of planning

1.361 Beiträge seit 2007
vor 15 Jahren

Das ganze als Plugin für den Fotoshop wäre Klasse

Man nehme Photoshop CS4 und nutze die bereits eingebaute Funktion "Content Aware Scaling" 🙂

...daß man nach dem gleichen Prinzip auch Pixel einfügen kann, um das Bild zu vergrößern.

Das stimmt, sollte eigentlich kein Problem sein. Anstatt einen Seam zu entfernen wird er einfach verdoppelt. (anschließend aber trotzdem als "entfernt" markeirt, damit er im nächsten Schritt nicht wieder ausgewählt wird, da er ja eigentlich immernoch die minimalste Energie hätte)

Allerdings geht es (bisher?) nur horizontal zu skalieren, nicht vertikal

Ja, aber das merkt man ja daran, dass ich MinSize und MaxSize festgesetzt habe 😉
Das Vertikale Skalieren verläuft natürlich quasi gleich. (Im Notfall wird das Bild intern um 90 grad hin- und anschließend wieder zurückgekippt 😉)

Aber wenn ich mich recht entsinne, ist es etwas schwieriger gleichzeitig beide Dimensionen zu skalieren. Es macht nämlich einen Unterschied ob man zuerst komplett x-skaliert und danach y-skaliert. Oder vielleicht immer abwechselnd einen vertikalen und eine horizontalen Seam entfernt. Das ist mir noch nicht ganz klar.

Aber bevor ich da Erweiterungen mache, wird der Code aufgehübscht und veröffentlicht. 🙂

beste Grüße
zommi

5.657 Beiträge seit 2006
vor 15 Jahren

Man nehme Photoshop CS4 und nutze die bereits eingebaute Funktion "Content Aware Scaling" smile

Ahso, naja ich verwende kein Fotoshop 😃 Ich hab Paintshop Pro, da gibs sowas nocht nicht...

Anstatt einen Seam zu entfernen wird er einfach verdoppelt.

Könnte aber zu Artefakten führen. Ist es da nicht besser, aus dem Seam mit der geringsten Energie zwei neue Seams zu erstellen, indem man mit den Nachbar-Seams interpoliert? Dann muß man sich auch nicht mehr merken, welche Seams dupliziert wurden, sondern kann den Algorithmus einfach im nächsten Schritt weiterlaufen lassen. Nur so eine Idee...

Aber wenn ich mich recht entsinne, ist es etwas schwieriger gleichzeitig beide Dimensionen zu skalieren. Es macht nämlich einen Unterschied ob man zuerst komplett x-skaliert und danach y-skaliert. Oder vielleicht immer abwechselnd einen vertikalen und eine horizontalen Seam entfernt. Das ist mir noch nicht ganz klar.

Kommt darauf an, wie aufwendig das erstellen der Seams ist. Und ob man gleichzeitig die Seams in X- und Y-Richtung erstellen kann.

Ich hab es mal mit einem 4K-Bild probiert, da dauert das Laden es ziemlich lange. Die CPU-Auslastung liegt bei 50 % bei meinem DualCore. Kann man den Algorithmus vielleicht parallel verarbeiten? Im einfachsten Fall eine for oder foreach Schleife mit Parallel.For bzw. Parallel.Foreach ersetztn...?

Ansonsten: Hut ab, und

Aber bevor ich da Erweiterungen mache, wird der Code aufgehübscht und veröffentlicht. 😃

alle Achtung!

Christian

Weeks of programming can save you hours of planning

1.361 Beiträge seit 2007
vor 15 Jahren

Hier nun der vorläufige SourceCode.

Erläuterungen sollen auch noch kommen.

beste Grüße
zommi

pdelvo Themenstarter:in
1.346 Beiträge seit 2008
vor 15 Jahren

Das sieht super aus. einen kritikpunkt habe ich aber. du solltest fehler abfangen. wenn ich zum beispiel bei dem Öffnen Dialog auf Abbrechen klicke, gibt es einen fehler.

Gruß pdelvo