UNIVERSIDAD POLITÉCNICA DE MADRID

ESCUELA TÉCNICA SUPERIOR DEINGENIEROS DE TELECOMUNICACIÓN

PROYECTO FIN DE CARRERA

SISTEMA DE AUTOCALIBRACIÓN DE CÁMARAS

Y RECONSTRUCCIÓN 3D

Autor: Guillermo Gallego Bonete-mail: ggb@gti.ssr.upm.es

Tutor: José Ignacio Ronda PrietoDepartamento: Señales, Sistemas y Radiocomunicaciones

Fecha de lectura: 23 de febrero de 2004Calicación: Matrícula de Honor, 10p.

Sistema de Autocalibración de Cámaras yReconstrucción 3D

1. IntroducciónEl presente proyecto está englobado dentro del campo de la visión articial, la cual pretende emular elcomportamiento de la visión humana utilizando una cámara como sensor y un ordenador como proce-sador. Suponemos que se dispone de un conjunto de imágenes digitales o una secuencia de vídeo quereeja una escena estática. El objetivo del proyecto es fascinante: sólo con la información contenida en lasimágenes, obtener un modelo en tres dimensiones de la escena y las características de la cámara con quefueron adquiridas las imágenes. Suponemos que se desconoce la posición espacial de la cámara respectode la escena (parámetros extrínsecos), así como los parámetros intrínsecos de la misma.

Los dos elementos principales del título del proyecto ya han sido presentados: el término autocalibraciónsignica obtener los parámetros que denen la cámara (distancia focal, punto principal, posición del espa-cio, etc.) sin ningún conocimiento a priori de la escena adquirida, mientras que el término reconstrucción3D signica obtener un modelo tridimensional de la escena bajo estudio: forma y localización de losobjetos que están delante de la cámara.

Las herramientas necesarias para lograr el citado objetivo son: el tratamiento digital de imágenes, lageometría proyectiva y las técnicas de optimización. El tratamiento digital de imágenes permite extraerla información adecuada de las proyecciones de la escena, características tales como puntos y/o rectas.Esto reduce el problema a uno puramente geométrico. La geometría proyectiva permite crear modelossencillos que describen el sistema de formación de la imagen en la cámara y plantear diversos algoritmospara invertir dicha operación. Las técnicas de optimización consiguen que dichos algoritmos sean útilesdesde el punto de vista numérico y práctico.

No es objeto del proyecto la extracción de características de las imágenes digitales de partida, ni su corres-pondencia entre imágenes, ni la representación tridimensional de la escena reconstruida mediante malladoy pegado de texturas. El proyecto se centra en abordar las etapas intermedias entre estos extremos.

Me gustaría resaltar que este proyecto no está precedido de ninguno otro en la escuela: es innovador yaque la teoría de autocalibración de cámaras y reconstrucción 3D es muy reciente. Durante su elaboración,he podido desarrollar mis habilidades e imaginación en temas no habituales de los ingenieros de telecomu-nicación, lo que constituye un primer acercamiento a mi tarea investigadora, reejada en las aportacionescitadas en el capítulo 1.

El ejemplo del capítulo 8 es muy ilustrativo y se recomienda su consulta en caso de que el lector se sientaabrumado por los capítulos intermedios. Así no se pierde de vista el objetivo nal.

2. Planteamiento del problema y modelo utilizadoEn adelante, suponemos que ya han sido detectados ciertos puntos entre imágenes y puestos en corres-pondencia, a través de algún algoritmo de seguimiento. A partir de este número nito de característicaspretendemos resolver nuestro problema, además de imponer ciertas restricciones, si no sería imposiblereconstruir nuestro mundo físico, ya que su complejidad es innitamente superior a la complejidad de lasmedidas que podamos hacer en las imágenes.

Habitualmente, la resolución del problema planteado se divide en varias etapas y los posibles resultadosintermedios de cada una de ellas son lo que se conoce como una reconstrucción proyectiva o una recons-trucción afín de la escena. Estas fases reciben el nombre de reconstrucción o calibración estraticada.Ambas reconstrucciones están relacionados con la reconstrucción nal, denominada reconstrucción euclí-dea o métrica, mediante una transformación geométrica del espacio: proyectiva o afín, respectivamente.Las transformaciones proyectivas también reciben el nombre de homografías.

1

Todos somos conscientes de que perdemos una dimensión al proyectar el mundo real sobre una ima-gen: pasamos de un mundo 3D al mundo 2D de las imágenes. Nuestra misión es tratar de recuperar estadimensión perdida, inferirla a partir de varias proyecciones, tomadas desde distintas posiciones del espacio.

Una cámara es un dispositivo que realiza esta proyección del mundo tridimensional al mundo de las imá-genes. Este proceso es complejo porque intervienen muchos elementos: un conjunto de lentes se utilizapara dirigir la luz de tal forma que incida sobre un dispositivo CCD y se convierta la información en bits,etc. Los fundamentos ópticos de la formación de la imagen habitualmente suponen un modelo ideal decámara de ojo de aguja (pinhole): lente delgada o na cuya apertura tiende a cero, lo que simplica elanálisis porque despreciamos los efectos de difracción y reexión de las lentes, quedándonos con el modelomás sencillo de refracción en el que todos los rayos pasan por el centro óptico de la lente.

