Direkt linjär transformation

Direkt linjär transformation ( DLT ) är en algoritm som löser en uppsättning variabler från en uppsättning likhetsrelationer:

$\mathbf {x} _{k}\propto \mathbf {A} \,\mathbf {y} _{k}$ för $\, k=1,\ldots ,N$

där $\mathbf {x} _{k}$ och $\mathbf {y} _{k}$ är kända vektorer, $\,\propto$ betecknar likhet upp till en okänd skalär multiplikation, och $\mathbf {A}$ är en matris (eller linjär transformation) som innehåller de okända som ska lösas.

Denna typ av relation förekommer ofta i projektiv geometri . Praktiska exempel inkluderar relationen mellan 3D-punkter i en scen och deras projicering på bildplanet av en pinhole-kamera och homografier .

Introduktion

Ett vanligt system av linjära ekvationer

$\mathbf {x} _{k}=\mathbf {A} \,\mathbf {y} _{k}$ för $\,k =1,\ldots ,N$

kan t.ex. lösas genom att skriva om det som en matrisekvation $\mathbf {X} =\mathbf {A} \,\mathbf {Y}$ där matriser $\mathbf {X }$ och $\mathbf {Y}$ innehåller vektorerna $\mathbf {x} _{k}$ och $\mathbf {y} _{k}$ i sina respektive kolumner. Med tanke på att det finns en unik lösning, ges den av

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

Lösningar kan också beskrivas i det fall att ekvationerna är över- eller underbestämda.

Det som skiljer det direkt linjära transformationsproblemet från ovanstående standardfall är det faktum att vänster och höger sida av den definierande ekvationen kan skilja sig åt med en okänd multiplikativ faktor som är beroende av k . Som en konsekvens $\mathbf {A}$ inte beräknas som i standardfallet. Istället skrivs likhetsrelationerna om till egentliga linjära homogena ekvationer som sedan kan lösas med en standardmetod. Kombinationen av att skriva om likhetsekvationerna som homogena linjära ekvationer och lösa dem med standardmetoder kallas en direkt linjär transformationsalgoritm eller DLT-algoritm . DLT tillskrivs Ivan Sutherland.

Exempel

Antag att $k\in \{1,...,N\}$ . Låt $\mathbf {x} _{k}=(x_{1k},x_{2k})\in \mathbb {R} ^{2 }$ och $\mathbf {y} _{k}=(y_{1k},y_{2k},y_{3k} )\in \mathbb {R} ^{3}$ vara två kända vektorer, och vi vill hitta $2\times 3$ matrisen $\mathbf {A}$ så att

$\alpha _{k}\,\mathbf {x} _{k}=\mathbf {A} \,\mathbf {y} _{k}$

där $\alpha _{k}\neq 0$ är den okända skalära faktorn relaterad till ekvation k .

För att bli av med de okända skalärerna och få homogena ekvationer, definiera den antisymmetriska matrisen

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

och multiplicera båda sidor av ekvationen med $\mathbf {x} _{k}^{T}\,\mathbf {H}$ från vänster

${\begin{aligned}(\mathbf {x } _{k}^{T}\,\mathbf {H} )\,\alpha _{k}\,\mathbf {x} _{k}&=(\mathbf {x} _{k}^{ T}\,\mathbf {H} )\,\mathbf {A} \,\mathbf {y} _{k}\\\alpha _{k}\,\mathbf {x} _{k}^{T }\,\mathbf {H} \,\mathbf {x} _{k}&=\mathbf {x} _{k}^{T}\,\mathbf {H} \,\mathbf {A} \, \mathbf {y} _{k}\end{aligned}}$

Eftersom ${\displaystyle \mathbf {x} _{k}^{T}\,\mathbf {H} \,\mathbf {x} _{k}=0,} följande$ homogena ekvationer, som inte längre innehåller de okända skalärerna, är till hands

$\mathbf {x} _{k}^{T}\,\mathbf {H} \,\mathbf {A} \,\mathbf {y} _{k}= 0$

För att lösa $\mathbf {A}$ från denna uppsättning ekvationer, betrakta elementen i vektorerna $\mathbf {x} _{k}$ och $\mathbf { y} _{k}$ och matris $\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}}$ och $\mathbf {A} ={\begin{pmatrix}a_{11}&a_{12}&a_{13}\ \a_{21}&a_{22}&a_{23}\end{pmatrix}}$

och ovanstående homogena ekvation blir

$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}$ för $\,k=1,\ldots ,N.$

Detta kan också skrivas i matrisformen:

$0=\mathbf {b} _{k}^{T}\,\mathbf {a}$ för $\,k=1,\ldots ,N$

där $\mathbf {b} _{k}$ och $\mathbf {a}$ båda är 6-dimensionella vektorer definierade som

$\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}}$ och $\mathbf {a} ={\begin{pmatrix}a_{11}\\a_{21}\\a_{12}\\a_{22}\\a_{13}\\a_{23}\ slut{pmatrix}}.$

Hittills har vi 1 ekvation och 6 okända. En uppsättning homogena ekvationer kan skrivas i matrisform

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

