Watershed (version 2.0.1, 2016-June-10)

Watershed.py
 
Version: 2.0.1
   
Author: Avinash Kak (kak@purdue.edu)
 
Date: 2016-June-10
 
 
Download Version 2.0.1:  gztar   bztar

  		     Total number of downloads (all versions): 2220
     This count is automatically updated at every rotation of
     the weblogs (normally once every two to four days)
     Last updated: Mon May 6 06:01:01 EDT 2024
View version 2.0.1 code in browser  
 
 
 
SWITCH TO VERSION 2.0.2
CHANGES:
  Version 2.0.1
 
    With this version, you can now directly access the segmented blobs in
    your own code.  The previous versions only displayed the segmented
    image on your terminal screen.  This version also incorporates
    improvements in the implementation of the logic of watershed
    segmentation.
 
  Version 2.0
 
    This is a Python 3.x compliant version of the Watershed module.  This
    version should work with both Python 2.7 and Python 3.x.
 
  Version 1.1.2
 
    This version fixes the module packaging errors that had crept into the
    previous version.
 
  Version 1.1.1
 
    This version presents cleaned-up documentation.  The implementation
    code remains unchanged.
 
  Version 1.1
 
    This version 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 gradient 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 it is 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 class was packaged using setuptools.  For installation,
    execute the following command in the source directory (this is the
    directory that contains the setup.py file after you have downloaded and
    uncompressed the package):
 
            sudo python setup.py install
 
    and/or, for the case of Python3, 
 
            sudo python3 setup.py install
 
    On Linux distributions, this will install the module file at a location
    that looks like
 
             /usr/local/lib/python2.7/dist-packages/
 
    and, for the case of Python3, at a location that looks like
 
             /usr/local/lib/python3.4/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 the Watershed module 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/local/lib/python2.7/dist-packages/Watershed*
 
    If you want to carry out a non-standard install of the Watershed
    module, 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,
                   padding = 20,
               )
        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.extract_watershed_contours_with_random_sampling(30, 50)    #(C)
        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 implementation of
    the BLM algorithm, you would need to delete those two statements.
 
    The statement in line (C) can be replaced by
 
        shed.extract_watershed_contours_separated()
 
    for faster contour extraction.  However, if the different contours are
    expected to share pixels, you are likely to get superior results with
    the call shown in line (C) above.  Both contour extraction methods
    return a list of contours, with each contour a list of pixel
    coordinates.
 
    If you just want to use this module just 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 want 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 now you must 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 to create 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.
 
    padding: This parameter pads the input image with a band of zeros, the
                   width of the band being equal to the value of this
                   parameter.  You will get better results for the
                   watershed contours if you use this parameter.  The band
                   needs to be wide enough so that even after LoG
                   smoothing, the border pixels for the padded image are
                   still set to to zero.
 
 
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()
 
         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_all_segmented_blobs()
 
         This method creates a composite image consisting of rectangular
         cells.  Each segmented object is placed in a separate cell.
 
 
    (7)  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.
 
 
    (8)  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.
 
 
    (9)  display_watershed_contours_in_color()
 
         The boundary contours for the segmented regions of the image are
         displayed against the original image by this method.
 
         To write this result image as a jpeg file to the disk, click on
         the "save" and "exit" buttons at the bottom of the window --- as
         opposed to just closing the window.  You can subsequently display
         the image from the disk file by using, say, the 'display' function
         from the ImageMagick library.  You can create a hardcopy version
         of the result by sending the jpeg image to a printer.
 
 
    (10) display_watershed_in_color()
 
         This display method shows the watershed pixels in color against
         the original image supplied to the module for segmentation.
 
         To write this result image as a jpeg file to the disk, click on
         the "save" and "exit" buttons at the bottom of the window --- as
         opposed to just closing the window.  You can subsequently display
         the image from the disk file by using, say, the 'display' function
         from the ImageMagick library.  You can create a hardcopy version
         of the result by sending the jpeg image to a printer.
 
 
    (11) 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.
 
 
    (12) 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.
 
 
    (13) extract_rectangular_masked_segment_of_image(self, horiz_start, horiz_end, vert_start, vert_end)
 
         This method is useful for extracting a rectangular section from
         the data image supplied to the module.  Now how the parameters
         are laid out.  The first two parameters together specify the 
         width of the rectangle and the last two parameters together 
         the height.
 
 
    (14) extract_segmented_blobs_using_contours( min_length )
 
         This method uses the inside/outside logic at a point (based on the
         number of times a line through the point intersects the contour)
         in order to decide whether the point is inside a closed contour or
         outside it.  A contour must be longer than 'min_length' pixels in
         order to be considered for this logic. This method returns a list
         of lists, with each list in the latter being a list of all the
         pixels that are in a segmented blob.
 
 
    (15) extract_segmented_blobs_using_region_growing( num_of_segments, min_area )
 
         This method uses region growing to pull out the segmented blobs
         from the output of watershed segmentation.  All such segments
         whose area (in terms of the number of pixels) is less than the
         parameter 'min_area' are discarded.  Set the first parameter,
         'num_of_segments', to the number of segmented blobs you wish to
         extract from the image.  The value given to 'num_of_segments' sets
         a maximum for the number of segmented blobs the method will seek
         out from the watershed segmentation.  This method returns a list
         of lists, with each list in the latter being a list of all the
         pixels that are in a segmented blob.
 
 
    (16) extract_watershed_contours_with_random_sampling( how_many, min_len )
 
         This method extracts the watershed pixels as boundary contours
         using an 8-connected boundary following algorithm. Use this method
         if the different contours are expected to share pixels.  The
         parameter 'how_many' is the number of contours you'd like to
         extract and the parameter 'min_len' sets the smallest acceptable
         length for the contours.  You can use 'min_len' to reject small
         noise induced contours.  This method returns a list of contours,
         with each contour a list of pixel coordinates.
 
 
    (17) extract_watershed_contours_separated()
 
         This much faster method extracts the watershed pixels as boundary
         contours using an 8-connected boundary following algorithm. Use
         this method if all contours are disjoint.  Like the previous
         method, this method also returns a list of contours, with each
         contour a list of pixel coordinates.
 
 
    (18) gendata(feature, size_tuple, location_tuple, orientation_or_radius, filename)
 
         This static method is useful for generating simple binary patterns
         for checking the validity of the logic used for dilation, erosion,
         IZ calculation, geodesic skeleton calculation, etc.  The
         permissible values for the 'feature' parameter are: 'line',
         'triangle', 'rectangle', 'broken_rectangle', 'disk' and
         'twin_rect'.  The parameter 'size_tuple' is for the size of the
         output image desired.  The parameter 'position' is supposed to be
         a tuple (x,y) of pixel coordinates for specifying the position of
         the binary pattern in your image.  The parameter
         'orientation_or_radius' is an integer value specifying the number
         of degrees of rotation that should be applied to the pattern for a
         given 'feature' for the case of 'line', 'triangle', 'rectangle'
         and 'broken_rectangle'.  The same parameter for the case of
         'circle' means the radius of the disk. Finally, the parameter
         'filename' names the file in which the binary image will be
         deposited.  For the parameters that take tuple values, the first
         coordinate is along the horizontal direction pointing to the right
         and the second coordinate is along vertical direction pointing
         downwards.  The origin is at the upper left corner of your
         terminal screen.
 
 
    (19) 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".
 
 
    (20) 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.
 
 
    (21) 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.
 
 
    (22) 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
 
        dilate_erode.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
 
        edge_repair.py
 
    If you want to play with the distance mapping code in the module,
    execute the script:
    
        distance_mapping.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
 
        distance_mapping2.py
 
    For a demonstration of the calculation of the influence zones (IZ) in a
    binary blob, execute the script
 
        influence_zones.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 an automatic watershed segmentation that does NOT involve any
    user interaction, execute the script:
 
        segment_automatic_and_show_watershed.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
 
        automatic_output_segmentation_for_orchid.jpg
 
    To see the individual blobs extracted from your input image through the
    watershed contours, execute the following script:
 
        segment_automatic_and_use_contours_to_extract_blobs.py
 
    This script finds the blobs by using the logic that a pixel belongs to
    the region bounded by a contour if a line through the pixel intersects
    the contour an even number of times. For a totally different approach
    to blob extraction, you may wish to try the script:
 
        segment_automatic_and_use_region_growing_to_extract_blobs.py
 
    This script uses region-growing logic to pull out the individual blobs.
 
    That brings us to marker based watershed segmentation in which a user
    is asked to place marker points in an image in order to manually modify
    the gradient map. To see how this works, execute the script:
 
        segment_with_markers_and_show_watershed.py
 
    In order to interact with the module for this segmentation exercise,
    pay careful attention to the titles of the image frames that are
    displayed.  When it asks you to click on the "save" and then "exit"
    buttons that appear at the bottom of the image window, you must do
    exactly do that (as opposed to just closing the window).  To see
    all the markers I placed in the image in one of my own attempts at
    segmenting the orchid image, view the image file:
 
       composite_image_with_all_marks_orchid.jpg
 
    The watersheds produced by this marker-assisted segmentation can be
    seen in the output image:
 
       marker_assisted_segmentation_for_orchid.jpg
 
    To see the individual blobs extracted for the case of marker-based
    watershed segmentation, execute the following script:
 
        segment_with_markers_and_use_contours_to_extract_blobs.py
 
    As for the "automatic" version of this script, this script finds the
    blobs by using the logic that a pixel belongs to the region bounded by
    a contour if a line through the pixel intersects the contour an even
    number of times. For a totally different approach to blob extraction,
    you may wish to try the script:
 
        segment_with_markers_and_use_region_growing_to_extract_blobs.py
 
    This script uses region-growing logic to pull out the individual blobs.
 
    Finally, if you want to create your own binary images for some of the
    scripts mentioned above, execute the script
 
        data_gen.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:
 
    Avi Kak (kak@purdue.edu) recently completed his multi-year "Objects
    Trilogy" project.  See his web page at Purdue for what this project is
    all about.  If nothing else, you will get to enjoy Harry Potter all
    over again.
 
