Embed Size (px)
DESCRIPTION
Work for getting the Licenciada en Matemáticas, Especialidad en Estadística y Computación at Universidad de Cantabria
Citation preview
UNIVERSIDAD DE CANTABRIAFACULTAD DE CIENCIASDPTO. DE MATEMÁTICAS, ESTADÍSTICA Y COMPUTACIÓN
Fundamentos matemáticos de la Visión porComputador.
TRABAJO DIRIGIDO EN “ESTADÍSTICA Y COMPUTACIÓN”REALIZADO POR GEMA R. QUINTANA PORTILLA
BAJO LA DIRECCIÓN DEL PROF. D. FERNANDO ETAYO GORDEJUELA.
Índice general
Índice general 1
Índice de figuras 3
1. Introducción. 41.1. Comentarios generales. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41.2. Descripción de la memoria. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41.3. Agradecimientos. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2. Modelización geométrica. 82.1. Introducción. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82.2. Lentes. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102.3. Cámara pinhole. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112.4. Modelo geométrico del proceso de formación de la imagen. . . . . . . . . . . . . . . . . 12
2.4.1. Cámara perspectiva ideal. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122.4.2. Cámara con parámetros intrínsecos. . . . . . . . . . . . . . . . . . . . . . . . . 142.4.3. Distorsión radial. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.5. Notas. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
3. Geometría epipolar. 193.1. Introducción. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 193.2. La restricción epipolar y la matriz esencial. . . . . . . . . . . . . . . . . . . . . . . . . 203.3. Propiedades de la matriz esencial. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
4. Reconstrucción a partir de dos vistas calibradas. 254.1. Introducción. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 254.2. El algoritmo lineal de los ocho puntos: justificación teórica. . . . . . . . . . . . . . . . . 254.3. Algoritmo lineal de los ocho puntos. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 294.4. Reconstrucción “euclídea”. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 314.5. Implementación en Matlab. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
5. Apéndice. 365.1. CCD . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 365.2. Correspondencia y emparejamiento de puntos. . . . . . . . . . . . . . . . . . . . . . . . 365.3. Vectores y matrices. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 385.4. Movimientos del sólido rígido. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 395.5. Grupos y álgebras de Lie. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
ÍNDICE GENERAL 2
Bibliografía 43
Índice de figuras
1.1. Durero utilizando una proyección cónica. . . . . . . . . . . . . . . . . . . . . . . . . . 61.2. Modelo clásico de cámara pinhole. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.1. Representaciones de una imagen. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92.2. Modelo de lente delgada. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102.3. Cámara pinhole. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112.4. Modelización de una cámara pinhole. . . . . . . . . . . . . . . . . . . . . . . . . . . . 122.5. Transformación de coordenadas métricas a coordenadas en píxeles. . . . . . . . . . . . . 142.6. Transformación de coordenadas 3-D a coordenadas en píxeles. . . . . . . . . . . . . . . 152.7. Distorsión radial. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
3.1. Geometría epipolar. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 203.2. Restricción epipolar. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
4.1. Proyección sobre E . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 264.2. Recuperación de p a partir de la matriz esencial. . . . . . . . . . . . . . . . . . . . . . . 284.3. Puntos en correspondencia. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
5.1. Sensor CCD. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 375.2. Correspondencia entre puntos. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 385.3. Movimiento del sólido rígido. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 395.4. Movimiento del sólido rígido entre C y W . . . . . . . . . . . . . . . . . . . . . . . . . 40
Capítulo 1
Introducción.
1.1. Comentarios generales.
El sentido de la visión es quizá el más importante de los sentidos humanos. Es el que nos proporcionade manera instantánea la información sobre el mundo tridimensional que nos rodea. Mundo que está encontinuo cambio el cual asumimos de manera inmediata gracias a un complicado proceso del que apenassomos conscientes: el proceso visual.
Lo que busca la Visión por Computador es imitar este hecho. Lograr que los ordenadores sean capa-ces de entender e interpretar información a partir de fotografías o secuencias de vídeo, para una posteriortoma de decisiones.
Esta disciplina surgió a mediados del siglo XX y ha experimentado grandes avances en los últimostiempos, gracias al crecimiento exponencial de la velocidad de los procesadores y al aumento de lacapacidad de memoria de los ordenadores. Es un campo de trabajo muy amplio y en auge actualmentepor la gran diversidad de aplicaciones que posee: robótica, medicina, tecnología espacial, industria, etc.
Precisamente por todo ello este área está desarrollada, sobre todo, por ingenieros e informáticos, porlo que muchas veces las matemáticas en las que se basa, esto es, la Geometría Proyectiva, la Estadística,la Optimización, el Álgebra Lineal... son usadas como meras herramientas de cálculo, perdiendo partede ese rigor que es necesario para que, a los que nos dedicamos a ellas, nos resulten consistentes.
El objetivo de este trabajo es precisamente estudiar las matemáticas que subyacen en el problemade reconstruir un objeto a partir de dos vistas calibradas1 del mismo. Para ello primero realizamos unamodelización geométrica del problema y después ponemos el énfasis en los algoritmos empleados pararesolverlo. A la hora de hacer esto la principal dificultad con el que nos hemos encontrado ha sido que lostextos sobre la materia en cuestión, en su mayoría, están escritos con rigor deficiente en las definicionesy demostraciones, por lo que la primera tarea que hemos llevado a cabo ha sido la traducción al lenguajematemático y la formalización de los conceptos.
El nivel de conocimientos del que partimos a la hora de redactar el trabajo es el de la asignatura deGeometría Proyectiva de tercer curso de la Licenciatura en Matemáticas de la Universidad de Cantabria.Todo lo que se haya podido emplear que exceda este nivel es definido en el mismo.
1.2. Descripción de la memoria.
El trabajo se divide en cinco capítulos. El primero es una mera introducción al tema y el quinto, unapéndice en el que recogemos algunas observaciones y definiciones no incluidas en el texto, para evitaruna excesiva sobrecarga en su lectura.
1Más adelante explicaremos detalladamente en qué consiste esto.
1.3 Agradecimientos. 5
En el segundo, comenzamos explicando lo que es una imagen para un ordenador, que no es otracosa que una aplicación lineal asignando a cada punto un valor de gris. A continuación se realiza lamodelización geométrica del proceso de formación de la imagen. Esto es lo que va a sustentar todos losalgoritmos, lo que da solidez a la Visión por Computador y lo que nos va a permitir formalizar el hechoque queremos estudiar. Se emplea el modelo más sencillo de cámara: la cámara pinhole que básicamentees una proyección cónica, de ahí que la Geometría Proyectiva desempeñe un papel fundamental en elcampo de la visión por computador. Dicho papel se pone de manifiesto de forma clara si pensamos en loque es una fotografía, ya que una sola imagen no preserva ni ángulos, ni longitudes, ni paralelismo, esdecir, esencialmente tiene una naturaleza proyectiva.
En el capítulo tercero estudiamos la geometría de dos vistas, llamada también geometría epipolar.Conociendo dos vistas de un mismo objeto se pueden realizar dos operaciones básicas en Visión porComputador: (1) calibrar las cámaras con las que se han tomado las imágenes (lo que significa podercalcular sus parámetros intrínsecos, como la distancia focal, factor de escala a la hora del pixelado de laimagen, etc.), y (2) realizar la reconstrucción euclídea del objeto, es decir, hallar sus verdaderas medidas.La realización de estas dos tareas se basa en el cálculo de la matriz esencial (en el caso de vistas cali-bradas) y la matriz fundamental (si no lo están). Matrices que relacionan los parámetros de las cámarasy el movimiento que ha experimentado la cámara entre la toma de una vista y la otra. En nuestro caso,suponemos las vistas calibradas, toda la geometría epipolar quedará codificada por la matriz esencial.
Una vez sentadas las bases geométricas, nos centramos en lo principal: la reconstrucción de un objetoa partir de dos vistas calibradas. Es decir, poseemos toda la información sobre los parámetros intrínsecosde la cámara y lo que tenemos que estimar es las matrices de rotación y traslación que describen elmovimiento de la cámara que ha tenido lugar entre las tomas de la primera imagen y la segunda. Unavez que lo hemos conseguido, el llegar a la matriz esencial es un sencillo cálculo, cuya justificación, sinembargo, requiere unos cuantos teoremas descritos en este trabajo. Para ello utilizamos el algoritmo delos ocho puntos que es el que permite recuperar la matriz esencial a partir de ocho correspondenciasentre puntos de ambas imágenes. No nos conformamos únicamente con su implementación sino quejustificamos todos sus pasos, por ejemplo respondiendo a preguntas como ¿por qué ocho puntos?, ¿y porqué hay otro que usa siete puntos?, etc. Preguntas que no son respondidas en los textos que existen sobreel tema, la mayoría de los cuales consisten en una mera concatenación de algorítmos y métodos que sepueden aplicar y que casi siempre funcionan salvo en situaciones “atípicas” que no se concretan muybien porque no existe la definición rigurosa de “situación buena”.
Para la implementación de los algoritmos hemos empleado Matlab ya que este mismo software estápreparado para el tratamiento de imágenes y es el más utilizado en las asignaturas de visión por compu-tador que se imparten en cursos de doctorado de la licenciatura de Matemáticas de muchas universidades,así como en estudios de Informática y de Ingeniería.
Por último, cabe señalar que al realizar este trabajo nos hemos dado cuenta de cuán estrechamenteligadas están distintas áreas de la matemática y cómo en un sencillo problema pueden aparecer campostan dispares como la Topología Diferencial y la Estadística, por ejemplo. Así que, a modo de conclusiónpodemos afirmar:
“Todo lo que se estudia en la Licenciatura sí es importante, es más, nunca sabes cuando lo vas anecesitar.”
1.3. Agradecimientos.
En primer lugar, mencionar a Laureano González Vega quien nos acompañó en los comienzos deeste proyecto y ayudó a sentar sus bases.
En segundo lugar, a la Universidad de Cantabria por la concesión de una beca de Iniciación a la
1.3 Agradecimientos. 6
Figura 1.1: Durero utilizando una proyección cónica (1525). Los pintores del Renacimiento desarrolla-ron métodos sistemáticos, como el que se aprecia en la figura, para determinar la proyección perspectivade paisajes tridimensionales.
Figura 1.2: Modelo clásico de cámara pinhole.
1.3 Agradecimientos. 7
Investigación dentro de la cual se ha desarrollado este trabajo. Muchas gracias por permitirme disfrutarde una experiencia tan formativa.
Por último, pero no menos importante, dedicar un especial recuerdo a mi director Fernando Etayo,por la gran cantidad de horas y atención que me ha dedicado, y a mi tutor Juan Manuel de Olazábal,quien me prestó parte de su amplia experiencia en redacción.
Capítulo 2
Modelización geométrica.
2.1. Introducción.
Pretendemos buscar un modelo matemático para el proceso de formación de la imagen. La visiónes el problema inverso al proceso de formación de la imagen: la última estudia el paso de objetos aimágenes; mientras que la primera, cómo usar las imágenes para obtener una descripción tridimensionalde los objetos. Por ello, el diseño de algoritmos para visión requiere de un previo desarrollo de un modeloútil del proceso de formación de la imagen. Con útil nos referimos a que sea fácilmente invertible.
Emplearemos un modelo clásico de cámara, la cámara pinhole, cuyo estudio y uso se remonta alRenacimiento1. A pesar de su antigüedad, es una aproximación muy cercana a los fotosensores CCD2
actuales. Responde perfectamente a nuestros objetivos, aunque cabe señalar que no resulta adecuado silo que se desea es modelizar sistemas ópticos complejos (con zoom o múltiples lentes).
No obstante, no debemos olvidar que la Geometría es sólo una parte del proceso. Para obtener unaimagen no sólo necesitamos saber dónde dibujar los puntos, sino también qué valor de brillo tenemosque asignarlos.
Definición 2.1.1. Una imagen es una función I , definida en una región compacta Ω de una superficie,tomando valores en R+. Es decir, es un array dos-dimensional de brillo3.
En el caso de una cámara Ω es una región plana rectangular ocupada por un medidor fotográfico oun sensor CCD:
I : Ω ⊆ R2 → R+
(x, y) 7→ I(x, y).
Una función imagen, I , puede representarse mediante su gráfica o usando una matriz. Una representa-ción diferente de la misma imagen, que es la que comprende el sistema visual humano, es la obtenidagenerando una “foto". Podemos entender una “foto” como una escena distinta de la real que produce enel sensor de imagen (en este caso, el ojo) la misma imagen que la real. En este sentido las “fotos” sonilusiones controladas: son escenas diferentes de la realidad (ya que son planas) que producen en el ojo lamisma impresión que la escena original. Lo que hay que tener en cuenta es que las tres representacionescontienen exactamente la misma información.
1Ver figuras 1.1 y 1.2.2Ver apéndice, sección 5.1, pág. 36.3Si es en color sus valores RGB (rojo, verde y azul) se representan en tres arrays como éste.
2.1 Introducción. 9
Figura 2.1: Tres representaciones equivalentes de una misma imagen: como fotografía, como matrizde enteros y como superficie. Aunque a “simple vista” no lo parezca, las tres representaciones guardanexactamente la misma información.
2.2 Lentes. 10
Figura 2.2: Modelo de lente delgada. La imagen del punto p es el punto x.
2.2. Lentes.
Una cámara (o sistema óptico) se compone de un conjunto de lentes usadas para producir cambios enla dirección de propagación de la luz (difracción, refracción, reflexión). Nosotros sólo consideraremos elmodelo más simple: las lentes delgadas.
Definición 2.2.1. Una lente delgada es un modelo matemático definido por un eje, el eje óptico, y unplano perpendicular al eje, el plano focal, con una apertura centrada en el centro óptico, es decir,la intersección del plano focal con el eje óptico. Consta de dos parámetros la distancia focal, f , y eldiámetro, d.
Presenta dos propiedades:
todos los rayos que pasan por la apertura paralelamente al eje óptico intersecan al eje óptico adistancia f del centro óptico;
los rayos que pasan a través del centro óptico no son desviados.
Proposición 2.2.2. La ecuación fundamental de la lente delgada es
1Z
+1z
=1f
Demostración. Sea p ∈ E3 un punto4 no muy lejano del eje óptico y a distancia Z, sobre el eje óptico,del centro óptico, o. Consideramos dos rectas a través de p: una paralela al eje óptico, y otra a través deo (ver figura 2.2).
La primera interseca al eje óptico en el foco; la segunda, no se refleja. Sea x el punto donde lasdos rectas se intersecan, y sea z la distancia entre éste y el centro óptico. Descomponiendo cualquierrecta que pase por p en dos “componentes” una paralela al eje óptico y otra a que pase a través de o,obtenemos que todos las rectas ues pasan por p, se intersecan en x al otro lado de la lente. En particular,una recta que pase por x, paralela al eje óptico, debe pasar por p. Usando semejanza de triángulos en laconstrucción llevada a cabo se obtiene la ecuación buscada.
4Donde E3 representa el espacio euclídeo tridimensional.
2.3 Cámara pinhole. 11
Figura 2.3: Cámara pinhole.
2.3. Cámara pinhole.
A continuación pasamos a considerar el modelo de cámara más sencillo que existe. Decimos sencilloporque se modeliza con una proyección cónica. Cabe señalar que ha sido considerado tradicionalmenteya que imita la construcción de las primeras cámaras5.Si hacemos que la apertura de una lente delgada tienda a cero, estamos forzando a que todas las rectaspasen por el centro óptico, o y, por lo tanto ninguno es desviado. De este modo, un punto p y su imagen,x, están alineados en una recta que pasa por o (ver figura 2.4).
Si el punto p tiene coordenadas X = [X,Y, Z]T relativas a la referencia centrada en el centro óptico,o con el eje z siendo el eje óptico de la lente, es inmediato (por semejanza de triángulos), siendo f ladistancia focal, que las coordenadas de p y su imagen x están relacionadas por las ecuaciones:
x = −f XZ, y = −f Y
Z
El signo negativo de las fórmulas se debe a que si consideramos que el plano imagen está detrás delcentro óptico la imagen se forma invertida (al igual que ocurre en la retina), como se observa en la figura2.3. Para solucionarlo, basta considerar que el plano imagen está delante, cambiando (x, y) por (−x,−y)que es como aparece representado en la figura 2.4. En este caso la imagen del punto p estará dada por
x = fX
Z, y = f
Y
Z
Hemos de señalar que estas ecuaciones simplemente representan una proyección cónica de centro o yeje el plano imagen, π : R3 → R2; X → x, escribiremos X = π(x). Notemos que todos los puntos queestán alineados con p y o tienen la misma imagen x = [x, y]T , lo que es lógico ya que representan el mis-mo punto proyectivo6 y tienen las mismas coordenadas homogéneas, es decir, las mismas coordenadasmódulo multiplicación por constante.
5Ver figura 1.2.6Se define un punto proyectivo de un espacio proyectivo P (X), donde X es un espacio vectorial, como el conjunto de
rectas vectoriales de X .
2.4 Modelo geométrico del proceso de formación de la imagen. 12
Figura 2.4: Modelización de una cámara pinhole.
2.4. Modelo geométrico del proceso de formación de la imagen.
Una vez que conocemos en qué punto de la imagen se proyecta cada punto del espacio, podemosreducir el proceso de formación de la imagen a trazar rectas entre puntos tridimensionales y píxeles. Paraestablecer esta correspondencia entre los puntos del espacio tridimensional y sus imágenes proyectadasen un plano imagen dos-dimensional, necesitamos un modelo matemático que tenga en cuenta tres tiposde transformaciones:
1. transformaciones coordenadas entre el sistema de referencia de la cámara (C) y el del mundo (W);
2. paso de coordenadas 3-D a coordenadas 2-D;
3. transformación coordenada entre las posibles elecciones del sistema de referencia de la imagen.
Lo que haremos será describir tal proceso de formación de la imagen como una serie de transformacionescoordenadas. Invertir esa cadena de transformaciones es lo que se conoce por “calibración de la cámara”(proceso previo a la reconstrucción de un objeto a partir de dos o más vistas y que no vamos a tratar eneste trabajo, ya que sólo usaremos vistas calibradas).
2.4.1. Cámara perspectiva ideal.
Consideremos un punto genérico p con coordenadas X0 = [X0, Y0, Z0]T ∈ R3 relativas al sistemade referencia del mundo7. Las coordenadas de este mismo punto X = [X,Y, Z]T con respecto al sistemade referencia de la cámara están dadas por una transformación lineal8 g = (R, T ) de X0:
X = RX0 + T ∈ R3.
Adoptando el modelo de cámara pinhole presentado en la sección anterior (ver figura 2.4), es fácil verque el punto X se proyecta en el plano imagen en el punto
x =[xy
]=f
Z
[XY
].
7Normalmente denotaremos con X0 las coordenadas de un punto relativas a la posición inicial del sistema de referenciamóvil de una cámara.
8Donde R y T son matrices rotación y traslación, respectivamente.
2.4 Modelo geométrico del proceso de formación de la imagen. 13
En coordenadas homogéneas, la relación de semejanza anterior se puede reescribir como:
Z
xy1
=
f 0 0 00 f 0 00 0 1 0
XYZ1
,o, lo que es lo mismo,
Zx =
f 0 0 00 f 0 00 0 1 0
X
donde X := [X,Y, Z, 1]T y x := [x, y, 1]T en coordenadas homogéneas. Representaremos la coordenadaZ de p (es decir, su “profundidad”) por un escalar positivo arbitrario λ ∈ R+, que no es otra cosa que laconstante que se obtiene de deshomogeneizar las coordenadas.La matriz anterior la podemos expresar como producto de dos matrices: f 0 0 0
0 f 0 00 0 1 0
=
f 0 00 f 00 0 1
1 0 0 00 1 0 00 0 1 0
,obteniendo dos matrices que llamaremos:
Kf :=
f 0 00 f 00 0 1
∈ R3×3, Π0 :=
1 0 0 00 1 0 00 0 1 0
∈ R3×4.
La matriz Π0 se conoce como la matriz de proyección canónica. Sustituyendo las coordenadas de latransformación lineal, tenemos:
XYZ1
=[R T0 1
]X0
Y0
Z0
1
.Y, resumiendo todo, el modelo de una cámara ideal puede ser descrito como:
λ
xy1
=
f 0 00 f 00 0 1
1 0 0 00 1 0 00 0 1 0
[ R T0 1
]X0
Y0
Z0
1
,o, en forma matricial,
λx = KfΠ0X = KfΠ0gX0.
Si conocemos la distancia focal, f , dividiendo el modelo anterior se reduce a una transformación euclí-dea9 g seguida de una proyección canónica Π0, es decir,
λx = Π0X = Π0gX0
9Transformación lineal que preserva las distancias.
2.4 Modelo geométrico del proceso de formación de la imagen. 14
Figura 2.5: Transformación de coordenadas métricas a coordenadas en píxeles.
2.4.2. Cámara con parámetros intrínsecos.
La ecuación del modelo anterior responde a una elección particular del sistema de referencia, lo quese llama “referencia canónica de la retina”, con centro en el centro óptico y con un eje alineado con eleje óptico. En la práctica, cuando se toman imágenes con una cámara digital las medidas se obtienenen términos de píxeles (i, j), con el origen del sistema de coordenadas de la imagen pixelada, situadotípicamente en la esquina superior izquierda de la misma. Para conseguir que el modelo nos sea útil,necesitamos especificar la relación entre el sistema de coordenadas del plano de la retina y el array depíxeles. A la par que encontremos tal relación, descubriremos los denominados parámetros intrínsecosde la cámara, ya que dependen de su geometría y óptica internas.
El primer paso consiste en especificar en qué unidades vamos a medir a lo largo de los ejes x ey. Si (x, y) están en unidades métricas (por ejemplo, mm), y (xs, ys) son versiones a escala de lascorrespondientes coordenadas del píxel, es decir, se les ha aplicado la siguiente transformación:[
xsys
]=[sx 00 sy
] [xy
].
La matriz de la transformación se llama matriz de escalado y depende del tamaño del píxel (enunidades métricas) (ver figura 2.5). Si sx = sy cada píxel es cuadrado, pero esto, en general, no es así,sino que los píxeles son rectangulares. Las coordenadas (xs, ys) son relativas al punto principal (donde eleje z interseca al plano imagen), mientras que los píxeles (i, j) normalmente se especifican relativos a laesquina superior izquierda. Entonces, lo que necesitamos es trasladar el origen del sistema de referenciaa dicha esquina mediante la transformación:
x′ = xs + ox y′ = ys + oy,
donde (ox, oy) son las coordenadas (en píxeles) del punto principal relativas al sistema de referencia dela imagen. Esto se muestra en la figura 2.5.
2.4 Modelo geométrico del proceso de formación de la imagen. 15
Figura 2.6: Transformación de coordenadas 3-D a coordenadas en píxeles.
Todos los pasos que hemos realizado se representan (en coordenadas homogéneas):
x′ =
x′
y′
1
=
sx 0 ox0 sy oy0 0 1
xy1
donde x′ e y′ son las coordenadas de la imagen actual en píxeles. Esto se ilustra en la figura 2.5. Si lospíxeles no son rectangulares, podemos utilizar una forma más geneal de la matriz de escalado:[
sx sθ0 sy
]∈ R2×2
donde sθ es lo que se denomina “skew factor” (en español diríamos “factor de torcimiento”) y es pro-porcional a cot(θ), donde θ es el ángulo formado por los ejes de la imagen10 xs e ys. La matriz detransformación toma entonces la forma general:
Ks =
sx sθ ox0 sy oy0 0 1
∈ R3×3.
En la práctica lo habitual es suponer que sθ = 0.Ahora, combinando el modelo de proyección de la sección precedente con el escalado y la traslación
obtenemos un modelo más realista de la transformación entre las coordenadas homogéneas de un punto 3-D relativas al sistema de referencia de la cámara y las coordenadas homogéneas de su imagen expresadasen términos de píxeles:
λ
x′
y′
1
=
sx sθ ox0 sy oy0 0 1
f 0 00 f 00 0 1
1 0 0 00 1 0 00 0 1 0
XYZ1
10Normalmente, el ángulo θ es muy próximo a 90o, y, por lo tanto, sθ es casi cero.
2.4 Modelo geométrico del proceso de formación de la imagen. 16
Nótese que en la ecuación anterior la modelización de una cámara se realiza en dos pasos:
El primer paso es una proyección perspectiva con respecto a un sistema normalizado de coorde-nadas11. Se determina mediante la matriz de proyección estándar Π0 = [I, 0].
El segundo, es una transformación adicional de la imagen del punto que acabamos de obtener enel paso primero, que depende de los parámetros intrínsecos de la cámara: distancia focal f ; losfactores de escala sx,sy y sθ; y el centro de la imagen (ox, oy).
La segunda transformación queda determinada por el producto de las matrices Ks y Kf :
K = KsKf =
sx sθ ox0 sy oy0 0 1
f 0 00 f 00 0 1
=
fsx fsθ ox0 fsy oy0 0 1
Esto nos permite escribir la ecuación de proyección como sigue:
λx′ = KΠ0X =
fsx fsθ ox0 fsy oy0 0 1
1 0 0 00 1 0 00 0 1 0
XYZ1
donde la matriz constante Π0 representa la proyección perspectiva; la matriz K es la denominada ma-triz de los parámetros intrínsecos o matriz de calibración. Las entradas de esta matriz, es decir, losparámetros intrínsecos, tienen la siguiente interpretación geométrica:
ox: coordenada x del punto principal en píxeles,
oy: coordenada y del punto principal en píxeles,
sx: anchura de un píxel,
sy: altura de un píxel,
f : distancia focal,
σ = sx/sy: razón entre la altura y la anchura de un píxel,
fsθ: “torcimiento” del píxel, normalmente cercano a cero.
Cuando se conoce la matriz de calibración K, las cordenadas calibradas x de un punto se obtienena partir de las coordenadas en píxeles x′ del mismo, simplemente invirtiendo la matriz K:
λx = λK−1x′ = Π0X =
1 0 0 00 1 0 00 0 1 0
XYZ1
Puede ser que conozcamos la matriz K de la cámara o que no. Si no es así, para conocerla, tenemos quellevar a cabo el proceso conocido como calibración12 de la cámara.
Resumiendo, la relación geométrica entre un punto de coordenadas X0 = [X0, Y0, Z0]T relativas ala referencia del mundo y las coordenadas de su imagen x′ = [x′, y′, 1]T (en píxeles) depende de:
11Se considera la distancia focal f = 1.12Consiste en la estimación de los parámetros intrínsecos de la cámara a partir de dos o más imágenes. Y es un paso necesario
para extraer información métrica a partir de imágenes y obtener resultados precisos.
2.4 Modelo geométrico del proceso de formación de la imagen. 17
el movimiento (R, T ) entre el sistema de coordenadas del mundo, W, y de la cámara, C (que es loque se conoce como parámetros extrínsecos de calibración),
la proyección ideal Π0, y
la matriz de calibración K.
Así, el proceso de formación de la imagen se modeliza:
λx′ = KΠ0X =
fsx fsθ ox0 fsy oy0 0 1
1 0 0 00 1 0 00 0 1 0
[ R T0 1
]X0
Y0
Z0
1
que en forma matricial queda
λx′ = KΠ0X = KΠ0gX0,
o, equivalentemente,λx′ = KΠ0X = [KR,KT ]X0.
Llamaremos matriz de proyección y denotaremos Π a la matriz KΠ0g = [KR,KT ] con lo que laecuación anterior se reduce a
λx′ = ΠX0 = KΠ0gX0.
Dividiendo por el escalar λ obtenemos las siguientes expresiones para las coordenadas de la imagen(x′, y′, z′):
x′ =πT1 X0
πT3 X0, y′ =
πT2 X0
πT3 X0, z′ = 1,
donde ΠT1 ,Π
T2 ,Π
T3 ∈ R4 son las filas de la matriz de proyección Π.
2.4.3. Distorsión radial.
Los parámetros de la matriz K describen distorsiones lineales. Sin embargo, los sistemas ópticosreales suelen presentar desviaciones respecto al modelo proyectivo ideal. Por ejemplo, frecuentementeaparece una deformación radial que hace que las líneas rectas se vean curvadas (ver figura 2.7). Es másgrave en imágenes con un gran campo de visión y se debe a que , dependiendo de la óptica de la cámara,las líneas que unen puntos del objeto con puntos de la imagen pueden cruzar puntos superpuestos conángulos diferentes.
El modelo más efectivo para corregirla es:
x = xd(1 + a1r2 + a2r
4),y = yd(1 + a1r
2 + a2r4),
,
(xd, yd) son las coordenadas de los puntos distorsionados, r2 = x2d + y2
d y a1, a2 son parámetros adicio-nales de la cámara que miden el grado de distorsión. Existen diversos algoritmos y paquetes de softwarepara compensar la distorsión radial usando procedimientos de calibración. Otra posibilidad es estimarladirectamente a partir de las imágenes13. Y una tecera,el empleo de múltiples imágenes en corresponden-cia.
Nosotros supondremos la distorsión radial compensada y que una cámara viene descrita símplementepor la matriz K.
13Para esto, lo más sencillo es minimizar mediante el método de Newton la curvatura de un conjunto de rectas conocidas enla imagen.
2.5 Notas. 18
Figura 2.7: Imagen distorsionada y corrección de la distorsión.
2.5. Notas.
1. Hemos introducido la proyección cónica como modelo de formación de imagen de una cámarapinhole.
2. En el caso ideal, si la matriz de calibración K es la matriz identidad, las coordenadas 3-D de unpunto las coordenadas de su imagen son14:
λx = Π0X = Π0gX0,
donde λ es un escalar (que indica la “profundidad” del punto) desconocido.
3. Si K no es la identidad, es decir, si las vistas del objeto no son calibradas, tenemos que realizarotra transformación lineal del plano imagen:
x′ = Kx.
Así, la transformación total queda:
λx′ = KΠ0X = KΠ0gX0.
14Usando coordenadas homogéneas.
Capítulo 3
Geometría epipolar.
3.1. Introducción.
La fotogrametría es la ciencia o técnica cuyo objetivo es el conocimiento de las dimensiones y posi-ción de objetos en el espacio, a través de la medida o medidas realizadas sobre una o varias fotografías.Si trabajamos con una foto podemos obtener información en primera instancia sobre la geometría delobjeto, es decir, información bidimensional. Si trabajamos con dos fotos, en la zona común a éstas (zonade solape), podremos tener visión estereoscópica; o dicho de otro modo, información tridimensional. Esoes lo que se conoce como geometría epipolar o geometría de dos vistas: disponemos de dos fotografíasde un mismo objeto, tomadas desde distintos puntos de vista, y queremos determinar la estructura delmismo.
El punto proyectado y los dos centros ópticos de las cámaras se disponen como se indica en la figura3.1. Las relaciones geométricas entre los elementos que ahí aparecen pueden describirseese de formaalgebraica mediante una restricción que involucra las posiciones de las cámaras y las coordenadas delas dos imágenes del punto p, x1, x2, pero no sus coordenadas tridimensionales. Así, dados suficientespuntos en correspondencia1, esta restricción puede usarse para recuperar las posiciones de las cámaras.Eso constituye el objetivo de este capítulo.
Partiremos de las siguientes hipótesis:
disponemos de dos imágenes de la misma escena tomadas desde dos puntos de vista distintos;
suponemos las vistas calibradas (la matriz de calibración K es la identidad), es decir, las coorden-das (homogéneas) X de un punto p y las de su imagen x, con respecto al sistema de referencia dela cámara, están relacionadas por:
λx = Π0X, donde Π0 = [I, 0];
la escena es estática, es decir, no contiene objetos en movimiento;
conocemos las correspondencias entre los puntos.
Si x1, x2 son un par de puntos en correspondecia, ambos son imágenes de un mismo punto, se tendrá queestán relacionados como se describirá en el teorema 3.2.1.
1Consultar apéndice, sección 5.2, pág. 36
3.2 La restricción epipolar y la matriz esencial. 20
Figura 3.1: Geometría epipolar.
3.2. La restricción epipolar y la matriz esencial.
Cada cámara, como vimos en el capítulo anterior, tiene asociado un sistema de referencia, con origeno en el centro óptico y el eje z alineado con el eje óptico. La relación entre las coordenadas de unpunto con respecto a ella y sus coordenadas 3-D con respecto a W , la referencia del “mundo” puedeser expresada mediante un movimiento del sólido rígido2. Sin pérdida de generalidad, podemos suponerque la referencia W coincide con la de una de las cámaras, y que está relacionada con la posición de lasegunda cámara por una transformación euclídea3 g = (R, T ) ∈ SE(3). Sean X1 y X2 las coordenadas3-D del punto p relativas a las dos referencias de las cámaras, respectivamente; se relacionan mediantela transformación:
X2 = RX1 + T.
Llamemos x1, x2 ∈ R3 a las coordenadas homogéneas de la proyección de p en ambos planos imagen.Como Xi = λixi, i = 1, 2, la relación anterior queda:
λ2x2 = Rλ1x1 + T.
Teorema 3.2.1 (Restricción epipolar). Sean x1, x2 los dos proyectados del mismo punto p obtenidosa partir de dos posiciones de la cámara relacionadas por la transformación g = (R, T ), donde R ∈SO(3) y T ∈ R3. Entonces,
〈x2, T ×Rx1〉 = 0, es decir, xT2 TRx1 = 0.
Demostración. Consideremos la igualdad λ2x2 = Rλ1x1 + T, premultiplicamos a ambos lados por T 4:
λ2Tx2 = TRλ1x1.
2Consultar apéndice, sección 5.4,pág. 393Consultar apéndice, sección 5.4,pág. 394Consultar apéndice, sección 5.3, pág. 38.
3.3 Propiedades de la matriz esencial. 21
Figura 3.2: La restricción epipolar surge a partir de que los puntos en correspondencia están relacionadosmediante una transformación euclídea.
Como el vector Tx2 = T × x2 es perpendicular al vector x2, el producto escalar 〈x2, Tx2〉 = xT2 Tx2 escero, así, multiplicando a la izquierda por xT2 en ambos lados de la igualdad obtenemos 0 = x2TRλ1x1
y, dado que λ1 > 05, podemos dividir y obtener: x2TRx1 = 0
Nota 3.2.2. La ecuación xT2 TRx1 = 0 es denominada restricción epipolar.
Definición 3.2.3. Dadas dos posiciones distintas de una cámara, relacionadas por la transformacióng = (R, T ) ∈ SE(3) se llama matriz esencial y se denota E la matriz
E := TR
Definición 3.2.4. (Elementos de la geometría epipolar)6.
El plano (o1, o2, p) determinado por los dos centros de proyección o1, o2 y el punto p se conocecomo plano epipolar7.
Los puntos e1, e2 son llamados epipolos. ei es el proyectado de oj , i ∈ 1, 2, i 6= j con respectoa la cámara con centro oi8.
El plano epipolar interseca a los planos imagen en dos rectas l1, l2: las líneas epipolares.
3.3. Propiedades de la matriz esencial.
La matriz E = TR ∈ R3×3 contiene la información sobre la posición relativa de las dos cámaras.5Nótese que λ1 y λ2, lo que hemos denominado “escalares de profundidad”, no son más que los factores que resultan de
“normalizar” los puntos proyectivos x1 y x2, entendiendo por esto el que su tercera coordenada sea 1. Proceso siempre posibleya que ésta es distinta de cero porque x1 y x2 no pertenecen al hiperplano del infinito.
6Ver figura 3.1.7Claramente, existe un plano epipolar asociado a cada punto p.8Podríamos decir que es el punto donde cada cámara “ve” a la otra.
3.3 Propiedades de la matriz esencial. 22
Definición 3.3.1. Se denomina espacio esencial el conjunto de las matrices esenciales:
E := TR|R ∈ SO(3), T ∈ R3.
Nota 3.3.2. Obsérvese que el conjunto E tiene estructura de variedad diferenciable.9No es un grupo deLie porque no satisface los axiomas de grupo: el determinante de una matriz esencial es cero10.
Antes de comenzar con el estudio de la estructura de las matrices esenciales, introduciremos un lemade Álgebra Lineal que nos resultará muy útil.
Lema 3.3.3 (El operador gorro). Dado un vector T ∈ R3 y una matriz K ∈ R3×3, si det(K) = 1 yT ′ = KT, entonces T = KT T ′K.
Demostración. Como KT (.)K y K−1(.) son aplicaciones lineales de R3 en R3×3, basta comprobar quelas imágenes de los vectores de la base, [1, 0, 0]T , [0, 1, 0]T , [0, 0, 1]T por ambas aplicaciones son lasmismas. No incluiremos la comprobación que hemos efectuado con Maple por consistir en un simplecálculo.
Teorema 3.3.4 (Caracterización de matriz esencial). Una matriz no nula E ∈ R3×3 es una matrizesencial si y sólo si E tiene una descomposición en valores singulares11 (SVD), E = UΣT con
Σ = diagσ, σ, 0
para σ ∈ R+ y U, V ∈ SO(3).
Demostración. En primer lugar, probemos que es condición necesaria. Por definición de matriz esencial,existe al menos un par (R, T ), R ∈ SO(3), T ∈ R3, tales que TR = E.Sea R0 ∈ SO(3) satisfaciendoR0T = [0, 0, ‖T‖]T . Llamemos a := R0T ∈ R3. Como det(R0) = 1, por el lema 3.3.3, sabemos queT = RT0 aR0. Entonces, EET = TRRT T T = T T T = RT0 aR0R
T0 a
TR0 = RT0 aaTR0. Se tiene que
aaT =
0 −‖T‖ 0‖T‖ 0 0
0 0 0
0 ‖T‖ 0−‖T‖ 0 0
0 0 0
=
‖T‖2 0 00 ‖T‖2 00 0 0
.Así, el conjunto de valores singulares de la matriz esencial E = TR es ‖T‖, ‖T‖, 0. Nos resta probarque U, V ∈ SO(3). Ya sabemos que E = TR = RT0 aR0R. Sea RZ(θ) la matriz del giro de θ radianesalrededor del eje Z12 entonces,
RZ(+π
2) =
0 −1 01 0 00 0 1
.9Ver apéndice, sección 5.5, pág.42.
10E = bTR, luego det(E) = det( bT ) det(R) y det( bT ) = 0 por ser una matriz antisimétrica de tamaño n = 3 que es impar.11Descomposición en valores singulares (SVD). Sea A ∈ Rm×n con rango p. Además, supongamos, sin pérdida de gene-
ralidad, que m ≥ n. Entonces,
∃U ∈ Rm×p con columnas ortonormales,
∃V ∈ Rn×p con columnas ortonormales,
∃Σ ∈ Rp×p,Σ = diagσ1, σ2, . . . , σp matriz diagonal con σ1 ≥ σ2 ≥ . . . ≥ σp,tales que A = UΣV T .
12Es decir, RZ(θ) =
24 cos(θ) − sin(θ) 0sin(θ) cos(θ) 0
0 0 1
35 .
3.3 Propiedades de la matriz esencial. 23
Y, por lo tanto,
a = RZ(+π
2)RTZ(+
π
2)a = RZ(+
π
2)
0 1 0−1 0 00 0 1
0 −‖T‖ 0‖T‖ 0 0
0 0 0
= RZ(+π
2)diag‖T‖, ‖T‖, 0.
Sustituyendo,E = TR = RT0 RZ(+
π
2)diag‖T‖, ‖T‖, 0R0R.
Ahora, para obtener la SVD de E, E = UΣV T , basta tomar U = RT0 RZ(+π2 ) y V T = R0R. Como
hemos construido U y V como producto de matrices de SO(3), (que es un grupo) se tiene que U, V ∈SO(3).
Veamos que es condición suficiente. Dada E ∈ R3×3 con SVD E = UΣV T con U, V ∈ SO(3) yΣ = diagσ, σ, 0, σ ∈ R+, se definen (R1, T1), (R2, T2) ∈ SE(3) como
(T1, R1) = (URZ(+π2 )ΣUT , URTZ(+π
2 )V T ),(T2, R2) = (URZ(−π
2 )ΣUT , URTZ(−π2 )V T ).
De la definición es inmediato que T1R1 = T2R2 = E. Luego E es una matriz esencial.
Hasta ahora, sabemos construir una matriz esencial E dados una matriz de rotación R ∈ SO(3) yun vector de traslación T ∈ R3, usando que E = TR. El problema inverso, es decir, calcular R y T apartir de la matriz fundamental es menos obvio. En la demostración de la condición de suficiencia en elteorema anterior, hemos empleado la SVD para construir dos soluciones para (R, T ). Pero, ¿serán éstaslas únicas soluciones? Antes de dar respuesta a esta cuestión, en el teorema 3.3.6, necesitamos un lema:
Lema 3.3.5. Consideremos una matriz antisimétrica no nula cualquiera T ∈ so(3), con T ∈ R3. Siexiste R ∈ SO(3) tal que TR es también antisimétrica, entonces13 R = I o R = ebuπ, donde u = T
‖T‖ .
Además, T ebuπ = −T .
Demostración. Sin pérdida de generalidad, supongamos que ‖T‖ = 1. Como TR es también antisimé-
trica,(TR)T
= −TR⇒ RT T T = −TR⇒ RT(−T)
= −TR⇒ RT T = TR y, premultiplicandopor R ambos miembros de la igualdad,
T = RTR.
Como R es una matriz de rotación, podemos expresarla en notación exponencial, R = ebωθ, con ω ∈ R3,‖ω‖ = 1, y θ ∈ R; donde ω y θ denotan el eje y el ángulo de giro, respectivamente.Si θ = 0 el lema está probado (porque R = I).Supongamos entonces que θ 6= 0. Reescribiendo la igualdad anterior tenemos ebωθT ebωθ = T . Postmulti-plicando por ω, ebωθT ebωθω = T ω; ebωθω = ω, luego ebωθT ω = T ω ⇒
(ebωθ − 1
)T ω = 0. Como ω es
el único autovector asociado al autovalor 1 de la matriz ebωθ, y T ω es ortogonal a ω, T ω ha de ser cero14
Así, como T T = 0 y ‖ω‖ = 1, se tiene ω = ± T‖T‖ ; es decir, ω = ±u. R conmuta con T : T = RTR⇔
RT = TRT ⇔ RT =(−RT
)T⇔ RT = TR. Usando esto RRT = T ⇔ e2bωθT = T .
De acuerdo con la fórmula de Rodrigues15, tenemos
e2bωθ = I + ω sin(2θ) + ω2(1− cos(2θ)),13Denotaremos ebuθ el giro de eje u y ángulo θ. El porqué se explica en el apéndice, sección 5.5, pág. 5.5.14De lo contrario, se tendría ebωθ = 1 lo que es una contradicción, porque habría más autovectores que ω asociados al valor
propio 1.15Ver apéndice, sección 5.4, pág. 39.
3.3 Propiedades de la matriz esencial. 24
y, como e2bωθ = I , se sigueω2 sin(2θ) + ω3(1− cos(2θ)) = 0.
Como ω2 y ω3 son linealmente independientes,16 como elementos de R9, ha de ser
sin(2θ) = 1− cos(2θ) = 0.
Es decir, θ es igual a 2kπ ó (2k + 1)π, k ∈ Z. De donde R es igual a I ó ebωπ.Dos posibles casos:
ω = u = T‖T‖ , entonces ebωπT = −T ;
ω = −u = − T‖T‖ , entonces ebωT = −T .
Ambos casos satisfacen lo pedido.
Teorema 3.3.6 (Cálculo de la posición a partir de la matriz esencial). Existen exactamente dos po-siciones relativas (R, T ) con R ∈ SO(3) y T ∈ R3 correspondientes a una matriz esencial no nulaE ∈ E .
Demostración. Supongamos que (R1, T1), (R2, T2) ∈ SE(3) son dos soluciones de la ecuación TR =E. Entonces, se tiene T1R1 = T2R2 ⇔ T1 = T2R2R
T1 . Como T1, T2 son matrices antisimétricas y
R2RT1 es una matriz de rotación, por el lema 3.3.5, se tienen dos casos excluyentes:
(R2, T2) = (R1, T1),
(R2, T2) = (ebu1πR1,−T1), con u1 = T1‖T1‖ .
Así, dada una matriz esencial, E, hay únicamente dos pares (R, T ) ∈ SO(3), tales que TR = E. Másaún, si E = UΣV es la factorización SVD de E, con U, V ∈ SO(3), las soluciones vienen dadas por lasiguiente fórmula17
(T1, R1) = (URZ(+π2 )ΣUT , URTZ(+π
2 )V T ),(T2, R2) = (URZ(−π
2 )ΣUT , URTZ(−π2 )V T ).
16Sea ω = [a, b, c]T , entoces
bω =
24 0 −c bc 0 a−b a 0
35 , bω2 =
24 −(c2 + b2) ab acab −(c2 + a2) bcac bc −(b2 + a2)
35 , bω3 =
24 0 c −b−c 0 ab −a 0
35 = −bω.17Recordemos que RZ(θ) := ebe3θ , con e3 = [0, 0, 1]T ∈ R3.
Capítulo 4
Reconstrucción a partir de dos vistascalibradas.
4.1. Introducción.
En el capítulo anterior, hemos visto que los puntos en correspondencia verifican la restricción epi-polar. Lo que perseguimos es determinar la posición relativa de las cámaras dadas dos imágenes de unamisma escena. En este capítulo explicaremos cómo resolver este problema. Se hará en dos pasos: prime-ro, hallaremos la matriz E a partir de un número1de puntos en correspondencia; después basta calcularlas matrices R y T dada E. Sin embargo, la matriz que obtendremos como solución usando los puntosen correspondencia puede no ser una matriz esencial, por lo que necesitaremos tomar la matriz esencialmás próxima a ella, proyectándola sobre el espacio de las matrices esenciales, previamente al cálculo dela posición relativa.Aunque el algoritmo que proponemos aquí es poco óptimo si los datos presentan ruido, lo hemos elegidoporque es el que mejor ilustra la estructura geométrica del espacio de las matrices esenciales.
4.2. El algoritmo lineal de los ocho puntos: justificación teórica.
Definición 4.2.1. Sea E = TR una matriz esencial , con coeficientes E =
e11 e12 e13
e21 e22 e23
e31 e32 e33
, llama-
mos ES al vector ES = [e11, e12, e13, e21, e22, e23, e31, e32, e33] ∈ R9. Definimos la norma de Frobe-nius de una matriz E como ‖ES‖2. Se denotará ‖E‖f .
Nota 4.2.2. Es decir, tomamos la norma euclídea del vectorES asociado a la matriz E = (eij) ∈ R9×9,
‖E‖f = ‖ES‖2 =√∑
i,j e2ij , lo que equivale a ‖E‖f =
√traza(EET ).
Definición 4.2.3. Sean x1 = [x1, y1, z1]T y x2 = [x2, y2, z2]T vectores en R3 se define el producto deKronecker como
x1 ⊗ x2 = [x1x2, x1y2, x1z2, y1x2, y1y2, y1z2, z1x2, z1y2, z1z2]T ∈ R9.
Denotaremos el producto de Kronecker a := x1 ⊗ x2. Con estas notaciones podemos reescribir larestricción epipolar, xT2 Ex1 = 0, así:
aTES = 01Ya se verá cuál es y por qué.
4.2 El algoritmo lineal de los ocho puntos: justificación teórica. 26
Figura 4.1: Proyección sobre E : E ∈ E es la matriz esencial más próxima a F .
Definición 4.2.4. Dado un conjunto de pares de puntos de la imagen en correspondencia (xj1, xj2), j =
1, 2, . . . n, se define la matriz X ∈ Rn×9 asociada
X := [a1, a2, . . . , an]T ,
donde la j-ésima fila aj es el producto de Kronecker del par (xj1, xj2).
Si los datos no presentan ruido, el vector ES cumple XES = 0. A partir de este sistema linealobtenemos ES . Como E es una matriz homogénea, para resolverlo el rango de X ha de ser 8, por lo quenecesitamos ocho pares de puntos en correspondencia.
Lo habitual, como las correspondencias suelen tener errores, es que el sistema no tenga solución. Enese caso, se aplica el método de los mínimos cuadrados: tomamos ES tal que minimice la función deerror2 ‖XES‖2.
Otra situación que puede darse es que el rango de X sea menor que ocho a pesar de que tengamosmás de nueve correspondencias. Esto es debido a que hay menos de ocho puntos en posición general3.En este caso el problema tiene soluciones múltiples.
Sin embargo, aun sin ruido, para que un vectorES sea solución de nuestro problema, no es suficientecon que esté en el núcleo de X . De hecho, tiene que satisfacer una restricción adicional: que su formamatricial E sea una matriz esencial. Para solucionarlo lo que haremos será primero calcular el núcleode X obteniendo una matriz, digamos F , que probablemente no pertenezca a E ; y, en segundo lugar,proyectarla sobre la variedad de las matrices esenciales. Proceso que ilustramos en la figura 4.1. Elsiguiente teorema caracteriza la matriz proyección.
Teorema 4.2.5 (Proyección sobre E). Dada una matriz realF ∈ R3×3 con SVDF = Udiagλ1, λ2, λ3V T ,cumpliendo U, V ∈ SO(3), λ1 ≥ λ2 ≥ λ3, se tiene que la matriz esencial E ∈ E que minimiza el error‖E − F‖2f viene dada por E = Udiagσ, σ, 0V T con σ = λ1+λ2
2 .
Demostración. Sea Σ = diagσ, σ, 0 fija. Definimos Eσ ⊆ E como el conjunto de las matrices esen-ciales cuya SVD es de la forma U1ΣV T
1 , U1, V1 ∈ SO(3). Para simplificar la notación llamaremosΣλ = diagλ1, λ2λ3. Ahora efectuaremos la prueba del teorema en dos pasos.Paso 1. Probaremos que para Σ fijo, la matriz esencial E ∈ EΣ que minimiza el error ‖E − F‖2f es de laforma E = UΣV T (no tiene por qué ser única). Como E ∈ EΣ, E = U1ΣV T
1 ; entonces,
2Ello se consigue tomando ES el vector propio de X TX que corresponde al menor valor propio.3Entendiendo por posición general que cuatro de los ocho puntos formen una referencia proyectiva.
4.2 El algoritmo lineal de los ocho puntos: justificación teórica. 27
Lema 4.2.6.‖E − F‖2f = ‖Σλ − UTU1ΣV T
1 V ‖2f .
Demostración. ‖E−F‖2f = ‖U1ΣV T1 −UΣλV
T ‖2f = traza[(U1ΣV T1 −UΣλV
T )(V1ΣUT1 −V ΣλUT )] =
traza[(Σλ − UTU1ΣV T1 V )(Σλ − V TV1ΣUT1 U)] = ‖Σλ − UTU1ΣV T
1 V ‖2f .
Definimos P := UTU1, Q := V TV1 ∈ SO(3), que son de la forma:
P =
p11 p12 p13
p21 p22 p23
p31 p32 p33
, Q =
q11 q12 q13
q21 q22 q23
q31 q32 q33
.Con esta notación, lema anterior y usando que la traza de A y AT es la misma llegamos a ‖E − F‖2f =traza[(Σλ − PΣQT )(Σλ − QΣP T )] = traza(Σ2
λ − ΣλQΣP T − PΣQTΣλ + Σ2) = traza(Σ2λ) −
2traza(PΣQTΣλ) + traza(Σ2).Desarrollando el segundo término
traza(PΣQTΣλ) = σ[λ1(p11q11 + p12q12) + λ2(p21q21 + p22q22)].
Por otro lado, como P,Q ∈ SO(3) sus columnas tienen norma a lo sumo uno4 y son ortogonales dos ados, luego
p11q11 + p12q12 ≤ 1,p21q21 + p22q22 ≤ 1.
Como Σ y Σλ son fijos y λ1, λ2 ≥ 0, el error ‖E − F‖2f se minimiza cuando p11q11 + p12q12 =p21q21 + p22q22 = 1. O sea, cuando P y Q son de la forma
P = Q =
cos(θ) − sin(θ) 0sin(θ) cos(θ) 0
0 0 1
.Obviamente, P = Q = I es una de las soluciones. Representa el caso U1 = U , V1 = V .Paso 2. Por el Paso 1 necesitamos minimizar la función de error sólo sobre las matrices de la formaUΣV T ∈ E , donde Σ puede variar. Así hemos reducido el problema a minimizar la función de error 5
‖E − F‖2f = (λ1 − σ)2 + (λ2 − σ)2 + (λ3 − 0)2.
Claramente, el mínimo se alcanza en σ = 2λ1+λ22 .
Nota 4.2.7. El lector se habrá percatado de que en el teorema anterior hemos supuesto que en la SVDde E tanto U como V son matrices de SO(3). Eso no es siempre cierto cuando E se estima a partir dedatos con ruido. De hecho, los algoritmos estándar que computan la factorización SVD no garantizanque las matrices U y V que devuelven, tengan determinante positivo. Sin embargo, nuestra suposición escorrecta porque la matriz E es homogénea y basta cambiarla de signo para que esté en las condicionesdel teorema.
Como E es única salvo factor de escala, por convenio se suele tomar la matriz esencial normalizada,esto es, ‖T‖ = ‖E‖ = 1. Cada matriz normalizada, de acuerdo con el teorema 3.3.6, nos proporcianados posibles posiciones relativas (R, T ). Así, a partir de ±E, tenemos cuatro soluciones para (R, T ).El último paso del algoritmos de los ocho puntos consistirá en combinar los signos + y − para obtenertodas las posibles soluciones.
4Porque det(P ) = det(Q) = 1.5La igualdad se sigue de sustituir p = q = 1 y operar: traza(Σ2
λ) − 2traza(PΣQTΣλ) + traza(Σ2) = λ21 + λ2
2 + λ23 −
2(σλ1 + σλ2) + (σ2 + σ2 + 0) = λ21 + σ2 − 2σλ1 + λ2
2 + σ2 − 2σλ2 + λ23.
4.2 El algoritmo lineal de los ocho puntos: justificación teórica. 28
Figura 4.2: Cuatro posibles reconstrucciones de un punto a partir de E. Nótese que sólo una de ellas,(a),satisface que el punto tiene profundidad positiva con respecto a ambas cámaras. Es decir, sólo uno de loscuatro puntos está delante de o1 y o2.
Ejemplo 4.2.8 (Ejemplo numérico). Supongamos que
R =
cos(π4 ) 0 sin(π4 )0 1 0
− sin(π4 ) 0 cos(π4 )
=
√
22 0
√2
20 1 0−√
22 0
√2
2
, T =
200
.Entonces la matriz esencial es
E = TR =
0 0 0√2 0 −
√2
0 2 0
.Como ‖T‖ = 2, la matrizE que hemos obtenido no está normalizada. Esto también se aprecia fácilmentea partir de la SVD de E,
E = UΣV T =
0 0 −1−1 0 00 1 0
2 0 00 2 00 0 0
−
√2
2 0 −√
22
0 1 0√2
2 0 −√
22
T
,
donde los valores singulares no nulos toman el valor 2 en vez de 1. Normalizar E es equivalente asustituir la matriz Σ anterior por Σ = diag1, 1, 0.Ahora es fácil calcular las cuatro posibles descomposiciones (R, T ) para E
4.3 Algoritmo lineal de los ocho puntos. 29
1. URTZ(π2 )V T =
√
22 0
√2
20 −1 0√2
2 0 −√
22
, URZ(π2 )ΣUT =
0 0 00 0 10 −1 0
;
2. URTZ(π2 )V T =
√
22 0
√2
20 −1 0√2
2 0 −√
22
, URZ(−π2 )ΣUT =
0 0 00 0 −10 1 0
;
3. URTZ(−π2 )V T =
√
22 0
√2
20 1 0−√
22 0
√2
2
, URZ(π2 )ΣUT =
0 0 00 0 −10 1 0
;
4. URTZ(−π2 )V T =
√
22 0
√2
20 1 0−√
22 0
√2
2
, URZ(π2 )ΣUT =
0 0 00 0 10 −1 0
.La tercera solución es exactamente el movimiento original (R, T ) excepto porque la traslación, T , estánormalizada.
Una vez que hemos terminado con las bases teóricas, vamos a describir cómo actúa el algoritmolineal de los ocho puntos.
4.3. Algoritmo lineal de los ocho puntos.
Dado un cojunto de correspondencias entre las dos imágenes (xi, xj), j = 1, 2, . . . , n (n ≥ 8), elalgoritmo devuelve (R, T ) ∈ SE(3), tales que
xjT2 TRxj1 = 0, j = 1, 2, . . . , n.
1. Cálculo de una aproximación de la matriz esencial.Construir X = [a1, a2, . . . , an]T ∈ Rn×9 a partir de las correspondencias xj1 y xj2 como se hizo enel teorema 4.2.5:
aj = xj1 ⊗ xj2 ∈ R9.
Encontrar el vector ES ∈ R9 de norma 1 tal que ‖XES‖ se minimimice como sigue: calcular laSVD de X = UXΣXV T
X y definir ES la novena columna de VX . Calcular la matriz asociada a ES ,E. (Esta matriz, en general, no pertenecerá a E .)
2. Proyección sobre E .Descomponer la matriz E, calculada a partir de los datos, en valores singulares
E = Udiagσ1, σ2σ3V T ,
donde σ1 ≥ σ2 ≥ σ3 ≥ 0 y U, V ∈ SO(3). En general, como E puede no ser una matrizesencial, σ1 6= σ2 y σ3 6= 0. Pero su proyección sobre E (normalizada6) es de la forma UΣV T ,con Σ = diag1, 1, 0.
6Tomando ‖T‖ = ‖E‖ = 1
4.3 Algoritmo lineal de los ocho puntos. 30
Figura 4.3: Ocho parejas de puntos en correspondencia.
3. Recuperación de la posición relativa.A partir de la SVD de la proyección, calculamos R y T como sigue:
R = URTZ(±π2
)V T ; T = URZ(±π2
)ΣUT ,
donde RTZ(±π2 ) =
0 ±1 0∓1 0 00 0 1
.
A continuación, realizaremos algunos comentarios generales sobre el algoritmo propuesto:
• Número de puntos. Se toman ocho puntos por simplicidad en la presentación del algoritmo. Enrealidad, la matriz E (como función de (R, T )) tiene sólo cinco grados de libertad: tres para la rotacióny dos para la traslación. Usando propiedades algebraicas de E, puede reducirse el número de puntos.Por ejemplo, como det(E) = 0, podemos exigir que rango(X ) = 7 (en vez de 8) y encontrar dos solu-ciones ES1 y ES2 ∈ R9 del núcleo de X . De hecho, existe un algoritmo lineal que sólo usa seis puntos,pero emplea propiedades algebraicas de la matriz esencial más complicadas. Esto no debería resultarnossorprendente, ya que Kruppa (1913) probó que sólo se necesitan cinco puntos en posición general pararecuperar (R, T ). Se prueba que hay hasta diez soluciones (posiblemente complejas), aunque no puedenobtenerse de forma cerrada. Además, para algunos movimientos especiales, como los movimientos pla-nos, sólo se necesitan cuatro puntos para calcular E.
• Número de soluciones. Tanto E como −E satisfacen las mismas restricciones epipolares, luegoen general tendremos 2× 2 = 4 posibles soluciones para (R, T ). Para conseguir unicidad en la soluciónse suele tomar la única de ellas que hace que las “profundidades” de los puntos 3-D sean positivas conrespecto a los dos sistemas de referencia de las cámaras. Es decir, tres de las cuatro soluciones son físi-camente imposibles y se descartan.
• Posición relativa. En todos nuestros cálculos hemos asumido que E 6= 0, lo que nos permite po-der normalizar esta matriz. De la definición de matriz esencial se sigue que E = 0 ⇔ T = 0. Así, el
4.4 Reconstrucción “euclídea”. 31
algoritmo de los ocho puntos requiere que T 6= 0. En la práctica, debido al ruido en los datos, el algo-ritmo puede dar una respuesta incluso aunque el movimiento sea una rotación pura. Se ha comprobadoexperimentalmente que en estos casos, si hay suficiente ruido, (por la traslación ficticia que se crea) elalgoritmo puede devolver una correcta estimación de R.
4.4. Reconstrucción “euclídea”.
El algoritmo de los ocho puntos que hemos descrito usa como input un conjunto de ocho o máspuntos en correspondencia y devuelve la posición relativa (rotación y traslación) entre las dos cámarassalvo factor de escala α ∈ R+. Sin pérdida de generalidad, podemos suponer que α = 1, lo que equivalea normalizar el vector de traslación. En estas condiciones, la posición relativa y las correspondenciasentre los puntos se pueden utilizar para recuperar su configuración 3-D, calculando sus “profundidades”con respecto a las referencias de las cámaras.
Considérese la ecuación básica del sólido rígido, donde la posición (R, T ) es conocida, salvo factorde escala para T (α). En términos de las coordenadas de las imágenes y de profundidades, está dada por
λj2xj2 = λj1Rxj1 + αT, j = 1, 2, . . . , n.
Como (R, T ) son conocidos, las ecuaciones anteriores son lineales en los λ’s y α’s, y pueden resolversefácilmente. Para cada punto, λ1, λ2 son sus profundidades con respecto a la primera y la segunda refe-rencias de las cámaras, respectivamente. Una de ellas es redundante; por ejemplo, si se conoce λ1, λ2 essimplemente una función de (R, T ). Entonces, podemos eliminar , digamos, λ2 de la ecuación anterior,multiplicando ambos miembros por x2:
λj1xj2Rxj1 + αxj2T = 0, j = 1, 2, . . . , n.
Lo que es equivalente a resolver la ecuación lineal:
M jλj :=[
xj2Rxj1, xj2T
] [λj1α
],
donde M j =[
xj2Rxj1, xj2T
]∈ R3×2 y λj = [λj1, α]T ∈ R2, para j = 1, 2, . . . , n. Para que tenga
solución única, la matriz M j necesita tener rango igual a 1. Este caso no se da sólo cuando x2T = 0, esdecir, cuando el punto p pertenece a la recta que une los centros de las cámaras o1 y o2.
Definimos λ := [λ11, λ
21, . . . , λ
n1 , α]T ∈ Rn+1 y una matriz M ∈ R3n×(n+1) como:
M :=
x12Rx1
1 0 0 0 0 x12T
0 x22Rx2
1 0 0 0 x12T
0 0. . . 0 0
...
0 0 0 xn−12 Rxn−1
1 0 xn−12 T
0 0 0 0 xn2Rxn1 xn2T
.
Luego la ecuaciónMλ = 0
determina todas las profundidades salvo factor de escala.
4.5 Implementación en Matlab. 32
4.5. Implementación en Matlab.
En esta sección se recogen el código del algoritmo de los ocho puntos y de los algoritmos intermediosa los que llama.• Algoritmo lineal de los ocho puntos.
function [T0, R0] = essentialDiscrete(p,q)% estima la posición relativa de las cámaras a partir% de ocho correspondencias
n = size(p); NPOINTS = n(2);
% definimos una matriz A tal que A*[v1,v2,v3,s1,s2,s3,s4,s5,s6]’ = 0
A = zeros(NPOINTS, 9);
if NPOINTS < 9error(’No hay suficientes datos’)return;
end
for i = 1:NPOINTSA(i,:) = kron(p(:,i),q(:,i))’;end
r = rank(A);
if r < 8warning(’El rango de la matriz ha de ser 8’)T0 = 0; R = [];
end;
[U,S,V] = svd(A);
% elegir el vector propio que corresponde al valor propio más pequeñoe = V(:,9); e = (round(1.0e+10*e))*(1.0e-10);% matriz esencialE = reshape(e, 3, 3);
% así, las cuatro posibilidades sonRzp = [0 -1 0 ; 1 0 0 ; 0 0 1 ]; % rotación(pi/2)Rzn = [0 1 0 ; -1 0 0 ; 0 0 1 ]; % rotación(-pi/2)
[U,S,V] = svd(E); S = diag([1,1,0]); detu = det(U); detv = det(V);if detu < 0 & detv < 0
U = -U; V = -V;% break;
elseif detu < 0 & detv > 0S1 = Rzp*S;U = -U*rot_matrix([S1(3,2), S1(1,3) S1(2,1)],pi)*Rzp;
4.5 Implementación en Matlab. 33
V = V*Rzp;% break;
elseif detu > 0 & detv < 0S1 = Rzp*S;U = U*rot_matrix([S1(3,2), S1(1,3) S1(2,1)],pi)*Rzp;V = -V*Rzp;% break;
end
R(:,:,1) = (U*Rzp’*V’); Th(:,:,1) = (U*Rzp*S*U’); t(:,1) =[-Th(2,3,1), Th(1,3,1), -Th(1,2,1)]’; [omega(:,1),theta(1)] =exp_matrix(R(:,:,1)); R(:,:,2) = (U*Rzn’*V’); Th(:,:,2) =(U*Rzn*S*U’); t(:,2) = [-Th(2,3,2), Th(1,3,2), -Th(1,2,2)]’;[omega(:,2),theta(2)] = exp_matrix(R(:,:,2));
[U,S,V] = svd(-E); S = diag([1,1,0]); detu = det(U); detv = det(V);
if detu < 0 & detv < 0U = -U; V = -V;% break
elseif detu < 0 & detv > 0S1 = Rzp*S;U = -U*rot_matrix([S1(3,2), S1(1,3) S1(2,1)],pi)*Rzp;V = V*Rzp;% break
elseif detu > 0 & detv < 0S1 = Rzp*S;U = U*rot_matrix([S1(3,2), S1(1,3) S1(2,1)],pi)*Rzp;V = -V*Rzp;% break
end
R(:,:,3) = (U*Rzp’*V’); Th(:,:,3) = U*Rzp*S*U’; t(:,3) =[-Th(2,3,3), Th(1,3,3), -Th(1,2,3)]’; [omega(:,3),theta(3)] =exp_matrix(R(:,:,3)); R(:,:,4) = (U*Rzn’*V’); Th(:,:,4) =U*Rzn*S*U’; t(:,4) = [-Th(2,3,4), Th(1,3,4), -Th(1,2,4)]’;[omega(:,4),theta(4)] = exp_matrix(R(:,:,4));
index = 0; posdepth = zeros(1,4);
% =============================================================% elegir la solución correcta usando el criterio de profundidad positiva% calculando el volumen, que tiene que ser positivo si los dos escalares de% profundidad tienen el mismo signo y comprobar si uno de los dos tiene% signo positivo% =============================================================
for i = 1:4
4.5 Implementación en Matlab. 34
for j = 1:NPOINTS% c (a x b) (That*q)’*That*R*p > 0% si las profundidades tienen el mismo signo el producto triple% tiene que ser mayor que 0volume(j) = triple_product(t(:,i), R(:,:,i)*p(:,j), Th(:,:,i)*q(:,j));alpha1(j) = -(skew(q(:,j))*t(:,i))’*...(skew(q(:,j))*R(:,:,i)*p(:,j)) .../(norm(skew(q(:,j))*t(:,i)))^2;alpha2(j) = (skew(R(:,:,i)*p(:,j))*q(:,j))’*...(skew(R(:,:,i)*p(:,j))*t(:,i)) .../norm(skew(R(:,:,i)*p(:,j))*q(:,j))^2;
endvol = sum(sign(volume));depth = sum(sign(alpha1));depth2 = sum(sign(alpha2));% pauseposdepth(i) = vol + depth;
end % fin de todos los movimientos
[val, index] = max(posdepth);index_final = index;T0 = t(:,index);R0 = R(:,:,index);
•Matriz de rotación.
% calcula una matriz de rotación usando la fórmula de Rodrigues
function [rot_matrix] = rot_matrix(omega,theta) if nargin == 1theta = norm(omega);omega = omega/norm(omega);end; omega_hat = [0 -omega(3) omega(2);
omega(3) 0 -omega(1);-omega(2) omega(1) 0 ];
norm_omega = norm(omega); if (norm(omega) ~= 0) rot_matrix =diag([1,1,1])+(omega_hat./norm_omega).* sin(norm_omega*theta) ...
+ ((omega_hat^2)./norm_omega^2) .* (1 - cos(norm_omega*theta));else rot_matrix = diag([1 1 1]); end;
•Matriz exponencial.
%Toma una matriz de rotación y devuelve el ángulo y el eje
function[omega, theta] = exp_matrix(R) theta = 0; theta =acos((R(1,1) + R(2,2) + R(3,3)-1)/2);
if theta ~= 0 omega = 1/(2*sin(theta))*[R(3,2)-R(2,3) R(1,3)-R(3,1)R(2,1)-R(1,2)]’; else omega = [1 0 0]’; theta = 0;%error(’ Rotation matrix arbitrary’);end
4.5 Implementación en Matlab. 35
•Matriz antisimétrica.
% Dado un vector 3D devuelve su matriz antisimétrica asociada
function S_hat = skew(S)
S_hat = zeros(3,3);
S_hat(1,2) = - S(3); S_hat(1,3) = S(2); S_hat(2,3) = - S(1);
S_hat(2,1) = S(3); S_hat(3,1) = - S(2); S_hat(3,2) = S(1);
• Producto triple.
% producto triple de tres vectores (a x b) c% para calcular el volumen del paralelepípedo asociado
function[volume] = triple_product(a,b,c) volume = c(1)*(a(2)*b(3) -b(2)*a(3)) + c(2)*(a(3)*b(1) - b(3)*a(1)) + ...
c(3)*(a(1)*b(2) - b(1)*a(2));
Capítulo 5
Apéndice.
5.1. CCD
Un CCD (del inglés Charge-Coupled Device, “dispositivo de cargas (eléctricas) interconectadas”)es un circuito integrado que contiene un número determinado de condensadores enlazados o acoplados.Bajo el control de un circuito interno, cada condensador puede transferir su carga eléctrica a uno o avarios de los condensadores que estén a su lado en el circuito impreso. La alternativa digital a los CCDson los dispositivos CMOS (Complementary Metal Oxide Semiconductor) utilizados en algunas cámarasdigitales y en numerosas Webcam. En la actualidad, los CCD son mucho más populares en aplicacionesprofesionales y en cámaras digitales.
Popularmente, el término CCD es conocido por ser uno de los elementos principales de las cámarasfotográficas y de video digitales. En éstas, el CCD es el sensor con diminutas células fotoeléctricas queregistran la imagen. Desde allí la imagen es procesada por la cámara y registrada en la tarjeta de memoria.
La capacidad de resolución o detalle de la imagen depende del número de células fotoeléctricas delCCD, que se expresa en píxeles. Cuantos más píxeles, mayor es la resolución. Hoy en día, las cámarasfotográficas digitales incorporan CCDs con capacidades de hasta ciento sesenta millones de píxeles.
Los píxeles del CCD registran tres colores diferentes: verde, azul y rojo (abreviado “RGB”, delinglés Red, Green, Blue), por lo cual tres píxeles, uno para cada color, forman un conjunto de célulasfotoeléctricas capaz de captar cualquier color en la imagen. Por esto, la matriz de una imagen captadapor una cámara digital habitual no es una, sino tres, una para cada color.
5.2. Correspondencia y emparejamiento de puntos.
Supongamos que disponemos de dos imágenes de una escena tomadas desde diferentes puntos devista, por ejemplo las que se aprecian en la figura 5.2.
Si consideramos las coordenadas de un punto específico de la imagen izquierda, por ejemplo, el quehemos señalado con el cuadrado blanco. Es inmediato para el observador establecer cuál es su punto“correspondiente” de la imagen de la derecha. Decimos que ambos son correspondientes porque son losproyectados del mismo punto del espacio. Así, el problema de correspondencia consiste en establecerqué punto de la primera imagen se corresponde con qué punto de la segunda, en el sentido de que ambosson la imagen del mismo punto tridimensional.
El hecho de que el ser humano sea capaz de resolver este problema de forma tan fácil no nos de-bería hacer pensar que el proceso es trivial. Al contrario, los humanos utilizamos una gran cantidad deinformación a la hora de establecer las correspondencias, realizamos un análisis de las estructuras de laimagen, cómo están dispuestas, cuáles son próximas o colindantes, etc. Para darse cuenta de esto basta
5.2 Correspondencia y emparejamiento de puntos. 37
Figura 5.1: Sensor CCD.
intentar estalecer una correspondencia con sólo mirar las dos pequeñas regiones que quedan enmarcadasdentro de la circunferencia y el cuadrado de la figura 5.2. Lo que hace el ordenador es parecido a esto.
En los sistemas estéreo (y entre parejas de imágenes en las cuales la distancia del punto fijo a lascámaras es mucho mayor que la distancia entre los centros de las cámaras) se verifican dos hipótesisbásicas1:
1. muchos puntos de la escena son visibles en ambas imágenes,
2. las regiones que se corresponden son similares.
Por lo tanto, podemos mirar el problema de la correspondencia como un problema de búsqueda: dadoun elemento en la imagen izquierda, buscamos el elemento correspondiente en la imagen derecha. Estoconlleva dos decisiones:
¿Que elementos de las imágenes emparejar?
¿Que medida de similitud se debe adoptar?
Para responder a estas preguntas existen numerosos algoritmos de correspondencias, que emplean técni-cas de Estadística y de Optimización, y que podríamos dividir en dos tipos2:
1. basados en correlación: los elementos a emparejar son ventanas de la imagen de tamaño fijo, y elcriterio de similitud es una medida de la correlación entre las ventanas en las dos imágenes.
2. basados en características: intentan establecer correspondencias entre conjuntos dispersos de pun-tos de la imagen con las mismas características: esquinas, bordes...Existen numerosos algoritmospara detección de esquinas y bordes y emparejamiento de los puntos. Son los que se conocen comoalgoritmos de “matching” y “tracking”.
En el trabajo hemos supuesto dadas las correspondencias, pero en un problema real lo primero quehabría que hacer es correr estos algoritmos para obtener las correspondencias óptimas.
1En general, sin embrago, ambas hipótesis pueden ser falsas y el problema de la correspondencia puede muy difícil.2“A grosso modo”.
5.3 Vectores y matrices. 38
Figura 5.2: Los puntos “en correspondencia” de las dos vistas son los proyectados del mismo punto delespacio.
5.3. Vectores y matrices.
Definición 5.3.1 (Producto vectorial). Dados dos vectores u, v ∈ R3, su producto vectorial es otrovector perpendicular a ambos con coordenadas
u× v =
u2v3 − u3v2
u3v1 − u1v3
u1v2 − u2v1
∈ R3.
Definición 5.3.2 (Matriz antisimétrica). Una matriz A ∈ Rn×n se dice antisimétrica si AT = −A.
Nota 5.3.3 (Propiedades de una matriz antisimétrica). SiA es una matriz antisimétrica real, entonces:
Todos los valores propios de A son cero o imaginarios puros, es decir, son de la forma iω coni =√−1 y ω ∈ R.
Existe una matriz ortogonal V tal que A = V DV T con D matriz diagonal por bloques D =diagA1, . . . , Am, 0, . . . , 0, donde cada Ai es una matriz antisimétrica real 2× 2 de la forma
Ai =[
0 ai−ai 0
]∈ R2×2, i = 1, 2, . . . ,m.
Definición 5.3.4 (Matriz antisimétrica asociada a un vector). Dado u = [u1, u2, u3]T ∈ R3 se definesu matriz antisimétrica asociada como la matriz
u =
0 −u3 u2
u3 0 −u1
−u2 u1 0
∈ R3×3.
Nota 5.3.5. La matriz antisimétrica asociada a un vector es antisimétrica,es decir, uT = −u. Se definedel modo anterior porque si u, v ∈ R3 se tiene que uv = u× v. Si u 6= 0, el rango de u es dos. Tambiénse satisface que uu = 0 y que uT u = 0, es decir, las columnas y las filas de la matriz u son ortogonalesa u.
5.4 Movimientos del sólido rígido. 39
Figura 5.3: Un movimiento del sólido rígido preserva las distancia d entre dos cualesquiera de suspuntos, p, q.
Lema 5.3.6. Una matriz M ∈ R3×3 es anti-simétrica si y sólo si M = u para algún u ∈ R3.
Definición 5.3.7. Se define so(3) como el conjunto de las matrices antisimétricas de R3×3,
so(3) :=ω ∈ R3×3|ω ∈ R3
.
Por lo anterior, el espacio vectorial R3 y el espacio de las matrices 3 × 3 antisimétricas con coefi-cientes en R, so(3), son isomorfos. El isomorfismo viene dado por el llamado operador gorro:
∧ : R3 → so(3)u 7→ u,
su inverso es el operador “uve”, que obtiene las coordenadas del vector u a partir de una matriz antisi-métrica u:
∨ : so(3)→ R3
u 7→ u∨ = u.
5.4. Movimientos del sólido rígido.
Considérese un objeto moviéndose delante de una cámara. Queremos describir su movimiento. Enprincipio, parece que podríamos hacerlo especificando las coordenadas de sus puntos en función deltiempo, X(t). Afortunadamente, para los sólidos rígidos no necesitamos especificar el movimiento decada punto. Es suficiente, como veremos, especificar el movimiento de un punto y el movimiento de lostres ejes coordenados colocados en ese punto. La razón de esto es que en un sólido rígido la distanciaentre dos cualesquiera de sus puntos es constante(ver figura 5.3).
Definición 5.4.1. Un movimiento continuo del sólido rígido consiste en una familia de aplicacioneslineales que preservan las distancias entre los puntos del sólido y describen cómo cambian las coorde-nadas de cada uno de sus puntos en el tiempo. Denotamos cada aplicación como
g(t) : R3 → R3; X 7→ g(t) (X) .
Si en vez de preocuparnos por el movimiento continuo realizado por el objeto, nos fijamos sólo ensus posiciones inicial y final tenemos un desplazamiento del sólido rígido,
g : R3 → R3; X 7→ g (X) .
5.4 Movimientos del sólido rígido. 40
Figura 5.4: Un movimiento del sólido rígido entre el sistema de coordenadas de la cámara C : (x, y, z)y el del mundo W : (X,Y, Z).
Nótese que g también actúa sobre los vectores: si v es el vector definido por los puntos p, q concoordenadas respectivas X,Y, v = Y− X, su transformado es
u = g∗(v) := g (Y)− g (X) .
Como g conserva las distancias entre los puntos, tenemos que ‖g∗(v)‖ = ‖v‖ para todo vector v de R3.
Definición 5.4.2. Una aplicación que conserva las distancias se dice transformación euclídea.
Nota 5.4.3. Denotaremos E(3) el conjunto de todas las transformaciones euclídeas en R3.
Nota 5.4.4. Obsérvese que preservar las distancias entre los puntos no es una condición necesaria perono suficiente para caracterizar el movimiento de un objeto en el espacio. De hecho, hay transformacionesque mantienen las distancias y que son físicamente imposibles de realizar para el objeto. Por ejemplo,una reflexión en el plano XY . Para eliminar estos casos necesitamos imponer una condición más: quese conserven las orientaciones. Es decir, además de la norma de los vectores queremos que también sepreserve su producto vectorial.
Definición 5.4.5 (Movimiento del sólido rígido o transformación especial euclídea). Una aplicaciónlineal g : R3 → R3 es un movimiento del sólido rígido o una transformación especial euclídea sipreserva la norma y el producto vectorial,
norma: ‖g∗(v)‖ = ‖v‖, ∀v ∈ R3,
producto vectorial: g∗(u)× g∗(v) = g∗ (u× v) , ∀u, v ∈ R3.
¿Y cómo nos ayudan las propiedades anteriores a describir un movimiento del objeto? El hecho deque las distancias y las orientaciones se conserven por un movimiento del sólido rígido, quiere decir queun punto no se puede mover con respecto al resto. Como consecuencia, para describir un movimientode este tipo sólo necesitamos el de uno cualquiera de los puntos del objeto. Así fijaremos un sistemacoordenado en un punto p del objeto y observaremos el movimiento que ha experimentado con respecoal sistema de referencia externo (que llamaremos “del mundo” y denotaremos W ).
En la figura 5.4 mostramos un objeto, en este caso una cámara, moviéndose relativamente al sistemade coordenadas del mundo W : (X,Y, Z) fijado de antemano. Para especificar la posición de la cámaracon respecto a W , tomamos un punto o de la cámara y fijamos en él el sistema de referencia del objeto.En este caso, el sistema de coordenadas de la cámara, C : (x, u, z). Así, la configuración de la cámaraqueda determinada por:
5.4 Movimientos del sólido rígido. 41
la traslación de vector T con extremos el origen o de la referencia W y el de C, g(0);
la rotación R que ha experimentado la referencia C, con respecto a W .
Definición 5.4.6. Se dice que una matriz M es ortogonal si cumple MT = M−1.
Nota 5.4.7. De la definición se sigue que M ha de ser cuadrada y además con determinante +1 ó −1.
Definición 5.4.8. Se define el grupo especial ortogonal(de dimensión 3) como el grupo de las matricesortogonales de R3×3 que preservan la orientación, es decir,
SO(3) :=R ∈ R3×3|RTR = I, det(R) = +1
.
Es trivial que SO(3) satisface todos los axiomas de la definición de grupo3con el producto usual dematrices.
Teorema 5.4.9 (Fórmula de Rodrigues para una matriz de rotación). Dado ω ∈ R3, la matriz expo-nencial R = eω está dada por
ebω = I +ω
‖ω‖sin(‖ω‖) +
ω2
‖ω‖2(1− cos(‖ω‖)) .
Aplicando a un punto p0 ∈ R3 de coordenadas X0 una rotaciónR y luego una traslación T obtenemosX = RX0 +T . No hay duda de que esta transformación preserva las distancias y la orientación, es decir,es una transformación especial euclídea.
Definición 5.4.10. Se denomina grupo especial euclídeo el conjunto de todas las transformacioneseuclídeas
SE(3) :=g = (R, T )|R ∈ SO(3), T ∈ R3
.
O, lo que es lo mismo, pero en notación homogénea,
SE(3) :=g =
[R T0 1
]|R ∈ SO(3), T ∈ R3
.
Nota 5.4.11. Se tiene que ∀g1, g,2g ∈ SE(3),
g1g2 =[R1 T1
0 1
] [R2 T2
0 1
]=[R1R2 R1T2 + T1
0 1
]∈ SE(3)
y
g−1 =[R T0 1
]−1
=[RT −RTT0 1
]∈ SE(3),
luego SE(3) es un grupo.3Se denomina grupo al par (G, ∗) donde G es un conjunto y ∗ una operación cumpliendo:
(1) a ∗ (b ∗ c) = (a ∗ b) ∗ c ∀a, b, c ∈ G,(2) ∃e ∈ G tal que a ∗ e = e ∗ a = a ∀a ∈ G,(3) ∀a ∈ G ∃a−1 ∈ G g ∈ G tal que a ∗ a−1 = a−1 ∗ a = e.
5.5 Grupos y álgebras de Lie. 42
5.5. Grupos y álgebras de Lie.
Hemos creído conveniente incluir unos breves comentarios sobre variedades diferenciales porque suspropiedades se usan implicitamente a lo largo de todo el trabajo. En las referencias utilizadas apenas sehabla de la Geometría Proyectiva; las variedades diferenciales ni se mencionan.
Definición 5.5.1. Una variedad diferenciable de clase CK es un conjuntoM dotado de un atlas maximaltal que los cambios de carta son difeomorfismos de clase CK . Se llama dimensión de la variedad a ladimensión del espacio euclídeo Rn donde toman valores las cartas.
Nota 5.5.2. El conjunto de las matrices esenciales E posee estructura de variedad diferenciable4cincodimensional. Es por esto que se puede proyectar sobre él.
Definición 5.5.3. Un grupo de Lie G es una variendad diferenciable dotada de una esctuctura de grupotal que las funciones f(a, b) = ab y f(a) = a−1 son C∞.
Nota 5.5.4. Todos los grupos de matrices que han aparecido en el trabajo son grupos de Lie.
Definición 5.5.5. Un espacio vectorial V se denomina álgebra de Lie si en él está definido un conmuta-dor, es decir, una aplicación bilineal V× V→ V que satisface las siguientes condiciones:
1. [u, v] = −[v, u] ,
2. [[u, v], w] + [[w, u], v] + [[v, w], u] = 0, ∀u, v, w ∈ V.
Dos álgebras de Lie, V,V′, sobre un mismo cuerpo se dicen isomorfas si existe un isomorfismo linealφ : V→ V′ tal que consrva el conmutador, es decir, φ[u, v] = [φ(u), φ(v)]
Nota 5.5.6. Se tiene que R3 es un álgebra de Lie si tomamos el producto vectorial usual como conmu-tador. Lo mismo ocurre con so(3) tomando como conmutador AB − BA, A,B ∈ so(3). Por esto, elisomorfismo definido por el operador “gorro”,
∧ : R3 → so(3)u 7→ u
,
es un isomorfismo de álgebras de Lie.
También hemos empleado la notación exponencial para las matrices de rotación. Justificaremos estehecho a grandes rasgos5:
Los grupos de Lie están relacionados con las álgebras de Lie: a cada grupo de Lie se le asocia elespacio tangente en la identidad, que tiene estructura de álgebra de Lie6.
SO(3) es un grupo de Lie y su álgebra asociada es so(3).
Se define la aplicadión exponencial del álgebra de Lie en el grupo de Lie.
En el caso de los grupos de matrices la anterior aplicación coincide con la exponencial usual deuna matriz.
Quedando así justificado por qué la exponencial de una matriz antisimétrica es una matriz de rotación.4No incluimos la demostración de este hecho por no ser uno de los objetivos de este trabajo. Únicamente señalaremos que
para probarlo basta aplicar el teorema del rango para variedades diferenciables.5Ya que una justificación teórica rigurosa exigiría prácticamente la realización de otro trabajo.6Sin embargo, grupos de Lie distintos pueden tener álgebras de Lie isomorfas y existen álgebras de Lie que no están
asociadas a ningún grupo de Lie
Bibliografía
[1] LUIS BAUMELA, Curso de doctorado: “Visión por Computador”, Universidad Politécnica deMadrid (2004).
[2] DEPARTAMENTO DE ELECTRÓNICA DE LA UNIVERSIDAD DE ALCALÁ, Curso de doctorado:“Procesamiento digital de imágenes. Aplicaciones en robótica”, (2005-2006).
[3] FERNANDO ETAYO, Apuntes de Geometría Proyectiva, Universidad de Cantabria (2006-2007).
[4] FERNANDO ETAYO, Apuntes de Topología Diferencial, Universidad de Cantabria (2006-2007).
[5] R. I. HARTLEY, A. ZISSERMAN, Multiple View Geometry in Computer Vision, segunda edición,Cambrdige University Press (2004).
[6] Y. MA, S. SOATTO, J. KOSECKÁ, S. SHANKAR SASTRY, An Invitation to 3-D Vision, Springer-Verlag, New York (2004).
[7] DOMINGO MERY, Asignatura: “Visión por Computador”, Universidad Católica de Chile(2004).
[8] J. M. OLAZÁBAL, Procedimientos simbólicos en Álgebra Lineal, Universidad de Cantabria(1998).
[9] J. M. SANCHIZ, F. PLA, Curso de doctorado: Fundamentos de Visión por Computador, Uni-versitat Jaume I (2006).
[10] ALBERTO RUIZ, Apuntes de sistemas de percepción y Visión por Computador(5o de Informáti-ca), Universidad de Murcia (2004).
[11] B.N. SHAPUKOV, Grupos y álgebras de Lie en ejercicios y problemas, URSS, Moscú (2001).
Comentarios.
La cantidad de información que existe sobre la Visión por Computador, es, como cualquiera puedeimaginarse, inmensa. Ello, unido a nuestro desconocimiento inicial del área (al comienzo de este trabajonuestras bases partían de [3],[4],[8]) nos dificultó, en parte, la búsqueda inicial. Siempre encontrábamosinformación relacionada con los tópicos que nos ocupaban, pero, muchas veces, o no nos servía o noestábamos seguros de si era del todo correcta. Por ello, la búsqueda inicial nos llevó bastante tiempo.Tiempo que no fue perdido porque al final de este proceso habíamos adquirido una visión general delárea.
BIBLIOGRAFÍA 44
La primera aproximación al problema se realizó de la mano de asignaturas de doctorado o de licen-ciatura de otras universidades, [1]; [2]; [7], que recoge muy claramente la modelización geométrica delproblema; [9]; [10].
Una vez familiarizados con los conceptos básicos, pasamos a considerar el que ha sido nuestro librode cabecera, [6]. De él hemos tomado las principales definiciones y teoremas y la implementación de losalgoritmos.
Otro libro que nos ha sido muy útil es [5]. Algunos de sus capítulos están disponibles en la web, asícomo sus figuras.
Por último, señalar que las nociones de grupo y álgebra de Lie proceden de [11].
