6. Geometrija več pogledov

Kako iz dveh ali treh slik dobimo globino. To je poglavje z največ izpitnimi nalogami — 14, 15, 16, 17 in 18 na prvem izpitu ter 1–5 na drugem kolokviju. Skupaj 100 od 500 točk.

Dva pogleda (splošno) ključno

Na osnovi ene slike ne moremo določiti globine (oddaljenosti) točke iz scene vzdolž projekcijskega žarka. Že iz dveh slik (iste scene, a posnete pod različnim kotom) lahko merimo globino — uporabimo triangulacijo.

Oznaka	Pomen
$O$, $O'$	optična centra (luknjici) prve oz. druge kamere
$P$	točka v prostoru
$p$, $p'$	sliki točke $P$ na virtualni slikovni ravnini $\Pi$ in $\Pi'$
$e$, $e'$	epipola posamezne kamere
$l = pe$, $l' = e'p'$	epipolarni premici (daljici)

Virtualni ravnini se nahajata pred luknjico — uporabljeni sta zaradi lažjega risanja. Vse enačbe in razlage veljajo tudi za fizikalno sliko oz. mrežnico, ki se nahaja za luknjico.

Točke $O$, $O'$ in $P$ definirajo ravnino, ki jo imenujemo epipolarna ravnina — točki $p$ in $p'$ ležita na tej ravnini. Epipol $e$ dobimo na presečišču virtualne ravnine $\Pi$ in osnovnice (daljice) $OO'$.

🔑 Epipolarna omejitev — najpomembnejša ideja poglavja

Če sta točki $p$ in $p'$ sliki (projekciji) iste točke $P$, potem mora $p'$ ležati na epipolarni premici, prirejeni točki $p$.

Če poznamo položaj točke $p$, potem lahko potencialne ujemajoče se točke v drugi sliki ležijo le na epipolarni premici $l'$. Ta omejitev igra ključno vlogo v stereo vidu ter pri analizi gibanja — namesto 2D iskanja po celi sliki iščemo po 1D premici.

Originalni prosojnici (str. 75–76)

A. Umerjene (kalibrirane) razmere naloga 14

Predpostavimo, da so notranji parametri obeh kamer poznani. Velja:

na listu

Epipolarna omejitev z osnovno matriko

$$p^T \mathsf{E}\, p' = 0, \qquad \text{kjer } p = [u, v, 1] \text{ in } p' = [u', v', 1]$$

Matrika $\mathsf{E}$ je osnovna matrika (essential matrix), velikosti $3\times3$.

Produkt $\mathsf{E}p'$ interpretiramo kot koordinatni vektor, ki predstavlja epipolarno premico, povezano s točko $p'$, v PRVI sliki (tj. premica $l$):

na listu $$\mathsf{E}p' = [a, b, c]' \qquad \Rightarrow \qquad \text{premica } l:\; au + bv + c = 0$$

Podobno velja za produkt $\mathsf{E}p$, vendar za drugo sliko.

na listu

Definicija osnovne matrike

$$\mathsf{E} = [t_\times]\mathsf{R}, \qquad [a_\times] = \begin{bmatrix} 0 & -a_3 & a_2 \\ a_3 & 0 & -a_1 \\ -a_2 & a_1 & 0 \end{bmatrix}$$

kjer je $t$ vektor $OO'$, $\mathsf{R}$ pa rotacijska matrika, ki poveže drugi pogled s prvim. Poljuben vektor $w'$ (predstavljen v drugem koordinatnem sistemu) je v prvem koordinatnem sistemu izražen kot $\mathsf{R}w'$.

⚠️ Dve stvari, ki ju je treba imeti prav

Predznaki v $[t_\times]$. Vrstice so $[0, -t_3, t_2]$, $[t_3, 0, -t_1]$, $[-t_2, t_1, 0]$ — ni preprosto zrcaljenje, ampak protisimetrična matrika.
Smer. $\mathsf{E}p'$ (piksel iz druge slike) da premico v prvi sliki. Naloga 14 sprašuje ravno to smer.

Iz $au + bv + c = 0$ dobimo obliko, kot jo pričakuje izpit:

Enačba premice v obliki v = k·u + n

