GRASS GSoC 2012 Image Segmentation

(See also other GRASS GSoC 2012 projects)

Student Name:	Eric Momsen
Organization:	OSGeo - Open Source Geospatial Foundation
Mentor Name:	Mentor: Markus Metz (backup mentors: M Lennert, P Roudier)
Title:	Image Segmentation

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.

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 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 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 algorithm's are added to the module, attention should be given to diversify so algorithms with different strengths are implemented first.

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. 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 + 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, or even image subgroup, 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)
  • 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)
• Output
  • raster map of segments (i.e. each pixel value represents id of segment the pixel belongs to)
  • 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 r.texture
    • geometric/morphological attributes: area, perimeter, length/width measures, see also 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

Lower priority

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

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
• 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: 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 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)
  • Comparison function T(t)... as t increases, threshold for similarity is lower. SPRING used: $T(t)=T(0)alpha^{t}$, where T(0) > ), t =0,1,2... and alpha <1
  • Size of smallest allowed area

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

References

TODO: complete references with links.

[1] Carleer, et al: Assessment of Very High Spatial Resolution Satellite Image Segmentations, 2005 (Evaluates 2 boundary and 2 region based algorithms.)

[2] Bins, et al: Satellite Imagery Segmentation: A Region Growing Approach, 1996 (Describes approach taken in SPRING software.)

[3] Cheng et. al.: Color image segmentation: advances and prospect, 2000 (survey of segmentation methods and color spaces)

[4] G. Meinel, M. Neubert: A Comparison of Segmentation Programs for High Resolution Remote Sensing Data, 20?? (Includes timing to complete segmentation)