visión tridimensional - ami research...

Visión tridimensional

Javier Sánchez PérezFacultad de Informática

Universidad de Las Palmas de Gran Canariaemail: [email protected]

http://serdis.dis.ulpgc.es/~jsanchez

Contents

1 Introducción 2

2 Geometría proyectiva y transforma-ciones 2D 32.1 El plano proyectivo 2D . . . . . . . 3

2.1.1 Puntos y líneas . . . . . . . 32.1.2 Puntos ideales y la línea en

el infinito . . . . . . . . . . 32.1.3 Cónicas y cónicas duales . . 3

2.2 Transformaciones proyectivas . . . 42.2.1 Transformaciones de

líneas y cónicas . . . . . . . 42.3 Jerarquía de transformaciones . . . 4

2.3.1 Clase I: Isometrías . . . . . 42.3.2 Clase II: Transformaciones

de similaridad . . . . . . . . 52.3.3 Clase III: Transforma-

ciones afines . . . . . . . . . 52.3.4 Clase IV: Transforma-

ciones proyectivas . . . . . 52.4 Geometría proyectiva 1D (P1) . . . 52.5 Recuperación de propiedades

afines y métricas a partir de lasimágenes . . . . . . . . . . . . . . . 62.5.1 Línea en el infinito . . . . . 62.5.2 Recuperación de

propiedades afines . . . . . 62.5.3 Puntos circulares y su dual 72.5.4 Ángulos en el plano

proyectivo . . . . . . . . . . 72.5.5 Recuperación de

propiedades métricas . . . . 72.6 Otras propiedades de las cónicas . 8

2.6.1 La relación pole-polar . . . 8

3 Geometría proyectiva y transforma-ciones 3D 83.1 Puntos y transformaciones

proyectivas . . . . . . . . . . . . . 83.2 Planos, líneas y cuádricas . . . . . 83.3 Plano en el infinito . . . . . . . . . 93.4 La cónica absoluta . . . . . . . . . 93.5 La cuádrica dual absoluta . . . . . 10

4 Estimación de transformacionesproyectivas 104.1 Algoritmo DLT . . . . . . . . . . . 104.2 Estimación robusta . . . . . . . . . 11

4.2.1 RANSAC . . . . . . . . . . 114.3 Cálculo automático de una homo-

grafía . . . . . . . . . . . . . . . . 12

5 Geometría de una vista simple -Modelo de la cámara 125.1 Cámara finita . . . . . . . . . . . . 125.2 Cámara proyectiva . . . . . . . . . 145.3 Cámaras en el infinito . . . . . . . 15

5.3.1 Cámara afines . . . . . . . 15

6 Cálculo de la matriz P 156.1 Ecuaciones básicas . . . . . . . . . 15

7 Geometría epipolar y matriz funda-mental 167.1 Geometría epipolar . . . . . . . . . 167.2 La matriz fundamental . . . . . . . 16

7.2.1 Deducción geométrica . . . 167.2.2 Deducción algebraica . . . . 177.2.3 Condición de correspon-

dencia . . . . . . . . . . . . 17

1

1 INTRODUCCIÓN 2

7.2.4 Propiedades de la matrizfundamental . . . . . . . . . 17

7.2.5 Homografía de la líneaepipolar . . . . . . . . . . . 17

7.3 Matrices fundamentales especiales 177.3.1 Traslación pura . . . . . . . 17

7.4 Cálculo de las matrices de las cá-maras . . . . . . . . . . . . . . . . 18

7.5 Matriz esencial . . . . . . . . . . . 18

8 Reconstrucción 3D de cámaras 188.1 Método de reconstrucción . . . . . 188.2 Ambigüedad en la reconstrucción . 188.3 Teorema de la reconstrucción

proyectiva . . . . . . . . . . . . . . 198.4 Reconstrucción estratificada . . . . 19

9 Cálculo de la matriz F 209.1 Ecuaciones básicas . . . . . . . . . 209.2 El algoritmo de 8 puntos normal-

izados . . . . . . . . . . . . . . . . 209.3 Distancia geométrica . . . . . . . . 209.4 Cálculo automático de F . . . . . . 21

10 Cálculo de la estructura 2110.1 Métodos lineales de triangulación . 2110.2 Función de coste de error geométrico 2210.3 Solución óptima . . . . . . . . . . . 22

11 Geometría epipolar afín 2311.1 La matriz F afín . . . . . . . . . . 2311.2 Cálculo de FA a partir de puntos

en correspondencia . . . . . . . . . 23

1 Introducción

El objetivo de este curso es el de profundizaren temas relacionados con la visión tridimen-sional y, en concreto, con la reconstrucción 3D.De forma básica, el campo de la visión tridimen-sional trata de obtener, a partir de imágenes 2D,información relacionada con la escena original dedonde se tomaron dichas imágenes.Las imágenes 2D se suelen capturar a través

de cámaras digitales o videocámaras. Estas cá-maras suelen proyectar los objetos 3D en unplano a través de una transformación proyectiva.Esta transformación se puede representar por

medio de una matriz que facilita el tratamientode muchos problemas gracias al álgebra lineal.Una parte fundamental del curso será, por

tanto, el estudio de la geometría proyectiva.Veremos muchos conceptos que tienen un rep-resentación geométrica real y, lo más impor-tante, propondremos modelos matématicos quenos permitirán representarlos y trabajar con el-los.Otra parte importante es el modelado de las

cámaras. Para poder conocer la geometría deuna escena real, es necesario que conozcamoscómo las cámaras transforman los objetos y losproyectan en la imagen. Las cámaras se puedenmodelar a través de un conjunto de parámetros,intrínsecos y extrínsecos, que tienen un signifi-cado físico concreto. Los parámetros intrínsecosson los que tienen que ver con la propia lente dela cámara, mientras que los extrínsecos tienenque ver con la posición y orientación de la cá-mara en la escena.Por otra parte, estudiaremos el problema de la

calibración. Estos son métodos que nos ayudan aestimar la configuración del sistema de cámarasy del propio modelo de las cámaras a partir de lasimágenes que se toman de la escena. Este prob-lema es importante de cara a estimar de formaprecisa los datos necesarios para poder realizarposteriormente la reconstrucción de la escena opara relacionar geométricamente las cámaras.Posteriormente extrapolaremos el caso de la

visión a partir de una cámara al caso en que ten-emos dos cámaras. Esto es lo que se denominala visión estereoscópica. La visión estereoscópicaes la que posee el ser humano y un gran númerode animales. El interés de este tipo de visiónes que nos permite percibir la profundidad delos objetos y realizar un amplio conjunto de tar-eas que sin ella serían bastante complejas. Nosinteresaremos por los modelos matemáticos quenos permitirán representar y trabajar con doscámaras que visualizan una escena común y es-tudiaremos sus características más interesantes.Finalmente trataremos el problema de la re-

construcción tridimensional. A partir de dos cá-maras y de ciertas correspondencias entre susimágenes, es posible obtener los puntos 3D orig-inales. Estudiaremos formas distintas de recon-

2 GEOMETRÍA PROYECTIVA Y TRANSFORMACIONES 2D 3

struir la escena a partir de un conjunto de cor-respondencias.Existen muchos problemas en visión 3D que

no requieren realizar la reconstrucción final.Muchas veces sólo nos basta con conocer lageometría de las cámaras y cómo están rela-cionadas para realizar ciertas medidas que deigual forma se pueden realizar entre los puntos dela escena. Por esto, la reconstrucción es, muchasveces, un paso opcional.

2 Geometría proyectiva ytransformaciones 2D

2.1 El plano proyectivo 2D

2.1.1 Puntos y líneas

Un punto se puede representar en un plano pormedio de un par (x, y) en R2.Una línea en el plano se representa por medio

de la ecuación ax + by + c = 0. l = (a, b, c)T .Los vectores (a, b, c)T y k(a, b, c)T representanla misma línea. Vector homogéneo es una clasede equivalencia de vectores que cumplen estarelación. El conjunto de clases de equivalenciade vectores en R3. − (0, 0, 0)T forma el espacioproyectivo P2Un punto en coordenadas homogéneas se rep-

resenta como x = (x, y, 1)T . Los puntos inclui-dos en una recta son aquellos que cumplen x · l =0. Se cumple además que x · l = k (x · l) = 0,por lo tanto los puntos en el espacio proyec-tivo P2 se representan como x = (kx, ky, k) =(x1,x2, x3), y su correspondiente en R2 comox = (x1/x3, x2/x3).

Theorem 1 La intersección de dos líneas l y l0

es el punto x = l× l0.

Proof. l ·¡l× l0

¢= l0 ·

¡l× l0

¢= 0 = l0T · x =

lT · x

Example 2 Encontrar el punto de intersecciónentre las rectas x = 1 e y = 1.La representación homogénea de la primera

línea es l = (−1, 0, 1)T y la de la segunda esl0 = (0,−1, 0), por lo que la intersección esx = l× l0 = (1, 1, 1)T .

Remark 3 La línea que une dos puntos x y x0

es l = x× x0.

2.1.2 Puntos ideales y la línea en el in-finito

La intersección de dos líneas paralelas l =(a, b, c)T y l0 = (a, b, c0)T da como resultado unpunto x = l × l0 = (b,−a, 0) que se denominapunto ideal o punto en el infinito. Si obtenemosel correspondiente punto en coordenadas inho-mogéneas, obtenemos (b/0,−a/0)T . Gracias alas coordenadas homogéneas podemos represen-tar puntos de este estilo.Luego los puntos en el infinito son aquellos que

