WP4: Data-integratie services in GIS

Faculteit Toegepaste Wetenschappen Vakgroep Telecommunicatie en Informatieverwerking

iDAS: Intelligente Data-integratie Services voor Actualisatie van Spatiale data

WP4: Data-integratie services in GIS Voortgangsrapport September 2007

Niels Charlier Sidharta Gautama Rik Bellens

Hoofdstuk 1

Inleiding 1.1

Probleem- en doelstelling

De belangrijkste stap in het voortdurende proces van actualisatie van Geografische Informatie Systemen, zoals de GRB-data, is het detecteren van veranderingen en fouten; in een ruimere bewoording het meten van de kwaliteit van de data. Het automatiseren van deze detectie of kwaliteitsmeting is geen gemakkelijke opdracht. De centrale vraag in dit project is: op welke manier kan beeldinformatie gebruikt worden om op een betrouwbare manier uitspraken te maken over spatiale kwaliteit van een GIS dataset? De informatie in beelddata biedt potentieel voor automatische veranderingsdetectie. Automatische beeldanalysetechnieken leveren echter geen zuivere beschrijving van de beeldinformatie. Hierbij duiken verschillende problemen op die deze technieken niet volledig betrouwbaar maken. Deze problemen staan nader beschreven in sectie 1.3. Samengevat beoogt het iDAS-project de praktische implementatie van automatische kwaliteitsmeting en veranderingsdetectie van GRB-objecten op basis van beelddata en derivate producten. Het project bevat twee aspecten waaronder 5 werkpakketten: 1. Definitie en implementatie van een kwaliteitsrapport voor spatiale data Hoe kunnen verschillende aspecten van spatiale kwaliteit in GIS-data gedefinieerd en gemeten worden? WP 1: Definitie van absolute en relatieve spatiale kwaliteit WP 2: GIS-implementatie voor het meten van spatiale kwaliteit 2. Definitie en implementatie van een GIS-signaalfunctie op basis van beelddata Hoe kan beeldinformatie gebruikt worden om op een betrouwbare manier een rapportering te maken over spatiale kwaliteit van GIS-data WP 3: Informatiekarakterisatie van beeldclassificatie WP 4: Data-integratie services in GIS WP 5: Analyse van databronnen voor actualisatie van GRB-objecten

1

Dit werkpakket: “Data-integratie services in GIS” maakt dus deel uit van het tweede aspect. De doelstellingen hiervan zijn om een aantal operatoren te defini¨eren die voldoen aan de volgende voorwaarden: - De operatoren zijn in staat een raster/vector vergelijking te doen, zodanig dat beeldinformatie kan ge¨ıntegreerd worden bij het genereren van een kwaliteitsrapport; - Er wordt vertrokken van GIS-operatoren voor kwaliteitsmeting uit WP1 en WP2; - Zeer belangrijk hierbij is dat de gebruiker feedback krijgt over de betrouwbaarheid van het antwoord op de GIS-query. We kunnen dus stellen dat het de bedoeling is, gegeven de informatie uit de beeldclassificatie zoals die geoptimaliseerd is in WP3 als “input data” en gekoppeld is aan informatie over de betrouwbaarheid hiervan, een gefundeerde stelling te doen over de kwaliteit van de vectori¨ele data; waarbij de betrouwbaarheid van de input data wordt gepropageerd en mee ge¨ıntegreerd wordt in het eindresultaat.

1.2

Opbouw van het rapport

Het rapport begint met een algemene inleiding waarin het probleem en de doelen van het project en de plaats van dit werkpakket in dit project geschetst wordt. In de volgende sectie gaan we dieper in op de probleemstelling van dit werkpakket. In hoofdstuk 2 zullen we een theoretisch kader scheppen dat nodig is voor de rest van dit rapport. Hierin worden de fundamenten van vaagverzamelingen uitgelegd en de toepassing die ze kan hebben op geografische informatiesystemen (vaaggebieden); deze theorie wordt vervolgens gebruikt om een aantal GIS-operatoren uit te breiden. In hoofdstuk drie wordt de modellering van de de geclassificeerde beelddata en hun imperfectie besproken en een concrete toepassing uitgewerkt om betrouwbare kwaliteitsmeting en veranderingsdetectie uit te voeren. In hoofdstuk vier wordt dit concreet toegepast op data uit het testgebied. Tot slot wordt de stand van zaken bekeken en de zaken die nog moeten gedaan worden opgesomd.

1.3

Imperfecties in de beeldclassificatie

In Werkpakket 1 worden een aantal kwaliteitsmaten formeel gedefinieerd en besproken. Deze zijn grotendeels bedoeld om vector/vector vergelijkingen uit te voeren. Zoals reeds eerder vermeld is het in de eerste plaats de bedoeling een aantal operatoren voor kwaliteitsmeting te definiren die het toelaten om een vector/raster vergelijking uit te voeren. Het gaat echter verder dan dit. In werkpakket 3 werd er gewerkt aan een optimale classificatie van de beelddata, die zo betrouwbaar mogelijk informatie biedt over de werkelijkheid. Deze classificaties worden als “input” gebruikt om de vergelijking met de vectori¨ele data te maken. Er blijven echter significante problemen van onbetrouwbaarheid in de beeldclassificaties bestaan.

2

