+ All Categories
Home > Documents > Manual ID Gpi

Manual ID Gpi

Date post: 31-Dec-2015
Category:
Upload: marian-dragomir
View: 87 times
Download: 0 times
Share this document with a friend
Description:
asd
144
Grafică pentru calculator. Note de curs. Material în construcţie! Pentru lămuriri şi observaţii, a se contacta: [email protected] INTRODUCERE Bibliografie: Grafică: Foley & van Dam “Computer Graphics. Principles and Practice”. Addison Wesley, 1999. Prelucrarea imaginilor: V. Gui, D. Lacrămă, D. Pescaru “Prelucrarea imaginilor” (Ed. “Politehnica” 1999) Introducere Grafica pentru calculator şi prelucrarea imaginilor sunt discipline înrudite. Aplicaţii ale graficii de calculator: desen tehnic industrial (CAD) desene animate producţia grafică artistică şi publicitară (TV, WWW, CD...) jocuri pe calculator realitate virtuală (jocuri, medicină, simulatoare, CAD...) Aplicaţii ale prelucrării imaginilor ameliorarea imaginilor restaurarea imaginilor compresia imaginilor analiza imaginilor recunoaşterea formelor în imagini baze de date imagistice Aplicaţii comune suprarealitate comunicaţii om maşină de calcul Elemente comune: se adresează vederii o parte din suportul teoretic unele echipamente hardware utilizate intensiv (ecran, LUT, printer, PC, mouse etc.)
Transcript
Page 1: Manual ID Gpi

Grafică pentru calculator. Note de curs. Material în construcţie!Pentru lămuriri şi observaţii, a se contacta: [email protected]

INTRODUCERE

Bibliografie: Grafică:

Foley & van Dam “Computer Graphics. Principles and Practice”. Addison Wesley, 1999.Prelucrarea imaginilor:

V. Gui, D. Lacrămă, D. Pescaru “Prelucrarea imaginilor” (Ed. “Politehnica” 1999)

Introducere

Grafica pentru calculator şi prelucrarea imaginilor sunt discipline înrudite.

Aplicaţii ale graficii de calculator: desen tehnic industrial (CAD) desene animate producţia grafică artistică şi publicitară (TV, WWW, CD...) jocuri pe calculator realitate virtuală (jocuri, medicină, simulatoare, CAD...)

Aplicaţii ale prelucrării imaginilor ameliorarea imaginilor restaurarea imaginilor compresia imaginilor analiza imaginilor recunoaşterea formelor în imagini baze de date imagistice

Aplicaţii comune suprarealitate comunicaţii om maşină de calcul

Elemente comune: se adresează vederii o parte din suportul teoretic unele echipamente hardware utilizate intensiv (ecran, LUT,

printer, PC, mouse etc.)

Elemente distinctive:Grafica generează imagini, prelucrarea imaginii modifică sau

analizează imagini.

Reprezentare numerică:

Imagine: matrice cu elementul general fx,y – pixel pixelul= nivel gri (0-255) sau culoare (triplet R,G,B)secvenţe de imaginiimagini 3D (volumetrice)imagini multispectrale

Memoria ocupată este relativ mare (n* 100K octeţi)

Page 2: Manual ID Gpi

Grafică pentru calculator. Note de curs. Material în construcţie!Pentru lămuriri şi observaţii, a se contacta: [email protected]

Elementele grafice (curbe, suprafeţe, caractere) sunt reprezentate intern prin modele. Modelul este caracterizat printr-un set de parametri, ce pot fi grupaţi formal într-un vector. O asemenea reprezentare este independentă de contextul hardware utilizat la redare (rezoluţia ecranului, printerului etc.) şi în special mult mai concisă decât imaginea (uzual forma finală pentru vizualizare). Necesită un proces de conversie pentru redarea pe ecran sau imprimare.

1.1. Domeniul prelucrărilor de imagini

Între toate simţurile cu care suntem dotaţi, sistemul vizual ne furnizează cea mai mare cantitate de informaţii referitoare la mediul înconjurător. Cu toate că percepţia vizuală este departe de a fi complet înţeleasă, ingineria modernă se preocupă intens de problema realizării unor sisteme de vedere artificială, capabile să emuleze, fie şi parţial, capabilităţile sistemului vizual uman. În acest demers, s-au acumulat progrese importante în decursul ultimelor decenii, prin contribuţiile conjugate ale cercetărilor din matematică, fizică, electronică, tehnică de calcul, biologie, fiziologie, psihologie, inteligenţă artificială etc. Aflat într-un proces de dezvoltare rapidă, domeniul prelucrării imaginilor este unul interdisciplinar şi pluridisciplinar.

În sens restrâns, obiectivul prelucrării numerice a imaginilor constă în transformarea imaginii în scopul facilitării interpretării vizuale sau al reducerii cerinţelor de memorie pentru reprezentare sau stocare, respectiv al debitului de date sau benzii de frecvenţă necesare transmiterii la distanţă. În sensul cel mai larg, prelucrarea poate urmări măsurarea unor parametri de poziţie, viteză de mişcare sau formă al unor obiecte, recunoaşterea obiectelor dintr-un cadru de imagine, interpretarea scenei sau recunoaşterea tipului de activităţi ce sunt surprinse în videosecvenţe. O reprezentare generală schematizată a etapelor de prelucrare a unei imagini este redată în Fig. 1.1. Nu întotdeauna toate etapele reprezentate sunt necesare.

Imaginile supuse prelucrării sunt adesea afectate de ceea ce denumim generic “zgomot”. Agitaţia termică a electronilor în senzorii de imagine şi în dispozitivele şi circuitele electronice utilizate în amplificarea şi conversia digitală a imaginii este doar una din numeroasele surse ce afectează calitatea acesteia. Imperfecţiuni ale sistemului optic, turbulenţa atmosferică, fenomenele meteo, iluminarea neuniformă, sau umbrele sunt alţi factori ce fac necesară dezvoltarea tehnicilor de preprocesare. Tehnicile de preprocesare sunt clasificate în tehnici de ameliorare şi de tehnici de restaurare a imaginilor. În restaurare, prelucrarea este ghidată de un model fizic riguros al procesului de degradare ce se doreşte a fi inversat.

Page 3: Manual ID Gpi

Grafică pentru calculator. Note de curs. Material în construcţie!Pentru lămuriri şi observaţii, a se contacta: [email protected]

Fig. 1.1. Etape ale procesului de prelucreare şi analiză a imaginii.

Un exemplu de operaţie de preprocesare este eliminarea zgomotului, cu ajutorul unui filtru de netezire, aşa cum se ilustrează pentru imaginea de angiocardiografie radionuclidică de echilibru din Fig. 1.2.

Fig. 1.2. Exemplu de filtrare de netezire a unei imagini.

ACHIZIŢIEIMAGINE

PREPROCESARE

SEGMENTARE

ANALIZĂ/INTERPRETARE

RECUNOAŞTEREFORME

DESCRIERE

MODEL

Page 4: Manual ID Gpi

Grafică pentru calculator. Note de curs. Material în construcţie!Pentru lămuriri şi observaţii, a se contacta: [email protected]

Prin segmentare, se umăreşte fragmentarea imaginii într-o serie de regiuni, pe baza unor atribute ale imaginii ce sunt aproximativ constante în fiecare regiune dar diferă semnificativ de la regiune la regiune. Ideal, regiunile corespund obiectelor sau unor părţi de sine stătătoare ale acestora. Un exemplu de segmentare a ventriculului stâng în imaginea din exemplul anterior se găseşte în Fig. 1.3.

Fig. 1.3. Exemplu de segmentare a ventriculului stâng (mărit la scara 2:1).

În aplicaţiile de recunoaştere a formei, obiectul segmentat este supus unor operaţii de extragere de trăsături caractetistice, ce descriu forma sau textura segmentului şi stau la baza procesului ulterior de clasificare, pe baza vectorului descriptor al caracteristicilor. În aplicaţie de analiză a imaginii scintigrafice, segmentarea are ca obiectiv măsurarea volumului de sânge din ventriculul stâng în imaginile corespunzătoare celor două faze extreme (sistolă şi diastolă) ale ciclului cardiac. Pe baza lor, se poate determina fracţia de ejecţie a ventriculului stâng,

FE = (Vmax-Vmin) / Vmax ,

reprezentând un indicator important al sinergiei mişcării de contracţie şi stării de sănătate a inimii.

1. 2. Percepţia vizuală

Înţelegerea principiilor de bază ale percepţiei vizuale este importantă pentru oricine este implicat în prelucrarea imaginilor din motive multiple. În analiza imaginilor, rezultatul prelucrării este o imagine în care utilizatorul trebuie să “perceapă” mai uşor ceea ce îl interesează. În compresie, rezultatul este o imagine reprezentată concis, în care utilizatorul trebuie să nu perceapă, pe cât posibil, diferenţa faţă de imaginea originală. Pe de altă parte, progresele în înţelegerea percepţiei vizuale ajută la elaborarea metodelor de prelucrare.

1.2.1 Ochiul umanLumina incidentă pe ochi străbate un sistem optic compus dintr-o lentilă (cristalinul) şi o diafragmă (pupila), formînd o imagine pe retina situată pe fundul ochiului. Retina conţine două categorii de elemente fotosensibile: conuri, în număr de aproximativ 6.000.000 şi bastonaşe,

Page 5: Manual ID Gpi

Grafică pentru calculator. Note de curs. Material în construcţie!Pentru lămuriri şi observaţii, a se contacta: [email protected]

în număr de aproximativ 120.000.000. Zona centrală, foveea, conţine numai conuri, care au densitatea maximă în această regiune. Pe măsură ce ne îndepărtăm de zona centrală, densitatea conurilor scade. Treptat, apar şi bastonaşele, a căror densitate este mai redusă. Conurile sunt răspunzătoare de acuitatea spaţială şi de vederea colorată la niveluri de iluminare ridicate, corespunzătoare luminii zilei (vedere fotopică). Există trei tipuri de conuri, cu sensibilităţi maxime la roşu, verde-gălbui şi albastru. Primele două tipuri de conuri sunt dispuse numai în zona foveală, în timp ce conurile albastre se găsesc şi în afara ei. Bastonaşele sunt mult mai sensibile la lumină decât conurile şi sunt răspunzătoare de vederea la iluminare redusă (vederea scotopică). Deoarece bastonaşele sunt toate de acelaşi tip, la iluminare redusă percepţia culorilor nu este posibilă. La niveluri de iluminare intermediare, ambele tipuri de vedere se îmbină (vedere mesopică).

Lumina absorbită de receptori iniţiază reacţii chimice care dispersează pigmentul fotosensibil, reducând sensibilitatea generală. Acest mecanism acţionează ca un sistem de reglare automată a sensibilităţii. Mecanismul menţionat este lent, adaptarea la nivelul general de iluminare a scenei necesitând un timp de reacţie de ordinul minutelor.

Celulele fotoreceptoare sunt interconectate lateral prin intermediul celulelor amacrine. Conexiunile produc o reducere a semnalului furnizat de o celulă când vecinii sunt iluminaţi (fenomenul de inhibiţie laterală). În acest mod se explică procesul de accentuare a contururilor la nivelul sistemului vizual, ce poate fi pus în evidenţă de exemplu prin fenomenul Mach, prezentat puţin mai jos.

Conexiuni pe verticală se stabilesc prin celulele ganglionare la fasciculul nervului optic. Acesta conţine numai aproximativ 800.000 de nervi, ceea ce demonstrează că informaţia vizuală suferă o prelucrare la nivelul retinei. Informaţia transportată de nervul optic se bazează pe impulsuri electrice. Se presupune că informaţia este codificată prin frecvenţa acestor impulsuri, cuprinsă între 200 cicli pe secundă la întuneric şi 300 cicli pe secundă la lumină, la saturaţie. Informaţiile preluate de cele două fascicule de nervi optici (stâng şi drept) se încrucişează şi se despart în chiasma optică, combinându-se în nucleii geniculaţi, pentru a se proiecta în final în zona cortexului vizual, situată în lobii occipitali. Se presupune că, până la proiectarea pe cortex, informaţia mai este prelucrată intensiv.

1.2.2 Percepţia luminanţei

Datorită mecanismelor de adaptare, gama dinamică a intensităţilor percepute de sistemul vizual uman (SVU) este uriaşă, de ordinul 1010. Cu toate acestea, pentru un anumit nivel de adaptare (ce se poate schimba relativ încet datorită naturii chimice a proceselor responsabile) gama dinamică percepută este mai mică decât 102. Percepţia luminanţei este influenţată de mai mulţi factori.

Page 6: Manual ID Gpi

Grafică pentru calculator. Note de curs. Material în construcţie!Pentru lămuriri şi observaţii, a se contacta: [email protected]

Pentru lumină acromatică, factorii principali sunt:a) iluminarea fundaluluib) schimbările de luminanţă în zone apropiate stimululuic) forma spaţială şi variaţia temporală a stimulului

Efectele de mai sus interacţionează, dar pentru mai multă claritate, le vom analiza independent.

Iluminarea fundalului are efecte ce pot fi studiate folosind aranjamentul din Fig.1.4

Fig. 1.4. Schema experimentului pentru studiul percepţiei luminanţei.

Subiectul trebuie să stabilească pragul L la care zona stimulului se distinge pe fundalul apropiat, la diferite iluminări ale fundalului apropiat şi îndepărtat. Rezultatele acestor experimente sunt redate în Fig.1.5. Se observă că raportul L/L, denumit fracţie Weber, este aproximativ constant, ceea ce implică o percepţie logaritmică a luminanţei, asemenea celorlalte simţuri. La luminanţe reduse, fracţia Weber creşte uşor. O valoare orientativă a fracţiei Weber este 2%, ceea ce corespunde capacităţii de a se distinge aproximativ 50 de niveluride luminanţă într-o imagine cu contrast ridicat. Pe un ecran de calculator sau TV, numărul lor este uşor redus faţă de această cifră.

Influenţa fundalului îndepărtat este de fapt o manifestare a efectului menţionat la punctul b), denumit fenomen de mascare. Datorită conturului ce se formează între fundalul apropiat şi cel îndepartat, se produce o creştere a pragului de sensibilitate. Rezultatul este util în compresia imaginilor pentru că el relevă faptul că zonele cu texturi complicate pot fi redate cu un număr redus de niveluri de gri, fără ca acest lucru să fie sesizat de observatorul uman. Prezenţa fundalului

Lb

1.5 grd.

Ls

Zonă fundalapropiat

Zonă stimul

Zonă fundalîndepărtat

Lb+L

Page 7: Manual ID Gpi

Grafică pentru calculator. Note de curs. Material în construcţie!Pentru lămuriri şi observaţii, a se contacta: [email protected]

afectează nu numai pragul de sensibilitate ci şi nivelul de luminanţă perceput.

Fig. 1.5. Rezultatele experimentelor privind percepţiei luminanţei.

Un experiment interesant ce pune în evidenţă relativitatea percepţiei luminanţei este ilustrat în Fig. 1.6. Cele două regiuni pătrate cu luminanţe identice sunt percepute cu luminanţe diferite când sunt separate şi plasate pe fundal diferit.

Fig. 1.6. Relativitatea percepţiei luminanţei.

Relativitatea percepţiei nu se limitează la luminanţă. Dimensiunile percepute sunt supuse unei legi similare (Fig. 1.7). Cercurile interioare par de dimensiuni diferite. Linia superioară pare mai lungă.

Lb <mL>

L <mL> Ls=50mL

Ls=Lb

L/Lb=ct.

0.1

2

10.50.2

0.05

0.02

5

1 2 5 10 20 50 100

Page 8: Manual ID Gpi

Grafică pentru calculator. Note de curs. Material în construcţie!Pentru lămuriri şi observaţii, a se contacta: [email protected]

Fig. 1.7. Iluzii optice ce ilustreză relativitatea percepţiei dimensiunilorTrebuie evitată confuzia care se face uneori între fenomenul de

mascare şi fenomenul Mach. Ultimul este o manifestare directă a inhibiţiei laterale, care operează o filtrare de tip trece-sus, ce poate fi modelată prin convoluţia cu un operator obţinut prin derivarea de ordinul doi a unei funcţii gaussiene. În Fig. 1.8 se ilustrează fenomenul Mach cu ajutorul mirei cu trepte de gri. O bandă uniformă este percepută mai luminoasă în stânga ei şi mai întunecată în partea dreaptă prin efectul derivativ al inhibiţiei laterale.

Fig. 1.8. Fenomenul benzilor MachEfectul de mascare se manifestă şi în domeniul temporal.

Percepţia obiectelor aflate în mişcare este dependentă de faptul dacă observatorul urmăreşte obiectul de-a lungul traiectoriei sau atenţia nu este fixată pe un anumit obiect. Este util să reţinem orientativ că, în cazul mişcărilor violente, rezoluţia obiectului aflat în mişcare poate fi redusă de zece ori fără a fi percepută, cu condiţia de a fi restabilită la valoarea normală în mai puţin de o jumătate de secundă de la încetarea mişcării.

O formă importantă de manifestare a pragului de vizibilitate temporală este frecvenţa critică de fuziune a imaginilor. Presupunând că stimulul este descris de o lege de variaţie de forma:

Se poate determina vizibilitatea stimulului în funcţie de L, L şi f. Pentru o curbă L = ct., L are un maxim în jurul frecvenţei de 15 cicli pe secundă. La frecvenţe mari, răspunsul se anihilează rapid în jurul valorii de 70 Hz. Mărimea suprafeţei stimulului de pâlpâire influenţează, de asemenea, vizibilitatea lui. Este un aspect ce a fost deja exploatat în televiziune, prin alegerea modului de explorare întreţesută şi reducerea frecvenţei cadrelor la numai 25 Hz.

1.2.3 Acuitatea vizuală

Acuitatea vizuală reprezintă capaciatea SVU de a detecta detalii în imagine. Efectul formei spaţiale asupra vizibilităţii stimulului se poate

S(t)=L+ L cos(2ft), (1.1)

Page 9: Manual ID Gpi

Grafică pentru calculator. Note de curs. Material în construcţie!Pentru lămuriri şi observaţii, a se contacta: [email protected]

determina considerând SVU un sistem liniar bidimensional (neliniaritatea poate fi neglijată la amplitudini mici ale stimulului). Pentru a-i determina funcţia de transfer, se generează un stimul de forma unei sinusoide spaţiale:

unde s-a notat:

O miră cu un semnal stimul modulat în amplitudine ( L) pe verticală şi în frecvenţă (x) pe orizontală este ilustrată în Fig. 1.9. Rezultatele experimentale se prezintă uzual sub forma caracteristicii senzitivităţii contrastului, reprezentând caracteristica percepută, L / L funcţie de frecvenţa spatială, x, măsurată în cicli pe grad. Forma este de filtru trece-bandă. Practic, acest lucru înseamnă că ochiul este mai puţin sensibil la variaţii spaţiale foarte lente sau foarte rapide ale luminanţei. Căderea răspunsului la frecvenţe joase se poate atribui fenomenului de inhibiţie laterală, ce ridică frecvenţele înalte. Se obţine un efect de accentuare a contururilor ce au un rol central în interpretarea informaţiei vizuale. La frecvenţe foarte înalte, căderea este datorată sistemului optic şi rezoluţiei finite a fotoreceptorilor. Răspunsul este mai slab la marginile câmpului vizual, pentru vederea periferică. Senzitivitatea contrastului prezintă maxime pe direcţiile orizontală şi verticală, având o cădere maximă (de 3dB) pe direcţiile diagonale. În optică, rezoluţia este definită de inversul valorii unghiului de vedere maxim (aproximativ 2 minute) la care două puncte alăturate nu pot fi distinse. Rezoluţia este maximă la distanţa de 250 mm şi iluminarea de 500 lux (furnizabilă de un bec de 60 W la distanţa de 400 mm). În aceste condiţii, distanţa dintre două puncte ce pot fi distinse este de aproximativ 0.16 mm.

Experimente mai generale fac apel la modulaţia spaţio-temporală. Stimulul generat este de forma:

Se confirmă faptul că SVU se comportă ca un filtru trece-bandă şi în domeniul temporal. Teste cu mixaje de semnale sinusoidale de frecvenţe diferite arată că stimulii interacţionează numai dacă frecvenţele lor sunt separate cu mai puţin de o octavă. Aceste constatări pot fi sintetizate într-un model al SVU de tipul unei bănci de filtre trece bandă. Pe această bază sunt construite compresoarele de imagine de tip sub-bandă.

S(xx)=L+ L cos(xx), (1.2)

x=2fx. (1.3)

L(x,y,t) = L+ L cos[2fv (xcos y sin)] cos(2ft t) (1.4)

Page 10: Manual ID Gpi

Grafică pentru calculator. Note de curs. Material în construcţie!Pentru lămuriri şi observaţii, a se contacta: [email protected]

Fig. 1.9. Semnal 2D pentru studiul dependenţei acuităţii vizualede contrast

1.2.4 Percepţia culorilor

Culoarea este o proprietate foarte importantă a imaginilor, deoarece ochiul distinge într-o imagine mult mai multe culori decât trepte de gri. Sistemul vizual uman percepe senzaţia de culoare în funcţie de lungimile de undă ale radiaţiilor electromagnetice vizibile (sau luminoase). Spectrul radiaţiilor electromagnetice vizibile (Fig. 1.10) se întinde de la lungimea de undă de aproximativ 700 nm, corespunzătoare culorii roşii, la aproximativ 400 nm, corespunzătoare culorii violet.

Fig. 1.10. Spectrul radiaţiilor vizibile

Radiaţiivizibile

Infra-roşu

Ultra-violet

RazeX

Razegama

Micro-unde

Radio-frecvenţ

ă0,001nm 1nm 10nm 400nm 0,7m 25m 0,1m 1km

violet albastru

verde galben orange roşu

400 450 480 550 580 610 700

