KÉPFELDOLGOZÁS JEGYZET SZILÁGYI LÁSZLÓ

KÉPFELDOLGOZÁS JEGYZET SZILÁGYI LÁSZLÓ

2008

1. Bevezetés 1.1. Alapfogalmak A kép egy minimum kétdimenziós információhordozó. Egy digitális kép képpontokból áll, minden egyes képpont a többitől független, saját információt tartalmaz. Pl. kétdimenziós a fénykép, térben háromdimenziós a mágneses rezonanciás képalkotó rendszerrel készített metszetsorozat (sok párhuzamos metszet segítségével el lehet érni a 3D élményét), szintén háromdimenziós a videofelvétel, de ott az egyik dimenzió az idő. Az egyszerűség kedvéért az emberek többnyire mátrixos elhelyezésű 2D képeket használnak, melyben a képpontok sorokba és oszlopokba vannak rendezve, a sorok közti távolság konstans, az oszlopok közti távolság szintén konstans, valamint a sor- és oszloptávolság a legtöbb esetben egyenlő. Logikailag még a hexagon rács lenne egy értelmes megoldás, de nehéz lenne vele dolgozni. Függvényként a következőképpen írhatjuk le a képek különböző típusait: 1. analóg kép: f : X → R , ahol X ⊆ R × R 2. féldigitális kép (értelmezési tartomány digitális, értéktartomány analóg): f : X → R , ahol X ⊆ Z × Z 3. digitális kép: f : X → {0,1,2,..., m − 1} , ahol X ⊆ Z × Z A 2D képek a gyakorlatban általában téglalap alakúak, melyet egy hosszúság és egy szélesség jellemez. Elvileg ennek nem feltétlenül kell így lennie, egy kép nem kötelezően téglalap alakú (analóg ellenpélda a háromszögű bélyeg). Ennek a struktúrának a leírására találták ki a határolt mátrix (angolul bound matrix) fogalmát, amely mátrixba foglalja a kép értelmezett képpontjait, de ez a mátrix tartalmazhat egy speciális, csillaggal jelölt („ ∗ ”) elemet, ami azt jelenti, hogy az illető képpont értéke nem értelmezett. Ezen kívül a határolt mátrixnak van egy origója, melynek pozícióját vagy az illető érték bekarikázásával, vagy pedig a bal felső elem koordinátáinak megadásával jellemezzük. Pl.

1  3 f1 =  3  4 

1  3 f3 =  3  4 

2 ∗ 5 5

2 3 5 1   3 ∗ 4 5 és f 2 =   3 5 4 6   4 5 ∗ 7  −1,−2 

3 4 4 ∗

5 1   5 3 és f 4 =   6 3   4 7  −1, −3 

2 ∗ (5) 5

2 3 5  ∗ 4 5 ugyanazt a képet jelölik, egyenlő képek. (5) 4 6  5 ∗ 7  3 4 4 ∗

5  5 nem egyenlő képek, mert nem azonos az origójuk. 6  7 

1.2. Digitális képek a számítógépben A képeket a számítógép egyértelműen téglalap formátumban kezeli. A számítógép által használt képek főbb jellemzői: Méretei: szélesség [képpont], és hosszúság [képpont] Egy képpont információja lehet: - bináris (fekete vagy fehér, 1-es vagy 0-s, igaz vagy hamis) 2

- intenzitás érték vagy szürke árnyalat (16, 256, vagy egyéb számú fokozat van a fekete és fehér között) Egy kép lehet egy vagy több csatornás. Az egycsatornás képet intenzitás képnek is szokták nevezni, vagy szürke árnyalatokból álló képnek. Az emberi szemmel érzékelhető színeket három csatornával lehet leírni. A színes képernyő RGB kódolást használ (Red-GreenBlue), míg a színes nyomtató CMYK (Cyan-Magenta-Yellow-blacK) színeiből állítja elő bármelyik színt vagy árnyalatot. Képek feldolgozásakor az a lényeg, hogy a számítógép könnyedén és gyorsan hozzáférjen bármelyik képpont információtartalmához. Ezért van az, hogy amikor a gép „betölt” egy képet a memóriájába, akkor egy könnyen bejárható kétdimenziós tömbbe írja az adatokat. Az egy csatornán belüli intenzitást ilyenkor vagy egy egész szám jelöli (pl. 0..255), vagy pedig egy [0,1] intervallumban elhelyezkedő valós szám írja le. Amikor a képeket a számítógép eltárolja, kimenti egy fájlba, akkor nem az a fontos, hogy bármelyik képpont információtartalma gyorsan elérhető legyen, hanem a fájl méretét célszerű minimalizálni. Ennek következtében fejlesztettek ki és alkalmaznak rengeteg fájlformátumot. Ezek főbb jellemzői: - tömörít-e vagy sem? A nem tömörítő fájlformátumok sorra tartalmazzák minden egyes képpont információját. A mentés (save) vagy betöltés (load) műveletek ez esetben gyorsak. A tömörített képformátumok kimentéskor egy tömörítő algoritmus segítségével kisebb méretűvé alakítják a teljes kép információanyagát. Betöltéskor inverz művelet történik, a kicsomagolás. A tömörítés előnye a szükséges tárolókapacitás csökkenése, hátránya (1) a lelassított mentés és betöltés és (2) az a tény, hogy nem tudjuk megállapítani, hogy egy bizonyos képpont információja a fájl hányadik bájtjában helyezkedik el. - ha tömörít, akkor bitvesztésesen-e vagy sem? A bitvesztéses algoritmus tömörítéskor mintát vesz a képpontok értékeiből egy bizonyos sűrűséggel, és ezeket a mintákat tömöríti be, míg kicsomagoláskor a minták értékei szerint interpolációval kapja meg minden egyes képpont színét. A minőség rovására csökkenti a fájl méretét. Fontosabb képformátumok: 1. BMP, azaz bitmap, nem tömörít, nagy fájlméret, rendezett információ. 2. PCX, egyszerű tömörítés1, nincs bitvesztés 3. JPG, tömörít bitvesztéssel. Diszkrét koszinusz transzformációt és Huffmann kódolást használ 2 . A tömörítésnek több verziója van. Digitális fényképezőgépek gyors kódolást alkalmaznak, melynek hátránya a nagyobb fájlméret, míg a számítógép szoftverei a méret szerint optimalizálnak. 4. GIF, tömörít, bitvesztéssel. Egy vagy több azonos méretű képet tárol, amit bizonyos programok3 rövidfilmként meg tudják jeleníteni. 5. PNG és társai, tömörítnek bitvesztés nélkül 1.3. A számítógépes képfeldolgozás lépései 1. Képalkotás. Mindazon műveletek összessége, amíg a kép eljut a számítógép memóriájába vagy valamely háttértárolójába. Pl. - digitális fényképezőgéppel készítünk egy képet és letöltjük számítógépünkbe 1

Az egymás melletti azonos színű képpontokat tudja tömöríteni, emiatt hatékony a rajzfilmek tömörítésekor. ifj. Dávid László véleménye szerint 3 pl. Internet Explorer vagy egyéb web böngészők 2

3

- egy analóg fényképet szkenner segítségével digitalizálunk - ipari kamerával felvételt készítünk egy raktárhelységről a patkányok szaladási átlagsebességének mérése céljából - mágneses rezonanciás technológiával a radiológus orvos metszet felvételeket készít egy páciens valamely szervéről, majd ezeket JPG formátumban CD lemezre írja 2. Előfeldolgozás. Ennek célja az, hogy a kép minőségét feljavítsuk (pl. szűrés, élesség javítása, stb.), valamint a további feldolgozás céljának megfelelő formájúvá alakítsuk (pl. nagyítás, kicsinyítés) 3. Szegmentálás. A kép felbontása alkotó részeire. 4. Identifikálás. A képen található objektumok felismerése. 5. Utófeldolgozás. A felismert objektumokból további következtetések levonása. Pl. - az identifikált patkányok haladási sebességének meghatározása - diagnózis készítése az MRI felvételekből azonosított objektumok alapján. 1.4. Határolt mátrix (bound matrix) Minden kép képpontokból áll. Ahhoz, hogy a képet könnyen le lehessen írni egy matematikai modellel, szükség van egy rendre a képpontok között. Ezért találták ki azt, hogy a képpontok egy egyenletes sűrűségű négyzetes rács rácspontjaiban helyezkedjenek el, amit egy mátrixszal egyértelműen le lehet írni. A mátrix formátum viszont feltételezi, hogy a képünk téglalap alakú. Ha általános leírásra törekszünk, ezt a megkötést fel kell oldanunk valahogy. Erre ad megoldást az úgynevezett határolt mátrix (bound matrix) fogalma. A határolt mátrix fogalmát a valós elemű mátrixból tudjuk származtatni, a következő tulajdonságok hozzáadásával: 1. A mátrix értékei (a képpontot leíró intenzitásértékek) az R ∪ {∗} halmaz elemei, ahol R a valós számok halmaza, a ∗ pedig azt jelenti, hogy az illető képpont intenzitásértéke határozatlan (nem ismert vagy nem érdekes). Úgy is felfoghatjuk, hogy az illető képpont nem része a képnek. Például egy 100 képpontnyi átmérőjű kör alakú képet egy 100*100-as határolt mátrix fog leírni, melynek a sarkaiban ∗ értékek vannak. 2. A határolt mátrixnak van egy origója. Ennek jelölésére két mód van: a. az illető képpont intenzitásértékének bekarikázásával b. a mátrixnak írhatunk bal alsó indexbe egy vesszővel elválasztva két koordináta értéket. Ezek a mátrix jobb felső elemének a koordinátái. Függvény formában a határolt mátrix így írható fel: f : Z × Z → R ∪ {∗} Definíció szerint a határolt mátrix a következőképpen néz ki:  a00   a10 f = M  a  m−1, 0

a01 a11 M am−1,1

a0,n−1   a1,n−1  , ahol a p ,q ∈ R ∪ {∗} , O M   L am−1,n−1  r ,t L L

4

p = 0..m − 1 , q = 0..n − 1 , r , t ∈ Z f (r , t ) = a00 , f (i, j ) = at − j , r − i .

Két határolt mátrix egyenlő, ha az origóhoz viszonyított elhelyezkedés szerint az összes képpont-pár intenzitásértéke megegyezik. Pl.

1  3 f1 =  3  4 

2 3 5 1   ∗ 4 5 3 és f 2 =   5 4 6 3     5 ∗ 7  −1,2 4

2 ∗

(5) 5

3 5  4 5 4 6  ∗ 7 

ugyanazt a képet jelölik, egyenlő képek.

2. Egyszerűbb műveletek képekkel 2.1. Aritmetikai műveletek digitális képekkel Az egyszerűbb aritmetikai műveletek a következők: 1. összeadás, kivonás 2. szorzás, osztás 3. minimum- és maximumszámítás 4. skaláris értékkel való szorzás A legfontosabb dolog, amire vigyázni kell az aritmetikai műveleteknél, hogy hogyan feleltetjük meg egymásnak a két határolt mátrix elemeit. Kiindulópontnak használjuk az origót, s az ahhoz viszonyított pozíciót használjuk a megfeleltetéshez. Összeadás és kivonás Adott két kép, jelölje f és g ezek határolt mátrixát. Az összeadás függvényt ADD-el, a két kép összegét ADD(f,g)-el jelöljük. Az összeget definíció szerint a következőképpen számoljuk:  f (i, j ) + g (i, j ), ha f (i, j ) ≠ ∗ ∧ g (i, j ) ≠ ∗ ∗, ha f (i, j ) = ∗ ∨ g (i, j ) = ∗   ∗ 2 3    2 3 4 2    3 3  2 1 0  ADD(f,g)=  Pl. f =  1 2 0 2  és g =   2 ∗  −1, 0 ∗ 1 0   ∗ 0 1 2    −1,0   ∗ 1 ∗  − 2, −2

[ADD(f,g)](i,j)= 

A kivonás függvénynek nincs saját jele, az f és g képek különbségét az ADD(f,-g) kifejezéssel számíthatjuk ki. A –g értelmezését lásd a skaláris értékkel való szorzásnál.  f (i, j ) − g (i, j ), ha f (i, j ) ≠ ∗ ∧ g (i, j ) ≠ ∗ ∗, ha f (i, j ) = ∗ ∨ g (i, j ) = ∗   ∗ 2 3    2 3 4 2    1 3  2 1 0  ADD(f,-g)=  Pl. f =  1 2 0 2  és g =   ∗ 1 0 0 ∗  −1,0   ∗ 0 1 2    −1,0   ∗ 1 ∗  − 2, −2

[ADD(f,-g)](i,j)= 

5

A szorzás függvényt MUL-lal, a két kép szorzatát MUL(f,g)-vel jelöljük. A szorzatot definíció szerint a következőképpen számoljuk:  f (i, j ) ⋅ g (i, j ), ha ∗, ha 

f (i, j ) ≠ ∗ ∧ g (i, j ) ≠ ∗ f (i, j ) = ∗ ∨ g (i, j ) = ∗

