¿Cómo deshacer el cuadrilátero en rectángulo?

tl; dr: Problema matemático en geometría proyectiva: ¿Cómo se puede encontrar una matriz de cámara 4x4 que proporcione una proyección como se ilustra a continuación, de modo que los puntos A, B, C, D estén en algún lugar en los bordes de la caja de la unidad (por ejemplo, dispositivo normalizado OpenGL coordenadas), y las esquinas de la caja de la unidad caen en algún lugar razonable a lo largo de los rayos EA, EB, EC, ED?

(Este puede ser un caso especial posiblemente de una homografía, una perspectiva y / o una colación. No está familiarizado con la terminología).

elaboración

Dado un cuadrilátero ABCD dentro de la ventana gráfica, creo que existe una transformación única (?) Que la asigna de nuevo a un rectángulo. Como se ve en la imagen a continuación: el cuadrilátero ABCD en la ventana gráfica actúa como una 'ventana' física, y si lo asignamos de nuevo a un rectángulo, aparecerá distorsionado.

(el cuadro de la derecha representa NDC, de lo que hablo más adelante)

El objetivo es obtener rápidamente la imagen de la derecha. Podríamos rastrear cada punto para obtener la imagen (lo que he hecho), pero preferiría usar OpenGL u otras técnicas proyectivas porque quería aprovechar cosas como mezclas, primitivas, etc.

primer intento

Creo que puedo resolver el problema de encontrar la matriz de cámara 3x4 que hace que la coordenada homogénea 3 + 1-dimensional en 3 espacios (a la izquierda) y la proyecte a las coordenadas homogéneas 2 + 1 dimensionales en 2-espacio (en la derecha). Uno puede resolver esto usando la transformación lineal directa para obtener un sistema de ecuaciones Ba=0para las entradas desconocidas ade la matriz de la cámara, y resolviendo el sistema usando la descomposición de valores singulares(SVD). Tomaría los vectores EA, EB, EC, ED (donde E es su ojo físico o la cámara en el espacio mundial) como puntos en la imagen previa, y (0,0), (1,0), (1 , 1), (0,1) o algo así como los puntos en la imagen posterior, y cada par de puntos daría unas pocas ecuaciones lineales para conectar a la SVD. La matriz resultante mapearía EA -> (0,0) etc. (suponiendo que haya suficientes grados de libertad, es decir, si la solución es única, de lo que no estoy seguro, vea la nota [a]).

Pero para mi disgusto, así no es cómo funciona OpenGL. OpenGL no proyecta directamente 3d a 2d con una matriz 3x4. OpenGL requiere "coordenadas de dispositivo normalizadas" (NDC), que son puntos tridimensionales. Después de proyectar en NDC, se dibuja todo en el cuadro 'unidad' desde (-1, -1, -1,1) hasta (1,1,1,1); todo el exterior está recortado (ya que estamos tratando con coordenadas homogéneas: cualquier punto (x, y, z, w) aparecerá solo en la pantalla solo si las primeras tres coordenadas de (x / w, y / w, z / w , 1) están dentro del cuadro de unidad de -1 a 1).

Entonces la pregunta es: ¿existe alguna transformación razonable que mapee algún cuboide de aspecto extraño en coordenadas homogéneas (específicamente el cuboide dibujado a la izquierda, con ABCD (puntos frontales) y A'B'C'D '(puntos posteriores, ocultos detrás de los puntos frontales)) al cubo de la unidad, por ejemplo, usando una matriz 4x4? ¿Cómo se hace?

lo que he intentado

