Teorie SPG

Curbe si suprafete de forma libera

Se folosesc pentru reprezentarea suprafelelor cu geometrie complexa.
Se pot modela in Geometry Shader.
Modelul geometric este o expresie matematica prin care se pot calcula puncte de pe
suprafata/curba.
Se folosesc algoritmi de redare care discretizeaza curba/suprafata:
- printr-o polilinie, in cazul curbei
- printr-o fateta plana, in cazul suprafetelor ( + calculul normalei la suprafata)

Cum sunt definite?

- Puncte din plan sau spatiu
- Tangente in punctele respective

Doua tipuri de curbe:

- de interpolare: punctele dete se afla pe curba
- de aproximare: punctele date controleaza forma curbei, nu apartin in mod necesar
curbei

Cum sunt modelate?

Ecuatii explicite - y=f(x)
- Dependente de sistemul de coordonate
- Nu pot reprezenta puncte multiple
- Rar folosite
Ecuatii implicite - ax + by + c = 0
- nu reflecta relatia dintre forma curbei si datele prin care este definita
- utile in cazurile de suprafete inchise
Curbele si suprafetele de forma libera sunt modelate prin ecuatii parametrice.
Curbele de forma libera se deosebesc prin forma lor geometrica (nu prin forma algebrica).

Forma geometrica a curbelor

p=U*M*G
U = [u^3, u^2, u, 1] - polinomul
M = matricea de baza
G = vectorul conditiilor geometrice pentru curba

Curbe Hermite
Date geometrice: punctele extreme si tangentele in punctele extreme (P0, P1, P0u, P1u)

Formele matriciale permit extinderea directa a modelelor curbelor la suprafeṭe.

Compunerea curbelor Hermite
Necesara pentru a obtine curbe care trec prin mai mult de 2 puncte si au proprietatile curbelor
Hermite.
Conditii de compunere:
- P1 coincide cu Q0
- cele doua curbe au aceeasi tangenta in punctul de jonctiune

Afisarea curbelor Hermite: se foloseste forma geometrica si se gliseaza u intre 0 si 1, cu pas

constant de discretizare.

Curbe Berzier
Date geometrice: o secventa de puncte, P0, P1,….,Pn – varfurile poligonului de control al
curbei, care determina forma si pozitia curbei
Curbele Bezier sunt curbe de aproximare.

Proprietati
- Curba trece numai prin primul si ultimul punct din secventa data si este tangenta in
primul punct la vectorul P0-P1 si in ultimul punct la vectorul Pn-1 - Pn
- Gradul polinomului care modeleaza curba depinde de numarul de puncte de control
- Forma curbei depinde de toate punctele de control
- Polinoamele Bernstein sunt functiile de ponderare (amestec - blending) pentru
curbele Bezier

Curba cubica Bezier = 4 puncte de control (folosit in practica)

Compunerea curbelor Bezier

Necesara pentru a obtine curbe cu mai mult de 4 puncte de control si au proprietatile curbelor
Bezier.
Conditii de compunere:
- Q0 coincide cu P3
- P2, P3, Q0, Q1 = coliniare
 -

Avantaje:
- Usor de definit în mod interactiv
- Curba este complet inchisa in figura convexă definita de punctele de control
(proprietatea de închidere convexă)
- Invarianţa afină: curba obtinuta prin aplicarea unei transformari afine punctelor sale se
poate obtine transformand numai punctele de control si apoi calculand punctele de pe
curba.
- Curbele Bezier de grad 2 sunt folosite in proiectarea caracterelor din fontul TrueType.
Dezavantaje:
- Numarul de puncte de control determina gradul polinomului de aproximare
- Functiile de amestec sunt nenule pe intreg intervalul de definitie →fiecare punct de pe
curba depinde de toate punctele de control (control global) → nu putem ajusta local
forma curbei

Curbe B-spline
Datele geometrice: o secventa de puncte care determina forma si pozitia curbei – varfurile
poligonului de control al curbei.
Sunt curbe de aproximare.

Elimina dezavantajele curbelor Bezier:

- Gradul polinomului care modeleaza o curba B-spline nu depinde de numarul punctelor
de control
- Punctele de pe o curba B-spline nu depind de toate punctele de control
- Deplasarea unui punct de control afecteaza forma curbei local (proprietatea de control
local)

O curba B-spline se obtine prin jonctiunea mai multor segmente de curba, fiecare segment fiind
determinat de:
- 3 puncte de control consecutive – B-spline de grad 2
- 4 puncte de control consecutive – B-spline de grad 3

Curba B-spline de grad 2 uniforma neperiodica

Prin adaugarea unui punct de control se adauga un nou segment la curba.

Curba B-spline de grad 2 uniforma periodica

Se poate utiliza o forma normalizata a ecuatiei parametrice.

Proprietatile curbelor B-spline uniforme periodice

- Puncte de control confundate
- Curbe inchise
- Inchidere convexa
- Invarianta afina

Curbe Nurbs
Sunt curbe B-spline neuniforme şi raţionale.
Datele geometrice: secventa de puncte care determina forma si pozitia curbei si ponderile
asociate punctelor de control (prin care poate fi controlata forma curbei)

Curbele B-spline ne-rationale sunt invariante numai la transformari afine, nu si la transformari

perspectiva.
Valorile wi asociate punctelor de control se numesc ponderi:
- Cand wi creste, curba se apropie de punctul de control
- Cand wi scade, curba se indeparteaza de punctul de control
- Daca wi= 0, punctul de control nu are efect asupra curbei

Avantaje:
- Ofera o forma matematica comuna pentru curbele analitice standard (de ex. curbe
conice) care nu pot fi bine definite prin curbe B-spline şi curbele de forma libera
- Ofera flexibilitate in proiectarea unei game largi de forme → sunt larg utilizate in
sistemele CAD/CAM
- Pot fi evaluate destul de rapid prin algoritmi numerici stabili si exacti
 - Sunt invariante fata de transformarile afine
- Sunt invariante fata de transformarea perspectiva

Curbe spline cubice de interpolare

Curba spline cubica de interpolare:
- Definită printr-o secvenṭă de puncte de control, P0 , P1 , P2 ,………Pn-1
- Trece prin toate punctele de control date
- Este modelata prin polinoame de grad 3 definite pe portiuni.

Datele geometrice:
- Secventa de puncte de control prin care trebuie sa treaca curba: P0 , P1 , P2
,………Pn-1
- Alte conditii impuse curbei (în functie de tipul curbei): - tangenta la curba în fiecare punct
de control: P’0 , P’1 , P’2 ,………P’n-1 - curbura în fiecare punct de control: P”0 , P”1 ,
P”2 ,………P”n-1

Curbe spline cubice Hermite

Datele geometrice:
- O secvenṭă de n puncte de control, P0 ,.., Pk , Pk+1 .., Pn-1
- Tangentele în cele n puncte
Fiecare segment de curbă este definit prin 2 puncte de control succesive si tangentele în
punctele respective: fiecare segment de curba este o curbă Hermite.

Curbe spline Catmull-Rom

Dezavantajul curbelor spline Hermite: proiectantul trebuie sa defineasca tangente în punctele
de control.
Curbele spline Catmull-Rom sunt definite numai prin punctele de control: tangenta in fiecare
punct intermediar Pk este determinata de punctul anterior Pk-1 si cel urmator Pk+1: vectorul
Pk-1 → Pk+1 determină direcṭia tangentei in Pk

Parametrul tau este numit “tension”; el determina cat de mult se “îndoaie” curba în punctele de
control; de regula este setat la 0.5.

Proprietati:
- Trece prin toate punctele de control si are control local.
 - Este relativ usor de calculat – tangentele se determina automat.
- Are continuitate geometrica de ordinul 1 in punctele de jonctiune (nu sunt discontinuitati
in directia tangentei)
- Nu are continuitate geometrica de ordinul 2 (derivata de ordinul 2 este interpolata liniar
pe fiecare segment)
- Nu are proprietatea de închidere convexa.

Suprafete de forma libera

- Suprafeţele de “baleiere spatiala”(Sweep surfaces ): obtinute prin rotaţia/ translaţia în
spaţiul 3D a unei drepte sau curbe.
- Suprafeţele de formă liberă (Freeform surfaces): definite prin puncte din spatiul 3D si
alte conditii geometrice atasate punctelor, sau folosind curbe de forma libera.

Suprafete de baleiere spatiala

C(u) – o curba in spatiu, numita “curba profil” (sau obiectul generator)
T(w) – o matrice de transformare a curbei C(u), care defineste regula de “baleiere” a spatiului
T(w) - include: rotatie sau/si translatie - poate sa includa scalare si forfecare
T(w): numai rotatie → suprafata de rotatie
T(w): numai translatie →suprafata de translatie

Suprafete de forma libera

Definite prin:
- “puncte de control” (puncte din spatiul 3D) si, in unele cazuri, alte conditii geometrice
asociate punctelor de control
- Exemple: suprafete Hermite, Bézier, B-spline, Nurbs
- curbe 3D de forma libera
- Exemple: suprafete riglate, suprafete cilindrice

Modelarea matematica: foloseste notiunea de “patch” (petic de suprafata). Un petic de

suprafata (patch) este o colectie de puncte marginita de 4 curbe.

Forma geometrica a suprafetelor

p(u, w) = U * M * S * Mt * Wt
U = [u^3, u^2, u, 1] - polinomul
W = [w^3, w^2, w, 1] - polinomul
M = matricea de baza
S = matricea conditiilor geometrice
Suprafete biliniare
O suprafaṭă biliniară este definită prin patru puncte situate arbitrar in spatiu, care se asociaza
colturilor patratului unitate din spatiul parametric (u,w)

Frontierele suprafetei biliniare sunt segmente de dreapta → peticele biliniare nu sunt adecvate
pentru modelarea suprafetelor 3D curbe, deoarece nu se poate asigura continuitatea
geometrica la jonctiunea a 2 petice biliniare.
Daca 2 dintre cele 4 puncte care definesc suprafata coincid se obtine un petic de suprafata
triunghiular.

Petice bicubice
Sunt suprafete de interpolare sau de aproximare.
Un petic bicubic este compus din 2 seturi (infinite) de curbe cubice (Hermite, Bezier, BSpline)
ortogonale in spatiul parametric.

Peticul bicubic Hermite

Definit prin:
- coordonatele colturilor suprafetei
- cei 8 vectori tangenti in cele 4 colturi
- cei 4 vectori de rasucire in cele 4 colturi

Compunerea a 2 petice Hermite:

- cu asigurarea continuitatii geometrice de ordin 1 pe frontiera de jonctiune: aceleasi
tangente in extremitatile frontierei de jonctiune
- cu asigurarea continuitatii geometrice de ordin 2 pe frontiera de jonctiune: aceiasi vectori
de rasucire in extremitatile frontierei de jonctiune

Dezavantajele peticelor Hermite:

- Greu de definit
- Numai 4 puncte de control

Peticul Ferguson
Este un caz particular de petic Hermite:

Dezavantaje
 - Daca vectorul de rasucire este = 0 intr-un colt, suprafata este plata in coltul respectiv.
- La jonctiunea dintre 2 F-petice se poate asigura numai continuitatea de ordin 1 →
suprafete insuficient de netede pentru unele aplicatii.

Peticul definit prin 16 puncte

Cele 16 puncte se pun in corespondenţă unei grile regulate din spatiul parametric.
Suprafaṭă de interpolare (contine toate punctele date).

Suprafete Bézier
Un petic de suprafaṭă Bézier, p(u,w), conṭine două familii de curbe Bézier ortogonale în spatiul
parametric: p(ui,w) şi p(u,wj), 0<=u, w <= 1
Peticul Bézier definit prin (m+1) x (n+1) puncte de control

Peticul bicubic Bezier

Este definit prin 4x4 puncte de control, care determina poliedrul de control al suprafetei.

Avantaje
- Este definit numai prin puncte
- Se pot alege colţurile suprafetei (4 dintre cele 16 puncte de control)
- Se pot defini tangentele la curbele marginitoare ale suprafetei, prin alegerea punctelor
de control care definesc frontierele
- Are proprietatea de închidere convexă ( peticul este conţinut în poliedrul convex
determinat de punctele de control)
- Are forma poliedrului de control
- Se poate actiona interactiv asupra formei sale prin deplasarea punctelor de control
- Are proprietatea de invarianţă afină
- Calculele necesare pentru divizarea suprafetei (în scopul vizualizarii) sunt simple

