Traitement d'images par équations aux dérivées partielles ... · I Exemple de traitement basique : d etection de contours par calcul de la norme du gradient f krfk I En pratique,

Des equations sur l’image...Methodes variationnelles

Traitement d’images par equations aux deriveespartielles et methodes variationnelles

Julien MILLE

M2R IGI

25 novembre 2014


Applications

Segmentation et suivi Filtrage

Estimation du mouvement Reconstruction 3D

2


Calcul differentiel et integral sur les imagesEquations aux derivees partiellesDiscretisation et implementation

Plan

Des equations sur l’image...Calcul differentiel et integral sur les imagesEquations aux derivees partiellesDiscretisation et implementation

Methodes variationnellesPrincipe generalExemple 1 : modele de debruitageExemple 2 : modele de contour actif

3



Plan


Methodes variationnelles

4



Image

I Modelisation continue de l’ensemble de depart (espace) et del’ensemble d’arrivee (intensite/couleur)

I Domaine de definition (support) de l’image : un sous-domaine de R2

D ⊂ R2

I Image a valeurs scalaires (intensite = niveau de gris)

f : D → R

I f(p) = intensite en un point p = (x, y) ∈ DI Pour une image a valeurs vectorielles (couleur, souvent 3

composantes), on ecrirait :

f : D → R3

f(p) = [f1(p) f2(p) f3(p)]T

5



Image

I La fonction image est supposee continue et derivable (au moins deuxfois)

I f est au moins de classe C2 sur D

→ses derivees partielles∂f

∂x,∂f

∂y,∂2f

∂x2 ,∂2f

∂x∂y,∂2f

∂y2 sont toutes

continues sur DI Elle est integrable sur n’importe quel sous-domaine Ω de D∫

Ω

f(p)dp ≤ +∞

6



Principes et interet

I Modelisation de l’image comme une quantite physique continue enespace, et egalement en temps dans le cas d’un modele base sur uneevolution

I Interet : acces aux outils mathematiques d’analyse des fonctions(derivation, integration, equations aux derivees partielles, calcul desvariations, etc.) et de concepts issus de la physique (diffusion,densite, energie, etc.)

I En aval du raisonnement mathematique continu, discretisationspatiale et temporelle pour permettre la resolution numerique et sonimplementation algorithmique

I Dans ce cours, presentation du cheminement complet : desequations au code...

7



Derivation : premier ordre

I Derivees partielles d’ordre 1, gradient

∇f =

[∂f

∂x

∂f

∂y

]T

I Le gradient donne la direction et l’amplitude de variation de l’image(analogie avec la pente d’un relief)

I Sa norme donne l’amplitude de variation →utilisee pour la detectiondes contours

‖∇f‖ =

√(∂f

∂x

)2

+

(∂f

∂y

)2

I Derivee directionnelle selon un vecteur u

∇uf(p) =df(p+ εu)

dε

∣∣∣∣ε=0

= ∇f · u

ou · est le produit scalaire8



Detection de contours

I Exemple de traitement basique : detection de contours par calcul dela norme du gradient

f ‖∇f‖I En pratique, lissage prealable

9



Derivation : second ordre

I Derivees partielles d’ordre 2, laplacien, hessienne...

I Hessienne H : matrice des derivees partielles d’ordre 2

Hf =

∂2f

∂x2

∂2f

∂x∂y

∂2f

∂x∂y

∂2f

∂y2

I Laplacien ∇2 (note egalement ∆)

∇2f =∂2f

∂x2 +∂2f

∂y2

I Hf (p) et ∇2f(p) sont calculables en tout point p

10



Integration

I Integration d’un terme dependant de l’image sur un sous-ensembledu domaine image D

I Le long d’une courbe γ, sur une region (sous-domaine) Ω, ...

γ

Ω

11



Integration

I Exemple 1 : moyenne et variance d’intensite sur une region Ω

µ[Ω] =1

|Ω|

∫Ω

f(p)dp

