Prelucrarea Imaginilor

download Prelucrarea Imaginilor

of 40

Transcript of Prelucrarea Imaginilor

P I

crarea relu nilor magi

Info IV2001

CuprinsPag. Prefa1.

.................................................................................... ..............................................

3 4

Reprezentarea imaginilor digitale1.1. 1.2.

Reprezentarea imaginilor prin funcii picturale i cuvinte picturale... 4 Reprezentarea imaginilor prin arbori (quad i binari) .................... 15

2.

mbuntirea imaginilor2.1. 2.2. Operaiuni punctuale Operaiuni spaiale

............................................................................................................................... .....................................................................

1818 23

3.

Transformri ale imaginilor3.1. 3.2. 3.3. 3.4.

........................................................

2929 31 32 33

Determinarea conturului .............................................................. Scheletizare ................................................................................ Subiere ..................................................................................... Transformri morfologice .......................................................

Lucrri de laborator ............................................................................ Bibliografie .........................................................................................

39 40

2

PrefaGrafica pe calculator este un domeniu modern cu multiple aplicaii practice n diverse domenii de activitate (medicin, art, etc.), care pot fi realizate datorit dezvoltrii disciplinelor matematice specializate n aceast direcie. n acest material sunt abordate aspecte doar dintr-o singur ramur ale graficii pe calculator, definite de Pavlidis n [3] (vezi schemele de mai jos) i anume Prelucrarea imaginilor (transformarea imiginilor).a) Grafic propriu-zis Descriere de imagine Imagine b) Prelucrarea imaginilor

c) Recunoaterea formelor

n cele ce urmemz sunt prezentate diverse metode, tehnici i algoritmi utilizai n reprezentarea i prelucrarea digital a imaginilor, att n vederea creterii calitii imaginii destinate ochiului uman (paragraful doi intitulat mbuntirea imaginilor, prin operaiuni punctuale i spaiale) ct i n scopul recunoaterii formelor (paragraful trei Transformri ale imaginilor cuprinznd algoritmi de determinare a conturului, scheletizare i subiere).Segmentare 1. Imagini Color Determinarea Conturului Determinarea Punctelor Critice

2. Imagini Alb-Negru

3. Linii i Curbe

4. Puncte Critice

Colorare

Umplere

Interpolare

Printre primele prelucrri de imagini amintim realizarea transmisiei peste Atlantic a imaginilor de ziar, n 1920, reducnd timpul de transmisie de la o sptmn la trei ore prin codificarea, transmisia prin cablu marin i decodificarea unor imagini avnd cinci nivele de strlucire. n continuare s-au mbuntit metodele de cretere a calitii imaginilor, iar ncepnd din 1964 (cnd au fost ptreluate imagini de la bordul staiei spaiale Ranger 7) s-au utilizat diverse tehnici de restaurare i mbuntire a imaginilor preluate din spaiul cosmic (misiunile Surveyor, Mariner i Apollo). Prelucrarea imaginilor i propune:

mbuntirea informa iei vizuale n vederea optimizrii analizei i interpretrii de ctre om, cu aplicaii n diverse domenii cum ar fi medicin (trecerea de la imagini alb/negru la imagini color, prelucrarea imaginilor biomedicale), ecologie (studiul polurii utiliznd imagini aeriene), criminalistic, aprare, industrie, etc. extragerea informa iilor ntr-o form intern pentru analiza cu ajutorul calculatorului a informaiilor video, n recunoatrea caracterelor (chinezeti, de exmplu), a formulelor chimice sau matematice, n verificarea calitii produselor, recunoatrea preurilor (coduri de bare), recunoaterea amprentelor i a feei, n sortarea corespondenei, n meteorologie, aprare, etc. [2].

3

1. Reprezentarea imaginilor digitale1.1. Reprezentarea imaginilor prin funcii picturale i cuvinte picturalen cele ce urmeaz, sunt abordate n special probleme referitoare la imaginile de tip 3 i 4 (definite n [3]) i anume cteva metode de reprezentare a imaginilor prin linii i curbe respectiv printr-o mulime de puncte critice, prin desene descrise de -cuvinte (iruri de comenzi de deplasare a cursorului pe cele patru direcii r, u, l i d). De asemenea este prezentat i o modalitate de conversie a unui desen dintr-o form n alta. Pentru interpolare sunt utilizate curbele Bezier, datorit faptului c acestea au anumite proprieti care se potrivesc cu desenele descrise prin cuvinte picturale ( -cuvinte). O imagine poate fi modelat printr-o funcie de dou variabile definit n planul ecranului (pe matricea de puncte din fereastra de lucru, ViewPort). Valoarea funciei ntr-un punct va reprezenta nuana (culoarea) acelui pixel de pe ecran. Aceasta nseamn c funcia ia valori din mulimea culorilor posibile ale punctelor ecranului, deci o astfel de funcie este nenegativ i mrginit. Dac fereastra ecran este [u1,u2] [v1,v2] (figura 1.1.1), punctele Pij din fereastr au coordonatele limitate astfel: v1 i v2 i u1 j u2.

