´ ¨ O ˝ ALGORITMUSOK A VAZKIJEL OL ´ ´ ´ DIGITALIS KEPFELDOLGOZ ASBAN
Fazekas Attila Debrecen ¨ Osszefoglal´ as: A digit´ alis k´ epfeldolgoz´ asban vonalas ´ abr´ ak feldolgoz´ asa sor´ an gyakran haszn´ alatos a v´ azkijel¨ ol´ es. Ez a m´ odszer a saj´ ats´ agok kinyer´ es´ et seg´ıti el˝ o azzal, hogy el˝ otte a k´ epet a feldolgoz´ as szempontj´ ab´ ol kedvez˝ obb alakra hozza. Ebben a dolgozatban egy r¨ ovid ´ attekint´ est adunk az irodalomban tal´ alhat´ o k¨ ul¨ onb¨ oz˝ o algoritmusokr´ ol, a v´ azkijel¨ ol´ es matematikai h´ atter´ er˝ ol ´ es az ezzel kapcsolatos alapvet˝ o fogalmakr´ ol.
´s Bevezete A digit´alis k´epfeldolgoz´ as k¨ ozel hetven ´eves m´ ulttal rendelkezik. A kezdeti probl´em´ak a digit´ alis k´epek ´ atvitele sor´ an ad´ odtak. Az 1920-as ´evekt˝ol kezd˝od˝oen a haszn´alt technik´ ak fejl˝ od´es´eben nagy v´ altoz´ast az u ˝rprogram hozott. A digit´alis k´epfeldolgoz´asi technik´ akat az´ ota m´ as ter¨ uleteken is haszn´alj´ak. P´eldak´ent az orvosi, ipari, katonai ´es hum´ an alkalmaz´ asokat eml´ıthetj¨ uk [3,10,24]. A digit´alis k´epfeldolgoz´ asi elj´ ar´ asok alkalmaz´asuk szempontj´ab´ol k´et alapvet˝o csoportba sorolhat´ ok. Az egyik csoport a k´epi inform´aci´ok ´atalak´ıt´asa emberi feldolgoz´as sz´am´ara kedvez˝ obb alakra. A m´ asik az ¨on´all´o g´epi felismer´es megval´os´ıt´asa. Az automatikus g´epi felismer´est megval´ os´ıt´o m´odszereket a szakirodalomban alapvet˝oen h´arom nagy csoportba sorolj´ ak [5]. Term´eszetesen az egyes csoportok k¨oz¨ott nem lehet ´eles hat´ arvonalakat h´ uzni. Ez a csoportos´ıt´as a felismer´es folyamat´at is t¨ ukr¨ozi. Most tekints¨ uk r¨ oviden ´ at ezeket a csoportokat: • K´eptranszform´ aci´ o. Ezen elj´ ar´ asok a digit´alis k´epen tal´alhat´o k´eppontok tulajdons´agai (pl. vil´ agoss´ aguk) alapj´ an az eredeti k´epb˝ol egy m´asik digit´alis k´epet (az u ´n. transzform´ alt k´epet) ´ all´ıtanak el˝o. • K´epelemz´es. Az egyes objektumpontok egy¨ uttes tulajdons´agai alapj´an az ´altaluk alkotott objektum, illetve h´ att´er komponens legfontosabb jellemz˝oit ´all´ıtj´ak el˝ o. Ezeket a jellemz˝ oket saj´ ats´agoknak is nevezik. • K´epfelismer´es. A saj´ ats´ agok ismeret´eben egy tud´asb´azis seg´ıts´eg´evel felis” merik” a k´epen l´ athat´ o objektumo(ka)t. Egy objektum felbont´ asa egyszer˝ ubb ´es kisebb objektumokk´a gyakran hasznos a digit´alis k´epfeldolgoz´ asban. A karakterfelismer´esben — amely az alakfelismer´es Kulcsszavak: Dilation, erosion, hit/miss transform, mathematical morphology, medial axis, skeleton, thinnig, relaxation, contour processing algorithm, templates. Az OTKA 1994/895. ´ es MKM 442/94 t´ amogat´ as´ aval k´ esz¨ ult Typeset by AMS-TEX
1
2
FAZEKAS ATTILA
egy r´eszter¨ ulete — gyakran haszn´ alnak erre a c´elra egy speci´alis technik´at, a v´azkijel¨ol´est. Ez egy olyan speci´ alis k´epelemz˝o algoritmus, amelyik a digit´alis k´epet a saj´ats´agok kinyer´es´ehez kedvez˝ obb alakra alak´ıtja ´at. Az objektum vonalait, foltvonalait egy pixel vastags´ ag´ u vonallal helyettes´ıti, amely megk¨ozel´ıt˝oleg az eredeti foltvonal k¨ oz´epvonala. Ez a m´ odszer ny´ılv´anval´oan vonalas” ´abr´ak eset´en ” alkalmazhat´o sikeresen. A v´az kifejezi az eredeti objektum f˝ o komponensei k¨oz¨otti szerkezeti ¨osszef¨ ugg´eseket. Ez azt eredm´enyezi, hogy a tov´abbi feldolgoz´ast a v´azzal v´egezhetj¨ uk. Ezzel a felhaszn´ alt mem´ ori´ at cs¨ okkenthetj¨ uk, az alakfelismer´eshez sz¨ uks´eges adatszerkezetet egyszer˝ us´ıthetj¨ uk. Term´eszetesen cs¨okken a feldolgoz´asi id˝o is. A v´azkijel¨ol˝o algoritmusok ´ altal´ aban digitaliz´alt, k´etszint˝ u k´epet v´arnak bemenetk´ent ´es ugyanilyen t´ıpus´ u k´epet adnak eredm´eny¨ ul. Ebben a cikkben egy rendszerez˝ o jelleg˝ u ´ attekint´est k´ıv´anunk adni a v´azkijel¨ol´es irodalm´ar´ol. R¨ ogz´ıtj¨ uk ezen t´emak¨ or megismer´es´ehez sz¨ uks´eges matematikai modelleket ´es fogalmakat. Az els˝ o fejezetben a legfontosabb matematikai ismereteket foglaljuk ¨ossze. A tov´ abbi fejezetekben a csoportos´ıt´as alapj´at a felhaszn´alt matematikai m´odszer, illetve modell adja. A fejezetek sorrendje megk¨ozel´ıt˝oleg az egyes m´odszerek id˝ obeli sorrendj´et is jelenti. Ebben a t´emak¨ orben hatalmas t¨ omeg˝ u publik´aci´o jelenik meg ´evente. Ehhez k´epest nagyon eleny´esz˝ o sz´ amban jelenik meg ¨ osszefoglal´o, ¨osszehasonl´ıt´o ´es ´attekint˝o jelleg˝ u cikk [17,33]. Tudom´ asunk szerint magyar nyelven ilyen jelleg˝ u munka kor´abban nem jelent meg. Ezt a hi´ anyt szeretn´enk p´otolni munk´ankkal, amely el˝oseg´ıtheti a magyar szakkifejez´esek elterjed´es´et is. ˝ fogalmak 1. Alapveto 1.1. Defin´ıci´ o. A Z 2 halmazt digit´ alis s´ıknak, elemeit k´ eppontoknak (vagy r¨ oviden pontoknak) nevezz¨ uk. A digit´ alis s´ık egy v´eges r´eszhalmaz´ at digit´ alis halmaznak nevezz¨ uk. Egy D digit´ alis halmaz feletti n-szint˝ u digit´ alis k´ ep alatt egy olyan f f¨ uggv´enyt ´ert¨ unk, amely a D-t a R = {0, 1, · · · , n − 1} halmazba k´epezi. A R halmaz elemeit vil´ agoss´ agk´ odoknak nevezz¨ uk. Az n = 2 eset´en a bin´ aris k´ ep elnevez´es is haszn´ alatos. Egy f bin´ aris k´ep el˝ oter´en az F = {P ∈ D|f (P ) = 1}, a h´ atter´en a B = {P ∈ D|f (P ) = 0} halmazt ´ertj¨ uk. Az el˝ ot´er pontjait objektumpontoknak, a h´ att´er pontjait h´ att´ erpontoknak nevezz¨ uk. 1.2. Jel¨ ol´ es. A k´es˝ obbiekben, ha egy digit´ alis halmaz P pontj´ anak koordin´ at´ ait is fel k´ıv´ anjuk t¨ untetni, akkor azt a P (i, j) alakban fogjuk megtenni. 1.3. Defin´ıci´ o. Legyen P (i, j) ´es Q(k, l) ugyanazon digit´ alis halmaz k´et pontja. A Q a P 4-szomsz´ edja, ha a koordin´ at´ akra teljes¨ ul, hogy |i − k| + |j − l| = 1. A 4-szomsz´ed helyett haszn´ alhatjuk a k¨ ozvetlen szomsz´ ed elnevez´est is. Ha a koordin´ at´ akra a fenti egyenl˝ os´eg helyett az |i − k| = |j − l| = 1 teljes¨ ul, akkor a Q a P k¨ ozvetett szomsz´ edja. A k¨ ozvetlen ´es k¨ ozvetett szomsz´edokat egy¨ uttesen 8-szomsz´ edoknak nevezz¨ uk.
´ ¨ O ˝ ALGORITMUSOK A DIGITALIS ´ ´ ´ VAZKIJEL OL KEPFELDOLGOZ ASBAN
3
Az irodalomban ´ altal´ anos m´ odszer a D, F ´es B digit´alis halmazok szeml´eltet´es´ere az al´abbi grafikus reprezent´ aci´ o:
1. ´ abra
Ahol ◦ a h´att´erpontokat, • az objektumpontokat ´es ezek egy¨ uttesen a vizsg´alt digit´alis halmaz pontjait jel¨ olik. Most tekints¨ unk egy egyszer˝ u p´eld´ at a fenti fogalmak szeml´eltet´es´ere. Legyen a D digit´alis halmaz a k¨ ovetkez˝ ok´eppen defini´ alva: D = {(0, 0), (1, 0), (2, 0), (3, 0), (4, 0), (0, 1), (1, 1), (2, 1), (3, 1), (4, 1), (4, 2), (3, 3), (4, 3), (3, 4), (4, 4)}. Legyen f egy D feletti bin´aris k´ep, amely rendelkezik a k¨ ovetkez˝o tulajdons´aggal: ∀P ∈ D eset´en f (P (x, y)) =
1
, ha |x − y| ≤ 2
0
, egy´ebk´ent.
Ekkor az f bin´ aris k´ep el˝ otere az F = {(0, 0), (1, 0), (2, 0), (0, 1), (1, 1), (2, 1), (3, 1), (4, 2), (3, 3), (4, 3), (3, 4), (4, 4)} digit´ alis halmaz lesz. Ny´ılv´anval´oan a h´att´ert a B = D \ F = {(3, 0), (4, 0), (4, 1)} ¨ osszef¨ ugg´essel kaphatjuk meg. A (3, 1) koordin´ at´ aj´ u pont k¨ ozvetett szomsz´edja a (4, 2) koordin´at´aj´ u pontnak. A (0, 0) koordin´ at´ aj´ u pont k¨ ozvetlen szomsz´edja a (0, 1) koordin´at´aj´ u pontnak. Egy P pont 8-szomsz´edainak (4-szomsz´edainak) halmaz´at N8 (P )-vel (N4 (P )-vel) szok´as jel¨olni. P´eld´aul: N4 (P (3, 1)) = {(2, 1), (3, 0), (4, 1)} ´es N8 (P (3, 1)) = {(2, 1), (2, 0), (3, 0), (4, 0), (4, 1), (4, 2)}. Ny´ılv´anval´oan, ha P ´es Q egy D digit´ alis halmaz pontjai ´es P 8-szomsz´edja (4szomsz´edja) Q-nak, akkor Q is 8-szomsz´edja (4-szomsz´edja) P -nek. 1.4. Defin´ıci´ o. Legyen U ´es V digit´ alis halmaz. Az U -t a V 8-szomsz´ edj´ anak (4-szomsz´edj´ anak) nevezz¨ uk, ha ∃P ∈ U ´es ∃Q ∈ V u ´gy, hogy P 8-szomsz´edja (4-szomsz´edja) Q-nak az U ∪ V halmazon. 1.5. Defin´ıci´ o. Legyen D egy digit´ alis halmaz, X ´es Y annak tetsz˝ oleges pontja. Egy n (n ∈ N ∪ {0}) hossz´ us´ ag´ u X-b˝ ol Y -ba tart´ o 8-´ utnak (4-´ utnak) nevez¨ unk egy olyan X = X0 , X1 , · · · , Xn−1 = Y pontsorozatot, melyben Xi 8-szomsz´edja (4-szomsz´edja) Xi−1 -nek (0 < i ≤ n − 1) ´es Xi ∈ D. A kor´abbi p´eld´ ank jel¨ ol´eseit felhaszn´ alva az F halmazt bontsuk fel a k¨ovetkez˝ok´eppen: U = {(0, 0), (1, 0), (2, 0), (0, 1), (1, 1), (2, 1), (3, 1)}, V = {(4, 2), (3, 3), (4, 3),
4
FAZEKAS ATTILA
(3, 4), (4, 4)}. Az U a V 8-szomsz´edja lesz, mert P (3, 1) ∈ U , Q(4, 2) ∈ V ´es P 8-szomsz´edja Q-nak. K¨ onnyen ellen˝ orizhet˝o, hogy U nem 4-szomsz´edja V -nek. Nyilv´anval´oan, ha U 8-szomsz´edja (4-szomsz´edja) V -nek, akkor V is 8-szomsz´edja (4-szomsz´edja) U -nak. P´eldak´ent keress¨ unk egy olyan 8-utat amelyik a (2, 1) koordin´at´aj´ u pontot a (4, 3) koordin´at´aj´ u ponttal k¨ oti ¨ ossze. Az egyik lehets´eges megold´as a (2, 1), (3, 1), (4, 2), (4, 3) pontsorozat. Azonban eset¨ unkben 4-´ ut nem l´etezik. Vegy¨ uk ´eszre, hogy tetsz˝oleges digit´ alis halmaz k´et pontja eset´en, ha l´etezik az egyikb˝ol a m´asikba tart´o 8-´ ut (4-´ ut), akkor a m´ asikb´ ol az egyikbe tart´o is l´etezik. A p´eld´ankban a (4, 3), (4, 2), (3, 1), (2, 1) pontsorozat a (4, 3) koordin´at´aj´ u pontot a (2, 1) ponttal ¨osszek¨ot˝o 8-´ ut. 1.6. Defin´ıci´ o. Legyen D egy digit´ alis halmaz, X ´es Y ennek pontjai. Az X pontot 8-ir´ anyban (4-ir´ anyban) ¨ osszef¨ ugg˝ onek nevezz¨ uk Y -nal, ha l´etezik egy az X-et az Y -nal ¨ osszek¨ ot˝ o 8-´ ut (4-´ ut). A kor´abbi p´elda alapj´ an a (2, 1) koordin´ at´aj´ u pont 8-ir´anyban ¨osszef¨ ugg˝o a (4, 3) koordin´at´aj´ u ponttal. Azonban 4-ir´ anyban nem ¨osszef¨ ugg˝o. Fontos megjegyezni, hogy ha X ´es Y valamely digit´ alis halmaz pontjai, ´es X 4-ir´anyban ¨osszef¨ ugg˝o Y -nal, akkor 8-ir´ anyban is. 1.7. Defin´ıci´ o. Legyen X a D digit´ alis halmaz pontja. Az X 8-komponens´et a k¨ ovetkez˝ ok´eppen defini´ aljuk: 8 KD (X) = {Y |Y ∈ D ´es Y 8-¨ osszef¨ ugg˝ o az X ponttal}. 1.8. Defin´ıci´ o. Legyen X a D digit´ alis halmaz pontja. Az X 4-komponens´et a k¨ ovetkez˝ ok´eppen defini´ aljuk: 4 KD (X) = {Y |Y ∈ D ´es Y 4-¨ osszef¨ ugg˝ o az X ponttal}. 1.9. Defin´ıci´ o. Konstru´ aljuk meg egy D digit´ alis halmaz minden X pontj´ ahoz a 8 4 KD (X) (KD (X)) halmazt. Ezen halmazok k¨ oz¨ ul a p´ aronk´ent diszjunktakat a D 8-komponenseinek (4-komponenseinek) nevezz¨ uk. 1.10. Defin´ıci´ o. A D digit´ alis halmazt 8-¨ osszef¨ ugg˝ onek (4-¨ osszef¨ ugg˝ onek) ne8 4 vezz¨ uk, ha minden P pontja eset´en KD (P ) = D (KD (P ) = D) teljes¨ ul. Visszat´erve a kor´ abbi p´eld´ ankhoz ´es annak jel¨ol´eseihez a k¨ovetkez˝o meg´allap´ıt´asokat 8 4 4 8 (P (4, 3)) = V . (P (2, 1)) = U ´es KD (P (4, 3)) = F , KD tehetj¨ uk: KD (P (2, 1)) = KD Ezek alapj´an a D egyetlen 8-komponensb˝ ol ´all, ´es ´ıgy 8-¨osszef¨ ugg˝o. Azonban nem 4-¨osszef¨ ugg˝o, mert k´et 4-komponense van, nevezetesen U ´es V . 1.11. Defin´ıci´ o. Egy D digit´ alis halmazt ablaknak nevez¨ unk, ha l´etezik A(k, l) ´es B(m, n) pontja, u ´gy, hogy a D el˝ o´ all a k¨ ovetkez˝ o alakban: D = {X(i, j)|i = k, k + 1, · · · , m; j = l, l + 1, · · · , n}. Az A pontot az ablak balfels˝ o, a B pontot az ablak jobbals´ o sark´ anak nevezz¨ uk. Az ablak keret´en az L = {X(i, j)|i = k + p, j = l + q} halmazt ´ertj¨ uk, ahol p ∈ {0, m − k} ´es q ∈ {0, n − l}. 1.12. Defin´ıci´ o. Egy D digit´ alis halmaz ´ altal kifesz´ıtett ablak alatt a D-t tartalmaz´ o legsz˝ ukebb ablakot ´ertj¨ uk.
´ ¨ O ˝ ALGORITMUSOK A DIGITALIS ´ ´ ´ VAZKIJEL OL KEPFELDOLGOZ ASBAN
5
1.13. Defin´ıci´ o. Legyen f a D digit´ alis halmaz felett ´ertelmezett bin´ aris k´ep. Jel¨ olje B az f h´ atter´et ´es F az el˝ oter´et. Lyukaknak nevez¨ uk a B azon 4-komponenseit (8-komponenseit), amelyekhez nem lehet konstru´ alni olyan 4-utat (8-utat), amely a komponens egy tetsz˝ oleges elem´et a D ´ altal kifesz´ıtett W ablak keret´enek valamely pontj´ aval k¨ oti ¨ ossze, u ´gy, hogy az utat alkot´ o pontok mindegyike a W \ F halmaz eleme. Most n´ezz¨ unk egy-k´et szeml´eltet˝ o p´eld´ at az u ´j fogalmakra a kor´abbi p´eld´ank seg´ıts´eg´evel. Sem az U sem a V nem ablak. Ha p´eld´aul az U halmazb´ol a (3, 1) koordin´at´aj´ u pontokat elhagyjuk, akkor egy ablakot kapunk. A V halmaz ´altal kifesz´ıtett ablak a V ∪ {(3, 2)} halmaz lesz. A p´eld´aban szerepl˝o D digit´alis halmaz nem tartalmaz lyukat (f¨ uggetlen¨ ul att´ ol, hogy melyik ¨osszef¨ ugg˝os´eget v´alasztjuk). 2. Heurisztikus algoritmusok Kezdetben — hasonl´ ok´eppen a digit´ alis k´epfeldolgoz´as m´as algoritmusaihoz — a v´azkijel¨ol˝o algoritmusok is heurisztikusak voltak. Ebben a fejezetben k´et ilyen algoritmust ismertet¨ unk v´ azlatosan. Megfigyelhetj¨ uk ezen pr´ob´alkoz´asok gyenges´egeit is. A [28]-ban S.K. Parui ´es A. Datta ´ altal publik´alt algoritmus ¨otlete egy egyszer˝ u folytonos modellb˝ ol sz´ armazik. Ennek alapj´an a v´azat a folytonos esetben a k¨ovetkez˝ok´eppen defini´ alhatjuk: 2.1. Defin´ıci´ o [28]. Azon P objektumpontokat v´ azpontoknak fogjuk nevezni, amelyek a rajtuk ´ athalad´ o legr¨ ovidebb hossz´ us´ ag´ u h´ urok k¨ oz¨ ul legal´ abb egynek felez˝ opontja. A v´ azpontok ¨ osszes´eg´et az objektum v´ az´ anak nevezz¨ uk. Digit´alis k´epen — a fenti ¨ otletet felhaszn´ alva — a v´azat a f¨ ugg˝oleges ´es v´ızszintes ´ır´any´ u h´ urok vizsg´ alat´ aval jel¨ olhetj¨ uk ki. Ezeket lefut´asoknak fogjuk nevezni. Meg´allapodunk abban, hogy a f¨ ugg˝ oleges lefut´as kezd˝opixele a legfels˝o objektumpont, a v´ızszintes´e pedig a legbaloldalibb. Egy lefut´as hossz´an az azt alkot´o objektumpontok sz´ am´ at ´ertj¨ uk. Egy n hossz´ us´ag´ u lefut´as k¨oz´ep-pixel´en a lefut´as kezdet´et˝ol sz´am´ıtott [(n + 1)/2] objektumpontot ´ertj¨ uk. Ez a fogalom a folytonos modellben a felez˝ opontnak felelt meg. Az objektum v´ aza a k¨ ovetkez˝ ok´eppen tal´ alhat´o meg: minden objektumpont eset´en megvizsg´aljuk az ahhoz tartoz´ o lefut´ asokat. E k´et lefut´as k¨oz¨ ul a r¨ovidebbet v´alasztjuk ki. Ha a vizsg´ alt objektumpont k¨oz´ep-pixele ennek a minim´alis lefut´asnak, akkor v´ azpontnak nevezz¨ uk. A v´azpontok ¨osszes´ege alkotja a v´azat. Vil´agos, hogy egy v´ azpont megtal´ al´ asa f¨ uggetlen m´as v´azpontokt´ol, ´ıgy a v´azkijel¨ol´es p´arhuzamos´ıthat´ o. Nagyon egyszer˝ u a´br´ak eset´en is tapasztalhatjuk azt, hogy a v´az nem ˝orzi meg az objektum ¨ osszef¨ ugg˝os´egi viszonyait. P´eldak´ent tekints¨ uk a 2a. ´abr´an l´athat´ o objektumot ´es annak v´ az´at a 2b. ´abr´an.
6
FAZEKAS ATTILA
2a. ´ abra
2b. ´ abra
L´athat´o, hogy a v´ azkijel¨ ol´es eredm´enyek´ent (´altal´aban) cs¨okken az objektumpontok sz´ama. A v´ azpontok kiv´etel´evel minden objektumpont h´att´erpontt´a v´alik. A p´eld´ankban a 2a. ´ abr´ an csak azok az objektumpontok maradnak az elj´ar´as ut´an is objektumpontok, amelyek a 2.1. defin´ıci´o ´ertelm´eben v´azpontok. Az eredeti objektum 8-¨osszef¨ ugg˝ o (s˝ ot 4-¨ osszef¨ ugg˝ o) volt, de a v´az nem 8-¨osszef¨ ugg˝o. Ez nagy probl´ema, mert csak a v´ azat ismerve nem tudjuk eld¨onteni a feldolgoz´as k´es˝obbi szakasz´aban, hogy ez egy vagy k´et objektumnak a v´aza. Fontos, hogy a v´az meg˝orizze az eredeti objektum ¨ osszef¨ ugg˝ os´egi viszonyait. Enn´el a p´eld´an´al ez nem teljes¨ ult. A [7]-ben egy speci´ alis c´elokra kifejlesztett heurisztikus algoritmust tal´alhatunk. Arra val´o tekintettel, hogy ez csak k´eziratban jelent meg, ez´ert r´eszletesebben ismertetj¨ uk. Jel¨olje f az A(k, l) balfels˝ o ´es B(m, n) jobbals´o sark´ u W ablak felett ´ertelmezett bin´aris k´epet. Ezt a digit´ alis k´epet k¨ onnyen reprezent´alhatjuk egy m − k oszlopb´ol ´es n − l sorb´ol ´ all´ o bin´ aris m´ atrixszal. A kapcsolatot az f ´es M k¨oz¨ott a k¨ovetkez˝o egyenl˝os´eg teremti meg: Mx,y = f (P (x, y))
∀P ∈ W.
A v´azpontok kijel¨ ol´ese az M m´ atrix soraiban t¨ort´enik a sorok index´enek n¨ovekv˝o sorrendj´eben haladva. T´etelezz¨ uk fel, hogy az y0 -n´al (y0 > l) kisebb index˝ u sorokban a v´ azpontokat m´ ar kijel¨ olt¨ uk. K´epezz¨ uk az y0 , illetve az y0 − 1 sor megfelel˝o elemeinek felhaszn´ al´ as´ aval az Exy0 = 2(1 − my0 ,x ) + (1 − my0 −1,x ) o¨sszegeket. Ekkor Exy0 lehets´eges ´ert´ekei: 0, 1, 2, 3. Ha Exy0 = λ, akkor azt mondjuk, hogy az Exy0 sorozat a j-edik pontban az Aλ (λ = 0, 1, 2, 3) ´allapotban van. Most l´assunk egy p´eld´ at az Exy0 sorozat k´epz´es´ere. A 3. ´abr´an egy bin´aris k´epet l´atunk, ezt k¨ovet˝oen egy t´ abl´ azatot, amelyik a k´epet reprezent´al´o bin´aris m´atrixot, ´es ennek seg´ıts´eg´evel a fenti sorozat k´epz´es´et mutatja be.
3. ´ abra
y0 − 1 y0 Exy0 allapot ´
11 11 00 A0
1 0 2 A2
0 0 3 A3
0 1 1 A1
111 111 000 A0
0 0 3 A3
´ ¨ O ˝ ALGORITMUSOK A DIGITALIS ´ ´ ´ VAZKIJEL OL KEPFELDOLGOZ ASBAN
7
Az Aλ ´ert´ekek felhaszn´ al´ as´ aval a k´epet alkot´o foltvonalakat k´et nagy csoportba oszthatjuk. Az egyik csoportot a ”nem visszahajl´o foltvonalak” alkotj´ak. Erre jellegzetes p´elda a 4. ´ abr´ an l´ athat´ o foltvonal. Az ezeknek megfelel˝o ´allapotsorozatra az jellemz˝o, hogy egyetlen A0 sorozatot tartalmaz, amelynek hossza a foltvonal vastags´ag´aval becs¨ ulhet˝ o.
4. ´ abra
A m´asik csoportot a ”visszahajl´ o foltvonalak” alkotj´ak. Erre p´eld´at az 5. ´abr´an l´athatunk. Az ezeknek megfelel˝ o´ allapotsorozatban legal´abb k´et darab A0 sorozat van. Az A0 sorozatokat elv´ alaszt´ o A1 vagy A2 szelet hossza jellemz˝o a foltvonal g¨orb¨ ulet´ere.
5. ´ abra
A 3. ´abr´an l´ athat´ o k´epr˝ ol kis m´erete miatt nem tudjuk eld¨onteni, hogy melyik csoportba tartoz´ o foltvonal r´eszlet´et ´ abr´ azolja. Ezek ut´an az y0 sorban szerepl˝ o A0 sorozatok — mint v´ızszintes lefut´asok — k¨oz´eppixel´et (figyelembe v´eve a kor´ abban kijel¨ olt v´azpontok elhelyezked´es´et) kijel¨olj¨ uk v´azpontnak. El´ agaz´ asok, keresztez˝ od´esek eset´en a v´ızszintes lefut´asok mellett a f¨ ugg˝oleges lefut´ asok vizsg´ alat´ ara is sz¨ uks´eg van. Err˝ol r´eszletesebben olvashatunk
8
FAZEKAS ATTILA
az eml´ıtett dolgozatban. ´kony´ıto ´ algoritmusok 3. Ve A v´azkijel¨ol´esre haszn´ alt egyik alapvet˝ o technika a v´ekony´ıt´as. Ennek pontos defin´ıci´oj´at a 6. fejezetben fogjuk ismertetni. Az irodalomban a v´azkijel¨ol´est ´es a v´ekony´ıt´ast sokszor rokon ´ertelemben haszn´alj´ak. Pedig l´enyeges k¨ ul¨onbs´eg van a kett˝o k¨oz¨ott. A v´ azkijel¨ ol´es egy olyan algoritmus, amelyik egy objektum v´az´at szolg´altatja eredm´enyk´ent. A v´ekony´ıt´ as pedig egy olyan iterat´ıv m´odszer, amely minden iter´aci´ oban t¨ orli a vizsg´ alt objektum azon objektumpontjait, amelynek szomsz´eds´ag´aban van h´ att´erpont. (Az ilyen objektumpontot kont´ urpontnak nevezik.) Bizonyos j´ arul´ekos felt´etelekkel el´erhetj¨ uk azt is, hogy csak abban az esetben t¨ort´enjen meg egy kont´ urpontnak a t¨ orl´ese, ha az nem v´altoztatja meg az objektum ¨osszef¨ ugg˝os´egi viszonyait. R´egebben a v´ azat t¨ obbf´elek´eppen defini´ alt´ak. N´eh´anyat ezek k¨oz¨ ul mi is ismertett¨ unk ebben a munk´ aban. Gyakran a v´ekony´ıt´as sor´an kapott objektumot defini´alt´ak az eredeti objektum v´ azak´ent. Napjainkban a v´az ´altal´anosan elfogadott defin´ıci´oja (l´asd 7. fejezet) f¨ uggetlen a kinyer´es´ehez haszn´alt m´odszert˝ol. Ez´ert a v´ekony´ıt´o algoritmusok megkonstru´ al´ asa ut´an m´eg igazolni kell, hogy a kimenetk´ent kapott k´ep val´ oban a bemeneti k´epen l´ athat´o objektum v´az´at tartalmazza. A 7. fejezetben p´eldak´ent ismertet¨ unk egy ilyen komplex elemz´est. A v´ekony´ıt´o algoritmusok csal´ adj´ ara klasszikus p´elda E.S. Deutsch [14]-ben ismertetett algoritmusa. Itt a szerz˝ o egy Boole-egyenletrendszer seg´ıts´eg´evel adja meg azokat a felt´eteleket, amelyek meghat´ arozz´ak, hogy egy objektumpont mikor t¨or¨olhet˝o. 3.1. Jel¨ ol´ es. Legyen f a D digit´ alis halmaz felett ´ertelmezett digit´ alis k´ep. Legyen P (x, y) a D egy tetsz˝ oleges pontja. Ekkor a P1 (x + 1, y), P2 (x + 1, y + 1), P3 (x, y + 1), P4 (x−1, y+1), P5 (x−1, y), P6 (x−1, y−1), P7 (x, y−1), P8 (x+1, y−1) jel¨ ol´esekkel defin´ aljuk a γP (i) = f (Pi ) f¨ uggv´enyt. A γP helyett, ha nem okoz f´elre´ert´est a γ jel¨ ol´est fogjuk haszn´ alni. 3.2. Defin´ıci´ o. A Γ keresztsz´ amot (Hilditch-f´ele keresztez˝ od´esi sz´ am) a k¨ ovetkez˝ ok´eppen defini´ aljuk:
Γ=
8 X
|γ((k
mod 8) + 1) − γ(k)|.
k=1
Most r¨oviden ismertetj¨ uk a Deutsch-f´ele szab´alyrendszert ´es az azt haszn´al´o algoritmust. (3.1) (3.2)
Γ = 0, 2 vagy 4 8 X
γ(k) 6=1
k=1
(3.3)
γ(1) ∧ γ(3) ∧ γ(5) =0
(3.4)
γ(1) ∧ γ(3) ∧ γ(7) =0
´ ¨ O ˝ ALGORITMUSOK A DIGITALIS ´ ´ ´ VAZKIJEL OL KEPFELDOLGOZ ASBAN
9
Ha Γ = 4, akkor m´eg vagy az (3.5a) vagy az (3.5b) felt´etelnek is teljes¨ ulnie kell: {γ(1) ∧ γ(7) =1} ´es {γ(2) ∨ γ(6) =1} ´es (3.5a)
{γ(3) ∨ γ(4) ∨ γ(5) ∨ γ(8) =0} {γ(1) ∧ γ(3) =1} ´es {γ(4) ∨ γ(8) =1} ´es
(3.5b)
{γ(2) ∨ γ(5) ∨ γ(6) ∨ γ(7) =0}
(3.6)
γ(3) ∧ γ(5) ∧ γ(7) =0
(3.7)
γ(5) ∧ γ(7) ∧ γ(1) =0
Ha a Γ = 4, akkor m´eg vagy a (3.8a) vagy a (3.8b) felt´etelnek is teljes¨ ulnie kell: {γ(5) ∧ γ(3) =1} ´es {γ(6) ∨ γ(2) =1} ´es (3.8a)
{γ(1) ∨ γ(4) ∨ γ(7) ∨ γ(8) =0} {γ(7) ∧ γ(5) =1} ´es {γ(8) ∨ γ(4) =1} ´es
(3.8b)
{γ(5) ∨ γ(6) ∨ γ(7) ∨ γ(2) =0}.
Els˝o l´ep´esben megvizsg´ aljuk, hogy mely objektumpontok el´eg´ıtik ki az (3.1)-(3.5) szab´alyok mindegyik´et. Amelyek kiel´eg´ıtik azokat t¨or¨olj¨ uk. (T¨orl´es alatt egy objektumpontnak h´ att´erpontt´ a t¨ ort´en˝ o´ atmin˝os´ıt´es´et ´ertj¨ uk.) Ez lesz az els˝o alciklus. A m´asodik alciklusban az (3.1),(3.2) ´es (3.6)-(3.8) szab´alyok teljes¨ ul´es´et vizsg´aljuk. A vizsg´alat ut´ an a lehets´eges t¨ orl´eseket is elv´egezz¨ uk. A k´et alciklus egym´asut´ani egyszeri alkalmaz´ asa alkot egy ciklust. Ezt addig kell ism´etelni, am´ıg van t¨or¨olhet˝o objektumpont a k´epen. Az irodalomban tal´ alhat´ o v´ekony´ıt´ o algoritmusok csoportos´ıt´as´anak egyik lehets´eges szempontja az, hogy h´ any alciklusb´ ol ´all. Lehets´eges ´ert´ekek: 1 [22,23,33], 2 [12,29,34], 4 [1,17], 8 [1,17]. Csoportos´ıthatjuk az algoritmusokat a szekvenci´alis [9,21] vagy p´arhuzamos [28,32] voltuk alapj´an is.
10
FAZEKAS ATTILA
Vegy¨ uk ´eszre, hogy a vizsg´ alt algoritmusban az adott alciklusbeli szab´alyok teljes¨ ul´es´et az ¨osszes objektumpontra egyidej˝ uleg vizsg´alhatjuk meg. Ez´ert p´arhuzamos architekt´ ur´ aj´ u sz´ am´ıt´ og´ep haszn´ alat´ aval jelent˝osen cs¨okkenthetj¨ uk a v´egrehajt´asi id˝ot. Most vizsg´aljunk meg n´eh´ any szab´ alyt k¨ ozelebbr˝ol. A (3.2) szab´alynak az a hat´asa, hogy ha az ¨osszeg ´ert´eke 1, akkor megakad´alyozza a m´ar v´ekony´ıtott komponensek v´egeinek t¨ orl´es´et. A (3.3) ´es (3.4) a n´egyzetes ablakon bel¨ uli fels˝o ´es jobboldali poz´ıci´ok 4-¨osszef¨ ugg˝ os´eg´et biztos´ıtja. A (3.6)-(3.8) szab´alyok a (3.3)-(3.5) szab´alyok 180◦ -os ”elforgatottjai”. Az objektumpontok t¨ orl´es´ere vonatkoz´ o felt´eteleket nem csak Boole-egyenletekkel, hanem u ´gynevezett sablonok seg´ıts´eg´evel is megadhatjuk. 3.3. Defin´ıci´ o. Legyen X ´es Y digit´ alis halmaz. Egy ´ altal´ anos´ıtott, bin´ aris ´ert´ek˝ u Y -b´ ol X-be hat´ o t sablon alatt egy t : Y → f (X) f¨ uggv´enyt ´ert¨ unk, ahol f egy X feletti bin´ aris k´ep. A t egy r¨ ogz´ıtett P ∈ Y eset´en egy X feletti bin´ aris k´ep, azaz tP : X → {0, 1}. 3.4. Defin´ıci´ o. A 3.3. Defin´ıci´ o jel¨ ol´eseit haszn´ alva. Minden sablon eset´en lehet˝ os´eg van egy P (k, l) ∈ Y elem kit¨ untet´es´ere, amit centr´ alis elemnek nevez¨ unk. Azt mondjuk, hogy a t sablon illeszkedik a Q(m, n) ∈ X pontban a k´epre, ha ∀P 0 (i, j) ∈ Y eset´en f (Q0 (m−(k−i), n−(l−j))) = tP 0 (i,j) (Q0 (m−(k−i), n−(l−j))) teljes¨ ul. Pavan Kumar ´es munkat´ arsai [22], egy iterat´ıv, p´arhuzamos v´azkijel¨ol˝o algoritmust adtak, amely egyetlen alciklust alkalmaz. Az ´altaluk haszn´alatos sablonokat a 6. ´abr´an l´athatjuk.
6. ´ abra
Ezt a t´ız sablont A-t´ıpus´ u sablonnak nevezz¨ uk. Vizsg´aljuk meg p´eld´aul az els˝o sablont k¨ozelebbr˝ ol. N´ezz¨ uk meg a 3.4. defin´ıci´o jel¨ol´eseit haszn´alva, hogy mit jelent egy ilyen grafikus sablon-megad´ as. Ahogy azt kor´abban l´attuk ez meghat´aroz egy ´ meghat´aroz egy Y feletti g digit´alis halmazt, ez eset¨ unkben az Y -nak felel meg. Es ´ bin´aris k´epet is. Allapodjunk meg, hogy ez a megad´asi m´od ∀P ∈ Y eset´en jelentsen egy olyan X feletti f 0 bin´ aris k´epet, amely a k¨ovetkez˝ok´eppen van defini´alva: g(Q0 ) , ha Q0 eleme az Y -nak f 0 (P 0 ) = 0 , egy´ebk´ent. arozott poz´ıci´ ok k¨ oz¨ ul egy sablonon bel¨ ul legal´abb egynek ◦A jel ´altal meghat´ nek kell lennie. Ez tulajdonk´eppen t¨ obb sablon egy¨ uttes le´ır´as´at teszi lehet˝ov´e. P´eld´aul a harmadik sablon ezzel a r¨ ovid´ıt´esi technik´aval 31 sablont helyettes´ıt.
´ ¨ O ˝ ALGORITMUSOK A DIGITALIS ´ ´ ´ VAZKIJEL OL KEPFELDOLGOZ ASBAN
11
Ezek alapj´an k¨ onnyen eld¨ onthetj¨ uk, hogy ez a sablon a 7a. ´abr´an l´athat´o bin´aris k´ep mely poz´ıci´ oira illeszkedik.
7a. ´ abra
7b. ´ abra
Ezek ut´an a sablonok haszn´ alat´ at k¨ onny˝ u meg´erteni. Ez nem jelent m´ast, mint azoknak az objektumpontoknak a megkeres´es´et ´es t¨orl´es´et, amelyekre legal´abb egy sablon illeszkedik. Ezt a t´ıpus´ u sablonoz´ ast t¨orl˝o sablonoz´asnak nevezz¨ uk. Ha ilyen ´ertelemben haszn´ aljuk az els˝ o sablont, akkor az ezzel t¨ort´en˝o sablonoz´as eredm´enye a 7b. ´abr´an l´athat´ o. A fenti cikkben ismertetett algoritmus meg¨orz˝o sablonoz´ast haszn´al, ami azt jelenti, hogy csak azokat az objektumpontokat t¨ or¨olj¨ uk, amelyekre egyetlen sablon sem illeszkedik. Teh´ at a sablonok nem a t¨ orl´es, hanem a meg¨orz´es felt´eteleit hat´arozz´ak meg. Vizsg´aljuk tov´ abb a [22]-ben tal´ alhat´ o algoritmust. Ha csak az A-sablonokat haszn´aljuk, akkor a bels˝ o pontok is t¨ orl˝ odhetnek. (P´eld´aul a 8. ´abr´an l´athat´o objektum egyetlen ciklus alatt t¨ orl˝ odik, mert egyetlen objektumpontj´ara sem illeszkedik Asablon.) Ez´ert a szerz˝ o azt javasolja, hogy hozzunk l´etre egy u ´gynevezett s˝ ur˝ u k´eps´ıkot ´es tervezz¨ unk meg egy u ´jabb csoport sablont, amit ezen fogunk haszn´alni. Egy sablon illeszked´ese a s˝ ur˝ u k´eps´ıkon azt jelenti, hogy az objektumpont nem t¨or¨olhet˝o az A-sablonokkal. Ezekr˝ ol r´eszletesebben a fenti irodalomban olvashatunk. A s˝ ur˝ u k´eps´ık az eredeti digit´ alis k´epb˝ol nyerhet˝o a k¨ovetkez˝ok´eppen. Abban az esetben, ha az eredeti digit´ alis k´ep 2 × 2-es k¨ornyezet´eben csak objektumpontok vannak, akkor a megfelel˝ o s˝ ur˝ u k´eps´ıkbeli pont is objektumpont lesz. Minden m´as esetben a s˝ ur˝ u k´eps´ıkbeli pont h´ att´erpont lesz. Nagyon k¨olts´eges lenne, ha az eg´esz s˝ ur˝ u k´eps´ıkot t´ aroln´ ank, k¨ ul¨ on¨ osen, ha az eredeti k´ep nagyon nagy. Erre azonban nincs sz¨ uks´eg. A s˝ ur˝ u k´eps´ık pontjait helyileg lehet l´etrehozni, ´es azonnal elv´egezni a sablonoz´ast rajta a helyre´ all´ıt´ o sablonokkal.
12
FAZEKAS ATTILA
8. ´ abra
A sablonok haszn´ alata torz´ıt´ asokat okoz a k´epen. Ezen hat´asok cs¨okkent´es´ere k¨ ul¨onb¨oz˝o javaslatok tal´ alhat´ ok az irodalomban. Az egyik lehet˝os´eg speci´alis, u ´gynevezett tiszt´ıt´ o sablonok haszn´ alata [28], amelyek a hib´akat korrig´alj´ak. A m´asik elj´ar´as az adapt´ıv sablonoz´ as, amelyr˝ ol r´eszletesen a [33]-ban olvashatunk. Ezt most r¨oviden ´ attekintj¨ uk. Az alapelv tulajdonk´eppen nagyon egyszer˝ u. Bizonyos felt´etelek teljes¨ ul´ese eset´en a 3 × 3-as sablonok helyett 9 × 9-eseket haszn´alunk. (Ha ´alland´oan ilyen sablonokat haszn´aln´ank, az t´ ul dr´ aga” lenne v´egrehajt´asi id˝o ´es t´arhely szempontj´ab´ol egy” ar´ant.) A nagym´eret˝ u sablonok val´ oj´ aban nem 9 × 9-esek. A k¨oz´eps˝o r´esz egy szok´asos 3 × 3-as sablon. A nyolc darab perif´eri´alis r´esz mindegyike szint´en lefed egy-egy 3 × 3-as ter¨ uletet, de cs¨ okkentett inform´aci´oszolg´altat´assal (9. ´abra). Ezen r´eszeken k´et bin´ aris ´ert´ek gener´ al´ odik. Legyen ez a k´et ´ert´ek α ´es β. α=
0 , ha a
P8
k=1
γ(k) ≤ 5
1 , k¨ ul¨ onben.
(A vizsg´alt elem minden esetben a megfelel˝o perif´eri´alis elem centr´alis eleme.) A β bin´aris v´altoz´ ot ezen 3 × 3-as ter¨ uleten elhelyezked˝o pontok ´altal kiadott minta feljegyz´es´ere haszn´ aljuk. P´eld´ aul a tapasztalatok alapj´an az egy egyenesre es˝o h´arom pont ´altal alkotott mint´ at ´erdemes megk¨ ul¨onb¨oztetni az egy´eb elrendez´est˝ol. Az ilyen kit¨ untetett elrendez´es eset´en β = 1, k¨ ul¨onben β = 0.
´ ¨ O ˝ ALGORITMUSOK A DIGITALIS ´ ´ ´ VAZKIJEL OL KEPFELDOLGOZ ASBAN
13
9. ´ abra
A felt´etel ebben az esetben, ami alapj´ an a 3 × 3-as sablonr´ol a 9 × 9-es sablonra t´er¨ unk ´at, az, hogy a kont´ urpont alatt ´es felett van k´et el˝ot´erpont. Ez azt val´osz´ın˝ us´ıtheti, hogy egy hossz´ u f¨ ugg˝ oleges vonal tal´alhat´o a k´epen. M´as-m´as torz´ıt´as” ” eset´en m´as-m´ as felt´etelt ´es m´ as-m´ as 9 × 9-es sablont kell alkalmaznunk. Ennek a m´odos´ıt´asnak az az el˝ onye, hogy kev´es nagy” sablonra van sz¨ uks´eg, ´es nagyon ” ritk´an kell ´att´erni ezekre. Ezzel v´egrehajt´asi id˝ot ´es mem´ori´at takar´ıthatunk meg ahhoz k´epest, ha 9 × 9-es sablont haszn´ aln´ank ´alland´oan. ´ sz´ınu ˝ se ´gsza ´m´ıta ´si mo ´ dszerek alkalmaza ´sa 4. Valo Az iterat´ıv m´ odszerek jelent˝ os csoportja val´osz´ın˝ us´egsz´am´ıt´asi eszk¨oz¨ok¨on alapul. Ezek k¨oz¨ ul kett˝ ot szeretn´enk kiemelni ezen dolgozatban. Els˝ok´ent Sabri A. Mahmoud ´es munkat´ arsainak [25]-ben publik´ alt v´azkijel¨ol˝o algoritmus´at ismertetj¨ uk. A szerz˝ok egy X halmaz fuzzy c-feloszt´ as´ at a k¨ovetkez˝ok´eppen defini´alj´ak: 4.1. Defin´ıci´ o. Egy X halmaz egy fuzzy c-feloszt´ asa olyan c darab f¨ uggv´enyt tartalmaz´ o rendszer, amely teljes´ıti a k¨ ovetkez˝ o tulajdons´ agokat: ui : X → [0, 1], ahol 0 ≤ i ≤ c − 1 ´es i ∈ N , c−1 X
ui (x) = 1 ∀x ∈ X.
i=0
Az ui -t fuzzy halmaznak, illetve fuzzy klaszternek nevezz¨ uk X-ben. Az ui (x) az x tartalmaz´ asi foka az ui fuzzy halmazon. Ez az algoritmus egyenes szakaszokb´ ol ´ep´ıti fel az objektum v´az´at. Ez k´et l´ep´esben t¨ort´enik meg. Az els˝ o l´ep´esben a szakaszok v´egpontjait hat´arozza meg, a m´asodik l´ep´esben pedig ezek seg´ıts´eg´evel hozza l´etre a v´azat. A szakaszok v´egpontjait a k¨ovetkez˝o algoritmus seg´ıts´eg´evel hat´ arozhatjuk meg: Legyen c egy olyan r¨ ogz´ıtett konstans, amely kett˝on´el nem kisebb ´es nem nagyobb az X elemsz´amn´ al. Vegy¨ uk az X digit´ alis halmaznak egy fuzzy c-feloszt´as´at, amelyben tal´alhat´o ui f¨ uggv´enyek egyike sem azonosan nulla. Sz´am´ıtsuk ki az mi ´ert´ekeket, amelyek a klaszterek centrumai lesznek az algoritmus v´egrehajt´asa ut´ an: P (ui (x))2 x x∈X mi = P i = 0, 1, · · · , c − 1 (ui (x))2 x∈X
Ezek ut´an konstru´ aljunk egy u ´j fuzzy c-feloszt´ast a k¨ovetkez˝ok szerint:
14
FAZEKAS ATTILA
Legyen I(x) = {i|mi = x, 0 ≤ i ≤ c − 1}. Ha I(x) nem¨ ures, akkor legyen u ˆi (x) =
1,
ha i = ˆı
0,
ha i 6= ˆı,
ahol ˆı a legkisebb eg´esz I(x)-ben. Ha I(x) = ∅, akkor u ˆi (x) =
1/(kx − mi k2 ) . c−1 P (1/(kx − mj k2 ) j=0
Az euklideszi norm´ at alkalmazva hat´ arozzuk meg az ui ´es u ˆi k¨ozti elt´er´est. Ha ez kisebb, mint egy megadott k¨ usz¨ ob, akkor fejezz¨ uk be az algoritmus v´egrehajt´as´at, egy´ebk´ent legyen ui = u ˆi ´es l´epj¨ unk vissza az mi -k kisz´am´ıt´as´aig ´es folytassuk onnan a v´egrehajt´ ast. A fenti algoritmus kisz´ amolja a klaszterek centrum´at. Ezek ut´an a k´epet letapogatjuk egy 2×2-es m´eret˝ u ablakkal. Ha az ablak valamelyik k´et pontja k¨ ul¨onb¨oz˝o klaszterhez tartozik, akkor ezeket a klasztereket szomsz´edosoknak tekintj¨ uk. A szomsz´eds´agi rel´ aci´ ok le´ır´ as´ ara egy c × c-s m´atrixot alkalmazhatunk. K´et szomsz´edos klaszter centrum´ at egy egyenes szakasszal k¨otj¨ uk ¨ossze, amelynek v´egpontjai a vizsg´alt klaszterek centrumai. Az ´ıgy kapott k´ep a v´az. Olyan v´egpontok elhagyhat´ ok adatcs¨ okkent˝o l´ep´esk´ent, ahol majdnem folytonos” s´ag” van. Legyen vi egy v´egpont, amely ¨ossze van k¨otve vj ´es vk v´egpontokkal. Jel¨olje α a k¨ozbez´ art sz¨ oget. Ha 180◦ − γ ≤ α ≤ 180◦ + γ, ahol γ egy k¨ usz¨obsz¨og, akkor vi -t t¨or¨ olj¨ uk a v´ azb´ ol felt´eve, ha az nincs m´as cs´ uccsal is ¨osszek¨otve a fentieken k´ıv¨ ul. A t¨orl´es ut´ an a vj ´es vk v´egpontokat ¨ossze kell k¨otni. Az elj´ar´ast addig ism´etelj¨ uk, am´ıg nincs t¨ obb elhagyhat´ o cs´ ucs. Az S.S. You ´es W.H. Tsai algoritmusa [26] t¨obbszint˝ u k´epek eset´en is alkalmazhat´o. Ez az´ert ´erdekes, mert ´ altal´ aban a v´ azkijel¨ol˝o algoritmusok bin´aris k´epet v´arnak bemenetk´ent. Az algoritmus ismertet´ese el˝ott n´eh´any fontos fogalmat defini´alunk. 4.1. Defin´ıci´ o. Egy objektumpontot egyszer˝ unek nevez¨ unk, ha t¨ orl´ese nem v´ altoztatja meg az objektum ¨ osszef¨ ugg˝ os´egi viszonyait, ellenben ¨ osszek¨ ot˝ opontnak. 4.2. Defin´ıci´ o. Egy objektumpontot v´ egpontnak nevez¨ unk, ha pontosan egy objektumpont van 8-szomsz´edai k¨ oz¨ ott. 4.3. Defin´ıci´ o. Egy objektumpontot izol´ alt pontnak nevez¨ unk, ha nincs objektumpont a 8-szomsz´edai k¨ oz¨ ott. 4.4. Defin´ıci´ o. Egy objektumpontot bels˝ o pontnak nevez¨ unk, ha nincs h´ att´erpont a 8-szomsz´edai k¨ oz¨ ott. T´etelezz¨ uk fel, hogy a digit´ alis k´ep t¨ obbszint˝ u ´es a h´att´erpontok vil´agoss´agk´odja kisebb, mint az objektumpontok vil´ agoss´ agk´odja. Az elj´ar´as sor´an a k´eppontokat ¨ot oszt´alyba soroljuk. Az ¨ ot oszt´ aly k¨ oz¨ ul n´egy v´az-oszt´aly ´es egy nemv´az-oszt´aly. A v´az-oszt´alyok tulajdonk´eppen a 0◦ , 45◦ , 90◦ , 135◦ ir´anyhoz tartoz´o egyenesek oszt´aly´at jelentik. Ezzel felt´etelezz¨ uk, hogy minden egyes v´azpont a v´azban illeszkedni fog legal´ abb egy egyenesre a fentiek k¨oz¨ ul (10. ´abra). Ebben az algoritmusban is csak n´egy ir´ any van megadva. Ha sz¨ uks´eges, akkor t¨obb is megadhat´o. Az ¨ot oszt´alyt λ0 , λ1 , · · · , λ4 -el jel¨ olj¨ uk. A λ4 jel¨oli a nemv´az-oszt´alyt. Jel¨olje
´ ¨ O ˝ ALGORITMUSOK A DIGITALIS ´ ´ ´ VAZKIJEL OL KEPFELDOLGOZ ASBAN
15
Px,y (λi ) annak a val´ osz´ın˝ us´eg´et, hogy az (x, y) koordin´at´aj´ u pont a λi oszt´alyba P3 tartozik. Az (x, y) koordin´ at´ aj´ u pont Sx,y = i=0 Px,y (λi ) val´osz´ın˝ us´eggel tartozik a v´azhoz.
10. ´ abra
A m´odszer sor´ an a priori ismeretk´ent feltessz¨ uk, hogy ´altal´aban egy vastag vonal P kont´ urpontj´ anak vil´ agoss´ agk´ odja nagyobb, mint egy vonal belsej´eben l´ev˝o Q pont´e, ´es a P pont kisebb val´ osz´ın˝ us´eggel tartozik a v´azhoz, mint a Q. ´Igy az (x, y) koordin´ at´ aj´ u pont kezdetben a k¨ ovetkez˝ok´eppen defini´alt val´osz´ın˝ us´eggel fog a v´azhoz tartozni: Gx,y (0) Sx,y = α1 , Gmax ahol Gmax a legnagyobb lehets´eges vil´ agoss´agk´od, Gx,y az (x, y) koordin´at´aj´ u pont vil´agoss´agk´odja ´es 0 < α1 < 1, α1 ∈ R. Az α1 egy alkalmas megv´alasztott konstans, amelyik a kezdeti val´ osz´ın˝ us´egi ´ert´ekek kiigaz´ıt´as´ara szolg´al. Az (x, y) koordin´at´aj´ u pont kezdetben a k¨ ovetkez˝ ok´eppen defini´ alt val´osz´ın˝ us´eggel tartozik a h´att´erhez: (0) (0) Px,y (λ4 ) = 1 − Sx,y .
Hogy k¨ ul¨on-k¨ ul¨ on, oszt´ alyonk´ent megbecs¨ ulhess¨ uk az (x, y) koordin´at´aj´ u pont v´azhoz tartoz´as´anak kezdeti val´ osz´ın˝ us´eg´et, fel fogjuk haszn´alni 5 × 5-¨os k¨ornyezet´eben tal´alhat´o k´eppontok val´ osz´ın˝ us´egi ´ert´ekeit. Legyen dk (x, y) (k = 0, 1, 2, 3) a k¨ovetkez˝ok´eppen defini´ alva:
16
FAZEKAS ATTILA
2 1 X (0) (0) d0 (x, y) = |S − Sx+i,y | 4 i=−2 x,y i6=0
d1 (x, y) =
2 1 X (0) (0) |S − Sx+i,y+i | 4 i=−2 x,y i6=0
d2 (x, y) =
2 1 X (0) (0) |S − Sx,y+i | 4 i=−2 x,y i6=0
2 1 X (0) (0) d3 (x, y) = |S − Sx−i,y+i |. 4 i=−2 x,y i6=0 (0)
Ezek seg´ıts´eg´evel a Px,y (λk ) (k = 0, 1, 2, 3) a k¨ovetkez˝ok´eppen defini´alhat´o: (0) Px,y (λk ) =
α1 − dk (x, y) (0) Sx,y , k = 0, 1, 2, 3. 3 P (α1 − di (x, y)) i=0
Amikor arr´ol d¨ ont¨ unk, hogy egy adott pont meg˝orizend˝o-e v´azpontk´ent, csak a vizsg´alt pont ´es az 5 × 5-¨ os k¨ ornyezet´eben tal´alhat´o pontok k¨oz¨otti k¨olcs¨onhat´ast ´ vessz¨ uk figyelembe. Altal´ aban egy λj ir´ any´ u egyenes szakasz l´etez´es´et az (x, y) koordin´at´aj´ u pontban al´ at´ amasztja egy λk ir´any´ u egyenes szakasz l´etez´ese az (u, v) koordin´at´aj´ u pontban, ha az (u, v) az (x, y)-t´ol j · 45◦ ir´anyba esik ´es λk = λj (11. ´abra). A fenti elgondol´ asok alapj´ an defini´aljuk az al´abbi kompatibilit´asi egy¨ utthat´okat. ha az (u, v) az (x, y) j · 45◦ -os szomsz´edja ´es k = j 1, C((x, y), j, (u, v), k) = α2 , ha az (u, v) az (x, y) j · 45◦ -os szomsz´edja ´es k 6= j 0, egy´ebk´ent.
11. ´ abra
Az elj´ar´as sor´ an minden egyes iter´ aci´ oban minden pont val´osz´ın˝ us´eg´et ki kell igaz´ıtani. Ahhoz, hogy ezt megtehess¨ uk ki kell sz´amolni szomsz´edainak ¨osszhat´as´at. Ha az (x, y) koordin´ at´ aj´ u pont egyszer˝ u ´es nem v´egpont, akkor v´eg¨ ul t¨or¨olni fogjuk. Ez´ert k´ıv´anatos n¨ ovelni a h´ att´erhez tartoz´as´anak val´osz´ın˝ us´eg´et. Ha az (x, y) v´eg, izol´alt vagy ¨ osszek¨ ot˝ o pont, akkor v´ azpont, ´ıgy kisebb val´osz´ın˝ us´eggel tartozik a h´att´erhez. Ha (x, y) koordin´ at´ aj´ u pont bels˝o pont, akkor nem tudjuk, hogy v´azpont lesz-e vagy sem, ´es ´ıgy annak a val´osz´ın˝ us´eg´et, hogy a h´att´erhez tartozik nem v´altoztatjuk meg. A fenti meggondol´asok alapj´an annak a val´osz´ın˝ us´eg´et,
´ ¨ O ˝ ALGORITMUSOK A DIGITALIS ´ ´ ´ VAZKIJEL OL KEPFELDOLGOZ ASBAN
17
hogy az (x, y) koordin´ at´ aj´ u pont az r-edik iter´aci´oban a h´att´erhez tartozik, a k¨ovetkez˝ok´eppen defini´ alt egy¨ utthat´ oval v´ altoztatjuk meg: u, nem v´eg pont β1 , ha (x, y) egyszer˝ (r) Qx,y (λ4 ) = 0 , ha bels˝ o pont β2 , egy´ebk´ent, ahol β1 > 0 > β2 . A λ0 -oszt´ alyba tartoz´o pontok val´osz´ın˝ us´eg´enek v´altoz´as´at a k¨ovetkez˝ok´eppen defini´ aljuk:
Q(r) x,y (λ0 ) = β3
4 X 3 h X
(r) Px+i,y (λ0 ) · C (x, y), 1, (x + i, y), k · Mi · Ni
i=1 k=0
i (r) + Px−i,y (λ0 ) · C (x, y), 1, (x − i, y), k · mi · ni , ahol γ, ha (x + i, y) v´ azpont Mi = 1, egy´ebk´ent γ, ha (x − i, y) v´ azpont mi = 1, egy´ebk´ent N0 =1 1, ha Ni−1 = 1 ´es (x + i, y) nem h´att´erpont Ni = 0, k¨ ul¨ onben n0 =1 1, ha ni−1 = 1 ´es (x − i, y) nem h´att´erpont ni = 0, k¨ ul¨ onben. Az Mi ´es mi ´ert´ekeit arra haszn´ aljuk, hogy n¨ovelj¨ uk azon pontok hat´as´at, amelyek m´ar v´azpontnak bizonyultak. Az Ni ´es ni letiltja azon pontok hat´as´at, ame(r) lyek nincsenek k¨ ozvetlen kapcsolatban az (x, y) koordin´at´aj´ u ponttal. A Qx,y (λ1 ), (r) (r) ok´eppen defini´alhat´o. Ezek ut´an: Qx,y (λ2 ) ´es Qx,y (λ3 ) hasonl´ (r+1) Px,y (λk )
(r) (r) Px,y (λk ) 1 + Qx,y (λk ) = 4 . P (r) (r) Px,y (λh ) 1 + Qx,y (λh ) h=0
Megmutathat´ o, hogy az iter´ aci´ o konvergens, ha β3 ´es a γ ≥ 1 az egyes iter´aci´ok sor´an egyre kisebb ´ert´ekeket vesznek fel. Az iter´aci´os folyamat konvergenci´aj´anak apr´o anom´ali´ ait k¨ ul¨ onb¨ oz˝ ok´eppen korrig´ alhatjuk. Erre a szerz˝ok a [26]-ban k¨ ul¨onb¨oz˝o m´odszereket aj´ anlanak. ´ranal´ızis mo ´ dszere 5. A kontu A v´azkijel¨ol˝o algoritmus konstru´ al´ asa sor´ an haszn´alhatunk differenci´algeometriai eszk¨oz¨ok¨on alapul´ o modellt is. Erre igen sz´ep p´elda S. Riazanoff ´es szerz˝ot´arsainak munk´aja, amelyr˝ ol r´eszletesebben a [27]-ben olvashatunk.
18
FAZEKAS ATTILA
A folytonos modell a k¨ ovetkez˝ o: Legyen E egy objektum ´es C a kont´ urja. A tov´abbiakban feltessz¨ uk, hogy a C a k¨ ovetkez˝o alakban ´all el˝o: ! x(t) C : P (t) = t ∈ [0, T ] , y(t) ahol T egy r¨ogz´ıtett konstans. A C g¨ orbe legyen minden pontj´aban k´etszer differenci´alhat´o. A g¨ orbe κ(t) g¨ orb¨ ulete a P (t) pontban: 3/2
x(t)¨ ˙ y (t) − x ¨(t)y(t) ˙ . (x˙ 2 (t) + y˙ 2 (t)) 5.1. Defin´ıci´ o [27]. Az E objektum sugar´ u k¨ orlemezzel val´ o er´ ozi´ oj´ an — a tov´ abbiakban E -nal fogjuk jel¨ olni — az E azon pontjainak halmaz´ at fogjuk ´erteni, amelyek C kont´ urt´ ol val´ o t´ avols´ aga nagyobb, vagy egyenl˝ o mint . κ(t) =
A C jel¨olje az E kont´ urj´ at. A C -t a P (t) ismeret´eben a k¨ovetkez˝ok´eppen hat´arozhatjuk meg: 0 x (t) = x(t) − √ 02 y (t) 02 x (t)+y (t) C : P (t) = t ∈ [0, T ] . 0 y (t) = y(t) − √ x (t) x02 (t)+y 02 (t)
5.2. Defin´ıci´ o [27]. A P (t) pontot v´ azpontnak nevezz¨ uk, ha eleme az E er´ ozionak ´es teljes¨ ´ ul az al´ abbi felt´etelek valamelyike: • A P (t) pontban lok´ alis maximuma van P g¨ orb¨ uletnek. • Az x (t) ´es y (t) deriv´ altja nulla a P (t)-ben. • A C g¨ orbe a P (t) pontban metszi ¨ onmag´ at. 5.3. Algoritmus [27]. 1. ← 0 2. v´ az← ∅ 3. Repeat 3.1. A C meghat´ aroz´ asa. 3.2. A v´ azpontok megkeres´ese a 5.2. defin´ıci´ o alapj´ an. 3.3. A v´ az b˝ ov´ıt´ese a 3.2. pontban megtal´ alt v´ azpontokkal. 3.4. Az ´ert´ek´enek n¨ ovel´ese. 4. Until C 6= ∅ A diszkr´et esetben a g¨ orb¨ ulet a vizsg´ alt kont´ urpont 3 × 3-as k¨ornyezet´enek seg´ıts´eg´evel becs¨ ulhet˝ o. (Ez az algoritmus kis m´odos´ıt´assal k´epes t¨obbszint˝ u k´epen is a v´azkijel¨ol´est elv´egezni.) ´ gia 6. Matematikai morfolo A v´ekony´ıt´o algoritmusok fejleszt´es´evel p´ arhuzamosan fejl˝od¨ott a matematikai morfol´ogia, mint a k´epanal´ızis halmazelm´eleti megk¨ozel´ıt´ese. Ezt Matheron ´es Serra [15] alkotta meg. Ebben a fejezetben Ben-Kwei Jang ´es Roland T. Chin [6]-ban publik´alt eredm´enyeit ismertetj¨ uk kiss´e r´eszletesebben. A k¨ovetkez˝o jel¨ol´eseket fogjuk haszn´alni: • Az XB az X digit´ alis halmaz B vektorral val´o eltoltja ˇ az X digit´ • Az X alis halmaz orig´ ora vett t¨ ukr¨oz´ese sor´an keletkezett halmaz. Egy morfol´ogiai m˝ uvelet egy X digit´ alis halmazt egy m´asik digit´alis halmazba transzform´al. A transzform´ aci´ ot egy T digit´alis halmaz fogja meghat´arozni, ez´ert ezt a halmazt gyakran szerkeszt˝ o mint´ anak is nevezik.
´ ¨ O ˝ ALGORITMUSOK A DIGITALIS ´ ´ ´ VAZKIJEL OL KEPFELDOLGOZ ASBAN
19
6.1. Defin´ıci´ o. Legyen X ´es T digit´ alis halmaz. Az X ⊕ T Minkowski-¨ osszeget a k¨ ovetkez˝ ok´eppen defini´ aljuk: [ X ⊕ T = {A + B|A ∈ X, B ∈ T } = XB . B∈T
6.2. Defin´ıci´ o. Legyen X ´es T digit´ alis halmaz. Az X T Minkowski-k¨ ul¨ onbs´ eget a k¨ ovetkez˝ ok´eppen defini´ aljuk: \ X T = XB . B∈T
6.3. Defin´ıci´ o. Legyen X ´es T digit´ alis halmaz. Az X T -vel val´ o er´ ozi´ oja X Tˇ. 6.4. Defin´ıci´ o. Legyen X ´es T digit´ alis halmaz. Az X T -vel val´ o dilat´ aci´ oja X ⊕ Tˇ.
12. ´ abra
13a. ´ abra
13b. a ´bra
13c. ´ abra
Tekints¨ uk a 12. ´ abr´ an l´ athat´ o digit´ alis halmazt. Legyen a T sablon a 13a. ´abr´an l´athat´o. A sablonon az egyik pontot megjel¨olt¨ uk egy kerettel. Ez a centr´alis elem (a sablon k¨oz´eppontja), amelynek koordin´ at´ aja mindig (0, 0). A 14. ´abr´an l´athatjuk a T sablon hat´ as´ at a 12. ´ abr´ an dilat´ aci´ o ´es Minkowski-¨osszeg eset´en. Er´ozi´o ´es Minkowski-k¨ ul¨ onbs´eg eset´en a v´egeredm´eny az u ¨res halmaz lesz. Eset¨ unkben a sablon k¨oz´eppontos szimmetri´ aj´ anak k¨ osz¨ onhet˝o, hogy a dilat´aci´o ´es a Minkowski¨osszeg, illetve az er´ ozi´ o ´es a Minkowski-k¨ ul¨onbs´eg eset´en nincs k¨ ul¨onbs´eg.
20
FAZEKAS ATTILA
6.5. Defin´ıci´ o. Legyen X ´es T digit´ alis halmaz. A T 1 ´es T 2 tetsz˝ oleges diszjunkt r´eszhalmazai a T -nek, amelyek lefedik T -t. Az X T -vel val´ o hit-miss transzform´ altj´ at a k¨ ovetkez˝ ok´eppen defini´ aljuk: X⊕ ⊗T = (X T 1 )
\
(X ⊕ T 2 ).
A 12. ´abr´an tal´ alhat´ o digit´ alis halmaz hit-miss transzform´altja ¨onmaga, ha a 13a. ´abra T sablon´ at 13b. ´es 13c. ´ abr´ an l´ athat´o m´odon felbontjuk T 1 ´es T 2 -re.
14. ´ abra 1
Nyilv´anval´oan a T felbont´ asa T -re ´es T 2 -re nem egy´ertelm˝ u. A tov´abbiakban a T felbont´as´at egy adott sablon eset´en a k¨ ovetkez˝ok´eppen fogjuk ´ertelmezni. Az adott sablon lesz a T 1 , a sablon komplementere pedig a T 2 digit´alis halmaz. 6.6. Defin´ıci´ o. Legyen X ´es T digit´ alis halmaz. Az X T -vel val´ o v´ ekony´ıt´ as´ at a k¨ ovetkez˝ ok´eppen defini´ aljuk: X T = X \ (X⊕ ⊗T ). Ahhoz, hogy az X-et szimmetrikusan v´ekony´ıtsuk, ´ altal´ aban t¨ obb v´ekony´ıt´ o sablon sz¨ uks´eges. Ekkor a v´ekony´ıt´ as a k¨ ovetkez˝ o alakot ¨ olti: X T = (· · · ((X T1 ) T2 ) · · · ) Tn .
´kony´ıto ´ algoritmus elemze ´se 7. Egy ve ´ gia eszko ¨ zeivel a matematikai morfolo A [6]-ban Ben-Kwei Jung ´es R.T. Chin ismertet egy v´ekony´ıt´o algoritmust ´es annak komplex elemz´es´et. Az elemz´es eredm´enyeit r´eszletesebben ismertetj¨ uk, hogy szeml´eltess¨ uk ezzel az alapvet˝ o bizony´ıt´ asi technik´akat. El¨osz¨or ismerkedj¨ unk meg az algoritmussal. Ez k´et ciklusb´ol ´all. Az els˝o ciklus egy iterat´ıv p´arhuzamos elj´ ar´ as, amely n´egy alciklusra bonthat´o. Minden alciklusban ´ ´ DK egy 3 × 3-as szerkeszt˝ o sablont haszn´ alunk, hogy egy adott ir´anyb´ol (ENY, EK, ´es DNY) a kont´ urpontokat elt´ avol´ıthassuk. A n´egy szerkeszt˝o sablon a 15. ´abr´an
´ ¨ O ˝ ALGORITMUSOK A DIGITALIS ´ ´ ´ VAZKIJEL OL KEPFELDOLGOZ ASBAN
21
l´athat´o, D = {D1 , D2 , D3 , D4 }. A m´ asodik ciklus egy iterat´ıv elj´ar´as, amely az ´ E,K,D ´es NY kont´ urpontok elt´ avol´ıt´ as´ ara szolg´al. A n´egy szerkeszt˝o sablon E = {E 1 , E 2 , E 3 , E 4 } a 16. ´ abr´ an l´ athat´ o.
15. ´ abra
16. ´ abra
Legyen S egy 8-¨ osszef¨ ugg˝ o objektum. Az iter´aci´os elj´ar´as els˝o ´es m´asodik ciklus´at rendre m-mel ´es n-nel fogjuk indexelni. Az algoritmust teljes m´ert´ekben meghat´arozza a Ψ transzform´ aci´ o, amely az els˝o ´es a m´asodik ciklust jelenti. Az els˝o ciklus a Ψ{S, D, m} = {S D}m ahol m az iter´ aci´ ok sz´ am´ at jel¨ oli. Most fogadjuk el, hogy Ψ{S, D, m} konvergens ´es S 0 -h¨oz konverg´ al. A m´ asodik ciklust a Ψ{S 0 , E, n} = {S 0 E}n ¨osszef¨ ugg´es adja, ´es fogadjuk el azt, hogy Ψ{S 0 , E, n} konvergens ´es konverg´al I-hez. 7.1. Defin´ıci´ o [6]. Legyen adott egy 8-¨ osszef¨ ugg˝ o S objektum ´es S w ´ alljon 4-¨ osszef¨ ugg˝ o komponensekb˝ ol. Az S objektum v´ az´ an azt az I objektumot ´ertj¨ uk, amelyik kiel´eg´ıti a k¨ ovetkez˝ o felt´eteleket: ¨ • Osszef¨ ugg˝ os´ eg. Az S ´es I homot´ opi´ aja megegyezik. K´et v´eges halmaz S ´es I homot´ op, ha l´etezik k¨ olcs¨ on¨ osen egy´ertelm˝ u megfeleltet´es az S ´es I komponensei k¨ oz¨ ott, ´es l´etezik k¨ olcs¨ on¨ osen egy´ertelm˝ u megfeleltet´es az S ´es I lyukai k¨ oz¨ ott is. • Egy pixel vastags´ ag. Az I egy pixel vastags´ ag´ u, azaz ha egy olyan pont fordul el˝ o I-ben, amely a 17. ´ abr´ an l´ athat´ o 2 × 2-es n´egyzetes mint´ ak valamelyik´ehez tartozik, akkor ez a pont egyszer˝ u pont. • K¨ oz´ eptengely. I megfelel az S k¨ oz´eptengely´enek. Ennek a pontos defin´ıci´ oja a [6]-ban tal´ alhat´ o.
22
FAZEKAS ATTILA
17. ´ abra
A tov´abbiakban a cikk azon elm´eleti eredm´enyeit ismertetj¨ uk, amelyek a fenti algoritmus elemz´es´ere vonatkoznak. 7.2. T´ etel [6]. Ha S nem¨ ures digit´ alis halmaz ´es a T sablon t¨ obb, mint egy elemet tartalmaz, akkor S T sem u ¨res halmaz. Bizony´ıt´ as [6]. Nyilv´ anval´ o, hogy S T v´eges. Ugyanis S v´eges ´es S T = S \ (S⊕ ⊗T ) ⊆ S. Tegy¨ uk fel, hogy S T u ¨res, azaz (S⊕ ⊗T ) ⊇ S, ekkor pedig (S Tˇ) ⊇ S. Azonban az er´ ozi´ o defin´ıci´ oj´ ab´ ol k¨ ovetkezik, hogy S Tˇ =
\ B∈Tˇ
SB = S
\
(
\
SB ).
B6=(0,0) B∈Tˇ
Az azt jelenti, hogy S Tˇ ⊂ S, ez azonban ellentmond´ as. Teh´ at S T nem¨ ures. 7.3. K¨ ovetkezm´ eny [6]. Ha S nem¨ ures digit´ alis halmaz ´es T olyan szerkeszt˝ o sablonok v´eges sorozata, amelyek mindegyike tartalmazza az eredetit, ´es egyn´el t¨ obb elemet tartalmaz, akkor {S T }k = Ψ(S, T, k) is nem¨ ures digit´ alis halmaz minden pozit´ıv k-ra. 7.4. T´ etel [6]. A 7.2. t´etel felt´eteleit ´es jel¨ ol´eseit haszn´ alva S egy nem¨ ures digit´ alis halmazhoz konverg´ al v´eges iter´ aci´ on bel¨ ul. Bizony´ıt´ as [6]. Tegy¨ uk fel, hogy nincs olyan k term´eszetes sz´ am, ami kiel´eg´ıti a konvergencia felt´etelt, azaz Ψ(S, T, k + 1) = Ψ(S, T, k) ahol Ψ a v´ekony´ıt´ o transzform´ aci´ o. Mivel a szerkeszt˝ o mint´ ak mindegyike kiel´eg´ıti a 7.3. k¨ ovetkezm´eny felt´eteleit, ez´ert ezt ´es a k¨ ovetkezm´enyt alkalmazva azt kapjuk, hogy ∅ ⊂ Ψ(S, T, k + 1) ⊂ Ψ(S, T, k) ⊂ · · · ⊂ Ψ(S, T, 1) ⊆ S ami ellentmond annak a t´enynek, hogy {S T }k nem¨ ures egyetlen pozit´ıv k-ra sem. Azt is meg lehet mutatni, hogy ψ(S, T, k + t) = Ψ(S, T, k) minden t term´eszetes sz´ amra. 7.5. T´ etel [6]. Ebben a fejezetben ismertetett v´ekony´ıt´ o algoritmus ´ altal szolg´ altatott I v´ az egy pixel vastags´ ag´ u. Bizony´ıt´ as [6]. Nyilv´ anval´ o, hogy ha I nem tartalmaz egy 2×2-es n´egyzetes mint´ at sem a 17. ´ abr´ an l´ athat´ ok k¨ oz¨ ul, akkor I egy pixel vastags´ ag´ u. Azonban, ha tal´ aln´ ank egy vagy t¨ obb 2 × 2-es mint´ at I-ben, akkor vagy I nem egy pixel vastags´ ag´ u vagy I kritikus pontot tartalmaz. Legyen P egy olyan speci´ alis pontja I-nek, hogy
´ ¨ O ˝ ALGORITMUSOK A DIGITALIS ´ ´ ´ VAZKIJEL OL KEPFELDOLGOZ ASBAN
23
P ∈ I Aˇ1 . Most vizsg´ aljuk meg r´eszletesen a P pontot. K¨ onny˝ u l´ atni, hogy csak ot olyan lehets´eges minta l´etezik a 3 × 3-as ablakban, ami tartalmazza az Aˇ1 sablont ¨ (l´ asd a 15. , 16. ´es 18. ´ abr´ at). Teh´ at [ [ [ [ (7.1) P ∈ (I⊕ ⊗B 1 ) (I⊕ ⊗C) (I⊕ ⊗D1 ) (I⊕ ⊗E 1 ) (I⊕ ⊗E 4 ). Hasonl´ ok´eppen, ha P ∈ I⊕ ⊗Aˇ2 , P ∈ I⊕ ⊗Aˇ3 vagy P ∈ I⊕ ⊗Aˇ4 , ´ıgy [ [ [ [ (7.2) P ∈(I⊕ ⊗B 2 ) (I⊕ ⊗C) (I⊕ ⊗D2 ) (I⊕ ⊗E 1 ) (I⊕ ⊗E 2 ), [ [ [ [ (7.3) P ∈(I⊕ ⊗B 3 ) (I⊕ ⊗C) (I⊕ ⊗D3 ) (I⊕ ⊗E 2 ) (I⊕ ⊗E 3 ) vagy [ [ [ [ P ∈(I⊕ ⊗B 4 ) (I⊕ (7.4) ⊗C) (I⊕ ⊗D4 ) (I⊕ ⊗E 3 ) (I⊕ ⊗E 4 ). S S S Minden P ∈ I A helyett ´ırhatunk P ∈ (I A1 ) (I A2 ) (I SA3 ) (I S A4 )-t. i 1 2 S˝ ot, Saz A -k szimmetri´ aj´ at felhaszn´ alva ´ırhatunk P ∈ (I Aˇ ) (I Aˇ ) (I Aˇ3 ) (I Aˇ4 )-et. V´eg¨ ul a (7.1)-(7.4) ´ırhat´ o a k¨ ovetkez˝ o alakban is: [ [ [ (7.5) P ∈ (I⊕ ⊗B) (I⊕ ⊗C) (I⊕ ⊗D) (I⊕ ⊗E). Azonban az S 0 ´es I halmazok azok, amelyekhez az algoritmus els˝ o, illetve m´ asodik ciklusai konverg´ alnak, ´ıgy S 0 ⊕ ⊗D = ∅ ´es I⊕ ⊗E = ∅. Ez´ert (7.5) a k¨ ovetkez˝ o alakban ´ırhat´ o: [ [ (7.6) P ∈ (I⊕ ⊗B) (I⊕ ⊗C) (I⊕ ⊗D). Most vizsg´ aljuk meg az I⊕ ⊗D kifejez´est. Ha S 0 -nek nincs E-beli mint´ aja, azaz 0 S⊕ ⊗E = ∅, akkor I = S 0 ´es I⊕ ⊗D = ∅. Ha l´etezik legal´ abb egy minta S-en, p´eld´ aul E 0 ∈ S 0 , akkor meg kell vizsg´ alnunk, hogy mit kapunk, ha egy P ∈ S 0 ⊕ ⊗E 0 0 pontot elt´ avol´ıtunk S -b˝ ol. K¨ onnyen ellen˝ orizhetj¨ uk, hogy ha S⊕ ⊗E 6= ∅, D-beli minta sohasem lehet az S 0 E r´eszhalmaza, teh´ at I⊕ ⊗D = ∅. Innen a (7.6) tov´ abb egyszer˝ us¨ odik [ P ∈ (I⊕ ⊗B) (I⊕ ⊗C), ahol B ´es C az ¨ osszes lehets´eges kritikus minta. Ezzel a t´etelt bebizony´ıtottuk.
18. ´ abra
7.6. T´ etel [6]. Ha az S 8-¨ osszef¨ ugg˝ o, akkor I is 8-¨ osszef¨ ugg˝ o. 7.7. T´ etel [6]. Ha S w 4-¨ osszef¨ ugg˝ o, akkor I w is 4-¨ osszef¨ ugg˝ o. 7.8. T´ etel [6]. Ha S 8-¨ osszef¨ ugg˝ o, akkor a Ψ v´ekony´ıt´ o elj´ ar´ as minden l´ep´esben pontosan akkor ˝ orzi meg a homot´ opi´ at, ha [ [ S \ Ψ(S) ⊆ (S⊕ ⊗Di ) (S⊕ ⊗Di+1 ) (S⊕ ⊗E i ) i = 1, 2, 3, 4 A fenti t´etelek bizony´ıt´ as´ at megtal´ aljuk a [6]-ban.
24
FAZEKAS ATTILA
¨ ´s Osszefoglal a Az algoritmusok empirikus vagy elm´eleti vizsg´alata t´ ul mutat ezen cikk keret´en. Azt a feladatot sem v´ allaltuk fel, hogy az egyes algoritmusokat j´o”, illetve rossz” ” ” min˝os´ıt´essel l´ assuk el. Ez az´ert is neh´ez feladat lenne, mert az egyes alkalmaz´asok eset´en m´as-m´ as eredm´enyt szolg´ altatnak az algoritmusok. Az irodalomban tal´alhat´o utal´asok alapj´ an kider´ıthet˝ o, hogy a szerz˝ok az algoritmusokat ´altal´aban konkr´et alkalmaz´asok c´elj´ ara tervezt´ek. ´Igy az utal´asok ismeret´eben megeml´ıthetj¨ uk, hogy p´eld´aul a [27]-ben tal´ alhat´ o algoritmus a k´ınai karakterek, [25] az arab karakterek, [7] az ujjlenyomatok eset´en ny´ ujt j´ o eredm´enyt. ´k Irodalomjegyze [1]. Azriel Rosenfeld, A Characterization of Parallel Thinning Algorithms, Information and Control 29 (1975), 286–291. [2]. Azriel Rosenfeld, Image Analysis and Computer Vision: 1992, CVGIP: Image Understanding 58 (1993), 85–135. [3]. Andrew K. Hrechak, James A. McHugh, Automated Fingerprint Recognition Using Srtructural Matching, Pattern Recognition (1990), 893–903. [4]. Azriel Rosenfeld, Avinash C. Kak, Digital Picture Processing, Academic Press, 1992. ´ o G., Heged˝ [5]. All´ us-Gy. Cs., Kelemen D., Szab´ o J., A digit´ alis k´ epfeldolgoz´ as alapprobl´ em´ ai (1989). [6]. Ben-Kwei Jang, Roland T. Chin, Analysis of Thinning Algorithms Using Mathematical Morphology, IEEE Transactions on Pattern Analysis and Machine Intelligence 12 (1990), 541–551. [7]. Buz´ asi K., Fazekas G., Peth˝ o A., Szab´ o E., Sz´ am´ıt´ og´ epes karakterfelismer˝ o m´ odszerek, K´ ezirat, KLTE (1988), 86–94. [8]. Christian Ronse, A topological characterization of thinning, Theoretical Computer Science 43 (1986), 31–41. [9]. Carlo Arcelli, Pattern thinning by contour tracing, Computer Graphics and Image Processing 17 (1981), 130–144. [10].Chyuan Jy Wu, Jun S. Huang, Human Face Profile Recognition by Computer, Pattern Recognition 23 (1990), 255–259. [11].Chin-Sung Chen, Wen-Hsiang Tsai, A New Fast One-Pass Thinning Algorithm and Its Parallel HardwareImplementation, Pattern Recognition Letters 11 (1990), 471–477. [12].E. S. Deutsch, Thinning Algorithms on Rectangular, Hexagonal, and Triangular Arrays, Communications of the ACM 15 (1972), 827–837. [13].Fazekas A., Herendi Tam´ as, Methods and applications of digital image processing, Bulletins for Applied Mathematics 91 (1991), 369–378. [14].G. X. Ritter, J. N. Wilson, J. L. Davidson, Image Algebra: An Overview, Computer Vision, Graphics, and Image Processing 49 (1990), 297–331. [15].Jean Serra, Introduction to Mathematical Morphology, Computer Vision, Graphics, and Image Processing 35 (1986), 283–305. [16].J. R. Parker, A System for Fast Erosion and Dilation of Bi-level Images, Journal of Scientific Computing 5 (1990), 187–198. [17].Louisa Lam, Seong-Whan Lee, Ching Y. Suen, Thinning Methodologies — A Comprehensive Survey, IEEE Transactions on Pattern Analysis and Machine Intelligence 14 (1992), 869–882. [18].Liang Ji, Jim Piper, Fast Homotopy – Preserving Skeletons Using Mathematical Morphology, IEEE Transactions on Pattern Analysis and Machine Intelligence 14 (1992), 653–664. [19].Masahiro Kawagoe, Akio Tojo, Fingerprint Pattern Classification, Pattern Recognition 17 (1984), 295–303. [20].Nabil Jean Naccache, Rajjan Shinghal, An Investigation into The Skeletonization Approach of Hilditch, Pattern Recognition 17 (1984), 279–284. [21].Paul C. K. Kwok, A Thinning Algorithm by Contour Generation, Communications of the ACM 31 (1988), 1314–1324. [22].Pavan Kumar, Deepak Bhatnagar, P. S. Umapathi Rao, Pseudo One Pass Thinning Algorithm, Pattern Recognition Letters 12 (1991), 543–555.
´ ¨ O ˝ ALGORITMUSOK A DIGITALIS ´ ´ ´ VAZKIJEL OL KEPFELDOLGOZ ASBAN
25
[23].Rei-Yao Wu, Wen-Hsiang Tsai, A new one-pass parallel thinning algorithm for binary images, Pattern Recognition Letters 13 (1992), 715–723. [24].Raymond W. Smith, Computer Processing of Line Images: A Survey, Pattern Recognition 20 (1987), 7–15. [25].Sabri A. Mahmoud, Ibrahim AbuHaiba, Roger J. Green, Skeletonization of Arabic Characters Using Clustering Based Skeletonization Algorithm (CBSA), Pattern Recognition 24 (1991), 453–464. [26].Shiaw-Shian Yu, Wen-Hsiang Tsai, A New Thinning Algorithm for Gray-Scale Images by the Relaxation Technique , Pattern Recognition 23 (1990), 1067–1076. [27].S. Riazanoff, B. Cervelle, J. Chorowicz, Parametrisable Skeletonization of Binary and Multilevel Images, Pattern Recognition Letters 11 (1990), 25–33. [28].S. K. Parui, A. Datta, A parallel algorithm for decomposition of binary objects through skeletonization, Pattern Recognition Letters 12 (1991), 235–240. [29].Satoshi Suzuki, Keiichi Abe, Binary Picture Thinning by an Iterative Parallel Two-Subcycle Operation, Pattern Recognition 20 (1987), 297–307. [30].Theo Pavlidis, A Thinning Algorithm for Discrete Binary Images, Computer Graphics and Image Processing 13 (1980), 142–157. [31].Ulrich Eckhard, A theoretical basis for thinning methods, Computer Analysis of Images and Pattern, Proceedings of the III.International Conference CAIP’89 on Automatic Image Processing (1989), 65–70. [32].Y. F. Tsao, K. S. Fu, A Parallel Thinning Algorithm for 3-D Pictures, Computer Graphics and Image Processing 17 (1981), 315–331. [33].Yung-Sheng Chen, Wen-Hsing Hsu, A comparison of some one-pass parallel thinnings, Pattern Recognition Letters 11 (1990), 35–41. [34].Zicheng Guo, Richard W. Hall, Parallel Thinning with Two-Subiteration Algorithms, Communications of the ACM 32 (1989), 359–373. ´nyegyetem Matematikai ´ Fazekas Attila, Kossuth Lajos Tudoma es Informatikai Int´ ezet, 4010 Debrecen Pf.12 E-mail address:
[email protected]
