Základy zpracování obrazu

UNIVERZITA PARDUBICE FAKULTA CHEMICKO-TECHNOLOGICKÁ

Základy zpracování obrazu Ing. Miroslav Fribert, Dr

Pardubice 2006

1. Operace s maticemi, program Mathematica 1.1 Matice ve zpracování obrazu Matematickým modelem digitalizovaného obrazu je matice s M øádky a N sloupci, pøièem
jejími prvky jsou kvantované hodnoty jasu ve vzorkových bodech (pixelech) tohoto obrazu. V dalším je uveden pøehled maticových operací pou
ívaných pøi zpracování obrazu. Vektory a matice N´1 sloupcový vektor f je 1D vertikální struktura æ ç ç ç f =ç ç ç çç è

f1ö ÷ f 2÷ : ÷ ÷ fj ÷ : ÷ ÷ fN ÷ø

(1.1)

1´N øádkový vektor f T je 1D horizontální struktura vzniklá transpozicí vektoru f f T =( f1

f2 . .

fN )

fj . .

(1.2)

M´N matice je 2D struktura o M øádcích a N sloupcích æ F11 F12 ç ç F 21 F 22 F =ç : : çç è FM 1 FM 2

. .

. .

.

.

F1 N ö ÷ F2N ÷ : ÷ ÷ FMN ø÷

(1.3)

Nulová matice (symbol 0) má všechny prvky rovny nule. Diagonální matice je ètvercová (M=N) a všechny její prvky kromì diagonálních jsou nulové. Jednotková matice (symbol I) je diagonální matice se všemi diagonálními prvky rovnými 1. Souèet matic Souèet dvou matic C = A+B je definován pouze pro matice stejných velikostí. Výsledkem je M´N matice s prvky C ( m, n) = A( m, n) + B(m, n)

(1.4)

Násobení vektorù a matic Souèin matic C = AB je definován pro matice, u kterých je poèet sloupcù matice A s rozmìrem M´P rovný poètu øádkù matice B rozmìru P´N. Výsledkem je matice M´N s poètem øádkù matice A a poètem sloupcù matice B s prvky P

C ( m, n) = å A( m, p) × B( p, n) = A( m,1)B(1, n) + A( m,2)B(2, n)+......+ A( m, P )B( P, n) p =1

3

(1.5)

Násobení matice skalárem C = kA C ( m, n) = k × A( m, n)

(1.6)

Skalárním souèinem vektoru A s rozmìrem 1´M a vektoru B s rozmìrem M´1 je skalár M

S = å A(1, m ) × B( m,1)

(1.7)

m =1

Vektorovým souèinem vektoru A rozmìru M´1 a vektoru B rozmìru 1´N je matice C o rozmìru M´N s prvky C ( m, n) = A( m,1) × B(1, n) = A( m ) × B( n)

(1.8)

Inverzní matice Pro inverzní matice A-1 k matici A platí AA -1 = I ,

A -1 A = I , [ A -1 ] -1 = A

(1.9)

Jestli
e existuje k matici A inverzní matice A-1, potom je matice A regulární, jinak je singulární. Pro regulární matice A, B potom platí

[ AB] -1

= B -1 A -1

(1.10)

Transponovaná matice Transpozicí matice A rozmìru M´N je matice AT její
øádky jsou sloupce a sloupce jsou øádky pùvodní matice A. Je to v podstatì zámìna øádkù za sloupce. Platí tedy [AT]T = A. Je-li AT = A, je matice A symetrická. Pro dvì libovolné matice A, B platí

[ AB] T

= BT AT

(1.11)

Jestli
e je matice A regulární (existuje k ní matice inverzní) potom platí

[A ] T

-1

[ ]

= A -1

T

(1.12)

Ortogonální a unitární matice Øíkáme,
e ètvercová reálná matice A je ortogonální, jestli
e platí (1.13) AAT= I, tedy A-1 = AT Pokud o matici víme,
e je ortogonální, inverzní matici vypoèítáme, kdy
provedeme její transpozici. Determinant ortogonální matice je roven +1 nebo -1. Unitární matice je analogický pojem k ortogonální pro pøípad komplexních matic. Platí pro ni AAT*= I, tedy A-1 =AT*, kde AT* je transponovaná a komplexnì sdru
ená matice k A. Oznaèujeme ji také AH - Hermitovská matice. Potom AH = AT*, AAH=I

4

(1.14)

Stopa matice Stopou N´N matice F nazýváme skalár, který je souètem diagonálních prvkù tr[F ] =

N -1

å F( n, n)

(1.15)

n= 0

Norma vektoru a matice Normou vektoru a matice nazýváme skaláry f = f T f,

[

F = tr F T F

]

(1.16)

Hodnost matice N´N matice A má hodnost R (píšeme rank[A]=R), jestli
e její nejvìtší regulární submatice je rozmìru R´R. Hodnost souètu a souèinu matic rank [ A + B] £ rank [ A] + rank [B] rank [ AB] £ rank [ A]

(1.17)

rank [ AB] £ rank [B] Kronekerùv souèin Levý Kronekerùv souèin P´Q matice A a M´N matice B je matice C rozmìru PM´QN , )A B(12 , )A é B(11 ê B(21 , )A B(2,2) A C = AÄB = ê . . ê êB( M ,1) A B( M ,2) A ë

. . .

ù ú ú ú B( M , N ) A úû B(1, N ) A B(2, N ) A .

(1.18)

Pravý Kronekerùv souèin je potom , )B é A(11 ê A(21 , )B C =BÄA =ê . ê ê A( P,1)B ë

A(12 , )B A(2,2)B . A( P,2)B

. . .

A(1, Q )B ù A(2, Q )B ú ú . ú A( P, Q )B úû

(1.19)

Vlastní èísla a vlastní vektory Tyto pojmy se týkají pouze ètvercových matic. Vlastním èíslem matice A nazýváme takové èíslo l, ke kterému existuje aritmetický vektor u takový,
e platí rovnice A×u = l ×u

(1.20)

kde u je vlastní vektor matice A pøíslušný k vlastnímu èíslu l.

5

Mno
ina všech vlastních èísel matice A se nazývá spektrum matice A. Ka
dá ètvercová matice rozmìru N´N má N vlastních èísel, poèítáme-li jejich násobnost. Jestli
e jsou vlastní èísla matice A navzájem rùzná, potom ke ka
dému vlastnímu èíslu existuje jediný lineárnì nezávislý vlastní vektor.

1.2 Vzorkovací funkce Konvoluce dvou funkcí Konvoluce dvou funkcí v èasové oblasti f(t) a g(t) je definována pomocí konvoluèního integrálu ¥

¥

t =-¥

t =-¥

ò f ( t ) g( t - t ) dt = ò f ( t -t ) g( t ) dt

f ( t ) * g( t ) =

(1.21)

Podobnì pro funkce dvou promìnných v prostorové oblasti (napø. dvì obrazové funkce) f ( x, y ) * g ( x, y ) =

¥ ¥

¥ ¥

-¥-¥

-¥-¥

ò ò f (a ,b ) g( x - a , y - b ) dadb = ò ò f ( x - a , y - b ) g(a ,b ) dadb

(1.22)

Konvoluci je mo
né chápat jako posunující se okno funkce g(a,b) v souøadnicích x,y, kterým b

b

b

a

a

a

g2( a,b)

g1( a,b)

g2(-a,-b)

b

b

a

x

a

y

g1( a,b)g2(x-a,y-b)

g2(x-a,y-b)

Obr. 1.1 Grafické znázornìní konvoluce zkoumáme funkci f(x,y) (obr. 1.1). Funkce g(a,b) se také nazývá jádrem konvoluce. Diracova funkce a vzorkování Jednorozmìrná Diracova funkce v bodì a je definována ì¥ d( x - a ) = í î0

pro x = a pro x ¹ a

6

(1.23)

Obr.1.2 Vzorkování pomocí Diracova impulsu ¥

ò d( x - a ) dx = 1 -¥

(1.24)

Proto
e je d(x) ¹ 0 pouze pro x = a je souèin funkcí y(x) a d(x-a) (viz obr.1.2) y( x ) × d( x - a ) = y(a ) × d( x - a )

(1.25)

Z této rovnice vyplývá vzorkovací vlastnost Diracova impulsu. Po integraci pøedchozího souèinu dostaneme ¥

¥

-¥

-¥

ò y( x ) × d( x - a ) dx = y(a ) × ò d( x - a ) dx = y(a )

(1.26)

Tedy vzorek v bodì x = a dostaneme, kdy
v definièním intervalu Diracova impulsu integrujeme souèin vzorkované funkce a Diracovy funkce posunuté do bodu a.

1.3 Program Mathematica Na jednoduchých pøíkladech zde bude podán velmi krátký popis pou
ívání programu Mathematica od Wolfram Research. Dále budou prezentovány nìkteré operace s maticemi, proto
e jsou pou
ívány v oblasti analýzy obrazu. Pou
ití nadstavby Digital Image Processing programu Mathematica bude demonstrováno u jednotlivých kapitol tìchto pøednášek. Po spuštìní programu se objeví hlavní menu a okno zápisníku (notebook), do kterého se zapisují promìnné, operace a pøíkazy výpoètù, které chceme provádìt. Operace a pøíkazy lze psát pøímo z klávesnice a potom výbìrem z pomocných oken. Ka
dý notebook obsahující posloupnost operací lze ulo
it pod jménem a znovu ho naèíst. Na obrazovce si mù
eme zviditelnit rùzná pomocná okna (File ->Palletes), napøíklad BasicInput, BasicCalculation, která usnadòují zadávání vstupù. Velmi dùle
ité a praktické je pou
ívání menu Help, kde jsou podrobnì popsány syntaxe všech operací pøístupných v programu. Pøíklady základních operací Pøepneme se do anglické klávesnice. Pokud chceme reálný výsledek, èísla zadáváme s desetinnou teèkou. Pøíklad 1.1 Vypoèítat výraz 2´9.7 200 /3. Do notebooku napíšeme 2*9.7^200 /3 Shift Enter.

7

Pozn. Operace sèítání +, odeèítání -, násobení * (u matic teèka), dìlení /, mocnina ^. Ostatní operace z palety Basic Input. Pøíklad 1.2 Vypoèítejte hodnotu sin(p/3) a potom inverzi výsledku. Do notebooku napíšeme y=Sin[p/3.0] a a=ArcSin[y]. Pozn. Argumenty funkcí jsou v hranatých závorkách a jsou oddìleny èárkou. Výsledek se ulo
í do promìnných y, a . Tyto pak mohou být pou
ity v dalších výrazech. 1 x+a Pou
ijeme šablony v paletì BasicInput zobrazené na ploše + Shift Enter. Pozn. Znak se v šablonì aktualizuje klikem do jeho ètvereèku.

Pøíklad 1.3 Vysázejte matematický výraz x 2 +

Pøíklad 1.4 Vypoèítejte primitivní funkci (neurèitý integrál) funkce tg x a potom urèitý integrál té
e funkce v mezích 0.0, p/3. Pou
ijeme palety BasicInput na ploše jako pøi sazbì vzorcù, nebo pou
ijeme funkce Integrate. Do notebooku napíšeme Integrate[Tan[x],x] + Shift Enter. Pro urèitý integrál pou
ijeme paletu BasicInput. Pozn. Další palety (BasicTypesetting, BasicCalculation, AlgebraicManipulation, atd.) jsou k disposici pøes menu File – Palletes. Pøíklad 1.5 Vytvoøte grafy 2D funkce sinx2 a 3D funkce sin(y+sin3x). Do notebooku napíšeme: y = Sin[x^2] + Shift Enter, Plot[y, {x,-3, 3}] + Shift Enter z = Sin[y+Sin[3x]] + Shift Enter, Plot3D[z, {x, -3, 3}, {y, -3, 3}, PlotPoints ® 40]+ Shift Enter Pozn. Seznam hodnot se dává do slo
ených závorek. Zvìtšení zobrazení Format->Magnification. Pøíklady operací s maticemi Pøíklad 1.6 Definujte matici m1 rozmìru 3´4 s libovolnymi celoèíselnými prvky. Proveïte operace transpozice, násobení skalárem 33 a vypoèítejte normu této matice. Do notebooku napíšeme seznam m1={{12,58,21,8},{18,5,73,3},{22,4,86,66}}+ Shift Enter MatrixForm[m1] + Shift Enter Transponovaná matice mt = Transpose[m1] + Shift Enter. MatrixForm[mt] + Shift Enter Násobení skalárem naskal = 3.3m + Shift Enter. MatrixForm[naskal] + Shift Enter. Norma matice norm = Tr[Transpose[m1].m1], nebo norm=Tr[mt.m1]. Pøíklad 1.7 Zadejte matici m2 rozmìru 4´4 s prvky hodnot 1-16. Vypoèítejte determinant této matice. Jestli bude jeho hodnota rovna nule, zámìnou dvou prvkù v rùzných øádcích bude nenulový. V zápisníku napíšeme dtm = Det[m2] + Shift Enter. Proveïte souèin matice m1 z pøedchozího pøíkladu a matice m2. Ovìøte ruèním výpoètem prvek m00 výsledné matice. V zápisníku napíšeme souc = m1.m2 + Shift Enter. Pøíklad 1.8. Zadejte dva vektory v1={1,2,3,4}, v2={1,-j, -1, 1}a vypoèítejte jejich skalární a vektorový souèin. Do notebooku zadejte oba vektory. Pro skalární souèet napište pøíkaz skal1= v1.v2 + Shift Enter., skal2=v2.v1 + Shift Enter. Oba výsledky jsou stejné.

8

Pro vektorový souèet napište pøíkaz vek1=Outer[Times,v1,v2] + Shift Enter, vek2=Outer[Times,v2,v1] + Shift Enter. Výsledkem jsou matice 4´4, které nejsou shodné. Proveïte souèin vek1 ruènì. Pøíklad 1.9. Proveïte výpoèet inverzní matice k matici 3´3 slo
ené z devíti prvních prvoèísel. Proveïte zkoušku. V zápisníku zapíšeme: m4={{1,2,3},{5,7,11},{13,17,19}}+ Shift Enter. MatrixForm[m4] + Shift Enter. invm4=Inverse[m4] + Shift Enter. souc = m4.invm4 + Shift Enter. MatrixForm[souc] + Shift Enter. Pøíklad 1.10. Vypoèítejte vlastní èísla a vlastní vektory ètvercové matice m5. Pro první vlastní èíslo uka
te platnost definièního vzorce. Zadávejte reálná èísla (s desetinnou teèkou). Do zápisníku napíšeme seznam m5={{1.,2.,2.},{1.,5.,7.},{4.,3.,6.}}+ Shift Enter Eigenvalues[m5] + Shift Enter Eigenvectors[m5] + Shift Enter Správnost vypoètených vlastních èísel a vektorù ovìøíme s pou
itím vzorce A × u = l × u.

9

2. Úvod do zpracování obrazu 2.1 Proè chceme zpracovávat obrazy Se zpracováním obrazu souvisí tøi hlavní skupiny problémù: • získání, digitalizace a kódování obrazu z dùvodu jeho ukládání, pøenosu a reprodukce • vylepšování (image enhacement) a obnova (image restoration) obrazu z dùvodu odstranìní deformací a poruch a zvýrazòování detailù • segmentace obrazu a popis jeho objektù jako nejni
ší úroveò strojního zpracování (machine vision).

2.2 Charakteristika obrazu Matematickým modelem 2D monochomatického obrazu (èernobílá fotografie, obraz na monochromatické obrazovce) je obrazová funkce dvou promìnných f(x,y), kde x a y jsou prostorové souøadnice v jednotlivých bodech obrazu a hodnota f je úmìrná jasu v tìchto bodech. U barevného obrazu jsou hodnoty funkce f(x,y) vektory se tøemi jasovými slo
kami r, g, b , které odpovídají barevným pásmùm, na které rozdìlujeme kmitoètový rozsah viditelného svìtla. Pro manipulaci s obrazem (ukládání, modifikace, pøenos) je model obrazu ve tvaru analogové funkce dvou promìnných nevhodný. Proto obraz digitalizujeme, t.j. rozlo
íme ho na body, které nazýváme pixely (picture elements) a ka
dému pixelu pøidìlíme kvantovanou hodnotu, která odpovídá jasu bodu v pùvodní obrazové funkci. Modelem digitalizovaného obrazu je potom digitální funkce f(i,j), kde hodnoty promìnných f, i, j, jsou digitální. Výsledkem je digitalizovaný obraz, který je reprezentován dvojrozmìrným polem celoèíselného typu (u barevného obrazu tøemi poli), kde indexy pole jsou souøadnice bodù a hodnoty prvkù pole odpovídají jasu pøedlohy v tìchto bodech. Toto pole mù
eme v pøípadì ètvercového obrazu matematicky popsat maticí, která má tvar

æ f (0,0) ç , ) ç f (10 f ( i, j ) = ç × ç × ç ç f ( N - 10 , ) è

f (01 ,) f (11 ,) . . f ( N - 11 ,)

. .

.

. .

.

f (0, N - 1) ö ÷ f (1, N - 1) ÷ ÷ ÷ ÷ f ( N - 1, N - 1) ÷ø

(2.1)

kde N je poèet øádkù a poèet sloupcù matice, který odpovídá poètu pixelù v obraze, na který je tento digitalizací rozlo
en. Pro hodnoty kvantovaných úrovní jasu pixelù platí vztahy 0 £ f ( i, j ) £ G - 1 G =2

m

kde m je poèet bitù dvojkové hodnoty f(i,j).

11

(2.2)

Je nutné si ujasnit, co je to jas pixelu digitalizovaného obrazu. Hodnoty jasu rùzných pixelù mají význam pouze relativní, t.j. pouze ve vztahu jedna ke druhé. Ka
dé zaøízení sejme obraz jinak, hodnoty jasu pixelù po vícenásobném sejmutí stejné oblasti se pak od sebe liší. Napøíklad pøi snímání obrazu kamerou ji mù
eme napøed zkalibrovat na bílou barvu, co
znamená pøi m = 8 hodnotu jasu pøibli
nì 255. Jiná kamera bude interpretovat hodnotou 255 pøi jiném jasu snímané pøedlohy (zále
í na konstrukci kamery, vnìjším osvìtlení, pøípadnì na dalších faktorech). Poèet bitù, které musíme ulo
it do pamìti, pøípadnì pøenést komunikaèním kanálem (bez komprese obrazu) je pro obraz M´N pixelù s m bity na pixel b= M ´N ´m

(2.3)

Napøíklad pro obraz 200´200 pixelù s 256 úrovni šedi na pixel (m = 8 bitù) je b = 320 000 bitù.

2.3 Rozlišení obrazu Pojem rozlišení obrazu vyjadøuje kolik detailù (nebo jak velké) mù
eme v nasnímaném obraze vidìt a závisí pøímo na hodnotách N (prostorové rozlišení) a m (jasové rozlišení), které tak rozlišení obrazu charakterizují. Obecnì platí - èím vyšší je frekvence vzorkování, tedy vìtší N a èím vìtší rozsah kvantování, tedy vìtší m, tím více detailù mù
eme v obraze rozlišit. Tedy hodnoty N a m charakterizují rozlišení obrazu. Pozor, nezamìòujme tuto charakteristiku s parametrem rozlišovací schopnosti zaøízení, která zpracovávají grafické objekty. Pøi velkých hodnotách N a m je èasto poèet bitù obrazu velký, co
znamená velké datové soubory, a to zpùsobuje problémy pøi zpracování a pøenosech. Snahou je poèet bitù (tedy rozlišení obrazu) sni
ovat, co
zase mù
e pøinést ne
ádoucí efekty. Pøi konstantním m a klesajícím N je výsledkem tzv. šachovnicový efekt. Pøi konstantním N a klesajícím m (malý poèet úrovní šedi) vznikají "tvrdé" pøechody mezi jednotlivými úrovnìmi šedi a výsledkem jsou tzv. falešné obrysy.

2.4 Jak obraz zpracováváme ? Model vzorkovaného obrazu Zpracování obrazu se provádí pomocí transformací obrazu, které jsou realizovány pomocí operátorù. Aplikací operátoru O na vstupní obraz f(x,y) dostaneme výstupní obraz g(x,y)=O[f(x,y)]. Budeme se zabývat lineárními operátory. Pro lineární operátor O platí: O[a × f 1( x, y ) + b × f 2( x, y )] = a × O[ f 1( x, y )] + b × O[ f 2( x, y )] (2.4) kde f1 a f2 jsou vstupní obrazové funkce, a, b konstanty vzhledem k x, y. Abychom dostali model obrazu ve tvaru matice f(i,j), (i, j jsou celá èísla) a mohli jej digitálnì zpracovávat, musíme analogovou obrazovou funkci f(x,y) vzorkovat a kvantovat. Pro teoretické úvahy provádíme tzv. ideální vzorkování, kdy se vyu
ívá vzorkovací vlastnosti Diracovy funkce. Pro úèely vzorkování 2D obrazu se pou
ívá dvojrozmìrná Diracova funkce. Definice dvojrozmìrné Diracovy funkce ì¥ d ( x, y ) = í î0

pro x = 0, y = 0 pro x ¹ 0 nebo y ¹ 0

12

(2.5)

Dvojrozmìrná Diracova funkce posunutá do bodu [a,b] ì¥ d( x - a , y - b ) = í î0

pro x = a , y = b pro x ¹ a nebo y ¹ b

(2.6)

Pro dvojrozmìrnou Diracovu funkci platí vztah ¥

¥

ò ò d( x - a , y - b ) dx dy = 1 -¥ -¥

(2.7)

Spojité vzorkování Z rovnice dvojrozmìrné konvoluce (rov. 1.22), kdy druhou funkci nahradíme Diracovým impulsem d(x -a, y -b) a ze vzorkovací vlastnosti Diracovy funkce (rov. 1.26) vyplývá matematický model spojitì vzorkované obrazové funkce (vzdálenosti jednotlivých Diracových impulsù se blí
í k nule) fS ( x , y ) = ò

¥

¥

ò f (a ,b ) ×d( x - a , y - b ) da db

-¥ -¥

(2.8)

Tento tvar spojitì vzorkované obrazové funkce budeme nadále pou
ívat. Diskrétní vzorkování Diracova funkce je ideální vzorkovací funkcí a pro vzorkování diskrétních bodù obrazu si mù
eme pøedstavit dvojrozmìrné pole Diracových impulsù (obr.2.1), kdy ka
dý Diracùv impuls z tohoto pole odpovídá diskrétnímu bodu [x,y] vzorkovacího pole. Vzorkovaný obraz je potom tvoøen polem tìchto impulsù vá
ených v ka
dém bodì hodnotou obrazové funkce v tomto bodì.

Obr.2.1 Pole Diracových impulsù Pøi diskrétním vzorkování se posuvy a a b mìní po skocích a = jDx, b = kDy (Dx a Dy jsou intervaly vzorkování) a integrál pøechází na sumu. Pro diskrétnì vzorkovanou obrazovou funkci mù
eme potom psát fD ( x , y ) =

¥

¥

å å f (a ,b ) × d( x - a , y - b )

a =-¥ b=-¥

13

(2.9)

fD ( x , y ) =

¥

¥

å å f ( jDx, kDy ) × d( x - jDx, y - kDy )

(2.10)

j =-¥ k =-¥

Pøi reálném vzorkování pøedpokládáme,
e vzorkovaný obraz má koneènou velikost M´N. Potom je model reálného diskrétního navzorkovaného obrazu dán vztahy M -1 N -1

fD ( x, y ) = å å f (a ,b ) × d( x - a , y - b )

(2.11)

a = 0 b= 0

M -1 N -1

fD ( x, y ) = å å f ( jDx, kDy ) × d( x - jDx, y - kDy )

(2.12)

j =0 k =0

Aplikace transformaèního operátoru Nejprve si znázorníme pøíklad aplikace tranformaèního operátoru (v našem pøíkladu operaci filtrace prùmìrováním se zvýšenou vahou centrálního pixelu). Na obr. 2.2 je znázornìno prùmìrování v centrálním pixelu pomocí konvoluèní masky velikosti 3´3 pixely. Konvoluèní maska zde pøedstavuje transformaèní operátor. Pøedstavme si navzorkovaný obraz velikosti M´N, který chceme vyhladit naznaèeným prùmìrováním. Prakticky tento proces probíhá ve smyslu definice konvoluce tak,
e posouváme konvoluèní masku postupnì po jednom pixelu v obraze a poèítáme prùmìr hodnot jasu pixelù z maskovaného okolí vstupního obrazu. Výsledek pøiøazujeme pixelu výstupního obrazu, který polohou koresponduje s centrálním pixelem masky. 110

95

86

23

35

1/10 1/10 28

44

1/10 2/10 33

49

52

1/10 58

1/10 66

1/10 1/10 1/10

Obr.2.2 Konvoluèní maska filtrace prùmìrováním

14

V tomto konkrétním uspoøádání bude hodnota jasu centrálního pixelu Jc = 23 ×

1 1 432 1 1 1 1 2 1 1 = 43,2 + 35 × + 52 × + 28 × + 44 × + 58 × + 33 × + 49 × + 66 × = 10 10 10 10 10 10 10 10 10 10

Kdy
aplikujeme transformaèní operátor na obraz f(x,y) dostaneme výstupní obraz g(x,y) g( x, y ) = O[ f ( x, y )]

(2.13)

Aplikujeme lineární operátor O na model spojitého obrazu f(x,y) popsaný rovnicí (2.8). Potom mù
eme psát ¥ ¥

¥ ¥ g( x, y ) = O éò ò f (a ,b ) × d( x - a , y - b ) da db ù = ò ò f (a ,b ) ×O[d( x - a , y - b )] da db êë -¥ -¥ úû -¥-¥

(2.14)

Aplikujeme tedy transformaèní operátor pøímo na dvojrozmìrnou Diracovu funkci. Výsledkem je tzv. impulzní odezva (Point Spread Function - PSF) s oznaèením h(x,a,y,b). Tato funkce vyjadøuje, jak hodnoty pixelù vstupního obrazu na pozicích a, b v konvoluèní masce ovlivòují pøes operátor O hodnotu pixelu výstupního obrazu na pozici x, y. O[d( x - a , y - b )] = h( x, a , y,b )

(2.15)

kde h(x,a,y,b) je prostorová impulsní odezva PSF (v podstatì transformovaný obraz pole Diracových impulsù). Tedy g ( x, y ) = ò

¥

¥

ò f (a ,b ) × h( x, a , y,b ) da db

-¥ -¥

(2.16)

Tento integrál se nazývá superpozièní integrál (shifting integral). Pro digitalizovaný obraz rozmìru M´N dostaneme superpozièní sumu g ( x, y ) =

M -1 N -1

å å f (a ,b ) × h( x, a , y,b )

(2.17)

a = 0 b= 0

Uva
ujme,
e hodnoty jednotlivých operandù v masce nezávisí pøi posuvu na její poloze v poli Diracových impulsù. Tedy hodnoty PSF také nezávisí na pozici bodu [x,y] (poloze masky), ale pouze na relativní poloze bodù [x,y] a [a,b]. Transformace je potom prostorovì invariantní a platí h( x, a , y,b ) = h( x - a , y - b )

(2.18)

Rovnice superpozièní sumy (rov. 2.17) pøejde na konvoluci g ( x, y ) =

M -1 N -1

å å f (a ,b ) × h( x - a , y - b )

(2.19)

a = 0 b= 0

Pokud je transformaèní operátor navr
en tak,
e se vzájemnì neovlivòují operace v øádcích a sloupcích, potom je transformace separabilní a platí h( x, a , y,b ) = hc( x, a ) × hr ( y,b ) 15

(2.20)

V praxi to znamená,
e pixely výstupního obrazu v urèitém øádku jsou pøes transformaèní operátor ovlivnìny pouze pixely odpovídajícího tomuto øádku vstupního obrazu. Pøíkladem takového operátoru je Fourierova transformace. Potom mù
eme rovnici 2.17 napsat jako dvì postupné 1D transformace, co
znamená postupnou transformaci napøed ve smìru y a potom ve smìru x. Potom platí g ( x, y ) =

M -1

N -1

å h ( x, a ) å f (a ,b ) × h ( y,b ) c

r

a=0

(2.21)

b= 0

Pokud je transformaèní operátor prostorovì invariantní a souèasnì separabilní potom pro výstupní obraz platí g ( x, y ) =

M -1

N -1

a=0

b= 0

å hc( x - a ) å f (a ,b ) × hr( y - b )

(2.22)

2.5 Výsledek aplikování lineárního operátoru na obraz Pøedpokládejme obrazovou matici f(x,y) s N øádky a N sloupci. Teoreticky mù
eme pøedpokládat,
e všechny pixely vstupního obrazu f(x,y) ovlivòují pøes operátor O hodnotu pixelu na pozici [x,y] výstupního obrazu g(x,y). Rozepíšeme rovnici 2.17 superposièní sumy (rychleji se mìní a) g( x, y ) = f (0,0) × h( x,0, y,0) + f (10 , ) × h( x,1, y,0) + .................. + f ( N - 10 , ) × h( x, N - 1, y,0) + f (01 , ) × h( x,0, y,1) + f (11 , ) × h( x,1, y,1) + .................... + f ( N - 11 , ) × h( x, N - 1, y,1) + f (0,2) × h( x,0, y,2) + f (12 , ) × h( x,1, y,2) + .................. + f ( N - 12 , ) × h( x, N - 1, y,2) +

× × ×

+ f (0, N - 1) × h( x,0, y, N - 1) + f (1, N - 1) × h( x,1, y, N - 1) +.....+ f ( N - 1, N - 1) × h( x, N - 1, y, N - 1) Rozepíšeme rovnici 2.17 pro N=3 2

g ( x, y ) = å

2

å f (a ,b ) × h( x, a , y,b )

(2.24)

a = 0 b= 0

Po provedení operace souètu g( x, y ) = f (0,0) × h( x,0, y,0) + f (10 , ) × h( x,1, y,0) + f (2,0) × h( x,2, y,0) + f (01 , ) × h( x,0, y,1) + f (11 , ) × h( x,1, y,1) + f (2,1) × h( x,2, y,1)

(2.25)

+ f (0,2) × h( x,0, y,2) + f (12 , ) × h( x,1, y,2) + f 2,2) × h( x,2, y,2) Pro jednotlivé konkrétní body [x,y] výstupního obrazu poèítáme hodnoty g(x,y) postupným dosazováním x = 0,1,2; y = 0,1,2 a tak dostaneme postupnì hodnoty g(0,0), g(1,0), g(2,0), g(0,1), g(1,1), g(2,1), g(0,2), g(1,2), ..... g(2,2) z hodnot f(0,0) - f(2,2) pøes hodnoty h(x,a,y,b).