Fie Sij ptratul definit astfel : j < x j i i < y i . 1 1 n ptratul Sij funcia va lua o valoare constant egal cu codul culorii punctului Pij . O astfel de i v2 funcie o vom numi funcie pictural. Un caz particular important l reprezint funciile cu doar dou valori 0 i 1 pentru imagini alb-negru. v1

x Sij

Pij

y

u1

j

u2

Figura 1.1.1

4

Funciile picturale sunt utilizate n numeroase probleme de prelucrare a imaginilor (codificare, aproximare, filtrare, restaurare, scalare, etc.) prin diverse operaii aplicate acestora . Lema 1.1.1. Descrierea unei imagini printr-o funcie pictural este echivalent cu descrierea acesteia prin cuvinte picturale. Demonstraia acestei afirmaii o vom efectua prin precizarea modului de descriere a unei imagini format din ptrate (Sij), utiliznd cuvinte de descriere prezentate n continuare. Pentru imagini alb-negru este suficient un limbaj asemntor cu cel de descriere a desenelor discontinue (*, unde ={r,u,l,d, }), doar c primitivele de desenare nu vor , mai fi segmente de lungime unitate ci ptrate de latur unitate. De exemplu, -cuvntul r5d4l4u4 r descrie imaginea din figura 1.1.3. dr Pentru o funcie pictural care ia valori din mulimea {alb,negru} exist i putem construi un -cuvnt care s descrie aceeai imagine. Desigur c exist mai multe posibiliti de definire a -cuvintelor echivalente cu o funcie pictural. Teoretic este suficient s punem n eviden un singur -cuvnt pentru o funcie pictural oarecare. Practic ns, ne intereseaz i complexitatea descrierii, adic o descriere minim a unei imagini. n cele ce urmeaz vom prezenta o prim metod de construcie a unui cuvnt pictural pornind de la o funcie pictural dat. -cuvntul echivalent este w=wv1wv1...wi...wv2-1wv2, unde prin wi nelegem subcuvntul de descriere al liniei i, iar funcia Redu este definit astfel: * Redu( )= ; , . -cuvntul wi de descriere a liniei i (v1 i v2) este definit astfel :

wi =

i,u1i,u1+1...i,j...i,u2-1i,u2 i,u2i,u2-1... i,j...i,u1+1i+1,u1

pentru i impar, pentru i par.

Subcuvintele de colorare (ij, ij) a ptratelor Sij sunt definite dup cum urmeaz:

=

ij

r r d d

pentru pentru pentru pentru

j1 i ij d pentru j =1 i = d pentru j =1 i Se observ c -cuvntul de descriere, parcurge matricea de ptrate care reprezint

5

Figura 1.1.2

imaginea descris de funcia f i coloreaz acele ptrate pentru care valoarea funciei picturale este negru. Ordinea de parcurgere este cea din figura 1.1.2. Invers, valoarea funciei picturale corespunztoare ptratului Sij este dat de poziia creionului ( sau ) nainte de colorarea ptratului Sij . Pentru descrierea unei imagini color putem utiliza comenzi din mulimea C. Pentru a descrie o imagine format din ptrate Sij de tipul celor de mai sus (vezi figura 1.1.1), vom preciza i culoarea ptratului care se deseneaz (dup deplasarea definit prin comanda {r,u,l,d}). De exemplu -cuvntul w = arbr3arbd3adbl3albu3fdrcr c (C)* descrie imaginea din figura 1.1.4 (unde C={a,b,c,f), iar cu f am notat culoarea fondului care poate fi alb sau poate fi interpretat ca fr culoare ). Pentru funciile picturale de descriere a imaginilor color, -cuvntul echivalent c se definete analog ca i n cazul imaginilor discontinue , doar subcuvintele ij (respectiv ij) se definesc astfel : cr r cd d pentru pentru pentru pentru j0). Pentru imagini alb-negru vom construi -cuvntul astfel : w = wv1,u1wv1,u1+1...wv1,j ...wv1,u2 ... wi,u1wi,u1+1...wi,j...wi,u2 ... wv2,u1wv2,u1+1...wv2,j...wv2,u2 , unde: wi,j = r j d i u u i l j dac f (Sij) = 0 , dac f (Sij) > 0 . (v1 i v2 , u1 j u2)

