Metody Poˇc´ıtaˇcov´eho Vidˇen´ı (MPV) - 3D poˇc´ıtaˇcov´e vidˇen´ı Projektivn´ı geometrie dvou pohled˚ u
Ing. Zdenˇek Krˇ noul, Ph.D. Katedra Kybernetiky Fakulta aplikovan´ ych vˇ ed Z´ apadoˇ cesk´ a univerzita v Plzni
Metody Poˇ c´ıtaˇ cov´ eho Vidˇ en´ı (MPV) - 3D poˇ c´ıtaˇ cov´ e vidˇ en´ı
Obsah pˇredn´aˇsky I
I
Perspektivn´ı kamera I model kamery I kalibrace kamery I rozklad matice projekce Projektivn´ı geometrie dvou pohled˚ u I Epipol´ arn´ı geometrie I Epipol´ arn´ı podm´ınka I Fundament´ aln´ı matice I Odhad pohybu kamery I 3D rekonstrukce
Metody Poˇ c´ıtaˇ cov´ eho Vidˇ en´ı (MPV) - 3D poˇ c´ıtaˇ cov´ e vidˇ en´ı
1 / 51
Perspektivn´ı kamera I I
obecn´y model perspektivn´ı kamery slouˇz´ı k popisu projekce 3D prostoru do 2D prostoru (obrazov´a rovina) vˇzdy se jedn´a o stˇredovou projekci
Pozn. speci´aln´ı pˇr´ıpad ... stˇred projekce leˇz´ı v nekoneˇcnu → afinn´ı kamera a jde o zobecnˇen´ı tzv. paraleln´ı projekce Metody Poˇ c´ıtaˇ cov´ eho Vidˇ en´ı (MPV) - 3D poˇ c´ıtaˇ cov´ e vidˇ en´ı
2 / 51
I
I I
projekce bodu X = (x, y , z) do obrazov´e roviny π souˇradn´e osy (u, v ) poˇc´atek souˇradn´eho syst´emu svˇetov´ych souˇradnic je v bode C vzd´alenost obrazov´e roviny od tohoto bodu je tzv. ohniskov´a vzd´alenost f
Metody Poˇ c´ıtaˇ cov´ eho Vidˇ en´ı (MPV) - 3D poˇ c´ıtaˇ cov´ e vidˇ en´ı
3 / 51
I
model kamery je reprezentov´an matic´ı P o velikosti 3 × 4 tzv. matic´ı projekce
I
libovoln´y bod v prostoru se transformuje do obrazov´e roviny pouh´ym n´asoben´ım matic´ı projekce:
I
m = PX
(1)
x f 0 0 0 m1 m2 = 0 f 0 0 y z m3 0 0 1 0 1
(2)
a maticovˇe zap´ıˇseme jako:
Metody Poˇ c´ıtaˇ cov´ eho Vidˇ en´ı (MPV) - 3D poˇ c´ıtaˇ cov´ e vidˇ en´ı
4 / 51
Pˇrechod z homogenn´ı reprezentace: I normalizujeme (na jedniˇ cku) tˇret´ı homogenn´ı souˇradnici m1 m2 T ... pak vlastnˇ [m , , 1] e modeluje v´ypoˇcet projekce takto: 3 m3 fx m2 fy m3 m1 = = u, = = v, = 1 pro m3 6= 0 m3 z m3 z m3 I I
(3)
ˇr´ık´ame, ˇze vyj´adˇr´ıme bod v obraze Proˇc to tak je? uk´azka pˇrepoˇctu projekce za pomoci podobnosti troj´ uheln´ık˚ u, n´ahled os (Y,Z) a obdobnˇe plat´ı pro (X,Z)
Metody Poˇ c´ıtaˇ cov´ eho Vidˇ en´ı (MPV) - 3D poˇ c´ıtaˇ cov´ e vidˇ en´ı
5 / 51
Model obecn´e kamery (matice P) zahrnuje dalˇs´ı prvky (celkem 5 vnitˇrn´ıch a 6 vnˇejˇs´ıch parametr˚ u), kter´e poskytuj´ı dalˇs´ı stupnˇe volnosti projekce: I posun poˇ c´ atku souˇradnic obrazov´e roviny do lev´eho horn´ıho rohu I kompenzace nepravo´ uhlosti os senzoru.
fku −fku coth(θ) fkv / sin(θ) P= 0 0 0 fku −fku coth(θ) fkv / sin(θ) K= 0 0 0 Metody Poˇ c´ıtaˇ cov´ eho Vidˇ en´ı (MPV) - 3D poˇ c´ıtaˇ cov´ e vidˇ en´ı
u0 0 v0 0 resp. 1 0 u0 v0 je kalibraˇ cn´ı matice kamery 1 6 / 51
I
+ 6 vnˇejˇs´ıch parametr˚ u (3 kr´at rotace kolem tˇrech z´akladn´ıch os a posun kamery, resp. souˇradnice stˇredu prom´ıt´an´ı)
I
posun a otoˇcen´ı poˇc´atku souˇradnic svˇetov´ych souˇradnic
I
X = R(Xcamera − C), kde RT R = I je matice rotace kamery oproti svˇetov´ym souˇradnic´ım
Metody Poˇ c´ıtaˇ cov´ eho Vidˇ en´ı (MPV) - 3D poˇ c´ıtaˇ cov´ e vidˇ en´ı
7 / 51
I
vˇse dohromady definuje obecn´y pˇredpis pro perspektivn´ı kameru, P = KR[I, −C]
(4)
a projekce bodu je: m = KR[I, −C]X pˇrepisem m˚ uˇzeme vyj´adˇrit jako: P = K[R, t] kde t = −RC I
(5)
perspektivn´ı kamera m´a 11 stupˇ n˚ u volnosti: 1x ohniskov´a vzd´alenost v pixelech + 1x pomˇer stran pixelu + 1x zkosen´ı os + 2x poˇc´atek obr´azku + 3x posun + 3x rotace kamery= 11 DOF (degree of freedom)
Metody Poˇ c´ıtaˇ cov´ eho Vidˇ en´ı (MPV) - 3D poˇ c´ıtaˇ cov´ e vidˇ en´ı
8 / 51
Kalibrace kamery z mnoˇziny zn´am´ych bod˚ u - Camera resection
Metody Poˇ c´ıtaˇ cov´ eho Vidˇ en´ı (MPV) - 3D poˇ c´ıtaˇ cov´ e vidˇ en´ı
9 / 51
I
kalibrace kamery je numerick´a metoda pro urˇcen´ı matice projekce P
I
vyˇzaduje pozici prostorov´eho bodu a jeho projekci do obrazov´e roviny
I
z nˇekolika tˇechto dvojic m˚ uˇzeme urˇcit matici projekce
I
pro kaˇzd´y p´ar Xi ↔ xi mus´ı b´yt splnˇena projekce xi = PXi pro i = 1 : N
Pozn´amka 1: Pˇredpokladem je linearita projekce tak jak je zm´ınˇena a neuvaˇzuje se distorze obrazu dan´a napˇr´ıklad ˇcoˇckou objektivu Pozn´amka 2: Postup hled´an´ı projekˇcn´ı matice je velmi podobn´y hled´an´ı matice pro projektivn´ı transformaci (rozd´ıl je pouze v rozmˇeru matic) P a H
Metody Poˇ c´ıtaˇ cov´ eho Vidˇ en´ı (MPV) - 3D poˇ c´ıtaˇ cov´ e vidˇ en´ı
10 / 51
I
pro kaˇzdou dvojici Xi ↔ xi m˚ uˇzeme napsat vztah: T 0 −wi XT yi XT p1 i i T T wi X T 0 −xi Xi p2 = 0 i T T T −yi X xi Xi 0 p3
(6)
I
ı ˇr´adek matice P, podobnˇe druh´y xi = (xi , yi , wi ) a pT 1 je prvn´ a tˇret´ı ˇr´adek jsou sloˇzeny do sloupcov´eho vektoru nezn´am´ych veliˇcin o rozmˇeru 1 × 12
I
podobnˇe m˚ uˇzeme uvaˇzovat pouze prvn´ı dva ˇr´adky soustavy rovnic ... tˇret´ı ˇr´adek je line´arnˇe z´avisl´y na prvn´ıch dvou. Tedy: T p1 T T 0 −wi Xi yi Xi p2 = 0 (7) T T wi Xi 0 −xi XT i p3
Metody Poˇ c´ıtaˇ cov´ eho Vidˇ en´ı (MPV) - 3D poˇ c´ıtaˇ cov´ e vidˇ en´ı
11 / 51
I
pro mnoˇzinu n zn´am´ych prostorov´ych bod˚ u a jejich projekc´ı z´ısk´av´ame matici A velikosti (2n) × 12 T 0 −XT y1 XT 1 1 X T 0T −x1 XT 1 1 .. . . .. .. A= . (8) T T T 0 −Xn yn Xn XnT 0T −xn XT n
I
ˇreˇsen´ım t´eto soustavy (Ap = 0) z´ısk´ame vektor p a tedy potˇrebn´e ˇr´adky matice projekce P.
I
matice P m´a 12 prvk˚ u a 11 stupˇ n˚ u volnosti (nen´ı modelov´ano mˇeˇr´ıtko, k-n´asobek matice je stejn´a projekce)
I
z kaˇzd´eho prostorov´eho bodu z´ısk´av´ame dvˇe rovnice → teoreticky n´am staˇc´ı pro DOF 11 pˇresnˇe 5,5 prostorov´ych bod˚ u
I
pak existuje jedno ˇreˇsen´ı → prav´ y nulov´ y prostor matice A
Metody Poˇ c´ıtaˇ cov´ eho Vidˇ en´ı (MPV) - 3D poˇ c´ıtaˇ cov´ e vidˇ en´ı
12 / 51
I
vˇsak nepˇresnosti mˇeˇren´ı tˇechto bod˚ u → z´ısk´av´ame vˇsak pˇre-urˇcenou soustavu rovnic ... rank(A) = 9
I
→ hled´ame ˇreˇsen´ı s nejmenˇs´ı chybou (algebraickou nebo geometrickou)
I
v z´akladu proto pouˇzijeme SVD rozklad, nalezneme ˇreˇsen´ı s nejmenˇs´ı algebraickou chybou ... Ap = → SVD minimalizuje ||Ap|| s podm´ınkou ||p|| = 1
I
tedy |||| → min a pokud A = UDVT a σ12 σ11
I
pak ˇreˇsen´ı p odpov´ıd´a posledn´ımu ˇr´adku matice V a |||| = σ12
Metody Poˇ c´ıtaˇ cov´ eho Vidˇ en´ı (MPV) - 3D poˇ c´ıtaˇ cov´ e vidˇ en´ı
13 / 51
Existuj´ı jist´e degenerativn´ı konfigurace prostorov´ych bod˚ u, pro kter´e nelze urˇcit ˇreˇsen´ı a tedy matici projekce. Nejz´avaˇznˇejˇs´ı jsou tyto: I
stˇred projekce kamery a prostorov´e body leˇz´ı na ”twisted cubic”
I
kalibraˇcn´ı prostorov´e body leˇz´ı v jedn´e rovinˇe a na pˇr´ımce, kter´a proch´az´ı stˇredem projekce aj.
Metody Poˇ c´ıtaˇ cov´ eho Vidˇ en´ı (MPV) - 3D poˇ c´ıtaˇ cov´ e vidˇ en´ı
14 / 51
Radi´aln´ı zkreslen´ı - Radial distorsion I I
I
Vˇsechny pˇredchoz´ı vztahy plat´ı pro pˇr´ıpad, ˇze projekce je ide´aln´ı stˇredov´e prom´ıt´an´ı skuteˇcn´y pˇr´ıstroj (fotoapar´at nebo kamera) obsahuje ˇcoˇcku, kter´a zp˚ usobuje v´ıce ˇci m´enˇe jev, ˇze prostorov´e pˇr´ımky nejsou prom´ıt´any na pˇr´ımky v obraze - tzv. radi´ aln´ı zkreslen´ı tento jev nar˚ ust´a d˚ uleˇzitosti s klesaj´ıc´ı ohniskovou vzd´alenost´ı a cenou objektivu
Metody Poˇ c´ıtaˇ cov´ eho Vidˇ en´ı (MPV) - 3D poˇ c´ıtaˇ cov´ e vidˇ en´ı
15 / 51
I
korekci zkreslen´ı souˇradnic obr´azku m˚ uˇzeme pˇrespat jako: xˆ = xc + L(r )(x − xc ) yˆ = yc + L(r )(y − yc ) I I I I
(x, y ) je bod v obraze kter´y je podˇr´ızen radi´aln´ımu zkreslen´ı (xc , yc ) stˇred radi´aln´ıho zkreslen´ı p r je radi´aln´ı vzd´alenost od stˇredu radi´aln´ıho zkreslen´ı x 2 + y 2 L(r ) je funkce popisuj´ıc´ı zkreslen´ı, parametrem je vzd´alenost od stˇredu
I
aproximaci funkce L(r ) m˚ uˇzeme zvolit: L(r ) = 1 + κ1 r + κ2 r 2 + κ3 r 3 + . . .
I
parametry popisuj´ıc´ı radi´aln´ı zkreslen´ı jsou pak (κ1 , κ2 , κ3 , . . . ), xc , yc
Pozn. stˇred radi´aln´ıho zkreslen´ı m˚ uˇze b´yt zvolen ”principal point”... projekce stˇredu projekce do obrazu
Metody Poˇ c´ıtaˇ cov´ eho Vidˇ en´ı (MPV) - 3D poˇ c´ıtaˇ cov´ e vidˇ en´ı
16 / 51
I
I
urˇcen´ı funkce L(r ) je ˇcasto provedenou souˇcasnˇe s v´ypoˇctem projekˇcn´ı matice (je zahrnuta do minimalizaˇcn´ıho procesu) chybov´a veliˇcina pak urˇcuje odchylku skuteˇcn´ych bod˚ u kalibraˇcn´ıho obrazce v obraze od bod˚ u popsan´ych line´arn´ı transformac´ı
Pozn. obdobnˇe mohou b´yt parametry radi´aln´ıho zkreslen´ı urˇceny bˇehem v´ypoˇctu homografie
Metody Poˇ c´ıtaˇ cov´ eho Vidˇ en´ı (MPV) - 3D poˇ c´ıtaˇ cov´ e vidˇ en´ı
17 / 51
Rozklad matice projekce P
I
metodou kalibrace kamery z´ısk´av´ame pˇr´ımo projekˇcn´ı matici P jako celek (tedy matici 3 × 4)
I
matici m˚ uˇzeme pouˇz´ıt pro pˇr´ıpadnou 3D rekonstrukci a nen´ı bezprostˇrednˇe nutn´e zn´at jednotliv´e vnitˇrn´ı a vnˇejˇs´ı parametry kamery
I
pokud vˇsak tyto parametry potˇrebujeme urˇcit, mus´ıme z´ıskanou projekˇcn´ı matici rozloˇzit do zm´ınˇen´eho maticov´eho souˇcinu
I
tedy v´ıme, ˇze P = KR[I, −C]
Metody Poˇ c´ıtaˇ cov´ eho Vidˇ en´ı (MPV) - 3D poˇ c´ıtaˇ cov´ e vidˇ en´ı
18 / 51
I
d´ale matici budeme znaˇcit jako:
I
P = [Q, q] → KR[I, −C], kde
I
Q = KR ∈ R3,3 je ˇctvercov´a matice, pro perspektivn´ı kameru m´a plnou hodnost
I
q ∈ R3,1 stˇred syst´emu svˇetov´ych souˇradnic
I
K ∈ R3,3 je ˇctvercov´a matice horn´ı troj´ uheln´ıkov´a
I
R ∈ R3,3 je ˇctvercov´a matice rotace, je ortogon´aln´ı (R−1 = RT a tedy RT R = I) pozn. vektory sloupc˚ u takov´e matice maj´ı jednotkovou normu a jsou na sebe kolm´e
Metody Poˇ c´ıtaˇ cov´ eho Vidˇ en´ı (MPV) - 3D poˇ c´ıtaˇ cov´ e vidˇ en´ı
19 / 51
I
Pro urˇcen´ı vnitˇrn´ıch parametr˚ u m˚ uˇzeme napˇr´ıklad pouˇz´ıt QR rozklad, resp. variantu RQ
I
z teorie je RQ rozklad je dekompozice nˇejak´e matice A tak, ˇze plat´ı A = RQ za podm´ınky, ˇze R je horn´ı troj´ uheln´ıkov´a matice a Q je ortogon´aln´ı matice (Nezamˇenit s naˇs´ım oznaˇcen´ım pro matice Q a R!)
I
jednou z moˇznost´ı takov´eho rozkladu je pouˇzit´ı Givensov´ych rotac´ı
I
postupnˇe uvaˇzujeme n´asoben´ı matice Q (ta naˇse co vznikla z matice P) zprava maticemi R1 , R2 a R3 tak, aby platilo: c s 0 K = QR1 R2 R3 , R1 = −s c 0 0 0 1 kde c 2 + s 2 = 1 apod. R2 a R3
Metody Poˇ c´ıtaˇ cov´ eho Vidˇ en´ı (MPV) - 3D poˇ c´ıtaˇ cov´ e vidˇ en´ı
20 / 51
Rotace kamery oproti svˇetov´ym souˇradnic´ım:
I
I
c s 0 K = QR1 R2 R3 , R1 = −s c 0 0 0 1 chceme tedy na lev´e stranˇe dostat horn´ı troj´ uheln´ıkovou matici
I
postupnˇe tedy, hled´am nejprve u ´hel reprezentovan´y matic´ı R1 → na pozici Q32 byl nulov´y. Pak hled´am druh´y u ´hel matice R2 tak, aby prvek na pozici Q31 byl nulov´y
I
nakonec najdu tˇret´ı u ´hel v matici R3 , aby i tˇret´ı prvek pod diagon´alou byl nulov´y, tedy prvek Q21
I
m´ame tedy 3 vnˇejˇs´ı parametry ... rotaci kamery ve svˇetov´ych souˇradnic´ıch
Metody Poˇ c´ıtaˇ cov´ eho Vidˇ en´ı (MPV) - 3D poˇ c´ıtaˇ cov´ e vidˇ en´ı
21 / 51
Ohniskov´a vzd´alenost, posun poˇc´atku obr´azku a kolmost os obr´azku: I
pˇren´asoben´ım p˚ uvodn´ı matice Q zprava vˇsemi tˇremi z´ıskan´ymi maticemi z´ısk´av´am kalibraˇcn´ı matici K a tedy potaˇzmo i vnitˇrn´ı parametry kamery: ohnisko, velikost pixelu, posun poˇc´atku obr´azku a u ´hel os obr´azku
I
tedy K = QR1 R2 R3
Metody Poˇ c´ıtaˇ cov´ eho Vidˇ en´ı (MPV) - 3D poˇ c´ıtaˇ cov´ e vidˇ en´ı
22 / 51
Optick´y stˇred: I I I I
posledn´ı 3 vnˇejˇs´ı parametry jsou pro posun kamery od poˇc´atku svˇetov´ych souˇradnic optick´y stˇred m´a tu vlastnost, ˇze projekce tohoto bodu (C) je nulov´a pak PC = 0 a C jsou prostorov´e souˇradnice stˇredu projekce m˚ uˇzeme odvodit vztah pro urˇcen´ı optick´eho stˇredu jako: C 0 = PC = [Q, q] = QC + q ⇒ C = −Q−1 q 1
Metody Poˇ c´ıtaˇ cov´ eho Vidˇ en´ı (MPV) - 3D poˇ c´ıtaˇ cov´ e vidˇ en´ı
23 / 51
Uved’me jeˇstˇe dalˇs´ı vlastnosti z odvozen´e matice projekce, kter´e nejsou vnitˇrn´ı ani vnˇejˇs´ı parametry kamery: I
optick´y paprsek
I
optick´a rovina
I
vztah optick´a rovina a optick´y paprsek
I
...
Metody Poˇ c´ıtaˇ cov´ eho Vidˇ en´ı (MPV) - 3D poˇ c´ıtaˇ cov´ e vidˇ en´ı
24 / 51
Optick´y paprsek:
I
I I
optick´y paprsek je vektor, kter´y smˇeˇruje z optick´eho stˇredu (C ) smˇerem k prostorov´emu bodu (X ) v obrazov´e rovinˇe pak urˇcuje bod m bod v prostoru je d´an jako: X = C + λd = C + λQ−1 m ⇒ d = Q−1 m
Metody Poˇ c´ıtaˇ cov´ eho Vidˇ en´ı (MPV) - 3D poˇ c´ıtaˇ cov´ e vidˇ en´ı
(9)
25 / 51
Optick´a rovina: I
optick´a rovina je prostorov´a rovina, proch´azej´ıc´ı optick´ym stˇredem a urˇcuj´ıc´ı pˇr´ımku v obrazov´e rovinˇe.
I
potom optick´y paprsek dan´y bodem m je d = Q−1 m
I
druh´y paprsek jako d0 = Q−1 m0
Metody Poˇ c´ıtaˇ cov´ eho Vidˇ en´ı (MPV) - 3D poˇ c´ıtaˇ cov´ e vidˇ en´ı
26 / 51
I
po dosazen´ı z´ısk´ame vztah pro norm´alov´y vektor optick´e roviny jako: p = d × d0 = QT (m × m0 ) = QT n
Pozn´amka: optick´y paprsek z tohoto pohledu je si moˇzn´e pˇredstavit tak´e jako pr˚ useˇc´ık dvou optick´y rovin
Metody Poˇ c´ıtaˇ cov´ eho Vidˇ en´ı (MPV) - 3D poˇ c´ıtaˇ cov´ e vidˇ en´ı
27 / 51
Shrnut´ı
I
T q1 q14 q24 = KR[I, −C] P = [Q, q] = qT 2 T q3 q34 fku −fku coth(θ) u0 αx s x0 fkv / sin(θ) v0 = 0 αy y0 K= 0 0 0 1 0 0 1 R ... orientace kamery, ortogon´aln´ı matice 3 × 3
I
C = rnull(P) ... optick´y stˇred
I
d = Q−1 m ... optick´y paprsek
I
det(Q)q3 ... optick´a osa
I
Qq3 ... principal point
I
p = QT n ... optick´a rovina (n je pˇr´ımka v obrazov´e rovinˇe)
I
I
Metody Poˇ c´ıtaˇ cov´ eho Vidˇ en´ı (MPV) - 3D poˇ c´ıtaˇ cov´ e vidˇ en´ı
28 / 51
Projektivn´ı geometrie dvou pohled˚ u
I
projektivn´ı geometrie m˚ uˇze b´yt d´ale rozˇs´ıˇrena v pˇr´ıpadˇe, ˇze m´ame dva pohledy na stejnou sc´enu z r˚ uzn´ych smˇer˚ u
I
dva pohledy mohou b´yt z´ısk´any soubˇeˇznˇe v jeden okamˇzik (dva pˇr´ıstroje)
I
nebo jedn´ım pˇr´ıstrojem postupnˇe za sebou (pohyb pˇr´ıstroje pˇred objektem)
I
podobnˇe pohyb objektu pˇred pˇr´ıstrojem (stejn´e)
I
tyto u ´lohy jsou du´aln´ı a vedou na stejn´e ˇreˇsen´ı
Metody Poˇ c´ıtaˇ cov´ eho Vidˇ en´ı (MPV) - 3D poˇ c´ıtaˇ cov´ e vidˇ en´ı
29 / 51
I
prvn´ı a druh´y pohled je pops´an matic´ı projekce P resp. P0
I
oznaˇcen´ı 0 pouˇzije pro druh´y pohled
I
d´ale plat´ı ... x = PX a x0 = P0 X
I
body v obraze x a x0 jsou tzv. sobˇe koresponduj´ıc´ı body protoˇze poch´azej´ı projekc´ı od stejn´eho prostorov´eho bodu X projektivn´ı geometrie dvou pohled˚ u umoˇzn ˇuje ˇreˇsit n´asleduj´ıc´ı skupiny probl´em˚ u:
I
I
I
I
geometrie korespondence - pro dan´y bod x n´as zaj´ım´a, v jak´e ˇc´asti v druh´em obrazu je jeho korespondent x0 geometrie pohybu kamery - zn´ame mnoˇzinu sobˇe koresponduj´ıc´ıch obrazov´ych bod˚ u a zaj´ım´a n´as, jak´y pohyb je kamery (tedy pohyb mezi sn´ımkem jedna a dva) geometrie trojrozmˇern´e sc´eny - opˇet zn´ame sobˇe koresponduj´ıc´ı obrazov´e body a zaj´ım´a n´as jejich pozice ve 3D
Metody Poˇ c´ıtaˇ cov´ eho Vidˇ en´ı (MPV) - 3D poˇ c´ıtaˇ cov´ e vidˇ en´ı
30 / 51
Epipol´arn´ı geometrie
I I I
epipol´arn´ı geometrie popisuje vz´ajemn´y vztah dvou pohled˚ u na sc´enu vˇsechny vztahy a v´ypoˇcty epipol´arn´ı geometrie jsou nez´avisl´e na geometrii sc´eny z´avis´ı pouze na vnitˇrn´ıch parametrech dan´ych dvou pohled˚ ua na jejich vz´ajemn´e pozici
Metody Poˇ c´ıtaˇ cov´ eho Vidˇ en´ı (MPV) - 3D poˇ c´ıtaˇ cov´ e vidˇ en´ı
31 / 51
I I I I
b je b´ aze, spojnice stˇred˚ u kamer b = C2 − C1 epip´ol ei ∈ πi je obraz stˇred˚ u v obrazov´e rovinˇe, e1 = P1 C2 a e2 = P2 C1 li ∈ πi je obraz roviny (epipol´ arn´ı roviny) spojuj´ıc´ı prostorov´e body = (C2 , X , C1 ) li je epilop´ arn´ı pˇr´ımka
Metody Poˇ c´ıtaˇ cov´ eho Vidˇ en´ı (MPV) - 3D poˇ c´ıtaˇ cov´ e vidˇ en´ı
32 / 51
Epipol´arn´ı podm´ınka
I
vych´az´ı z podm´ınky, ˇze d1 , d2 a b leˇz´ı v jedn´e rovinˇe
I
epipol´arn´ı geometrii je moˇzn´e zcela zahrnout do jedn´e 3 × 3 matice, tzv. fundament´aln´ı matice
I
obrazov´y bod x v prvn´ım pohledu a bod x0 z druh´eho pohledu jsou projekce spoleˇcn´eho bodu X pak plat´ı: x0T Fx = 0
I
tento vztah se naz´yv´a epipol´ arn´ı podm´ınka
I
matice F se naz´yv´a fundament´ aln´ı matice
Metody Poˇ c´ıtaˇ cov´ eho Vidˇ en´ı (MPV) - 3D poˇ c´ıtaˇ cov´ e vidˇ en´ı
(10)
33 / 51
I
I I I
pokud F popisuje vztah kamer P1 a P2 pak transponovan´a matice FT pak popisuje kamery P2 a P1 epipol´arn´ı pˇr´ımka v druh´em obraze je vyj´adˇrena jako l0 = Fx a podobnˇe l = FT x0 pro epip´ol v druh´em obraze plat´ı e0T F = 0, tedy je to lev´y nulov´y prostor fundament´aln´ı matice, a podobnˇe pro epip´ol v prvn´ım obraze Fe = 0 je prav´y nulov´y prostor.
Metody Poˇ c´ıtaˇ cov´ eho Vidˇ en´ı (MPV) - 3D poˇ c´ıtaˇ cov´ e vidˇ en´ı
34 / 51
Fundament´aln´ı matice
I
fundament´aln´ı matice F je ˇctvercov´a homogenn´ı matice velikosti 3 × 3
I
hodnost matice je 2, je singul´arn´ı (det(A) = 0), a m´a 7 stupˇ n˚ u volnosti
I
m´a prav´y a lev´y nulov´y prostor, kter´e odpov´ıdaj´ı epip´ol˚ um
I
fundament´aln´ı matice m˚ uˇze b´yt urˇcena numerick´ym v´ypoˇctem pouze z nˇekolika sobˇe koresponduj´ıc´ıch bod˚ u
I
princip v´ypoˇctu vych´az´ı ze zm´ınˇen´e epipol´arn´ı podm´ınky, kter´a mus´ı platit pro kaˇzd´y p´ar bod˚ u
Metody Poˇ c´ıtaˇ cov´ eho Vidˇ en´ı (MPV) - 3D poˇ c´ıtaˇ cov´ e vidˇ en´ı
35 / 51
Urˇcen´ı fundament´aln´ı matice I
mˇejme tedy nˇekolik sobˇe koresponduj´ıc´ıch bod˚ u x ↔ x0
I
necht’ plat´ı epipol´arn´ı podm´ınka x0 Fx = 0
I
pokud je x = (x, y , 1) a x0 = (x 0 , y 0 , 1), pak epipol´arn´ı podm´ınku m˚ uˇzeme pro jeden p´ar rozepsat jako: x 0 xf11 +x 0 yf12 +x 0 f13 +y 0 xf21 +y 0 yf22 +y 0 f23 +xf31 +yf32 +f33 = 0 (11)
I
tento vztah urˇcuje sloupcov´y 9 × 1vektor f
I
f pˇredstavuje postupnˇe ˇr´adky matice F
I
parametry pˇredchoz´ı rovnice formuj´ı jeden ˇr´adek (rovnici) line´arn´ı soustavy rovnic (x 0 x, x 0 y , x 0 , y 0 x, y 0 y , y 0 , x, y , 1)
Metody Poˇ c´ıtaˇ cov´ eho Vidˇ en´ı (MPV) - 3D poˇ c´ıtaˇ cov´ e vidˇ en´ı
(12)
36 / 51
I
pro n vz´ajemn´e koresponduj´ıc´ıch bod˚ u v prvn´ım a druh´em obraze z´ısk´ame maticov´y z´apis n rovnic : x10 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 (13) pokud je hodnost matice A pr´avˇe 8, pak existuje pr´avˇe jedno netrivi´aln´ı ˇreˇsen´ı, coˇz je prav´y nulov´y prostor matice A v d˚ usledku pˇr´ıtomnosti ˇsumu je tato soustava pˇreurˇcen´a a tedy ˇcasto nem´a ˇreˇsen´ı z´akladn´ı postup nalezen´ı odhadu ˇreˇsen´ı je v´ypoˇcet takov´eho f s nejmenˇs´ım kvadr´atem chyby ... postup je totoˇzn´y s postupem pouˇzit´ı SVD rozkladu napˇr. pˇri urˇcen´ı homografie tedy minimalizujeme normu ||Af|| s podm´ınkou mˇeˇr´ıtka ||f|| = 1 v tomto kontextu nalezen´ı ˇreˇsen´ı pouˇz´ıv´ame oznaˇcen´ı 8-bodov´ y algoritmus.
I I I
I I
Metody Poˇ c´ıtaˇ cov´ eho Vidˇ en´ı (MPV) - 3D poˇ c´ıtaˇ cov´ e vidˇ en´ı
37 / 51
I
pokud nen´ı F singul´arn´ı (rank(F > 2)), pak se epipol´arn´ı pˇr´ımky neprot´ınaj´ı v jednom bodˇe (chyba)
I
pro zajiˇstˇen´ı hodnosti 2 m˚ uˇzeme prov´est znovu SVD rozkladu opravenou F0 z´ısk´ame zpˇetnˇe pˇren´asoben´ım F = UDVT , kde uprav´ıme D = diag (r , s, t) s t´ım r ≥ s ≥ t a fundament´aln´ı matice F0 = Udiag (r , s, 0)VT minimalizuje Frobeniovu normu ||F − F0 || a jedn´a se o nejbliˇzˇs´ı singul´arn´ı matici k p˚ uvodn´ı matici F
I I
Metody Poˇ c´ıtaˇ cov´ eho Vidˇ en´ı (MPV) - 3D poˇ c´ıtaˇ cov´ e vidˇ en´ı
38 / 51
Dalˇs´ı moˇznosti zpˇresnˇen´ı nalezen´eho odhadu ˇreˇsen´ı fundament´aln´ı matice: I
A je obecnˇe pˇredurˇcena ke ˇspatn´e numerick´e stabilitˇe v´ypoˇctu, protoˇze A je ˇspatnˇe podm´ınˇen´a (velk´a rozd´ılnost prvk˚ u ... v ˇr´adech)
I
proto se ˇcasto matice pˇred vlastn´ım v´ypoˇctem normalizuje tzv. umˇel´e sn´ıˇzen´ı rozd´ılnosti jej´ı prvk˚ u
I
dalˇs´ı u ´prava pro zv´yˇsen´ı robustnosti v´ypoˇctu fundamnt´aln´ı matice je pouˇzit´ı pouze 7 bod˚ u a n´asledn´y postprocesing (tzv. 7 bodov´y algoritmus)
Metody Poˇ c´ıtaˇ cov´ eho Vidˇ en´ı (MPV) - 3D poˇ c´ıtaˇ cov´ e vidˇ en´ı
39 / 51
Automatick´y v´ypoˇcet fundament´aln´ı matice
I
ˇcasto nem´ame jistotu, ˇze vˇsechny nalezen´e p´ary jsou korespondenti (jsou nalezeny automaticky)
I
pak mus´ıme pouˇz´ıt nˇejakou metodu iterativn´ıho zkouˇsen´ı a hled´an´ı ˇreˇsen´ı, napˇr.: I
I
pouˇzit´ı Least median of squared residuals (LMedS) (r. 1984), metoda pˇredpokl´ad´a alespoˇ n 50 % vˇsech p´ar˚ u jsou spr´avn´ı korespondenti, nebo Random Sample Consensus (RANSAC) (r. 1981) aˇz 90 % bod˚ u m˚ uˇze b´yt ˇspatnˇe koresponduj´ıc´ı
Metody Poˇ c´ıtaˇ cov´ eho Vidˇ en´ı (MPV) - 3D poˇ c´ıtaˇ cov´ e vidˇ en´ı
40 / 51
Esenci´aln´ı matice I I I
I
historicky byla esenci´aln´ı matice pops´ana dˇr´ıve neˇz matice fundament´aln´ı (r. 1981) tato matice m´a m´enˇe stupˇ n˚ u volnosti neˇz fundamant´aln´ı matice, jen 5 stupˇ n˚ u volnosti oznaˇcme projekˇcn´ı matice obou pohled˚ u jako: P = K[I, −C1 ] P0 = K0 R[I, −(C1 + b)] a vektor b = (b1 , b2 , b3 ) matice R pˇredstavuje relativn´ı rotaci druh´e kamery v˚ uˇci kameˇre prvn´ı a vektor b je posun stˇredu druh´e kamery od prvn´ı kamery x0T Fx = x0T K0−T EK−1 x = 0
I
(14)
matice E se naz´yv´a esenci´aln´ı matice a tedy F = K0−T EK−1
Metody Poˇ c´ıtaˇ cov´ eho Vidˇ en´ı (MPV) - 3D poˇ c´ıtaˇ cov´ e vidˇ en´ı
(15) 41 / 51
I
a naopak pˇren´asoben´ım kalibraˇcn´ı matic´ı zprava a zleva z´ısk´ame vztah pro v´ypoˇcet esenci´aln´ı matice z fundament´aln´ı matice jako: E = K0T FK
I
pro esenci´aln´ı matici d´ale plat´ı: E = RS(b)
I
(16)
kde S(b) je antisymetrick´a matice: 0 −b3 b2 0 −b1 S(b) = b3 −b2 b1 0 I
I
(17)
(18)
esenci´aln´ı matice zachycuje relativn´ı pozici druh´e kamery oproti prvn´ı kameˇre hodnost matice rank(E) ≤ 2 (5 stupˇ n˚ u volnosti = 3 rotace + 3 translace -1 nejednoznaˇcnost rozkladu - prvn´ı dvˇe vlastn´ı ˇc´ısla jsou stejn´e a tˇret´ı je nulov´e
Metody Poˇ c´ıtaˇ cov´ eho Vidˇ en´ı (MPV) - 3D poˇ c´ıtaˇ cov´ e vidˇ en´ı
42 / 51
Odhad pohybu kamery I
I I I
odhad pohybu kamery spoˇc´ıv´a v urˇcen´ı vektoru b´aze b a matice rotace R ze zn´am´e mnoˇziny koresponduj´ıc´ıch bod˚ u k≥8 jde tedy o nalezen´ı a rozklad esenci´aln´ı matice v z´akladu m˚ uˇze b´yt esenci´aln´ı matice urˇcena z fundament´aln´ı matice pouˇzit´ım kalibraˇcn´ıch matic obou pohled˚ u pokud nezn´amˇe tyto dvˇe projekˇcn´ı matice ... odhad esenci´aln´ı matice stejn´ym zp˚ usobem jako odhad fundament´aln´ı matice I I
I
jak? Pokud prvn´ı pohled plat´ı P = K[R|t] a plat´ı, ˇze x = PX pak pouˇzijeme vztahu reprojekce s kalibraˇcn´ı matic´ı a z´ısk´ame bod ˆ x = K−1 x, kter´y naz´yv´ame bod v normalizovan´ych souˇradnic´ıch jin´ymi slovy bod v tˇechto souˇradnic´ıch z´ısk´ame projekc´ı s jedniˇckovou kalibraˇcn´ı matic´ı I (ohniskov´a vzd´alenost je 1) a bod mˇeˇren´y v obraze vyd´avat za tento bod
Metody Poˇ c´ıtaˇ cov´ eho Vidˇ en´ı (MPV) - 3D poˇ c´ıtaˇ cov´ e vidˇ en´ı
43 / 51
I
potom pro projekci mluv´ıme o matici normalizovan´e kamery, ztr´ac´ıme mˇeˇr´ıtko.
I
dostaneme prvn´ı pohled jako P = [I|0] a druh´y pohled se stejnou projekc´ı, ale s pootoˇcen´ım a posunem je P0 = [R|b]
I
epipol´arn´ı podm´ınka pro formulov´an´ı rovnic z´ısk´a tvar: ˆ x0T Eˆ x=0
I
(19)
esenci´aln´ı matici pak m˚ uˇzeme urˇcit stejn´ym postupem jako matici fundament´aln´ı, napˇr. 8-bodov´ym algoritmem
Metody Poˇ c´ıtaˇ cov´ eho Vidˇ en´ı (MPV) - 3D poˇ c´ıtaˇ cov´ e vidˇ en´ı
44 / 51
Rozklad esenci´aln´ı matice I
rozklad esenci´aln´ı matice na E = SR pouˇzijeme zn´am´y SVD rozklad
I
nejprve si definuje pomocn´e matice 0 −1 0 W = 1 0 0 0 0 1
(20)
matice W je ortogon´aln´ı
0 1 0 Z = −1 0 0 0 0 0
(21)
a matice Z je antisymentrick´a
Metody Poˇ c´ıtaˇ cov´ eho Vidˇ en´ı (MPV) - 3D poˇ c´ıtaˇ cov´ e vidˇ en´ı
45 / 51
I
pokud SVD rozklad E = UDVT
I
matice rotace je moˇzn´e urˇcit dvˇema zp˚ usoby, bud’ jako R = UWVT nebo jako R = UWT VT (nezn´am´e znam´ınko)
I
d´ale matice S je d´ana jako S = UZUT resp. b = V(0, 0, |β|)T (opˇet nezn´am´e znam´ınko)
I
jin´ymi slovy m´ame dvˇe moˇznosti jak urˇcit matici R a dvˇe moˇznosti (znam´enko) jak urˇcit posun
I
v kombinaci z´ısk´ame celkem ˇctyˇri moˇzn´a (spr´avn´a) ˇreˇsen´ı pro matici P0
I
avˇsak pouze jedno z tˇechto ˇreˇsen´ı pˇredstavuje pozorov´an´ı sc´eny pˇred obˇema pohledy (kamerami).
Pozn´amka: esenci´aln´ı (fundament´aln´ı) matici je moˇzn´e pouˇz´ıt pˇr´ımo pro 3D rekonstrukci z p´aru nezkalibrovan´ych kamer (aˇz r. 1990) Existuje nˇekolik postup˚ u a doplˇ nuj´ıc´ıch podm´ınek jak z´ıskat spr´avnou metrickou rekonstrukci.
Metody Poˇ c´ıtaˇ cov´ eho Vidˇ en´ı (MPV) - 3D poˇ c´ıtaˇ cov´ e vidˇ en´ı
46 / 51
3D rekonstrukce - Linear triangulation
pokud zn´ame dvˇe projekˇcn´ı matice P a P0 I a souˇ casnˇe m´ame koresponduj´ıc´ı p´ar, tedy obrazov´y bod v prvn´ım pohledu x a obrazov´y bod v druh´em pohledu x0 I pak m˚ uˇzeme urˇcit 3D souˇradnici nezn´am´eho bodu Pozn´amka: jedin´e body,kter´e nelze rekonstruovat jsou body leˇz´ıc´ı na spojnici mezi stˇredy kamer I
Metody Poˇ c´ıtaˇ cov´ eho Vidˇ en´ı (MPV) - 3D poˇ c´ıtaˇ cov´ e vidˇ en´ı
47 / 51
I
pro tento p´ar mus´ı platit epipol´arn´ı podm´ınka, tedy x0T Fx = 0
I
pro bod x m˚ uˇzeme oˇcek´avat bod x0 na epipol´arn´ı pˇr´ımce
I
rovina spojuj´ıc´ı prostorov´y bod X a stˇredy kamer urˇcuje epipol´arn´ı pˇr´ımky v obou pohledech
I
plat´ı x = PX a x0 = P0 X a m˚ uˇzeme pˇrev´est probl´em na formu AX = 0
I
mˇeˇr´ıtko dan´e homogenn´ı souˇradnic´ı je eliminov´ano vektorov´ym souˇcinem napˇr. pro prvn´ı pohled jako x × PX = 0 x(p3T X) − (p1T X) = 0 y (p3T X) − (p2T X) = 0 x(p2T X) − y (p1T X) = 0
Metody Poˇ c´ıtaˇ cov´ eho Vidˇ en´ı (MPV) - 3D poˇ c´ıtaˇ cov´ e vidˇ en´ı
48 / 51
I
jen 2 rovnice jsou vˇzdy line´arnˇe nez´avisl´e
I
po vypuˇstˇen´ı tˇret´ı rovnice dost´av´ame vztah pro urˇcen´ı matice A sloˇzen´e ze ˇctyˇr rovnic (odpov´ıdaj´ıc´ı dvou bod˚ um)
I
kaˇzd´y bod po dvou souˇradnic´ıch korespondenˇcn´ıho p´aru
I
ˇreˇsen´ım soustavy z´ısk´av´ame nezn´am´y vektor 4 × 1 X, tedy 3D rekonstrukci 3T xp − p1T y p3T − p2T A= (22) x 0 p03T − p01T y 0 p03T − p02T
Metody Poˇ c´ıtaˇ cov´ eho Vidˇ en´ı (MPV) - 3D poˇ c´ıtaˇ cov´ e vidˇ en´ı
49 / 51
I
ˇcasto mˇeˇren´ı obsahuje ˇsum a soustava nem´a netrivi´aln´ı ˇreˇsen´ı
I
nalezen´ı nejlepˇs´ıho odhadu nez´am´eho bodu je podobn´e pˇredchoz´ım pˇr´ıpad˚ um
I
tedy SVD rozklad A = UDVT a ˇreˇsen´ı je posledn´ı sloupec matice V odpov´ıdaj´ıc´ı nejmenˇs´ımu vlastn´ımu ˇc´ıslu
I
nalezen´y odhad ˇreˇsen´ı dehomogenizujeme tak, X = (x1 , x2 , x3 , x4 )T podˇel´ıme posledn´ı (homogenn´ı) souˇradnic´ı, tedy: (x, y , z)T = (x1 /x4 , x2 /x4 , x3 /x4 )T
Metody Poˇ c´ıtaˇ cov´ eho Vidˇ en´ı (MPV) - 3D poˇ c´ıtaˇ cov´ e vidˇ en´ı
50 / 51
Algoritmus tzv. ˇr´ıdk´e 3D stereo rekonstrukce: I
pouˇziji nˇejak´y detektor v´yznamn´ych bod˚ u, detekce tzv. stabiln´ıch bod˚ u ... invariantn´ıch zmˇenˇe a posunu pohledu
I
spoˇc´ıtat lok´aln´ı deskriptor kaˇzd´eho dobu v obou pohledech
I
prov´est pˇredbˇeˇzn´e p´arov´an´ı nalezen´ych bod˚ u porovn´an´ım vektor˚ u z deskriptoru
I
nal´ezt pouze spr´avn´e korespondenty napˇr. s pomoc´ı metody RANSAC a splnˇen´ım epipol´arn´ı podm´ınky
I
prov´est 3D rekonstrukci tˇechto spr´avn´ych korespondent˚ u
Metody Poˇ c´ıtaˇ cov´ eho Vidˇ en´ı (MPV) - 3D poˇ c´ıtaˇ cov´ e vidˇ en´ı
51 / 51
