Transformaciones 2D

1Un punto en dos sistemas de coordenadas

Pon un segundo sistema de coordenadas en el plano, con ejes x′ e y′. Su origen está en t′ = (t_x, t_y) y sus ejes están girados en un ángulo θ. Un punto tiene entonces dos juegos de coordenadas, m′ = [x′ y′ 1]^T en el sistema nuevo y m = [x y 1]^T en el antiguo, y una sola matriz convierte entre ellos:

Lee H columna por columna. La primera columna, (cos θ, sin θ), es el vector unitario del eje x′ escrito en las coordenadas antiguas, y la segunda, (−sin θ, cos θ), es el vector unitario del eje y′. La tercera es el nuevo origen t′. Así, Hm′ dice: parte en t′, avanza x′ unidades a lo largo del eje x′ e y′ unidades a lo largo del eje y′. El 1 al final de m′ es lo que suma t′. Sin esa tercera componente, una traslación no podría escribirse como un producto de matrices.

Por bloques, con R′ el giro de 2 × 2 en θ:

En el otro sentido

Para obtener m′ a partir de m, invierte H: m′ = H⁻¹m. No hace falta una inversión general. Las columnas de R′ son vectores unitarios perpendiculares, así que R′^TR′ = I: la inversa de R′ es su transpuesta, R = R′^T, que gira los puntos en −θ, lo mismo que girar los ejes en θ. Sus filas son los ejes nuevos, así que R da las coordenadas de un punto en los ejes girados. Deshaciendo primero la traslación y luego el giro, m′ = R(m − t′), se obtiene

En la figura, el nuevo origen es t′ = (3, 1) y el eje x′ apunta hacia (7, 4), cuatro unidades a la derecha y tres hacia arriba, así que cos θ = 0.8 y sin θ = 0.6. El punto (6, 5) está a (3, 4) del nuevo origen, así que

y en el sistema nuevo el punto está en (4.8, 1.4): 4.8 unidades a lo largo de x′ y 1.4 a lo largo de y′.

Agregar una escala

Si el sistema nuevo usa además otra unidad, de modo que una unidad a lo largo de x′ o y′ mide s unidades en el sistema antiguo, los dos vectores unitarios de H crecen en un factor s:

Esta es una transformación de similitud. Multiplica todas las longitudes por s pero conserva los ángulos, así que las figuras conservan su forma. Con s = 1 es la transformación euclídea de arriba, que además conserva las longitudes.

Convertir coordenadas o mover puntos

Hasta aquí el punto se quedó donde estaba y H convirtió sus coordenadas. El mismo producto se puede leer con un solo sistema de coordenadas: H mueve el punto que está en m′ al punto que está en m. El resto de esta página usa esa lectura, con los nombres intercambiados para que H lleve m a m′. Hacia dónde apunta H es una elección: H⁻¹ devuelve los puntos, y es una transformación del mismo tipo.

2Cuatro tipos de transformación

En general, H puede ser cualquier matriz invertible de 3 × 3. Lleva el punto m = [x y 1]^T al punto m′ dado por

El factor λ está ahí porque Hm no tiene por qué terminar en 1. Como con cualquier vector homogéneo, divide por la tercera componente para leer el punto; λ es esa tercera componente.

Las matrices de la sección 1 conservan la fila de abajo [0 0 1]. Liberar más entradas da transformaciones más flexibles, cuatro tipos en total, cada uno nombrado por lo que todavía conserva:

Cada tipo conserva además todo lo que conservan los tipos más flexibles: una transformación euclídea también conserva las rectas paralelas y las rectas.

¿De dónde salen las cuentas? La matriz euclídea tiene tres números libres, la de similitud agrega s, y la afín libera las seis entradas de sus dos filas de arriba. La matriz proyectiva tiene nueve entradas, pero λH lleva cada punto exactamente adonde lo lleva H, porque la división por la tercera componente cancela λ. Solo importan ocho números.

