Rasterpfad nach Algorithmen
Ich habe ein Raster-Raster mit Werten, die ungefähr so aussehen wie das Bild unten (Weiß ist hoch, der schwarze Hintergrund ist Null).
Ich versuche, eine Art Pfadfolgecode zu schreiben, um am Ende einer der Zeilen zu beginnen und zum anderen Ende zu gehen, wobei ich über die höchstmöglichen Werte gehe (das heißt, je weißer die ausgewählten Pixel sind) in der Linie, desto besser), aber immer noch zum anderen Ende.
Ich habe seit einiger Zeit damit zu kämpfen und kann anscheinend nichts bekommen, was ich versuche zu arbeiten. Also habe ich mich gefragt, ob ein generischer Algorithmus für diese Art von Problem bereits entwickelt wurde? Ich habe viel gesucht, aber die meisten Pfadalgorithmen scheinen so entworfen zu sein, dass sie an Vektoren / Netzwerken arbeiten, nicht an solchen Rasterrastern.
Irgendwelche Ideen?
4 Antworten
Die einfachste Idee ist wahrscheinlich, den A * -Algorithmus zu verwenden, wobei jedes Pixel ein Knoten ist und der Kosten des Knotens ist die Pixel Dunkelheit.
Update: Ein nettes Tutorial gefunden.
Eine Möglichkeit, dies zu tun:
- Filtern Sie das Bild, um es näher an nur schwarze und weiße Pixel zu bringen.
- Zeichnen Sie eine Linie durch die weißen Pixel. Beginnen Sie dazu mit einem weißen Pixel. Zeichnen Sie eine Linie von diesem Pixel zu einem anderen weißen Pixel in einer Entfernung von 2 (oder 3 oder so), aber ignorieren Sie Pixel in der Nähe einer vorherigen Linie. Machen Sie weiter so lange, bis Sie alle Pixel, die nicht in der Nähe sind (2 oder 3 Pixel), von einer Linie abgedeckt haben. Sie müssen hier einige kleine Anpassungen vornehmen, damit es gut funktioniert.
- Verbinde die Endpunkte der Linien, die du gezeichnet hast. Wenn sich zwei Endpunkte in der Nähe von (1 oder 2 Pixel?) Befinden, verbinden Sie sie. Sie sollten mit ein paar Zeilen enden, die aus vielen kurzen Segmenten bestehen, möglicherweise mit einigen Schleifen und Gabeln.
- Entfernen Sie alle kleinen Schleifen in den Linien und trennen Sie die Linien bei den Gabeln, damit Sie einige Linien aus vielen kurzen Segmenten haben.
- Punkte reduzieren. Überprüfen Sie für jede Linie, ob sie fast gerade ist. Wenn ja, entfernen Sie alle inneren Punkte. Wenn nicht, überprüfen Sie die zwei Hälften der Zeile rekursiv, bis Sie zu den minimalen Segmentlängen kommen.
- Sie können optional eine Spline-Kurve durch die Linien an dieser Stelle einfügen.
- Gewinn.
Es wird einige Feinabstimmungen brauchen, damit es gut funktioniert, aber es ist möglich, es auf diese Weise zu machen. Eine andere Variante besteht darin, die weißen Abschnitte zu umreißen, wenn sie breiter als 1 oder 2 oder 3 Pixel sind, und danach die doppelten Linien zu kombinieren.
Ich glaube nicht, dass Sie einen genetischen Algorithmus oder etwas lächerliches brauchen werden; gute alte Mode Rekursion und dynamische Programmierung sollten ausreichen. Ich denke zuerst, dass Sie in der Lage sein sollten, Ihr Ziel zu erreichen, indem Sie eine breite erste Suche durchführen. Von Ihrem Ausgangspunkt aus besuchen Sie alle Nachbarn mit Werten, die größer sind als der Pfadwert - alle Zellen beginnen im Unendlichen, und die Kosten für schwarze Zellen sind unendlich, und dies sind die Pfade, die Sie abschneiden können. Sobald Sie an Ihrem Ziel angekommen sind, sollten Sie in der Lage sein, den Pfad zurückzuverfolgen. Es ist gierig, aber wenn deine Wege sich so gut benehmen wie diese, sollte es in Ordnung sein.
Bei Pfaden mit mehr Grautönen und Drehungen kann es sinnvoll sein, das Rasterbild in ein Diagramm zu konvertieren, wobei das Kantengewicht die Grauwerte der Nachbarn (oder die Differenz der Grauwerte) ist was diese Daten eigentlich bedeuten). Daher sollten Sie in der Lage sein, einen beliebigen Algorithmus für kürzeste Pfade basierend auf dieser Interpretation zu verwenden.