Page 11: Manual ID Gpi

Grafică pentru calculator. Note de curs. Material în construcţie!Pentru lămuriri şi observaţii, a se contacta: [email protected]

În natură, culorile reprezintă rezultatul amestecului unui număr mai mare sau mai mic de radiaţii cu lungimi de undă diferite. Lumina albă conţine toate lungimile de undă din domeniul menţionat în proporţii egale, altfel spus, are o distribuţie spectrală uniformă. Obiectele absorb o parte din lumina ambiantă, partea din spectru neabsorbită fiind transmisă de obiectele transparente sau translucide, respectiv reflectată de cele opace. Culoarea obiectului este determinată de lumina reflectată, mai precis de lungimile de undă ale radiaţiilor reflectate şi de proporţiile dintre energiile acestor radiaţii.

Orice culoare poate fi sintetizată prin amestecul în proporţii adecvate a unui număr de culori de bază. Din colorimetrie se cunoaşte faptul că, folosind numai trei culori de bază, se poate obţine practic orice culoare. Suficienţa unui număr de trei culori de bază este legată direct de existenţa pe retină a trei tipuri de conuri, cu sensibilitate maximă la roşu, verde şi albastru. În televiziune, au fost adoptate aceleaşi culori de bază: roşu, verde şi albastru (sistemul de coordonate color RGB). Este interesant că decizia a fost luată înaite de a se fi demonstrat existenţa celor trei tipuri de conuri.

Observaţie: folosind un sistem unic de culori de bază, de exemplu RGB, se poate reproduce un număr foarte mare de culori, dar nu orice culoare din spectrul natural.

Amestecul culorilor pe ecran unui tub cinescop are loc aditiv, adică prin însumarea radiaţiilor emise de luminoforii roşu, verde şi albastru activaţi de fasciculul de explorare. În tipografie, amestecul culorilor se produce substractiv. De exemplu, o cerneală roşie depusă pe hârtie absoarbe din spectrul uniforma al unei surse de lumină albă ce se proiectează pe ea toate radiaţiile cu excepţia celor situate într-un interval de lungimi de undă corespunzător culorii roşii. Culorile primare folosite în televiziune şi tipografie şi modul lor de compunere sunt ilustrate în Fig. 1.11.

1.2.5 Atributele culorilorPresupuând că o culoare este reprezentată prin vectorul RGB, intensitatea ei poate fi calculată cu ajutorul relaţiei:

Ecuaţia de mai sus, reflectă faptul că ochiul prezintă sensibilităţi diferite pentru radiaţiile luminoase cu lungimi de undă diferite. În cazul culorilor de bază, sensibilitatea este maximă pentru verde şi minimă pentru albastru.

Y=0,3R+0,59G+0,11B. (1.5)

Page 12: Manual ID Gpi

Grafică pentru calculator. Note de curs. Material în construcţie!Pentru lămuriri şi observaţii, a se contacta: [email protected]

Fig. 1.11. Culorile primare şi compunerea lor în televiziune şi tipografie

Un alt atribut al culorii este nuanţa ei, semnificând lungimea de undă dominantă din componenţa ei spectrală. Nuanţa depinde exclusiv de proporţiile în care sunt prezente culorile primare şi nu de valorile absolute. Aceste proporţii sunt exprimate de coeficienţii tricromatici:

De observat că toţi coeficinţii sunt subunitari şi suma lor este întotdeauna egală cu 1.

roşu

albastru

verde

alb

galben magenta

cian

Compunerea aditivăa culorilor primare

în televiziune

magenta

ciangalben

negru

roşu albastru

verde

Compunerea substractivăa culorilor primare

în tipografie

(1.6)

Page 13: Manual ID Gpi

Grafică pentru calculator. Note de curs. Material în construcţie!Pentru lămuriri şi observaţii, a se contacta: [email protected]

Saturaţia defineşte proporţia de alb în componenţa culorii. Folosind coeficienţii tricromatici, saturaţia se poate calcula simplu cu ajutorul ecuaţiei:

Culorile saturate (saturaţie 100%) au unul din coeficienţii tricromatici nul, semnificând absenţa totală a uneia din culorile primare. Saturaţia de 0% presupune egalitatea coeficienţilor tricromatici, respectiv un obiect incolor (alb, negru sau gri, în funcţie de intensitate). Culorile nesaturate pot fi considerate un amestec ponderat între o culoare saturată şi alb. Culorile saturate nu conţin lumină albă. Roşul saturat este culoarea metalului încins. Rozul se obţine prin amestecul roşului cu alb, deci prin desaturare. Cerul într-o zi fără nori are culoarea albastră nesaturată.

Principalii factori ce afectează percepţia unui stimul color sunt:a) densitatea spectrală de putere a sursei ce iluminează scenab) caracteristicile de reflectivitate ale obiectelor prezente în imaginec) aranjamentul spaţial, forma şi dimensiunile obiectelor d) răspunsul spectral al observatorului uman (dependent de conţinutul scenei şi obiectul pe care se fixează atenţia)Între aceşti factori există interacţiuni de tipul celor menţionate la imagini acromatice, dar în general mai complexe. De exemplu, fenomenul de adaptare cromatică, nu pe deplin elucidat încă, modifică percepţia culorii într-o regiune a imaginii în funcţie de conţinutul spectral al scenei observate anterior şi de culorile zonelor aflate în proximitate. Adaptarea, la fel ca sensibilitatea logaritmică sau fenomenul de mascare, este o proprietate mai generală a organelor de simţ.

S=1-3min{r, g, b}. (1.7)

Page 14: Manual ID Gpi

Grafică pentru calculator. Note de curs. Material în construcţie!Pentru lămuriri şi observaţii, a se contacta: [email protected]

REPREZENTAREA MATEMATICĂ A IMAGINILOR NUMERICE

2.1. Conversia analog numerică a imaginilor Orice imagine cu dimensiuni finite din lumea reală conţine o infinitate de puncte. Pentru a putea fi reprezentată în formă numerică şi stocată în memoria unui calculator, este necesar un proces de conversie analog/digitală. În esenţă, conversia analog/digitală implică două operaţii distincte: eşantionarea imaginii şi cuantizarea ei.

2.1.1 Eşantionarea imaginilor

În contextul imaginilor, eşantionarea asigură prelevarea informaţiei referitoare la intensitatea sau culoarea imaginii în puncte situate într-o reţea cu pas constant, numită şi grilă de eşantionare (Fig. 2.1).

Fig.2.1. Grilă de eşantionare rectangulară, uniformă

Reconstrucţia exactă a imaginii originale pe baza eşantioanelor prelevate este posibilă teoretic dacă imaginea este un semnal de bandă limitată şi pasul de eşantionare este mai mic decît o limită stabilită de teorema eşantionării.

De notat că imaginile din lumea reală nu sunt semnale de bandă limitată. Pentru limitarea benzii este necesară utilizarea unui filtru de tip trece jos înainte de eşantionare sau concomitent cu acest proces. În literatură, acest filtru este denumit curent ”anti alias”, iar erorile pricinuite de neutilizarea unei asemenea filtrări ”erori alias”. Aşa cum

Eşantionarea poate fi definită ca un proces prin care, dintr-o mulţime conţinînd un număr (posibil infinit) de elemente se extrage o submulţime cu un număr finit de elemente.

Pasul critic de eşantionare este invers proporţional cu dublul benzii de frecvenţă.

Page 15: Manual ID Gpi

Grafică pentru calculator. Note de curs. Material în construcţie!Pentru lămuriri şi observaţii, a se contacta: [email protected]

se ilustrează în exemplul unidimensional din Figura 2.2, erorile alias pot produce în unele situaţii o alterare semnificativă a rezultatului eşantionării.

Fig. 2.2. Exemplu de eroare alias la eşantionarea unui semnal sinusoidal, de perioadă spaţială , cu nerespectarea condiţiei x <

1/2.

Imaginile folosite curent în prelucrare conţin între 6464 eşantioane (pixeli) şi 20482048 eşantioane. În Figura 2.3a), este redată o imagine în formatul 256256 pixeli, în timp ce versiunea subeşantionată la 6464 de pixeli este redată în Figura 2.3b). Înainte de reeşantionare, imaginea a fost filtrată cu un filtru anti alias (trece-jos).

Numărul de pixeli de pe linie stabileşte rezoluţia pe orizontală, în timp ce numărul de pixeli de pe coloană stabileşte rezoluţia verticală a imaginii. În optică, rezoluţia se măsoară in inversul unei unităţi de grad. Acuitatea vizuală corespunde unui unghi de aproximativ 2 minute. Detalii ce se proiectează pe pupilă sub un unghi mai mic decât acesta nu mai sunt percepute distinct.

x

x

x=12/11

12

Rezultat

eşantionaresult:

aliasing

Page 16: Manual ID Gpi

Grafică pentru calculator. Note de curs. Material în construcţie!Pentru lămuriri şi observaţii, a se contacta: [email protected]

Fig. 2.3. a) imaginea originală, de 256 256 pixeli; b) imaginea subeşantionată la 64 64 pixeli.

2.1. 2 Cuantizarea imaginilor

Imaginile reale (analogice) conţin o infinitate de nuanţe de gri sau culori. Având în vedere faptul că eşantioanele imaginii sunt reprezentate după conversie folosind un număr finit de biţi, rezultă şi un număr finit de niveluri posibile.

Imaginea din Fig. 2.3 este reprezentată pe 8 biţi, ceea ce corespunde la un număr maxim de 28 = 256 niveluri de gri. În Fig. 2.4, aceeaşi imagine este reprezentată succesiv pe 32, 16, 8, 4 şi 2 niveluri de gri, folosind cuantizare cu pas constant, numită cuantizare uniformă. Se poate remarca la aceste imagini apariţia unor contururi false (fenomen de conturare) în zone de imagine netede, cu variaţii lente ale luminanţei. Fenomenul de conturare este o consecinţă a erorilor introduse de procesul de cuantizare. Conturarea este nu este perceptibilă în imagini redate pe 128 sau 64 de niveloride gri, motiv pentru care acele imagini nu au fost incluse în figură. Practic, erorile sau zgomotul de cuantizare din acele imagini rămân imperceptibile ochiului. Cu toate acestea, zgomotul de cuantizare produce efecte nedorite asupra unor operatori de prelucrare sensibili la zgomot, cum sunt cei de derivare, folosiţi la extragerea contururilor.

Cuantizarea uniformă nu asigură o reprezentare optimă, cu eroare medie patratică minimă, decât pentru cazul particular în care nivelurile de gri au o distribuţie uniformă. Presupunând că se doreşte cuantizarea unei variabile f pe un număr specificat, de Q niveluri de cuantizare, legea de cuantizare.

Mărimile care pot lua un număr finit de valori se numesc cuantizate, iar operaţia prin care o mărime continuă se transformă într-una cuantizată se numeşte cuantizare.

Page 17: Manual ID Gpi

Grafică pentru calculator. Note de curs. Material în construcţie!Pentru lămuriri şi observaţii, a se contacta: [email protected]

Fig. 2.4. Cuantizare uniformă. Imagine cu: a) 32 niveluri de gri; b) 16 niveluri de gri; c) 8 niveluri de gri; d) 4 niveluri de gri; e) 2 niveluri de

gri.

O lege de cuantizare poate fi specificată prin precizarea subdomeniilor mărimii de intrare, f, care se transformă în fiecare nivel de ieşire, ri, numit nivel de reconstricţie. Subdomeniile sunt delimitate de niveluri de decizie, dk (vezi Figura 2.5).

Deoarece sistemele de achiziţie a imaginilor sunt proiectate de cele mai multe ori pentru a servi aplicaţii diverse, distribuţia nivelurilor de gri la conversia analog numerică este în general necunoscută. În medie se poate considera uniformă. În plus, sistemele de achiziţie contemporane asigură o cuantizare suficient de fină pentru a reduce importanţa problemei minimizării erorilor de cuantizare. Totuşi, în numeroase situaţii, optimizarea procesului de cuantizere a imaginilor rămâne de actualitate. Este cazul compresiei imaginilor sau al tipăririi imaginilor color folosind o paletă redusă de culori.

d1 d2 d3

intrare

d-3 d-2

d-1

r2

r1

r0r-

1

r-2

ieşire

Page 18: Manual ID Gpi

Grafică pentru calculator. Note de curs. Material în construcţie!Pentru lămuriri şi observaţii, a se contacta: [email protected]

Fig. 2.5. Exemplu de lege de cuantizare

Uzual distribuţia nivelurilor de gri în imagine este neuniformă. Considerând numărul nivelurilor de cuantizare, Q, fix se pune problema determinării nivelurilor de decizie şi a nivelurilor de cuantizare, astfel încât un anumit criteriu de optimizare să fie realizat. Se presupune cunoscută distribuţia nivelurilor degri (histograma nivelurilor de gri). Cel mai frecvent se impune minimizarea erorii medii patratice, EMP. Se demonstrează [Max 1960] că soluţia îndeplineşte condiţiile următoare:

Prima condiţie stabileşte că fiecare interval este reprezentat (reconstruit) prin valoarea medie a nivelului de gri în interiorul său. De observat că valoarea medie coincide cu mijlocul intervalului numai dacă variabila este distribuită uniform în interiorul intervalului respectiv. Notând cu pi

probabilitatea de apariţie a nivelului fi şi cu Ik intervalul reconstruit prin rk, avem expresia valorii medii:

Condiţia a doua plasează nivelurile de decizie la jumătatea distanţei dintre două niveluri de reconstrucţie, ceea ce asigură alocarea fiecărui nivel de intrare la nivelul de ieşire cel mai apropiat. Soluţia optimă poate fi obţinută prin metode numerice. Pentru unele legi de distribuţie mai frecvent întâlnite în prelucrarea semnalelor (Gauss, Laplace etc.), rezultatele cuantizării optimale sunt tabelate şi pot fi consultate în literatura de specialitate. Pentru legi mai generale, se pot folosi cu succes algoritmi de învăţare nesupervizată (de exemplul algoritmul mediilor).

2.2 Caracterizarea matematică a imaginilor numerice

2.2.1 ReprezentareExistă diferite modalităţi de a interpreta din punct de vedere matematic o imagine numerică. Astfel, imaginea poate fi considerată o secvenţă

1. Nivelurile de reconstrucţie sunt valorile medii (centroizii) variabilei cuantizate în interiorul fiecărui interval determinat de nivelurile de decizie.

2. Nivelurile de decizie sunt situate la distanţe egale de nivelurile de reconstrucţie ale intervalelor adiacente.

(2.1)

Page 19: Manual ID Gpi

Grafică pentru calculator. Note de curs. Material în construcţie!Pentru lămuriri şi observaţii, a se contacta: [email protected]

bidimensională (2D) discretă, definită pe o grilă de format MN, cu elementul general f(x,y), x = 0,1,…,N-1, y = 0,1,…,M-1. Alternativ, imaginea poate fi reprezentată ca o matrice F, de format MN:

Un element al imaginii, f(x,y) sau fm,n este denumit curent pixel (de la termenii din limba engleză ”picture” plus ”element”). Într-o imagine monocromatică, pixelul este un scalar, reprezentând luminozitatea sau nivelul de gri. La imaginile color, pixelul devine un vector,

reprezentând componentele tricromatice ce definesc culoarea. De asemenea, imaginea color poate fi reprezentată cu ajutorul a trei matrici R,G şi B, a trei secvenţe 2D, sau a unei matrice 3D de format MN3. Imaginile multispectrale furnizate de sateliţii de teledetecţie conţin mai mult decât trei componente, uzual 10-15.

Uneori este mai convenabil să reprezentăm imaginea unidimensional, ca un vector lung, f, obţinut de exemplu prin concatenarea coloanelor imaginii. Un element al imaginii poate fi referit în acest caz printr-un singur indice, de exmplu fk.

Vecinătăţi Vecinătăţile V4 şi V8 ale unui pixel p sunt definite grafic în Figura 1.5. Prima conţine numai vecinii orizontali şi verticali, în timp ce a doua îi include şi pe cei diagonali. Considerente legate de analiza topologică a imaginilor bitonale (cuantizate pe un singur bit) impun utilizarea ambelor definiţii. Doi pixeli situaţi reciproc în vecinătatea V4 a celuilalt se numesc 4-conecşi sau 4-adiacenţi. Doi pixeli situaţi reciproc în vecinătatea V8 a celuilalt se numesc 8-conecşi sau 8-adiacenţi.

Distanţe

(2.2)

(2.3)

Page 20: Manual ID Gpi

Grafică pentru calculator. Note de curs. Material în construcţie!Pentru lămuriri şi observaţii, a se contacta: [email protected]

Distanţa euclidiană între doi pixeli, de coordonate p = (xp,yp) şi q = (xq,yq) se calculează cu ajutorul ecuaţiei:

Alte tipuri de distanţă folosite în prelucrarea numerică a imaginilor sunt distanţa d4 (”block city distance”):

şi d8 (”chessboard distance”):

Cercurile de rază unitară, definind cele mai mici vecinătăţi în imaginile digitale sunt ilustrate în Fig. 2.6.

Fig. 2.6. Vecinătăţile unui pixel. a) Vecinătatea V4; b) Vecinătatea V8;

2.2.2 Caracteristici statisticePrelucrarea imaginii poate fi adaptată automat la specificul fiecărei imagini folosind caracteristici statistice ale acesteia. Astfel, distribuţia nivelurilor de gri poate fi utilă pentru recuantizare sau pentru transformarea scării de gri în vederea redării optimale pe ecran sau la prin imprimare. Probabilitatea de apariţie e fiecărui nivel de gri se poate calcula folosind ecuaţia:

x-1 x x+1

y-1

y

y+1

x-1 x x+1

y-1

y

y+1

a) b)

p p

(2.4)

(2.5)

(2.6)

(2.7)

Page 21: Manual ID Gpi

Grafică pentru calculator. Note de curs. Material în construcţie!Pentru lămuriri şi observaţii, a se contacta: [email protected]

unde pi este probabilitatea de apariţie a nivelului zi, ni este numărul de pixeli cu nivelul zi şi Npix este numărul total de pixeli din imagine. Frecvent distribuţia nivelurilor de gri este vizualizată cu ajutorul histogramei nivelurilor de gri:

Histograma normalizată corespunde ecuaţiei (2.7), cu coloanele reprezentând probabilităţile de apariţie ale fiecărui nivel de gri. Un exemplu de imagine cu histograma asociată se găseşte în Figura 2.7. Pe axa orizontală a histogramei este reprezentat nivelul de gri. Pe axa verticală înălţimea fiecărei coloane este proporţională cu numărul de pixeli care au nivelul de gri corespunzător. Factorul de proporţionalitate a fost ales astfel încât înălţimea maximă a coloanei să fie de 128 de pixeli în imaginea histogramei. Procedeul utilizat se numeşte scalare a histogramei.

Fig. 1.6. Imaginea ”boats” (stânga) şi histograma ei (dreapta).

Pentru imagini color sau multispectrale, putem construi câte o histogramă pentru fiecare componentă tricromatică. Alternativ, cele trei histograme pot fi concentrate într-una singură, tridimensională, a cărei vizualizere nu este însă o sarcină simplă. Cel mai frecvent histogramele se calculează global, adică pentru întreaga imagine, însă există şi aplicaţii care fac apel la histograme locale, calculate pe subblocuri precizate ale imaginii.

Media şi dispersia nivelului de gri în imagine se numără printre caracteristicile statistice cele mai simple şi frecvent utilizate în prelucrare. Media de gri a unei imagini f se poate calcula cu ajutorul ecuaţiei:

(2.8)

(2.9)

Page 22: Manual ID Gpi

Grafică pentru calculator. Note de curs. Material în construcţie!Pentru lămuriri şi observaţii, a se contacta: [email protected]

Media pătratică a nivelului de gri are o definiţie asemănătoare:

Dispersia nivelului de gri este:

Dacă dispersia se evaluează regional, pentru un număr de pixeli relativ scăzut, Npix din ultima ecuaţie, se înlocuieşte cu Npix-1. În caz contrar, se poate demonstra că estimatorul dispersiei este unul deplasat.

3. Operatori liniari 2D. Convoluţia 2D discretă Operatorii liniari joacă un rol important în prelucrarea numerică a imaginilor, având la bază un suport teoretic ce a fost în mare parte dezvoltat anterior dezvoltării preocupărilor din domeniul prelucrării numerice a semnalelor.

3.1. Operatorul liniar bidimensional generalizat

În forma serie cea mai generală, un operator liniar 2D (o transformare liniară) este definit prin ecuaţia:

g O j k m n fk

N

j

M

m,n j,k( , ; , )

0

1

0

1

.

(3.1)

Ecuaţia (3.1) arată că un element oarecare al imaginii de ieşire, gm,n, se obţine ca o sumă ponderată a elementelor imaginii de intrare, de dimensiuni MN. Ponderile sunt specificate de nucleul operatorului liniar, O(j,k;m,n). În cazul general, toate elementele imaginii de intrare participă la calculul fiecărui element al imaginii de ieşire. Mai remarcăm faptul că definiţia nu precizează dimensiunile imaginii de ieşire. Acest aspect urmează a fi clarificat pentru formele particulare

(2.10)

(2.11)

Page 23: Manual ID Gpi

Grafică pentru calculator. Note de curs. Material în construcţie!Pentru lămuriri şi observaţii, a se contacta: [email protected]

importante ale operatorului liniar. Ecuaţia (3.1) poate fi scrisă mai concis în reprezentare vectorială:

g = Of. (3.2)

Din punct de vedere practic, suntem adesea interesaţi în operatori liniari separabili, de forma:

O(m,n; j,k) = OC(j;m) OR(k;n). (3.3)

Pentru operatorul liniar separabil, relaţia (3.1) devine:

g O j m O k n fk

N

j

M

m,n C R j,k( ; ) ( ; )

0

1

0