se pueden representar como (x1, x2, 0) en P2. To-dos los puntos en el infinito están incluidos enuna misma línea, línea en el infinito, que se rep-resenta como l∞ = (0, 0, 1)T .Cualquier línea y sus paralelas, l = k(a, b, c)T ,

intersectan la línea en el infinito en x = (b. −a, 0). En coordenadas inhomogéneas, el vector(b,−a) es ortogonal a la normal (a, b), con lo querepresenta la dirección de la línea. La línea enel infinito se puede ver como el conjunto de lasdirecciones de las líneas del plano.

Remark 4 Principio de dualidad: A cualquierteorema sobre geometría proyectiva en 2D le cor-responde un teorema dual que se deriva de inter-cambiar los roles entre puntos y líneas.

2.1.3 Cónicas y cónicas duales

La ecuación de una cónica en coordenadas inho-mogéneas es:

ax2 + bxy + cy2 + dx+ ey + f = 0.

Si homogeneizamos esta ecuación atendiendoa las relaciones x→ x1/x3 e y → x2/x3 entoncestenemos:

ax21 + bx1x2 + cx22 + dx1x3 + ex2x3 + fx23 = 0

que si lo expresamos a través de notación matri-cial tenemos xTCx = 0, con

C =

⎛⎝ a b/2 d/2b/2 c e/2d/2 e/2 f

⎞⎠ .


Figure 1: Líneas que satisfacen lTC∗l = 0.

Esta matriz tiene cinco grados de libertad, conlo que necesitaríamos cinco puntos distintos parapoder especificarla.

Theorem 5 La línea l tangente a la cónica Cen el punto x viene dada por l = Cx

Proof. La línea l = Cx pasa por x ya quexTl = xTCx = 0. Si la línea tiene otro punto deintersección, y, en la cónica entonces se tiene quecumplir que xTCy = yTl = 0. De esto se deduceque (x+λy)TC(x+λy)=0 se tiene que cumplirpara cualquier λ, lo que significa que la línea yla cónica coinciden (cónica degenerada).

Puntos que satisfacen xTCx = 0.

Cónica dual: La cónica dual nos da el conjuntode líneas que son tangentes a la cónica y vienedado por lTC∗l = 0, con C∗ la matriz adjuntade C. Si C es invertible entonces C∗ = C−1.

2.2 Transformaciones proyectivas

Una proyectividad es un mapeo invertible h deP2 sobre sí mismo de tal forma que tres puntosx1,x2 y x3 reposan sobre la misma línea sí y solosí h (x1) , h (x2) y h (x3) también reposan sobreuna misma línea.Una proyectividad se suele llamar también

colineación, transformación proyectiva u homo-grafía.Una proyectividad se puede representar a

través de una matriz H de 3×3 no singular deforma que la relación entre puntos originales ytransformados, es una aplicación lineal, x0= Hx.

2.2.1 Transformaciones de líneas y cóni-cas

Las líneas, bajo una transformación proyectiva,se transforman de la siguiente manera. Ten-emos dos líneas lTx = 0 y l0Tx0 = 0, y sabe-mos que los puntos se corresponden a través dex0 = Hx, luego las líneas se relacionan comol0Tx0 = lTH−1Hx, con lo que la línea transfor-mada es

l0 = H−T l.

Las cónicas se transforman comoxTCx = x0TH

−TCH−1x0, con lo que

C0 = H−TCH−1.

2.3 Jerarquía de transformaciones

2.3.1 Clase I: Isometrías

Son transformaciones que preservan la distanciaEuclídea.

⎛⎝ x0

y0

1

⎞⎠ =

⎛⎝ cos θ − sin θ txsin θ cos θ ty0 0 1

⎞⎠⎛⎝ xy1

⎞⎠donde = ±1. Este tipo de transformacionessirve para modelar movimientos rígidos. Sepuede representar como una rotación, un de-splazamiento y reflexión:

x0 = HEx =

µR t0T 1

¶x.

Este tipo de transformaciones tiene tres gradosde libertad, con lo que se puede calcular a partirde dos puntos en correspondencia.Los invariantes que se mantienen con estas

transformaciones son: la distancia entre dos pun-tos, el ángulo entre dos líneas, y el área.


2.3.2 Clase II: Transformaciones de sim-ilaridad

Es igual que una isometría compuesta con unescalado isotrópico.

⎛⎝ x0

y0

1

⎞⎠ =

⎛⎝ s cos θ −s sin θ txs sin θ s cos θ ty0 0 1

⎞⎠⎛⎝ xy1

⎞⎠x0 = HSx =

µsR t0T 1

¶x.

Esta transformación tiene como característicaque preserva la forma de los objetos, teniendocuatro grados de libertad, con lo que se puedencalcular a partir de dos puntos en corresponden-cia.Los invariantes para este tipo de transforma-

ciones son: ángulo entre dos líneas, el ratio entredos distancias y el ratio entre dos áreas.Cuando hablamos de estructura métrica nos

referimos a que la estructura está definida hastauna similaridad.

2.3.3 Clase III: Transformaciones afines

Una transformación afín se representa como unamatriz:

⎛⎝ x0

y0

1

⎞⎠ =

⎛⎝ a11 a12 txa21 a22 ty0 0 1

⎞⎠⎛⎝ xy1

⎞⎠x0 = HAx =

µA t0T 1

¶x.

Un transformación afín tiene seis grados de lib-ertad, con lo que se puede especificar a travésde tres puntos en correspondencia. Este tipode transformaciones se puede ver como la com-posición de una rotación y de un escalado noisotrópico. La matriz afín se puede descomponersiempre como:

A = R(θ)R(−φ)DR(φ)

con D =

µλ1 00 λ2

¶.

Los invariantes que se mantienen a través deeste tipo de transformaciones son: líneas parale-las (se mantienen los puntos en el infinito), ratiode longitudes de segmentos de líneas paralelas yratio de áreas.

2.3.4 Clase IV: Transformacionesproyectivas

La forma de una transformación proyectiva vienedada por la siguiente matriz:

x0 = HPx =

µA tvT v

¶x.

con v = (v1, v2)T . La matriz tiene ocho grados

de libertad, con lo que se necesitan al menos 4puntos en correspondencia.El invariante proyectivo más importante es el

cross ratio (ratio de ratios) de cuatro puntos co-lineales.Las transformaciones proyectivas nos permiten

trabajar con puntos en el infinito de igual formaque con cualquier otro punto.El número de invariantes funcionalmente inde-

pendientes para cada transformación es igual omayor que el número de grados de libertad dela configuración menos el número de grados delibertad de la transformación.

Example 6 Un cuadrado tiene 8 grados de lib-ertad (2 por cada punto), por lo que posee 4 in-variantes para transformaciones de similaridad,2 para afines y cero para proyectivas.

2.4 Geometría proyectiva 1D (P1)

Un punto en una línea se representa como x =(x1, x2)

T . Cuando el segundo componente esigual a cero entonces se trata de un punto en elinfinito. Una transformación proyectica se repre-senta como una matriz homogénea de 2×2. Estamatriz tiene tres grados de libertad.El cross ratio. Es el invariante básico proyec-

tivo de P1. Dados 4 puntos el cross ratio se definecomo:

Cross(x1,x2,x3,x4) =|x1x2| |x3x4||x1x3| |x2x4|


x1

x2 x3

x4

l1

l2

l3

l4

l

c

Figure 2: Línea Concurrentes.

con |x1x2| el determinante de los dos puntos. Al-gunos comentarios sobre el cross ratio:

1. El cross ratio es independiente del escalarque multiplica al punto ya que este se can-cela en la división.

2. Si la segunda compenente de los puntos esigual a 1 entonces el determinante entre dospuntos es igual a la distancia con signo entreesos dos puntos..

3. La definición del cross ratio también esválido para puntos ideales.

4. El valor del cross ratio es invari-ante bajo cualquier transforma-ción proyectiva. Si x0 = H2×2xentonces Cross(x01,x

02,x

03,x

04) =

Cross(x1,x2,x3,x4).

Líneas Concurrentes. Las líneas que inter-sectan en un punto de un plano también tienenla geometría de P1. El cross ratio de las líneas esigual al cross ratio de los puntos y es independi-ente de la posición de la línea l.

2.5 Recuperación de propiedadesafines y métricas a partir de lasimágenes

Si queremos realizar algún tipo de estimación ac-erca de longitudes de líneas o de ángulos en la im-agen, entonces tenemos que eliminar la distorsióndebida a la proyección de la escena en la imagen.Los grados de libertad de una transformación

l = HP(l∞)

Figure 3: Rectificación afín.

proyectiva es de 8 mientras que los de una trans-formación de similaridad es de 4, con lo que siqueremos determinar algunas propiedades métri-cas de la imagen, entonces tenemos que eliminarlos 4 grados de libertad de diferencia. Estos gra-dos de libertad se pueden asociar a objetos ge-ométricos concretos: La línea en el infito (l∞)que representa 2 dof y los dos puntos circulares(2 dof) que se encuentran sobre esa línea.

2.5.1 Línea en el infinito

