Der Seam-Carving-Algorithmus

Via Twitter auf diese Anregung gestoßen, von dort zu dieser ausführlichen und sehr hilfreichen Princeton-Programmieraufgabe geleitet worden, und am Ende einfach Wikipedia dazu gelesen, wo man das schön interaktiv ausprobieren kann. Natürlich zum Lernen gleich nachprogrammiert und Blogpost daraus gemacht, damit es sich lohnt und ich es wirklich verstehe. Aber man kann statt dessen auch einfach Wikipedia lesen, da steht das auch alles.

Es geht um einen gar nicht mal so alten Algorithmus zur Bildbearbeitung. Nehmen wir mal dieses Bild, das wir bearbeiten wollen:

Da sieht man sechs Tiere, das Bild ist 700 Pixel breit, und wenn man nur 350 Pixel Platz hat für ein Bild, dann kann man es entweder verkleinern (alles wird klein), zuschneiden (aber dann fehlen Tierteile) oder zusammenquetschen (aber dann sieht alles so schmal aus). Eigentlich möchte man vielleicht, dass die Tiere einfach näher bei einander wären, mit weniger Grün dazwischen, davon gibt es eh genug.

Und das kann der Seam-Carving-Algorithmus. Aus jeder Zeile des Bildes soll erst einmal ein Pixel verschwinden, dann ist das Bild einen Pixel schmaler. Dabei wird zuerst für jeden Pixel bestimmt, wie wichtig er ist. (Zu den Details später.) Die Wichtigkeit der Pixel sieht man hier:

Wenn man in jeder Zeile den unwichtigsten Pixel entfernt, und das alles 350 mal wiederholt, kommt leider nicht ganz das heraus, was man möchte:

Man sieht, dass die Bildpixel, die zu den wichtigen Elementen gehören (den Tieren), noch alle vorhanden sind und demnach aus jeder Zeile viele – nämlich 350 – zumeist grüne, also tatsächlich eher unwichtige Pixel verschwunden sind. Aber das Bild ist verzerrt – aus der ersten Zeile sind vielleicht Pixel aus der linken Hälfte verschwunden, danach welche aus der rechten, dann immer wieder abwechselnd. Hier sind die unwichtigsten Pixel des ersten Durchgangs rosa markiert:

Man sieht, eher sprunghaft. (Dass sie im mittleren Bereich halbwegs zusammenhängen, ist Zufall und passt für mein Beispiel gar nicht so.)

Abhilfe schafft das seam carving. Seam heißt hier so viel wie Ader, und zwar die aus dem Bergbau. Man beginnt mit dem unwichtigsten Pixel in der ersten Zeile und bahnt sich von diesem aus einen Weg nach unten, wobei man immer nur die Wahl hat zwischen dem Pixel unmittelbar darunter oder dem links oder rechts davon. Das macht man so, dass man ganz unten den minimalen aller möglichen derartigen Wege hat. (Wie man das macht: später.) Dann kriegt man beim ersten Durchgang diese Ader ganz rechts im Bild:

Wenn man alles rechts der rosa Linie einen Pixel nach links verschiebt, fällt das sehr viel weniger auf, als wenn man das bei den versprengten rosa Punkten oben machen würde. Wiederholt man das 350 mal, kommt folgendes Bild heraus:

Die Proportionen der Tiere sind größtenteils erhalten, obwohl das Bild nur halb so breit ist. Nur die Kuh rechts unten ist schmaler, aber nicht am Kopf, so dass es wenig auffällt.

Ähnlich lässt sich diese Schafherde zusammentreiben:

Halb so breit:

Ich musste ein bisschen suchen, bis ich geeignete Bilder zum Demonstrieren fand. Sinnvoll ist das, wenn mindestens am rechten und am linken Bildrand Objekte sind, die sich vom Rest abheben, die also beim Ergebnis dabei sein sollen, und wenn dazwischen neben eventuellen anderen Objekten viel gleichartige Fläche ist – Himmel, Wasser, Wiese. Oft ist der Algorithmus weniger erfolgreich. Hier ein Original:

Und die wieder um 50% verschmälerte Fassung, was zugegeben schon auch recht viel ist. Die Proportionen sind weitgehend okay, aber es fehlen schlicht Stellen:

Natürlich gibt es noch Möglichkeiten, den Algorithmus schneller oder besser zu machen, aber mir reicht das erst einmal.

Technische Details

Drei Probleme habe ich oben allenfalls angedeutet: 1. Wie findet man heraus, welcher Pixel wichtig ist und welcher nicht? 2. Wie findet man so einen seam, einen relativ unwichtigen vertikalen Pfad? Und: 3. Wie entferne ich diesen Pfad aus dem Bild? Das erste Problem ist das interessante, und die anderen beiden sind programmiertechnisch fisseliger, als ich erwartet hatte.

1. Energie/Wichtigkeit eines Pixels