1

.

(3.4)

Se observă că numărul maxim de operaţii pe pixel scade drastic, de la MN la M+N. Operatorul OR(k;n) efectuează prelucrarea unidimensională a tuturor liniilor (rândurilor) imaginii f şi are ca rezultat intermediar o imagine prelucrată pe linii:

p O k n fk

N

j,n R j,k( ; )

0

1

, (3.5)

unde j = 0, 1, ... , M-1 şi n = 0,1, ... , Q-1.Această imagine este apoi prelucrată unidimensional de-a lungul coloanelor:

g O j m pCj

M

m,n j,n( ; )

0

1

, (3.6)

unde m = 0,1, ... , P-1 şi n = 0,1, ... , Q-1. Evident, era posibilă şi altă factorizare, care conducea la ordinea de prelucrare inversată. Examinând ultimele două ecuaţii, se observă că operatorul liniar separabil poate fi scris şi în forma:

G O FO C RT . (3.7)

Şi din această ecuaţie se observă că ordinea de prelucrare este arbitrară, ţinând cont de proprietatea de asociativitate a produsului matricilor.

3.2. Convoluţia bidimensională discretă

Definiţie Un caz particular important este operatorul liniar spaţial-invariant 2D numit operator de convoluţie bidimensională discretă, caracterizat prin proprietatea:

h(j,k;m,n) = hm-j,n-k. (3.8)

Page 24: Manual ID Gpi

Grafică pentru calculator. Note de curs. Material în construcţie!Pentru lămuriri şi observaţii, a se contacta: [email protected]

Convoluţia bidimensională discretă se poate exprima în forma serie prin ecuaţia:

g h fm n m j n k j kk

N

j

M

, , ,

0

1

0

1

. (3.9)

Convoluţia bidimensională discretă poate fi interpretată ca o discretizare a unei convoluţii bidimensionale continue. Limitele de sumare din ecuaţia (3.9) cer câteva precizări, existând în literatură mai multe moduri echivalente de a defini convoluţia bidimensională discretă. Elementele operatorului de convoluţie pot fi aranjate în forma unei matrici, H cu elementul general hp,q. Denumită sugestiv şi mască de convoluţie, matricea operatorului de convoluţie nu trebuie confundată cu matricea operatorului liniar generalizat. Uzual, dimensiunile măştii operatorului de convoluţie sunt mult mai mici decât cele ale imaginii. Fără pierderea generalităţii, vom presupune o mască de formă pătrată, cu dimensiunile LL:

H

h h h

h h h

h h h

L

L

L L L L

0 0 0 1 0 1

1 0 1 1 1 1

1 0 1 1 1 1

, , ,

, , ,

, , ,

. (3.10)

Matricea H reprezintă răspunsul sistemului liniar la (o imagine) impuls unitar 2D, , având un pixel cu nivelul de luminanţă unitar în origine şi fiind nulă în restul domeniului real.

Cu aceste notaţii, putem acum preciza că, în ecuaţia (3.9), hp,q = 0 dacă: p < 0 sau q < 0 sau p > L-1 sau q > L-1. Asemănator convoluţiei imaginilor continuale, ecuaţia (3.9) se scrie concis:

G = FH. (3.11)

Convoluţia 2D are toate proprietăţile cunoscute ale operatorilor liniari discreţi 1D:

comutativitate asociativitate distributivitate în raport cu adunarea imaginilor

Interpretare grafică a procesului de convoluţie

Convoluţia reprezintă o operaţie locală, pentru că un element al imaginii de ieşire se obţine prin combinarea unor elemente ale imaginii de intrare localizate într-un subdomeniu al imaginii, de regulă de dimensiuni mici în comparaţie cu dimensiunile imaginii. Este util să dăm o interpretare grafică intuitivă procesului de convoluţie (Fig. 3.1.). Imaginea este explorată, de exemplu în ordine lexicografică, cu ajutorul măştii de convoluţie, rotită cu 180. Pentru fiecare pixel de ieşire, de

Page 25: Manual ID Gpi

Grafică pentru calculator. Note de curs. Material în construcţie!Pentru lămuriri şi observaţii, a se contacta: [email protected]

coordonate (m,n) se calculează suma ponderată a pixelilor din imaginea de intrare, aflaţi sub masca de convoluţie deplasată cu originea la coordonatele (m,n). Ponderea fiecărui pixel este specificată de coeficientul care i se suprapune din mască. Rotirea cu 180 a măştii este consecinţa (neesenţială a) semnului minus din ecuaţia de definiţie a convoluţiei, fiind introdus în definiţie pentru convenienţe teoretice.

Se observă că imaginea de ieşire are dimensiunile extinse cu L-1 elemente pe ambele direcţii. Nu toate elementele suplimentare sunt utile în general. Un exemplu clarifică mai uşor motivul.

Fig. 3.1. Geometria procesului de convoluţie

De exemplu, să presupunem că operatorul 33 din Fig. 3.1 este:

. (3.12)

h00h01h02

h10

h20h21h22

h11h12

h00h01h02

h10

h20h21h22

h11h12

h00h01h02

h10

h20h21h22

h11h12h00h01h02

h10

h20h21h22

h11h12

N+L-1

N

N-L+1

h00h01h02

h10

h20h21h22

h11h12

L-12

L-12

L-12 L-1

2H

G

F

Page 26: Manual ID Gpi

Grafică pentru calculator. Note de curs. Material în construcţie!Pentru lămuriri şi observaţii, a se contacta: [email protected]

Operatorul este denumit operator de mediere aritmetică sau filtru uniform în varianta cauzală (originea este marcată). Fiecare element al imaginii de ieşire este media aritmetică a pixelilor dintr-o regiune de 33 pixeli. Primul element din imaginea de ieşire este g0,0=(1/9)f0,0 şi provine din medierea pixelului f0,0 cu opt zerouri din fundal. Este, evident, un pixel afectat de eroare. Toţi pixelii de ieşire pentru care masca de convoluţie nu este integral suprapusă pe imaginea de intrare vor avea valori mai mici decât media aritmetică a 9 pixeli de intrare. În principiu, calculul acestor elemente ale imaginii de ieşire poate fi omis. Totuşi, din punct de vedere practic, este adesea inconvenabil să restrîngem imaginea de ieşire, G, la dimensiunile [N -(L-1)/2] [N -(L-1)/2]. Ar fi preferabil să păstrăm formatul de imagine, NN al imaginii de intrare, F. În acest caz, avem de rezolvat problema erorilor de margine reprezentate umbrit în Fig.4.1. Soluţia constă în extinderea imaginii de intrare prin continuitate (exemplu repetarea sau oglindirea liniilor sau coloanelor).

4. Transformări ale scării de gri Transformările scării de gri reprezintă una din cele mai simple şi mai

frecvent utilizate metode de prelucrare a imaginii. Din această categorie de prelucrări fac parte, de exemplu, tehnicile pentru modificarea iluminarii şi a contrastului sau cele pentru modificarea paletei cromatice.

4.1. Operatori punctuali spaţial variabili

Un operator punctual spaţial variabil este de forma:

unde f reprezintă imaginea de intrare şi g imaginea de ieşire. Se remarcă faptul că rezultatul prelucrării la coordonalele (x,y) depinde numai de valoarea imaginii de intrare la coordonatele respective (Fig. 4.1).

Fig. 4.1. Operatorul punctual

În cazul cel mai general, operatorul punctual defineşte o transformare neliniară şi este spaţial variabil, ceea ce înseamnă că transformarea se modifică în raport cu coordonatele spaţiale, (x,y).

Ox,y(fx,y

)

f g

gx,y = Ox,y(fx,y), (4.1)

Page 27: Manual ID Gpi

Grafică pentru calculator. Note de curs. Material în construcţie!Pentru lămuriri şi observaţii, a se contacta: [email protected]

Operatorul punctual spaţial variabil poate fi utilizat, de exemplu, pentru corecţia neuniformităţii spaţiale a sensibilităţii senzorului de imagine şi/sau a dispozitivului pentru redarea imaginii. De asemenea, pentru corecţia iluminării neuniforme a scenei captate. Un exemplu de operator spaţial variabil este cel multiplicativ:

În cazul corecţiei neuniformităţii de câmp a senzorului de imagine, operatorul necesar pentru corecţie, ox,y, poate fi identificat în următorul mod:Se captează imaginea unui ecran alb imaculat, iluminat uniform;Se memorează imaginea (neuniformă) obţinută, f;Se compară cu valoarea ideală constantă, t, obţinută prin calcul (în

absenţa unui model fizic precis, se poate utiliza media nivelurilor de gri pentru imaginea f).

Se defineşte operatorul de corecţie:

Observaţie: în ecuaţia (4.3), operatorul spaţial variabil, ox,y, poate fi interpretat şi ca o imagine În această idee, ecuaţia (4.3) defineşte o operaţie între două imagini: multiplicarea lor. Multiplicarea imaginilor face parte din categoria operatorilor diadici. Alte exemple de operatori diadici sunt suma imaginilor, substracţia imaginilor, operaţiile logice între imagini bitonale etc.

De reţinut faptul că “imaginea” operatorului folosind numere întregi este inadecvată. Întrebare: din ce motiv ?

4.2. Operatori punctuali spaţial invarianţi

O transformare a scării de gri poate fi descrisă cu ajutorul unui operator punctual spaţial invariant:

Transformarea definită de un asemenea operator nu se modifică în funcţie de poziţia pixelului prelucrat în imagine. În consecinţă, coordonatele spaţiale pot fi omise:

Vom analiza în continuare câteva cazuri particulare mai frecvent utilizate ale operaţiei descrise de ecuaţia (4.5).

gx,y = ox,yfx,y. (4.2)

ox,y = t/fx,y. (4.3)

gx,y = O(fx,y). (4.4)

g = O(f). (4.5)

Page 28: Manual ID Gpi

Grafică pentru calculator. Note de curs. Material în construcţie!Pentru lămuriri şi observaţii, a se contacta: [email protected]

4.2.1. Modificarea liniară a luminanţei şi a contrastuluiModificarea luminanţei sau a contrastului pot fi necesare în situaţii diverse. De exemplu, creşterea contrastului poate fi necesară la imagini achiziţionate în condiţii de iluminare precare sau cu un reglaj al camerei necorespunzător. Prelucrarea liniară a luminanţei şi contrastului se poate exprima în forma:

În ecuaţia de mai sus, c este coeficientul de multiplicare a contrastului, iar l parametrul aditiv pentru modificarea luminanţei. În planul f-g, ecuaţia reprezintă o dreaptă (Fig. 4.2). Pentru creşterea contrastului, este necesar să se utilizeze un coeficient c >1.

Fig. 4.2. Transformare pentru modificarea contrastului

Exemplu de implementare a transformării pentru modificarea contrastuluiO posibilă implementare C a transformării este prezentată în continuare.

#define BYTE unsigned char#define lim(x) (x<0?0:x>255?255:x)void contrast(BYTE * ptin, // pointer la imaginea de intrare

BYTE * ptout, // pointer la imaginea de ieşire int linii,

int coloane, float C, // coeficient contrast

int L // luminanţă ) {long pixeli =(long) linii*coloane;while( pixeli-->0 ) ptout++ = lim(C*(*ptin++)+L);}

g

f

l

g = cf+l (4.6)

Page 29: Manual ID Gpi

Grafică pentru calculator. Note de curs. Material în construcţie!Pentru lămuriri şi observaţii, a se contacta: [email protected]

Se presupune că imaginea supusă prelucrării este stocată cu începere de la locaţia de memorie indicată de pointerul ptin şi că imaginea ce rezultă se stochează începând cu locaţia indicată de pointerul ptout. De asemenea, se presupune că au fost realizate în prealabil alocările de memorie necesare. În afara celor doi pointeri menţionaţi, funcţia de prelucrare a contrasului şi luminanţei primeşte ca parametri numărul de linii şi de coloane, precum şi c şi l din ecuaţia (4.6). De remarcat prezenţa macroinstrucţiunii lim()în linia de program din interiorul buclei while. Cu ajutorul ei, rezultatele prelucrării care depăşesc gama valorilor de gri [0-255] sunt limitate la valorile extreme ale intervalului. În situaţiile în care intervine limitarea, prelucrarea încetează de fapt a mai fi una liniară.

Bucla principală conţine o singură linie de program. Cu toate acestea, programul nu este optimizat din punctul de vedere al vitezei de execuţie. În general, complexitatea prelucrării nu are prea multă legătură cu lungimea codului de program. O soluţie mai rapidă, bazată pe tabele convertoare de cod (memorii LUT – “look-up table”), care poate fi aplicată şi pentru prelucrarea liniară a luminanţei şi contrastului, se prezintă într-un exemplu ulterior.

4.2.2. Transformări liniare pe porţiuni a scării de griO transformare a scării de gri cu trei porţiuni liniare este ilustrată în Fig.4.3, fiind descrisă de ecuaţia:

Fig. 4.3. Transformare pentru modificarea selectivă a contrastului

Transformarea permite accentuarea sau atenuarea independentă a contrastului pentru trei domenii de valori ale intrării, corespunzătoare regiunilor cu iluminare redusă, medie şi ridicată. Coeficienţii de contrast ai fiecărui domeniu sunt mi =g / f = tgi. Contrastul este amplificat dacă panta este supraunitără.

fl fh fma

x

fgl

gh

gmax

g

(4.7)

Page 30: Manual ID Gpi

Grafică pentru calculator. Note de curs. Material în construcţie!Pentru lămuriri şi observaţii, a se contacta: [email protected]

4.2.3. Fereastra de griUn caz particular frecvent întîlnit îl constituie fereastra de gri (Fig. 4.4), definită prin ecuaţia:

Fig.4.4. Fereastră de gri

Parametrii B (de la “base line”) şi W (de la “window”) sunt reglabili, pentru a se putea explora cu fereastra activă întreg domeniul de variaţie a nivelului de gri. Intervalul de gri cuprins în fereastra de lăţime reglabilă W este expandat pe întreaga gamă de contrast disponibilă sau în general la un alt interval de intensităţi dorit. Uzual gmin = 0 şi gmax= 255. Cu ajutorul prelucrării de tip fereastră de gri, este posibilă evidenţierea unor regiuni ale imaginii ce se detaşează de fundal cu diferenţe de intensitate imperceptibile sau abia perceptibile. Imaginile scintigrafice sau tomografice prezintă o gamă dinamică de 8 până la 12 biţi, corespunzând unui număr de 256 pînă la 4096 niveluri de gri în timp ce, în condiţiile contrastului limitat, pe ecranul unui monitor distingem bine în jur de 20-25 de niveluri de gri. Un exemplu de utilizare a prelucrării de tip fereastră de gri este ilustrat în Fig. 4.5. Vizibilitatea tumorii după aplicarea transformării cu B = 110 şi W = 10 este net ameliorată. Alte detalii neinteresante se pierd.

g

gmax

gmin

B B+W

fmax

f

(4.8)

Page 31: Manual ID Gpi

Grafică pentru calculator. Note de curs. Material în construcţie!Pentru lămuriri şi observaţii, a se contacta: [email protected]

Fig. 4.5. a) -sus: imaginea neprelucrată şi histograma ei; b) -jos: imaginea prelucrată cu fereastra de gri (B = 110, W = 10) şi

histograma ei.

Orice operator punctual spaţial invariant se poate implementa eficient cu ajutorul unui tabel de memorie de tip LUT (“look-up table”). O implementare naivă a transformării (4.4) sau (4.5) pentru o imagine 512512 presupune evaluarea expresiei în cauză de 262144 ori. Presupunând o imagine monocromã pe 8 biţi, este mai eficient sã evaluăm expresia (4.4) sau (4.5) pentru toate cele 256 de valori posibile ale intrării f, valorile obţinute fiind memorate într-un tabel cu 256 elemente, tab[256]. După calculul tabelului, transformarea se efectuează prin citirea tabelului de 262144 ori, operaţie mult mai rapidă decât calculul. Redăm codul C++ al unei funcţii ce calculează fereastra de gri definită prin (4.8) folosind o tehnică de tabelare.

#define BYTE unsigned char