En una transformación proyectiva, los puntos ylíneas en el infinito se pueden transformar enpuntos y líneas finitas. Si la transformación fuerauna afinidad, entonces los puntos y líneas en elinfinito se quedarían en el infinito.La línea en el infinito l∞ se mantiene fija

bajo una transformación proyectiva si y solo sila transformación es una afinidad.

2.5.2 Recuperación de propiedadesafines

Una manera de recuperar las propiedades afineses localizar l∞ en la imagen y transformarla asu posición canónica l∞ = (0, 0, 1)T . La matrizque logra esta transformación se puede aplicar atoda la imagen con el fin de rectificarla y podertomar medidas afines. Si la imagen de la línea enel infinito es l = (l1, l2, l3), entonces una trans-formación para eliminar el efecto proyectivo es:

H =

⎛⎝ 1 0 00 1 0l1 l2 l3

⎞⎠HA


2.5.3 Puntos circulares y su dual

Bajo cualquier transformación de similidaridadexisten dos puntos en l∞ que se mantienen fijos.Estos son los puntos circulares I, J con coorde-nadas canónicas

I =

⎛⎝ 1i0

⎞⎠ J =

⎛⎝ 1−i0

⎞⎠Se ve fácilmente que son fijos bajo este tipo

de transformaciones ya que si les aplicamosuna transformación de similaridad cualquiera lospuntos no cambian

I0 = HSI

=

⎛⎝ s cos θ −s sin θ txs sin θ s cos θ ty0 0 1

⎞⎠ I= se−iθ

⎛⎝ 1i0

⎞⎠ = I.

Se llama puntos circulares porque todos loscírculos intersectan a l∞ en esos dos puntos.La ecuación de un cículo en coordenadas ho-mogéneas es

x21 + x22 + dx1x3 + ex2x3 + fx23 = 0.

Esta ecuación intersecta a la línea en el infinitoen los puntos ideales para los que x3 = 0, con loque nos queda

x21 + x22 = 0

que tiene por soluciones precisamente los puntosI, J.Si identificamos los puntos circulares, entonces

pordemos recuperar las propiedades de similari-dad de la imagen.

2.5.4 Ángulos en el plano proyectivo

El ángulo entre dos líneas l = (l1, l2, l3) y m =(m1,m2,m3) es

cos θ =l1m1 + l2m2q¡

l21 + l22¢ ¡m21 +m2

2

¢

Esto no se puede aplicar después de una trans-formación afín o proyectiva. Existe una expre-sión análoga que sí es invariantea transforma-ciones proyectivas:

cos θ =lC∗∞mp

(lTC∗∞l) (mTC∗∞m)

donde C∗∞ es la cónica dual a los puntos circu-lares. Gracias a esta fórmula, si se puede identi-ficar C∗∞ en el plano proyectivo, entonces pode-mos calcular ángulos.Dos líneas son ortogonales si se cumple que

lC∗∞m = 0.También se pueden medir ratios de longitud si

la cónica dual en el infinito es identificada.

2.5.5 Recuperación de propiedadesmétricas

Se pueden recuperar las propiedades métricas deuna imagen si conseguimos transformar los pun-tos circulares a su forma canónica. Si conocemoslos puntos circulares en una imagen podemos en-contrar una transformación proyectiva, H, quelos convierta a (1,±i, 0) en l∞.La cónica dual en el infinito C∗∞ nos per-

mite realizar una rectificación métrica, identif-icando los componentes afines y proyectivos dela transformación y dejando sólo las de similar-idad. Si suponemos que un conjunto de puntoseuclídeos se transforman a través de H, entoncesla cónica en el infinito C∗∞ se transforma comoC∗0∞ = HC∗∞H

T . Descomponiendo la transfor-mación tenemos

C∗0∞ = HPHAHSC∗∞ (HPHAHS)

T

= (HPHA)¡HSC

∗∞H

TS

¢ ¡HT

AHTP

¢= (HPHA)C

∗∞¡HT

AHTP

¢=

µKKT KTvvTK 0

¶.

C∗∞ es invariante frente a transformaciones desimilaridad, con lo que la componente de simi-laridad está indefinida.Por lo tanto, si podemos identificar C∗∞ en

la imagen, entonces la distorsión proyectiva sepuede rectificar hasta una similaridad.


l x

C

y

Figure 4: Relación pole-polar

Una forma sencilla de encontrar esta transfor-maciónH es por medio del SVD. El SVD de C∗0∞es

C∗0∞ = U

⎛⎝ 1 0 00 1 00 0 0

⎞⎠UT

con lo que la transformación para rectificar laimagen es H = U.Para localizar la cónica dual en el infinito

podemos especificar 5 pares de líneas ortogo-nales.

2.6 Otras propiedades de las cónicas

2.6.1 La relación pole-polar

Un punto x y una cónica C definen una rectal = Cx. Esta recta se denomina el polar de xcon respecto a C, y el punto x es el pole de l conrespecto a C.La línea polar intersecta a la cónica en dos

puntos que coinciden con las rectas tangentes ala cónica que intersectan en x (ver figura 4). Siel punto x está en C, entonces la línea polarcoincide con la línea tangente a la cónica en elpunto.

Example 7 Si suponemos un círculo de radior centrado en el eje de las x en el punto a, suecuación será (x− a)2 + y2 = r2. La cónica querepresenta esta ecuación es

C =

⎛⎝ 1 0 −a0 1 0−a 0 a2 − r2

⎞⎠ .

La línea polar del origen es l = C(0, 0, 1)T =¡−a, 0, a2 − r2

¢T . Esto es una línea vertical enx = (a2−r2)/a. Si r = a entonces el origen estáincluido en el borde del círculo y la línea polar esel eje de las y (que es tangente al círculo en elorigen).

Puntos conjugados: Si un punto y estáen la línea l = Cx, entonces yT l = yTCx =0.Cualquier par de puntos x,y que satisfacenyTCx =0 son puntos conjugados. Esta relaciónes simétrica, lo que quiere decir que si x está enla línea polar de y, entonces y está en la polarde x.Existe una relación dual con las líneas con-

jugadas: dos líneas l,m son conjugadas silTC∗m = 0.

3 Geometría proyectiva ytransformaciones 3D

3.1 Puntos y transformacionesproyectivas

Un punto en P3se representa en coordenadashomogéneas como X = (x1, x2, x3, x4). Estepunto en el espacio R3 representa el punto X =(x1/x4, x2/x4, x3/x4).

Aquellos puntos que cumple que x4 = 0 repre-sentan puntos en el infinito.Una transformación proyectiva en P3 es

una transformación lineal en coordenadas ho-mogéneas representada por una matriz de 4×4:X0 = HX. Esta matriz tiene 15 grados de liber-tad (16 menos uno por el escalado).

3.2 Planos, líneas y cuádricas

En P3 los puntos y los planos son duales. Lalíneas son duales entre sí.Planos: Un plano se puede escribir como

π1x+π2y+π3z+π4 = 0, con lo que un plano tiene3 grados de libertad. Si homogeneizamos estaecuación obtenemos π1x1+π2x2+π3x3+π4x4 =0, o lo que es lo mismo πTX = 0. Las tresprimeras coordenadas del plano representan lanormal del plano.


Tres puntos definen un plano: si tenemos trespuntosXi que reposan sobre un plano π entoncestenemos un sistema de ecuaciones de la forma⎛⎝ XT

1

XT2

XT3

⎞⎠π = 0.

Otra forma de obtener un plano es a través deldeterminante de la matrizM = (X,X1,X2,X3).Si el detM = 0, entonces significa que el puntoX es una combinación lineal de los otros tres, y,por tanto, reposa en el mismo plano que ellos

detM = x1D234 − x2D134 + x3D124 − x4D123,

luego el plano viene dado por

π =(D234,−D134,D124,−D123)T

Tres planos definen un punto: Se puedeobtener el punto de intersección de tres planosa través del sistema de ecuaciones⎛⎝ πT

1

πT2

πT3

⎞⎠X = 0.

También podemos obtener el punto de formaanáloga a como se obtiene un plano a partir detres puntos descrito anteriormente.Bajo una transformación proyectiva,

X0= HX, un plano se transforma comoπ0 = H−1π.Líneas: Una forma de representar las líneas

en el espacio es a través de dos puntos, A,B.Podemos utilizar notación matricial para repre-sentarlas:

W =

µAT

BT

¶.

Los puntos de la línea se forman como(λ, µ)W =λA + µB. El espacio nulo por laderecha es el conjunto de planos que tienen esalínea como generadora:WP = 0, con ATP = 0y BTP = 0, lo que significa que los dos puntosestán en el plano.Análogamente, si tenemos dos planos P,Q,

entonces la matriz

W∗ =

µPT

QT

¶

representa el conjunto de planos, λP+µQT , quetienen la línea común de ambos como eje y el es-pacio nulo de la derecha, es el conjunto de puntosque reposan sobre la recta: W∗X = 0.

3.3 Plano en el infinito

El plano en el infinito en el espacio es similar ala línea en el infinito en 2D. Su forma canónicaes π∞ = (0, 0, 0, 1)T .

Este nos permite identificar propiedadesafines: dos planos son parelelos sí y solo sí sulínea de intersección está en π∞; una línea esparalela a otra línea, o a un plano, si el punto deintersección está en π∞.El plano en el infinito π∞ es un plano fijo bajo

