IZ ZNANOSTI IN STROKE POS USA AT1S TRIDI E ZIONAL E UDK 528. 77.0ll.561U.6 061.3(497.12 Otočec),,1995":528 RE ONSTRU CIJE ZGRADB IZ LET S H STERE POSNET OV Drago Torkar Institut Jožef Stefan, Ljubljana Prispelo za objavo: 1995-11-13 Pripravljeno za objavo: 1995-11-21 Izvleček V članku opisujemo poskus avtomatske rekonstrukcije zgradb, pn' katerem smo iz levega in desnega posnetka najprej izluščili ravne odseke obrisov objektov, nato pa med njimi iskali strukture, ki so potecialni kandidati za zgradbe, in jih zapisali z grafi. Korespondenčne zgradbe smo nato iskali s pomočjo algoritma za pn'leganje grafov. Ključne besede: Geodetski dan, luščenje značilk, odkrivanje zgradb, Otočec, rekonstrukcija zgradb, stereo pn·me,janje z značilkami, teorija grafov, 1995 1 UVOD ekonstrukcija zgrad v treh dimenzijah iz letalskih stereo posnetkov je ena od pogostih aplikacij s področja stereo posnetkov. Ker gre za časovno zahtevno opravilo, so se v zadnjih letih povečala raziskovanja avtomatskih metod (Huertas et al., 1993, Dang et al., 1994, Deren et al., 1994). den o problemov, ki ga je treba razrešiti pri avtomatski rekonstrukciji zgradb iz digitalnih stereo posnetkov, je samodejna določitev položaja korespondenčnih (istih) točk na levem in desnem posnetku. Iz lege korespondenčnih točk lahko izračunamo njihovo oddaljenost od perspektivnega centra kamere in nato položaj v absolutnih koordinatah. Do lege korespondenčnih točk oz. elementov slik pridemo tako, da med seboj primerjamo dele levega in desnega posnetka ali pa iz posnetkov najprej izluščimo simbolne zapise· slik - značilke, ti morajo vsebovati opise objektov, ki nas zanimajo, in jih nato primerjamo med seboj. Nekatere metode pa uporabljajo tudi digitalni model reliefa (DMR), ki je lahko pridobljen s stereo prileganjem okolic točk iz letalskih posnetkov ali kako drugače (Weidner et. al., 1994). V splošnem nam pri iskanju korespondenčnih točk ali značilk s prileganjem povzroča preglavice več faktorjev, ki so pogojeni z geometrijo sterea. Geodetski vestnik 39 (1995) 4 2 ZASNOVA AVTOMATSKEGA POSTOPKA Pri izdelavi lastnega postopk~ a~tomatske rekonstr~kcije zgradb iz letalskih stereo posnetkov smo se delno opirali na delo Horauda m Skordasa (Horaud et. al., 1989). Za najtežji del naloge, t.j. poiskati korespondenčne elemente na levem in desnem posnetku, smo si izbrali metodo, ki spada v skupino iskanja disparitet s prileganjem značilk. Ker so zgradbe na posnetkih lahko tudi precej kompleksne, jih zadovoljivo opišemo le s strukturiranimi značilkami, ki jih sestavimo iz enostavnejših. Vsaka strukturirana značilka tako predstavlja eno zgradbo ali kompleks med seboj stikajočih se zgradb. Treba je bilo torej najprej izdelati postopek za odkrivanje posameznih zgradb in njihovo predstavitev s strukturami, nato pa uporabiti učinkovito metodo za ugotovitev korespondenčnih zgradb na levem in desnem posnetku. Celoten post~pek smo razbili na naslednje korake: o izločitev osnovnih značilk o povezovanje osnovnih značilk v strukture s pomočjo grafov o iskanje korespondenčnih značilk s prileganjem grafov o tridimenzionalna rekonstrukcija zgradb. 3 IZLOČITEV ZNAČILK a osnovne značilke smo si izbrali ravne odseke obrisov zgradb. S Cannyjevim operatorjem (Canny, 1983) smo na levem in desnem posnektu poiskali robove objektov na sliki. S spreminjanjem širine operatorja lahko vplivamo na to, kako podrobne spremembe v intenziteti točk bodo privzete kot del roba. Izbira širine je odvisna od osvetlitve in kontrasta slike in od vsebine oz. objektov, ki jim želimo poiskati robove. Za vsak posnetek posebej smo s poskušnjem določili primerno širino operatorja. Ker imajo zgradbe obrise večinoma sestavljene iz ravnih segmentov, smo zato z algoritmom gradnje ravnih črtnih odsekov poiskali ravne odseke robov, ki predstavljajo potencialne stranice zgradb. Zaradi vpliva šuma in toleranc postopka odkrivanja ravnih odsekov robov, je bilo smiselno izvesti popravljanje daljic. Algoritem vsebuje dva koraka. Najprej med vsemi značilkami iščemo tiste, ki so kolinearne in imajo krajišča dovolj blizu skupaj. Združimo jih v novo daljico. Nato pa za vsako krajišče vsake daljice pregledamo vsa preostala krajišča in v primeru, da sta dve ali več krajišč dovolj blizu, skrajšamo ali podaljšamo ustrezne daljice, tako da krajišča sovpadajo. Prav tako podaljšamo ali skrajšamo daljice, katerih krajišča so dovolj blizu drugih daljic, tako da so nova krajišča v presečiščih. 4 POVEZOVANJE OSNOVNIH ZNAČILK V STRUKTURE S POMOČJO GRAFOV Pri gradnji struktur želimo na koncu postopka dobiti množico struktur za levo in desno sliko stereo para, od katerih bo vsaka predstavljala simbolični opis zgradbe na sliki. Pri tem predpostavimo, da imajo zgradbe samo ravne robove in da je njihov obris vedno sklenjen. Gradnje struktur srno se lotili v dveh delih. V prvem smo gradili graf za levo in desno sliko iz osnovnih značilk, t.j. linearnih segmentov robov. Rezultat tega dela je bil nepovezan, obtežen graf, ki ga lahko poimenujemo tudi relacijski graf, saj odraža odnose med osnovnimi značilkami. V drugem pa smo izločili nekatera vozlišča in poiskali vse povezane podgrafe, ki opisujejo po eno zgradbo. Geodetski vestnik 39 (1995) 4 4.1 Gradnja relacijskega grafa iz osnovnih značilk Vsaka značil~a predsta~lj_a vozlišče z vr~dno_~tmi: leg~, velikost in kon_trast ter polji kazalcev, ki prcdstavlJaJO povezave. T1 polJi sta: polJe kazalcev se_stika_ z m polje kazalcev je_vzporeden_z. Kazalci iz polja se_stika_z kažejo na značilke, ki se stikajo ali sečejo z obravnavano značilko. Kazalci polja je_vzporeden_z pa na najbližje značilke, ki so vzporedne z omenjeno značilko. Tako ima vsaka značilka lahko največ dva kazalca je_vzporeden_z. Vsakemu vozlišču priredimo še število povezav tipa se_stika_z in število povezav je_vzporeden_z. v u l J'° a, d,2. Slika 1: Značilke leve in desne slike, za katere želimo zgraditi relacijska grafa rednosti vozlišč, ki predstavljajo uteži, določimo tako: lega je določena s koordinatami krajišč, velikost je enaka dolžini značilk in jo enostavno izračunamo, kontrast pa določimo s pregledovanjem okolice vsake daljice v obeh smereh, pravokotnih na njo, dokler ne naletimo na nov rob ali smo oddaljeni za dolžino daljice. Povezave tipa se_stika_z (na sliki 2 označene z 1) določimo tako, da za vsako značilko izračunamo presečišče premice, na katerih leži, s premicami, na katerih ležijo preostale značilke. Če leži presečišče na obeh značilkah, priredimo kazalcu ustrezno vrednost Če ne najdemo nobene povezave, postavimo vrednost, ki opisuje število povezav tipa se_stika_z, za ustrezno vozlišče grafa na nič. Podobno iščemo tudi povezave tipa je_vzporeden_z (na sliki 2 označene z 2). Za vsako daljico izračunamo smerni naklon premice, na kateri leži. Izmed daljic, katerih naklon je znotraj meja ±10%, hkrati pa se vzajemno prekrivajo v dolžini 60% ali več dolžine obravnavane daljice, izberemo tisto, ki ji je najbližja v eni od obeh smeri. Gradnja relacijskega grafa za primer iz slike 1 je prikazana na sliki 2. Geodetski vestnik 39 (1995) 4 Slika 2: Relacijska grafa leve in desne slike 4.2 Izločanje vozlišč in odkrivanje podgrafov gradili smo torej obteženi relacijski graf, ki pa je nepovezan, saj obstaja množica značilk, ki nimajo stičišč s sosedi niti niso z njimi vzporedne. Take proglasimo za neuporabne in jih izločimo tako, da iz grafa odstranimo vozlišča, ki jih predstavljajo. Prav tako odstranimo vozlišča, ki imajo samo eno povezavo posamezne vrste. S tem izločimo značilkc, ki imajo le eno vzporedno značilko ali se z njo stikajo. V praksi se zelo redko zgodi, da bi dve med seboj tako organizirani značilki v resnici predstavljali zgradbo. Če jo, je to posledica zelo slabe detekcije robov in ravnih odsekov, ki je običajno povezano s slabo izbiro parametrov, ki jih imamo pri tem na voljo. Poiskali bi radi tiste podgrafe, ki predstavljajo eno samo zgradbo na sliki. Le-ta je lahko sestavljena iz več sklopov, ki pa morajo biti med seboj povezani. Iskanje zaprtosti tokrat prevedemo na iskanje ciklov v grafu. Odkrivanje ciklov je dovolj preprosto in učinkovito. Predpostavljamo, da so zgradbe s stališča robov zaključene celote in da je predhodno odkrivanje osnovnih značilk dovolj učinkovito, da poišče vse robove na njih. Pri iskanju ciklov smo upoštevali samo povezave tipa se_stika_z. Uporabili pa smo metodo preiskovanja grafa v globino, s katero pa dobimo tudi cikle, ki na sliki ne predstavljajo zaprtosti. Zato jih s ponovnim preverjanjem vseh odkritih ciklov izločimo. Prav tako s pregledom preostalih ciklov odkrijemo tiste, ki so med seboj povezani. Tako smo našli vse povezane podgrafe. Vsak povezan podgraf načelno predstavlja eno ali več med seboj dotikajočih se zgradb. Ker smo take podgrafe odkrili na levi in desni sliki posebej, nam preostane še, da ugotovimo, kateri med njimi so korespondenčni. 5 ISKANJE KORESPONDENČNIH ZNAČILK S PRILEGANJEM GRAFOV aradi raznih vzrokov, kot so fotometrične razlike med levo in desno sliko, zakrivanje, problemi s sencami, napake pri pridobivanju osnovnih značilk, napake pri grajenju struktur idr. ne moremo pričakovati izomorfizma med povezanimi podgrafi relacijskih grafov. Korespondenčne podgrafe bomo torej morali Geodetski vestnik 39 ( 1995) 4 ugotavljati na osnovi podobnosti. Zato smo dvema vozliščema (i in j) relacijskega grafa. I ( min(Ki, Kj) + .!_ min(li, lj) + .!_ rc - 2