Pentru c acest cuvnt conine multe deplasri inutile cu creionul ridicat, este necesar o reducere a acestui cuvnt. -cuvntul redus este wr = ref (w) care reprezint -cuvntul independent de retrageri relativ la mulimea retragerilor: R = {ud, du, lr, rl, , }. Pentru imagini color definirea -cuvntului este asemntoare. Subcuvntul wi,j c pentru cazul f (Sij) = c > 0 este wi,j = r j d i c u u i l j , unde prin am notat culoarea invizibil (prin care se permite deplasarea fr colorare). Cuvintele picturale definite anterior sunt echivalente cu funciile picturale, dar nu sunt minimale. Desigur, ne-ar interesa un algoritm care s construiasc un cuvnt de descriere ct mai scurt posibil, plecnd de la o funcie pictural f.

Algoritmul 1.1.1.

Construiete graful G=(V,A) astfel : V={ (i,j) / f(Sij) > 0 }, A=V V; Calculeaz distanele directe ( : A N) dintre vrfuri astfel : ((i1,j1), (i2,j2))= | i1 i2 |+| j1 2|, ((i1,j1), (i2,j2))A, j Determin cel mai scurt lan hamiltonian, H = ( vi1, vi2, ... , vin) ( n=|V| );

7

Construiete cuvntul de descriere w = Reduc(ci1r i2 wi3 ... win), unde w | j1-j2 |-1 c wik =2 k n -

dac i1=i2 , dac i1i2 ; iar (1.1.1)

| j1-j2 |-1 d | i2-i1 | -1 c d | j1-j2 |-1 u | i2-i1 | -1 c u

ci1 este culoarea ptratului vi1, (i1,j1) i (i2,j2) sunt coordonatele vrfurilor vik-1 respectiv vik-1 , =r pentru j1j2, c reprezint culoarea ptratului Si2,j2 (c=f (Si2,j2)>0), invizibil , dac f (Si2,j2)=0, Reduc(c)=c (nu se ridic creionul dac urmeaz imediat o culoare). Lema 1.1.2.

- reprezint culoarea -

Algoritmul 1.1.1 determin un cuvnt minimal de descriere a unei imagini definit prin funcia pictural f . Demonstraie. Se observ c formula 1.1.1 urmrete deplasarea cursorului ncepnd din vrful vi1 prin ptratele vi2, ... , vik , ... , vin , pe care le coloreaz. n funcie de poziia relativ a dou ptrate consecutive (vik-1 , vik) din lanul hamiltonian, cursorul se va deplasa pe unul din cele patru trasee din figura 1.1.5. Din cele C u trasee ( u = | j1 j2|, iar v = |i1 i2|, vezi figura 1.1.6), nu u+v conteaz pe care l vom parcurge pentru c n dreptungiul definit de cele dou vrfuri diagonal opuse nu exist nici un vrf pe care trebuie s-l colorm (dac ar exista, atunci lanul determinat nu mai este minim) .

i1 < i2 j1 < j2

i1 > i2 j1 < j2

i1 < i2 j1 > j2

i1 > i2 j1 > j2 Figura 1.1.6

Figura 1.1.5

8

n cele ce urmeaz vom studia diverse moduri de descriere a imaginilor de tip 3 (formate din linii i curbe). Pentru c descrierea imaginilor formate din linii a fost prezentat n primul capitol (utiliznd -limbaje), n continuarea acestui paragraf vor fi prezentate cteva tehnici de descriere a curbelor. O imagine este de tip 3 dac poate fi complet descris printr-un numr finit de linii i curbe [3]. O curb poate fi aproximat utiliznd o mulime de puncte alese dintr-o mulime de puncte din plan (de exemplu dintr-un sistem cartezian rectangular, ca n figurile 1.1.7 i 1.1.8). Prin unirea punctelor apropiate de curb se va obine o aproximare poligonal format din segmente de lungime unitate sau 2 . Aceast aproximare se poate reprezenta prin iruri de comenzi (pe cele 4 sau 8 direcii). De exemplu curba din figura 1.1.7 se poate aproxima prin desenul descris de cuvntul urruurur iar curba din figura 1.1.8 prin aaura (am notat cu a deplasarea pe direcia NE). Acest procedeu de trecere de la o imagine reprezentat prin curbe la o imagine reprezentat prin puncte se numete determinarea punctelor critice, iar procedeul invers se numete interpolare. Figura 3.1.7

Figura 1.1.8

Mulimea punctelor critice determinate de curba cR2 este MPc(c)={Apr(P)/Pc} (Apr : R2 Z2, returneaz cel mai apropiat punct de coordonate ntregi). O imagine reprezentat prin puncte (de tip 4) poate fi mbuntit prin interpolare, obinnd o imagine reprezentat prin curbe. Pentru a ilustra aceasta, am ales interpolarea Bezier (descris n [3]). n figurile urmtoare (1.1.9 i 1.1.10) se poate vedea o curb i punctele critice determinate, apoi descrierea corespunztoare -cuvntului rezultat (pentru patru respectiv opt direcii), iar n final curba Bezier corespunztoare.