[MUL(f,g)](i,j)=  Pl.

3 0 1   2 1 MUL  3 2 4  ,   ∗ 2   1 2 0  − 1 , − 1   3 (2) 8   3  =  =   2 2 ∗  2

 3 0 1     2 1 (1) 2   1 2   =   = MUL  3 (2) 4 ,  ∗ 2 1 ∗   1 ∗ − 2,0       1 2 0   2 8  2 ∗  −1, 0

A minimum-, illetve maximumszámítás függvényt MIN-nel, illetve MAX-szal jelöljük, és a következő definíció szerint számoljuk: min( f (i, j ), g (i, j )), ha ∗, ha  max( f (i, j ), g (i, j )), ha [MAX(f,g)](i,j)=  ∗, ha  2 2 3     2 3 4 2   4 1 0  Pl. f =  1 2 (0) 2  és g =  6 1 (0)   0 0 1 2     ∗ 1 ∗   

[MIN(f,g)](i,j)= 

f (i, j ) ≠ ∗ ∧ g (i, j ) ≠ ∗ f (i, j ) = ∗ ∨ g (i, j ) = ∗ f (i, j ) ≠ ∗ ∧ g (i, j ) ≠ ∗ f (i, j ) = ∗ ∨ g (i, j ) = ∗

2 1 0  4 3 4      MIN(f,g)=  1 1 (0)  , MAX(f,g)=  6 2 (0)  ∗ 0 ∗  ∗ 1 ∗     

A skaláris értékkel való szorzást SCALAR(t,f)-el jelöljük, ahol f a képet reprezentáló határolt mátrix, t pedig a skaláris szám. t ⋅ f (i, j ), ha  ∗, ha

f (i, j ) ≠ ∗ f (i, j ) = ∗

[SCALAR(f,t)](i,j)= 

A –1 értékű skalárissal való szorzást SUB-bal jelöljük. A kivonást ezek után így is felírhatjuk: ADD(f,-g)=ADD(f,SUB(g))=ADD(f,SCALAR(-1,g)) Pl. Egy lehetséges vizsgafeladat: adott bizonyos f, g és h határolt mátrix. Számítsuk ki a következő kifejezés értékét: ADD(SUB(f),MUL(MIN(f,h),SCALAR(2/5,MAX(h,g)))) 2.2. Geometriai műveletek digitális képekkel Az egyszerűbb geometriai műveletek a következők: 1. transzláció4 4

translation, horizontal translation, vertical translation

6

2. forgatás avagy rotáció5 3. tükrözés6 A transzláció a határolt mátrixok világában csak annyit jelent, hogy elmozdítjuk az origót. Jelölje f = (a pq ) r ,t egy f kép határolt mátrixát. Az f kép transzlációját (i,j) vektor szerinti irányba TRAN(f;i,j) fogja jelölni. Ezt a következőképpen számítjuk ki: TRAN(f;i,j)= (a pq ) r +i ,t + j [TRAN(f;i,j)](u,v)= f (u − i, v − j ) Ez utóbbi kifejezést ellenőrizni kell és el kell tudni magyarázni egy rajz kíséretében, ahogyan nekem második próbálkozásra sikerült is.  2 3 4 2  2 3 4 2     Pl. f =  1 2 0 2  , TRAN(f;1,1)=  1 2 0 2   0 0 1 2  0 0 1 2 − 2, −1  −1,0  

Az transzláció után az origó értéke: [TRAN(f;1,1)](0,0)=f(-1,-1)=3 Rotáció A forgatás vagy rotáció 90 fokos egységekben történik. Pozitív iránynak választjuk a trigonometriai irányú forgatást. A 90 fokos forgatás műveletet a NINETY függvénnyel érjük el. A forgatás mindig az origó körül történik, tehát a forgatás során az origó értéke nem változik.  2 3 4 2  2 3 4 2     Pl. f =  1 2 0 2  =  1 2 (0) 2     0 0 1 2 − 2, −1  0 0 1 2   2 2   4 (0) 90 fokos forgatás trigonometriai irányba: NINETY(f)=  3 2  2 1  További forgatások: 2 1 0  180 fok: NINETY2(f)=NINETY(NINETY(f))=  2 (0) 2 2 4 3 

2  1 0  0  0  1 2 

 0 1 2   0 2 3   270 fok: NINETY3(f)=  1 (0) 4     2 2 2   4 360 fok: NINETY (f)=f, teljes körbeforgatás során visszakapjuk az eredeti képet.

5 6

rotation, clockwise and counter-clockwise rotation flip, horizontal flip, vertical flip, directional flip

7

Tükrözés

A tükrözés mindig egy, az origón átmenő egyeneshez viszonyítva történik, melynek iránya lehet vízszintes (0 fok), függőleges (90 fok), főátló irányú (135 fok), illetve mellékátló irányú (45 fok). Jelöljük az f kép főátló irányú tükrözését FLIP(f)-el.  2 3 4 2  2 3 4 2     Pl. f =  1 2 0 2  =  1 2 (0) 2     0 0 1 2 − 2, −1  0 0 1 2    2 1 0    3 2 0 FLIP(f)=  4 (0) 1     2 2 2  

Az előadáson egy példán keresztül igazoltuk, hogy: 1. a vízszintes tükrözést megadó összefüggés: NINETY(FLIP(f)) 2. a mellékátló szerinti tükrözést megadó összefüggés: NINETY2(FLIP(f)) 3. a függőleges szerinti tükrözést megadó összefüggés: NINETY3(FLIP(f)) FLIP 135°

f

FLIP 0°

NINETY

FLIP

NINETY

FLIP 45°

FLIP 90°

NINETY

Esetleges vizsgafeladat: adott f,g,h képek esetén számítsuk ki a következő összefüggés értékét: NINETY2(MUL(NINETY(f),FLIP(ADD(g,h)))) 2.3. Adatbázis típusú műveletek – [ezt az idén nem tanítottam] Ebbe a csoportba tartoznak a következő alapműveletek: 1. SELECT(f;m,n,r,t): adott f képből kiválasztunk egy m*n méretű téglalapot, amely az (r,t) koordinátájú ponttól kezdődik. Matematikai megfogalmazásban ez azt jelenti, hogy:  f (i, j ), ha (r ≤ i < r + m) ∧ (t ≤ j < t + n) ∗ különben 

[SELECT(f;m,n,r,t)](i,j)=  1  2 Pl. f =  3  4 5 

2 3 4 5 6

3 4 4 5 5 (6) 6 7 7 8

5  6 4 5     7 , SELECT(f;2,3,-1,-1)=  5 (6)   6 7  8   9 

2. EXTEND(f,g): az f képet megtoldja a g képpel, azaz

8

 f (i, j ), ha  g (i, j )

[EXTEND(f,g)](i,j)= 

f (i, j ) ≠ ∗ különben

Ennek értéke az f képből választódik ki minden olyan képpont esetében, amely az f képben értelmezett, a g képből választódik ki minden olyan képpont esetében, amely a f képben nem értelmezett de a g képben igen, és értelmezetlen (*) lesz minden olyan képpont esetében, amely se az f képben, se a g képben nincs értelmezve. Az EXTEND függvény nem kommutatív. 3. Az előző hasonlatára készült az EXTADD(f,g) függvény, mely összeadja a két képben levő képpont értékeket mindazon helyeken, ahol mindkét kép értelmezett. Ahol csak az egyik értelmezett, ott azt az értéket őrzi meg.  f (i, j ) + g (i, j ), ha (i, j ) ∈ D f ∩ Dg  f (i, j ), ha (i, j ) ∈ D f − Dg  [EXTADD(f,g)](i,j)=  , ∈ − g ( i , j ), ha ( i , j ) D D g f   ∗, ha (i, j ) ∉ D f ∪ Dg

ahol Df és Dg az f és g képek értelmezési tartományát jelöli. 4. Hasonlóképpen értelmezhető az EXTMUL függvény is, meg egyéb állatfajták. 1

2 

 (6) 7   9 

 , g =  Pl. f =   3 (4)   8

1 2 ∗ 1 2 ∗     EXTEND(f,g) =  3 (4) 7  , EXTADD(f,g) =  3 (10) 7  ∗ 8 9 ∗ 8 9     

5. Az EXTEND mintájára készült a REST függvény is. A REST(f,g) viszont csak azokban a képpontokban van értelmezve, ahol g értelmezve van:  f (i, j ), ha  ∗, ha

[REST(f,g)](i,j)= 

g (i, j ) ≠ ∗ g (i, j ) = ∗

6. A CREATE függvény mottója akár a „semmiből egy új világot teremtettem”7 is lehetne. Ez a függvény egy képet hoz létre egy értelmezési tartomány halmazból és egy értéksorozatból. Az értelmezési tartományt koordináta párok alkotják: D=[(i1,j1), (i2,j2), (i3,j3),…, (in,jn)] Az értéksorozatot a következőképpen adjuk meg: R={y1, y2, y3,.. yn} A CREATE függvény létrehoz egy képet a következő képlet szerint:  yk , ha (i, j ) = (ik , jk ) különben  ∗

[CREATE(D,R)](i,j)= 

Pl. D=[(1,1),(1,3),(3,2),(3,3),(4,1),(4,3)], R={1,2,3,4,5,6}

7

Bolyai János, 1823 november 3, Temesvár

9

 2 ∗ 4 6   f=CREATE(D,R)=  ∗ ∗ 3 ∗  1 ∗ ∗ 5 1,3 

2.4. Vágás (thresholding) A vágás egy olyan művelet, amely összehasonlítást végez a képpontok intenzitásértéke és egy küszöbérték között, és ennek eredménye szerint adja a kimenetet. A f kép t küszöbérték szerint vágását THRESH(f,t)-vel jelöljük, és a következőképpen számoljuk: f (i, j ) ≥ t

1, ha  [THRESH(f,t)](i,j)= 0, ha ∗, ha 

f (i, j ) < t f (i, j ) = ∗

Ezen művelethez hasonlóan egyéb műveleteket is definiálhatunk. A TRUNC(f,t) az f kép mindazon értékeit meghagyja változatlanul, amelyek nagyobbak vagy egyenlőek a küszöbértékkel, míg a kisebbeket lekerekíti nullára. Azaz:  f (i, j ), ha  [TRUNC(f,t)](i,j)=  0, ha  ∗, ha 

f (i, j ) ≥ t f (i, j ) < t f (i, j ) = ∗

Egy összefüggés az előbbi két függvény között: TRUNC(f,t)=MUL(f,THRESH(f,t)) Az EQUAL(f,t) függvény azt vizsgálja meg, hogy a képpontok intenzitásértéke egyenlő-e egy bizonyos értékkel: 1, ha  [EQUAL(f,t)](i,j)= 0, ha ∗, ha 

f (i, j ) = t f (i, j ) ≠ t f (i, j ) = ∗

A THRESH függvény akkor adott 1-es értéket, ha az illető képpont intenzitásértéke nagyobb vagy egyenlő a küszöbértéknél. Létezik ennek egy olyan verziója is, amely az egyenlőség esetén már 0 értéket ad: 1, ha  [GREATER(f,t)](i,j)= 0, ha ∗, ha 

f (i, j ) > t f (i, j ) ≤ t f (i, j ) = ∗

Pl. f=

THRESH(f,3)=

TRUNC(f,3)=

 ∗ 2 (3)    2 3 4  3 4 5   

 ∗ 0 (1)    0 1 1  1 1 1   

 ∗ 0 (3)    0 3 4  3 4 5   

10

EQUAL(f,3)= GREATER(f,3)=  ∗ 0 (1)    0 1 0  1 0 0   

 ∗ 0 ( 0)    0 0 1  0 1 1   

A vágás függvények fontos tulajdonsága: nem változtatnak semmit a kép értelmezési tartományán, se az origó helyzetén. 2.5. Vektor típusú műveletek, normák számítása – [erre nem fektettünk nagy hangsúlyt az idén] A vektor típusú műveletek tömbként kezelik a képet. Van egypár egyszerűbb függvény, ami globális információt ad a képről, majd meg fogjuk ismerni a skaláris szorzat fogalmát. 1. A kép képpontjainak száma8: CARD(f)= ∑ [exp( f (i, j ))]0 ( i , j )∈D f

2. A képpontok intenzitásösszege: PIXSUM(f)= ∑ f (i, j ) ( i , j )∈D f

3. A kép képpontjainak átlagos intenzitása: AVER(f)=PIXSUM(f)/CARD(f). 4. Az f és g képek skaláris szorzatát DOT(f,g) jelöli, amit a következőképpen számítunk ki: 

∑ f (i, j ) ⋅ g (i, j ), ha D f = Dg = D

DOT(f,g)= (i , j )∈D 

∗, ha

D f ≠ Dg

