Watershed Transform

Watershed Transform

The watershed algorithm is an image segmentation algorithm that splits an image into areas of interests. It is described in the book of “digital image processing” by Gonzales and Woods as following:

“The concept of watershed is based on visualizing an image in three dimensions: two spatial coordinates versus gray levels. In such a “topographic” interpretation, we consider three types of points: (a) points belonging to a regional minimum; (b) points at which a drop of water, if placed at the location of any of those points, would fall with certainty to a single minimum; and (c) points at which water would be equally likely fall to more than one such minimum … The points satisfying condition (c) form crest lines on the topographic surface and are termed divide lines or watershed lines”

The goal of the algorithm is to find the watershed lines.

References:

1). IMAGE SEGMENTATION AND MATHEMATICAL MORPHOLOGY

2). The Watershed Transform: Definitions, Algorithms and Parallelization Strategies

3). Matlab implementation (watershed) (a sequential algorithm introduced by introduced
by F. Meyer):
MATLAB\R2008a\toolbox\images\images\private\watershed_meyer.cpp

4). Writing C Functions in MATLAB (MEX-Files)

5). Matlab acceleration using CUDA via the MEX file interface

Dithering

According to Wikipedia:

“Dithering is a technique used in computer graphics to create the illusion of color depth in images with a limited color palette (color quantization). In a dithered image, colors not available in the palette are approximated by a diffusion of colored pixels from within the available palette. The human eye perceives the diffusion as a mixture of the colors within it (see color vision). Dithering is analogous to the halftone technique used in printing. Dithered images, particularly those with relatively few colors, can often be distinguished by a characteristic graininess, or speckled appearance.”

References:

1). Floyd, R. W., and L. Steinberg, "An Adaptive Algorithm for Spatial Gray Scale," International Symposium Digest of Technical Papers, Society for Information Displays, 1975, p. 36.

2). Lim, Jae S., Two-Dimensional Signal and Image Processing, Englewood Cliffs, NJ, Prentice Hall, 1990, pp. 469-476.

3). Matlab implementation (dither):

MATLAB\R2008a\toolbox\images\images\private\ditherc.c (ditherc.m)

4). Optimal Parallel Error-Diffusion Dithering, Proceedings of the 1999 Electronic Imaging, SPIE, San Jose, CA, January, 1999.

Morphological Reconstruction

“Morphological reconstruction can be thought of conceptually as repeated dilations of an image, called the marker image, until the contour of the marker image fits under a second image, called the mask image. In morphological reconstruction, the peaks in the marker image "spread out," or dilate.” Link here.

1). Vincent, L., "Morphological Grayscale Reconstruction in Image Analysis: Applications and Efficient Algorithms," IEEE Transactions on Image Processing, Vol. 2, No. 2, April, 1993, pp. 176-201.

2). Improving performance of morphological reconstruction

3). Matlab implementation:

MATLAB\R2008a\toolbox\images\images\private\imreconstructmex.cpp

Demosaicing

A demosaicing algorithm is a digital image technique used to reconstruct a full color image from the incomplete color samples output from image sensors.

1). Matlab description and implementation:

http://www.mathworks.com/access/helpdesk/help/toolbox/images/demosaic.html

MATLAB\R2008a\toolbox\images\images\private\demosaicmex.cpp