## Sunday, April 20, 2014

### Watershed image segmentation algorithm with Java

I am very interested in image segmentation, that is why the watershed segmentation caught my attention this time. People are using the watershed algorithm at least in the medical imaging applications, and the F. Meyer's algorithm was mentioned to be "one of the most common" one [1]. It also looked like it is quite easy to implement.

My favorite method for studying and understanding algorithms is to actually implement the algorithm. During the implementation, you really have to understand what is happening in each step. Also the produced images (in image algorithms) during the development process are helpful. It is fun to analyze the errors and what causes the artifacts in the image. So, the result for my studies is here: the watershed image segmentation algorithm implemented with Java.

#### Watershed algorithm explained (italics are from Wikipedia):

1. "A set of markers, pixels where the flooding shall start, are chosen. Each is given a different label."
• Find all the minimum points from the image. This means that you need to loop through pixels and find the darkest pixel which has not been already selected and which is not close to already selected minimum pixel. You can find as many minimums you like or only selected count of minimums. These minimums are the lowest points of the "basins" which will be flooded.
• The label can be for example the index numbering or color values from a known premade palette.

2. "The neighboring pixels of each marked area are inserted into a priority queue with a priority level corresponding to the gray level of the pixel."
• For each found minimum point, add the surrounding pixels to the priority queue. Set the initial labels to the label table (result image). Sort the priority queue from dark to light pixels. Now you can start the flooding.

3. "The pixel with the highest priority level is extracted from the priority queue. If the neighbors of the extracted pixel that have already been labeled all have the same label, then the pixel is labeled with their label. All non-marked neighbors that are not yet in the priority queue are put into the priority queue."
• Take out the first pixel (the darkest one) from the priority queue. Check the neighboring pixels for that pixel. If all the labeled pixels are having the same label, label the current pixel with the same label; the current pixel is "inside" of the basin. Remember, there has to be at least one labeled pixel; the one that was previously next to the current pixel.
• If there are at least two pixels with different label, it means that we have found a boundary between two different flood basins. We can mark this pixel then as an "edge" pixel.
• Finally, add all those neighboring pixels that do not have label to the priority queue.

4. "Redo step 3 until the priority queue is empty."
• Loop until there are no pixels left in the priority queue. When the priority queue is empty, all the pixels from the image are processed.

#### Sample images

Image 1. This is the sample image I have been using for testing. I created it myself with GIMP.

Image 2. This is the result after executing the Watershed algorithm to the sample image. Red squares are the found minimums and the white borders are the basins edges.

Image 3. Here are the sample image and the result image combined in a same image. The boundaries have been colored to green.

#### Notes:

• In this implementation, the minimums are found by "sweeping" the pixels from top-left to bottom-right. This way the found minimum is always the "first" one with the lowest value. That is why the minimum centers (the red squares) are not in the exact center of the darkest area.
• If you rotate the source image, the result will be different, that is because the minimum locations are changing (see the note above) and this discussion [2].
• After segmentation, you probably need the remove the "background" pixels. What you need to do might change per application. See more examples for fine tuning the Watershed algorithm from http://cmm.ensmp.fr/~beucher/wtshed.html [3].

#### The Java source

Implementation notes:
• To find more speed in the pixel sorting, I implemented a crude SortedVector, which uses insertion sort like algorithm to keep the inserted pixels (FloodPoints) in sorted order.
• I am disabling the pixels from a rectangle shaped area around the minimum. A circle shape should work better in some cases.
• The source contains commented code for saving the image in different steps of the process. Just uncomment the lines to get the images saved on your drive.
• The source contains commented code for real time view of the process. Just uncomment the parts where the JFrame is accessed to see the final image being built. You should try that, it looks nice! :)
• You can run the code in 4-connected pixels or 8-connected pixels mode. The results are slightly different. You should try them both.
Please let me know if you spot errors or have any other comments. Thanks!

#### Usage

java Watershed [source file] [result file] [number of segments, 1-256] [minimum window width, 8-256] [connected pixels, 4|8]

For example:
java Watershed sample_image.png result.png 22 60 8

#### SortedVector.java

 import java.util.Vector; public class SortedVector { Vector> data; public SortedVector() { data = new Vector>(); } public void add(Object o) { if (o instanceof Comparable) { insert((Comparable

#### Watershed.java

Sources:
[1] http://en.wikipedia.org/wiki/Watershed_%28image_processing%29
[2] http://imagej.1557.x6.nabble.com/Watershed-Algorithm-source-bug-td3685192.html
[3] http://cmm.ensmp.fr/~beucher/wtshed.html

San said...

Hello Jussi,

Thank you very much for the code shared here.

Could you please share the code to compare the watershed of two images and get the relevancy?

for my application, I want to find relevant images. If we search for a black check shirt, the system should return similar shirt image names based on the similarity. I think watershed comparison will find most relevant matches. So the front facing shirt image also match with the side view of the same shirt image.

Do you know some algorithm implementations already exists to do the same thing?

Thank you,
San.

Der Mawan said...

how to operate it jussi?

Jürgen K. said...

Well, I'm always getting an ArrayIndexOutOfBoundsException. Which parameters do you use?