El modelo matemático más popular que describe esta operación es el de cámara proyectiva o proyec-ción cónica, por lo que sus elementos básicos son el plano de proyección o plano de la imagen y el centrode proyección. Son necesarios varios cambios de referencia, tanto en el espacio como en el plano paraestablecer una correspondencia precisa entre puntos del espacio 3D, expresados respecto de un sistemade referencia global jo, y sus proyecciones en la imagen, expresadas respecto de un sistema de referencialocal a la imagen. La ecuación que determina las proyecciones en las imágenes, x = (x, y, 1)>, de lospuntos 3D, X = (X, Y, Z, 1)>, se expresa en coordenadas homogéneas (geometría proyectiva) de formalineal: x ∼ PX, donde el símbolo ∼ signica igualdad salvo proporcionalidad.

La cámara se modela mediante su matriz de proyección, P de 3× 4, que contiene la matriz de parámetrosintrínsecos, K, que a su vez depende de 5 parámetros: distancia focal, αv, relación de aspecto de los píxelesτ = αu/αv, ángulo θ entre los lados de los píxeles (skew), punto principal1 (u0, v0)> y los parámetrosextrínsecos: rotación R y traslación C respecto de un sistema de referencia del mundo 3D.

P = K[I | 0]He =

ταv −ταv cot θ u0

0 αv/ sen θ v0

0 0 1

1 0 0 00 1 0 00 0 1 0

[R t0> 1

]= KR[I | −C]

También se utilizará un modelo mejorado que añade parámetros en la cámara que modelan la distorsiónradial, que constituye la desviación más relevante respecto del modelo lineal. En la práctica, este errores más acusado cuanto menor es la distancia focal y peor es la calidad de la lente. Es posible corregir ladistorsión radial producida en las imágenes para seguir utilizando la suposición de cámara lineal.

Con los elementos que ya han sido presentados podemos formalizar el problema más general de lareconstrucción 3D de la forma siguiente: dadas m imágenes con las proyecciones xi

ji=1,...,m;j=1,...,n den puntos (convenientemente identicados uno en cada imagen como correspondientes al mismo punto delespacio), queremos hallar las posiciones de estos puntos en el espacio y los parámetros de las cámaras,es decir, las coordenadas Xjj=1,...,n de los puntos y las matrices y vectores Ki, Ri, Cii=1,...,m talesque xi

j ∼ Ki[Ri| − RiCi]Xj . Esta reconstrucción es posible salvo una transformación de semejanza, la cual

incluye un escalado, una rotación y una traslación.

La presencia de errores en la posición de las proyecciones xij hace interesante plantear el problema en

términos de estimación estadística. Un planeamiento natural consiste en identicar el problema con laminimización de la función de coste de máxima verosimilitud conocida como error de reproyección:2

∑

i,j

d2(xij , Ki[Ri| − RiCi

]Xj),

Se trata por tanto de un problema de optimización no lineal con un número elevado de variables queno es resoluble mediante técnicas genéricas de optimización. La estrategia para resolver el problemapasa por dividirlo en subproblemas que se puedan resolver mediante factorización de matrices o pro-blemas de optimización factibles. Posteriormente estos resultados pueden renarse mediante técnicas de

1El punto principal es la intersección del eje óptico de la lente con el plano de la imagen.2d representa la distancia euclídea en el plano de la imagen.

2

optimización que busquen la minimización de la función de coste anterior o una aproximación a la misma.

El esquema de procesamiento completo desde que se dispone de las imágenes hasta que se visualizala reconstrucción en tres dimensiones consta de los siguientes pasos:

1. Extracción de las características de las imágenes y su correspondencia.2. Calibración proyectiva de las cámaras. Una reconstrucción proyectiva es una reconstrucción de la

escena que está relacionada con la reconstrucción real mediante una transformación geométrica delespacio llamada homografía.

3. Autocalibración. Dada una calibración proyectiva de las cámaras, obtener una transformación delespacio para convertir una reconstrucción proyectiva en una reconstrucción métrica o euclídea.

4. Optimización de la calibración euclídea obtenida, minimizando el error de reproyección.5. Presentación de la reconstrucción. La información de la calibración euclídea de las cámaras y las

posiciones de los puntos 3D se combina con la información de texturas de las imágenes para construirun modelo tridimensional de la supercie del mundo real y visualizarlo mediante algún programade realidad virtual.

Muchos algoritmos de autocalibración realizan hipótesis sobre los valores de algunos parámetros intrínse-cos de las cámaras, en otras ocasiones se imponen restricciones en lugar de conocer esos valores. Algunasde estas suposiciones son:

Todas las cámaras comparten los mismos parámetros intrínsecos, constantes, pero desconocidos.Cámaras con píxeles de forma conocida o cuadrados, es decir, θ = π/2 y τ = 1.El punto principal de la cámara es conocido o está en el origen de coordenadas.

La hipótesis de píxeles cuadrados es más cercana a la realidad que la hipótesis de punto principal enel origen. La posición del punto principal puede variar signicativamente de una imagen a otra, ambastomadas con la misma cámara; sin embargo la relación de aspecto y el skew son parámetros jos debidosa la construcción del dispositivo CCD de las cámaras digitales. Éste no cambia de una imagen a otra.

3. Geometría ProyectivaLa geometría euclídea describe localmente nuestro mundo tridimensional. En ella, los lados de los objetostienen longitudes, las líneas que se intersecan determinan ángulos entre ellas, y se dice que dos líneasson paralelas si pertenecen al mismo plano y nunca se cortan. Además, estas propiedades no cambiancuando aplicamos las transformaciones euclídeas (traslación y rotación). Sin embargo, no es el único tipode geometría. La geometría euclídea es en realidad un subconjunto de lo que se conoce como geometríaproyectiva. De hecho, hay dos geometrías entre ambas: la geometría del grupo conforme formado por lassemejanzas y la geometría afín.