Dezavantaje
- Gradul polinomului de aproximare depinde de nr de puncte de control→în practica se
lucreaza cu petice bicubice → numai 4x4 puncte de control
- Punctele de control permit un control global al formei suprafetei (fiecare punct de pe
suprafata depinde de toate punctele de control)
- Dificil de controlat forma suprafeţei la frontiera de jonctiune a 2 petice bicubice: pentru a
fi menţinută continuitatea geometrică de ordin 1 vectorii tangenti in punctele fronierei
comune trebuie sa ramȃnă coliniari
Suprafete B-spline
Definite printr-o grila spatiala cu un numar arbitrar de puncte (minim 3x3 sau 4x4).

Proprietăṭi
- O suprafata B-spline este alcatuita din mai multe segmente de suprafata (bipatratice sau
bicubice) compuse cu continuitate geometrica de ordin 1.
- Fiecare segment de suprafata este determinat de 3x3 sau 4x4 puncte de control
- Proprietatile curbelor B-spline se extind la suprafetele B-spline:
- Invarianṭa fata de transformarile afine
- Proprietatea de control local
- Proprietatea de închidere convexă: o suprafaṭă B-spline este închisă în poliedrul
convex determinat de punctele de control

Suprafete riglate
O suprafata riglata este definita prin 2 curbe de forma libera.

Suprafete cilindrice
O suprafata cilindrica este definita printr-o curba de forma libera, g(u), si un vector, d[dx,dy,dz].
Suprafata se obtine prin translatia vectorului pe curba.

Divizarea curbelor si a suprafetelor de forma libera

Necesara pentru: calcule de intersectii, calcul puncte de pe curba, ş.a. Permite definirea
matematica a divizarii suprafetelor de forma libera.

O curba parametrica cubica: C(u) = U*M*G , este divizata in punctul de mijloc, u=0.5
Divizarea suprafetelor Bezier

Divizarea curbelor si a suprafetelor B-spline

Mai dificila, deoarece curbele B-spline nu sunt curbe intregi.
Alternativa de divizare a unui segment de curba cubica B-spline: Se converteste segmentul de
curba cubica B-spline in curba cubica Bezier
Analog, divizarea suprafetelor B-spline: conversie segment de petic B-spline in petic Bezier

Vizualizarea suprafetelor de forma libera

Afişare wireframe
- Suprafata este aproximata prin doua familii de curbe ortogonale in spatiul parametric
(curbe de u=const si curbe de w=const), care unesc varfurile unei grile regulate de
puncte de pe suprafaţă

-
Afişare prin feţe opace
- Suprafata este aproximata printr-o rețea de fețe care conecteaza varfurile unei grile
regulate de puncte de pe suprafaţă: p(ui , wj ), 0<= ui , wj <= 1, ui+1 = ui + du, wj+1 = wj
+ dw Fiecare faţa conecteaza 4 varfuri vecine ale grilei, este considerata plată şi
aproximată la afişare printr-un patrulater sau 2 triunghiuri.
- Suprafata este aproximata printr-o reţea de feţe plane obţinută prin divizarea suprafetei.

Afisarea unei suprafete Bezier printr-o retea de fatete plane

- Suprafata este descompusa în segmente de suprafaṭă care satisfac un criteriu de
planeitate

-
- Divizarea este recursiva, din fiecare divizare rezultand 4 segmente de suprafaṭă 4
 - Se verifica planeitatea fiecarui segment rezultat din divizarea curenta: daca un segment
nu este plan, se continua divizarea.
- Segmentele de suprafata plane sunt aproximate prin patrulatere sau triunghiuri plane,
care sunt trimise in banda grafica.

Divizarea este neuniforma: divizarea unui segment de suprafata se opreste daca satisface
criteriul de planeitate impus; se mai numeste divizare adaptiva.
- mai eficienta decat divizarea uniforma a spatiului parametric: pot rezulta mai putine
fatete
- pot sa apara defecte la frontiera a doua fațete care corespund la nivele diferite de
divizare

Criterii de planeitate pentru un petic de suprafata Bezier

1. Coplanaritatea varfurilor peticului (cu o anumita eroare/toleranta)
2. Coplanaritatea colturilor peticului si liniaritatea marginilor peticului

Redarea suprafetelor 3D folosind texturi

Pixelii imaginii trebuie pusi in corespondenta punctelor suprafetei 3D.
Elementele imaginii textura sunt culori si se numesc « texeli ».
Corespondenta dintre punctele suprafetei 3D si spatiul discret al texturii este realizata prin
intermediul unui spatiu continuu, (u,v), numit spatiul parametric al texturii, 0 <= u,v =< 1

Maparea directa
adresa texel, (i,j) → adresa (u,v) → punct de pe suprafaţa 3D (x,y,z) → adresa pixel, (xp, yp)
Nu este adecvata hardware-ului grafic actual.

Maparea inversa

Se calculeaza pentru fiecare fragment rezultat din rasterizarea suprafetei 3D texelul/texelii din
care se obtine culoarea textura.
- Fiecare fragment (xp,yp) are asociata adresa (u,v) corespunzatoare punctului de pe
suprafaţa 3D (x,y,z) care se afisaza în (xp,yp); adresa (u,v) → adresa (ir, jr) in spatiul
texturii, unde ir, jr sunt numere reale.
- Afiseaza fragmentul folosind culoarea obtinuta de la adresa (ir, jr) prin filtrarea texturii.

Obtinerea unei culori din imaginea textura in maparea inversa

ir, jr = numere reale, i, j = numere intregi => filtrarea texturii
2 posibilitati:
- Culoare = textura (i,j), unde (i,j) adresa cea mai apropiata de (ir,jr) in spatiul discret al
texturii; în OpenGL: GL_NEAREST
- Culoare = interpolare_biliniara (textura, ir, jr); în OpenGL: GL_LINEAR
Adresa texelului se obtine folosind functii de mapare inversa si « filtrarea texturii ».

Functii de mapare inversa

Definesc o corespondenta intre punctele suprafetei 3D si punctele spatiului (u,v) :
u = fu (x,y,z) ; v = fv (x,y,z)
In general, aceasta corespondenta este calculata pentru varfurile primitivelor rasterizate,
adresele (uf,vf) pentru fragmentele rezultate din rasterizare obtinandu-se prin interpolare intre
adresele (u,v) asociate varfurilor.
Exista functii de mapare inversa numai pentru suprafeţe definite intr-un spatiu parametric, (s,t)
a.î. se poate stabili o corespondenta (x,y,z) → (s,t) → (u,v)
Ele se numesc funcţii de mapare standard.

Functii de mapare standard

Maparea plana
u = su*x – ou
v = sv*y - ov
su, sv = factorii de scalare pentru aducerea in smaptiul [0, 1]
ou, ov = originea texturii pe suprafata
Se renunta la coordonata z: suprafata 3D devine plana

Maparea cilindrica
u = θ/2π
v=w
Maparea sferica
u = θ/2π
v = φ/ π

Aplicarea unei texturi pe o suprafata de forma libera

Orice suprafata de forma libera este definita intr-un spatiu parametric.

Maparea in 2 pasi
Este independenta de forma obiectului pe care se aplica textura.
Pentru calculul coordonatelor textura ale punctelor suprafetei texturate se foloseste o suprafata
intermediara pentru care exista o functie de mapare inversa.
Aplicarea texturii este descompusa in doua operatii, al caror efect este :
- mularea texturii pe suprafata intermediara;
- mularea suprafetei intermediare pe suprafata de texturat.
Maparea S
(mapare inversa): u = fu(xi, yi, zi) v = fv(xi, yi, zi)
Se folosesc 4 tipuri de suprafete intermediare (plan, sfera, cilindru, cub)
Alegerea tipului suprafetei intermediare este dependenta de forma obiectului pe care trebuie sa
fie aplicata textura.

Maparea O
(x,y,z) – un punct al suprafetei , pentru care se doreste calculul coordonatelor (u,v)
(xi, yi, zi) – punctul corespunzator lui (x,y,z) pe suprafata intermediara

Aplicarea texturilor pe fetele unei retele poligonale 3D

Pentru fiecare fragment rezultat din rasterizare se poate obtine o culoare din textură in 2
moduri:
- In fragment shader, se calculeaza coordonatele (uf,vf) corespunzatoare adresei
fragmentului în spatiul obiect (xf,yf,zf), folosind functii de mapare standard uf=fu(xf,yf,zf),
vf= fv(xf,yf,zf) sau maparea in 2 pasi.
- In fragment shader, se utilizeaza coordonatele (uf,vf) calculate de rasterizator prin
interpolarea coordonatelor (ui,vi) atasate varfurilor primitivei din care face parte
fragmentul.
Transparenta texturii
Imaginea textura poate avea o componenta aditionala, numita “canalul alfa”, prin care se poate
modela transparenta texturii.
Pentru a combina culoarea: glBlendFunc(..)

Filtrarea texturii
Textura trebuie sa fie mărită sau micşorată în funcṭie de dimensiunea în spaṭiul ecran a
suprafeṭei.
- Mărire (magnification): un texel contribuie la culoarea mai multor pixeli adiacenṭi
- Micşorare (minification): mai mulṭi texeli contribuie la culoarea unui pixel

Metoda “mip-mapping”
Necesară atunci când textura trebuie să fie micşorată.
Factorul de compresie a texturii intr-un pixel se calculeaza pe GPU pentru fiecare primitiva
grafica, dupa transformarea varfurilor în spatiul ecran, tinand cont de suprafata primitivei în
spatiul ecran si zona u-v folosita la texturarea sa.
Suprafata primitivei se aproximeaza printr-un patrat, la fel si zona u-v (→ aceeasi compresie pe
axele u si v)

m=50, n= 100 se aprox printr-un patrat cu latura de 100

Zona u_v se aproximeaza prin patratul incadrator cu latura de 0.5 Factorul de compresie a
texturii într-un pixel acoperit de primitivă: f=0.5/100 = 1/200
Daca rezolutia texturii este de 512x512 texeli → 512/200 = 2.56 → 2.56x2.56 = 6.55 texeli se
comprima într-un pixel.
Se calculeaza o piramida de imagini textură comprimate, fiecare nivel al piramidei
corespunzand unui factor de compresie al texturii → nr de factori de compresie este limitat la nr.
de niveluri ale piramidei!

Piramida mip-map
Calculul piramidei mip-map
Pentru o imagine textura de 512x512 texeli rezulta o piramida compusa din 10 niveluri (0, …, 9 -
512 = 2 ^ 9)
Nivelul k: aria(u-v)k corespunzatoare unui texel = 2 ^ 2(k - 9)
Factorul de compresie al imaginii textura de pe nivelul k este: dk = (aria (u-v)k )^0.5 = 2^(k - 9)

Piramida mip-mapping - Filtrarea texturii

Pentru calculul culorii unui fragment, se adreseaza piramida mip-map prin 3 coordonate:
(u, v, d):
d = nivelul piramidei
(u,v) prin care se calculeaza o culoare prin filtrare de pe un nivel al piramidei

Daca nu se vrea interpolare (tehnica nearest)

=> se adreseaza (u, v, d), cele mai apropiate coordonate intregi de (uf, vf, df)
Daca se vrea interpolare:
=> fie dk <= df <= dk+1
Folosind (uf, vf) - se determina o culoare din textura de pe nivelul k, Ck, Ck+1
=> C = Ck + dInterp ( Ck+1 – Ck ) , dInterp = 2^(9-k) * df - 1

Pentru o imagine textura color de 512x512 texeli, piramida se poate memora pe (1024 x1024)
octeti, cu fiecare canal de culoare pe un plan separat, astfel :

Metoda “mip-mapping” - Aprecieri

- da rezultate bune, chiar daca se bazeaza pe aproximari
- este implementata pe GPU
- Existenta piramidei de imagini simplifica filtrarea texturii in cazul micsorarii
- Elimina artefactele vizuale produse de accesarea aleatorie a texturii la micsorarea
suprafetei texturate.
- Creste performanta procesului de extragere a culorilor din textura, atunci cand un numar
mare de texeli trebuie folositi pentru un pixel.
- Consumul de memorie suplimentar pentru memorarea piramidei este de 33%.

Comprimare şi repetare
Coordonatele (u, v) în afara domeniului [0,1] rezultate in procesul de rasterizare sunt
transformate de GPU în coordonate 0<= uf, vf <=1.

Clamping (Comprimare)
Coordonatele u/v sunt transformate in uf/ vf astfel:
uf/ vf = min(max(0,u),1) / min(max(0,v),1)
Aplicarea acestei transformari are ca efect propagarea culorii de la marginea texturii de-a lungul
directiei in care coordonata textura este < 0 sau > 1.
Wrapping (Repetare)
Pentru accesarea texturii se calculeaza (uf,vf) cu formula:
uf/vf = u- [u] / v-[v]
unde [w] reprezinta cel mai mare intreg mai mic sau egal cu w.
Acest mod de transformare permite repetarea unei texturi, producand un efect periodic.

