Zpracování rastrového obrazu

Note	Bodové transformace. Histogram, vyrovnání histogramu, analýza histogramu. Lineární a nelineární filtry. Detekce hran. Fourierova transformace. Vzorkovací teorém, převzorkování, geometrické transformace. Vlnková transformace. Houghova/Radonova transformace. PB130/PV131

Rastr / bitmapa

Obraz reprezentovaný pomocí 2D pole pixelů. Každý pixel obsahuje jednu (pokud je obraz černobílý) nebo více (typicky RGB nebo CMYK) intenzit. Intenzity jsou zakódovány na bity. [3]

Je to 2D mapa bitů… bitmapa. Get it?

Zpracování obrazu / digital image processing

Oblast informatiky zabývající se manipulací s obrazy pomocí počítače. Obsahuje třeba: [4]

zpracování raw dat ze senzorů ve foťácích,
odstranění šumu,
zvýraznění hran,
zvýšení kontrastu,
detekci tváří,
rozpoznávání objektů,
rozpoznávání textu — optical character recognition (OCR).

Klasifikace transformací

Neměnící geometrii obrazu
- Bodové
- Lokální
- Globální
Geometrické

Bodové transformace

Transformace hodnot pixelů nezávisle na jejich okolí. Nemění velikost obrazu.

Homogenní

