Zpracování tematických okruhů na státní zkoušku z předmětu
"Rozpoznávání a zpracování obrazu", která zahrnuje předměty ROZ1,
ROZ2 a SFTO (PGR013)
Tento soubor obsahuje obrázky ze slajdů prezentovaných na přednášce z
předmětu ROZ1, ROZ2 a SFTO, proto je možné ho dále šířit jen
s výslovným souhlasem Prof. Ing. Jana Flussera, DrSc.
Otázky zpracoval pro své studijní účely Adam Novozámský.
1. Okruh - Lineární filtrace v prostorové a frekvenční oblasti(definice
a základní vlastnosti ve spojité a diskrétní oblasti):
1.1.Konvoluce:
f nechám a g posunu do t a otočím:
∞
∗  =
  ( − )
−∞
∗: 1 × 1 → 1
V podstatě se jedná o průměrování fce  jinou fcí , protože je obyčejně g symetrická fce
s malým supportem. Většinou se požaduje, aby výsledná fce měla stejně omezený obor
hodnot jako původní fce , takže se volí   = .
Funkci () se říká konvoluční jádro. Pokud jde o konvoluci v Image Processing je funkce
() většinou zkoumaný obrázek a funkce () nějaký filtr.
Vlastnosti konvoluce:
Komutativní
Asociativní
Distributivní
Existence jednotky
∗ =∗
 ∗  ∗  = ( ∗ ) ∗ 
 ∗  +  =  ∗  + ( ∗ )
∗ = ∗ = 
kde δ je tzv. Diracova delta funkce:   = 0,  ≠ 0
a v  = 0 to není definováno.
Integrál Delta funkce je roven 1:
∞
   = 1
−∞
Jde tedy o puls trvající nekonečně krátkou dobu.
Asociativita pří násobení
skalárem
Konvoluční teorém
  ∗  =  ∗  =  ∗ ()
pro všechna reálná (nebo komplexní) čísla a.
  ∗  = () ∙ () =  ∙ 
kde () značí Fourierovu transformaci 
∞
() ≡ () ≡
∞
Diskrétní konvoluce
   −2 
−∞
∗  =
  ∙ −
 =−∞
V případě diskrétní konvoluce lze jádro chápat jako tabulku (konvoluční maska), kterou
položíme na příslušné místo obrazu. Každý pixel překrytý tabulkou vynásobíme koeficientem
v příslušné buňce a provedeme součet všech těchto hodnot. Tím dostaneme jeden nový pixel.
Možnosti v MatLabu:
valid
obrázek se zmenší o půlku g
same
obrázek je stejný
full
obrázek se zvětší o půlku g
Ošetření okrajového jevu:
• Oblepení nulami – zero padding
• Zrcadlové prodloužení – mirror extension
• Periodické prodloužení – periodic extension
1.2.Fourierova transformace
Fourierova řada:
Transformační vztahy:
Linearita
Konvoluce
convolution theorem
Posun
shift theorem
Rotace
Změna měřítka
similarity theorem
F(R( f )) = R(F( f ))
2D Fourierova transformace:
Bázové funkce 2D FT:
real, u=v
imag, u=v
Některé příklady FT:
Diskrétní Fourierova transformace (DFT):
Přímý výpočet - O(N^2)
FFT - O(N logN) (Cooley, Tookey, 1960)
Filtrace ve frekvenční oblasti:
Otázky:
 Zdvojnásobují se data při FT? – ne, FT je symetrická středově (n je reálné)
 Nejvyšší frekvence u DFT? – n=0 to je konstanta, n=1 je to pul sinu, n=2 je to
sin…Takže nejvyšší vlnová dálka jde přes 2 body a tím, že je to simetrické tak je to
v n=N/2.
 Co nese více informací – amplituda nebo fáze? – fáze (tu vizuální)
 Co se stane, když amplitudu nahradím jedničkami a fázi nechám? – Po inverzní FT
dostanu černý obrázek a obrysy budou bílé.
 Porovnání rychlosti výpočtu s konvolucí – Při malém filtru je rychlejší počítat
v obrazové oblasti, ale při velikém je lépe přejít do frekvenční.
2. okruh - Digitalizace obrazu:
2.1.vzorkování spojitých funkcí
Jde o diskretizaci v soustavě souřadnic.
Matematický model vzorkování:
Obrazová oblast –
f(x,y) je původní obraz;
d(x,y) je výsledný obrázek;
s(x,y) je pole delta fcí:
Frekvenční oblast (s použitím konvolučního teorému) –
D(u,v) jsou ta spektra, kterých je nekonečně mnoho
vedle sebe.Čím více budu vzorkovat, tím budou
dále od sebe.
Signál jde zpětně zrekonstruovat,
jednotlivá spektra nepřekrývají.
pokud
se
Zpětná rekonstrukce obrazu:
Vyříznutí jednoho spektra a následná inverzní FT
odpovídá interpolaci v obrazové oblasti.
10
9
2.2.kvantování spojitých funkcí
7
6
Output
Diskretizace oboru hodnot signálu – vždy ztrátové
Kvantizér Q: R  L
L = {0, 1, ... , k}
(k = 255)
8
5
4
3
2
1
0
0
t1
t2
t3
t4
t5
Input
t6
t7
t8
t9
0
Kvantovaný signál:
Jak nastavit kvantovací prahy:
 vše co je menší než nulový práh je rovno 0
 nejvyšší práh nastavím tak, aby se rovnal citlivosti snímače
 to mezi se většinou dělá rovnoměrně
 jen pokud mě zajímá něco víc, tak to rozdělím třeba logaritmicky
Kvantizační šum:
Mohou vznikat falešné kvantizační hrany.
Lidské oko dokáže rozlišit 100 úrovní šedi, když jsou vedle sebe. Pokud jsou odděleně tak jen
40 úrovní.
2.3.Shannonův teorém
Nyquist (1915), Kotelnikov (1933), Shannon (1945)
Obecně znám jako tzv. vzorkovací teorém.
„Přesná rekonstrukce spojitého, frekvenčně omezeného, signálu z jeho vzorků je možná tehdy,
pokud byl vzorkován frekvencí alespoň dvakrát vyšší než je maximální frekvence
rekonstruovaného signálu.“
2.4.Nyquistovy podmínky
Existuje taková frekvence vzorkování, že se ty opsané obdélníky (Wu a Wv) dotknou, ale
nepřekryjí.
Podmínky:
při rovnosti je to optimální;
Pokud je W:
1. Jsou maximální frekvence zastoupená ve spektru signálu – potom tam musejí být
v podmínkách ostré nerovnosti
2. Jsou omezovací koeficienty pro vzorkovací frekvenci – pak tam může být i to rovnítko
Bohužel v reálu nejsou obrázky jasně frekvenčně ohraničeny, resp. jsou, ale vysokou
frekvencí, kterou nezachytíme s žádným přístrojem, proto jsou téměř vždy podvzorkovány –
• Rastr je omezený
• Jen několik možných vzorkovacích frekvencí
• Vzorkování není pomocí δ – funkcí
• Optika působí jako low-pass filtr
Vzorkování s nedostatečnou frekvencí:
Překrytí sousedních spekter
D(u,v)

ztráta
VF
informace (hrany, detaily,
...), aliasing
Moiré efekt – falešné nízké
frekvence (kola ve filmu,
zářivka, cirkulárka)
Anti-aliasing techniky:
• Zvýšení vzorkovací frekvence – to ale nejde vždy
• Odstranění vysokých frekvencí ještě před vzorkováním – nějakým filtrem(optika –
mírné rozostření); to mi zabrání překrytí těch spekter a vznik falešných frekvencí.
Otázky:
 Je dobré mít pravoúhlé vzorkování? – efektivnější by bylo jiné, třeba hexagonální, aby
spektra pokrývali největší plochu a zároveň se nepřekrývala. Ale většina scannerů a
dalších přístrojů má pravoúhlé vzorkování, kvůli jednodušší konstrukci.
 Když mám hodně členitou scénu, co je více potřeba, jemnější vzorkování nebo
kvantování? – vzorkování.
 Když mám v obraze hodně velké plochy, scéna není tak členitá – co je více potřeba,
jemnější vzorkování nebo kvantování? – kvantování.
3. okruh - Základní operace s obrazy:
3.1.Histogram
Je sloupcový graf, v němž každé třídě přiřadíme její četnost (počet pixelů
s danou intenzitou).
Jde vlastně o hustotu pravděpodobnosti.
Kontrast: rozptyl (malý kontrast – rozptyl histogramu je úzký); změnit jas =
přičíst nebo odečíst hodnotu v pixelech obrázku
Jas: střední hodnota histogramu; změnit kontrast = vynásobit nebo vydělit
hodnoty v pixelech
3.2.změny kontrastu a jasu
Transformace:
Lineární binární transformace
Přechod od pozitivu k negativu
Pro zvýraznění kontur


Gama korekce: Output = (input)gama
slouží ke zvýraznění kontrastu
pokud gama < 1 dojde ke zvýraznění tmavých částí
;gama = 3, 4, 5
3.3.ekvalizace histogramu
Ekvalizace histogramu je algoritmus, který změní rozložení
intenzit v obraze tak, aby se v něm vyskytovaly pokud možno
intenzity v širokém rozmezí, a to přibližně se stejnou četností. U
obrazů s konečným počtem obrazových bodů se lze tomuto cíli
jen přiblížit. (Upravuje kontrast obrazu tak, aby byl jeho
histogram vyrovnaný.)
K transformaci používáme distribuční fci(kumulativní histogram).
Na histogram se můžeme dívat jako na hustotu pravděpodobnosti a na kumulativní histogram
jako na distribuční funkci. Chceme, aby histogram nesl co nejvíce informace. (Uvažujeme
opačně, kdy nese informace nejméně? Je to právě při konstantní ploše, tedy když je histogram
dirakův impulz. Opakem je konstantní histogram, kterého chceme dosáhnout.)
kumulativní histogram lze z normálního histogramu vypočítat podle vztahu:
Každá p-tá položka má tedy v kumulativním histogramu hodnotu rovnou součtu hodnot všech
položek normálního histogramu, které mají index menší nebo roven p.
4. okruh - Odstranění šumu:
míra šumu v obraze:
Signal-to-noise ratio (SNR)
SNR = 10 log (D(f)/D(n))
[dB]
D(f) … rozptyl nezašuměného signálu
D(n)… rozptyl šumu
 čím vice decibelů, tím méně zašuměné; v praxi od 15dB a více pro pouhé oko
dostačující.
Ve frekvenční oblasti je SNR definována takto:
2
, 
2
Kdyby šum byl bílý =>  2 = 2
Pokud je signál nekorelovaný =>  2 = 2
Což jsou ty rozptyly:
2
2
Protože ty rozptyly v praxi moc neznáme, tak to odhadujeme většinou jako celek.
4.1.lineární metody
4.1.1. průměrování v čas
Scéna je statická, nehýbe se. => Nafotím ji vícekrát,
sečtu v jednotlivých pixelech a vydělím počtem snímků
(šum klesá s hodnotou 2/N).
Tato metoda nepřináší žádné degradace.
4.1.2. Konvoluční filtry
Jde o lokální průměrování s maskou, kterou použijeme
při konvoluci. Daní za odstranění šumu je rozmazání obrázku a ztráta hran, protože většinou
potlačují vysoké frekvence, kde vadí šum nejvíce.
 Průměrování (prosté a vážené):


Průměrování podél hran: pokud máme informaci o tom, kde jsou hrany a jakým
směrem jdou, můžeme měnit masku podle toho a průměrovat jen podél hran.
Problémem je ale to, že hranový detektor detekuje stejně
hrany jako šum, tedy se to dá použít jen s apriorní
informací o tom, kde jsou.
Rotující okno: máme dva typy konvoluční matice pro
všech 8 směrů v daném bodě. Spočítám jednotlivé
konvoluce a vyberu tu, která vznikla v okně, jenž má
minimální rozplyt od této hodnoty. Tato metoda dává
docela dobré výsledky.
4.1.3. Filtry ve frekvenční oblasti
Podívám se do frekvenční oblasti a odstraním nebo utlumím vysoké frekvence pomocí
hladkých low-pass filtrů.
4.2.metody zachovávající hrany
 Minimalizace funkcionálu
 Splajnové metody