La utilizarea acestui mod este necesar ca laturile stanga/dreapta, respectiv sus/jos ale imaginii
textura se se potriveasca, astfel incat sa nu se observe marginile texturii.
Daca pentru una dintre coordonate se utilizeaza transformarea “comprimare” iar pentru cealalta
“repetare”, textura se numeste “cilindrica”.
Daca pentru ambele coordonate se utilizeaza modul “repetare”, textura se numeste “toroidala”.

Interpolarea coordonatelor textura

Interpolare liniara
Este efectuata de GPU, intre coordonatele textura ale varfurilor unei primitive, pentru obtinerea
coordonatelor textura ale unui fragment.
In interpolarea liniara, calculul coordonatelor (u,v) pentru fragmentele interioare poligonului este
similar calculului culorilor in modelul Gouraud:
- Pentru fragmentele de pe laturi - prin interpolare liniara intre valorile asociate varfurilor
- Pentru fiecare fragment interior – prin interpolare liniara intre valorile asociate
extremitatilor segmentului de linie interior poligonului
Pe liniile raster care trec prin varfuri apar discontinuitati ale texturii datorita schimbarii bruste a
lui du si dv atunci cand se trece printr-un varf.
Nu produce efectul de scalare specific proiectiei perspectiva
Interpolarea perspectiva
Este necesara numai pentru proiectia perspectiva; pentru proiectia paralela interp. liniara in
spatiul ecran corespunde interp. liniare in spatiul camerei.
Nu este necesara pentru linii si poligoane paralele cu planul de proiectie (planul “near”).
Poate fi aplicata tuturor atributelor atasate unui varf: culoare, normala, coord. textura.
Modul implicit de interpoare pe placile grafice moderne (cu versiunile actuale OpenGL) este cel
perspectiva

Simularea detaliilor fizice ale suprafetelor (“Bump Mapping”)

Calculul reflexiei luminii este bazat pe normala la suprafata.
Modificand normalele se pot obtine variatii mari ale intensitatii luminii reflectate in puncte vecine,
care ar corespunde unor variatii mari ale geometriei suprafetei (exemplu, sfera din stanga)

Modificarea normalei intr-un punct al unei suprafete este definita printr-o “functie de perturbare”.
Fie Q(u,w) ecuatia parametrica a suprafetei

Suprafata perturbata:
P(u,w) este functia de perturbare
Se poate folosi ca functie de perturbare orice functie derivabila.
Functia de perturbare poate fi aproximata printr-un tablou bi-dimensional adresat prin valori
discrete (u,v); valorile functiei pentru valori intermediare ale lui u sau v se obtin prin interpolare
bi-liniara iar derivatele partiale se aproximeaza prin diferente finite.
Efectul texturii este invariant fata de translatie dar nu si fata de scalarea obiectului pe care se
aplica: deoarece textura nu se modifica la scalarea suprafetei, apare efectul de aplatisare a
texturii.
Pentru ameliorarea efectului de aplatisare , Blinn a sugerat urmatoarea corectie:

Implementarea moderna a metodei Bump mapping foloseste hărṭi de normale

Harti de normale
O harta de normale (normal map) este o imagine textura ale carei elemente sunt vectori 3D,
folositi ca normale in calculul culorii fragmentelor.
Hartile de normale se pot obtine in 2 moduri:
- Se calculeaza normalele la modelul detaliat si se memoreaza intr-o textura, apoi se
simplifica geometria modelului.
 - Folosind hărṭi de înaltimi

Codificarea normalelor in textura

Componentele unui vector normal normalizat: -1<= nx,ny,nz <=1
Componentele culorii dintr-un texel RGB: 0<= R,G,B <= 1
Codificarea normalelor in textura: RGB (nx,ny,nz) = (nx,ny,nz) / 2 + (0.5,0.5,0.5)
Conversia culoare texel → vector normal: N(R,G,B) = 2*(R,G,B) – (1,1,1)
Normalele dintr-o textura sunt raportate la “spaṭiul tangent”, definit pentru fiecare faṭă a
mesh-ului pe care se aplica.

Spatiul tangent al unei feṭe este definit printr-un sistem de coordonate 3D, determinat de 3
vectori ortogonali:
- Vectorul normal atasat unui vârf al feṭei, N, care da directia axei OZ a spatiului tangent
- Un vector tangent la suprafaṭă în vârf, T, care da directia axei OX a spatiului tangent
- Vectorul obtinut ca produs vectorial între N şi T, numit vectorul bitangent, B

Vectorii N, T si B se asociaza fiecarui varf al mesh-ului care aproximeaza suprafata texturata. Ei

sunt raportati la spatiul obiect (in care sunt reprezentate coordonatele varfurilor). - Prin aplicarea
transformarii de modelare, (T,B,N) sunt transformati in sistemul coordonatelor globale (spatiul
scenei 3D).
Pentru calculul luminii reflectate (in fragment shader) este necesar ca vectorii V (directia
observatorului), L (directia sursei de lumina) si N sa fie exprimati in acelasi sistem de
coordonate.

Harti de inaltimi
Intr-o imagine harta de inaltimi (hight map), fiecare pixel reprezinta inaltimea unui punct de pe o
suprafata. In implementarea metodei Bump mapping, hartile de inaltimi se folosesc pt
generarea hartilor de normale.

Fie HI harta de inaltimi.

Cei doi vectori tangenti intr-un punct (x,y) se aproximeaza prin diferente finite astfel:
H1= (1, 0, Hx), Hx = HI[x+1, y] - HI[x, y] – variatia inaltimii pe directia x
H2 = (0, 1, Hy), Hy = HI[x, y+1] - HI[x, y] – variatia inaltimii pe directia y
Normala normalizata in punctul (x,y) este : Nu = H1xH2/|H1xH2|

Parallax mapping
Este o imbunatatire a metodei Normal Mapping prin marirea efectului de adancime pe suprafete
cum ar fi pereti din caramida sau piatra.
Metoda nu afecteaza performanta
Metoda foloseste o textura harta de înalṭimi, dar nu modifica coordonatele fragmentelor
suprafetei pe care se aplica textura, ci creaza iluzia ca fragmentele se afla la diferite inaltimi
alterand coordonatele textura ale fragmentelor in functie de directia vederii in fiecare fragment si
înaltimea din harta de înaltimi pentru acel fragment.

Folosind in A coord. textura ale lui B se creaza efectul ca observatorul priveste catre B.
Pentru aceasta maparea parallax scaleaza lungimea vectorului V a.i. sa fie egala cu H(A).
Maparea parallax se face in spatiul tangent.
Folosirea unei hărṭi de normale obtinuta din harta de inaltimi asigura o iluminare coerenta cu
variatia inaltimilor
In parallax mapping se prefera sa se foloseasca inversa hartii de inaltimi, fiind mai usor de creat
iluzia de denivelari pe adancime decat pe inaltime pe o suprafata plata

Maparea hartii mediului inconjurator (“Environment mapping” )

Ideea: de a simula ceea ce vede un observator pe suprafetele obiectelor din scena 3D daca
acestea au suprafete care reflecta/refracta lumina, atunci cand se deplaseaza in scena 3D.
Se foloseste ca imagine textură imaginea mediului inconjurator obiectului/obiectelor pe care
este redata textura
Imaginea redata pe suprafata obiectului texturat este dependenta de pozitia observatorului, căci
raza reflectata/refractata este calculata in functie de pozitia observatorului si normala la
suprafata.

Se calculeaza o singura raza reflectata/ refractata pentru fiecare fragment.

- Normala fragmentului (obtinuta prin interpolare in procesul de rasterizare) trebuie sa fie
raportata la sistemul coordonatelor globale.
- Se calculeaza raza reflectata/ refractata folosind normala fragmentului si pozitia
observatorului (tot in coord. globale)
- Se calculeaza intersectia razei cu suprafata intermediara pe care se aplica harta
mediului inconjurator (cubul sau sfera).
- Se calculeaza coordonatele textura care determina culoarea fragmentului, folosind
coordonatele punctului de intersectie si functia de mapare inversa ( sferica sau plana).
Metoda presupune ca mediul inconjurator al unui obiect se afla la distanta infinita de el si deci
poate fi reprezentat ca o imagine omni-directionala. Aceasta deoarece harta mediului este
accesata printr-un singur vector 3D.

Calculul razei reflectate/rafractate pentru un fragment

Se folosesc: normala fragmentului si pozitia observatorului, în coordonate globale.
Vectorul reflectat (R) sau cel transmis (T) este intersectat cu suprafata intermediara.

Limitarile metodei
- In mod ideal, fiecare obiect dintr-o scena trebuie sa aiba propria harta textura a mediului
inconjurator. In practica, mai multe obiecte pot partaja aceeasi harta a mediului
inconjurator, fara ca acest aspect sa se observe.
- Harta textura ar trebui sa fie modificata atunci cand obiectele scenei isi schimba pozitia
sau cand un obiect isi schimba semnificativ pozitia relativ la mediu. In practica, se obtin
reflexii foarte bune cu harti ale mediului statice.
- Obiectele pot reflecta numai mediul codificat prin harta textura. Nu pot reflecta parti
proprii. De aceea, metoda este adecvata pentru obiecte convexe sau aproape convexe.
- Nu pot fi redate reflexii multiple: doua obiecte stralucitoare care se reflecta unul pe
celalalt.

Cube Environment Mapping

Se folosesc 6 imagini textura care se asociaza feţelor cubului unitate centrat in originea sist de
coord globale
Cubul se foloseste ca suprafata intermediara pentru maparea in 2 pasi a imaginii mediului
inconjurator pe obictele scenei 3D.
Modelarea si animatia structurilor articulate
O structura articulata este alcatuita din:
- obiecte rigide, numite legături
- jonctiuni, in care sunt conectate obiectele rigide

Compunerea unei structuri articulate

Structura articulata este compusa aplicând fiecarui obiect component o transformare din
sistemul său de coordonate locale in sistemul de coordonate locale al obiectului la care se
conecteaza.
Transformarea este atasata arcului din arbore care conecteaza nodul obiectului conectat cu
nodul său parinte (nodul obiectului la care se conecteaza).
Transformarile de compunere a structurii articulate nu se modifica in timpul animatiei!

Animarea structurii articulate

In timpul animatiei, fiecare legatura se poate roti in articulatia care o conecteaza de legatura
aflata pe nivelul ierarhic imediat superior.
Aceasta rotatie este cea de-a 2-a transformare atasata arcului care conecteaza nodul
corespunzator legaturii rotite de nodul sau parinte.
Fiecarui nod ii sunt asociate datele care descriu geometria legaturii (obiectului rigid) pe care o
reprezinta

Pozitia intregii structuri articulate in sistemul coordonatelor globale, la un moment dat, este
definita printr-o transformare aplicata nodului radacina: T0.
Transformarea nodului radacina, T0, este atasată arcului radacina: schimbarea acestei
transformari va repozitiona rigid intreaga structura, in sistemul coordonatelor globale.
Pozitiile celorlalte noduri ale ierarhiei sunt localizate relativ la pozitia nodului radacina.

Un set complet de parametri care redau structura articulata intr-o pozitie spatiala, se numeste
poză.
O poză se reprezintă printr-un vector poză, care contine cate un parametru pentru fiecare
joncṭiune (arc din arborele structurii articulate): unghiul de rotaṭie al unei legaturi în joncṭiunea
cu legatura parinte.
Animatorul defineste un set de “poze cheie”. Cadrele intermediare dintre cadrele cheie se obtin
prin interpolarea parametrilor ataşaṭi jonctiunilor.
Exista 2 metode de calcul al pozelor cheie:
- Cinematica directa
- Cinematica inversa

Cinematica directa (Forward kinematics)

= Pozitionarea unei structuri articulate prin specificarea parametrilor atasati tuturor arcelor
(jonctiunilor)
Pentru a calcula o anumita pozitie si orientare pentru un obiect frunza al arborelui intr-un cadru
cheie, animatorul trebuie sa calculeze unghiurile de rotatie atasate tuturor arcelor de la nodul
frunza la radacina.
=> extrem de obositor si dificil

Cinematica inversa (Inverse kinematics)