una transformación proyectiva H, sí y solo sí Hes una afinidad.

3.4 La cónica absoluta

La cónica absoluta, Ω∞, es una cónica en π∞.Los puntos en Ω∞ satisfacen

x21 + x22 + x23x4

¾= 0

La cónica absoluta, Ω∞, es una cónica fija bajouna transformación proyectiva H, sí y solo sí Hes una similaridad.Propiedades interesantes de la cónica absoluta:

1. Los puntos de la cónica absoluta per-manecen en ella después de una transfor-mación de similaridad (sólo globalmente, nopunto a punto).

2. Todos los círculos la intersectan en dos pun-tos.

3. Todas las esferas intersectan a π∞ en Ω∞.

Propiedades métricas:

cos θ =lΩ∞mp

(lTΩ∞l) (mTΩ∞m)

4 ESTIMACIÓN DE TRANSFORMACIONES PROYECTIVAS 10

3.5 La cuádrica dual absoluta

La dual de la cónica absoluta es una cuádricadual que se denota por Q∗∞ y tiene la forma

Q∗∞ =

µI 00T 0

¶La cuádrica absoluta, Q∗∞, es una cónica fija

bajo una transformación proyectiva H, sí y solosí H es una similaridad.El plano en el infinito π∞ es el vector nulo de

Q∗∞.El ángulo entre dos planos viene dado por

cos θ =πT1Q

∗∞π2q¡

πT1Q

∗∞π1

¢ ¡πT2Q

∗∞π2

¢4 Estimación de transforma-

ciones proyectivas

4.1 Algoritmo DLT

Vamos a desarrollar un algoritmo para calcularuna matrizH a partir de un conjunto de 4 puntos2D en correspondencia,x0i = Hxi.Si trabajamos en coordenadas homogéneas,

sabemos que los vectores están multiplicados porun escalar, luego para resolver el anterior sistemanos fijamos en la dirección de los vectores, quetienen que cumplir que x0i ×Hxi = 0.Si desarrollamos este producto y extraemos

las incógnitas (elementos de H), entonces obten-emos el siguiente sistema de ecuaciones⎛⎝ 0T −w0ixi y0ixi

w0ixi 0T −x0ixi−y0ixi x0ixi 0T

⎞⎠⎛⎝ h1

h2

h3

⎞⎠ = 0.

Estas ecuaciones tienen la forma Aih = 0,donde la matriz es de dimensión 3×9 y el vectortiene 9 elementos.Este sistema tiene en realidad dos ecuaciones

linealmente independientes, por lo que cadapunto en correspondencia ofrece dos ecuacionesal sistema. Como la matriz H tiene ocho gra-dos de libertad, entonces necesitamos 4 puntosen correspondencia. Generalmente, los puntos

que se toman para formar el sistema suelen con-tener cierto error, o muchas veces se tienen másde 4 puntos, con lo que es necesario aplicar unmétodo de minimización por mínimos-cuadradosen el que se minimiza kAhk con la restricciónkhk = 1.

Algorithm 8 Algoritmo DLT: Dados n ≥ 4puntos 2D en correspondencia xi ↔ x0i deter-minar la homografía H tal que x0i = Hxi

1. Para cada correspondencia xi ↔ x0i calcu-lar la matriz Ai(solo las dos primeras ecua-ciones)

2. Ensamblar las n 2 × 9 matrices Ai en unasola A de 2n× 9

3. Obtener el SVD de A. El vector singularcorrespondiente al valor singular menor esla solución para h

4. Recolocar los elementos de h para obtenerH

Este algoritmo depende de lo bien condi-cionado que esté la matriz del sistema,A. Si éstaestá mal condicionada, entonces la solución delmismo será errónea. Es por esto que a este algo-ritmo se le suele aplicar una normalización antesde calcular la homografía. Esta normalizaciónconsiste en aplicar un escalado y una traslacióna los puntos en correspondencia antes de formarla matriz y resolver el sistema. El algoritmoquedaría de la siguiente manera:

Algorithm 9 Algoritmo DLT normalizado:Dados n ≥ 4 puntos 2D en correspondenciaxi ↔ x0i determinar la homografía H tal quex0i = Hxi

1. Normalización x: transformar los puntosx a través de una transformación de sim-ilaridad T, que consiste en un escalado ytraslación, de forma que se obtenga un con-junto de puntos x tal que su centroide re-caiga en el origen y su distancia media seade√2.

4 ESTIMACIÓN DE TRANSFORMACIONES PROYECTIVAS 11

2. Normalización x0: realizar la misma op-eración que en el paso anterior para los pun-tos x0. En este paso se obtiene una transfor-mación de similaridad T0 y los puntos trans-formados x0

3. DLT: aplicar el algoritmo anterior a lascorrespondencias xi ↔ x0i para obtener lamatriz H

4. Denormalización: deshacer las trans-formaciones de normalización de formaH = T0−1HT

Esta normalización es necesaria y no se debeconsiderar un paso excepcional.

4.2 Estimación robusta

Cuando queremos realizar algoritmos en los quetodos los pasos, desde la puesta en correspon-dencia, hasta el cálculo de las matrices, se cal-culan de forma totalmente automática, entonceses posible que nos encontremos con outliers. Losoutliers son puntos que se a través de una algo-ritmo se han estimado que están en correspon-dencia pero que realmente no lo están. Esto tieneel inconveniente de que si intentamos solucionarel sistema de ecuaciones con puntos de este estilo,entonces obtendremos soluciones completamenteerróneas.Existen métodos (robustos) que tienen en

cuenta este hecho e intentan identificar los out-liers con el fin de que no se tengan en cuenta. Seclasifican los conjuntos de puntos entre outlierse inliers.

4.2.1 RANSAC

El método RANSAC (RANdom SAmple Consen-sus) es el más conocido y se basa en ir cogiendopequeños conjuntos de puntos (el menor númeropermitido), en calcular el modelo a partir de esospuntos, y en estimar cuántos puntos del conjuntocompleto están dentro de una distancia mínimacon respecto a ese modelo. Este proceso se repitehasta obtener un conjunto de puntos grandes quecumplan con el modelo.

Algorithm 10 Obtención robusta de un modeloasociado a un conjunto de datos, S, con outliers

1. Se selecciona aleatoriamente una muestrade s puntos a partir de S y se calcula elmodelo para este subconjunto

2. Se determina el conjunto de puntos Si queestán dentro de una distancia umbral t delmodelo. El conjunto Si es el consenso de lamuestra y define los inliers de S.

3. Si el tamaño de Si (número de inliers) esmás grande que un umbral T , se recalculael modelo utilizando todos sus puntos y setermina

4. Si el tamaño de Si es más pequeño que elumbral T , se selecciona un nuevo subcon-junto y se repite lo de arriba

5. Después de N intentos el consenso Si mayorse selecciona y el modelo se recalcula uti-lizando todos los puntos en el subconjuntoSi

En este algoritmo tenemos tres umbrales(T,N, t). El parámetro t depende del tipo demodelo que estemos estimando, p.e. si el modeloes una recta, entonces el umbral se compara conla distancia de un punto a la recta d(p, l) < t.Para el parámetro T se suele suponer un porcent-age de puntos que puedan ser outliers. EntoncesT = (1 − ε)n, lo que representa el número depuntos que nosotros consideramos el máximo deinliers.El parámetro N es más complejo puesto que

puede incrementar considerablemente el tiempode ejecución del algoritmo. Por un lado no puedeser muy pequeño porque la muestra final selec-cionada puede no ser la más conveniente, mien-tras que por el otro, si es muy grande el algoritmopuede tardar demasiado tiempo.Se puede adaptar N iterativamente, atendi-

endo a la probabilidad de tener en cuenta a losinliers, de la siguiente manera:

1. N =∞, sample_count = 0

2. Mientras N > sample_count hacer

5 GEOMETRÍA DE UNA VISTA SIMPLE - MODELO DE LA CÁMARA 12

(a) Elegir una muestra y contar el númerode inliers

(b) Colocar ε = 1 −(n_inliers)/(puntos_totales)

(c) Igualar N = log(1−p)/ log(1−(1−ε)s)con p = 0.99

(d) Incrementar sample_count en 1

3. Terminar

4.3 Cálculo automático de una homo-grafía

En el siguiente algoritmo se propone una manerade calcular de forma automática una homografíaentre dos imágenes.

Algorithm 11 Cálculo de una homografía 2Dentre dos imágenes

1. Puntos de interés: se calculan puntos deinterés en ambas imágenes

2. Correspondencias potenciales: se po-nen en correspondencia dichos puntos de in-terés atendiendo a su proximidad y parecido

3. Estimación robusta por RANSAC:repetir para N muestras

(a) Seleccionar aleatoriamente una mues-tra de 4 correspondencias y calcular lahomografía H

(b) Se calcula la distancia d⊥ para cadacorrespondencia potencial

(c) Se calcula el número de inliers consis-tentes con H para el número de corre-spondencias para las cuales d⊥ < t =√5.99σ pixels

Se elige la H con el mayor número de in-liers.

4. Estimación óptima: se recalcula H paratodas las correspondencias clasificadas comoinliers minimizando la función de coste MLutilizando Levenberg-Marquardt

5. Correspondencia guiada: se seleccionannuevos puntos de interés en correspondenciautilizando H

X

xz

x