16

Pøíklad 2.1. Pro g(0,0), g(1,0) dostaneme g(0,0) = f (0,0) × h(0,0,0,0) + f (10 , ) × h(010 , , ,0) + f (2,0) × h(0,2,0,0) + f (01 , ) × h(0,0,01 , ) + f (11 , ) × h(0101 , , , ) + f (2,1) × h(0,2,01 ,) + f (0,2) × h(0,0,0,2) + f (12 , ) × h(010 , , ,2) + f 2,2) × h(0,2,0,2) g(10 , ) = f (0,0) × h(10 , ,0,0) + f (10 , ) × h(110 , , ,0) + f (2,0) × h(12 , ,0,0) + f (01 , ) × h(10 , ,01 , ) + f (11 , ) × h(1101 , , , ) + f (2,1) × h(12 , ,01 ,) + f (0,2) × h(10 , ,0,2) + f (12 , ) × h(110 , , ,2) + f 2,2) × h(12 , ,0,2) Hodnoty h(x,a,y,b) uspoøádáme do matice tak, aby pro g(0,0) byly hodnoty h(x,y) v prvním øádku matice, pro g(1,0) v druhém øádku, g(2,0) ve tøetím atd, a koneènì pro g(2,2) v posledním, devátém øádku. Dostaneme tak v pøípadì obrazu se tøemi øádky a tøemi sloupci následující matici koeficientù PSF s devíti øádky a devíti sloupci. æ h(0000) ç ç h(1000) ç h(2000) ç ç h(0010) H = ç h(1010) ç ç h(2010) ç h(0020) ç ç h(1020) ç h(2020) è

h(0100) h(1100) h(2100) h(0110) h(1110) h(2110) h(0120) h(1120) h(2120)

h(0200) h(1200) h(2200) h(0210) h(1210) h(2210) h(0220) h(1220) h(2220)

h(0001) h(1001) h(2001) h(0011) h(1011) h(2011) h(0021) h(1021) h(2021)

h(0101) h(1101) h(2101) h(0111) h(1111) h(2111) h(0121) h(1121) h(2121)

h(0201) h(1201) h(2201) h(0211) h(1211) h(2211) h(0221) h(1221) h(2221)

h(0002) h(1002) h(2002) h(0012) h(1012) h(2012) h(0022) h(1022) h(2022)

h(0102) h(1102) h(2102) h(0112) h(1112) h(2112) h(0122) h(1122) h(2122)

h(0202) ö ÷ h(1202) ÷ h(2202) ÷ ÷ h(0212) ÷ h(1212) ÷ ÷ h(2212) ÷ h(0222) ÷ ÷ h(1222) ÷ h(2222) ÷ø

Obr.2.3 Matice koeficientù PSF Uspoøádejme hodnoty f a g vstupního a výstupního obrazu z maticové formy 3´3 tzv. stohováním sloupcù do vektorové fomy 9´1 dostaneme æ ç ç ç ç ç f =ç ç ç ç ç ç ç è

æ g(0,0) ö ÷ ç , )÷ ç g(10 ç g(2,0) ÷ ÷ ç , )÷ ç g(01 , )÷ g = ç g(11 ÷ ç , )÷ ç g(21 ç g(0,2) ÷ ÷ ç , )÷ ç g(12 ç g(2,2) ÷ ø è

f (0,0) ö ÷ , )÷ f (10 f (2,0) ÷ ÷ , )÷ f (01 , )÷ f (11 ÷ , )÷ f (21 f (0,2) ÷ ÷ , )÷ f (12 f (2,2) ÷ø

17

(2.26)

Potom mù
eme (po zobecnìní na matici M´N) rovnici 2.17 napsat v maticovém tvaru g=Hf

(2.27)

Tato maticová rovnice je fundamentální rovnicí lineárního zpracování obrazu. H je transformaèní matice koeficientù impulzní odezvy PSF o rozmìru M2´N2 na pole Diraciových impulzù. Vektory f a g jsou rozmìru MN´1 vzniklé "stohováním" sloupcù matic f a g o rozmìru M´N. Matice H je slo
ena ze submatic, ka
dá o rozmìru M´N podle schéma na obr.2.4 ( pøíklad pro obraz rozmìru 3´3).

®b ®a

®a

®a

æ y = 0ö çç ÷÷ èb = 0 ø

æ y = 0ö çç ÷÷ èb =1ø

æ y = 0ö çç ÷÷ èb = 2 ø

¯ x

æ y = 1ö çç ÷÷ èb = 0 ø

æ y = 1ö çç ÷÷ èb = 1ø

æ y = 1ö çç ÷÷ èb = 2 ø

¯ x

æ y = 2ö çç ÷÷ èb = 0 ø

æ y = 2ö çç ÷÷ èb =1ø

æ y = 2ö çç ÷÷ èb = 2 ø

¯ x

¯ y

Obr.2.4 Schéma matice H

Pøíklad 2.2 Ze schéma na obr. 2.4 odvoïte submatici N12 (pro y = 1, b = 2). Zkontrolujte s rozepsaným rozvojem na obr. 2.3. Tato submatice je ve druhém øádku a tøetím sloupci ve schématu. Hodnoty y = 1, b = 2 se v ní nebudou mìnit, mìní se a v øádcích a x ve sloupcích. , , ) h(0112 , , , ) h(0,212 , , )ö æ h(0,012 ç ÷ N 12 = ç h(1012 , , , ) h(11 , ,12 , ) h(1212 , , , )÷ ç h(2,012 , , ) h(2112 , , , ) h(2,212 , , ) ÷ø è Zkontrolujeme výsledek s rozpisem na obr. 2.3.

2.6 Stohovací operátor Tento operátor dovoluje prezentovat matici N´N jako vektor N2´1 a obrácenì. Definujeme si vektor vn a matici Nn následujícím zpùsobem:

18

ö æ ÷ ç ÷ ç ç 1 0 ... 0 ÷ ÷ ç 0 1 ... 0 ÷ ç Nn = ç: : :÷ ÷ ç 1÷ ç0 0 ÷ ç ÷ ç ø è

0

æ0ö ç ÷ ç :÷ ç0÷ ç ÷ vn = ç 1 ÷ ç0÷ ç ÷ ç :÷ ç0÷ è ø

(2.28)

0

Rozmìr vn je N´1 a rozmìr Nn je N2´N. Pøedpokládejme matici f rozmìru N´N. Potom je vektor fs vzniklý stohováním z matice f vytvoøen vztahem N

fs =

åN f v n

(2.29)

n

n=1

Rozmìr vektoru fs je N2´1 a prakticky vznikne stohováním jednotlivých sloupcù matice f rozmìru N´N na sebe. Obrácenì matici f vytvoøíme z vektoru fs podle vztahu N

f=

å N fs v n

n

T

(2.30)

n=1

Pøíklad 2.3 Vypoèítejte první sèítanec (n = 1) nastohovaného vektoru fs matice f s pou
itím rovnice 2.29 pro následující matici æ1 2 3ö ç ÷ f = ç 5 7 11 ÷ . ç13 17 19 ÷ è ø

Podle rov 2.28

æ1ö ç ÷ v1 = ç 0 ÷ ç0÷ è ø

æ1 ç ç0 ç0 ç ç0 N 1 = ç0 ç ç0 ç0 ç ç0 ç0 è

19

0 1 0 0 0 0 0 0 0

0ö ÷ 0÷ 1÷ ÷ 0÷ 0÷ ÷ 0÷ 0÷ ÷ 0÷ 0 ÷ø

æ1ö ç ÷ f v1 = ç 5 ÷ ç13 ÷ è ø

æ1ö ç ÷ ç5÷ ç13 ÷ ç ÷ ç0÷ N 1 f v1 = ç 0 ÷ ç ÷ ç0÷ ç0÷ ç ÷ ç0÷ ç0÷ è ø

2.7 Vliv separability na strukturu transformaèní matice Separabilita linearního operátoru znamená,
e mù
eme prostorovou impulsní funkci PSF vyjádøit souèinem dvou funkcí, kdy první je závislá pouze na promìnné x (sloupcích navzorkovaného obrazu) druhá na promìnné y (øádcích navzorkovaného obrazu) (viz rov. 2.20). Pokud pøedpokládáme separabilní operátor (napø. separabilní je Fourierova transformace) a aplikujeme souèin hc( x, a ) × hr ( y,b ) v matici H, vidíme,
e uvnitø ka
dé submatice M´N jsou promìnné y,b konstantní a mù
eme èlen hr ( y,b ) vytknout pøed tuto submatici. Dostaneme následující tvar matice H (pøíklad pro obraz 3´3). æ æ hc00 ç ç ç hr 00ç hc10 ç hc20 ç è ç hc00 æ ç ç H = ç hr10ç hc10 ç ç hc20 è ç ç æ hc00 ç hr 20ç hc10 ç ç ç hc20 ç è è

hc01 hc11 hc21 hc00 hc11 hc21 hc01 hc11 hc21

hc02 ö æ hc00 hc01 ç ÷ hc12 ÷ hr 01ç hc10 hc11 ç hc20 hc21 hc22 ø÷ è hc02 ö æ hc00 hc01 ÷ ç hc12 ÷ hr11ç hc10 hc11 ç hc20 hc21 hc22 ÷ø è hc02 ö æ hc00 hc01 ç ÷ hc12 ÷ hr 21ç hc10 hc11 ç hc20 hc21 hc22 ø÷ è

hc02 ö æ hc00 hc01 ç ÷ hc12 ÷ hr 02ç hc10 hc11 ç hc20 hc21 hc22 ÷ø è hc02 ö æ hc00 hc01 ÷ ç hc12 ÷ hr12ç hc10 hc11 ç hc20 hc21 hc22 ø÷ è hc02 ö æ hc00 hc01 ç ÷ hc12 ÷ hr 22ç hc10 hc11 ç hc20 hc21 hc22 ÷ø è

hc02 ö ö ÷÷ hc12 ÷ ÷ hc22 ÷ø ÷ ÷ hc02 ö ÷ ÷ hc12 ÷ ÷ ÷ hc22 ÷ø ÷ hc02 ö ÷ ÷ hc12 ÷ ÷ ÷ hc22 ÷ø ÷ø

(2.31)

Ze schématu je zøejmé,
e matice H je vlastnì Kronekerùv souèin dvou matic hc( x, a ), hr ( y,b ) o rozmìrech 3´3. H = h c ( x , a ) Ä h r ( y ,b )

(2.32)

Na základì definièní rovnice (2.21) separabilní transformace je mo
né odvodit maticovou rovnici separabilní transformace obrazu f [1]. g( x, y ) = hc ( x, a ) f ( x, y ) hrT ( y,b )

(2.33)

Budeme pou
ívat zkrácený zápis g = hc f hrT . Všimnìme si,
e operace násobení se provádìjí postupnì s maticemi o rozmìrech N´N. To má za následek,
e provádíme pøi transformaci 2N 3 operací oproti N 4 pøi násobení neseparabilní matice H a vektoru f. Pøíklad 2.4 Pøesvìdète se o správnosti vztahu g = hc f hrT aplikováním separabilních matic hc a hr na matici f. æ1 2 3ö æ9 8 7ö ç ÷ ç ÷ hc = ç 4 5 6 ÷, hr = ç 4 5 6 ÷, ç 7 8 9÷ ç3 2 1÷ è ø è ø

20

æ1 2 3ö ç ÷ f = ç 5 7 11 ÷ ç13 17 19 ÷ è ø

Vypoèítáme matici H = hc Ä hr (ruènì nebo pomocí funkce KroneckerProduct v modulu Image Processing programu Mathematica), vynásobíme ji vektorem matice f a tak dostaneme výsledný vektor g. Potom pomocí programu Mathematica vypoèítáme g pomocí g = hc f hrT . Mìli bychom v obou pøípadech dostat stejný výsledek æ 1560 1027 366 ö ç ÷ g = ç 3390 2239 792 ÷ ç 5220 3451 1218 ÷ è ø Pøíklad 2.5 Pro obraz z pøíkladu 2.3 zjistìte transformaèní matici H a výsledný filtrovaný obraz s maskou 3´3 pro prùmìrování se zvýšenou vahou støedního pixelu (hodnota 2). Pro okrajové pixely pøedpokládejme rozšíøení obrazu, jako by se v obou smìrech periodicky opakoval. f 22 f 02

f 20 f 00

f 21 f 01

f 22 f 02

f 20 f 00

f 12 f 22

f 10 f 20

f 11

f 12

f 10

f 02

f 00

f 21 f 01

f 22 f 02

f 20 f 00

Vyhlazený pixel g00 (odpovídá vstupnímu pixelu f00): g 00 =

1 ( f 22 + f 20 + f 21 + f 02 + 2 f 00 + f 01 + f 12 + f 10 + f 11) 10

Vyhlazený pixel g00 g10 =

1 ( f 02 + f 00 + f 01 + f 12 + 2 f 10 + f 11 + f 22 + f 20 + f 21) 10

První øádek matice H tedy bude (v poøadí f00, f10, f20, f01, ..... f22): 2,1,1,1,1,1,1,1,1, druhý øádek 1,2,1,1,1,1,1,1,1. Podobnì se odvodí další øádky pro g20, g01, ..... g22. Výsledkem je následující maticová rovnice a vyhlazený obraz. æ2 1 1 æ g 00 ö ç ç ÷ ç1 2 1 ç g10 ÷ ç1 1 2 ç g 20 ÷ ç ç ÷ ç1 1 1 ç g 01 ÷ ç g11 ÷ = 1 ç 1 1 1 ç ÷ 10 ç ç1 1 1 ç g 21 ÷ ç1 1 1 ç g 02 ÷ ç ç ÷ ç1 1 1 ç g12 ÷ ç1 1 1 ç g 22 ÷ è è ø

1 1 1 2 1 1 1 1 1

1 1 1 1 2 1 1 1 1

1 1 1 1 1 2 1 1 1

1 1 1 1 1 1 2 1 1

1 1 1 1 1 1 1 2 1

21

1ö æ 1 ö æ 7,9 ö ç ÷ ÷ ç ÷ 1÷ ç 5 ÷ ç 8,3 ÷ ÷ ç 91 ÷ ç , ÷ 1 13 ç ÷ ÷ ç ÷ 1÷ ç 2 ÷ ç 8,0 ÷ ÷ ÷ ç = ç 8,5 ÷ 1 ´ 7 ç ÷ ÷ ç ÷ 1 ÷ ç17 ÷ ç 9,5 ÷ ÷ ç 81 ÷ ç , ÷ 1 3 ç ÷ ÷ ç ÷ 1 ÷ ç 11 ÷ ç 8,9 ÷ ç 9.7 ÷ ÷ ÷ ç 2 ø è19 ø è ø

Na závìr tohoto tématu shrneme problémy, které øeší lineární metody zpracování obrazu: • máme obraz f a hledáme matici h(x,a,y,b) (pøípadnì hc a hr) pro zdokonalení obrazu (image enhacement) • máme obraz f a hledáme matici h(x,a,y,b) (pøípadnì hc a hr) takové, aby matice g byla reprezentována menším poètem bitù, ani
se výraznì zhorší rozlišení (image compression) • máme obraz g (degradovaný napø. procesem jeho získání) a hledáme matici h(x,a,y,b) pro rekonstrukci obrazu f (image restoration) • máme obraz f a hledáme matici h(x,a,y,b) (pøípadnì hc a hr) takovou, aby mìl výstupní obraz g zvýraznìny nìkteré rysy (napø. hrany) - úpravy pro machine vision).

22

3. Integrální transformace obrazu Integrální transformace dovolují vyjádøit obraz jako lineární superpozici (obvykle souèet) více tzv. elementárních obrazù. Tìmito transformacemi se obraz pøevádí z prostorové oblasti do frekvenèní oblasti (jedná se o prostorové frekvence s rozmìrem 1/m). Potom mù
eme obrazy zpracovávat ve frekvenèní oblasti pomocí tzv. frekvenèních filtrù, co
je v nìkterých pøípadech výhodnìjší. Po provedené filtraci se obraz pøevede zpìtnou transformací zpìt do prostorové oblasti. Na obr.3.1 je blokovì znázornìno zpracování v obou oblastech. V s tupní obraz

P øímá trans formace

P ros torový filtr

V ýs tupní obraz

F rekvenèní filtr

Z pìtná trans formace

Obr.3.1 Zpracování obrazu v prostorové a frekvenèní oblasti Zpracování v prostorové oblasti (prostorový filtr) se provádí pomocí lineárních kombinací hodnot jasu pixelù vstupního obrazu s koeficienty h(x-a,y-b) impulsní odezvy, kterou nazýváme lokálním prostorovým filtrem. Základním nástrojem v pøípadì prostorovì invariantní transformace je konvoluce g( x, y ) = f ( x, y ) * h( x - a , y - b )

(3.1)

Zpracování ve frekvenèní oblasti (frekvenèní filtr) se provádí omezováním frekvenèního rozsahu obrazu v rùzných oblastech (nízké, støední, vysoké frekvence). Základní operací je násobení transformovaného obrazu F(u,v) funkcí H(u,v), kterou nazýváme frekvenèní pøenos MTF (Modulation Transfer Function). Tím dostaneme transformovaný výstupní obraz G(u,v), který mù
eme zpìtnou transformací pøevést do prostorové oblasti. G ( u, v ) = F( u, v ) × H ( u, v )

(3.2)

Frekvenèní pøenos H(u,v) získáme Fourierovou transformací funkce PSF, v maticové formì koeficientù h(x-a, y-b) do frekvenèní oblasti.

3.1 Základní teorie Pøi transformaci obrazù do frekvenèní oblasti se budeme zabývat lineárními unitárními transformacemi. Unitární transformace je speciální pøípad lineární transformace a znamená,
e její separabilní transformaèní matice hc, hr (obecnì komplexní) jsou unitární. Matice U se nazývá unitární, pokud k ní inverzní matice U–1 je komplexnì sdru
ená k transponované matici UT. Potom platí U -1 = U T * ,

UU T * = I

23

(3.3)

U reálných matic platí UT*=UT a tedy za pøedpokladu unitárnosti platí U -1=UT (inverzní matice je rovna transponované matici) øíkáme,
e U je ortogonální matice. Odpovídající transformace se potom nazývají ortogonálními transformacemi. Pokud f a g oznaèují vektorové reprezentace vstupního a výstupního obrazu, potom platí následující vztahy pro dvojrozmìrnou unitární transformaci: g = Af ,

f = Bg ,

B = A -1 = A T*

(3.4)

kde A je tranformaèní matice pøímé transformace, B je transformaèní matice inverzní transformace, AT* je transponovaná a konjugovaná matice A. Pro reálné transformaèní matice pak platí B=AT, matice inverzní transformace je rovna transponované matici pøímé transformace a tedy f = ATg. Rozvoj obrazu na vektorové souèiny Vektorový souèin dvou vektorù

ui vj T

æ ui1 vj 1 ui1 vj 2 ... ui1 vjN ö æ ui1 ö ÷ ç ç ÷ ç ui 2 vj 1 ui 2 vj 2 ... ui 2 vjN ÷ ç ui 2 ÷ = ç ÷ ( vj 1 vj 2 .. vjN ) = ç : : : ÷ : ÷÷ çç çç ÷÷ è uiNvj 1 uiNvj 2 ... uiNvjN ø è uiN ø

(3.5)

Z pøedchozí kapitoly víme,
e lineární separabilní transformaci obrazu lze vyjádøit ve tvaru g = hc f hrT

(3.6)

Vyjádøíme matice hc, hrT pomocí jejich sloupcových a øádkových vektorù hc = ( u1 u2 .... uN )

(3.7)

ö ÷ ÷ ÷ ÷ ÷ ø

(3.8)

æ v1 T ç T ç v2 T hr = ç : ç T ç vN è

Potom dosazením do (3.6)

g = ( u1 u2 ... uN )

æ v1 T ç T ç v2 fç : ç T ç vN è

24

ö ÷ ÷ ÷ ÷ ÷ ø

(3.9)

Matici f mù
eme rozepsat jako souèet N2 matic rozmìru N´N podle následujícího schéma æ ç ç f =ç çç è

f 11 0 ... 0 ö æ 0 ÷ ç 0 0 ... 0 ÷ ç 0 + : : :÷ ç : ÷ ç 0 0 ... 0 ÷ø çè 0

0ö æ 0 0 ... ÷ ç 0÷ ç 0 0 ... + + .... ç: : :÷ ÷÷ çç 0ø è 0 0 ...

f 12 ... 0 ... : 0 ...

0 ö ÷ 0 ÷ : ÷ ÷ fNN ÷ø

(3.10)

Potom mù
eme z rovnic 3.9 a 3.10 odvodit vztah pro transformovaný obraz [1] N

N

i =1

j =1

g = å å fij ui vj T

(3.11)

Èlen fij mù
eme pøesunout pøed vektorový souèin, proto
e se jedná pro ka
dou kombinaci indexù i,j o násobení skalárem. Tato rovnice vyjadøuje rozvoj transformovaného obrazu g na èleny slo
ené z vektorových souèinù sloupce ui se sloupcem vj transformaèních matic hc a hr, vá
ených koeficienty fij. Tyto souèiny mohou být interpretovány jako elementární obrazy a tvoøí dekompozici transformovaného obrazu g na tyto elementární obrazy. Rozvoj pùvodního obrazu f na vektorové souèiny se odvodí podobným zpùsobem z rovnice

( )

f = hc-1 × g × hrT

-1

(3.12)

Potom po odvození bude rozvoj pùvodního obrazu [1] N

N

i =1

j =1

f = å å gij ui vj T

(3.13)

( )

kde ui a vj jsou sloupcové a øádkové vektory matic hc-1 a hrT

-1

.

Pøíklad 3.1. Na základì zadání matic hc, hr a f z pøíkladu 2.3 vypoèítejte elementární obraz pro i=1, j=2 s pou
itím vztahu 3.11.

f 12 = 2 ,

æ1 2 3ö ç ÷ hc = ç 4 5 6 ÷ , ç 7 8 9÷ è ø

EO12 = f 12 × u1 × v2

T

hr

T

æ9 4 3ö ç ÷ = ç8 5 2÷ ç 7 6 1÷ è ø

æ 16 10 4 ö æ1ö ç ç ÷ ÷ = 2 × ç 4 ÷ (8 5 2) = ç 64 40 16 ÷ ç112 20 28 ÷ ç 7÷ è è ø ø

V programu Mathematica otevøete z výukových pøíkladù soubor Elemobr.nb a sledujte jednotlivé kroky výpoètu dalších slo
ek a zkoušku seètením tìchto slo
ek.

25

3.2 SVD rozklad matice obrazu Pøi pøenosech obrazù vzniká problém s velikostí datového souboru, který obraz reprezentuje. Obecnì lze tento problém øešit transformací matice pùvodního obrazu f s N2 elementy pou
itím takových transformaèních matic hc a hr,
e matice g takto transformovaného obrazu bude diagonální. Potom je pùvodní obraz f reprezentován pouze N nenulovými elementy matice g a pou
itými transformaèními maticemi. Jak tedy takovou transformaci provést? Z teorie maticového poètu je známo,
e reálnou matici f rozmìru N´N, která má hodnost r mù
eme rozlo
it na souèin 1