Cinematica inversa permite animatorului sa se concentreze numai pe conditiile pe care trebuie
sa le indeplineasca obiectele din frunzele arborelui.
Animatorul defineste:
- poza initiala
- pentru fiecare obiect frunza din structura ierarhica (“end effector”)
- pozitia si orientarea sa în poza finala
Sistemul de animatie trebuie sa calculeze valorile tuturor arcelor (jonctiunilor), de la nodul
frunza pana la nodul radacina, astfel incat sa se obtina configuratia dorita pentru obiectul
frunza.
Problema calculului vectorului “poza finala”poate avea:
- zero solutii (sistemul este supra-constrans)
- o solutie
- mai multe solutii (sistemul este sub-constrans)
Solutia poate fi:
- analitica, daca problema este simpla (lanturi foarte scurte)
- numerica, iterativa – in caz contrar

Modelarea si animatia personajelor

Animatia reprezentarii prin mesh

Personajul este reprezentat printr-o plasa poligonala 3D.
Animatia personajului consta in deformarea plasei, fiecarui cadru imagine corespunzandu-i o
“poza” (ipostaza) a personajului.
Numarul de varfuri ale plasei si conectivitatea lor nu se modifica de la o poza la alta, ci doar
pozitiile varfurilor.
Avantajul metodei:
- Animatorul poate decide cat de apropiat de realitate sa fie modelul personajului.
Teoretic, cu suficiente poligoane se poate obtine orice.
Dezavantajele metodei:
- Trebuie creat cate un model 3D (poza) pentru fiecare cadru cheie.
- Consumul de memorie creste odata cu numarul de poligoane ale modelului.
- Pozele din cadrele cheie trebuie sa fie foarte apropiate pentru a se obtine rezultate
bune.
- Animatiile produse sunt greu de refolosit, ceea ce duce la costuri mari .
 - Calitatea animatiei depinde de inspiratia si talentul animatorului. Spre deosebire de o
animatie 2D, o animatie 3D este mult mai greu de conceput: trebuie sa arate cat mai
natural din orice pozitie 3D ar fi privita.
- Volumul mare de munca necesar pentru a produce o animatie si implicarea puternica a
omului ii limiteaza aplicatiile.
- Nu se pot crea animatii care sa se poata adapta unor conditii cunoscute de-abia la
rulare. Pentru aceasta ar fi necesar sa se creeze un numar foarte mare de animatii.
Metoda poate fi implementata pe GPU.

Animatia bazata pe schelet

Personajul este reprezentat prin doua sau mai multe “straturi”( reprezentare “multistrat”):
- Schelet + piele
- Schelet + muschi + piele
Animatia se transmite de la schelet catre straturile superioare.

Skinning
Pielea este reprezentata printr-un obiect “mesh”, asociat unui schelet.
Scheletul este doar un mecanism de control al deformarii obiectului mesh atasat.
Un os poate fi reprezentat printr-o locatie 3D, care corespunde unei articulatii, si un vector, care
da lungimea si directia sa.
“Pielea” este atasata unui schelet in sistemul de animatie, iar operatia se numeste “rigging”:
fiecare varf al mesh-ului piele este asociat unuia sau mai multor oase
Pentru animatie, fiecare varf al « pielii » este transformat pe baza transformarilor oaselor
asociate. Un schelet poate fi folosit sau adaptat pentru mai multe mesh-uri.
Transformarea unui varf al mesh-ului poate fi influentata de unul sau mai multe oase. Numarul
de oase la care este atasat un varf este limitat la 4 (practic, nu este nevoie de mai multe)

Fiecare os contribuie la transformarea unui varf cu o anumita pondere.

wij - ponderea asociata varfului Vi pentru fiecare Os_j
daca wij = 1 → varful Vi este atasat rigid osului Os_j
Este necesar ca:
- Ponderile sa fie pozitive
- Suma ponderilor wij pentru un varf sa fie egala cu 1.

Legarea pielii la schelet

Plasa poligonala este mai intai “legata” de ierarhia de oase, rezultand “poza de legare”, numita
si “poza de referinta”.
Legarea pielii la oase se face intr-o pozitie initiala a scheletului
Fiecare os al scheletului este definit in propriul sau sistem de coordonate locale. Pentru legarea
unui os la piele, i se aplica o transformare, numita transformare de legare a osului la piele:
transformare din sistemul de coordonate local al osului in sistemul de coordonate al pielii
nedeformate (poza de legare). Tos_i - matricea transformarii de legare a osului i la piele -
concateneaza toate transformarile (de compunere) atasate arcelor scheletului de la nodul i pana
la radacina.
Pe parcursul animatiei, fiecare poză a structurii articulate de oase este reprezentata prin
matricile de transformare a oaselor din sistemele lor de coordonate locale in sistemul
coordonatelor globale (calculate prin cinematica directa sau inversa). Aceste matrici se folosesc
la transformarea varfurilor plasei care modeleaza pielea.

Animatia

Odata cu varfurile plasei trebuie transformate si normalele in varfuri, necesare in calculele de

iluminare.

Implementarea animatiei folosind numai GPU

- Aplicatia calculeaza si memoreaza coordonatele varfurilor plasei si normalele in varfuri,
raportate la sistemul de coordonate local al fiecarui os
- Pe parcursul animatiei (pentru fiecare cadru), aplicatia transmite la GPU reprezentarile
varfurilor (Vk i ) si ale normalelor (Nk i ) in cele 1,2,3 sau 4 sisteme de coordonate locale
ale oaselor de care depinde fiecare varf.

Implementarea animatiei folosind CPU + GPU

- Aplicatia calculeaza si memoreaza:
- Coordonatele varfurilor plasei in spatiul de modelare, Vk
- Normalele varfurilor plasei in spatiul de modelare, Nk
- Pentru fiecare varf, matricea Tos_i ^ -1 prin care varful este transformat in
sistemul de coordonate locale al osului i.
- Pe parcursul animatiei (pentru fiecare cadru):
- aplicatia (CPU) calculeaza matricile Ti = Aos_i • Tos_i ^ -1 care vor fi utilizate la
transformarea varfurilor legate la osul i
- transmite la GPU (pentru Vertex Shader) varfurile si normalele in spatiul de
modelare (Vk, Nk) precum si matricile Ti.
Animatia corpurilor rigide

Obiect rigid
Obiect care nu-si schimba forma, nici chiar daca asupra lui actioneaza o forta mare. Spatiul unui
obiect rigid nu se intersecteaza niciodata cu spatiul unui alt obiect rigid.
Animatia unui obiect rigid - Se poate reduce la o modificare in timp a pozitiei si orientarii in
spatiu a fiecarei parti rigide din care este compus. Modificarea are la baza interpolarea pozitiilor
si a orientarilor între cadre cheie.

Transformarea varfurilor obiectului

In timpul animatiei, punctul de referinta al obiectului se deplaseaza pe traiectoria miscarii.
Pentru fiecare cadru cheie al animatiei, animatorul specifica:
- Pozitia punctului de referinta al obiectului
- Orientarea obiectului/Orientarea fiecarei legaturi rigide a structurii articulate in jonctiunea
cu legatura parinte
Pentru fiecare cadru intermediar dintre 2 cadre cheie:
- Se calculeaza pozitia punctului de referinta pe curba traiectorie
- Se calculeaza noile coordonate ale varfurilor obiectului, folosind:
- Pozitia punctului de referinta
- Orientarea/orientarile corespunzatoare cadrului, obtinute prin interpolarea
orientarilor celor 2 cadre cheie
Pentru fiecare cadru al animatiei, se transforma coordonatele varfurilor obiectului din sistemul
coordonatelor locale in sistemul coordonatelor globale (al scenei 3D)

Specificarea animatiei
Intre 2 cadre succesive, se pot modifica valorile mai multor parametri:
- Coordonatele pozitiei punctului de referinṭă al obiectului
- Unghiul dintre 2 componente conectate ale obiectului (simularea structurilor articulate)
- Transparenta
- Culoarea sursei de lumina
- Orice alt atribut utilizat in modelarea si redarea elementelor grafice
Problema specificarii animatiei poate fi descompusa in 3 subprobleme:
- Specificarea traiectoriei deplasarii: calea pe care se deplaseaza punctul de referinta al
obiectului.
- Specificarea caracteristicilor miscarii: viteza, acceleratia, aspecte temporale ale
deplasarii obiectului pe traiectoria specificata.
- Specificarea orientarii obiectului in timpul animatiei

Specificarea traiectoriei deplasarii

Curba este 3D→ dificultati de percepere a tri-dimensionalitatii; solutii:
- redarea simultana a proiectiilor traiectoriei in planele principale;
- vizualizarea curbei traiectorie in scena 3D impreuna cu linii verticale de la ea in planul
XOY.
Cazul general: curba traiectorie este o curba parametrica 3D, Q(u) = (X(u), Y(u), Z(u)):
- o curba de interpolare: Hermite(necesita tangente), Catmull-Rom (preferata-numai pozitii
de pe curba)
- o curba de aproximare (Bezier, B-spline)
Continuitatea: apare in cazul curbelor compuse: Hermite, Bezier; este suficienta continuitatea
geometrica de ordinul 1 (coliniaritatea tangentelor in punctul de jonctiune).

Specificarea caracteristicilor mişcării

Cu cât numărul de cadre intermediare este mai mare cu atât viteza de deplasare este mai mica

Deplasare cu viteza constanta

Curba “ease-in, ease-out” : acelerare lina la plecare, scadere lina a acceleratiei la oprire

Avantajele metodei:
- Curbele de viteza sunt independente de traiectorie
- Animatorul poate specifica separat curba traiectorie si curba de viteza.
- Specificarea este usor de efectuat de animator: nu necesita cunostinte de Informatica.
- Exista curbe de viteza tipice pentru anumite caracteristici ale deplasarii: pot fi memorate
pentru a fi reutilizate cu diferite traiectorii.
Probleme de calcul
- Curbele de viteza sunt curbe de forma libera 2D: V(u) = (S(u), T(u)).
- Trebuie calculata pozitia pe traiectorie a obiectului la fiecare moment de timp al animatiei

Corelatia curbelor traiectorie si viteza

Curba de viteza este parametrizata in functie de u, nu de t!
Curba traiectorie este parametrizata in functie de u, nu de s - lungimea arcului de curba parcurs
pana la momentul t!

Corelatia curbelor traiectorie si viteza

Pentru fiecare moment de timp, ti, tinitial <= ti <= tfinal
- se determina ui, a.i. T(ui) = ti
- se calculeaza si = S(ui), lungimea arcului de curba parcurs pana la momentul ti
 - se determina uk, astfel incat lungimea arcului de curba de la Q(0) la Q(uk) = si
- se calculeaza pozitia pe curba traiectorie la momentul ti: X(uk), Y(uk), Z(uk)

Calculul lungimii arcului de curba parcurs pana la un moment de timp dat

O metoda aproximativa:
- Se calculeaza si se memoreaza intr-o tabela pozitii succesive de pe curba V(u),
esantionand u cu pas mic
Pentru fiecare moment de timp ti al animatiei:
- Se cauta in tabelă tk, tk+1, astfel incat: tk< ti < tk+1
- Se aproximeaza si interpoland liniar intre sk si sk+1

Posibilitati de reprezentare a orientarii

Rotatia in jurul axelor sistemului de coordonate globale

Transformarea care se aplica varfurilor obiectului pentru obtinerea unui cadru consta din una
sau mai multe rotatii in jurului axelor sistemului de coordonate locale, urmate de o translatie:
este o transformare rigida.
Rotatia corespunzatoare unui cadru= produsul matricilor de rotatie in jurul celor 3 axe:
R = Rx(ux)*Ry(uy)*Rz(uz)
Avantajele reprezentarii rotatiilor prin matrici de rotatie
- Usurinta in folosire
- Rotatia poate fi combinata cu translatia prin inmultirea matricilor, si cu alte transformari,
atunci cand transformarea totala este nerigida.
Dezavantaje ale reprezentarii prin matrici de rotatie
- Ordinea rotatiilor in jurul axelor este importanta. Rotatiile nu sunt independente.
- Pentru animator este greu de determinat unghiul de rotatie in jurul unei axe, dupa o
rotatie in jurul altei axe.
- Efectul “Gimbal Lock”: are loc atunci cand o serie de transformari de rotatie duce la
pierderea unui grad de libertate de rotatie.
- Interpolarea intre doua orientari cheie nu este unica

Rotatia in jurul axelor unui sistem de coordonate local

Orientarea pentru un cadru este specificata printr-o matrice care transforma sistemul de
coordonate locale (x,y,z) al obiectului in cel corespunzator cadrului (u,v,w). Aceasta include
rotatii in jurul axelor x,y,z: metoda are aceleasi dezavantaje ca rotatia raportata la un sistem de
coord fix

