Transformação linear direta

Transformação linear direta (DLT) é um algoritmo que calcula um conjunto de variáveis a partir de um conjunto de relações de semelhança:

$$\mathbf {x} _{k}\propto \mathbf {A} \,\mathbf {y} _{k}{\text{ para }}k=1,\ldots ,N$$

em que $\mathbf {x} _{k}$ e $\mathbf {y} _{k}$ são vetores conhecidos, $\propto$ denota igualdade a menos de uma multiplicação por um escalar desconhecido, e $\mathbf {A}$ é uma matriz (ou transformação linear) que contém as incógnitas a serem calculadas.

Este tipo de relação aparece frequentemente em geometria projetiva. Exemplos práticos incluem a relação entre pontos 3D em uma cena e a sua projeção sobre o plano da imagem de uma câmera pinhole, e homografias.

Introdução

Uma equação linear ordinária

$$\mathbf {x} _{k}=\mathbf {A} \,\mathbf {y} _{k}{\text{ para }}k=1,\ldots ,N$$

pode ser resolvida, por exemplo, reescrevendo-a como uma equação matricial $\mathbf {X} =\mathbf {A} \,\mathbf {Y}$ na qual as matrizes $\mathbf {X}$ e $\mathbf {Y}$ contêm os vetores $\mathbf {x} _{k}$ e $\mathbf {y} _{k}$ em suas respectivas colunas. Dado que existe uma única solução, ela é dada por

$$\mathbf {A} =\mathbf {X} \,\mathbf {Y} ^{T}\,(\mathbf {Y} \,\mathbf {Y} ^{T})^{-1}.$$

As soluções também podem ser descritas nos casos em que as equações são sobredeterminadas ou subdeterminadas.

O que torna o problema da transformação linear direta diferente do caso padrão acima é o fato de que os lados esquerdo e direito das equações que o definem podem diferir por um fator multiplicativo desconhecido que é dependente de k. Como consequência, $\mathbf {A}$ não pode ser calculada como no caso padrão. Em vez disso, as relações de semelhança são reescritas como equações lineares homogêneas apropriadas que podem então ser resolvidas por um método padrão. A combinação da reescrita das equações de semelhança como equações lineares homogêneas com a sua resolução por métodos padrão é conhecida como algoritmo de transformação linear direta ou algoritmo DLT. A sigla DLT é atribuída a Ivan Sutherland.

Exemplo

Sejam $\mathbf {x} _{k}\in \mathbb {R} ^{2}$ e $\mathbf {y} _{k}\in \mathbb {R} ^{3}$ dois conjuntos de vetores conhecidos e o problema é encontrar uma matriz $\mathbf {A}$ de ordem $2\times 3$ tal que que

$$\alpha _{k}\,\mathbf {x} _{k}=\mathbf {A} \,\mathbf {y} _{k}{\text{ para }}k=1,\ldots ,N$$

onde $\alpha _{k}\neq 0$ é o fator escalar desconhecido relacionado à equação k.

Para se livrar dos escalares desconhecidos e obter equações homogêneas, defina a matriz antissimétrica

$$\mathbf {H} ={\begin{pmatrix}0&-1\\1&0\end{pmatrix}}$$

e multiplique ambos os lados da equação pela esquerda por $\mathbf {x} _{k}^{T}\,\mathbf {H}$

$$\alpha _{k}\,\mathbf {x} _{k}^{T}\,\mathbf {H} \,\mathbf {x} _{k}=\mathbf {x} _{k}^{T}\,\mathbf {H} \,\mathbf {A} \,\mathbf {y} _{k}{\text{ para }}k=1,\ldots ,N.$$

Como $\mathbf {x} _{k}^{T}\,\mathbf {H} \,\mathbf {x} _{k}=0,$ tem-se as seguintes equações homogêneas, que já não contêm os escalares desconhecidos:

$$0=\mathbf {x} _{k}^{T}\,\mathbf {H} \,\mathbf {A} \,\mathbf {y} _{k}{\text{ para }}k=1,\ldots ,N.$$

