Metody Poˇc´ıtaˇcov´eho Vidˇen´ı (MPV) - 3D poˇc´ıtaˇcov´e vidˇen´ı Projektivn´ı geometrie
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
Projektivn´ı geometrie I projektivn´ ı prostor I projektivita I projektivn´ ı transformace Perspektivn´ı kamera I model kamery I kalibrace kamery I rozklad matice projekce
Metody Poˇ c´ıtaˇ cov´ eho Vidˇ en´ı (MPV) - 3D poˇ c´ıtaˇ cov´ e vidˇ en´ı
1 / 55
Obsah pˇredn´aˇsky
I
I
Projektivn´ı geometrie I projektivn´ ı prostor I projektivita I projektivn´ ı transformace Perspektivn´ı kamera I model kamery I kalibrace kamery I rozklad matice projekce
Metody Poˇ c´ıtaˇ cov´ eho Vidˇ en´ı (MPV) - 3D poˇ c´ıtaˇ cov´ e vidˇ en´ı
2 / 55
Projektivn´ı geometrie ´ Uvod do projektivn´ı geometrie, reprezentace a z´apis I
bod ve 2D prostoru budeme znaˇcit x ∈ R2
I
bod ve 3D prostoru budeme znaˇcit X
I
pˇr´ımka ve 2D prostoru n
I
pˇr´ımka ve 3D prostoru O
I
rovina ve 3D prostoru φ, ϕ
Vektorov´e reprezentace pak budou n´asleduj´ıc´ı: bod v rovinˇe x = [u, v ]T , nebo x = [x, y ]T , bod v prostoru X = [x1 , x2 , x3 ]T nebo X = [x, y , z]T , pˇr´ımka n = [a, b, c]T Geometrick´e entity budeme uvaˇzovat jako sloupcov´y vektor, n´asoben´ı matice t´ımto sloupcov´ym vektorem zprava m´a v´ysledek opˇet sloupcov´y vektor.
Metody Poˇ c´ıtaˇ cov´ eho Vidˇ en´ı (MPV) - 3D poˇ c´ıtaˇ cov´ e vidˇ en´ı
3 / 55
Projektivn´ı prostor P2 I
I
I
I
I I
pˇr´ımka v rovinˇe je reprezentov´ana obecnou rovnic´ı pˇr´ımky: ax + by + c = 0 zmˇena parametr˚ u a, b a c n´am urˇcuje odliˇsnou pˇr´ımku ... pˇrirozenˇe pak pˇr´ımka m˚ uˇze b´yt vyj´adˇrena vektorem n = [a, b, c]T vztah obecn´ a rovnice ↔ vektor ... rovnice pˇr´ımky ax + by + c = 0 a (ka)x + (kb)y + (kc) = 0 jsou stejn´e → ale odliˇsn´y vektor k je mˇeˇr´ıtko 7→ vˇsechny vektory liˇs´ıc´ı se pouze v mˇeˇr´ıtku pˇredstavuj´ı jednu tˇr´ıdu prvk˚ u (pˇr´ımku) tento vztah ekvivalence je zn´am´ı jako homogenn´ı vektor mnoˇzina vˇsech tˇechto tˇr´ıd prvk˚ u v R3 − [0, 0, 0]T tvoˇr´ı projektivn´ı prostor P2 (vektor [0, 0, 0]T nekoresponduje ˇz´adn´e pˇr´ımce a je z prostoru vyjmut)
Metody Poˇ c´ıtaˇ cov´ eho Vidˇ en´ı (MPV) - 3D poˇ c´ıtaˇ cov´ e vidˇ en´ı
4 / 55
P2 - homogenn´ı reprezentace bodu I
bod v rovinˇe x = [x, y ]T leˇz´ı na pˇr´ımce n = [a, b, c]T ⇔ ax + by + c = 0
I
podm´ınka lze zapsat jako skal´arn´ı souˇcin [x, y , 1][a, b, c]T = 0
I
p˚ uvodn´ı bod v rovinˇe, definovan´y v R2 , je proto reprezentovan´y vektorem o velikosti 3 pˇrid´an´ım tˇret´ı souˇradnice 1 (homogenn´ı souˇradnice)
I
pro k, kdy [kx, ky , k] je zm´ınˇen´a podm´ınka tak´e splnˇena ⇔ [x, y , 1][a, b, c]T = 0
I
pak bod [x, y , 1] i vˇsechny body k[x, y , 1] v P2 reprezentuj´ı stejn´y bod v nehomogenn´ıch souˇradnic´ıch [x, y ]T v R2 ... z´ısk´ame ho jako [x1 /x3 , x2 /x3 ]T .
Metody Poˇ c´ıtaˇ cov´ eho Vidˇ en´ı (MPV) - 3D poˇ c´ıtaˇ cov´ e vidˇ en´ı
5 / 55
Pˇr´ımka a bod I
pr˚ useˇc´ık dvou pˇr´ımek n a n0 je d´an vektorov´ym souˇcinem: n × n0
I
bod x = [x1 , x2 , 0]T patˇr´ı do P2
I
jeho nehomogenn´ı souˇradnice v R2 tedy [x1 /0, x2 /0]T → bod, kter´y v rovinˇe m´a nekoneˇcn´e souˇradnice ... bodu ˇr´ık´ame Ideal Point - bod v nekoneˇcnu
I
takov´yto bod je vlastnˇe pr˚ useˇc´ıkem dvou rovnobˇeˇzn´ych pˇr´ımek
I
vˇsechny body v nekoneˇcnu leˇz´ı na jedn´e ”pˇr´ımce v nekoneˇcnu”[0, 0, 1]T
Podobn´e odvozen´ı nalezneme pro z´apis pr˚ useˇc´ık˚ u dvou pˇr´ımek, nebo pro z´ısk´an´ı pˇr´ımky spojen´ım dvou bod˚ u.
Metody Poˇ c´ıtaˇ cov´ eho Vidˇ en´ı (MPV) - 3D poˇ c´ıtaˇ cov´ e vidˇ en´ı
6 / 55
Shrnut´ı I
bod x leˇz´ı na pˇr´ımce l pokud xT l = 0
I
pr˚ useˇc´ık m dvou pˇr´ımek n a n0 (i rovnobˇeˇzn´ych) je d´an vektorov´ym souˇcinem: m = n × n0 (rovnobˇeˇzn´e pˇr´ımky maj´ı pr˚ useˇc´ık bod v nekoneˇcnu)
I
pˇr´ımka n spojuj´ıc´ı dva body m a m0 je analogicky: n = m × m0
I
myˇslenka zaveden´ı projektivn´ıho prostoru je zaveden´ı nˇejak´eho popisu pro perspektivu
I
geometrick´e objekty jako je bod, pˇr´ımka a rovina jsou zapisov´any vektorovˇe
I
pak vztahy mezi tˇemito objekty je moˇzn´e zapisovat jednoduˇseji nˇeˇz kdyby se zapisovaly v nehomogenn´ıch souˇradnic´ıch
Metody Poˇ c´ıtaˇ cov´ eho Vidˇ en´ı (MPV) - 3D poˇ c´ıtaˇ cov´ e vidˇ en´ı
7 / 55
Model pro projektivn´ı rovinu a princip duality I
I I I
body v P2 jsou paprsky v R3 ... mnoˇzina vˇsech vektor˚ u x = k[x1 , x2 , x3 ]T s mˇen´ıc´ım se k formuje paprsek, kter´y smˇeˇruje ze stˇredu prom´ıt´an´ı analogicky pˇr´ımka v prostoru P2 odpov´ıd´a rovinˇe v R3 proch´azej´ıc´ı stˇredem projekce obdobnˇe dva odliˇsn´e paprsky urˇcuj´ı zm´ınˇenou rovinu stejnˇe jako dva odliˇsn´e body urˇcuj´ı R2 pˇr´ımku obr´acenˇe ... dvˇe pˇr´ımky maj´ı spoleˇcn´y bod - pr˚ useˇc´ık a tedy dvˇe roviny maj´ı spoleˇcn´y pr˚ useˇc´ık ... paprsek
Metody Poˇ c´ıtaˇ cov´ eho Vidˇ en´ı (MPV) - 3D poˇ c´ıtaˇ cov´ e vidˇ en´ı
8 / 55
Projektivita
Definice Projektivita je invertibiln´ı mapov´an´ı h bod˚ u v P2 (tedy homogenn´ıch 3 × 1 vektor˚ u) do sam´eho prostoru P2 ⇔ tˇri body x1 , x2 a x3 leˇz´ıc´ı na spoleˇcn´e pˇr´ımce jsou mapov´any na body h(x1 ), h(x2 ) a h(x3 ), kter´e leˇz´ı tak´e na spoleˇcn´e pˇr´ımce. Pozn´amka. Projektivita je tak´e nˇekdy naz´yv´ana kolineace, projektivn´ı transformace, nebo homografie. Tyto oznaˇcen´ı jsou synonyma.
Metody Poˇ c´ıtaˇ cov´ eho Vidˇ en´ı (MPV) - 3D poˇ c´ıtaˇ cov´ e vidˇ en´ı
9 / 55
D˚ usledek Mapov´an´ı h : P2 → P2 je projektivita pouze a jen, existuje-li nesingul´arn´ı matice H, 3 × 3, (det(H) 6= 0), pro kterou plat´ı, ˇze nˇejak´y bod v P2 reprezentovan´y vektorem x lze transformovat jako h(x) = Hx.
Metody Poˇ c´ıtaˇ cov´ eho Vidˇ en´ı (MPV) - 3D poˇ c´ıtaˇ cov´ e vidˇ en´ı
10 / 55
pρ
ρ
S π
R=R′
B′
A′ p ′
B A
p
Pozn´amka: jde vlastnˇe o projektivn´ı zobrazen´ı roviny do roviny
Metody Poˇ c´ıtaˇ cov´ eho Vidˇ en´ı (MPV) - 3D poˇ c´ıtaˇ cov´ e vidˇ en´ı
11 / 55
Projektivn´ı transformace I
projektivn´ı transformace je line´arn´ı transformace homogenn´ıho vektoru nesingul´arn´ı 3 × 3 matic´ı d´ana jako: 0 x1 h11 h12 h13 x1 x20 = h21 h22 h23 x2 (1) x30 h31 h32 h33 x3
I
matice H m´a 8 stupˇ n˚ u volnosti → pomˇer˚ um dvojic 9 prvk˚ u matice
I
pˇren´asoben´ı matice konstantou k nemˇen´ı definovanou transformaci a konstanta pˇredstavuje pouze mˇeˇr´ıtko
I
H je jednoznaˇcnˇe je urˇcena ˇctveˇric´ı sobˇe koresponduj´ıc´ıch bod˚ u nebo pˇr´ımek v obecn´e pozici
Metody Poˇ c´ıtaˇ cov´ eho Vidˇ en´ı (MPV) - 3D poˇ c´ıtaˇ cov´ e vidˇ en´ı
12 / 55
Shrnut´ı I
koline´arn´ı body (body leˇz´ıc´ı na spoleˇcn´e pˇr´ımce) jsou opˇet transformov´any na koline´arn´ı body
I
nˇekolik r˚ uznobˇeˇzn´ych pˇr´ımek se spoleˇcn´ym pr˚ useˇc´ıkem jsou transformov´any opˇet na r˚ uznobˇeˇzn´e pˇr´ımky s jedn´ım spoleˇcn´ym pr˚ useˇc´ıkem
I
poˇrad´ı koline´arn´ıch bod˚ u je zachov´ano (viz pozdˇeji)
I
bod x je transformov´an na bod x0 tak, ˇze: x0 = Hx
I
pˇr´ımka l je transformov´an na pˇr´ımku l0 tak, ˇze: l0 = H −T l
Pˇr´ıkladem takov´eho transformace poˇr´ızen´ı stejn´e sc´eny r˚ uzn´ym fotoapar´atem, nebo pˇribl´ıˇzen´ı (ZOOM), nebo pootoˇcen´ı kamery (ve stˇredu projekce, viz d´ale), nebo vˇse najednou.
Metody Poˇ c´ıtaˇ cov´ eho Vidˇ en´ı (MPV) - 3D poˇ c´ıtaˇ cov´ e vidˇ en´ı
13 / 55
Urˇcen´ı 2D projektivn´ı transformace
I
2D homografie je d´ana mnoˇzinou bod˚ u xi v prostoru P2 a mnoˇzinou koresponduj´ıc´ıch bod˚ u ve stejn´em P2
I
nalezen´ı takov´eto transformace z xi ↔ x0i znamen´a urˇcit matici H tak, ˇze plat´ı Hxi = x0i pro kaˇzd´e i.
I
minim´aln´ı poˇcet potˇrebn´ych bod˚ u ↔ poˇctu stupˇ n˚ u volnosti hledan´e transformace ... obecn´a projektivn´ı transformace ... 3 × 3 matice (9 prvk˚ u) ale 8 stupˇ n˚ u volnosti
I
1 bod m´a dva stupnˇe volnosti, tedy souˇradnice (x, y ) → ˇctyˇri body a korespondenty
Metody Poˇ c´ıtaˇ cov´ eho Vidˇ en´ı (MPV) - 3D poˇ c´ıtaˇ cov´ e vidˇ en´ı
14 / 55
I
vztah Hxi = x0i urˇcuje soustavu line´arn´ıch rovnic (s pravou stranou)
I
xi a Hxi nejsou stejn´e vektory, ale maj´ı stejn´y smˇer a liˇs´ı se pouze velikost´ı, viz obr´azek
I
m˚ uˇzeme pˇrepsat jako vektorov´y souˇcin x0i × Hxi = 0 a pak: 0 3T yi h xi − wi0 h2T xi x0i × Hxi = wi0 h1T xi − xi0 h3T xi xi0 h2T xi − yi0 h1T xi
(2)
I
h1T je sloupcov´y vektor odpov´ıdaj´ıc´ı prvn´ımu ˇr´adku matice H
I
transformovan´y bod (tedy x0i ) je v homogenn´ıch souˇradnic´ıch znaˇcen x0i = (xi0 , yi0 , wi0 )
Metody Poˇ c´ıtaˇ cov´ eho Vidˇ en´ı (MPV) - 3D poˇ c´ıtaˇ cov´ e vidˇ en´ı
15 / 55
Maticov´y z´apis soustavy line´arn´ıch rovnic pak pˇrepisem z´ısk´ame jako: T 1 0 −wi0 xT yi0 xT h i i T 0 xT h2 = 0 w 0 xT 0 −x (3) i i i i 0 xT T 3 −yi0 xT x 0 h i i i I
pro i oznaˇc´ıme soustavu jako Ai h = 0, kde vektor h je sloupcov´y vektor 9 × 1 sloˇzen´y ze tˇrech ˇr´adk˚ u matice H
I
ze 3 rovnic jsou jen dvˇe line´arnˇe nez´avisl´e; 3. rovnice je pˇre-n´asoben´y souˇcet prvn´ı a druh´e rovnice ⇒ 3. ˇr´adek lze vypustit: T h1 0 xT 0 −wi0 xT y i i i h2 = 0 (4) T 0 xT wi0 xT 0 −x i i i h3
Metody Poˇ c´ıtaˇ cov´ eho Vidˇ en´ı (MPV) - 3D poˇ c´ıtaˇ cov´ e vidˇ en´ı
16 / 55
I
tˇret´ı homogenn´ı souˇradnice prom´ıtnut´eho bodu (wi0 ) m˚ uˇze b´yt zvolena wi0 = 1 jsou mˇeˇreny v obraze, jin´a volba je tak´e moˇzn´a
I
ˇreˇs´ıme soustavu rovnic Ah = 0 pˇresnˇe pro 4 body je rank(A) = 8 a existuje jedno ˇreˇsen´ı odpov´ıdaj´ıc´ı prav´emu nulov´emu prostoru a voliteln´e mˇeˇr´ıtko m˚ uˇze b´yt zvoleno tak aby ||h|| = 1
I
ˇcasto vol´ıme v´ıce bod˚ u (n > 4) a matice A m´a pak pˇr´ısluˇsn´y rozmˇer 2n × 9 T 0 −w10 xT y10 xT 1 1 w 0 xT 1 0T −x10 xT 1 h 1 1 .. .. .. h2 = 0 (5) . . . T 3 0 T 0 T 0 −wn xn yn xn h 0 T T wn xn 0 −xn0 xT n
Metody Poˇ c´ıtaˇ cov´ eho Vidˇ en´ı (MPV) - 3D poˇ c´ıtaˇ cov´ e vidˇ en´ı
17 / 55
I
v praxi mˇeˇren´ı obsahuj´ı chybu (ˇsum) a tak z´ıskan´a soustava je pˇreurˇcen´a, tedy neexistuje ˇreˇsen´ı rank(A) > 8
I
pak hled´ame takov´e ˇreˇsen´ı, kter´e minimalizuje chybu ||Ah||
I
pro tento u ´ˇcel pouˇzijeme SVD rozklad (singular value decomposition)
I
pak A = UDVT a hledan´e ˇreˇsen´ı h je posledn´ı sloupec matice V odpov´ıdaj´ıc´ı nejmenˇs´ımu vlastn´ımu ˇc´ıslu (prav´y nulov´y prostor matice A)
Metody Poˇ c´ıtaˇ cov´ eho Vidˇ en´ı (MPV) - 3D poˇ c´ıtaˇ cov´ e vidˇ en´ı
18 / 55
Obsah pˇredn´aˇsky
I
I
Projektivn´ı geometrie I projektivn´ ı prostor I projektivita I projektivn´ ı transformace Perspektivn´ı kamera I model kamery I kalibrace kamery I rozklad matice projekce
Metody Poˇ c´ıtaˇ cov´ eho Vidˇ en´ı (MPV) - 3D poˇ c´ıtaˇ cov´ e vidˇ en´ı
19 / 55
Perspektivn´ı kamera
I
obecn´y model perspektivn´ı kamery slouˇz´ı k popisu projekce 3D prostoru do 2D prostoru (obrazov´a rovina)
I
vˇzdy se jedn´a o stˇredovou projekci
I
speci´aln´ı pˇr´ıpad ... stˇred projekce leˇz´ı v nekoneˇcnu → afinn´ı kamera a jde o zobecnˇen´ı tzv. paraleln´ı projekce napˇr´ıklad paprsky slunce je moˇzn´e povaˇzovat za paraleln´ı projekci
I
model perspektivn´ı kamery je reprezentov´an matic´ı
I
matice transformuje homogenn´ı souˇradnice prostorov´eho bodu (ve 3D - velikost vektoru 4 × 1) do homogenn´ıch souˇradnic obrazov´eho bodu (ve 2D - velikost vektoru 3 × 1).
Metody Poˇ c´ıtaˇ cov´ eho Vidˇ en´ı (MPV) - 3D poˇ c´ıtaˇ cov´ e vidˇ en´ı
20 / 55
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´ı
21 / 55
I
kamera je reprezentovan´a matic´ı 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
a maticovˇe
m = PX
(6)
x m1 f 0 0 0 m2 = 0 f 0 0 y z m3 0 0 1 0 1
(7)
Metody Poˇ c´ıtaˇ cov´ eho Vidˇ en´ı (MPV) - 3D poˇ c´ıtaˇ cov´ e vidˇ en´ı
22 / 55
I I
z´ısk´ame projekci m = PX normalizujeme (na jedniˇcku) tˇret´ı homogenn´ı souˇradnici T 1 m2 e modeluje v´ypoˇcet projekce takto: [m m3 , m3 , 1] ... pak vlastnˇ m1 fx m2 fy m3 = = u, = = v, = 1 pro m3 6= 0 m3 z m3 z m3
I I
(8)
ˇ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´ı
23 / 55
Model obecn´e kamery (matice P) m´a dalˇs´ı prvky (5 vnitˇrn´ıch a 6 vnˇejˇs´ıch parametr˚ u), kter´e poskytuj´ı dalˇs´ı stupnˇe volnosti projekce: I zmˇ ena souˇradn´eho syst´emu obrazu: 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 24 / 55
I
posun a otoˇcen´ı poˇc´atku souˇradnic svˇetov´ych souˇradnic
I
X = R(X − C), kde RT R = I je matice rotace kamery oproti svˇetov´ym souˇradnic´ım
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´ı)
Metody Poˇ c´ıtaˇ cov´ eho Vidˇ en´ı (MPV) - 3D poˇ c´ıtaˇ cov´ e vidˇ en´ı
25 / 55
I
vˇse dohromady definuje obecn´y pˇredpis pro perspektivn´ı kameru, m = KR[I, −C]X, kde pouˇz´ıv´ame jednotn´e oznaˇcen´ı P = KR[I, −C]
(9)
P = K[R, t] kde t = −RC
(10)
nebo nˇekdy
I
obecn´a perspektivn´ı kamera m´a 11 stupˇ n˚ u volnosti
I
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´ı
26 / 55
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´ı
27 / 55
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´ı
28 / 55
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
(11)
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 (12) 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´ı
29 / 55
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= . (13) 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´ı
30 / 55
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´ı
31 / 55
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´ı
32 / 55
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´ı
33 / 55
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 jako Taylor˚ uv rozvoj 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
I
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´ı
34 / 55
I
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´ı obdobnˇe parametry zkreslen´ı mohou b´yt 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´ı
35 / 55
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 P = KR[I, −C]
Metody Poˇ c´ıtaˇ cov´ eho Vidˇ en´ı (MPV) - 3D poˇ c´ıtaˇ cov´ e vidˇ en´ı
36 / 55
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´ı
37 / 55
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´ı
38 / 55
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´ı
39 / 55
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´ı
40 / 55
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´ı
41 / 55
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´ı
42 / 55
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´ı
(14)
43 / 55
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´ı
44 / 55
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´ı
45 / 55
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´ı
46 / 55
Dalˇs´ı vlastnosti projektivn´ı geometrie I I I I I
Nevlastn´ı bod (vanishing point - u ´bˇeˇzn´ık) nevlastn´ı body lze nal´ezt v bˇeˇzn´em ˇzivotˇe, napˇr. dlouh´e rovn´e koleje se v oku (obr´azku) sb´ıhaj´ı koleje jsou rovnobˇeˇzn´e, v 3D prostoru se protnout nemohou projektivn´ı transformace vˇsak v obraze tyto dvˇe pˇr´ımky zd´anlivˇe pˇribliˇzuje tento zd´anliv´y pr˚ useˇc´ık je obrazem nevlastn´ıch bod˚ u tˇechto pˇr´ımek
Metody Poˇ c´ıtaˇ cov´ eho Vidˇ en´ı (MPV) - 3D poˇ c´ıtaˇ cov´ e vidˇ en´ı
47 / 55
Definice Nevlastn´ı bod je limit projekce nˇejak´eho body, kter´y se pohybuje po libovoln´e prostorov´e pˇr´ımce do nekoneˇcna.
I I I
uk´azka projekce dvou rovnobˇeˇzn´ych prostorov´ych pˇr´ımek a jejich pr˚ useˇc´ık je moˇzn´e jen z informac´ı z obr´azku urˇcit poˇcet praˇzc˚ u odspodu obr´azku aˇz ke vlaku? jak urˇcit vzd´alenost vlaku pokud v´ıme, ˇze vzd´alenost praˇzc˚ u je 0,806 m?
Metody Poˇ c´ıtaˇ cov´ eho Vidˇ en´ı (MPV) - 3D poˇ c´ıtaˇ cov´ e vidˇ en´ı
48 / 55
Nevlastn´ı pˇr´ımka, (vanishing line - u ´bˇeˇznice) I nevlastn´ ı pˇr´ımka je pˇr´ımka v obraze tzv. pr˚ useˇcnice dvou (vˇsech) rovnobˇ eˇ zn´ ych prostorov´ych rovin I nebo jako pozice vˇ sech nevlastn´ıch bod˚ u vˇsech pˇr´ımek leˇz´ıc´ı v jedn´e prostorov´e rovinˇe I napˇ r. horizont ... pohled na otevˇren´e moˇre ... rovnobˇeˇzn´e prostorov´e pˇr´ımky bˇeˇz´ıc´ı po hladinˇe se na horizontu prot´ınaj´ı
I
pak tyto pr˚ useˇc´ıky jsou obrazy nevlastn´ıch bod˚ u a horizont obraz nevlastn´ı pˇr´ımky
Metody Poˇ c´ıtaˇ cov´ eho Vidˇ en´ı (MPV) - 3D poˇ c´ıtaˇ cov´ e vidˇ en´ı
49 / 55
Dvojpomˇer (cross ratio) I
I
dvojpomˇer je ˇc´ıslo, kter´e charakterizuje pomˇer d´elek u ´sek˚ u mezi ˇctyˇrmi koline´arn´ımi body (body na jedn´e prostorov´e pˇr´ımce) tyto ˇctyˇri koline´arn´ı prostorov´e body R,S,T a U definuj´ı dvojpomˇer jako:
[RSTU] =
|RT | |SU| |RU| |ST |
(15)
Metody Poˇ c´ıtaˇ cov´ eho Vidˇ en´ı (MPV) - 3D poˇ c´ıtaˇ cov´ e vidˇ en´ı
50 / 55
I
dvojpomˇer je invariantn´ı kolineaci
I
dvojpomˇer je invariantn´ı perspektivn´ı projekci
Metody Poˇ c´ıtaˇ cov´ eho Vidˇ en´ı (MPV) - 3D poˇ c´ıtaˇ cov´ e vidˇ en´ı
51 / 55
1D projektivn´ı souˇradnice I I I I I
mˇejme nˇejak´e ˇctyˇri (tˇri) body n´aleˇz´ıc´ı prostorov´e pˇr´ımce jsou prom´ıtnuty do obrazov´e roviny nˇejak´e kamery (kolineace) pak v t´eto kameˇre plat´ı stejn´y dvojpomˇer, jako v p˚ uvodn´ı pˇr´ımce pˇredpokl´adejme, ˇze posledn´ı (ˇctvrt´y) bod je u ´bˇeˇzn´ık, kter´y v obraze m´a koneˇcnou souˇradnici tento fakt n´am umoˇzn ˇuje mˇeˇrit o obraze bez dalˇs´ıch znalost´ı projektivn´ı transformace
Metody Poˇ c´ıtaˇ cov´ eho Vidˇ en´ı (MPV) - 3D poˇ c´ıtaˇ cov´ e vidˇ en´ı
52 / 55
[P] = [P∞ P0 PI P] =
|P∞ PI | |P0 P| |P0 PI | |P∞ P|
(16)
I
P0 - je poˇc´atek zvolen´eho souˇradn´eho syst´emu [P0 ] = 0
I
P - pracovn´ı bod, jeho souˇradnici v prostoru chceme urˇcit
I
PI - je bod urˇcuj´ıc´ı mˇeˇr´ıtko, m˚ uˇzeme zvolit [PI ] = 1 nebo z velikosti zn´am´eho objektu (um´ıstˇen´y v dan´em smˇeru osy).
I
P∞ - pomocn´y bod (nevlastn´ı bod dan´e prostorov´e pˇr´ımky osy) [P∞ ] = ±∞
Metody Poˇ c´ıtaˇ cov´ eho Vidˇ en´ı (MPV) - 3D poˇ c´ıtaˇ cov´ e vidˇ en´ı
53 / 55
2D projektivn´ı souˇradnice I I
rozˇs´ıˇren´ım m˚ uˇzeme zav´est mˇeˇren´ı ve dvou na sebe kolm´ych os´ach (2D Euklidovsk´y prostor) umoˇzn ˇuje n´am mˇeˇrit pod´el prostorov´e roviny (napˇr. podlaha) za pomoci jej´ı projekce do obrazu bez dalˇs´ı znalost´ı (kalibrace kamery aj.)
Metody Poˇ c´ıtaˇ cov´ eho Vidˇ en´ı (MPV) - 3D poˇ c´ıtaˇ cov´ e vidˇ en´ı
54 / 55
I
souˇradnice (x,y) libovoln´eho bodu t´eto prostorov´e roviny se analogicky urˇc´ı jako: [Px ] = [Px∞ P0 PxI Px ] [Py ] = [Py ∞ P0 PyI Py ]
I
Metody Poˇ c´ıtaˇ cov´ eho Vidˇ en´ı (MPV) - 3D poˇ c´ıtaˇ cov´ e vidˇ en´ı
55 / 55