Figura 1.1.9

Figura 1.1.10 9

Modul de determinare al curbei Bezier (din figura 1.1.11), plecnd de la irul de puncte P1,P2,...,Pn este descris n cele ce urmeaz i ilustrat n figura 1.1.12, pentru n=4 (interpolarea Bezier este descris n [6]). Din irul punctelor date P1, P2, ... ,Pn se calculeaz, utiliznd formula de mai jos (1.1.2), un alt ir de puncte P1,2, P2,2, ... ,Pn-1,2 , apoi din punctele calculate vom determina punctele P1,3, P2,3, ... ,Pn-2,3 (utiliznd aceeai formul) i aa mai departe pn cnd vom ajunge la un singur punct P1,n. Acest punct obinut pentru o valoare [0,1] aparine curbei Bezier. Dnd valori lui din acest interval vom obine aproximarea dorit (n figura 1.1.12, =1/4).

P2 PlB1

P3B2 B3 B4 P4

Figura 1.1.11 P3P2,3

P2 P1,2 PlP1,3

P2,2 P1,4(1/4)

P3,2

P4

Figura 1.1.12 Se observ c pentru =0 se obine punctul P1 iar pentru =1 se obine punctul Pn. Formula de calcul a irului de puncte de pe nivelul m+1 n funcie de punctele de pe nivelul m este urmtoarea : Pi,m+1()=(1 Pi,m()+ Pi+1,m() ; i=1,n m=1,n =0,1, 1/(s ) m; 1; 1) (1.1.2)

Se observ c formula determin punctele ncepnd de pe nivelul doi, pentru c primul nivel conine punctele date, adic Pi,1()=Pi , i=1,n . Dac dorim s determinm s puncte B1=P1,n(1), B2=P1,n(2), ... , Bj=P1,n(j), ... , Bs=P1,n(s) corespunztoare valorilor 1=0, 2=1/(s ... ,j=(j / (s ... ,s=1, vom 1), 1) 1), calcula coordonatele punctelor P1,n(j) pentru fiecare valoare j. Pentru a obine i alte puncte n afara celor dou capete (pentru c B1 i Bs coincid cu P1 respectiv Pn , ca n figura 1.1.11 pentru s=4), trebuie ca s s fie mai mare dect 2. Algoritmul Bezier de determinare a celor s puncte (Bj, j=1,s) de pe aceast curb este prezentat n cele ce urmeaz. Algoritmul 1.1.2. Pentru i:=1,n execut Pi,1:=Pi; Pentru j:=1,s execut :=(j 1)/(s 1); Pentru m:=1,n execut 1 Pentru i:=1,n execut m Pi,m+1 := (1 Pi,m + Pi+1,m ; ) Bj:= P1,n Sf_alg.

1 10

Algoritmul prezentat ne d ca rezultat un ir de puncte B1,B2,...,Bs. Teoretic, curba de interpolare Bezier (a punctelor P1,P2,...,Pn) este: Bezier(P1,P2,...,Pn) = { P1,n() / [0,1] }. Practic, reprezentatarea grafic a curbei este realizat prin desenarea celor s-1 segmente determinate de irul punctelor B1, B2, ... , Bs , adic BezierSeg(P1,P2,...,Pn) = { BjBj+1 / j=1,s (vezi figura 1.1.11). 1} Se observ n figurile 1.1.9 i 1.1.10 c dac plecm de la o curb c i determinm mulimea punctelor critice MPc(c) , apoi prin algoritmul Bezier calculm punctele Bj, j=1,s , acestea se deprteaz de punctele critice iniiale, adic MPc(c) {Apr(Bj) / j = 1,s}, iar curba c'= BezierSeg(MPc(c)) c. Desigur c ne-ar interesa ca aceast curb determinat prin interpolarea punctelor critice s fie ct mai apropiat de curba iniial, adic : {Apr(P1,n () ) / [0,1]} = {Apr(P) / Pc }. (1.1.3.)