void feGri(BYTE * ptin, // pointer la imaginea de intrare BYTE * ptout, // pointer la imaginea de ieşire int linii,

int coloane, int B, // nivel de bază

int W // lăţime fereastră ){long pixeli =(long) linii*coloane;

Page 32: Manual ID Gpi

Grafică pentru calculator. Note de curs. Material în construcţie!Pentru lămuriri şi observaţii, a se contacta: [email protected]

BYTE tab[256];int i;

// generare tabelint UP = B + W < 256 ? B + W : 255;for( i = 0; i < B; i++ ) tab[i]=0; for( i = UP; i < 256; i++ ) tab[i]=255;if(W) for( i = B; i < UP; i++ ) tab[i] = ( BYTE ) ( (i-B)*255) / W ); // transformarea propriu zisăwhile( pixeli-->0 ) *ptout ++ = tab[*ptin ++];}

4.2.4. Binarizarea imaginilorUn caz particular de interes larg al ferestrei de gri este fereastra cu W = 0. Transformarea este exprimabilă în forma:

Uzual gmax = 1 şi gmin = 0, astfel că imaginea rezultată se poate memora pe un singur bit. O asemenea imagine este denumită imagine binară. Ecuaţia (4.9) reprezintă o formă simplă de detecţie de prag, utilă în segmentarea imaginilor.

Un exemplu de binarizare a imaginii este dat în Fig. 4.6. Pentru convenienţe legate de afişare, regiunea luminoasă a fost redată cu nivelul de gri 128, iar fundalul a fost stabilit mai luminos. Pragul th a fost stabilit automat printr-un algoritm de segmentare adecvat.

Fig.4.6. Binarizarea imaginii

4.2.5. Inversarea contrastului (negativarea)Transformarea este definită cu ajutorul ecuaţiei:

(4.9)

g

fth

g = Lmax f, (4.10)

Page 33: Manual ID Gpi

Grafică pentru calculator. Note de curs. Material în construcţie!Pentru lămuriri şi observaţii, a se contacta: [email protected]

unde Lmax este nivelul maxim posibil la intrare (255 pentru o imagine pe 8 biţi). Un exemplu de negativare a imaginii este redat în Fig. 4.7.

Fig. 4.7. Negativarea imaginii.

4.2.6. Corecţia scării de griModificarea scării de gri poate fi utilă pentru corecţia neliniarităţii procesului de achiziţie sau de formare a imaginii. De exemplu, procesul fotografic este neliniar şi conduce la o logaritmare a intensităţii. Absorbţia radiaţiei în imagini radiologice depinde tot aproximativ logaritmic de densitatea ţesuturilor. La răndul său, senzorul de imagine (vidicon, tub CCD etc.) nu are un răspuns liniar. Neliniaritatea răspunsului este adesea aproximată printr-o lege exponenţială de forma

, compensarea necesară fiind denumită corecţie gamma. Nici tubul cinescopic folosit pentru redarea imaginilor nu produce o strălucire strict proporţională cu amplitudinea semnalului video aplicat. Efectul combinat al unor neliniarităţi de acest tip poate fi corectat cu ajutorul unei singure transformări de tipul celei definite prin ecuaţia (4.5). Observaţie: Datorită cuantizării imaginii de intrare, corecţia nu este perfectă, chiar dacă dispunem de un model perfect al neliniarităţii şi redăm ieşirea pe un număr de biţi oricât de mare. 4.2.7. Normalizarea contrastuluiO altă prelucrare de tip fereastră folosită curent urmăreşte aducerea imaginilor la contrastul maxim. Fie fmax şi fmin intensităţile maximă şi minimă în imaginea de intrare şi Lmax şi Lmin nivelurile de intensitate maxim şi minim dorite la ieşire. Transformarea corespunde ferestrei de gri (3.8) cu B = fmin , W = fmax fmin , gmax = Lmax şi gmin = Lmin. Uzual Lmax

= 255 şi Lmin = 0. O asemenea transformare este denumită extindere a

g

f

Lmax

Lmax

Page 34: Manual ID Gpi

Grafică pentru calculator. Note de curs. Material în construcţie!Pentru lămuriri şi observaţii, a se contacta: [email protected]

contrastului (“contrast stretching”). Extinderea se face uneori cu tăiere (“clipping”). În acest caz, B şi W se aleg astfel încât un anumit procent minim (tipic 5%) din pixelii cei mai întunecaţi şi din cei mai luminoşi să fie redaţi la fel (cu gmin, respectiv cu gmax). Prin acest procedeu se poate evita efectul advers al unui număr mic de pixeli “extremişti” capabili, în anumite situaţii, de a diminua drastic extinderea scării.

Exemplu Să presupunem că avem imagini redate pe 12 niveluri de gri şi dorim să normalizăm fără tăiere mini-imaginea cu histograma:

.

Datorită unui singur pixel cu nivel 0 şi a unui singur pixel cu nivel 11, normalizarea nu va modifica nimic, deşi era mult mai utilă transformarea cu B = 3 şi W = 4.

4.2.8. Transformări de modificare a histogrameiCu excepţia negativării imaginii, transformările scării de gri prezentate până acum presupun specificarea de către utilizator a unuia sau mai multor parametri, respectiv interactivitate. Folosind informaţii de natură statistică despre imagine, se pot defini prelucrări ale scării de gri ce nu necesită intervenţia operatorului uman. Astfel, histograma nivelurilor de gri permite extragerea unei categorii largi de parametri ai imaginii, de tipul intensităţii maxime şi minime, a contrastului, luminanţei medii etc. Prezentăm în continuare câteva posibilităţi de transformare a scării de gri ce pot fi definite pe baza histogramei.

Tehnicile de modificare a histogramei sunt transformări ale scării de gri ce aduc histograma la o formă dorită. Motivele pentru care o asemenea transformare poate fi dorită sunt diverse şi dependente de aplicaţie. Pentru edificare, vom considera cazul mai frecvent al egalizării histogramei. Imaginea neprelucrată din Fig. 4.5a are o histogramă puternic neuniformă. Structuri de interes medical sunt concentrate pe o gamă dinamică redusă şi nu pot fi distinse, în timp ce numeroase niveluri de gri sunt practic nefolosite sau foarte rar folosite. În Fig. 4.8, este redat rezultatul transformării scării de gri cu egalizarea histogramei.

Fig. 4.8. Imaginea din Fig. 4.5a cu histograma egalizată

Remarcăm că: imaginea permite observarea unui număr mai mare de entităţi,

Page 35: Manual ID Gpi

Grafică pentru calculator. Note de curs. Material în construcţie!Pentru lămuriri şi observaţii, a se contacta: [email protected]

imaginea conţine numai 16 niveluri de gri, histograma este mai uniformă, dar nu perfect uniformă.Ultimele observaţii sunt legate de faptul că imaginea supusă transformării este digitizată. Imaginile cu histograme mai uniforme utilizează mai armonios nivelurile de gri disponibile, fiind adesea mai utile pentru analiza imaginii decât imaginea originală.

Pentru imagini digitizate, există un algoritm de egalizare simplu, pe care îl prezentăm în continuare. Metoda presupune ca imaginea transformată să fie reprezentată pe un număr de niveluri mai mic decât imaginea supusă transformării. Se obţine o imagine cu histogramă ce aproximează orice formă se doreşte. Egalizarea histogramei este un caz particular al acestei transformări.

Algoritm de modificare a histogramei Notăm cu h(n) coloanele histogramei de intrare, n = 0,1,..., L1 şi cu hd(n) pe cele ale histogramei dorite, n = 0,1,...,Q1. Definim histogramele cumulative ale imaginii de intrare şi ale imaginii dorite prin ecuaţiile:

De remarcat, faptul că dacă se folosesc histograme normalizate, histograma cumulativă c(k) semnifică probabilitatea ca nivelul de gri să fie mai mic sau egal cu k.

Consemnăm, de asemenea, că pentru implementare, este avantajos un calcul recursiv al histogramei cumulative:

Presupunem aceste histograme cumulative calculate. Algoritmul se derulează în următorii paşi:

1. Se caută un număr întreg, k1, astfel încât: c k c c kd( ) ( ) ( )1 10 1 .Toate nivelurile de gri fk cu 0 < k < k1 se transformă în nivelul

de ieşire g0.

2. Se caută un număr întreg, k2 > k1, astfel încât: c k c c kd( ) ( ) ( )2 21 1 .Toate nivelurile de gri fk cu k1 < k < k2 se transformă în nivelul

de ieşire g1.

c k h nn

k

( ) ( )

0(4.11)

c k h nd dn

k

( ) ( )

0(4.12)

(4.13)

Page 36: Manual ID Gpi

Grafică pentru calculator. Note de curs. Material în construcţie!Pentru lămuriri şi observaţii, a se contacta: [email protected]

3. Se continuă ca la pasul 2, până la epuizarea nivelurilor de gri de la intrare. Nu rămân niveluri nedistribuite, pentru că c(L-1) = cd(Q-1) = număr de pixeli în imagine.

Exemplu

Fie imaginea:1 0 1 2 2

1 1 2 2 3

1 2 3 4 3

6 7 7 7 8

7 6 7 7 9

Histograma imaginii este:

h 1 5 5 3 1 0 2 6 1 1 .

Imaginea transformată pentru egalizarea histogramei cu 5 niveluri de ieşire are histograma dorită

hd 5 5 5 5 5 .

Transformarea obţinută este definită prin tabelul de mai jos:

Histograma imaginii transformate prin algoritmul de egalizare este:

hr 1 5 8 3 8

Este indicată o renormalizare a scării, pentru a se compensa reducerea numărului de niveluri. Transformarea este

g’ = 2g.

Imaginea finală este:

2 0 2 4 4

2 2 4 4 4

2 4 4 6 4

6 8 8 8 8

8 6 8 8 8

.

4.2.9. Transformarea pseudocolorO generalizare a transformărilor scării de gri prezentate până acum este transformarea pseudocolor:

c=O{f}, (4.14)

Page 37: Manual ID Gpi

Grafică pentru calculator. Note de curs. Material în construcţie!Pentru lămuriri şi observaţii, a se contacta: [email protected]

prin care fiecare nivel de gri, f, este transformat într-o culoare,

Transformarea exploatează capacitatea sistemului vizual uman de a distinge simultan într-o imagine un număr mult mai mare de nuanţe de culori decât niveluri de gri. Transformarea poate fi utilă, de exemplu, în analiza imaginilor “termice” folosite la detecţia defecţiunilor în circuite integrate sau a pierderilor de căldură la clădiri. Pe de altã parte, colorarea regiunilor rezultate în urma unui proces de segmentare a imaginii poate fi convenabilă pentru analiza vizuală a rezultatelor. Alegerea unei corespondenţe intuitive în raport cu specificul aplicaţiei este problema ce trebuie soluţionată prin stabilirea paletei cromatice şi a legii de transformare. Menţionăm că procesul de colorare a filmelor alb/negru vechi este mai complicat, legea de transformare nefiind unic definită nici măcar la un cadru de imagine singular. Metodele de prelucrare numerică interactive pot facilita însă enorm sarcina prin procedee de segmentare şi estimare a mişcării, ce permit propagarea rezultatelor valide de la un cadru la altul.

4.2.10. Prelucrarea culorilor Mai generală decât transformarea pseudocolor este transformarea de modificare a culorilor, numită adesea culori false:

sau mai explicit,

Transformarea modifică orice culoare într-o altă culoare, conform legii de transformare selectate. Scopul poate fi corecţia procesului fotografic, obţinerea unor efecte artistice în cinematografie etc. În primul caz, culorile după transformare sunt mai apropiate de cele reale. În cel de-al doilea, dimpotrivă, culorile sunt modificate pentru a se accentua anumite aspecte ale mesajului vizual, uneori chiar pentru a şoca.

.(4.15)

c’ = O{c}, (4.16)

(4.17)

Page 38: Manual ID Gpi

Grafică pentru calculator. Note de curs. Material în construcţie!Pentru lămuriri şi observaţii, a se contacta: [email protected]

Modificarea contrastului unei imagini color se poate obţine cu o prelucrare de forma:

unde k este un coeficient ce ia valori supraunitare pentru creşterea contrastului şi subunitare în cazul contrar.

5.1. Definiţii Transformările geometrice au aplicaţii numeroase în analiza

imaginilor şi în compresie. Ele permit, de exemplu, corecţia unor distorsiuni geometrice produse la captarea imaginii, modelarea schimbării parametrilor de poziţie, orientare şi transfocare a camerei, estimarea mişcării sau modelarea transformării imaginii.

O transformare geometrică proiectează fiecare pixel, de coordonate (x, y), al imaginii de intrare la o nouă poziţie, (x’, y’). Transformarea poate fi descrisă prin ecuaţiile:

Transformările Tx ,Ty pot fi cunoscute dinainte sau pot fi estimate pe baza imaginii iniţiale şi a celei transformate.

5.2. Transformări geometrice 2D uzuale

Transformarea geometrică generală este aproximată frecvent cu ajutorul unor ecuaţii polinomiale. Cîteva transformări particulare de interes mai larg sunt prezentate în continuare.

5.2.1. Transformările afineEcuaţiile de transformare sunt:

Transformările afine includ: Translaţia

rotaţia în planul imaginii, cu unghiul faţă de origine

,(4.18)

x’ = Tx(x, y), (5.1)y’ = Ty(x, y). (5.2)

x’ = a0 + a1x + a2 y, (5.3)y’ = b0 + b1x + b2 y. (5.4)

x’ = a0 + x, (5.5)y’ = b0 + y. (5.6)

x’ = xcos + ysin, (5.7)y’ = -xsin + ycos. (5.8)

Page 39: Manual ID Gpi

Grafică pentru calculator. Note de curs. Material în construcţie!Pentru lămuriri şi observaţii, a se contacta: [email protected]

rescalarea cu factor diferit pe cele două direcţii

înclinare cu unghiul

Transformările de perspectivăEcuaţiile transformărilor de perspectivă sunt:

Transformările de perspectivă, şi transformările afine corespund proecţiilor de perspectivă, respectiv ortografice ale unui corp solid tridimensional şi nedeformabil ce se poate mişca arbitrar.

5.2.2. Interpolarea luminanţeiImplementarea unei transformări geometrice particulare

presupune inversarea ecuaţiilor (5.1), (5.2). Aplicaţia este privită din perspectiva imaginii de ieşire. Pentru fiecare punct, de coordonate (x’, y’) al acestei imagini, se caută coordonatele (x, y) ale pixelului din imaginea de intrare ce l-a generat. Practic, trebuie să atribuim la ieşire intensitatea:

Problema este că valorile (x, y) obţinute în urma calculelor nu sunt în general numere întregi, în timp ce imaginea fx, y este definită numai pentru un număr finit de puncte (Fig. 5.1), corespunzând unor valori întregi ale coordonatelor (x, y). Soluţia pentru estimarea intensităţii în punctele nesituate pe grila de eşantionare a imaginii de intrare o constituie interpolarea.

Punct căutat, cu intensitatea

nedefinită

x’ = ax, (5.9)y’ = by. (5.10)

x’ = x + ytg, (5.11)y’ = y. (5.12)

xa x a y a

a x a y'

1 2 3

7 8 1,

(5.13)

ya x a y a

a x a y'

4 5 6

7 8 1.

(5.14)

gx’, y’ = fx, y. (5.15)

Page 40: Manual ID Gpi

Grafică pentru calculator. Note de curs. Material în construcţie!Pentru lămuriri şi observaţii, a se contacta: [email protected]

Fig. 5. 1. Problema interpolării imaginii

Fie m, n coordonate întregi, pentru care imaginea de intrare, fm,n , este definită. Imaginea interpolată pentru o pereche de coordonate (x, y) arbitrară este

Recunoaştem în ecuaţia de mai sus o sumă de convoluţie bidimensională aproape obişnuită.

Observaţii: Suma poate fi evaluată pentru coordonate (x, y) continuale,

numărul lor fiind nelimitat. Nucleul operatorului, h, este o funcţie de coordonatele

continue x şi y. În practică, fereastra operatorului de interpolare, h, are

dimensiuni ce nu depăşesc trei-şapte pixeli.

Interpolarea de ordinul zeroCea mai simplă soluţie la problema expusă este interpolarea de ordinul zero, numită sugestiv şi metoda de interpolare a vecinului celui mai apropiat, conform căreia, pixelului căutat i se atribuie intensitatea celui mai apropiat pixel din grila de eşantionare. Formal, metoda poate fi descrisă cu ajutorul sumei de convoluţie (5.16), cu hx,y definit ca:

Pentru calcule este convenabilă exprimarea interpolării de ordin zero cu ajutorul operaţiei de rotunjire. Notând cu x partea întreagă a lui x, interpolarea de ordinul zero se reduce la:

În Fig. 5.2, este ilustrată interpolarea de ordinul zero a unui semnal unidimensional.

h0 X

x-0,5 0,5

1

(5.16)

hx,y = rect(x,y) = rect(x) rect(y). (5.17)

fx,y = fx+0,5,y+0,5. (5.18)

Page 41: Manual ID Gpi

Grafică pentru calculator. Note de curs. Material în construcţie!Pentru lămuriri şi observaţii, a se contacta: [email protected]

Fig. 5. 2. Interpolare de ordinul zero a unui semnal 1D.

nterpolarea de ordinul zero produce rezultate modeste în special la mărirea imaginilor (zoom), prin faptul că imaginea interpolată conţine arii de intensitate constantă de dimensiunea pixelului în imaginea iniţială. Un aspect pozitiv este acela că tranziţiile abrupte se păstrează.

Interpolarea de ordinul unu sau liniarăNucleul de interpolare liniară se poate obţine prin convoluţia

nucleului de interpolare de ordinul zero cu el însuşi. Fig. 5.3 prezintă un exemplu de interpolare liniară pentru semnalul unidimensional din Fig. 5.2. La semnale bidimensionale, h1xy = h1x h1y. Notând cu şi partea fracţionară a coordonatelor x şi y,

interpolarea liniară bidimensională, numită şi interpolare biliniară, se poate scrie:

Fig. 5. 3. Interpolare liniară 1D.

h1 X

x-1 1

1h1 X = h0 X h0 X

= x - x , (5.19)

= y - y. (5.20)

fx,y = (1-)(1-)fx,y + (1-)fx +1,y + (1-)fx,y +1 + fx +1,y +1.

(5.21)

Page 42: Manual ID Gpi

Grafică pentru calculator. Note de curs. Material în construcţie!Pentru lămuriri şi observaţii, a se contacta: [email protected]

Procedura de interpolare liniară 2D (biliniară) este ilustrată în Fig. 5.12. Interpretarea grafică se bazează pe faptul că interpolarea liniară 2D se poate obţine prin interpolări 1D succesive pe direcţiile axelor

Fig. 5.4. Interpretare grafică a interpolării liniare 2D

de coordonate. De exemplu, putem proceda în ordinea:

f 1 = (1-)fx,y + fx +1,y ,f 2 = (1-)fx,y +1 + fx +1 ,y +1,f x, y = (1-) f 1 + f 2.

Un pixel interpolat rezultă prin medierea ponderată a celor patru pixeli vecini situaţi pe grila de eşantionare a imaginii de intrare. Prin procesul de mediere se obţine o imagine mai netedă (vezi şi Fig. 5.5). Efectul este benefic în regiunile omogene ale imaginii, dar i se poate reproşa faptul că prin mediere contururile obiectelor se estompează. Pentru comparaţie, în Fig. 5.5 este redat un detaliu din rezultatul prelucrării de tip lupă ( “zoom”) cu interpolare de ordin zero şi de ordin unu, la imaginea “Lena”.

Fig. 5.5. Efect de mărire (“zoom”) prin interpolare de ordin zero (stânga) şi liniară (dreapta)

fx ,y +1

fx +1,y

1-

fx,y

fx ,y

fx +1,y +1

1-

f1

f2

Page 43: Manual ID Gpi

Grafică pentru calculator. Note de curs. Material în construcţie!Pentru lămuriri şi observaţii, a se contacta: [email protected]

Exemplul 5.2.1

Se dă imaginea: 1 6 8

2 3 9

5 4 7 .

Se măreşte imaginea pentru a fi redată în formatul 55. Se utilizează interpolare de ordinul unu. Se cere intensitatea la coordonatele (2,3).Rezolvare:Transformarea geometrică este:

x’ = 5x/3,y’ = 5y/3.

Prin inversarea ecuaţiilor transformării, obţinem:x = 3x’/5,y = 3y’/5.

Pentru (x’, y’) = (2, 3), obţinem:x = 1.2y = 1.8.

La interpolarea imaginii fx,y = f1.2, 1.8 , folosim eşantioanele 3 9

4 7:

fx,y = f1,1 = 3, fx +1,y = f2,1 = 9, fx,y +1 = f1,2 = 4, fx +1,y +1 = f2,2 = 7.Avem = 0.2, = 0.8. Folosind ecuaţia (5.38), obţinem:

f1.2, 1.8 = (1-0.2)(1-0.8)3 + 0.2(1-0.8)9 + (1-0.2)0.84 + 0.20.87 = 4.52.În final, g3,3 = f1.2, 1.8 = 4.52. În aproximarea cu numere întregi, g3,3 5.

Interpolare bicubicăNuclee de interpolare de ordin superior se pot obţine prin

convoluţia repetată a nucleului de ordinul zero (fereastra rectangulară). Pe măsură ce ordinul de interpolare creşte, forma lui hx,y tinde spre o funcţie gaussiană. Totodată dimensiunile ferestrei de interpolare cresc şi efectul de netezire mai accentuat. Pentru a se obţine imagini interpolate cu contururi mai puţin estompate, se pot folosi operatori ce combină netezirea cu derivarea. Un asemenea operator de interpolare, ce foloseşte o regiune de 1616 pixeli este operatorul bicubic [Sonka 1995] cu

Alternativ, imaginea interpolată liniar poate fi postprocesată cu un filtru de tip trece-sus. Metode de interpolare neliniare, de tip morfologic, pot fi, de asemenea avute în vedere.

(5.22)

Page 44: Manual ID Gpi

Grafică pentru calculator. Note de curs. Material în construcţie!Pentru lămuriri şi observaţii, a se contacta: [email protected]

6. FILTRE

6.1. Obiectivele filtrării imaginilor Prin filtrarea imaginilor, se urmăreşte eliminarea selectivă a

informaţiei ce nu prezintă interes din punctul de vedere al obiectivelor analizei imaginii, concomitent cu păstrarea informaţiei utile. Informaţia ce se doreşte a fi eliminată este denumită “zgomot”, datorită probabil celei mai vechi probleme de filtrare abordate în electronică : reducerea zgomotului produs de amplificatoare. Un exemplu de imagine afectată de zgomot şi filtrată este prezentat în Fig. 6.1.

Fig. 6.1.Exemplu de filtrare pentru atenuarea zgomotului

Abordarea tradiţională a problemei filtrării prin sisteme liniare, spaţial invariante, are la bază descompunerea (reală sau ipotetică) a semnalului supus filtrării în componente de frecvenţă. Proiectarea filtrului se concentrează, în această abordare, pe realizarea atenuării şi eventual defazării dorite pentru fiecare componentă spectrală. De aici şi denumirile consacrate : filtru trece-sus, trece-jos, trece-bandă, opreşte bandă etc. Datorită faptului că toate celelalte tipuri de filtru pot fi sintetizate pornind de la un filtru trece-jos, acest tip de filtru ocupă cel mai însemnat loc în lucrările dedicate filtrelor liniare. Capitolul prezent urmează aceeaşi tendinţă, prin concentrarea pe filtre de netezire. Termenul de netezire a imaginilor este nu numai mai sugestiv decât cel de filtru trece jos pentru imagini, ci şi mai general, fiind adecvat şi pentru filtrele neliniare care sunt robuste şi la care ne referim în principal. Pentru o perspectivă mai largă, este inclusă şi o scurtă prezentare a tehnicilor de netezire liniare.

Succesul oricărei operaţii de prelucrare a imaginii sau, mai general, al oricărui proiect ingineresc, depinde în primul rând de măsura în care cerinţele reale ale utilizatorului sunt incorporate în modelarea matematică a problemei. Evoluţia tehnicilor de netezire a imaginilor reflectă această realitate, prin tendinţa de modelare din ce în ce mai exactă a cerinţelor. În netezirea imaginilor, o cerinţă importantă o reprezintă păstrarea contururilor.

Page 45: Manual ID Gpi

Grafică pentru calculator. Note de curs. Material în construcţie!Pentru lămuriri şi observaţii, a se contacta: [email protected]

6.2. Operatori de netezire liniari Operatorii de netezire liniari pot fi consideraţi operatori de

filtrare de tip trece-jos. Efectul lor asupra spectrului Fourier constă în atenuarea componentelor de înaltă frecvenţă. Proiectarea filtrelor de netezire a imaginilor se concentrează cel mai frecvent pe domeniul spaţial şi nu cel de frecvenţă, datorită dificultăţii de a găsi formularea precisă a răspunsului în frecvenţă dorit. De exemplu, un filtru trece-jos cu a anumită bandă de trecere, produce numeroase oscilaţii la apariţia unui semnal de tip treaptă, un efect cât se poate de indezirabil.

6.2.1. Medierea aritmetică. Filtrul uniformMedierea aritmetică este una din cele mai simple metode de eliminare a zgomotului, utilizată cu succes şi în tehnica măsurării. Să presupunem că se captează o imagine statică f, afectată aditiv de zgomotul n. Putem presupune că zgomotul este alb şi are dispersia 2. Mai presupunem că se captează N cadre de imagine. Prin medierea aritmetică a imaginilor captate, obţinem:

g f n f n 1 1 1

1 1 1N N Nk kk

N

kk

N

kk

N

( ) . (6.1)

Pentru că imaginile captate, fk sunt statice, ele sunt toate identice şi egale cu imaginea ideală, f. În consecinţă,

g f + n1

1N kk

N

. (6.2)

Zgomotul în imaginea mediată este

z n1

1N kk

N

. (6.3)

Matricea de covarianţă a zgomotului la ieşire este:

(6.4)

Se observă că zgomotul rămâne alb şi dispersia scade de N ori, respectiv abaterea standard de N ori. Acest gen de mediere aritmetică temporală este mijloc de eliminare a zgomotului deosebit de eficient. Teoretic N poate fi oricât de mare. Practic, N este limitat numai prin faptul că imaginea poate să nu rămână statică un timp nelimitat.

De cele mai multe ori, dispunem de un singur cadru de imagine, astfel că procedura de eliminare a zgomotului prin mediere în timp, nu

Page 46: Manual ID Gpi

Grafică pentru calculator. Note de curs. Material în construcţie!Pentru lămuriri şi observaţii, a se contacta: [email protected]

este realizabilă. În locul ei, putem folosi medierea spaţială prin convoluţia cu filtrul uniform de dimensiuni LL:

h

1

1 1 1

1 1 1

1

1 1 1

2L

.

(6.5)

Presupunând că zgomotul este alb, şi acest filtru reduce abaterea standard a zgomotului de L ori.

Filtrul uniform posedă o proprietate de optimalitate, în sensul că, media aritmetică furnizează o estimare de eroare pătratică minimă a intensităţii dintr-o fereastră cu un nivel constant. Într-adevăr, fie fk elementele imaginii cuprinse într-o fereastră oarecare, conţinând N pixeli. Se caută un estimator, g, astfel încât eroarea

(6.6)

să fie minimă. Punând condiţia:

2

0( )

,g

g (6.7)

obţinem după calcule simple soluţia:

. (6.8)

Este de aşteptat, prin urmare, ca filtrul uniform să funcţioneze excelent în regiunile uniforme, în care ipotezele ce au condus la optimalitatea soluţiei de mediere aritmetică sunt întrunite. Pentru utilizarea adecvată a filtrului uniform, aceste ipoteze, sau, echivalent, modelul optimizat trebuiesc conştientizate.

Cu totul alta este funcţionarea filtrului în regiunile neuniforme, de tipul muchiilor. În Fig. 2 este redată o muchie ideală de tip treaptă 1D şi rezultatul medierii aritmetice cu un filtru uniform de lungime L. Filtrul produce o degradare a conturului ce se manifestă vizual prin estomparea tranziţiilor din zonele de contur, echivalând cu pierderea clarităţii imaginii. Rezultatul ar trebui să nu surprindă, pentru că în vecinătatea muchiei, modelul de imagine constantă este invalidat.

Page 47: Manual ID Gpi

Grafică pentru calculator. Note de curs. Material în construcţie!Pentru lămuriri şi observaţii, a se contacta: [email protected]

Fig 6.2. Efectul unui filtru uniform de lungime L asupra unei muchii treaptă 1D.

Rezultatele filtrului cu mediere aritmetică cu fereastră de 5×5 asupra unei imagini este ilustrat în figura 6.3. Dimensiunea ferestrei influenţează decisiv proprietăţile filtrului uniform. Creşterea ei conduce la eliminarea mai drastică a zgomotului, prin reducerea abaterii standard proproţional cu radicalul numărului elementelor din fereastră. În acelaşi timp, efectul advers al filtrului asupra muchiilor se agravează, alegerea dimensiunii ferestrei fiind bazată pe un compromis între gradul de suprimare a zgomotului şi pierderea clarităţii contururilor.

Modelul de imagine constantă în fereastră care a condus la filtrul cu mediere aritmetică ignoră complet caracterul zgomotului ce se presupune a fi eliminat. Să presupunem că zgomotul este aditiv, independent si identic distribuit în fereastra de filtrare şi că distribuţia este una de tip Gaussian, cu medie nulă şi dispersie necunoscută. Deoarece semnalul imagine este presupus constant, în fereastră, acesta poate fi modelat ca având o distribuţie Gaussiană, cu media nenulă şi necunoscută, , egală cu nivgelul semnalului şi cu dispersie nenulă, egală cu a zgomotului şi de asemenea, necunoscută. Neglijând efectele cuantizării în imaginea digitală, putem exprima densitatea de probabilitate a imaginii f prin:

muchie idealã

rezultat medierearitmeticã

L

Page 48: Manual ID Gpi

Grafică pentru calculator. Note de curs. Material în construcţie!Pentru lămuriri şi observaţii, a se contacta: [email protected]

Fig. 6.3. Rezultatele filtrului de mediere aritmetică cu mască de 5×5 pixeli

(6.9)

Probabilitatea de a observa mulţimea eşantioanelor {fk , k=1,2,…,N} în fereastră devine (folosind independenţa distribuţiilor),

(6.10)

Prin logaritmarea exprsiei, devine evident că această probabilitate este maximizată pentru

Page 49: Manual ID Gpi

Grafică pentru calculator. Note de curs. Material în construcţie!Pentru lămuriri şi observaţii, a se contacta: [email protected]

, (6.11)

adică pentru constanta egală cu media aritmetică a eşantioanelor.

6.2.2. Medierea ponderată. Filtre binomialeDacă privim filtrul de netezire ca o modalitate de a estima

valoarea corectă a nivelului de gri la locaţia situată în centrul măştii, este firesc să punem în discuţie faptul că, la filtrul uniform, toţi pixelii din fereastră contribuie egal la rezultatul estimării. Intuitiv, pixelii aflaţi la distanţă mai mare de centrul măştii au şanse mai mari să aparţină unui obiect diferit din imagine şi să aibă nivel de gri mai puţin reprezentativ pentru pixelul estimat. În consecinţă, efectul lor asupra rezultatului estimării ar trebui diminuat. Este exact ceea ce şi fac filtrele cu mediere ponderată.

Există multiple posibilităţi de a se obţine filtre cu mediere ponderată. Între acestea, de o largă utilizare se bucură filtrele binomiale, datorită simplităţii şi a proprietăţilor lor favorabile [Jahne 1995]. Filtrele binomiale 2D sunt construite în formă separabilă, pe baza filtrelor binomiale 1D. Un filtru binomial de orice dimensiune poate fi obţinut prin convoluţia repetată a măştii:

bx 1

21 1 (6.12)

ce calculează pur şi simplu media a doi pixeli vecini. Vom nota

bxn

n

1

21 1

1

21 1

1

21 1

de ori

. (6.13)

sunt de interes mai ales măştile cu n par, conţinând un număr impar de elemente. Exemplificăm câteva asemenea filtre:

b

b

b

b

x

x

x

x

2

4

6

8

1

21 2 1

1

161 4 6 4 1

1

641 6 15 20 15 6 1

1

2561 8 28 56 70 56 28 8 1

(6.14)

Versiunea lui 2D a filtrului binomial de lungime 3 este

b 2

1

41 2 1

1

4

1

2

1

1

16

1 2 1

2 4 2

1 2 1

.

(6.15)

Page 50: Manual ID Gpi

Grafică pentru calculator. Note de curs. Material în construcţie!Pentru lămuriri şi observaţii, a se contacta: [email protected]

Pentru filtrul de lungime 5, rezultă:

.

(6.16)

Filtrul binomial posedă, asemenea filtrului uniform, o proprietate de optimalitate. Fie, din nou, fk elementele imaginii cuprinse într-o fereastră oarecare, conţinând K pixeli. Se caută un estimator, g, astfel încât suma ponderată a abaterilor pătratice faţă de estimator

(6.17)

să fie minimă. Punând din nou condiţia:

2

0( )

,g

g (6.18)

obţinem după calcule simple soluţia:

. (6.19)

Se recunoaşte că în acest caz, soluţia optimală este o medie ponderată a eşantioanelor din fereastră. În particular, ponderile pot fi alese a fi coeficienţii filtrului binomial.

Efectul filtrului binomial asupra unei muchii 1D este ilustrat în Fig. 6.4. Se observă că, la dimensiuni egale, un filtru binomial afectează muchiile mai puţin decât unul uniform. Pentru obiectivitatea comparaţiei, este necesară precizarea că, la dimensiuni egale, gradul de suprimare a zgomotului este, de asemenea, mai redus la filtrul binomial.

Rezultate comparative ale netezirii cu filtrul binomial 5×5 şi cu filtrul uniform 5×5 sunt ilustrate în Fig. 6.5.

muchie idealã

medierearitmeticã

L

Filtru binomial

Page 51: Manual ID Gpi

Grafică pentru calculator. Note de curs. Material în construcţie!Pentru lămuriri şi observaţii, a se contacta: [email protected]

Fig. 6.4. Efectul filtrelor cu mediere ponderată asupra muchiilor

Efectul de estompare a muchiilor mai redus al filtrului binomial în comparaţie cu filtrul cu mediere aritmetică având aceeaşi dimensiune, se explică prin ponderarea mai redusă a efectului pixelilor îndepărtaţi de centrul imaginii asupra rezultatului estimării imaginii în centrul ferestrei, ceea ce este în concordanţă cu faptul că probabilitatea ca pixelii îndepărtaţi de centru să se abată de la modelul (implicit) de imagine constantă în fereastră este creşte cu distanţa de la centru. Prin ponderarea introdusă, filtrul binomial este mai puţin sensibil decât filtrul uniform la abaterile imaginii faţa de modelul optimizat de filtru. Este un prim pas util spre obţinerea unui filtru robust.

Fig. 6.5. Stânga: Imagine Lena original. Mijloc: Rezultat filtru binomial 5×5 . Dreapta: rezultat filtru uniform 5×5 .

6.2.3. Filtrul GaussianFiltrul Gaussian discret se obţine prin eşantionarea unei Gaussiene cu medie nulă:

(6.20)

Dispersia Gaussienei este un parametru ce permite dozarea gradului de netezire. Dimensiunile matricii operatorului discret trebuiesc alese astfel încât să se eşantioneze cel puţin intervalul 3 pe amblele direcţii. Chiar pentru parametri de valori moderate, rezultă operatori de dimensiuni relativ mari. Datorită eşantionării şi trunchierii spaţiale, constanta ce intervine în ecuaţia (6.20) nu se poate alege conform definiţiei distribuţiei continue. Considerând o fereastră de format (2w+1)× (2w+1), constanta se alege:

Page 52: Manual ID Gpi

Grafică pentru calculator. Note de curs. Material în construcţie!Pentru lămuriri şi observaţii, a se contacta: [email protected]

, (6.21)

pentru a se asigura normalizarea necesară păstrării valorii medii a imaginii. Calculul convoluţiei cu masca filtrului gaussian poate fi accelerat substanţial prin exploatarea separabilităţii nucleului:

.

(6.22)

De remarcat, de asemenea, simetria circulară a operatorului: coeficienţii filtrului sunt constanţi pe o rază, r2=x2+y2.Filtrul Gaussian are numeroase proprietăţi de optimalitate.

6.3. Filtre de netezire neliniare

6.3.1. Filtrul median Metodele de netezire liniare funcţionează bine în regiunile de imagine netede, afectate de zgomot cu distribuţie gaussiană, dar au probleme în prezenţa zgomotului în impulsuri, de tipul produs de erorile introduse de canale de comunicaţie digitală afectate de perturbaţii. Un asemenea zgomot se caracterizează prin faptul că pixelii afectaţi sunt relativ distanţaţi spaţial, dar amplitudinea erorii este mare, valoarea pixelului afectat de zgomot părând să nu mai aibă vreo legătură cu valoarea corectă. Acest tip de zgomot mai este denumit zgomot de canal sau zgomot de tip sare şi piper, de la aspectul produs în imagine (Fig. 6.6 a).

a)

