Watershed Algorithm

Pre-process

• Apply Otsu Binarization to find the optimal threshold value.
  • OTSU works by creating a histogram
  • Iterate through the histogram to test different threshold values.
  • Each chosen threshold value creates two groups
  • Then the algo determines optimal threshold when the difference in intensity values are very different between the two groups (High between class variance) or when the difference in intensities are the lowest within class (Low in class variance)
• Invert the result, we want the centre of our coins in white.

Mat otsuOut;
threshold(src, otsuOut, 0.0, 255.0, THRESH_OTSU);
threshold(otsuOut, otsuOut, 0.0, 255.0, THRESH_BINARY_INV);

OTSU Output

Find sure background

• Remove any noise on the image by performing a open morphological operation. It applies erosion and then dilation on the image.
• Then we dilate the image for a few iterations, to make the binary image’s edge very wide, so anything beyond the dilation is sure to be the background.

Mat struc = getStructuringElement(MORPH_ELLIPSE, Size(3, 3));
morphologyEx(otsuOut, openOut, MORPH_OPEN, struc);
dilate(openOut, bg, struc, Point(-1, -1), 3);

Sure Background

Find sure foreground

• To find the sure foreground, we apply a distance transform on the dilated image.

  • Distance transform finds the distance between a foreground pixel and the nearest background pixel (i.e) find the closest dark pixel for each bright pixel in the image.
  • The commonly used math underneath is the Euclidean distance.
  • Euclidean distance:
  $$dist(p,q) = (q1 - p1)^2 + (q2 - p2)^2$$
  • Once we find all the distances, we pick only the top 70% or the 50% of the items closest to the centre, this way we know that these items are sure to be the foreground.

distanceTransform(openOut, disTrans, DIST_L2, 3, CV_8U);
 
double minVal, maxVal;
minMaxLoc(disTrans, &minVal, &maxVal);
threshold(disTrans, fg, 0.7 * maxVal, 255.0, THRESH_BINARY);

Sure Foreground

Determine “Unknown” region

• This is the region between the sure background and foreground.
• We need to figure out which object in foreground it belongs to.
• We will use this for our markers in the next step.

subtract(bg, fg,  unknown);

Unknown output

Label objects in foreground

• Label the different objects present in the foreground using the connectedComponents method.
• Next assign the label 0 to background
  • So increment all values in marker by 1. Now no markers will be labelled 0.
  • We know the pixel locations of the “unknown” pixels from the ‘unknown’ matrix.
  • In the marker mat, we set these unknows pixel locations to 0.
• This is one of the inputs to the watershed Algorithm.

connectedComponents(fg, markers);
add(markers, cv::Scalar(1), markers);
markers.setTo(0, unknown == 255);

Labelled Markers

Watershed Algorithm

Finally, now lets apply the markers matrix to the watershed Algorithm. In a nutshell, there are two steps involved:

• Expand the markers regions: For each of the markers, E.g. Label 2, any unknown pixel around it gets marked with the marker’s label.
• Recognize the border and stop the expansion of the border: If the neighbour is a label (E.g. 2) of another marker (E.g. 3), this means that we are at a border and our current marker needs to stop expanding and we need to mark this as a border.

watershed(img, markers);

Watershed Output