Programul de studii: Matematic a si Informatic a Aplicat a n Inginerie [613254]

UNIVERSITATEA POLITEHNICA DIN BUCURES TI
FACULTATEA DE S TIINT E APLICATE
Programul de studii: Matematic a  si Informatic a Aplicat a ^ n Inginerie
PROIECT DE DIPLOM A
^INDRUM ATOR S TIINT IFIC, ABSOLVENT: [anonimizat] sti
2017

UNIVERSITATEA POLITEHNICA DIN BUCURES TI
FACULTATEA DE S TIINT E APLICATE
Programul de studii: Matematic a  si Informatic a Aplicat a ^ n Inginerie
Aprobat Decan,
Prof. Univ. Dr. Emil PETRESCU
PROIECT DE DIPLOM A
Reconstruct ia 3D a obiectelor
din multiple imagini
^INDRUM ATOR S TIINT IFIC, ABSOLVENT: [anonimizat] sti
2017

1 Introducere
Reconstruct ia 3D din imagini multiple reprezint a crearea unui model tridimensional dintr-un
set de imagini. Ideea principal a a acestei probleme este c^ a stigarea informat iei de ad^ ancime
ce se pierde atunci c^ and se realizeaz a o imagine. Imaginile sunt proiect ii ale scenelor 3D
^ ntr-un plan 2D. Astfel, obiectul sau scena pe care dorim s a ^ l reconstruim ^ n 3D va  fo-
tograat din mai multe puncte de vedere. Pentru ecare dou a poze consecutive se va realiza
o triangulare pentru a determina pozit ia punctelor 3D. Cheia procesului este reprezentat a de
relat iile dintre punctele de vedere multiple, care transmit informat ii corespunz^ and seturilor
de puncte, ce trebuie s a cont in a o structur a spat ial a  si c a acea structur a are leg atur a cu
pozit iile  si calibrarea camerei [26].
Scopul unui algoritm de reconstruct ie 3D din multiple imagini poate  descris ca: "ind
dat un set de fotograi ale unui obiect sau peisaj, el trebuie s a estimeze cea mai potrivit a
form a 3D care explic a acele fotograi, sub presupunerea c a materialele sunt cunoscute,
punctele de vedere  si condit iile de iluminat" [17].
1.1 Important a  si actualitatea temei abordate ^ n lucrare
Reconstruirea geometriei 3D din fotograi este o problem a clasic a a domeniului Computer
Vision care a fost abordat a de c atre cercet atori de mai bine de 30 de ani. Aplicat iile variaz a
de la map ari 3D  si navigat ie la shopping online, 3D printing, fotograe computat ional a,
jocuri video sau prezervarea tezaurului cultural. Numai recent, ^ ns a, aceste tehnici au ajuns
la un nivel de maturitate sucient pentru a ie si din stadiul de experiment  si s a e utilizate
^ n mediul industrial, astfel oferind acuratet e  si scalabilitate.
Reconstruct ia 3D a obiectelor este o tehnologie folosit a ^ n domenii  stiint ice, precum
Design-ul Geometric Asistat pe Calculator (CAGD), Grac a pe Calculator, Animat ie pe
Calculator, Imagistica Medical a, S tiint e Computat ionale, Realitate Virtual a, Digital Media,
etc. Un exemplu ar  reprezentarea 3D a informat iilor despre leziuni ale pacient ilor, pe
calculator, astfel oferind o nou a abordare corect a  si precis a ^ n diagnosticare, un proces de o
important  a vital a ^ n medicin a [27].
Reconstruct ia 3D din imagini multiple este folosit a din ce ^ n ce mai des de c atre:
industria de Divertisment (Televiziune, Cinematograe, Jocuri) ^ n implementarea unor
tehnologii precum: "realitate augmentat a"  si recontruct ie digital a a obiectelor.
industria Navigat iei (Cartograe, GPS) pentru realizarea de h art i virtuale (GoogleEarthTM)
sau asocierea unei interfet e grace sistemelor GPS.
1.2 Motivat ia alegerii temei
Tema stereo reconstruct iei digitale reprezint a un subiect de interes deoarece este o metod a
alternativ a ecient a de reducere a timpului de lucru ^ n vederea cre arii de elemente pentru
simul ari video. Aceast a lucrare poate  considerat a ca ind o etap a introductiv a esent ial a
realiz arii unei unelte de simulare planetar a. Unealta va  folosit a^ n simularea video a evolut iei
de populat ii at^ at umane c^ at  si celei animale ^ n funct ie de mediul ^ nconjur ator.
3

Aceast a abordare are avantaje artistice, din moment ce:
putem realiza reconstruct ii veridice ale tuturor obiectelor sau viet at ilor ce vor  supuse
procesului;
putem prelua texturile din imaginile folosite ^ n procesul de reconstruct ie.
Acest lucru ^ nseamn a c a timpul investit ^ n design sau num arul de persoane necesare pen-
tru a naliza produsul va sc adea vertiginos, al aturi de costuri.
2 Not iuni teoretice ale algoritmilor de reconstruct ie 3D
2.1 Preimagine  si coimagine pentru puncte de vedere multiple
2.1.1 Preimaginea pentru puncte de vedere multiple
O preimagine a unui punct reprezin a multimea de puncte care duc de la punctul 3D observat
spre punctul de observat ie folosit [2].
^In cazul pozit iilor multiple, preimaginea unui punct sau a unei drepte este setul (cel mai
mare) de puncte 3D care ridic a acela si num ar de imagini multiple ale punctului sau dreptei [ ?].
De exemplu, oricare dou a imagini i1 sii2ale drepteiL, pre-imaginea acestor dou a imagini
este intersect ia planurilor P1 siP2, adic a exact dreapta 3D L=P1\P2.
^In general, pre-imaginea imaginilor multiple ale unui punct sau drepte pot  denite de
intersect ia :
preimaginea (X1;


;Xm) =preimaginea (X1)\


\preimaginea (Xm);
preimaginea (a1;


;am) =preimaginea (a1)\


\preimaginea (am):
Denit ia de mai sus ne permite s a cre am preimagini pentru orice set puncte sau drepte
din imagine. Preimaginea unor multiple imagini cu puncte sau drepte, de exemplu, poate
ori un o multime goal u a, un punct, o dreapt a sau un plan, depinz^ and doar de faptul dac ele
vin sau nu de pe aceea si dreapt a ^ n spat iu [1].
2.2 Preimaginea  si co-imaginea punctelor  si dreptelor
Pentru o camer a ce este deplasat a ^ n intervalul de timp t, ex(t) coordonata unui punct X
din 3D ^ n coordonate omogene:
(t)x(t) =K(t)u0g(t)X;
unde(t) reprezint a ad^ ancimea punctului, K(t) reprezint a parametrii intrinseci, u0este
proiect ia generic a,  si
g(t) =R(t)T(t)
0 1
2SE(3);
4

ce reprezint a mi scarea rigid a a obiectului la timpul t, iar SE(3) reprezint a spat iul rotat iilor
si translat iilor [5].
S a consider am o dreapta 3D ^ n coordonate omogene:
L=fXjX=X0+V;2RgR4;
unde X0= [X0;Y0;Z0;1]>2R4sunt coordonatele bazei  si V= [V1;V2;V3;0]>2R4este un
vector nenul care indic a direct ia dreptei [4] .
T  in^ and cont de imaginea la momentul t,pre-imaginea dreptei Lformeaz a un plan Pcu
normala a(t), unde P= dima. Vectorula(t) este ortogonal pe dreapt a pentru toate punctele
salex:
a(t)>x(t) =a(t)>K(t)u0g(t)X= 0:
Presupunem c a ne este dat un set de mimagini pentru momentele t1;


;tmunde
i=(ti);xi=x(tj); a i=a(ti);ui=K(ti)u0g(ti):
Folosindu-ne de aceste notat ii, putem lega ai-a imagine a unui punct pde coordonatele
Xdin 3D:
ixi=uiX;
 siai-a co-imagine a dreptei Lde coordonatele ( X0;V):
a>
iuiX0=a>
iuiV= 0:
2.3 De la preimagine la restrict iile de rang
Ecuat iile de mai sus cont in parametrii 3D ai punctelor  si dreptelor ca necunoscute. Ceea ce
dorim este s a elimin am necunoscutele pentru a putea obt ine leg aturi ^ ntre proiect iile 2D  si
parametrii camerei.
Exist a diferite metode de eliminare a parametrilor 3D care duc la diferite tipuri de
restrict ii care au fost studiate ^ n materia grac a pe calculator.
O eliminare sistematic a a acestora va duce la un set de condit ii complete [1].
2.3.1 Caracteristicile punctului
Consider am imaginile unui punct X3D. v azut din mai multe puncte de observare:
X!
0
BBB@x10


0
0x2


0
…………
0 0


xm1
CCCA0
BBB@1
2
…
m1
CCCA=0
BBB@u1
u2
…
um1
CCCAXuX;
care are forma
5

X!
=uX;
unde!
2Rmeste scala de ad^ ancime a vectorului ,  siu2R3mmeste matricea de proiect ie
din puncte de vedere multiple asociat a cu matricea imaginii X2R3mm[5].
,
Este de  stiut faptul c a ^ n afar a de coordonatele din 2D cont inute de matricea X, orice alt
element din ecuat ie reprezint a o necunoscut a. Obiectivul nostru este s a decupl am ecuat ia de
mai sus ^ n restrict ii care s a ne permit a s a obt inem, prima dat a, mi sc arile camerei ui si apoi
structura scenei i si coordonatele Xdin 2D [1].
Fiecare coloan a a lui Xse a
 a^ ntr-un spat iu patru-dimensional dimensionat dup a coloanele
matriciiu. Pentru a avea o solut ie pentru ecuat ia anterioar a, coloanele lui X siutrebuie
astfel s a e liniar dependente. Cu alte cuvinte, matricea:
Np(u;X) =0
BBB@u1x10


0
u20x2


0
……………
um0 0


xm1
CCCA2R3m(m+4)
trebuie s a e supradiagonal a nul a. Pentru m2 (adic a 3mm+ 4), rangul maximal
ar trebui s a e m+ 4. Dependent a liniar a a coloanelor trebuie s a e deci rangul restrict iei:
rang(Np)m+ 3:
De fapt, vectorul u(X>;!
>)>2Rm+4se a
 a ^ n zona nul a, notat ca Npu= 0 [5].
Pentru o formulare mai compact a a restrict iei rangului de mai sus introducem matricea
X?0
BBB@bx10


0
0bx2


0
…………
0 0


cxm1
CCCA2R3m3m;
care are proprietatea de a asasina pe X:
X?X= 0;
putem pre^ nmult i ecuat ia pentru a obt ine
X?uX= 0:
Astfel vectorul Xse a
 a ^ n spat iul nul al matricei
WpX?u=0
BBB@bx1u1
bx1u1
…
cxmum1
CCCA2R3m4:
Pentru a avea o solut ie unic a, trebuie ca
6

rang(Wp)3:
Dac a toate imaginile xisunt dintr-un singur punct Xdin 3D, atunci matricea Wpar
trebui s a aib a numai un spat iu nul unidimensional [1]. Fiind date mimagini xi2R3ale
punctuluip^ n funct ie de cele mframe-uri ale camerei ui, trebuie s a avem condit ia de rang
rang(Wp) = rang(Np)m3:
2.3.2 Caracteristicile dreptei
Putem deriva restrict ia de rang similar  si pentru drepte [5]. Precum am v azut anterior,
pentru co-imaginile ai; i= 1;


;mpentru o drepta Lcu baza X0 si direct iaVavem:
a>
iuiX0=a>
iuiV= 0:
Astfel matricea
Wi0
BBB@a>
1u1
a>
1u2
…
a>
1um1
CCCA2Rm4
trebuie s a satisfac a rangul restrict iei
rang(Wi)2;
din moment ce spat iul nul al lui Wicont ine cei doi vectori X0 siV.
2.4 Interpretarea geometric a
2.4.1 Restrict iile rangului: interpretare geometric a
^In cazul unui punct X, aveam ecuat ia
WpX= 0;cuWp=0
BBB@bx1u1
bx1u1
…
cxmum1
CCCA2Rm4:
Din moment ce toate matricele bxiau rangul 2, num arul de linii independente ^ n Wpeste
cel mult 2m. Aceste r^ anduri denesc un set de 2 mplane. Din moment ce WpX= 0, punctul
Xse a
 a la intersect ia tuturor planelor. Pentru ca toate cele 2 mplane s a aib a o intersect ie
unic a, avem nevoie de rang (Wp) = 3 [23].
7

2.5 Matricerea punctelor de vedere multiple
2.5.1 Matricea punctelor de vedere multiple ale unui punct
Vom prespune c a avem mimagini, prima din ele ind ^ n coordonate 3D. Apoi avem matricele
de proiect ie ale formei
u= [I;0];u= [R2;T2];


;u= [Rm;Tm]2R34;
care modeleaz a proiect ia unui punct Xdin imaginile individuale.
^In general pentru camerele necalibrate (adic a Ki6=I),Rinu va  o matrice rotat ie or-
togonal a ci mai degrab a o matrice inversabil a arbitrar a [4].
Din nou, denim matricea Wp
Wp=0
BBB@bx1u1
bx1u1
…
cxmum1
CCCA2Rm4:
Asta ^ nseamn a c a rang( Wp)3 dac a  si numai dac a submatricea
Mp=0
BBB@bx2R2bx1bx2T2
bx3R3bx1bx3T3
……
bx2Rmbx1cxmTm1
CCCA2R3(m1)2
are rang( Mp)1.
Matricea
Mp=0
BBB@bx2R2bx1bx2T2
bx3R3bx1bx3T3
……
bx2Rmbx1cxmTm1
CCCA2R3(m1)2
se nume ste matricea puctelor de vedere multiple asociat a unui punct p. Ea este compus a
din a at^ at imaginea x1din primul punct de vedere, c^ at  si co-imaginea bxidin restul punctelor
de vedere [1].
Pe scurt:
Pentru imaginile multiple ale unui punct pmatriceleNp,Wp siMpsatisfac
rang(Mp) = rang( Wp)2= rang( Np)(m+2)1
Vom verica informat ia geometric a cont inut a de matricea punctelor de vedere multiple
8

Mp=0
BBB@bx2R2bx1bx2T2
bx3R3bx1bx3T3
……
bx2Rmbx1cxmTm1
CCCA2R3(m1)2:
Rangul restrict iei rang( Mp)1ne spune c a cele dou a coloane sunt liniar dependente [1].
De fapt, avem
1bxiRix1+bxiTi= 0; i= 2;


;m;
din care rezult a
Mp1
1
= 0:
De aceea coecientul ce captureaz a liniar dependent a este pur  si simplu distant a1a
punctuluipde la primul centru al camerei. Cu alte cuvinte, matricea punctelor de vedere
multiple captureaz a exact informatia despre punctul pcare lipse ste dintr-o singur a imagine,
dar codat a ^ n imagini multiple [4].
2.6 Leg atura cu restrict iile epipolare
Pentru matricea punctelor de vedere multiple,
Mp0
BBB@bx2R2bx1bx2T2
bx3R3bx1bx3T3
……
bx2Rmbx1cxmTm1
CCCA2R3(m1)2;
s a aib a rang( Mp) = 1, este necesar ca perechile de vectori bxiTi sibxiRibx1s a e liniar
dependente pentru tot i i= 2;


;m[23]. Astfel vom obt ine restrict iile epipolare
x>
ibTiRix1= 0
pentru primele i imagini.
Vom presupune c a vectorii bxiTi sibxiRibx1sunt liniar independent i, adic a exist a un scalar

, astfel ^ ncat
bxiTi=
bxiRibx1:
Din moment ce bxiTibxiTieste proport ional a normalei planului generat de bxi siTi,
 sibxiRibx1este proport ional a normalei planului generat de bxi siRibx1, liniar dependent a este
echivalent a cu not iunea c a vectoriibxi; Ti siRibx1sunt coplanari [1].
Acest lucru, din nou, este echivalent cu armat ia c a vectorul xieste ortogonal pe normala
de pe planul generat de vectorii Ti siRix1, adic a
x>
i(TiRix1) =x>
ibTiRix1= 0:
9

2.6.1 Analiza restrict iilor punctelor de vedere multiple
Pentru oricare vectori nenuli bi;ci2R3;i= 1;2;


;n;matricea
0
BBB@b1c1
b2c2
……
bncn1
CCCA2R3n2
nu are un rang maximal dac a  si numai dac a bic>
jcib>
j= 0 pentru toate i;j= 1;


;n.
Aplic^ and restrict ia de rang pe Mpobt inem:
bxiRix1(bxjTj)>bxiTi(bxjRjx1)>= 0;
care ne ofer a restrict ia triliniar a
bxi(Tix>
1R>
jRix1T>
j)bxj= 0:
Aceasta este ecuat ia matriceal a care ofer a 3 3 = 9 ecuat ii scalar triliniare, patru dintre
care sunt liniar independente [6].
De la ecut iile
bxiRix1(bxjTj)>bxiTi(bxjRjx1)>= 0;8i;j2R;
putem vedea c a at^ ata timp c^ at termenii bxjTj sibxjRjx1sunt diferit i de 0, rezult a de mai
sus c a, perechile de vectori bxiTi,bxiRix1 sibxjTj,bxjRjx1sunt liniar independent i.
Cu alte cuvinte: ^ n afar a de cazurile degenerate, restrict iile biliniare (epipolare) care
fac leg atura dintre cele dou a puncte de vedere sunt deja cont inute de restrict iile triliniare
obt inute pentru cazul punctelor de vedere multiple [2].
De  stiut este c a echivalent a dintre restrict iile biliniare  si triliniare pe de-o parte  si condit ia
c a rang(Mp)1 pe de alt a parte este valabil a numai dac a vectorii din Mpsunt nenuli. ^In
anumite cazuri degenerate acest lucru nu are loc [6].
2.6.2 Unicitatea unei preimagini
Folosind matricea punctelor de vedere multiple obt inem o caracterizare mai general a  si mai
simpl a a unicit at ii unei preimagini:
Fiind dat i vectorii mreprezent^ and cele mimagini ale unui punct din mpuncte de vedere,
ele corespund aceluia si punct ^ n spat iul 3D dac a rangul matricei Mprelativ la orice cadru al
camerei este unu. Dac a rangul este zero, punctul este determinat p^ an a la o dreapt a pe care
toate centrele camerelor trebuie s a e a sezate [10].
Pe scurt obt inem:
rang(Mp) = 2)nici-un punct de corespondent  a  si o imagine goal a
rang(Mp) = 1)punct de corespondent  a  si preimagine unic a
rang(Mp) = 0)punct de corespondent  a dar preimaginea nu e unic a
10

Cu aceste restrict ii putem s a ne decidem ce opt iuni ne sunt necesare pentru a realiza
corespondent a unui punct pe mai multe cadre.
2.7 Algoritm de reconstruct ie cu puncte de vedere multiple
2.7.1 Factorizarea din puncte de vedere multiple a caracteristicilor unui punct
Condit ia de rang aplicat a matricei punctelor de vedere multiple cont ine toate restrict iile din
mult imea de imagini ale unui singur punct. ^In principiu, cineva poate aplica o reconstruct ie
prin maximizarea unor funct ii obiectiv globale supuse condit iei de rang [11].
Vom presupune c a avem mimagini anpunctepj si ne dorim s a estim am matricea de
proiect ieunecunoscut a.
Condit ia rang(Mp)1ne spune c a Mpare dou a coloane liniar dependente. Pentru al jlea
punctpjasta ^ nseamn a
0
BBB@bxj
2R2xj
1
bxj
3R3xj
1…
bxj
mRmxj
11
CCCA+j0
BBB@bxj
2T2
bxj
2T2
…
bxj
mTm1
CCCA= 02R3(m1)1;
pentru c^ at iva parametri j2R; j= 1;


;n. Fiecare linie de mai sus poate  obt inut a din
j
ixj
i=j
1Rixj
1+Ti, multiplic^ and prin bxj
i:
bxj
iRixj
1+xj
iTi=j
1= 0:
Astfel,j= 1=j
1nu este altul dec^ at inversa ad^ ancimii punctului pjc^ and vine vorba de
primul cadru [1].
2.7.2 Estimarea deplas arii dintr-o structur a cunoscut a
S a presupunem c a at^ at ad^ ancimile punctelor c^ at  si inversa j(structura cunoscut a) sunt
 stiute. Atunci ecuat ia anterioar a este liniar a pentru parametrii de deplasare Ri siTi. Folosind
urm atoarea notat ie RS
i= [r11;r21;r31;r12;r22;r32;r13;r23;r33]>2R9 siTi2R3, avem sistemul
liniar de ecuat ii
PiRS
i
Ti
=0
BBBB@x1
1>
bx1
j1bx1
j
x2
1>
bx2
j2bx2
j……
xn
1>
cxn
jncxn
j1
CCCCARS
i
Ti
= 02R3n:
Se poate ar ata c a matricea Pi2R3n12arerangul egal cu 11 dac a mai mult de 6 npuncte
cu pozit iile generale sunt date .^In cazul ^ n care spat iul nul al lui Pieste unidimensional  si se
renuntt  a la matricea de proiect ie u= (Ri;Tj) pentru un factor de scalare. ^In practic a cineva
ar folosi mai mult de 6 puncte, ar obt ine o matrice de rang ^ ntreg  si ar calcula solut ia prin
decompozit ia unei valori singulare (SVD) [19], [1].
11

2.7.3 Estimarea structurii din deplas ari cunoscute
Dac a deplasarea camerei ui= (Ri;Tj);i=1;meste cunoscut a, putem estima structura
(parametrii de ad^ ancime j;j=1;m). Solut ia ^ n direct ia celor mai mici p atrate pentru
ecuat ia de mai sus este dat a de:
j=Pm
i=2(cxj
iTi)>cxj
iRixj
1Pm
i=2jjcxj
iTijj2;j=1;n:
^In acest fel putem estima structura  si deplasarea iterativ, p astr^ and una dintre ele xe  si
a
^ and-o pe cealalt a [2].
Pentru init ializare se poate aplica algoritmul cu opt puncte pentru primele dou a imagini
pentru a obt ine o valoare estimativ a a parametrilor de structur a j[11].
At^ ata timp c^ at ecuat ia pentru uise folose ste numai de dou a cadre 1  si i, estimarea
parametrului de structur a va lua ^ n considerare toate cadrele. Acest lucru poate  realizat
e ^ n modul grupat e ^ n cel recursiv [1].
2.8 Reconstruct ia dreptelor din puncte de vedere multiple
2.8.1 Matricea dreptelor din puncte de vedere multiple
Matricea
Wi=0
BBB@`>
1u1
`>
2u2
…
`>
mum1
CCCA2Rm4
asociat a cu mimagini ale unei drepte ^ n spat iu satisface restrict ia de rang rang (Wi)2,
deoareceWiX0=WiV= 0 pentru punctul de baz a X0 si direct ia Va dreptei. Pentru o
reprezentare mai compact a, s a presupunem c a prima camer a se a
 a la coordonatele reale
u1= (I;0).Rangul nu este afectat de ^ nmult irea cu o matrice de rang ^ ntreg Di2R45:
WiDi=0
BBB@`>
1 0
`>
2R2`>
2T2
……
`>
mRm`>
mTm)1
CCCA
`b`10
0 0 1
=0
BBB@`>
1`1 0 0
`>
2R2`1`>
2R2b`1l>
2T2
………
`>
mRm`1`>
mRmb`1l>
mTm1
CCCA
Din moment ce multiplicarea cu o matrice de rang complet nu afecteaz a rangul, avem
rang (WiDi) =rang (Wi)2:
Din moment ce prima coloan a a lui WiDieste liniar independent a cu celelalte r amase,
submatricea
Mi=0
B@`>
2R2b`1l>
2T2
……
`>
mRmb`1`>
mTm1
CA2R(m1)5;
12

are restrict ia de rang:
rang (Mi)1:
Pentru cazul unei drepte proiectate ^ n m imagini, avem o restrict ie de rang mai puternic a
dec^ at ^ n cazul proiect arii unui singur punct. Pentru un num ar sucient de mare de puncte
de vederem, matricea Mipoate, ^ n principu, s a aib a rangul 5. Restrict ia de mai sus ne
spune c a o pre-imagine important a a m drepte observate poate exista dac a  si numai dac a
rang (Mi)1 [2].
2.8.2 Restrict ia triliniar a a unei linii
Consider^ and restrict ia de rang de mai sus, primele trei coloane ale lui Mine spun c a acel
r^ and specic trebuie s a e liniar dependent ^ n pereche, adic a i;j6= 1:
`>
iRib`1l>
jRib`1;
care este echivalent a cu ecuat ia triliniar a
`>
jRib`1R>
j`j= 0:
Restrict ia de mai sus trateaz a numai rotat iile camerei, nu  si translat iile [1].
2.8.3 Analiza restrict iei ale punctelor de vedere multiple
Pentru oricare vectori nenuli ai;bi2R3;i=1;n, matricea
0
BBB@a1b1
a2b2
……
anbn1
CCCA2R3n2
prezint a o decient  a de rang dac a  si numai dac a aib>
jbia>
j= 0 pentru i;j=1;n. Nu vom
demonstra aceast a armat ie. Aplic^ and restrict ia de rang pentru Mpvom obt ine:
bxiRix1(bxjTj)>bxiTi(bxjRjx1)>= 0;
din care rezult a restrict ia triliniar a
bxi(Tix>
1R>
jRix1T>
j)bxj= 0:
Aceasta este o ecuat ie matriceal a de 3 3 = 9 ecuat ii triliniare scalare, numai patru dintre
care sunt liniar independente [4].
2.8.4 Restrict iile triliniare pentru o dreapt a
Tin^ and cont de a patra coloan a a matricei punctelor de vedere multiple Mi, restrict ia de rang
implic a liniar dependent a dintre al i-lea  si alj-lea r^ and. Aceasta este echivalentul restrict iei
triliniare:
`>
jTj`>
iRib`1`>
iTi`>
jRjb`1= 0:
13

Restrict ia de mai sus se leag a de prima, a i-a  si aj-a imagine. Din capitolele anterioare am
v azut c a restrict iile non-triviale ^ n cazul dreptelor implic a cel put in trei imagini. Cele dou a
restrict ii triliniare de mai sus, sunt echivalente cu restrict ia de rang dac a scalarul `>
jTj6= 0,
adic a ^ n cazuri nedegenerate [1].
^In general, rang (Mi)1 dac a  si numai dac a tot i minorii 2 2, au determinantul egal cu
zero. Din moment ce ace sti minori includ numai trei imagini odat a, se poate trage concluzia
c aorice restrict ie a punctelor de vedere multiple pentru drepte poate  redus a la restrict ii
care implic a numai trei drepte concomitent [5].
2.8.5 Unicitatea pre-imaginii
Obiectivul principal a restrict iei de rang pentru matricea punctelor de vedere multiple Mi
este acela de a asigura c a mpuncte de vedere ale unei drepte corespund consistent unei pre-
imaginiL. Unicitatea pre-imaginii ^ n cazul restrict iilor triliniare poate  caracterizat astfel:
Lem a: Fie trei cadre de camer a cu centrii optici distinct i  si oricare trei vectori `1;`2;`32
R3ce reprezint a trei imagini ale dreptelor date. Dac a cele trei drepte ale imaginii trebuie
satisfac restric ctiile triliniare
`>
jTji`>
kRkjb`i`>
kTkj`>
jRjib`i= 0; i;j;k2f1;2;3g;
atunci pre-imaginea lor Leste unic determinat a except^ and cazul ^ n care pre-imaginea
ec arei`ieste ^ n acela si plan. Acesta este singurl caz degenerat,  si ^ n acest caz, matricea Mi
devine zero [10].
Teorem a: Fie vectorii `i2R3reprezent^ and imaginile dreptelor pentru mcadre ale camerei.
Ei corespund aceleia si drepte ^ n spat iu dac a rangul matriciei Mirelativ la oricare dintre
cadrele camerei este 1. Dac a rangul este 0 (implic^ and c a matricea Mieste zero), atunci
dreapta se va a
a pe planul pe care tot i centrii camerelor trebuie s a se a
e [19].
Per total avem urm atoarele cazuri:
rang (Mi) = 2)nu exist a corespondent  a ^ ntre drepte
rang (Mi) = 1)corespondent  a ^ ntre drepte  si pre-imagine unic a
rang (Mi) = 0)corespondent  a ^ ntre drepte  si pre-imagine neuinic a
14

3 Aplicat ie
3.1 Introducere
Aceasta este o aplicat ie demonstrativ a de reconstruct ie a formelor 3D din puncte de vedere
multiple ce are la baz a o abordare simpl a de modelare spat ial a. Aceast a tehnic a este folosit a,
adesea, atunci c^ and avem nevoie s a reconstruim un model 3D al unui obiect mic care poate
 plasat pe o mas a rotativ a. Putem executa  si folosi, astfel, zeci, chiar  si sute, de imagini.
Tipul acesta de aplicat ie a fost folosit cu foarte mult success in muzee pentru creat ia galeriilor
virtuale online [12].
Creatorul acestei aplicat ii demonstrative este Ben Tordo.
Aplicat ia este disponibil a gratuit pentru uz necomercial [12].
Tehnica de modelare spat ial a saumodelare din siluete este una dintre cele mai de baz a metode
de reconstruct ie 3D. Aceasta va folosi ecare imagine ca o masc a. Un obiect voxel va  plasat
^ n mijlocul scenei  si din ecare imagine se va t aia din obiect tot ce se a
 a ^ n afara siluetei
[20]. Pentru ca aceast a tehnic a s a funct ioneze trebuie s a  stim unde se a
a camera fat  a de
obiect atunci c^ and fotograa a fost f acut a, care este cu totul o problem a separat a [9].
Un voxel este o unitate de informat ie grac a care dene ste un punct ^ n spat iul tridimensional.
Un program de interpretare 3D a imaginilor poate folosi informat ia cont inut a de acel element
grac pentru a ^ l putea vedea din orice punct de vedere [29].
Aceast a tehnic a a fost ranat a^ n ultimul deceniu  si poate  realizat a s a e at^ at computat ional a
c^ at  si eciente din punctul de vedere al memoriei [24].
3.1.1 Date
Imaginile folosite au fost create de c atre Wolfgang Niem, de la Universitatea din Hanovra.
Datele camerei utilizate ^ n acest exemplu au fost create de Dr. A. W. Fitzgibbon  si Prof. A.
Zisserman de la Centrul de Cercetare al Universit at ii din Oxford.
Imaginile  si datele camerei pot  ambele desc arcate de la Grupul de Geometrie Vizual a al
Universit at ii Oxford [16].
3.2 Explicarea aplicat iei
3.2.1 Init ializare
Toate funt iile pentru acest program demonstrativ se vor reg asii ^ n folderul spacecarving  si
toate datele de input necesare ^ n directorul DinosaurData .
1 import spacecarving . ;
2 datadir = f u l l f i l e ( f i l e p a r t s ( mfilename ( ' f u l l p a t h ' ) ) , ' DinosaurData ' ) ;
3close all ;
15

3.2.2 ^Inc arcarea datelor de intrare despre imagini  si camer a
Funct ia loadcameradata() va  folosi t a pentru citirea directorul DinosaurData , ^ nc arc^ and
datele legate de calibrarea intern a  si extern a a camerei  si ecare  sier imagine pentru ecare
camer a. Aceste calibr ari au fost determinate folosind un proces automat de care nu ne vom
lega la momentul de fat  a.
1 cameras = loadcameradata ( datadir )
2
3 montage ( cat ( 4 , cameras . Image ) ) ;
4set(gcf( ) , ' Position ' ,[100 100 600 600] ) axis o f f ;
3.2.3 Convertirea imaginilor ^ n siluete
Imaginea din ecare camer a este convertit a ^ ntr-o imagine binar a folosindu-ne de fundalul
albastru  si de ni ste operatori morfologici pentru a cur at a colt urile. Aceste siluete vor deveni
m a stile ment ionate ^ n introducere. G aurile ^ n aceste m a sti sunt deosebit de periculoase,
deoarece vor face ca voxelii corect i, care fac parte din obiect,  s a e  ster si – putem ajunge s a
g aurim modelul nostru 3D! Pentru a evita orice astfel de inconvenient funct iile din pachetul
Image Processing Toolbox [13], [14] vor  de foarte mare ajutor [9].
1for c =1:numel ( cameras )
2 cameras ( c ) . S i l h o u e t t e = g e t s i l h o u e t t e ( cameras ( c ) . Image ) ;
3end
4
5figure ( ' Position ' ,[100 100 600 3 0 0 ] ) ;
6
7subplot (1 ,2 ,1) imshow ( cameras ( c ) . Image ) ; title ( ' Original Image ' )
8axis o f f
9
10subplot (1 ,2 ,2) imshow ( cameras ( c ) . S i l h o u e t t e ) ; title ( ' S i l h o u e t t e '
11 ) axis o f f
12
13 makeFullAxes ( gcf ) ;
3.2.4 A
area spat iului ocupat de scena
Init ial nu  stim unde s a c autam modelul. Vom presupune c a modelul se a
 a^ n spat iul delimitat
de camere  si direct iile lor principale de vizibilitate. Apoi vom realiza o modelare spat ial a la
o rezolut ie foarte mic a folosind toate camerele pentru a vedea unde se a
 a obiectul [9].
1 [ xlim , ylim , zlim ] = findmodel ( cameras ) ;
3.2.5 Crearea unei matrici voxel
Aceast a funct ie construie ste o ret ea 3D de elemente gata s a e modelate prin t aiere. Ar-
gumentele de intrare seteaz a conturul obiectului  si num arul aproximativ de voxeli de creat.
Din moment ce voxelii trebuie s a e cuburi, num arul real generat ar putea s a e mai mare
sau mai mic. Vom ^ ncepe cu aproximativ 6 milioane de voxeli (^ n caz c a sistemul pe care
ruleaz a aplicat ia ruleaz a nu are ^ ndeajuns a memorie, atunci se propune reducea num arului
de voxeli).
16

Pentru implement ari ^ n lumea real a a model arii spat iale prin t aiere cu sigurant  a nu am
dori s a construim o matrice uniform a 3D ca aceasta. OctTrees  si alte reprezent ari de ranare
sunt mult mai eciente, at^ at din punctul de vedere al memoriei  si al timpului computat ional
[9].
1 voxels = makevoxels ( xlim , ylim , zlim , 6000000 ) ; starting volume =
2 numel ( voxels . XData ) ;
3.2.6 Modelarea prin t aiere a voxelilor cu ajutorul primei imagini
Silueta este proiectat a pe matricea voxel. Orice voxel ce se a
 a ^ nafara siluetei va  eliminat
prin t aiere, l as^ and doar voxelii din interiorul modelului [20]. Folosind doar o camer a, vom
ajunge s a avem o prism a^ n form a de dinozaur – o singur a imagine nu ne poate oferi informat ii
de ad^ ancime [9].
1 voxels = carve ( voxels , cameras (1) ) ;
3.2.7 A sarea rezultatelor
1figure ( ' Position ' ,[100 100 600 3 0 0 ] ) ; subplot (1 ,2 ,1) showscene (
2 cameras (1) , voxels ) ; title ( ' 1 camera ' ) subplot (1 ,2 ,2)
3 showsurface ( voxels ) title ( ' Result a f t e r 1 carving ' )
Ad augarea a mai multe puncte de vedere ne va ajuta s a ran am forma. Dac a vom include
^ nc a dou a sau mai multe vom obt ine o form a mult mai u sor de recunoscut.
1 voxels = carve ( voxels , cameras (4) ) ;
2 voxels = carve ( voxels , cameras (7) ) ;
1figure ( ' Position ' ,[100 100 600 3 0 0 ] ) ;
2subplot (1 ,2 ,1) title ( ' 3cameras ' )
3 showscene ( cameras ( [ 1 4 7 ] ) , voxels ) ;
4subplot (1 ,2 ,2) title ( ' Result a f t e r 3 carvings ' )
5 showsurface ( voxels )
A sarea rezultatului pentru 3 imagini
Acum vom include toate punctele de vedere. ^In acest caz vom avea 36 de puncte de vedere
(distant a dintre ele ind de aproximativ 10 grade) [9]. Putem obt ine un model mai detaliat
dac a am avea ^ n posesie o ma sin a automat a de fotograat, put^ and folosi mai multe imagini
– singura limit a ind timpul necesar pentru calcule  si memoria disponibil a. C^ and folosim o
mas a rotativ a controlat a de calculator (cum sunt folosite ^ n muzee) stocarea acestei ma sini
este singura limitare real a [20].
1for i i =1:numel ( cameras )
2 voxels = carve ( voxels , cameras ( i i ) ) ;
3end figure ( ' Position ' ,[100 100 600 7 0 0 ] ) ; showsurface ( voxels )
4set(gca, ' Position ' ,[ 0.2 0 1.4 0 . 9 5 ] ) axis o f ftitle ( ' Result a f t e r
5 36 carvings ' )
6
17

7 final volume = numel ( voxels . XData ) ;
8fprintf ( ' Final volume i s %d (%1.2 f%%) nn ' , . . .
9 final volume , 100 final volume / starting volume )
3.2.8 Obt inerea de valori reale
Ideal ne dorim o rezolut ie mult mai mare, dar acest lucru ar consuma foarte mult a memorie.
^In schimb vom folosi un truc de atribuire a unei valoari reale ec arui voxel ^ n loc de o valoare
binar a. Vom face asta prin mutarea tuturor voxelilor cu un sfert de p atrat ^ n ecare direct ie
apoi vom vedea dac a vor  t aiat i sau nu. Raportul dintre voxelii decupat i  si cei nedecupat i
pentru ecare voxel ^ i va atribui un scor (care este grosier echivalent cu estimarea a c^ at de
mult din ecare voxel se af a ^ n interiorul siluetei) [9].
1 o f f s e t v e c = 1/3voxels . Resolution [1 0 1 ] ;
2
3 [ o f f x , o f f y , o f f z ] = meshgrid ( o f f s e t v e c , o f f s e t v e c , o f f s e t v e c ) ;
4
5 num voxels = numel ( voxels . Value ) ;
6 num offsets = numel ( o f f x ) ;
7 s c o r e s = zeros ( num voxels , 1 ) ;
8
9for j j =1: num offsets
10 keep = true ( num voxels , 1 ) ;
11 myvoxels = voxels ;
12 myvoxels . XData = voxels . XData + o f f x ( j j ) ;
13 myvoxels . YData = voxels . YData + o f f y ( j j ) ;
14 myvoxels . ZData = voxels . ZData + o f f z ( j j ) ;
15 for i i =1:numel ( cameras )
16 [ ~ , mykeep ] = carve ( myvoxels , cameras ( i i ) ) ;
17 keep ( s e t d i f f ( 1 : num voxels , mykeep ) ) = f a l s e ;
18 end
19
20 s c o r e s ( keep ) = s c o r e s ( keep ) + 1 ;
21end voxels . Value = s c o r e s / num offsets ; figure ( ' Position ' ,[100 100
22 600 7 0 0 ] ) ;
23
24 showsurface ( voxels ) ;
25set(gca, ' Position ' ,[ 0.2 0 1.4 0 . 9 5 ] )
26axis o f f
27title ( ' Result a f t e r 36 carvings with refinement ' )
3.2.9 Rezultat nal
Pentru galeriile online, de exemplu, am dori s a color am ecare voxel din imaginea cu cel
mai bun punct de vedere, adic a cel mai aproape de vectorul normal), astfel vom ajunge s a
color am modelul 3D. Aceast a funct ie nu face nicio diferent  a pentru estimarea volumetric a
[9].
1figure ( ' Position ' ,[100 100 600 7 0 0 ] ) ;
2 ptch = showsurface ( voxels ) ;
3 c o l o r s u r f a c e ( ptch , cameras ) ;
4set(gca, ' Position ' ,[ 0.2 0 1.4 0 . 9 5 ] )
5axis o f f
18

6title ( ' Result a f t e r 36 carvings with refinement and colour ' )
3.3 Explicarea funct iilor folosite
3.3.1 Funct ia ndmodel
Funct ia ndmodel determin a lungimile dreptelor Ox,Oy,Oz^ n care se va a
a modelul ce va
urma s a e modelat prin t aiere. Acest lucru ne va permite s a construim volumul init ial de
voxeli [9].
1function [ xlim , ylim , zlim ] = findmodel ( cameras )
2
3 camera positions = cat ( 2 , cameras .T ) ; xlim = [ min(
4 camera positions ( 1 , : ) ) , max( camera positions ( 1 , : ) ) ] ; ylim = [ min(
5 camera positions ( 2 , : ) ) , max( camera positions ( 2 , : ) ) ] ; zlim = [ min(
6 camera positions ( 3 , : ) ) , max( camera positions ( 3 , : ) ) ] ;
Pentruzlim avem nevoie s a vedem ^ n ce direct ie este orientat a ecare camer a.
1 range = 0.6 sqrt (diff ( xlim ) .^2 + diff ( ylim ) .^2 ) ; for
2 i i =1:numel ( cameras )
3 viewpoint = cameras ( i i ) .T rangespacecarving . getcameradirection (
4 cameras ( i i ) ) ;
5 zlim (1) = min( zlim (1) , viewpoint (3) ) ;
6 zlim (2) = max( zlim (2) , viewpoint (3) ) ;
7end
Mut am limitele spre interior put in, din moment ce obiectul trebuie s a e ^ n interiorul
cercului.
1 xrange = diff ( xlim ) ;
2 xlim = xlim + xrange /4 [11];
3 yrange= diff ( ylim ) ;
4 ylim = ylim + yrange /4 [11];
Acum vom executa o modelare prin t aiere grosier a pentru a vedea unde se a
 a obiectul.
1 voxels = spacecarving . carve ( voxels , cameras ( i i ) ) ; end
Ne asigur am c a a mai r amas ceva din model.
1i f isempty ( voxels . XData )
2 error ( ' SpaceCarving : FindModel ' , ' Nothing l e f t a f t e r i n i t i a l serach ! Check
3
4 your camera matrices . ' ) ; end
Veric am limitele unde am g asit datele  si le m arim rezolut ia.
1 xlim = [ min( voxels . XData) , max( voxels . XData) ] + 2 voxels . Resolution [1 1 ] ;
2 ylim = [ min( voxels . YData) , max( voxels . YData) ] + 2 voxels . Resolution [1 1 ] ;
3 zlim = [ min( voxels . ZData ) , max( voxels . ZData ) ] + 2 voxels . Resolution [1 1 ] ;
3.3.2 Funct ia showcamera
Funct ia showcamera deseneaz a o camer a pe axele specicate.
19

1function showcamera ( ax , camera )
2
3i f nargin <2
4 camera = ax ;
5 ax = gca( ) ;
6end
7
8 s c a l e = 0 . 2 ; subsample = 16;
9
10for c =1:numel ( camera )
11 cam t = camera ( c ) .T;
Desen am centrii camerelor.
1 plot3 ( camera ( c ) .T(1) , camera ( c ) .T(2) , camera ( c ) .T(3) , 'b . ' , ' markersize ' ,5) ;
G asim colt urile imaginii.
1 [ h ,w, colordepth ] = size ( camera ( c ) . Image ) ; % #ok<NASGU >
2 imcorners = [ 0 w 0 w
3 0 0 h h
4 1 1 1 1 ] ;
5 worldcorners = iBackProject ( imcorners , scale , camera ( c ) ) ;
6 iPlotLine ( cam t , worldcorners ( : , 1 ) , 'b ' )
7 hold on
8 iPlotLine ( cam t , worldcorners ( : , 2 ) , 'b ' )
9 iPlotLine ( cam t , worldcorners ( : , 3 ) , 'b ' )
10 iPlotLine ( cam t , worldcorners ( : , 4 ) , 'b ' )
11
Desen am planul imaginii. Vom avea nevoie de coordonatele ec arui pixel pentru a construi
harta de textur a.
1 [ x , y , z ] = meshgrid ( 1 : subsample :w, 1 : subsample : h , 1 ) ;
2 pix = [ x ( : ) , y ( : ) , z ( : ) ] ' ;
3 worldpix = iBackProject ( pix , scale , camera ( c ) ) ;
4 smallim = camera ( c ) . Image ( 1 : subsample : end, 1 : subsample : end, : ) ;
5 surface ( 'XData ' , reshape ( worldpix ( 1 , : ) ,h/subsample ,w/ subsample ) , . . .
6 'YData ' , reshape ( worldpix ( 2 , : ) ,h/subsample ,w/ subsample ) , . . .
7 ' ZData ' , reshape ( worldpix ( 3 , : ) ,h/subsample ,w/ subsample ) , . . .
8 ' FaceColor ' , ' texturemap ' , . . .
9 ' EdgeColor ' , ' none ' , . . .
10 'CData ' , smallim ) ;
11end set ( ax , ' DataAspectRatio ' , [ 1 1 1 ] )
12
Funct ia iBackProject ofer a o distant  a DIST unei locat ii din imagine  si returneaz a locat ia
din spat iul 3D corespunz atoare [9].
1function X = iBackProject ( x , dist , camera )
2
3i f size (x , 1 )==2
4 x = [ x ; ones (1 , size (x , 2 ) ) ] ;
5end
6
7 X = camera .K nx ;
8 normX = sqrt (sum(X.X, 1 ) ) ; X = X . / repmat (normX , size (X, 1 ) ,1) ;
20

9 X = repmat ( camera .T, 1 , size (x , 2 ) )d i s tcamera .R'X;
10
11function iPlotLine ( x0 , x1 , s t y l e ) plot3 ( [ x0 (1) , x1 (1) ] ,
12 [ x0 (2) , x1 (2) ] , [ x0 (3) , x1 (3) ] , s t y l e ) ;
3.3.3 Funct ia decomposeP
Funct ia decompose este folosit a pentru a descompune matricea de proiect ie P^ n matricea
parametrilor de camer a interni K si parametrii externi pentru rotat ie R si translat ie t. Ma-
tricea original a este recompus a ca P=K[R;t].
1function [K,R, t ] = decomposeP (P)
2
3 [ q , r ] = qr(inv(P( 1 : 3 , 1 : 3 ) ) ) ;
4 invK = r ( 1 : 3 , 1 : 3 ) ;
5 R = inv( q ) ;
O matrice de rotat ie ar trebui s a aib a un determinant de unitate, sau doar garanteaz a o
matrice unitar a Q.
1i f det ( R ) <0
2 R =R;
3 invK =invK ;
4end
5 K = inv( invK ) ;
6 t = invKP( : , 4 ) ;
3.3.4 Funct ia colorsurface
Funct ia colorsurface coloreaz a toate fragmentele vertex ale buc at ii de suprafat  a folosind cel
mai apropiat pixel al imaginii din una din camere [9].
1function c o l o r s u r f a c e ( ptch , cameras )
2
3error (nargchk ( 2 , 2 , nargin ) ) ;
4
5i f~ ishandle ( ptch ) jj~ strcmpi ( get( ptch , 'Type ' ) , ' patch ' )
6 error ( 'COLORSURFACE: BadPatch ' , ' F i r s t argument must the handle to a patch
object created using the PATCH command ' ) ;
7end
8
9 v e r t i c e s = get( ptch , ' V e r t i c e s ' ) ;
10 normals = get( ptch , ' VertexNormals ' ) ;
11 num vertices = size ( v e r t i c e s , 1 ) ;
Obt inerea ec arui vector de punct de vedere de la ecare camer a.
1 num cameras = numel ( cameras ) ;
2 cam normals = zeros ( 3 , num cameras ) ;
3
4for i i =1:num cameras
5 cam normals ( : , i i ) = spacecarving . getcameradirection ( cameras ( i i ) ) ;
6end
21

Pentru ecare vertex, ne vom folosi de normal a pentru a g asi cea mai potrivit a camer a  si
apoi c autam valoarea asociat a [20].
1 vertexcdata = zeros ( num vertices , 3 ) ; for i i =1: num vertices
Produsul cu punct va  folosit pentru a g asi cea mai bun a camer a.
1 angles = normals ( i i , : ) cam normals . / norm ( normals ( i i , : ) ) ;
2 [ ~ , cam idx ] = min( angles ) ;
Vertexul va  proiectat ^ n camera proiectat a.
1 [ imx , imy ] = spacecarving . p r o j e c t ( cameras ( cam idx ) , . . .
2 v e r t i c e s ( i i , 1 ) , v e r t i c e s ( i i , 2 ) , v e r t i c e s ( i i , 3 ) ) ;
3 vertexcdata ( i i , : ) = double ( cameras ( cam idx ) . Image ( round ( imy ) , round ( imx )
, : ) ) /255;
4end
Plasarea ^ n bucata de suprafat  a.
1set( ptch , ' FaceVertexCData ' , vertexcdata , ' FaceColor ' , ' i n t e r p ' ) ;
3.3.5 Funct ia showsurface
Funct ia showsurface deseneaz a o suprafat  a pe baza structurii de voxeli existent a folosindu-se
de comanda MatLab ISOSURFACE .
1function ptch = showsurface ( voxels )
Prima ret ea de date.
1 ux = unique ( voxels . XData) ;
2 uy = unique ( voxels . YData) ;
3 uz = unique ( voxels . ZData ) ;
Extinderea modelului cu un pas ^ n ecare direct ie.
1 ux = [ ux (1) voxels . Resolution ; ux ; ux ( end)+voxels . Resolution ] ;
2 uy = [ uy (1) voxels . Resolution ; uy ; uy ( end)+voxels . Resolution ] ;
3 uz = [ uz (1) voxels . Resolution ; uz ; uz ( end)+voxels . Resolution ] ;
Convertirea ^ ntr-o retea.
1 in voxels [X,Y, Z ] = meshgrid ( ux , uy , uz ) ;
Crearea unei ret ele voxel goale, apoi umplerea lor cu valorile prezente ^ n voxeli.
1 in voxels V = zeros (size ( X ) ) ; N = numel ( voxels . XData ) ; for
2 i i =1:N
3 ix = ( ux == voxels . XData( i i ) ) ;
4 iy = ( uy == voxels . YData( i i ) ) ;
5 i z = ( uz == voxels . ZData ( i i ) ) ;
6 V( iy , ix , i z ) = voxels . Value ( i i ) ;
7end
8
Desenarea.
22

1 ptch = patch ( i s o s u r f a c e ( X, Y, Z , V, 0.5 ) ) ; isonormals ( X, Y, Z ,
2 V, ptch ) set( ptch , ' FaceColor ' , ' g ' , ' EdgeColor ' , ' none ' ) ;
3
4set(gca, ' DataAspectRatio ' , [ 1 1 1 ] ) ; xlabel ( 'X ' ) ; ylabel ( 'Y ' ) ;
5zlabel ( 'Z ' ) ; view (140 ,22) l i g h t i n g ( ' gouraud ' ) camlight ( ' r i g h t ' )
6axis ( ' t i g h t ' )
3.3.6 Funct ia showscene
Funct ia showscene are ca scop a sarea listei specicate de camere  si a modelului actual ca o
suprafat  a aranjat a ^ n jurul voxelilor.
1function showscene ( cameras , voxels )
2
3error (nargchk ( 1 , 2 , nargin ) ) ;
Plotarea ec arui centru de camer a.
1set(gca, ' DataAspectRatio ' , [ 1 1 1 ] ) hold on
2
3 N = numel ( cameras ) ; for i i =1:N
4 spacecarving . showcamera ( cameras ( i i ) ) ;
5end xlabel ( 'X ' ) ylabel ( 'Y ' ) zlabel ( 'Z ' )
A sarea unei suprafet e ^ n jurul obiectului se va face astfel:
1i f nargin >1 && ~ isempty ( voxels )
2 spacecarving . showsurface ( voxels ) ;
3end
Iluminarea reprezent arii  si ajustarea unghiului de vizualizare pentru o interpretare mai
u soar a.
1view (3) ;
2grid on ;
3 l i g h t ( ' Position ' , [ 0 0 1 ] ) ;
4axis t i g h t
3.3.7 Funct ia project
Funct ia project va proiecta unul sau mai multe puncte 3D ^ ntr-o imagine. Din codul de mai
sus [x;y] reprezint a coordonatele unui punct 2D din imagine, iar (camera, voxels.XData,
voxels.YData, voxels.ZData) reprezint a datele camerei  si coordonatele punctului 3D ce urmeaz a
s a e proiectat.
1function [ im x , im y ] = p r o j e c t ( camera , world X , world Y , world Z )
2
3 z = camera . rawP (3 ,1) world X . . .
4 + camera . rawP (3 ,2) world Y . . .
5 + camera . rawP (3 ,3) world Z . . .
6 + camera . rawP (3 ,4) ;
7 im y =round ( ( camera . rawP (2 ,1) world X . . .
8 + camera . rawP (2 ,2) world Y . . .
9 + camera . rawP (2 ,3) world Z . . .
10 + camera . rawP (2 ,4) ) . / z ) ;
23

11 im x =round ( ( camera . rawP (1 ,1) world X . . .
12 + camera . rawP (1 ,2) world Y . . .
13 + camera . rawP (1 ,3) world Z . . .
14 + camera . rawP (1 ,4) ) . / z ) ;
3.3.8 Funct ia makevoxels
Funct ia makevoxels(xlim, ylim, zlim, N) creaz a o matrice uniform a de voxeli ce va urma s a e
t aiat a. Comanda voxels = makevoxels(N) va crea o ret ea 3D de voxeli de m arimea NNN
^ ntr-un volum predenit.
1function voxels = makevoxels ( xlim , ylim , zlim ,N)
2
3error (nargchk ( 4 , 4 , nargin ) ) ;
Trebuie s a construim voxelii ^ n form a de cub, astfel trebuie s a alegem o rezolut ie care s a ne
ofere aproximativ N voxeli.
1 volume = diff ( xlim )diff ( ylim )diff ( zlim ) ;
2 voxels . Resolution = power ( volume/N, 1/3 ) ; x = xlim (1) :
3 voxels . Resolution : xlim (2) ; y = ylim (1) : voxels . Resolution :
4 ylim (2) ; z = zlim (1) : voxels . Resolution : zlim (2) ;
5
6
7 [X,Y, Z ] = meshgrid ( x , y , z ) ; voxels . XData = X( : ) ; voxels . YData =
8 Y( : ) ; voxels . ZData = Z ( : ) ; voxels . Value = ones ( numel (X) ,1) ;
3.3.9 Funct ia carve
Funct ia carve modeleaz a prin t aiere voxelii care nu sunt ^ n silueta generat a de camer a. Rezul-
tatul va  o matrice de voxeli numit a voxels ^ n acest caz.
O alt a metod a de a folosi aceast a funct ie este
[voxels;keep ] =carve (voxels;camera )
care va returna  si indicii voxelilor care au fost p astrat i. Proiectarea ^ n imagine.
1function [ voxels , keep ] = carve ( voxels , camera )
2
3 [ x , y ] = spacecarving . p r o j e c t ( camera , voxels . XData ,
4 voxels . YData , voxels . ZData ) ;
Cur at area voxelilor ce nu se reg asesc ^ n imagine deloc.
1 [ h ,w, d ] = size ( camera . Image ) ; % #ok<NASGU >
2 keep = find ( (x>=1) & (x <= w) & (y >=1) & (y <=h) ) ; x = x ( keep ) ; y =
3 y ( keep ) ;
Aceast a sect iune de cod va cur at a tot ce nu se a
 a ^ n interiorul siluetei.
1 ind = sub2ind ( [ h ,w] , round ( y ) , round ( x ) ) ;
2 keep = keep ( camera . S i l h o u e t t e ( ind ) >= 1) ;
3
4 voxels . XData = voxels . XData( keep ) ;
5 voxels . YData = voxels . YData( keep ) ;
6 voxels . ZData = voxels . ZData ( keep ) ;
7 voxels . Value = voxels . Value ( keep ) ;
24

3.3.10 Funct ia getcameradirection
Funct ia getcameradirection va returna directt ia de orientare a unei camere.
1function dirn = getcameradirection ( camera )
Vom g asi centrul ^ n coordonatele imaginii.
1 x = [
2 size ( camera . Image , 2 ) / 2
3 size ( camera . Image , 1 ) / 2
4 1.0
5 ] ;
6
7 X = camera .K nx ;
8 X = camera .R' X;
9 dirn = X . / norm ( X ) ;
3.3.11 Funct ia getsilhouette
Funct a getsilhouette g ase ste silueta unui obiect centrat ^ n imagine.
1function S = g e t s i l h o u e t t e (im)
2
3 [ h ,w, d ] = size (im) ;
Segmentarea init ial a e bazat a mai mult pe ro su dec^ at pe albastru.
1 S = im ( : , : , 1 ) >(im ( : , : , 3 )2) ;
^Indep artarea regiunilor care ating conturul sau mai mici dec^ at 10% din aria imaginii.
1 S = imclearborder (S) ; S = bwareaopen (S , ceil (hw/10) ) ;
^Indep artarea g aurilor <1% din aria imaginii.
1 S = ~bwareaopen (~S , ceil (hw/100) ) ;
3.3.12 Funct ia makeFullAxes
Funct ia makeFullAxes dezactiveaz a etichetele pentru axele ^ n AXH  si modic a axele astfel
^ nc^ at s a ocupe tot spat iul disponibil. ^In termeni generali asta ^ nseamn a setarea pozit iei ax-
elor respective s a e axele din exterior.
Modic^ and parametrul axhcufigh va aplica aceste schimb ari tuturor axelor din gura
FIGH.
1function makeFullAxes ( axh )
2
3i fstrcmpi ( get( axh , ' type ' ) , ' f i g u r e ' )
4 axh = f i n d o b j ( axh , ' type ' , ' axes ' ) ;
5end axis ( axh , ' o f f ' ) ;
Vom presupune c a toate axele vor avea m arimi egale.
25

1i fnumel ( axh ) >1
2 outPos = cell2mat ( get( axh , ' OuterPosition ' ) ) ;
3 width = min( outPos ( : , 3 ) ) ;
4 height = min( outPos ( : , 4 ) ) ;
5 outPos ( : , 3 ) = width ;
6 outPos ( : , 4 ) = height ;
7 for i i =1:numel ( axh )
8 set( axh ( i i ) , ' Position ' , outPos ( i i , : ) ) ;
9 end
10else
11 myPos = get( axh , ' OuterPosition ' ) ;
12 myPos ( 1 : 2 ) = max( myPos ( 1 : 2 ) , [ 0 0 ] ) ;
13 myPos ( 3 : 4 ) = min( myPos ( 3 : 4 ) , [ 1 1 ] ) ;
14 set( axh , ' Position ' , myPos ) ;
15end
3.4 Rezultate experimentale
Aplicat ia a fost testat a pentru a vedea cum se comport a atunci c^ and setul de imagini expe-
rimentale folosite a fost defectuos. Imaginile originale au fost astfel importate  si modicate
^ n programul de editare de imagini Photoshop CS6TM. Modic arile efectuate au fost f acute
pentru a simula seturi de imagini blurate, subexpuse  si cu zgomot, exemple de alter ari ce pot
afecta procedeul de reconstruct ie 3D.
^Intregul set de imagini este ^ n formatul Portable Pixel Map (.ppm). Acesta este un format
vechi  si relativ inecient ^ n viat a de zi cu zi, precum cont ine foarte multe informat ii pe care
ochiul uman nu le poate distinge. ^In plus, formatul nu ofer a prea multe informat ii ^ n afar a
de culorile de baz a, ceea ce ^ nseamn a c a ar putea  nevoie s a adaugi manual informat ii cheie
lelor respective pentru a putea  folosit cu mai multe scopuri ^ n g^ and. ^In schimb, este foarte
usor s a scrii  si analizezi programe concepute special s a lucreze cu acest format, precum pot
 modicate s a cont in a numai culorile pe care diverse aparate de m asur a le folosesc pentru
a extrage informat iile necesare [18].
Fi sierul dino ps.mat cont ine matricele camerelor, formate din elemente precum distant a a
focal a  si distant a dintre camere. Toate aceste informat ii sunt codate ^ n format binar pentru
o mai rapid a folosire.
3.4.1 Cazul setului de imagini original
Pentru a putea ^ ncepe procesul de reconstruct ie 3D cu aceast a aplicat ie avem nevoie de setul
de 36 de imagini si  sierul cu date intrinseci  si extrinseci ale camerei.
Pentru^ nceput, vom folosi un set de imagini optime pentru setarea standardului de comparat ie.
Imaginile^ n format .ppm vor  depozitate^ n  sierul DinosaurData ,^ mpreun a cu dino ps.mat
pentru a putea  preluate de aplicat ia MatLabR
.
26

Exemplu imagine din setul original
^In continuare, vom rula programul principal space carving demo.m cu ajutorul software-
ului MatLabR
.
Aplicat ia odat a rulat a va ^ nc arca toate datele necesare reconstruct iei  si va a sa ^ n prima
gur a setul de imagini aranjat ^ ntr-o matrice p atratic a de grad 6.
Set imagini originale
27

A doua gur a a sat a reprezint a silueta primei imagini din set. Aceast a silueta c^ at si
celelalte 35 vor  folosite ^ n procesul de t aiere al obiectului format din voxeli cu ajutorul
funct iei carve .
Silueta primei imagini din set
A treia gur a ne va descrie pozit ia tuturor camerelor  si a obiectului format din voxeli,
conform funt iilor showscene  sishowcamera .
Plasarea camerelor  si a obiectelor ^ n spat iu
Dup a cum se poate observa, folosindu-se de informat iile din  sierul dino ps.mat  si funct ia
loadcameradata camerele au fost asezate la aproximativ 10 grade una fat  a de cealalt a ^ n jurul
obiectului ce va urma s a e t aiat.
28

A patra gur a ne descrie procesul de t aiere a obiectului format din voxeli pe baza siluetei
pentru o singur a imagine, descris a ^ n fuct ia carve .
Obiect dup a o t aietur a
^In partea st^ ang a a gurii putem observa pozit ionarea camerei dup a care s-a realizat silueta
folosit a ^ n procesul de t aiere ^ mpreun a cu obiectul voxel t aiat. ^In partea dreapt a este a sat
rezultatul t aieturii f ar a alte elemente perturbatoare.
A cincea gur a descrie o situat ie identic a cu cea de la gura patru, ^ ns a doar pentru 3
camere.
Obiect dup a 3 t aieturi
^In aceast a gur a se poate observa c a executarea t aieturilor din mai multe puncte de vedere
apropiate ofer a un rezultat mult mai u sor reconscibil.
29

A  sasea gur a ne arat a rezultatul dupa toate cele 36 de t aieturi.
Obiect dup a 36 t aieturi
Obiectul rezultat poate  distins clar ca ind un dinozaur, ^ ns a forma acestuia nu este ^ nc a
ranat a din cauza formei cubice ale voxelilor component i.
A  saptea gur a ne a seaz a rezultatul netezit al t aieturilor.
Obiect netezit
30

^In ultima gur a putem vedea dinozaurul texturat cu ajutorul funt iei colorsurface .
Obiect texturat
.
3.4.2 Cazul setului de imagini blurate
Pentru a obt ine imagini blurate articial putem altera imaginile originale ^ n PhotoshopTM.
Acest lucru se poate realiza ^ n felul urm ator:
1. Cre am un folder nou ^ n care s a depozit am imaginile modicate;
2. Deschidem Photoshop CS6TM;
3. Import am o imagine din setul original;
4. Filter Blur Box Blur…;
5. Introducem valoarea 3;
6. Salv am imaginea ^ n folderul nou creat;
7. Repet am procesul pentru restul celorlalte 35 de imagini;
8.^Inlocuim numele folderului nou cu cel original  si copiem  sierul dinops:mat .
31

Exemplu imagine blurat a
Prima diferent  a fat  a de original apare la nivelul siluetei.
Comparat ie siluete original a  si blurat a
Din c^ ate se poate observa, la nivelul ghearelor, falangele nu mai sunt separate, iar, solzii de
pe coad a  si spate nu mai sunt la fel de detaliat i.
32

O a doua diferent  a apare la rezultatul nal al celor 36 de t aieturi.
Comparat ie 36 t aieturi ^ ntre setul original (st^ anga)  si cel blurat (dreapta)
La nivelul botului se poate observa c a mandibula apare mic sorat a  si modicat a de form a. De
asemenea o pierdere de informat ii poate  observat a  si la nivelul solzilor de pe spate, coad a
 si gheare.
Datorit a acestui fenomen, atunci c^ and funct ia de nisare act ioneaz a asupra obiectului,
aceasta va decupa fragmentul de mandibul a ce plutea ^ n gura anterioar a.
Obiect nisat (blur)
33

O ultim a diferent  a fat  a de gura original a se poate observa la etapa de texturare a obiec-
tului.
Obiect texturat (blur)
Dup a cum se poate observa, detaliile ce t in de culoarea texturii au suferit pierderi. Din
moment ce efectul de blur a afectat elementele de contur ale imaginilor  si culorile specice
unor anumite zone au ajuns s a e afectate.
3.4.3 Cazul setului de imagini subexpuse
Pentru a obt ine imagini subexpuse putem altera imaginile originale ^ n PhotoshopTM. Acest
lucru se poate realiza ^ n felul urm ator:
1. Cre am un folder nou ^ n care s a depozit am imaginile modicate;
2. Deschidem Photoshop CS6TM;
3. Import am o imagine din setul original;
4. Image Adjustment Exposure;
5. Introducem valoarea 3:00;
6. Salv am imaginea ^ n folderul nou creat;
7. Repet am procesul pentru restul celorlalte 35 de imagini;
34

8.^Inlocuim numele folderului nou cu cel original  si copiem  sierul dinops:mat .
Din c^ ate se poate observa din imaginea urm atoare, nu exista diferent e la nivelul siluetei,
^ ntre folosirea setului original  si cel subexpus.
Silueta obiectului (subexpunere)
Din moment ce nu exist a diferent e la nivelul siluetei, nu exist a diferent e nici ^ ntre rezul-
tatele model arii.
Comparat ie modelare set imagini original  si subexpus
Imaginea de pe partea st^ ang a este rezultatul cu setul de imagini original, iar cea din dreapta
cel pentru subexpuse.
35

Singurul loc unde exist a o diferent  a vizibil a ^ ntre cele dou a cazuri este la nivelul textur arii
dinozaurului.
Rezutat texturare (subexpus)
Deoarece imaginea subexpus a este mai ^ ntunecat a  si culorile rezultate ^ n urma textur arii sunt
mai ^ ntunecate.
3.4.4 Cazul setului de imagini cu zgomot
Pentru a obt ine imagini cu zgomot simulat putem altera imaginile originale ^ n PhotoshopTM.
Acest lucru se poate realiza ^ n felul urm ator:
1. Cre am un folder nou ^ n care s a depozit am imaginile modicate;
2. Deschidem Photoshop CS6TM;
3. Import am o imagine din setul original;
4. Filter Noise Add Noise…;
5. Introducem valoarea 10%;
6. Select am zgomotul alb-negru;
7. Salv am imaginea ^ n folderul nou creat;
36

8. Repet am procesul pentru restul celorlalte 35 de imagini;
9.^Inlocuim numele folderului nou cu cel original  si copiem  sierul dinops:mat .
Set imagini cu zgomot alb-negru
Dup a cum se poate vedea, setul de imagini este vizibil alterat de zgomot. Acest lucru nu
pare s a  afectat forma siluetei, ^ ns a.
Silueta obiectului (zgomot)
37

Silueta neind afectat a, nici rezultatul model arii nu a fost afectat.
Obiect texturat (zgomot)
Procesul de texturare pare s a e neafectat.
4 Concluzii
Subiectul reconstruct iei 3D din multiple imagini a fost abordat din dorint a de a g asi o metod a
mult mai simpl a  si rapid a de modelare 3D, dec^ at cea convent ional a (manual a), cu scopul de
a vedea dac a chiar  si o persoan a f ar a not iuni de modelare 3D  si echipamente specializate ar
putea s a obt in a rezultate comparabile sau chiar mult mai eciente. ^In urma cercet arilor efec-
tuate ^ n jurul acestui subiect, dovezi ale ecacit at ii  si disponibilit at ii not iunilor teoretice  si a
aplicat iilor demonstrative au fost numeroase. Toate informat iile descoperite au fost concrete
 si explicite, iar mare parte a aplicat iilor s-au dovedit a ind opensource.
Aplicat ia demonstrativ a opensource prezentat a ^ n aceast a lucrare de licent  a, dezvoltat a
de Ben Tordo [12], reprezint a exemplul inedit care s a conrme faptul c a reconstruct ia 3D
din multiple imagini este o solut ie alternativ a facil a, ieftin a  si mai rapid a dec^ at modelarea 3D
manual a. Aceast a aplicat ie a fost conceput a ^ ntr-un soft licent iat, MatLabR
, ^ nsa el poate
38

rulat ecient  si ^ n Octave [15], software opensource. Datele necesare reconstruct iei sunt u sor
de procurat  si creat [2], grat ie disponibilit at ii gratuite a ghidurilor de realizare a seturilor
de imagini sau din cauza existent ei a foarte multe seturi predenite de date pe internet [16],
[3]. Odat a introduse datele, aplicat iei ^ i va lua ^ n jur de 40 de secunde pentru a realiza o
reconstruct ie 3D din 36 de imagini pe un laptop cu procesor IntelTMcore I5. Aplicat ia are o
limitare, ^ ns a pentru a obt ine rezultate c^ at mai reu site, este nevoie de un set mai mare de
imagini, care, la r^ andul lui, ar face ca programul s a ruleze mai greu, ^ ns a, fat  a de modelarea
manual a ^ ntr-un soft specializat, tot este mult mai rapid a  si mai ecient a din punctul de
vedere al resurselor.
^In urma rezultatelor experimentale, am putut observa c a aplicat ia poate face fat  a unor
imagini de o calitate ce ar putea  considerate subobtime, ^ n mod normal. ^In cazul setului
de imagini cu zgomot alb-negru, aplicat ia a reu sit s a ofere un rezultat optim, neexist^ and nici
un tip de discrepant  a ^ ntre rezultatele setului cu zgomot  si cel de imagini originale. Rezul-
tatele setului de imagini subexpus au fost asem an atoare cu cele setului de imagini original,
discrepant e au ap arut la nivelul texturii, care a fost mult mai ^ ntunecat a dec^ at s-ar  dorit.
Setul de imagini cu blur a oferit cele mai slabe rezultate, obiectul reconstruit suferind viz-
ibil ^ n zonele detaliate ale obiectului folosit. Av^ and ^ n vedere aceste rezultate, aplicat ia de
reconstruct ie 3D s-a dovedit s a e  si abil a ^ n cazul ^ n care setul de imagini ar  fost prelevat
^ ntr-un mod inecient.
^In concluzie, reconstruct ia 3D din multiple imagini reprezint a o metod a viabil a ^ n contrast
cu reconstruct ia 3D manual a.
39

5 Anex a
1
2% Author : Ben Tordoff
3%
4% Copyright 2005 2009 The MathWorks , Inc .
5
6
7
8
9
10 datadir = f u l l f i l e ( f i l e p a r t s ( mfilename ( ' f u l l p a t h ' ) ) ,
11 ' DinosaurData ' ) ;
12close all ;
13
14
15 cameras = loadcameradata ( datadir )
16
17 montage ( cat ( 4 , cameras . Image ) ) ; set(gcf( ) , ' Position ' , [100 100
18 600 600] ) axis o f f ;
19
20
21for c =1:numel ( cameras )
22 cameras ( c ) . S i l h o u e t t e = g e t s i l h o u e t t e ( cameras ( c ) . Image ) ;
23end
24
25figure ( ' Position ' ,[100 100 600 3 0 0 ] ) ;
26
27subplot (1 ,2 ,1) imshow ( cameras ( c ) . Image ) ; title ( ' Original Image ' )
28axis o f f
29
30subplot (1 ,2 ,2) imshow ( cameras ( c ) . S i l h o u e t t e ) ; title ( ' S i l h o u e t t e '
31 ) axis o f f
32
33 makeFullAxes ( gcf ) ;
34
35
36 [ xlim , ylim , zlim ] = findmodel ( cameras ) ;
37
38
39 voxels = makevoxels ( xlim , ylim , zlim , 6000000 ) ; starting volume =
40 numel ( voxels . XData ) ;
41
42figure ( ' Position ' ,[100 100 600 4 0 0 ] ) ; showscene ( cameras , voxels ) ;
43
44
45 voxels = carve ( voxels , cameras (1) ) ;
46
47
48figure ( ' Position ' ,[100 100 600 3 0 0 ] ) ; subplot (1 ,2 ,1) showscene (
49 cameras (1) , voxels ) ; title ( ' 1 camera ' ) subplot (1 ,2 ,2)
50 showsurface ( voxels ) title ( ' Result a f t e r 1 carving ' )
51
52
53 voxels = carve ( voxels , cameras (4) ) ; voxels = carve ( voxels ,
54 cameras (7) ) ;
40

55
56
57figure ( ' Position ' ,[100 100 600 3 0 0 ] ) ; subplot (1 ,2 ,1) title ( ' 3
58 cameras ' ) showscene ( cameras ( [ 1 4 7 ] ) , voxels ) ; subplot (1 ,2 ,2)
59 showsurface ( voxels ) title ( ' Result a f t e r 3 carvings ' )
60
61
62
63for i i =1:numel ( cameras )
64 voxels = carve ( voxels , cameras ( i i ) ) ;
65end figure ( ' Position ' ,[100 100 600 7 0 0 ] ) ; showsurface ( voxels )
66set(gca, ' Position ' ,[ 0.2 0 1.4 0 . 9 5 ] ) axis o f ftitle ( ' Result a f t e r
67 36 carvings ' )
68
69 final volume = numel ( voxels . XData ) ;
70fprintf ( ' Final volume i s %d (%1.2 f%%) nn ' , . . .
71 final volume , 100 final volume / starting volume )
72
73
74 o f f s e t v e c = 1/3voxels . Resolution [1 0 1 ] ; [ o f f x , o f f y ,
75 o f f z ] = meshgrid ( o f f s e t v e c , o f f s e t v e c , o f f s e t v e c ) ;
76
77 num voxels = numel ( voxels . Value ) ; num offsets = numel ( o f f x ) ;
78 s c o r e s = zeros ( num voxels , 1 ) ; for j j =1: num offsets
79 keep = true ( num voxels , 1 ) ;
80 myvoxels = voxels ;
81 myvoxels . XData = voxels . XData + o f f x ( j j ) ;
82 myvoxels . YData = voxels . YData + o f f y ( j j ) ;
83 myvoxels . ZData = voxels . ZData + o f f z ( j j ) ;
84 for i i =1:numel ( cameras )
85 [ ~ , mykeep ] = carve ( myvoxels , cameras ( i i ) ) ;
86 keep ( s e t d i f f ( 1 : num voxels , mykeep ) ) = f a l s e ;
87 end
88 s c o r e s ( keep ) = s c o r e s ( keep ) + 1 ;
89end voxels . Value = s c o r e s / num offsets ; figure ( ' Position ' ,[100 100
90 600 7 0 0 ] ) ; showsurface ( voxels ) ; set(gca, ' Position ' ,[ 0.2 0 1.4
91 0 . 9 5 ] ) axis o f ftitle ( ' Result a f t e r 36 carvings with refinement ' )
92
93
94
95figure ( ' Position ' ,[100 100 600 7 0 0 ] ) ; ptch = showsurface ( voxels ) ;
96 c o l o r s u r f a c e ( ptch , cameras ) ; set(gca, ' Position ' ,[ 0.2 0 1.4 0 . 9 5 ] )
97axis o f ftitle ( ' Result a f t e r 36 carvings with refinement and
98 colour ' )
41

References
[1] D. Cremers, Multiple View Geometry , Technische Universit at M unchen, 2013,

[2] Y. Furukawa, Multi-View Stereo: A Tutorial , Washington University in St. Louis,
http://www.cse.wustl.edu/ furukawa/papers/fnt mvs.pdf
[3] Y. Furukawa, J. Ponce, 3D Photography Dataset , Beckman Institute and De-
partment of Computer Science University of Illinois at Urbana-Champaign,
http://www.cs.wustl.edu/ furukawa/research/mview/index.html
[4] R. Hartley, A. Zisserman, Multiple View Geometry in Computer Vision, 2nd Edition ,
Cambridge University Press 2000, 2003
[5] R. Hartley, A linear method for reconstruction from lines and points , International Con-
ference in Computer Vision, 1995
[6] R. Hartley, Lines and Points in Three Views and the
Trifocal Tensor , G.E. CRDM Schenectady, NY, 12301
pdfs.semanticscholar.org/6d47/e8ae644db2eff3d6aa58d82b8980eaa66b77.pdf
[7] P. Heise, B. Jensen, S. Klose, A. Knoll, Variational PatchMatch MultiView Reconstruction
and Renement , Department of Informatics, Technische Universit at M unchen, Germany,
http://www6.in.tum.de/Main/Publications/Heise2015.pdf
[8] K. Kolev, M. Klodt, T. Brox, S. Esedoglu, D. Cremers, Continuous Global Opti-
mization in Multiview 3D Reconstruction , Department of Computer Science, Univer-
sity of Bonn, Germany Department of Mathematics, University of Michigan, USA,
http://www.math.lsa.umich.edu/ esedoglu/Papers Preprints/emmcvpr2007.pdf
[9] A. Ladikos, Multi-View 3D-Reconstruction , Computer Aided Medical Procedures
(CAMP), Technische Universit at M unchen, Germany,
http://campar.in.tum.de/twiki/pub/Chair/TeachingWs09Cv2/MultiView3DReconstruction.pdf
[10] Y. Ma, J. Soatto, S. Kosecka, S. Sastry, An Invitation to 3D Vision , 2004,
https://www.eecis.udel.edu/ cer/arv/readings/old mkss.pdf
[11] J. Mao and L. Xu, Automatic 3D Reconstruction via Object Detection and 3D Trans-
formable Model Matching CS 269 Class Project Report , University of California, Los
Angeles,
http://www.stat.ucla.edu/ junhua.mao/misc files/ProjectReport Automatic 3DReconstruction Junhua MaoLunbo Xu.pdf
[12] Mathworks, B. Tordo, Dinosaur Carving ,
https://www.mathworks.com/matlabcentral/fileexchange/26160-carving-a-dinosaur
[13] Mathworks, Image Processing Toolbox
http://www.mathworks.com/access/helpdesk/help/toolbox/images/bwareaopen.html
[14] Mathworks, imclose ,
http://www.mathworks.com/access/helpdesk/help/toolbox/images/imclose.html
42

[15] Octave, Scientic Programming Language
https://www.gnu.org/software/octave/
[16] Oxford Computer Vision Group, data, Oxford University,
http://www.robots.ox.ac.uk/ vgg/data/data-mview.html
[17] Photogrammetry, Photogrammetry
http://www.photogrammetry.com/
[18] Sourceforge, PPM – Netpbm color image format ,
http://netpbm.sourceforge.net/doc/ppm.html
[19] C. Rother, Multi-view Reconstruction and Camera Recovery using a
Real or Virtual Reerence Plane , Phd. thesis, Computational Vision
and Active Perception Laboratory, Kungl Tekniska Hogskolan, 2003
http://www6.in.tum.de/Main/Publications/Heise2015.pdf
[20] S. Savarese, M. Andreetto, H. Rushmeier, F. Bernardini, P. Perona 3D Reconstruction
by Shadow Carving: Theory and Practical Evaluation , California Institute of Technology,
2006
http://www.vision.caltech.edu/savarese/papers web/shadow carving 06.pdf
[21] A. Saxena, M. Sun and A. Y. Ng, Make3D: Learning 3D Scene Structure from a Single
Still Image , Computer Science Department, Stanford University, Stanford,
http://www.cs.cornell.edu/ asaxena/reconstruction3d/saxena make3d learning3dstructure.pdf
[22] Stackover
ow, How to create 3D model from 2D image ,
http://stackoverflow.com/questions/7705377/how-to-create-3d-model-from-2d-image
[23] L. Torresani, D. Yang, G. Alexander, C. Bregler, Tracking and modeling non rigid objects
with rank contraints , Computer Science Department, Stanford University, Stanford,
xenon.stanford.edu/ dbyang/tyab-cvrp01.pdf
[24] A. Ya sar, U. Ylmaz, V. Atalay, Silhouette-based 3D Model Reconstruction from Multiple Im-
ages, IEEE TRANSACTIONS ON SYSTEMS, MAN AND CYBERNETICS, PART B,
https://www.cv.tu-berlin.de/fileadmin/fg140/Silhouette-based 3D.pdf
[25] R. Zhao, Y. Wang, A. M. Martinez, A Simple, Fast and Highly-Accurate Algorithm to
Recover 3D Shape from 2D Landmarks on a Single Image , Department of Electrical and
Computer Engineering, The Ohio State University, Columbus, OH, 43210,
https://arxiv.org/pdf/1609.09058.pdf
[26] Wikipedia, 3D Reconstruction from Multiple Images ,
https://en.wikipedia.org/wiki/3D reconstruction from multiple images
[27] Wikipedia, 3D Reconstruction ,https://www.wikipedia.org/wiki/3D reconstruction
[28] Wikipedia, Distortions (optics) ,
https://en.wikipedia.org/wiki/Distortion (optics)
[29] Whatis, Voxel ,
http://whatis.techtarget.com/definition/voxel
43

Index
matrice supradiagonal a nul a, 6
ad^ ancimea punctului, 4
algoritm 8 puncte, 12
blur, 26
camere necalibrate, 8
cazuri degenerate, 10
coimagine, 8
Computer Vision, 3
condit ii complete, 5
coordonate omogene, 4, 5
decupare, 18
decient  a de rang, 13
determinant de unitate, 21
ecuat ii triliniare, 10
extrinsec, 26
nisare, 30
hart a de textur a, 20
imagine ca masc a, 15
informat ie de ad^ ancime, 3
intrinsec, 26
ISOSURFACE, 22
liniar dependent  a, 6
map ari 3D, 3
matrice de proiect ie ale formei, 8
matricea de proiect ie din puncte de vedere
multiple, 6
matricea imaginii, 6
mi sc arile camerei, 6
model tridimensional, 3
netezire, 30
operatori morfologici, 16
parametrii camerei, 5
parametrii intrinseci, 4
plan 2D, 3
ppm, 26
preimagine, 4preimagine a unui punct, 4
proiect ia generic a, 4
proiect ii, 3
rang maximal, 6, 10
rangul restrict iei, 7
ret ea de date, 22
restrict ia de rang, 7
restrict ia trilinar a, 10
restrict ii, 5
restrict ii de rang, 13
restrict ii non-triviale, 14
rezolut ie, 19
scala de ad^ ncime a vectorului, 6
scene 3D, 3
SE(3), 5
siluet a, 15
structura scenei, 6
subexpunere, 26
SVD, 11
textur a, 31
triangulare, 3
unicitatea unei preimagini, 10
vector nenul, 5
vertex, 21, 22
voxel, 15
zgomot, 26
44