LUCRAREA NR

Sisteme de vedere artificial Lucrarea de laborator nr. 4

LUCRAREA NR. 41. Scopul lucrrii

Cea de-a patra lucrare de laborator trateaz problema detectrii colturilor obiectelor dintr-o imagine.2. Breviar teoreticDetectarea traiectoriei de micare a unui obiect n timp se poate realiza identificnd anumite trsturi ale obiectului ce corespund n dou imagini achiziionate la timpii t1 si t1 + . Aceste trsturi trebuiesc determinate astfel nct ele s poate fi urmrite i detectate n ambele imagini.

Din multitudinea de algoritmi dedicati detectiei trasaturilor tip punct doar trei algoritmi au fost propui pentru a fi analizai i implementai: Interest Point Operator, operatorul Smith i operatorul Harris. Alegerea celor trei operatori a fost facute deoarece, Interest Point Operator folosete n cadrul procesului de cutare al colurilor variaia intensitii pixelilor de-a lungul a patru axe (orizontal, vertical i cele dou diagonale), Operatorul Smith folosete un criteriu geometric pentru detecia punctelor de interes, iar Operatorul Harris se bazeaz pe calculul cu prima derivat si folosirea funciei de auto-corelaie; astfel se va face analiza a trei operatori ce au la baz principii de funcionare total diferite.

2.1. Interest Point Operator

Operatorul calculeaz variaia de intensitate a imaginii, vi, de-a lungul a patru direcii: vertical, orizontal i cele dou diagonale pe o masc centrat in pixelul P(i,j).Fig. 2. Masca 3x3 centrat n P(x,y). f-valoarea intensitii n pixelul respectiv.Variaiile vi , i = 1,4 , sunt determinate cu ajutorul formulelor:

(1)

Avnd cele patru variaii, se determin minimul dintre acestea. Dac valoarea gasit depaete un anumit prag:

(2)

atunci punctul P este considerat punct de interes (col), unde este un prag stabilit in funcie de zgomotul prezent in imagine.

Acest operator garanteaz gsirea unor pixeli care au o variaie important pe toate direciile din V8. Este util deoarece pixelii care au variaii pe toate direciile aparin colurilor obiectului, punnd astfel n eviden forma obiectului.

Operatorul poate fi extins pentru vecinti mai mari asigurnd n aceste fel o mai bun precizie pentru imaginile afectate de zgomot, dar crete considerabil efortul computaional ct i numrul de puncte determinate; acest lucru nu este de dorit n multe cazuri deoarece creterea efortului computaional afecteaz cerinele de lucru n timp real.

2.2. Detectorul Smith

Pentru detectarea punctelor de interes (colurilor), operatorul Smith folosete o masca circular pe care o suprapune pe imagine precum n figura 3.

Fig. 3. Patru mti circulare plasate n diferite poziii in imagine.

Centrul matii (numit nucleu) reprezint pixelul ce se va testa pentru a observa dac este col. Dac mai muli pixeli din cadrul mtii au intensitatea comparativ egal cu intensitatea nucleului atunci se poate considera c ei aparin unei anumite regiuni (obiect) din poz. n figura 3, mtile au zona ce conine pixeli cu valoarea intensitii apropiat de cea a nucleului, colorat cu negru, iar zona ce conine pixelii cu valoarea intensitii diferit de cea a nucleului, cu alb. Aceast zon poart numele de USAN (abreviere de la Univalue Segment Assimilating Nucleus ). Zona USAN ofer informaii importante privind structura imaginii din jurul oricrui punct testat. Din figura II.2 reiese faptul c suprafa USAN atinge valoarea maxim atunci cand masca este suprapus pe o zon din imagine ce nu prezint variaii importante ale intensitaii pixelilor, scade la jumtate atunci cand masca nucleul mtii se apropie de o margine i scade i mai mult n cazul n care nucleul se apropie de un col. Aceasta este proprietatea principal a zonei USAN utilizat pentru a detecta prezena colurilor.

