Capitolul 1. Eliminarea unui obiect nedorit 5 1.1 Prelucrarea imaginilor 5 1.2 Reconstituirea imaginilor 7 1.3 Algoritmii existen ț i 10 [609554]

UNIVERSITATEA „BABE
Ș
-BOLYAI”

FACULTATEA DE MATEMATICǍ
Ș
I INFORMATICǍ

SPECIALIZAREA INFORMATICǍ

Lucrare de diplomă

Eliminarea unui obiect nedorit

dintr-o imagine

Conducător
ș
tiin
ț
ific
Absolvent: [anonimizat]. dr.
​
Vasile Prejmerean
​
Rus Cristian-Vlad

Cluj-Napoca

2018

1

CUPRINS

CUPRINS
2

Introducere
3

Capitolul 1. Eliminarea unui obiect nedorit
5

1.1 Prelucrarea imaginilor
5

1.2 Reconstituirea imaginilor
7

1.3 Algoritmii existen
ț
i
10

Capitolul 2. Caracteristici ale aplica
ț
iilor
ș
i tehnologiilor web
15

2.1 Introducere
15

2.2 Prezentare generală
16

2.3 Componentele principale
16

2.3.1 Redactarea documentelor web – HTML
16

2.3.2 Protocolul HTTP
17

2.3.3 Limbajul de scriptare Javascript
19

Capitolul 3. Implementarea aplica
ț
iei
21

3.1 Definirea problemei
21

3.1.1 Interac
ț
iunea cu utilizatorul
22

3.1.2 Necesitatea celor doi algoritmi
23

3.2 Metoda rapidă
24

3.2.1 Modelul matematic
24

3.2.2 Folosirea Fast Marching Method pentru reconstituire
25

3.2.3 Func
ț
ia de p ondere w
26

3.3 Metoda lentă
27

3.3.1 Ordinea reconstituirii
28

3.3.2 Găsirea celui mai potrivit exemplar
29

3.3.3 Completarea ferestrei
31

3.4 Contribu
ț
ii person ale
31

3.5 Studiu de caz
33

Capitolul 4. Concluzii
34

Bibliografie
36

2

Introducere

Obiective

Dorin
ț
a de
ș
tergere a obiectelor nedorite din imagini este foarte v eche. Scopurile acestei

dorin
ț
e pot fi numeroase, de la restaurarea unor picturi sau fotografii care au suferit

modificări datorită factorilor externi pană la
ș
tergerea propriu zisă a unor obiecte nedorite.

Obiectivul acestei lucrări este de a dezvolta o aplica
ț
ie cu ajutorul căreia un utilizator poate

modifica fără soft specializat imagini digitale reu
ș
ind să elimine
ș
i să umple locul unor

obiecte nedorite dintr-o imagine, cu texturi
ș
i structuri din vecinătate, într-un mod automat
ș
i

insesizabil ochiului uman.

Există diferite tipuri de tehnici folosite pentru a umple formele
ș
terse. Unele dintre ele

folosesc o bază de date cu imagini în care se caută lucruri similare cu fundalul din apropierea

obiectului
ș
ters altele înc earcă să umple partea
ș
tearsă cu informa
ț
iile disponibile în imaginea

curentă folosind diferi
ț
i algoritmi. Există o mul
ț
ime de astfel de algoritmi însă problema de

reconstituire nu a fost automatizată în totalitate, pentru rezultate bune fiind deseori necesară

interven
ț
ia utilizatorului î n diferite feluri. Majoritatea algoritmilor se bazează pe procedee

folosite de speciali
ș
tii în r econstituiri de picturi, portrete, fotografii. De asemenea această

tehnică poate fi folosită
ș
i în grafica pe calculator, post produc
ț
ia de filme, eliminarea

subtitrărilor nedorite.

Contribu
ț
ii Personale

Contribu
ț
ia mea în aceast ă lucrare constă în faptul că am optimizat una din metodele folosite

pentru reconstituirea imaginilor. Am modificat metoda în func
ț
ie de care se prioritizează

zonele care trebuie reconstruite pentru o mai bună propagare a structurilor liniare, am redus

timpul de procesare al imaginii, încercând să optimizez algoritmul din punct de vedere

computa
ț
ional, mic
ș
orând partea din imagine în care se caută cel mai bun exemplar pentru

înlocuire, dar
ș
i să folose sc mijloacele moderne de distribuire a calculelor pe mai multe fire

de execu
ț
ie acolo unde a fost posibil.

3

Structura lucrării

Lucrarea este formată din 4 capitole principale, care sunt structurate astfel:

– Capitolul 1 – Con
ț
ine teoria temei abordate de această lucrare, în acest capitol fiind

conturat domeniul din care face parte această temă, prelucrarea imaginilor, de asemenea se

conturează
ș
i subdomeniu l, reconstituirea imaginilor, fiind prezentate rezultatele ob
ț
inute

pană în momentul actual de diferi
ț
i cercetători, reliefându-se atât avantajele cât
ș
i

dezavantajele fiecărei abordări în parte prin compararea lor.

– Capitolul 2 – Constituie o prezentare generală a aplica
ț
iilor web, precum
ș
i o

prezentare generală a tehnologiilor
ș
i limbajelor folosite pentru dezvoltarea aplica
ț
iei de

fa
ț
ă. Sunt prezentate tehn ologiile ce au ca rol principal dezvoltarea unei aplica
ț
ii web pe

latura de func
ț
ionalitate, t ehnologiile ce sunt utilizate în partea de interfa
ț
ă cu utilizatorul dar

ș
i arhitectura
ș
i implementarea, importan
ț
a lor în interac
ț
iunea cu utilizatorul, dar
ș
i unul din

elementele principale ale aplica
ț
iilor web, comunicarea între tehnologii diferite .

– Capitolul 3 – Sunt prezentate mai amănun
ț
it contribu
ț
iile proprii asupra lucrării.

Totodată am prezentat cele două tehnici de reconstituire digitală a imaginii care au fost

folosite în realizarea acestei aplica
ț
ii web, fiecare metodă în parte având plusurile
ș
i

minusurile ei. De asemenea sunt reliefate func
ț
ionalită
ț
ile aplica
ț
iei, performan
ț
ele

algoritmului îmbunătă
ț
it dar
ș
i procesul prin care s-a ajuns la prod usul final.

– Capitolul 4 – Sunt eviden
ț
iate concluziile trase în urma dezvoltării aplica
ț
iei
ș
i a

implementării algoritmului, limitele impuse de algoritm, precum
ș
i posibile îmbunătă
ț
iri care

pot fi aduse aplica
ț
iei.

4

Capitolul 1. Eliminarea unui obiect nedorit

1.1 Prelucrarea imaginilor

Prelucrarea imaginilor este o metodă de a transforma un semnal analog într-o form
​
ă
​
digital
​
ă

care poate fi u
ș
or manipu lat
​
ă
​
prin diferite tehnici în scopul de a ob
ț
ine o imagine sau diferite

informa
ț
ii utile din ea.
​
Într-un sens cât mai general, o imagine este o descriere a varia
ț
iei unui

parametru pe o suprafa
ț
ă. De exemplu, imaginile (în sensul clasic) sunt rezultatul varia
ț
iei

intensită
ț
ii luminii într-un plan bidimensional. Dar acest parametru nu este singurul folosit, de

exemplu o imagine poate fi generată de temperatura unui obiect, emisiile radia
ț
iilor (cu

diverse lungimi de undă) etc. Însă aceste tipuri de imagine sunt, de obicei, convertite în

imagini clasice pentru ca operatorul uman să poată face o evaluare vizuală a varia
ț
iei unor

parametrii. Din aceste considerente, pe parcursul lucrării toate referirile se vor face la imagini

în sensul clasic.

O imagine este deci un semnal bidimensional, prin urmare prelucrarea imaginilor poate fi

considerată
ș
i o ramură a prelucrării digitale de semnal (care mai include prelucrarea audio,

telecomunica
ț
ii). Prelucra rea de imagini
ș
i în general prelucrarea digitală a semnalelor

presupune un consum relativ mare de resurse de calcul
ș
i memorie.

Procesarea imaginilor este una din tehnologiile care se dezvoltă foarte mult în zilele de azi,

având aplica
ț
ii în diverse aspecte ale unei afaceri. Companii precum Apple, Samsung fac

mari eforturi în efortul de a dezvolta noi metode de a modifica imaginile în timp real,

procesarea imaginilor fiind una din principalele arii de cercetare ale acestor companii.

Pe scurt, procesarea unei imagini se face în trei pa
ș
i:

– ob
ț
inerea imagi ni digitale prin intermediul scanării sau a unui aparat digital

– analiza
ș
i manip ularea imaginii incluzând compresia datelor
ș
i îmbunătă
ț
irea

imaginii

5

– ob
ț
inerea rezulta telor în urma procesării imaginii fie ca e vorba de aceea
ș
i imagine

care a trecut prin diferite procese sau unor rapoarte care s-au construit în urma analizării

imaginii.

Scopul prelucrării imaginilor se poate împar
ț
i în mai multe subcategorii:

– Vizualizare – observarea obiectelor care nu sunt vizibile ochiului uman

– Îmbunată
ț
irea im aginii
ș
i restaurare