σ2[Ω] =1

|Ω|

∫Ω

(f(p)− µ[Ω])2 dp

→σ2 mesure l’heterogeneite d’une region (beaucoup d’intensitesdifferentes ?)

I Exemple 2 : amplitude du gradient le long d’unecourbe γ : [0, 1]→ D

g[γ] =

∫ 1

0

‖∇f(γ(s))‖∥∥∥∥dγ

ds

∥∥∥∥ ds

→g mesure l’adequation de la courbe aux contours presents dansl’image

12



Plan



13



Equation aux derivees partielles

I Application d’equations aux derivees partielles (EDP) autraitement d’images : l’image ou une ou plusieurs fonctions associeessont soumises a des lois physiques modelisees sous forme d’equationsd’evolution

I Introduction de la dimension temporelle t

I Schema general :∂f(p, t)

∂t= ...

ou le membre de droite represente l’evolution de la fonction f enchaque point au cours du temps

I Equation accompagnee de condition(s) initiale(s) : l’image initiale (at = 0) est donnee

f(p, 0) = f0(p)

I Resolution numerique et iterative, avec critere d’arret (seuil sur lavariation, nombre d’iterations fixe, etc.)

14



Equation de diffusion de chaleur

I Exemple 1 d’EDP : equation de diffusion de la chaleur

∂f

∂t= ∇2f

I Appliquer iterativement cette equation revient a effectuer deslissages laplaciens successifs

Image initiale Image finale Evolution

15



Equation de diffusion de chaleur

I Utilisation : debruitage (inconvenient : degradation des contours)

Image initiale Image finale Evolution(+ bruit gaussien)

Image initiale Image finale Evolution(+ bruit impulsionnel)

16



Equation de diffusion anisotrope

I Exemple 2 d’EDP : equation de diffusion anisotrope∂f

∂t= ∇c · ∇f + c∇2f

ou c est le coefficient de diffusion (decroissant avec l’amplitude dugradient)

c(p, t) =1

1 + ‖∇f(p, t)‖I Appliquer iterativement cette equation revient a effectuer des

lissages successifs, avec conservation des contours saillants

Image initiale Image finale Evolution 17



Equation de diffusion anisotrope

I Utilisation : debruitage avec preservation des contours saillants

Image initiale Image finale Evolution(+ bruit gaussien)

Image initiale Image finale Evolution(+ bruit impulsionnel)

18



Plan



19



Differences finies

I Rappel de la definition de la derivee partielle (ordre 1) :

∂f(x0, y0)

∂x= limh→0

f(x0 + h, y0)− f(x0, y0)

h

I Une difference finie est une approximation de la deriveeI Trois schemas de discretisation possibles (par rapport a x, dans cet

exemple)I Difference finie arriere (a gauche) :

f(x, y)− f(x− 1, y)

I Difference finie avant (a droite) :

f(x+ 1, y)− f(x, y)

I Difference finie centree :

f(x+ 1, y)− f(x− 1, y)

220



Differences finies

I Rappel de la definition de la derivee partielle (ordre 2) :

∂2f(x0, y0)

∂x2 = limh→0

f(x0 + h, y0)− 2f(x0, y0) + f(x0 − h, y0)

h2

I Pour la discretisation de la derivee seconde, on utilise generalementla difference finie centree :

∂2f(x, y)

∂x2 ≈ f(x+ 1, y)− 2f(x, y) + f(x− 1, y)

(idem par rapport a y)

I Pour la derivee croisee, deux differences finies centrees d’ordre 1 :

∂2f(x, y)

∂x∂y

≈ f(x+1, y+1)− f(x−1, y+1)− f(x+1, y−1) + f(x−1, y−1)

421



Discretisation d’une EDP

I Discretisation temporelle d’Euler = approximation par differencefinie arriere de la derivee par rapport au temps (membre de gauche)

∂f

∂t≈ f (t+1) − f (t)

∆t

I Notation : temps discret place en exposant

