Přímá lineární transformace - Direct linear transformation

Přímá lineární transformace (DLT) je algoritmus, který řeší sadu proměnných ze sady podobnostních vztahů:

${displaystyle mathbf {x} _ {k} propto mathbf {A}, mathbf {y} _ {k}}$ pro ${displaystyle, k = 1, ldots, N}$

kde ${displaystyle mathbf {x} _ {k}}$ a ${displaystyle mathbf {y} _ {k}}$ jsou známé vektory, ${displaystyle, propto}$ označuje rovnost až do neznámého skalárního násobení a ${displaystyle mathbf {A}}$ je matice (nebo lineární transformace), která obsahuje neznámé, které mají být vyřešeny.

Tento typ vztahu se často objevuje v projektivní geometrie. Mezi praktické příklady patří vztah mezi 3D body ve scéně a jejich projekce do obrazové roviny a dírková komora,^[1] a homografie.

Úvod

Obyčejný soustava lineárních rovnic

${displaystyle mathbf {x} _ {k} = mathbf {A}, mathbf {y} _ {k}}$ pro ${displaystyle, k = 1, ldots, N}$

lze vyřešit například přepsáním na maticovou rovnici ${displaystyle mathbf {X} = mathbf {A}, mathbf {Y}}$ kde matice ${displaystyle mathbf {X}}$ a ${displaystyle mathbf {Y}}$ obsahují vektory ${displaystyle mathbf {x} _ {k}}$ a ${displaystyle mathbf {y} _ {k}}$ v příslušných sloupcích. Vzhledem k tomu, že existuje jedinečné řešení, je dáno

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

Řešení lze také popsat v případě, že rovnice jsou stanoveny nad nebo pod.

To, co odlišuje problém přímé lineární transformace od výše uvedeného standardního případu, je skutečnost, že levá a pravá strana definující rovnice se mohou lišit o neznámý multiplikativní faktor, který je závislý na k. Jako následek, ${displaystyle mathbf {A}}$ nelze vypočítat jako ve standardním případě. Místo toho jsou vztahy podobnosti přepsány jako správné lineární homogenní rovnice, které pak lze vyřešit standardní metodou. Kombinace přepisování podobnostních rovnic na homogenní lineární rovnice a jejich řešení standardními metodami se označuje jako algoritmus přímé lineární transformace nebo Algoritmus DLT. DLT se připisuje Ivanu Sutherlandovi.^[2]

Příklad

Předpokládejme to ${displaystyle kin {1, ..., N}}$. Nechat ${displaystyle mathbf {x} _ {k} = (x_ {1k}, x_ {2k}) v mathbb {R} ^ {2}}$ a ${displaystyle mathbf {y} _ {k} = (y_ {1k}, y_ {2k}, y_ {3k}) v mathbb {R} ^ {3}}$ být dva známé vektory a my chceme najít ${displaystyle 2 imes 3}$ matice ${displaystyle mathbf {A}}$ takhle

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

kde ${displaystyle alpha _ {k} eq 0}$ je neznámý skalární faktor vztahující se k rovnici k.

Chcete-li se zbavit neznámých skalárů a získat homogenní rovnice, definujte anti-symetrickou matici

${displaystyle mathbf {H} = {egin {pmatrix} 0 & -1 1 & 0end {pmatrix}}}$

a vynásobte obě strany rovnice s ${displaystyle mathbf {x} _ {k} ^ {T}, mathbf {H}}$ zleva

${displaystyle {egin {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}}}$

Od té doby ${displaystyle mathbf {x} _ {k} ^ {T}, mathbf {H}, mathbf {x} _ {k} = 0,}$ po ruce jsou následující homogenní rovnice, které již neobsahují neznámé skaláry

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

Aby bylo možné vyřešit ${displaystyle mathbf {A}}$ z této sady rovnic zvažte prvky vektorů ${displaystyle mathbf {x} _ {k}}$ a ${displaystyle mathbf {y} _ {k}}$ a matice ${displaystyle mathbf {A}}$:

${displaystyle mathbf {x} _ {k} = {egin {pmatrix} x_ {1k} x_ {2k} konec {pmatrix}}}$,   ${displaystyle mathbf {y} _ {k} = {egin {pmatrix} y_ {1k} y_ {2k} y_ {3k} konec {pmatrix}}}$, a ${displaystyle mathbf {A} = {egin {pmatrix} a_ {11} & a_ {12} & a_ {13} a_ {21} & a_ {22} & a_ {23} end {pmatrix}}}$

a výše uvedená homogenní rovnice se stává

${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}}$ pro ${displaystyle, k = 1, ldots, N.}$

To lze také napsat ve formě matice:

${displaystyle 0 = mathbf {b} _ {k} ^ {T}, mathbf {a}}$ pro ${displaystyle, k = 1, ldots, N}$

kde ${displaystyle mathbf {b} _ {k}}$ a ${displaystyle mathbf {a}}$ oba jsou 6-rozměrné vektory definované jako

${displaystyle mathbf {b} _ {k} = {egin {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} konec {pmatrix}}}$ a ${displaystyle mathbf {a} = {egin {pmatrix} a_ {11} a_ {21} a_ {12} a_ {22} a_ {13} a_ {23} konec {pmatrix}}.}$

Zatím máme 1 rovnici a 6 neznámých. Soubor homogenních rovnic lze napsat ve formě matice

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

kde ${displaystyle mathbf {B}}$ je ${displaystyle N imes 6}$ matice, která obsahuje známé vektory ${displaystyle mathbf {b} _ {k}}$ v jeho řadách. Neznámý ${displaystyle mathbf {a}}$ lze určit například pomocí a rozklad singulární hodnoty z ${displaystyle mathbf {B}}$; ${displaystyle mathbf {a}}$ je pravý singulární vektor ${displaystyle mathbf {B}}$ odpovídá singulární hodnotě, která se rovná nule. Jednou ${displaystyle mathbf {a}}$ bylo určeno, prvky matice ${displaystyle mathbf {A}}$ lze přeskupit z vektoru ${displaystyle mathbf {a}}$. Všimněte si, že změna měřítka ${displaystyle mathbf {a}}$ nebo ${displaystyle mathbf {A}}$ není důležité (kromě toho, že musí být nenulové), protože definující rovnice již umožňují neznámé škálování.

V praxi vektory ${displaystyle mathbf {x} _ {k}}$ a ${displaystyle mathbf {y} _ {k}}$ může obsahovat šum, což znamená, že rovnice podobnosti jsou platné pouze přibližně. V důsledku toho nemusí existovat vektor ${displaystyle mathbf {a}}$ který řeší homogenní rovnici ${displaystyle mathbf {0} = mathbf {B}, mathbf {a}}$ přesně. V těchto případech a celkem nejméně čtverců řešení lze použít výběrem ${displaystyle mathbf {a}}$ jako pravý singulární vektor odpovídající nejmenší singulární hodnotě ${displaystyle mathbf {B}.}$

Obecnější případy

Výše uvedený příklad má ${displaystyle mathbf {x} _ {k} v mathbb {R} ^ {2}}$ a ${displaystyle mathbf {y} _ {k} v mathbb {R} ^ {3}}$, ale obecnou strategii pro přepisování vztahů podobnosti do homogenních lineárních rovnic lze zobecnit na libovolné rozměry pro oba ${displaystyle mathbf {x} _ {k}}$ a ${displaystyle mathbf {y} _ {k}.}$

Li ${displaystyle mathbf {x} _ {k} v mathbb {R} ^ {2}}$ a ${displaystyle mathbf {y} _ {k} v mathbb {R} ^ {q}}$ předchozí výrazy mohou stále vést k rovnici

${displaystyle 0 = mathbf {x} _ {k} ^ {T}, mathbf {H}, mathbf {A}, mathbf {y} _ {k}}$ pro ${displaystyle, k = 1, ldots, N}$

