Structuri vectoriale 3D din colecții raster

Introducere

Tutorialul se adresează soluționării unei probleme complexe studiate în domeniul recunoașterii formelor sau Computer Vision în scopul determinării unui model spațial vectorial al unei realități 3D obținută din serii de imagini 2D capturate cu un aparat foto convențional. Metoda practică prezentată este liberă și lipsită de patente sau alte obligațiuni de proprietate intelectuală cu o singură excepție¹ substituibilă, iar suita software este disponibilă gratuit sub licențe generice opensource de tip GPL, BSD și Public Domain. Suita soft reflectă și inglobează una din metodele numerice “rarefiată” (sparse) și post-densificată particular detaliată în articolul: Un Doi și Trei: Istoria unei Margarete.

Suita software este compusă din patru componente esențiale, prezente în tutorial:

• Sift Detector – Scale Invariant Feature Transform detector
• Bundler – Structure from Motion (SfM) for Unordered Image Collections
• PMVS – Patch-based Multi-view Stereo Software
• CMVS – Clustering Views for Multi-view Stereo

O îmbunătățire autohtonă esențială în suita soft prezentă în tutorial față de pachetele soft originale disponibile pe pagina universității din Washington este faptul că Bundler folosește în pasul de corelare a punctelor SIFT comune libraria FLANN în loc de ANN, respectiv în PMVS/CMVS pasul de minimizare LMA este înlocuită cu librăria lmfit, o îmbunătățire remarcabilă adusă de Nghia Ho care permite o viteză suplimentară notabilă de până la 40%, respectiv un grad de precizie în a determina inferențele mai acurat în pașii de corelare între poze, un lucru ce scutește numeric pașii de aliniament al camerelor în spațiu (bundle).

Rechizitoriu

Pentru a utiliza suita este recomandată platforma LINUX, particular în acest tutorial s-a optat în mod convenabil de către autor distribuția Fedora (versiunea 16) pentru care este pregătit un rechizitoriu în format RPM cu pachetele soft precompilate ale suitei. Există o încercare din partea autorului acestui tutorial de a porta suita soft pentru platformele Microsoft Windows dar din păcate aceste platforme sunt limitate la lucru mapat cu memoria undeva la 1.5Gb, un fapt mult insuficient, anume heap_size e limitat din motive comerciale în speță pe varianta win32, în plus autorul constată o compatibilitate cod sursă insuficientă a componentelor soft cu API-ul cerut de aceste platforme Microsoft.

Sunt disponibile două soluții alternative linux, și anume în mod convenabil utilizatorul poate opta să instaleze cu ușurință întreaga suită Linux pe un stick USB fară a perturba sistemul de operare existent deja (modul recomandat) sau dacă dispune de o distribuție Fedora deja instalată prin simpla adăugare a unei căi către rechizitoriu de pe site. Distribuția pe stick USB este una minimalistă conține doar suita și mediul necesar rulării CMVS/PMVS.

Instalare pe stick USB

Pentru a instala pe un stick USB întreaga suită se descarcă una din variantele de imagini .iso:

• i386 cmvs-i386-2011Nov05.iso sha1: 60d68be729ccf9f451cc5fdcce3682bde5e5e7d0
• x86_64 cmvs-x86_64-2011Nov05.iso sha1: 1e291571a8ed7f958c3f3961f1f050f1a65ab494

După descărcare, cu ajutorul tool-ului Live USB Creator disponibil pentru Microsoft Windows se poate transfera una din variantele imaginii .iso optată pe un stick USB, stickul rezultat fiind unul bootabil.

• Recomandat un stick USB de o capacitate de 4Gbyte sau minim 2Gbyte
• Formatați obligatoriu prealabil stick-ul USB în format tip FAT32
• Alocați ~100M “Persistent Storage” la transferul .iso cu LiveUSBCreator

Odată preparat stickul USB, din meniul BIOS al calculatorului se poate alege ca stickul să fie considerat prioritar la pornirea sistem sau la startarea calculatorului printr-o tastă specială (dacă e suportat de sistem) afișearea unui meniu de selecție spre alegerea dispozitivului de start USB.

Instalare directă pe Fedora

