CENTER FOR MACHINE PERCEPTION
Matematicky´ model kamery v afinnı´m prostoru CZECH TECHNICAL
(Verze 1.0.1)
UNIVERSITY
Jan Sˇochman, Toma´sˇ Pajdla
[email protected],
[email protected]
CTU–CMP–2002–11
Lze zı´skat na ftp://cmp.felk.cvut.cz/pub/cmp/articles/sochman/Sochman-TR-2002-11.pdf Tato pra´ce byla podporˇena granty GACˇR 102/01/0971 a MSM 212300013
ISSN 1213-2365
VY´ZKUMNA´ ZPRA´VA
6. brˇezna 2003
Research Reports of CMP, Czech Technical University in Prague, No. 11, 2002 Published by Centrum strojove´ho vnı´ma´nı´, Katedra kybernetiky Fakulta elektrotechnicka´ CˇVUT Technicka´ 2, 166 27 Praha 6 fax: (02) 2435 7385, tel: (02) 2435 7637, www: http://cmp.felk.cvut.cz
1 Motivace Meˇjme kameru a snı´mejme s nı´ okolnı´ sveˇt. Vy´stupem takove´ho snı´ma´nı´ je rovinny´ obraz sveˇta. Chteˇli bychom neˇjak vyuzˇ´ıt tohoto obrazu sveˇta k popisu nasnı´mane´ sce´ny. Zna´me vsˇak pouze sourˇadnice bodu˚, u, v , v obraze. Jelikozˇ je vsˇak kamera sama umı´steˇna v prostoru, ktery´ sleduje, a rovina obrazu odpovı´da´ obrazove´ rovineˇ kamery, lze se na obrazove´ body dı´vat jako na body ve sveˇteˇ (prostoru A). Nasˇ´ım cı´lem je najı´t vztah mezi sourˇadnicemi u, v a sourˇadnicemi v prostoru A, neboli najı´t takove´ zobrazenı´ f , ktere´ bodu z prostoru A prˇirˇadı´ sourˇadnice v obraze. Aby bylo mozˇno cˇinit neˇjaka´ dalsˇ´ı prohla´sˇenı´, je nejdrˇ´ıve nutno blı´zˇe specifikovat prostor A. V nasˇem prˇ´ıpadeˇ pouzˇijeme afinnı´ prostor 1 .
2 Afinnı´ prostor Afinnı´ prostor je definova´n jako trojice P, V, ϕ , kde P je mnozˇina bodu˚, V vektorovy´ prostor a ϕ zobrazenı´ ϕ P × P → V. Navı´c musı´ by´t splneˇno na´sledujı´cı´: 1. ∀P, Q ∈ P ∃ ~v ∈ V ϕ P, Q ~v 2. ∀P ∈ P ∀~v ∈ V ∃ Q ∈ P ϕ P, Q ~v 3. ∀P, Q, R ∈ P ϕ P, Q ϕ Q, R − ϕ P, R Prˇedpokla´da´ se, zˇe V ma´ dimenzi n. Pak hovorˇ´ıme o afinnı´m prostoru dimenze n, ktery´ znacˇ´ıme An . Vektorove´mu prostoru V ˇr´ıka´me zameˇrˇenı´ afinnı´ho prostoru An . Prvnı´ axiom da´va´ do souvislosti dva body z P s jednı´m vektorem. Rˇ´ıka´, zˇe ϕ je funkce z mnozˇiny bodu˚ do vektorove´ho prostoru. Take´ je mozˇno se na tvrzenı´ dı´vat tak, zˇe ϕ prˇirˇazuje dvojicim bodu˚, na ktery´ch nemusı´ by´t definova´ny zˇa´dne´ operace, prvek z vektorove´ho prostoru, ve ktere´m uzˇ umı´me scˇ´ıtat a na´sobit. Druhy´ axiom ˇr´ıka´, zˇe ke kazˇde´mu bodu z mnozˇiny P a vektoru z vektorove´ho prostoru V existuje pra´veˇ jeden bod z P. Je tak tedy definova´na funkce ψ P × V → P. 1
Afinnı´ prostor dobrˇe modeluje geometrii beˇzˇne´ho sveˇta kolem na´s. Za´veˇry ucˇineˇne´ na za´kladeˇ axiomu˚ afinnı´ho prostoru souhlası´ se za´veˇry o sveˇteˇ, ke ktery´m dojdeme beˇzˇny´m usuzova´nı´m na za´kladeˇ zdrave´ho rozumu. Oproti uzˇitı´ zdrave´ho rozumu ma´ formulace a ˇresˇenı´ proble´mu˚ v ˇrecˇi afinnı´ho prostoru tu vy´hodu, zˇe zkouma´nı´ je systematicke´ a lze se prˇi neˇm oprˇ´ıt o vy´sledky zna´me´ z teorie linea´rnı´ch prostoru˚.
1
Q
R−Q
Q−P
R R−P
P
Obra´zek 1: Troju´helnı´kova´ rovnost. Trˇetı´mu axiomu se ˇr´ıka´ troju´helnı´kova´ rovnost. Ta je zna´meˇjsˇ´ı ve formeˇ (viz obra´zek 1) Q − P R − Q R − P , (1)
kde P, Q, R jsou opeˇt body. Je vsˇak trˇeba si uveˇdomit, co znamenajı´ operace a −. Za prˇedpokladu, zˇe body P, Q, R jsou body z An , tedy n-dimenziona´lnı´ho afinnı´ho prostoru, prˇedstavuje operace − zobrazenı´ ϕ, ktere´ prˇirˇadı´ usporˇa´dane´ dvojici bodu˚ vektor. Toto zobrazenı´ je neˇkdy oznacˇova´no jako odcˇ´ıta´nı´ bodu˚. Operace je scˇ´ıta´nı´ vektoru˚ ve vektorove´m prostoru V. Na funkci ψ bychom narazili, pokud bychom rovnici (1) prˇepsali do tvaru Q
R − Q − P
Zde funkce ψ odpovı´da´ operaci je opeˇt bod.
R − Q
R−P .
(2)
, jejı´mzˇ parametrem je bod a vektor a vy´sledek
3 Zobrazenı´ ϕ Zı´skat mnozˇinu bodu˚ P a vektorovy´ prostor V lze snadno. Mu˚zˇeme vzı´t naprˇ´ıklad vektorovy´ prostor R . Tı´m vsˇak jesˇteˇ nenı´ urcˇeno zobrazenı´ ϕ, natozˇ jednoznacˇneˇ. Dı´ky vlastnostem afinnı´ho prostoru vsˇak nemusı´me zobrazenı´ ϕ definovat pro vsˇechny body, ale postacˇ´ı na´m k tomu cˇtyrˇi specia´lneˇ vybrane´. Ukazˇme postup jeho konstrukce. Meˇjme A , tedy P, V dimenze 3 a ϕ splnˇujı´cı´ axiomy 1–3, ktere´ nezna´me, ale o ktere´m vı´me, zˇe existuje. Vezmeˇme bod O ∈ P a trˇi linea´rneˇ neza´visle´ vektory ~b , ~b , ~b z V. Podle druhe´ho axiomu platı´ ϕ O, Bi ~bi pro neˇjake´ trˇi body Bi , i . . . . Zı´skali jsme tak dalsˇ´ı trˇi body z P. Ukazˇme, zˇe je ϕ takto definovane´ na cˇtyrˇech dvojicı´ch bodu˚ jednoznacˇneˇ da´no i na zbyly´ch bodech. Nejdrˇ´ıve uka´zˇeme jednoznacˇnost pro dvojice O, X , kde X 2
je libovolny´ bod z P. Z prvnı´ho axiomu vı´me, zˇe pro takovouto dvojici existuje pra´veˇ jeden vektor ~v ∈ V. Jelikozˇ jsou ~b , ~b , ~b linea´rneˇ neza´visle´, tvorˇ´ı ba´zi a vektor ~v lze zapsat jako jejich linea´rnı´ kombinaci. Ma´me tedy ϕ O, X ~v
x ~b x ~b x ~b
x ϕ , B x ϕ , B x ϕ , B ,
cozˇ jednoznacˇneˇ prˇirˇazuje te´to dvojici vektor z V. Naopak z druhe´ho axiomu zı´ska´me pro kazˇdy´ vektor ~v ∈ V bod X takovy´, zˇe ϕ O, X ~v . Zobrazenı´ ϕ je tedy pro dvojici O, X , kde X je libovolne´, urcˇeno jednoznacˇneˇ. Vektoru ~v splnˇujı´cı´mu rovnost ~v ϕ O, X pro danny´ bod X ˇr´ıka´me zameˇrˇenı´ bodu X. Pro libovolne´ dva body A, B ∈ P je pak zobrazenı´ ϕ A, B definova´no jednoznacˇneˇ z troju´helnı´kove´ rovnosti jako ϕ A, B ϕ O, B − ϕ O, A . Takove´to zobrazenı´ existuje pro vsˇechny dvojice, nebot’ vy´razy na prave´ straneˇ jsou definova´ny pro vsˇechny body a je i jednoznacˇne´ dı´ky jednoznacˇnosti vy´razu˚ na prave´ straneˇ.
4 Sourˇadna´ soustava kamery Vrat’me se k nasˇ´ı u´loze nalezenı´ vztahu mezi sourˇadnou soustavou obrazu a souˇradnou soustavou okolnı´ho sveˇta. Zatı´m jsme specifikovali okolnı´ sveˇt jako afinnı´ prostor A . Dalsˇ´ım krokem je definice sourˇadne´ soustavy obrazu vzhledem ke kamerˇe. Pokud se na´m toto podarˇ´ı, prˇevedeme na´sˇ proble´m na nalezenı´ zobrazenı´ jedne´ ba´ze zameˇˇrenı´ prostoru A na druhou. Kamera je totizˇ umı´steˇna v prostoru A a tak je tedy ba´ze spojena´ se sourˇadnou soustavou kamery i ba´zı´ zameˇˇrenı´ prostoru A . Sourˇadnou soustavu kamery lze definovat mnoha zpu˚soby, takzˇe si uka´zˇeme jednu z mozˇny´ch a uka´zˇeme si, procˇ je pra´veˇ tato vy´hodna´. Na obra´zku 2 je naznacˇena situace v kamerˇe2 . C je opticky´ strˇed kamery a π obrazova´ rovina. V rovineˇ π jizˇ ma´me sourˇadnou soustavu o, b , b , ktere´ odpovı´dajı´ ba´zove´ vektory~ı, ~. Tato sourˇadna´ soustava odpovı´da´ sourˇadne´ soustaveˇ obra´zku. Zde je trˇeba pozastavit se nad pojmem „rovina“. Takovy´to pojem v nasˇem afinnı´m prostoru zatı´m nema´me. Je trˇeba vyvarovat se toho, zˇe si afinnı´ prostor A , ve ktere´m se pohybujeme, prˇedstavujeme jako R . V R jizˇ vı´me, co je rovina. Je to podprostor dimenze 2. Intuitivneˇ tak ztotozˇnˇujeme rovinu v R s rovinou v A , cozˇ nenı´ spra´vneˇ. 2
Prˇedpokla´da´me dı´rkovy´ model kamery.
3
X
π
PSfrag replacements
u
u, v b
C b
~ı ~
o
Obra´zek 2: Promı´tnutı´ bodu do obrazu. Rovina v afinnı´m prostoru A P, V, ϕ je opeˇt podprostor dimenze 2, ovsˇem afinnı´ podprostor. Tedy A P 0 , V 0 , ϕ0 , kde V 0 je podprostor V 0 dimenze 2, ϕ0 je „zu´zˇenı´“ ϕ na V 0 a P 0 jsou body z P, na ktery´ch je definova´no ϕ0 . Je tedy nutne´ vzı´t v potaz zmensˇenı´ dimenze nejenom u vektorove´ho prostoru V, ale take´ pro zobrazenı´ ϕ a mnozˇinu bodu˚ P. Jak prˇesneˇ je definova´no ono „zu´zˇenı´“ ϕ a vy´beˇr bodu˚ z P je videˇt na na´sledujı´cı´ forma´lnı´ definici roviny v afinnı´m prostoru. Definice: Rovinou v afinnı´m prostoru A P, V, ϕ rozumı´me takovy´ afinnı´ prostor A P 0 , V 0 , ϕ0 , kde V 0 je podprostor V dimenze 2 a pro mnozˇinu bodu˚ P 0 platı´ 1. pro kazˇdy´ vektor ~v ∈ V 0 a vsˇechny body P, Q ∈ P, pro ktere´ platı´ ϕ P, Q ~v , platı´ P, Q ∈ P 0 , 2. pro kazˇdou dvojici bodu˚ P, Q ∈ P 0 platı´ ϕ P, Q ∈ V 0 . Zobrazenı´ ϕ0 je definova´no stejneˇ jako ϕ ovsˇem pouze na P 0 a V 0 . Pokud tedy ma´me bod C, ktery´ nelezˇ´ı v rovineˇ π, znamena´ to, zˇe pro libovolny´ bod X ∈ π platı´ ϕ C, X 6∈ V 0 . Dosta´va´me tak vektor, ktery´ je linea´rneˇ neza´visly´ na vektorech z roviny π. K nadefinova´nı´ sourˇadne´ soustavy kamery potrˇebujeme stejneˇ jako v prˇ´ıpadeˇ hleda´nı´ sourˇadne´ soustavy A trˇi linea´rneˇ neza´visle´ vektory a jeden bod. Navı´c chceme, aby tyto byly sva´za´ny s kamerou. Asi nejjednodusˇsˇ´ı volbou je pouzˇ´ıt jako ba´zi vektory ~ı, ~, ϕ o, C (vı´me, zˇe jsou linea´rneˇ neza´visle´) a jako pocˇa´tek bod o. Takova´to volba je korektnı´ a ma´ tu vy´hodu, zˇe body z obrazove´ roviny v neˇm budou mı´t sourˇadnice u, v, . Dostali 4
p X π Y
PSfrag replacements u
~ı C
~ o
Obra´zek 3: Linea´rnı´ za´vislost vektoru˚ prˇi nevhodneˇ zvolene´ sourˇadne´ soustaveˇ kamery. jsme tedy snadny´ prˇevod ze sourˇadne´ soustavy obrazu do sourˇadne´ soustavy kamery. Takto zvolena´ sourˇadna´ soustava vsˇak ma´ i jeden nedostatek (viz obra´zek 3). Pozdeˇji budeme pro zformulova´nı´ rovnice (3) pozˇadovat, aby vektory zameˇˇrujı´cı´ vsˇechny body na prˇ´ımce p (naprˇ´ıklad X, Y ) byly linea´rneˇ za´visle´ na zameˇˇrenı´ bodu u, ktere´ reprezentuje projekci bodu˚ na prˇ´ımce p do roviny π. V na´mi navrzˇene´ sourˇadne´ soustaveˇ jsou vsˇak vektory ϕ o, X a ϕ o, Y linea´rneˇ neza´visle´ na zameˇˇrenı´ bodu u. Pokusı´me se sourˇadnou soustavu zvolit vhodneˇji. Vezmeme jako pocˇa´tek bod C a trˇi neza´visle´ vektory~ı, ~, ϕ C, o (obra´zek 4). Ty na´m opeˇt definujı´ sourˇadnou soustavu kamery, ve ktere´ ma´me jednoduchy´ prˇevod z obrazovy´ch sourˇadnic do sourˇadne´ soustavy kamery. Bod u, v z obrazu bude mı´t sourˇadnice u, v, . Navı´c jsme zı´skali linea´rnı´ za´vislost vektoru˚ ϕ C, X a ϕ C, Y na ϕ C, u . Nalezli jsme tedy vhodnou sourˇadnou soustavu kamery, do ktere´ ma´me snadny´ prˇevod ze sourˇadne´ soustavy obrazu a navı´c jsou v nı´ zameˇˇrenı´ vsˇech bodu˚ na jedne´ prˇ´ımce (paprsku) procha´zejı´cı´ strˇedem promı´ta´nı´ linea´rneˇ za´visle´ na zameˇˇrenı´ bodu reprezentujı´cı´m projekci teˇchto bodu˚. Mu˚zˇeme tedy pokrocˇit k definici matematicke´ho modelu kamery.
5 Matematicky´ model kamery Nynı´ jizˇ ma´me vsˇe nachysta´no k tomu, abychom doka´zali vyja´drˇit na´sˇ proble´m forma´lneˇ. Oznacˇme sourˇadnice vzhledem k obecne´ sourˇadne´ soustaveˇ afinnı´ho 5
p X π Y
PSfrag replacements u
~ı
~ı ~
~
o
C
Obra´zek 4: Vhodneˇ zvolena´ sourˇadna´ soustava kamery. prostoru A indexem β a sourˇadnice vzhledem k sourˇadne´ soustaveˇ kamery indexem β 0 . Jak jizˇ bylo ˇrecˇeno, body na jednom paprsku vycha´zejı´cı´m z opticke´ho strˇedu kamery by se meˇly promı´tnout do stejne´ho bodu v obraze. Pro kazˇdy´ bod X z prostoru A tedy musı´ platit u α v ϕβ 0 C, X . (3)
Neboli vektor ϕβ 0 C, X je α-na´sobkem vektoru u, v, , ktery´ v sourˇadne´ soustaveˇ kamery odpovı´da´ bodu u – promı´tnuty´ bod X. Tedy ϕ β 0 C, u u, v, . Obvykle vsˇak ϕβ 0 C, X nezna´me. Pokud ma´me zna´my´ objekt, mu˚zˇeme vsˇak nale´zt ϕβ C, X tak, zˇe si v A zvolı´me libovolnou sourˇadnou soustavu. Potrˇebujeme tedy navı´c najı´t zobrazenı´ f takove´, zˇe ϕβ 0 C, X f ϕβ C, X . Jelikozˇ se nejedna´ o nic jine´ho, nezˇ o prˇechod z jedne´ ba´ze do druhe´, je mozˇno zobrazenı´ f vyja´drˇit maticı´, takzˇe lze ekvivalentneˇ napsat ϕβ 0 C, X !
Aϕβ C, X
kde A je odpovı´dajı´cı´ matice. S vyuzˇitı´m (4) dosta´va´me prˇepis vztahu (3) u α v Aϕβ C, X A X − C .
6
(4)
(5)
Tato rovnice je za´kladnı´m vztahem mezi kamerou (reprezentovanou maticı´ A), bodem v prostoru X a bodem v obraze u, v . Cˇasteˇji se s touto rovnicı´ setka´me ve tvaru X αu P ,
kde P ∈ R ×" odpovı´da´ matici A a nazy´va´ se projekcˇnı´ matice. Takto vybudovany´ model kamery je sice spra´vny´, ale jesˇteˇ ne zcela u´plny´. Zatı´m nevı´me, co deˇlat z body v rovineˇ rovnobeˇzˇne´ s π a procha´zejı´cı´ bodem C. Kam se promı´tnou? Dalsˇ´ı zvla´sˇtnı´ prˇ´ıpad nastane, kdyzˇ budeme zobrazovat prˇ´ımku kolmou na rovinu π neprocha´zejı´cı´ strˇedem promı´ta´nı´. Pokud bychom po nı´ sˇli porˇa´d da´l a da´l, azˇ do nekonecˇna, promı´tne se na´m toto nekonecˇno do bodu v obraze. Jak se ma´me chovat k takovy´mto bodu˚m? Je tedy nutno ucˇinit dalsˇ´ı krok a prˇejı´t z afinnı´ho prostoru do prostoru projektivnı´ho.
7