Er zijn twee oorzaken voor imperfecties in de beeldclassificatie: misclassificatie (waarbij een cel in het raster een verkeerde klasse toegewezen krijgt) en ontbrekende informatie (waarbij de klasse van een cel onbekend is). Drie belangrijke fenomenen duiken hierdoor op: * Verplaatsing: De positie maar ook de vorm en grootte van objecten worden vervormd. Een mogelijke oorzaak is bijvoorbeeld een schaduw die als deel van het object wordt gezien. * Fragmentatie: Een object wordt gefragmenteerd in verschillende delen, doordat delen van het object ontbreken. Dit kan bijvoorbeeld veroorzaakt worden door een overweg die niet als deel van de weg wordt beschouwd. * Ruis: Verschillende pixels in de omgeving van het object worden valselijk beschouwd als een deel van het object. Verplaatsing en ruis ontstaan door misclassificatie, fragmentatie kan zowel door misclassificatie als ontbrekende informatie veroorzaakt worden. Er moet op gewezen worden dat dit probleem niet evident is. In het verleden is er men bij theorien omtrent meting van kwaliteit er immers steeds vanuit gegaan dat men dit doet aan de hand van een referentie waarvan de kwaliteit hoog genoeg is om als een perfecte representatie van de werkelijkheid door te gaan, of toch ten minste een significant hogere kwaliteit dan de data die men wil testen. In dit geval willen we echter de kwaliteit van data testen aan de hand van een referentie die zelf per definitie imperfect is. De kwaliteit van de rasterdata kan mogelijks zelfs slechter zijn dan de kwaliteit van de vectorile data. Toch kunnen zij eventueel potenti¨eel bieden om fouten en veranderingen te detecteren. In de eerste plaats zullen wij ons dus moeten richten op de voorstelling van de rasterdata en zijn inherente onbetrouwbaarheid. We willen onze kennis zo natuurgetrouw modelleren, dat wil zeggen: representeren wat we weten alsook wat we niet weten en in welke mate we er zeker van zijn. Zo zal die kennis over betrouwbaarheid gepropageerd wordt naar de conclusies die uit deze data voortkomen. In een sterk vereenvoudigde beschouwing kunnen we stellen dat er drie mogelijke “scherpe” antwoorden zijn op een kwaliteitsmeting: 1. De kwaliteit van het testgebied is voldoende 2. De kwaliteit van het testgebied is onvoldoende 3. De kwaliteit van het testgebied is onbekend omwille van de onbetrouwbaarheid van de classificatie Tot slot nog n opmerking. Omdat vectorile data gemakkelijk kan omgezet worden naar een rastervorm, kunnen operatoren die raster/raster vergelijkingen doen zonder problemen gebruikt worden om vector/raster vergelijkingen te doen. En aangezien raster/raster vergelijking theoretisch gemakkelijker uit te werken zijn omdat zij vertrekken van dezelfde soort data, zal ik voor de rest van dit rapport uitgaan van een raster/raster vergelijking.

3

Hoofdstuk 2

Vage gebieden en operatoren 2.1

Inleiding op de vaagverzamelingleer

De vaagverzamelingenleer werd het eerst geintroduceerd door Zadeh [13]. Een traditionele verzameling (of “scherpe” verzameling) is gekoppeld aan een booleaanse lidmaatschapsfunctie. Dat wil zeggen dat ieder mogelijk element ofwel tot de verzameling behoort, ofwel niet. De vaagverzameling generaliseert deze definitie, door aan ieder element een lidmaatschapsgraad te koppelen, een getal uit het interval [0, 1] die bepaalt in welke mate het element tot de verzameling behoort. De lidmaatschapsgraad van de verzameling Ve kan dan als volgt formeel voorgesteld worden: µVe : U → [0, 1] U wordt het universum genoemd, dat is de verzameling van alle mogelijke elementen. Wanneer de lidmaatschapsgraad 0 is, behoort het element niet tot de verzameling. Wanneer de lidmaatschapsgraad 1 is, behoort het element volledig tot de verzameling. Wanneer de lidmaatschapsgraad ergens daartussen is, behoort het element gedeeltelijk tot verzameling, waarin de grootte van het getal de mate aanduidt waarin het element tot de verzameling behoort. De vaagverzameling wordt dan formeel vaak als een verzameling van koppels voorgesteld: Ve , {(x, µ(x)) | µVe (x) > 0} De verzameling van alle vaagverzamelingen over het universum U word genoteerd als ℘(U e ) (de vage machtsverzameling over U ). Een genormaliseerde vaagverzameling is een vaagverzameling waarbij minstens n element lidmaatschapsgraad 1 heeft. Een alpha-cut van een vaagverzameling is als volgt gedefini¨eerd: Veα = {x | µVe (x) ≥ α} De drager (support) supp(Ve ) en kern (core) core(Ve ) van een vaagverzameling worden als volgt gedefinieerd: supp(Ve ) , {x | x ∈ U ∧ µVe > 0} 4

core(Ve ) , {x | x ∈ U ∧ µVe = 1} Het complement van eeen vaagverzameling is als volgt gedefinieerd: comp(Ve ) , {(x, 1 − µ(x)) | µV (x) < 1} De doorsnede en unie van twee vaagverzamelingen Ve1 en Ve1 worden als volgt gedefinieerd: Ve1 ∩ Ve2

