Osmibodový algoritmus - Eight-point algorithm

The osmibodový algoritmus je algoritmus používaný v počítačové vidění odhadnout základní matice nebo základní matice vztahující se ke dvojici stereofonních kamer ze sady odpovídajících obrazových bodů. To bylo představeno Christopher Longuet-Higgins v roce 1981 pro případ základní matice. Teoreticky lze tento algoritmus použít i pro základní matici, ale v praxi normalizovaný osmibodový algoritmus, který popsal Richard Hartley v roce 1997, je pro tento případ vhodnější.

Název algoritmu je odvozen od skutečnosti, že odhaduje základní matici nebo základní matici ze sady osmi (nebo více) odpovídajících obrazových bodů. Varianty algoritmu však lze použít pro méně než osm bodů.

Omezení koplanárnosti

Příklad epipolární geometrie. Dvě kamery s příslušnými středy projekčních bodů Ó_L a Ó_R, pozorujte bod P. Projekce P na každé z obrazových rovin p_L a p_R. Body E_L a E_R jsou epipoly.

Jeden může vyjádřit epipolární geometrie dvou kamer a bodu v prostoru s algebraickou rovnicí. Všimněte si toho, bez ohledu na to, kde to má smysl ${displaystyle P}$ je ve vesmíru, vektory ${displaystyle {overline {O_ {L} P}}}$ , ${displaystyle {overline {O_ {R} P}}}$ a ${displaystyle {overline {O_ {R} O_ {L}}}}$ patří do stejné roviny. Volání ${displaystyle X_ {L}}$ souřadnice bodu ${displaystyle P}$ v referenčním rámci levého oka a zavolejte ${displaystyle X_ {R}}$ souřadnice ${displaystyle P}$ v referenčním rámečku pravého oka a zavolejte ${displaystyle R, T}$ rotace a translace mezi dvěma referenčními snímky s.t. ${displaystyle X_ {R} = R (X_ {L} -T)}$ je vztah mezi souřadnicemi ${displaystyle P}$ ve dvou referenčních rámcích. Následující rovnice vždy platí, protože vektor generovaný z ${displaystyle Twedge X_ {L}}$ je kolmý k oběma ${displaystyle T}$ a ${displaystyle X_ {L}}$ :

{displaystyle X_ {L} ^ {T} Twedge X_ {L} -T ^ {T} Twedge X_ {L} = (X_ {L} -T) ^ {T} Twedge X_ {L} = 0}

Protože ${displaystyle I = R ^ {T} R}$ , dostaneme

{displaystyle (X_ {L} -T) ^ {T} R ^ {T} RTwedge X_ {L} = 0}

.

Výměna ${displaystyle (X_ {L} -T) ^ {T} R ^ {T}}$ s ${displaystyle X_ {R} ^ {T}}$ , dostaneme

{displaystyle X_ {R} ^ {T} RTwedge X_ {L} = X_ {R} ^ {T} RSX_ {L} = X_ {R} ^ {T} EX_ {L} = 0}

Dodržujte to ${displaystyle Twedge}$ lze považovat za matici; Longuet-Higgins použil tento symbol ${displaystyle S}$ naznačit to. Produkt ${displaystyle RTwedge = RS}$ se často nazývá základní matice a označeno ${displaystyle E}$ .