y

c

Figure 5: El modelo pinhole

5 Geometría de una vista sim-ple - Modelo de la cámara

En esta sección estudiaremos cómo se modelauna cámarar. Básicamente podemos clasificarlas cámaras en dos conjuntos: Cámaras con cen-tro finito, que son aquellas cuyo centro está auna distancia finita del plano proyectivo y que sepuede modelar a través de una matriz de proyec-ción convencional; Cámaras con centro en el in-finito, denominada cámara afín, que son aquellosque proyectan los puntos en el plano proyectivopor medio de líneas paralelas.

5.1 Cámara finita

El modelo pinhole: Los puntos del espaciose proyectan a través de un punto en el planoproyectivo (ver figura 5).

La proyección del espacio R3 al espacio R2 serealiza como (x, y, z)T 7−→ (fx/z, fy/z)T . Elcentro de proyección se denomina el centro decámara La línea perpendicular al plano de laimagen que pasa por el centro de la cámara sedenomina eje o rayo principal y el punto de in-tersección entre éste y el plano de la imagen sellama el punto principal. El plano principal es elque pasa por el centro de la cámara y es paraleloal plano de la imagen.

Utilizando coordenadas homogéneas, laproyección se expresa como


x =

⎛⎝ fxfyz

⎞⎠ =

⎛⎝ f 0f 01 0

⎞⎠⎛⎜⎜⎝

xyz1

⎞⎟⎟⎠= PX

x = PX

También se puede representar comodiag(f, f, 1)[I|0].Si el origen del plano de la imagen está de-

splazado del origen con respecto al centro de lacámara por (px, py), entonces los puntos se trans-forman como (x, y, z)T 7−→ (fx/z + px, fy/z +py)

T , que si lo representamos en coordenadas ho-mogéneas tenemos

⎛⎝ fx+ zpxfy + zpy

z

⎞⎠ =

⎛⎝ f px 0f py 0

1 0

⎞⎠⎛⎜⎜⎝

xyz1

⎞⎟⎟⎠Si llamamos

K =

⎛⎝ f pxf py

1

⎞⎠entonces x = K[I|0]X. Esta matriz K se de-nomina matriz de calibración de la cámara. Siademás suponemos que el eje de coordenadas dela cámara no está situado en el eje de coorde-nadas universal, entonces tenemos que expresarlos puntos 3D de la escena en el eje de referenciade la cámara. Los dos ejes de coordenadas es-tán relacionados a través de una rotación y unatraslación (ver figura 6).La relación entre un punto de la cámara

y el correspondiente universal viene dado porXcam = R(X−C)

Xcam =

µR −RC0 1

¶⎛⎜⎜⎝xyz1

⎞⎟⎟⎠=

µR −RC0 1

¶X

z

x

y

O

X

zcam

xcam

ycam

C

R, t

Figure 6: Relación entre el eje de coordenadasde la cámara y el eje de coordenadas universal

Si ponemos este resultado con el que habíamosobtenido anteriormente, tenemos que P =KR[I|− C]. Esta matriz tiene 9 grados de lib-ertad (3 para K, 3 para R y 3 para C). Losparámetros de K se denominan parámetros in-ternos o intrínsecos de la cámara y los de R yC se llaman parámetros externos o extrínsecos.

cámaras CCD: En este tipo de cámarases posible que los pixels de la imagen no seancuadrados. En este caso, la escala para cada di-rección es distinta. Esto se modela utilizandodos factores mx y my, uno para cada direcciónobteniendo

K =

⎛⎝ αx x0αy y0

1

⎞⎠donde αx = fmx y αy = fmy. representan ladistancia focal de la imagen en términos de ladimensión del pixel. Además, (x0, y0) es el puntoprincipal en términos de la dimensión del pixel,con x0 = mxpx, y0 = mypy. Este tipo de cámarastiene por tanto, 10 grados de libertad.

cámara proyectiva finita: Podemos au-mentar la generalidad de esta transformación si


añadimos otro parámetro en la matriz

K =

⎛⎝ αx s x0αy y0

1

⎞⎠El parámetro s se denomina skew. Gracias

a éste podemos modelar el caso en que los ejesde la cámara no sean perfectamente ortogonales,aunque en la mayoría de los casos éste va a serigual a cero. En este caso tenemos 11 grados delibertad.

5.2 Cámara proyectiva

Podemos representar la matriz de proyeccióncomo P = [M|p4]. SiM no es singular entoncesse trata de una cámara finita.El centro de la cámara cumple la siguiente

relación PC = 0. Si se trata de una cá-mara finita (M no es singular), entonces C =µ−M−1p4

1

¶. Si la cámara es infinita (M es

singular), entonces C =

µd0

¶donde d es el

vector nulo deMd = 0.Los vectores columnas de la matriz

P, (p1,p2,p3) son los puntos en el infinitode los ejes X, Y, Z del sistema de coordenadasuniversal. Estos puntos son la proyección de lasdirecciones de los ejes. el eje X tiene la direcciónD = (1, 0, 0, 0) cuya imagen es p1 = PD.Los vectores fila se corresponden con los planos

del sistema universal

P =

⎛⎝ p11 p12 p13 p14p21 p22 p23 p24p31 p32 p33 p34

⎞⎠ =

⎛⎝ P1T

P2T

P3T

⎞⎠El plano principal es aquel que incluye al cen-

tro de la cámara y es paralelo al plano de la ima-gen. Este contiene al conjunto de puntos X quese proyectan a la línea en el infinito de la imagen,PX =(x, y, 0). Por lo tanto, un punto reside enel plano principal sí y solo sí P3TX =0. O lo quees lo mismo, P3 representa el plano principal.

Los puntos en el plano P1 satisfacen P1TX =0 y se proyectan como PX = (0, y, w)T . El cen-tro de la cámara se encuentra en la intersecciónde los tres planos.

z

y

x

C

P1

P3

P2

x’ y’

Figure 7:

El punto principal es la intersección del ejeprincipal (línea que pasa por C y es perpen-dicular a P3) con el plano de la imagen. Paracalcularlo podemos tomar la normal al planoP3 : (p1, p2, p3). Este vector se puede repre-sentar alternativamente con el punto en el in-finito P3 = (p1, p2, p3, 0)

T , luego proyectandoeste punto a través de la matriz de proyecciónobtenemos

x0 = PP3= [M|p4]

⎛⎜⎜⎝p1p2p30

⎞⎟⎟⎠ =M

⎛⎝ p1p2p3

⎞⎠

y como (p1, p2, p3)T es igual a la tercera fila de

M,m3T , entonces nos queda que x0 =Mm3.

Para encontrar el rayo de proyección que pasapor el centro de la cámara e intersecta al planode la imagen en un punto x podemos utilizar dospuntos. El primero es el centro de la cámara Cy el otro puede ser el dado por P+x, con P+

la pseudoinversa de P, P+ = PT (PPT )−1. Elrayo formado por estos dos puntos sería X(λ) =P+x+ λC.

Si tuviésemos una cámara finita, podríamostomar los puntos C = −M−1p4 y el vector direc-torD = ((M−1x)T , 0), con lo que la recta se rep-

resentaría como X(λ) =µM−1(λx− p4)

1

¶.

6 CÁLCULO DE LA MATRIZ P 15

5.3 Cámaras en el infinito

Son aquellas cuyo centro está en el plano en elinfinito. Esto significa que la matrizM es singu-lar. El centro de la cámara se puede encontrarigual que antes como PC = 0.Las cámaras en el infinito se pueden clasificar

como cámaras afines o no-afines.

5.3.1 Cámara afines

Cámaras afines son aquellas que tiene la tercerafila de la matriz P de la forma (0, 0, 0, 1). Sedenominan afines porque los puntos en el infinitose corresponden con puntos en el infinito en laimagen.

P∞ = KR[I|− C] = K

⎛⎝ r1T −r1T Cr2T −r2T Cr3T −r3T C

⎞⎠La matriz K tiene la forma siguiente

K =

⎛⎝ 110

⎞⎠ de forma que la proyección

en x e y son idénticas a las coordenadas orig-inales del punto en el espacio y la matriz

P =

⎛⎝ 110 1

⎞⎠ y de forma general,

P∞ = KR[I|− C] = K

⎛⎝ r1T −r1TCr2T −r2TC0T d0

⎞⎠

6 Cálculo de la matriz P

6.1 Ecuaciones básicas

Dado un conjunto de puntos 3D puestos en cor-respondencia con puntos en 2D, Xi ↔ xi, elproblema consiste en encontrar la matriz P quecumpla xi = PXi para todos los puntos. De-bido a que la relación es válida para cualquierescalar que multiplique a la relación, entoncesnos interesa que la dirección de los vectores sea

la misma, por lo que podemos utilizar el pro-ducto escalar

xi ×PXi = 0

Nuestras incógnitas son los parámetros de lamatriz P.⎛⎝ 0T −wiX

Ti yiX

Ti

wiXTi 0T −xiXT

i

−yiXTi xiX

Ti 0T

⎞⎠⎛⎝ P1

P2

P3

⎞⎠ = 0

Podemos seleccionar dos de las tres ecuacionesanteriores debido que dependen linealmente en-tre sí. Para cada punto obtenemos dos ecua-ciones con 12 incógnitas cada una. Este sistemase puede resolver como un sistema de ecuacioneslineal de la forma Ap = 0, donde p contienetodos los elementos de la matriz de proyección.Se necesitan en total 11 ecuaciones para de-

