watershed algorithm for blob detection

below we generate random 2d gaussians (left), detect peaks and use watershed for image segmentation (right)

algorithm

1.	Background noise estimation

•	Select smallest 1% pixels

•	Compute mean and variance from their 4-connectivity neighbors 

2.	Gaussian smoothing with estimated variance

3.	Convolution with Laplace filter, sharpening

4.	Replace pixels smaller than noise mean with 0

5.	Retrieve list of maximum regions with maximum filter from original picture

6.	Watershed from maximum regions

addressing color invasion

Illustrating color invasion

To address color invasion

• Check before we label a region whether this region is in the 8-connectivity neighborhood of a region with this label. If not, we leave the region unlabeled. Other criteria for region labeling still hold: o If a region has two higher neighbor region with different label, it is background o If a region has a higher neighbor which is background, it is background

• Know when a blob is resolved. A blob is fully resolved when it is no more surrounded with unlabeled, in the 8-connectivity sense. As soon as a blob is fully resolved, we empty its queue.

That's better

But "coeluted zones" are detected poorly.

hollow coeluted zones

Another example

coeluted zones are here

or nicely seen in 3D

Intuition

We have a contour for the coeluted zone. This is the ‘envelop for points already resolved as belonging to the blob’.

We wish to fill the zone with colors from the blobs in the zone. The demarcation line is the valley between adjacent blobs.

We can distinguish between these two cases:

• Almost resolved zone, as zone with blobs 1 and 10 on figure 5b. Integration error for each of these blobs is approximately 15%. Valley could be defined as the set of lowest points from paths binding already resolved regions from one blob to already resolved regions from second blob.

• Poorly resolved zone as three blobs zone.

-Blobs 6 and 2 are said to be strongly coeluted. They could not be resolved separately, they are merged and the peaks apex with the highest volume only is kept

-This conclusion holds at this scale. We don’t definitively discard the blob, but given preprocessing, this blob is not ‘seen’ by segmentation method.

Algorithm for coeluted zones filling

1.	Find coeluted zones

Blobs in a same coeluted zone are identified

2.	Find a hull

Quickhull algorithm, [7], computes convex hull for the coeluted zone. 
The convex hull is the smallest convex set containing all points already identified as belonging to blobs contained in this coeluted zone. 
Implementation details are in appendix.

Improvement could resort to alpha-shapes to closer fit the blob’s shape. 

3.	Find points in valley

4.	Complete valley 

From isolated points located in valley, complete valley finding the minimum spanning tree of these points

5.	Fill with color with valley as a separation

Convex hull

We try to join points in valleys in the most natural way. We build the minimum spanning tree of points in valley with Kruskal algorithm and we add to valleys all points on edges.

Green dots fill in valleys smoothly.