La geometría proyectiva modela bien el proceso de adquisición de imágenes en una cámara porque permi-te una clase más amplia de transformaciones que sólo traslaciones y rotaciones. Estas transformacionespreservan el tipo (los puntos siguen siendo puntos y las rectas se transforman en rectas), la incidencia(esto es, si un punto pertenece a una recta) y la razón doble, pero no mantiene otras medidas: longitu-des, ángulos, paralelismo, etc. La geometría proyectiva existe para cualquier dimensión, al igual que lageometría euclídea. Por ejemplo la recta proyectiva, que denotamos por P1, es análoga al mundo euclídeounidimensional; el plano proyectivo, P2, se corresponde con el plano euclídeo; y el espacio proyectivo,P3, está vinculado con el espacio euclídeo tridimensional. El proceso de formación de la imagen es unaproyección de P3 en P2.

El propósito del capítulo 3 es hacer autocontenido el documento e instruir al lector sobre los elementosgeométricos básicos tales como puntos, rectas, planos, cónicas, cuádricas, cúbicas, etc. y las operacionesentre los mismos. Todo esto se utilizará para resolver nuestro problema, según mostramos a continuación.

El paso de autocalibración consiste en determinar la estructura afín o la estructura euclídea de la escenadada una reconstrucción proyectiva de la misma. Esto se logra si identicamos unos objetos geométricos

3

especiales: el plano del innito, π∞ y la cónica absoluta Ω∞ u objetos equivalentes.

El plano del innito contiene la información del paralelismo (dos rectas o planos son paralelos si se cortanen el innito) y la razón simple de longitudes. Si identicamos este plano en la reconstrucción proyectivade la escena, podemos construir una transformación espacial que coloque el plano del innito en su posi-ción correcta en una referencia euclídea. Del mismo modo, la cónica absoluta, que es una cónica especialcontenida en el plano del innito, contiene la información de ortogonalidad de la escena. Si identicamosesta cónica, podremos recticar la reconstrucción proyectiva de tal forma que seamos capaces de medirángulos y longitudes (habremos denido un producto escalar).

Los siguientes objetos son equivalentes a los dos anteriores, es decir, contienen la información de ambos: lacuádrica absoluta dual, Q∗∞, que es el conjunto de todos los planos tangentes a Ω∞ y la cuádrica absolutade rectas, Σ, que es el conjunto de todas las rectas tangentes a Ω∞.

Otros objetos con información de ortogonalidad son: la PAC o IAC, que es la proyección o imagen de lacónica absoluta sobre el plano de la imagen de una cámara, expresada por ωi = (KiKi>)−1 y la DIAC, dualde la imagen de la cónica absoluta, cuya ecuación es ω∗i = KiKi> y es la imagen de Q∗∞ en la cámara i.Tanto la IAC como la PAC son cónicas que se utilizan mucho en autocalibración, ya que sólo dependende la matriz de parámetros intrínsecos y es la información que se desea recuperar.

4. Estimación de homografías entre imágenesLas homografías del plano (las transformaciones lineales 2D más generales) tienen muchas aplicaciones:corrección de la distorsión perspectiva de una imagen, creación de imágenes panorámicas a partir devarias imágenes, autocalibración de una cámara rotatoria, etc. Sin embargo, el objetivo de este capítulono es aprender a estimar homografías, sino introducir la teoría de estimación de transformaciones u otrasentidades geométricas a partir de ciertas medidas u observaciones. Se dan los fundamentos para estimar:homografías 2D a partir de pares de puntos en dos imágenes, matrices de proyección a partir de pares depuntos 3D y 2D, la matriz fundamental entre dos imágenes dadas unas parejas de puntos entre ambas, etc.

En la memoria se aplica la teoría de la estimación de forma estructurada en el sentido de que en cadacapítulo se plantean uno o varios problemas de estimación de cierto objeto o transformación y siempre seproporcionan los siguientes métodos: primero un algoritmo lineal basado en la técnica de mínimos cua-drados propuesta por Gauss, después varios algoritmos no lineales basados en la minimización de ciertafunción de coste algebraico o geométrico mediante el algoritmo de LevenbergMarquardt (una modica-ción del método de Newton) y por último, un algoritmo robusto de estimación frente a datos atípicos(outliers), basado en la técnica RANSAC (RANdom SAmple Consensus).

Los algoritmos lineales utilizan técnicas estándar de álgebra lineal: principalmente la descomposición enautovalores y autovectores o la descomposición en valores singulares. Se utilizan para obtener una prime-ra solución que inicialice algoritmos no lineales. Para que los algoritmos sean numéricamente estables esnecesario normalizar los datos y no se debe descuidar la desnormalización de los resultados.

Los algoritmos no lineales persiguen la minimización de una función de coste o distancia mediante esque-mas iterativos, habitualmente fundamentados en la suposición de que la función a minimizar es localmentecuadrática. Estos algoritmos son muy útiles porque permiten imponer las restricciones propias que de-be satisfacer la geometría de la solución mediante una parametrización adecuada del espacio de soluciones.

