[PYTHON] Eine Geschichte über die Verbesserung des Programms zum teilweisen Füllen von binärisierten 3D-Bilddaten

Das Füllprogramm, das ich das letzte Mal erstellt habe, hatte einen Stapelüberlauf

Das in Vorheriger Artikel erstellte Programm hatte einen Stapelüberlauf. Die Ursache ist ziemlich klar, und da es zurückgerufen wird, wird es das Gedächtnis überwältigen, wenn es mehr als eine bestimmte Menge wiederholt. Ich dachte, dass es kein Problem geben würde, wenn die Daten für Forschungszwecke verwendet würden, aber die Daten, die ich tatsächlich verwendete, liefen über, also entschied ich mich, den Algorithmus zu ändern.

Umgebung

Ich habe die Bibliothek nicht besonders benutzt.

Lösungsmethode

Die Ursache war, dass es den Speicher drückte, also entschied ich mich, es zu lösen, indem ich es mit for anstelle eines Rückrufs wiederholte. Es dauert jedoch zu lange, alle Zellen jedes Mal zu betrachten und zu verarbeiten. Erstellen Sie daher eine Funktion, die die 6 Richtungen (oben / unten / links / rechts + Z-Achse oben / unten) Ihrer eigenen Zelle ausfüllt und die Koordinaten der zu durchsuchenden Zelle speichert. Und nur diese Zelle verarbeiten. Ich weiß nicht einmal, ob ich es in Sätzen schreibe, also schreibe ich die Reihenfolge der Verarbeitung.

Status

Zunächst zeigt eine Tabelle, in welchen Zellen sich die Zellen befinden.

wird bearbeitet

Dann ist es der Inhalt der eigentlichen Verarbeitung. Ich werde den ersten nicht wiederholen (natürlich)

1. Bestimmen Sie den ersten Punkt
2. Fügen Sie die Koordinaten der angegebenen Punkte in die Liste ein (z, y, x).
3. Daten aus der Liste extrahieren. (Löschen Sie die abgerufenen Daten aus der Liste)
4. Füllen Sie die entsprechende Zelle (auf 2 gesetzt)
5. Fügen Sie die Koordinaten der entsprechenden Zelle in 6 Richtungen in die Liste ein (setzen Sie sie nicht ein, wenn sie bereits durchsucht wurde oder nicht das Ziel des Füllens ist).
6. Wiederholen Sie die Schritte 3 bis 5, bis die Liste leer ist

Es ist so. Beim letzten Mal habe ich jeweils eine Zelle durchsucht, aber diesmal ist es so, als würde ich mich daran erinnern, welche Zellen im Voraus durchsucht werden sollen, und sie alle gleichzeitig verarbeiten.

Implementierung

Werfen wir einen Blick auf den Code. Die erste ist die iterative Hauptfunktion.

new_fill.py

def fill(data, plot):
    stack=[]
    end_stack=[]
    data, defaultvalue= plot_point(data, plot, stack) #Geben Sie den ersten Punkt an

    while stack: #Wiederholen, sofern nicht leer
        for pop_data in stack: #Daten aus dem Stapel extrahieren
            stack.remove(pop_data) #
            data = step_fill(data, pop_data["x"], pop_data["y"], pop_data["z"], defaultvalue, stack) #
            end_stack.append(pop_data) #
    return data

Das Programm, das den ersten Punkt angibt, ist fast das gleiche wie das vorherige. Der Unterschied besteht darin, dass die Koordinatendaten in den Stapel eingefügt werden, sodass sich der Rückgabewert ändert und intern in den Stapel eingefügt wird.

new_fill.py

def plot_point(data, plot, stack):
    defaultvalue = data[plot["z"]][plot["y"]][plot["x"]]
    data[plot["z"]][plot["y"]][plot["x"]]=2
    stack.append(plot)
    return data, defaultvalue

Sie haben gerade "stack.append (plot)" hinzugefügt.

Und obwohl es sich um eine Funktion handelt, die die Umgebung ausfüllt, ist dies die Funktion, die ursprünglich den Neustartaufruf ausgeführt hat. Dieses Mal fülle ich mich einfach selbst und lege die umgebenden nicht gesuchten Koordinaten in den Stapel Es ist eine Funktion wie.

new_fill.py

def step_fill(data, x, y, z, defaultvalue, stack):
    data[z][y][x]=2
        
    if (data[z][y][x-1]==defaultvalue) and (not {"x":x-1, "y":y, "z":z} in stack):
        stack.append({"x":x-1, "y":y, "z":z})

    if (data[z][y][x+1]==defaultvalue) and (not {"x":x+1, "y":y, "z":z} in stack):
        stack.append({"x":x+1, "y":y, "z":z})
        
    if (data[z][y-1][x]==defaultvalue) and (not {"x":x, "y":y-1, "z":z} in stack):
        stack.append({"x":x, "y":y-1, "z":z})

    if (data[z][y+1][x]==defaultvalue) and (not {"x":x, "y":y+1, "z":z} in stack):
        stack.append({"x":x, "y":y+1, "z":z})

    if (data[z-1][y][x]==defaultvalue) and (not {"x":x, "y":y, "z":z-1} in stack):
        stack.append({"x":x, "y":y, "z":z-1})

    if (data[z+1][y][x]==defaultvalue) and (not {"x":x, "y":y, "z":z+1} in stack):
        stack.append({"x":x, "y":y, "z":z+1})
    return data

Es ist einfach. Ich habe das Gefühl, dass ich etwas Schöneres schreiben kann, also werde ich darüber nachdenken.

Mit den oben genannten drei können Sie 3D-Füllung implementieren.

Übrigens habe ich die Zeit des vorherigen ursprünglichen Experiments verglichen.

Die Bearbeitungszeit hat sich um das 200-fache erhöht. Vielleicht gibt es eine Mischung aus nutzloser Verarbeitung, also werde ich noch einmal darüber nachdenken.