Mapeo de un cuadrilátero irregular a un rectángulo

Question

Tengo una cámara mirando el monitor de una computadora desde varios ángulos. Como la cámara es una cuadrícula de píxeles, puedo definir los límites del monitor en la imagen de la cámara como:

Espero que eso tenga sentido. Lo que quiero hacer es crear un algoritmo para traducir los puntos dentro de esta forma a esto:

Tengo puntos dentro del mismo dominio que el ABCD, según lo determinado por la cámara, pero necesito dibujar estos puntos en el dominio de la resolución del monitor.

¿Tiene sentido? ¿Alguna idea?

Answer 1

En general, no existe ninguna transformación afín que mapee un cuadrilátero arbitrario en un rectángulo. Pero hay (exactamente una) transformación proyectiva $T$ que mapea un cuadrilátero determinado $(A, B, C, D)$ en el plano proyectivo sobre un cuadrilátero dado $(A', B', C' D')$ en el mismo u otro plano proyectivo. Este $T$ es ${\it collinear}$ es decir, mapea líneas a líneas. Para hacer los cálculos hay que introducir coordenadas homogéneas $(x,y,z)$ tal que $D=(0,0,1)$ , $C=(1,0,1)$ , $A=(0,1,1)$ , $B=(1,1,1)$ y de forma similar para $A'$ , $B'$ , $C'$ , $D'$ . Con respecto a estas coordenadas el mapa $T$ es lineal y su matriz es la matriz identidad.

Answer 2

La mejor solución que he encontrado hasta ahora en un foro perdido en el mar de foros es descomponer tu problema así :

Aquí, U y V representan coordenadas dentro del cuadrilátero (escaladas entre 0 y 1).

Desde $P0$ , $P1$ , $P2$ & $P3$ podemos calcular fácilmente los vectores normales normalizados $N0$ , $N1$ , $N2$ & $N3$ . Entonces, es fácil ver que : $$u = \frac{dU0}{dU0 + dU1} = \frac{(P-P0) \cdot N0}{(P-P0).N0 + (P-P2) \cdot N2} \\ v = \frac{dV0}{dV0 + dV1} = \frac{(P-P0) \cdot N1}{(P-P0).N1 + (P-P3) \cdot N3}.$$

Esta parametrización funciona a las mil maravillas y es realmente fácil de calcular dentro de un shader, por ejemplo. Lo que es difícil es lo contrario: encontrar $P(x,y)$ de $(u,v)$ así que aquí está el resultado:

$$x = \frac{vKH \cdot uFC - vLI \cdot uEB}{vJG \cdot uEB - vKH \cdot uDA}, \\ y = \frac{vLI \cdot uDA - uFC \cdot vJG}{vJG \cdot uEB - vKH \cdot uDA},$$

donde: $$uDA = u \cdot (D-A), \quad uEB = u \cdot (E-B), \quad uFC = u \cdot (F-C), \\ vJG = v \cdot (J-G), \quad vKH = v \cdot (K-H), \quad vJG = v \cdot (J-G),$$

y finalmente: $$A = N0_x, \qquad \qquad B = N0_y, \quad C = -P0 \cdot N0, \qquad \\ D = N0_x + N2_x, \quad E = N0_y + N2_y, \quad F = -P0 \cdot N0 - P2 \cdot N2, \\ G = N1_x, \qquad \qquad H = N1_y, \quad I = -P0 \cdot N1, \qquad \\ J = N1_x + N3_x, \quad K = N1_y + N3_y, \quad L = -P0 \cdot N1 - P2 \cdot N3.$$

He estado usando esto con éxito para el mapeo de sombras de un frustum de cámara deformado mapeado en una textura cuadrada regular y puedo asegurar que funciona muy bien! :D

Answer 3

Prueba con esta solución Me ha funcionado.

Answer 4

Esta es una solución implementada en VBA Una solución algebraica general, más general que la formulación de la transformación afín 2D aumentada en Wikipedia.

