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)

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 2𝜋𝑎2 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 + 4𝜇11

2 = 𝜙1 + 𝜙2

2

>> 𝜇′02 ≡ 𝜆2 =

𝜇20 + 𝜇02 −

𝜇20 − 𝜇02

2

2 + 4𝜇11

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.