V sešitě mám poznámku, že se tyto metody nemusíme učit, jen je stačí znát => zeptat se
JF, jestli to stačí i ke státnicím.
4.3.mediánový filtr (nelineární filtr)
Posouvám okno jako při konvoluci.
V každém posunutí spočítám medián a
dosadím ho do středového bodu. (Medián se
počítá tak, že dané hodnoty v masce seřadím
a vezmu prostřední z nich.)
Na šum „pepř a sůl“ to funguje dobře. Ale
pokud je výskyt šumu v daném vybrání větší
než 50%, tak je originální signál brán jako
šum a je z obrázku odstraněn.
Má to také špatný vliv na hrany, kde okusuje
okraje a rohy. Proto je vhodnější za výběrové
okno brát třeba kříž. Pokud je obrázek málo nebo vůbec zašuměn, tak hrany zůstávají. Ale
čím více šumu, tím více se to rozmazává. Např. pokud máme jednopixelovou čáru, tak ji filtr
sežere.
4.4.pojem "bílý šum"
Gaussovský bílý šum má normální rozložení => míra šumu je stejná na všech pixelech.
Pokud něco nazýváme bílým, myslíme tím:
 že dvě náhodné veličiny jsou navzájem nekorelované. V tomto případě to tedy
znamená, že míra šumu je pixel od pixelu na sobě nezávislá. Jedná se třeba o tepelný
šum na CCD.
 že střední hodnota je rovna nule
Značíme AGWN = Additing Gaussian White Noise.
Nekorelované x Nezávislé se u gaussovských veličin rovná.
Další modely šumu:
 aditivní náhodný šum – k obrázku se přičítá: g = f + n. Prostě se vezme stejně velká
matice hodnot a ta se přičte.
 Impulsní šum(sůl a pepř) – náhodné veličiny šumu nabývají tří hodnot:
pravděpodobnost
o +∞
p
(bílé)
o –∞
p
(černé)
o 0
1-2p (nemění se)
Čím se „p“ zvětšuje, tím to je horší. Sůl a pepř se odstraňuje lépe než gaussovský šum.
5. okruh:
5.1.Detekce hran
5.1.1. 1. derivace
Roberts, Sobel, Prewitt, Kirsch
Založeno na derivaci obrázku a sledování velkých hodnot derivace.




−1
v druhém
1
směru (vodorovném). Porovnám oba směry a beru maximum z nich. Nevýhodou této
metody, že je strašně citlivá na šum – kde je šum, jsou všude hrany. Proto ostatní
metody pracují s trochu rozmazanými obrázky. Ale zas to nesmí být moc, pak už
nedetekujeme nic 
−1 −2 −1
Sobelův detektor – používá masku 0
0
0 , takových masek je celkem 8.
1
2
1
Většinou se použijí všechny a pak podle maxima vyberu tu největší (je to ta, kde hrana
běží ve směru nul). Jde vlastně o průměrování 1. Derivací, kde centrální bod má
dvojnásobnou váhu. Je to robustnější proti šumu, díky velikosti matice.
Dále máme Prewitta a Kirsche – obdobné, jen jiné masky.
Canny – požadavky při jeho konstrukci byly:
o jedna hrana jedna odezva
o přesná lokalizace hran
o nic nepřehlédnout
o nevytvářet zbytečné hrany
Postup:
o obraz se vyhladí pomocí konvoluce s gaussovským
jádrem, za účelem odstranění šumu –  ∗ 
o poté to derivuji, třeba jen jednoduchým Robertsem
∗ ′
o oprahuji a zůstanou mi jen významné body – tedy
odstraním to, co není maximem a zbude mi obrázek
s úseky hran
o a pak to trasuji – tedy jedu po těch částečných
hranách, a pokud v nějakém směru hrana pokračuje,
tak to naváže
Roberts – konvoluce s maskou −1
1 v jednom směru (svislém) a
5.1.2. 2. derivace
Detekce hran, tam kde 2. derivace je nula. Primitivní metoda ∆ = 0 moc
nefunguje, protože je ještě více citlivá na šum a navíc se to rovná nule i tam,
kde jsou homogenní oblasti, plus ještě některé velmi jasné hrany
nedetekuje.
 D. Marr, E. Hildreth (1980):LoG (Laplacian of Gaussian) ∆  ∗  = ∆ ∗ 
∆ … vypadá jako obrácený mexický klobouk (viz níže)
Provádím „zero-crossing detection“ – procházím obrázek třeba
maskou 2x2 a sleduji, jestli se mi tam objevují změny z velké kladné
hodnoty do velké záporné a naopak. Tam pak řeknu, že to prochází
nulou a je tam hrana, i když tam bod roven nule vůbec nemusí být.
sigma = 2
sigma = 2
sigama = 4
Výsledek je odpověď ano/ne, tedy černobílý. Hrany
mají tendenci se u této metody uzavírat do sebe.
sigma = rozptyl masky;


5.1.3. Jen pro úplnost – máme ještě detektory:
nepracující s derivací: Whitening
pracující ve frekvenční oblasti:
Chci-li ve frekvenční oblasti detekovat hrany pod
určitým úhlem, musím se ve spektru signálu dívat
ve směru kolmém na tento úhel.
∆
5.2.zaostření obrazu
Pokud bereme hranici hrany jako přechod od jedné oblasti k druhé, tak potom, čím je tento
přechod strmější, tím je hrana jasnější.
Díky Laplaceově operátoru ∆ jsme schopni v obrázku zvýraznit hrany a tím i obraz zaostřit. A
to tím, že od f odečteme ∆F:  − ∆
Nebo v praxi, provedeme konvoluci s konvolučním jádrem:
0 −1 0
−1 5 −1
0 −1 0
Otázky:
 Proč je potřeba zvýrazňovat hrany, aby obrázek lépe vypadal? – Mozek má schopnost
doplňovat nízkofrekvenční informace, ale vysokofrekvenční ne.
6. okruh:
6.1.segmentace obraz
Jedná se o analýzu obrazu vedoucí k nalezení objektů v obraze. Za objekty se zde považují
části obrazu, které jsou bodem zájmu v dalším průběhu zpracování. Cílem segmentace je tedy
rozdělení obrazu do částí odpovídající předmětům či oblastem reálného světa. Výsledkem
segmentace by měl být soubor oblastí, které odpovídají objektům ve vstupním obraze. Jedná
se pak o tzv. kompletní segmentaci. Pokud ale oblasti neodpovídají přesně objektům, tak tuto
segmentaci nazýváme částečnou. Kompletní segmentace obecně využívá vyšší úrovně
zpracování, která je založena na znalostech řešeného problému. Částečná segmentace je
založena na principu homogenity obrazových částí (např. jas, barva) uvnitř segmentu.
Detekci objektů můžeme tedy rozdělit:
6.1.1. Thresholding (prahování)
Histogram objektu je tzv. bimodální – má 2 lokální maxima –
jedno odpovídá objektu jedno pozadí. A tak ho vezmu a
naleznu lokální minimum mezi nimi. To co je pod ním, dám
roven nule a to co je nad, dám rovno 1. Tím nám vznikne
binární obrázek.
 lze provést jen lokální prahování
 funguje dobře u obrázků, které jsou ve své podstatě
binárními (např. text)
 teoreticky možné použít i více prahů
6.1.2. Edge linking
Postup:
 pustí se hranový detektor, který vrací hodnoty gradientu (např. Sobell)
 poté se to oprahuje, aby zůstal jen vysoký gradient
 pak to pomocí morfologických operací „vyčistím“ od izolovaných bodů nebo malých
hran
 začnu od nějaké náhodné hrany a jdu po ní třeba okénkem 3x3, když dojdu na konec,
zkoumám okolí. A jestliže je ve stanoveném okolí (třeba 5pix) nalezena další hrana,
spojím ji s předchozí a pokračuji po ní
 není garantované, že úseky budou uzavřené
 navíc, co dělat, pokud:
o najdu více pokračování
o hrana se najednou rozdvojuje
 díky špatným výsledkům se to moc raději nepoužívá
6.1.3. Region growing
Častěji používané – lepší výsledky.
 detekce bodů, které jsou s vysokou pravděpodobností uvnitř objektů (oblastí)
o to se udělá tak, že se vezme nějaký hranový detektor – výstup se pak oprahuje
vysokým prahem
o a vyberu body, kde není žádná hrana
 tyto body nazýváme zárodečné = seed points

prohledává se okolí toho bodu – testuje se kritérium homogenity (nejjednodušší
způsob je testování úrovně šedi)
 pokud je kritérium splněno, přidám bod do oblasti a pokračuji s jeho okolímˇ
 možné odlišnosti:
o kritérium homogenity – úroveň jasu nebo barev, textura
o způsob prohledávání okolí bodů
V současnosti:
 funkcionál, v jehož minimu je fce, která aproximuje původní jasovou fci funkcí po částech
konstantní
 minimalizační úloha
6.2.popis oblastí
Přesně nevím, co tím JF myslí – příznaky jsou samostatná otázka.
6.3.základy matematické morfologie
Jde o matematický nástroj pro předzpracování i segmentaci obrazů. Podle toho s jakými
obrázky pracuje, mluvíme o binární nebo šedotónové morfologii.
Minkowského součet (Hermann Minkowski 1864-1909, geometrie čísel 1889)
Minkowského rozdíl (pojem zavedl až H. Hadwiger 1957)
Dvě základní operace:
6.3.1. eroze
Skládá dvě množiny pomocí Minkovského rozdílu.
Pro každý bod obrazu p se ověřuje, zda pro všechna možná p + b leží
výsledek v X. Pokud ano, je výsledek 1, jinak 0.
Laicky: Projíždím celý obrázek a obarvuji středovým bodem jen tehdy, pokud
je celé kolečko uvnitř.
Objekty menší než strukturní element vymizí (např. čáry tloušťky 1).
Eroze se používá ke zjednodušení struktury (rozložení objektu na jednodušší části).
6.3.2. dilatace
Sčítá dvě bodové množiny. Jde o duální morfologickou transformaci k erozi.
Dilatace se používá k zaplnění malých děr a úzkých zálivů v objektech.
Zvětší původní velikost objektu. Má-li být velikost zachována, potom se
používá dilatace s erozí, viz níže.
6.3.3. otevření (opening)
Eroze následovaná dilatací.
Pokud se obraz X nezmění po otevření strukturním elementem B, říkáme, že
je otevřený vzhledem k B.
6.3.4. zavření (closing)
Dilatace následovaná erozí. Zaplňuje díry menší než B.
Pokud se obraz X nezmění po uzavření strukturním elementem
B, říkáme, že je uzavřený vzhledem k B.
7. okruh – Degradace obrazu a jeho modelování:
 ,  … PSF (point spread function) – charakterizuje zobrazovací systém
 =  + 
  ,  =  ∗  ,  +  , 
jedná se o lineární, polohově invariantní model. Tedy, že rozmazání je konstantní po celém
obrázku. Toto je příliš velké omezení pro 3D scény, kde se rozmazání mění s hloubkou
ostrosti.
Ideální PSF je delta funkce.
Rozlišujeme dva „problémy“:
 šum a rozmazání působí na hodnoty jasu – Radiometrický inverzní problém
 transformace souřadnic působí na polohu pixelů – Geometrický inverzní problém
(bude probírán v okruhu 8)
Řeší se odděleně.
7.1.1. Radiometrický inverzní problém
Jde o zjednodušení – podmínky: musí být statická a rovinná scéna.
 ,  =  ∗  ,  +  , 
Tři možnosti:
 známe impulsní odezvu (PSF):
Lze ji získat třeba vyfocením bodu -  ∗  =  >> výstup je PSF
Pokud to je možné, tak se to používá. Mám-li k dispozici pouze snímek, tak na něm naleznu
něco, co odpovídá obrazu ideálního bodu. V praxi to moc nefunguje (snad jen v astronomiii).
Pokud znám h a zanedbám šum, tak stejně výraz  =  ∗  není přes konvoluci moc dobře
řešitelný. Díky tomu, že inverzní konvoluce není dobře definovaná (ve spojité oblasti –
integrální rovnice; v diskrétní oblasti – soustava lineárních rovnic pro každý pixel). Tedy dá
se to, ale nepoužívá se to.


V praxi se použije FT:
 =∙
=>
=
=>
 = − 
Dále viz Inverzní [7. 2.] a Wienerův [7. 3.] filtr

známe ji jen částečně – třeba jak rozmazání vzniklo [7. 4.]
 impulsní odezva není známa – provádí se tedy slepá dekonvoluce
Pokud neznám nic a mám jen jeden obrázek, je to téměř ztracený boj.
 =∗
neznám ani f ani h
Navíc h se může skládat z dílčích:  =  ∗  ∗  … ∗ 
A stejně tak f:  =  ∗  ∗  … ∗ 
I kdybychom tedy měli dobrý algoritmus na rozklad g na konvoluci dvou fcí, tak by nevěděl,
jak přesně zkombinovat ty dílčí části jednotlivých fcí.
Mám-li více obrázků téže scény, šance se zvyšují (vícekanálová slepá dekonvoluce), protože
se sníží počet neznámých. Je zde tedy předpoklad, že se f nemění.
7.2.Inverzní filtr
Pro zopakování:
 =∙

