Scale postprocessing

[dchaley]

This one is hard!

The algorithm doesn’t divide into neat tiles. Pixel values can “spread” from tile to tile.

Naive / inefficient algorithm:

• Repeat until convergence:
  • For each pixel:
  • Spread pixel values to neighbors as controlled by the pixel mask.

We could do something similar, processing each tile until it converges. If a tile pushes to its neighbors, those would need to be reprocessed as well.

Something like:

• Enqueue every tile
  • Repeat until queue is empty:
  • For each tile:
    • Spread pixel values within the tile.
    • If the pixel values push into other tiles: put those tiles back on the processing queue.

[dchaley]

After improving h_maxima (called by deep_watershed) in #350 there remains a lot of postprocessing time spent in fill_holes, approximately 14% for 140M pixels:

and approximately 40% for 260k pixels:

Note that the larger image was profiled with cProfile which has some accuracy limitations particularly for very short function calls (< 0.001s) and very many calls. We have both of these situations … shown very clearly for the 260k-pixel image.

Speedscope couldn't handle the 140M pixel image: it generated 4GB of profiling json 🤯

We did spot a potential improvement, see #357