{"id":13264,"date":"2019-08-08T19:22:45","date_gmt":"2019-08-08T17:22:45","guid":{"rendered":"https:\/\/www.herr-rau.de\/wordpress\/?p=13264"},"modified":"2023-05-04T18:40:20","modified_gmt":"2023-05-04T16:40:20","slug":"der-seam-carving-algorithmus","status":"publish","type":"post","link":"https:\/\/www.herr-rau.de\/wordpress\/2019\/08\/der-seam-carving-algorithmus.htm","title":{"rendered":"Der Seam-Carving-Algorithmus"},"content":{"rendered":"
(4 Kommentare.<\/a>)<\/small> <\/div>\n

Via Twitter auf diese Anregung<\/a> gesto\u00dfen, von dort zu dieser ausf\u00fchrlichen und sehr hilfreichen Princeton-Programmieraufgabe<\/a> geleitet worden, und am Ende einfach Wikipedia dazu<\/a> gelesen, wo man das sch\u00f6n interaktiv ausprobieren kann. Nat\u00fcrlich 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.<\/p>\n\n\n\n

Es geht um einen gar nicht mal so alten Algorithmus zur Bildbearbeitung. Nehmen wir mal dieses Bild, das wir bearbeiten wollen:<\/p>\n\n\n\n

\"\"<\/figure>\n\n\n\n

Da sieht man sechs Tiere, das Bild ist 700 Pixel breit, und wenn man nur 350 Pixel Platz hat f\u00fcr 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\u00f6chte man vielleicht, dass die Tiere einfach n\u00e4her bei einander w\u00e4ren, mit weniger Gr\u00fcn dazwischen, davon gibt es eh genug.<\/p>\n\n\n\n

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\u00fcr jeden Pixel bestimmt, wie wichtig er ist. (Zu den Details sp\u00e4ter.) Die Wichtigkeit der Pixel sieht man hier:<\/p>\n\n\n\n

\"\"<\/figure>\n\n\n\n

Wenn man in jeder Zeile den unwichtigsten Pixel entfernt, und das alles 350 mal wiederholt, kommt leider nicht ganz das heraus, was man m\u00f6chte:<\/p>\n\n\n\n

\"\"<\/figure>\n\n\n\n

Man sieht, dass die Bildpixel, die zu den wichtigen Elementen geh\u00f6ren (den Tieren), noch alle vorhanden sind und demnach aus jeder Zeile viele – n\u00e4mlich 350 – zumeist gr\u00fcne, also tats\u00e4chlich eher unwichtige Pixel verschwunden sind. Aber das Bild ist verzerrt – aus der ersten Zeile sind vielleicht Pixel aus der linken H\u00e4lfte verschwunden, danach welche aus der rechten, dann immer wieder abwechselnd. Hier sind die unwichtigsten Pixel des ersten Durchgangs rosa markiert:<\/p>\n\n\n\n

\"\"<\/figure>\n\n\n\n

Man sieht, eher sprunghaft. (Dass sie im mittleren Bereich halbwegs zusammenh\u00e4ngen, ist Zufall und passt f\u00fcr mein Beispiel gar nicht so.)<\/p>\n\n\n\n

Abhilfe schafft das seam carving. Seam <\/em>hei\u00dft 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\u00f6glichen derartigen Wege hat. (Wie man das macht: sp\u00e4ter.) Dann kriegt man beim ersten Durchgang diese Ader ganz rechts im Bild:<\/p>\n\n\n\n

\"\"<\/figure>\n\n\n\n

Wenn man alles rechts der rosa Linie einen Pixel nach links verschiebt, f\u00e4llt das sehr viel weniger auf, als wenn man das bei den versprengten rosa Punkten oben machen w\u00fcrde. Wiederholt man das 350 mal, kommt folgendes Bild heraus:<\/p>\n\n\n\n

\"\"<\/figure>\n\n\n\n

Die Proportionen der Tiere sind gr\u00f6\u00dftenteils 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\u00e4llt.<\/p>\n\n\n\n

\u00c4hnlich l\u00e4sst sich diese Schafherde zusammentreiben:<\/p>\n\n\n\n

\"\"<\/figure>\n\n\n\n

Halb so breit:<\/p>\n\n\n\n

\"\"<\/figure>\n\n\n\n

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\u00e4che ist – Himmel, Wasser, Wiese. Oft ist der Algorithmus weniger erfolgreich. Hier ein Original:<\/p>\n\n\n\n

\"\"<\/figure>\n\n\n\n

Und die wieder um 50% verschm\u00e4lerte Fassung, was zugegeben schon auch recht viel ist. Die Proportionen sind weitgehend okay, aber es fehlen schlicht Stellen:<\/p>\n\n\n\n

\"\"<\/figure>\n\n\n\n

Nat\u00fcrlich gibt es noch M\u00f6glichkeiten, den Algorithmus schneller oder besser zu machen, aber mir reicht das erst einmal. <\/p>\n\n\n\n

Technische Details<\/h2>\n\n\n\n

Drei Probleme habe ich oben allenfalls angedeutet: 1. Wie findet man heraus, welcher Pixel wichtig<\/em> ist und welcher nicht? 2. Wie findet man so einen seam,<\/em> 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.<\/p>\n\n\n\n

1. Energie\/Wichtigkeit eines Pixels<\/h4>\n\n\n\n

Gespeichert habe ich die Energien in einem eindimensionalen int-Array der L\u00e4nge Bildgr\u00f6\u00dfe*Bildbreite. <\/em> Wahrscheinlich gibt es mehrere M\u00f6glichkeiten, die Energie eines Pixels (hei\u00dft in der Anleitung, die ich verwendet habe, so, energy)<\/em> zu berechnen. Die oben verlinkte Anleitung macht das so: <\/p>\n\n\n\n

    \n
  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<\/code> so:
    int r1 = new Color(image.getRGB(x,y)).getRed();<\/code>
    int g1 = new Color(image.getRGB(x,y)).getGreen();<\/code>
    int b1 = new Color(image.getRGB(x,y)).getBlue();<\/code>
    Nat\u00fcrlich ist es umst\u00e4ndlich, aus dem mit getRGB erhaltenen int-Wert erst wieder eine Farbe machen zu m\u00fcssen, 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.<\/li>\n\n\n\n
  2. Quadriere diesen Rot-Unterschied.<\/li>\n\n\n\n
  3. Mache das gleiche f\u00fcr die Unterschiede bei den Gr\u00fcn- und Blau-Anteilen.<\/li>\n\n\n\n
  4. Wiederhole das alles f\u00fcr die Unterschiede zwischen den Pixeln \u00fcber und unter dem Pixel, dessen Energie bestimmt werden soll.<\/li>\n\n\n\n
  5. Addiere diese sechs Quadrate. Das ist die Energie!<\/li>\n\n\n\n
  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.<\/li>\n<\/ol>\n\n\n\n

    2. Finden eines minimalen Pfades<\/h4>\n\n\n\n

    Auch daf\u00fcr gibt es viele verschiedene M\u00f6glichkeiten, die aber nat\u00fcrlich alle zum selben Ergebnis f\u00fchren. Ich habe das, der Anleitung folgend, so gemacht. Gespeichert wird der (vertikale) Pfad in einem eindimensionalen int-Array der L\u00e4nge Bildh\u00f6he<\/em>.<\/p>\n\n\n\n

    Erster Teil, Anpassung der Energiewerte: <\/p>\n\n\n\n

      \n
    1. \u00c4ndere nichts an den Energiewerten der Pixel in der ersten Zeile.<\/li>\n\n\n\n
    2. Betrachte f\u00fcr jeden Pixel der Zeile darunter die zwei bis drei oberen <\/em>Nachbarn (Randpixel haben hier nur zwei <\/em>obere Nachbarn). Addiere den kleinsten der zwei oder drei Energiewerte zum eigenen Energiewert.<\/li>\n\n\n\n
    3. Wiederhole das f\u00fcr alle Zeilen einschlie\u00dflich der letzten. <\/li>\n<\/ol>\n\n\n\n

      Zweiter Teil, Speichern des Pfades:<\/p>\n\n\n\n

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

        3. Entfernen eines Pfades<\/h4>\n\n\n\n
          \n
        1. Erzeuge ein neues leeres Bild, um 1 Pixel schm\u00e4ler als das vorhergehende.<\/li>\n\n\n\n
        2. Gehe das Originalbild zeilenweise durch.<\/li>\n\n\n\n
        3. Kopiere jeweils alle Pixel links des Pfades vom alten in das neue Bild.<\/li>\n\n\n\n
        4. Verschiebe alle Pixel rechts des Pfades im alten Bild um 1 nach links im neuen Bild.<\/li>\n<\/ol>\n\n\n\n

          Das wird vielleicht etwas klarer bei der Java-Implementierung.<\/p>\n\n\n\n

          Java-Umsetzung<\/h2>\n\n\n\n

          Attribute und einfache Methoden der Klasse SeamCarver<\/code>:<\/p>\n\n\n\n

          import java.awt.image.BufferedImage;\nimport java.awt.Color;\n\npublic class SeamCarver {\n  BufferedImage image;\n  int [] energy;\n  int [] seam;\n  int width;\n  int height;\n\n  public SeamCarver(BufferedImage img){ setImage(img);}               \n  public SeamCarver(){}               \n  public void setImage(BufferedImage img) { \n    image = img; \n    width=image.getWidth();\n    height=image.getHeight();\n  }\n  public BufferedImage getImage() { return image; }\n}<\/code><\/pre>\n\n\n\n
          H\u00f6he und Breite des Bildes brauche ich so oft, dass ich sie als Attribute speichere. Die Energie k\u00f6nnte ich auch in einem zweidimensionalen Array speichern, aber erstens habe ich das Projekt mit Processing <\/em>angefangen, wo die Bildpixel als eindimensionales Array bearbeitet werden und ein entsprechendes Energy-Feld nahe liegt; au\u00dferdem wei\u00df ich nicht, ob sich meine Sch\u00fcler und Sch\u00fclerinnen mit zweidimensionalen Arrays zu schwer tun, und drittens sind die Arrays in Java ja gar nicht wirklich zweidimensional.<\/p>\n\n\n\n
          Die von au\u00dfen haupts\u00e4chlich aufzurufende Methode ist die hier:<\/p>\n\n\n\n
          public void carveVertical(int number) {\n  for (int i=0; i < number; i++) {\n    setEnergy();\n    findVerticalSeam();\n    removeVerticalSeam();\n  }\n}<\/code><\/pre>\n\n\n\n
          Dann kann man sich mit getImage()<\/code> das neue Bild geben lassen. Die kniffligen Methoden sind die hier:<\/p>\n\n\n\n
          void setEnergy(); \/\/ruft fuer alle Pixel die beiden calculateEnergy-Methoden auf und fuellt das energy-Array\n\nvoid findVerticalSeam(); \/\/fuellt das seam-Array von hinten nach vorn mit den x-Positionen der entsprechenden Pixel\n\nvoid removeVerticalSeam(); \/\/ersetzt das alte Bild durch ein neues, schmaeleres\n\nint calculateEnergyStart(int x, int y); \/\/berechnet den Energiewert anhand der Differenzen der vier Nachbarpixel \n\nint calculateEnergyChanged(int x, int y); \/\/aendert den Energiewert anhand der zwei oder drei oberen Nachbarpixel<\/code><\/pre>\n\n\n\n
          Dazu kommen noch folgende Hilfsmethoden:<\/p>\n\n\n\n
          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<\/code><\/pre>\n\n\n\n
          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\u00e4ndlich.<\/p>\n\n\n\n
          Was man noch machen k\u00f6nnte<\/h2>\n\n\n\n
          Methoden, um horizontale Pfade geringster Energie zu finden und zu entfernen. Methoden, um vertikale oder horizontale Pfade einzuf\u00fcgen,<\/em> um das Bild dezent zu vergr\u00f6\u00dfern.<\/p>\n\n\n\n
          Kann ich das mal mit Sch\u00fclern und Sch\u00fclerinnen machen? Ich schwanke immer: Wenn ich zu viel vorgebe, wird die Arbeit zu kleinschrittig und man interessiert sich nicht mehr f\u00fcr den Zusammenhang; aber vorgeben muss ich viel. Vielleicht arbeitsteilig die Methoden machen lassen? Dazu ordentliche Testklassen mitgeben.<\/p>\n","protected":false},"excerpt":{"rendered":"
          (4 Kommentare.) Via Twitter auf diese Anregung gesto\u00dfen, von dort zu dieser ausf\u00fchrlichen und sehr hilfreichen Princeton-Programmieraufgabe geleitet worden, und am Ende einfach Wikipedia dazu gelesen, wo man das sch\u00f6n interaktiv ausprobieren kann. Nat\u00fcrlich zum Lernen gleich nachprogrammiert und Blogpost daraus gemacht, damit es sich lohnt und ich es wirklich verstehe. Aber man kann statt […]<\/p>\n","protected":false},"author":2,"featured_media":13278,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_jetpack_memberships_contains_paid_content":false,"footnotes":""},"categories":[25],"tags":[227],"class_list":["post-13264","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-informatik","tag-informatik"],"jetpack_featured_media_url":"https:\/\/www.herr-rau.de\/wordpress\/archiv\/seam_carving_1_carved.jpg","jetpack_sharing_enabled":true,"jetpack_likes_enabled":true,"_links":{"self":[{"href":"https:\/\/www.herr-rau.de\/wordpress\/wp-json\/wp\/v2\/posts\/13264","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.herr-rau.de\/wordpress\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.herr-rau.de\/wordpress\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.herr-rau.de\/wordpress\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/www.herr-rau.de\/wordpress\/wp-json\/wp\/v2\/comments?post=13264"}],"version-history":[{"count":3,"href":"https:\/\/www.herr-rau.de\/wordpress\/wp-json\/wp\/v2\/posts\/13264\/revisions"}],"predecessor-version":[{"id":55675,"href":"https:\/\/www.herr-rau.de\/wordpress\/wp-json\/wp\/v2\/posts\/13264\/revisions\/55675"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.herr-rau.de\/wordpress\/wp-json\/wp\/v2\/media\/13278"}],"wp:attachment":[{"href":"https:\/\/www.herr-rau.de\/wordpress\/wp-json\/wp\/v2\/media?parent=13264"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.herr-rau.de\/wordpress\/wp-json\/wp\/v2\/categories?post=13264"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.herr-rau.de\/wordpress\/wp-json\/wp\/v2\/tags?post=13264"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}