Bezpośrednia transformacja liniowa

Bezpośrednia transformacja liniowa ( DLT ) to algorytm, który rozwiązuje zbiór zmiennych ze zbioru relacji podobieństwa:

${\ Displaystyle \ mathbf {x} _ {k} \ propto \ mathbf {A} \ \ mathbf {y} _ {k}}$ dla ${\ Displaystyle \, k=1,\ldkropki ,N}$

gdzie ${\ Displaystyle \ mathbf {x} _ {k}}$ i $\ mathbf {y} _ {k}}$$Displaystyle$ są znanymi wektorami, równość do nieznane mnożenie przez skalar, a jest $)$ , która zawiera niewiadome do rozwiązania.

Ten typ relacji pojawia się często w geometrii rzutowej . Praktyczne przykłady obejmują relacje między punktami 3D w scenie a ich projekcją na płaszczyznę obrazu kamery otworkowej oraz homografie .

Wstęp

Zwykły układ równań liniowych

$\ Displaystyle \ mathbf {x} _ {k} = \ mathbf {A} \, \ mathbf {y} _ {k}}$ dla ${\ Displaystyle \, k =1,\ldkropki ,N}$

można rozwiązać, na przykład, przepisując je jako równanie macierzowe gdzie macierze $Y}}$$} }$$mathbf {$ i $Displaystyle$ zawierają wektory $\ mathbf {x} _ {k}}$ i ${\ Displaystyle \ mathbf {y} _ {k}}$ w ich odpowiednich kolumny. Biorąc pod uwagę, że istnieje unikalne rozwiązanie, jest ono podane przez

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

Rozwiązania można również opisywać w przypadku, gdy równania są przekreślone lub niedookreślone.

To, co odróżnia problem bezpośredniej transformacji liniowej od powyższego przypadku standardowego, to fakt, że lewa i prawa strona równania definiującego mogą różnić się o nieznany współczynnik multiplikatywny, który jest zależny od k . W konsekwencji $,$ jak w przypadku standardowym. Zamiast tego relacje podobieństwa są przepisywane jako właściwe liniowe równania jednorodne, które następnie można rozwiązać standardową metodą. Połączenie przepisywania równań podobieństwa jako jednorodnych równań liniowych i rozwiązywania ich standardowymi metodami jest określane jako algorytm bezpośredniej transformacji liniowej lub algorytm DLT . DLT przypisuje się Ivanowi Sutherlandowi.

Przykład

Załóżmy, że ${\ Displaystyle k \ w \ {1, ..., N \}}$ . Niech ${\ Displaystyle \ mathbf {x} _ {k} = (x_ {1k}, x_ {2k}) \ w \ mathbb {R} ^ {2 }}$ i ${\ Displaystyle \ mathbf {y} _ {k} = (y_ {1k}, y_ {2k}, y_ {3k} )\in \mathbb {R} ^{3}}$ być dwoma znanymi wektorami i chcemy znaleźć $}$ macierz , że ${\ Displaystyle 2 \ razy 3$

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

gdzie jest nieznanym współczynnikiem skalarnym związanym z równaniem k . ${\ Displaystyle \ alpha _ {k} \ neq 0}$

Aby pozbyć się nieznanych skalarów i otrzymać równania jednorodne, zdefiniuj macierz antysymetryczną

${\ Displaystyle \ mathbf {H} = {\ rozpocząć {pmatrix} 0 i -1 \\ 1 i 0 \ koniec {pmatrix}}}$

i pomnóż obie strony równania przez ${\ Displaystyle \ mathbf {x} _ {k} ^ {T} \, \ mathbf {H}}$ od lewej

$\ Displaystyle {\ rozpocząć {wyrównane} (\ 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{wyrównane}}}$

Ponieważ $_$ _ równania, które nie zawierają już nieznanych skalarów, są w zasięgu ręki

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

Aby rozwiązać $Displaystyle \ mathbf {$${\ Displaystyle \ mathbf { {\ Displaystyle \ mathbf {} y} _ {k}}$ zestawu równań, rozważ elementy wektorów $} _ {k}}$ y i macierz ${\ Displaystyle \ mathbf {A}}$ :

${\ Displaystyle \ mathbf {x} _ {k} = {\ rozpocząć {pmatrix} x_ {1k} \\ x_ {2k} \ koniec {pmatrix}}$ } ${\ Displaystyle \ mathbf {y} _ {k} = {\ rozpocząć {pmatrix} y_ {1 k} \\ y_ {2 k} \\ y_ {3 k} \ koniec { pmatrix}}}$ i ${\ Displaystyle \ mathbf {A} = {\ rozpocząć {pmatrix} a_ {11} i a_ {12} i a_ {13} \ \a_{21}&a_{22}&a_{23}\end{pmatrix}}}$

i powyższe jednorodne równanie staje się

${\ Displaystyle 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}}$ dla ${\ Displaystyle \, k = 1, \ ldots, N.}$