Page 53: Manual ID Gpi

Grafică pentru calculator. Note de curs. Material în construcţie!Pentru lămuriri şi observaţii, a se contacta: [email protected]

b)

c)

d)

Fig.6. 6. Imagine cu zgomot binar: a) imaginea cu zgomot, b) filtru median 55, c) filtru uniform 55, d) filtru binomial 55

Filtrele liniare cu mediere sau cu mediere ponderată, vezi Fig. 6.6. c) şi d), au o eficacitate modestă în prezenţa unui asemenea zgomot. Prin mediere, impulsurile scad în intensitate, dar se redistribuie pe suprafaţă

Page 54: Manual ID Gpi

Grafică pentru calculator. Note de curs. Material în construcţie!Pentru lămuriri şi observaţii, a se contacta: [email protected]

mai mare, vizibilitatea lor fiind puţin influenţată favorabil de opera’ia de filtrare liniară. Concomitent, se manifestă şi efectul nefavorabil al filtrelor liniare, de estompare a contururilor. Atât zgomotul binar cât şi contururile violează flagrant ipotezele de optimalitate pentru filtrele liniare. Prin comparaţie, filtrul median 55 (Fig. 6.6 b), elimină aproape integral zgomotul binar şi în acelaşi timp afectează mai puţin redarea contururilor.

Filtrul median este un operator neliniar, ce înlocuieşte fiecare pixel cu mediana pixelilor aflaţi într-o fereastră centrată în jurul acestuia. Mediana unui şir de numere reprezintă elementul aflat la mijlocul şirului, după ordonarea lui. Prin ordonare, vom înţelege în general ordonarea în sensul crescător, deşi acest aspect este neimportant din punctul de vedere al definiţiei medianei. Schema bloc a procedeului de prelucrare pentru un pixel de ieşire este redată în fig.6.7. Vom nota cu f1, f2, ..., fN pixelii din fereastră şi cu f(1), f(2), ..., f(N) pixelii din şirul ordonat. Rezultatul prelucrării este f(m) , cu proprietatea: m = (N + 1) / 2. De menţionat că numărul elementelor din fereastră, N, se alege impar, astfel ca m să fie un număr întreg .

Fig. 6.7 Schema-bloc a filtrului median

Un exemplu de calcul pentru un filtru median cu fereastră pătrată de 33 pixeli se dă în Fig. 6.8.

Fig. 6.8. Exemplu de calcul al medianei într-o fereastră pătrată 33

Proprietăţi ale filtrului median

f1

f2

fN

.

.

.

ordonare

f(1)

f(2)

f(N)

.

.

.

selecţie f(m)

mediană

6 7

3 7 8

2 3

4 6 7

2, 3, 3, 4, 6, 7, 7, 7, 8

Page 55: Manual ID Gpi

Grafică pentru calculator. Note de curs. Material în construcţie!Pentru lămuriri şi observaţii, a se contacta: [email protected]

NeliniaritateSelecţia este o operaţie neliniară. Astfel,

mediana{ f1 + f2} mediana{ f1} + mediana{ f2}. (6.23)

Totuşi,

mediana{c f } = c mediana{ f }, (6.24)

mediana{c + f } = c + mediana{ f }. (6.25)

Efectul asupra mediei Mediana modifică media imaginii, dacă distribuţia intensităţii este nesimetrică.

Optimalitate Asemenea filtrului de mediere aritmetică, filtrul median posedă o anumită proprietate de optimalitate, în sensul că furnizează o estimare de eroare minimă a intensităţii dintr-o fereastră cu un nivel constant. În acest caz însă, eroarea minimizată este definită prin suma abaterilor în modul faţă de nivelul estimat:

( ) | |( ) ( )f f fm k mk

N

1

(6.26)

Pentru a demonstra acest fapt, grupăm termenii sumei în mod convenabil:

( ) (| | | |) ( )( ) ( ) ( )

( )/

( ) ( ) ( ) ( )

( )/

f f f f f f fm k mk

N

N k m N k kk

N

1

1 2

1

1 2

.

(6.27)

Să presupunem că selectăm la ieşirea filtrului un element diferit de mediană, de exemplu f(m1). Eroarea devine:

( ) (| | | |) | |

( ) | |

( ) ( ) ( )

( )/

( ) ( ) ( ) ( )

( ) ( ) ( )

f f f f f f f

f f f

m k mk

N

N k m m m

m m m

1 11

1 2

1 1

1

(6.28)Continuând raţionamentul, obţinem pentru orice selecţie a unui rang q mai mic decât m,

( ) ( ) | |( ) ( ) ( ) ( )f f f fq m q qk q

m

1

1

, (6.29)

Page 56: Manual ID Gpi

Grafică pentru calculator. Note de curs. Material în construcţie!Pentru lămuriri şi observaţii, a se contacta: [email protected]

deci eroarea este mai mare decât la mediană. Similar se arată că eroarea este mai mare pentru oricare q>m.

Această proprietate a filtrului median, de a minimiza suma distanţelor la restul eşantioanelor din ferestră, poate servi şi ca definiţie mai generală a filtrului median, valabilă şi pentru date vectoriale, de exemplu imagini color. Prin aplicarea independentă a filtrului median asupra componentelor color (de exemplu R,G,B) nu se mai garantează selecţia medianei pentru cele trei componente de la acelaşi eşantion din fereastră, putând rezulta culor false, mai ales la zonele de tranziţie dintre obiecte.

Rejecţia zgomotului Aşa cum s-a menţionat deja, filtrul median este deosebit de eficient în rejecţia zgomotului binar. Să presupunem că într-o zonă cu nivelul de gri constant se injectează un zgomot contând în impulsuri, de mare amplitudine. Cât timp proporţia pixelilor afectaţi de zgomot este sub 50% în fereastra de filtrare, filtrul median reconstituie semnalul perfect, ca şi cum zgomotul nu ar fi existat! Pe de altă parte, filtrul median are performanţe mediocre în prezenţa zgomotului gaussian, pentru care filtrele liniare sunt mai bine adaptate.

Efectul asupra muchiilorFiltrul median păstrează muchiile mult mai bine decît filtrele de netezire liniare. O muchie treptă este redată perfect, pentru că filtrul median nu mediază ci selectează un anumit pixel din fereastră. Filtrul median păstrează rampele de luminanţă.

Efectul asupra punctelor, colţurilor şi a liniilor subţiri O proprietate uneori mai puţin favorabilă a filtrului median este aceea că el şterge punctele izolate, colţurile, liniile subţiri, şi alte detalii de dimensiuni reduse în comparaţie cu fereastra de filtrare. Câteva exemple concludente sunt ilustrate în Fig. 6.9.

Aplicare repetată Filtrul median poate fi aplicat în mod repetat, rezultând o netezire mai pronunţată. După un număr de iteraţii, ieşirea tinde să se stabilizeze, deşi acest lucru nu se întîmplă în mod necesar.

Filtrul median separabil Aplicarea succesivă a unui filtru median cu fereastră orizontală şi a unuia cu fereastră verticală definesc filtrul median separabil. Filtrul separabil nu este echivalent cu un filtru cu fereastră rectangulară, dar are performanţe apropiate. Avantajul filtrului separabil constă în reducerea numărului de operaţii. Câştigul este mai mare decât la filtrele liniare, pentru că numărul mediu de comparaţii creşte pătratic cu numărul elementelor din fereastră.

Page 57: Manual ID Gpi

Grafică pentru calculator. Note de curs. Material în construcţie!Pentru lămuriri şi observaţii, a se contacta: [email protected]

Fig.6.9. Efectul filtrului median cu fereastră pătrată 33 asupra unor imagini-test

Unele din deficienţele exemplificate pot fi remediate prin utilizarea unei ferestre în formă de cruce (Fig. 6.10).

Fig. 6.10. Rezultatul prelucrării imaginilor-test din Fig. 4.10, cu filtrul median cu fereastră în formă de cruce, cu 9 elemente

Variante ale filtrului median

Filtrul median ponderat sau mediana cu repetiţii se defineşte cu ajutorul unei măşti cu ponderi, asemănător filtrelor liniare. Ponderea fiecărui pixel indică de cîte ori se repetă acel pixel pentru a fi introdus în

imagine test de intrare

rezultatul prelucrării cu filtrul median cu fereastră de 33 pixeli

rezultatul prelucrării cu filtrul median cu fereastră în formã de cruce, cu 9 elemente

Page 58: Manual ID Gpi

Grafică pentru calculator. Note de curs. Material în construcţie!Pentru lămuriri şi observaţii, a se contacta: [email protected]

şirul ordonat. Procedeul permite să li se acorde pixelilor o importanţă dependentă de poziţia lor în fereastră. În general, pixelii centrali vor fi ponderaţi mai puternic. De menţionat că ponderile pot fi şi numere neîntregi. Mediana se obţine pornind de la o extremă a şirului ordonat şi însumând ponderile aferente eşantioanelor şirului până când se cumulează jumătate din suma totală a ponderilor acordate. Un exemplu se dă în Fig. 6.12. Filtrul median cu repetiţii păstrează contururile mai bine decât filtrul median convenţional. În acelaşi timp, eficienţa lui în eliminarea zgomotului binar este diminuată.

Fig. 4.15. Filtrul median ponderat

Filtrul median multiplu este conceput în ideea detecţiei şi păstrării structurilor locale coerente, de tipul liniilor subţiri sau al curbelor, concomitent cu rejecţia energică a zgomotului în impulsuri (Fig.6.13).Răspunsul filtrului este mediana medianelor celor patru regiuni şi a pixelului central.

6.3.2. Filtre LFiltrul median este un caz particular al filtrelor cu ordonare. Caracteristic acestor filtre este faptul că operează asupra eşantioanelor semnalului cuprinse într-o fereastră, după o ordonare prealabilă. O clasă generală de filtre cu ordonare o reprezintă filtrele de tip L, denumite astfel după estimatorii de tip L, cunoscuţi în statistică. Schema-bloc a unui filtru L este redată în Fig.6.14.

6 7

3 7 8

2 3

4 6 7

2, 2, 3, 3, 3, 3, 4, 6, 6, 7, 7, 7, 7, 7, 8

3

1 1

1 1

2 2

2

2

Page 59: Manual ID Gpi

Grafică pentru calculator. Note de curs. Material în construcţie!Pentru lămuriri şi observaţii, a se contacta: [email protected]

Fig. 6.13. Filtru median multiplu

Fig. 6.14. Schema-bloc a filtrelor L, cu ordonare.

Prima etapă de prelucrare realizează ordonarea elementelor de imagine din fereastră. În faza următoare, fiecare element din şirul ordonat f(i), este multiplicat cu un coeficient care ponderează importanţa lui, în funcţie de poziţia în şir. Ne reamintim că, la filtrul median cu repetiţii, ponderile se alocă în funcţie de poziţia pixelului în fereastra de filtrare, nu în şirul ordonat. Stabilind câte un singur coeficient diferit de zero, obţinem diferite versiuni ale filtrelor procentilă. Câteva cazuri particulare importante ale filtrelor de tip L sunt redate sintetic în Fig. 6.15.

Filtrul mid range calculează media extremelor. Este interesant să arătăm că, asemenea filtrului de mediere aritmetică şi a filtrului median, media extremelor este un estimator ce aproximează cu eroare minimă

mi = mediana(Ri), i =1,2,3,4.

Rezultat = mediana(m1,m2,m3,m4,m5)

R1

R2

R3

R4

m5

insumare

y

f(1)f1

f2

fN

.

.

.

ordonare

f(2)

f(N)

.

.

.

a1

a2

aN

ponderi

y = a1f(1) + a2 f(2)+...+ aN f(N)

Page 60: Manual ID Gpi

Grafică pentru calculator. Note de curs. Material în construcţie!Pentru lămuriri şi observaţii, a se contacta: [email protected]

nivelul de gri din fereastră cu un nivel constant. Vom da erorii o definiţie mai generală:

Fig. 6.15. Filtre L elementare.

( ) | |( )f f fkr

k

N

1

. (6.30)

Pentru r = 1, regăsim că estimatorul optimal este mediana. Pentru r = 2, regăsim că estimatorul optimal este media aritmetică. Pentru r , estimatorul optimal este media extremelor.

