Odhad vzdálenosti překážek od automobilu ze sekvence obrazů

CENTER FOR MACHINE PERCEPTION

Odhad vzdálenosti překážek od automobilu ze sekvence obrazů

CZECH TECHNICAL

Ondřej Sychrovský

UNIVERSITY

[email protected]

CTU–CMP–2008–12

Lze získat na ftp://cmp.felk.cvut.cz/pub/cmp/articles/pajdla/Sychrovsky-TR-2008-12.pdf Školitel: Ing. Tomáš Pajdla, Ph.D.

Research Reports of CMP, Czech Technical University in Prague, No. 12, 2008 ISSN 1213-2365

DIPLOMOVÁ PRÁCE

19. května 2008

Published by Centrum strojového vnímání, Katedra kybernetiky Fakulta elektrotechnická ČVUT Technická 2, 166 27 Praha 6 fax: (02) 2435 7385, tel: (02) 2435 7637, www: http://cmp.felk.cvut.cz

České vysoké učení technické v Praze Fakulta elektrotechnická

DIPLOMOVÁ PRÁCE Odhad vzdálenosti překážek od automobilu ze sekvence obrazů Ondřej Sychrovský

Školitel: Ing. Tomáš Pajdla, Ph.D.

19. května 2008

Prohlášení Prohlašuji, že jsem svoji diplomovou práci vypracoval samostatně a použil jsem pouze podklady (literaturu, projekty, SW atd.) uvedené v přiloženém seznamu.

V Praze dne 19. května 2008

Ondřej Sychrovský

ii

Abstrakt Klasické systémy pro detekci překážek, kterými jsou automobily dnes vybaveny, jsou založeny na mechanickém šíření ultrazvukových vln. V této práci jsme navrhli asistenční systém pro detekci překážek na základě sekvence obrazů z kamery, která je umístěna v zadní části vozu. Nejprve nalezneme významné body v obrazech a určíme jejich korespondence v po sobě jdoucích obrazech. Z takto získaných korespondencí nalezneme pomocí metody RANSAC epipolární geometrii. Na základě známých vnitřních parametrů kamery a známé ujeté vzdálenosti mezi snímky můžeme rekonstruovat trojrozměrnou scénu. Body v obrazech jsou ovšem určeny s nepřesností, která je způsobena šumem měření. Tento šum jsme modelovali jako náhodnou veličinu s normálním rozdělením a zahrnuli jej do výpočtu. Navrhli jsme metodu, jak se rozhodovat v přítomnosti tohoto šumu na základě výpočtu pravděpodobnosti polohy jednotlivých bodů v prostoru. Funkčnost navrženého systému jsme ověřili na reálných datech. Experimenty s různými přirozenými překážkami ukazují, že systém funguje dobře. Simulovali jsme také couvání k barevně nevýrazné zdi. V tomto případě nebylo možné scénu zrekonstruovat a systém selhal. Pokud ovšem scénu rekonstruovat můžeme, experimenty, které jsme provedli, ukazují, že program vždy správně rozhodl a nenechal vozidlo do překážky narazit.

Klíčová slova detekce překážek, epipolární geometie, asistenční systémy řidiče, zpracování obrazu

iii

Car-to-obstacle distance estimation from a sequence of images

Abstract Obstacle detection systems that vehicles are nowadays equipped with are based on mechanical ultrasound waves measurement. In this work, we propose an assistance system for obstacle detection based on a sequence of images captured from a camera mounted on the rear of a vehicle. At first we locate significant points in images and track them over consecutive frames. From these corresponding points we estimate epipolar geometry using RANSAC. Knowing the intrinsic camera parameters and the travelled distance between two frames we can reconstruct the 3D scene. However, the points in images are located inaccurately due to the measurement noise. We model this noise as a random variable with Gaussian distribution and include it in the computation process. We propose a decision method working in presence of noise based on points’ space position probability. We have evaluated the performance of our system on experimental data. The experiments show that the proposed system works quite correctly. We have also simulated reversing towards a gray non-textured wall. In that case the system was unable to estimate the geometry and the decision process failed. However, in experiments in which we were able to reconstruct the 3D scene, the system always decided correctly and didn’t let the vehicle hit the obstacle.

Keywords obstacle detection, epipolar geometry, driver assistance systems, image processing

iv

Obsah 1. Úvod

1

2. Teoretický rozbor úlohy 2.1. Vstupní data . . . . . . . . . . . . . . . . . . . . . . . 2.2. Stanovení korespondencí mezi dvěma obrazy . . . . . . 2.2.1. Nalezení významných bodů . . . . . . . . . . . 2.2.2. Stanovení korespondencí pro dva obrazy . . . . 2.3. Model kamery . . . . . . . . . . . . . . . . . . . . . . . 2.3.1. Vnější parametry . . . . . . . . . . . . . . . . . 2.3.2. Vnitřní parametry . . . . . . . . . . . . . . . . 2.3.3. Projekční matice kamery . . . . . . . . . . . . . 2.3.4. Kalibrovaná kamera . . . . . . . . . . . . . . . 2.3.5. Stanovení parametrů – kalibrace . . . . . . . . . 2.4. Epipolární geometrie . . . . . . . . . . . . . . . . . . . 2.4.1. Fundamentální matice . . . . . . . . . . . . . . 2.4.2. Esenciální matice . . . . . . . . . . . . . . . . . 2.5. Výpočet esenciální matice . . . . . . . . . . . . . . . . 2.5.1. 5-bodový algoritmus . . . . . . . . . . . . . . . 2.5.2. RANSAC . . . . . . . . . . . . . . . . . . . . . 2.6. Zpracování esenciální matice . . . . . . . . . . . . . . . 2.6.1. Stanovení matic kamer . . . . . . . . . . . . . . 2.6.2. Nalezení 3D souřadnic bodů v obrazech . . . . . 2.7. Rekonstrukce 1:1 . . . . . . . . . . . . . . . . . . . . . 2.7.1. Zvětšení . . . . . . . . . . . . . . . . . . . . . . 2.7.2. Rotace a posunutí . . . . . . . . . . . . . . . . . 2.8. Nepřesnost lokalizace bodů v prostoru . . . . . . . . . 2.8.1. Skutečná neurčitost . . . . . . . . . . . . . . . . 2.8.2. Převedení neurčitosti do epipolární roviny . . . 2.8.3. Výpočet neurčitosti bodu v prostoru . . . . . . 2.8.4. Pokus o aproximaci normálním rozdělením . . . 2.9. Rozhodnutí o překážkách . . . . . . . . . . . . . . . . . 2.9.1. Rozměry vozidla . . . . . . . . . . . . . . . . . 2.9.2. Rozhodovací kritérium . . . . . . . . . . . . . . 2.10. Propojení více rekonstrukcí . . . . . . . . . . . . . . . 2.10.1. Určení počtu kroků, kdy překážka nebude vidět 2.10.2. Dvě rekonstrukce . . . . . . . . . . . . . . . . .

v

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3 3 4 5 6 8 8 9 11 11 12 12 13 14 15 15 16 18 18 19 20 20 21 22 22 23 23 24 25 26 27 30 31 31

Obsah 2.10.3. Více rekonstrukcí . . . . . . . . . . . . . . . . . . . . . . . . . 33 3. Popis algoritmu 3.1. Vstup . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.1.1. Data . . . . . . . . . . . . . . . . . . . . . . . . . 3.1.2. Kamera . . . . . . . . . . . . . . . . . . . . . . . 3.2. Výstup . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.3. Algoritmus . . . . . . . . . . . . . . . . . . . . . . . . . . 3.3.1. Nalezení významných bodů v obraze . . . . . . . 3.3.2. Nalezení kandidátů na korespondenci . . . . . . . 3.3.3. Propojení korespondencí přes více snímků (tracks) 3.3.4. Výběr dat pro výpočet geometrie . . . . . . . . . 3.3.5. Výpočet esenciální matice . . . . . . . . . . . . . 3.3.6. Výpočet matic kamer z esenciální matice . . . . . 3.3.7. Výpočet 3D souřadnic bodů . . . . . . . . . . . . 3.3.8. Transformace do 1:1 . . . . . . . . . . . . . . . . 3.3.9. Rozhodnutí . . . . . . . . . . . . . . . . . . . . . 3.3.10. Spojení více geometrií . . . . . . . . . . . . . . . 4. Experimentální ověření funkce 4.1. Kamera . . . . . . . . . . . . . . . . . 4.1.1. Kalibrace . . . . . . . . . . . . 4.1.2. Orientace v soustavě vozidla . . 4.1.3. Nejistota měření bodů v obraze 4.2. Rozměry vozidla . . . . . . . . . . . . 4.3. Experimenty . . . . . . . . . . . . . . . 4.3.1. První experiment . . . . . . . . 4.3.2. Druhý experiment . . . . . . . . 4.3.3. Třetí experiment . . . . . . . . 4.3.4. Čtvrtý experiment . . . . . . . 4.3.5. Pátý experiment . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . . . . . .

34 34 34 34 35 35 36 36 37 37 38 40 40 41 41 42

. . . . . . . . . . .

44 44 44 45 46 48 48 48 48 48 51 53

5. Možná vylepšení algoritmu

55

6. Závěr

56

Literatura

57

Přílohy A. Obsah přiloženého CD

60

vi

Seznam obrázků 2.1. Instalace magnetů na kole. . . . . . . . . . . . . . . . . . . . . . 2.2. Vnější parametry kamery. . . . . . . . . . . . . . . . . . . . . . 2.3. Promítnutí bodu v prostoru do obrazu. . . . . . . . . . . . . . . 2.4. Projekce bodu do plochy obrazu. . . . . . . . . . . . . . . . . . 2.5. Schéma epipolární geometrie . . . . . . . . . . . . . . . . . . . . 2.6. Ilustrace nesplnění epipolární podmínky . . . . . . . . . . . . . 2.7. Orientace souřadných systémů kamery a vozidla. . . . . . . . . . 2.8. Skutečné rozdělení pravděpodobnosti pro rekonstrukci bodu . . 2.9. Pravděpodobnost polohy bodu v prostoru. . . . . . . . . . . . . 2.10. Použitý model neurčitosti určení bodu. . . . . . . . . . . . . . . 2.11. Porovnání skutečné a aproximované hustoty pravděpodobnosti. . 2.12. Model vnějších rozměrů vozidla. . . . . . . . . . . . . . . . . . . 2.13. Pravděpodobnost polohy bodu. . . . . . . . . . . . . . . . . . . 2.14. Průsečík vozidla a epipolární roviny – v prostoru. . . . . . . . . 2.15. Průsečík vozidla a epipolární roviny – v rovině. . . . . . . . . . 2.16. Když přestane být překážka vidět. . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

4 9 9 10 13 19 21 23 24 25 26 27 28 30 31 32

3.1. Omezení polohy kamery P0 při výpočtu esenciální matice . . . . . . . 39 4.1. 4.2. 4.3. 4.4.

Fotografie umístění kamery na vozidle. . . . . . . . . . . . . Snímky s kalibračním obrazcem pro kameru Unibrain. . . . . Kalibrační obrazec pro vztah mezi vozidlem a kamerou. . . . Pomocná souřadná soustava pro určení vztahu mezi kamerou dlem. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.5. První experiment . . . . . . . . . . . . . . . . . . . . . . . . 4.6. Druhý experiment . . . . . . . . . . . . . . . . . . . . . . . . 4.7. Třetí experiment . . . . . . . . . . . . . . . . . . . . . . . . 4.8. Čtvrtý experiment . . . . . . . . . . . . . . . . . . . . . . . 4.9. Čtvrtý experiment – graf rozhodnutí . . . . . . . . . . . . . 4.10. Pátý experiment . . . . . . . . . . . . . . . . . . . . . . . . .

vii

. . . a . . . . . . .

. . . . . . . . . vozi. . . . . . . . . . . . . . . . . . . . .

. 44 . 45 . 46 . . . . . . .

47 49 50 51 52 53 54

Seznam tabulek 2.1. Možnosti při rozhodování o překážce. . . . . . . . . . . . . . . . . . . 29 4.1. Vnitřní parametry kamery získané kalibrací. . . . . . . . . . . . . . . 45 4.2. Rozměry vozidla použitého při experimentech. . . . . . . . . . . . . . 48

viii

1. Úvod Asistenční systémy řidiče zažívají v posledních letech nebývalý rozvoj. Výrobci automobilů se snaží zvyšovat komfort řidiče i posádky nepřeberným množstvím systémů, které zjednodušují a zpříjemňují řízení vozidla. Jedním ze systémů, které jsou ve vozidlech již několik let používány, je ultrazvukový detektor překážek. Tento systém, označovaný jako parkovací asistent, měří vzdálenost na principu mechanického zvukového vlnění. V případě, že se u vozidla nachází nějaká překážka, zvuk se od ní odrazí a systém tento signál zachytí a vyhodnotí. Ultrazvukový asistent pro detekci překážek v současné době nabízí téměř každý výrobce automobilů v různých variantách. Někteří výrobci mají vyvinuté systémy svoje, někteří používají komerční řešení od jiných společností [1,8]. Základní variantou je umístění senzorů do zadní části vozu a signalizace překážky pro celou zadní část. Vyšší variantou je signalizace překážky zvlášť pro levou a zvlášť pro pravou stranu vozu a nejvyšší variantou je kombinace senzorů vzadu i vpředu. Některé automobilky nabízejí automatický parkovací systém pro parkovaní do řady stojících vozidel na základě ultrazvukových senzorů [1]. Vozidlo je vybaveno kromě senzorů vpředu a vzadu ještě dvěma senzory na stranách před předními koly. Pokud systém při jízdě aktivujeme, je jedním z těchto senzorů hledána mezera pro naše vozidlo. Systém nás upozorní v okamžiku, kdy nějakou nalezne a následně umí točit volantem a vozidlo do nalezené mezery zaparkovat. Se zvyšujícím se počem kamer instalovaných do vozidel přibývá systémů, které poskytují řidiči informace na základě zpracovaného videa. Kamery jsou instalovány na záď vozidla a samy o sobě zjednodušují couvání k překážkám. Systémy, které pracují s těmito kamerami jsou z velké části pasivní. Velká část automobilů vybavených kamerou ukazuje pouze neupravený obraz. Některé systémy do obrazu kreslí nehybné čáry, které zobrazují předem pevně nastavené vzdálenosti od vozidla. Pokročilejší systémy umí podle natočení volantu do obrazu vyznačit, kam se bude vozidlo pohybovat. Nejsložitější automatický parkovací systém, který je v současné době k dispozici umí parkovat podélně i kolmo ke směru jízdy [2]. Tento systém do obrazu ze zpětné kamery nakreslí obdélník, který představuje cílovou polohu vozidla a tento obdélník může řidič libovolně posunovat. Dále je v obraze možné vyznačit překážku, které se musí vozidlo vyhnout. Systém pak opět sám točí volantem a vozidlo navede na cílovou pozici. Tento systém ale stále pracuje s informacemi z ultrazvukových senzorů.

1

