Počítačové vidění pro informatiku - Úloha 2
Projektivní rekonstrukce ze dvou pohledů

Josef Šivic

Contents

• Contents
• Zadání
• Výpočet epipolární geometrie
  • Odhad fundamentální matice
  • Výpočet epipolární geometrie z naměřených dat
• Rekonstrukce z kalibrovaných kamer
  • Triangulace
  • Příčka mimoběžek
• Projektivní rekonstrukce
  • Výpočet projektivní rekonstrukce
  • Výpočet transformační matice H
• Závěr
• Bibliography

Zadání

Máte dva obrazy téže prostorové scény sejmuté stejnou kamerou ze dvou různých míst viz. obr. 1.

• pomocí corrgui zadejte korespondence v obou obrazech
• nalezněte epipolární geometrii
• proveďte rekonstrukci ze zadaných kalibrovaných kamer
• nalezněte projektivní rekonstrukci
• nalezněte transformaci mezi skutečnou scénou (z kalibrovaných kamer) a nalezenou projektivní rekonstrukcí.

  

Figure 1: Vstupní obrázky s vyznačenými 15 korespondencemi

  

Figure 2: Vstupní obrázky s vyznačenými 25 korespondencemi

Výpočet epipolární geometrie

Mějme dva obrazy téže scény s vyznačenými n korespodujícími body

$${\bf u}_i^k=\left [\begin {array}{c} u_i\\ v_i\\ 1\end {array}\right ],$$

kde k=1,2 je počet pohledů(obrazů) a i=1...n je počet bodů. ${\bf u}_i^k \in \mathcal{P}_2$. Dle [1] str.460-2 lze pro takovouto soustavu bodů odvodit epipolární geometrii, která je vyjádřena rovnicí

$${{\bf u}_i^1}^T F\, {\bf u}_i^2 = 0,$$ (1)

kde F se nazývá fundamentální matice. Fundamentální matice tedy plně určuje vztah mezi korespondujícími body ve dvou obrazech. Z rovnice (1) je zřejmé, že $hod\, F<3$. [Proč je ale hodnost F právě 2?]

Z rovnice (1) lze také odvodit rovnice epipolárních přímek ${\bf\lambda}_i^k$.

Vyjdeme z

$$\underbrace{{{\bf u}_i^1}^T F}_{{\bf\lambda}_i^2}\, {\bf u}_i^2 = 0$$

a

$${{\bf u}_i^1}^T \underbrace{F\, {\bf u}_i^2}_{{\bf\lambda}_i^1} = 0.$$

Rovnice epipolár zapíšeme jako

$${{\bf\lambda}_i^2}^T{\bf u}_i^2=0$$

a

$${{{\bf u}_i^1}^T}{\bf\lambda}_i^1=0.$$

Epipóly ${\bf e}^1$ a ${\bf e}^2$ lze spočíst z rovnic

$${{\bf e}^1}^T F=0$$

a

$$F\,{{\bf e}^2}=0.$$

Význam epipoláry a epipólu je následující

• Epipolární přímka v prvním obrázku je obrazem spojnice středu druhé kamery a bodu scény.
• Epipól v prvním obraze je obrazem středu druhé kamery.

   
Odhad fundamentální matice

Matice F má devět neznámých koeficientů. Napíšeme-li rovnici (1) pro osum bodů a přepíšeme-li neznámé koeficienty matice F do vektoru

$${\bf f}=\left [\begin {array}{c} f_{11}\\ \vdots\\ f_{33}\end {array}\right ],$$

lze pak tuto homogenní soustavu 8 rovnic o 9 neznámých zapsat maticově ve tvaru

$$A\,{\bf f}=0.$$

Je-li hod A = 8, soustava má jedno netriviální řešení.

V naměřených datech je ale vždy šum, který způsobí, že rovnice (1) neplatí přesně. Matice $\hat{F}$, kterou spočteme z osmi naměřených bodů, se od správné matice F liší. Proto je výhodné matici A sestavit z více než osmi bodů a hledat řešení této přeurčené soustavy metodou nejmenších čtveců (např. pomocí SVD, viz.PVI-Úloha č.1). Hodnost spočtené matice $\hat{F}$ je obecně 3. Aby platila rovnice (1), je potřeba hodnost $\hat{F}$ snížit pomocí SVD na 2 (viz.PVI-Úloha č.1). Nesnížíme-li hodnost $\hat{F}$ na 2, epipoláry se neprotnou v jednom bodě.