Function Quad_to_Logical_Cell(Qx() As Double, Qy() As Double, x As Double, y As Double) As Variant

  'WJW 7-13-15
  'This function performs a coordinate transform from X,Y space to the normalized L,M.
  '
  'If a point {is within {0,1} on both axes, it is within the transformed unit square.
  'Qx,Qy vectors contain the 4 coordinates of the corners - x and y values, respectively, ordered as indicated below:
  '
  'The unit cell L(l,m) corresponding to Q(x,y) is oriented as:
  'L0(x=0,y=0),L1(0,1), L2(1,1), L3(1,0).  The order matters.
  'The following represent an algebraic solution to the system:
  'l=a1 + b1x + c1y + d1xy
  'm=a2 + b2x + c2y + d2xy

    Dim L_Out() As Double
    ReDim L_Out(2)

    ax = (x - Qx(0)) + (Qx(1) - Qx(0)) * (y - Qy(0)) / (Qy(0) - Qy(1))
    a3x = (Qx(3) - Qx(0)) + (Qx(1) - Qx(0)) * (Qy(3) - Qy(0)) / (Qy(0) - Qy(1))
    a2x = (Qx(2) - Qx(0)) + (Qx(1) - Qx(0)) * (Qy(2) - Qy(0)) / (Qy(0) - Qy(1))
    ay = (y - Qy(0)) + (Qy(3) - Qy(0)) * (x - Qx(0)) / (Qx(0) - Qx(3))
    a1y = (Qy(1) - Qy(0)) + (Qy(3) - Qy(0)) * (Qx(1) - Qx(0)) / (Qx(0) - Qx(3))
    a2y = (Qy(2) - Qy(0)) + (Qy(3) - Qy(0)) * (Qx(2) - Qx(0)) / (Qx(0) - Qx(3))
    bx = x * y - Qx(0) * Qy(0) + (Qx(1) * Qy(1) - Qx(0) * Qy(0)) * (y - Qy(0)) / (Qy(0) - Qy(1))
    b3x = Qx(3) * Qy(3) - Qx(0) * Qy(0) + (Qx(1) * Qy(1) - Qx(0) * Qy(0)) * (Qy(3) - Qy(0)) / (Qy(0) - Qy(1))
    b2x = Qx(2) * Qy(2) - Qx(0) * Qy(0) + (Qx(1) * Qy(1) - Qx(0) * Qy(0)) * (Qy(2) - Qy(0)) / (Qy(0) - Qy(1))
    by = x * y - Qx(0) * Qy(0) + (Qx(3) * Qy(3) - Qx(0) * Qy(0)) * (x - Qx(0)) / (Qx(0) - Qx(3))
    b1y = Qx(1) * Qy(1) - Qx(0) * Qy(0) + (Qx(3) * Qy(3) - Qx(0) * Qy(0)) * (Qx(1) - Qx(0)) / (Qx(0) - Qx(3))
    b2y = Qx(2) * Qy(2) - Qx(0) * Qy(0) + (Qx(3) * Qy(3) - Qx(0) * Qy(0)) * (Qx(2) - Qx(0)) / (Qx(0) - Qx(3))

  'Dependent on the way your data is formatted, you may have to swap x and y to get the order right.
  'L=L(0) is the x coordinate here (row)
  'M=L(1) is the y coordinate here (colum)
    L_Out(0) = (ax / a3x) + (1 - a2x / a3x) * (bx - b3x * ax / a3x) / (b2x - b3x * a2x / a3x)
    L_Out(1) = (ay / a1y) + (1 - a2y / a1y) * (by - b1y * ay / a1y) / (b2y - b1y * a2y / a1y)

    Quad_to_Logical_Cell = L_Out
End Function

Answer 5

Echa un vistazo en Tutorial de Gernot Hoffmann sobre la rectificación de la imagen. También se explican los casos especiales (de rectángulo a cuadrilátero).

Otra página que me ayudó a discutir la transformación de la perspectiva en 2D (es decir, la homografía plana).

Para una comprensión profunda del tema y algoritmos más estables numéricamente, sólo puedo recomendar Hartley y Zisserman: Geometría multivista en la visión por ordenador .