| Watershed (version 1.0, 2012-November-8) |
Watershed.py
Version: 1.0
Author: Avinash Kak (kak@purdue.edu)
Date: 2012-November-8
Download Version 1.0:
gztar
bztar
View version 1.0 code in browser
SWITCH TO VERSION 1.1
INTRODUCTION:
Over the years, the watershed algorithm has emerged as a powerful
approach to image segmentation. Image segmentation means to separate
the foreground --- meaning the objects of interest --- from the
background. This approach becomes even more powerful when you allow a
user to modify the image gradients prior to the application of the
watershed algorithm.
In the watershed algorithm, we think of the gradient image as a 3D
topographic relief map that consists of mountains where the gradient
values are high and valleys where they are low. The watersheds are the
ridge lines in this 3D map that delineate common basins for water
drainage. Note that the term watershed is also used to denote all of
the surface area where the water drains toward a common basin (or
valley). When thought of as in the latter definition, watershed area
would be delineated by the aforementioned ridge lines. In computer
vision algorithms, a watershed consists of the highest points that
delineate a surface area in which the water would drain to a common
valley. It is important to realize that the points on a watershed can
be at very different elevations; that is, the height above the ground
plane along a watershed can vary significantly. Think of the Great
Continental Divide as a watershed that divides the two American
continents, the North and the South, into two regions, one that drains
into the Pacific and the other that drains into the Atlantic. If you
were to walk along this Great Divide all the way from where it begins
in Alaska to its final point in Patagonia at the southern tip of Chile,
you will be at vastly different elevations above the sea level. If you
are on the Divide in Colorado, you are likely to find snow at several
places even in summer months. But if you follow the divide into
Arizona, at several places you'll be in the middle of what to the naked
eye would like a flat dessert.
These properties of the natural watersheds make the Watershed a
powerful paradigm for image segmentation. When you closely examine the
semantically meaningful regions in typical images, you are likely to
see a large variation in the gradient levels that separate the
foreground regions from the background regions. Obviously, the
strength of the gradient that separates the foreground and the
background is a function of the local gray levels in both the
foreground and the background in the vicinity of the border between
them. So, while you cannot attribute specific values to such
separating gradients, the gradients highlights are nonetheless real for
the most part since that's how the human eye sees the different regions
in an image.
That brings to the question of how to actually implement the watershed
paradigm for image segmentation. This module is based on what is known
as the "flooding model" of computations for extracting the watershed
from a gradient image when thought of as a 3D relief. The flooding
model is based on the idea that if we prick holes at the lowest points
in all of the valleys of a topographic relief representation of a
gradient image and gradually submerge the holed 3D structure in a pool
of water, the rising flood in one valley will meet the flood in another
valley at the watershed ridge points between the two valleys. Since
the watershed ridges can be at varying heights, in order to identify
the watershed points beyond the first such point, we immediately put up
a dam at the discovered watershed points so that the logic of watershed
identification can be maintained at all heights.
The flooding model that is implemented in this module is based on the
work of Beucher, Lantuejoul, and Meyer. A description of the algorithm
can be found in the following Google accessible report by S. Beucher:
"The Watershed Transformation Applied to Image Segmentation." We will
refer to this algorithm as the BLM algorithm in the rest of this
document.
The BLM algorithm uses morphological operators for simulating the
rising flood in the topographic relief map of the gradient image. The
most important morphological operations in this context are those of
dilations, distance mapping, calculation of the influence zones in a
binary blob with respect to marker sets, and the determination of
geodesic skeletons. These operators are applied to the Z level sets
derived from the gradient map. For a given level, the pixels that
belong to the Z set at that level are those whose gradient values are
less than or equal to the level. Flooding in the BLM algorithm is
simulated by computing the influence zones of the flooded pixels at one
Z level in all the pixels that belong to the next higher Z level.
COMPARISON WITH THE OpenCV WATERSHED IMPLEMENTATION:
If your main interest is in just the final output --- good-quality
watershed segmentations based on user-supplied seeds --- then this
Python module is not for you and you should use the OpenCV
implementation. With regard to the speed of execution, a pure Python
module such as this cannot hope to compete with the C-based
implementation in the OpenCV library.
But do bear in mind that the segmentation produced by the OpenCV
implementation is driven entirely by the user-supplied seeds. In fact,
the number of image segments produced by the OpenCV algorithm does not
exceed the number of seeds supplied by the user --- even when two
different seeds are placed in the same homogeneous region of the image.
On the other hand, this Python module will give you a watershed
segmentation even when you do not supply any seeds (or, marks, as I
refer to them in the implementation here). So you could say that the
user supplied marks (seeds) for this Python module are more for the
purpose of creating new valleys in the topographic relief representation
of the gradient map than for nucleating the formation of valleys for the
discovery of watersheds that must partition the image into a specific
number of segments.
INSTALLATION:
The Watershed module was packaged using Distutils. For installation,
execute the following command-line in the source directory (this is the
directory that contains the setup.py file after you have downloaded and
uncompressed the tar archive):
python setup.py install
You have to have root privileges for this to work. On Linux
distributions, this will install the module file at a location that
looks like
/usr/lib/python2.7/dist-packages/
If you do not have root access, you have the option of working directly
off the directory in which you downloaded the software by simply placing
the following statements at the top of your scripts that use the
Watershed class
import sys
sys.path.append( "pathname_to_Watershed_directory" )
To uninstall the module, simply delete the source directory, locate
where Watershed was installed with "locate Watershed" and delete those
files. As mentioned above, the full pathname to the installed version
is likely to look like /usr/lib/python2.7/dist-packages/Watershed*
If you want to carry out a non-standard install of Watershed, look up the
on-line information on Disutils by pointing your browser to
http://docs.python.org/dist/dist.html
USAGE:
To segment an image, you would first construct an instance of the
Watershed class and invoke the methods shown below on this instance:
from Watershed import *
shed = Watershed(
data_image = "orchid0001.jpg",
binary_or_gray_or_color = "color",
size_for_calculations = 128,
sigma = 1,
gradient_threshold_as_fraction = 0.1,
level_decimation_factor = 16,
debug = 0,
)
shed.extract_data_pixels()
shed.display_data_image()
shed.mark_image_regions_for_gradient_mods() #(A)
shed.compute_gradient_image()
shed.modify_gradients_with_marker_minima() #(B)
shed.compute_Z_level_sets_for_gradient_image()
shed.propagate_influence_zones_from_bottom_to_top_of_Z_levels()
shed.display_watershed()
shed.display_watershed_in_color()
shed.extract_watershed_contours()
shed.display_watershed_contours_in_color()
The statements in lines (A) and (B) are needed only for marker-assisted
segmentation with the module. For a fully automated implemented of the
BLM algorithm, you would need to delete those two statements.
If you just want to use this module for demonstrating basic
morphological operations of dilations and erosions, your script would
look like:
shed = Watershed(
data_image = "triangle1.jpg",
binary_or_gray_or_color = "binary",
)
shed.extract_data_pixels()
shed.display_data_image()
dilated_image = shed.dilate(5)
shed.erode(dilated_image, 5)
On the other hand, if you just wanted to use this module to demonstrate
distance mapping of a binary blob with respect to one or more marker
blobs, your code is likely to look like:
shed = Watershed(
data_image = "artpic3.jpg",
binary_or_gray_or_color = "binary",
debug = 0,
)
shed.extract_data_pixels()
shed.display_data_image()
shed.connected_components("data")
shed.mark_blobs()
shed.connected_components("marks")
shed.dilate_mark_in_its_blob(1)
Note that you must now make calls to "connected_components()" to
separate out the blobs in your input binary image, and to
"mark_blobs()" to let a user mark up a blob for distance mapping. It
is the last call shown above, to "dilate_mark_in_its_blob()" that
carries out distance mapping of the chosen blob with respect to the
mark. Note that this takes an integer argument that is supposed to be
integer index of the mark. If you placed only one mark in the blob,
this arg must be set to 1. On the other hand, if you placed, say, two
marks in a blob, then by supplying 2 for the argument you will see
distance mapping with respect to the other mark. So, what you supply
for the argument is an integer value between 1 and the number of marks
you created.
If you want to demonstrate the calculation of influence zones with this
module, replace the last statement in the example shown above with the
statement:
shed.compute_influence_zones_for_marks()
The module also includes two static methods that allow you to create
your own binary images for demonstrating the basic operations built
into the module. The syntax for calling these method looks like:
Watershed.gendata("triangle", (100,100), (10,10), 30, "new_triangle.jpg"
Watershed.make_binary_pic_art_nouveau("new_art_from_me")
The second call in particular allows you artsy looking binary blobs
just by rapidly moving your mouse over the window that is shown as you
keep your left mouse button pressed. Alternating clicks of the left
mouse button start and stop this process.
CONSTRUCTOR PARAMETERS:
data_image: The image you wish to segment as, say, a '.jpg' file
binary_or_gray_or_color: Must be set to either 'binary', or 'gray', or
'color', as the case may be. A binary image is
thresholded after it is loaded in to produce binary
pixels. And a color image is converted into a grayscale
image before the application of the watershed algorithm.
Ordinarily, you would want to use binary images just for
demonstrating the dilation, erosion, distance mapping,
IZ calculation, and geodesic skeleton calculation
capabilities of this module.
size_for_calculations: If the larger of the two image dimensions is
greater than this number, the image is reduced in size
so that its larger dimension corresponds to the number
supplied through this parameter. As you would expect,
the smaller this parameter, the faster your results.
The default for this parameter is 128.
sigma: Controls the size of the Gaussian kernel used for
smoothing the image before its gradient is calculated.
Assuming the pixel sampling interval to be unity, a
sigma of 1 gives you a 7x7 smoothing operator with
Gaussian weighting. The default for this parameter is
1.
gradient_threshold_as_fraction: This parameter when set allows the
system to ignore small gradients in the image. Note
that the gradient values are normalized to be between 0
and 255, both ends inclusive. The default for this
parameter is 0.1.
level_decimation_factor: This factor controls the number of levels of
the gradient that are subject to watershed calculations.
Recall that the image gradient is normalized to values
between 0 and 255. If you set level_decimation_factor
to 8, only every 8th gradient level will be considered
for the flooding calculations. That is, with
level_decimation_factor set to 8, you will have a total
of 32 levels of the gradient for the discovery of the
watersheds.
max_gradient_to_be_reached_as_fraction: This parameter is useful for
debugging purposes. When set to, say, 0.5, it will stop
the rising flood at half of the maximum value for image
gradient. So by setting this parameter to a small
value, you can carry out a more detailed examination of
the propagation of the influence zones from one level to
the next.
debug: When set to 1, the module dumps out a lot of information
that is useful for debugging. The default is 0.
PUBLIC METHODS:
(1) compute_LoG_image()
This method computes the Laplacian-of-Gaussian (LoG) of an image.
The LoG image is calculated as the difference of two
Gaussian-smoothed versions of the input image at two slightly
difference scales. The LoG itself is NOT used in watershed
calculations.
(2) compute_Z_level_sets_for_gradient_image()
This method computes the Z levels for the BLM watershed algorithm.
A pixel belongs to a specified Z level if the value of the image
gradient at the pixel is less than or equal to that level.
(3) connected_components(arg)
where 'arg' is the string "data" if you want to carry out
connected-components labeling of binary blobs. When the same
method is called for the binary marks created by mouse clicks, we
change the value of 'arg' to "marks". Obviously, the components
labeling logic works exactly the same in both cases. The only
differences are in how the labels are saved for bookkeeping
purposes.
(4) dilate(arg)
where the 'arg' would generally be a small integer denoting the
radius of a disk structuring element to be used for the purpose of
dilating the input pattern. NOTE: This method only makes sense
for binary input images, since it only carries out binary
dilations.
(5) dilate_mark_in_its_blob(1)
This is the method that demonstrations the distance mapping
notions used in this module. The module carries out a distance
transformation of the blob that the user clicked on and does so
with respect to the mark placed in the chosen blob when the left
button of the mouse was clicked in it.
(6) display_data_image():
It is always good to call this method after you have invoked
"extract_data_pixels()" just to confirm the output of the data
extraction step.
(7) display_watershed()
This method displays the watershed pixels against the image that
was actually used for the application of the watershed algorithm.
Even when the input image is in color, the image used for
calculations is a grayscale version of the input
image. Additionally, depending on the constructor parameter
'size_for_calculations', the image used for calculations may also
be of reduced size.
(8) display_watershed_contours_in_color()
The boundary contours for the segmented regions of the image are
displayed against the original image by this method.
(9) display_watershed_in_color()
This display method shows the watershed pixels in color against
the original image supplied to the module for segmentation.
(10) erode(arg)
where the 'arg' would generally be a small integer denoting the
radius of a disk structuring element to be used for the purpose of
eroding the input pattern. NOTE: This method only makes sense for
binary input images, since it only carries out binary erosions.
(11) extract_data_pixels():
This is the very first method you should call in all cases. This
loads your image into the module. If you declared your input image
to be binary (when your image is in, say, the Jpeg format, the
actual pixel values will in general not be binary), the loaded
image is binarized by thresholding it in the middle of the gray
scale range. If you declared your input image to be color, it is
first converted into grayscale for the calculation of the
watersheds. The image may also be reduced in size if that step is
dictated by the value you supplied for the constructor parameter
'size_for_calculations'. Depending on this parameter, an input
image declared to be gray will also be downsized.
(12) extract_watershed_contours()
This method extracts the watershed pixels as boundary contours
using an 8-connected boundary following algorithm.
(13) gendata(feature, size_tuple, location_tuple, rotation_angle, filename)
This is a static method of the Watershed class for the purpose of
generating binary images that can subsequently be used to
demonstrate basic morphological operations like dilation, erosion,
distance mapping, calculation of influence zones, calculation of
the geodesic skeletons, etc. The first argument, 'feature', must
be set to one of the following: 'line', 'triangle', 'rectangle',
and 'broken_rectangle'. The parameter 'size_tuple' is supposed to
be a tuple (m,n) for the size of the output image desired. The
parameter 'location_tuple' is supposed to be a tuple (x,y) of
pixel coordinates for specifying the position of the binary
pattern in your image with respect to the center of the image.
The parameter 'rotation_angle' is an integer value specifying the
number of degrees of clockwise rotation that should be applied to
the pattern with respect to the image coordinate frame. Finally,
the parameter 'filename' names the file in which the binary image
will be deposited.
(14) make_binary_pic_art_nouveau( filename )
This static method can be used to make "fun" binary images for
demonstrating distance mapping of binary blobs, calculation of
influence zones, etc. This method is taken from Chapter 13 of my
book "Scripting with Objects".
(15) mark_image_regions_for_gradient_mods()
For mark-based segmentation with the BLM watershed algorithm, this
method elicits mouse clicks from the user that demarcate polygonal
regions in the image where the gradient should be modified prior
to the flooding process. The mouse clicks must be supplied in a
clockwise fashion to demarcate the polygonal regions.
(16) modify_gradients_with_marker_minima()
For mark-based application of the Watershed algorithm, it is this
method that actually modifies the gradient image after a user has
defined the regions for that purpose through the mouse clicks
elicited by the mark_image_regions_for_gradient_mods() method. In
the current module, this modification simply consists of setting
the gradient values to zero in such regions.
(17) propagate_influence_zones_from_bottom_to_top_of_Z_levels()
This is the workhorse of the module for watershed based
segmentation of an image. As explained elsewhere in this
documentation, this method starts at the lowest Z level to
discover the lowest valleys in the topographic relief
representation of the image gradients. Subsequently, the notion
of a rising flood is simulated by calculating the influence zones
(IZ) of the flooded pixels for one Z level in all of the pixels
that belong to the next Z level. The geodesic skeletons formed by
the IZs lead to the discovery of the watershed pixels in a
gradient image.
THE EXAMPLES DIRECTORY:
See the Examples directory in the distribution for the different ways
in which you can use this module. If you just want to play with
dilate-erode methods of the module, execute the script
DilateErode.py
This script assumes a disk structuring element whose radius is supplied
as the integer argument to the methods 'dilate(arg)' and 'erode(arg)'.
As currently programmed, this script produces results on a binary image
called "triangle1.jpg". You can change the filename supplied through
the constructor parameter 'data_image' to compute the dilations and
erosions for any binary image of your choice. To demonstrate the
usefulness of these operations for "repairing" breaks in edges, execute
the script
EdgeRepair.py
If you want to play with the distance mapping code in the module, execute
the script:
DistanceMapping.py
This script will ask you to place a mark with a mouse click in one of
the blobs in your binary image. Subsequently, it will distance mapping
of the blob with respect to that mark. For a demonstration that
involves more complex blobs --- these being blobs with holes in them
--- execute the script
DistanceMapping2.py
For a demonstration of the calculation of the influence zones (IZ) in a
binary blob, execute the script
InfluenceZones.py
For a visually interesting demonstration of IZ calculation, you must
place at least two marks inside a blob. Each mark is dilated into its
IZ and the boundaries between the IZs constitute the geodesic skeleton
of the binary blob.
All of the scripts mentioned above run on binary image files. As a first
demonstration involving grayscale or color images, execute the script
LoG.py
that calculates the Laplacian-of-Gaussian of an image. The LoG is
calculated by taking a difference of two Gaussian-smoothed images with
two different values of sigma. The first Gaussian smoothed image is
calculated with the sigma as set in the constructor and the second with
a sigma that 20% larger.
To see watershed segmentation of an image that does not require any user
interaction, execute the script:
WatershedSegmentationWith_no_Marks.py
As you will notice, without any help from the user, the watershed algorithm
over-segments the image. For an example of the segmentation produced by
this script, for the following image
orchid0001.jpg
of an orchid, the script produced the segmentation shown in
_output_segmentation_for_orchid_with_no_marks.jpg
Now execute the following script
WatershedSegmentationWithMarks.py
that first elicits from the user a delineation of polygonal regions in
the image that should be subject to gradient modification. For the same
orchid image, the segmentation produced is shown in the following image
_output_segmentation_for_orchid_with_marks.jpg
The marks that were used for this segmentation are shown in
_composite_image_with_all_marks_orchid0001.jpg
The following three images show another example of watershed segmentation
without and with marks:
_output_segmentation_for_stacey_with_no_marks.jpg
_output_segmentation_for_stacey_with_marks.jpg
_composite_image_with_all_marks_stacey_in_peru.jpg
Finally, if you want to create your own binary images for some of the
scripts mentioned above, execute the script
DataGen.py
Do not forget to execute the script
cleanup.py
in the Examples directory after running the scripts mentioned above to
cleanup the intermediate images created by the scripts. Ordinarily,
the destructor of the class would take care of such cleanup. But
depending on how you exit the module, that may not always happen.
CAVEATS:
As mentioned earlier, this module is NOT meant for production work ---
meaning situations where the primary goal is just to get good-quality
segmentations quickly based solely on user-supplied seeds. For that
type of work, you should use the OpenCV implementation. Being pure
Python, this module is slow compared to the OpenCV implementation.
However, in my opinion, this module makes it easier to experiment with
different approaches for implementing the various steps that go into
the BLM algorithm for watershed segmentation of images.
BUGS:
Please notify the author if you encounter any bugs. When sending
email, please place the string 'Watershed' in the subject line to get
past the author's spam filter.
AUTHOR:
Avinash Kak, kak@purdue.edu
If you send email, please place the string "Watershed" in your
subject line to get past my spam filter.
COPYRIGHT:
Python Software Foundation License
Copyright 2012 Avinash Kak
| Imported Modules | ||||||
| ||||||
| Classes | ||||||||
|
| ||||||||
| Data | ||
| ACTIVE = 'active' ALL = 'all' ANCHOR = 'anchor' ARC = 'arc' BASELINE = 'baseline' BEVEL = 'bevel' BOTH = 'both' BOTTOM = 'bottom' BROWSE = 'browse' BUTT = 'butt' CASCADE = 'cascade' CENTER = 'center' CHAR = 'char' CHECKBUTTON = 'checkbutton' CHORD = 'chord' COMMAND = 'command' CURRENT = 'current' DISABLED = 'disabled' DOTBOX = 'dotbox' E = 'e' END = 'end' EW = 'ew' EXTENDED = 'extended' FALSE = 0 FIRST = 'first' FLAT = 'flat' GROOVE = 'groove' HIDDEN = 'hidden' HORIZONTAL = 'horizontal' INSERT = 'insert' INSIDE = 'inside' LAST = 'last' LEFT = 'left' MITER = 'miter' MOVETO = 'moveto' MULTIPLE = 'multiple' N = 'n' NE = 'ne' NO = 0 NONE = 'none' NORMAL = 'normal' NS = 'ns' NSEW = 'nsew' NUMERIC = 'numeric' NW = 'nw' OFF = 0 ON = 1 OUTSIDE = 'outside' PAGES = 'pages' PIESLICE = 'pieslice' PROJECTING = 'projecting' RADIOBUTTON = 'radiobutton' RAISED = 'raised' RIDGE = 'ridge' RIGHT = 'right' ROUND = 'round' S = 's' SCROLL = 'scroll' SE = 'se' SEL = 'sel' SEL_FIRST = 'sel.first' SEL_LAST = 'sel.last' SEPARATOR = 'separator' SINGLE = 'single' SOLID = 'solid' SUNKEN = 'sunken' SW = 'sw' TOP = 'top' TRUE = 1 UNDERLINE = 'underline' UNITS = 'units' VERTICAL = 'vertical' W = 'w' WORD = 'word' X = 'x' Y = 'y' YES = 1 __author__ = 'Avinash Kak (kak@purdue.edu)' __copyright__ = '(C) 2012 Avinash Kak. Python Software Foundation.' __date__ = '2012-November-8' __url__ = 'https://engineering.purdue.edu/kak/distWatershed/Watershed-1.0.html' __version__ = '1.0' __warningregistry__ = {('the sets module is deprecated', <type 'exceptions.DeprecationWarning'>, 640): True} | ||
| Author | ||
| Avinash Kak (kak@purdue.edu) | ||