Image Segmentation with Watershed, C++, OpenCV 3.X and CUDA

This prototype tests the image segmentation with several Watershed-based algorithms, including the marker-controlled variation provided by OpenCV 3.X, with the graph-based variation Power Watershed implemented in C++, with the unified version of waterfalls, standard and P algorithms implemented in C++, and a CUDA implementation of the standard algorithm.

In computer vision, image segmentation is the process of partitioning a digital image into multiple segments. The goal of segmentation is to simplify and/or change the representation of an image into something that is more meaningful and easier to analyze. Image segmentation is typically used to locate objects and boundaries (lines, curves, etc.) in images. More precisely, image segmentation is the process of assigning a label to every pixel in an image such that pixels with the same label share certain characteristics.

The result of image segmentation

The result of image segmentation

There are many segmentation algorithms available, from simple histogram thresholding to complex based on mathematical models, but nothing works perfect in all the cases. In computer vision, Image segmentation algorithms available either as interactive or automated approaches. In medical imagine, interactive segmentation techniques are mostly used due to the high precision requirement of medical applications. But some applications like semantic indexing of images may require fully automated segmentation method.

Automated segmentation methods can be divided into two categories namely supervised and unsupervised segmentation. In supervised segmentation the method use a machine learning technique to provide the knowledge of objects (or ground truth segments) in images to the segmentation algorithm. Unsupervised segmentation may use basic image processing techniques to complex optimization algorithms. The main problem in unsupervised segmentation algorithms is the difficulty of balancing the over-segmentation and under-segmentation.

This article explains the unsupervised method and the implementation of Watershed-based algorithms and optimizations to reduce over-segmentation occurred with the standard Watershed algorithm.

In the study of image processing a watershed of a grayscale image is analogous to the notion of a catchment basin of a heightmap. In short, a drop of water following the gradient of an image flows along a path to finally reach a local minimum. Intuitively, the watershed of a relief correspond to the limits of the adjacent catchment basins of the drops of water.

Bright areas are "high" and dark areas are "low,". With surfaces, it is natural to think in terms of catchment basins and watershed lines.

Bright areas are “high” and dark areas are “low,”. With surfaces, it is natural to think in terms of catchment basins and watershed lines.

Five different variations of the Watershed algorithm are compared to each other in this prototype:

  • OpenCV 3.x CPU based method cv::watershed from the imgproc module implemented as marker-controlled variation as described in this official tutorial. The OpenCV GPU version is not available yet.
  • An improved version of the official tutorial using histograms to reduce over-segmentation as discribed in this article.
  • The Power Watershed graph-based variation that includes the graph cuts, random walker, and shortest path optimization implemented in C++  by the author of the algorithm.
  • The unified version of waterfalls, standard and P algorithms implemented by the autor in C++ and Python as a part of the mamba-image library.
  • A basic implementation of the standard watershed algorithm without over-segmentation reduction using Cuda as described here.

OpenCV CPU, marker-controlled variation implementation:

OpenCV 3.x CPU based method cv::watershed from the imgproc module implemented as marker-controlled variation as described in this official tutorial. The OpenCV GPU version is not available yet.

OpenCV CPU, marker-controlled variation with histograms based over-segmentation reduction:

An improved version of the official tutorial using histograms to reduce over-segmentation as discribed in this article.

Power Watershed graph-based variation:

The Power Watershed graph-based variation that includes the graph cuts, random walker, and shortest path optimization implemented in C++  by the author of the algorithm.

Unified version of waterfalls, standard and P algorithms

The unified version of waterfalls, standard and P algorithms implemented by the autor in C++ and Python as a part of the mamba-image library.

The implementation is based half on a low-level C++ API and half on a high level Python API, and for this reason it can only be used using Python.

Standard watershed algorithm implemented in Cuda:

A basic implementation of the standard watershed algorithm without over-segmentation reduction implemented in Cuda with wrappers for Python as described here.

This implementation is based on this sources. The algorithm is implemented in Cuda but the samples are in Python. So in this prototype the execution is ported to C++/Cuda using optimization techniques such textures wich gives fast reads using a dedicated hardware and memory chached on chip, and techniques such constatnt and shared memory as well for fast reads.

Execution times of the 4 C++/Cuda implementations on 8 different images:

Profiling of the CUDA implementation using NSight profiler:

Only one of the five implementations is done in Cuda, and it is split in a few kernels as visible in the picture below.

It can also be seen that one method uses 98.5% of the total computation time, so this is a good starting point for further optimizations.

watershed_profiling

watershed profiling

Original image and generated segmented images:

Test image : watershed_test_0.jpg

watershed_test_0

watershed_test_0

watershed_out_0_Mamba_P_Algorithm

watershed_out_0_Mamba_P_Algorithm

watershed_out_0_OpenCv_Cpu_And_Markers

watershed_out_0_OpenCv_Cpu_And_Markers

watershed_out_0_OpenCv_Cpu_Markers_And_Histograms

watershed_out_0_OpenCv_Cpu_Markers_And_Histograms

watershed_out_0_Order_Variant_Watershed_Cuda

watershed_out_0_Order_Variant_Watershed_Cuda

Test image : watershed_test_1.jpg

watershed_test_1

watershed_test_1

watershed_out_1_Mamba_P_Algorithm

watershed_out_1_Mamba_P_Algorithm

watershed_out_1_OpenCv_Cpu_And_Markers