Pentru a instala pe o distributie Fedora Linux deja existentă se poate rula într-o consolă cu drepturi depline “root” urmatoarele spre a aduce și instala pachetele soft precompilate:

rpm -ivh http://www.geo-spatial.org/cmvs/geo-spatial.org-1.0.0-1.noarch.rpm
yum -y install sift bundler cmvs meshlab

Rechizitoriul pachetelor soft, dar și codul sursă în format .srpm ce includ și patch-urile necesare compilării corecte pe platforma Linux se gasesc aici. Pachetele soft în format .rpm precompilate sunt disponibile momentan pentru versiunile Fedora Linux 15 și 16.

Cerințe sistem

• disponibilitate sistem PC cu memorie 4G RAM sau un minim de 2G.
• cameră foto de 12Mpix pentru rezultate dense sau minim 5M.
• capabilitate a camerei de marcaj a distanței focale în antetul EXIF a pozei rezultate.

Suita a fost compilată cu un efort autohton de catre autor în conformitate cu ghidul riguros a distribuției Fedora, fiind necesară o suită întreagă de patch-uri si adaptări peste codul original pentru un rulaj corect.

Pregătire set poze

Odată ce pozele au fost colectate din teren ele se copiază într-un dosar pe rădăcina stick-ului USB sau dacă deja dețineti o instalare pe PC a distribuției Fedora Linux atunci se copiază într-un dosar dedicat. În acest tutorial denumirea dosarului din rădăcina stick-ului USB se va numi “my3dwork”.

Iată câteva seturi de imagini disponibile la scară mică:

• Cluj Napoca – Statuia Sf. Gheorghe²: cluj-statue.zip 70 × 5Mpix
• București – Scenă Teatru: buc-scena.zip 34 × 8Mpix
• București – Scenă Pietre: buc-pietre.zip 7 × 8Mpix
• București – Scenă Stradă: buc-strada.zip 8 × 8Mpix

---

I. SIFT și Bundler

Pasul întâi constă în găsirea descriptorilor de tip SIFT, corelarea elementelor comune între poze cu ajutorul descriptorilor determinați și ajustarea completă a scenei în mod “sparse”, adică rarefiat.

În cazul în care ați pornit proaspăt de pe stick USB, deschideți o fereastră terminal (icoana cu ecran negru), respectiv poziționati cursorul în dosarul de lucru, cu următoarele comenzi:

su -
cd /mnt/stick/my3dwork/

Comanda care se rulează direct în dosarul cu imagini prezent:

RunBundler.sh .

Modelul obținut va fi un model vectorial special într-un format intern tip bundler, reprezentat prin fișierul bundle.out în care sunt determinate pozițiile tuturor camerelor în spațiu cu parametrii particular reprezentativi: rotație, scalare, translație a fiecărei camere cât și o mărime scalară exactă. Practic fiecărei poze/camere în parte se asignează o matrice de homografie. Precizia scenei ca valoare metrică este una foarte înaltă, pasul executat de LMA conferă precizii sub centimetrice în special dacă se foloseste ca sursă imagini de rezoluție înaltă și multe imagini care sa descrie scena.

Se remarcă fișierele auxiliare generate în acest pas, fiecare poză este însoțită de câte un fișier ce conține descriptorii SIFT în format .key comprimat gzip, respectiv rezultatul corelării tuturor imaginilor cu metoda FLANN este reprezentat prin fișierul: matches.init.txt.

Secventa de extragere SIFT la o rezoluție de 5Mpix oscilează între 5k și 14k puncte descriptor, iar la 8Mpix între 50k și 120k descriptori tip SIFT, adică rezultate net superioare. Ideal este să existe un bazin mare de descriptori locali SIFT. Acest lucru depinde de calitatea și acuratețea camerei și este direct influențată de rezoluția în pixeli a camerei. Un dezavantaj să aveți prea mulți descriptori SIFT este viteza de execuție la punctul de corelare “KeyMatching” care va fi semnificativ mai lent, dată fiind multidimensionalitatea ridicată a vectorilor SIFT în spațiul numerelor reale R. Observați această informație despre numărul descriptorilor în consolă la mesajele afișate în timpul acestui pas de execuție.

