Watershed Image Segmentation


In image processing, the watershed transform is a process of image segmentation and regions boundaries extraction. The image is a topographic surface where high color levels mean higher altitudes while lower ones are valleys. The segmentation process simulates flooding from seed points – markers.

A common way to select markers is the gradient local minimum. However, we can also use any other method of seed selection . The Watershed is based on geological surface representation, therefore we divide the image in two sets: the catchment basins and the watershed lines.

Watershed transform
Seed 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. When it floods a gradient image the basins should emerge along the objects edges. The process describes as following:

  1. Initialize object groups with previously 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

Boundary markers, i.e. the watershed lines are all remaining unlabeled pixel.

How to select seed points for segmentation

There are different strategies to select seed points. We use a user-controlled markers selection in our HTML5 demo application. Use Left Mouse Click and Right Mouse Click to select foreground and background areas. Some articles discuss different algorithms for automatic seeds selection 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 we take each point neighbor and push it in our queue. The push method makes a scan for proper position by a simple binary search. This way the list remains sorted throughout the 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

Typically, algorithms use a gradient image to measure the distance between pixels. In our demo application we use different weighting function. The weight is calculated based on the improved RGB Euclidean distance [2]. The distance between the center point and selected neighbor is as on the following equation:

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

The math equation implements as on the following JavaScript code segment:


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 image partition

At first, we eliminate image noise by a Gaussian filter 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 adjacent 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);
		}
	}
}

 


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


Related Articles