| Watershed (version 1.1, 2013-August-2) |
Watershed.py
Version: 1.1
Author: Avinash Kak (kak@purdue.edu)
Date: 2013-August-2
Download Version 1.1:
gztar
bztar
Total number of downloads (all versions):
2203
weblogs (normally once every two to four days)
Last updated:
Sun Apr 21 06:04:02 EDT 2024
View version 1.1 code in browser
SWITCH TO VERSION 1.1.1
CHANGE LOG:
Version 1.1 fixes a bug in the dilate() and erode() methods of the module that
caused these methods to misbehave for non-square images. Version 1.1 also
includes improvements in the explanatory comments included in the scripts in the
Examples directory.
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 desert.
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 us 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 equals 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.
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(radius, shape)
where 'radius' 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. The parameter 'shape' must be set to either "square" or "circular"
to specify the shape of the structuring element. 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(radius, shape)
where 'radius' 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. The parameter 'shape' must be set to either "square" or "circular"
to specify the shape of the structuring element. NOTE: This method only
makes sense for binary input images, since it only carries out binary
dilations.
(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 and shape are
supplied as the arguments to the methods 'dilate(radius,shape)' and
'erode(radius,shape)'. 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 display a distance map 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
with respect to the marks placed in the 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 is 20% larger.
To see the watershed segmentation of an image that does NOT involve any user
interaction, execute the script:
WatershedSegmentationWith_no_Marks.py
As you will notice, when there is no 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 a watershed based 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 2013 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) 2013 Avinash Kak. Python Software Foundation.' __date__ = '2013-August-2' __url__ = 'https://engineering.purdue.edu/kak/distWatershed/Watershed-1.1.html' __version__ = '1.1' __warningregistry__ = {('the sets module is deprecated', <type 'exceptions.DeprecationWarning'>, 605): True} | ||
| Author | ||
| Avinash Kak (kak@purdue.edu) | ||