=>
 = −
 
=∙+ ≫ = −
 
=>
=



Z této rovnice je vidět, že zanedbáváme člen −  .
Tento člen ale dosahuje obrovských hodnot, takže
tyto metody dávají velmi špatné výsledky při
použití u zašuměných obrázků.
Tady je důkaz: Jako impulzní odezvu mějme
standardní gaussovu funkci
 ,  . Její
fouriérova transformace je opět gaussova funkce.
Šum bereme libovolný, například takový, že jeho
fourierův obraz je konstantní funkce (ale není podmínkou, bereme jen pro jednoduchost). A
protože gaussovka jde pro velké x k nule, tak její převrácená hodnota jde k nekonečnu a to
násobené nějakým nenulovým šumem je zase velmi velké číslo (viz obrázek vpravo). Z toho
plyne, že je při výpočtu zanedbán velmi významný člen. To je také důvod, proč se inverzní
filtr moc nepoužívá. Místo něho se dá aplikovat na zašuměný obrázek Wienerův filtr [7.3.],
který dává daleko lepší výsledky.
7.3.Wienerův filtr
Tento filtr byl navržen tak, aby dokázal zpětně rekonstruovat obrázek, který byl poničen
šumem nebo špatnou impulzní odezvou snímacího zařízení.
Tedy motivace: dekonvoluce robustnější vůči šumu
Podmínky odvození filtru:
 Střední hodnota druhé mocniny přes všechny realizace šumu a pro jejich všechny
parametry bude mít od hledaného obrázku minimální vzdálenost. Tedy, že získaný
odhad má mít minimální odchylku od originálu:
 ´ −  2 →  (střední kvadratická chyba)
E…střední hodnota
f´…odhad
f…originál
 má to být lineární filtr, tedy to má být násobení ve frekvenční oblasti:
´ =  ∙ 
G… je zašuměný obrázek
R…je transformační matice, jež násobením transformuje poškozený obrázek do jeho
"opravené" varianty
Z předchozích požadavků byl odvozen následující filtr, který po vynásobení (jedná se o
násobení matic po prvcích) s maticí poničeného obrázku dá rekonstruovaný obraz:
1
 ,  2
 ,  =
∙
 ,   ,  2 +  ,   , 
V tomto vzorci  ,  značí fouriérův obraz impulzní odezvy  ,  a podíl
 ,   ,  je jen jiný zápis SNR, což nám určuje míru zašumění obrázku.
Vidíme, že tento výraz obecně závisí na parametrech frekvence ,  . Ale za předpokladu
bílého šumu můžeme  ,  psát jako rozptyl šumu 2 (což je konstanta v celém obrázku),
dále budeme předpokládat nekorelovanost obrázku (což v reálu neplatí, ale jako přiblížení se
to dá použít) a můžeme tedy  ,  aproximovat rozptylem obrázku 2 . Z tohoto přiblížení
nám vyjde, že podíl  ,   ,  máme roven konstantě (číslu) 2 2 . V praxi to
znamená, že za tento podíl dosazujeme různá čísla (např. od 0.001 do 1000) a koukáme, co
nám dá nejlepší výsledek. Když Wienerův filtr aplikujeme na nezašuměný obrázek (tedy
 ,  bude rovno nule), pak nám tento filtr  ,  přechází v  ,  = 
1
,
, což je
předpis pro inverzní filtr.
7.4.odstranění základních typů degradací
7.4.1. rozmazání pohybem
Rozmazání vzniklo tím, že se během expozice
hýbe objekt, nebo samotný snímací systém. Bod
se tedy rozmaže na úsečku.
Jde o 1-D obdélníkový puls, který je orientován ve směru pohybu. Kolmo
na směr pohybu je delta funkce.
 
 =   . Fce   =  je vlastně tlumená sinusovka, jak jde
vidět z obrázku.
7.4.2. defokusací (špatné zaostření)
Z bodu se stane kolečko. Jde tedy o válec.
 
 =  .   je tzv. Besselova fce.
Jak tyto degradace odstranit?
Podíváme se do spektra poškozeného obrázku.
Najdeme zde nulové množiny, které detekujeme:
 pohyb – čáry odpovídají nulovým bodům sinc fce
 rozostření – soustředné kružnice – odpovídají nulovým bodům
Besselovy fce
Na základě jejich detekce můžeme odvodit parametry rozmazání a dále
použít Wienerův filtr.
Pozn.: Čím rychlejší pohyb nebo větší rozostření, tím jsou čáry nebo kružnice hustší (blíž
sobě).
8. okruh – Geometrická registrace (matching) obrazů:
Model geometrického zkreslení obrazu lze zapsat jako:
 =  
Máme-li snímek téže scény z různých pohledů (tj. s jiným geometrickým zkreslením) a
potřebujeme-li zjistit odpovídající pixely (tedy, aby stejné pixely měli stejné souřadnice),
mluvíme o Registraci obrazu (Image Registration). Nepřesná registrace vede na chybnou
detekci resp. zjištění změn, tam kde nejsou.
Registrace se provádí pomocí řídících bodů (control points). Pokud jsou řídící body správně
nalezeny, je možné sestavit geometrické transformace a snímky zregistrovat.
Kategorie registrace obrazu:
 Different viewpoints – multiview (vícepohledový)
 Different times – multitemporal (vícečasový)
 Different modalities - multimodal (multimodální)
 Scene to model registration (Scéna k modelu registrace)
Model geometrického zkreslení obrazu lze zapsat jako:
Postup se provádí čtyřmi kroky:
1. vyberou se kandidáti na řídících body – požadavky:
 musí jít dobře automaticky detekovat
 jsou stabilní
 musí jich být dostatečný počet
 měli by být rozmístěny pokud možno po celém snímku
 musí být invariantní k transformaci – z tohoto hlediska nejvíce vyhovují právě
ty těžiště uzavřených oblastí
V tomto prvním kroku se vybírají zvlášť na referenčním obrázku a zvlášť na
registrovaném obrázku.
Jsou to většinou rohy, těžiště uzavřených oblastí nebo extrémní křivosti křivek.
2. Naleznutí korespondence mezi kandidátskými body v obou obrázcích a vybrání
z nich řídících bodů:
 mnoho technik, jak toto provádět
 zde je hlavní teoretický problém
techniky dělíme:
 signálově závislé – pracují s barvami obrázku
o Obrazová korelace:
Kolem kandidátního bodu se vezme okolí velikosti
nějakého okna a spočtu korelace se všemi možnými
polohami tohoto v druhém obrázku
Jen pro zopakování:
rozptyl…  = ( − )2
kovariance…  ,  = (  −   −  )
(,)
korelace… ,  =
=0…pokud jsou nekorelované
  ()
max. = -1, 1
pokud =1…X je násobkem Y
Obrázky se považují za realizace náhodné veličiny:
, −  , ∙ ( − ())
 ,  =
, −  ,
2
∙ ( − ())2
U této metody, se většinou nedetekují ŘB v druhém obrázku, ale hledají se nejvyšší
korelace vzhledem k ŘB prvního obrázku. Nejčastěji hledám malý výřez na velkém
obrázku. Hodnoty intenzit se liší pouze lineárně.
V této podobě se metoda tolik nepoužívá, protože je výpočetně časově náročná a
maximum bývá někdy „ploché“.
Proto modifikace: korelace hran, rohů, korelace ve frekvenční oblasti (fázová
korelace), pyramidal representation (viz níže)
o Jiná míra podobnosti než korelace:
Ne 2 norma, ale 1 norma – např.: , −, →  Výpočet je velice rychlý,
protože suma neklesá, pouze roste – pokud jsme ve špatné poloze, tak velice rychle
přeroste nějakou předchozí hodnotu a můžu ten výpočet zastavit.
Dnes spolu s fázovou korelací nejpoužívanější.
o Rozšíření na obecnější transformace:
rotace – natáčení, okénko je kruh. Výpočetně velice
náročné. Dá se nejdříve projet prostým posunutím, tam
kde to zjistí maximum, tak to začnu natáčet. Vyberu
úhel natočení, kde to je maximální. A poté projedu opět
celý obrázek s tímto natočením.
o Pyramidální reprezentace:
Prostě snižuji o dvojnásobek rozlišení obrázků –
začínám pak na nízkém rozlišení, kde najdu „nadějné
body“ a u vyššího rozlišení počítám jen v okolí těchto
bodů.
o Fázová korelace:
Fáze FT (když zahodíme amplitudy=spektrum se vydělí amplitudami) je blízká
hranám obrázků. Ty jsou výhodnější kvůli nezávislosti na barvách a mají menší
prostorovou korelaci. Nevracíme se hned do obrazové oblasti pro počítání korelace,
ale zůstane se ve frekvenční, kde se využívá Fourier Shift Theorem (FST):
() → ( − )…amplituda je u obou stejná, ale fáze se posune o 22
Cross-power spektrum:
 ∙ ∗
=  −2  +
∙
vyplývá z předpokladu, že obrázky jsou stejné jen posunuté (FST)
F… Fourier originálního obrázku
F*… komplexně sdružený
W… Fourier okénka w
a,b… neznámé parametry posunu
Provede se IFT:
  −2  + = ( − ,  − )
Výpočet je rychlejší a robustnější vůči nelinearitám
V praxi asi nejpoužívanější.

signálově nezávislé (Příznakové metody)
o Kombinatorické (grafové):
Využívá globální informace o kandidátních bodech a jejich vzájemné polohy. Z níž hledá
jejich korespondenci. Zkouší všechny možné kombinace a hledá tu nejlepší – jde o
minimalizaci fce.
o RST (rotation, scaling, translation)
Libovolnou úsečku můžeme namapovat na libovolnou úsečku. V základním případě se každá
dvojice bodů namapuje na každou dvojici z druhého obrázku.
Tedy že namapujeme úsečku a podle ní transformujeme ostatní body a koukáme se, kolik
bodů se shoduje se vzory – počítání zásahů. A pokud toto uděláme pro všechny dvojice bodů,
můžeme pak říci, že ta transformace, která má nejvíce zásahů, je ta správná.
3. Odhadnutí modelu transformace souřadnic
 dobře známá úloha
 jedná se o transformaci, která řídící body promítne na stejné místo
Mějme transformační fce:
 =  , 
 =  , 
Tato transformace může platit pro celý obrázek (globální transformace), nebo jednotlivé dílčí
části můžou mít odlišné transformace (lokální).
o Affiní
’ = a0 + a1  + a2 
’ = b0 + b1  + b2 
 zobrazuje čtverec na rovnoběžník
 zachovává přímky a jejich rovnoběžnost
 Nutné tři body pro její určení. V praxi se ale
počítá z mnohem více bodů, pomocí metody nejmenších čtverců.
 affiní model je jeden z nejjednodušších, ale přesto se hojně používá
o Projektivní
’ = (a0 + a1  + a2 ) (1 + c1  + c2 )
’ = (b0 + b1  + b2 ) (1 + c1  + c2 )
 Jde o obecnější transformaci , pokud ale
pozorujeme předmět z větší vzdálenosti (c1 a
c2 budou zanedbatelně malé), můžeme ji aproximovat transformací affiní.
V praxi se při transformacích ani projektivní nepoužívá, protože nevede na
lineární soustavu a nejde ji nějak „rozumně“ řešit.
 Vystihuje promítání rovinných předmětů fotoaparátem.
 čtverec zobrazuje na jakýkoli čtyřúhelník
 nutné čtyři body
o Nelineární transformace
 = a0 + a1  + a2  + a3  + a4  2 + a5  2
 = b0 + b1  + b2  + b3  + b4  2 + b5  2
 Tento model je silně nelineární, nezachovává přímky ani rovnoběžnost.
Používá se často.
4. Vlastní transformace:
 zabírá nejvíce výpočetního času
 musí se převzorkovávat, protože nové pixely mají neceločíselné souřadnice
Forward
Backward
Také se používá interpolací (nejbližší soused, lineární, kubické).
Pro doplnění:
o Lokální transformace
Obrázek rozdělíme na trojúhelníky pomocí řídících bodů. Na každém trojúhelníku pak
počítám affiní transformaci. Nemá spojité derivace a řeší se pomocí kubické transformace
s 10 parametry, kde se předepíší spojitosti derivací.
Nejčastěji se používá TPS (Thin-Plate-Splines): hledá se minimální křivost plochy ideálně
neformovatelného ocelového plátu fixovaného v řídících bodech.
9. okruh - Základy příznakového rozpoznávání:
Rozpoznávání je rozhodování, jestli objekt patří do dané třídy. Objekt je popsán množinou
příznaků (n-D vektor v metrickém prostoru).
9.1.klasifikátory s učením a bez učení


