Slice interpolation

[GenevieveBuckley]

This issue is intended as a record of some of our offline & email discussions.

We've discussed three different types of approaches:

1. Shape based slice interpolation
2. Convex hulls
3. Contour slice interpolation

1. Shape based slice interpolation

Resources

• Paper: Raya and Udupa "Shape-Based Interpolation of Multidimensional Objects" IEEE TRANSACTIONS ON MEDICAL IMAGING, VOL. 9, NO. I , MARCH 1990
• This StackOverflow question (useful to look at, although it's not n-dimensional & I think there's a subtle bug in there too)

Work done

• Gen put together a demo (in particular, see this notebook)
• James put together https://github.com/jni/zarpaint/pull/32 based on the notebook, and is considering how the user interaction is best handled (tricky to do well)
• Draga talked to Caleb Hulbert about how Paintera's shape interpolation mode handles this

Problems

• You get artifacts if there is not significant overlap of pixels between the labelled slices. So that's a problem, especially if you have to label long thin things like filaments of neurons, that may not be well aligned with the image axes.

Plan

Continue figuring out the user interface. This will be necessary regardless of the interpolation algorithm used.

2. Convex hulls

Resources

• scikit-image convex_hull_image function
• The quickhull algorithm. Although, it turns out the scikit-image is using quickhull already (because the scipy ConvexHull uses it)

Work done

• Gen tried out convex hulls in this notebook

Problems

• It's super, super slow. It's not useable because of this, and I don't see a way to make it as fast as we'd need.
• It's also not solving the actual problem. You'd get most of your object labelled, but you'd still need to edit every single slice at the edges, which defeats the point.

Plan

Discontinue the convex hull approach.

3. Contour slice interpolation

Resources:

• ND morphological contour interpolation: https://www.insight-journal.org/browse/publication/977
• Paper: https://pubmed.ncbi.nlm.nih.gov/18632365/
• The napari-nd-annotator plugin (in particular, this file). Uses opencv contours, BSD-3 licence (same licence as zarpaint). Note that this plugin currently does suffer from performance problems when there are ~30 labelled objects. It's more likely that's caused by other parts of the plugin though, and not the contour slice interpolation algorithm

Plan

Try contour slice interpolation in place of the shape based euclidean distance transform method above. See if the results are nicer on a broader range of datasets (at first glance, it certainly seems like it)

[GenevieveBuckley]

@jni and @jamesyan-git - the content about the napari-nd-annotator is new, we haven't talked about that yet. I think it would be useful to look at, even if there are some problems with the performance (see here) and documentation (although I did write up some notes here)

[bauerdavid]

@GenevieveBuckley The performance drop happens regardless of the interpolation part, it is rather related to UI problems. For a single object, interpolating ~20-30 slices is done in ~0.01s (with 300 contour points), so theoretically up to 100 similar-sized objects it would run under 1s (although I assume this could be further optimized).

[jni]

The contour stuff in nd-annotator is so great! Makes me feel rather validated, thanks @bauerdavid! 😂

[GenevieveBuckley]

Link to https://github.com/jni/zarpaint/pull/32