Bodové transformace, které nezávisí na pozici pixelu v obraze. Je definována pomocí převodní funkce $I^{'} (u, v) \leftarrow f (I (u, v))$ . Patří sem třeba:

úprava jasu,
úprava kontrastu,
hue, saturation, atd.,
gama korekce,
globální prahování.

Lineární transformace

Převodní funkce je lineární, definována, jako $f (a) = ka + q$ .

Identita: $k = 1, q = 0$
Inverze intenzit (negativ): $k = - 1, q = a_{ma x}$
Zvýšení jasu: $k = 1, q > 0$
Snížení jasu: $k = 1, q < 0$
Zvýšení kontrastu: $k > 1, q = 0$
Snížení kontrastu: $0 < k < 1, q = 0$
Lineární roztažení: viz dále
(Percentilové roztažení: viz dále)

Negativ

Inverze hodnot pixelů. Nejvyšší hodnota se změní na nejnižší a naopak.

Pokud maximální intenzita je 255 pak negativ je definován jako:

$f (x) = 255 - x$

Lineární roztažení

Přemapování rozsahu intenzit $(a_{low}, a_{high})$ na rozsah $(a_{min}, a_{max})$ pomocí lineární interpolace. Často ke zvýraznění kontrastu.

$f (x) = \frac{a _{max} - a _{min}}{a _{high} - a _{low}} \cdot (x - a_{min}) + a_{min}$

kde $a_{low}$ je nejnižší hodnota a $a_{high}$ nejvyšší hodnota v obraze. Obvykle $a_{min} = 0$ a $a_{max} = 255$ .

Alternativně lze použít percentilové roztažení, které převede $p$ procent nejnižších a nejvyšších hodnot na $a_{min}$ a $a_{max}$ (tedy "uřízne" extrémy). není striktně řečeno lineární.

Nelineární transformace

Převod nelze vyjádřit v lineárním tvaru

Gama korekce

Nelineární bodová transformace kompenzující vlastnosti lidského oka pro lepší využití bitové hloubky.

Vstupní obraz je normalizován na rozsah $(0, 1)$ .
Každá hodnota $x$ je transformována typicky pomocí $x^{γ}$ .
Výsledný obraz je přeškálován na původní rozsah.

Kvantizace

Nelineární bodová transformace, která snižuje bitovou hloubku obrazu. Výsledkem je obraz s menším počtem barev.

Může vypadat cool. Viz toon shading.

Prahování / thresholding

Nelineární bodová transformace, která rozdělí obraz na dvě skupiny podle intenzity. Výsledkem je binární obraz.

f (x) = {01 pokud x < T pokud x \geq T

kde $T$ je práh. Pokud je $T$ konstanta, pak se jedná o globální prahování.

Important

Prahování se pořádně věnuje otázka Analýza rastrového obrazu.

Paleta

Můžeme použít funkci či vyhledávácí tabulku pro přemapování existujících hodnot v obrazu na jiné (viz barevné škály u vizualizací).

Nehomogenní

Bodové transformace, které závisí na pozici pixelu v obraze. Je definována pomocí převodní charakteristiky $I^{'} (u, v) \leftarrow f (I (u, v), u, v)$ . Patří sem třeba:

korekce nerovnoměrného osvětlení,
vignette,
přechodové filtry.

Histogramy

Histogram kvantifikuje množství a frekvenci barev obsažených v obraze. Ve statické terminologii je to aproximace hustoty pravděpodobnosti.

Hodnota histogramu $H$ v indexu $i$ odpovídá počtu pixelů v obraze s intenzitou $i$ .
Šedotónní obraz má jeden histogram. RGB obraz má tři.

Kumulativní histogram

Kumulativní histogram $H$ bbsahuje množství pixelů s intenzitou menší nebo rovnou než $i$ . Ve statické terminologii je to aproximace distribuční funkce.

H [i] = j = 0 \sum i H [j]

Vyrovnání histogramu / histogram equalization

Změna obrazu tak, aby jeho kumulativní histogram měl konkrétní tvar, obvykle aby byl lineární. [20]

Typicky k tomu využíváme funkci $f (x) = H [x] \cdot \frac{a _{max}}{w \cdot h}$ , kde $cumhist$ je kumulativní histogram pro barvu v bodě x, $a_{max}$ je maximální intenzita a $w \cdot h$ je velikost obrazu.

Před vyrovnáním histogramu

szp09 histogram eq before 01 szp09 histogram eq before 02

Po vyrovnání histogramu

szp09 histogram eq after 01 szp09 histogram eq after 02

Note	Původní fotku vyfotil Phillip Capper.

Analýza histogramu

Z histogramu lze vysledovat řadu věcí jak manuálně tak automaticky. Často se proto používá jako mezikrok v jiných algoritmech. Lze z něj například zjistit: [19] [21]

průměrný jas,
kontrast,
vztah mezi mediánem a střední hodnotou,
přepaly a podexponované oblasti,
šikmost / skewness.

Konvoluční filtry

Filtr

Filtr je termín ze zpracování signálů (kterýmžto obraz z jisté perspektivy je). Je to zařízení, postup, či transformace, která ze signálu odstraňuje nechtěnné informace. [5]

Šum / noise

Šum je informace, která v obrazu vznikla kvůli nedokonalosti snímače, přenosu, uložení dat, atd. Ač někdy může vypadat docela cool, obvykle je to nechtěná informace. Podle frekvenční charakteristiky se dělí na:

bílý šum: má stejnou energii ve všech frekvencích; je to jen matematická abstrakce,
Poissonův šum / photon noise: vzniká při náhodném procesu, jako je například dopad světla na snímač,
Aditivní: přidává se k signálu; $g = f + n$ , kde $f$ je originální funkce signálu a $n$ je šum,
Impulzní: nahrazuje některé hodnoty signálu jinými hodnotami; patří sem například sůl a pepř / salt and pepper noise.

Konvoluce

Matematická operace, která vezme dvě funkce $f$ a $g$ a produkuje třetí funkci $h = f * g$ popisující, jak jedna funkce mění tvar té druhé. Je komutativní, takže je jedno, která je první a která je druhá. Ve spojité doméně je definována jako: [6]

(f * g) (t) = \int_{- \infty}^{\infty} \cdot f (τ) g (t - τ) d τ

Pokud jsou funkce $f$ a $g$ diskrétní a $g$ navíc je doména (množina povolených vstupů) $g$ konečná a je třeba ${- M, - M + 1, ..., M - 1, M}$ , pak se používá diskrétní konvoluce:

(f * g) [t] = m = - \infty \sum \infty f [m] \cdot g [t - m]

Obrazy však mají dvě dimenze, takže se používá dvourozměrná diskrétní konvoluce:

(f * g) [x, y] = m = - k \sum k n = - k \sum k f [x - m, x - n] \cdot g [m, n]

kde $h$ je kernel / konvoluční jádro dáno jako matice velikosti $(2 k + 1) \times (2 k + 1)$ .

Warning

Všimni si, že kvůli

f [x - m, x - n]

se jádro při aplikaci na obraz překlápí. Kdyby to bylo

f [x + m, x + n]

, tak jde o korelaci, ne o konvoluci.

Konvoluce má složitost $O (MN K L)$ , kde $M \times N$ je velikost obrazu a $K \times L$ je velikost jádra. Pro velká jádra se složitost blíží $O (M^{2} N^{2})$ .

Konvoluce je komutativní, asociativní, xy separabilní (lze ji rozdělit na dvě jednorozměrné konvoluce, pokud platí, že $H_{x, y} (i, j) = H_{x} (i) \cdot H_{y} (j)$ ), a lineární (tedy lze ji násobit skalárem a sčítat).

Okrajové hodnoty

Je důležité si uvědomit, že na okrajích obrazu nelze aplikovat konvoluci tak, jak je definována. Existuje několik způsobů, jak s tímto problémem pracovat:

Doplnění nulami: okraje se doplní nulami,
Doplnění nejbližší hodnotou: okraje se doplní hodnotou nejbližšího pixelu,
Doplnění zrcadlením: okraje se doplní hodnotami jako podle zrcadla,
Doplnění periodickým opakováním: okraje se doplní hodnotami z opačné strany obrazu.
Zmenšení okolí pro pixely u krajů obrazu: pixely mimo obraz se ignorují.

Lineární

Lineární filtr: Je takový filtr $Θ : I^{w \times h} \to I^{w \times h}$ , kde $I$ je množina povolených hodnot pixelů v obraze a $I^{w \times h}$ je množina všech obrazů s šířkou $w$ a výškou $h$ . Musí splňovat podmínky linearity:

$a \cdot Θ (I) Θ (I_{1} + I_{2}) = Θ (a \cdot I) = Θ (I_{1}) + Θ (I_{2})$

kde $I, I_{1}, I_{2}$ jsou obrazy a $a$ je skalární hodnota.
Posunutí: Jednoduchý lineární filtr, který posune obraz o nějaký vektor.

$000000001$
Box filtr / box blur: Rozmazání pomocí okolních pixelů.

$\frac{1}{9} \cdot 111111111$
Gaussian filtr / Gaussian blur: Rozmazání pomocí okolních pixelů s Gaussovským váhováním, kde $σ$ je parametr určující šířku Gaussova zvonu.
Rozdílové filtry: Filtry, které počítají rozdíly mezi okolními pixely. Často se využívají pro detekci hran (viz dále).

Nelineární

Nelineární filtry jsou takové filtry, které nejsou lineární. (Duh.) Tedy nesplňují podmínky linearity.

Detekce hran

Proces, kdy hledání hran v obraze. Hrana je křivka, podél níž pixely výrazně mění intenzitu — výrazně se mění gradient.

Detekce hran je důležitá při identifikaci objektů a počítačovém vidění.
Bývá implementováná pomocí (první, druhé) derivace (resp. numerické diferenciace).
Hrany lze detekovat pomocí konvoluce.

Important

Numerické diferenciaci se věnuje otázka Numerické metody.

Podle první derivace (gradientu)

Prewittové operátor / Prewitt operator

Aproximuje velikost gradientu pomocí centrálních konečných diferencí. Skládá se ze dvou konvolucí s jádry:

P_{x} = - 1 - 1 - 1 000111 P_{y} = 10 - 1 10 - 1 10 - 1

Které se dají odseparovat na:

P_{x} = - 1 01 \cdot [111] P_{y} = 111 \cdot [- 1 01]

Aproximace je pak dána jako:

∣ \nabla f (m, n)∣ \approx (P_{x} * I)^{2} + (P_{y} * I)^{2}

kde $I$ je vstupní obraz.

Note	Všimni si podobnosti s Sobelovým operátorem. Jen místo Gaussovského rozmazání používá box filtr.

Sobelův operátor

Aproximuje velikost gradientu pomocí centrálních konečných diferencí. Skládá se ze dvou konvolucí s jádry:

G_{x} = - 1 - 2 - 1 000121 G_{y} = 10 - 1 20 - 2 10 - 1

Tato jádra se dají odseparovat na:

G_{x} = - 1 01 \cdot [121] G_{y} = 121 \cdot [- 1 01]

Note	Všimni si, že jeden kernel je Gaussovo rozmázání a druhý jsou centrální diference.

Aproximace je pak dána jako:

∣ \nabla f (m, n)∣ \approx (G_{x} * I)^{2} + (G_{y} * I)^{2}

kde $I$ je vstupní obraz.

Robertsův operátor / Roberts cross

Aproximuje velikost gradientu pomocí konečných diferencí. Detekuje především hrany se sklonem 45°.

∣ \nabla f (m, n)∣ \approx ∣ f (m, n) - f (m + 1, n + 1)∣ + ∣ f (m + 1, n) - f (m, n + 1)∣

kde barevné výrazy získa dvěma konvolucemi s jádry:

R_{x} = [10 0 - 1] R_{y} = [0 - 1 10]

Robinsonův operátor / Robinson compass mark

Detekuje hrany pomocí centrální diferencí. Používá osm různých jader, jedno prokaždý směr na kompasu. To mu umožňuje snadno aproximovat nejen velikost ale i směr gradientu.

Canny edge detector

Algoritmus pro detekci hran. [23] [24]

Má nízké procento chyb.
Přesně lokalizuje hrany.
Má jednoznačnou odezvu (hrana prostě buď je nebo není).
Ale neprodukuje nutně spojité hrany.

Zjednodušený postup:

Aplikuj Gaussovo rozmazání na vstupní obraz, pro odstranění šumu.
Spočítej gradient intenzity obrazu (pomocí Roberts, Sobela, …).
Non-maximum suppression: zuž hrany na jednopixelovou šířku.
Double threshold: urči, které pixely jsou strong, weak a non-relevant.
Aplikuj hysterezní prahování: spoj strong pixely s weak pixely, pokud je kolem nich strong pixel.

Podle druhé derivace

Hrany lze detekovat pomocí druhé derivace obrazu. Nacházejí se v nulových bodech / zero crossings (tedy v maximech a minimech první derivace).

Divergence

Divergence je operátor, který vrací skalární hodnotu. Popisuje zda gradient roste či klesá. Je definován jako: [25]

div F = \nabla \cdot F = \frac{\partial F _{x}}{\partial x} + \frac{\partial F _{y}}{\partial y} + \frac{\partial F _{z}}{\partial z}

Laplaceův operátor / Laplacian

Laplaceův operátor $Δ$ hledá hrany pomocí divergence gradientu.

Produkuje spojité hrany.
Uzavřené kontury.
Invariantní k otáčení o násobky $π /2$ .
Ale je velmi citlivý na šum.
Nedetekuje orientaci hrany.

Δ f = \nabla^{2} f = \nabla \cdot \nabla f = f_{xx} + f_{yy}

kde $f$ je vstupní obraz.

Jeho diskrétní aproximace v maticové podobě potom vypadá jako:

010 1 - 4 1 010

Laplacian of Gaussian (LoG)

Kombinace Gaussovského rozmazání a Laplacianu.

Laplaceův operátor je velmi citlivý na šum. Proto se před jeho použítím obraz často prožene Gaussovským rozmazáním.

Matice pro LoG je potom dána jako:

00 - 1 00 0 - 1 - 2 - 1 0 - 1 - 2 16 - 2 - 1 0 - 1 - 2 - 1 0 00 - 1 00

Říká se mu Mexican hat.

Integrální transformace

Transformace, která mapuje funkci $f : A \to B$ z jejího původního funkčního prostoru $A \to B$ do nějakého jiného funkčního prostoru $A^{'} \to B^{'}$ . Používá se, protože s některými vlastnostmi funkcí je snazší pracovat v jiném prostoru. [18]

Patří sem transformace jako:

Fourierova transformace,
vlnková transformace,
Houghova transformace,
Radonova transformace.

Fourierova transformace

Fourierka je ako more. Je to hromada vlniek.

— Nika Kunzová

Tip	3Blue1Brown má skvělý video o Fourierově transformaci, ze kterého to pochopíš! (a evidentně je tak dobrý, že mi Copilot sám nabídl správný link…)

Je operace (integrální transformace) při níž je obraz převeden z prostorové do frekvenční domény. A při inverzní Fourierově transformaci obráceně. [8]

Frekvenční doména je složena ze sinusoid s různými frekvencemi a fázemi (indikovaných pomocí polárních souřadnic).
Intenzita pixelu v obrazu frekvenční domény pak udává amplitudu dané sinusoidy.
Roztažení (stretch) funkce v prostorové doméně odpovídá opakování funkce (repetition) ve frekvenční doméně.
Posun (shift) v prostorové doméně ovlivňuje jenom fázi.

Eulerova formule: Eulerova formule je vztah mezi komplexními čísly a goniometrickými funkcemi.

$e^{i θ} = cos θ + i sin θ$

Lidskými slovy říká (viz 3b1b), že komplexní číslo $e^{i t}$ popisuje pohyb po jednotkové kružnici v komplexní rovině proti směru hodinových ručiček. Jedna otáčka je $t = 2 π$ radianů.
1D Fourierova transformace: Eulerovu formuli využijeme při popisu Fourierovy transformace:

$FT pro frekvenci u F (u) = pro v \overset{s}{ˇ} echna x v cel \overset{e}{ˊ} m defini \overset{c}{ˇ} n \overset{ı}{ˊ} m oboru funkce f \int_{- \infty}^{\infty} polom \overset{e}{ˇ} r podle funkce f f (x) f \overset{a}{ˊ} ze kru \overset{z}{ˇ} nice podle frekvence a \overset{c}{ˇ} asu e^{chceme po sm ru hodin - komplexn slo i cel kru nice 2 π frekvence ve FT u as ve funkci f x} d x$

Forward (z prostorové do frekvenční domény): [8]

$F (u) F (k) = \int_{- \infty}^{\infty} f (x) e^{- i 2 π ux} d x = \frac{1}{N} m = 0 \sum N - 1 f (m) e^{\frac{- i 2 πkm}{N}} spojit \overset{a}{ˊ} diskr \overset{e}{ˊ} tn \overset{ı}{ˊ}$

Inverse (z frekvenční do prostorové domény):

$f (x) f (x) = \int_{- \infty}^{\infty} F (u) e^{i 2 π ux} d u = \frac{1}{N} m = 0 \sum N - 1 F (k) e^{\frac{2 πimk}{N}} spojit \overset{a}{ˊ}$
2D Fourierova transformace: Forward (z prostorové do frekvenční domény): [8]

$F (u, v) F (u, v) = \int_{- \infty}^{\infty} \int_{- \infty}^{\infty} f (x, y) e^{- i 2 π (ux + v y)} d x d y = \frac{1}{MN} m = 0 \sum M - 1 n = 0 \sum N - 1 f (x, y) e^{- i 2 π (\frac{m \cdot u}{M} + \frac{n \cdot v}{N})} spojit \overset{a}{ˊ} diskr \overset{e}{ˊ} tn \overset{ı}{ˊ}$

Inverse (z frekvenční do prostorové domény):

$f (m, n) f (m, n) = \int_{- \infty}^{\infty} \int_{- \infty}^{\infty} F (u, v) e^{i 2 π (u m + v n)} d u d v = \frac{1}{MN} k = 0 \sum M - 1 l = 0 \sum N - 1 F (u, v) e^{i 2 π (\frac{u m}{M} + \frac{v n}{N})} spojit \overset{a}{ˊ} diskr \overset{e}{ˊ} tn \overset{ı}{ˊ}$
Fast Fourier Transform (FFT): Algoritmus pro rychlé výpočty diskrétní Fourierovy transformace (DFT). [9]
Konvoluční teorém: Říká, že běžné násobení ve frekvenční doméně odpovídá konvoluci v prostorové doméně a obráceně. To je cool, protože konvoluce je pomalá, ale násobení je rychlé. [6]

$F {f * g} = F {f} \cdot F {g}$

kde $F$ je Fourierova transformace.

Sampling / vzorkování

Samplování je převod spojitého signálu na diskrétní. [sampling]

Převzorkování

Je proces, kdy na vstupu je diskrétní signál s nějakou vzorkovací frekvencí a na výstupu je diskrétní signál s jinou vzorkovací frekvencí.

V případě 2D obrazů to může ale nemusí znamenat změnu velikosti obrazu. [image-scaling]

Vzorkovací teorém / Nyquist-Shannon sampling theorem

Říká, že chceme-li spojitý signál převést na diskrétní a pak z tohoto diskrétního signálu zrekonstruovat původní spojitý signál, můsíme samplovat s alespoň dvojnásobnou frekvencí než je nejvyšší frekvence v původním signálu. [12]

Původní spojitý signál musí být frekvenčně omezený (band-limited), aby bylo možné v něm určit nejvyšší frekvenci.
Při nesplnění těchto podmínek vzniká aliasing.

Tip
Aliasingu se věnuje část otázky Renderování s využitím GPU.

Tip	Intuitivně je signál hromádka kopečků. Abychom poznali i ty nejužší kopečky — s nejvyšší frekvencí — musíme mít dostatečně jemné síto — koukat na kopečky s dvakrát takovou frekvencí, abychom si všimli, že někde začíná a končí.

Rekonstrukce

Proces, kdy z diskrétního signálu zpět získáme spojitý signál. [14]

Rekonstrukční filtr

Filtr pro rekonstrukci signálu.

box: nejbližší soused,
tent: lineární interpolace,
sinc,
Lanczos,
Gaussian.

Geometrické transformace

Geometrická transformace $T$ je bijekce mezi body dvou obrazů $I$ a $J$ . Díky tomu, že je to bijekce, k ní musí vždy existovat inverze. [13]

J [u, v] = T (u, v) = I [x (u, v), y (u, v)]

Patří sem operace jako:

posunutí / translace,
rotace,
škálování,
zkosení / shear,
zrcadlení / flip,
deformace / warping (na rozdíl od operací výše není lineární).

Dopředné mapování / forward mapping: Procházíme pixely v $I$ a hledáme jejich umístění v $J$ (metoda "Kam s ním?").
Zpětné mapování / backward mapping: Pro každý pixel $J$ počítáme jeho původní umístění v $I$ (metoda "Kde je?").

Vlnková transformace / wavelet transform

Tip	Opět výborné video, bohužel ne od 3b1b, ale obdobně kvalitně zpracované: Wavelets: a mathematical microscope.

Vlnka / wavelet

Funkce $ψ$ , která je omezená v čase. Je to "brief oscillation". [15]

Má konečnou energii:

$\int_{- \infty}^{\infty} ∣ ψ (t) ∣^{2} d t < \infty$
Splňuje podmínku přípustnosti:

$C_{ψ} = \int_{0}^{\infty} \frac{∣ ψ ^ ( ω ) ∣ ^{2}}{ω} d ω < \infty$

kde $\hat{ψ}$ je Fourierova transformace $ψ$ . Tato podmínka zajišťuje invertibilitu vlnkové transformace.
Z podmínky přípustnosti plyne, že vlnka musí mít nulovou střední hodnotu:

$\int_{- \infty}^{\infty} ψ (t) d t = 0$

⁂

Vlnková transformace je integrální transformace, která popisuje funkci v čase a frekvenci zároveň. Popis v čase je dán tím, že vlnky (narozdíl od sinusoid u Fourierky) jsou časově omezené. [15]

Používá se k:

Detekci nespojitosti signálu a jeho derivaci.
Identifikaci okamžitých frekvencí.
Odstranění šumu.
Extrakci příznaků.
Kompresi signálu.

Základní myšlenka je:

Zvolíme mateřskou vlnku $ψ$ (je spousta různých, ale nejznámnější je Morletova vlnka $ψ (t) = k \cdot Rotace jako u FT e^{i ω_{0} t} \cdot \overset{ˇ}{S} k \overset{a}{ˊ} la e^{\frac{- t ^{2}}{2}}$
Tuto vlnku můžeme posouvat a škálovat pomocí parametrů $a$ a $b$ - $ψ_{a, b} = ψ \frac{t - b}{a}$ .
Posouváme naši vlnkovou funkci po signálu oběma parametry a pro každý bod sledujeme shodu s funkcí. Tu získáme intuitivně, jako integrál součinu vlnky a signálu $\int_{- \infty}^{\infty} y (t) ψ_{a, b} (t) d t$ . Pokud se ale podíváme na to, co to znamená ve frekvenční doméně, zjistíme, že to je skalární součin mezi Fourierovou transformací signálu a vlnky $⟨ f, ψ_{a, b} ⟩$ .
Pokud toto uděláme pro každý bod časové ( $a$ ) a frekvenční ( $b$ ) domény, dostaneme výsledný obraz vlnkové transformace.
Ale co to? V reálné části výsledku vidíme podivné vlnky! To je proto, že vlnková funkce je komplexní a ve skutečnosti nám dot product nevrací jednu hodnotu, ale komplexní číslo. Pokud zkoumáme to, pak vidíme, že rotuje kolem středu imaginární roviny. Stačí nám tedy změřit jeho vzdálenost od středu (absolutní hodnotu komplexního čísla) a dostáváme vlnkovou transformaci.

Ve výsledku je to fakt jen dot product funkce $f$ s upravenou vlnkou $ψ_{a, b}$ !

[W_{ψ} f] (a, b) = ⟨ f, ψ_{a, b} ⟩ = \int_{- \infty}^{+ \infty} f (t) ψ_{a, b}^{*} (t) d t = \int_{- \infty}^{+ \infty} f (t) \frac{1}{a} ψ^{*} (\frac{t - b}{a}) d t = f * ψ_{a}^{*} (b) = \frac{1}{2 π} ⟨ \hat{f}, \hat{ψ}_{a, b} ⟩,

kde:

$ψ$ je mateřská vlnka,
$ψ_{a, b}$ je škálovaná a posunutá mateřská vlnka,
$a$ je škálovací parametr,
$b$ je posunutí.
$\hat{f}$ je Fourierova transformace funkce $f$ ,
$\hat{ψ}$ je Fourierova transformace vlnky $ψ$ ,
$⟨ \cdot, \cdot ⟩$ je skalární součin,
$*$ u $ψ^{*}$ je komplexně sdružená funkce,
$*$ je spojitá konvoluce,
$ψ_{a} (t) = \frac{1}{a} ψ (\frac{- t}{a})$ je spojitý filtr, který odpovídá vlnce $ψ$ , pro dané měřítko $a$ .

Dále platí:

Vlnky jsou konstruovány, aby měly vhodné vlastnosti například pro zpracování signálů.
Vlnková transformace je v podstatě konvoluce signálu s vlnkou.

Představme si například vlnku, která má frekvenci tónu střední C a krátké trvání odpovídající osminové notě. Provedeme-li v pravidelných intervalech konvoluci takovéto vlnky se signálem - nahrávkou písně - pak nám výsledky této konvoluce napoví, kdy byla nota „osminové střední C“ v nahrávce použita.

Matematicky vzato, k vysoké korelaci vlnky se signálem (vysokému korelačnímu koeficientu) dojde v těch místech (intervalech), kde signál obsahuje informaci o podobné frekvenci, tedy tam, kde je námi zvolené vlnce nejpodobnější. Tento koncept je jádrem mnoha aplikací vlnkové transformace. [27]

Houghova transformace

Tip	Super minutu a půl dlouhé video, co ti řekne úplně všechno.

Integrální transformace, která identifikuje přímky v obraze. V rozšířené podobě hledá libovolné tvary zadané parametricky. [16]

Dlouho byla používána pro detekci čar na silnici pro autonomní řízení aut. (Už ne. Dnes se používají neuronové sítě.)
Pracuje nad binárním obrazem.
Mapuje tvar na bod v parametrickém prostoru.

Houghův prostor: Prostor je definován jednoduchou rovnicí $x \cdot cos (θ) + y \cdot sin (θ) = ρ$ .

Bod v prostoru obrázku je reprezentován jako křivka v Houghově prostoru. Bod v Houghově prostoru je reprezentován jako přímka v obrázku.

Můžeme promítnout všechny body z obrázku do Houghova prostoru s intenzitou odpovídající intenzitě bodu v obrázku. Pak hledáme body v Houghově prostoru, které mají největší intenzitu. To jsou body, které reprezentují přímky v obrázku.

Radonova transformace

Tip	Jako je již tradicí, mám pro vás video…

Integrální transformace, která integruje funkci přes přímky. Tedy rozkládá funkci na hromádku parametrů, které definují přímky.

Užitečná je především inverzní Radonova transformace, která se používá v tomografii ("CTčko"). [17]

Mějme 3D objekt, který chceme "proskenovat" z různých úhlů $ϕ$ . Pro každý úhel chceme získat 1D projekci objektu $p (s, ϕ)$ . Tato projekce je dána integrálem funkce $f (x, y)$ přes přímku.

Uvažme, že nejprve celý prostor otočíme o úhel $ϕ$ a potom provedeme jednoduchou projekci všech bodů na této přímce.

(x y) = (cos ϕ sin ϕ - sin ϕ cos ϕ) (s u) \Rightarrow x = s cos ϕ - u sin ϕ y = s sin ϕ + u cos ϕ

p (s, ϕ) = R {f (s, ϕ)} = \int_{- \infty}^{\infty} f (x, y) d u = \int_{- \infty}^{\infty} f (s cos ϕ - u sin ϕ, s sin ϕ + u cos ϕ) d u

Pokud vezmeme všechny hodnoty z této projekce, získáme tzv. Sinogram:

Inverzní funkce je velice užitečná, ale poměrně složitá, takže doufám, že stačí tato obecná myšlenka.

⁂

Tabulka 1. Radon vs Hough
Radon	Hough
Vyvinuta v 1917	Vyvinuta v 1962
Nejčastěji hledá přímky	Hledá nějaký tvar zadaný parametricky (přímky, kružnice, elipsy, …)
Dopředná transformace nás moc nezajímá tu provádí CT skener kontinuálně	Dopředná transformace je implementovaná diskrétně
Hlavním cílem je rekonstrukce obrazu — inverzní transformace	Hlavním cílem je detekce tvarů

Zdroje

[1] PB130 Úvod do digitálního zpracování obrazu (podzim 2022)
[2] PV131 Digitální zpracování obrazu (jaro 2023)
[3] Wikipedia: Raster graphics
[4] Wikipedia: Digital image processing
[5] Wikipedia: Filter (signal processing)
[6] Wikipedia: Convolution
[7] Wikipedia: Edge detection
[8] Wikipedia: Fourier transform
[9] Wikipedia: Fast Fourier transform
[10] Wikipedia: Sampling (signal processing)
[11] Wikipedia: Image scaling
[12] Wikipedia: Nyquist–Shannon sampling theorem
[13] Wikipedia: Geometric transformation
[14] Wikipedia: Signal reconstruction
[15] Wikipedia: Wavelet transform
[16] Wikipedia: Hough transform
[17] Wikipedia: Radon transform
[18] Wikipedia: Integral transform
[19] Wikipedia: Histogram
[20] Wikipedia: Histogram equalization
[21] Bitesize: Histograms - Higher only
[22] Wikipedia: Sobel operator
[23] Wikipedia: Canny edge detector
[24] Canny Edge Detection Step by Step in Python — Computer Vision
[25] Wikipedia: Divergence (operátor)
[26] Wikipedia: Difference of Gaussians
[27] https://hackmd.io/@fi-muni-viz-2022/SywCznl2t
[28] Wikipedia: Vlnka