El marco descriptivo común de estos algoritmos consta de los siguientes elementos: un vector de pa-rámetros P ∈ RM (variables independientes respecto a las cuales minimizar), un vector de medidasX ∈ RN (variables dependientes) con matriz de covarianzas ΣX, una función modelo f : RM → RN ,cuyo recorrido es, localmente, el conjunto de medidas permitidas y una función de coste a minimizar, quese expresa como el cuadrado de la distancia de Mahalanobis: ‖X−f(P)‖2ΣX = (X−f(P))>Σ−1

X (X−f(P)).

Este capítulo también proporciona los fundamentos para calcular analíticamente cotas del rendimiento delos algoritmos de máxima verosimilitud, mediante los conceptos de error residual y error de estimación,

4

bajo la hipótesis de ruido gaussiano en los datos. Esto es muy útil para evaluar la calidad de los resultadosde los algoritmos programados respecto de los resultados del algoritmo óptimo o de máxima verosimilitud.

5. Matriz de ProyecciónAntes de pasar a la calibración proyectiva de cámaras es necesario saber caracterizar las matrices deproyección que las representan. En el capítulo 5 se describen los elementos que componen una cámaraproyectiva en una reconstrucción euclídea y la información recogida en la matriz de proyección de unacámara. También se incluyen varios algoritmos de estimación de una matriz de proyección a partir decorrespondencias de puntos del espacio y del plano: el algoritmo lineal y el algoritmo no lineal de máximaverosimilitud (Gold Standard) que minimiza el error de reproyección en una imagen. Esta operación seconoce como resección.

Como ya se ha indicado, una matriz de proyección en un sistema de referencia euclídeo se puede descom-poner de la forma: P = KR[I | −C]. Contemos los grados de libertad: 5 parámetros intrínsecos, 3 grados delibertad de la rotación y 3 de la traslación (posición del centro óptico), 11 en total. Este número coincidecon los grados de libertad de una matriz de 3 × 4 arbitraria denida salvo proporcionalidad, que es lacaracterización de una cámara en una reconstrucción proyectiva arbitraria.

Sólo si la submatriz formada por las tres primeras columnas de P es regular, la cámara recibe el nombrede cámara proyectiva nita y es lícito descomponerla para obtener la matriz de parámetros intrínsecos K,la orientación R y la posición de la cámara C. Esto caracteriza las cámaras en reconstrucciones euclídeas.También se describen las matrices de rotación para encontrar parametrizaciones adecuadas de las mismas.Existen distintas alternativas: ángulos de Euler, exponencial de una matriz antisimétrica o eje de rotacióny ángulo de giro alrededor del eje.

6. Calibración proyectivaEl capítulo 6 afronta el problema de obtener una calibración proyectiva de las cámaras a partir de lascorrespondencias de puntos (y a veces, rectas) entre las imágenes. Está organizado de la siguiente manera:primero se supone la existencia de sólo 2 cámaras y se estudia la geometría de la escena, la geometríaepipolar, que nace de la restricción epipolar y da lugar a relaciones bilineales entre las correspondenciasde puntos en las imágenes: las matrices fundamental y esencial. A continuación se estudia la geometríade tres cámaras, que da lugar a relaciones bilineales entre parejas de cámaras y relaciones trilineales, eltensor trifocal, al considerar las tres cámaras a la vez. Seguimos aumentando el número de cámaras, estavez a cuatro y se presenta la geometría involucrada, aparecen relaciones bilineales, trilineales y cuadrili-neales entre las correspondencias de puntos: surge el tensor cuadrifocal.

Si seguimos aumentando el número de cámaras la complejidad aumenta y se parametriza el problemade forma directa mediante las matrices de proyección y las coordenadas de los puntos 3D de los queprovienen los puntos observados: no interesa obtener ningún tensor de mayor dimensión. Aparece latécnica del ajuste de haces como preponderante en estas situaciones.

6.1. Geometría de dos cámarasLas matrices esencial y fundamental describen completamente las relaciones geométricas entre puntoscorrespondientes de un par de cámaras estéreo. La única diferencia entre las dos es que la primera se usacon cámaras calibradas, mientras que la segunda se utiliza en caso de cámaras no calibradas. La matrizesencial contiene cinco parámetros (tres que denen la rotación y dos para la dirección de traslación) ytiene dos restricciones: (1) su determinante vale cero, y (2) sus dos valores singulares no nulos son iguales.La matriz fundamental contiene siete parámetros: una matriz de 9 elementos, salvo proporcionalidad ysalvo la restricción de rango dos: 9− 1− 1 = 7.

Dadas n ≥ 7 parejas de puntos correspondientes entre dos imágenes podemos estimar la matriz funda-mental, F, utilizando varios algoritmos:

5

1. Solución exacta con n = 7 parejas de puntos.2. Método lineal con n ≥ 8 parejas de puntos e imposición a posteriori de la condición de singularidad.3. Método no lineal que minimiza el error algebraico dentro de la variedad de las matrices singulares.4. Método no lineal que minimiza el error de reproyección en las dos imágenes (Gold Standard).5. Estimación robusta basada en RANSAC.

La anterior lista establece una jerarquía de algoritmos: la estimación de la matriz fundamental es mejora medida que descendemos en la lista. Una limitación de la calibración proyectiva es que la solución esúnica a falta de una homografía del espacio, es decir, que el conocimiento de la matriz F no nos permiteobtener la estructura euclídea del espacio.

Dada una matriz fundamental es posible obtener una calibración proyectiva de las dos cámaras involu-cradas. También es posible y fácil el paso inverso: la obtención de la matriz fundamental a partir de lasmatrices de proyección de las dos cámaras.

