# The fastest way to "fill holes" in 3D?

I have a 3D binary image that I must fill all of the holes in the image.

"Fill holes 3D" in this case, is basically a 3D version of

BW2 = imfill(BW,'holes') from MatLab,

but I am not focusing on Matlab here. I am focusing on the algorithm in general.

Currently, I simply perform a "flood fill 3D" algorithm on all voxels at the border area of the 3D matrix. Anything not filled are holes so take this as a mask and remove all voxels on the real image with this mask.

Sure, the algorithm works, but somehow, I feel this is inefficient.

What is the fastest way to "fill holes" in 3D in this case?

I don't have the privilege to comment, so I'm going write my comment as an answer.

I'm guessing your function, as well as imfill in Matlab, performs the "filling" iteratively.

Two basic improvements to speed these kind of iterative functions up would be to 1. increase the seed points, i.e. using other possible locations in addition to the border area, maybe base on image intensity before the binerization process, or whatever characteristics the images have, and 2. try to parallelize your function (see Dirk-Jan Kroon's Region Growing function for an example). If this doesn't speed things up, or you just have too many seed points, then I would suggest you start implementing a function that uses your GPU for parallel processing.

Now there may be "non-iterative" functions that fill 3d holes... so I'll leave that to the experts here on dsp.se. It would also be nice if you can show us a slice of your 3D image for a better understanding of what you are dealing with.

You seem to be saying that it's essentially a voxel space. "binary 3d image" is confusing.

You have to logically trace every voxel along like a stream, to determing what is connected and what is not within internal voids, so flood fill is essential. you can trace the outside edge of the volume but it only returns the periphery pixels.

I have done the same floodfill as you. I refined an algorithm that can fill 1 billion voxels in 2-3 minutes using less memory than stack and recursive and much faster. for 100 million voxel spaces my program always takes less than 10 seconds to flood fill: http://unity3dmc.blogspot.fr/2017/02/ultimate-3d-floodfill-scanline.html

The other option available to you is edge finding. it only works if you have a surface. find a boundary/edge pixel of your surface, and propagate around it, then you have your outline, which is kindof related. you can start a flood fill using every pixel outside of the outline. it's probably a bit faster.

Yes that is the most efficient. You can find the boundary of the object using flood fill. Then the negative image of that flood filled space is a perfectly filled object. Otherwise you would be implementing kindof despeckle routines and void pattern recognition algo's which are not efficient.

Here is a program where I do the same as you are doing using image stack voxels. Where it sais "reverse checksum array into supernormous" is where the program takes the negative image of the flood fill and defines it as the space without voids.

The fastest way to floodfill is this method:

it fills 4 million pixels per second.

On an I7 from 2017, that's equivalent to 9 million flooded pixels per second, so a 1024x1024 pixel image can be processed in about 0.1 seconds,using 10-15MB memory: