Többnézetes geometria

Vizu´alis helymeghat´aroz´as T¨ obbn´ezetes geometria Pl´ osz S´andor1 1 Budapesti

M˝ uszaki ´ es Gazdas´ agtudom´ anyi Egyetem T´ avk¨ ozl´ esi ´ es M´ ediainformatikai Tansz´ ek

2015

Pl´ osz S´ andor (BME TMIT)

Navig´ aci´ os szolg´ altat´ asok ´ es alkalmaz´ asok

2015

1 / 37

Tartalom

I

Ism´etl´es

I

Vizu´alis helymeghat´aroz´as elve

I

Projekt´ıv geometria alapjai

I

Kamer´ak reprezent´al´asa

I

T¨obbn´ezetes geometria, fundament´alis m´atrix

I

Fundament´alis m´atrix meghat´aroz´asa

I

T´er´ep´ıt´es, triangul´aci´ o

Pl´ osz S´ andor (BME TMIT)

Navig´ aci´ os szolg´ altat´ asok ´ es alkalmaz´ asok

2015

2 / 37

Ism´etl´es Line´ aris egyenletek - SVD felbont´ as (1)

A ∈ Cm×n

I

Line´aris egyenletek: y = f (x) = Ax

I

Minden AM×N m´atrixra l´etezik egy u ´n. SVD (Singular Value Decomposition) felbont´as H AM×N = UM×M ΣM×N VN×N

I

I

U ´es V unit´er (val´os esetben ortogon´alis) m´atrixok (UUH = UH U = I ´es VVH = VH V = I) Σ m´atrixban a f˝o´atl´oban nemnegat´ıv val´ os sz´amok tal´alhat´ok, m´ashol nulla I

A f˝ o´atl´ o elemeit h´ıvjuk szingul´aris ´ert´ekeknek (σn )

Pl´ osz S´ andor (BME TMIT)

Navig´ aci´ os szolg´ altat´ asok ´ es alkalmaz´ asok

2015

3 / 37

Ism´etl´es Line´ aris egyenletek - SVD felbont´ as (2) I

Nem n´egyzetes esetben t´etelezz¨ uk fel, hogy A = UDV T az SVD felbont´as szerint

I

Minimaliz´aljuk a kAx − yk kifejez´est! kAx − yk = kUDV T x − yk = kDV T x − U T yk

I

Legyen y0 = U T y ´es x0 = V T x!

I

Ekkor a kDx0 − y0 k kifejez´est kell minimaliz´alnunk

Pl´ osz S´ andor (BME TMIT)

Navig´ aci´ os szolg´ altat´ asok ´ es alkalmaz´ asok

2015

4 / 37

Bevezet´es Vizu´ alis helymeghat´ aroz´ as l´ep´esei I

Felt´erk´epez´es: I

I I

I

I

referencia k´epek k´esz´ıt´ese, tart´ ozkod´asi hely (C ) ´es orient´aci´o (R) r¨ ogz´ıt´ese Megalkotni minden referencia k´ephez a Pr referencia kamera m´atrixot. A kamer´ak bels˝ o param´etereit (K m´atrix) sz´am´ıt´assal vagy kalibr´aci´ oval meg kell hat´arozni

A tesztk´ep ¨osszehasonl´ıt´asa referencia k´epekkel (valamely p´aros´ıt´o algoritmussal), megkeresni a legjobb p´art ¨ Osszetartoz´ o pontp´arok kinyer´ese, ezek alapj´an kamera rel´aci´ot le´ır´o (fundament´alis) m´atrix meghat´aroz´asa

I

Ebb˝ol relat´ıv hely ´es orient´aci´ o meghat´aroz´asa

I

Optimaliz´al´as, 3d triangul´aci´ o, t´er´ep´ıt´es

Pl´ osz S´ andor (BME TMIT)

Navig´ aci´ os szolg´ altat´ asok ´ es alkalmaz´ asok

2015

5 / 37

Bevezet´es K´etn´ezetes geometria

Pl´ osz S´ andor (BME TMIT)

Navig´ aci´ os szolg´ altat´ asok ´ es alkalmaz´ asok

2015

6 / 37

A projekt´ıv geometria alapjai I I

Az n dimenzi´os projekt´ıv geometria n dimenzi´ os pontokat n + 1 dimenzi´oban ´ır le. Pontok le´ır´asa I I

π : x3 = 1 egy s´ıkot defini´al, mely x1 -x2 s´ıkkal p´arhuzamos Tetsz˝ oleges s´ıkon tal´alhat´ o x pont le´ırhat´ o az O ´es x pontokon ´atmen˝o egyenes egyenlet´evel:

ax + by + c = 0 I

Az egyenes param´eterei: 2.2 a, The b, c2D projective plane

29

x2

ideal point

l O

Pl´ osz S´ andor (BME TMIT)

x1

x

π

x3

Navig´ aci´ os szolg´ altat´ asok ´ es alkalmaz´ asok

2015

7 / 37

A projekt´ıv geometria alapjai Projekt´ıv t´er I

Egyenes konstansal val´ o szorz´assal nem v´altozik: (a, b, c) ↔ (ka, kb, kc), k 6= 0

I

I

I

I

x = (x, y ) pont akkor van az egyenesen, ha teljes´ıti:     a x y 1 b  = 0 c

(kx, ky , k) ugyanazt azt az x s´ıkbeli pontot jel¨ oli → pont homog´en koordin´at´aja Egy ´altal´anos x = (x1 , x2 , x3 ) pont a s´ık (x1 /x3 , x2 /x3 ) pontj´anak felel meg P2 k´et dimenzi´os projekt´ıv t´er R3 − (0, 0, 0) felett (val´os sz´amh´armasok kiv´eve a nullvektor)

Pl´ osz S´ andor (BME TMIT)

Navig´ aci´ os szolg´ altat´ asok ´ es alkalmaz´ asok

2015

8 / 37

A projekt´ıv geometria alapjai Projekt´ıv geometria tulajdons´ agai I

K´et egyenes l, l 0 metsz´espontja x = l × l 0 = [l]× l 0

I I

I

Hiszen l(l × l 0 ) = l 0 (l × l 0 ) = 0 l × l 0 a k´et vektor vektori´alis szorzata i j k  ay az ax a × b = ax ay az = , by bz bx bx by bz [l]× a vektori´alis szorz´as m´atrix alakban  0 −az  az 0 [a]× = −ay ax

Pl´ osz S´ andor (BME TMIT)

az ax , bz bx

 ay by

 ay −ax  0

Navig´ aci´ os szolg´ altat´ asok ´ es alkalmaz´ asok

2015

9 / 37

A projekt´ıv geometria alapjai Projekt´ıv geometria tulajdons´ agai

I

K´et p´arhuzamos egyenes l : (a, b, c)

I

l 0 : (a, b, c 0 )

Metsz´espontjuk: l × l 0 = (c 0 − c)(b, −a, 0)T

I

´ altva norm´al koordin´at´akra (d = (c 0 − c)) Atv´

l × l 0 = d(b/0, −a/0)T I

A pont koordin´at´ai v´egtelen nagyok → projekt´ıv t´erben a p´arhuzamosak a v´egtelenben tal´alkoznak!

Pl´ osz S´ andor (BME TMIT)

Navig´ aci´ os szolg´ altat´ asok ´ es alkalmaz´ asok

2015

10 / 37

Vet´ıt´es

154

6 Camera Models Y

X

Y

X y x

x

fY/Z

C

C

Z

p

p

Z

f

principal axis

camera centre

image plane

Fig. 6.1. Pinhole camera geometry. C is the camera centre and p the principal point. The camera I is centre hereegy placed at the origin. Note the ´ image is placed in ufront of theank camera Van X(x, y ,coordinate z) pontunk a t´ erben es egyplane f param´ eter˝ kamer´ a centre.

C pontban, mely Z tengely fel´e n´ez

0

0

Hol that l´atszik vet¨ u(Xlete ankon to (x the , y point )? (f X/Z, f Y/Z, f )T on the T computes the X point , Y, aZ)kamer´ is mapped 0 y y fy 0 I Egyszer˝ image plane. Ignoring we see that u ar´any:thez final = fimage → y coordinate, = z I

I

Ugyan´ıgy: x 0 =

fx z

(X, Y, Z)T → (f X/Z, f Y/Z)T

(6.1)

describes the central projection mapping from world to image coordinates. This is a (x, y , z)T 7→ (fx/z, fy /z)T mapping from Euclidean 3-space IR3 to Euclidean 2-space IR2 . The centre of projection is called the camera centre. It is also known as the optical Pl´ osz S´ andor (BME TMIT)

Navig´ aci´ os szolg´ altat´ asok ´ es alkalmaz´ asok

2015

11 / 37

Vet´ıt´es I

Kamera s´ıkj´ara val´o vet´ıt´es: y0 =

fy 1 = fy z z

x0 =

fx 1 = fy z z

I

Mivel az oszt´as m˝ uvelet´et nem tudjuk fel´ırni m´atrix alakban, ez´ert bevezett´ek a homog´en koordin´at´akat

I

A h´anyados egy u ´jabb koordin´ata  0    x fx f y 0    7→ fy  =  z 0  z 1

I I

M´ask´eppen P = diag(f , f , 1) [I |0]

f

   x 0   y 0  z  1 0 1

Ahol P m´atrix az u ´n. vet´ıt´esi (projekci´ os) m´atrix

Pl´ osz S´ andor (BME TMIT)

Navig´ aci´ os szolg´ altat´ asok ´ es alkalmaz´ asok

2015

12 / 37

Kamera bels˝o param´eterei I

A val´os´agban f -et valamilyen fizikai m´ert´ekben adj´ak meg (pl. mm)

I

A k´epfeldolgoz´as sor´an pixel koordin´ata rendszerben dolgozunk

I

f -et ´at kell transzform´al´alni pixel koordin´atarendszerbe

I

r = (rx , ry ) a szenzor felbont´asa, d = (dx , dy ) a szenzor m´erete [mm]

I

αx = rx /dx ,

αy = ry /dy

[pixel/mm] 6.1 Finite cameras

 f αx K = 0 0

0 f αy 0

 x0 y0  1

ycam y0

I

x0 , y0 a kamera orig´oja

I

K m´atrixot a kamera bels˝ o (intrinsic) param´etereinek h´ıvjuk

Pl´ osz S´ andor (BME TMIT)

p

x cam

y

x

x0

Fig. 6.2. Image (x, y) and camera (xcam , ycam ) coordinate syste

Navig´ aci´ os szolg´ altat´ asok ´ es alkalmaz´ asok

2015

13 / 37

Kamera k¨uls˝o param´eterei I

A kamera a t´erben nem felt´etlen¨ ul a z koordin´atatengely ir´any´aba n´ez

I

Ezt egy R forgat´asi m´atrixszal ´es egy C k¨ oz´epponttal (eltol´as) jellemezhetj¨ uk

I

A megfelel˝o k¨ uls˝o transzform´aci´ ot (extrinsic parameters) a k¨ovetkez˝ok´epp kapjuk:   R −RC Pex = 0 1

I

A k¨ uls˝o ´es bels˝o param´eter m´atrixok szorzata adja a teljes P kamera m´atrixot: P = K [R| − RC ] = KR[I | − C ]

Pl´ osz S´ andor (BME TMIT)

Navig´ aci´ os szolg´ altat´ asok ´ es alkalmaz´ asok

2015

14 / 37

Kamera transzform´aci´oja

I

Kamera projekci´o egyenlete: P = K [R| − RC ] = KR[I | − C ]

I

L´ep´esek: 1. Eltol´as → x0 = (x − C) 2. Forgat´as → x00 = (Rx0 ) 3. Vet´ıt´es → x000 = (Kx00 )

Pl´ osz S´ andor (BME TMIT)

Navig´ aci´ os szolg´ altat´ asok ´ es alkalmaz´ asok

2015

15 / 37

C

C

Epipol´aris geometria Bevezet´es

/

a

Fig. 9.1. Point correspondence geometry. (a) The C
and image planes. The camera centres, 3-space π. (b) An image point x back-projects to a ra I Egy t´ erbeli pont, ´es k´etGeometry vet´ıtettplane k´ex. pe k¨ oz¨ ott milyen ¨osszef¨ ugg´es van 240 9 Epipolar and theThis Fundamental Matrix and ray is imaged as a line l
in the second lie on this ray, so the image of X in the second view X X? I

Epipol´aris: k´etn´ezetes

epipolar plane

π

X

π

X?

l l

/

x/

x

x

e C

C

l

/

e e/ /

e

/

baseline epipolar line for x

a

a

b

Fig. 9.1. Point correspondence geometry. (a)Fig. The9.2. two cameras indicated (a) by their an Epipolarare geometry. The centres cameraCbas
´es alkalmaz´ Pl´ osz S´ andor planes. (BME TMIT) aci´ os szolg´ altat´ asokpoint asok its images x and x
2015 / 37 image The cameraNavig´ centres, 3-space X, and lie in a16commo C
and

epipolar plane

π

Epipol´aris geometria Fogalmak

240

9 Epipolar Geometry and x/

x

X epipolar plane

I

K´et kamera C ´es C 0 k¨ oz´epponttal

I

X t´erbeli pont, k´epe a k´et kamer´an rendre x ´es x 0 C 0,

x0

I

C, x, ´es X pontok egy u ´n. π epipol´aris s´ıkra esnek

I

A C ´es C 0 pontot ¨osszek¨ ot˝ o egyenest alapegyenesnek h´ıvjuk, a k´eps´ıkokat e ´es e 0 pontban metszik (epip´ olus)

I

Az e ´es x pontok az l epipol´aris egyenesre esnek, ahogy e 0 ´es x 0 az l 0 epipol´aris egyenesre.

π C

C

a x/

x

Fig. 9.1. Point correspondence geometry. (a) Th C
and image planes. The camera centres, 3-space plane π. (b) An image point x back-projects to ar / C C and x. This ray is imaged as a line l
in the second lie on this ray, so the image of X in the second view π

a

Fig. 9.1. Point correspondence geometry. (a) The C
and image planes. The camera centres, 3-space l plane π. (b) An image point x back-projectsl /to a ra and x. This ray is imaged as a line l
in the second v lie on this ray, so the image of X in the second view m e

e/

π baseline

l

a Pl´ osz S´ andor (BME TMIT)

/

Navig´ aci´ os szolg´ altat´ asok ´ es alkalmaz´ sok Fig. a9.2.

l

/

2015 17 / 37 Epipolar geometry. (a) The camera bas

Epipol´aris geometria Epipol´ aris egyenlet 240

I

9 Epipolar Geometry an

Tudjuk, hogy PX = x, amib˝ ol X -et meghat´arozhatjuk a k¨ov. egyenlet megold´as´aval:

X epipolar plane

X (λ) = P + x + λC I

P + a P m´atrix pszeudoinverze (PP + = I )

I

C a kamera k¨oz´eppont, (P nullvektora, hiszen PC = 0)

π

x/

x

C

C

/

a

Fig. 9.1. Point correspondence geometry. (a) Th

I

A megold´as egy egyenes, k´et kiemelt pontC
Pand+image x (λplanes. = 0)The´escamera C centres, 3-spac plane π. (b) An image point x back-projects to a (λ = inf) and x. This ray is imaged as a line l
in the second

I

Ezen pontok k´epei a 2. kamer´an: P 0 P + x ´es P 0 C = e 0

lie on this ray, so the image of X in the second view π l

Pl´ osz S´ andor (BME TMIT)

Navig´ aci´ os szolg´ altat´ asok ´ es alkalmaz´ asok

2015

/