I Mise sous forme d’un schema explicite : calcul de f (t+1) en fonctionde f (t)

I Exemple avec l’equation de diffusion de la chaleur

∂f

∂t= ∇2f

⇒ f (t+1) = f (t) + ∆t∇2f (t)

ou ∇2f (t) est discretise (en espace) par differences finies22



Implementation en C

I Pour les images en niveaux de gris, on considerera unerepresentation en tableau 2D de reels (peu efficace, mais genere ducode tres lisible !)

...

typedef struct

unsigned int width, height;

float **pixels;

ImageGrayscale;

void initImage(ImageGrayscale *, unsigned int, unsigned int);

void freeImage(ImageGrayscale *);

void copyImage(ImageGrayscale *, const ImageGrayscale *);

...

I Dans la fonction d’initialisation, on suppose que pixels est alloue detelle sorte que pixels[x][y] corresponde a f(x, y)

23



Implementation en C : lissage Laplacien

I Discretisation de l’operateur Laplacien

∇2f(x, y) ≈ f(x+1, y)+f(x−1, y)+f(x, y+1)+f(x, y−1)−4f(x, y)

void smoothImageLaplacian(const ImageGrayscale *pImgInput,

ImageGrayscale *pImgOutput, float delta_t)

unsigned int x, y;

float **f, **g;

initImage(pImgOutput, pImgInput->width, pImgInput->height);

f = pImgInput->pixels;

g = pImgOutput->pixels;

...

for (y=1; y<pImgInput->height-1; y++)

for (x=1; x<pImgInput->width-1; x++)

g[x][y] = f[x][y] + delta_t*

(f[x+1][y] + f[x-1][y] + f[x][y+1] + f[x][y-1] - 4*f[x][y]);

I Remarque : bords non traitesI A appeler dans une boucle jusqu’a verification d’un critere d’arret

24


Principe generalExemple 1 : modele de debruitageExemple 2 : modele de contour actif

Plan



25



Plan

Des equations sur l’image...


26



Probleme d’optimisation

I Le traitement a realiser a partir de l’image est formule comme unprobleme d’optimisation, qui comporte :

I des donnee(s) : une ou plusieurs fonction(s) (dont l’image f)I des variable(s) : une ou plusieurs fonction(s) (notee u par defaut)I une fonction objective : une fonctionnelle J de u a minimiserI eventuellement, des contraintes : equation(s) ou inequation(s)

faisant intervenir u

I Exemple : recherche d’une image lisse proche de f et nulle sur lesbords

minu∈F

∫D‖∇u(p)‖︸︷︷︸regularisation

+ λ(u(p)− f(p))2︸︷︷︸attache aux donnees

dp

t.q. u(p) = 0 ∀p ∈ ∂D

ou F est un espace de fonctions verifiant certaines proprietes sur Det λ ∈ R+ est un parametre de la fonctionnelle

27



Remarques

I Le probleme d’optimisation est de dimension infinie, car larecherche de la solution se fait dans un espace de fonctions

I A l’inverse, dans les problemes d’optimisation de dimension finie, oncherche un nombre fini de variables (exemple : optimisation discrete,probleme lineaire simple, ...)

I Exemple de probleme d’optimisation discret en traitement d’images :champs de Markov →une variable par pixel

I La fonctionnelle a minimiser (souvent appelee energie ou cout) estla plupart du temps une integrale d’un terme dependant de f , u etde leurs derivees

I L’energie est une traduction mathematique des proprietesrecherchees de la ou des variable(s)

I Difficulte : savoir ecrire mathematiquement lesproprietes/phenomenes que l’on souhaite penaliser (exemple :penaliser la norme du gradient revient a encourager une fonctionlisse)

28



Optimisation de fonctionnelles : un exemple simple

I Existence de cas d’ecoles, pour lesquels une solution analytique existeI Exemple : trouver le plus court chemin (une courbe) allant d’un

point a a un point b dans le plan continu R2

