Watershed Image Segmentation


In image processing, the watershed transform is a process of image segmentation and regions boundaries extraction. The theory behind is that the image is represented as a topographic surface where the high color levels mean higher altitude while the lower ones are treated as valleys. The segmentation process simulates flooding from seed points – markers. A common approach for markers selection is the gradient local minimal, but the method is applicable to any other seeds selection method. Since the method is based on geological surface representation, the image is partitioned into two sets: the catchment basins and the watershed lines.

Watershed transformSeed controlled Watershed transform

How does the Watershed works

Our algorithm is based on Meyer’s flooding introduced by F. Meyer in the early 90’s. Originally the algorithm  works on a grayscale image. A flooding process is performed over a gradient image, so the basins should emerge along the objects edges. The process describes as following:

  1. Initialize object groups with previouseely selected seeds markers.
  2. This step extracts the neighboring pixels of each group and moves them into a priority queue. Originally the priority level corresponds to pixel gradient value, but it is possible to use different weighting measure.
  3. The lowest priority pixels are extracted from the queue and processed first. If all visited neighbors of extracted pixel have the same label the pixel is marked with their same label. All non-visited pixels are included into the priority queue.
  4. Repeat step 3 till completion

All remaining unlabeled pixel are marked as a boundary i.e. the watershed lines.

 

Seed Points Selection

As it was mentioned there are different strategies for seed points selection. In our HTML5 demo application we are using user-controlled markers selection using Left Mouse Click and Right Mouse Click to mark foreground and background areas. Some articles discuss different automatic seeds selection using algorithms like BinarizationMorphological Opening, Distance Transform and so on. Although the focus of this post is not this part of the image segmentation process, we plan to review it in future articles.

 

Priority Queue Details

Our HTML5 realization of Watershed Image Segmentation is based on our custom JavaScript priority queue object. During the pixels extraction each neighbor of the currently processed point is inserted into our queue. At this insertion the push method makes a scan for proper position by a simple binary search thus the list remains sorted for the whole process. The nodes comparator is a custom input method and it allows flexible PQueue usage.


var PQueue = function(){
	this.nodes = [];
}

PQueue.prototype.push = function(el, comparator){
	var nodes = this.nodes;
	var offset = 0,
		size = nodes.length;
		
	while (offset < size){ 
		const pos = ((offset + size) >>> 1);
		const diff = comparator(el, nodes[pos]);
		((diff < 0) ? (offset = pos + 1) : (size = pos));
	}
	
	nodes.splice(offset, 0, el);
}

 

Distance between pixels

Normally as a distance measurement between pixels the algorithm use the gradient image. In our demo application we are using different weighting function. The weight is calculated based on the improved RGB Euclidean distance [2] between the center point and selected neighbor as on the following equation:

`\sqrt{(2\Delta R^2 + 4\Delta G^2 + 3\Delta B^2)}`

Which the following JavaScript code segment represents:


function diffRGB(p1, p2){
	const rmean = (data[p1 + 0] + data[p2 + 0]) >>> 1;
	const r = (data[p1 + 0] - data[p2 + 0]),
			g = (data[p1 + 1] - data[p2 + 1]),
			b = (data[p1 + 2] - data[p2 + 2]);
		
	return Math.sqrt((((512+rmean)*r*r)>>8) + 4*g*g + (((767-rmean)*b*b)>>8));
}

 

Watershed Transform

As a preprocessing step we eliminate image noise by a Gaussian blur with small sigma value. After this we initialize the image buffer with appropriate label values corresponding to the input seeds:


for (var i = 0, l = seeds.length; seeds[i]; i++){
	var p = seeds[i].pixels;
	for (var j = 0, c = p.length; j < c; j++){
		buff[p[j]] = (i + 1)*80; // For example 80 and 160 grey values
		addPoint(p[j]);
	}
}

As a next step we extract all central pixels from our priority queue until we process the whole image:


while (!queue.empty()){
	var el = queue.pop();
	addPoint(el);
}

The neighbor pixels are extracted and placed into the PQueue for further processing:


function addPoint(p){
	for (var i = 0; i < 4; i++){
		const pos = p + dirxy[i];
		if (buff[pos] === 0){
			buff[pos] = buff[p];
			buff[pos + 1] = diffRGB(p, pos);
			queue.push(pos, comparator);
		}
	}
}


 

Watershed Image Segmentation Demo

Use Left and Right mouse buttons to draw foreground and background seeds. Press the Execute button to trigger segmentation.

Sigma: 3


Visit FivekoGFX on GitHub for more image processing examples and detailed source code!


References

  1. Image Segmentation and Mathematical Morphology
  2. Color Difference – Wikipedia