1. Úvod Cíl práce Cílem této práce je vytvořit detektor překážek, který zpracovává pouze signál z kamery, která je umístěna v zadní části vozu. Zpracování obrazu a usuzování na strukturu scény je obecně špatně podmíněná úloha a proto není možné zaručit, že takový systém bude vždy bezchybně fungovat. Chceme zjistit, jak může být systém detekce překážek, který funguje pouze na základě videosignálu, spolehlivý a jaké problémy mohou nastat. Ukážeme, že v příznivých případech jsou výsledky velice dobré, ale že existují i takové situace, kdy systém selže. Jiná díla zabývající se detekcí překážek Problému detekce překážek se věnuje velké množství literatury. Převážně se jedná o problémy spojené s automatickým pohybem a navigací mobilních robotů. Na principu výpočtu optického toku je založen přístup podle [9]. Autoři zde počítají optický tok metodou normalizované vzájemné korelace a z ní dále tzv. time to contact (čas do srážky) pro všechny nalezené body. Podobně jedná i [4], který ale používá jinou metodu na výpočet optického toku. Dále také tento tok zpracovává a počítá čas do srážky. Jiná metoda je k nalezení v [12]. Zde se předpokládá, že se robot pohybuje na rovné zemi a tím pádem víme, jak má vypadat optický tok, když v cestě není žádná překážka. Tento se pak porovná se skutečným změřeným tokem a překážka může způsobit, že se tyto dva toky budou lišit. Na principu výpočtu korespondencí významných bodů (podobně jako je naše práce) je založeno dílo [11]. Je zde uveden postup pro počáteční fáze naší práce spolu s informacemi, jak tyto výpočty optimálně implementovat na počítači. Struktura diplomové práce Další část diplomové práce je organizována následovně: Kapitola 2 popisuje funkce a principy metod použitých při výpočtu a kapitola 3 přesně popisuje algoritmus našeho programu, který jsme vytvořili. Kapitola 4 ukazuje experimenty, které jsme provedli. V kapitole 5 jsou uvedeny modifikace, kterými by bylo možné navržený systém vylepšit a konečně kapitola 6 shrnuje výsledky, kterých jsme dosáhli.

2

2. Teoretický rozbor úlohy V této kapitole podrobně popíšeme metody a principy, které jsme v této úloze použili. Uvedeme teoretické postupy a odvodíme některé zákonitosti, které v našem problému využijeme: • Forma vstupních dat. • Jak spolu provážeme vstupní obrazy. • Jak budeme modelovat projekci bodů ze světa do obrazu. • Proč chceme použít kalibrovanou kameru. • Jak vypočítáme prostorovou strukturu scény z obrazů. • Podle čeho budeme klasifikovat jednotlivé body jako překážky.

2.1. Vstupní data Zpracování dat neprobíhá v reálném čase. Experimenty jsme prováděli s kamerou namontovanou na vozidle. Signál byl nahráván do PC a ukládán do videosouboru. Rozlišení videa je 640x480 obrazových bodů a video je nahráno a zpracováno v odstínech šedi. Všechna další zpracování se pak týkají vždy daného souboru. Parametry kamery a způsob montáže je uveden později v další kapitole. Jelikož pro správnou rekostrukci scény je nutné vědět i to, jaké jsou vzdálenosti mezi jednotlivými kamerami1 při snímání jednotlivých snímků, bylo nutné zaznamenat pohyb vozu. Metoda, kterou jsme zvolili funguje na principu bezkontaktního měření otáčení kola. Na zadním kole je umístěno několik magnetů. Proti nim je umístěn pevný magnetický spínač, který sepne, když se do jeho blízkosti dostane magnet pootočením kola. Při dalším otočením se magnet dostane opět dál a spínač rozepne. Při známém obvodu kola a rozložení magnetů můžeme vypočítat vzdálenost, kterou vůz přibližně ujede mezi dvěma okamžiky sepnutí spínače. Fyzická realizace je zobrazena na obrázku 2.1. Obvod, který je takto spínán, uvádí do provozu piezo bzučák, který po dobu sepnutí píská. Při nahrávání videosignálu je také nahráván zvuk pomocí mikrofonu 1

Ve skutečnosti se stále jedná o jedinou kameru, která se pohybuje, ale také si to můžeme představit tak, že ty snímky jsou vyfoceny najednou několika kamerami. V tomto není z pohledu naší úlohy rozdíl. Ve druhém případě se však tato vzdálenost dá lépe představit a proto je to tak řečeno.

3

2. Teoretický rozbor úlohy

Obrázek 2.1.: Fotografie zachycující instalaci magnetů a magnetického snímače pro získání informace o ujeté vzdálenosti. Spínač je sepnut vždy po ujetí 1/10 otáčky, což je přibližně 173 mm.

umístného na počítači. Výsledkem pak je tedy videosoubor se zvukovou stopou, podle které se pak dají přesně určit snímky, které korespondují se známou ujetou vzdáleností.

2.2. Stanovení korespondencí mezi dvěma obrazy Aby bylo možné danou úlohu vůbec začít řešit, je nutné stanovit spojitosti mezi jednotlivými obrazy. V našem případě jsou snímky vybírány z videosekvence, ale to samo o sobě neříká nic o tom, co se na nich vyskytuje. Znalost toho, že jsou jednotlivé snímky ve videosekvenci a tím pádem snímány ve velmi krátkých časech od sebe, využijeme, protože se dá předpokládat, že se scéna mezi dvěma snímky změní jen málo. Metoda, kterou jsme použili v této práci je následující: Nejprve jsou v obou obrazech nalezeny významné body. Dále je každý bod z prvního2 obrazu porovnán s každým bodem ve druhém obraze. Na základě podobností jsou pak stanoveny korespondence. Některé dvojice, které na základě podobnosti označíme za odpovídající, však ve skutečnosti odpovídat nemusí. Proto je nutné tyto předběžné korespondence dále zpracovat a vyloučit ty špatné. Postup bude vysvětlen podrobně v části 2.5.2. Nyní podrobně popíšeme jednotlivé kroky od nalezení významných bodů v obrazech až po stanovení předběžných korespondencí. 2

Pojem první a druhý obrázek vyjadřuje relativní pořadí těch dvou obrazů ve zdrojové videosekvenci. První obrázek je sejmutý dříve než druhý. Obecně nemusí jít ihned za sebou. V tomto případě nemusí být dodrženo pořadí, ale je nutné, aby se jednalo o snímky, které jsou ihned za sebou. Důvod je vysvětlen v části 2.2.2.

4


2.2.1. Nalezení významných bodů V každém obraze je nejprve nutné nalézt významné body. Jako významné body jsou voleny ty body, které mají tyto vlastnosti: • Existuje jich jen určité množství. • Jsou izolované – nenachází se v obraze hned vedle sebe. • Jsou v obraze dobře lokalizované a jsou invariantní vůči rotaci a malým změnám velikosti. Body, které tyto vlastnosti mají, jsou nalezeny například Harrisovým detektorem rohů. 2.2.1.1. Harrisův detektor rohů Harrisův detektor rohů [5,16] funguje na principu autokorelační funkce. Pro každý bod obrázku (x, y) lze vypočítat hodnotu autokorelační funkce, která porovnává výřez z obrázku se stejně velkým výřezem posunutým o ∆x, ∆y: X c(x, y; ∆x, ∆y) = w(u, v) [I(u, v) − I(u + ∆x, v + ∆y)]2 , (2.1) (u,v)∈W (x,y)

kde W (x, y) vyjadřuje porovnávaný výřez (okno) a w(u, v) jsou váhy pro jednotlivé body z výřezu. Výraz I(u, v) vyjadřuje intenzitu obrazu na souřadnicích u a v. Jako w(u, v) jsme zvolili normální rozdělení se střední hodnotou v (x, y) a směrodatnou odchylkou σ = 3. Velikost okna je 5 pixelů. Rovnici (2.1) upravíme následovně: Výraz pro intenzitu posunutého okna nahradíme Taylorovým rozvojem v okolí bodu (u, v): . I(u + ∆x, v + ∆y) = I(u, v) + Ix (u, v)∆x + Iy (u, v)∆y,

(2.2)

kde Ix a Iy jsou parciální derivace intenzitního obrazu, které vypočítáme podle vzorců Ix = I ∗ [1, 0, −1] a Iy = I ∗ [1, 0, −1]T ,

(2.3)

kde ∗ značí diskrétní konvoluci. Dosadíme linearizovanou funkci (2.2) do (2.1) a získáme X

c(x, y; ∆x, ∆y) =

w(u, v)

Ix (u, v) Iy (u, v)

(u,v)∈W (x,y)

=

∆x ∆y

Q(x, y)

5

∆x ∆y

∆x ∆y

2

,

(2.4)

2. Teoretický rozbor úlohy P P kde ( pro přehlednost budeme psát (u,v)∈W (x,y) w(u, v) jako W ) P 2 P I (u, v ) I (u, v)I (u, v) x y x W W P 2 Q(x, y) = P . W Ix (u, v)Iy (u, v) W Iy (u, v )

(2.5)

Podle (2.4) jsme tedy autokorelační funkci aproximovali funkcí kvadratickou. Vlastní čísla matice Q(x, y) nám prozradí, jaký průběh má funkce c(x, y). Pokud budou velká, je funkce c(x, y) strmá a tím pádem se zde nachází roh. Přesněji, podle [16] je zavedena funkce H(x, y), tzv. „cornerness functionÿ, neboli funkce vyjadřující míru rohovitosti. Pokud definujeme hodnoty λ1 a λ2 jako vlastní čísla matice Q(x, y), můžeme poté zapsat funkci H(x, y) takto: H(x, y) = λ1 λ2 − 0,04(λ1 + λ2 )2 .

(2.6)

Funkci (2.6) spočítáme pro každý bod v obraze a jako rohy označíme body (i, j) takové, kde funkce H(i, j) nabývá lokálního maxima. Lokální maximum je v tomto případě definováno tak, že hodnota H(i, j) je větší než jakákoliv hodnota H(x, y) v okolí bodu (i, j). Jako okolí jsme zvolili okno o velikosti 5x5 pixelů s bodem (i, j) uprostřed. Můžeme také brát do dalšího zpracování jen rohy, jejichž hodnota cornerness funkce je vyšší než určitý práh. V naší práci jsme zvolili práh H ≥ 1000.

2.2.2. Stanovení korespondencí pro dva obrazy V tuto chvíli máme nalezeny významné body (dále jen rohy) ve dvou obrazech. Lze předpokládat, že rohy, které korespondují, budou mít i korespondující okolí. Proto u každého rohu vybereme okolí (11x11) s rohem uprostřed. Každý tento obrázek pak porovnáme se všemi obrázky ve druhém obraze. Metoda, kterou jsme použili je normalizovaná vzájemná korelace (NCC). Její výhoda je v tom, že je invariantní vůči změnám osvětlení mezi porovnávanými obrazy. Další možnosti jsou součet umocněných rozdílů (SSD) nebo součet rozdílů v absolutních hodnotách (SAD). Nyní můžeme využít znalosti toho, že snímky, pro které hledáme korespondence, jsou vybrány z videosekvence, takže se obraz moc neliší. Dá se tedy říci, že pokud k rohu v prvním obrázku existuje korespondující roh ve druhém obrázku, tak že nebude v obraze moc daleko. Maximální vzálenost mezi rohy pro snímky, které jsou v sekvenci ihned za sebou, jsme experimentálně stanovili na 15 pixelů. 2.2.2.1. Normalizovaná vzájemná korelace (NCC) Normalizovaná vzájemná korelace nebo také lineární korelační koeficient (r) vyjadřuje to, jak jsou sady hodnot xi a yi lineárně závislé. Platí, že r ∈< −1; 1 >. r = 1 pokud je xi lineární funkcí yi , r = −1 pokud je xi lineární funkcí −yi . Čím blíže je r k jedničce, tím jsou si hodnoty podobnější a to nás zajímá. Vstupní hodnoty xi a yi získáme tak, že vezmeme 11x11 bodů z okolí rohu a přeskupíme je do vektoru x = [x1 . . . x121 ]T . Podobně převedeme body ze druhého obrázku do vektoru y.

6

2. Teoretický rozbor úlohy Výpočet koeficientu r je provedeme tímto způsobem: 1. Posuneme čísla xi a yi tak, aby vektory x a y měly nulové střední hodnoty: xi = xi − x, i = 1 . . . 121, yi = yi − y, i = 1 . . . 121. 2. Vydělíme čísla xi a yi tak, aby vektory x a y měly jednotkové rozptyly: xi xi = p , i = 1 . . . 121, x2 yi yi = q , i = 1 . . . 121. y2 3. Z takto normalizovaných hodnot vypočteme koeficient r následovně: 121

1 X r =x?y = xi y i , 121 i=1 kde ? značí násobení vektorů po prvcích. Koeficient r nám tedy říká, jak jsou si dva rohy (se svým okolím) podobné. Pokud zanedbáme hodnoty r menší než nula, můžeme přibližně konstatovat, že r udává pravděpodobnost s jakou je na našich dvou výřezech stejný bod. Nyní popíšeme postup, jak prověříme všechny možné dvojice rohů a jak vybereme ty nejlepší. 2.2.2.2. Výpočet podobnosti pro všechny rohy Jak bylo řečeno dřive, porovnáváme vždy roh v prvním obraze se všemi rohy ve druhém obraze. Pro každou takovou dvojici vypočítáme korelační koeficient r(i, j). Pokud jsou rohy z prvního a druhého obrazu od sebe příliš daleko, nemusíme r počítat a nastavíme jej na nějakou nízkou hodnotu, např. −10. Pro roh i v prvním obraze tedy máme řádkový vektor ri = [r(i, 1) . . . r(i, N2 )], kde N2 je počet rohů ve druhém obraze. Pokud tyto řádkové vektory poskládáme do matice r = [rT1 . . . rTN1 ]T , máme všechny koeficienty v jedné matici, jejíž počet řádků odpovídá počtu rohů v obraze prvním a počet sloupců odpovídá počtu rohů v obraze druhém. Sobě odpovídající body budeme hledat na principu vzájemné náklonnosti. Postup, který zopakujeme pro každý roh v prvním obraze, je následující: Vybereme roh v prvním obraze, řekněme, že má index i. Tomuto rohu odpovídá řádek matice r, vektor ri . Tento vektor říká, jak je roh i podobný každému rohu ve druhém obrázku. Ze druhého obrázku vybereme ten roh, kterému je roh i nejpodobnější tak, že z vektoru ri vybereme prvek s nejvyšší hodnotou, řekněme j. Platí tedy j = arg max ri (k). k∈<1,N2 >

7

2. Teoretický rozbor úlohy Nyní jsme tedy pro roh i v prvním obraze určili roh ve druhém obraze j, který se k němu nejvíce hodí. Označme si tyto indexy rohů jako iA a jA . Nyní zopakujeme předchozí postup s tím rozdílem, že budeme vycházet ze druhého obrázku, kde zvolíme roh jA a k němu budeme hledat nejlepší shodu v prvním obraze. Z matice r tedy vybereme sloupec odpovídající bodu jA a v něm hledáme řádek s největším korelačním koeficientem r(i, jA ): i = arg max r(k, jA ). k∈<1,N1 >

Pro roh ze druhého obrazu jA jsme nyní určili roh v prvním obraze i = iB , který se k němu nejvíce hodí. Podle principu vzájemné náklonnosti musí platit iA = iB , abychom tyto dva rohy mohli považovat za sobě odpovídající. Jinak řečeno, pokud si roh i vybere ve druhém obraze nějaký roh j, musí si j v prvním obraze vybrat roh i, abychom mohli prohlásit, že spolu korespondují. Pokud iA 6= iB , bod i nemá korespondující roh ve druhém obraze. Z korespondencí, které takto získáme, vybereme do dalšího zpracování jen ty, které mají korelační koeficient r ≥ 0,8. Ani to však nezaručí, že jsou všechny takto vybrané korespondence správně ohodnoceny a že body si ve skutečnosti opravdu odpovídají. Tyto špatné korespondence je možné částečně později odhalit, ale nikdy není zaručeno, že odstraníme všechny.