I Soit C l’espace de fonction decrivant toutes les courbes planespossibles, de [0, 1] dans R2

I Fonction a determiner : une courbe γ ∈ CI Fonctionnelle d’energie J : la longueur de la courbe, J : C → RI Contraintes : γ(0) = a et γ(1) = b

I En d’autres termes :

minγ∈C

∫ 1

0

∥∥∥∥dγ(s)

ds

∥∥∥∥ ds t.q. γ(0) = a et γ(1) = b

I Solutions triviales : segment de droite [ab], mais demontrable par lecalcul. Une solution possible est :

γ(s) = sb+ (1− s)aI Dans notre cas, les problemes ne pourront jamais etre resolus

analytiquement ! →resolution numerique29



Principe

I Etude des extrema locaux de la fonctionnelle d’energie a l’aide ducalcul des variations

I Resolution numerique (le plus souvent iterative) pour atteindre unminimum local de l’energie : methode de descente de gradient

I En resume, le traitement d’image par methode variationnelle suit lesetapes suivantes :

1. Introduction d’une energie2. Calcul des variations de l’energie3. Formulation de l’EDP4. Discretisation et implementation de la descente de gradient de l’EDP5. Tests sur un ensemble d’images

30



Extrema locaux

Extrema d’une fonction d’une seule variable reelleI Lorsqu’on cherche a minimiser une fonction ρ : R→ R par rapport a

une variable reelle x,minx∈R

ρ(x)

la premiere etape consiste a etudier les extrema locaux de ρ, doncresoudre ∂ρ

∂x= 0

Extrema d’une fonctionnelleI Ici, on cherche a minimiser une fonctionnelle J : F → R par rapport

a une fonction u ∈ F

minu∈F

J [u] =

∫L

(x, u(x),

∂u(x)

∂x

)dx

ou F est l’espace des fonctions etudieesI Besoin de caracteriser les fonctions u entrainant un extremum local

de J [u] →necessite d’etendre la notion de derivee classique auxfonctionnelles 31



Calcul des variations

I Admettons que J [u] soit dans un minimum local lorsque u = u0

→pour n’importe quelle infime perturbation η ∈ F ajoutee a u,l’energie augmentera : J [u0 + η] > J [u0] ∀η

I On suppose que J est differentiable ∀uI Introduction d’une variation infinitesimale η et derivation →calcul

des variations

I On obtient la variation premiere de J en u pour une variation η :

limε→0

J [u+ εη]− J [u]

ε=

dJ [u+ εη]

dε

∣∣∣∣ε=0

I Remarque : ressemble a une derivee directionnelle

32



Equation d’Euler-Lagrange

Cas de fonctions d’une seule variable reelleI L’espace F contient les fonctions u : R→ R de classe C2

I Soit la fonctionnelle J definie sur [a, b] ⊂ R,

J [u] =

∫ b

a

L(x, u(x), u′(x))dx avec u′(x) =∂u(x)

∂x

I Par le calcul des variations, on peut montrer que si J [u] est unextremum local de J , alors l’equation d’Euler-Lagrange estverifiee :

∂L

∂u− d

dx

∂L

∂u′

= 0 ∀ x ∈ [a, b]

I Les derivees partielles de L sont calculees en considerant x, u et u′

comme des variables independantes (par abus de notation,∂L

∂uet

∂L

∂u′designent les derivees partielles de L par rapport a ses 2eme et

3eme parametre)33



Equation d’Euler-Lagrange

Cas de fonctions de plusieurs variables reelles

I L’espace F contient les fonctions u : Rn → R de classe C2

I Un point est note x = [x1 x2 ... xn]

I Soit la fonctionnelle J definie sur D ⊂ Rn,

J [u] =

∫DL(x, u(x), ux1

(x), ux2(x), ..., uxn

(x))dx

avec uxi(x) =

∂u(x)

∂xi(autre ecriture possible : L(x, u(x),∇u(x)))

I Equation d’Euler-Lagrange correspondante :