Presupunem c avem o curb c0 , pentru care determinm irul punctelor s0 de coordonate ntregi cele mai apropiate. Acest ir poate fi descris printr-un -cuvnt w astfel nct mulimea punctelor desenului descris de w s fie mulimea punctelor critice corespunztoare curbei c0 , adic : V(dpic(w)) = {Apr(P) / Pc0}. n continuare, dac pentru acest ir de puncte s0=(Sh(a1...ai), i=1,n) determinat de -cuvntul w=a1...an (ir definit prin funcia Sh), determinm curba c1 prin interpolare Bezier, este puin probabil s obinem aceeai curb iniial c0. Aplicnd iterativ acelai procedeu vom obine un ir de curbe c0, c1, c2, ... , cp , ... . Problema care n mod natural se va pune este urmtoarea: Cum pot fi obinute aceste transformri, astfel nct acest ir s fie finit ?. Dac reuim s obinem o curb (prin interpolare) care s menin punctele critice, atunci s1=s0 , deci curba de aproximare nu se mai modific ori de cte ori se aplic aceste transformri : c0 s0 c1 s0 c1 ... . (1.1.5) Observaia 1.1.1. Aceast proprietate (1.1.5) a celor dou transformri (de interpolare i de determinare a punctelor critice) este important, pentru c fiecare transformare este, n acest caz, inversa celeilalte. De exemplu, dup codificarea unei imagini (n scopul comprimrii), decodificarea (adic transformarea invers) se va efectua printr-o interpolare (care s conserve punctele critice, deci descrierea prin -cuvinte). n acest scop, n continuare se va prezenta o transformare (prin interpolare Bezier) care conserv -cuvntul de descriere.

1 11