2.3. Model kamery Model kamery představuje zobrazení bodů z 3D prostoru do roviny obrázku. V této sekci popíšeme model kamery, který jsme v této práci použili. Jedná se o obecný model dírkové kamery s centrální projekcí, který je podrobně popsán v [6].

2.3.1. Vnější parametry Vnější parametry kamery představují transformaci bodu ze souřadného systému světa do souřadného systému kamery. Musíme nějak vyjádřit to, že body v prostoru obvykle měříme v jiném souřadném systému než je souřadný systém kamery. Situaci znázorňuje obrázek 2.2. Transformace je představována rotační maticí R ( RT R = I ) a translačním vektorem t. Jestliže Xw = [xw , yw , zw ]T je bod v souřadné soustavě světa, tak jej můžeme transformovat do souřadné soustavy kamery podle vzorce Xc = RXw + t.

(2.7)

Pokud vektor Xw rozšíříme na homogenní čtyřvektor, můžeme rovnici (2.7) napsat elegantněji jako Xw . (2.8) Xc = R t 1 Parametry R a t budeme nazývat vnějšími parametry kamery.

8


Obrázek 2.2.: Obrázek znázorňuje propojení souřadných soustav světa a kamery.

2.3.2. Vnitřní parametry 2.3.2.1. Normalizované obrazové souřadnice Dírková kamera promítá body z 3D prostoru do roviny obrazu podle obrázku 2.3. Vytvoříme polopřímku ze středu kamery C do bodu Xc = [xc , yc , zc ]T . V místě, kde tato polopřímka protne rovinu obrazu, vznikne bod xn = [xn , yn ]T , neboli normalizovaný obrazový bod. Podle věty o podobnosti trojúhelníků můžeme určit souřadnice

Obrázek 2.3.: Tento obrázek vyjadřuje promítnutí bodu v prostoru do roviny obrazu.

normalizovaného bodu v obraze: xc f zc yc = f. zc

xn = yn

(2.9)

Pro normalizované souřadnice platí f = 1. Rovnice (2.9) pak můžeme napsat jako     xn 1 0 0 α  y n  =  0 1 0  Xc . (2.10) 1 0 0 1

9

2. Teoretický rozbor úlohy 2.3.2.2. Zkreslení kamery V reálných kamerách dochází při průchodu paprsků skrz čočky k různým zkreslením, které musíme zachytit, pokud chceme, aby model kamery odpovídal skutečnosti. Model zkreslení, který jsme použili, je zvolen podle [3], kde je také velice podrobně vysvětlen. Korekce zkreslení vyjádříme jako funkci normalizovaných souřadnic. Souřadnice po korekci označíme jako xd = [xd , yd ]T : xd = f (xn ).

(2.11)

Funkce (2.11) je obecně nelineární a její složitost závisí na tom, jak složitý model kamery používáme. 2.3.2.3. Kalibrační matice

Obrázek 2.4.: Obrázek ilustrující projekci souřadnic po upravení zkreslení do souřadnic v ploše obrazu.

Kalibrační matice vyjadřuje vztah (viz. obr. 2.4) mezi souřadnicemi v obrázku xp = [x, y]T a opravenými normalizovanými souřadnicemi xd :      x fx s x 0 xd  y  =  0 f y y 0   y d  = K xd . (2.12) 1 1 0 0 1 1 Kalibrační matice K obsahuje informace o ohniskové vzdálenosti pro každou osu (fx , fy ), pro případ, že pixely na snímacím čipu nejsou čtvercové, y0 a x0 určují souřadnice bodu, kde osa zc prochází obrazovou rovinou. Parametr s je nenulový v případě, kdy osy xp a yp v obraze na sebe nejsou kolmé. Podrobnosti a detailní popis lze nalézt v [6]. Souřadný systém bodů v obraze xp je definován tak, že bod [0, 0]T je vlevo nahoře, souřadnice x roste vpravo a souřadnice y roste dolů. Pro obraz s rozlišením 640x480 pixelů má tedy pravý horní roh souřadnice [639, 0]T , levý dolní [0, 479]T a pravý dolní [639, 479]T .

10


2.3.3. Projekční matice kamery V dalších odvozeních potřebujeme použít pouze lineární model kamery. Můžeme proto v tichosti přeskočit výpočet zkreslení a do odvození a maticových výpočtů jej nepsat. Ve všech výpočtech jej však použijeme. Projekce bodů z prostoru světa na bod v obraze pak můžeme psát jako   x Xw X w =P , (2.13) α y  = K R t 1 1 1 kde P je matice kamery. V tomto případě je matice P obecná matice s hodností 3, která promítá body z prostoru do obrazu.

2.3.4. Kalibrovaná kamera Pokud u kamery známe vnitřní parametry a parametry zkreslení, říkáme, že kamera je zkalibrovaná. Práce se zkalibrovanou kamerou přináší několik velkých výhod při rekonstrukci scény, které budou uvedeny v části 2.4.2. Podrobně je situace popsána v [6]. Pokud máme souřadnice bodu v obraze, můžeme vynásobit rovnici (2.12) zleva maticí K−1 a získat tak vztah pro xd :     xd x α  yd  = K−1  y  . (2.14) 1 1 Nyní můžeme použít známé parametry zkreslení a podle inverzní funkce (2.11), f , můžeme vypočítat normalizované obrazové souřadnice: −1

xn = f −1 (xd ).

(2.15)

Pro normalizované souřadnice bodu v obraze platí projekční rovnice kamery podobná (2.13), která se ale liší tím, že matice K je jednotková a v tomto případě je veškeré zkreslení již zahrnuto:   xn Xw X w =P . (2.16) α  yn  = R t 1 1 1 Je vidět, že v tomto případě má matice P speciální tvar: skládá se z rotační matice R a vektoru t. Jedná se tedy jen o otočení a posunutí. Kalibrační toolbox [3] obsahuje funkci normalize, která ze zadaných souřadnic v obraze a zadaných parametrů matice K a zkreslení vypočítá normalizované souřadnice.

11


2.3.5. Stanovení parametrů – kalibrace Parametry, které jsou v předchozích odstavcích popsané je třeba zjistit pomocí kalibrace. Ke kalibraci jsme použili kalibrační toolbox [3]. Postup, který toolbox používá, je tento: 1. Vstupem je několik obrázků, na kterých je vyobrazen kalibrační obrazec (šachovnice) o známých rozměrech. 2. V každém obraze je nutné označit rohy šachovnice. 3. Je nutné zvolit, jak složitý model požadujeme, zda se má odhadovat i parametr s atp. 4. Kalibrační matice K, parametry zkreslení a vnější parametry Ri a ti pro každý obraz jsou pak odhadováný nelineárním optimalizačním postupem. Funkce kalibračního toolboxu [3] je založena hlavně na díle [17]. Známé parametry jsou souřadnice bodů kalibračního obrazce v prostoru a v obraze. Hledané parametry jsou vnitřní parametry kamery, parametry zkreslení a vnější parametry kamery. Tyto všechny jsou optimalizovány najednou. Nejprve proběhne inicializace parametrů a následně probíhá optimalizace. Tato optimalizace je provedena pomocí gradientní metody a hledá minimum vzdálenostní funkce XX ||mij − m ˆ ij ||2 , i

j

kde i vyjadřuje bod v obraze j, mij jsou souřadnice změřeného i-tého bodu v obraze j am ˆ ij je projekce bodu kalibračního obrazce z prostoru do obrazu pomocí hledaných parametrů. Konkrétní hodnoty kalibrace a výsledné parametry pro námi použitou kameru jsou uvedeny později v příslušné kapitole.

2.4. Epipolární geometrie Epipolární geometrie vyjadřuje geometrický vztah mezi dvěma pohledy. Pohledem je myšlena kamera a obrázek scény sejmutý touto kamerou. Epipolární geometrie určuje relativní pozice dvou kamer nezávisle na scéně. Nezáleží na tom, zda jsou obrázky sejmuty ve stejný okamžik dvěmi různými kamerami, nebo zda se jedná o jedinou kameru a obrázky jsou sejmuty po sobě v čase.3 Podrobné vysvětlení je k nalezení v [6]. Nyní se stále jedná o obecné, nekalibrované kamery. Epipolární geometrie je znázorněna na obrázku 2.5. Jsou zde zobrazeny dvě kamery se středy C a C0 a bod v prostoru X. Tyto tři body tvoří v prostoru rovinu. Bod x je průmětem bodu v prostoru na obraz první kamery, podobně bod x0 je 3

Důležité ale je, že se scéna nesmí mezi jednotlivými snímky změnit.

12


X

l’

l x

x’ e

e’

C’

C

Obrázek 2.5.: Schéma, které zobrazuje princip epipolární geometrie. Středy kamer a bod v prostoru vytvářejí rovinu. Bod ve druhém obrázku, který odpovídá bodu v prvním obraze se musí nacházet na tzv. epipoláře.

průmět do druhé kamery. Úsečka spojující středy kamer vytváří v rovinách obrazu body e a e0 , tzv. epipóly. Přímka, která je v rovině obrazu a prochází body x a e, resp. x0 a e0 se nazývá epipolára.

2.4.1. Fundamentální matice Důležitou vlastností epipolární geometrie je to, že pokud máme průmět bodu X do obrazu jedné kamery, známe epipoláru ve druhém obraze a pouze na ní může ležet bod x0 . Tuto vlastnost shrnuje rovnice (2.17): T

x0 Fx = 0,

(2.17)

kde F je tzv. fundamentální matice. Výraz Fx vyjadřuje přímku l0 a protože bod x0 na ní leží, platí x0 T l0 = 0. Fundamentální matice F musí mít vždy hodnost 2, protože představuje zobrazení z dvourozměrného do jednorozměrného projektivního prostoru. 2.4.1.1. Nejednoznačnost určení fundamentální matice Fundamentální matice v sobě zapouzdřuje informace o relativní poloze kamer P a P0 a přitom je podle rovnice (2.17) svázána pouze s body x a x0 . Tento vztah je vyjádřen pomocí projektivní geometrie, resp. jde jen o průsečíky přímek a rovin v prostoru, které jsou zachovány přes jakoukoliv projektivní transformaci. ˆ = Hx a x ˆ 0 = H0 x0 , Pokud změníme body v obraze 2D projektivní transformací x pak získáme jinou fundamentální matici, která odpovídá těmto bodům: ˆx ˆ 0T H0−T FH−1 x ˆ=0=x ˆ 0T F ˆ. x

13

2. Teoretický rozbor úlohy Podobně, pokud x a x0 jsou korespondující body v obrazech, které jsou projekcí bodu X v prostoru přes kamery P a P0 , můžeme zvolit 3D homografii H, která způsobí: x = PX = (PH)(H−1 X),

x0 = P0 X = (P0 H)(H−1 X).

(2.18)

Z této rovnice vyplývá, že body x a x0 jsou korespondující body i pro bod H−1 X z prostoru promítnutý kamerami PH a P0 H. Tato nejednoznačnost, tedy určení až na projektivní transformaci, je podle [6] to nejhorší, co můžeme získat z obecných nekalibrovaných kamer.

2.4.2. Esenciální matice V případě, že máme kalibrované kamery, můžeme podle postupu v části 2.3.4 získat z korespondujících bodů x a x0 normalizované souřadnice xn a x0n . Pro tyto body platí podobné epipolární omezení jako (2.17): x0T n Exn = 0,

(2.19)

kde matici E nazveme esenciální maticí. Pro esenciální matici platí stejné vlastnosti jako pro fundamentální a má další vlastnost navíc: má dvě stejná singulární čísla a třetí singulární číslo je nula. Výhoda použití matice E je ta, že používáme normalizované souřadnice bodů v obrazech a tím se zmenší nejednoznačnost projekce bodů, kterou ukazuje rovnice (2.18). Jelikož kalibrační matice K je u kamer známá, musí se shodovat u kamer P a (PH−1 ). Podle [6] je možné za H zvolit libovolnou stejnolehlost. Matice kamery P je K [R|t]. Pokud zvolíme Rh t H= , 0T λ můžeme napsat ˆ t0 , t0 = K R PH−1 = K RR−1 h kde t0 je translační vektor, který není v tomto okamžiku zajímavý. Je vidět, že při násobení matice kamery maticí, která představuje stejnolehlost ve 3D, zůstane zachována matice vnitřních parametrů K. Kamery, které jsou zapouzdřené v esenciální matici a tím pádem i souřadnice bodů v prostoru, je možné rekonstruovat až na neznámou stejnolehlost. Tento případ si můžeme představit tak, že získáme stejný obrázek, když budeme fotit malý objekt z blízka, jako když budeme fotit velký objekt z dálky. Podle [6] je tato nejednoznačnost to nejhorší, co můžeme při použití kalibrovaných kamer získat. Z tohoto důvodu budeme dále v této práci vždy používat normalizované souřadnice bodů, které nebudeme značit speciálním indexem tak, jak tomu bylo doposud. Matice kamer budeme uvažovat ve tvaru podle rovnice (2.16).

14


2.5. Výpočet esenciální matice Esenciální matice svazuje normalizované souřadnice rohů ze dvou obrazů podle rovnice (2.19). Při znalosti několika korespondujících bodů je možno vypočítat esenciální matici pouze z rovnice (2.19), do které dosadíme známé body. Problém je v tom, že esenciální matice musí splňovat ještě další omezení, která je nutné při výpočtu zajistit. Algoritmy pro výpočet esenciální matice jsou uvedeny v [6]. Všechny algoritmy mají za základ rovnici (2.19). Tuto rovnici můžeme přepsat tak, že neznámé proměnné v matici E naskládáme do vektoru e a rovnici (2.19) přepíšeme do tvaru aT e = 0, kde vektor a obsahuje koeficienty vytvořené ze souřadnic x a x0 . Ve vektoru e je 8 neznámých (až na násobek), je proto potřeba 8 korespondujících bodů pro výpočet. Z vektorů aT1 . . . aT8 vytvoříme matici A:   aT1  ..  (2.20)  .  e = Ae = 0. T a8 Z této rovnice vypočítáme vektor e jako nulový prostor matice A. Podmínka, že matice E je singulární není v tomto výsledku zaručena, proto je nutné matici ještě upravit tak, aby podmínka platila (podrobnosti jsou k nalezení v [6]). Tento algoritmus se nazývá základním 8-bodovým algoritmem. Znalost toho, že matice E musí být singulární, je možné použít již v algoritmu. V tom případě stačí 7 bodů a tato podmínka pro výpočet. Pokud počítáme esenciální matici, známe ještě omezení, že SVD rozklad musí mít dvě stejná singulární čísla a třetí musí být rovno nule. Algoritmus, který toto zohledňuje, může vypočítat esenciální matici z pouhých pěti korespondujících bodů. Takový algoritmus jsme v této práci použili.

2.5.1. 5-bodový algoritmus Algoritmus, který jsme použili je naimplementován podle [13,14]. Vstupem tohoto algoritmu jsou normalizované souřadnice 5 dvojic korespondujících bodů a výstupem jsou všechny (max. 10) esenciální matice, které těmto korespondencím vyhovují. Nyní uvedeme hrubý postup, jak algoritmus funguje: 1. Z 5 korespondencí vytvoříme matici A podle rovnice (2.20). Tato matice bude mít hodnost 5, takže nulový prostor bude mít hodnost 4. Matice E se pak dá vyjádřit jako E = xE1 + yE2 + zE3 + wE4 , (2.21) kde Ei jsou vektory nulového prostoru matice A.

15

