kleemans.ch

Seam Carving beschreibt eine Technik, mit der Bilder mit Rücksicht auf ihren Inhalt zurechtgestutzt werden.

Vorher:

Nachher:

Nicht aus Faulheit, sondern weil es schon ausgezeichnete Beschreibungen gibt, hier eine solche (von schieb.de):

Bei dieser Methode wird ein Bild in Breite oder Höhe verkleinert, allerdings ohne an den Rändern etwas abzuschneiden. Stattdessen werden im Bildinneren Informationen entfernt, aber derart behutsam, dass es kaum auffällt. Die meisten Bilder wirken nach der Verkleinerung genauso wie vorher, obwohl sich das Seitenverhältnis teilweise erheblich verändert.

Dahinter steckt ein komplexer Algorithmus. Die Software analysiert das Foto in drei Schritten. Zuerst werden Kanten im Bild ermittelt, zum Beispiel die Umrisse von Gegenständen oder Personen. Solche Objekte im Bild bleiben unangetastet, da sie in der Regel den Kern des Bildes ausmachen. Im zweiten Schritt wird ein “Energiebild” angefertigt: Pixel in der Höhe von Kanten erhalten einen höheren Wert als solche, die weiter entfernt sind. In der Folge lassen sich Farbflächen ermitteln, die sich problemlos schrumpfen lassen. Im dritten Schritt ermittelt die Software die so genannten “Seams”, der die Technik ihren Namen verdankt: Das sind Pixelpfade durch die Bilder hindurch, die für das eigentliche Bild weniger wichtig sind. Diese Seams lassen sich aus einem Bild entfernen, ohne dass es besonders auffällt.

Ablauf

Kurz gesagt können folgende Schritte durchgeführt werden:

1. Analysiere Bild hin auf “Energie” der einzelnen Pixel.
2. Finde die Naht, welche am wenigsten “kostet” = die kleinste Energie hat.
3. Entferne diese Naht.

Dynamische Programmierung

Der ganze Ablauf basiert auf dynamischer Programmierung. Durch zerlegen in Teilprobleme und das zwischenspeichern der Resultate kann so effizient berechnet werden, wo die optimale Naht ist.

Eine ausgezeichnete Einleitung findet sich auch auf Wikipedia. Beispiel zur Festlegung der Energie der Pixel in einer Tabelle M (Funktion engergy() ist vorhanden):

public static float[][] computeCosts(BufferedImage img) {
  int width, height;
  width = img.getWidth();
  height = img.getHeight();

  float[][] M = new float[height][width];

  for (int y=0; y<height; y++) {
    for (int x=0; x<width; x++) {
      if (y==0) {
        M[y][x] = energy(img, x, y);
        break;
      }
      //right two upper pixels
      else if (x==0) {
        M[y][x] = energy(img, x, y) + Math.min(M[y-1][x], M[y-1][x+1]);
      }
      //left two upper pixels
      else if (x==width-1) {
        M[y][x] = energy(img, x, y) + Math.min(M[y-1][x-1], M[y-1][x]);
      }
      //three pixels
      else
        M[y][x] = energy(img, x, y) + Math.min(M[y-1][x-1], Math.min(M[y-1][x], M[y-1][x+1]));
    }
  }
  return M;
}

Beispiel zur Berechnung der optimalen Naht:

public static int[] computeSeam(float[][] costs, int width, int height) {
  int[] seam = new int[height];

  //find best lowest pixel
  int yLow = height-1;
  float bestScore = 1000000000.0f;
  for (int x=0; x<width; x++) {
    if (costs[yLow][x] < bestScore) {
      seam[yLow] = x;
      bestScore = costs[yLow][x];
    }
  }

  //calculate rest of seam
  int x = seam[yLow];
  for (int y=height-2; y>=0; y--) {

    //left pixel
    if (x==0 && costs[y][x] <= costs[y][x+1])
      seam[y] = x;
    else if (x==0 && costs[y][x] >= costs[y][x+1])
      seam[y] = x+1;

    //right pixel
    else if (x==width-1 && costs[y][x-1] <= costs[y][x])
      seam[y] = x-1;
    else if (x==width-1 && costs[y][x-1] >= costs[y][x])
      seam[y] = x;

    //middle pixel
    else if (costs[y][x-1] <= costs[y][x] && costs[y][x-1] <= costs[y][x+1])
      seam[y] = x-1;
    else if (costs[y][x] <= costs[y][x-1] && costs[y][x] <= costs[y][x+1])
      seam[y] = x;
    else if (costs[y][x+1] <= costs[y][x] && costs[y][x+1] <= costs[y][x-1])
      seam[y] = x+1;

    //new x
    x = seam[y];
  }

return seam;
}

Aus einem beliebigen Bild kann der “wichtige” Inhalt extrahiert werden. Dies kann dann zu folgenden Ergebnissen führen (bei allen rechten Bildern wurden genau 100 Nähte entfernt):

Der Source code für die Beispiele findet sich in diesem Github Repo.

Man kann die Technik auch direkt online hier selbst ausprobieren.