Geometria Computacional (I) Josep Blat

Universitat Pompeu Fabra

´Index 1 Geometria af´ı i m` etrica 1.1 Espai af´ı i subespais . . . . . . . . . . . . . . . . . . . 1.2 Sistemes de refer` encia afins . . . . . . . . . . . . . . . 1.3 Canvi de sistema de refer` encia . . . . . . . . . . . . . 1.4 Operativa amb matrius ampliades . . . . . . . . . . . 1.5 Orientaci´ o de l’espai . . . . . . . . . . . . . . . . . . . 1.6 Producte escalar i dist` ancia . . . . . . . . . . . . . . . 1.7 Ortogonalitat, projeccions i m` etode de Gram-Schmidt 1.8 Rotacions i matrius ortogonals . . . . . . . . . . . . . 1.9 Algunes aplicacions: projeccions i dist` ancies en 3D . . 1.10 Producte vectorial en el espai 3D . . . . . . . . . . . . 1.11 Objectes geom` etrics b` asics al pla . . . . . . . . . . . . 1.12 Objectes geom` etrics b` asics a l’espai . . . . . . . . . . . 1.13 Problemes . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

2 2 3 4 5 5 6 7 8 8 9 10 10 11

2 Transformacions afins i canvis de variables 2.1 Transformacions afins en general . . . . . . . . . 2.2 Transformacions afins en 2D . . . . . . . . . . . . 2.3 Coordenades polars . . . . . . . . . . . . . . . . . 2.4 Transformacions afins en 3D . . . . . . . . . . . . 2.5 Coordenades cil´ındriques i coordenades esf` eriques 2.6 Problemes . . . . . . . . . . . . . . . . . . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

12 12 13 13 14 14 15

3 Corbes i superf´ıcies 3.1 Corbes param` etriques i vectors tangents . . . . . . . . . 3.2 Parametritzacions equivalents de les corbes, multiplicitat 3.3 Longitud d’una corba, parametritzaci´ o can` onica . . . . . 3.4 Curvatura i torsi´ o . . . . . . . . . . . . . . . . . . . . . 3.5 Algunes corbes importants . . . . . . . . . . . . . . . . . 3.6 Superf´ıcies en 3D i plans tangents . . . . . . . . . . . . . 3.7 Algunes superf´ıcies importants . . . . . . . . . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

16 16 17 17 18 19 20 20

. . . . . . . . . . . . . . . de la . . . . . . . . . . . .

. . . . .

22 22 23 24 24 25

. . . .

25 26 27 27

. . . . . .

. . . . . .

. . . . . .

4 Projeccions, geometria i calibratge de c` ameres 4.1 Introducci´ o . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.2 La projecci´ o perspectiva en el sistema de refer` encia c` amera . . 4.3 Transformaci´ o c` amera-imatge . . . . . . . . . . . . . . . . . . . 4.4 Combinant projecci´ o i transformaci´ o: els par` ametres intr´ınsecs 4.5 La transformaci´ o a sistema objecte i els par` ametres extr´ınsecs . 4.6 La matriu de projecci´ o perspectiva; la obtenci´ o dels par` ametres matriu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.7 Calibratge . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.8 Reconstrucci´ o 3D utilitzant estereoscopia . . . . . . . . . . . . 4.9 Perspectiva c` onica i perspectiva cil´ındrica . . . . . . . . . . . .

1

. . . . . . . . . . . . . . . . . . . . . . . . . a partir . . . . . . . . . . . . . . . . . . . .

Cap´ıtol 1

Geometria af´ı i m` etrica 1.1

Espai af´ı i subespais

Recordem que l’espai   n  IRn = x =  

x1 x2 .. .

  o   : x1 , x2 , . . . , xn ∈ IR . 

xn amb les dues operacions suma de vectors i producte d’un escalar per un vector ´es un espai vectorial i als seus elements els hi direm vectors. ´ 1.1 Definicio Un espai af´ı real de dimensi´ o n ´es el parell (IRn , E) on E ´es un conjunt de punts i est` a definida una operaci´ o suma de punt P ∈ E i vector v ∈ IRn com un vector P + v que iverifica les propietats: 1. (P + v) + w = P + (v + w) (regla del paral.lelogram) 2. Donats dos punts P i Q hi ha un u ´nic vector v tal que P + v = Q, el que tamb´e es denota com v = Q − P = P Q 2 La recta que passa per un punt P i t´e com a direcci´o la d’un vector v es defineix com el conjunt de punts X de la forma X = P + λv

∀λ ∈ IR

Si u ´nicament considerem els λ ≥ 0 tindrem una semirecta d’origen P . Si tenim dos punts, P, Q, el segment d’extrems P, Q ´es el conjunt de punts X de la forma X = P + (1 − λ)P Q

∀λ ∈ [0, 1]

De forma semblant es defineixen els subespais afins, que s´on els punts suma d’un punt donat i un subespai vectorial. Si el subespai vectorial ´es un hiperpl`a, tindrem un hiperpl` a af´ı. I tamb´e podem definir tamb´e semiespais ... 2

` CAP´ITOL 1. GEOMETRIA AF´I I METRICA

3

