Segmentare split & merge

1. Tema proiectului

Prezenta lucrare îşi propune sa prezinte diferite prelucrari split and merge. In prima parte a proiectului se va realiza un studiu bibliografic, care va consta in prezentarea generala a tehnicilor de segmentare si a relatiilor matematice de baza. In mod uzual algoritmii de segmentare care implementeaza operatiile de tip “split and merge” sunt obligati sa aiba doua etape: o prima etapa de “divizare” (split stage), urmata de o etapa de “unire” (merge stage). In cele ce urmeaza va fi prezentat un algortim ce se bazeaza pe o structura de date numita discrete map (harta discreta). Aceastra structura furnizeaza un cadru eficient de implementare a algoritmului split and merge. In continuare fi realizat si testat un cod in Matlab.

2. Studiu bibliografic

2.1. Prezentare generala. Segmentare. Tehnici de segmentare.

Segmentarea imaginilor se refera la descompunerea unei scene (imagini) în componentele sale. În urma procesului de segmentare vor fi extrase din imagine obiecte distincte, regiuni ce satisfac anumite criterii de uniformitate, sau alte elemente.

Scopul este acela de a împărţi imaginea în regiuni ce au o corelaţie puternică cu obiectele sau suprafeţele din imagine. Există două tipuri de segmentare [1]: completă şi parţială. Segmetarea completă generează un set de regiuni disjuncte ce corespund în mod unic cu obiectele din imagine. Pentru realizarea unei segmentări complete , este necesară cooperarea cu nivelele superioare de procesare , care utilizează cunoştinţe specifice din domeniu. În cazul segmentării parţiale, imaginea este împărţită în regiuni disjuncte care sunt omogene relative la o anumită proprietate cum ar fi luminozitatea, culoarea, contextul reflectivitatea, etc.

Ambiguitatea prezentă în imagini este principala problemă a segmentării şi ea este deseori însoţită de zgomot. Tehnicile de segmentare pot fi clasificate în patru categorii:

• filtrare locală şi fixare de praguri (threshold);

• metode bazate pe snake şi de tip balon, algoritmul watershed;

• tehnici de region growing şi split and merge;

• metode de optimizare globală bazate pe funcţii de energie, funcţii bayesiene sau pe criteriul MDL (Minimum Description Length).

Metoda filtrării foloseşte informaţia locală şi nu poate garanta contururi continue. Metodele de tip balon sau cele bazate pe snake folosesc doar informaţia existentă de-a lungul conturului şi necesită o bună estimare a poziţiei de iniţializare pentru obţinerea unei convergenţe corecte. Avantajul metodelor de region growing este acela că se bazează pe statistici realizate în interiorul fiecărei regiuni. Cele trei tehnici nu folosesc informaţia existentă la nivelul întregii imagini. Spre deosebire de acestea, metodele bazate pe energie, bayes sau MDL, utilizează criterii globale, dar fiind bazate pe o minimizare, miinimul este de multe ori greu de atins.

Tehnica region growing detectează o regiune identificând acei pixeli conectaţi la punctul de pornire care au intensitatăţi “similare”. Algoritmul recursiv asigură extinderea regiunii în patru direcţii (spre cei patru pixeli vecini), dacă intensităţile acestora se încadrează în intervalul [m-t, m+t], unde m este intensitatea medie a regiunii, iar t este o valoare prag introdusă de utilizator (parametru). Un alt parametru care trebuie introdus de utilizator este punctul de pornire care poate fi introdus printr-un click al mouse-ului pe imagine sau prin precizarea directă a coordonatelor acestuia. Ieşirea programului constă într-o copie binară a imaginii procesate, în care, un 1 reprezintă un pixel al obiectului detectat, iar un 0 indică un pixel care aparţine fundalului.