Gespeichert habe ich die Energien in einem eindimensionalen int-Array der Länge Bildgröße*Bildbreite. Wahrscheinlich gibt es mehrere Möglichkeiten, die Energie eines Pixels (heißt in der Anleitung, die ich verwendet habe, so, energy) zu berechnen. Die oben verlinkte Anleitung macht das so:

  1. Berechne die Rot-Differenz zwischen dem linken und dem rechten Nachbarpixel des Pixels, dessen Energie bestimmt werden soll.
    In Java bestimmt man die rgb-Anteile eines Pixels (x,y) des BufferedImage image so:
    int r1 = new Color(image.getRGB(x,y)).getRed();
    int g1 = new Color(image.getRGB(x,y)).getGreen();
    int b1 = new Color(image.getRGB(x,y)).getBlue();
    Natürlich ist es umständlich, aus dem mit getRGB erhaltenen int-Wert erst wieder eine Farbe machen zu müssen, um sich daraus dann wieder mit getRed() den Rotwert geben zu lassen. Das geht mit Bitmanipulation schneller, aber das haben wir in der Schule noch nicht.
  2. Quadriere diesen Rot-Unterschied.
  3. Mache das gleiche für die Unterschiede bei den Grün- und Blau-Anteilen.
  4. Wiederhole das alles für die Unterschiede zwischen den Pixeln über und unter dem Pixel, dessen Energie bestimmt werden soll.
  5. Addiere diese sechs Quadrate. Das ist die Energie!
  6. Randpixel: Die linke Spalte hat die rechte als linken Nachbarn, die oberste Zeile hat die unterste als oberen Nachbarn, und jeweils umgekehrt. Alle Pixel haben also zwei horizontale und zwei vertikale Nachbarn.

2. Finden eines minimalen Pfades

Auch dafür gibt es viele verschiedene Möglichkeiten, die aber natürlich alle zum selben Ergebnis führen. Ich habe das, der Anleitung folgend, so gemacht. Gespeichert wird der (vertikale) Pfad in einem eindimensionalen int-Array der Länge Bildhöhe.

Erster Teil, Anpassung der Energiewerte:

  1. Ändere nichts an den Energiewerten der Pixel in der ersten Zeile.
  2. Betrachte für jeden Pixel der Zeile darunter die zwei bis drei oberen Nachbarn (Randpixel haben hier nur zwei obere Nachbarn). Addiere den kleinsten der zwei oder drei Energiewerte zum eigenen Energiewert.
  3. Wiederhole das für alle Zeilen einschließlich der letzten.

Zweiter Teil, Speichern des Pfades:

  1. Suche in der untersten Zeile den niedrigsten Energiewert. Das ist das letzte Element des Pfades.
  2. Suche in den zwei bis drei oberen Nachbarn den mit dem niedrigsten Energiewert. Der ist dann das vorletzte Element des Pfades.
  3. Wiederhole das mit allen Zeilen, von unten nach oben immer das Element mit dem niedrigsten Energiewert auswählen und da weitermachen.

3. Entfernen eines Pfades

  1. Erzeuge ein neues leeres Bild, um 1 Pixel schmäler als das vorhergehende.
  2. Gehe das Originalbild zeilenweise durch.
  3. Kopiere jeweils alle Pixel links des Pfades vom alten in das neue Bild.
  4. Verschiebe alle Pixel rechts des Pfades im alten Bild um 1 nach links im neuen Bild.

Das wird vielleicht etwas klarer bei der Java-Implementierung.

Java-Umsetzung

Attribute und einfache Methoden der Klasse SeamCarver:

import java.awt.image.BufferedImage;
import java.awt.Color;
 
public class SeamCarver {
  BufferedImage image;
  int [] energy;
  int [] seam;
  int width;
  int height;
 
  public SeamCarver(BufferedImage img){ setImage(img);}               
  public SeamCarver(){}               
  public void setImage(BufferedImage img) { 
    image = img; 
    width=image.getWidth();
    height=image.getHeight();
  }
  public BufferedImage getImage() { return image; }
}

Höhe und Breite des Bildes brauche ich so oft, dass ich sie als Attribute speichere. Die Energie könnte ich auch in einem zweidimensionalen Array speichern, aber erstens habe ich das Projekt mit Processing angefangen, wo die Bildpixel als eindimensionales Array bearbeitet werden und ein entsprechendes Energy-Feld nahe liegt; außerdem weiß ich nicht, ob sich meine Schüler und Schülerinnen mit zweidimensionalen Arrays zu schwer tun, und drittens sind die Arrays in Java ja gar nicht wirklich zweidimensional.

Die von außen hauptsächlich aufzurufende Methode ist die hier:

public void carveVertical(int number) {
  for (int i=0; i<number; i++) {
    setEnergy();
    findVerticalSeam();
    removeVerticalSeam();
  }
}

Dann kann man sich mit getImage() das neue Bild geben lassen. Die kniffligen Methoden sind die hier:

