Fast marching method through diagonal pixels?

[cmarshak]

I am not sure if this is possible within the confines of the fast marching algorithm but can the existing method be adjusted to move through a diagonal as in the image below where the blue indicates the masked areas (obstacle)?

The "movement" must occur vertically / horizontally only and requires the channel to be

Thanks for your help.

[jkfurtney]

Hmm, I am not sure what you are asking. I see a purple background with a diagonal yellow band. Which one is the mask? Can you provide some code that demonstrates the problem?

The stencil that this method uses to update each point only looks in the cardinal directions. There are stencils that "look" in the diagonal directions.

[cmarshak]

Thank you for your reply. Here are some code snippets. I suspect, as you say, a stencil option would probably make diagonal movement possible - thank you again for any help.

import numpy as np
import numpy.ma as ma
import matplotlib.pyplot as plt
import skfmm

mask_diag = np.diag(np.ones(10))
mask_diag_buff = np.diag(np.ones(10)) + np.diag(np.ones(9), k=1)
init_mask = np.zeros((10, 10))
init_mask[:2, :2] = 1

fig, ax = plt.subplots(1, 3, figsize=(9, 3))
ax[0].imshow(mask_diag)
ax[0].set_title('Diagonal Mask')
ax[1].imshow(mask_diag_buff)
ax[1].set_title('Diagonal Mask with Superdiagonal')
ax[2].imshow(init_mask)
ax[2].set_title('Initialization Mask')

mask_diag = ~(mask_diag.astype(bool))
phi = ma.masked_array(np.ones(mask_diag.shape), mask=mask_diag)
phi.data[init_mask.astype(bool)] = 0
dist = skfmm.distance(phi)

mask_diag = ~(mask_diag_buff.astype(bool))
phi = ma.masked_array(np.ones(mask_diag.shape), mask=mask_diag)
phi.data[init_mask.astype(bool)] = 0
dist_buff = skfmm.distance(phi)

fig, ax = plt.subplots(1, 2, figsize=(8, 4))
ax[0].imshow(dist)
ax[0].set_title('Diagonal Mask')
ax[1].imshow(dist_buff)
ax[1].set_title('Diagonal Mask with Superdiagonal')

[jkfurtney]

Yes, changing the stencil would be the only way to do this as far as I can tell. There is a paper that describes something similar: Multistencils Fast Marching Methods. http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.69.741&rep=rep1&type=pdf

The first- and second-order stencils used by scikit-fmm are baked into the c++ code in a fairly deep way. So adding new stencils would not be easy. I cannot look into this at the moment unfortunately, but I will keep this in mind for future developments.

If you want to experiment with different stencils, you could make a test implementation of FMM in Python. The binary min-heap provided by the module (skfmm.heap) is for just this purpose. Stay in touch if you get something working, it would be a nice feature to add.

[cmarshak]

I am preparing a paper using your package and will cite the github repo. I will also reference the paper for future developments that would improve some of the products I am generating and try to look into the heap method - that's awesome that its easy to experiment with from python.

Thank you for your help.

[jkfurtney]

I am going to close this issue for now. If anything else come up, let me know.