Można to również zapisać w postaci macierzowej:

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

gdzie oba są 6-wymiarowymi wektorami zdefiniowanymi jako ${\ Displaystyle \ mathbf {b} _ {k}}$ i ${\ Displaystyle \ mathbf {a}}$

${\ Displaystyle \ 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{pmacierz}}}$ i ${\ Displaystyle \ mathbf {a} = {\ rozpocząć {pmatrix} a_ {11} \\ a_ {21} \\ a_ {12} \\ a_ {22} \\ a_ {13} \\ a_ {23} \ koniec {pmacierz}}.}$

Jak dotąd mamy 1 równanie i 6 niewiadomych. Układ równań jednorodnych można zapisać w postaci macierzowej

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

gdzie jest $_$$która$$zawiera$ znane w Nieznane można określić na przykład za pomocą $rozkładu$ wartości osobliwej na $B}}$ ; ${\ displaystyle \ mathbf {a}}$$jest$ prawym wektorem liczby pojedynczej wartości osobliwej równej zeru. Po określeniu elementy macierzy $zmienić$ z wektora ${\ displaystyle \ mathbf {a$$}$ . Zauważ, że skalowanie lub nie jest ważne (poza tym, że musi być niezerowe), ponieważ równania definiujące już pozwalają $na$$nieznane$

W praktyce wektory $,$ mogą zawierać szum $, co oznacza$ że ​​równania podobieństwa są poprawne tylko W konsekwencji może nie istnieć wektor $Displaystyle$ który rozwiązuje równanie jednorodne $\ mathbf {0} = \ mathbf {B} \, \ mathbf {a}}$ Dokładnie. W takich przypadkach całkowite rozwiązanie najmniejszych kwadratów , wybierając prawy $osobliwy$ odpowiadający najmniejszej wartości osobliwej ${\ Displaystyle \ mathbf {B}.}$

Bardziej ogólne przypadki

Powyższy przykład ma ${\ Displaystyle \ mathbf {x} _ {k} \ in \ mathbb {R} ^ {2}}$ i ${\ Displaystyle \ mathbf {y} _ {k } \ in \ mathbb {R} ^ {3}}$ , ale ogólną strategię przepisywania relacji podobieństwa na jednorodne równania liniowe można uogólnić na dowolne wymiary zarówno dla ${\ Displaystyle \ mathbf {x} _ {k}}$ i ${\ Displaystyle \ mathbf {y} _ {k}.}$

x ${\ Displaystyle \ mathbf {x} _ {k} \ in \ mathbb {R} ^ {2}}$ i $Displaystyle \ mathbf {y} _ {k} \ in \mathbb {R} ^{q}}$ poprzednie wyrażenia nadal mogą prowadzić do równania

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