´ convenient comen¸car per revisar les operacions matricials Problemes: Es (p.e., amb els exercicis de l’apartat 2.5 dels apunts de Geometria per a Sistemes Multim`edia, de V. Sacristan, n´ umeros 13-20).

1.2

Sistemes de refer` encia afins

Recordem que una base d’un espai vectorial ´es un conjunt de vectors v1 , . . . , vn que 1. Generen l’espai vectorial. 2. S´ on linialment independents. i que llavors es verifica que per cada v existeixen uns u ´nics escalars c1 , . . . , cn que compleixen v = c1 v1 + · · · + cn vn : De forma semblant, ´ 1.2 Definicio Un sistema de refer` encia af´ı est`a constitu¨ıt per 1. Un punt O que es denomina origen de coordenades 2. Una base de l’espai vectorial, v1 , . . . , vn ; les rectes que passen per O amb les direccions d’aquests vectors s´on els eixos de coordenades. 2 Donat un punt qualsevol X, llavors les components del vector OX respecte a la base es denominen coordenades afins del punt. Quan est`a clarament definit un sistema de refer`encia es poden identificar punts i vectors: el punt X s’identifica amb el vector OX. Exemple 1: Escriure les equacions vectorial, param`etriques, impl´ıcites i expl´ıcites d’una recta en 2D. ♠ Exemple 2: Escriure les equacions vectorial, param`etriques, impl´ıcites i expl´ıcites d’una recta en 3D. ♠ Exemple 3: Escriure les equacions vectorial, param`etriques, impl´ıcites i expl´ıcites d’un pla en 3D. ♠ En dimensi´ o n, hi ha una u ´nica equaci´o impl´ıcita d’un hiperpla. Exemple 4: Demostreu que les diagonals d’un paral.lelogram s’intersequen m´ utuament en els punts mitjans. ♠ Exemple 5: Demostreu que les tres mitjanes d’un triangle s’intersequen en un punt, que es diu baricentre, i determinar les coordenades d’aquest punt. ♠ Problemes: Els exercicis de l’apartat 3.7 dels mateixos apunts de Geometria per a Sistemes Multim`edia s´ on elementals d’espais i subespais afins.

` CAP´ITOL 1. GEOMETRIA AF´I I METRICA

1.3

4

Canvi de sistema de refer` encia

Recordem que si {e1 , . . . , en } i {v1 , . . . , vn } s´on dues bases de IRn , ej =

n X

aij vi

i=1

i si (α1 , . . . , αn ) i (β1 , . . . , βn ) s´on les components d’un vector qualsevol v ∈ IRn respecte de cada base, llavors es verifica que      α1 a11 . . . a1n β1  ..   .. ..   ..  .  . = . .  .  βn

an1

...

ann

αn

Ho podem representar de forma m´es concisa com β = Aα, i direm que A ´es la matriu de canvi de base. De forma semblant, ens interessa estudiar el canvi de sistema de refer`encia, que pot ser per: 1. canvi d’origen de coordenades 2. canvi d’eixos de coordenades 3. canvi de les dues coses Suposem el primer cas, que tenim dos sistemes de refer`encia S = (O, {e1 , . . . , en }) i S 0 = (O0 , {e1 , . . . , en }) i que les coordenades d’O0 respecte a S s´on (w1 , . . . , wn ) - que s´ on les components del vector OO0 - . Ens interessa la relaci´o entre les coordenades d’un punt qualsevol P respecte als dos sistemes. Recordem que seran les components del vector OP , que denotarem per X = (x1 , . . . , xn ) i les de O0 P , X 0 = (x01 , . . . , x0n ). Com O0 P = OP − OO0 i la base ´es la mateixa, podem traduir-ho en termes de components: x0i = xi − wi

i = 1, . . . , n

X0 = X − W Si u ´nicament canviem els eixos de coordenades, ´es a dir, tenim dos sistemes de refer`encia S = (O, {e1 , . . . , en }) i S 0 = (O, {v1 , . . . , vn }), es tracta simplement d’un canvi de base, i si utilitzem la terminologia anterior, el que tindrem ´es X 0 = AX Si el canvi ´es tant d’origen com d’eixos, podem combinar els dos apartats anteriors i queda: X 0 = A(X − W ). Utilitzant la matriu inversa A−1 podem obtenir les f´ormules de les transformacions de X 0 a X. Exemple 6: Utilitzant canvi de sistema de refer`encia, obtenir l’equaci´ o de la circumfer`encia centrada en el punt (3, 7) i radi 2. ♠

` CAP´ITOL 1. GEOMETRIA AF´I I METRICA

5

Exemple 7: Obtenir les equacions del canvi de sistema de refer`encia en IR2 ♠ quan es produeix una rotaci´ o d’angle π6 Exemple 8: Utilitzant canvi de sistema de refer`encia, obtenir l’equaci´ o de l’el.lipse centrada en el punt (2, 3), de semieixos 3 i 2 i d’eixos rotats π6 . ♠ Problemes: Els exercicis 40-46 dels apunts de Geometria per a Sistemes Multim`edia permeten revisar els conceptes de canvis de sistema de refer`encia.

1.4

Operativa amb matrius ampliades

Recordem que un canvi de base ´es equivalent a una aplicaci´o linial i, m´es concretament a un isomorfisme (transformaci´o linial bijectiva de l’espai vectorial en ell mateix); i que per a concatenar dos canvis de base, basta multiplicar (en l’ordre correcte) les dues matrius respectives. De forma semblant, un canvi de sistema de refer`encia ´es equivalent a un isomorfisme af´ı; per a facilitar la operativa (per exemple, en infografia), es pot representar de forma compacta el canvi de sistema de refer`encia mitjan¸cant una matriu ampliada; la concatenaci´o de dos canvis de refer`encia ´es el producte d’aquestes dues matrius (encara que la matriu ampliada no representa la d’una aplicaci´ o linial). Exemple 9: Determinar la matriu ampliada corresponent a la concatenaci´ o de dos canvis de sistema de refer`encia a partir de les matrius ampliades respectives. ♠ Exemple 10: Determinar la matriu ampliada corresponent a la inversi´ o d’un canvi de sistema de refer`encia, a partir de la matriu ampliada d’aquest. ♠

1.5

Orientaci´ o de l’espai

Suposem que considerem, com abans, dues bases de IRn , {e1 , . . . , en } i {v1 , . . . , vn }, i que A ´es la matriu de canvi de base. Per al seg¨ uent concepte ´es important recordar que hem de mantenir l’ordre dels vectors. ´ 1.3 Definicio Direm que les dues bases tenen la mateixa orientaci´ o si det(A) > 0 2 Es pot mostrar que aquesta ´es una relaci´o bin`aria d’equival`encia, i que les bases queden partides en dues classes. Si a una d’aquestes classes la definim com a orientaci´ o positiva, direm que hem definit una orientaci´ o de l’espai. Usualment la orientaci´ o positiva ´es l’antihor`aria en el cas de IR2 , i la que d´ ona la regla del tirataps en el cas de IR3 (gr`aficament, l’eix Z positiu est`a definit pel sentit del moviment del tirataps quan girem aquest de l’eix X cap a l’Y pel cam´ı m´es curt). La orientaci´ o ´es conservada pels isomorfismes tals que el determinant de la seva matriu ´es positiu.

` CAP´ITOL 1. GEOMETRIA AF´I I METRICA

1.6

6

Producte escalar i dist` ancia

Recordem la definici´ o de producte escalar: ´ 1.4 Definicio Siguin x = (xi )n , y = (yi )n dos vectors d’IRn o Cn . El producte escalar euclidi`a d’x i y ´es hx, yi = x1 y1 + x2 y2 + · · · + xn yn si x, y ∈ IRn o hx, yi = x1 y¯1 + x2 y¯2 + · · · + xn y¯n si x, y ∈ Cn .

2

El producte escalar t´e les propietats seg¨ uents, si x1 , x2 , x, y ∈ IRn o Cn i λ ∈ IR o C: 1. hx1 + x2 , yi = hx1 , yi + hx2 , yi i hλx, yi = λhx, yi. 2. hx, yi = hy, xi si x, y ∈ IRn i hx, yi = hy,¯xi si x, y ∈ Cn . 3. hx, xi ≥ 0. 4. Si hx, xi = 0 llavors x = (0), ja que hx, xi = x21 + · · · + x2n . 5. (desigualtat de Cauchy-Schwartz) Si x, y ∈ IRn , llavors |hx, yi| ≤ kxk kyk. Les propietats 3 i 4 ens permeten definir la longitud d’un vector x ∈ IRn : p kxk = hx, xi, de manera que kxk2 = x21 +· · ·+x2n . Tamb´e es coneix com a norma euclidiana del vector x. Exemple 11: Mostrar la llei del paral.lelogram: la suma dels quadrats de les longituds de les diagonals ´es igual al doble de la suma dels quadrats de les longituds dels costats. ♠ La longitud ens permet definir la dist` ancia entre dos punts P i Q com la norma del vector P Q: d(P, Q) = kP Qk La dist` ancia t´e les propietats:: 1. d(P, Q) = d(Q, P ). 2. d(P, Q) = 0 ↔ P = Q. 3. (desigualtat triangular) d(P, Q) ≤ d(P, R) + d(R, Q)

` CAP´ITOL 1. GEOMETRIA AF´I I METRICA

7

La desigualtat de Cauchy-Schwartz permet definir l’ angle entre dos vectors x, y ∈ IRn − {0} com l’angle θ ∈ [0, π] que compleix cos θ =

hx, yi . kxk kyk

(1.1)

ja que el membre de la dreta pren valors entre −1 i 1. En el cas de IR2 , si adoptem una orientaci´ o, podem definir la noci´o d’angle orientat.

1.7

Ortogonalitat, projeccions i m` etode de GramSchmidt

´ 1.5 Definicio Dos vectors x, y ∈ IRn o Cn s´ on ortogonals (o perpendiculars) si hx, yi = 0. 2 ´ 1.6 Definicio Siguin a, b ∈ IRn o Cn . Definim la projecci´ o de b sobre a com δ=

ha, bi a. ha, ai 2

Recordem que una base v1 , . . . , vn d’IRn o Cn ´es ortogonal si hvi , vj i = 0 per tots i, j diferents (´es a dir, els vectors de la base s´on ortogonals dos a dos). Si, a m´es, els vectors s´ on unitaris (hvi , vi i = 1 per tot i) llavors la base ´es ortonormal. Si la base del sistema de refer`encia af´ı ´es ortonormal, direm que ´es un sistema de coordenades cartesianes. El m` etode de Gram-Schmidt permet obtenir una base ortonormal a partir d’una base qualsevol. Recordem-ho. Sigui v1 , . . . , vk un sistema de vectors linealment independents d’IRn . Es construeix un sistema de vectors que generen el mateix subespai per inducci´o. Primer de tot definim w1 =

v1 kv1 k

i llavors amb w20 = v2 − hv2 , w1 iw1 , w2 =

w20 ; kw20 k

en general, si ja hem constru¨ıt l vectors w1 , . . . , wl (l < k) que formen un sistema ortonormal, podem continuar fent: 0 wl+1 = vl+1 − Pw1 (vl+1 ) − · · · − Pwl (vl+1 ) = = vl+1 − hvl+1 , w1 iw1 − · · · − hvl+1 , wl iwl

i, finalment, wl+1 =

0 wl+1 . 0 kwl+1 k

` CAP´ITOL 1. GEOMETRIA AF´I I METRICA

1.8

8

Rotacions i matrius ortogonals

´ 1.7 Definicio ´ a dir, Q : V → V Una rotaci´ o ´es una aplicaci´ o lineal que conserva longituds. Es ´es una rotaci´ o si ´es aplicaci´ o lineal i kQxk = kxk per tot x ∈ V . 2 El seg¨ uent teorema ens d´ ona propietats importants de les rotacions: Teorema 1.1 Sigui Q : V → V una aplicaci´ o. S´on equivalents: 1. Q ´es una rotaci´ o. 2. Per tots x, y ∈ V , hQx, Qyi = hx, yi. 3. Qt Q = QQt = I (si V = IRn ) o Q¯t Q = QQ¯t = I (si V = Cn ). 2 La seg¨ uent definici´ o i proposici´o ens s´on molt u ´tils operativament. ´ 1.8 Definicio Una matriu Q ´es ortogonal si QQt = I (´es a dir, si Q−1 = Qt ). En tal cas, det Q = ±1. 2 ´ 1.1 Proposicio Siguin v1 , . . . , vn els vectors columna d’una matriu quadrada Q d’ordre n. Llavors, Q ´es ortogonal si i nom´es si v1 , . . . , vn s´on una base ortonormal d’IRn . 2

1.9

Algunes aplicacions: projeccions i dist` ancies en 3D

Recordem que l’equaci´ o impl´ıcita d’un pla en l’espai tridimensional ´es ax + by + cz − d = 0 i es pot transformar en a(x − x0 ) + b(y − y0 ) + c(z − z0 ) = 0; aqu´ı podem observar 1. que el punt A = (x0 , y0 , z0 ) ´es un punt del pla, 2. que si denotem per P = (x, y, z) un punt qualsevol del pla, el vector AP pertany al subesbai director del pla, 3. que el vector (a, b, c) ´es ortogonal al pla. Definim l’angle entre dos plans com el que formen les normals respectives. Exemple 12: Donar l’equaci´ o param`etrica de la recta que passa per un punt i ´es perpendicular a un pla prenent com a vector de direcci´ o de la recta el normal al pla. Obtenir a continuaci´ o la projecci´ o ortogonal d’un punt sobre un pla. Utilitzar tant coordenades com f´ ormules vectorials i comparar. ♠ Exemple 13: Calcular la projecci´ o d’un punt sobre una recta, utilitzant tant coordenades com f´ ormules vectorials. ♠

` CAP´ITOL 1. GEOMETRIA AF´I I METRICA

Exemple 14: recta.

9

Calcular les dist` ancies d’un punt a un pla, i d’un punt a una ♠

Exemple 15: Escriure les equacions de la circumfer`encia en 2D. Calcular les interseccions d’una circumfer`encia i una recta utilitzant notaci´ o vectorial d’aquesta. ♠ Exemple 16: Escriure les equacions de la superf´ıcie esf`erica i de la cil´ındrica en 3D. ♠

1.10

Producte vectorial en el espai 3D

Donada una base ortonormal orientada positivament en IR3 es pot mostrar que la definici´ o seg¨ uent ´es correcta: ´ 1.9 Definicio Donats dos vectors u, v ∈ IR3 el producte vectorial u ∧ v respecte a aquesta base ´es el vector u ´nic que verifica la identitat det (u, v, w) = h(u ∧ v), wi

∀v ∈ IR3 2

A partir d’aquesta definici´ o es pot mostrar la f´ormula de les coordenades del producte vectorial coneguda i les propietats seg¨ uents: Si u, v, u1 , u2 , v1 , v2 ∈ IR3 i λ ∈ R 1. Anticommutativitat: u ∧ v = −v ∧ u i en particular u ∧ u = 0, 2. (λu) ∧ v = λ(u ∧ v) i u ∧ (λv) = λ(u ∧ v), 3. (u1 + u2 ) ∧ v = u1 ∧ v + u2 ∧ v i u ∧ (v1 + v2 ) = u ∧ v1 + u ∧ v2 , 4. u ∧ v = 0 ↔ u, v s´ on linialment dependents, 5. u ∧ v ´es ortogonal a u i a v, 6. Si u, v s´ on linialment independents, {u, v, u ∧ v} ´es una base d’orientaci´o positiva, 7. Si θ ´es l’angle dels vectors u i v, llavors ku ∧ vk = kukkvk sin θ. Com exemple d’aplicaci´ o del producte vectorial tenim: Exemple 17: Calcular l’equaci´ o del pla que passa per tres punts donats.

♠

` CAP´ITOL 1. GEOMETRIA AF´I I METRICA

1.11

10

Objectes geom` etrics b` asics al pla

Recordem que una recta queda definida per un punt i una direcci´o (un vector director); alternativament, dos punts tamb´e la determinen. Si el punt ´es P i el vector v, la recta ´es el conjunt de punts: {X = P + λv : λ ∈ IR} Si considerem u ´nicament els λ ≥ 0, tenim la semirecta d’origen P i sentit definit per v. Dos punts, anomenats extrems, defineixen un segment, que ´es una porci´ o de recta delimitada per aquests. Una recta separa dues regions del pla, anomenades semiplans: dos punts no pertanyents a la recta s´ on al mateix semipl`a si es poden unir mitjan¸cant una l´ınia cont´ınua que no talli la recta. Una poligonal queda definida per una successi´o finita de punts (v` ertexs), {P0 , . . . , Pn }, i est` a formada pels segments consecutius ordenats Pi−1 Pi , i = 1, . . . , n, que es denominen costats o arestes. Un pol´ıgon ´es una poligonal tancada, ´es a dir: P0 = Pn ; direm que ´es simple si es compleix la condici´o que nom´es els costats consecutius comparteixen punts en com´ u, concretament el v`ertex com´ u. Direm que ´es convex si ´es la intersecci´o afitada d’un conjunt finit de semiplans, el que ´es equivalent a dir que ´es un pol´ıgon simple tal que els angles interiors que formen els costats consecutius s´on convexos (aguts). La circumfer` encia de centre C i radi r > 0 ´es el conjunt dels punts del pla situats a dist` ancia r del punt C. El cercle est`a format pels punts a dist`ancia menor o igual que r de C. Recordem tamb´e l’arc de circumfer`encia, el sector circular i la corona circular.

1.12

Objectes geom` etrics b` asics a l’espai

Recordem que un pla queda definit per un punt i dos vectors directors independents; tres punts no colineals tamb´e ho determinen. Si el punt ´es P i els vectors v, w, el pla ´es el conjunt de punts: {X = P + λv + µw : λ, µ ∈ IR} Un pla separa dues regions de l’espai, anomenades semiespais: dos punts no pertanyents al pla s´ on al mateix semiespai si es poden unir mitjan¸cant una l´ınia cont´ınua que no talli el pla. Un pol´ıedre es un conjunt finit de pol´ıgons plans anomenats cares, de forma que: 1. cada dues cares o b´e s´ on disjuntes; o quan s´on adjacents o incidents tenen un u ´nic v`ertex en com´ u o tenen dos v`ertexs en com´ u i per tant l’aresta que els uneix tamb´e 2. no hi ha cares o arestes ”penjants” 3. la superf´ıcie ´es connexa, tancada i afitada.

` CAP´ITOL 1. GEOMETRIA AF´I I METRICA