Tulajdonságai: Kommutatív DOT(f,g)=DOT(g,f) Összeadásra nézve tranzitív DOT(f,ADD(g,h))=DOT(f,g)+DOT(f,h) DOT(SCALAR(t,f),g)=DOT(f,SCALAR(t,g))=t*DOT(f,g) Egy vektor normája a vektor hosszát (magnitúdóját) jelenti egy bizonyos metrika szerint. A képfeldolgozási algoritmusok keretében 3 féle (első-, másod- és végtelened rendű) normát használunk. Minden képet tekinthetünk vektornak, melyben felsorakoznak a képpontok intenzitásértékei. Ennek a vektornak a normája lesz a kép normája. Az euklideszi metrikának a másodrendű norma felel meg. Ezt a következőképpen számoljuk ki: NORM(f)=MAG2(f)= ∑ [ f (i, j )]2 = DOT ( f , f ) ( i , j )∈D f

A norma tulajdonságai: bármely f és g képek és t skaláris érték esetén NORM ( f ) ≥ 0 NORM ( SCALAR (t , f )) = t ⋅ NORM ( f )

NORM ( SCALAR (1 / NORM ( f ), f )) = 1 , ha NORM ( f ) ≠ 0 DOT ( f , g ) ≤ NORM ( f ) ⋅ NORM ( g ) , ha D f = Dg

9

NORM ( EXTADD( f , g )) ≤ NORM ( f ) + NORM ( g )

Az elsőrendű norma egyenlő a képpontok intenzitásának abszolút értékeinek az összegével: MAG1(f)= ∑ f (i, j ) . ( i , j )∈D f

8 9

A szummában levő kifejezés 1-et ad mindegyik képpontra, helyettesíthető bármely hasonló tulajdonságú kifejezéssel A SCALAR(1/NORM(f),f) műveletet normalizálásnak is szokták nevezni.

11

A végtelened rendű norma egyenlő a képpontok intenzitásának abszolút értékeinek a maximumával. MAG0(f)= max{ f (i, j ) , (i, j ) ∈ D f } . Képfeldolgozási algoritmusokban leggyakoribb a végtelened rendű norma használata, míg a másodrendű normával találkozunk legritkábban. 2.6. Konvolúciós szűrők A konvolúciós szűrő egy lokális operátor. Mindenek előtt szüksége van egy maszkra, ami egy kis méretű kép, mely tartalmazza az origót, sőt a legtöbb esetben szimmetrikus az origóra. A leggyakoribb maszkok 3*3 képpontból álló négyzet alakúak, középen az origóval. A szűrés úgy működik: 1. bejárjuk a kép összes olyan képpontját, ahova el lehet helyezni transzlációval a maszkot úgy, hogy az origó fedi az illető képpontot és a maszk teljes felülete benne van a kép értelmezési tartományában (pl. 3*3 maszk és nagy téglalap alakú képeknél kimarad körben egy egy képpontnyi vastagságú csík). 2. kiszámítjuk az elhelyezett maszk és kép lefedett részének a konvolúcióját (skaláris szorzatát) 3. az így kapott értéket beírjuk a az origó által fedett helyre. A konvolúció számítási módja: [FILTER(f,M)](i,j)= ∑ [TRAN ( M , i, j )](u, v) ⋅ f (i + u, j + v) ( u ,v )∈N

10,

ahol az N halmaz a maszk

értelmezési tartományát jelöli. Ennek a képletnek a jelentését magyarázzuk el egy példán keresztül: 1 2  1 0 1   2 3 , a kép pedig f =  Legyen a maszk M =  0 − 4 0  3 2 1 0 1  −1, −1  4 4 

3 4  2 3 . A képnek az 1 4  4 3 17 , 23

origója valahol messze van, fogjuk fel úgy, hogy egy nagyobb képből metszettünk ki egy kisebb részletet. Meg akarjuk vizsgálni a képben az aláhúzott 1-es értéknek megfelelő képpontban a szűrés eredményét. A maszk méreteiből ítélve N={(u,v)|u=-1,..,1; v=-1,..,1}. Az aláhúzott képpont koordinátái: i=17+2=19, j=23+2=25. Tehát a keresett szűrt érték: [FILTER(f,M)](19,25)= ∑ [TRAN (M ,19,25)](u, v) ⋅ f (19 + u,25 + v) . ( u , v )∈{−1, 0,1}×{−1, 0,1}

1 0 1   De TRAN(M,19,25)=  0 − 4 0  , tehát tovább számolva: 1 0 1 18, 24  10

Vigyázzatok, ez a képlet nem így volt felírva a táblára, de ez a helyes forma

12

[FILTER(f,M)](19,25)= 1 ⋅ 3 + 0 ⋅ 2 + 1 ⋅ 3 + 0 ⋅ 2 - 4 ⋅ 1 + 0 ⋅ 4 + 1 ⋅ 4 + 0 ⋅ 4 + 3 ⋅ 1 = 13 - 4 = 9. [A fenti számítast sem matematizáltuk el ennyire, azaz körülírtuk szöveggel] Maszkok esetében gyakori (de nem feltétlenül szükséges) tulajdonságok: 1. Az értékek összege PIXSUM(M)=1 (ennek értelme az, hogy a szűrt képben azonos nagyságrendű értékek legyenek, mint az eredetiben), vagy PIXSUM(M)=0 (főleg a deriváltaknál fordulnak elő, csak a változás legyen benne a szűrt képben, a konstans alapszín nem) 2. Nagyon sok olyan maszk van, ami szimmetrikus az origóra nézve, vagy valamelyik tengelyére nézve. Az előbbinek az az oka, hogy a vizsgált képponttól azonos távolságra levő képpontok azonos hatással legyenek a szűrésben; az utóbbinak az, hogy az illető iránnyal kapcsolatosan vizsgál meg valamit a szűrő. Mire jó? 1. Szűrésre: alul- és felül áteresztő szűrő, különböző zavarok eltávolítása, stb. 2. Deriváltak számításához, aminek következménye lesz az éldetektálás, majd szegmentálás 3. Másodrendű deriválás, amivel élesíteni lehet a képet. 4. stb. Alul áteresztő szűrő (low pass filter) 1 / 9 1 / 9 1 / 9  1 / 32 1 / 32 1 / 32      Például: M 1 = 1 / 9 (1 / 9) 1 / 9  vagy M 2 = 1 / 32 (1 / 2) 1 / 32  . 1 / 9 1 / 9 1 / 9  1 / 32 1 / 32 1 / 32     

Mit csinálnak? Átlagolnak. M1 nagyon, M2 kevésbé. Szinte eltűnnek a hirtelen változások. A lassú változások is csökkennek, de nem olyan látványosan. Előny: eltűnteti az elszórt hibás fehér és fekete képpontokat (salt and pepper noise). Hátrány: élek elmosódnak. Felül áteresztő szűrő (high pass filter) −1/ 4 0   0   Például: M 3 =  − 1 / 4 (2) − 1 / 4  .  0 −1/ 4 0  

Mit csinál? Nem sokat változtat a gyors változásokon. Erősíti a lassú változásokat. Előny: éleket kiemeli. Hátrány: erősíti a zajt. 2.7. Gradiensek (deriváltak) számítása digitális képek esetében A derivált a változási sebesség mértéke. Digitális képeknél a változás az egymás melletti képpontok intenzitásértékeinek különbségéből adódik. Ezeket könnyen lehet számítani konvolúciós maszkok segítségével.

13

Egy 2D képben két egymásra merőleges (egymástól lineárisan független) irányban tudunk deriválni. Ez legtöbb esetben a vízszintes és a függőleges irány, de lesz példa átló menti deriválási irányra is. A legegyszerűbb deriválási operációk (DX – vízszintes, DY – függőleges ):  f (i, j ) − f (i − 1, j ), ha ∗, ha   f (i, j ) − f (i, j − 1), ha [DY(f)](i,j)=  ∗, ha 

f (i, j ) ≠ ∗ ∧ f (i − 1, j ) ≠ ∗ f (i, j ) = ∗ ∨ f (i − 1, j ) = ∗ f (i, j ) ≠ ∗ ∧ f (i, j − 1) ≠ ∗ f (i, j ) = ∗ ∨ f (i, j − 1) = ∗

[DX(f)](i,j)= 

A gradiens vektor értéke minden egyes képpontban a fenti két összetevőből áll: [GRAD(f)](i,j)=([DX(f)](i,j), [DY(f)](i,j)) A gradiens vektor hosszának avagy magnitúdójának számításához használhatunk első-, másod- vagy végtelened rendű normát. GRADMAG0(f) = MAG0[GRAD(f)] GRADMAG1(f) = MAG1[GRAD(f)] GRADMAG2(f) = MAG2[GRAD(f)] 11 1 2  3 3 Pl. f =  3 (5)  4 5 

3 4 4 6

5 1 ∗ 1   5 1 ∗ 0 DX ( f ) =   ∗ (2) − 1 6     7 1 ∗ 1

∗ 1 1  1 ∗ 0 GRAD( f ) =   ∗ ( 2) − 1  ∗ 1 1  2 1  0 2 GRADMAG0( f ) =  1 (2)  ∗ 1  2 2  0 2 GRADMAG2( f ) =   1 (2) ∗ 1 

2  − 2 −1 −1 0     1  0 − 2 0 − 1 DY ( f ) =  − 1 (0) − 2 − 1 2     ∗ ∗ ∗ ∗  1   2  − 2 −1 −1 0    1   0 − 2 0 − 1  , 2   − 1 ( 0 ) − 2 − 1    1   ∗ ∗ ∗ ∗   1 2  2 2 2 2    1 1  0 2 1 2 GRADMAG1( f ) =  2 2 1 (2) 3 3     ∗ 1 1 1 1 1    2 1 5 1

2   2  5 1 

 (1)   .  − 1

A DX-hez használt konvolúciós maszk: D1 = ((−1) 1) , míg a DY-é D 2 =  DX(f)=FILTER(f,D1), DY(f)=FILTER(f,D2)

11

MAG0, MAG1, MAG2 definícióját lásd a normák ismertetésénél

14

Az eddigi ismertetett deriválási módok mindkét iránynál az éppen vizsgált képpontnak csak az egyik oldalán levő változást vette figyelembe. Mintha egy {xn} számsor xn-ben levő deriváltját az (xn - xn-1) különbséggel határoznánk meg. Számításain pontosabbak lennének mindkét oldal megvizsgálásával, azaz az [(xn - xn-1) + (xn+1 - xn)]/2 képlet alkalmazásával. Ezt a szimmetrikus deriváltat a következőképpen jelöljük és számítjuk: SYMDX(f)=SCALAR(1/2, FILTER(f,SYM1)), ahol SYM 1 = (− 1 (0) 1)  1    SYMDY(f)=SCALAR(1/2, FILTER(f,SYM2)), ahol SYM 2 =  (0)   −1  

A fenti maszkokban kellene legyen meg egy ½-es szorzó, ezt viszont a képletben egy skalárral való szorzás formájában mutatkozik. Ezt akár el is hanyagolhatnánk12, úgyis a deriváltak számításánál a változás (egymáshoz viszonyított) mértéke a fontos, ha mindegyik érték esetében ugyanazt a nem nulla szorzót használjuk vagy elhanyagoljuk, nem ártunk semmit. Szimmetrikus deriváltak esetében is lehet gradienst számolni, teljesen azonos módon. A gradiens vektort SYMGRAD, a különböző normák szerinti magnitúdókat SYMGRAD0, SYMGRAD1 és SYMGRAD2 jelöli. Deriváltak számításához a szakirodalom további, az eddigieknél komplikáltabb maszkokat javasol. Prewitt-féle maszkok:  − 1 0 1   PREW 1 =  − 1 (0) 1  − 1 0 1  

1 1 1   PREW 2 =  0 (0) 0   − 1 − 1 − 1  

A deriváltak számítása ezekkel a maszkokkal: PREWDX=SCALAR(1/6,FILTER(f,PREW1)) PREWDY=SCALAR(1/6,FILTER(f,PREW2)) Ezekből fel lehet írni a PREWGRAD(f) gradiens vektort, és ennek a PREWMAG0, PREWMAG1, PREWMAG2 magnitúdó függvényeit. Sobel-féle maszkok:  −1 0 1   SOB1 =  − 2 (0) 2   −1 0 1  

2 1 1   SOB 2 =  0 (0) 0   − 1 − 2 − 1  

A deriváltak számítása ezekkel a maszkokkal: SOBDX=SCALAR(1/8,FILTER(f,SOB1)) SOBDY=SCALAR(1/8,FILTER(f,SOB2)) Ezekből fel lehet írni a SOBGRAD(f) gradiens vektort, és ennek a SOBMAG0, SOBMAG1, SOBMAG2 magnitúdó függvényeit.

12

gyakorlati megvalósításoknál el is szokták hanyagolni

15

Általánosítás13:  −1 0 1    SHEP1 =  − λ (0) λ   −1 0 1   

λ 1  SHEP 2 =  0 (0)  −1 − λ 

1  0 − 1

SHEPDX=SCALAR(1/(4+2λ),FILTER(f,SHEP1)) SHEPDY=SCALAR(1/(4+2λ),FILTER(f,SHEP2)) Roberts-féle maszkok: Ezek megint nem szimmetrikusak, és nem vízszintes-függőleges iránypár szerint deriválnak, hanem a kép átló mentén.  (−1) 0   ROB1 =   0 1

 (0) 1   ROB2 =   −1 0