18 l/ 37

Epipol´aris geometria Fundament´ alis m´ atrix

I

Az el˝oz˝oek alapj´an: l 0 = (P 0 C ) × (P 0 P + x) = e 0 × (P 0 P + x) = [e 0 ]× (P 0 P + x) = Fx

I

[e 0 ]× az e 0 vektorral t¨ ort´en˝ o keresztszorzatot jelent˝o m´atrix

I

Az F m´atrixot fundament´alis m´atrixnak nevezz¨ uk

I

F kapcsolatot ad a k´et n´ezet k¨ oz¨ ott, egy adott n´ezetben levet´ıttet ponthoz hozz´arendel a m´asik n´ezetben egy egyenest.

I

Mivel az x 0 pont az l 0 egyenesen fekszik, ez´ert minden x ´es x 0 pont k¨oz¨ott fenn´all x 0T Fx = 0

Pl´ osz S´ andor (BME TMIT)

Navig´ aci´ os szolg´ altat´ asok ´ es alkalmaz´ asok

2015

19 / 37

Epipol´aris geometria Fundament´ alis m´ atrix

I

F rangja 2, ´es 7 szabads´agfokkal b´ır

I

B´armely k´et n´ezetet le´ırhatunk egy F m´atrixal, u ´gy, hogy a vet´ıtett pontp´arokra ´erv´enyes az el˝ oz˝ o egyenlet

I

B´armely k´et kamer´ahoz egy´ertelm˝ uen tartozik egy fundament´alis m´atrix, de ford´ıtva nem felt´etlen¨ ul igaz!

I

Minden kamerap´arhoz, amelyek csak egy projekt´ıv transzform´aci´oban k¨ ul¨onb¨oznek ugyanaz a fundament´alis m´atrix tartozik

Pl´ osz S´ andor (BME TMIT)

Navig´ aci´ os szolg´ altat´ asok ´ es alkalmaz´ asok

2015

20 / 37

Epipol´aris geometria Esszenci´ alis m´ atrix I

Legyen P = K [R| − RC ] = KR[I | − C ] form´aj´ u

I

Vezess¨ uk be minden x pontra az u ´n. normaliz´alt xˆ = K −1 x koordin´at´akat

I

Bel´athat´o, hogy minden xˆ ↔ xˆ0 pontp´arra igaz: xˆ0T E xˆ = 0

I

Az E m´atrixot esszenci´alis m´atrixnak h´ıvjuk, ´es: E = K 0T FK = [t]× R.

I

Amennyiben a k´et kameram´atrix fel´ep´ıt´ese P = K [I |0] ´es P 0 = K [R|t].

Pl´ osz S´ andor (BME TMIT)

Navig´ aci´ os szolg´ altat´ asok ´ es alkalmaz´ asok

2015

21 / 37

Epipol´aris geometria Esszenci´ alis m´ atrix

I

E m´atrix szabads´agfoka 5 → t¨ obb megszor´ıt´as vonatkozik r´a, mint a fundament´alis m´atrixra

I

Bel´athat´o, hogy amennyiben egy kameram´atrixhoz tartoz´o esszenci´alis m´atrix ismert, akkor abb´ ol a kamera m´atrixokra n´egy megold´as tal´alhat´o.

I

Ebb˝ol a n´egy megold´asb´ ol kisz˝ urhet˝ o az az egy, amelyik szerint az X pontok mind a kamer´ak n´ezeti ir´any´aban (s nem a kamer´ak m¨og¨ott) tal´alhat´ok.

I

A pontos megold´asi m´ odszer az SVD (Singular Value Decomposition) felbont´ason alapul

Pl´ osz S´ andor (BME TMIT)

Navig´ aci´ os szolg´ altat´ asok ´ es alkalmaz´ asok

2015

22 / 37

Fundament´alis m´atrix meghat´aroz´asa

I