11

De vegades es d´ ona una definici´o m´es restrictiva, que no considera la possibilitat de forats, de forma que cada aresta d’una cara pertany exactament a una altra cara (les dues cares s’anomenen adjacents ) i el pol´ıedre ´es topol`ogicament equivalent a una esfera. Un pol´ıedre convex ´es la intersecci´o afitada d’un conjunt finit de semiespais. Un pol´ıedre regular ´es un pol´ıedre convex que t´e totes les cares regulars i iguals, i tots els v`ertexs de mateix grau. Nom´es hi ha cinc pol´ıedres regulars: tetr` aedre, cub (o hex`aedre), oct`aedre, dodec`aedre i icos`aedre.

1.13

Problemes

1. Exercicis 26-39 dels apunts de Geometria per a Sistemes Multim`edia. 2. Els exercicis del cap´ıtol 1 dels Problemes de Geometria Computacional permeten revisar tot el cap´ıtol.

Cap´ıtol 2

Transformacions afins i canvis de variables 2.1

Transformacions afins en general

´ 2.1 Definicio Una transformaci´ o af´ı ´es una aplicaci´o de l’espai af´ı en ell mateix f : E → E, de forma que l’aplicaci´ o associada, ϕ sobre l’espai vectorial dels vectors definits per parells de punts, ´es una aplicaci´o linial. 2 Operativament, aix` o significa que es pot expressar una transformaci´o af´ı per f (X) = AX + B, i respecte a un sistema de coordenades com:        x1 a11 a12 . . . a1n x1 b1  x2   a21 a22 . . . a2n   x2   b2         f . = . .. ..   ..  +  ..  ..  ..   ..     . . . . .  xn

am1

am2

...

amn

xn

bn

La imatge per una transformaci´o af´ı d’un subespai af´ı ´es un subespai af´ı, el que significa que es mantenen les propietats de depend`encia lineal i paral.lelisme. Vegem ara les transformacions afins principals. 1. Una translaci´ o ´es la que t´e com a matriu associada la identitat. 2. Si per a una base e1 , . . . , en , es verifica que ϕ(ei ) = λi (ei ) direm que tenim un canvi d’escala, i si tots els λi s´on iguals (a λ), direm que ´es una homot` ecia de ra´ o vectorial λ. 3. Si es conserva la norma dels vectors, llavors direm que tenim una isometria, i, en funci´ o del que hem vist anteriorment, la matriu A d’una isometria ser` a ortogonal. Remarquem que, el mateix que la composici´o de funcions no ´es una operaci´o commutativa, la concatenaci´ o de transformacions afins no ´es commutativa (en general, encara que hi ha excepcions)