Un nucleu corespunde unui col (cazul d din figura 3) dac suprafaa USAN este mai mic dect jumtate din suprafaa total a mtii.

n practic, masca circular este aproximat folosind masca din figura 3, avnd o suprafa de 5x5 pixeli, cu 3 pixeli adugai n centrul fiecrei margini. Toi pixelii din cadrul mtii sunt comparai cu nucleul conform formulei:

(3)

Fig. 4. Masca de cutare a operatorului Smith

unde: r0 poziia nucleului; r poziia oricrui alt pixel din interiorul mtii, f valoarea intensitii, t diferena de intensitate setat, c valoarea comparaiei.

Suma acestor valori se calculeaz cu ajutorul formulei:

(4)

n urmtoarea etap, n este comparat cu o valoare calculat n funcie de suprafaa mtii de cutare, numit prag geometric g. Pentru ca un col sa fie prezent este necesar ca n sa fie mai mic decat jumtate din valoarea maxim posibil, nmax . Cu alte cuvinte, nucleul este un col dac USAN este mai mic dect jumtate din suprafaa mtii i este un minim local. Pragul geometric g afecteaz calitatea colurilor. Cu toate ca determin numrul de coluri gsite, mult mai important este faptul c influeneaz forma colurilor detectate. De exemplu, daca pragul g este redus atunci colurile gsite vor fi mai ascuite.

O alt valoare care influeneaz rezultatele returnate de operator, o constituie diferen de intensitate, t. Nu influeneaz calitatea precum g, dar influeneaz numrul de coluri gsite. Deoarece definete variaia maxim de intensitate permis ntre nucleu i ceilali pixeli ce aparin mtii, o mrire a valorii pragului t duce la creterea numrului de pixeli reportai ca puncte de interes (coluri). n consecin, acest prag poate fi folosit pentru a controla numrul de coluri returnat fr a afecta calitatea acestora. Acest lucru prezint dou aspecte: unul negativ i unul pozitiv. Pe de o parte nseamn ca pragul t trebuie s fie ales n funcie de contrastul i de nivelul zgomotului prezent n imagine, pe de alt parte, poate fi ales n funcie de numrul dorit de coluri gsite.

n unele cazuri, operatorul Smith poate conduce la detectarea de coluri false. Acest lucru se poate ntmpla n cazul imaginilor reale, cnd prezena diferitelor margini existente ntre regiunile din imagine provoac un efect de umbrire a zonelor vecine (fig.5). Etapa final n utilizarea operatorului Smith este de a elimina rspunsurile false. Acest lucru se realizeaz n dou etape:

- se determin valoarea de maxim local mai mare dect zero pe o suprafa de 5x5 (aria de cutare poate fi prestabilit de utilizator) cu ajutorul formulei:

(5)

Fig. 5. Exemplu de rspunsuri false returnate de operatorul Smith

- se localizeaz centrul de greutate al suprafeei USAN. Avnd localizat centrul de greutate, se determin distana dintre acesta si nucleul mtii (pixelul indicat ca fiind col). Se consider ca fiind colul real cel care este cel mai ndeprtat de centrul de greutate corespunztor (figura II.5).

a) b)

Fig. 6. Poziia nucleului fa de centrul de greutate al suprafeei USAN: a) n cazul unui col real; b) n cazul unui col fals.

O alt condiie care trebuie ndeplinit este ca suprafaa USAN sa prezinte o oarecare uniformitate n sensul c toi pixelii ce aparin mtii i care se afl pe direcia dintre nucleu si centrul de greutate trebuie s fac parte din USAN. Aceast criteriu de eliminare al raspunsurilor false este util n cazul imaginilor ce conin un nivel ridicat de zgomot.

n concluzie, n utilizarea operatorului Smith, se parcurg urmtoarele etape:

Suprapunerea unei mti circulare n jurul pixelului testat (nucleul);