terminar los 11 grados de libertad de la matrizP. Por lo tanto necesitamos al menos 5 puntosy medio para poder calcularla.Si los datos de las correspondencias no son

exactos o tenemos más de los puntos necesita-dos (≥ 6), entonces necesitamos aplicar algúnmétodo de minimización. Para esto se minimizala norma de kApk con algún tipo de restricciónde la forma kpk = 1.Es importante realizar la normalización de los

datos antes de calcular la matriz de forma que elsistema esté bien condicionado. Generalmentese suele trasladar los puntos de forma que sucentroide caiga en el centro del sistema de coor-denadas y se escalan de forma que su distanciamedia al centroide diste

√2.

Podemos minimizar el error geométrico dadopor min

P

Pid(xi,PXi)

2. Esta minimización

requiere el uso de técnicas iterativas comoLevenberg-Marquardt.Muchas veces se suele utilizar algún tipo de

patrón, del estilo de la figura 8, para calibraruna cámara.Se seleccionan las esquinas de cada cuadrado y

se ponen en correspondencia con sus posicionesen 3D (conocidas). Para seleccionar las esquinas,generalmente se detectan primero los contornosde la imagen, luego se detectan las líneas, paraluego encontrar las intersecciones de las mismas.

7 GEOMETRÍA EPIPOLAR Y MATRIZ FUNDAMENTAL 16

Figure 8: Calibrador de cuadrados

Algorithm 12 Cálculo de la matriz P a partirde un conjunto de correspondencias, Xi ↔ xi

1. Solución lineal: Se calcula P usando unmétodo lineal

(a) Normalización: Normalizar los pun-tos 2D y 3D de la forma xi= Txi yXi= UXi

(b) DLT: Formar la matriz A de 2n ×12 con todas las correspondencias. Lasolución para Ap = 0 con kpk = 1viene dado por el vector singular uni-tario de A correspondiente a su valorsingular más pequeño.

2. Minimización del error geométrico: Uti-lizando la aproximación lineal calcularminP

Pid(xi, PXi)

2 utilizando un método it-

erativo.

3. Denormalización: La matriz de proyecciónoriginal es igual a P = T−1PU

7 Geometría epipolar y matrizfundamental

7.1 Geometría epipolar

Epipolo: El punto de intersección (e) de la líneaque une los dos centros de cámara con el planode la imagen.

c´ c e´ e

l´ l

π

Figure 9:

c´ c e´ e

l´ l

π

X

x’x

Figure 10:

Plano epipolar: Plano que contiene a la líneabase (línea que une los dos centros de cámara ycontiene a los epipolos). Existe una familia deplanos epipolares (pencil of planes).Línea epipolar: La intersección de un plano

epipolar con el plano de la imagen.

7.2 La matriz fundamental

Es la representación algebraica de la geometríaepipolar. Para cada punto en una imagen existeuna línea en la otra imagen en la que está inclu-ido el punto en correspondencia. Luego existeuna correspondencia entre un punto de una ima-gen y una línea en la otra. Este correspondenciase representa a través de una matriz F, la matrizfundamental, de dimensión 3× 3.

7.2.1 Deducción geométrica

La línea epipolar que pasa por x0 y e0 se puedeescribir como l0 = x0 × e0 = [e0]× x0. Como x0 =

7 GEOMETRÍA EPIPOLAR Y MATRIZ FUNDAMENTAL 17

Hπx, entonces l0 = [e0]×Hπx = Fx, por lo queF = [e0]×Hπ.La matriz fundamental tiene rango 2 ya que

[e0]× tiene rango 2 y Hπ rango 3.

7.2.2 Deducción algebraica

Otra forma de deducir la matriz es a través de lalínea que une el punto de la imagen con el punto3D

X(λ) = P+x+ λC

l0 = P0C×P0P+x =£e0¤×P

0P+x = Fx

F =£e0¤×P

0P+

Luego Hπ = P0P+

7.2.3 Condición de correspondencia

Para cualquier par de puntos en correspondenciaentre las dos imágenes, la matriz fundamentalcumple

x0TFx = 0

Podemos, por tanto, calcular la matriz F apartir de puntos en correspondencia entre lasimágenes.

7.2.4 Propiedades de la matriz funda-mental

Traspuesta: Si F es la matriz fundamental aso-ciada al par de cámaras (P,P0), entonces FT esla asociada a (P0,P).Líneas epipolares: La línea epipolar correspon-

diente a un punto x es l0 = Fx. La línea epipolarpara un punto x0 es l = FTx0.Epipolos: Para cualquier punto x que no sea el

epipolo (e), la línea epipolar l0 = Fx contiene elepipolo e0. Esto satisface e0TFx =

¡e0TF

¢x =0

para cualquier x, lo que implica que e0TF =0 y,análogamente, Fe =0.Grados de libertad: F tiene 7 grados de liber-

tad ya que detF = 0.F es una correlación.

c´ c e´ e

Figure 11: Lineas epipolares

7.2.5 Homografía de la línea epipolar

El conjunto de líneas epipolares intersectan en elepipolo (ver figura 11).Como se puede ver en la figura, las líneas

epipolar están relacionadas a través de una trans-formación proyectiva, con lo que existe una ho-mografía entre las líneas eipolares de una imageny de la otra. Esta homografía tiene 3 grados delibertad. Los grados de libertad de la matriz fun-damental se pueden contar como 2 para e otros2 para e0 y 3 para la homografía.Si suponemos que hay dos líneas epipolares

correspondientes, l y l0, y k es una líneacualquiera que no pasa por e, entonces l y l0 estánrelacionadas por l0 = F [k]× l o, simétricamente,por l = FT [k0]× l

0.Una elección conveniente para k es la línea e,

ya que kTe = eTe 6= 0, por lo que no pasa porel epipolo. La homografía de la línea epipolar sepuede escribir como

l0 = F [e]× l l = FT£e0¤× l

0

7.3 Matrices fundamentales espe-ciales

7.3.1 Traslación pura

Cuando los parámetros intrínsecos de las cá-maras son iguales y una de las cámaras estádesplazada con respecto a la otra por un vec-tor t sin rotación. Podemos suponer que lasdos cámaras vienen dadas por P = K[I|0] yP0=K[I|t]. La matriz fundamental quedaríacomo

F =£e0¤×KK

−1 =£e0¤×

8 RECONSTRUCCIÓN 3D DE CÁMARAS 18

Si el desplazamiento de la segunda cámara serealiza en la dirección del eje x, entonces e0 =(1, 0, 0)T , así que

F =

⎛⎝ 0 0 00 0 −10 1 0

⎞⎠ .

La relación entre puntos en correspondencia sereduce a y = y0, o lo que es lo mismo, las líneasepipolares son horizontales y paralelas al eje x.

7.4 Cálculo de las matrices de las cá-maras

Una de las propiedades más significantes de lamatriz F es que nos permite calcular las matricesde las cámaras.Si H es una matriz de 4×4 que representa

una transformación proyectiva del espacio 3D,entonces las matrices fundamentales que corre-sponden al par de matrices de cámaras (P,P0) y(PH,P0H) son la misma. De esta forma, aunquelas matrices de dos cámaras identifican unívoca-mente una matriz fundamental, lo inverso no escierto. Una matriz fundamental define un con-junto de matrices de cámaras que están rela-cionadas por una transformación proyectiva.Forma canónica de las matrices de las cámaras:

Podemos suponer que una de las cámaras estánormalizada en el sentido de que sus parámet-ros intrínsecos son iguales a la unidad y que estásituada en el origen de coordenadas apuntandoen la dirección del eje z. La matriz para esta cá-mara es de la forma P = [I|0]. Si representamosla otra matriz de la forma P0 = [M|m], entoncesla matriz fundamental correspondiente a ellas esF = [m]×M.Se pueden seleccionar las matrices de cámara

a partir de la matriz fundamental de la siguienteforma: P = [I|0] y P0 = [[e0]×F|e

0].La fórmula general para un para de matrices

de cámara canónicas viene dada por:

P = [I|0] P0 = [[e0]×F+ e0vT |λe0].

7.5 Matriz esencial

La matriz esencial es la especialización de lamatriz fundamental al caso en que las coorde-

nadas de la imagen están normalizadas. Co-ordenadas normalizadas significa que la matrizK es igual a la identidad. Un matriz de cá-mara se puede descomponer como P = K[R|t].Si conocemos la matriz de calibración los pun-tos proyectados, x = PX = K[R|t]X, se puedenrepresentar como x = K−1x, con lo que tenemosx = [R|t]X. Estos puntos están en coordenadasnormalizadas. Si consideramos el par de matri-ces P = [I|0] y P0 = [R|t], la matriz fundamen-tal que se obtiene se denomina esencial y tienela forma

E = [t]×R

Se cumple la relación x0TEx = 0. Si susti-tuimos por los puntos originales, obtenemosx0T

¡K0−TEK−1

¢x = 0, con lo que la relación

con la matriz fundamental es

E =K0TFK.

La matriz esencial tiene 5 grados de libertad

8 Reconstrucción 3D de cá-maras

8.1 Método de reconstrucción

Una forma de reconstruir una escena a partir dedos vistas se puede realizar siguiendo los pasos