Vektory ${displaystyle {overline {O_ {L} p_ {L}}}, {overline {O_ {R} p_ {R}}}}$ jsou rovnoběžné s vektory ${displaystyle {overline {O_ {L} P}}, {overline {O_ {R} P}}}$ a proto platí omezení koplanárnosti, pokud tyto vektory dosadíme. Pokud zavoláme ${displaystyle y, y '}$ souřadnice projekcí ${displaystyle P}$ do levé a pravé obrazové roviny, pak může být omezení koplanárnosti zapsáno jako

{displaystyle y '^ {T} mathbf {E} y = 0}

Základní algoritmus

Zde je popsán základní osmibodový algoritmus pro případ odhadu základní matice ${displaystyle mathbf {E}}$ . Skládá se ze tří kroků. Nejprve formuluje a homogenní lineární rovnice, kde řešení přímo souvisí ${displaystyle mathbf {E}}$ , a poté rovnici vyřeší, přičemž vezme v úvahu, že nemusí mít přesné řešení. Nakonec jsou spravována vnitřní omezení výsledné matice. První krok je popsán v práci Longuet-Higgins, druhý a třetí krok jsou standardní přístupy v teorii odhadu.

Omezení definované základní maticí ${displaystyle mathbf {E}}$ je

{displaystyle (mathbf {y} ') ^ {T}, mathbf {E}, mathbf {y} = 0}

pro odpovídající obrazové body představované v normalizovaných souřadnicích obrazu ${displaystyle mathbf {y}, mathbf {y} '}$ . Problém, který algoritmus řeší, je určit ${displaystyle mathbf {E}}$ pro sadu odpovídajících obrazových bodů. V praxi jsou obrazové souřadnice obrazových bodů ovlivněny šumem a řešení může být také nadměrně určeno, což znamená, že nemusí být možné najít ${displaystyle mathbf {E}}$ který splňuje výše uvedené omezení přesně pro všechny body. Tato otázka je řešena ve druhém kroku algoritmu.

Krok 1: Formulace a homogenní lineární rovnice

S

{displaystyle mathbf {y} = {egin {pmatrix} y_ {1} y_ {2} 1end {pmatrix}}}

a

{displaystyle mathbf {y} '= {egin {pmatrix} y' _ {1} y '_ {2} 1end {pmatrix}}}

a

{displaystyle mathbf {E} = {egin {pmatrix} e_ {11} & e_ {12} & e_ {13} e_ {21} & e_ {22} & e_ {23} e_ {31} & e_ {32} & e_ {33} konec {pmatrix}}}

omezení lze také přepsat jako

{displaystyle y '_ {1} y_ {1} e_ {11} + y' _ {1} y_ {2} e_ {12} + y '_ {1} e_ {13} + y' _ {2} y_ {1} e_ {21} + y '_ {2} y_ {2} e_ {22} + y' _ {2} e_ {23} + y_ {1} e_ {31} + y_ {2} e_ {32 } + e_ {33} = 0,}

nebo

{displaystyle mathbf {e} cdot {ilde {mathbf {y}}} = 0}

kde

{displaystyle {ilde {mathbf {y}}} = {egin {pmatrix} y '_ {1} y_ {1} y' _ {1} y_ {2} y '_ {1} y' _ { 2} y_ {1} y '_ {2} y_ {2} y' _ {2} y_ {1} y_ {2} 1end {pmatrix}}}

a

{displaystyle mathbf {e} = {egin {pmatrix} e_ {11} e_ {12} e_ {13} e_ {21} e_ {22} e_ {23} e_ {31} e_ {32 } e_ {33} konec {pmatrix}}}

to je ${displaystyle mathbf {e}}$ představuje základní matici ve formě 9-dimenzionálního vektoru a tento vektor musí být na vektor kolmý ${displaystyle {ilde {mathbf {y}}}}$ což lze považovat za vektorovou reprezentaci ${displaystyle 3 imes 3}$ matice ${displaystyle mathbf {y} ', mathbf {y} ^ {T}}$ .

Každá dvojice odpovídajících obrazových bodů vytváří vektor ${displaystyle {ilde {mathbf {y}}}}$ . Vzhledem k sadě 3D bodů ${displaystyle mathbf {P} _ {k}}$ to odpovídá množině vektorů ${displaystyle {ilde {mathbf {y}}} _ {k}}$ a všichni musí uspokojit

{displaystyle mathbf {e} cdot {ilde {mathbf {y}}} _ {k} = 0}

pro vektor ${displaystyle mathbf {e}}$ . Vzhledem k dostatečně velkému počtu (nejméně osmi) lineárně nezávislých vektorů ${displaystyle {ilde {mathbf {y}}} _ {k}}$ je možné určit ${displaystyle mathbf {e}}$ přímočarým způsobem. Sbírejte všechny vektory ${displaystyle {ilde {mathbf {y}}} _ {k}}$ jako sloupce matice ${displaystyle mathbf {Y}}$ a pak to tak musí být

{displaystyle mathbf {e} ^ {T}, mathbf {Y} = mathbf {0}}

Tohle znamená tamto ${displaystyle mathbf {e}}$ je řešení a homogenní lineární rovnice.

Krok 2: Řešení rovnice

To naznačuje standardní přístup k řešení této rovnice ${displaystyle mathbf {e}}$ je levý singulární vektor z ${displaystyle mathbf {Y}}$ odpovídající a singulární hodnota to se rovná nule. Za předpokladu, že alespoň osm lineárně nezávislých vektorů ${displaystyle {ilde {mathbf {y}}} _ {k}}$ se používají ke konstrukci ${displaystyle mathbf {Y}}$ z toho vyplývá, že tento singulární vektor je jedinečný (bez ohledu na skalární násobení) a v důsledku toho ${displaystyle mathbf {e}}$ a pak ${displaystyle mathbf {E}}$ lze určit.

V případě, že ke konstrukci je použito více než osm odpovídajících bodů ${displaystyle mathbf {Y}}$ je možné, že nemá žádnou singulární hodnotu rovnou nule. K tomuto případu dochází v praxi, když jsou souřadnice obrazu ovlivněny různými typy šumu. Běžným přístupem k řešení této situace je popsat ji jako a celkem nejméně čtverců problém; nalézt ${displaystyle mathbf {e}}$ což minimalizuje

{displaystyle | mathbf {e} ^ {T}, mathbf {Y} |}

když ${displaystyle | mathbf {e} | = 1}$ . Řešením je vybrat si ${displaystyle mathbf {e}}$ jako levý singulární vektor odpovídající nejmenší singulární hodnota ${displaystyle mathbf {Y}}$ . Změna pořadí ${displaystyle mathbf {e}}$ zpět do a ${displaystyle 3 imes 3}$ matice dává výsledek tohoto kroku, zde označovaného jako ${displaystyle mathbf {E} _ {m {est}}}$ .

Krok 3: Prosazování vnitřního omezení

Dalším důsledkem řešení hlučných souřadnic obrazu je, že výsledná matice nemusí uspokojit vnitřní omezení základní matice, to znamená, že dvě z jejích singulárních hodnot jsou stejné a nenulové a druhá je nula. V závislosti na aplikaci mohou nebo nemusí být menší nebo větší odchylky od vnitřního omezení problém. Pokud je kritické, aby odhadovaná matice splňovala vnitřní omezení, lze toho dosáhnout vyhledáním matice ${displaystyle mathbf {E} '}$ 2. úrovně, která se minimalizuje

{displaystyle | mathbf {E} '-mathbf {E} _ {m {est}} |}

kde ${displaystyle mathbf {E} _ {m {est}}}$ je výsledná matice z kroku 2 a Frobeniova maticová norma se používá. Řešení problému je dáno nejprve výpočtem a rozklad singulární hodnoty z ${displaystyle mathbf {E} _ {m {est}}}$ :

{displaystyle mathbf {E} _ {m {est}} = mathbf {U}, mathbf {S}, mathbf {V} ^ {T}}

kde ${displaystyle mathbf {U}, mathbf {V}}$ jsou ortogonální matice a ${displaystyle mathbf {S}}$ je diagonální matice, která obsahuje singulární hodnoty ${displaystyle mathbf {E} _ {m {est}}}$ . V ideálním případě jeden z diagonálních prvků ${displaystyle mathbf {S}}$ by měla být nula nebo alespoň malá ve srovnání s ostatními dvěma, které by měly být stejné. V každém případě nastavte

{displaystyle mathbf {S} '= {egin {pmatrix} s_ {1} & 0 & 0 0 & s_ {2} & 0 0 & 0 & 0end {pmatrix}},}

kde ${displaystyle s_ {1}, s_ {2}}$ jsou největší a druhou největší singulární hodnotou v ${displaystyle mathbf {S}}$ resp. Konečně, ${displaystyle mathbf {E} '}$ je dána

{displaystyle mathbf {E} '= mathbf {U}, mathbf {S}', mathbf {V} ^ {T}}

Matice ${displaystyle mathbf {E} '}$ je výsledný odhad základní matice poskytnutý algoritmem.

Normalizovaný algoritmus

Základní osmibodový algoritmus lze v zásadě použít také pro odhad základní matice ${displaystyle mathbf {F}}$ . Definující omezení pro ${displaystyle mathbf {F}}$ je

{displaystyle (mathbf {y} ') ^ {T}, mathbf {F}, mathbf {y} = 0}

kde ${displaystyle mathbf {y}, mathbf {y} '}$ jsou homogenní reprezentace odpovídajících obrazových souřadnic (není nutné normalizovat). To znamená, že je možné vytvořit matici ${displaystyle mathbf {Y}}$ podobným způsobem jako u základní matice a řešit rovnici

{displaystyle mathbf {f} ^ {T}, mathbf {Y} = mathbf {0}}

pro ${displaystyle mathbf {f}}$ což je přetvořená verze ${displaystyle mathbf {F}}$ . Postupováním podle výše uvedeného postupu je pak možné určit ${displaystyle mathbf {F}}$ ze sady osmi shodných bodů. V praxi však výsledná základní matice nemusí být užitečná pro určení epipolárních omezení.

Obtížnost

Problém je, že výsledný ${displaystyle mathbf {Y}}$ často je špatně podmíněný. Teoreticky, ${displaystyle mathbf {Y}}$ by měl mít jednu singulární hodnotu rovnou nule a zbytek je nenulový. V praxi se však některé nenulové singulární hodnoty mohou vzhledem k větším zmenšit. Pokud se ke konstrukci použije více než osm odpovídajících bodů ${displaystyle mathbf {Y}}$ , kde jsou souřadnice pouze přibližně správné, nemusí existovat dobře definovaná singulární hodnota, kterou lze identifikovat jako přibližně nulu. V důsledku toho nemusí být řešení homogenního lineárního systému rovnic dostatečně přesné, aby bylo užitečné.

Způsobit

Hartley se tímto problémem odhadu zabýval ve svém článku z roku 1997. Jeho analýza problému ukazuje, že problém je způsoben špatným rozložením homogenních obrazových souřadnic v jejich prostoru, ${displaystyle mathbb {R} ^ {3}}$ . Typická homogenní reprezentace souřadnice 2D obrazu ${displaystyle (y_ {1}, y_ {2}),}$ je

{displaystyle mathbf {y} = {egin {pmatrix} y_ {1} y_ {2} 1end {pmatrix}}}

kde oba ${displaystyle y_ {1}, y_ {2},}$ leží v rozmezí 0 až 1000 - 2000 pro moderní digitální fotoaparát. To znamená, že první dvě souřadnice v ${displaystyle mathbf {y}}$ se mění v mnohem větším rozsahu než třetí souřadnice. Dále, pokud obraz ukazuje, které se používají ke konstrukci ${displaystyle mathbf {Y}}$ leží v relativně malé oblasti obrazu, například v ${displaystyle (700 700) pm (100 100),}$ , opět vektor ${displaystyle mathbf {y}}$ body ve více či méně stejném směru pro všechny body. Jako následek, ${displaystyle mathbf {Y}}$ bude mít jednu velkou singulární hodnotu a zbývající jsou malé.

Řešení

Jako řešení tohoto problému Hartley navrhl, aby se souřadnicový systém každého ze dvou obrazů nezávisle transformoval do nového souřadnicového systému podle následujícího principu.

Počátek nového souřadného systému by měl být vycentrován (mít svůj počátek) na těžiště (těžiště) obrazových bodů. Toho je dosaženo překladem původního původu do nového.
Po překladu jsou souřadnice rovnoměrně upraveny tak, aby se střední vzdálenost od počátku k bodu rovnala ${displaystyle {sqrt {2}}}$ .

Tento princip obvykle vede ke zřetelné transformaci souřadnic pro každý ze dvou obrazů. Výsledkem jsou nové homogenní souřadnice obrazu ${displaystyle mathbf {ar {y}}, mathbf {ar {y}} '}$ jsou dány

{displaystyle mathbf {ar {y}} = mathbf {T}, mathbf {y}}

{displaystyle mathbf {ar {y}} '= mathbf {T}', mathbf {y} '}

kde ${displaystyle mathbf {T}, mathbf {T} '}$ jsou transformace (překlad a změna měřítka) ze starého do nového normalizované souřadnice obrazu. Tato normalizace je závislá pouze na obrazových bodech, které jsou použity v jediném snímku, a je obecně odlišná od normalizovaných obrazových souřadnic vytvořených normalizovanou kamerou.

Epipolární omezení založené na základní matici lze nyní přepsat na

{displaystyle 0 = (mathbf {ar {y}} ') ^ {T}, ((mathbf {T}') ^ {T}) ^ {- 1}, mathbf {F}, mathbf {T} ^ {- 1}, mathbf {ar {y}} = (mathbf {ar {y}} ') ^ {T}, mathbf {ar {F}}, mathbf {ar {y}}}

kde ${displaystyle mathbf {ar {F}} = ((mathbf {T} ') ^ {T}) ^ {- 1}, mathbf {F}, mathbf {T} ^ {- 1}}$ . To znamená, že je možné použít normalizované homogenní souřadnice obrazu ${displaystyle mathbf {ar {y}}, mathbf {ar {y}} '}$ odhadnout transformovanou základní matici ${displaystyle mathbf {ar {F}}}$ pomocí základního osmibodového algoritmu popsaného výše.

Účelem normalizačních transformací je matice ${displaystyle mathbf {ar {Y}}}$ , zkonstruované z normalizovaných obrazových souřadnic, má obecně lepší číslo podmínky než ${displaystyle mathbf {Y}}$ má. To znamená, že řešení ${displaystyle mathbf {ar {f}}}$ je lépe definována jako řešení homogenní rovnice ${displaystyle mathbf {ar {Y}}, mathbf {ar {f}}}$ než ${displaystyle mathbf {f}}$ je relativní k ${displaystyle mathbf {Y}}$ . Jednou ${displaystyle mathbf {ar {f}}}$ byl rozhodnut a přetvořen do ${displaystyle mathbf {ar {F}}}$ to druhé může být deaktivováno dát ${displaystyle mathbf {F}}$ podle

{displaystyle mathbf {F} = (mathbf {T} ') ^ {T}, mathbf {ar {F}}, mathbf {T}}

Obecně je tento odhad základní matice lepší, než jaký by byl získán odhadem z nenormalizovaných souřadnic.

Použití méně než osmi bodů

Každý pár bodů přispívá jednou omezující rovnicí prvku v ${displaystyle mathbf {E}}$ . Od té doby ${displaystyle mathbf {E}}$ má pět stupňů volnosti, proto by to mělo stačit k určení pouze pěti dvojic bodů ${displaystyle mathbf {E}}$ . I když je to z teoretického hlediska možné, praktická implementace není přímá a spoléhá se na řešení různých nelineárních rovnic.

Kaveh Fathian a kol. navrhované algoritmy pro pět, šest a sedm bodů, které obcházejí výpočet základní matice přímým výpočtem rotačního čtveřice.^[1]^[2]

Viz také

Reference

^ Fathian, Kaveh (2018). „QuEst: Kvartérní přístup k odhadu pohybu fotoaparátu z minimálních bodů funkcí“. IEEE Robotics and Automation Letters. arXiv:1704.02672. doi:10.1109 / LRA.2018.2792142.
^ Fathian, Kaveh (2018). "Odhad relativní pozice kamery pro vizuální servoování pomocí čtveřic". Robotika a autonomní systémy. doi:10.1016 / j.robot.2018.05.014.

Další čtení

Richard I.Hartley (červen 1997). „Na obranu osmibodového algoritmu“. Transakce IEEE na rozpoznávání vzorů a strojové inteligenci. 19 (6): 580–593. doi:10.1109/34.601246.

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.

H. Christopher Longuet-Higgins (září 1981). "Počítačový algoritmus pro rekonstrukci scény ze dvou projekcí". Příroda. 293 (5828): 133–135. doi:10.1038 / 293133a0.

[1] Fathian, Kaveh (2018). „QuEst: Kvartérní přístup k odhadu pohybu fotoaparátu z minimálních bodů funkcí“. IEEE Robotics and Automation Letters. arXiv:1704.02672. doi:10.1109 / LRA.2018.2792142.

[2] Fathian, Kaveh (2018). "Odhad relativní pozice kamery pro vizuální servoování pomocí čtveřic". Robotika a autonomní systémy. doi:10.1016 / j.robot.2018.05.014.

[1]

[2]