GRASS SoC Ideas 2013

@ @

About

This is the GRASS page for Google Summer of Code 2013 (see the timeline). Here we will list project ideas and and other information related to the GRASS GSoC projects.

Ideas

• Also review ideas from 2009, 2010, 2011 and 2012 which are still open.

• Project ideas of your own are also most welcome and often the best.

General

• If you're really stuck for ideas, hunt around the wish list in the trac system.

• Clean-room write a LGPL or BSD/MIT-X GRASS data format plugin for GDAL/OGR. An option should exist to support both GRASS 6 and 7 versions of the format.

Why is a new plugin needed? Add here

• Improve and fix bugs in the QGIS GRASS Toolbox. Generally make it smoother to pass projects and workflows between the two.

Or simply use Sextante plugin in QGIS which does this already

GRASS GIS core improvements

• Implement a buffered binary balanced search tree using external memory: Rationale: some modules and library functions use a binary search tree, which can lead to out-of-memory errors for large datasets. A buffered binary balanced search tree using external memory would solve this problem and enhance the capability of GRASS to work with large datasets on limited hardware resources.

• Parallelize CPU-heavy modules using OpenMP, OpenCL (GPU), and/or pthreads.

Willing to Mentor:

Python

• GRASS magic extension for the IPython Notebook: http://www.google-melange.com/gsoc/proposal/review/google/gsoc2013/panwar9/1

Willing to Mentor: Massimo Di Stefano, Anna Petrasova

Symbology / Cartography

• Allow display of a vector legend in the map display (equivalent to current d.legend implementation for rasters)

• Expand symbology and re-classify groups

note that SoC only accepts coding projects, not graphics design or documentation projects.

• Add svg/eps support to a d.* module and ps.map would be quite helpful. See the d.graph help page and ps.map's "eps" and "vpoints" instructions. The first step would be to write a stand-alone tool in C to create d.graph commands; the second step would be to add as a new option in d.graph; a third step would be to backport this to GRASS 6's graphics API. See also trac #733 wish re. implementing Bézier curves in the display drivers.

Willing to co-mentor: Hamish Bowman

• Rework the complete set of thematic cartography tools such as d.vect.thematic and d.thematic.area and the related classification routines. This would comprise:
  • Revising the classification algorithms already implemented and possibly adding new ones (kmeans, Jenks)
  • Replace the existing d.vect.thematic script with a C-based module (in the likes of d.thematic.area) combing thematic cartography of points, lines and areas
  • Include representation of legend of the thematic map
  • Use colorbrewer rules to make classifications pretty
  • Implement one or several specific GUI interface(s) to this new module

note that since d.vect.thematic was written d.vect has added DB-column based sizing, rotation, and other tasks making parts of d.vect.thematic ready for much simplification.