1. Calcular la matriz fundamental a partir depuntos en correspondencia

2. Calcular las matrices de las cámaras a partirde la matriz fundamental

3. Para cada par de puntos en correspondenciase calcula el punto en el espacio

8.2 Ambigüedad en la reconstrucción

A partir de dos vistas no podemos situar la posi-ción y orientación de la escena con respecto a uneje de coordenadas universal. Esto significa quela reconstrucción está supeditada a una transfor-mación Euclídea desconocida.Tampoco es posible determinar el escalado

general de la escena. Para cámaras calibradases posible realizar la reconstrucción hasta una

8 RECONSTRUCCIÓN 3D DE CÁMARAS 19

transformación de similaridad, donde no cono-cemos ni la rotación, ni el desplazamiento, ni elescalado de la escena.Si las cámaras no están calibradas, entonces

la ambigüedad en la reconstrucción sería posiblehasta una transformación proyectiva. Si las cá-maras se relacionan a través de un movimientotraslacional, entonces la ambigüedad es hastauna transformación afín y si no se conocen lasdistancias focales de las cámaras, entonces seríahasta una transformación de similaridad.Dependiendo de qué tipo de ambigüedad se

trate, hablamos de reconstrucción proyectiva, re-construcción afín, reconstrucción de similaridady reconstrucción Euclídea.

8.3 Teorema de la reconstrucciónproyectiva

Theorem 13 Suponemos que tenemos un con-junto de correspondencias xi ←→ x0i entrepuntos de dos imágenes y que determinamosunívocamente la matriz fundamental F, en-tonces para cualquier par de reconstrucciones(P1,P01, X1i) y (P2,P02, X2i) existe una ma-triz no singular H que cumple que P2 =P1H

−1,P02 = P01H

−1 y X2i = HX1i.

Este teorema es importante porque es la basepara realizar una reconstrucción proyectiva sóloa partir de un conjunto de puntos en correspon-dencia. Este tipo de reconstrucción es suficientepara realizar distintos tipos de aplicaciones comolocalizar la intersección entre líneas y planos.Además también es interesante porque a partirde ésta se pueden obtener la reconstrucción afíny posteriormente la métrica.

8.4 Reconstrucción estratificada

Esta reconstrucción consiste en primero estimaruna reconstrucción proyectiva, luego refinarla auna transformación afín y posteriormente a unamétrica.Para refinar la reconstrucción proyectiva a

una afín, tenemos que identificar el plano enel infinito, π∞. En una transformación afín,el plano en el infinito se mantiene invariante.Las coordenadas del plano en el infinito son

π∞ = (0, 0, 0, 1)T , así que lo que tenemos quehacer es encontrar una transformación proyec-tiva que me transforme el plano en el infinito de-tectado al plano con las coordenadas anteriores,o lo que es lo mismo, encontrar un H tal queH−Tπ =(0, 0, 0, 1)T . Esta transformación vienedada por

H =

µI|0πT

¶.

Con una reconstrucción afín podemos realizarcálculos como el punto medio entre dos puntos,el centroide para un conjunto de estos u otroscálculos que tengan que ver con los invariantespara este tipo de transformaciones.

¿Cómo identificar el plano en el infinito? Paradefinir el plano en el infinito podemos utilizartres puntos en el infinito. Si el desplazamientoentre las cámaras es una traslación pura, en-tonces los puntos en el infinito se corresponderáncon las mismas coordenadas en las dos imágenes,luego bastaría con seleccionar tres coordenadasiguales en las dos imágenes, obteners los puntosXi en la escena y obtener a partir de ellos elplano en el infinito.

También se puede identificar el plano en el in-finito a través de líneas paralelas en la escena.Si podemos reconocer en la imagen las líneasque son paralelas originalmente en la escena, en-tonces podemos calcular los puntos de fuga comola intersección de dichas líneas en la imagen. Siconseguimos tres conjuntos de líneas paralelasdistintos, entonces podremos obtener tres pun-tos de fuga (puntos en el infinito) y, por tanto,obtener el plano en el infinito.

Otra forma de indentificar el plano en el in-finito es a través de ratios de distancia en unalínea. Si conocemos dos intervalos en una líneacon un ratio de distancia conocido, entonces elpunto en el infinito para esa línea se puede de-terminar.

Para refinar a una reconstrucción métrica, ten-emos que identificar la cónica absoluta, Ω∞.

9 CÁLCULO DE LA MATRIZ F 20

9 Cálculo de la matriz F

9.1 Ecuaciones básicas

La matriz fundamental se define a partir de laecuación x0TFx = 0. Si tenemos un conjuntomínimo de puntos en correspondencia (al menos7), entonces podemos calcular la matriz. Cadapar de puntos, x = (x, y, 1) y x0 = (x0, y0, 1) dalugar a una ecuación lineal. De esta forma, sitomamos un conjunto de puntos y representa-mos en un vector f los elementos de la matrizF, entonces tendremos que resolver un sistemade la forma Af = 0. Si los datos no son exac-tos o tenemos más correspondencias de las quenecesitamos, se busca una solución por mínimoscuadrados. Esta solución es el vector singularque se corresponde con el valor singular de Amás pequeño, esto es, la última columna de Ven el SVD A = UDVT .La matriz F tiene rango 2, con lo que hay

que forzar que la solución obtenida por míni-mos cuadrados se convierta en una matriz cuyodetF = 0. Para esto, lo que se suele hacer esbuscar una matriz F0 que minimice kF− F0k talque detF0 = 0. Esto se puede calcular de nuevoutilizando el SVD.

9.2 El algoritmo de 8 puntos normal-izados

Algorithm 14 Algoritmo de los 8 puntosDados 8 ó más puntos en correspondencia

xi ←→ x0i calcular la matriz F tal quex0Ti Fxi = 0.

1. Normalización: Se transforman las coorde-nadas de imagen xi = Txi, x0i = Tx

0i

2. Encontrar la matriz fundamental:

(a) Solución lineal: Se calcula la matriz Fa partir del SVD de la matriz A com-puesta por las correspondencias de lospuntos xi ←→ x0i.

(b) Forzar restricción: Reemplazar F porF0 tal que det F0 = 0 utilizando el SVD.

3. Denormalizar: La matriz fundamental orig-inal es F = T0T F0T para los puntos en cor-respondencia originales.

9.3 Distancia geométrica

El algoritmo de los 8 puntos normalizados es sim-ple y rápido, pero tiene el inconveniente que noes óptimo en el sentido de que no le da igual im-portancia a todas las entradas de F. Otra formade calcular la matriz fundamental es a través demétodos no lineales.La estimación del Máximo Parecido (Maxi-

mum Likelihood) de la matriz fundamental de-pende de la asunción de un modelo de error.Podemos suponer que los puntos en correspon-dencia contienen ruido Gausiano. En este caso,la estimación ML es la que minimiza la distanciageométrica X

i

d (xi, xi) + d¡x0i, x

0i

¢donde xi ↔ x0i son los puntos que se han medio yxi, x

0i son los que se suponen las verdaderas cor-

respondencias que satisfacen x0Ti Fxi = 0. Paraminimizar este funcional, podemos definir dosmatrices P = [I|0] y P0= [M|t]. Se obtienen lospuntos 3D, Xi, asociados a las correspondenciasde forma que xi = PXi, x

0i = P0Xi. Luego se

varía el valor de P0 y deXi para minimizar la ex-presión. La matriz fundamental se obtiene comoF = [t]×M. Para encontrar el mínimo se puedeutilizar el algoritmo de Levenberg-Marquardt.Los métodos de minimización iterativos necesi-tan por lo general una aproximación inicial, conlo que podemos utilizar el resultado del algoritmode 8 puntos como estimación inicial.

Algorithm 15 Algoritmo de minimización delerror de reproyección

1. Se calcula un estimación lineal inicial de F(algoritmo de los 8 puntos)

2. Se calculan las correspondencias estimadasxi, x0i :

(a) Se eligen las matrices de cámaraP = [I|0] y P0= [[e0]×F|e0] donde e0 seobtiene de F

10 CÁLCULO DE LA ESTRUCTURA 21

(b) A partir de las correspondencias xi ↔x0i y de F se obtienen los puntos 3DXi

(c) Las correspondencias consistentes conF se obtienen como xi = PXi, x

0i =

P0Xi

3. Se minimiza la función costeXi

d (xi, xi) + d¡x0i, x

0i

¢sobre F y Xi utilizando un método como elde Levenberg-Marquardt.

Se necesita parametrizar la matriz fundamen-tal para forzar que su rango sea igual a 2.Una forma de parametrizarla es F = [t]×M ya

que [t]× es singular y hace que F también lo sea.Otra forma de parametrizarla es especificandodos columnas y representar la tercera como unacombinación lineal de las dos primeras

F =

⎛⎝ a b αa+ βbc d αc+ βde f αe+ βf

⎞⎠9.4 Cálculo automático de F

Es interesante poder calcular la matriz funda-mental únicamente a partir de dos imágenes.Para esto se utiliza un algoritmo de estimaciónrobusta basado en el RANSAC (RANdom SAm-ple Consensus).

Algorithm 16 Cálculo de la matriz fundamen-tal entre dos imágenes

1. Puntos de interés: Se calculan puntos en lasdos imágenes (método de Harris)

