GRASS-Wiki - User contributions [en]

User:Emomsen

2012-10-30T14:14:15Z

⚠️Emomsen: Created page with "GRASS user, first code contribution was [https://trac.osgeo.org/grass/browser/grass-addons/grass7/imagery/i.segment i.segment] for GSoC 2012."

GRASS user, first code contribution was [https://trac.osgeo.org/grass/browser/grass-addons/grass7/imagery/i.segment i.segment] for GSoC 2012.

PSC election 2012

2012-10-30T14:11:34Z

⚠️Emomsen: Added nomination for Moritz

=== List of nominees for the [[PSC]] election ===

'''Any community member is eligible to propose a new PSC member candidate.'''

To submit a PSC member nomination:
* Please confirm with the nominated person first.
* Please send an email to PSC mailing list - grass-psc@lists.osgeo.org (you should be subscribed) - and also feel free to cc: the nomination to the GRASS user list - grass-user@lists.osgeo.org - so that the community remains informed.
* Please add details below.
* Also, you might want to reference your Wiki profile here:

Deadline: [http://www.timeanddate.com/worldclock/fixedtime.html?year=2012&month=10&day=31&hour=12&min=0&sec=0 Wednesday, 31 October 2012, 12:00 UTC]

The list of nominees:

{| class="wikitable sortable" border="1" cellpadding="5"
|-
!Name
!Country
!Notes


|- valign="top"
|'''Candidate's name'''
|'''Country'''
|From: '''Your name (Nominator)'''

I'd like to nominate XXX

|- valign="top"
|''Martin Landa''
|''Czech Republic''
|From: ''[[User:Madi|Margherita Di Leo]]''

[http://lists.osgeo.org/pipermail/grass-psc/2012-October/000936.html]

|- valign="top"
|''Markus Metz''
|''Germany''
|From: ''[[User:lucadelu|Luca Delucchi]]''

[http://lists.osgeo.org/pipermail/grass-psc/2012-October/000937.html]

|- valign="top"
|''Margherita Di Leo''
|''Italy''
|From: ''[[User:Hellik|Helmut Kudrnovsky]]''

[http://lists.osgeo.org/pipermail/grass-user/2012-October/065859.html]

|- valign="top"
|''Moritz Lennert''
|''Belgium''
|From: ''[[User:Emomsen|Eric Momsen]]''

[http://lists.osgeo.org/pipermail/grass-psc/2012-October/000952.html]



[[Category:PSC]]

GRASS GSoC 2012 Image Segmentation

2012-08-20T15:13:43Z

⚠️Emomsen: /* ToDo List */ finalized list.

{{GSoC}}
''(See also other [[GRASS_SoC_Ideas_2012#Accepted_Ideas|GRASS GSoC 2012 projects]])''

{| {{table}}
|Student Name: || Eric Momsen
|-
|Organization: || [http://www.osgeo.org OSGeo - Open Source Geospatial Foundation]
|-
| Mentor Name: || Mentor: Markus Metz (backup mentors: M Lennert, P Roudier)
|-
| Title: || '''Image Segmentation'''
|-
|-
| Repository: || AddOns, browse at: [https://trac.osgeo.org/grass/browser/grass-addons/grass7/imagery/i.segment i.segment]
|-
|}
=Abstract=

GRASS GIS has many imagery related processing capabilities, but the field is rapidly developing and many techniques are not yet implemented. The goal of this GSoC project is to implement the region growing image segmentation algorithm.

Input: Raster map(s) to be segmented (plus optional vector map for a constraint)

Output: To include segmented regions with statistics. This information can be directly used or taken as input to existing image classification modules.

Update: This process will be split into two modules, the first will output a raster map with segments, the second will compute statistics for the segments.

=Background=

Image classification techniques already implemented in GRASS GIS include supervised and unsupervised classification. Classification of images based on pixels can often be very noisy. By first segmenting the image, later classification of 'objects' can be more effective. Noise is reduced, classification speed is increased, and most importantly the classification is performed on objects instead of pixels. The {{cmd|i.smap}} module does include a segmentation step (based on Gaussian mixture distribution), but there does not exist a module intended to segment the image and provide segment data for general use. A summary of the existing methods implemented in GRASS are at [[Image classification]]. Furthermore, the module {{AddonCmd|r.seg}} in GRASS-addons uses internally the Mumford-Shah variational model for image segmentation.

== Segmentation Methods ==

* Boundary Based
** optimal edge detector +
** watershed +
* Region Based
** multilevel thresholding technique +
** region growing +
* Combined boundary/region (is this a correct category for these two?)
** mean-shift
** watershed

Carleer et.al. [1] reviewed 4 methods (marked with + above). Boundary based methods are sensitive to noise and texture, and usually depend on good pre-processing. (Does GRASS already have this pre-processing/filtering?) Good results with urban zones, high contrast. Both region based methods had difficulty with transition zones. Region growing was less sensitive to texture (good for high resolution (1m) images). Multi-level techniques are the only way to get all objects without over-segmentation.

I don't recall the source, but I read in one place that mean-shift could be difficult to apply to very large images, and elsewhere it was mentioned watershed sees more use in greyscale images.

As additional algorithms are added to the module, attention should be given to diversify so algorithms with different strengths are implemented first.

=== Region Growing Variations ===

Even within the region growing label, there are a number of approaches. Here are two described in [5].

1. Growing

Seeds (as a subset of the pixels) are selected (using image histogram, previous knowledge, or other methods). Region growing is done by adding adjacent pixels. No merging of segments is done, only unassigned pixels can be assigned to adjacent regions.

2. Growing and Merging

Use all pixels as seeds, no need to have user figure out a reasonable starting seed selection. Now adjacent segments can be merged.

Is there ever a case where someone may want to start with seeds, but still allow segment merging? Or does that fall into the realm of classification to be done in the next step?

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

== Segmentation Considerations ==

All(?) methods have some input parameter(s) that can be set. These parameters influence if the algorithm will over-segment (one expected region is divided into 2 or more segments) or under-segment (putting two expected regions into one segment). If the segments are used for later classification, over-segmentation should usually get preference to under-segmentation. With extensive over-segmentation, some of the advantages provided by segmentation can be lost, but at least the classification can combine the segments into the expected region. Under-segmentation is more critical, as the classification step will not divide the segment to recover the different regions. (Based on a summary of a number of papers from [1])

In order to respond to the issue of over/under-segmentation, a multiscalar approach would be interesting. This would mean either a top-down approach with a first coarse segmentation (under-segmentation) and the finer segmentation in selected segments, or a bottom-up approach with first a very fine-grained segmentation (over-segmentation) and the regrouping of segments to form higher levels. The first approach can be solved by doing a first segmentation, using certain segments as masks and then relaunching a second segmentation. {Or by using a vector map of the first segmentation as a boundary constraint in the second segmentation.} The second approach requires an algorithm to decide which segments should be combined in a larger higher-level segments. A simple nearest neighbor or kmeans approach based on spectral mean can be used here. In terms of implementation in GRASS, this would probably call for several modules, one for the segmentation, and another for grouping of segments. The latter could be an all-purpose clustering module (and can also be emulated by simple data analysis in the attribute table + {{cmd|v.dissolve}}).

It can sometimes be interesting to do a first segmentation on one band (e.g. panchromatic with higher resolution) and then regroup segments based on multispectral data (possibly weighting bands).

=Main Goal=

Implement an image segmentation method to extend the available options for image processing in GRASS. The region growing method has been selected as a robust general purpose method. An important contribution of the new method will be to include vector maps (for example road networks) as a constraint in growing the segments. Output from the module will include Spectral (mean/variance/range/ect) and Spatial (area/shape/location/etc) data for each region.

=Specifications=

* General considerations
** The general principle in GRASS is KISS, with each module doing one thing. It is to be seen if the result of this project is one single module or rather more than one module each specialised in one task in a segmentation workflow.
** As soon as code is to be (potentially) used in several modules, the use of a library should be envisaged.
** Be able to process large images while being considerate of system memory
* Input
** in the GRASS logic, input should be an image group, <del>or even image subgroup</del>, which can contain any number of raster maps, but generally satellite or areal images that are pre-processed and ready for analysis (i.e. no pre-processing in the module) (Update: subgroups are not often used, there use will not be implemented unless someone asks.)
*** This input group will define the feature space which can include spectral and other continuous (elevation, PCA layers, slope aspect...) and possibly (probably not initially) even discrete data (soil type, land cover...)
*** Default action will be to normalize/scale all input rasters to a 0-1 range. The allows bands (0-255), NDVI, and other numbers to be compared on an equal basis in the distance formula without any preprocessing steps. Since it gives equal weights to all rasters in the input group, a flag will give the user the option to skip this normalization step in case they want to use the actual values.
** optionally vector maps of existing features
*** lines (be it linear features or boundary lines of polygons) should be used as constraints meaning that no segment boundary should cross such a line
*** 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
** multi-scalar segmentation can significantly improve results and should thus be implemented if possible (see i.smap code for example)
* Similarity measurement
** The squared euclidean distance will be the default similarity measurement. If time allows, Manhattan distance will be added as an option. (Using the square will give same results, we will also square the similarity threshold so the user doesn't need to worry about this detail.
** For the default scaling of the input, the similarity threshold will be 0 to 1. This should be a good intuitive range for the user, 0 being the entire image is one segment and 1 being no segments can be formed. (Internally, this number must be multiplied by the number of rasters in the image group, but again the user doesn't need to worry about the details.) If the user selects the option to skip the normalization function, they will need to be careful how to select this parameter.
* Output
** first (segmentation) module: raster map of segments (i.e. each pixel value represents id of segment the pixel belongs to)
** second (stats) module: one vector map of segments per hierarchy level with a series of attributes (not all of these attributes should probably be calculated directly be the segmentation module)
*** spectral attributes:
**** per spectral band: mean, min, max, skewness
**** combination of bands: brightness, indices (i.e. results of multi-band calculations)
*** textural attributes: stdev (per-band and/or multi-band), mean difference to neighbor, Haralick texture features cf {{cmd|r.texture}}
*** geometric/morphological attributes: area, perimeter, length/width measures, see also {{cmd|r.li}}
*** context attributes: mean difference to all other regions in the same upper hierarchical level, relative localisation within upper hierarchical level, absolute localisation, number of objects in lower level
** depending on segmentation algorithm: raster map indicating for each pixel the probability of belonging to the segment it was put into, i.e. some measure of reliability of results

=== Questions ===

Number of modules: Should the user run one module to create the segments (raster output), then if they are interested, run r.to.vect and run a second module (vector input/output) if they want to get the statistics. (GUI glue to put them in one screen would be a low priority task for time remaining at the end of the summer.) (I wonder if the stats module should take vector or raster as the input, it will also need the original raster.)

"Probability of belonging to the segment": For region growing - should this be the similarity measure when it was merged? Or similarity measure of the pixel compared to the average?
/*ML: Not sure, but I would think that similarity between pixel and average of region it belongs to might be a good choice. Am not a specialist in statistics, but maybe it is possible to translate this into some form of probability of really "belonging" to that region (cf i.maxlik)*/
So this would be a comparison of the pixel to the final segment. Does anyone have a standard measurement that should be used?

4 vs. 8 neighbors: Should this be a user input option? It seems 4 neighbors (no diagonals) is the normal definition for segmentation, but not for other GRASS modules. Update: Using 4 neighbors as default, with optional flag to select 8 neighbors.

Null cells: Is it possible for some pixels inside the image to have null values? If yes, should they just be excluded from the calculation, or merged into the nearest segment? Update: current plan is to ignore all NULL values in the calculations.

Are there any examples of using linear features to constraint segment growth, or will it usually be polygons?

=== Lower priority ===

Add shape characteristics (smoothness, compactness) to the similarity measurement. Similar to eCognition "Multiresolution Segmentation"

It may be useful to do some calculations for the color space (RGB, HSI, L*u*v*, L*a*b*)? (I saw one paper [3] discussing pro/con of different systems, "best" answer is application dependent.)

ML: I would say leave decisions on color space (which is just one portion of feature space) to the user: one can group any kind raster maps with i.group and submit that to segmentation, and so the user can decide whether to use an image represented by different bands in a specific color space, plus any kind of other bands, indices, etc.

= Test Images =

The results of the implemented algorithm should be compared against the results of a similar algorithm implement in other software. The North Carolina GRASS sample location will be used for documentation and manuals.

Carleer [1] used images with 1m resolution from Ikonos, panchromatic band from 08 June 2000, Brussels area.

Should check segmentation results on images from a few different resolutions and different numbers of bands against what is obtained in other software.

Is there a benchmark for processing speed that should be considered? [4]

=Project Plan=

Preparation: Gather ideas from the community! Feature requests, image segmentation literature, and any other ideas and suggestions.

* May 21: Start coding, 8 weeks until Midterm Evaluation
* Week 1: Develop pseudocode to outline the work [http://lists.osgeo.org/pipermail/soc/2012-May/001747.html Report 1]
* Week 2-4: Implement the main algorithm [http://lists.osgeo.org/pipermail/soc/2012-June/001779.html Report 2] [http://lists.osgeo.org/pipermail/soc/2012-June/001804.html Report 3] [http://lists.osgeo.org/pipermail/soc/2012-June/001826.html Report 4]
* Week 5: Add vector maps as a constraint to the segmentation [http://lists.osgeo.org/pipermail/soc/2012-June/001854.html Report 5]
* Week 6: Validation [http://lists.osgeo.org/pipermail/soc/2012-June/001879.html Report 6]
* Week 7: Debugging [http://lists.osgeo.org/pipermail/soc/2012-July/001898.html Report 7]
* Week 8: Contingency time for finishing the above, ensure a solid main program. [http://lists.osgeo.org/pipermail/soc/2012-July/001921.html Report 8]
* July 9: Midterm Evaluation: Evaluate the existing program, determine the plan for the remaining 3-4 weeks. Options include:
* Improving the main algorithm
* Adding control for what scale the segmentation is performed at
* Providing updates to {{cmd|i.maxlik}} to ensure the segmentation output can be used as input for the existing classification functionality
* GUI
* Adding a second image segmentation algorithm

[http://lists.osgeo.org/pipermail/soc/2012-July/001941.html Report 9], [http://lists.osgeo.org/pipermail/soc/2012-July/001960.html Report 10], [http://lists.osgeo.org/pipermail/soc/2012-August/001986.html Report 11], [http://lists.osgeo.org/pipermail/soc/2012-August/002002.html Report 12], [http://lists.osgeo.org/pipermail/soc/2012-August/002041.html Report 13]

= Region Growing Algorithm =

Here is (a start!) for the processing steps, based on SPRING [2]

Region Growing, bottom up processing. Main improvement compared to simple algorithm is to slowly lower the similarity function, so only best matches are made first. This prevents the "first" segment from taking over any unclear areas between it and the next clear segment.

1. Input:
** Seeds: all pixels (Later addition can be alternate seeding methods)
** Similarity Threshold T(t)... as t increases, threshold for similarity is lower. SPRING used: <math>T(t) = T(0) alpha^t </math>, where T(0) > 0, t =0,1,2... and alpha <1
** Size of smallest allowed area (Is this wanted or needed ???)
2. Loop for t
** initialize candidate regions, save mean value vector and neighboring regions (Not sure why this needs to be calculated/saved ahead of time ??)
3. For each region i in candidate region set (first pass this equals the seeds):
** Compare Ri with neighbors (Question: should neighbors include or exclude those regions that were already matched?
** If it exists, Rk is best neighbor if smallest D of all neighbors and and D < T.
** Check Rk's neighbors.
** Merge IF Ri is Rk's best neighbor
** remove from candidate region set. (give all "small" regions a chance to merge with best neighbor before growing larger regions)
** update segment values
** next i
3. next t, with all segments returned to candidate region set, until no regions can be merged

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.

The list has been updated for the status at the end of GSoC 2012. Remaining items to be developed later are added to the TODO manual section. Further progress and new features requests will not be added to this listing.

== Functionality ==

<del>1: Implement the 8 neighbor option (currenly only the 4 pixel neighbors are considered).</del> (done)

<del>1: Starting seed pixels for the segments</del> (done)

<del>1: handle null cells in the optional boundary constraints raster.</del> (done)

<del>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.)</del> (documented limitation)

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 (<del>Manhattan</del>, Malahanobis) (Added Manhattan distance)

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.)

== Statistics/metrics ==

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.

== Speed ==

<del>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.</del> implemented, ~20% speed reduction

<del>2: Search continuation. If Ri isn't Rk's best neighbor, then use Rk as the next Ri. (Skips one neighbor finding routine.)</del> TODO: need to decide if this should stay in or out, or as an option. Currently implemented as an option. Need to do some speed tests to see if it is faster or slower after finishing some other changes.

<del>2: Consider peano or other ordering for pixel processing (instead of row major order), should help processing time if an entire "row" of segments are not in RAM.</del> implemented. No significant time change on the small maps it was tested on. Probably this will be helpful if disk I/O becomes limiting.

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

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

?: 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.)

== Memory ==

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

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

<del>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.)</del> Decided not to do this.

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.)

<del>3: Put segment ID in SEG instead of RAM. (Possibly make this dependent on available RAM?) (Only consider if we run into RAM limitations.)</del> Implemented

== Polish ==

<del>1: Add error traps. (Certainly for memory allocation, Minimum number of non-NULL cells in the input bands?anything else?)</del> Added some additional checks.

<del>2: Make the output segment ID's sequential (currently they have what ID the "first" pixel in the segment had).</del> Decided not to do this.

<del>2: There are many small TODO scattered in the code. Resolve some easy questions to clean up the code.</del> Resolved most. Some are left as enhancement suggestions for later.

<del>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.)</del> Using % complete of the input number of passes threshold.

<del>3: GUI (to combine i.segment with the stats module)</del> Wait until there is user demand for this.

== Documentation ==

How to choose parameters, what their impact is.

Typical workflow:

* {{cmd|i.group}}
* i.segment
* {{cmd|r.to.vect}}
* i.segment.metrics and/or {{cmd|i.maxlik}} and/or {{AddonCmd|r.fuzzy}}

= Workflow =

Todo: Some typical workflow examples, type of data, GRASS modules used before and after the image segmentation.

= Results =

== Ortho-photo ==

The [http://grass.osgeo.org/wiki/where_are_these_data link to ortho data is missing] has 3 bands, and the computational region is 1,120,080 cells, at 1-m resolution.

Here's the code used to generate this segmentation result:

i.segment group=ortho output=ortho_segs_ha threshold=0.02 endt=10000 final_mean=ortho_segs_mean_ha min=20 --o

The segmentation performed in 22m53.255s on a Intel i5 laptop with 4Go RAM. The memory consumption was around 38 Mo.

[[File:Raglan_ortho_seg.png]]

== SPOT5 scene ==

The [http://grass.osgeo.org/wiki/where_are_these_data link to SPOT data is missing] has 4 bands, and the computational region is 4,444,517 cells, at 10-m resolution.

Here's the code used to generate this segmentation result:

i.segment group=spot output=spot_seg threshold=0.01 endt=10000 min=30 --o

The segmentation performed in 87m3.870s on a Intel Core 2 workstation with 8Go RAM. The memory consumption was around 170 Mo.

[[File:Taranaki spot seg.png]]

= References =

TODO: complete references with links.

[http://www.armurs.ulb.ac.be/images/8/86/PERS_Carleer_05.pdf] Carleer, et al: Assessment of Very High Spatial Resolution Satellite Image Segmentations, 2005 (Evaluates 2 boundary and 2 region based algorithms.)

[http://marte.dpi.inpe.br/col/sid.inpe.br/deise/1999/02.05.09.30/doc/T205.pdf] Bins, et al: Satellite Imagery Segmentation: A Region Growing Approach, 1996 (Describes approach taken in SPRING software.)

[http://www.sciencedirect.com/science/article/pii/S0031320300001497] Cheng et. al.: Color image segmentation: advances and prospect, 2000 (survey of segmentation methods and color spaces)

[http://www.isprs.org/proceedings/XXXV/congress/comm4/papers/506.pdf] G. Meinel, M. Neubert: A Comparison of Segmentation Programs for High Resolution Remote Sensing Data, 20?? (Includes timing to complete segmentation)

[http://www.wiley.com/WileyCDA/WileyTitle/productCd-0471377392.html?0471377392=] Pitas, I: Digital Image Processing Algorithms and Applications, 2000 (Textbook, including 1 chapter on segmentation methods.)

eCognition Reference Manual

Kurtz et. al: Hierarchical Segmentation of Multiresolution Remote Sensing Images, 2011

Comaniciu, Dorin: Mean Shift: A Robust Approach Toward Feature Space Analysis, 2002

GRASS GSoC 2012 Image Segmentation

2012-08-20T15:11:48Z

⚠️Emomsen: /* Polish */

{{GSoC}}
''(See also other [[GRASS_SoC_Ideas_2012#Accepted_Ideas|GRASS GSoC 2012 projects]])''

{| {{table}}
|Student Name: || Eric Momsen
|-
|Organization: || [http://www.osgeo.org OSGeo - Open Source Geospatial Foundation]
|-
| Mentor Name: || Mentor: Markus Metz (backup mentors: M Lennert, P Roudier)
|-
| Title: || '''Image Segmentation'''
|-
|-
| Repository: || AddOns, browse at: [https://trac.osgeo.org/grass/browser/grass-addons/grass7/imagery/i.segment i.segment]
|-
|}
=Abstract=

GRASS GIS has many imagery related processing capabilities, but the field is rapidly developing and many techniques are not yet implemented. The goal of this GSoC project is to implement the region growing image segmentation algorithm.

Input: Raster map(s) to be segmented (plus optional vector map for a constraint)

Output: To include segmented regions with statistics. This information can be directly used or taken as input to existing image classification modules.

Update: This process will be split into two modules, the first will output a raster map with segments, the second will compute statistics for the segments.

=Background=

Image classification techniques already implemented in GRASS GIS include supervised and unsupervised classification. Classification of images based on pixels can often be very noisy. By first segmenting the image, later classification of 'objects' can be more effective. Noise is reduced, classification speed is increased, and most importantly the classification is performed on objects instead of pixels. The {{cmd|i.smap}} module does include a segmentation step (based on Gaussian mixture distribution), but there does not exist a module intended to segment the image and provide segment data for general use. A summary of the existing methods implemented in GRASS are at [[Image classification]]. Furthermore, the module {{AddonCmd|r.seg}} in GRASS-addons uses internally the Mumford-Shah variational model for image segmentation.

== Segmentation Methods ==

* Boundary Based
** optimal edge detector +
** watershed +
* Region Based
** multilevel thresholding technique +
** region growing +
* Combined boundary/region (is this a correct category for these two?)
** mean-shift
** watershed

Carleer et.al. [1] reviewed 4 methods (marked with + above). Boundary based methods are sensitive to noise and texture, and usually depend on good pre-processing. (Does GRASS already have this pre-processing/filtering?) Good results with urban zones, high contrast. Both region based methods had difficulty with transition zones. Region growing was less sensitive to texture (good for high resolution (1m) images). Multi-level techniques are the only way to get all objects without over-segmentation.

I don't recall the source, but I read in one place that mean-shift could be difficult to apply to very large images, and elsewhere it was mentioned watershed sees more use in greyscale images.

As additional algorithms are added to the module, attention should be given to diversify so algorithms with different strengths are implemented first.

=== Region Growing Variations ===

Even within the region growing label, there are a number of approaches. Here are two described in [5].

1. Growing

Seeds (as a subset of the pixels) are selected (using image histogram, previous knowledge, or other methods). Region growing is done by adding adjacent pixels. No merging of segments is done, only unassigned pixels can be assigned to adjacent regions.

2. Growing and Merging

Use all pixels as seeds, no need to have user figure out a reasonable starting seed selection. Now adjacent segments can be merged.

Is there ever a case where someone may want to start with seeds, but still allow segment merging? Or does that fall into the realm of classification to be done in the next step?

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

== Segmentation Considerations ==

All(?) methods have some input parameter(s) that can be set. These parameters influence if the algorithm will over-segment (one expected region is divided into 2 or more segments) or under-segment (putting two expected regions into one segment). If the segments are used for later classification, over-segmentation should usually get preference to under-segmentation. With extensive over-segmentation, some of the advantages provided by segmentation can be lost, but at least the classification can combine the segments into the expected region. Under-segmentation is more critical, as the classification step will not divide the segment to recover the different regions. (Based on a summary of a number of papers from [1])

In order to respond to the issue of over/under-segmentation, a multiscalar approach would be interesting. This would mean either a top-down approach with a first coarse segmentation (under-segmentation) and the finer segmentation in selected segments, or a bottom-up approach with first a very fine-grained segmentation (over-segmentation) and the regrouping of segments to form higher levels. The first approach can be solved by doing a first segmentation, using certain segments as masks and then relaunching a second segmentation. {Or by using a vector map of the first segmentation as a boundary constraint in the second segmentation.} The second approach requires an algorithm to decide which segments should be combined in a larger higher-level segments. A simple nearest neighbor or kmeans approach based on spectral mean can be used here. In terms of implementation in GRASS, this would probably call for several modules, one for the segmentation, and another for grouping of segments. The latter could be an all-purpose clustering module (and can also be emulated by simple data analysis in the attribute table + {{cmd|v.dissolve}}).

It can sometimes be interesting to do a first segmentation on one band (e.g. panchromatic with higher resolution) and then regroup segments based on multispectral data (possibly weighting bands).

=Main Goal=

Implement an image segmentation method to extend the available options for image processing in GRASS. The region growing method has been selected as a robust general purpose method. An important contribution of the new method will be to include vector maps (for example road networks) as a constraint in growing the segments. Output from the module will include Spectral (mean/variance/range/ect) and Spatial (area/shape/location/etc) data for each region.

=Specifications=

* General considerations
** The general principle in GRASS is KISS, with each module doing one thing. It is to be seen if the result of this project is one single module or rather more than one module each specialised in one task in a segmentation workflow.
** As soon as code is to be (potentially) used in several modules, the use of a library should be envisaged.
** Be able to process large images while being considerate of system memory
* Input
** in the GRASS logic, input should be an image group, <del>or even image subgroup</del>, which can contain any number of raster maps, but generally satellite or areal images that are pre-processed and ready for analysis (i.e. no pre-processing in the module) (Update: subgroups are not often used, there use will not be implemented unless someone asks.)
*** This input group will define the feature space which can include spectral and other continuous (elevation, PCA layers, slope aspect...) and possibly (probably not initially) even discrete data (soil type, land cover...)
*** Default action will be to normalize/scale all input rasters to a 0-1 range. The allows bands (0-255), NDVI, and other numbers to be compared on an equal basis in the distance formula without any preprocessing steps. Since it gives equal weights to all rasters in the input group, a flag will give the user the option to skip this normalization step in case they want to use the actual values.
** optionally vector maps of existing features
*** lines (be it linear features or boundary lines of polygons) should be used as constraints meaning that no segment boundary should cross such a line
*** 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
** multi-scalar segmentation can significantly improve results and should thus be implemented if possible (see i.smap code for example)
* Similarity measurement
** The squared euclidean distance will be the default similarity measurement. If time allows, Manhattan distance will be added as an option. (Using the square will give same results, we will also square the similarity threshold so the user doesn't need to worry about this detail.
** For the default scaling of the input, the similarity threshold will be 0 to 1. This should be a good intuitive range for the user, 0 being the entire image is one segment and 1 being no segments can be formed. (Internally, this number must be multiplied by the number of rasters in the image group, but again the user doesn't need to worry about the details.) If the user selects the option to skip the normalization function, they will need to be careful how to select this parameter.
* Output
** first (segmentation) module: raster map of segments (i.e. each pixel value represents id of segment the pixel belongs to)
** second (stats) module: one vector map of segments per hierarchy level with a series of attributes (not all of these attributes should probably be calculated directly be the segmentation module)
*** spectral attributes:
**** per spectral band: mean, min, max, skewness
**** combination of bands: brightness, indices (i.e. results of multi-band calculations)
*** textural attributes: stdev (per-band and/or multi-band), mean difference to neighbor, Haralick texture features cf {{cmd|r.texture}}
*** geometric/morphological attributes: area, perimeter, length/width measures, see also {{cmd|r.li}}
*** context attributes: mean difference to all other regions in the same upper hierarchical level, relative localisation within upper hierarchical level, absolute localisation, number of objects in lower level
** depending on segmentation algorithm: raster map indicating for each pixel the probability of belonging to the segment it was put into, i.e. some measure of reliability of results

=== Questions ===

Number of modules: Should the user run one module to create the segments (raster output), then if they are interested, run r.to.vect and run a second module (vector input/output) if they want to get the statistics. (GUI glue to put them in one screen would be a low priority task for time remaining at the end of the summer.) (I wonder if the stats module should take vector or raster as the input, it will also need the original raster.)

"Probability of belonging to the segment": For region growing - should this be the similarity measure when it was merged? Or similarity measure of the pixel compared to the average?
/*ML: Not sure, but I would think that similarity between pixel and average of region it belongs to might be a good choice. Am not a specialist in statistics, but maybe it is possible to translate this into some form of probability of really "belonging" to that region (cf i.maxlik)*/
So this would be a comparison of the pixel to the final segment. Does anyone have a standard measurement that should be used?

4 vs. 8 neighbors: Should this be a user input option? It seems 4 neighbors (no diagonals) is the normal definition for segmentation, but not for other GRASS modules. Update: Using 4 neighbors as default, with optional flag to select 8 neighbors.

Null cells: Is it possible for some pixels inside the image to have null values? If yes, should they just be excluded from the calculation, or merged into the nearest segment? Update: current plan is to ignore all NULL values in the calculations.

Are there any examples of using linear features to constraint segment growth, or will it usually be polygons?

=== Lower priority ===

Add shape characteristics (smoothness, compactness) to the similarity measurement. Similar to eCognition "Multiresolution Segmentation"

It may be useful to do some calculations for the color space (RGB, HSI, L*u*v*, L*a*b*)? (I saw one paper [3] discussing pro/con of different systems, "best" answer is application dependent.)

ML: I would say leave decisions on color space (which is just one portion of feature space) to the user: one can group any kind raster maps with i.group and submit that to segmentation, and so the user can decide whether to use an image represented by different bands in a specific color space, plus any kind of other bands, indices, etc.

= Test Images =

The results of the implemented algorithm should be compared against the results of a similar algorithm implement in other software. The North Carolina GRASS sample location will be used for documentation and manuals.

Carleer [1] used images with 1m resolution from Ikonos, panchromatic band from 08 June 2000, Brussels area.

Should check segmentation results on images from a few different resolutions and different numbers of bands against what is obtained in other software.

Is there a benchmark for processing speed that should be considered? [4]

=Project Plan=

Preparation: Gather ideas from the community! Feature requests, image segmentation literature, and any other ideas and suggestions.

* May 21: Start coding, 8 weeks until Midterm Evaluation
* Week 1: Develop pseudocode to outline the work [http://lists.osgeo.org/pipermail/soc/2012-May/001747.html Report 1]
* Week 2-4: Implement the main algorithm [http://lists.osgeo.org/pipermail/soc/2012-June/001779.html Report 2] [http://lists.osgeo.org/pipermail/soc/2012-June/001804.html Report 3] [http://lists.osgeo.org/pipermail/soc/2012-June/001826.html Report 4]
* Week 5: Add vector maps as a constraint to the segmentation [http://lists.osgeo.org/pipermail/soc/2012-June/001854.html Report 5]
* Week 6: Validation [http://lists.osgeo.org/pipermail/soc/2012-June/001879.html Report 6]
* Week 7: Debugging [http://lists.osgeo.org/pipermail/soc/2012-July/001898.html Report 7]
* Week 8: Contingency time for finishing the above, ensure a solid main program. [http://lists.osgeo.org/pipermail/soc/2012-July/001921.html Report 8]
* July 9: Midterm Evaluation: Evaluate the existing program, determine the plan for the remaining 3-4 weeks. Options include:
* Improving the main algorithm
* Adding control for what scale the segmentation is performed at
* Providing updates to {{cmd|i.maxlik}} to ensure the segmentation output can be used as input for the existing classification functionality
* GUI
* Adding a second image segmentation algorithm

[http://lists.osgeo.org/pipermail/soc/2012-July/001941.html Report 9], [http://lists.osgeo.org/pipermail/soc/2012-July/001960.html Report 10], [http://lists.osgeo.org/pipermail/soc/2012-August/001986.html Report 11], [http://lists.osgeo.org/pipermail/soc/2012-August/002002.html Report 12], [http://lists.osgeo.org/pipermail/soc/2012-August/002041.html Report 13]

= Region Growing Algorithm =

Here is (a start!) for the processing steps, based on SPRING [2]

Region Growing, bottom up processing. Main improvement compared to simple algorithm is to slowly lower the similarity function, so only best matches are made first. This prevents the "first" segment from taking over any unclear areas between it and the next clear segment.

1. Input:
** Seeds: all pixels (Later addition can be alternate seeding methods)
** Similarity Threshold T(t)... as t increases, threshold for similarity is lower. SPRING used: <math>T(t) = T(0) alpha^t </math>, where T(0) > 0, t =0,1,2... and alpha <1
** Size of smallest allowed area (Is this wanted or needed ???)
2. Loop for t
** initialize candidate regions, save mean value vector and neighboring regions (Not sure why this needs to be calculated/saved ahead of time ??)
3. For each region i in candidate region set (first pass this equals the seeds):
** Compare Ri with neighbors (Question: should neighbors include or exclude those regions that were already matched?
** If it exists, Rk is best neighbor if smallest D of all neighbors and and D < T.
** Check Rk's neighbors.
** Merge IF Ri is Rk's best neighbor
** remove from candidate region set. (give all "small" regions a chance to merge with best neighbor before growing larger regions)
** update segment values
** next i
3. next t, with all segments returned to candidate region set, until no regions can be merged

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.

== Functionality ==

<del>1: Implement the 8 neighbor option (currenly only the 4 pixel neighbors are considered).</del> (done)

<del>1: Starting seed pixels for the segments</del> (done)

<del>1: handle null cells in the optional boundary constraints raster.</del> (done)

<del>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.)</del> (documented limitation)

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 (<del>Manhattan</del>, Malahanobis) (Added Manhattan distance)

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.)

== Statistics/metrics ==

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.

== Speed ==

<del>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.</del> implemented, ~20% speed reduction

<del>2: Search continuation. If Ri isn't Rk's best neighbor, then use Rk as the next Ri. (Skips one neighbor finding routine.)</del> TODO: need to decide if this should stay in or out, or as an option. Currently implemented as an option. Need to do some speed tests to see if it is faster or slower after finishing some other changes.

<del>2: Consider peano or other ordering for pixel processing (instead of row major order), should help processing time if an entire "row" of segments are not in RAM.</del> implemented. No significant time change on the small maps it was tested on. Probably this will be helpful if disk I/O becomes limiting.

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

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

?: 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.)

== Memory ==

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

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

<del>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.)</del> Decided not to do this.

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.)

<del>3: Put segment ID in SEG instead of RAM. (Possibly make this dependent on available RAM?) (Only consider if we run into RAM limitations.)</del> Implemented

== Polish ==

<del>1: Add error traps. (Certainly for memory allocation, Minimum number of non-NULL cells in the input bands?anything else?)</del> Added some additional checks.

<del>2: Make the output segment ID's sequential (currently they have what ID the "first" pixel in the segment had).</del> Decided not to do this.

<del>2: There are many small TODO scattered in the code. Resolve some easy questions to clean up the code.</del> Resolved most. Some are left as enhancement suggestions for later.

<del>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.)</del> Using % complete of the input number of passes threshold.

<del>3: GUI (to combine i.segment with the stats module)</del> Wait until there is user demand for this.

== Documentation ==

How to choose parameters, what their impact is.

Typical workflow:

* {{cmd|i.group}}
* i.segment
* {{cmd|r.to.vect}}
* i.segment.metrics and/or {{cmd|i.maxlik}} and/or {{AddonCmd|r.fuzzy}}

= Workflow =

Todo: Some typical workflow examples, type of data, GRASS modules used before and after the image segmentation.

= Results =

== Ortho-photo ==

The [http://grass.osgeo.org/wiki/where_are_these_data link to ortho data is missing] has 3 bands, and the computational region is 1,120,080 cells, at 1-m resolution.

Here's the code used to generate this segmentation result:

i.segment group=ortho output=ortho_segs_ha threshold=0.02 endt=10000 final_mean=ortho_segs_mean_ha min=20 --o

The segmentation performed in 22m53.255s on a Intel i5 laptop with 4Go RAM. The memory consumption was around 38 Mo.

[[File:Raglan_ortho_seg.png]]

== SPOT5 scene ==

The [http://grass.osgeo.org/wiki/where_are_these_data link to SPOT data is missing] has 4 bands, and the computational region is 4,444,517 cells, at 10-m resolution.

Here's the code used to generate this segmentation result:

i.segment group=spot output=spot_seg threshold=0.01 endt=10000 min=30 --o

The segmentation performed in 87m3.870s on a Intel Core 2 workstation with 8Go RAM. The memory consumption was around 170 Mo.

[[File:Taranaki spot seg.png]]

= References =

TODO: complete references with links.

[http://www.armurs.ulb.ac.be/images/8/86/PERS_Carleer_05.pdf] Carleer, et al: Assessment of Very High Spatial Resolution Satellite Image Segmentations, 2005 (Evaluates 2 boundary and 2 region based algorithms.)

[http://marte.dpi.inpe.br/col/sid.inpe.br/deise/1999/02.05.09.30/doc/T205.pdf] Bins, et al: Satellite Imagery Segmentation: A Region Growing Approach, 1996 (Describes approach taken in SPRING software.)

[http://www.sciencedirect.com/science/article/pii/S0031320300001497] Cheng et. al.: Color image segmentation: advances and prospect, 2000 (survey of segmentation methods and color spaces)

[http://www.isprs.org/proceedings/XXXV/congress/comm4/papers/506.pdf] G. Meinel, M. Neubert: A Comparison of Segmentation Programs for High Resolution Remote Sensing Data, 20?? (Includes timing to complete segmentation)

[http://www.wiley.com/WileyCDA/WileyTitle/productCd-0471377392.html?0471377392=] Pitas, I: Digital Image Processing Algorithms and Applications, 2000 (Textbook, including 1 chapter on segmentation methods.)

eCognition Reference Manual

Kurtz et. al: Hierarchical Segmentation of Multiresolution Remote Sensing Images, 2011

Comaniciu, Dorin: Mean Shift: A Robust Approach Toward Feature Space Analysis, 2002

GRASS GSoC 2012 Image Segmentation

2012-08-20T15:11:04Z

⚠️Emomsen: /* Polish */ Updated list

{{GSoC}}
''(See also other [[GRASS_SoC_Ideas_2012#Accepted_Ideas|GRASS GSoC 2012 projects]])''

{| {{table}}
|Student Name: || Eric Momsen
|-
|Organization: || [http://www.osgeo.org OSGeo - Open Source Geospatial Foundation]
|-
| Mentor Name: || Mentor: Markus Metz (backup mentors: M Lennert, P Roudier)
|-
| Title: || '''Image Segmentation'''
|-
|-
| Repository: || AddOns, browse at: [https://trac.osgeo.org/grass/browser/grass-addons/grass7/imagery/i.segment i.segment]
|-
|}
=Abstract=

GRASS GIS has many imagery related processing capabilities, but the field is rapidly developing and many techniques are not yet implemented. The goal of this GSoC project is to implement the region growing image segmentation algorithm.

Input: Raster map(s) to be segmented (plus optional vector map for a constraint)

Output: To include segmented regions with statistics. This information can be directly used or taken as input to existing image classification modules.

Update: This process will be split into two modules, the first will output a raster map with segments, the second will compute statistics for the segments.

=Background=

Image classification techniques already implemented in GRASS GIS include supervised and unsupervised classification. Classification of images based on pixels can often be very noisy. By first segmenting the image, later classification of 'objects' can be more effective. Noise is reduced, classification speed is increased, and most importantly the classification is performed on objects instead of pixels. The {{cmd|i.smap}} module does include a segmentation step (based on Gaussian mixture distribution), but there does not exist a module intended to segment the image and provide segment data for general use. A summary of the existing methods implemented in GRASS are at [[Image classification]]. Furthermore, the module {{AddonCmd|r.seg}} in GRASS-addons uses internally the Mumford-Shah variational model for image segmentation.

== Segmentation Methods ==

* Boundary Based
** optimal edge detector +
** watershed +
* Region Based
** multilevel thresholding technique +
** region growing +
* Combined boundary/region (is this a correct category for these two?)
** mean-shift
** watershed

Carleer et.al. [1] reviewed 4 methods (marked with + above). Boundary based methods are sensitive to noise and texture, and usually depend on good pre-processing. (Does GRASS already have this pre-processing/filtering?) Good results with urban zones, high contrast. Both region based methods had difficulty with transition zones. Region growing was less sensitive to texture (good for high resolution (1m) images). Multi-level techniques are the only way to get all objects without over-segmentation.

I don't recall the source, but I read in one place that mean-shift could be difficult to apply to very large images, and elsewhere it was mentioned watershed sees more use in greyscale images.

As additional algorithms are added to the module, attention should be given to diversify so algorithms with different strengths are implemented first.

=== Region Growing Variations ===

Even within the region growing label, there are a number of approaches. Here are two described in [5].

1. Growing

Seeds (as a subset of the pixels) are selected (using image histogram, previous knowledge, or other methods). Region growing is done by adding adjacent pixels. No merging of segments is done, only unassigned pixels can be assigned to adjacent regions.

2. Growing and Merging

Use all pixels as seeds, no need to have user figure out a reasonable starting seed selection. Now adjacent segments can be merged.

Is there ever a case where someone may want to start with seeds, but still allow segment merging? Or does that fall into the realm of classification to be done in the next step?

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

== Segmentation Considerations ==

All(?) methods have some input parameter(s) that can be set. These parameters influence if the algorithm will over-segment (one expected region is divided into 2 or more segments) or under-segment (putting two expected regions into one segment). If the segments are used for later classification, over-segmentation should usually get preference to under-segmentation. With extensive over-segmentation, some of the advantages provided by segmentation can be lost, but at least the classification can combine the segments into the expected region. Under-segmentation is more critical, as the classification step will not divide the segment to recover the different regions. (Based on a summary of a number of papers from [1])

In order to respond to the issue of over/under-segmentation, a multiscalar approach would be interesting. This would mean either a top-down approach with a first coarse segmentation (under-segmentation) and the finer segmentation in selected segments, or a bottom-up approach with first a very fine-grained segmentation (over-segmentation) and the regrouping of segments to form higher levels. The first approach can be solved by doing a first segmentation, using certain segments as masks and then relaunching a second segmentation. {Or by using a vector map of the first segmentation as a boundary constraint in the second segmentation.} The second approach requires an algorithm to decide which segments should be combined in a larger higher-level segments. A simple nearest neighbor or kmeans approach based on spectral mean can be used here. In terms of implementation in GRASS, this would probably call for several modules, one for the segmentation, and another for grouping of segments. The latter could be an all-purpose clustering module (and can also be emulated by simple data analysis in the attribute table + {{cmd|v.dissolve}}).

It can sometimes be interesting to do a first segmentation on one band (e.g. panchromatic with higher resolution) and then regroup segments based on multispectral data (possibly weighting bands).

=Main Goal=

Implement an image segmentation method to extend the available options for image processing in GRASS. The region growing method has been selected as a robust general purpose method. An important contribution of the new method will be to include vector maps (for example road networks) as a constraint in growing the segments. Output from the module will include Spectral (mean/variance/range/ect) and Spatial (area/shape/location/etc) data for each region.

=Specifications=

* General considerations
** The general principle in GRASS is KISS, with each module doing one thing. It is to be seen if the result of this project is one single module or rather more than one module each specialised in one task in a segmentation workflow.
** As soon as code is to be (potentially) used in several modules, the use of a library should be envisaged.
** Be able to process large images while being considerate of system memory
* Input
** in the GRASS logic, input should be an image group, <del>or even image subgroup</del>, which can contain any number of raster maps, but generally satellite or areal images that are pre-processed and ready for analysis (i.e. no pre-processing in the module) (Update: subgroups are not often used, there use will not be implemented unless someone asks.)
*** This input group will define the feature space which can include spectral and other continuous (elevation, PCA layers, slope aspect...) and possibly (probably not initially) even discrete data (soil type, land cover...)
*** Default action will be to normalize/scale all input rasters to a 0-1 range. The allows bands (0-255), NDVI, and other numbers to be compared on an equal basis in the distance formula without any preprocessing steps. Since it gives equal weights to all rasters in the input group, a flag will give the user the option to skip this normalization step in case they want to use the actual values.
** optionally vector maps of existing features
*** lines (be it linear features or boundary lines of polygons) should be used as constraints meaning that no segment boundary should cross such a line
*** 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
** multi-scalar segmentation can significantly improve results and should thus be implemented if possible (see i.smap code for example)
* Similarity measurement
** The squared euclidean distance will be the default similarity measurement. If time allows, Manhattan distance will be added as an option. (Using the square will give same results, we will also square the similarity threshold so the user doesn't need to worry about this detail.
** For the default scaling of the input, the similarity threshold will be 0 to 1. This should be a good intuitive range for the user, 0 being the entire image is one segment and 1 being no segments can be formed. (Internally, this number must be multiplied by the number of rasters in the image group, but again the user doesn't need to worry about the details.) If the user selects the option to skip the normalization function, they will need to be careful how to select this parameter.
* Output
** first (segmentation) module: raster map of segments (i.e. each pixel value represents id of segment the pixel belongs to)
** second (stats) module: one vector map of segments per hierarchy level with a series of attributes (not all of these attributes should probably be calculated directly be the segmentation module)
*** spectral attributes:
**** per spectral band: mean, min, max, skewness
**** combination of bands: brightness, indices (i.e. results of multi-band calculations)
*** textural attributes: stdev (per-band and/or multi-band), mean difference to neighbor, Haralick texture features cf {{cmd|r.texture}}
*** geometric/morphological attributes: area, perimeter, length/width measures, see also {{cmd|r.li}}
*** context attributes: mean difference to all other regions in the same upper hierarchical level, relative localisation within upper hierarchical level, absolute localisation, number of objects in lower level
** depending on segmentation algorithm: raster map indicating for each pixel the probability of belonging to the segment it was put into, i.e. some measure of reliability of results

=== Questions ===

Number of modules: Should the user run one module to create the segments (raster output), then if they are interested, run r.to.vect and run a second module (vector input/output) if they want to get the statistics. (GUI glue to put them in one screen would be a low priority task for time remaining at the end of the summer.) (I wonder if the stats module should take vector or raster as the input, it will also need the original raster.)

"Probability of belonging to the segment": For region growing - should this be the similarity measure when it was merged? Or similarity measure of the pixel compared to the average?
/*ML: Not sure, but I would think that similarity between pixel and average of region it belongs to might be a good choice. Am not a specialist in statistics, but maybe it is possible to translate this into some form of probability of really "belonging" to that region (cf i.maxlik)*/
So this would be a comparison of the pixel to the final segment. Does anyone have a standard measurement that should be used?

4 vs. 8 neighbors: Should this be a user input option? It seems 4 neighbors (no diagonals) is the normal definition for segmentation, but not for other GRASS modules. Update: Using 4 neighbors as default, with optional flag to select 8 neighbors.

Null cells: Is it possible for some pixels inside the image to have null values? If yes, should they just be excluded from the calculation, or merged into the nearest segment? Update: current plan is to ignore all NULL values in the calculations.

Are there any examples of using linear features to constraint segment growth, or will it usually be polygons?

=== Lower priority ===

Add shape characteristics (smoothness, compactness) to the similarity measurement. Similar to eCognition "Multiresolution Segmentation"

It may be useful to do some calculations for the color space (RGB, HSI, L*u*v*, L*a*b*)? (I saw one paper [3] discussing pro/con of different systems, "best" answer is application dependent.)

ML: I would say leave decisions on color space (which is just one portion of feature space) to the user: one can group any kind raster maps with i.group and submit that to segmentation, and so the user can decide whether to use an image represented by different bands in a specific color space, plus any kind of other bands, indices, etc.

= Test Images =

The results of the implemented algorithm should be compared against the results of a similar algorithm implement in other software. The North Carolina GRASS sample location will be used for documentation and manuals.

Carleer [1] used images with 1m resolution from Ikonos, panchromatic band from 08 June 2000, Brussels area.

Should check segmentation results on images from a few different resolutions and different numbers of bands against what is obtained in other software.

Is there a benchmark for processing speed that should be considered? [4]

=Project Plan=

Preparation: Gather ideas from the community! Feature requests, image segmentation literature, and any other ideas and suggestions.

* May 21: Start coding, 8 weeks until Midterm Evaluation
* Week 1: Develop pseudocode to outline the work [http://lists.osgeo.org/pipermail/soc/2012-May/001747.html Report 1]
* Week 2-4: Implement the main algorithm [http://lists.osgeo.org/pipermail/soc/2012-June/001779.html Report 2] [http://lists.osgeo.org/pipermail/soc/2012-June/001804.html Report 3] [http://lists.osgeo.org/pipermail/soc/2012-June/001826.html Report 4]
* Week 5: Add vector maps as a constraint to the segmentation [http://lists.osgeo.org/pipermail/soc/2012-June/001854.html Report 5]
* Week 6: Validation [http://lists.osgeo.org/pipermail/soc/2012-June/001879.html Report 6]
* Week 7: Debugging [http://lists.osgeo.org/pipermail/soc/2012-July/001898.html Report 7]
* Week 8: Contingency time for finishing the above, ensure a solid main program. [http://lists.osgeo.org/pipermail/soc/2012-July/001921.html Report 8]
* July 9: Midterm Evaluation: Evaluate the existing program, determine the plan for the remaining 3-4 weeks. Options include:
* Improving the main algorithm
* Adding control for what scale the segmentation is performed at
* Providing updates to {{cmd|i.maxlik}} to ensure the segmentation output can be used as input for the existing classification functionality
* GUI
* Adding a second image segmentation algorithm

[http://lists.osgeo.org/pipermail/soc/2012-July/001941.html Report 9], [http://lists.osgeo.org/pipermail/soc/2012-July/001960.html Report 10], [http://lists.osgeo.org/pipermail/soc/2012-August/001986.html Report 11], [http://lists.osgeo.org/pipermail/soc/2012-August/002002.html Report 12], [http://lists.osgeo.org/pipermail/soc/2012-August/002041.html Report 13]

= Region Growing Algorithm =

Here is (a start!) for the processing steps, based on SPRING [2]

Region Growing, bottom up processing. Main improvement compared to simple algorithm is to slowly lower the similarity function, so only best matches are made first. This prevents the "first" segment from taking over any unclear areas between it and the next clear segment.

1. Input:
** Seeds: all pixels (Later addition can be alternate seeding methods)
** Similarity Threshold T(t)... as t increases, threshold for similarity is lower. SPRING used: <math>T(t) = T(0) alpha^t </math>, where T(0) > 0, t =0,1,2... and alpha <1
** Size of smallest allowed area (Is this wanted or needed ???)
2. Loop for t
** initialize candidate regions, save mean value vector and neighboring regions (Not sure why this needs to be calculated/saved ahead of time ??)
3. For each region i in candidate region set (first pass this equals the seeds):
** Compare Ri with neighbors (Question: should neighbors include or exclude those regions that were already matched?
** If it exists, Rk is best neighbor if smallest D of all neighbors and and D < T.
** Check Rk's neighbors.
** Merge IF Ri is Rk's best neighbor
** remove from candidate region set. (give all "small" regions a chance to merge with best neighbor before growing larger regions)
** update segment values
** next i
3. next t, with all segments returned to candidate region set, until no regions can be merged

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.

== Functionality ==

<del>1: Implement the 8 neighbor option (currenly only the 4 pixel neighbors are considered).</del> (done)

<del>1: Starting seed pixels for the segments</del> (done)

<del>1: handle null cells in the optional boundary constraints raster.</del> (done)

<del>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.)</del> (documented limitation)

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 (<del>Manhattan</del>, Malahanobis) (Added Manhattan distance)

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.)

== Statistics/metrics ==

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.

== Speed ==

<del>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.</del> implemented, ~20% speed reduction

<del>2: Search continuation. If Ri isn't Rk's best neighbor, then use Rk as the next Ri. (Skips one neighbor finding routine.)</del> TODO: need to decide if this should stay in or out, or as an option. Currently implemented as an option. Need to do some speed tests to see if it is faster or slower after finishing some other changes.

<del>2: Consider peano or other ordering for pixel processing (instead of row major order), should help processing time if an entire "row" of segments are not in RAM.</del> implemented. No significant time change on the small maps it was tested on. Probably this will be helpful if disk I/O becomes limiting.

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

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

?: 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.)

== Memory ==

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

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

<del>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.)</del> Decided not to do this.

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.)

<del>3: Put segment ID in SEG instead of RAM. (Possibly make this dependent on available RAM?) (Only consider if we run into RAM limitations.)</del> Implemented

== Polish ==

<del>1: Add error traps. (Certainly for memory allocation, Minimum number of non-NULL cells in the input bands?anything else?)</del> Added some additional checks.

<del>2: Make the output segment ID's sequential (currently they have what ID the "first" pixel in the segment had).</del> Decided not to do this.

<del>2: There are many small TODO scattered in the code. Resolve some easy questions to clean up the code.<del> Resolved most. Some are left as enhancement suggestions for later.

<del>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.)</del> Using % complete of the input number of passes threshold.

<del>3: GUI (to combine i.segment with the stats module)</del> Wait until there is user demand for this.

== Documentation ==

How to choose parameters, what their impact is.

Typical workflow:

* {{cmd|i.group}}
* i.segment
* {{cmd|r.to.vect}}
* i.segment.metrics and/or {{cmd|i.maxlik}} and/or {{AddonCmd|r.fuzzy}}

= Workflow =

Todo: Some typical workflow examples, type of data, GRASS modules used before and after the image segmentation.

= Results =

== Ortho-photo ==

The [http://grass.osgeo.org/wiki/where_are_these_data link to ortho data is missing] has 3 bands, and the computational region is 1,120,080 cells, at 1-m resolution.

Here's the code used to generate this segmentation result:

i.segment group=ortho output=ortho_segs_ha threshold=0.02 endt=10000 final_mean=ortho_segs_mean_ha min=20 --o

The segmentation performed in 22m53.255s on a Intel i5 laptop with 4Go RAM. The memory consumption was around 38 Mo.

[[File:Raglan_ortho_seg.png]]

== SPOT5 scene ==

The [http://grass.osgeo.org/wiki/where_are_these_data link to SPOT data is missing] has 4 bands, and the computational region is 4,444,517 cells, at 10-m resolution.

Here's the code used to generate this segmentation result:

i.segment group=spot output=spot_seg threshold=0.01 endt=10000 min=30 --o

The segmentation performed in 87m3.870s on a Intel Core 2 workstation with 8Go RAM. The memory consumption was around 170 Mo.

[[File:Taranaki spot seg.png]]

= References =

TODO: complete references with links.

[http://www.armurs.ulb.ac.be/images/8/86/PERS_Carleer_05.pdf] Carleer, et al: Assessment of Very High Spatial Resolution Satellite Image Segmentations, 2005 (Evaluates 2 boundary and 2 region based algorithms.)

[http://marte.dpi.inpe.br/col/sid.inpe.br/deise/1999/02.05.09.30/doc/T205.pdf] Bins, et al: Satellite Imagery Segmentation: A Region Growing Approach, 1996 (Describes approach taken in SPRING software.)

[http://www.sciencedirect.com/science/article/pii/S0031320300001497] Cheng et. al.: Color image segmentation: advances and prospect, 2000 (survey of segmentation methods and color spaces)

[http://www.isprs.org/proceedings/XXXV/congress/comm4/papers/506.pdf] G. Meinel, M. Neubert: A Comparison of Segmentation Programs for High Resolution Remote Sensing Data, 20?? (Includes timing to complete segmentation)

[http://www.wiley.com/WileyCDA/WileyTitle/productCd-0471377392.html?0471377392=] Pitas, I: Digital Image Processing Algorithms and Applications, 2000 (Textbook, including 1 chapter on segmentation methods.)

eCognition Reference Manual

Kurtz et. al: Hierarchical Segmentation of Multiresolution Remote Sensing Images, 2011

Comaniciu, Dorin: Mean Shift: A Robust Approach Toward Feature Space Analysis, 2002

GRASS GSoC 2012 Image Segmentation

2012-08-20T15:09:09Z

⚠️Emomsen: /* Memory */ Updated list

{{GSoC}}
''(See also other [[GRASS_SoC_Ideas_2012#Accepted_Ideas|GRASS GSoC 2012 projects]])''

{| {{table}}
|Student Name: || Eric Momsen
|-
|Organization: || [http://www.osgeo.org OSGeo - Open Source Geospatial Foundation]
|-
| Mentor Name: || Mentor: Markus Metz (backup mentors: M Lennert, P Roudier)
|-
| Title: || '''Image Segmentation'''
|-
|-
| Repository: || AddOns, browse at: [https://trac.osgeo.org/grass/browser/grass-addons/grass7/imagery/i.segment i.segment]
|-
|}
=Abstract=

GRASS GIS has many imagery related processing capabilities, but the field is rapidly developing and many techniques are not yet implemented. The goal of this GSoC project is to implement the region growing image segmentation algorithm.

Input: Raster map(s) to be segmented (plus optional vector map for a constraint)

Output: To include segmented regions with statistics. This information can be directly used or taken as input to existing image classification modules.

Update: This process will be split into two modules, the first will output a raster map with segments, the second will compute statistics for the segments.

=Background=

Image classification techniques already implemented in GRASS GIS include supervised and unsupervised classification. Classification of images based on pixels can often be very noisy. By first segmenting the image, later classification of 'objects' can be more effective. Noise is reduced, classification speed is increased, and most importantly the classification is performed on objects instead of pixels. The {{cmd|i.smap}} module does include a segmentation step (based on Gaussian mixture distribution), but there does not exist a module intended to segment the image and provide segment data for general use. A summary of the existing methods implemented in GRASS are at [[Image classification]]. Furthermore, the module {{AddonCmd|r.seg}} in GRASS-addons uses internally the Mumford-Shah variational model for image segmentation.

== Segmentation Methods ==

* Boundary Based
** optimal edge detector +
** watershed +
* Region Based
** multilevel thresholding technique +
** region growing +
* Combined boundary/region (is this a correct category for these two?)
** mean-shift
** watershed

Carleer et.al. [1] reviewed 4 methods (marked with + above). Boundary based methods are sensitive to noise and texture, and usually depend on good pre-processing. (Does GRASS already have this pre-processing/filtering?) Good results with urban zones, high contrast. Both region based methods had difficulty with transition zones. Region growing was less sensitive to texture (good for high resolution (1m) images). Multi-level techniques are the only way to get all objects without over-segmentation.

I don't recall the source, but I read in one place that mean-shift could be difficult to apply to very large images, and elsewhere it was mentioned watershed sees more use in greyscale images.

As additional algorithms are added to the module, attention should be given to diversify so algorithms with different strengths are implemented first.

=== Region Growing Variations ===

Even within the region growing label, there are a number of approaches. Here are two described in [5].

1. Growing

Seeds (as a subset of the pixels) are selected (using image histogram, previous knowledge, or other methods). Region growing is done by adding adjacent pixels. No merging of segments is done, only unassigned pixels can be assigned to adjacent regions.

2. Growing and Merging

Use all pixels as seeds, no need to have user figure out a reasonable starting seed selection. Now adjacent segments can be merged.

Is there ever a case where someone may want to start with seeds, but still allow segment merging? Or does that fall into the realm of classification to be done in the next step?

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

== Segmentation Considerations ==

All(?) methods have some input parameter(s) that can be set. These parameters influence if the algorithm will over-segment (one expected region is divided into 2 or more segments) or under-segment (putting two expected regions into one segment). If the segments are used for later classification, over-segmentation should usually get preference to under-segmentation. With extensive over-segmentation, some of the advantages provided by segmentation can be lost, but at least the classification can combine the segments into the expected region. Under-segmentation is more critical, as the classification step will not divide the segment to recover the different regions. (Based on a summary of a number of papers from [1])

In order to respond to the issue of over/under-segmentation, a multiscalar approach would be interesting. This would mean either a top-down approach with a first coarse segmentation (under-segmentation) and the finer segmentation in selected segments, or a bottom-up approach with first a very fine-grained segmentation (over-segmentation) and the regrouping of segments to form higher levels. The first approach can be solved by doing a first segmentation, using certain segments as masks and then relaunching a second segmentation. {Or by using a vector map of the first segmentation as a boundary constraint in the second segmentation.} The second approach requires an algorithm to decide which segments should be combined in a larger higher-level segments. A simple nearest neighbor or kmeans approach based on spectral mean can be used here. In terms of implementation in GRASS, this would probably call for several modules, one for the segmentation, and another for grouping of segments. The latter could be an all-purpose clustering module (and can also be emulated by simple data analysis in the attribute table + {{cmd|v.dissolve}}).

It can sometimes be interesting to do a first segmentation on one band (e.g. panchromatic with higher resolution) and then regroup segments based on multispectral data (possibly weighting bands).

=Main Goal=

Implement an image segmentation method to extend the available options for image processing in GRASS. The region growing method has been selected as a robust general purpose method. An important contribution of the new method will be to include vector maps (for example road networks) as a constraint in growing the segments. Output from the module will include Spectral (mean/variance/range/ect) and Spatial (area/shape/location/etc) data for each region.

=Specifications=

* General considerations
** The general principle in GRASS is KISS, with each module doing one thing. It is to be seen if the result of this project is one single module or rather more than one module each specialised in one task in a segmentation workflow.
** As soon as code is to be (potentially) used in several modules, the use of a library should be envisaged.
** Be able to process large images while being considerate of system memory
* Input
** in the GRASS logic, input should be an image group, <del>or even image subgroup</del>, which can contain any number of raster maps, but generally satellite or areal images that are pre-processed and ready for analysis (i.e. no pre-processing in the module) (Update: subgroups are not often used, there use will not be implemented unless someone asks.)
*** This input group will define the feature space which can include spectral and other continuous (elevation, PCA layers, slope aspect...) and possibly (probably not initially) even discrete data (soil type, land cover...)
*** Default action will be to normalize/scale all input rasters to a 0-1 range. The allows bands (0-255), NDVI, and other numbers to be compared on an equal basis in the distance formula without any preprocessing steps. Since it gives equal weights to all rasters in the input group, a flag will give the user the option to skip this normalization step in case they want to use the actual values.
** optionally vector maps of existing features
*** lines (be it linear features or boundary lines of polygons) should be used as constraints meaning that no segment boundary should cross such a line
*** 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
** multi-scalar segmentation can significantly improve results and should thus be implemented if possible (see i.smap code for example)
* Similarity measurement
** The squared euclidean distance will be the default similarity measurement. If time allows, Manhattan distance will be added as an option. (Using the square will give same results, we will also square the similarity threshold so the user doesn't need to worry about this detail.
** For the default scaling of the input, the similarity threshold will be 0 to 1. This should be a good intuitive range for the user, 0 being the entire image is one segment and 1 being no segments can be formed. (Internally, this number must be multiplied by the number of rasters in the image group, but again the user doesn't need to worry about the details.) If the user selects the option to skip the normalization function, they will need to be careful how to select this parameter.
* Output
** first (segmentation) module: raster map of segments (i.e. each pixel value represents id of segment the pixel belongs to)
** second (stats) module: one vector map of segments per hierarchy level with a series of attributes (not all of these attributes should probably be calculated directly be the segmentation module)
*** spectral attributes:
**** per spectral band: mean, min, max, skewness
**** combination of bands: brightness, indices (i.e. results of multi-band calculations)
*** textural attributes: stdev (per-band and/or multi-band), mean difference to neighbor, Haralick texture features cf {{cmd|r.texture}}
*** geometric/morphological attributes: area, perimeter, length/width measures, see also {{cmd|r.li}}
*** context attributes: mean difference to all other regions in the same upper hierarchical level, relative localisation within upper hierarchical level, absolute localisation, number of objects in lower level
** depending on segmentation algorithm: raster map indicating for each pixel the probability of belonging to the segment it was put into, i.e. some measure of reliability of results

=== Questions ===

Number of modules: Should the user run one module to create the segments (raster output), then if they are interested, run r.to.vect and run a second module (vector input/output) if they want to get the statistics. (GUI glue to put them in one screen would be a low priority task for time remaining at the end of the summer.) (I wonder if the stats module should take vector or raster as the input, it will also need the original raster.)

"Probability of belonging to the segment": For region growing - should this be the similarity measure when it was merged? Or similarity measure of the pixel compared to the average?
/*ML: Not sure, but I would think that similarity between pixel and average of region it belongs to might be a good choice. Am not a specialist in statistics, but maybe it is possible to translate this into some form of probability of really "belonging" to that region (cf i.maxlik)*/
So this would be a comparison of the pixel to the final segment. Does anyone have a standard measurement that should be used?

4 vs. 8 neighbors: Should this be a user input option? It seems 4 neighbors (no diagonals) is the normal definition for segmentation, but not for other GRASS modules. Update: Using 4 neighbors as default, with optional flag to select 8 neighbors.

Null cells: Is it possible for some pixels inside the image to have null values? If yes, should they just be excluded from the calculation, or merged into the nearest segment? Update: current plan is to ignore all NULL values in the calculations.

Are there any examples of using linear features to constraint segment growth, or will it usually be polygons?

=== Lower priority ===

Add shape characteristics (smoothness, compactness) to the similarity measurement. Similar to eCognition "Multiresolution Segmentation"

It may be useful to do some calculations for the color space (RGB, HSI, L*u*v*, L*a*b*)? (I saw one paper [3] discussing pro/con of different systems, "best" answer is application dependent.)

ML: I would say leave decisions on color space (which is just one portion of feature space) to the user: one can group any kind raster maps with i.group and submit that to segmentation, and so the user can decide whether to use an image represented by different bands in a specific color space, plus any kind of other bands, indices, etc.

= Test Images =

The results of the implemented algorithm should be compared against the results of a similar algorithm implement in other software. The North Carolina GRASS sample location will be used for documentation and manuals.

Carleer [1] used images with 1m resolution from Ikonos, panchromatic band from 08 June 2000, Brussels area.

Should check segmentation results on images from a few different resolutions and different numbers of bands against what is obtained in other software.

Is there a benchmark for processing speed that should be considered? [4]

=Project Plan=

Preparation: Gather ideas from the community! Feature requests, image segmentation literature, and any other ideas and suggestions.

* May 21: Start coding, 8 weeks until Midterm Evaluation
* Week 1: Develop pseudocode to outline the work [http://lists.osgeo.org/pipermail/soc/2012-May/001747.html Report 1]
* Week 2-4: Implement the main algorithm [http://lists.osgeo.org/pipermail/soc/2012-June/001779.html Report 2] [http://lists.osgeo.org/pipermail/soc/2012-June/001804.html Report 3] [http://lists.osgeo.org/pipermail/soc/2012-June/001826.html Report 4]
* Week 5: Add vector maps as a constraint to the segmentation [http://lists.osgeo.org/pipermail/soc/2012-June/001854.html Report 5]
* Week 6: Validation [http://lists.osgeo.org/pipermail/soc/2012-June/001879.html Report 6]
* Week 7: Debugging [http://lists.osgeo.org/pipermail/soc/2012-July/001898.html Report 7]
* Week 8: Contingency time for finishing the above, ensure a solid main program. [http://lists.osgeo.org/pipermail/soc/2012-July/001921.html Report 8]
* July 9: Midterm Evaluation: Evaluate the existing program, determine the plan for the remaining 3-4 weeks. Options include:
* Improving the main algorithm
* Adding control for what scale the segmentation is performed at
* Providing updates to {{cmd|i.maxlik}} to ensure the segmentation output can be used as input for the existing classification functionality
* GUI
* Adding a second image segmentation algorithm

[http://lists.osgeo.org/pipermail/soc/2012-July/001941.html Report 9], [http://lists.osgeo.org/pipermail/soc/2012-July/001960.html Report 10], [http://lists.osgeo.org/pipermail/soc/2012-August/001986.html Report 11], [http://lists.osgeo.org/pipermail/soc/2012-August/002002.html Report 12], [http://lists.osgeo.org/pipermail/soc/2012-August/002041.html Report 13]

= Region Growing Algorithm =

Here is (a start!) for the processing steps, based on SPRING [2]

Region Growing, bottom up processing. Main improvement compared to simple algorithm is to slowly lower the similarity function, so only best matches are made first. This prevents the "first" segment from taking over any unclear areas between it and the next clear segment.

1. Input:
** Seeds: all pixels (Later addition can be alternate seeding methods)
** Similarity Threshold T(t)... as t increases, threshold for similarity is lower. SPRING used: <math>T(t) = T(0) alpha^t </math>, where T(0) > 0, t =0,1,2... and alpha <1
** Size of smallest allowed area (Is this wanted or needed ???)
2. Loop for t
** initialize candidate regions, save mean value vector and neighboring regions (Not sure why this needs to be calculated/saved ahead of time ??)
3. For each region i in candidate region set (first pass this equals the seeds):
** Compare Ri with neighbors (Question: should neighbors include or exclude those regions that were already matched?
** If it exists, Rk is best neighbor if smallest D of all neighbors and and D < T.
** Check Rk's neighbors.
** Merge IF Ri is Rk's best neighbor
** remove from candidate region set. (give all "small" regions a chance to merge with best neighbor before growing larger regions)
** update segment values
** next i
3. next t, with all segments returned to candidate region set, until no regions can be merged

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.

== Functionality ==

<del>1: Implement the 8 neighbor option (currenly only the 4 pixel neighbors are considered).</del> (done)

<del>1: Starting seed pixels for the segments</del> (done)

<del>1: handle null cells in the optional boundary constraints raster.</del> (done)

<del>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.)</del> (documented limitation)

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 (<del>Manhattan</del>, Malahanobis) (Added Manhattan distance)

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.)

== Statistics/metrics ==

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.

== Speed ==

<del>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.</del> implemented, ~20% speed reduction

<del>2: Search continuation. If Ri isn't Rk's best neighbor, then use Rk as the next Ri. (Skips one neighbor finding routine.)</del> TODO: need to decide if this should stay in or out, or as an option. Currently implemented as an option. Need to do some speed tests to see if it is faster or slower after finishing some other changes.

<del>2: Consider peano or other ordering for pixel processing (instead of row major order), should help processing time if an entire "row" of segments are not in RAM.</del> implemented. No significant time change on the small maps it was tested on. Probably this will be helpful if disk I/O becomes limiting.

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

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

?: 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.)

== Memory ==

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

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

<del>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.)</del> Decided not to do this.

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.)

<del>3: Put segment ID in SEG instead of RAM. (Possibly make this dependent on available RAM?) (Only consider if we run into RAM limitations.)</del> Implemented

== Polish ==

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)

== Documentation ==

How to choose parameters, what their impact is.

Typical workflow:

* {{cmd|i.group}}
* i.segment
* {{cmd|r.to.vect}}
* i.segment.metrics and/or {{cmd|i.maxlik}} and/or {{AddonCmd|r.fuzzy}}

= Workflow =

Todo: Some typical workflow examples, type of data, GRASS modules used before and after the image segmentation.

= Results =

== Ortho-photo ==

The [http://grass.osgeo.org/wiki/where_are_these_data link to ortho data is missing] has 3 bands, and the computational region is 1,120,080 cells, at 1-m resolution.

Here's the code used to generate this segmentation result:

i.segment group=ortho output=ortho_segs_ha threshold=0.02 endt=10000 final_mean=ortho_segs_mean_ha min=20 --o

The segmentation performed in 22m53.255s on a Intel i5 laptop with 4Go RAM. The memory consumption was around 38 Mo.

[[File:Raglan_ortho_seg.png]]

== SPOT5 scene ==

The [http://grass.osgeo.org/wiki/where_are_these_data link to SPOT data is missing] has 4 bands, and the computational region is 4,444,517 cells, at 10-m resolution.

Here's the code used to generate this segmentation result:

i.segment group=spot output=spot_seg threshold=0.01 endt=10000 min=30 --o

The segmentation performed in 87m3.870s on a Intel Core 2 workstation with 8Go RAM. The memory consumption was around 170 Mo.

[[File:Taranaki spot seg.png]]

= References =

TODO: complete references with links.

[http://www.armurs.ulb.ac.be/images/8/86/PERS_Carleer_05.pdf] Carleer, et al: Assessment of Very High Spatial Resolution Satellite Image Segmentations, 2005 (Evaluates 2 boundary and 2 region based algorithms.)

[http://marte.dpi.inpe.br/col/sid.inpe.br/deise/1999/02.05.09.30/doc/T205.pdf] Bins, et al: Satellite Imagery Segmentation: A Region Growing Approach, 1996 (Describes approach taken in SPRING software.)

[http://www.sciencedirect.com/science/article/pii/S0031320300001497] Cheng et. al.: Color image segmentation: advances and prospect, 2000 (survey of segmentation methods and color spaces)

[http://www.isprs.org/proceedings/XXXV/congress/comm4/papers/506.pdf] G. Meinel, M. Neubert: A Comparison of Segmentation Programs for High Resolution Remote Sensing Data, 20?? (Includes timing to complete segmentation)

[http://www.wiley.com/WileyCDA/WileyTitle/productCd-0471377392.html?0471377392=] Pitas, I: Digital Image Processing Algorithms and Applications, 2000 (Textbook, including 1 chapter on segmentation methods.)

eCognition Reference Manual

Kurtz et. al: Hierarchical Segmentation of Multiresolution Remote Sensing Images, 2011

Comaniciu, Dorin: Mean Shift: A Robust Approach Toward Feature Space Analysis, 2002

GRASS GSoC 2012 Image Segmentation

2012-08-20T15:08:21Z

⚠️Emomsen: /* Speed */ updated list

{{GSoC}}
''(See also other [[GRASS_SoC_Ideas_2012#Accepted_Ideas|GRASS GSoC 2012 projects]])''

{| {{table}}
|Student Name: || Eric Momsen
|-
|Organization: || [http://www.osgeo.org OSGeo - Open Source Geospatial Foundation]
|-
| Mentor Name: || Mentor: Markus Metz (backup mentors: M Lennert, P Roudier)
|-
| Title: || '''Image Segmentation'''
|-
|-
| Repository: || AddOns, browse at: [https://trac.osgeo.org/grass/browser/grass-addons/grass7/imagery/i.segment i.segment]
|-
|}
=Abstract=

GRASS GIS has many imagery related processing capabilities, but the field is rapidly developing and many techniques are not yet implemented. The goal of this GSoC project is to implement the region growing image segmentation algorithm.

Input: Raster map(s) to be segmented (plus optional vector map for a constraint)

Output: To include segmented regions with statistics. This information can be directly used or taken as input to existing image classification modules.

Update: This process will be split into two modules, the first will output a raster map with segments, the second will compute statistics for the segments.

=Background=

Image classification techniques already implemented in GRASS GIS include supervised and unsupervised classification. Classification of images based on pixels can often be very noisy. By first segmenting the image, later classification of 'objects' can be more effective. Noise is reduced, classification speed is increased, and most importantly the classification is performed on objects instead of pixels. The {{cmd|i.smap}} module does include a segmentation step (based on Gaussian mixture distribution), but there does not exist a module intended to segment the image and provide segment data for general use. A summary of the existing methods implemented in GRASS are at [[Image classification]]. Furthermore, the module {{AddonCmd|r.seg}} in GRASS-addons uses internally the Mumford-Shah variational model for image segmentation.

== Segmentation Methods ==

* Boundary Based
** optimal edge detector +
** watershed +
* Region Based
** multilevel thresholding technique +
** region growing +
* Combined boundary/region (is this a correct category for these two?)
** mean-shift
** watershed

Carleer et.al. [1] reviewed 4 methods (marked with + above). Boundary based methods are sensitive to noise and texture, and usually depend on good pre-processing. (Does GRASS already have this pre-processing/filtering?) Good results with urban zones, high contrast. Both region based methods had difficulty with transition zones. Region growing was less sensitive to texture (good for high resolution (1m) images). Multi-level techniques are the only way to get all objects without over-segmentation.

I don't recall the source, but I read in one place that mean-shift could be difficult to apply to very large images, and elsewhere it was mentioned watershed sees more use in greyscale images.

As additional algorithms are added to the module, attention should be given to diversify so algorithms with different strengths are implemented first.

=== Region Growing Variations ===

Even within the region growing label, there are a number of approaches. Here are two described in [5].

1. Growing

Seeds (as a subset of the pixels) are selected (using image histogram, previous knowledge, or other methods). Region growing is done by adding adjacent pixels. No merging of segments is done, only unassigned pixels can be assigned to adjacent regions.

2. Growing and Merging

Use all pixels as seeds, no need to have user figure out a reasonable starting seed selection. Now adjacent segments can be merged.

Is there ever a case where someone may want to start with seeds, but still allow segment merging? Or does that fall into the realm of classification to be done in the next step?

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

== Segmentation Considerations ==

All(?) methods have some input parameter(s) that can be set. These parameters influence if the algorithm will over-segment (one expected region is divided into 2 or more segments) or under-segment (putting two expected regions into one segment). If the segments are used for later classification, over-segmentation should usually get preference to under-segmentation. With extensive over-segmentation, some of the advantages provided by segmentation can be lost, but at least the classification can combine the segments into the expected region. Under-segmentation is more critical, as the classification step will not divide the segment to recover the different regions. (Based on a summary of a number of papers from [1])

In order to respond to the issue of over/under-segmentation, a multiscalar approach would be interesting. This would mean either a top-down approach with a first coarse segmentation (under-segmentation) and the finer segmentation in selected segments, or a bottom-up approach with first a very fine-grained segmentation (over-segmentation) and the regrouping of segments to form higher levels. The first approach can be solved by doing a first segmentation, using certain segments as masks and then relaunching a second segmentation. {Or by using a vector map of the first segmentation as a boundary constraint in the second segmentation.} The second approach requires an algorithm to decide which segments should be combined in a larger higher-level segments. A simple nearest neighbor or kmeans approach based on spectral mean can be used here. In terms of implementation in GRASS, this would probably call for several modules, one for the segmentation, and another for grouping of segments. The latter could be an all-purpose clustering module (and can also be emulated by simple data analysis in the attribute table + {{cmd|v.dissolve}}).

It can sometimes be interesting to do a first segmentation on one band (e.g. panchromatic with higher resolution) and then regroup segments based on multispectral data (possibly weighting bands).

=Main Goal=

Implement an image segmentation method to extend the available options for image processing in GRASS. The region growing method has been selected as a robust general purpose method. An important contribution of the new method will be to include vector maps (for example road networks) as a constraint in growing the segments. Output from the module will include Spectral (mean/variance/range/ect) and Spatial (area/shape/location/etc) data for each region.

=Specifications=

* General considerations
** The general principle in GRASS is KISS, with each module doing one thing. It is to be seen if the result of this project is one single module or rather more than one module each specialised in one task in a segmentation workflow.
** As soon as code is to be (potentially) used in several modules, the use of a library should be envisaged.
** Be able to process large images while being considerate of system memory
* Input
** in the GRASS logic, input should be an image group, <del>or even image subgroup</del>, which can contain any number of raster maps, but generally satellite or areal images that are pre-processed and ready for analysis (i.e. no pre-processing in the module) (Update: subgroups are not often used, there use will not be implemented unless someone asks.)
*** This input group will define the feature space which can include spectral and other continuous (elevation, PCA layers, slope aspect...) and possibly (probably not initially) even discrete data (soil type, land cover...)
*** Default action will be to normalize/scale all input rasters to a 0-1 range. The allows bands (0-255), NDVI, and other numbers to be compared on an equal basis in the distance formula without any preprocessing steps. Since it gives equal weights to all rasters in the input group, a flag will give the user the option to skip this normalization step in case they want to use the actual values.
** optionally vector maps of existing features
*** lines (be it linear features or boundary lines of polygons) should be used as constraints meaning that no segment boundary should cross such a line
*** 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
** multi-scalar segmentation can significantly improve results and should thus be implemented if possible (see i.smap code for example)
* Similarity measurement
** The squared euclidean distance will be the default similarity measurement. If time allows, Manhattan distance will be added as an option. (Using the square will give same results, we will also square the similarity threshold so the user doesn't need to worry about this detail.
** For the default scaling of the input, the similarity threshold will be 0 to 1. This should be a good intuitive range for the user, 0 being the entire image is one segment and 1 being no segments can be formed. (Internally, this number must be multiplied by the number of rasters in the image group, but again the user doesn't need to worry about the details.) If the user selects the option to skip the normalization function, they will need to be careful how to select this parameter.
* Output
** first (segmentation) module: raster map of segments (i.e. each pixel value represents id of segment the pixel belongs to)
** second (stats) module: one vector map of segments per hierarchy level with a series of attributes (not all of these attributes should probably be calculated directly be the segmentation module)
*** spectral attributes:
**** per spectral band: mean, min, max, skewness
**** combination of bands: brightness, indices (i.e. results of multi-band calculations)
*** textural attributes: stdev (per-band and/or multi-band), mean difference to neighbor, Haralick texture features cf {{cmd|r.texture}}
*** geometric/morphological attributes: area, perimeter, length/width measures, see also {{cmd|r.li}}
*** context attributes: mean difference to all other regions in the same upper hierarchical level, relative localisation within upper hierarchical level, absolute localisation, number of objects in lower level
** depending on segmentation algorithm: raster map indicating for each pixel the probability of belonging to the segment it was put into, i.e. some measure of reliability of results

=== Questions ===

Number of modules: Should the user run one module to create the segments (raster output), then if they are interested, run r.to.vect and run a second module (vector input/output) if they want to get the statistics. (GUI glue to put them in one screen would be a low priority task for time remaining at the end of the summer.) (I wonder if the stats module should take vector or raster as the input, it will also need the original raster.)

"Probability of belonging to the segment": For region growing - should this be the similarity measure when it was merged? Or similarity measure of the pixel compared to the average?
/*ML: Not sure, but I would think that similarity between pixel and average of region it belongs to might be a good choice. Am not a specialist in statistics, but maybe it is possible to translate this into some form of probability of really "belonging" to that region (cf i.maxlik)*/
So this would be a comparison of the pixel to the final segment. Does anyone have a standard measurement that should be used?

4 vs. 8 neighbors: Should this be a user input option? It seems 4 neighbors (no diagonals) is the normal definition for segmentation, but not for other GRASS modules. Update: Using 4 neighbors as default, with optional flag to select 8 neighbors.

Null cells: Is it possible for some pixels inside the image to have null values? If yes, should they just be excluded from the calculation, or merged into the nearest segment? Update: current plan is to ignore all NULL values in the calculations.

Are there any examples of using linear features to constraint segment growth, or will it usually be polygons?

=== Lower priority ===

Add shape characteristics (smoothness, compactness) to the similarity measurement. Similar to eCognition "Multiresolution Segmentation"

It may be useful to do some calculations for the color space (RGB, HSI, L*u*v*, L*a*b*)? (I saw one paper [3] discussing pro/con of different systems, "best" answer is application dependent.)

ML: I would say leave decisions on color space (which is just one portion of feature space) to the user: one can group any kind raster maps with i.group and submit that to segmentation, and so the user can decide whether to use an image represented by different bands in a specific color space, plus any kind of other bands, indices, etc.

= Test Images =

The results of the implemented algorithm should be compared against the results of a similar algorithm implement in other software. The North Carolina GRASS sample location will be used for documentation and manuals.

Carleer [1] used images with 1m resolution from Ikonos, panchromatic band from 08 June 2000, Brussels area.

Should check segmentation results on images from a few different resolutions and different numbers of bands against what is obtained in other software.

Is there a benchmark for processing speed that should be considered? [4]

=Project Plan=

Preparation: Gather ideas from the community! Feature requests, image segmentation literature, and any other ideas and suggestions.

* May 21: Start coding, 8 weeks until Midterm Evaluation
* Week 1: Develop pseudocode to outline the work [http://lists.osgeo.org/pipermail/soc/2012-May/001747.html Report 1]
* Week 2-4: Implement the main algorithm [http://lists.osgeo.org/pipermail/soc/2012-June/001779.html Report 2] [http://lists.osgeo.org/pipermail/soc/2012-June/001804.html Report 3] [http://lists.osgeo.org/pipermail/soc/2012-June/001826.html Report 4]
* Week 5: Add vector maps as a constraint to the segmentation [http://lists.osgeo.org/pipermail/soc/2012-June/001854.html Report 5]
* Week 6: Validation [http://lists.osgeo.org/pipermail/soc/2012-June/001879.html Report 6]
* Week 7: Debugging [http://lists.osgeo.org/pipermail/soc/2012-July/001898.html Report 7]
* Week 8: Contingency time for finishing the above, ensure a solid main program. [http://lists.osgeo.org/pipermail/soc/2012-July/001921.html Report 8]
* July 9: Midterm Evaluation: Evaluate the existing program, determine the plan for the remaining 3-4 weeks. Options include:
* Improving the main algorithm
* Adding control for what scale the segmentation is performed at
* Providing updates to {{cmd|i.maxlik}} to ensure the segmentation output can be used as input for the existing classification functionality
* GUI
* Adding a second image segmentation algorithm

[http://lists.osgeo.org/pipermail/soc/2012-July/001941.html Report 9], [http://lists.osgeo.org/pipermail/soc/2012-July/001960.html Report 10], [http://lists.osgeo.org/pipermail/soc/2012-August/001986.html Report 11], [http://lists.osgeo.org/pipermail/soc/2012-August/002002.html Report 12], [http://lists.osgeo.org/pipermail/soc/2012-August/002041.html Report 13]

= Region Growing Algorithm =

Here is (a start!) for the processing steps, based on SPRING [2]

Region Growing, bottom up processing. Main improvement compared to simple algorithm is to slowly lower the similarity function, so only best matches are made first. This prevents the "first" segment from taking over any unclear areas between it and the next clear segment.

1. Input:
** Seeds: all pixels (Later addition can be alternate seeding methods)
** Similarity Threshold T(t)... as t increases, threshold for similarity is lower. SPRING used: <math>T(t) = T(0) alpha^t </math>, where T(0) > 0, t =0,1,2... and alpha <1
** Size of smallest allowed area (Is this wanted or needed ???)
2. Loop for t
** initialize candidate regions, save mean value vector and neighboring regions (Not sure why this needs to be calculated/saved ahead of time ??)
3. For each region i in candidate region set (first pass this equals the seeds):
** Compare Ri with neighbors (Question: should neighbors include or exclude those regions that were already matched?
** If it exists, Rk is best neighbor if smallest D of all neighbors and and D < T.
** Check Rk's neighbors.
** Merge IF Ri is Rk's best neighbor
** remove from candidate region set. (give all "small" regions a chance to merge with best neighbor before growing larger regions)
** update segment values
** next i
3. next t, with all segments returned to candidate region set, until no regions can be merged

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.

== Functionality ==

<del>1: Implement the 8 neighbor option (currenly only the 4 pixel neighbors are considered).</del> (done)

<del>1: Starting seed pixels for the segments</del> (done)

<del>1: handle null cells in the optional boundary constraints raster.</del> (done)

<del>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.)</del> (documented limitation)

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 (<del>Manhattan</del>, Malahanobis) (Added Manhattan distance)

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.)

== Statistics/metrics ==

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.

== Speed ==

<del>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.</del> implemented, ~20% speed reduction

<del>2: Search continuation. If Ri isn't Rk's best neighbor, then use Rk as the next Ri. (Skips one neighbor finding routine.)</del> TODO: need to decide if this should stay in or out, or as an option. Currently implemented as an option. Need to do some speed tests to see if it is faster or slower after finishing some other changes.

<del>2: Consider peano or other ordering for pixel processing (instead of row major order), should help processing time if an entire "row" of segments are not in RAM.</del> implemented. No significant time change on the small maps it was tested on. Probably this will be helpful if disk I/O becomes limiting.

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

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

?: 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.)

== Memory ==

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.)

3: Put segment ID in SEG instead of RAM. (Possibly make this dependent on available RAM?) (Only consider if we run into RAM limitations.)

== Polish ==

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)

== Documentation ==

How to choose parameters, what their impact is.

Typical workflow:

* {{cmd|i.group}}
* i.segment
* {{cmd|r.to.vect}}
* i.segment.metrics and/or {{cmd|i.maxlik}} and/or {{AddonCmd|r.fuzzy}}

= Workflow =

Todo: Some typical workflow examples, type of data, GRASS modules used before and after the image segmentation.

= Results =

== Ortho-photo ==

The [http://grass.osgeo.org/wiki/where_are_these_data link to ortho data is missing] has 3 bands, and the computational region is 1,120,080 cells, at 1-m resolution.

Here's the code used to generate this segmentation result:

i.segment group=ortho output=ortho_segs_ha threshold=0.02 endt=10000 final_mean=ortho_segs_mean_ha min=20 --o

The segmentation performed in 22m53.255s on a Intel i5 laptop with 4Go RAM. The memory consumption was around 38 Mo.

[[File:Raglan_ortho_seg.png]]

== SPOT5 scene ==

The [http://grass.osgeo.org/wiki/where_are_these_data link to SPOT data is missing] has 4 bands, and the computational region is 4,444,517 cells, at 10-m resolution.

Here's the code used to generate this segmentation result:

i.segment group=spot output=spot_seg threshold=0.01 endt=10000 min=30 --o

The segmentation performed in 87m3.870s on a Intel Core 2 workstation with 8Go RAM. The memory consumption was around 170 Mo.

[[File:Taranaki spot seg.png]]

= References =

TODO: complete references with links.

[http://www.armurs.ulb.ac.be/images/8/86/PERS_Carleer_05.pdf] Carleer, et al: Assessment of Very High Spatial Resolution Satellite Image Segmentations, 2005 (Evaluates 2 boundary and 2 region based algorithms.)

[http://marte.dpi.inpe.br/col/sid.inpe.br/deise/1999/02.05.09.30/doc/T205.pdf] Bins, et al: Satellite Imagery Segmentation: A Region Growing Approach, 1996 (Describes approach taken in SPRING software.)

[http://www.sciencedirect.com/science/article/pii/S0031320300001497] Cheng et. al.: Color image segmentation: advances and prospect, 2000 (survey of segmentation methods and color spaces)

[http://www.isprs.org/proceedings/XXXV/congress/comm4/papers/506.pdf] G. Meinel, M. Neubert: A Comparison of Segmentation Programs for High Resolution Remote Sensing Data, 20?? (Includes timing to complete segmentation)

[http://www.wiley.com/WileyCDA/WileyTitle/productCd-0471377392.html?0471377392=] Pitas, I: Digital Image Processing Algorithms and Applications, 2000 (Textbook, including 1 chapter on segmentation methods.)

eCognition Reference Manual

Kurtz et. al: Hierarchical Segmentation of Multiresolution Remote Sensing Images, 2011

Comaniciu, Dorin: Mean Shift: A Robust Approach Toward Feature Space Analysis, 2002

GRASS GSoC 2012 Image Segmentation

2012-08-20T15:05:56Z

⚠️Emomsen: /* Project Plan */ Added links to reports.

{{GSoC}}
''(See also other [[GRASS_SoC_Ideas_2012#Accepted_Ideas|GRASS GSoC 2012 projects]])''

{| {{table}}
|Student Name: || Eric Momsen
|-
|Organization: || [http://www.osgeo.org OSGeo - Open Source Geospatial Foundation]
|-
| Mentor Name: || Mentor: Markus Metz (backup mentors: M Lennert, P Roudier)
|-
| Title: || '''Image Segmentation'''
|-
|-
| Repository: || AddOns, browse at: [https://trac.osgeo.org/grass/browser/grass-addons/grass7/imagery/i.segment i.segment]
|-
|}
=Abstract=

GRASS GIS has many imagery related processing capabilities, but the field is rapidly developing and many techniques are not yet implemented. The goal of this GSoC project is to implement the region growing image segmentation algorithm.

Input: Raster map(s) to be segmented (plus optional vector map for a constraint)

Output: To include segmented regions with statistics. This information can be directly used or taken as input to existing image classification modules.

Update: This process will be split into two modules, the first will output a raster map with segments, the second will compute statistics for the segments.

=Background=

Image classification techniques already implemented in GRASS GIS include supervised and unsupervised classification. Classification of images based on pixels can often be very noisy. By first segmenting the image, later classification of 'objects' can be more effective. Noise is reduced, classification speed is increased, and most importantly the classification is performed on objects instead of pixels. The {{cmd|i.smap}} module does include a segmentation step (based on Gaussian mixture distribution), but there does not exist a module intended to segment the image and provide segment data for general use. A summary of the existing methods implemented in GRASS are at [[Image classification]]. Furthermore, the module {{AddonCmd|r.seg}} in GRASS-addons uses internally the Mumford-Shah variational model for image segmentation.

== Segmentation Methods ==

* Boundary Based
** optimal edge detector +
** watershed +
* Region Based
** multilevel thresholding technique +
** region growing +
* Combined boundary/region (is this a correct category for these two?)
** mean-shift
** watershed

Carleer et.al. [1] reviewed 4 methods (marked with + above). Boundary based methods are sensitive to noise and texture, and usually depend on good pre-processing. (Does GRASS already have this pre-processing/filtering?) Good results with urban zones, high contrast. Both region based methods had difficulty with transition zones. Region growing was less sensitive to texture (good for high resolution (1m) images). Multi-level techniques are the only way to get all objects without over-segmentation.

I don't recall the source, but I read in one place that mean-shift could be difficult to apply to very large images, and elsewhere it was mentioned watershed sees more use in greyscale images.

As additional algorithms are added to the module, attention should be given to diversify so algorithms with different strengths are implemented first.

=== Region Growing Variations ===

Even within the region growing label, there are a number of approaches. Here are two described in [5].

1. Growing

Seeds (as a subset of the pixels) are selected (using image histogram, previous knowledge, or other methods). Region growing is done by adding adjacent pixels. No merging of segments is done, only unassigned pixels can be assigned to adjacent regions.

2. Growing and Merging

Use all pixels as seeds, no need to have user figure out a reasonable starting seed selection. Now adjacent segments can be merged.

Is there ever a case where someone may want to start with seeds, but still allow segment merging? Or does that fall into the realm of classification to be done in the next step?

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

== Segmentation Considerations ==

All(?) methods have some input parameter(s) that can be set. These parameters influence if the algorithm will over-segment (one expected region is divided into 2 or more segments) or under-segment (putting two expected regions into one segment). If the segments are used for later classification, over-segmentation should usually get preference to under-segmentation. With extensive over-segmentation, some of the advantages provided by segmentation can be lost, but at least the classification can combine the segments into the expected region. Under-segmentation is more critical, as the classification step will not divide the segment to recover the different regions. (Based on a summary of a number of papers from [1])

In order to respond to the issue of over/under-segmentation, a multiscalar approach would be interesting. This would mean either a top-down approach with a first coarse segmentation (under-segmentation) and the finer segmentation in selected segments, or a bottom-up approach with first a very fine-grained segmentation (over-segmentation) and the regrouping of segments to form higher levels. The first approach can be solved by doing a first segmentation, using certain segments as masks and then relaunching a second segmentation. {Or by using a vector map of the first segmentation as a boundary constraint in the second segmentation.} The second approach requires an algorithm to decide which segments should be combined in a larger higher-level segments. A simple nearest neighbor or kmeans approach based on spectral mean can be used here. In terms of implementation in GRASS, this would probably call for several modules, one for the segmentation, and another for grouping of segments. The latter could be an all-purpose clustering module (and can also be emulated by simple data analysis in the attribute table + {{cmd|v.dissolve}}).

It can sometimes be interesting to do a first segmentation on one band (e.g. panchromatic with higher resolution) and then regroup segments based on multispectral data (possibly weighting bands).

=Main Goal=

Implement an image segmentation method to extend the available options for image processing in GRASS. The region growing method has been selected as a robust general purpose method. An important contribution of the new method will be to include vector maps (for example road networks) as a constraint in growing the segments. Output from the module will include Spectral (mean/variance/range/ect) and Spatial (area/shape/location/etc) data for each region.

=Specifications=

* General considerations
** The general principle in GRASS is KISS, with each module doing one thing. It is to be seen if the result of this project is one single module or rather more than one module each specialised in one task in a segmentation workflow.
** As soon as code is to be (potentially) used in several modules, the use of a library should be envisaged.
** Be able to process large images while being considerate of system memory
* Input
** in the GRASS logic, input should be an image group, <del>or even image subgroup</del>, which can contain any number of raster maps, but generally satellite or areal images that are pre-processed and ready for analysis (i.e. no pre-processing in the module) (Update: subgroups are not often used, there use will not be implemented unless someone asks.)
*** This input group will define the feature space which can include spectral and other continuous (elevation, PCA layers, slope aspect...) and possibly (probably not initially) even discrete data (soil type, land cover...)
*** Default action will be to normalize/scale all input rasters to a 0-1 range. The allows bands (0-255), NDVI, and other numbers to be compared on an equal basis in the distance formula without any preprocessing steps. Since it gives equal weights to all rasters in the input group, a flag will give the user the option to skip this normalization step in case they want to use the actual values.
** optionally vector maps of existing features
*** lines (be it linear features or boundary lines of polygons) should be used as constraints meaning that no segment boundary should cross such a line
*** 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
** multi-scalar segmentation can significantly improve results and should thus be implemented if possible (see i.smap code for example)
* Similarity measurement
** The squared euclidean distance will be the default similarity measurement. If time allows, Manhattan distance will be added as an option. (Using the square will give same results, we will also square the similarity threshold so the user doesn't need to worry about this detail.
** For the default scaling of the input, the similarity threshold will be 0 to 1. This should be a good intuitive range for the user, 0 being the entire image is one segment and 1 being no segments can be formed. (Internally, this number must be multiplied by the number of rasters in the image group, but again the user doesn't need to worry about the details.) If the user selects the option to skip the normalization function, they will need to be careful how to select this parameter.
* Output
** first (segmentation) module: raster map of segments (i.e. each pixel value represents id of segment the pixel belongs to)
** second (stats) module: one vector map of segments per hierarchy level with a series of attributes (not all of these attributes should probably be calculated directly be the segmentation module)
*** spectral attributes:
**** per spectral band: mean, min, max, skewness
**** combination of bands: brightness, indices (i.e. results of multi-band calculations)
*** textural attributes: stdev (per-band and/or multi-band), mean difference to neighbor, Haralick texture features cf {{cmd|r.texture}}
*** geometric/morphological attributes: area, perimeter, length/width measures, see also {{cmd|r.li}}
*** context attributes: mean difference to all other regions in the same upper hierarchical level, relative localisation within upper hierarchical level, absolute localisation, number of objects in lower level
** depending on segmentation algorithm: raster map indicating for each pixel the probability of belonging to the segment it was put into, i.e. some measure of reliability of results

=== Questions ===

Number of modules: Should the user run one module to create the segments (raster output), then if they are interested, run r.to.vect and run a second module (vector input/output) if they want to get the statistics. (GUI glue to put them in one screen would be a low priority task for time remaining at the end of the summer.) (I wonder if the stats module should take vector or raster as the input, it will also need the original raster.)

"Probability of belonging to the segment": For region growing - should this be the similarity measure when it was merged? Or similarity measure of the pixel compared to the average?
/*ML: Not sure, but I would think that similarity between pixel and average of region it belongs to might be a good choice. Am not a specialist in statistics, but maybe it is possible to translate this into some form of probability of really "belonging" to that region (cf i.maxlik)*/
So this would be a comparison of the pixel to the final segment. Does anyone have a standard measurement that should be used?

4 vs. 8 neighbors: Should this be a user input option? It seems 4 neighbors (no diagonals) is the normal definition for segmentation, but not for other GRASS modules. Update: Using 4 neighbors as default, with optional flag to select 8 neighbors.

Null cells: Is it possible for some pixels inside the image to have null values? If yes, should they just be excluded from the calculation, or merged into the nearest segment? Update: current plan is to ignore all NULL values in the calculations.

Are there any examples of using linear features to constraint segment growth, or will it usually be polygons?

=== Lower priority ===

Add shape characteristics (smoothness, compactness) to the similarity measurement. Similar to eCognition "Multiresolution Segmentation"

It may be useful to do some calculations for the color space (RGB, HSI, L*u*v*, L*a*b*)? (I saw one paper [3] discussing pro/con of different systems, "best" answer is application dependent.)

ML: I would say leave decisions on color space (which is just one portion of feature space) to the user: one can group any kind raster maps with i.group and submit that to segmentation, and so the user can decide whether to use an image represented by different bands in a specific color space, plus any kind of other bands, indices, etc.

= Test Images =

The results of the implemented algorithm should be compared against the results of a similar algorithm implement in other software. The North Carolina GRASS sample location will be used for documentation and manuals.

Carleer [1] used images with 1m resolution from Ikonos, panchromatic band from 08 June 2000, Brussels area.

Should check segmentation results on images from a few different resolutions and different numbers of bands against what is obtained in other software.

Is there a benchmark for processing speed that should be considered? [4]

=Project Plan=

Preparation: Gather ideas from the community! Feature requests, image segmentation literature, and any other ideas and suggestions.

* May 21: Start coding, 8 weeks until Midterm Evaluation
* Week 1: Develop pseudocode to outline the work [http://lists.osgeo.org/pipermail/soc/2012-May/001747.html Report 1]
* Week 2-4: Implement the main algorithm [http://lists.osgeo.org/pipermail/soc/2012-June/001779.html Report 2] [http://lists.osgeo.org/pipermail/soc/2012-June/001804.html Report 3] [http://lists.osgeo.org/pipermail/soc/2012-June/001826.html Report 4]
* Week 5: Add vector maps as a constraint to the segmentation [http://lists.osgeo.org/pipermail/soc/2012-June/001854.html Report 5]
* Week 6: Validation [http://lists.osgeo.org/pipermail/soc/2012-June/001879.html Report 6]
* Week 7: Debugging [http://lists.osgeo.org/pipermail/soc/2012-July/001898.html Report 7]
* Week 8: Contingency time for finishing the above, ensure a solid main program. [http://lists.osgeo.org/pipermail/soc/2012-July/001921.html Report 8]
* July 9: Midterm Evaluation: Evaluate the existing program, determine the plan for the remaining 3-4 weeks. Options include:
* Improving the main algorithm
* Adding control for what scale the segmentation is performed at
* Providing updates to {{cmd|i.maxlik}} to ensure the segmentation output can be used as input for the existing classification functionality
* GUI
* Adding a second image segmentation algorithm

[http://lists.osgeo.org/pipermail/soc/2012-July/001941.html Report 9], [http://lists.osgeo.org/pipermail/soc/2012-July/001960.html Report 10], [http://lists.osgeo.org/pipermail/soc/2012-August/001986.html Report 11], [http://lists.osgeo.org/pipermail/soc/2012-August/002002.html Report 12], [http://lists.osgeo.org/pipermail/soc/2012-August/002041.html Report 13]

= Region Growing Algorithm =

Here is (a start!) for the processing steps, based on SPRING [2]

Region Growing, bottom up processing. Main improvement compared to simple algorithm is to slowly lower the similarity function, so only best matches are made first. This prevents the "first" segment from taking over any unclear areas between it and the next clear segment.

1. Input:
** Seeds: all pixels (Later addition can be alternate seeding methods)
** Similarity Threshold T(t)... as t increases, threshold for similarity is lower. SPRING used: <math>T(t) = T(0) alpha^t </math>, where T(0) > 0, t =0,1,2... and alpha <1
** Size of smallest allowed area (Is this wanted or needed ???)
2. Loop for t
** initialize candidate regions, save mean value vector and neighboring regions (Not sure why this needs to be calculated/saved ahead of time ??)
3. For each region i in candidate region set (first pass this equals the seeds):
** Compare Ri with neighbors (Question: should neighbors include or exclude those regions that were already matched?
** If it exists, Rk is best neighbor if smallest D of all neighbors and and D < T.
** Check Rk's neighbors.
** Merge IF Ri is Rk's best neighbor
** remove from candidate region set. (give all "small" regions a chance to merge with best neighbor before growing larger regions)
** update segment values
** next i
3. next t, with all segments returned to candidate region set, until no regions can be merged

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.

== Functionality ==

<del>1: Implement the 8 neighbor option (currenly only the 4 pixel neighbors are considered).</del> (done)

<del>1: Starting seed pixels for the segments</del> (done)

<del>1: handle null cells in the optional boundary constraints raster.</del> (done)

<del>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.)</del> (documented limitation)

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 (<del>Manhattan</del>, Malahanobis) (Added Manhattan distance)

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.)

== Statistics/metrics ==

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.

== Speed ==

<del>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.</del> implemented, ~20% speed reduction

<del>2: Search continuation. If Ri isn't Rk's best neighbor, then use Rk as the next Ri. (Skips one neighbor finding routine.)</del> TODO: need to decide if this should stay in or out, or as an option. Currently implemented as an option. Need to do some speed tests to see if it is faster or slower after finishing some other changes.

2: Consider peano or other ordering for pixel processing (instead of row major order), should help processing time if an entire "row" of segments are not in RAM.

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.)

== Memory ==

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.)

3: Put segment ID in SEG instead of RAM. (Possibly make this dependent on available RAM?) (Only consider if we run into RAM limitations.)

== Polish ==

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)

== Documentation ==

How to choose parameters, what their impact is.

Typical workflow:

* {{cmd|i.group}}
* i.segment
* {{cmd|r.to.vect}}
* i.segment.metrics and/or {{cmd|i.maxlik}} and/or {{AddonCmd|r.fuzzy}}

= Workflow =

Todo: Some typical workflow examples, type of data, GRASS modules used before and after the image segmentation.

= Results =

== Ortho-photo ==

The [http://grass.osgeo.org/wiki/where_are_these_data link to ortho data is missing] has 3 bands, and the computational region is 1,120,080 cells, at 1-m resolution.

Here's the code used to generate this segmentation result:

i.segment group=ortho output=ortho_segs_ha threshold=0.02 endt=10000 final_mean=ortho_segs_mean_ha min=20 --o

The segmentation performed in 22m53.255s on a Intel i5 laptop with 4Go RAM. The memory consumption was around 38 Mo.

[[File:Raglan_ortho_seg.png]]

== SPOT5 scene ==

The [http://grass.osgeo.org/wiki/where_are_these_data link to SPOT data is missing] has 4 bands, and the computational region is 4,444,517 cells, at 10-m resolution.

Here's the code used to generate this segmentation result:

i.segment group=spot output=spot_seg threshold=0.01 endt=10000 min=30 --o

The segmentation performed in 87m3.870s on a Intel Core 2 workstation with 8Go RAM. The memory consumption was around 170 Mo.

[[File:Taranaki spot seg.png]]

= References =

TODO: complete references with links.

[http://www.armurs.ulb.ac.be/images/8/86/PERS_Carleer_05.pdf] Carleer, et al: Assessment of Very High Spatial Resolution Satellite Image Segmentations, 2005 (Evaluates 2 boundary and 2 region based algorithms.)

[http://marte.dpi.inpe.br/col/sid.inpe.br/deise/1999/02.05.09.30/doc/T205.pdf] Bins, et al: Satellite Imagery Segmentation: A Region Growing Approach, 1996 (Describes approach taken in SPRING software.)

[http://www.sciencedirect.com/science/article/pii/S0031320300001497] Cheng et. al.: Color image segmentation: advances and prospect, 2000 (survey of segmentation methods and color spaces)

[http://www.isprs.org/proceedings/XXXV/congress/comm4/papers/506.pdf] G. Meinel, M. Neubert: A Comparison of Segmentation Programs for High Resolution Remote Sensing Data, 20?? (Includes timing to complete segmentation)

[http://www.wiley.com/WileyCDA/WileyTitle/productCd-0471377392.html?0471377392=] Pitas, I: Digital Image Processing Algorithms and Applications, 2000 (Textbook, including 1 chapter on segmentation methods.)

eCognition Reference Manual

Kurtz et. al: Hierarchical Segmentation of Multiresolution Remote Sensing Images, 2011

Comaniciu, Dorin: Mean Shift: A Robust Approach Toward Feature Space Analysis, 2002

GRASS GSoC 2012 Image Segmentation

2012-08-15T17:58:30Z

⚠️Emomsen: /* Functionality */ updated completed tasks

{{GSoC}}
''(See also other [[GRASS_SoC_Ideas_2012#Accepted_Ideas|GRASS GSoC 2012 projects]])''

{| {{table}}
|Student Name: || Eric Momsen
|-
|Organization: || [http://www.osgeo.org OSGeo - Open Source Geospatial Foundation]
|-
| Mentor Name: || Mentor: Markus Metz (backup mentors: M Lennert, P Roudier)
|-
| Title: || '''Image Segmentation'''
|-
|-
| Repository: || AddOns, browse at: [https://trac.osgeo.org/grass/browser/grass-addons/grass7/imagery/i.segment i.segment]
|-
|}
=Abstract=

GRASS GIS has many imagery related processing capabilities, but the field is rapidly developing and many techniques are not yet implemented. The goal of this GSoC project is to implement the region growing image segmentation algorithm.

Input: Raster map(s) to be segmented (plus optional vector map for a constraint)

Output: To include segmented regions with statistics. This information can be directly used or taken as input to existing image classification modules.

Update: This process will be split into two modules, the first will output a raster map with segments, the second will compute statistics for the segments.

=Background=

Image classification techniques already implemented in GRASS GIS include supervised and unsupervised classification. Classification of images based on pixels can often be very noisy. By first segmenting the image, later classification of 'objects' can be more effective. Noise is reduced, classification speed is increased, and most importantly the classification is performed on objects instead of pixels. The {{cmd|i.smap}} module does include a segmentation step (based on Gaussian mixture distribution), but there does not exist a module intended to segment the image and provide segment data for general use. A summary of the existing methods implemented in GRASS are at [[Image classification]]. Furthermore, the module {{AddonCmd|r.seg}} in GRASS-addons uses internally the Mumford-Shah variational model for image segmentation.

== Segmentation Methods ==

* Boundary Based
** optimal edge detector +
** watershed +
* Region Based
** multilevel thresholding technique +
** region growing +
* Combined boundary/region (is this a correct category for these two?)
** mean-shift
** watershed

Carleer et.al. [1] reviewed 4 methods (marked with + above). Boundary based methods are sensitive to noise and texture, and usually depend on good pre-processing. (Does GRASS already have this pre-processing/filtering?) Good results with urban zones, high contrast. Both region based methods had difficulty with transition zones. Region growing was less sensitive to texture (good for high resolution (1m) images). Multi-level techniques are the only way to get all objects without over-segmentation.

I don't recall the source, but I read in one place that mean-shift could be difficult to apply to very large images, and elsewhere it was mentioned watershed sees more use in greyscale images.

As additional algorithms are added to the module, attention should be given to diversify so algorithms with different strengths are implemented first.

=== Region Growing Variations ===

Even within the region growing label, there are a number of approaches. Here are two described in [5].

1. Growing

Seeds (as a subset of the pixels) are selected (using image histogram, previous knowledge, or other methods). Region growing is done by adding adjacent pixels. No merging of segments is done, only unassigned pixels can be assigned to adjacent regions.

2. Growing and Merging

Use all pixels as seeds, no need to have user figure out a reasonable starting seed selection. Now adjacent segments can be merged.

Is there ever a case where someone may want to start with seeds, but still allow segment merging? Or does that fall into the realm of classification to be done in the next step?

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

== Segmentation Considerations ==

All(?) methods have some input parameter(s) that can be set. These parameters influence if the algorithm will over-segment (one expected region is divided into 2 or more segments) or under-segment (putting two expected regions into one segment). If the segments are used for later classification, over-segmentation should usually get preference to under-segmentation. With extensive over-segmentation, some of the advantages provided by segmentation can be lost, but at least the classification can combine the segments into the expected region. Under-segmentation is more critical, as the classification step will not divide the segment to recover the different regions. (Based on a summary of a number of papers from [1])

In order to respond to the issue of over/under-segmentation, a multiscalar approach would be interesting. This would mean either a top-down approach with a first coarse segmentation (under-segmentation) and the finer segmentation in selected segments, or a bottom-up approach with first a very fine-grained segmentation (over-segmentation) and the regrouping of segments to form higher levels. The first approach can be solved by doing a first segmentation, using certain segments as masks and then relaunching a second segmentation. {Or by using a vector map of the first segmentation as a boundary constraint in the second segmentation.} The second approach requires an algorithm to decide which segments should be combined in a larger higher-level segments. A simple nearest neighbor or kmeans approach based on spectral mean can be used here. In terms of implementation in GRASS, this would probably call for several modules, one for the segmentation, and another for grouping of segments. The latter could be an all-purpose clustering module (and can also be emulated by simple data analysis in the attribute table + {{cmd|v.dissolve}}).

It can sometimes be interesting to do a first segmentation on one band (e.g. panchromatic with higher resolution) and then regroup segments based on multispectral data (possibly weighting bands).

=Main Goal=

Implement an image segmentation method to extend the available options for image processing in GRASS. The region growing method has been selected as a robust general purpose method. An important contribution of the new method will be to include vector maps (for example road networks) as a constraint in growing the segments. Output from the module will include Spectral (mean/variance/range/ect) and Spatial (area/shape/location/etc) data for each region.

=Specifications=

* General considerations
** The general principle in GRASS is KISS, with each module doing one thing. It is to be seen if the result of this project is one single module or rather more than one module each specialised in one task in a segmentation workflow.
** As soon as code is to be (potentially) used in several modules, the use of a library should be envisaged.
** Be able to process large images while being considerate of system memory
* Input
** in the GRASS logic, input should be an image group, <del>or even image subgroup</del>, which can contain any number of raster maps, but generally satellite or areal images that are pre-processed and ready for analysis (i.e. no pre-processing in the module) (Update: subgroups are not often used, there use will not be implemented unless someone asks.)
*** This input group will define the feature space which can include spectral and other continuous (elevation, PCA layers, slope aspect...) and possibly (probably not initially) even discrete data (soil type, land cover...)
*** Default action will be to normalize/scale all input rasters to a 0-1 range. The allows bands (0-255), NDVI, and other numbers to be compared on an equal basis in the distance formula without any preprocessing steps. Since it gives equal weights to all rasters in the input group, a flag will give the user the option to skip this normalization step in case they want to use the actual values.
** optionally vector maps of existing features
*** lines (be it linear features or boundary lines of polygons) should be used as constraints meaning that no segment boundary should cross such a line
*** 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
** multi-scalar segmentation can significantly improve results and should thus be implemented if possible (see i.smap code for example)
* Similarity measurement
** The squared euclidean distance will be the default similarity measurement. If time allows, Manhattan distance will be added as an option. (Using the square will give same results, we will also square the similarity threshold so the user doesn't need to worry about this detail.
** For the default scaling of the input, the similarity threshold will be 0 to 1. This should be a good intuitive range for the user, 0 being the entire image is one segment and 1 being no segments can be formed. (Internally, this number must be multiplied by the number of rasters in the image group, but again the user doesn't need to worry about the details.) If the user selects the option to skip the normalization function, they will need to be careful how to select this parameter.
* Output
** first (segmentation) module: raster map of segments (i.e. each pixel value represents id of segment the pixel belongs to)
** second (stats) module: one vector map of segments per hierarchy level with a series of attributes (not all of these attributes should probably be calculated directly be the segmentation module)
*** spectral attributes:
**** per spectral band: mean, min, max, skewness
**** combination of bands: brightness, indices (i.e. results of multi-band calculations)
*** textural attributes: stdev (per-band and/or multi-band), mean difference to neighbor, Haralick texture features cf {{cmd|r.texture}}
*** geometric/morphological attributes: area, perimeter, length/width measures, see also {{cmd|r.li}}
*** context attributes: mean difference to all other regions in the same upper hierarchical level, relative localisation within upper hierarchical level, absolute localisation, number of objects in lower level
** depending on segmentation algorithm: raster map indicating for each pixel the probability of belonging to the segment it was put into, i.e. some measure of reliability of results

=== Questions ===

Number of modules: Should the user run one module to create the segments (raster output), then if they are interested, run r.to.vect and run a second module (vector input/output) if they want to get the statistics. (GUI glue to put them in one screen would be a low priority task for time remaining at the end of the summer.) (I wonder if the stats module should take vector or raster as the input, it will also need the original raster.)

"Probability of belonging to the segment": For region growing - should this be the similarity measure when it was merged? Or similarity measure of the pixel compared to the average?
/*ML: Not sure, but I would think that similarity between pixel and average of region it belongs to might be a good choice. Am not a specialist in statistics, but maybe it is possible to translate this into some form of probability of really "belonging" to that region (cf i.maxlik)*/
So this would be a comparison of the pixel to the final segment. Does anyone have a standard measurement that should be used?

4 vs. 8 neighbors: Should this be a user input option? It seems 4 neighbors (no diagonals) is the normal definition for segmentation, but not for other GRASS modules. Update: Using 4 neighbors as default, with optional flag to select 8 neighbors.

Null cells: Is it possible for some pixels inside the image to have null values? If yes, should they just be excluded from the calculation, or merged into the nearest segment? Update: current plan is to ignore all NULL values in the calculations.

Are there any examples of using linear features to constraint segment growth, or will it usually be polygons?

=== Lower priority ===

Add shape characteristics (smoothness, compactness) to the similarity measurement. Similar to eCognition "Multiresolution Segmentation"

It may be useful to do some calculations for the color space (RGB, HSI, L*u*v*, L*a*b*)? (I saw one paper [3] discussing pro/con of different systems, "best" answer is application dependent.)

ML: I would say leave decisions on color space (which is just one portion of feature space) to the user: one can group any kind raster maps with i.group and submit that to segmentation, and so the user can decide whether to use an image represented by different bands in a specific color space, plus any kind of other bands, indices, etc.

= Test Images =

The results of the implemented algorithm should be compared against the results of a similar algorithm implement in other software. The North Carolina GRASS sample location will be used for documentation and manuals.

Carleer [1] used images with 1m resolution from Ikonos, panchromatic band from 08 June 2000, Brussels area.

Should check segmentation results on images from a few different resolutions and different numbers of bands against what is obtained in other software.

Is there a benchmark for processing speed that should be considered? [4]

=Project Plan=

Preparation: Gather ideas from the community! Feature requests, image segmentation literature, and any other ideas and suggestions.

* May 21: Start coding, 8 weeks until Midterm Evaluation
* Week 1: Develop pseudocode to outline the work [http://lists.osgeo.org/pipermail/soc/2012-May/001747.html Report 1]
* Week 2-4: Implement the main algorithm [http://lists.osgeo.org/pipermail/soc/2012-June/001779.html Report 2] [http://lists.osgeo.org/pipermail/soc/2012-June/001804.html Report 3] [http://lists.osgeo.org/pipermail/soc/2012-June/001826.html Report 4]
* Week 5: Add vector maps as a constraint to the segmentation
* Week 6: Validation
* Week 7: Debugging
* Week 8: Contingency time for finishing the above, ensure a solid main program.
* July 9: Midterm Evaluation: Evaluate the existing program, determine the plan for the remaining 3-4 weeks. Options include:
* Improving the main algorithm
* Adding control for what scale the segmentation is performed at
* Providing updates to {{cmd|i.maxlik}} to ensure the segmentation output can be used as input for the existing classification functionality
* GUI
* Adding a second image segmentation algorithm

= Region Growing Algorithm =

Here is (a start!) for the processing steps, based on SPRING [2]

Region Growing, bottom up processing. Main improvement compared to simple algorithm is to slowly lower the similarity function, so only best matches are made first. This prevents the "first" segment from taking over any unclear areas between it and the next clear segment.

1. Input:
** Seeds: all pixels (Later addition can be alternate seeding methods)
** Similarity Threshold T(t)... as t increases, threshold for similarity is lower. SPRING used: <math>T(t) = T(0) alpha^t </math>, where T(0) > 0, t =0,1,2... and alpha <1
** Size of smallest allowed area (Is this wanted or needed ???)
2. Loop for t
** initialize candidate regions, save mean value vector and neighboring regions (Not sure why this needs to be calculated/saved ahead of time ??)
3. For each region i in candidate region set (first pass this equals the seeds):
** Compare Ri with neighbors (Question: should neighbors include or exclude those regions that were already matched?
** If it exists, Rk is best neighbor if smallest D of all neighbors and and D < T.
** Check Rk's neighbors.
** Merge IF Ri is Rk's best neighbor
** remove from candidate region set. (give all "small" regions a chance to merge with best neighbor before growing larger regions)
** update segment values
** next i
3. next t, with all segments returned to candidate region set, until no regions can be merged

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.

== Functionality ==

<del>1: Implement the 8 neighbor option (currenly only the 4 pixel neighbors are considered).</del> (done)

<del>1: Starting seed pixels for the segments</del> (done)

<del>1: handle null cells in the optional boundary constraints raster.</del> (done)

<del>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.)</del> (documented limitation)

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 (<del>Manhattan</del>, Malahanobis) (Added Manhattan distance)

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.)

== Statistics/metrics ==

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.

== Speed ==

<del>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.</del> implemented, ~20% speed reduction

<del>2: Search continuation. If Ri isn't Rk's best neighbor, then use Rk as the next Ri. (Skips one neighbor finding routine.)</del> TODO: need to decide if this should stay in or out, or as an option. Currently implemented as an option. Need to do some speed tests to see if it is faster or slower after finishing some other changes.

2: Consider peano or other ordering for pixel processing (instead of row major order), should help processing time if an entire "row" of segments are not in RAM.

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.)

== Memory ==

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.)

3: Put segment ID in SEG instead of RAM. (Possibly make this dependent on available RAM?) (Only consider if we run into RAM limitations.)

== Polish ==

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)

== Documentation ==

How to choose parameters, what their impact is.

Typical workflow:

* {{cmd|i.group}}
* i.segment
* {{cmd|r.to.vect}}
* i.segment.metrics and/or {{cmd|i.maxlik}} and/or {{AddonCmd|r.fuzzy}}

= Workflow =

Todo: Some typical workflow examples, type of data, GRASS modules used before and after the image segmentation.

= Results =

== Ortho-photo ==

The [http://grass.osgeo.org/wiki/where_are_these_data link to ortho data is missing] has 3 bands, and the computational region is 1,120,080 cells, at 1-m resolution.

Here's the code used to generate this segmentation result:

i.segment group=ortho output=ortho_segs_ha threshold=0.02 endt=10000 final_mean=ortho_segs_mean_ha min=20 --o

The segmentation performed in 22m53.255s on a Intel i5 laptop with 4Go RAM. The memory consumption was around 38 Mo.

[[File:Raglan_ortho_seg.png]]

== SPOT5 scene ==

The [http://grass.osgeo.org/wiki/where_are_these_data link to SPOT data is missing] has 4 bands, and the computational region is 4,444,517 cells, at 10-m resolution.

Here's the code used to generate this segmentation result:

i.segment group=spot output=spot_seg threshold=0.01 endt=10000 min=30 --o

The segmentation performed in 87m3.870s on a Intel Core 2 workstation with 8Go RAM. The memory consumption was around 170 Mo.

[[File:Taranaki spot seg.png]]

= References =

TODO: complete references with links.

[http://www.armurs.ulb.ac.be/images/8/86/PERS_Carleer_05.pdf] Carleer, et al: Assessment of Very High Spatial Resolution Satellite Image Segmentations, 2005 (Evaluates 2 boundary and 2 region based algorithms.)

[http://marte.dpi.inpe.br/col/sid.inpe.br/deise/1999/02.05.09.30/doc/T205.pdf] Bins, et al: Satellite Imagery Segmentation: A Region Growing Approach, 1996 (Describes approach taken in SPRING software.)

[http://www.sciencedirect.com/science/article/pii/S0031320300001497] Cheng et. al.: Color image segmentation: advances and prospect, 2000 (survey of segmentation methods and color spaces)

[http://www.isprs.org/proceedings/XXXV/congress/comm4/papers/506.pdf] G. Meinel, M. Neubert: A Comparison of Segmentation Programs for High Resolution Remote Sensing Data, 20?? (Includes timing to complete segmentation)

[http://www.wiley.com/WileyCDA/WileyTitle/productCd-0471377392.html?0471377392=] Pitas, I: Digital Image Processing Algorithms and Applications, 2000 (Textbook, including 1 chapter on segmentation methods.)

eCognition Reference Manual

Kurtz et. al: Hierarchical Segmentation of Multiresolution Remote Sensing Images, 2011

Comaniciu, Dorin: Mean Shift: A Robust Approach Toward Feature Space Analysis, 2002

GRASS GSoC 2012 Image Segmentation

2012-07-24T14:02:04Z

⚠️Emomsen: /* Speed */ crossed off two items

{{GSoC}}
''(See also other [[GRASS_SoC_Ideas_2012#Accepted_Ideas|GRASS GSoC 2012 projects]])''

{| {{table}}
|Student Name: || Eric Momsen
|-
|Organization: || [http://www.osgeo.org OSGeo - Open Source Geospatial Foundation]
|-
| Mentor Name: || Mentor: Markus Metz (backup mentors: M Lennert, P Roudier)
|-
| Title: || '''Image Segmentation'''
|-
|-
| Repository: || AddOns, browse at: [https://trac.osgeo.org/grass/browser/grass-addons/grass7/imagery/i.segment i.segment]
|-
|}
=Abstract=

GRASS GIS has many imagery related processing capabilities, but the field is rapidly developing and many techniques are not yet implemented. The goal of this GSoC project is to implement the region growing image segmentation algorithm.

Input: Raster map(s) to be segmented (plus optional vector map for a constraint)

Output: To include segmented regions with statistics. This information can be directly used or taken as input to existing image classification modules.

Update: This process will be split into two modules, the first will output a raster map with segments, the second will compute statistics for the segments.

=Background=

Image classification techniques already implemented in GRASS GIS include supervised and unsupervised classification. Classification of images based on pixels can often be very noisy. By first segmenting the image, later classification of 'objects' can be more effective. Noise is reduced, classification speed is increased, and most importantly the classification is performed on objects instead of pixels. The {{cmd|i.smap}} module does include a segmentation step (based on Gaussian mixture distribution), but there does not exist a module intended to segment the image and provide segment data for general use. A summary of the existing methods implemented in GRASS are at [[Image classification]]. Furthermore, the module {{AddonCmd|r.seg}} in GRASS-addons uses internally the Mumford-Shah variational model for image segmentation.

== Segmentation Methods ==

* Boundary Based
** optimal edge detector +
** watershed +
* Region Based
** multilevel thresholding technique +
** region growing +
* Combined boundary/region (is this a correct category for these two?)
** mean-shift
** watershed

Carleer et.al. [1] reviewed 4 methods (marked with + above). Boundary based methods are sensitive to noise and texture, and usually depend on good pre-processing. (Does GRASS already have this pre-processing/filtering?) Good results with urban zones, high contrast. Both region based methods had difficulty with transition zones. Region growing was less sensitive to texture (good for high resolution (1m) images). Multi-level techniques are the only way to get all objects without over-segmentation.

I don't recall the source, but I read in one place that mean-shift could be difficult to apply to very large images, and elsewhere it was mentioned watershed sees more use in greyscale images.

As additional algorithms are added to the module, attention should be given to diversify so algorithms with different strengths are implemented first.

=== Region Growing Variations ===

Even within the region growing label, there are a number of approaches. Here are two described in [5].

1. Growing

Seeds (as a subset of the pixels) are selected (using image histogram, previous knowledge, or other methods). Region growing is done by adding adjacent pixels. No merging of segments is done, only unassigned pixels can be assigned to adjacent regions.

2. Growing and Merging

Use all pixels as seeds, no need to have user figure out a reasonable starting seed selection. Now adjacent segments can be merged.

Is there ever a case where someone may want to start with seeds, but still allow segment merging? Or does that fall into the realm of classification to be done in the next step?

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

== Segmentation Considerations ==

All(?) methods have some input parameter(s) that can be set. These parameters influence if the algorithm will over-segment (one expected region is divided into 2 or more segments) or under-segment (putting two expected regions into one segment). If the segments are used for later classification, over-segmentation should usually get preference to under-segmentation. With extensive over-segmentation, some of the advantages provided by segmentation can be lost, but at least the classification can combine the segments into the expected region. Under-segmentation is more critical, as the classification step will not divide the segment to recover the different regions. (Based on a summary of a number of papers from [1])

In order to respond to the issue of over/under-segmentation, a multiscalar approach would be interesting. This would mean either a top-down approach with a first coarse segmentation (under-segmentation) and the finer segmentation in selected segments, or a bottom-up approach with first a very fine-grained segmentation (over-segmentation) and the regrouping of segments to form higher levels. The first approach can be solved by doing a first segmentation, using certain segments as masks and then relaunching a second segmentation. {Or by using a vector map of the first segmentation as a boundary constraint in the second segmentation.} The second approach requires an algorithm to decide which segments should be combined in a larger higher-level segments. A simple nearest neighbor or kmeans approach based on spectral mean can be used here. In terms of implementation in GRASS, this would probably call for several modules, one for the segmentation, and another for grouping of segments. The latter could be an all-purpose clustering module (and can also be emulated by simple data analysis in the attribute table + {{cmd|v.dissolve}}).

It can sometimes be interesting to do a first segmentation on one band (e.g. panchromatic with higher resolution) and then regroup segments based on multispectral data (possibly weighting bands).

=Main Goal=

Implement an image segmentation method to extend the available options for image processing in GRASS. The region growing method has been selected as a robust general purpose method. An important contribution of the new method will be to include vector maps (for example road networks) as a constraint in growing the segments. Output from the module will include Spectral (mean/variance/range/ect) and Spatial (area/shape/location/etc) data for each region.

=Specifications=

* General considerations
** The general principle in GRASS is KISS, with each module doing one thing. It is to be seen if the result of this project is one single module or rather more than one module each specialised in one task in a segmentation workflow.
** As soon as code is to be (potentially) used in several modules, the use of a library should be envisaged.
** Be able to process large images while being considerate of system memory
* Input
** in the GRASS logic, input should be an image group, <del>or even image subgroup</del>, which can contain any number of raster maps, but generally satellite or areal images that are pre-processed and ready for analysis (i.e. no pre-processing in the module) (Update: subgroups are not often used, there use will not be implemented unless someone asks.)
*** This input group will define the feature space which can include spectral and other continuous (elevation, PCA layers, slope aspect...) and possibly (probably not initially) even discrete data (soil type, land cover...)
*** Default action will be to normalize/scale all input rasters to a 0-1 range. The allows bands (0-255), NDVI, and other numbers to be compared on an equal basis in the distance formula without any preprocessing steps. Since it gives equal weights to all rasters in the input group, a flag will give the user the option to skip this normalization step in case they want to use the actual values.
** optionally vector maps of existing features
*** lines (be it linear features or boundary lines of polygons) should be used as constraints meaning that no segment boundary should cross such a line
*** 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
** multi-scalar segmentation can significantly improve results and should thus be implemented if possible (see i.smap code for example)
* Similarity measurement
** The squared euclidean distance will be the default similarity measurement. If time allows, Manhattan distance will be added as an option. (Using the square will give same results, we will also square the similarity threshold so the user doesn't need to worry about this detail.
** For the default scaling of the input, the similarity threshold will be 0 to 1. This should be a good intuitive range for the user, 0 being the entire image is one segment and 1 being no segments can be formed. (Internally, this number must be multiplied by the number of rasters in the image group, but again the user doesn't need to worry about the details.) If the user selects the option to skip the normalization function, they will need to be careful how to select this parameter.
* Output
** first (segmentation) module: raster map of segments (i.e. each pixel value represents id of segment the pixel belongs to)
** second (stats) module: one vector map of segments per hierarchy level with a series of attributes (not all of these attributes should probably be calculated directly be the segmentation module)
*** spectral attributes:
**** per spectral band: mean, min, max, skewness
**** combination of bands: brightness, indices (i.e. results of multi-band calculations)
*** textural attributes: stdev (per-band and/or multi-band), mean difference to neighbor, Haralick texture features cf {{cmd|r.texture}}
*** geometric/morphological attributes: area, perimeter, length/width measures, see also {{cmd|r.li}}
*** context attributes: mean difference to all other regions in the same upper hierarchical level, relative localisation within upper hierarchical level, absolute localisation, number of objects in lower level
** depending on segmentation algorithm: raster map indicating for each pixel the probability of belonging to the segment it was put into, i.e. some measure of reliability of results

=== Questions ===

Number of modules: Should the user run one module to create the segments (raster output), then if they are interested, run r.to.vect and run a second module (vector input/output) if they want to get the statistics. (GUI glue to put them in one screen would be a low priority task for time remaining at the end of the summer.) (I wonder if the stats module should take vector or raster as the input, it will also need the original raster.)

"Probability of belonging to the segment": For region growing - should this be the similarity measure when it was merged? Or similarity measure of the pixel compared to the average?
/*ML: Not sure, but I would think that similarity between pixel and average of region it belongs to might be a good choice. Am not a specialist in statistics, but maybe it is possible to translate this into some form of probability of really "belonging" to that region (cf i.maxlik)*/
So this would be a comparison of the pixel to the final segment. Does anyone have a standard measurement that should be used?

4 vs. 8 neighbors: Should this be a user input option? It seems 4 neighbors (no diagonals) is the normal definition for segmentation, but not for other GRASS modules. Update: Using 4 neighbors as default, with optional flag to select 8 neighbors.

Null cells: Is it possible for some pixels inside the image to have null values? If yes, should they just be excluded from the calculation, or merged into the nearest segment? Update: current plan is to ignore all NULL values in the calculations.

Are there any examples of using linear features to constraint segment growth, or will it usually be polygons?

=== Lower priority ===

Add shape characteristics (smoothness, compactness) to the similarity measurement. Similar to eCognition "Multiresolution Segmentation"

It may be useful to do some calculations for the color space (RGB, HSI, L*u*v*, L*a*b*)? (I saw one paper [3] discussing pro/con of different systems, "best" answer is application dependent.)

ML: I would say leave decisions on color space (which is just one portion of feature space) to the user: one can group any kind raster maps with i.group and submit that to segmentation, and so the user can decide whether to use an image represented by different bands in a specific color space, plus any kind of other bands, indices, etc.

= Test Images =

The results of the implemented algorithm should be compared against the results of a similar algorithm implement in other software. The North Carolina GRASS sample location will be used for documentation and manuals.

Carleer [1] used images with 1m resolution from Ikonos, panchromatic band from 08 June 2000, Brussels area.

Should check segmentation results on images from a few different resolutions and different numbers of bands against what is obtained in other software.

Is there a benchmark for processing speed that should be considered? [4]

=Project Plan=

Preparation: Gather ideas from the community! Feature requests, image segmentation literature, and any other ideas and suggestions.

* May 21: Start coding, 8 weeks until Midterm Evaluation
* Week 1: Develop pseudocode to outline the work [http://lists.osgeo.org/pipermail/soc/2012-May/001747.html Report 1]
* Week 2-4: Implement the main algorithm [http://lists.osgeo.org/pipermail/soc/2012-June/001779.html Report 2] [http://lists.osgeo.org/pipermail/soc/2012-June/001804.html Report 3] [http://lists.osgeo.org/pipermail/soc/2012-June/001826.html Report 4]
* Week 5: Add vector maps as a constraint to the segmentation
* Week 6: Validation
* Week 7: Debugging
* Week 8: Contingency time for finishing the above, ensure a solid main program.
* July 9: Midterm Evaluation: Evaluate the existing program, determine the plan for the remaining 3-4 weeks. Options include:
* Improving the main algorithm
* Adding control for what scale the segmentation is performed at
* Providing updates to {{cmd|i.maxlik}} to ensure the segmentation output can be used as input for the existing classification functionality
* GUI
* Adding a second image segmentation algorithm

= Region Growing Algorithm =

Here is (a start!) for the processing steps, based on SPRING [2]

Region Growing, bottom up processing. Main improvement compared to simple algorithm is to slowly lower the similarity function, so only best matches are made first. This prevents the "first" segment from taking over any unclear areas between it and the next clear segment.

1. Input:
** Seeds: all pixels (Later addition can be alternate seeding methods)
** Similarity Threshold T(t)... as t increases, threshold for similarity is lower. SPRING used: <math>T(t) = T(0) alpha^t </math>, where T(0) > 0, t =0,1,2... and alpha <1
** Size of smallest allowed area (Is this wanted or needed ???)
2. Loop for t
** initialize candidate regions, save mean value vector and neighboring regions (Not sure why this needs to be calculated/saved ahead of time ??)
3. For each region i in candidate region set (first pass this equals the seeds):
** Compare Ri with neighbors (Question: should neighbors include or exclude those regions that were already matched?
** If it exists, Rk is best neighbor if smallest D of all neighbors and and D < T.
** Check Rk's neighbors.
** Merge IF Ri is Rk's best neighbor
** remove from candidate region set. (give all "small" regions a chance to merge with best neighbor before growing larger regions)
** update segment values
** next i
3. next t, with all segments returned to candidate region set, until no regions can be merged

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.

== Functionality ==

<del>1: Implement the 8 neighbor option (currenly only the 4 pixel neighbors are considered).</del> (done)

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.)

== Statistics/metrics ==

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.

== Speed ==

<del>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.</del> implemented, ~20% speed reduction

<del>2: Search continuation. If Ri isn't Rk's best neighbor, then use Rk as the next Ri. (Skips one neighbor finding routine.)</del> TODO: need to decide if this should stay in or out, or as an option. Currently implemented as an option. Need to do some speed tests to see if it is faster or slower after finishing some other changes.

2: Consider peano or other ordering for pixel processing (instead of row major order), should help processing time if an entire "row" of segments are not in RAM.

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.)

== Memory ==

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.)

3: Put segment ID in SEG instead of RAM. (Possibly make this dependent on available RAM?) (Only consider if we run into RAM limitations.)

== Polish ==

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)

== Documentation ==

How to choose parameters, what their impact is.

Typical workflow:

* {{cmd|i.group}}
* i.segment
* {{cmd|r.to.vect}}
* i.segment.metrics and/or {{cmd|i.maxlik}} and/or {{AddonCmd|r.fuzzy}}

= Workflow =

Todo: Some typical workflow examples, type of data, GRASS modules used before and after the image segmentation.

= Results =

== Ortho-photo ==

The [http://grass.osgeo.org/wiki/where_are_these_data link to ortho data is missing] has 3 bands, and the computational region is 1,120,080 cells, at 1-m resolution.

Here's the code used to generate this segmentation result:

i.segment group=ortho output=ortho_segs_ha threshold=0.02 endt=10000 final_mean=ortho_segs_mean_ha min=20 --o

The segmentation performed in 22m53.255s on a Intel i5 laptop with 4Go RAM. The memory consumption was around 38 Mo.

[[File:Raglan_ortho_seg.png]]

== SPOT5 scene ==

The [http://grass.osgeo.org/wiki/where_are_these_data link to SPOT data is missing] has 4 bands, and the computational region is 4,444,517 cells, at 10-m resolution.

Here's the code used to generate this segmentation result:

i.segment group=spot output=spot_seg threshold=0.01 endt=10000 min=30 --o

The segmentation performed in 87m3.870s on a Intel Core 2 workstation with 8Go RAM. The memory consumption was around 170 Mo.

[[File:Taranaki spot seg.png]]

= References =

TODO: complete references with links.

[http://www.armurs.ulb.ac.be/images/8/86/PERS_Carleer_05.pdf] Carleer, et al: Assessment of Very High Spatial Resolution Satellite Image Segmentations, 2005 (Evaluates 2 boundary and 2 region based algorithms.)

[http://marte.dpi.inpe.br/col/sid.inpe.br/deise/1999/02.05.09.30/doc/T205.pdf] Bins, et al: Satellite Imagery Segmentation: A Region Growing Approach, 1996 (Describes approach taken in SPRING software.)

[http://www.sciencedirect.com/science/article/pii/S0031320300001497] Cheng et. al.: Color image segmentation: advances and prospect, 2000 (survey of segmentation methods and color spaces)

[http://www.isprs.org/proceedings/XXXV/congress/comm4/papers/506.pdf] G. Meinel, M. Neubert: A Comparison of Segmentation Programs for High Resolution Remote Sensing Data, 20?? (Includes timing to complete segmentation)

[http://www.wiley.com/WileyCDA/WileyTitle/productCd-0471377392.html?0471377392=] Pitas, I: Digital Image Processing Algorithms and Applications, 2000 (Textbook, including 1 chapter on segmentation methods.)

eCognition Reference Manual

Kurtz et. al: Hierarchical Segmentation of Multiresolution Remote Sensing Images, 2011

Comaniciu, Dorin: Mean Shift: A Robust Approach Toward Feature Space Analysis, 2002

GRASS GSoC 2012 Image Segmentation

2012-07-17T18:32:04Z

⚠️Emomsen: /* Functionality */ implemented 8 neighbors

{{GSoC}}
''(See also other [[GRASS_SoC_Ideas_2012#Accepted_Ideas|GRASS GSoC 2012 projects]])''

{| {{table}}
|Student Name: || Eric Momsen
|-
|Organization: || [http://www.osgeo.org OSGeo - Open Source Geospatial Foundation]
|-
| Mentor Name: || Mentor: Markus Metz (backup mentors: M Lennert, P Roudier)
|-
| Title: || '''Image Segmentation'''
|-
|-
| Repository: || AddOns, browse at: [https://trac.osgeo.org/grass/browser/grass-addons/grass7/imagery/i.segment i.segment]
|-
|}
=Abstract=

GRASS GIS has many imagery related processing capabilities, but the field is rapidly developing and many techniques are not yet implemented. The goal of this GSoC project is to implement the region growing image segmentation algorithm.

Input: Raster map(s) to be segmented (plus optional vector map for a constraint)

Output: To include segmented regions with statistics. This information can be directly used or taken as input to existing image classification modules.

Update: This process will be split into two modules, the first will output a raster map with segments, the second will compute statistics for the segments.

=Background=

Image classification techniques already implemented in GRASS GIS include supervised and unsupervised classification. Classification of images based on pixels can often be very noisy. By first segmenting the image, later classification of 'objects' can be more effective. Noise is reduced, classification speed is increased, and most importantly the classification is performed on objects instead of pixels. The {{cmd|i.smap}} module does include a segmentation step (based on Gaussian mixture distribution), but there does not exist a module intended to segment the image and provide segment data for general use. A summary of the existing methods implemented in GRASS are at [[Image classification]]. Furthermore, the module {{AddonCmd|r.seg}} in GRASS-addons uses internally the Mumford-Shah variational model for image segmentation.

== Segmentation Methods ==

* Boundary Based
** optimal edge detector +
** watershed +
* Region Based
** multilevel thresholding technique +
** region growing +
* Combined boundary/region (is this a correct category for these two?)
** mean-shift
** watershed

Carleer et.al. [1] reviewed 4 methods (marked with + above). Boundary based methods are sensitive to noise and texture, and usually depend on good pre-processing. (Does GRASS already have this pre-processing/filtering?) Good results with urban zones, high contrast. Both region based methods had difficulty with transition zones. Region growing was less sensitive to texture (good for high resolution (1m) images). Multi-level techniques are the only way to get all objects without over-segmentation.

I don't recall the source, but I read in one place that mean-shift could be difficult to apply to very large images, and elsewhere it was mentioned watershed sees more use in greyscale images.

As additional algorithms are added to the module, attention should be given to diversify so algorithms with different strengths are implemented first.

=== Region Growing Variations ===

Even within the region growing label, there are a number of approaches. Here are two described in [5].

1. Growing

Seeds (as a subset of the pixels) are selected (using image histogram, previous knowledge, or other methods). Region growing is done by adding adjacent pixels. No merging of segments is done, only unassigned pixels can be assigned to adjacent regions.

2. Growing and Merging

Use all pixels as seeds, no need to have user figure out a reasonable starting seed selection. Now adjacent segments can be merged.

Is there ever a case where someone may want to start with seeds, but still allow segment merging? Or does that fall into the realm of classification to be done in the next step?

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

== Segmentation Considerations ==

All(?) methods have some input parameter(s) that can be set. These parameters influence if the algorithm will over-segment (one expected region is divided into 2 or more segments) or under-segment (putting two expected regions into one segment). If the segments are used for later classification, over-segmentation should usually get preference to under-segmentation. With extensive over-segmentation, some of the advantages provided by segmentation can be lost, but at least the classification can combine the segments into the expected region. Under-segmentation is more critical, as the classification step will not divide the segment to recover the different regions. (Based on a summary of a number of papers from [1])

In order to respond to the issue of over/under-segmentation, a multiscalar approach would be interesting. This would mean either a top-down approach with a first coarse segmentation (under-segmentation) and the finer segmentation in selected segments, or a bottom-up approach with first a very fine-grained segmentation (over-segmentation) and the regrouping of segments to form higher levels. The first approach can be solved by doing a first segmentation, using certain segments as masks and then relaunching a second segmentation. {Or by using a vector map of the first segmentation as a boundary constraint in the second segmentation.} The second approach requires an algorithm to decide which segments should be combined in a larger higher-level segments. A simple nearest neighbor or kmeans approach based on spectral mean can be used here. In terms of implementation in GRASS, this would probably call for several modules, one for the segmentation, and another for grouping of segments. The latter could be an all-purpose clustering module (and can also be emulated by simple data analysis in the attribute table + {{cmd|v.dissolve}}).

It can sometimes be interesting to do a first segmentation on one band (e.g. panchromatic with higher resolution) and then regroup segments based on multispectral data (possibly weighting bands).

=Main Goal=

Implement an image segmentation method to extend the available options for image processing in GRASS. The region growing method has been selected as a robust general purpose method. An important contribution of the new method will be to include vector maps (for example road networks) as a constraint in growing the segments. Output from the module will include Spectral (mean/variance/range/ect) and Spatial (area/shape/location/etc) data for each region.

=Specifications=

* General considerations
** The general principle in GRASS is KISS, with each module doing one thing. It is to be seen if the result of this project is one single module or rather more than one module each specialised in one task in a segmentation workflow.
** As soon as code is to be (potentially) used in several modules, the use of a library should be envisaged.
** Be able to process large images while being considerate of system memory
* Input
** in the GRASS logic, input should be an image group, <del>or even image subgroup</del>, which can contain any number of raster maps, but generally satellite or areal images that are pre-processed and ready for analysis (i.e. no pre-processing in the module) (Update: subgroups are not often used, there use will not be implemented unless someone asks.)
*** This input group will define the feature space which can include spectral and other continuous (elevation, PCA layers, slope aspect...) and possibly (probably not initially) even discrete data (soil type, land cover...)
*** Default action will be to normalize/scale all input rasters to a 0-1 range. The allows bands (0-255), NDVI, and other numbers to be compared on an equal basis in the distance formula without any preprocessing steps. Since it gives equal weights to all rasters in the input group, a flag will give the user the option to skip this normalization step in case they want to use the actual values.
** optionally vector maps of existing features
*** lines (be it linear features or boundary lines of polygons) should be used as constraints meaning that no segment boundary should cross such a line
*** 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
** multi-scalar segmentation can significantly improve results and should thus be implemented if possible (see i.smap code for example)
* Similarity measurement
** The squared euclidean distance will be the default similarity measurement. If time allows, Manhattan distance will be added as an option. (Using the square will give same results, we will also square the similarity threshold so the user doesn't need to worry about this detail.
** For the default scaling of the input, the similarity threshold will be 0 to 1. This should be a good intuitive range for the user, 0 being the entire image is one segment and 1 being no segments can be formed. (Internally, this number must be multiplied by the number of rasters in the image group, but again the user doesn't need to worry about the details.) If the user selects the option to skip the normalization function, they will need to be careful how to select this parameter.
* Output
** first (segmentation) module: raster map of segments (i.e. each pixel value represents id of segment the pixel belongs to)
** second (stats) module: one vector map of segments per hierarchy level with a series of attributes (not all of these attributes should probably be calculated directly be the segmentation module)
*** spectral attributes:
**** per spectral band: mean, min, max, skewness
**** combination of bands: brightness, indices (i.e. results of multi-band calculations)
*** textural attributes: stdev (per-band and/or multi-band), mean difference to neighbor, Haralick texture features cf {{cmd|r.texture}}
*** geometric/morphological attributes: area, perimeter, length/width measures, see also {{cmd|r.li}}
*** context attributes: mean difference to all other regions in the same upper hierarchical level, relative localisation within upper hierarchical level, absolute localisation, number of objects in lower level
** depending on segmentation algorithm: raster map indicating for each pixel the probability of belonging to the segment it was put into, i.e. some measure of reliability of results

=== Questions ===

Number of modules: Should the user run one module to create the segments (raster output), then if they are interested, run r.to.vect and run a second module (vector input/output) if they want to get the statistics. (GUI glue to put them in one screen would be a low priority task for time remaining at the end of the summer.) (I wonder if the stats module should take vector or raster as the input, it will also need the original raster.)

"Probability of belonging to the segment": For region growing - should this be the similarity measure when it was merged? Or similarity measure of the pixel compared to the average?
/*ML: Not sure, but I would think that similarity between pixel and average of region it belongs to might be a good choice. Am not a specialist in statistics, but maybe it is possible to translate this into some form of probability of really "belonging" to that region (cf i.maxlik)*/
So this would be a comparison of the pixel to the final segment. Does anyone have a standard measurement that should be used?

4 vs. 8 neighbors: Should this be a user input option? It seems 4 neighbors (no diagonals) is the normal definition for segmentation, but not for other GRASS modules. Update: Using 4 neighbors as default, with optional flag to select 8 neighbors.

Null cells: Is it possible for some pixels inside the image to have null values? If yes, should they just be excluded from the calculation, or merged into the nearest segment? Update: current plan is to ignore all NULL values in the calculations.

Are there any examples of using linear features to constraint segment growth, or will it usually be polygons?

=== Lower priority ===

Add shape characteristics (smoothness, compactness) to the similarity measurement. Similar to eCognition "Multiresolution Segmentation"

It may be useful to do some calculations for the color space (RGB, HSI, L*u*v*, L*a*b*)? (I saw one paper [3] discussing pro/con of different systems, "best" answer is application dependent.)

ML: I would say leave decisions on color space (which is just one portion of feature space) to the user: one can group any kind raster maps with i.group and submit that to segmentation, and so the user can decide whether to use an image represented by different bands in a specific color space, plus any kind of other bands, indices, etc.

= Test Images =

The results of the implemented algorithm should be compared against the results of a similar algorithm implement in other software. The North Carolina GRASS sample location will be used for documentation and manuals.

Carleer [1] used images with 1m resolution from Ikonos, panchromatic band from 08 June 2000, Brussels area.

Should check segmentation results on images from a few different resolutions and different numbers of bands against what is obtained in other software.

Is there a benchmark for processing speed that should be considered? [4]

=Project Plan=

Preparation: Gather ideas from the community! Feature requests, image segmentation literature, and any other ideas and suggestions.

* May 21: Start coding, 8 weeks until Midterm Evaluation
* Week 1: Develop pseudocode to outline the work [http://lists.osgeo.org/pipermail/soc/2012-May/001747.html Report 1]
* Week 2-4: Implement the main algorithm [http://lists.osgeo.org/pipermail/soc/2012-June/001779.html Report 2] [http://lists.osgeo.org/pipermail/soc/2012-June/001804.html Report 3] [http://lists.osgeo.org/pipermail/soc/2012-June/001826.html Report 4]
* Week 5: Add vector maps as a constraint to the segmentation
* Week 6: Validation
* Week 7: Debugging
* Week 8: Contingency time for finishing the above, ensure a solid main program.
* July 9: Midterm Evaluation: Evaluate the existing program, determine the plan for the remaining 3-4 weeks. Options include:
* Improving the main algorithm
* Adding control for what scale the segmentation is performed at
* Providing updates to {{cmd|i.maxlik}} to ensure the segmentation output can be used as input for the existing classification functionality
* GUI
* Adding a second image segmentation algorithm

= Region Growing Algorithm =

Here is (a start!) for the processing steps, based on SPRING [2]

Region Growing, bottom up processing. Main improvement compared to simple algorithm is to slowly lower the similarity function, so only best matches are made first. This prevents the "first" segment from taking over any unclear areas between it and the next clear segment.

1. Input:
** Seeds: all pixels (Later addition can be alternate seeding methods)
** Similarity Threshold T(t)... as t increases, threshold for similarity is lower. SPRING used: <math>T(t) = T(0) alpha^t </math>, where T(0) > 0, t =0,1,2... and alpha <1
** Size of smallest allowed area (Is this wanted or needed ???)
2. Loop for t
** initialize candidate regions, save mean value vector and neighboring regions (Not sure why this needs to be calculated/saved ahead of time ??)
3. For each region i in candidate region set (first pass this equals the seeds):
** Compare Ri with neighbors (Question: should neighbors include or exclude those regions that were already matched?
** If it exists, Rk is best neighbor if smallest D of all neighbors and and D < T.
** Check Rk's neighbors.
** Merge IF Ri is Rk's best neighbor
** remove from candidate region set. (give all "small" regions a chance to merge with best neighbor before growing larger regions)
** update segment values
** next i
3. next t, with all segments returned to candidate region set, until no regions can be merged

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.

== Functionality ==

<del>1: Implement the 8 neighbor option (currenly only the 4 pixel neighbors are considered).</del> (done)

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.)

== Statistics/metrics ==

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.

== Speed ==

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.)

2: Consider peano or other ordering for pixel processing (instead of row major order), should help processing time if an entire "row" of segments are not in RAM.

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.)

== Memory ==

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.)

3: Put segment ID in SEG instead of RAM. (Possibly make this dependent on available RAM?) (Only consider if we run into RAM limitations.)

== Polish ==

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)

== Documentation ==

How to choose parameters, what their impact is.

Typical workflow:

* {{cmd|i.group}}
* i.segment
* {{cmd|r.to.vect}}
* i.segment.metrics and/or {{cmd|i.maxlik}} and/or {{AddonCmd|r.fuzzy}}

= Workflow =

Todo: Some typical workflow examples, type of data, GRASS modules used before and after the image segmentation.

= Results =

== Ortho-photo ==

The [http://grass.osgeo.org/wiki/where_are_these_data link to ortho data is missing] has 3 bands, and the computational region is 1,120,080 cells, at 1-m resolution.

Here's the code used to generate this segmentation result:

i.segment group=ortho output=ortho_segs_ha threshold=0.02 endt=10000 final_mean=ortho_segs_mean_ha min=20 --o

The segmentation performed in 22m53.255s on a Intel i5 laptop with 4Go RAM. The memory consumption was around 38 Mo.

[[File:Raglan_ortho_seg.png]]

== SPOT5 scene ==

The [http://grass.osgeo.org/wiki/where_are_these_data link to SPOT data is missing] has 4 bands, and the computational region is 4,444,517 cells, at 10-m resolution.

Here's the code used to generate this segmentation result:

i.segment group=spot output=spot_seg threshold=0.01 endt=10000 min=30 --o

The segmentation performed in 87m3.870s on a Intel Core 2 workstation with 8Go RAM. The memory consumption was around 170 Mo.

[[File:Taranaki spot seg.png]]

= References =

TODO: complete references with links.

[http://www.armurs.ulb.ac.be/images/8/86/PERS_Carleer_05.pdf] Carleer, et al: Assessment of Very High Spatial Resolution Satellite Image Segmentations, 2005 (Evaluates 2 boundary and 2 region based algorithms.)

[http://marte.dpi.inpe.br/col/sid.inpe.br/deise/1999/02.05.09.30/doc/T205.pdf] Bins, et al: Satellite Imagery Segmentation: A Region Growing Approach, 1996 (Describes approach taken in SPRING software.)

[http://www.sciencedirect.com/science/article/pii/S0031320300001497] Cheng et. al.: Color image segmentation: advances and prospect, 2000 (survey of segmentation methods and color spaces)

[http://www.isprs.org/proceedings/XXXV/congress/comm4/papers/506.pdf] G. Meinel, M. Neubert: A Comparison of Segmentation Programs for High Resolution Remote Sensing Data, 20?? (Includes timing to complete segmentation)

[http://www.wiley.com/WileyCDA/WileyTitle/productCd-0471377392.html?0471377392=] Pitas, I: Digital Image Processing Algorithms and Applications, 2000 (Textbook, including 1 chapter on segmentation methods.)

eCognition Reference Manual

Kurtz et. al: Hierarchical Segmentation of Multiresolution Remote Sensing Images, 2011

Comaniciu, Dorin: Mean Shift: A Robust Approach Toward Feature Space Analysis, 2002

GRASS GSoC 2012 Image Segmentation

2012-07-17T18:28:54Z

⚠️Emomsen: /* Memory */ lowered priority on taking seg id out of RAM.

{{GSoC}}
''(See also other [[GRASS_SoC_Ideas_2012#Accepted_Ideas|GRASS GSoC 2012 projects]])''

{| {{table}}
|Student Name: || Eric Momsen
|-
|Organization: || [http://www.osgeo.org OSGeo - Open Source Geospatial Foundation]
|-
| Mentor Name: || Mentor: Markus Metz (backup mentors: M Lennert, P Roudier)
|-
| Title: || '''Image Segmentation'''
|-
|-
| Repository: || AddOns, browse at: [https://trac.osgeo.org/grass/browser/grass-addons/grass7/imagery/i.segment i.segment]
|-
|}
=Abstract=

GRASS GIS has many imagery related processing capabilities, but the field is rapidly developing and many techniques are not yet implemented. The goal of this GSoC project is to implement the region growing image segmentation algorithm.

Input: Raster map(s) to be segmented (plus optional vector map for a constraint)

Output: To include segmented regions with statistics. This information can be directly used or taken as input to existing image classification modules.

Update: This process will be split into two modules, the first will output a raster map with segments, the second will compute statistics for the segments.

=Background=

Image classification techniques already implemented in GRASS GIS include supervised and unsupervised classification. Classification of images based on pixels can often be very noisy. By first segmenting the image, later classification of 'objects' can be more effective. Noise is reduced, classification speed is increased, and most importantly the classification is performed on objects instead of pixels. The {{cmd|i.smap}} module does include a segmentation step (based on Gaussian mixture distribution), but there does not exist a module intended to segment the image and provide segment data for general use. A summary of the existing methods implemented in GRASS are at [[Image classification]]. Furthermore, the module {{AddonCmd|r.seg}} in GRASS-addons uses internally the Mumford-Shah variational model for image segmentation.

== Segmentation Methods ==

* Boundary Based
** optimal edge detector +
** watershed +
* Region Based
** multilevel thresholding technique +
** region growing +
* Combined boundary/region (is this a correct category for these two?)
** mean-shift
** watershed

Carleer et.al. [1] reviewed 4 methods (marked with + above). Boundary based methods are sensitive to noise and texture, and usually depend on good pre-processing. (Does GRASS already have this pre-processing/filtering?) Good results with urban zones, high contrast. Both region based methods had difficulty with transition zones. Region growing was less sensitive to texture (good for high resolution (1m) images). Multi-level techniques are the only way to get all objects without over-segmentation.

I don't recall the source, but I read in one place that mean-shift could be difficult to apply to very large images, and elsewhere it was mentioned watershed sees more use in greyscale images.

As additional algorithms are added to the module, attention should be given to diversify so algorithms with different strengths are implemented first.

=== Region Growing Variations ===

Even within the region growing label, there are a number of approaches. Here are two described in [5].

1. Growing

Seeds (as a subset of the pixels) are selected (using image histogram, previous knowledge, or other methods). Region growing is done by adding adjacent pixels. No merging of segments is done, only unassigned pixels can be assigned to adjacent regions.

2. Growing and Merging

Use all pixels as seeds, no need to have user figure out a reasonable starting seed selection. Now adjacent segments can be merged.

Is there ever a case where someone may want to start with seeds, but still allow segment merging? Or does that fall into the realm of classification to be done in the next step?

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

== Segmentation Considerations ==

All(?) methods have some input parameter(s) that can be set. These parameters influence if the algorithm will over-segment (one expected region is divided into 2 or more segments) or under-segment (putting two expected regions into one segment). If the segments are used for later classification, over-segmentation should usually get preference to under-segmentation. With extensive over-segmentation, some of the advantages provided by segmentation can be lost, but at least the classification can combine the segments into the expected region. Under-segmentation is more critical, as the classification step will not divide the segment to recover the different regions. (Based on a summary of a number of papers from [1])

In order to respond to the issue of over/under-segmentation, a multiscalar approach would be interesting. This would mean either a top-down approach with a first coarse segmentation (under-segmentation) and the finer segmentation in selected segments, or a bottom-up approach with first a very fine-grained segmentation (over-segmentation) and the regrouping of segments to form higher levels. The first approach can be solved by doing a first segmentation, using certain segments as masks and then relaunching a second segmentation. {Or by using a vector map of the first segmentation as a boundary constraint in the second segmentation.} The second approach requires an algorithm to decide which segments should be combined in a larger higher-level segments. A simple nearest neighbor or kmeans approach based on spectral mean can be used here. In terms of implementation in GRASS, this would probably call for several modules, one for the segmentation, and another for grouping of segments. The latter could be an all-purpose clustering module (and can also be emulated by simple data analysis in the attribute table + {{cmd|v.dissolve}}).

It can sometimes be interesting to do a first segmentation on one band (e.g. panchromatic with higher resolution) and then regroup segments based on multispectral data (possibly weighting bands).

=Main Goal=

Implement an image segmentation method to extend the available options for image processing in GRASS. The region growing method has been selected as a robust general purpose method. An important contribution of the new method will be to include vector maps (for example road networks) as a constraint in growing the segments. Output from the module will include Spectral (mean/variance/range/ect) and Spatial (area/shape/location/etc) data for each region.

=Specifications=

* General considerations
** The general principle in GRASS is KISS, with each module doing one thing. It is to be seen if the result of this project is one single module or rather more than one module each specialised in one task in a segmentation workflow.
** As soon as code is to be (potentially) used in several modules, the use of a library should be envisaged.
** Be able to process large images while being considerate of system memory
* Input
** in the GRASS logic, input should be an image group, <del>or even image subgroup</del>, which can contain any number of raster maps, but generally satellite or areal images that are pre-processed and ready for analysis (i.e. no pre-processing in the module) (Update: subgroups are not often used, there use will not be implemented unless someone asks.)
*** This input group will define the feature space which can include spectral and other continuous (elevation, PCA layers, slope aspect...) and possibly (probably not initially) even discrete data (soil type, land cover...)
*** Default action will be to normalize/scale all input rasters to a 0-1 range. The allows bands (0-255), NDVI, and other numbers to be compared on an equal basis in the distance formula without any preprocessing steps. Since it gives equal weights to all rasters in the input group, a flag will give the user the option to skip this normalization step in case they want to use the actual values.
** optionally vector maps of existing features
*** lines (be it linear features or boundary lines of polygons) should be used as constraints meaning that no segment boundary should cross such a line
*** 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
** multi-scalar segmentation can significantly improve results and should thus be implemented if possible (see i.smap code for example)
* Similarity measurement
** The squared euclidean distance will be the default similarity measurement. If time allows, Manhattan distance will be added as an option. (Using the square will give same results, we will also square the similarity threshold so the user doesn't need to worry about this detail.
** For the default scaling of the input, the similarity threshold will be 0 to 1. This should be a good intuitive range for the user, 0 being the entire image is one segment and 1 being no segments can be formed. (Internally, this number must be multiplied by the number of rasters in the image group, but again the user doesn't need to worry about the details.) If the user selects the option to skip the normalization function, they will need to be careful how to select this parameter.
* Output
** first (segmentation) module: raster map of segments (i.e. each pixel value represents id of segment the pixel belongs to)
** second (stats) module: one vector map of segments per hierarchy level with a series of attributes (not all of these attributes should probably be calculated directly be the segmentation module)
*** spectral attributes:
**** per spectral band: mean, min, max, skewness
**** combination of bands: brightness, indices (i.e. results of multi-band calculations)
*** textural attributes: stdev (per-band and/or multi-band), mean difference to neighbor, Haralick texture features cf {{cmd|r.texture}}
*** geometric/morphological attributes: area, perimeter, length/width measures, see also {{cmd|r.li}}
*** context attributes: mean difference to all other regions in the same upper hierarchical level, relative localisation within upper hierarchical level, absolute localisation, number of objects in lower level
** depending on segmentation algorithm: raster map indicating for each pixel the probability of belonging to the segment it was put into, i.e. some measure of reliability of results

=== Questions ===

Number of modules: Should the user run one module to create the segments (raster output), then if they are interested, run r.to.vect and run a second module (vector input/output) if they want to get the statistics. (GUI glue to put them in one screen would be a low priority task for time remaining at the end of the summer.) (I wonder if the stats module should take vector or raster as the input, it will also need the original raster.)

"Probability of belonging to the segment": For region growing - should this be the similarity measure when it was merged? Or similarity measure of the pixel compared to the average?
/*ML: Not sure, but I would think that similarity between pixel and average of region it belongs to might be a good choice. Am not a specialist in statistics, but maybe it is possible to translate this into some form of probability of really "belonging" to that region (cf i.maxlik)*/
So this would be a comparison of the pixel to the final segment. Does anyone have a standard measurement that should be used?

4 vs. 8 neighbors: Should this be a user input option? It seems 4 neighbors (no diagonals) is the normal definition for segmentation, but not for other GRASS modules. Update: Using 4 neighbors as default, with optional flag to select 8 neighbors.

Null cells: Is it possible for some pixels inside the image to have null values? If yes, should they just be excluded from the calculation, or merged into the nearest segment? Update: current plan is to ignore all NULL values in the calculations.

Are there any examples of using linear features to constraint segment growth, or will it usually be polygons?

=== Lower priority ===

Add shape characteristics (smoothness, compactness) to the similarity measurement. Similar to eCognition "Multiresolution Segmentation"

It may be useful to do some calculations for the color space (RGB, HSI, L*u*v*, L*a*b*)? (I saw one paper [3] discussing pro/con of different systems, "best" answer is application dependent.)

ML: I would say leave decisions on color space (which is just one portion of feature space) to the user: one can group any kind raster maps with i.group and submit that to segmentation, and so the user can decide whether to use an image represented by different bands in a specific color space, plus any kind of other bands, indices, etc.

= Test Images =

The results of the implemented algorithm should be compared against the results of a similar algorithm implement in other software. The North Carolina GRASS sample location will be used for documentation and manuals.

Carleer [1] used images with 1m resolution from Ikonos, panchromatic band from 08 June 2000, Brussels area.

Should check segmentation results on images from a few different resolutions and different numbers of bands against what is obtained in other software.

Is there a benchmark for processing speed that should be considered? [4]

=Project Plan=

Preparation: Gather ideas from the community! Feature requests, image segmentation literature, and any other ideas and suggestions.

* May 21: Start coding, 8 weeks until Midterm Evaluation
* Week 1: Develop pseudocode to outline the work [http://lists.osgeo.org/pipermail/soc/2012-May/001747.html Report 1]
* Week 2-4: Implement the main algorithm [http://lists.osgeo.org/pipermail/soc/2012-June/001779.html Report 2] [http://lists.osgeo.org/pipermail/soc/2012-June/001804.html Report 3] [http://lists.osgeo.org/pipermail/soc/2012-June/001826.html Report 4]
* Week 5: Add vector maps as a constraint to the segmentation
* Week 6: Validation
* Week 7: Debugging
* Week 8: Contingency time for finishing the above, ensure a solid main program.
* July 9: Midterm Evaluation: Evaluate the existing program, determine the plan for the remaining 3-4 weeks. Options include:
* Improving the main algorithm
* Adding control for what scale the segmentation is performed at
* Providing updates to {{cmd|i.maxlik}} to ensure the segmentation output can be used as input for the existing classification functionality
* GUI
* Adding a second image segmentation algorithm

= Region Growing Algorithm =

Here is (a start!) for the processing steps, based on SPRING [2]

Region Growing, bottom up processing. Main improvement compared to simple algorithm is to slowly lower the similarity function, so only best matches are made first. This prevents the "first" segment from taking over any unclear areas between it and the next clear segment.

1. Input:
** Seeds: all pixels (Later addition can be alternate seeding methods)
** Similarity Threshold T(t)... as t increases, threshold for similarity is lower. SPRING used: <math>T(t) = T(0) alpha^t </math>, where T(0) > 0, t =0,1,2... and alpha <1
** Size of smallest allowed area (Is this wanted or needed ???)
2. Loop for t
** initialize candidate regions, save mean value vector and neighboring regions (Not sure why this needs to be calculated/saved ahead of time ??)
3. For each region i in candidate region set (first pass this equals the seeds):
** Compare Ri with neighbors (Question: should neighbors include or exclude those regions that were already matched?
** If it exists, Rk is best neighbor if smallest D of all neighbors and and D < T.
** Check Rk's neighbors.
** Merge IF Ri is Rk's best neighbor
** remove from candidate region set. (give all "small" regions a chance to merge with best neighbor before growing larger regions)
** update segment values
** next i
3. next t, with all segments returned to candidate region set, until no regions can be merged

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.

== Functionality ==

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.)

== Statistics/metrics ==

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.

== Speed ==

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.)

2: Consider peano or other ordering for pixel processing (instead of row major order), should help processing time if an entire "row" of segments are not in RAM.

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.)

== Memory ==

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.)

3: Put segment ID in SEG instead of RAM. (Possibly make this dependent on available RAM?) (Only consider if we run into RAM limitations.)

== Polish ==

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)

== Documentation ==

How to choose parameters, what their impact is.

Typical workflow:

* {{cmd|i.group}}
* i.segment
* {{cmd|r.to.vect}}
* i.segment.metrics and/or {{cmd|i.maxlik}} and/or {{AddonCmd|r.fuzzy}}

= Workflow =

Todo: Some typical workflow examples, type of data, GRASS modules used before and after the image segmentation.

= Results =

== Ortho-photo ==

The [http://grass.osgeo.org/wiki/where_are_these_data link to ortho data is missing] has 3 bands, and the computational region is 1,120,080 cells, at 1-m resolution.

Here's the code used to generate this segmentation result:

i.segment group=ortho output=ortho_segs_ha threshold=0.02 endt=10000 final_mean=ortho_segs_mean_ha min=20 --o

The segmentation performed in 22m53.255s on a Intel i5 laptop with 4Go RAM. The memory consumption was around 38 Mo.

[[File:Raglan_ortho_seg.png]]

== SPOT5 scene ==

The [http://grass.osgeo.org/wiki/where_are_these_data link to SPOT data is missing] has 4 bands, and the computational region is 4,444,517 cells, at 10-m resolution.

Here's the code used to generate this segmentation result:

i.segment group=spot output=spot_seg threshold=0.01 endt=10000 min=30 --o

The segmentation performed in 87m3.870s on a Intel Core 2 workstation with 8Go RAM. The memory consumption was around 170 Mo.

[[File:Taranaki spot seg.png]]

= References =

TODO: complete references with links.

[http://www.armurs.ulb.ac.be/images/8/86/PERS_Carleer_05.pdf] Carleer, et al: Assessment of Very High Spatial Resolution Satellite Image Segmentations, 2005 (Evaluates 2 boundary and 2 region based algorithms.)

[http://marte.dpi.inpe.br/col/sid.inpe.br/deise/1999/02.05.09.30/doc/T205.pdf] Bins, et al: Satellite Imagery Segmentation: A Region Growing Approach, 1996 (Describes approach taken in SPRING software.)

[http://www.sciencedirect.com/science/article/pii/S0031320300001497] Cheng et. al.: Color image segmentation: advances and prospect, 2000 (survey of segmentation methods and color spaces)

[http://www.isprs.org/proceedings/XXXV/congress/comm4/papers/506.pdf] G. Meinel, M. Neubert: A Comparison of Segmentation Programs for High Resolution Remote Sensing Data, 20?? (Includes timing to complete segmentation)

[http://www.wiley.com/WileyCDA/WileyTitle/productCd-0471377392.html?0471377392=] Pitas, I: Digital Image Processing Algorithms and Applications, 2000 (Textbook, including 1 chapter on segmentation methods.)

eCognition Reference Manual

Kurtz et. al: Hierarchical Segmentation of Multiresolution Remote Sensing Images, 2011

Comaniciu, Dorin: Mean Shift: A Robust Approach Toward Feature Space Analysis, 2002

GRASS GSoC 2012 Image Segmentation

2012-07-10T20:36:20Z

⚠️Emomsen: /* Speed */ - added peano ordering

{{GSoC}}
''(See also other [[GRASS_SoC_Ideas_2012#Accepted_Ideas|GRASS GSoC 2012 projects]])''

{| {{table}}
|Student Name: || Eric Momsen
|-
|Organization: || [http://www.osgeo.org OSGeo - Open Source Geospatial Foundation]
|-
| Mentor Name: || Mentor: Markus Metz (backup mentors: M Lennert, P Roudier)
|-
| Title: || '''Image Segmentation'''
|-
|-
| Repository: || AddOns, browse at: [https://trac.osgeo.org/grass/browser/grass-addons/grass7/imagery/i.segment i.segment]
|-
|}
=Abstract=

GRASS GIS has many imagery related processing capabilities, but the field is rapidly developing and many techniques are not yet implemented. The goal of this GSoC project is to implement the region growing image segmentation algorithm.

Input: Raster map(s) to be segmented (plus optional vector map for a constraint)

Output: To include segmented regions with statistics. This information can be directly used or taken as input to existing image classification modules.

Update: This process will be split into two modules, the first will output a raster map with segments, the second will compute statistics for the segments.

=Background=

Image classification techniques already implemented in GRASS GIS include supervised and unsupervised classification. Classification of images based on pixels can often be very noisy. By first segmenting the image, later classification of 'objects' can be more effective. Noise is reduced, classification speed is increased, and most importantly the classification is performed on objects instead of pixels. The {{cmd|i.smap}} module does include a segmentation step (based on Gaussian mixture distribution), but there does not exist a module intended to segment the image and provide segment data for general use. A summary of the existing methods implemented in GRASS are at [[Image classification]]. Furthermore, the module {{AddonCmd|r.seg}} in GRASS-addons uses internally the Mumford-Shah variational model for image segmentation.

== Segmentation Methods ==

* Boundary Based
** optimal edge detector +
** watershed +
* Region Based
** multilevel thresholding technique +
** region growing +
* Combined boundary/region (is this a correct category for these two?)
** mean-shift
** watershed

Carleer et.al. [1] reviewed 4 methods (marked with + above). Boundary based methods are sensitive to noise and texture, and usually depend on good pre-processing. (Does GRASS already have this pre-processing/filtering?) Good results with urban zones, high contrast. Both region based methods had difficulty with transition zones. Region growing was less sensitive to texture (good for high resolution (1m) images). Multi-level techniques are the only way to get all objects without over-segmentation.

I don't recall the source, but I read in one place that mean-shift could be difficult to apply to very large images, and elsewhere it was mentioned watershed sees more use in greyscale images.

As additional algorithms are added to the module, attention should be given to diversify so algorithms with different strengths are implemented first.

=== Region Growing Variations ===

Even within the region growing label, there are a number of approaches. Here are two described in [5].

1. Growing

Seeds (as a subset of the pixels) are selected (using image histogram, previous knowledge, or other methods). Region growing is done by adding adjacent pixels. No merging of segments is done, only unassigned pixels can be assigned to adjacent regions.

2. Growing and Merging

Use all pixels as seeds, no need to have user figure out a reasonable starting seed selection. Now adjacent segments can be merged.

Is there ever a case where someone may want to start with seeds, but still allow segment merging? Or does that fall into the realm of classification to be done in the next step?

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

== Segmentation Considerations ==

All(?) methods have some input parameter(s) that can be set. These parameters influence if the algorithm will over-segment (one expected region is divided into 2 or more segments) or under-segment (putting two expected regions into one segment). If the segments are used for later classification, over-segmentation should usually get preference to under-segmentation. With extensive over-segmentation, some of the advantages provided by segmentation can be lost, but at least the classification can combine the segments into the expected region. Under-segmentation is more critical, as the classification step will not divide the segment to recover the different regions. (Based on a summary of a number of papers from [1])

In order to respond to the issue of over/under-segmentation, a multiscalar approach would be interesting. This would mean either a top-down approach with a first coarse segmentation (under-segmentation) and the finer segmentation in selected segments, or a bottom-up approach with first a very fine-grained segmentation (over-segmentation) and the regrouping of segments to form higher levels. The first approach can be solved by doing a first segmentation, using certain segments as masks and then relaunching a second segmentation. {Or by using a vector map of the first segmentation as a boundary constraint in the second segmentation.} The second approach requires an algorithm to decide which segments should be combined in a larger higher-level segments. A simple nearest neighbor or kmeans approach based on spectral mean can be used here. In terms of implementation in GRASS, this would probably call for several modules, one for the segmentation, and another for grouping of segments. The latter could be an all-purpose clustering module (and can also be emulated by simple data analysis in the attribute table + {{cmd|v.dissolve}}).

It can sometimes be interesting to do a first segmentation on one band (e.g. panchromatic with higher resolution) and then regroup segments based on multispectral data (possibly weighting bands).

=Main Goal=

Implement an image segmentation method to extend the available options for image processing in GRASS. The region growing method has been selected as a robust general purpose method. An important contribution of the new method will be to include vector maps (for example road networks) as a constraint in growing the segments. Output from the module will include Spectral (mean/variance/range/ect) and Spatial (area/shape/location/etc) data for each region.

=Specifications=

* General considerations
** The general principle in GRASS is KISS, with each module doing one thing. It is to be seen if the result of this project is one single module or rather more than one module each specialised in one task in a segmentation workflow.
** As soon as code is to be (potentially) used in several modules, the use of a library should be envisaged.
** Be able to process large images while being considerate of system memory
* Input
** in the GRASS logic, input should be an image group, <del>or even image subgroup</del>, which can contain any number of raster maps, but generally satellite or areal images that are pre-processed and ready for analysis (i.e. no pre-processing in the module) (Update: subgroups are not often used, there use will not be implemented unless someone asks.)
*** This input group will define the feature space which can include spectral and other continuous (elevation, PCA layers, slope aspect...) and possibly (probably not initially) even discrete data (soil type, land cover...)
*** Default action will be to normalize/scale all input rasters to a 0-1 range. The allows bands (0-255), NDVI, and other numbers to be compared on an equal basis in the distance formula without any preprocessing steps. Since it gives equal weights to all rasters in the input group, a flag will give the user the option to skip this normalization step in case they want to use the actual values.
** optionally vector maps of existing features
*** lines (be it linear features or boundary lines of polygons) should be used as constraints meaning that no segment boundary should cross such a line
*** 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
** multi-scalar segmentation can significantly improve results and should thus be implemented if possible (see i.smap code for example)
* Similarity measurement
** The squared euclidean distance will be the default similarity measurement. If time allows, Manhattan distance will be added as an option. (Using the square will give same results, we will also square the similarity threshold so the user doesn't need to worry about this detail.
** For the default scaling of the input, the similarity threshold will be 0 to 1. This should be a good intuitive range for the user, 0 being the entire image is one segment and 1 being no segments can be formed. (Internally, this number must be multiplied by the number of rasters in the image group, but again the user doesn't need to worry about the details.) If the user selects the option to skip the normalization function, they will need to be careful how to select this parameter.
* Output
** first (segmentation) module: raster map of segments (i.e. each pixel value represents id of segment the pixel belongs to)
** second (stats) module: one vector map of segments per hierarchy level with a series of attributes (not all of these attributes should probably be calculated directly be the segmentation module)
*** spectral attributes:
**** per spectral band: mean, min, max, skewness
**** combination of bands: brightness, indices (i.e. results of multi-band calculations)
*** textural attributes: stdev (per-band and/or multi-band), mean difference to neighbor, Haralick texture features cf {{cmd|r.texture}}
*** geometric/morphological attributes: area, perimeter, length/width measures, see also {{cmd|r.li}}
*** context attributes: mean difference to all other regions in the same upper hierarchical level, relative localisation within upper hierarchical level, absolute localisation, number of objects in lower level
** depending on segmentation algorithm: raster map indicating for each pixel the probability of belonging to the segment it was put into, i.e. some measure of reliability of results

=== Questions ===

Number of modules: Should the user run one module to create the segments (raster output), then if they are interested, run r.to.vect and run a second module (vector input/output) if they want to get the statistics. (GUI glue to put them in one screen would be a low priority task for time remaining at the end of the summer.) (I wonder if the stats module should take vector or raster as the input, it will also need the original raster.)

"Probability of belonging to the segment": For region growing - should this be the similarity measure when it was merged? Or similarity measure of the pixel compared to the average?
/*ML: Not sure, but I would think that similarity between pixel and average of region it belongs to might be a good choice. Am not a specialist in statistics, but maybe it is possible to translate this into some form of probability of really "belonging" to that region (cf i.maxlik)*/
So this would be a comparison of the pixel to the final segment. Does anyone have a standard measurement that should be used?

4 vs. 8 neighbors: Should this be a user input option? It seems 4 neighbors (no diagonals) is the normal definition for segmentation, but not for other GRASS modules. Update: Using 4 neighbors as default, with optional flag to select 8 neighbors.

Null cells: Is it possible for some pixels inside the image to have null values? If yes, should they just be excluded from the calculation, or merged into the nearest segment? Update: current plan is to ignore all NULL values in the calculations.

Are there any examples of using linear features to constraint segment growth, or will it usually be polygons?

=== Lower priority ===

Add shape characteristics (smoothness, compactness) to the similarity measurement. Similar to eCognition "Multiresolution Segmentation"

It may be useful to do some calculations for the color space (RGB, HSI, L*u*v*, L*a*b*)? (I saw one paper [3] discussing pro/con of different systems, "best" answer is application dependent.)

ML: I would say leave decisions on color space (which is just one portion of feature space) to the user: one can group any kind raster maps with i.group and submit that to segmentation, and so the user can decide whether to use an image represented by different bands in a specific color space, plus any kind of other bands, indices, etc.

= Test Images =

The results of the implemented algorithm should be compared against the results of a similar algorithm implement in other software. The North Carolina GRASS sample location will be used for documentation and manuals.

Carleer [1] used images with 1m resolution from Ikonos, panchromatic band from 08 June 2000, Brussels area.

Should check segmentation results on images from a few different resolutions and different numbers of bands against what is obtained in other software.

Is there a benchmark for processing speed that should be considered? [4]

=Project Plan=

Preparation: Gather ideas from the community! Feature requests, image segmentation literature, and any other ideas and suggestions.

* May 21: Start coding, 8 weeks until Midterm Evaluation
* Week 1: Develop pseudocode to outline the work [http://lists.osgeo.org/pipermail/soc/2012-May/001747.html Report 1]
* Week 2-4: Implement the main algorithm [http://lists.osgeo.org/pipermail/soc/2012-June/001779.html Report 2] [http://lists.osgeo.org/pipermail/soc/2012-June/001804.html Report 3] [http://lists.osgeo.org/pipermail/soc/2012-June/001826.html Report 4]
* Week 5: Add vector maps as a constraint to the segmentation
* Week 6: Validation
* Week 7: Debugging
* Week 8: Contingency time for finishing the above, ensure a solid main program.
* July 9: Midterm Evaluation: Evaluate the existing program, determine the plan for the remaining 3-4 weeks. Options include:
* Improving the main algorithm
* Adding control for what scale the segmentation is performed at
* Providing updates to {{cmd|i.maxlik}} to ensure the segmentation output can be used as input for the existing classification functionality
* GUI
* Adding a second image segmentation algorithm

= Region Growing Algorithm =

Here is (a start!) for the processing steps, based on SPRING [2]

Region Growing, bottom up processing. Main improvement compared to simple algorithm is to slowly lower the similarity function, so only best matches are made first. This prevents the "first" segment from taking over any unclear areas between it and the next clear segment.

1. Input:
** Seeds: all pixels (Later addition can be alternate seeding methods)
** Similarity Threshold T(t)... as t increases, threshold for similarity is lower. SPRING used: <math>T(t) = T(0) alpha^t </math>, where T(0) > 0, t =0,1,2... and alpha <1
** Size of smallest allowed area (Is this wanted or needed ???)
2. Loop for t
** initialize candidate regions, save mean value vector and neighboring regions (Not sure why this needs to be calculated/saved ahead of time ??)
3. For each region i in candidate region set (first pass this equals the seeds):
** Compare Ri with neighbors (Question: should neighbors include or exclude those regions that were already matched?
** If it exists, Rk is best neighbor if smallest D of all neighbors and and D < T.
** Check Rk's neighbors.
** Merge IF Ri is Rk's best neighbor
** remove from candidate region set. (give all "small" regions a chance to merge with best neighbor before growing larger regions)
** update segment values
** next i
3. next t, with all segments returned to candidate region set, until no regions can be merged

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.

== Functionality ==

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.)

== Statistics/metrics ==

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.

== Speed ==

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.)

2: Consider peano or other ordering for pixel processing (instead of row major order), should help processing time if an entire "row" of segments are not in RAM.

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.)

== Memory ==

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.)

== Polish ==

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)

== Documentation ==

How to choose parameters, what their impact is.

Typical workflow:

* i.group
* i.segment
* r.to.vect
* i.segment.metrics and/or i.maxlik and/or r.fuzzy

= Workflow =

Todo: Some typical workflow examples, type of data, GRASS modules used before and after the image segmentation.

= References =

TODO: complete references with links.

[http://www.armurs.ulb.ac.be/images/8/86/PERS_Carleer_05.pdf] Carleer, et al: Assessment of Very High Spatial Resolution Satellite Image Segmentations, 2005 (Evaluates 2 boundary and 2 region based algorithms.)

[http://marte.dpi.inpe.br/col/sid.inpe.br/deise/1999/02.05.09.30/doc/T205.pdf] Bins, et al: Satellite Imagery Segmentation: A Region Growing Approach, 1996 (Describes approach taken in SPRING software.)

[http://www.sciencedirect.com/science/article/pii/S0031320300001497] Cheng et. al.: Color image segmentation: advances and prospect, 2000 (survey of segmentation methods and color spaces)

[http://www.isprs.org/proceedings/XXXV/congress/comm4/papers/506.pdf] G. Meinel, M. Neubert: A Comparison of Segmentation Programs for High Resolution Remote Sensing Data, 20?? (Includes timing to complete segmentation)

[http://www.wiley.com/WileyCDA/WileyTitle/productCd-0471377392.html?0471377392=] Pitas, I: Digital Image Processing Algorithms and Applications, 2000 (Textbook, including 1 chapter on segmentation methods.)

eCognition Reference Manual

Kurtz et. al: Hierarchical Segmentation of Multiresolution Remote Sensing Images, 2011

Comaniciu, Dorin: Mean Shift: A Robust Approach Toward Feature Space Analysis, 2002

GRASS GSoC 2012 Image Segmentation

2012-07-10T16:11:58Z

⚠️Emomsen: Added ToDo list

{{GSoC}}
''(See also other [[GRASS_SoC_Ideas_2012#Accepted_Ideas|GRASS GSoC 2012 projects]])''

{| {{table}}
|Student Name: || Eric Momsen
|-
|Organization: || [http://www.osgeo.org OSGeo - Open Source Geospatial Foundation]
|-
| Mentor Name: || Mentor: Markus Metz (backup mentors: M Lennert, P Roudier)
|-
| Title: || '''Image Segmentation'''
|-
|-
| Repository: || AddOns, browse at: [https://trac.osgeo.org/grass/browser/grass-addons/grass7/imagery/i.segment i.segment]
|-
|}
=Abstract=

GRASS GIS has many imagery related processing capabilities, but the field is rapidly developing and many techniques are not yet implemented. The goal of this GSoC project is to implement the region growing image segmentation algorithm.

Input: Raster map(s) to be segmented (plus optional vector map for a constraint)

Output: To include segmented regions with statistics. This information can be directly used or taken as input to existing image classification modules.

Update: This process will be split into two modules, the first will output a raster map with segments, the second will compute statistics for the segments.

=Background=

Image classification techniques already implemented in GRASS GIS include supervised and unsupervised classification. Classification of images based on pixels can often be very noisy. By first segmenting the image, later classification of 'objects' can be more effective. Noise is reduced, classification speed is increased, and most importantly the classification is performed on objects instead of pixels. The {{cmd|i.smap}} module does include a segmentation step (based on Gaussian mixture distribution), but there does not exist a module intended to segment the image and provide segment data for general use. A summary of the existing methods implemented in GRASS are at [[Image classification]]. Furthermore, the module {{AddonCmd|r.seg}} in GRASS-addons uses internally the Mumford-Shah variational model for image segmentation.

== Segmentation Methods ==

* Boundary Based
** optimal edge detector +
** watershed +
* Region Based
** multilevel thresholding technique +
** region growing +
* Combined boundary/region (is this a correct category for these two?)
** mean-shift
** watershed

Carleer et.al. [1] reviewed 4 methods (marked with + above). Boundary based methods are sensitive to noise and texture, and usually depend on good pre-processing. (Does GRASS already have this pre-processing/filtering?) Good results with urban zones, high contrast. Both region based methods had difficulty with transition zones. Region growing was less sensitive to texture (good for high resolution (1m) images). Multi-level techniques are the only way to get all objects without over-segmentation.

I don't recall the source, but I read in one place that mean-shift could be difficult to apply to very large images, and elsewhere it was mentioned watershed sees more use in greyscale images.

As additional algorithms are added to the module, attention should be given to diversify so algorithms with different strengths are implemented first.

=== Region Growing Variations ===

Even within the region growing label, there are a number of approaches. Here are two described in [5].

1. Growing

Seeds (as a subset of the pixels) are selected (using image histogram, previous knowledge, or other methods). Region growing is done by adding adjacent pixels. No merging of segments is done, only unassigned pixels can be assigned to adjacent regions.

2. Growing and Merging

Use all pixels as seeds, no need to have user figure out a reasonable starting seed selection. Now adjacent segments can be merged.

Is there ever a case where someone may want to start with seeds, but still allow segment merging? Or does that fall into the realm of classification to be done in the next step?

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

== Segmentation Considerations ==

All(?) methods have some input parameter(s) that can be set. These parameters influence if the algorithm will over-segment (one expected region is divided into 2 or more segments) or under-segment (putting two expected regions into one segment). If the segments are used for later classification, over-segmentation should usually get preference to under-segmentation. With extensive over-segmentation, some of the advantages provided by segmentation can be lost, but at least the classification can combine the segments into the expected region. Under-segmentation is more critical, as the classification step will not divide the segment to recover the different regions. (Based on a summary of a number of papers from [1])

In order to respond to the issue of over/under-segmentation, a multiscalar approach would be interesting. This would mean either a top-down approach with a first coarse segmentation (under-segmentation) and the finer segmentation in selected segments, or a bottom-up approach with first a very fine-grained segmentation (over-segmentation) and the regrouping of segments to form higher levels. The first approach can be solved by doing a first segmentation, using certain segments as masks and then relaunching a second segmentation. {Or by using a vector map of the first segmentation as a boundary constraint in the second segmentation.} The second approach requires an algorithm to decide which segments should be combined in a larger higher-level segments. A simple nearest neighbor or kmeans approach based on spectral mean can be used here. In terms of implementation in GRASS, this would probably call for several modules, one for the segmentation, and another for grouping of segments. The latter could be an all-purpose clustering module (and can also be emulated by simple data analysis in the attribute table + {{cmd|v.dissolve}}).

It can sometimes be interesting to do a first segmentation on one band (e.g. panchromatic with higher resolution) and then regroup segments based on multispectral data (possibly weighting bands).

=Main Goal=

Implement an image segmentation method to extend the available options for image processing in GRASS. The region growing method has been selected as a robust general purpose method. An important contribution of the new method will be to include vector maps (for example road networks) as a constraint in growing the segments. Output from the module will include Spectral (mean/variance/range/ect) and Spatial (area/shape/location/etc) data for each region.

=Specifications=

* General considerations
** The general principle in GRASS is KISS, with each module doing one thing. It is to be seen if the result of this project is one single module or rather more than one module each specialised in one task in a segmentation workflow.
** As soon as code is to be (potentially) used in several modules, the use of a library should be envisaged.
** Be able to process large images while being considerate of system memory
* Input
** in the GRASS logic, input should be an image group, <del>or even image subgroup</del>, which can contain any number of raster maps, but generally satellite or areal images that are pre-processed and ready for analysis (i.e. no pre-processing in the module) (Update: subgroups are not often used, there use will not be implemented unless someone asks.)
*** This input group will define the feature space which can include spectral and other continuous (elevation, PCA layers, slope aspect...) and possibly (probably not initially) even discrete data (soil type, land cover...)
*** Default action will be to normalize/scale all input rasters to a 0-1 range. The allows bands (0-255), NDVI, and other numbers to be compared on an equal basis in the distance formula without any preprocessing steps. Since it gives equal weights to all rasters in the input group, a flag will give the user the option to skip this normalization step in case they want to use the actual values.
** optionally vector maps of existing features
*** lines (be it linear features or boundary lines of polygons) should be used as constraints meaning that no segment boundary should cross such a line
*** 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
** multi-scalar segmentation can significantly improve results and should thus be implemented if possible (see i.smap code for example)
* Similarity measurement
** The squared euclidean distance will be the default similarity measurement. If time allows, Manhattan distance will be added as an option. (Using the square will give same results, we will also square the similarity threshold so the user doesn't need to worry about this detail.
** For the default scaling of the input, the similarity threshold will be 0 to 1. This should be a good intuitive range for the user, 0 being the entire image is one segment and 1 being no segments can be formed. (Internally, this number must be multiplied by the number of rasters in the image group, but again the user doesn't need to worry about the details.) If the user selects the option to skip the normalization function, they will need to be careful how to select this parameter.
* Output
** first (segmentation) module: raster map of segments (i.e. each pixel value represents id of segment the pixel belongs to)
** second (stats) module: one vector map of segments per hierarchy level with a series of attributes (not all of these attributes should probably be calculated directly be the segmentation module)
*** spectral attributes:
**** per spectral band: mean, min, max, skewness
**** combination of bands: brightness, indices (i.e. results of multi-band calculations)
*** textural attributes: stdev (per-band and/or multi-band), mean difference to neighbor, Haralick texture features cf {{cmd|r.texture}}
*** geometric/morphological attributes: area, perimeter, length/width measures, see also {{cmd|r.li}}
*** context attributes: mean difference to all other regions in the same upper hierarchical level, relative localisation within upper hierarchical level, absolute localisation, number of objects in lower level
** depending on segmentation algorithm: raster map indicating for each pixel the probability of belonging to the segment it was put into, i.e. some measure of reliability of results

=== Questions ===

Number of modules: Should the user run one module to create the segments (raster output), then if they are interested, run r.to.vect and run a second module (vector input/output) if they want to get the statistics. (GUI glue to put them in one screen would be a low priority task for time remaining at the end of the summer.) (I wonder if the stats module should take vector or raster as the input, it will also need the original raster.)

"Probability of belonging to the segment": For region growing - should this be the similarity measure when it was merged? Or similarity measure of the pixel compared to the average?
/*ML: Not sure, but I would think that similarity between pixel and average of region it belongs to might be a good choice. Am not a specialist in statistics, but maybe it is possible to translate this into some form of probability of really "belonging" to that region (cf i.maxlik)*/
So this would be a comparison of the pixel to the final segment. Does anyone have a standard measurement that should be used?

4 vs. 8 neighbors: Should this be a user input option? It seems 4 neighbors (no diagonals) is the normal definition for segmentation, but not for other GRASS modules. Update: Using 4 neighbors as default, with optional flag to select 8 neighbors.

Null cells: Is it possible for some pixels inside the image to have null values? If yes, should they just be excluded from the calculation, or merged into the nearest segment? Update: current plan is to ignore all NULL values in the calculations.

Are there any examples of using linear features to constraint segment growth, or will it usually be polygons?

=== Lower priority ===

Add shape characteristics (smoothness, compactness) to the similarity measurement. Similar to eCognition "Multiresolution Segmentation"

It may be useful to do some calculations for the color space (RGB, HSI, L*u*v*, L*a*b*)? (I saw one paper [3] discussing pro/con of different systems, "best" answer is application dependent.)

ML: I would say leave decisions on color space (which is just one portion of feature space) to the user: one can group any kind raster maps with i.group and submit that to segmentation, and so the user can decide whether to use an image represented by different bands in a specific color space, plus any kind of other bands, indices, etc.

= Test Images =

The results of the implemented algorithm should be compared against the results of a similar algorithm implement in other software. The North Carolina GRASS sample location will be used for documentation and manuals.

Carleer [1] used images with 1m resolution from Ikonos, panchromatic band from 08 June 2000, Brussels area.

Should check segmentation results on images from a few different resolutions and different numbers of bands against what is obtained in other software.

Is there a benchmark for processing speed that should be considered? [4]

=Project Plan=

Preparation: Gather ideas from the community! Feature requests, image segmentation literature, and any other ideas and suggestions.

* May 21: Start coding, 8 weeks until Midterm Evaluation
* Week 1: Develop pseudocode to outline the work [http://lists.osgeo.org/pipermail/soc/2012-May/001747.html Report 1]
* Week 2-4: Implement the main algorithm [http://lists.osgeo.org/pipermail/soc/2012-June/001779.html Report 2] [http://lists.osgeo.org/pipermail/soc/2012-June/001804.html Report 3] [http://lists.osgeo.org/pipermail/soc/2012-June/001826.html Report 4]
* Week 5: Add vector maps as a constraint to the segmentation
* Week 6: Validation
* Week 7: Debugging
* Week 8: Contingency time for finishing the above, ensure a solid main program.
* July 9: Midterm Evaluation: Evaluate the existing program, determine the plan for the remaining 3-4 weeks. Options include:
* Improving the main algorithm
* Adding control for what scale the segmentation is performed at
* Providing updates to {{cmd|i.maxlik}} to ensure the segmentation output can be used as input for the existing classification functionality
* GUI
* Adding a second image segmentation algorithm

= Region Growing Algorithm =

Here is (a start!) for the processing steps, based on SPRING [2]

Region Growing, bottom up processing. Main improvement compared to simple algorithm is to slowly lower the similarity function, so only best matches are made first. This prevents the "first" segment from taking over any unclear areas between it and the next clear segment.

1. Input:
** Seeds: all pixels (Later addition can be alternate seeding methods)
** Similarity Threshold T(t)... as t increases, threshold for similarity is lower. SPRING used: <math>T(t) = T(0) alpha^t </math>, where T(0) > 0, t =0,1,2... and alpha <1
** Size of smallest allowed area (Is this wanted or needed ???)
2. Loop for t
** initialize candidate regions, save mean value vector and neighboring regions (Not sure why this needs to be calculated/saved ahead of time ??)
3. For each region i in candidate region set (first pass this equals the seeds):
** Compare Ri with neighbors (Question: should neighbors include or exclude those regions that were already matched?
** If it exists, Rk is best neighbor if smallest D of all neighbors and and D < T.
** Check Rk's neighbors.
** Merge IF Ri is Rk's best neighbor
** remove from candidate region set. (give all "small" regions a chance to merge with best neighbor before growing larger regions)
** update segment values
** next i
3. next t, with all segments returned to candidate region set, until no regions can be merged

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.

== Functionality ==

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.)

== Statistics/metrics ==

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.

== Speed ==

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.)

== Memory ==

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.)

== Polish ==

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)

== Documentation ==

How to choose parameters, what their impact is.

Typical workflow:

* i.group
* i.segment
* r.to.vect
* i.segment.metrics and/or i.maxlik and/or r.fuzzy

= Workflow =

Todo: Some typical workflow examples, type of data, GRASS modules used before and after the image segmentation.

= References =

TODO: complete references with links.

[http://www.armurs.ulb.ac.be/images/8/86/PERS_Carleer_05.pdf] Carleer, et al: Assessment of Very High Spatial Resolution Satellite Image Segmentations, 2005 (Evaluates 2 boundary and 2 region based algorithms.)

[http://marte.dpi.inpe.br/col/sid.inpe.br/deise/1999/02.05.09.30/doc/T205.pdf] Bins, et al: Satellite Imagery Segmentation: A Region Growing Approach, 1996 (Describes approach taken in SPRING software.)

[http://www.sciencedirect.com/science/article/pii/S0031320300001497] Cheng et. al.: Color image segmentation: advances and prospect, 2000 (survey of segmentation methods and color spaces)

[http://www.isprs.org/proceedings/XXXV/congress/comm4/papers/506.pdf] G. Meinel, M. Neubert: A Comparison of Segmentation Programs for High Resolution Remote Sensing Data, 20?? (Includes timing to complete segmentation)

[http://www.wiley.com/WileyCDA/WileyTitle/productCd-0471377392.html?0471377392=] Pitas, I: Digital Image Processing Algorithms and Applications, 2000 (Textbook, including 1 chapter on segmentation methods.)

eCognition Reference Manual

Kurtz et. al: Hierarchical Segmentation of Multiresolution Remote Sensing Images, 2011

Comaniciu, Dorin: Mean Shift: A Robust Approach Toward Feature Space Analysis, 2002

GRASS GSoC 2012 Image Segmentation

2012-06-20T16:02:54Z

⚠️Emomsen: /* Project Plan */ - added links to weekly reports

GRASS GSoC 2012 Image Segmentation

2012-06-20T15:45:19Z

⚠️Emomsen: /* Specifications */ - updated based on email discussions.

GRASS GSoC 2012 Image Segmentation

2012-06-20T15:19:54Z

⚠️Emomsen: /* Abstract */ - splitting segmentation and stats into two modules.

GRASS GSoC 2012 Image Segmentation

2012-06-08T13:42:10Z

⚠️Emomsen: /* Region Growing Algorithm */ (fixed typo in formula)

GRASS GSoC 2012 Image Segmentation

2012-05-29T15:18:31Z

⚠️Emomsen: /* Specifications */

GRASS GSoC 2012 Image Segmentation

2012-05-25T15:49:25Z

⚠️Emomsen: added code repository in header info

GRASS GSoC 2012 Image Segmentation

2012-05-24T19:59:09Z

⚠️Emomsen: /* References */

GRASS GSoC 2012 Image Segmentation

2012-05-24T19:56:04Z

⚠️Emomsen: /* Segmentation Methods */ - added section on region growing variations

GRASS GSoC 2012 Image Segmentation

2012-05-24T19:32:02Z

⚠️Emomsen: /* Specifications */ -updated input - idea of feature space instead of color space

GRASS GSoC 2012 Image Segmentation

2012-05-24T17:20:18Z

⚠️Emomsen: added header for Workflow

GRASS GSoC 2012 Image Segmentation

2012-05-24T17:19:15Z

⚠️Emomsen: /* References */

GRASS GSoC 2012 Image Segmentation

2012-05-24T16:09:50Z

⚠️Emomsen: /* Region Growing Algorithm */ adjusted terminology

GRASS GSoC 2012 Image Segmentation

2012-05-24T16:01:43Z

⚠️Emomsen: /* Lower priority */ some specifications to be added later

GRASS GSoC 2012 Image Segmentation

2012-05-24T15:59:22Z

⚠️Emomsen: /* Segmentation Considerations */ Added second approach for top down multiscalar segmentation

GRASS GSoC 2012 Image Segmentation

2012-05-24T15:56:41Z

⚠️Emomsen: /* Segmentation Methods */

GRASS GSoC 2012 Image Segmentation

2012-05-24T15:55:11Z

⚠️Emomsen: /* Specifications */

GRASS GSoC 2012 Image Segmentation

2012-05-22T20:45:40Z

⚠️Emomsen: /* Specifications */

GRASS GSoC 2012 Image Segmentation

2012-05-22T20:42:26Z

⚠️Emomsen: /* Segmentation Methods */

GRASS GSoC 2012 Image Segmentation

2012-05-22T20:38:22Z

⚠️Emomsen: /* Specifications */

GRASS GSoC 2012 Image Segmentation

2012-05-22T18:27:55Z

⚠️Emomsen: /* Program Steps */

GRASS GSoC 2012 Image Segmentation

2012-05-22T18:23:10Z

⚠️Emomsen: /* Test Images */

GRASS GSoC 2012 Image Segmentation

2012-05-22T18:22:52Z

⚠️Emomsen: /* References */

GRASS GSoC 2012 Image Segmentation

2012-05-22T18:14:50Z

⚠️Emomsen: /* Specifications */

GRASS GSoC 2012 Image Segmentation

2012-05-22T03:40:35Z

⚠️Emomsen: /* Program Steps */

GRASS GSoC 2012 Image Segmentation

2012-05-22T03:27:21Z

⚠️Emomsen: /* References */

GRASS GSoC 2012 Image Segmentation

2012-05-22T03:22:19Z

⚠️Emomsen: /* Specifications */

GRASS GSoC 2012 Image Segmentation

2012-05-22T03:09:21Z

⚠️Emomsen: /* References */

GRASS GSoC 2012 Image Segmentation

2012-05-21T16:41:04Z

⚠️Emomsen:

GRASS GSoC 2012 Image Segmentation

2012-05-21T14:08:03Z

⚠️Emomsen: /* Test Images */

GRASS GSoC 2012 Image Segmentation

2012-05-15T20:06:31Z

⚠️Emomsen:

GRASS GSoC 2012 Image Segmentation

2012-04-30T04:34:29Z

⚠️Emomsen:

=Abstract=

GRASS has many imagery related processing capabilities, but the field is rapidly developing and many techniques are not yet implemented. The goal of this GSoC project is to implement the region growing image segmentation algorithm.

Input: Raster map(s) to be segmented (plus optional vector map for a constraint)

Output: To include segmented regions with statistics. This information can be directly used or taken as input to existing image classification modules.

=Background=

Image classification techniques already implemented in GRASS include supervised and unsupervised classification. Classification of images based on pixels can often be very noisy. By first segmenting the image, later classification of 'objects' can be more effective. Noise is reduced, classification speed is increased, and most importantly the classification is performed on objects instead of pixels. The i.smap module does include a segmentation step (based on Gaussian mixture distribution), but there does not exist a module intended to segment the image and provide segment data for general use. A summary of the existing methods implemented in GRASS are at http://grass.osgeo.org/wiki/Image_classification

=Main Goal=

Implement an image segmentation method to extend the available options for image processing in GRASS. The region growing method has been selected as a robust general purpose method. An important contribution of the new method will be to include vector maps (for example road networks) as a constraint in growing the segments. Output from the module will include Spectral (mean/variance/range/ect) and Spatial (area/shape/location/etc) data for each region.

=Specifications=

=Project Plan=

Preparation: Gather ideas from the community! Feature requests, image segmentation literature, and any other ideas and suggestions.

* May 21: Start coding, 8 weeks until Midterm Evaluation
* Week 1: Develop pseudocode to outline the work
* Week 2-4: Implement the main algorithm
* Week 5: Add vector maps as a constraint to the segmentation
* Week 6: Validation
* Week 7: Debugging
* Week 8: GUI
* July 9: Midterm Evaluation: Evaluate the existing program, determine the plan for the remaining 3-4 weeks. Options include:
* Improving the main algorithm
* Adding control for what scale the segmentation is performed at
* Providing updates to i.maxlik to ensure the segmentation output can be used as input for the existing classification functionality

GRASS GSoC 2012 Image Segmentation

2012-04-30T04:31:16Z

⚠️Emomsen: Google Summer of Code (GSoC) 2012 background, plan and weekly reports for Image Segmentation project.

=Abstract=

GRASS has many imagery related processing capabilities, but the field is rapidly developing and many techniques are not yet implemented. The goal of this GSoC project is to implement the region growing image segmentation algorithm.

Input: Raster map(s) to be segmented (plus optional vector map for a constraint)

Output: To include segmented regions with statistics. This information can be directly used or taken as input to existing image classification modules.

=Background=

Image classification techniques already implemented in GRASS include supervised and unsupervised classification. Classification of images based on pixels can often be very noisy. By first segmenting the image, later classification of 'objects' can be more effective. Noise is reduced, classification speed is increased, and most importantly the classification is performed on objects instead of pixels. The i.smap module does include a segmentation step (based on Gaussian mixture distribution), but there does not exist a module intended to segment the image and provide segment data for general use. A summary of the existing methods implemented in GRASS are at http://grass.osgeo.org/wiki/Image_classification

=Main Goal=

Implement an image segmentation method to extend the available options for image processing in GRASS. The region growing method has been selected as a robust general purpose method. An important contribution of the new method will be to include vector maps (for example road networks) as a constraint in growing the segments. Output from the module will include Spectral (mean/variance/range/ect) and Spatial (area/shape/location/etc) data for each region.

=Feature Requests=

=Project Plan=

Preparation: Gather ideas from the community! Feature requests, image segmentation literature, and any other ideas and suggestions.

* May 21: Start coding, 8 weeks until Midterm Evaluation
* Week 1: Develop pseudocode to outline the work
* Week 2-4: Implement the main algorithm
* Week 5: Add vector maps as a constraint to the segmentation
* Week 6: Validation
* Week 7: Debugging
* Week 8: GUI
* July 9: Midterm Evaluation: Evaluate the existing program, determine the plan for the remaining 3-4 weeks. Options include:
* Improving the main algorithm
* Adding control for what scale the segmentation is performed at
* Providing updates to i.maxlik to ensure the segmentation output can be used as input for the existing classification functionality

GRASS SoC Ideas 2012

2012-04-30T04:17:21Z

⚠️Emomsen:

<center>

[[Image:grasslogo_vector_small.png|link=http://grass.osgeo.org]]<font size="+3"> @ </font> [[Image:Gsoc-2012-logo-color.png|250px|link=http://wiki.osgeo.org/wiki/Google_Summer_of_Code_2012]] <font size="+3"> @ </font> [[Image:OSGeo 220pix.png|link=http://www.osgeo.org]]
</center>

* See also previous Google Summer of Code [[GRASS SoC Ideas 2011|ideas from 2011]].

* Visit the [http://wiki.osgeo.org/wiki/Google_Summer_of_Code_2012 main OSGeo Google Summer of Code 2012 @ OSGeo wiki page].

__TOC__
== About ==

This is the GRASS page for [http://wiki.osgeo.org/index.php/Google_Summer_of_Code Google Summer of Code 2012]. Here we will list project ideas and and other information related to the GRASS GSoC projects.

* [http://code.google.com/soc/ Official Google Summer of Code 2012 homepage]
* [http://wiki.osgeo.org/wiki/Google_Summer_of_Code_2012 OSGeo SoC 2012 homepage]

Promotion:

* Videos at http://code.google.com/p/google-summer-of-code/wiki/Videos
* More Flyers at http://code.google.com/p/google-summer-of-code/wiki/GsocFlyers

== Timeline ==

* '''[http://www.google-melange.com/gsoc/document/show/gsoc_program/google/gsoc2012/faqs#timeline The official timeline]'''

== Required Steps ==

* '''List ideas'''

* Assign Mentors to Ideas

* Notify OSGeo

* Mentors evaluate student applications

* Accepted students announced

* Students subscribe to the [http://lists.osgeo.org/mailman/listinfo/grass-dev grass-dev mailing list] and introduce themselves

* Mentor will create directory structure in the [http://trac.osgeo.org/grass/browser/grass-addons GRASS add-ons SVN] for projects and setup access for students
** Students must read and post agreement to [http://grass.osgeo.org/programming7/rfc2_psc.html RFC2] to the [http://lists.osgeo.org/mailman/listinfo/grass-psc grass-psc mailing list] to gain SVN access
** Create a Wiki page for each accepted project, to be used as a progress reporting tool

* Coding begins...

* Students and mentors: Complete the Mid-term survey

* Final commit and packaging for Google

== Ideas ==

* Also review ideas from [[GRASS SoC Ideas 2007#Ideas|2007]], [[GRASS SoC Ideas 2008#Ideas|2008]], [[GRASS SoC Ideas 2009#Ideas|2009]], [[GRASS SoC Ideas 2010#Ideas|2010]], and [[GRASS SoC Ideas 2011#Ideas|2011]] which are still open.

* Project ideas of '''your own''' are also most welcome and often the best.

=== [[wxGUI]] ===

# Develop GUI support in wxPython for visualy analyzing series of raster map layers. The module should provide users with capabilities to browse and animate raster (and potentially also vector) data series in a 2D display and save outputs to animated GIF, MOV, or MPEG files. A related module that displays the series as small images and support re-ordering, deleting and adding raster maps (frames) to the series would also be helpful. To compare visually two images a slider functionality could be added to the 2D display, for example, to compare before and after images, or two consequent images in series. The series of data layers can be handled as multiple standard raster or vector layers or using the new time series support. See existing modules {{cmd|xganim}}, {{cmd|r.out.mpeg}}, [[NVIZ]]'s animation tools, and the [[Movies]] creation wiki page. There is also a related capability in the TclTk GUI. (co-mentor Helena Mitasova).
# Develop an interactive vector geometry selection and export tool for [[wxGUI]] as described in the trac ticket [http://trac.osgeo.org/grass/ticket/1471 #1471]
# Offer also (optional) "conventional" '''GUI layout''': For some users, the current approach of separate windows (SDI) leads to a '''windows flooding'''. This is a common complaint especially from newbies. Especially on large monitors or dual screen systems catching the [[wxGUI]] windows can be tedious when they appear on separate monitors (depends on windows manager, the much used KDE scatters typically the wxGUI windows all over the screen real estate). Almost each task generates a new wxGUI window which is freely floating around on the screen: [http://grass.osgeo.org/grass63/screenshots/images/wxgrass_digit-03.png example 1] and [http://grass.osgeo.org/grass63/screenshots/images/wxgrass_digit-01.png example 2]. On a dual-screen this may sum up to 50cm of distance! The idea is to capture all those windows in one frame. For details, see [[wxGUI#Layout| wxGUI layout]].
<center>
<gallery widths=400 heights=250>
Image:Wxgui_current.png|Current wxGUI layout with detached window components
Image:Wxgui_proposal.png|Proposal for wxGUI layout modification (Recomposition of existing toolbars, mapview and menus)
</gallery>
</center>
# ''Your idea here''

'''Willing to Mentor:''' [[User:Landa|Martin Landa]], [[User:MarisN|Maris Nartiss]], [[User:Mmetz|Markus Metz]], (''your name here'')

=== Raster ===

#Add '''[[OpenMP]] parallelization''' where appropriate, for example {{cmd|r.cost}}, {{cmd|r.surf.contour}}, {{cmd|r.watershed}}. It is important to understand which modules are processor bound, and concentrate on them. i.e. do not needlessly complicate the code of non-long running processor bound modules. A good working knowledge of ANSI C and {{wikipedia|OpenMP}} is required. ({{wikipedia|OpenCL}} and {{wikipedia|pthreads}} are fine too!)
#Create a new GRASS module to find the {{wikipedia|topographic_prominence}} of peaks from a raster elevation map within the region. (probably this would only make up 1/4 to 1/2 of a multi-part GSoC project)
# ''Your suggestion here!''

'''Willing to Mentor:''' Hamish (co-mentor parallelization and prominence projects), Wolf Bergenheim(''your name here'')

=== Vector ===

# Add '''[[OpenMP]] parallelization''' where appropriate, for example, {{cmd|v.surf.rst}} and {{cmd|v.vol.rst}} ''(co-mentor Helena Mitasova)''. (OpenCL and pthreads are fine too!) See above idea in the [[GRASS SoC Ideas 2012#Raster|Raster section]].
# Better '''support for wrap-around at 180 longitude''': Currently the raster engine is pretty good at wrapping data over 180 longitude. The vector data isn't, but it should be. This is a great task if by the end of the summer you'd like to be familiar with the implementation method of an entire vector stack of a fully featured modern GIS.
# Add '''break lines support to interpolation modules''' ({{cmd|v.surf.rst}}, {{cmd|v.surf.idw}}, {{cmd|v.surf.bspline}}). Current implementations provide no support to specify locations of cliffs or faults* thus leading to improper results within non-continous datasets. See [http://www.spatialanalysisonline.com/output/html/Breaklinesandnaturalboundaries.html Geospatial Analysis - a comprehensive guide. 3rd edition] for description. [*] well, some support exists, see {{AddonCmd|v.surf.icw}}.
# Speed up [[wxGUI]] handling and 2D display of large point clouds (several million points). This is likely to include additional "Level-1 Vector" support in the backend modules (for which a working knowledge of ANSI C is req'd).
# ''Your idea here'' ...

'''Willing to Mentor:''' [[User:Landa|Martin Landa]], [[User:Mmetz|Markus Metz]], Hamish (co-mentor for parallelization), Wolf Bergenheim, (''your name here'')

=== Imagery ===

# GRASS's imagery modules (for satellite, scanned maps, and orthophotos) act as enhanced raster modules. In GRASS 5 and 6 they were mostly implemented using interactive X-monitors which are not available in MS Windows and so are removed in the new cross-platform code of GRASS 7.
#* We need someone willing to '''port the old modules to work with GRASS 7''', including writing new '''wxPython GUI frontends''' to a number of existing tools and updating the imagery libraries to current raster library standards.
#* In addition, there are a number of '''improved/automated georectification tools''' which have not been merged into GRASS 5/6 which it would be nice to have updated and merged into the main code.
# Implement '''[[OpenMP]] (multithreading)''' as much as possible (where appropriate; OpenCL and pthreads are fine too)
# In addition to the porting of the georectification tools mentioned above, it would be interesting to implement an orthorectification tool for satellite imagery. Currently, GRASS only has {{cmd|i.ortho.photo}} for aerial photographs.
# Implement image segmentation algorithms and tools
# Implement region-based classification
# Implement hierarchical classification tools (e.g. being able to create a large class "forest", with subclasses of different types of forests)
# ''Your idea here''

See the [[Image_processing#Ideas_collection_for_improving_GRASS.27_Image_processing_capabilities|ideas for imagery improvement]] and [http://trac.osgeo.org/grass/wiki/Grass7/ImageryLib GRASS 7 ideas] wiki pages for more details.

'''Willing to Mentor:''' Hamish (co-mentor for parallelization), Markus Metz (orthorectification), (''your name here'')

=== Cartography and display ===

# Add SVG (and perhaps EPS) support to the display library, for use via {{cmd|d.graph}} and/or {{cmd|d.vect}}, and add SVG support to {{cmd|ps.map}} via a SVG to EPS converter tool (probably by adapting an existing GPL-compatible library). Code to be written in ANSI C. Step 1 is adding a Bézier curve rendering library function.
# Integrate Quantum/GRASS SVG output plugin with Inkscape. Python can serve as a common glue between these tools. The project would facilitate easy cartographic workflow while utilizing the advanced design functionality of Inkscape. This would be a two way bridge:
## QGIS/GRASS plugins to invoke an Inkscape process and send a data set.
## Inkscape plugin to query various OSGeo projects and display various data sets as layers.
# ''Your idea here ...''

'''Willing to Mentor:''' Hamish (as a co-mentor)

=== 3D visualization ===

# Optimize OGSF (and NVIZ/wxNVIZ) to '''display large 3D point clouds with uninterupted tought speed'''. OGSF + (wx)NVIZ should be able to rotate point cloud (i.e. LiDAR dataset) with 4 millions of points on medium hardware (i.e. 2GHz CPU with 2Gb RAM and GPU with hardware transform and lighting support and dedicated video RAM) with response time not greater than 1.0 second.
# Design and implement '''text displaying and styling in OGSF library''' and it's front-ends (NVIZ, [[wxNVIZ]]). Solution should be user configurable (fonts, colors, effects etc.) and multilanguage friendly.
# Design and implement user-provided '''symbol support in OGSF library''' and it's front-ends (NVIZ, [[wxNVIZ]]). Solution should support GRASS symbols, SVG, and/or simple EPS symbols.

# Drape multiple color maps over topography (equivalent to running r.patch or r.composite and draping the result; second raster is currently supported as transparency).
# Improve handling of z-exageration so that z-exag=1 is a realistic representation of landscape in terms of vertical scaling. Other default settings could also be improved to support wider range of data and improve robustness.

'''Willing to Mentor:''' [[User:Landa|Martin Landa]] (for 2), co-mentor for 1 and 5: Helena Mitasova, (''your name here'')

=== Volume modeling ===

# Develop '''r3.flow''' for computing 3D flow lines and 3D flow accumulation from 3D rasters
# Enhance volume interpolation module '''{{cmd|v.vol.rst}}''' for handling of data in space-time cube, including computation of gradients and hypercurvatures

'''Willing to Mentor:''' co-mentor Helena Mitasova, [[User:Huhabla|Sören Gebbert]]

=== Improved Python interface ===

Design '''sophisticated Python scripting interface''' for GRASS based on [http://grass.osgeo.org/programming7/pythonlib.html GRASS Python Scripting Library]. This API should become more intuitive and more integrative

GRASS GIS would gain even more attractiveness!

'''Willing to Mentor:''' [[User:Huhabla|Sören Gebbert]]

=== Other ===

* See also the [https://trac.osgeo.org/grass/query?status=assigned&status=new&status=reopened&order=priority&col=id&col=summary&col=status&col=type&col=priority&col=milestone&col=component&type=enhancement GRASS wish list]

# Implement selected modules (in C/C++) for geospatial analysis (kriging, etc.) based on [http://hpgl.aoizora.org/ HPGL] library (see also [http://hub.qgis.org/projects/quantum-gis/wiki/Python_Plugin_Ideas#Add-and-R-Free-geostatistic-toolbox-using-HPGL QGIS plugin wish]).
# Design and implement modern '''metadata management system''' for GRASS to support [http://www.opengeospatial.org/standards/cat OGC CSW] and INSPIRE discovery a view services

# ''Your idea here''

'''Willing to Mentor:''' Wolf Bergenheim (Python API, metadata management), [[User:Landa|Martin Landa]] (for HPGL) (''your name here'')

== Guidelines for Students ==

How do you maximize your chances of getting picked? First read the [http://code.google.com/p/google-summer-of-code/wiki/AdviceforStudents Google SoC FAQ]. Then talk to us about your idea. Try emailing our [http://lists.osgeo.org/mailman/listinfo/grass-dev dev-mailing list], or come and talk to us in [[IRC]] (#grass). You can also reach the mentors directly by emailing:
* [http://lists.osgeo.org/mailman/listinfo/soc The OSGeo SoC mailing list]



* If you are thinking about applying, do make a point of reading the "[http://google-opensource.blogspot.co.nz/2011/02/flip-bits-not-burgers-student-guide.html Flip bits not Burgers: The Student's Guide to the Summer of Code]" eBook

=== Getting started with GRASS coding ===

* The source code is maintained in a [http://trac.osgeo.org/grass/browser/grass/trunk SVN server] which is easy to browse

* Please review the submitting files for our coding standards
** {{src|SUBMITTING|branch=trunk}} for C coding rules
** {{src|SUBMITTING_PYTHON|branch=trunk}} for Python coding rules
** {{src|SUBMITTING_DOCS|branch=trunk}} for Documentantion coding rules

* There is lots of good info at the [http://trac.osgeo.org/grass/wiki GRASS Developer's wiki]
: See also the [[Development|development section]] of the GRASS user's wiki

== Guidelines for Mentors ==

* Un(?)official book: http://www.booki.cc/gsoc-mentoring/
* Some more hints on the [http://wiki.osgeo.org/wiki/Google_Summer_of_Code_2012_Administrative#Links OSGeo wiki]

== Accepted Ideas ==

# ''Python high level map interaction for GRASS GIS'' ([http://www.google-melange.com/gsoc/project/google/gsoc2012/zarch/11001 abstract])
#: Student: Pietro Zambelli
#: Mentor: Sören Gebbert
#: Backup mentors: Luca Delucchi, Martin Landa
#: Wiki page: [[GRASS SoC Ideas 2012/High level map interaction]]
# ''GRASS GIS WxGui front end for vector analysis modules'' ([http://www.google-melange.com/gsoc/project/google/gsoc2012/turek/38001 abstract])
#: Student: Stepan Turek
#: Mentor: Martin Landa
#: Backup mentor: Markus Metz
#: Wiki page: wiki/blog page maintained by the student (typically in this GRASS wiki, or the trac development wiki, with weekly progress reports)
# ''Image Segmentation in GRASS GIS'' ([http://www.google-melange.com/gsoc/project/google/gsoc2012/emomsen/20001 abstract])
#: Student: Eric Momsen
#: Mentor: Markus Metz
#: Backup mentors: Moritz Lennert, Pierre Roudier
#: Wiki page: [[GRASS GSoC Image Segmentation]]



[[Category:Development]]
[[Category:Community]]
[[Category:GSoC]]