Maa-57.270 Fotogrammetrian, kaukokartoituksen ja kuvatulkinnan seminaari
3.4.1996
tekn.yo Markku Lindgren
36465E
Geometrisia malleja rakennetaan tietyn tehtävän suorittamiseksi. Tässä esityksessä tarkastellaan geometrisen mallin muodostamista erityisesti fotogrammetrian ja tietokonenäön näkökulmasta. Geometrisen mallin rakentamiseksi on valittava jokin mallinnustapa. Toiset kohteet voidaan mallintaa esimerkiksi säännöllisiin kappaleisiin perustuvalla mallinnusmenetelmällä, jotkin toiset paremmin esimerkiksi kolmioverkolla. Geometrisessa mallinnuksessa on aina tehtävä päätös mallinnettavien yksityiskohtien minimikoosta. Tällöin valittua minimikokoa pienempiä yksityiskohtia ei sisällytetä geometriseen malliin, vaan ne voidaan tarvittaessa esittää esimerkiksi tekstuurikarttojen avulla. Tämän esityksen tarkoituksena on selvittää minkä tyyppisiä mallinnusmenetelmiä 3D-mallinnuksessa on käytettävissä sekä millä kriteereillä mallinnusmenetelmän valinta tulisi suorittaa. Tarkoituksena ei ole kuitenkaan käsitellä itse malliinnusprosessin kulkua vaan kiinnittää enemmänkin huomiota prosessin lopputuotteeseen.
Geometrisella esityksellä tarkoitetaan tietyntyyppistä kehystä sekä rakenneosia joiden puitteissa ja joiden avulla geometrinen malli muodostetaan. Geometrinen esitys rakentuu geometrisista alkeisosista (primitives) sekä alkeisosien yhdistämismenetelmistä (primitive composition methods) [Besl]. Lisäksi esityksen pitäisi sisältää tieto mallin tarkkuudesta sekä algoritmeista joilla mallia voidaan käsitellä [Faugeras].
Kuva 1) Geometrisen esityksen rakenne
3D-avaruudessa geometrisia alkeisosia ovat [Besl]:
Käyrien esitysmuotoja on useita, yleisesti voidaan sanoa että mitä enemmän käyrän esityksessä on parametreja, sitä ilmaisukykyisempi käyrä on. Toisaalta ainakaan käyrän sovituksessa ilmaisuvoimaisimmille käyrille ei ole olemassa tehokkaita sovitusalgoritmeja [Besl]. Tämä pätenee useissa muissakin sovelluksissa.
Pinnoista mainitsemisen arvoisia ovat tasopinnat, neliölliset pinnat sekä NURBS pinnat (Non-Uniform Rational B-Spline Surfaces), jotka ovat esimerkiksi CAD- suunnittelussa standardoituja pinnan esitystapoja [Besl].
Tilavuuskappale voidaan esittää esimerkiksi vokselimatriisina, alkeiskappaleista konstruoituna yhdistettynä kappaleena tai pintojen rajoittamana kappaleena.
Alkeisosat voidaan esittää usealla tavalla, joista seuraavassa esitetään tämän aiheen kannalta olennaisimmat:
n-dimensionaalisen alkeisosan parametrinen muoto n+m-ulotteisessa avaruudessa on
n-dimensionaalisen alkeisosan implisiittinen muoto n-ulotteisessa
avaruudessa on:
n-dimensionaalsen alkeisosan digitaalinen muoto n+m-ulotteisessa
avaruudessa on lista pisteitä jotka kuuluvat alkeisosaan
Lisäksi Besl, jonka esitykseen edellä esitetty perustuu mainitsee ratkaisumuodon, jolla tarkoitetaan esimerkiksi osittaisdifferentiaaliyhtälön ratkaisuna saatua esitystä, sekä graafimuodon.
Yksittäisten alkeisosien kyky ilmaista muotoa on rajoitettu. Tämän vuoksi on määriteltävä keinot joiden avulla alkeisosia voidaan yhdistää suuremmiksi kokonaisuuksiksi [Besl]. Yhdistämismenetelmiä ovat Boolen yhdistämismenetelmä (boolean composition method), rajamenetelmä (boundary composition method) sekä pyyhkäisymenetelmä (sweep composition method).
Boolen yhdistämismenetelmässä yhdistetty kappale rakentuu Boolen operaatioiden avulla yhdistetyistä alkeisosista. Boolen operaatioita ovat yhdiste, leikkaus ja erotus. Yhdistetty kappale voidaan esittää binääripuuna, jossa lehdet ovat alkeisosia ja muut solmut operaattoreita [Besl].
Rajamenetelmä (Boundary composition method) määrittelee n-ulotteisen kappaleen n-1 -ulotteisten alkeisosien avulla [Besl]. Esimerkki tästä menetelmästä on epäsäännöllinen kolmioverkko, jossa tilavuus määritellään tasokolmioiden avulla.
Pyyhkäisymenetelmä määrittelee n+1 -ulotteisen kappaleen n-ulotteisen kappaleen ja 1-ulotteisen käyrän avulla. n+1 -ulotteinen kappale syntyy siten, että n-ulotteista kappaletta liikutetaan pitkin käyrää tietty matka. n-ulotteista kappaletta voidaan myös skaalata tai pyörittää pyyhkäisyn aikana [Besl].
Yhdistämismenetelmiä voidaan käyttää yhdistetysti saman projektin puitteissa erityyppisten kappaleiden mallintamiseen. Esimerkiksi maaston muodot voidaan mallintaa rajamenetelmää käyttäen kolmioverkolla, mutta alueella olevat rakennukset voidaan mallintaa Boolen menetelmällä käyttäen yksinkertaisia geometrisia alkeisosia.
Geometrinen malli voidaan muodostaa joko interaktiivisesti tai mittausten perusteella. Interaktiivisessa tapauksessa, esimerkiksi CAD-suunnittelussa, mallin ulkoista tarkkuutta ei ole mielekästä määrittää, koska kohteesta, jota malli kuvaa ei ole saatavilla täsmällistä tietoa. Sen sijaan jos malli muodostetaan mittausten perusteella, voidaan arvioida kohteen ja sitä kuvaavan mallin vastaavuutta määrittämällä mittausten ja niistä konstruoidun mallin virhelähteet ja virheet. Tieto mallin tarkkuudesta tulisi sisältyä geometriseen esitykseen, koska se mahdollistaa arvion tekemisen mallin soveltuvuudesta tiettyyn käyttötarkoitukseen.
Mallin käyttäminen tiettyyn käyttötarkoitukseen tapahtuu soveltamalla tiettyjä algoritmeja. Malli sinänsä ei ole kovinkaan käyttökelpoinen, jos sen käsittelemiseksi ei ole olemassa kattavaa valikoimaa tehokkaita algoritmeja (ja niiden implemantaatioita). Geometristen mallien, kuten muidenkin tietorakenteiden, sekä malleihin perustuvien algoritmien välillä on hyvin läheinen riippuvuussuhde siten, että tietyt algoritmit ovat luonnollisia tietylle mallille. Algoritmin luonnollisuus ilmenee yksinkertaisena rakenteena sekä tehokkaana suoritusnopeutena. Näistä edellä mainituista syistä geometrisen esityksen pitäisi sisältää tieto käytettävissä olevista algoritmeista sekä niiden kompleksisuudesta.
3D-geometristen esitysten päätyypit voidaan luokitella seuraavasti tilavuus- ja pinta-alkeisosien perusteella [Besl]:
Tilavuusmallit voivat perustua ei-päällekkäisiin tilavuuselementteihin, CSG-puihin (constructive solid geometry), pyyhkäisyalkeisosiin tai rajoittaviin pintoihin (BRep). Ei-päällekkäisiä tilavuuselementtejä ovat esimerkiksi vokselit. CSG-puulla tarkoitetaan Boolen menetelmällä muodostettua binääripuuesitystä, jossa lehtisolmut ovat 3D-kappaleita ja muut solmut edustavat Boolen operaatioita.
Pintamallit voivat perustua esimerkiksi tasokolmioihin, muihin monikulmioihin tai toisen asteen pintoihin. Näin muodostetut pinnat voivat edelleen muodostaa rajoittaviin pintoihin perustuvan tilavuusmallin.
Kuva 2) 3D-geometristen esitysten päätyypit [Mukaeltu Besl:stä].
Faugeras esittää joukon kriteereitä joiden perusteella geometrinen esitys tiettyyn käyttötarkoitukseen tulisi valita. Perusvaatimus on että esitys on mahdollisimman yksinkertainen, koska esityksen yksinkertaisuus on suorassa suhteessa siihen kuinka helposti malli on muodostettavissa. Kuitenkin esityksen on oltava tarpeeksi ilmaisuvoimainen, jotta sen puitteissa voidaan esittää kaikki käyttötarkoituksen kannalta olennainen informaatio. Myös mallin tarkkuuden on oltava käyttötarkoitusta vastaava.
Jos valintatilannetta tarkastellaan annetun tehtävän näkökulmasta, niin geometrisen esityksen valinta voidaankin tiivistää kahteen kysymykseen [Faugeras]:
1. Mitä informaatiota mallissa on esitettävä annetun tehtävän suorittamiseksi?
Tähän kysymykseen on vastattava yleensä tapauskohtaisesti ja se edellyttää tehtävänannolta täsmällisyyttä ja yksiselitteisyyttä. On myös harkittava miten tarvittava informaatio kerätään ja miten se liitetään valittavaan esitykseen.
2. Millä tarkkuudella informaatio on esitettävä?
Tässä on arvioitava paitsi mittauksilta edellytettävää tarkkuutta, myös sitä millä alkeisosilla malli tullaan toteuttamaan, esimerkiksi voidaanko kohdetta approksimoida riittävän hyvin tasokolmioilla vai pitäisikö käyttää esimerkiksi toisen asteen pintoja?
Jos valintaa lähestytään esitysten ja niiden ominaisuuksien suunnasta, olisi harkittava seuraavia asioita ja niiden soveltuvuutta kyseessä olevaan käyttötarkoitukseen [Faugeras]:
1. Mitkä ovat esityksen alkeisosat?
Onko kyseessä esimerkiksi pinta- vai tilavuusmalli ja koostuuko malli esimerkiksi 3D-alkioista (vokseleista) vai 2D-alkioista.
2. Missä koordinaatistossa alkeisosat esitetään?
Mittaustilanteessa käytetään yleensä sensorikeskeistä koordinaatistoa, mutta mallinnus tapahtuu kohdekeskeisessä koordinaatistossa. Koordinaatiston valinta liittyy joissain tapauksissa läheisesti tietorakenteiden valintaan, koska muutoksen esityksessä tulisi heijastua samaa kertaluokkaa olevana muutoksena tietorakenteessa. Joissain tapauksissa visuaalisesti pieni muutos mallissa voi aiheuttaa suuren muutoksen sitä kuvaavassa tietorakenteessa, mikä ei ole yleensä toivottavaa.
3. Miten alkeisosat on järjestetty esityksessä?
Esityksen rakenteella on suora yhteys siihen miten mallia voidaan käsitellä. Tiettyjä operaatioita varten tietyssä tietorakenteessa on olemassa tehokkaita algoritmeja, mutta vastaavat operaatiot voivat olla hitaita tai jopa mahdottomia toisten tietorakenteiden kanssa.
4. Mitkä operaatiot ovat helppoja suorittaa kyseiseen esitykseen perustuen ja mitkä vaikeita?
Tällä on selkeä yhteys mallin käyttöön ja annettuun tehtävään. Malli tulisi valita siten että yleisimmille operaatioille on olemassa mahdollisimman tehokkaat ja vakaat algoritmit.
5. Kuinka paljon tietojenkäsittelykapasiteettia mallin muodostaminen ja tallentaminen vaatii?
Tässä tulisi tarkastella myös lähtöaineiston merkitystä eikä rajoittua ainoastaan mallin muodostamisessa käytettävien algoritmien ja tietorakenteiden tarkasteluun. Jos tarkastelussa tehdään oletuksia lähtöaineistosta niiden tulisi perustua todelliseen tilanteeseen.
6. Minkä tyyppisiä kohteita esityksellä pyritään mallintamaan?
Jos annettu tehtävä koskee rajallista muotojen joukkoa, niin yleensä voidaan valita käytettäväksi suhteellisen yksinkertainen geometrinen esitys. Tämä on mahdollista esimerkiksi yksinkertaisten kohteiden tunnistuksessa tai säännöllisten kappaleiden mallintamisessa. Topografian mallintamisessa ei kuitenkaan yleensä voida käyttää yksinkertaisiin kappaleisiin perustuvaa mallinnusta.
7. Kuvaavatko erot kohteita vastaavissa tietorakenteissa eroja kohteiden muodossa?
Tämä kysymys tulee esille silloin, kun tarkastellaan rajoitettua muotojen joukkoa. Jotta eroista ylipäätään voitaisiin puhua täsmällisesti, olisi joukolle määriteltävä topologia sopivalla tavalla [Faugeras].
Näiden yleisten kriteerien lisäksi on harkittava sovelluskohtaisia kriteerejä joista Faugeras esittelee kohteen tunnistukseen, navigointiin ja esteiden välttämiseen liittyviä asioita. Näistä mielestäni seuraavien pitäisi kuulua myös yleisten kriteerien listaan:
8. Esityksen pitäisi pystyä määrittelemään malli jo vähäisten mittausten perusteella ja mallin tulisi konvergoida kohti oikeita tilavuuksia ja pintoja mittausten määrän lisääntyessä.
9. Esityksen tulisi pystyä suodattamaan "ylimääräiset" mittaukset sellaisilta alueilta joissa malli voidaan muodostaa luotettavasti harvemman datan perusteella. Esimerkiksi tasomaisilla alueilla mittauspisteitä on yleensä liian tiheässä, varsinkin jos mittaus on suoritettu automaattisesti. Ylimääräiset pisteet aiheuttavat malliin turhaa redundanssia joka haittaa mallin käsittelyä. Kaikki redundanssi mallissa ei kuitenkaan ole välttämättä turhaa.
Edellä esitetty kriteerien ja vaatimusten lista on hyvin vaativa, mutta ei varmastikaan kattava. Kaikkia kriteereitä ei yleensä pystytä täyttämään, joten käytettävä geometrinen esitys on valittava tehtävän kannalta tärkeimpien kriteerien perusteella. On kuitenkin hyödyllistä tuntea käytettävän esityksen ominaisuudet, jotta voitaisiin arvioida muodostettavan mallin käyttökelpoisuutta mahdollisesti muihin käyttötarkoituksiin.
Lähdeluettelo
Faugeras, Olivier; Three-Dimensional Computer Vision, The MIT Press, Cambridge Massachusetts
s. 403-477
Besl, Paul J.; Geometric Modeling and Computer Vision, Proceedings of the IEEE, vol 76, no. 8, August 1988