2. Teoretický rozbor úlohy 2. Víme, že matice E je určena až na násobek, zvolíme w = 1 a získáme matici E parametrizovanou třemi proměnnými. 3. Matici E podle (2.21) dosadíme do podmínky det(E) = 0 (podmínka že hodnost esenciální matice je 2). 4. Podmínku na dvě stejná singulární čísla a třetí nulové se dá podle [13] zapsat jako 2EET E − trace(EET )E = 0. Do této rovnice opět dosadíme podle (2.21) a spolu s předchozí podmínkou získáme deset rovnic pro 3 neznámé. 5. Vytvoříme vektor monómů, které se v těchto rovnicích vyskytují a tyto rovnice přepíšeme jako násobení monómů. 6. Tuto soustavu vyřešíme pomocí Gröbnerovy báze. Rovnice, které řešíme, jsou třetího stupně pro všechny proměnné, můžeme tedy dostat až deset možných reálných řešení. Všechna tato řešení je nutné následně otestovat na ostatních bodech. K tomu s úspěchem použijeme metodu RANSAC, která je vysvětlena v následující části.

2.5.2. RANSAC RANSAC (RAndom SAmple Consensus) je robustní algoritmus, který hledá model odpovídající datům. Výhoda tohoto algoritmu je ta, že se dokáže vypořádat s velkým procentem chybných měření v datech. Podrobný popis je k dispozici v [6]. Vstupní data jsou v našem případě nalezené korespondence rohů ve dvou obrazech. Bylo řečeno, že rohy, které jsme prohlásili za korespondující, nemusí ve skutečnosti korespondovat. Jsou to tedy chybná měření. Body, které nekorespondují s modelem nazýváme outliers, body, které korespondují, nazýváme inliers. Model, který hledáme, je epipolární geometrie, resp. esenciální matice. Funkce RANSACu je následující: v každém cyklu se náhodně vybere z dat tolik vzorků, kolik je potřeba k vytvoření modelu. Tento model se pak na všech datech otestuje podle zvoleného kritéria. Pokud tento model vyhovuje datům lépe než doposud nejlepší nalezený, tak si jej poznačíme jako nejlepší nalezený. Předpokladem této myšlenky je to, že pokud vytvoříme model ze špatného vzorku, tak bude mít malou podporu mezi ostatními daty. Tento postup je schematicky zobrazen v algoritmu 2.1. V našem případě je možné v jednom cyklu získat ze vzorků více než jeden model, jak je vysvětleno v části 2.5.1. V takovém případě otestujeme v jednom kroku více modelů a z nich vybereme ten nejlepší. Počet opakování cyklu je možné zvolit libovolně nebo podle vzorce, který vyjadřuje, s jakou pravděpodobností alespoň jednou sestavíme model ze samých inliers. Pokud in udává procento inliers v datech, s udává počet vzorků pro sestavení modelu a k je počet cyklů algoritmu, tak

16

2. Teoretický rozbor úlohy • výraz ins udává pravděpodobnost toho, že všechny vybrané vzorky do modelu jsou inliers, • výraz (1 − ins ) udává pravděpodobnost, že alespoň jeden vzorek je outlier, • výraz (1 − ins )k udává pravděpodobnost, že v k cyklech za sebou nesestavím model, který by byl ze samých inliers. Tuto pravděpodobnost chceme mít pod kontrolou. Zvolíme tedy p jako pravděpodobnost, že alespoň v k cyklech sestavím model ze samých inliers. Platí poté (1 − ins )k ≤ 1 − p. Z tohoto výrazu pak můžeme odvodit vzorec pro minimální počet cyklů k, abychom s pravděpodobností p alespoň jednou vybrali vzorky, které budou správné: k ≥

log(1 − p) . log(1 − ins )

(2.22)

Pravděpodobnost p volíme obyčejně rovno 0,99. . . V praktických úlohách většinou neznáme procento správných vzorků in. V tom případě jej můžeme odhadovat při ověřování modelu na datech. Pokud model vyhovuje a označíme jej jako zatím nejlepší, poznačíme také počet bodů, kterým vyhovuje a in vypočteme jako jejich procento ze všech bodů. Inicializace: M ∗ ← null //nejlepší model supp∗ ← −∞ //podpora nejlepšího modelu k←∞ Cyklus: 1: while počet cyklů ≤ k do 2: Vyber s vzorků a vytvoř model M 3: Spočítej podporu supp modelu M 4: if supp > supp∗ then 5: M∗ ← M 6: supp∗ ← supp 7: spočítej in jako procento inliers podle supp 8: spočítej nové k podle in podle vzorce (2.22) 9: end if 10: end while Algoritmus 2.1: RANSAC.

17


2.6. Zpracování esenciální matice V části 2.4 jsme poznamenali, že esenciální matice v sobě obsahuje informace o relativní poloze dvou kamer a bodů v prostoru. Tato geometrie je u esenciální matice určena až na neznámou stejnolehlost.

2.6.1. Stanovení matic kamer Jelikož není možné stanovit matice kamer absolutně, zavádí se tzv. kanonický tvar matic, kde (2.23) P = [ I 0 ] a P0 = [ R t ]. Podle [6] je možné vypočítat esenciální matici ze zadaných matic kamer ve tvaru (2.23) podle vzorce E = [t]× R, kde [t]× je antisymetrická matice vytvořena z vektoru t. Pokud t = [t1 , t2 , t3 ]T , pak tuto matici získáme následovně:   0 −t3 t2 0 −t1  . [t]× =  t3 −t2 t1 0 Opačným postupem můžeme z esenciální matice získat matice kamer v kanonickém tvaru. Podle [6] je třeba rozložit matici E na součin antisymetrické a rotační matice. Pokud SVD rozklad matice E je U diag(1, 1, 0) VT , tak jsou jen dva možné rozklady matice E = SR: S = UZUT , R = UWVT nebo R = UWT VT , (2.24) kde



 0 1 0 Z =  −1 0 0  0 0 0



 0 −1 0 a W =  1 0 0 . 0 0 1

Podrobné odvození a důkaz je uveden v [6]. Upřesnění, které je uvedeno v [10] ještě dodává, že SVD rozklad musíme zvolit tak, že det(U) > 0 a det(V) > 0. Jinak totiž bude matice R v matici kamery P0 tzv. antirotační, resp. bude platit, že det(R) = −1. Z výše uvedených vzorců plyne, že [t]× = S. Platí St = 0 a protože S lze rozložit podle (2.24), tak vektor t je u3 , třetí sloupec matice U. Znaménko E a následně i znaménka S a t není možné určit a proto existují čtyři možné matice kamery P0 , které odpovídají dané esenciální matici E: P01 = [ UWVT +u3 ], P03 = [ UWVT −u3 ],

P02 = [ UWT VT +u3 ], P04 = [ UWT VT −u3 ].

(2.25)

Postup jak z těchto čtyř matic vybrat tu správnou je jenoduchý. Podle geometrické interpretace těchto čtyř řešení, které je uvedeno v [6] platí, že rekostruovaný bod do

18

2. Teoretický rozbor úlohy prostoru bude pouze v jednom případě ležet před oběma kamerami. Podle tohoto principu vybereme tu správnou kameru P0 . Kamera P je vždy stejná. Tímto způsobem jsme z esenciální matice získali matice kamer P a P0 .

2.6.2. Nalezení 3D souřadnic bodů v obrazech Pro promítnutí bodu X z prostoru do normalizovaných souřadnic v obrazech platí tyto rovnice: x = PX a x0 = P0 X. (2.26) Pokud známe matice kamer a normalizované souřadnice v obou obrazech, můžeme rovnice (2.26) upravit do tvaru AX = 0. Vektor X pak vypočítáme jako nulový vektor matice A:   xp3 − p1  yp3 − p2    0 0 (2.27)  x p3 − p01  X = AX = 0, y 0 p03 − p02 kde pi je i–tý řádek matice P a x = [x, y]T . Podmínkou v tomto případě je, že matice A má hodnost 3. Normalizované souřadnice bodů musí tedy přesně splňovat podmínku (2.19). V reálném případě tuto podmínku splňují jen body, které byly použity k výpočtu té dané esenciální matice. Ostatní body obecně tuto podmínku nesplňují. Geometricky si to můžeme představit podle obrázku 2.6 tak, že paprsky, které vycházejí ze středů kamer C a C0 do bodů x a x0 se obecně ve 3D nemusí protínat.

X

x’ d’ ˆ’ x

xˆ d x

C’

C

Obrázek 2.6.: Normalizované souřadnice obecně nesplňují epipolární podmínku (2.19). Projevuje se to tím, že se paprsky ze středů kamer do bodů x a x0 v prostoru âx ˆ 0 , které omezení splňují a jsou neprotnou. Musíme proto nalézt body x 0 v nějakém smyslu nejblíže k x a x .

19