6.2. TriangulaciónLa triangulación consiste en el cálculo la posición de un punto 3D del espacio dadas sus proyecciones endos imágenes y las matrices de proyección de ambas cámaras. Bajo la hipótesis de existencia de ruido,los rayos retroproyectados (rectas con origen en el centro óptico de cada cámara y que pasan por loscorrespondientes puntos en cada imagen) no se cortarán, en general, por lo que hay que estimar unamejor aproximación al punto 3D. Esto requiere denir una función de coste a minimizar.

En la memoria se tratan dos algoritmos de triangulación: uno lineal y otro, estimador óptimo, cuyasolución se obtiene sin una minimización iterativa. La reconstrucción es más able cuanto mayor sea elángulo entre los rayos retroproyectados que pasan por las correspondientes proyecciones de un mismopunto 3D.

6.3. Geometría de tres cámarasEl tensor trifocal T juega un papel análogo en tres imágenes al que juega la matriz fundamental en dos.Dadas tres proyecciones, encapsula todas las relaciones geométricas (proyectivas) independientes de laestructura de la escena. El tensor sólo depende del movimiento entre las cámaras y de los parámetrosintrínsecos de las mismas y está denido unívocamente por las matrices de proyección. Para que el tensorsea geométricamente válido (compatible con tres matrices de proyección) es necesario que satisfaga 8restricciones algebraicas propias.

Dadas n ≥ 6 correspondencias de puntos entre tres imágenes existen métodos numéricos para estimarel tensor trifocal asociado, sin necesidad de conocer el movimiento o la calibración. En concreto, se handesarrollado los siguientes algoritmos:

1. Método de cálculo exacto del tensor Trifocal dadas las proyecciones de 6 puntos en 3 cámaras.2. Método lineal para n ≥ 7 puntos, que no es capaz de imponer las restricciones propias del tensor.3. Método iterativo que minimiza el error algebraico e impone las restricciones propias del tensor.4. Método iterativo que minimiza el error de reproyección entre las 3 imágenes (Gold Standard).5. Estimación robusta basada en RANSAC.

El segundo y tercer método permiten estimar el tensor mediante relaciones de incidencia entre rectas oentre puntos y rectas. Esta es una ventaja que tiene el tensor trifocal sobre la matriz fundamental. Unavez estimado el tensor trifocal, es fácil calcular las matrices de proyección y así obtener la calibraciónproyectiva de tres cámaras.

También se puede utilizar el tensor para transferir puntos y rectas: si conocemos el tensor y la proyecciónde un punto o recta en dos imágenes, podemos calcular la proyección correspondiente del punto o rectaen la tercera imagen.

6

6.4. Geometría de cuatro cámarasEl tensor cuadrifocal Q juega un papel análogo en cuatro imágenes al que juega la matriz fundamental endos y el tensor trifocal en tres. Para que el tensor sea geométricamente válido (compatible con cuatromatrices de proyección) es necesario que satisfaga 51 restricciones algebraicas propias.

Dadas n ≥ 6 correspondencias de puntos entre cuatro imágenes, se han desarrollado los siguientes algo-ritmos para estimar el tensor cuadrifocal asociado:

1. Método lineal, que no es capaz de imponer las restricciones propias del tensor.2. Método lineal de Heyden, que sí impone las restricciones propias del tensor.3. Dos métodos no lineales que minimizan el error algebraico a la vez que satisfacen todas las restric-

ciones del tensor.

No se ha implementado el algoritmo que minimiza el error reproyección para el caso particular de 4 cáma-ras, sino para el caso general de un número arbitrario de cámaras, que es la técnica conocida como ajustede haces. Este algoritmo es el de máxima verosimilitud y proporciona los mejores resultados posibles.

Los métodos 1 y 3 también permiten estimar del tensor mediante correspondencias de rectas o correspon-dencias mixtas de puntos y rectas. Hay más combinaciones posibles que en el caso del tensor trifocal. Esinmediato calcular las matrices de proyección a la vez que se estima el tensor cuadrifocal. Así se disponede la calibración proyectiva de cuatro cámaras.

6.5. Geometría multicámaraEsta sección está dedicada a los algoritmos de calibración proyectiva en caso de m > 2 cámaras. La orga-nización es la siguiente: primero se introduce el ajuste de haces y se explica cómo inicializar este algoritmomediante una calibración proyectiva previa. Después se aplican los conocimientos del RANSAC para crearun ajuste de haces proyectivo robusto. Por último, se complica el modelo introduciendo la estimaciónde la distorsión radial en las cámaras. Con estos algoritmos pretendemos conseguir una reconstrucción ocalibración proyectiva óptima, tanto incluyendo distorsión radial como sin incluirla.

La técnica del ajuste de haces consiste en la estimación de las matrices de proyección Pi y los puntos 3DXj tales que minimizan la distancia entre el punto reproyectado xi

j ∼ PiXj y el punto observado xij , es

decir, el error de reproyección:

mınPi

,Xj

m∑

i=1

n∑

j=1

d2(PiXj ,xij)

Las matrices de proyección no tienen necesariamente que ser las de una cámara proyectiva nita porquetodavía se está considerando un mundo proyectivo, no euclídeo. Se llama ajuste de haces porque implicaajustar los haces de rayos entre cada centro óptico de cada cámara y el conjunto de puntos 3D paraconseguir las proyecciones xi