COPYRIGHT:
 
    Python Software Foundation License
 
    Copyright 2016 Avinash Kak
 
@endofdocs

 
Imported Modules
       
PIL.Image
PIL.ImageDraw
PIL.ImageTk
Tkinter
copy
functools
glob
math
numpy
os
random
signal
sys

 
Classes
       
__builtin__.object
Watershed

 
class Watershed(__builtin__.object)
     Methods defined here:
__del__(self)
__init__(self, *args, **kwargs)
compute_LoG_image(self)
This method computes the Laplacian-of-Gaussian (LoG) of an image. The LoG 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.
compute_Z_level_sets_for_gradient_image(self)
For any value of n between 0 and 255, both ends inclusive, a pixel is in the
set Z_n if the gradient value at that pixel is less than or equal to n.  Note
that the gradient values are normalized to be between 0 and 255.
compute_gradient_image(self)
The Watershed algorithm is applied to the gradient of the input image.  This
method computes the gradient image.  The gradient calculation is carried out
after the image is smoothed with a Gaussian kernel whose sigma is set in the
constructor.
compute_influence_zones_for_marks(self)
Calculates the influence zones in a binary blob with respect to the marks
placed inside the blob.  The method also identifies the pixels at the
geodesic skeleton formed by the influence zones.
connected_components(self, data_or_marks)
This method is the basic connected components algorithm in the Watershed
module.  Just for programming convenience related to the I/O from this
method, I have made a distinction between carrying out a connected-components
labeling of a binary image and doing the same for a binary pattern that
contains all of the marks made by the user.
dilate(self, structuring_element_rad, structuring_ele_shape)
This is to just demonstrate the basic idea of dilation of a binary pattern by
a disk structuring element whose radius is supplied as the first
argument. The precise shape of the structuring element, which can be either
"square" or "circular", is supplied through the second argument. This method
itself is NOT used in the watershed calculations.  For large binary patterns,
it would be more efficient to carry out the dilations only at the border
pixels.
dilate_mark_in_its_blob(self, mark_index)
This method illustrates distance mapping of a blob in a binary image with
respect to a mark created by clicking at a point within the blob.
displayImage(self, argimage, title='')
Displays the argument image.  The display stays on for the number of seconds
that is the first argument in the call to tk.after() divided by 1000.
displayImage2(self, argimage, title='')
Displays the argument image.  The display stays on until the user closes the
window.  If you want a display that automatically shuts off after a certain
number of seconds, use the previous method displayImage().
displayImage3(self, argimage, title='')
Displays the argument image in its actual size.  The display stays on until the 
user closes the window.  If you want a display that automatically shuts off after 
a certain number of seconds, use the method displayImage().
displayImage4(self, argimage, title='')
Displays the argument image in its actual size without imposing the constraint
that the larger dimension of the image be at most half the corresponding screen
dimension.
displayImage5(self, argimage, title='')
This does the same thing as displayImage4() except that it also provides for
"save" and "exit" buttons.  This method displays the argument image with more 
liberal sizing constraints than the previous methods.  This method is 
recommended for showing a composite of all the segmented objects, with each
object displayed separately.
display_all_segmented_blobs(self)
display_data_image(self)
This is just a convenience method for displaying the image that you want to
subject to watershed segmentation.
display_watershed(self)
Displays the watershed segmentation of the image in the grayscale mode.  That
is, the image shown is what the computations are carried out on --- a
grayscale version of the input image (assuming it was a color image).
display_watershed_contours_in_color(self)
Shows the watershed contours as extracted by the extract_watershed_contours()
method.
 
