Zpracování obrazu pomocí minimalizace energie

Note	Variační filtrování. Aktivní křivky a plochy (geodetický model, Chan-Vese model). Minimalizace pomocí grafových řezů. Variační optický tok. PA166

Tip	Doporučuju kouknout na shrnutí v zápiscích z předmětu PA166 od xrosecky

Gradient $\nabla$: Vektorové pole ve směru největšího nárůstu.

Standardně ho spočítáme jako derivaci obrazu podle x a y. V praxi ale používáme aproximaci derivace podle Taylorova rozvoje.
Aproximace derivace: Taylorův polynom vypadá takto: $f (x + h) = f (x) + h f^{'} (x) + \frac{h ^{2}}{2 !} f^{''} (x) + \dots + \frac{h ^{n}}{n !} f^{(n)} (x) + O (h^{n + 1})$ .

Z něho můžeme odvodit rovnici pro první derivaci (v našem případě ji nazýváme dopředná diference):

$f (x + h) \approx f (x) + h f^{'} (x) f^{'} (x) \approx \frac{f ( x + h ) - f ( x )}{h}$

Tu můžeme dále zpřesnit, pokud si vypíšeme taylorův rozvoj až do druhé derivace včetně (tím získáme centrální diferenci):

$h_{1} = 1, h_{2} = - 1 f (x + h_{1}) - f (x + h_{2}) f (x + 1) - f (x - 1) \approx f (x) + h f^{'} (x) + \frac{h ^{2}}{2 !} f^{''} (x) - f (x) + h f^{'} (x) - \frac{h ^{2}}{2 !} f^{''} (x) f (x + 1) - f (x - 1) \approx 2 h f^{'} (x) f^{'} (x) \approx \frac{f ( x + 1 ) - f ( x - 1 )}{2 h}$

Podobným stylem získáme i druhou derivaci

Variační filtrování

Variační filtrování neřeší lokálně jednotlivé pixely, ale snaží se minimalizovat enetgii celého obrázku.

Typickým předpisem takovéhle funkce je

E_{f} (u) = \int_{Ω} (similarity (u - f)^{2} + α smoothness Ψ (∣\nabla u ∣^{2})) d x

Chceme, aby byl obrázek co nejpodobnější původnímu (data/similarity term), ale zároveň co nejvíc vyhlazený (smoothness term/regularizer/penaliser). Poměr těchto dvou členů určuje parametr $α$ . Regularizer $Ψ$ určuje “metodu” vyhlazení:

Tikhonov (linear) — identita

$Ψ (∣ \nabla u ∣^{2}) = ∣ \nabla u ∣^{2}$

Charbonnier

$Ψ (∣ \nabla u ∣^{2}) = 2 λ^{2} 1 + ∣ \nabla u ∣^{2} / λ^{2} - 2 λ^{2}$

Total Variation

$Ψ (∣ \nabla u ∣^{2}) = 2 ∣ \nabla u ∣^{2} = 2 ∣ \nabla u ∣$

Tuto funkci můžeme minimalizovat dvěma způsoby:

Přímé řešení (lineární funkce)

Provedeme diskretizaci a poté parciálně zderivujeme pro jednotlivé pixely. Tím dostáváme sadu lineárních funkcí položených nule. Tyto poté položíme do matice, kterou řešíme. Matice má hodnoty pouze kolem diagonály, což znamená, že je velmi rychle řešitelná např. pomocí Thomas method.

Pokud je obraz 2D, bereme všechny pixely jako dlouhou 1D posloupnost a řešíme obdobně.

Matice je ale obrovská, proto můžeme využít např. Gauss-Seidel metodu, s pomocí které matici řešíme iterativně po řádcích.

Nelineární řešení

Použijeme Variační kalkulus, který dokáže minimalizovat Funkcionály

Funkcionál: Bere na vstupu funkci a přiřazuje jí nějakou hodnotu $u (x) \Rightarrow R$ .

Pro řešení můžeme nyní využít Euler-Lagrangeovy rovnice. Pro funkcionál $E_{f} (u) = \int_{Ω} ((u - f)^{2} + α Ψ (∣\nabla u ∣^{2})) d x d y$ získáme předpis pro minimalizaci:

0 = u - f - α div (Ψ^{'} (∣ \nabla u ∣^{2}) \nabla u)

Nyní můžeme hezky vidět vztah k difuznímu filtrování (otázka PGV10):

Variační metoda

$\frac{u - f}{α} = div (Ψ^{'} (∣ \nabla u ∣^{2}) \nabla u)$

Difuzní filtrování

$\partial_{t} u = div (Ψ^{'} (∣ \nabla u ∣^{2}) \nabla u)$

Přičemž vidíme, že

Tikhonov regulariser ~ Linear diffusivity
- $Ψ (∣ \nabla u ∣^{2}) = ∣ \nabla u ∣^{2}$
- $Ψ^{'} (∣ \nabla u ∣^{2}) = 1$
Charbonnier regulariser ~ Charbonnier diffusivity
- $Ψ (∣ \nabla u ∣^{2}) = 2 λ^{2} 1 + ∣ \nabla u ∣^{2} / λ^{2} - 2 λ^{2}$
- $Ψ^{'} (∣ \nabla u ∣^{2}) = \frac{1}{1 + ∣ \nabla u ∣ ^{2} / λ ^{2}}$
Total Variation regulariser ~ Total Variation diffusivity s difusivitou $\frac{1}{∣ \nabla u ∣}$
- $Ψ (∣ \nabla u ∣^{2}) = 2 ∣ \nabla u ∣$
- $Ψ^{'} (∣ \nabla u ∣^{2}) = \frac{1}{∣ \nabla u ∣}$

Aktivní křivky a plochy

Segmentace: Chceme rozdělit obrázek podle něčeho (region based, edge based, texture, …)
Segmentace založená na energii: Hledáme konturu s minimální energií. Závisí na volbě iniciální křivky - hledá pouze lokální minimum.

Hadi

Působí dvě energie:

Vnitřní - tvar a plynulost křivky
Vnější - omezení z obrázku

Kontura zadaná, jako parametrická křivka $p (s) : [0, 1] \to R p (s) = (x (s), y (s))^{T}$ . Podobně, jako u variačního filtrování, definujeme funkcionál energie, který se snažíme minimalizovat:

E (p) = \int_{0}^{1} E_{in t} (p (s)) + E_{e x t} (p (s)) d s

Kde $E_{in t}$ je vnitřní energie, kde $α$ a $β$ jsou váhy pro délku ( $α$ ) a křivost ( $β$ ) křivky:

E_{in t} (p (s)) = α (s) ∣ p^{'} (s) ∣^{2} + β (s) ∣ p^{''} (s) ∣^{2}

A $E_{e x t}$ je vnější energie, kde $P$ je potenciální funkce:

E_{e x t} (p (s)) = P (p (s))

Potenciál

Potenciál určuje vztah křivky k obrázku. Může být definován různými způsoby:

Hrany - $P (x, y) = - ∣ \nabla f (x, y) ∣^{2}$
Hrany po rozmazání - $P (x, y) = - ∣ \nabla (G_{σ} (x, y) * f (x, y)) ∣^{2}$
Linie - $P (x, y) = - f (x, y)$
Linie po rozmazání - $P (x, y) = - G_{σ} (x, y) * f (x, y)$

Minimalizaci funkcionálu chceme opět udělat Euler-Lagraneovou rovnicí, tedy:

α p^{''} (s) + β p^{'''} (s) - \nabla P = 0, kde p (0), p^{'} (0), p (1), p^{'} (1) jsou zadan \overset{e}{ˊ} .

Na derivace můžeme použít finite differences a přepíšeme výsledek do matice $A X = F_{e x t}$ . Blbý ale je, že F_{ext} závisí na p a p závisí na F_{ext}. Proto se to řeší iterativně $\frac{\partial p}{\partial t} = F_{in t} (p) + F_{e x t} (p) p (s, 0) = p_{0} (s)$

Problémy

Reparametrizace
- Body mají tendenci se slévat do míst s nízkou potenciální energií
- Musíme jednou za čas rozmístit body pravidelně podél vzniklé křivky
Normalizace (Diskretizace času)
- Velikost gradientu není ničím omezena a může nám “vystřelit” body úplně do kša
- Místo klasického gradientu vezmeme gradient normalizovaný, tedy jen směr
Diskretizace prostoru
- Potenciální funkce je spočítaná pouze v diskrétních bodech, ale křivka může procházet i mimo tyto body
- Na dopočítání použijeme například bilineární interpolaci
Problémy předchozí detekce hran
- Výsledkem detekce hran je často binární obrázek, kde by ale křivka nevěděla, kam se pohybovat - kuličky jsou na rovině
- Můžeme obrázek Gaussovsky rozmazat, nebo dopočítat vzdálenost všech bodů od bodů hran (distance function from the edge pixels)
Balonování
- Kontury mají tendenci se slévat do středu do jednoho bodu, kde zaniknou
- Často chceme detekovat něco, kde začneme uvnitř
- K externím silám přidáme tzv. balonovou sílu ve směru normály křivky
  
  $F_{e x t} = k_{1} n (s) - k \frac{\nabla P}{∣\nabla P ∣}$
- Parametr $k_1$ ovlivňuje, jestli se křivka “nafukuje”, nebo “vyfukuje”, můžeme měnit během iterování
GVF Snakes
Kontury mají problém opsat “tvar rohlíku” a nic je nenutí dostávat se do úzkých prostor
Převedeme externí síly na nové pole sil, kterému říkáme Gradient Vector Flow
Chceme v podstatě přidat síly tam, kde nejsou hrany, aby celý prostor k hranám směřoval

Geodetické aktivní křivky

Hloupé na hadech (to, co jsem popisoval doteď) je, že závisí na parametrizaci (rozložení bodů na křivce). GAC naopak na parametrizaci nezávisí.

Pro křivku minimalizujeme funkcionál (Chceme co nejmenší délku křivky && co nejnižší celkový gradient):

E_{G A C} (C) = \int_{0}^{1} g (Vyhlazen \overset{y}{ˊ} obr \overset{a}{ˊ} zek ∣ \nabla G_{σ} * I (C (q))∣) D \overset{e}{ˊ} lka k \overset{r}{ˇ} ivky ∣ C^{'} (q)∣ d q

Funkce $g$ snižuje vliv délky na energii, pokud leží v místech s vysokým gradientem, protože je nepřímo úměrná rozmazanému gradientu:

g (∣ \nabla G_{σ} * I (x, y)∣) = \frac{1}{1 + ∣ \nabla G _{σ} * I ( x , y )∣}

Chan-Vese model

Do teď jsme neřešili, co je uvnitř kontur (homogenita), jen co je přímo pod nimi. Chan-Vese model se snaží najít konturu, která rozdělí obrázek na dvě části s různými intenzitami.

E_{C V} (K \overset{r}{ˇ} ivka C, Odhad pop \overset{r}{ˇ} ed \overset{ı}{ˊ} c_{1}, Odhad pozad \overset{ı}{ˊ} c_{2}) = D \overset{e}{ˊ} lka k \overset{r}{ˇ} ivky μL (C) + Odli \overset{s}{ˇ} nost pop \overset{r}{ˇ} ed \overset{ı}{ˊ} od odhadu λ_{1} \int_{Ω_{1}} (f (x) - c_{1})^{2} d x + Odli \overset{s}{ˇ} nost pozad \overset{ı}{ˊ} od odhadu λ_{2} \int_{Ω_{2}} (f (x) - c_{2})^{2} d x

Regularity term - délka dělící křivky
Data term (2x) - rozdíl částí (fg,bg; $Ω_{1}, Ω_{2}$ ) od konstantního odhadu $c_{1}, c_{2}$
Parametry $μ, λ_{1}, λ_{2}$ určují vyhlazení, variabilitu pozadí a popředí respectively
Pro danou křivku C jsou optimální $c_{1}, c_{2}$ s průměrnou hodnotou

Abychom se zbavili integrálů přes část oblasti, můžeme použít Harveside funkci, která vrací 0 pro nulu a 1 jinak. Tím dostaneme:

E_{C V} (C, c_{1}, c_{2}) = μ \int_{Ω} ∣ \nabla H (u (x))∣ d x + λ_{1} \int_{Ω} (f (x) - c_{1})^{2} H (u (x)) d x + λ_{2} \int_{Ω} (f (x) - c_{2})^{2} (1 - H (u (x))) d x D \overset{e}{ˊ} lka k \overset{r}{ˇ} ivky Odli \overset{s}{ˇ} nost pop \overset{r}{ˇ} ed \overset{ı}{ˊ} od odhadu Odli \overset{s}{ˇ} nost pozad \overset{ı}{ˊ} od odhadu

Diskretizujeme a řešíme.

Minimalizace pomocí grafových řezů

Rozdělení metodou minimálního řezu využívá algoritmu pro hledání minimálního řezu v grafech. Uvažme graf, kde každý pixel je jeden vrchol a pro všechny pixely vytvoříme hrany ze zdroje (s) a spotřebiče (t) a hrany mezi sousedy.

Riemannovy metrické systémy

Normálně, když počítáme délku mezi dvěma body, počítáme ji, jako $d = u^{T} \cdot u$ . Můžeme ale přidat tzv. metrický tensor $M$ , který může tuto délku upravit v závislosti na směru $d = u^{T} \cdot M \cdot u$ . Díky tomu potom můžeme měřit nejen euklidovskou vzdálenost, ale třeba:

Euklidovskou vzdálenost - $M = I$ (identita)
Geodetickou vzdálenost - $M = diag (g (∣ \nabla I (\cdot)∣))$
Anizotropní vzdálenost - $M = g (∣ \nabla I (\cdot)∣) \cdot E + (1 - g (∣ \nabla I (\cdot)∣)) \cdot u \cdot u^{T}$ (kde $u = \frac{\nabla I}{∣ \nabla I ∣}$ jednotkový vektor ve směru gradientu a $E$ je identita)

Pro aproximaxi vah hran v našem grafu můžeme použít Riemannovu metriku:

w_{k}^{R} = w_{k}^{ϵ} \cdot \frac{det M}{( u _{k}^{T} \cdot M \cdot u _{k} ) ^{p}}

Geodetická segmentace

Můžeme rozdělit obrázek na dvě části pomocí minimálního řezu na dvě části podle geodetické vzdálenosti.

t-linky (hrany do s nebo do t) - nastavíme váhy na 0 vyjma pixelů s omezením (víme, že jsou popředí, nebo pozadí), které nastavíme na nekonečno (nebo velkou konstantu), čímž zabráníme výběr do minimálního řezu
n-linky (mezi sousedními pixely) - podle Riemannovy metriky

Chan-Vese pomocí minimálního řezu

Můžeme rozdělit obrázek na dvě části, přičemž o některých pixelech víme, jestli patří do popředí, nebo do pozadí. Podobně, jako u Chan-Vese křivkami máme odhad $c_{1}, c_{2}$ pro popředí a pozadí. Nastavme tedy váhy:

t-linky - $w_{s i} = λ_{2} (f (i) - c_{2})^{2}, w_{i t} = λ_{1} (f (i) - c_{1})^{2}$
n-linky - podle Riemannovy metriky

Bohužel $w_{s i}, w_{i t}$ jsou závislé na $c_{1}, c_{2}$ . Typicky řešíme tak, že si tipneme, provedeme iteraci, aktualizujeme a jedem znovu

Variační optický tok

Pro sekvenci obrázků $f (x, y, t)$ chceme získat vektor posunutí $(u (x, y, t), v (x, y, t))^{T}$ každého místa obrázku.

Máme 2 předpoklady, které platí pro všechny metody: - Zachování jasu (mezi snímky se nám nemění jas obrázku) = BCA - $f (x + u, y + v, t + 1) = f (x, y, t)$ (posunutý pixel se rovná neposunutému) - Malé změny (objekty se posouvají jen o několik málo (třeba 5) pixelů) - Abychom mohli provést linearizaci Taylorovým rozvojem

Z rovnice pro BCA můžeme linearizací dostat

0 = f (x + u, y + v, t + 1) - f (x, y, t) \approx f_{x} (x, y, t) u + f_{y} (x, y, t) v + f_{t} (x, y, t)

Tím dostáváme nejdůležitější rovnici linearised optical flow constraint (OFC) $f_{x} u + f_{y} v + f_{t} = 0$ ( $\nabla f \cdot (u, v) + f_{t} = 0$ )

Problém Apertury = OFC ukazuje jen tok rovnoběžný s gradientem (protože jinak to není vidět)

pgv09 nonuniqueness

Taky protože $f_{x} u + f_{y} v + f_{t} = 0 \sim \nabla f \cdot (u, v) + f_{t} = 0$ , tedy máme projekci reálného směru na gradient
→ Nonuniqueness = Můžeme libovolně přidat část toku kolmou na gradient, aniž bychom změnili výsledek

Lukas a Kanade (Lokální metoda)

Přidává 3. předpoklad:

Zachování jasu
Malé změny
Konstantnost toku v okolí $B_{ρ}$ každého bodu

Chceme minimalizovat následující lokální energii (integrál přes okolí)

E (u, v) = \frac{1}{2} \int_{B_{ρ} (x_{0}, y_{0})} (f_{x} u + f_{y} v + f_{t})^{2} d x d y

Parciálně zderivujeme a převedeme na matice

0 = \frac{\partial E}{\partial u} 0 = \frac{\partial E}{\partial v} = \int_{B_{ρ}} f_{x} (f_{x} u + f_{y} v + f_{t}) d x d y = 0 = \int_{B_{ρ}} f_{y} (f_{x} u + f_{y} v + f_{t}) d x d y = 0 (\int_{B_{ρ}} f_{x}^{2} d x d y \int_{B_{ρ}} f_{x} f_{y} d x d y \int_{B_{ρ}} f_{x} f_{y} d x d y \int_{B_{ρ}} f_{y}^{2} d x d y) (u v) = (- \int_{B_{ρ}} f_{x} f_{t} d x d y - \int_{B_{ρ}} f_{y} f_{t} d x d y)

Můžeme nahradit integrály za Gaussovské rozmazání, čímž dostaneme "plynulejší okolí"

(G_{σ} * (f_{x}^{2}) G_{σ} * (f_{x} f_{y}) G_{σ} * (f_{x} f_{y}) G_{σ} * (f_{y}^{2})) (u v) = (- G_{σ} * (f_{x} f_{t}) - G_{σ} * (f_{y} f_{t}))

Snadno vyřešíme Cramerovým pravidlem

Výhody

Jednoduché, rychlé
Stačí nám 2 snímky

Nevýhody

Problémové situace, kde neplatí podmínka konstantnosti - rotace, protijedoucí auta, …
Nepočítá husté pole toků (jen tam, kde víme gradient)

Horn-Schunck (Globální metoda)

Pouze dva přepoklady:

Zachování jasu - $f_{x} u + f_{y} v + f_{t} = 0$
Malé změny (Gradient vektorového pole je malý) - $\int_{Ω} (∣ \nabla u ∣^{2} + ∣ \nabla v ∣^{2}) d x d y$ je malé

Kombinací dostáváme funkcionál energie optického toku

E_{H S} (u, v) = \int_{Ω} ((f_{x} u + f_{y} v + f_{t})^{2} + α (∣ \nabla u ∣^{2} + ∣ \nabla v ∣^{2})) d x d y

Tento funkcionál minimalizujeme na jediné globální řešení

Výhody

Jsme schopni řídit smoothness pomocí $α$
Produkuje dense flow fields

Nevýhody

Stále musíme splňovat předpoklad malých změn
Celkem pomalé a drahé