Conducător științific : Prof. dr. ing. Daniel Volovici Absolvent: Kadar Ioan-Alexandru Specializarea: CALCULATOARE Sibiu, 2019 – UNIVERSITATEA… [302226]

UNIVERSITATEA “LUCIAN BLAGA” DIN SIBIU

FACULTATEA DE INGINERIE

DEPARTAMENTUL DE CALCULATOARE ȘI INGINERIE ELECTRICĂ

PROIECT DE DIPLOMĂ

Conducător științific : Prof. dr. ing. Daniel Volovici

Absolvent: [anonimizat]:

CALCULATOARE

Sibiu, 2019 –

UNIVERSITATEA “LUCIAN BLAGA” DIN SIBIU

FACULTATEA DE INGINERIE

DEPARTAMENTUL DE CALCULATOARE ȘI INGINERIE ELECTRICĂ

3D MAPS OBȚINUTE DIN

IMAGINI 2D

Conducător științific : Prof. dr. ing. Daniel Volovici

Absolvent: [anonimizat]:

[anonimizat] o combinație de stimuli pe care ființele umane le interpretează cu ajutorul simțurilor (vizual, auditiv, olfactiv, gustativ și tactil), acestea reprezintă o legătură strânsă între sistemul senzorial și percepția fiziologică a organismului uman.

În urma achiziției informațiilor cu ajutorul simțurilor (acțiunea de a vedea, acțiunea de a auzi), [anonimizat] a [anonimizat].

Este cunoscut faptul că ființa umană are tendința de a [anonimizat] a reproduce cu succes părți ale corpului uman sau modele de funcționare a corpului uman ([anonimizat].). Acest lucru a devenit mult mai accesibil și mai abordabil odată cu evoluția și dezvoltarea tehnologiei.

[anonimizat], [anonimizat] a putea înțelege mai ușor cum funcționează și pentru a lua, [anonimizat].

O ramură bine dezvoltată și încă în curs de dezvoltare este cea a procesării imaginilor.

[anonimizat], este împărțită în două nivele și anume procesarea la nivel scăzut și procesarea la nivel ridicat.

[anonimizat], [anonimizat], fără a ține seamă prea mult conținutul imaginilor ([anonimizat]).

În procesarea de nivel înalt se folosesc însă diferiți algoritmi pentru a [anonimizat].

Pentru a “copia” modul de vedere al omului și pentru observarea lumii reale avem nevoie de informație 3D, dar este cunoscut faptul că într-o [anonimizat].

Pentru a rezolva această problemă se folosește combinarea a două sau mai multe imagini provenite de la două sau mai multe camere de fotografiat plasate în puncte diferite în spațiu (în general la distanțe mici una de cealaltă), [anonimizat].

[anonimizat], robotica și chiar și în jocuri. [anonimizat] a stereoviziunii, deoarece corectitudinea informațiilor depinde de factori precum calitatea camerelor, unghiurile din care se capturează imaginile și multe altele.

Însă, datorită progreselor remarcabile ale tehnologiei, calitatea camerelor și a imaginilor obținute s-au îmbunătățit considerabil, astfel încât acest factor nu mai poate fi considerat o problemă importantă.

Imaginile obținute pot fi bruiate de zgomot sau interferențe din partea mai multor surse, inclusiv a zgomotului senzorilor electronici. Există mulți algoritmi de curățare a zgomotului, cei mai cunoscuți fiind filtrarea homomorfă, filtrarea folosind un filtru median sau un filtru pseudomedian.

Așadar, înainte de începerea extragerii informațiilor este indicată aplicarea unui algoritm de curățare al zgomotului.

În cadrul stereoviziunii apare fenomenul de disparitate, fenomen provocat de faptul că cele două sau mai multe camere sunt distanțate și imaginile sunt puțin deplasate una față de cealaltă. Disparitatea poate fi calculată prin mai multe metode, acestea au scopul de a găsi potrivirea dintre doi pixeli sau două regiuni din imagini diferite.

Pentru a simplifica procesul, considerăm constrângerea locală ca fiind o matrice pătratică de pixeli de dimensiunea 3×3 sau 5×5 în care pixelul central este pixelul de interes, iar constrângerea globală ca fiind un număr de pixeli de pe linia de scanare sau în unele cazuri întreaga imagine.

Metodele globale ale stereoviziunii oferă rezultate superioare celor locale, însă necesită timp mai îndelungat de procesare deoarece sunt mai multe calcule de executat.

Metodele locale, însă, oferă rezultate mai slabe decât metodele globale, avantajul major al acestora fiind timpul mai scurt de calcul, iar dezavantajul fiind sensibilitatea la regiunile locale ambigue, cum ar fi regiunile cu textură uniformă.

Din clasa metodelor locale fac parte algoritmi precum cel de block matching sau gradient-based optimization.

Pentru a putea procesa imaginile stereo, e nevoie să parcurgem anumite etape, așadar, după ce se efectuează curățarea de zgomot, se trece la etapa de rectificare, apoi urmează etapa de potrivire urmând ca la final să rămână etapa de găsire a profunzimii și reconstrucție a imaginii 3D.

În etapa de rectificare se transformă imaginile de intrare, astfel încât liniile epipolare să fie orizontale și paralele. Linia epipolară pentru două imagini (imagine camera stângă, imagine camera dreaptă) reprezintă locul geometric al corespondentului pixelului PR, dacă se dă un punct în imaginea stângă pixelul PL.

În etapa de potrivire, corespondența unui punct dat dintr-o imagine trebuie căutată în cea de-a doua imagine, de-a lungul liniei epipolare. Căutarea corespondenței necesită mult timp de procesare deoarece sunt necesare comparări între pixeli. În urma etapei de rectificare se compară pixelii de-a lungul liniei de scanare, singura diferență fiind cea de deplasament.

În ultima etapă, cea de găsire a profunzimii, se calculează coordonatele 3D ale punctului reconstituit în sistemul de coordonate al camerei/lumii, iar apoi urmează reconstrucția imaginii 3D și afișarea acesteia.

Sistemul de captare al imaginilor necesită două sau mai multe camere sau folosirea unei singure camere cu un sistem complex de oglinzi. Indiferent de metoda aleasă, este necesară calibrarea camerelor și declanșarea lor simultană.

În această lucrare se utilizează perechi de câte două imagini ale porțiunilor de pe harta pământului preluate de la “Jet Propulsion Laboratory, California Institute of Technology” realizate cu ajutorul camerelor stereo amplasate pe sateliții folosiți de NASA.

Scopul lucrării este de a genera hărți 3D din imagini 2D.

Aplicația atașată acestei lucrări realizează prelucrări succesive asupra celor două imagini de intrare (curățare a zgomotului, etapele procesării stereo) pentru ca la final să se obțină și să se afișeze un model 3D (o hartă 3D).

Considerații teoretice

Istoric

Un domeniu bine dezvoltat și care evoluează în continuare foarte rapid este cel al procesării imaginilor, a cărei aplicații se găsesc pretutindeni, inclusiv în domenii precum medicină, robotică și chiar și industrie.

Fie că vorbim de urmărirea unei linii pentru a trasa sau a tăia materialele, fie ne referim la roboți care urmăresc să recunoască gesturile oamenilor, expresiile faciale ale acestora sau semnele de circulație pentru a putea lua deciziile cele mai bune ori fie urmărim să scanăm și să reconstituim 3D diferite obiecte pentru a le putea modifica ulterior cu diferite programe pe calculator, procesarea imaginilor are o importanță majoră în dezvoltarea tehnologiei și a sistemelor bazate pe luare de decizii.

Încă de la începutul dezvoltării acestui domeniu, reconstrucția 3D a imaginilor a reprezentat o problemă, deoarece imaginilor le lipsește informația de profunzime.

Însă, în decursul anilor au apărut numeroase soluții care rezolvă această problemă, una din soluțiile propuse fiind stereoviziunea.

Stereoviziunea presupune combinarea a două sau mai multe imagini pentru a reconstitui coordonatele 3D a fiecărui pixel al imaginii, obținând astfel modelul 3D.

Pentru a capta imaginile, în stereoviziune, se folosesc camere speciale, formate din două sau mai multe aparate de fotografiat, configurate identic și declanșate simultan pentru a obține imaginile dorite din mai multe poziții, ușor depărtate.

Primele astfel de aparate fotografice au apărut după anii 1950 și au suferit pe parcurs, evoluții remarcabile, ajungând la performanțe impresionante. Însă interesele pentru acest domeniu au fost prezente încă din 1850, iar prototipuri ale acestor aparate de fotografiat stereo fiind cunoscute încă din anii 1870.

Pentru stereoviziune există mulți algoritmi disponibili, care folosesc fie constrângeri locale fie constrângeri globale, dar nu există un algoritm optim și general și de fiecare dată când trebuie aplicat un astfel de algoritm, trebuie să se facă un compromis între acuratețea rezultatelor și timpul de procesare al informațiilor.

Achiziția imaginilor

Pentru a captura un fragment din realitate se folosesc anumite dispozitive care imortalizează momentele și le transformă în fișiere care pot fi stocate, prelucrate și redate pe dispozitive care dispun de sisteme de afișare.

Aceste dispozitive au nevoie de două componente pentru a putea reuși să captureze imaginile. Prima componentă necesară este un senzor sensibil într-o anumită gamă a spectrului energetic electromagnetic, cum ar fi spectrul vizibil, ultraviolet sau cel al razelor x.

A doua componentă este un dispozitiv numit digitizor care are rolul să convertească semnalul electric analogic produs de prima componentă, adică de senzor, într-un semnal digital.

În stereoviziune, dispozitivul de captare al imaginilor este format în general din două camere, configurate identic și declanșate în același moment de timp, în caz contrar imaginile obținute nu ar produce rezultatele așteptate.

Figura 1 – Cameră de fotografiat stereo

Figura 2 – Cameră de fotografiat stereo

În locul celor două camere, se poate folosi și o singură cameră cu un sistem de oglinzi, dar în cazul acesta sunt necesare calcule minuțioase pentru a configura geometria oglinzilor.

Figura 3 – Cameră de fotografiat stereo cu sistem de oglinzi

Tipuri de formate grafice

Imaginile captate de aparatele de fotografiat, camerele de fotografiat ale dispozitivelor, sunt stocate în memoria calculatorului sub forma unor fișiere cu diferite extensii, care conțin anumite informații despre imaginile respective.

Dimensiunea unei imagini este dată de numărul pixelilor și de dimensiunea pe care este salvată informația pentru fiecare pixel.

Să presupunem că o imagine are dimensiunea de 640 x 480 pixeli, iar pentru fiecare pixel informația e stocată pe 24 de biți.

(2.3.1)

Așadar, o astfel de imagine ocupă aproape un megabyte ca și spațiu de stocare.

În momentul actual, problema stocării reprezintă doar o mică piedică, deoarece există multe posibilități și dispozitive fizice destinate stocării (card microSD, HDD, SSD) cât și dispozitive online deținute de companii precum Google (Google Drive), unde pot fi stocate informațiile.

Principalele tipuri de formate grafice sunt BMP, JPEG și PNG.

Formatul BMP poate fi numit și fișier imagine Bitmap și este utilizat pentru a stoca imaginile digitale independent de dispozitivul de afișare în special pentru sistemele de operare Microsoft Windows.

Acest format de fișier grafic permite stocarea imaginilor digitale bidimensionale de mărimi diferite (lățime, înălțime și rezoluție variabilă), monocrome sau color, iar un astfel de fișier este alcătuit dintr-un header de recunoaștere a formatului (BITMAPFILEHEADER), un header cu informații referitoare la imagine (BITMAPINFOHEADER), o tabelă de culori (RGBQUAD) și un șir de octeți care reprezintă informația propriu-zisă existentă la nivelul pixelilor din imagine (biWidth – lățimea imaginii, biHeight – înălțimea imaginii, biCompression – tipul de compresie folosit, biClrUsed – numărul culorilor folosite).

Formatul grafic JPEG (Joint Photographic Experts Group) are scopul de a reduce dimensiunile fișierelor ce conțin imagini grafice de tip fotografic și cu un număr mare de culori fără a afecta calitatea imaginii. În general fișierele care conțin imagini compresate cu această metodă poartă extensia “.jpg”.

PNG (Portable Network Graphics) a fost dezvoltat ca un înlocuitor îmbunătățit al formatului GIF (Graphics Interchange Format), dar nu suportă animații.

Îmbunătățirea imaginilor

Pentru a reduce timpul de procesare, putem transforma imaginile dintr-un spectru

color în nivele de gri, astfel, în loc să efectuăm câte trei calcule pentru fiecare pixel (pentru fiecare nivel în parte – roșu, verde, albastru) vom avea nevoie de un singur calcul (pentru nivelul de luminanță).

În urma acestei conversii, fiecare pixel va avea o valoare cuprinsă în intervalul 0-255 (fiecare nivel al componentelor RGB este codificat în valori din intervalul 0-255) în funcție de metoda aleasă. Arpad Gellert și Remus Brad[1] propun următoarea metodă de aflare a intensități comună a celor trei componente RGB:

(2.4.1)

Figura 4 – Transformarea imaginii în grayscale

După transformarea imaginilor în format grayscale, putem aplica anumite metode de curățare a zgomotului.

Remus Brad[9] afirmă că imaginile pot fi bruiate de zgomote sau interferențe din partea mai multor surse, inclusiv zgomotul senzorilor electronici și zgomotul granulelor fotografice. Zgomotul se manifestă de cele mai multe ori ca fiind variații la nivelul pixelilor, necorelați spațial, acest lucru putând fi ușor observat vizual atunci când apar pixeli diferiți de vecinii lor. Pe urma acestei observații, au fost dezvoltate mai multe metode de curățare a zgomotului, metode care oferă rezultate satisfăcătoare.

Putem împărți aceste metode de curățare a zgomotului în trei categorii, și anume:

Metode liniare

Metode neliniare

Metode adaptive

Metode liniare de curățare a zgomotului

Zgomotul care apare în imagine are un spectru mai larg de frecvență decât componentele normale ale imaginii datorită decorelării spațiale. Remus Brad[9] susține că o filtrare “trece-jos” simplă poate fi eficientă în îndepărtarea zgomotului.

Așadar, o primă metodă liniară de îndepărtare a zgomotului este procesarea în domeniul spațial, care presupune convoluția imaginii originale cu o matrice răspuns la semnal de tip impuls, adică aplicarea unei măști de tip matrice de dimensiunea NxN, în care toate elementele sunt pozitive, iar pentru a nu introduce schimbări de amplitudine în imaginea rezultată este necesară o normalizare la unitate.

Dimensiunea matricei reprezintă numărul de pixeli vecini luați în considerare pentru operația de convoluție. Cu cât dimensiunea filtrului crește, cu atât se obține o îndepărtare mai eficientă a zgomotului, dar există riscul de a pierde detalii.

Forma generală a unui filtru “trece-jos” de dimensiune 3×3 este:

(2.4.2)

Filtrarea homomorfă reprezintă o altă metodă de curățare liniară a zgomotului.

Aceasta presupune că imaginea de intrare (ImgIn) este produsul dintre o imagine fără zgomot (ImgClean) și o matrice de interferență a iluminării (InterfIlum) (2.4.3) și care se calculează logaritmând ecuația (2.4.3) la care, apoi se aplică tehnici de filtrare liniară neconvențională pentru eliminarea componentei logaritmice.

(2.4.3)

O a treia metodă de curățare liniară a zgomotului este cea care folosește procesarea Fourier. Considerăm că avem o imagine binară, de dimensiune NxN și o frecvență de tăiere a filtrului notată cu C, atunci se folosesc următoarele funcții de transfer:

(2.4.4)

(2.4.5)

pentru:

(2.4.6)

(2.4.7)

Și pentru restul cazurilor.

Metode neliniare de curățare a zgomotului

În comparație cu metodele liniare, cele neliniare oferă o echilibrare mai bună între eliminarea zgomotului și păstrarea detaliilor din imagini.

Există mai mulți algoritmi de curățare neliniară a zgomotului, dar în cele ce urmează se vor detalia doar cei mai eficienți și mai cunoscuți precum tehnica Outlier, filtrarea mediană sau filtrarea pseudomediană.

Tehnica Outlier presupune compararea fiecărui pixel cu media celor opt pixeli vecini, iar în cazul în care această diferență depășește o anumită valoare de prag, atunci pixelul respectiv este considerat zgomot și valoarea acestuia se înlocuiește cu valoarea mediei celor opt pixeli vecini ai săi(2.2.8). Bineînțeles, această tehnică poate fi extinsă și la un număr mai mare de vecini (matrice 3×3 – 8 vecini, matrice 4×4 – 16 vecini etc) dar, odată cu creșterea numărului de vecini crește și timpul de execuție, iar imaginea va deveni mai netezită.

(2.4.8)

Următoarea metodă de curățare a zgomotului despre care se va discuta în cele ce urmează, este filtrarea mediană propusă și dezvoltată de Tukey. Aceasta poate fi implementată prin două variante – filtru median unidimensional și filtru median bidimensional.

Filtrul median unidimensional folosește o fereastră formată dintr-un număr impar de pixeli învecinați, de cele mai multe ori formată din trei sau cinci pixeli, în care pixelul aflat în centrul ferestrei este înlocuit cu medianul pixelilor din fereastra respectivă.

Să considerăm că se aplică un filtru median unidimensional cu o fereastră de cinci pixeli învecinați (a, b, c, d, e). Cu ajutorul formulei (2.4.9) se poate calcula valoarea pixelului din centrul ferestrei după cum urmează:

(2.4.9)

Varianta filtrului median bidimensional oferă o suprimare superioară a zgomotului față de cea a filtrului median unidimensional și folosește o fereastră dreptunghiulară sau în formă de cerc discretizat.

Ultima metodă neliniară de curățare a zgomotului este filtrarea pseudomediană, iar Pratt a propus această metodă ca și o alternativă la filtrul median, care necesită un volum mare de calcule. Metoda elimină atât zgomotul de tip impuls de culoare deschisă cât și pe cel de culoare închisă (zgomot de tip “sare și piper”).

Mai exact, operatorul MAXIMIN îndepărtează zgomotul de tip impuls de culoare deschisă, însă nu are efect asupra zgomotului de tip impuls de culoare închisă, pe când operatorul MINIMAX îndepărtează zgomotul de culoare închisă fără a avea vreun efect asupra celui de culoare deschisă.

Dacă se aplică un filtru pseudomedian, ca și în cazul anterior la filtrul median, pentru o fereastră de 5 pixeli (a, b, c, d, e), formula de calcul pentru valoarea pixelului central este:

(2.4.10)

Sau

(2.4.11)

Această formulă poate fi generalizată astfel:

Avem un șir de elemente , atunci pseudomedianul este:

(2.4.12)

(2.4.13)

(2.4.14)

Asemenea filtrului median, și cel pseudomedian poate fi extins la ferestre bidimensionale, însă și în acest caz, această modalitate tinde să netezească imaginea, chiar dacă oferă rezultate mai bune.

Considerăm un filtru pseudomedian bidimensional în formă de “+” (Figura 5) de dimensiune 5×5, care conține următoarele:

– șirul de pixeli din fereastră aflați pe orizontală – (a, b, c, d ,e)

– șirul de pixeli din fereastră aflați pe verticală – (f, g, c, h, j)

– elementul comun celor două șiruri (pixelul central) – (c)

Figura 5 – Filtru pseudomedian bidimensional în formă de “+”

În cazul de față, pseudomedianul este:

(2.4.15)

Metode adaptive de curățare a zgomotului

În această categorie de metode de curățare a zgomotului se folosesc algoritmi care au ca scop minimizarea erorii medii pătratice sau algoritmi care aparțin domeniului rețelelor neuronale având scopul de a oferi o comportare adaptivă a filtrelor mediane.

Unele filtrări pot avea efecte destructive asupra imaginilor, iar în acest scop au fost introduși algoritmi adaptivi și aplicați unor filtre de tip “trece-jos” sau algoritmi bazați pe media ponderată a pixelilor vecini.

Odată cu alegerea unei metode adaptive care să nu deterioreze imaginea, crește însă și timpul necesar de procesare datorita volumului mare de calcule.

Stereoviziune

Ființele umane preiau imaginile din lumea reală prin intermediul ochilor, urmând ca mai apoi informațiile să ajungă la creier, care va analiza și va lua deciziile cele mai bune drept răspuns pentru imaginile respective. Ochii sunt poziționați la o distanță mică unul de celălalt, iar din acest motiv imaginile preluate și transmise mai departe sunt diferite. Odată ajunse la creier, aceste imagini sunt combinate în una singură în care apare și informația de profunzime, obținându-se astfel modelul 3D. Antrenând creierul cu această capacitate de a combina imaginile, se ajunge la performanța de a crea modelul 3D chiar și prin intermediul imaginilor preluate de un singur ochi, datorită capacității creierului de a memora informațiile combinărilor anterioare ale imaginilor. Bineînțeles, creierul poate fi “păcălit” prin diverse metode, cum ar fi imagini 2D care conțin umbre, iluminări sau texturi pe care acesta le percepe ca fiind modele 3D. Acestea se numesc iluzii optice și sunt folosite în diverse domenii, în special in domeniul jocurilor.

Încă din anii ’70, stereoviziunea a reprezentat un domeniu major de interes, iar primii care și-au centrat cercetările pe fundamentele reconstrucției stereo au fost Barnard și Fischer[4], care s-au ocupat de criterii de evaluare a performanțelor și trecerea în revistă a informațiilor deja cunoscute.

După anii ’80, cercetările în stereoviziune au avansat în mod signifiant datorită lui Dhond și Aggarwal[5] care au venit cu noi metode de matching, precum și o serie de constrângeri care prevăd reducerea ambiguității stereo.

Cel mai mare punct de interes în cercetările acestui domeniu îl reprezentau algoritmii de stereo matching.

Principala limitare în dezvoltarea algoritmilor stereo a fost performanța sistemelor de calcul, dar, odată cu progresele remarcabile ale tehnologiei a fost posibilă continuarea dezvoltării și îmbunătățirii acestor algoritmi precum și a reconstrucției stereo.

După cum am precizat și în introducere, acest domeniu permite implementarea algoritmilor stereo folosind mai multe camere, iar cu detalii despre asta (informații asupra aspectelor geometrice care implică folosirea mai multor camere) au venit Hartley și Zisserman[7] alături de Faugeras și Luong[6].

Găsirea unui algoritm optim care să rezolve problema stereo-corespondenței depinde foarte mult de locul unde trebuie aplicat și de modul în care este folosit acesta. Putem exemplifica afirmația anterioară prin punerea în paralel a doi roboți.

Unul care își desfășoară activitățile într-un mediu controlat(condiții de iluminare constante, obiecte cu o geometrie simplă) ca de exemplu într-o fabrică, iar celălalt își desfășoară activitățile într-un mediu deschis, predispus condițiilor extreme, ca de exemplu pe suprafața unei planete. Evident, programarea primului robot cu un algoritm care oferă rezultate satisfăcătoare mediului respectiv ar fi mult mai puțin costisitoare decât programarea celui de-al doilea robot în care trebuie să se țină cont de o mulțime de factori, care pot interveni în orice moment și pot influența rezultatele.

Revenind la algoritmii stereo, am arătat că aceștia se pot împărți în trei etape:

Rectificarea

Potrivirea

Găsirea profunzimii

Rectificarea este crucială deoarece prin intermediul ei se simplifică procesul de stereo matching. Metodele de implementare a acestei etape se pot împărți în două categorii:

Metode care presupun că s-a făcut calibrarea camerelor

Metode care presupun că nu s-a făcut calibrarea camerelor

O teorie elegantă, alături de care vine o metodă practică de rectificare a fost prezentată în anul 1993 de către Hartley și Gupa, care merge pe ideea găsirii a două transformări omografice care pot alinia corect configurația geometrică și totodată pe ideea minimizării distorsiunilor în timpul transformării.

Metodele care presupun că nu s-a făcut o calibrare a camerelor sunt mai greu de aplicat în cazul sistemelor multioculare, adică a sistemelor formate din mai mult de două camere de fotografiat.

Un algoritm simplu care se bazează pe faptul că axele camerelor rectificate sunt paralele și perpendiculare pe linia de bază a fost propus în anul 2000 de către Fusiello.

Acest sistem de rectificare se bazează pe trei reguli în care noile axe X, Y și Z vor avea alte coordonate, și anume:

Noua axă X este paralelă cu linia de bază

Noua axă Y este ortogonală cu axa X

Noua axă Z este ortogonală cu planul X-Y

Rectificarea se face astfel încât orientarea fiecărei camere să coincidă cu noul sistem de axe X-Y-Z.

Metodele de rectificare au fost gândite pentru cazurile în care sunt folosite sisteme formate din două camere, dar pot fi aplicate și pentru cazurile în care se folosesc sisteme multioculare, prin anumite operații suplimentare.

După ce etapa de rectificare este încheiată, se trece la etapa a doua, adică la cea a potrivirii în care se caută pentru fiecare pixel dintr-o imagine, pixelul corespondent din celelalte imagini de-a lungul liniei epipolare, operație care necesită multe calcule și care impune un timp de procesare îndelungat.

În ultima etapă, cea a găsirii profunzimii, se calculează coordonatele 3D (x,y,z) ale punctelor reconstituite cu ajutorul formulelor stereoviziunii.

Camera fotografică în stereoviziune

Sistemul de captare a imaginilor în stereoviziune este format din două sau mai multe camere de fotografiat situate la distanțe apropiate unele față de celelalte (după modelul ochilor ființelor umane), configurate identic și declanșate simultan.

În reconstrucția 3D, foarte des se folosește ca și model de referință cel al camerei fotografice. (unde f – distanța focală)

Figura 6 – Geometria camerei fotografice

Figura 7 – Geometria camerei fotografice

Avem așadar formulele:

(2.5.1)

(2.5.2)

(2.5.3)

Asemănător modelului camerei fotografice, se prezintă în continuare modelul stereo format din două camere paralele:

Figura 8 – Geometria camerei fotografice stereo

(2.5.4)

(2.5.5)

Să presupunem că avem două imagini (Img1 și Img2) care capturează două puncte ale unui obiect P și Q (Figura 9).

Figura 9 – Geometria camerei stereo

Dacă punctul p corespunde cu q’ și q corespunde cu p’, atunci vom găsi corespondența de la P la P’ și de la Q la Q’.

Fiecare pixel dintr-o imagine poate avea sau nu un pixel corespondent în cealaltă imagine. În cazul în care un pixel nu are corespondență, atunci el va fi numit ”punct ocludat”, ceea ce înseamnă ca punctul respectiv va fi vizibil doar de o singură cameră. Însă, dacă există un pixel corespondent, atunci acel punct se poate localiza în spațiul 3D.

Dacă disparitatea dintre locațiile a doi pixeli este prea mare sau prea mică atunci punctele vor fi generate eronat pe axa optică. Dacă disparitatea este prea mică, punctele se vor genera prea departe de axa optică, iar dacă disparitatea este prea mare, atunci punctele vor fi generate prea aproape de axa optică.

În (figura 9) ne este exemplificată o disparitate între doi pixeli q și q’ mai mare decât cea existentă între pixelii p și p’.

Figura 10 – Disparitatea a doi pixeli

Segmentul care unește centrele optice (pentru camera stângă) și respectiv (pentru camera dreaptă) corespunzătoare celor două imagini este definit ca fiind baseline-ul unei perechi de imagini, iar adâncimea unui punct P cu proiecție pe cele două centre optice este definită ca fiind intersecția razelor care trec prin centrele optice, respectiv imaginile P, p și p’.

Disparitatea este notată cu d (d = x-x’) , distanța dintre cele două camere ( și adică baseline-ul) este notată cu T, iar distanța de la centrul optic până la planul imaginii cu f (distanță focală). Formula de calcul pentru aflarea profunzimii este atunci:

(2.5.6)

Din formula 2.5.6 putem deduce că adâncimea și disparitatea sunt invers proporționale.

Acest proces se numește triangulare și presupune determinarea a două drepte care trec prin centrul de proiecție și imaginea punctului ce aparține obiectului.

Dacă cele două camere ale sistemului de captare al imaginilor nu sunt paralele, atunci intervine un proces secundar numit rectificare, deoarece punctele pot fi captate în moduri diferite, la fel ca în figura 11.

Figura 11 – Captarea punctelor în mai multe moduri

Procesul care stă în spatele stabilirii potrivirii dintre două puncte în cadrul a două imagini se numește corespondența. Când vine vorba de operația de găsire a corespondențelor, constrângerile epipolare lasă impresia că pixelul corespondent este căutat în întreaga imagine, pe când acesta este căutat doar pe o linie.

Această linie este numită linie epipolară și reprezintă linia care unește planul epipolar cu planul imaginii, iar aceasta intersectează epipolii.

În figura 11, planul format din baseline-ul T și razele optice respectiv se mai numește și plan epipolar. Liniile epipolare care trec prin punctele p respectiv p’ se află în opoziție.

Punctele e și e’ se numesc epipoli, adică puncte în care liniile epipolare intersectează baseline-ul. Pentru calculul profunzimii ne folosim de geometria epipolară, iar prin constrângeri geometrice, informațiile de profunzime vor fi date sub formă matriceală, matricea respectivă fiind numită matrice esențială, pentru mediul calibrat iar pentru mediul necalibrat informațiile vor fi reținute tot în formă matriceală, de această dată fiind numită matrice fundamentală.

Putem descrie coordonatele camerelor prin operațiile de translație (T) și rotație(R).

(2.5.7)

Figura 12 – Geometrie epipolară

Figura 13 – Geometrie epipolară

Notând vectorul produs cu T și scalarul produs cu x’:

(2.5.8)

Ecuație care reprezintă întocmai ecuația algebrică a geometriei epipolare în cazul calibrat, iar din această formulă reiese că:

Expresia (2.3.8) mai poate fi scrisă și astfel:

(2.5.9a)

În cazul necalibrat R și T nu se cunosc și tot ceea ce știm sunt coordonatele în plan ale imaginii. Astfel, presupunem că avem două vederi ale punctului M din figura 13, aparține primei vederi, iar celei de-a doua.

(2.5.10)

(2.5.11)

Unde P și P’ sunt matricele de proiecție.

Coordonatele centrelor optice O și O’ se obțin prin rezolvarea a două sisteme liniare

(2.5.12)

(2.5.13)

Ecuația o putem rescrie ca .

Astfel, având un punct din prima vedere, linia epipolară corespunzătoare lm poate fi calculată cu ajutorul a două puncte și anume unul din cei doi epipoli (ecuația – 2.5.14) și celălalt care este punctul de la infinit în care raza optică se intersectează cu centrul optic O și punctul m (ecuația – 2.5.15).

(2.5.14)

(2.5.15)

Știind cele două puncte, putem defini linia epipolară astfel:

(2.5.16)

Relația 2.3.16 poate fi scrisă ca , unde F este o matrice de 3×3 calculată în felul următor:

matricea fundamentală (2.5.17)

Dacă ne referim la spațiul Euclidian, punctele imaginii și razele sunt definite astfel:

(2.5.18)

Și

(2.5.19)

Dacă este punctul corespondent, atunci:

(2.5.20)

Dacă sistemul este calibrat, relația dintre matricea esențială și cea fundamentală este ușor de definit:

(2.5.21)

Proprietățile celor două matrice (esențială și fundamentală) sunt:

Matricea fundamentală încapsulează și parametrii intrinseci și cei extrinseci ai camerei, pe când matricea esențială doar parametrii extrinseci

Matricea esențială are 3 grade de libertate

Matricea fundamentală are 7 grade de libertate

Disparitatea

Disparitatea reprezintă deplasamentul rezultat prin proiecția unui punct din prima imagine în raport cu un alt punct din a doua imagine. Aceasta poate fi calculată doar pentru punctele vizibile în ambele imagini. Putem defini harta disparităților ca fiind mulțimea disparităților dintre două imagini.

Există foarte multe metode de a calcula disparitatea, fiecare din aceste metode având rolul de a găsi potrivirea dintre doi pixeli aflați în imagini diferite.

În continuare, vom considera ca fiind constrângere locală un număr mic de pixeli din jurul unui pixel central numit pixel de interes și constrângere globală un număr de pixeli de pe linia de scanare sau chiar întreaga imagine.

Metodele care folosesc constrângerea locală sunt foarte sensibile la zonele ambigue (cum ar fi zonele cu texturi uniforme) însă sunt în general foarte eficiente, pe când metodele care folosesc constrângeri globale oferă rezultate mai bune, având dezavantajul unui timp de procesare îndelungat datorită numeroaselor calcule.

Cele mai cunoscute și utilizate metode care se folosesc de constrângeri locale sunt algoritmi din clasa block matching și din clasa gradient-based optimization, iar din partea metodelor care se folosesc de constrângeri globale avem algoritmi precum graph cuts, nonlinear diffusion și dynamic programming.

În cele ce urmează, o să ne îndreptăm atenția spre o categorie de algoritmi care folosesc constrângeri locale și care au fost predați și explicați inclusiv în cursul de Procesare a Imaginilor și Computer Vision, curs ținut de Prof. univ. dr. ing. Remus Brad în anul de studiu IV, semestrul I al Facultății de Inginerie, ULBS.

Clasa de algoritmi la care ne referim este cea a algoritmilor de block matching.

În această clasă avem cele mai cunoscute metode de căutare a similarității dintre două imagini. Algoritmii cei mai utilizați au la bază fie suma pătratelor diferențelor (Sum of Square Differences – SSD), fie suma diferențelor absolute (Sum of Absolute Differences – SAD) fie metode statistice standard pentru determinarea similaritățiilor (Normalized Cross-Correlation – NCC). În cele ce urmează, vor fi detaliați acești algoritmi, iar apoi ne vom opri atenția asupra algoritmului folosit în aplicația din această lucrare, și anume Matching Pixel Count – MPC.

Presupunem pentru început două imagini S și D capturate de o cameră de fotografiat stereo (S – imaginea captată de obiectivul stâng al aparatului, D – imaginea captată de obiectivul drept al aparatului).

Un punct de pe imagine S poate fi localizat prin intermediul parametrilor (i, j) (i – rândul și j – coloana), iar pentru imaginea D un punct poate fi localizat prin intermediul parametrilor (u, v) (u – rândul și v – coloana). Disparitatea dintre imaginea stângă S și imaginea dreaptă D este notată cu d (di – rândul, dj – coloana).

În cazul sumei pătratelor diferențelor (SSD), fixăm o fereastră de dimensiuni mici în jurul unui punct dintr-o imagine și căutăm în a doua imagine fereastra cea mai apropiată ca și asemănare. Algoritmul se aplică pentru fiecare punct din imagine. Diferența dintre două regiuni reprezintă suma pătratelor diferențelor intensităților pentru fiecare punct din imaginile stânga S și dreapta D. Considerând fereastra de dimensiune NxN atunci:

(2.5.22)

În cazul sumei absolute a diferențelor, pentru aceeași fereastră de dimensiune NxN, avem:

(2.5.23)

Când vorbim despre Normalized Cross-Correlation, se folosește o normalizare, care face ca algoritmul să fie insensibil la erorile de măsură:

(2.5.24)

Matching Pixel Count sau pe scurt MPC este o metodă care folosește constrângeri locale, nu foarte utilizată, cu o complexitate destul de scăzută și care oferă rezultate asemănătoare cu cele ale sumei pătratelor diferențelor.

B Kasi Viswanatha Reddy supervizat de Prof Sukadev Meher[2] prezintă acest algoritm în teza de masterat intitulată FAST BLOCK MATCHING MOTION ESTIMATION ALGORITHMS FOR VIDEO COMPRESSION și susțin că pixelii din fereastra unei imagini sunt comparați cu pixelii corespondenți din block-ul cu deplasament în cadrul de referință, iar dacă această diferență depășește o anumită valoare de prag, atunci pixelii sunt marcați ca fiind pixeli potriviți și sunt adunați la suma corespunzătoare acelei ferestre.

Așadar, și în acest caz se lucrează cu ferestre, iar dimensiunea acestora este variabilă și setată de utilizator pentru imaginea din stânga, iar apoi se caută în imaginea din dreapta, cea mai bună fereastră din punct de vedere al asemănării. Căutarea se face pe aceeași linie în ambele imagini, iar linia este dată de pixelul central al ferestrei. Se alege apoi o plajă de valori în care fereastra din imaginea dreaptă D se deplasează față de cea din stânga S. Fereastra din imaginea dreaptă se va deplasa de la poziția până la poziția , unde deplasamentul, iar x – coordonata pe axa X a pixelului central din fereastra de referință. Totalitatea acestor deplasări va forma o fereastră mai mare din punct de vedere al coloanelor, dar cu același număr de linii.

Dacă diferența absolută dintre doi pixeli cu aceeași poziție este mai mică decât o anumită valoare de prag, atunci la suma corespunzătoare ferestrei respective se va adăuga valoarea 1, astfel se va adăuga 0.

(2.5.25)

(2.5.26)

(2.5.27)

După ce s-a parcurs imaginea de căutare, trebuie să se emită disparitatea corespunzătoare pixelului care are coordonatele pixelului central al ferestrei de referință. Valoarea acestuia va fi dată de poziția în care suma corespunzătoare a fiecărei ferestre este cea mai mare.

Figura 14 – Imaginea de referință (template)

Figura 15 – Imaginea în care se caută template-ul (pe direcția stânga spre dreapta, cu o fereastră de căutare de aceeași dimensiuni ca și template-ul)

Pentru a elimina sensibilitățile se poate aplica o transformare locală non-parametrică pe imagini înainte de a se face potrivirea. O metodă de calcul a corespondenței care are la bază o astfel de transformare a fost propusă de Zabih și Woodfill[11] și utilizează așa numita transformare rank, care este definită ca fiind numărul de pixeli din regiunea respectivă care au intensități mai mici decât pixelul central.

Rezultatele se deosebesc astfel pe ordinea relativă a intensităților și nu pe intensitățile propriu-zise.

(2.5.28)

(2.5.29)

Dacă ne referim la Figura 14, atunci transformarea rank pentru fereastra (template-ul) respectivă ar returna:

Figura 16 – Exemplu transformare rank

Tot Zabih și Woodfill[11] mai propun o variațiune a transformări rank, numită transformare census și care păstrează distribuția spațială a rank-ului folosind o codare reținută într-un șir de biți potrivirea fiind calculată cu ajutorul distanței Hamming.

(2.5.30)

(2.5.31)

Pentru același template din Figura 10, transformarea census ar returna:

Figura 17– Exemplu transformare census

Cu mai multe detalii despre acești algoritmi și despre procesul de reconstrucție 3D, vin Yasutaka Furukawa și Carlos Hernandez[10], care oferă informații prețioase despre Multi-View Stereo.

Alte metode care folosesc constrângeri locale, pe lângă cele de block matching, sunt cele bazate pe gradient.

Acestea caută să determine disparitățile locale mici dintre două imagini cu ajutorul unei ecuații diferențiale în care intră mișcarea și strălucirea imaginii. Se presupune că translația unui punct este constantă în cele două imagini, iar translația orizontală a unui punct dintr-o imagine în alta este redată de o simplă ecuație diferențială:

(2.5.32)

Unde reprezintă componenta orizontală a gradientului imaginii, reprezintă derivata temporală (diferența intensității între imaginea stângă și cea dreaptă), iar este translația dintre cele două imagini.

Avem nevoie de constrângeri suplimentare pentru a obține rezultate mai bune, deci, presupunem că disparitățile diferă lin într-o fereastră de pixeli de mici dimensiuni, atunci disparitatea unui punct poate fi calculată folosind ecuația diferențială a sistemului liniar pentru fiecare pixel într-o fereastră de n pixeli și punctele .

(2.5.33)

Unde

(2.5.34)

În ceea ce privește metodele care folosesc constrângeri globale putem aminti de programarea dinamică (dynamic programming), în care Baker și Binford[3] alături de Ohta și Kanade[8] au rezolvat problemele de potrivire folosind contururile ca și primitive de bază.

Această metodă reprezintă o cale eficientă de minimizare/maximizare a funcțiilor care au un număr mare de variabile discrete. Totodată, această metodă presupune rezolvarea unei probleme complexe prin desfacerea ei într-o colecție de subprobleme și stocarea soluțiilor utilizând o structură de date bazată pe memorie. Fiecare dintre soluțiile subproblemelor este indexată pe valorile parametrilor de intrare, pentru a facilita căutarea acesteia. Iar de fiecare dată când subproblema respectivă se repetă, în loc să se recalculeze soluția, se caută pur și simplu în memorie. Tehnica aceasta se numește memoizare.

Indiferent de metoda de calcul aleasă pentru disparitate sau de tipul de constrângere utilizată, odată cu aflarea acesteia putem afla și distanța în planul Z până la obiect/obiecte și astfel, pe baza informațiilor cunoscute se poate construi modelul 3D al obiectului.

În concluzie, de cele mai multe ori, pentru a evita timpul mare de procesare a nenumăratelor calcule, suntem dispuși să acceptăm metode care folosesc constrângeri locale și a căror rezultate sunt mai puțin satisfăcătoare decât a metodelor care folosesc constrângeri globale, deși metodele care folosesc constrângeri locale au fost foarte bine optimizate și dezvoltate.

Rezolvarea temei de proiect

În acest capitol vor fi prezentate tehnologiile de programare utilizate și limbajul de programare ales pentru dezvoltarea aplicației cât și mediul de dezvoltare folosit.

Se vor detalia metodele aplicației și vor fi discutate și prezentate pe larg fragmente de cod, eventual imagini ale rezultatelor obținute în urma rulării metodelor respective.

Limbajul de programare C# (.NET Framework)

Microsoft .NET Framework reprezintă o colecție de clase care vin în ajutorul programatorilor și al dezvoltatorilor de software în special la scrierea aplicațiilor destinate diferitelor servicii (servicii WEB, aplicații Windows, aplicații WEB).

Conceput ca un concurent pentru limbajul de programare JAVA, C# a fost dezvoltat de către Microsoft la sfârșitul anilor 1990, fiind un limbaj orientat pe obiecte și derivat din limbajul C++.

Figura 18 – Exemplu cod C#

Multe firme importante au sprijinit și finanțat dezvoltarea acestui limbaj de programare, iar cele mai importante au fost Microsoft, Hewlett-Packard și Intel Corporation.

Pentru a încuraja și mai mult dezvoltarea limbajului C#, Microsoft a ajuns la acordul de a nu da în judecată dezvoltatorii open source pentru încălcarea brevetelor în proiectele non-profit.

Principalele scopuri ale dezvoltării acestui limbaj de programare au fost:

Necesitatea de a avea un limbaj simplu, modern și orientat pe obiecte

Se dorea ca limbajul și implementările acestuia să ofere suport pentru principiile de inginerie software, verificarea limitelor tablourilor (unidimensionale, bidimensionale etc), detectarea încercărilor de utilizare a variabilelor neinițializate, cu alte cuvinte, să trateze excepțiile.

Necesitatea pentru dezvoltarea de software destinate implementării în medii distribuite

Necesitatea portabilității codului sursă

Dorința de a avea un limbaj potrivit atât pentru dezvoltarea de aplicați pentru sisteme incorporate cât și pentru diferite aplicații destinate sistemului de operare, WEB-ului etc.

Fiind un limbaj de programare derivat din limbajul C++, putem compara și observa diferite avantaje ale acestui limbaj față de C sau C++, cele mai importante deosebiri fiind:

C# compilează codul în CLR (Common Language Runtime) pe când C++ compilează codul direct în cod mașină

C# rulează pe o mașina virtuală care se ocupă automat de gestionarea memoriei, iar C++ necesită o gestionare manuală a memoriei

C++ poate fi utilizat pe orice platformă/sistem de operare, iar C# este standardizat și rare ori folosit înafara sistemului de operare Windows

C++ poate crea aplicații de sine stătătoare, pe când în C# nu, dar putem dezvolta aplicații pentru Windows, console, aplicații pentru Android etc.

Probabil cel mai cunoscut criteriu de diferențiere, C++ folosește pointeri aproape peste tot pe când în C# nu se folosesc.

În figura 19 am exemplificat o aplicație simplă care afișează în consola textul ”Hello World” în limbajele de programare C, C++ și C#.

Figura 19 – Program care afișează în consolă mesajul “Hello World” în diferite limbaje de programare

Mediul de programare Microsoft Visual Studio

Microsoft Visual Studio include un set complet de instrumente de dezvoltare pentru generarea de aplicații ASP.NET, servicii WEB, XML, aplicații desktop și aplicații pentru smartphone-uri, tablete etc. Deci, putem spune că Microsoft Visual Studio este un IDE (Integrated Development Environment), adică un mediu de dezvoltare integrat.

Acesta folosește platforme de dezvoltare de software precum Windows API, Windows Forms sau Windows Store și include un editor de text ”dotat” cu IntelliSense care ajută la completarea codului și la redenumire (refactoring). Acest mediu de dezvoltare deține și un debugger integrat care poate fi folosit atât ca și source-level debugger cât și ca machine-level debugger.

Visual Studio suportă 36 de limbaje de programare, iar pentru cele mai multe din acestea există servicii de debugging și servicii la nivelul de editor de cod. Principalele limbaje de programare utilizate sunt:

C

C++

C#

Visual Basic .NET

JavaScript

XML

HTML

CSS

Python

Ruby

Node.js

Aproximativ odată la doi ani, Microsoft lansează noi versiuni de Visual Studio, care vine în mai multe ediții (Community, Enterprise, Professional).

Cea mai populară ediție este Microsoft Visual Studio Community, o ediție gratuită care vine sub sloganul ”Free, fully featured IDE for students, open-source and individual developers”, iar versiunea actuală suportată este Visual Studio 2019.

Pe lângă editorul de text integrat și debugger, Visual Studio mai pune la dispoziția dezvoltatorilor și un designer. Acesta dispune de mai multe tool-uri care simplifică munca celor care folosesc acest mediu de dezvoltare, atunci când vine vorba de crearea interfețelor grafice (GUI), design-ul claselor. Cele mai remarcate astfel de tool-uri sunt:

Windows Forms Designer – utilizat pentru crearea interfețelor grafice utilizând aplicații din categoria Windows Forms

Class Designer – utilizat pentru a avea o vizualizare mai detaliată a claselor (inclusiv al membrilor fiecărei clase și a tipurilor lor de acces)

Data Designer – utilizat pentru a edita in mod vizual baze de date, tabele etc.

Web Designer – website editor și designer care facilitează crearea paginilor WEB prin intermediul mecanismului de ”Drag and Drop” a widgeturilor.

Microsoft DirectX

Microsoft DirectX este o colecție de API-uri pentru controlul funcțiilor multimedia pe platformele Microsoft. Kitul de dezvoltare software (SDK) este alcătuit din biblioteci runtime în formă binară redistribuibilă, împreună cu documentația și anteturile care o însoțesc.

Cele mai utilizate versiuni de DirectX sunt:

DirectX 9 – apărut în 2002 pentru Windows 98 și Windows XP

DirectX 10 – utilizat pentru Windows Vista și următoarele versiuni ale sistemului de operare

DirectX 11

DirectX 12 – lansat în 20 martie 2014

Principalele API-uri(Application Programming Interface) sunt:

Direct3D

DirectDraw

DirectMusic

DirectInput

DirectPlay

DirectShow

DirectSound

Direct3D – rol în manipularea și vizualizarea obiectelor 3D, permițând dezvoltatorilor să folosească acceleratorul grafic al calculatorului

DirectDraw – reprezintă o interfață software care permite acces direct la resursele de vizualizare compatibile GDI

DirectSound – permite redarea sunetelor și controlul aplicațiilor asupra resurselor hardware disponibile

DirectMusic – furnizează împreună cu DirectSound o soluție completă pentru redarea de sunete și efecte sonore

DirectInput – permite aplicațiilor să primească date de la dispozitivele de intrare (tastatură, mouse, joystick) și furnizează suport pentru orice tip de dispozitiv de intrare

DirectPlay – API ce furnizează servicii de rețea la nivelul protocolului de rețea (o sesiune poate fi rulată pe TCP/IP, IPX)

DirectShow – o arhitectură pentru streaming-ul media pe platforme Windows. Permite capturări și redări la un nivel de calitate foarte bun pentru streamuri multimedia.

DirectX utilizează 3 matrice pentru control. Aceste matrice sunt View Matrix, World Matrix și Projection Matrix.

World Matrix este utilizat pentru a putea controla modelele 3D. Pentru fiecare operație care se dorește a fi făcută pentru modelul 3D (rotire față de o anumită axă, mărire, translație pe o anumită axă) se modifică această matrice în mod corespunzător astfel încât în urma funcției de rendering să rezulte operația dorită.

View Matrix este utilizat pentru a putea controla camera și caracteristicile acesteia.

Astfel se poate împărți în 3 componente:

LookAt – direcția de vedere a camerei (unde să vadă camera)

EyePosition – poziția camerei (de unde să vadă camera)

Up – un vector în care se setează care axă este utilizată pentru sus (în cazul multiplelor rotiri să se știe care e direcția sus, standard se folosește axa Y)

Projection Matrix este utilizat pentru a determina cum să se vadă modelele 3D (asemănător cu ce fel de lentilă să folosească o cameră pentru a vedea).

Pentru aplicația din această lucrare s-au folosit DirectDraw și Direct3d pentru a realiza și a afișa modelul 3D, iar pentru rotirea/translația acestuia s-a folosit DirectInput.

Descrierea metodelor utilizate în aplicație

Pentru dezvoltarea aplicației care să realizeze 3D maps din imagini 2D, am implementat diferite metode și diverși algoritmi care procesează imaginile de intrare, provenite de la camere de fotografiat stereo, determină și apoi afișează modelul 3D obținut.

Metodele utilizate vor fi detaliate în cele ce urmează, iar în capitolul următor va fi descrisă aplicația propriu-zisă, modul de lucru, etapele care duc la crearea modelului 3D și rezultatele obținute în urma rulării aplicației.

În continuare, vor fi prezentați pe larg pașii pentru realizarea aplicației.

Pentru început avem nevoie de imagini de test, imagini provenite de la camere de fotografiat stereo. Pentru aplicația din această lucrare se folosesc imagini ale diferitelor zone ale Pământului, captate de către sateliți ai NASA și descărcate de pe site-ul oficial al NASA.

Apoi urmează încărcarea imaginilor în cadrul aplicației și transformarea acestora în format Grayscale, pentru a reduce timpul de procesare de trei ori și pentru a simplifica toate calculele necesare. (În format RGB sunt necesare calcule complexe dacă dorim să implementăm anumiți algoritmi).

Pentru a continua, este necesară o filtrare care să netezească imaginea și să accentueze contururile, operații care vor fi de folos în momentul în care se va aplica algoritmul stereo matching.

Metodele de mai sus se vor aplica pentru fiecare imagine în parte, fără a avea dependențe una față de cealaltă.

După ce se termină netezirea imaginii și accentuarea contururilor, urmează aplicarea algoritmului stereo, care calculează disparitatea și găsește corespondența între pixelii din imagini.

Algoritmul stereo poate produce rezultate afectate de zgomot, iar pentru a rezolva această problemă se va folosi un artificiu de calcul pentru a simplifica și a îmbunătății procesul de curățare a zgomotului aplicat imediat după aceea.

Deoarece se lucrează cu matrice ale imaginilor, trebuie să ne asigurăm că valorile obținute se încadrează în intervalul [0,255] care reprezintă domeniul de reprezentare pentru imagini, indiferent de formatul acestora (RGB – 3 nivele de valori în intervalul precizat, Grayscale – 1 nivel, cel de luminanță).

La final se realizează modelul 3D pe baza rezultatelor obținute și se afișează pe ecran, iar cu ajutorul mișcărilor camerei, ne putem deplasa pe modelul 3D.

Figura 20 – Etapele algoritmului de obținere hărți 3D din imagini 2D

Transformarea în Grayscale

Pentru a reduce timpul de procesare cu până la de 3 ori, vom transforma imaginile în format grayscale, adică pentru fiecare pixel al imaginii, în loc de 3 componente (R – roșu, G – verde, B – albastru) cu valori cuprinse între 0 și 255, vom avea o singură componentă și anume nivelul de luminanță (R = G = B tot în intervalul [0,255]).

Această transformare nu reduce doar timpul de procesare, ci și volumul necesar stocării imaginii.

Un avantaj major al acestei operații este că imaginile în nivele de gri se pot îmbunătății mai ușor apelând doar la modificările din domeniul ajustării luminozității sau modificări aduse asupra histogramei imaginii.

Se cunosc multe metode de calcul pentru nivelul de luminanță, pornind de la media aritmetică a celor 3 componente pentru fiecare pixel (3.4.1.1) până la formule diferențiate în funcție de zone geografice, datorită percepțiilor diferite asupra culorilor pentru diverse popoare (3.4.1.2 – Europa și 3.4.1.3 – SUA/Japonia)

Pentru această aplicație am folosit formula 3.4.1.3, formulă propusă și de către Arpad Gellert și Remus Brad[1] în Procesarea Imaginilor, Aplicații.

Metoda primește ca și parametru de intrare o imagine (un obiect de tipul bitmap) în format RGB și returnează tot o imagine (obiect de tip bitmap) în format grayscale.

Pentru fiecare imagine în parte se întoarce o imagine grayscale specifică neexistând legături și dependențe între imagini.

Figura 21 – Transformare în format grayscale

Figura 22 – Cod funcție transformare în format grayscale

Detecție și accentuare de contur (Laplacian of Gaussian – LoG)

Acest filtru are dublă acțiune asupra unei imagini. LoG sau Laplacian of Gaussian semnifică aplicarea unui Laplacian, care determină schimbările rapide de intensitate, asupra unei imagini filtrate cu un Gaussian, filtru care netezește imaginea și reduce sensibilitatea la zgomot.

Pentru o imagine în format grayscale se produce ca și rezultat o altă imagine tot în format grayscale, dar în care nivelele de gri ale pixelilor sunt modificate.

Dacă notăm intensitatea pixelului care se găsește la rândul ”x” și coloana ”y” dintr-o imagine cu I(x,y) atunci Laplacianul L(x,y) este dat de formula 3.4.2.1 și poate fi calculat folosind un filtru de convoluție.

Deoarece operația de convoluție este asociativă, se poate realiza o convoluție între Gaussian și Laplacian, iar rezultatul se poate aplica direct pe imagine.

Unde – deviația Gaussiană standard.

Trebuie găsită o mască de convoluție care aproximează derivata de ordinul doi în definiția Laplacianului, iar cele mai frecvent utilizate măști de dimensiunea 3×3 sunt:

Figura 23 – Măști LoG

Dacă se utilizează una din aceste măști, atunci Laplacianul poate fi calculat utilizând metoda standard de convoluție. Totodată, utilizarea unei astfel de măști pentru a aproxima derivata de ordinul doi, induce o sensibilitate crescută la zgomot. Pentru a elimina aceasta sensibilitate, se filtrează imaginea cu un Gaussian.

Pentru aplicația din această lucrare s-a utilizat un filtru de dimensiune 5×5, a cărei reprezentare grafică poate fi observată în Figura 24.

Figura 24 – Reprezentare 3D a filtrului Gaussian aplicat

Mai precis, se aplică un filtru Gaussian pentru netezirea imaginii, iar apoi rezultatul convoluției este împărțit unei valori, care reprezintă valoarea necesară pentru normalizare a rezultatului obținute în urma convoluției. Algoritmului i se aplică o inversare de culoare, pentru a evidenția zonele înalte și zonele joase, dar acest calcul nu va influența rezultatul algoritmului de stereo matching. Parametrul de intrare al acestei metode este imaginea asupra căreia dorim să efectuăm filtrarea, sub formă de matrice și ale cărei valori reprezintă intensitățile pixelilor, iar parametrul de ieșire este tot o imagine sub formă de matrice, dar care va conține noile valori pentru fiecare pixel, obținute în urma filtrării.

În cadrul acestei metode se apelează o funcție (GetWindowArrayFromImageArray) care va returna o fereastră bidimensională din tabloul care conține valorile în format grayscale ale pixelilor, fereastra returnată fiind cuprinsă între valorile precizate ca și parametrii.

Tot în cadrul acestei metode se mai apelează și funcția ApplyFilter care primește ca și parametrii de intrare două tablouri bidimensionale de aceeași mărime și returnează valoarea obținută în urma convoluției celor două tablouri.

Figura 25 – Cod Filtru LoG

Figura 26 – Cod ApplyFilter

Figura 27 – Rezultatul aplicării filtrului LoG

Algoritm stereo (Matching Pixel Count – MPC)

După cum am prezentat și în capitolul anterior, există mai multe metode de calcul a disparității, iar fiecare metodă încearcă să găsească corespondența între pixeli.

Aceste metode pot fi împărțite în două categorii, în funcție de tipul de constrângere utilizat:

Metode care folosesc constrângeri locale.

Metode care utilizează constrângeri globale.

Fiecare categorie de metode vine cu avantajele și dezavantajele ei. Principalul dezavantaj al metodelor care utilizează constrângeri locale este sensibilitatea la zonele cu textură ambiguă sau uniformă, dar rezultatele obținute în urma aplicării unei astfel de metode sunt de cele mai multe ori convenabile. În ceea ce privește metodele care utilizează constrângeri globale, regiunile cu textură uniformă nu mai reprezintă o problemă deoarece acestea sunt mai puțin sensibile în astfel de situații datorită numărului mai mare de pixeli luați în considerare, însă dezavantajul major îl reprezintă costul mare de procesare al calculelor necesare.

În urma comparării rezultatelor obținute prin intermediul mai multor metode printre care SSD, NNC și MPC, dar și al complexității implementării algoritmului, la sfaturile și îndrumările conducătorului prof. dr. ing. Daniel Volovici, am ajuns la concluzia că algoritmul optim pentru această aplicație este MPC (Matched Pixel Count).

Înainte de a aplica această metodă, trebuie setați anumiți parametrii în cadrul aplicației pentru a avea toate datele necesare . Acești parametrii sunt:

Dimensiunea ferestrei template.

Dimensiunea ferestrei din imaginea de căutare (mai mare ca și număr de coloane decât fereastra template, dar egal ca și număr de linii cu aceasta).

Pragul necesar calculului MPC.

Apoi valorile pixelilor din cele două imagini sunt salvate în două tablouri bidimensionale imageLeft și imageRight, iar în cadrul metodei MPC se va lucra cu aceste tablouri și rezultatul, adică valorile pixelilor calculate vor fi salvate într-un alt tablou bidimensional imageMPCResult. Pentru a salva valorile pixelilor dintr-o imagine într-un tablou, vom apela o altă metodă ImageToArray, care are ca și parametrii de intrare imaginea pentru care se dorește extragerea ferestrei și limitele între care se vor lua pixelii din imagine și returnează un tablou bidimensional care va conține valorile pixelilor din limitele stabilite.

După ce avem aceste tablouri bidimensionale ale ferestrei template și ale ferestrei care reprezintă imaginea de căutare se aplică algoritmul MPC.

Figura 28 – Cod Calculare MPC

Figura 29 – Cod Algoritm Stereo Matching – MPC

În cadrul acestui algoritm se apelează funcțiile:

GetWindowFromSearch – returnează un tablou bidimensional de mărimea dată de parametrii de intrare doi și trei ai funcției în care pixelul central are coordonatele i și j.

CreateImageFromArray – returnează un Bitmap creat din tabloul bidimensional transmis ca parametru, alături de lungimea și lățimea acestuia.

CalculareMPC – returnează un întreg care semnifică numărul comparațiilor dintre pixeli a căror diferență este mai mică decât un anumit prag.

Figura 30 – Rezultatul aplicării algoritmului stereo MPC

Netezirea imaginii

Această metodă vine în ajutorul algoritmilor de curățare a imaginilor de zgomot și este implementată astfel:

Se parcurge tabloul bidimensional rezultat în urma aplicării algoritmului stereo MPC.

Se consideră o fereastră bidimensională de mărimea 3×3 pentru fiecare poziție a imaginii.

Fiecare pixel din fereastra respectivă va avea valoarea egală cu media aritmetică a valorilor pixelilor din fereastră.

Rezultatul acestei metode este un tablou bidimensional netezit, din care se realizează prin intermediul funcției CreateImageFromArray un bitmap care va fi afișat în unul ferestrele din cadrul aplicației.

Figura 31 – Cod RescaleFilter – Netezirea imaginii

Filtrare curățare zgomot (Filtru pseudomedian)

După ce am făcut artificiul de calcul (netezirea imaginii, care are scopul de a simplifica și îmbunătății procesul de curățare de zgomot) se va aplica un algoritm pentru curățarea zgomotului din imagini.

În urma testării mai multor algoritmi, inclusiv în cadrul laboratorului destinat materiei Procesarea Imaginilor, an IV, semestrul I, Facultatea de Inginerie, Specializarea Calculatoare, laborator susținut de către conf. dr. ing. Gellert Arpad, am hotărât împreună cu conducătorul de proiect prof. dr. ing. Daniel Volovici, că, pentru aplicația din această lucrare să fie utilizată ca și metodă de curățare a zgomotului din imagini filtrul pseudomedian bidimensional în formă de ”+” având dimensiunea 5×5.

Putem generaliza definiția filtrului pseudomedian bidimensional de dimensiune arbitrară astfel:

Fie șirul de elemente notat .

Pseudomedianul lui este:

Dacă notăm:

Și

(3.4.5.3)

(3.4.5.4)

Figura 32 – Filtru pseudomedian bidimensional în formă de ”+” și de dimensiune arbitrară

(3.4.5.5)

Dacă dimensiunile filtrului sunt prea mari, acesta poate deteriora imaginea, așadar e necesar să alegem cât mai bine dimensiunea filtrului pentru a elimina cât mai mult zgomotul care este perturbator pentru funcțiile aplicate în continuare necesare creării modelului 3D.

Metoda primește ca și parametru de intrare imaginea rezultată în urma artificiului de calcul, sub formă de matrice, iar prin intermediul unui parametru care poate fi setat în secțiunea de parametrii ai aplicației se specifică dimensiunea filtrului.

Ca și parametru de ieșire avem o imagine sub formă de matrice în care avem imaginea curățată de zgomot (valorile pixelilor imaginii în urma aplicării filtrului).

Figura 33 – Diferite funcții utilizate în metoda Filtrului Pseudomedian

Figura 34 – Cod Filtru Pseudomedian

Deoarece rezultatele metodelor de netezire al imaginii și al aplicării filtrului pseudomedian sunt asemănătoare (produc netezirea imaginii, iar imaginile obținute sunt doar puțin diferite) am decis să prezint doar rezultatele metodei de aplicare a unui filtru pseudomedian.

Figura 35 – Rezultatele aplicării metodei de netezire și a filtrului pseudomedian

Normalizare

Deoarece am lucrat cu imagini sub formă de tablouri bidimensionale, prin aplicarea diferitelor metode enumerate mai sus, nu putem fi siguri că matricele rezultate conțin valori care pot fi reprezentate sub forma de imagini (intervalul [0,255] de luminanță).

De aceea, vom aplica o normalizare la domeniul [0,255] pentru matricea obținută în urma filtrării de curățare a zgomotului.

Metoda primește ca și parametru de intrare o imagine sub formă de matrice, calculează minimul și maximul din matricea respectivă, iar apoi se aplică o normalizare la domeniul [0,255] . După aceea, matricea obținută va fi returnată ca și parametru de ieșire.

Trebuie precizat faptul că domeniul este prestabilit la [0,255], însă poate fi modificat de către utilizator.

Figura 36 – Cod pentru normalizarea unui vector la intervalul [0,255]

Creare model 3D

Ultimul pas în această aplicație îl reprezintă cel al creării și afișării modelului 3D.

În urma aplicării algoritmului stereo MPC, ne rezultă o singură imagine, iar pentru a crea modelul 3D vor fi utilizate diferite API-uri din DirectX.

Metoda primește ca și parametru de intrare o imagine sub formă de matrice și afișează pe ecran, într-o fereastră nouă modelul 3D al imaginii, în jurul căreia ne putem roti, ne putem deplasa pe oricare din cele 3 axe și schimba gradul de la care este observat modelul 3D.

Pentru a realiza această etapă, pentru început trebuie să setăm dimensiunea modelului, mărimea VertexBuffer-ului și mărimea IndexBuffer-ului.

Figura 37 – Creare fereastră în care se va desena modelul 3D și apelul funcției care să configureze parametrii

Figura 38 – Setare parametrii

După ce am setat parametrii, apelăm o funcție numită LoadMap, care prin intermediul Bitmapului primit ca și parametru (bitmap-ul obținut din tabloul bidimensional rezultat în urma metodelor de obținere a hărții disparitățiilor, adică întocmai bitmap-ul hărții disparităților), creează un VertexBuffer în care valoarea pentru axa Y (înălțime) este dată de valoarea pixelului de la poziția respectivă.

După încheierea acestui pas, se va redesena fereastra, modelul 3D va fi vizibil și cu ajutorul tastaturii ne putem deplasa, roti pe deasupra hărții obținute.

Figura 39 – Creare VertexBuffer și setarea acestora pentru a putea fi afișat pe ecran modelul 3D

Figura 40 – Transformare 2D în 3D

Pentru a putea vedea modelul 3D, este necesar să inițializăm și să setăm camera. Acest lucru se face de fiecare dată când se redesenează fereastra sau se modifică parametrii camerei prin intermediul tastaturii sau al mouse-ului.

Figura 41 – Cod pentru setarea camerei

Pentru lucrul cu tastatura și mouse-ul, am folosit API-ul DirectInput pentru a putea avea acces la device-urile respective.

În momentul apăsării unei taste, se verifică ce valoare are tasta apăsată prin intermediul unui switch și se execută partea de cod specifică pentru fiecare tastă în parte.

În aplicația aceasta am definit astfel tastele:

A – pentru a deplasa camera la stânga

D – pentru a deplasa camera la dreapta

W – pentru a deplasa camera în față

S – pentru a deplasa camera în spate

Q – pentru a roti camera spre stânga

E – pentru a roti camera spre dreapta

Space – pentru a reseta poziția camerei la punctul inițial

Esc – pentru a închide fereastra

Up – pentru a ridica unghiul camerei

Down – pentru a coborî unghiul camerei

Pentru mouse am definit astfel:

Scroll în față – pentru a ridica poziția camerei

Scroll în spate – pentru a coborî poziția camerei

Scroll apăsat – mișcare pe axele X și Y în funcție de poziția mouse-ului

Figură 42 – Cod pentru mișcarea camerei din tastatură

Figura 43 – Cod cu alte evenimente pentru lucrul cu tastatura

Așa cum spuneam mai sus, pentru a desena și vedea pe ecran modelul 3D avem nevoie ca forma să se redeseneze tot timpul în funcție de parametrii aleși de noi (poziția camerei, modul de afișare al modelului).

Acest lucru este posibil datorită proprietății Invalidate în interiorul metodei de redesenare a formei. Cu ajutorul acestei proprietăți se creează practic o buclă infinită în care modelul este redesenat continuu.

În cadrul metodei de redesenare, se curăță ecranul de imagine, se setează camera, se obține VertexBuffer-ul și IndexBuffer-ul, se desenează pe ecran modelul în funcție de parametrii aleși, iar apoi se invalidează fereastra pentru a continua bucla.

Figura 44 – Cod redesenare fereastră

Prezentarea aplicației

Aplicația realizată pentru această lucrare este formată din două părți. O parte în care se achiziționează imaginile, se prelucrează, se aplică algoritmul de stereo matching, iar apoi se obține harta disparităților și o parte în care, prin intermediul DirectX se creează modelul 3D pentru depthmap-ul respectiv, se afișează în fereastră și cu ajutorul tastaturii ne putem deplasa în interiorul modelului pentru a-l examina. Tot în această parte, se poate încărca un alt depthmap, iar după încărcare se va afișa noul model 3D pentru depthmap-ul încărcat.

La pornirea aplicației metodele de prelucrare a imaginilor sunt dezactivate, la fel și butonul pentru deschiderea ferestrei în care vom reprezenta modelul 3D.

După încărcarea celor două imagini, metodele se activează și pot fi accesate rând pe rând, activându-se după încheierea etapei anterioare. În dreptul fiecărei metode se află fie o bifă verde fie un x roșu pentru a marca dacă aplicația a executat sau nu cu succes metoda respectivă. Modul de lucru poate fi atât manual cât și automat, dar doar după încărcarea celor două imagini stereo. În timpul rulării aplicației, imaginile rezultate pot fi salvate cu un click dreapta urmat de save în interiorul imaginii.

După parcurgerea tuturor metodelor de procesare și obținere de depthmap (hartă a disparităților) se activează butoanele de salvare a depthmap-ului și de creare a modelului 3D.

Aplicația dispune de un meniu din care se pot acționa metodele, din care se pot modifica parametrii algoritmului de stereo matching și o zonă de alte informații care cuprinde două ferestre, mai exact fereastra de pași în care ne sunt prezentate etapele de lucru ale aplicației și fereastra de informații (autor, facultate, specializare).

Procesarea imaginilor și obținerea hărții disparităților

