35. Fejezet - RASZTERES TÁROLÁS
Szerkesztette: Donna Peuquet, Pennsylvania State University
Magyar változat: Végső Ferenc, Erdészeti és Faipari Egyetem, Székesfehérvár
A. BEVEZETÉS
Miért használjunk rasztert ?
Szempontok
B. A RASZTERTÁROLÁS LEHETŐSÉGEI
Mi legyen több fedvény esetén ?
Mi tárolható pixelekben ?
Raszter/vektor kombinációk
C. HOSSZKÓDOLÁS
Problémák
D. LETAPOGATÁSI SORREND
1. Sor szerint
2. Sor iránya szerint (Boustrophedon)
3. Morton sorrend
4. Peano módszer (illetve Pi-sorrend vagy Hilbert)
A letapogatási módszerek összehasonlítása
E. LETAPOGATÁSOK DEKÓDOLÁSA
Módszer
Általánosítás
IRODALOM
ELLENŐRZŐ KÉRDÉSEK
MEGJEGYZÉSEK
Ennek a fejezetnek a vége és a következő kettő igényli a 2 és 4 alapú számrendszer ismeretét, valamint az átszámítást közöttük és a tízes számrendszer között. Célszerű, ha valamilyen háttéranyagot ad a hallgatóinak ezekről, mielőtt e fejezetekkel megbirkóznának.
35. Fejezet - RASZTERES TÁROLÁS
Szerkesztette: Donna Peuquet, Pennsylvania State University
Magyar változat: Végső Ferenc, Erdészeti és Faipari Egyetem, Székesfehérvár
A. BEVEZETÉS
Miért használunk rasztert?
- a távérzékelés, a fotogrammetria vagy a letapogatás ilyen formában gyűjtik adataikat
- így ábrázolják a leggyakrabban a digitális magassági adatokat
- a raszter nem kíván előzetes ismereteket a jelenségekről, a mintavétel egységesített
- ha a változásokról tudunk, sokkal több mintát vehetünk a gyorsan változó területekről (tagolt domborzat), mint a lassan változó részekről (sima felületű terep)
- az adatcsere gyakori formája a raszter, ezért gyakran konvertálnak adatokat raszter formába
- kapcsolódhatunk távérzékelt képekhez vagy digitális terepmodellhez
- a raszter algoritmusok gyakran egyszerűbbek és gyorsabbak
- pl. az övezet generálás egyszerűbb raszterben
- a raszter alkalmas lehet, ha a megoldás egységes felbontást kíván pl. optimális út számítása vonalas elemek számára, mint az elektromos vezetékek, vagy csatornák helyének levezetése DTM-ből
Szempontok
- sokféle lehetőség van a rasztertárolás megoldására (sokféle adatszerkezet)
- van, amelyik gazdaságosabban tárol, mint a többi
- van, amelyik gyorsabb az adatelérésben és a feldolgozási sebességben, mint a többi
- ez a fejezet a fentiek néhány vonatkozását tárgyalja
- néhány szempontot bevezettünk a 4. Fejezetben, ezeket itt bővebben kifejtjük
B. A RASZTERTÁROLÁS LEHETŐSÉGEI
- szokásosan a raszteradatokat sorról-sorra tárolják a bal felső saroktól kezdve
- ez az európai-észak amerikai olvasási sorrend
- ez a letapogatási sorrendje a TV képnek is
- példa
- a kép
A A A A
A B B B
A A B B
A A A B
- tárolható 16 memória rekeszben, mindegyikben egy adat, sorrendben:
A A A A A B B B A A B B A A A B
Mi legyen több fedvény esetén ?
- két lehetőség
1. a fedvényeket külön tároljuk
- ez az általános eljárás
2. a képpontok minden adatát együtt tároljuk
- az olyan fedvények számára is előre le kell foglalni a tárolóhelyet, amelyek esetleg a feldolgozás közben jönnek létre
- ezt nehéz előre megjósolni (a távérzékelésben ezeket a módszereket "sáv sorrend"-nek és "pontonként átfedő sávoknak" hívják)
Mi tárolható pixelekben?
- néhány rendszer kötött hosszúságú, egész szám tárolását teszi lehetővé pl. -127-től +127-ig (1 byte pixelenként), vagy -32767-től +32767-ig (2 byte pixelenként)
- néhány elfogad egész számokat, tizedes törteket és vegyesen számokat és betűjeleket, minden képpontra
- ebben az esetben hasznos, ha a rendszer számon tartja a tárolt adat típusát és figyelmezteti a felhasználót az illegális műveletekre
- példa:
- a növényzet adatait osztályokba soroltuk A-tól G-ig
- a magassági adatokat tizedestörtként vittük be (pl. 100.3 m)
- a rendszer nem engedheti meg, hogy a két fedvényt pixelenként összeadjuk (A+ 100.3), vagy a növényzet fedvényén számtani műveleteket kezdeményezzünk
Raszter/vektor kombinációk
- sok raszter alapú rendszer elfogad vektor adatokat
Példa:
- a bemenő adat legyen vonalszakaszokkal határolt poligon
- alakítsuk ezt pontokká
- vagyis a poligonba eső pontok értéke legyen 1 és a kívül esőké legyen 0
- sok adat eleve keveréke a raszternek és a vektornak
- a Freeman-féle lánckód véges nagyságú pntokon alapul (raszter-szerű), de vonalakat és objektum határokat definiál (vektor-szerű)
- a rasztert kötött pixelméret mellett objektumok leírására is használhatjuk, ha a képpontoknak valamely érték helyett az objektum számát adjuk
- az objektum száma egy mutató a leíró adatok táblázatához:
raszter obj. szám leíró adatok
23 23 23 24 23 A 100.0
23 23 24 24 24 B 101.1
23 23 24 24
23 23 23 24
- ez megadja nekünk az objektumot a leíró adataival, és egy listát az ojektumhoz kapcsolt képpontokról, de nem adja meg az objektum koordinátáit
- ebben az értelemben a raszter véges felbontású geometria, nem pedig egy lehetőség a struktúrált térbeli adatok ábrázolására
C. HOSSZKÓDOLÁS
- a földrajzi adatok jól közelítik a "térbeli autokorrelációt", ami azt jelenti, hogy a szomszédos objektumok jellemzői közel egyformák
- Tobbler ezt így fejezte ki: "Minden dolog kapcsolatban van a többivel, de a közeli dolgok szorosabban mint a távoliak"
- a fenti elv alapján tapasztalhatjuk, hogy a közeli pontoknak hasonló értékeik vannak
- tehát, felhasználva az ismétlődő értékeket, a rasztert számpárok formájában kódolhatjuk (adathossz, érték)
- pl. az eredeti raszter mátrix 16 elemét így is felírhatjuk:
4A 1A 3B 2A 2B 3A 1B
- ami 7 egész szám/érték tárolását jelenti
- ha az adatsort nem kell megszakítanunk minden sor végén, további helyet takaríthatunk meg:
5A 3B 2A 2B 3A 1B = 6 számpár
- ez segít korlátozni az adathosszat, így kisebb hely kell az adathossz tárolására, tehát az összes fenntartott helynek elégnek kell lenni a legnagyobb adathosszhoz is
Problémák
- a fedvények eltérő hosszúak lesznek, a tömörítés mértékétől függően
- több fedvény együttes tárolásának így nincs értelme
- az adathossz-szerinti tárolás kevéssé alkalmazható a digitális terepmodellnél, vagy olyan típusú adatoknál, ahol a szomszédos pontoknak általában eltérő értéke van
D. LETAPOGATÁSI SORREND
1. Sor szerint
- már fentebb ismertettük
- van jobb mód a raszter elrendezésére, mint sorról-sorra a bal felső sarokból indulva?
- egyéb módszerek nagyobb tömörséget eredményeznek
35.1.a ábra - a szokásos letapogatási sorrend
2. Sor iránya szerint (Boustrophedon)
35.1.b ábra - a szokásos letapogatási sorrend (folytatás)
- képzeljük el, hogy megfordulunk minden második sorban:
- ennek a módszernek a beceneve a Boustrophedon a görögök után, "ahogyan az ökör szántja a mezőt"
- megtakarítva egy hosszú ugrást a sorok végén, a raszter rövidebb hosszat ad és így nagyobb tömörséget
- ezt a sorrendet használja a polgári térképészet : minden városrészben így számozzák a tömböket
- az eredeti raszter eszerint így fest:
4A 3B 3A 3B 3A = 5 adatpár
3. Morton sorrend
35.1.c ábra - a szokásos letapogatási sorrend (folytatás)
- a Morton sorrend az alapja az adatbázis csökkentési erőfeszítéseknek
- Guy Mortonról nevezték el, aki a Kanadai Földrajzi Információs Rendszer adatelrendezése számára találta ki
- egyébként a letapogatásnak, vagy az adatelrendezésnek ez a módja már jól ismert volt jóval Morton előtt is
- kapcsolódik sok jól ismert matematikus nevéhez is: Hilbert, Peano és Koch
- ráadásul Morton a neve Kansas állam bal alsó megyéjének is
- az eljárás szerint kiürítjük a térkép minden területét adott sorrendben, ahol sorról sorra tapogatunk le, egyik oldalról haladva a másikra
- ez minimalizálja a nagyobb ugrások számát
- ez egyike a különböző hierarchikus elrendezésű rendszereknek
- szintről-szintre épül fel, ismételve ugyanazt a mintát minden szinten, az alábbiak szerint
2 3 10 11 14 15 42 43 46 47 58 59 62 63
0 1 8 9 12 13 40 41 44 45 56 57 60 61
2 3 6 7 34 35 38 39 50 51 54 55
0 1 4 5 32 33 36 37 48 49 52 53
10 11 14 15 26 27 30 31
8 9 12 13 24 25 28 29
2 3 6 7 18 19 22 23
0 1 4 5 16 17 20 21
- csak olyan négyzetes tömbökre érvényes, ahol a sorok és oszlopok száma 2 hatványaival egyenlő
- pl. 2x2, 4x4, 8x8, 16x16, 32x32, 64x64, stb.
- hogyan néz ki a mi 4x4-es tömbünkön ?
5A 3B 1A 1B 2A 2B 2A = 7 hossz
- ami olyan hosszú, mint a soronkénti kódolás
4. Peano módszer (illetve Pi-sorrend vagy Hilbert)
- a Peano vagy Pi sorrend olyan mint a sor iránya szerinti letapogatás, mindig a szomszédos képpont irányába mozogva
35.1.d ábra - a szokásos letapogatási sorrend (folytatás)
- Peano nevét ehhez a módszerhez is és a Morton módszerhez is társítják, bár gyakrabban ehhez
- ez szintén hierarchikus, de a minták az eltérő szinteken eltérő irányban jelennek meg
A letapogatási módszerek összehasonlítása
- tanulságos összehasonlítani a különböző letapogatási sorrendekkel elérhető helymegtakarítást (l. Goodchild és Grandfield, 1983)
35.2. ábra - letapogatási sorrend összehasonlítása
- az összehasonlítás alapja: egy 64x64 pixeles kép számadatai
- minden képpont fekete vagy fehér
- változik:
- nagy fekete-fehér foltoktól
- a zavaros részekig, ahol minden képpont egymástól függetlenül fekete vagy fehér
- a táblázatban a H jelzi a zavarosság mértékét a képen:
- nagyobb H érték nagyobb foltokat jelez,
- alacsony H érték a zavarosabb részekhez tartozik
- a táblázat minden sora megadja azoknak az adathosszaknak a számát, amelyek szükségesek ugyanannak a fekete-fehér képnek a kódolásához
- az utolsó sor számai elméleti értékek
- a táblázat azt mutatja, hogy a letapogatási sorrend alig befolyásolja az adattömörítést
- az adathosszak nem nagyon változnak az adott képen a letapogatási sorrend hatására
- mindamellett azok a sorrendek, amelyek a szomszédos pixelek irányába mennek (Boustrophedon és Peano) jobbnak tűnnek, mint a sor szerinti vagy a Morton
E. LETAPOGATÁSOK DEKÓDOLÁSA
- bár a Morton vagy a Peano sorrend hasznos, de bonyolult, két kérdés fölmerül a használatuk közben:
1. Mi az adott pixel sor- és oszlopszáma?
2. Mi a helyzete a letapogatási sorrendben egy adott sor- és oszlopszámnak ?
Módszer
- kezdjük el beszámozni a sorokat és oszlopokat 0-tól:
3 10 11 14 15
2 8 9 12 13
1 2 3 6 7
0 0 1 4 5
0 1 2 3
- a 2 jelű sor, a 3 jelű oszlop a 13 pozíciója a Morton sorrenben
1. Hogyan térünk rá a 2-es sorról és 3-as oszlopról a Morton sorrendre?
a. alakítsuk át a sor és oszlop számokat bináris alakba:
16 8 4 2 1 bináris helyiérték
1 0 2 sor
1 1 3 oszlop
b. fűzzük össze a biteket, váltogatva a sorok és oszlopok bitjeit:
1 1 0 1
sor.oszl.sor.oszl.
c. tekintsük a bitek ezen sorrendjét bináris számoknak:
Eredmény: 8 + 4 + 1 = 13
- tehát megkaptuk a Morton pozíciót, a sor és oszlopszámok bitjeinek összefűzésével
2. Hogyan kaphatjuk meg a sor és oszlop számot a 9-es Morton pozíción?
a. alakítsuk át a pozíciószámot bináris számmá
16 8 4 2 1 bináris helyiérték
1 0 0 1 (mert 9 = 8 + 1)
sor oszl. sor oszl.
b. válasszuk szét a biteket
1 0 sor = 2
0 1 oszl.=1
Általánosítás
- a sor és oszlop számot bármely alapon felbonthatjuk, nem csak binárisan, sőt keverhetjük az alapokat
- például: a 6. sor, 15. oszlop 4-es alapon
64 16 4 1 helyiérték
1 2 6 sor = 1x4 + 2x1
3 3 5 oszl. = 3x4 + 3x1
összefűzés:
1 3 2 3 1x64 + 3x16 + 2x4 + 3x1 = 123
megoldás: a 6. sor és 15. oszlop a 123-as pozíció
- hogyan néz ki ez a sorrend ?
35.3. ábra - 4x4 alapú letapogatási sorrend
- a 4 sorból és 4 oszlopból álló tömböket soronként és oszloponként letapogatjuk, majd ez ismétlődik magasabb szinteken
- a letapogatási sémák széles skáláját állíthatjuk elő a különböző alapú számok összefűzésével
- a számok összefűzésének elve nagyon elterjedt, és beépítették a PLSS és a GEOLOC rácsrendszerbe, mint számos más rendszerbe a térképek szelvényszámozására és a földrajzi hivatkozás céljára
IRODALOM
Abel, D. J., 1986. "Bit interleaved keys as the basis for spatial access in a front-end spatial database
management system," Proceedings, Tesseral Workshop #2, Reading, England
Franklin, W., 1979. "Evaluation of algorithms to display vector plots on raster devices", Computer Graphics
and Image Processing 11:377-397
Goodchild, M. F., and A. W. Grandfield, 1983. "Optimizing raster storage: an examination of four
alternatives",Poceedings, AutoCarto 6, Ottawa 1:400-7
Peuquet, D., 1981. "An examination of techniques for reformatting digital cartographic data, Part II,
The vector-to-raster Process," Cartographica 18(3):21-33
ELLENŐRZŐ KÉRDÉSEK
1. Milyen rendszereket használnak a topográfiai térképek szelvényszámozására az USA-ban és más országokban? Beszéljük meg a számok összefűzésének használatát ebben az összefüggésben, hivatkozva a különböző nemzeti példákra.
2. A metaadat fogalmát a térképfedvény jellemzőinek tárolására használjuk, mint a pontosság, a sorok és oszlopok száma, a képpontokhoz tárolt adatok típusa, stb. Beszéljünk a metaadat fontosságáról abból a szempontból, hogy hogyan korlátozza a felhasználó által végrehajtható műveleteket.
3. A raszter és a vektor a GIS két, részben független területeként lett kifejlesztve. Összegezze a raszter-vektor ellentét vonatkozásait, tekintettel a térbeli objektumok fontosságára mindkét rendszerben.
4. Mindegyik eddig tárgyalt letapogatási sorrend egy pixelt egyszer vesz sorra. Beszéljünk a lehetséges előnyökről - ha vannak - azoknál a sorrendeknél, amelyek többször olvasnak le egy pixelt. Mondjunk példákat.
5. Minden raszteres GIS tartalmaz megkötéseket a tárolható adatokra és a műveletekre vonatkozóan. Beszéljünk erről a pontról, ahogyan az IDRISI használja és az egyéb elérhető GIS-ekről. Lehetővé teszik-e ezek betűk (mint az A) tárolását, lehetővé tesznek-e számtani műveleteket egy ilyen fedvényen?
6. Vizsgálja meg, milyen tárolási műveleteket (sorról-sorra, adathossz szerint, pixelenként, fedvényenként stb.) használ az IDRISI és más raszteres GIS-ek (GRASS, MAP, stb.), amelyeket el tud érni.
|