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

From GRASS-Wiki
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



Contents

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

t.select

Description

t.select performs selection of maps that are registered in space time datasets using temporal algebra.

Program Use

The module expects an expression as input parameter in the following form:

"result = expression"

The statement structure is similar to r.mapcalc. Where result represents the name of a space time dataset (STDS)that will contain the result of the calculation that is given as expression on the right side of the equality sign. These expression can be any valid or nested combination of temporal operations and functions that are provided by the temporal algebra.
The temporal algebra works with space time datasets of any type (STRDS, STR3DS and STVDS). The algebra provides methods for map selection from STDS based on their temporal relations. It is also possible to temporally shift maps, to create temporal buffer and to snap time instances to create a valid temporal topology. Furthermore expressions can be nested and evaluated in conditional statements (if, else statements). Within if-statements the algebra provides temporal variables like start time, end time, day of year, time differences or number of maps per time interval to build up conditions. These operations can be assigned to space time datasets or to the results of operations between space time datasets.

The type of the input space time datasets must be defined with the input parameter type. Possible options are STRDS, STVDS or STR3DS. The default is set to space time raster datasets (STRDS).

As default, topological relationships between space time datasets will be evaluated only temporal. Use the s flag to activate the additionally spatial topology evaluation.

The expression option must be passed as quoted expression, for example:

t.select expression="C = A : B"

Where C is the new space time raster dataset that will contain maps from A that are selected by equal temporal relationships to the existing dataset B in this case.

Temporal Algebra for t.select

The temporal algebra provides a wide range of temporal operators and functions that will be presented in the following section.

Temporal relations

Several temporal topology relations between space time datasets are supported:

equals            A ------
                  B ------

during            A  ---- 
                  B ------

contains          A ------
                  B  ---- 

starts            A ----
                  B ------

started           A ------
                  B ----

finishs           A   ---- 
                  B ------

finished          A ------
                  B   ----

precedes          A ----
                  B     ----

follows           A     ----
                  B ----

overlapped        A   ------
                  B ------

overlaps          A ------
                  B   ------

over              booth overlaps and overlapped

The relations must be read as: A is related to B, like - A equals B - A is during B - A contains B

Topological relations must be specified in {} parentheses.

Temporal selection

The temporal selection simply selects parts of a space time dataset without processing raster or vector data.

The algebra provides a selection operator : that selects parts of a space time dataset that are temporally equal to parts of a second one by default. The following expression

C = A : B

means: Select all parts of space time dataset A that are equal to B and store it in space time dataset C. The parts are in this case time stamped maps.

In addition the inverse selection operator !: is defined as the complement of the selection operator, hence the following expression

C = A !: B

means: select all parts of space time time dataset A that are not equal to B and store it in space time dataset (STDS) C.

To select parts of a STDS by different topological relations to other STDS, the temporal topology selection operator can be used. The operator consists of topological relations, that must be separated by the logical OR operator || and the temporal selection operator. Both parts are separated by comma and surrounded by curly braces: {"topological relations", "temporal selection operator"}

Examples:

C = A {equals,:} B
C = A {equals,!:} B

We can now define arbitrary topological relations using logical OR operator to connect them:

C = A {equals||during||overlaps,:} B

Select all parts of A that are equal to B, during B or overlaps B.

The selection operator is implicitly contained in the temporal topology selection operator, so that the following statements are exactly the same:

C = A : B
C = A {:} B
C = A {equal,:} B

Same for the complementary selection:

C = A !: B
C = A {!:} B
C = A {equal,!:} B

Conditional statements

Selection operations can be evaluated within conditional statements.

Note A and B can either be space time datasets or expressions.

if statement                         decision option                        temporal relations
  if(if, then, else)
  if(conditions, A)                    A if conditions are True;              temporal topological relation between if and then is equal.
  if(conditions, A, B)                 A if conditions are True, B otherwise; temporal topological relation between if, then and else is equal.
  if(topologies, conditions, A)        A if conditions are True;              temporal topological relation between if and then is explicit specified by topologies.
  if(topologies, conditions, A, B)     A if conditions are True, B otherwise; temporal topological relation between if, then and else is explicit specified by topologies.

The conditions are comparison expressions that are used to evaluate space time datasets. Specific values of temporal variables are compared by logical operators and evaluated for each map of the STDS.

The supported logical operators:

Symbol  description

  ==    equal
  !=    not equal
  >     greater than
  >=    greater than or equal
  <     less than
  <=    less than or equal
  &&    and
  ||    or

Temporal functions:


td(A)                   Returns a list of time intervals of STDS A

start_time()            Start time as HH::MM:SS
start_date()            Start date as yyyy-mm-DD
start_datetime()        Start datetime as yyyy-mm-DD HH:MM:SS
end_time()              End time as HH:MM:SS
end_date()              End date as yyyy-mm-DD
end_datetime()          End datetime as  yyyy-mm-DD HH:MM