A fim de obter $\mathbf {A}$ a partir deste conjunto de equações, considere os elementos dos vetores $\mathbf {x} _{k}$ e $\mathbf {y} _{k}$ e a matriz $\mathbf {A} :$

$$\mathbf {x} _{k}={\begin{pmatrix}x_{1k}\\x_{2k}\end{pmatrix}},\mathbf {y} _{k}={\begin{pmatrix}y_{1k}\\y_{2k}\\y_{3k}\end{pmatrix}},{\text{ e }}\mathbf {A} ={\begin{pmatrix}a_{11}&a_{12}&a_{13}\\a_{21}&a_{22}&a_{23}\end{pmatrix}}$$

e a equação homogênea acima torna-se

$$0=a_{11}\,x_{2k}\,y_{1k}-a_{21}\,x_{1k}\,y_{1k}+a_{12}\,x_{2k}\,y_{2k}-a_{22}\,x_{1k}\,y_{2k}+a_{13}\,x_{2k}\,y_{3k}-a_{23}\,x_{1k}\,y_{3k}{\text{ para }}k=1,\ldots ,N.$$

Isso também pode ser escrito como

$$0=\mathbf {b} _{k}^{T}\,\mathbf {a} {\text{ para }}k=1,\ldots ,N$$

em que tanto $\mathbf {b} _{k}$ quanto $\mathbf {a}$ são vetores de 6 dimensões definidos como

$$\mathbf {b} _{k}={\begin{pmatrix}x_{2k}\,y_{1k}\\-x_{1k}\,y_{1k}\\x_{2k}\,y_{2k}\\-x_{1k}\,y_{2k}\\x_{2k}\,y_{3k}\\-x_{1k}\,y_{3k}\end{pmatrix}}$$

  e   $\mathbf {a} ={\begin{pmatrix}a_{11}\\a_{21}\\a_{12}\\a_{22}\\a_{13}\\a_{23}\end{pmatrix}}.$

Este conjunto de equações homogêneas também pode ser escrito em forma matricial como

$$\mathbf {0} =\mathbf {B} \,\mathbf {a}$$

onde $\mathbf {B}$ é uma matriz $N\times 6$ que contém os vetores $\mathbf {b} _{k}$ em suas linhas. Isto significa que $\mathbf {a}$ pertence ao espaço nulo de $\mathbf {B}$ e pode ser determinado, por exemplo, por meio de uma decomposição em valores singulares de $\mathbf {B} ;$ $\mathbf {a}$ é um vetor singular à direita de $\mathbf {B}$ correspondente a um valor singular nulo. Uma vez que $\mathbf {a}$ foi determinado, os elementos de $\mathbf {A}$ podem ser encontrados por uma simples reorganização do vetor de 6 dimensões na forma de uma matriz $2\times 3.$ Note que o fator escalar de $\mathbf {a}$ ou $\mathbf {A}$ não é importante (exceto por ter que ser diferente de zero) uma vez que as equações que as definem já levam em conta o escalar desconhecido.

Na prática, os vetores $\mathbf {x} _{k}$ e $\mathbf {y} _{k}$ pode conter ruído, o que significa que as equações de semelhança são apenas aproximadamente válidas. Como consequência, pode não existir um vetor $\mathbf {a}$ que seja uma solução exata da equação homogênea $\mathbf {0} =\mathbf {B} \,\mathbf {a} .$ Nestes casos, uma solução de mínimos quadrados totais pode ser utilizada escolhendo $\mathbf {a}$ como um vetor singular à direita correspondente ao menor valor singular de $\mathbf {B} .$

Casos mais gerais

O exemplo acima tem $\mathbf {x} _{k}\in \mathbb {R} ^{2}$ e $\mathbf {y} _{k}\in \mathbb {R} ^{3},$ mas a estratégia geral para reescrever as relações de semelhança como equações lineares homogêneas pode ser generalizada para casos em que tanto $\mathbf {x} _{k}$ quanto $\mathbf {y} _{k}$ têm dimensões arbitrárias.

