A story about improving the program for partial filling of 3D binarized image data

The Fill program I made last time had a stack overflow

The program created in Previous article caused a stack overflow. The cause is quite clear, and since it is recalled, it will overwhelm the memory if it repeats more than a certain amount. I thought that there would be no problem if the data was used for research, but the data I was actually using overflowed, so I decided to change the algorithm.

environment

python 3.7.4

I haven't used the library in particular.

Solution method

The cause was that it was squeezing memory, so I decided to solve it by repeating it using for instead of recalling it. However, it takes too much time to look at all the cells each time and process them, so create a function that fills the 6 directions (up / down / left / right + Z-axis up / down) of your own cell, and save the coordinates of the cell to be searched. And only process that cell. I don't know even if I write it in sentences, so I will write the order of processing.

Status

First, a table shows what the cells are in.

Status symbol Contents of the state
0 One of the binarization
1 One of the binarization
2 Filled cell

processing

Then, it is the content of the actual processing. I will not repeat the first one (naturally)

  1. Determine the first point
  2. Put the coordinates of the specified point in the list (z, y, x)
  3. Extract the data from the list. (Delete the retrieved data from the list)
  4. Fill the corresponding cell (set to 2)
  5. Put the coordinates of the corresponding cell in 6 directions in the list (do not put it if it has already been searched or is not the target of filling)
  6. Repeat steps 3-5 until list is empty

It is like this. Last time, I searched one cell at a time, but this time I have an image of remembering the cells to be searched in advance and processing them all at once.

fill.gif

Implementation

Let's take a look at the code. The first is the main iterative function.

new_fill.py


def fill(data, plot):
    stack=[]
    end_stack=[]
    data, defaultvalue= plot_point(data, plot, stack) #Specify the first point

    while stack: #Repeat unless empty
        for pop_data in stack: #Extract data from the stack
            stack.remove(pop_data) #Delete the retrieved data
            data = step_fill(data, pop_data["x"], pop_data["y"], pop_data["z"], defaultvalue, stack) #Fill function
            end_stack.append(pop_data) #Save as searched data
    return data

It looks like this.

As I said above, save the data of the cell to be searched, and it will end when there are no more cells to search It is a simple program.

The program that specifies the first point is almost the same as the previous one. The difference is that the coordinate data is put on the stack, so the return value changes and it is put on the stack internally.

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

You just added stack.append (plot).

And it is a function that fills the surroundings, but this is the function that originally made the restart call. This time I simply fill myself and put the surrounding unsearched coordinates on the stack It is a function such as.

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

It's simple. I feel like I can write something more beautifully, so I'll think about it.

With the above three, you can implement 3D fill.

By the way, I compared the time of the previous original experiment.

Previous fill This fill
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
average 0.00588448047637 0.115191650390625

The processing time has increased by about 200 times. Maybe there is a mixture of useless processing, so I'll think about it again.

Recommended Posts

A story about improving the program for partial filling of 3D binarized image data
The story of writing a program
A program that searches for the same image
Image processing? The story of starting Python for
A story about changing the master name of BlueZ
The story of creating a VIP channel for in-house chatwork
A story about clustering time series data of foreign exchange
The story of making a standard driver for db with python.
[AtCoder for beginners] A story about the amount of calculation that you want to know very roughly
A story about trying to improve the testing process of a system written in C language for 20 years
A story about creating a program that will increase the number of Instagram followers from 0 to 700 in a week
Latin learning for the purpose of writing a Latin sentence analysis program (Part 1)
A story of a person who started aiming for data scientist from a beginner
The story of verifying the open data of COVID-19
The story of blackjack A processing (python)
[Introduction to Python] How to get the index of data with a for statement
The story of low learning costs for Python
A note about the python version of python virtualenv
The story of making a lie news generator
The story of reading HSPICE data in Python
The story of making a mel icon generator
[Small story] Download the image of Ghibli immediately
A story about data analysis by machine learning
The story of switching from WoSign to Let's Encrypt for a free SSL certificate
A program that summarizes the transaction history csv data of SBI SECURITIES stocks [Python3]
A story about trying to introduce Linter in the middle of a Python (Flask) project
Created a fooling image for the caption generative model
The story of launching a Minecraft server from Discord
[Python] A program that counts the number of valleys
A story about making 3D space recognition with Python
A memorandum about the warning of the pylint output result
Generate a vertical image of a novel from text data
The story of making a music generation neural network
About the inefficiency of data transfer in luigi on-memory
Story of image analysis of PDF file and data extraction
A story about struggling to loop 3 million ID data
Zip 4 Gbyte problem is a story of the past
A story that analyzed the delivery of Nico Nama.
A reminder about the implementation of recommendations in Python
[Python] A program that compares the positions of kangaroos.
The story of creating a "spirit and time chat room" exclusively for engineers in the company
A story about finding the longest shiritori of a given word group by ignoring computational complexity
About the contents of wscript when building a D language environment like that with Waf
A story about porting the code of "Try and understand how Linux works" to Rust