start_doy()             Day of year (doy) from the start time [1 - 366]
start_dow()             Day of week (dow) from the start time [1 - 7], the start of the week is Monday == 1
start_year()            The year of the start time [0 - 9999]
start_month()           The month of the start time [1 - 12]
start_week()            Week of year of the start time [1 - 54]
start_day()             Day of month from the start time [1 - 31]
start_hour()            The hour of the start time [0 - 23]
start_minute()          The minute of the start time [0 - 59]
start_second()          The second of the start time [0 - 59]
end_doy()               Day of year (doy) from the end time [1 - 366]
end_dow()               Day of week (dow) from the end time [1 - 7], the start of the week is Monday == 1
end_year()              The year of the end time [0 - 9999]
end_month()             The month of the end time [1 - 12]
end_week()              Week of year of the end time [1 - 54]
end_day()               Day of month from the start time [1 - 31]
end_hour()              The hour of the end time [0 - 23]
end_minute()            The minute of the end time [0 - 59]
end_second()            The second of the end time [0 - 59]            

Additionally the number of maps in intervals can be computed and used in conditional statements.
The operator to count the number of maps is the hash #.

A{contains,#}B

This expression computes the number of maps from space time dataset B which are during the time intervals of maps from space time dataset A.
A list of integers (scalars) corresponding to the maps of A that contain maps from B will be returned.

Furthermore the temporal algebra allows temporal buffering, shifting and snapping with the functions buff_t(), tshift() and tsnap() respectively.

buff_t(A, size)         Buffer STDS A with granule ("1 month" or 5)
tshift(A, size)         Shift STDS A with granule ("1 month" or 5)
tsnap(A)                Snap time instances and intervals of STDS A

Examples

Select all maps from space time dataset A which have equal time stamps with space time dataset B and C and are ealier that Jan. 1. 2005 and store them in space time dataset D.

D = if(start_date() < "2005-01-01", A : B : C)

Select all maps from space time dataset A which contains more than three maps of space time dataset B, else select maps from C with time stamps that are not equal to A and store them in space time dataset D.

D = if(A {contain, #} B > 3, A {contain, :} B, C)

Select all maps from space time dataset B which are during the temporal buffered space time dataset A with a map interval of three days, else select maps from C and store them in space time dataset D.

D = if(contain, td(buff_t(A, "1 days")) == 3, B, C)

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
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 in progress
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.

Week 10 - 2012-08-02

What did I do this week?

  • Implemented vector operations for the vector overlay function like (intersection, union, disjoint union, exclusive union and the complement).
  • Fixed bugs in the temporal algebra.
  • More testing of the temporal algebra.

What will I be working on next week?

Continue the integration of the vector operations into the temporal vector algebra and write documentation and tests.

Did I meet with any stumbling blocks?

Only minor problems occured.

Week 11 - 2012-08-09

What did I do this week?

  • Finished implementation of vector operations for the vector overlay function like (intersection, union, disjoint union, exclusive union and the complement).
  • Integrated a new function to evaluate spatio-temporal operators with PLY.
  • Worked on a lot minor fixes and tests.

What will I be working on next week?

Finish the the temporal vector algebra and write documentation. Start implementing the temporal raster algebra.

Did I meet with any stumbling blocks?

Only minor problems occured.

Week 12 - 2012-08-16

What did I do this week?

  • Integrated buffer function into temporal vector algebra.
  • Finished temporal vector algebra.
  • Worked on documentation and examples for the temporal vector algebra.

What will I be working on next week?

Write documentation and start implementing the temporal raster algebra.

Did I meet with any stumbling blocks?

I travelled to Estonia for my PhD thesis, so I had limited time for my project.


Week 13 - 2012-08-23

What did I do this week?

  • Write tests and documentation for the temporal vector algebra.
  • Fixed a lot of bugs in the temporal vector algebra.
  • Worked on examples for the temporal vector algebra.

What will I be working on next week?

Start implementing the temporal raster algebra.

Did I meet with any stumbling blocks?

I was still busy with the temporal vector algebra this week. Some difficult and time intensive bugs prevent me from starting with the raster algebra.

Week 14 - 2012-08-30

What did I do this week?

  • Fixed some more bugs in the temporal vector algebra.
  • Made some improvements to speed up the meta data analysis.
  • Finished the temporal vector algebra.
  • Started with the temporal raster algebra.

What will I be working on next week?

Continue implementing the temporal raster algebra.

Did I meet with any stumbling blocks?

Only minor problems occurred

Week 15 - 2012-09-06

What did I do this week?

  • Worked on the temporal raster algebra.
  • Implemented the lexical analysis for expressions.
  • Added arithmetic operations to the temporal raster algebra.
  • Rearrange the command list to work with r.mapcalc expression strings.

What will I be working on next week?

Continue implementing the temporal raster algebra.

Did I meet with any stumbling blocks?

Occurring problems could be solved.

Week 16 - 2012-09-13

What did I do this week?

  • Finished the temporal raster algebra.
  • Implemented the correct precedence for arithmetic operations.
  • Get the arithmetic operators running.
  • Improved and fixed the command list to work better with r.mapcalc expression strings.
  • Created the new module t.rast.mapcalc to work with the temporal raster algebra,

What will I be working on next week?

Adding some more r.mapcalc functions to the temporal raster algebra and writing documentation for t.rast.mapcalc

Did I meet with any stumbling blocks?

Occurring problems could be solved.


Week 17 - 2012-09-20

What did I do this week?

  • Added additional functions to the raster algebra.
  • Wrote documentation for the temporal raster algebra.
  • Did intensive testing and fixed a lot bugs.

What will I be working on next week?

Writing some tutorials for the vector and raster algebra and add some more functions from r.mapcalc into the algebra.

Did I meet with any stumbling blocks?

Only minor issues.

Repository

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