12

CAP´ITOL 2. TRANSFORMACIONS AFINS I CANVIS DE VARIABLES 13

2.2

Transformacions afins en 2D

Les principals transformacions afins en 2D s´on: 1. Translaci´ o. Com hem dit abans, una translaci´o t´e com a matriu associada la identitat; per tant tenim que f (X) = X + B Exemple 18: Escriure les equacions de la translaci´ o en el pla, donat el vector de translaci´ o. ♠ 2. Girs. Un gir ve definit per un centre de gir O, i un angle de rotaci´o ω : en el gir f (OX) resulta de rotar amb aquest angle el vector OX. Exemple 19: l’angle.

Escriure les equacions del gir en el pla, donat el centre i ♠

La concatenaci´ o de girs, en general no ´es commutativa, per`o si s´on del mateix centre, s´ı ho ´es. La simetria respecte a un punt es pot considerar com un gir respecte a aquest centre i angle π. 3. Simetries axials. Una simetria axial ve definida per una recta que ´es l’eix de simetria. Direm que X 0 ´es el sim`etric del punt X respecte a una recta r si XX 0 ´es perpendicular a r i el punt d’intersecci´o ´es el punt mitj`a del segment. Exemple 20: Escriure les equacions de la simetria axial en el pla, donada la recta. ♠ Altres transformacions s´ on tamb´e aplicaci´o directa de les generals, quan es d´ ona un punt que n’´es el centre: Exemple 21: Escriure les equacions de canvi d’escala, i d’homot`ecia en el pla, donat el centre. ♠ Exemple 22: Escriure les equacions de projecci´ o ortogonal sobre una recta en el pla. ♠

2.3

Coordenades polars

Al pla hi ha un sistema de coordenades especialment important, les coordenades polars. Donat un origen de coordenades O, i una semirecta, que ´es l’eix de les abscisses positives, les coordenades polars d’un punt P s´on el parell (r, θ) on r = kOP k i θ ´es l’angle que formen OP i l’eix OX. La relaci´o entre aquestes coordenades polars i les cartesianes d’un punt ve donada per les f´ormules: (x, y) = (r cos θ, r sin θ) Remarquem que, si r = 0, l’angle no est`a un´ıvocament determinat; i que aquest no ´es un canvi de sistema de refer`encia tal com ho hem definit anteriorment. Fer l’exercici 58 de Geometria per a Sistemes Multim`edia.

CAP´ITOL 2. TRANSFORMACIONS AFINS I CANVIS DE VARIABLES 14

2.4

Transformacions afins en 3D

Les translacions i homot`ecies s´on semblants a les que tenim al pla. Altres transformacions afins interessants en 3D s´on: 1. Gir o rotaci´ o axial. Donada una recta r, per a rotar un punt X respecte a aquest eix, calculem la projecci´o de X sobre la recta, O, i girem amb l’angle corresponent el punt, amb centre O en el pla ortogonal a la recta que passa per X. Exemple 23: Escriure les equacions.

