Added watershed segmentation

[tejus-gupta]

Implements watershed transformation based image segmentation.

The algorithm considers a grayscale image as a topographic surface. This surface is flooded from the marker positions (local minima of the image by default) and final basins correspond to the segments. (Nicely explained here).

The basic version often produces over-segmentation due to noise and too many local minima. There are several strategies to deal with this - preprocessing the image to remove shallow(insignificant) minima, flooding the surface from predefined markers and post processing the image to merge similar regions.

[tejus-gupta]

In some implementations, a one-pixel wide line (watershed line/dam) separates the basins identified by the watershed transformation. Would this be useful to have?

I haven't implemented any region merging algorithm for post processing because I couldn't find any widely used method. Every paper seemed to using their own version of region merging heuristic. Please tell if there is any good method I missed.

[annimesh2809]

@tejus-gupta I was looking for papers regarding k-means clustering and found this paper. I thought it might be of interest to you regarding the over-segmentation.

[timholy]

In some implementations, a one-pixel wide line (watershed line/dam) separates the basins identified by the watershed transformation. Would this be useful to have?

It might, but doesn't seem essential. Seems like adding it might slow it down?

I haven't implemented any region merging algorithm for post processing because I couldn't find any widely used method. Every paper seemed to using their own version of region merging heuristic. Please tell if there is any good method I missed.

I haven't used watershed much (for low SNR images there are better approaches), so I don't know of one. We could let the users call such methods independently and keep watershed itself "clean."

[timholy]

If you generalize this to 3d then you can compare against https://github.com/seung-lab/Watershed.jl. I think it's really good to have a simple implementation available, but also to know how it stacks up against more complex ones.

[codecov[bot]]

Codecov Report

Merging #6 into master will decrease coverage by 4.61%. The diff coverage is 68.18%.

@@            Coverage Diff             @@
##           master       #6      +/-   ##
==========================================
- Coverage     100%   95.38%   -4.62%     
==========================================
  Files           5        6       +1     
  Lines         281      325      +44     
==========================================
+ Hits          281      310      +29     
- Misses          0       15      +15

Impacted Files	Coverage Δ
src/ImageSegmentation.jl	100% <ø> (ø)	:arrow_up:
src/watershed.jl	68.18% <68.18%> (ø)
src/fast_scanning.jl	98.5% <0%> (-1.5%)	:arrow_down:

---

Continue to review full report at Codecov.

Legend - Click here to learn more Δ = absolute <relative> (impact), ø = not affected, ? = missing data Powered by Codecov. Last update d7dff8e...76ee028. Read the comment docs.

[codecov[bot]]

Codecov Report

Merging #6 into master will decrease coverage by 0.62%. The diff coverage is 97.5%.

@@            Coverage Diff             @@
##           master       #6      +/-   ##
==========================================
- Coverage     100%   99.37%   -0.63%     
==========================================
  Files           5        6       +1     
  Lines         281      321      +40     
==========================================
+ Hits          281      319      +38     
- Misses          0        2       +2

Impacted Files	Coverage Δ
src/ImageSegmentation.jl	100% <ø> (ø)	:arrow_up:
src/watershed.jl	97.5% <97.5%> (ø)
src/fast_scanning.jl	98.5% <0%> (-1.5%)	:arrow_down:

---

Continue to review full report at Codecov.

Legend - Click here to learn more Δ = absolute <relative> (impact), ø = not affected, ? = missing data Powered by Codecov. Last update d7dff8e...79f2744. Read the comment docs.

[tejus-gupta]

Demo:

using Images, ImageView, ImageSegmentation;

img = load("im.jpg");
bw = Gray.(img).>0.5;
dist = 1.-distance_transform(feature_transform(bw));
markers = label_components(dist.<-15);
out=watershed(dist, markers);
show_seg(out.image_indexmap.*(1.-bw));

[timholy]

LGTM. Squash & merge at will!