Pentru a obine un ir de puncte ct mai apropiat de punctele critice, vom grupa punctele P1,P2,...,Pn n subiruri de o anumit lungime q (de exemplu n figura 1.1.13 am grupat cte 5 respectiv cte 7), apoi vom aplica algoritmul Bezier pentru fiecare subir. F Figura 1.1.13 Curba rezultat fiind obinut prin reuniunea curbelor descrise: c = Bezier (P1,...,Pq) Bezier (Pq,...,P2q1) ... Bezier (Pn(n Mod q)+1,...,Pn) Lema 1.1.4. O transformare de tipul 1.1.6, utiliznd grupri de lungime qn execut j:=j 1; Ct_timp (j1

Practic se verific pentru fiecare punct PVE condiiile de tipul celor de mai sus, sau mai simplu, putem spune c P Conturului dac urmtoarea expresie este adevrat: Ob(P) Xor (Ob(u(P)) Or (Ob(d(P))) Or (Ob(P) Xor (Ob(l(P)) Or (Ob(r(P))) , unde Ob(P) = (Culoare(P)= Culoare_Obiect) , Culoare_Obiect { Alb, Negru }. c) Obinerea descrierii conturului prin traversarea punctelor determinate. Mulimea punctelor P determinate anterior se va ordona, prin parcurgerea acestei din vecin n vecin (rezultnd i irul comenzilor de descriere, adic -cuvntul corespunztor) ncepnd cu un punct ales din contur (de exemplu cel mai din stngasus), pn se revine la punctul iniial sau nu se mai poate deplasa. Dac mai exist puncte din contur netraversate se construiete alt cuvnt de descriere i aa mai departe. In final vom avea o mulime de -cuvinte de descriere, deci un -limbaj (aa cum se poate vedea n figura alturat unde vor fi dou cuvinte de descriere).

Figura 3.1.4

30

3.2. ScheletizareObiectele sau scenele pot fi descrise prin diverse structuri compuse din diferite elemente (linii, curbe, etc). De exemplu n recunoaterea caracterelor, amprentelor, cromozomilor, a norilor, etc., sunt necesare transformri ale axei mediane n scopul obinerii unei descrieri a obiectului studiat. n cele ce urmeaz vor fi prezentate dou clase de algoritmi i anume: de scheletizare i de subiere. Intuitiv, putem s definim scheletul ca fiind mulimea punctelor n care se ntlnesc cel puin dou tangente la contur care pleac cu aceeai vitez (vezi figura alturat). Practic, scheletul unui obiect Ob este definit ca fiind mulimea punctelor POb pentru care distana pn la cel mai apropiat punct de pe contur (notat cu (P) ) realizeaz un maxim local. Algoritmul de determinare a scheletului unui obiect este urmtorul:

Figura 3.2.1

Calculeaz (P) pentru toate punctele POb: 1. 0(P) = Culoare(P) {0, 1} , POb;

0 = Negru este culoarea fondului iar 1 = Alb este culoarea obiectului; 2. k(P) = Culoare(P) +

QV4(P)

Min k -1(Q) ,

POb,

Figura 3.2.2

k=1,2,...,limea obiectului;

Determin Scheletul = { S Ob / (S) (P) , P V(S) }

Reconstituirea obiectului avnd scheletul acestuia se poate realiza utiliznd formula :

Obr =

{ OVE / d(O,P)1) nu provoac prin eliminare o deconectare a obiectului (rupere a legturilor) : Ob este conex Ob \ {P} este conex. Defini ia 3.3.1

Figura 3.3.1

3 45 32148 567 110 110111000

R este o regiune conex dac pentru P,Q R exist P0=P, P1,...,Pn=Q Ob astefl nct PiV8(Pi-1), i=1,2,...,n. Observaia 3.3.1

Figura 3.3.2

Extremitile arcelor subiri nu trebuie eliminate prin aceti algoritmi. Notaia 3.3.1 Numrul vecinilor punctului P (de culoare alb, Ob) este : Nv(P)::= |{Q/QOb}V8(P)|. Notaia 3.3.2 Numrul tranziiilor de la 0 la 1 n irul punctelor P1, P2 ,..., P8, P9=P1 este: Nt(P) :: = |{i{1,...,8} / PiOb i Pi+1Ob}V8(P)| (vezi figura 3.3.2, unde Nt(P)=2) Propozi ia 3.3.1 Punctul POb se poate elimina dac urmtoarele condiii sunt ndeplinite:

2 Nv(P) 6 ( dac Nv(P)=1 atunci P este extremitate, iar dac Nv(P)>6 atunci P este punct interior, deci nu se poate elimina nici n acest caz); Nt(P)=1 ( pentru a nu deconecta obiectul ).

Algoritmul const n determinarea i eliminarea punctelor care ndeplinesc propoziia 3.3.1. Verificarea condiiilor se repet pn cnd nu mai sunt modificri n imagine.

32

3.4. Transformri morfologice ( Morphological Processing [4])Termenul de morfologie provine din studiul formelor plantelor i animalelor, dar pentru noi, Morphological Processing ([4]), nseamn determinarea structurii obiectelor din imaginile acestora. Transformrile morfologice constau n operaii prin care un obiect X este modificat de ctre un element structural B rezultnd o form convenabil prelucrrilor ulterioare (recunoaterea formei). Cele dou elemente care interacioneaz (X i B) sunt reprezentate ca mulimi din spaiul Euclidian bidimensional. Majoritatea operaiilor morfologice pot fi definite prin doua operaii de baz, eroziune i dilatare descrise n cele ce urmeaz. Notaia 3.4.1 Translaia lui B n x notat cu Bx, este acea translaie pentru care originea elementului structural B (OB) va coincide cu x (vezi figura alturat). Defini ia 3.4.1 Eroziunea lui X de ctre B, notat cu XO- B, este mulimea tuturor punctelor x pentru care Bx este inclus n X: XO- B = { x / Bx X }. Exemplul 3.4.1oooooooooo oooooooooo oooooooooo oooooooooo oooooooooo oooooooooo oooooooooo oooooooooo oooooooooo oooooooooo oooooooooo oooooooooo oooooooooo oooooooooo oooooooooo oooooooooo oooooooooo oooooooooo

Bx x X B

OB

o o o oo o oo oo o o o oo o oo oo o o oo o oo o oo o o o oo o oo o o o o o o oo o oo o o o o o oo o oo o o o o oo o oo o o o o o oo o oo oo o o o o oo o oo o

Ooo oo

o oo oo o oo oo o o o oo o oo oo o o o o o oo o oo oo oo oo oo oo o oo o oo o oo o o oo o oo oo oo oo oo oo oo oo o oo oo o oo oo o oo o oo o oo o

O-

oo oo

=

Se observ c eroziunea este o operaie de micorare a obiectului.

Legend: o - Origine, o - Obiect, o - Fond, o - ters.

33

Defini ia 3.4.2 Dilatarea lui X prin B, notat cu XO+ B, este mulimea acelor puncte x pentru care Bx i X au cel puin un element (punct) comun: XO+ B = { x / Bx X }. Exemplul 3.4.2ooooooooo ooooooooo ooooooooo ooooooooo ooooooooo ooooooooo ooooooooo ooooooooo ooooooooooooooo ooooooooooooooo ooooooooooooooo ooooooooooooooo ooooooooooooooo ooooooooooooooo ooooooooooooooo ooooooooooooooo ooooooooooooooo ooooooooooooooo ooooooooooooooo ooooooooooooooo ooooooooooooooo ooooooooooooooo

oo o oo oo o o oo o oo oo o o oo o oo oo o o oo o oo o oo o oo o oo o oo o oo o oo oo oo oo o oo oo o o oo o oo oo o o

O+ooo ooo ooo

o oo o oo oo o oo oo o o o oo o oo oo o oo oo o o o oo o oo oo o oo o oo o o oo o oo oo o oo o oo o o oo o oo oo oo o oo oo o oo o oo oo oo o oo oo o oo o oo oo oo o oo o o o oo o oo oo o oo oo o o o oo o oo o oo oo oo o o o oo oo o oo oo o oo o o o oo oo o oo oo o oo oo o oo oo o oo oo o oo oo o oo o oo oo o oo oo o o o oo o oo oo o oo oo o o

O+

ooo ooo ooo

=

Se poate observa c dilatarea este o operaie de extindere a obiectului.

Legend: o - Origine, o - Obiect, o - Fond, o - ters, o - Adugat.

Cele dou transformri morfologice de baz prezentate mai sus au urmtoarele proprieti: a) Invariana la translaie (Tr) : - Tr(X) O+ B = Tr(XO+ B) , - Tr(X) O- B = Tr(XO- B) ; b) Nici una nu este inversa celeilalte : c) Distributivitate : - X O+ (BB') = (XO+ B) (XO+ B') , - X O- (BB') = (XO- B) (XO- B') , - (XY) O- B = (XO- B) (YO- B) ; d) Iteraie : - (X O+ B) O+ B' = X O+ (BO+ B') , 34 (X O+ B) O- B X , (X O- B) O+ B X ;