gdzie teraz $_$${\ Displaystyle 2 \ razy q.}$ Każde k zapewnia jedno równanie w $}$ elementach ${\ displaystyle 2q$ i razem te równania można zapisać ${\ displaystyle \ mathbf {B} \, \ mathbf {a} = \ mathbf {0}}$ dla znanej macierzy B ${\ Displaystyle \$$mathbf {B}}$ i nieznanej 2q wektor wymiarowy ${\ displaystyle \ mathbf {a}.}$ Ten wektor można znaleźć w podobny sposób jak poprzednio.

W najbardziej ogólnym przypadku ${\ Displaystyle \ mathbf {x} _ {k} \ in \ mathbb {R} ^ {p}}$ i ${\ Displaystyle \ mathbf {y} _ { k} \ w \mathbb {R} ^{q}}$ . Główna różnica w porównaniu z poprzednio polega na $macierz$$że$ antysymetryczna . Kiedy przestrzeń takich macierzy nie jest już $,$

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

Oznacza to, że każda wartość k dostarcza M równań jednorodnych tego typu

${\ Displaystyle 0 = \ mathbf {x} _ {k} ^ {T} \ \ mathbf {H} _ {m} \ \ mathbf {A} \, \ mathbf { y} _ {k}}$ dla ${\ Displaystyle \, m = 1, \ ldots, M}$ i dla ${\ Displaystyle \, k = 1, \ ldots, N}$

gdzie jest $H} _ {m}} .$ -wymiarową podstawą przestrzeni antysymetrycznych macierzy $\ displaystyle \ mathbf$ {

Przykład p = 3

W przypadku, gdy p = 3 można wybrać następujące trzy macierze: ${\ Displaystyle \ mathbf {H} _ {m}}$

${\ Displaystyle \ mathbf {H} _ {1} = {\ rozpocząć {pmatrix} 0 i 0 i 0 \\ 0 i 0 i -1 \\ 0 i 1 i 0 \ koniec {pmatrix}}}$ , ${\ Displaystyle \ mathbf {H} _ {2} = {\ rozpocząć {pmatrix} 0 i 0 i 1 \\ 0 i 0 i 0 \\ -1 & 0 i 0 \ koniec {pmatrix}}}$ , ${\ Displaystyle \ mathbf {H} _ {3} = {\ początek {pmatrix} 0&-1&0 \\1&0&0\\0&0&0\koniec {pmatrix}}.}$

W tym konkretnym przypadku jednorodne równania liniowe można zapisać jako

${\ Displaystyle \ mathbf {0} = [\ mathbf {x} _ {k}] _ {\ razy} \, \ mathbf {A} \, \ mathbf {y} _ { k}}$ dla ${\ Displaystyle \, k = 1, \ ldots, N}$

gdzie ${\ Displaystyle [\ mathbf {x} _ {k}] _ {\ razy}}$ jest macierzową reprezentacją iloczynu wektorowego . Zauważ, że to ostatnie równanie ma wartość wektorową; lewa strona to element zerowy w ${\ displaystyle \ mathbb {R} ^ {3}}$ .

Każda wartość k zapewnia trzy jednorodne równania liniowe w nieznanych elementach . ${\ Displaystyle \ mathbf {A}}$ . Ponieważ jednak $niezależne$ rangę = 2, co najwyżej dwa Dlatego w praktyce często używa się tylko dwóch z trzech macierzy , na przykład dla m $= 1,$ zależność między równaniami zależy od , $, że ​​w pechowych przypadkach lepiej$ wybrać np. m = 2,3. W $macierzy .$ , jeśli liczba równań nie jest problemem, może być lepiej użyć wszystkich trzech równań podczas konstruowania

Liniowa zależność między wynikowymi jednorodnymi równaniami liniowymi jest ogólnym problemem w przypadku p > 2 i należy się nią zająć albo poprzez zmniejszenie zbioru antysymetrycznych macierzy. ${\ displaystyle \ mathbf {H} _ {m}}$ lub pozwalając, $aby stał się$ niż jest to konieczne do określenia ${\ Displaystyle \ mathbf {a}.}$

•   Richarda Hartleya i Andrew Zissermana (2003). Geometria wielu widoków w wizji komputerowej . Wydawnictwo Uniwersytetu Cambridge. ISBN 978-0-521-54051-3 .

Linki zewnętrzne

• Homography Estimation autorstwa Elana Dubrofsky'ego (§2.1 szkicuje „Podstawowy algorytm DLT”)

• Solver DLT oparty na MATLAB autorstwa Hsiang-Jen (Johnny) Chien