Výpočet epipolární geometrie z naměřených dat

Postup z předchozího odstavce jsme aplikovali na dvě množiny korespondencí. V prvním přápadě jsme použili 15 bodů (Obr.3) v druhém případě nově zadaných 25 bodů (Obr.4). Z obrázků je vidět, že v obou případech nám vyšla jiná epipolární geometrie. Obě řešení mohou být správná. Výpočet epipolární geomterie ze 7 bodů (nejmenší možný počet bodů) vede totiž na rovnici třetího stupně a ta může mít až 3 různá řešení.

  

Figure 3: Epipolární geometrie získaná z 15 bodů

  

Figure 4: Epipolární geometrie získaná z 25 bodů

Rekonstrukce z kalibrovaných kamer

Pro bod ${\bf\bar{X}_i} \in \mathcal{P}^3$ skutečné scény a jeho obraz ${\bf \bar{u}_i} \in \mathcal{P}^2$, získaný perspektivní kamerou platí zobrazovací rovnice

$$\alpha_i {\bf\bar{u}}_i=P{\bf\bar{X}}_i,$$ (2)

kde P je $3 \times 4$ projektivní matice. Odvození viz. [1] str. 449-53.

Díváme-li se tedy na 3D scénu stejnou kamerou z dvou různých míst, dostaneme pro každý bod scény, který je vidět oběma kamerami dvě rovnice

$$\alpha_i^k {\bf\bar{u}}^k_i=P^k{\bf\bar{X}}_i,$$ (3)

kde k=1,2.

Triangulace

V našem případě máme změřeny body ${\bf\bar{u}}^k_i$, známe projekční matice P^k (z kalibrace kamer, zadáno) a chceme získat body ${\bf\bar{X}}_i$ ve scéně a jím odpovídající koeficienty $\alpha_i^k$. Tento problém lze vyřešit triangulací. Promítneme body ${\bf\bar{u}}^k_i$ zpětně přes středy příslušných kamer do scény. Vzniknou tak dvě přímky, které se protnou právě v bodě ${\bf\bar{X}}_i$. V reálném případě jsou naměřené body ${\bf\bar{u}}^k_i$ zatíženy šumem a takto vzniklé přímky se protnout nemusí - mohou být mimoběžné. Bod ${\bf\bar{X}}_i$pak získáme jako střed příčky těchto mimoběžek.

Příčka mimoběžek

Viz. sešit.

Triangulací a výpočtem příčky mimoběžek spočítáme rekonstrukci scény z kalibrovaných kamer (viz obr. 5).

  

Figure 5: Čtyři různé pohledy na scénu rekonstruovanou z kalibrovaných kamer

Rekonstruované body pro kontrolu promítneme zpět do vstupních obrázků (viz obr. 6). Zpětně promítnuté body se téměř kryjí s vyznačenými vstupními body.

  

Figure 6: Zpětné projekce scény rekonstruované z kalibrovaných kamer

Projektivní rekonstrukce

Nemáme-li k dispozici projekční matice kamer ani žádnou apriorní informaci o kamerách nebo o scéně, můžeme se pokusit spočítat projektivní rekonstrukci. Projektivní rekonstrukce scény z obrazových bodů ${\bf u}_i^k$ jsou takové dvě množiny

$$\{ P^k, \, k=1,2 \} \; a \; \{ {\bf X}_i, \, i=1...n\} ,$$ (4)

které splňuje rovnici (3). Lze ukázat, že množiny

$$\left \{ \frac{1}{\sigma^k} P^k H^{-1} \right \} \; a \; \left \{ \frac{1}{\lambda_i} H {\bf X}_i \right \},$$ (5)

kde $H \in \mathcal{R}^{4 \times 4}$, $hod \, H=4$, $\sigma^k$, $\lambda_i \in \mathcal{R}$, $\neq 0$, které se liší od (4) o lineární transformaci H jsou také projektivní rekonstrukcí z bodů ${\bf u}_i^k$.

Dále lze ukázat, že souřadnice ${\bf X}_i$ projektivní rekonstrukce se liší od souřadnic ${\bf\bar{X}}_i$ skutečné scény o lineární transformaci H