, {(x, i(µVf1 (x), µVf2 (x)) | i(µVf1 (x), µVf2 (x)) > 0}

Ve1 ∪ Ve2

, {(x, u(µVf1 (x), µVf2 (x)) | u(µVf1 (x), µVf2 (x)) > 0}

Waarbij de functies i : [0, 1] × [0, 1] → [0, 1] en u : [0, 1] × [0, 1] → [0, 1] respectievelijk de t-norm en de t-conorm genoemd worden. Een t-norm correspondeert met de “en”-operator uit de booleaanse logica, en moet voldoen aan de volgende axioma’s: ∀a ∈ [0, 1] : i(a, 1) = a (randvoorwaarde) ∀a, b, d ∈ [0, 1] : b ≤ d ⇒ i(a, b) ≤ i(a, d) (monotoniteit) ∀a, b ∈ [0, 1] ∀a, b, d ∈ [0, 1]

: i(a, b) = i(b, a) (commutativiteit) : i(a, i(b, d)) = i(i(a, b), d) (associativiteit)

Een t-conorm correspondeert met de “of”-operator uit de booleaanse logica, en moet voldoen aan de volgende axioma’s: ∀a ∈ [0, 1]

: u(a, 0) = a (randvoorwaarde)

∀a, b, d ∈ [0, 1] : b ≤ d ⇒ u(a, b) ≤ u(a, d) (monotoniteit) ∀a, b ∈ [0, 1] : u(a, b) = u(b, a) (commutativiteit) ∀a, b, d ∈ [0, 1]

: u(a, u(b, d)) = u(u(a, b), d) (associativiteit)

Verder geldt er dat i(a, b) = 1 − u(1 − a, 1 − b)

(2.1)

wat correspondeert met de wetten van de Morgan uit de booleaanse logica. Hierdoor bestaat er voor elke t-norm een corresponderende t-conorm. De t-norm en t-conorm van Zadeh zijn als volgt gedefinieerd: iZ (a, b)

= min(a, b)

uZ (a, b)

= max(a, b)

Zij worden ook de standaard t-norm en t-conorm genoemd. Er kan bewezen worden dat zij respectievelijk een bovengrens en ondergrens voor alle andere t-normen en t-conormen zijn. 5

Voor een vaagverzameling kan ook een scalaire cardinaliteit gedefinieerd worden. Die is, wanneer Ve een discrete lidmaatschapsfunctie heeft: X card(V ) , µVe (x) (2.2) x∈U

Wanneer Ve echter een continue lidmaatschapsfunctie heeft wordt die: Z µVe (x) card(V ) ,

(2.3)

U

2.2

Vage gebieden en vage rasters

Geometrische figuren in een bepaalde ruimte worden traditioneel gerepresenteerd door de verzameling van punten die tot deze figuur behoren. Dit is een deelverzameling van de verzameling van alle punten die tot de beschouwde ruimte behoren. Deze verzameling zal gedefinieerd zijn aan de hand wijze waarop locaties uitgedrukt worden. Doorgaans wordt dit gedaan met een Cartesiaans cordinatensysteem dat gedefinieerd is door n assen voor een n-dimensionale ruimte. Dus, de figuur is dan gedefinieerd door een verzameling G ⊂ Rn . De locatie en vorm van gebieden op een tweedimensionale kaart kunnen op deze manier voorgesteld worden. Een vaaggebied is een eenvoudige uitbreiding van e over het universum R2 . Een vaaggebied dit concept naar een vaagverzameling G heeft geen scherpe afgelijnde grenzen, maar eerder vage grenzen. Vaaggebieden vindt men in de literatuur meermaals terug [6], het meest uitgebreid worden zij besproken in [12]. Zie ook een illustratie uit dit werk in figuur 2.1.

e waarbij tinten van Figuur 2.1: Een visuele voorstelling van een vaag gebied A, grijs de lidmaatschapsgraden aanduiden (1 als volledig zwart, 0 als volledig wit). Voor de duidelijkheid is er een grijze lijn rond het vaag gebied getrokken. Bovendien wordt als illustratie de lidmaatschapsgraden van de punten op een rechte door het gebied voorgesteld op een grafiek.

6

Voor een computervoorstelling van het object moet de verzameling van mogelijke locaties wel gediscretizeerd worden naar een raster van m × n cellen. Een gebied G kan dan voorgesteld worden als G ⊂ Nn × Nm waar Na staat voor de verzameling van natuurlijke getallen in het interval [0, a]. Een rasterkaart specifieert voor iedere cel in een raster een aantal attributen. Formeel kan elk attribuut voorgesteld worden door een functie We beperken ons hier tot de vorm en locatie van objecten, waardoor we uiteraard slechts n booleaans attribuut nodig hebben, de lidmaatschap van de cel tot het object. Om een vaaggebied in een raster voor te stellen hoeven de attribuutverzameling van dit enige attribuut alleen maar uitbreiden naar het interval [0, 1], als representatie van de lidmaatschapsfunctie. We zullen in de rest van het hoofdstuk de ruimte van locaties voorstellen als de verzameling U . In het geval van een m × n raster is U = Nn × Nm maar de definities zijn in principe algemeen toepasbaar.

2.3

Vage Buffering

Een buffer is een GIS-operator die een gebied uitbreid in een zekere mate. Een gangbare definitie voor een buffer is: het gebufferd gebied is de verzameling van alle punten die zich binnen een zekere afstand d van het oorspronkelijk gebied bevinden. Uiteraard is dit een scherpe definitie die toegepast wordt op scherpe gebieden. Een vage bufferoperatie zal echter moeten: 1. Kunnen inwerken op vage gebieden (en dus ook op scherpe gebieden); 2. Een gebied met vage grenzen resulteren. De bufferoperatie wordt formeel voorgesteld als BU F F ER : ℘(U e ) → ℘(U e ) In [7] stelt Guesgen een vage bufferoperatie voor een vaag raster voor. Deze bufferoperatie kan samengevat worden aan de hand van de volgende definitie: e ∈ ℘(U Voor elk vaag gebied: G e ): µBU F F ER(Fe) (l) 7→ max{ψ(µFe (l0 ), δ(l, l0 ))} l0 ∈U

De definitie gebruikt een afstandsfunctie δ(l, l0 ) : U ×U → R tussen twee locaties in U . In een raster gebruiken we δ((x, y), (x0 , y0 )) 7→ max(|x − x0 |, |y − y0 |), dit is het aantal cellen om van cel l naar l0 te gaan, waarbij men cellen met tenminste n hoek gemeenschappelijk als buren beschouwd. De bufferfunctie ψ : [0, 1] × N → [0, 1] beeldt de lidmaatschapsgraad van een bronlocatie l0 en de afstand tussen de twee cellen af op de nieuwe lidmaatschapsgraad van de bestemmingslocatie l. Ze is monotonisch stijgend in z’n eerste argument en monotonisch dalend in z’n tweede argument, wat betekent dat cellen met een hogere lidmaatschapgraad een grotere invloed hebben en dat cellen die veraf zijn een lagere invloed hebben, wat strookt met de intu¨ıtie. Ook moet het voldoen aan de conditie ψ(m, d) ≤ m and d2 = d1 + d0 ⇒ ψ(m, d2 ) ≥ ψ(ψ(m, d1 ), d0 ). Deze condities creert het “fading out“ effect dat we beogen met de buffer. Als m voorbeeld van een bufferfunctie stelt Guesgen ψ(m, d) 7→ 1+d voor.

7

Onze nieuwe benadering herdefinieert de buffer operatie als volgt: µBU F F ER(Fe) (l) 7→ U {µFe (l0 )µBe (δ(l, l0 ))} l0 ∈U

waar U de gegeneraliseerde t-conorm is: U{a1 , a2 ...an } 7→ u(a1 , u(a2 , u(..., u(an ))))

(2.4)

e een strikt dalende, genormaliseerde vaagverzameling over het univeren waar B sum R is die staat voor een vage representatie van de buffergrootte. Enerzijds werd de max operator uit Guesgen’s defenitie dus gegeneraliseerd naar meer algemene een t-conorm. Het idee hierachter is dat de globale buffer wordt aanzien als de unie van de buffer van iedere cel. Wanneer men de t-conorm van Zadeh (het maximum) gebruikt, zal een “sterkere buffer” steeds een “zwakkere” buffer volledig “overwinnen”. Wanneer een andere t-conorm gebruikt wordt, zullen de twee buffers met elkaar gedeeltelijk samengevoegd worden. Dit effect is gedemonstreerd in figuur 2.2. Anderzijds werd de bufferfunctie van Guesgen gespecifi¨eerd als ψ(m, d) 7→ mµBe (d).

(a)

(b)

(c)

Figuur 2.2: Twee cellen (a) niet gebufferd (b) vaag gebufferd (met Zadeh’s t-conorm) and (c) vaag gebufferd met de t-conorm of Dubois uα D (a, b) = 1 − (1−a)(1−b) met α ∈ [0, 1] (α = 0.90). max(1−a,1−b,α)

Als t-conorm stellen we de t-conorm van Dubois voor. Die is als volgt gedefinieerd: (1 − a)(1 − b) uα met α ∈ [0, 1] D (a, b) = 1 − max(1 − a, 1 − b, α) Deze t-conorm is gelijk aan de t-conorm van Zadeh wanneer α = 0 en is gelijk aan de “probabilistische” t-conorm uP (a, b) = a+b−ab wanneer α = 1. Op deze manier geeft de parameter α de mate aan waarin buffer samengevoegd moeten worden. Wat hiervan het practische nut kan zijn zal in het volgende hoofdstuk duidelijk worden. Als lidmaatschapsgraad voor de vage buffergrootte stellen we de volgende functie voor: 1 µBe (x) = x met λ > 1 λ Om de totale buffergrootte B te berekenen nemen we de cardinaliteit van de e vaagverzameling B: Z +∞ e B = card(B) = µBe (x)dx 0

8

Z

+∞

= 0

=

1 dx λx

1 ln(λ)

Hieruit kunnen wij afleiden dat λ = exp(

1 ) B

Op deze manier kunnen we een scherpe buffergrootte fuzzifi¨eren (een scherpe waarde omzetten naar een vaagverzameling). We vatten de buffer operator nu samen als:   1 (δ(l, l )) µBU F F ERα (Fe) (l) 7→ Uα µ (l ) 0 0 e D F B exp( B1 )x l0 ∈U

2.4 2.4.1

Kwaliteitsmaten Volledigheid

Het kwaliteitsaspect volledigheid kan opgesplitst worden in twee soorten fouten: omissiefouten (ontbrekend gedeelte) en comissiefouten (het gedeelte dat teveel is). e de refeStel dat Te het gebied is waarvan we de kwaliteit willen testen en R rentie die we hiervoor gebruiken. Dan defini¨eren we omissie voor vage rasterdata als volgt: OM : ℘(U e ) × ℘(U e ) →

R

OM : ℘(U e ) × ℘(U e ) → [0, 1] e e 7→ card(compl(Te) ∩ R) e OM (T , R) e e e 7→ OM (T , R) OM (Te, R) e card(R) OM is de absolute omissie en is uitgedrukt in aantal cellen. Merk dus op dat de grootte hiervan relatief is ten opzichte van de resolutie. OM is de genormaliseerde omissie en geeft steeds een waarde uit het interval [0, 1] terug, waarbij 0 geen omissie betekent en 1 volledige omissie (alles uit het referentiegebied ontbreekt in het testgebied). Comissie voor vage rasterdata defini¨eren we als volgt: COM : ℘(U e ) × ℘(U e ) →

R

COM : ℘(U e ) × ℘(U e ) → e e 7→ COM (T , R)

[0, 1]

e 7→ COM (Te, R)

e card(Te ∩ compl(R)) e COM (Te, R) card(Te)

Er wordt weer een onderscheid gemaakt tussen absolute comissie (COM ) en genormaliseerd omissie. COM is de genormaliseerde comissie en geeft steeds 9

een waarde uit het interval [0, 1] terug, waarbij 0 geen omissie betekent en 1 volledige omissie (alles uit het onderzochte testgebied is niet aanwezig in het referentiegebied).

2.4.2

Positionele nauwkeurigheid

In WP1 worden als mogelijke kwaliteitsmaten voor (absolute) positionele nauwkeurigheid onder meer epsilon [10] [1] en proportionele epsilon [5] besproken. We zullen deze uitbreiden voor rasterdata en vaaggebieden. We gaan ervan uit dat de afstand tussen twee locaties δ(a, b) in het universum U gedefinieerd is. De afstand van om het even welke locatie l tot een scherp object X ⊆ U wordt nu gedefinieerd als: δ : U × ℘(U ) → δ(l, X) 7→ δ(l, ∅) 7→

R min δ(l, x) met X 6= ∅

x∈X

0

Stel dat T het gebied is waarvan we de kwaliteit willen testen en R de referentie die we hiervoor gebruiken. Dan defini¨eren we de epsilon-nauwkeurigheid als volgt: ε : ℘(U ) × ℘(U ) → ε(T, R) 7→

R max δ(x, R) x∈T

Deze definitie is echter zeer afhankelijk van uitschieters. Wanneer we zoeken naar systematische fouten, willen we deze uitsluiten. De functie P beeldt een afstand d af op het deel van T dat binnen deze afstand ligt van R. PT,R : R

→

PT,R (d) 7→

[0, 1] S{x ∈ T | δ(x, R) ≤ d} S(T )

waarbij de functie S : ℘(D) → R een object op een grootte afbeeldt (wanneer de objecten eendimensionaal zijn zal dit lengte zijn, wanneer zij tweedimensionaal zijn, zal dit oppervlakte zijn; dit om compabiliteit met de vectori¨ele definitie van epsilon-nauwkeurigheid te behouden en deze uit te breiden). The proportionele epsilon εp met p ∈ [0, 1] is gedefinieerd als εp : ℘(U ) × ℘(U ) → εp (T, R) 7→

R min

d

PT ,R (d)≥p

Men moet p dicht bij 1 kiezen, bijvoorbeeld 0.99, waardoor 1 procent van de punten van T die het verst van R liggen als uitschieters beschouwd worden.

10

Nu moeten de definities nog uitgebreid worden naar vaaggebieden. We bee perken ons hier tot een vaag referentiegebied R. Hiervoor moeten we alleen maar de definitie van afstand uitbreiden: e) → δ : U × ℘(U

R R1

e 7→ δ(l, X)

0

eα ) dα δ(l, X supx µXe (x)

De definities voor epsilon is nu zo goed als analoog: e 7→ ε(T, R)

e max δ(x, R) x∈X

Ook de proportionele epsilon kan analoog gedefinieerd worden aan de hand van de functie P: PT,R˜ : R

→

PT,R˜ (d) 7→ εp : ℘(U ) × ℘(U e ) → εp (T, R) 7→

[0, 1] e ≤ d} S{x ∈ T | δ(x, R) S(T ) R min PT , R ˜ (d)≥p

11

d

Hoofdstuk 3

Modellering van de classificatiedata 3.1

Inleiding tot de possibiliteitstheorie

Possibiliteitstheorie is een theorie om onzekerheden te behandelen [3] [14], als alternatief voor de probabiliteitstheorie. De possibiliteitstheorie wilt de probabiliteitstheorie echter niet vervangen maar zal in andere situaties gebruikt worden. Probabiliteiten waren historisch gezien gebasseerd op frequenties en dus objectief, terwijl possibiliteiten altijd subjectief zijn en men er nooit een frequentie-gebasseerde interpretatie aan kan geven. Maar ook met subjectieve probabiliteiten is er een semantisch verschil. Daar waar probabiliteiten de zekerheid aangeven van bepaalde uitkomsten, geven possibiliteiten de mate van mogelijkheid aan van de uitkomsten. Dat wil zeggen dat verschillende uitkomsten die disjunctief voorkomen tegelijkertijd volledig mogelijk kunnen zijn. Onder een possibiliteitsdistributie van een veranderlijke X verstaan we elke U → [0, 1] afbeelding πX , met U het universum waarin X waarden aanneemt, die voldoet aan ∃x ∈ U : πX (x) = 1 Terwijl de normalisatievoorwaarde van probabileiten zegt dat de som van alle probabiliteiten van de mogelijke uitkomsten 1 is; moet bij possibiliteiten minstens ´e´en uitkomst volledig mogelijk zijn en dus een possibiliteit hebben van 1. Voor iedere gebeurtenis A ⊆ U kunnen we nu zowel een possibiliteitsmaat als een neccesiteitsmaat defini¨eren: P osX (A)

=

sup πX (x) x∈A

N ecX (A)

=

1 − P osX (A)

Waarbij A het complement is van A ten opzichte van het universum U . De noodzakelijkheid van A is dus gelijk aan de mate waarin het niet mogelijk is dat de gebeurtenis A niet plaatsvindt. Wanneer de noodzakelijkheid gelijk is aan 1 is de gebeurtenis volledig zeker. 12

Een possibiliteitsdistributie kan worden voorgesteld als een genormaliseerde vaagverzameling Ve ∈ ℘(U e ). Dan is dus πX (x) = µVe (x). Een speciale toepassing van possibiliteitsdistributies is het gebruik van possibilistische waarheidswaarden of ”possibilistic truth values“ (PTV) [11] [2] ter uitbreiding van de tweewaardige logica. Deze stellen de mate van mogelijkheid dat een propositie waar is of vals is voor door een possibiliteitsdistributie over het booleaanse universum I = {T, F }. De possibilistische waarheidswaarde e t(p) van een propositie p ∈ P is formeel gedefinieerd door middel van de functie e t : P → ℘(I). e De vaagverzameling stelt hier dus een possibiliteitsdistributie voor. {(T, 1)} betekent volledig waar, {(F, 1)} betekent volledig vals en {(T, 1), (F, 1)} betekent dan weer volledig onbekend.

3.2

Naar een possibilistisch model

Vele beeldclassificatoren resulteren in eerste instantie voor iedere cel een probabiliteitsdistributie over de mogelijke klassen. Dit noemt men de softclassificatie. Hieruit wordt meestal voor iedere cel de klasse met de grootste probabiliteit gekozen, dit resulteert in de harde classificatie. Met onze nieuwe benadering opteren wij er echter voor om de soft-classificatie als beginpunt te nemen. Op deze manier behouden we immers informatie over de mate van zekerheid en precisie van de classificatie. En aangezien het immers in de bedoeling is, zo natuurgetrouw mogelijk onze kennis te modelleren, willen we deze informatie niet weggooien. Bij wijze van voorbeeld zullen we een classificatie in vier mogelijke klassen beschouwen: Wegbaan, Gebouw, Vegetatie en Grond. Stel dat we de kwaliteit van een straat willen meten, dan zijn we enkel genteresseerd in de klasse “Wegbaan”. Voor een bepaalde cel kan de beeldclassificator bijvoorbeeld de volgende probabiliteitsdistributie geven: P (W egbaan) = 0.40 P (V egetatie) = 0.20

P (Gebouw) = 0.20 P (Grond) = 0.20

We willen nu een maat van zekerheid vaststellen dat deze cel tot een straat behoort. Men zou kunnen voorstellen de probabiliteit P(Wegbaan) te gebruiken. De verdeling van de overige drie klassen interesseert ons in feite niet, en de kans dat de cel niet tot een straat behoort is de som ven deze probabiliteiten. Dit leid tot een tweevoudige probabiliteitsdistributie P (W egbaan) = 0.40 and P (¬W egbaan) = P (Gebouw) + P (V egetatie) + P (Grond) = 0.60. Dit leidt tot de conclusie dat het eerder aanneembaar is dat de cel niet tot een straat behoort, dan dat ze dit wel zou doen. Dit strookt echter niet met onze intu¨ıtie, die ons zegt dat het eerder aanneembaar is dat de cel wel tot een straat behoort omdat zijn probabiliteit het grootst is. Het probabilistische model geeft dus een slechte representatie van onze kennis. Door de overige klassen bij elkaar op te tellen, verliezen we immers een belangrijk onderscheid. Stel dat we bijvoorbeeld een probabiliteit van 0.25 voor alle vier de klassen hebben. Dan wilt dit zeggen dat we eigenlijk niets weten over die cel. Hebben we echter 0.25 voor straat en 0.75 voor huis, dan weten we dat ze zeer waarschijnlijk tot een huis behoort en dus wellicht niet tot de straat. Dus ondanks het feit dat we enkel informatie over de klasse Wegbaan 13

willen behouden, willen we de verhouding tegenover de andere probabiliteiten niet verliezen. Om dit te bereiken, zouden we de probabiliteitsdistributie kunnen omzetten naar een possibiliteitsdistributie. Dit is semantisch verdedigbaar, omdat het hier om subjectieve probabiliteiten gaat die niet frequentie-gebasseerd zijn. Dit kan gebeuren volgens de volgende transformatie: πX (x) =

P (X = x) max{P (X = y)} y

Hierdoor krijgen we de volgende possibileitsdistributie: π(W egbaan) = 1 π(V egetatie) = 0.5

π(Gebouw) = 0.5 π(Grond) = 0.5

Dit wil zeggen dat het volledig mogelijk is dat de cel tot een straat behoort, maar slechts half zo mogelijk is dat de cel tot de klasse Gebouw, Vegetatie of Grond behoort. In possibiliteitstheory wordt disjunctie niet bereikt door optelling, maar door het maximum te nemen. Willen wij slechts informatie over de klasse “Wegbaan”, dan krijgen we: π(W egbaan) π(¬W egbaan)

= P os({W egbaan}) = 1 = P os({Huis, V egetatie, Grond}) =

max{0.5, 0.5, 0.5} = 0.5

We kunnen dit ook schrijven in de vorm van een possibilistische waarheidswaarde: t˜(W egbaan) = {(T, 1), (F, 0.5)} Nu hebben we een perfecte representatie van onze kennis: het is het meest mogelijk dat de cel tot een straat behoord, maar toch ook half zo mogelijk dat de cel niet tot een straat behoord. Als alle klassen gelijk gedistribueerd waren, zouden we de ”onbekende“ PTV {(T, 1), (F, 1)} krijgen, heeft straat echter een probabiliteit van 1 of 0; dan krijgen we {(T, 1)} of {(F, 1)}, die een absolute zekerheid representeren. Wanneer wij aan iedere cel een PTV associeren, defini¨eert dit onze kennis over de klasse. Elementen kunnen dan zeker een straatcel zijn, zeker niet, volledig onbekend of wellicht iets tussen deze drie extremen.

3.3

Het vage egg/yolk model

Het is echter niet evident om deze voorstellingswijze te interpreteren. Daarom willen we nog ´e´en stap verder gaan. Het egg-yolk model [8] is een model om imprecisie in the grenzen van een geografisch gebied toe te laten. Hierbij is een gebied voorgesteld als een paar van verzamelingen (L, U ) waarbij L de ondergrens (de punten die noodzakelijk tot het gebied behoren) en U de bovengrens van het gebied (de punten die mogelijks tot het gebied behoren) is. Zij moeten dus per definitie voldoen aan de voorwaarde L ⊆ U . Gevisualiseerd lijkt dit op een spiegelei, met L de dooier en de rest van U het eiwit. 14

Vaaggebieden worden echter aanzien als een veel beter alternatief voor het egg/yolk model omdat ze vage grenzen toelaat (“scrambled eggs”) [6]. Wij combineren echter beide theorien en stellen echter een zogenaamd vaag egg/yolk model voor. Deze hebben een vaaggebied als bovengrens en een vaaggebied als ondergrens. Hiervoor putten we uit de theorie van de “tweevoudige vaagverzae U e ) die voldoen aan de melingen” [4]. Dit is een paar van vaagverzamelingen (L, volgende conditie: e ⊆ core(U e) supp(L) (3.1) De semantische interpretatie van een tweevoudige vaagverzameling kan als volgt eC , U eC ) is een kennisrevoorgesteld worden, de tweevoudige vaagverzameling (L presentatie van de klasse C met de volgende gelijkheden: µUeC (x) µLeC (x)

= P os(x ∈ C) = N ec(x ∈ C)

eC aan in welke mate cellen mogelijks tot C behoren Met andere woorden geeft U e C aan in welke mate cellen noodzakelijk tot C behoren. Dit leidt ons en geeft L tot een zeer eenvoudige afleiding uit de cel-PTV mapping: µUe (x) µLe (x)

= e t(x ∈ C)(T ) = 1−e t(x ∈ C)(F )

Merk op dat dat conditie (3.1) equivalent is met de normalisatieconditie van de PTV’s. Andere vaaggebieden die we uit het model kunnen afleiden zijn e COM P (L(C)) die aangeeft in welke mate cellen mogelijks niet tot het gebied e (C)) die aangeeft in welke mate cellen onmogelijk tot het behoren, en COM P (U e gelijk is aan de harde classificatie. gebied behoren. Merk ook op dat supp(L) In figuur 3.1 zie je een stuk van een straat in Sint-Denijs: een grondwaarheid en de vage ondergrens en de bovengrens ge¨extraheerd van geclassificeerde beelddata zoals beschreven in deze sectie. De afbeelding was geclassificeerd met een neuraal netwerk.

(a)

(b)

(c)

Figuur 3.1: Straat in Sint-Denijs. (a) Grondwaarheid van de straat dergrens van de straat (c) Bovengrens van de straat

3.4

(b) On-

Onbetrouwbaarheid van de classificatie

We hebben een model van imperfectie opgebouwd voor de klassen. We hebben getoond hoe de onnauwkeurige grenzen van de klassen die teruggegeven 15

worden door de classificator hierin kunnen ge¨ınterpreteerd worden. Niets is echter gezegd over de betrouwbaarheid van deze (onnauwkeurige) informatie. Betrouwbaarheid en nauwkeurigheid zijn immers twee orthogonale vormen van imperfectie in deze context [9]. Bijvoorbeeld, beschouw de uitspraak “Jan is ongeveer 20 tot 25 jaar oud”. Deze uitspraak is duidelijk onnauwkeurig, maar ze is misschien wel volledig betrouwbaarheid indien we zeker zijn dat ze juist is. Omgekeerd: “Jan is precies 24 jaar oud” is nauwkeurig maar kan eventueel onbetrouwbaar zijn. Toch kan tussen beide vormen van imperfectie ge¨ınterageerd worden: als “Jan is 22 jaar oud” niet volledig betrouwbaar is, zal de statement “Jan is ongeveer 20 tot 25 jaar oud” meer betrouwbaar zijn [9]. In het geval van de classificatiedata hebben we te kampen met zowel onnauwkeurigheid als onbetrouwbaarheid. Deze onbetrouwbaarheid wordt gegeven door drie belangrijke factoren: verplaatsing, fragmentatie en ruis. Om deze problemen te overkomen zullen onze informatie nog dichter bij onze werkelijke kennis brengen. Dit zal resulteren in een grotere onnauwkeurigheid, maar beoogt een aanvaardbare betrouwbaarheid. Om meer tolerantie met betrekking tot deze problemen toe te laten, zullen de grenzen wijder uit elkaar getrokken worden. Dit zullen we doen met de BUFFER-operatie. Twee vaaggebieden zullen gebufe (C), de verzameling van wat mogelijks tot de klasse C behoort en ferd worden: U e COM P (L(C)), de verzameling van wat mogelijks niet tot de klasse C behoort. Formeel: α e e 0 (C) = BU F F ERB U (U (C)) e 0 (C)) = BU F F ERα (COM P (L(C))) e COM P (L B

De buffers moeten groot genoeg zijn om een betrouwbaarheid te hebben die aanvaardbaar is. Maar de buffers mogen niet t`e groot zijn, want dit maakt de data onnauwkeuriger. De buffergrootte moet afhankelijk zijn van de performantie van de classificator, want die bepaalt de betrouwbaarheid. De spatiale betrouwbaarheid van de classificator kan gemeten worden aan de hand van de vage epsilon-maat. Formeel: B B

e (C), C)) = E(εp (U e = E(εp (COM P (L(C)), C))

Het samenvoegen van buffers (α > 0) heeft een effect zowel op verplaatsing als fragmentatie en ruis. Hoe meer cellen met een hoge lidmaatschapsgraad geconcentreerd zijn in groep, hoe meer hun lidmaatschapsgraad zal stijgen. Dit betekent dat cellen die werkelijk tot een object behoren zullen stijgen in lidmaatschapsgraad. Cellen die zich eerder in het centrum van een object bevinden zullen een hogere lidmaatschapsgraad krijgen dan cellen op de rand van een object. Dit heeft zin, omdat verplaatsing moeilijk kan plaatsvinden in het centrum van een groot object. Ruis zijn cellen met een relatieve hoge lidmaatschapsgraad die verspreid zijn rond een object. Hun lidmaatschapsgraad zal significant minder stijgen dan de cellen van het object. Ruis dat ver verwijderd is van het object, zal zelf helemaal niet stijgen in lidmaatschapsgraad. Delen van het object die missen zullen echter een veel grotere lidmaatschapsgraad hebben. Dit zorgt ervoor dat gefragmenteerde objecten gedeeltelijk terug verbonden worden.

16

Deze effecten worden getoond voor een lineair object in figuur 3.2. Initieel hebben de cellen een lidmaatschapsgraad van 0.7, de ruis een lidmaatschapsgraad van 0.4. De lijn is gefragmenteerd in twee delen door een ontbrekend stuk. Een bufferoperatie is toegepast met α = 0.90. Buiten het ruis dat het dichtst bij de lijn staat, is het ruis niet in lidmaatschapsgraad gestegen. De twee fragmenten zijn nu gedeeltelijk verbonden. Interessant om op te merken is dat het centrum van het ontbrekende stuk het ruis heeft voorbijgestoken met een lidmaatschapsgraad van 0.53. e Bij het bufferen van COM P (L(C)) zal het omgekeerde effect ook precies zijn wat we willen: er zal eerder ruis verwijderd worden dan “goede” cellen. Het effect op de straat in Sint-Denijs wordt gedemonstreerd in figuur 3.3. We kunnen dus besluiten dat deze techniek de betrouwbaarheid verhoogt.

Figuur 3.2: Een gefragmenteerde lijn gebufferd met α = 0.90

(a)

(b)

Figuur 3.3: Straat in Sint-Denijs gebufferd met α = 0.90. (a) Ondergrens van de straat, het complement is gebufferd (c) Bovengrens van de straat, gebufferd.

3.5

Meten van kwaliteit

We kunnen nu onze kwaliteitsmaten gaan toepassen op tweevoudige vaagverzamelingen. Voor elke van de drie kwaliteitsmaten zullen we een interval terugkrijgen, begrensd door een minimum en een maximum. Voor positionele nauwkeurigheid: min(p (T, C)) max(p (T, C))

e (C)) = p (T, U e = p (T, L(C))

17

Voor omissie: min(OM (T, C)) max(OM (T, C))

e (C)) = OM (T, U e = OM (T, L(C))

De definities zijn analoog voor niet genormaliseerde omissie. Voor comissie: min(COM (T, C)) max(COM (T, C))

e = COM (T, L(C)) e (C)) = COM (T, U

De definities zijn analoog voor niet genormaliseerde comissie. Hoe betrouwbaarder en precies de classificatiedata is, hoe kleiner deze intervallen zullen zijn in het eindresultaat. Op een eenvoudige manier echter kunnen deze intervallen dikwijls leiden tot een betrouwbare conclusie over het feit of de kwaliteit al dan niet aanvaardbaar is. Dit kan door drempels op te stellen. Om de kwaliteit van een gebied met betrekking tot een bepaalde fout te verwerpen moet de het minimum van die fout een zekere drempel overschrijden. Omgekeerd, om de kwaliteit van een gebied met betrekking tot een bepaalde fout te aanvaarden moet het maximum van die fout onder een zekere drempel liggen. Wanneer de beide einden van het interval buiten deze drempels liggen, is het resultaat onzeker. Stel bijvoorbeeld dat, om aanvaardbaar te zijn, de omissie in geen geval groter mag zijn dan 0.20. Dan zal een omissie interval van [0.25, 0.99] leiden tot de conclusie dat de kwaliteit niet aanvaardbaar is. Voor omissie en comissie zal normaal gezien de genormaliseerde maten gebruikt worden omdat die onafhankelijk van de resolutie zijn; de niet genormaliseerde zullen echter soms moeten dienen als test om foute conclusies bij randgevallen te vermijden. Stel dat het testgebied leeg is, en de grondwaarheid uit ´e´en pixel bestaat (eventueel door een kleine fout). Dan zal de genormaliseerd omissie 1 zijn (volledige omissie). Omdat de niet-genormaliseerde omissie duidelijk beneden een aanvaardbare drempel is (slechts ´e´en pixel) kunnen we besluiten dat de kwaliteit toch niet onaanvaardbaar hoeft te zijn.

18

Hoofdstuk 4

Toepassing op testgebied 4.1

Voorbeelden

De methode werd toegepast op een aantal subsets uit het testgebied, aan de hand van de eerste classificatie uit WP3. Voor elk testgebied werd een grondwaarheid uitgetekend aan de hand van de beelddata. Deze beelddata werd dan ook geclassificeerd door de vakgroep Geografie van de VUB in vier klassen: wegbaan, grond, vegetatie en gebouwen. Er werd eerst een vegetatiemasker opgesteld. Vervolgens werd de rest geclassificeerd aan de hand van een neuraal netwerk. De drie kwaliteitsmaten werden enerzijds toegepast op de grondwaarheid, resulterend in n waarde; en anderzijds op de geclassificeerde data via het besproken model, resulterend in een interval. In figuur 4.1 ziet u het eerste testgebied met grondwaarheid. In figuur 4.2 ziet u dan de ondergrens en bovengrens zoals geextraheerd uit de classificatie. De ondergrens diende niet gebufferd te worden aangezien in dit geval B = 0 was. In tabel 4.1 ziet u dan de resultaten. Zoals u kan zien valt de echte waarde binnen het interval. Bovendien dient opgemerkt te worden dat uit de vergelijking met de classificatie alleen duidelijk kan afgeleid worden dat er een comissieprobleem is: die is immers minstens 0.57, wat nooit aanvaardbaar kan zijn.

OM COM ε0.99

min 0.01 0.57 51.25

max 0.42 0.78 62.23

grondwaarheid 0.01 0.6 53

Tabel 4.1: Kwaliteitsmaten Testgebied 1

In figuur 4.3 ziet u het eerste testgebied met grondwaarheid. Het rode gedeelte behoort niet tot de beschouwde ruimte. In figuur 4.4 ziet u dan de ondergrens en bovengrens zoals geextraheerd uit de classificatie. In tabel 4.2 ziet u dan de resultaten. In dit geval zien we dat er een verschuiving is, die hier echter minder duidelijk gedetecteerd wordt (De echte epsilon is 12 maar we hebben maar een

19

(a)

(b)

Figuur 4.1: Testgebied 1 (a) Grondwaarheid (b) Testgebied in databank

(a)

(b)

(c)

Figuur 4.2: Testgebied 1 (a) Ondergrens (b) Bovengrens (c) Bovengrens, gebufferd

20

minimum van 2.71). Dit komt omdat de classificatiedata dus niet betrouwbaar genoeg is om die conclusie te trekken.

(a)

(b)

Figuur 4.3: Testgebied 2 (a) Grondwaarheid (b) Testgebied in databank

OM COM ε0.99

min 0.1 0.04 2.71

max 0.55 0.45 20.71

grondwaarheid 0.1 0.05 12

Tabel 4.2: Kwaliteitsmaten Testgebied 2

4.2

Besluit

Aan de hand van een goede theoretische onderbouw hebben we een goed model opgebouwd om de imperfecte kennis te representeren die afgeleid kan worden uit de beeldclassificaties. Hierop hebben we operatoren gedefinieerd die ons in staat stellen om betrouwbare uitspraken over de kwaliteit van geografische data te doen aan de hand van deze classificaties. Deze kunnen ons in staat stellen om aan verandering- en foutdetetectie te doen. Experimenten op vele gesimuleerde fouten hebben getoond dat bij een gewone classificatie grote fouten wel 21

(a)

(b)

(c)

(d)

Figuur 4.4: Testgebied 2 (a) Ondergrens (b) Ondergrens, gebufferd (c) Bovengrens (d) Bovengrens, gebufferd

22

gedecteerd worden. Het bevestigen van goede kwaliteit is echter moeilijker. Het eindresultaat schommelt tussen slechte en onzekere kwaliteit. Door de onzekerheid die ontstaat door de fouten in de classificaties is het dus niet gegarandeerd dat alles gedetecteerd wordt. Deze experimenten zouden dus best eens herhaald worden met grotere hoeveelheden echte data om de prestatie van de methode in het detecteren van fouten te meten. Vanuit werkpakket drie wordt nog een verbeterde classificatie verwacht. Door hier op te testen zal een vergelijking tussen verschillende maten van betrouwbaarheid kunnen gemaakt worden en het verwachte effect op het resultaat hiervan aangetoond kunnen worden. Zal de nieuwe classificatie bijvoorbeeld de verschuiving in het tweede testgebied eventueel kunnen detecteren? Het werk dat nog moet gedaan worden situeert zich voornamenlijk in het verder experimenteren en practisch toepassen van het theoretisch model en het meten van de prestatie.

23

Bibliografie [1] M. Blakemore. Generalisation and error in spatial databases. Cartographica: the International Journal Journal for Geographic Information and Geovisualization, 21(2-3):131–139, 1984. [2] G. de Cooman. Towards a possibilistic logic., pages 89–133. Boston: Kluwer Academic Publishers, 1995. [3] D. Dubois and H. Prade. Possibility Theory. Plenum Press, New York, USA, 1980. [4] D. Dubois and H. Prade. Twofold fuzzy sets and rough sets - some issues in knowledge representation. Fuzzy Sets and Systems, 23:3–18, 1987. [5] M.F. Goodchild and G.J. Hunter. A simple positional accuracy measure for linear features. International Journal of Geographical Information Science, 11(3):299–306, 1997. [6] Hans W. Guesgen. From the egg-yolk to the scrambled-egg theory. pages 476–480. FLAIRS Conference, 2002. [7] H.W. Guesgen, J. Hertzberg, R. Lobb, and A. Mantler. Buffering fuzzy maps in gis. Spatial Cognition and Computation, 3(2 and 3):207–222, 2003. [8] F. Lehmann and A.G. Cohn. The egg/yolk reliability hierarchy: Semantic data integration using sorts with prototypes. pages 272–279. Conference on Information Knowlegde Management, ACM Press, 1994. [9] Simon Parsons. Current approaches to handling imperfect information in data and knowledge bases. IEEE Transactions on Knowledge and Data Engineering, 8(3):353–372, 1996. [10] J. Perkal. On the length of empirical curves. discussion paper no.10. Ann Arbor: Michigan Inter-University Community of Mathematical Geographers, 1966. [11] H. Prade. Possibility sets, fuzzy sets and their relation to lukasiewicz logic. Number 12, pages 223–227. International Symposium on Multiple-Valued Logic, 1982. [12] J. Verstraete. Fuzzy Modelling of Spatial Information. 2007. [13] L.A. Zadeh. Fuzzy sets. Information and Control, 8(3):338–353, 1965.

24

[14] L.A. Zadeh. Fuzzy sets as a basis for a theory of possibility. Fuzzy Sets and Systems, 1(1):3–28, 1978.

25