∂L

∂u−

n∑i=1

d

dxi

∂L

∂uxi

= 0 ∀ x ∈ D

34



Derivee fonctionnelle

I Le membre de gauche de l’equation d’Euler-Lagrange est appelederivee fonctionnelle de J par rapport a u.

I La derivee fonctionnelle de

J [u] =

∫ b

a

L(x, u(x), u′(x))dx

s’ecritδJ [u]

δu=∂L

∂u− d

dx

∂L

∂u′

I Intuition pour la minimisation numerique de J : resoudre

iterativement l’equation d’Euler-Lagrange en chaque point x→a chaque iteration, prendre la direction opposee a la deriveefonctionnelle (principe de descente de gradient)

35



Lien entre variation premiere et derivee fonctionnelle

I Calculons la variation premiere de

J [u] =

∫ b

a

L(x, u(x), u′(x))dx

pour une variation η. On obtient : (detail au tableau)

dJ [u+ εη]

dε

∣∣∣∣ε=0

=

∫ b

a

η(x)∂L

∂u+ η′(x)

∂L

∂u′dx

I En integrant par partie et en posant η(a) = 0 et η(b) = 0, (detail autableau)

dJ [u+ εη]

dε

∣∣∣∣ε=0

=

∫ b

a

(∂L

∂u− d

dx

∂L

∂u′

)︸︷︷︸

derivee fonctionnelle

η(x)dx

36



Lien entre derivee fonctionnelle et variation premiere

I Si J [u] est un extremum local de J , alors sa variation premiere doits’annuler quelle que soit la fonction η

dJ [u+ εη]

dε

∣∣∣∣ε=0

=

∫ b

a

(∂L

∂u− d

dx

∂L

∂u′

)η(x)dx = 0 ∀η

I Lemme fondamental du calcul des variations →si la conditionprecedente est vraie, alors on a :

δJ [u]

δu=∂L

∂u− d

dx

∂L

∂u′

= 0 ∀x ∈ [a, b]

I On retombe ainsi sur l’equation d’Euler-Lagrange

37



Exercice

I Soit une fonction u : R→ R de classe C2 sur l’intervalle [a, b] ⊂ RI Soit la fonctionnelle

J [u] =

∫ b

a

(u′(x))2 + (u(x)− f(x))2dx

I Calculer la variation premiere de J pour une variation η (nulle en aet b) et la derivee fonctionnelle correspondante

Solution : (les (x) sont parfois omis)

dJ [u+ εη]

dε

∣∣∣∣ε=0

=

∫ b

a

d

dε

(u′ + εη′)2 + (u+ εη − f)2

∣∣ε=0

dx

=

∫ b

a

2η′(u′ + εη′) + 2η(u+ εη − f)

∣∣ε=0

dx

=

∫ b

a2η′u′ + 2η(u− f)dx

=

∫ b

a(−2u′′(x) + 2(u(x)− f(x)))η(x)dx

δJ [u]

δu(x)= 2(u(x)− f(x)− u′′(x))

38



Exercice

I Soit une fonction u : R→ R de classe C2 sur l’intervalle [a, b] ⊂ RI Soit la fonctionnelle

J [u] =

∫ b

a

(u′(x))2 + (u(x)− f(x))2dx

I Calculer la variation premiere de J pour une variation η (nulle en aet b) et la derivee fonctionnelle correspondante

Solution : (les (x) sont parfois omis)

dJ [u+ εη]

dε

∣∣∣∣ε=0

=

∫ b

a

d

dε

(u′ + εη′)2 + (u+ εη − f)2

∣∣ε=0

dx

=

∫ b

a

2η′(u′ + εη′) + 2η(u+ εη − f)

∣∣ε=0

dx

=

∫ b

a2η′u′ + 2η(u− f)dx

=

∫ b

a(−2u′′(x) + 2(u(x)− f(x)))η(x)dx

δJ [u]

δu(x)= 2(u(x)− f(x)− u′′(x))