$$\lambda_i {\bf X}_i = H {\bf\bar{X}}_i,$$ (6)

kde $H \in \mathcal{R}^{4 \times 4}$, $hod \, H=4$, $\lambda_i \in \mathcal{R}$, $\neq 0$.

Výpočet projektivní rekonstrukce

Dosazením rovnic (3) do (1) dostaneme

$${{\bf X}_i}^T {P^1}^T F\, P^2{\bf X}_i = 0,$$ (7)

Naším úkolem je zrekonstruovat matice P¹ a P² tak, aby vyhovovaly rovnicím (7).

Zvolíme-li P¹ ve tvaru

P¹=(I|0),

což znamená, že střed první kamery je umístěn v počátku světových souřadnic, vyjde nám z rovnice (7), že P² je ve tvaru

P²=(A|e²),

kde $A \in \mathcal{R}^{3 \times 3}$, $hod \, A=3$ a e² je epipól v druhém obraze. Z rovnice (7) dále vyplyne, že platí

 

FA = - FA^T, (8)

neboli můžeme říci, že matice FA je antisymetrická. Rozepíšeme-li podmínku (8) a přepíšeme-li prvky A po sloupcích do sloupcového vektoru ${\bf a}=(a_{11} ... a_{33})^T$, dostaneme lineární soustavu rovnic ve tvaru

$$\underbrace{W}_{6 \times 9} \, \overbrace{{\bf a}}^{9 \times 1}=0.$$ (9)

$hod \, F = 2$ tedy $hod \, W = 5$ [Proč?] a prostor řešení soustavy (9) má dimenzi 4. Z prostoru řešení soustavy (9) zvolíme jedno řešení, které po přeuspořádání do matice A splňuje podmínku $hod \, A=3$ ( $det A \neq 0$).

Do výpočtu matice A lze závést i podmínku dobré podmíněnosti matice A. Z prostoru řešení (9) vybereme náhodně mnoho řešení a vybereme to, pro které je matice A nejépe podmíněná.

[Proč je dobré, aby byla matice A dobře podmíněná? (špatná podmíněnost = skoro singularita)]

Znám-li matice P¹ a P², vypočtu z rovnic (3) metodou triangulace a příčky mimoběžek body projektivní rekonstrukce ${\bf X}_i$. Výsledky zpětné projekce projektivní rekonstrukce pomocí spočtených matic P¹ a P² jsou na obrázku 7.

  

Figure 7: Zpětné projekce projektivní rekonstrukce. Body získané zpětnou projekcí projektivní rekonstrukce jsou označeny křížkem +.

Výpočet transformační matice H

Rovnici (6), která určuje vztah mezi skutečnou scénou a její projektivní rekonstrukcí, přepíšeme do tvaru

$$-\lambda_i {\bf X}_i + H {\bf\bar{X}}_i=0$$ (10)

Soustavu (10) lze dále přepsat jako

 

$$-\lambda_i x_i + {h^1}^T {\bf\bar{X}}_i$$ = 0 (11)

$$-\lambda_i y_i + {h^2}^T {\bf\bar{X}}_i$$ = 0

$$-\lambda_i z_i + {h^3}^T {\bf\bar{X}}_i$$ = 0

$$-\lambda_i w_i + {h^4}^T {\bf\bar{X}}_i$$ = 0

Hledáme 16 koeficientů h₁₁...h₄₄ matice H a koeficient $\lambda_i$. Je vidět, že aby existovalo jednodimenziální řešení soustavy (11), potřebujeme alespoň 5 korespondujících dvojic bodů ${\bf X}_i$ a ${\bf\bar{X}}_i$, z nichž (myšleno z každé pětice) jsou každé 4 nekoplanární tzn. neleží v jedné rovině. Máme tedy soustavu 20 rovnic pro 21 neznámých (16 parametrů h_kl a 5 parametrů $\lambda_i$). Kterou lze přepsat do maticového tvaru

$$W \, (h_{11} \ldots h_{44} \lambda_1 \ldots \lambda_5)^T =0$$ (12)

[Proč nesmí být body koplanární? Vyplývá to z důkazu věty o kolineaci v $\mathcal{P}^2$. Geom. smysl?]

