Como desprojetar quadrilátero em retângulo?

tl; dr: Problema matemático em geometria projetiva: Como encontrar uma matriz de câmera 4x4 que faça uma projeção como ilustrado abaixo, de modo que os pontos A, B, C, D estejam em algum lugar nas bordas da caixa da unidade (por exemplo, dispositivo normalizado OpenGL coordenadas), e os cantos da caixa da unidade caem em algum lugar razoável ao longo dos raios EA, EB, EC, ED?

(Esse pode ser um caso especial, possivelmente de uma homografia, uma perspectiva e / ou uma colineação. Não familiarizado com a terminologia.)

elaboração

Dado um ABCD quadrilateral dentro da janela de visualização, acho que existe uma transformação (?) Única que mapeia de volta para um retângulo. Como visto na imagem abaixo: o ABCD quadrilateral na janela de exibição atua como uma 'janela' física e, se a mapearmos de volta para um retângulo, ela parecerá distorcida.

(a caixa à direita representa a NDC, da qual falo mais adiante)

O objetivo é obter rapidamente a imagem à direita. Poderíamos rastrear todos os pontos para obter a imagem (o que eu fiz), mas eu preferiria usar o OpenGL ou outras técnicas projetivas, porque queria tirar proveito de coisas como mesclagem, primitivas etc.

primeira tentativa

Acredito que posso resolver o problema de encontrar a matriz da câmera 3x4 que faz a coordenada homogênea tridimensional em 3 espaços (à esquerda) e a projeta até as coordenadas homogêneas bidimensionais em 2 espaços (em o certo). Pode-se resolver isso usando a transformação linear direta para obter um sistema de equações Ba=0para as entradas desconhecidas ada matriz da câmera e resolver o sistema usando decomposição de valor singular(SVD). Eu usaria os vetores EA, EB, EC, ED (onde E é seu olho físico ou a câmera no espaço do mundo) como pontos na pré-imagem e (0,0), (1,0), (1 , 1), (0,1) ou algo como os pontos na pós-imagem, e cada par de pontos daria algumas equações lineares para conectar ao SVD. A matriz resultante mapeará EA -> (0,0) etc. (supondo que haja graus de liberdade suficientes, isto é, se a solução for única, da qual não tenho certeza, consulte a nota [a].)

Mas, para meu desgosto, não é assim que o OpenGL funciona. O OpenGL não projeta diretamente 3d para 2d com uma matriz 3x4. O OpenGL requer "coordenadas de dispositivo normalizadas" (NDC), que são pontos tridimensionais. Depois de projetar no NDC, tudo na caixa 'unit' de (-1, -1, -1,1) a (1,1,1,1) é desenhado; tudo do lado de fora é cortado (já que estamos lidando com coordenadas homogêneas: qualquer ponto (x, y, z, w) aparecerá apenas na tela apenas se as três primeiras coordenadas de (x / w, y / w, z / w , 1) estão dentro da caixa da unidade de -1 a 1).

Portanto, a pergunta se torna: existe alguma transformação razoável que mapeia algum cubóide de aparência estranha em coordenadas homogêneas (especificamente o cubóide desenhado à esquerda, com ABCD (pontos de frente) e A'B'C'D '(pontos de trás, ocultos atrás dos pontos frontais)) ao cubo unitário, por exemplo, usando uma matriz 4x4? Como fazer isso?

o que eu tentei