- (X O- B) O- B' = X O- (BO+ B') , e) Incluziune : i Dac XX' Atunci X O- B X' O- B, B , X O+ B X' O+ B, B ; Dac BB' Atunci X; X O- B X O- B',

f) Dualitate (eroziunea i dilatarea sunt duale fa de complementare notat cu XC): - (XC O+ B) = (X O- B)C . n continuare vom prezenta cteva transformri uzuale, derivate din operaiile de baz (eroziune i dilatare) descrise mai sus. Vom vedea c transformrile axei mediane i subierea pot fi descrise i realizate prin astfel de transformri morfologice. a) BCXC: Potrivirea, notat cu XO* B, verific dac o structur BX i - X O* B= (X O- B) (XCO- BC) = (X O- B) (XO+ BC )C = = (X O- BOb) \ (XO+ BBk) (s-a notat B cu BOb, iar BC cu BBk)*

pentru c dac (XC O+ B) = (X O- B)C (proprietatea f) pentru X i B) rezult c (X O+ BC) = (XC O- BC)C (aplicat pentru XC i BC). (*) BOb trebuie s se potriveasc cu obiectul X, iar BBk cu fundalul (Background); n exemplul de mai jos se caut colurile obiectului pe direcia dreapta-jos:ooooooooo ooooooooo ooooooooo ooooooooo ooooooooo ooooooooo ooooooooo ooooooooo ooooooooo ooooooooo ooooooooo ooooooooo ooooooooo ooooooooo ooooooooo ooooooooo

O*

ooo ooo ooo

=

respectiv pe direcia stnga sus:oooooooooo oooooooooo oooooooooo oooooooooo oooooooooo oooooooooo oooooooooo oooooooooo oooooooooo oooooooooo oooooooooo oooooooooo oooooooooo oooooooooo oooooooooo oooooooooo oooooooooo oooooooooo

O*

ooo ooo ooo

=

35

b) Deschiderea lui X fa de B, notat cu XB este domeniul baleiat de toate translaiile lui B incluse n X: - XB = (X O- B) O+ B; Netezete conturul (elimin asperitile) i separ insulele mici:ooooooooo ooooooooo ooooooooo ooooooooo ooo ooo ooo ooooooooo ooooooooo ooooooooo ooooooooo

X

Booooooooo ooooooooo ooooooooo ooooooooo

ooooooooo ooooooooo ooooooooo ooooooooo

XB

XO- B

(XO- B)O+ B

c) nchiderea lui X fa de B, notat cu XB este duala deschiderii: - XB = (X O+ B) O- B; Blocheaz (nchide) calanele nguste i lacurile mici:ooooooooo ooooooooo ooooooooo ooooooooo ooo ooo ooo ooooooooo ooooooooo ooooooooo ooooooooo

X d) Determinarea Conturlui ( X ): - X = X \ (X O- G);

B

XB

Determin punctele de pe contur fr a da o ordine a acestora:ooooooooo ooooooooo ooooooooo ooooooooo ooooooooo ooooooooo ooo ooo ooo ooooooooo ooooooooo ooooooooo ooooooooo ooooooooo ooooooooo

X

G

Se poate observa n exemplul de mai sus c X O- G reprezint interiorul lui X, pe care dac l eliminm din X vom obine conturul acestuia.

X

e) Subierea, ca operaie mofologic se definete astfel: 36

- X O B = X \ (X O* B); o - obiect, unde: o - fond, * - neutru.

Elementul structural uzual este B = ooo*o*ooo o * *o

;

Pentru o subiere simetric se va aplica succesiv operaia descris mai sus, utiliznd ca element structural obiectul B rotit: X O s B = ((((X O B1) O B2) O ) O Bn), unde: B1=B i Bi = Rotit(Bi-1), 1 i n.oooooooooooooo oooooooooooooo oooooooooooooo oooooooooooooo oooooooooooooo oooooooooooooo oooooooooooooo oooooooooooooo oooooooooooooo oooooooooooooo oooooooooooooo oooooooooooooo oooooooooooooo oooooooooooooo

ooo ooo ooo

X

B

s XOB

f) ngroarea lui X prin B, notat cu X Oo B este duala subierii i se definete astfel: X Oo B = X (X O* B);oooooooooooooo oooooooooooooo oooooooooooooo oooooooooooooo oooooooooooooo oooooooooooooo oooooooooooooo

