Metode de Segmentare a Imaginilor de Hemangiom

Universitatea Politehnica București

Facultatea de Inginerie Medicală

Specializarea: Sisteme și echipamente medicale

LUCRARE DE LICENȚĂ

Metode de segmentare a imaginilor de hemangiom

Absolvent Coordonator

Negrescu Noemi Prof.dr.ing. Elena Ovreiu

București, 2016

CUPRINS:

Introducere ………………………………………………………………..…1

Capitolul 1: Hemangioame……………………………………………………2

Capitolul 2: Spatii de culoare RGB…………………………………………..

Capitolul 3: Spatii de culoare LAB…………………………………..

Capitolul 4: Segmentarea imaginilor…………………………………….

INTRODUCERE…………………………………………………………………..

SEGMENTAREA IMAGINII………………………………………………

INTENSITY BASED SEGMENTATION…………………………………..

DISCONTINUITY BASED METHODS……………………………………………

REGION BASED SEGMENTATION……………………………………………..

CLUSTERING BASED METHODS………………………………………….

HYBRID METHODS………………………………………………………….

GRAPH BASED METHODS………………………………………………….

PIXON BASED METHOD…………………………………………………………..

Chapter 5: Algoritmul Fuzzy C-Means……………………………………………

Capitolul 6: Concluzii.…………………………………………

Bibliografie…………………………………………………………………

Anexe

INTRODUCERE

CAPITOLUL 1

HEMANGIOAME

Hemangioamele infantile (IH) sunt tumori de origine vasculară, care sunt prezente la nastere sau se dezvolta la câteva săptămâni după. Diagnosticul diferential al malformatiilor vasculare este dificil de stabilit. IH care afectează regiunile cefalică și cervicală (cele mai frecvente), zona genitală sau extremitățile, in functie de localizare, dimensiuni și evoluția rapidă, pot determina sechele functionale si estetice importante, debilitante pentru pacient. Pentru a evita aceste consecințe nefaste, este necesar să se stabilească exact momentul oportun pentru a începe tratamentul și să se decidă care este procedura terapeutică cea mai adecvată.

Până în prezent, la nivel internațional, nu există nicio metodă standard de diagnosticare a hemangioamelor infantile, nici un mijloc de a prezice progresul lor din punct de vedere clinic și posibilele complicații care pot aparea. Tratamente utilizate în prezent se bazează numai pe observația subiectivă, instinctul și experiența medicului curant, susținută de dezvoltarea tehnică și farmacologică în medicină.

Proiectul propus intenționează (pe baza datelor clinice colectate prin observații clinice în serie, corelate cu date imagistice) dezvoltarea un algoritm de tratament pentru a prezice cu exactitate cele mai bune rezultate finale, din punct de vedere estetic și funcțional, pentru un anumit tip de leziune.

În scopul de a atinge acest obiectiv, vom folosi și/sau vom dezvolta metode moderne pentru a procesa imagini medicale și algoritmi inteligenți pentru a ajuta la diagnostic (CAD). Software-ul va incorpora metode avansate pentru măsurarea precisă a leziunilor IH specifice, se vor integra informații medicale rezultate în urma observațiilor clinice și se vor integra metode statistice și/sau metode de calcul inspirate din natură (de exemplu: dinamica neliniare, retele neuronale celulare, retele neuronale artificiale) pentru a corela aceste informații cu cele obținute din prelucrarea imaginilor. Pe baza acestor corelații vom stabili un mecanism de predicție a evoluției hemangioamelor. Acest lucru va ajuta la determinarea celei mai bune metode de interventie terapeutica pentru minimizarea complicațiilor.

Impactul științific și tehnologic al proiectului constă în dezvoltarea acestor metode inovatoare. Punerea în aplicare a acestora va avea ca rezultat un tip de dispozitiv medical care va contribui în mod evident, pentru a crește competitivitatea economiei românești, având în vedere faptul că existența unui astfel de produs, care are ca scop de a îmbunătăți într-adevăr calitatea vieții copiilor afectați de o patologie estetică și funcțională deformatoare, este o necesitate.

Produsul implica reale beneficii de sanatate atat pentru pacienti cat si pentru sistemul de sanatate, acesta primind o minimizare a costurilor pentru fiecare pacient în aceast caz. Prin scăderea numărului de proceduri și prin definirea unei strategii terapeutice unice pentru tratarea unui pacient, pot fi salvate sume de bani si în consecință, alocate în beneficiul altor nevoi. Mai mult decât atât, în cazul în care rezultatele estetic si functional sunt maximizate, vom salva resursele alocate pentru reintegrarea pacientului în societate, ceea ce este mai costisitor în cazul în care gradul de eșec este mai mare. Diminuarea perioadei de monitorizare a bolii, accelerarea diagnosticului, reducerea timpului de spitalizare, o mai rapida integrare socială a pacienților sunt doar câteva avantaje pe care un astfel de produs le-ar aduce, nu numai pentru pacienți, dar si pentru sistemul medical național și european, de asemenea.

Consorțiul format din Universitatea "Carol Davila" de Medicină și Farmacie București (coordonator de proiect), Universitatea Politehnica din Bucuresti (P1), Universitatea Valahia din Târgoviste (P2) și Medical Technologies & Research Company (P3) a format o echipă unită in vederea punerii în aplicare cu succes a proiectului. Proiectul se va derula pe o perioadă de 24 de luni, cu un buget de 1,437,500 lei, și implică o echipă de 17 cercetători, trei doctoranzi și un student post-doctorat.