– Măsurarea modelului – Măsoară diferite obiecte dintr-o imagine.

– Recunoa
ș
terea im aginii – Distinge obiectele dintr-o imagine.

Tehnicile de procesare digitală ajută la manipularea imaginilor digitale prin utilizarea

calculatoarelor. Dat fiind că datele brute de la senzorii care capturează imagini pot con
ț
ine

defecte. Pentru a depă
ș
i astfel de defecte
ș
i pentru a ob
ț
ine acurate
ț
ea informa
ț
iilor, trebuie să

treacă prin diferite faze de procesare. Cei trei pa
ș
i pe care toate tipurile de date digitale

trebuie să le suporte sunt:

– Preprocesarea

– Îmbunătă
ț
irea
ș
i afi
ș
area

– Extragerea informa
ț
iilor

Prelucrarea imaginilor este folosit
​
ă
​
în diferite discipline precum în:

–
Sisteme inteligente de transport – utilizând imaginile preluate de senzorii ma
ș
inii

pentru a identifica
ș
i recunoa
ș
te semnele de circula
ț
ie, pietonii etc.

–
Teledetec
ț
ie – în a ceastă aplica
ț
ie, senzorii captează imagi nile suprafe
ț
ei pământului în

sateli
ț
i de teledete c
ț
ie sau scaner multi-spectral care este m ontat pe o aeronavă.

–
Tehnici imagistice biomedicale – Pentru diagnosticul medical, sunt utilizate diferite

tipuri de instrumente de imagistică, cum ar fi raze X, ultrasunete, tomografie asistată

de calculator etc. Procesarea imaginilor este folosit
​
ă
​
cu succes în identificarea bolilor

de inim
​
ă
​
, plămâni sau a tumorilor.

–
Supraveghere – folosind procesarea imaginilor se poate detecta mi
ș
carea, astfel se pot

reduce resursele necesare de stocare a datelor

6

Suntem în mijlocul unei revolu
ț
ii informatice, aprinse de dezvoltarea rapidă în domeniul

tehnologiei informa
ț
iilor. Odată cu cre
ș
terea puterii de procesare a computerelor moderne,

se a
ș
teaptă ca paradigmel e de calcul paralel
ș
i distribuit să îmbunătă
ț
ească rezultatele

procesării imaginilor.

1.2 Reconstituirea imaginilor

Odată cu popularizarea camerei digitale, în ziua de azi fiecare om având în buzunarul sau un

telefon inteligent capabil să facă o poză care să imortalizeze anumite momente,
ș
i cu

digitalizarea fotografiilor vechi, reconstituirea a devenit un proces des folosit pentru a

îmbunătă
ț
ii aceste imagin i. Mai mult de îndepărtarea zgârieturilor, tehnicile de reconstituire

sunt capabile sa elimine elemente nedorite, text
ș
i să producă alte modificări imaginilor
ș
i

filmelor. În plus restaurarea poate fi folosită în diferite domenii cum ar fi compresia imaginii

ș
i super-rezolu
ț
ie
.

1

Principalul scop al reconstituirii unei imagini este de a repara anumite păr
ț
i care au suferit

degradări din cauza factorilor externi cum ar fi timpul, manipularea neglijentă depozitarea

necorespunzătoare, de obicei aceste lucrări sunt efectuate de speciali
ș
ti care încearcă să aducă

lucrarea în forma ini
ț
ială. Ace
ș
ti speciali
ș
ti folosesc diferite tehnici pentru a reconstitui, fără a

modifica operele de artă. Din aceste tehnici s-au inspirat
ș
i cercetătorii care au venit cu solu
ț
ii

diferite de reconstituire a imaginilor digitale, fiecare solu
ț
ie încearcă sa imite cât mai bine

procesul urmat de speciali
ș
tii în reconstituiri. Însă solu
ț
iile găsite se adresează unui fel de

problemă, în momentul de fa
ț
ă neexistând un algoritm care să rezolve toate problemele de

acest fel.

Procesul de reconstituire a unei imagini digitale dore
ș
te să reproducă munca depusă de

speciali
ș
tii în reconstituir i într-un mod automat. Exista diferite tehnici de reconstituire,
ș
i

anume :

1
Super-rezolu
ț
ia
se
referă
la
metoda
de
a
crea
o
imagine
folosind
mai
multe
imagini,

suprapunând imaginile, rezultatul fiind o imagine de înaltă defini
ț
ie [5]

7

–
reconstituirea structurală – folose
ș
te abordări geometrice pentru a reconstitui zona

ș
tearsă, ace
ș
ti algoritmi se concentrează să păstreze consis ten
ț
a geometrică a structurii

rezultate în urma reconstituirii

–
reconstituirea texturii – ca
ș
i celelalte metode reconstituirea texturii are avantaje
ș
i

dezavantaje, principala problema fiind ca textura are un model repetitiv ceea ce

înseamnă că o por
ț
iune lipsă nu poate fi reconstruită doar prin continuarea texturii,

fără a lua în seamă structura din vecinătate.

–
reconstituirea combinând cele 2 forme anterioare – prin combinarea reconstituirii

structurii
ș
i a textu rii simultan pentru a ob
ț
ine rezultate bune, majoritatea par
ț
ilor

dintr-o imagine fiind formate atât din structuri cât
ș
i texturi.

Marginile dintre regiunile unei imagini acumulează informa
ț
ie structurală complexă în

urma amestecului texturilor, din acest motiv se încearcă combinarea celor două tipuri de

reconstituire. Exista numeroase metode care îmbină reconstituirea structurii
ș
i a texturii,

precum cea bazată pe exemplu, bazată pe ecua
ț
ii cu derivate par
ț
iale, pe sintetizarea texturii,

alte metode urmăresc direc
ț
ia unei izofote
pentru a efectua reconstituirea. Toate aceste

2
metode de reconstituire au un lucru în comun – folosesc informa
ț
iile cunoscute din imagine

pentru a umple golul.

Sintetizarea texturii se adresează unui mic subset de probleme întâlnite nefiind optime pentru

imagini în care se dore
ș
te eliminarea unor obiecte mari. Reconstituirea bazată pe exemplu

reconstruie
ș
te iterativ reg iunea necunoscută cu zone din imagine care se potrivesc cu partea

care trebuie reconstruită, însă această tehnică produce rezultate bune doar dacă zona lipsa se

poate reface din structuri
ș
i texturi simple. Un algoritm bazat pe convolu
ț
ii reface imaginea

înlocuind pixelii lipsă cu pixeli din vecinătate, folosind un
ș
ablon potrivit, această tehnică

este foarte rapidă dar nu produce rezultate bune în zonele cu margini deteriorate care au

diferen
ț
e mari intre struc turile înconjurătoare.

2
izofotă
s.
f.
linie
care
une
ș
te
punctele
cu
valori
egale
ale
intensită
ț
ii
luminii.
(
lb.germana

Isophote)

8

Principalele tipuri de algoritmi pentru
ș
tergerea obiectelor se bazează pe:

–
sintetizarea texturii: imaginea se reconstruie
ș
te pixel cu pixel alegând pixeli cu

vecinătă
ț
i similare într-un mod aleator. Algoritmul are rezultate bune însă procesarea

imaginii durează foarte mult
ș
i are dificultă
ț
i în a recrea marginile obiectelor, fiind

optim în cazul în care imaginile sunt mici
ș
i obiectele
ș
terse au mărimi reduse.

–
reconstituirea bazată pe convolu
ț
ii: acest tip de algoritmi sunt foarte rapizi însă

rezultatele nu sunt întotdeauna cele dorite. Acestea nu oferă rezultate adecvate când

detaliile sunt bine conturate, cum ar fi marginile. În această metodă se calculează

coeficien
ț
ii mă
ș
tii utilizând gradientul imaginii care urme ază a fi umplută. Algoritmul

este rapid, iterativ, simplu de implementat
ș
i oferă rezultate adecvate în unele situa
ț
ii,

însă în cazul obiectelor mari rezultatul nu este unul mul
ț
umitor.

–
reconstituirea bazată pe exemplu: încearcă să automatizeze procesul de clonare. Acest

proces constă în căutarea de zone asemănătoare în apropierea regiunii
ș
terse
ș
i

înlocuirea bucă
ț
ii
ș
terse cu o zonă asemănătoare găsită. Pr in folosirea de zone
ș
i nu

pixeli individuali se reduce zgomotul adăugat de tehnicile anterioare. Tehnica de

reconstituire bazată pe exemplu folose
ș
te diferite măsurători pentru a găsi cea mai

potrivită zonă cunoscută pentru a umple golurile lăsate în urma
ș
tergerii obiectelor.

Este un algoritm de tip “greedy”
astfel că ordinea de reconstituire a imaginii este

3
foarte importantă. Această tehnică are rezultate bune dacă regiunea care trebuie

reconstituită este formată din structuri bine definite, însă datorită procesului prin care

se găse
ș
te cea ma i potrivită por
ț
iune, fiind un proces în ca re se efectuează numeroase

calcule, timpul necesar reconstituirii imaginii este foarte mare. Datorită faptului că

este un algoritm care lucrează cu por
ț
iuni
ș
i nu cu pixeli, în urma reconstituirii

imaginea rezultată nu suferă de fenomenul de zgomot, precum tehnicile prezentate

