What is Watershed Algorithm?
Any grayscale image can be viewed as a topographic surface where high intensity denotes peaks and hills while low intensity denotes valleys. This algorithm uses that analogy and starts filling those low points (valleys) with a different colored label.
As the water rises, depending on the peaks (gradients) nearby, water from different valleys, obviously with different colors will start to merge. To avoid that, we build barriers in the locations where water merges. Continuing the work of filling water and building barriers until all the peaks are under water. Those barriers we created gives us the segmentation result. This is the “philosophy” behind the watershed.
Their approach however, gives us oversegmented result due to noise or any other irregularities in the image. Thus, OpenCV implemented a marker-based watershed algorithm where you specify which are all valley points are to be merged and which are not. It gives different labels for our object we know. Label the region which we are sure of being the foreground or object with one color, label the region which we are sure of being background or non-object with another color and finally the region which we are not sure of anything, label it with 0. That is our marker.
Then apply watershed algorithm. Then our marker will be updated with the labels we gave, and the boundaries of objects will have a value of -1.
Steps of watershed
Get foreground
It can be done by thresholding the output of cv2.distanceTransform(src, distanceType, markSize) where- src : 8-bit, single-channel (binary) source image. In my case I used morphologied image
- distanceType : Type of distance
- markSize : Size of the distance transform mask.
- Get Background
It can be done by dilating the thresholded original image.
- Get unkown region.
It can be done by cv2.subtract(src1, src2).
- Get boundaries
Perform cv2.connectedComponents(image) with foreground that we got at step 2 to determines the connectivity of blob-like regions in a binary image. Then, make the all values to 1 except unkown area.
Types of distance
DIST_USER : User defined distance.
DIST_L1 : distance = $ x1-x2 + y1-y2 $ DIST_L2 : the simple euclidean distance
DIST_C : distance = $max( x1-x2 , y1-y2 )$ DIST_L12 : L1-L2 metric: distance = $2(\sqrt{1+x \times \frac{x}{2}} - 1)$
DIST_FAIR : distance = $c^2(\frac{ x }{c}-log(\frac{1+ x }{c}))$, c = 1.3998 DIST_WELSCH : distance = $\frac{c^{2}}{2}(1-e^{-(x/c)^{2}}), c = 2.9846$
- DIST_HUBER : distance = $|x|<c\ ?\ \frac{x^{2}}{2}\ :\ c(|x|-\frac{c}{2}), c=1.345$
Distance Transform Masks
- DIST_MASK_3 : mask = 3
- DIST_MASK_5 : mask = 5