där $\mathbf {B}$ är en $N\ gånger 6$ matris som håller de kända vektorerna $\mathbf {b} _{k}$ i sina rader. Den okända $\mathbf {a}$ kan till exempel bestämmas genom en singularvärdesuppdelning av $\mathbf {B}$ ; $\mathbf {a}$ är en höger singularvektor av $\mathbf {B}$ som motsvarar ett singularvärde som är lika med noll. När $\mathbf {a}$ har bestämts kan elementen i matris $\mathbf {A}$ omarrangeras från vektor $\mathbf {a}$ . Lägg märke till att skalningen av $\mathbf {a}$ eller $\mathbf {A}$ inte är viktig (förutom att den måste vara icke-noll) eftersom de definierande ekvationerna redan tillåter okänd skalning.

I praktiken kan vektorerna $\mathbf {x} _{k}$ och $\mathbf {y} _{k}$ innehålla brus vilket betyder att likhetsekvationerna endast är ungefär giltiga. Som en konsekvens kanske det inte finns en vektor $\mathbf {a}$ som löser den homogena ekvationen $\mathbf {0} =\mathbf {B} \,\mathbf {a}$ exakt. I dessa fall kan en total minsta kvadraters lösning användas genom att välja $\mathbf {a}$ som en höger singular vektor som motsvarar det minsta singularvärdet av $\mathbf {B} .$

Mer allmänna fall

Exemplet ovan har $\mathbf {x} _{k}\in \mathbb {R} ^{2}$ och $\mathbf {y} _{k }\in \mathbb {R} ^{3}$ , men den allmänna strategin för att skriva om likhetsrelationerna till homogena linjära ekvationer kan generaliseras till godtyckliga dimensioner för både $\mathbf {x} _{k}$ och $\mathbf {y} _{k}.$

Om $\mathbf {x} _{k}\in \mathbb {R} ^{2}$ och $\mathbf {y} _{k}\in \mathbb {R} ^{q}$ de tidigare uttrycken kan fortfarande leda till en ekvation

$0=\mathbf {x} _{k}^{T}\,\mathbf {H} \,\mathbf {A} \,\mathbf {y} _{k }$ för $\,k=1,\ldots ,N$

där $\mathbf {A}$ nu är $2\times q.$ Varje k ger en ekvation i de $2q$ okända elementen i $\mathbf {A}$ och tillsammans kan dessa ekvationer skrivas $\ mathbf {B} \,\mathbf {a} =\mathbf {0}$ för den kända $N\ gånger 2\,q$ matrisen $\mathbf {B}$ och okänd 2q -dimensionell vektor $\mathbf {a} .$ Denna vektor kan hittas på liknande sätt som tidigare.

I det mest allmänna fallet $\mathbf {x} _{k}\in \mathbb {R} ^{p}$ och $\mathbf {y} _{ k}\in \mathbb {R} ^{q}$ . Huvudskillnaden jämfört med tidigare är att matrisen $\mathbf {H}$ nu är $p\times p$ och antisymmetrisk. När $p>2$ är utrymmet för sådana matriser inte längre endimensionellt, det är av dimension

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

Detta betyder att varje värde på k ger M homogena ekvationer av typen

$0=\mathbf {x} _{k}^{T}\,\mathbf {H} _{m}\,\mathbf {A} \,\mathbf { y} _{k}$ för $\,m=1,\ldots ,M$ och för $\,k=1,\ldots , N$

där $\mathbf {H} _{m}$ är en M -dimensionell bas för rymden av $p\times p$ antisymmetriska matriser.

Exempel p = 3

I fallet att p = 3 kan följande tre matriser $\mathbf {H} _{m}$ väljas

$\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}}.$

I detta speciella fall kan de homogena linjära ekvationerna skrivas som

$\mathbf {0} =[\mathbf {x} _{k}]_{\times }\,\mathbf {A} \,\mathbf {y} _{ k}$ för $\,k=1,\ldots ,N$

där $[\mathbf {x} _{k}]_{\times }$ är matrisrepresentationen av vektorkorsprodukten . Lägg märke till att denna sista ekvation är vektorvärderad; den vänstra sidan är nollelementet i $\mathbb {R} ^{3}$ .

Varje värde på k ger tre homogena linjära ekvationer i de okända elementen i $\mathbf {A}$ . Men eftersom $[\mathbf {x} _{k}]_{\times }$ har rang = 2, är högst två ekvationer linjärt oberoende. I praktiken är det därför vanligt att endast använda två av de tre matriserna ${\displaystyle \mathbf {H} _{m}} ,$ till exempel för m =1, 2. Det linjära beroendet mellan ekvationerna är dock är beroende av $\mathbf {x} _{k}$ , vilket betyder att det i olyckliga fall hade varit bättre att välja till exempel m =2,3. Som en konsekvens, om antalet ekvationer inte är ett problem, kan det vara bättre att använda alla tre ekvationerna när matrisen $\mathbf {B}$ konstrueras.

Det linjära beroendet mellan de resulterande homogena linjära ekvationerna är ett allmänt problem för fallet p > 2 och måste hanteras antingen genom att reducera mängden antisymmetriska matriser $\mathbf {H} _{m}$ eller genom att tillåta $\mathbf {B}$ att bli större än nödvändigt för att bestämma $\mathbf {a} .$

•   Richard Hartley och Andrew Zisserman (2003). Multiple View Geometri i datorseende . Cambridge University Press. ISBN 978-0-521-54051-3 .

externa länkar

• Homography Estimation av Elan Dubrofsky (§2.1 skisserar "Basic DLT Algorithm")

• En DLT-lösare baserad på MATLAB av Hsiang-Jen (Johnny) Chien