2. Correspondencias potenciales: Se encuen-tran posibles correspondencias entre las dosimágenes

3. RANSAC: Para N muestras se repite

(a) Se seleccionan aleatoriamente 7 corre-spondencias y se calcula la matriz fun-damental

(b) Se calcula la distancia d⊥ para cadacorrespondencia potencial

(c) Se calculan el número de inliers con-sistentes con F tal que d⊥ < t

(d) Si existen tres soluciones para F se se-lecciona aquella con mayor número deinliers

Se selecciona la F con mayor número de in-liers

4. Estimación no-lineal: Se recalcula F a par-tir de todas las correspondencias poten-ciales clasificadas como inliers, utilizandoLevenberg-Marquardt

5. Correspondencia guiada: Se determinanmás puntos en correspondencia utilizandoahora la matriz F

10 Cálculo de la estructura

Si tenemos las matrices de las cámaras y un con-junto de puntos en correspondencia, entonces esposible obtener los puntos 3D originales. Unode los problemas con los que nos econtramos esque los rayos que unen las correspondencias conlos centros de las cámaras generalmente no inter-sectan en un punto, sino que determinan rectasconvergentes que no se llegan a tocar. Esto es asídebido a que la precisión de las imágenes es finitay a que las correspondencias no son exactas.

10.1 Métodos lineales de triangu-lación

El método más simple para reconstruir un puntoes el de la triangulación. Este consiste en deter-minar los dos rayos que unen cada corresponden-cia con el foco de la cámara y después encontrarel punto cuya distancia a dichas rectas sea mín-ima.El método lineal es análogo al método DLT

para el cálculo de las homografías. Las proyec-ciones x = PX y x0= PX se pueden combi-nar de forma que obtengamos un sistema de laforma AX = 0. Para eliminar el factor de es-cala utilizamos el producto escalar de la formax×PX = 0 y obtenemos lo siguiente

10 CÁLCULO DE LA ESTRUCTURA 22

x¡p3TX

¢−¡p1TX

¢= 0

y¡p3TX

¢−¡p2TX

¢= 0

x¡p2TX

¢− y

¡p1TX

¢= 0.

Estas ecuaciones son lineales en los compo-nentes de X y una de ellas depende linealmentede las otras dos. Si introducimos la informacióndel otro punto, entonces podemos obtener la ma-triz

A =

⎛⎜⎜⎝xp3T − p1Typ3T − p2Tx0p03T − p01Ty0p03T − p02T

⎞⎟⎟⎠Para resolver el sistema podemos utilizar el

DLT.

10.2 Función de coste de error ge-ométrico

Este método consiste en encontrar las verdaderascorrespondencias x y x0 cumpliendo la restricciónepipolar de la forma

C(x,x0) = d(x, x)2 + d(x0, x0)2 restringido a

x0TFx = 0.

Esto es equivalente a minimizar el error dereproyección de los puntos 3D estimados. Sisuponemos un error Gaussiano, entonces los pun-tos x y x0 son las Estimaciones de Máximo Pare-cido (MLE) de las correspondencias entre lasimágenes.

10.3 Solución óptima

Este método encuentra el mínimo global de lafunción de coste anterior utilizando un algoritmono lineal.F(1, 0, f)T = (1, 0, f 0)F = 0

F =

⎛⎝ ff 0d −f 0c −f 0d−fb a b−fd c d

⎞⎠Suponemos que la línea epipolar pasa por

el punto (0, t, 1)T y por el epipolo (1, 0, f)T .Esta línea se representa como l(t) = (0, t, 1) ×

(1, 0, f) = (tf, 1,−t). La distancia del origen aesta recta es

d2(0, l(t)) =t2

1 + (tf)2

La línea epipolar en la otra imagen es l0(t) =F(0, t, 1)T = (−f 0(ct+ d), at+ b, ct+ d)T . Ladistancia del origen a esta línea es

d2(0, l(t)) =(ct+ d)2

(at+ b)2 + f 02 (ct+ d)2

s(t) =t2

1 + f2t2+

(ct+ d)2

(at+ b)2 + f 02 (ct+ d)2

s0(t) =2t

(1 + f2t2)2− 2 (ad− bc) (at+ b) (ct+ d)³

(at+ b)2 + f 02 (ct+ d)2´2

g(t) = t³(at+ b)2 + f 02 (ct+ d)2

´2−¡1 + f2t2

¢2(ad− bc) (at+ b) (ct+ d)

= 0

Algorithm 17 Reconstrucción óptima

1. Se obtienen las matrices de traslación

T =

⎛⎝ 1 −x1 −y

1

⎞⎠ y T0 =

⎛⎝ 1 x1 y1

⎞⎠para trasladar los puntos al origen

2. Se reemplaza la matriz F por T0−TFT−1

3. Se calculan los epipolos como Fe = 0 ye0TF = 0. Se normalizan de forma quee21 + e22 = 1

4. Se crean las matrices de rotación

R =

⎛⎝ e1 e2−e2 e1

1

⎞⎠ y R0 =

⎛⎝ e01 e02−e02 e01

1

⎞⎠de forma que Re =(1, 0, e3)

T y R0e0

=(1, 0, e03)T

11 GEOMETRÍA EPIPOLAR AFÍN 23

5. Se reemplaza la matriz F por R0FRT

6. Se igualan f = e3, f0 = e03, a = F22, b =

F23, c = F32 y d = F33

7. Se forma el polinomio g(t) y se buscan las 6raíces

8. Se evalúa la función de coste s(t) en lasraíces y para el valor de t = ∞. Se selec-ciona el valor de t que dé el menor valor

9. Se obtienen las dos líneas l = (tf, 1,−t) yl0 para el valor del mínimo y se encuentranlos valores x y x0 sobre dichas líneas que es-tén más próximos al origen. Para una líneacualquiera (λ, µ, ν) el punto más próximo alorigen viene dado por (−λν,−µν, λ2 + µ2)

10. Se deshacen las transformaciones anteri-ores sustituyecto x por T−1RT x y x0 porT0−1R0T x

11. El punto 3D X se calcula a través delmétodo de triangulación homogéneo

11 Geometría epipolar afín

Cuando trabajamos con cámaras afines, la ge-ometría epipolar se simplifica considerablemente,permitiendo realizar ciertos algoritmos de formamás sencilla. Las cámaras afines tienen su centroen el infinito y la proyección se realiza perpen-dicularmente al plano de la imagen.Para este tipo de cámaras, las líneas epipolares

son paralelas, así como los planos epipolares. Losepipolos también se encuentran en el infinito.

11.1 La matriz F afín

La matriz fundamental se obtiene a partir de lasmatrices de las cámaras que tienen la tercera filaigual a (0, 0, 0, 1). En particular, la matriz FA

tiene la forma

FA =

⎛⎝ 0 0 a0 0 bc d e

⎞⎠ .

Las correspondencias entre las imágenes vienedado por una transformación afín de forma quex0= HAx.

La línea epipolar se obtiene a través de x0 y elepipolo e0, l0 = e0 ×HAx = FAx, así que

FA = [e0]×HA =

⎛⎝ 0 0 ∗0 0 ∗∗ ∗ 0

⎞⎠⎛⎝ ∗ ∗ ∗∗ ∗ ∗0 0 1

⎞⎠=

⎛⎝ 0 0 ∗0 0 ∗∗ ∗ ∗

⎞⎠ .

También podemos deducir la matriz alge-braicamente sabiendo que = [e0]×P0P+.La matriz fundamental afín tiene, por tanto,

4 grados de libertad. El epipolo de la primeraimagen se puede obtener como FAe =0, por loque e = (−d, c, 0) y e0 = (−b, a, 0).Las líneas epipolares son paralelas. Esto se

puede ver como l0 = FAx =(a, b, cx + dy + e)T .Aquí todas las líneas epipolares tienen la mismadirección dada por (a, b).Las correspondencias entre puntos se estable-

cen como x0TFAx =0, ax0+by0+cx+dy+e = 0.Las matrices de las cámaras canónicas también

tienen una forma bastante simple:

PA =

⎛⎝ 1 0 0 00 1 0 00 0 0 1

⎞⎠ P0A =

µM2×3

0 0 0

¯t1

¶con a = m23, b = −m13, c = m13m21 −m11m23, d = m13m22 − m12m23 y e = m13t2 −m23t1.

11.2 Cálculo de FA a partir de puntosen correspondencia

Algorithm 18 Cálculo del MLE de FA a par-tir de un conjunto de n ≥ 4 correspondencias.Representamos cada correspondencia como Xi =(x0i, y

0i, xi, yi)

1. Calcular el centroide X = 1N

NPiXi y centrar

los puntos ∆Xi = Xi − X

2. Calcular la matriz A de n×4 con ∆Xi comofilas

3. N = (a, b, c, d)T es el vector singular corre-spondiente al valor singular más pequeño deA y e = −NT X.

REFERENCES 24

References

[1] Richard Hartley y Andrew Zisserman, Mul-tiple View Geometry in Computer Vision,Cambridge University Press, 2000

[2] Olivier Faugeras, Three-Dimensional Com-puter Vision, a Geometric Viewpoint , MITPress, 1993

[3] Olivier Faugeras, Quang-Tuan Luong andTheo Papadopoulo, The Geometry of Mul-tiple Images, MIT Press, 2001

visión tridimensional - ami research...

Documents