Se $\mathbf {x} _{k}\in \mathbb {R} ^{2}$ e $\mathbf {y} _{k}\in \mathbb {R} ^{q}$ as expressões anteriores ainda podem levar a uma equação

$$0=\mathbf {x} _{k}^{T}\,\mathbf {H} \,\mathbf {A} \,\mathbf {y} _{k}{\text{ para }}k=1,\ldots ,N$$

onde $\mathbf {A}$ agora é $2\times q.$ Cada k fornece uma equação nos $2q$ elementos desconhecidos de $\mathbf {A}$ e juntas, essas equações podem ser escritas na forma $\mathbf {B} \,\mathbf {a} =\mathbf {0}$ com a matriz B de ordem N x 2q que é conhecida e o vetor de incógnitas $\mathbf {a} ,$ de dimensão 2q. Este vetor pode ser encontrado de forma similar à que foi feita anteriormente.

No caso mais geral, $\mathbf {x} _{k}\in \mathbb {R} ^{p}$ e $\mathbf {y} _{k}\in \mathbb {R} ^{q}.$ A principal diferença em relação ao caso anterior é que a matriz $\mathbf {H}$ agora é $p\times p$ e antissimétrica. Quando $p>2$ o espaço de tais matrizes não é mais unidimensional, mas sim de dimensão

$$M={\frac {p\,(p-1)}{2}}.$$

Isso significa que cada valor de k fornece M equações homogêneas do tipo

$$0=\mathbf {x} _{k}^{T}\,\mathbf {H} _{m}\,\mathbf {A} \,\mathbf {y} _{k}{\text{ para }}m=1,\ldots ,M{\text{ e para }}k=1,\ldots ,N$$

onde $\mathbf {H} _{m}$ é uma base de dimensão M do espaço de matrizes $p\times p$ antissimétricas.

Exemplo p = 3

No caso em que p = 3, podem ser escolhidas as três matrizes $\mathbf {H} _{m}$ a seguir

$$\mathbf {H} _{1}={\begin{pmatrix}0&0&0\\0&0&-1\\0&1&0\end{pmatrix}},\mathbf {H} _{2}={\begin{pmatrix}0&0&1\\0&0&0\\-1&0&0\end{pmatrix}},\mathbf {H} _{3}={\begin{pmatrix}0&-1&0\\1&0&0\\0&0&0\end{pmatrix}}.$$

Neste caso particular, as equações lineares homogêneas podem ser escritas como

$$\mathbf {0} =[\mathbf {x} _{k}]_{\times }\,\mathbf {A} \,\mathbf {y} _{k}{\text{ para }}k=1,\ldots ,N$$

onde $[\mathbf {x} _{k}]_{\times }$ é a representação matricial do produto vetorial. Observe que esta última equação é em valores vetoriais; o lado esquerdo é o elemento zero em $\mathbb {R} ^{3}.$

Cada valor de k fornece três equações homogêneas nos elementos desconhecidos de $\mathbf {A} .$ No entanto, como $[\mathbf {x} _{k}]_{\times }$ tem posto 2, no máximo duas equações são linearmente independentes. Na prática, portanto, é comum usar apenas duas das três matrizes, $\mathbf {H} _{m},$ por exemplo, para m=1, 2. No entanto, a dependência linear entre as equações é dependente de $\mathbf {x} _{k},$ o que significa que em certos casos seria melhor escolher, por exemplo, m=2,3. Assim, se o número de equações não é uma preocupação, pode ser melhor usar as três equações ao construir a matriz $\mathbf {B} .$

A dependência linear entre as equações lineares homogêneas é uma preocupação geral para o caso p > 2 e tem de ser tratada reduzindo o conjunto de matrizes antissimétricas $\mathbf {H} _{m}$ ou então permitindo que $\mathbf {B}$ se torne maior do que o necessário para determinar $\mathbf {a} .$

Referências

• Richard Hartley and Andrew Zisserman (2003). Multiple View Geometry in computer vision. [S.l.]: Cambridge University Press. ISBN 978-0-521-54051-3 

Ligações externas

• Homography Estimation por Elan Dubrofsky (§2.1 esboça o "algoritmo DLT básico")