Watershed2D result is sensitive to the order of neighbors enumeration?

[dmikushin]

Hello,

I would like to offer a confusing observation. During my testing of 2D watershed I came across the case being sensitive to the order of accessing the pixel neighbors. For example, if we change 8D pattern definition from:

		neighbors.add( new Cursor2D( x-1, y-1 ) );
		neighbors.add( new Cursor2D( x-1, y   ) );
		neighbors.add( new Cursor2D( x-1, y+1 ) );
		neighbors.add( new Cursor2D(   x, y-1 ) );
		neighbors.add( new Cursor2D(   x, y+1 ) );
		neighbors.add( new Cursor2D( x+1, y-1 ) );
		neighbors.add( new Cursor2D( x+1, y   ) );
		neighbors.add( new Cursor2D( x+1, y+1 ) );

to

		neighbors.add( new Cursor2D(   x, y+1 ) );
		neighbors.add( new Cursor2D( x+1, y-1 ) );
		neighbors.add( new Cursor2D( x+1, y   ) );
		neighbors.add( new Cursor2D( x+1, y+1 ) );
		neighbors.add( new Cursor2D( x-1, y-1 ) );
		neighbors.add( new Cursor2D( x-1, y   ) );
		neighbors.add( new Cursor2D( x-1, y+1 ) );
		neighbors.add( new Cursor2D(   x, y-1 ) );

the resulting 2048x2048 image will have one previously zero pixel as non-zero, and the rest - equal to the original version. Weird?

From the program point of view, such sensitivity feels logical, as long as there is a break out of the neighbors enumeration loop:

	    		// read neighbor coordinates	    		
	    		neigh.setCursor( p );
	    		for( Cursor2D c : neigh.getNeighbors() )			       		
	    		{       			
	    			int u = c.getX();
	    			int v = c.getY();

	    			// initialize queue with neighbors at level h of current basins or watersheds
	    			if ( u >= 0 && u < size1 && v >= 0 && v < size2 
	    					&& tabLabels[ u ][ v ] >= WSHED 
	    					&& maskImage.getf( u, v ) > 0 ) 
	    				//&&  ( tabLabels[ u ][ v ] > 0 || tabLabels[ u ][ v ] == WSHED ) )
	    				{
	    					fifo.addLast( p );
	    					tabLabels[ i ][ j ] = INQUEUE;
	    					break;
	    				}	    			
	    		}// end for	    	

So, if neighbors are reordered, another neighbor may be picked up and change the result.

I'm wondering if this is a program bug in a sense that it breaks the symmetric nature of the watershed algorithm? Or is the algorithm itself non-symmetric?

Full patch to reproduce: benchmark.patch.txt

[iarganda]

Hello @dmikushin

I don't know what @dlegland will say but my feeling is this type of behaviors are expected in the most basic watershed algorithm. Also the order of the neighbor might always have an impact in the final result if the neighbors have the same intensity.

[dlegland]

hello @dmikushin , I agree with @iarganda, most watershed algorithms are sensitive to the ordering of neighbors. The, rotation an image and applying the WS may result in a different segmentation...

However this kind of behaviour should happen only when several neighbor pixels/voxels have same value. When they have different values, their natural ordering removes ambiguity of neighbor order.