- Werbung -

"Content-aware resizing“: Bildgröße unter Berücksichtigung des Inhalts ändern. Das sind die Begriffe, mit denen Seamcarving beschrieben wird. Dahinter steckt ein Algorithmus, der auf der Siggraph 2007 unter dem Titel "ACM Transactions on Graphics (TOG)“vorgestellt wurde.

Hintergrund

"Content-aware resizing“: Bildgröße unter Berücksichtigung des Inhalts ändern

Das sind die Begriffe, mit denen Seamcarving beschrieben wird. Dahinter steckt ein Algorithmus, der auf der Siggraph 2007 unter dem Titel "ACM Transactions on Graphics (TOG)“vorgestellt wurde. Entwickelt wurde er von Shai Avidan (Mitsubishi Electric Research Labs) und Ariel Shamir (The Interdisciplinary Center & MERL), die unterdessen wohl beide von Adobe "eingekauft" wurden. Man kann die Wirkung des Algorithmus online hier testen. 

Seamcarving befasst sich mit der Änderung einer Bildgröße. Hierzu kennen wir üblicherweise 2 Verfahren: das Ausschneiden eines Bildteiles mit den gewünschten Proportionen ("Cropping") oder das "Verzerren" des Bildes bis zur gewissen Größe ("Scaling"). Beides sind erprobte Verfahren - oft aber sind beide nicht optimal. "Seamcarving" ist nun quasi die "dritte Methode" - sie verändert die Bildgröße unter Beibehaltung des gesamten "wichtigen" Inhalts. Hierbei "löscht" das Verfahren "unwichtige" Bildteile oder ergänzt das Bild um weitere "unwichtige" Details. Die Bilder hier zeigen das Prinzip ganz gut.

 

 

 

 

 

 

 

Links das Originalbild, rechts eine schmalere Version, unten dann eine breitere. (Achten Sie mal auf die Vögel am Strand!) 

Momentan kann Photoshop CS4 "Seamcarving", sogar interaktiv und stufenlos. GIMP kann es über ein Plugin: "Liquid Rescale" heißt es. Weiterhin findet man eine Benutzeroberfläche zum Original-Algorithmus unter dem Namen "Seamcarving-GUI" für verschiedene Betriebssysteme im Netz.

Bedeutung und Prinzip

"Seam" ist ein Pfad, eine Kante, ein Saum, eine Fuge. "Carven" heißt schneiden, einritzen, schnitzen. Grundsätzlich findet Seamcarving einen "weniger wichtigen Pfad" in einem Bild und entfernt resp. verdoppelt ihn. Der Algorithmus wurde 2008 sogar unter der Beteiligung von Michael Rubinstein für Videos weiter entwickelt. Um ihn zu verstehen, benötigt man auch ein bisschen Mathematik. Im Prinzip besteht er aus 3 Schritten:
- Helligkeitswerte bestimmen und Kanten finden,
- Energiemap bestimmen,
- Pfad bestimmen und löschen/verdoppeln, (danach "glätten"=interpolieren).

Die Kanten in einem Bild erachtet der Algorithmus als "wichtig", weil hier relevante Bildinformation wiedergegeben wird. Um sie zu finden, benutzt man Filter, welche die mathematische Operation "Faltung" benutzen. Dazu betrachtet man nur die Helligkeitswerte eines Bildes, was sich durch eine Umwandlung in ein Graustufenbild bewirken lässt.
Das nebenstehende Bild zeigt nun einen Ausschnitt aus einem Bild - genau genommen sollen dies die Helligkeitswerte von 9 Pixeln sein.

Dazu benötigt man einen "Filterkern", mit dem man die Faltung dann durchführt. Das Bild rechts zeigt einen solchen Filterkern. Programme wie GIMP erlauben es, mit solchen selbstdefinierten Filterkernen zu arbeiten. Sie finden dies dort im Menü unter "Filter" / "Allgemein" / "Faltungsmatrix". (GIMP sieht eine 5x5-Matrix vor - wenn Sie die äußeren Felder leer lassen, können Sie auch mit dieser 3x3-Matrix arbeiten!)