Deplasamentul unghiular
O rotatie poate fi reprezentata in mod unic printr-o axa si un unghi R(ф, N), unde N este axa de
rotatie (un vector 3D) si ф unghiul de rotatie in jurul axei N. O orientare se poate reprezenta
printr-o axa (diferita de la un cadru la altul) si un unghi de rotatie in jurul axei respective.
Interpolarea reprezentarii prin axa si unghi
Fie: - A1 si A2 axele de rotatie pentru 2 cadre cheie succesive - axa Ak, pentru cadrul
intermediar k, interpolata intre A1 si A2.
Axa Ak se poate obtine rotind A1 catre A2 in jurul axei B, cu unghiul k*θ
Unghiul φk, pentru cadrul k, se obtine prin interpolare liniara intre unghiurile φ1 si φ2

Rotatia unui varf in jurul unei axe

r : vectorul pozitie al unui varf, P, al obiectului animat, in sist. de coordonate locale
Rr: vectorul pozitie al varfului rotit, P’, cu unghiul φ in jurul axei N, |N|=1

Quaternioni
Notiune matematica introdusa in incercarea de a extinde planul numerelor complexe, pentru a
defini un volum complex.
A numit numarul q = a + bi + cj + dk ‘quaternion’ cu proprietatea:
i^2= j^2 = k^2 = -1, ij = k; ji = -k
Notatia prescurtata: q = (s,v) = s + v_x i + v_y j + v_z k,
- s este partea scalara (s – numar real)
- v partea vectoriala (i,j,k) pot fi considerati ca versorii unui sistem de coord carteziene 3D
In grafica se folosesc cuaternioni pentru a reprezenta orientarea prin axa si deplasament
unghiular.
Este posibila:
- Interpolarea unica intre orientarea initiala si cea finala, reprezentate prin cuaternioni
- Concatenarea mai multor rotatii pentru a defini o transformare compusa prin cuaternioni
Partea vectoriala a cuaternionului este similara cu expresia vectorului r rotit in jurul axei N
(deplasamentul unghiular), cu diferenta ca unghiul este 2ф in loc de ф
Avantajele utilizarii cuaternionilor pentru reprezentarea orientarii:
- Compunerea rotatiilor se obtine prin inmultirea cuaternionilor
- interpolare unica intre 2 orientari reprezentate prin cuaternioni
Dezavantajul cuaternionilor in specificarea animatiei:
- Reprezinta numai rotatie, nu si translatia
Analiza si prelucrarea imaginilor
Imbunatatirea imaginilor = cresterea calitatii imaginii in scopul interpretarii sale vizuale sau a
extragerii caracteristicilor
Operati tipice de imbunatatire:
- Conversia nivelelor de gri (intensitate)
- Imbunatatirea contrastului
- Conversia culorilor
- Netezirea zgomotului
- Evidentierea caracteristicilor (de ex. contururi)

Restaurarea imaginilor = reconstruirea imaginii fără defectele introduse de sistemul de achizitie

Operatii tipice de restaurare:
- Corectia distorsiunilor geometrice
- Corectia defectelor produse de defocalizarea camerei
- Corectia defectelor produse de miscarea camerei sau a obiectelor din imagine (motion
blur)
- Reducerea zgomotului din imagine (zgomot = pixel in imaginea discreta, care nu are
corespondent in imaginea reala)

Restaurarea si Imbunatatirea imaginilor in domeniul spatial

Conversia nivelelor de gri

O imagine discreta: este o functie f(x,y) = g, unde g este un nivel de gri (intensitate)
Conversia nivelelor de gri: Functie de transformare T: [0 - (L-1)] → [0 - (L-1)]
g(x,y) = T(f(x,y))

Aplicarea unui prag (thresholding)

Imbunatatirea contrastului (Contrast stretching) - Normalizarea

Intensitatile din imaginea de intrare cuprinse intre Lval şi Hval (un domeniu ingust de intensitati)
sunt scalate a.i. sa fie uniform distribuite in imaginea de iesire.

Evidenţierea caracteristicilor
Se evidenţiaza un domeniu specific de niveluri de gri din imagine, reducand totodata nivelurile
din afara domeniului la un nivel constant.

Se evidentiaza un domeniu specific de niveluri de gri din imagine, lasand nemodificate nivelurile
din afara domeniului.

Cazul general
Functia de transformare: functie liniara definita pe portiuni

Conversia nivelelor de gri folosind histograma imaginii

Histograma unei imagini: functie discreta,
h(k) = nk, nk este numarul de pixeli din imagine, cu intensitatea k
Histograma normalizata: h(k) = nk / n, n este numarul total de pixeli din imagine

Egalizarea histogramei

Imbunatatirea contrastului prin egalizarea histogramei

Egalizarea histogramei: egalizarea contributiei nivelurilor de intensitate din imagine.
Transformarea T trebuie sa produca o imagine cu o histograma aplatisata
Corectia distorsiunilor geometrice
Distorsiunea geometrică a unei imagini se manifestă printr-o deplasare a poziṭiilor pixelilor din
imagine faṭă de poziṭiile lor ideale, produse de un sensor ideal în condiṭii de achiziṭie ideale.
Corectia se bazeaza pe cunoasterea modelului matematic al distorsiunilor.
Distorsiunea geometrica este definita printr-un set de ecuatii de transformare a pozitiilor
pixelilor, din pozitiile reale (x,y) in pozitiile distorsionate (x',y'):
x' = hx (x,y)
y' = hy (x,y)
hx si hy sunt de obicei functii liniare pentru distorsiunile perspectiva si functii de grad 2 pentru
distorsiunile produse de lentilele camerelor foto.

Corectia:
- pentru fiecare pixel (x, y) al imaginii f(x,y)
- Calculeaza pozitiile distorsionate: x’ = hx (x,y) si y’ = hy (x,y)
- g(x,y) = f ( x’, y’ ) - memoreaza in pozitia corecta intensitatea din pozitia
distorsionata
- (x’, y’): numere reale → g(x,y) se calculeaza prin interpolare biliniara intre valorile
pixelilor din f

Estimarea zgomotului dintr-o imagine

Fie n imagini ale aceleiasi scene, obtinute cu acelasi sistem de achizitie si in aceleasi conditii de
achizitie: E0 , ... En-1 de N*N pixeli.
Pentru fiecare pixel (i, j) se calculeaza media intensitatilor sale din cele n imagini si deviatia
standard:

Modelarea zgomotelor
Eliminarea zgomotului din imagini se bazeaza pe cunoasterea modelului matematic al diferitelor
tipuri de zgomot.
Exista doua tipuri de zgomote:
- Independente de conţinutul imaginii
- Dependente de conţinutul imaginii

O imagine cu zgomot independent de conţinutul imaginii poate fi modelata prin:

g(x,y) = f(x,y) + n(x,y) unde:
f(x,y) este imaginea fara zgomot
n(x,y) reprezinta zgomotul independent de continutul imaginii, numit si zgomot aditiv
Zgomotul dependent de continutul imaginii poate fi reprezentat printr-un model ne-liniar:
model mai complicat →se considera (daca se poate) zgomotul independent de continutul
imaginii.
Tipurile uzuale de zgomot:
- zgomotul uniform
- zgomotul gaussian
- zgomotul sare si piper (salt-and peper) numit si impuls

Zgomotul modifica nivelul de intensitate (gri) al pixelilor in mod aleator. Se modeleaza ca o

variabila aleatoare discretă cu o functie de probabilitate care depinde de tipul zgomotului.

Zgomotul uniform
Zgomot cauzat de operatia de cuantizare cu un pas constant (reprezentarea valorilor
esantioanelor pe un numar limitat de niveluri discrete): valorile zgomotului sunt egal distribuite
în intervalul de intensitati [a,b] rezultate prin cuantizare, de ex. 0-255.

Intensitatea unui pixel dintr-o imagine cu zgomot uniform:

g(x,y) = f(x,y) + FDP(f(x,y))
FDP(f(x,y)) are aceeasi valoare pt orice f(x,y).

Zgomotul Gaussian

Fiecare pixel din imaginea cu zgomot Gaussian are o valoare rezultata din insumarea valorii
reale a pixelului cu o valoare aleatoare cu distributie Gaussiana.
g(x,y) = f(x,y) + FDP(f(x,y))
Modelul gaussian este cel mai des folosit pentru modelarea proceselor cu zgomot natural, cum
este zgomotul produs de sistemul de achizitie al imaginilor: zgomotul senzorului, produs de
proasta iluminare sau temperatura ridicata, zgomotul introdus de circuitele electronice.

Zgomotul sare şi piper

Numit si zgomot impuls – produs de variatii bruste ale semnalului electric, cauzate de
functionarea proasta a celulelor din senzorii camerelor, greseli ale locatiilor de memorie, erori de
sincronizare in procesul de digitizare sau erori (pierderi de biti) pe canalul de comunicatie in
cazul transmisiei imaginilor. Se manifesta prin puncte albe si negre cu aparitie aleatoare.

Filtre spatiale
Scopul: reducerea zgomotului din imagini sau evidentierea anumitor caracteristici
Filtre de mediere: filtre liniare
- g(x,y) este o medie ponderata a valorilor pixelilor din vecinatatea v(x,y);
- mai eficiente pentru imagini cu zgomot uniform sau zgomot gaussian;
Filtrele ordonate (filtre rang), filtrul conservativ: filtre neliniare
- Filtrul rang: g(x,y) este una dintre valorile pixelilor din vecinatatea v(x,y), aleasa pe baza
pozitiei sale in vectorul ordonat crescator al valorilor pixelilor din vecinatate (prima,
ultima, la mijloc);
- mai eficiente pentru imaginile cu zgomote sare-si-piper, zgomote exponential negative si
zgomote Rayleigh.
Filtre adaptive:
- îsi schimba comportamentul in functie de caracteristicile nivelelor de gri din vecinatatea
v(x,y);
- des folosite in multe aplicatii practice;

Filtre de mediere
Valoarea unui pixel(x,y) din imaginea filtrata este o medie ponderata a valorilor pixelilor dintr-o
vecinatate a pixelului, numită fereastra de filtrare.
Ponderile sunt definite într-o matrice de forma vecinatatii, numita masca de convolutie sau filtru
sau kernel

Filtrul trece-jos
Numit si filtru de netezire
- toate ponderile w(i,j) sunt pozitive
- suma ponderilor = 1 → aplicarea filtrului pe o zona de intensitate constanta nu produce
schimbari
Un filtru trece-jos (FTJ) atenueaza componentele de inalta frecventa din imagine (tranzitii bruste
de intensitate intre pixeli vecini), care pot reprezenta zgomote.
Imaginea rezultata din aplicarea unui FTJ este mai incetostata (neclara) decat imaginea
originala.
Prin atenuarea tranzitiilor bruste de intensitate se pot pierde detalii din imagine.

Filtrul medie: cat particular de FTJ. g(x,y) este media aritmetica a pixelilor din vecinatate

Filtrul trece-sus
Un filtru trece sus (FTS) accentueaza schimbarile de intensitate.
Masca filtrului este proiectata a.î. sa măreasca intensitatea pixelului din centru relativ la ceilalti
pixeli din vecinatate. De regula singura valoare pozitiva din masca este in centru.

Suma ponderilor = 1 → filtrul lasă neschimbate zonele de intensitate constanta.

FTS este folosit pentru imbunatatirea contrastului dintre zone adiacente între care exista o
diferenta mica de intensitate, în scopul evidentierii frontierelor şi a detaliilor din imagini.

Evidentierea frontierelor (Unsharp filter)

FTS amplifică zgomotele din imagine si detaliile mici (nesemnificative). Solutia: Unsharp filter
(“unsharp” – neascutit)
Fie: g(x,y) = f(x,y) - fnet(x,y)
unde f(x,y) este imaginea de intrare
fnet(x,y) este imaginea de intrare netezita prin aplicarea unui filtru trece-jos
g(x,y) are valori diferite de zero in pixelii de frontiera din imaginea de intrare

Filtrul “Unsharp” este definit astfel:

funsharp(x,y) = f(x,y) + k*g(x,y)
k este un factor de scara cuprins intre 0.2 – 0.7;
valorile mari ale lui k amplifica frontierele

Filtrul Gaussian
Masca filtrului Gaussian este o aproximare discreta a functiei de distributie Gaussiana 2D
Se considera nula valoarea functiei la o distanta de 3 fata de medie

Filtrul Gaussian este un filtru de netezire.