Pozițiile determinate ale camerelor în scena “statuie”, modelul rarefiat.

---

II. Preparare PMVS

Pentru a pregati rezultatul bundler.out către pașii următori este nevoie de o conversie de format specială respectiv o ajustare a distorsiunilor radiale ale imaginilor, respectiv de preparare a unui proiect de tip “pmvs”:

Bundle2PMVS list.txt bundle/bundle.out

Suita premergătoare este preparată, pentru a finaliza proiectul “pmvs” rulați:

sh pmvs/prep_pmvs.sh

Se poate observa la finalul mesajelor câmpul “Num visible:” indică numărul punctelor rarefiate de tip reper inter-poze disponibile și “Num cameras:” numărul total de camere/poze reliabile care în mod normal trebuie să coincidă cu numarul original de poze, în caz contrar anumite poze nu sunt utilizabile și au fost scoase din proiect.

Imaginile au fost corectate radial spre a fi utilizate în mod fotogrametric în pașii de densificare unde practic se vor proiecta sub forma unor “patch-uri” sau grupuri de pixeli din imagine înspre scena vectorială deja aliniată și ajustată în spațiu.

---

III. Densificare model final

CMVS sau PMVS ?

La finalul mesajelor tiparite din consola pasului anterior, poate ați remarcat sub forma unui avertisment în consolă cum că sunt două opțiuni distincte pentru densificarea finală:

• CMVS: este practic un tool care divide proiectul “pmvs” în mai multe proiecte mici (clustere), ce pot fi rulate fiecare în parte cu utilitarul PMVS. Utilizați CMVS doar la proiecte mari cu sute de poze sau mii, încercați o diviziune în clustere de 50-100 de poze în funcție de rezoluția imaginilor.

• PMVS: este util când aveți o scenă simplă, este un utilitar de reconstrucție bazat pe “patch-uri”, practic densifică complet într-un nor de puncte 3D scena de tip “sparse” bundle.out obținută, respectiv adaugă informația culoare RGB ca atribut al fiecărui punct vectorial.

Varianta PMVS:

Pentru densificare finală puteți merge cu utilitarul pmvs2, de notat că puteți ajusta prealabil fișierul de configurare pmvs_options.txt:

pmvs2 pmvs/ pmvs_options.txt

Varianta CMVS:

Pentru densificarea unui proiect amplu de tot cu peste >100 sau mii de imagini este recomandat mecanismul de divizare în clustere a întregului proiect. Practic se generează mai multe sub-proiecte care sunt rulate secvențial sau cine are posibilitatea în cadrul unui proiect mai amplu chiar pe mai multe mașini paralele simultan:

cmvs pmvs/ 50 2
genOption pmvs/

Rulați pentru fiecare fișier în parte pmvs/option-XXXX comanda:

pmvs pmvs/ option-XXXXX

---

IV. Model Final

Scena “teatru”, Facultatea de Geografie București.

Modelul (sau modelele dacă s-a rulat via CMVS) finale le găsiți în format PLY în dosarul local: pmvs/models/ , se pot deschide cu ajutorul MeshLab rulând:

cd /mnt/stick/my3dwork/pmvs/models/
meshlab *.ply

Există posibilitatea de vizualizare cu ochelari 3D anaglifici (roșu-albastru) pe un ecran clasic 2D (TFT sau analogic) cu ajutorul: ScanView, pentru a-l utiliza este posibil exportul din MeshLab a formatului PLY în ceva acceptat de acesta.

---

• ¹ Algoritmul SIFT se supune patentului: “Method and apparatus for identifying scale invariant features in an image and use of same for locating an object in an image,” David G. Lowe, US Patent 6,711,293 (March 23, 2004). Provisional application filed March 8, 1999. Asignee: The University of British Columbia. For further details, contact David Lowe (lowe@cs.ubc.ca) or the University-Industry Liaison Office of the University of British Columbia.
• ² Scena Cluj Napoca a statuii Sf. Gheorghe a fost pusă la dispoziție de către Dl. arhitect Dan Clinci (Cluj Napoca).
• ³ Imaginile scenelor prezente au fost luate în cadrul ediției 2011 a seminariilor Geo-Spațial.org din București.