Pentru început, se va detalia meniul din fereastra de procesare. Aici găsim trei opțiuni:

File

Settings

Help

În zona File, sunt trecute metodele în ordinea executării lor. Se poate apela metoda prin selectarea acesteia din această zonă. După ce se execută metoda, în stânga opțiunii din zona File va apărea un check, care înseamnă că metoda a fost executată cu succes. (Figura 45 – opțiune File – stânga).

În zona Settings se setează parametrii pentru algoritmul de stereo matching (MPC Threshold, Small Window Size și Big Window Size).

Fiecare opțiune are câte trei variante de selecție, iar dacă utilizatorul dorește să introducă o altă valoare decât cele prezente, o poate face în zona destinată noii valori pentru fiecare opțiune în parte. (Figura 45 – opțiune Settings – dreapta sus).

Iar ultima zonă este dedicată pentru Help, în care avem posibilitatea să aflăm etapele de lucru ale aplicației și informații precum autor, îndrumător etc. (Figura 45 – opțiune Help – dreapta jos).

Figura 45 – Meniul aplicației de procesare

Fereastra dedicată procesării este împărțită în trei zone:

Zona pentru afișarea imaginilor în funcție de metoda parcursă

Zona de control – aici se află butoane prin intermediul cărora putem apela metodele pentru procesare, salvare depthmap sau creare model 3D. În dreptul fiecărui buton se află o imagine reprezentativă pentru execuția metodei (bifă verde – metoda a fost parcursă fără a apărea erori, x roșu – în cadrul metodei au intervenit erori sau mai poate reprezenta și că aplicația încă nu a apelat metoda respectivă)

Zona de status – aici se afișează etapa și informații despre ce metodă se execută și care este stadiul execuției în funcție de background (galben – în curs de procesare, verde – metodă încheiată cu succes, roșu – eroare în cadrul metodei)

Figura 46 – Fereastra de procesare a imaginilor

Fereastra de informații conține pe lângă informații despre autorul aplicației, îndrumător și două butoane prin intermediul cărora utilizatorul poate accesa pagina WEB a Facultății de Inginerie sau a Universității Lucian Blaga din Sibiu.

Figura 47 – Fereastra de informații

Fereastra de prezentare a etapelor vine în sprijinul utilizatorului cu prezentarea unui exemplu de executare cu succes a aplicației.

Figura 48 – Fereastra de prezentare a etapelor de procesare

Crearea și afișarea modelului 3D

După procesarea imaginilor și obținerea hărții disparităților, se deblochează butonul care permite utilizatorului să vizioneze modelul 3D creat pe baza acestei hărți.

Ca și în fereastra de procesare, avem un meniu care vine în ajutorul utilizatorului în ceea ce privește modul de afișare sau, în cazul în care se dorește afișarea unui alt depthmap, utilizatorul are posibilitatea să încarce și să vizualizeze modelul 3D pentru depthmap-ul respectiv.

Meniul este format din două secțiuni:

Menu – utilizatorul are posibilitatea de a încărca un nou depthmap prin selectarea opțiunii Load Heightmap, poate reseta harta prin selectarea opțiunii Reset sau poate închide fereastra prin selectarea opțiunii Exit.

Properties – se împarte în două submeniuri:

FillMode – aici se selectează modul în care să fie afișat modelul 3D. Sunt disponibile trei variante – Solid, Wireframe și Point.

Background Color – de aici se poate schimba culoarea background-ului pentru fereastra de afișare a modelului 3D.

Figura 49 – Meniu fereastră de afișare a modelului 3D

În funcție de modul de afișare selectat, în dreapta opțiunii alese va apărea un check, iar în momentul redesenării ferestrei, modelul 3D va fi redesenat cu modul de afișare ales de utilizator.

Dacă utilizatorul dorește să schimbe culoarea background-ului, o poate face prin selectarea opțiunii Background Color care va deschide o casetă de culori de unde acesta poate alege ce culoare dorește. Modelul 3D nu va fi afectat de schimbarea culorii background-ului.

În modul de afișare Solid, modelul 3D este prezentat utilizatorului ca și o hartă continuă, dar în format 3D, iar culoarea este dată în funcție de nivelul de luminanță al pixelului din Bitmap-ul trimis ca și parametru către fereastra de afișare.

Figura 50 – Mod de afișare Solid

În modul de afișare Wireframe, modelul 3D este prezentat utilizatorului ca și o rețea de triunghiuri interconectate.

Figura 51 – Mod de afișare Wireframe

În modul de afișare Point, modelul 3D este prezentat utilizatorului ca și o rețea de puncte (Point Cloud).

Figura 52 – Mod de afișare Point

Cu ajutorul tastaturii, utilizatorul se poate deplasa în interiorul modelului, iar cu ajutorul mouse-ului, poate schimba unghiul de vedere pe cele trei axe.

Concluzii și dezvoltări ulterioare

Concluzii și rezultate

În urma aplicării algoritmului asupra mai multor imagini stereo de test (imagini stereo ale hărților obținute din sateliți, imagini stereo ale obiectelor) s-a constatat că un număr mare de factori pot influența rezultatele.

Acești factori diferă de la nivelul de zgomot până la parametrii setați de către utilizator (prag MPC, dimensiune fereastră mică – template, dimensiune fereastră mare – fereastra de căutare).

În timpul dezvoltării aplicației, la implementarea algoritmului block matching pentru stereo, pe lângă algoritmul MPC, au fost implementate și alte metode (mai exact SSD – Sum of Square Differences, SAD – Sum of Absolute Differences și NCC – Normal Cross Correlation) pentru a se putea compara rezultatele obținute cu cele ale algoritmului ales.

În continuare sunt prezentate comparațiile algoritmiilor de block matching pentru trei din testele aplicate.

Figura 53 – Comparații rezultate diferiți algoritmi de block matching

Figura 54 – Comparații rezultate diferiți algoritmi de block matching

Figura 55 – Comparații rezultate diferiți algoritmi de block matching

Deoarece algoritmii de mai sus, folosesc constrângeri locale, sunt sensibili la zonele cu textură uniformă. În funcție de selectarea diferitelor valori pentru parametrii algoritmului MPC, se obțin depthmap-uri mai netezite sau mai puțin netezite.

Pragul joacă un rol important deoarece dacă se alege o valoare prea mare pentru el, atunci se pot produce detecții false, iar dacă este prea mic, e posibil să omită unele corelații reale.

Dimensiunea ferestrei mici, adică a template-ului are și ea un rol important, iar din testele experimentale s-a putut constata că o dimensiune mai mică oferă rezultate mai bune.

Ultimul factor, dar la fel de important este dimensiunea ferestrei mari, adică a ferestrei de căutare. O dimensiune prea mică a acestei ferestre poate face ca rezultatul obținut să nu fie cel real, iar o dimensiune prea mare ar putea însemna corelații false.

În continuare se prezintă o serie de teste realizate cu diferite valori ai acestor parametrii.

Figura 56 – Rezultate obținute prin variația threshold-ului

Figura 57 – Rezultate obținute prin variația template-ului (fereastra mică)

Figura 58 – Rezultate obținute prin variația ferestrei de căutare (fereastra mare)

După cum se poate observa, rezultatele diferă în funcție de valorile parametrilor necesari algoritmului de stereo matching. Valorile potrivite diferă de la imagine la imagine (dacă pentru o imagine rezultatele obținute sunt bune cu parametrii standard – Threshold = 7, Small Window = 9 și Big Window = 45, e posibil ca pentru alte imagini să nu mai ofere rezultate bune). Calitatea rezultatelor diferă așadar, atât în funcție de calitatea imaginii cât și în funcție de valorile parametrilor pentru MPC.

Dezvoltări ulterioare

Ca și dezvoltări ulterioare pentru aplicație și algoritm ar putea fi următoarele:

Salvarea modelului 3D.

Crearea de depthmap color și afișarea acestuia ca și model 3D în format RGB.

Combinarea metodelor care oferă cele mai bune rezultate.

Optimizarea algoritmului pentru a reduce durata de așteptare al aplicării metodei de stereo matching.

Implementarea rețelelor neuronale pentru a seta parametrii cei mai optimi în scopul obținerii rezultatelor mai bune.

Bibliografie

[1] Arpad Gellert și Remus Brad – Procesarea Imaginilor, Aplicații.

[2] B Kasi Viswanatha Reddy, Prof. Sukadev Meher, Fast Block Matching Motion Estimation Algorithms for Video Compression, Master of Technology in Electronics and Instrumentation, National Institute of Technology Rourkela, pages 37-41, 2013.

[3] Baker H.H. și Binford T.O. – Depth from edge-and intensity-based stereo. In Proceedings Joint Conference on Artificial Intelligence, Vancouver, Canada, pages 631-636, August 1981.

[4] Barnard S.T. și Fischer M. A. – Computational Stereo, ACM Computing Surveys, vol. 14, pp. 553-572, 1982.

[5] Dhond U. R. și Aggarwal J. K. – Structure from a Stereo – A Review, IEEE Trans.Systems, Man and Cybenretics, vol. 19, pp. 1489-1510, 1989.

[6] Faugeras O. și Luong Q. T. – The Geometry of Multiple Images, The MIT Press, Cambridge, Massachusetts, 2001.

[7] Hartley R. și Zisserman A. – Multiple View Geometry in Computer Vision, Cambridge University Press, Cambridge, United Kingdom, 2000.

[8] Ohta Y. și Kanade T. – Stereo by intra-and inter-scanline search. IEEE Transactions on PAMI, 7, No 2:139-154, 1985

[9] Remus Brad – Procesare de imagine și elemente de computer vision, Editura Universității “Lucian Blaga”, Sibiu, 2003.

[10] Y. Furukawa și C. Hernández . Multi-View Stereo: A Tutorial. Foundations and TrendsR in Computer Graphics and Vision, vol. 9, no. 1-2, pp. 1–148, 2013.

[11] Zabih R. și Woodfill J. – Non-Parametric Local Transforms for Computing Visual Correspondence, Proc. 3rd European Conf. Computer Vision, pp. 150-158, 1994.