rozpoznávání řízené (s učením) – pro každou třídu je k dispozici množina
reprezentantů (trénovací množina)
rozpoznávání neřízené (bez učení) – nemáme ani trénovací množinu, ani nevíme
kolik je tříd. Musíme tedy z dat zjistit, jestli tam je nějaká podobnost mezi objekty a
jestli tam mohou být nějaké skupiny a kolik jich asi tak je (viz Shluková analýza
[11.1.]).
Trénovací množina:
 reprezentativní – obsahu typické vzorky dané třídy, všechny hlavní tipy, neměli by
tam být jiné vzorky
 dostatečně velká – k podchycení vnitřní variability
 měl by ji sestavovat odborník v dané oblasti
Musíme si dát pozor na přetrénování (overtraining), abychom při zkoušení nerespektovali
přespříliš trénovací množinu. Klasifikátor by sice fungoval bezchybně na trénovací množině,
ale v praxi by nešel použít. Proto není nutná podmínka
dobrého klasifikátoru, aby bezchybně rozpoznával
trénovací množinu.
Příznakový prostor:
Třídy by měli být dostatečně daleko od sebe, nesmějí se
v žádném případě překrývat. Klasifikátor definuje
nadplochy (o dimenzi menší, než je prostor) a každá se
ztotožní s jednou třídou.
Problém spočívá ve správné definici oblastí. Definovat
klasifikátor znamená správně definovat rozhodující
křivku. Pro každou množinu je možné nadefinovat mnoho různých klasifikátorů s různou
úspěšností, úkolem bývá vybrat ten nejlepší.
Formální definice klasifikátorů:
Každá třída je charakterizována diskriminační fcí (). Klasifikace = maximalizace ().
9.2.NN-klasifikátor
NN = nejbližší soused (nearest neighbor)
() = 1/ (, )
Extremně citlivá na chyby v trénovací množině, a na extrémy. Můžeme to modifikovat tak, že
budeme brát nejbližší vzdálenost k těžištím množin, ale to zase nerespektuje jejich tvar ani
počet prvků. Pokud mám více tříd, ve kterých je vždy jen jeden bod, vznikne mi taková
mozaika – Voronojovi polynomy. A pokud budu chtít rozdělit plochu do trojúhelníků
podobných rovnostranným, používají se Delonejova triangulace.
Modifikace k-NN – jde o to najít k-prvních bodů jedné třídy.
Popis algoritmu: hledám nejbližší bod a udělám k němu čárku, poté hledám další nejbližší bod
a opět k němu udělám čárku >> opakuji do té doby, než získám k-čárek pro jednu třídu.
Jak správně volit k?: řádově menší než počet prvků v trénovací množině (většinou 2-5).
Algoritmy se liší způsobem výpočtu vzdáleností a optimalizací.
9.3.lineární klasifikátor
Mezi dvěma třídami vždy jen jedna hadrovina – přímka, žádná lomená čára. Lineární
rozdělení usnadňuje hledání hranic, ale nemusí to být správně.
Jak hranice najít?
 začnu osou mezi dvěma body z různých tříd, pak přidávám další body o když padají na správnou stranu, nic s přímkou nedělám, začnu ji posouvat a
naklánět teprve, až se trefím na špatnou stranu
o lepší je ale upravovat přímku vždy, i když padají nové body na správnou stranu
(např. minimalizace rozdílu středních vzdáleností od přímky)
 SVM (support vector machine)
Snaží se konstruovat 2 rovnoběžné hadroviny tak, aby separovali třídy a byli co nejdále od
sebe. Body, které takovéto hadroviny protnou, se nazývají support vector. Vlastní
rozhodovací nadrovina je s nimi rovnoběžná a vede mezi nimi.
Nevýhody:
o support v. jsou většinou extremální body
o nezohledňuje počty v množinách – to se dá napravit, tak že rozhodovací
přímku posunu v poměru k té množině, kde je více prvků
o často nemusí existovat dvě rozdělující přímky, pokud nejsou třídy lineárně
separovatelné
o programování je náročné, protože se musejí prozkoušet všechny možnosti
Pokud nejsou třídy lineárně separovatelné, může se zavést transformace. Nebo někdy stačí jen
přidat jeden příznak – ale na to pozor (prokletí dimenzionality) – zvyšování počtu příznaků,
bez přidávání dat vede k vyšší nestabilitě a menší
přesnosti.
9.4.rozhodovací stromy
Používají se tam, kde je těžké určit metriku.
Kořen stromu je vstupní neznámý prvek a listy
jsou jednotlivé třídy. Každý rozhodovací strom
se dá přepsat do binárního. Trénování spočívá
v sestavování stromu a nastavování podmínek.
Při reálných příznacích se rozhoduje na základě
nerovností.
Rozhodovací hranice = hyperkvádry v prostoru.
10.
okruh – Bayesův klasifikátor:
10.1.
základní princip
Jedná se o statistický klasifikátor – vrací pravděpodobnosti všech tříd.
Založen na Bayesově pravidle o podmíněné pravděpodobnosti –
  =
   ()
()
jinak podmíněná pravděpodobnost:    =
(∩)
()
Bayesův klasifikátor:
   ( )
()
   … podmíněná pravděpodobnost v třídě – že ve třídě  se může vyskytnout X
( ) … pravděpodobnost i-té třídy v Ω (v reálu)
   … pravděpodobnost, že na prvku ze třídy i můžeme naměřit vektor x
  = =1    ( ) … celková pravděpodobnost
   =
Chceme maximalizovat    , ale ve skutečnosti maximalizujeme    ( ) a
jestliže jsou všechny apriorní pravděpodobnosti stejné, maximalizujeme jen    .
Pro srovnání s diskriminační fcí:
  =     
často jsou pravděpodobnosti exponenciální:
  =     +   
10.2.
metody určení hustoty pravděpodobnosti
  :
 odhad z předchozích studií o výskytu ve skutečnosti – např. statistika výskytu písmen
v textu
 odhad na základě výskytu v trénovací množině – použitelné jen někdy
1
 předpokládám stejnou pravděpodobnost   =  ∀ ∈ , kde n je počet tříd
   :
 předpokládáme normální rozdělení tříd (parametrický odhad – viz [10.3.]) – fitujeme
gaussovkou – ale pozor ne vše má normální rozdělení!!
 neparametrický odhad
Pokud tedy nejsou třídy normálně rozděleny, máme tyto možnosti:
o Pokud uvnitř těchto tříd leží nějaké „shluky“ s normálním rozdělením >> použijeme
Gaussovskou směs: což je konečná suma Gaussovek - 
  () - jednotlivé
Gaussovky jsou tzv. komponenty a je těžké určit kolik těch komponent ve skutečnosti
je – čím více jich je, tím menší jsou odchylky – extrémem je, jedna Gaussovka pro
jeden bod. Používá se často.
o Pokud víme, jaké je to rozdělení, postupujeme stejně jako u normálního rozdělení,
tedy parametrickým odhadem. Moc se nepoužívá.
o Nepředpokládáme žádné rozdělení, jen hledáme hustotu pravděpodobnosti – to jsou ty
neparametrické odhady.
Neparametrický odhad:
Pravděpodobnost, že se veličina vyskytne v intervalu I je integrál přes tento interval –
=
  

Pravděpodobnost odhadnu podle četnosti výskytů v daném intervalu –
 
≈

 … počet v intervalu
 … celkový počet
 … velikost toho intervalu

Budu posouvat interval jako při konvoluci a za odhad budu brát  ve středním bodě toho
intervalu.
Postup můžeme zdokonalit tím, že budeme body v intervalu vážit nějakou fcí, protože
předpokládáme, že body ve středu intervalu jsou důležitější, než ty na jeho okraji. Tyto
váhové fce se nazývají Parzenova okna. Integrál přes tyto okna se musí rovnat jedné.
Vliv rozptylu na výsledný odhad:
 delta fce – shodné s původními daty, je to náchylné na přetrénování – skutečná hustota
tak s vysokou pravděpodobností nevypadá
 široké – velmi vyhlazené, až konstantní – ani tak skutečná hustota většinou nevypadá
 optimální – něco mezi – není jasné jak to najít
- s rostoucím počtem bodů v trénovací množině vliv okna klesá, až nakonec při  = ∞
nehraje roli
- tím, že jsou neparametrické odhady závislé na velikosti množin a tak i náchylné k chybám,
používají se až jako poslední možnost
10.3.
rozbor pro normálně rozložené třídy
Nejprve je dobré provést test normality –
 Pearsonův test – někdy se označuje jako test dobré shody nebo  2 test
o dáme data do grafu a zároveň v grafu nafituji normální rozdělení
o vypočítáme rozdíly ∆ a pak


1

2
 ∆
=1 

>> to má  2 rozdělení a tím testuji
hypotézu, že data mají normální rozdělení (podívám se do tabulek na 5%
hranici a buď to příjmu, nebo odmítnu)
Momentový test – nafituji data opět normálním rozdělením a spočítám momenty toho
fitovaného a skutečného a porovnám nějakou statistikou
o p-tý moment = ∫   ()
 1. moment – střední hodnota
 2. moment – rozptyl
 3. moment – šikmost
Pokud potřebuji testovat normalitu pro více rozměrů je to velmi komplikované, proto
se provádí jen test pro každý rozměr zvlášť a pak se řekne, že pokud to je normální ve
všech rozměrech (příznacích), pak to je normální i celkově. Což ale nemusí platit.
Parametrický odhad Gaussovky:
1
 střední hodnota (aritmetický průměr) –  =   =1 
 rozptyl (aritmetický průměr kvadratických odchylek) 1
 2 =   =1 ( − )2

  =
1
2 
1 − 2

 −2

1
D-dimenzionální Gauss:   =
2

2

1
2

1
− −   −1 −
2

o  … počet dimenzí
o  … vektor střední hodnoty (= vektor aritmetických průměrů)

o
… transpozice vektoru
o  … kovarianční matice
o
… determinant
 = ( ,  ) na diagonále má  = 2

 = 
1



 =1(
−  )( −  ) , kde  je počet
bodů v dané třídě
Velikost kovarianční matice je závislá na množství prvků.
2 0
Např.: 1
, pokud 1 = 2 , tak to jsou soustředné
0 22
kružnice.
Jak vypadají rozhodovací křivky ve 2-D:
Jsou tam, kde se gaussovky rovnají a jsou to:
 hyperboly
 kružnice a elipsy
 přímka – jiná střední hodnota, jinak jsou stejné
 dvě přímky – mají stejné rozptyly a střední hodnoty
 Nutná a postačující podmínka proto, aby klasifikátor byl lineární je, aby kovarianční
matice byly stejné.
1
Kdy je    = − 2  −    −1  −  ? – tehdy, když je Mahalanobisova vzdálenost
minimální –   −    −1  − 
Pro více tříd se postupuje stejně, jen je více rozhodovacích čar.
Maximum Likelihood – Bayesův klasifikátor, kde jsou třídy normálně
rozděleny a apriorní pravděpodobnosti jsou stejné.
11.
okruh- Klasifikace bez učení:
11.1.
Shluková analýza (clustering) v prostoru příznaků
Neznám trénovací množinu a většinou ani počet tříd. Dostaneme
jen naměřená data a na jejich základě máme odhadnout počet
tříd.
Shluk = není přesně definován, ale znamená zhruba to, že
rozptyly parametrů ve shluku jsou „malá“ a naproti tomu
vzdálenosti jednotlivých shluků jsou „velké“. V praxi můžeme za
shluk považovat jakoukoli libovolnou podmnožinu a proces
shlukování lze pak přirovnat k pokrytí celé množiny disjunktními
podmnožinami.
Můžeme tedy nalézt různá shlukování a porovnávat, které je
nejlepší.
2
Jednoduché Wardovo kritérium:  = 
… suma přes prvky daného i-tého
=1  ∈  − 
shluku, kde druhá suma je až na normování klasický rozptyl a  je těžištěm i-tého shluku.
Hledáme tedy minimum .
Lze použít jen tehdy, srovnávám-li pevný počet shluků s různými rozděleními. Globální
minimum  je počet shluků = počet prvků.
Metody hledání shlukování:
1) Iterační [11.2.]
2) Hierarchické [11.3.]
3) Ostatní – kombinace předchozích, sekvenční
Sekvenční:
Jedná se o velmi špatnou metodu, která se v praxi nepoužívá.
Postup –
1) vyberu si libovolný bod
2) přidám k němu nejbližší
3) testuji rozptyl vytvořeného shluku, a pokud nepřekročí zadanou mez, skočím do bodu
2), pokud ji překročí, pokračuji v bodu 4)
4) ukončím jeden shluk, a pokud mám ještě nezařazené body, vyberu z nich libovolný
bod a pokračuji bodem 2)
Dává sice špatné výsledky, na druhou stranu je velice rychlá, protože je každý bod
zpracováván jen jednou. Výsledek závisí na výběru bodů.
11.2.
iterační metody
N-Means Clustering
1) Náhodně zvolíme N bodů, které jsou rovnoměrně rozloženy, a označíme je za těžiště
shluků.
2) Zbylé body rozdělíme do shluků podle nejkratší vzdálenosti k těžišti.
3) Nyní přepočítáme těžiště vzniklých shluků.
4) Pokud jsou jiná než předchozí >> oklasifikujeme všechny body znovu (i ty původní
těžiště)
5) Tím vzniknou opět nové těžiště, které spočítám. Pokud se znovu nerovnají, opakuji
bod 4).
6) Pokud se už nemění a jsou stejná, prohlásím to za konečné rozdělení do shluků.
Je to poměrně rychlé, ale pokud na začátku odhadneme špatně počet shluků, tak je i výsledek
špatně. Špatné je, že to neminimalizuje .
Iterativní minimalizace J
1) Počáteční inicializace je výstup N-means clusteringu.
2) U každého bodu testuji, jestli by se  nezmenšilo, pokud bych ho přiřadil do jiného
shluku. A tam kde je největší pokles J, tak bod přeřadím. A pokračuji s dalším bodem.
3) Algoritmus se zastaví, pokud se body přestanou přesouvat.
Pozn.
 Všechny těžiště se nemusí přepočítávat, když vím, který bod se přesouval a kam. Ve