39



Descente de gradient

I L’equation d’Euler-Lagrange ne peut etre resolue analytiquementI Fonctionnelle d’energie souvent non-convexe →presence de

nombreux minima locauxI Introduction d’une EDP effectuant une descente de gradient de

l’energie :∂u(x, t)

∂t= − δJ [u]

δu(x)∀x

I Convergence attendue vers un minimum local relativement proched’une solution initiale fournie u0 = u(., 0)

I Discretisation temporelle d’Euler :

u(t+1)(x) = u(t)(x)−∆tδJ [u(t)]

δu(t)(x)∀x

I Implementation la plus simple : l’equation d’evolution est appliqueeen parallele point par point

I Necessite de definir un critere de stabilite (= d’arret)I Inconvenient : dependance par rapport a l’initialisation

40



Descente de gradient

I Illustration pour une fonction d’une variable reelle

...

f(x)

x(0) x(1) x(2)x(3) x(T )...

x(t+1) = x(t) −∆tdf(x(t))

dx

I Difficile de representer graphiquement le meme processus pour unefonctionnelle !

41



Plan



42



Modele de debruitage

I Recherche d’une image debruitee (lisse et proche de l’imaged’entree)

I La fonction recherchee u a les memes ensembles de depart etd’arrivee que l’image : u : D → R

I Energie de debruitage :

J [u] =

∫D‖∇u(p)‖2 + (u(p)− f(p))2dp

Calcul des variations : (les (p) sont parfois omis)

dJ [u+ εη]

dε

∣∣∣∣ε=0

=

∫D

d

dε

‖∇u+ ε∇η‖2 + (u+ εη − f)2

∣∣∣ε=0

dp

=

∫D2∇η · (∇u+ ε∇η) + 2η(u+ εη − f)|ε=0 dp

=

∫D2∇η · ∇u+ 2η(u− f)dp

=

∫D

(−2∇2u(p) + 2(u(p)− f(p))

)η(p)dp

δJ [u]

δu(p)= 2(u(p)− f(p)−∇2u(p))

43




I Recherche d’une image debruitee (lisse et proche de l’imaged’entree)

I La fonction recherchee u a les memes ensembles de depart etd’arrivee que l’image : u : D → R

I Energie de debruitage :

J [u] =

∫D‖∇u(p)‖2 + (u(p)− f(p))2dp

Calcul des variations : (les (p) sont parfois omis)

dJ [u+ εη]

dε

∣∣∣∣ε=0

=

∫D

d

dε

‖∇u+ ε∇η‖2 + (u+ εη − f)2

∣∣∣ε=0

dp

=

∫D2∇η · (∇u+ ε∇η) + 2η(u+ εη − f)|ε=0 dp

=

∫D2∇η · ∇u+ 2η(u− f)dp

=

∫D

(−2∇2u(p) + 2(u(p)− f(p))

)η(p)dp

δJ [u]

δu(p)= 2(u(p)− f(p)−∇2u(p))

44




I Equation d’evolution discretisee en temps (pour minimiser J) :

u(t+1)(p) = u(t)(p)−∆tδJ [u(t)]

δu(t)(p)

= u(t)(p) + 2∆t[∇2u(t)(p)− u(t)(p) + f(p)

]I Initialisation pertinente : u(0)(p) = f(p)I Exemple :

u(0) u(tend) Iterations

45



Modele de debruitage : implementation

I Discretisation spatiale de

l’expression 2[∇2u(t)(p)− u(t)(p) + f(p)

]→vitesse en p

I Principe : calcul de la vitesse en chaque point, puis ajout de lavitesse en chaque point (l’algorithme est parallelisable)

I Choix du critere d’arret : nombre d’iterations fixe

void smoothImageVariational(const ImageGrayscale *pImgInput,

ImageGrayscale *imgOutput, float delta_t, int nb_iter)

unsigned int x, y, t;

float **f, **u, **s;

ImageGrayscale imgU, imgSpeed;