He intentado algo más fuerte: hice que ABCD y A'B'C'D 'parecieran un frustrum piramidal normal (por ejemplo, gl frustrum) (es decir, en esta configuración hipotética, la imagen de la izquierda solo tendría un rectángulo negro superpuesto en no es un cuadrilátero), y luego usó la DLT / transformación lineal directa para resolver la supuesta matriz 4x4. Sin embargo, cuando lo probé, no parecía haber suficientes grados de libertad ... la matriz 4x4 resultante no asignó cada vector de entrada a cada vector de salida. Mientras uso A, B, C, D, A '(5 pares de vectores pretransformados y postransformados), I / casi / obtengo el resultado que quiero ... los vectores se asignan correctamente, pero por ejemplo B', C ', D' se asignan a (3,3,1,1) en lugar de (-1, -1,1,1) y OpenGL los recorta. Si trato de agregar un sexto punto (6 pares de puntos para la matriz 4x4 para proyectar), mi solución parece degenerada (ceros, infinitos). ¿Con cuántos grados de libertad estoy lidiando aquí? ¿Es esto posible con una matriz 4x4 que mapee los 4 vectores habituales (vectores de coordenadas homogéneas de 3 + 1 dimensiones) que conocemos y amamos?

pensamientos menores al azar

Supongo que no es posible asignar ningún cuboide arbitrario a cualquier cuboide arbitrario con una matriz 4x4, aunque estoy confundido porque pensé que era posible asignar cualquier cuadrilátero convexo a cualquier otro cuadrilátero convexo en 2D con alguna matriz como en , por ejemplo, Photoshop? ... ¿puede / no puede hacerse esto con una transformación proyectiva? ¿Y cómo se generaliza a 3d? ...... También dado el intento fallido de encontrar una matriz 4x4, el álgebra lineal dice que no deberíamos esperar que una matriz NxN mapee más de N puntos linealmente independientes a N puntos objetivo en el mejor de los casos, pero siento que de alguna manera es homogéneo las coordenadas engañan esto porque hay una cierta colinealidad oculta? ¿Supongo que no?

¿otra solución?

Supongo que uno también podría hacer lo siguiente feo, donde usa una matriz típica de proyección de cámara frustrum, encuentra los puntos 2d correspondientes a las esquinas, luego realiza una homografía de distorsión de perspectiva 2d, pero si eso sucediera después de que se renderizaran los píxeles (por ejemplo, Photoshop), entonces habría problemas con la resolución ... ¿tal vez hipotéticamente se podría encontrar una matriz para realizar esta transformación en el plano XY dentro del espacio NDC, y luego componerla con la matriz basada en frustrum normal?

(nota [a]: Grado de libertad: ABCD se puede restringir aún más para que sea la imagen posterior de una transformación proyectiva que actúa sobre un rectángulo, si eso es necesario ... podría decirse que el rectángulo negro de la izquierda es el resultado de proyectar un modelo de imágenes prediseñadas de marco de imagen)

Creo que la solución está buscando la transformación proyectiva que transforme correctamente los cuatro puntos.

es decir

$x' = [x_0, x_1, 1]$$y = [\frac{y'_0}{y'_2}, \frac{y'_1}{y'_2}]$

$P$

Ahora puede usar álgebra para hacer esto, o simplemente usar OpenCV's getPerspectiveTransform:).

Consulte también las coordenadas homógenas en wikipedia para familiarizarse con el concepto.

Resolví mi propia pregunta implementando la transformación lineal directa . La sección de ejemplos en Wikipedia fue mi caso de uso.

Para obtener las ecuaciones, conecte las matrices (p [x1 x2 x3 x4; x5 x6 x7 x8; x9 x10 x11 x12]. Ej. ) En su sistema de álgebra de computadora favorito como SageMath, luego resuelva la ecuación de matriz requerida como se ilustra, copie y pegue las soluciones en términos de variables en su código y ajuste el formato.

Entonces, uno podría adaptar la solución al caso de uso de uno escalando o ignorando dimensiones particulares según corresponda (por ejemplo, ignorar la coordenada de profundidad / z en la matriz de Coordenadas de dispositivo normalizadas según corresponda al caso de uso).

Necesitará una función de descomposición SVD o una biblioteca en su idioma.