2. Teoretický rozbor úlohy âx ˆ 0 v obrázku 2.6 je podrobně popsán v [6]. Kritérium, Postup, jak nalézt body x které minimalizujeme, je zvoleno jako součet Euklidovských vzdáleností mezi body ˆ v obou obrazech: xax ˆ ) + d(x0 , x ˆ 0 ). C(x, x0 ) = d(x, x

(2.28)

Problém nalezení minima kritéria (2.28) převedeme na jinou úlohu podle [6]. Epipoláru v prvním obraze vyjádříme jako funkci úhlu od osy x, l = f (θ). Nyní, pokud v prvním obraze máme zvolenu nějakou epipoláru, přes esenciální matici se nám promítne do epipoláry ve druhém obraze, l0 = f 0 (θ, E). Body, které minimizují kritérium (2.28) a zároveň splňují epipolární omezení (2.19) musí v obrazech ležet na epipolárách. Vzdálenosti bodů d(∗, ∗) se pak změní na vzdálenosti bodů od přímky. Kritérium (2.28) potom vyjádříme jako funkci úhlu C = h(θ). Tato funkce je podle [6] polynom šestého stupně a jeho minimum je snadné získat položením derivace rovno nule. Algoritmus, který toto provádí je přesně podrobně popsán v literatuře. âx ˆ 0 takové, které splňují epipolární V tomto okamžiku máme vypočítané body x podmínku a jsou nejblíže bodům změřeným, x a x0 . Tyto nové souřadnice použijeme pro výpočet souřadnic bodu X v prostoru. Tento výpočet provedeme podle vzorce (2.27).

2.7. Rekonstrukce 1:1 Nyní máme vypočítané dvě matice kamer a souřadnice bodů ve 3D. Jak jsme řekli dříve, tyto údaje jsou určené až na neznámou stejnolehlost    H= 

sRH 0 0 0

tH  .  1

Tato stejnolehlost upraví souřadnice bodů X a matice kamer takto: x = PX = (PH−1 )(HX) a x0 = P0 X = (P0 H−1 )(HX).

(2.29)

Úkolem je nyní zjistit parametry této stejnolehlosti, kterou můžeme aplikovat také po krocích, jak bude ukázáno dále.

2.7.1. Zvětšení Vzdálenost mezi kamerami, které jsou zvolené podle postupu v části 2.6.1 je podle [6] jednotková. Ze senzoru pohybu však známe pravou vzdálenost mezi kamerami. Zvětšení tedy bude s = distc /1, pokud jako distc označíme správnou vzdálenost mezi kamerami. Pokud X je zrekonstruovaný bod v prostoru, tak Xs = sX bude bod v prostoru správně zvětšený. Kamera P zůstane stejná, jelikož její střed je na [0, 0, 0]T a kamera P0 = [R|t] se posune o s: P0s = [R|st].

20


2.7.2. Rotace a posunutí Absolutní rotace RH a posunutí tH v prostoru není možné určit a ani pro nás není zajímavé. Postačí nám jen rotace a posunutí tak, abychom dostali druhou kameru, která odpovídá orientaci kamery na vozidle podle obr. 2.7.

zv C

zc

C

xc

tH

yc

RH

xc zc

yc zv

yv

0

xv

yv

xv Obrázek 2.7.: Orientace souřadných systémů kamery a vozidla. Obě souřadné soustavy jsou spojené s vozidlem. Po aplikaci stejnolehlosti budou rekonstruované body vyjádřeny v souřadné soustavě v.

Kalibrační toolbox [3] nabízí funkci pro výpočet vnějších parametrů kamery. Při známých vnitřních parametrech je možné z obrázku kalibračního obrazce spočítat vnější parametry kamery Rc , tc (viz. část 2.3.1, str. 8). Pokud tento obrazec umístíme na zem tak, aby souřadná osa x obrazce byla rovnoběžně s osou xv , získáme přesně rotaci, kterou požadujeme po druhé kameře (Rc ). Pro posunutí vyjádříme vektor tH = −RTc tc a vybereme pouze výšku nad obrazcem (z souřadnici). Translaci, kterou požadujeme po druhé kameře získáme transformací zpět jako t0c = −Rc [0, 0, zH ]T . Projekce druhé kamery je vyjádřena rovnicí (2.29). V tomto případě budeme uvažovat kamery již po aplikaci zvěšení, takže i v matici H bude parametr s = 1. Požadujeme   Rc

 (P0 H−1 ) =   0

0

t0c  .  0 1

(2.30)

0

Matici kamery P upravíme na čtvercovou přidáním řádku [0, 0, 0, 1]. Transformaci H pak získáme upravením předchozí rovnice (2.30): −1    Rc

 H=  0

0

t0c    0 1

  

P0

 . 

(2.31)

0 0 0 1

Transformaci H pak použijeme na kamery P a P0s a na body Xs podle rovnic (2.29) následovně: Pr = PH−1 , P0r = P0s H−1 , a Xr = HXs . (2.32)

21

2. Teoretický rozbor úlohy Tímto způsobem získáme body v prostoru odpovídající skutečnosti v měřítku 1:1 spolu s dvojicí kamer. Dále je budeme značit pro jednoduchost bez indexu r. Pokud bychom body v obrazech měřili přesně a nemuseli je podle esenciální matice upravovat tak, aby se paprsky v prostoru protly, měli bychom geometrii úlohy tímto vyřešenou. Bohužel měříme nepřesně a proto je nutné ještě tuto nepřesnost zachytit.

2.8. Nepřesnost lokalizace bodů v prostoru Doposud jsme předpokládali, že rohy v obrazech měříme přesně. Ve skutečnosti tomu tak není a do procesu jsme zavedli chybu hned na samém počátku. Je velice obtížné přesně tuto chybu lokalizovat a předejít jí. Budeme proto předpokládat jen omezený vliv.

2.8.1. Skutečná neurčitost Neurčitost modelujeme tak, že určení pixelových souřadnic bodu v obraze je náhodná veličina s normálním rozložením pravděpodobnosti se střední hodnotou µ a diagonální kovarianční maticí Σ. Tato nepřesnost má tedy vliv na to, kde bude v prostoru bod, odpovídajícím těmto projekcím v obraze, rekonstruován. Tento přístup je zobrazen také v [6]. Pro jednoduchost ukážeme postup na případě dvourozměrného prostoru, kde se bod promítá do kamer na přímky. Pokud je r1 souřadnice promítnutí bodu z prostoru do první kamery náhodná veličina se střední hodnotou r10 a rozptylem σ 2 , je pravděpodobnost r1 vyjádřena známým vzorcem: (r1 −r10 )2 1 e− 2σ2 . p(r1 |r10 , σ 2 ) = √ 2πσ

Podobně je vyjádřena pravděpodobnost promítnutí bodu do druhé kamery r2 . Pokud máme bod X v prostoru, můžeme vypočítat pomocí projekce matic kamer hodnoty r10 a r20 . Za předpokladu, že náhodné veličiny r1 a r2 jsou nezávislé, výraz pro pravděpodobnost hodnot r1 a r2 je p(r1 , r2 |X) = p(r1 |r10 , σ 2 )p(r2 |r20 , σ 2 ). Podle Bayesova vzorce můžeme nyní vyjádřit vztah pro pravděpodobnost polohy X za předpokladu změření hodnot r1 a r2 : p(X|r1 , r2 ) =

p(r1 , r2 |X)p(X) . p(r1 , r2 )

Za předpokladu toho, že apriorní rozložení pravděpodobnosti p(X) je rovnoměrné, můžeme předchozí rovnici upravit: p(X|r1 , r2 ) ∼ p(r1 , r2 |X) = p(r1 |r10 , σ 2 )p(r2 |r20 , σ 2 ).

(2.33)

Pravděpodobnost podle rovnice (2.33) neodpovídá normálnímu rozdělení. Tvar tohoto rozdělení pro umělý případ je zobrazen na obr. 2.8.

22


4 3.5 3 2.5

y

2 1.5 1 0.5 0 −0.5 −0.5

0

0.5

1

1.5

2

2.5

3

3.5

4

x

Obrázek 2.8.: Průběh rozložení pravděpodobnosti pro rekonstrukci bodu v ploše. Kamery jsou umístěný na souřadnicích [−1, 1]T a [1, −1]T . Rovina obrazu první kamery je osa y a rovina obrazu kamery druhé je osa x. V obou kamerách je bod měřen s normálním rozdělením ri ∼ N (0; 0,52 ). Střední hodnota bodu X je v ploše na souřadnicích [1, 1]T a pravděpodobnost výskytu je znázorněna vrstevnicemi. Z tohoto obrazu je jasně vidět, že rozdělení není normální.

2.8.2. Převedení neurčitosti do epipolární roviny V předchozí kapitole jsme uvedli, že bod v obraze je měřen s nepřesností aproximovanou normálním rozdělením. Toto rozdělení je dvourozměrné, ve směrech os x a y v obraze. Bod, který změříme na stínítku ale nemusí splňovat epipolární omezení podle obr. 2.6 str. 19. To spravíme tím, že body posuneme na nově vypočítané body âx ˆ0. x Neurčitost těchto bodů také změníme tak, že ji ze dvou rozměrů promítneme do jednoho rozměru na epipoláry. Body na stínítkách se tedy mohou pohybovat na âx ˆ 0 a s rozptylem σ 2 . (Pro přehlednost epipolárách, se střední hodnotou v bodech x budeme v dalším textu tyto body značit bez stříšky, jako x a x0 .) Vznikne tak situace, která vychází z ukázkového obrázku 2.8. Tato situace je zobrazena na obr. 2.9. Bod v prostoru X tedy budeme vždy předpokládat na epipolární rovině.

2.8.3. Výpočet neurčitosti bodu v prostoru Kovarianční matici Σ náhodného rozdělení bodu na stínítku jsme zvolili diagonální se stejnými hodnotami na diagonále (Σ = diag(σ 2 , σ 2 )). Pokud tedy nyní řekneme, že bod bude vždy na epipoláře a nejistota bude vyjádřena normálním rozdělením, rozptyl tohoto rozdělení můžeme zvolit z matice Σ jako σ 2 . Střední hodnota tohoto rozdělení bude odpovídat původnímu bodu x resp. x0 . Schematicky je tento stav

23


C

X

x e e’

x’

C’ Obrázek 2.9.: Rozložení pravděpodobnosti polohy bodu v prostoru je omezeno na epipolární rovinu. Epipolární rovina prochází body C, C0 a X a dále průměty e a e0 a x a x0 . Body x a x0 jsou na stínítku měřeny na epipoláře s normálním rozdělením pravděpodobnosti. Hustota pravděpodobnosti bodu v prostoru X je znázorněna vrstevnicemi.

zobrazen na obrázku 2.10. Nyní můžeme vyjádřit hustotu pravděpodobnosti bodu X podle vzorce (2.33): f (X) = k p(x|x0 , σ 2 )p(x0 |x00 , σ 2 ). Podle definice hustoty pravděpodobnosti náhodné veličiny musí platit, že ZZ ∞ f (X) = 1.

(2.34)

(2.35)

−∞

Z tohoto důvodu také vzorec (2.34) obsahuje neznámou konstantu k, jelikož výraz (2.33) ze kterého je tato hustota odvozena také není určen přesně. Pro každý bod X proto musíme vyjádřit pravděpodobnost podle vzorce (2.34) (k = 1) pro každou možnou polohu bodu v rovině. Tyto hodnoty poté sečteme a na základě tohoto součtu vypočítáme konstantu k v rovnici (2.34) tak, aby platila podmínka (2.35).

2.8.4. Pokus o aproximaci normálním rozdělením Pro zjednodušení situace jsme se pokusili nahradit rozdělení pravděpodobnosti podle obrázku 2.9 normálním rozdělením. Výsledek je zobrazen na obrázku 2.11. Je vidět, že v případě, kdy úhel mezi paprsky je malý, není vůbec možné tuto aproximaci použít, protože průběhy hustoty vůbec neodpovídají. Z tohoto důvodu nebudeme aproximaci používat vůbec a pro každý rekonstruovaný bod budeme počítat skutečnou hustotu.

24


X

x’ x x’0 x0 e

e’

C’

C

Obrázek 2.10.: Zobrazení modelu, který jsme použili pro zachycení nepřesnosti při měření bodů v obraze. Pro dvojici bodů na stínítkách je nejprve nalezena epipolární rovina. Neurčitost určení bodů na stínítku je modelována normálním rozdělením podél epipolár.

2.9. Rozhodnutí o překážkách To, jaké rozhodnutí o překážkách je nejlepší provádět a co a jakým způsobem o nich sdělovat řidiči, je velice složitá otázka. My jsme zvolili následující přístup: V okamžiku, kdy změříme (zrekonstruujeme) překážku tak blízko u vozidla, že bychom do ní při dalším couvání narazili, řekneme řidiči, že má zastavit. Přesněji řečeno, systém, který jsme vytvořili, rekonstruuje scénu vždy po určité ujeté vzdálenosti. Proto nezávisle na čase, další měření při přibližovaní se k překážce, získáme až po ujetí vzdálenosti ∆d. Proto je zásadní, abychom řidiči oznámili aby zastavil v tom okamžiku, kdy by ujetí další ∆d znamenalo náraz do překážky. Obecně ale chceme řidiče upozornit na překážku dříve. Proto v obraze při každé rekonstrukci také označíme body, které jsou v určité vzdálenosti od vozidla, v koridoru, ve kterém se vozidlo pohybuje. Provádíme tedy dvě rozhodnutí: • Rozhodujeme, zda bod tvoří překážku tak blízko, že musíme zastavit a • zda bod tvoří překážku na kterou musíme upozornit. Podrobnosti, jak jsou tato kritéria geometricky implementována, jsou v kapitole 2.9.1. Teoretický postup jak na základě bodu, jehož polohu známe s určitou pravděpodobností, rozhodneme, je uveden v části 2.9.2.

25

2. Teoretický rozbor úlohy 16

40

14

35 30

12

25

10

20 y

y

8 15

6 10 4

5

2

0

0

−5

−2 −2

0

2

4

6

8

10

12

14

−10 −2

16

−1

0

1 x

x

0.04

2

3

4

0.045 Gaussian approximated dist. Real distribution

0.035

Gaussian approximated dist. Real distribution

0.04 0.035

0.03

0.03 0.025 f(X)

f(X)

0.025 0.02

0.02 0.015 0.015 0.01

0.01

0.005 0

0.005

0

5

10

15

20 y

25

30

35

0 −10

40

0

10

20

30

40

y

Obrázek 2.11.: Porovnání skutečné hustoty pravděpodobnosti a její aproximace normálním rozdělením. V obrázcích nahoře je zobrazena skutečná hustota pravděpodobnosti na epipolární rovině (scéna je transformována tak, že epipolární rovina je v obraze rovina xy). V obrázcích dole je zobrazen řez pravděpodobností na přímce mezi středem druhé kamery a střední hodnotou bodu X v rovině (v horních obrázcích je tento řez naznačen modrou čárou). Střed první kamery je [0, 0]T , střed druhé kamery je na souřadnicích [0, 1]T . V obou případech σ 2 = 10−4 . Vlevo má bod souřadnice X = [10, 10]T , což tvoří úhel mezi paprsky přibližně 3◦ . Vpravo je bod na souřadnicích X = [1, 10]T , což dává úhel asi 0,6◦ .

2.9.1. Rozměry vozidla Na obrázku 2.7 na straně 21 jsme ukázali naši zvolenou souřadnou soustavu spojenou s vozidlem. V této soustavě máme rekonstruované body v prostoru s jejich neurčitostí (viz. kapitola 2.8) a dvě kamery. Druhá kamera má střed na souřadnicích [0, 0, zB ]T , jak je na obrázku 2.7 uvedeno. Nyní zvolíme model vozidla a jeho rozměry následovně: V této souřadné soustavě vyvoříme kvádr, který bude představovat vnější rozměry vozidla. Situace je znázorněna na obrázku 2.12. Vnější rozměry vozidla jsou dány hodnotami xA , xB , y0 a z0 . Tento kvádr představuje fyzické rozměry vozidla (1). Dále je na obrázku vyznačen kvádr (2), který je směrem vzad od vozidla rozšířen

26


zv CB

CA

1

2

3

xB

z0

y0 + warnd

0

y0

y0 + Δd

yv

xA

xv Obrázek 2.12.: Model vnějších rozměrů vozidla. Kvádr, který představuje fyzické hranice vozidla je parametrizován čtyřmi hodnotami xA , xB , y0 a z0 (1). V opačném směru kvádr teoreticky nekončí. Kvádr (2) vyznačuje hranice vozidla, která je v kladném směru osy y zvětšena o ∆d. Tento kvádr je použit k rozhodování o tom, zda řidiči říci, aby zastavil. Pokud zrekonsturuujeme bod v pásmu y0 + ∆d, příští rekonstrukce může být již do vozidla, což nesmíme dopustit. Pokud se nějaký bod bude nacházet v oblasti (3), řidič bude upozorněn na překážku a ta bude v obraze zvýrazněna.

o ∆d. Pokud se bude některý zrekonstruovaný bod nacházet uvnitř tohoto kvádru, bude řidiči signalizováno, aby zastavil. Při další rekonstrukci by totiž tento bod byl již ve vozidle. Pokud zrekonstruujeme některý bod uvnitř kvádru (3), zvýrazníme pro řidiče tento bod v obraze a upozorníme jej tím na to, že se v obraze nachází překážka. Vzdálenost warnd je možné nastavit libovolně, v našem případě jsme zvolili hodnotu dva metry. Model, který jsme takto zvolili, nepracuje s možností, že by vozidlo při couvání zatáčelo. Pro určení toho, zda má řidič zastavit, to nevadí. Běžné vozidlo má průměr otáčení cca 10 metrů a tak při vzdálenosti kamer ∆d = 10 cm pro jednu rekonstrukci je úhel otočení přibližně jeden stupeň, což lze zanedbat.

2.9.2. Rozhodovací kritérium Pokud bychom měli body v prostoru rekonstruovány bez nejistoty, bylo by rozhodovací kritérium velice jednoduché. Pouze bychom porovnali vzájemnou polohu bodu a kvádru a na základě toho bychom rozhodli o překážce. V našem případě ovšem máme body rekonstruované nepřesně, se známým rozložením pravděpodobnosti na epipolární rovině. Musíme proto při rozhodování využít statistický přístup.

27

2. Teoretický rozbor úlohy 2.9.2.1. Definice problému Problém můžeme definovat následovně. Pro jednoduchost budeme předpokládat jednorozměrné rozdělení pravděpodobnosti. Známe rozložení pravděpodobnosti f (x) bodu na ose x. Dále zvolíme, že vozidlo (kvádr (2) podle obrázku 2.12) bude zabírat zápornou osu x, x ≤ 0. Tato situace je znázorněna na obrázku 2.13. 0.14

0.12

0.1

f(x)

0.08

0.06

0.04

0.02

0 −10

−5

0

5

10

15

x

Obrázek 2.13.: Znázornění hustoty pravděpodobnosti bodu na ose x. Zelená plocha ukazuje pravděpodobnost, že se bod nachází na záporné poloose.

Pravděpodobnost, že je daná náhodná veličina X menší než x vyjadřuje distribuční funkce náhodné veličiny [7]: Z x p(X ≤ x) = F (x) = f (t)dt. −∞

Za podmínky, že známe hustotu f (x), můžeme vypočítat pravděpodobnost, s jakou se bod nachází na záporné poloose p(X ≤ 0), neboli pravděpodobnost, s jakou se bod nachází v oblasti „vozidlaÿ. Tento integrál je znázorněn na obrázku 2.13 jako zelená plocha. 2.9.2.2. Ztrátová funkce Nyní máme vypočítanou pravděpodobnost, s jakou se bod nachází v oblasti vozidla. Jedna z možností, které se nyní naskýtají je ta, že tuto pravděpodobnost sdělíme řidiči na displeji. Při každé rekonstrukci dostane řidič tuto informaci a bude muset pokaždé zvažovat, zda ještě bude couvat, nebo ne. Dá se předokládat, že se řidič bude chovat stále stejně a proto pokaždé zastaví, když pravděpodobnost překročí jím stanovenou mez. Z tohoto důvodu se zdá být rozumné, nechat rozhodnutí o tom, zda zastavit, na našem systému a po řidiči jen požadovat, aby zvolil pravděpodobnostní hranici.

28

2. Teoretický rozbor úlohy Tuto hranici musíme zvolit individuálně pomocí následujícího principu podle [7]: V tabulce 2.1 jsou zobrazeny čtyři možnosti pro naše rozhodnutí. V případě, že bod Tabulka 2.1.: Stavy, které mohou nastat pro různé skutečnosti a naše různá rozhodnutí.

provedené rozhodnutí nezastavíme zastavíme

skutečná poloha bodu bod nás neohrožuje bod nás ohrožuje správné rozhodnutí chyba 2. řádu – nabourání do překážky chyba 1. řádu – zby- správné rozhodnutí tečné zastavení vozu

ve skutečnosti neleží v oblasti (2) podle obrázku 2.12 a my rozhodneme, že leží (chyba 1. řádu), bude systém zbytečně plašit a řidič bude stále zastavovat. V případě, že bod ve skutečnosti vozidlu překáží a my rozhodneme, že ne (chyba 2. řádu), budou následky mnohem horší. Je proto na řidiči, aby tyto dvě možnosti nějak zvážil a poté nastavil práh pro rozhodování. Tento práh označíme jako threshold. Pro experimentální ověřování jsme zvolili hranici pravděpodobnosti 5%, tj. v případě, že pravděpodobnost toho, že se bod nachází v oblasti vozidla je větší než 5%, děláme rozhodnutí „zastavÿ. 2.9.2.3. Definice rozhodovací funkce V této části definujeme rozhodnutí pomocí matematické funkce. V předchozí části jsme ukázali, jak vypočítáme pravděpodobnost toho, že se bod i nachází u oblasti (2) podle obr. 2.12. Tuto pravděpodobnost označíme jako pi,2 . Podobně můžeme vypočítat pravděpodobnost výskytu bodu v oblasti (3), kterou označíme jako pi,3 . Při rozhodování vycházíme z předpokladu, že i jediný bod, který hrozí, může způsobit srážku. Musíme tedy rozhodovat na základě „nejhoršihoÿ příspěvku mezi všemi body: max(pi,2 ) ≥ threshold → ZASTAV, i

max(pi,3 ) ≥ threshold → VAROVÁNÍ. i

(2.36)

2.9.2.4. Převedení na výpočet v prostoru Předchozí postup výpočtu byl demonstrovnán na jednorozměrném případě. Ve skutečnosti máme problém složitější. Na obrázku 2.14 je znázorněno vozidlo a epipolární rovina, která je tvořena bodem X a středy kamer A a B. Dříve jsme konstatovali, že nejistota bodu je pouze v epipolární rovině. Celkovou hustotu pravděpodobnosti bodu na této rovině umíme spočítat podle kapitoly 2.8.3 na straně 23. Nyní tedy ukážeme, jak vypočítat obsah obrazce na epipolární rovině, který se nachází uvnitř prostoru vozidla.

29


zv CB

CA

0

yv X

xv Obrázek 2.14.: Průsečík kvádru představující vozidlo a epipolární roviny, která je tvořena středy kamer A a B a bodu v prostoru X.

Zvolíme transformaci souřadnic tak, abychom dostali epipolární rovinu do roviny xy, z = 0. První část transformace posune střed kamery A do bodu [0, 0, 0]T , střed kamery B do [0, 1, 0]T a následně otočíme kolem osy y tak, aby z-souřadnice bodu X byla 0. V tomto okamžiku máme body v rovině xy. Druhá část transformace pouze tyto body v rovině posune tak, že střed kamery B bude v [0, 0]T a otočí soustavu tak, aby přímka tvořená průsečíkem epipolární roviny a roviny obrazu druhé kamery (epipolára lB ) byla rovnoběžná s osou x. Schématické znázornění je na obrázku 2.15. Pomocí této transformace převedeme do této souřadné soustavy i obrys vozidla, který ohraničí v rovině prostor, který je zobrazen na obr. 2.15 jako šedá plocha. Pro výpočty dále předpokládáme, že se rekonstruovaný bod nenachází za druhou kamerou, proto jsme zvolili takto složitou transformaci. Umožní nám totiž tento předpoklad realizovat tím, že budeme integrovat jen pro kladné hodnoty y.

2.10. Propojení více rekonstrukcí V případě, že kamera, kterou používáme k nahrání videosekvence nemá dostatečně velký zorný úhel, může se stát, že při couvání zmizí překážka z obrazu. Tato situace je znázorněna na obrázku 2.16. Z tohoto důvodu je nutné, abychom informace z rekonstrukce k zachovali ještě několik dalších kroků. V každém kroku k+i musíme však rekonstrukci k aktualizovat podle současného stavu.

30

2. Teoretický rozbor úlohy y

X

lB 0 C B

x

lA CA

Obrázek 2.15.: Průmět hranice vozidla na epipolární rovinu. Pravděpodobnost toho, že bod je v oblasti vozidla vypočítáme jako obsah šedého obrazce.

2.10.1. Určení počtu kroků, kdy překážka nebude vidět Na obrázku 2.16 je znázorněna geometrie pro výpočet počtu kroků. Hodnota z0 ukazuje, jaká nejnižší překážka nám vadí. Vzdálenost h pak vyjadřuje to, jak nejdále může být překážka od vozidla aniž ji uvidíme. Tuto vzdálenost můžeme vypočítat, jelikož výšku kamery známe a úhel α můžeme vypočítat z dat, které máme z kapitoly 2.7, str. 20. Počet rekonstrukcí, které si musíme pamatovat pak vypočítáme podle vzorce n = floor(h/∆d).

2.10.2. Dvě rekonstrukce Nyní ukážeme, jakým způsobem propojíme dvě po sobě jdoucí rekonstrukce. Jak jsme dříve popsali, rekonstrukcí získáme dvě kamery a jim odpovídající body v prostoru. V tomto případě tedy P1 , P01 a body X1 a ze druhé rekonstrukce kamery P2 , P02 a body X2 . Rekonstrukce 1 vznikla dříve, vozidlo je tedy dál od překážky než při rekonstrukci 2. 2.10.2.1. Zřetězení kamer Podle charakteru vstupních dat platí pro tyto dvě rekonstrukce to, že kamera P01 je fyzicky totožná s kamerou P2 . Toho využijeme a transformujeme rekonstrukci 1 tak, aby se matice kamery P01 rovnala matici P2 . Projekční rovnice druhé kamery v první rekonstrukci je x = P01 X1 = (P01 H−1 )(HX1 ).

(2.37)

Je vidět, že transformační maticí H můžeme získat libovolnou jinou matici kamery a tím pádem i jiné body. Podle výše uvedeného principu chceme získat transformaci

31


z

C α z0 y0

y0+h Δd

Δd

y Δd

Obrázek 2.16.: Znázornění situace, kdy se nízká překážka dostane z obrazu kamery a ohrozí vozidlo. Na obrázku je znázorněno, jak se překážka přibližuje při rekonstrukcích vždy po ujetí vzdálenosti ∆d.

H takovou, aby platilo !

(P01 H−1 ) = P2 . Z rovnice (2.38) odvodíme výraz pro matici H: −1 P2 P01 H= . 0 0 0 1 0 0 0 1

(2.38)

(2.39)

Čtvté řádky jsou v rovnici přidány proto, aby bylo možné vytvořit inverzní matici H−1 . V tuto chvíli můžeme transformovat souřadnou soustavu první rekonstrukce pomocí transformační matice následovně: P1 ← P1 H−1 , P01 ← P01 H−1 , X1 ← HX1 . Tím získáme to, že se první rekonstrukce posune přesně za druhou tak, že si budou odpovídat rekonstruované kamery P01 a P2 . V ideálním případě by si odpovídaly i body nacházejí se v obou rekonstrukcích. Tento fakt ale zkoumat nebudeme. 2.10.2.2. Zpracování bodů Pro tyto dvě rekonstrukce je možné vytvořit mnoho pravidel, podle kterých se bude s body zacházet. Například vážit polohu bodu s ohledem na neurčitost měření z jednotlivých rekonstrukcí, považovat bod za překážku pouze pokud je ve více rekonstrukcích za sebou apod. Problém je v tom, že v našem případě máme k dispozici

32

2. Teoretický rozbor úlohy pouze velmi málo měření, pouze jedno každých přibližně 17 centimetrů. Nemůžeme si proto dovolit hodnoty průměrovat. V našem případě rekonstrukce spojíme následovně: Body, které se nacházejí v obou rekonstrukcích, z té dřívější odstraníme. Můžeme předpokládat, že v pozdější rekonstrukci jsou body blíže ke kamerám a tím pádem jsou určeny s větší spolehlovostí.

2.10.3. Více rekonstrukcí Výše popsaným způsobem můžeme po sobě jdoucí rekonstrukce neomezeně řetězit. Samozřejmě platí, že čím více jich spojíme, tím větší chyby se dopouštíme. Budeme proto řetězit jen nejnutnější počet rekonstrukcí podle hodnoty, kterou jsme vypočetli v části 2.10.1 tak, abychom zaručili, že dokážeme zastavit vozidlo na základě překážky, kterou jsme někdy dříve v obraze viděli.

33

3. Popis algoritmu V předchozí kapitole jsme vysvětlili principy fungování jednotlivých metod, které jsou součástí této práce. V této kapitole popíšeme podrobně celý algoritmus po jednotlivých blocích. Při tom se budeme u jednotlivých částí odkazovat do předchozí kapitoly. Samotný program je napsán v MATLABu. Pro popsání algoritmu v této sekci jsme nicméně zvolili zápis pomocí tzv. pseudokódu. Tento způsob je vhodnější k ukázání a pochopení všech principů. Zdrojové kódy programu pro MATLAB jsou samozřejmě přiloženy na CD.

3.1. Vstup Systém nepracuje v reálném čase ani není úplně autonomní. Data, která mají být zpracována musí být pro algoritmus předpřipravena.

3.1.1. Data Fyzicky máme z vozidla k dispozici nahraný videosoubor se zvukovou stopou, kde je slyšet pípání magnetického senzoru otáčení kola (viz. kapitola 2.1 na str. 3). Předzpracování spočívá v těchto krocích: • Obrazová část videa je v rozlišení 640x480 obrazových bodů, 30 snímků za vteřinu. Obrazovou část nijak nepředzpracováváme. • Podle zvukové stopy ručně vybereme snímky, kde dochází k sepnutí magnetického spínače. Tyto indexy uložíme do proměnné FRAME_INDICES. • Vzdálenosti mezi snímky, které jsme vybrali v předchozím bodě známe, jelikož víme, jak jsou umístěny magnety po obvodu kola. Tyto vzdálenosti uložíme do proměnné CAMERAS_DISTANCES. Pokud má proměnná FRAME_INDICES N prvků, proměnná CAMERAS_DISTANCES jich pak má N − 1.

3.1.2. Kamera Pro výpočty geometrie musíme znát vnitřní parametry kamery. Kameru je proto potřeba předem zkalibrovat. Postup kalibrace je uveden v části 2.3.5 na straně 12. Vstupem tedy je několik snímků kalibračního obrazce.

34

3. Popis algoritmu Pro získání pravé rekonstrukce musíme znát i její umístění na vozidle. Popis rekonstrukce je uveden v kapitole 2.7 na straně 20. K tomuto účelu potřebujeme snímek kalibračního obrazce na vodorovné ploše s osou rovnoběžnou s osou xv . Parametry kamery a postup nalezení polohy na vozidle je pro použitou kameru uveden v další části práce.

3.2. Výstup Výstupem algoritmu jsou informace pro řidiče. Z principu může systém někdy selhat a řidič by vždy měl mít poslední slovo při rozhodování. Náš algoritmus pouze informuje o překážkách a doporučuje zastavení vozidla. Forma tohoto varování může být při případné teoretické instalaci do vozidla různě pozměněna. Metoda, kterou zde použijeme, je pouze informativní. Pokud je v obraze rozpoznána překážka, je v obraze vyznačena žlutou barvou a objeví se nápis „VAROVÁNÍÿ. Pokud byla překážka rozpoznána dříve a nyní není v obraze vidět, je tam napsáno „VAROVÁNÍ – NENÍ VIDĚTÿ. Pokud je rozpoznána překážka, která je tak blízko, že je třeba zastavit, je v obraze vyznačena červenou barvou spolu s nápisem „ZASTAVÿ. Pokud tato překážka není vidět (byla v předchozích rekonstrukcích), je na obrazovce pouze nápis „ZASTAV – NENÍ VIDĚTÿ. Důležité je si uvědomit, že tento systém v případě výskytu překážky nezaručuje její detekci! Pokud překážku správně odhalí, tak na ni upozorní. Pokud však neupozorňuje, neznamená to, že tam žádná překážka není!

3.3. Algoritmus Počáteční fáze algoritmu je nezávislá na pohybu kamery. Zpracováváme celý videosoubor bez dalších informací.

35

3. Popis algoritmu

3.3.1. Nalezení významných bodů v obraze Vstup: video //proměnná, která reprezentuje videosoubor Program: 1: Nf rames ← počet snímků ve videu 2: g ← gaussian(5; 1,5) //Gaussův filtr velikosti 5x5 pixelů a σ = 1,5 3: for i = 1 to Nf rames do 4: f rame ← video(i) 5: f rame ← conv2( f rame, g ) //vyhlazení obrázku filtrem g 6: corners(i) ← get corners( f rame ) //nalezení rohů podle alg. 2.2.1.1, str. 5. 7: end for Výstup: corners //proměnná, kde jsou uloženy rohy pro jednotlivé snímky Nf rames počet snímků ve videu

3.3.2. Nalezení kandidátů na korespondenci Kandidáty na korespondenci hledáme vždy mezi dvěma vedlejšími snímky. Vstup: corners //proměnná, kde jsou uloženy rohy pro jednotlivé snímky Nf rames počet snímků ve videu Program: 1: for j = 2 to Nf rames do 2: (crni , crnj ) ← (corners(j − 1), corners(j)) //rohy ve dvou po sobě jdoucích snímcích 3: spočítej matici NCC koeficientů r podle 2.2.2.2, str. 7 4: for each řádek k v r do 5: l ← max(k) //vyber sloupec, pro nějž je hodnota v řádku k max. 6: kl ← max(l) //vyber řádek, pro nějž je hodnota ve sloupci l max. 7: if k == kl then 8: kandidati(i).dalsi(k) ← l //uložení kandidáta z dalšího snímku 9: kandidati(i).ncc(k) ← r(k, l) //uložení hodnoty koeficientu 10: end if 11: end for 12: end for Výstup: kandidati //Struktura, ve které je pro každý roh každého snímku uložena informace o kandidátech na korespondenci.

36

3. Popis algoritmu

3.3.3. Propojení korespondencí přes více snímků (tracks) Pro stanovení korespondujících rohů mezi dvěma vzdálenými snímky musíme sledovat elementární korespondence snímků po sobě jdoucích. Pro každý snímek ve videu vytvoříme matici, kde každý řádek odpovídá jednotlivé dlouhé korespondenci a sloupec určuje relativní pořadí snímku. Hodnota prvku v matici pak udává index do odpovídající proměnné corners. Vstup: corners //proměnná, kde jsou uloženy rohy pro jednotlivé snímky kandidati //informace o korelačních koeficientech jednotlivých rohů Nf rames počet snímků ve videu Program: 1: rmin ← 0,8 //minimální korelační koeficient 2: for i = 1 to Nf rames do 3: ind ← vyber indexy rohů, které mají kandidáta v následujícím snímku podle kandidati(i).dalsi a jejichž korelační koeficient je větší než rmin podle kandidati(i).ncc 4: tracks(i).tracks(1) ← ind //ulož tyto indexy do matice tracků i-tého snímku 5: k ← i //hodnota vnitřního cyklu začíná na současném snímku 6: while ind > ∅ & not ( konec videa ) do 7: k ←k+1 8: z corners(k) vybereme podle ind rohy, které korespondují s předchozím snímkem. Uložíme je do tracks(i).tracks(1 + k − i) (do dalšího sloupce matice tracků pro daný snímek i) 9: ind ← podle kandidati(k).dalsi vybereme opět další kandidáty těch rohů, které jsme vybrali z corners(k) 10: end while 11: end for Výstup: tracks //Struktura, ve které je pro každý snímek matice tracků, které v tomto snímku začínají.

3.3.4. Výběr dat pro výpočet geometrie V tento okamžik máme nalezené rohy ve všech snímcích videa a máme pro každý snímek nalezené všechny tracky, které v něm začínají. Další výpočty pracují vždy se dvěma snímky, které jsou vybrány podle indexů v proměnné FRAME_INDICES. S každou touto dvojicí pracujeme zvlášť. Dále tedy bude popsáno, jak je zpracována tato dvojice a na závěr ukážeme, jak jednotlivé výsledky spojíme dohromady.

37

3. Popis algoritmu Vstup: corners //proměnná, kde jsou uloženy rohy pro jednotlivé snímky tracks //informace o korespondujících bodech f rameIndices //vektor s indexy snímků u kterých známe relativní vzdálenosti camerasDistances //vzdálenosti kamer mezi snímky v f rameIndices Program: 1: Nindices ← počet indexů v f rameIndices 2: for i = 1 to Nindices − 1 do 3: (fA , fB ) ← (f rameIndices(i), f rameIndices(i + 1)) //indexy snímků 4: (crA , crB ) ← (corners(fA ), corners(fB )) //odpovídající rohy 5: (cA , cB ) ← (normalize(crA ), normalize(crB )) //normalizované souřadnice distc ← camerasDistances(i) //uložení vzdálenosti kamer pro dané dva snímky 7: end for Výstup: cA , cB //normalizované souřadnice rohů ve dvou obrazech, ze kterých budeme počítat geometrii distc //vzdálenost kamer, kterým korespondují rohy cA a cB 6:

3.3.5. Výpočet esenciální matice Esenciální matici vypočteme z normalizovaných souřadnic rohů cA a cB pomocí 5-bodového algoritmu metodou RANSAC tak, jak je popsáno v části 2.5 na straně 15. Funkce RANSACu ukazuje algoritmus 2.1. Doplňující informace jsou uvedeny dále: • Proměnná s v rovnici (2.22) je 5, protože používáme 5-bodový algoritmus. • Pravděpodobnost p, neboli pravděpodobnost, s jakou chceme vybrat všechny dobré vzorky pro výpočet volíme 0,999. • Pro každou navrženou esenciální matici počítáme supp podle následujícího postupu: – Pro každou dvojici bodů vypočítáme opravené souřadnice, které vyhovují navržené esenciální matici, podle sekce 2.6.2, str. 19. – Pro každou dvojici bodů vypočítáme součet Euklidovských vzdáleností Ci podle rovnice (2.28). – Dvojice, pro které platí Ci > 0.01 označíme za outliers. P – Podporu vypočítáme jako −supp = Ci + počet outliers. ( Pozor na záporné znamínko. )

38

3. Popis algoritmu • Víme, že se kamery mezi snímky nemohou pohnout libovolně, jelikož jsou umístěné na vozidle. Této znalosti využijeme a omezíme prostor možných poloh druhé kamery a tím i omezení na esenciální matice. Omezení je popsáno v následující kapitole. V případě, že esenciální matice tomuto omezení nevyhoví, zahazujeme ji s supp = −∞. 3.3.5.1. Omezení polohy druhé kamery Způsob omezení polohy druhé kamery je zobrazeno na obrázku 3.1. Epipól e1 vypočítáme z naklonění kamery získané podle kapitoly 2.7, str. 20. Epipól e může být od e1 odchýlen ve směru x maximálně o ±7◦ . Tato hodnota je odvozena přibližně z hodnoty průměru otáčení vozidla a ze vzdálenosti, kterou vozidlo ujede mezi dvěma snímky. Ve směru y může být odchylka přibližně ±15◦ . Tato hodnota přibližně vyplývá z hodnoty o kolik se může zvednout zadní část vozu při nájezdu zadními koly na překážku. Z hodnoty epipólu e1 a naklonění kamery vypočítáme rozsah možných hodnot epipólu e v normalizovaných obrazových souřadnicích.

C’ e

C1’

C e1

Obrázek 3.1.: Znázornění relativní polohy dvou kamer. Bod C01 zobrazuje střed druhé kamery při vodorovném pohybu. Tento bod je první kamerou promítán do epipólu e1 . Polohu druhé kamery omezíme tím, že omezíme polohu epipólu v prvním obraze.

Výstupem této části algoritmu je ta nejlepší esenciální matice E∗ a indexy dvojic ind∗ , které byly k výpočtu této matice použity.

39

3. Popis algoritmu

3.3.6. Výpočet matic kamer z esenciální matice Vstup: E∗ ind∗ Program: 1: P01 . . . P04 ← 4 možné matice podle rovnice (2.25), str. 18 2: P ← [I|0] 3: for i = 1 to 4 do 4: vypočítej 3D souřadnice X některého rohu z ind∗ podle (2.27), str. 19 âx ˆ 0 , protože bod, ze kterého byla matice //Zde není nutné hledat body x E vypočítána, epipolární geometrii vyhovuje. 5: XA ← transformace bodu X do souřadné soustavy první kamery 6: XB ← transformace bodu X do souřadné soustavy druhé kamery 7: if souřadnice z bodů XA i XB > 0 then 8: P0 ← P0i 9: break 10: end if 11: end for Výstup: P, P0 //matice kamer

3.3.7. Výpočet 3D souřadnic bodů Může se stát, že některé korespondence označí algoritmus RANSAC jako outliers. Tyto korespondence neodpovídají nalezenému modelu E∗ , a proto je z dalšího zpracování odstraníme. Vstup: E∗ P, P0 cA , cB Program: 1: for i = 1 to N do âx ˆ 0 ← vypočítej opravené obrazové souřadnice bodů cA (i) a cB (i) podle 2: x algoritmu 12.1 v [6] 3: X(i) ← vypočítej 3D souřadnice bodu podle 2.6.2, str. 19 4: end for 5: X ← X(inliers) //pro další zpracování vezmeme jen body vyhovující modelu E∗ Výstup: X //souřadnice bodů v prostoru

40

3. Popis algoritmu

3.3.8. Transformace do 1:1 Transformace do skutečnosti probíhá přesně podle kapitoly 2.7 str. 20. Vstup: Rc , zc , distc P, P0 X Program: 1: s ← distc 2: for each X do 3: X ← sX 4: end for 5: P0 = [R|t] 6: P0 ← [R|st] 7: 8: 9: 10: 11:

H ← podle (2.31) str. 21 P ← PH−1 P0 ← P0 H−1 X ← HX Výstup: X //souřadnice bodů v prostoru, rekostruované 1:1. Tyto body jsou v souřadné soustavě v podle obrázku 2.7 na straně 21 P, P0 //matice kamer odpovídající bodům X

3.3.9. Rozhodnutí V tomto okamžiku máme rekonstruovány body v prostoru, v souřadné soustavě vozidla. V této soustavě také máme definováno vozidlo jako kvádr a ještě další dva kvádry podle obrázku 2.12 v části 2.9.1. Pro každý zrekonstruovaný bod nyní musíme převést problém do epipolární roviny a v této rovině vypočteme • integrál hustoty pravděpodobnosti sall pro bod X v celé rovině, • integrál hustoty pravděpodobnosti sobst ve výřezu roviny, který představuje oblast pro okamžité zastavení (2) a • integrál hustoty pravděpodobnosti swarn ve výřezu roviny, který představuje oblast pro upozorňování na překážky (3). Na základě těchto hodnot rozhodneme v obou případech podle rovnic (2.36). Funkce je opět shrnuta v následujícím algoritmu:

41

3. Popis algoritmu Vstup: P, P0 , X threshold //řidičem zvolený práh pro rozhodování podle kapitoly 2.9.2.2 Program: 1: for each Xi in X do 2: Převeď P, P0 a Xi , které tvoří epipolární rovinu do souřadné soustavy, kde ta rovina je rovnoběžná s rovinou xy tak, jak je popsáno v kapitole 2.9.2.4. Transformaci, která toto udělá označ M. 3: Pro každý bod v této rovině, pro který platí y > 0, spočítej pravděpodobnost výskytu bodu Xi podle vzorce (2.34). Sumu ulož jako sall,i . 4: Vypočítej body průniku epipolární roviny s kvádrem (2) podle obr. 2.12. Tyto body transformuj maticí M do roviny xy. Vznikne obrazec podobný 2.15. 5: Podobně pro každý bod v rovině xy, který se nachází v obrazci, vypočítej pravděpodobnost výskytu bodu podle (2.34). Tuto sumu ulož do proměnné sobst,i . 6: Řádky 4 a 5 zopakuj pro kvádr (3). Sumu pravděpodobnosti ulož do swarn,i . 7: Pravděpodobnost polohy bodu v kvádru (2) spočítej jako collisioni = sobst,i /sall,i . 8: Pravděpodobnost polohy bodu v kvádru (3) spočítej jako obstaclei = swarn,i /sall,i . 9: end for 10: Nakresli druhý obrázek z této geometrie. (Ten, který souvisí s kamerou P0 .) 11: if collisioni ≥ threshold then 12: Označ tento bod v obraze červeně a doporuč „ZASTAVÿ. 13: end if 14: if obstaclei ≥ threshold then 15: Označ tento bod v obraze žlutě a napiš „VAROVÁNÍÿ. 16: end if

3.3.10. Spojení více geometrií V tuto chvíli máme kompletně popsaný algoritmus pro každé dva snímky a geometrii, která je spojuje. Jak je ale popsáno v kapitole 2.10 na straně 30, v případě, že používáme kameru, která nemá úhel pohledu 180◦ , může se nějaká překážka ztratit z výhledu. Proto musíme při rozhodování k aktuální geometrii částečně přidat i geometrie předchozí. Postup, jak propojit dvě geometrie je uveden v kapitole 2.10. Celkový algoritmus bude vypadat následovně:

42

3. Popis algoritmu Vstup: g1...n //vypočítané geometrie, počet je určený podle 2.10.1, n-tá geometrie je poslední Program: 1: g1...n−1 ← Převeď geometrie g1...n−1 podle rovnic (2.39) a (2.40) vzhledem ke geometrii gn . 2: g1...n−2 ← Podobně převeď geometrie g1...n−2 vzhledem ke geometrii gn−1 . 3: . . . 4: g1 ← Podobně převeď geometrii g1 vzhledem ke geometrii g2 . 5: for each dvojice geometrií gi a gi+1 do 6: Body, které jsou v obou geometriích, z geometrie gi odstraň. 7: end for 8: Každou geometrii analyzuj a rozhodni podle postupu uvedeného v předchozí kapitole (3.3.9).

43

4. Experimentální ověření funkce V této kapitole uvedeme přesné informace o všech hodnotách nastavení, které jsme v předchozích kapitolách používali jen obecně. Dále ukážeme kalibraci kamery a několik experimentů, které demonstrují funkci našeho programu.

4.1. Kamera K pokusům jsme používali kameru Unibrain Fire-i (popis lze nalézt v [15]). Jedná se o jednoduchou, levnou kameru pro domácí využití. Připojení k počítači je realizováno přes rozhraní Firewire. Fotografie umístění kamery na vozidle pro experimentální ověření je na obrázku 4.1.

Obrázek 4.1.: Fotografie umístění kamery na vozidle.

4.1.1. Kalibrace Kameru jsme zkalibrovali pomocí [3]. Na obrázku 4.2 jsou zobrazeny dva snímky s kalibračním obrazcem sejmuté touto kamerou. Celkem jsme pro kalibraci použili 40 různých snímků. Kamera má poměrně malé radiální zkreslení, zvolili jsme proto model zkreslení závislý na druhé mocnině vzdálenosti od středu zkreslení. Střed zkreslení je v počátku normalizovaných souřadnic. Funkce, která upravuje normalizované souřadnice

44

4. Experimentální ověření funkce

Obrázek 4.2.: Několik snímků z kamery, na kterých je zobrazen kalibrační obrazec.

xn = [xn , yn ]T podle zvoleného modelu zkreslení je uvedena v části 2.3.2.2 jako rovnice (2.11). Nyní tuto rovnici můžeme vyjádřit konkrétně: xd = f (xn ) = (1 + kc r2 )xn ,

(4.1)

kde r je vzdálenost normalizovaného bodu od počátku souřadnic: r2 = x2n + yn2 . Hodnota koeficientu kc je uvedena v souhrnné tabulce 4.1. Kalibrací získáme také matici vnitřních parametrů K. Matice K má strukturu popsanou v kapitole 2.3.2.3 na straně 10. V kalibraci jsme odhadovali parametry fx , fy , x0 a y0 . Parametr s jsme zvolili 0, předpokládáme osy v obraze na sebe kolmé. Hodnoty, které jsme získali jsou uvedené v tabulce 4.1. Tabulka 4.1.: Vnitřní parametry kamery získané kalibrací.

parametr hodnota fx 858,365 fy 861,628 x0 347,958 y0 242,719 kc −0,0888

4.1.2. Orientace v soustavě vozidla Kapitola 2.7 na straně 20 uvádí, jakým způsobem získáme body zrekonstruované v souřadné soustavě vozidla podle obrázku 2.7. Je k tomu potřeba vypočítat vzájemnou orientaci kamery a vozidla. V našem případě jsme tento problém vyřešili následovně: Kalibrační toolbox nabízí funkci compute extrinsic, která umí vypočítat vnější parametry kamery Rc ,

45

4. Experimentální ověření funkce tc při známých vnitřních parametrech. Vyfotíme tedy kamerou kalibrační obrazec a z něj získáme tyto dva parametry. Obrázek kalibračního obrazce je vidět na obr. 4.3. Je na něm také zakreslena souřadná soustava světa, kterou kalibrační toolbox zvolil. 50 100 150 200

Y 250

X

O 300

Z 350 400 450 100

200

300

400

500

600

Obrázek 4.3.: Kalibrační obrazec, sloužící k určení vztahu mezi souřadnou soustavou vozidla a kamery. Je zde také zakreslena souřadná soustava světa podle kalibračního toolboxu.

Kalibrační obrazec z obrázku 4.3 se ale nenachází na zemi. Víme, že se nachází na zdi kolmé k vozovce a známe tedy vztah souřadné soustavy vozidla a tohoto obrazce. Tento vztah je znázorněn na obrázku 4.4. V tomto obraze známe transformaci ze souřadné soustavy vozidla (v) do soustavy p a pak transformaci ze soustavy p do soustavy kamery. Transformaci ze soustavy vozidla do soustavy kamery, jinými slovy požadovanou matici kamery P0 v rekonstrukci 2.7.2, získáme upravením rovnice (2.30) takto:      Rh

 (P0 H−1 ) =   0

0

  th  Rc tc  Rp tp  . =      0 0 0 1 0 1 0 0 0 1

(4.2)

Z této rovnice vyjádříme transformační matici H a s její pomocí upravíme kamery a body podle rovnice (2.32).

4.1.3. Nejistota měření bodů v obraze V kapitole 2.8.3 na straně 23 jsme uvedli předpoklad, že body v obraze měříme s nejistotou, kterou modelujeme šumem s normálním rozdělením pravděpodobnosti.

46


zv C

zc

tH

R H yc

yp

Rc

xc

tc zp

tp 0

0p Rp

xp

yv xv

Obrázek 4.4.: Pomocná souřadná soustava pro určení vztahu mezi kamerou a vozidlem. Střed kamery C se nachází na ose zv . x a y prvky vektorů tc a tp (vyjádřené v soustavě v) nás nezajímají, protože se od sebe odečtou. Při určování transformace H je ani neznáme.

Parametry tohoto šumu zvolíme µ = 0 a σp2 = 0,52 . Zajímá nás, jaká je neurčitost určení normalizovaných souřadnic bodů. Vztah mezi bodem v obraze xp a normalizovaným bodem xd je uveden jako rovnice (2.12). Pokud zanedbáme rozdíl mezi hodnotami fx a fy (v tabulce 4.1 je vidět, že jsou téměř stejné) a zkreslení kamery, můžeme psát x = f xn + x0 (parametr s = 0), y = f yn + y0 .

(4.3)

Pokud X je náhodná veličina a a je konstanta, platí podle [7] následující vzorce pro rozptyl: var(aX) = a2 var(X), var(a + X) = var(X).

(4.4)

Pokud tedy z libovolné rovnice (4.3) vyjádříme libovolnou veličinu in , můžeme podle pravidel (4.4) určit také její rozptyl: x x0 x − x0 = − , f f f 1 1 var(x) = 2 σp2 . var(xn ) = 2 f f xn =

(4.5)

Hodnota σ 2 pro výpočet neurčitosti bodu v epipolární rovině podle rovnice (2.34) je tedy vypočítána podle rovnice (4.5). Použili jsme hodnotu σ 2 = 10−6 .

47


4.2. Rozměry vozidla Jak je uvedeno v kapitole 2.9.1, jako model vozidla jsme vybrali kvádr, charakterizovaný čtyřmi hodnotami. Pro experimentální ověření jsme podle použitého vozidla zvolili rozměry uvedené v tabulce 4.2. Počet geometrií, které musíme řetězit na základě vyjádření z kapitoly 2.10 je 4. Tabulka 4.2.: Rozměry vozidla použitého při experimentech.

xA 950 mm

xB −950 mm

y0 200 mm

z0 100 mm

4.3. Experimenty Nyní ukážeme několik experimentů, které jsme provedli k ověření funkce našeho programu. Ukážeme vždy několik snímků z nahrané videosekvence a obrázek s vypočtenými informacemi. Všechny experimenty, které jsme provedli a nezkrácená videa jsou k nalezení na přiloženém CD.

4.3.1. První experiment První experiment je zobrazen na obrázku 4.5. Zde couváme k tenkému sloupku z cihel. Část překážky zmizí z pohledu, ale část zůstane. Je vidět, že je rozhodnuto i na základě dřívějších rekonstrukcí.

4.3.2. Druhý experiment Další experiment ukazuje nízké překážky různých výšek. Program správně rozliší výšku a upozorní pouze na tu, která zasahuje do území vozidla. Tento pokus je zobrazen na obrázku 4.6. Je zde také vidět to, že i když překážka úplně zmizela z obrazu, přesto na jejím základě rozhodneme o zastavení, protože si pamatujeme i předchozí geometrie.

4.3.3. Třetí experiment Třetí pokus ukazuje případ, kdy s vozidlem couváme k překážce, která nemá výraznou texturu. Není na ní možné nalézt významné body a tím pádem není možné rekonstruovat geometrii ani upozornit na překážky. Toto je ten hlavní důvod toho, proč není možné se na tento program za všech okolností spoléhat, protože některé situace tímto přístupem prostě nemohou jít vyřešit. Experiment je zobrazen na obr. 4.7. Tato situce simuluje například couvání k bílé zdi v podzemní garáži.

48


1000

1000

800

800

600 z [mm]

400

400

v

zv [mm]

600

200

200

0

0

−200 −1000

−200 −1000 0

0 1000

−500

xv [mm]

0

500

1000 1500 yv [mm]

2000

2500

3000

3500

1000

4000

−500 xv [mm]

0

500

1000 1500 y [mm]

2000

2500

3000

3500

4000

v

STOP STOP − not visible ATTENTION ATTENTION − not visible

ATTENTION

Geometrie 1; est: 1

Geometrie 7; est: 1

Obrázek 4.5.: První experiment. Levý sloupec představuje rekonstrukci na počátku sekvence, pravý sloupec představuje poslední rekonstrukci. V prvním řádku je zobrazen snímek, který vidí první kamera, ve druhém řádku je zobrazen snímek z druhé kamery. Ve třetím řádku je zobrazena 3D rekonstrukce bodů a kamer současné a předchozí geometrie. Body, které jsou ze současné geometrie jsou modré, předchozí jsou zelené. Body jsou zobrazeny bez neurčitosti. Také jsou zde zobrazeny hranice vozidla podle obr. 2.12. Poslední řádek ukazuje obraz, který je promítán řidiči. Obshuje vyznačené překážky podle kapitoly 3.2.

49


1000 800

1000

600 z [mm]

800

zv [mm]

600

400 200

400

0

200

−200 −1000 −500

0

0 −200 −1000

4000 −500

2000 0

500

1000

500

0

1000 x [mm]

y [mm] xv [mm]

v

−500

0

500

1000 1500 y [mm]

ATTENTION

STOP − not visible ATTENTION ATTENTION − not visible

Geometrie 1; est: 1

Geometrie 5; est: 1

2000

2500

3000

3500

4000

Obrázek 4.6.: Druhý experiment. Tento experiment porovnává detekci různě vysokých překážek. Vlevo se nachází překážka vysoká přibližně 17 cm, vpravo je překážka vysoká 8 cm. Obrázky jsou organizovány stejně jako u obrázku 4.5. V levém sloupci je první rekonstrukce, v pravém sloupci je rekonstrukce, kde je již rozhodnutí „ZASTAVÿ. Ve třetím řádku vpravo jsou zobrazeny body ze všech čtyř geometrií. Body, na základě kterých je zastaveno jsou z nejstarší geometrie a jsou zobrazeny černě.

50


ATTENTION NO DATA

Geometrie 1; est: 1

Geometrie 5; est: 0

Obrázek 4.7.: Třetí experiment. Tento experiment ukazuje špatně podmíněný případ. S vozidlem couváme k jednolité barevné desce, která tvoří překážku. Není možné na ní zachytit body a sledovat je a tím pádem nelze ani rekonstruovat scénu. První tři obrázky ukazují rekonstrukci ze začátku sekvence, kde je vidět i nějaké okolí. Poslední obraz ukazuje pozdější snímek, kde nebyla provedena rekonstrukce scény.

4.3.4. Čtvrtý experiment Čtvrtý experiment zobrazuje couvání k zaparkovanému vozidlu. Tento pokus je vidět na obrázku 4.8. Znázornili jsme zde situaci, při které došlo k tomu, že body v obrazech byly nesprávně označeny za korespondující. Rekonstruovaný bod z této korespondence je špatně umístěn a tvoří překážku. Na obrázku 4.9 je znázorněn průběh hodnot pravděpodobností podle kapitoly 2.9.2.3. V této kapitole jsme konstatovali, že pro varování nebo zastavení se rozhodujeme na základě maxima všech příspěvků pravděpodobnosti od všech bodů. Tento graf znázorňuje pro jednotlivé geometrie tuto hodnotu.

51


1000

ATTENTION

800

400

v

z [mm]

600

200

0

−200 −500

0

500

1000

1500 2000 yv [mm]

2500

3000

3500

4000 Geometrie 2; est: 1

STOP ATTENTION ATTENTION − not visible

ATTENTION

Geometrie 19; est: 1

Geometrie 27; est: 1

Obrázek 4.8.: Čtvrtý experiment zobrazuje couvání k vozidlu. První řádek obrázků ukazuje vstupní obrazy z první a druhé kamery pro druhou rekonstrukci. Je zde znázorněn bod, který je špatně lokalizován, jelikož si v obrazech neodpovídá. Uprostřed vlevo je zobrazena rekonstruovaná scéna bez nejistot bodů, vpravo je pak obrázek s informacemi pro řidiče. Spodní dva obrazy ukazují obrazy pro řidiče z některých dalších rekonstrukcí.

52


1.4 k = 3, kvadr (3), VAROVANI k = 2, kvadr (2), ZASTAV 1.2

maxi ( pi,k )

1

0.8

0.6

0.4

0.2

0

0

5

10

15 Geometrie

20

25

30

Obrázek 4.9.: Graf, podle kterého je rozhodováno ve čtvrtém experimentu. Zeleně je zobrazena hodnota maxi (pi,3 ), neboli největší z hodnot, které vyjadřují pravděpodobnost toho, že se daný bod i nachází v prostoru kvádru (3). Podobně je červeně zobrazena hodnota maxi (pi,2 ), která souvisí s kvádrem (2). Při výpočtu si pamatujeme vždy tři starší geometrie. Pokud tedy např. v geometrii 2 byl (špatně) detekován bod, který tvoří překážku s pravděpodobností 1, bude ještě další tři rekonstrukce tuto překážku způsobovat.

4.3.5. Pátý experiment V průběhu výzkumu jsme zjistili, že rekonstrukce do skutečné velikosti podle kapitoly 2.7 je velice náchylná na nepřesnost měření ujeté vzdálenosti mezi jednotlivými snímky. Provedli jsme proto umělý experiment, který tuto situaci znázorňuje. Tento experiment je zobrazen na obrázku 4.10.

53


800 skutecna vzdalenost: 163mm skutecna vzdalenost: 173mm skutecna vzdalenost: 183mm

1 700 0.8 0.6

600

0.4

500 z [mm]

z [mm]

0.2 0 −0.2 −0.4

400 300 200

−0.6 100 −0.8 −1 −400

0 −200

0 x [mm]

200

400

1000

1200

1400

1600 y [mm]

1800

2000 −100 −500

0

500

1000 y [mm]

1500

2000

2500

Obrázek 4.10.: Pátý experiment, který ukazuje závislost rekonstrukce na správně stanovené ujeté vzdálenosti. Vlevo je zobrazena uměle vytvořená scéna. Body leží na vozovce (z = 0). Tyto body jsou několikrát vyfoceny dvěma kamerami, jejichž relativní vzdálenost měníme. Z těchto bodů je pak standardním způsobem nalezena trojrozměrná scéna. Vpravo je vidět výsledek, který porovnává tři případy. Pro rekonstrukci scény vždy používáme vzdálenost kamer 173 mm, pro vytvoření korespondujících bodů byly relativní vzdálenosti kamer 163 mm, 173 mm a 183 mm. Je vidět, že pokud je skutečná vzdálenost mezi kamerami menší, než si myslíme, jsou rekonstruované body dále od vozidla. Naopak pokud jedeme pomaleji (skutečná vzdálenost je větší), jsou body rekonstruovány blíže. Z pokusu je vidět, že nepřesnost měření pohybu kamery o 1 cm způsobí rozdíl v poloze bodu na vozovce o cca 6 cm.

54

5. Možná vylepšení algoritmu V této kapitole stručně nastíníme vylepšení, která by byla na tomto systému možno provést a tím jej vylepšit: • V systému, který by měl být nasazen ve vozidle, by bylo žádoucí, aby rekonstrukce probíhaly častěji. Toho je možné dosáhnout, protože všechna nová vozidla již mají čidla pohybu kol, například snímače systému ABS. Tato čidla generují mnohem více impulzů na jednu otáčku kola než náš systém. Výhoda použití těchto snímačů je také ta, že spínají přesněji než spínač magnetický a určí tak ujetou vzdálenost mnohem přesněji. • V případě, že bychom měli k dispozici více dat z měření, bylo by možné body různými metodami filtrovat a jednotlivá měření více slučovat. Tím by byla zajištěna větší stabilita systému a menší množství planých poplachů.

55

6. Závěr V této práci jsme navrhli systém pro detekci překážek ze sekvence obrazů. Video jsme získali z kamery umístěné na zadní části vozu. Informace o přibližném pohybu vozidla pro rekonstrukci geometrie jsme získali z magnetického snímače otáčení kola. Vytvořili jsme systém, který hledá v jednotlivých snímcích významné body, které následně spojuje přes několik po sobě jdoucích snímků. Pomocí těchto korespondencí systém rekonstruuje trojrozměrnou scénu. Do modelu jsme zahrnuli předpoklady o nejistotě měření bodů v obrazech. Poloha bodů je ovlivněna šumem, který jsme modelovali jako šum s normálním rozdělením pravděpodobnosti. Ukázali jsme, že můžeme vypočítat, s jakou pravděpodobností se bod nachází v daném místě v prostoru. Na základě této pravděpodobnosti jsme sestavili rozhodovací proces, který hledá body, které tvoří překážku a upozorňuje řidiče. Systém jsme otestovali na reálných datech. V experimentech je vidět, že v dobře podmíněných situacích funguje systém poměrně dobře. Při rozhodování o zastavení systém téměř ve všech experimentech rozhodl správně. Pouze ve čtvrtém pokusu rozhodl o jednu rekonstrukci dříve, což ale není na škodu. Nestalo se, že by systém nechal vozidlo narazit (kromě třetího pokusu ve kterém nebyla k dispozici data). Při rozhodování o překážce jsou výsledky poněkud horší, zejména co se týče bodů rekonstruovaných na vozovce. Jedním z hlavních důvodů je to, že systém prohlásil dva body na vozovce za korespondující, které ve skutečnosti korespondující nejsou. Tento problém by bylo možné určitými modifikacemi odstranit. Další problém může být to, že jsme ujetou vzdálenost měřili pomocí magnetického spínače poměrně nepřesně. Ukázali jsme experiment, který znázorňuje, že při chybě měření ujeté vzdálenosti o 1 centimetr je chyba rekonstrukce bodu na vozovce přibližně 6 cm. Naše metoda principiálně selže v situaci, kdy překážku představuje jednobarevný nekontrastní objekt, na kterém není možné dostatečně dobře dektekovat významné body. V takovém případě nemůžeme scénu rekonstruovat a analyzovat. Na takové překážky nemůžeme tedy upozornit. V poslední části práce jsme navrhli několik možných témat, která ukazují, jak by bylo možné dále tento algoritmus do budoucna vylepšit. . .

56

Literatura [1] Bosch Automatic parking system. URL http://www.bosch.com.mx/content/language1/html/715_11132.htm [2] Lexus Intelligent Parking System. URL http://www.youtube.com/watch?v=W5_0Q3OU7tI [3] Bouguet, J.-Y.: Camera Calibration Toolbox for MATLAB. URL http://www.vision.caltech.edu/bouguetj/calib_doc/index.html [4] Camus, T.: Calculating Time-to-Contact Using Real-Time Quantized Optical Flow. 1995. URL citeseer.ist.psu.edu/camus95calculating.html [5] Harris, C. G.; Stephens, M. J.: A combined corner and edge detector. Proceeding Fourth Alvey Vision Conference, 1988: s. 147–151. [6] Hartley, R.; Zisserman, A.: Multiple View Geometry in Computer Vision. Cambridge University Press, druhé vydání, 2004, ISBN 0521540518. [7] Hindls, R.; Hronová, S.; Seger, J.; aj.: Statistika pro ekonomy. Professional Publishing, sedmé vydání, 2006, ISBN 80-86946-16-9. [8] JABLOTRON: Ultrazvukové parkovací senzory. URL http://www.jablotron.cz/autotechnika.php?pid=autotechnika/ parkovani [9] Low, T.; Wyeth, G.: Obstacle Detection using Optical Flow. Proceedings of the Australasian Conference on Robotics & Automation, 2005. [10] Nistér, D.: An Efficient Solution to the Five-Point Relative Pose Problem. IEEE Transactions on Pattern Analysis and Machine Intelligence, ročník 26, č. 6, 2003: s. 756–777. URL http://doi.ieeecomputersociety.org/10.1109/TPAMI.2004.17 [11] Nistér, D.; Naroditsky, O.; Bergen, J.: Visual Odometry for Ground Vehicle Applications. Journal of Field Robotics, ročník 23, č. 1, 2006: s. 3–20, ISSN 1556-4959. URL http://dx.doi.org/10.1002/rob.20103

57

Literatura [12] Santos-Victor, J.; Sandini, G.: Uncalibrated Obstacle Detection Using Normal Flow. Machine Vision and Applications, ročník 9(3), 1996: s. 130–137. URL citeseer.ist.psu.edu/article/santos-victor96uncalibrated. html [13] Stewénius, H.; Engels, C.; Nistér, D.: Recent Developments on Direct Relative Orientation. ISPRS Journal of Photogrammetry and Remote Sensing, ročník 60, Červen 2006: s. 284–294. URL http://dx.doi.org/10.1016/j.isprsjprs.2006.03.005 [14] Stewénius, H.: Gröbner Basis Methods for Minimal Problems in Computer Vision. Phd thesis, Centre for Mathematical Sciences LTH, Lund, Sweden, 2005. [15] Unibrain: Fire-i Firewire camera, model roku 2001. URL http://www.unibrain.com/Products/VisionImg/pHist_Fire_i_DC. htm [16] Werner, T.: Harrisův detektor rohů – odvození. Doprovodný text k předmětu 33PVR, 2007. URL http://cmp.felk.cvut.cz/cmp/courses/PVR/2007/LabsZ/docs/ harris.pdf [17] Zhang, Z.: Flexible Camera Calibration by Viewing a Plane from Unknown Orientations. In ICCV99, 1999, s. 666–673.

58

Přílohy

59

A. Obsah přiloženého CD Nedílnou součástí této diplomové práce je přiložené CD, které obsahuje: • elektronickou verzi této diplomové práce, • veškeré zdrojové soubory programu pro MATLAB, • data z provedených experimentů a • vstupní i výstupní experimentální videa.

60

Odhad vzdálenosti překážek od automobilu ze sekvence obrazů

Recommend Documents