shluku, kde se nic nedělo, to není potřeba.
 Někdy i toto vyjde špatně, protože minimum  preferuje shluky se stejným počtem
bodů, což může být někdy na škodu.
ISODATA
Jde také o iterační metodu, kde se N může měnit. ISODATA je komerční ochranná známka.
11.3.


hierarchické metody
Aglomerativní
–
počátečním
předpokladem je, že každý bod je sám
shlukem a v pak v každém kroku spojím
dva shluky.
Divizivní – na počátku jsou všechna data
v jediném shluku – to se používá jen pro
menší počet konečných shluků (2).
Postup aglomerativní metody:
1) každý bod je shluk
2) spojím 2 nejbližší body
3) v každém dalším kroku hledám 2 nejbližší shluky a ty spojím
4) opakuji do dosažení nějaké podmínky
Různé metody se liší podle STOP podmínky – počet shluků, velikost, rozptyl.
Vzdálenost shluků:
 minimální vzdálenost mezi nejbližšími body – bude spojovat blízké shluky (veliké)
 max. vzdálenost nejvzdálenějších bodů – stejně velké shluky
 střední vzdálenost těžišť
Ačkoli ani jedna není metrikou, tak se hojně používá. Metrikou je třeba Hausdorfova - pro
všechny prvky A se spočítají vzdálenosti k nejbližšímu sousedu v B a vezme se maximum.
Takovýto model neminimalizuje , ale můžeme to modifikovat takto:
 je na počátku = 0, v každém kroku budu spojovat takové shluky, aby nárůst byl  minimální.
min  ,  =   ∪  −  , 
Nedostatek – opět nenalezne globální minimum. A
navíc není dobře definováno co se stane, když se
v jednom kroku nalezne více kandidátů na spojení.
>> Definitivní Aglomerativní Spojování – pokud je
více kandidátů v jednom kroku, spojím všechny.
Používá se i grafické znázornění Dendrogramem,
který je užitečný pro určení počtu shluků.
Postup divizivní metody:
1) všechny body tvoří jeden shluk
2) rozdělím shluk na dvě části, aby jejich vzdálenost byla maximální
3) opakuji až do konce (počet shluků = počet bodů)
– dost výpočetně náročné, protože je nutné vytvořit všechny možné dvojice podmnožin a
spočítat jejich vzdálenosti - 2 2
– proto se to musí obcházet:
1) všechny body tvoří jeden shluk
2) najdu bod, jehož průměrná vzdálenost od ostatních bodů je maximální – ten považuji
za „zárodek“
3) Pro každý bod spočítám střední vzdálenost mezi množinou A (všechny ostatní body) a
zárodečným bodem B
4) je-li blíže k B, než k A, tak ho přidám k B
5) tím se vytvoří dvě množiny, na něž aplikuji rekurzivně to samé
Optimální počet shluků:
- je ve zlomu fce
- zlom existuje jen při výrazné shlukovací
tendenci
12.
okruh:
12.1.
Redukce dimenzionality příznakového prostoru
Máme  příznaků a chci tento počet zredukovat na číslo , tak aby  ≪ :
(1 2 , ⋯ ,  ) → (1 2 , ⋯ ,  )
Výhody:
 nižší výpočetní náročnost
 někdy zlepšení klasifikace
 levnější
 v medicíně může měření přinášet pacientovi bolest
Nevýhody:
 možná ztráta informace
Dva hlavní přístupy:
1. Feature extraction –
Nové příznaky jsou funkcemi těch starých: Transformace :  → 
např.: n=1 : 1 = =1 
Příznaky ztrácí svůj původní fyzikální význam (někdy to je na škodu, někdy ne).
2. feature selection –
Nové příznaky jsou vybrány z těch starých.
Tento výběr můžeme provádět dvěma způsoby:
a. One class problem:
Máme nerozklasifikovaná data, kde chci redukovat příznaky ještě před
klasifikací – tu nechci ještě před redukcí provádět.
b. Multi class problem:
Máme trénovací množinu, musíme vy brat ty příznaky, které trénovací
množinu nejlépe separují.
Důležité je, že vždy chceme příznaky, které jsou nekorelované.
12.2.
Transformace podle hlavních komponent
Principal Component Transform (PCT) – Karhunen-Loeve
 jde o metodu one-class-problem
 chceme odstranit korelace mezi příznaky
Otázka – ∃ taková lineární transformace, aby nové příznaky byly nekorelované? – Ano:
kovariantní matice je symetrická, tedy i diagonalizovatelná. Protože u symetrické matice jsou
vlastní čísla reálná a počet vlastních vektorů je  a jsou ortogonální (matice je rozměru
). Tyto vlastní vektory definují ty transformace.
PCT je rotace příznakového prostoru –  = , tak aby  bylo nekorelované
 =    
…vlastní ortogonální vektory
Na diagonále budou vlastní čísla (rozptyli nových příznaků).
 Spočítám tedy vlastní čísla, vlastní vektory.
 nyní mám nekorelované příznaky, ale stejný počet jako předtím a až teď přichází ta
samotná redukce
Redukce:
 Seřadíme příznaky podle velikosti rozptylů (tedy diagonálních prvků).

Předpokládáme, že informační hodnota je tím vyšší, čím vyšší rozptyl toho příznaku
je. Vycházíme z předpokladu, že příznak s nulovým rozptylem je konstantní pro
všechny prcky.
 Zvolíme si počet příznaků  a vezmu prvních  příznaků >> to jsou ty hlavní
komponenty.
Aplikace PCT:
1. „Optimální“ reprezentace dat - ∀ příznaky jsou nekorelované a jsou tam jen ty hlavní.
2. Vizualizace a komprimace multimodálních (hyperspektrálních) obrázků – snímky
z družic mají hodně pásem s vysokou korelací,
můžeme tedy tyto korelace pomocí PCT zahodit.
Problém PCT pro klasifikaci – protože vybírá příznaky
podle velikosti rozptylů, což nemusí být dobře pro
diskiminalitu – viz obrázek. Pokud vezmu ten největší
rozptyl není zde to nejlepší.
12.3.
míry separability (diskriminibility)
Multi-class problem –
 tréninkové množiny jsou dostupné zvlášť pro
všechny třídy
 chceme nerukovat příznakový prostor, aby zůstaly
jen ty příznaky, které dobře klasifikují jednotlivé
třídy
 cíl je maximalizovat vzdálenost mezi třídami
o dobrá diskriminabilita
o optimalizace metody – zde nám přechází feature selection v optimalizační
úlohu
2
12.3.1.  = 
…Wardovo pravidlo
=1  ∈  − 
Na rozdíl od shlukování, tady příznaky zahazuji, proto toto kritérium nefunguje.
12.3.2.   −1  - nejpoužívanější pro výběr příznaků:
Jestliže  = 2 a obě trénovací množiny mají stejný počet prvků, potom: máme tzv.
Mahalanobisova vzdálenost mezi dvěma třídami:
  −  ≈ ( –  ) ( +  )− ( –  )
1 – 2 …rozdíl středních hodnot dělený rozptylem
 …kovarianční matice
Pozn.:Mahalanobisova vzdálenost bodu od třídy:
(– ) − (– )
Praktické použití:

, což vede na

mnoho možností a není to příliš použitelné pro velká čísla. Ale přesto pouze toto zaručí
dosažení globálního maxima. Ostatní metody nalezení globálního extrému nezaručí.
M. vzdálenost nelze zobecnit do více rozměrů >> používá se po dvojicích a pak se
maximalizuje ta minimální, protože chceme dobrou separabilitu všech tříd.
Mahalanobisova vzdálenost porušuje metriku (pokud je stejná střední hodnota, tak je
vzdálenost rovna nule.), proto se používá Bhattacharyova metrika:
Mahalanobisova vzdálenost + člen měřící stejnost kovariantním matic
Musíme vzít všechny možné n-tice, spočítat všechny možné možnosti:
12.4.

optimální metody pro výběr příznaků

nepoužívá se

branch & bound - začínáme se všemi příznaky a postupně je odebíráme až na
požadovaný počet 
uspořádám příznaky do stromu
v kořeni je úplný vektor
v každém patře odeberu příznaky podle nějakého počítaného kritérie
dojdu až na konec (k listům) a pamatuji si hodnotu kritéria (M. a B. vzdálenost je
monotónní, takže nemůže při odebírání růst.)
v každé další větvi postupně porovnávám hodnotu kritéria, a pokud je horší,
nemusím dále pokračovat v této větvi
při extrémní smůle je pak složitost horší než u úplného prohledávání >> jen listůje

totiž
, uzlů je pak ještě 2krát více.

fast (predictive) branch & bound – odhadují se velikosti úbytků při odebírání
jednotlivých příznaků a v každém uzlu se tak kritéria nemusí počítat
úplné hledání -








Pro lepší pochopení optimálních metod viz demo: http://ro.utia.cas.cz/dem.html
12.5.
suboptimální metody pro výběr příznaků
Hledají něco, čemu bychom rádi věřili, že to je globálním maximem, ale nemusejí k němu
dojít. Každopádně jsou mnohem rychlejší.
 přímá selekce – tato metoda funguje jen pokud jsou příznaky nekorelované, pokud
jsou navíc jde navíc o množiny s normálním rozdělením, je optimální metodou
o Najdu příznak, který množinu separuje nejlépe, ten si pamatuji a hledám druhý
nejlepší, takto jich najdu  a je to.
o Protože jsou bohužel příznaky většinou korelované, není to moc použitelné.
 zobecnění – sequential forward selection – najdu nejlepší a druhý vyberu tak, aby
tvořil s tím prvním nejlepší dvojici. Problémy:
o nesting effect = zahnízdění – jednou špatně zvoleného příznaku se už
algoritmus nezbaví.
o přidává se po jednom – proto další vylepšení – SFS(k) – kde se vybírá úplným
prohledáváním nejlepší např. dvojice (k=2) a k ní se přidává další nejlepší
dvojice. Což ale neřeší problém nesting effectu.
 zlepšení – plus k minus m – typicky  =  − 1
o v prvním kroku přidám k nejlepších a z těch vybraných zase vyhodím m
nejhorších
 další zlepšení – floating search – stejný jako předcházející algoritmus, ale tentokrát
nejsou m a k konstanty
 oscillating search- nezačíná se od nuly, ale od náhodného výběru
13.
okruh – Příznakový popis rovinných objektů:
13.1.
obecné požadavky
Příznaky jsou charakteristiky, které nezávisí na konkrétních výskytech v obrázku >> nezávislé
na otočení, velikosti, barvě, fontu písma atd.
Měli by tedy být invariantní ke všemu přípustnému, co by se mohlo vyskytnout v dané úloze.
 Diskriminalita – objekty patřící do různých tříd, by měli mít různé hodnoty příznaků
(invariance jde většinou proti diskriminalitě)
 Robustnost – měli bychom zajistit jen malé nepřesnosti; měli by být dosti robustní na
šum
 Efektivnost
 Nezávislost – žádná složka vektoru příznaků není funkce jiných
 Úplné – toto není nikdy zajištěno, ale znamená to, že lze přesně zrekonstruovat daný
objekt z těchto příznaků
13.2.




principy
vizuální
transformační koeficienty
diferenciální
momentové
14.
okruh – Invarianty pro popis a rozpoznávání 2-D objektů:
14.1.
vizuální příznaky
Vizuální proto, že už pouhým okem jde odhadnout, jak velkou
hodnotu bude mít daný příznak. Mají intuitivní interpretaci – jedná se
o plochu, délku obvodu, kompaktnost, podlouhlost atd.
4
 Kompaktnost – 2 …  je plocha a  je obvod