CAPITOLUL 2

SPATII DE CULOARE RGB

CAPITOLUL 3

SPAȚII DE CULOARE Lab

Un spațiu de culoare Lab este un spațiu de culoare adversar cu dimensiunea L pentru luminozitate, iar a și b pentru dimensiunile de culoare adversara, bazat pe coordonate nonliniare comprimate (de exemplu, spațiul de culoare CIE XYZ). Terminologia provine din cele trei dimensiuni ale spațiului de culoare Hunter 1948, care sunt L, a și b. [1] [2] Cu toate acestea, Lab este acum mai des folosit ca abreviere informală pentru reprezentarea Lab a spațiului de culoare CIE 1976 (sau CIELAB, descris mai jos). Diferența dintre original culoarea Hunter și CIE coordonează este că coordonatele CIE se bazează pe o transformare cub rădăcină a datelor de culoare, în timp ce coordonatele Hunter se bazează pe o transformare rădăcină pătrată. Alte exemple de spații de culoare cu reprezentări Lab includ spațiul de culoare CIE 1994 și spațiul de culoare CIE 2000.

L * a * b * spațiu de culoare include toate culorile perceptibile, ceea ce înseamnă că gamut sa depășește pe cele ale modelelor de culoare RGB și CMYK (de exemplu, ProPhoto RGB include aproximativ 90% toate culorile perceptibile). Una dintre cele mai importante atribute ale L * a * b * -Model este independenta de dispozitiv. Acest lucru înseamnă că culorile sunt definite independent de natura lor de creație sau dispozitivul în care sunt afișate. L * a * b * spațiu de culoare este utilizat atunci când grafica pentru imprimare trebuie să fie convertite din RGB la CMYK, ca L * a * b * gamut include atat RGB si CMYK gama. De asemenea, este folosit ca un format de transfer între dispozitive diferite ca și pentru dispozitivul său independențe. Spațiul în sine este un spațiu tridimensional număr real, care conține un infinit reprezentări posibile de culori. Cu toate acestea, în practică, spațiul este, de obicei, mapat pe un spațiu întreg tridimensional pentru reprezentare digitală independentă de dispozitiv, precum și din aceste motive, L *, a *, iar valorile b * sunt, de obicei absolută, cu un interval predefinit . Lejeritatea, L *, reprezintă cel mai închis negru la L * = 0, iar cea mai strălucitoare alb la L * = 100. Canalele de culoare, un * și b *, vor reprezenta adevărate valori neutre de gri la * = 0 și b * = 0. rosii culorile / adversarului verde sunt reprezentate de-a lungul axei un *, cu verde, la un valori negative * și roșu la un valori pozitive *. Galbenă / culorile adversarului albastru sunt reprezentate de-a lungul axei b *, cu albastru la valori negative, b * și galben la valori pozitive b *. Scalarea și limitele unei axe * și b * va depinde de implementarea specifică de culoare Lab, așa cum este descris mai jos, dar de multe ori rula în intervalul de ± 100 sau -128-127.

Atât Hunter și spațiile de culoare 1976 CIELAB au fost derivate din anterioară "maestru" spațiu CIE 1931 XYZ spațiul de culoare, care poate prezice ce distribuții spectrală a puterii va fi percepută ca fiind aceeași culoare (a se vedea metamerism), dar care nu este deosebit de uniformă perceptiv . [3], puternic influențat de sistemul de culoare Munsell, intenția ambelor "Lab", spații de culoare este de a crea un spațiu care poate fi calculat prin formule simple din spațiul XYZ, dar este mai uniform perceptiv decât XYZ. [4] perceptiv uniformă înseamnă că o schimbare de aceeași valoare într-o valoare de culoare ar trebui să producă o schimbare de aproximativ aceeași importanță vizuală. Atunci când stocarea culorilor în valori de precizie limitate, acest lucru poate îmbunătăți reproducerea tonurilor. Ambele spații de laborator sunt raportate la punctul alb al datelor XYZ au fost convertite din. Valorile de laborator nu definesc culorile absolute, cu excepția cazului este de asemenea specificat punctul alb. De multe ori, în practică, punctul alb, se presupune să urmeze un standard și nu este menționat în mod explicit (de exemplu, pentru "colorimetric absolut" intenția de redare, Internațională Color Consorțiul L * a * b * Valorile sunt raportate la CIE D50 iluminant Standard, în timp ce acestea sunt în raport cu substratul netipărită pentru alte scopurile de randare). [5]

Corelativul lejeritate în CIELAB se calculează folosind rădăcina cub de luminanța relativă.

