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

python 3.7.4

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.

Symbole d'état Contenu de l'état
0 Une de la binarisation
1 Une de la binarisation
2 Cellule remplie

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.

fill.gif

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.

Remplissage précédent Ce remplissage
1 0.004987001419067383 0.12566423416137695
2 0.003987789154052734 0.10970711708068848
3 0.003989219665527344 0.11269998550415039
4 0.004986763000488281 0.11568784713745117
5 0.00598454475402832 0.11369585990905762
6 0.015959978103637695 0.11469197273254395
7 0.004986763000488281 0.11768507957458496
8 0.003989934921264648 0.11369562149047852
9 0.003988981246948242 0.1136932373046875
10 0.005983829498291016 0.11469554901123047
moyenne 0.00588448047637 0.115191650390625

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.

Recommended Posts

Une histoire sur l'amélioration du programme pour le remplissage partiel des données d'image binarisées 3D
L'histoire de l'exportation d'un programme
Programme pour rechercher la même image
Traitement d'image? L'histoire du démarrage de Python pour
Une histoire sur le changement du nom principal de BlueZ
L'histoire de la création d'un canal VIP dans le chatwork en interne
Une histoire de regroupement de données de séries chronologiques d'échange
L'histoire de la création d'un pilote standard pour db avec python.
[Pour les débutants chez AtCoder] Parlez de la quantité de calcul que vous voulez connaître approximativement
Une histoire d'essayer d'améliorer le processus de test d'un système vieux de 20 ans écrit en C
Une histoire sur la création d'un programme qui augmentera le nombre d'abonnés Instagram de 0 à 700 en une semaine
Apprendre le latin dans le but d'écrire un programme d'analyse de phrases latines (partie 1)
L'histoire d'une personne qui a commencé à viser un data scientist depuis un débutant
L'histoire du traitement A du blackjack (python)
[Introduction à Python] Comment obtenir l'index des données avec l'instruction for
L'histoire selon laquelle le coût d'apprentissage de Python est faible
Écrire une note sur la version python de python virtualenv
L'histoire de la lecture des données HSPICE en Python
L'histoire de la création d'un générateur d'icônes mel
[Petite histoire] Téléchargez l'image de Ghibli immédiatement
Histoire de l'analyse de données par apprentissage automatique
L'histoire du passage de WoSign à Let's Encrypt pour un certificat SSL gratuit
Programme qui résume les données csv de l’historique des transactions de l’action SBI Securities [Python3]
Une histoire sur la tentative d'introduire Linter au milieu d'un projet Python (Flask)
Création d'une image trompeuse pour le modèle de génération de légende
L'histoire du lancement d'un serveur Minecraft depuis Discord
[Python] Un programme qui compte le nombre de vallées
Un mémorandum sur les avertissements dans les résultats de sortie de pylint
Générer une image verticale d'un roman à partir de données textuelles
L'histoire de la création d'un réseau neuronal de génération musicale
À propos de l'inefficacité du transfert de données dans luigi on-memory
Histoire de l'analyse d'image du fichier PDF et de l'extraction de données
Une histoire sur la difficulté à traiter en boucle 3 millions de données d'identification
Le problème Zip 4 Gbyte est une histoire du passé
Une histoire qui a analysé la livraison de Nico Nama.
Un mémorandum sur la mise en œuvre des recommandations en Python
[Python] Un programme qui compare les positions des kangourous.
L'histoire de la création d'un «espace de discussion sur l'esprit et le temps» exclusivement pour les ingénieurs de l'entreprise
Une histoire sur la recherche de la compression la plus longue d'un groupe de mots donné en ignorant le pistolet de calcul du montant
À propos du contenu de wscript lors de la création d'un environnement en langage D comme celui avec Waf
Une histoire sur le portage du code de "Essayez de comprendre comment fonctionne Linux" sur Rust