kde ${displaystyle mathbf {A}}$ teď je ${displaystyle 2 imes q.}$ Každý k poskytuje jednu rovnici v ${displaystyle 2q}$ neznámé prvky ${displaystyle mathbf {A}}$ a společně lze tyto rovnice psát ${displaystyle mathbf {B}, mathbf {a} = mathbf {0}}$ pro známé ${displaystyle N imes 2, q}$ matice ${displaystyle mathbf {B}}$ a neznámé 2q-dimenzionální vektor ${displaystyle mathbf {a}.}$ Tento vektor lze najít podobným způsobem jako dříve.

V nejobecnějším případě ${displaystyle mathbf {x} _ {k} v mathbb {R} ^ {p}}$ a ${displaystyle mathbf {y} _ {k} v mathbb {R} ^ {q}}$. Hlavní rozdíl ve srovnání s dříve spočívá v tom, že matice ${displaystyle mathbf {H}}$ teď je ${displaystyle p imes p}$ a anti-symetrický. Když ${displaystyle p> 2}$ prostor takových matic již není jednorozměrný, má rozměr

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

To znamená, že každá hodnota k poskytuje M homogenní rovnice typu

${displaystyle 0 = mathbf {x} _ {k} ^ {T}, mathbf {H} _ {m}, mathbf {A}, mathbf {y} _ {k}}$ pro ${displaystyle, m = 1, ldots, M}$ a pro ${displaystyle, k = 1, ldots, N}$

kde ${displaystyle mathbf {H} _ {m}}$ je M-dimenzionální základ prostoru ${displaystyle p imes p}$ anti-symetrické matice.

Příklad p = 3

V případě, že p = 3 následující tři matice ${displaystyle mathbf {H} _ {m}}$ lze zvolit

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

V tomto konkrétním případě lze homogenní lineární rovnice psát jako

${displaystyle mathbf {0} = [mathbf {x} _ {k}] _ {imes}, mathbf {A}, mathbf {y} _ {k}}$ pro ${displaystyle, k = 1, ldots, N}$

kde ${displaystyle [mathbf {x} _ {k}] _ {imes}}$ je maticová reprezentace vektorového křížového produktu. Všimněte si, že tato poslední rovnice má vektorovou hodnotu; levá strana je nulový prvek v ${displaystyle mathbb {R} ^ {3}}$.

Každá hodnota k poskytuje tři homogenní lineární rovnice v neznámých prvcích ${displaystyle mathbf {A}}$. Nicméně od té doby ${displaystyle [mathbf {x} _ {k}] _ {imes}}$ má hodnost = 2, maximálně dvě rovnice jsou lineárně nezávislé. V praxi je proto běžné používat pouze dvě ze tří matic ${displaystyle mathbf {H} _ {m}}$například pro m= 1, 2. Lineární závislost mezi rovnicemi však závisí na ${displaystyle mathbf {x} _ {k}}$, což znamená, že v nešťastných případech by bylo lepší zvolit například m= 2,3. V důsledku toho, pokud počet rovnic není problémem, může být lepší použít všechny tři rovnice, když je matice ${displaystyle mathbf {B}}$ je postaven.

Lineární závislost mezi výslednými homogenními lineárními rovnicemi je obecným problémem případu p > 2 a musí být řešeno buď snížením množiny anti-symetrických matic ${displaystyle mathbf {H} _ {m}}$ nebo povolením ${displaystyle mathbf {B}}$ stát se větším, než je nutné pro určení ${displaystyle mathbf {a}.}$

Reference

• Richard Hartley a Andrew Zisserman (2003). Geometrie více pohledů v počítačovém vidění. Cambridge University Press. ISBN  978-0-521-54051-3.

externí odkazy

• Odhad homografie autor Elan Dubrofsky (§2.1 načrtává „Základní DLT algoritmus“)

• Řešič DLT založený na MATLABu autor: Hsiang-Jen (Johnny) Chien