Folosind ecuaia (4) se calculeaz numrul de pixeli din interiorul mtii ce au valoarea intensitii apropiat de cea a nucleului (aceti pixeli definesc suprafaa USAN);

Folosind ecuaia (5), se face diferena dintre pragul geometric g si valoarea USAN;

Se elimin rezultatele false determinnd centrul de greutate si omogenitatea USAN; Se determin valoarea de maxim local.

2.3. Operatorul Harris

Operatorul se bazeaz pe utilizarea funciei de autocorelaie. n implementarea sa, se disting dou etape: o prim etap n care sunt calculate valorile funciilor de autocorelaie pentru fiecare pixel din imagine; i o a doua etap n care se determin valoarea de maxim local a acestei funcii intr-o vecintate definit de utilizator. Pixelii care sunt asociai acestor valori de maxim local sunt considerai puncte de interes (coluri).

Considernd o masc de dimensiuni liber alese n cadrul imaginii, se pot determina variaiile de intensitate ale pixelilor ce survin n urma deplasrii pe o distan mic a mtii de-a lungul a diferite direcii. Se disting trei cazuri:

dac masca conine pixeli cu nivel apropiat al intensitii, atunci n urma deplasrilor pe orice direcie, va rezulta o variaie mic;

dac masca conine poriuni dintr-o margine, atunci o deplasare de-a lungul marginii va duce la variaii mici pe cnd o deplasare perpendicular pe margine va duce la obinerea unei variaii semnificative;

dac masca conine un col sau un punct izolat, atunci deplasarea pe orice direcie va duce la obinerea unei variaii semnificative. Astfel, un col poate fi determinat gsind valoarea minim a variaiei considernd acest caz.

Schimbarea local a intensitii imaginii este dat de relaia:

(6)

unde w este o masc circular de netezire, de exemplu masca gaussian:

(7)

Aproximnd primii gradieni cu:

(8)

pentru mici schimbri, E din relaia (6) poate fi scris [6]:

(9)

unde:

(10)

Astfel, modificarea valorii lui E pentru mici schimbri este strns legat de funcia de autocorelaie local. Un col este detectat daca matricea A este de rang 2 i are valori proprii semnificative. Considerm cele dou valori proprii ca fiind i . Acestea, mpreun, determin graficul funciei de autocorelaie local (figura 7). Se disting trei cazuri:

dac ambele valori proprii sunt mici, atunci nu este detectat prezena vreo unei margini sau vreo unui col;

dac una din valorile proprii este mare iar cealalt mica, atunci este detectat prezena unei margini;

dac ambele valori proprii sunt mari, atunci este indicat prezena unui col.

Fig. 7. Principiul funciei de auto-corelaie

Pentru fiecare pixel testat, este calculat valoarea lui c, numit cornerness value.

(11)

Un col bine determinat se caracterizeaz printr-o valoare mic a lui c , ndeplinind condiia:

(12)

unde reprezint valoarea maxim definit de utilizator pe care c o poate avea.

3. Exercitii

1. Analizati implementarea existenta a celor trei algoritmi si realizati imbunatatiri din punct de vedere a performantelor implementarilor (timp de lucru, bucle, etc.)

2. Realizati achizitii de imagini si detectati colturile obiectelor ce compun imagine analizand performantelor celor trei

i=4

i=1

i=2

i=3

y

x

f(x+1,y+1)

f(x,y+1)

f(x-1,y+1)

f(x+1,y)

f(x,y)

f(x-1,y)

f(x+1,y-1)

f(x,y-1)

f(x-1,y-1)

regiunea

marginilor

regiunea

marginilor

regiuneacolurilor

4

3

2

1

0

-1

-2

-3

regiune omogen

PAGE 6

_1208984249.unknown

_1208984316.unknown

_1210203822.unknown

_1210206220.unknown

_1210189867.unknown

_1208984287.unknown

_1208810995.unknown

_1208984225.unknown

_1208984240.unknown

_1208984126.unknown

_1208034802.unknown

_1208363987.unknown