K´et k¨ ul¨onb¨oz˝o kamer´aval, k¨ ul¨ onb¨ oz˝ o helyr˝ ol r¨ ogz´ıtett k´epek megfelel˝o 0 x ↔ x k´eppontp´arjai k¨ oz¨ ott a k¨ ov. epipol´aris megk¨ot´es ´all fenn: x0T F3x3 x = 0

I I

F3x3 a szingul´aris fundament´alis m´atrix (rangja 2). Meghat´aroz´asa: I I I

Kezdeti becsl´es Hiba fel´ır´asa K¨ olts´egf¨ uggv´eny optimaliz´al´as

Pl´ osz S´ andor (BME TMIT)

Navig´ aci´ os szolg´ altat´ asok ´ es alkalmaz´ asok

2015

23 / 37

Fundament´alis m´atrix meghat´aroz´asa K¨ olts´egf¨ uggv´eny I

Szimmetrikus epipol´aris hiba k¨ olts´egf¨ uggv´eny

I

Tudjuk, hogy az egyik k´epen az x ponthoz a m´asik k´epen egy l egyenes tartozik, amelyekre: l0 = F x

I

Hasonl´oan az x0 pontokra: l = F T x0

I

(1)

A szimmetrikus epipol´aris hiba ´ıgy az egyenesek ´es pontok t´avols´ag´at ¨osszegzi: X d(x0i , F xi )2 + d(xi , F T x0i )2 (2) i

I

ahol d(x, y) az y egyenes ´es a x pont euklideszi t´avols´ag´at jelenti.

Pl´ osz S´ andor (BME TMIT)

Navig´ aci´ os szolg´ altat´ asok ´ es alkalmaz´ asok

2015

24 / 37

Fundament´alis m´atrix meghat´aroz´asa Becsl´es

I

Ha a m´ert k´eppontok norm´alis eloszl´as´ u zajjal terheltek alkalmazhat´o a maximum likelihood (ML) becsl´es

I

Zajjal terhelt pontp´aroknak megfelel˝ oˆ xi ↔ ˆ x0i pontp´arok kiel´eg´ıtik: T xˆ0 i F ˆ xi = 0

I

A reprojekci´os hiba k¨ olts´egf¨ uggv´eny: X d(xi , ˆ xi )2 + d(x0i , xˆ0 i )2

(3)

i

Pl´ osz S´ andor (BME TMIT)

Navig´ aci´ os szolg´ altat´ asok ´ es alkalmaz´ asok

2015

25 / 37

Fundament´alis m´atrix meghat´aroz´asa 8 pontos m´ odszer I

x0T F3x3 x = 0 egyenlet az F line´aris f¨ uggv´enye

I

F m´atrixra line´aris egyenletrendszer ´ırhat´ o fel, pontonk´ent egy egyenlettel

I

Legyen xi = (x, y , 1) ´es x0i = (x 0 , y 0 , 1), ekkor ∀(xi , x0i )-re: x 0 xf11 + x 0 yf12 + x 0 f13 + y 0 xf21 + y 0 yf22 + y 0 f23 + xf31 + yf32 + f33 = 0

I

I

Legyen f T = (f11 , f12 , f13 , f21 , f22 , f23 , f31 , f32 , f33 )   0 x1 x1 x10 y1 x10 y10 x1 y10 y1 y10 x1 y1 1  .. .. .. .. .. .. .. ..  f = 0 Af =  ... . . . . . . . . 0 0 0 0 0 0 xn xn xn yn xn yn xn yn yn yn xn yn 1 F nem felt´etlen¨ ul lesz szingul´aris!

Pl´ osz S´ andor (BME TMIT)

Navig´ aci´ os szolg´ altat´ asok ´ es alkalmaz´ asok

2015

26 / 37

Fundament´alis m´atrix meghat´aroz´asa 8 pontos m´ odszer

I

Legt¨obbsz¨or t¨obb mint 8 pontunk van

I

Legkisebb n´egyzetes megold´as elve: legkisebb szingularit´ashoz tartoz´o szingul´aris vektor

I

Ha A SVD felbont´asa A = UDV T , akkor a megold´as ViT amennyiben σi = min σk k

