Tässä blogisarjan toisessa osassa tarkastellaan avoimen lähdekoodin työkaluja joiden avulla minimaalisen kustannuksen tuottavaa polkua voidaan lähteä etsimään. Blogisarjan edellisessä osassa käsiteltiin aiheeseen liittyvää teoriaa.

Periaatteessa minimikustannuspolun määrittämiseen ei vaadita paikkatieto-ohjelmistoja. Tämä väite on kuitenkin totta oikeastaan vain sellaisissa tilanteissa, joissa käyttäjä saa kustannuspinnan valmiina tai haluaa tarkastella ongelmaa hyvin pitkälle abstrahoidun maailman kautta. Mikäli käyttäjä haluaa käyttää analyysinsa pohjana todellista karttapohjaa tai maastomalleja, QGIS:in kaltainen avoimen lähdekoodin paikkatieto-ohjelmisto on ensiarvoisen tärkeä työkalu kustannuspinnan muodostuksessa. Tämän blogin työkaluvertailussa oletuksena on, että kustannuspintarasteri on jo muodostettu ja tavoitteena on löytää optimaalinen reitti liikkua pitkin tätä rasteripintaa.

QGIS lisäosa Least-Cost path

QGISin lisäosavalikoimasta löytyy ratkaisu useimpiin yleisiin paikkatietohaasteisiin. Sama pätee myös pienimmän kustannuksen tuottavan polun etsimiseen. Paitsi että QGISillä voi tehokkaasti muodostaa varsinaisen kustannuspinnan, edellisessä blogissa kuvatut työvaiheet 2 ja 3 voi myös hoitaa QGIS:n avulla asentamalla QGIS:iin ongelman ratkaisemiseen soveltuvan laajennuksen (Plugins – Manage and Install Plugins – Least-Cost Path).

Laajennuksen käyttö on hyvin yksinkertaista. Laajennukselle annetaan syötteenä kustannuspinta (rasterimuotoisena) sekä aloitus- ja päätepisteet (vektorimuotoisena). Halutessaan voi määrittää tulostiedoston nimen ja valita mihin polkuun tulostiedosto tullaan tallentamaan. Käyttäjä voi myös vaikuttaa hieman laajennuksen toimintalogiikkaan mikäli hän on etsimässä minimikustannuspolkua useasta mahdollisesta päätepisteestä koostuvaan ongelmaan.

+ Helppo käytettävyys
+ Pystyy käsittelemään syötetiedot oletusmuotoisina
+ Tuottaa ratkaisun selkeässä ja havainnollistavassa muodossa
– Hitaus (algoritmin suorittamiseen kuluu 5-10 min koneen tehosta riippuen)

WhiteBox tools: komentorivityökalu rasterianalyyseihin

WhiteboxTools on MIT-lisenssillä varustettu kokoelma analyysityökaluja ja on kehitetty alkujaan Guelphin yliopistossa Kanadassa. WhiteboxTools on komentorivipohjainen hyvin laaja työkalukirjasto, jonka voi asentaa omalle koneelleen standalone asennuksena (binääritiedostot yleisimmille käyttöjärjestelmille löytyvät osoitteesta, mutta myös lähdekoodista asentaminen on mahdollista). Työkalun voi asentaa myös Docker imagesta ja algoritmeja on mahdollista hyödyntää myös QGIS-lisäosan kautta. Kannattaa kuitenkin huomioida, että QGIS-lisäosan ylläpito on lakkautettu ja resurssit on kohdennettu komentorivipohjaisen työkalukirjaston kehittämiseen.

Asennuksen jälkeen  työkalua Whitebox Tools toimii suoraan komentorivin kautta seuraavasti:

1. Kustannusetäisyystiedon tuottaminen

.\whitebox_tools.exe --run=”CostDistance” -v --wd=”path_to_input_data_folder” --source=”start_point.tif” --cost=”cost_rast.tif” --out_accum=”acc_cost.tif” --out_backlink=”back.tif”

2. Pienimmän kustannuksen tuottavan polun etsiminen

.\whitebox_tools.exe --run=”CostPathway” --wd=”path_to_input_data_folder” --destination=”points.tif” --backlink=”back.tif” --output=”path.tif” -v

tai kirjoittamalla yksinkertaisen python-ohjelman ja suorittamalla sen (tallenna skripti samaan kansioon whitebox_tools.exe tiedoston kanssa):

import os
import sys
from whitebox_tools import WhiteboxTools
 
wbt = WhiteboxTools()
 
# Aseta polku syöte- ja tulostetiedostot sisältävään kansioon
wbt.work_dir = os.path.dirname(os.path.abs_path(__file__)) + “\\testdata\\”
 
