Compute Voronoi? about scikit-fmm HOT 12 CLOSED

Hi and thanks for the message. What you describe should not be too hard. Have a look at this pull request as it does almost what you want. #30

As far as I understand, when a point is frozen it can look at the adjacent frozen points and carry out either the value at phi=0 or the coordinates of phi=0. I think this is also how 2D image skeletonization works.

from scikit-fmm.

from scikit-fmm.

from scikit-fmm.

from scikit-fmm.

Thanks for the optimization, I will add that. I need to get a release out soon. I do not see any pictures from in the email or in the GH issue. Can you try to send them some other way?

from scikit-fmm.

If you have a minute could you make a pull request for the root change? I will merge it in and try to get a release out this week.

from scikit-fmm.

from scikit-fmm.

Something to consider in terms of accuracy is that this module has a second-order point update, but the narrow band initialization is only first-order. The first-order error gets marched out, particularly along diagonals.
We have a (now quite old) branch that uses a higher order narrow band initialization https://github.com/scikit-fmm/scikit-fmm/tree/bicubic-init I need to revisit this branch. You could try this and you may get better results.

from scikit-fmm.

Thanks for the hint.

The actual problem is that the algorithm was not designed to keep the 'identity' of the source/emitter voxels; the algorithm was designed to compute an 'anonymous' distance. Furthermore, the algorithm just investigates the orthogonal neighbors of a cell. This results in (some) mislabeling of voxels when the 'voxel front' with different label values meet.

If the source/emitter voxels are fairly far apart, then those mislablings may be tolerable, depending on the use case. But if the source/emitter voxels are close to each other, those mislablings spread over the whole image. Because the algorithm investigates orthogonal neighbors, those artifacts in the voxel fronts lead to orthogonal artifacts in the resulting image.

Unfortunately, raising the overall accuracy will not change this.

In our application we need a correct labeling of voxels, we have a little computation time to spare, some memory to fill, and we know exactly the set of labels values to be spread. So for each label, we set up a phi image where only those label voxels define the zero contour. Then, we compute the (masked) distance image with your algorithm. When all the distance images are computed, we iterate over all voxels and find the minimum computed distance; we then use the index where we found the minimum distance and map this index back to the label value and write that label value to the output image.

This results in a Voronoi division based on geodesic distances.

And because we don't have that much time to spare, we use OpenMP to let the distance images for each label value be computed in parallel.

Images show a direct volume rendering of test images with 24x24x24 voxels, the result images show only one set of labeled voxels, the other set is transparent. No masks were used for this example for clarity.

From left to right: 1. Input source voxels, 2. Result of the augmented FMM, 3. Result of an Euclidean Voronoi algorithm, 4. Result of the min-distance-index-to-label algorithm.

From top to bottom: 1. Emitter voxels fairly far apart, 2. Emitter voxels closer, artifacts appear in the AugFMM, 3. Artifacts in the AugFMM render the result useless.

from scikit-fmm.

OK, makes sense, you could also check out multi-stencil fast marching: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.69.741&rep=rep1&type=pdf This may address the diagonal issue. Or simpler you could use a stencil that also has diagonals terms? I have also been thinking about adding this.

from scikit-fmm.

Thanks for giving it more thought! Those 'little errors' at the voxel fronts are inherent in those FM methods and they will all amplify them when giving enough space/iterations. They are inherent because of the order of evaluation of orthogonal neighbors.

We are fine with computing a distance image for each label and then choosing the minimum distance as this approach directly implements the definition of a Voronoi division.

However, we'd appreciate the FMM being more precise as you described with the initialization of the narrow band also using second-order terms where applicable. This will likely reduce the amount of differences in the interface of Voronoi regions when compared to the result of a classical Euclidean Voronoi division (in open space).

from scikit-fmm.

Closing the issue because we found a stable way to compute a geodesic Voronoi division using the FMM.

from scikit-fmm.