j más verosímiles a las observadas xij .

El ajuste de haces debería, en general, ser utilizado como el paso nal de cualquier algoritmo de recons-trucción. Este método tiene la ventaja de ser tolerante si se pierden datos a la vez que proporciona unaauténtica estimación de máxima verosimilitud.

Para comenzar la optimización del ajuste de haces es necesario una fase previa que proporcione una cali-bración proyectiva inicial. El objetivo es obtener una aproximación inicial a las matrices de proyección detal forma que todas estén expresadas en una misma referencia proyectiva espacial. Una buena estrategiaconsiste en estimar la matriz fundamental entre dos imágenes, obtener sus matrices de proyección, utilizarun algoritmo de triangulación para obtener los puntos 3D y estimar las matrices del resto de cámarasmediante resección. Hay varias combinaciones: ya que existen tanto algoritmos lineales como óptimospara cada paso.

Este paso de obtención de la calibración proyectiva inicial tiene que ser lo sucientemente bueno comopara que el ajuste de haces posterior tenga una optimización fácil. Como en todos los algoritmos deoptimización, es deseable que el punto de partida caiga dentro de la zona de atracción del mínimo. Sin

7

embargo no debe ser demasiado costoso obtener el punto de partida, ya que la optimización posteriorpuede ser más rápida.

Una vez que se dispone de una calibración proyectiva inicial, se aplica el ajuste de haces que optimizamediante un algoritmo de LevenbergMarquardt particionado y disperso adaptado al problema. Estopermite una cómoda minimización en un espacio de parámetros de grandes dimensiones.

Si la calibración proyectiva inicial no es buena, es muy costoso realizar una ajuste de haces con todos lospuntos y cámaras desde un principio. Por eso se ha ideado una estrategia robusta basada en RANSACpara mejorar la ecacia.

También se ha diseñado un ajuste de haces proyectivo con distorsión radial, incluyendo los parámetrosde distorsión radial de las matrices de proyección en el espacio de parámetros. En este caso, la función decoste a minimizar es el error de reproyección de los puntos proyectados y distorsionados respecto de lospuntos medidos en las imágenes. Este error puede ser menor que el error de reproyección de la proyecciónlineal porque hay más grados de libertad, sin embargo, en las buenas cámaras como las utilizadas paralas pruebas experimentales casi no se nota, ya que la distorsión radial es despreciable.

Respecto a las pruebas experimentales, sólo me gustaría destacar que se ha comprobado que las cotasteóricas de los algoritmos de máxima verosimilitud se cumplen, no sólo cualitativamente, sino cuanti-tativamente. Esto indica que se ha alcanzado el objetivo de implementar algoritmos óptimos para lacalibración proyectiva.

7. AutocalibraciónLa autocalibración consiste en la obtención los parámetros de las cámaras dada una calibración proyectivade las mismas. Al contrario que la calibración, no se utiliza ningún patrón (ej. rejilla de calibración en elespacio) ni objeto cuyas dimensiones sean conocidas, sólo la información contenida en las imágenes.

Para conseguir una reconstrucción euclídea es necesario identicar el plano del innito π∞ y la cónicaabsoluta Ω∞ contenida en él, o de forma equivalente identicar las otras dos cuádricas con la mismainformación, Q∗∞ o Σ, mencionadas en el capítulo 2. Todos los algoritmos de autocalibración persiguen laestimación de estos objetos geométricos especiales haciendo ciertas hipótesis sobre los parámetros de lascámaras. Conociendo estos objetos, podemos hallar una transformación H que convierta la reconstrucciónproyectiva actual en una reconstrucción más restrictiva: afín o conforme, conservando las proyecciones:

Pi,Xj −→ PiH, H−1Xj

xij ∼ PiXj = (PiH)(H−1Xj) = PiXj .

Existen dos formas de determinar H: de una sola vez o en dos pasos (estraticadamente). En la calibraciónestraticada el paso costoso es el primero: determinar el plano del innito π∞; el segundo paso es lineal.

En este capítulo se describen varios algoritmos de autocalibración, que comentamos brevemente. El al-goritmo de cámaras ortogonales consiste en suponer que las cámaras poseen píxeles cuadrados y puntoprincipal en el origen de coordenadas, lo que permite estimar la cuádrica absoluta dual mediante unalgoritmo lineal. Las ecuaciones de Kruppa son restricciones en dos imágenes para las que sólo hacefalta conocer la matriz fundamental F y consisten en dos ecuaciones cuadráticas independientes para loselementos de la DIAC, ω∗. La restricción unimodular es una ecuación polinómica en las coordenadas delplano del innito para cámaras con mismos parámetros intrínsecos. Hay varios algoritmos para estimarla cuádrica absoluta dual Q∗∞ y la DIAC de cada cámara a la vez. Todos ellos se basa en la ecuación deproyección de la cuádrica absoluta dual sobre el plano de la imagen: ω∗i ∼ PiQ∗∞Pi>.

También se consideran algoritmos de autocalibración basados en la curva horóptera que se dene entrecada par de cámaras con idénticos parámetros intrínsecos. Esta curva es el lugar geométrico de los puntosdel espacio que se ven igual desde las dos cámaras, por lo que sólo depende del movimiento entre las cá-maras y de los parámetros intrínsecos de las mismas. La horóptera corta al plano del innito π∞ en tres

8

puntos con una conguración característica respecto de la cónica absoluta. Explotando esta disposición,es posible estimar el plano del innito y la cónica absoluta.