Putem demonstra acest lucru, grupând termenii erorii ca la filtrul median:

( ) (| | | | )( )

( )/

( )f f f f fkr

k

N

N kr

1

1 2

1 . (6.31)

Când r , suma este dominată de termenul k =1, care, prin ridicare la o putere infinită face neglijabilă contribuţia celorlalţi termeni. Putem aproxima deci

( ) | | | | max{| | , | | }.( ) ( ) ( ) ( )f f f f f f f f frN

r rN

r 1 1 (6.32)

Evident, expresia de mai sus este minimizată de media extremelor,

( ) ( )f

f f N1

2 . (6.33)

a1=1

Min. . .

. . .

aN=1

Max

. . . . . .

am=1

Median

a1=.5 aN=.5

Mid range. . .

Page 61: Manual ID Gpi

Grafică pentru calculator. Note de curs. Material în construcţie!Pentru lămuriri şi observaţii, a se contacta: [email protected]

Media în jurul medianei este un alt caz particular interesant al filtrului L, la care:

aQ pentru Q k Q

în restk

1 2 1

0

/ ( ),

, (6.34)

Procentul pixelilor din fereastra ordonată care se utilizează, = (2Q + 1) / N, defineşte gradul de mediere. Filtrul prezintă proprietăţi intermediare între filtrele cu mediere şi filtrul median. Pentru = 1 se obţine media aritmetică, în timp ce valoarea = 1 / N corespunde medianei.

6.3.3. Filtre adaptive Filtrele adaptive folosesc coeficienţi de ponderare, ak, variabili. Valorile coeficienţilor se aleg “adaptiv”, în funcţie de proprietăţi locale ale datelor din fereastră, estimate într-un anumit mod. Media, dispersia sau relaţia dintre valorile unor eşantioane din setul ordonat pot constitui indicii pentru adaptarea coeficienţilor.

Media în jurul medianei devine un filtru adaptiv cu ordonare statistică dacă se alege adaptiv. Dacă are valori reduse, este probabil să ne găsim pe un platou de gri cu zgomot gaussian. Filtrul optim este cel de mediere, deci 1. Dacă are valori ridicate, poate fi o zonă de muchie sau să existe zgomot binar. În acest caz, filtrul median este preferabil, cu = 1 / N. O variantă adaptivă a mediei în jurul medianei defineşte coeficienţii filtrului în forma:

apentru f f p

în resti

i m

1

0

, | |

,( ) ( )

(6.35)

Practic, putem alege p = 3, în absenţa unor criterii de optimizare mai precis enunţate. Media adaptată în funcţie de modulul diferenţelor se defineşte cu ajutorul ecuaţiei (6.35) unde:

p = mediana{| f(k )f(m) |}, k = 1,2,...,N. (6.36)

Acest filtru calculează media eşantioanelor ce diferă în modul faţă de mediană cu o valoare mai mică decât mediana diferenţelor în modul. Mediana diferenţelor în modul faţă de median este un estimator robust al dispersiei, fiind adesea adoptat în aplicaţii de vedere artificial.

Mediana kNN (k nearest neighbour) selectează în fereastră eşantioanele, în număr de k, cele mai apropiate ca valoare de pixelul central al ferestrei (neordonate). Rezultatul este mediana eşantioanelor selectate. O variantă apropiată a acestui filtru (filtrul kNN) calculează media celor k eşantioane selectate.

Page 62: Manual ID Gpi

Grafică pentru calculator. Note de curs. Material în construcţie!Pentru lămuriri şi observaţii, a se contacta: [email protected]

Filtrul adaptat sigma defineşte coeficienţii cu ajutorul ecuaţiei

, (6.37)

unde f0 este pixelul central al ferestrei. Rezultate ale filtrului adaptat sigma cu fereastră de 7×7 pixeli şi prag 32 pentru o imagine monocromatică, sunt prezentate în figura 6.16.

Fig. 6.16. Rezultate ale filtrului adaptat sigma, cu fereastră de 7×7 pixeli şi prag 32, asupra unei imagini monocromatice.

Se observă eliminarea detaliilor ce contrastează slab, concomitent cu păstrarea celor cu contrast ridicat.

O altă versiune a filtrului adaptat sigma, cu ponderare nuanţată, defineşte ponderile :

Page 63: Manual ID Gpi

Grafică pentru calculator. Note de curs. Material în construcţie!Pentru lămuriri şi observaţii, a se contacta: [email protected]

c f f

ac

c

i i

ii

kk

N

255 0

1

| |,

.

( )

(6.38)

Ideea centrală a ultimelor două filtre este de a estima valoarea imaginii în centrul ferestrei pe baza unei regiuni omogene căreia pixelul central să-i aparţină cu maximă probabilitate. Există numeroase variante ale acestei idei, de mediere în regiuni selective, ce nu este legată de fapt de operaţia de ordonare.

Filtrul propus de Kuwahara şi dezvoltat ulterior de [Nagao şi Matsuyama 1980] defineşte un set de 8 regiuni de 7 pixeli generate prin rotirea unei măşti de formă alungită în jurul unui pixel central (Fig.6.17). Pentru fiecare mască, Mi, se calculează media, i şi dispersia i

2 a pixelilor de sub mască. Rezultatul filtrării la coordonatele pixelului este media i a regiunii de dispersie minimă.

Medierea dependentă de gradient defineşte coeficienţii de mediere din fereastră proporţionali cu inversul “gradientului”, evaluat ca modul al diferenţei faţă de pixelul central:

m n

m n

m n

m n

m nm n W

f f

a

a

,

, ,

,

,

,,

,

| |,

,

.

11

21

2

1

2

0 0

0 0

(6.39)

Definiţia normalizează gradientul invers la intervalul (0-2] şi acordă jumătate din suma ponderilor pixelului central.

Netezirea cu extrem selectează elementul minim sau maxim din fereastră. Decizia se face pentru nivelul maxim dacă acesta este mai apropiat de media pixelilor din fereastră decât nivelul minim. În caz contrar, minimul este nivelul selectat. În locul mediei, se poate folosi mediana. Concomitent cu netezirea, filtrul tinde să accentueze contururile în imagine.

6.4. Accentuarea contururilor şi a detaliilor în imagine

Page 64: Manual ID Gpi

Grafică pentru calculator. Note de curs. Material în construcţie!Pentru lămuriri şi observaţii, a se contacta: [email protected]

Analiza imaginilor poate avea ca obiectiv examinarea unor structuri locale de dimensiuni reduse, de tipul liniilor subţiri, punctelor etc. Fisurile în lagărele de safir pentru pivoţi, utilizate în mecanica fină, sau accidentele vasculare în angiografia de contrast sunt asemenea exemple.

6.4.1. Filtre trece-susCreşterea vizibilităţii detaliilor fine poate fi obţinută prin operaţii de filtrare de tip trece-sus. O modalitate simplă şi convenabilă de a obţine accentuarea frecvenţelor înalte este de a scădea din imagine o versiune filtrată cu un filtru trece-jos. Operaţia se poate scrie:

L L

L( )

f = f h,

g f f

c c ,1(6.50)

unde c1 este o constantă care controlează gradul de accentuare a detaliilor. Denumită “unsharp masking”, tehnica este cunoscută din domeniul fotografic. Imaginea filtrată trece-jos se obţine prin expunerea defocalizată iar scăderea prin adunarea negativului. Folosind un filtru uniform 33 şi c = 10, obţinem operatorul trece-sus

Sh

1 1 1

1 9 1

1 1 1

. (6.51)

Alţi operatori 33 generaţi prin acest procedeu sunt:

Sh

0 1 0

1 5 1

0 1 0

(6.52)

şi

Sh

1 2 1

2 13 2

1 2 1

. (6.54)

De remarcat că operatorii astfel obţinuţi au suma ponderilor unitară, deci păstrează media imaginii.Operatorul definit de ecuaţia (5.76) poate fi interpretat ca o însumare a imaginii cu imaginea filtrată cu un operator de ordinul doi, ce aproximează discret un laplacian:

Lh

1

1 4 1

1

.

(6.55)

Page 65: Manual ID Gpi

Grafică pentru calculator. Note de curs. Material în construcţie!Pentru lămuriri şi observaţii, a se contacta: [email protected]

În Fig. 6.23, este ilustrat rezultatul filtrării unei imagini cu operatorul trece-sus definit prin ecuaţia (6.52).

Datorită prezenţei operaţiilor de scădere (de tip derivativ), este posibilă (şi în general se şi produce) depăşirea gamei dinamice iniţiale a imaginii. La implementare, este necesar să se trateze atent acest aspect, prin transformarea scării de gri.

Fig. 6.23. Imagine filtrată cu operatorul trece-sus definit prin ecuaţia (6.52)

Elemente de grafică de calculator

Formele grafice complexe sunt sintetizate cu ajutorul unor elemente grafice (“primitive grafice”) simple: segmente de dreaptă, cercuri, curbe, suprafeţe elementare (petice). Pentru că majoritatea aplicaţiilor graficii de calculator sunt

Page 66: Manual ID Gpi

Grafică pentru calculator. Note de curs. Material în construcţie!Pentru lămuriri şi observaţii, a se contacta: [email protected]

interactive sau necesită funcţionare în timp real cu frecveţe de schimbare a cadrelor compatibile cu cele din televiziune, sunt necesare metode de trasare rapide. Prin trasare, înţelegem redarea pe un ecran cu rezoluţie finită sau tipărirea folosind, de asemenea, o imprimantă cu rezoluţie finită. Procesul prin care o formă grafică, precizată în calculator cu ajutorul unui număr redus de parametri, este transpusă pe ecran sau hârtia de imprimare mai este denumit şi conversie de scanare.

1. Trasarea segmentelor de dreaptă

1.1.Metoda diferenţială

Ecuaţia unei drepte se poate scrie:(1.1)

Rezultă forma iterativă a ecuaţiei dreptei:(1.2)

Segmentul de dreaptă este definit de punctele de pornire şi de oprire (xp,yp), (xo,yo).Alegerea incrementului:

mic: ineficientmare: linia discontinuă

Optim: max(Δx, Δy) = 1.

1.2. Algoritmul DDA pentru trasarea segmentelor de dreapt ă

// DDA: “differential digital analyzer”lineDDA( int xPornire, int yPornire, int xOprire, int yOprire ){//Se calculează iniţial:

int distX = abs( xPornire ─ xOprire );int distY = abs(yPornire ─ yOprire );int numarPasi = max( distX, distY );float deltaX = distX / numarPasi;float deltaY = distY / numarPasi;float x = xPornire; float y = yPornire; // sunt necesare variabile x,y flotante!

//Se derulează bucla principală:for( int index = 0; index < numarPasi; index ++ ){

Putpixel( round(x), round(y), 0 ); // traseaza un pixel negru

// pe fundalul, presupus alb

// round() efectueaza operatia de

Page 67: Manual ID Gpi

Grafică pentru calculator. Note de curs. Material în construcţie!Pentru lămuriri şi observaţii, a se contacta: [email protected]

// rotunjire la intreg

x +=deltaX; y +=deltaY;

}} // terminat funcţie

Avantaj: simplu de programatDezavantaj: necesită operaţii cu numere flotante în bucla principală

1.3. Algoritmul Bresenham pentru segmente de dreaptă

Este mai eficient decât DDA, pentru că evită complet operaţiile cu numere flotante. Se pretează şi la implementare hardware cu procesoare ieftine (nu necesită nici înmulţiri sau împărţiri).

Fig. 1. Eroarea la un pas pe direcţia orizontală

Presupunem că dreapta trasată aparţine primului octant (panta m între 0 şi 450). Rezultă că numărul de paşi este egal cu xOprire-xPornire. La fiecare pas se incrementează x. La unii paşi se incrementează şi y: când eroarea cumulată este mai mare decât 0.5. Eroarea cumulată se defineşte ca distanţa la care se află punctul curent trasat faţă de dreapta teoretică. Un pas pe direcţia x creşte eroarea cumulată cu

.

(1.3)

Un pas pe direcţia y reduce eroarea cumulată cu 1. Putem acum construi un algoritm care trasează un pixel al dreptei la fiecare pas, bazat pe bucla:

for(x=xPornire; x<=xOprire;x++){

Putpixel(x,y,0);

2

1

2

1

e0

0

Page 68: Manual ID Gpi

Grafică pentru calculator. Note de curs. Material în construcţie!Pentru lămuriri şi observaţii, a se contacta: [email protected]

eroare+=e_0;if(eroare>0.5){

y++;eroare-=1;

}}

Problema este că variabila eroare trebuie să fie flotantă în implementarea de mai sus. acest lucru poate fi evitat, dacă înmulţim ecuaţia eroarea din (1.3) cu 2*(xOprire-xPornire). În acest caz, deplasarea pe direcţia x va creşte noua eroare cu DY= 2*(yOprire-yPornire).Similar, deplasarea pe direcţia y reduce eroarea cuDX=2*(xOprire-xPornire).

În expresia if(), comparaţia ar trebui să se facă acum cu xOprire-xPornire. Pentru că o comparaţie cu 0 este mai rapidă (testare de semn), putem iniţializa eroarea cu ─( xOprire-xPornire)= xPornire-xOprire şi testa în buclă eroarea pentru zero. Rezultă următorul algoritm, datorat lui Bresnham: // “algoritm Bresenham pentru segmente de dreaptă în primul octant”// versiune C++lineBresenheim( int xPornire, int yPornire, int xOprire, int yOprire ){//Se calculează iniţial:

int DX = 2 * ( xOprire ─ xPornire );int DY = 2 * ( yOprire ─ yPornire );int eroare = xPornire ─ xOprire; // valoare negativăint x, y=yPornire;

//Se derulează bucla principală:for( x = xPornire; x < xOprire; x ++ ){

Putpixel( x, y, 0 ); // traseaza un pixel negru // pe fundalul, presupus alb

eroare += DY;if( eroare > 0 ){

y ++;eroare -= DX;

}}

} // terminat funcţia lineBresenham()Drepte ce nu aparţin primului octant se trasează similar (prin simetrie).

2. Cercuri

Ecuaţia unui cerc ce trece prin origine:

. (1.4)

Dacă centrul este în (xc, yc), se face o translaţie, definită prin

Page 69: Manual ID Gpi

Grafică pentru calculator. Note de curs. Material în construcţie!Pentru lămuriri şi observaţii, a se contacta: [email protected]

(1.5)

Forma (1.4) nu este adecvată pentru trasare. De exemplu, dând valori lui x, pentru a găsi y trebuie rezolvată o ecuaţie de gradul doi, trebuie verificat dacă soluţiile sunt reale etc.

Forma diferenţială a ecuaţiei cercului: 2xdx+2ydy=0, sau

.

(1.6)

Incrementul ε se alege invers proporţional cu raza r.Forma discretă a ecuaţiei:

(1.7)

Problemă: trasează o spirală, pentru că

Soluţie: Se modifică ecuaţiile (1.7), în forma(1.8)

Se poate arăta (ca exerciţiu) că raza rămâne constantă în acest caz.

2.1. Algoritmul DDA pentru cerc Se obţine următorul algoritm DDA pentru cerc. Algoritmul exploatează simetria cercului şi trasează simultan câte 8 puncte. De fapt se generează doar un octant (între 450 şi 900).

cercDDA(int x_c, int y_c, int r){float x = 0, y = r;float epsilon = 1 / (float) r;while( x < y )

{put8pix( round(x), round(y), x_c, y_c ); // pune 8 pixelix += epsilon * y;y -= epsilon * x; // x a fost deja actualizat!}

} // end cercDDA()

put8pix( int x, int y, int x_c, int y_c ){putpixel(x+x_c, y+y_c, 0);putpixel(x–x_c, y+y_c, 0);putpixel(x+x_c, y–y_c, 0);putpixel(x–x_c, y–y_c, 0);putpixel(y+y_c, x+x_c, 0);putpixel(y–y_c, x+x_c, 0);putpixel(y+y_c, x–x_c, 0);putpixel(y–y_c, x–x_c, 0);

Page 70: Manual ID Gpi

Grafică pentru calculator. Note de curs. Material în construcţie!Pentru lămuriri şi observaţii, a se contacta: [email protected]

}

2.2. Metoda rota ţ iei

Se porneşte de la ecuaţiile parametrice ale cercului:(1.9)

Un punct rotit în sens trigonometric cu unghiul θ are coordonatele:(1.10)

Pentru trasarea cercului, se alege un unghi incremental θ foarte mic.

Observa ţie privind implementarea Apelul repetat al funcţiilor trigonometrice (lente) poate fi simplu evitat. Se precalculeazăa=cos(θ), b=sin(θ), rezultând apoi algoritmul în forma:

(1.11)

Algoritmul ce rezultă este similar celui DDA. Exerciţiu: scrieţi o funcţie pentru trasarea cercului prin metoda rotaţiei.

2.3. Algoritmul Bresenham pentru cerc

Conduce la operaţii exclusiv cu numere întregi.Generează de fapt un octant, ca şi DDA, restul rezultă prin simetrie. Porneşte tot de la punctul maxim superior, de coordonate x=0, y=r.Coordonata x se incrementează la fiecare pas. Coordonata y se decrementează numai la unii paşi. Trebuie găsită condiţia pentru decrementarea lui y. Apar situaţiile posibile din figura 2:

Pn este punctul curent, A, B, puncte succesoare candidat. Pentru P(x,y) notăm f(x,y)=f(P).Observăm că f(P)<0 în interiorul cercului, f(P)=0 pe cerc şi f(P)>0 în exteriorul cercului.

Pentru situaţiile a) şi b) succesorul punctului Pn trebuie să fie punctul A, mai apropiat de cerc decât B (y nu se incrementează). Pentru situaţiile d) şi e), succesorul trebuie să devină punctul B. Situaţia din c) este cea mai complicată, succesori putînd fi atât A, cât şi B. Trebuie ales punctul cel mai apropiat de cerc. Acesta este A dacă f(A) < –f(B), respectiv dacă f(A)+f(B) <0. Observăm că aceeaşi inegalitate este valabilă şi pentru situaţiile a) şi b). Semnul inegalităţii se schimbă pentru situaţiile când opţiunea ideală este pentru punctul B. Rezultă următoarea regulă simplă: y se decrementează (se alege B) dacă S= f(A)+f(B) <0.

Page 71: Manual ID Gpi

Grafică pentru calculator. Note de curs. Material în construcţie!Pentru lămuriri şi observaţii, a se contacta: [email protected]

Fig. 2

Interesant este faptul că suma S poate fi evaluată recursiv, fără operaţii de ridicare la putere, presupuse de ecuaţia (1.4) a cercului. Formula de calcul este dependentă de direcţia de deplasare de la pasul precedent. Apar două situaţii (v. figura 3):

I) S≥0, deplasare orizontală,II) S<0, deplasare oblică (orizontală şi verticală)

f(A)<0, f(B)<0.

a)

ynPn A

Byn+1

xn xn+1

f(A)=0, f(B)<0.

b)

ynPn A

Byn+1

xn xn+1

f(A)>0, f(B)<0.

c)

ynPn A

Byn+1

xn xn+1

f(A)>0, f(B)=0.

d)

ynPn A

Byn+1

xn xn+1

f(A)>0, f(B)>0.

e)

ynPn A

Byn+1

xn xn+1

Pn Pn+1 A

B

xn+1

cazul I)

yn

Pn Pn+1

A

B

xn+1

cazul II

yn

Page 72: Manual ID Gpi

Grafică pentru calculator. Note de curs. Material în construcţie!Pentru lămuriri şi observaţii, a se contacta: [email protected]

Cazul I:Sn = (xn+1)2+yn

2–r2+(xn+1)2+(yn–1)2–r2,Sn+1 = (xn+2)2+yn

2–r2+(xn+2)2+(yn–1)2–r2 şi rezultăSn+1=Sn+4xn+6.

Cazul II:Sn = (xn+1)2+yn

2–r2+(xn+1)2+(yn–1)2–r2,Sn+1 = (xn+2)2+(yn–1)2–r2+(xn+2)2+(yn–2)2–r2 şi rezultăSn+1=Sn+4(xn– yn)+10.

La pornire, xn=0, yn=r şi Sn=1+r2– r2+1+(r–1)2–r2= 3–2r.

Rezultă următorul algoritm (în cod C++)// algoritmul Bresenham pentru cerccercBresenham( int x_c, int y_c, int r ){

int x=0, y=r, S=3–2*r;while(x<y){

put8pix( x, y, x_c, y_c );if(S<0)

S+=4*x+6;else{

S+=4*(x-y)+10;y++;

}x++;

}if(x==y)

put8pix( x, y, x_c, y_c );} // end cercBresenham()

3. Poligoane

Page 73: Manual ID Gpi

Grafică pentru calculator. Note de curs. Material în construcţie!Pentru lămuriri şi observaţii, a se contacta: [email protected]

Un poligon poate definit ca o succesiune de noduri (vârfuri). Ordinea nodurilor este importantă. Poate fi definit 2D sau 3D (wireframe).

Poligonul 2D este mai mult decât o colectie de segmente de dreaptă. El are un interior, ce poate poseda diferite atribute, ca: transparenţă, culoare, textură.

Trasarea laturilor se face ca la segmentele de dreaptă. Umplerea interiorului, la reprezentarea în imagine (aşa numita conversie de scanare) este o problemă distinctă. Înaintea umplerii trebuie realizată decuparea poligonului, ce se va prezenta puţin mai jos.

3.1. Umplerea poligoanelor Pentru simplitate, să considerăm cazul poligonului cu interiorul colorat (nu texturat)În principiu, putem proceda în următorul mod:

Exporăm imaginea linie cu linie şi pixel cu pixel Daca pixelul curent este unul interior, îl colorăm