Por qué cada tipo conserva lo que conserva: un giro y una traslación mueven el plano como una pieza rígida, así que las longitudes se mantienen. Una escala multiplica todas las longitudes por el mismo s, así que se mantienen las razones de longitudes, y con ellas los ángulos. Con la fila de abajo [0 0 1], no se divide nada, y la transformación es una aplicación lineal más una traslación. Lleva cada dirección d a una única dirección nueva Ad, con A el bloque de 2 × 2 de arriba a la izquierda, así que las rectas que compartían dirección siguen compartiéndola y siguen paralelas; pero A puede estirar unas direcciones más que otras, así que los ángulos cambian. Una fila de abajo proyectiva hace que la división final dependa del punto, y la sección 3 muestra qué le hace eso a las rectas paralelas.

La razón de cruz

¿Qué conserva una transformación proyectiva, además de las rectas? Las longitudes a lo largo de una recta cambian, y también sus razones, pero hay una razón de razones que no cambia. Para cuatro puntos A, B, C y D sobre una recta, su razón de cruz es

donde AC es la distancia de A a C. Para los puntos en 0, 1/4, 1/2 y 1 del lado de arriba del cuadrado vale (1/2 · 3/4) / (1/4 · 1) = 1.5, y sigue valiendo 1.5 se transforme como se transforme el cuadrado.

Aplicar una transformación tras otra es un producto de matrices: primero H₁ y luego H₂ es H₂H₁. Dos transformaciones de un tipo dan una tercera del mismo tipo, igual que dos giros dan un giro.

3La foto de una superficie plana

Las transformaciones proyectivas aparecen cada vez que una cámara fotografía algo plano, como una pared, una página o un piso. Pon el centro de la cámara C en el origen, su plano de imagen a distancia f₁ delante de él, y una superficie plana a distancia f₂. Cada punto de la superficie llega a la imagen por la recta que pasa por C, así que la foto de la superficie es una aplicación de un plano en otro.

Si la superficie mira a la cámara, paralela al plano de imagen, todos sus puntos están a la misma distancia, y los triángulos semejantes achican toda la superficie por el mismo factor f₁/f₂. La aplicación de la superficie en la foto es una similitud:

Inclina la superficie en φ en torno a una recta horizontal que pasa por su centro, con su parte de arriba alejándose. Mide sus puntos (u, v) desde su centro, con u hacia la derecha y v hacia abajo, como se cuentan las filas de una imagen, y los (x, y) de la foto de la misma manera. El punto (u, v) queda entonces a la profundidad f₂ − v sin φ: la mitad de arriba, donde v es negativo, está más lejos. La cámara divide la posición de cada punto por su profundidad. Esa división es exactamente lo que hace una fila de abajo en H:

La tercera componente, λ, es la profundidad. Las partes de la superficie más lejanas a la cámara salen más chicas, y la foto es una transformación proyectiva de la superficie. En la figura, f₁ = 1, f₂ = 3, y la superficie es un cuadrado de 3 × 3 baldosas. Su lectura divide H por f₂, para que termine en 1; como mostró la sección 2, eso no mueve ningún punto.

Las rectas siguen siendo rectas

Incluso el tipo más flexible conserva las rectas, y el producto punto muestra por qué. Un punto m está en la recta ℓ cuando ℓ^Tm = 0. Pon H⁻¹H = I en el medio:

Así, todos los puntos de ℓ caen en una misma recta, ℓ′ = H^−Tℓ, donde H^−T es la transpuesta de H⁻¹. Los puntos se mueven con H, y las rectas con H^−T. En la imagen de las coordenadas homogéneas, donde un punto es una recta que pasa por el origen y una recta es un plano que pasa por el origen, H es una aplicación lineal del espacio: lleva rectas por el origen a rectas por el origen, y planos a planos.

Las rectas paralelas pueden cortarse

Las rectas paralelas se cortan en un punto en el infinito, [p q 0]^T, donde (p, q) es su dirección. Aplícale H:

Si la fila de abajo de H es [0 0 1], como en los tres primeros tipos, la tercera componente sigue siendo 0, y las rectas siguen paralelas. Con una fila de abajo proyectiva vale 0 para una sola dirección, y las rectas paralelas en cualquier otra dirección se llevan a rectas que se cortan en un punto común y corriente, su punto de fuga: el punto de una foto donde se juntan los rieles de una vía recta. En la figura, los bordes de las baldosas que se alejan de la cámara tienen dirección (0, 1) sobre la superficie, así que se cortan en el punto en el infinito [0 1 0]^T, y en la foto en H[0 1 0]^T. Los bordes transversales, de dirección (1, 0), se cortan en [1 0 0]^T, que H lleva a un punto que sigue terminando en 0, así que siguen paralelos.

La foto de una escena plana no es la única fuente de homografías. Dos fotos tomadas desde un mismo lugar, con la cámara girada, también se relacionan por una, sea cual sea la profundidad de la escena, porque las líneas de visión que pasan por el centro común son las mismas para ambas fotos. La sección 5 usa eso para unir fotos.

4Estimar H a partir de cuatro pares

A menudo H es desconocida, pero se conocen algunos pares de puntos correspondientes. Para enderezar la foto de un letrero, marca sus cuatro esquinas en la foto, m′₁ a m′₄, y emparéjalas con las esquinas de un cuadrado, m₁ a m₄. Cada par m ↔ m′ da dos ecuaciones. Como H solo importa salvo escala, fija h₃₃ = 1, lo que deja 8 incógnitas, y divide por la tercera componente de Hm:

La división hace que estas ecuaciones no sean lineales en las incógnitas, pero multiplicar ambos lados por el denominador las vuelve lineales:

Apila las incógnitas en h = [h₁₁ h₁₂ h₁₃ h₂₁ h₂₂ h₂₃ h₃₁ h₃₂]^T. Cada par agrega entonces dos filas a un sistema lineal Ah = b:

Cuatro pares dan ocho ecuaciones para las ocho incógnitas, así que cuatro es el mínimo, y entonces h = A⁻¹b. Tres de los cuatro puntos no pueden estar sobre una misma recta; si lo están, A es singular y no se encuentra una única H. La H que se obtiene así lleva cada píxel de la imagen enderezada al lugar de la foto que muestra, que es justo lo que necesita la transformación de una imagen (sección 5). Si un clic está corrido, H igual se ajusta exactamente a los cuatro pares, y el letrero enderezado sale torcido: la figura te deja verlo.

Más de cuatro pares

Los puntos medidos nunca son exactos, así que en la práctica se usan más pares de los necesarios. Con n > 4 pares, A tiene 2n filas y ningún h las cumple todas. Los mínimos cuadrados toman el h que hace más chicos los errores al cuadrado ‖Ah − b‖². Igualar su derivada a cero da A^TAh = A^Tb, y de ahí la solución por mínimos cuadrados

La matriz A^TA es de 8 × 8 sin importar cuántos pares haya, así que el sistema a resolver sigue siendo chico.

Fijar h₃₃ = 1 falla en un caso: cuando el h₃₃ verdadero es 0, lo que ocurre cuando H manda el origen de las coordenadas al infinito. El método general deja las nueve entradas como incógnitas, agrega −x′ y −y′ como novena columna de A, y resuelve Ah = 0 con ‖h‖ = 1. La respuesta es el vector singular derecho de A con el menor valor singular, la última fila de V^T en la SVD. Cuando h₃₃ ≠ 0 y los pares se ajustan exactamente, como ocurre con cuatro, da la misma H salvo escala. Con más pares que no se ajustan exactamente, los dos métodos miden el error de manera distinta, así que sus respuestas difieren un poco.

5Transformar una imagen

Para transformar una imagen completa, cada píxel del resultado necesita un valor de gris. En coordenadas de píxel, x cuenta columnas hacia la derecha e y cuenta filas hacia abajo. Sea I′ la imagen original e I el resultado. En la figura, el resultado es la imagen original agrandada 1.5 veces y girada en 20°.

Ir hacia adelante, enviando cada píxel del original adonde cae en el resultado, parece lo natural, pero falla. El lugar donde cae rara vez es el centro de un píxel, y después de redondear, algunos píxeles del resultado reciben dos píxeles del original y otros ninguno. Cuando la imagen se agranda, la mayoría no recibe ninguno: en la figura, la imagen original agrandada cubre 124 píxeles del resultado, pero sus 64 píxeles llenan solo 56 de ellos (los otros 8 caen fuera del borde del resultado), y 68 quedan como agujeros.