# Kustannusetäisyystieto
wbt.cost_distance(start_point.tif, cost_rast.tif, acc_cost.tif, back.tif)
 
# Pienimmän kustannuksen tuottava polku
wbt.cost_pathway(points.tif, back.tif, path.tif)

WhiteboxTools määrittää minimikustannuksen tuottavan polun kahdessa osassa. Luonnollinen seuraus tästä on se, että käyttäjä saa tällöin enemmän informaatiota tutkittavasta ilmiöstä. WhiteboxToolseja käyttämällä käyttäjä ei saa tulokseksi pelkkää vektorimutoista ratkaisupolkua vaan myös rasterimuotoiset tiedostot siitä, miten kerrytetty kustannus muuttuu tutkittavassa avaruudessa (acc_cost.tif) ja mistä suunnasta löytyy kunkin ruudun pienimmän kerrytetyn kustannuksen omaava naapuriruutu (back.tif). 

Suurin ongelma WhiteboxToolsin algoritmeissa on, että ne eivät osaa käsitellä vektorimuotoista tietoa. Tämä puute vaikuttaa sekä siihen, miten paljon esikäsittelyä syöteaineistot vaativat että siihen, miten havainnollistavassa muodossa ratkaisu saadaan tuotettua. Kuitenkin, jos puutteen tiedostaa, siihen voi reagoida jo ratkaisuprosessin alkuvaiheessa tuottamalla esimerkiksi QGIS:n avulla kustannusrasterin ohessa myös toisen, dimensioiltaan kustannusrasteria vastaavan ruudukon, jonka ainoat nollasta eroavat ruudut ovat päätepisteet sisältävät ruudut (aloitusruudun / aloitus- ja päätepisteruudun arvoksi voi asettaa minkä tahansa positiivisen vakion).

+ Huomattavasti tehokkaampi kuin QGIS-laajennus
+ Tuottaa paljon relevanttia kustannusetäisyysanalyysitietoa
– Tuki vektoritasojen käsittelyyn puuttuu
– Komentorivipohjainen (riippuu mistä tykkää)

GRASS: vanhassa vara parempi

GRASS on alkujaan jo vuonna 1984(!) kehitetty työkalu spatiaaliseen analyysiin. Se on kuitenkin edelleen aktiivisessa käytössä ja kehityksessä erityisesti tiedeyhteisössä. GRASS GIS on monipuolinen rasteri- ja vektoritiedostomuotojen analysointiin soveltuva ohjelmisto. 

GRASS tarjoaa vaihtoehdon kahden edellisen ratkaisun välimaastoon sijoittuvan vaihtoehdon. GRASS:n suurin vahvuus verrattuna edellä esiteltyihin lähestymistapoihin on se, että se on paitsi erittäin tehokas ja toimiva, myös huomattavasti WhiteboxToolseja käyttäjäystävällisempi. GRASS GIS on yksi QGIS:n ydinlaajennuksista ja sen voi käydä aktivoimassa QGIS:n asetuksista (Settings – Options – Processing – Providers) tai asentaa Plugin Managerin avulla. GRASS GIS:llä on sekä komentotulkkipohjainen että graafinen käyttöliittymä. Minimikustannuspolku saadaan määritettyä molemmilla tavoilla yhtä tehokkaasti.

Hyödyntämällä GRASSin omaa komentoriviä

1. Luo GRASS Mapset (linkki)

2. Vie tarvittava data Grass Mapsettiin syöttämällä GRASS Shelliin

r.in.gdal input=path_to_data/cost_rast.tif output=cost_rast2.tif

v.in.ogr input=path_to_data/start_point.gpkg output=start_point2

v.in.ogr input=path_to_data/end_point.gpkg output=end_point2

3. Suorita kustannusetäisyysanalyysi syöttämällä GRASS Shelliin

r.cost input=cost_rast2 output=acc_cost2 outdir=back2 start_coordinates=x1,y1 stop_coordinates=x2,y2

• start_coordinates=x1,y1 stop_coordinates=x2,y2 tilalle voi laittaa start_points=start_point2 stop_points=end_point2

4. Etsi pienimmän kustannuksen tuottava polku

r.path input=back2 format=degree vector_path=path2 start_coordinates=x1,y1,x2,y2

• start_coordinates=x1,y1,x2,y2 tilalle voi laittaa start_points=start_point2,end_point2

Huomaa, että tieto polun päätepisteistä voidaan antaa koordinaattimuotoisen tiedon lisäksi yhtä hyvin myös rasterimuotoisina karttatasoina (tällöin start_points avainsanan tilalla tulee vain olla start_raster). Myös tulospolun voi tallentaa halutessaan rasterimuotoisena (avainsananana toimii tällöin raster_path).