Cu puţine excepţii, putem afla simplu dacă un pixel este interior. Presupunem că linia curentă intersectează poligonul de un număr de n ori şi că primul pixel de pe linie este unul exterior. Folosim variabila e_interior pentru a marca starea pixelului curent. Variabila poate lua valoarea 0 sau FALSE dacă pixelul este exterior şi 1 sau TRUE dacă pixelul este interior. Fiecare intersecţie cu o latura a poligonului schimbă starea variabilei e_interior. Practic, pixelul curent este interior după un număr impar de intersecţii cu laturile poligonului. Pentru a scăpa de excepţiile nedorite, ce apar în apropierea vârfurilor, putem recurge la un artificiu foarte simplu. Trebuie să ne asigurăm că nici un vârf nu cade pe o linie de scanare. În acest caz, orice linie intersectează latura în două puncte distincte (NU se face aproximarea la întreg a poziţiei intersecţiei!). În acest scop, înlocuim coordonata y a fiecărui vârf cu trunc(y) + 0,5. Astfel toate vârfurile vor fi situate pe linia mediană dintre două linii de scanare succesive (vezi figura de mai jos).

La implementarea algoritmului de umplere pentru un poligon anume, nu se explorează întreaga imagine, ci numai liniile din intervalul (ymin, ymax). Mai mult, nu este cazul să calculăm analitic independent intersecţiile pentru fiecare linie de scanare. Cunoscând coordonata x1 a primului vârf al laturii definite de (x1, y1) şi (x2, y2), putem calcula panta dreptei:

Page 74: Manual ID Gpi

Grafică pentru calculator. Note de curs. Material în construcţie!Pentru lămuriri şi observaţii, a se contacta: [email protected]

(1.12)

Intersecţia cu prima dreaptă de scanare va fi decalată cu m/2 faţă de x1. Următoarele linii intersectează latura respectivă la abscise decalate succesiv cu dx=m.

Umplerea poligoanelor cu modele texturate se face de o manieră asemănătoare. Modelul este definit ca o mini-imagine de tip Bitmap (hartă de biţi), uzual o imagine binară. De exemplu, dacă modelul este un bitmap 8×8, prima linie a modelului se copiază pe liniile 0, 8, 16, ..., a doua pe liniile 1, 9, 17,... şi aşa mai departe. Similar se procedează pe coloane. Se va evita cu atenţie depăşirea limitelor interioare ale poligonului.

4. Fereastra de vizualizare

În aplicaţiile grafice, apare frecvent necesitatea transpunerii unei reprezentări grafice pe o anumită porţiune a ecranului, denumită fereastră de vizualizare sau viewport. Uzual, entitatea ce trebuie transpusă este definită în raport cu un sistem de coordonate specifice aplicaţiei, pe care le vom numi coordonate utilizator. Pentru a face operaţia de transpunere independentă de rezoluţia ecranului, este utilă normalizarea coordonatelor, astfel încât acestea să ia valori în intervalul 0-1. La schimbarea rezoluţiei ecranului, ceea ce mai trebuie schimbat în acest caz rămâne numai aşa-numitul driver de dispozitiv, ce interfaţează programul grafic cu ecranul.

Fie (x,y) coordonatele unui punct în fereastra utilizatorului, definită prin coordonatele: xul, xur, yut, yub cu indicii l şi r având semnificaţia stânga şi dreapta (de la left şi right) şi t, b semnificaţiile sus şi jos (de la top şi bottom). Fie xvl, xvr, yvt, yvb, coordonatele ferestrei de vizualizare, cu indicii având semnificaţii similare. Legătura între coordonatele utilizator şi cele de vizualizare este dată de transformarea de vizualizare:

(1.13)

(xul, yut)

(xur, yub)

FEREASTRA UTILIZATOR

ECRAN

FEREASTRA DE VIZUALIZARE

(xvl, yvt)

(xvr, yvb)

Page 75: Manual ID Gpi

Grafică pentru calculator. Note de curs. Material în construcţie!Pentru lămuriri şi observaţii, a se contacta: [email protected]

5. Tehnici de decupare

În procesul de manipulare şi reprezentare a obiectelor grafice, este posibil ca unele părţi ale acestora să nu se încadreze în interiorul ferestrei de vizualizare. O soluţie simplă pentru rezolvarea evitarea redării punctelor situate în afara ferestrei de afişare este să se verifice pentru fiecare punct încadrarea în fereastră şi să se traseze pixelul corespunzător numai în cazul afirmativ. O asemenea rezolvare nu este însă şi rapidă. Pentru forme simple, de tipul dreaptă sau poligon, este mai eficient să se determine partea vizibilă înainte de afişare şi să se reprezinte numai partea respectivă. Partea invizibilă se decupează.

5.1. Decuparea segmentelor de dreaptă 2D. Algoritmul Cohen-Sutherland

Planul grafic se împarte în nouă regiuni, codificate conform figurii de mai jos.

a)

1001 0001 0101

yvt

yvb

0110

xvr

0010

xvl

1010

1000 0000 0100

P2

C

BA

P1

b)

Page 76: Manual ID Gpi

Grafică pentru calculator. Note de curs. Material în construcţie!Pentru lămuriri şi observaţii, a se contacta: [email protected]

Codurile se construiesc atribuind fiecăruia din cei 4 biţi valori după cum urmează:

Bitul b0 este 1 dacă punctul este deasupra marginii superioare, yvt

Bitul b1 este 1 dacă punctul este dedesubtul marginii inferioare, yvb

Bitul b2 este 1 dacă punctul este la dreapta marginii din dreapta, xvr

Bitul b3 este 1 dacă punctul este la stânga marginii din stânga, xvl

Algoritmul primeşte codurile capeletor segmentului de dreaptă, pe care le combină eficient pentru a identifica mai multe situaţii posibile. În exemplul din figură, P1 are codul 1010, iar P2 are codul 0001.

Pasul 1. Se calculează funcţia logică pe biţi SAU. Dacă SAU dă zero pe toate poziţiile, ambele puncte sunt în interiorul ferestrei de afişare şi nu este nevoie de decupare. Se trece la Pasul 5, pentru a se trasa dreapta. În caz contrar, se trece la pasul următor.

Pasul 2. Dacă SAU nu dă 0 pe toate poziţiile, se face ŞI logic între coduri. Dacă funcţia ŞI nu dă zero pe toate poziţiile (avem cel puţin un 1) segmentul este complet în afara ferestrei de afişare, deci nu avem de trasat nimic şi algoritmul se încheie. În caz contrar, segmentul trebuie decupat şi se trece la pasul următor.

Pasul 3. Se inspectează codul lui P1. Astfel, dacă P1 are codul este 0000, P1 este un punct valid şi se trece la pasul următor. Dacă P1 are nu are codul este 0000, urmează să fie decupat. Se verifică întâi bitul cel mai semnificativ, b3. Dacă b3=1, P1 este situat la stânga marginii din

Page 77: Manual ID Gpi

Grafică pentru calculator. Note de curs. Material în construcţie!Pentru lămuriri şi observaţii, a se contacta: [email protected]

stânga. În acest caz (valabil pentru figura de mai sus), se calculează intersecţia dintre segmentul P1P2 şi marginea din stânga. Se obţin coordonatele punctului care înlocuieşte P1. În exemplul din figură, este punctul A. Acesta primeşte codul corespunzător poziţiei şi algoritmul se reia de la primul pas, cu P1=A. În exemplul din figură, A primeşte codul 0010 (un punct de pe marginea stângă este considerat valid pentru trasare, deci bitul b3 este setat pe zero).

Pasul 4. Se inspectează codul lui P2. Se procedează la fel ca la Pasul 3, pentru punctul P2.

De observat că la acest punct se ajunge numai după ce punctul P 1 a fost complet rezolvat. În exemplul din figură, pentru că noul P1 (A) are codul nenul, este din nou decupat, de data aceasta faţă de marginea de jos, pentru care bitul b1 este setat pe 1. Se obţine punctul B, care devine noul P1. La Pasul 4, P2 va fi decupat şi va primi coordonatele lui C.

Pasul 5. Se trasează segmentul de dreaptă P1P2 decupat (devenit segmentul BC). Algoritmul se încheie.

Un exemplu de program C de decupare ce foloseşte două funcţii pentru implementarea agoritmului de decupare Cohen-Sutherland se prezintă în continuare.

#define LEFT 8 // 1000 #define RIGHT 4 // 0100#define BOTTOM 2 // 0010#define TOP 1 // 0001////////////////////////////////////////////////////////////////////////////////////////////////////////int cod_regiune( // returnează codul regiunii pentru punctul (x,y) double x, // coordonate punct testat

double y, double xvl, // coordonate margini

double xvr,double yvt,double yvb)

{int regiune=0; // 0000if( x<xvl )

regiune = regiune | LEFT; // SAU pe bitielse if( x>xvr )

regiune = regiune | RIGHT; if( y<yvb )

regiune = regiune | BOTTOM; else if( y>yvt )

regiune = regiune | TOP;

return( regiune );}/////////////////////////////////////////////////////////////////////////////////////////////////////////////void decupare(

double x1, // coordonate P1

double y1,double x2, // coordonate P2

Page 78: Manual ID Gpi

Grafică pentru calculator. Note de curs. Material în construcţie!Pentru lămuriri şi observaţii, a se contacta: [email protected]

double y2 )

{int cod1, cod2, cod;double x,y;

cod1 = cod_regiune(x1,y1);cod2 = cod_regiune(x2,y2);

while( (cod1 | cod2) != 0 ) // SAU diferit de zero, mai avem de decupat

{if( (cod1 & cod2) != 0 ) // SI diferit de zero, nu avem de

trasat nimicreturn;

cod = cod1;if( cod == 0 ) // daca P1 nu trebuie decupat, se verifica P2

cod = cod2;

if( cod & LEFT ) // decupare la stinga{

x=xvl;y=y1 + (y2-y1)*(xvl-x1) / ( x2-x1 );

}else if( cod & RIGHT ) // decupare la dreapta {

x=xvr;y=y1 + (y2-y1)*(xvr-x1) / ( x2-x1 );

}

else if( cod & BOTTOM ) // decupare jos {

y=xvb;x=x1 + (x2-x1)*(yvb-y1) / ( y2-y1 );

}

else if( cod & TOP ) // decupare sus {

y=xvt;x=x1 + (x2-x1)*(yvt-y1) / ( y2-y1 );

}if( cod == cod1 ){

x1=x;y1=y;cod1 = cod_regiune(x1, y1);

}else{

x2=x;y2=y;cod2 = cod_regiune(x2, y2);

}

Page 79: Manual ID Gpi

Grafică pentru calculator. Note de curs. Material în construcţie!Pentru lămuriri şi observaţii, a se contacta: [email protected]

} // end while – bucla este parcursa de 4 ori in cazul cel mai defavorabil linie_2d( x1, y1, x2, y2 ); // functie de trasare a segmentului de dreapta} ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////

5.2. Decuparea poligoanelor. Algoritmul Sutherland-Hodgman

Decuparea poligoanelor NU se reduce la decuparea laturilor, fiind mult mai complexă. E chiar posibil ca un poligon concav să se separe în mai multe componente, aşa cum se ilustrează în figura următoare.

Algoritmul Shuterland-Hodgman foloseşte o strategie de tipul divide şi câştigă (divide and conquer), pentru a rezolva o problemă complexă rezolvând succesiv mai multe probleme simple identice. În acest caz, problema simplă constă în decuparea unei laturi a poligonului în raport cu una din marginile ferestrei, considerată o dreaptă (infinit de lungă). Menţionăm că algoritmul Shuterland-Hodgman original este de fapt mai general, realizând decuparea 3D a unui poligon oarecare în raport cu un alt poligon oarecare.

Algoritmul se derulează în patru etape succesive şi similare. În fiecare etapă se realizează decuparea întregului poligon în raport cu o singură margine.

În cadrul unei etape de decupare, se parcurg succesiv vârfurile poligonului, în ordinea de definiţie şi se examinează relaţia dintre punctul curent (C) şi punctul următor (U) în raport cu latura pentru care se face decuparea. Pe măsură ce se parcurg vârfurile poligonului, se construieşte o nouă listă de vârfuri.

Fereastra de vizualizare

Page 80: Manual ID Gpi

Grafică pentru calculator. Note de curs. Material în construcţie!Pentru lămuriri şi observaţii, a se contacta: [email protected]

Fig….Decuparea poligoanelor

Dreapta corespunzătoare laturii pentru care se face decuparea înparte planul de vizualizare în două regiuni: interioară şi exterioară. În consecinţă, sunt posibile următoarele 4 situaţii:

C U1)

Interior Interior

2)

Interior Exterior

3)

Exterior

Interior

4)

Exterior

Exterior

În funcţie de situaţia întâlnită, algoritmul face următoarele acţiuni, ilustrate în figura de mai jos:

1) Inserează U în noua listă de vârfuri.2) Găseşte intersecţia I a laturii CU cu dreapta de margine şi o inserează

în noua listă de vârfuri.3) Găseşte intersecţia I a laturii CU cu drapta de margine şi inserează în

noua listă de vârfuri pe I şi pe U.4) Nu inserează nimic.

Cele 4 etape de decupare a unui poligon concav sunt ilustrate în figura următoare.

U

C

Interior Exterior

Inserează U

Cazul 1)

C U

Inserează I

Cazul 2)

ExteriorInterior

I

CU

Inserează I şi U

Cazul 3)

ExteriorInterior

I

Nu inserează

Cazul 4)

C

Interior Exterior

U

Page 81: Manual ID Gpi

Grafică pentru calculator. Note de curs. Material în construcţie!Pentru lămuriri şi observaţii, a se contacta: [email protected]

Page 82: Manual ID Gpi

Grafică pentru calculator. Note de curs. Material în construcţie!Pentru lămuriri şi observaţii, a se contacta: [email protected]

În ordine lexicografică, sunt ilustrate: poligonul iniţial cu fereastra de vizualizare, decuparea la dreapta, decuparea jos,

decuparea la stânga şi decuparea sus (finală).

5.3. Decuparea cercurilor şi elipselor

Se face iniţial o evaluare globală, testând-se dacă dreptunghiul de încadrare al cercului sau elipsei este sau nu complet conţinut de fereastra de vizualizare. În caz afirmativ, nu este nevoie de decupare. În cazul negativ, se testează încluziunea cadranelor (sferturi de cerc). Cele complet incluse se pot trasa, nu se decupează. Cele parţial incluse se pot divide în continuare în octanţi (optimi de cerc). Octanţii complet incluşi se trasează. La cei parţial incluşi se poate proceda la determinarea intersecţiilor cu marginile prin metode analitice sau, mai simplu şi adesea chiar mai rapid în această fază, se testează individual poziţia fiecărui pixel la trasare, fiind marcaţi numai cei interiori. La elipse, descompunerea se face numai până la nivel de quadranţi.

5.4. Decuparea textelor

Se poate face în următoarele moduri: La nivel de pixel La nivel de literă (dacă este parţial inclusă se decupează toată

litera) La nivel de cuvânt (se decupează întreg cuvântul parţial

inclus)

6. Erori alias

Aspectul dreptelor şi curbelor pe ecrane cu rezoluţie slabă poate fi considerat inestetic, fiind perceptibilă reprezentarea prin puncte distincte. Liniile au un aspect rugos, grosimea este neuniformă. În contextul teoretic al prelucrării semnalelor, problema poate fi identificată ca una de subeşantionare.

Page 83: Manual ID Gpi

Grafică pentru calculator. Note de curs. Material în construcţie!Pentru lămuriri şi observaţii, a se contacta: [email protected]

Aici vom face doar o scurtă discuţie, mai degrabă pragmatică şi intuitivă asupra modalităţilor de abordare posibile. Menţionăm doar că termenul alias desemnează în limba engleză un nume echivalent. Asemeni spionilor ce-şi ascund identitatea reală sub un alias, componente de frecvenţe înalte din spectrul semnalului pot reapare cu frecvenţele modificate, determinând false componente de joasă frecvenţă şi de aici imposibilitatea reconstruirii corecte a semnalului, la o eşantionare insuficient de fină.

O primă soluţie posibilă constă în creşterea rezoluţiei. Este o soluţie costisitoare în sensul consumului de memorie şi creşterii timpului de trasare. În plus, nu rezolvă problema de fond, o face doar mai puţin acută.

O soluţie alternativă constă filtrarea imaginilor prin convoluţie cu un operator de tip trece jos (filtru de netezire). Asemenea filtre se vor prezenta într-un capitol special dedicat. Filtrarea transformă imaginea binară (cu numai două niveluri de gri, corespunzătorare albului şi negrului) într-o imagine cu nuanţe de gri.

O soluţie a cărei idee este foarte simplă, o reprezintă eşantionarea de suprafaţă neponderată, ilustrată în figură.

Intensitatea fiecărui pixel este proporţională cu procentul din suprafaţa sa ce se suprapune cu linia, considerată a avea o grosime finită, precizată. Prin intensitate înţelegem în contextul de faţă negativul ei. Astfel, intensităţii maxime, 255 îi corespunde negrul, 0. Valorii 100 îi corespunde 255 – 100 etc. Se obţine o redare cu tranziţii mai line a contururilor, cu un aspect mai natural, deşi aparent metoda antrenează o pierdere de rezoluţie prin îngroşarea de facto a traseului liniei. O redare şi mai realistă a liniilor se obţine prin eşantionare de suprafaţă ponderată. Metoda reprezintă o generalizere a ideii precedente, prin care intensitatea unui pixel depinde nu numai de procentul din aria sa suprapus cu traseul liniei ci şi de distanţa la mediana liniei. O interpretare posibilă a eşantionării neponderate ar fi următoarea. Pe fiecare pixel suprapunem centrat un cub cu latura egală cu cea a pixelului. Dacă linia intersectează pixelul, delimitează un subvolum al cubului (proporţional cu suprafaţa de intersecţie). Intensitatea pixelului este apoi stabilită proporţională cu subvolumul delimitat de linia ce se trasează. La eşantionarea de suprafaţă ponderată, figura centrată pe pixel nu mai este un cub. Poate fi înlocuită de exemplu cu un con, a cărui înalţime descreşte monoton de la centru spre margini, dar se poate utiliza orice alt corp cu proprietăţi similare (sferă, clopot gaussian etc.). Corpurile (ce stabilesc până la urmă dimensiunea pixelului) pot depăşi în dimensiuni pasul reţelei, ceea ce înseamnă o suprapunere a zonelor acoperite de pixeli vecini. Nimic nou în acest aranjament, ţinând cont de faptul că acest lucru se întâmplă curent la toate monitoarele bazate pe tuburi catodice, la care spotul de explorare are o alură aproximativ gaussiană şi acoperă semnificativ mai mult decât o linie de explorare.

Tehnicile anti alias sunt incorporate uzual direct în algoritmii de trasare.

7. Transformări geometrice

Page 84: Manual ID Gpi

Grafică pentru calculator. Note de curs. Material în construcţie!Pentru lămuriri şi observaţii, a se contacta: [email protected]

Transforrmările geometrice sunt folosite extensiv de programele de grafică pe calculator. Un program CAD pentru arhitecură, de exemplu, va folosi transformarea de translaţie pentru a poziţiona clădirile şi copacii la locul potrivit, rotaţia pentru a le expune din unghiul dorit de utilizator şi scalarea pentru a le reda la mărimea la care se văd din poziţia specificată de utilizator.

7.1. Transformări 2D

Putem translata un punct de coordonate (x,y) la locaţia dorită, (x*,y*), adunând diferenţele coordonatelor la cele iniţiale:

Definind vectorii coloană

Ecuaţia (7.1) poate fi rescrisă mai concis:

Un punct poate fi rescalat de-a lungul axelor prin multiplicarea coordonatelor cu coeficienţii adecvaţi:

Notând

Putem rescrie concis ecuaţia (7.4) în forma

De observat că, în timp ce translaţia nu afectează scara de redare, rescalarea afectează poziţia unui obiect pe ecran. De exemplu, având triunghiul definit prin vârfurile de coordonate (1,1), (2,4) şi (3,1), centrul de greutate este la ((1+2+3)/3,(1+4+1)/3) = (2,2). După rescalarea cu factorul sx=2 şi sy=2, coordonatele noi vor fi (2,2), (4,8), (6,2) şi centrul de greutate (4,4). Rotaţia cu ungiul α în sens trigonometric este descris de ecuaţiile:

În forma matricială,

7.2. Coordonate omogene şi reprezentări matriciale ale transformărilor 2D

Reprezentările matriciale introduse prezintă inconvenientul că translaţia este descrisă de o ecuaţie cu formă diferită de cele pentru scalare sau rotaţie. Acest neajuns poate fi înlăturat simplu prin introducerea coordonatelor

Page 85: Manual ID Gpi

Grafică pentru calculator. Note de curs. Material în construcţie!Pentru lămuriri şi observaţii, a se contacta: [email protected]

omogene. Coordonatele omogene 2D ale unui punct sunt de forma unui triplet (xh, yh, w). Variabila suplimentară nu este propriu-zis o coordonată, deşi se poate găsi şi o interpretare de acest tip. Rolul ei este de a permite manipularea convenabilă a calculelor cu transformări geometrice în forma matricială. Coordonatele carteziene se obţin pe baza coordonatelor omogene prin ecuaţiile:

Frecvent se alege w=1, împărţirea fiind astfel evitată, dar există situaţii în care este util ca w să poată lua valori diferite de 1.

În coordonate omogene, translaţia se poate scrie în forma:

Menţionăm că unii autori preferă să scrie ecuaţia de mai sus cu vectorul linie al coordonatelor premultiplicând matricea de transformare, în speţă matricea de translaţie. În acest caz matricea de translaţie are forma transpusă, pentru că (Tp)T = pT TT.

În coordonate omogene toate cele trei transformări introduse au forma generală a ecuaţiei (7.10). Ceea ce diferă este numai forma matricii din ecuaţia de tranformare. Pentru scalare, ecuaţia ia forma:

Respectiv pentru rotaţie forma

. Ce se întâmplă dacă facem două translaţii succesive cu (dx1, dy1) şi (dx2, dy2)? Din proprietăţile elementare ale operaţiilor cu vectori, anticipăm că rezultatul este echivalent cu o translaţie unică cu vectorul-sumă (dx1+ dx2, dy1+ dy2). Este uşor de verificat că:

(7.13)

Similar se comportă şi celelalte două transformări. Ele pot fi simplu concatenate, prin multiplicări succesive ale matricilor de transformare. Mai mult, o succesiune de transformări de tipul translaţie, urmată de rescalare, urmată de a doua translaţie, urmată de o rotaţie, se poate realiza prin multiplicare cu o singură matrice M = RT2ST1.

Page 86: Manual ID Gpi

Grafică pentru calculator. Note de curs. Material în construcţie!Pentru lămuriri şi observaţii, a se contacta: [email protected]

Un exemplu de folosire a proprietăţii de concatenare a transformărilor constă în rotaţia unei figuri în jurul unui punct arbitrar, P, nesituat în originea sistemului de coordonate. Transformarea se poate realiza prin succesiunea:1. Translaţie ce aduce P în origine2. Rotaţie3. Translaţie ce readuce P la coordonatele iniţialeDacă P are coordonatele (x,y) şi unghiul de rotaţie este α, succesiunea de transformări necesare are matricea de transformare

(7.14)

O abordare similară este posibilă pentru rescalarea unui obiect în jurul unui punct oarecare, de exemplu în jurul centrului de greutate al obiectului. Succesiunea de transformări este: translaţie, scalare, retranslaţie.

Este interesant de remarcat faptul că operaţiile de translaţie comută. La fel şi cele de scalare sau rotaţie. Mai mult, scalarea cu factor egal pe direcţiile x şi y comută cu rotaţia. Matricile implicate sunt comutative. În general însă, înmulţirea matricilor este numai asociativă, nu şi comutativă.

7.3. Transform ă ri geometrice 3D

Transformările geometrice 3D pot fi exprimate avantajos folosind coordonate omogene 3D. Acestea se obţin adăugînd vectorilor 2D o componentă suplimentară, corespunzătoare coordonatei z. Matricile de transformare devin matrici 4×4.

Există două sisteme de coordonate carteziene 3D, denumite de mâna stângă şi respectiv de mâna dreaptă. În cele ce urmează, vom folosi sistemul de mâna dreaptă.

Sistemul de coordonate demâna dreaptă

Sistemul de coordonate demâna stângă

z

y

x

z

y

x

Page 87: Manual ID Gpi

Grafică pentru calculator. Note de curs. Material în construcţie!Pentru lămuriri şi observaţii, a se contacta: [email protected]

În spaţiul 3D, rotaţiile sunt mai complexe decât în spaţiul 2D. Rotaţia 3D are loc în jurul unei axe. Pentru sistemul de mână dreaptă, prin convenţie, sensul de rotaţie pozitiv este cel trigonometric, privind dinspre axa de rotaţie spre origine. O rotaţie pozitivă de 90o transformă una din axe în cealaltă axă, în planul de rotaţie.

Translaţie 3D se poate scrie în forma:

Scalarea 3D are forma:

Matricea de rotaţie în jurul axei z (în planul x-y) are forma:

Matricea de rotaţie pentru axa x este:

Matricea de transformare pentru rotaţie în jurul axei y este:

Ultimele două se pot obţine din prima prin permutări circulare succesive în submatricea 3×3 din stânga sus.Rotaţia în jurul unei axe oarecare, definită de două puncte P1, P2, cu un unghi α se poate realiza, de exemplu, în următorii paşi:

translaţie ce aduce P1 în originea sistemului de coordonaterotaţie ce aduce P2 în planul xOzrotaţie în jurul axei y, ce aduce P2 pe axa z

Page 88: Manual ID Gpi

Grafică pentru calculator. Note de curs. Material în construcţie!Pentru lămuriri şi observaţii, a se contacta: [email protected]

rotaţia dorită cu unghiul α, în jurul axei zrotaţie în jurul axei y, pentru inversarea efectului rotaţiei de la punctul

3rotaţie în jurul axei x, pentru inversarea efectului rotaşiei de la punctul

2translaţie pentru a readuce P1 în poziţia iniţială.

Matricea de transformare se poate scrie în forma:M = TP1R-xR-yRzRyRxT-P1 .

7.4. Proiecţii

Redarea unui obiect grafic 3D pe ecran presupune o reprezentare 2D. Trecerea la reprezentarea 2D se poate realiza folosind o transformare de proiecţie. În grafica de calculator se folosesc mai multe tipuri de proiecţii. Există două categorii majore:

proiecţii paralele proiecţia de perspectivă

O proiecţie este definită de două elemente geometrice: planul de proiecţie punctul de proiecţie

Punctele imaginii proiectate se obţin ca intersecţii cu planul de proiecţie ale unor segmente de dreaptă ce unesc puncte ale obiectului cu punctul de proiecţie.

Proiecţiile paralele corespund reprezentărilor necesare în desenul tehnic ingineresc. În acest caz, punctul de proiecţie este situat la infinit. Dreptele de proiecţie sunt paralele între ele şi uzual paralele şi cu una din axele sistemului. Proiecţia de perspectivă corespunde vederii naturale şi generează imagini cu aspect mai realist. Obiectele îndepărtate au dimensiuni micşorate în conformitate cu efectul de perspectivă. Paralelismul dreptelor şi mărimile unghiurilor nu se păstrează, însă, ceea ce poate fi inconvenabil pentru reprezentările inginereşti.

Din punct de vedere practic, este mai simplu aranjamentul în care planul de proiecţie coincide cu unul din planurile determinate de o pereche de axe de coordonate. Uzual, este planul xOy. Proiecţia unui punct din lumea reală pe planul xOy este ilustrată în figura de mai jos.

pr=[xr yr zr]T

pi=[xi yi 0]T

xiyi

xryr x

z

y

f zr

Page 89: Manual ID Gpi

Grafică pentru calculator. Note de curs. Material în construcţie!Pentru lămuriri şi observaţii, a se contacta: [email protected]

,

(7.21)de unde rezultă imediat că:

.

(7.22)Similar, se găseşte şi pentru axa y că:

.

(7.23)Ecuaţiile transformării de perspectivă, deduse mai sus, ne permit calculul coordonatelor punctului din planul imagine în funcţie de coordonatele punctului din lumea reală care l-a generat. Pe de altă parte, zi=0, independent de coordonatele punctului din lumea reală. Din acest motiv, operaţia inversă, de reconstituire a coordonatelor punctului din lumea reală în funcţie de coordonatele punctului din imagine devine imposibilă. Constatarea nu este deloc surprinzătoare. Este clar că toate punctele situate pe dreapta de proiecţie ce uneşte punctul proiectat cu imaginea sa şi trece prin centrul optic se proiectează la aceleaşi coordonate din planul imagine. Ecuaţiile (7.21) şi (7.22) definesc două plane. Considerate ca un sistem, ele definesc intersecţia celor două plane care este chiar dreapta menţionată mai sus.

Aranjamentul din figură corespunde formării imaginii pe camera de luat vederi. Parametrul f este centrul optic echivalent. Pentru grafica de calculator se consideră adesea centrul de proiecţie situat în spatele planului de proiecţie şi ecuaţiile transformării de perspectivă iau forma:

Ecuaţiile de mai sus pot fi exprimate convenabil în formă matricială, folosind coordonate omogene:

Pe baza coordonatelor omogene, folosind ecuaţia (7.9), se pot obţine rapid coordonatele carteziene specificate de ecuaţia (7.24). Verificarea este lăsată în seama cititorului.

Page 90: Manual ID Gpi

Grafică pentru calculator. Note de curs. Material în construcţie!Pentru lămuriri şi observaţii, a se contacta: [email protected]

REPREZENTAREA CURBELOR ŞI A SUPRAFEŢELOR

1. Introducere

În grafica de calculator sunt necesare tehnici prin care utilizatorul poate genera curbe cu aspectul dorit. Exemple: aplicaţii AUTOCAD pentru proiectarea caroseriilor automobilelor, fuselaje de avion etc.Suntem în căutarea unor tehnici care:

pot genera curbe de o varietate cât mai mare utilizatorul poate transmite uşor calculatorului intenţiile sale să permită verificarea rapidă a apartenenţei unui punct la

curbă să faciliteze găsirea intersecţiei cu altă curbă

Ecuaţii implicite ex:

f(x,y)=x2+ y2- r2=0.(1)

nu sunt convenabile în forma respectivă pentru trasare. De exemplu, având coordonata curentă, x0, obţinem

(2)

În plus, pentru că există o foarte mare varietate de curbe posibile, vom avea nevoie de un număr imans de reprezentări (ecuaţii) diferite.

Reprezentări parametrice ex.

x=rcos(u),(3)y=rsin(u),

sunt mai convenabile pentru trasare. Mai mult, permit calculul derivatelor locale de o manieră mai directă şi mai intuitivă. Derivata întâi exprimă viteza de variaţie pe direcţia de creştere a parametrului, adică de-a lungul curbei:

(4)De exemplu, pentru u=0 avem valorile (0, r), ceea ce indică faptul că pentru moment x este constant şi y se schimbă, deci curba merge într-o direcţie verticală. Prin comparaţie, pentru forma implicită, avem

(5)

Page 91: Manual ID Gpi

Grafică pentru calculator. Note de curs. Material în construcţie!Pentru lămuriri şi observaţii, a se contacta: [email protected]

În punctul (r,0), corespunzător lui u=0, avem derivata , o valoare cu tratarea căreia calculatoarele au unele dificultăţi.

Forma de reprezentare implicită, deşi neadecvată pentru trasare, are proprietatea dezirabilă de a permite verificarea facilă a aparteneţei unui punct oarecare la curbă sau calculul intersecţiei curbelor. Reprezentarea parametrică are însă o serie de avantaje ce precumpănesc. Curbele de forme complexe sunt reprezentate în grafica de calculator ca o colecţie de segmente de curbă de complexitate moderată. Fiecare segment este reprezentat cu ajutorul unui polinom. Ansamblul este o curbă polinomială pe porţiuni. Uzual gradul polinomului de aproximare nu depăşeşte valoarea 3. Un polinom de gradul trei este o formă suficient de generală pentru putea asigura cu uşurinţă două cerinţe fundamentale: continuitatea de ordinul zero (punctele de capăt, în care se îmbină segmentele coincid) şi continuitatea de ordinul întâi (tangentele în punctele de îmbinare coincid). Condiţia a doua nu este întotdeauna necesară, dar este dorită de cele mai multe ori, astfel încât utilizatorul să nu perceapă îmbinările dintre segmente. De exemplu, poligonul permite o reprezentare a curbei liniară pe porţiuni, corespunzătoare unui poligon de ordinul întâi şi nu asigură continuitatea de ordinul doi.

Ecuaţiile parametrice ale unei curbe sunt de forma:

(6)În cazul particular al reprezentării prin polinoame de ordinul trei, ecuaţiile iau forma:

(7)Mai concis, folosind notaţiile vectoriale:

(8)şi

(9)putem rescrie ecuaţiile (7) în forma concisă

.

(10)

Page 92: Manual ID Gpi

Grafică pentru calculator. Note de curs. Material în construcţie!Pentru lămuriri şi observaţii, a se contacta: [email protected]

Orice polinom de grad n poate fi scris în forma din ecuaţiile (7). Polinomul este definit unic de coeficienţii săi, pi. Polinoamele de gradul n (ordinul n+1) formează un spaţiu vectorial, de dimensiunea n+1, în care u0, u1, u2, …, un reprezintă o bază (baza de putere). Funcţiile bi(u)=ui reprezintă funcţiile de bază, ce pot fi definite cu ajutorul veectorilor de bază. Pentru cazul particular de interes n=3, aceştia sunt:

Se poate vedea uşor că sunt liniar independenţi.Cu toate că baza de putere oferă cea mai simplă, directă şi

intuitivă modalitate de reprezentare a unui polinom, ea nu este unica bază pe care o putem folosi şi nici măcar cea mai convenabilă pentru grafica de calculator. Impedimentul principal constă în faptul că, pentru a se genera o curbă de forma dorită, este relativ dificil de anticipat valorile necesare ale coeficienţilor pi. Pentru o bază oarecare, ecuaţia (10) se poate rescrie în forma:

.

(11)

2. Proprietăţi utile ale bazelor Majoritatea bazelor utilizate curent în grafica de calculator posedă două proprietăţi importante:

proprietatea învelişului convex proprietatea invarianţei la transformările afine

Proprietatea învelişului convex

Ecuaţia (11) poate fi interpretată în felul următor: fiecare punct de pe curbă reprezintă o medie ponderată a punctelor pi, pe care le vom denumi puncte de control. Învelişul convex al punctelor de control este poligonul convex de arie minimă ce cuprinde toate punctele de control în interiorul sau pe conturul său. Este poligonul care s-ar obţine plasînd o badă elastică în jurul punctelor de control. Acesta include poligonul de control, al cărui interior este redat umbrit în (fig. 1).

Page 93: Manual ID Gpi

Grafică pentru calculator. Note de curs. Material în construcţie!Pentru lămuriri şi observaţii, a se contacta: [email protected]

fig. 1Proprietatea învelişului convex consă în faptul că forma generată se află în interiorul învelişului convex dacă:

(12)adică, funcţiile de bază au suma identic egală cu 1 şi sunt nenegative pe intervalul de definiţie (uzual u aparţine intervalului [0,1]).

Invarianţa le transformări afine

Transformările afine includ translaţia, rotaţia şi scalarea. Prprietatea invarianţei la transformările afine constă în faptul că figura generată de punctele de control care au suferit o transformare afină corespunde transformării afine a figurii corespunzătoare punctelor iniţiale. Notând transformarea afină cu Φ(), proprietatea enunţată presupune că

.

(13)Proprietatea este deoasebit de utilă în manipularea curbelor (de exemplu în animaţie), deoarece nu este necesar să efectuăm transformarea pentru fiecare punct al curbei ci numai pentru punctele de control, utilizând apoi rutinele obişnuite de trasare a curbei.

ObservaţieO curbă reprezentată parametric prin punctele ei de control poate fi redată cu o rezoluţie oricât de mare este necesară. Dacă aceeaşi curbă ar fi reprezentată ca o mini-imagine, rezoluţia ar fi limitată de formatul imaginii. Desigur există şi pentru imagini posibilitatea de creştere a rezoluţiei prin tehnici ce folosesc interpolarea, dar rezultatele pentru curbe nu sunt totdeauna cele aşteptate. Astfel, prin creşterea rezoluţiei, o linie cu grosime de un pixel poate deveni o linie cu grosime mai mare de un pixel.

3. Curbe Bézier Funcţiile de bază ale unei curbe Bézier de gradul n sunt:

(14)

Pentru gradul 3, utilizat cel mai frecvent în grafica de calculator, funcţiile de bază Bézier (fig. 2) sunt:

Page 94: Manual ID Gpi

Grafică pentru calculator. Note de curs. Material în construcţie!Pentru lămuriri şi observaţii, a se contacta: [email protected]

.

(15)O curbă Bézier de gradul trei se scrie:

(16)(0<u<1).

Care este avantajul faţă de formularea din ecuaţia (10)?

Fig. 2

În primul rând, observăm căr(0)=p0,

(17)r(1)=p3,

(18)deci curba Bézier trece prin primul şi prin ultimul punct de control.Pentru a vedea semnificaţiile celorlalte două puncte de control, derivăm curba în raport cu u:

.

(19)Rezultă că:r'(0)=3(p1─ p0),

(20)r'(1)=3(p3─ p2).

(21)Dezvoltarea funcţiei în serie Taylor în jurul punctului u=t se scrie:r (t+h)= r(t)+hr'(t),

(22)

1

1

b0,3

b1,3 b2,3

b3,3

Page 95: Manual ID Gpi

Grafică pentru calculator. Note de curs. Material în construcţie!Pentru lămuriri şi observaţii, a se contacta: [email protected]

ceea ce arată că r'(t) este direcţia tangentei în punctul u=t. Prin urmare, direcţia tangentei în punctul iniţial este 3(p1─ p0), adică direcţia dreptei ce uneşte primele două puncte de control (multiplicarea vectorului cu factorul 3 nu schimbă direcţia). Ecuaţia (22) mai sugerează faptul că, pe măsură ce punctul de control p1 este mai indepărtat de p0, curba înaintează mai mult pe direcţia tangentei în origine. O interpretare similară există şi pentru tangenta în punctul final.

Funcţiile Bézier respectă condiţiile (12), pentru că funcţiile de bază sunt de fapt termenii dezvoltării binomului ((1-u)+u)n. Prin urmare, ele posedă şi proprietatea învelişului convex.

În concluzie, punctele de control pot fi utilizate de o manieră simplă pentru asigurarea continuităţii de ordinul zero şi unu ale unei curbe compuse din segmente Bézier de ordinul trei. Ordinul trei este suficient de ridicat pentru a permite o mare varietate de curbe, în general nesimetrice. Totodată, curbele generate sunt netede, o proprietate dorită de cele mai multe ori.

4. Algoritmul Casteljau

Funcţiile de bază Bézier de un anumit ordin se pot obţine prin interpolarea liniară a funcţiilor de rang inferior, conform ecuaţiei:

,(23)

ceea ce se poate verifica uşor, folosind ecuaţia (14).În consecinţă, un punct de pe curbă, situat la coordonata u, poate fi generat recursiv, folosind următorul algoritm:

1. Punctele iniţiale sunt chiar punctele de control:,

i=0,1,...,n - r,r=0. // semnifică iteraţiau se iniţializează cu valoarea dorită, în intervalul 0-1.

2. Pentru r=1,2,...,n, se determină succesiv punctele:.

(24)Se observă că:

fiecare punct nou se obţine prin interpolarea liniară a două puncte consecutive din iteraţia precedentă

le fiecare iteraţie, numărul punctelor calculate se reduce cu unul

Interesant este faptul că ultimul punct care se obţine, este =r(u) şi este pe curbă! Cititorul este invitat să verifice afirmaţia pentru n=3, folosind calculul recursiv indicat de algoritm. O ilustrare grafică a algoritmului Casteljau pentru u=1/2 se dă în figura 3.

Page 96: Manual ID Gpi

Grafică pentru calculator. Note de curs. Material în construcţie!Pentru lămuriri şi observaţii, a se contacta: [email protected]

Fig. 3

Se poate demonstra că punctul final obţinut divide curba Bézier în două curbe Bézier (subdiviziune) ale căror puncte de control sunt chiar

, respectiv , ce au fost deja calculate. În consecinţă, este posibilă trasarea curbei folosind subdiviziunea recursivă. Costul de calcul pentru fiecare punct nou este de numai patru medii ponderate. Dacă se alege u=1/2, multiplicările pot fi evitate: împărţirea cu doi se poate implementa ca o operaţie de deplasare la dreapta cu o unitate( operatorul >>1 în limbajul C). Noile puncte de control ale celor două segmente se reduc la:

00p

01p

02p

03p

12p

11p

20p

30p

10p

21p

03

12

02

21

11

01

30

20

10

00

p

pp

ppp

pppp

Page 97: Manual ID Gpi

Grafică pentru calculator. Note de curs. Material în construcţie!Pentru lămuriri şi observaţii, a se contacta: [email protected]

Soluţia este extrem de convenabilă şi pentru o eventuală implementare hardware. Algoritmul se termină când învelişul convex al poligonului de control Bézier este suficient de plat pentru a se putea aproxima segmentul curent de curbă cu o dreaptă, care se trasează.

Algoritmul Casteljau este un punct forte major al reprezentării Bézier a curbelor. El are însă şi o importanţă teoretică. Pentru că interpolarea liniară este invariantă la transfomrarea afină, algoritmul demonstrează faptul că reprezentarea Bézier are proprietatea invarianţei la transformări afine.

5. Formularea matricială a curbelor Bézier

O convenţie alternativă pentru a specifica o curbă Bézier este cu ajutorul matricii Bézier şi a vectorilor bazei de putere:

.

(25)De precizatat, că vectorii r şi p sunt vectori-linie în formularea de mai sus. Funcţiile de bază Bézier cubice se obţin din produsul primelor două matrici în ecuaţia (25).

Formularea matricială a curbelor Bézier este utilă în următoarele două situaţii:

implementarea hardware la reprezentarea în altă bază conversia între baze

De ce să folosim şi alte baze? la reprezentarea Bézier modificarea unui singur punct de

control afectează alura întregii curbe reprezentarea Bézier nu are flexibilitatea necesară în

unele aplicaţii, de exemplu nu permite sinteza operativă a unor curbe cu colţuri (ca în figura 4)

Page 98: Manual ID Gpi

Grafică pentru calculator. Note de curs. Material în construcţie!Pentru lămuriri şi observaţii, a se contacta: [email protected]

Fig. 4

Tema

P1.Triunghiul cu vârfurile Vi(x,y)={V1(50,50), V2(60,50), V3 (52,60) }Se roteşte cu 30o in jurul lui V1. Calculaţi centroidul triunghiului rezultant.

P2.Găsiţi direcţia tangentei în punctul (4,1) la curba Bézier definită de punctele de control {(2,3), (5,9), (7,5), (4,1)}.

P3. Folosind algoritmul Casteliau, aflaţi coordonatele punctului corespunzător parametrului u = 0,4.

P4. Găsiţi rezultatul filtrului median 3x3 în centrul imaginii I.

P5. Găsiţi rezultatul filtrului binomial 3x3 în centrul imaginii I.

P6. Găsiţi histograma nivelurilor de gri pentru imaginea I. Pe baza histogramei, calculaţi nivelul mediu de gri.


Recommended