copyImage(&imgU, pImgInput);

initImage(&imgSpeed, pImgInput->width, pImgInput->height);


u = imgU.pixels;

s = imgSpeed.pixels;

46



Modele de debruitage : implementation

for (t=0; t<nb_iter; t++)



s[x][y] = 2*((u[x+1][y] + u[x-1][y] + u[x][y+1] + u[x][y-1]

- 4*u[x][y]) - u[x][y] + f[x][y]);



u[x][y] += delta_t*s[x][y];

copyImage(pImgOutput, &imgU);

freeImage(&imgU);

freeImage(&imgSpeed);

I Bords non traites dans cet exemple

47



Plan



48



Modele de contour actif

I Principe : deformation d’une courbe de maniere a segmenter (isoler)progressivement un objet en particulier dans l’image

I Initialisation fournie par l’utilisateur

I Connaissance a priori sur l’emplacement de l’objet

I Particulierement utilise en imagerie medicale

49




I L’energie depend d’une courbe superposee a l’image

I Soit γ une courbe de parametre s :

γ : [0, 1] → R2

s 7→ [γ1(s) γ2(s)]T

I Courbe simple (sans intersection) et fermee : γ(0) = γ(1)

γ

γ(0) = γ(1)

γ(s)

n(s)t(s)

t = tangente, n = normale interieure50




I Objectif : segmentation d’un objet →la courbe doit s’ajuster auxfrontieres de l’objet recherche

I Les contours de l’objet correspondent a des zones de fort gradientI Recherche d’une courbe a la fois lisse et localisee sur les contours→l’energie penalise une courbe etiree ou situee sur des zones ou lanorme du gradient est faible

J [γ] =

∫ 1

0

α1

2‖γ′(s)‖2 − ‖∇f(γ(s))‖ ds

avec γ′(s) =dγ(s)

dsI Version simplifiee du modele original (qui comporte un terme

dependant de la derivee seconde →penalisation de la courbure)I Le calcul des variations donne :

δJ [γ]

δγ(s)= −αγ′′(s)−∇‖∇f(γ(s))‖

51



Modele de contour actif : discretisation

I Equation d’evolution discretisee en temps :

γ(t+1)(s) = γ(t)(s) + ∆t

[αγ(t)

′′

(s) +∇∥∥∥∇f(γ(t)(s))

∥∥∥]I Discretisation spatiale →echantillonnage de la courbe

I Representation simple : polygone defini par une sequence de nsommets v1,v2, ...,vn

I Les coordonnees des sommets sont reelles : vi ∈ R2

I Equation d’evolution discretisee en temps et espace (sommet parsommet) :

v(t+1)i = v

(t)i + ∆t

[α(v

(t)i+1 + v

(t)i−1 − 2v

(t)i

)+∇

∥∥∥∇f(v(t)i )∥∥∥]

52



Interpolation

I En pratique, la fonction image n’est donnee que pour des points decoordonnees entieres (pixels)

I Pour approximer l’image aux points de coordonnees non-entieres→interpolation bilineaire

f(x, y) ≈ (dxe − x)(dye − y) f(bxc, byc)+ (x− bxc)(dye − y) f(dxe, byc)+ (dxe − x)(y − byc) f(bxc, dye)+ (x− bxc)(y − byc) f(dxe, dye)

(x, y)

(bxc, byc) (dxe, byc)

(bxc, dye) (dxe, dye) 53



Modele de contour actif : implementation

I Besoin de l’interpolation bilineaire pour estimer ‖∇f‖ et ∇‖∇f‖aux coordonnees des sommets

float interpImage(const ImageGrayscale *pImg, float x, float y)

unsigned int xi, yi, xs, ys;

float **f;

xi = (unsigned int)floor(x); yi = (unsigned int)floor(y);

xs = xi+1; ys = yi+1;

f = pImg->pixels;

return (xs-x)*(ys-y)*f[xi][yi] + (x-xi)*(ys-y)*f[xs][yi]