anterior. Reconstituirea bazată pe exemplu se face în trei pa
ș
i:

–
prioritizarea zonelor care trebuie înlocuite

–
selectarea celei mai potrivite zone

–
copierea ferestrei găsite în locul regiunii
ș
terse

3
algoritm
greedy
–
proces
matematic
care
caută
după
solu
ț
ii
simple
u
ș
oare
de
implementat

pentru
probleme
complexe
cu
multi
pa
ș
i
alegând
cea
mai
optimă
solu
ț
ie
la
un
moment
dat,

însă asta nu garantează solu
ț
ia optimă pentru întreaga problemă. [8]

9

1.3 Algoritmii existen
ț
i

Majoritatea metodelor de reconstituire func
ț
ionează după următorii pa
ș
i mai întâi este

selectată por
ț
iunea care tr ebuie reconstituită, pe urmă informa
ț
ia texturii din vecinătatea zonei

selectate este propagată spre interior. Pentru a produce o reconstruire plauzibilă din punct de

vedere vizual, un algoritm de reconstituire ar trebui să continue
​
izofot
​
ele (liniile de aceea
ș
i

valoare de gri) într-un mod cât mai
​
verosimil în interiorul zonei reconstituite.

Câteva tehnici de reconstituire a imaginii sunt bazate pe ideile de mai sus, de exemplu, în

lucrarea “Images Inpainting”[7] Bertalmio
ș
i asocia
ț
ii lui, reu
ș
esc să reconstruiască textura

spre interiorul obiectului
ș
ters cu ajutorul filtrului laplacian care este propagat de-a lungul

direc
ț
iilor izofotelor. Met oda Total Varia
ț
ională definită de Tony Chan
ș
i Jianhong Shen [12]

folose
ș
te o ecua
ț
ie Euler-Lagrange împreună cu difuzia anizotrop ă
pentru a men
ț
ine

4
direc
ț
iile
​
izofot
​
elor. De a semenea Tony Chan
ș
i Jianho ng Shen mai au o implementare care

îmbunătă
ț
e
ș
te metoda total varia
ț
ională prin propagarea difuziei pe direc
ț
iile izofotelor,

permi
ț
ând restaurarea zon elor pu
ț
in mai mari.

Toate tehnicile men
ț
ionat e mai sus rezolva o ecua
ț
ie diferen
ț
ială par
ț
ială cu ajutorul cărora se

descrie propagarea culorilor în zona care trebuie reconstituita. De
ș
i prezervarea izofotelor

este dorită, în practică nu este întotdeauna reu
ș
ită, principala problema fiind ca atât

aproximarea izofotelor cât
ș
i propagarea informa
ț
iilor sunt supuse difuziei numerice. De
ș
i

difuzia numerică este dorită pentru ca stabilizează rezultatul ecua
ț
iei diferen
ț
iale par
ț
iale,

crează inevitabil o anumită cantitate de zgomot în zona reconstituită.

Manuel Oliveira
ș
i asocia
ț
ii săi au descris o metodă bazată pe con volu
ț
ii[6] în care aplică un

filtru de trei pe trei pixeli peste regiunea
ș
tearsă pentru a propaga informa
ț
iile din imagine

spre zona care trebuie reconstituită, însă
ș
i de această dată reconstituirea are rezultate

satisfăcătoare doar în cazul regiunilor cu dimensiuni reduse.

4
difuzia
anizotropă
–
reprezintă
o
tehnică
care
are
ca
scop
reducerea
zgomotului
fără
a

provoca
daune
par
ț
ilor
importante
din
imagine,
de
obicei
margini,
linii
ș
i
alte
detalii
care
sunt

importante în interpretarea imaginii

10

De
ș
i impresionante, meto dele descrise mai sus au câteva neajunsuri care împiedică utilizarea

lor în practică. Metodele bazate pe ecua
ț
ii diferen
ț
iale par
ț
iale necesită implementarea

netriviala a unor metode numerice iterative
ș
i tehnici, precum difuzia anizotropă. Informa
ț
iile

despre implementarea practică sunt pu
ț
ine spre deloc, detalii precum diferite praguri sau

metode de difuzie lipsesc,
ș
i unii pa
ș
i sunt descri
ș
i ca fiind instabili numeric. Mai mult decât

atât astfel de metode sunt destul de lente, de exemplu durează câteva minute pentru regiuni

relativ mici precum cele din Figura 1.1, în contrast metoda propusă de Oliveira[6] este rapidă,

relativ u
ș
or de implement at, însă această metodă nu are mecanisme pentru a conserva

direc
ț
iile izofotelor.

În figura 1.2 se observa rezultatul algoritmului lui Manuel Oliveira[6] dar
ș
i rezultatul lui

Marcelo Bertalmio[6], principala diferen
ț
ă notabilă fiind timpul raportat de către ace
ș
tia,

algoritmii rulând pe ma
ș
ini asemănătoare.

11

Un algoritm de reconstituire bazat pe exemplu care are rezultate bune dar nu este eficient din

punct de vedere computa
ț
ional, este algoritmul dezvoltat de Antonio Criminisi
ș
i asocia
ț
ii

săi[2], însă din nou timpul necesar reconstituirii unei imagini fiind destul de lung. Dacă

timpul nu este o problema algoritmul lui Antonio Criminisi[2] are rezultate bune chiar
ș
i în

reconstituiri mai complexe, care implică regiuni mari, reu
ș
ind să păstreze atât partea

structurală cât
ș
i texturile , însă algoritmul are dezavantajele lui,
ș
i anume structurile curbate

sunt problematice având în vedere faptul ca algoritmul trebuie să găsească în imaginea

curentă o por
ț
iune potrivi tă.

Algoritmii care se bazează pe exemplu, func
ț
ionează precum o metodă de
ș
teaptă de copiere
ș
i

lipire. În figura 1.3 b se observă rezultatul remarcabil al acestui algoritm fiind greu de

remarcat că o parte a acestei imagini a fost reconstituită de o ma
ș
ină .

12

În momentul de fa
ț
ă,

probabil cea mai avansată

metodă disponibilă de a

reconstitui anumite zone

din imagini este

dezvoltată de o echipă de

cercetători de la Nvidia

condu
ș
i de Guilin Liu[4].

Ei au prezentat o

tehnologie de ultimă oră

care folose
ș
te învă
ț
area

automată în scopul de

edita imagini sau a reconstrui o imagine care are găuri sau ii lipsesc por
ț
iuni de pixeli.

Metoda poate fi folosită pentru editarea imaginilor prin eliminarea con
ț
inutului
ș
i

reconstituirea regiunii
​

​
rezultate.

Metoda, care efectuează un proces de reconstituire a imaginii, ar putea fi implementată în

diferite programe de editare a fotografiilor pentru a elimina con
ț
inutul nedorit, în timp ce îl

umple cu o alternativă realistă generată de calculator. Pentru a-
ș
i pregăti re
ț
eaua neuronală,

echipa a generat prima dată 55 000 de scenarii de reconstituire, de forme
ș
i dimensiuni

arbitrare pentru a antrena re
ț
eaua neuronală. De asemenea, au generat aproape 25 000 de

teste. Acestea au fost în continuare clasificate în diferite categorii pe baza dimensiunilor

relative la imaginea de reconstituit, pentru a îmbunătă
ț
i acurate
ț
ea reconstruc
ț
iei. Pentru

pregătirea re
ț
elei neurona le echipa s-a folosit de clusterul companiei, numit NVIDIA®

Tesla® V100 Tensor Core
, acest cluster fiind format din placi video de înaltă performan
ț
ă

5
optimizate pentru antrenarea inteligentei artificiale. În timpul testării s-au reconstituit regiuni

complexe de diferite mărimi pentru a valida acurate
ț
ea metodei în scenarii diferite. Guilin Liu

5
NVIDIA®
Tesla®
V100
Tensor
Core
–
cel
mai
avansat
cluster
de
procesoare
grafice

construit
vreodată
pentru
accelerarea
antrenării
inteligentei
artificiale,
un
singur
procesor

grafic reu
ș
ind să ob
ț
ină performanta a 100 unită
ț
i centrale de procesare (CPU) [4].

13

ș
i echipa lui au afirmat ca sunt primii care demonstrează eficien
ț
a reconstituirii bazată pe

inteligenta artificială reu
ș
ind să repare diferite modele de forme iregulare.

Pentru a demonstra performantele acestei tehnici cei de la Nvidia au publicat un videoclip[15]

în data de 23 aprilie 2018 în care rezultatele sunt excelente atât din punct de vedere vizual

cât
ș
i din punctul de vede re al timpului necesar reconstituirii (dacă nu se ia în calcul perioada

de antrenare a re
ț
elei neu ronale). În figura 1.4 se poate observa rezultatul acestei metode. Un

alt dezavantaj major îl reprezinta faptul ca nu oricine are acces la un cluster precum a celor de

la Nvidia astfel de
ș
i o me todă excelentă de a reconstitui imagini problema nu este în totalitate

rezolvată încă.

Pe lângă metodele prezentate mai sus, în momentul de fa
ț
ă există aplica
ț
ii pentru sisteme care

rulează Windows sau Mac, de exemplu Adobe Photoshop, care folose
ș
te un algoritm hibrid,

