Detectie de contururi folosind algoritmi euristici

1.Descrierea aplicatiei

Aplicatia are ca scop gasirea contururilor intr-o imagine color, format *.gif, *.jpg, *.jpeg. La selectarea unei poze din lista din dreapta se incarca in fereastra appletului imaginea respectiva si se deseneaza cu rosu contururile gasite.

2.Descrierea algoritmului folosit

Se asociaza fiecarui pixel din imagine un numar natural intre 0 si 255 reprezentand nivelul sau de gri, si se creeaza o matrice din aceste numere.

Se considera ca intre fiecare 2 pixeli exista o frontiera. Pentru a o reprezenta am folosit clasa FElement, care contine:

1. membri:

- coordonatele pixelilor vecini ce determina acest element de frontiera;

-cost (diferenta intre nivelurile de gri asociate celor 2 pixeli vecini). Observatii:

a) Frontiera este orientata, adica perechea de pixeli vecini este ordonata;

b) Costul poate fi si negativ si se poate calcula in doua moduri; (folosind notatiile din figura) cost=Cp1-Cp2, caz in care executarea algoritmului duce la gasirea de contururi ce ocolesc eventualele forme lasandu-le in partea stanga si respectiv cost= Cp2-Cp1 pentru ocolire invers;

- adancime (numarul de elemente de frontiera parcurse pana la descoperirea elementului respectiv);

- parinte (pointer catre elementul de frontiera dinainte);

-destinatie (pointer catre un element de frontiera ce reprezinta coltul dreapta jos al imaginii);

- f (costul real al drumului parcurs pana la acest element);

- g (costul estimat al drumului de la acest element pana la destinatie);

- h (suma ultimelor doua);

2. metode:

- getVeciniS (construieste o lista de vecini folosind a doua formula de cost);

- getVeciniD (construieste o lista de vecini folosind prima formula de cost);

- equals (pentru a putea determina situatia in care drumul curent formeaza un ciclu);

- getCostTotal (costul drumului gasit pana la acest element);

- getCostMediu (costul de mai sus impartit la adancime);

Observatie: Nu am luat in considerare decat contururile cu costul mediu mai mare decat 100 (contraste mai puternice).

- draw (deseneaza drumul gasit pana aici).

Algoritmul propriu-zis de detectie a contururilor este implementat in functia drumMinim( ). El se bazeaza pe gasirea unui drum de cost minim intre doua puncte ale imaginii. Algoritmul este executat de mai multe ori, de fiecare data punctul de start este un varf al unei retele laticeale care acopera imaginea. Latura retelei este determinata experimental. Punctul „destinatie” este coltul dreapta jos al imginii. Descriem in continuare algoritmul folosit. Acesta este in esenta un A* „omorat”, in sensul ca dupa parcurgerea unui anumit numar de pasi (deteminat prin incercari astfel incat sa optimizeze raportul performanta/timp de executie) se pastreaza drumul cel mai bun gasit pana in prezent, si nu se mai revine niciodata asupra lui.

Folosim trei liste OPEN ,CLOSED si FINAL, prima dintre ele continand elementele de frontiera descoperite dar neprelucrate, a doua elemente descoperite si prelucrate, iar ultima elementele care fac parte din conturul final. Initial, OPEN are un singur element (sursa) si CLOSED este vida. Cat timp OPEN nu este vida se executa urmatotul ciclu:

- Se alege din OPEN cel mai „bun” element, dupa un criteriu specificat de functia best descrisa mai jos.

- Se prelucreaza elementul extras, in sensul ca se sterge din OPEN si se adauga in CLOSED, iar vecinii lui sunt adaugati in OPEN.

- Se actualizeaza variabila adancimeBest cu adancimea elementului extras.

- Daca adancimeBest atinge o anumita valoare, fixata la inceput, listele OPEN si elementele din CLOSED se transfera in FINAL. In OPEN se pune ultimul element de frontiera explorat. Aceasta are ca scop limitarea complexitatii si deci a timpului de executie si nu afecteaza sensibil calitatea conturului descoperit.