Alapműveletek terbeli adatokkal Szilágyi Péter
Kivonat A dolgozat a térinformatikában előforduló alapműveletekről szól. Eleinte röviden említést teszünk a két elterjedt képtárolási adatstruktúráról: raszter és vektor, majd hosszasan tárgyaljuk egyik formátumnak a másikba való átalakítását különös hangsúlyt fektetve a szükséges előfeltételekre valamint az algoritmikai részletekre. Végezetül pedig az alap affin transzformációkról lesz szó (transzláció, rotáció és skálázás) illetve más térinformatikában hasznos matematikai fogalmakról (különböző távolságok).
Kolozsvár 2010. Április 28.
Raszter képek, vektorképek, konverziók Ebben a fejezetben a teljesség érdekében röviden megemlítjük a raszter- és vektorképek/grafika tulajdonságait, felépítését, majd rátérünk a két fajta formátum közötti átalakításokra, konverziókra.
Raszter grafika A raszter kép, vagy más néven bittérkép (bitmap), az egy általában téglalap alakú négyzetrácsot ábrázoló adatstruktúra, melynek minden rácspotja egy sz ínpont (pixel). Az adatstruktúrának a fő célja a megjelenítés (képernyőn, papíron vagy más médiumon). A bittérkép egy-az-egyhez megfeleltetés egy megjelenített kép bitjeivel, általában a megjelenítő videómemóriájának megfelelő formátumban, vagy egy eszköz független formátumban. Technikailag három tulajdonsággal jellemezhető: szélesség és magasság (színpontok száma) valamint a színmélység (egy színpontot ábrázoló bitek száma). Mivel a raszter grafika felbontás függő, csak korlátozott mértékben lehet nagyítani szembetűnő minőség-vesztés nélkül.
Vektor grafika A vektor grafika az matematikai egyenletekre alapuló geometriai primitívek (pontok, vonalak, görbék és formák/poligonok) felhasználása képeknek az ábrázolása érdekében. Ebből adódóan egy vektorképekkel dolgozó program a megjelenítésnek megfelelő lehető legalkalmasabb felbontású képet elő tudja állítani. Mivel a vektorkép matematikai egyenletekre alapozódik, a megjelenítés minőségét kizárólag a megjelenítő eszköz felbontása korlátozza, ugyanakkor viszont a vektoradatnak a mérete konstans marad. Vagyis bár a nyomtatáshoz egy sokkal több információval rendelkező kép szükséges mint képernyőn való megjelenítéshez, ugyanaz a vektorkép mindkét célt tökéletesen tudja szolgálni.
Raszter skálázás
Vektor skálázás
Raszter és vektor közötti konverziók Sokáig elegendő volt a raszter képekkel való dolgozás és csak nagyon speciális esetekben volt szükség a vektorképek használatára. Manapság viszont egyre gyakrabban van szükség mindkét formátumnak az egyidejű kezelése annak függvényében, hogy a kívánt művelet végrehajtása épp melyik rendszerben egyszerűbb (pl. forgatások és területszámítások vektorképekkel, metszési műveletek raszter képekkel valósíthatóak meg hatékonyabban). Azokat a programokat, amelyek egy időben mindkét adatformátummal dolgoznak hibrid adatmodellű szoftvereknek hívunk. Ezek a szoftverek viszont elképzelhetetlenek helyes, egyértelmű raszter-vektor átalakítások nélkül. Az alábbiakban ezekre a konverziókra térünk ki részletesebben. Raszter → vektor átalakítás Az egyszerűség kedvéért a színes és tónusos raszter képek helyett ebben a részben kizárólag a bináris raszter képek vektorokká való alakításáról lesz szó. A korrekt mintavételezés feltételei Egyik alapfeltétele a számítógépes grafikának valamint a számítógépes alakfelismerésnek az analóg képek (nyomtatott kép) helyes diszkretizálása (pixelekre bontása). Ahhoz, hogy az analóg képet a diszkrét (pixeles) kép kielégítően ábrázolja szükséges, hogy a két kép topológiailag egyenértékű legyen. Ez egyszerűen fogalmazva azt jelenti, hogy a két alakzat nyújtással és zsugorítással, szakadás és vágás nélkül átvihető egymásba. A mellékelt ábrán látható egy példa bemeneti analóg kép illetve az abból előállított diszkrét kép. Bár a két kép topológiailag ekvivalens, mégis egyszerű szemlélet alapján megállapíthatjuk, hogy a diszkretizált kép hasonlósága az eredeti képhez a legtöbb gyakorlati feladat szempontjából nem kielégítő. Ahhoz, hogy a topológia mellett az eredeti kép alakját is megőrizzük, jelentős mértékben kisebb képpontokkal kell dolgoznunk a raszteres kép esetén (vagy más szóval a növelnünk kell a diszkterizálás felbontását). Összefoglalva megállapítható, hogy a kompatibilitás megléte biztosítja az analóg kép topológiájának megőrzését a diszkrét képben, és egyben biztosítja az alak megtartását is. Idomok határvonalának megkeresése Raszterből vektorba való konverzió során két fontos adattípust különböztetünk meg: vastag régiókat és vékony vonalakat. Bármelyik adattípust is kívánjuk azonban feldolgozni, mindenekelőtt meg kell határoznunk az objektum körvonalát (kontúrját). Egy összetett objektum több belső szigetet is tartalmazhat, viszont mielőtt rátérnénk e szigetek kontúrjainak meghatározására, foglalkozzunk az objektum egészét határoló körvonal megkeresésével.
A határoló körvonalat kereső algoritmus lényege az, hogy kezdetnek keresünk egy fekete pixelt melynek egyik (például keleti) szomszédja fehér, majd ebből a pontból kiindulva próbáljuk a körvonalat jobb fordulási irányba kiterjeszteni (a fordulást a fekete pixel melletti lyuktól (fehér pixeltől) kezdjük). A kiterjesztést folytatjuk mindegyik új képpontra mindaddig, amíg visszaérünk az indulási pontba. Megfigyelhető, hogy lesznek olyan képpontok melyeken többször is áthaladunk a kiterjesztés során (pl. két szigetet egy vonal köt össze). Ezek a többszörös pixelek fontos szerepet fognak játszani a vékony vonalak meghatározásában. Az algoritmus lépéseit az alábbi ábrán szemléltetjük.
Vékony objektumok tengelyvonalainak meghatározása A raszteres ábrázolás során erősen torzulnak az euklideszi geometria olyan hagyományos fogalmai, mint a távolság, egyenes, metszéspont, hisz két tetszőleges pixel közötti út nem azonos az analóg síkon két pixelnek megfelelő pontok között húzható legrövidebb távolsággal. Ezek a problémák világossá teszik, hogy ilyen jellegű feladatokat célszerűbb az analóg teret geometriailag leképező vektor modellben végrehajtani. A vektor modellt viszont csak akkor tudjuk létrehozni, ha meghatározzuk, hogy mikor tekinthetünk egy pixel formációt vonalszerűnek. Az egyik meghatározás szerint raszteres vonalábrázolásnak olyan pixel halmaz tekinthető, melynek valamennyi pixele egyben a halmaz körvonalának is része. A raszter képek létrehozásakor az analóg képen vonalként jelentkező objektumok azonban nem feltétlenül felelnek meg a fenti meghatározásnak, azaz a pixeles képen az eredeti vonalak teli objektumként is jelentkezhetnek az eredeti vonal vastagság illetve a pixelméret függvényében. Többszörös pixel: 1. A körvonalkereső algoritmus többször is kiválasztja 2. Nincs szomszédja a tartomány belsejében 3. Van legalább egy direkt szomszédja, mely része a határvonalnak, de a határvonalat leíró útban nincs közvetlenül a kérdéses pixel előtt vagy után
2
1
3
3
3
3
1
2
A vékonyítási algoritmusok alapgondolata az, hogy a síkbeli objektumokat vázukkal (más szóval középtengelyükkel) helyettesítjük, és hogy ez a váz a pixeltérben lehetőleg egy pixel vastag legyen. Az alap algoritmus szavakban a következőképpen fogalmazható meg. Minden lépésben meghatározzuk az objektum összes pontjának halmazát, határvonalát valamint többszörös pixeleit (a fenti definíció szerint), majd az objektum pontjainak halmazából eltávolítjuk azokat a határpontokat, amelyek nem többszörös pontok. Ezt ismételjük mindaddig, amíg az objektum összes határpontja egyben többszörös pixel is lesz.
A bináris váz vektorizálása Ahhoz, hogy a vektorizálás megtörténjen, még két lépés hátra van. Az első lépésben létre kell hoznunk a vékony bináris kép topológiáját. Majd ezek után a “vektorizált pixeleket” ritkítanunk kell. A topológia létrehozásánál abból indulunk ki, hogy a vektoros modellben azokat a pontokat nevezzük csomópontoknak, melyekben kettőtől eltérő számú vonal találkozik. A csomópontok megkeresésére egy egyszerű gráf bejáró algoritmust használunk, ami eredményképpen íveket alkotó ponthalmazokat határoz meg. Ez a struktúra elvileg már vektor struktúra gyakorlatilag azonban még szükség van ezeknek a pontoknak a ritkítására.
A vektorizált pixelpontok igen sűrűn vannak, különösen, ha az eredetijükül szolgáló analóg vonalak egyenesek vagy szabályos ívek voltak. Ezeknek a ritkítására interpolációs módszereket lehet alkalmazni, vagyis megpróbáljuk a pontokat egy görbére illeszteni. Ennél a műveletnél három szempontot kell figyelembe vennünk: a kihagyandó pontok eltérése a helyettesítő görbéjüktől nem haladhat meg egy megadott értéket, az eltérések előjele váltakozó kell legyen, valamint az eredeti pontsor hossza a helyettesítő görbe hosszánál nem lehet sokkal nagyobb. Vektor → raszter átalakítás A térinformatika szempontjából a vektor-raszter átalakítás megoldandó kérdései kissé más aspektusból jelentkeznek, mint a klasszikus átalakítás során, mivel ebben az esetben az a lényeges, hogy a vektor darabok egyértelműen és lehetőleg visszaállíthatóan nyerjék el raszteres alakjukat. Egy vektor raszterizálása során a legelső dolog az a koordinátarendszer leszögezése, vagyis az origó pozíciója a raszter képen, valamint a diszkrét pixeleknek a rendszerben való mérete. Ezek után egy vektor komponens (egyenes, görbe) raszterizálása mindössze annyiból áll, hogy a görbét leképezzük a raszterkép pixeleire. Ha a vonal két szomszédos cellát is érint, csak azt feketítjük be, amelyiken a hosszabb utat teszi meg. A mellékelt ábrán látszik két raszterizálás, azonban ezek közül az “a” az helyes, míg a “b” az helytelen pixelkiválasztás.
Vektoros poligonoknak a raszteres képpé való alakítása ugyancsak egy gyakori művelet, ezért a továbbiakban erről lesz egy pár szó. A félreértés elkerülése érdekében poligon alatt egy zárt formát értünk, melynek az oldalai nem metszik egymást. A raszterré alakítás a pásztázó (scan line) algoritmusra épül, melyben először rendezzük a poligon éleit y (csökkenő) majd x (növekvő) koordináta szerit. Ezek után kiszámítjuk a pásztázó egyenesnek a poligon éleivel való metszéspontjait (a pontos pixelt a imént említett módszerrel állapítjuk meg), majd az ezek közötti pixeleket az addigi metszéspontok számának függvényében festjük vagy sem (ha páratlan akkor belső pont, ha páros akkor külső).
Térbeli alapműveletek Ebben a részben szó lesz a raszter- illetve vektorképekkel végezhető műveletekről: transzformációk, távolságok, metszéspontok, stb.
Síkbeli transzformációk A síkbeli transzformációk annyit jelentenek, hogy a sík egyik koordináta rendszeréből a vektorokat átvisszük egy másikba valamilyen művelet segítségével. Röviden affin transzformáció két vektortér között. A három legfontosabb síkbeli transzformáció a következő: transzláció (mozgatás), rotáció (forgatás) és skálázás (nagyítás/kicsinyítés). Transzláció Euklideszi geometriában a transzláció az minden pontnak egy konstans értékkel való elmozdítása egy adott irányba. Úgy is lehet értelmezni, mint egy vektor hozzáadása minden ponthoz, vagy a koordináta-rendszer origójának az elmozdítása. A transzlációt mátrixos művelet formájában is fel lehet írni, viszont mivel affin művelet, de nem lineáris, ezért homogén koordinátás segítségével lehet megadni (tehát (x, y) helyett (x, y, 1) lesz). Ha egy mátrix és
vektorral szeretnénk eltolni egy az eredmény.
vektort, akkor
[
[
][
lesz a transzlációs
]
]
[
]
Rotáció Euklideszi geometriában a rotáció az a tér minden pontjának az elforgatása az rögzített pont körül. A rotáció egy izomorfizmus, vagyis a transzformáció során nem változik a távolság a tér két pontja között. Két dimenzióban (síkban) egyetlen egy szög szükséges a forgatás meghatározására. A forgatás kiszámítására két módszer létezik: mátrix algebra valamint komplex számok. Egy
pont elforgatása egy [
szöggel az alábbi transzformációval történik. ]
[
][
]
Skálázás Euklideszi geometriában az egyenletes skálázás egy lineáris transzformáció, aminek segítségével az objektum méretét növeljük vagy csökkentjük; a skálázási együttható ugyanakkora minden irányba. Ennek az általánosítása a skálázás, amely esetében a különbség annyi, hogy a különböző tengelyeken különböző skálázási együttható van. Egy objektum vektorral való skálázása az az objektum minden mátrixxal való beszorzását jelenti. [ [
pontjának az
] ][
]
[
]
Távolságfogalmak A legkézenfekvőbb és megszokottabb távolság vektoros adatmodellek esetén az az euklideszi távolság, mely két, egy síkban fekvő pont távolságát a Pitagorasz tétel segítségével definiálja. √ Egy másik kevésbé ismert távolság, ami viszont ugyancsak fontos szerepet játszik a térinformatikában az a Manhattan távolság, amit talán inkább használnak a raszteres adatmodelleknél.
Az alábbi képen látszik a különbség két pontnak az euklideszi (zöld) és a Manhattan (piros, kék, sárga) távolsága között.
Bibliográfia
Dr. Sárközy Ferenc: Térinformatikai elméleti oktató anyag. Budapest, 1991. 2010. Április 26. < http://www.agt.bme.hu/tutor_h/terinfor/tbev.htm >
Wikipedia: Affine transformation 2010. Április 26. < http://en.wikipedia.org/wiki/Affine_transformation > Wikipedia: Manhattan distance 2010. Április 26. < http://en.wikipedia.org/wiki/Manhattan_distance > Wikipedia: Raster graphics 2010. Április 26. < http://en.wikipedia.org/wiki/Raster_graphics > Wikipedia: Rotation (mathematics) 2010. Április 26. < http://en.wikipedia.org/wiki/Rotation_(mathematics) > Wikipedia: Scaling (geometry) 2010. Április 26. < http://en.wikipedia.org/wiki/Scaling_(geometry) > Wikipedia: Translation (geometry) 2010. Április 26. < http://en.wikipedia.org/wiki/Translation_(geometry) > Wikipedia: Vector graphics 2010. Április 26. < http://en.wikipedia.org/wiki/Vector_graphics >
