[PYTHON] Une histoire sur l'amélioration du programme pour le remplissage partiel des données d'image binarisées 3D

Le programme Fill que j'ai créé la dernière fois a eu un débordement de pile

Le programme créé dans Article précédent avait un débordement de pile. La cause est assez claire, et puisqu'elle est rappelée, elle submergera la mémoire si elle se répète plus d'un certain montant. Je pensais qu'il n'y aurait pas de problème si les données étaient utilisées pour la recherche, mais les données que j'utilisais réellement débordaient, alors j'ai décidé de changer d'algorithme.

environnement

Je n'ai pas utilisé la bibliothèque en particulier.

Méthode de solution

La cause était que cela réduisait la mémoire, j'ai donc décidé de le résoudre en le répétant en utilisant for au lieu d'un appel de rappel. Cependant, il faut trop de temps pour regarder toutes les cellules à chaque fois et les traiter, alors créez une fonction qui remplit les 6 directions (haut / bas / gauche / droite + axe Z haut / bas) de votre propre cellule et enregistrez les coordonnées de la cellule à rechercher. Et ne traitez que cette cellule. Je ne sais même pas si je l'écris en phrases, donc j'écrirai l'ordre de traitement.

Statut

Tout d'abord, un tableau montre dans quoi se trouvent les cellules.

En traitement

Ensuite, c'est le contenu du traitement proprement dit. Je ne répéterai pas le premier (naturellement)

1. Déterminez le premier point
2. Mettez les coordonnées des points spécifiés dans la liste (z, y, x)
3. Extraire les données de la liste. (Supprimer les données récupérées de la liste)
4. Remplissez la cellule correspondante (définie sur 2)
5. Mettez les coordonnées de la cellule correspondante dans 6 directions dans la liste (ne la mettez pas si elle a déjà été recherchée ou n'est pas la cible de remplissage)
6. Répétez les étapes 3 à 5 jusqu'à ce que la liste soit vide

C'est comme ça. La dernière fois, j'ai cherché une cellule à la fois, mais cette fois, c'est comme me souvenir des cellules à rechercher à l'avance et les traiter toutes en même temps.

la mise en oeuvre

Jetons un coup d'œil au code. La première est la fonction itérative principale.

new_fill.py

def fill(data, plot):
    stack=[]
    end_stack=[]
    data, defaultvalue= plot_point(data, plot, stack) #Spécifiez le premier point

    while stack: #Répéter sauf si vide
        for pop_data in stack: #Extraire les données de la pile
            stack.remove(pop_data) #Supprimer les données récupérées
            data = step_fill(data, pop_data["x"], pop_data["y"], pop_data["z"], defaultvalue, stack) #Fonction de remplissage
            end_stack.append(pop_data) #Enregistrer en tant que données recherchées
    return data

Ça ressemble à ça.

Comme je l'ai dit ci-dessus, enregistrez les données de la cellule à rechercher, et cela se terminera lorsqu'il n'y aura plus de cellules à rechercher C'est un programme simple.

Le programme qui spécifie le premier point est presque le même que le précédent. La différence est que les données de coordonnées sont placées dans la pile, donc la valeur de retour change et elle est placée dans la pile en interne.

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

Vous venez d'ajouter stack.append (plot).

Et c'est une fonction qui remplit l'environnement, mais c'est la fonction qui a initialement lancé l'appel de redémarrage. Cette fois, je me remplis simplement et je mets les coordonnées non recherchées environnantes dans la pile C'est une fonction telle que.

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

C'est simple. Je sens que je peux écrire quelque chose de plus beau, alors je vais y réfléchir.

Avec les trois ci-dessus, vous pouvez implémenter un remplissage 3D.

Au fait, j'ai comparé le temps de l'expérience originale précédente.

Le temps de traitement a été multiplié par environ 200. Peut-être y a-t-il un mélange de traitements inutiles, alors j'y repenserai.