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

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.

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.

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.

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