To write the result image as a jpeg file to the disk, click on the "save"
and "exit" buttons at the bottom of the window --- as opposed to just closing
the window.  You can subsequently display the image from the disk file by
using, say, the 'display' function from the ImageMagick library.  You can
create a hardcopy version of the result by sending the jpeg image to a
printer.
display_watershed_in_color(self)
Displays the watershed segmentation on top of the original color image
(assuming that the input image was a color image to begin with.)
 
To write this result image as a jpeg file to the disk, click on the "save"
and "exit" buttons at the bottom of the window --- as opposed to just closing
the window.  You can subsequently display the image from the disk file by
using, say, the 'display' function from the ImageMagick library.  You can
create a hardcopy version of the result by sending the jpeg image to a
printer.
erode(self, argimage, structuring_element_rad, structuring_ele_shape)
This is to just demonstrate the basic idea of erosion of a binary pattern by
a disk structuring element whose radius is supplied as the first argument.
The precise shape of the structuring element, which can be either "square" or
"circular", is supplied through the second argument. This method itself is
NOT used in the watershed calculations.
extract_data_pixels(self)
Gets the binary, grayscale, and color images ready for watershed processing.
If the images are too large, they are reduced to the size set by the
constructor.  Color images are converted into grayscale images.
extract_rectangular_masked_segment_of_image(self, horiz_start, horiz_end, vert_start, vert_end)
Keep in mind the following convention used in the PIL's Image class: the first
coordinate in the args supplied to the getpixel() and pupixel() methods is for
the horizontal axis (the x-axis, if you will) and the second coordinate for the
vertical axis (the y-axis).  On the other hand, in the args supplied to the
array and matrix processing functions, the first coordinate is for the row
index (meaning the vertical) and the second coordinate for the column index
(meaning the horizontal).  In what follows, I use the index 'i' with its
positive direction going down for the vertical coordinate and the index 'j'
with its positive direction going to the right as the horizontal coordinate. 
The origin is at the upper left corner of the image.
extract_segmented_blobs_using_contours(self, min_contour_length=50)
This method uses the inside/outside logic at a point (based on the number of times a
line through the point intersects the contour) in order to decide whether the point is
inside a closed contour or outside it.
extract_segmented_blobs_using_region_growing(self, num_of_segments, min_area=50)
This method uses region growing to extract segmented blobs.  We start at a pixel
and grow from there by incorporating other neighboring pixels recursive until we
hit a watershed ridge.
extract_watershed_contours_separated(self)
This method uses the border following algorithm to extract the watershed
contours from the final propagation of influences by the propagate_influences
method.
extract_watershed_contours_with_random_sampling(self, num_of_contours, min_length=20)
This method uses the border following algorithm to extract the watershed
contours from the final propagation of influences by the propagate_influences
method.
mark_blobs(self, purpose)
For demonstrations of distance mapping of a binary blob with respect to a
marker blob, this method allows a user to both select one or more blobs in a
binary image for the purpose of distance mapping and to also place marks on
the blobs.
mark_blobs2(self)
For demonstrations of distance mapping of a binary blob with respect to a
marker blob, this method allows a user to both select one or more blobs in a
binary image for the purpose of distance mapping and to also place marks on
the blobs.
mark_blobs_no_image_scale_change(self)
For demonstrations of distance mapping of a binary blob with respect to a
marker blob, this method allows a user to both select one or more blobs in a
binary image for the purpose of distance mapping and to also place marks on
the blobs.
mark_image_regions_for_gradient_mods(self)
For watershed segmentation that incorporates user-supplied modifications to
the image gradients, this method allows a user to demarcate through mouse
clicks polygonal regions where the gradient can be explicitly set to 0.  For
each region thus demarcated, the mouse clicks must be supplied in a clockwise
fashion.
modify_gradients_with_marker_minima(self)
After a user has demarcated the regions in which the image gradients can be
modified, this method carries out the gradient modifications.
propagate_influence_zones_from_bottom_to_top_of_Z_levels(self)
Basic to watershed computation is the calculation of influence zones of the
connected components for one Z level in the connected components in the next
Z level.  Note that we stop at one level below the max level at which Z sets
are known.  That is because the last IZ calculation consists of finding the
influence zones of the Z sets at the 'self.max_grad_level-1' level in the Z
sets at the 'self.max_grad_level' level.
Static methods defined here:
gendata(feature, imagesize, position, orientation_or_radius, output_image_name)
This method is useful for generating simple binary patterns for checking the
validity of the logic used for dilation, erosion, IZ calculation, geodesic
skeleton calculation, etc.  Note that the permissible values for the
'feature' parameter are: 'line', 'triangle', 'rectangle', 'broken_rectangle',
'disk' and 'twin_rect'.  The parameter 'imagesize' is supposed to be a tuple
(m,n) for the size of the output image desired.  The parameter 'position' is
supposed to be a tuple (x,y) of pixel coordinates for specifying the position
of the binary pattern in your image.  The parameter 'orientation_or_radius' is an
integer value specifying the number of degrees of rotation that should be
applied to the pattern for a given 'feature' for the case of 'line', 'triangle',
'rectangle' and 'broken_rectangle'.  The same parameter for the case of 'circle'
means the radius of the disk.  Note that the x coordinate is along the horizontal 
direction pointing  to the right and the y coordinate is along vertical direction 
pointing downwards.  The origin is at the upper left corner.
make_binary_pic_art_nouveau(under_what_name)
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".
Data descriptors defined here:
__dict__
dictionary for instance variables (if defined)
__weakref__
list of weak references to the object (if defined)
Data and other attributes defined here:
canvas = None
drawEnable = 0
region_mark_coords = {}
startX = 0
startY = 0

 
Functions
       
ctrl_c_handler(signum, frame)

 
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) 2016 Avinash Kak. Python Software Foundation.'
__date__ = '2016-June-10'
__url__ = 'https://engineering.purdue.edu/kak/distWatershed/Watershed-2.0.1.html'
__version__ = '2.0.1'

 
        __author__ = 'Avinash Kak (kak@purdue.edu)'
__copyright__ = '(C) 2016 Avinash Kak. Python Software Foundation.'
__date__ = '2016-June-10'
__url__ = 'https://engineering.purdue.edu/kak/distWatershed/Watershed-2.0.1.html'
__version__ = '2.0.1'
 
Author
        Avinash Kak (kak@purdue.edu)