Felület előállítása rendezetlen 3D pontfelhőből Vass Gergely
[email protected] Tanuló és hibrid információs rendszerek 2002 tavasz Budapesti Műszaki és Gazdaságtudományi Egyetem
Feladat Gyakori feladat a 3D grafikában valós felszínek rekonstrukciója 3D pontfelhő alapján. Ez a ponthalmaz származhat egy lézeres szkennertől vagy egy képszekvenciát feldolgozó képalapú (image based) modellező eszköztől. A feladat megoldása során általam készített parametrikus felületeket (NURBS felületeket) mintavételeztem egyenletesen (a paraméter tartományban) és az így kapott pontfelhőt alkalmaztam. A feladatot a Maya nevű 3D programcsomag saját nyelve, a MEL (Maya Embedded Language) segítségével implementáltam. Ez szükségtelenné tette a 3D megjelenítés és a felületek tárolásának megvalósítását.
1. Bevezető A feladat megoldásához Yizhou Yu (University of California at Berkely) Surface Reconstruction from Unorganized Points Using Self-Organizing Networks című dolgozatát alkalmaztam. A megoldás alapötlete a Kohonen háló alkalmazása úgy, hogy egy polygon felszín csúcspontjait tekintjük neuronoknak, koordinátájuk pedig a súlyoknak felelnek meg. 1.1 Kohonen háló Egy egyszerű Kohonen háló neuronok két dimenziós tömbjéből áll. A neuronok egymással össze lehetnek kötve, az alkalmazástól függően más és más konfigurációban. A háló tanításához egy bemeneti vektor halmazt használunk, esetünkben ezek három dimenziós vektorok. A tanítás lényege a következő: minden egyes tanítóponthos megkeressük a legközelebbi súlyú csomópontot (ez lesz az un. győztes), majd ennek a súlyát módosítjuk úgy, hogy az éppen számított tanítóponthoz közeledjen. 1.2 Tanítás megvalósítása Az általam megvalósított algoritmus “menetekre” osztja fel a tanítást. Egy menet alatt az összes tanító vektor egyszer kerül felhasználásra. A tanulási faktor – annak a mértéke, hogy a csomópont súlyának és a tanító vektor távolságának hanyad részével módosítsuk az eredeti súlyt – minden menetben szabadon választható.
2. Megvalósítás 2.1 Mintavételezés A teszteléshez használt NURBS felületet az UV paraméter tartományban egyenletesen mintavételeztem jitter használatával, hogy ne egy szabályos rács szerkezetű pontfelhőt kapjak. Sajnos ahol a NURBS felület paraméter-vonalai nagyon sűrűek voltak ott a mintapontok is sűrűn helyezkednek el. A mintavételezést végző MEL program váza (a MEL nyelv szintaktikája a C-hez hasonlít): global proc mintavetelez(int $f){ string $nev[]=`ls -sl`; string $obj=$nev[0];
//az aktuális objektum nevet kiolvasom az $obj változóba
float $pos[]; float $p1,$p2;
//ide fog kerülni a minta 3d koordinátája //a mintavételi hely (u és v koordináta)
int $szamlalo1; int $szamlalo1;
//két számláló a két ciklushoz
for($szamlalo1=0;$szamlalo1<$number;$szamlalo1++) //u és v mentén egyenletesen végigfor($szamlalo2=0;$szamlalo2<$number;$szamlalo2++) //haladunk, ezert van 2 ciklus {$p1=rand(-1,1)*0.4; $p2=rand(-1,1)*0.4; $p1=($szamlalo1/$f)+$p1/$f; $p2=($szamlalo2/$f)+$p2/$f;
//jitter értéke //minta helye (egyenletes lépés+jitter)
$pos=eval("pointPosition"+$obj+".uv["+$p1+"]["+$p2+"]"); eval("spaceLocator -p"+$pos[0]+" "+$pos[1]+" "+$pos[2]); }
//mintapont koordin. //egy 3d pont készítése
}
A tanítás elvégzéséhez lehetőség van több menet autómatikus elvégzésére. Ehhez szintén egy rövid programot készítettem, mely egy ciklusban meghívja a tanítást végző “pass” függvényt. A jelenlegi verzióban nem változik a tanítás során a bátorsági faktor, ezt kézzel kell megváltoztatni.
2.2 Háló létrehozása A fentiekben leírtak alapján a Kohonen háló egy polygon felszín lesz, mely sokszögekből áll. A csúcspontok a háló neuronjai és 3D koordinátájuk a súlyvektor. A polygon felszínt úgy érdemes felvenni, hogy a pontfelhőt minél jobban megtanulja. A tesztek során két típusú feladattal probálkoztam. Az első egy deformált – hegyes völgyes – síklap tanítása volt. Ehhez a feladathoz egy síklap alakú polygon felszíből indultam ki. A csúcspontok száma célszerűen kevesebb volt mint a tanítópontok száma. A másik feladat egy gömbszerű – fejhez hasoló – 3D objektum közelítése volt. Ehhez egy polygon gömböt inicializáltam.
2.3 Tanítás A tanítás elemi lépése a “menet”. Ez azt jelenti, hogy a tanító vektorokat sorban beolvasom, megkeresem a nyertes csúcspontot és megváltoztatom a súlyát. A kísérletek során kiderült, hogy zavaró lehet, ha a súlyokat a meneten belül folyamatosan változtatom. Gyakran előfordult, hogy az első nyerő pontok annyira megközelítették a ponthálót, hogy a többi pont soha nem lett nyertes, és így a súlya sem változott. Az egy menet tanítására szolgáló MEL program váza:
global proc pass(float $bator){
string $selected[]=`ls -sl`; string $obj=$selected[0]; //az aktuális objektum nevet kiolvasom az $obj változóba int $szemet[]=eval("polyEvaluate -v "+$obj); int $vtx=$szemet[0]; select -cl; select -hi "tpontok"; select -d "tpontok";
// a “tpontok” csoportban lév• tanítópontok kiválasztása
string $locatorok[]=`ls -sl -type transform`; int $locszam=size($locatorok); int $szaml; string $aktual; string $parancsok[]; float $pos[3];
//tanítópontok nevei egy tömbbe //a tanítópontok száma
//változók
for($szaml=0;$szaml<$locszam;$szaml++){ $aktual=$locatorok[$szaml]; $pos=eval("pointPosition "+$aktual); int $vszaml; int $winner; float $winnertav=9999999; float $aktpos[]; float $akttav;
//kiolvasom a csúcspontok számát
//minden egyes input vektorra lefut //vizsgált tanítópont helye
//változók a legközelebbi pont kereséséhez
for($vszaml=0;$vszaml<$vtx;$vszaml++){
//megkeressuk a legkozelebbi vertexet
$aktpos=eval("pointPosition "+$obj+".vtx["+$vszaml+"]");//az aktuális vertex súlya $akttav=($pos[0]-$aktpos[0])*($pos[0]-$aktpos[0])+($pos[1]-$aktpos[1])*($pos[1]$aktpos[1])+($pos[2]-$aktpos[2])*($pos[2]-$aktpos[2]); //távolság számítása if($akttav<$winnertav) {$winner=$vszaml; $winnertav=$akttav;} }
//legközelebbi kiválasztása
//megvan a legkozelebbi vertex, most ezt kell mozgatni float $vector[3]; $aktpos = eval("pointPosition "+$obj+".vtx["+$winner+"]"); $vector[0]=($pos[0]-$aktpos[0])*$bator; $vector[1]=($pos[1]-$aktpos[1])*$bator; //módosítás kiszámítása a különbség vektor $vector[2]=($pos[2]-$aktpos[2])*$bator; //és a bátorsági faktor alapján $parancsok[$szaml]=("move "+$obj+".vtx["+$winner+"]");
-r
"+$vector[0]+"
"+$vector[1]+"
"+$vector[2]+"
//mozgatások elvégzése a menet végén, addig // egy tömbben tároljuk }//for szaml int $pszaml; for($pszaml=0;$pszaml<$locszam;$pszaml++) eval($parancsok[$pszaml]); //súlyok módosítása }
3. Tesztelés A kezdeti tesztek leggyakoribb hibája az volt, hogy bizonyos csúcspontok nem soha nem nyertek, így a helyükön maradtak. Ennek eredetileg az volt az oka, hogy a súlyok módosítását a tanítás alatt folyamatosan végeztem, így egyes csúcspontok kiugrottak a többiek közül. Az algoritmus átalakítás után – mikor már a súlyok módosítása csak a menetek után történt meg – kellően alacsony bátorsági faktor mellett már képes volt a háló minden pontja tanulni. Sajnos azonban a hibát nem tudtam teljesen kiküszöbölni, és a tanítás során gyakran ragadtak be pontok az eredeti helyükbe. A probléma másik lehetséges megoldása az, hogy egy nagyon egyszerű polygon felülettel indítom a tanítást és a tanítási menetek után finomítom a polygon hálót. Bár ez a módszer kiválóan működni látszik a polygonok száma nagyon gyorsan elszáll, hiszen minden menetben négyszereződik a finomság. Ez pedig a tanítást nagyon lelassítja.
Látható, hogy a túl nagy bátorsági faktor hatására sok csomópont beragadt az eredeti helyén.
A bátorsági faktor csökkentésével és a tanítópontok sűrítésével sokkal jobb az eredmény (de nem tökéletes).
4. Fejlesztési lehetőségek Az egyedüli megoldatlan probléma – a lassú számítási időn kívül – a “beragadó” súlyok esete. Lehetséges lenne annak implementálása, hogy a gyakran nyertes és így kilendülő súlyok magukkal húzzák szomszédaikat, így megakadályozva, hogy azok a helyükön maradjanak. Sajnos a felhasznált irodalom nem is foglalkozik ezzel a problémával. A sebesség növelésének egyetlen hatékony módja az lenne, hogy az algoritmust egy önálló alkalmazásként kell implementálni. Ez valószínűleg sokkal nagyobb hálók és tanító halmazok alkalmazását is lehetővé tenné.
Ha a hálót folyamatosan finomítottam a tanítás során jó eredményeket kaptam. Sajnos a probléma komplexítása nagyon gyorsan nőtt és a tanítási idő leromlott.
