Add support for compact and masked watersheds

tlnagy commented 5 years ago

This PR adds support for the compact watershed algorithm (https://www.tu-chemnitz.de/etit/proaut/publications/cws_pSLIC_ICPR.pdf). This algorithm is nice because it results in more uniform watershed basins as you increase the compactness parameter.

I still need to do the following before I think it should be merged:

[x] Add tests
[x] More docs (and reference!)
[x] Benchmarking (thanks to https://github.com/scikit-image/scikit-image/issues/2636 for speed enhancements)

Example segmentation following the coin example from the docs:

Simple Watershed	Compact watershed

closes #34

tlnagy commented 5 years ago

~~Looks like my PR introduces quite a few allocations which are causing some slowdowns. Not sure where they are creeping in just yet.~~ Looks like I had some parameterization problems, the updated PR has the same performance as master

Simple watershed

Master

julia> @benchmark segments = watershed(dist, markers)
BenchmarkTools.Trial: 
  memory estimate:  3.24 MiB
  allocs estimate:  119
  --------------
  minimum time:     41.722 ms (0.00% GC)
  median time:      42.512 ms (0.00% GC)
  mean time:        43.070 ms (0.92% GC)
  maximum time:     48.598 ms (5.49% GC)
  --------------
  samples:          117
  evals/sample:     1

This PR

julia> @benchmark segments = watershed(dist, markers)
BenchmarkTools.Trial: 
  memory estimate:  3.37 MiB
  allocs estimate:  119
  --------------
  minimum time:     44.658 ms (0.00% GC)
  median time:      45.398 ms (0.00% GC)
  mean time:        45.813 ms (0.92% GC)
  maximum time:     48.927 ms (5.84% GC)
  --------------
  samples:          110
  evals/sample:     1

timholy commented 5 years ago

Sorry for the delay here. It will take me a little while to read the paper so that I can understand this. Once you get eager to have this merged strip the WIP and ping me.

tlnagy commented 5 years ago

The TL;DR on the compact watershed algorithm is that, instead of assigning the final label as a pixel is pushed into the queue, it updates the label every time it encounters that position if the new label is more optimal than the previous label. More optimal in this case is a linear combination of the euclidean distance between the seed and the pixel and the typical brightness of the pixel. It doesn't lock in the final labelling until the pixels come off the queue, this lets it find better labelings later and replace initial labelings, which cannot happen with standard watershed.

I hope that helps explain what happens.