jde o míru podobnosti ke kruhu, kde kruh má hodnotu "1"
()
 Konvexita – ( ) jde o míru podobnosti ke konvexnímu obalu




Elongation (Podlouhlost) – poměr krátké a dlouhé strany >>
míra podobnosti ke čtverci
Rectangularity – jde o poměr plochy objektu a opsaného
obdélníku >> míra podobnosti k obdélníku
Eulerovo číslo – počet komponent mínus počet děr
Vizuální příznaky
předklasifikace.
14.1.1.
se
někdy
používají
jako
Úplné vizuální příznaky
Dají se s nimi zpětně zrekonstruovat objekty.
 Řetězový kód (Chain code) – jde o kódování
směru hranice
určíme si start pixel a pak jednu podle čísel:
Je to nepoužitelné jako příznak – stačí lehká změna hranice a už to je celé jinak. Invariantnost
se dá řešit jednoduchým trikem – udělám jen reaktivní kód (diferenční) – odečtu z absolutního
kódu dvě následující hodnoty (22223>>0001).
Používá se pokud chceme zakódovat objekty, jedná se totiž o bezztrátovou kompresi. Špatně
se u něho definuje vzdálenost (metrika) mezi příznaky.
 Polygonální aproximace – nahrazuje hranici polygonem
Pro rozpoznávání se většinou nepoužívá. Problém zde je, jak určit počet vrcholů polygonu. A
pro dobré srovnání je potřeba, aby byl konstantní počet vrcholů, což ale neodpovídá realitě.
Stejně těžce je zde definovat metriku.
 Tvarový vektor (Shape vector) – v rozpoznávání se používá. Jde vlastně o
převzorkování v polárních souřadnicích.
o najdu bod těžiště
o najdu bod o těžiště nejvzdálenější
o vedu úsečku těžiště >> ten bod a tu nazvu poloměrem kružnice
o udělám kružnici a rozdělím ji na nějaký počet stejně velikých oblastí
Je to invariantní:
 posun – začínáme od těžiště
 otáčení – nalezneme nejvzdálenější bod
 změna měřítka – ano, pokud vektor normalizuji první
složkou
Diskriminalita je dobrá, pokud počet oblastí  je dostatečně velké. Špatné to je, pokud
„paprsek“ protne objekt více než jednou, tak se to nedá použít. Tedy dá se použít jen pro
hvězdicové objekty.
Pokud nastává problém s určením počátečního bodu s maximální vzdáleností, vektor se pak
liší jen posunutím >> řešíme to tím, že projedeme všechna cyklická posunutí a uděláme
korelaci.

zobecnění na Tvarovou matici (Shape matrix) – Stejný
postup jako u shape vector
– zase si naleznu těžiště a nejvzdálenější bod, a vedu
ekvidistantní úsečky z těžiště, ale tentokrát nedělám jen jednu
kružnici, ale více ekvidistantních soustředných kružnic, čím
jednotlivé oblasti rozdělím do více částí.
Tímto postupem dostáváme vlastně binární matici – každý prvek odpovídá jednomu
segmentu. Číslo je rovno "1" pokud je více jak 50% segmentu pokryto objektem. Viz
obrázek, kde  je počet kružnic a  je počet výsečí.
Je dobré, aby se segmenty blížili čtverci.
Metriku zavedeme, tak že je to počet stejných prvků v matici.
Pokud máme opět problém s nalezení maxim, tak se prochází všechny možné matice –
jednalo by jen o cyklické posunutí prvků matice.
Otázka: Proč se nepoužívají kartézské (čtvercové) souřadnice? – Ztrácíme tím odolnost vůči
špatnému nalezení maxima – proto se to nepoužívá.
14.2.
Fourierovy deskriptory
Fourierovy deskriptory patří do skupiny transformačních koeficientů – stejně jako wavelet
transform.
Jsou založeny na Fourier shift teorému (FST), který nám říká, jak vypadá fourierka posunuté
fce – je jen násobkem fourierky té původní.
Amplituda FT se při posunu nemění, fáze se definovaně posouvá.
Zkonstruujeme radiální fci:
Radiální fce je invariantní k –
 posunutí – protože to vztahuji k těžišti tak nemusím uvažovat o posunutí
 rotaci – při ní se bude radiální fce pouze posouvat – tedy nezávisí na startovním bodu
Udělám FT této radiální fce a vezmu její amplitudu – prvních pár jejích koeficientů prohlásím
za ty naše hledané FOURIEROVY DESKRIPTORY.
Abychom zajistili invarianci k měřítku >> dělí se tato sada prvním koeficientem, což je
koeficient konstantní fce – neboli střední hodnota fce:
  =
() −2 
 0 = ∫ ()…střední hodnota
Funguje jen pro hvězdicovité objekty.
Použití:
 Vezmeme hranici a představíme si ji jako komplexní číslo:   =   + ()
 Z toho se spočítá FT a vezmou se ty absolutní hodnoty
 Nultý bod má nyní jiný význam – říká nám vzdálenost od počátku, a proto používáme
až ty další body a tenhle zahodíme.
Pozn.: Ve F. deskriptorech moc informace není – u FT je podstatná část informace ve fázi,
kterou vůbec neuvažujeme.
14.3.
diferenciální příznaky
Používají se pro rozpoznávání objektů, které nejsou celé vidět – do dnes tato úloha uspokojivě
vyřešená. Mozek je v tomto vybaven daleko lépe, díky zkušenosti. Do teď jsme popisovali jen
příznaky, které byly globální, takže lokální změna funkce vedla ke změně všech koeficientů.
IDEA:
 LOKÁLNÍ PŘÍZNAKY – počítají se v částech objektu
 hranice musí být dobře diferencovatelná
 chodíme po té hranici a hledáme vysoké derivace
 příznakový vektor je tvořen hodnotami funkce ve všech hraničních bodech
 protože mi pro výpočet fce stačí malé okolí bodu >>
lokální
 Vypočteme první (I1) a druhou (I2) křivost a z toho
sestavíme tzv. Signaturu:
 Dostanu opět uzavřenou křivku v příznakovém prostoru a
pak porovnávám s databází a musím určit, v kolika % se
může lišit.
 To zakrytí eliminuji tím, že porovnávám jen podkřivky (části té Signatury).
Problémy:
 I když to je invariantní vůči projektivní transformaci, tak to stejně není moc
použitelné, protože je zde nutná podmínka, aby křivky byly hladké a dobře diferencovatelné.
 není to moc odolné vůči šumu – díky vysokým derivacím - NESTABILNÍ
 někdy se to řeší aproximací křivek spliny a pak se to počítá až z nich
 dnes se to používá jako srovnávací metrika a asi neexistuje žádná reálna aplikace
přímo v rozpoznávání
14.3.1.
Jiné možnosti:
Objekt se rozdělí na malé části, u kterých se spočítají
některé z globálních příznaků.
Otázkou je, jak takový objekt rozdělit – např. pomocí
inflexních bodů (  −   = 0). Existují i algoritmy které je
hledají bez počítání derivací. Tyto inflexní body, jsou
invariantní vůči affiní i projektivní transformaci.
15.
okruh – Momenty obrazu:
15.1.
základní definice
Momenty jsou projekcí funkce obrázku do polynomiální báze.
()
Obecný moment  obrázku (, ), kde , ℕ+ a  =  +  je stupeň momentu
()
 =
 ,  (, )

00 ,  , 10 ,  , ⋯ ,  ,  je polynomiální báze funkcí definovaných na D
15.2.
vlastnosti
Geometrický moment:
∞
()

    (, )
=
−∞
()
00 …“hmotnost“ obrázku – pro binární obrázky je to plocha


souřadnice těžiště:  =  10 ,  =  01
00
00
Pokud považujeme obrázek jako hustotu pravděpodobnosti a normalizujeme 00 = 1, tak pak
jsou:
 10 a 01 střední hodnoty
 20 a 02 jsou odchylky středních vertikální a horizontální
15.3.
momenty vzhledem k různým systémům polynomů
Komplexní moment:  ,  = ( + ) ( − )
∞
()

( + ) ( − ) (, )
=
−∞
Vyjádření komplexního momentu z geometrického:


 =
=0  =0
 =

1
2

− + − −
+ ,+−−
 (−1) 



+ 
 =0  =0



−
+ ,+−−
 (−1)
 =  ∗
>> zeptat se JF – úplně nevím, jestli touhle otázkou myslel Legendrovi & Zernikovi? –
jejich formální zápis jsme totiž ke zkouškám z ROZu umět nemuseli…
15.4.
rekonstrukce obrazu z momentů
Teorém jedinečnosti: Funkce obrázku může být přesně zrekonstruována z množiny jejich
momentů.
Obecně u geometrických momentů platí:
 ,  ≠
  (, )
Ale pokud máme Ortogonální momenty:
Je-li polynomiální báze { (, )} ortogonální, tj. pokud její prvky splňují podmínku
ortogonality:
 ,  ∙  ,   = 0
nebo váženou ortogonalitu:

(, ) ∙  ,  ∙  ,   = 0

pro všechny indexy  ≠  nebo  ≠ , mluvíme o ortogonálních (OG) momentech a  je
oblast ortogonality.
Potom se rekonstrukce obrazu z OG momentů provádí takto:
 ,  =
  (, )
 ,
Pokud používáme pouze konečnou množinu momentů, je tato rekonstrukce "optimální",
protože to minimalizuje chybu pomocí nejmenších čtverců. Na druhou stranu, rekonstrukce
obrazu z geometrických momentů nelze provádět přímo v prostorové doméně. Ale provádí se
ve frekvenční doméně, z Taylorova rozvoje geometrických momentů:
(−2)+
 ,  =
   
! !


16. okruh – Momentové invarianty vzhledem ke geometrickým
transformacím obrazu:
Translace = T, Scaling = S, Rotace = R
 invariant k T - centrální geometrický moment
∞
( −  ) ( −  ) (, )
 =

−∞

kde  =  10 ,  =  01
00
00
pozn.:


 =
 =0  =0
01 = 10 = 0
00 = 00



+
    − ,−
 (−1)

invariant k T a rovnoměrnému S – normalizovaný centrální moment

 = 
00
+
kde  = 2 + 1
D.:
∞
′  =
′ −  ′ 
−∞
′ − ′ 
 ′  ′ ,  ′  ′  ′
  ( −  )   ( −  ) (, ) 2  =  ++2 
−∞
′
z toho tedy vyplívá:

∞
=
dále: ′00 =  2 00
potom tedy:

′  ++2 
=  = 2
= 
′00
( 00 )
 + +2
+
= 1 → 2 =  +  + 2 →  =
+1
2

2
 invariant k R –
M.K. Hu, 1962 - 7 invariantů třetího řádu:
Těžko se hledají, ale dají se lehce pozkoušet pokud do nich dosadíme transformační vztahy
pro rotaci:
 ′ =  cos  −  sin 
 ′ =  sin  +  cos 
Problémy:

závislost: 3 =
 52 + 72
 43
 neúplnost
Proto konstruujeme rotační invarianty z kompexních momentů:
∞
()
 = ∬−∞ ( + ) ( − ) (, ), nechť  ≥ 
v polárních souřadnicích:
 =  cos 
 =  sin 
 = 2 + 2
 = arctan  
Dosadíme:
∞ 2
()

 + +1  (− ) (, )
=
0 0
Stejně jako u Fourierova Shift Teorému, otáčení je totiž v polárních souřadnicích posun:
′

=  −(−) ∙ 
fáze je tedy posunuta o ( − ) >> repetition faktor = ( − )
pokud  −  = 1 potom se moment otáčí stejně jako obrázek
Teorém:
Nechť  ≥ 1 a  ,  ,  ∈ ℕ+ , i ∈  a nechť
pak:

=0  (
−  ) = 0


=
  
=1
je invariant k rotaci.
D.:


 ′   
′ =
=1
 − 
=
  −    
   
=  −

=0  
  − 
=
 =1
2
Některé jednoduché invarianty jsou tedy např.: 11 , 20 02 , 20 12
atd.
Teorém nám pomáhá najít nekonečně mnoho invariantů vzhledem k otočení, ale jen pár z nich
je nezávislých.
Otázka je, jak najít bázi – úplnou a nezávislou množinu z těchto invariantů?
Definujme nezávislost invariantů: Nechť  > 1 a ℐ = I1 , I2 , ⋯ , Ik je množina rotačních
invariantů, pak  je na této množině nezávislý, pokud ∄ zobrazení  takové, že  =
 I1 , I2 , ⋯ , Ik .
