Rappresentazion
e raster
Vittorio Maniezzo - Algoritmi e Sistemi di Elaborazione - A.S.E.
1/16
Rappresentazione Raster
mais
frutta
trifoglio
L’area è coperta con una griglia di
celle (usualmente) di uguali
dimensioni
La posizione di una cella è calcolata
dall’origine della griglia (di solito in
alto a sx, i basso a dx in ARCVIEW)
Le celle spesso sono dette pixels; i
dati raster sono spesso immagini
Gli attributi sono memorizzati
assegnando ad ogni cella un valore
calcolato come media (maggioritario)
dei valori assunti nell’area della cella.
Facile fare sovrapposizioni, basta
combinare (es. sommare) questi
valori.
E’ Vittorio
unaManiezzo
struttura
semplice e non c’è
- Algoritmi e Sistemi di Elaborazione - A.S.E.
bisogno di un DBMS di supporto
frumento
frutta
1
1
1
1
2
2
2
2
2
1
1
1
1
2
2
2
2
2
1
1
1
1
2
2
2
4
4
1
1
1
1
2
2
2
4
4
1
1
1
1
2
2
2
2
2
4
4
4
4
2
2
2
2
2
4
4
4
4
2
2
2
2
2
5
5
5
5
3
3
3
3
3
5
5
5
5
3
3
3
3
3
5
5
5
5
3
3
3
3
3
2/16
Sovrapposizione (overlay)
Tutti i layer devono avere la stessa scala
Collegamenti che assicurano un
riferimento spaziale comune
Layer risultante per
l’analisi
Vittorio Maniezzo - Algoritmi e Sistemi di Elaborazione - A.S.E.
3/16
Overlay (2)
• Una qualsiasi operazione matematica può essere applicata a
layer corrispondenti.
• Viene prodotto un nuovo layer.
Risultato
Layer di input da
sovrapporre per l’analisi
Territorio, campionato a
intervalli regolari
Vittorio Maniezzo - Algoritmi e Sistemi di Elaborazione - A.S.E.
4/16
Overtlay (3)
E’ possibile un’analisi tramite soglie di valori e
combinazione booleana dei risultati
AND
OR
Fase Geometrica:
rappresentazione comune su
griglia che assicura che ogni
pixel si sovrapponga nella
stessa posizione.
Vittorio Maniezzo - Algoritmi e Sistemi di Elaborazione - A.S.E.
Fase attribuzionale
Sogliazione
L’operazione
(regola di
combinazione)
produce il
risultato
5/16
Overlay (4)
Analisi combinatoria: produce una nuova categoria per
ogni combinazione di valori presente nella
sovrapposizione.
Combina
Fase Geometrica:
rappresentazione comune su
griglia che assicura che ogni
pixel si sovrapponga nella
stessa posizione.
1
1
1
6
8
1
1
3
7
8
1
3
4
4
8
2
2
5
5
8
1
2
3
4
5
6
7
8
Chiavi delle categorie
Fase attribuzionale: si crea una
nuova categoria per ogni combinazione
di valori.
Vittorio Maniezzo - Algoritmi e Sistemi di Elaborazione - A.S.E.
6/16
Compressione
• Per ridurre la quantità di dati nella
rappresentazione di un layer raster si usano
tecniche di compressione
• Se le celle non variano continuamente, si
utilizzano Run-length encoding o GIF e quadtrees.
• Per immagini con variazione continua si utilizzano
metodi più complessi, come ad esempio JPEG.
Vittorio Maniezzo - Algoritmi e Sistemi di Elaborazione - A.S.E.
7/16
Huffmann
Il formato GIF è basato su codifica compressa
secondo Huffmann.
Esempio:
Carattere Prob.
A
0.4
0.55
0.35
0.25
B
0.2
C
0.15
0
1
0
1
0
0.15
D
0.1
E
0.1 0
F
0.05
1
0
1
A
B
C
D
E
F
1
000
001
011
0100
0101
1
Vittorio Maniezzo - Algoritmi e Sistemi di Elaborazione - A.S.E.
8/16
Run-length encoding (RLE)
RLE
monodimensionale:
3
3
3
3
3
7
7
3
3
3
3
3
3
7
7
7
3
3
3
3
3
3
7
7
3
3
3
3
3
3
7
7
3
3
7
7
3
3
3
3
3
3
7
7
3
3
3
3
3
7
7
7
3
3
3
3
3
7
7
3
3
3
3
3
1
2
3
4
5
6
7
8
1
2
2
3
1
2
2
3
8
6
4
4
8
2
4
1
Vittorio Maniezzo - Algoritmi e Sistemi di Elaborazione - A.S.E.
3
3
3
3
3
7
7
3
2 7
4 7
3 7
1 3
6 3
4 3
3 7
4 3
Riga 1: 1 run di 8 3
Riga 2: 2 run: 6 3 e 2 7
Riga 3: 2 run: 4 3 e 4 7
Riga 4: 3 run: 4 3, 3 7 e un 3
Riga 5: 1 run di 8 3
Riga 6: 2 run: 2 7 e 6 3
Riga 7: 2 run: 4 7 e 4 3
Riga 8: 3 run: 1 3, 3 7 e 4 3
9/16
Quadtree
a) Un oggetto
b) Il raster corrispondente
c) La decomposizione gerarchica del
layer
d) L’albero corrispondente (prossimo
lucido)
0 0 0 0 0 0 0 0
0
0
0
0
0
0
0
a)
0
0
0
0
0
0
0
0
0
0
0
1
1
1
0
0
0
1
1
1
1
b)
Vittorio Maniezzo - Algoritmi e Sistemi di Elaborazione - A.S.E.
0
1
1
1
1
1
1
0
1
1
1
1
1
0
0
1
1
1
1
0
0
0
1
1
1
1
0
0
2
3
4
5
13
14
1
6
11
7
8
9 10
12
15 16
17 18
19
c)
10/16
Quadtree (2)
NW
SE
SW
NE
1
2
3
4
5
6
7
Vittorio Maniezzo - Algoritmi e Sistemi di Elaborazione - A.S.E.
11
8
9 10
12
13
14
19
15 16 17 18
11/16
Quadtree, esempio 2
0
0
0
0
1
1
1
1
0
0
0
0
1
1
1
1
0
0
0
0
1
1
1
1
0
0
0
0
1
1
1
1
0
0
0
0
1
1
1
1
0
0
0
0
1
1
1
1
0
0
0
0
1
1
2
2
0
0
0
0
1
1
2
2
0
0
0
0
1
1
2
2
0
0
0
0
1
1
2
2
0
0
0
0
1
1
2
2
0
0
0
0
1
1
2
2
0
0
1
1
3
3
3
3
0
0
1
1
3
3
3
3
0
0
1
1
3
3
3
3
0
0
1
1
3
3
2
2
0
0
1
1
3
3
2
2
0
0
1
1
3
3
2
2
1
1
1
1
1
1
2
2
1
1
1
1
1
1
2
2
1
1
1
1
1
1
2
2
1
1
1
1
1
1
2
2
1
1
1
1
1
1
2
2
1
1
1
1
1
1
2
2
1. Matrice dei pixel
2.Decomposizione del nodo
radice
Vittorio Maniezzo - Algoritmi e Sistemi di Elaborazione - A.S.E.
3.Individuazione di tutti i
quadranti
12/16
Quadtree, esempio 2
0
1
1
1
2
0
1
1
1
3
3
Vittorio Maniezzo - Algoritmi e Sistemi di Elaborazione - A.S.E.
1
3
2
2
2
13/16
Raster: vantaggi
• La posizione geografica di ogni cella é implicita nella
sua posizione nella griglia. Quindi, a parte per l’origine
(es. L’angolo in basso a destra) non vengono
memorizzate coordinate geografiche.
• Date le strutture di memoria usate (matrici), l’analisi dei
dati é di solito facile da programmare e veloce a run
time.
• La natura stessa delle mappe raster é ben adatta a
modellizzazione matematiche e analisi quantitative che
non coinvolgano analisi di reti (grafi).
• Sia dati discreti, es. particolari colture, sia dati continui,
es. elevazione, possono essere gestiti efficacemente e
la loro integrazione é molto semplice.
• La rappresentazione a griglia é molto ben compatibile
con
periferiche di output di tipo raster, quali terminali
14/16
Vittorio Maniezzo - Algoritmi e Sistemi di Elaborazione - A.S.E.
grafici o plotter elettrostatici.
Raster: svantaggi
• La dimensione della cella determina la
risoluzione con cui si possono rappresentare i
dati.
• È particolarmente difficile rappresentare
adeguatamente elementi lineari, a seconda della
risoluzione delle cella. È quindi difficile definire
dei collegamenti in rete (distributiva, di
comunicazione, … ).
• L’elaborazione degli attributi associati può
essere complessa se bisogna gestire grosse
quantità di dati. Le mappe raster sono in gradi
di rappresentare solo un attributo o
15/16
caratteristica di un’area.
Vittorio Maniezzo - Algoritmi e Sistemi di Elaborazione - A.S.E.
Raster: svantaggi
• Dato che la maggior parte dei dati in input
é in formato vettoriale, é necessaria una
pre-elaborazione di conversione. Questo
può anche introdurre problemi di integrità
dei dati derivanti dalla generalizzazione e
dalla scelta di una inadeguata dimensione
delle celle.
• La maggior parte delle mappe in output da
sistemi raster non soddisfano le esigenze
di una cartografia di alta qualità.
Vittorio Maniezzo - Algoritmi e Sistemi di Elaborazione - A.S.E.
16/16