acesta folose
ș
te atât recon stituirea bazată pe exemplu cât
ș
i cea bazată pe sinteza de textură,

însă acestea nu oferă posibilitatea reconstituirii automate în mod gratuit.

14

Capitolul 2. Caracteristici ale aplica
ț
iilor
ș
i tehnologiilor web

2.1 Introducere

Termenul “web” este o prescurtare ce provine de la termenul World Wide Web (WWW)
ș
i

reprezintă totalitatea informa
ț
iilor compuse din structuri de tip hipertext(html)
ș
i alte tipuri de

resurse imagini, fi
ș
iere au dio, videoclipuri care sunt legate între ele. Acestea pot fi utilizate
ș
i

accesate prin intermediul internetului, fiind accesate printr-un identificator unic, numit URL

(uniform resource locators). Aceste resurse sunt randate
ș
i afi
ș
ate cu ajutorul programelor de

navigare dezvoltate de-a lungul timpului, numite navigatoare web(browser).

2.2 Prezentare generală

Principalele tehnologii cu ajutorul cărora se dezvolt
​
ă
​
aplica
ț
iile web sunt: HTTP – reprezintă

un protocol folosit transferul de informa
ț
ii
ș
i resurse la nivelul aplica
ț
iilor HTML – limbajul

folosit pentru scrierea informa
ț
iilor de tip hipertext.

Cu ajutorul tehnologiilor men
ț
ionate mai sus, se pot dezvolta aplica
ț
ii de tip web, însă pentru

a dezvolta o aplica
ț
ie com plexă
ș
i u
ș
oară de utilizat sunt necesare
ș
i alte tehnologii. În acest

scop au apărut diverse limbaje de programare
ș
i scriptare a acestor informa
ț
ii care ajută la

dezvoltarea u
ș
oară
ș
i rapidă a aplica
ț
iilor. Printre acestea sunt de luat în considerare limbajele