Der Filterkern wird nun quasi über den Bildausschnitt gelegt, alle übereinanderliegenden Zahlen werden dann multipliziert, die Ergebnisse addiert und das Gesamtergebnis ist dann der Wert des neuen (mittleren) Pixels. (Siehe Rechnung und Bild nebenan.)
Überlegen wir kurz, wie dieser Filter arbeitet: wenn alle Pixel etwa gleich hell sind, liefert er einen Wert nahe Null (also dunkelgrau bis schwarz). Waren nun aber die Pixel rechts z.B. schwarz und die links weiß, dann erhalten wir hier einen Wert in der Nähe von weiß; also: Kanten werden "gefunden", strukturarme Gebiete ignoriert. In dieser Form findet der Filter speziell vertikale Kanten - wenn Sie die Zahlen in die obere und untere Reihe schreiben statt in die linke und rechte Spalte, findet er waagerechte Kanten. (Probieren sie es in GIMP ruhig aus!) Spezielle Filter finden alle Kanten: "Sobel" und "Laplace" sind die bekanntesten Vertreter (in GIMP haben sie ein eigenes Menü: "Filter" / Kanten finden" / "Sobel" oder "Lapalace".
Das Ergebnis zeigt nebenstehendes Bild.

 Nun muss - auf der Basis der gefundenen Kanten - eine "Energymap" für die Pfade aufgebaut werden. Hierzu werden die Helligkeitswerte - zum Beispiel von oben nach unten - aufsummiert. Ein Pfad, der über wenige Kanten lief, hat dann ganz unten eine kleinere Summe stehen als andere. Genau genommen wird jedem Punkt die Summe aus seinem Helligkeitswert und dem Minimum der drei über ihm liegenden Punkte zugeordnet. Das Bild soll diesen Zusammenhang verdeutlichen.

 Die beiden abgebildeten Tabellen sollen eine Helligkeitsverteilung zeigen (links), während in der unteren Tabelle die erläuterte Summenbildung stattgefunden hat und ein "Seam" mit minimaler Energie rot dargestellt ist. Dieser kann nun entfernt beziehungsweise verdoppelt werden. Normalerweise führt die Software danach jeweils noch eine "Glättung" über eine Interpolation durch, damit nicht harte Übergänge oder Blockstrukturen entstehen.
Eigentlich müsste die Energymap nach jeder Aktion neu berechnet werden - meistens werden aber so 10 bis 30 Berechnungen für Seams mit "geringer Energie" im Voraus durchgeführt, damit etwas zügiger gearbeitet werden kann.

Einen Schritt weiter als die Energymap geht die "Weightmap", die es noch erlaubt, bestimmte Bildteile zu gewichten. Man versieht - z.B. in der Seamcarving-GUI - einzelne Bildbereiche über einen Stift einfach mit einer grünen oder roten Markierung (grün bedeutet: unbedingt beibehalten, rot entsprechend: soll gelöscht werden). Diese Bildteile werden dann "schwerer" oder "leichter". Arbeitet man mit einer solchen Weightmap, kann der Algorithmus zum Beispiel dann - ohne Bildgrößenänderung - einfach bestimmte Bildteile entfernen und durch "umgebungsähnliche" Strukturen ersetzen. Oder aber man kann ihn durch eine grüne Markierung dazu bringen, bestimmte Bildteile als "wichtig" zu erachten, obwohl das System selbst zu einem anderen Schluss käme.

Diese Bildmontage zeigt ein solches Beispiel: das Originalbild befindet sich rechts oben, in der Seamcarving-GUI 1.10 wurde der Hai grob markiert, und mit dem Remove-Knopf haben wir - wie rechts unten zu sehen ist - ein haifreies Gewässer erzeugt.