Definice Báze: Mějme množinu rot. invariantů ℐ = I1 , I2 , ⋯ , Ik . Nechť  ⊂ ℐ.  je
kompaktní, pokud ∀  0 ∈ ℐ  jsou závislé na .
 je báze, jeli kompaktní a nezávislá.
Teorém jak sestavit takovou bázi invariantů požadovaného stupně:
Mějme stupeň  ≥ 2.
Zkonstruujme množinu rotačních invariantů takto:
p −q
 =  p, q ≡ cpq cq 0 p 0 | ≥  ∧  +  ≤ 
kde 0 a 0 jsou libovolné indexy, které splňují podmínky:
 0 +0 ≤ 
 0 -0 = 1
 0 0 ≠ 0
Pro všechny přípustné obrázky.
Potom  nazvu bází všech rotačních invariantů do stupně výšky .
Můžeme tedy tuto bázi nejen spočítat, ale předem znát počet členů  ≔ 
1
  = 4  + 1 ( + 3)…pokud je  liché

1
 = 4  + 2 2 …pokud je  sudé
Př.: Vygenerujte bázi 3. řádu:
 = 3 → 0 + 0 ≤  → tedy 0 , 0 můžou nabývat hodnot od 0 do 3
ale protože 0 − 0 = 1 → 0 = 2, 0 = 1
A tedy konečný výsledek je:
 1,1 = 11
 2,1 = 21 12
2
 2,0 = 20 12
3
 3,0 = 30 12
Kdyby to mělo být úplné, muselo by tam být ještě:
 0,0 = 00
 1,0 = 10 11
Ale není to tam, protože 00 = 00 je většinou
používáno k normalizaci a 10 = 10 + 01 se
používá jako translační invariant.
N-fold rotační symetrie: pokud je zrotovaný
objekt stejný jako původní s rotací 2  pro
∀  = .
Vztah N-fold symetrie k osové:
 má-li osovou symetrii S – má i N-fold a
N=S
 má-li N-fold tak pak:
o nemá osovou
o nebo má a S=N
Proto se můžeme zabývat jen N-fold.
Máme-li symetrický objekt je to problém, protože mnoho invariantů je rovno „0“.
Věta: Pokud (, ) má N-fold rotační symetrii, potom  = 0 pro ∀ ,  takové, že
není integer.
D.:
2
′

=  −(−) ∙  >> úhel aby se rovnal objekt po otočení:  =
′

=  −2 (−)/
−2 (− )/

′


−

∙  >> zároveň musí platit:
=  >> tedy buď  = 0 nebo
= 1 >> protože pokud ( − )/ není integer, tak musí platit  = 0.
Čím vyšší číslo  tím méně netriviálních invariantů.
 = 1 není symetrie >> předchozí řešení
 = 2 (centrální symetrie) >> jen sudé stupně invariantů ( je sudé číslo) jsou netriviální
 = ∞ >> jen  p, p =  jsou netriviální
Zobecnění teorému o bázi pro N-fol symetrii:
 ∀, :  p, q ≡ cpq cqk 0 p 0
  = ( − )/
 + ≤ 
 ≥
 0 +0 ≤ 
 0 -0 = 
 0 0 ≠ 0
o rotační invarianty pomocí normalizace
Nepřevzorkováváme jen pracujeme s normalizací momentů:
′
1) normalizujeme měřítko: 00
=1
′
′
2) normalizujeme posun: 10 = 0, 01
=0
′
3) normalizujeme rotaci podle hlavních os: 11
=0
1
2 11
4) úhel mezi 1. vlastním vektorem a osou  ≔  = 2 arctan  −
20
5)
6)
7)
8)
02
Pokud  neexistuje, tak je to už natočené >>  = ∞ (kruh)
díky tan 2 → 4 varianty natočení: ↑ → ↓ ←
′20 ≥ ′02 preferuje směry: ↓ ∧ ←
′ 30 > 0 preferuje směry: ↓ ∨ ←
momenty po normalizaci jsou invarianty – níže si je spočítáme a dokážeme to:
20 11
D.: Normalizační momentová matice:  ≡ 
02 ,  −  = 0 >> jde o ortogonální
11
matici tvořenou z vlastních vektorů , nazveme jí .
′20
0

0
Pak  ′ =    = 1
=
0 2
0
′02
>> ′20 ≡ 1 =
20 + 02 +
20 − 02
2
2
+ 411
2 = 1 + 2
2
>> ′02 ≡ 2 =
20 + 02 −
20 − 02
2
2
+ 411
2 = 1 − 2
2
Momenty normalizovaného obrázku jsou skutečně invarianty.
Mějme elipsu takovou jako na obrázku –
Ta má stejné 2. momenty jako původní objekt:
3 
′20 =
4
3

′
 02 =
4
,  – major/minor semi-axis
Takovou elipsu nazveme referenční elipsou.
Z toho vyplívá, že jen tyto dva momenty nám dávají málo informace >> je jich potřeba více.
Právě proto, že jsou potřeba momenty vyšších řádů, se normalizace pomocí komplexních
momentů příliš nepoužívá.
17.
okruh – Momentové invarianty vzhledem ke konvoluci:
 ,  =  ∗  , 
(, )…originál
(, )…rozmazaný obrázek
(, )…PSF impulsní odezva
hledáme tedy invariant, takový že:   =   ∗  pro ∀
Pro zopakování komplexní moment:
∞
()
( + ) ( − ) (, )
 =
−∞
Mějme Lemma:
Nechť (, ) a (, ) jsou dva libovolné funkce obrazu a nechť (, ) = ( ∗ )(, ).
Pak (, ) je také funkce obrazu a pro jeho momenty platí:


()
 =
 =0  =0


()
 =
 =0  =0

()


=
 =0  =0
pro ∀, 



() ()
  −, −


 ( ) ()
  − ,−


 () ()
  − ,−
PSF je centro-symetrická vzhledem k jejímu těžišti:
 ,   = 1
Věta:
Nechť (, ) je funkce obraz a ,  jsou nezáporná celá
čísla. Pak definujeme následující funkcionál (, )() :
Je-li ( + ) liché pak (, )() = 0.
Je-li (p + q), pak je sudé:
(, )
 , 

()
=
()

−
1

()
00  =0

 =0
0<+ <+



()
( − ,  − )() ∙ 

je tzv. blur invariant pro všechny  a .
(, )() = (, )(∗ )
Můžeme tímto měřit třeba asymetrii. Pokud je kruhově symetrická, tak  =  a je tam jen
jedna suma.
−
Pro N-fold symetrii: místo podmínek 0 <  +  <  +  tam je podmínka 0 <  +  a 
je Integer.
Kombinované invarianty:
 rotace + konvoluce –
 ′ ,  =  −(− ) ∙ (, )
Pokud:  = =1 ( ,  ) 
A platí-li: =0   −  = 0
Pak máme invariant:   =    ∗ 

afinní + konvoluce – Nechť I(00 , ⋯ ,  ) jsou afinní invarianty. Pak podle definice
z nich je ( 0,0 , ⋯ ,  ,  ) soubor blur&afinních invariantů.
Pozn.:
 liché stupně momentů >> blur invarianty
 sudé stupně momentů >> měření rozmazaní
  = 20  + 02 ()
Pokud  1 >  2 , potom je 1 více rozmazáno.
Je to robustní na šum, ale blbé je, že jde pořád o globální invarianty.
18.
okruh – Rychlé algoritmy pro výpočet 2-D momentů:
Diskrétní momenty:
()

∞


=

  (, ) →
()


    
=
=1  =1
−∞
Jde vlastně o sumu Diracl. delta fcí,  je funkční hodnota v pixelu (, )

 
U binárního obrázku: 
=1  =1  
Obtížnost (2 ) u binárního obrázku ()
Metody pro zrychlení výpočtu:
 Dekompozice
Liší se způsobem výpočtu a na jaké bloky rozkládáme.
o po K-blocich:

()

( )
=

=1
( )
 <<  2
()
 ~(1),  ~()
o Delta metoda (Zakaria): Po „řádcích“
 0 +−1
( )

Zjednodušení přes integraci:
( )

=


= 0
  +
0 ∫ 0
0
= 0

0
   =  +1 0 + 
 +1
+1
− 0
o Obdélníky: stejný postup jen pospojujeme stejné řádky
( )
1
1
Suma pak vypadá takto:  = =
  =

0
0
A integrace:
 1 1
1
( )
+1
+1
 =
      =
1 +1 − 0
∙ 1 +1 − 0
( + 1)( + 1)
 0 0
Tento vzorec se používá i u dalších metod, jen je rozdíl, jak získáváme ty bloky.
o Čtvercová dekompozice: obrázek rozdělujeme do kvadrantů a
jednotlivé kvadranty na další podkvadranty do té doby dokud není celá část
kvadrantu buď obrázek, nebo bez obrázku. Zde je rychlost algoritmu po
dekompozici při počítání jednotlivých bloků opět (1). Ale celková rychlost
závisí na čase stráveném při samotné dekompozici.
o Největší vepsané čtverce: Zde se snažíme do obrázku vepsat největší vepsaný
čtverec a na zbytky obrázku, co jsou nezakryté opět největší čtverec, až je nakonec celý
obrázek zakrytý různě velkými čtverci. To co platí o rychlosti u čtvercové dekompozice, platí
i tady. Opět celkový čas závisí na čase zabraném dekompozicí. Metodu můžeme modifikovat
tak, že místo čtverců používáme i obdélníky.

Po hranici
Greenův teorem:∬
mějme:  ,  =

 ,   =

  +1  

(, )
+1
1

a tedy můžeme počítat moment: 
= +1

 +1   
Metody se liší jako diskrétně počítat integrál po hranici
o sumace pixel-by-pixel
o polygonální aproximace
o aproximace pomocí splinů
SHRNUTÍ MOMENTŮ
výhody
nevýhody
skvěle zvládnutá matematika
momenty jsou globální
kompaktní nezávislé množiny
malé lokální chyba ovlivní všechny momenty
dobrá míra diskriminality
je potřeba dobrá segmentace
dobrá robustnost na noise
invariance k mnoha transformacím
19.
okruh – Waveletová transformace:
wave… – osciluje
…let – dobře lokalizovaná kolem 0, pak rychle mizí
Použití:
 komprese
 odstranění šumu a poškození
 detekce struktur
 fúze dat s různým rozlišením
 problematika rozmazání
 registrace obrazu
Okno proměnné šířky
o analýza vysokých frekvencí  úzké okno pro lepší „time“ rozlišení
o analýza nízkých frekvencí  širší okno pro lepší „frequency“ rozlišení
Okénková Fourierova transformace:
 ,  =
z toho:   = () −2
1

mějme funkci:   =
( )

∞
   ∗ ( − ) −2 
−∞

Když tuto funkci dosadíme do integrálu, dostáváme waveletovou transformaci:
∞
1
−
 ,  =
  ∗ (
)

 −∞
, ,  > 0
τ…translace - pomocí proměnné  posouváme wavelet v čase a tím určujeme polohu okénka.
…dilatace - pomocí proměnné  wavelet takzvaně škálujeme. Pro velká  je wavelet
“rozplizlý” a pro malá je naopak “smrsknutý”. Tím v podstatě definujeme šířku okénka.
Pokud necháme proměnnou  konstantní a proměnnou  budeme měnit, dostávám časový
signál, který nám dává údaj o tom, která oblast transformovaného signálu je nejvíce podobná
použité vlnce (v tom bodě bude mít WT maximální amplitudu). Pokud budeme postupně
dosazovat za  i za , dostaneme o něco podrobnější tabulku koeficientů, ve které budou jak
údaje o čase (koeficient  udávající časový posun waveletu) tak i o škále (koeficient ).
Je možné vypozorovat, že škála  vlastně souvisí s frekvencí. Čím větší , tím “rozplizlejší”
wavelet a tím spíše bude odpovídat nižším frekvencím ve zkoumaném signálu.
 , →  , …matečná waveleta (mother wavelet)
, =


(
−

), , ,  > 0… normalizace přes škály
Vlastnosti: ∫  = 0, ∫ 
2
< ∞, je to něco jako band-pass filtr ve FT
Spojitá waveletová transformace:
∞
 ,  =
∞
  =
−∞
…záleží na 
Redundantní – diskretizace , 
−∞
  ∗,  
 ,  , 


, ,  > 0
Ortonormální báze 2  :   = 2 (2  − ), , ,  = 2 + 
Diskrétní waveletová transformace:

 
() =
=

  =  (),   =
  
=
19.1.
MRA - Mutliresolution analysis
19.2.
waveletová dekompozice funkce f
Postup pro konstrukci ortonormálních bází v 2 ℝ prostoru
- vnořená sekvence
uzavřených
podprostorů 
- každé  odpovídá
jednomu měřítku
- plně určeno volbou
škálovací funkce 
-každý  je generován posuny ,
Ty elipsy, to je prostor bazických fcí ortonormální báze 2 ℝ =

 ,
 = 0
