Seam Carving ein Bild mit Dijkstra-Algorithmus in C++

Question

Ich versuche Seam Carving mit Dijkstra-Algorithmus zu implementieren.

Bisher habe ich das Bild in Graustufen konvertiert und mit einem 2D-Array habe ich die Energiefunktion des Bildes herausgefunden. Um nun Dijkstra zu implementieren, muss ich dieses 2D-Array in ein Diagramm umwandeln und der Dijsktra-Funktion eine Quelle und eine Senke geben.

Ich würde gerne wissen, wie zu ändern Sie diese 2D-Array in ein Diagramm, als das 2D-Array, eine Matrix von MxN, wo M, N beide sehr große Zahlen sein können, könnte möglicherweise eine große entstehen Anzahl der Grafiken möglich, und entscheiden Sie die Senke für sie.

Answer 1

Sie müssen das Bild nicht in ein Diagramm konvertieren. Alles, was Sie tun müssen, ist die dynamische Programmierung, um Nähte zu berechnen und dann die Naht mit minimaler Energie zu finden. Um genauer zu sein, berechnen S [i, j] (Naht für das Pixel (i, j)):

1. Für die erste Reihe, weist den Energiewert als Nahtwert des Pixel S [1, j ] = E [1, j]

2. Für die nächsten Zeilen, propagieren Sie die minimale Naht von den Nachbarn des Pixels nach unten: S [i, j] = E [i, j] + min (S [i-1 , j-1], S [i-1, j], S [i-1, j + 1])

3. Beginnen Sie mit dem Element mit Mindestwert in der letzten Reihe von S und steigen Sie durch Auswahl von Nachbarn auf mit minimalen Nahtwerten. Speichern Sie jeden Schritt.

4. Der von Ihnen gespeicherte Weg ist die Naht mit minimaler Energie.

ich auch einen schönen Artikel mit erklärt gründlich den Algorithmus mit MATLAB-Quellcode finden haben:

https://kirilllykov.github.io/blog/2013/06/06/seam-carving-algorithm/