de programare ce sunt utilizate pe partea de server (PHP, Java, C#..) cât
ș
i cele pe partea de

client (JavaScript, jQuery…), dar nu în ultimul rând limbaje cu ajutorul cărora se

înfrumuse
ț
ează interfa
ț
a grafica(CSS – Cascading Style Sheets). U nele din aceste limbaje de

programare vor fi prezentate în capitolele ce urmează.

2.3 Componentele principale

Componentele principale ale aplica
ț
iilor web sunt formate din cele două tehnologii precizate

mai sus,
ș
i anume: HTTP
ș
i HTML. Pentru dezvoltarea unei aplic a
ț
ii web simple sunt

15

suficiente cele două, însă pentru aplica
ț
ii complexe sunt necesare folosirea mai multor

limbaje de programare, scripting
ș
i de stilizare.

2.3.1 Redactarea documentelor web – HTML

Limbajul HTML (
​
H
​
yper
​
T
​
ext
​
M
​
arkUp
​
L
​
anguage) este un limbaj de marcare (limbaj

hipertextual) care se bazează pe un stil de compozi
ț
ie numit markup. Acest tip de fi
ș
ier

markup, se referă la o secventă de caractere sau simboluri speciale, numite etichete, ce sunt

inserate la nivelul unui text pentru a putea fi ulterior interpretate de un browser. Randarea

diferită poate fi realizată la nivelul fontului textului, culoarea, dimensiunea sau pozi
ț
ia.

Modificarea textelor de tip HTML se realizează cu orice editor de text.

Din punct de vedere sintactic, tag-urile de tip HTML sunt reprezentate ca fiind simboluri

sugestive delimitate de paranteze unghiulare (< , >). Tagurile sunt folosite cel mai des în

perechi, având ca rol delimitarea unei por
ț
iuni de text ce prime
ș
te proprietatea respectivă.

Prin urmare, textul ce prime
ș
te o proprietate va fi încadrat intre o etichetă de start la început

ș
i o etichetă de final la sfâ r
ș
it, etichetă ce va avea în plus fa
ț
ă de cea ini
ț
ială simbolul “/”. De

exemplu, eticheta de început <div> are eticheta de sfâr
ș
it “</div>”.

Având în vedere evolu
ț
ia în timp a fi
ș
ierelor de tip HTML, s-a co nstatat un progres imens la

nivel de dezvoltare
ș
i inte rpretare a acestora. Astfel că, dacă la începutul apari
ț
iei fi
ș
ierelor de

tip HTML, se foloseau etichete simple care în combina
ț
ie ofereau rezultatul dorit, acum

limbajul de markup s-a dezvoltat (HTML 5), oferind utilizatorilor
ș
i dezvoltatorilor

posibilită
ț
i ce duc la o mu ncă mai u
ș
oară
ș
i mai rapida. S-au introdus diferite tag-uri noi care

oferă aceea
ș
i func
ț
ionalitate cu o combina
ț
ie mult mai complicată de etichete din versiunile

anterioare, având ca scop dezvoltarea unor aplica
ț
ii web mai complexe într-un mod mai u
ș
or.

Pentru a oferi aplica
ț
iilor web o structură mai dinamică se pot adăuga scripturi ce se vor

executa la încărcarea paginii în browser sau la apari
ț
ia unui eveniment în pagină. JavaScript

este cel mai des folosit limbaj de scripting. Codul JavaScript se poate insera în interiorul

paginii HTML cu ajutorul etichetelor de tip: <script>cod</script>. Una din marile schimbări

16

care a venit împreună cu apari
ț
ia versiunii HTML 4, este introdusă
ș
i proprietatea de stilizare

a tagurilor html printr-un nou tip de limbaj de stil, numit CSS (
​
Cascade Style Sheet
​
).

2.3.2 Protocolul HTTP

Protocolul HTTP (
​
H
​
yper
​
T
​
ext
​
T
​
ransfer
​
P
​
rotocol) reprezintă cea mai utilizată metodă ce are

ca scop accesarea informa
ț
iilor care sunt
ț
inute pe serverele de tip World Wide Web. HTTP

reprezintă protocolul implicit al aplica
ț
iilor web. De asemenea protocolul HTTP presupune că

dispozitivul ce are rolul de “destina
ț
ie” poate în
ț
elege protocolul. Fi
ș
ierele transmise intre

server
ș
i client pot fi docu mente HTML, fi
ș
iere grafice, audio, anima
ț
ie, video, etc.

Protocolul HTTP este creat cu scopul de a realiza schimburi, într-un mod distribuit, în

internet
ș
i drept urmare e xploatează un sistem standard de adresare a resurselor. Resursele

HTTP sunt identificate prin URL
, având următorul format:

6
http://<host>[:port][<path>[?<query>]

Modul de func
ț
ionare est e dat prin tehnica de comunicare prin care paginile web sunt

transmise de la un calculator la altul, aflate la o distan
ț
ă oarecare unul fa
ț
ă de celălalt. Ca

prim pas, este accesat un URL (ex: http://www.exemplu.ro) prin care se cere afi
ș
area unor

informa
ț
ii de tip html. Ca proces principal, în primă fază numele URL-ului este convertit de

6
​
URL
–
reprezintă
un
localizator
uniform
de
resurse,
acesta
este
reprezentat
printr-o
secven
ț
ă

de
caractere
folosită
în
denumirea,
localizarea
ș
i
identificarea
unor
resurse
sau
pagini
în

Internet.

17

protocolul DNS într-o adresă IP. Cu ajutorul protocolului TCP (Transmission Control

Protocol) pe portul 80 al serverului HTTP, este transmisă informa
ț
ia cerută. Răspunsul

returnat poate să con
ț
ină informa
ț
ii aleatoare cu privire la cererea realizată ini
ț
ial (Figura 1.1).

Câteva aspecte de precizat necesare asupra protocolului HTTP, aspecte ce au stat la baza

dezvoltării aplica
ț
iilor de tip web:

–
Interac
ț
iunea între client
ș
i server are loc doar în momentu l în care clientul solicită

serverului informa
ț
ii, serverul nu poate trimite date care nu au fost cerute. Astfel,

informarea clien
ț
ilor nu poate fi utilizată doar dacă se folose
ș
te protocolul HTTP.

–
Protocolul HTTP folose
ș
te asa numitele metode pentru a comunica, fiecare metodă în

parte având scopuri diferite. Aceste metode sunt: GET, HEAD, POST, PUT,

DELETE, CONNECT, OPTIONS, TRACE, PATCH.

–
Fiecare cerere a unui client este interpretată
ș
i tratată de serverul web independent.

Astfel că în cazul în care un client trimite două cereri, serverul va interpreta

independent, la fel ca
ș
i cum ar veni cererile de la doi clien
ț
i diferi
ț
i.

–
În cazul în care se dore
ș
te păstrarea unui istoric asupra cererilor
ș
i răspunsurilor între

un client
ș
i un ser ver, datorită proprietă
ț
ilor protocolului H TTP, care nu re
ț
ine în

niciun fel o sesiune a unui client, va fi nevoie de o implementare externă, utilizând

alte proceduri de a stoca informa
ț
iile sau sesiunile.

–
De asemena protocolul HTTP de
ț
ine o rutină de a trata răspunsurile, fiecare răspuns

având un cod unic, aceste coduri fiind împăr
ț
ite în 5 categorii:

–
1xx – răspuns informa
ț
ional care indic
​
ă
​
c
​
ă
​
cererea a fost transmisă
ș
i în
ț
eleasă

–
2xx – indica c
​
ă
​
cererea a fost primit
​
ă
​
în
ț
eleasă
ș
i acceptată

–
3xx – arat
​
ă
​
c
​
ă
​
utilizatorul trebuie să facă pa
ș
i suplimentari, în general se

folose
ș
te în cazul redirectărilor către alte URL-uri

–
4xx – acest tip de răspuns este folosit pentru a semnala probleme pe partea de

client

–
5xx – indic
​
ă
​
o eroare pe partea de server

2.3.3 Limbajul de scriptare Javascript

Partea de interfa
ț
ă cu util izatorul reprezintă un element important în ziua de azi, când clien
ț
ii

18

doresc o interfa
ț
ă u
ș
or de folosit, func
ț
ională dar
ș
i frumoasă din punct de vedere al

design-ului.

Pentru a rezolva unele probleme în interac
ț
iunea intre utilizator
ș
i site web a fost creat

limbajul de scriptare JavaScript (JS) care reprezintă un limbaj de programare de nivel înalt

orientat obiect. Alături de HTML
ș
i CSS face parte din principalele tehnologii folosite în

WWW pentru crearea aplica
ț
iilor. Acest limbaj de programare este folosit
ș
i pentru

introducerea unor func
ț
ionalită
ț
i pe paginile web, scriptul fiind ru lat
ș
i interpretat la fel ca
ș
i

limbajul HTML, de către browser. Datorit
​
ă
​
dezvoltării din ultimii ani prin intermediul

limbajului JavaScript s-au creat diferite librarii, cu ajutorul cărora se pot crea de la aplica
ț
ii

mobile pană la servere care au în spate limbajul JavaScript.

Limbajul JavaScript de bază constă în câteva func
ț
ii comune care permit următoarele ac
ț
iuni:

-Stocarea valorilor utile în interiorul variabilelor pentru folosirea lor ulterioară.

-Opera
ț
ii pe
ș
iruri de caractere.

-Rularea codului ca răspuns la anumite evenimente care apar pe o pagină web.

Sunt cunoscute câteva proprietă
ț
i ale limbajului de scripting JavaScript:

–
reprezintă un limbaj dependent de mediu, astfel încât fiind un limbaj de scriptare, el

rulează la nivelul browserului fiind în totalitate interpretat
ș
i rulat de către acesta.

Codul este în totalitate interpretat de browser înainte de a fi executat. Prin urmare nu

necesită compilări sau preprocesări, ci rămâne parte integrantă a documentului

HTML.

–
are posibilitatea de fi introdus în fi
ș
iere format HTML – majoritatea obiectelor

JavaScript au etichete HTML pe care le reprezintă, astfel încât programul este inclus

pe partea de client.

–
marea majoritate a codului scris în JavaScript este bazat pe evenimentele care au loc

la nivelul interfe
ț
ei cu utilizatorul. De asemenea poate răspunde
ș
i la evenimente

generate de sistem.

În ceea ce prive
ș
te sintax a limbajului de programare JavaScript, aceasta este asemănătoare cu

codul limbajului de programare C++. De asemenea acest limbaj de
ț
ine o amplă listă rutine
ș
i

19

comenzi ce au rol să ajute la manipulări de
ș
iruri, opera
ț
ii matematice, sunete, videoclipuri,

imagini, obiecte
ș
i ferestr e ale browserului, validări de introducere a datelor
ș
i altele. În

lucrarea curentă folosindu-se numeroase metode care lucrează cu canvasul. Acest element

html fiind principala resursă folosita de aplica
ț
ie, în el fiind încărcată imaginea digitală.

Javascript are metode pentru manipularea acestei imagini.

Evolu
ț
ia JavaScript este f oarte rapidă, dorindu-se aducerea multor func
ț
ionalită
ț
i pe care o

aplica
ț
ie web le realizeaz ă pe server, pe partea de client. De asemenea este din ce în ce mai

utilizat datorită proprietarilor sale putând fi interpretat pe majoritatea dispozitivelor

electronice, ajutând la dezvoltarea multor tehnologii. Una dintre cele mai cunoscute librarii

care au la baza limbajul JavaScript este jQuery
.
​
Acesta este conceput pentru a u
ș
ura
ș
i

7
îmbunătă
ț
i procese precu m traversarea arborelui DOM în HTML, managementul

inter-browser al evenimentelor, anima
ț
ii
ș
i cereri tip
​
AJAX
. jQuery a fost gândit să aibă un

8
impact al performantei cât mai mic posibil
ș
i să respecte filosofia Unobtrusive JavaScript
.

9

Un alt aspect important al limbajului JavaScript îl reprezintă web workers, cu ajutorul

acestora este posibilă rularea în fundal a mai multor fire de execu
ț
ie fără a interfera cu

interfa
ț
a grafică. Odată c reat, un web worker poate trimite mesaje către codul JavaScript care

l-a creat prin postarea mesajelor într-un manager de evenimente specificat de codul respectiv

ș
i invers, reu
ș
ind să reducă considerabil timpul necesar pentru pre lucrarea imaginii.

7
jQuery – jQuery este o bibliotecă care face mai rapidă
ș
i mai u
ș
oară să construirea

paginilor Web
ș
i aplica
ț
iilor web JavaScript. De multe ori cu jQu ery se poate scrie o singură

linie de cod pentru a realiza ceea ce ar fi luat 5-10 de linii de cod JavaScript obi
ș
nuit.[3]

8
AJAX – reprezintă un grup de tehnologii de dezvoltare bazate pe arhitectura

client-server care permit păr
ț
ilor de pagină web să fie actualizate fără a trebui ca pagina să fie

reîncărcată . [14]

9
Unobtrusive JavaScript – este o metodologie de bune practici pentru adăugarea

codului JavaScript pe partea de client a unui site web. [1]

20

Capitolul 3. Implementarea aplica
ț
iei

3.1 Definirea problemei

De multe ori s-a întâmplat ca după o vacan
ț
ă în care s-au făcut numeroase fotografii, unele

din aceste fotografii să fie compromise de anumite detalii nedorite, astfel anumite persoane

pot avea dorin
ț
a de a
ș
terge obiecte din fotografiile făcute. Acesta nu este singurul motiv

pentru a reconstitui imagini. Asemenea dorin
ț
ă de a
ș
terge zone din imagini poate avea

diferite scopuri, de la restaurarea unor picturi sau fotografii care au suferit modificări datorită

factorilor externi, eliminarea subtitrărilor, zgârieturilor. Obiectivul acestei lucrări este de a

dezvolta o aplica
ț
ie web c u ajutorul căreia un utilizator poate modifica fără soft specializat

imagini digitale reu
ș
ind s ă elimine
ș
i să umple locul unor obiecte nedorite dintr-o imagine, cu

texturi
ș
i structuri, într-un mod automat
ș
i insesizabil ochiului uman.

3.1.1 Interac
ț
iunea cu utilizatorul

Proiectul este împăr
ț
it în două păr
ț
i principale, o parte care asigur ă interac
ț
iunea cu

utilizatorul
ș
i o parte care se ocupă de opera
ț
iunile de reconstituire pe baza datelor de intrare

procesate în prima parte.

Func
ț
ionalită
ț
ile de bază ale aplica
ț
iei sunt:

–
încărcarea unei imagini digitale

–
alegerea regiunii nedorite

–
reconstituirea regiunii alese

–
descărcarea imaginii rezultate în urma reconstituirii

Totodată aplica
ț
ia oferă f unc
ț
ionalitatea de a anula modificările fă cute
ș
i de a le reface.

Interac
ț
iunea cu aplica
ț
ia este una simplă (figura 3.1.1), odată aju ns pe aplica
ț
ia, utilizatorul

trebuie să încarce imaginea dorită, să selecteze partea din imagine care vrea să fie

reconstituită(masca)
ș
i să aleagă unul din cei doi algoritmi oferi
ț
i. Ace
ș
ti algoritmi încep

reconstituirea la apăsarea butonului corespunzător fiecărui algoritm.

21

Imaginea încărcată de utilizator este reprezentată sub forma unui vector bidimensional de

pixeli reprezenta
ț
i în spa
ț
iul de culoare RGBA
. Odată încărcată imaginea, utilizatorul

10
folose
ș
te cursorul pentru a alege regiunea nedorită, aplica
ț
ia colorează pixelii din jurul

cursorului( cu raza selectată de utilizator ), cu verde. Ace
ș
ti pixeli reprezintă masca imagini,

ce trebuie reconstituită. După crearea mă
ș
tii utilizatorul alege unul din algoritmii prezenta
ț
i în

sub-capitolele următoare pentru a reconstitui imaginea. Dacă rezultatele sunt mul
ț
umitoare,

utilizatorul are posibilitatea de a descărca imaginea reconstituită.

3.1.2 Necesitatea celor doi algoritmi

În urma studierii literaturii prezentate în primul capitol se poate deduce faptul ca în momentul

de fa
ț
ă nu există o rezolv are optimă pentru toate situa
ț
iile, în vederea acoperirii unui număr

cât mai mare de scenarii care pot fi rezolvate de aplica
ț
ia propusă, am ales să implementez

două metode de reconstituire a imaginii fiecare metodă bazându-se pe algoritmi existen
ț
i,

unul rapid care face parte din familia algoritmilor care folosesc sintetizarea texturii
ș
i altul

reprezentând un algoritm bazat pe exemplu. Datorită celor două metode de reconstituire a

10
RGBA – spa
ț
iu de culo are, fiecare pixel este reprezentat prin cantitatea de lumina ro
ș
ie,

verde
ș
i albastra con
ț
inută, alfa fiind folosit pentru a indica nivelu l de opacitate al culorii

22

imaginii aplica
ț
ia web ofe ră utilizatorilor posibilitatea de a alege ceea ce li se potrive
ș
te,

fiecare metodă venind cu propriile avantaje
ș
i dezavantaje.

Termeni utiliza
ț
i în urmă toarele explica
ț
ii
ș
i semnifica
ț
ia

acestora:

–
Imagine : I

–
Regiunea de reconstruit : Ω

–
Regiunea sursă (I – Ω) :
Φ

-Marginea regiunii de reconstruit : ઠ Ω

3.2 Metoda rapidă

Metoda propusă de prof. dr. Alexandru Telea în lucrarea sa [11] reprezintă o evolu
ț
ie majoră

fa
ț
ă de metodele care folo sesc ecua
ț
ii diferen
ț
iale par
ț
iale pentru a aproxima direc
ț
ia

izofotelor. Metoda descrisă în lucrarea [11] se bazează pe un algoritm care are ca obiectiv

propagarea unei estimări fluente a imaginii de-a lungul gradientului imaginii.

Algoritmul, folose
ș
te Fas t Marching Method
[10] pentru a propaga informa
ț
iile imaginii în

11
regiunile
ș
terse, având an umite avantaje precum:

–
u
ș
urin
ț
a implementării(pseudocodul algoritmului fiind dis ponibil în lucrarea[11])

–
este considerabil mai rapidă decât alte metode de reconstituire, procesarea unei

imagini, având dimensiune de 800 X 600 pixeli, durează mai pu
ț
in de trei secunde

–
are rezultate similare cu celelalte metode care se bazează pe sintetizarea texturii

11
Fast Marching Method – metodă numerică creată de prof. dr. James Sethain pentru a

rezolva problemele valorilor limită a ecua
ț
iei eikonale.

23

3.2.1 Modelul matematic

Pentru a explica metoda propusă de prof. dr. Alexandru Telea, se consideră figura 3.2.1

În această figură se dore ș te reconstituire a punctului p situat pe mar ginea ( ઠ Ω) regiunii de

reconstituit (Ω). Se ia o mică vecinătate B
​
ε
​
(p) de raza ε din regiunea cunoscută din jurul

punctului p (figura 3.2.1 a), reconstituirea acestui punct ar trebui să se determine de pixelii

cunoscu
ț
i
ș
i apropia
ț
i (B
​
ε
​
(p)). Pentru o raza(ε) destul de mică, se consideră o aproximare de

nivel primar I
​
q
​
(p) a imaginii în punctul p, dându-se imaginea I(q)
ș
i gradientul
∇
I(q) valorile

punctului q(figura 3.2.1 b) :

(3.2.1)
q
(
p
)

I
(
q
)

∇
I
(
q
)
(
p
)

I
=

+

−
q

În următorul pas se reconstituie punctul p în func
ț
ie de toate punctele q
∈
B
​
ε
​
(p) însumând

estimarea tuturor punctelor q, ponderată de o func
ț
ie de ponderare normalizată:
(3.2.2)
(
p
)

I
=

∈
B
ε
(
p
)

w
(
p
,

q
)
∑

q
∈
B
ε
(
p
)

w
(
p
,

q
)
[
I
(
q
)

+

∇
I
(
q
)
(
p

−

q
)
]

∑

q
*

Func
ț
ia de ponderare w(p ,q) detaliată în capitolele următoare, este făcută în a
ș
a fel încât în

reconstituirea punctului p să se propage atât culoarea cât
ș
i detaliile proeminente din B
​
ε
​
(p).

3.2.2 Folosirea Fast Marching Method pentru reconstituire

În sub capitolul precedent s-a explicat cum se poate reconstitui un punct care apar
ț
ine de

marginea regiunii
ș
terse f olosind pixelii cunoscu
ț
i din vecinătate. Pentru reconstituirea

întregii regiuni(Ω), se parcur ge iterativ fiecare punct apar ț inând mar gini obiectului ș ters ( ઠ Ω)

ș
i se aplică ecua
ț
ia 3.2.2, avansându-se strat cu strat până când to ată regiunea a fost

reconstituită. Reconstituind strat cu strat ne asigurăm de faptul c
​
ă
​
pixelii apropia
ț
i de zona

cunoscută sunt refăcu
ț
i primii.

Implementarea algoritmului descris mai sus necesită o metoda care propaga schimbările

punctelor din mar gine ઠ Ω în func ț ie de d istanta fa ț ă de mar ginea ini ț ială ઠ Ω
i
​
, pentru aceasta

24

se folose
ș
te Fast Marchin g Method[10], la baza acesta fiind un algoritm care rezolvă ecua
ț
ia

Eikonala :

în Ω pentru T = 0 în ઠ Ω (3.2.3)

∇
T
|
|
=
1

Solu
ț
ia T a ecua
ț
iei 3 reprezentând distanta dintre pixelii din cent rul Ω pana la marginea

acestuia ઠ Ω. Izoliniile lui T reprezentând exact mar ginile succesive( ઠ Ω) al zonei de

12
reconstituit care se mic
ș
orează. Normala N necesară reconstituirii este exact
. Fast
T
∇

Marching Method garantează faptul ca pixelii conturului zonei de reconstituit, sunt procesa
ț
i

în ordinea crescătoare fa ț ă de distanta lo r de mar ginea ini ț ială ( ઠ Ω
i
​
). Pentru fiecare pixel din

imagine se păstrează valoarea T, culoarea ,
ș
i o variabila f care poate avea următoarele valori:

-Margine – pixelul apar ț ine bandei îngust e ( ઠ Ω)

-Cunoscut – pixelul se afla în afara mar ginii ( ઠ Ω), ii sunt cunoscute atât culoarea cât ș i

valoarea T

–
Necunoscut – pixelul se afla în interiorul zonei de reconstituit, culoarea
ș
i valoarea T

încă nu sunt cunoscute

Algoritmul are nevoie de ini
ț
ializare, având nevoie să se seteze pixelii cunoscu
ț
i cu valoarea

0, iar cei din interiorul por
ț
iuni
ș
terse cu o valoare cât mai mare, p recum
ș
i setarea variabilei

f după instruc
ț
iunile de m ai sus. To
ț
i pixelii de tipul Margine sun t introdu
ș
i într-un heap

sorta
ț
i în ordine crescătoa re în func
ț
ie de valorile lor T. În continu are se propagă pixelii spre

mijlocul regiunii
ș
terse.

3.2.3 Func
ț
ia de pondere w

Func
ț
ia de ponderare repr ezintă produsul a trei termeni:

–
termenul direc
ț
ional – acesta se asigură că pixelii mai apropia
ț
i de normala N au o

pondere mai mare fa
ț
ă de cei mai depărta
ț
i de N, astfel ob
ț
inându-se o propagare mai

bună a direc
ț
iei

–
termenul geometric – garantează ca pixelii mai apropia
ț
i de pixelul care trebuie

reconstituit, să aibă o pondere mai mare fa
ț
ă de cei mai depărta
ț
i

12
izolinie – linia care une
ș
te puncte cu aceea
ș
i valoare a unei mărimi oarecare

25

–
termenul izoliniilor – are rolul de a m
​
ă
​
ri ponderea finală a pixelilor cunoscu
ț
i mai

apropia
ț
i de contu rul regiunii care trebuie reconstituită

Pentru demonstrarea utilită
ț
ii func
ț
iei de ponderare se poate obser va figura 3.2.2. În această

imagine de test se poate observa clar rezultatul fiecărui factor în parte, factorul direc
ț
ional fig.

3.2.2c), factorul geometric fig. 3.2.2 d), factorul izoliniilor fig. 3.2.2 e), iar în fig. 3.2.2 f)