Por último, se consideran los algoritmos de autocalibración que estiman la cuádrica absoluta de rectas (elCalibration Pencil) para cámaras con píxeles cuadrados. Esta cuádrica ha sido recientemente introducidaen la literatura por el grupo en el que realicé el proyecto n de carrera y es objeto de investigación. Enla actualidad desarrollamos algoritmos no lineales de estimación de la misma basados en su proyecciónsobre el plano de la imagen, ya que nos publicaron el algoritmo lineal en el IEEE ICIP04.

8. Reconstrucción euclídeaEl siguiente paso en el esquema de procesamiento consiste en optimizar la reconstrucción euclídea queproporciona el algoritmo de autocalibración (posiciones de los puntos 3D y los parámetros de las matricesde proyección). El capítulo 8 indica cómo obtener una reconstrucción euclídea inicial y cómo renarlamediante un ajuste de haces euclídeo.

Supongamos que ya se ha realizado la autocalibración, entonces la la situación de partida está formadapor las matrices de proyección modicadas por la homografía que transforma lo proyectivo en lo euclídeo,junto con los puntos 3D asociados. Una vez que se dispone unas matrices de cámaras proyectivas nitas, sepuede pasar a optimizar la calibración euclídea. Para ello se ha diseñado un ajuste de haces euclídeo paracámaras con píxeles de forma conocida (τ = 1 y θ = π/2). El algoritmo emplea una parametrización delas matrices de proyección que permite optimizar sin salirse del espacio de soluciones que son matrices deproyección euclídeas. La función de coste a minimizar es el error de reproyección presentado al principiode la memoria (capítulo 2).

Una gran parte de este capítulo está dedicado al cálculo exacto de la matriz jacobiana que utiliza elalgoritmo de LevenbergMarquardt durante la optimización. Este cálculo se fundamenta en la composiciónde funciones para aprovechar al máximo lo que ya se conoce sobre el ajuste de haces proyectivo.

8.1. Un ejemplo completoVeamos en un ejemplo cómo los algoritmos descritos a lo largo de la memoria sirven para reconstruiruna escena 3D dadas unas imágenes de datos reales. Con una cámara digital doméstica modelo NikonCoolpixr 3700 se tomaron 23 fotografías del Patio de los Reyes en el interior del Monasterio de SanLorenzo de el Escorial. Todas las imágenes fueron adquiridas sin utilizar el zoom de la cámara, así quese supone que los parámetros intrínsecos son constantes, salvo variaciones debidas al auto-enfoque. Sedesconoce la matriz de parámetros intrínsecos. La gura 1 muestra dos imágenes de la secuencia.

Se conoce un poco más de la cámara: la distancia focal equivalente empleada durante la adquisición delas imágenes fue de 35 mm (la cámara permite variar la distancia focal entre 35 y 105 mm). Sin embargo,no utilizaremos este conocimiento a durante la calibración.

Se parte de unas correspondencias de puntos extraídos de forma semi-automática y el objetivo consiste enobtener una reconstrucción euclídea de la escena y una calibración euclídea de las cámaras minimizandoel error de reproyección, según se presentó en el capítulo 2. Seguiremos el esquema de procesamiento dadoen ese mismo capítulo:

1. Obtener la calibración proyectiva de las dos cámaras extremas (la N 1 y la N 23) y los puntos 3Dmediante el algoritmo Gold Standard para la matriz fundamental (capítulo 6).

2. Estimar las matrices de proyección de las cámaras intermedias (números 2 a 22) mediante el algo-ritmo Gold Standard para la resección (capítulo 5).

3. Optimizar la calibración proyectiva existente mediante el ajuste de haces proyectivo, minimizandoel error de reproyección (capítulo 6).

4. Utilizar un algoritmo de autocalibración para calcular el plano del innito y la matriz de parámetrosintrínsecos. En el ejemplo se ha utilizado el primero de los algoritmos de estimación de la cuádricaabsoluta dual y la DIAC (capítulo 7).

9

Figura 1: Ejemplo con datos reales: imágenes 12 (izquierda) y 21 (derecha) de la secuencia del Patio delos Reyes situado en el interior del Monasterio de San Lorenzo de el Escorial, con las correspondenciasde puntos superpuestas (cruces).

5. Actualizar la reconstrucción: construir la homografía del espacio que rectica los puntos 3D y lasmatrices de proyección, es decir, los convierte en datos métricos (capítulo 7).

6. Optimizar la calibración euclídea actual mediante el ajuste de haces euclídeo, imponiendo la res-tricción de píxeles cuadrados a la vez que se minimiza el error de reproyección (capítulo 8).

Tras el ajuste de haces euclídeo se puede representar la reconstrucción 3D de la escena (gura 2). Paraello hay que unir los puntos 3D mediante una malla triangular y pegar las texturas de las imágenes sobrelos triángulos. Esta descripción permite navegar por la escena 3D reconstruida si se utiliza un visualizadorde realidad virtual.

Figura 2: Reconstrucción 3D de la escena en el Patio de los Reyes, en VRML.

También se mide objetivamente la calidad de la reconstrucción calculando el error de reproyección norma-lizado por el número de medidas, que indica el error medio por cada coordenada de los puntos observadosy se calcula según la expresión:

ε2res =

12mn

m∑

i=1

n∑

j=1

d2(PiXj ,xij).

