|
31. Fejezet - A VONALAK HATÉKONY TÁROLÁSA - LÁNCKÓDOK
Szerkesztette: David H. Douglas, University of Ottawa
Magyar változat: Gross Miklós, Budapesti Geodéziai és Térképészeti Vállalat
A. BEVEZETÉS
Fogalmak
B. SZABÁLYTALAN VONALAK ÁBRÁZOLÁSÁNAK TECHNIKÁJA
1. Egyenes vonal szegmensek
2. Körívek
3. Spline-ok
C. LÁNCOK (CHAIN) TÁROLÁSA (ARC-OK)
Előnyök és hátrányok
Freeman-féle lánc kód
Tömörítő kód
Ismétlő sorok
Összefoglalás
D. A LÁNC KÓD ALKALMAZÁSA
Raszter adatok vektorizálása
Scanner output vektorizálása
IRODALOM
ELLENŐRZŐ KÉRDÉSEK
31. Fejezet - A VONALAK HATÉKONY TÁROLÁSA - LÁNCKÓDOK
Szerkesztette: David H. Douglas, University of Ottawa
Magyar változat: Gross Miklós, Budapesti Geodéziai és Térképészeti Vállalat
A. BEVEZETÉS
- az előbbi szakaszban átnéztük azokat a struktúrákat, amelyek a térbeli kapcsolatok bizonyos típusait kódolják
- ebben a szakaszban a vonalak és területek geometriájának a kódolását tekintjük át
31.1. ábra - példák geográfiai vonalakra
- megjegyzendő, hogy ezen vonalak mindegyikének karakterisztikája más és más
- ezen vonalak mindegyike különböző földrajzi alakzatot jelent - tudja-e ön azonosítani azokat?
- legtöbb rendszer a vonalakat és területeket úgy tárolja, mint a pontok sorozatát, amelyeket egyenes vonalak kapcsolnak össze
- egyszerű, de legjobb vonalábrázolás az irányok éles törésével és nem sima görbékkel történik
- pl. egy kanyargó folyót vagy egy vasutat sokkal hatékonyabb kevés simuló görbével ábrázolni, mint nagy számu egyenes vonallal
- ez nagyon leegyszerűsíti a digitalizálást
- igen sok módszer van egy vonal diszkrét ábrázolására
- ez a szakasz áttekint ezek közül néhányat és azokat az alkalmazási területeket, ahol hasznosak
Fogalmak
- mivel a terület objektumokat többnyire egyenes vonalszegmensek sorával ábrázoljuk, ezért azt gyakran poligonként kezeljük
- a fogalmak egész sora használatos egy szabálytalan vonal kódolásának, mint egy egyenes vonal szegmensei sorozatának leírására, különösen akkor, amikor a vonal két terület objektum közös határvonala
- ezek a fogalmak magukban foglalják az ív (arc), szegmens, él (edge) és lánc (chain) fogalmait
- ezek közül a lánc (chain) az amerikai digitális térképkészítés szabvány terminógiája, ott ahol a vonal közös határvonal, de talán sokkal gyakrabban használják az arc-ot
B. SZABÁLYTALAN VONALAK ÁBRÁZOLÁSÁNAK TECHNIKÁJA
1. Egyenes vonal szegmensek
- ha a vonal a természetben görbe vonal, pl. folyópart, akkor az egyenes vonal szegmensek a valóságot csak megközelíteni tudják
- a megközelítés pontossága függ az alkalmazott egyenes szegmens hosszától, de a szegmenseknek végtelenül rövideknek kell lenniük, hogy a valódi görbületet ábrázolják
- ekképpen az egyenes vonal szegmensek a folytonos vonal ábrázolásának egyik útja, felhasználva egy véges mennyiségű információt, leginkább a szegmens végpontok koordinátáit
2. Körívek
- néhány rendszert a felmérési adatokra alapoztak, megengedve mind az egyenes vonalakat, mind a köríveket a pontok között
- görbéknél, a rendszernek tárolnia kell a görbület sugarát, valamint kezdő és végpontját
- és azt is pontosan kell azonosítani, hogy mely szegmensek egyenes vonalak és melyek ívek
- ezt a megközelítést használják a Prime System 9 GIS-nél
- ez a műszaki létesítményeknél hasznos, mint pl. az autóutak és vasutak esetében, amelyeket egyenes és görbe vonalakkal terveztek
3. Spline-ok
- használhatók a simuló görbék leírásához, mint pl. a kanyargó folyók esetében
- a görbét "spline" funkció modellezi, ez egy matematiaki funkció, ami a meghatározott pontokon megy keresztül, de minimális görbülete van
- a spline-okat gyakran használják a görbe vonalak "simítására" plotteren történő kirajzoláskor, mint a szintvonal operációk egy részét
- sokkal általánosabban használt a CAD-ban, mint a GIS-ben
C. LÁNCOK (CHAIN) TÁROLÁSA (ARC-OK)
- gyakran jelentős redundancia alakul ki, amikor egy vonalat úgy tárolunk, mint koordináta párok sorozatát
- pl. egy görbe utca négy ponttal van ábrázolva Columbiában, MO a következő koordinátákkal
(38.9519 92.3503)
(38.9519 92.3510)
(38.9522 92.3511)
(38.9522 92.3527)
- vegyük figyelembe, hogy a koordináták az első 4 számjegye (szélesség, hosszúság) minden pontnál ugyanaz
- nagyon gazdaságosan lehet tárolni, ha az előző ponttól való koordináta eltéréseket (növekményeket) tárolják 0.0001 egységgel
(38.9519, 92.3503) (+00,+07) (+03,+01) (+00,+16)
- ez az eljárás minden következő pontnál, lehetővé teszi, hogy négy decimális számjegyet használjunk 12 helyett, vagy megközelítően 12 bit-et, 36 helyett
- egy bit szükséges mindegyik szélesség és hosszúság változás előjelének tárolásához (+,-)
- ezzel összesen 14 bit
- ez határt szab a maximális változásnak 0.0099 egységig a szélesség vagy hosszúság bármelyik pontpárja között
Előnyök és hátrányok
- az előny a tárolási volumen csökkenésében,
- a hátrány a generalitás elvesztésében van
- adott egy fix térbeli felbontás (0.0001 egység) és a pontok közötti maximális távolság (0.0099 egység szélességben vagy hosszúságban)
- ez akkor okoz problámát, amikor földrajzi koordinátarendszert használunk és koordináta átalakítást végzünk
- ez a technika és változatai különösen jól alkalmazhatók scanner és digitalizált adatok előállítására
- ezeknek az eszközöknek fix felbontásuk, van
- a scannereknek van egy felbontásuk, ami az adott scanner pixel (képelem) nagyságával egyenlő és a pontok között minden távolság a köztük levő pixelek számával fejezhető ki
- a digitalizálók szintén diszkrét egységekkel dolgoznak
Freeman-féle lánc kód
- vannak rendszerek, amelyekben koordináta párok adatlánca helyett, erősen bízva a scanner inputban, gyakran úgy kódolnak vonalakat, mint a mozgások növekményeinek listáját
- fix számú mozgásirányt határoznak meg, szokásosan ez 8, kijelölik ezekhez az egész számokat 0-tól 7-ig
- a négy mozgás sorozatát lehet úgy kódolni, mint négy 0-t
- a "01012" string használható a következő görbe kódolásához
- a vonal mentén minden lépést egy számjegy fejez ki 0 és 7 között, vagy három (bináris) számjegy 000 és 111 között
- a vonalak vagy láncok kódjánál ezt a folyamatos kódolási technikát általánosan Herbert Freeman alkalmazta
- habár ezt sokkal korábban a 19. sz-ban már Francis Galton úgy írta le, mint egy információ átvitelt, ami egy billentyűnyomást jelent a távírón
- lásd Freeman (1961) számos algoritmus leírását, amelyek a lánc kódon alapulnak
Tömörítő kód
- bizonyos kódpárok sokkal valószínűbb, hogy lánc kódként bukkannak fel, mint más formában
- vonalak általában "simán" fordulnak és az éles kanyarok sok földrajzi adatban szokatlanok
- nagyon valószínű, hogy a következő elmozdulás ugyanolyan, mint a megelőző volt
- a következő nagyon valószínű, hogy jobbra vagy balra 45 fok
- a legkisebb valószínűséggel 180 fok a következő elmozdulás
- eképpen, ha egy kód 4, nagyon valószínű, hogy egy másik 4 követi, vagy 3, vagy 5 és a legkisebb valószínűséggel 0, 1 vagy 7
- ezt ki lehet fejezni egy kóddal, aminek a hossza a fordulat szögének élességétől függ
1 előre
01 45°
jobbra
001 45°
balra
0001 90°
jobbra
00001 90°
balra
000001 135°
jobbra
0000001 135°
balra
- ilyen módon egy vonal ábrázolásához szükséges bináris számjegyek teljes számát tudjuk redukálni
31.2. ábra - tömörítő kód
Ismétlő sorok
- ha a vonalakat hosszú egyenes szakaszokkal kódolták, lánc kód sorok fognak ismétlődni
31.3. ábra - ismétlő sorok
- például egyik ponttól egy másikig haladva 6 mozdulatot kell megtenni kelet felé és hármat északkelet felé (3 1-es és 6 2-es)
- a 222222111 sorozat egy egyenes vonal veszedelmes torzulása lenne
- az egyenes vonalat a 221221221 sorozattal lehet legjobban megközelíteni
- ismételje meg a 221 mintát háromszor
- az egyenest a legjobban megközelíteni mindig a kódok homogén keverékével lehet
- a vonalak kódolása hosszu egyenes szakaszokkal az ábrázolás egy utja lehet, amihez a minták futtatása szükséges
- pl. 3(221) jelezheti a 221 sorozatnak négy ismétlését
Összefoglalás
31.1. melléklet - Hasonlítsa össze a különböző kódolási sémákat
D. A LÁNC KÓD ALKALMAZÁSA
- a lánc kódok két különleges alkalmazása lehet hasznos
Raszter adatok vektorizálása
- raszter adat outputja az A és B zónát végig elkülönítő határ a következőképpen jelenik meg
AAAB
AABB
ABBB
BBBB
- egy vonalat tételezzünk fel a pixel élek mentén, ami elválasztja az A-t a B-től
- a vonal ábrázolását vektor- (a 202020 lánc-) kóddal lehet kódolni
Scanner output vektorizálása
- amikor egy vonalat scanner olvas le, ez valami olyasmi, mint:
000111
001110
011100
111000
- 1-ek jelölik, hogy hol "látta" a vonalat a scanner és a 0-ák jelölik, hogy a vonal körül hol volt üres terület
- az első lépés egy vonal vektor ábrázolásának levezetésében pixelek levékonyítása, egy szabvány algoritmussal
- sokféle algoritmus alkalmas erre
- jó forrás ehhez Pavlidis (1982) cikke
- a "levékonyítás" eredménye lesz:
000010
000100
001000
010000
- a vonal ekkor a megmaradó 1-ek vázából származhat
- a lánc kóddal ábrázolva 111 (3 elmozdulás északkeletnek)
- általában a vonal a lánc kóddal követett (x,y) koordinátával tárolt
- lánc-kód alkalmazása leghasznosabb ott, ahol raszter formátumból ered a vektor adat, egy scannerből vagy képből
- miután mind a távolság, mind az irány szét van választva (mindkettőnek van a lehetséges értékekből egy lehatárolt sorozata), így az általánosabb alkalmazásra nem különösen jó
IRODALOM
Freeman, H.,1961. "On the encoding of arbitrary geometric configurations", Institute of Radio Engineers,
Transactions on Electronic Computers, EC 10:260-8
Pavlidis, T. 1982. "Algorithms for Graphics and Image Processing", Springer-Verlag, Berlin
ELLENŐRZŐ KÉRDÉSEK
1. Rajzoljunk egy vonalat, írja ki:
a. A vonal ábrázolásának a Freeman lánc-kódját egyszerű számokkal 0-tól 7-ig
b. Bináris kóddal történő ábrázolását, törés szögek alapján
c. Ábrázolását a lánc-kód futtatás használatával
Melyik adat nyújt nagyobb adattömörítést? Fejezze ki mindegyik kód hasznát bit-ekben és emlékezzen, hogy 0 és 7 közötti szám 3 bit-et igényel. Egy példa rajzot is szükséges csatolni.
2. A válasz az előző kérdésre függ a kódolt vonal típusától. Beszéljük meg a karaktereket, amelyek a legnagyobb adattömörítést adják mindhárom feltételnek és írjon le vonal példákat ezekkel a karakterekkel.
3. A pontosság, amellyel egy vonalat ábrázolni lehet, mint egyenes vonal szegmensek sorozata, függ az eljárástól, amit a digitalizálásnál a pontok kiválasztásához használtunk. Beszéljük meg a feltételt, amelyet a pontok kiválasztásánál írunk elő abból a célból, hogy a vonalnak pontos ábrázolását kapjuk meg. Hogyan változhatnának ezek a feltételek a vonal természetétől függően?
4. Egy egyszerű osztályozó rasztert alkalmazva írjon ki egy vektorizált ábrázolást arc-t és Freeman féle lánc-kódot használva. Beleértve a jobb és bal poligonokat és mutatókat a szomszédos ívekhez, mint mindegyik arc attribútumát és az osztályát, mint mindegyik poligon attribútumát. Mutassa meg mindegyik vonalat a kezdőpont koordinátáival, kötve a lánc-kóddal, a számjegyeket 0-tól 7-ig felhasználva.
5. A 32. Fejezet előkészítéséhez találja ki, hogyan állítana fel egy programot annak meghatározására, hogy hol fogja két vonal keresztezni egymást, ha végpontjaikkal vannak megadva. Induljon egy ábrával! Milyen feltételek mellett fog a programja hibázni?
|