rezultatul factorilor utiliza
ț
i deodată. Utilizarea celor trei factori împreună, produce cele mai

bune rezultate(fig. 3.2.2 f).

În ansamblu ace
ș
ti factor i descriu modul de a colora un pixel în func
ț
ie de vecinătatea lui.

Am ales acest algoritm deoarece produce rezultate bune
ș
i rapide în reconstituirea regiunilor

de mici dimensiuni, din imagini.

3.3 Metoda lentă

În ultima perioadă, metodele de reconstituire bazate pe exemplu au fost tot mai mult abordate

de diferi
ț
i cercetători din cauza rezultatelor bune pe care aceste metode le produc. Tehnica

folose
ș
te păr
ț
ile vizibile din imagine drept un set de posibile surse , cu care se poate

reconstitui imaginea. În acest fel zona
ș
tearsă este replicată, nu sintetizată, folosind

informa
ț
iile disponibile. C omparată cu celelalte metode de reconstituire această metodă nu

produce degradări ale imaginii
ș
i se poate folosi atât pentru regiuni mici cât
ș
i pentru regiuni

mari. Unul din algoritmii care produce rezultate bune este algoritmul[2] lui Antonio

Criminisi, acest algoritm va fi detaliat mai mult în sub-capitolele următoare.

26

