Elektrotehniški vestnik 79(3): 129-134, 2012 Existing separate English edition Primerjava razčlenjevanja magnetnoresonančnih slik z uporabo postopkov &-tih in mehkih c-tih povprečij rojenja Tomaž Finkšt Univerza v Ljubljani, Fakulteta za strojništvo, Aškerčeva 6, 1000 Ljubljana, Slovenija E-pošta: tomaz.finkst@fs.uni-lj.si Povzetek. Pri obdelavi medicinskih slik se v zadnjih letih čedalje pogosteje uporabljajo različne slikovne tehnike za razpoznavanje objektov. Pri obdelavi slik je razčlenjevanje ključni postopek, pomemben za pravilno izločanje, analizo in interpretacijo slikovne vsebine. Informacijska vsebina medicinskih slik je ključnega pomena za odkrivanje in razumevanje normalnih in bolezenskih stanj človeškega organizma. Raziskave se nanašajo na dva pogosta postopka rojenja, in sicer na postopek k-tih povprečij in mehki postopek c-tih povprečij. Ta dva postopka smo izvedli na bazi magnetnoresonančnih slik možganov in jih primerjali z ročno razčlenjenimi. Pri primerjavi obeh postopkov smo prišli do sklepa, da je mehki postopek c-tih povprečij v vseh pogledih boljši od postopka k-tih povprečij. Prednost tega postopka je tako imenovana mehkoba oziroma da lahko vzorci pripadajo roju z določeno stopnjo pripadnosti. Ključne besede: razčlenjevanje slik, mehka metoda c-tih povprečij, metoda k-tih povprečij, magnetnoresonančne slike Evaluation of Segmentation in Magnetic Resonance Images using K-Means and Fuzzy C-Means Clustering Algorithms The purpose of cluster analysis is to partition a data set into a number of disjoint groups or clusters. Members within a cluster are more similar to each other than to members from different clusters. This research work deals with two of the most delegated clustering algorithms, which are centroid based k-means and representative object based fuzzy c-means. These two algorithms are implemented and the performance is analyzed based on the quality of their clustering results. The behaviors of both algorithms depend on the number of data points as well as on the number of clusters. The algorithms are implemented in MATLAB for the two-dimensional multispectral magnetic resonance (MRI) image segmentation. 1 Uvod Slikovne tehnike so postale temeljno orodje v sodobni medicini. Njihova uporaba pomaga v zdravniški praksi na različne načine, od diagnosticiranja zlomov kosti, odkritja rakastih tvorb do slikovno vodenih kirurških posegov. V uporabi so številne slikovne tehnike, kjer vsaka od njih prikazuje slikani objekt na drugačen način. Čeprav različne slikovne modalnosti, dobljene z različnimi tehnikami slikanja, v osnovi prikazujejo različne informacije, med njimi ostajajo tudi nekatere podobnosti. Na primer, medicinske slike so bolj ali manj pošumljene svetlostne slike na črnem ozadju, ki predstavlja okoliški zrak. Torej je na tako rekoč vseh medicinskih slikah opazen zunanji obris med slikanim objektom in okolico. Z uvedbo slikovnih postopkov [1], kot so: magnetna resonanca (MR), ultrazvok (US), računalniška tomografija (CT) in druge, je omogočen boljši vpogled v zgradbo anatomskih struktur. Pomemben korak postopkov razčlenjevanja medicinskih slik je definicija področja, na podlagi katere sliko razčlenjujemo. Razčlenjevanje slik lahko temelji na analizi prostora značilk slikovnih elementov, analizi homogenosti povezanih slikovnih elementov, iskanju robov med različnimi območji v prostoru slike ali na analizi fizikalnih lastnosti površin, ki jih predstavlja slika [2]. Magnetnoresonančno (MR) slikanje [3, 4, 5] spada med anatomske slikovne tehnike in je v nasprotju s CT za človeško telo neinvazivna slikovna tehnika. Nastane kot odziv vodikovih atomov v telesu na zunanje magnetno vzbujanje. Slikano telo se mora nahajati v močnem stalnem magnetnem polju, tako da gostota magnetnega polja doseže od 0.04 do 4 Tesla. Obstaja več različnih postopkov magnetnoresonančnega zajemanja slik, ki dajo različno informacijo o slikanem tkivu in tako predstavljajo različne modalnosti. Uveljavljene modalnosti MR slikanja so T1, T2 in PD. MR slikanje odlikuje dober kontrast med različnimi tipi tkiv in je zato primerno za podroben prikaz anatomije. Uporablja se predvsem za diagnosticiranje tumorjev in drugih nepravilnosti možganskega tkiva. Za Prejet 31. maj, 2012 Odobren 4. junij, 2012 pravilno vrednotenje rezultatov razčlenjevanja MR-slik je treba imeti tako ročno obrisana območja kot tudi območja, ki jih obrišejo različni postopki. Glede na primerjavo subjektivne presoje zdravnikov specialistov in samodejnih postopkov razčlenjevanja lahko vrednotimo samodejne postopke razčlenjevanja MR slik. Spoznavanje področja uporabe vzorcev objektov temelji na samodejnem razvrščanju (rojenju, samoorganizaciji) vzorcev iz dane množice in njihovem označevanju glede na pripadnost rojem (angl. clustering) [6]. S tem dano množico vzorcev preslikamo v učno množico vzorcev, ki jo pregleda in prilagodi še kompetentna oseba - učitelj oziroma strokovnjak za določeno področje uporabe. V našem primeru je namen omenjenih postopkov ugotavljanje rojenja vzorcev. S temi postopki preslikamo oziroma razbijemo dano množico vzorcev v podmnožice, kjer preslikava temelji na merjenju podobnosti vzorcev. Pri tem pričakujemo, da so v posameznem roju med seboj čim bolj podobni vzorci. Podobnost med dvema vzorcema merimo s preslikavo, ki primerjana vzorca preslika v realno število. Podobnost med vzorci, ki so predstavljeni s krajevnimi vektorji značilk, ponavadi merimo z razdaljami, med katerimi se najpogosteje uporablja Evklidova razdalja. Pri teh razdaljah manjše realno število pomeni večjo podobnost med primerjanima vzorcema. V obeh postopkih, tako k-tih povprečij (angl. k-means (kM)) in mehkih c-tih povprečij (angl. fuzzy c-means (FcM)) je treba na začetku nastaviti središče rojev [7]. Vhodni vektorji (podatkovne točke) so nato dodeljeni v enega od obstoječih rojev glede na kvadrat evklidske razdalje od roja, ki je najbližji. Povprečje (sredino) vsakega roja nato izračunamo tako, da dopolnimo središče roja. Ta posodobitev je posledica spremembe v pripadnosti za vsak roj. Združevanje vhodnih vektorjev in posodobitev središč rojev ponavljamo, dokler ni več sprememb vrednosti katerih koli središč rojev. V zadnjem času se postopek c-tih povprečij uporablja v nenadzorovanih postopkih rojenja na podlagi vidnih rezultatov pri samodejnem razčlenjevanju medicinskih slik [7,8,9,10]. Rojenje z mehkim postopkom c-tih povprečij [11,12,13] uspešno uporabljamo na številnih področjih, kot so astronomija, geologija, medicinsko slikanje in razčlenjevanje slik. Omenjena mehka razčlenjevalna metoda ima precejšnje prednosti, ker lahko ohrani veliko več informacij iz prvotne slike kot klasične razčlenjevalne metode [11]. Dva preprosta pristopa za začetno nastavitev središča roja sta naključna izbira začetne vrednosti ali izbira prvih k-vzorcev iz podatkovnih točk. Različne množice začetnih vrednosti so izbrane (zunaj podatkovnih točk) in izbrana je množica, ki je najbližja optimalni. Vendar pa je testiranje različnih začetnih vrednosti množic praktično neizvedljivo zaradi velikega števila rojev [9]. V literaturi [7,14,15,16] so bile predlagane različne metode. Rojenje je učinkovito orodje pri razčlenjevanju medicinskih slik in za nadaljnje načrtovanje zdravljenja. V MR slikah možganov je možgansko tkivo zapletena struktura in s tem je pravilna diagnoza številnih bolezni možganov v veliki meri odvisna od natančnega razčlenjevanja treh možganskih tkiv, in sicer belega tkiva (WM), sivega tkiva (GM) in cerebrospinalne tekočine (CSF). 2 Razčlenjevanje slik Proces razčlenjevanja je razdelitev slike na neprekrivajoča se območja, tako da vsako območje ustreza kriteriju homogenosti [17], ki jo definiramo takole: naj bo f (x,y) množica vrednosti značilk v različnih točkah koordinatnega sistema slike in P() predikat homogenosti, definiran nad skupino povezanih slikovnih elementov. Razčlenjevanje je razdelitev slike f (x, y) na n povezanihpodmnožic oziroma območij (S1,S2,...,Sn), tako da velja: |JS,.=/(x,>0 ; St S j = 0, i* j. (!) i=i Predikat homogenosti ima za vsako območje S. vrednost P (S.) = 1, medtem ko je vrednost predikata za povezani sosednji območji P(St ^ S) = 0. Ta definicija je splošna za vse tipe slik. Tako predikat homogenosti pomeni pri svetlostnih sivinskih slikah kriterij homogenosti svetlostne intenzitete, pri globinskih slikah pa kriterij homogenosti globinskega reliefa površin. Pri vektorskih slikah pa predikat definira homogenost barve ali teksture. V literaturi zasledimo veliko postopkov razčlenjevanja slik, vendar noben od njih ni optimalen za razčlenjevanje vseh tipov slik, pa tudi vse metode ne dajejo enakih rezultatov razčlenjevanja za isti tip slike. Podroben pregled metod razčlenjevanja sivinskih slik je podan v literaturi [17]. Postopki, razviti za določen tip slik, na primer svetlostne sivinske slike, niso vedno uporabni za magnetnoresonančne slike. Zato si v takšnem primeru pomagamo pri razčlenjevanju slike z modelom nastanka slike. Izbira primerne metode razčlenjevanja je zahtevna, ker ni splošne metode vrednotenja razčlenjene slike. Pavlidis [18] meni, da je razčlenjevanje vizualnih slik problem psihofizičnega zaznavanja. Vsak matematični postopek je ponavadi dopolnjen s hevristiko, ki vključuje znanje o vhodni sliki. Na splošno obstajata dva pristopa razčlenjevanja slik [17]: klasični in mehki matematični pristop. Opazno je pomanjkanje metod za objektivno vrednotenje rezultatov razčlenjevanja. Objektivna primerjava metod razčlenjevanja je bila podana za globinske slike [19]. V tem primeru je primerjalna referenca za razčlenjevanje globinskih slik dobro definirana. Bistvo razčlenjevalnih postopkov je združevanje delov slike z dovolj sorodnimi lastnostmi v en oziroma v isti objekt [6]. Obstaja množica razčlenjevalnih postopkov, katerih uporabnost je od primera do primera različna. Ni pa univerzalnega razčlenjevalnega postopka. V našem primeru smo uporabili za razčlenjevanje slik postopek rojenja [6]. Najbolj znana postopka rojenja sta postopek k-tih povprečij in mehki postopek c-tih povprečij. Obstaja še vrsta drugih razčlenjevalnih metod, ki pa že poznajo in upoštevajo določene lastnosti anatomije razčlenjenih slik. Postopke rojenja [6] na splošno razdelimo po načelu: objektivni, grafično-teoretični, hierarhični, ali po vrsti vzorcev: deterministični, statistični, mehki. V nadaljevanju bosta uporabljeni neskončni družini objektivnih funkcij postopkov rojenja, imenovani metoda rojenja k-tih povprečij in mehka metoda rojenja c-tih povprečij . Vse to kaže velik napredek tako teorije kot uporabe teh dveh postopkov v zadnjih letih [12]. 2.1 Postopek k-tih povprečij Postopek k-tih povprečij, ki ga uvrščamo med parametrične postopke rojenja, temelji na minimizaciji kriterijske funkcije J. V vsaki iteraciji izračuna srednjo intenziteto za vsak razred in potem razčleni sliko tako, da vsak slikovni element dodeli v razred, ki ima intenziteti slikovnega elementa najbližjo srednjo vrednost intenzitete. Ena najpogosteje uporabljanih kriterijskih funkcij je vsota kvadratov razdalj med vzorci v roju (enačba (2)) in aritmetična sredina roja (enačba (3)): Nc N J = X XI |xc, j=1 ¿=1 1 N C, = — X X j Nj. X1 (2) (3) kjer je x n-dimenzionalni vzorec, N število rojev, S. j-ti roj vzorcev. roja N. pa je število vzorcev v roju S . Postopek k-tih povprečij lahko strnemo v naslednje korake: (1) V prvi iteraciji izberemo število vseh vzorcev, ^(1)^(1),...,^ (1). Nc < N, N je središč rojev (2) V k-ti ponovitvi postopka razdelimo vzorce v N rojev. Vzorec x uvrstimo v roj j, če: ||x — m j (k )|| < | |x — mi (k )|| V/ = 1,2,...,Nc a/* j. (3) Izračunamo nova središča rojev (4) Če je cJ(k + \) = cJ(Jc) za j = \2,...,Nc, je postopek končan. Uporaba tega postopka na splošno zahteva eksperimentiranje z različnimi začetnimi središči rojev in če vnaprejšnje število rojev ni znano, tudi z različnim številom rojev. Začetna središča rojev smo poiskali s pomočjo hierarhičnega postopka rojenja: najnižji nivo v hierarhiji rojenja je sistem, kjer je vsak vzorec sam zase v svojem roju, najvišji nivo pa rojenje vseh vzorcev v en sam roj [9]. Na vsakem nivoju rojenja, začenši z najnižjim, združimo dva najbolj podobna roja v en sam večji roj. Združena roja se na poznejših - višjih nivojih ne razdružita več. Postopek združevanja smo prekinili pri nivoju s tremi roji (tri vrste možganskih tkiv) in središča teh rojev smo uporabili kot začetna središča v postopku k-tih povprečij. 2.2 Mehki postopek c-tih povprečij Z mehkim rojenjem želimo podatke razdeliti na več mehkih rojev. Tako vsak vzorec pripada posameznemu mehkemu roju z določeno stopnjo pripadnosti, ki se izračuna glede na razdaljo vzorca do središč posameznih mehkih rojev, ki jih postopek določa v vsakem koraku sproti. Metoda mehkega rojenja c-tih povprečij temelji na minimizaciji kriterijske funkcije, ki jo podaja enačba (4) Jmr=X X( h, ) 1 |x --c j j=1 '=1 (4) c aritmetična sredina vzorcev j-tega V enačbi (4) je m izbrano realno število, pri čemer mora veljati 1 < m < . N je število vzorcev, Nc je število rojev, ^ je vrednost pripadnostne funkcije j-tega roja za i-ti vzorec x,.. c označuje središče roja j, ||x — c.| pa razdaljo, s katero je določena podobnost med središčem roja c in vzorcem x . V praksi najpogosteje uporabljamo Evklidsko razdaljo, ki jo podaja enačba (5). |=vx (5) Mehko rojenje se izvaja iterativno, pri čemer se v vsakem koraku sproti izračunavajo vrednosti pripadnostnih funkcij ^ , kot kaže enačba (6), in središča rojev c , kot kaže enačba (7). 2 2 X (6) Z 2 II V™-1) pri čemer za vsak i e {1..... N} velja ^ v | ju.. = 1 c j =■ Z M T- i=1_ N Z M )™ za Vi. (7) V enačbah (6) in (7) je i indeks posameznega vzorca, j in k pa označujeta indeks posameznega mehkega roja oziroma njegovega središča. Vrednost parametra m določa mehkost oz. ostrost porazdelitve pripadnostnih funkcij v prostoru. Za skrajni primer m = 1 velja, da so pripadnostne funkcije, ki so definirane nad prostorom, degenerirane v ostre stopnje pripadnosti. Pripadnostne funkcije lahko torej v vsaki točki prostora zavzamejo samo eno od vrednosti M&e{0,1}. Iz enačbe (6) vidimo, da je m = 1, če je norma ||x - cj za i-ti vzorec in središče j-tega roja najmanjša glede na vsa središča rojev. Za preostale roje pa velja Ht=0,kjerje k e {1,. ..,NC} ■ Za drugo skrajnost, m = x>, pa velja, da so pripadnostne funkcije degenerirano zmehčane, kar pomeni, da so vrednosti pripadnostnih funkcij po vsem prostoru enake: m= 1/ N, in sicer za vsak V praksi sta najpogosteje uporabljeni vrednosti parametra m = 1,25 ali m = 2 [20]. Postopek mehkega rojenja c-tih povprečij je opisan v nadaljevanju. (1) Izberemo število rojev Nc in parameter m ter določimo začetno matriko pripadnosti Y(0) = [Mj ]. (2) V k-ti iteraciji določimo središča rojev c. za j = \,...,Nc glede na T (k). (3) Določimo novo matriko pripadnosti Y(k +1) . (4) Če je ||Y(fc + 1)-