f = U L2 V T

(3.14) 1

kde U,V jsou ortogonální matice rozmìru N ´r a L2 je diagonální matice rozmìru r´ r. Pøi transformaci rozlo
íme matici f podle pøedchozího vztahu na diagonální matici násobenou zleva transformaèní maticí U a zprava transformaèní maticí VT. Tato transformace se nazývá SVD transformace (Singular Value Decomposition), kde L je matice vlastních èísel a U, V matice vlastních vektorù. My budeme rozkládat matici f, která reprezentuje obrazovou funkci f(x,y). Výpoèet matic U, V a L pro rozklad matice f Vytvoøíme z rovnice 3.14 souèin ffT za pøedpokladu,
e U a V jsou ortogonální matice 1

1

1

1

ff T = UL2V T ×VL2U T = UL2 L2U T = ULU T

(3.15)

Z pøedchozí rovnice vyplývá,
e matice ffTje charakterizována diagonální maticí L, která obsahuje r vlastních èísel matice ffT a maticí U tvoøené z vlastních vektorù matice ffT. Podobnì f T f = VLV T

(3.16)

Diagonální matice L obsahuje r vlastních èísel matice fTf a matice V je slo
ena z vlastních vektorù matice fTf. Aproximace obrazu pomocí SVD SVD obrazu f je jeho rozvoj na vektorové souèiny, kdy tyto vektory jsou vlastní vektory matic ff a fTf násobené koeficienty, co
jsou vlastní èísla tìchto matic. S pou
itím rovnice 3.13 se dá odvodit transformovaný obraz jako souèet elementárních obrazù [1]. T

r

f = å li 2 ui vi T 1

(3.17)

i =1

Násobíme pouze vektory se stejnými indexy, proto
e koeficienty l jsou nenulové pouze pro i=j (matice L je diagonální). Pøi diagonalizaci matice f dochází k tomu,
e nìkteré hodnoty vlastních èísel jsou malé (blí
í se k nule). Pokud tyto èleny zanedbáme a vezmeme do zpracování jen k < r èlenù rozvoje, dostaneme pro aproximovaný obraz k

f k = å l i 2 u i vi T 1

(3.18)

i =1

26

Dùsledkem je menší poèet elementárních obrazù a za urèitých podmínek i menší mno
ství dat v souboru transformovaného obrazu oproti pùvodnímu obrazu f. Zanedbáním malých hodnot koeficietù rozvoje vzniká chyba aproximace. Tato chyba se poèítá jako norma matice D = f - fk =

r

ål

i

1 2

uiviT

(3.19)

i = k +1

Po odvození [1] D =

r

ål

(3.20)

i

i = k +1

Tedy chyba aproximace je rovna souètu zanedbaných vlastních èísel matic ffT a fTf. æ 1. 0. 3.ö Pøíklad 3.2 ç ÷ Vypoèítejte pomocí SVD elementární obrazy obrazu popsaného maticí ç 2. 1. 1. ÷. ç 4. 0. 1. ÷ è ø Pou
ijte program Mathematica pro výpoèet elementárních obrazù. Proveïte zkoušku výpoètu jejich seètením podle rovnice 3.18. (Otevøít SVDtest1 z výukových pøíkladù a sledovat jednotlivé kroky výpoètu). Vyu
ití SVD transformace ke kompresi obrazu pro efektivnìjší pøenos spoèívá v tom,
e se pøenášejí pouze významná vlastní èísla a k nim nále
ející vlastní vektory matic ffT a fTf. Ty se potom na pøijímací stranì transformují na výsledný obraz (rov. 3.18).

3.3 Fourierova transformace obrazu Z teorie signálù je známo,
e ka
dý spojitý periodický signál s peridou T, tedy s kruhovou frek2p vencí w = , lze s urèitou nepøesností vyjádøit koneèným souètem harmonických signálù (sinuT sových a kosinusových slo
ek) rùzných amplitud s frekvencemi rovnými celistvým násobkùm n ×2p 1 2p 4p základní frekvence f = , tedy kruhovými frekvencemi w1 = , w2 = , ........ wn = . T T T T Na obr.3.2 je zobrazeno skládání obdélníkového signálu z harmonických signálù [5]. Proto
e pro harmonické signály platí vztah e - jj = cos j - j sin j

(3.21)

mù
eme pro periodický signál napsat tento souèet ve tvaru ¥

f ( t ) = å F(wn ) e n= 0

jn

2p ×t T

¥ 2p 2p ö æ = å F(wn )ç cos n t + j sin n t ÷ T ø T n= 0 è

(3.22)

kde F(wn) jsou komplexní èísla, která vyjadøují amplitudu a fázi jednotlivých harmonických slo
ek této sumy. Tento vztah vyjadøuje zpìtnou Fourierovu transformaci.

27

Obr.3.2 Skládání obdélníkového signálu z harmonických slo
ek

Jednotlivé harmonické slo
ky poèítáme ze vztahu 1 F(wn ) = T

T

ò f (t) e 0

- jn

2p ×t T

1 dt = T

T

2p

2p

ò f ( t )(cos n T t - j sin n T

t ) dt

(3.23)

0

kde n = 0, 1, 2,....n pro F(w0), F(w1), F(w2) .....F(wn), tedy w0 = 0, w1 =

n ×2p 2p 4p . , w2 = … .wn = T T T

Tento vztah vyjadøuje pøímou Fourierovu transformaci. Øíkáme,
e FT pøevádí èasovou funkci f(t) do frekvenèní oblasti. Slo
ky F(wn) jsou komplexní èísla. Mají tedy reálnou a imaginární èást F(wn) = Re(wn)+jIm(wn). Amplitudy a fáze tìchto slo
ek F(wn ) = Re(wn ) 2 + Im(wn ) 2 y (wn ) = arctg

Im(wn ) Re(wn )

28

(3.24) (3.25)

Obr.3.3 Amplitudové spektrum obdélníkového signálu Závislost |F(wn)| a Y(wn) na frekvencích wn se nazývá amplitudové spektrum a fázové spektrum. Druhá mocnina amplitudy P(wn) = |F(wn)|2 se nazývá výkonová spektrální hustota. Na obr.3.3 je znázornìn pøíklad spektra amplitud obdélníkového signálu s periodou T, tedy w1 = 2p/T. Pokud chceme aplikovat Fourierovu transformaci v prostoru (nezávisle promìnná je prostorová souøadnice), nahradíme èas t prostorovou promìnnou x, periodu T prostorovou periodou X a frekvenci wn prostorovou frekvencí un. Potom 1 F( un ) = X kde n = 0, 1, 2,....n a un =

X

ò f (x) e

- jn

2p ×x X

dx

(3.26)

0

n ×2p . X

Pokud pracujeme s digitalizovaným obrazem, potom musíme aplikovat tzv. diskrétní Fourierovu transformaci - DFT. Pøedpokládejme napøíklad jednorozmìrný diskrétní (vzorkovaný) obdélníkový prostorový signál (obr.3.4) s N vzorky (ekvivalentní periodì X), který se periodicky opakuje v jednom rozmìru.

Obr.3.4 Diskrétní jednorozmìrná obdélníková funkce Integrál nahradíme sumou a periodu X poètem vzorkù, oznaèení frekvencí un pøímo promìnnou u, která nabývá postupnì hodnot 0,1,2, .... N. Potom je jednorozmìrná DFT v prostoru definována rovnicí F( u) =

1 N

N -1

å

f (x) e

x=0

29

-j

2p u ×x N

(3.27)

Inverzní jednorozmìrná DFT 2p

j u ×x 1 N -1 (3.28) f (x) = F( u) e N å N u= 0 Slo
ka F(0) je tzv. stejnosmìrná slo
ka a je to v podstatì støední hodnota diskrétního signálu.

F(0) =

1 N

N -1

1 N

å f (x) = x=0

( f (0) +

f (1) + K + f ( N - 1))

(3.29)

Slo
ka F(1) je tzv. první harmonická diskrétního signálu o frekvenci 1/N. F(1) =

1 N

N -1

å

f (x) e

-j

x=0

2p ×x N

=

1 N

4p 2 ( N -1)p 2p -j -j -j æ N ç f (0) + f (1)e N + f (2)e N +K+ f ( N - 1)e ç è

ö ÷ ÷ ø

Pøíklad 3.3 Vypoèítejte frekvenèní slo
ky F(0), F(1),.... F(7) diskrétní impulsové funkce pro poèet vzorkù N = 8. Do programu Mathematica zadáme vektor x = {1,1,1,1,0,0,0,0}, který charakterizuje vstupní impulzovou funkci. Pomocí pøíkazu Fourier[x] vypoèítáme výstupní vektor (zaokrouhleno na 2 místa) V={1.41+0i, 0.35+0.85i, 0+0i, 0.35+0.15i, 0+0i, 0.35-0.15i, 0+0i, 0.35-0.85i}, který charakterizuje frekvenèní slo
ky Fourierova rozvoje. Pomocí funkce ListPlot[v] zobrazíme výsledek graficky. Zadáme znovu zaokrouhlený vektor a pomocí funkce InverseFourier[v] získáme pùvodní impulsovou funkci (bude mírnì zkreslená kvùli zaokrouhlení). Na obr.3.6-3.8 je zobrazen výsledek v programu Mathematica.

Obr. 3.6 Graf diskrétní impulzové funkce

Obr.3.7 Graf DFT diskrétní impulzové funkce

Obr.3.8 IDFT diskrétní impulzové funkce

DFT digitálního obrazu Pro 2D digitální obraz f(x,y) rozmìru M´N je pøímá DFT definována rovnicí f ( u, v ) =

1 MN

M -1 N -1

å å f ( x, y ) e

- ju

2p 2p ×x - jv × y M N

x=0 y=0

=

1 MN

M -1 N -1

å å f ( x, y ) e

vy -2pj ( ux + ) M N

(3.31)

x=0 y=0

kde x,y jsou prostorové souøadnice pùvodního obrazu, u,v prostorové frekvence diskrétních harmonických signálù, na které je pùvodní obraz rozlo
en. Z rovnice je zøejmá separabilita DFT.

30

Obr.3.9 DFT dvojrozmìrné funkce ve smìru x Místo obvyklého oznaèení výstupního obrazu g volíme oznaèení f , proto
e výstup z DFT není vlastnì obraz, my si jen jednotlivé slo
ky zobrazujeme v rovinì tak,
e nejni
ší frekvence jsou uprostøed a smìrem k okrajùm se zvyšují. Pøedpokládáme pøitom,
e se motiv obrazu periodicky opakuje v obou prostorových souøadnicích, abychom vyhovìli podmínkám definice obecné Fourierovy transformace. Pokud si zobrazíme jednotlivé slo
ky Fourierova obrazu ve frekvenèní rovinì, dostaneme “obraz” M´N frekvenèních slo
ek. Tento “obraz” bude mít stejný poèet pixelù jako originál, pouze tyto pixely nebudou pøedstavovat hodnoty jasu, ale amplitudy prostorových frekvencí. Na obr. 3.9 je zobrazena impulzní funkce a její DFT ve smìru souøadnice její zmìny. Z obrázku je zøejmé,
e obraz spektra obsahuje polovinu nadbyteèných hodnot (symetrie kolem støedu). Inverzní DFT zkonstruovaná z harmonických slo
ek f ( u, v ) je potom f ( x, y ) =

1 MN

M -1 N -1

å å f ( u, v ) e

vy 2p j ( ux + ) M N

u= 0 v = 0

Obr. 3.10 Jednoduché obrazy a "obrazy" jejich DFT

31

(3.32)

Na obr. 3.10 jsou obrazy se sinusovým a nesinusovým (impulzovým) motivem v jednom smìru a obrazy jejich DFT normované do rozsahu 0-256. Na obr. 3.11 je prezentován obraz DFT konkrétního monochromatického obrazu. Vyšším hodnotám amplitud jednotlivých frekvencí odpovídá tmavší odstín.

Obr.3.11 DFT èernobílého obrazu

DFT v maticové formì Vytvoøíme matici U pro N´N obraz s prvky [1] 2p

1 - j N ×x a (3.33) Ux , a = e N kde x se mìní v rozmezí od 0 do N-1 ve sloupcích a a v tom samém rozmezí v øádcích. Tato komplexní matice reprezentuje jak matici hr tak i hc, proto
e u Fourierovy transformace platí vztah hr = hc. Polo
íme tedy hr = hc = U, matice U potom pøedstavuje jádro DFT. Víme,
e platí vztah g = hc f hrT , tedy g = Uf U T

(3.34)

_

Po zámìnì g a f mù
eme psát f = UfU T

(3.35)

Proto
e je matice U symetrická, tedy platí UT=U, potom DFT obrazu f v maticové formì je f = UfU

(3.36)

Zpìtná DFT transformace je potom (za pøedpokladu,
e U je komplexní) f =U* fU*

(3.37)

32

Pøíklad 3.4 Z rovnice 3.33 odvodíme matici DFT pro obraz velikosti 4´4: æ e - j 4 ×0 ç 2p - j ×0 1 çe 4 U = ç - j 2 p ×0 2 e 4 ç 2p ç e - j 4 ×0 è 2p

Èlen U2,3 bude roven e prvky matice. Výsledkem bude matice

- j 24p ´ 6

- j 2 p ×0

e 4 - j 2 p ×1 e 4 e e

e

- j 24p ×0 -j

2p ×2 4

e - j 2 p ×4 e 4

- j 24p ×2 - j 24p ×3

e

- j 24p ×6

ö ÷ -j ÷ e - j 24p ×6 ÷ e ÷ - j 24p ×9 ÷ e ø e

- j 24p ×0

2p ×3 4

= e - j ×3p = e - j ×p = cos p - j sin p = -1 . Podobnì vypoèítáme ostatní

æ 12 ç1 ç U = ç 12 çç 12 è2

1 2

ö ÷ ÷ - 12 ÷ ÷ - 2j ø÷

1 2

- 12

-

j 2

1 2 j 2

1 2

1 2

- 12

j 2

Pøíklad 3.5 Pou
ijte matici DFT z pøíkladu 3.4 pro výpoèet transformace následujícího obrazu æ0 ç ç0 f =ç 0 çç è0

0 1 1 0

0 1 1 0

0ö ÷ 0÷ 0÷ ÷ 0 ÷ø

Vypoèítáme souèin UfU, výsledkem je matice DFT æ 1 ç ç-1 f =ç 2 0 ç ç- 1 + è 2

- 12 j 2

j 2

0 j 2

1 2

j 2

0 - 12 + 1 0 2 0 0 0 - 2j

Oddìlíme reálnou a imaginární slo
ku matice f æ 1 ç 1 çRe( f ) = ç 2 0 çç 1 è- 2

- 12 0 - 12 ö ÷ 0 0 12 ÷ 0 0 0 ÷ ÷ 1 0 0 ÷ø 2

æ 0 ç 1 çIm( f ) = ç 2 0 çç 1 è 2

- 12 0 12 ö ÷ 1 0 0 ÷ 2 0 0 0 ÷ ÷ 0 0 - 12 ÷ø

33

j 2

ö ÷ ÷ ÷ ÷ ÷ ø

Elementární obrazy DFT Ka
dému prvku matice U odpovídá elementární obraz diskretní kosinusovky (reálná èást komplexní slo
ky) a diskrétní sinusovky (imaginární èást komplexní slo
ky) s prostorovou frekvencí závislou na poloze prvku v matici (nízké frekvence odpovídají prvku s nízkými indexy, vysoké frekvence prvkùm s vysokými indexy). Tyto elementární obrazy získáme jako vzájemné vektorové souèiny odpovídajících øádkù a sloupcù matice U. Ka
dý elementární obraz rozvoje DFT získáme také jako vektorový souèin dvou libovolných øádkù matice U (i stejných), proto
e matice U je symetrická. Potom tedy bude poèet tìchto elementárních obrazù 2N2 jestli bude rozmìr matice N´N (poèítají se i dvojice v opaèném poøadí). Na obr. 3.12 je zobrazen rozvoj DFT matice U (reálné a imaginární èásti) obrazu o rozmìru 4´4 na elementární obrazy. Hodnoty v ka
dém obraze jsou kvùli zobrazení z rozmezí -1/4, +1/4 rozšíøeny na interval 0-255.

Obr. 3.12 Reálná a imaginární èást elementárních obrazù DFT

Pøíklad 3.6. Vypoèítejte elementární kosinovou (reálnou) slo
ku I1,0 obrazu z DFT rozvoje z pøíkladu 3.4. Provedeme vektorový souèin prvního øádku a nultého sloupce reálné slo
ky matice U. æ 12 ö ç ÷ ç 0 ÷ 1 ç - 1 ÷( 2 çç 2 ÷÷ è 0 ø

1 2

1 2

æ 14 ç ç 0 1 2) = ç 1 çç 4 è 0

1 4

1 4

0 - 14

0 - 14

0

0

ö ÷ 0 ÷ - 14 ÷ ÷ 0 ÷ø 1 4

Matice koresponduje s druhým vzorkem prvního sloupce kosinové slo
ky (levý obrázek) v obr.3.12. Pokud pøehodíme v souèinu oba vektory, dostaneme slo
ku I0,1, která koresponduje s druhým vzorkem prvního øádku (symetrie kolem hlavní diagonály). Elementární obrazy vlastního transformovaného obrazu potom získáme násobením ka
dého vektorového souèinu rozvoje DFT odpovídající hodnotou fi,j matice pùvodního obrazu f podle rovnice 3.11.

34

Konvoluèní teorém Dùvodem popularity DFT v praxi je jednoduchý vztah mezi operací konvoluce dvou obrazù (obecnì 2D funkcí) a jejich Fourierovými rozvoji ve frekvenèní oblasti. Diskrétní konvoluce je definována vztahem g( x, y ) = f ( x, y ) * h( x, y ) =

N -1 N -1

å å f (a ,b ) × h( x - a , y - b )

(3.38)

a = 0 b= 0

Konvoluèní teorém øíká,
e konvoluci obrazu s impulzní odezvou h mù
eme vyjádøit jako zpìtnou Fourierovu transformací souèinu DFT obrazu a DFT impulzní odezvy h. V nìkterých pøípadech zpracování obrazu je tento postup jednodušší, ne
pøímý výpoèet konvoluce. f ( x, y ) * h( x, y ) = F -1 [F( u, v ) × H ( u, v )]

(3.39)

Prakticky to znamená,
e na vstupní obrazovou funkci a impulzní odezvu aplikujeme pøímou Fourierovu transformaci. Potom tyto transformované funkce vynásobíme, a tím získáme Fourierovu transformaci výstupního obrazu. Inverzní FT získáme obraz v prostorové oblasti. Pro H(u,v) potom tedy platí H ( u, v ) = F[h( x, y )]

(3.40)

Funkce H(u,v) se nazývá frekvenèní pøenos MTF (Modulation Transfer Function). Druhým dùvodem pou
ívání DFT je,
e pøi aproximaci obrazu omezeným poètem elementárních obrazù se dopouštíme menší aproximaèní chyby ne
u jiných transformací. Na základì konvoluèního teorému se provádí filtrace ve frekvenèní oblasti. Podrobnìji se tomuto tématu budeme vìnovat v kapitole 5.

3.4 Diskrétní kosinová transformace Z definice DCT je zøejmá základní odlišnost od Fourierovy transformace a to,
e kosinová transformace je reálná, co
je její výhodou. Tato transformace má uplatnìní pøedevším v oblasti kódování a komprese obrazu a pou
ívá se pøedevším pøi JPEG kompresi. Obecnì je Fourierova transformace komplexní, dá se ale dokázat,
e Fourierova trasformace sudé funkce je také reálná. Pokud provedeme sudé prodlou
ení transformované funkce (rozšíøení do záporných hodnot kolem bodu 0), mù
eme odvodit DCT z Fourierovy transformace. Potom pøímá dvojrozmìrná DCT [2,3]

F( u, v ) =

N -1 N -1 2 (2 y + 1)p é (2x + 1)p K ( u)K ( v ) å å f ( x, y )êcos u × cos 2N 2N N x=0 y=0 ë

kde normovací koeficienty K ( u) = K ( v ) =

ù vú û

(3.41)

2 1 pro u¹0,v¹0 a K ( u) = K ( v ) = pro u=v=0. N N

35

Inverzní DCT f ( x, y ) =

2 N

N -1 N -1

å å K ( u)K ( v )F( u, v )éêëcos u= 0 v = 0

(2 y + 1)p (2x + 1)p u × cos 2N 2N

ù vú û

(3.42)

Transformaèní matice DCT ì ï ï Tpq = í ï ïî

1 N

pro p = 0, 0 £ q £ N - 1

p ( q + 1) × p 2 cos N 2N

pro 1 £ p £ N - 1, 0 £ q £ N - 1

Potom pøímá DCT f =T f T T Inverzní DCT f =T T f T Pøi JPEG kompresi obrazu se po provedení DCT transformace provádí dìlení frekvenèních slo
ek transformovaného obrazu tzv. kvantizaèními koeficienty. Tím se èást tìchto slo
ek pøiblí
í svojí velikostí nule a na nulu se následnì zaokrouhlí. Následuje CCITT komprese, která zmenšuje fyzickou velikost souboru reprezentujícího transformovaný obraz. Po pøenosu se frekvenèní obraz pomocí inverzní DCT pøevede do prostorové oblasti.

3.5 Haarova transformace Další funkce, které mù
eme pou
ít pro transformaci obrazu do elementárních obrazù jsou Haap rovy funkce. Tyto funkce nabývají hodnot 0, ±1, 2 p = 0,1, 2,K a jsou definovány vztahy H 0( t ) = 1 pro 0 £ t £ 1 ìï1 pro 0 £ t £ 12 H 1( t ) = í ïî-1 pro 12 £ t £ 1 ì 2 p pro n £ t £ n+ 0. 5 2p 2p ï ïï p H 2 p+ n ( t ) = í- 2 pro n+20p. 5 £ t £ n2+p1 ï ï0 jinde ïî kde p = 1, 2, 3, … a n = 0, 1, … 2p - 1.

36

(3.43)

Potom pøímá Haarova transformace v maticovém tvaru g$ =

1 H f HT N

(3.44)

Zpìtná Haarova transformace v maticovém tvaru f =

1 T H g$ H N

(3.45)

Pøíklad 3.7. Výpoèet Haarovy transformaèní matice 4×4 H 0( t ) = 1 pro 0 £ t £ 1 ìï1 pro 0 £ t £ 12 H 1( t ) = í ïî-1 pro 12 £ t £ 1 Pro p = 1 bude n nabývat hodnot 0 a 1. Pøípad p = 1, n = 0: ì 2 pro 0 £ t £ 14 ï ï H 2( t ) = í- 2 pro 14 £ t £ 12 ï pro 12 £ t £ 1 ï0 î Pøípad p = 1, n = 1: ì0 pro 0 £ t £ 12 ï ï H 3( t ) = í 2 pro 12 £ t £ 34 ï ïî- 2 pro 34 £ t £ 1 Na obr.3.13 jsou graficky znázornìny Haarovy funkce pro obraz 4´4. Pokud uspoøádáme hodnoty Haarových funkcí po øádcích od H0 po H3 dostaneme výslednou Haarrovu transformaèní matici. æ ç ç H =ç çç è

1 1 2 0

1 1 - 2 0

1 1 ö ÷ -1 -1 ÷ 0 0 ÷ ÷ 2 - 2 ÷ø

37

(3.46)

Obr. 3.13 Haarovy funkce pro obraz 4´4

Podobnì mù
eme vypoèítat Haarovu transformaèní matici pro obraz 8´8. æ ç ç ç ç ç H=ç ç ç ç çç è

1 1 2 0 2 0 0 0

1 1 2 0 -2 0 0 0

1 1

1 1

- 2 0 0 2 0 0

- 2 0 0 -2 0 0

1 -1 0 2 0 0 2 0

1 1 -1 -1 0 0 2 - 2 0 0 0 0 -2 0 0 2

1 ö ÷ -1 ÷ 0 ÷ ÷ - 2÷ 0 ÷ ÷ 0 ÷ 0 ÷ ÷ -2 ÷ø

(3.47)

Elementární obrazy Haarovy transformace vytvoøíme pomocí vektorových souèinù øádkù transformaèní matice mezi sebou. Na obr.3.14 je zobrazen rozvoj 8´8 Haarových elementárních obrazù. Z uspoøádání pixelù v Haarových elementárních obrazech vyplývá jedna dùle
itá vlastnost. Vyšší øády elementárních obrazù obsahují stejný vzor hodnot pixelù pro rùzné èásti obrazu. To je vidìt v obr.3.14 vpravo nahoøe. Pokud nás nezajímají detaily v nìkterých èástech obrazu mù
eme odpovídající elementární obrazy zanedbat. Haarovy funkce nám umo
òují rekonstruovat rùzná

38

místa pùvodního obrazu s rùznou úrovní detailù. To je vlastnost, která se vyu
ívá u tzv. wavelet (vlnkových) transformací.

Obr.3.14 Haarovy elementární obrazy pro obraz 8x8 Elementární obraz EO1,7 dostaneme jako vektorový souèin 1. a 7. øádku uspoøádané matice(poèítáno od indexu 0).

æ1ö æ0 ç ÷ ç ç1÷ ç0 ç1÷ ç0 ç ÷ ç ç1÷ ç0 EO 2 , 3 = ç ÷ (0 0 0 0 0 0 2 -2) = ç -1 0 ç ÷ ç ç -1÷ ç0 ç -1÷ ç0 çç ÷÷ çç è -1ø è0

0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0

2 2 2 2 -2 -2 -2 -2

-2 ö ÷ -2 ÷ -2 ÷ ÷ -2 ÷ 2÷ ÷ 2÷ 2÷ ÷ 2 ÷ø

(3.48)

Výsledná matice odpovídá elementárnímu obrazu v øádku 1 a sloupci 7 rozvoje na obr.3.14. Bílá odpovídá hodnotì 2, èerná hodnotì -2 a šedá hodnotì 0.

39

3.6 Walsch-Hadamardova transformace Walsch-Hadamardova transformace pøedstavuje další neharmonickou transformaci obrazu. Transformace je zalo
ena na systému Hadamardových matic, jejich
prvky nabývají pouze hodnot +1 a -1. Hodnoty prvkù tìchto matic ze systému Walshových funkcí: W 0( t ) = 1 j

W 2 j + q( t ) = ( -1) 2

pro 0 £ t £ 1

[W (2t) + ( -1)

+q

j

j +q

]

Wj (2t - 1)

(3.49)

kde q = 0 nebo 1, j = 0, 1, 2, … a j/2 je nejvìtší celé èíslo, které je menší nebo rovné j/2. Konstrukce Hadamardových matic (jádra transformace) vychází ze schématu

æ HN H 2 N = çç è HN