În general un algoritm bazat pe exemplu include următorii trei pa
ș
i:

–
calcularea priorită
ț
ilor – o func
ț
ie de calculare predefinită este folosită pentru a calcula

prioritatea tuturor pixelilor care apar ț in marginii regiunii de reconstituit.( p ∈ ઠ Ω ),

la începutul fiecărei itera
ț
ii în parte

–
căutarea celei mai potrivite regiuni din imagine pentru punctul curent

–
replicarea regiunii găsite în pasul anterior

3.3.1 Ordinea reconstituirii

Ordinea reconstituirii este foarte importantă,

aceasta este dată de o func
ț
ie care se asigură

că structurile liniare sunt propagate înainte de

textură pentru a asigura conectivitatea

muchilor obiectelor. Pentru fiecare pixel (p

∈ ઠΩ) prioritatea este calculată ca produsul

a doi termeni:

P(p)=C(p)*D(p) (3.3.1)

Termenul de confidentă C(p)
ș
i termenul de

date D(p). Termenul de confiden
ț
ă este

utilizat pentru a reprezenta textura din vecinătatea punctului de reconstituit, iar termenul de

date reprezintă structura vecinătă
ț
ii. Ace
ș
ti termeni sunt defini
ț
i de următoarele ecua
ț
ii.

(3.3.2)
(
p
)

,
0
(
p
)
C
=
Ψ
p
|
|
∑

q
∈
Ψ
p
⋂
Φ

≤
C
≤
1

,
(3.3.3)
(
p
)
D
=
α
∇
I
n
|
p
⊥
*
p
|
(
p
)

0
≤
D
≤
1

unde, | Ψ
​
p
​
| este aria regiunii Ψ
​
p
​
,
este factorul de normalizare(ex
= 255),
izofota ,
α
α
∇
I
p
⊥
vectorul perpendicular pe ઠ Ω în punctul p. Dimensiunea ferestrei (Ψ) este în mod implicit
n
p

de 9×9 pixeli. În ceea ce prive
ș
te factorul de confidentă acesta este ini
ț
ializat cu C(p)=0
∀
p

∈
Ω,
ș
i C(p)=1
∀
p
∈

.
Φ

27

Factorul de confidentă poate fi considerat ca o măsură pentru informa
ț
iile de încredere din

jurul punctului p, scopul acestuia este de a reconstitui întâi ferestrele care au mai multă

informa
ț
ie originală. Fact orul de date folosit pentru a reprezenta izofotele(
) care se
∇
I
p
⊥

intersectează cu ઠ Ω, acest factor favorizează reconstituirea cu prioritate a regiunilor care

trebuie să continue structura obiectelor . Prioritatea P(p) este calculată pentru fiecare p ∈ ઠ Ω.

Efectul celor doi termeni de confidentă
ș
i de date

se poate observa în figura 3.3.2. Zonele cu verde

au prioritate mare de a fi reconstituite primele iar

regiunile cu rosu definesc o prioritate mai mică.

În figura 3.3.2 a se observă comportamentul

termenului de confiden
ț
ă, acesta bazându-se pe

datele de încredere din jurul punctelor,

extremită
ț
ile au prioritate a mai mare, iar regiunile

interioare au prioritate mai mică. În figura 3.3.2 b

se remarcă comportamentul termenului de date,

acesta oferă o prioritate mai mare continuării

structurilor imaginii. Combina
ț
ia dintre cele două

oferă un echilibru în ceea ce prive
ș
te ordinea

reconstituirii.

3.3.2 Găsirea celui mai potrivit exemplar

Odată ce s-au calculat priorită ț ile puncte lor ∀ p ∈ ઠ Ω, se găse ș te fereastra(Ψ
p
​
) cu cea mai

mare prioritate, această fereastră fiind reconstituită în itera
ț
ia curentă cu cea mai potrivită

fereastră găsită (Ψ
​
q
​
) din restul imaginii(
). Cea mai potrivită fereastră se determină după
Φ

următoarea formulă:

Ψ
​
q
​
= min(d(Ψ
​
q
​
,Ψ
​
p
​
)) (3.3.4)

28

unde: Ψ
​
q
​
∈
, d(Ψ
​
q
​
,Ψ
​
p
​
) este suma dintre pătratul diferen
ț
elor pixelilor ne
ș
ter
ș
i din cele 2
Φ

ferestre. Culoarea pixelilor este reprezentată în spa
ț
iul de culoare CIE Lab
din cauza

13
proprietă
ț
ilor de uniformi tate perceptuală, în acest sistem distan
ț
ele euclidiene intre culori

fiind mai bine conturate[2]. Conversia de la RGB către CIE Lab
ș
i invers, se face printr-o

conversie intermediară în spa
ț
iul de culoare XYZ[9] .

Astfel:

1) RGB L a*b*

a)
RGB XYZ:

X = 0.412453*R + 0.357580*G + 0.180423*B

Y = 0.212671*R + 0.715160*G + 0.072169*B

Z = 0.019334*R + 0.119193*G + 0.950227*B

b) XYZ L a*b*

L* = 116 * (Y/Yn)
​
1/3
​
– 16 pentru Y/Yn > 0.008856 altfel L* = 903.3 * Y/Yn

a* = 500 * ( f(X/Xn) – f(Y/Yn) )

b* = 200 * ( f(Y/Yn) – f(Z/Zn) )

unde f(t) = t
​
1/3
​
pentru t > 0.008856 altfel f(t) = 7.787 * t + 16/116

2) L a*b* RGB

a)
L a*b* XYZ

X = Xn * ( P + a* / 500 )
​
3

Y = Yn * P
​
3

Z = Zn * ( P – b* / 200 )
​
3

unde P = (L* + 16) / 116

b) XYZ RGB

R = 3.240479*X + -1.537150*Y + -0.498535*Z

G = -0.969256*X + 1.875992*Y + 0.041556* Z

B = 0.055648*X + -0.204043*Y + 1.057311* Z

13
CIE Lab – spa
ț
iu de cul oare, care exprima culorile în trei valori L -lumina, a – rosu-verde,

b – galben-albastru

29

3.3.3 Completarea ferestrei

Odată găsită cea mai potrivită fereastră( Ψ
​
q
​
), pixelii acesteia completează pixelii ferestrei

care trebuie reconstituită (Ψ
​
p
​
), actualizându-se atât noua mască cât
ș
i confiden
ț
a pixelilor

înlocui
ț
i.

Procesul descris se repetă pană când s-au reconstituit to
ț
i pixelii imaginii (Ω=0).

3.4 Contribu
ț
ii personale

Pentru a eficientiza algoritmul lent am ales să mic
ș
orez partea din imagine în care se caută cel

mai potrivit exemplar, din cauza faptului că probabilitatea ca acest exemplar să fie în

imediata vecinătate este destul de mare. Pentru determinarea por
ț
iunii din imagine în care se

caută exemplarul, se iau în considerare extremită
ț
ile mă
ș
tii, dimensiunea ferestrei

folosite(implicit 9×9). Calcularea ferestrei în care se va cauta cel mai bun exemplar se face o

dată pentru fiecare por
ț
iune care trebuie reconstituită, astfel se asigură o mic
ș
orare constantă

a timpului de căutare.

Pentru a calcula dimensiunea ferestrei în care se face căutarea, am venit cu următoarele

formule:

startX = max(0, vfN – Ψ
​
d
​
*C
​
x
​
) startY = max(0, vfV – Ψ
​
d
​
*C
​
y
​
)

endX = min(h, vfS + Ψ
​
d
​
*C
​
x
​
) endY = min(w, vfE – Ψ
​
d
​
*C
​
y
​
)

unde vfN,vfS,vfV.vfE sunt extremită
ț
ile mă
ș
tii fiecare punct reprezentând o coordonată

carteziană( nord, sud, est, vest ), Ψ
​
d
​
reprezintă dimensiunea ferestrei folosite de utilizator, h
ș
i

w înăl
ț
imea respectiv lă
ț
imea, iar C
​
x
​

ș
i C
​
y
​
reprezintă două constante predefinite. Pentru a

evita ie
ș
irea din imagine în cazul în care se reconstituie o por
ț
iune din marginea unei imagini,

am folosit func
ț
iile de mi nim
ș
i maxim, cu ajutorul cărora nu se v or depă
ș
i marginile

imaginii.

În ceea ce prive
ș
te numer oasele calcule care se fac pentru a determina cel mai potrivit

exemplar, am reu
ș
it să pa ralelizez o parte din acestea, în scopul de a reduce considerabil

timpul necesar reconstituirii. Metoda de paralelizare este una simplă,
ș
i anume, mă folosesc

30

de o func
ț
ionalitate pusă la dispozi
ț
ie de mediul de programare
ș
i anume javascript. Web

workerii, din javascript, crează thread-uri la nivelul sistemului de operare care pot executa în

paralel opera
ț
iuni, iar la t erminarea lor trimit informa
ț
iile către părinte, acesta din urmă

determinând cel mai potrivit exemplar. Astfel se reduce considerabil timpul necesar

reconstituirii.

De asemenea am modificat pu
ț
in func
ț
ia de prioritate din cauza fa ptului că aceasta nu se