Por eso la transformación va hacia atrás. Escribe H de modo que λm′ = Hm lleve cada píxel del resultado m al lugar m′ del original que muestra, y para cada píxel del resultado calcula m′ y lee el original ahí. Cada píxel del resultado pregunta de dónde viene y obtiene exactamente una respuesta, así que no quedan agujeros. Los puntos sobre el original en la figura son esas respuestas, uno por cada píxel del resultado.

Una respuesta m′ = (x′, y′) rara vez es el centro de un píxel, así que el valor hay que leerlo entre los cuatro píxeles del original que la rodean. Llámalos I′₁ (arriba a la izquierda), I′₂ (arriba a la derecha), I′₃ (abajo a la izquierda) e I′₄ (abajo a la derecha). Hay dos maneras comunes.

Píxel más cercano. Toma el valor del más cercano de los cuatro. Es rápido, pero los bordes salen dentados.

Interpolación bilineal. Mezcla los cuatro. El punto m′ divide el cuadrado entre sus centros en cuatro rectángulos, con áreas A (arriba a la izquierda), B (arriba a la derecha), C (abajo a la izquierda) y D (abajo a la derecha). Cada píxel se pondera por el área del rectángulo opuesto:

¿Por qué el rectángulo opuesto? A medida que m′ se acerca a I′₁, el rectángulo D opuesto crece hasta llenar todo el cuadrado. Así, un punto justo sobre un píxel toma exactamente el valor de ese píxel, y entre medio el valor cambia suavemente. Las cuatro áreas suman el cuadrado completo, 1, así que una región de gris constante conserva su gris.

Cuando m′ cae fuera de la imagen original, no hay nada que leer, y el píxel del resultado queda vacío, normalmente como 0.

Unir fotos en un mosaico

Un panorama se arma con fotos tomadas desde un mismo lugar mientras la cámara gira. Como mostró la sección 3, esas fotos se relacionan por una homografía, así que una se puede transformar sobre la otra. Son cuatro pasos, que ponen a trabajar las secciones 4 y 5.

1. Encontrar puntos distintivos. Un detector de puntos clave como SIFT encuentra esquinas y manchas en cada foto, y describe el parche alrededor de cada una con un vector. Los vectores se construyen para que el mismo lugar visto en la otra foto tenga uno parecido.
2. Emparejarlos. Para cada punto clave de una foto, busca los dos vectores más parecidos en la otra. Quédate con el par solo si el mejor está mucho más cerca que el segundo. Esta prueba de la razón descarta lugares que se parecen a muchos otros, como una ventana en una fila de ventanas.
3. Estimar H de forma robusta. Algunos pares siguen siendo erróneos después de la prueba de la razón, y un solo par malo puede alejar mucho la H de mínimos cuadrados. RANSAC lo evita: elige cuatro pares al azar, calcula H exactamente a partir de ellos, y cuenta cuántos de todos los pares lleva esta H a pocos píxeles de su pareja. Repite muchas veces, quédate con la H con más de esos pares consistentes (inliers), y refínala por mínimos cuadrados solo con ellos. Los apuntes de calibración de cámaras muestran RANSAC en acción.
4. Transformar sobre un lienzo más grande. Escribe H de modo que lleve puntos de la segunda foto a la primera. Enviar las esquinas de la segunda foto a través de H muestra dónde cae, y algunas esquinas pueden caer en coordenadas negativas o más allá de los bordes de la primera foto. Una traslación T que deje todas las esquinas a la vista lo arregla. Una traslación es también una homografía, así que la segunda foto va al lienzo a través del producto TH, y la primera a través de T sola. Para llenar el lienzo, cada uno de sus píxeles lee la segunda foto a través de (TH)⁻¹, hacia atrás como antes.

6Resumen

Las ideas clave junto a sus equivalentes en NumPy y OpenCV.