watershed_out_1_OpenCv_Cpu_And_Markers

watershed_out_1_OpenCv_Cpu_Markers_And_Histograms

watershed_out_1_OpenCv_Cpu_Markers_And_Histograms

 

watershed_out_1_Order_Variant_Watershed_Cuda

watershed_out_1_Order_Variant_Watershed_Cuda

Test image : watershed_test_2.jpg

watershed_test_2

watershed_test_2

watershed_out_2_Mamba_P_Algorithm

watershed_out_2_Mamba_P_Algorithm

watershed_out_2_OpenCv_Cpu_And_Markers

watershed_out_2_OpenCv_Cpu_And_Markers

watershed_out_2_OpenCv_Cpu_Markers_And_Histograms

watershed_out_2_OpenCv_Cpu_Markers_And_Histograms

watershed_out_2_Order_Variant_Watershed_Cuda

watershed_out_2_Order_Variant_Watershed_Cuda

Test image : watershed_test_3.jpg

watershed_test_3

watershed_test_3

watershed_out_3_Mamba_P_Algorithm

watershed_out_3_Mamba_P_Algorithm

watershed_out_3_OpenCv_Cpu_And_Markers

watershed_out_3_OpenCv_Cpu_And_Markers

watershed_out_3_OpenCv_Cpu_Markers_And_Histograms

watershed_out_3_OpenCv_Cpu_Markers_And_Histograms

watershed_out_3_Order_Variant_Watershed_Cuda

watershed_out_3_Order_Variant_Watershed_Cuda

Test image : watershed_test_4.jpg

watershed_test_4

watershed_test_4

watershed_out_4_Mamba_P_Algorithm

watershed_out_4_Mamba_P_Algorithm

watershed_out_4_OpenCv_Cpu_And_Markers

watershed_out_4_OpenCv_Cpu_And_Markers

watershed_out_4_OpenCv_Cpu_Markers_And_Histograms

watershed_out_4_OpenCv_Cpu_Markers_And_Histograms

watershed_out_4_Order_Variant_Watershed_Cuda

watershed_out_4_Order_Variant_Watershed_Cuda

Test image : watershed_test_5.jpg

watershed_test_5

watershed_test_5

watershed_out_5_Mamba_P_Algorithm

watershed_out_5_Mamba_P_Algorithm

watershed_out_5_OpenCv_Cpu_And_Markers

watershed_out_5_OpenCv_Cpu_And_Markers

watershed_out_5_OpenCv_Cpu_Markers_And_Histograms

watershed_out_5_OpenCv_Cpu_Markers_And_Histograms

watershed_out_5_Order_Variant_Watershed_Cuda

watershed_out_5_Order_Variant_Watershed_Cuda

Test image : watershed_test_8.jpg

watershed_test_8

watershed_test_8

watershed_out_8_Mamba_P_Algorithm

watershed_out_8_Mamba_P_Algorithm

watershed_out_8_OpenCv_Cpu_And_Markers

watershed_out_8_OpenCv_Cpu_And_Markers

watershed_out_8_OpenCv_Cpu_Markers_And_Histograms

watershed_out_8_OpenCv_Cpu_Markers_And_Histograms

watershed_out_8_Order_Variant_Watershed_Cuda

watershed_out_8_OpenCv_Cpu_Markers_And_Histograms

Conclusion:

All these implementations work OK with very simple images and with poor results for complex real-life images.

The standard Watershed implemented in Cuda has no over-segmentation reduction and returns the worst results. But it is a good starting point for developing an advanced algorithm which includes techniques such shape, surface and context analysis to reduce over-segmentation.

Sources:

https://bitbucket.org/coldvisionio/coldvision-library/src/97c769e70dbedf5e6bdd7a9f974e7608a1f9b4b8/samples/2_imaging/watershed/

Resources:

https://en.wikipedia.org/wiki/Image_segmentation

https://en.wikipedia.org/wiki/Watershed_(image_processing)

http://cmm.ensmp.fr/~beucher/wtshed.html

http://docs.opencv.org/3.1.0/d2/dbd/tutorial_distance_transform.html#gsc.tab=0

http://docs.opencv.org/3.1.0/d3/db4/tutorial_py_watershed.html#gsc.tab=0

http://www.codeproject.com/Articles/751744/Image-Segmentation-using-Unsupervised-Watershed-Al

http://cmm.ensmp.fr/~beucher/publi/P-Algorithm_SB_BM.pdf

http://cmm.ensmp.fr/~beucher/publi/Unified_Segmentation.pdf

https://github.com/nicolasBeucher/mamba-image

http://ieeexplore.ieee.org/xpl/articleDetails.jsp?tp=&arnumber=5639015

http://perso.esiee.fr/~najmanl/papers/couprie2009iccv.pdf

https://sourceforge.net/projects/powerwatershed/

https://github.com/louismullie/watershed-cuda

http://www.vision.cs.ucla.edu/papers/fulkersonS10really.pdf

http://www.nvidia.com/content/gtc/documents/1060_gtc09.pdf

https://www.researchgate.net/post/How_can_I_do_image_segmentation_in_GPU_using_CUDA

http://adessowiki.fee.unicamp.br/media/Attachments/courseIA366F2S2010/aula10/ijncr.pdf

http://vision.stanford.edu/projects/totalscene/

Leave a Reply

Your email address will not be published.