descurcă foarte bine în cazul în care imaginea are mult zgomot, coeficientul de date fiind

puternic influen
ț
at de ace st zgomot, de

asemenea termenul de confidentă se apropie de

valori mici destul de rapid (fig 3.4), odată cu

avansul reconstituirii[13]. Asta face ca

priorită ț ile calculate pentru fiecare p ∈ ઠ Ω să

aibă valori apropiate, ordinea de reconstituire

fiind compromisă. Înmul
ț
irea este sensibila la

valori extreme
ș
i influen
ț
a lor este amplificată,

a
ș
a c
​
ă
​
func
ț
ia de prioritate în care se înmul
ț
esc

cei doi termeni de confiden
ț
​
ă
​

ș
i de date, trebuie

modificată. Folosind adunarea (P(p)=C(p)+D(p)) se pot ob
ț
ine priorită
ț
i mai stabile din punct

de vedere numeric, zgomotul având un impact mai mic asupra priorită
ț
ilor, însă datorită

diferen
ț
elor de comportam ent a curbelor termenului de confidentă
ș
i de date, adunarea nu este

sigură fără a modifica ace
ș
ti termeni. Astfel pentru a reduce apropierea confiden
ț
ei de valori

mici am ales să aplic termenului de confidentă o formulă pentru a tempera varia
ț
iile acestuia

în timpul reconstituirii. În consecin
ț
ă C(p) = 0.3*C(p)+0.7, unele din rezultatele ob
ț
inute fiind

promi
ț
ătoare.

De asemenea diferite imagini pot avea caracteristici diferite, astfel ca termenul de date
ș
i de

confidentă ar trebui să aibă ponderi diferite pentru a mari influenta lor asupra rezultatului

final. De exemplu într-o imagine unde se reconstituie în general structuri termenul de date ar

trebui să aibă o pondere mai mare, astfel prioritizându-se structura imaginii. Forma finală a

priorită
ț
ii este dată de for mula următoare: P(p)=
𝛼
*C(p)+(
𝛼
-1)*D(p) unde 0 <
𝛼
< 1. Variabila

31

𝛼
are valoarea implicită 0.5 pentru a oferi un echilibru pentru term enul de confidentă
ș
i de

date, ulterior utilizatorul poate să modifice acestă valoare.

3.5 Studiu de caz

După efectuarea unor teste, pot afirma ca algoritmul îmbunătă
ț
it se descurcă cel pu
ț
in la fel

de bine cu metoda propusă în [2], însă datorită avansului tehnologiei am reu
ș
it să reduc

drastic timpul de procesare, în unele situa
ț
ii reconstituirea terminându-se chiar de 5 ori mai

repede, rezultatul fiind asemănător după cum se poate observă în figura 3.7. Pentru

procesarea 3.7b au fost necesare aproximativ 2 minute în timp ce pentru 3.8c 15 secunde au

fost suficiente, imaginea având o rezolu
ț
ie de 400×400 pixeli

32

Capitolul 4. Concluzii

În dezvoltarea acestei aplica
ț
ii, am parcurs toate etapele dezvoltării unei aplica
ț
ii web

complexe. De la definirea paginii în format HTML, stilizarea acesteia folosind CSS p
​
â
​
nă la

implementarea algoritmilor utiliza
ț
i de această aplica
ț
ie în scopul de a reconstitui imagini

digitale.

Rezultatele algoritmului îmbunătă
ț
it sunt mul
ț
umitoare atât din punct de vizual c
​
â
​
t
ș
i în ceea

ce prive
ș
te timpul necesa r reconstituirii.

Din literatura prezentată în această lucrare următoarele concluzii pot fi trase:

–
Algoritmi care folosesc sinteza de textura
ș
i cei baza
ț
i pe exemplu sunt des folosi
ț
i

pentru a reconstitui imagini

–
Algoritmul lui Criminisi
ș
i asocia
ț
ii[2] lui este capabil să propage atât structura liniară

cât
ș
i textura bidim ensională în regiunea
ș
tearsă, cu un singur algoritm, simplu de

în
ț
eles, însă este l imitată când vine vorba de reconstituirea imaginilor în care nu

exista regiuni similare rezultatul nefiind satisfăcător, de asemenea algoritmul are

dificultă
ț
i în a ges tiona structurile curbate.

–
Reconstituirea bazată pe sintetizarea texturii aproximează bine, dar are dificultă
ț
i în a

trata imaginile naturale, ele fiind compuse din structuri
ș
i texturi complexe. Se

adresează unui mic subset de situa
ț
ii nefiind viabile când vine vorba de a reconstitui

par
ț
i mari din ima gine.

–
Printre numeroasele tehnici de reconstituire, cele care se bazează pe exemplu au

rezultate bune în majoritatea cazurilor fiind preferate atunci când vine vorba de a

elimina obiecte mari din imagini.

–
Algoritmii care se bazează pe sinteza de textura reu
ș
e
ș
te să umple partea
ș
tearsă

propagând structura liniară prin difuzie, însă în urma acestui proces rezultatul con
ț
ine

por
ț
iuni neclare.

Aplica
ț
ia poate fi dezvolt ată în continuare prin adăugarea de noi algoritmi mai performan
ț
i de

reconstituire, de asemenea se poate îmbunătă
ț
ii interac
ț
iunea cu utilizatorul prin oferirea unor

33

modalită
ț
i diferite de sele ctare a p
​
ă
​
r
ț
ii care trebuie reconstituită, de exemplu anumite

instrumente disponibile în programe precum Photoshop, oferă utilizatorilor posibilitatea de a

selecta obiecte din imagine după contur
ș
i culori.

Pe baza studiului literaturii de mai sus, putem deduce că s-au realizat pu
ț
ine evolu
ț
ii de-a

lungul anilor în domeniul reconstituirii imaginilor. Aceasta deschide un nou orizont pentru

cercetări viitoare în domeniul restaurării informa
ț
iilor structurale complexe cum ar fi portrete,

monumente deteriorate
ș
i artefacte istorice, imagini mici, precum
ș
i imagini mari. În prezent

pe lângă cele trei tipuri de algoritmi prezenta
ț
i în aceasta lucrare: sintetizarea texturii,

reconstituirea bazată pe convolu
ț
ii sau pe exemplu, se cercetează noi metode folosind atât

puterea de procesare existentă cât
ș
i inteligen
ț
a artificială în ob
ț
inerea unor rezultate mai bune

în reconstituirea imaginilor.

34

Bibliografie

[1] ChalkleyAndrew: What is Unobtrusive Javascript,

​

What is Unobtrusive JavaScript and Why it’s Important?

[2] Criminisi Antonio, P. Perez
ș
i K. Toyama :Region filling and object removal by

exemplar-based image inpainting,

http://www.irisa.fr/vista/Papers/2004_ip_criminisi.pdf

[3] Doyle Matt :What Is jQuery?,
​
https://www.elated.com/articles/what-is-jquery/

[4] Guilin Liu Fitsum A. Reda Kevin J. Shih Ting, Chun Wang Andrew Tao Bryan

Catanzaro: Image Inpainting for Irregular Holes Using Partial Convolutions,

https://arxiv.org/pdf/1804.07723.pdf

[5] Jianchao Yang Thomas Huang: Image super-resolution: Historical overview and future

challenges,
​
http://www.ifp.illinois.edu/~jyang29/papers/chap1.pdf

[6] Manuel Oliveira, Brian Bowen, Richard McKenna, Yu-Sung Chang: Fast Digital Image

Inpainting,
​
http://www.inf.ufrgs.br/~oliveira/pubs_files/inpainting.pdf

[7] Marcelo Bertalmio ,Guillermo Sapiro,Vicent Caselles, Coloma Ballester: Image

Inpainting,
​
http://www.dtic.upf.edu/~mbertalmio/bertalmi.pdf

[8] Margaret Rouse: Greedy algorithm:
​
whatis.techtarget.com/definition/greedy-algorithm

[9] Prejmerean Vasile: Curs Prelucrarea Imaginilor,

http://www.cs.ubbcluj.ro/~per/Scs_Per/PrelImg/Prel_Img%20C9.pdf

[10] Sethian A.: A Fast Marching Level Set Method for Monotonically Advancing Fronts,

http://ugweb.cs.ualberta.ca/~vis/courses/CompVis/readings/modelrec/sethian95fastlev.pdf

[11] Telea Alexandru: An Image Inpainting Technique Based on the Fast Marching Method,

https://pdfs.semanticscholar.org/622d/5f432e515da69f8f220fb92b17c8426d0427.pdf

[12] Tony Chan
ș
i Jianho ng Shen: Mathematical models for local non-texture inpaintings,

http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.30.8542&rep=rep1&type=pdf

[13] Wen-Huang Cheng , Chun-Wei Hsieh , Sheng-Kai Lin , Chia-Wei Wang ,
ș
i Ja-Ling

Wul: Robust Algorithm for Exemplar-based Image Inpainting,

https://pdfs.semanticscholar.org/dbdd/33be20a843bda89c5d9317116e662b8c20f4.pdf

[14]
​
W
​
oderhouse
​
Carey
​
: How AJAX Works,

h
​
ttp://www.upwork.com/hiring/development/how-ajax-works/

[15] ***
​

35