Spațiul de culoare Lab definit de către CIE (Commission Internationale de l'Eclairage) este bazat pe un singur canal pentru luminanță (luminozitate) (L)și două canale de culoare (a și b).

O problema cu sistemul de culoare XYZ, este faptul că distanțele colorimetrice între culorile individuale nu corespund diferențelor de culoare percepute. De exemplu, în

figura alăturată, o diferență între verde și galben-verzui este relativ mare,

întrucât distanța distinctivă dintre roșu și albastru este destul de mică. CIE a rezolvat această

problemă în 1976, odată cu dezvoltarea spațiului de culoare tridimensional Lab (sau spațiu de culoare CIELAB).

În acest model, diferențele de culoare pe care le percepem corespund distanțelor atunci când sunt măsurate colorimetric. O axă se extinde de la verde (-a) la roșu (+ a) și axa b

de la albastru (-b) până la galben (+b). Luminozitatea (L) modelului tridimensional crește de jos în sus.

Acest spațiu de culoare este potrivit pentru mai multe manipulări de imagine digitală decât spațiul RGB, care este folosit de obicei în programele de editare a imaginilor. De exemplu, spațiul Lab este util pentru conturarea imaginilor și eliminarea artefactelor din imagini JPEG sau din imagini de la camerele digitale și scanere.

Când se utilizează spațiul de culoare LAB

– la Vopsea de potrivire culori pe suporturi tipărite

– Culori tesatura de potrivire într-un catalog sau site

– Comunicarea ta culoarea preferată Pantone într-o altă formă de mass-media

– Spațiul de culoare LAB este back-os toată gestionarea culorilor între dispozitive din fluxul de lucru de culoare

CAPITOLUL 4

SEGMENTAREA IMAGINILOR

Segmentarea imaginii este etapa fundamentală pentru analiza imaginilor și extragerea datelor din ele. Este domeniul cercetat pe scară largă și oferă în continuare diferite provocări pentru cercetători. In continuare voi pune în lumină principiile de bază privind metodele utilizate pentru segmentarea imaginilor. Ma voi concentra pe ideea din spatele metodelor de bază utilizate. Segmentarea imaginilor poate fi clasificată în linii mari ca abordare semi-interactivă și abordare complet automată, iar algoritmii dezvoltați se incadreaza în oricare dintre aceste abordări. Segmentarea imaginilor este un pas crucial deoarece influențează în mod direct succesul pentru înțelegerea imaginii.

INTRODUCERE

O imagine este de fapt o funcție bidimensională a coordonatelor spațiale f(x, y), iar amplitudinea acestei funcții la anumite coordonate, dă valoarea intensității imaginii. Imaginea poate fi exprimată ca produsul funcțiilor de iluminare și de reflectare.

f (x, y) = i(x, y). r(x, y)

unde i(x, y) este funcția de intensitate și r(x, y) este funcția de reflectivitate.

Procesarea digitală a imaginii constă în aplicarea diferitor algoritmi pe imagine pentru a îmbunătăți calitatea acesteia prin eliminarea zgomotului și a altor pixeli nedoriți și de asemenea, pentru a obține mai multe informații despre imagine.

Printre diferitele tehnici de procesare a imaginii, segmentarea imaginii este pas foarte important pentru a analiza imaginea dată. M-am concentrat în principal pe această tehnică (segmentarea), diferitele metode prin care se relizeaza și câțiva algoritmi care sunt utilizați pe scară largă.

SEGMENTAREA IMAGINII

Segmentarea imaginii este o tehnică de procesare de nivel mediu utilizata pentru analiza imaginilor și poate fi definită ca o tehnică de prelucrare utilizată pentru a clasifica sau pentru a grupa o imagine în mai multe părți disjuncte, prin gruparea pixelilor pentru a forma o regiune de omogenitate pe baza caracteristicilor pixelilor precum nivelele de gri, culoarea, textura, intensitatea și alte caracteristici. Scopul principal al procesului de segmentare este de a obține mai multe informații în regiunea de interes într-o imagine care ajută în adnotarea scenei obiectului. Segmentarea imaginilor are ca scop partiția domeniului independent de imagine într-un set de regiuni distincte vizual și omogene în ceea ce privește anumite proprietăți. Principalul obiectiv al segmentării este de a diferenția în mod clar obiectul și fundalul într-o imagine.

Segmentarea imaginii este foarte utilă în aplicații medicale pentru a diagnostica anomaliilor din imagine, in imagistica prin satelit și în vizualizarea pe calculator precum și în ANN. Criteriile pentru a segmenta imaginea sunt foarte greu de stabilit deoarece variază de la o imagine la alta si de asemenea, variază în mod semnificativ si la modalitatile utilizate pentru a captura imaginea.

Metodele de clustering au fost discutate pentru segmentarea imaginilor medicale, în special pentru imagini MR ale creierului si sunt de succes în combinarea fuzzy-c means și k-means pentru a obține un nou algoritm fuzzy-k means. De asemenea, au fost declarate câteva limitări ale algoritmului obținut.

Tehnica hibrida pentru segmentarea imaginilor medicale funcționează în principal pe fuzzy c-means și metoda lui Otsu după aplicarea filtrului median pe vector; s-a încercat demonstrarea faptului ca metoda este complexa, prin adaugarea câtorva tipuri de zgomot imaginii; s-au obținut rezultate satisfăcătoare.

Yuri și Jolly au fost propus o nouă tehnică cu scopul general de segmentare interactivă a imaginilor N-dimensionale folosind metoda graph-cut. În aceasta metoda, utilizatorul va marca anumiti pixeli ca „obiect” sau „fundal” pentru a oferi constrângeri mai mari la segmentare.

Yuri si Jolly pretind că metoda lor oferă cel mai bun echilibru intre delimitarea regiunii și proprietățile acesteia în comparație cu alte metode segmentare și de asemenea, oferă o soluție optimă pentru segmentarea N-dimensionala.

SEGEMENTARE BAZATA PE INTENSITATE

Una dintre cele mai simple abordări pentru a segmenta o imagine este bazata pe nivelurile de intensitate și este denumita theshold based approach. Tehnicile theshold based clasifică imaginea în două clase și funcționează conform postulatului ca pixelii care aparțin unui anumit interval de valori de intensitate reprezintă o clasă și restul pixelilor din imagine reprezintă altă clasă. Binarizarea poate fi implementata atat la nivel global, cat si local. Binarizarea globală distinge obiectul și pixelii de fundal, prin compararea cu o valoare de prag aleasa și foloseste o partiție binara pentru segmentarea imaginii. Pixeli care trec pragul ales sunt considerati „pixeli obiect” și li se atribuie valoarea binară "1" și celorlalți pixeli li se atribuite valoare binară "0" și sunt considerati „pixeli fundal”. Tehnicile threshold based segmentation sunt ieftine, rapide computațional și pot fi utilizate în aplicații in timp real cu un ajutor hardware specializat.

Binarizarea locală este, de asemenea, numita binarizare adaptiva. În această tehnică valoarea prag variază în imagine în funcție de caracteristica locală a regiunii subdivizate din imagine. Algoritmul urmat pentru binarizarea adaptivapoate fi, în general, urmatorul:

1. Se împarte imaginea în sub-imagine.

2. Alegem un prag local considerat pentru sub-imagine.

3. Comparam pixelii din sub-imagine si segmentam regiunea.

4. Luam în considerare toate sub-imaginile în mod individual și de a alegem valorile prag corespunzătoare.

5. Oprim segmentarea când toate sub-imaginile sunt prelucrate.

În cazul binarizarii globale, valoarea prag aleasă rămâne aceeași pentru întreaga imagine și acționează ca o valoare „cutoff”. În cazul binarizarii locale imaginea este împărțită in sub-imagini și pragul este ales în funcție de proprietățile pixelilor locali din acea sub-imagine.

Valoarea prag poate fi modificata și sunt clasificate ca thresholding band, multi-thresholding si semithresholding. Fie ca avem binarizare globala sau binarizare locala, rezultatul se obține în funcție de valoarea pragului ales. Prin urmare, alegerea pragului este crucială și complicat. Există mai multe metode utilizate pentru detectarea valorii prag, cum ar fi: p-tile- thresholding, bimodal histogram, optimal thresholding, multispectral thresholding, edge maximization method. Dintre tehnicile disponibile pentru segmentarea threshold based, selecția pragului bazata pe histogramele sugerate de Nobuyuki Otsu în 1979 este cea mai utilizata, cu modificări minore. Metoda Otsu este optimă pentru binarizarea obiectelor mari din fundal. Aceasta metoda prevede un prag optim (sau un set de praguri) selectate după criteriul discriminant prin maximizarea mărimii discriminantului η (sau mărimea separabilitatii claselor rezultate în nivele de gri).

Celelalte abordări folosite pentru a selecta valoarea prag sunt metode bazate pe histograma, metode bazate grupare, metode bazate pe atribute și metode bazate segmentare locale de adaptare.

Avantajele algoritmilor threshold based:

Computațional ieftin

Rapid și simplu de implementat

Pot lucra în aplicații în timp real

Dezavantaje:

Neglijeaza informația spațială a imaginii

Foarte sensibil zgomot

Selectarea valorii de prag este esențială și de multe ori conduce la o segmentare mult prea mare sau mica.

Poate duce la pseudo-margini sau margini lipsă.

METODE BAZATE PE DISCONTINUITATE

Aceste metode se bazează pe principiul de variație de intensitate între pixeli. Dacă imaginea este format din două sau mai multe obiecte există limite și prin urmare, pot fi aplicate segmentarii imaginii. Limitele obiectelor duc la formarea marginilor. Cele mai semnificative schimbări bruște în nivelurile de intensitate între pixelii învecinati în anumite direcții sunt denumite muchii și rezultata în discontinuitatile dintre pixeli. Detectia marginilor implică în principiu, următorii pași: netezirea imaginii, detectia marginilor și localizarea acestora.

Pe imaginea de test este aplicat un filtru de netezire adecvat in vederea eliminarii zgomotului din imagine pentru a o pregati de segmentare. Apoi, "posibilele" margini sunt grupate împreună pentru a verifica apartenenta și în cele din urmă sunt găsite marginile "adevărate" localizând marginile "candidați".

Marginile sunt de obicei găsite prin aplicarea măștilor deasupra imaginii. Gradientul sau tehnicile de trecere la zero sau sunt utilizate pentru a găsi marginile din imaginea dată. Operatia de convoluție între mască și imagine determină marginea setată pentru imagine.

Operatorii de detectie a marginilor pot fi clasificati pe larg în două categorii ca: operatori derivativi de ordin I și operatori derivativi de ordin II.

Operatori derivativi de ordin I:

Există două metode pentru detectia muchiilor cu operatori derivativi de ordin I:

Una din metode evalueaza gradientii generati pe două direcții ortogonale.

Cea de-a doua abordare utilizeaza un set de șabloane de margini discrete cu

orientări diferite.

Primul operator derivativ folosește metoda de gradient pentru a găsi marginile cu ajutorul valoarii maxime și minime a gradientului.

Robert’s operator- este cel mai simplu operator derivativ care poate fi folosit pentru a găsi marginile în imaginile date. Găsește marginile în rânduri și coloane separat și le pune împreună pentru a găsi marginea rezultantă.

Prewitt’s operator- acest operator utilizeaza o masca de 3×3 pentru a gasi marginile.

Sobel’s Operator- este utilizat pe scară largă pentru a găsi marginile și este modificarea operatorului Prewitt prin modificarea coeficientului central cu „2”.

The Frei-Chen mask- este un alt operator pentru gasirea marginilor.

Operatori derivativi de ordin II:

Acești operatori funcționează prin detectarea trecerii prin zero al celui de-al doilea derivat al gradientului. Acesta detectează local maxime în valori de gradient și le tratează ca margini. Operatorul Laplacian este utilizat cu operatorul derivativ de ordin II.

Laplacianul operatorului Gaussian – Laplacianul unei imagini evidențiază regiunile cu o schimbare de intensitate rapida. Operatorul ia în mod normal, un singur nivel de gri din imagine ca intrare și produce o imagine cu un alt nivel de gri ca ieșire.

Operatorul e margine Canny – Operatorul de margine Canny este considerat ca detector al marginii superioare pe baza rezultatelor experimentale, deoarece determină marginile puternice și slabe din imagine.

Avantaje:

Operatorii de ordinul doi dau rezultate fiabile.

Utili în calcularea numărului de obiecte diferite prezente în imaginea dată.

Dezavantaje:

Niciun operator nu se poate potrivi pentru orice varietate de imagini și complexitatea computațională crește odată cu mărimea operatorului.

De multe ori marginile obținute nu sunt continue.

SEGMENTAREA BAZATA PE REGIUNI

Region growing methods:

Seeded Region Growing method

Unseeded Region Growing method

Region Split and Merge method

Seeded Region Growing method

Unseeded Region Growing method

METODELE BAZATE PE CLUSTERING

Agglomerative clustering

Partitional clustering

K-means algorithm

Fuzzy C-Means [FCM] Algorithm

METODELE HIBRIDE

Metodele hibride combina una sau mai multe dintre metodele de segmentare de bază. Acești algoritmi moștenesc calitatea bună a mai multor abordări și oferă o performanță mai bună în comparație cu abordarea sa mamă. Combinatiile dintre metoda bazata pe prag si a celei de clustering sunt folosite in segmentarile imaginilor medicale impreuna cu abordarile de delimitare a regiunilor, modelele regiunilor deformabile, si delimitarea regiunilor cu watershed morfologice. Metodele hibride se bazează pe operații morfologice efectuate pe imagini. Tehnicile cele mai utilizate pe scară largă sunt de segmentare watershed, de suprafață variabilă, pentru metodele de contur de montare și activă.

O regiune watershed este definita ca regiunea de la care toate punctele curg "în jos" pana la un punct comun.

Algoritmul watershed folosește concepte de detectare a marginilor și morfologie matematică pentru partiționarea imaginilor în regiuni omogene și se aplică magnitudinii gradientului imaginii. Imaginea gradientului poate fi considerata ca topografie cu limite între regiuni ca varfuri. Această metodă produce limite închise atunci când tranziția între regiuni este de rezistență sau claritate variabilă.

Dezavantaje:

Metoda are de suferit din cauza supra-segmentarii, adică imaginea este segmentată într-un număr inutil de mare de regiuni.

Asadar, algoritmii watershed este urmat, de obicei, de o etapă de post-procesare pentru a fuziona regiuni separate care aparțin aceleași zone.

Algoritmul watershed oferă o componentă de margine conectată la costul timpului de calcul.

Algoritmul watershed întâmpină dificultăți la imagini în care regiunile sunt atât de zgomotoase, cat au și limitele estompate sau neclare.

Metoda de ordonare de suprafață variabilă începe cu o segmentare grosieră a imaginii în mai multe primitive, care sunt rafinate printr-o procedură iterativa de creștere a regiunii. Modelele active de contur se bazează pe informații de gradient de-a lungul limitei dintre regiuni, dar ele sunt utile doar atunci când este facuta o estimare inițială bună.

METODELE BAZATE PE GRAFURI

METODA BAZATA PE PIXONI

Conceptul de Pixon a fost introdusă de Pina și Puetter în 1993. Pixonii pe care i-au introdus au fost un set de regiuni disjuncte cu forme constante și dimensiuni variabile. Schema lor de definiție a pixonilor a fost o convoluție local, între o funcție de nucleu și o pseudo- imagine.

Dezavantajul acestui sistem a fost că, după selectarea funcției nucleului, forma

pixonilor nu a putut varia. Yang și Jiang au prezentat o nouă schemă de definiție a pixonilor, a căror forma și mărime pot varia în mod simultan. Ei au folosit, de asemenea, ecuația de difuzie anizotropa pentru a forma pixonii și în cele din urmă au combinat conceptul pixon și MRF (Markov Random Fields) pentru segmentarea imaginilor. Recent, a fost propusa o altă reprezentare a unei imagini, bazata pe pixoni. În schema lor, pixonii sunt combinati cu atributele și adiacentele lor construiesc un grafic, care reprezintă imaginea observata. Ei au folosit algoritmul FQTC (Fast QuadTree Combination) pentru a extrage reprezentarea buna a pixonilor. Aceste tehnici sunt integrate în modelul MRF. Principalul dezavantaj al metodelor bazate pe MRF este că în acesti algoritmi minimizarea problemei functiei obiective consuma foarte mult timp. Cea mai nouă metodă care utilizează conceptul de pixon pentru segmentarea de imagini este introdus de Hassanpour et al. În această metodă, prima etapă de pre-procesare este realizat prin aplicarea tehnicii de binarizare wavelet. Acest pas este potrivit pentru uniformizarea imaginii datorită proprietății de reducere a zgomotului a binarizarii wavelet. Pentru a evita problema supra-netezirii, valoarea pragului de binarizare trebuie să fie

atribuite în mod corespunzător. Apoi, algoritmul bazat pe pixoni este folosit pentru a forma și a extrage pixonii. În cele din urmă, este aplicat algoritmul Fuzzy C-means (FCM) pentru segmentarea imaginii. Avantajul utilizării pixonilor este că, după formarea pixonilor nivelul de decizie se schimbă de la pixeli la pixoni si aceasta scade timpul de calcul, datorita numărului mai mic de pixoni comparativ cu numărul pixelilor. Acesta este aspectul cheie al algoritmilor bazati pe pixoni în segmentarea imaginilor.

Segmentarea imaginilor este un proces de divizare unei imagini în regiunile sale constitutive omogene pentru a extrage date din atributele imaginii. Drept urmare, o bună segmentare ar trebui să rezulte în regiunile în care elementele de imagine ar trebui sa aiba proprietăți uniforme în ceea ce privește luminozitatea, culoarea sau textura etc. Deși imaginea trebuie să fie porționată în regiuni, schimbările considerabile în cadrul regiunilor ar trebui să poată fi observate vizual. Măsurarea calității segmentarii este faptul că elementele aceleași regiuni ar trebui să fie similare și ar trebui să aibă o diferență clară între elementele altor regiuni.

Procesul de segmentare poate fi împărțit în diverse categorii pe baza parametrului selectat pentru segmentare cum ar fi intensitatea pixelilor, omogenitate, discontinuitate, date de dispersie, topologie etc. Fiecare abordare are propriile sale avantaje și dezavantaje. Rezultatul obținut folosind o anumita abordare poate să nu fie la fel în comparație cu alte abordări. Metode care sunt specifice anumitor aplicatii pot de multe ori obține o performanță mai bună și această selecție a unei abordari adecvate in cazul unei probleme de segmentare poate fi o dilemă dificilă.

În principiu, segmentarea poate fi semi-interactive sau complet automata. Algoritmii dezvoltati pentru segmentare se incadreaza în oricare din această categorie. Cu dificultatea majoră a naturii iillposed de segmentare este greu să se obțină un singur răspuns pentru segmentarea imaginii date pentru ca interpretarea variază la abordări individuale. În unele cazuri, interacțiunea manuala pentru segmentarea imaginii poate fi predispus la erori (de exemplu, în cazul selectării semințelor), în timp ce abordarea complet automatizata poate da eroare la ieșire (de exemplu, în cazul segmentarii watershed) și în unele cazuri, metodele interactive pot fi laborioase și consumatoare de timp. Deci, o singura abordare de segmentare a tuturor varietatilor de imagini poate fi practic nerealizabila. Cunoașterea anterioară privind imaginea poate da rezultate mai bune și oferă utilizatorului posibilitatea de a decide care este metoda optima de segmentare a imaginii.

CAPITOLUL 5

FUZZY C- MEANS

1. Introducere. Un algoritm de grupare ce organizează itemi în grupuri pe baza unor criterii de similitudine. Algoritmul Fuzzy C-Means este un algoritm de grupare în care fiecare element poate face parte din mai mult de un grup (de aici și cuvântul „fuzzy” (neclar)), unde gradul de apartenență pentru fiecare element este dat de o distribuție de probabilitate asupra clusterelor.

2. Algoritmul Fuzzy C-Means. Algoritmul Fuzzy C- Means (FCM) este un algoritm de grupare dezvoltat de Dunn, iar ulterior îmbunătățit de Bezdek. Este util atunci când numărul necesar de clustere este predeterminat; astfel, algoritmul încearcă să pună fiecare dintre punctele de date la unul dintre clustere. Ceea ce face FCM diferit este faptul că nu decide apartenența absolută a unui punct de date într-un anumit grup dat; în schimb, calculează probabilitatea (gradul de apartenență) ca un punct de date să facă parte din acel grup. Prin urmare, în funcție de precizia grupării care este necesară în practică, pot fi puse în aplicare măsuri de toleranță corespunzătoare. Din moment ce apartenența absolută nu este calculată, FCM poate fi extrem de rapid deoarece numărul de iterații necesare pentru realizarea unui exercițiu de grupare specifică corespunde preciziei cerute.

3. Iterații. La fiecare iterație a algoritmului FCM, următoarea funcția obiectivă J este minimizată:

(1)

Aici, N este numărul de puncte de date; C este numărul de clustere necesar; cj este vectorul central pentru clusterul j și 𝛿ij este gradul de apartenență pentru al-i-lea punct de date xi în clusterul j. Norma, ||xi – cj|| măsoară similitudinile (sau gradul de apropiere) a punctului de date xi la vectorul central cj al clusterului j. Rețineți că, la fiecare iterație, algoritmul menține un vector central pentru fiecare dintre clustere. Aceste puncte de date sunt calculate ca medie ponderată a punctelor de date, unde ponderile sunt date de gradele de apartenență.

4. Gradul de apartenență. Pentru un anumit punct de date xi, gradul de apartenență la clusterul j este calculat după cum urmează:

𝛿ij= (2)

unde, m este coeficientul fuzzy și vectorul central cj este calculat după cum urmeaza:

(3)

În ecuația (3) de mai sus, 𝛿j este valoarea gradului de apartenență calculată în iterația anterioară.

Rețineți că, la începutul algoritmului, gradul de apartenență la punctul de date i a clusterului j este inițializată cu o valoare aleatoare Ɵij, 0 Ɵij 1, astfel încât = 1.

Coeficientul fuzzy. În ecuațiile (2) și (3), coeficientul fuzzy m, unde 1 < m < ∞, măsoară toleranța grupării necesare. Această valoare determină cât de mult clusterele se pot suprapune unul peste altul. Cu cât valoarea lui m este mai mare, cu atât mai mare va fi si suprapunerea clusterelor. Cu alte cuvinte, daca algoritmul utilizează un coeficient fuzzy crescut, un număr mai mare de puncte de date vor cădea în interiorul unei benzi „fuzzy” unde gradul de apartenență nu este nici 0, nici 1, ci undeva între.

5.2 REZILIEREA CONDIȚIEI FCM

Starea de încetare. Precizia necesară gradului de apartenență determină numărul de iterații realizate de algoritmul FCM. Această măsură de precizie este calculată folosind gradul de apartenență de la o iterație la alta, luând cea mai mare dintre aceste valori în toate punctele de date, considerând toate clusterele. Dacă reprezentăm măsura de precizie între iterațiile k și k+1 cu ϵ , vom calcula valoarea după cum urmează:

ϵ= | – | (4)

unde 𝛿kij și 𝛿ijk+1 sunt respectiv, gradul de apartenență la iterațiile k și k +1, și operatorul Δ- atunci când este furnizat un vector de valori, returnează cea mai mare valoare din acel vector.

5.3 PROGRAM

Programul FCM. Programul fcm asteaptă un fișier de intrare, care conține parametrii pentru rularea algoritmului FCM. Aceast fișier de intrare poate fi generat cu ușurință prin intermediul programulului aferent gen.

Variabile globale și constante. Programul fcm, la executare, utilizează mai multe variabile globale. Aceste variabile sunt parametrii ceruți de algoritm și în mod normal sunt inițializate cu valori de la datele de intrare le generate de programul gen.

Variabila num_data_points este inițializată cu numărul de puncte de date care urmează să fie grupate; întrucât, variabila num_clusters este inițializată cu numărul de clustere necesar. Algoritmul FCM descoperă clustere în conformitate cu un număr prestabilit de clustere, în contrast cu descoperirea unui număr arbitrar de clustere.

*declar variabilele globale

Variabila num_dimensions este inițializată la numărul de dimensiuni pe care fiecare punct de date îl are. De exemplu, dacă grupăm puncte carteziene în planul euclidian bidimensional, vom avea num_dimensions ≡ 2.

*declar variabilele globale

Pentru fiecare punct de date, valoarea pe care o poate lua o dimensiune este mărginită. Noi folosim o matrice bidimensională, low_high, pentru a stoca valorile mici și mari pentru fiecare dimensiune. Fiecare punct de date trebuie să se încadreze în acest interval de valori.

*declar variabile globale

O matrice bidimensională, degree_of_ memb, stochează gradul de apartenență pentru fiecare dintre punctele de date ale fiecărui cluster in parte. Astfel, de exemplu, degree_of_memb[i][j] dă o măsură a probabilității ca punctul de date i să aparțină clusterului j. Această matrice este actualizată în mod dinamic în timpul iterațiilor.

*declar variabile globale

5.4 VARIABILE SI CONSTANTE GLOBALE

Algoritmul de grupare foloseste o masură de precizie, epsilon, pentru a stabili dacă un exercițiu de grupare poate fi considerat satisfăcător. Acest lucru determină în cele din urmă numărul de iterații care trebuie să fie efectuat înainte ca algoritmul să se termine.

Gradul de fuzzy, fuzzyness, dă o măsură de toleranță în timpul desfășurării exercițiului de grupare și, prin urmare, afectează ​​calculul gradului de apartenență.

*declar variabile globale

Fiecare punct de date are coordonate (x1, x2,…, xd) dat de un set ordonat de valori corespunzătoare fiecarei dintre dimensiuni (unde d dă cea mai mare dimensiune pentru un punct de date). Aceste coordonate depind de numărul de dimensiuni pe care fiecare punct de date trebuie să-l aibă. De exemplu, pentru punctele de pe o linie, numărul de dimensiuni este 1. Pentru puncte de pe un plan, numărul de dimensiuni este 2, unde fiecare punct de date este reprezentat de coordonatele sale 2D, de exemplu (x, y). Pentru punctele din interiorul unui volum, numărul de dimensiuni este 3, unde fiecare punct de date este reprezentat de coordonatele sale 3D, de exemplu (x, y, z). Punerea în aplicare a acestui algoritm FCM funcționează cu orice număr de dimensiuni mai mici decât MAX_DATA_DIMENSION.

Pentru fiecare dintre clustere, un punct central temporar este menținut în timpul fiecărei iterații. Punctele centrale pentru toate clusterele sunt menținute ca o matrice (fiecare rând reprezentând un vector în același sistem de coordonate ca și punctele de date). Valorile stocate în această matrice sunt actualizate în cursul fiecarei iteratii în funcție de gradul de apartenență al punctelor de date pentru fiecare dintre clustere.

Initializare. Funcția init inițializează parametrii de execuție prin analizarii datelor de intrare. Este nevoie ca argument de intrare de numele datelor de intrare, fname, și returnează 0 dacă inițializarea a fost realizata cu succes. În caz contrar, este returnat -1.

5.5 RANDOMIZAREA MATRICII GRADELOR DE APARTENENTA

Randomizarea matricii gradelor de apartenenta. Noi folosim un generator de numere aleatorii pentru a inițializa gradul de apartenenta înainte de aplicarea algoritmului FCM. Pentru a face acest lucru, folosim functia rand() din biblioteca standard math.

Pentru fiecare punct de date, în raport cu unul dintre clustere, vom atribui o probabilitate aleatoare că punctul va aparține acelui grup. Valoarea este un număr real între 0 și 1 inclusiv. Având în vedere că suma probabilităților tuturor clusterelor pentru un punct de date dat ar trebui să fie 1, vom ajusta probabilitatea primului cluster după ce am atribuit probabilități pentru toate clusterele rămase.

5.6 CALCULUL VECTORILOR CENTRALI

Calculul vectorilor centrali. Funcția calculate_centre_vectors actualizează vectorii centrali pentru fiecare cluster. Scopul algoritmului este de a continua actualizarea acestui centru de vectori până când este aproape de valoarea reală/ actuala. Apropierea de valoarea actuala este determinată de criteriul de terminare (epsilon).

Precompute puterile gradelor de apartenență. Valorile calculate aici sunt utilizate în două părți ale următorului calcul al centrului de vectori. Ne-am mutat calculul puterilor aici pentru refolosirea valorilor, astfel încât să nu trebuiasca să calculam din nou puterile. Calculul puterilor este scump.

Calculul normei. Funcția get_norm este una dintre cele mai importante calcule ale algoritmului FCM. Aceasta determină apropierea unui punct de date de centrul de vectori pentru un anumit cluster dat. Calculul normei depinde de numărul de dimensiuni pe care punctele de date il au.

5.7 ACTUALIZAREA GRADELOR DE APARTENENTA

Actualizarea gradului de apartenenta. Funcția get_new_value calculează noul grad de apartenență pentru punctul de date i din clusterul j.

Funcția update_degree_of_membership actualizeaza valorile gradelor de apartenență pentru toate punctele de datele. Din moment ce ne dorim să oprim iteratiile când toate punctele sunt destul de aproape de unul dintre vectorii centrali, această funcție returnează diferenta maxima dintre valoarea veche și noua valoare, astfel încât acesta poate fi verificata antagonic condiției de terminare.

Algoritmul FCM. Funcția fcm încapsulează principalele faze ale algoritmului FCM. Contine scheletul algoritmului, care corespunde descrierii matematice din introducere.

5.8 INTRARE

Intrare. Această secțiune listează funcțiile de intrare și segmentele de cod care sunt folosite pentru citirea valorilor initializate, ale parametrilor din datele de intrare.

5.9 IESIRE

Ieșire. Această secțiune listează funcțiile de ieșire și segmentele de cod care sunt utilizate atunci când afisam ieșirea, mesaje de eroare etc., fie la fluxul de ieșire standard al unui fisier de ieșire.

Această funcție emite matricea de apartenenta actuala, astfel încât să poată fi reprezentate folosind gnuplot.

NOTA: Acest lucru va funcționa numai în cazul în care numărul de dimensiuni este de 2.

Aceastea sunt punctele dintr-un plan. Acest lucru poate fi extins pentru dimensiuni mai mari.

*verificarea daca numarul de dimensiuni este 2

*am creat un fisier separat pentru fiecare cluster. Fiecare fisier conține punctele de date care au cel mai mare grad de apartenență.

*curatarea fisierelor de date ale clusterelor

*trimiterea punctelor de date la un anumit cluster

*inchiderea clusterului

*scrierea sciptului gnuplot

Am inclus biblioteci de sistem care definesc constante și prototipuri funcționale.

CAPITOLUL 6

CONCLUZII

Avantaje:

Oferă cele mai bune rezultate pentru setul de date suprapuse și este comparativ mai bună decât algoritmul k-means.

Spre deosebire de k-means unde punctele de date trebuie să aparțină în mod exclusiv centrului unui cluster, aici punctului de date ii este atribuita calitatea de membru fiecărui centru de cluster ca rezultat al punctului de date care poate aparține mai multor centre de cluster.

Dezavantaje:

Specificația apriori a numărului de clustere.

Cu o valoare mai mică de β obținem rezultate mai bune, dar în detrimentul mai multor iterații.

Măsurile distanțelor euclidiene pot ingreuna inegal factori care stau la baza.

Imagine inițială

Imagine segmentată cu Fuzzy C-Means

aplici functia fcm care are o imagine ca input si imaginea segmentata ca output (partea de hemangiom este o culoare si restul imaginii alta culoare)

Aplici fcm pe mai multe imagini input: imaginea de hemangion in spatiul RGB

apoi in spatiul LAB

-doar pe planul A din LAB

-doar pe planul L din LAB

-pe planul cu imaginile L si A din spatiul LAB

-faci comparatii intre aceste imagini si vezi ce obtii 

-faci si segmentarea manuala a imaginilor si compari cu ce se obtine in urma fcm