Eu tentei algo mais forte: fiz ABCD e A'B'C'D 'parecerem um frustrum piramidal regular (por exemplo, gl frustrum) (ou seja, nessa configuração hipotética, a imagem à esquerda teria apenas um retângulo preto sobreposto , não um quadrilátero) e, em seguida, usou a transformação linear DLT / direta para resolver a suposta matriz 4x4. No entanto, quando tentei, não parecia haver graus de liberdade suficientes ... a matriz 4x4 resultante não mapeou todos os vetores de entrada para cada vetor de saída. Ao usar A, B, C, D, A '(5 pares de vetores de pré-transformação e pós-transformação), eu / quase / obtenho o resultado desejado ... os vetores são mapeados corretamente, mas, por exemplo, B', C ', D' estão mapeando para (3,3,1,1) em vez de (-1, -1,1,1) e são cortados pelo OpenGL. Se eu tentar adicionar um sexto ponto (6 pares de pontos para a matriz 4x4 projetar), minha solução parece degenerada (zeros, infinitos). Com quantos graus de liberdade eu estou lidando aqui, e isso é possível com uma matriz 4x4 que mapeia os 4 vetores usuais (vetores de coordenadas homogêneas tridimensionais 1 + 1) que conhecemos e amamos?

pensamentos menores aleatórios

Eu estou supondo que não é possível mapear nenhum cubóide arbitrário para qualquer cubóide arbitrário com uma matriz 4x4, embora eu esteja confuso porque pensei que era possível mapear qualquer quadrilátero convexo para qualquer outro quadrilátero convexo em 2d com alguma matriz como em , digamos, Photoshop? ... isso pode / não pode ser feito com uma transformação projetiva? E como isso generaliza para 3d? ...... Também dada a tentativa fracassada de encontrar uma matriz 4x4, a álgebra linear diz que não devemos esperar que uma matriz NxN mapeie mais do que N pontos linearmente independentes para N pontos-alvo, na melhor das hipóteses, mas acho que de alguma forma homogêneo coordenadas enganam isso porque há alguma colinearidade oculta acontecendo? Eu acho que não?

outra solução?

Eu acho que alguém poderia talvez fazer a seguinte coisa feia, onde você usa uma matriz típica de projeção de câmera de frustrum, encontra os 2d pontos correspondentes aos cantos e, em seguida, executa uma perspectiva 2D de distorção da homografia, mas se isso acontecer depois que os pixels forem renderizados (por exemplo, photoshop), então haveria problemas com a resolução ... talvez, hipoteticamente, alguém pudesse descobrir uma matriz para realizar essa transformação no plano XY no espaço NDC, e depois compor com a matriz normal baseada no frustrum?

(nota [a]: Grau de liberdade: o ABCD pode ser ainda mais restrito a ser a pós-imagem de uma transformação projetiva que atua em um retângulo, se for necessário ... ou seja, o retângulo preto à esquerda pode ser considerado o resultado da projeção de um modelo de clipart de quadro de imagem)

Eu acho que a solução está procurando a transformação projetiva que transforma corretamente os quatro pontos.

ie

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

$P$ é uma matriz 3x3 com 9 entradas. Devido à normalização final, ela é única até a escala, deixando 8 graus de liberdade, que são determinados exclusivamente pelas 8 equações dadas pela correspondência (2 por par de pontos).

Agora você pode usar álgebra para fazer isso, ou apenas usar OpenCV's getPerspectiveTransform:).

Verifique também as coordenadas homogêneas na wikipedia para se familiarizar com o conceito.

Resolvi minha própria pergunta implementando a Transformação Linear Direta . A seção de exemplos na Wikipedia foi o meu caso de uso.

Para obter as equações, conecte as matrizes (por exemplo [x1 x2 x3 x4; x5 x6 x7 x8; x9 x10 x11 x12]) ao seu sistema de álgebra de computador favorito, como o SageMath, depois resolva a equação da matriz necessária conforme ilustrado, copie e cole as soluções em termos de variáveis ​​em seu código e ajuste a formatação.

Pode-se então adaptar a solução ao seu caso de uso escalando ou ignorando dimensões específicas conforme apropriado (por exemplo, ignore a coordenada de profundidade / z na matriz de coordenadas de dispositivo normalizadas conforme apropriado para o caso de uso).

Você precisará de uma função ou biblioteca de decomposição SVD no seu idioma.