I

F szingul´aris felbont´asa F = Udiag(r , s, 0)V T form´aj´ u, hiszen a rangja 2

I

C´elszer˝ u F = Udiag(r , s, t)V T helyett az F 0 = Udiag(r , s, 0)V T m´atrix haszn´alata

Pl´ osz S´ andor (BME TMIT)

Navig´ aci´ os szolg´ altat´ asok ´ es alkalmaz´ asok

2015

27 / 37

Fundament´alis m´atrix meghat´aroz´asa 7 pontos m´ odszer I

F fundament´alis m´atrix szabads´agi foka 7

I

A m´atrix 9 oszloppal rendelkezik, ha 7 pontb´ ol ´ep´ıtj¨ uk fel magtere k´et dimenzi´os lesz

I

Legyen e k´etdimenzi´os t´ernek a b´azisa f1 ´es f2 , amelyeket az A m´atrix SVD felbont´as´ab´ol kaphatunk F = F1 + αF2

I

(4)

F m´atrix az Af = 0 homog´en egyenletnek megfelel˝o m´atrix, α ismeretlen szorz´o. A k¨ ov. egyenletet kell megoldani: det(F1 + αF2 ) = 0

I

Ez m´ar z´art alakban megolhat´ o!

I

El˝onye: 7 pont el´eg, ´es F szingul´aris lesz

Pl´ osz S´ andor (BME TMIT)

Navig´ aci´ os szolg´ altat´ asok ´ es alkalmaz´ asok

(5)

2015

28 / 37

Fundament´alis m´atrix meghat´aroz´asa Optim´ alis megold´ as

I

Kezdeti becsl´esre j´o a normaliz´alt 8 pontos ´es 7 pontos algoritmus

I

ML becsl´eshez reprojekci´ os hiba k¨ olts´egf¨ uggv´eny minimaliz´al´asa kell A legk´ezenfekv˝obb megold´as a t´er projekt´ıv rekonstrukci´oja

I

I I I

I

F -nek megfelel˝ o P ´es P 0 kameram´atrixok meghat´aroz´asa Pontok triangul´aci´ oja Optimaliz´aci´ o

Seg´ıts´eg´evel a kamer´ak relat´ıv helye meghat´arozhat´o → sk´al´az´as erej´eig

Pl´ osz S´ andor (BME TMIT)

Navig´ aci´ os szolg´ altat´ asok ´ es alkalmaz´ asok

2015

29 / 37

Esszenci´alis m´atrix meghat´aroz´asa I I I

I

I

Ha F megvan → E = K T FK

Ha P = K [I |0] → P 0 = K [R|t] hogy kapjuk meg? Legyen az esszenci´alis m´atrix Defini´aljuk:  0 −1  W = 1 0 0 0

SVD felbont´asa E = Udiag(1, 1, 0)V T .  0 0 1



 0 1 0 Z = −1 0 0 0 0 0

Ha P = K [I |0], akkor P 0 kameram´atrixra n´egy megold´as ad´odik:     P10 = UWV T +u3 P30 = UW T V T +u3     P40 = UW T V T −u3 P20 = UWV T −u3 Csak egy megold´as helyes (pontok mindk´et kamera el˝ott)

Pl´ osz S´ andor (BME TMIT)

Navig´ aci´ os szolg´ altat´ asok ´ es alkalmaz´ asok

2015

30 / 37

Triangul´aci´o Bevezet´es

I

Legyen P ´es P 0 a k´et kamera m´atrixunk

I

Legyen X t´erbeli pont, mely k´epe x = PX ´es x0 = P 0 X

I

A triangul´aci´o ennek megford´ıt´asa, teh´at ismerve x ↔ x0 pontp´arokat, melyik az az X pont, amelyre x = PX ´es x0 = P 0 X?

I

A feladat a k¨ovetkez˝o τ triangul´aci´ o megtal´al´asa: X = τ (x, x0 , P, P 0 )

I

Csak zajmentes esetben lenne egy´ertelm˝ u

