Algebraické metody v počítačovém vidění

Abstrakt

Počítačové vidění vyžaduje schopnost efektivně řešit systémy polynomiálních rovnic. Například určování relativní nebo absolutní polohy kamery, lze formulovat jako minimální problémy, tedy je lze řešit z minimálního počtu vstupních dat. Minimální problémy vedou na systémy polynomiálních rovnic s konečným počtem řešení. Systémy vycházející z minimálnich problémů jsou často komplikované a obecné algoritmy k řešení systémů polynomiálních rovnic pro ně vedou na relativně neefektivní řešení. Proto je pro řešení těchto problémů obvykle zapotřebí navrhnout numericky robustní a výpočetně efektivní specifické algoritmy. V této disertaci navrhujeme modifikace dvou standartních algebraických technik pro řešení systémů polynomiálnich rovnic a to metody založené na Gröbnerových bázích a metody založené na rezultantech, které jsou vhodné právě pro efektivní řešení mnoha problémů v počítačovém vidění a jiných oblastech. Základní rozdíl mezi prezentovanými specializovanými metodami a standartními obecnými metodami je, že prezentované specializované metody využívají znalosti struktury systému polynomiálních rovnic, který reprezentuje konkrétní problém k návrhu efektivního a stabilního algoritmu na řešení tohoto problému. Při tomto návrhu se část výpočtů společná pro všechny instance daného problému připraví předem, což ušetří čas při opakovaném řešení systémů s identickou strukturou. Takto vytvořený algoritmus není obecným algoritmem a řeší jen systémy polynomiálních rovnic jednoho tvaru, avšak je rychlejší než obecné algoritmy a proto je vhodný pro aplikace, které se objevují například v počítačovém vidění. Obě navržené specializované metody mohou být snadno zautomatizovány a takto používány i neodborníky k řešení problémů vedoucích na systémy polynomiálnich rovnic. V této disertaci prezentujeme automatický generátor efektivních algoritmů založený na modifikované metodě Gröbnerových bázi. Jako ukázku užitečnosti obou navržených metod a našeho automatického generátoru v této disertaci prezentujeme nová efektivní a numericky stabilní řešení několika velmi důležitých problémů určování relativní polohy kamer. Většina těchto problémů nebyla v minulosti vyřešena. Mezi těmito problémy jsou problémy určování relativní polohy a kalibračních parametrů kalibrovaných, částečně kalibrovaných (s neznámou ohniskovou vzdáleností) nebo kompletně nekalibrovaných perspektivních kamer či kamer s radiálním zkreslením snímajících obecnou scénu nebo scénu s dominující rovinou. Všechny tyto algoritmy mohou být efektivně použity v aplikacích jako je lokalizace, rekonstrukce 3D scény či rozpoznávání. Kvalita prezentovaných algoritmů je demonstrována experimenty na syntetických i reálných datech