Gradul de netezire este determinat de valoarea deviatiei standard (creste odata cu sigma ).
sigma determina dimensiunea mastii: se alege in functie de nivelul de zgomot din imagine.
Filtrul Gaussian produce o netezire mai fina decat filtrul medie
Conserva frontierele mai bine decat un filtru medie de aceeasi dimensiune
Filtrul gaussian poate fi folosit pentru eliminarea zgomotului gaussian si a zgomotului uniform.

Filtre ordonate
Folosesc ordonarea intensitatilor pixelilor din fereastra de filtrare
Reduc zgomotele (frecvente inalte) fara a degrada detaliile din imagine (fronturile)
Nu produc nivele noi de intensitate in imaginea filtrata

Filtrul rang: g(x,y) = Rang-j (FP(x,y)) (FP = pixelii ordonati crescator din fereastra)
- intensitatea pixelului (x,y) din imaginea filtrata este aceea din pozitia j a vectorului FP
- j=0: filtrul min
- j=n-1: filtrul max
- j = n/2, n impar : filtrul median

Filtrul median
Inlatura zgomotele fara a atenua punctele de frontiera.
Forma ferestrei de filtrare influenteaza efectul filtrului (se alege mica, ca sa nu dureze sortarea)
Reduce variatia intensitatilor din imagine, producand regiuni de intensitate constanta sau
aproape constanta. Forma regiunilor depinde de geometria ferestrei de filtrare, aspect neplacut
deoarece sunt introduse in imaginea filtrata regiuni care nu existau.
Netezeste oscilatiile de intensitate cu o perioada mai mica decat latimea ferestrei
Modifica valoarea medie a intensitatilor din imagine daca distributia spatiala a zgomotului nu
este simetrica in fereastra.
Conserva anumite forme de frontiere.
Nu genereaza noi nivele de gri.
Principalul efort de implementare: ordonarea vectorului de intensitati

Filtrul de netezire conservativ

Netezeşte zgomotul conservând frontierele / detaliile reprezentate prin frecvenṭe mari în imagini.
Nu introduce niveluri noi de intensitate.
Proiectat pentru a elimina zgomotul de tip “sare şi piper”: pixelii izolaṭi cu intensitate foarte mare
sau foarte mică în comparaṭie cu cea a pixelilor din vecinătatea lor.
Mai puṭin eficient pentru eliminarea zgomotului aditiv de tip Gaussian sau uniform.

- Imin/Imax, cea mai mica/mare valoare de intensitate din vecinatatea pixelului (x,y)
- daca Imin <= f(x,y) <= Imax atunci g(x,y) = f(x,y)
 - altfel daca f(x,y) > Imax atunci g(x,y) = Imax
- daca f(x,y) < Imin atunci g(x,y) = Imin

Detectia pixelilor de frontiera din imagini

Frontierele:
- Alcatuite din pixeli in care intensitatea variaza brusc.
- Pot reprezenta obiecte subtiri (linii) sau pixelii aflati la adiacenta a doua zone din
imagine cu intensitati diferite.
Etape:
- Detectia pixelilor de front
- este un pixel in care intensitatea se schimba brusc: poate fi un punct de frontiera
sau un punct de zgomot
- este utila eliminarea/reducerea zgomotelor din imagine, inainte de detectia
pixelilor de front
- filtrele de netezire diminueaza nu numai intensitatea punctelor de zgomot ci si pe
aceea a pixelilor de frontiera
- Eliminarea pixelilor de front falsi
- Conectarea pixelilor de front pentru a forma frontiere

Detectia pixelilor de front

Se utilizeaza operatori (masti de convolutie) care aproximeaza in planul discret Gradientul
(derivata de ordinul 1) sau Laplacianul (derivata de ordinul 2 a) functiei imagine
Mastile sunt de dimensiune mica (3x3) → operatorii sunt sensibili la zgomot (pot produce
puncte de front false)

Detectia pixelilor de front bazata pe Gradient-ul imaginii

Amplitudinea gradientului:
- Este zero in zonele de intensitate constanta
- Este mare in pixelii in care intensitatea se schimba brusc (pixeli de front)
- directia gradientului = directia frontului: directia schimbarii maxime de intensitate
Vectorul gradient calculat intr-un pixel al unei imagini reprezinta directia si marimea variatiei
maxime de intensitate in acel pixel. Este definit în funcţie de derivatele parţiale ale funcţiei
imagine, f(x,y)
Amplitudinea gradientului în pixelul (x,y) este:

Ea reprezinta puterea frontului (marimea variatiei de intensitate) în pixelul respectiv Este

aproximata prin:

Directia gradientului este directia creşterii maxime de intensitate, intr-un pixel

Vectorul gradient este perpendicular pe directia frontierei.
Punctele de front dintr-o imagine sunt detectate calculând gradientul in fiecare pixel şi
identificând acei pixeli pentru care amplitudinea gradientului este mai mare decât un prag dat.
Cei mai utilizati detectori de fronturi bazati pe gradient sunt: Roberts (numit si operatorul cruce),
Sobel si Prewitt.

Detectorul Roberts

Detectorul se aplica in pixelul (x,y):

D+ (x,y) = f(x + 1, y + 1) – f(x,y) = P2 - P3
D- (x,y) = f(x , y + 1) – f(x + 1, y) = P1 - P4
D+ si D- se calculeaza cu urmatoarele 2 masti de convolutie:

Amplitudinea gradientului in (x,y) este aproximata prin: D(x,y) = |D+(x,y)| + |D-(x,y)|

Principalul avantaj al utilizarii acestui detector este simplitatea calculelor.
Dezavantajul: deoarece utilizeaza un nucleu foarte mic,
- este foarte sensibil la zgomot,
- raspunsul său la frontiere reale este slab daca acestea nu sunt foarte “abrupte” (o
tranzitie de intensitate foarte mare).

Detectorul Sobel
Gradientul este aproximat prin convolutia imaginii cu urmatoarele masti:

Pixelul (x,y) in care se calculeaza gradientul este cel pe care este centrata masca.
Mastile sunt proiectate pentru raspuns maxim la frontiere verticale si orizontale. Masca Dx
evidentiaza frontierele orizontale: (Dx=0) iar Dy frontierele verticale (Dy=0)
Amplitudinea gradientului este aproximata prin: D(x,y) = |Dx| + |Dy|
Frontierele produse de operatorul Sobel sunt groase (mai mult de un pixel).
Comparatie cu Roberts
- Necesita mai multe calcule
- Masca fiind mai mare, este mai putin sensibil la zgomot
- Produce valori de amplitudine mai mari decat cele produse de operatorul Roberts,
pentru aceleasi frontiere

Detectorul Prewitt
La fel ca Sobel, dar alte matrice de masca.

Detectia pixelilor de front bazata pe Laplacianul imaginii

Laplacianul unei imagini contine:
- Valori mari, pozitive si negative in vecinatatea unui punct in care intensitatea se schimba
brusc (punct de front)
- Zero in zone de intensitate constanta
Operatorul Laplacian este definit în funcţie de derivatele parţiale de ordinul 2

Rezulta ca Laplacianul poate fi implementat prin urmatoarea masca de convolutie:

Laplacian, este tot o imagine cu mai multe nivele de gri:

- g(x,y) = 0 in zonele de intensitate constanta
- <0 sau > 0 in vecinatatea unei frontiere (>0 de partea mai intunecata, <0 de partea mai
luminoasa)
- Pentru afisarea iesirii operatorului Laplacian sub forma unei imagini, valorile din |g(x,y)|
sunt normalizate la domeniul [0-nivel maxim de intensitate].
-
Pentru extragerea frontierelor din Laplacianul imaginii, se poate proceda in mai multe moduri:
- Se aplica un prag peste |g(x,y)|, rezultand o imagine binara, B(x,y):
- B(x,y) = 1 , daca |g(x,y)| > prag; 0, altfel
- Cat de aproape de frontiera reala sunt pixelii cu valoarea 1 in B(x,y) depinde de
alegerea pragului.
- Sunt considerate puncte de frontiera acele puncte in care g(x,y) != 0 si amplitudinea
gradientului este peste un prag dat.
- Daca in vecinatatea pixelului curent valorile Laplacianului sunt atat pozitive cat si
negative, dar peste o valoare de prag ca marime, atunci pixelul este unul de frontiera
(trecere prin zero a Laplacianului).

Utilizarea Laplacianului ca filtru

Masca de convolutie Laplacian poate fi utilizata ca filtru de îmbunătăṭire a imaginilor prin
evidentierea frontierelor (image sharpening).
Operatorul LoG - Laplacian of Gaussian
Laplacianul produce variatii pozitiv/negativ si la schimbari mici de intensitate, care nu reprezinta
frontiere, sau in pixeli de zgomot. De aceea, inainte de Laplacian se poate aplica imaginii un
filtru.
Imbina urmatoarele doua operatii:
- Filtrarea, prin aplicarea unui filtru Gaussian
- Detectia frontierelor, ca puncte de trecere prin zero a Laplacianului
In loc sa se aplice succesiv cei doi operatori de convolutie, se aplica un singur operator, numit
“Laplacian of Gaussian”, care are expresia: naiba stie…nu invat asa ceva nici picata cu ceara.
Operatorul LoG se aproximeaza in planul discret printr-o masca. Pot fi utilizate masti de orice
marime dar suma elementelor mastii trebuie sa fie zero (ca si in cazul mastilor Laplace), a.i.
rezultatul aplicarii intr-o zona omogena sa fie zero.

Evaluarea performantei detectorilor de fronturi

Criterii de evaluare a performantei unui detector de pixeli de frontiera (fronturi) :
- Probabilitatea detectiei de fronturi false
- Probabilitatea de a nu detecta fronturile
- Erori in estimarea directiei fronturilor
- Distanta dintre fronturile detectate si cele reale
Performanţa este influentata de:
- Nivelul de zgomot din imagine
- Marimea mastii filtrului de netezire utilizat inainte de detectie
- Pragul aplicat pe iesirea detectorului pentru a decide daca un pixel este front.
Pratt’s Figure Of Merit (FOM) : formula care depinde de numarul de fronturi detectate in
imaginea reala, numarul ideal de fronturi, distanta dintre frontul real si cel detectat, etc.

Prelucrarea imaginilor color

Proprietăṭile culorilor
Culorile percepute de sistemul vizual uman sunt caracterizate prin trei proprietăṭi:
- Nuanṭa (o culoare pură), determinată de lungimea de unda dominantă în distribuṭia
spectrală a luminii, perceputa ca o culoare.

- Saturaţia sau puritatea - o măsură a amestecului de alb într-o culoare pură. O culoare
pura are saturatia maxima (100% - nu contine alb)
- Intensitatea, determinata de energia luminii, percepută ca luminozitate sau strălucire
Nuanṭa + saturaṭia determină cromaticitatea unei culori.

Teoria tricromaticitatii
Orice culoare din spectrul vizibil se obtine ca o combinatie intre Rosu, Verde, Albastru
RGB: “primitive aditive“ - permit formarea de culori prin adunarea lor în diferite proporţii;
Două culori care prin amestec produc lumină albă se numesc complementare.
Culorile complementare culorilor primare sunt : cian (Cyan), magenta (Magenta), galben
(Yellow)
CMY: “primitive extractive” - Se folosesc pentru a caracteriza culorile reflectate de documentele
imprimate.

Modele de culoare
Se folosesc mai multe modele de culoare:
- Orientate catre utilizator - HSV, HLS, HSI
- Orientate catre echipamente şi transmisia imaginilor - RGB, CMY, YIQ, YCbCr.

Tehnici de prelucrare a imaginilor color

Doua categorii de metode de prelucrare a imaginilor color:
- Se proceseaza separat fiecare componenta a culorii si se compune rezultatul; in unele
cazuri prelucrarea se aplica numai uneia dintre componente, de exemplu, intensitatea
sau nuanta;
- Se lucreaza cu vectori de culoare (fiecare culoare are trei componente, fiind
reprezentata printr-un vector in spatiul culorilor). De exemplu, culoarea unui pixel p(x,y)
se reprezinta in spatiul (R,G,B) prin vectorul (0,0,0) →(Cr(x,y), Cg(x,y), Cb(x,y)).

Transformari de culoare
Imbunatatirea contrastului: se aplica numai componentei intensitate (value)

Evidentierea culorilor de interes in spatiul RGB

Subspatiul culorilor de interes dintr-o imagine poate fi reprezentat printr-un cub sau printr-o
sfera. Pixelii a caror culoare nu se incadreaza in volumul de interes sunt setati la o culoare
“neutrala”, pe care o notam cu n, ceilalti isi pastreaza culoarea.

Complementul unei imagini RGB

Neg(g) = Lmax – g