HN ö ÷ -HN ÷ø

(3.50)

kde H2N je matice øádu 2N vycházející z matice øádu N. Volíme H1=1 æ1 1 1 1 ö ÷ ç æ1 1 ö ç1 - 1 1 - 1 ÷ K H 2 = çç ÷÷ , H 4 = ç 1 1 -1 -1÷ è1 - 1 ø ÷÷ çç è1 - 1 - 1 1 ø

(3.51)

Potom pøímá Walsh-Hadamardova transformace v maticovém tvaru pro N´N obraz W ( u, v ) =

1 HN f ( x , y ) HN N

(3.52)

Zpìtná Walsh-Hadamardova transformace má stejný tvar f ( x, y ) =

1 HN W ( u, v ) HN N

(3.53)

Øádky (neuspoøádané) a sloupce Hadamardovy matice mù
eme chápat jako obdélníkové funkce o základní frekvenci odpovídající rozmìru obrazu N a jejích násobcích. Tyto obdélníkové prùbìhy tvoøí soubor Walshových funkcí. Na obr. 3.15 je zobrazen rozvoj elementárních obrazù jádra WHT pro obraz 4´4. Hodnotì -1 odpovídá èerná, hodnotì 1 bílá. ´

40

Obr.3.15 Rozvoj elementárních obrazù WHT (Walshovy funkce) Pro výpoèet elementárních obrazù z matice H4 musíme uspoøádat poøadí øádkù podle poètu znaménkových zmìn (dostaneme tzv. uspoøádanou Hadamardovu matici) æ1 1 1 1 ö 0 ÷ ç ç1 - 1 1 - 1 ÷ 3 , H4 = ç 1 1 -1 -1÷ 1 ÷÷ çç è1 - 1 - 1 1 ø 2

H 4U

æ1 1 1 1 ö ÷ ç ç1 1 - 1 - 1 ÷ =ç 1 -1 -1 1 ÷ ÷÷ çç è1 - 1 1 - 1 ø

(3.54)

Potom ka
dý elementární obraz dostaneme jako vektorový souèin dvou øádkù, které pøíslušejí pozici elementárního obrazu v jejich rozvoji. Elementární obraz EO2,3 dostaneme jako vektorový souèin 2. a 3. øádku uspoøádané matice (poèítáno od indexu 0).

æ 1 -1 1 -1ö æ1ö ÷ ç ç ÷ ç -1 1 -1 1 ÷ ç -1÷ EO 2 , 3 = ç ÷ (1 -1 1 -1) = ç -1 1 -1 1 ÷ -1 ÷÷ çç çç ÷÷ è 1 -1 1 -1ø è1ø

(3.55)

Výsledná matice odpovídá elementárnímu obrazu ve 3. øádku a 4. sloupci rozvoje na obr.3.15.

41

4. Statistický popis obrazu 4.1 Charakteristiky náhodných velièin Hustota pravdìpodobnosti, distribuèní funkce O velièinì, která charakterizuje nìjakou mìøitelnou hodnotu øíkáme,
e je náhodná, jestli
e jsou hodnoty poruch, které ji ovlivòují srovnatelné s jejími vlastními hodnotami. Existují dva typy náhodných velièin (NV) - spojité a diskrétní. Spojitá náhodná velièina nabývá nespoèetnì mnoha hodnot, diskrétní spoèetnì mnoha hodnot. Náhodnou velièinu mù
eme pøesnì popsat velièinami hustoty pravdìpodobnosti nebo distribuèní funkce. Hustota pravdìpodobnosti pøiøazuje jednotlivé hodnoty pravdìpodobnosti hodnotám diskrétní NV a u spojité NV hodnoty pravdìpodobnosti intervalùm NV. Prùbìh hustoty pravdìpodobnosti od minus nekoneèna do plus nekoneèna definuje tzv. pravdìpodobnostní rozlo
ení (rozdìlení) náhodné velièiny.

Obr.4.1 Rozdìlení hustoty pravdìpodobnosti náhodné velièiny Na obr. 4.1 je nakreslen pøíklad pravdìpodobnostního rozdìlení náhodné velièiny, co
je závislost mezi všemi jejími hodnotami x a pravdìpodobnostmi jejího výskytu p(x). Jako pøíklad je uveden matematický vztah tzv. normálního (Gaussova) rozdìlení hustoty pravdìpodobnosti: (x -m ) 2

1 2 (4.1) p( x ) = exp 2 s 2p × s pro -¥ < x < ¥ a kde m je støední hodnota a s smìrodatná odchylka normálního rozdìlení.

Pro spojitou NV platí vztahy b

P( x = x 0 ) = 0, P( x Î< a, b >) = ò p( x ) dx, a

¥

ò p( x ) dx = 1

(4.2)

-¥

Pro malé Dx platí (viz obr.4.1) P( x Î Dx ) = Dx × p( x )

43

(4.3)

Pro diskrétní NV platí vztahy xk

P( x = xi ) = p( xi ), P( x Î< xi, xk >) = å p( x ),

å p( x ) = 1

(4.4)

"xi

xi

Distribuèní funkce je definována F( x ) = P( NV £ x )

(4.5)

Distribuèní funkce definuje pravdìpodobnost toho,
e náhodná velièina je v intervalu od minus nekoneèna do hodnoty x. Pro spojitou NV platí x

F( x ) =

ò f ( u) du

(4.6)

-¥

Pro diskrétní NV platí F( x ) = å p( xi )

(4.7)

xi£x

Pro jednodušší manipulaci s náhodnými velièinami jsou definovány èíselné konstanty, které jednoduše popisují dané rozdìlení náhodné velièiny. Støední hodnota (mean value, expectation value) Pro spojitou NV je støední hodnota ¥

mx = E{x} = ò x × p( x ) dx -¥

(4.8)

kde x je náhodná velièina a p(x) je funkce hustoty pravdìpodobnosti této náhodné velièiny (napø. normální rozdìlení, charakterizované Gaussovou køivkou). Pro diskrétní NV n

mx = E{x} = å xi × p( xi )

(4.9)

i =1

kde xi je i-tá hodnota náhodné velièiny x a p(xi) je její pravdìpodobnostní funkce (obdoba hustoty pravdìpodobnosti u spojité NV). Pøíklad 4.1 Pravdìpodobnostní rozdìlení diskrétní NV udává pravdìpodobnost,
e náhodná velièina x = xi. Napø. pøi házení kostkou je pravdìpodobnost padnutí jednoho z šesti èísel 1/6. Potom E{x}= 1/6 + 2/6 +3 /6 + 4/6 + 5/6 + 6/6 = 21/6 = 3,5. Rozptyl (variance) Rozptyl je støední hodnota druhých mocnin rozdílù hodnot náhodné velièiny a její støední hodnoty.

{( x - m ) } = ò

sx 2 = D{x} = E

2

x

¥

-¥

44

( x - mx ) 2× p( x ) dx

(4.10)

Pro diskrétní NV n

sx 2 = D{x} = å ( xi - mx ) 2 × p( xi )

(4.11)

i =1

Smìrodatná odchylka s je druhá odmocnina z rozptylu a platí tedy D{x}= sx2. Vícerozmìrná NV je popsána souborem jednorozmìrných NV. U dvojrozmìrné NV jsou její realizacehodnoty dvojic NV získané napø. mìøením nìjakých dvou parametrù (napø. u chemické reakce mìøíme souèasnì PH a teplotu). Definujeme další èíselnou charakteristiku - kovarianci, která charakterizuje vztah mezi obìma NV. Cxy = CV {x, y} = E{( x - mx ) × ( y - my )}

(4.12)

Kovariance je støední hodnota souèinu rozdílù náhodných velièin x, y a jejich støedních hodnot. Pro pratické výpoèty se definuje korelaèní koeficient r=

CV {x, y}

D{x} × D{ y}

=

cxy sx × sy

(4.13)

Pro kovarianci se dá odvodit praktický výpoètový vztah Cxy = E{x × y} - E{x} × E{ y}

(4.14)

Rozptyl NV je zvláštní pøípad kovariance pro jednu NV

{

}

sx 2 = Cxx = E{( x - m x ) × ( x - m x )} = E ( x - m x ) 2

(4.15)

Potom obdobný výpoèetní vztah

{ }

sx 2 = E x 2 - E{x}

2

(4.16)

Jsou-li x, y nezávislé (nekorelované), potom je CV(x,y) = 0 a platí E{x × y} = E{x} × E{ y}

(4.17)

Pro dvì náhodné promìnné mù
eme sestavit kovarianèní matici, kdy v hlavní diagonále jsou rozptyly obou NV, ve vedlejší diagonále jejich kovariance. ésx 2 C=ê ë cyx

cxy ù ú sy 2 û

45

(4.18)

Pro omezený výbìr realizací NV (pøi mìøení reálných velièin) jsou definovány výbìrové èíselné charakteristiky, které jsou odhadem støední hodnoty, rozptylu a kovariance. Výbìrový prùmìr N

mx =

1 N

sx =

1 N

å(x - m )

cx =

1 N

å ( x - m )( y - m )

åx

i

i =1

Výbìrový rozptyl N

i

x

2

i =1

Výbìrová kovariance N

i

x

i

y

i =1

Pøíklad 4.1 Sestavte kovarianèní matici r, g, b slo
ek obrazu 4´4, tedy ze16 realizací tøírozmìrné náhodné velièiny. é3 ê3 R=ê ê4 ê4 ë

3 4 5 5

5 4 5 5

6ù é3 ú ê1 5 ú G=ê 6ú ê4 ú ê 6û ë2

2 5 5 4

3 3 3 4

4ù é4 ú ê1 6 ú B=ê 6ú ê4 ú ê2 5û ë

2 4 3 3

3 2 3 5

4ù 4ú ú 5ú 5 úû

Slo
ky R, G, B pøedstavují tøírozmìrnou NV, ka
dá se šestnácti realizacemi. Prùmìrné hodnoty ka
dé ze tøí NV jsou R0 = 4,5625, G0 = 3,75, B0 = 3,375 Poèítáme jednotlivé slo
ky kovarianèní matice: CRR =

1 4 4 ( R( k , l ) - R0) 2 = (3 - 4,5625) 2 + (3 - 4,5625) 2 +.......+(6 - 4,5625) 2 = 0,996094 å å 16 k =1 l =1

Podobnì vypoèítáme CGG a CBB. CRG =

1 4 4 å å ( R( k , l ) - R0)(G( k , l ) - G 0) = (3 - 4,5625)(3 - 3,75) +......+(6 - 4,5625)(5 - 3,75) = 16 k =1 l =1

= 0953125 . Podobnì vypoèítáme CRB a CGB. Po výpoètu všech hodnot je výsledná kovarianèní matice é0,996094 0,953126 0,726563ù ú C = ê0,953125 1937500 , 1281250 , ê ú , 1359375 , êë0,726563 128125 úû

46

4.2 Obraz jako náhodný proces Pøedpokládejme vícenásobné snímání obrazu o rozmìru N´N v èase. Získáme tak soubor obrazù, který nazveme náhodný proces (NP). Jedná se v podstatì o vícerozmìrnou náhodnou velièinu, kdy ka
dý obraz pøedstavuje jednu realizaci NP, která obsahuje N 2 pixelù. Hodnoty jasù stejných poloh x, y pixelù pøedstavují N 2 náhodných velièin (obr.4.2).

Obr. 4.2 Obraz jako náhodný proces Oznaèíme si jednotlivé NV (u obrazu hodnoty úmìrné jasu pixelù) jako funkci tøí promìnných f(x,y,wi), kde x,y charakterizují polohu náhodných velièin v prostorových souøadnicích a wi, i=1,...k polohu v èase i-tého obrazu v NP. Potom pro pevné [x,y] a promìnné i dostaneme jednu náhodnou velièinu náhodného procesu a pro pevné i a promìnné hodnoty [x,y] dostaneme jednu realizaci náhodného procesu, v našem pøípadì jeden obraz. Statistické charakteristiky NP Støední hodnota Oznaème si písmenem z hodnoty náhodné velièiny f(x,y,wi), i=1,...k. Potom mù
eme psát pro støední hodnotu jedné náhodné velièiny na posici [x,y] v náhodném procesu mf ( x, y ) = E{ f ( x, y, wi )} =

¥

ò z × p( z ; x, y ) dz

(4.19)

-¥

kde p(z; x,y) je pravdìpodobnost výskytu hodnoty z na pozici [x,y]. Tedy støední hodnota náhodné velièiny z náhodného procesu je obecnì závislá na pozici [x,y]. Støední hodnota diskrétního náhodného procesu tvoøeného n náhodnými velièinami mù
e být reprezentována jako aritmetický vektor støedních hodnot jednotlivých náhodných velièin mT(x,y) = (m1, m2,........ mn), kde m(xj,yj) = E{f(xj, yj)} pro j=1, .... n. Autokorelace Pro dvì rùzné NV na pozicích [x1,y1], [x2,y2] z jednoho náhodného procesu mù
eme definovat autokorelaèní funkci Rff ( x1, y1; x 2, y 2 ) = E{ f ( x1, y1, wi ) × f ( x 2, y 2, wi )}

47

(4.20)

Jednotlivé hodnoty autokorelaèní funkce náhodného procesu mù
eme sestavit do autokorelaèní matice. Hlavní diagonála je tvoøena souèiny stejných náhodných velièin NP. Pøíklad vytváøení struktury autokorelaèní matice náhodného procesu souboru obrazù velikosti 3´3. Písmeny a-i jsou oznaèeny jednotlivé náhodné velièiny náhodného procesu, pøi vytváøení korelaèních dvojic postupujeme po sloupcích:

æa b ç çd e çg h è

cö ÷ f÷ i ÷ø

®

æ aa ç ç da ç ga ç ç ba ç ea ç ç ha ç ca ç ç fa ç ia è

ad dd gd bd ed hd cd fd id

ag dg

ab ae ah ac af db de dh dc df gg gb ge gh gc gf bg bb be bh bc bf eg eb ee eh ec ef hg hb he hh hc hf cg cb ce ch cc cf fg fb fe fh fc ff ig ib ie ih ic if

ai ö ÷ di ÷ gi ÷ ÷ bi ÷ ei ÷ ÷ hi ÷ ci ÷ ÷ fi ÷ ii ÷ø

Autokovariance Pro dvì rùzné NV na pozicích [x1,y1], [x2,y2] z jednoho náhodného procesu mù
eme definovat autokovarianèní funkci: Cff ( x1, y1; x 2, y 2 ) = E{[ f ( x1, y1, wi ) - mf ( x1, y1 )] × [ f ( x 2, y 2, wi ) - mf ( x 2, y 2 )]}

(4.21)

Zvláštním pøípadem autokovariance pro jednu NV z jednoho NP je rozptyl této NV

{

}

Cff ( x1, y1; x1, y1 ) = E [ f ( x1, y1, wi ) - mf ( x1, y1 )] 2

(4.22)

Dá se odvodit výpoètový vztah Cff ( x1, y1; x 2, y 2 ) = Rff ( x1, y1; x 2, y 2 ) - m( x1, y1 ) × m( x 2, y 2 )

( 423 . )

Pokud jsou NV na pozicích [x1,y1], [x2,y2] nekorelované, tak je Cff = 0 a platí Rff ( x1, y1; x 2, y 2 ) = m( x1, y1 ) × m( x 2, y 2 ) = E{ f ( x1, y1, wi )}× E{ f ( x 2, y 2, wi )} Jednotlivé hodnoty autokovarianèní funkce náhodného procesu mù
eme sestavit do autokovariaèní matice podobnì jako u autokorelaèní funkce. Hlavní diagonála je tvoøena rozptyly jednotlivých náhodných velièin NP. Vzájemná korelace a kovariance Pøedpokládejme dva náhodné procesy f(x,y,wi) a g(x,y,wj), tedy dvì série obrazù (indexy i, j pou
ijeme pro rozlišení obou procesù). Potom mù
eme definovat vzájemnou korelaci dvou NV Rfg ( x1, y1 , wi; x 2, y 2 , wj ) = E{ f ( x1, y1, wi ) × g( x 2, y 2, wj )}

48

(4.24)

Podobnì vzájemná kovariance dvou NV Cfg ( x1, y1 , wi; x 2, y 2 , wj ) = E{[ f ( x1, y1, wi ) - mf ( x1, y1 , wi )] × [g( x 2, y 2, wj ) - mg ( x 2, y 2 , wj )]} (4.25) Analogicky ke vztahu 4.14 platí výpoèetní vztah Cfg ( x1, y1 , wi; x 2, y 2 , wj ) = Rfg ( x1, y1, wi; x 2, y 2, wj ) - mf ( x1, y1 , wi ) × mg ( x 2, y 2, wj )

(4.26)

Dva náhodné procesy jsou nekorelované, kdy
platí Cfg = 0 (vzájemná kovariance je rovna nule). Proto
e pro dvì nekorelované NV platí rov. 4.17, potom pro dva nekorelované NP platí E{ f ( x1, y1 , wi ) × g( x 2, y 2 , wj )} = E{ f ( x1, y1, wi )}× E{g( x 2, y 2, wj )}

(4.27)

Homogenita náhodného procesu Náhodný proces je homogenní (jiný název stacionární) pokud jsou • støední hodnoty jeho náhodných velièin (rov. 4.19) jsou stejné, tedy mf ( x, y ) = const (nezávislé na poloze x,y) • jeho autokorelaèní funkce (rov. 4.20) je prostorovì invariantní. Prostorová invariantnost znamená,
e korelaèní koeficienty dvojic NV nezávisí na jejich absolutní poloze v obraze, ale pouze na jejich vzájemném posunutí x0 a y0 (obr. 4.3).

Obr.4.3 Posunutí souøadnic pro výpoèet autokorelaèní funkce

Za pøedpokladu invariantnosti NP mù
eme pro autokorelaèní funkci (rov. 4.20) pro promìnné posunutí x0, y0 psát Rff ( x 0, y 0 ) = E{ f ( x, y, wi ) × f ( x + x 0, y + y 0, wi )}

49

(4.28)

Pøíklad 4.2. Pro náhodný proces charakterizovaný následujícími osmi vzorky obrazu 4×4 vypoèítejte - vektor jeho støední hodnoty, - prostorové prùmìry jednotlivých realizací, - tøi hodnoty autokorelaèní funkce Rff = E{f11×f11}, Rff = E{f23×f32}, Rff = E{f23×f34}. æ5 ç ç5 ç6 çç è5

4 3 6 4

6 4 7 2

2ö æ 4 ÷ ç 3÷ ç 7 , 1÷ ç3 ÷ ç 3 ÷ø çè 4

2 2 5 6

2 4 4 6

1ö æ3 ÷ ç 9÷ ç5 , 5÷ ç2 ÷ ç 2 ÷ø çè 6

5 2 3ö æ6 ÷ ç 4 4 3÷ ç3 , 2 6 6÷ ç 4 ÷ ç 5 4 6 ÷ø çè 5

æ4 ç ç6 ç4 çç è3

3 5 3 3

5 6 3 6

4ö æ 4 ÷ ç 2÷ ç1 , 4÷ ç 4 ÷ ç 5 ÷ø çè 1

5 6 8 3

4 2 4 2

5ö æ2 ÷ ç 6÷ ç2 , 4÷ ç6 ÷ ç 7 ÷ø çè 4

7 4 3 3

6 2 4 6

4ö æ5 ÷ ç 4÷ ç 4 , 7÷ ç 4 ÷ ç 2 ÷ø çè 5

4 2 8ö ÷ 5 6 4÷ 3 2 2÷ ÷ 3 3 4 ÷ø 3 4 2 5

6 5 3 4

6ö ÷ 2÷ 4÷ ÷ 4 ÷ø

Prùmìry jednotlivých NV náhodného procesu m11 =

5+ 4+3+6+ 4+ 4+2+5 = 4125 . 8

Podobnì m12 = m13 = m14 = ¼¼= m44= 4.125. Prostorové prùmìry mw1 =

5 + 4 + 6 + 2 + 5 + 3 + 4 + 3 + 6 + 6 + 7 +1+ 5 + 4 + 2 + 3 = 4125 . 16

Podobnì mw2 = mw3 = mw4 = ¼¼= mw16 = 4.125. Hodnoty autokorelaèní matice 5 ×5 + 4 × 4 + 3 ×3 + 6 ×6 + 4 × 4 + 4 × 4 + 2 ×2 + 5 ×5 = 18375 . 8 4 ×6 + 4 ×5 + 4 ×2 + 6 ×3 + 6 ×3 + 2 ×8 + 2 ×3 + 5 ×2 f 32 ) = = 150 . 8 4 ×1 + 4 × 5 + 4 × 6 + 6 × 2 + 6 × 4 + 2 × 4 + 2 × 7 + 5 × 4 f 34 ) = = 15.75 8