A gradiens vektor képlete: ROBGRAD(f)=(SCALAR( 2 / 2 ,FILTER(f,ROB1)), SCALAR( 2 / 2 ,FILTER(f,ROB1))

Ebből is számíthatunk ROBMAG0, ROBMAG1 és ROBMAG2 magnitúdókat.  2 7 3   Példa: f =  3 5 7  1 5 8  

MASZKOK 1. IRÁNY

DX, DY

2. IRÁNY

 5 − 4   −1 2 − 4    (2) 2   2 (0) − 1     4 3  

 1   ∗ 1  2   2 SYM  ( 4 2)  1 2 ( 2 2) − 5 2  1 2 (2)     7   ∗ 7 2  2  

(

)

MAG0

MAG1

 1 5 4   1 7 8   1     2 ( 2) 2   2 ( 2) 3   2  ∗ 4 3   ∗ 4 3   ∗   

∗  5  2 ∗  

 ∗ 1  2 1 (3)  2  ∗ 7 2 

∗  5  2 ∗  

MAG2 29 (2) 4

32   5  3 

1  ∗ ∗   2 1 ( 5) 5  2  2 7  ∗ ∗  2  

PREWITT

(12 6 )

(− 2 6 )

(2)0,0

(7 3 )

 37   3  0,0 

SOBEL

(16 8 )

(0 8 )

(2)0,0

(2)0,0

(2)0,0

ROBERTS

13

0, 0

0, 0

2  3 0   2  2 3  0, 0

0,0

0,0

0,0

2  4 − 2 2  4 2 2  7 2   12.5       2  4 2  0,0 2  4 3  0, 0 2  6 5  0, 0  10

általánosítottam én és Shepard bácsi segített; λ=1 a Prewitt sajátos esete, λ=2 a Sobelé

16

2   6.5  0, 0

Irány szerinti deriválás Definíció szerint az f kép α irány szerinti deriváltja: [DIRECT(f;α)](i,j)=[DX(f)](i,j)*cos α + [DY(f)](i,j)*sin α Vagy vektorosan:

 cos α    sin α 

[DIRECT(f;α)](i,j)= [GRAD( f )](i, j ) • 

(ez skaláris szorzás).

Tehát a tetszőleges α szög által meghatározott irány szerinti deriváltat a vízszintes és függőleges irány szerinti deriváltakból tudjuk kiszámítani.  2 7 3   Pl. Adott az f =  3 (5) 7  kép. Számítsuk ki az α=127°-os irány szerinti deriváltját, 1 5 8  

tudva azt, hogy sin α=0.8. Megoldás: ha α=127°, azaz 90 és 180 fok között van, akkor cos α = − 1 − sin 2 α = −0.6 .  5 − 4    −1 2 − 4  , tehát DX(f)=  (2) 2  , DY(f)=  2 ( 0 ) − 1    4 3  

[DIRECT(f;α)](i,j)=  − 0 .8 − 1 .4 − 0 .8    =  1.6 (−1.2) − 2   ∗ − 2.4 − 1.8  

 − 1 × 0.8 5 × (−0.6) + 2 × 0.8 − 4 × (−0.6) − 4 × 0.8     2 × 0.8 2 × (−0.6) + 0 × 0.8 2 × (−0.6) − 1× 0.8    ∗ 4 × (−0.6) 3 × (−0.6) −1, −1 

=

14

2.8. Másodrendű derivált. Laplace maszk alkalmazása képek élesítésére Az {xn}n>0 számsorozat másodrendű deriváltját xi-ben az xi+1-2xi+ xi-1 képlet adja meg. Ennek megfelelően felírhatjuk a másodrendű derivált maszkját, melybe beleírjuk ezeket az együtthatókat függőlegesen is és vízszintesen is. ∂2 Vízszintes irányú másodrendű deriválás maszkja, mely a 2 operátor megfelelője: ∂x 0 0 0   1 − 2 1 0 0 0 −1, −1 

14

Remélem jól számoltam

17

Függőleges irányú másodrendű deriválás maszkja, mely a

∂2 operátor megfelelője: ∂y 2

0 1 0   0 − 2 0 0 1 0 −1, −1   ∂2

∂2 

E két maszk összege a  2 + 2  operátor, a Laplace operátor megfelelője, ezért ∂y   ∂x 0 1 0   nevezik a  1 − 4 1  maszkot Laplace-féle maszknak. 0 1 0 −1, −1 

A képi információ esetében a másodrendű derivált egy remek mutatója az elmosódottságnak, azaz éles képeken a másodrendű derivált értéke kicsi, elmosódott képeken viszont nagyobb. Éppen emiatt alkalmas a Laplace-féle maszkkal történő szűrés a kép élesítésére. A módszer lényege a következő: Minden egyes képpont esetében kiszámítjuk a Laplace maszk segítségével szűrt értéket, ezt megszorozzuk egy k faktorral és kivonjuk az eredeti intenzitásértékből. Jelöljük g-vel az f kép kiélesített változatát. A fennebb leírtak alapján ennek számítása a következőképpen történik: g (i, j ) = f (i, j ) − k ⋅ [ FILTER( f , LAPL)](i, j ) , azaz 1 0  0 0 0 0     g (i, j ) = [ FILTER ( f ,  0 (1) 0 )](i, j ) − k ⋅ [ FILTER ( f ,  1 (−4) 1 )](i, j )  0 0 0 0 1 0    

,

vagy

összevonva  0  g (i, j ) = [ FILTER ( f ,  − k  0 

−k

0   (4k + 1) − k )](i, j ) −k 0  −k 0   0   Tehát a kép élesítése a  − k 4k + 1 − k  maszk segítségével történő szűréssel  0 −k 0  

egyenértékű. Minél nagyobb a k értéke, annál élesebb lesz a kép (természetesen van ennek ára is, a nagyfrekvenciás zajok felerősödnek), k=0 esetén a szűrés változatlanul hagyja a képet, negatív k esetén pedig elmosódottabb lesz az eredményként kapott kép. 2.9. Éldetektálás gradiensek segítségével A képek nagy része homogén zónák gyűjteménye. Miki egér rajzfilmes portréja nem tartalmaz több mint 5-6 színt, azaz a homogén régiók teljesen azonos színűek. Egy digitális fénykép esetén már más a helyzet, ott egy egyszínű tárgy képpontjai különböző színűek a térben változó fényviszonyok és a zaj miatt, de azért ezek a színek nagyon hasonlítanak egymáshoz, a képpontok homogén zónákat alkotnak. Ezen régiók 18

találkozásánál vannak olyan szomszédos képpontok, amelyek színe jelentősen eltér egymástól. Az ilyen zónák közötti határvonalak lesznek az élek a képben. Egyesek erősebbek, mások gyengébb élek lesznek. Az élek erősségét matematikailag a gradienssel tudjuk legjobban jellemezni. Ha élet akarunk keresni, olyan képpontokat kell keresnünk, melyekben a gradiens valamely norma szerint számolt magnitúdója nagy értékkel rendelkezik. Ha egy bináris képen keressük az éleket, ott a fekete és fehér közötti határvonal egyértelmű. Ha egy intenzitásképben keressük a sötét és világos közti határvonalat, azt megpróbálhatnánk egy vágással is megoldani, ami sötétebb egy bizonyos értéknél azt feketévé konvertáljuk, ami világosabb azt fehérré, s ezután máris visszatértünk a bináris esetre. De az intenzitásképek zajt is tartalmaznak, ezért egy vágás nem vezet jó eredményhez. Maradunk a deriválás, a gradiens mellett. Éldetektálási algoritmus általánosan megfogalmazva: adott egy maszkcsalád, mely különböző irányok menti deriváltat számolja. Pl. PREW1 és PREW2, D1 és D2, vagy bármelyik pár az előző fejezetből. A család mindegyik tagjával kiszámoljuk a kép deriváltját, és képezzük valamely 15 gradiens magnitúdó mátrixot. Ezt a mátrixot egy vágásnak vetjük alá, és az eredmény mátrixban az 1-esek fogják képezni a határvonalakat. Kérdés: mennyi legyen a küszöbérték? Ha a küszöb túl kicsi, akkor a határvonalak nem 1 képpontnyi vastagságúak lesznek, vagy esetleg kevésbé jelentős élek is látszani fognak az ábrán. Viszont ha túl nagy a küszöb, akkor túl kevés él fog látszani. Milyen maszkcsaládok kerülhetnek alkalmazásra? 1. D1 és D2 2. SYM1 és SYM2 3. PREW1 és PREW2 4. SOB1 és SOB2 5. ROB1 és ROB2 6. Iránytű gradiens maszkcsaládok. Ezeket úgy képezzük, hogy van egy alap maszk, amelyet 45 fokonként megforgatunk valamely irányba, s így 8 különböző maszkot kapunk. Prewitt iránytű maszkjai: 1 1  − 1 1 1  1     − 1 (−2) 1  − 1 (−2) 1  − 1 1 1  − 1 − 1 1    − 1  1 − 1 − 1 1 1    1 (−2) − 1 1 (−2) − 1 1 1 − 1 1 1 1  

1 1  1 1 1 1     1 (−2) 1  1 (−2) − 1  − 1 − 1 − 1  1 − 1 − 1     − 1 − 1 − 1  − 1 − 1 1     1 ( −2) 1   − 1 ( −2) 1 1 1 1   1 1 1 

Kirsh (Kirsch) iránytű maszkjai

15

fejben a MAG0-át tudjuk könnyen számolni, de valójában a MAG2 lenne a legigazságosabb, a számítógépnek viszont nagyjából mindegy melyiket számolja

19

3 3  − 5 3 3  3     − 5 ( 0) 3   − 5 ( 0) 3   − 5 3 3  − 5 − 5 3     3 3 − 5  3 − 5 − 5     3 ( 0) − 5   3 ( 0) − 5   3 3 − 5  3 3 3   

 3   3 −5  −5   3  3 

3 (0)

−5 −5 (0) 3

3  3 3 3    3   3 ( 0) − 5  − 5   3 − 5 − 5  − 5   − 5 − 5 3   3   − 5 ( 0) 3  3   3 3 3 

3 szintű (3-level) iránytű maszkok: PREW1 megforgatva 8-szor. Megjegyzések: 1. Mindegyik ilyen maszkban az értékek összege NULLA. 2. A Kirsh maszkcsalád esetében mind a 8 deriváltat végig kell számolni, a másik két családból elég az első 4-et, mert a többi csak egy negatív előjelben különbözik. Tehát a derivált nagysága ugyanakkora lesz, a fordított előjel a magnitúdó számításnál nem érvényesül. Ide kellene egy példa, de 8*8-as mátrixokat most nincs kedvem rajzolni. Egyet rajzoltam annak idején a táblára. 2.10. Hisztogram és egyéb állatfajták Egy intenzitáskép hisztogramja megmutatja, hogy milyen intenzitású (színű) képből hány darab van a képen. Ha a kép definíció szerint f : X → {0,1,2,..., m − 1} , ahol X ⊆ Z × Z , akkor ennek a hisztogram függvénye így néz ki: [HIST(f)](c), ahol c ∈ {0,1,2,..., m − 1} . Ennek értéke megadja, hogy hány képpontnak a színe egyenlő c-vel. m −1

Értelemszerűen ∑ [ HIST ( f )](c) = CARD ( f ) . Miért? (vizsgakérdés átmenő jegyhez) c =0

1  1 1 Pl. Az f =  1 1  4 

2 7 5 5 2 2

7 2 0 0 2 2

7 5 3 3 3 1

2 1 2 2 2 1

3  3 1  kép 8 árnyalatú intenzitáskép. Az f hisztogramja: 2 2  5 

[HIST(f)]=(2, 9, 12, 5, 1, 4, 0, 3). Hány darab 3-as színű képpont van? [HIST(f)](3)=5. Tehát öt! Ha egy kép túlnyomóan sötét vagy túlnyomóan világos színekből áll, akkor nem elég éles. Ezen lehet változtatni egy hisztogram kiegyenlítéssel. Hisztogram kiegyenlítés lépései az előbbi példával bemutatva: 1. Kiszámoljuk, hogy hány db egyszínű képpontunk lenne, ha mindegyik színből ugyanannyi lenne: Q=CARD(f)/m=36/8=4.5 20

2. Négy és fél. Ha ez nem egész szám, akkor lesznek olyan színű képpontok, amelyből lekerekített számú db lesz (a mi esetünkben 4), és lesz olyan osztály amelyikben felkerekített számú db lesz (a mi esetünkben 5). 3. Elindulunk a legsötétebb képpontoktól, és kiválasztjuk az első Q db legsötétebb pontot, bejelöljük 0-val. Majd a maradékból kiválasztjuk a legsötétebb Q db pontot és bejelöljük 1-essel. Majd jöhet Q db 2-es, 3-as, …, végül 7-es. 4. Sajnos nem csak az nem egyértelmű, hogy Q éppen 4 vagy 5, hanem legtöbbször az se, hogy melyik az a Q db legsötétebb pont a maradékból. Ilyenkor választunk találomra. A képünk élesebb lesz, de a találomra választott képpontok miatt előfordulhat és elő is fordul egy valamekkora zajszint (jó esetben plusz-mínusz egy-két színárnyalatnyi fehér zaj). Ez 8 színű kép esetben sok, 256-nál már kevés. Jöhet a példa lefutása. Előbb kiosztjuk a 0-kat, majd az 1-eseket, s így tovább…: 0  . 0  . .  .  0  1 0  1 2  . 

. . . . . . 3 . . . 2 3

. . 0 0 . . . 4 0 0 4 2

. . . . . .

.  . .  . . .

. 0 . . . . . . . . . 1

3 0 4 3 2 2

0 .  1 . 0 .  1 . . .  . .  .  0  .  1 1 0  4 1 3   2 .  

. . 0 0 . . 3 . . . 2 3

. . . . . 1 . 4 0 0 4 2

. 0 . . . . . . 5 5 5 1

. 0  . 1 1  0  . 1 .   2 .   . 3 5  0 5 4 1  3 4 2 3  2 . 

. . . . 2 . 0  1 0  1 2  6 

. . 0 0 . 2 3 . 6 . 2 3

. . . . . 1 . 4 0 0 4 2

. 0 . . 2 2 . 6 5 5 5 1

. 0 3  . 1 . 1  0 .  . 1 . .   2 2 .   . 3 3 5 0  0 5 1 4 1 0  3 4 1 2 3   2 2 6   6

. . 0 0 . 2

. . . . . 1 3 7 6 7 2 3

3 .  0 . . 1  3 . 2 3  2 .  7 7 3 4 6 0 0 5 4 0 5 3 4 5 2 2 1 2

5  5 1  4 3  6 

Tehát a hisztogram kiegyenlítése után a hisztogramunk: HIST(f ’)=(5,4,5,5,4,5,4,4). A hisztogram kiegyenlítési művelet nem determinisztikus a találomra történő választások miatt. Tehát ha még egyszer újra kiegyenlítjük az eredeti képünket, akkor más eredményt fogunk kapni. Egyéb állatfajta az angolosan elnevezett co-occurence matrix, melyet magyarul együttállási mátrixnal lehetne leginkább nevezni. A mátrix (i,j) koordinátájú eleme megmutatja, hogy a képben i intenzitású képpontoknak összesen hány j intenzitású szomszédja van. Nem egyértelmű, hogy mit nevezünk szomszédságnak, mert lehet szó a négyelemű erős szomszédságról vagy a 8 elemű teljes közvetlen szomszédságról16. Az együttállási mátrix jele a C(f,R), ahol f a kép, R pedig a szomszédság típusát jelöli. A histogramnál használt jelölések szerint az együttállási mátrix m*m-es méretű. 16

4 elemű szomszédság alatt a képponttól közvetlenül jobbra, balra, fölötte és alatta fekvő képpontokat értjük, melyek távolsága az aktuális képponttól 1 egységnyi. 8 elemű szomszédságban ezen kívül benne vannak a

2 egységnyi távolságra fekvő, átlós irányban közvetlen szomszédok.

21

4   1 2 2   1 Pl. f =  2 3 1  C ( f ,4) =  1  0 0 0   −1, 2  1 

1 0 3 1

1 3 2 2

1  1 2  0 

Hogy hogyan számoltam ki, nem akarom részletezni, ilyen példát a vizsgán nem fogok kérni. Se a hisztogram, se az együttállási mátrix nem függ az origó helyzetétől. A hisztogram kiegyenlítés csak a képpontok színét változtatja, az origó pozícióját nem. 2.11. Medián szűrő Korábban láttuk, hogy átlagolással ki lehet szűrni a „só és bors” jellegű zajokat a képekből. Ehhez kellett egy alul áteresztő szűrő maszk, amivel konvolúciós szűrést kellett végighajtani. A medián szűrő nem átlagol. Inkább definiál egy origóra szimmetrikus szomszédságot (leginkább a 8 elemű szomszédságot használják), és mindegyik képpont intenzitásértékét kicseréli a szomszédságában található intenzitásértékek medián, azaz középső értékével. Tehát a szűrés lépései a következők: 1. Definiáljuk a szomszédság fogalmát: pl. minden képpont szomszédsága önmagából + a körülötte levő 8 közvetlen szomszédból áll. 2. Minden egyes képpont esetén növekvő sorrendbe állítjuk a szomszédságban levő képpontok intenzitásértékeit egy külön vektorba, majd kiválasztjuk a medián, azaz a középső értéket. 1+8=9 elemű szomszédságból ez az ötödik elem17. 3. Ezt a középső értéket visszaírjuk az aktuális képpontba. Megjegyzés: a kép szélén levő képpontok szomszédsága nem lesz teljes, ezekben előfordulhat az is, hogy páros számú elemből kell kiválasztani a medián értéket. Ekkor a két középső közül válasszunk, első megközelítésben találomra, másodikban megközelítésben azt amelyik közelebb áll az átlagértékhez. 5  9 Pl. f =  6  15 

7 8 6  0 15 7  , melyben a 0-s értékek hibásan regisztrált fekete képpontok, a 158 15 0   6 6 8 

ösök hibásan regisztrált fehér képpontok. Medián szűrés eredménye a középső négy képpontra: (0,5,7,9), tehát 5 vagy 7, inkább 5(második megközelítés) (0,5,7,8,9,15), tehát 7 vagy 8, inkább 7. (0,6,7,7,8,15), tehát 7 (6,7,8,15), tehát 7 vagy 8, inkább 8. (0,5,6,7,8,9), tehát 6 vagy 7, inkább 6. (0,5,6,7,8,8,9,15,15), tehát 8. (0,0,6,7,7,8,8,15,15), tehát 7. (0,6,7,8,15,15), tehát 7 vagy 8, inkább 8. (0,6,6,8,9,15), tehát 6 vagy 8, inkább 8. 17

Rendeze Luc Besson, főszerepben Milla Jovovich és Bruce Willis

22

(0,6,6,6,8,9,15,15,15), tehát 8. (0,0,6,6,7,8,8,15,15), tehát 7. (0,6,7,8,15,15), tehát 7 vagy 8, inkább 8. (6,6,8,15), tehát 6 vagy 8, inkább 8. (6,6,6,8,15,15), tehát 6 vagy 8, inkább 8. (0,6,6,8,8,15), tehát 6 vagy 8, inkább 8. (0,6,8,15), tehát 6 vagy 8, inkább 8. 5  6 Végeredmény:  8  8 

7 8 8 8

7 7 7 8

8  8 . Értékelés: a széleken kapott értékekkel nem föltétlenül 8  8 

vagyok megelégedve. A gyakorlatban sokkal több belső pont van mint szélső, mert nagyobbak a képek. Képpontjainknak 30%-a zaj volt, mind kiszűrődött, tehát hatékony módszer. Használni fogjuk nem csak a vizsgán, hanem utána is. 2.12. Box szűrő Box szűrő alatt a szakirodalom egy, a mediánhoz hasonló szűrőt ért. Azaz: a box szűrő az éppen szűrni kívánt (továbbiakban: aktuális) képpont környezetében (3x3, 5x5, stb.) megvizsgálja, hogy az aktuális képpont intenzitása a legnagyobb (legkisebb) a környezetben. Amennyiben az aktuális képponté a legnagyobb (legkisebb) intenzitás, úgy annak intenzitásértékét egyenlővé tesszük a második legnagyobb (második legkisebb) intenzitás értékkel. Előnye a medián szűrővel szemben, hogy a kép szélén és sarkain levő képpontokat is le tudjuk kezelni. Hatása: kevésbé homályosít és kevésbé szűr, mint a medián szűrő. 5  9 Pl: f =  6  15 

7 8 6 5 7 8 7    0 15 7   9 5 15 7  kép 3x3 box szűrés után lesz: f =  8 15 0  6 8 15 6     8 6 6 8 6 6 8   

3. Morfológia A morfológia latinul alaktant jelent. A mi estünkben a morfológia egy olyan eszköztárat képvisel, mellyel a képeken látható objektumok alakját tudjuk változtatni, határvonalakat kisimítani, stb. Ez a satöbbi azt jelenti, hogy a morfológiai alapműveletek felhasználásával komplikáltabb műveleteket is elvégezhetünk, pl. a váz (skeleton) keresése. A morfológiai alapműveleteket Hermann Minkowski18 matematikusnak köszönhetjük, az ő munkásságának folyománya az, amit ma morfológiának nevezünk a képfeldolgozásban. A morfológiai műveletek célja: 1. előfeldolgozás során zajok eltávolítása, formák/határvonalak egyszerűsítése/simítása 2. objektumok struktúrájának kiemelése 3. szegmentálás 18

Albert Einstein kortársa volt, legalábbis nagyjából egy időben alkották meg legjelentősebb munkáikat

23

3.1. Egyszerűbb morfológiai műveletek: dilation, erosion, opening, closing. Analóg és bináris képek esetében. A morfológia két alapművelete a tágítás (dilation) és a szűkítés (erosion). Ezek kombinációjából tevődik össze a nyitás (opening) és a zárás (closing). A fennebb említett műveletek mindegyikéhez szükség van egy strukturáló elemre (structuring element), melyet általában B-vel jelölünk. A strukturáló elem egy kisméretű objektum, melynek rögzítve van az origója. Általában az origóra vagy valamely tengelyre nézve szimmetrikus, de ez nem kötelező. Alábbi ábrán láthatunk néhány strukturáló elemet. Az origó legtöbb esetben a strukturáló elemhez tartozik, de ez sem kötelező (ellenpélda az utolsó).

Tágítás / Dilation: a Minkowski-féle összeadás analógiája. Jele az ⊕ . Definíció szerint egy X halmaz (kép) tágítása egy B strukturáló elemmel a következőt jelenti: X ⊕ B = p ∈ ε 2 : p = x + b, x ∈ X , b ∈ B , ahol ε 2 a kép értelmezési tartománya (kétdimenziós koordináták halmaza). Konkrétan ez azt jelenti, hogy az objektum minden képpontjához elvisszük a strukturáló elemet, és annak képpontjait egyesítjük. Példa: X = {(1,0),(1,1),(1,2),(2,2),(0,3),(0,4),(1,5)} B = {(0,0),(1,0),(1,1)} X ⊕ B = {(1,0),(1,1),(1,2),(2,2),(0,3),(0,4),(1,5), (2,0),(2,1),(2,2),(3,2),(1,3),(1,4),(2,5), (2,1),(2,2),(2,3),(3,3),(1,4),(1,5),(2,6)}

{

}

Az ábrán bal oldalt található az X objektum, középen a B strukturáló elem, jobb oldalt pedig a tágítás eredménye. Az eredményben a képpontokban levő számok azt jelölik, hogy az adott képpont a strukturáló elemnek melyik eredeti képpontra való ráhelyezéséből keletkezett. Az X ⊕ B halmazból látható, hogy egyes képpontok többszörösen szerepelnek.

24

A tágítás legfontosabb matematikai tulajdonságai: a. kommutatív, azaz X ⊕ B = B ⊕ X b. asszociatív, azaz ( X ⊕ B1 ) ⊕ B2 = X ⊕ ( B1 ⊕ B2 ) c. a tágítás egy növekedési transzformáció, azaz a képen az objektumok megnőnek. Ugyanakkor a szűk lyukak és öblök eltűnnek tágítás során. Szűkítés / Erosion: a Minkowski-féle kivonás analógiája. Jele a bekarikázott mínusz jel: ө. Definíció szerint egy X halmaz (kép) szűkítése egy B strukturáló elemmel a következőt jelenti: = { p ∈ ε 2 : p + b ∈ X , ∀b ∈ B} ,

ahol ε 2 a kép értelmezési tartománya (kétdimenziós koordináták halmaza). Konkrétan ez azt jelenti, hogy az objektumnak azok a képpontjai maradnak meg, ahova el tudjuk helyezni a strukturáló elemet úgy, hogy annak minden pontja az objektumon belül maradjon. Példa: X = {(1,-1),(2,-1),(1,0),(2,0),(3,0),(1,1),(2,1),(0,2),(1,2),(2,2),(3,2),(4,2),(1,3),(1,4)} B = {(0,0),(0,-1),(1,-1)} X ⊕ B = {(1,0),(1,1),(2,1),(1,2),(1,3)}

Az ábrán bal oldalt található az X objektum, középen a B strukturáló elem, jobb oldalt pedig a szűkítés eredménye. Az eredeti objektum képpontjaiban levő számjegyek azt jelzik, hogy melyik képpontok objektumhoz tartozására volt szükség ahhoz, hogy az illető számmal jelzett képpont az eredményben benne legyen. A szűkítés nem kommutatív, nem asszociatív. A szűkítés egy csökkenési transzformáció, mert a művelet végrehajtása során az eredeti objektumok csak csökkenni tudnak, növekedni nem. Szűkítés során az objektumok elveszítik hosszú vékony nyúlványaikat. Nyitás és Zárás / Opening and Closing az előbbi két művelet kombinációja. A nyitás egy olyan transzformáció, mely során egy szűkítést követő tágítás: A zárás egy olyan transzformáció, mely során egy szűkítést követő tágítás: Mindkét művelet esetében a szűkítést és tágítást ugyanazzal a strukturáló elemmel végezzük. Legfontosabb tulajdonságuk: A nyitás során az objektumok csak csökkenni tudnak, növekedés kizárt. A zárás során az objektumok csak növekedni tudnak, csökkenés kizárt.

25

Egy egyszerű alkalmazás: bináris képekben az objektumoknak egy képpontnyi vastagságú külső határvonalát kapjuk, ha végrehajtunk egy tágítást az ábrán látható strukturáló elemmel és az eredményből kivonjuk az eredeti ábrát.

A határvonal betűi azt mutatják, hogy az eredeti objektum melyik képpontjának tágítása által keletkeztek (van köztük olyan is, amelyikbe más betűt is írhattunk volna). 3.2. Bináris képek, objektumok váza (skeleton). Hit-or-miss transzformáció. Szűkítés és vastagítás. Golay-ábécé. Hit-or-miss transzformáció. Angolul a „hit” azt jelenti: „talál”, a „miss” pedig azt, hogy „nem talál”19. Ez a transzformáció arról szól, hogy adott egy maszk, melyben három féle elem szerepelhet: 1, 0, *.  1 0 ∗   Pl. H =  ∗ (1) 1   0 ∗ 1  

A fenti H maszk szerinti hit-or-miss transzformáció azokat a képpontokat választja ki egy képből, amelyikre • minden 1-es elem helyén objektumnak megfelelő képpont van (rajzon fekete) • minden 0-ás elem helyén háttérnek megfelelő képpont van (rajzon fehér) A * értékek nem befolyásolják a hit-or-miss transzformációt eredményét. Jelölés: X ⊗ H jelöli az X kép H maszk szerinti transzformáltját. Az alábbi példában csak egyetlen képpont felel meg a hit-or-miss transzformáció feltételének, s annak sincs látszólag semmilyen speciális tulajdonsága. Ez azért van, mert találomra választottuk meg a H maszkot.

Objektumok (például fekete ceruzával fehér papírra írt betűk) azonosítási feladatainál felmerült az az egyszerűsítő ötlet, hogy a vastag vonalakat le kell vékonyítani, majd amikor 19

Mindkettő köztudottan jelent mást is, de ez most senkit ne hozzon tévedésbe

26

minden vonal egyetlen képpontnyi vastagságú lesz (ez a váz vagy angolosan skeleton) akkor majd abból azonosítják az objektumot. Valamely objektum vázát megkaphatjuk a következő két definíció segítségével: 1. Az objektumot teljes kerülete mentén egyszerre elkezdjük égetni. Az égési frontok egyenletesen haladnak végig az objektumon, majd mindazok a pontok, amelyekben égési frontok találkoznak, részei lesznek az objektum vázának.20

2. Legnagyobb körök módszere. Köröket rajzolunk az objektum teljes területére. Legnagyobb körök lesznek azok a körök, amelyekről elmondható, hogy nincs olyan kör amelyikben teljes terjedelemben benne lennének és amelyik az objektum része lenne. Ha megkapjuk a legnagyobb köröket, akkor ezek középpontjait összekötve megkapjuk az objektum vázát:

Az alábbi ábrán látható 3 különböző objektum váza:

Hit-or-miss transzformáció alkalmazásai: Egyszer volt, hol nem volt, volt egyszer egy Golay nevű emberke, aki nem találomra választotta meg a hit-or-miss transzformáció maszkjait, s ezek segítségével kidolgozott egy módszert az objektumok vázának megkeresésére diszkrét bináris képek esetén. Objektumok vékonyítása úgy lehetséges morfológiailag, hogy hit-or-miss transzformációval kiválasztjuk a szélső képpontokat és azokat eltávolítjuk azaz kivonjuk az eredeti objektumból. Általánosan ez így néz ki: X ø L = X \ ( X ⊗ L) . Vastagítás úgy lehetséges morfológiailag, hogy hit-or-miss transzformációval kiválasztjuk azokat a háttérhez tartozó képpontokat, amelyek az objektum közvetlen közelében vannak és ezeket hozzáadjuk az objektumhoz. Általánosan ez így néz ki: X ☺ L = X ∪ ( X ⊗ L) .21 20

De sajnos az objektum már elégett…

27

Golay kidolgozta a szekvenciális vékonyítás módszerét. Létrehozta az úgynevezett Golayábécét, mely valójában maszk családok gyűjteménye. A szekvenciális vékonyítást az L1…L8 maszkok segítségével valósítja meg: 0 0 0   L1 =  ∗ (1) ∗  1 1 1   1 1 1   L5 =  ∗ (1) ∗   0 0 0  

∗ 0 0   L2 =  1 (1) 0  ∗ 1 ∗    ∗ 1 ∗   L6 =  0 (1) 1   0 0 ∗  

1 ∗ 0    L3 = 1 (1) 0  1 ∗ 0     0 ∗ 1   L7 =  0 (1) 1  0 ∗ 1  

∗ 1 ∗   L4 =  1 (1) 0  ∗ 0 0    0 0 ∗   L8 =  0 (1) 1   ∗ 1 ∗  

A szekvenciális vékonyítás képlete: X ø L = (((((((( XøL1 )øL2 )øL3 )øL4 )øL5 )øL6 )øL7 )øL8 ) , melyet mindaddig ismételjük, amíg vékonyodik. Mind a 8 maszk szerinti vékonyítás egyegy réteget vesz le az objektumról valamilyen irányból (iránytű 8 fő iránya): az L1 az objektum tetejéről (északról), az L2 északkeletről, az L3 az objektum jobb oldaláról azaz keletről, stb. Ha végrehajtjuk mind a 8 irányból a szűkítést, akkor hiányozni fog az objektum külsejéről egy teljes réteg (lásd alább a rajzot). Igazságosabb lenne az L1…L8 maszkokat véletlenszerű sorrendbe tenni, mert a sorrend befolyásolja a végeredményt. Különböző színekkel jelöltük az első-, második-, harmadik-, illetve negyedik iterációban eltávolított képpontokat, és azt is bejelöltük, hogy melyik képpontot melyik maszk segítségével távolítottuk el. A feketén maradt képpontok alkotják az objektum vázát. Tehát láthatjuk, hogy az L betűvel jelölt maszkok a Golay-ábécében objektumok vázát keresik meg.

A Golay-ábécé E betűvel jelölt maszkjaival a már megtalált váz végződéseit lehet lerövidíteni, míg az esetleges zárt görbéket változatlanul hagyja. Működési elve hasonlít az előzőleg ismertetett L maszkokéhoz. 21

Itt a ☺ helyett olyan jel kellene legyen, hogy egy pont a karikán belül, de ilyent nem találtam winwordfalván

28

∗ 1 ∗   E1 =  0 (1) 0  0 0 0   0 0 0   E5 =  0 (1) 0  ∗ 1 ∗  

 0 ∗ ∗   E2 =  0 (1) 0   0 0 0    0 0 0   E6 =  0 (1) 0  ∗ ∗ 0  

 0 0 ∗   E3 =  0 (1) 1   0 0 ∗   ∗ 0 0   E7 =  1 (1) 0  ∗ 0 0  

 0 0 0   E4 =  0 (1) ∗   0 0 ∗   ∗ 0 0   E8 =  ∗ (1) 0   0 0 0  

Golay ábécéje további maszkcsaládokat tartalmaz, melyeket M, D és C betűkkel jelölünk. Ezeket napjainkban nagyon ritkán alkalmazzák. Vékonyításhoz használt maszkok közepén 1-es, vastagításhoz használt maszkok közepén 0-s van. Ez azért kell így legyen, mert a vékonyításnál olyan, az objektumhoz tartozó azaz fekete, képpontokat keresünk, amelyeket el lehet távolítani, míg a vastagításnál olyan, a háttérhez tartozó azaz fehér, képpontokat keresünk, amelyeket az objektumhoz lehet csatolni. 3.3. Intenzitás képek morfológiája: dilation, erosion, opening, closing. Alkalmazás: top hat transzformáció. Az intenzitásképek dilatációja egy maximum számításra, az erózió pedig minimum számításra vezetődik vissza. Ebből kifolyólag a dilatáció során a világos foltok kiterjednek, a sötétek összehúzódnak, erózió közben pedig mindez fordítva történik. Közben a bináris morfológiai műveletekhez hasonlóan, itt is öblök illetve nyúlványok tűnnek el a dilatáció, illetve erózió során. Magától értetődően, az nyitás és zárás definíciója ugyanaz, mint bináris esetben, ami a műveletek sorrendjét illeti.

4. Szegmentálás 4.1. Digitális képek szegmentálása: célja, módszereinek osztályozása Digitális képek szegmentálásánál az egyértelmű cél, hogy a képet homogén részeire, homogén régióira bontsuk. Mi az, hogy homogén? Azonos vagy hasonló színűek kell legyenek a régión belüli képpontok, vagy valamilyen textúrával, mintával kell rendelkezniük. Általánosabban: eleget kell tegyenek egy homogenitási kritériumnak. Definíció szerint a homogenitási kritérium egy olyan függvény22, ami a képpontok egy bizonyos összefüggő halmazáról egyértelműen el tudja dönteni, hogy homogén közeget alkotnak vagy sem. A szegmentálás lehet teljes, hogyha a képet diszjunkt halmazokra, egyértelmű objektumokra bontja, vagy részleges, ami a képet valamely tulajdonság (homogenitási kritérium) alapján régióira bontja.

22

C++-ban: BOOL IsHomogeneous(CRegion reg){...};

29

Szegmentálás célja általában: részleges vagy parciális szegmentálás végrehajtása, melynek eredményét egy magasabb szintű feldolgozó rendszernek vetjük majd alá (intelligens, tudásbázisú feldolgozó rendszerek). Osztályozás: 1. Globális ismeretek alapján (hisztogram, vágás, osztályozás) 2. Él alapú szegmentálás 3. Régió alapú szegmentálás. 4.2. Szegmentálás globális ismeretek alapján Legegyszerűbb: intenzitásképre alkalmazunk egy vágást és kész a szegmentálás. Jó ez a módszer pl. arra, hogy elkülönítsük egy röntgen felvételből a csontokat a többi objektumtól. Ez is csak akkor jó, ha a csontok nem fedik egymást, merthogy a röntgen felvétel az egy vetület. Ha a csontok fedik egymást, akkor már nem tudjuk hatékonyan szétválasztani. Legalábbis így nem. Ettől függetlenül a vágást lehet használni. Sőt kell is. Vannak speciálisabb vágások. Vágási eljárások felsorolása következik: 1, ha f (i, j ) ≥ T , korábban THRESH-sel jelöltük. 0, ha f (i, j ) < T  f (i, j ), ha f (i, j ) ≥ T , korábban TRUNC-kal jelöltök Semi thresholding : g (i, j ) =  f (i, j ) < T  0, ha 1, ha f (i, j ) ∈ D , ahol D egy részhalmaza az Egyszerű osztályozás: g (i, j ) =  0, ha f (i, j ) ∉ D

Hagyományos vágás: g (i, j ) = 

értéktartománynak. k , ha f (i, j ) ∈ Dk , k = 1..n  n , azaz van több lehetséges 0, ha f (i, j ) ∉ U Dk  k =1 osztály. Alapfeltétel, hogy Dk ∩ Dl = ∅, ∀k ≠ l esetén. Ezt az osztályozást alkalmazza a

Komplikáltabb osztályozás: g (i, j ) = 

fuzzy osztályozó algoritmus is, de előbb megállapítja, hogy az osztályokhoz tartozó D halmazokhoz melyik elemek tartozzanak. Vágás alapkérdése: hogyan válasszuk meg a küszöbértéket? Válasz: optimálisan ☺. Használjuk a kép hisztogramját. Vegyünk egy egyszerűsített esetet: a kép tartalmaz egy objektumot meg egy hátteret. Mindkettőnek van egy átlagos színe, meg egy szórása, haranggörbeszerű eloszlással. A hisztogram tartalmazza mindkét szín árnyalatait. De mi csak a két görbe összegét látjuk. Optimális lenne az a küszöbérték, ahol a két szín két haranggörbéje metszi egymást a két csúcs között. Ha a hisztogramnak van két domináns csúcsa, akkor vehetjük a kettő közti minimumot küszöbértéknek (hogy minél kevesebb legyen a kérdéses képpontok száma), de ez egy konvencionális küszöbérték. Az optimális és a konvencionális küszöbérték jó

30

esetben nem tér el nagyon egymástól. De el lehet képzelni azt a legrosszabb esetet, amikor a két haranggörbe maximuma közel van egymáshoz és az összegüknek (a hisztogramnak) csak egy csúcsa van. Ilyenkor nem létezik a konvencionális küszöbérték.

Ez utóbbi esetben használjuk a következő iteratív algoritmust optimális küszöbérték számítására: Jelölés: B a háttér képpontok halmaza, O az objektum képpontok halmaza, f a teljes kép. # jelöli a halmaz számosságát (CARD függvény) 1. Inicializálás, a küszöbérték kezdetben legyen a kép átlagos intenzitásértéke: T

( t =0 )

= AVER( f ) =

∑ f (i, j )

( i , j )∈ f

#f

2. Átlagértékek számítása. Kiszámítjuk, hogy a pillanatnyi küszöb szerinti háttér, illetve objektum képpontoknak mennyi az átlagos intenzitásértéke: µ = AVER( B) = t B

3. Legyen T (t +1) =

(

∑ f (i, j )

( i , j )∈B

1 t µ B + µOt 2

#B

és µ = AVER(O) = t O

)

∑ f (i, j )

( i , j )∈O

#O

4. Ha T (t +1) = T (t ) , akkor az algoritmus leáll, különben visszaugrik a 2. pontra. A kapott küszöbérték úgy helyezkedik el, hogy a hisztogramban a tőle balra levő alakzat súlypontja, és a tőle jobbra levő alakzat súlypontja azonos távolságra legyen. Ez nem feltétlenül azonos a teljes hisztogram súlypontjával. 4.3. Globális szegmentálás fuzzy osztályozással Jelen módszer célja, hogy a képen található N db képpontot ossza szét c db osztály között úgy, és a c db osztálynak válasszon optimális intenzitásértéket úgy, hogy a szétosztás

31

optimális legyen, azaz minél jobban megfeleljen egy négyzetes kritériumfüggvény globális minimum értékének. Legyen c az osztályok száma, indexként használunk i-t vagy j-t; i,j=1…c Legyen q az eredeti képben az intenzitásértékek száma, indexként használjuk a l-et, l=1…q. Legyen N a képpontok száma, indexként használjuk k-t, k=1…N. Legyen γ l = [HIST(f)](l), azaz az eredeti képből az l-el megegyező intenzitású képpontok száma. Jelöljük vi -vel az i-dik osztályhoz tartozó prototípus színt, amit az algoritmus számol. Jelöljük uil -lel az l-el megegyező intenzitási képpontok i-dik osztályhoz viszonyított fuzzy c

tagsági függvényét. Értelemszerűen, definíció alapján: ∑ uil = 1 , bármely l=1…q esetén. i =1

Költségfüggvényünket a következőképpen vesszük fel: q

c

J = ∑∑ γ l uilp (l − vi ) 2 , i =1 l =1

ahol p egy konstans valós szám, konvergencia érdekében p>1. Ennek a költségfüggvénynek a minimumát keressük, szükségünk van egy Lagrange multiplikátor bevezetésére, azaz

[

]

q c c q   F = ∑∑ γ l uilp (l − vi ) 2 + ∑ λl 1 − ∑ uil  . l =1  i =1 i =1 l =1 

Ennek az első, dupla szummás tagja az eredeti költségfüggvény, a második szummás tagja pedig egyértelműen NULLA, de a deriválásoknál nagy szükségünk lesz rá. Deriváljuk a Lagrange multiplikátort uil és vi szerint, s a deriváltakat egyenlővé tesszük 0val. δF = pγ l uilp−1 (l − vi ) 2 − λl = 0 , δuil innen azt kapjuk, hogy 1

−2

 λ  p−1 uil =  l  (l − vi ) p−1 .  pγ l  c

Ezek után a ∑ uil = 1 feltétel segítségével kiküszöböljük a λl értéket, s kapjuk azt, hogy i =1

  c  l − vi uil = ∑   j =1 l − v j  

   

2 p −1

−1

   . 

A másik deriváltból a következőket kapjuk: −1 q q δF  q p  p p = −2 ⋅ ∑ (γ l uil (l − vi ) ) = 0 ⇒ vi =  ∑ γ l uil l  ∑ γ l uil  . δvi l =1  l =1  l =1  Ezek után fogalmazzuk meg az algoritmust:

32

1. Inicializálás: vi -ket egyenletesen szétszórjuk az kép intenzitás értéktartományában, az uil értékek kezdeti értéke legyen 1/c, hogy egyenletes legyen és eleget tegyen a feltételeknek. 2. Kiszámítjuk a hisztogramját az eredeti képnek, megkapjuk a γ l értékeit. 3. Kiszámítjuk a költségfüggvény értékét.  c  l −v i 4. Frissítjük a fuzzy tagsági függvények értékét: uil = ∑  j =1 l − v j  

   

2 p −1

−1

   , ahol i=1...c, l=1...q. 

5. Frissítjük az osztályokhoz hozzárendelt optimális színek értékeit: −1

  q  q vi =  ∑ γ l uilp l  ∑ γ l uilp  , , ahol i=1...c.   l =1  l =1

6. Kiszámítjuk újra a költségfüggvény értéket, s ha jelentősen csökkent, akkor visszaugrunk a 4. pontra, különben jön a 7. pont 7. Minden egyes l=1…q szín esetében megvizsgáljuk, hogy melyik i=1…c osztályhoz viszonyított tagsági függvénye a legnagyobb. Amelyik a legnagyobb, abba az osztályba fogjuk osztályozni az ilyen színű képpontokat. Eredmény: egy mágneses rezonanciás agyi metszet, 256 szín, 3 osztály esetén.

A színek konvergenciája:

Hatékony osztályozó algoritmus, nem csak képfeldolgozásban használják, hanem rengeteg tudományág kedvenc módszere. Feltalálóját Bezdek-nek hívják.

33

4.4. Szegmentálás a detektált élek alapján. Canny szűrő. A Canny szűrő egy 20 évvel ezelőtt keletkezett éldetektáló algoritmus. Alapvetően a lépései a következők: 1. előfeldolgozásként elvégezünk a képen egy simító szűrést, leginkább egy-egy Gauss szűrőt javasolnak erre a célra, külön függőleges és külön vízszintes irányban: cvSmooth(im1, im2, CV_GAUSSIAN,1,3) és cvSmooth(im1, im2, CV_GAUSSIAN,3,1). 2. Minden egyes képpont esetében kiszámoljuk a vízszintes és függőleges irány szerinti gradiens értékét. Ebből meghatározzuk a gradiens magnitúdóját (nagyságát), ami a két irány szerinti gradiens négyzetösszegének a négyzetgyöke. Szintén meghatározzuk a gradiens vektor irányát minden egyes képpontban. Ez a függőleges és a vízszintes irány szerinti gradiensek arányának arctangense szerint számolódik, figyelembe véve a komponensek előjelét. A legalkalmasabb erre a célra az atan2() függvény használata. 3. Nem maximális intenzitású élek eltávolítása (Nonmaximum suppression). Minden egyes képpontban van a gradiensnek egy iránya. Erre az irányra merőleges az az él, ami átmegy a képponton. Az él kép oldalán levő szomszédos képpontokban számított gradiens magnitúdó értékeket összehasonlítjuk az aktuális képpontban számított gradienssel, s ha valamelyik szomszéd gradiense nagyobb akkor az aktuális képpontot eltávolítjuk az élek közül. Így csak azok az élek maradnak meg a képen, amelyek a saját közvetlen szomszédságukban maximális intenzitásúak. 4. Hiszterézis: kettős küszöbértékkel vágjuk az előző lépésben kapott élekből álló képet. Adott T1 és T2 küszöbértékek. Minden olyan élpontot megtartunk, amelynek gradiense nagyobb vagy egyenlő a nagyobbik küszöbnél (T2). Ezek után rekurzívan keresünk olyan élpontokat, amelyek gradiense nagyobb vagy egyenlő mint a kisebbik küszöb (T1) és van már megtartásra bejelölt élpont a szomszédságukban. Az összes megmaradó be nem jelölt élpontot töröljük. Canny javaslata szerint T2/T1 értéke 2 és 3 között kell legyen. Utófeldolgozás Canny szűrőjéhez Canny szűrője egy képpontnyi vastagságú éleket talál a képen, de ezek az élek általában szakadozottak. Régiók bejelölésére egy utófeldolgozást lehet alkalmazni. Ennek lépései a következők: 1. A szakadozott élekből álló képen, minden élpontból az élre merőlegesen kiindulva keresünk egy maximum M távolságra levő másik élpontot, amely egy olyan élen helyezkedik el, amely a kiindulási élpont élével inkább párhuzamos mint merőleges (a két él érintője által bezárt szög 0…45 fok vagy 135…180 fok között van, azaz a szög szinusza kisebb mint 0.707). Ha találunk ilyen szomszédos élpontot, akkor az útba ejtett összes képpontnak adunk egy markert. 2. Miután minden élpontból megpróbáltunk szomszédos élpontot keresni, kiszámítjuk, hogy melyik képpontnak hány markere van. Jelöljük b(x)-el az x képpont markereinek számát. 3. A b(x) értékekből számolunk egy újabb változót, B(x)-et. Így: if (b(x)<=2) B(x)=0.1*b(x); else if (b(x)==3) B(x)=0.5; else if (b(x)>3) B(x)=1.0; else cout << „elkúrtad! Nem kicsit, nagyon”.

34

4. Jelöljük Nx-el az x képpont 3x3-as szomszédságát. Az x képpont akkor fog a régió belsejébe tartozni, ha:

∑ B( x) ≥ 1.0

y∈N x

Azaz, ha a 3x3-as szomszédságban levő B(x)-ek összege legalább 1, akkor van régión belül. Hough Transzformáció A Hough féle transzformáció egy olyan eljárás, mellyel egyeneseket, köröket és egyéb analitikus egyenlettel rendelkező alakzatokat lehet egy képen detektálni. Előnye, hogy a szakadozott élek nem zavarják. Egyenes detektálása Hough transzformációval: Az egyenes analitikai egyenlete y=ax+b, vagy inkább poláris koordináták szerint x cos θ + y sin θ = r . Ez utóbbi képletben r az origóból az egyeneshez húzott merőleges hossza, θ pedig a merőleges és az Ox tengely által bezárt szög. Mindez le volt rajzolva a táblán. Hough megfigyelte, hogy ha az egyenest nem az xy síkban, hanem az rθ síkban ábrázolja, annak képe egyetlen pont lesz. Ebből kiindulva alkotta meg Hough az egyenes detektálásának algoritmusát. Ennek lépései: 1. Az eredeti képen lefuttatunk egy éldetektáló algoritmust (pl. Canny szűrő). Ez lesz az előfeldolgozás, melynek során kapunk egy képet, melyen sok szakadozott él lesz. 2. Felrajzoljuk az rθ síkot, és kvantáljuk mindkét mennyiséget, pl. az r távolságot képpontban, a θ szöget fokban. Elkészítünk egy 2-D táblázatot, melyben minden egyes rekesz (cella) egy adott r és egy adott θ kvantált értéknek felel meg. 3. Sorba vesszük az éleket tartalmazó kép élpontjait, és a rajta potenciálisan áthaladható összes egyenest (minden ponton keresztülhalad 180 db egyenes, ha θ -t fokonként kvantáltuk). Minden ilyen egyenes Hough transzformáltja egy pont lesz. Minden ilyen pont után az rθ síkban a neki megfelelő cellában elhelyezünk egy markert23. 4. Miután minden ilyen élponton végigmentünk, megkeressük, hogy az rθ sík melyik cellájában van a legtöbb marker. Ennek a cellának megfelelő egyenes lesz a legrelevánsabb az eredeti képen a Hough transzformáció szerint. Amennyiben kör detektálása a célunk, akkor annak az egyenletéből indulunk ki: ( x − a) 2 + ( y − b)2 = ρ 2 = r , ahol a és b meghatározza a kör közepét, ρ pedig a kör sugara. Ennek megfelelően a Hough transzformált sík helyett 3-D terünk lesz, melynek dimenziói az a, b és r. Minden potenciális körnek az eredeti síkban megfelel egy pont a Hough transzformált térben, melynek koordinátái (a,b,r). Az eljárás elvileg ugyanaz mint az előbb, gyakorlatilag abban különbözik, hogy az éldetektált kép élpontjainak minden pontjára a potenciálisan jelen lehető összes kört kell figyelembe vennünk és transzformálnunk a Hough térbe. A kvantált Hough tér cellái közül megint azt választjuk ki, melynek a legtöbb markere van. Ennek alapján be tudjuk rajzolni az eredeti képre a detektált, szakadozásmentes kört.

23

piros pont

35

Ha egy adott sugarú kört keresünk, akkor a Hough térből kihagyhatjuk az r dimenziót, s így csak ab síkunk lesz. A módszer ellipszisre is működik, de annak két sugara van, s ugyanakkor figyelembe kell venni azt is, hogy az ellipszis el lehet fordulva egy ϕ szöggel a vízszintes és függőleges tengelyekhez viszonyítva. Így mindenképpen több mint 2 dimenziós lesz a Hough tér24. Az általánosított Hough transzformáció megoldja az analitikusan le nem írható alakzatok felismerését. A részleteket 80 évre titkosítottam… 4.5. Régió alapú szegmentálás Régiónak nevezzük a kép azon összefüggő részeit (foltjait), melynek képpontjai valamely szempontból homogén közeget alkotnak. Homogén minden olyan folt, melynek képpontjai eleget tesznek a homogenitási kritérium feltételének. Egy kép akkor van sikeresen szegmentálva, amikor teljesülnek az alábbi feltételek: 1. H ( Ri ) = true , bármely i=1,2,…S esetén 2. H ( Ri ∪ R j ) = false , bármely Ri és Rj szomszédos folt esetén Egyesítés módszere: Egyik legegyszerűbb módszer a régió alapú szegmentálásra a következő: 1. Osszuk fel a képet olyan apró darabjaira, amelyek már biztosan homogének 2. Definiáljunk egy egyesítési kritériumot (homogenitás vizsgálat alapján) 3. Párosával egyesítgetjük a régiókat, ha eleget tesznek a feltételnek. 4. Amikor már nincs amit egyesítgetni, akkor kész a szegmentálás. A módszer implementálásához használatos adatstruktúra az ún. szuperháló, angolul supergrid, lásd alább:

Ebben a struktúrában az X jelöli a képpontokat, az üres karika (○) a régiók (kezdetben képpontok) közötti élet, míg a sötét karika (●) mezőket nem használjuk. Amikor két régiót egyesítünk, akkor eltüntetjük a közöttük levő éleket. Minden egyes él (○) rendelkezik egy tulajdonsággal: az ő két oldalán levő képpont színe (szürke intenzitása) közötti abszolút különbség függvényében minden él lehet gyenge vagy erős. Ezek után a régiók egyesítéseinek kritériumai a következők lehetnek: Ettől nem kell megijedni, a Hough tér háromnál több dimenziós is lehet. A számítógép nekünk ezt jól lekezeli, esetleg több ideig számol. 24

36

1. Az Ri és Rj régiókat akkor egyesíthetjük, ha W ≥ T1 min(li , l j )

ahol li és lj a két régió kerülete (a körülöttük levő élpontok száma), W a közös határon levő gyenge élpontok száma, T1 pedig ez küszöbérték. 2. Az Ri és Rj régiókat akkor egyesíthetjük, ha W ≥ T2 , l

ahol l a közös határ hossza, T2 pedig ez küszöbérték. 3. Az Ri és Rj régiókat akkor egyesíthetjük, ha W ≥ T3 , ahol l a közös határ hossza, T3 pedig ez küszöbérték. Minden egyesítés után megvizsgálandó, hogy kell-e takarítani: pl. ha egyesítettük R1-et R2vel, majd R3-at R4-el, ezek után rájövünk, hogy ezek mind egyesíthetők az R2 és R3 közötti határ eltüntetésével. Ezek után meg kell vizsgálni, hogy például az R1 és R4 közös határvonala le lett-e törölve, mert ha nem akkor le kell törölni. Felosztás módszere: Ez a módszer abból indul ki, hogy a teljes kép egy régió és addig osztja darabjaira, míg a darabok mind homogének lesznek. A módszer nagyon körülményes, mert minden egyes kettéosztásnál rengeteg lehetséges felosztás közül kell az optimálisat választani. A rengeteg eset megvizsgálása sok időbe telik, ezért a módszer lassú. Felosztás és egyesítés módszere: Ez a módszer sem a gyorsaságáról híres, de a laborban látottakhoz képest még jelentősen fel lehet gyorsítani ☺ Mindenek előtt ki kell találni egy homogenitási kritériumot, amivel meg tudjuk állapítani a kép bármelyik foltjáról, hogy homogén-e. Kiindulásként négyzet alakú képet használunk, melynek szélessége és hossza 2 hatványa kell legyen (pl. 256x256 képpont). Ha ennek a feltételnek nem felel meg a kép, akkor ki kell egészíteni alul és/vagy jobb oldalon. Ha ezek megvannak, akkor egy hierarchikus struktúrát, egy úgynevezett kvadrikus fát hozunk létre, amelyben nyilvántarthatjuk a felosztás során keletkező régiókat. A felosztás algoritmus a következő: Megnézzük, hogy a teljes kép homogén-e? Ha igen, akkor a teljes kép egy régió, ha nem akkor vízszintesen és függőlegesen kettévágjuk középen, és mind a 4 keletkező részt alávetünk ennek a homogenitási vizsgálatnak. Amelyik rész homogén, azt kinevezzük régiónak, amelyik nem homogén azt tovább bontjuk további 4 egyforma részre. Ezt mindaddig folytatjuk, amíg minden darabka homogén nem lesz. Biztosan találunk homogén részeket akkor, amikor a régió csak egy képpontból áll (egy képpont önmagában garantáltan homogén). Felosztás során egy ilyen struktúrát kapunk végeredményként:

37

A felosztás egy nagyon gyors művelet, az egyesítéshez viszonyítva az időtartam teljesen elhanyagolható. A felosztás során keletkező régiókat felírjuk egy listára. Az egyesítés a következő algoritmus szerint működik: A régiók listáján keresünk olyan régió párokat, amelyek szomszédosak. Ha találtunk szomszédos régiókat, megvizsgáljuk a homogenitási kritérium segítségével, hogy ha egyesítenénk őket, akkor együttesen homogének lennének-e? Ha igen, akkor egyesítjük őket. Ezután újabb szomszédos régió párost keresünk, stb… Amikor végigjártuk a teljes listát és nem találtunk egyesíthető párost, akkor vége van az egyesítésnek. Utófeldolgozás: a nagyon kis méretű régiókat egyesítjük nagyobb szomszédaik közül azzal, amelyikhez a leginkább illeszkednek homogenitás szempontjából. Víztárolók módszere (watershed) A víztárolók módszere szintén egy régió alapú szegmentáló módszer. Célja: intenzitás képet szegmentálni homogén régióira. Lépései: 0. Előfeldolgozás: valamely simító szűrő alkalmazása szükséges (átlagoló, medián, stb.) 1. Számítsuk ki az eredeti kép gradiens képét, melyben minden képpont intenzitása egyenlő az eredeti kép adott képpontjában számított gradiens amplitúdójával. Ezt számíthatjuk bármely gradiens számító maszk páros segítségével, és a két komponensből amplitúdót számolhatunk bármely norma szerint. Javasolom a másodrendű normát kombinálni a Prewitt vagy Sobel maszkokkal. 2. Tekintsük ezt a gradiens képet mint egy domborzati térképet, melyen a gradiens nagysága jelenti a tengerszint feletti magasságot. 3. A domborzati térkép minden lokális minimumába25 vízvezetéket szerelünk és a föld alatt összekötjük őket úgy, hogy egyetlen közlekedő edényt alkossanak. 4. Elkezdjük feltölteni a közlekedő edényeket. Ahogy emelkedik a vízszint, egyre több lokális minimumban megjelenik a víz, tó keletkezik.

25

Azért kellett az előfeldolgozás, hogy ne legyen olyan rahedli sok lokális minimumunk

38

5. Egyre inkább emeljük a vízszintet. 26 Közben egyes tavak úgy megnőnek, hogy elkezdenének egybefolyni. Ahol a vizek találkoznak, azokban a pontokban végtelen magas gátat emelünk. 6. Addig emeljük a vízszintet, amíg az összes hegyet ellepi a víz. Ekkor a szegmentálás befejeződött, az általunk emelt gátak lesznek a régiók határvonalai. 7. Ekkor indult útra Noé a bárkájával27.

5. 3D Felületmodellek A sétáló kocka módszere 3D felületek képzésére Megjegyzés: az alábbi bemutatás nem taglalja a fekete, illetve fehér képpontok közötti demokrácia kérdését. Ha valaki precíz sétáló kockát akar, ezt a leírást pontosítani kell. Az alapelveket viszont ebből is el lehet sajátíthatani. Van amikor nem csak egy darab 2D képet dolgozunk fel. Például amikor az orvosok komputertomográfiát alkalmaznak egy emberi szerv belső szerkezetének vizsgálatára, akkor párhuzamos keresztmetszeteket készítenek a vizsgált szervről. Például a mágneses rezonanciás agyi vizsgálatnál 256x256 képpont méretű, 256 szürke árnyalatú intenzitásképeket készítenek, kb. 150-250 darabot. Ezeket a 2D keresztmetszeteket egyenként szegmentálhatjuk, pl. a fuzzy módszerrel. Viszont a 2D szeletek közötti összefüggéseket jobban átlátjuk, ha fel tudjuk építeni és meg tudjuk jeleníteni a háromdimenziós felületeket, pl. a fehér állomány külső felületét, vagy a fehér- és szürkeállomány közötti határfelületet. A 3D felületmodellek közül az egyik legegyszerűbb a sétáló kocka módszere. A módszer alapelve az, hogy a vizsgált térrészt kis kockákra osztja, majd minden egyes kis kockában eldönti, hogy milyen felület elemek vannak jelen. Természetesen arra is kell vigyáznia, hogy az egymás melletti kockákban levő felületelemek illeszkedjenek egymáshoz. De mi is az a kis kocka? Nézzük az alábbi ábrát. Tekintsünk két egymás utáni, azaz szomszédos keresztmetszetet. Mindkettőből kiválasztunk négy-négy szomszédos képpontot. Amennyiben ezeket úgy választottuk, hogy egymás alattiak vagy felettiek, a nyolc kiválasztott képpont egy kis kocka csúcsai lesznek.

26 27

Aki fél a mély víztől, forduljon bizalommal Gátvéderhez. Azt a rohadt fakopáncsot otthagyhatta volna…

39

A kocka csúcspontjai a 2D szegmentálás után lehetnek feketék vagy fehérek, annak függvényében a régión belül vagy kívül helyezkednek el. Tegyük fel, hogy a fekete régió külső falát keressük, így a fekete képpontok vannak a régión belül, a fehérek pedig kívül. A kockának 8 csúcspontja van, ezek mindegyike egymástól függetlenül lehet fekete vagy fehér. Ez azt jelenti, hogy összesen van 28, azaz 256 esetünk, amelyeket 0..255 közötti számokkal jelölhetünk. Például az alábbi ábrán láthatjuk a 11-es (bináris 00001011) és a 244-es (bináris 11110100) eseteket.

Az említett 256 eset közül mindegyiknek megfelel bizonyos véges számú felületelem (háromszög). De a szimmetria miatt nincs 256 teljesen különböző esetünk. Például minden esetnek van egy komplemense (a fenti ábrán a 244 komplemense a 11). A fekete és fehér régiók közötti határfelület ugyanaz, mint a fehérek és feketék közötti határ, tehát e két esetnek ugyanazok a háromszögek fognak megfelelni. De a szimmetria miatt az esetek száma nemcsak megfeleződik, hanem lecsökkenthető lesz 14-re. Lásd az alábbi teljes oldalas ábrán. Megfigyelhető, hogy minden esetben amikor a kocka egy élének egyik végén fekete képpont van, a másikon meg fehér, akkor az élen található egy felületelem (háromszög) csúcspontja. Amikor az él mindkét végén azonos színű képpont van, akkor az élet a háromszögek elkerülik. Mi garantálja, hogy a felület elemek jól illeszkedjenek egymáshoz? Az, hogy ugyanaz az él szerepel négy szomszédos kockában, és ugyanannak az élnek ugyanolyan színűek a végpontjai mind a négy kockában. Tehát ha háromszög érint égy élet az egyik kockában akkor a másik szomszédos kockákban is fogják érinteni.

40

Ha a teljes vizsgált térrészben megállapítottuk a jelen levő háromszögeket, akkor azokat meg kell tudni jeleníteni valahogyan. A háromszögek térbeli megjelenítéséhez OpenGL technológiát érdemes használni. Egy-egy nézet előállításánál fontos eldönteni, hogy:

41

1. Melyik háromszög látszik és melyik nem, ha egy adott helyről egy adott irányba nézünk. Ezt megteszi helyettünk az OpenGL. 2. A megjelenítést érdemes perspektivikus ábrázolással készíteni, így a távoli háromszögek kisebbek lesznek a közelieknél. Ezt is megteszi az OpenGL, ha jól állítjuk be a dolgokat. 3. Ahhoz, hogy valamit lássunk is az ábrán, a háromszögeket ki kell színezni, azaz kell adni nekik egy szürke árnyalatot. Például Phong színezési algoritmusa szerint egy háromszög színe attól függ, hogy a háromszög síkja és a nézési irányunk hány fokos szöget zár be egymással. Ha merőlegesen nézünk egy síkra, akkor az fehér kell legyen, ha párhuzamosan nézünk a síkkal akkor az fekete azaz egyáltalán nem látszik. A köztes szögeket pedig ki lehet színezni a bezárt szög szinuszával arányosan (vagy a normálvektor és nézetvektor bezárt szögének koszinuszával arányosan). Erről röviden ennyit.

42