Filtrarea imaginilor color

In cazul filtrelor spatiale liniare, definite prin diferite masti de convolutie, filtrarea se aplica:
- Separat asupra componentelor culorii, in RGB,
- Asupra componentei de intensitate

Detecţia pixelilor de front din imagini color

Folosind HSV:
- diferente in intensitate (V)
- diferente cromatice (H)
Folosinf RGB:
- diferente in intensitate (se converteste in grayscale)
- diferente cromatice
- detectia separata pentru cele 3 canale
- calcularea gradientului vectorului de culoare

Detectia fronturilor separat pentru cele 3 canale de culoare

- Se calculeaza amplitudinile gradientilor pe cele 3 canale (cea mai populara metoda)
- Se calculeaza matricea fronturilor din suma gradientilor
Calcularea gradientului pe vectorul de culoare
- Se calculeaza gradientul imaginii in care fiecare pixel este un vector culoare.

Extragerea frontierelor din imagini

Binarizarea (Thresholding) matricei amplitudinilor

Extragerea frontierelor → binarizarea matricei amplitudinii gradientului, prin aplicarea unui prag.
In imaginea binara: pixelii =1 reprezinta fronturi, restul au valoarea zero
Alegerea pragului: mare →intreruperi in frontiera; mica→frontiere late

Detectorul Canny
A fost proiectat cu urmatoarele obiective:
- scaderea ratei de eroare – detectorul sa nu piarda puncte de frontiera si sa nu raspunda
la puncte care nu sunt puncte de frontiera
- punctele de frontiera sa fie bine localizate – distanta dintre punctele de frontiera gasite
de detector si cele reale sa fie minima
- detectorul sa furnizeze un singur raspuns la un singur punct de frontiera
Pasi:
- Se aplica imaginii de intrare un filtru Gaussian
- Cu cat latimea mastii este mai mare cu atat este mai mica senzitivitatea
detectorului la zgomot
- Se aplica operatorul Sobel
- Subṭierea frontierelor
- In matricea amplitutidinilor, frontierele apar ca zone late
- Se subtiaza frontierele eliminand pixelii care nu au amplitudinea gradientului
maxima locala.
- Sunt declarate puncte de frontiera acele puncte care au amplitudinea
gradientului maxima locala pe directia gradientului. Celelalte puncte sunt
eliminate (setate la zero). Efectul: subtierea frontierei fara intreruperea ei.
- Extragerea frontierelor
- Se elimina pixelii falsi de frontiera (zgomotele) fara intreruperea frontierei:
- Se utilizeaza operatia de “histerezis”, care consta in aplicarea a 2 praguri:
pragul de jos, P1, si pragul de sus, P2 (P2 aproximativ egal cu 2*P1).
- aceste praguri se aplica separat matricei amplitudinilor rezultata in pasul
anterior, rezultand 2 imagini binare, T1 si T2:
- Frontierele se obtin legand punctele din T2 si folosind puncte din T1 acolo
unde apar întreruperi în T2

Urmarirea frontierei prin predictia punctului urmator

a(P) = a(x,y) amplitudinea frontului in pixelul P(x,y)
θ(P) = θ(x,y) directia frontului in pixelul P(x,y)
T, T1 si T2 – valori de prag, date.
Două puncte de front, Pi , Pj , pot fi conectate dacă diferenţele în amplitudine şi direcţie sunt
sub valorile de prag date iar amplitudinile fronturilor sunt relativ mari

Algoritmul constă in :
- Determinarea punctului de start
- Determinarea celorlalte puncte de frontiera
- Din punctul curent:
 - Se aproximeaza pozitia urmatorului punct: punctul de frontiera anticipat
- Se alege următorul punct de frontiera din vecinatatea celui anticipat

Determinarea punctului de star

Se cauta doua puncte, P1, P2, care sa respecte conditia de conectare, dintr-o vecinatate de 3x3
pixeli.
Predicţia punctului următor (punctul anticipat)
Se bazează pe punctele de frontieră deja determinate şi eventual pe cunoaşterea tipului de
frontieră (linie dreapta, curba neteda).
Punctul anticipat se afla la o distanta d de punctul curent, pe frontiera determinata pana la
momentul curent.
Determinarea punctului de frontiera următor
Punctul următor este căutat în vecinătatea punctului anticipat.
El trebuie să fie un punct de front care poate fi conectat cu ultimul punct de frontieră determinat

Extragerea liniilor drepte din imagini - Transformata Hough

Metoda globala de extragere a frontierelor: se bazeaza pe ecuatia matematica a frontierelor
Intrarea: B - matricea obţinută prin binarizarea matricei amplitudinilor fronturilor.
Iesirea: o matrice binara in care pixelii cu valoarea 1 apartin unor linii drepte.
Imaginea: N1xN2 pixeli

Transformata Hough utilizează o reprezentare parametrică a liniilor pentru reducerea

complexităţii calculului căutării lor în imagini: y = ax + b
Daca dreapta y = a*x + b exista in imagine
- exista cel putin 2 pixeli care satisfac ecuatia
- exista cel putin doua drepte in spatiul parametric care se intersecteaza in punctul (a,b).
Numarul de drepte care se intersecteaza in (a,b) = numarul de pixeli din imagine, care se afla
pe dreapta y=a*x + b

Detectia liniilor drepte

- Se discretizează spaţiul parametric şi se reprezintă printr-o matrice P (numita
acumulator), astfel încât fiecare P[i][j] corespunde unui punct al spatiului discretizat:
- a1<= a <= aK-1 , aj = a1 + j*da
- b1<= b <= bL-1 , bi = b1 + i*db
- Pentru fiecare pixel (x, y), cu B[y][x] = 1 (pixel de front)
- se formeză ecuaţia b = - a*x + y ( dreapta coresp. pixelului in spatiul parametric)
- Pentru fiecare element P[i][j] al matricei P:
- dacă P[i][j] >= T (prag) atunci
- in imagine exista dreapta y = a*x + b, unde a = a1 + j* da, b = b1 + i*db
- marcheaza in matricea de iesire pixelii care se afla pe dreapta y = a*x + b
Precizia metodei depinde de pasul de discretizare a spaţiului (a , b), deci de mărimea matricei P
Complexitatea calculului transformatei Hough este O(K*N), unde K este numărul de
subintervale pe axa a iar N este numărul de pixeli din imaginea de intrare.
Utilizarea ecuaţiei parametrice y = a*x + b produce dificultăţi în reprezentarea liniilor verticale (
a-> ∞)
O reprezentare parametrica mai convenabilă este reprezentarea polară : r = x* cos(θ) + y*
sin(θ) unde r este distanta de la origine la dreapta.
Segmentarea imaginilor
= Determinarea zonelor (regiunilor) dintr-o imagine care conţin pixeli cu anumite caracteristici
similare: intensitate, culoare, adâncime – ȋntr-o imagine RGBD (D: Depth)

Metode de segmentare:
- Segmentarea bazata pe determinarea frontierelor regiunilor (detectia fronturilor, unirea
punctelor de front pentru delimitarea regiunilor)
- Segmentarea bazata pe regiuni
- Segmentarea prin divizare („ splitting ” )
- Segmentarea prin divizare şi unificare („ split & merge ”)
- Segmentarea prin extindere („region growing”)
- Segmentarea prin extindere şi unificare („region growing and merging”)
- Segmentarea bazata pe praguri de intensitate (la nivel de pixel).
- Segmentarea prin clusterizarea pixelilor pe baza intensitatilor (la nivel de pixel)

Segmentare prin divizare recursiva

Se verifică dacă întreaga imagine este omogenă, conform unui criteriu. Dacă nu este omogenă,
atunci imaginea este divizată în patru regiuni egale. Se verifica omogenitatea fiecărei regiuni.
Procedura de divizare este aplicată recursiv până când se obţin numai regiuni omogene.

Algoritmul de segmentare prin divizare recursivă produce o imagine segmentată care poate fi
reprezentată printr-un arbore cuadric :

Se memoreaza în fiecare nod al arborelui intensitatea care a fost atribuită pixelilor regiunii.
Dezavantajele algoritmului:
- pot rezulta regiuni adiacente similare
- poate produce o suprasegmentare
Solutia: dupa segmentare sunt unificate regiunile adiacente similare folosind arborele cuadric al
imaginii segmentate.
Unificarea a 2 regiuni: se calculeaza media intensitatilor regiunilor si se atribuie pixelilor
regiunilor unificate.

Segmentarea prin divizare şi unificare

Fie P predicatul care defineşte regula de segmentare (de exemplu Imax – Imin < prag )
- dacă Ri si Rj sunt adiacente si P(Ri) = TRUE (predicatul este satisfacut pentru regiunea
Ri) şi P(Rj) = TRUE atunci,
- daca P(Ri U Rj) = TRUE => Ri si Rj sunt regiuni similare si trebuie să fie
unificate.
Avantaj:
- Algoritmul produce un numar de regiuni mai mic si regiuni mai compacte decât
algoritmul bazat numai pe divizare.
- Criteriul de unificare poate fi diferit de cel de divizare
- Prin cele 2 criterii se poate controla suprasegmentarea imaginii
Dezavantaj: poate produce regiuni rectangulare

Segmentare prin extindere folosind pixeli germen (Region growing)

Se pleacă de la pixeli „germen” în jurul cărora se vor forma regiunile.
Plecând de la pixelii germen se formează în jurul lor regiuni adăugând iterativ pixelii vecini care
satisfac criteriul de similaritate.
Segmentarea prin extindere se bazează pe :
- O regulă care descrie mecanismul de extindere
- Un criteriu de similaritate, care restrictioneaza extinderea regiunilor

Algoritmul se termină atunci când într-o iteraţie numărul de pixeli clasificaţi nu s-a modificat (nici
o regiune nu s-a mai putut extinde).
Pixelii germen pot fi aleşi interactiv de către utilizator, sau automat ca pixeli a căror
intensitate/nuanṭă corespunde vârfurilor histogramei.
Performanţa algoritmului depinde mult de alegerea pixelilor germen.
Rezultatele algoritmului pot fi diferite pentru pixeli germen diferiti.

Segmentare prin extindere si unificare folosind pixeli germen

In urma segmentării prin extindere („creşterea” regiunilor) pot rezulta regiuni adiacente cu
proprietăţi statistice similare. Ele pot fi reunite printr-un algoritm de unificare („merging”).
Ca proprietăţi statistice se pot folosi media şi deviaţia standard. Criteriul de unificare a doua
regiuni adiacente, R1 şi R2: mediile lor sunt suficient de apropriate si deviatiile standard sunt
mici.
Unificarea poate fi înglobată în mecanismul de extindere descris anterior: dupa fiecare pas de
extindere se incearca unificarea regiunii extinse cu regiunile vecine.
Segmentarea bazată pe praguri
Se modifică intensitatea fiecărui pixel din imaginea de intrare în funcṭie de intervalul de
intensităṭi în care se află.
Valorile de prag pot fi alese ca puncte de minim local ale funcţiei histogramă

Functia histograma nu este o functie derivabila: este o functie definita pt valori discrete → se
folosesc diverse metode pentru a aproxima minimele functiei histogramă

Dezavantajele segmentarii bazate pe praguri:

- Segmentarea bazată pe aplicarea de praguri ṭine cont de omogenitatea regiunilor
obtinute, nu şi de conectivitatea lor, deoarece aplicarea pragurilor se face pixel cu pixel,
fără să se ţină cont de vecinătatea fiecărui pixel. Pot rezulta mai multe regiuni cu acelasi
nivel de intensitate neconectate (ar putea fi parti ale aceluiasi obiect).
- Rezultatul segmentarii bazate pe praguri poate fi supus unei analize de conectivitate a
regiunilor pentru detectia regiunilor conectate.

Segmentarea pe baza de adancime

Unele camere pot surprinde adancimea obiectului - D -, iar segmentarea se poate face doar pe
baza valorii D.
Dezavantaje: D este sensibil la zgomot (distante mari - zgomote mari)

Extragerea contururilor regiunilor

Doi pixeli sunt vecini direcţi (vecini-d) dacă celulele lor au o latură comună.
Doi pixeli sunt vecini indirecţi (vecini-i) dacă celulele lor se ating numai într-un colţ.
Termenul vecin-N, 0≤N≤7, desemnează un pixel aflat în poziţia N faţă de un pixel P:

O cale este o secvenţă de pixeli vecini Ak-1 , Ak, Ak+1.