E( f 11 × f 11 ) = E( f 23 × E( f 23 ×

Náhodný proces z tohoto pøíkladu není homogenní, proto
e není splnìna druhá podmímka homogenity, tedy invariantnost autokorelaèní funkce (E{f23×f34} není stejná jako E{f23×f32}).

50

4.3 Výpoèet statistických charakteristik z jednoho vzorku NP Pøi praktických aplikacích máme èasto k dispozici pouze jeden vzorek obrazu a chceme znát statistické charakteristiky (støední hodnoty, autokorelace a autokovariance) náhodného procesu s ním svázaného. Pokud chceme poèítat statistiky náhodného procesu pouze z jednoho vzorku obrazu, tak pro dobrý výsledek musí být náhodný proces, který je s tímto obrazem svázaný, homogenní a ergodický. Potom mù
eme k výpoètu pou
ít tzv. prostorové statistiky NP. Prostorové statistiky NP Prostorový prùmìr NP 1 f ( x, y, wi ) dxdy S ®¥ S òS

m(wi ) = lim

(4.29)

kde S je plocha oblasti obrazu a ò je plošný integrál pøes tuto plochu. S

Hodnota m(wi ) je funkcí jednotlivých realizací (obrazù) a je to také náhodná velièina (obr.4.4).

Obr.4.4 Prostorové prùmìry realizací NP Prostorový prùmìru pro digitální obraz m (wi ) =

1 N2

N

N

å å f ( j, k , w )

(4.30)

i

j =1 k =1

Prostorová autokorelaèní funkce pro hodnoty f posunuté o x0, y0 1 f ( x, y, wi ) × f ( x + x 0, y + y 0, wi ) dxdy S ®¥ S òS

R( x 0, y 0, wi ) = lim

(4.31)

Tato funkce je také náhodná velièina a je funkcí jednotlivých realizací (obrazù). Prostorová autokorelaèní funkce digitálního obrazu pro posunutí Dj, Dk. R ( Dj, Dk , wi ) =

1 N2

N

N

å å f ( j, k , w ) × f ( j + Dj, k + Dk , w ) i

j =1 k =1

51

i

(4.32)

Ergodicita náhodného procesu Øíkáme,
e NP je ergodický s ohledem na prùmìr, jestli
e je homogenní a dále platí,
e prostorový prùmìr m(wi) = const pro i=1,....k. Je tedy nazávislý na realizaci NP a mù
eme ho tedy poèítat z kterékoliv realizace. Øíkáme,
e NP je ergodický s ohledem na autokorelaèní funkci, jestli
e je homogenní a jeho prostorová autokorelaèní funkce (rov. 4.31) není závislá na realizaci NP a je rovna autokorelaèní funkci NP (rov. 4.20), tedy Rff ( x 0, y 0 , wi ) = Rff ( x1 , y1; x 2, y 2 ). Z této úvahy vyplývá,
e jestli
e je NP ergodický, mù
eme poèítat jeho støední hodnotu a autokorelaèní funkci nikoliv z jednotlivých náhodných velièin NP (tedy ze všech obrazù NP), ale z prostorových statistik pouze jedné libovolné realizace (obrazu) NP (rov. 4.29, 4.31). Tento pøedpoklad je správný, pokud je vzájemná variabilita všech realizací NP stejná jako vlastní variabilita obsahu ka
dé realizace zvláš. Pro digitální obrazy rozmìru N´N je v obou prostorových statistikách integrál nahrazen sumou a plocha S poètem pixelù N2 (rov. 4.30, 4.32). U prostorové autokorelaèní funkce mù
eme jednotlivé koeficienty korelace, které jsou funkcí posunutí Dj, Dk sestavit do prostorové autokorelaèní matice o rozmìru N 2´N 2. Rovnice pro výpoèet koeficietù Cij prostorové autokorelaèní matice obrazu Cij =

1 N2

min( N , N + k 0) min( N , N + l 0)

å

åg

kl

k = max(1 ,1 + k 0) l = max(1 ,1 + l 0)

kde k 0 = ( i - 1) mod N - ( j - 1) mod N a l 0 =

× gk

- k 0, l - l 0

(4.33)

i- j - k0 . N

Pøíklad 4.3

æ1 2 1 ö ç ÷ Vypoètìte podle rovnice 4.33 autokorelaèní matici obrazu popsaného maticí ç1 2 1÷ . ç1 2 1 ÷ è ø Nejprve vypoèítáme hodnotu diagonálních prvkù (modN je zbytek po dìlení èíslem N). C11: k0 = (i-1)mod3 - (j-1)mod3 = 0mod3 - 0mod3 = 0 - 0 = 0; l0 = (i-j-k0)/3 = 0 C 11 =

1 N2

3

3

å åg

kl

k =1

l =1

× gkl =

1 (1 + 4 + 1 + 1 + 4 + 1 + 1 + 4 + 1) = 2 9

Podobnì C22= C33 = .... = C99 = 2. Vypoèítáme hodnotu prvku C12 C12: k0 = 0mod3 - 1mod3 = 0-1=-1; C 12 =

1 N2

2

3

å åg

kl

k =1

l =1

× gkl =

l0 = (1-2+1)/3 = 0;

1 , (1 + 4 + 1 + 1 + 4 + 1) = 12 / 9 = 133 9

52

Podobným zpùsobem mù
eme poèítat ostatní prvky. Potom výsledná autokorelaèní matice æ 2 ç . ç 133 ç 067 . ç . ç 133 . Cff = ç 089 ç ç 0.44 ç 033 . ç . ç 022 ç 011 è .

133 . 2 133 . 089 . 133 . 089 . 022 . 033 . 022 .

067 . 133 . 2 0.44 089 . 133 . 011 . 022 . 033 .

133 . 089 . 0.44 2 133 . 067 . 133 . 08 .9 0.44

089 . 133 . 089 . 133 . 2 133 . 089 . 133 . 089 .

0.44 089 . 133 . 067 . 133 . 2 0.44 089 . 133 .

033 . 022 . 011 . 133 . 089 . 0.44 2 133 . 067 .

022 . 033 . 022 . 089 . 133 . 089 . 133 . 2 133 .

011 . ö ÷ 022 . ÷ 0.22 ÷ ÷ 0.44 ÷ 089 . ÷ ÷ 1.33 ÷ 067 . ÷ ÷ 133 . ÷ 2 ÷ø

4.4 Karhunen-Loeve transformace Pøedpokládejme obraz z ergodického NP a chceme jej pøenést po komunikaèním kanále. Chceme pøed pøenosem provést jeho kompresi. Pro tento úèel je vhodné provést takovou transformaci obrazu, aby transformovaný obraz obsahoval pouze nekorelované hodnoty pixelù, vzájemì závislé hodnoty se budou v transformovaném obraze blí
it k nule a mohou být komprimovány. Autokorelaèní fumkce takto transformovaného obrazu má speciální formu - bude diagonální (nenulové hodnoty jen v hlavní diagonále). Pro pøenos pak pou
ijeme tuto transformovanou nekorelovanou matici obrazu a pøíslušnou transformaèní matici. Zpìtnou tranformací transformovaného obrazu, pøeneseného po komunikaèním kanále, získáme pùvodní obraz. K výpoètu takové transformace vyu
ijeme pøedpokládané ergodicity NP a urèíme koeficienty tranformaèní matice ze statistik jednoho obrazu, místo z celého souboru obrazù náhodného procesu. Jak tedy transformovat obraz N´N, aby jeho autokorelaèná matice byla diagonální? Pøedpokládejme,
e g je vektor výchozího obrazu vytvoøený stohováním a g~ je transformovaný vektor obrazu. Dále pøedpokládáme,
e obraz g je souèástí ergodického NP. Transformaci, kterou hledáme, pøedpokládejme ve tvaru g~ = A( g - mg )

(4.34)

kde A je transformaèní matice N 2´N 2 a mg konstantní vektor N 2´1 prostorového prùmìru obrazu. Dá se odvodit,
e prostorový prùmìr transformovaného je roven nule, tedy mg~ = 0. Po odvození autokovarianèní matice transformovaného obrazu (je stejná jako autokorelaèní matice z dùvodu,
e mg~ = 0) platí ~~ = A × C gg × A T Cgg

(4.35)

Aplikací transformaèní matice A na autokovarianèní matici Cgg pùvodního obrazu podle rovnice 4.35 dostaneme autokovarianèní matice transformovaného obrazu. Ta bude mít nenulové jen diagonální prvky. To znamená,
e transformovaný obraz g~ bude mít nenulové jen nekorelované hodnoty pixelù.

53

Transformaèní matice A vyhovuje rovnici 4.36, jestli
e bude matice A vytvoøena po øádcích z vlastních vektorù autokovarianèní matice Cgg pùvodního obrazu g. Diagonální elementy matice ~~ potom budou vlastní èísla autokovarianèní matice Cgg [2]. Cgg ~~ Øádky vlastních vektorù v matici A jsou øazeny vzestupnì podle hodnot vlastních èísel Cgg . Autokovarianèní matice obrazu g-mg (je rovna autokorelaèní matici) se vypoèítá z jednoho obrazu, napøíklad podle rovnice 4.33, za pøedpokladu ergodicity pøíslušného NP. Potom pøímá K-L transformace pro transformovaný vektor g~ g~ = A( g - mg )

(4.37)

kde mg je N 2´1 vektor s hodnotami prùmìrné hodnoty jasu obrazu g, A je transformaèní matice vytvoøená z vlastních vektorù autokovarianèní matice obrazu g. Obraz je potom reprezentován nekorelovanou maticí g~ vytvoøenou podle rov.4.34 a transformaèní maticí A vytvoøenou z vlastních vektorù autokovarianèní matice pùvodního obrazu g. Postup pøi K-L transformaci: • z obrazu g vytvoøíme prùmìr všech pixelù mg • odeèteme tento prùmìr od matice obrazu g • vytvoøíme autokorelaèní matici této nové matice g - mg • vypoèítáme vlastní èísla a vlastní vektory autokolelaèní matice ~~ • vlastní èísla tvoøí hlavní diagonálu matice Cgg • vlastní vektory srovnané po øádcích tvoøí transformaèní matici A • vypoèítáme matici g~ podle 4.37 Pùvodní obraz g získáme aplikací inverzní K-L transformace g = A T g~ + mg

(4.38)

Kompresi obrazu mù
eme provést tím,
e polo
íme ménì významná vlastní èísla autokovari~~ anèní matice Cgg rovny nule. Tak budou rovny nule také odpovídající vlastní vektory v matici A ~ který mù
e mít významné mno
ství a aplikací rovnice 4.37 dostaneme transformovaný obraz g, nulových hodnot pixelù. Pøi pøenosu pøenášíme jen nenulové hodnoty obrazu g~ a matice A. Rozepsaná transformaèní matice A a12 æ a11 ç a22 ç a21 ç ç ç ç aN 1 aN 2 A =ç ç aN + 1 1 a N + 1 2 ç ç ç ç ç ç a 2 aN 2 2 è N 1

K K

a1 N a2 N

+1

K K

a12 N a22 N

+1

K

aN 2 N

a1 N a2 N

+1

aNN

M M aNN K K aN + 1 N

aN

+ 1N + 1

K aN

+ 1 2N

M M K

aN 2N

a N 2 N +1

54

K

aN 2 2N

K K K K

a1 N 2 ö ÷ a2 N 3 ÷ ÷ ÷ ÷ K K a NN 2 ÷ ÷ K K a N +1 N 2 ÷ ÷ ÷ ÷ ÷ ÷ K K a N 2 N 2 ÷ø

(4.30)

Chyba aproximace K-L transformace Po zpìtné K-L transformaci (rov. 4.38) dostaneme obraz g, který je však zatí
en chybou z dùvodu zkráceného K-L rozvoje. Dá se odvodit vztah pro støední kvadratickou odchylku (mean square error) e za pøedpokladu,
e v rozvoji ponecháme k vlastních èísel autokovarianèní matice z øady sestupnì uspoøádané a zbytek zanedbáme. Potom e =

N

2

å l . Støední kvadratická chyba e je tedy i

i = k +1

rovna souètu zanebaných vlastních èísel autokovarianèní matice obrazu g. Je tøeba poznamenat,
e pøedpoklad ergodicity náhodného procesu spojeného s transformovaným obrazem není pøíliš realistický. Reálné obrazy nejsou jednoduše realizacemi homogenního náhodného procesu. V jednotlivých obrazech existují v
dycky jako základ deterministické komponenty. Nedá se potom pøedpokládat,
e jednotlivý obraz bude obsahovat takové mno
ství variací hodnot pixelù,
e zahrnuje úplnou rozmanitost celého souboru obrazù náhodného procesu. Pouze obrazy obsahující èistý náhodný šum splòují zcela pøedpoklad ergodicity. Je však mo
né aplikovat pøedpoklad ergodicity také na menší èásti obrazu, které se tomu pøedpokladu blí
í. Pokud máme k disposici celý soubor vzorkù urèitého obrazu, potom pøedpoklad ergodicity náhodného procesu nemusí být splnìn. Autokovarianèní matici a následnì K-L transformaci mù
eme poèítat ze statistik celého NP postupem podobným jako v pøíkladì 4.2. Elementární obrazy K-L transformace Kdy
vyjdeme z rovnice zpìtné transformace g = A T g~ + mg, mù
eme psát g - m g = A T g~

(4.40)

Rozepsáním této rovnice a po dalším odvození [1] dostaneme æ g11 - mg ç ç g 21 - mg ç M çç è gN 1 - m g

g12 - mg K g1 N - mg ö æ a11 ç ÷ g 22 - mg K g 2 N - mg ÷ ~ ç a12 ÷ = g 11ç M M M çç ÷ gN 2 - mg K gNN - mg ÷ø è a1 N

æ a21 ç ç a22 + g~ 21ç M çç è a2 N

a2 , N a2 , N M

+1 + 2

a2 , 2 N

K a2 , N 2 K a2 , N 2 K

a2 , N 2

+1 + 2

a1 , 2 N

K a1 , N 2 K a1 , N 2 K

ö ÷ + 2÷ ÷+ ÷÷ ø

- N +1 - N

M

æ a N 21 ö ç ÷ + 2÷ ~NN ç a N 2 2 + + g KK ç M ÷ ç ÷÷ ça 2 ø è N N

- N +1 - N

a1 , N a1 , N M

a1 , N 2

a N 2 N +1 K a N 2 N 2 - N +1 ö ÷ a N 2 N +2 K a N 2 N 2 - N +2 ÷ ÷ M M ÷ aN 2 2N K a N 2 N 2 ÷ø

Z tohoto výsledku je zøejmé,
e elementární obrazy pùvodního obrazu g jsou tvoøeny jednotlivými vlastními vektory, tedy øádky transformaèní matice A. Prvních N slo
ek vlastního vektoru tvoøí první sloupec elementárního obrazu, druhých N slo
ek tohoto vektoru tvoøí druhý sloupec atd. K-L transformace poskytuje N 2 elementárních obrazù, pokud nìkteré nazanedbáme. Koeficin~ ty rozvoje jsou potom hodnoty transformovaného obrazu g.

55

5. Zlepšování kvality obrazu Pod pojmem zlepšování obrazu (image enhancement) rozumíme manipulaci s obrazem, která zpùsobí,
e subjektivnì vypadá líp. Pøíkladem mù
e být napøíklad zvyšování kontrastu, filtrace šumu, zvýrazòování detailù ostøením. My ve skuteènosti nevíme, jak by mìl obraz vypadat, aby byl co nejvíce ve shodì s jeho pøedlohou. Chceme ho však zlepšit, pokud se nám jeví subjektivnì nekvalitní. To je rozdíl ve srovnání s operacemi rekonstrukce obrazu (image restoration), kdy víme, jak by mìl obraz vypadat. Odstraòujeme pak jeho zkreslení, abychom se pøiblí
ili originálu. Metody zvyšování kvality obrazu se dìlí na dva základní smìry • zalo
ené na statistickém rozdìlení úrovní šedi obrazu a jejích zmìnách (operace v prostorové oblasti) • zalo
ené na obsahu prostorových frekvencí v obraze a jejích zmìnách (operace ve frekvenèní oblasti).

5.1 Bodové transformace Bodové operátory Bodové operátory se týkají transformace hodnoty v jednotlivých bodech obrazu, kdy hodnota výstupního pixelu je ovlivnìna pouze transformací hodnoty jasu vstupního pixelu, tedy bez vlivu jasu pixelù okolí. Bodový operátor je pak definován jednoduchou funkèní závislostí g( x, y ) = F[ f ( x, y )]

(5.1)

Funkce F se nazývá pøevodní charakteristika a mù
e být lineární, nelineární, spojitá nebo diskrétní. V digitálních systémech je realizována pomocí tzv. vyhledávací tabulky (look up table). Tabulka je ulo
ena v pamìti a hodnoty všech mo
ných úrovní jasu (obvykle 0-255) jsou adresami na kterých jsou ulo
eny nové (výstupní) hodnoty jasu. Jiná interpretace je mo
ná jako dvojrozmìrné pole N´2 typu integer, kdy jeden sloupec obsahuje hodnoty vstupních jasù (0-255), druhý hodnoty výstupních jasù ve shodì s funkèní závislostí F. Lze tak vytváøet libovolný prùbìh. V grafických programech je pou
ití bodových operací realizováno pomocí tzv. køivek (také gamma funkcí). Na obr.5.1 je znázornìno nìkolik pøíkladù takových pøevodních charakteristik. g

f

Obr.5.1 Pøevodní charakteristiky bodových transformací

57

Histogram Histogram digitálního obrazu je diskrétní funkce urèená v ka
dém bodì poètem pixelù které mají stejnou hodnotu úrovnì šedi. Pokud tuto funkci normalizujeme tak, aby souèet hodnot poètu pixelù všech jasù pøítomných v obraze byl roven 1, mù
eme s ním zacházet jako s funkcí hustoty pravdìpodobnosti (propability density function) jasu v obraze. Z toho vyplývá,
e hodnoty jasu pixelù v obraze mù
eme chápat jako náhodné velièiny a konkrétní obraz je jednou z realizací odpovídajícího náhodného procesu. Ekvalizace histogramu Pøedpokládejme nekontrastní obraz, t.j. jasy pixelù v obraze jsou v úzkém rozmezí hodnot (obr. 5.2 levý). Chceme zvìtšit kontrast obrazu modifikací jeho histogramu, která spoèívá v rozta
ení histogramu na vìtší rozsah jasu pixelù (napø. 0 - 255). Poèet jasových úrovní pøítomných v obraze se nezmìní, pouze se jasy nìkterých pixelù transformují na jiné hodnoty jasu (obr. 5.2 pravý).

Obr.5.2 Ekvalizace histogramu Pøedpokládejme,
e úrovnì jasu vstupní obrazové funkce f jsou charakterizovány funkcí hustoty pravdìpodobnosti pf(f) danou vstupním histogramem a obdobnì úrovnì jasu výstupního obrazu g funkcí hustoty pravdìpodobnosti pg(g). Hledejme bodovou transformaci g = T(f) tak,
e funkce hustoty pravdìpodobnosti pf(f) se transformuje do funkce pg(g) podobné prùbìhu histogramu pravé èásti obr.5.3. Pøedpokládejme transformaci úrovní jasu v rozmezí f+df do intervalu g+dg. Z definice funkce hustoty pravdìpodobnosti pro spojité náhodné velièiny vyplývá,
e pro df ->0 je poèet jasových úrovní v tomto intervalu roven pf(f)df. Podobnì pro promìnnou g je to pg(g)dg.

pf

pg

df

f

g dg

Obr.5.3 Histogramy originálu a transformovaného obrazu

58

Proto
e poèet jasových úrovní v obraze zùstává pøi transformaci stejný, platí pg ( g )dg = pf ( f )df

(5.2)

Pro distribuèní funkci potom platí rovnice g

f

ò p ( g )dg = ò p ( f )df g

f

g min

f

(5.3)

min

Pokud po
adujeme tzv. uniformní (konstantní) rozdìlení hustoty pravdìpodobnosti, tak jsou všechny hodnoty jasových úrovní stejnì pravdìpodobné (plochý histogram transformovaného obrazu), tedy pg(g) = c, kde c je konstanta. Pro distrubuèní funkci v celém intervalu hodnot g platí g max

ò p ( g )dg = 1

(5.4)

g

g min

Po integraci konstanty c ( g max - g min) = 1 c=

1 g max - g min

(5.5)

Potom mù
eme rovnici 5.3 psát g

g

1 1 dg = ( g - g min ) g max - g min g max - g min g min

ò p ( g )dg = ò g

g min

(5.6)

Distribuèní funkci hustoty pravdìpodobnosti oznaèíme Pf(f) f

ò p ( f )df f

f

= Pf ( f )

(5.7)

min

Potom výsledná transformace dosazením do rovnice 5.6 g = ( g max - g min)Pf ( f ) + g min

(5.8)

Tato rovnice definuje pøevodní tabulku mezi pùvodními hodnotami jasu f a novými hodnotami jasu g. Musíme znát prùbìh distribuèní funkce jasù pixelù, kterou dostaneme aproximací vstupního histogramu. Výsledkem je ekvalizovaný obraz, jeho
histogram má za pøedpokladu spojitého obrazu konstantní rozlo
ení hustoty pravdìpodobnosti pg(g)= c. Kdy
provedeme eqkvalizaci histogramu podle pøedchozího vztahu na reálný obraz, tak nedosáhneme plochý histogram, tedy pg ( g ) ¹ c. Je to zpùsobeno tím,
e rozlo
ení hustoty pravdìpodobnosti není v tomto pøípadì spojité. Úrovnì šedi jsou pro digitalizovaný obraz diskrétní hodnoty a máme tedy v intervalu [f, f+df] koneèný poèet hodnot jasu. Potom není mo
né mìnit poèty pixelù

59

s hodnotami jasu mezi tìmito diskrétními hodnotami. Dojde tak pouze k rozta
ení histogramu do širšího intervalu úrovní jasu. Pro získání absolutnì plochého histogramu u digitálních obrazù je tøeba pou
ít slo
itìjší metody redistribuce pixelù v okolí jejich úrovní jasu, napø. metodu náhodných pøídavkù. Jiný tvar výstupního histogramu. Pokud chceme zdùraznit nìkteré úrovnì jasu, tedy nechceme uniformní rozdìlení, vycházíme opìt z rovnice 5.3 a funkci pg(g) volíme podle tohoto po
adavku. Pøíkladem mù
e být tzv. hyperbolizace histogramu, kdy je po
adovaná výsledná hustota pravdìpodobnosti pg ( g ) = a e - ag

(5.9)

Po integraci pøedchozí rovnice a dosazením do rov. 5.3 hledáme vztah mezi novým histogramem obrazu g a starým histogramem obrazu f. Výsledná transformaèní funkce g = g min -

1 ln[1 - Pf ( f )] a

(5.10)

Obraz s nehomogenním kontrastem V pøípadì,
e má obraz nehomogenní kontrast, tedy v nìkterých èástech výraznì odlišnou kvalitu od jiných èástí, pou
íváme techniku lokálního zvyšování kontrastu. Skenujeme obraz pomocí posuvného okna a uvnitø ka
dého provádíme ekvalizaci histogramu, ale poka
dé uva
ujeme rozlo
ení hustoty pravdìpodobnosti vstupního histogramu pro toto konkrétní okno. Velikost posuvného okna volíme podle velikosti oblastí podobné kvality (kontrastu). Alternativní metoda zvyšování kontrastu Pøi bodových transformacích mù
eme pracovat také s jednoèíselnými charakteristikami náhodné velièiny, tedy výbìrovým prùmìrem a výbìrovým rozptylem jasù v definovaném oknì. Pøedpokládejme,
e m je výbìrový prùmìr jasu pixelù v oknì se støedem v [x,y], s je smìrodatná odchylka hodnot jasù v tomto oknì. Zvìtšit rozptyl jasù (tedy kontrast) v oknì mù
eme pomocí následující transformace g( x, y ) = A[ f ( x, y ) - m] + m

(5.11)

kde A je tzv. "zesilovací" èinitel. Mù
eme A definovat tak, aby se oblasti s malým rozptylem "zesílily" více. Toho dosáhneme pokud A bude nepøímo úmìrné smìrodatné odchylce s. A=

kM s

(5.12)

kde k je konstanta a M je prùmìr úrovnì jasu celého obrazu.

60

5.2 Zlepšování kvality barevných obrazù Pøedchozí popsané metody vylepšování obrazu mohou být pou
ity také na multispektrální obrazy slo
ené z barevných pásem (RGB, CMYK, YIQ atd.). Musíme však s tìmito transformacemi zacházet opatrnì, abychom zachovali prùmìrné hodnoty barevných komponent. Jinak mù
e dojít po transformaci k ne
ádoucím posunùm v hodnotách barevného odstínu a sytosti. Je vhodné tyto transformace provádìt v percepèních barvových prostorech (napøíklad HSB, Lab, YIQ). Mapování obrazù Mapování barevných obrazù je pøevod slo
ek pixelù na jiné hodnoty. Pou
ívá se mapování do tzv. pseudobarev nebo nepravých barev (false colours). Mapování do pseudobarev se èasto pou
ívá pøi pøemìnì monochromatického obrazu na barevný. Dùvodem je usnadnìní vizuální detekce detailù. Mapování do pseudobarev je definováno rovnicemi R( j, k ) = OR{RS} G ( j, k ) = OG{GS}

(5.13)

B( j, k ) = OB{BS} kde OR, OG, OB, jsou lineární nebo nelineární operátory aplikované na zdrojové slo
ky RS, GS, BS. Napøíklad zámìna slo
ek R, G, B na B, G, R je realizována rovnicí æ R ö æ 0 0 1 ö æ RS ö æ Bs ö ç ÷ ç ÷ç ÷ ç ÷ ç G ÷ = ç 0 1 0 ÷ ç GS ÷ = ç Gs ÷ ç B ÷ ç 1 0 0 ÷ ç BS ÷ ç Rs ÷ è ø è øè ø è ø

(5.14)

Aritmetické operace mezi barevnými pásmy Tyto operace slou
í pøedevším ke zdùraznìní nìkterých významných rysù obrazu operacemi s jednotlivými barevnými pásmy. To mù
e být následnì vyu
ito v oblasti poèítaèového vidìní. Èasto se pou
ívá odeèítání a dìlení dvou pásem m, n. Dm , n( j, k ) = Fm( j, k ) - Fn( j, k ) Rm , n( j, k ) =

Fm( j, k ) Fn( j, k )

(5.15) (5.16)

V pøípadì dìlení dvou pásem se pøedpokládá nenulová hodnota Fn(j,k). To je v praxi zajištìno tím
e obrazy jsou vìtšinou produktem odrazu svìtla od objektu vlivem osvìtlení funkcí I(j,k) identickou pro všechna pásma. Pokud jsou hodnoty Fn(j,k) malé, potom i malé zmìny DFn(j,k) mohou mít za následek významné zmìny Rm,n(j,k). Problém je mo
né omezit logaritmováním Rm,n(j,k). Lm , n( j, k ) = log{Rm. n( j, k )} = log{Fm( j, k )} - log{Fn( j, k )}

61

(5.17)

PCA transformace Kdy
zobrazíme hodnoty r, g, b pixelù barevného obrazu v 3D souøadném systému RGB, vytvoøí tyto hodnoty 3D graf ve formì hroznu (clusteru) (obr.5.4). Hrozen má obvykle v urèitém smìru nejvìtší rozmìr, co
odpovídá nejvìtšímu rozprostøení hodnot jasu slo
ek pixelù. Tento smìr není obvykle rovnobì
ný s nìkterou z hlavních os RGB barevného prostoru. Proto napøíklad zvìtšení kontrastu ve smìru nìkteré z os není optimální a má vliv na další dvì slo
ky. B

P2

P1

P3

G

R

Obr.5.4 Metoda hlavních smìrù Abychom provedli optimální zvýšení kontrastu barevného obrazu, musíme urèit smìr maximálního rozprostøení hodnot jasu pixelù v prostoru RGB. To se dá provést metodou hlavních smìrù (Principal Component Analysis - PCA), co
v podstatì znamená provést K-L transformaci s kovarianèní maticí obrazù barevných slo
ek. Rozdíl oproti aplikaci K-L transformace z prostorových statistik jednoho obrazu je v tom,
e máme k disposici celý NP pro tøi náhodné velièiny r, g, b. PCA je lineární transformace, která transformuje souøadný systém do smìru nejvìtšího rozprostøení barevných slo
ek r, g, b. Po této transformaci budou slo
ky vzájemnì nekorelované. To znamená,
e pokud budeme upravovat obraz jedné transformované slo
ky, nebude to ovlivòovat obrazy zbylých slo
ek. Pøedstavme si náhodný proces slo
ený ze tøí NV, které pøedstavují tøi N´N obrazy jednotlivých barevných slo
ek r, g, b. Kovarianèní matice tohoto NP má tvar éCrr Crg Crb ù C = êCgr Cgg Cgb ú ê ú êëCbr Cbg Cbb úû

(5.18)

Prvky této matice vypoèítáme pomocí rovnice Ci , j =

1 N2

N

N

å å ( x ( k , l ) - m( x ) × ( x ( k , l ) - m( x )) i

i

j

j

k =1 l =1

kde i, j jsou pásma r, g, b a xi, xj jsou jsou hodnoty pixelù v tìchto pásmech.

62

(5.19)

Pro nekorelované slo
ky obrazu bude C diagonální matice, t.j. C(i,j) = 0 pro i¹j. Abychom toho dosáhli, musíme provést transformaci obrazu pomocí matice A, kterou vytvoøíme z vlastních vektorù kovarianèní matice obrazu. Postup bude následující: • vypoèítáme støední hodnoty jednotlivých slo
ek R0, G0, B0 • vypoèítáme kovarianèní matici C z obrazù slo
ek pomocí rovnice 5.19. • Vypoèítáme vlastní èísla a vlastní vektory matice C, vlastní èísla uspoøádáme sestupnì a sestavíme v tomto poøadí tranformaèní matici A z vlastních vektorù po øádcích • Provedeme transformaci ka
dého pixelu jednotlivých obrazù slo
ek æ P1 ö é A11 ç ÷ ê ç P2 ÷ = ê A21 ç P3 ÷ ê A31 è ø ë

A12 A22 A32

A13 ù é R ù A23 ú êG ú úê ú A33 úû êë B úû

(5.20)

kde P1, P2, P3 jsou obrazy “nových slo
ek”, pøièem
obraz P1 obsahuje maximum informace z pùvodního obrazu. Pokud nám staèí monochromatická verze obrazu, tak pou
ijeme slo
ku P1, která obsahuje maximum informace pøenášené v jedné slo
ce a má maximální mo
ný kontrast ve všech oblastech. Pokud budeme slo
ky P1, P2, P3 intrepretovat jako barevné slo
ky R, G, B potom si musíme být vìdomi,
e jejich hodnoty nemají fyzikální význam barevných slo
ek a není mo
né je vyu
ít pro klasifikaci barev v obraze. Pokud nám však v nìkterých aplikacích staèí ke klasifikaci pixelù jenom úrovnì šedi pixelù jednotlivých slo
ek P1, P2, P3, tak jsou pou
itelné. Pøíklad 5.1. Proveïte PCA 4´4 obrazu s následujícími slo
kami: é3 ê3 R=ê ê4 ê4 ë

3 4 5 5

5 4 5 5

6ù é3 2 ê1 5 5ú ú G=ê 6ú ê4 5 ê 6úû ë2 4

3 3 3 4

4ù é4 ê1 6ú ú B=ê 6ú ê4 ê2 5 úû ë

2 4 3 3

3 2 3 5

4ù 4ú ú 5ú 5 úû

Prùmìrné hodnoty slo
ek R0 = 4,5625, G0 = 3,75, B0 = 3,375 Poèítáme jednotlivé slo
ky kovarianèní matice slo
ek R, G, B: CRR =

1 4 4 ( R( k , l ) - R0) 2 = (3 - 4,5625) 2 + (3 - 4,5625) 2 +.......+(6 - 4,5625) 2 = 0,996094 å å 16 k =1 l =1

CRG =

1 4 4 å å ( R( k , l ) - R0)(G( k , l ) - G 0) = (3 - 4,5625)(3 - 3,75) +......+(6 - 4,5625)(5 - 3,75) = 16 k =1 l =1

= 0,95312 Po výpoètu všech hodnot je výsledná kovarianèní matice

CRGB

é0,996094 0,953125 0,726563ù = ê0,953125 1937500 , 1281 , 250 ú ê ú , 1359375 , êë0,726563 1281250 úû

63

Pomocí programu Mathematica vypoèítáme vlastní èísla a vlastní vektory této matice. Vlastní èísla této matice jsou l1=3,528765, l2=0,435504, l3=0,328700. Transformaèní matice A sestavená z vlastních vektorù kovarianèní matice 0,70833 0,561576 ö æ 0,42767 ç ÷ A = ç 0,876742 -0173808 , -0,448457 ÷ ç 0,220050 -0,684149 0,695355 ÷ è ø Nyní vypoèítáme hodnoty P1, P2, P3 pro jednotlivé pixely podle rovnice 5.20. Napøíklad pro pixel v levém horním rohu tvoøí jeho slo
ky r, g, b vektor (3,3,4)T. Tento vynásobíme zleva maticí A a dostaneme vektor nových slo
ek tohoto pixelu. 0,561576 ö æ 3 ö æ 5,654 ö æ 0,427670 0,708330 ÷ ÷ç ÷ ç ç , -0,448457 ÷ ç 3 ÷ = ç 0,315 ÷ ç 0,876742 -0173808 ÷ ç 0,220050 -0,684149 0,695355 ÷ ç 4 ÷ ç 1389 ø øè ø è , è Podobnì provedeme výpoèty všech ostatních pixelù a dostaneme obrazy slo
ek P1, P2, P3.

. æ 565 ç . ç 255 P1 = ç 6.79 çç . è 425

382 . 750 . 736 . 666 .

595 . 496 . 595 . 7.78

765 . ö . æ 032 ç ÷ . 863 . ÷ ç 200 P = 2 ç 102 . 96 . 2÷ çç ÷÷ . 892 . ø è 226

139 . 084 . 217 . 234 .

252 . 209 . 252 . 145 .

. 068 . 2.77 ö æ 139 ç ÷ . 024 . 155 . ÷ ç 067 P3 = ç 0.92 -023 . 197 . ÷ çç ÷÷ . 0.45 215 . ø è 090

113 . 136 . ö ÷ 022 . -022 . ÷ . . ÷ 113 069 ÷ . . ÷ø 184 138

Kontrasty v obrazech slo
ek r, g, b jsou 3, 5, a 4. Kontrast v P1 je 9.62 - 2,52 = 7.07, co
je více ne
pøedchozí hodnoty. Pokud nyní vypoèítáme kovarianèní matici slo
ek P1, P2, P3 nového transformovaného obrazu, tak nenulové budou pouze diagonální slo
ky, ostatní budou pøibli
nì nulové. 0 0 ù é3,5287 CP 123 = ê 0 0,4355 0 ú ê ú 0 0,3287úû êë 0 Tím je prokázáno,
e slo
ky P1, P2, P3 jsou nekorelované. Ve slo
ce P1 transformovaného obrazu získáme slo
ku obrazu s maximálním kontrastem.

5.3 Filtrace šumu v obraze Filtrace šumu (vyhlazování) vylepšuje obraz ve smyslu odstraòování Gaussovského šumu (normální rozdìlení poruch) a impulsního šumu (náhodné velké poruchy). Filtrovat obraz mù
eme pou
itím operace konvoluce, kdy k výpoètu nové hodnoty “filtrovaného” pixelu pou
ijeme jeho malého okolí (konvoluèní maska). Konvoluèní maskou se systematicky obraz prochází a poèítá se

64

nová hodnota na základì stejné konvoluèní masky (prostorová invariantnost konvoluce). Nevýhodou je,
e se potlaèí vysoké frekvence, tedy také hrany, které chceme v obraze mít (hrany se rozostøí). Metody mohou být i nelineární (rotující maska, medián), keré tolik nerozostøují významné hrany. Tyto metody byly popsány v pøedmìtu Zpracování textu a obrazu I. Druhá skupina metod vyhlazování obrazu je zalo
ena na pou
ití tzv. filtrù ve frekvenèní oblasti. Gaussovský šum je nekorelovaný, jeho spektrum je ploché. Naproti tomu spektra vìtšiny signálù mají maximální hodnoty na nízkých frekvencích (obr.5.5). Existuje urèitá frekvence f0, od které jsou hodnoty spektra šumu vìtší ne
hodnoty spektra signálu. Tato hodnota se volí jako hranice filtru, od které se vysoké frekvence odøíznou.

Obr.5.5 Spektra obrazu a šumu V pøípadì filtrace obrazu pou
ijeme na obraz Fourierovu transformaci (FT) a v transformovaném obraze odøízneme pásmo vysokých frekvencí, které nechceme v obraze mít. Prakticky to znamená oøezání vysokých frekvencí obrazu od urèitých hodnot frekvencí (obr.5.6). Oøezání vysokých frekvencí je tedy realizováno souèinem FT vstupního obrazu a FT konvoluèní masky. Takto zpracovaný obraz pøevedeme pomocí inverzní FT zpìt do prostorové oblasti. Jádro ideálního nízkofrekvenèního 2D filtru je mo
né popsat vztahem ì1 pro u 2 + v 2 £ R0 ï H ( u, v ) = í ïî0 pro u 2 + v 2 > R0

(5.21)

kde hodnota R0 je hranice filtru a bývá urèována v procentech všech frekvencí v obraze. Mù
e se pou
ít i slo
itìjší funkce ne
0 a 1, která vysoké frekvence neoøezává, ale pouze je potlaèuje. Pou
itím zpìtné FT dostaneme potom vyhlazený obraz g( x, y ) = F -1 [F( u, v ) × H ( u, v )]

(5.22)

Definice 2D filtru Existuje ještì jiná cesta filtrace - pøevedením tzv. 2D filtru do prostorové oblasti. 2D filtr H(u,v) ve frekvenèní oblasti je definován jako Fourierova transformace impulzní odezvy h(x,y) a nazývá se frekvenèní pøenos (MTF). Pøi aplikaci inverzní Fourierovy transformace na filtr H(u,v) tvaru (5.21), dostaneme zpìt impulsní odezvu filtru h(x,y) na tuto konkrétní funkci . Tento postup filtrace je prezentován na obr.5.7.

65

Obr.5.6 Oøezávání pásma vysokých frekvencí obrazu

Obr.5.7 Filtrace ve frekvenèní oblasti

66

H(u,v) je obvykle definována jako spojitá funkce frekvencí u,v. Funkce h(x,y) jako inverzní FT je tedy také spojitá, ale proto
e bude pou
ita pro konvoluci s digitálním obrazem, musí být prakticky definována v diskrétních bodech - oznaèíme h(k,l). Prakticky pou
ívané rovnice pro reálný 2D filtr (bez sinusové imaginární slo
ky) mají tvar p p

1 h( k , l ) = H ( u, v )cos( uk + vl ) dudv 2p -òp -òp

(5.23)

Výpoètem impulzní odezvy podle rovnice (5.23) dostaneme vztah h( k , l ) =

R0

k +l kde J1 je Besselova funkce funkce1. øádu. 2

2

J 1 ( R0 k 2 + l 2

(5.24)

Konstrukce 2D filtru v prostorové oblasti My chceme v nìkterých pøípadech provádìt filtraci v prostorové oblasti, napø. z dùvodu konstrukce filtru technickými prostøedky, nebo opakování filtrace stejným filtrem. Na základì znalosti parametrù ideálního filtru ve frekvenèní oblasti mù
eme takový filtr navrhnout. Problém optimální filtrace v prostorové oblasti je tedy konstrukce digitálního konvoluèního filtru, který má pøedem specifikované spojité spektrum ve frekvenèní oblasti. Filtr z obr.5.6, který propouští nízké frekvence se nazývá dolní propust (lowpass filter). Pomocí jeho inverzní FT dostaneme impulzní odezvu - ideální dolní propust v prostorové oblasti (obr. 5.7). Na obr.5.8 jsou znázornìny impulzní odezva ideální 1D dolní propusti a 1D øez v impulsní odezvì ideální 2D dolní propusti. Z obr. 5.8 je patrné,
e nestaèí provést inverzní FT ideální dolní propusti H(u,v), proto
e potom impulsní odezva h(k,l) obsahuje nekoneènì mnoho bodù a nemù
e být prakticky provedena konvoluce. Pro konvoluci je potøeba pou
ít pouze omezený poèet bodù impulzní odezvy h(k,l) omezením velikosti konvoluèní masky.

Obr.5.8 Ideální nízkofrekvenèní 1D filtr a øez ideálním 2D filtrem Proto v prostorové oblasti omezíme konvoluèní filtr na koneèný poèet bodù ale tak, aby dostateènì dobøe aproximoval ideální filtr H(u,v). Existuje více metod konstrukce “dobrého” digitálního konvoluèního fitru. Jednou z mo
ností je konstrukce tzv. FIR (Finite Impulse Response) filtru metodou oøezového okna (windowing). Touto metodou se oøe
e impulsní odezva h(k,l) násobením oøezovým oknem.

67

ì1 w( x, y ) = í î0

pro - a £ x £ a, - b £ y £ b jinde

(5.25)

Pøi konstrukci filtru se postupuje tak,
e se provede FT oøezané impulzní odezvy a tak dostaneme nový frekvenèní pøenos H(u,v) a kontrolujeme jeho prùbìh, jak se liší od ideálního obdélníkového prùbìhu. V pøípadì vìtší deformace vhodnì upravíme oøezové okno v prostorové oblasti. V praxi se pou
ívají další tvary "vyhlazených" oken, které eliminují nìkteré nedostatky (napø. artefakty na hranách) obdélníkového okna (viz obr.5.9 pro jednu souøadnici).

Obr.5.9 Oøezová okna Pøíklad 5.2 Proveïte pomocí modulu Image Processing programu Mathematica filtraci obrazu Vzam1.bmp pomocí funkce WindowFilter2D. Parametry filtru: velikost (poèet bodù N), zadání po
adované frekvenèní charakteristiky v bodech zlomù (v rozmezí 0-0.5), hodnoty frekvenèní odezvy a tvar okna v prostorové oblasti (Hamming, Box, Bartlett atd). Pøíkazy: <
68

6. Rekonstrukce obrazu Rekonstrukce (obnovení) obrazu je technika operací pøedzpracování obrazu, která se sna
í potlaèit narušení obrazu na základì znalosti nebo odhadu poruchy. Obraz mù
e být degradován geometricky, kdy pozice jednotlivých pixelù mohou být posunuty oproti jejich správné pozici, nebo jasovì, kdy se po zpracování zmìní jasy jednotlivých pixelù. Zamìøíme se na jasové lineární degradace, pro které mù
eme narušený obraz modelovat jako konvoluci nenarušeného obrazu s degradaèní funkcí. Jako pøíklady dobøe odstranitelných degradací mù
eme uvést: • relativní pohyb mezi objektem a kamerou (pohybující se objekt zpùsobí rozmazání) • rozostøení vlivem optiky • turbulence atmosféry u zpracování obrazù z astronomie nebo dálkového prùzkumu Zemì.

6.1 Lineární model degradací Z pøedchozího výkladu víme,
e výstupní obraz po lineární transformaci mù
eme modelovat pomocí konvoluèní sumy, za pøepokladu prostorové invariantnosti této transformace gD ( x, y ) =

N -1 N -1

å å f (a ,b ) × h

D

a = 0 b= 0

( x - a , y - b ) = f ( x, y ) * hD ( x, y )

(6.1)

Pro úèely rekonstrukce obrazu oznaèíme gD(x,y) degradovaný obraz, f(x,y) nedegradovaný obraz a hD(x,y) prostorovou impulsní odezvu (PSF), která charaterizuje degradaèní efekt. V maticové formì mù
eme tuto rovnici psát (viz kap.2) jako gD = HD f, kde gD je vektorový tvar matice výstupního degradovaného obrazu, f vektorový tvar matice vstupního nedegradovaného obrazu a HD je matice degradaèní transformace. Na základì konvoluèního teorému mù
eme konvoluci mezi nedegradovaným obrazem f(x,y) a impulsní odezvou PSF hD(x, y) vyjádøit pomocí Fourierovy transformace GD ( u, v ) = F( u, v ) × HD ( u, v )

(6.2)

kde GD, F jsou Fourierovy transformace obrazù gD a f a HD je Fourierova transformace impulsní odezvy hD.

6.2 Øešení problému rekonstrukce Rekonstruovat originální obraz z jeho degradované formy mù
eme za pøedpokladu,
e se nám podaøí získat prostorovou impulsní odezvu hD(x, y) degradaèního procesu nebo její Fourierovu transformaci HD(u,v), která se nazývá frekvenèní pøenos MTF. Frekvenèní pøenos degradace mù
eme získat dvìma zpùsoby: • Mù
eme se pokusit získat HD(u,v) nebo hD(x,y) nasnímáním scény s jednoduchými objekty z efektu degradace na tyto objekty.

69

• Ze znalosti fyzikálního procesu, který degradaci zpùsobuje. Napøíklad pokud je degradace zpùsobena pohybem kamery vùèi snímané scénì (rozmazaný obraz), potom mù
eme HD(u,v) vypoèítat. V prvním pøípadì aplikujeme na jednoduchý obraz, napøíklad obdélníkové funkce I(x,y), konkrétní typ zpracování, které zpùsobuje degradaci obrazu (napø. snímání nevhodnou optikou). Získáme tak degradovaný obraz ID(x,y). Pomocí Fourierovy transformace pøevedeme ID(x,y) do frekvenèní oblasti a dostaneme funkci ID(u,v). Dále aplikujeme Fourierovu transformaci pøímo na obdélníkovou funkci, tedy výpoètem získáme nedegradovanou funkci I(u,v) ve frekvenèní oblasti. Napøíklad pro jednorozmìrnou obdélníkovou funkci I(x) s amplitudou A a šíøkou t platí I ( u) =

(

A 1 - e - jut ju

)

(6.3)

Potom z rovnice 6.2 frekvenèní pøenos degradace HD ( u, v ) =

ID ( u, v ) I ( u, v )

(6.4)

Zpìtná Fourierova transformace pøenosové charakteristiky HD(u,v) je potom prostorová impulsní odezva hD(x, y). Frekvenèní pøenos HD(u,v) mù
eme potom pou
ívat na rekonstrukci rùzných obrazù degradovaných tímto konkrétním typem zpracování pou
itím rovnice 6.2. F( u, v ) =

GD ( u, v ) HD ( u, v )

(6.5)

Na obr.6.1 je uveden pøíklad obrazu mo
né testovací funkce slo
ené z jednotkových obdélníkových funkcí v rùzných smìrech pro výpoèet frekvenèního pøenosu degradace pro tyto smìry.

Obr.6.1 Testovací obrazec pro zjištìní HD(u,v)

70

V dalším odvodíme frekvenèní pøenos degradace vzniklé pohybem scény o hodnoty x0(t), y0(t) (jsou funkcí èasu). Uzávìrka kamery je otevøena od t = 0 do t = T. Pøedpokládáme,
e pøi statické scénì bychom nasnímali obrazovou funkci f(x,y). Degradovaná hodnota jasu na posici [x,y] T

gD ( x, y ) = ò f [x - x 0( t ), y - y 0( t )] dt

(6.6)

0

Pro statickou scénu toti
platí x0(0) = 0, y0(0) = 0. Z toho vyplývá,
e g(x,y) = f(x,y) a obraz se pøi snímání nedegraduje. Pro hodnotu T = t1 se naexponuje obraz posunutý o x0(t1), y0(t1), podobnì pro T = t2 atd. Vznikne tak rozmazaný obraz scény (viz obr.6.2).

Obr.6.2 Rozmazaný obraz v dùsledku pohybu scény a jeho rekonstrukce Pøenos degradace odvodíme pomocí spojité Fourierovy transformace (rov. 3.26). Fourierova transformace funkce g (x,y) (pøedpokládáme prostorovou periodu X = 1) GD ( u, v ) =

¥ ¥

ò òg

D

( x, y )e -2pj (ux + vy) dxdy

(6.7)

-¥-¥

GD ( u, v ) =

¥ ¥ T

ò ò ò f ( x - x ( t ), y - y ( t ))dt e 0

0

-2pj (ux + vy)

dxdy

(6.8)

dxdy}dt

(6.9)

-¥-¥ 0

Zamìníme poøadí integrálù T

¥ ¥

GD ( u, v ) = ò{ ò 0

ò f ( x - x ( t ), y - y ( t ) e 0

0

-2pj (ux + vy)

-¥ -¥

Ve slo
ených závorkách je FT funkce f posunuté o x0 a y0. FT posunuté funkce je FT neposunuté funkce násobená faktorem e -2pj (ux0 + vy0 ) . Potom T

GD ( u, v ) = ò F( u, v )e -2pj (ux0 (t ) + vy0 (t )) dt 0

71

(6.10)

F(u,v) vytkneme pøed integrál a provedeme podíl HD(u,v) = GD(uv)/F(u,v) (vyplývá z konvoluèního teorému). Tak dostaneme frekvenèní pøenos T

HD ( u, v ) = ò e -2pj (ux0 (t ) + vy0 (t )) dt

(6.11)

0

Pøedpokládejme pohyb pouze ve smìru x s rychlostí a/T, tedy x0(t) = a t /T. Potom y0(t)=0 a frekvenèní pøenos bude T

HD ( u, v ) = ò e

-2pju

at T

(6.12)

dt

0

Po výpoètu integrálu bude HD ( u, v ) =

(

T 1 - e -2pjua 2pjua

)

(6.13)

Po úpravách je výsledný vztah frekvenèního pøenosu pro rozmazaný obraz HD ( u, v ) =

T sin( pua ) - jpua e pua

(6.14)

Další typické pøenosy Pro zkreslení zpùsobené rozostøením optiky HD ( u, v ) =

[

]

J 1 a( u 2 + v 2 ) a( u + v ) 2

(6.15)

2

Pro zkreslení vlivem turbulencí atmosféry v dálkovém prùzkumu Zemì é HD ( u, v ) = expê- c u 2 + v 2 ë kde c je experimentální konstanta.

(

zobrazovací s ous tava

hD(x,y) f(x,y)

)

5 6

ù ú û

(6.16)

rekons trukèní filtr

gD(x,y)

+

hR (x,y) fR (x,y)

n(x,y)

Obr. 6.3 Rekonstrukce obrazu pomocí inverzního filtru

72

Inverzní filtr Na obr. 6.3 je nakresleno blokové schéma rekonstrukce s pou
itím inverzního filtru. Pokud známe frekvenèní pøenos HD(u,v) degradace a pøevedeme degradovaný obraz do frekvenèní oblasti, potom mù
eme za pøedpokladu nepøítomnosti šumu jednoduše vypoèítat Fourierovu transformaci rekonstruovaného obrazu. FR ( u, v ) =

GD ( u, v ) HD ( u, v )

(6.17)

Potom pomocí zpìtné Fourierovy transformace získáme rekonstruovaný obraz fR(x,y) v prostorové oblasti. Pøevrácenou hodnotu frekvenèního pøenosu nazýváme rekonstrukèním filtrem, který aplikujeme násobením s degradovaným obrazem GD(u,v): HR ( u, v ) =

1 HD ( u, v )

FR ( u, v ) = GD ( u, v ) × HR ( u, v )

(6.18) (6.19)

Bohu
el, tento pøímoèarý postup nedává dobré výsledky. Pøíèina spoèívá v tom,
e v nìkterých bodech (u,v), obvykle v oblasti vysokých frekvencí, mù
e být HD(u,v) ® 0 (tzv. nulové body), potom HR(u,v) roste nade všechny meze. V tìchto bodech nemù
e být obraz invertován zpìt do prostorové oblasti. Další problém pøedstavuje šum. V pøípadì,
e šum není zanedbatelný, musíme rovnici 6.2 pøepsat GD ( u, v ) = F( u, v ) × HD ( u, v ) + N ( u, v )

(6.20)

kde N(u,v) je Fourierova transformace šumové slo
ky. Potom Fourierova transformace nedegradovaného obrazu F( u, v ) =

GD ( u, v ) N ( u, v ) = HR ( u, v ) × GD ( u, v ) - HR ( u, v ) × N ( u, v ) HD ( u, v ) HD ( u, v )

(6.21)

Z výsledné rovnice vyplývá,
e pokud je HR(u,v) velké, zesiluje se významnì šumová slo
ka obrazu (tzv. šumová katastrofa), co
je nepøípustné. Praktický rekonstrukèní filtr typu okna, který zabraòuje zesilování šumu volíme následovnì: HR(u,v)=1/HD(u,v) pro u2+v2 < w02

(6.22)

HR(u,v)=1 pro u2+ v2 ³ w02

(6.23)

kde w0 je prostorová frekvence taková,
e všechny nulové body HD(u,v) jsou za touto frekvencí. Tímto zpùsobem omezíme vysoké frekvence, tedy nedostaneme po rekonstrukci pøesnì vstupní nedegradovaný obraz. Výsledek bývá pøijatelný.

73

Wienerùv rekonstrukèní filtr Pokud není šum zanedbatelný a dají se odhadnout jeho statistické vlastnosti, potom lze k rekonstrukci pou
ít Wienerùv filtr. Hledáme rekonstruovaný obraz fR ( x, y ), který je statistickým odhadem nedegradovaného originálu f(x,y) . Toho se dosáhne minimalizací støední kvadratické odchylky rekonstruovaného obrazu od pùvodního

{

}

e 2 = E ( f ( x, y ) - fR ( x, y )) 2

(6.24)

kde E oznaèuje operátor støední hodnoty náhodné velièiny a odhad fR ( x, y ) je støední hodnotou náhodného procesu f(x,y), za který pova
ujeme všechny mo
né varianty f(x,y). Existenci náhodného procesu f(x,y) pøedpokládáme díky pøítomnému šumu. Bez odvození je uveden vztah pro Wienerùv optimální filtr HW(u,v) 2

H D ( u, v ) 1 HW ( u, v ) = H D ( u, v ) H ( u, v ) 2 + Svv( u,v ) D Sff ( u,v )

(6.25)

kde HD(u,v) je FT degradace, Svv výkonová spektrální hustota šumu a Sff výkonová spektrální hustota nedegradovaného obrazu. Pomìr Sff a Svv je SNR (signal noise-ratio)- pomìr signál-šum SNR =

Sff ( u, v ) Svv( u, v )

(6.26)

Potom FT odhadu rekonstruovaného obrazu FR ( u, v ) = HW ( u, v ) ×GD ( u, v )

(6.27)

Ze vztahu pro Wienerùv filtr je vidìt,
e pro aplikaci filtru musíme odhadnout statistické vlastnosti šumu a pùvodního nedegradovaného obrazu. To je dost obtí
né, kdy
výpoèet nedegradovaného obrazu je právì cílem rekonstrukce. Prakticky se Wienerùv filtr aplikuje tak,
e se pomìr Svv/Sff degradovaného obrazu násobí experimentální promìnnou g a experimentuje se s jejími rùznými hodnotami od 0 do 1. 2

H D ( u, v ) 1 HW ( u, v ) = H D ( u, v ) H ( u, v ) 2 + g Svv( u,v ) D Sff ( u,v )

(6.28)

Pro g = 0 dostáváme inverzní filtr, hodnoty mezi 0 a 1 definují tzv. parametrický Wienerùv filtr, který je optimalizovaný pro daný konkrétní pøípad.

74

7. Segmentace objektù v obraze Úèelem segmentace je získání oblastí z obrazu t.j. rozdìlení obrazu na èásti, které jsou slo
eny z pixelù podobných vlastností (napø. podobného jasu nebo barvy). Tyto vlastnosti indikují,
e se jedná o stejné objekty nebo stejné rysy objektù. Hlavními pøístupy k segmentaci objektù jsou prahování (thresholding), metody zalo
ené na prostorových souvislostech (narùstání oblastí, urèování hranice objektu) a segmentace zalo
ená na srovnávání se vzorem. Na obr.7.1 je uveden pøíklad segmentace purpurových tiskových bodù z barevného vzorku tisku.

Obr.7.1 Segmentace purpurových tiskových bodù

7.1 Prahování Pøi prahování se vyu
ívá histogramu jasu obrazu. Histogram je odhadem hustoty pravdìpodobnosti hodnot jasu. Pokud máme napø. obraz svìtle šedých objektù na èerném pozadí, bude mít histogram dva výrazné vrcholy a mezi nimi údolí (obr.7.2). My mù
eme jako segmentaèní práh t0 (globální práh) pou
ít hodnotu jasu, odpovídající minimu údolí v histogramu. Pixely, které mají hodnoty jasu nad hodnotou prahu patøí do objektù, pixely s jasem pod prahem patøí do pozadí. Tímto zpùsobem klasifikujeme pixely do dvou skupin. Ve výsledku se mohou objevit následující chyby segmentace: • v segmentovaných objektech chybí pixely, které tam patøí • v segmentovaných objektech jsou pixely, které patøí do pozadí

Obr.7.2 Histogram se dvìma vrcholy

75

Málokdy se stává,
e jeden globální práh je optimální pro všechny objekty v obraze. Jednou z metod, jak obejít problém s globálním prahem je rozdìlit obraz na nìkolik èástí a v ka
dé èásti poèítat lokální práh. Hodnota lokálního prahu je závislá na lokálních vlastnostech obrazu. Velmi èasto se stává,
e histogram jasu nemá výrazné údolí a je obtí
né urèit optimální práh. Existují toti
pixely, jejich
jasy je øadí jak do objektù, tak do pozadí. V takovém pøípadì lze pou
ít prahování s hysterezí: místo jednoho prahu se pou
ijí dva prahy T1 a T2 na ka
dé stranì údolí (obr.7.2). Vìtší je v pøípadì bílých objektù pou
it pro segmentaci hlavního jádra objektù. Menší práh je pak následnì pou
it ve spojení s "prostorovou blízkostí" pixelù jádra. Prakticky to znamená,
e pokud je pixel, získaný menším prahem a sousedí s jádrem, je pak oznaèen jako pixel bílého objektu. Pokud nesousedí s jádrem, je zaøazen do èerného pozadí. Optimalizace globálního prahu Iteraèní metoda Jinou cestou, jak obejít neurèitost získání prahové hodnoty z histogramu je urèení optimálního globálního prahu. Tím omezíme poèet špatnì klasifikovaných pixelù. Jedna z iteraèních metod je zalo
ena na minimalizaci rozdílu prùmìrné hodnoty jasù pixelù objektu a jasù pixelù pozadí bìhem iteraèního procesu. Pøedpokládáme bimodální histogram a šedé objekty na bílém pozadí. Postup bude následující: • první odhad prahu udìláme z histogramu jasu pùvodního obrazu tìsnì za prvním maximem • provedeme segmentaci objektù s tímto prahem a ulo
íme výsledný obraz segmentovaných objektù • provedeme logický rodíl mezi pùvodním obrazem a obrazem segmentace objektù, tak dostaneme obraz segmentovaných pixelù pozadí • vypoèítáme prùmìr hodnot jasu m1 z obrazu segmentace objektù a prùmìr hodnot jasu m2 z obrazu segmentace pozadí . Z nich vypoèítáme novou hodnotu prahu podle rovnice TN =

m1 + m 2 2

(7.1)

• vypoèítáme rozdíl nového vypoèítaného prahu s pøedchozí hodnotou • pokud je rozdíl vìtší, ne
stanovená minimální hodnota, pokraèujeme segmentací s novým prahem • postup opakujeme v
dy s novou hodnotou prahu, a
je rozdíl mezi dvìma po sobì následujícími hodnotami prahù menší nebo rovna zadané minimální hodnotì Metoda za pøedpokladu vhodného pøedzpracování obrazu dobøe konverguje a obvykle staèí ménì ne
10 iterací. Pracuje spolehlivì, pokud jsou v histogramu pouze dvì maxima. Pøíklad 7.1 Pomocí modulu Image processing programu Mathematica vypoèítejte optimální práh segmentace obrazu Sep1yel.bmp. V notebooku napíšeme pøíkazy: <
76

Show[GraphicsArray[Graphics[imgsep]]];+ Shift Enter imgr = Round[imggray];+ Shift Enter ShowImage Histogram[ImageHistogram[imgr]];+ Shift Enter Print[OptimumThreshold[imgr];+ Shift Enter imgseg = Threshold[imgr,109];+ Shift Enter Show[GraphicsArray[{Graphics[imgsep],Graphics[imgseg]}]];+ Shift Enter Pravdìpodobnostní pøístup Další metoda vyu
ívá odhadu statistického rozlo
ení pixelù objektù a pixelù pozadí k minimalizaci špatnì klasifikovných pixelù. Musíme znát pøedem pøibli
né èíslo, které charakterizuje pomìr poètu pixelù objektù a pixelù pozadí. Oznaème hustotu pravdìpodobnosti objektù po(x) a pozadí pb(x). Pøedpokládejme práh segmentace t (obr.7.3). Potom bude chyba špatnì klasifikovaných pixelù objektù (objeví se jako pixely po¥ t zadí) ò po( x )dx a chyba špatnì klasifikovaných pixelù pozadí (budou souèástí objektù) ò pb( x )dx. -¥

t

Obr.7.3 Optimalizace prahu Oznaème q èást která tvoøí pixely objektù v obraze, potom èást pozadí bude rovna 1- q. Musíme tedy znát pøibli
nì pomìr poètu pixelù objektù a pixelù pozadí. Celková chyba potom bude ¥

t

E( t ) = q ò po( x )dx + (1 - q )ò pb( x )dx -¥

t

Rovnice pro práh t za pøedpokladu,
e E(t) bude minimální, tedy ¶E = q po( t ) - (1 - q ) pb( t ) = 0 ¶t

¶E =0. ¶t

q × po( t ) = (1 - q ) × pb( t ) Tato rovnice platí pro libovolné rozdìlení funkce hustoty pravdìpodobnosti.

77

(7.2)

(7.3) (7.4)

Pokud pøedpokládáme normální rozlo
ení pro pixely objektù i pozadí, platí 1 po( t ) = exp 2pso

1 pb( t ) = exp 2psb

(t -m 0 ) 2 2 s 20

(7.5)

(t -m b ) 2 2 s b2

(7.6)

Potom dosazením do rov. 7.4 za pøedpokladu so = sb mù
eme odvodit vztah pro práh t s minimální chybou segmentace [1] t=

so 2 æ 1 - q ö mo - mb lnç ÷2 mo - mb è q ø

(7.7)

7.2 Narùstání oblastí Metodu narùstání (rozšiøování) oblastí pou
íváme v pøípadì, kdy je obtí
né urèení hranic oblastí a tím selhává i metoda prahování, popøípadì metoda detekce hran. Základní myšlenkou metody rozšiøování oblastí je rozèlenit obrazy do souvislých oblastí tak, aby byly relativnì homogenní. Kritérium homogenity H(R) se mù
e opírat o jasové nebo barvové vlastnosti. Napøíklad to mù
e být u monochromatického obrazu støední hodnota jasu a její rozptyl. Obecnì mù
eme pou
ít metodu rozšiøování oblastí, pokud máme v oblasti tzv. semínkový pixel, který patøí do oblasti objektù. Od tohoto pixelu zkoumáme pixely jeho okolí a rozhodujeme se na základì pøedem známých atributù homogenity, jestli pixely z tohoto okolí do oblasti patøí nebo nepatøí. Jako semínkové pixely mù
eme pou
ít oblasti po segmentaci prahováním, kdy je prahová hodnota menší ne
optimální. Potom je metoda narùstání oblasti pou
ita ke zpøesnìní segmentace prahováním. V pøípadì,
e nemáme k disposici semínkové pixely, pou
íváme metody spojování, štìpení a kombinaci spojování a štìpení. Narùstání oblastí pomocí semínkových pixelù Jedním s vhodných modelù pro segmentaci barevných obrazù je model HSB (Hue, Saturation, Brightness). Hue je v intervalu 0-360°, S a B v intervalu 0-1. Ze souøadnic R, G, B obrazu vypoèítáme souøadnice H, S, B podle následujících vztahù [12]: Pro Hue mezi yellow a magenta, tedy MAX(R,G,B) = R: H=

MAX ( R, B, G ) - B MAX ( R, G , B) - G MAX ( R, G , B ) - MIN ( R, G , B) MAX ( R, G , B) - MIN ( R, G , B)

Pro Hue mexi cyan a yellow, tedy MAX(R,G,B) = G: H =2+

MAX ( R, B, G ) - R MAX ( R, G , B) - B MAX ( R, G , B) - MIN ( R, G , B) MAX ( R, G , B) - MIN ( R, G , B)

78

Pro Hue mezi cyan a magenta, tedy MAX(R,G,B) = B: H = 4+

MAX ( R, B, G ) - G MAX ( R, G , B) - R MAX ( R, G , B ) - MIN ( R, G , B) MAX ( R, G , B ) - MIN ( R, G , B)

Pro pøevod do intervalu 0-360° se provede H=60*H. Je-li S=0 je H nedefinováno a je-li H<0, potom se provede H=H+360.

S=

MAX ( R, G , B )) - MIN ( R, G , B) MAX ( R, G , B)

S =0

pro MAX ( R, G , B) > 0

pro MAX ( R, G , B) = 0

B = MAX ( R, G , B) V dalším kroku rozšiøování oblasti zjistíme statistické hodnoty velièin výbìrového prùmìru a výbìrového rozptylu jednotlivých slo
ek H, S, B semínkových pixelù. Napøíklad pro slo
ku H H=

1 NS å Hi , NS i=1

sH 2 =

NS 2 1 × å ( Hi - H ) NS - 1 i=1

(7.8)

kde NS je poèet semínkových pixelù. Za pøedpokladu normálního rozlo
ení velièin H, S, B mù
eme testovat pixely z okolí semínkových pixelù, jestli patøí do testované oblasti nebo ne. Pokud testovaný pixel do oblasti patøí, tak o nìj oblast rozšíøíme. Testování provádíme pomocí statistických testù (napø. studentùv t-test) na zvolené hranici významnosti a, èím
je definován tzv. interval spolehlivosti. Pokud hodnota testované velièiny, napøíklad H, padne do tohoto intervalu, potom mù
eme s pravdìpodobností 1-a øíci,
e tento pixel do semínkové oblasti patøí.

7.3 Štìpení a spojování oblastí Na zaèátku zpracování je celý obraz pova
ován za jednu oblast. Napøíklad u jednoduchých vzorkù se dvìma druhy oblastí se urèí kritérim homogenity H(R) pro objekty oblasti R . Jestli
e vypoèítané hodnoty pixelù vyboèují z tolerancí kritéria (H(R) = FALSE), oblast není homogenní. Potom je oblast R rozdìlena do ètyø kvadrantù R1, R2, R3, R4 a ka
dý kvadrant je pak testován stejnì jako v pøedchozím kroku. Ty, které kritérium homogenity nesplní, se štìpí dál. V tom samém kroku se testují dvojice vzniklých štìpením (i z pøedchozích krokù) vzájemnì pøilehlých oblastí a pokud splòují stejné kritérium homogenity, tak se spojí do jedné oblasti. Potøebný poèet krokù je dán stavem, kdy jsou ve všech podoblastech splnìna pøedem definovaná kritéria homogenity. Nakonec nastává proces spojování malých oblastí pøilehlých k vìtším tzv. podobným oblastem (s malou odchylkou od kritéria homogenity) z dùvodu odstranìní oblastí pøíliš malých rozmìrù.

79

Obr.7.4 Segmentace štìpením oblastí Na obr.7.4 je pro jednoduchost prezentován èernobílý obraz 8´8 bitù a jeho štìpení do homogenních oblastí. Stromová struktura ukazuje úspìšné štìpení obrazu do jednotlivých kvadrantù. Tato stromová struktura se nazývá kvadrantový strom. Na konci štìpení dostaneme následující oblasti: (AFIE) (FBGI) (GKNJ) (JNMI) (MNLH) (KCLN) (RSXV) (SMTX) (THUX) (XUOV) (QIMR) (EQRP) (PROD) To jsou potomci kvadrantového stromu. Ka
dá dvojice pøilehlých oblastí je pak testována na stejné kritérium homogenity a spojena, pokud ho obì splòují. Toto testování se provádí u
pøi štìpení, nikoliv a
po rozštìpení na koneèný kvadrantový strom. Algoritmus štìpení a spojování mù
e startovat i na vyšší úrovni kvadrantového stromu, místo štìpení na 2´2 bloky na 2k ´ 2k, k
7.4 Detekce hran Detekce hran je operace nutná k urèování hranic objektù. Hrana na urèitém pixelu je vlastnost tohoto pixelu a jeho malého okolí. Popisuje, jak rychle se mìní hodnota obrazové funkce g(x,y) v tomto okolí. Zmìnu obrazové funkce udává její gradient. Pixely s velkými hodnotami modulu gradientu v jejich okolí se nazývají hranami. Velikost a smìr gradientu

|Ñ g ( x, y )| =

y = arctg

2

æ dg ö æ dg ö ÷ ç ÷ + ç è dx ø è dy ø

dg / dy dg / dx

2

(7.9)

(7.10)

Na principu hledání maximální hodnoty modulu gradientu v okolí pixelu jsou zalo
eny Sobelùv operátor, Robertsùv operátor, operátor Prewittové a další.

80

Pokud nás zajímá jen velikost gradientu, pou
ívá se všesmìrový Laplaceùv operátor (Laplacián), který vychází z druhých parciálních derivací. Ñ 2 g ( x, y ) =

d 2 g ( x, y ) d 2 g ( x, y ) + dx 2 dy 2

(7.11)

Pro monotónnì rostoucí obrazovou funkci v místech maximální velikosti gradientu |Ñg(x,y)| je Laplacián roven nule (druhá derivace zde prochází nulou). Potom hrany hledáme v místech prùchodu Laplaciánu nulou. Tato metoda je dost citlivá na pøítomnost šumu v obraze. Detekce hran na základì hledání zmìny obrazové funkce je u digitalizovaného obrazu zalo
ena na výpoètu rozdílù jasu pixelù v okolí urèité velikosti kolem vyhodnocovaného pixelu místo výpoètu parciálních derivací. Takovýmto zpùsobem rozdìlíme pixely na skupinu s velkými hodnotami rozdílù jasù (velkými hranami) a skupinu s malými hranami, zbytek je mezi tìmito hodnotami. V místì velkých hran jsou pak hranice oblastí v obraze, co
mù
e být vyu
ito k zaostøování obrysù oblastí, nebo segmentaci tìchto oblastí. Postup pøi výpoètu hran konvolucí Pøi výpoètu hran posouváme horizontálnì po obraze postupnì okno velikosti, která charakterizuje okolí pixelù. Na ka
dé pozici tohoto okna vyhodnocujeme hodnoty pixelù v jedné polovinì a pak ve druhé polovinì okna a výsledky srovnáme (obr.7.5). Místa s velkými rozdíly jsou místa hran, tedy místa hranic objektù.

x x x x x x x x x

x x x x x x x x x

x x x x x x x x x

x x x x x x x x x

x x x x x x x x x

x x x x x x x x x

x x x x x x x x x

x x x x x x x x x

x x x x x x x x x

Obr.7.5 Princip detekce hran Oblast O pøedstavuje pøedstavuje pixely, na kterých poèítáme hranu, oblasti A, B pøedstavují dvì poloviny okolí, ze kterých poèítáme statistické parametry, mohou to být kromì diferencí také smìrodatné odchylky jasu sA, sB v obou polovinách a odchylka s v celém oknì. Vypoèítáme napøíklad hodnotu E = 2s - sA - sB

(7.12)

Tuto hodnotu pøiøadíme centrálním pixelùm v oblasti O. Pokud takto prozkoumáme celý obraz, pak lokální maxima hodnot E jsou horizontální hranice objektù v obraze. Podobnì mù
eme testovat celé okno ve vertikálním smìru a poèítat vertikální hranice. Je zøejmé,
e velkou roli zde hraje velikost okna, ve kterém poèítáme statistické parametry.

81

Nejmenší mo
né okno, které lze pou
ít tvoøí dva pøilehlé pixely. Potom lze poèítat rozdíl jasù tìchto pøilehlých pixelù. Pokud je rozdíl dostateènì velký, øekneme,
e mezi obìma pixely je významná hrana. Rozdíly jasù ve smìrech x a y Dfx = f ( i + 1, j ) - f ( i, j )

(7.13)

Dfy = f ( i, j + 1) - f ( i, j )

(7.14)

Tyto rovnice jsou ekvivalentní horizontální konvoluci s maskou ru s maskou . -1 1

-1

a ve vertikálním smì-

1

Problémem u tohoto jednoduchého zkoumání hran je, kterému pixelu z této dvojice pøidìlíme atribut hrany. Teoreticky je hrana mezi obìma pixely masky, ale v praxi mù
eme hranu pøidìlit pouze jednomu pixelu masky. Hlavní nevýhodou tohoto jednoduchého zjišování hran v obraze je,
e jakákoliv malá šumová fluktuace výraznì ovlivní výsledek. Proto je vhodné pou
ití vìtší masky. Pro 2D obraz to bude dvoudimenzionální maska, minimální velikost masky pro souèasné vyhlazení a výpoèet diferencí je 3´3 pixely. Výpoèet diferencí se potom provádí pro centrální pixel, kterému se pøidìluje hodnota velikosti hrany. Sobelùv operátor detekce hran Obecný tvar masky Sobelova detektoru hran (pro smìr y) K æ1 ç h=ç 0 0 ç -1 - K è

1ö ÷ 0÷ -1÷ø

(7.15)

Sobelùv operátor je vhodný pro obrazy s malým šumem, pou
ívá odvozenou masku pro rùzné hodnoty K. Pokud zvolíme K = 2, potom Sobelovy masky pro smìr x a y mají tvar (hx vznikne po rotaci hy o 90° vpravo): æ1 2 1ö ç ÷ hy = ç 0 0 0 ÷ ç -1 -2 -1÷ è ø

æ -1 ç hx = ç - 2 ç -1 è

0 0 0

1ö ÷ 2÷ 1 ÷ø

(7.16)

Potom rovnice diferencí (centrální pixel je I(i,j), kladný smìr doprava a dolù) DIx = -I ( i - 1, j - 1) - 2I ( i - 1, j ) - I ( i - 1, j + 1) + I ( i + 1, j - 1) + 2I ( i + 1, j ) + I ( i + 1, j + 1)

82

(7.17)

DIy = I ( i - 1, j - 1) + 2I ( i, j - 1) + I ( i + 1, j - 1)

(7.18)

- I ( i - 1, j + 1) - 2I ( i, j + 1) - I ( i + 1, j + 1) Velikost a smìr hrany je potom E = DIx + DIy

y = arctan

DIy DIx

(7.19)

Pøíklad 7.2 Detekujte hrany obrazu books.tif a Sep1yel.bmp pomocí Sobelova operátoru. V notebooku programu Mathematica napíšeme pøíkazy: <
(7.20)

Laplaceùv operátor patøí do skupiny operátorù, které vyhledávají hrany z druhých derivací (diferencí) obrazové funkce, respektive v místech, kde tato druhá derivace nabývá nulové hodnoty. Pokud aplikujeme Laplaceùv operátor pøímo na obrazovou funkci, budeme mít obvykle potí
e se šumem, který mù
e výraznì ovlivnit koneèný výsledek. Pokud pøed aplikací Laplaceova operátoru pou
ijeme vyhlazení filtrem ve tvaru Gaussovy køivky, potom mù
eme místa, kde druhá derivace prochází nulou urèit s mnohem vìtší pøesností. Pøedpokládejme filtr ve tvaru normalizovaného 2D Gaussiánu G ( x, y ) = e

-

x2 + y2 2s 2

(7.21)

Pro Laplacián konvoluce obrazu a vyhlazovacího filtru mù
eme psát [3] Ñ 2 (G * g ) = (Ñ 2G )* g = 0

83

(7.22)

Laplacián Gaussova filtru G (LoG operátor) mù
eme vypoèítat analyticky, následnì se provede konvoluce výsledku a zpracovávaného obrazu. Po odvozenídostaneme vztah pro hodnoty konvoluèní masky æ x2 + y2 -s2 h( x, y ) = c çç s4 è

ö ÷÷ e ø

x2 + y2 2 s2

(7.23)

kde c je koeficient zajišující, aby souèet všech koeficientù v masce byl roven nule. Výpoètem z této rovnice 5´5 LoG operátor æ 0 0 -1 0 0 ö ÷ ç ç 0 -1 -2 -1 0 ÷ h( x, y ) = ç -1 -2 16 -2 -1÷ ÷ ç ç 0 -1 -2 -1 0 ÷ ç 0 0 -1 0 0 ÷ ø è

(7.24)

Pøíklad 7.3 Pomocí Laplaciánu 3´3 detekujte významnou hranu v obraze f. æ0 1 0ö ç ÷ L = ç 1 -4 1 ÷ , ç0 1 0÷ è ø

æ1 10 10 ö ç ÷ f = ç1 10 10 ÷ ç1 10 10 ÷ è ø

Rozšíøíme si okraje obrazu æ10 ç ç10 f = ç10 ç ç10 ç10 è

1 1 1 1 1

10 10 10 10 10

10 10 10 10 10

1ö ÷ 1÷ 1÷ ÷ 1÷ 1÷ø

Aplikujeme konvoluèní masku Laplaciánu na jednotlivé pixely pùvodního obrazu g11 = 1 + 10 - 4 + 10 + 1 = 18 g12 = 1 + 10 - 40 + 10 + 10 = -9 M g 33 = 10 + 1 - 40 + 10 + 10 = -9

84

Po výpoètu všech hodnot je obraz hrany æ18 -9 -9 ö ç ÷ g = ç18 -9 -9 ÷ ç18 -9 -9 ÷ è ø Výsledná hrana je detekována zmìnou znaménka. Cannyho detektor hran V pøípadì obrazù s významnými úrovnìmi Gaussovského šumu je pou
ití Sobelova operátoru problematické. Pøi hledání hran je problémem správnì zvolené mìøítko, tedy správná velikost okolí, ve kterém hrany hledáme. Správná velikost okolí závisí toti
také na velikostech pro nás zajímavých objektù. Hledání nejlepšího okolí realizuje Cannyho hranový detektor. Základní myšlenka spoèívá v realizaci frekvenèního filtru (je to v podstatì vysokofrekvenèní filtr - horní propust), který má dobrou impulsní odezvu v prostorové oblasti za podmínky splnìní tzv. Cannyho kritérií: • šumové kritérium po
aduje na výstupu filtru dobrý pomìr SNR (Signal to Noise Ratio), který zajistí, aby detektor nereagoval na šumové zmìny hrany • detekèní kritérium po
aduje, aby významná hrana nebyla pøehlédnuta, ale aby na jednu hranu nereagoval vícekrát (falešné odezvy) • lokalizaèní kritérium po
aduje, aby rozdíl mezi skuteènou hranou a její nalezenou polohou byl minimální

Obr.7.6 Zašumìná 1D hrana Pøedpokládejme,
e chceme detekovat hranu u(x), která je “zapuštìna” do šumu n(x) pomocí filtraèní funkce f(x). Pøedpokládáme jednorozmìrný signál (obr.7.6). Canny dokázal,
e filtr f(x) implikuje na výstupu maximální pomìr SNR, jestli
e je konstruován za pøedpokladu maximalizace velièiny ¥

Sº

ò f ( x )u( -x )dx

-¥

¥

òf

2

( x )dx

-¥

85

(7.25)

Dále prokázal,
e filtraèní funkce f(x) detekuje hrany s minimální chybou oproti skuteèné poloze, kdy
je konstruován za pøedpokladu maximalizace velièiny ¥

Lº

ò f ¢¢( x )u( -x )dx

-¥

¥

ò [ f ¢( x )]

2

(7.26)

dx

-¥

Nakonec odvodil,
e konvoluce signálu s filtrem f(x) vykazuje minimum falešných odezev za pøedpokladu maximalizace velièiny ¥

Dº

ò [ f ¢( x )]

2

dx

-¥

(7.27)

¥

ò [ f ¢¢( x )]

2

dx

-¥

Canny na základì tìchto kritérií odvodil optimální konvoluèní hranový filtr. Následnì se ukázalo se,
e tento filtr lze s chybou menší ne
20 % aproximovat derivací 2D Gaussiánu a to tak,
e koeficienty konvoluèní masky filtru odpovídají této funkci. Na obr. 7.7 je provedena detekce hran rozmazaného zašumìlého obrazu pomocí Sobelova detektoru hran. Výsledek není moc uspokojivý. Na obr.7.8 jsou prezentovány výsledky pou
ití optimálního Cannyho filtru s rùznými velikostmi filru (13´13 a 21´21) na tentý
vstupní obraz. Výsledek je v pøípadì Cannyho detektoru výraznì lepší.

Obr.7.7 Detekce hran Sobelovým operátorem Pøíklad 7.4 Detekujte hrany obrazu Sep1yel.bmp pomocí Laplaciánu a LoG filtru. V notebooku napíšeme pøíkazy: <
86

Obr.7.8 Detekce hran optimálním Cannyho filtrem

Ostøení obrazu Gradientních operátorù lze vyu
ít i k ostøení obrazu. Cílem ostøení je upravit ho tak, aby v nìm byly strmìjší významné hrany. Pro zaostøený obraz f mù
eme psát rovnici ostøení f ( x, y ) = g ( x, y ) - C × S ( x, y )

(7.28)

kde C je kladný souèinitel “síly” ostøení, S je strmost zmìny obrazové funkce v daném bodì daná velikostí gradientu v tomto bodì. Strmost mù
e být urèena napøíklad pomocí Sobelova operátoru.

87

8. Mìøení vlastností objektù v obraze Výsledkem segmentace obrazu jsou objekty, u kterých mù
eme zjišovat jejich vlastnosti. Tyto vlastnosti mù
eme rozdìlit do ètyø základních skupin: velikost, poloha, tvar a jas. Ty se mohou dále dìlit na další charakteristiky, napø. popis jasu mù
e obsahovat popis barevných charakteristik, popis polohy mù
e obsahovat parametry orientace nebo vzájemné polohy sousedních objektù [5]. Namìøené charakteristiky nám pak umo
òují klasifikovat objekty do tøíd, co
je dùle
itý krok k rozpoznávání obrazu a k realizaci poèítaèového vidìní. My se budeme zabývat podrobnìji nìkterými vlastnostmi objektù, které urèitým zpùsobem souvisejí s vyhodnocováním charakteristik tiskových motivù.

8.1 Mìøení velikosti Základními velièinami charakterizující velikost jsou prùmìr (diameter) objektu (maximální a minimální), plocha (area) objektu a obvod (perimeter) objektu. V rastrové reprezentaci objektu to mohou být poèty pixelù, kterými jsou tyto velièiny urèeny (napøíklad lze takto urèovat plošné pokrytí výøezu obrazu tiskovou barvou). Parametry velikosti mù
eme také poèítat v klasických jednotkách, musíme pak provést kalibraci napøíklad pomocí lineární mìrky, která se snímá souèasnì se vzorkem obrazu. Pro vìtšinu praktických aplikací je charakteristika poètu pixelù objektu v obraze vhodná. Výpoèet relativního plošného krytí Pro urèování parametru relativního plošného krytí (objekty vzhledem k pozadí) je z dùvodu pøesnosti a reprodukovatelnosti výsledku dùle
itá definice oblasti vzorku, ze kterého tento parametr poèítáme. Na obr.8.1 jsou mo
nosti definice takové oblasti v pravidelné struktuøe objektù.

Obr.8.1 Definice oblasti vzorku tisku pro výpoèet plošného krytí Potom je vztah pro relativní plošné krytí v procentech F=

NO ×100 NO + NP

(8.1)

kde NO je poèet pixelù objektù ve výøezu vzorku a NP je poèet pixelù pozadí. Tento vztah se pou
ívá v oblasti tisku pro výpoèet parametru geometrické síové tónové hodnoty. Druhou mo
ností je definovat oblast vzorku libovolnì, s vìtším poètem objektù ve vzorku. Potom musíme vyøíznout a ulo
it více vzorkù a z nich vypoèítat prùmìrnou hodnotu (výbìrový prùmìr) parametru plošného krytí.

89

Výpoèet obvodu Obvod je také mo
né charakterizovat jako poèet pixelù hranice oblasti. V pøípadì potøeby pøesného mìøení se ale objevuje chyba za pøedpokladu ètvercových pixelù, které nejsou rozlo
eny vodorovnì nebo svisle. Tím je také délka hranice závislá na orientaci objektu. V pøípadì potøeby pøesného mìøení musíme pro dvojice pixelù pou
ít Pythagorovu vzdálenost. Perim = å

( xi - xi - 1) 2 + ( yi - yi - 1) 2

i

(8.2)

kde xi, yi jsou souøadnice i-tého pixelu.

8.2 Popis tvaru Máme k dispozici nìkolik adjektiv, která charakterizují tvary objektù (kostrbatý, hladký, podlouhlý, úzký, atd). Nalezení numerických popisù tvaru slo
itìjších objektù je obtí
né, proto
e vztah mezi nimi a naší ka
dodenní zkušeností není dostateènì tìsný. Nejstarší formy popisu tvaru objektù jsou jednoduché kombinace parametrù základních dimenzí (prùmìr, plocha, délka hranice) takovým zpùsobem,
e se dimenze pokud mo
no aritmeticky “krátí”. Napøíklad parametr prodlou
ení - elongation nám charakterizuje pomìr šíøka /délka a celková zmìna velikosti objektu nemá na tento parametr vliv. Parametry popisující tvar objektu vycházejí buï ze znalosti jeho hranice, nebo ze znalosti oblasti (plochy). Parametry vycházející z hranice mohou být délka a pøímost (køivost). Parametry popisu vycházející ze znalosti oblasti jsou velikost, podlouhlost, smìr, kompaktnost, konvexnost. Pro slo
itìjší oblasti tyto popisy selhávají a je potøeba pou
ít dekomposici na jednodušší èásti, napøíklad ztenèení oblasti na skelet a popis pomocí grafù. Hranice mù
e být, kromì základní obrazové reprezentace, popsána øetìzovým kódem. Co jsou to øetìzové kódy? Je to reprezentace hranice pomocí posloupnosti smìrù úseèek daných polohou hranièních pixelù. Kdy
potøebujeme z øetìzového kódu získat nìjakou informaci, musíme ho systematicky procházet a analyzovat tvar hranice v úseku, který nás zajímá. Na obr. 8.2 je nakresleno schéma 8-smìrového øetìzového kódu a pøíklad hranice popsané tímto kódem. V následujícím pøehledu jsou uvedeny nìkteré parametry, které charakterizují tvary objektù s pou
itím znalosti hranice i oblasti [5].

P oè.bod

2 1

3

4

0 7

5 6

K ód 076666553321212

Obr. 8.2 Pøíklad osmismìrového øetìzového kódu

90

Prodlou
ení (elongation) E=

MaxDiameter MinDiameter

(8.3)

4p × plocha perimetr 2

(8.4)

Faktor tvaru (Formfactor) FF =

Napøíklad pro kru
nici je FF = 1. Èím více se tvar od kru
nice liší, tím hodnota FF klesá. Na obr.8.3 jsou pøíklady objektù s rùznými hodnotami prodlou
ení a faktoru tvaru.

Tvar E FF --------------------------------------A 1.34 0.257 B 2.1 0.256 C 1.29 0.46 D 2,02 0.46

Obr.8.3 Objekty s rùznými parametry prodlou
ení a kompaktnosti

Kruhovost (Roundness) ROUND =

4 × Plocha p × MaxDiameter 2

(8.5)

Konvexnost (Convexity) CONV =

Convex Perimeter Perimeter

(8.6)

Na obr.8.4 jsou zobrazeny objekty s rùznými hodnotami kruhovosti a konvexnosti. Tvar

ROUND

CONV

-------------------------------A B C D

0,578 0,584 0,447 0,589

Obr.8.4 Objekty s rùznými parametry kruhovosti a komnvexnosti

91

0,351 0,483 0,349 0,497

Pokrytí objektu (Coverage) Tento parametr charakterizuje kvalitu krytí pozadí z hlediska nehomogenity obrazových struktur. Na obr.8.5 jsou definovány dimenze pro výpoèet plošného krytí objektu. Parametr s je velikost hranice, x je celková plocha uvnitø hranice, y je plocha nepokrytých pixelù objektu.

Obr.8.5 Dimenze charakterizující pokrytí objektu Základní parametr pokrytí C=

x- y ×100 [%] x

(8.7)

kde x je celková plocha objektu, y je poèet nepokrytých pixelù. Parametry deformace objektu Parametry charakterizují zkreslení z hlediska zkreslení tvaru objektu i nehomogenity krytí. V tomto pøípadì je mo
né definovat následující parametry deformace [9] na základì znalosti dimenzí z obr. 8.5. Deformace S1 - zkreslení z hranice x+ y æ sref ö S 1 = ç1 ÷ ×100 , sref = 2p × s ø p è

(8.8)

Pro rostoucí zkreslení S1 roste od 0 do 100 %. Deformace S2 - zkreslení z plochy S2 =

Aref , x+ y

æ a+ bö Aref = pç ÷ è 4 ø

2

(8.9)

Pro rostoucí zkreslení S2 roste od hodnoty 1 nahoru. Modifikace Deformace S2 S 2m = 1 -

x+ y Aref

(8.10)

Potom je parametr S2m pro mimimální a maximální zkreslení v rozmezí 0-1. Na obr. 8.6 jsou zobrazeny rùznì zkreslené tiskové body a hodnoty jejich zkreslení.

92

Obr.8.6 Hodnoty parametrù zkreslení tiskových bodù

Fraktální dimenze V moderních systémech analýzy obrazu se pou
ívají parametry zalo
ené na popisu fraktálových objektù. Jedná se o objekty s neurèitým tvarem (koruny stromù ve vìtru, oblaka atd.) a velkou èlenitostí. Podstatou fraktální analýzy je urèení èlenitosti fraktálového objektu. To je vyu
itelné v oblasti tisku napøíklad pro mìøení kvality pokrytí tiskových bodù nebo jejich tvarových zkreslení. K urèení èlenitosti objektu (nehomogenity) v obraze se pou
ívají parametry fraktální míry a fraktální dimenze. Tyto je mo
né získat mìøením závislosti délky hranice objektù s v obraze na velikosti mìøítka e, které pou
ijeme k mìøení [5,7]. Pro tuto závislost platí vztah (pro 2D obrazy) s = K × e 2- D

(8.11)

kde K je fraktální míra a D je fraktální dimenze. Parametr fraktální dimenze D se mù
e mìnit v rozmezí <1,2> podle èlenitosti objektu. Èím více se parametr D blí
í k hodnotì 2, tím je objekt èlenitìjší. Prakticky se délka hranice mù
e vypoèítat nìkolika zpùsoby. Jedna z metod je zalo
ena na pokládání ètvercové sítì s promìnlivou hustotou (velikost mìøítka e) na segmentovaný obraz (obr.8.7). Sí nám vymezí èistì bílé ètverce, èistì èerné ètverce a ètverce s bílými i èernými pixely. Délka hranice je potom souètem ètvercù, které obsahují pouze èernobílé pixely. Postup mù
e být následující: urèujeme poèty bílých (NW), èerných (NB) a èernobílých (NBW) ètvercù pro postupnì se zmenšující velikosti ètverce e = 1/r (r =1, 2, 3, 4, ...) je parametr velikosti sítì pro1´1, 2´2, 3´3, 4´4, …poèty ètvercù sítì). Kdy
vyneseme závislost pøirozeného logaritmu poètu NBW na funkci lne (obr. 8.7), získáme v ideálním pøípadì pøímkovou závislost, její
smìrnice je hodnota fraktální dimenze D a úsek na ose y je úmìrný fraktální míøe K.

93

Obr.8.7 Urèování fraktální dimenze

8.3 Urèování polohy a orientace V nìkterých aplikacích analýzy obrazu je nutné mìøit polohu objektu v obraze. U objektù nepravidelného tvaru mù
eme jeho polohu definovat více zpùsoby. Je to obvykle poloha støedního bodu objektu, jeho
souøadnice mohou být urèeny napø. v polovinì mezi maximální a minimální souøadnicí pixelù vytváøejících objekt. xp =

x max + x min , 2

y max + y min 2

yp =

(8.12)

Støední bod získaný z maximální a minimální souøadnice objektu mù
e polohu objektu výraznì zkreslit nìkolika pixely. Proto existují definice, které berou do úvahy všechny pixely a také tvar objektu. Je to v podstatì urèení souøadnic tì
ištì objektu (obr.8.8). Souøadnice tì
ištì

åx

i

Cx =

i

Area

åy

i

Cy =

i

Area

(8.13)

kde xi a yi jsou souøadnice i-tého pixelu a Area je celkový poèet pixelù v objektu.

Obr. 8.8 Tì
ištì poèítané ze všech pixelù (nahoøe) a z hranièních pixelù (dole)

94

Jiný zpùsob výpoètu tì
ištì spoèívá v pou
ití pouze hranièních pixelù objektu (obr.8.8 dolní). Výsledek mù
e být výraznì zkreslený oproti pøedchozímu postupu, proto
e nastal posuv do smìru, kde je tvar èlenitìjší a tedy je tam více hranièních pixelù. S polohou objektu úzce souvisí také parametr orientace podlouhlých objektù. Existuje více parametrù, které charakterizují tuto vlastnost (napø. orientace osy vìtšího prùmìru). Pro výpoèet orientace se podobnì jako u parameru tì
ištì vyu
ívá všech pixelù objektu. Na základì toho pøístupu mù
e být orientace popsána jako úhel osy objektu, její
poloha vykazuje minimální souèet ètvercù individuálních odchylek pixelù objektu. Vhodná procedura je popsána následujícími rovnicemi [5]:

Sumy souøadnic pixelù Sx = å xi , Sy = å yi , Sxx = å x i2 , Syy = å y i2 , Sxy = å xi × yi i

i

i

i

(8.14)

i

Momenty Mxx = Sxx -

S y2 S x2 S x × Sy , Myy = Syy , Mxy = Sxy Area Area Area

(8.15)

Úhel osy orientace é Mxx - Myy + Q = arctg ê ê ë

( Mxx - Myy ) 2 + 4 × M xy2 ùú 2 × Mxy

ú û

(8.16)

8.4 Mìøení jasových hodnot v obrazech V digitálních obrazech, které prakticky zpracováváme, je ka
dý pixel charakterizován hodnotou, která je úmìrná jasu odpovídajícího bodu v originální scénì. V pøípadì barevného obrazu je to trojice hodnot, odpovídající spektrálním slo
kám r, g, b. Digitální rozsahy hodnot jasu jsou rùzné a závisejí na snímacím zaøízení (kamera, skener). Nejèastìji pou
ívaný rozsah je 8 bitù (0-255), ale i 12 a 16 bitù, napøíklad u moderních skenerù. Potom hodnota 0 u rozsahu 8 bitù na jednu slo
ku odpovídá èerným pixelùm, hodnota 255 bílým pixelùm, ostatní hodnoty odpovídají rùzným úrovním šedi. Pøi snímání obrazu v podstatì mìøíme mno
ství odra
eného svìtla od motivù pøedlohy. Dùle
itý je vztah mezi úrovnìmi hodnot intenzity odra
eného svìtla z jednotlivých bodù v obraze a výstupními numerickými hodnotami výstupní velièiny v uvedených rozsazích. Tento vztah, který vìtšinou není pøesnì lineární, je definován kalibraèními funkcemi ve formì tabulek nebo køivek. Kalibraèní funkce definují poèátek a konec stupnice a její prùbìh. U kamery nebo digitálního fotoaparátu se pøedpokládá linearní stupnice a kalibrace poèátku a konce jasové stupnice se získají snímáním èerného a bílého normálu. Kalibraèní funkci je potøeba pro ka
dé zaøízení vytvoøit a pøed ka
dým mìøením kalibraci kontrolovat, pøípadnì nastavovat. Nemusí to být jednoduchá úloha pøedevším v pøípadì, kdy
mìøící zaøízení (denzitometr, kamera, skener) má nìjaké automatické funkce (automatické nastavení citli-

95

vosti, gamma korekce), které není mo
né vyøadit. V dalším budeme pøedpokládat mìøení jasových hodnot pomocí denzitometru. Prakticky se kalibrace denzitometrických zaøízení provádí pomocí standardù, napøíklad denzitních klínù s definovanými úrovnìmi šedi, které jsou souèástí mìøených vzorkù (obr.8.9). Potom se kalibrace mìøicího pøístroje mù
e provádìt pøímo pro ka
dý mìøený vzorek.

Obr.8.9 Denzitní klín pro kalibraci mìøení jasu Denzitometr se kalibruje nastavením denzit políèek klínu na známé hodnoty (napøíklad jas pixelù 255 denzitì 0, jas pixelù 0 denzitì 2, další hodnoty jsou mezi). Tím získáme kalibraèní stupnici. Tato stupnice se pou
ívá k pøepoètu namìøených hodnot jasu pixelù objektù na hodnoty denzit pøi mìøení jednotlivých objektù ve vzorku (obr.8.10). V jiných pøípadech se pou
ívají samostatné kalibraèní vzorky (klíny, barevné obrazce). Potom je potøeba provádìt v urèitých intervalech periodickou kalibraci pøístroje. Statistická mìøení hodnot jasu Mìøení jasu lze provádìt pro jednotlivé pixely, ale také pro definované okolí pixelu w ´ w . Potom lze pou
ít parametry výbìrového prùmìru a výbìrového rozptylu jasu pixelù obrazové funkce v tomto okolí. Jk , l =

1 w2

w

w

å å F( k + m, l + n) m =1 n =1

Obr.8.10 Kalibraèní stupnice

96

(8.17)

1 w w × [F( k + m, l + n) - Jk , l ] 2 2 åå w m=1 n=1

s 2k,l =

(8.18)

Po segmentaci šedotónových (nebo barevných) objektù v obraze je mo
né mìøit rovnomìrnost rozlo
ení jasu pixelù v ploše objektu pomocí statistických parametrù výbìrového prùmìru a výbìrového rozptylu a tím kvalitu pokrytí objektu barvou. J=

1 N

åJ

i,

s 2J =

i

2 1 × å ( Ji - J ) N -1 i

(8.19)

kde Ji je jas i-tého pixelu, J je støední hodnota jasu všech N pixelù objektu a sJ2 rozptyl jasù pixelù segmentovaného objektu. Pro mìøení statistických parametrù v obraze je mo
né také vyu
ít vypoèítaných hodnot histogramu jasu digitalizovaného obrazu, který je odhadem pravdìpodobnostního rozdìlení jednorozmìrné náhodné velièiny. p( J ) »

N (J ) M

(8.20)

kde J je kvantovaná úroveò jasu pixelù napøíklad v rozmezí 0 £ J £ 255, N(J) poèet pixelù jasu J a M celkový poèet pixelù v definovaném okolí. Tvar histogramu potom poskytuje vodítka k charakterizování vlastností obrazu. Napøíklad “úzký” histogram ukazuje na málo kontrastní obraz. Byly zformulovány následující parametry charakterizující tvar histogramu jasu. Prùmìr (Mean) L -1

SM º J = å J p( J )

(8.21)

J =0

Stadardní odchylka (Deviation) é L -1 ù SD º sJ = êå ( J - J ) 2 p( J )ú ëJ = 0 û

12

(8.22)

Šikmost (Skewness) SS =

1 s 3J

L -1

å(J - J )

3

p( J )

(8.23)

J =0

Energie (Energy) L -1

SEN = å [ p( J )] 2

(8.24)

J =0

Entropie (Entropy) L -1

SE = -å p( J ) log 2[ p( J )] J =0

97

(8.25)

Mìøení jasových parametrù v barevných obrazech U barevných objektù v obraze mù
eme vyhodnocovat výše uvedené parametry pro jednotlivé barevné slo
ky r, g, b. K mìøení se pou
ívají spektrátní fotometry, skenery a digitální barevné kamery a fotoaparáty. Pøi výpoètech pou
íváme rùzné barvové prostory podle toho, jaký parametr vyhodnocujeme. Pøi mìøení získáváme obvykle jasové slo
ky r, g, b nebo slo
ky X, Z, Y a z nich v pøípadì potøeby provádíme pøevody do vhodných barvových prostorù (napø. HSB, YUV, L*a*b* atd.). Na základì namìøených a vypoèítaných velièin, které charakterizují barevnost objektù v obraze, mù
eme vyhodnocovat také barevné rozdíly oproti referenèním hodnotám. Referenèní hodnoty získáme mìøením na barevných normálech nebo na smluvních výtiscích. V pøípadì relativních mìøení barevných parametrù je mo
né barevné rozdíly mìøit v libovolném barvovém prostoru. Pro RGB barvový prostor je barevná odchylka DRGB = ( r - rr ) 2 + ( g - g r ) 2 + ( b - br ) 2

(8.26)

kde r, g, b jsou hodnoty aktuální barvy, rr, gr, br jsou hodnoty referenèní barvy. V L*a*b* barvovém prostoru je barevná odchylka DE = ( L - Lr ) 2 + ( a - ar ) 2 + ( b - br ) 2

(8.27)

kde L, a, b jsou hodnoty aktuální barvy, Lr, ar, br jsou hodnoty referenèní barvy. Mù
eme mìøit také barevné rozdíly pouze jedné nebo dvou slo
ek, napøíklad DHS (Hue, Saturation). Hodnoty barevných rozdílù pou
íváme napøíklad pro zajišování stálosti barevnosti rùzných výrobkù pøi výrobì (v textilním prùmyslu, v tiskovém prùmyslu atd.).

8.5 Klasifikace objektù v obrazech Na závìr této kapitoly se budeme zabývat struènì metodami klasifikace objektù, co
je první úroveò vyššího zpracování obrazu. Tato úroveò zpracování umo
òuje automatické tøídìní objektù do skupin se spoleènými rysy, které nazýváme tøídy. Jakmile máme v obraze po segmentaci vyèlenìny objekty, provádíme výpoèty pøíznakù (napø. tvar, rozmìr, barva) jednotlivých obrazových objektù, jak bylo popsáno v pøedchozích kapitolách. Vektory pøíznakù jednotlivých objektù mohou být pou
ity jako vstupy pro klasifikátory, pomocí kterých provádíme klasifikaci tìchto objektù do tøíd. Rozeznáváme dvì skupiny klasifikátorù - pøíznakové klasifikátory a syntaktické klasifikátory. Dále bude struènì popsán princip pøíznakové klasifikace. Pøíznaková klasifikace obrazových objektù Pøi klasifikaci R tøíd obrazových objektù, odpovídají jednotlivým tøídám oblasti shlukù objektù, které lze od sebe oddìlit vhodnou plochou, kterou nazýváme rozdìlující nadplocha (obr.8.11 pro R=3). Objekty tøídy i jsou potom klasifikovány vektorem pøíznakù xi. Existuje-li u urèitého obrazu taková rozdìlující nadplocha,
e v ka
dé oblasti Ki le
í obrazové objekty jen tøídy i, jedná se o separabilní mno
iny objektù. Pøevá
ná èást praktických úloh však

98

Obr. 8.11 Rozdìlující nadplochy tøíd objektù objektového prostoru nemá separabilní obrazové objekty. Oblasti Ki nelze v
dy vymezit tak, aby v ka
dé z nich byly jen obrazové objekty stejné tøídy. Proto je èást objektù klasifikována chybnì. Pøíznakový klasifikátor si mù
eme pøedstavit jako stroj s n vstupy a jedním výstupem. Na ka
dý vstup se pøivádí jeden z n pøíznakù pøíznakového vektoru x = (x1, x2, ......xn), které jsou namìøeny na klasifikovném objektu. Tento vektor x popisuje obrazové objekty jedné tøídy (pøíznaky mohou být napø. barevný odstín, tvar, velikost atd.). Pøi vhodné volbì vektoru pøíznakù je podobnost objektù v ka
dé jednotlivé tøídì vyjádøena jejich geometrickou a jasovou blízkostí. Pøi klasifikaci do R tøíd se na výstupu klasifikátoru pro ka
dou tøídu generuje jeden indikátor wi z mno
iny w = (w1, w2, .... wR), který odpovídá pøíznakovému vektoru xi. Funkce wi = d(xi) je tzv. rozhodovací pravidlo, které popisuje vztah mezi vstupy x a výstupem klasifikátoru pro tídu i. Rozhodovací pravidlo rozdìluje prostor obrazových objektù na R oddìlených podmno
in K1,…,KR tak,
e podmno
ina Ki obsahuje všechny obrazové objekty xi pro které platí wi = d(xi). Pøíklad: robot na sbìr rajèat. Robot musí umìt rozlišit 5 typù objektù: listy, stonky, zralá rajèata, nezralá rajèata a pùdu. Klasifikátory jednotlivých typù objektù budou obsahovat pøíznaky tvaru a barvy: • rajèe zralé: barva èevená - parametr HUE, tvar parametrem konvexnosti CONV • rajèe nezralé: barva zelená a
bílá - HUE, SATURATION, tvar CONV • listy: barva zelená - HUE, tvar CONV • stonek: barva zelená - HUE, tvar ELONG • pùda: barva šedá nebo hnìdá - parametry SATURATION, LIGHTNESS Tedy pro zralé rajèe bude mít pøíznakový vektor 2 pøíznaky - HUE a CONV. Rozhodovací pravidlo pro zralé rajèe by mohlo být w1 = 360>HUE>300 | | 00.8.

99

Diskriminaèní funkce Rozhodovací pravidlo je vlastnì toto
né s urèením rozdìlujících nadploch z obr.8.13. Rozdìlující nadplochy mù
eme urèit také pomocí tzv. diskriminaèních funkcí g1(x), …gR(x) . Jsou to skalární funkce pro které pro všechna x Î Kr a libovolné s Î [1, R], s ¹ r platí nerovnost gr ( x) ³ gs( x)

(8.28)

kde r a s oznaèují r-tou a s-tou tøídu objektù. Rovnice rozdìlující nadplochy mezi mno
inami Kr , Ks je potom gr ( x) - gs( x) = 0

(8.29)

Rozhodovací pravidlo, realizované takovou diskriminaèní funkcí je potom: Objekt x je klasifikován do tøídy wr , kdy
je diskriminaèní funkce pro toto x maximální pro všechny mo
né hodnoty s. d( x) = wr Û gr ( x) = MAX gs( x) s =1 ,... R

(8.30)

Výhodou pou
ívání skalární diskriminaèní funkce je,
e výpoèty podle rovnice 8.30 jsou jednodušší, ne
v pøípadì aplikace rozhodovacího pravidla w = d(x), kdy musíme provádìt rozhodovací proces u všech promìnných pøíznakového vektoru x. Klasifikátor, jeho
všechny diskriminaèní funkce jsou lineární se nazývá lineární klasifikátor. Obecný tvar lineární diskriminaèní funkce je potom gr ( x) = gr 0 + gr 1 x1 + KK+ grnxn

(8.31)

kde gr0, gr1, ...... grn jsou konstanty. Etalonový pøíznakový klasifikátor Jiný zpùsob konstrukce klasifikátoru je zalo
en na minimální vzdálenosti od etalonu. Je to v podstatì speciální pøípad diskriminaèního klasifikátoru, který má v nìkterých aplikacích svoje pøednosti. Pøedpokládejme,
e v obrazovém prostoru máme R vzorových bodù v1, v2, .... vR, které se nazývají etalony tøíd w1, w2, ....wR. Klasifikátor zaøadí klasifikovaný objekt s pøíznakovým vektorem x do tøídy, její
etalon má od objektu x nejmenší vzdálenost. Pøítomnost ke tøídì wi je urèena vztahem d( x) = wi Û | vr - x| = MIN | vs - x|

(8.32)

s =1 ,... R

Nastavení klasifikátoru Nastavení klasifikátoru se týká optimálního nastavení rozhodovacího pravidla. Pro nìkterý z pøedmìtù, který vektor pøíznakù x klasifikuje, mù
e být rozhodnutí o zaøazení nebo nezaøazení do jeho tøídy nesprávné, tedy generuje chybu klasifikace. Pøedpokládejme,
e v klasifikátoru mù
eme nastavovat soubor více rozhodovacích pravidel pro konkrétní pøíznakový vektor x a hledáme optimální rozhodovací pravidlo. Oznaème q vektor ukazatelù na konkrétní rozhodovací pravidlo.

100

Z hlediska optimálního nastavení rozhodovacího pravidla vyhodnocujeme chybná rozhodnutí pro jednotlivá rozhodovací pravidla ve formì støední hodnoty ztráty J(q), která je závislá na zvoleném rozhodovacím pravidle w = d(x,q). Pokud oznaèíme q* jako ukazatel na optimální rohodovací pravidlo, je støední ztráta oznaèená J(q*) minimální pro rozhodovací pravidlo w = d(x,q*) a platí J ( q* ) = MIN J ( q ) q

(8.33)

Rozhodovací pravidlo w = d(x,q*) je potom optimální rozhodovací pravidlo a q* je optimální ukazatel. V praxi jsou obvykle zadány po
adavky na pøesnost klasifikace a tzv. trénovací mno
ina objektù, které jsou správnì zaøazeny do testované tøídy. Tato trénovací mno
ina je v
dy koneèná. Informaci získanou z trénovací mno
iny, co
je optimální rozhodovací pravidlo w = d(x,q*), pak zobecníme na celý obrazový prostor. Jinými slovy, nastavení klasifikátoru bude pøibli
nì optimální i pro další objekty, které nepatøí do trénovací mno
iny. Pøesnost nastavení klasifikátoru a velikost trénovací mno
iny jsou v pøímé úmìrnosti. Teprve po vyzkoušení trénovací mno
iny konstruktér zjišuje, zda je tato mno
ina pro po
adovanou pøesnost dostateènì velká, èi nikoliv. Musíme tedy pøipustit dodateèné opakované rozšiøování trénovací mno
iny a další optimalizaci rozhodovacího pravidla w = d(x,q*). Tento proces optimalizace systému zalo
ený na postupném rozšiøování trénovací mno
iny se nazývá uèení. Uèení je prostøedkem k samoèinnému optimálnímu nastavení systému prostøednictvím ukázkových pøíkladù. Cílem uèení by mìla být optimalizace zobecnìním urèitého mno
ství ukázkových pøíkladù a nikoliv pøedlo
ením všech mo
ných pøíkladù. Øešení ka
dé úlohy klasifikace je ale v
dy kompromisem mezi velikostí tolerované chyby na jedné stranì a slo
itostí realizace a její èasové nároènosti.

101

Seznam literatury [1] Petrou M., Bosdogianni P.: Image Processing - The Fundamentals. John Willey & Sons, Chichester 2000. [2] Pratt W. K.: Digital Image Processing. John Willey & Sons, New York 2001. [3] Sonka M., Hlavac V., Boyle R.: Image Processing, Analysis and Machine Vision. Chapman & Hall, London 1995. [4] Klíma M., Bernais M., Hozman J., Dvoøák P.: Zpracování obrazové informace. Skriptum ÈVUT, Praha 1996. [5] Russ J.C.: The Image Processing Handbook. CRC Press, North Carolina State University 1999. [6] Hlaváè V., Šonka M.: Poèítaèové vidìní. Grada, Praha 1992. [7] Zmeškal O., Julínek M., B
atek T.: Fraktální analýza povrchu potiskovaných materiálù a potištìných ploch. VI. polygrafický semináø, Pardubice 2003. [8] Sangwine S.J., Horne R.E.N.: The Colour Image Processing Handbook. Chapmann & Hall, London 1998. [9] Salerma H., Oittinen P.: Definition and Measurement of Print Quality. Teknillinen Korkeakoulu, Graafisen Tekniikan Laboratorio, Otaniemi 1991. [10] Sochor J., ára J., Beneš B.: Algoritmy poèítaèové grafiky. Skriptum ÈVUT, Praha 1998. [11] Kohler R.A.: Segmentation System Based on Thresholding. Computer Graphics and Image Processing 15 (1981), 319-338. [12] Skala V.: Algoritmy poèítaèové grafiky I, II, III. Skripta ZÈU, Plzeò 1992.

103

Obsah 1. Maticové operace, program Mathematica . . . . . . . . . . . . . . . . 3 2. Úvod do zpracování obrazu . . . . . . . . . . . . . . . . . . . . . . . 11 3. Integrální transformace . . . . . . . . . . . . . . . . . . . . . . . . . 23 4. Statistický popis obrazu . . . . . . . . . . . . . . . . . . . . . . . . . 43 5. Zlepšování kvality obrazu . . . . . . . . . . . . . . . . . . . . . . . . 57 6. Rekonstrukce obrazu . . . . . . . . . . . . . . . . . . . . . . . . . . 69 7. Segmentace objektù v obraze . . . . . . . . . . . . . . . . . . . . . . 75 8. Mìøení vlastností objektù v obraze . . . . . . . . . . . . . . . . . . . 89

104