♠

En 3D, la simetria respecte a una recta es pot considerar com un gir respecte a aquest eix i angle π. 2. Simetries especulars. Una simetria especular ve definida per un pla de simetria. Direm que X 0 ´es el sim`etric del punt X respecte a aquest pla π si XX 0 ´es perpendicular a π i el punt d’intersecci´o ´es el punt mitj`a del segment. Exemple 24: Escriure les equacions de la simetria especular.

♠

Tamb´e pot ser interessant la simetria central.

2.5

Coordenades cil´ındriques i coordenades esf` eriques

A l’espai 3D hi ha dos sistemes de coordenades especialment importants, les coordenades cil´ındriques i les coordenades esf` eriques. 1. Donat un sistema de refer`encia cartesi`a, si les coordenades cartesianes d’un punt P s´ on (x, y, z), les seves coordenades cil´ındriques s´on (r, θ, z) de forma que (r, θ) s´ on les coordenades polars del punt projecci´o ortogonal de P sobre el pla OXY , en aquest pla. La relaci´o entre aquestes coordenades cil´ındriques i les cartesianes d’un punt ve donada per les f´ormules: (x, y, z) = (r cos θ, r sin θ, z) 2. Donat un sistema de refer`encia cartesi`a, les coordenades esf` eriques d’un punt P s´ on (ρ, θ, φ), de forma que ρ = kOP k, θ ´es la longitud geogr` afica de P - que coincideix amb la coordenada θ de les cil´ındriques -, i φ ´es semblant a la latitud geogr`afica de P , ´es l’angle que formen OZ i OP . La relaci´ o entre les coordenades esf`eriques i cartesianes d’un punt ve donada per les f´ ormules: (x, y, z) = (ρ sin φ cos θ, ρ sin φ sin θ, ρ cos φ) Remarquem de nou que aquests no s´on canvis de sistema de refer`encia tal com hem definit al cap´ıtol anterior. Fer l’exercici 67 de Geometria per a Sistemes Multim`edia.

CAP´ITOL 2. TRANSFORMACIONS AFINS I CANVIS DE VARIABLES 15

2.6

Problemes

1. Els exercicis 47-57 dels apunts de Geometria per a Sistemes Multim`edia s´ on relativament elementals. 2. Exercicis del cap´ıtol 4 dels Problemes de Geometria Computacional.

Cap´ıtol 3

Corbes i superf´ıcies 3.1

Corbes param` etriques i vectors tangents