O cale-d este o cale în care toţi pixelii sunt vecini-d.
O cale simplă este o cale în care toţi pixelii sunt distincti şi nici un pixel nu are mai mult de 2
vecini-d în cale.
O cale închisă este o cale în care primul pixel coincide cu ultimul.
Un set de pixeli, S, este conectat (sau conectat-i), dacă pentru fiecare pereche de pixeli A şi B
din S, există o cale în care A şi B sunt primul respectiv ultimul element, iar toţi ceilalţi pixeli ai
căii aparţin lui S.
Un set de pixeli este conectat-d, daca fiecare pereche de pixeli din set poate fi conectata
printr-o cale-d inclusa in set.
O regiune este un set de pixeli conectat în care toţi pixelii au aceleaşi caracteristici:
intensitate/culoare/adâncime.
Un pixel de contur al unei regiuni este un pixel care are cel putin un vecin-d in afara regiunii.
Reprezentarea contururilor
Prin lista adreselor absolute ale pixelilor care-l compun.
Adresa absoluta a pixelui de start urmata de deplasamente relative de la un pixel la urmatorul.
Deplasamentele relative pot fi reprezentate prin:
- Coduri de înlănţuire absolute (cod Freeman)
- Coduri de înlănţuire diferenţiale

Extragerea conturului unei regiuni

Conturul unei regiuni este traversat pe o cale închisă, fiind posibil întotdeauna să se aleagă o
astfel de cale.
Pixelul de start se poate alege scanand imaginea de sus in jos şi de la stanga la dreapta: este
un pixel care aparţine regiunii considerate (are intensitatea/eticheta pixelilor regiunii) şi este
pixel de contur (are cel putin un vecin-d in afara regiunii).
Traversarea constă într-o deplasare pixel cu pixel, în fiecare pas fiind ales ca pixel de contur
urmator, pixelul din regiune care este cel mai in dreapta faţa de pixelul curent. In acest fel,
interiorul regiunii se afla intotdeauna in stanga pixelului selectat (conturului).
Cu aceasta regula de traversare, contururile exterioare sunt parcurse in sens trigonometric, iar
cele interioare in sensul acelor de ceas.

Extragerea tuturor contururilor unei regiuni: se parcurge toata forma si se aplica algoritmul
pentru fiecare pixel de start gasit acum si nevizitat anterior.

Aproximarea poligonala a frontierelor

- Simplifica forma frontierei, fara efecte de netezire
- Conduce la eliminarea zgomotului
- Elimină caracteristicile nerelevante, pastrandu-le pe cele relevante pentru forma
frontierei
- Conṭine pixeli ai frontierei – nu introduce pixeli noi
- Poate fi folosita ca metoda de preprocesare inainte de extragerea caracteristicilor unei
forme
Fie p1 , p2 , … , pN pixelii unei frontiere, care poate fi o curba deschisa oarecare sau o parte
dintr-o curba inchisa (conturul unei regiuni).
di – distanţa de la pixelul pi la segmentul de dreaptă (p1 -pN )
di este eroarea de aproximare a frontierei prin segmentul (p1 -pN ) în pixelul pi
Eroarea maximă de aproximare a frontierei prin segmentul (p1 -pN ) este Emax = max(di)

Poligonalizarea prin divizarea recursiva a frontierei

Algoritmul se aplica unei frontiere deschise.
Dacă frontiera este un contur închis, punctele p1 şi pN se aleg astfel încât să fie situate la
distanţa maximă pe contur (p1 - pN reprezinta axa majora a formei marginita de contur).

Fie p1 şi pN punctele extreme ale frontierei la un apel al functiei de poligonalizare.

- Daca frontiera poate fi aproximata prin segmentul p1- pN ( Emax < prag) atunci se iese
din recursivitate
- altfel
- se determina pixelul p(x,y), aflat la distanţă maximă de segmentul (p1 -pN )
- se apeleaza recursiv functia de poligonalizare pentru segmentul de frontiera (p1
– p)
- se adauga p la lista de varfuri a liniei poligonale
- se apeleaza recursiv functia de poligonalizare pentru segmentul de frontiera (p-
pN )

Dacă pragul este mic, poligonul va avea un număr mare de varfuri.

Principalul avantaj al metodei: detectează punctele de inflexiune ale frontierei, care devin vârfuri
ale liniei poligonale.

Poligonalizare prin parcurgerea frontierei

- Se pleacă din p1 şi se avansează în lista de pixeli până într-un punct pi , în care eroarea
de aproximare a frontierei p1 -pi printr-un segment de dreaptă depăşeşte pragul.
- Se memorează pi-1 în lista vârfurilor liniei poligonale.
- Se repetă procesul plecând din pi-1 .
- Dacă frontiera este închisă, se alege p1 ca punctul de inflexiune cel mai proeminent
Principalul dezavantaj al metodei: vârfurile poligonului nu coincid cu punctele de inflexiune ale
frontierei.

Operatii morfologice
Morfologia: studiul formelor.
Imaginile binare contin numeroase defecte, mai ales cele obtinute prin aplicarea unui prag.
In prelucrarea imaginilor binare: operatiile morfologice se folosesc pentru eliminarea defectelor
si simplificarea imaginilor in vederea recunoasterii formelor.

Intrările :
- I(x,y) - o imagine binara: 0 – pixeli de fond; 1 –pixeli din regiuni
- Un element structural (şablon) - contine, in general, trei tipuri de valori: 0, 1, neutrala;
valorile neutrale nu au efect la utilizarea sablonului

Iesirea: O(x,y): o imagine binara

Executia:
- Se translateaza ṣablonul cu originea sa peste fiecare pixel I(x,y) al imaginii de intrare,
comparandu-se pixelii acoperiti de ṣablon cu valorile ṣablonului egale cu 0 sau 1.
- In functie de rezultatul comparatiei si scopul operatiei: O(x,y) ← I(x,y) sau O(x,y) ← 0
sau O(x,y) ← 1.

Erodarea (Erosion)
Erodarea frontierelor regiunilor – de exemplu, pentru extragerea scheletului unei regiuni
Elementul structural contine numai valori 1 si neutrale.

Pentru fiecare pixel I(x,y) al unei regiuni din imaginea de intrare (I(x,y) =1)
- Se suprapune ṣablonul cu originea sa peste pixelul I(x,y)
- Daca fiecare element al ṣablonului =1 coincide cu pixelul imaginii de intrare acoperit de
el, atunci O(x,y) ← I(x,y), altfel O(x,y) ← 0 (devine pixel de fond)
- Fie urmatoarele elemente structurale:

-
- Efectul operatiei de erodare cu aceste sabloane: orice pixel care nu este inconjurat de
pixeli ai unei regiuni este eliminat (devine pixel de fond); astfel, pixelii aflati la frontierele
regiunilor sunt eliminati.

Dilatarea (Dilation)
Este operatia duală erodarii :
- Erodarea regiunilor - echivalenta cu dilatarea zonelor cu pixeli de fond.
- Dilatarea regiunilor - echivalenta cu erodarea zonelor cu pixeli de fond.
Pentru fiecare pixel de fond al imaginii de intrare (I(x,y)=0)
- Se suprapune ṣablonul cu originea sa peste pixelul I(x,y)
- Daca cel putin un element al ṣablonului coincide cu pixelul imaginii de intrare acoperit de
el, atunci O(x,y) ← 1 (devine pixel de regiune)
 -
- Efectul operatiei de dilatare: devine pixel de regiune orice pixel de fond care are in
vecinatatea sa un pixel de regiune. Astfel, regiunile cresc iar gaurile din interiorul
regiunilor se micsoreaza.

Deschiderea
- erodare + dilatare cu acelasi sablon
- Este eficienta in eliminarea zgomotului de tip “sare”
- Produce regiuni care contin complet elementul de structurare, eliminand regiunile mici
(care nu contin elementul de structurare).

Inchiderea
- dilatare + erodare
- Este eficienta in eliminarea zgomutului de tip “piper”.
- Pastreaza zonele de fond care au forma similara cu cea a elementului de structurare
sau care contin complet elementul de structurare eliminand toate celelalte zone de pixeli
de fond.

Subţierea (Thinning)
Operatie de erodare iterativă, prin care sunt indepărtati succesiv pixeli de frontiera ai regiunilor
unei imagini binare.
Este utila pentru:
- scheletizarea regiunilor rezultate din segmentarea imaginilor, in scopul recunoasterii
formelor
- subtierea frontierelor produse de detectoarele de frontiere

Scheletizarea
Multe forme, mai ales cele subtiri, pot fi descrise prin versiunile lor subtiate, alcatuite din linii
conectate, aflate, in mod ideal, de-a lungul axei mediane.

Scopul scheletizarii: extragerea axei schelet (axa mediana) a unei regiuni, in scopul
recunoasterii formei regiunii.
Axa schelet a unei regiuni este o aproximare in spatiul discret a scheletului unei forme.
Trebuie sa satisfaca 2 cerinte:
- Topologica: sa conserve caracteristicile topologice ale formei: lungimea si latimea
formei, nr. de puncte de jonctiune si alte caracteristici
- Geometrica: sa se situeze cat mai aproape de axa mediana a formei originale
Se utilizeaza pentru:
- recunoasterea caracterelor de text din documente scanate (unde, la o rezolutie mare,
caracterele apar cu o grosime de mai multi pixeli)
 - recunoasterea scrisului manual si a semnaturilor
- recunoasterea de forme diverse.

In planul continuu, axa schelet este alcatuita din puncte P care sunt centre ale unor cercuri
conţinute în întregime în R, cu proprietatea ca nu exista alte cercuri cu aceleasi centre, de raza
mai mare, continute în R

In planul discret, axa schelet se obtine prin 2 tipuri de metode:

- Calculand distantele aproximative ale pixelilor regiunii fata de pixelii de frontiera – pixelii
de schelet sunt cei aflati la distanta maxima locala faṭă de cei mai apropiati pixeli de
frontiera
- Printr-un proces iterativ de erodare a marginilor formei (subtiere)

Metrici de distanta in planul discret

Folosite pentru aproximarea distantei dintre doi pixeli.

Distanta euclidiana:

Distanta City-block (Manhatten):

Distanta “Tabla de sah”:

Transformarea distanţă
Se marcheaza in imaginea de intrare, I, pixelii de interes (pot fi pixelii conturului unei regiuni).
Fiecare pixel (x,y) din imaginea transformata (imaginea de iesire) are ca valoare distanta
pixelului fata de cel mai apropiat pixel de interes.
Implementarea iterativa a transformarii consta in utilizarea unor masti cu ajutorul carora se pot
calcula iterativ distantele de la pixelii imaginii la pixelii de interes.

- repeta
- gata = 1
- pentru fiecare pixel I(x,y) al imaginii
- plaseaza masca centrata pe pixelul (x,y)
- pentru fiecare element m[k][l] al mastii care acopera vecinatatea pixelului
(x,y)
- calculeaza sum[k][l] = suma dintre m[k][l] si valoarea pixelului
acoperit
- calculeaza summin = minim(sum[k][l])
- daca I(x,y) ≠ summin atunci
- gata = 0;
- I(x,y) ← summin
- cat timp(!gata)
Ȋn imaginea segmentată binară pixelii regiunilor au valoarea 1 iar cei de fundal valoarea 0.
Imaginea este transformata în mai multe iteratii, executand algoritmul anterior, folosind o masca
de aproximare a distantei.
Pixelii din imaginea finala care au valoarea locala maxima sunt considerati pixeli de schelet.
Numarul de iteratii este proportional cu cea mai mare distanta de la un pixel de regiune la cel
mai apropiat pixel de frontiera.

Scheletizarea prin subtiere

Subtierea este un proces iterativ de erodare a marginilor unei regiuni..
In fiecare iteratie se viziteaza o singura data fiecare pixel al imaginii, verificandu-se daca poate
fi indepartat, cu satisfacerea celor 2 constrangeri de conservare a topologiei:
- sa nu fie distrusa conectivitatea formei
- sa nu fie scurtate terminatiile formei

Dezavantajul algoritmului: nu subtiaza imaginea simetric. Axa schelet este localizata in partea
de sud - est a regiunii, deoarece pixelii de frontiera din partea de nord – vest sunt eliminati
primii. → rezultat nesatisfacator atunci cand obiectele din imagine sunt relativ mari si convexe.

Subtierea in doi pasi (subtiere simetrică – axa schelet in apropierea axei mediane a formei):
Intr-o iteratie imaginea este vizitata de 2 ori (in 2 pasi):
- In primul pas sunt eliminati pixelii care apartin unei frontiere de est, de sud sau unui colt
de nord - vest.
- In pasul al doilea sunt eliminati cei care apartin unei frontiere de nord, de vest sau unui
colt de sud - est.