Hyödyntämällä GRASSin moduuleja

1. Suorita kustannusetäisyysanalyysi

• Processing Toolbox – GRASS – Raster – r.cost
• Mahdollisuus asettaa ylärajan sallitulle kustannukselle (mikäli käyttäjä ei halua määrittää polun päättymispistettä, tulos kertoo minne asti tietyllä resurssilla voi kuhunkin suuntaan edetä)
• Mahdollisuus kontrolloida prosessin suorittamiseen allokoitavan muistin määrää
• Tuottaa kolme tulostiedostoa (kerrytetyt kustannukset, suuntatieto pienimmän kerrytetyn kustannuksen naapuriruutuun ja tieto kustannusten kohdentamisesta)

2. Etsi pienimmän kustannuksen tuottava polku

• Processing Toolbox – GRASS – Raster – r.drain
• Syöteaineistoina toimivat edellisessä vaiheessa ajetun r.cost algoritmin tulostiedostot ja tieto polun päätepisteistä (vähintään aloituspiste tulee antaa syötteenä, mutta myös molemmat on mahdollista antaa, kunhan nämä pisteet sisältyvät samaan karttatasoon)
• Mahdollisuus laskea erinäisiä tunnuslukuja (esimerkiksi polun kokonaiskustannus)
• Tuottaa kaksi tulostiedostoa (ratkaisupolku rasterimutoisena ja vektorimuotoisena)

Huomaa, että vaikka GRASS komentorivin kautta käskyt toimivat millä tahansa QGIS versiolla, niin moduulien kanssa kannattaa käyttää LTR-versiota (esim. QGIS 3.14).

+ Erittäin tehokas (algoritmit menevät läpi sekunneissa)
+ Tuottaa paljon relevanttia kustannusetäisyysanalyysitietoa
+ Tuki niin vektori- kuin rasterimuotoisellekin tiedolle
+ Valittavissa komentorivipohjainen lähestymiskulma tai graafinen käyttöliittymä (ainut eroavaisuus on siinä, että r.path algoritmia ei ole implementoitu graafisen käyttöliittymän työkaluksi, mutta r.drain algoritmilla saa saman asian selville)
– GRASS Mapsetin käyttö, jos halutaan ajaa käskyjä komentorivin kautta

Muut työkaluvaihtoehdot

Myös SAGA tarjoaa minimikustannuspolun määrittämiseen soveltuvia algoritmeja (Accumulated cost, Least cost paths), mutta nämä algorit kärsivät niin vakavista suorituskykyongelmista, ettei niiden avulla pystynyt ratkaisemaan tässä blogissa käsiteltyä esimerkkiongelmaa. Samaan lopputulokseen päätyi myös GDAL & Skimage kirjastoihin perustuva python-ohjelma, jonka suoritus keskeytyi “Killed”-ilmoitukseen. Mainittakoot vielä, että on tietenkin mahdollista ohjelmoida myös itse algoritmi, joka kykenee määrittämään kustannusetäisyys- ja suuntarasteritiedostot ja niiden  perusteella löytämään minimikustannuspolun.

Tällaiset “brute force” algoritmit ovat kuitenkin vaarallisia, sillä mahdollisten polkujen määrä räjähtää helposti käsiin ja ohjelmien ajaminen syö tietokoneen koko muistin ja/tai laskentakapasiteetin. Jonkin verran helpotusta skaalautuvuusongelmiin voi hakea dynaamisesta ohjelmoinnista ja muistia säästävistä rakenteista (mm. priority queue). Kannattaa kuitenkin pitää mielessä, että avoimen lähdekoodin maailmassa on jo olemassa varsin toimivia keinoja pienimmän kustannuksen omaavien polkujen löytämiseen.

Yhteenveto

Tätä klassista paikkatieto-ongelmaa voi ratkoa siis useammalla avoimen lähdekoodin työkalulla. On kuitenkin tärkeä muistaa, että analyysin lopputulos on vain niin hyvä kuin lähtöaineisto. Eli vaikka tässä blogissa ei kustannuspinnan muodostamista käsitelty tarkemmin, se näyttelee keskeistä roolia lopputuloksen luotettavuuden kannalta.

Kenties lähtöaineistojen kerääminen ja muokkaaminen on blogisarjan seuraava osa. Mukavia reitityshetkiä minimikustannuspolkujen parissa!

Gispo

Gispo on suomalainen avoimen lähdekoodin paikkatietotalo, jonka palveluihin kuuluu paikkatietokonsultointia, sovelluskehitystä, koulutusta sekä ylläpitoa ja tukea.