Los errores RMS de reproyección tras cada etapa signicativa del esquema de procesamiento son losmostrados en el cuadro 1. Estos resultados indican que la desviación típica del ruido presente en lospuntos observados es inferior a 1 píxel. Aunque se ha impuesto la condición de píxeles cuadrados en laúltima etapa, el error sigue siendo muy pequeño, lo que justica la hipótesis de píxeles cuadrados.

10

Etapa εres (píxeles)Calibración proyectiva inicial 0,7399Tras el ajuste de haces proyectivo 0,5508Calibración euclídea inicial (píxeles cuadrados) 1,5878Tras el ajuste de haces euclídeo 0,5528

Cuadro 1: Ejemplo con datos reales: errores de reproyección en cada etapa del esquema de procesamiento.

Sólo hacen falta 7 iteraciones del algoritmo de Levenberg-Marquardt en cada uno de los ajuste de hacesproyectivo y euclídeo para converger a la solución deseada, lo que indica que el punto de partida es muybueno: cae dentro del pozo de atracción del mínimo.

Considérense las dimensiones del problema: m = 23 cámaras y n = 162 puntos implican que la optimiza-ción de la calibración proyectiva se hace dentro en un espacio de parámetros de dimensión 762, es decir,se busca el mínimo en R762 y ½se consigue en sólo 7 iteraciones del algoritmo LM! El ajuste de haceseuclídeo no se queda atrás, el espacio de parámetros es de dimensión 693.

La salida del ajuste de haces euclídeo son las matrices de proyección y los puntos 3D métricos que mini-mizan el error de reproyección. De las matrices de proyección podemos extraer las matrices de parámetrosintrínsecos de cada imagen (en ellas se cumple que los píxeles son cuadrados, como impone el ajuste dehaces). Por ejemplo, las matrices de parámetros intrínsecos de las cámaras N 12 y N 21 son:

K12 =

1157,9 0 21,40 1157,9 −13,30 0 1

, K21 =

1173,7 0 −21,60 1173,7 −29,90 0 1

.

En ambas matrices, el punto principal está expresado respecto del centro de la imagen, es decir, el píxelde coordenadas [512, 384] respecto del sistema de referencia habitual de las imágenes (esquina superiorizquierda).

Además, se ha aplicado el ajuste de haces proyectivo con distorsión radial y el error de reproyecciónobtenido es εres = 0,5367 píxeles, menor que el error de reproyección sin distorsión radial, como erade esperar, pero la mejora no es espectacular. Los parámetros de distorsión de las cámaras 12 y 21están recogidos en el cuadro 2. Para cada cámara, se han utilizado cuatro coecientes en el polinomio dedistorsión radial y las dos coordenadas del centro de distorsión. Como se aprecia en el error de reproyeccióny en los parámetros de la cámara, la distorsión radial casi no tiene importancia. Por ejemplo, para lacámara N 12 hay que situar muy lejos del centro de la imagen el centro de distorsión para disminuir elerror de reproyección. En cambio, para la imagen N 21, el centro de distorsión radial no está tan alejadodel centro de la imagen y los coecientes son mayores que los de la otra cámara, aunque siguen siendopequeños.

Parámetro Cámara N 12 Cámara N 21xc −706,17 −145,90yc 110,60 −130,95κ1 8,246 · 10−6 2,934 · 10−6

κ2 1,167 · 10−8 −5,700 · 10−8

κ3 −1,564 · 10−11 −1,043 · 10−10

κ4 4,745 · 10−15 1,936 · 10−13

Cuadro 2: Parámetros de distorsión radial de las dos cámaras consideradas.

No se debe olvidar que se está evaluando en el punto más propenso a la distorsión, ya que si las imágeneshubiesen sido adquiridas con cualquier otra distancia focal de las que admite la cámara, la distorsiónobservada sería menor.

11

9. Resumen y trabajo futuroA lo largo de la memoria se han descrito e implementado numerosos algoritmos de calibración proyectiva,clasicados es tres tipos: lineales, no lineales y robustos. Proporcionan diversidad de combinaciones paraobtener la calibración proyectiva de las cámaras a partir de las coordenadas de los puntos y/o rectas enlas imágenes. Dicha calibración proyectiva se puede optimizar mediante un ajuste de haces: una técnicamuy beneciosa para etapas posteriores (autocalibración, etc.). También se ha diseñado un ajuste dehaces euclídeo particularizado para cámaras con píxeles cuadrados.

Los algoritmos descritos permiten obtener la reconstrucción tridimensional de una escena estática y losparámetros de las cámaras sólo mediante la información contenida en las imágenes que ésta adquiere, se-gún se ha demostrado en el ejemplo del capítulo 8. Sólo resta automatizar la extracción de característicasde las imágenes y la representación 3D, en lugar de utilizar herramientas semi-automáticas, de tal formaque sea fácil procesar secuencias de vídeo.

Una vez que se dispone de un esquema completo de autocalibración y reconstrucción 3D se puede daruna segunda pasada y renar más algunos pasos. Por ejemplo, habría que evaluar si es posible atajar elproblema de la calibración euclídea desde el principio: en lugar de establecer dos pasos separados, tratarde realizar en un esquema conjunto la calibración proyectiva y la autocalibración euclídea.

Durante el proyecto, a medida que se iban implementando más y más algoritmos surgió la idea de darforma y sentido al conjunto, completarlo para así crear una librería de rutinas de calibración que sirvieracomo base sólida para futuros proyectos en el campo de la visión por ordenador. Puedo decir, con gransatisfacción, que este objetivo se ha cumplido.

12