[Jsou-li čtyři body koplanární (lze říci lineárně závislé tzn. každý lze vyjádřit jako LK ostních třech ), měla by se nějakým způsobem zredukovat hodnost W v soustavě (12), JAK ??]

Mám-li k dispozici více než pět bodů nabízí se možnost sestavit přeurčenou soustavu rovnic (12) a tu pak vyřešit pomocí SVD. Matice W je ale řídká a proto metoda SVD není vhodná. [Experiment to potvrzuje, ale proč SVD špatně pracuje s řídkými maticemi?]

Pro výpočet matice H lze použít ještě další metodu. Aby byla matice H dobře určena, [tzn. popisovala vztah mezi skutečnou scénou a rekonstrukcí v celém prostoru a ne jen v okolí pěti bodů z kterých byla spočtena] je potřeba, aby pětice bodů použitých pro výpočet H, byla po čtveřicích 'co nejméně' koplanární.

Jsou-li 4 body ${\bf X}_i \in \mathcal{P}^3$, i=1...4 koplanární, pak existuje rovina ${\bf a}=(a,b,c,d) \subset \mathcal{P}^3$, ${\bf a} \neq 0$, taková že

$${\bf X}_i \, {\bf a} = 0,$$ (13)

kde i=1...4. Soustavu (13) lze přepsat maticově do tvaru

$$X \, {\bf a} = 0,$$ (14)

Míru koplanarity m zvolíme jako číslo podmíněnosti matice X, $m= \sigma_1/ \sigma_n$, kde $\sigma_i$ jsou singulární čísla matice X. Je-li číslo podmíněnosti velké, matice je blízko singularitě a body ${\bf X}_i$ jsou téměř koplanární. [Dalo by se očekávat, že H nebude dobře zobrazovat právě ve směru kolmém k takovéto rovině]. Výběr pětice bodů pro výpočet matice H probíhá podle následujícího postupu

• Z množiny všech dostupných bodů náhodně vybereme pětici bodů X_i, $i=1 \ldots 5$
• Spočítáme míru koplanarity m_k, $k=1 \ldots 5$ pro všech 5 možných čtveřic bodů, které lze sestavit z vybrané pětice.
• Jako míru koplanarity m celé pětice bodů vybereme nejhorší kombinaci, tedy $m= \max(m_i)$, $k=1 \ldots 5$.
• Postup opakujeme pro velké množství náhodně vybraných pětic a matici H spočteme z pětice, která má nejmenší m.

Jedná se tedy o minimalizaci nejhorší možné chyby.

Použijeme-li pro odhad matice H z rovnice (12) více bodů a SVD, výsledky transformace jsou špatné viz obr. (8). Spočteme-li matici H pomocí rovnice (12) jen z pěti dobře vybraných ('málo koplanárních') bodů. Výsledky trnasformace jsou podstatně lepší viz obr. (9).

  

Figure 8: Pohled na scénu transformovanou maticí H z projektivní rekonstrukce. Matice H byla spočtena ze všech dostupných bodů metodou SVD.

  

Figure 9: Čtyři různé pohledy na scénu transformovanou maticí H z projektivní rekonstrukce. Matice H byla spočtena z pěti bodů s malou mírou koplanarity.

Závěr

Pro dva zadané obrazy jsme nalezli dvě různé epipolární geometrie, které vznikly z různého počtu nezávisle zadaných bodů. I když z druhé množiny obsahující 25 bodů použijeme jen 15 bodů zadaných přibližně na stejných místech jako body první množiny, epipolární geometrie vyjde stále stejná. Z toho je patrná značná závislost výpočtu epipolární geometrie na přesnosti zadaných bodů.

Z naměřených dat jsme provedli pomocí triangulace a příčky mimoběžek rekonstrukci z kalibrovaných kamer.

Vypočetli jsme projektivní rekonstrukci scény a ověřili správnost výpočtu zpětnou reprojekcí bodů. Nalezli jsme transformaci mezi skutečnou scénou a námi vypočtenou projektivní rekonstrukcí. Ukázali jsme, že lepší výsledky při výpočtu transformační matice lze dosáhnout výpočtem z pěti 'málo koplanárních' bodů než pomocí přeurčené soustavy rovnic a SVD.

Bibliography

1

©onka M., Hlavaè V., Boyle R.,
Image Processing, Analysis, and Machine Vision,
PWS, Boston, USA, 1998