oooooooooooooo oooooooooooooo oooooooooooooo oooooooooooooo oooooooooooooo oooooooooooooo oooooooooooooo

ooo ooo ooo

X

B

X oB O

g) Scheletul unui obiect X este definit astfel: Fie rDx discul de raz r i centru x; Fie sr(x) mulimea centrelor discurilor de raz r, maximale, coninute n X i care intersecteaz conturul obiectului X n cel puin dou puncte.

Scheletul lui X, notat cu S(X) este mulimea centrelor sr(x): - S(X) =r >0

sr(x) , iar sr(x) = (X O- rD) \ (X O- rD)drD , unde drD este un disc orict de mic;

Obiectul X reconstituit din scheletul su este: - X=r >0

[sr(x) O+ rD ] .ooooooo ooooooo ooooooo ooooooo ooooooo ooooooo ooooooo ooooooo ooooooo ooooooo ooooooo ooooooo ooooooo ooooooo ooooooo ooooooo ooooooo ooooooo

Pentru a obine scheletul unui obiect vom nlocui discul rD cu

37

ooo ooo ooo

X

G

S(X)

elementul de structur (G) definit de un ptrat de dimensiuni 3x3 aa cum se opate vedea n figura alturat:

n acest mod putem obine

Scheletul lui X:nmax nmax

- S(X) =n=0

sn(x) =n=0

[(X O- nG) \ (X O- nG)G ] ,

unde nmax este cel mai mic n pentru care X O- nG = (erodat succesiv devine vid);

Obiectul X reconstituit:nmax

- X=n=0

[sn(x) O+ nG ] .

h) Curare (Prune ), elimin ramurile nedorite, care pot rezulta la o operaie de subiere: - Xpn = X1 [ (X2O+ G)

X ] , unde:

X1 = X O s E ;8

X2 =j= 1

[ X1O* E j ] ;o - obiect, o - fond, * - neutru.

E= ; *** o o ***oooooo

oooooooooooooo oooooooooooooo oooooooooooooo oooooooooooooo oooooooooooooo oooooooooooooo oooooooooooooo

ooo ooo ooo

X

B

oooooooooooooo oooooooooooooo oooooooooooooo oooooooooooooo oooooooooooooo oooooooooooooo oooooooooooooo

Xpn

38

Lucr ri de laborator1. Reprezentarea imaginilor prin funcii picturale i cuvinte picturale (1.1)

Conversii ntre imagini descrise prin funcii picturale i cuvinte picturale (algoritmii 1.1.1-1.1.3), descrieri prin puncte critice i aproximare Bezier.

2. Reprezentarea imaginilor prin arbori (1.2)

Codificarea i decodificarea unei imagini digitale utiliznd quad arbori i arbori binari.

3. mbun tirea imaginilor - Operaiuni punctuale (2.1)

S se genereze pe ecran o imagine i apoi s se aplice o transformare de mbuntire a imaginilor prin operaiuni punctuale (accentuarea contrastului, reducerea zgomotului i modificarea histogramei).

4. mbun tirea imaginilor - Operaiuni spaiale (2.2)

S se genereze o imagine pe ecran iar apoi s se aplice acesteia o transformare de mbuntire utiliznd operaiuni spaiale (mediere, filtrare i accentuarea conturului).

5. mbun tirea imaginilor - Operaiuni spaiale (2.2)

Dilatarea, mbuntirea i pseudocolorarea unei imagini medicale date de tip 2 (cu nuane de gri).

6. Transform ri ale imaginilor - Determinare contur, Scheletizare, Subiere (3.1-3.3)

Aplicai cele trei transformri (Determinare contur, Scheletizare i Subiere) unei imagini generate pe ecran.

7. Transform ri ale imaginilor (II) - Transformri morfologice (3.4)

Aplicai cele dou transformri de baz (Eroziune i Dilatare), plus nc dou oparaii (de acest tip, la alegere), unei imagini aflate pe ecran.

39

Bibliografie

1. A.K. Jain, Fundamentals of DigitalImage Processing, Prentice-Hall, London, 1989. 2. S. Nedevski, Prelucrarea Imaginilor i Recunoaterea Formelor, Editura Albastr, Cluj-Napoca, 1998. 3. T. Pavlidis, Algorithms for Graphics and Image Processing, Springer-Verlag, Berlin-Heidelberg, 1982. 4. V. Prejmerean, Grafic pe calculator i prelucrri de imagini, Litografia Universitii de Nord Baia Mare, 2000. 5. A. Vlaicu, Prelucrarea digital a imaginilor, Editura Albastr, Cluj-Napoca, 1997. 6. A. Watt, 3D Computer Graphics, Addison-Wesley, Great Britain, 1993.

40