$$v = -\frac{a}{b}u - \frac{c}{b}$$

B. Neumerjene (nekalibrirane) razmere naloga 15

Notranji parametri obeh kamer niso poznani. Velja:

na listu $$p^T \mathsf{F}\, p' = 0$$

Matrika $\mathsf{F}$ je temeljna matrika (fundamental matrix), velikosti $3\times3$:

na listu $$\mathsf{F} = \mathsf{K}^{-T}\mathsf{E}\,\mathsf{K}'^{-1}$$

kjer sta matriki $\mathsf{K}$ in $\mathsf{K}'$ matriki notranjih parametrov oz. kalibracijski matriki kamer. Izraz $\mathsf{F}p'$ prav tako določa epipolarno premico $l$ (izraz $\mathsf{F}p$ pa premico $l'$).

1. Umerjanje oz. kalibracija

Postopek določitve matrike $\mathsf{F}$ imenujemo umerjanje oz. kalibracija. Za določitev matrike $\mathsf{F}$ moramo določiti korespondenčne točke — par ujemajočih se točk $(p_i, p'_i)$, kjer je $p_i$ točka iz prve slike, $p'_i$ pa pripadajoča točka iz druge slike.

2. Algoritem osmih točk

$F_{33}$ postavimo na 1 (matrika je določena do skalarja natančno).
Izbrati je treba osem korespondenčnih točk (parov!).
Rešiti moramo nehomogen sistem linearnih enačb.

Za vsak par dobimo eno vrstico oblike:

na listu

Vrstica sistema za en korespondenčni par

$$\big[\, u_i u'_i \;\; u_i v'_i \;\; u_i \;\; v_i u'_i \;\; v_i v'_i \;\; v_i \;\; u'_i \;\; v'_i \,\big] \cdot [F_{11}, F_{12}, F_{13}, F_{21}, F_{22}, F_{23}, F_{31}, F_{32}]^T = -1$$

Če izberemo $n > 8$ korespondenčnih točk, lahko matriko $\mathsf{F}$ ocenimo z uporabo linearne metode najmanjših kvadratov, kjer minimiziramo izraz $\sum_{i=1}^{n}\left(p_i^T \mathsf{F} p'_i\right)^2$.

Normalizacija

Raziskave so pokazale, da dobimo boljše rezultate, če algoritem normaliziramo:

Podatke (točke) v obeh slikah premaknemo tako, da je center podatkov v koordinatnem izhodišču.
Podatke nato še skaliramo tako, da je povprečna razdalja do koordinatnega izhodišča enaka $\sqrt{2}$ piksla.

⚠️ Vrstni red je bistven

Najprej odštej povprečje, šele nato pomnoži s skalirnim faktorjem: $u = (u_{\text{orig}} - \bar{u}) \cdot s$. Če bi najprej skaliral, dobiš popolnoma drugo vrstico — in prav ta odgovor je med ponujenimi na izpitu.

Algoritem daje povprečne rezultate — boljši so robustni postopki kalibracije: npr. metoda M-cenilk, metoda RANSAC, metoda LMedS (najmanjša mediana kvadratov).

3. Kako določiti korespondenčne točke?

Pare korespondenčnih točk lahko izberemo:

ročno — ročno določimo položaje točk na slikah;
avtomatsko — v slikah iščemo določene karakteristike (npr. oglišča objektov).

Paziti moramo, da so korespondenčne točke izbrane oz. razpršene po vsej sliki (da ne ležijo preveč skupaj) — sicer postane umerjanje nestabilno.

Originalne prosojnice (str. 77–80)

Trije pogledi razumevanje

Sceno opazujemo s tremi perspektivnimi kamerami z optičnimi centri $O_1$, $O_2$, $O_3$. Opazovana točka $P$ ima projekcije $p_1$, $p_2$, $p_3$ na virtualnih slikovnih ravninah $\Pi_1$, $\Pi_2$, $\Pi_3$.

Vsak par kamer definira svojo epipolarno omejitev — obravnavamo torej 3 neodvisne enačbe:

Epipolarne omejitve za tri poglede

$$p_1^T \mathsf{E}_{12}\, p_2 = 0 \qquad p_2^T \mathsf{E}_{23}\, p_3 = 0 \qquad p_3^T \mathsf{E}_{31}\, p_1 = 0$$

$\mathsf{E}_{ij}$ je osnovna matrika, prirejena slikama $i$ in $j$. Podane enačbe veljajo za umerjene razmere; pri neumerjenih bi namesto osnovne matrike uporabili temeljno matriko ($\mathsf{F}_{ij}$).

Določanje položaja točk v 3D naloga 16

V praksi se žarki $R_1$, $R_2$ in $R_3$, ki so prirejeni slikovnim točkam $p_1$, $p_2$ in $p_3$, ne sekajo! Enako situacijo imamo že pri dveh pogledih.

1. Postopek za 2 kameri

Točki $P_1$ in $P_2$ sta približka za pravi položaj opazovane točke $P$.
Poiščemo najkrajšo razdaljo med žarkoma $R_1$ in $R_2$ — tj. daljico, ki je pravokotna na oba žarka.
Položaj točke $P$ določimo na sredini te najkrajše razdalje!

2. Postopek za 3 kamere

Točke $P_1$, $P_2$ in $P_3$ so približki za pravi položaj opazovane točke $P$.
Za vsak par kamer uporabimo postopek za 2 kameri — dobimo 3 približne položaje točke $P$; te 3 točke določajo trikotnik.
Položaj točke $P$ določimo kot težišče tega trikotnika!

⚠️ »Postopek z geometrijsko interpretacijo«

Ta fraza v nalogi 16 pomeni težišče trikotnika. Če naloga pove, da je ena rekonstrukcija »2× bolj natančna«, jo v povprečju štej dvakrat — torej deli s 4, ne s 3. Odgovor, ki ustreza navadnemu povprečju treh točk, je namenoma med ponujenimi.

Originalne prosojnice (str. 81–83)

Stereo vid ključno

A. Rekonstrukcija

Imejmo dve ujemajoči se slikovni točki $p$ in $p'$ opazovane točke $P$ v prostoru.

Teoretično: položaj točke $P$ določimo kot presečišče žarka $R = Op$ in $R' = O'p'$.
Praksa: žarka $R$ in $R'$ se nikoli ne sekata — vzrok so napake pri umerjanju in lokaliziranju značilnic na slikah.

1. rešitev: točko $P$ postavimo na sredino daljice z najkrajšo razdaljo med žarkoma.

2. rešitev: izraz $p = \frac{1}{z}\mathsf{M}P$ lahko zapišemo kot $p \times \mathsf{M}P = 0$ in na tej osnovi dobimo sistem:

Predeterminiran sistem

$$\begin{bmatrix} [p_\times]\mathsf{M} \\ [p'_\times]\mathsf{M}' \end{bmatrix} P = 0_{4\times1}$$

Rešiti moramo torej predeterminiran sistem 4 neodvisnih linearnih enačb.

B. Primer paralelnih kamer naloga 17

Poseben primer stereo konfiguracije:

fizikalni mrežnici (ravnini) sta horizontalno odmaknjeni in koplanarni;
kameri imata identično goriščno razdaljo $f$.

Vrednost razlike med točkama — dispariteta $d$:

na listu

Dispariteta in globina

$$d = v' - v \qquad\qquad z = \frac{fB}{d}$$

Pozor: $u$ in $u'$ sta enaka! Absolutna oddaljenost $z$ točke $P$ je odvisna od razlike $d$; $B$ je osnovnica — razdalja med optičnima centroma $OO'$.

Epipolarne premice sovpadajo s horizontalnimi linijami slike (tj. vrsticami) in so tudi vzporedne z osnovnico; epipola sta v neskončnosti.

⚠️ Enote — brez tega je odgovor 1400× narobe

Dispariteta $d$ je najprej v pikslih. Formula $z = fB/d$ zahteva, da je $d$ v istih enotah kot $f$ in $B$ (metrih). Zato: $d_{\text{[m]}} = d_{\text{[px]}} \,/\, \text{prostorska ločljivost [px/m]}$. Šele nato v formulo.

C. Rektifikacija oz. izravnavanje slik

Rektifikacija je proces, ki originalni sliki obeh kamer (lahko poljubno postavljeni!) zamenja z ekvivalentnima slikama, ki imata skupno slikovno ravnino, le-ta pa je paralelna z osnovnico, ki povezuje optična centra.

S tem postopkom pridemo na umeten način do situacije paralelnih kamer — velja vse, kar smo povedali pri paralelnih kamerah (tudi enačbe!).

na listu

Rekonstrukcija po rektificiranju (v k. s. 1. kamere)

$$P = zp = -\frac{fB}{d}p, \qquad p = [u, v, 1]$$

Rektifikacija je preslikava, ki ima 2 parametra:

oddaljenost nove slikovne ravnine od osnovnice;
smer normale — izbira smeri normale te nove rektificirane ravnine na ravnini, ki je pravokotna na osnovnico. Običajno izberemo ravnino, ki je vzporedna premici, kjer se sekata originalni sliki.

D. Ujemanje stereo slik (paralelne kamere) naloga 18

Gre za reševanje problema: kje se nahaja določen del prve (leve) slike na drugi (desni) sliki.

Možna pristopa:

Iskanje na osnovi intenzitet sivin — primerjamo intenzitetne profile vrstic leve in desne slike ter poiščemo najboljšo razliko (premik) $d$.
Iskanje ujemanja na osnovi značilnic — najprej v obeh slikah poiščemo značilnice, zatem pa iščemo ujemanje med temi značilnicami. Največkrat uporabljene značilnice: robovi, oglišča, linije (daljice), krivuljni segmenti, krogi/elipse, regije.

Omejitve, ki jih upoštevamo pri iskanju ujemanja

Omejitev	Pomen
Podobnost (kompatibilnost)	podobne vrednosti sivin oz. značilnic v obeh slikah
Enoličnost	en piksel oz. značilnica se ujema z enim pikslom oz. značilnico z druge slike
Zveznost	vrednost razlike (disparity) se skozi sliko spreminja gladko
Urejanje	če sta ujemajoča se para $(m, m')$ in $(n, n')$ in je $m$ levo od $n$, potem bo tudi $m'$ levo od $n'$
Epipolarna omejitev	ujemajoča se točka lahko leži le na pripadajoči epipolarni premici — ta omejitev je najbolj zanesljiva!

Originalne prosojnice (str. 84–88)

Preveri se

1Osnovnica je 12 cm, goriščna razdalja 50 mm, dispariteta 17 pikslov, prostorska ločljivost 1400 px/m. Kolikšna je oddaljenost z?

Razlaga

Najprej enote: $B = 0{,}12$ m, $f = 0{,}05$ m. Dispariteta v metrih: $d = 17 / 1400 = 0{,}012143$ m.

$z = \dfrac{fB}{d} = \dfrac{0{,}05 \cdot 0{,}12}{0{,}012143} = \dfrac{0{,}006}{0{,}012143} = \mathbf{0{,}49}$ m. Odgovor a) je past za tiste, ki pozabijo pretvoriti disparieto iz pikslov.

2Pri algoritmu osmih točk je leva točka (272, 230), povprečje leve slike (558, 163) in skalirni faktor 0,52. Kolikšen je normiran u?

Razlaga

Normalizacija ima dva koraka v določenem vrstnem redu: (1) premik v težišče, (2) skaliranje.

$u = (272 - 558) \cdot 0{,}52 = -286 \cdot 0{,}52 = \mathbf{-148{,}72}$. Odgovor a) je past za obrnjen vrstni red, odgovor d) za pozabljeno skaliranje.

3Tri rekonstruirane točke: (488, 535, 104) — 2× natančnejša, (414, 508, 174) in (446, 567, 170). Kolikšna je rekonstrukcija?

Razlaga

»Postopek z geometrijsko interpretacijo« = težišče. Prva točka šteje dvakrat, zato delimo s 4:

$x = (2\cdot488 + 414 + 446)/4 = 1836/4 = 459$
$y = (2\cdot535 + 508 + 567)/4 = 2145/4 = 536{,}25 \to 536$
$z = (2\cdot104 + 174 + 170)/4 = 552/4 = 138$

Odgovor b) je natanko tisto, kar dobiš, če uteži ne upoštevaš.