GRASS GSoC 2012 Image Segmentation

From GRASS-Wiki
Revision as of 08:11, 10 July 2012 by Emomsen (talk | contribs) (Added ToDo list)

Jump to: navigation, search

(See also other GRASS GSoC 2012 projects)

Student Name: Eric Momsen
Organization: OSGeo - Open Source Geospatial Foundation
Title: Image Segmentation
Repository: AddOns, browse at: i.segment








Segmentation Methods

  • Boundary Based
    • optimal edge detector +
    • watershed +
  • Region Based
    • multilevel thresholding technique +
    • region growing +
    • mean-shift
    • watershed




Region Growing Variations


1. Growing


2. Growing and Merging



At this point, it seems both variations should be implemented.

Segmentation Considerations




Main Goal



  • General considerations
  • Input
    • optionally vector maps of existing features
      • centroids/points to be used as initial seeds
    • What segmentation algorithm to use
    • Parameters for that algorithm
  • Algorithm of segmentation
    • in GSoC implementation of only one algorithm
    • code should be structured to allow easy implementation of additional algorithms
  • Similarity measurement
  • Output
      • spectral attributes:
        • per spectral band: mean, min, max, skewness







Lower priority




Test Images





Project Plan


  • May 21: Start coding, 8 weeks until Midterm Evaluation
  • Week 1: Develop pseudocode to outline the work Report 1
  • Week 6: Validation
  • Week 7: Debugging
  • Improving the main algorithm
  • Adding control for what scale the segmentation is performed at
  • GUI
  • Adding a second image segmentation algorithm

Region Growing Algorithm



1. Input:

    • Similarity Threshold T(t)... as t increases, threshold for similarity is lower. SPRING used: T(t) = T(0) alpha^t   , where T(0) > 0, t =0,1,2... and alpha <1

2. Loop for t



    • Check Rk's neighbors.
    • Merge IF Ri is Rk's best neighbor
    • update segment values
    • next i


4. Force a merge of regions that are too small

ToDo List

The following list was developed at the "mid" point review, with about 1 month left. Rating system is 1: must do, 2: would be nice, 3: probably only will be finished if it is a quick task.


1: Implement the 8 neighbor option (currenly only the 4 pixel neighbors are considered).

1: Starting seed pixels for the segments

1: handle null cells in the optional boundary constraints raster.

2: Current input limit is 2 billion starting segments, constrained by "int" data type for segment ID. Consider long int, and/or dynamic allocation of different storage depending on what is needed. (MM: Unfortunately you are stuck with the largest integer type that a GRASS raster supports with is 32 bit integer. Internally you could use larger integer types, but then you can not save the results... EM: Hmm, if the segments are renumbered sequenctial at the end, it would be possible to then save them if the resulting number of segments is less then 2 billion... Does anyone want to segment a raster with more than 2 billion pixels? As a work around, larger maps could be processed, if a random selection of pixels are used as seeds... At a minimum, put this limitation in as error checking and the documents.)

2: Check input parameters for mean-shift and other segmentation algorithms, try to make input parameters "generic" so they could be used for any/other algorithms.

2: Add shape characteristics (smoothness, compactness) to the similarity measurement. Similar to eCognition "Multiresolution Segmentation". Check Baatz and Shape paper. Adds two input parameters (weight of radiometric to shape, and weight of compactness to smoothness.) (Maybe use the ratio of the number of edge cells to the total number of cells as a proxy for compactness, which could be easily obtained as a side-product when finding neighbors.)

2: Alternate similarity measurements (Manhattan, Malahanobis)

3: Adding a parameter to make it easier to merge smaller segments and harder to merge large segments. (Preliminary testing is not promising, low priority)

3: Estimating the threshold value. (at least add to docs) (1 to 5% of the max difference gave me (MM) subjectively good results.)

?: Adding control for what scale the segmentation is performed at. (EM: I'm not certain what is meant/needed for this, but I think it is a different concept from just using g.region.)


1: i.segment.stats (It should do more then just statistics... .evaluation .metrics .data Maybe i.segment.metrics?) (Will need to evaulate what is already available from other GRASS modules, what is easy, what is hard. Start from the specifications for what is desired.)

1: Providing updates to i.maxlik to ensure the segmentation output can be used as input for the existing classification functionality.

1: Integration/workflow for r.fuzzy.


2: Neighbor finding, keep a tree structure of found neighbor segments to reduce the number of neighbor pixels that the similarity function will be run on.

2: Search continuation. If Ri isn't Rk's best neighbor, then use Rk as the next Ri. (Skips one neighbor finding routine.)

3: neighbor finding: When checking for Rk's neighbors, account for already knowing Ri and skip those pixels.

?: change candidate flag to int (compare with pass number) to avoid resetting each time. (32x RAM requirement for the flag, is it worth it?)

?: RAM storage of the segment membership and the neighboring segments (calculate first the requirements, if this is even possible for reasonable (what size?) maps). (check what % of the processing time is spent finding neighbors.)


1: Put segment ID in SEG instead of RAM. (Possibly make this dependent on available RAM?)

1: User input for how much RAM can be used.

2: Consider putting the optional boundary constraints raster into RAM (dependent on available RAM).

2: Use "zero" for segment ID's of Null cells, discard the NULL flag. (Need to check speed impact with Seg ID in SEG storage.)

3: Check input map type(s), currently storing in DCELL sized SEG file, could reduce this dynamically depending on input map time. (Could only reduce to FCELL, since will be storing mean we can't use CELL. Might not be worth the added code complexity.)


1: Add error traps. (Certainly for memory allocation, Minimum number of non-NULL cells in the input bands?anything else?)

2: Make the output segment ID's sequential (currently they have what ID the "first" pixel in the segment had).

2: There are many small TODO scattered in the code. Resolve some easy questions to clean up the code.

2: Change G_percentage: estimate total number of passes expected from histogram and threshold. (If this isn't reliabe, maybe change to show 1% for each pass, i.e. % complete out of first 100 passes, then % complete out of next 100 passes, etc.)

3: GUI (to combine i.segment with the stats module)


How to choose parameters, what their impact is.

Typical workflow:

  • i.segment
  • i.segment.metrics and/or i.maxlik and/or r.fuzzy




TODO: complete references with links.






eCognition Reference Manual