Dilatační rovnice:
  =    ( − )…škálovací – FATHER WAVELET
  =    ( − )… waletová – MATHER WAVELET
, …kompaktní = nulové krom určitého konečného intervalu
  - ortonormální projekce fce  do 
 −
 
, ,  → , =
 =
=
 −
 
, , () → , =
 =
=
>>Kompaktní suport:
∞
−∞
() ,  
∞
−∞
() ,  
−
  =

,  ,  +
, , ()
= 
  = á +   ůé ěří
−, =    −  , …h - low pass filtr
−, =  ( − ), …g - high pass filtr
Různé tipy wavelet:
 Haar waveleta:
  =  2 + (2 − 1)
  =  2 − (2 − 1)
• kompaktní
• dyadická
• ortonormální
FT Haara:

Mexican hat waveleta
2
  = 1 −  2  − /2

Daubechies 4 waveleta
Je nyní asi v praxi nejpoučnější.
SHRNUTÍ WAVELET
výhody
nevýhody
jednoduchost konstrukce a reprezentace
ortogonální kompaktní wavelety nemohou
být symetricke
invariance k některým operacím
(kromě Haara)
hladkost, spojitost, diferenc.
dobré vlast. vzhledem k počtu nul. momentů
Jen ještě pro úplné pochopení WT:
Waveletová transformace spočívá v tom, že máme nějaký spojitý časový signál () a na
jeho různě posunuté a různě široké oblasti (tzv. okna) se snažíme “napasovat” vlnku. Pro
každé okno dostaneme jako výsledek transformace nějaký koeficient, který je tím větší,
čím větší je podobnost onoho signálu v rámci daného okna s onou vlnkou. Když to
porovnáme s velmi dobře známou Fourierovou transformací, tak si můžeme všimnout
podstatné analogie, ale i podstatného rozdílu. Zatímco ve Fourierově transformaci rozkládáme
celý signál na sinusovky, tak ve waveletové, jsou to wavelety. Rozdíl je i v tom, že FT se
provádí nad celým signálem, kdežto WT nám nabízí zastoupení vlnek v různých časových
úsecích signálu. Existuje sice takzvaná STFT (short-time FT), která také „rozkouskovává“
signál na víc části, ale ty jsou vždy stejně široké.
20.
okruh – Waveletová komprese:
20.1.
principy a základní pojmy
Jde nám o eliminaci redundantní informace, díky čemuž ušetříme velikost přenášené
informace a tím i čas a peníze.
 prostorová – hodnoty v sousedních pixelech jsou korelované
 frekvenční – frekvenční hodnoty ze stejného pixelu jsou korelované
 časová – video: většina pixelů se ve framech za sebou nemění, proto je lepší kódovat
jednotlivé změny pixelů, než ukládat sekvenci snímku, snímek po snímku
WT provádí dekorelaci dat a to buď ztrátově, nebo bezztrátově.
# ř
# 
WT je například použita v kompresním algoritmu JPEG2000 (obyčejný JPEG, ale i všechna
MPEGx videa jsou komprimována diskrétní kosinovou transformací). Ať už v DWT nebo
DCT jde o to, že se zpracují a uloží jen koeficienty do určitého levelu a dochází tak ke ztrátě
informace. Lidské oko to ale není schopno příliš poznat. DWT přitom zachycuje o něco lépe
detaily, protože je velmi citlivá na ostré změny v obrazu, zatímco DCT spíše “rozmazává”.
Porovnání DCT a DWT
Diskrétní Kosinusová Transformace
Diskrétní Waveletová Transformace
 každý koeficient reprezentuje plochu a  lépe zachyceny „anomálie“
frekvenční rozsah
 zachycení pozic koeficientů - náročné
 někdy nezbude dost bitů na „anomálie“ =
hrany
 blokový efekty
20.2.
prahování
ztrátová komprese - vynulování koeficientů menší než práh
Prahování:
Po prahování rozdělím bitmapu na dva obrázky:
 binární – abych věděl, kde jednotlivé pixely leží
 hodnotový – stačí znát první hodnotu pixelu a pak už jen změny od
této hodnoty
Po prahování máme kvantizaci
Vektorová kvantizace (blokové kódování):  = { : }
…codebook
 …codeword
NP úplný problém nalezení codebook nejlépe reprezentující
danou množinu vektorů.
Linde-Buzo-Gray algoritmus ( LBG ) k nalezení optmálního codebooku:
1. urči velikost N
2. vyber náhodně N codewords
3. „clusterize“
4. nové codewords – průměr
5. vrať se k bodu 3. dokud změna
RLE („run length coding“) kódování – bezztrátovou komprese, která kóduje vstupní data
tak, že kóduje posloupnosti stejných hodnot do dvojic (délka posloupnosti, hodnota).
Účinnost komprese je silně závislá na charakteru vstupních dat, která musí obsahovat delší
sekvence stejných znaků, jinak výrazně účinnost komprese klesá.
Příklad vstupních dat kodéru RLE:
WWWWWWWWWWWWBWWWWWWWWWWWWBBBWWWWWWWWWWWWWWWWWWWWWWWWBWWWWWWWWWWWWWW
Výsledek kódování RLE: 12W1B12W3B24W1B14W
Huffmanovo kódování:
Nový tip komprese:
modelování závislostí mezi koeficienty - deterministická struktura „do hloubky“- „Zero trees“
Embedded Zerotree Wavelet Encoding
nevýhody:
 obtížné dekódování pouhé části obrázku špatné
 vzpamatování se z chyb
následující přístupy:
 Set Partitioning in Hierarchical Trees
(SPIHT)
 Embedded Block Coding with Optimized
Truncation (EBCOT) - v JPEG2000
EBCOT: Taubman, JPEG 2000
vhodný pro vzdálené prohlížení velkých souborů
škálovatelná komprese obrázků (embedded)
- kvalita
- rozlišení
náhodný přístup (různé části signálu - různé části obrázku)
kódování ROI
 EBCOT bloky:
o dělí každý sub-band na code bloky (32x32) ty separátně kóduje
o všechny bloky v sub-bandu – stejná velikost
o každý blok kódován zvlášť
o výhody
 paralelní zpracování
 využití lokálních informací
 omezený dopad chyb
 možnost náhodného přístupu
0 
0 
0 
0 
0 
0 
0 
0 
1 
1 
1 
1 
 2  2 
1 
1 
2  2 
2  2 
21.
okruh – Odstraňování šumu pomocí wavelet:
21.1.








principy a základní pojmy
snaha o rekonstrukci lokálních struktur
rozložení spekter x amplitudy spekter
hlavní je amplituda
obrázky jsou převážně hladké oblasti s pár hranami
WT má dobré kompresní vlastnosti (komprese + šum)
jen málo velkých koeficientů
dobrá lokalizace
používáme ortonormální waveleta
(Gaussovský bílý šum + ortonormální báze WT = zase Gaussovský bílý šum)
Princip odstraňování šumu:
hlavní problém: prahování – volba prahu
 způsob hledání bývá heuristický
 chceme to jednotné pro jednotlivé úrovně?
 často různé, jen do určité hloubky
21.2.
"soft" prahování
hladší, „líbivější“ výsledky
21.3.
"hard" prahování
lépe zachovává hrany
Mnohdy se na detailní úrovně používá SOFT, a pro ostatní věci HARD.
Odstraňování šumu – VisuShrink:
 nejčastěji - univerzální práh Donoho, Johnstone
 rychlé a automatické
 práh určen: = 2 log   ,  – délka signálu,  – STD



idea – odstranit koeficienty, které jsou menší
než očekávané maximu předpokládaného
šumu délky n
často jen pro 1. odhad prahu
odhady 2
2 =

1
 2
−1, − 
2

2 − 1 =1
 2 = 1 0.6745 ({−1, ,  = 1,  2})
MAD – medián absolutní hodnoty odchylky od mediánu –
  −1, −   −1,
21.4.






adaptivní metody
v praxi - prahy nezávislé na velikosti obrázku
adaptace prahu na každý band nebo na lokální variaci koeficientů
spatial x scale adaptivní
velký práh - odstranění šumu
malý práh - zachování detailů
adaptace podle hladkosti okolí
22.
okruh - Použití zavelet:
22.1.
detekce hran
WT lze použít jako velmi dobrý algoritmus pro detekci hran v obraze (obzvláště když se
použije nějaký wavelet s ostrým přechodem).
Jde o obdobu Cannyho detektoru hran - lokální maxima ve směru maximální změny.
multiscale verze:
 vyhlazování low-pass filtrem
 nejčastěji Gauss
 (x,y)
(, )
1 (, ) =

(,
)
 2 (, ) =

1
 
2 ,  =     , 
2
2 2
 1 ≤  ≤ 2
Dále pak:
1
− −
2 ,  =    , 
2
2 2
21 ,  = −2
   (, )
2

,
22 ,  = −2
   (, )
2

2 wavelety odpovídají vektoru gradientu vyhlazeného obrázku
1

 (2 , , )
= −2
 2 (2 , , )

 ∗ 2 (, )


 ∗ 2 (, )

= −2 ∇  ∗ 2 (, )
velikost gradientu:
 2 , ,  =
 1 (2 , , ) 2 +  2 (2 , , )
směr gradientu:
 2 , ,  = argtan
hrany ~ 1D lokální maxima  ve
směru 
posun obrázku:
 posun maxim
 nemění se hodnoty maxim
 koeficienty WT se můžou měnit
Používáme:
 multiscale informace o hranách, z
jednotlivých úrovní
 analýzu vztahů mezi jednotlivými
úrovněmi
Mizení koeficientů do hloubky závisí na
lokální hladkosti signálu.
 2 (2 , , )
 1 (2 , , )
2
diferencovatelnost - Lipschitzovské koeficienty:
Věta: Funkce f je uniformně Lipschitzovská s  (0 <  < 1) na intervalu [, ] právě tehdy,
když existuje konstanta K taková, že pro libovolné (0 , 1 ) z [, ] platí:
 0 −  1 ≤  0 − 1 
 čím větší , tím víc diferencovatelná funkce
 v nespojitosti  = 0 (step hrana)
 nutná podmínka pro f aby byla někde L. s  je existence
 C>0
 2 , ,  ≤ 2 (+1)
 podle vývoje velikosti w. koef. - odhad hladkosti obr. f.
Detekce hran - analýza
- pro detekci hran – odhady přes úrovně co šum a co hrana
- je L. – nárůst koeficientů (hrany)
- není L. – pokles koeficientů
- není L. – pravděpodobně šum a detaily
- použít hlubší úroveň když rychlý pokles
- použít vyšší úroveň když pomalý pokles
- přesnost umístění hran
22.2.
rohů
Zde jsme si na přednášce neříkali nic (resp. jsem to ve svých zápiskách ani v přednáškách
neviděl), ale předpokládám, že zde bude platit něco podobného jako při detekci hran.
22.3.
registrace obrazu
Díky dobré detekci hran můžeme WT používat pro detekci obrazu. Navíc je zde výhoda, že
můžeme detekci provádět na nižších úrovních a tak pracovat s menšími obrázky a tak i snížit
výpočetní náročnost. Také je zde výhoda, že přechodem do nižších řádů odstraníme šum.
22.4.
měření zaostření (~rozmazání)
 () - high pass bandy
 - hloubka DWT
 - dilatační faktor
 ,  =  ∗  ,  ,  = 
 =  ()
 
 =  () ( −  )

Jelikož si DWT všímá detailů a zároveň dokáže zvýrazňovat hrany, je možné použít jí i pro
softwarové doostřování.
K doplnění – Image Psion


Input – několik obr. stejné scény
Output – jeden obr. s high quality
multifocus fusion:
1) použijeme WT
2) vytvoříme fusion map (FM) >> popis co odkud (ze kterého obrázku) budeme brát –
nesmí být moc rozbitá
3) „poslepujeme“ HP z těch obrázků podle FM a LP se vezme většinou jen
zprůměrováním
4) IWT
multimodální fusion:
např. panchromatický a barevný obrázek jedné scény a jejich spojení
- máme jeden obrázek vícekanálový a jeden 2krát větší (rozlišením) panchromatický
- uděláme WT toho panchromatického, a jeho LP (horní kvadrant po WT) zahodíme a
místo něho tam dosadíme ten vícekanálový, který tam díky poměru velikostí přesně
zapadne
- nakonec uděláme IWT
To aby bylo rozlišení v daném poměru, uděláme tak, že dáme nejmenší společný násobek,
nebo to prostě tupě převzorkujeme.
Download

SZZ - Zpracování a rozpoznávání obrazu.pdf