Pl´ osz S´ andor (BME TMIT)

Navig´ aci´ os szolg´ altat´ asok ´ es alkalmaz´ asok

2015

31 / 37

Triangul´aci´o Zaj szeml´eltet´ese 12.1 Problem statement

311

x/

x

C

C

/

a l = F x/

x

x/

l /= F x

e/

e image 1

image 2

b Fig. 12.1. (a) Rays back-projected from imperfectly measured points x, x
are skew in 3-space in general. (b) The epipolar geometry for x, x
. The measured points do not satisfy the epipolar constraint.
T
The epipolar line lTMIT) = Fx is the image of the ray through l=F x is the image of the ray through Pl´ osz S´ andor (BME Navig´ aci´ os szolg´ altat´ asokx, ´ es and alkalmaz´ asok 2015

32 / 37

Triangul´aci´o Egyenletek I

A k¨ovetkez˝o egyenleteket ´ırhatjuk fel: x × (PX) = 0

0

x × (P 0 X) = 0 I

Az els˝o egyenletet felbonthatjuk az al´abbi form´aban (piT a P m´atrix i-dik sor´at jel¨oli) x(p3T X) − (p1T X) = 0

y (p3T X) − (p2T X) = 0

x(p2T X) − y (p1T X) = 0 I

Line´aris egyenletrendszer

Pl´ osz S´ andor (BME TMIT)

Navig´ aci´ os szolg´ altat´ asok ´ es alkalmaz´ asok

2015

33 / 37

Triangul´aci´o Megold´ as I

A m´asik keresztszorzatot hasonl´ oan felbontva ¨ osszesen hat egyenletet kapunk, amelyeket ¨osszevonhatunk AX = 0 alakra   3T xp − p1T  y p3T − p2T    2T  xp − p1T   A= x 0 p03T − p01T    y 0 p03T − p02T  x 0 p02T − p01T

I

Megold´asa a legkisebb n´egyzetes hiba minimaliz´al´as´aval (a legkisebb szingul´aris ´ert´ekhez tartoz´ o szingul´aris vektor)

I

A m´atrix szingul´aris felbont´as´aval (SVD) kaphatjuk meg

Pl´ osz S´ andor (BME TMIT)

Navig´ aci´ os szolg´ altat´ asok ´ es alkalmaz´ asok

2015

34 / 37

Optimaliz´aci´o

I

a xi ↔ x0i pontp´arok ismeret´eben az Xi h´arom dimenzi´os pontok meghat´arozhat´ok triangul´aci´ oval

I

A feladat innent˝ol a k¨ ovetkez˝ o egyenletrendszer reprojekci´os hib´aj´anak nemline´aris optimaliz´aci´ oja Xi ´es P 0 f¨ uggv´eny´eben: xi = PXi

(6)

x0i = P 0 Xi I

¨ Osszesen 3n + 12 v´altoz´ o, ahol n a 3d pontp´arok sz´ama (ritka Levenberg-Marquardt minimaliz´aci´ o)

Pl´ osz S´ andor (BME TMIT)

Navig´ aci´ os szolg´ altat´ asok ´ es alkalmaz´ asok

2015

35 / 37

T´ermodell

Pl´ osz S´ andor (BME TMIT)

Navig´ aci´ os szolg´ altat´ asok ´ es alkalmaz´ asok

2015

36 / 37

T´ermodell

Pl´ osz S´ andor (BME TMIT)

Navig´ aci´ os szolg´ altat´ asok ´ es alkalmaz´ asok

2015

37 / 37

T´ermodell

Pl´ osz S´ andor (BME TMIT)

Navig´ aci´ os szolg´ altat´ asok ´ es alkalmaz´ asok

2015

38 / 37

Forr´as

I

Richard Hartley and Andrew Zisserman, ”Multiple View Geometry in Computer Vision”, 2nd edition, 2004

Pl´ osz S´ andor (BME TMIT)

Navig´ aci´ os szolg´ altat´ asok ´ es alkalmaz´ asok

2015

39 / 37