Si considerem una part´ıcula que es mou en l’espai al llarg del temps, la seva posici´ o en cada instant es pot descriure com (x(t), y(t), z(t)). La traject`oria de la part´ıcula ´es una corba en IR3 . En aquest exemple, la derivada respecte al temps ´es la velocitat (en cada instant), i la segona derivada ´es l’acceleraci´o, que en els dos casos s´ on vectors: v(t) = (x0 (t), y 0 (t), z 0 (t)), a(t) = (x00 (t), y 00 (t), z 00 (t)). M´es formalment, ´ 3.1 Definicio Sigui una funci´ o de variable real i valors vectorials g : J ⊂ IR → IRN i t un punt interior de J; el vector derivada de g en el punt t ´es: g 0 (t) = lim

∆t→0

g(t + ∆t) − g(t) ∆t 2

Si tenim un sistema de refer`encia, la funci´o g es pot imaginar tamb´e com el vector format per les N funcions components g(t) = (g1 (t), g2 (t), . . . , gN (t)). 0 Llavors g 0 (t) = (g10 (t), g20 (t), . . . , gN (t)) es pot considerar com una funci´o de variable real a valors vectorials de IRN , quan el vector derivada existeix en tots els punts de l’interval. Suposem que J = [a, b], i g ∈ C (1 (J), ´es a dir, ´es cont´ınuament derivable en J; denominarem corba param` etrica en IRN a g, sempre que g 0 (t) 6= 0 ∀t ∈ [a, b]. Aquesta condici´ o garanteix que no hi hagin punts singulars de la corba en l’interval. Observacions: 1. Si g 0 (t) 6= 0, es diu que ´es un vector tangent a la corba en g(t). La recta (subespai af´ı) que passa pel punt g(t) i t´e com a vector director g 0 (t) es diu recta tangent a la corba en el punt g(t). En el cas d’una corba g : J → IR3 , g(t) = (x(t), y(t), z(t)), la recta tangent a la corba en un punt g(t0 ) = (x(t0 ), y(t0 ), z(t0 )) = (x0 , y0 , z0 ) t´e com a 16

CAP´ITOL 3. CORBES I SUPERF´ICIES

17

equacions: x − x0 y − y0 z − z0 = 0 = 0 0 x (t0 ) y (t0 ) z (t0 ) 2. Si t representa el temps, la corba seria la traject`oria en l’espai (IRN ) al llarg del temps. El vector tangent seria en aquest cas el vector velocitat (en cada instant). PN 3. Si (ei )1≤i≤N ´es una base can`onica de IRN , i g = i=1 gi ei , tenim que g ´es derivable si i solament si les components gi , funcions reals de variable real, ho s´ on. Es pot identificar el grau de diferenciabilitat de g amb el de les seves components. 4. En dues dimensions, l’equaci´o d’una corba es diu expressada implicitament si t´e la forma F (x, y) = 0; es diu expl´ıcita si t´e la forma y = f (x).

3.2

Parametritzacions equivalents de les corbes, multiplicitat

De vegades podem tenir la mateixa corba amb representacions diferents. En aquest cas es diu que tenim parametritzacions equivalents. Per exemple, l’aplicaci´ o g : [0, 2π] → IR2 definida per g(t) = (a cos t, a sin t) ´es una corba param`etrica en IR2 . Una parametritzaci´ o equivalent la tenim si agafem l’interval [2π, 4π] en lloc de [0, 2π]. Altres conceptes importants s´on: 1. Sigui g : [a, b] → IRN una corba param`etrica C (1 i x ∈ g([a, b]); definim multiplicitat de x com: mlt(x) = card({t ∈ [a, b] : g(t) = x}) 2. Un punt x ∈ g([a, b]) ´es un punt simple si mlt(x) = 1 i una corba g ´es una corba simple si tots els seus punts s´on simples. 3. Denominem extrem inicial de la corba parametritzada per g a g(a), i extrem final a g(b). Direm que g ´es tancada si g(a) = g(b), i que ´es tancada simple si ´es tancada i tots els seus punts s´on simples llevat dels extrems (que constitueixen un punt doble).

3.3

Longitud d’una corba, parametritzaci´ o can` onica

´ 3.2 Definicio Definim longitud de la corba C (1 parametritzada per g : [a, b] → IRN com: Z l=

b

|g 0 (t)|dt

a

2

CAP´ITOL 3. CORBES I SUPERF´ICIES

18

Aquesta definici´ o de longitud ´es independent de la parametritzaci´o. Cal remarcar que, com |g 0 | ´es cont´ınua, la longitud sempre existeix i ´es finita. Tamb´e es pot demostrar que si a = t0 < t1 < . . . < tn = b ´es una partici´o de l’interval X l = lim |g(ti+1 ) − g(ti )|. i

quan la norma de la partici´ o tendeix cap a zero. Si considerem la corba definida de forma que el par´ametre ´es la longitud (parcial) d’aquesta, donada per Z t l(t) = kg 0 (t)kdt a

es diu que tenim la parametritzaci´ o can` onica o intr´ınseca. Aix`o es pot conseguir ´ a dir, tenim la funci´o utilitzant la funci´ o inversa de la funci´o longitud. Es t 7→ l(t), definida per la integral de longitud, i es pot mostrar que aquesta funci´o t´e una inversa l 7→ t, que podem representar com t = t(l). Com l0 (t) = kg 0 (t)k, 1 per les propietats de la funci´ o inversa, tenim que dt dl = kg 0 (t)k . Recordem que, 0 per definici´ o de corba param`etrica, g (t) 6= 0. Es pot comprovar, aplicant la regla de la cadena, que els vectors tangents en aquesta parametritzaci´ o can` onica s´on unitaris. Si utilitzem la parametritzaci´o can` onica, que denominem γ(l), llavors kγ 0 (l)k ja ´es 1 (ja que γ 0 (l) = g 0 (t) kg01(t)k ); denominarem T (l) a aquest vector unitari que ´es γ 0 (l). Utilitzant altra parametritzaci´o es pot conseguir un vector unitari tangent dividint la tangent pel seu m`odul: 0 (t) T (t) = kgg0 (t)k

3.4

Curvatura i torsi´ o

Utilitzant la parametritzaci´ o can`onica, i derivant respecte a l el vector unitari tangent T (l), obtenim un vector ortogonal al tangent (en general, sempre la derivada d’un vector de m` odul constant ´es ortogonal a aquest vector). El m`odul d’aquest vector ortogonal κ = kγ 00 (l)k es denomina curvatura, i κ−1 es diu radi de curvatura. El vector unitari normal aquest es representa per N (l) i es denomina vector normal principal Si tenim altra parametritzaci´o, utilitzant 1. la regla de la cadena i 0

00

(t),g (t)> 2. que la derivada de kg 0 (t)k ´es . kg 0 (t) ∧ g 00 (t)k2

Exemple 25: Calculeu els vectors velocitat i acceleraci´ o, l’equaci´ o de la tangent, la curvatura i la torsi´ o, en cada punt, de la corba parametritzada g(t) = (t sin t, t cos t, 3t). ♠

3.5

Algunes corbes importants

Les c` oniques s´ on corbes planes que tenen per equaci´o impl´ıcita una equaci´o polin` omica de segon grau. Es pot mostrar que les u ´niques possibles s´on: Circumfer`encia, El·lipse, Par` abola i Hip`erbola. Centrades a l’origen de coordenades i eixos els de coordenades, les seves equacions impl´ıcites s´on, respectivament: x2 + y 2 = r2 x2 y2 + =1 a2 b2 y 2 = 2px x2 y2 − 2 =1 2 a b Possiblement, la parametritzaci´o m´es u ´til ´es mitjan¸cant coordenades polars, com, per exemple, l’el·lipse x = a cos t y = b sin t L’h` elix espiral ´es un exemple senzill de corba a l’espai, que es pot parametritzar com: x = at cos t y = at sin t z = ct Problemes 1. Exercicis 58-64 dels apunts de Geometria per a Sistemes Multim`edia. 2. Exercicis 71-100 dels Problemes de Geometria Computacional.

CAP´ITOL 3. CORBES I SUPERF´ICIES

3.6

20

Superf´ıcies en 3D i plans tangents

Suposem la funci´ o g : J ⊂ IRN → IRM ; recordem que la gr`afica de g ´es el N +M subconjunt de R definit per {(x, y) : y = g(x), x ∈ J}; si g ´es diferenciable en el punt a de l’interior de J, el subespai (af´ı, i de dimensi´o N ) de RN +M definit per {(a + x, g(a) + y) : y = dg(a)x, x ∈ IRN } ´es el tangent a la gr`afica de la funci´ o g en el punt (a, g(a)); el seu subespai director ve definit per l’aplicaci´o linial diferencial, i ´es de dimensi´o N . Intu¨ıtivament, una corba t´e un par`ametre (´es un subconjunt unidimensional), i una superf´ıcie, que ´es bidimensional, dos par`ametres independents. Si tenim una funci´ o real de dues variables reals, z = f (x, y), la gr`afica de la funci´o ser` a una superf´ıcie en 3D. Aquesta ´es la f´ ormula expl´ıcita de la superf´ıcie en 3D, i una f´ ormula impl´ıcita ´es F (x, y, z) = 0 (on F ha de verificar unes condicions determinades). Si tenim una superf´ıcie definida expl´ıcitament, en un punt d’aquesta, que ser` a de la forma (x0 , y0 , z0 = f (x0 , y0 )), tindrem un pla tangent a la superf´ıcie en aquest punt. Observem que, a partir de la f´ormula del subespai tangent, podem escriure l’equaci´o d’aquest pla tangent com    x − x0 ∂f ∂f z − z0 = ∂x (x0 , y0 ) ∂y (x0 , y0 ) y − y0 i per tant, l’equaci´ o pot quedar tamb´e com z − z0 =

∂f ∂f (x0 , y0 )(x − x0 ) + (x0 , y0 )(y − y0 ) ∂x ∂y

o (z − z0 ) −

∂f ∂f (x0 , y0 )(x − x0 ) − (x0 , y0 )(y − y0 ) = 0 ∂x ∂y

∂f i aqu´ı es veu que un vector normal al pla tangent ve donat per (− ∂f ∂x (x0 , y0 ), − ∂y (x0 , y0 ), 1)

3.7

Algunes superf´ıcies importants

Les qu` adriques s´ on superf´ıcies que tenen per equaci´o impl´ıcita en l’espai 3D una equaci´ o polin` omica de segon grau. Es pot fer una classificaci´o de les qu` adriques, que no farem aqu´ı, per`o, donem les diferents qu`adriques i una equaci´ o tipus: 1. L’equaci´ o de l’esfera centrada a l’origen ´es: x2 + y 2 + z 2 = r2 2. L’equaci´ o de l’el·lipsoide centrat a l’origen ´es: x2 y2 z2 + 2 + 2 =1 2 a b c 3. L’equaci´ o del paraboloide el·l´ıptic centrat a l’origen ´es: z=

x2 y2 + 2 2 a b

CAP´ITOL 3. CORBES I SUPERF´ICIES

21

4. L’equaci´ o del paraboloide hiperb` olic centrat a l’origen ´es: z=

x2 y2 − 2 2 a b

5. L’equaci´ o de l’hiperboloide d’un full centrat a l’origen ´es: y2 z2 x2 + − =1 a2 b2 c2 6. L’equaci´ o de l’hiperboloide de dos fulls centrat a l’origen ´es: −

x2 y2 z2 − + =1 a2 b2 c2

7. L’equaci´ o del con el·l´ıptic centrat a l’origen ´es: −

y2 z2 x2 + 2 − 2 =0 2 a b c

8. Tamb´e s´ on interessants els cilindres el·l´ıptic, hiperb` olic i parab` olic, d’equacions respectives: x2 y2 + 2 =1 2 a b 2 x y2 − 2 =1 2 a b y 2 = 2px Remarquem que es poden permutar les variables, traslladar el centre, girar, ... donant lloc a altres equacions. De forma semblant al cas 2D, les coordenades cil´ındriques i esf`eriquesla donen parametritzacions u ´tils en 3D. Les superf´ıcies de revoluci´ o s´on generades per una corba (plana) que gira al voltant d’una recta fixa. La corba s’anomena generatriu i la recta eix de revoluci´ o. L’expressi´ o m´es senzilla d’una superf´ıcie de revoluci´o ´es quan una corba parametritzada com (x(t), 0, z(t)) gira al voltant de l’eix OZ. Llavors, en forma param`etrica, la superf´ıcie de revoluci´o queda com: (x(t) cos θ, x(t) sin θ, z(t)) El tor de centre C, eix e (que passa per C) i radis R i r (amb R > r) ´es la superf´ıcie obtinguda per revoluci´o al voltant de l’eix d’una circumfer`encia coplan` aria amb ell, de radi r, centrada en un punt distant R de C. Les equacions param`etriques del tor, considerant C com origen de coordenades, i eix z l’eix del tor, s´ on: x = (R + r cos α) cos β y = (R + r cos α) sin β z = r sin α Problemes 1. Exercicis 67-75 dels apunts de Geometria per a Sistemes Multim`edia. 2. Exercicis del cap´ıtol 3 dels Problemes de Geometria Computacional.

Cap´ıtol 4

Projeccions, geometria i calibratge de c` ameres Si volem reconstruir objectes 3D a partir d’imatges dels objectes obtingudes mitjan¸cant c` ameres, un proc´es de reconstrucci´o consisteix en fixar les c`ameres en unes posicions; col·locar un objecte que es diu calibrador i prendre’n unes imatges a partir de les quals podem obtenir els par`ametres de les c`ameres (calibratge); despr´es llevar l’objecte calibrador sense moure les c`ameres i posar els objectes a reconstruir; amb les imatges que obtenim i els par`ametres de calibraci´ o podem fer aquesta reconstrucci´o 3D. Posteriorment, voldrem fer un moviment ”virtual”d’una de les c`ameres i obtenir les imatges corresponents en forma de film, ´es a dir, un travelling virtual.

4.1

Introducci´ o

La projecci´ o perspectiva ens permet obtenir la relaci´o entre la imatge que d´ona una c` amera i l’objecte corresponent. Per a obtenir la imatge d’un punt B qualsevol d’un objecte calculem la intersecci´o de la recta que passa pel punt B i pel centre de projecci´ o (punt on es troba situada el centre de la lent de la c` amera), i el pla on es forma la imatge. Per a donar aquesta projecci´o en forma de coordenades utilitzarem tres sistemes de refer`encia: ´ la millor refer`encia per a fer la projecci´o perspectiva. 1. Sistema c` amera. Es El centre de coordenades ´es la posici´o de la c`amera (el centre de projecci´o perspectiva) i el pla imatge ´es ortogonal a un dels eixos, que passa per aquest centre. ´ un sistema de refer`encia ”extern”, adaptat a les posi2. Sistema objecte. Es cions dels punts dels objectes, el calibrador, i els que es vol reconstruir. ´ un sistema pla, com la imatge, a la qual s’adapta 3. Sistema imatge. Es i preferiblement donem les coordenades en p´ıxels, a difer`encia dels altres sistemes on les unitats m´es adients s´on de longitud (per exemple mil·l´ımetres). 22

` CAP´ITOL 4. PROJECCIONS, GEOMETRIA I CALIBRATGE DE CAMERES23

La f´ ormula en coordenades m´es u ´til ´es la que permet passar del punt B, expressat en el sistema objecte (”extern”), a les coordenades del punt imatge b corresponent en el sistema imatge (en p´ıxels). Farem les seg¨ uents transformacions: 1. Transformar el punt B del sistema objecte al sistema c`amera. 2. Aplicar la projecci´ o perspectiva al resultat del pas anterior, passant de B a b en el sistema c` amera. 3. Transformar al sistema imatge la projecci´o perspectiva b, que tenim referenciada en el sistema c`amera. El resultat obtingut ´es una matriu que agrupa les transformacions anteriors, anomenada matriu de projecci´ o, que, en principi, serveix per a obtenir la imatge de cada punt. El proc´es que s’anomena calibratge de c` ameres consisteix en calcular aquest conjunt de par`ametres a partir de coordenades conegudes de m´ ultiples punts de l’objecte calibrador en el sistema objecte i les seves coordenades p´ıxel corresponents a la imatge (es necessiten al menys 6 punts). Aix´ı tenim, experimentalment, la matriu de projecci´o, que tamb´e serveix per a, partint d’un p´ıxel imatge, tra¸car una recta que passa per aquest i pel centre de projecci´ o, i que utilitzem per a la reconstrucci´o 3D mitjan¸cant la correspond` encia estereosc` opica: identifiquem un punt de l’objecte a al menys dues imatges, el que ens permet calcular les rectes de projecci´o, i la seva intersecci´ o ens dona les coordenades 3D del punt objecte.

4.2

La projecci´ o perspectiva en el sistema de refer` encia c` amera

L’eix ` optic passa pel punt F , centre de la projecci´o, i ´es ortogonal al pla imatge, al qual intersecta en O, punt principal. La dist`ancia f del punt F al pla imatge es denomina dist` ancia focal. Es pot col·locar el centre de projecci´o davant o darrera el pla imatge, i nosaltres ho farem davant. El punt B es projecta en el pla imatge mitjan¸cant una recta que passa per B i F . El sistema de coordenades c`amera t´e com a origen el punt F , l’eix Z ´es l’eix ` optic, i el pla XY ´es paral.lel al pla imatge. Si (x, y, z) s´on les coordenades de B, les de la seva projecci´ o en el pla imatge s´on: x z y y0 = f z z0 = f

x0 = f

Aquesta transformaci´ o ´es no linial, per`o si utilitzem coordenades homog`enies passa a linial, i es pot escriure en forma matricial:      sx0 1 0 0 0 x  sy 0   0 1 0   0      y   sz 0  =  0 0 1 0  z  s 0 0 0 1/f 1

` CAP´ITOL 4. PROJECCIONS, GEOMETRIA I CALIBRATGE DE CAMERES24

Si la projecci´ o de B ´es b, i denominem P a la matriu, ho podem escriure de forma compacta com: b = PB

4.3

Transformaci´ o c` amera-imatge

El sistema imatge, adaptat espec´ıficament a la visualitzaci´o de la imatge per pantalla, t´e l’origen a un cant´o de la pantalla (per exemple, el superior a l’esquerra), com a eixos els vertical i horitzontal, i d´ona les mesures expressades en p´ıxels. Per a transformar les coordenades del punt ja obtingudes en el sistema c` amera a aquest sistema, necessitem: u0 , v0 , i w0 , (coordenades de F en el sistema imatge i per tant en p´ıxels); i els factors d’escala vertical ku i horitzontal ku , (en p´ıxels/mil·l´ımetre), que s´on diferents ja que els p´ıxels d’una pantalla s´on rarament quadrats. Les coordenades de b referenciades en el sistema c`amera ja utilitzades, s´on (x0 , y 0 , z 0 ); si en el sistema imatge les denotem per (u, v), la transformaci´o ve donada pel canvi de sistema de refer`encia, i queda com:      0    u ku 0 0 −1 0 0 x u0  v  =  0 kv 0   0 1 0   y 0  +  v0  w 0 0 0 0 0 −1 z0 w0 i si ens quedem u ´nicament amb les coordenades planes i utilitzem coordenades homog`enies, ho podem re-escriure com:  0      x −ku 0 0 u0 su  y0    sv  =  0 kv 0 v0    z0  s 0 0 0 1 1 Si denominem K a la matriu, ho podem escriure de forma compacta com:  0    x su  y0   sv  = K  0   z  s 1

4.4

Combinant projecci´ o i transformaci´ o: els par` ametres intr´ınsecs

Multiplicant les matrius K i P concatenem la projecci´o perspectiva i la transformaci´ o. Com estem utilitzant coordenades homog`enies, podem multiplicar tots els coeficients de la matriu KxP per f i queda:       x su αu 0 u0 0    sv  =  0 αv v0 0   y   z  s 0 0 1 0 1

` CAP´ITOL 4. PROJECCIONS, GEOMETRIA I CALIBRATGE DE CAMERES25

on αu = −ku f , αv = kv f , que, juntament amb u0 i v0 constitueixen els par` ametres intr´ınsecs. Si denominem Ic a la matriu, tenim, en forma compacta:     x su    sv  = Ic  y   z  s 1

4.5

La transformaci´ o a sistema objecte i els par` ametres extr´ınsecs

Finalment, queda fer la transformaci´o objecte-c`amera on fem una translaci´o de l’origen i una rotaci´ o d’eixos:        x r11 r12 r13 X tx  y  =  r21 r22 r23   Y  +  ty  z r31 r32 r33 Z tz que es pot  x  y   z 1

escriure utilitzant   r11 r12   r21 r22 =   r31 r32 0 0

matrius ampliades com:   r13 tx X   r23 ty   Y    r33 tz Z  1 0 1

Els coeficients de la matriu ampliada (que denotem per A) es coneixen com a par` ametres extr´ınsecs. De vegades utilitzarem la notaci´o ri = (ri1 , ri2 , ri3 ).

4.6

La matriu de projecci´ o perspectiva; la obtenci´ o dels par` ametres a partir de la matriu

Finalment, multiplicant    su   sv  = Ic A   s

les matrius Ic i A, tenim  X Y  , Z  1

que ens d´ ona l’expressi´ o que busc`avem. Coneixem la matriu 3x4 resultant Ic A com matriu de projecci´ o perspectiva M :   m11 m12 m13 m14 M =  m21 m22 m23 m24  m31 m32 m33 m34 Si denotem per mi = (mi1 , mi2 , mi3 ), la matriu M es pot representar de forma m´es compacta com:   m1 m14 M =  m2 m24  m3 m34

` CAP´ITOL 4. PROJECCIONS, GEOMETRIA I CALIBRATGE DE CAMERES26

A partir dels coeficients de la matriu M tamb´e podem recuperar els par`ametres intr´ınsecs i extr´ınsecs, mitjan¸cant les f´ormules seg¨ uents: r3 = m3 u0 =< m1 , m3 > v0 =< m2 , m3 > αu = −km1 ∧ m3 k αv = km2 ∧ m3 k 1 (m1 − u0 m3 ) αu 1 r2 = (m2 − v0 m3 ) αv 1 tx = (m14 − u0 m34 ) αu 1 ty = (m24 − v0 m34 ) αv tz = m34

r1 =

Aquestes f´ ormules es poden utilitzar per al travelling virtual.

4.7

Calibratge

Ara podem definir el procediment (experimental) del calibratge d’una c`amera. Si tenim una imatge obtinguda amb la c`amera d’un objecte adient (que es denomina calibrador), per a cada punt de l’objecte (Xi , Yi , Zi ) que es projecta en la imatge com (ui , vi ) tenim       Xi sui m11 m12 m13 m14    svi  =  m21 m22 m23 m24   Yi  ,  Zi  s m31 m32 m33 m34 1 el que d´ ona dues equacions per a cada punt. Si volem calcular les 12 inc`ognites mij de la matriu M , el m´ınim n´ umero de punts necessari ´es 6, per`o millor si tenim m´es, els resultats del calibratge seran m´es precisos. El sistema resultant, a m´es de sobredeterminat, ´es homogeni, i per a resoldre-ho, hi ha dues alternatives: 1. Fixar un dels coeficients mij . Usualment farem m34 = 1 ja que ´es la component z del vector de translaci´o entre els sistemes objecte i c`amera. Aquesta ´es una soluci´ o una mica arbitr`aria. 2. Utilitzar el fet geom`etric que en les rotacions els vectors s´on unitaris; en el nostre cas, m3 = r3 , i per tant podem escriure que com km3 k2 = 1. En els dos casos utilitzarem m´ınims quadrats (i en el segon cas, extrems condicionats).

` CAP´ITOL 4. PROJECCIONS, GEOMETRIA I CALIBRATGE DE CAMERES27

4.8

Reconstrucci´ o 3D utilitzant estereoscopia

El proc´es de reconstrucci´ o basat en correspond`encia estereosc`opica es basa en haver fet pr`eviament el calibratge d’al menys dues c`ameres. Suposem que tenim un punt de l’objecte que es veu per les c`ameres, i sabem les coordenades de les imatges del punt per les diferent c`ameres, (u, v), (u0 , v 0 ), ... llavors cada c` amera ens subministra 2 equacions, com abans, i per tant necessitem al menys dues c` ameres per a les tres inc`ognites que s´on ara les coordenades del punt objecte (X, Y, Z). Si tenim m´es c`ameres, millor. En tot cas, com el sistema ´es sobredeterminat, cal aplicar m´ınims quadrats. Aquesta ´es una reconstrucci´o punt a punt. Per altres procediments recuperem les superf´ıcies que determinen.

4.9

Perspectiva c` onica i perspectiva cil´ındrica

La projecci´ o que hem vist ´es un cas particular de la perspectiva c` onica, que ´es una projecci´ o central: donat un centre, C, i un pla π, el punt projecci´o d’un punt P ´es la intersecci´ o de la recta que passa per C i P amb el pla π. Cal que es verifiqui C ∈ / π. Tamb´e s’utilitza de vegades la perspectiva cil´ındrica, que ´es una projecci´ o paral·lela: donada una direcci´o, v, i un pla π, el punt projecci´o d’un punt P ´es la intersecci´ o de la recta que passa per P en la direcci´o de v amb el pla π. Cal que es verifiqui que v no ´es paral·lela a π. En aquest cas ´es com si l’observador est` a a dist` ancia infinita de l’objecte.