• Generalized ASCII table input for d.legend (see trac #89 wish)
• Histogram sidebar support for d.legend and ps.map (see trac #1049 wish)

Willing to co-mentor d.legend bits: Hamish Bowman

Imagery

• Based on the work on segmentation in GSoC 2012 develop routines for object-based (or region-based) image classification. This probably entails:
  • Characterizing segments. This includes producing statistics such as mean, median, variance of the segmented data within each delineated segment (customized interface to r.statistics2).
  • Classifying segments based on the characteristics and (possibly) training areas
  • Interface with other modules in a consistent workflow (i.cluster, r.fuzzy, etc)

• Implement hierarchical classification tools (e.g. being able to create a large class "forest" with subclasses of different types of forests). Hierarchical classification is already used internally by i.gensigset/i.smap. Hierarchical segmentation can currently be done by using the output of a previous run of i.segment as input for the next run of i.segment with increased threshold.

• Interface with the Orfeo toolbox (OTB), which is an open source, ITK-based, C++ library of (spatial) image processing library. OTB implements a very wide set of interesting features for anybody working with raster data - in particular satellite imagery: radiometric corrections, orthorectification, filtering, feature extraction, image segmentation, classification, change detection, etc.

Vector

1. Line intersection: implement an efficient algorithm based on literature review, focusing on the Bentley-Ottmann algorithm and its derivates. The best or best two should be implemented. Coupled to the problem of calculating line intersections is the problem of calculating segment intersections, currently implemented in Vect_segment_intersection() and dig_find_intersection(), which could also be replaced with more efficient algorithms.
   • Rationale: the current function Vect_line_intersection() is "home-brew" and rather slow for lines with many segments, whereas the Bentley-Ottmann algorithm can find line intersections in logarithmic time per intersection.
   • Requirements: at least interest in, preferably knowledge of the art of searching and sorting (search trees, priority queues, heaps).
   • Implementation goals: One function to search for intersections between two lines, ignoring self-intersections, and another function to test one single line for self-intersections. The API and output should be compatible with the current Vect_line_intersection() function. Optionally an alternative to Vect_segment_intersection().
2. Your suggestion here!

Willing to Mentor: Markus Metz

Temporal GIS Algebra for raster and vector data

We (Soeren Gebbert and Thomas Leppelt) would like to develop a temporal GIS algebra for raster and vector data in GRASS7.

Role:

• Mentor: Soeren Gebbert
• GSoC Student: Thomas Leppelt

Implementation goals:

• Spatio-temporal vector algebra module t.vect.mapcalc
  • The algebra will be based on vector map operations provided from v.overlay (and, or, xor, not), v.buffer (buff_point, buff_line, buff_area), v.patch (patch), ... , temporal variables (day of year, weekday, datum, time, ...), temporal topology relations (predecessor, successor, follows, equals, ...) and spatial topology relations (equivalent, in, disjoint, ..)
  • The resulting module will be able to process space time vector datasets using expressions like:

# Compute the intersection between the space time vector datasets A and B
# from maps with equal time stamps. The STVDS A is used as temporal reference.
# A new STVDS C will be created with the same time stamps as A.
t.vect.mapcalc inputs=A,B timeref=A output=C expr="C = if(equal(B), and(A,B))"


 time     |STVDS|STVDS|STVDS
 stamp    |  A  |  B  |  C
-------------------------------------
Jan 2001  |  a1 |  b1 |  v.overlay ain=a1 bin=b1 op=and out=c1
Feb 2001  |  a2 |     | 
Mar 2001  |     |  b2 |
Apr 2001  |  a3 |     | 
May 2001  |  a4 |  b3 |  v.overlay ain=a4 bin=b3 op=and out=c2
Jun 2001  |     |  b4 |


# Nested operations are supported and temporal neighborhood computation
t.vect.mapcalc input=A,B,C tempref=A output=D \
    expr="D = if(successor(B) && predecessor(C), and(A, xor(successor(B), buff_point(predecessor(C), 100)))"

# Date and time can be used in the expression
t.vect.mapcalc input=A,B timeref=A output=C \
    expr="C = if(start_year() >= 2001 && start_month() > 6, and(A,B), not(A,B))"

• Spatio-temporal raster algebra module t.rast.mapcalc
  • The algebra will be based on the existing r.mapcalc raster map algebra, temporal variables (day of year, weekday, datum, time, ...), temporal topology relations (predecessor, successor, follows, equals, ...) and spatial topology relations (equivalent, in, disjoint, ..)
  • The resulting module will be able to process space time raster datasets using expressions like:

# Compute the sum between the space time raster datasets A and B
# from maps with equal time stamps. The STRDS A is used as temporal reference.
# A new STRDS C will be created with the same time stamps as A.
t.rast.mapcalc inputs=A,B timeref=A output=C expr="C = if(equal(B), A + B)"

# Spatio-temporal neighborhood computation. STRDS C will have the same time stamps as A.
t.rast.mapcalc input=B timeref=A output=C \
    expr="C = if(successor(B) && predecessor(B), (successor(B)[0,0] + B[0,0] + predecessor(B)[0,0])/3.0, B[0,0])"

• The GRASS GIS temporal framework will be utilized and extened with the spatio-temporal algebra
• The pygrass module interface will be used to call the raster mapcalc and vector overlay/buffer modules
• PLY will be used for lexical analysis and parser generation
• Spatio-temporal algebra will be equivalent for booth modules with about 60 internal variables and functions

Improve GRASS' kriging and 3D interpolation capabilities

One of GRASS' most outstanding features is its support for 3D raster (voxel) data. In fact, GRASS offers more functionality for 3D volumetric data processing than many expensive proprietary solutions. This GSoC project aims to improve on GRASS' existing strengths by significantly enhancing the methods for interpolation of data in voxel space. Currently, GRASS offers spline-based interpolation of 3D vector points to 3D voxel data. We plan to add the following (see also notes below):

• 3D geostatistics/kriging
• 3D interpolation using radial basis functions (RBF)
• transition probability models (TBM)
• stratigraphic modeling

These improved 3D interpolation capabilities would combine ideally with the 3D processing modules already present in GRASS (flexible 3D map algebra, export to VTK format for visualization, 3D vector data manipulation, etc.).

If this project can be realized as planned, it will allow GRASS to establish itself as the open source tool of choice for applications in geology, geophysics, soil science and archaeology, all of which have a need to model subsurface soil structures and properties based on 3D sampling points. These areas of application are currently dominated by expensive and inflexible proprietary tools, which is why we feel that this project could make a real difference for open source users.

Available mentors:

• Benjamin Ducke
• Sören Gebbert

Notes on 3D kriging: Since GRASS currently lacks native geostatistical capabilities, this project will cover 3D and 2D variograms, kriging interpolation, etc. There are already efforts underway in the GRASS community to supply complete geostatistical functionality and we expect our GSoC student to make full use of them (see [1]), minimzing the time this GSoC project will have to spent on the 3D kriging component.

Notes on radial basis functions (RBF): RBF are straight-forward interpolation functions. Most GIS users will be aware of Inverse Distance Weighting (e.g. GRASS has v.surf.idw), which is just one specific case of RBF. In the context of 3D interpolation, RBF provide simple and efficient interpolators useful for dense 3D samples (or for producing incomplete models from sparse samples).

Notes on transition probability models (TBM): TBMs allow to interpolate category (integer) data, such as soil classes in 3D space. Naturally, the result of such an interpolation will not be as accurate as that of interpolation of continuous data via splines or kriging. However, soil horizons, layers etc. are very common data in soil science and geology (borehole samples!) and there is currently no robust method for interpolating such data in GRASS. There is a FORTRAN implementation of TBM called T-PROGS (by Steven F. Carle) that is in the public domain. T-PROGS could be run from within GRASS as a command line tool or translated to C and converted into a "real" GRASS module (see [2]; see also [3]).

Notes on stratigraphic modeling: Another approach to soil horizon interpolation, that may be easy to implement in GRASS, is documented here: [4]. Basically, this involves taking 2D cross sections of soil horizons and extruding them into a 3D model in the most straight-forward way. This is something that is often done manually by soil scientists and archaeologists, but could be done more efficiently and transparently using a simple algorithm.

See also these GRASS mailing list posts for further information:

Further information

http://lists.osgeo.org/pipermail/grass-user/2010-January/054246.html

http://lists.osgeo.org/pipermail/grass-dev/2013-April/063389.html

Accepted Ideas

• See also the Trac wiki

1. GRASS GIS Interactive Scatter Plot Tool (abstract)

   Student: Stepan Turek

   Mentor: Martin Landa

   Backup mentors: Michael Barton

   Wiki page: GRASS GSoC 2013 GRASS GIS Interactive Scatter Plot Tool

2. Temporal GIS Algebra for raster and vector data in GRASS (abstract)

   Student: Thomas Leppelt

   Mentor: Sören Gebbert

   Backup mentors: Helena Mitasova & Michael Barton

   Wiki page: GRASS GSoC 2013 Temporal GIS Algebra for raster and vector data in GRASS

3. An Implementation of Horizon Based Stratigraphy for GRASS (abstract)

   Student: Tim Bailey

   Mentor: Benjamin Ducke

   Backup mentors: Michael Barton, Sören Gebbert, & Hamish Bowman

   Wiki page: GRASS GSoC 2013 An Implementation of Horizon Based Stratigraphy for GRASS