void setEnergy(); //ruft fuer alle Pixel die beiden calculateEnergy-Methoden auf und fuellt das energy-Array
void findVerticalSeam(); //fuellt das seam-Array von hinten nach vorn mit den x-Positionen der entsprechenden Pixel
void removeVerticalSeam(); //ersetzt das alte Bild durch ein neues, schmaeleres
int calculateEnergyStart(int x, int y); //berechnet den Energiewert anhand der Differenzen der vier Nachbarpixel 
int calculateEnergyChanged(int x, int y); //aendert den Energiewert anhand der zwei oder drei oberen Nachbarpixel

Dazu kommen noch folgende Hilfsmethoden:

void paintVerticalSeam(); //malt einen rosa Strich, wo der seam ist 
BufferedImage getEnergyImage(); //erzeugt ein neues Bild mit Grauwerten, der Energie an dieser Position entsprechend
int energyToColor(int energyValue); //Hilfsmethode, um Energiewert in einen Grauton umzuwandeln
void printSeam(); //zum Debuggen und Testen
void printEnergy(); //zum Debuggen und Testen

Sehr lustig finde ich dabei, wie ich mich anstelle, wenn es gilt, Funktionen herausfinden. Das Hinundherrechnen mit dem eindimensionalen Energie-Array und der zweidimensionales Ansprache des Bildes ist ein wenig umständlich.

Was man noch machen könnte

Methoden, um horizontale Pfade geringster Energie zu finden und zu entfernen. Methoden, um vertikale oder horizontale Pfade einzufügen, um das Bild dezent zu vergrößern.

Kann ich das mal mit Schülern und Schülerinnen machen? Ich schwanke immer: Wenn ich zu viel vorgebe, wird die Arbeit zu kleinschrittig und man interessiert sich nicht mehr für den Zusammenhang; aber vorgeben muss ich viel. Vielleicht arbeitsteilig die Methoden machen lassen? Dazu ordentliche Testklassen mitgeben.

3 Antworten auf „Der Seam-Carving-Algorithmus“

  1. Ah, mal wieder was zum programmieren, und dann auch noch zu Bildbearbeitung, sehr schön!

    Ich denke eines der größten Probleme (habe ehrlich gesagt den Code noch nicht richtig anschauen können, also erstmal rein algorithmisch gesprochen) sind regelmäßige diagonale Strukturen. Da treten größere Verzerrungen oder sogar Sprünge auf.
    Schön erkennbar am Pelikanschnabel z.B.

    Das andere sind große Formen. Je größer desto schlimmer.
    Also die Kuhherde zusammenzufassen verzerrt das Bild merklich stärker als die Schafherde.
    Tatsächlich muss ich sagen dass das Ergebnis für die Schafherde sogar extrem gut ist.

    Klar, der hohe Kontrast der Schafe zur Weide hilft natürlich auch sehr dabei, die Formen zu erkennen.
    Geringer Kontrast innerhalb der Form eines Körpers hat den Mann im letzten Bild sein Bein gekostet, und das Mädchen in der Mitte hat durch diesen Effekt ziemlich an Masse eingebüßt denke ich.

    Gerade beim letzten Bild ist das zentrale Motiv des Bildes leider dabei draufgegangen (Pelikan auf Bank). Da würde mich interessieren wie das um nur 30% geschrumpfte Bild aussieht. 50% ist schon recht viel.

    Es ist aber auch ein sehr schweres Bild. Da ist viel los, und der Algorithmus hat Probleme damit, die wichtigen Pixel und damit die Seams zu finden.
    Am besten funktioniert der Algorithmus mit Bildern, in denen sehr prägnante Objekte auf gleichförmigem Untergrund zu sehen sind:
    – Flugzeuge oder Drachen am Himmel
    – Schafe auf der Weide
    – Schiffe auf dem Wasser
    – Geldscheine auf einem weißen Bettuch
    – wild verteilte Buchstaben auf einem weißen Papier? Das könnte künstlerisch wertvoll sein…

    Gruß
    Aginor

  2. Mit 70% der Originalbreite ist der Pelikanschnabel besser, das Mädchen nur etwas schmäler, aber die Beinpaare rechts und vor allem links sind weiterhin nur zur Hälfte da:

    Ich habe ein bisschen versucht, die Energiefunktion nach Gefühl anzupassen, aber das hat nichts gebracht außer der Erkenntnis, dass es so einfach nicht geht.

    Hier die ursprüngliche Energiefunktion, vielleicht trägt die zur Erklärung bei:

    Diese diagonale Mauer geht eher:

    zu:

    Ein Zaunpfosten ist verschwunden, große Teile des Zauns. Das fällt wohl bei Menschen besonders auf.

Schreibe einen Kommentar

Deine E-Mail-Adresse wird nicht veröffentlicht. Erforderliche Felder sind mit * markiert.