Watershed Transform
The watershed transform is the most important morphological tool for image segmentation. The watershed itself is not a segmentation tool by itself but it is a building block to design very successful image segmentation procedures.
The watershed from markers can be intuitively described as the following flooding simulation. First, the input image must be modeled as a plastic surface. The watershed markers are the places to create holes in the surface model. The plastic model is then submerged slowly in water. From each of the holes, the flooding water is painted with the color associated to the marker (hole). At any time that different colored water coming from different holes meet, a dam is built to avoid their mixing. This mechanism continues progressively until the hole model is flooded. The final dams are the watershed lines and the colored water is the watershed partitioning of the image.
Although this description is very intuitive, it is the mechanism used in one of the most efficient implementations of the watershed, called watershed using hierarchical queues. Also, it can be shown that the watershed is an optimal partition of the input image which minimizes the cost from the pixel to the assigned marker.
1-D Example
Below is a simple illustration of the watershed on an 1-D signal (ECG). The idea is to partition the signal in four regions at the three most salient peaks. The marker is made of four different label values, 20, 30, 40 and 50 each one placed manually in any part of the region to segment. The watershed lines are shown in blue precisely at the three prominent peaks. The watershed regions are shown in magenta, each region with the same value of the marker. The watershed is classified as a region growing algorithm as the marker labels are propagated following the flooding criteria. One important property of the watershed is in regard of the robustness of the marker placement. In the example below, if the markers are extented anywhere inside the resulting partition, the watershed transform will give the same result.
f=imread('heart_uint8.tif');
m=mmsubm(f,f);
m(40)=20; % markers
m(100)=30;
m(200)=40;
m(300)=50;
wbin=mmcwatershed(f,m); % watershed lines
wreg=mmcwatershed(f,m,mmsecross,'REGIONS'); % regions
x=1:length(f);
plot(x,f,'r', x,m,'k', x,mmgray(wbin),'b', x,wreg,'m');
|
Basic methodology for image segmentation
To use the watershed for image segmentation, the idea is to compute the gradient of the image, place the markers inside of the objects of interest and use the watershed to find the best edge (highest points) between the markers to partition the image. The recipie used for watershed based image segmentation is:
- Image smoothing
- Gradient
- Marker finding, one to each object
- Watershed from markers applied to the gradient image
This methodology is very general and can be applied successfuly to many different problems. Usually the most difficult part is to detect the markers. One can say that the segmentation problem was shifted from object segmentation to marker detection. It is correct, the segmentation problem was simplified to find the markers (samples of the object). Usually the markers are small and robust to position.
Examples
The toolbox has many segmentation examples using the watershed approach. In all of them the most difficult part is related to find the markers automatically. In the two examples below, the markers were calculated based on the geometry properties of the object to segment. In the beef example, the inside marker is placed on the center of the whole beef and the outside marker is the border of the beef. For the keyboard example, the inside markers are the white writings on each key and the outside marker is computed using the watershed with the first set of markers.
SKIZ - SKeleton of Influence Zone
The SKIZ is a generalized Voronoi diagram, where the points in Voronoi are replaced to regions. The SKIZ are the lines which are equidistant to two or more connected components of the image. See mmskiz. The SKIZ can be computed using the watershed on the distance transform of the complement of the image.
f=imread('blob2.tif');
dt=mmdist(mmneg(f),mmsebox,'EUCLIDEAN');
mmdtshow(dt,50);
sk=mmcwatershed(dt,f);
mmshow(mmsurf(dt),mmdil(sk),f);
|
Watershed to separate touching blobs in binary images
The first use of the watershed was to separate touching convex blobs in binary images. This technique is very popular to solve this kind of problem. Below is an illustrative example where two circles overlap. The goal is to detect the best line to desconnect them. The method is based on the distance transform. The markers are the regional maximum of the distance transform and the line separating the circles is computed using the watershed on the negated distance transform. The final watershed line is used to cut the two circles apart.
f=imread('touchcell.tif');
fd=mmdist(f,mmsebox,'EUCLIDEAN');
m=mmregmax(fd);
ws=mmcwatershed(mmneg(fd),m);
g=mmintersec(f,mmneg(ws));
mmshow(f);
mmdtshow(fd);
mmshow(f,mmdil(m),ws);
mmshow(g);
|
This technique is used to separate touching blood cells in the demonstration below:
- Demo: mmdcells Separate blood cells
Exercises
- What happens if the SKIZ of the markers is used to separate the connected circles in the example used with the image
touchcell.tif?
- Plot the horizontal line of the inverse of the distance transform of the touchcell example to understand why the watershed line lies at the touching cell
touchcell.tif?