L7 - Raster Algorithms L7 Raster Algorithms NGEN06(TEK230) Algorithms in Geographical Information Systems L7 - Raster Algorithms Background Store and analyse the geographic information Raster data or Vector data. Raster data have been common in analysis in physical geography. Aerial and satellite images within GIS Continuous surface presentations

L7 - Raster Algorithms Aim The main objective is to familiarize the students with some raster algorithms. After this lecture the student should be able to write a minor program that treat raster data in one of the areas cost analysis, shaded relief, viewshed and resampling. L7 - Raster Algorithms Content 1. 2.

3. 4. 5. 6. Introduction Local and regional operators Morphological operators Shaded relief Resampling Flow analysis in hydrology L7 - Raster Algorithms Example of raster data and raster analysis

1. Digital maps Cost analysis, location analysis, overlay analysis and generalisation (e.g. by morphological operators) 2. DTMs and DEMs Viewshed analysis, flow analysis, and shaded relief . 3. Images (most often aerial or satellite images) Resampling, image classification and information extraction. L7 - Raster Algorithms Example of raster analysis 1) Morphological operators

This is a basic method for digital maps. Several manipulations and analysis of raster maps are based on morphological operators. (shrink and expand) L9 genralization 2) Shaded relief A shaded layer is created (based on the DEM) for a fictitious sun; this layer is then added to a map to enhance the feeling of topography. 3) Resampling of images To use e.g. an ortophoto in a geographic analysis it must be geocoded. Geocoding - resampling of the image to the new geometry. 4) Flow analysis in hydrology All above are regional operations

L7 - Raster Algorithms Vector vs. Raster Distances, area of polygon, point-in-polygon are all fairly simple to perform with raster data. Result is often worse than in the vector case since the resolution of the raster data is not that good Cost analysis for raster maps Means that the path between two pixels with the lowest total cost (sum of the pixel values for the path) is found. Raster version of Dijkstras algorithm can be used. Raster data is often used for locational analyses. For example, all buildings that are closed to a lake, close to a road and far from industries are sought.

L7 - Raster Algorithms Local and regional operations Kernel filter L7 - Raster Algorithms Morphological operators L7 - Raster Algorithms Shaded relief

Enhance the feeling of topography in a map. L7 - Raster Algorithms Shaded relief L7 - Raster Algorithms Computing the shaded relief L7 - Raster Algorithms Approximating the partial derivatives Steepest gradient approach

L7 - Raster Algorithms Approximating the partial derivatives Sobel filter L7 - Raster Algorithms Resampling Original grid Transformed grid L7 - Raster Algorithms

Resampling method It is important to state what kind of raster data that is used and the application of the resampled data. If the raster data is a digital map (or contain any type of data in nominal or ordinal scale) it is not allowed to do calculations on the raster data values. A recommended resampling method is then nearest neighbour. If the data is an image (which contain continuous data that is in ratio or interval scale ) it is allowed to do calculations on the raster data values L7 - Raster Algorithms Nearest neighbour resampling

Original grid Transformed grid L7 - Raster Algorithms Inverse distance resampling L7 - Raster Algorithms Flow analysis in hydrology L7 - Raster Algorithms Drainage Direction 2 ways

7 8 9 6 7 9 5 8 8 Simplified: In a matrix of 9 cells, the water from the centre cell flows to the neighboring cell with the lowest

elevation OR, for more realistic algorithms, is distributed proportionally to a number of neighboring cells with lower elevation Surface flow algorithms over digital elevation models Single flow direction algorithm SFD L7 - Raster Algorithms Multiple flow direction algorithm MFD

99.6 100 100. 7 100 100 99.8 100. 99.8 98.8 4 fi tan i x 8 tan j

j 1 x for all > 0 L7 - Raster Algorithms Topographic form Multiple flow direction algorithm Form based flow direction algorithm A convex surface (flow is split)

L7 - Raster Algorithms Multiple flow direction algorithm L7 - Raster Algorithms Form based flow direction algorithm A concave surface one directional flow Artefacts in real world data L7 - Raster Algorithms

Flat area Break line Sink Stream Network Flow Accumulation Grid. Area draining in to a grid cell 0 0 0

0 0 0 0 2 2 2

0 0 0 0 10 0 1 0

0 1 0 0 14 0 1

0 0 4 1 19 1 0 0

0 2 2 10 0 4 1 0 0

2 0 0 1 14 19 0 1

Flow Accumulation > 10 Cell Threshold Stream Network for 10 cell Threshold Drainage Area 0 0 0 0 0

0 0 2 2 2 0 0

0 0 10 0 1 0 0 1

0 0 14 0 1 0 0

4 1 19 1 0 0 0 2

2 10 0 4 1 0 0 2 0

0 1 14 19 0 1 Watershed Draining to Outlet Estimation of flow accumulation

Why we need to create new flow distribution algorithm ? An empirical equation is used to estimate flow distribution in most flow distribution Algorithms. Concave verses convex form. fi tan i x 8 tan

x for all > 0 j j 1 The flow is distributed to some or all down slope cells, no influence from upslope cells. Problems related to sinks, man made structures and flat areas. Triangular form-based multiple flow distribution algorithm (TFM)

Area of one triangle =1/8 area of grid cell Triangles has a constant slope C1 8 1 7 2 3 6M 5 4 C2 Triangular form-based multiple flow distribution algorithm

(TFM) C1 8 1 7 2 3 6M 5 4 C2 Triangular form-based multiple flow distribution algorithm (TFM) 1

2 2 3 3 4 Triangular form-based multiple flow distribution algorithm (TFM) Drainage area estimation on standard surfaces Convex Mathematica l estimation

TFM D8 Concave Plane Saddle TF M