CENTER FOR MACHINE PERCEPTION CZECH TECHNICAL UNIVERSITY DOKTORSKÁ DIZERTACE Verifikace a zpřesnění lokálních modelů povrchu pro geometrickou stereorekonstrukci Vít Zýka [email protected]únor 2003 Lze získat na ftp://cmp.felk.cvut.cz/pub/cmp/articles/zyka/zyka-phd.pdf Školitel: Prof. Ing. Václav Chalupa, DrSc., Školitel specialista: Ing. Radim Šára, Dr. Tech. Autor byl podpořen finančním příspěvkem Ministerstva školství mládeže a tělovýchovy v rámci podpory projektu výzkumu a vývoje LN00B096. Centrum strojového vnímání, Katedra kybernetiky Fakulta elektrotechnická ČVUT Technická 2, 16627 Praha 6 fax: (02) 2435 7385, tel: (02) 2435 7637, www: http://cmp.felk.cvut.cz
Verifikace a zpřesnění lokálních modelů povrchupro geometrickou stereorekonstrukci
Vít Zýka
disertační prácek získání akademického titulu doktor, ve zkratce Ph.D.
únor 2003
školitel: Prof. Ing. Václav Chalupa, DrSc.školitel specialista: Ing. Radim Šára, Dr. Tech.
České vysoké učení technické, Fakulta elektrotechnickáKatedra kybernetiky, Centrum Strojového vnímáníTechnická 2, 166 27 Praha 6, Česká republika
Abstract
This work deals with the automatic reconstruction of geometric surface model of anunknown 3D object from several 2D images. The reconstruction task can be dividedinto two principal stages. In the first stage the position of the 3D object points isreconstructed. This recovers the dimension which was lost during the projection.The output of this stage is a set of unorganized 3D points without a neighbourhoodrelation which approximate the surface. This representation is still insufficient formeasurement and visualisation. In the second reconstruction stage the global surfacemodel is recovered. The model consists of a set of 3D vertices and the neighbourhoodrelation.One way of proceeding from the isolated points to the global surface is using
the Fish-Scale Model. Every fish-scale can be imagined as a disk, whose principalplane approximates the surface. The fish-scale is reconstructed by statistical pointapproximation in a certain volume of space.This work focuses on the fish-scale surface model, mainly on the methods of
verification and refinement. The verification is a decision whether the model is oris not consistent with a given set of images. The refinement is an optimization taskmaximizing consistency statistics based on the re-projection of the model to imagesand on the calculation of image value correlation. To this end, four different types ofarea correlation statistics are suggested. The necessary conditions are derived thatallow the verification and refinement tasks, including the minimum required numberof images.Next, the verification procedure is demonstrated on a multi-scale reconstruction
of the fish-scale model that adapts to local surface curvature. The current algo-rithm was only able to recover models consisting of single-size fish-scales. Both newmethods, the verification and the refinement, are experimentally validated by ana-lyzing their behaviour on a planar object. Finally, the results of reconstruction ofreal complex scenes are shown.
3
Resumé
Práce se zabývá automatickou rekonstrukcí geometrického modelu povrchu nezná-mého třírozměrného (3D) objektu z několika dvourozměrných obrazů. Úloha re-konstrukce povrchu může být rozdělena do dvou základních fází. V první fázi serekonstruuje 3D poloha bodů scény. Obnovuje se tak znalost, která se ztratila pro-jekcí scény do obrazů. Výsledkem první fáze je velké množství izolovaných 3D bodůbez explicitní relace sousednosti. Tato reprezentace povrchu ještě není vhodná proúčely měření a vizualizace. Ve druhé fázi rekonstrukce povrchu se vytváří z množinyizolovaných bodů globální model povrchu. Takový model se skládá z vrcholů a relacesousednosti.Jeden ze způsobů, jak přejít od množiny izolovaných 3D bodů ke globálnímu
modelu povrchu, je použití šupinového modelu. Každou šupinu si můžeme předsta-vit jako disk, jehož hlavní rovina aproximuje povrch. Šupina vznikne statistickouaproximací bodů v jistém objemu prostoru.Tato práce se zaměřuje na šupinový model povrchu, zejména na návrh metody
jeho verifikace a zpřesnění. Verifikací je nazýváno rozhodnutí, zda šupina je nebo neníkonzistentní s obrazy. Zpřesnění parametrů šupin je optimalizační úloha maximali-zující konzistenci a je založené na reprojekci modelu do obrazů a vzájemné korelaciobrazových hodnot. Pro tento účel jsou navrženy čtyři statistiky konzistence. Dálejsou teoreticky odvozeny podmínky, za kterých jsou verifikace a zpřesnění možné,včetně minimálního nutného počtu obrazů.Využití verifikační procedury je demonstrováno na víceměřítkové rekonstrukci šu-
pinového modelu, který se adaptuje na lokální křivost povrchu. Dosavadní algoritmytotiž umožňovaly generovat šupiny jen jedné zvolené velikosti. Obě nové metody, jakverifikace, tak zpřesnění šupin, jsou experimentálně ověřeny analýzou chování při re-konstrukci rovinné desky. Výsledky jsou demonstrovány na rekonstrukcích složitýchreálných scén.
5
Poděkování
Především bych chtěl poděkovat mému školiteli specialistovi Dr. Radimu Šároviza neúnavné a obětavé vedení po celou dobu mého doktorského studia. Bez jehoobrovské trpělivosti a pevného přesvědčení o smysluplnosti této práce bych ji stěžídokončil.Dále děkuji prof. Ing. Václavu Hlaváčovi, CSc., Ing. Tomáši Wernerovi, Ph.D.
a Mgr. Ondřeji Drbohlavovi za pečlivé pročtení rukopisu, upozornění na některéobsahové nesprávnosti a za připomínky vedoucí k vyšší srozumitelnosti textu. Zakonzultace v oblasti statistiky děkuji doc. Ing. Mirko Navarovi, DrSc. a Dr. RNDr.Janě Noskové. Za návrh a realizaci snímacího čtyřkamerového zařízení děkuji Ing.Vladimíru Smutnému. Rád bych také na tomto místě jmenoval dva své nejbližšíspolupracovníky Ing. Pavla Krska, Ph.D. a Ing. Martina Urbana, Ph.D. a poděkovaljim za drobné, ale časté rady technického i odborného charakteru.Závěrem bych chtěl poděkovat vedení Centra počítačového vnímání řízenému
prof. Ing. Václavem Hlaváčem, CSc. za vydatnou podporu, RNDr. Evě Matyskové zavýrazné odstínění od byrokratické práce, Ing. Danielu Večerkovi za instalaci, údržbua aktualizaci počítačové sítě a veškerého výpočetního softwaru a všem kolegům zavýborné a inspirující podmínky pro studium.
Funkce označuji malým antikvovým písmenem, např. f. Pro zobrazení volím malářecká písmena. Proměnné označuji písmenem matematické italiky, např. i nebo q.Vektory označuji malým tučným groteskem (souřadnice bodu třírozměrného objek-tového prostoru x a dvourozměrného obrazového prostoru u). Matice, jejíž triviálnímpříkladem je jednotková matice E, značím verzálkovým tučným groteskem. Definičníobory, jako obor reálných R nebo přirozených N čísel, značím velkým písmenemo dvou tazích. Kaligrafická písmena používám pro pojmenování množin (množinabodů povrchu S).Výčet prvků množiny uzavírám do složených závorek, např. 1, 2, 3. Hranaté
závorky užívám pro sestavování matic a vektorů. Implicitně jde o sloupcový vektor,řádkový zapisuji pomocí transpozice. Např. bod X má souřadnice x = [x y z]T.
Potřebuju-li indexovat body, používám index i = 1, . . . , n, pro obrazy použí-vám indexu j = 1, . . . ,m.
10
1 Úvod
Rekonstrukce tvaru povrchu třírozměrných objektů nalézá stále větší uplatnění v ob-lastech průmyslové výroby (zpětné inženýrství, manipulace s předměty, defektosko-pie), průzkumu (pohyb v nebezpečných či špatně přístupných prostorách), medicíny(výroba protéz), kriminalistiky (identifikace osob), muzejnictví a restaurátorství (do-kumentace objektů), stavebnictví (architektonické návrhy staveb), e-obchodu (inter-aktivní vizualizace) i zábavy (filmové animace, hry). Cílem je rekonstruovat povrchpokud možno automaticky, protože alternativní manuální způsob pořizování digi-tálních modelů povrchu je velmi zdlouhavý, v mnoha případech nepřesný a někdyi nemožný. O výhodách digitální reprezentace dat dnes není pochyb; dávají možnostprovádět složité analýzy, simulace a vizualizace.Rekonstrukce povrchu z obrazových dat patří mezi složité úlohy. Technicky jde Obtížnost rekonstrukce
o získání popisu 3D objektu z jeho 2D projekce, viz obr. 1.1. Projekcí ztrácímejednu prostorovou souřadnici, takže zpětná rekonstrukce objektu z jednoho obrazuje obecně nemožná. Obrazů potřebujeme více, a přesto nemusí být rekonstrukce jed-noznačná. Často vidíme z jednoho pozorovacího místa jen část povrchu a musímeřešit problém skládání dílčích rekonstrukcí. Tyto díly se mohou zakrývat a mohouobsahovat díry. Mezi povrchy může navzájem docházet k interreflexím. Další dimenzisložitosti přidávají vržené stíny. Povrch může být hladký nebo drsný, pokrytý pra-videlnou či pseudonáhodnou texturou, nebo naopak nemusí být pozorována žádnátextura.Tyto vlastnosti nám z hlediska lidského vnímání světa nepřipadají příliš proble-
matické. Náš mozek také přijímá dvourozměrnou informaci o třírozměrném světě apřesto nám nečiní problémy jeho tři rozměry vnímat. Je to tím, že jednotlivé objekty
Obrázek 1.1 Příklad rekonstrukce obličeje. Vidíme dva ze čtyř vstupních obrazů a dva pohledy na rekonstruovanýmodel s nanesenou texturou z pátého barevného obrazu. Příklad pochází z projektu mezi Centrem strojového vnímánía Department of Psychiatry na University of Pennsylvania.
11
1 Úvod
ihned interpretujeme s přispěním naší znalosti předmětů, jejich funkcí a fyzikálníchzákonů. Tato zkušenost činí úlohu relativně snadnou. Počítač, který by dovedl vyu-žít obecnou zkušenost o reálném světě k interpretaci scény na podobné úrovni jakodokáže člověk, zatím neexistuje. Proto máme dvě krajní možnosti. Buď zúžit třídurekonstruovaných objektů a využít této znalosti v algoritmech rekonstrukce neboalternativně připustíme rekonstrukci obecných předmětů, ale budeme se muset přirekonstrukci obejít bez jejich interpretace. Touto druhou možností se zabývá tatopráce.Složitost úlohy rekonstrukce ji předurčuje k tomu, aby tato úloha byla dekom-Kontrola každé fáze
rekonstrukce ponována na jednodušší fáze. Každou fázi pak řešíme samostatně. Je výhodné, kdyžmůžeme dílčí výsledky omezit nějakými předpoklady, které garantují určitou správ-nost výsledku. V duchu této úvahy chceme (rozuměj já a můj školitel), aby každáfáze rekonstrukce byla zakončena verifikační či zpřesňovací částí. Od začlenění tétokontroly si slibujeme včasné potlačení chyb. Výsledkem je zjednodušení následujícíhokroku rekonstrukce a celkově přesnější tvar získaného povrchu.Tato práce navazuje na dlouhodobý výzkumný směr mého školitele specialisty
Dr. Radima Šáry v oblasti rekonstrukce obecných 3D povrchů geometrickým ste-reem. Jeho přístup lze rozdělit do tří fází:1. Nalezení korespondencí v páru obrazů a z nich vypočítání mraku 3D bodů.2. Vytvoření souboru lokálních modelů (tzv. šupin).3. Vybudování konzistentního popisu povrchu ve formě triangulované sítě.V duchu úvahy o kontrole vytvořených dat po každé fázi rekonstrukce se v této diser-tační práci zabývám nalezením verifikační procedury a zpřesněním druhé fáze taktopojaté rekonstrukce povrchu, viz obr. 1.2. Verifikace první fáze spočívá v reprojekcivšech bodů (získaných sloučením ze všech stereopárů) zpět do obrazů. Tyto projekcejsou považovány za korespondenční hypotézy, na kterých je opět použit stereokore-
Obrazy
1. fáze: stereo
3D body
Verifikace 1. fáze
Verifikované body
2. fáze: lokální analýza
Primární šupiny
Verifikace a zpřesnění 2. fáze
Verifikované šupiny
3. fáze: vytvoření topologieSít
Verifikace 3. fáze
Verifikovaná síť
Obrázek 1.2 Rekonstrukce podle Šáry.Červeně je vyznačena oblast, které se vě-nuje tato práce.
100 200 300 400 500 600
Obrázek 1.3 Příklad šupinového modelu.Každá šupina je zobrazena ve tvaru disku.Její barva odpovídá počtu bodů, ze kterýchvznikla.
12
Motivace 1.1
spondenční algoritmus. Získané body z tohoto druhého průchodu stereem jsou ještěověřovány na variační chybu ve směru osy určující vzdálenost od kamer. Zatímcotato kontrola pracuje s izolovanými body, verifikace druhé fáze rekonstrukce budemoci využít lokální modely se znalostí jejich orientace.
1.1 Motivace
Tato práce zkoumá možnosti kontroly mezivýsledků po druhé ze tří hlavních fázírekonstrukce 3D povrchu metodou zdola nahoru podle Šáry [61]. Zabývá se tzv.šupinovým modelem povrchu. Šupinový model si můžeme představit jako soubormalých lokálních částic – šupin – ve tvaru disku, viz obr. 1.3. Každý model svýmiparametry popisuje geometrické vlastnosti okolí nějakého bodu na povrchu objektu.Vznikl statistickým proložením bodů z 1. fáze rekonstrukce. Podrobněji si šupinovýmodel popíšeme v kapitole 3.1.Kromě obecného předpokladu o užitečnosti každé dílčí kontroly byla naší moti-
vací k verifikaci a zpřesnění lokálních modelů i reálná pozorování. Občas se stalo,že vygenerované modely se odchylovaly od reálného povrchu. Tyto odchylky bylomožné rozdělit do dvou skupin:
• Topologické.• Geometrické.Geometrické odchylky jsou méně nápadné. Jde o vychýlení lokálního modelu v po-loze a orientaci nebo přesahy na okrajích povrchu. Výraznější geometrická odchylkamůže vést ke změně topologie povrchu. Např. může vzniknout na povrchu nereálnádíra nebo smyčka. Geometrické odchylky vedou k méně přesné rekonstrukci. To-pologické deformace mohou ve třetí fázi rekonstrukce způsobit zcela neočekávanévýsledky (např. rekonstruovaný model bude zabalen ještě jedním povrchem). Kezměně topologie může dojít i tím, že se skutečné díry povrchu zacelí. K tomuto jevučasto dochází vlivem nedostatečného rozlišení vstupních obrazů. V takovém případějde o generalizaci povrchu nutně spojenou s vytvářením modelu reálného povrchu,a proto se jí v této práci nebudeme zabývat. Předpokládáme, že uživatel přizpůsobilrozlišení vstupního zařízení žádané přesnosti rekonstrukce.Na obr. 1.4 a 1.5 jsou příklady topologických a geometrických deformací modelu
rovinného čtvercového objektu. K dosažení konzistence modelu s objektem by zřejmě
a) Díra posunutím šupiny. b) Díra náklonem šupiny. c) Díry a Möbiův pruhnáklonem šupin.
d) Díra nereálnýmišupinami.
Obrázek 1.4 Topologické deformace. Příklady změn topologické struktury rovinné plochy zobrazené pomocí šupin.
bylo třeba některé lokální modely na obrázcích 1.4a–1.4c a 1.5a posunout, či pootočita některé na obr. 1.4d a 1.5b vyloučit.Cílem mé práce je prozkoumat způsoby, jak detekovat nebo zpřesnit geometricky
a topologicky deformované lokální modely. Výzkum jsem zaměřil na ty metody, kterévyužívají jen intenzitní obrazy. Toto omezení má své opodstatnění. Rekonstrukcez intenzitních obrazů je metoda relativně dostupná a nenákladná. Na druhé straněje ve výsledcích značné procento chyb, zvláště uvažujeme-li rekonstrukci geometric-kým stereem. Toto procento bychom rádi snížili ovšem bez zbytečného prodražovánívyužitím jiného typu senzoru.Pokud se podaří najít spolehlivou metodu, jak zpřesnit geometrii a topologii
lokálních modelů, zlepší se i přímo přesnost výsledné rekonstrukce. Detekce defor-movaných modelů se může využít dvojím způsobem. Jednak můžeme deformovanémodely ze souboru vyloučit. Využijeme při tom pozorování, že navazující krokyrekonstrukce (budující topologickou strukturu povrchu) se snáze vyrovnávají s chy-bějícím elementem než s elementem posunutým nebo chybně natočeným. Za druhémůžeme tyto chybně umístěné či posunuté modely označit a jejich konzistenci ře-šit poloautomaticky s asistencí uživatele. Usnadní se tak a zpřesní další fáze 3Drekonstrukce povrchu.
1.2 Struktura práce
V následující kapitole 2 shrnuji stav vědění v oblasti rekonstrukce 3D modelu z in-tenzitních obrazů. Také zde upřesňuji některé pojmy, se kterými budu dále pracovat,jako je kamera, obraz a model povrchu. V kapitole 3 se zaměřím na způsob rekon-strukce povrchu pomocí šupin a formuluji úlohy, které na takovém modelu můžemeřešit. Cíle této disertační práce jsou uvedeny v kapitole 4. V kapitole 5 tyto cíleformalizuji a navrhuji jejich řešení. Reálné chování teoreticky navržených postupůdemonstruji v kapitole 6 věnované experimentům. Praktické využití navržených me-tod na reálných rekonstrukčních úlohách jsou ilustrovány v kapitole 7. Výsledkypráce shrnuji v kapitole 8 a diskutuji další možné pokračování výzkumu.
14
2 Stav vědění v oblasti rekonstrukce modelu povrchu3D objektu z intenzitních obrazů
Nazvěme část reálného světa, který pozoruje pozorovatel, scénou. Entity ve scéně, Scéna, objekt
a obrazkteré zajímají pozorovatele, nazvěme (reálnými) objekty. Zbylou část scény nazvěmepozadím. Zobrazení scény do zvoleného obrazového prostoru označme pozorováníma jeho činitelem je pozorovatel. Výsledkem pozorování je obraz.Rozhlížíme-li se po světě, který nás obklopuje, vytváří se na sítnici našeho oka
obraz. Zkusme udělat následující experiment: Najdeme si nějakou neznámou scénu,se kterou dosud nemáme zkušenost1 a pohlédneme na ní jedním okem. Co uvidíme?
Objekt
Pozorování
Obraz
Rekonstrukce
Model
Nejprve asi jen jakési různobarevné plochy, které nebudeme schopni hned interpreto-vat. Víme, že pocházejí z předmětů ležících ve směru daným polohou ploch v obraze,a tušíme, že na jejich barvu mají vliv vlastnosti povrchu a způsob osvětlení.Při pohledu jedním okem bude velmi obtížné určit, co je v obraze od nás blíže a
co dále. Trochu nám pomůže, pokud se některé předměty překrývají nebo na sebevrhají stíny. Pokud bychom místo na neznámou scénu pohlédli jedním okem na scénuznámou, třeba na náš pokoj, pravděpodobně bychom prostorový vjem neztratili. Jeto tím, že bychom využívali apriorní informaci. Je dána našimi zkušenostmi; můžejít o znalost tvaru předmětů, jejich funkčnost nebo vzájemné proporce. Je-li takováinformace k dispozici, je vždy výhodné ji využít. Pochopení scény se výrazně usnadní.Pokud však taková apriorní informace k dispozici není (vrátíme se zpět k ne- Model
známé scéně), musíme si pomoci jinak. Třeba tak, že odkryjeme druhé oko. Ačkolivv jednotlivém obrazu z každého oka nedošlo k žádné kvalitativní změně, oba dohro-mady výrazně zlepší prostorové vnímání scény. Čím je to způsobeno? Náš mozekdokázal vytvořit – zrekonstruovat – z obou obrazů a nastřádaných apriorních infor-mací model pozorovaného světa. Jde o složitou a ne zcela probádanou schopnostnašeho mozku [41, 8].Vědní obor třírozměrné (3D) počítačové vidění se inspiroval takovou schopností
lidského mozku a hledá metody, jak automaticky získat model 3D objektů z dvou-rozměrných (2D) obrazů. Abychom mohli neznámý model z obrazů rekonstruovat,musíme vědět, jak obrazy vznikly. Proto si nejprve popíšeme pořízení obrazu pozo-rovatelem a teprve pak se budeme zabývat metodami třírozměrné rekonstrukce.
2.1 Pořízení obrazu
2.1.1 Geometrický model kamery
Obrazy 3D scény snímáme kamerou. V naší práci bude modelem kamery svazekpaprsků (obr. 2.1). Každému bodu scény x odpovídá jeden paprsek. Tento paprsekprotíná obrazovou rovinu v obrazovém bodě u. Paprsek p můžeme popsat bodem c
a směrovým vektorem v násobeným koeficientem a ∈ R
p = c+ a v . (2.1)
1Pojmem neznámá scéna nemyslíme neznámé rozmístění známých předmětů, ale rozmístění před-mětů, které neznáme. Najít takovou scénu je obtížné. Můžeme si však pomoci něčím, co másložitou strukturu, kterou běžně vnímáme jako celek. Poslouží třeba rozvětvená koruna stromunebo pokojová květina s množstvím listů.
15
2 Stav vědění v oblasti rekonstrukce modelu povrchu 3D objektuz intenzitních obrazů
Obraz
Objekt
Optická osa
Obrazová rovina
Střed
Obrázek 2.1 Příkladem modelu ka-mery je dírková komora neboli Ca-mera Obscura Leonarda da Vinci.Paprsky procházejí od objektu dír-kou stanovující polohu optickéhostředu. Obraz vzniká dopadem pa-prsku na obrazovou rovinu.
cx
cy
cz ≡ optická osa
x
y
zX
cxcy
cz
x
y
z
Ot,RC
Obrázek 2.2 Projekce světovéhosouřadnicového systému do kame-rového. Bod X o světových souřad-nicích x = [x, y, z] má v kamerovémsystému souřadnice cx = [cx, cy, cz].Převod je dán translačním vektoremt mezi počátky a rotační maticí R.
Takovému paprskovému modelu vyhovuje většina reálných kamer. Nejčastějším pří-Centrální projekce
kladem je kamera s centrální projekcí (také perspektivní) obr. 2.3a [29, 66]. Zavedeme-li souřadný systém tak, že jeho počátek položíme do bodu C o souřadnicích c, paklze paprsek snadno vyjádřit v homogenních souřadnicích. Paprsek p euklidovskéhoprostoru R3 bude bodem x projektivního prostoru P3. Pokud dále otočíme souřadnýsystém tak, že jedna osa bude rovnoběžná s optickou osou kamery (obr. 2.2), mů-žeme centrální projekci objektového bodu x do obrazového bodu u zapsat maticovourovnicí perspektivní kamery
u =M x . (2.2)
Matici M ∈ M 3×4 nazýváme projekční maticí sdružující jak vnější, tak vnitřní para-metry kamery. Nalezení koeficientů projekční matice nazýváme kalibrací kamery [66].Pokud jsou všechny prvky této matice známé, říkáme, že kamera je (úplně) kalibro-vaná.Speciálním případem centrální projekce je projekce paralelní (ortografická), kdeParalelní projekce
jsou všechny paprsky rovnoběžné. (obr. 2.3b) [29]. Tento případ nastane, položíme-li střed promítání centrální projekce do nekonečna. V takovém případě je zbytečnézavádět homogenní souřadnice a rovnici afinní kamery vyjádříme v euklidovskýchsouřadnicích vztahem
u = A x . (2.3)
kde A ∈ M 2×3 je afinní matice.Dvě kamery jsou svázány epipolární podmínkou [48, 29]. Ta říká, že ke zvolenémuEpipolární geometrie
bodu uA v obraze Amůže ležet jeho korespondující bod uB pouze na přímce obrazu B.Tato přímka je průnikem obrazové roviny a epipolární roviny. Epipolární rovinu de-finují optické středy obou kamer a jeden paprsek. Jsou-li obě kamery zkalibrovány,lze epipolární podmínku vyjádřit rovnicí kB = F uA, kde zobrazení F : P2 → P jetzv. fundamentální matice F ∈ M 3×3 a k je přímka v homogenních souřadnicích.
16
Pořízení obrazu 2.1
cx
cy
cz
vu
J
X
U
Fcxcy
cz
u0 v0u
v
Cf
a) Centrální projekce
cx
cy
cz
vu
JX
U
F
cz
u0 v0u
v
b) Paralelní projekce
Obrázek 2.3 Centrální a paralelní pro-jekce. a) Reálný třírozměrný bod X sepromítá do obrazového bodu U . Všim-něme si, že tento obrázek je ekvivalentnís obrázkem dírkové komory 2.1, pouzeobrazová rovina je, bez újmy na obec-nosti, přemístěna dle středové souměr-nosti do objektového poloprostoru. Směrobrazových os odpovídá zavedeným kon-vencím – u označuje řádky shora dolů av sloupce zleva doprava, osa vzdálenostiz směřuje od pozorovatele a celá sou-stava je pravotočivá. b) Paralelní pro-jekce vznikne z centrální posunutím oh-niska do nekonečna. Paprsky pak smě-řují rovnoběžně s optickou osou.
2.1.2 Fotometrický model kamery
Fotometrickým modelem kamery se zabývá radiometrie. Hodnota obrazové funkce izávisí na (i) osvětlení pozorovaného elementu povrchu L, (ii) odrazivostním vlast-nostem povrchu a (iii) vzájemné geometrii osvětlení l, normály povrchu n a senzoru x
i = f(L, l,n, x) . (2.4)
Funkce f se nazývá dvousměrová funkce odrazivosti (bidirectonal reflectance dis-tribution function, BRDF) [37] a zahrnuje příspěvek dvou složek odrazu: difuzní aspekulární. Pokud je spekulární složka nevýrazná, lze ji zanedbat. Nezávisí-li navícodraz na poloze pozorovatele, říkáme, že povrch je lambertovský [43]. Fyzikálnímrozměrem hodnoty obrazové funkce, kterou nepřesně nazýváme intenzita jasu nebojas, je [cd srm−2].Protože je velikost senzoru kamery konečná, musíme počítat příspěvky celého
elementu povrchu do prostorového úhlu daného elementem senzoru [36]. Pro účelytéto práce však použijeme zjednodušující paprskový přístup, který předpokládá bo-dový senzor, bodový element povrchu a bodový zdroj světla.
2.1.3 Obraz
Obrazem nazýváme funkci I(u, v). Parametry u a v označují definiční obor R2 sou-řadnic obrazu a hodnotou funkce je osvětlení [66]. Digitální obraz vznikne diskretizací Digitální obraz
spojitého obrazu na pixely o souřadnicích v oboru hodnot D2, kde D ⊂ N, a kvan-tizací obrazových hodnot do oboru V, kde V ⊂ N. Nejčastěji se používá pravidelnápravoúhlá souřadnicová síť s celočíselnými funkčními hodnotami v intervalu 〈0,255〉.Takový digitální obraz popíšeme maticí
I =
[I(1, 1) · · ·· · · I(M,N)
], (2.5)
kde M je počet obrazových řádků a N počet sloupců.
17
2 Stav vědění v oblasti rekonstrukce modelu povrchu 3D objektuz intenzitních obrazů
2.2 Rekonstrukce modelu povrchu 3D objektu
Rekonstrukci modelu povrchu 3D objektu z intenzitních obrazů můžeme rozdělit dodvou základních fází:1. Vytvoření množiny (mraku) 3D bodů z množiny intenzitních obrazů.2. Vytvoření simplexové sítě z množiny 3D bodů.Tři fáze rekonstrukce podle Šáry [61] uvedené v kapitole 1 jsou speciálním případemtohoto dělení. První fáze se shodují. Zde uvedená druhá fáze zahrnuje druhou atřetí fázi postupu podle Šáry. Dříve než se zaměříme na obě fáze, je nutné popsat sidatové reprezentace třírozměrného povrchu.
2.2.1 Modely povrchu 3D objektů
Podívejme se na známé reprezentace globálních i lokálních modelů povrchu. Vodít-kem nám k tomu bude diagram na obrázku 2.4. Zobrazuje jednotlivé modely a jejichvzájemné transformace. V horních třech čtvrtinách diagramu jsou modely, kte-rými se převážně zabývá obor počítačové vidění. Většina z nich je dočasná, sloužícípouze jako mezikrok rekonstrukce. Cílové reprezentace (např. sítě) přebírají apli-kační obory jako počítačová grafika, robotika, prostorová analytika ap. Modely jsoushora setříděny podle jejich autonomie na lokální (bodové), pololokální a globální.Vidíme, že pro aplikační sféru jsou potřeba téměř vždy modely globální. Hlavnímdůvodem je, že tyto modely obsahují topologickou informaci.
Charakterizujme si postupně jednotlivé povrchové modely.Neorganizované body. Lokální model tvořený vybranými body povrchu [51, 35, 21,60]. Poloha každého neorganizovaného bodu ve R3 je určena prostorovými sou-řadnicemi [x y z]T. Souřadnice bodů jsou libovolné, nemusí být součástí nějaképravidelné mřížky. Povrch popsaný neorganizovanými body se vyznačuje velkýmobjemem dat, často se mluví o mraku bodů. Typickým zdrojem neorganizova-ných bodů je geometrické stereo.
Organizované body. Povrch je popsán třemi souřadnicemi podobně jako v případněneorganizovaných bodů. V tomto případě je známá sousednost bodů, tzn. že prokaždý bod známe množinu bodů z jeho okolí. Zdrojem organizovaných bodů jenapř. hloubkoměr se strukturovaným světlem [53] nebo izoplochy z tomografů.
Neorganizovaná primitiva. Jde o soubor lokálních modelů popisujících polohu, ori-entaci, eventuálně tvar lokálního místa povrchu. Výhodou této reprezentace jevýrazně nižší objem dat při nevelkém snížení geometrické přesnosti. Významnáje znalost orientace modelu.Příkladem pololokálních primitiv jsou orientované částice [70, 21]. Každou ori-entovanou částici si můžeme představit jako kruh, jehož střed leží na povrchu aorientace je shodná s tečnou rovinou povrchu v tomto bodě. Definuje jej dvojiceci,ni, kde ci = [x y z]T značí polohu středu částice a normálový vektor ni
udává její orientaci. Orientované částice umožňují modelovat spojitý hladký po-vrch libovolného tvaru (vyjma fraktálů) a topologie. Tyto lokální modely bylypoužity k modelování dynamických jevů, jakými jsou spojování a průniky tě-les [47].Jiným příkladem pololokálních primitiv je šupinový model [64]. Tato reprezen-tace bude podrobně popsána v kapitole 3.1.
Primitiva v hierarchickém uspořádání. Jde o stejný popis povrchu jako v případěpololokálních primitiv, jen existuje několik vrstev v závislosti na generalizacipovrchu. Je známá hierarchická vazba mezi primitivy ze sousedních vrstev. Tato
Obrázek 2.4 Modely povrchu pro rekonstrukci 3D objektů z bodové množiny. V hranatézávorce jsou uvedeny citace prací, které navrhují přechod z jednoho modelu do druhého.
19
2 Stav vědění v oblasti rekonstrukce modelu povrchu 3D objektuz intenzitních obrazů
reprezentace je užitečná při generování povrchů s různým rozlišením (level-of-detail) [17].
Deformovatelné modely. Jde o skupinu povrchových modelů, jejichž tvar se dásnadno měnit [69, 24, 34, 11, 45, 18, 57, 9, 50, 15]. Povrchem může být funkcehloubky, superkvadrika. V praxi jím nejčastěji bývá konečný počet diskrétníchelementů, např. triangulace nebo simplexová síť. Deformovatelné modely jsouúzce svázány s rekonstrukcí shora dolů, viz kapitolu 2.2.3. Je-li např. cílem defor-mačního funkcionálu přimknout se ke vstupním bodům a zároveň minimalizovatplochu povrchu, jde o minimální povrch [9].
Model s logickými operacemi. Snaha o popis komplexnějších modelů a překonánírigidnosti deformačních modelů při potřebě změnit topologickou strukturu vedlaněkteré autory ke slučování jednodušších modelů logickými operacemi [46, 44].Tento postup je velmi náročný, a proto není vhodný na modelování obecných po-vrchů. Možná by mohl být využitelný jako dočasný vnitřní popis při dynamickémmodelování.
Sítě. Síť můžeme vyjádřit matematickou strukturou zvanou simplexový komplex.Simplexový komplex je konečná množina simplexů s těmito dvěma vlastnostmi:(i) Každá stěna libovolného simplexu je také simplexem tohoto komplexu. Dále,(ii) mají-li dva simplexy neprázdný průnik, pak jejich průnikem je stěna obousimplexů. Simplex je geometrická struktura definovaná jako konvexní obal k+1afinně nezávislých bodů. Podle toho počtu bodů v Rn mluvíme o k-simplexu(k ≤ n). Řád k-komplexu je dán řádem nejvyššího obsaženého simplexu. Např.v R3 je čtyřstěn 3-simplex, trojúhelník 2-simplex, úsečka 1-simplex a bod 0--simplex. V našem případě při popisu 2D povrchu 3D objektu jsou podstatnésimplexy druhého a nižšího řádu. Síť, která vznikne z 1-simplexů simplexovéhokomplexu se nazývá simplexová síť [23, str. 243–292].
Speciálním případem komplexu je pseudomanifold [1]. Je to k-komplex, pro kterýdále platí: (i) každá jeho k−1-stěna je obsažena v právě dvou k-stěnách komplexua (ii) duální graf nad k-stěnami komplexu je souvislý. Pokud jsou všechny prvkysubdivize komplexu simplexem, jde o triangulaci [23, str. 297–298].
Pomocí sítí dokážeme vyjádřit jakékoliv topologické struktury, a to s libovolnýmrozlišením a přesností. Struktura je paměťově úsporná. Proto jsou sítě velmi ob-líbeným popisem povrchu. Často slouží jako trvalá datová reprezentace povrchu3D objektu a je zdrojem dat pro výstupní aplikace.
Generalizující hierarchický model. Je o síť, na kterou lze snadno aplikovat operacerozděl vrchol a kontrahuj hranu. Cílem těchto modelů povrchu je snadné gene-rování povrchů v různém rozlišení a s různým stupněm generalizace. Příklademtakové struktury je progresivní síť (progressive mesh) [32, 33]. Při požadavku mo-delu určité stupně generalizace se testuje, zda je potřebné užít jednu z uvedenýchoperací, a zda je tato operace přípustná.
Hladký model. Jde o model povrchu se spojitými derivacemi. I zde modelujemeglobální povrch po částech (plátech), ale ne částmi rovin jako ve většině před-chozích případů. Využíváme ploch druhého nebo vyššího řádu.
Příkladem jsou NURBS (NonUniform Rational B-Spline). Jejich tvar je dán ří-dicími body. Pomocí vhodně zvolených hraničních podmínek jednotlivých částílze zajistit jak hladkost celku, tak nespojitost první i druhé derivace (hrana aroh). Body každé části NURBS jsou částí konvexního obalu řídicích bodů.
20
Rekonstrukce modelu povrchu 3D objektu 2.2
Jedna část NURBS je definována pomocí Bersteinova polynomu
Bi,n(u) =
(n
i
)ui(1− u)n−i
jako
S(u, v) =n∑
i=0
m∑j=0
Ri,j(u, v)Pi,j ,
kde Ri,j(u, v) je racionálně lomená funkce
Ri,j(u, v) =Bi,n(u)Bj,m(v)wi,j∑n
r=0
∑ms=0Br,n(u)Bs,m(v)wr,s
.
Proměnné 0 ≤ (u, v) ≤ 1 parametrizují část povrchu ohraničenou řídicími bodyP s váhami w. Počet bodů (n + 1)(m + 1) je dán řádem NURBS. Přechodemdo homogenních souřadnic projektivního prostoru můžeme odstranit lomenoufunkci. [56]NURBS je relativně úsporná reprezentace. Snadno se vizualizuje pomocí rekurze.Vytvoření NURBS povrchu z triangulace je možné, vyžaduje to však přechodk obdélníkové síti. Tento problém se snaží obejít podobná reprezentace zvanáTRI-NURBS. [27]
Použijeme-li hladkých modelů k popisu povrchu, dosáhneme vyšší přesnosti přistejné nebo nižší paměťové náročnosti. Neúměrně se však zvýší složitost rekon-strukce. Proto se téměř výhradně používají modely s rovinnou aproximací. Je-lipotřeba získat hladký povrch, třeba pro vizualizaci, budují se hladké modely ze sítíaž v cílové aplikaci. Triangulace nebo simplexová síť se tak jeví vhodnou cílovoureprezentací metod rekonstrukce povrchu.
2.2.2 Vytvoření množiny 3D bodů z intenzitních obrazů
3D body na geometrické bázi
Nejpoužívanější metodou výpočtu hloubky z intenzitních obrazů je geometrické ste-reo. Využívá rozdílných míst pozorování a triangulace korespondujících si bodů.Podmínkou je kalibrované snímací zařízení. Podle toho, zda nevyužíváme nebo vyu-žíváme strukturovaného světla, rozlišujeme stereorekonstrukci pasivní nebo aktivní.Pasivní stereo pracuje s množinou obrazů. Stěžejním problémem je nalezení tzv. Pasivní stereo
husté korespondence v obrazech [66, 61]. Znamená to najít každému pixelu kore-spondující protějšek v jiném obraze, tj. projekce stejného bodu scény, ale jen tehdy,je-li bod viditelný. Díky epipolární podmínce stačí hledat odpovídající bod v dru-hém obraze jen na přímce. Pokud obrazy podrobíme rektifikaci, tj. transformujemetak, aby měly jednu obrazovou osu společnou, je rozdíl souřadnice korespondujícíchsi bodů (disparita) nepřímo úměrný vzdálenosti.Pro výpočet vzdálenosti místa na povrchu potřebujeme minimálně dva obrazy.
Pokud ale bude ve scéně struktura orientovaná stejně jako pohyb pozorovatele mezisejmutím prvního a druhého obrazu, nebude korespondence jednoznačná. Jde o tzv.problém štěrbiny Podobná situace nastane, bude-li scéna obsahovat periodicky seopakující struktury (tvarové a texturní). V obou případech potřebujeme k určeníkorespondence alespoň tři kamery v obecné poloze. Protože se korespondence častoz výpočetního hlediska hledají po párech, vzniká z důvodu nejednoznačnosti úlohyurčité procento chybných korespondencí, a tím i chybně zrekonstruovaných bodů.
21
2 Stav vědění v oblasti rekonstrukce modelu povrchu 3D objektuz intenzitních obrazů
Ačkoliv je pasivní stereorekonstrukce velmi stará metoda a mohlo by se zdát,že vše podstatné zde bylo již objeveno, není tomu tak. Příkladem může být práceo stabilním párování [6, 62, 63]. Těžiště výzkumu se přesouvá z nalezení co nejvícekorespondencí na hledání správného kritéria pro jejich hledání. Takovým kritériemmůže být minimalizace pravděpodobnosti chyby. Běžně dosahuje poměr vychýlenýchbodů 10%.Úspěšnost hledání korespondencí v pasivním stereu značně závisí na kontrastuAktivní stereo
obrazů a intenzitě textur. Proto se někdy za účelem přesnější rekonstrukce promítána scénu umělá náhodná textura. Jinou možností je použití kalibrovaného struk-turovaného světla. Nahrazuje se jím jedna kamera ve stereopáru, takže dostávámekalibrovanou dvojici kamera-projektor. V takovém případě hovoříme o aktivním ste-reu. Promítat lze např. vzor s jednoznačně detekovatelnými body, barevnou duhuo známém spektru nebo laserovou rovinu. Zařízení, které pracuje s laserovou rovinou,se nazývá laserový hloubkoměr.Laserový hloubkoměr (laser rangefinder) používá bodový laser s válcovou čočkou,
která laserový paprsek rozmítá na svazek paprsků v rovině. Po dopadu takovéhosvazku na objekt vzniká stopa, která je deformovaná podle vzdálenosti od projek-toru a úhlu pozorování [53]. Najít laserovou stopu v obraze je nepoměrně snazší nežkorespondující si body, protože její kontrast je vysoký. Většinou jej ještě zvyšujemetím, že obraz snímáme přes filtr. Hloubku každého bodu laserové stopy pak opěturčíme triangulací jako u klasického sterea. Vzhledem k téměř nulovému výskytuvychýlených bodů, díky kterému můžeme přímo vytvářet po částech spojitou síť, jenalezení výsledné reprezentace povrchu mnohem snazší než u sterea. Touto metodouse na objektech velikosti několika decimetrů dosahuje přesnost 0,05mm i lepší. Ne-výhodou však je, že musíme nasnímat sekvenci obrazů, abychom laserovou stopoupokryli celou scénu. Laserovým hloubkoměrem proto lze rekonstruovat pouze sta-tické scény. Tato nevýhoda stejně jako nutnost svítit laserem nás v mnoha aplikacíchnutí používat pro rekonstrukci pasivní stereo.Existuje mnoho dalších metod k určení hloubky. Souhrnně se nazývají hloubka
z X. Jde o hloubku ze šilhání [42] a rozostření [55, 16], z textury [51] a obrysu [74, 40]a z pohybu [73]. Tyto metody však nemají obecné uplatnění, snad je lze použítv některých konkrétních aplikacích. Zmiňujeme je zde proto, že i na mrak bodůzískaný těmito metodami lze aplikovat zpřesnění popsané v této práci.
3D body na fotometrické bázi
Další metodou rekonstrukce je fotometrické stereo [75, 76, 30, 77]. Využívá závislostijasu na úhlu mezi osvětlením a normálou povrchu. Častými předpoklady jsou lam-bertovský povrch a bodové osvětlení v nekonečnu. Za takových podmínek můžemejas pixelu i při osvětlení j zapsat rovnicí
xij = αiλjσinTi lj + νij , (2.6)
kde α je hodnota albeda, λ ozáření, σ zaznamenává citlivost snímače a ztráty vli-vem vinětace, n je normálový vektor povrchu, l je vektor směru osvětlení a ν je šumsnímače. Bude-li systém geometricky a fotometricky kalibrovaný, můžeme scénu po-stupně osvětlit třemi světly a řešit tři takovéto rovnice o třech neznámých složkáchnormálového vektoru. Tvar povrchu za předpokladu jeho spojitosti pak získáme inte-grací normál v každém pixelu obrazu [68]. I zde existují další techniky rekonstrukce,jako je tvar ze stínování [38] a tvar z moaré [78, 28].
22
Rekonstrukce modelu povrchu 3D objektu 2.2
2.2.3 Vytvoření simplexové sítě z bodové množiny
Úlohou této druhé fáze rekonstrukce je vytvořit simplexovou síť, která dle zvolenéhokritéria vyhovuje vstupní bodové množině. V principu máme dvě možnosti, jak ur-čit vrcholy simplexové sítě. Buď ji (i) vybudujeme přímo na vstupních bodech nebo(ii) mimo vstupní body. V prvním případě bude úloha spočívat ve volbě vrcholů ahran tak, aby splňovaly definici simplexu. Ve druhém můžeme polohu vrcholů zvolita hrany snadno doplnit na jednoduché pravidelné síti. Problémy nastanou při mini-malizaci vzdálenosti sítě od vstupních bodů, protože půjde o rozsáhlou optimalizačníúlohu. Vidíme, že nám volba vytváření simplexové sítě vede na jiný způsob rekon-strukce: první na rekonstrukci zdola nahoru a druhý shora dolů. Charakterizujme sityto dva základní přístupy:Zdola nahoru. Apriorní model je implicitní, je reprezentován nutnými podmínkami(lokální spojitost a hladkost povrchu). Úloha rekonstrukce se zde formuluje jakopostupné shlukování jednodušších modelů do složitějších na základě nutnýchpodmínek. Vychází se ze vstupních bodů jako elementárních částic. Výslednýmodel musí zahrnovat topologickou strukturu rekonstruovaného objektu, napří-klad ve formě sítě.Výpočetní geometrie umožňuje vytvoření triangulované sítě nad vstupními body Výpočetní geometrie
pomocí algoritmů založených na Voronoiovu diagramu a Delaunayovy triangu-laci. Tato triangulace splňuje simplexovou podmínku. Složitost algoritmu v R3je O(n2), takže jde o polynomiální úlohu na n vstupních bodech. Tyto metodyvšak selhávají na reálné množině s vychýlenými a zašumělými body. Edelsbrun-ner proto navrhuje α tvary [13, 31]. Pojem α tvar je polyhedrální komplex, který α tvar
vznikne zobecněním konvexního obalu. Hranice povrchu je dána těmi body, kte-rých se může dotknout koule o zvoleném poloměru α, aniž by jediný bod celémnožiny vstoupil dovnitř koule. Pro α =∞ dostáváme konvexní obal. Dostávámetak celou třídu povrchů, které mohou být nekonvexní a nesouvislé, parametri-zovanou koeficientem α. Parametr α se volí experimentálně podle charakteruaplikace.Tento parametr odstraňuje Amenta [4, 3, 2] postupem vedoucím na model zvaný Krusta
krusta. Pomocí něj vytváří jednoznačný simplexový povrch bez volitelného para-metru. Zároveň definuje vzorkovací kritérium pro vstupní body. Problémy s jed-noznačností povrchu totiž nastávají, pokud je vzdálenost vzorků z povrchu menšínež vzdálenost dvou povrchů. Kritérium je založené na vzájemných vzdálenostechvzorků a vzdálenosti od středových os Voronoiovy stěny. Ve své práci dokazujemaximální poměr těchto vzdáleností, při kterých je garantován vznik simplexusprávně definující povrch. K vytvoření takového simplexového povrchu navrhlaalgoritmus tvořící krustu. Krusta je podmnožinou Delaunayovy triangulace. Z nívznikne tak, že odstraníme ty hrany, jejichž kulový obal obsahuje alespoň jedenbod vstupní množiny nebo jeden bod Voronoiova diagramu na vstupní množině.
Shora dolů. Apriorní model je explicitní (superkvadrika, síť, hladinový model) acílem je minimalizovat jeho geometrickou vzdálenost od vstupní bodové mno-žiny [69, 24, 34, 11, 45, 18, 57, 9, 50, 15]. Kritériem této optimalizace je funkce
E = Egeom + λ Edef , (2.7)
kde Egeom vyjadřuje střední geometrickou vzdálenost mraku bodů od modelu aEdef velikost deformace povrchu. Deformace se může měřit plochou povrchu, ve-likostí hlavní křivosti ap. Zásadní vliv na výsledný tvar má váhový koeficientλ. Je-li λ 1, bude se model těsně přimykat vstupním bodům, takže zachytí
23
2 Stav vědění v oblasti rekonstrukce modelu povrchu 3D objektuz intenzitních obrazů
i chyby a šum měření. Oproti tomu, když λ 1, pak ztratíme detaily po-vrchu. Optimalizace konkretizuje obecný prvotní model. Volba modelu (např.jeho topologie) má rozhodující vliv na přesnost rekonstrukce. Stupeň obecnostiprvotního modelu zase rozhoduje o rychlosti iteračního optimalizačního procesu.Ve výzkumných zprávách [11, 46] jsou navrženy způsoby změn topologie běhemoptimalizace. Kontrola, zda je změna topologie potřebná, a udržení konzistencecelého modelu při provádění změny, jsou ale postupy na sítích velmi neefektivní.Podobně neefektivní je řešení problému potlačení hran a rohů [25, 71] založenéna jejich předchozí detekci.Jinou možností je použít hladinový model (level sets) [65, 79]. Tato metoda před-Hladinový model
pokládá funkci definovanou na R3 ve tvaru φ(x, t). Vyvíjí se v místě x v čase t.Povrch je definován v bodech, kde φ(x, t) = 0. Z toho dostaneme rovnici časovéhovývoje povrchu ve tvaru
φ(x, t) +∂ φ(x, t)∂ t
· ∂ x
∂ t= 0 . (2.8)
Tím je definovaná optimalizační úloha. Pro získání triangulovaného povrchuz ustáleného řešení se nejčastěji používá metoda kráčející krychle (marching cu-bes) [49]. V ní se prostor objektů pravidelně rozdělí na krychle. Vrcholy výslednésítě se určí na základě porovnání řezu hladiny φ(x, t) = 0 skrze hrany krychles množinou všech možných vzorových řezů. Metoda hladinového modelu umož-ňuje topologické změny modelu. Pro náš případ, kdy máme na vstupu diskrétníizolované body, se mi nezdá neefektivní konstruovat spojitou funkci, abychommohli řešit rovnici (2.8). Daleko lépe se hodí tato metoda pro husté třírozměrnéúdaje, například z tomografů.
Kromě obou vyhraněných způsobů rekonstrukce se vyskytly i hybridní přístupy. Na-Hybridní přístupy
příklad Fua využil optimalizačních technik metod shora dolů na polyhedrální povrchvytvořený pomocí lokálních modelů. Optimalizace pak byla prováděna nejen na zá-kladě geometrických vlastností (vzdálenosti k bodové množině, křivost povrchu), alei využitím tvaru ze stínování [18, 20].
24
3 Lokální model povrchu
Zaměříme se nyní jen na druhou a třetí fázi rekonstrukce podle úvodní kapitoly 1.Vstupem druhé fáze je mrak 3D bodů, které považujeme za vzorky měřeného po-vrchu. Výstupem třetí fáze je povrch popsaný simplexovou sítí (kapitola 2.2.1).Vstupní bodové vzorky z povrchu jsou velmi neefektivní reprezentace. Důvodů je Neefektivita
bodové množinyněkolik: (i) jde o lokálním popis bez znalosti orientace povrchu, (ii) neznáme soused-nosti mezi body, (iii) vyskytují se mezi nimi vychýlené body (outliers), (iv) polohatěchto vzorků je zatížena šumem měření a (v) bodů bývá velké množství. Z těchtodůvodů bude výhodné pro obě metody rekonstrukce (zdola nahoru i shora dolů)vstupní body předzpracovat. Toto předzpracování zaručí:Vyloučení vychýlených bodů. Významné procento vychýlených bodů lze vyloučitze vstupní množiny dvojím způsobem: (i) verifikací omezujících podmínek a(ii) statisticky, převládají-li nevychýlené vzorky.
Filtraci šumu měření. Nahradíme-li vhodně zvolenou podmnožinu bodů její středníhodnotou (těžištěm), snížíme šum měření.
Postupnou redukci dat. Počet prvků bodové množiny snížíme tak, aby nové vzorkyzaručovaly Shannonův vzorkovací teorém vzhledem k rekonstruovaným prosto-rovým frekvencím povrchu.
Jak vidíme, všechny tyto postupy vyžadují redundantní počet vzorků povrchu. Mno-ho praktických úloh tuto podmínku splňuje, například rekonstrukce z husté kore-spondence. Předzpracování dat, které jsme v kapitole 1 uvedli jako druhou fázirekonstrukce, vede na vytvoření pomocné reprezentace povrchu, které nazveme sou-borem lokálních modelů.Lokálním modelem1 v této práci rozumíme geometrický popis části povrchu 3D Lokální model
objektu. Jde o parametrickou strukturu, jejíž parametry určují polohu a orientaciokolí bodu v prostoru. Soubor takových lokálních modelů vytváří globální reprezen-taci scény.
3.1 Šupinový model
Šupinový model je lokální reprezentací povrchu. Pro stereorekonstrukci z izolova- Definice šupiny
ných a zašumělých bodů jej navrhl Šára [64]. Mějme na definičním oboru R3 funkcipříslušnosti µ(x), která nabývá hodnot
µ(x)
= 1, pokud je x na povrchu a
< 1, jinak.(3.1)
Funkce µ(x) je definována jako vážený součet funkcí µk(x)
µ(x) =K∑
k=1
λk µk(x) , (3.2)
1Spíše než o lokálních modelech bychom měli mluvit o pololokálních modelech, protože striktněvzato lokálním popisem povrchu je bod a jeho okolí. Protože však toto slovní spojení je v této prácivelmi frekventované, rozhodli jsme se, byť trochu nepřesně, psát místo o pololokálních modelecho modelech lokálních.
25
3 Lokální model povrchu
kde
µk(x) =1√
det(2πSk)e−12 (x−x0k)
TS−1k (x−x0k) . (3.3)
Funkcím µk(x) říkáme šupiny. Každá šupina je lokálním modelem povrchu. Je po-psána dvojicí parametrů θ = x0,S:Střed modelu x0, x0 ⊂ R3 určuje polohu modelu v prostoru.Parametry šupiny
Strukturní matice modelu S, S ⊂ M 3,3 je matice hlavních směrů a popisuje orien-taci a velikost modelu.
Vlastní vektor strukturní matice náležící nejmenšímu vlastnímu číslu, dává odhadnormály povrchu n v bodě x0. Zbylé dva směry udávají hlavní rovinu, kterou bu-deme považovat za lokální lineární aproximaci povrchu ve středu šupiny x0. Někdyhovoříme o velikosti šupiny. Ačkoliv je podle definice její prostorový rozsah neko-nečný, definujeme její velikost v každém z hlavních směrů hodnotou vlastního číslastrukturní matice. Tvar šupiny popisuje hodnota daná poměrem vlastních čísel λi
strukturní matice
ρ =3∑
i=1
λi
λmax. (3.4)
Nazýváme ji řádem (rank) šupiny. Protože šupiny vznikají ze zašuměných bodů avychýlených bodů, není řád šupiny, která vznikla ze vzorků rovinného povrchu, rovnadvěma, ale je vyšší.Šupinový model lze z n vstupních bodů najít např. EM algoritmem [7]. FunkciGenerování šupin
příslušnosti vyjádříme jako podmíněnou pravděpodobnost µ(x|Θ). Najdeme takovéparametry Θ = θ1, . . . , θK , pro K šupin, které maximalizují věrohodnost L(Θ), tj.minimalizují funkcionál
E = − lnL(Θ) = −n∑
i=1
ln µ(xi|Θ) = −n∑
i=1
lnK∑
k=1
λk µk(xi|θk) . (3.5)
Tímto algoritmem dostaneme šupiny v optimální pozici, orientaci a velikosti. Velkéa ploché šupiny vznikají na rovinných částech povrchu, zatímco tam, kde je většíkřivost, je více malých šupin. Nevýhodou tohoto algoritmu je, že musíme dopředuzvolit počet šupin K.Protože je ale EM algoritmus v R3 výpočetně velmi náročný, používá se pro gene-
rování šupin v [64] pouze přibližné metody. Jedna šupina vznikne proložením bodůmetodou hledání hlavních směrů (principal component analysis) v části prostoru.Tato část vznikne pravidelným rozdělením prostoru na voxely. Velikost voxelu je pa-rametrem metody. Protože šupiny jsou generovány tak, že se jednotlivé modely pře-krývají, připomíná zobrazení povrchu pomocí eliptických plošek rybí šupiny. Odtudpramení inspirace pro pojmenování těchto lokálních modelů. Druhým parametremtéto heuristické metody je hustotní práh. Je-li počet bodů uvnitř voxelu nižší nežtento práh, šupinu negenerujeme. Tím zaručíme potlačení vychýlených bodů.
Na šupinovém modelu můžeme definovat několik základních úloh:Definice úloh
1. Verifikace konzistence šupiny (lokálního modelu) s množinou obrazů.2. Zpřesnění parametrů ve smyslu metody vyrovnání svazku paprsků.3. Rekonstrukce relace šupiny ke svým sousedům, tj. vytvoření globální topologiemodelu.
V této práci se budeme zabývat prvními dvěma úlohami.
26
Metoda vyrovnání svazku paprsků 3.2
3.2 Metoda vyrovnání svazku paprsků
Vyrovnání svazku paprsků (bundle adjustment) [72] [29, str. 423] je metoda, jak zá-roveň optimalizovat projektivní parametry kamery a polohu rekonstruovaných bodůpomocí množiny obrazů.Představme si, že je množina 3D bodů xi pozorována kamerami s projektivními
maticemi Mj . Průměty bodu i do obrazu j označme uji . Známe-li tyto průměty, pak
rekonstrukční úloha hledá takové Mj a takové body xi, které splňují rovnice
Úloha je pro projektivní kamery nejednoznačná, protože se rekonstruované bodymohou lišit o libovolnou projektivní transformaci (po příslušné transformaci kamer).Pokud počítáme s chybou měření, pak rovnice 3.6 nejsou přesně splněny. V ta-
kovém případě hledáme řešení ve smyslu maximální věrohodnosti za podmínky, žešum měření je gaussovský. Potom hledáme takové řešení rovnic Mj xi = u
ji , které
minimalizuje vzdálenost mezi promítnutými ui a měřenými ui obrazovými body
minMj ,xi
∑ij
d(Mj xi,uji )2 , (3.7)
kde d(u1,u2) je geometrická vzdálenost homogenních bodů u1 a u2. Jde o nale-zení optimálního svazku paprsků mezi každým středem kamery a množinou bodův prostoru.Řešení této optimalizační úlohy je složité, protože (i) vyžaduje dobrou počá-
teční pozici a (ii) množství optimalizovaných parametrů je veliké. Každý bod xi
přispívá k počtu parametrů třemi prostorovými souřadnicemi a každá kamera je-denácti nezávislými parametry matice Mj . To vede na faktorizaci matice rozměru(3n+ 11m)× (3n+ 11m).
3.3 Zjednodušení metody vyrovnání svazku paprsků
V současné době je rozumné hledat řešení úlohy vyrovnání svazku paprsků, jde-lipočet bodů do desítek. Bodů z husté korespondence bývá okolo sta tisíc na jedenobrazový pár. Pokud provedeme náhradu těchto bodů šupinami, dostaneme tisícestředů, které můžeme považovat za inicializační body pro metodu vyrovnání svazkupaprsků. Dokonce budou lépe vyhovovat podmínce gaussovského rozdělení, protoževzniknou z bodů všech obrazových párů, zatímco bod z jednoho páru může vykazovatsystematickou chybu kalibrace těchto dvou kamer. Na to, abychom je mohli efektivnězpřesnit metodou vyrovnání svazku paprsků, jich je však stále mnoho.Místo toho, abychom hledali řešení této rozsáhlé optimalizační úlohy, rozhodli
jsme se ji dekomponovat. V prvním kroku (i) provedeme zpřesnění kalibračníchparametrů kamer metodou vyrovnání svazku paprsků na několika málo desítkáchvybraných bodů a v kroku druhém (ii) samostatně optimalizujeme polohu všechlokálních modelů. První krok není náplní této práce, ale o jeho nezbytnosti jsmese experimentálně přesvědčili. Přesnost projektivních matic je stěžejní pro jakékolivdalší optimalizace.Tato práce se (mimo verifikace lokálních modelů) zabývá druhým krokem, tj.
optimalizací polohy lokálních modelů. Zdá se nám ale nevhodné optimalizovat pouzestředy modelů; rádi bychom využili i jeho okolí (např. orientaci a rozptyl). Budemese také muset vypořádat s problémem, že vyrovnání svazku paprsků měří chybupredikce bodů, tj. vzdálenost promítnutých bodů k predikovaným bodům obrazu.Takové obrazové body pro středy lokálních modelů zpravidla nemáme.
27
3 Lokální model povrchu
3.4 Inspirace pro zpřesnění lokálních modelů
Pro zpřesnění parametrů lokálních modelů pomocí obrazů nás inspirovala práce Pas-cala Fua [22]. Fua používá Szeliski-Tonnesenovy orientované částice [70] jako lokálnímodely, které optimalizuje minimalizací funkcionálu
E = Ecorr + λ Edef , (3.8)
kde Ecorr je funkce nazývaná jako meziobrazová korelace intenzit, Edef představujedeformační energii a λ je váhový koeficient. Meziobrazová korelace intenzit Ecorr sepočítá jako vážený součet rozptylu každé částice s indexem k
Ecorr =∑
k
Ekcorr . (3.9)
Rozptyl částice je pak součtem rozptylové funkce každého bodu xr,θ
Ekcorr =
1nk
∑r,θ
σ2(xr,θ) , (3.10)
kde r, θ parametrizují částici tak, aby promítané body rovnoměrně pokrývaly jejípovrch. Hodnota nk udává počet promítaných bodů částice k. Protože promítámedo m obrazů, je rozptylová funkce bodu x definovaná jako rozptyl jasů přes všechnyobrazové průměty
σ2(x) =1m
m∑j
(I(Mjx)− µ(x)
)2, µ(x) =
1m
m∑j
I(Mjx) . (3.11)
Deformační energie Edef klesá s hladkostí povrchu a je definována součtem dvoučlenů přes sousední páry částic
Edef =∑i,j
f(E ijcn + E ij
cp) , f(x) = log(1 + x/c) , (3.12)
kde c je volená konstanta. Hodnota E ijcn vzrůstá s úhlem mezi normálami částic i a j
E ijcn = 1− ninj (3.13)
a E ijcp roste se vzdáleností středů částic a úhly mezi normálami a spojnicí středů rij
E ijcp =
12
((nirij)
2 + (njrij)2) . (3.14)
Meziobrazová korelace jasů Ecorr, tak jak je navržena, má praktickou nevýhodu.Nezohledňuje fakt, že dva senzory nejsou zcela identické. Předpokladem takové ener-getické míry konzistence modelu s obrazy by měla být její (alespoň) lineární invari-antnost.Z definic vidíme, že Fua hledá optimum mezi konzistencí modelu s obrazy a hlad-
kostí povrchu. Optimalizace se provádí přes všechny částice dohromady. Deformačníenergie totiž využívá relací mezi sousedními částicemi (sousednost částic je totožnáse sousedností voxelů, ze kterých částice vznikly), a tudíž přesahuje lokální popis.Tento přístup předpokládá (tak jako předchozí zmiňované přístupy), že sousední ele-menty jsou zároveň sousedními elementy na povrchu. Navíc se však vyžaduje, aby
28
Inspirace pro zpřesnění lokálních modelů 3.4
byl povrch hladký. Domnívám se, že ignorovat hrany a rohy objektů, tedy nespo-jitosti první derivace povrchu (vzhledem k použitému rozlišení obrazů), je obecněnepřípustné.V práci Faugerase a Kerivena [15] lze nají mnohem čistší přístup. Lokální model
je regulárním povrchem popsaným funkcí f(p, q). Optimálním povrchem z hlediskajeho konzistence s obrazy je pak taková funkce f , která minimalizuje funkcionál
C(f) =∫∫Ω
(I1(m1(f(p, q)))− I2(m2(f(p, q))
))2dΩ . (3.15)
Integruji přes celý povrch Ω lokálního modelu, I je intenzita obrazu, mj funkcepromítající bod povrchu do bodu obrazu j. Řešení je pak převedeno na variačníúlohu, ve které se hledá f minimalizací funkcionálu (3.15) s regularizačním členemvyžadující hladkost povrchu.
V mé práci hledám metodu verifikace a zpřesnění lokálních modelů. Požaduji, abyse tato metoda vyhnula výpočetním problémům postupu vyrovnání svazku paprskůza cenu, že nebudeme zároveň optimalizovat parametry kamer. Na druhé straně kri-tériem nebude chyba predikce bodu, ale celého lokálního modelu. Inspirací mi budefunkcionál (3.15). Ukazuje se, že zařazení této metody do fáze rekonstrukce pracujícís lokálními modely (šupinami) je výhodné, protože (i) dřívější fáze pracují s jednot-livými pixely/body, u nichž jsou nespojitosti zatíženy vychýlenými body a šumem,(ii) v pozdějším kroku je složité udržet topologickou konzistenci globálního modelu a(iii) regularizace je snadno dosaženo tím, že předpokládáme lokální planaritu šupin.
29
4 Cíl disertace
Tato disertační práce si klade za cíl přispět ke trojrozměrné rekonstrukci povrchu,a to speciálně k lokálnímu modelu tvořeného šupinami. Věnuji se dvěma úkolům:1. Verifikaci konzistence lokálního modelu s množinou obrazů.2. Zpřesnění parametrů lokálního modelu ve smyslu metody vyrovnání svazku pa-prsků.
Cílem verifikace lokálního modelu bude ověření, zda je konzistentní s množinouVerifikace modelu
vstupních obrazů scény, jejíž je modelem. Vstupem bude množina K lokálních mo-delů a množina m obrazů popsaných projektivními maticemi Mj . Výstupem budebinární relace typu vyhovuje/nevyhovuje vstupním obrazům.Protože neuvažujeme žádnou apriorní znalost o objektech scény, nemůžeme veri-
fikační rozhodnutí opřít o absolutní porovnání s takovým apriorním modelem. Zbývánám tedy založit rozhodnutí na relativním porovnání průmětů do jednotlivých ob-razů. K vyčíslení konzistencí těchto průmětů budeme muset definovat vhodnou kon-zistenční míru. Na vyhodnocení budeme nahlížet jako na statistickou úlohu.Takové porovnání zřejmě nebude možné ve zcela obecných podmínkách a pro
obecné typy povrchů. Proto bude nutné vyjádřit podmínky, za kterých lze takovérozhodnutí provést.Cílem zpřesnění lokálního modelu bude změna jeho parametrů tak, aby nové pa-Zpřesnění modelu
rametry minimalizovaly vhodně zvolený funkcionál. Tento funkcionál nebude mocibýt zvolen jako u metody vyrovnání svazku paprsků jako geometrická vzdálenostpromítnutého a měřeného obrazového bodu, protože měřené body nemáme k dispo-zici. Volba funkcionálu je součástí této práce. Funkcionál se bude moci opírat o stejnékonzistenční míry jako verifikační úloha.
30
5 Verifikace a zpřesnění lokálního modelu
V této kapitole popíši nové teoretické výsledky, kterými přispívám ke druhé fázi re-konstrukce povrchu. Formuluji úlohu verifikace obecného lokálního modelu se dvěmači více obrazy. Dále odvozuji podmínky, za kterých má formulovaná úloha jedno-značné řešení. Tyto podmínky se vztahují na odrazové vlastnosti povrchu, na jehotexturu a vzájemnou konfiguraci kamery, pozorovatele a normály povrchu.Pro řešení takto formulované úlohy zavádím čtyři různé konzistenční statistiky.
Tyto statistiky se liší tím, jak obecné typy povrchů a jaké parametry pozorovatelůpřipouštějí. Konzistenční statistiky využívám pro výpočet verifikace a zpřesnění lo-kálního modelu, tj. obou metod, které jsem si určil jako cíle této práce v kapitole 4.Tyto metody jsem popsal v závěru této kapitoly. Součástí kapitoly jsou tři původníalgoritmy: (i) algoritmus výpočtu statistiky konzistence, (ii) algoritmus verifikacelokálního modelu a (iii) algoritmus zpřesnění lokálního modelu.
týž fyzikální objekt. Jde o zobrazení V : I1×I2×· · ·×Im → B = pravda, nepravda,kde Ii je obraz získaný pozorovatelem i.Pozorují-li pozorovatelé tentýž povrch fyzikálního objektu, pak musí existovat Projekce z obrazu
do obrazu
IA
IB
u
Tg
&&
Tv
přípustná transformace jednoho obrazu na druhý IB = T (IA) (a zároveň IA =T−1(IB)). Aby mohli různí pozorovatelé porovnat naměřené hodnoty ve svých ob-razech, musí existovat korespondence, která jednoznačně přiřadí obrazy téhož místaměření. Tyto obrazy míst měření nazýváme nosiče hodnot. Pak můžeme transfor-maci obrazu do jiného obrazu rozdělit do dvou složek. První složka, tj. zobrazení hod-not Tv, transformuje obor měřených hodnot V. Druhá složka, značkovací funkce Tg,zachycuje místo měření. Pomocí obou složek můžeme zobrazení z obrazu do obrazuzapsat rovnicí
IB(Tg(u)
)= Tv
(IA(u)
), (5.1)
kterou budeme nazývat rovnicí obrazové konzistence. Označení přípustná transfor-mace vyplývá z omezujících podmínek, které jsou dány dodatečnou znalostí o pozo-rování a objektu. Získáme-li například dva obrazy roviny dvěma perspektivními ka-merami, pak nosičem u je bod v obrazové rovině a značkovací funkcí Tg je homografie.Ta je určená rovinou a vnitřními i vnějšími parametry obou kamer. Zobrazení hod-not Tv zohledňuje intenzitu a směr osvětlení, odrazivost povrchu a citlivost kamer.Značkovací funkce Tg vyjadřuje složené zobrazení z obrazu IA do prostoru objektů
a následně z tohoto prostoru objektů do obrazu IB. Může se stát, že se část informacezobrazením z prostoru objektů do prostoru obrazu ztratí. Pak je zpětné zobrazeníz obrazu nejednoznačné. V takovém případě je potřeba dodat další informaci, kterágeometrickou nejednoznačnost odstraní. Takovou informací může být apriorní pa-rametrizovaný model objektu. Druhou složkou je zobrazení hodnot, které převádíhodnoty odpovídajících si vzorků obrazů. Vyjádřit toto zobrazení bývá složité, pro-tože hodnoty často závisí na vlastnostech pozorovaného objektu [52]. Uvedeme-lipříklad z oblasti zpracování obrazových dat, pak funkce zobrazující intenzity z jed-noho obrazu na druhý je dána dvousměrovou funkcí odrazivosti povrchu a parame-
31
5 Verifikace a zpřesnění lokálního modelu
try kamer (expoziční hodnoty, zesílení). Pokud bude povrch splňovat lambertovskoupodmínku, pak bude zobrazení hodnot dáno jen parametry kamer. I tak jej budeobtížné určit.O pozorovaných objektech ve scéně nepředpokládáme žádnou globální apriorní
znalost. Rozhodnutí tedy nemůže být opřeno o porovnání se vzorovým modelem, alebude moci využít pouze vzájemného porovnání obsahů obrazů. Některá omezení,které budeme na objekty vztahovat, vyplynou z další analýzy problému.Nezávislostí pozorovatelů máme na mysli to, že k vyřešení verifikační úlohy si
nesdělují žádnou informaci o pozorovaném objektu. Pozorovatele (senzor) můžemepopsat modelem a jeho parametry. Uvědomme si však, že model senzoru je zjednodu-šený a parametry jsou nepřesné, protože byly získány na základě měření (kalibrace).Zjednodušení může být záměrné, a to z důvodů velké složitosti úlohy nebo z ne-znalosti některých parametrů modelu. Důsledkem těchto zjednodušení a dále chybměření je, že obraz transformovaný do obrazového prostoru druhého obrazu se odněj liší i v případě, když oba vznikly snímáním téhož fyzikálního objektu. Přestomůže být učiněno věrohodné verifikační rozhodnutí, pokud vliv chyb a zjednodušenínepřeváží signál nesoucí vlastní informaci o scéně.Přistupme nyní k formulaci problému verifikace. Předpokládejme, že existuje zob-Definice obrazové
konzistence razení Tg : D(IA)→ D(IB), kde D je definiční obor značkovací funkce. Toto zobrazenínazveme korespondencí mezi obrazy. Potom obrazy jsou konzistentní, když existujezobrazení Tv : V(IA) → V(IB) takové, že platí rovnice obrazové konzistence (5.1).Podaří-li se najít nebo alespoň odhadnout obě zobrazení Tg a Tv, pak úloha verifi-kace spočívá v ověření platnosti rovnice obrazové konzistence pro dané obrazy.V další sekci konkretizujeme obecnou definici verifikace z této kapitoly a odvo-
díme nutné podmínky, za kterých lze verifikační úlohu realizovat.
5.1.1 Verifikace 3D povrchu pomocí intenzitních obrazů; formalizace problému
Napsal jsem, že verifikací nazveme rozhodnutí, zda pozorovatelé pozorují tentýžobjekt. V této práci pro mě bude pozorovatelem perspektivní nebo afinní kamera,jejímž výstupem je intenzitní obraz. Vnitřní a vnější parametry kamer budou známé,takže značkovací funkce Tg bude omezena epipolární podmínkou. Kamery budoupozorovat objekt v podobě povrchu třírozměrného tělesa.
Formalizujme nyní problém tak, abychom mohli odvodit podmínky, za kterých lzeprovést verifikační rozhodnutí.1. Reprezentujme lokálně regulární povrch S [67] množinou bodů určenou dvoupa-Regulární povrch
rametrickou skalární funkcí f(p, q), kde p, q ∈ R jsou parametry kartézské rovinya f je funkce se spojitými druhými parciálními derivacemi. Vektorově povrchzapíšeme
S(p, q) =
p
q
f(p, q)
. (5.2)
Derivací podle prvního, respektive druhého parametru, získáme tečny sp a sq
sp =∂ S(p, q)∂ p
=
1
0
∂ f(p, q)/∂ p
, sq =∂ S(p, q)∂ q
=
1
0
∂ f(p, q)/∂ q
(5.3)
32
Problém verifikace 5.1
Normovaným vektorovým součinem z tečen dostaneme jednotkový normálovývektor
n =sp × sq
||sp × sq||. (5.4)
2. Budeme pracovat v okolí nějakého bodu na povrchu, který nazveme pracovním Pracovní bod
bodem w. Povrch může být v pracovním bodě aproximován tečnou rovinou, jejížbody x vyhovují rovnici [nT d] [x 1]T = 0. Parametr d ∈ R určuje polohu roviny.
3. Beze ztráty na obecnosti zavedeme lokální souřadnicový systém, který usnadní Povrchový souřadnicový
systémvýpočty v okolí bodu S(p, q). Do pracovního bodu umístíme střed souřadnic a zaortonormální bázi budeme považovat po řadě vektory sp(p, q), sq(p, q), n(p, q).Tomuto souřadnicovému systému budeme říkat povrchový, protože jeho počátekje součástí povrchu S. Značit jej budeme levým horním indexem s. Indexy pa q jsme k jednotlivým složkám báze přiřadili proto, abychom zdůraznili jejichzávislost na vybraném pracovním bodě. V tomto povrchovém souřadnicovémsystému má jednotkový vektor normály tvar sn = [ 0 0 1 ]T a body tečnéroviny pak splňují rovnici [ 0 0 1 0 ] [ sxT 1 ]T = 0.
4. Bod v okolí pracovního bodu x, vyjádřený ve světovém souřadnicovém systému, Transformace světového
na povrchový systémpřevedeme do povrchového euklidovskou transformací
sx = sT (x − st) , (5.5)
kde ortonormální rotační matice sT je po řádcích složená s vektorů sp/||sp||,sq/||sq|| a n, translační vektor st je dán světovými souřadnicemi pracovníhobodu w.
5. Povrchové souřadnice pracovního bodu jsou sw = [ 0 0 0 ]T. Bod [ a b 0 ]T Tečná rovina
je prvkem tečné roviny. Tato rovina je aproximací prvního řádu povrchu v pra-covním bodě w.
6. Nechť je povrch pozorován dvěma afinními kamerami, viz obr. 5.1. Obrazové Afinní kamery
Obecně budeme zobrazení bodu scény do bodu obrazu označovat ω : R3 → R2.7. Paprsek, pod kterým pozorujeme bod scény sx, označíme so. Pro projektivní Paprsek
kameru platí vztah so = sx − sc, kde sc je optický střed. U afinní kamery jsouvšechny paprsky rovnoběžné a získáme je trojúhelníkovou dekompozicí afinnímatice sA = sK sR. Vektor paprsku je pak třetím řádkem rotační matice [29,str. 145]
so = sR3 . (5.7)
Připomeňme si, že u afinní kamery je směr pozorování paralelní s optickou osou.8. Ozáření iA v obrazovém bodě u je popsáno rovnicí ozáření, dané složeným zob- Ozáření
razenímiA(u) = iA(
sAAsx) = ρ(l,soA) γα(sx) , (5.8)
kde sx je bodem na povrchu S, γα je rozšířený Gaussův obraz [37] (zobrazení bodupovrchu na jeho normálu násobené velikostí albeda v tomto bodě) a nakoneczobrazení ρ je paprsková dvousměrová funkce odrazivosti povrchu (BRDF)s pa-rametry vektoru osvětlení l a směru paprsku soA. Symbolem značíme složenézobrazení. Protože v našich experimentech je povrch hledanou veličinou, budemečasto zkoumat i body mimo skutečný povrch. Takový bod se pak jeví v každékameře jako jiný zdánlivý bod na povrchu s pravděpodobně jiným normálovým
33
5 Verifikace a zpřesnění lokálního modelu
w
u11
x2
u12u21
u22
x22
x12
x1
nw
nx22
nx12
nx1
regulární povrch
tečná rovina
Obrázek 5.1 Regulární povrch pozorovaný dvěma afinními kamerami. Vidíme část re-gulárního povrchu, na něm pracovní bod w a jím proloženou tečnou rovinu. Tato rovinamůže být lokální aproximací povrchu v bodě w. Dále si všimněme bodu na povrchu x1 azdánlivého bodu x2 mimo povrch, ale v okolí w. Zdánlivý bod vnímá každá kamera jako jinýprůmět na povrchu (x12 a x22) s pravděpodobně jiným albedem a normálovým vektorem.
vektorem a albedem, viz obr. 5.1. Proto zavedeme zobrazení χj obecného 3Dbodu na povrch objektu χj : sx → sx, vzhledem ke kameře j. Bod sx se promítána povrch ve směru optického paprsku. Je tedy závislý na zvolené kameře. Je-li sxbodem povrchu S, pak zobrazení χ je identitou. Celé zobrazení ozáření obecnéhobodu pak vyjadřuje vztah
iA(u) = iA(sAA
sx) = ρ(l, soA) γα χA(sx) . (5.9)
Následující diagram ilustruje zobrazení popsané v tomto a předcházejícím bodě.Horní větev diagramu, která se týká geometrie, představuje značkovací funkciTg = ωBω−1A . Prostřední a dolní větev pak ukazuje zobrazení hodnot Tv, v našempřípadě hodnot intenzit.
Obrazová rovina UA
Tg
++
βA
Povrch SωB //ωAoo
γα
Obrazová rovina UBβB
Jas IA
Tv
33Normály s albedem N ×AρB //ρAoo Jas IB
9. Zobrazení rozšířeného Gaussova obrazu γα můžeme pro bod na povrchu sx ∈ SAproximace rozšířeného
gaussovského obrazu rozepsat na součin zobrazení albeda a normálového vektoru
γα(sx) = α(sx)sn(sx) = α(sx) γ(sx) . (5.10)
Jak jsme již uvedli v minulém odstavci, bod mimo povrch sx 6∈ S musíme trans-formovat pomocí zobrazení χ a dostaneme tak
γα(sx) = α
(χ(sx)
)γ(χ(sx)
). (5.11)
34
Problém verifikace 5.1
Protože hledáme tvar povrchu, většinou neznáme ani jeho normály. Proto rozší-řený Gaussův obraz γα musíme pouze odhadovat. Odhad lze získat na základěaproximace povrchu v pracovním bodě.a) Nejjednodušší možnou aproximací je vztáhnout celé okolí pracovního boduk tomuto bodu. V takovém případě je hodnota albeda i normály každéhobodu z okolí rovna albedu a normále pracovního bodu
γα(sx) = α(sw) sn(sx) = α
000
001
. (5.12)
b) Pokud povrch aproximujeme tečnou rovinou v pracovním bodě w, pak nani můžeme promítnout zdánlivý bod x zobrazením χ. V tomto průmětuzískáme albedo. Protože jde o aproximaci rovinou, bude normála vždy rovnanormále tečné roviny
γα(sx) = α
(χ(sx)
)sn(sx) = α(χ(sx)) 001
. (5.13)
c) Obecnější aproximací je popis oskulačním paraboloidem s lokálními souřad-nicemi p, q a koeficienty L, M a N
%(p, q) =12(L sp2 + 2M sp sq +N sq2) . (5.14)
Bude-li χ(sx) = [p, q, %]T průmětem zdánlivého bodu na paraboloid, pakrozšířený Gaussův obraz lze zapsat
γα(sx) = α
(χ(sx)
) L sp+MqN sq +Mp
1
. (5.15)
10. Paprsková dvousměrová funkce odrazivosti povrchu ρ(sl, so)(sn) vyjadřuje po- Aproximace
funkce odrazivostiměr energie paprsku odraženého k energii paprsku dopadajícího v závislostina geometrickém uspořádání vektoru osvětlení l, směru pozorovatele so a vek-toru normály sn. Nejčastěji se funkce odrazivosti parametrizuje čtveřicí úhlůρ(θl, ϕl, θp, ϕp). Jde o elevační a azimutální úhel v lokálním systému souřadnic,v nichž normálový vektor směřuje přesně na sever. První dva úhly se týkají směruosvětlení, druhé dva směru pozorovatele. Tyto úhly lze z vektorového vyjádřenísměrů snadno spočítat.Protože je tato funkce velmi obecná, používá se pro různé typy povrchů předpo-kladu, které ji zjednodušují. Uvedeme si některé z nich [36]:a) Předpokládáme-li izotropii povrchu na směru dopadajícího světla, pak funk-ce odrazivosti nezávisí na absolutních hodnotách azimutů, jen na jejich roz-dílu, tj.
ρ(θl, ϕl, θp, ϕp) = ρ(θl, θp, ϕl − ϕp) . (5.16)
b) Funkce nezávisí na úhlu pozorovatele, ale jen na elevaci osvětlení. Povrchu,který splňuje takovou podmínku, říkáme lambertovský povrch [43]
ρ(θl, ϕl, θp, ϕp) = ρ(θl) . (5.17)
c) Dále existují povrchy, u kterých je závislost na směru osvětlení malá, na-příklad u povrchu Měsíce, pak můžeme psát funkci odrazivosti
ρ(θl, ϕl, θp, ϕp) = ρ(θp, ϕp) . (5.18)
35
5 Verifikace a zpřesnění lokálního modelu
11. Zobrazení hodnot Tv definujeme následujícím vztahemZobrazení hodnot Tv
Tv ρ(l, soA) γα(sx)− ρ(l, soB) γα(
sx) ≡ 0 . (5.19)
Je to funkce, která zaručí stejné hodnoty jasu bodu, který pozorujeme na po-vrchu, z jedné i druhé kamery. Musí tedy vyrovnat závislost BRDF na pozoro-vacím vektoru a různost kamer. Pro lambertovský povrch a stejné kamery je Tvidentitou.Zobrazení hodnot se zavádí pro každý bod na povrchu x ∈ S zvlášť. Každý bodpovrchu tedy může mít jinak definovanou funkci Tv. Při zkoumání okolí bodux však budeme předpokládat, že se funkce Tv v tomto okolí nemění. Za tohotopředpokladu derivací (5.19) podle ∂ sx dostaneme
∂ Tv∂ iA1×1
· ∂ ρ(l,soA)
∂ snT1×3
· ∂ γα
∂ sxT3×3
− ∂ ρ(l, soB)∂ snT1×3
· ∂ γα
∂ sxT3×3
= 0 , (5.20)
kde pod jednotlivými členy jsou uvedeny rozměry matic. Pokud je sx rovinnýbod nebo ∂ ρ padne do nulového prostoru ∂ γα nebo je ∂ γα kritickým bodem∂ ρ, pak definujeme
∂ Tv∂ iA
= 1 , jinak z (5.20) plyne
∣∣∣∣∂ Tv∂ iA
∣∣∣∣ = ‖∂ ρ(l,soB)∂ snT
‖
‖∂ ρ(l,soA)∂ snT
‖= T (5.21)
jako poměr velikostí gradientu BRDF. Pro druhou derivaci ∂2Tv/∂ i2A platí
∂ γα
∂ sx·∂ ρ(l,
soA)∂ sn
·∂2Tv∂ i2A
·∂ ρ(l,soA)
∂ snT+∂ γα
∂ sx·∂2ρ(l, soA)∂ snsnT
·∂ Tv∂ iA
−∂ γα
∂ sx·∂2ρ(l, soB)∂ snsnT
= 0.
(5.22)12. Zavedeme rozdílovou funkci jako rozdíl dvou korespondujících si jasů po jejichRozdílová funkce
převedení na stejnou úroveň pomocí Tv
E(sx) =(Tv(iA(sAA
sx))− iB(
sABsx))2= F 2 ' (5.23)
'(Tv ρ(l, soA) γα χA(sx)− ρ(l, soB) γα χB(sx)
)2. (5.24)
Představme si, že dva pozorovatelé sledují stejný bod sx v prostoru. Pak nu-lovost této funkce vyjadřuje konzistenci tohoto bodu se dvěma obrazy povrchu.Vztahy po obou stranách znaku ' jsou si rovny, ale vyjadřují rozdílný popis, jed-nou z hlediska obrazové funkce a podruhé z hlediska fotometrického formováníintenzit.
13. Rozdílová funkce má následující vlastnosti:Vlastnosti
rozdílové funkce a) Je-li x bodem povrchu, tj. x ∈ S, pak můžeme zavést v tomto bodě lokálnípovrchový systém souřadnic. V něm je pracovní bod počátkem. Pro nul-tou, první a druhou derivaci rozdílové funkce v tomto počátku povrchovýchsouřadnic platí, že:i. Rozdílová funkce bude díky (5.19) na povrchu nulová
E(sx) ≡ 0 . (5.25)
Obě zobrazení χA = χB jsou identitou, takže oba pozorovatelé získávajíobraz stejného bodu a obrazové body navzájem korespondují.
36
Problém verifikace 5.1
ii. První derivace rozdílové funkce podle jednotlivých os povrchového sou-řadnicového systému bude zřejmě v prvních dvou složkách velmi malá,protože když bodem pohybujeme ve směru tečné roviny, odchylka boduod povrchu bude velmi malá. Co ovšem budeme vyžadovat je, aby de-rivace podle třetí složky, tj. ve směru normálového vektoru, byla rovnanule. Důvodem je, že rozdílová funkce má mít v bodě na povrchu lokálníextrém
∂ E
∂ sxT(sx) =
∂ E
∂ sxT([ 0 0 0 ]T) ≡ 0T . (5.26)
iii. Dále chceme, aby požadovaný extrém byl minimem, takže druhá deri-vace ve směru normálového vektoru byla větší než nula (druhá derivacerozdílové funkce podle prvních dvou povrchových os není zajímavá abude blízká nule, viz předchozí bod 13(a)ii.)
∂2E
∂ sxsxT(sx) =
∂2E
∂ sxsxT([ 0 0 0 ]T) =
0 0 ?0 0 ?? ? > 0
. (5.27)
Otazníky značíme hodnoty, na které neklademe žádné omezení.b) Jestliže vyčíslíme rozdílovou funkci v bodě mimo povrch sx 6∈ S, pak poža-dujeme, aby:i. Globální minima existovala pouze v bodech na povrchu, tj. rozdílováfunkce nebyla rovna nule
E(sx) 6= 0 . (5.28)
ii. Prostorový směr minimalizace rozdílové funkce byl jednoznačný a smě-řoval k povrchu, tj. funkce neměla lokální minima; proto první derivacefunkce podle směru normály nesmí být rovna nule
∂ E
∂ sxT(sx) = [ ? ? 6= 0 ] (5.29)
a pokud ano, pak abyiii. extrémem nebylo minimum, tj. druhá derivace nebyla kladná
∂2E
∂ sxsxT(sx) =
? ? ?? ? ?? ? ≤ 0
. (5.30)
Pokud tyto podmínky nebudou splněny, pak při pohybu v okolí bodu x
nepoznáme, zda jsme na povrchu, nebo ne.14. První derivace rozdílové funkce podle směrového vektoru sx má tvar 1. derivace
rozdílové funkce
∂ E
∂ sxT(sx) = 2F
∂ F
∂ sxT= 2F
(∂ Tv∂ iA
· ∂ iA∂ uTA
sAA −∂ iB
∂ uTB
sAB
)= 2F G ' (5.31)
' 2F
(∂ Tv∂ iA
· ∂ ρ(l,soA)
∂ snTA· ∂ γα
∂ sxTA
· ∂ χA(sx)
∂ sxT− ∂ ρ(l, soB)
∂ snTB· ∂ γα
∂ sxTB
· ∂ χB(sx)
∂ sxT
), (5.32)
kde (∂ i/∂ uT)sA je změna jasu ve směru, který získáme průmětem vektoru ∂ sxT
do obrazové roviny. Vyjadřuje tedy to, jak se mění jas v jednom obraze, kdyžměníme polohu jeho 3D vzoru ve směru vektoru ∂ sxT.Protože se naše požadavky zaměřují hlavně na derivaci podle třetí složky smě-rového vektoru sx (směr normály povrchu v pracovním bodě), vyčíslíme derivacijen podle tohoto směru
37
5 Verifikace a zpřesnění lokálního modelu
∂ E
∂ sx3(sx) = 2F
∂ F
∂ sx3= 2F
(∂ Tv∂ iA
· ∂ iA∂ uTA
sAA3 −∂ iB
∂ uTB
sAB3
)= 2FG3 ' (5.33)
' 2F
(∂ Tv∂ iA
· ∂ ρ(l,soA)
∂ snTA· ∂ γα
∂ sxTA
· ∂ χA(sx)
∂ sx3− ∂ ρ(l, soB)
∂ snTB· ∂ γα
∂ sxTB
· ∂ χB(sx)
∂ sx3
), (5.34)
kde index sAA3 označuje třetí sloupec afinní matice prvního obrazu v lokálníchsouřadnicích.
15. Druhou derivaci rozdílové funkce vyjádříme následujícím vztahem2. derivace
rozdílové funkce
∂2E
∂ sxsxT(sx) = 2
(∂ F
∂ sxG+ F
∂ G
∂ sx
)= 2
(sATA
∂ Tv∂ iA
· ∂ iA∂ uA
− sATB∂ iB∂ uB
)G+
+ 2F
(sATA
(∂2 Tv∂ i2A
· ∂2iA
∂ uTAuTA+∂ Tv∂ iA
· ∂2iA
∂ uAuTA
)sAA − sATB
∂2iB
∂ uBuTB
sAB
)= (5.35)
= 2(GTG+ FH
). (5.36)
Pro druhou derivaci pouze ve směru třetí složky vektoru sx dostaneme
∂2E
∂ sx23(sx) = 2(G23 + FH33) . (5.37)
Člen H33 spočítáme derivací G3 (5.34)
H33 =∂ G
∂ sx3=
∂
(∂ Tv∂ iA
· ∂ ρ(l,soA)
∂ snTA· ∂ γα
∂ sxTA
· ∂ χA(sx)
∂ sx3− ∂ ρ(l, soB)
∂ snTB· ∂ γα
∂ sxTB
· ∂ χj(sx)∂ sx3
)∂ sx3
=
= SA1 +∂ Tv∂ iA
(SA2 +
∂ ρ(l, soA)
∂ snTA
(SA3 +
∂ γα
∂ sxTA
· SA4))
− SB2 −∂ ρ(l, soB)
∂ snTB
(SB3 +
∂ γα
∂ sxTB
· SB4),
(5.38)
kde pro obecný obrázek j jsou zavedeny substituce
Sj1 =
∂ χj(sx)
∂ sxT3· ∂ γα
∂ sxj· ∂ ρ(l,
soj)∂ snj
· ∂2 Tv∂ i2j
· ∂ ρ(l,soj)
∂ snTj· ∂ γα
∂ sxTj· ∂ χj(sx)∂ sx3
,
Sj2 =
∂ χj(sx)
∂ sxT3· ∂ γα
∂ sxj· ∂2 ρ(l, soj)
∂ snjsnTj
· ∂ γα
∂ sxTj· ∂ χj(sx)∂ sx3
,
Sj3 =
∂ χj(sx)
∂ sxT3· ∂2 γα
∂ sxjsxTj
· ∂ χj(sx)∂ sx3
,
Sj4 =
∂2χj(sx)∂ sx23
.
(5.39)
Dosadíme-li derivace zobrazení hodnot (5.20) a (5.22) do (5.38), dostaneme
H33 =∂ χB(sx)
∂ sxT3· ∂ γα
∂ sxB· ∂2ρ(l, soB)
∂ snBsnTB
(∂ γα
∂ sxTA
· ∂ χA(sx)
∂ sx3− ∂ γα
∂ sxTB
· ∂ χB(sx)
∂ sx3
)+ T SA5 − SB5 . (5.40)
se substitucí
Sj5 =
∂ ρ(l, soj)
∂ snTj
(∂ χj(sx)∂ sx3
· ∂2γα
∂ sxjsxTj
· ∂ χj(sx)∂ sx3
+∂ γα
∂ sxTj· ∂2χj(sx)∂ sx23
). (5.41)
38
Problém verifikace 5.1
5.1.2 Nutné podmínky verifikační úlohy
Nyní je již problém formalizován tak, že se můžeme pokusit vyvodit nutné podmínky,za kterých rozdílová funkce popisuje verifikační úlohu. Tyto podmínky nám zaručí, žerozdílová funkce rozliší skutečný bod na povrchu od zdánlivého bodu mimo povrch.Pro jejich odvození vyjdeme z vlastností rozdílové funkce. Budeme prověřovat bodprostoru, který neleží na povrchu objektu.Podmínka A (5.28). Mimo povrch nesmí být rozdílová funkce rovna nule. To je Nulovost E
jen na povrchupodle (5.23) porušeno, když Tv(iA) = iB. Jsou-li obě zobrazení χA a χB prostá,tj. je-li zkoumaná část povrchu viditelná pro obě kamery a nevzniká tam okluze,můžeme zapsat sxA = χA(sx) a sxB = χB(sx). Rovnost jasů pak vyjádříme po-mocí (5.24)
Tv ρ(l, soA) γα(sxA) = ρ(l,soB) γα(sxB) . (5.42)
Vytkneme-li hodnotu albeda z rozšířeného Gaussova obrazu γα podle (5.10),dostaneme vztah
Tv
(α(sxA) ρ
(l, soA, γ(sxA)
))= α(sxB) ρ
(l, soB, γ(sxB)
). (5.43)
Tato rovnice je splněna, platí-li alespoň jeden z následujících vztahů:1. sxA = sxB, tj. χA = χB = χ. Tento vztah platí (i) na povrchu objektu nebo(ii) jsou-li optické paprsky rovnoběžné soA = soB. Obě kamery pak sledujístejný průmět na povrchu a pod stejným úhlem. Zobrazení Tv pak musí býtz definice (5.19) identitou a rovnost (5.43) je splněna.Pro splnění verifikačních podmínek stačí, když dvě kamery nebudou mítrovnoběžné paprsky.
2. Platí zároveň tři následující vztahya) ρ
(l, γ(sxA)
)= ρ(l, γ(sxB)
)povrch je lambertovský; pak Tv je identitou,
b) γ(sxA) = γ(sxB) normály obou průmětů jsou shodné,c) α(sxA) = α(sxB) na průmětech je stejné albedo.Použijeme-li více jak dvě kamery, zúžíme množinu povrchů, které nesplňujíverifikační podmínky. Pro všechny průměty totiž musí platit vztahy b) a c).
3. BRDF záleží jen na rozdílech vektorů l, snj a soj , např. (5.16). Pak jepodmínka splněna, je-li tvar a albedo povrchu symetrický vůči normálepracovního bodu a kamery jsou vůči této normále také symetricky umístěny.Tři kamery v obecné poloze tento případ vyloučí pro všechny orientacepovrchů.
4. Albedo dorovnává výchylky paprskové dvousměrové funkce odrazivosti. Proilustraci, příkladem takového povrchu je lambertovská plocha pokrytá šedoubarvou. Stupeň šedi odpovídá odrazivé funkci, řekněme že klesá s kosinemúhlu mezi normálou a vektorem osvětlení. Pravděpodobnost, že na takovýtopovrch v přirozených situacích narazíme, je mizivá. Může se však snadnostát, že nějaké lokální okolí bude této podmínce neměřitelně blízko.Na lambertovském povrchu nám počet kamer třídu přípustných úloh neroz-šíří.
Podmínka B (5.29). Třetí člen první derivace má být mimo povrch nenulový. Pro- Mimo povrch, 1. derivace
tože jsme si předchozím bodem zajistili F 6= 0, zbývá podle (5.33) zajistit i ne-nulovost G3. Tento člen je nulový, když
±T · ∂ ρ(l,soA)
∂ snTA· ∂ γα
∂ sxTA
· ∂ χA(sx)
∂ sx3=∂ ρ(l, soB)
∂ snTB· ∂ γα
∂ sxTB
· ∂ χB(sx)
∂ sx3, (5.44)
39
5 Verifikace a zpřesnění lokálního modelu
s podmínkou ∂ ρ(l, soA)/∂ snTA 6= 0, plynoucí z (5.20). Rozlišme dva případy, kdymůže k takovému případu dojít:1. Oba členy rovnice (5.44) jsou zároveň rovny nule
±T · ∂ ρ(l,soA)
∂ snTA· ∂ γα
∂ sxTA
· ∂ χA(sx)
∂ sx3= 0 ∧ ∂ ρ(l, soB)
∂ snTB· ∂ γα
∂ sxTB
· ∂ χB(sx)
∂ sx3= 0 . (5.45)
Tento případ nastane tehdy, když pro obě kamery dojde k alespoň jednéz následujících situací:a) ∂ χ(sx)/∂ sx3 = 0; průmět bodu na povrch zůstává konstantní, pohy-bujeme-li jím ve směru ∂ sx3. Také můžeme říci, že průmět na povrchse nemění, když bodem pohybujeme ve směru paprsku. Protože pohybbodem ve směru ∂ sx3 je pohybem ve směru třetí báze povrchového sou-řadnicového systému, kterou je vektor sn, musí být paprsek rovnoběžnýs normálou pracovního bodu so ‖ sn.Stačí použít dvě kamery v obecné poloze, aby se tento případ vyloučila verifikační podmínky byly splněny.
b) ∂ γα/∂ sxj = 0; tento vztah říká, že na průmětu vektoru ∂ sx3 je al-bedo i povrchová normála konstantní. Takovým kritickým povrchem jerovinný bod, na kterém jsou obě hlavní křivosti nulové.Tento příklad nevyloučí ani použití nekonečně mnoha afinních kamer.
c) Vektor ∂ χj(sx)/∂ sx3 padne do nulového prostoru matice ∂ γα/∂ sxTj .Příkladem je přímková plocha s nulovou křivostí ve směru ∂ sxj a kon-stantním albedem v tomto směru jako válcová plocha orientovaná vesměru ∂ sxj s konstantním albedem. Obě kamery tuto podmínku splňujítehdy, když soA, soB a osa válce leží v jedné rovině.
d) Vektor ∂ ρ(l, soB)/∂ snTB padne do nulového prostoru matice ∂ γα/∂ sxTj .Tato situace nastává v izolovaných bodech na parabolických křivkáchpovrchu. Jde o následující případy: (i) změna normály se pohybujepo izofotě, (ii) v bodě ∂ sxB je kritický bod BRDF (např. maximumintenzity na reflexním povrchu je-li úhel dopadu roven úhlu odrazu a∂ snB a l jsou v rovině nebo jiným příkladem je lambertovský povrch,je-li osvětlení ve směru normály ∂ snB).Bod (i) umožňuje třídu povrchů nevyhovujících verifikační podmíncezúžit, použijeme-li více kamer. Bod (ii) lze vyloučit i dvěma kamerami,budou-li v obecné poloze.
2. Levá i pravá strana rovnice (5.44) jsou si rovny, ale jsou nenulové. Tako-vou situaci splňují podmínky A a dále případy bodů na povrchu, kde mározdílová funkce lokální maximum, minimum nebo inflexi. Následující pod-mínky C vyčleňují z těchto případů body s minimy.
Podmínka C (5.30). Nyní připustíme, že podmínka z předchozího bodu bude poru-Mimo povrch, 2. derivace
šena, tj. G3 = 0. Jde o případ, kdy rozdílová funkce v bodě mimo povrch objektumá extrém. V tomto případě ale nesmí mít minimum (5.29). Nerovnost (5.37) sezjednoduší na FH33 ≤ 0. Ptejme se, kdy je tato podmínka porušena. Porušenaje tehdy, když oba členy mají stejná znaménka1. F > 0 a H33 > 0 nebo2. F < 0 a H33 < 0.Člen F > 0 říká, že jas promítaného bodu do prvního obrazu je vyšší než doobrazu druhého. Zjistit znaménko členuH33 (5.38) a fyzikálně jej interpretovat, jedosti komplikované i při omezující podmínce G3 = 0. Jde však o body, ve kterých
40
Problém verifikace 5.1
je rozdílová funkce nižší než v libovolném bodu svého okolí. K takovým případůmmůže dojít u periodických textur. Příkladem může být tapeta s puntíky. Průmětyzdánlivých bodů se pak mohou strefit do puntíku, každý však do jiného.
Shrňme omezující podmínky platnosti verifikační procedury afinních kamer do ná- Shrnutí podmínek
sledujících bodů:1. Průměty zdánlivého bodu musí být oběma kamerami viditelné a bez okluze.2. Normála a albedo (textura) nesmí být na lambertovském povrchu ve sledovanémokolí konstantní.
3. Albedo nesmí dorovnávat BRDF.4. Optické paprsky musí být nerovnoběžné.5. Pozorujeme-li přímkovou plochu s konstantním albedem podél přímky, nesmíprůměty padnout do jedné přímky této plochy.
6. Světlo, kamery, albedo a normály povrchy nesmí být symetrické vůči normálepracovního bodu. Při použití více kamer ubývá uspořádání, které vyhovují tétopodmínce.
7. Albedo (textura) nesmí být periodická ve směru průniku s epipolární rovinou.
Uveďme pro ilustraci příklady scén, které nesplňují podmínky verifikace: Příklady
• Rovina s homogenní texturou a libovolnou konfigurací kamer.• Válec s pruhy rovnoběžnými s jeho osou. Dvě kamery svírají s osou válce stejnýúhel nebo jejich osy a osa válce leží v rovině.
• Koule pozorovaná kamerami se stejným úhlem svých optických os k vektoruosvětlení. Izočáry albeda tvoří kružnice se středem na přímce spojující osvětlenía střed koule.
Podmínky jsme z důvodů zjednodušení odvozovali pro pozorovatele s afinní kamerou.I přes toto zjednodušení vycházely vztahy dosti nepřehledné. Afinní kamery námpodmínky splnitelnosti omezují silněji, než je třeba pro běžně užívané perspektivnímodely kamer. Je to tím, že perspektiva dále deformuje okolí bodů. Zatímco u afinníkamery například nezáleží na vzdálenosti od povrchu, musí být vzdálenost každéperspektivní kamery od bodového okolí stejná, aby vykazovalo stejné diferenciálníparametry. Z tohoto důvodu pro perspektivní kameru můžeme zmírnit poslední čtyřipodmínky.Rozdílová funkce E byla pro odvození podmínek realizovatelnosti zvolena ve
tvaru kvadrátu rozdílů jasů. Pro praktickou realizaci navrhujeme v dalších sekcíchrozdílovou funkci v jiných, vůči obrazovým deformacím více invariantních, tvarech.Umožní nám to odhadovat různé třídy funkcí Tv, zahrnující reálné podmínky měření.
5.1.3 Praktická realizace verifikace
Dosud byl návrh vztažen k ideálním podmínkám paprskové optiky. V reálné situ-aci bude rozdílová funkce pro body na povrchu nenulová. Způsobují to jak chybyznačkovací funkce, tak chyby zobrazení hodnot jasů. Jednotlivě si je nyní probereme.Při známém zobrazení geometrie, vystihujícím přesně reálnou projekci, dosta- Chyby značkovací funkce
neme v každém obraze vzájemně si odpovídající obrazové body UA a UB. Parametryzobrazení získané kalibrační procedurou (např. středy promítání CA a CB) jsou všakzatíženy náhodnou chybou. Jejím důsledkem je, že spočítané obrazové body UA a UBse od reálného promítnutí liší a nemusí si přesně korespondovat. V takovém případěse spočítané paprsky procházející korespondujícími si body UA a UB, neprotínajív jednom bodě, bodě X na povrchu objektu.
41
5 Verifikace a zpřesnění lokálního modelu
Dalším zdrojem, tentokráte systematických chyb, je zjednodušení modelu ka-mery. Může to být např. způsobeno zanedbáním radiálního zkreslení optiky. Je třebazvážit velikost této chyby vzhledem k požadované přesnosti verifikace.Chyby zobrazení jasů můžeme rozdělit do dvou skupin: (i) chyby při formováníChyby zobrazení jasů
obrazu a (ii) chyby při projekci z obrazu do obrazu. Zaznamenání světelné energiepři formování obrazu na CCD senzoru je doprovázeno náhodným tepelným šumems normálním rozdělením a poissonovským šumem generovaných elektronů. K tomutošumu je třeba ještě přičíst chybu, která vzniká integrací signálu na plošce konečnýchrozměrů spojenou s diskretizací obrazového prostoru a kvantizací výsledného jasu.Identická projekce jasů z obrazu do obrazu na základě lambertovského modelu
odrazivosti zcela zanedbává různou intenzitu odraženého paprsku do různých směrů,viz např. obr. 5.2. Musíme si uvědomit, že se tím dopouštíme značné chyby u reflex-ních povrchů, zvláště osvětlených bodovými zdroji světla. Naopak matné povrchy arozptýlené světlo jsou lambertovským modelem odrazivosti popsány poměrně přesně.Verifikační procedura zamítne správné lokální modely se spekularitami, protože bu-dou v obrazech vypadat rozdílně.Další nepřesnosti se dopouštíme interpolací intenzit pro neceločíselné souřadnice
pixelů. Vedlejším efektem tohoto procesu je potlačení šumu, protože pracuje jako(průměrovací) dolnopropustný filtr.Z důvodů popsaných chyb a přijatých zjednodušení budou projekce jednoho ob-Chyby zobrazení jasu jako
jasové deformace razu do druhého rozdílné. Protože jde o odchylky od ideálního stavu, budeme jimříkat jasové deformace. Shrňme příčiny takových deformací mezi obrazy téhož ob-jektu snímaných z různých míst nestejnou kamerou:a) Povrch objektu nesplňuje předpoklady o lambertovském povrchu; nejvýraznějšímdůsledkem jsou odlesky v některých pohledech.
b) Povrch na sebe vrhá stíny, zakrývá sám sebe a odráží se sám na sebe.c) Chyba aproximace; neznámý tvar povrchu je nahrazen hustotou pravděpodob-nosti povrchu a ta aproximována lokálním (rovinným) modelem.
d) Diskretizace a kvantizace obrazu a zpětná interpolace jasu v neceločíselnýchsouřadnicích.
e) Šum kamer.f) Rozdílnost kamer; vzájemný posun nulové úrovně, různé zesílení a nelinearita.Metoda verifikace bude pracovat tím lépe, čím slabší budou jasové deformace v ob-Potlačení chyb
razech nebo bude-li jejich přítomnost a intenzita známa. Bohužel, splnění tohotopředpokladu dost dobře nelze zajistit bez přídavných měření nebo apriorních zna-lostí o pozorované scéně. Nezbývá nám, než se (i) snažit vliv těchto faktorů potlačit
Obrázek 5.2 Odraz na detailu lidskéhooka, které má nelambertovský povrch.Obrys průmětu geometricky správnéholokálního modelu ve tvaru disku ve dvouobrazech. Všimněme si různého eliptic-kého tvaru vlivem perspektivního zkres-lení a radiometrických odchylek, hlavněna rohovce oka.
42
Konzistence modelu s obrazy 5.2
Obrázek 5.3 Verifikace bodového modelu.Model X1 je verifikován, protože jeho projekcepadne v obou obrazech do vzájemně si kore-spondujících oblastí. Říkáme, že model je kon-zistentní s obrazy. Oproti tomu model X2 jenekonzistentní, protože levá kamera jej zdán-livě vnímá na pozadí ε1 a pravá na pozadí ε2.Obrazy tohoto modelu se tedy vzájemně liší.
X1
X2
ε1ε2Objekt
nebo (ii) vliv modelovat. Pokud bychom zapojili znalost BRDF potlačíme příčinybodů (a) a (c). Přesnější popis odhadu hustoty pravděpodobnosti povrchu ve formělokálního modelu vyššího řádu pomůže potlačit bod (c). Vyšší rozlišení a vyšší jasovádynamika kamer sníží vliv (d), chlazení čipu vliv (e). Bod (f) můžeme zcela elimino-vat a bod (a) potlačit, použijeme-li lineární normalizaci obrazů. Náhradu nevhodnépřirozené textury (např. je-li textura slabá nebo periodická) a snížit vliv (a) lze do-sáhnout projekcí náhodné umělé kontrastní textury při pořizování obrazů. Přes tutosnahu snížit jasové deformace se občas může stát, že přijmeme chybné rozhodnutío konzistenci modelu. Protože nejvýraznější deformace (a) a (b) jsou závislé na úhlupohledu, lze využitím většího počtu obrazů a vhodným sdružením jejich příspěvkůke konečnému rozhodnutí zvýšit pravděpodobnost správného určení pozice bodu.V této práci se ovšem touto problematikou nebudeme zabývat.
5.2 Konzistence modelu s obrazy
Napsali jsme, že verifikaci budeme chápat jako ověření geometrických parametrůlokálního modelu na základě porovnání jeho průmětů v obrazech. K tomuto ověřeníbudeme potřebovat pojem konzistentního a nekonzistentního modelu.Přijměme nyní na chvíli předpoklad, že model je tvořen jen jedním bodem X Konzistence modelu jako
konzistence bodůa neuvažujme chyby zobrazení. Pokud jsou geometrické prametry tohoto modelusprávné, tj. bod leží na povrchu reálného objektu, pak jeho průměty si v obrazechodpovídají a mají stejnou hodnotu jasu. Takový bod nazýváme konzistentním bo-dem, viz obr. 5.3. Pokud naopak bod leží mimo reálný povrch (ať už před ním neboza ním), potom budou jeho průměty spadat do nekorespondujících si oblastí. Jasyjeho průmětů se budou pravděpodobně lišit a bod budeme považovat za nekonzis-tentní.Známe jasy v průmětech bodu do jednotlivých obrazů, ale neznáme zobrazení
hodnot Tv. K jeho určení nám jeden pár hodnot nestačí. Budeme měřit na okolí –lokálním modelu – za předpokladu, že se Tv na něm nemění. Zobrazení Tv pak mů-žeme zrekonstruovat nebo ověřit ze zvolené třídy funkcí, zda měřené hodnoty sva-zuje. Nalezneme-li takovou třídu funkcí, pak lokální model nazveme konzistentnímmodelem. Pro ověření, zda Tv spadá do zvolené třídy funkcí zavedeme statistikakonzistence. Na verifikační rozhodnutí budeme nahlížet jako na statistický problém.
43
5 Verifikace a zpřesnění lokálního modelu
Pro verifikační proceduru potřebujeme následující údaje:Shrnutí
• Minimálně dva obrazy z různých pozorovacích míst s překrývajícími se poli zá-běru statické scény nebo sejmutých synchronizovanými kamerami.
• Parametry projekce modelu svazující souřadnicový systém modelu a obrazů (pro-jekční matice).
• Lokální model povrchu objektu určený geometrickými parametry (poloha, orien-tace, velikost).
Realizaci verifikačního problému převedeme na rozhodovací úlohu o konzistenci lo-kálního modelu povrchu s obrazy. Omezení odvozená v kapitole 5.1.2 nám zaručujíjednoznačnost tohoto převodu. Jedinými vstupními daty tohoto procesu pro násbudou intenzitní obrazy, jejich projekční matice a parametery lokálního modelu.
5.2.1 Projekce modelu do obrazů
Perspektivní zobrazení geometrie a zobrazení hodnot jasu 3D objektu do obrazu jepopsáno v kapitole 2.1.3. Využívá model perspektivní kamery se znalostí jeho (vnitř-ních a vnějších) parametrů. Značkovací funkci z obrazu A do obrazu B vyjádřímes použitím dílčích zobrazení
Tg = ωB ω−1A . (5.46)
Takové zobrazení není jednoznačně určeno. Musíme přidat lokální model povrchu.Nejjednodušším modelem je rovina s normálovým vektorem n[
nT d]
x = 0 . (5.47)
Zobrazení obrazu do obrazu přes rovinný objekt je pak homografií H indukovanérovinou [29, str. 312] a vyjadřuje značkovací funkci Tg
uB = H uA . (5.48)
Pro praktické použití však bude výhodnější, když obrazové korespondence zís-káme projekcí lokálního modelu do každého obrazu. Nabízejí se zde dva základnípřístupy:• Model nahradit množinou bodů X podle zvolené vzorkovací funkce pa : model→
R3 a jednotlivé body x z této množiny promítnout do každého obrazu.• Promítnout celý model najednou (využít parametry modelu), určit v každémobraze plochu jeho průmětu a podle funkce pb : plocha → R2 ji aproximovatbody u v obraze.
Protože obě metody vrátí neceločíselné souřadnice obrazových bodů, je vhodné po-užít dvourozměrnou interpolaci zvoleného řádu k určení hodnoty jasu.Tato část verifikace je závislá na zvoleném lokálním modelu. Ukážeme si zde dvě
varianty projekce námi používaného šupinového modelu popsaného v kapitole 3.1.Modifikace projekce pro jiný model by neměla činit problémy.
Projekce bodové množiny, vzorek z funkce příslušnosti modelu
Máme-li množinu X bodů x v prostoru R3, je velice snadné ji promítnout do každéhoobrazu i pomocí rovnice (2.2) a dostat množiny obrazových bodů Ui. Obtížnější jezvolit vhodnou funkci pa, která k jednomu šupinovému modelu (kapitola 3.1) vyge-neruje množinu X o n prvcích. Protože šupina je fuzzy množinou s funkcí příslušnostipodle normálního rozdělení (3.3), je přirozené body náhodně generovat podle tétofunkce.
44
Konzistence modelu s obrazy 5.2
Věta. Jsou-li Nij ∈ N (0, 1) pro i = 1, . . . , n a j = 1, 2, 3 nezávislé hodnoty z jed-norozměrného normálního rozdělení, pak bod xi odpovídající středu x0 a strukturnímatici S = UTU šupiny lze vygenerovat pomocí vztahu
xi = UT
Ni1
Ni2
Ni3
+ x0. (5.49)
Důkaz. Strukturní matice šupiny S je normalizovanou autokovarianční maticí nbodů xi, s vlastnostmi E(xi) = x0 a
S =X XT
n− 1, kde X =
[x1 − x0, x2 − x0, . . . , xN − x0
]. (5.50)
Dosadíme-li (5.49) do (5.50), dostaneme
S =1
n− 1UT
N11N21 . . . NN1
N12N22 . . . NN2
N13N23 . . . NN3
N11N21 . . . NN1
N12N22 . . . NN2
N13N23 . . . NN3
T
U = UTE U = S , (5.51)
protože pro velký počet bodů n autokovariační matice normálně rozdělených číselse střední hodnotou v nule a jednotkovým rozptylem se blíží výrazu (n− 1)E, kde E
je jednotková matice.
Dále je třeba dát pozor, aby velikost šupiny byla dostatečná vůči rozlišení diskrétníhoobrazu, tj. většina vygenerovaných bodů nepadla do jediného pixelu. Pak by totižkonzistence mohla prudce vzrůst v závislosti na druhu interpolace a okamžité polozev obraze vzhledem k diskrétní mřížce.
Projekce bodové množiny, vzorek z hlavní roviny
Protože body vygenerované blíže středu šupiny mají na zakřiveném povrchu nižšíodchylku v poloze než body vzdálenější (za předpokladu správné polohy středu),odpovídá vyšší hustota normálního rozdělení u středu šupiny větší věrohodnostitěchto bodů ve smyslu lokální aproximace povrchu ve středu šupiny. (Věrohodnostse zde chápe obecně, ne jako logaritmus pravděpodobnosti.) Musíme si však zároveňuvědomit, že vzdálenější body jsou citlivější k případné odchylce modelu od skutečnépolohy. Z tohoto důvodu navrhujeme následující kompromis: body generujeme podleGaussova rozdělení, ale jen v hlavní rovině lokálního modelu. Docílíme toho tak,že zaměníme v rovnici (5.49) matici U za matici U. Tu získáme SVD rozklademstrukturní matice
U = V
s1 0 0
0 s2 0
0 0 s3
VT U = V
s1 0 0
0 s2 0
0 0 0
VT , (5.52)
u které nejslabší (normálový) směr zcela potlačíme. Statistika z takto spočítanýchbodů bude mít ostřejší extrém v optimální pozici, než kdybychom generovali bodyv celém objemu šupiny.
45
5 Verifikace a zpřesnění lokálního modelu
Projekce celého lokálního modelu
Druhou možností, jak měřit konzistenci lokálního modelu, je nalezení jeho plošnéhoprůmětu v obrazech a porovnání intenzit těchto ploch.Nazíráme-li na šupinu jako na elipsoid, definovaný izoplochou její funkce přísluš-
nosti (3.3), pak pro každý bod x na jeho povrchu platí rovnice
(x − x0)TS−1(x − x0) = 1 . (5.53)
Chceme-li nalézt průmět tohoto elipsoidu do obrazu I, hledáme množinu obrazovýchbodů u, které po zpětné transformaci do prostoru objektů vyhovují rovnici elipsoidu.Taková projekce je však nejednoznačná. Výsledný bod leží někde na paprsku pro-cházejícím optickým středem t. Rozepíšeme-li rovnici (2.2) do tvaru u = KR(x − t),potom pro bod na paprsku α(x − t) platí
α (x − t) = (KR)−1u . (5.54)
Zavedeme-li substituce β = 1/α a Q = KR, pak lze tuto zpětnou projekci přepsatdo tvaru
x = Q−1β u+ t . (5.55)
Tyto body v prostoru musí vyhovovat rovnici elipsoidu, takže po dosazení do (5.53)dostaneme rovnici(
Protože nás zajímá jen průmět okraje elipsoidu, uvažujeme jen ta řešení β, kdepaprsek protíná elipsoid jen v jednom bodě. Rovnice (5.56) má jen jediné řešení profixní u, pokud její diskriminant je rovene nule.Toto řešení nebude triviální, protože perspektivní průmět elipsoidu do roviny
není jednoduchou křivkou. Domníváme se však, že exaktní nalezení průmětů šu-piny do obrazů není třeba. Spokojíme se s přibližným řešením, protože sama hra-nice modelu je definována pouze přibližně a její přesná poloha není naší metodouvyžadována. Jde pouze o rozsah oblasti, kde budeme počítat konzistenci. Promít-neme tedy pouze elipsu danou průnikem elipsoidu s jeho hlavní rovinou – právě tavyjadřuje lokální aproximaci povrchu ve středu elipsoidu. Je pravda, že tak nezo-hledníme neurčitost šupiny danou její kulovostí (stejně tak jako u průmětu bodůpouze z hlavní roviny). Takové řešení je ale obecnější, protože nevyužívá speciálníchvlastností šupiny jako lokálního modelu. Druhou vlastností tohoto postupu je vyššícitlivost k orientaci modelu.V praxi postupujeme tak, že elipsu po částech linearizujeme, tj. promítáme její
vrcholy a několik mezilehlých bodů. Takto vzniklá oblast nám vyznačuje pixely,jejichž jasy nás zajímají. Z nich můžeme náhodným nebo jiným výběrem získatmnožinu obrazových bodů U pro další zpracování. Protože však obrazový rastr jenezávislý na perspektivním zobrazení modelu, nenajdeme obecně ke každému pixelu
46
Konzistence modelu s obrazy 5.2
o celočíselných obrazových souřadnicích korespondující celočíselný pixel v jiném ob-razu. Řešíme to tak, že zvolíme referenční obraz a ke každému jeho pixelu spadajícíhodo oblasti dané průmětem šupiny spočítáme korespondující neceločíselné souřadnicev ostatních obrazech.Nechť u1 je pixel v prvním obraze. Homografií (5.48) indukované rovinou lokál-
ního modelu získáme párový bod u2 ve druhém obraze. Bilineární nebo bikubickouinterpolací získáme jas ve druhém obraze.Referenční obraz můžeme volit libovolně. Doporučujeme však volit ten, který
obsahuje největší počet pixelů v průmětu, protože tak využijeme veškerou obrazovouinformaci.
5.2.2 Statistiky konzistence modelu s obrazy
Nechť Uj je množina obrazových bodů aproximujících šupinu v obraze Ij způsobempopsaným v předešlé části. Zvolenou dvourozměrnou interpolací můžeme získat in-tenzitu Lij v bodě uij ∈ Uj
Lij = Intrpl(Ij ,uij) (5.57)
a můžeme je sdružit do matice L ∈ M m×n pro m obrazů a n promítnutých bodů:
L = [Lij ] =
L11 . . . L1m
. . . . . .
Ln1 . . . Lnm
. (5.58)
Sloupce L·j této matice obsahují intenzity získané z jednoho obrazu j. Můžeme naně nahlížet jako na realizace náhodné veličiny o neznámém rozdělení. V jednotli-vých řádcích Li· jsou jasové hodnoty z různých obrazů, které by si měly vzájeměodpovídat. Naším cílem je najít statistiku toho, jak si tyto hodnoty odpovídají. Bu-deme ji nazývat PLIC (z angl. Polynocular Local Image Consistency), viz publikaciautora [C].1 Obecně půjde o zobrazení do množiny reálných čísel:
PLIC: (model, obrazy, kamery)→ R .
Čím vyšší bude hodnota PLIC, tím vyšší bude vzájemná konzistence mezi obrazy.Diskutujme nyní čtyři varianty výpočtu PLIC statistiky. Vzájemně se liší tím,
pro jak obecnou transformaci hodnot intenzit Tv (jak obecnou jasovou transformaci)jsou invariantní. Pokrývají rozsah od nejjednodušší identické transformace přes mo-notonní transformaci až po libovolné prosté zobrazení. Jak jsme uvedli v kapitole 5.1,obrazy jsou v reálných podmínkách deformovány mnoha vlivy, takže identita obrazův praxi téměř nenastane. Čím však připouštíme obecnější transformaci, tím více in-formace z obrazu ignorujeme. Na jednu stranu ztrácíme citlivost na deformace, nadruhou ztrácíme citlivost na vlastní obsah obrazů, na jejich podobnost, viz obr. 5.4.Popišme si tedy jednotlivé varianty PLIC:
1) Součet kvadrátů odchylek (Sum of Squared Differences, SSD). SSD
Tato statistika konzistence vychází z definice rozdílové funkce (5.23). Pro její správ-nou funkci musí být odpovídající intenzity obrazů shodné. Výpočet probíhá po ob-razových párech z množiny P a průměruje se jejich počtem |P|, stejně jako počtem1V předchozích publikacích [B, J] nalezneme funkci PLID (Polynocular Local Image Dissimilarity).Bez ztráty na obecnosti můžeme zavést PLIC = −PLID.
47
5 Verifikace a zpřesnění lokálního modelu
0 254 1
253 255 253
2 254 0
a) Vstupní obraz
0 4 1
3 5 3
2 4 0
b) Monotónní transformace
0 2 3
1 5 1
4 2 0
c) Prostá transformace
intenzita 0 1 2 253 254 255
pořadí intenzity 0 1 2 3 4 5
četnost 2 1 1 2 2 1
pořadí četnosti 0 3 4 1 2 5
d) Tabulka hodnot
Obrázek 5.4 Příklady deformace obrázku. Na ilustračním obrázku a) vidíme obraz ve tvaru kříže. Číselné hodnotyv každém pixelu vyjadřují intenzitu jasu. Pokud s obrázkem provedeme monotónní transformaci nahrazující hodnotyjasu jejich pořadím, dostaneme obrázek b). Všimněme si, že nám tato transformace kříž rozmazala. Použijeme-li ještěobecnější prosté zobrazení (v tomto případě pořadí četnosti jednotlivých jasů), dostaneme obraz, který se z lidskéhohlediska vstupnímu vůbec nepodobá c). Přesto jej statistika invariantní k prostému zobrazení bude považovat zakonzistentní.
promítaných bodů n. Aby šlo o statistiku konzistence, nikoliv rozdílnosti, je výsledeknásoben číslem −1:
PLIC1 =−1n|P|
|P|∑(r,s)∈P
n∑i=1
(Lir − Lis)2 (5.59)
Fua ve své práci [22] popisuje statistiku založenou na SSD, ale umožňující jejívýpočet ze všech použitých obrazů najednou bez průměrování párů. Výpočet využívástřední hodnoty korespondujících si pixelů
µ(i) =1m
m∑j=1
Lij
a vlastní statistika
PLIC1b =−1mn
n∑i=1
m∑j=1
(Lij − µ(i)
)2. (5.60)
Takto definovanou statistiku, ovšem vysčítanou přes všechny lokální modely, Fuanazývá meziobrazovou korelací intenzit (multi-image intensity correlation) .
2) Standardní korelační koeficient (Standard Correlation Coefficient, SCC).SCC
Druhou statistiku, kterou navrhujeme, je standardní korelační koeficient
PLIC2 =1|P|
|P|∑(r,s)∈P
cov(L·r, L·s)√cov(L·r) cov(L·s)
. (5.61)
Dosahuje hodnot v intervalu 〈−1, 1〉. Pokud zvolíme třídu zobrazení Tv jako lineární,pak ke statistickému rozhodnutí můžeme použít statistiku (5.61). Lineární funkci Tvnapř. odpovídá lambertovský povrch pozorovaný kamerami o různém zesílení signálua různé nulové úrovňi.
Spearmanův koeficient konkordance využívá pořadových (též rankových) korelací [39].Připouští jakoukoliv monotónní transformaci mezi intenzitami obrazů. Na rozdíl odPLIC1 a PLIC2 počítá konzistenci všech obrazů navzájem. Nejde tedy o středníhodnotu konzistence párů. Způsob výpočtu je následující. Nechť Rij je pořadí jasubodu i v obraze j; nabývá tak hodnot od jedné do celkového počtu promítanýchbodů. Dále nechť Ri =
∑mj=1Rij je součet pořadí hodnot jasů jednoho bodu přes
všechny (zvolené) obrazy. Střední hodnota Ri je rovna R = 12m(n+1). Pak Kendal-
lův koeficient v mezích 〈0, 1〉 je roven:
K =S
Smax, (5.62)
kde S je součet kvadrátů rozdílů pořadí od střední hodnoty pořadí přes všechnypromítnuté body a Smax je maximální možná hodnota S:
S =n∑
i=1
(Ri − R
)2a Smax =
n∑i=1
(im− R
)2.
Spearmanův koeficient konkordance odvodíme z Kendallova koeficientu normalizací:
PLIC3 =mK − 1m− 1
. (5.63)
Pro nezávislé veličiny je konkordance rovna 0, pro korelované 1 a pro negativněkorelované −1/(m− 1). Pro m > 2 nedosahuje koeficient hodnoty −1, protože sou-hlasnost a nesouhlasnost více než dvou veličin není symetrická. Všechny veličiny semohou shodovat, ale pokud náhodná veličina A je zcela v protikladu k C a veličinaB je také v protikladu k C, pak není možné, aby také A a B byly navzájem zcelanesouhlasné. Tyto veličiny se musí shodovat, protože ke každé pořadové náhodnéveličině (tedy i k C) existuje právě jedna veličina o inverzní konkordanci.
4) Vzájemná relativní informace (Mutual Relative Information, MIF). MIF
Tato statistika umožňuje nejobecnější transformaci mezi obrazy z navržených sta-tistik konzistence, tj. prosté zobrazení. Je to tím, že tato statistika není založena nakorelaci korespondujících si bodů, ale na entropii celé množiny [54]. Její normalizo-vaná hodnota je dána vztahem
PLIC4 =
∑mj=1H(L·j)−H(L·1 · L·2 · . . . · L·m)
max(H(L·j)
) , (5.64)
kde H(X·j) = −∑n
i=1 p(Xij) log2 p(Xij) je entropie promítnutých jasů Xi·. Pravdě-podobnost p(Xij) = nij/n je aproximována relativní četností jasů v buňkách zvolenévelikosti. Pravděpodobnost p(X·1 ·X·2 · . . . ·X·m) je relativní četností každého řádkumatice L.
49
5 Verifikace a zpřesnění lokálního modelu
Na závěr této sekce uveďme postup výpočtu statistiky konzistence:
Algoritmus 5.1 Výpočet statistiky konzistence.1. Zvol projekci modelu do obrazu.2. Zvol obrazy, ze kterých budeš počítat statistiky konzistence. Pro každý obraz:
a) Promítni lokální model pomocí známé projekční matice M. V obraze tak získejuspořádanou bodovou množinu.
b) Dvourozměrnou kubickou interpolací urči intenzitu v každém takovém bodě.3. Zvol statistiku konzistence.4. Vyžaduje-li statistika konzistence výpočet po korelačních párech, zvol páry obrazů.5. Spočítej korelační koeficient c z uspořádaných množin intenzit a zvolené statistiky kon-zistence. Pokud se koeficient počítá po obrazových párech, konečný koeficient spočítejjako průměrnou hodnotu z hodnot každého páru.
5.3 Verifikace jako statistické rozhodnutí
Nyní jsme schopni k danému lokálnímu modelu, zvolené projekci a statistice konzis-tence spočítat hodnotu konzistence PLIC. Naším úkolem je rozhodnout, zda modelbudeme považovat za konzistentní, či nikoliv. Byli bychom rádi, kdyby toto rozhod-nutí matematicky vyjadřovalo závislost testovaných veličin. Pokusíme se tedy využítnástrojů matematické statistiky.Nechť jsou porovnávané řetězce intenzit získané projekcí modelu do dvou různých
obrazů náhodné veličiny X1 a X2. Tyto veličiny se skládají z intenzit A či B a šumuN . Rozeberme si zvlášť dva případy:1. Model je správně parametrizován na povrchu objektu; veličiny můžeme rozepsat
X1 = A+N1X2 = Tv(A) +N2 .
(5.65)
2. Model je nesprávně parametrizován mimo povrch objektu; pak veličiny rozepí-šeme
X1 = B1 +N1X2 = Tv(B2) +N2 .
(5.66)
Vidíme, že v prvním případě, ve kterém je model správně umístěn a orientován, ob-sahují obě náhodné veličiny závislou složku A (danou texturou a formováním jasu nalambertovském povrchu). Dále se připojuje nezávislá část kvantově-mechanického atepelného šumu CCD senzoru a šumu diskretizačně-kvantizačního N1 a N2. Roz-dělení této nezávislé složky se blíží součtu Poissonova a normálního rozdělení. Vedruhém případě je závislá složka nahrazena složkou nezávislou B1 a B2. Jejich roz-dělení závisí na rozdělení jasů v promítaných oblastech, Je tedy různé pro obě složkyB1 a B2 a nelze se spoléhat, že by bylo normální či rovnoměrné. Koeficienty α a βvyjadřují lineární posun vlivem rozdílnosti senzorů.Náš test by měl zjistit, zda je ve veličinách X1 a X2 závislá složka A nebo
nezávislá složka B. Matematická statistika test závislosti nenabízí. Podobnost veličinX1 a X2 však vyjadřují definované statistiky konzistence založené na korelacích.Nabízí se tedy možnost testovat nekorelovanost veličin a výsledek negovat.
50
Verifikace jako statistické rozhodnutí 5.3
délka řetězce 5 10 100 500 1000
kritická hodnota 0,829 0,619 0,197 0,088 0,062
Tabulka 5.1 Kritické hodnoty testu nekorelovanosti standardního korelačního koeficientu.Uvedeny jsou kritické hodnoty pro několik hodnot délky korelačního řetězce při hladiněvýznamnosti 0,05.
délka řetězce 5 10 100 500 1000
kritická hodnota 0,900 0,636 0,197 0,088 0,062
Tabulka 5.2 Kritické hodnoty testu nekorelovanosti Spearmanova korelačního koefici-entu. Uvedeny jsou kritické hodnoty pro několik hodnot délky korelačního řetězce při hladiněvýznamnosti 0,05.
Testování nekorelovanosti standardního korelačního koeficientu se opírá o tvr-zení, že vztah
T =c√1− c2
√n− 2 (5.67)
pro řetězec délky n má Studentovo rozdělení, jsou-li veličiny (5.66) nezávislé [5,str. 117]. Zjistíme-li hodnoty pro hladinu významnosti α = 0,05, pak dostanemekritické hodnoty uvedené v tab. 5.1.
Podobně můžeme testovat Spearmanův korelační koeficient. U něj však neníomezující podmínka na normální rozdělení náhodných veličin (5.66). Jejich převodemna pořadí získáme rovnoměrné rozdělení a Spearmanův korelační koeficient se testujevůči hodnotám uvedeným v tab. 5.2 [5, str. 235]. Toto testování je tedy čistší nežtest korelačního koeficientu, protože předpoklad normálního rozdělení není obecněsplněn.
Oba testy mají jednu podstatnou nevýhodu. Tím, že testují nekorelovanost a nezávislost, jsou velmi tolerantní. Experimenty v kapitole 6.3.3 ukazují, že délka kore-lačního řetězce musí být okolo sta a více hodnot. Pro takto dlouhý řetězec vycházíkritické hodnoty pod 0,2, tedy za nekonzistentní považujeme pouze modely s koefi-cientem menším než tato hodnota. Podíváme-li se na histogram rozložení hodnotkorelačního koeficientu PLIC2 na obr. 5.5, vidíme, že většina modelů má Spearma-novu konkordanci nad 0,8. Mez, kde hledat vhodnou prahovou hodnotu konzistenceleží v těchto případech mnohem výše, někde v rozmezí 0,5 až 0,8.
Pokusili jsme se hledat jinou metodu testování než je nekorelovanost a našli jiv kontingenčních tabulkách. Pomocí nich lze testovat nezávislost veličin [5, str. 209].I zde však diskriminativní mez příliš nezvýšíme. Kromě toho přibude problém s roz-dělením intenzit korelačních řetězců do dostatečně početných tříd.
Ukazuje se, že vhodný práh je závislý na albedu, funkci odrazivosti povrchua osvětlení. Bude-li např. část povrchu pokrytá velmi kontrastní texturou, budemoci být kritická hodnota prahu vyšší než u méně kontrastních částí povrchu. Jinouhodnotu konzistence dostaneme s jiným osvětlením scény. Z tohoto důvodu má cenupoužívat jednu kritickou hodnotu konzistence jen pro objekty se stejnou texturoua stejnou odrazivostní funkcí na celém povrchu. Dále se ukázalo, že jakýkoliv testnekorelovanosti či nezávislosti veličin je velmi benevolentní. Pro praktickou realizacije vhodné použít empiricky nalezené prahy pro konkrétní rekonstruovanou scénu.
51
5 Verifikace a zpřesnění lokálního modelu
Vstupní a výstupní veličiny takto navržené verifikace zobrazuje následující dia-gram:
VerifikaceModel
ProjekceObrazy
Rozhodnutı konzistentnı
nekonzistentnı
Kriticka hodnota konzistence Ct (0,5. . . 0,8)Pocet promıtanych bodu n (500)
Zleva vstupují data v podobě parametrů lokálního modelu, projekční matice a mi-nimálně dva obrazy z různých pozorovacích míst, překrývající se svým obsahem.Shora jsou zakresleny parametry metody. Kritická hodnota konzistence Ct závisí napozorovaném povrchu a podmínkách snímání obrazů. Druhým méně významnýmparametrem je počet n náhodně vygenerovaných bodů aproximujících jeden lokálnímodel a stanovující tak délku korelačního řetězce. V závorkách jsou uvedeny ty-pické hodnoty těchto parametrů. Celou metodu verifikace můžeme zapsat pomocínásledujícího algoritmu:
Algoritmus 5.2 Verifikace lokálního modelu.1. Zvol práh konzistence Ct buď na základě statistického testu nezávislosti nebo empirickypřímo pro danou aplikaci.
2. Pro každý lokální model pozorovaného objektu proveď:a) Spočítej statistiku konzistence c, viz algoritmus 5.1
b) Rozhodni, že lokální model je
konzistentní právě když c ≥ Ct ,
nekonzistentní v jiném případě.
Takto navržený algoritmus je nezávislý na typu lokálního modelu i na zvolené metoděprojekce do obrazů. Důležité je, aby projekce vystihovala geometrii utváření obrazu,tj. aby v případě, že snímáme pespektivní kamerou šlo o perspektivní projekci. Takélze, podle typu aplikace, zvolit vhodnou statistiku konzistence.
−0.2 0 0.2 0.4 0.6 0.8 10
2
4
6
8
10
12
Spearman concordance
% o
f da
tapo
ints
a) Konev
−0.2 0 0.2 0.4 0.6 0.8 10
0.5
1
1.5
2
2.5
3
3.5
4
Spearman concordance
% o
f da
tapo
ints
b) Obličej
Obrázek 5.5 Nevhodnost testu nekorelovanosti pro rozhodnutí o konzistenci modelu. Na obrázcích vidíme dvatypické histogramy hodnot PLIC3 pro dvě reálné scény.
52
Zpřesnění parametrů modelu 5.4
Nejčastější aplikací verifikačního algoritmu je vyřazení nekonzistentních lokálníchmodelů ze souboru popisující globální model povrchu rekonstruovaného objektu.Funkčnost takového mechanismu demonstrujeme na reálných objektech v kapitole 6.
5.4 Zpřesnění parametrů modelu
Předcházející kapitola umožnila vyloučit ze souboru lokálních modelů popisujícíchglobální model povrchu ty, které jsou nekonzistentní s předloženými obrazy. V tétokapitole navrhneme postup, jak změnit parametry lokálního modelu tak, aby maxi-malizoval zvolenou statistiku konzistence s obrazy.
Uveďme důvody, proč optimalizovat parametry lokálního modelu:• Z různých důvodů jsou lokální modely nepřesně vygenerované a chceme dosáh-nout jejich vyšší přesnosti. Mezi tyto důvody patří:– Pro generování lokálních modelů byly použity zjednodušené postupy, napří-klad z důvodů zrychlení procesu.
– Pro generování modelů byly použity jiné, méně přesné techniky, než je ge-ometrické stereo.
– Parametry modelu byly pouze odhadnuty, například ze znalosti apriorníhomodelu.
– Byly generovány modely v celé škále možných hodnot parametrů a verifikacíbyla provedena jejich hrubá selekce.
• Protože verifikační algoritmus (není-li vyladěn na konkrétní scénu) je z principuvelmi tolerantní, stále v souboru zbudou relativně nekonzistentní modely. Ježádoucí, aby jejich konzistence byla zvýšena.
• Máme nové obrazy rekonstruovaného objektu (z lepšího pozorovacího úhlu, s vyš-ším rozlišením, lepším osvětlením). Snímání těchto obrazů mohlo být realizovánona základě analýzy přesnosti rekonstrukce prvotního modelu.
5.4.1 Optimalizované parametry
Hlavními parametry lokálního modelu jsou jeho poloha a orientace. Ačkoliv můžemodel popisovat i jiné charakteristiky (například jeho věrohodnost), zaměříme sepři optimalizaci pouze na tyto dvě základní.Poloha je určená třemi souřadnicemi středu ve 3D prostoru x0 = [x y z ]T.Orientace je určená normálovým směrem n. Pro jeho určení potřebujeme dva úhly,azimut ϕ a elevaci ψ.
Jednou z možností je optimalizovat polohu a orientaci zároveň, to znamená maxi-malizovat statistiku konzistence přes pět parametrů (tři parametry pro polohu a dvapro orientaci). Při optimalizaci polohy budeme muset zabránit tomu, aby se modelyspojily do shluků s lokálním maximem konzistence a přestaly rovnoměrně pokrý-vat povrch. Můžeme tomu bránit odpudivou silou, která vzroste, pokud se lokálnímodely začnou překrývat. Tento přístup má však tu nevýhodu, že budeme muset op-timalizovat přes všechny modely současně. Tím narůstá složitost algoritmu. Místotoho navrhujeme přijmout předpoklad, že počáteční orientace modelu není zcelašpatně – řekněme, že odchylka je do 30 od správného směru normály. Tuto hru-bou znalost orientace můžeme využít k optimalizaci pozice pouze podél současnéhosměru normály, takže snížíme počet optimalizovaných parametrů o dva a umožnímenezávislou optimalizaci každého modelu zvlášť. Musíme si však dát pozor, protožev tomto případě je způsob optimalizace jednoho parametru závislý na optimalizacizbylých dvou, takže záleží na pořadí, ve kterém jej aplikujeme.
53
5 Verifikace a zpřesnění lokálního modelu
5.4.2 Postup zpřesnění lokálního modelu
Zpřesnění parametrů lokálního modelu popisuje následující algoritmus:
Algoritmus 5.3 Zpřesnění lokálního modelu.1. Pro každý lokální model pozorovaného objektu proveď:
a) Ze současných hodnot parametrů modelu spočítej statistiku konzistence c0,viz algoritmus 5.1
b) Opakuj zvolených t iterací:i. Nalezni optimální hodnoty tří parametrů maximalizující statistiku konzis-tence. Tuto hodnotu označ ct. Parametry jsou: posunutí modelu ve směrunormálového vektoru, azimut a elevace určující úhel od normálového vektoru.
ii. Pokud došlo ke zlepšení, tj. ct > ct−1, zaměn okamžité hodnoty parametrů zahodnoty optimální.
Jako optimalizační metodu jsme zvolili simplexovou, protože nevyžaduje výpočetderivací konzistentní statistiky. Protože analytické vyjádření derivace není možné,museli bychom pro gradientní optimalizační metody derivace odhadovat.Co se týká počtu iterací t, pro naše experimenty jsme se spokojili pouze s jed-
ním průchodem. Případnou další iteraci doporučuji v případě, že nám jde o velkoupřesnost orientace normály.
54
6 Experimenty ověřující teorii
Tato kapitola ukazuje výsledky experimentů, které jsem provedl, abych ověřil správ-nost metod verifikace a zpřesnění teoreticky navržených v kapitole 5. V těchto testechjsem rekonstruoval jednoduchý, názorný, ale reálný objekt. Nepoužíval jsem umělegenerovaná data, protože hlavní náročnost rekonstrukce spočívá v překonání mnohavzájemně se sčítajících a na sobě často závislých faktorů, které vytváří reálná scénaa snímání reálnou kamerou. Výčet nepříznivých faktorů, které tyto reálné podmínkyzpůsobují, byl popsán v kapitole 5.1.3. Ke každému experimentu jsem připojil ko-mentář ve formě hesel. Číslo komentáře se shoduje s číslem obrázku, na kterém jsouzobrazeny výsledky relevantního experimentu.
6.1 Snímací zařízení
Pro účely stereorekonstrukce byl postaven prototyp zařízení na snímání až čtyř syn-chonizovaných šedotónových obrazů. Digitální kamery Pulnix TM-9701 s rozlišením484 × 760 a osmibitovou barevnou hloubkou byly namontovány na speciálně navr-žený pevný duralový rám zajišťující mechanickou tuhost celého zařízení, viz obr. 6.1.Směr pohledu podle vertikální osy lze nastavit zvlášť u každé kamery, podle horizon-tální je směr nastavitelný společně pro dvojici kamer. Vzdálenosti kamerových párůje možno upravit v rozmezí 70 až 310mm v horizontálním směru a 90 až 300mm vesměru vertikálním. Vzdálenost rekonstruovaného objektu od kamer byla přibližně80 cm. Používali jsme c-mount objektivy Tamron 25mm/1,6. Kamery byly připo-jeny k počítači přes digitizér Data Translation DT3157 a speciálně navrženou deskupro synchronizaci snímání.
468
428
4 3
12
256
261
Obrázek 6.1 Snímací zařízení. Čtyři kamery jsou upevněny v pevném duralovém rámuumístěném na optické lavici Krochmann v laboratoři Centra strojového vnímání. Vzdálenostikamer odpovídají jejich nastavení při experimentech.Rozměry jsou uvedeny v milimetrech.
55
6 Experimenty ověřující teorii
Kamery byly kalibrovány pomocí kalibračního rovinného obrazce o 64 bodech.Kalibrace
Tento obrazec byl sejmut ve třech vzdálenostech od kamer [53]. Relativní posun byl24mm a 26mm. Průměrná reprojekční chyba se pohybovala okolo 0,2 pixelu.
6.2 Experimentální rovinný objekt
Objektem pro experimentování s PLIC statistikami byla zvolena, bez újmy na obec-nosti, rovina. Má tu výhodu, že jak relativní poloha tak orientace mnoha lokálníchmodelů je analyticky dána bez ohledu na měřítko a můžeme snadno stanovit rela-tivní přesnost měření. Nemáme totiž k dispozici přesnější měření získané nezávisloumetodou, abychom mohli výsledky porovnat. Další výhodou roviny je, že nevznikáchyba aproximace, když rovinu nahrazujeme rovinnými lokálními modely (kapitola5.2.1). Na rovině také nemůže dojít k samozákrytům a stínům – jevům, které závisína pozorovaném úhlu, a tudíž diskreditujícím verifikační algoritmus. Požadavek napovrch roviny byl ten, aby co nejméně vyvolával odlesky.Popsané podmínky dobře splňovala broušená duralová deska s nerovností podMěřený objekt
0,02mm s matným povrchem potlačujícím odlesky. Jejím nasnímáním jsme získalisadu vstupních obrazů o minimu přídavných deformací popsaných v kapitole 5.1.3.Jak plyne z výpočtu PLIC statistik, je důležité zaručit nehomogenitu textury po-Projekce textury
vrchu, protože jinak by byl model konzistentní v jakékoliv poloze a orientaci. Protožedural je materiálem s velmi slabou texturou (minimálně vzhledem k testovanémurozlišení), pomohli jsme si projekcí náhodné textury diaprojektorem. Průměr tex-turových zrn činil v obraze asi dva pixely. Při této velikosti jsme dosahovali optimanejvyššího prostorového rozlišení projekce k fyzickému rozlišení kamer. Velikost tex-turových zrn na povrchu desky činil asi 2 pixely na milimetr.Rovina byla osvětlena pouze projekcí textury (se zanedbatelnou složkou roz-
ptýleného světla v tmavé místnosti). Clona kamer byla nastavena tak, aby nedošlok přeexpozici ani podexpozici snímků.Čtyři vstupní obrazy (jeden z nich spolu s jeho jasovým histogramem ukazujeStereo
obr. 6.2) byly uspořádány do dvou horizontálních a dvou vertikálních párů. Algorit-
150 200 250 300 350 400 450 500 550
200
250
300
350
400
450
0 50 100 150 200 2500
0.2
0.4
0.6
0.8
1
1.2
intensity value
Obrázek 6.2 Obraz rovinné scény s promítnutou náhodnou texturou a jeho jasový histo-gram. Měřenou rovinou byla broušená duralová deska. Pro redukci dat a potlačení okrajo-vých jevů byla oblast zájmu zúžena na obdélník 80× 95mm. Pro snadnou orientaci byla vescéně vyznačena provázky, viditelnými v obraze jako černé linie. Náhodná diskrétní texturabyla na scénu promítnuta diaprojektorem.
56
Experimentální rovinný objekt 6.2
mem stabilního párování (viz kapitolu 2.2.2) byly nalezeny disparitní mapy a z nichspočítán jeden mrak 3D bodů. Jejich počet byl 629 064.3D body ze sterea jsem proložil lokální modely zvané šupiny (kapitola 3.1). Generování šupin
Neuvedu-li jinak, je velikost šupin používaných v této kapitole 10mm. Typická chybapolohy šupiny na našem čtyřkamerovém systému s výše popsanou rekonstrukcí činí0,2mm (jde o směrodatnou odchylku vzdálenosti středů šupin od povrchu); za pří-znivých světelných a texturních podmínek až 0,05mm.Každá šupina byla aproximována množinou 3D bodů ležících na její hlavní rovině Projekce šupiny na rovinu
(kapitola 5.2.1). Tyto body byly promítány do vstupních obrazů. V zájmu přehled-nosti chování PLIC statistik byla zvolena projekce pouze do jedné dvojice obrazů,viz obr. 6.3a. Obrázek ukazuje, že body jsou promítnuté do vzájemně odpovídají-cích si oblastí obrazů bez pozorovatelných chyb. Přesně tak, jak bychom očekávalipro správně umístěný a orientovaný model. Prozkoumáme-li však blíže číselné cha-rakteristiky bodů, např. pořadí jasů, zjistíme, že nejsou v jednom a druhém obraze
2− 42
4− 79
6−122
7−190
1− 39
5−120
3− 49
310 320 330 340 350
375
380
385
390
395
400
3− 47
4− 75
6−113
7−184
2− 42
5−109
1− 41
370 380 390 400 410
370
375
380
385
390
395
a) Původní poloha modelu.
1− 41
4− 83
6−126
7−189
2− 43
5−123
3− 47
310 320 330 340 350
375
380
385
390
395
400
3− 43
4− 77
5−112
7−186
2− 43
6−114
1− 42
370 380 390 400 410
370
375
380
385
390
395
b) Poloha maximalizující SSD.
Obrázek 6.3 Korespondence průmětů bodů lokálního modelu. Detail levého a pravéhoobrazu s průměty sedmi bodů náležejících jednomu lokálnímu modelu a) v původní polozemodelu ze sterea a b) v poloze maximalizující konzistenci modelu s obrazy. Číselné hodnotyu každého průmětu vyjadřují vzájemné pořadí a absolutní velikost bikubicky interpolovanýchhodnot intenzit, zaokrouhlených zde pro účely zobrazení.
57
6 Experimenty ověřující teorii
totožné. Často je několik průmětů s nepříliš rozdílným jasem navzájem zaměněno.Svědčí to o tom, že buď (i) i přes naší snahu přichystat ideální podmínky mámeměření s chybami a zjednodušeními (hlavně s chybou kalibrace, dále s diskretizací as kvantizací, s vadami optiky, s tepelným šumem na čipu) a (ii) poloha modelu nenípřesná. Posuneme-li model do polohy maximalizující PLIC statistiku, viz obr. 6.3b,pozorujeme zlepšení v pořadí bodů. Pouze jedna dvojice bodů narušuje absolutnísoulad. V reálném případě nepromítáme pouze sedm bodů, ale daleko více, takžejejich vzájemné hodnoty jasů jsou daleko deskriptivnější. Vhodný počet bodů budediskutován dále.
6.3 Chování statistik konzistence
V této části ukážeme chování statistik konzistence, definovaných v kapitole 5.2.2,při změnách polohy nebo orientace jednoho lokálního modelu. Přesvědčíme se, zdaje možné na základě konzistence lokálního modelu s obrazy vyčíslené pomocí jednéz PLIC statistik verifikovat polohu modelu. Ukážeme si průběhy jednotlivých statis-tik, porovnáme hodnoty jejich maxim počítané pro různé dvojice obrazů a zaměřímese na volbu parametrů výpočtu konzistencí.
6.3.1 Posun lokálním modelem ve směru normályx
y
z
n
Posun+
-
Objektová rovina
Pro účely verifikace potřebujeme, aby statistiky konzistence v celém oboru posunutílokálního modelu vykazovaly jedno výrazné globální maximum, a to v oblasti správnépolohy modelu. Napočítejme tedy hodnoty konzistencí (kapitola 5.2.2) pro různépolohy lokálního modelu. Posunujme jím ve velmi širokém pásmu podél jeho normály.Z průběhů zobrazených na obr. 6.4 můžeme vyčíst následující komentář:
1. Všechny PLIC statistiky mají jasné globální maximum při posouvání ve směruKomentář 6.4.
normály modelu; ve velmi širokém pásmu ±10mm je to maximum jediné.
Obrázek 6.4 Průběh PLIC při posouvání lokálním modelem. Správně orientovaným lokálním modelem o průměru10mm bylo posouváno ve směru jeho normálového vektoru o ±20mm s krokem 0,2mm (kladná výchylka směrem kekamerám). Pro každou takovou polohu byly z jednoho páru obrazů (obrazy 1 a 2) spočítány čtyři PLIC statistiky podlekapitoly 5.2.2. Vlevo jsou zobrazeny jejich absolutní hodnoty (levé měřítko patří SSD, pravé ostatním konzistencím),vpravo pak relativní v procentech – maximu jedné statistiky odpovídá hodnota 100% a minimu 0%. Délka korelačníhořetězce byla n = 1000 prvků.
2. Maxima jsou blízko (0,25mm) původní polohy modelu dané proložením bodůze sterea. Protože předpokládáme, že chyba sterea může činit několik desetinmilimetru, je tato hodnota v toleranci.
3. Maxima jednotlivých statistik jsou si navzájem velmi blízko. Z toho vyplývá, žestatistiky jsou k vyjádření konzistence navzájem zaměnitelné.
4. Průběhy SSD, SCC a SpC jsou velmi podobné, u SSD a SCC jsou téměř totožné(vyplývá to z faktu, že SCC je normalizovaný SSD).
5. Hodnoty MIF při posunu modelem z místa maximální konzistence k 5mm klesajístrměji, než zbylé statistiky. MIF tak z tohoto pohledu vykazuje větší diskrimi-nační sílu pro účely verifikace.Tato pozorování se týkala globálních průběhů konzistencí. Zaměřme nyní naši Detail maxima PLIC
pozornost do oblastí maxim konzistence. Připomeňme, že poloha modelu maxima-lizující jeho konzistenci s obrazy, je pokládána za nejlepší odhad jeho správnéhoumístění. Protože takové umístění reálného objektu je v jednom časovém okamžikupouze jedno, měly by všechny PLIC statistiky mít maximum ve stejné poloze. Jakje tento předpoklad podpořen měřením na rovinném objektu ukazuje obrázek 6.5.Pro možnost srovnání jsou průběhy ukázány pro devět různých lokálních modelů.1. Maxima všech čtyř PLIC se téměř shodují (jejich směrodatná odchylka na jed- Komentář 6.5.
nom modelu je okolo 0,02mm).2. Všechny modely mají zápornou odchylku svého maxima od původní polohy. Tatoodchylka zde přibližně činí 0,25mm. Svou vysokou stabilitou nabádá k hledánípříčiny. Viz také komentář k obrázku 6.6.Z předchozího experimentu plyne, že různé PLIC statistiky mají poměrně přesné PLIC z různých
párů obrazůspolečné maximum. Tyto statistiky byly vždy spočítány z jednoho stejného páruobrazů. Můžeme se ptát, zda maximum z jiných dvojic obrazů bude ležet ve stejnépozici modelu. Využijeme toho, že naše snímací zařízení umožňuje získat čtyři ob-razy a spočítejme konzistenci čtyř sousedních párů. Poněkud překvapující výsledekzachycuje obrázek 6.6. Můžeme k němu učinit následující pozorování:1. Maxima konzistence z různých párů obrazů jsou vzájemně posunutá se směro- Komentář 6.6.
datnou odchylkou σmax = 0,5mm.2. Pořadí a dokonce i poloha všech maxim jednoho modelu pro jednu dvojici ob-razů je stabilní. To znamená, že lokální model je podle každého páru obrazůkonzistentní v trochu jiné poloze.
Tento experiment ukázal, že optimální hodnoty konzistencí z různých párů obrazůvykazují velkou rozdílnost. Jak si to vysvětlit? Vždyť každý obraz zobrazuje totožnýobjekt. Jsou snad přetrvávající deformace i v takovýchto ideálních podmínkách na-tolik silné, že způsobí rozdílnou polohu maxim?Myslíme si, že tomu tak není. Tento jev si vysvětlujeme rozdílnou chybou ka-
librace kamer. Každá je totiž kalibrována nezávisle. Tento závěr potvrzuje i pozo-rování 3D izolovaných bodů získaných stereokorespondenčním algoritmem a slouče-ných z několika párů obrazů. Jsou totiž rozmístěny po vrstvách. Body v každé vrstvěvznikly z jiného páru. Sdružením bodů ze všech párů při jejich prokládání lokálnímimodely dojde k průměrování polohy, a tím i k celkovému zpřesnění rekonstrukce.Na základě tohoto vysvětlení můžeme učinit následující závěr: (i) pokud bychom
chtěli zpřesnit polohu modelu na základě maximalizace PLIC, jsme omezeni (stejnějako u stereorekonstrukce) přesností kalibrace a (ii) potvrzuje se, že užití více párůobrazů – za podmínky, že dobře zobrazují místo modelované lokálním modelem–zpřesní výsledek vlivem průměrování. Předpokládáme, že chyba kalibrace je blízkáGaussovu rozdělení. Přesnost kalibrace by se zvýšila pomocí metody vyrovnánísvazku paprsků.
59
6 Experimenty ověřující teorii
−0.5 −0.4 −0.3 −0.2 −0.1 0 0.1 0.2 0.3 0.4 0.50
10
20
30
40
50
60
70
80
90
100σ
max = 0.025
move [mm]
cons
iste
ncy
mea
sure
[%]
SSD−0.26SCC−0.26SpC−0.30MIF−0.29
−0.5 −0.4 −0.3 −0.2 −0.1 0 0.1 0.2 0.3 0.4 0.50
10
20
30
40
50
60
70
80
90
100σ
max = 0.0065
move [mm]
cons
iste
ncy
mea
sure
[%]
SSD−0.20SCC−0.19SpC−0.18MIF−0.18
−0.5 −0.4 −0.3 −0.2 −0.1 0 0.1 0.2 0.3 0.4 0.50
10
20
30
40
50
60
70
80
90
100σ
max = 0.016
move [mm]
cons
iste
ncy
mea
sure
[%]
SSD−0.26SCC−0.23SpC−0.22MIF−0.23
−0.5 −0.4 −0.3 −0.2 −0.1 0 0.1 0.2 0.3 0.4 0.50
10
20
30
40
50
60
70
80
90
100σ
max = 0.015
move [mm]
cons
iste
ncy
mea
sure
[%]
SSD−0.22SCC−0.23SpC−0.21MIF−0.25
−0.5 −0.4 −0.3 −0.2 −0.1 0 0.1 0.2 0.3 0.4 0.50
10
20
30
40
50
60
70
80
90
100σ
max = 0.03
move [mm]
cons
iste
ncy
mea
sure
[%]
SSD−0.21SCC−0.23SpC−0.21MIF−0.16
−0.5 −0.4 −0.3 −0.2 −0.1 0 0.1 0.2 0.3 0.4 0.50
10
20
30
40
50
60
70
80
90
100σ
max = 0.027
move [mm]
cons
iste
ncy
mea
sure
[%]
SSD−0.22SCC−0.25SpC−0.26MIF−0.28
−0.5 −0.4 −0.3 −0.2 −0.1 0 0.1 0.2 0.3 0.4 0.50
10
20
30
40
50
60
70
80
90
100σ
max = 0.012
move [mm]
cons
iste
ncy
mea
sure
[%]
SSD−0.18SCC−0.18SpC−0.18MIF−0.20
−0.5 −0.4 −0.3 −0.2 −0.1 0 0.1 0.2 0.3 0.4 0.50
10
20
30
40
50
60
70
80
90
100σ
max = 0.033
move [mm]
cons
iste
ncy
mea
sure
[%]
SSD−0.24SCC−0.21SpC−0.21MIF−0.28
Obrázek 6.5 Detailní průběhy PLIC při posouvání lokálními modely. Zobrazena je závislostPLIC na posouvání modely jako u obrázku 6.4. Detailně je však ukázáno okolí maxim (posuno ±0,5mm, krok 0,005mm), která jsou zvýrazněna svislou čarou. Hodnota jejich polohyv milimetrech je uvedena v legendě každého grafu. Průběhy jsou ukázány pro osm lokálníchmodelů, graf vlevo nahoře je pro totožný model jako průběh na obrázku 6.4.
60
Chování statistik konzistence 6.3
−5 0 50
20
40
60
80
100µ
max = −0.087
σmax
= 0.54
move [mm]
cons
iste
ncy
mea
sure
[%]
1−2 −0.252−4 −0.703−4 +0.601−3 +0.00
−5 0 50
20
40
60
80
100µ
max = −0.063
σmax
= 0.54
move [mm]
cons
iste
ncy
mea
sure
[%]
1−2 −0.202−4 −0.703−4 +0.601−3 +0.05
−5 0 50
20
40
60
80
100µ
max = −0.1
σmax
= 0.51
move [mm]
cons
iste
ncy
mea
sure
[%]
1−2 −0.202−4 −0.703−4 +0.551−3 −0.05
−5 0 50
20
40
60
80
100µ
max = −0.087
σmax
= 0.54
move [mm]
cons
iste
ncy
mea
sure
[%]
1−2 −0.252−4 −0.703−4 +0.601−3 +0.00
−5 0 50
20
40
60
80
100µ
max = −0.075
σmax
= 0.56
move [mm]
cons
iste
ncy
mea
sure
[%]
1−2 −0.252−4 −0.703−4 +0.651−3 +0.00
−5 0 50
20
40
60
80
100µ
max = −0.075
σmax
= 0.52
move [mm]
cons
iste
ncy
mea
sure
[%]
1−2 −0.252−4 −0.653−4 +0.601−3 +0.00
−5 0 50
20
40
60
80
100µ
max = −0.037
σmax
= 0.53
move [mm]
cons
iste
ncy
mea
sure
[%]
1−2 −0.202−4 −0.653−4 +0.601−3 +0.10
−5 0 50
20
40
60
80
100µ
max = −0.1
σmax
= 0.47
move [mm]
cons
iste
ncy
mea
sure
[%]
1−2 −0.202−4 −0.653−4 +0.501−3 −0.05
Obrázek 6.6 Průběhy SCC z různých párů obrazů při posouvání modelem. V legendějsou uvedeny indexy obrazů (podle obr. 6.1b), ze kterých byl daný průběh SCC počítán.Dále je tam uveden index maxima. Vpravo nahoře je vypsána střední hodnota maxim µmaxa odchylka σmax všech čtyř párů. Průběhy jsou vykresleny pro stejné lokální modely a vestejném pořadí jako na obr. 6.5.
61
6 Experimenty ověřující teorii
6.3.2 Natáčení lokálního modelu
n
oϕ
ψ
Objektová rovina
Podobně jako jsme sledovali hodnoty konzistenčních statistik při posouvání lokálnímmodelem, zatímco jeho orientace zůstávala konstantní, podíváme se nyní na tytoprůběhy při otáčení modelem za stálé polohy jeho středu. Otáčením rozumíme změnusměru normálového vektoru n o elevační úhel ψ podle osy o. Ta leží v rovině kolména normálu a její směr je dán azimutem ϕ. Průmět osy x do normálové roviny jetotožný s osou o při ϕ = 0. Protože modelujeme rovinný objekt, očekáváme, žečím větší bude úhel mezi normálou modelu a normálou měřené roviny, tím menšíkonzistenci naměříme. Zde je komentář k obrázku 6.7, který zobrazuje výsledektohoto experimentu:1. Maximální hodnoty všech čtyř statistik vycházejí téměř v původní poloze mo-Komentář 6.7.
delu; maximum je nalezeno v prvním diskrétním kroku na ψ = 0,74 při přibližněstejném azimutu ϕ = −60.
2. Všechny PLIC klesají s rostoucím náklonem od skutečné polohy roviny, a tovšemi směry přibližně stejně rychle. Monotónnost je narušena až při náklonech70 až 90, tj. v poloze, kdy je model téměř kolmý ke skutečné rovině.
3. Vzájemná konzistence (MIF) je u natáčení stejně jako u posuvu citlivější nežostatní statistiky. Také tady však její hodnoty více kolísají a vytvářejí lokálnímaxima.
Ze všech pozorování chování konzistenčních statistik na ideální rovině můžeme tvr-dit, že odpovídají teoretickým předpokladům a vykazují vhodné vlastnosti pro účelyverifikačního algoritmu.
6.3.3 Volba parametrů verifikace
Lokálními modely jsme dosud posouvali pro fixní parametry výpočtu PLIC statistik.Nyní se zaměřím na volbu těchto parametrů: druh průmětu, délka korelačního řetězcea práh konzistence.
Průmět z objemu modelu či jeho hlavní roviny.
Některé typy lokálních modelů mohou popisovat 2D povrch nikoliv svou dvouroz-měrnou, ale třírozměrnou reprezentací. Příkladem takové reprezentace je šupinovýmodel (kap. 3.1), u které třetí rozměr vyjadřuje věrohodnost modelu. Čím je šu-pina plošší, tím je větší pravděpodobnost, že náleží skutečnému povrchu. A naopak,kulová šupina s velkým objemem vykazuje vysokou nejistotu. Proč tedy nevyužíttéto informace a nepromítat body z celého objemu modelu? Očekávali bychom, žeoproti projekci pouze z hlavní roviny bude konzistence rozostřena, s nižší absolutníhodnotou maxima. Umožní nám to diskriminaci kulovějších modelů s nižší míroujistoty. Ukažme si to na příkladě: Při projekci bodů z hlavní roviny modelu M1
dostaneme statistiku konzistence C1p = 0,92. Pokud je práh konzistence stanovenna Ct = 0,9, pak je tento model považován za konzistentní. Pokud bude ve stej-ném místě se stejnou orientací a se stejnou velikostí dvou hlavních poloos modelM2 s trojnásobným objemem (tudíž vyšší mírou nejistoty), dostaneme při projekciz hlavní roviny stejnou hodnotu kvantilu konzistence C2p = 0,92, a tudíž stejný výsle-dek verifikace. Pokud však budeme promítat z objemu, dostaneme pro M1 hodnotukvantilu C1o = 0,91 a pro M
2 C2o = 0,89. Prvním způsobem projekce je model stálekonzistentní, protože C1o > Ct, ale ve druhém je C2o < Ct považován za nekonzis-tentní a verifikační algoritmu jej zamítne. V závislosti na volbě projekční metodytak dostaneme pro jeden model dvě různá rozhodnutí.
62
Chování statistik konzistence 6.3
a) SSD
−90−30
03090
−90
−30
0
30
90
−4000
−3000
−2000
−1000
0
X axis (deg)Y axis (deg)
cons
iste
ncy
− a
bsol
ute
valu
es
−150
15
−15
0
15
−600
−400
−200
0
Y axis (deg)
cons
iste
ncy
− a
bsol
ute
valu
es
b) SCC
−90−30
03090
−90
−30
0
30
90
0.2
0.4
0.6
0.8
1
X axis (deg)Y axis (deg)
cons
iste
ncy
− a
bsol
ute
valu
es
−150
15
−15
0
15
0.85
0.9
0.95
1
Y axis (deg)
cons
iste
ncy
− a
bsol
ute
valu
es
c) SpC
−90−30
03090
−90
−30
0
30
90
0.2
0.4
0.6
0.8
1
X axis (deg)Y axis (deg)
cons
iste
ncy
− a
bsol
ute
valu
es
−150
15
−15
0
15
0.85
0.9
0.95
1
Y axis (deg)
cons
iste
ncy
− a
bsol
ute
valu
es
d) MIF
−90−30
03090
−90
−30
0
30
90
0
0.2
0.4
0.6
0.8
X axis (deg)Y axis (deg)
cons
iste
ncy
− a
bsol
ute
valu
es
−150
15
−15
0
15
0.3
0.4
0.5
0.6
0.7
Y axis (deg)
cons
iste
ncy
− a
bsol
ute
valu
es
Obrázek 6.7 Průběhy PLIC při natáčení lokálním modelem. Jedním lokálním mode-lem bylo natáčeno o elevační úhel ψ = ±90 (levý sloupec obrázků) nebo v detailnímpohledu okolo maxima konzistence o ψ = ±15 (pravý sloupec s krokem okolo 0,74)z jeho původní polohy (ϕ = 0, ψ = 0). Azimut byl volen rovnoměrně v celém inter-valu 〈0, 180〉. Vzhledem k minimální odchylce počátečního normálového vektoru n odosy z (n = [0,011, 0,002, 0,999], což činí 0,64), jsem bez postřehnutelné chyby tyto dvě osyv obrázcích ztotožnil.
63
6 Experimenty ověřující teorii
−5 −4 −3 −2 −1 0 1 2 3 4 5−60
−50
−40
−30
−20
−10
0
cons
iste
ncy
mea
sure
− a
bsol
ute
valu
es
SSDSCCSpCMIF
−5 −4 −3 −2 −1 0 1 2 3 4 50
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1
move [mm]
a) Hlavní rovina verzus objem.
−5 −4 −3 −2 −1 0 1 2 3 4 5−60
−50
−40
−30
−20
−10
0
cons
iste
ncy
mea
sure
− a
bsol
ute
valu
es
SSDSCCSpCMIF
−5 −4 −3 −2 −1 0 1 2 3 4 50
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1
move [mm]
b) Umělé nafukování objemu.
Obrázek 6.8 Promítání bodů z hlavní roviny modelu oproti promítání z jeho objemu. Plnou čarou jsou na a)zobrazeny průběhy posunu při promítání bodů pouze z hlavní roviny a čárkovaně z celého objemu lokálního modelu.Lokální model o přirozených délkách poloos 4,99×5,01×0,53mm byl dále uměle zvětšován ve směru normály do kula-tějšího tvaru b). Plná čára odpovídá poloose délky 1mm, čárkovaná délky 3mm a čerchovaná délky 5mm. Čerchovanéprůběhy tak odpovídají plně kulovému modelu. Měřítko na levé ose patří SSD, na pravé ostatním konzistencím.
Změny průběhů konzistence pro posouvání modelem při projekci z objemu vůčiprojekci z hlavní roviny ilustruje obrázek 6.8. Vyvodíme z něj následující pozorování:1. Relativní průběhy obou způsobů promítání se vzájemně příliš neliší.Komentář 6.8.
2. Při promítání z objemu přirozeného modelu dosahuje v maximu nižší konzistence,než při promítání z hlavní roviny. Pokles činí u SCC a SpC 2%, u SSD 5% au MIF dokonce 20%.
Ukazuje se, že má smysl rozlišovat způsoby promítání tehdy, pokud jsou v souboruobsaženy jak výrazně ploché, tak kulaté modely. Pak lze využít projekce z objektuk tomu, abychom diskriminovali modely s nižší mírou věrohodnosti. Pokud je mírau všech modelů zhruba stejně veliká (nebo není k dispozici vůbec), použije se pro-jekce bodů z hlavní roviny modelu. Dopustíme se tak nejmenší chyby, protože hlavnírovina je nejlepším odhadem povrchu v daném místě.
Délka korelačního řetězce.
Dalším parametrem výpočtu korelačních statistik je délka korelačního řetězce n ne-boli počet 3D bodů, které promítáme z každé šupiny do každého obrazu, abychomzískali jasy pro korelaci. Kdybychom měli spojité obrazy, museli bychom generovatnekonečně bodů, abychom pokryli celou plochu modelu. Protože jsou obrazy dis-krétní s konečnou velikostí, bude postačující promítat optimální počet bodů. Odjistého počtu již využijeme každý pixel, který by patřil do průmětu modelu. Protoževšak body generujeme podle Gaussova rozdělení, bude stále platit, že čím více budebodů, tím přesnější, ale pomalejší bude výpočet. V tomto experimentu jsme třicet-krát opakovali výpočet maxima korespondence, pokaždé s jinou náhodnou množinoubodů, ale o stejném počtu prvků (stejné délce korelačního řetězce). Výsledek vidímena grafu 6.9. Jde z něj vyčíst, jak dlouhý bychom potřebovali korelační řetězec, abyopakovací chyba maxim konzistence klesla pod zvolenou úroveň.1. Největší odchylku vykazuje MIF, pak SpC. Méně než poloviční je u SCC a SSD.Komentář 6.9.
Je to tím, že se projeví ztráta informace u více invariantních konzistentníchstatistik a zvýší se tak závislost na výběru vzorků z obrazů.
64
Chování statistik konzistence 6.3
2. Průběh MIF pro 10 bodů je téměř nepoužitelný – maximum konzistence je do-konce zcela vychýleno do -3mm. Je to způsobeno výpočtem sdružené entropiepomocí dvoudimenzionálního histogramu. Deset prvků v něm dává příliš málokombinací. Teprve promítnutím 100 bodů se objeví jednoznačné globální maxi-mum a pro 1000 bodů zmizí výrazné fluktuace.
3. Odchylka maxima konzistence činí 50% u SSD při délce řetězce 10. Pod 20%klesne odchylka u SSD a SCC při délce 100 bodů, u SpC při délce 200 a u MIFaž při délce 1000 promítaných bodů.
Pokud nám záleží na přesnosti, je třeba promítat minimálně 1000 bodů. V takovémpřípadě činí na rovině nejistota polohy vlivem generování bodů 0,02 mm pro SSDa SCC, u SpC 0,03 mm a u MIF 0,05 mm. Spokojíme-li se se směrodatnou odchylkou0,05mm, pak pro SSD a SCC stačí promítnout 100 bodů.
Práh konzistence.
Volba prahu konzistence Ct je stěžejní pro výsledek verifikačního rozhodnutí. Jehohodnota závisí na odrazivostních vlastnostech povrchu, jeho osvětlení a zvolené kon-zistenční míře, takže nelze určit jeho obecnou hodnotu. Určitou představu však dáváobrázek 6.10. Ukazuje šířku tolerančních pásem, uvnitř kterých je model konzistentnípro různé prahy konzistence.
1. Ačkoliv je rozsah hodnot statistik konzistence podobný (〈0, 1〉 u MIF, resp. Komentář 6.10.
〈−1, 1〉 u SCC i SpC, u nich se však záporné hodnoty odpovídající antikorelaciprakticky nevyskytují), je nutné pro MIF zvolit jinou hodnotu prahu konzistence.Je to tím, že rozdělení hodnot má MIF značně odlišné.
Obrázek 6.9 Rozptyl maxim PLIC při změně délky korelačního řetězce. Graf a) vyjadřuje hodnotu posunutílokálního modelu z původní hodnoty do maxima PLIC v závislosti na délce korelačního řetězce n. Vidíme průběhstřední hodnoty a směrodatnou odchylku maxim ze 30 měření. Body modelu byly v každém měření vygeneroványnáhodně. Pravý graf b) ukazuje průběhy MIF při posunu lokálním modelem pro n = 10, 100 a 1000 promítaných bodů.
Obrázek 6.10 Verifikační pásma modelu části roviny. Vidíme průběhy PLIC (zvlášť pro SCC, SpC i MIF) při posunulokálním modelem o ±5mm. Barevně jsou odlišeny toleranční pásma, uvnitř kterých verifikační algoritmus považujelokální model za konzistentní s obrazy 1 a 2. Odstíny diagramu odpovídají jedné hodnotě prahu konzistence Ct, jehožhodnota je po řadě uvedena v legendě. Například: Zkoumaný lokální model je konzistentní dle SCC statistiku a prahukonzistence Ct = 0,6 v pásmu posunu od −2,9 do 2,4mm z původní hodnoty, protože uvnitř tohoto intervalu jehodnota vyšší než zvolený práh Ct.
2. Toleranční pásmo ±0,5mm odpovídá prahu konzistence Ct = 0,96 pro SCCa SpC a Ct = 0,5 pro MIF.
3. Ačkoliv jsme prahy konzistencí Ct nastavili blízko maximálních hodnot, zůstávajítoleranční pásma relativně široká. Platí to zvláště pro SCC a SpC, u kterých jemaximum velmi ploché.
Jak jsme již uvedli, práh konzistence je aplikačně závislý, takže hodnoty naměřenév ideálních podmínkách mohou pouze posloužit k získání citu pro nastavení prahuv reálné situaci.
Shrňme výsledky dosavadních experimentů. Vyplynulo z nich, že pro praktickou re-Shrnutí průběhů PLIC
alizaci mají význam statistik SCC a SpC. Jejich minimálně lineární invariantnostvůči jasovým deformacím umožní použít obrazy z kamer o nestejném zesílení a po-sunu hodnot, aniž bychom tyto rozdíly museli měřit a kompenzovat. Statistika SpCumožní přesnější výpočet konzistence i v místech, kde je mírná odchylka od lam-bertovského povrchu. Statistika SCC je sice méně citlivá na deformace v obrazech,ale její průběh je hladší než u SpC. Díky tomu se SCC lépe hodí pro optimalizaciparametrů. Pro verifikaci, kde nám menší hladkost nevadí, doporučuji použít statis-tiku SpC. Statistika MIF má sice ostřejší maximum, ale pro své fluktuace a vysokénároky na délku korelačního řetězce její užití pro naše účely nedoporučuji.
6.4 Vliv textury
Textura, ať již je dána odrazivostí povrchu (albedem) nebo projekcí (anizotropnímosvětlením), má rozhodující vliv na kontrast v intenzitních obrazech. Vliv je mnohemvětší než fotometrické vlastnosti dané geometrií povrchu. Jak velkou roli texturahraje při porovnávání obrazových intenzit, ukáže následující experiment.Naši rovinnou duralovou desku jsme nasnímali pětkrát, pokaždé s jinou inten-
zitou promítané náhodné textury, viz obrázek 6.11. U nejslabší textury se projekcev podstatě neuplatnila, sejmuta byla pouze přirozená textura duralu. U dalšíchsnímků bylo přidáváno na intenzitě projekce a zároveň zeslabováno osvětlení tak,aby průměrná hodnota jasu ve sledované oblasti byla konstantní. Průběhy kon-zistenčních statistik při pohybu jednoho desetimilimetrového lokálního modelu ve
66
Vliv textury 6.4
100 200 300 400 500 600 700
100
200
300
400
1
100 200 300 400 500 600 700
100
200
300
400
2
100 200 300 400 500 600 700
100
200
300
400
3
100 200 300 400 500 600 700
100
200
300
400
4
100 200 300 400 500 600 700
100
200
300
400
5
1 2 3 4 510
15
20
25
30
35
40
45
50
55
Image number
Stan
dard
dev
iatio
n
Obrázek 6.11 Obrazy rovinné scény s promítnutou texturou různé intenzity. Obrazy jsou seřazeny od prvníhos nejslabší texturou až k pátému s texturou nejsilnější. Scéna byla dosvětlována tak, aby průměrný jas ve vyznačenéobdélníkové oblasti zůstával konstantní. Všechny zobrazené snímky pocházejí z kamery 1 (viz konfigurace na obr. 6.1).Graf znázorňuje směrodatnou odchylku jasů v obdélníkové oblasti.
−20 −15 −10 −5 0 5 10 15 20−100
−90
−80
−70
−60
−50
−40
−30
−20
move [mm]
SSD
−20 −15 −10 −5 0 5 10 15 20−0.4
−0.2
0
0.2
0.4
0.6
0.8
1
move [mm]
SCC
−20 −15 −10 −5 0 5 10 15 20−0.4
−0.2
0
0.2
0.4
0.6
0.8
1
move [mm]
SpC
−20 −15 −10 −5 0 5 10 15 200
0.1
0.2
0.3
0.4
0.5
0.6
0.7
move [mm]
MIF
54321
Obrázek 6.12 Konzistence lokálního modelu při různých intenzitách textury. Vybraným10mm lokálním modelem bylo pohybováno ve směru jeho normálového vektoru. Každý grafse týká jedné konzistence (SSD, SCC, SpC a MIF). Jednotlivé průběhy v každém grafu seliší intenzitou promítané textury. Indexování v legendě odpovídá číslování v obrázku 6.11.
67
6 Experimenty ověřující teorii
směru normály vypočtených z takových obrazů ukazuje obrázek 6.12. Ze zobraze-ných hodnot můžeme vyčíst:1. Pro všechny čtyři statistiky konzistence platí, že intenzivnější textura vede k vět-Komentář 6.12.
ším diferenciacím jejich hodnot. Tím je citlivěji vymezena konzistentní polohamodelu.
2. Relativně dobré průběhy dostáváme již od třetí sady snímků, kde osvětlení mápřibližně stejnou intenzitu jako promítaná textura.
6.5 Zpřesnění parametrů lokálních modelů
Zpřesněním parametrů lokálních modelů ve smyslu maximalizace statistik konzis-tence můžeme porovnat přesnost rekonstrukce. Postupovali jsme následujícím způ-sobem. Rovinu nasnímanou pro měření vlivu textury v předešlé kapitole 6.4 jsmezrekonstruovali pomocí korespondenčního algoritmu stabilního párování [62], pakvzniklými body proložili lokální modely (šupiny) a vyřízli vnitřní oblast o velikosti80×95mm. Tato oblast odpovídala ve scéně zhruba 180×245 pixelům (výškaךířka).Generované lokální modely měly v průměru 3mm, v obraze pokrývají eliptickouoblast asi 6,8×7,7 pixelů. Tato plocha přibližně odpovídá použitému korelačnímuokénku stereokorespondenčního algoritmu 7×7 pixelů. Volba takto odpovídajícíchsi velikostí korelačních okének pro stereo i pro verifikaci umožňuje objevit případnéprincipiální odlišnosti obou metod. Jinak předpokládáme, že u rovinné scény je většílokální model a tím rozlehlejší projekce do obrazů výhodou, protože obraz poskytnevíce informace, aniž by byla geometricky zkreslena aproximací. U nerovinného po-vrchu je volba velikosti modelu závislá na jeho křivosti.Abychom zjistili přesnost sterea, proložili jsme středy lokálních modelů rovinou
a spočítali směrodatnou odchylku vzdáleností každého středu od této roviny. Přitomjsme použili metodu jeden ven (leave one out) [7], tj. vzdálenost daného středu seměří od roviny získané proložením všech středů vyjma právě měřeného. Protožemetody hledání stereokorespondencí mohou být závislé na vzájemném uspořádáníobrazů (horizontální, vertikální, diagonální), provedli jsme tento experiment prokaždý obrazový pár zvlášť, a také pro společnou rekonstrukci ze šesti a ze čtyř párů(horizontálních+vertikálních a horizontálních+diagonálních), viz obr. 6.13.1. Sdružením rekonstruovaných bodů z více párů obrazů dosáhneme výrazně vyššíKomentář 6.13.
přesnosti než z jednoho libovolného páru. Je to tím, že měření v místech reálnéhopovrchu roste s každým párem, kdežto vychýlené body jsou z každého párurozmístěny náhodně. Zvyšuje se tak poměr signál/šum.
2. Nejméně přesná je rekonstrukce vertikálních párů a to o 80%. Vysvětlujeme sito poměrem šířky a výšky pixelů (ten byl 6:5; přesnost ve vertikálním směru jetak o 17% nižší než v horizontálním), různou vzdáleností vertikálních a hori-zontálních párů kamer a jejich odlišnými úhly, které svíraly jejich optické osy.Tyto faktory se umocňují, protože jednou se projeví při kalibraci a podruhé přirekonstrukci. Z tohoto důvodu se vyplatí sdružovat body pouze z horizontálnícha diagonálních párů.
3. Promítnutím textury jsme zvýšili přesnost asi dvakrát, z 0,1mm na 0,05mm.U takto vygenerovaných lokálních modelů jsme optimalizovali jejich parametryZpůsob optimalizace
tak, aby se maximalizovala jejich konzistence s obrazy. Postupovali jsme ve třechiteracích: (i) první optimalizovala polohu ve směru normálového vektoru, (ii) druháorientaci normálového vektoru a (iii) třetí opět polohu. Ze středů takto optimálněposunutých a natočených lokálních modelů jsme stejným způsobem jako v předešlémpřípadě spočítali směrodatnou odchylku od proložené roviny. Tyto odchylky jsme
68
Zpřesnění parametrů lokálních modelů 6.5
1 2 3 4 5
0.05
0.1
0.15
0.2
0.25
Texture
Plan
e St
d [m
m]
1234132414238n
a) Chování různých párů obrazů.
1 2 3 4 5
0.05
0.1
0.15
0.2
0.25
Texture
Plan
e St
d [m
m]
h v d 8n h+d
b) Průměry přes vertikální, horizontální a diagonální páry.
Obrázek 6.13 Odchylky rekonstruovaných lokálních modelů od roviny při různé intenzitě textury. Pro pět různýchintenzit promítané textury z obr. 6.11 (horizontální osa) byla z různých obrazových párů provedena rekonstrukcelokálních modelů. Za apriorního předpokladu rovinnosti objektu byly spočítány směrodatné odchylky vzdálenostistředů modelů od jimi proložené roviny. Jednotlivé křivky odpovídají obrazovým párům, např. 12 značí použití obrazuz první a druhé kamery, 8n z šesti sousedních párů, h z horizontálních párů 12 a 34.
1 2 3 4 5
0.05
0.1
0.15
0.2
0.25
Texture
Plan
e St
d [m
m]
1234132414238n
a) Chování různých párů při SCC míře.
1 2 3 4 5
0.05
0.1
0.15
0.2
0.25
0.3
0.35
Texture
Plan
e St
d [m
m]
StereoSSD SCC SpC MIF
b) Jednotlivé statistiky konzistence.
Obrázek 6.14 Odchylky optimalizovaných modelů od roviny. Sledujeme stejný druh měření jako na obrázku 6.13a,ale po optimalizaci každého lokálního modelu v poloze, orientaci a znovu v poloze pomocí maximalizace statistikkonzistence. Vpravo jsou porovnány odchylky pro jednotlivé statistiky konzistence při použití všech párů obrazů(žluté puntíky odpovídají červenému průběhu na levém obrázku).
porovnali s odchylkami měření ze sterea. Pokud by se odchylky zmenšily, znamenaloby to, že verifikace obsahuje principiální odlišnosti od stereorekonstrukce. Výsledekoptimalizace ukazuje obr. 6.14. Z tohoto grafu můžeme vyčíst:
1. Průběhy optimalizovaných odchylek se až překvapivě podobají odchylkám mo- Komentář 6.14.
delů ze sterea. Potvrzuje se tak domněnka velmi blízké příbuznosti obou metod.2. U použitých modelů velikosti 3mm je rovinnost optimalizovaných modelů vždyhorší než původní poloha ze sterea. Nejlepších výsledků optimalizace dosahujeSCC, pak SpC, MIF a s odstupem SSD. SCC má odchylku o 17% vyšší nežstereo.
3. Přesnost MIF roste s intenzivnější texturou výrazněji než ostatní statistiky.
69
6 Experimenty ověřující teorii
Jak jsme se již zmínili, maximalizace statistiky konzistence počítáme ve třechGlobální trendy
optimalizace iteracích. Mezi dvojím posunem do optimální pozice podél normálového vektoru semodel naklání do optimální polohy. Při posunu se mění poloha středu modelu, alezůstává konstantní jeho strukturní matice; při naklánění naopak střed zůstává pevněna místě, ale mění se strukturní matice. Histogramy na obr. 6.15 nám ukazují, jakvelké jsou posuny a natočení z původní pozice modelu do optimální.1. Posun modelů konverguje k nějaké optimální hodnotě konzistence, protože druhýKomentář 6.15.
posun má již mnohem menší rozptyl a střední hodnotu blízkou nule, jak ukazujez porovnání tmavého a světlého histogramu obr. 6.15a.
2. Při orientaci lokálních modelů by měly hodnoty azimutů být rovnoměrně dis-tribuovány v intervalu 〈−90, 90〉. Až na okolí 0 to platí. Důvodem třikrátčetnější hodnoty azimutu 0 je singularita v tomto bodě. Použitá dvourozměrnáoptimalizace přes oba úhly pak preferuje nevychýlený azimut.
3. Úhel elevace je velmi malý (průměrně 1,9). To odpovídá předpokladu, protožesměr normálových vektorů byl téměř kolmý k rekonstruované rovině.
Histogramy nám ukázaly rozdělení změn parametrů optimalizovaných lokálních mo-delů pro jednu PLIC statistiku, jednu intenzitu textury a jeden pár obrazů. Abychommohli porovnat rozdělení pro všechny kombinace těchto veličin, zobrazíme si jen smě-rodatné odchylky a rozptyly posunu a orientace přes všechny modely. Z výsledkůzobrazených na obr. 6.16 vyplývá:1. U všech párů obrazů, s výjimkou horizontálního páru 34, převažuje posun lokál-Komentář 6.16.
ními modely do kladných hodnot, tj. směrem ke kamerám. Tento systematickýjev nás znovu upozornil na nezávislost kalibrace každé kamery, jak jsme rozebíraliu obrázku 6.6. Také rozdíly v chování páru 12 a 34 lze vysvětlit tímto způsobem.Pomocí metody vyrovnání svazku paprsků lze optimalizovat projekční maticevšech čtyř kalibrací. Dalším zdrojem chyb může být posun v počátku souřadnico-vého systému kalibrační procedury. Tímto problémem se zde nebudeme zabývat,ale verifikační procedura nám dává nástroj, jak tuto hypotézu ověřit.
Obrázek 6.15 Histogramy posunů a změny orientace lokálních modelů při optimalizaci. Zobrazeny jsou pouzehodnoty počítané ze všech obrazových párů, nejsilnější textury a SCC. Tmavý histogram relativních posunů z aktuálnípolohy představuje první iteraci optimalizace, světlý třetí. Červená čára ukazuje střední hodnotu. U orientace se tmavýhistogram týká azimutu a světlý elevace (odklonu od původní normály).
−0.05 0 0.05 0.1 0.15 0.20
5
10
15
20
% o
f m
odel
s
Model movement [mm]
1. posun2. posun
a) Posuny.
−100 −50 0 50 1000
2
4
6
8
10
% o
f m
odel
s
Model orientation [deg]
Azimut Elevace
b) Orientace.
70
Zpřesnění parametrů lokálních modelů 6.5
2. Lokálními modely s přispěním všech párů je posouváno o 0,04mm v případěsilné textury (a o 0,1mm u slabé). Rozptyl prvního posunu ze všech párů činí0,04mm (0,1mm), u druhého posunu 0,008 (0,03mm).
3. Rozptyl úhlu elevace je opět pro všechny páry 6 (2).Porovnejme nyní přesnost modelů po naší optimalizaci a před ní (tak, jak je Porovnání se stereem
získáme stereem). Pro vyhodnocení si zobrazíme rozdíl diferencí směrodatných od-chylek rovinného modelu. Výsledek je zobrazen na obrázku 6.17.1. Optimalizace dává lepší výsledky u vertikálních párů, jejichž stereorekonstrukce Komentář 6.17.
dopadla nejhůře. Znamená to, že příčina většího rozptylu sterea z vertikálníchpárů je způsobena těmi kroky, kterými se obě metody liší. Tento poznatek ne-koresponduje s naší domněnkou, že příčina je v nečtvercovosti pixelů.
2. U rekonstrukce ze všech párů vede optimalizace ke zhoršení směrodatné odchylky,byť je maximálně o 0,02mm. Rozdíl je minimální a svědčí o blízké příbuznostiobou postupů.
3. Při zintenzivnění textury můžeme zaznamenat přibližování přesnosti optimali-zace k přesnosti sterea.V posledním experimentu zjistíme závislost přesnosti výpočtu na velikosti lo- Velikost modelu
kálního modelu. Můžeme si představit, že model zvětšujeme nkrát v každém směrua promítnuté body nám v obrazech zaujímají různě velkou korelační oblast. Čím je
1 2 3 4 5−0.04
−0.02
0
0.02
0.04
0.06
0.08
0.1
0.12
0.14
Texture
Mea
n of
mov
emen
t [m
m]
1234132414238n
a) Střední hodnota posunu.
1 2 3 4 50
0.05
0.1
0.15
0.2
0.25
Texture
Dev
iatio
n of
mov
emen
t [m
m]
1234132414238n
b) Rozptyl posunu.
1 2 3 4 50
5
10
15
Texture
Dev
iatio
n of
ele
vatio
n [d
eg]
1234132414238n
c) Rozptyl elevace.
Obrázek 6.16 Střední hodnota a rozptyl posunů aorientace lokálními modely. Jde o posun při prvníiteraci optimalizace a statistické veličiny se počítalyze všech lokálních modelů rekonstruované roviny. Přioptimalizaci orientace je zobrazena směrodatná od-chylka úhlů elevace. Opět jsou vyneseny výsledky po-čítané z různých obrazových párů a pro jednotlivé in-tenzity texturu.
71
6 Experimenty ověřující teorii
1 2 3 4 5−0.04
−0.03
−0.02
−0.01
0
0.01
0.02
0.03
0.04
0.05
Texture
Ster
eo a
nd o
ptim
izat
ion
std
diff
eren
cies
[m
m]
1234132414238n
Obrázek 6.17 Rozdíl odchylek od roviny modelů re-konstruovaných stereem a optimalizovaných konzistencís obrazy. Vidíme rozdíl obrazů 6.13a a 6.14a. Kladné hod-noty znamenají zlepšení pomocí optimalizace.
1.5 3 6 9 18 270
0.05
0.1
0.15
0.2
0.25
0.3
Model size [mm]
Plan
e St
d [m
m]
12345
Obrázek 6.18 Závislost na velikosti promítané oblasti.Vyneseny jsou hodnoty optimalizace statistikou SCC zapomoci všech čtyř obrazů (všechny páry 8n) pro různěvelké lokální modely.
oblast větší, tím více informací (pixelů) použijeme pro korelaci, a tím bychom mělidosáhnout vyšší přesnosti. To ovšem platí jen pro rovinný objekt. Pro nerovinnéobjekty narůstá se zvětšující se oblastí chyba jeho rovinné lokální aproximace odzakřiveného povrchu, viz obr. 6.18.
1. Nejnižší hodnoty deviace od roviny vznikají, aproximujeme-li lokální model většíKomentář 6.18.
oblastí, než stanovují jeho počáteční parametry. Platí to pro všechny intenzitytextury. Srovnej s přesností sterea na obr. 6.14b.
2. Čím intenzivnější je textura, tím dostáváme menší odchylku od roviny pro vícezvětšený model. Nejslabší textura dává nejpřesnější optimalizaci s 6mm lokál-ním modelem (odchylka 0,072mm), zatímco u nejsilnější textury je optimální až18mm model (0,016mm).
3. U velkých modelů hrozí, že mnoho bodů padne mimo obraz.4. Konzistence velmi velkých modelů s obrazy se slabými texturami klesají zřejměproto, že povrch není lambertovský (viz odlesky na obr. 6.11 vlevo uprostřed).Silnější textura fotometrickou složku přebije, takže se nelambertovskost povrchutak neprojeví.
V následujících bodech shrnuji pozorování z experimentů popsaných v této kapitole:Shrnutí
• Ověřil jsem, že všechny čtyři statistiky konzistence kvantifikují geometrickoupřesnost lokálního modelu povrchu (pokud jsou splněny podmínky, které jsemuvedené v kapitole 5.1.2 a vybraná statistika je invariantní vůči jasovým de-formacím popsaných v kapitole 5.1.3). Pro verifikaci považuji za nejvýhodnějšístatistiku SpC, pro optimalizaci SCC.
• Aproximace modelu body z jeho hlavní roviny považuji za obecně výhodnějšínež aproximace body z celého objemu modelu, protože maxima konzistencí jsouv prvním případě výraznější.
• Délka korelačního řetězce by měla přesahovat 100 bodů.• Potvrdilo se, že korelační práh je aplikačně závislý. Předpokládám, že volba prahupro statistiky SCC a SpC budou voleny v rozmezí 0,6 až 0,95, pro statistiku MIFod 0,3 do 0,6.
72
Zpřesnění parametrů lokálních modelů 6.5
• Ověřil jsem, že kontrast obrazu, který určuje hlavně textura, je pro přesnostvelmi významný.
• Objevilo se, že existuje optimální velikost modelu, která dává nejpřesnější vý-sledky. Taková velikost bývá několikrát větší, než původní velikost modelu.
• Přesnost optimalizace modelu je srovnatelná s přesností našeho geometrickéhosterea, tedy až 0,05mm. Lepších výsledků dostaneme jen pro velké modely (až0,02mm).
73
7 Experimenty s reálnými objekty
V této kapitole ukážeme výsledky verifikace a zpřesnění lokálních modelů při rekon-strukci reálných objektů – čajové konvice a lidských obličejů. Jde o zástupce dvou ty-pických druhů objektů, které bychom chtěli v praktických úlohách rekonstruovat. Po-vrch čajové konvice nemá žádnou vlastní texturu a má homogenní funkci odrazivosti.Lidské obličeje se oproti tomu vyznačují povrchem značně variabilním, mají různěintenzivní texturu, s různou odrazivostní funkcí a velmi různorodou křivostí povrchu.Dále nastíníme možnosti využití verifikace a zpřesnění pro řešení jiných úloh
rekonstrukce povrchů 3D objektů. Jde o rekonstrukci lokálních modelů různých veli-kostí a přímou rekonstrukci lokálních modelů bez předchozí 1. fáze zahrnující výpočetbodových množin (tedy např. bez geometrického sterea).
7.1 Čajová konvice
Prvním testovaných objektem je bílá keramická čajová konvice, kterou vidíme naobr. 7.1a. Zdrojové intenzitní obrazy pro stereorekonstrukci jsou na obr. 7.1b. Stejnéobrazy byly použity i pro verifikaci a optimalizaci. Na konvici byla diaprojektorempromítnuta náhodná textura stejně jako u obr. 6.2 a obrazy byly snímány stejnýmzařízením s podobnou konfigurací jako na obr. 6.1. Obr. 7.2 ukazuje správně zrekon-struované lokální modely velikosti 5.5mm. Jejich barva je úměrná statistice konzis-tence SCC. Tato statistika byla použita i pro další výpočty v této kapitole. Vidíme,že většina modelů má velmi vysokou hodnotu konzistence (korelace nad 0,9). Kon-zistence je nižší v místech, kde velikost modelu je neúměrná křivosti povrchu (ucho ašpička hubičky). Toto je žádoucí chování, protože takový model přestává vlivem ro-
Obrázek 7.1 Fotografie konvice,která byla rekonstruována a jejízdrojové intenzitní obrazy. Načtyřech černobílých intenzitníchobrazech je vidět promítnutá ná-hodná textura.
a) b)
74
Čajová konvice 7.1
0.45 0.5 0.55 0.6 0.65 0.7 0.75 0.8 0.85 0.9 0.95
0.4 0.5 0.6 0.7 0.8 0.9 10
1
2
3
4
5
6
% o
f da
ta p
oint
s
value
Obrázek 7.2 Vizualizace hodnot SCC na šupinách rekonstruované konvice. Každá šupina získaná stereorekonstrukcíje obarvený statistikou konzistence SCC. Vpravo vidíme histogram konzistencí všech modelů.
vinné aproximace věrně popisovat realitu. Velmi nízká konzistence je ve spodní částikonvice, protože je velmi blízko okraje obrazu a některé projekce padnou mimo ob-raz. Dále dochází k poklesu konzistence v místech, kde je povrch nelambertovský(tam, kde jsou odlesky). Takový povrch však nesplňuje požadavky na přípustnoulineární funkci Tv pro statistiku SCC.Protože nemáme k dispozici model konvice vytvořený jinou přesnější metodou,
budeme považovat za referenční model ten, který je získaný stereorekonstrukcí s ma-nuálně vyladěnými parametry, viz obr. 7.3a. Modely pak uměle posuneme a otočímenáhodným, ale známým způsobem. Takto deformovaný povrch vidíme na obr. 7.3b.Optimalizace by měla vrátit parametry modelů tak, aby byly v souladu s prvotnímpovrchem. Výsledek je zobrazen na obr. 7.3c.Úspěšnost zpřesnění lze měřit vzdáleností parametrů optimalizovaného modelu
k interpolovaným hodnotám referenčního povrchu. Prakticky jsem však tento postupzjednodušil. Počítal jsem vzdálenost parametrů k hlavní rovině referenčního modelu,
75
7 Experimenty s reálnými objekty
a) Originál (260 lokálních modelů) b) Uměle zašumělý povrch
c) Po optimalizaci . . . d) . . . a dále po verifikaci (přežilo 222)
Obrázek 7.3 Zpřesnění a verifikace při rekonstrukci konvice. Lokální modely zrekonstruo-vané stereem a), byly posunuty ve směru normálového vektoru o náhodnou hodnotu z inter-valu ±10mm b). Na modely s takto deformovanými parametry byl aplikován optimalizačníalgoritmus c). Protože některé modely (asi 6 z 260) uvízly v minimu mimo povrch, pou-žili jsme verifikaci, která je ze souboru vyřadila d). O konzistentní modely ze spodní částikonvice jsme přišli, protože jsou blízko okraje obrazu a projekce tak zasahují mimo obraz.U každé fáze zpracování povrchu je pohled shora a zepředu.
76
Čajová konvice 7.1
aniž bych interpoloval tvar povrchu s jeho sousedy. Dopouštím se tak chyby, pro-tože středy šupin mohou při optimalizaci putovat po povrchu a ustálit se dalekood středu referenčního modelu. Toto zjednodušení jsem přijal proto, protože zatímnemáme vybudovaný globální referenční model (se znalostí sousedností), který jenezbytný pro interpolaci tvaru povrchu. Čím menší bude chyba počáteční orientacereferenčního modelu, tím menší bude tato systematická chyba.
Chyby zpřesnění, počítané právě popsaným způsobem, jsou zaneseny do tabu-lek. Z první hodnoty tab. 7.1 usuzuji, že přesnost optimalizace polohy v hloubce je0,3mm (za předpokladu, že přesnost stereorekonstrukce referenčního modelu bylaalespoň o polovinu lepší). Při vychýlení každého modelu o náhodnou rovnoměrnouhodnotu z intervalu ±1mm z referenční pozice se přesnost nemění a zůstává 0,3mm.Teprve od maximální absolutní výchylky nad 5mm chyba optimalizovaných šupinroste, je ale vždy menší než ta před optimalizací. Znamená to, že většina modelůse přiblíží povrchu, ale uvíznou v lokálním minimu ještě před tím, než dosáhnoupovrchu. Výchylka normály do 30 nemá na přesnost výrazný vliv. Teprve s většímúhlem chyba velmi vzrůstá. Je to tím, že se model na počátku optimalizace vydá smě-rem zcela vychýlené normály, čímž se daleko vzdálí od středu referenčního modelu.
Sledování přesnosti odchylek orientace v tab. 7.2 vykazuje podobné výsledky jakoodchylky polohy. Při výchylkách středů do 1mm a normály do 10 dostáváme mediánsměrodatné odchylky normál do dvou stupňů. Přijatelné výsledky pozorujeme ještěpři výchylkách do 5mm a do 30.
Tabulka 7.1 Směrodatná odchylka středu od hlavní roviny po optimalizaci. Šupiny bylyposunuty ve směru normály, každá o náhodnou hodnotu z rovnoměrného rozdělení. Jeho ma-ximální absolutní hodnota je pro každý řádek tabulky stejná a je uvedena v prvním sloupciPak byly natočeny o náhodný úhel rovněž z rovnoměrného rozdělení z intervalu po sloup-cích ±0, ±10, ±30 a ±60. Takto vychýlené šupiny byly optimalizovány. Tabulka uvádísměrodatné odchylky středů optimalizovaných šupin od hlavních rovin referenčních šupin.
[mm] Vychýlení normály [deg]Vychýlení středu 0,00 10,00 30,00 60,00
Tabulka 7.2 Úhel mezi optimalizovanou normálou a normálou původní šupiny. Po stejné optimalizaci vychýlenýchšupin jako v tab. 7.1 byly měřeny směrodatné odchylky a mediány úhlů normál. Robustní popis mediánem je vý-stižnější, protože několik šupin z oblasti hubičky a ucha konvice, bylo zcela vychýleno. Je to tím, že povrch je tamneúměrně křivý vzhledem k velikosti šupin.
77
7 Experimenty s reálnými objekty
[mm] Vychýlení normály [deg]Vychýlení středu 0,00 10,00 30,00 60,00
Tabulka 7.3 Počet modelů vyloučených verifikací. Počet šupin v procentech, jejichž optimalizovaná statistika kon-zistence nedosáhla danou mez konzistence. Celkový počet modelů byl 225.
Skutečný povrch může obsahovat oblasti, které nevyhovují podmínkám, kteréjsme odvodili v sekci 5.1.2. Model pak může uvíznout v lokálním maximu kon-zistence, který je mimo povrch. Je-li takové maximum nízké, dokážeme jej vyloučitopětovnou verifikací s přísnějším prahem, jak ukazuje obr. 7.3d. Počty modelů, kteréby neprošly ani po druhé verifikaci, jsou uvedeny v tab. 7.3.
7.2 Obličeje
Obličej patří z hlediska rekonstrukce mezi složité povrchy. Obsahuje části širokéhorozpětí křivostí, od téměř rovinných na čele, až po velmi křivé na špičce nosu. Kůžemůže být hladká, ale také pokryta vráskami. Barva pokožky je velmi proměnná atextura pleti se liší nejen jedinec od jedince (hladká pleť versus pihy), ale i po-lohou v obličeji (tvář, rty). Kromě kůže jsou zde i další typy povrchů jako zuby,oční rohovka i velmi komplikované povrchy jako vlasy, vousy a obočí. Různé částiobličeje mají různou odrazivostní funkci, některé výrazně nesplňují lambertovskoupodmínku – nejvýraznějším projevem jsou pak odlesky. Obličej může být doplněndalšími předměty velmi odlišných vlastností (sklo a kov na brýlích a náušnicích).Z tohoto důvodu byla rekonstrukce obličejů zatěžkávací zkouškou navrženého algo-ritmu verifikace. Na druhé straně nám chybí referenční model obličejů, takže hod-nocení úspěšnosti je pouze subjektivní.Pro ilustraci jsme položili práh hustoty pro generování lokálních modelů velmi
nízko, takže vzniklo mnoho šupin zcela nekonzistentních s reálným povrchem. Tytonekonzistentní šupiny byly ve verifikovaném modelu odstraněny. Obrázky 7.4, 7.5a 7.6 ukazují vstupní obrazy, histogramy rozložení konzistencí SpC, rekonstruovanýi verifikovaný povrch. Druhá tvář je s vousy a třetí s brýlemi.
7.3 Víceměřítková rekonstrukce lokálních modelů
Jeden z velkých nedostatků současné implementace rekonstrukce pomocí modelušupin je, že dokážeme generovat šupiny jen jedné velikosti pro celou rekonstruovanouscénu. Obrázek 7.7 ukazuje nevýhodnost takového přístupu, protože proti sobě jdepřesnost rekonstrukce a celkový počet rekonstruovaných dat.Abychom tento nedostatek překonali, musíme mít k dispozici mechanismus vý-
běru největšího ještě konzistentního lokálního modelu. Napadlo mě, že tuto vlastnostmůže splňovat verifikace lokálních modelů. Budu postupně vytvářet menší a menšímodel v daném místě a verifikace bude sloužit jako ukončovací podmínka.Generování víceměřítkových modelů pomocí konzistence je iterativním algorit-
mem. Nejprve proložím jeden model všemi body a verifikuji jeho konzistenci. Je-li
78
Víceměřítková rekonstrukce lokálních modelů 7.3
−0.4 −0.2 0 0.2 0.4 0.6 0.8 10
0.2
0.4
0.6
0.8
1
1.2
1.4
1.6
1.8
% o
f da
ta p
oint
s
value
Obrázek 7.4 Verifikace obličeje, příklad 1. Na obrázku vidíme dva ze čtyřech vstupních obrazů použitých pro stereorekonstrukci a verifikaci. Nastavením nízkého prahu potlačení vychýlených bodů bylo vygenerováno 16988 lokálníchmodelů s rozložením hodnot SpC dle zobrazeného histogramu. Verifikací s prahem konzistence 0,8 získáme 1519konzistentních modelů. Zobrazen je rekonstruovaný obličej před a po verifikaci ve dvou různých pohledech s barevněvyznačenými hodnotami konzistence každého modelu.
79
7 Experimenty s reálnými objekty
−0.4 −0.2 0 0.2 0.4 0.6 0.8 10
0.5
1
1.5
2
% o
f da
ta p
oint
s
value
Obrázek 7.5 Verifikace obličeje, příklad 2. Tvář s vousy. Z původních 16723 lokálníchmodelů zbylo po verifikaci 1244 konzistentních.
80
Víceměřítková rekonstrukce lokálních modelů 7.3
−0.4 −0.2 0 0.2 0.4 0.6 0.8 10
0.5
1
1.5
2
% o
f da
ta p
oint
s
value
Obrázek 7.6 Verifikace obličeje, příklad 3. Tvář s brýlemi. Z původních 16103 lokálníchmodelů zbylo po verifikaci 1970 konzistentních.
81
7 Experimenty s reálnými objekty
a) 16mm, šupin 143 b) 8mm, 576
c) 4mm, 2277 d) 2mm, 8672
0.8 0.82 0.84 0.86 0.88 0.9 0.92 0.94 0.96 0.98 1
Obrázek 7.7 Konzistence konvice pokaždé s jinou velikostí šupin. Nízká konzistence modelů (modrá barva) seobjevuje v místech, kde velikost lokálního modelu neodpovídá křivosti povrchu. U šestnáctimilimetrových modelůa) jsou takové všechny, u osmimilimetrových b) jen ty, které tvoří ucho a špičku hubičky konvice. Přesnost popisupovrchu se zmenšováním lokálních modelů roste, ovšem za cenu nárůstu jejich celkového počtu c), d). Velikost a početmodelů je uveden pod každým obrazem.
82
Víceměřítková rekonstrukce lokálních modelů 7.3
nekonzistentní, pak se podprostor tohoto modelu rozdělí na oktanty podle os sou-řadného systému. V každém oktantu, ve kterém je dostatek bodů, se proložím novýmodel a opět testuji konzistenci. Pokud je konzistentní, pak jej uložím do výslednémnožiny rekonstruovaných lokálních modelů. Zde uvádím zápis algoritmu rekon-strukce víceměřítkových šupin:
Algoritmus 7.1 Víceměřítkových lokálních modelů pomocí verifikace1. Prolož všemi body šupinu a vlož ji do testovacího seznamu.2. Dokud není testovací seznam prázdný, vyjmi šupinu z vrcholu testovacího seznamu aproveď s ní následující kroky:a) Verifikuj ji podle algoritmus 5.2.b) Je-li konzistentní, zařaď ji do seznamu výsledných šupin a vrať se k bodu 2.c) V opačném případě rozděl prostor, který zabírala aktuální šupina, na oktanty.V každém oktantu, kde je více jak k bodů prolož šupinu a vlož ji do testovacíhoseznamu.
Pro praktickou realizaci tohoto algoritmu jsem prostor 3D bodů pravidelně rozdělildo základních krychlí. Hrana krychlí dávala nejmenší rekonstruovanou velikost šupin.Počet základních krychlí v každém směru byl mocninou dvou. Nad těmito buňkamijsem postavil oktantový strom. Každý list stromu jednoznačně definoval množinuzákladních buněk, které pod něj spadaly a tím i množinu bodů, které obsahoval.Algoritmus 7.1 pak efektivně pracuje nad tímto stromem.Šupiny rekonstruované algoritmem 7.1 zobrazuje obr. 7.8. Menší lokální modely
vznikají v místech s větší křivostí povrchu, zatímco větší tam, kde je povrch rovin-nější. Rekonstrukce porcelánové konvice tedy dopadla tak, jak jsme zamýšleli. Její
Velikost šupin proměnná pevná
8mm 4mm 2mm celkem 2mm
Počet šupin 69 1069 3414 4552 8672
Obrázek 7.8 Rekonstrukce konvice s víceměřítkovými lokálními modely. Barva modelů odpovídá rekonstruovanévelikosti. Největší červené modely mají 8mm v průměru, menší žluté 4mm a nejmenší zelené 2mm. Z tabulky počtumodelů můžeme vyčíst, že počet modelů klesl o 47,5% při zachování stejné přesnosti.
83
7 Experimenty s reálnými objekty
povrch je velmi výhodný, protože má homogenní odrazivostní funkci a hlavně nemávlastní texturu. Ta je pak dána pouze projekcí náhodného vzoru. U povrchů, jejichžcelková textura vzniká součtem vlastní a náhodné textury, však dostaneme méněpozitivní výsledky. Příkladem takového povrchu jsou obličeje na obr. 7.9. Můžemena nich pozorovat i zvláštní jevy, jako je nesymetričnost velikosti šupin levé a pravétváře. Domníváme se, že hlavní příčinou je opět chyba kalibrace.
Rekonstrukce levé tváře dopadla podstatně hůře, obsahuje mnoho malých modelův poměrně rovinných oblastech. Je to tím, že byla pokryta plnovousem, takový po-vrch je pod hranicí rozlišení obrazů a konzistence vychází nízká. Ze stejného důvodunedošlo ani k rekonstrukci vlasů. Na pravé tváři pozorujeme požadované pokrytírůzně velkými šupinami. Ale v oblasti úpatí nosu a očních jamek vidíme v rekon-struovaném povrchu díry. Snížíme-li práh konzistence ve verifikačním algoritmu, díryse zacelí, ale v jiných místech dojde ke generování příliš velkých modelů. Znamenáto, že pro složitější povrchy (s vlastní texturou, z různých odrazivostních materiálů)nenajdeme ani manuálně jeden práh konzistence pro celý globální model.
Ukazuje se, že rekonstrukce víceměřítkových lokálních modelů pomocí konzis-tence modelu s obrazy je možná, ale jen pro omezenou třídu modelů s homogennívlastní texturou a stejným modelem odrazivosti v celé rekonstruované scéně. Tentoexperiment ukázal, že nadějnější se jeví alternativní způsob, který využívá pouzeodhadu hustot pravděpodobnosti povrchu v podobě bodové množiny. Parametrymodelů, včetně jejich velikostí se určí pravděpodobnostním odhadem, např. pomocínějaké varianty EM algoritmu [7]. Zde se nalézá možnost dalšího výzkumu.
Obrázek 7.9 Rekonstrukce obličejů s víceměřítkovými lokálními modely. Velikost největ-ších červených modelů je tentokráte 16mm a nejmenších modrých 2mm.
84
Přímá rekonstrukce lokálních modelů 7.4
7.4 Přímá rekonstrukce lokálních modelů
Metodu, kterou zde v hrubých rysech nastíním, nemám experimentálně podpořenu.Protože však jde aplikaci optimalizace a verifikace, zmíním se o ní.Jde o rekonstrukci lokálních modelů bez znalosti jejich počátečních parametrů
získaných například stereorekonstrukcí. Princip je velmi jednoduchý a naivní. Vy-generujeme modely všech možných poloh, orientací a možná i velikostí a verifikacívybereme pravděpodobné kandidáty popisující povrch. Jejich parametry vyladímepomocí optimalizace. Je jasné, že tato metoda je algoritmicky velmi časově náročná,zato však má jednu výhodu: lze ji velmi snadno paralelizovat, neboť každý lokálnímodel počítáme zvlášť i v každé jeho parametrizované instanci.
85
8 Závěr
Navrhl jsem a otestoval dvě nové metody verifikace a zpřesnění modelu povrchu.Tyto metody zapadají do celého řetězce úloh rekonstrukce povrchu třírozměrnéhoobjektu tak, jak je dlouhodobě vytvářena Dr. Šárou v Centru strojového vnímání.Práce se zabývá stadiem, ve kterém je povrch reprezentován souborem lokálních mo-delů. Věnuje se kontrole a zpřesnění geometrických vlastností těchto modelů a jsouk ní využívány pouze zkalibrované intenzitní obrazy rekonstruovaného objektu. Me-tody jsou založeny na zpětném promítnutí lokálních modelů do (minimálně) dvouobrazů.Za určitých podmínek může vzájemná konzistence průmětů vyjadřovat přesnost
geometrických parametrů modelu. V této práci jsem tyto podmínky teoreticky od-vodil. Nedodržení těchto podmínek vede ke zhoršení přesnosti nebo dokonce chybámpři kontrole a zpřesnění.Navrhl jsem tři způsoby průmětu modelu do obrazů: dva způsoby projekce bo-
dové aproximace modelu a jeden přímým promítnutím parametrů modelu. Dále jsemvybral čtyři statistiky, vyjadřující konzistenci průmětů. Tyto konzistenční statistikyse liší invariantností vůči jasovým deformacím. Myslíme jimi například nelambertov-skou odrazivost povrchu, stíny a zákryty, diskretizaci a kvantizaci jasu, šum kamera jejich rozdílnost. Výpočet statistik konzistence uvádí algoritmus 5.1 na str. 50.V experimentální části práce jsem tyto čtyři statistiky intenzivně testoval. Dopředutotiž nebylo zřejmé, která statistika je ke kontrole nejvýhodnější, protože s invari-antností statistiky zároveň roste ztráta její informativnosti o vlastnostech povrchu.
8.1 Verifikace
Na základě výše popsaných teoretických a experimentálních rozborů jsem navrhlmetodu verifikace lokálního modelu. Jde o rozhodovací úlohu, která určuje, zda jemodel konzistentní s obrazy či nikoliv. V práci ukazuji, že pro verifikaci je výhodnéjako statistiku konzistence použít Spearmanův korelační koeficient (5.63). Má velmidobrý poměr mezi zachováním množství informace v obraze a invariantností vůčijasovým deformacím.Našel jsem několik možností, jak vyhodnotit tuto úlohu jako statistické rozhod-
nutí. Bohužel, všechny tyto statistické testy jsou pro naši úlohu málo diskrimina-tivní. Ukazuji, že mnoho modelů leží v pásmu nekorelace a zároveň nekonzistence.Oblast nekonzistence je aplikačně závislá. Záleží na texturních vlastnostech povrchu,jeho osvětlení a nastavení kamer. Nastavení diskriminativnějšího prahu konzistenceponechávám na uživateli konkrétní aplikace. Verifikaci popisuje algoritmus 5.2 nastr. 52.
8.2 Zpřesnění
Zpřesnění geometrických parametrů lokálních modelů navrhuji jako optimalizačnímetodu. Při ní maximalizuji zvolenou statistiku konzistence. Ukázal jsem, že nej-vhodnější statistikou konzistence pro tento účel je standardní korelační koeficient (5.61).
86
Víceměřítkové lokální modely 8.3
Je invariantní vůči lineární transformaci a na rozdíl od pořadového Spearmanova ko-eficientu má konzistenční statistika hladší průběh, což je pro optimalizaci důležité.Na str. 54 lze algoritmus zpřesnění lokálních modelů 5.3 nalézt.Dále jsem experimentálně porovnal přesnost optimalizace geometrických para-
metrů modelů s přesností modelů po stereorekonstrukci. Jsou-li splněny odvozenépodmínky, je přesnost srovnatelná. Pokud je povrch dosti rovinný a lze použít mo-dely, jejichž průmět do obrazu je několikrát větší než korelační okénko pro stere-okorespondenci, dostaneme dvakrát přesnějších výsledků. Pokud velikost lokálníchmodelů bude korespondovat s rovinností povrchu, bude tento poznatek zajímavý.Jinak jsou v reálných podmínkách výsledky o něco horší. Musíme vzít v úvahu, žepřesnost naší stereorekonstrukce je velmi dobrá, směrodatná odchylka v hloubce jelepší než 0,1mm. Pokud bychom použili jinou, méně přesnou techniku rekonstrukce,zpřesnění může být významné. Porovnání obou metod podporuje domněnku, žezpřesnění geometrie zpětnou projekcí se od stereorekonstrukce principiálně neliší.
8.3 Víceměřítkové lokální modely
Současná implementace rekonstrukce povrchu v Centru strojového vnímání používášupinový model o jedné zvolené velikosti šupin pro celou scénu. Taková reprezen-tace je značně neefektivní, viz obr. 7.7. Napadlo mě, že by tento nedostatek mohlodstranit algoritmus založený na verifikaci lokálního modelu –šupiny. Tento algorit-mus vytváření víceměřítkových lokálních modelů velikosti 7.1 je uveden na str. 83.Součástí této práce jsou i ukázky takto rekonstruovaných modelů.
8.4 Témata pro další práci
Během experimentů s verifikací lokálních modelů se ukázalo, že významný vliv nasprávnost rozhodnutí má volba obrazových párů, ze kterých se počítá konzistence.Pro naše experimenty jsem měl k dispozici čtyři obrazy, tedy šest obrazových párů.Několik experimentů uvedených v této práci jsem provedl pro každý obrazový párzvlášť. Výsledky byly dosti rozdílné. Důvodem bylo např. to, že některá kameraviděla povrch pod ostrým úhlem nebo se jí povrch leskl. Z tohoto pohledu vidímjako velmi významné zabývat se výběrem vhodných obrazů, které právě používámek rekonstrukci toho kterého místa na povrchu scény. Nalézám k tomu minimálně třidobré důvody:• Informativnost. Volit chceme obraz dosud málo zřetelných nebo neviděných míst.Také se můžeme zaměřit na charakteristická místa povrchu.
• Radiometrii. Volit chceme ty obrazy, které vyhovují lambertovské podmínce.• Geometrii. Čím jsou obrazy dále od sebe, tím menší je chyba výpočtu geometrie,ale tím menší je korelovanost obrazů.
Dále se nabízí otázka, zda není lepší využít více obrazových párů, protože můžemezískat silnější podporu konzistence. Systém, který by z nabízených obrazů volil opti-mální pár ke kontrole nebo ke zpřesnění modelu nebo by dokonce stanovil optimálnípozice k sejmutí takového páru obrazů, by mohl být tématem navazujícího výzkumu.
Při detailním zkoumání výsledků navržených metod jsem objevil několik nepřesnostív různých fázích pasivní rekonstrukce povrchu používané v CMP. Předně se jednáo systematický posun rekonstruovaných povrchů z různých párů obrazů. Protožetuto chybu vykazuje i povrch optimalizovaný, lze snadněji lokalizovat příčinu. Musíjít o tu část, která je použita ve stereu i optimalizaci. Nejvážnějším kandidátem se
87
8 Závěr
nabízí kalibrace. Proto navrhuji optimalizovat všechny kamery metodou narovnánísvazku paprsků. Tento postup nabízí obecné řešení minimalizující chybu reprojekcebodů. Pro naši optimalizační úlohu se nehodí, pro její velkou výpočetní složitost přirelativně velkém počtu modelů. Lze ji však aplikovat na několika málo desítkáchvybraných bodů před rekonstrukcí lokálních modelů. Věříme, že by se výrazně sní-žila odhalená chyba. Zpřesnili bychom jak rekonstrukci, tak v této práci navrženouverifikační proceduru.
Další pozorování ukazují na jistou nesymetričnost v rekonstrukci, jejíž důvody sizatím neumíme vysvětlit. Může jít o projev nějakého zjednodušení, rys který jsmesi neuvědomovali nebo chybu kódu. Každopádně by bylo dobré je vysvětlit.
Na závěr uvádím, že implementované algoritmy i měřená data jsou k dispozici k dal-šímu výzkumu v Centru strojového vnímání.
88
Literatura
[1] P. S. Aleksandrov. Combinatorial Topology. Graylock Press, Baltimore, MD,1960. 20
[2] Nina Amenta and Marshall Bern. Surface reconstruction by Voronoi filtering.In Proc. 14th Annual Symposium on Computational Geometry, pages 39–48,1998. 23
[3] Nina Amenta, Marshall Bern, and David Eppstein. The crust and the β-skeleton: Combinatorial curve reconstruction. Graphical Models and ImageProcessing, 60(2):125–135, 1988. 23
[4] Nina Amenta, Marshall Bern, and Manolis Kamvysselis. A new Voronoi-basedsurface reconstruction algorithm. In Proceedings of SIGGRAPH’98, Compu-ter Graphics Proceedings, Annual Conference Series, pages 415–421, Orlando,Florida, July 1998. ACM SIGGRAPH. 23
[5] Jiří Anděl. Matematická statistika. SNTL, Praha, Česká republika, 1978. 51
[6] Simon Baker, Terence Sim, and Takeo Kanade. A characterization of inherentstereo ambiguities. In Proceedings 8th International Conference on ComputerVision, volume 1, pages 428–435, Vancouver, Canada, July 2001. IEEE Com-puter Society Press. 22
[7] Christopher M. Bishop. Neural Networks for Pattern Recognition. OxfordUniversity Press, 1996. 26, 68, 84
[8] Heinrich H. Bülthoff, Shimon Y. Edelman, and Michael J. Tarr. How are three-dimensional objects represented in the brain? Memo can be obtain from theserver of Massachusetts Institute of Technology on the address publications.ai.mit.edu/ai-publications/1994/AIM-1479.ps.Z. 15
[9] Vicent Caselles, Ron Kimmel, Guillermo Sapiro, and Catalina Sbert. Threedimensional object modeling via minimal surfaces. In Bernard Buxton andRoberto Cipolla, editors, European Conference on Computer Vision, volume 1of LNCS 1065, pages 97–106, Cambridge, UK, April 1996. Springer. 19, 20, 23
[10] Mark de Berg, Marc van Kreveld, Mark Overmars, and Otfried Schwarzkopf.Computational Geometry. Algorithms and Applications. Springer-Verlag, 1997.19
[11] Hervé Delingette. Simplex meshes: a general representation for 3d shape re-construction. Technical Report 2214, Institut National de Recherche en Infor-matique et en Automatique, 06902 SOPHIA–ANTIPOLIS Cedex France, mar1994. 19, 20, 23, 24
[12] Matthias Eck and Hugues Hoppe. Automatic reconstruction of B-spline sur-faces of arbitrary topological type. In Computer Graphics (SIGGRAPH ’96Proceedings), pages 325–334, New Orleans, LA, USA, August 1996. 19
[13] Herbert Edelsbrunner. Weighted alpha shapes. Technical Report 1760, Dept.of CS, University of Illinois at Urbana-Champaign, Urbana, Illinois, 1992. 19,23
[14] Herbert Edelsbrunner and Ernst P. Mücke. Three-dimensional apha shapes.ACM Transaction on Graphics, 13(1):43–72, January 1994. 3-D Delaunay tri-angulation. 19
[15] Olivier Faugeras and Renaud Keriven. Complete dense stereovision using le-vel set method. In Hans Burkhardt and Bernd Neumann, editors, Proc. 5thEuropean Conference on Computer Vision, volume 1 of LNCS, pages 379–393.Springer, June 1998. 19, 20, 23, 29
[16] Paolo Favaro. Shape from focus/defocus. http://citeseer.nj.nec.com/462820.html. 22
[17] Leila De Floriani, Paola Magillo, and Enrico Puppo. Multi-shapes: Level-of-detail in object reconstruction. 20
[18] P. Fua and Y. G. Leclerc. Using 3-Dimensional meshes to combine image-based and geometry-based constraints. Technical report, SRI International,333 Ravenswood Avenue, Mentlo Park, CA 94025, USA, 1994. 19, 20, 23, 24
[19] P. Fua and Y. G. Leclerc. Object-centered surface reconstruction: Combiningmulti-image stereo and shading. International Journal of Computer Vision,16:35–56, 1995. 19
[20] P. Fua and Y. G. Leclerc. Using 3-Dimensional meshes to combine image-based and geometry-based constraints. Technical report, SRI International,333 Ravenswood Avenue, Mentlo Park, CA 94025, USA, 1995. 19, 24
[21] P. Fua and P. Sander. Reconstructing surfaces from unstructured 3D points. InProc. ARPA Image Understanding Workshop, San Diego, CA, January 1992.18, 19
[22] Pascal Fua. Reconstructing complex surfaces from multiple stereo views. TechNote 550, Artificial Intelligence Center, SRI International, Menlo Park, CA,November 1994. 19, 28, 48
[23] Jacob E. Goodman and Joseph O’Rourke, editors. Handbook of Discrete andComputational Geometry. Discrete Mathematics and its Applications. CRCPress, 1997. 20
[24] W. E. L. Grimson. A computational theory of visual surface interpolation. Phil.Trans. R. Lond. B, 298:395–427, 1982. 20, 23
[25] Gideon Guy and Gérard Medioni. Recovering surfaces, 3-D intersections, and3-D junctions using perceptual constraints. Final technical report, part 5, USCComputer Vision Group, 1995. 19, 24
[26] Song Han and Gerard Medioni. Reconstructing free-form surfaces from sparsedata. In Proc. International Conference on Pattern Recognition, volume 1,pages 100–104, Vienna, Austria, August 1996. IEEE Computer Society Press.extract of Han96a. 19
[27] Song Han and Gérard Medioni. Triangular NURBS surface modeling of scatte-red data. In IEEE Visualization, San Francisco, CA, 1996. 19, 21
[28] Jacques Harthong, 2000. Inverse Moiré, http://moire4.u-strasbg.fr/moire/theory/part1.htm. 22
[29] R. Hartley and A. Zisserman. Multiple View Geometry in Computer Vision.Cambridge University Press, Cambridge, UK, 2000. 16, 27, 33, 44
[30] Hideki Hayakawa. Photometric stereo under a light source with arbitrary mo-tion. Journal of the Optical Society of America, 11(11):3079–3089, nov 1994.22
[31] Aleš Holeček and Tomáš Pajdla. Shape reconstruction from images using alphashapes. Technical report, CTU, CMP, KADR, 1996. 19, 23
[32] Hugues Hoppe. Progressive meshes. In Computer Graphics (SIGGRAPH ’96Proceedings), pages 99–108, New Orleans, LA, USA, August 1996. 20
[33] Hugues Hoppe. View-dependent refinement of progressive meshes. In ComputerGraphics (SIGGRAPH ’97 Proceedings), 1997. 19, 20
[34] Hugues Hoppe, Tony DeRose, and Tom Duchamp. Mesh optimization. InProceeding of SIGGRAPH 20th Annual International Conference on ComputerGraphics and Interactive Techniques, pages 19–26, Anaheim, CA, USA, August1993. 19, 20, 23
[35] Hugues Hoppe, Tony DeRose, Tom Duchamp, John McDonald, and WernerStuetzle. Surface reconstruction from unorganized points. In Proc. ComputerGraphics (SIGGRAPH ’92), volume 26, pages 71–78, July 1992. 18, 19
[36] B. K. P. Horn. Robot Vision. The MIT Press, Cambridge, Massachusetts, USA,1986. 17, 35
[37] Berthold K. P. Horn. Extended Gaussian Images. Proceedings of the IEEE,72(12):1671–1686, December 1984. 17, 33
[38] Berthold Klaus Paul Horn. Shape from shading: A method for obtaining theshape of a smooth opaque sobject from one view. PhD thesis, M.I.T., Depart-ment of Electrical Engineering, Cambridge, MA., USA, 1970. 22
[39] Maurice Kendall and Jean Dickinson Gibbons. Rank Correlation Methods. Ed-ward Arnold, 1990. 49
[40] J. J. Koenderink. Solid Shape. The M.I.T. Press, 1990. 22
[41] J. J. Koenderink and A. J. van Doorn. Internal representation of solid shapewith respect to vision. Biological cybernetics, 32(4):211–216, 1979. 15
[42] Eric Krotkov and R. Bajcsy. Active vision for reliable ranging: Cooperating fo-cus, stereo, and vergence. International Journal of Computer Vision, 11(2):187–203, 1993. 22
[43] Johann Heinrich Lambert. Photometria, Sive de mensura et gradibus Luminis,Colorum et Umbrae. Eberhard Klett, Augsburg, Germany, 1760. 17, 35
[44] A. Leonardis, A. Jaklič, and F. Solina. Superquadrics for segmenting and mo-deling range data. IEEE Transactions on Pattern Analysis and Machine Intel-ligence, 19(11):1289–1295, November 1997. 20
[45] Chia-Wei Liao and Gérard Medioni. Surface approximation of a cloud of 3Dpoints. Final technical report, part 4, USC Computer Vision Group, 1995. 19,20, 23
[46] Chia-Wei Liao and Gérard Medioni. Surface approximation of complex 3-Dobjects. Graphical Models and Image Processing, 57(1):67–74, 1995. 19, 20,24
[47] Jean-Christophe Lombardo and Claude Puech. Oriented particles: A tool forshape memory objects modelling. In Proc. Graphics Interface, Quebec City,Canada, May 1995. 18
[48] H. C. Longuet-Higgins. A computer algorithm for reconstruction a scene fromtwo projections. Nature, 293(10):133–135, September 1981. 16
[49] William E. Lorensen and Harvey E. Cline. Marching cubes: A high resolution3D surface construction algorithm. Computer Graphic, 21(4):163–169, jul 1987.19, 24
[50] Chhandomay Mandal, Baba C. Vemuri, and Hong Qin. Shape recovery using dy-namic subdivision surfaces. In Proc. of International Conference on ComputerVision. The Institute of Electrical and Electronics Engineers, Narosa PublishingHouse, January 1998. 19, 20, 23
[51] D. Marr. Vision – A Computational Investigation into the Human Represen-tation and Processing of Visual Information. W. H. Freeman and Co., SanFrancisco, 1982. 18, 22
[52] S.K. Nayar, Katsushi Ikeuchi, and Takeo Kanade. Surface reflection: physi-cal and geometrical perspectives. IEEE Transactions on Pattern Analysis andMachine Intelligence, 13(7):611 – 634, July 1991. 31
[53] Tomáš Pajdla. Laser plane range finder – the implementation at the CVL. Tech-nical Report Nr. K335-95-98, Czech Technical University, Prague, Czech Tech-nical University, Prague, October 1995. 18, 22, 56
[54] Athanasios Papoulis. Probability, Random Variables, and Stochastic Processes.McGraw-Hill International Editions, 3rd edition, 1991. 49
[55] A. P. Pentland. A new sense for depth of field. IEEE Transactions on PatternAnalysis and Machine Intelligence, 9(4):523–531, 1987. 22
[56] Less Piegl and Wayne Tiller. The Nurbs Book. Springer Verlag, 2 edition, 1997.21
[57] Riccardo Poli, Giuseppe Coppini, and Guido Valli. Recovery of 3D closed sur-faces from sparse data. Computer Vision, Graphics, and Image Processing:Image Understanding, 60(1):1–25, July 1994. 19, 20, 23
92
Literatura
[58] Franco P. Preparata and Michael Ian Shamos. Computational Geometry, AnIntroduction, chapter 5. Proximity: Fundamental Algorithms, pages 179–218.Texts and Monograph in Computer Science. Springer-Verlag, New York, 1985.19
[59] Glynn Robinson, Lewis Griffin, and Alan Colchester. The Delaunay/Voronoi se-lection graph: a method for extracting shape information from 2-D dot-patternswith an extension to 3-D. In David Hogg and Roger Boyle, editors, British Ma-chine Vision Conference, pages 19–28, Leeds, U.K., September 1992. Springer-Verlag London. 19
[60] Radim Šára. Data-flow in stereo-based surface reconstruction system imple-mented in GRASP lab: A general description. Internal memo, GRASP Lab,University of Pennsylvania, December 1996. 18
[61] Radim Šára. Accurate natural surface reconstruction from polynocular stereo.In Proceedings NATO Advanced Research Workshop: Confluence of ComputerVision and Computer Graphics, NATO ASI Series, The Netherlands, August1999. IEEE Slovenia Section, Kluwer Academic Publishers. 13, 18, 21
[62] Radim Šára. The class of stable matchings for computational stereo. ResearchReport CTU-CMP-1999-22, Center for Machine Perception, Czech TechnicalUniversity, Prague, Czech Republic, November 1999. 22, 68
[63] Radim Šára. Finding the largest unambiguous component of stereo matching.In Anders Heyden, Gunnar Sparr, Mads Nielsen, and Peter Johansen, editors,Proceedings 7th European Conference on Computer Vision, volume 3 of LectureNotes in Computer Science, pages 900–914, Berlin, Germany, May 2002. Sprin-ger. 22
[64] Radim Šára and Ruzena Bajcsy. Fish-scales: Representing fuzzy manifolds. InProc. of International Conference on Computer Vision, pages 811–817. TheInstitute of Electrical and Electronics Engineers, Narosa Publishing House, Ja-nuary 1998. 18, 19, 25, 26
[65] James Albert Sethian. Level Set Methods and Fast Marching Methods EvolvingInterfaces in Computational Geometry, Fluid Mechanics, Computer Vision, andMaterials Science. Cambridge University Press, 1999. 24
[66] Milan Šonka, Václav Hlaváč, and Roger D. Boyle. Image Processing, Analysisand Machine Vision. PWS, Boston, USA, second edition, 1998. 16, 17, 21
[67] James J. Stoker. Differential Geometry. John Wiley, 1989. 32
[68] Richard Szeliski. Fast surface interpolation using hierarchical basis functions.10(6):222–228, June 1990. 22
[69] Richard Szeliski and Demetri Terzopoulos. From splines to fractals. ComputerGraphics, 23(3):51–60, July 1989. 20, 23
[70] Richard Szeliski and David Tonnesen. Surface modeling with oriented particlesystems. Computer Graphics (SIGGRAPH ’92), 26(2):185–194, July 1992. 18,19, 28
93
Literatura
[71] Chi-Keung Tang and Gérard Medioni. Integrated surfaces, curve and junctioninference from sparse 3-D data sets. In Proc. of International Conference onComputer Vision. The Institute of Electrical and Electronics Engineers, NarosaPublishing House, January 1998. 24
[72] Bill Triggs, Philip McLauchlan, Richard Hartley, and Andrew Fitzgibbon.Bundle adjustment – A modern synthesis. In W. Triggs, A. Zisserman, andR. Szeliski, editors, Vision Algorithms: Theory and Practice, LNCS, pages 298–375. Springer Verlag, 2000. 27
[73] S. Ullman. The Interpretation of Visual Motion. MIT Press, Cambridge, Ma,1979. 22
[74] S. Ullman. High-level Vision: Object Recognition and Visual Cognition. ABradford Book. MIT Press, Cambridge, Ma., USA, 1996. 22
[75] Robert J. Woodham. Photometric stereo: A reflectance map technique for deter-mining object relief from image intensity. In Proceedings of the Second NationalConference of the Canadian Society for Computational Studies of Intelligence,pages 117–124, Toronto, 1978. 22
[76] Robert J. Woodham. Photometric method for determining surface orientationfrom multile images. Optical Engineering, 19(1):139–144, January/February1980. 22
[77] Robert J. Woodham. Gradient and curvature from the photometric-stereo me-thod, including local confidence estimation. Journal of Optical Society of Ame-rica A, 11(11):3050–3068, November 1994. 22
[78] T. Yatagai, S. Nakadate, M. Idesawa, and H. Saito. Automatic fringe analysisusing digital image processing techniques. Optical Engineering, (21):432–435,1982. 22
[79] Hong-Kai Zhao, Stanley Osher, and Ronald Fedkiw. Fast surface reconstructionusing the level set method. In 1st IEEE Workshop on Variational and LevelSet Methods, pages 194–202, Vancouver, Canada, July 2001. IEEE ComputerSociety. 24
94
Publikace autora
Publikace vztahující se k tématu disertační práce
Články v tuzemských časopisech
[A] Vladimír Smutný, Radim Šára, Pavel Krsek, and Vít Zýka. Trojrozměrné měřeníreliéfu dlaždic. Automa, 8(8-9):28–29, říjen 2002. ISSN 1210-9592.
Příspěvky na zahraničních konferencích
[B] Vít Zýka and Radim Šára. Polynocular local image dissimilarity for 3D recon-struction. In Aleš Leonardis and Franc Solina, editors, Proc. Computer VisionWinter Workshop 1998, pages 15–25. IEEE Slovenia Section, Ljubjlana, Slove-nia, February 1998. ISBN 961-6062-13-1. 47
[C] Vít Zýka and Radim Šára. Polynocular image set consistency for local modelverification. In Robert Sablatnig, editor, Application of 3D-Imaging and Graph-based Modeling 2000 24th Workshop of the Austrian Association for Pattern Re-cognition (ÖAGM/AAPR), pages 81–88. Österreichische Computer Gesellschaft,Österreichische Computer Gesellschaft, 1080 Wien, Piaristengasse 19, May 2000.ISBN 3-85403-142-4. 47
Příspěvky na tuzemských konferencích
[D] Vít Zýka and Radim Šára. Scale model refinement for 3D reconstruction. InTomáš Pajdla, editor, Czech Pattern Recognition Workshop ’97, pages 121–125.Czech Pattern Recognition Society, Czech Pattern Recognition Society, Praha,Czech Republic, February 1997.
[E] Vít Zýka and Radim Šára. Fish-scale model refinement for 3D reconstruction. InCzech Technical University Workshop ’98, volume Part I., pages 167–168. CzechTechnical University, none, Praha, Czech Republic, February 1998.
[F] Vít Zýka and Radim Šára. Fish-scale model verification; a sub-step of 3D geo-metric model reconstruction. In Czech Technical University Workshop ’99, page112. Czech Technical University, none, Praha, Czech Republic, February 1999.
[G] Vít Zýka and Radim Šára. Local 3D model verification and refinement. InPoster ’99, page 1. Czech Technical University, none, Praha, Czech Republic,June 1999.
[H] Vít Zýka and Radim Šára. Local planar model verification in a polynocularimage set. In Tomáš Svoboda, editor, Czech Pattern Recognition Workshop 2000,pages 107–110. Czech Pattern Recognition Society, Czech Pattern RecognitionSociety, Praha, Czech Republic, February 2000. ISBN 80-238-5215-9.
[I] Vít Zýka and Radim Šára. Local model consistency for 3D reconstruction, April2001. Transfer 2001, Technická univerzita v Liberci.
95
Publikace autora
Výzkumné zprávy
[J] Vít Zýka. Recovering accurate geometric surface model from passive stereo vi-sion. Technical Report K335-98-153, ČVUT FEL, dep. of Control Engineering,Praha, Czech Republic, January 1998. Thesis proposal. 47
[K] Vladimír Smutný, Pavel Krsek, Vít Zýka, Tomáš Pajdla, and Radim Šára. Opti-cal measurement of a vehicle wheel geometry. Research Report CAK–340–03–1–2000–03, CTU–CMP–2000–24, Center for Machine Perception, Czech TechnicalUniversity, Prague, Czech Republic, December 2000.
[L] Jiří Matas, Pavel Mrázek, Radim Šára, Vladimír Smutný, Vít Zýka, Ondřej Dr-bohlav, and Václav Hlaváč. Zpracování obrazu z bezpilotního letounu Sojka. Re-search Report CTU–CMP–2001–35, Center for Machine Perception, K333 FEECzech Technical University, Prague, Czech Republic, December 2001. Confiden-tial.
Ostatní publikace
Články v zahraničních časopisech
[M] Vít Zýka. The semaphore alphabet. TUGboat, The Communication of the TeXUsers Group, 20(4):348–350, December 1999. ISSN 0896-3207.
Články v tuzemských časopisech
[N] Vít Zýka. Balíček maker cards pro sazbu kartiček. Zpravodaj Československéhosdružení uživatelu TEXu, 7(4):224–230, December 1997.
[O] Vít Zýka. Zvýraznění bloku textu s možností stránkového zlomu. ZpravodajČeskoslovenského sdružení uživatelu TEXu, 9(3):146–153, 1999.
[R] Vít Zýka. Používáme pdfTeX II: prezentace fotografií aneb jak na hypertext.Zpravodaj Československého sdružení uživatelu TEXu, 12(1):13–21, May 2002.ISSN 1211-6661.
[S] Vít Zýka. Používáme pdfTeX III: video a zvuk v prezentaci. Zpravodaj Česko-slovenského sdružení uživatelu TEXu, 12(2):47–55, November 2002. ISSN 1211-6661.
Další publikace
[T] Vít Zýka. Inteligentní zpracování vektorových dat. Master’s thesis, ČVUT FEL,katedra Řídící techniky, Praha, Česká republika, February 1996.
[U] Vít Zýka. Inteligentní zpracování vektorových dat. In ČVUT FEL, Poster1996—sborník abstrakt, page 110. Praha, Česká republika, June 1996.
96
Publikace autora
[V] Vít Zýka, Jan Buriánek, Léon Rothkrantz, and Václav Hlaváč. Nostrils andchin segmentation. Technical Report 96-159, TU Delft, faculty of Mathema-tics and Informatics, Delft, The Netherlands, September 1996. Report #96-159from students exchange stay.
[W] Vít Zýka. Pár typografických poznámek, April 1997. Nepublikováno.
[X] Vít Zýka. Jak psát URL, April 1998. Internal report.
[Y] Vít Zýka. Preparing posters with plakat package, May 1999. Manual.
[Z] Vít Zýka. TEX a pdf. In Jan Kasprzak and Petr Sojka, editors, SLT 2002 –sborník semináře o Linuxu a TEXu, volume 1, pages 69–77. CSTUG, CZLUG,Konvoj, CSTUG, CZLUG, Brno, Czech Republic, November 2002. ISBN 80-7302-043-2.