+ (xs-x)*(y-yi)*f[xi][ys] + (x-xi)*(y-yi)*f[xs][ys];

54




I Besoin de calculer et conserver l’image ‖∇f‖void gradientNormImage(const ImageGrayscale *pImgInput,

ImageGrayscale *pImgGrad)

unsigned int x,y;

float **f, **g;

float der_x, der_y;

initImage(pImgGrad, pImgInput->width, pImgInput->height);


g = pImgGrad->pixels;

...



der_x = (f[x+1][y]-f[x-1][y])/2;

der_y = (f[x][y+1]-f[x][y-1])/2;

g[x][y] = sqrt(der_x*der_x + der_y*der_y);

55




I Choix de representation du contour : tableau de sommets

typedef struct

float x, y;

Vertex;

typedef struct

Vertex *arrayVertices;

unsigned int nbVertices;

float delta_t;

float alpha;

ImageGrayscale *pImgGrad;

ActiveContour;

void initActiveContourCircle(ActiveContour *, float, float, float);

void moveActiveContour(ActiveContour *);

void resampleActiveContour(ActiveContour *);

I Fonctions d’initialisation, d’evolution et de re-echantillonnage (ajoutet suppression de sommet afin de conserver une repartitionhomogene et suffisamment dense le long de la courbe)

56




I Fonction d’initialisation en cercle

void initActiveContourCircle(ActiveContour *pAC,

float cx, float cy, float radius)

unsigned int i;

float _pi, angle, perimeter;

_pi = 3.14159;

perimeter = 2*_pi*radius;

pAC->nbVertices = perimeter/3; /* One vertex every 3 pixels */

pAC->arrayVertices =

(Vertex *)malloc(pAC->nbVertices*sizeof(Vertex));

for (i=0; i<pAC->nbVertices; i++)

angle = (float)i/(float)pAC->nbVertices*2*_pi;

pAC->arrayVertices[i].x = cx + radius*cos(angle);

pAC->arrayVertices[i].y = cy + radius*sin(angle);

57




void moveActiveContour(ActiveContour *pAC)

unsigned int i, ip1, im1, n;

Vertex *arraySpeed, *v;

float x, y, grad_x, grad_y;

arraySpeed =

(Vertex *)malloc(pAC->nbVertices*sizeof(Vertex));

v = pAC->arrayVertices;

n = pAC->nbVertices;

for (i=0; i<n; i++)

grad_x = (interpImage(pImgGrad, v[i].x+1.0, vi[i].y)

-interpImage(pImgGrad, v[i].x-1.0, vi[i].y))/2;

grad_y = (interpImage(pImgGrad, v[i].x, vi[i].y+1.0)

-interpImage(pImgGrad, v[i].x, vi[i].y-1.0))/2;

58




im1 = (i+n-1)%n;

ip1 = (i+1)%n;

arraySpeed[i].x = alpha*(v[im1].x + v[ip1].x - 2*v[i].x) + grad_x;

arraySpeed[i].y = alpha*(v[im1].y + v[ip1].y - 2*v[i].y) + grad_y;

for (i=0; i<n; i++)

v[i].x += delta_t*arraySpeed[i].x;

v[i].y += delta_t*arraySpeed[i].y;

free(arraySpeed);

59




I Fonction principale

ImageGrayscale imgInput, imgGradNorm;

ActiveContour ac;

unsigned int t, nb_iter;

... /* Load input image into imgInput */

gradientNormImage(&imgInput, &imgGradNorm);

ac.alpha = 0.5;

ac.delta_t = 0.25;

ac.pImgGrad = &imgGradNorm;

initActiveContourCircle(&ac, ...);

for (t=0; t<nb_iter; t++)

moveActiveContour(&ac);

resampleActiveContour(&ac);

... 60

Documents

Traitement d'images par équations aux dérivées partielles ... · I Exemple de traitement basique : d etection de contours par calcul de la norme du gradient f krfk I En pratique,