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

From GRASS-Wiki
Revision as of 08:58, 26 July 2013 by Mastho (talk | contribs) (Weekly Reports)

Jump to: navigation, search

(See also other GRASS GSoC 2013 projects)

Student Name: Thomas Leppelt, Thünen Institute Braunschweig Germany
Organization: OSGeo - Open Source Geospatial Foundation
Mentor Name: Mentor: Soeren Gebbert Backup mentor: Helena Mitasova & Michael Barton
Title: Temporal GIS Algebra for raster and vector data in GRASS



Abstract

Using the TGRASS GIS API to create spatio-temporal vector and raster algebra to process massive vector and raster datasets based on their spatio-temporal relationships.

Background

The temporal modules in GRASS are capable of managing, analysing, processing and visualizing large spatio-temporal datasets. Additionally various temporal framework properties were implemented to describe the temporal and spatial relationships for datasets. Our aim is to develop modules, that can be used to process massive vector and raster datasets based on their spatio-temporal relationships. Therefore a spatio-temporal vector and raster algebra is needed and has to be implemented into GRASS7.

The idea

I would like to develop a temporal GIS algebra for raster and vector data in GRASS7. The idea is also posted on the GRASS SoC ideas page for 2013 (http://grasswiki.osgeo.org/wiki/GRASS_SoC_Ideas_2013).

The temporal modules in GRASS are capable of managing, analysing, processing and visualizing large spatio-temporal datasets. Additionally various temporal framework properties were implemented to describe the temporal and spatial relationships for datasets. Our aim is to develop modules, that can be used to process massive vector and raster datasets based on their spatio-temporal relationships. Therefore a spatio-temporal vector and raster algebra is needed and has to be implemented into GRASS7.

The project will have three new GRASS7 modules and additions to the GRASS GIS temporal library as outcome:

v.mapcalc

According to r.mapcalc for raster datasets, v.mapcalc will provide the functionalities of GRASS modules like v.overlay (and, or, xor, not), v.buffer (buff_point, buff_line, buff_area) and v.patch (patch) as algebraic expression for vector map operations. The implementation will be realised with PLY (http://www.dabeaz.com/ply/) and PyGRASS and will work as a standalone module. In the next step we will develop the temporal algebra that provides temporal variables (day of year, weekday, datum, time, ...) and spatio-temporal topology relations (predecessor, successor, follows, equals, in, meet, …) to perform analyses based on dataset spatio-temporal topologies. The TGRASS GIS API delivers the required functionalities to set up the spatio-temporal relationships for raster and vector datasets. This is the base to create GRASS modules for spatio-temporal vector and raster map calculations:

t.vect.mapcalc

The spatio-temporal vector map calculation module will be derived by combining the new implemented module v.mapcalc with the spatio-temporal algebra into a new module named t.vect.mapcalc. This module will provide all vector calculation options from v.mapcalc with additional spatio-temporal algebra. The implementation of a class structure will ensure that the new class is based on the classes for vector and spatio-temporal algebra and inherits all their functionalities.

t.rast.mapcalc

The spatio-temporal raster map calculation module will be derived by combining the existing module r.mapcalc with the new implemented spatio-temporal algebra. In result the arithmetic operation from r.mapcalc will be extended by spatio-temporal algebra. This module will be based on the same class for spatio-temporal algebra as t.vect.mapcalc to avoid redundancy.

v.mapcalc

Description

v.mapcalc performs overlay and buffer functions on vector map layers. New vector map layers can be created which are expressions of existing vector map layers, boolean vector operations and buffer functions.

Program use

The module expects its input as expression in the following form:

  result = expression

This structure is similar to r.mapcalc, see r.mapcalc. Where result is the name of a vector map layer that will contain the result of the calculation and expression is any valid combination of boolean and buffer operations for existing vector map layers. The input is given by using the first module option expression= . This option passes a quoted expression on the command line, for example:

 
v.mapcalc expression="A = B"

Where A is the new vector map layer that will be equal to the existing vector map layer B in this case.

 
v.mapcalc "A = B"

Will give the same result.

Operators and functions

The module supports the following boolean vector operations:

Boolean Name Operator Meaning Precedence Correspondent function
AND & Intersection 1 (v.overlay operator=and)
OR | Union 1 (v.overlay operator=or)
DISJOINT OR + Disjoint union 1 (v.patch)
XOR ^ Symmetric difference 1 (v.overlay operator=xor)
NOT ~ Complement 1 (v.overlay operator=not)

And vector functions:

Function name Description
buff_p(A, size) Buffer the points of vector map layer A with size
buff_l(A, size) Buffer the lines of vector map layer A with size
buff_a(A, size) Buffer the areas of vector map layer A with size

Notes

As shown in the operator table above, the boolean vector operators do not have different precedence. In default setting the expression will be left associatively evaluated. To define specific precedence use parentheses around these expressions, for example:

  
v.mapcalc expression="D = A & B | C"

Vmapcalc example1.png

Here the first intermediate result is the intersection of vector map layers A & B. This intermediate vector map layer is taken to create the union with vector map C to get the final result D. It represents the default behaviour of left associativity.

  
v.mapcalc expression="D = A & (B | C)"

Vmapcalc example2.png

Here the first intermediate result is taken from the parenthesized union of vector map layers B | C. Afterwards the intersection of the intermediate vector map layer and A will be evaluated to get the final result vector map layer D.

It should be noticed, that the order in which the operations are performed does matter. Different order of operations can lead to a different result.

Examples

This example needed specific region setting. It should work in UTM and LL test locations. First set the regions extent and create two vector maps with one random points, respectively:

 
g.region s=0 n=80 w=0 e=120 b=0 t=50 res=10 res3=10 -p3

v.random --o -z output=point_1 n=1 seed=1 
v.info point_1
v.random --o -z output=point_2 n=1 seed=2 
v.info point_2

Then the vector algebra is used to create buffers around those points, cut out a subset and apply different boolean operation on the subsets in one statement:

 
v.mapcalc --o expr="buff_and = (buff_p(point_1, 30.0) ~ buff_p(point_1, 20.0)) & (buff_p(point_2, 35) ~ buff_p(point_2, 25))"

v.mapcalc --o expr="buff_or  = (buff_p(point_1, 30.0) ~ buff_p(point_1, 20.0)) | (buff_p(point_2, 35) ~ buff_p(point_2, 25))"

v.mapcalc --o expr="buff_xor = (buff_p(point_1, 30.0) ~ buff_p(point_1, 20.0)) ^ (buff_p(point_2, 35) ~ buff_p(point_2, 25))"

v.mapcalc --o expr="buff_not = (buff_p(point_1, 30.0) ~ buff_p(point_1, 20.0)) ~ (buff_p(point_2, 35) ~ buff_p(point_2, 25))"

Temporal Algebra concept

An overview of the Temporal GIS Algebra concept for Raster and Vector Data is open for discussion and can be found here.

Project plan

Period Task Status / Notes
May 31 Getting familiar with PLY and PyGRASS, read documentations
June 7 Implement v.mapcalc
June 14 Working with TGIS API framework
June 21 Create temporal algebra draft, writing example programs
June 28 Creating spatio-temporal algebra by using TGIS API
July 5 Implementation of temporal algebra in PLY
July 12 Continue testing and implementation of temporal algebra
July 19 Writing documentation for temporal algebra
July 26 Implementation of t.vect.mapcalc with documentation and tests in progress
August 2 Mid-term evaluations deadline
August 9 Write documentation and tests for t.vect.mapcalc
August 16 Implementation of t.rast.mapcalc
August 23 Continue implementation of t.rast.mapcalc
August 30 Continue implementation of t.rast.mapcalc
September 6 Write documentation and tests for t.rast.mapcalc
September 16 Suggested 'pencils down' date
September 20 Write tutorials for t.vect/t.rast.mapcalc
September 27 Final evaluation

Weekly Reports

Week 1 - 2012-05-31

What did I do this week?

  • Studying Python-Lex-Yacc parsing tool.
  • Getting familiar with PyGRASS.
  • Working with the Backus Naur form of context free grammar.
  • Create example programs for the vector algebra in PLY.

What will I be working on next week?

Implement the vector algebra GRASS module v.mapcalc with PLY and PyGRASS.

Did I meet with any stumbling blocks?

First I was a little bit confused about how PLY works. It took a while until I understood the principals and the functioning.

Week 2 - 2012-06-7

What did I do this week?

  • Develop a first implementation of vector algebra in PLY.
  • Create a new website on google code.
  • Upload v.mapcalc module into the new repository.

What will I be working on next week?

Getting familiar with the GRASS GIS Temporal Framework API.

Did I meet with any stumbling blocks?

Some problems with the vector algebra lexer class for boolean operations.

Week 3 - 2012-06-14

What did I do this week?

  • Fixed bugs and worked on comments for the v.mapcalc module.
  • Reading the documentation for the GRASS GIS Temporal Framework API.
  • Building up a concept for the temporal algebra together with my mentor.

What will I be working on next week?

Write example programs for the temporal algebra

Did I meet with any stumbling blocks?

The concept get considerably large and it was hard to design it clearly arranged and intuitive.

Week 4 - 2012-06-21

What did I do this week?

  • Extended the v.mapcalc module with a command list class (Important for later use in preprocessing steps of the temporal algebra).
  • Create a developer wiki page for the temporal algebra concept.
  • Working on the concept.
  • Writing first example programs, experience with the TGIS framework.

What will I be working on next week?

Start implementing the temporal algebra.

Did I meet with any stumbling blocks?

No major problem this week.

Week 5 - 2012-06-28

What did I do this week?

  • Using PLY for lexical analysis of temporal expressions.
  • Utilize TGIS methods to evaluate temporal selection expressions.
  • Start to implement an intern map list structure to store generated map lists, derived from temporal expressions, independently from input type (Vector, Raster).
  • Writing the structure for the temporal algebra and started to fill in the required methods.

What will I be working on next week?

Continue the implementation of the temporal algebra.

Did I meet with any stumbling blocks?

I try to keep track of the temporal algebra. Sometimes it gets very complex.

Week 6 - 2012-07-05

What did I do this week?

  • Implement functions to compare space time datasets by their topology and to perform temporal selection on raster and vector datasets.
  • Create Module t.select for temporal selection.
  • Changed some functionalities in the temporal algebra concept.

What will I be working on next week?

Continue the implementation of the temporal algebra functions like temporal buffering, snapping and shifting.

Did I meet with any stumbling blocks?

No big Problems this week

Week 7 - 2012-07-12

What did I do this week?

  • Implement functions for temporal buffering, snapping and shifting.
  • Add global temporal variables into the algebra (td(), start_time, end_time, ...)
  • Started to integrate conditional statements into the algebra.

What will I be working on next week?

This week I participate in the GRASS community sprint in Prague. Discussing and working intensively on the temporal algebra for the next six days.

Did I meet with any stumbling blocks?

Only minor problems.

Week 8 - 2012-07-19

What did I do this week?

  • Participation in the GRASS community sprint in Prague.
  • Discussing and working intensively on the temporal algebra.
  • Add global temporal variables into the algebra (td(), start_time, end_time, ...)
  • Implemented functions for if-statements in the temporal algebra.
  • Implemented topological relationships for if-statements.
  • Finished to implement the hash-operator (#) for map counting in conditional statements.
  • New module t.select alpha version in repository ready for testing.

What will I be working on next week?

Testing and documentation of the GRASS module t.select. Start to integrate the vector operations into the temporal vector algebra.

Did I meet with any stumbling blocks?

Due to direct contact to GRASS developers at the meeting in Prague all problems could be solved.

Week 9 - 2012-07-26

What did I do this week?

  • Implemented functions for temporal operators into the temporal algebra.
  • Finsihed the module t.select.
  • Wrote the manual page for t.select.
  • Started to implement vector operations into the temporal algebra.

What will I be working on next week?

Continue documentation of the GRASS module t.select and the integration of the vector operations into the temporal vector algebra.

Did I meet with any stumbling blocks?

Only minor problems occured.

Repository

The code for this project can be found in a svn repository at code.google: grass-gis-temporal-algebra