Ecole Nationale des Sciences de l’Informatique

Support de Cours

Traitement et Analyse d’Images

Cours de troisième année

Dr Slim MHIRI

Maître Assistant à l’ENSI Département Image et Modélisation Mathématique

AU 2013/2014

Traitement et analyse d’image

Table des Matières

1. Introduction au traitement et analyse d’images

Généralités Phénomènes visuels Machines de traitement d’images Echantillonnage/Quantification

2. Signaux et systèmes bidimensionnels

Récursivité Stabilité Représentation à modèle d’état Processus stochastique bidimensionnels

3. Transformation unitaires bidimensionnelles Transformation de Karhunen-Loève Transformation de Fourier discrète 2D Transformation en cosinus discrète Analyse statistique des transformées

4 Notions de base de la morphologie mathématique

Propriétés des transformations morphologiques Erosion Dilatation Ouverture morphologique Fermeture morphologique

5 Amélioration et restauration des images

Modification de l’hisogramme Lissage Filtre médian

6 Restauration d’images

Approche déterministe Approche statistique

7 Détection de contour / Segmentation d’images

Détection de contours Segmentation en régions

8 Estimation du mouvement

Estimation sur un domaine 2D Estimation du mouvement sur un contour

Slim M’HIRI

ENSI II3

Traitement et analyse d’image

9 Compression d’images

1. INTRODUCTION

Compression par transformation unitaire Codage prédictif Compression par quantification vectorielle

Certains phénomènes ne sont pas observables directement et peuvent être observer par l’intermédiaire d’une image, qui d’après la définition du dictionnaire Petit-Robert est La “représentation d’un être ou d’une chose”. La formation d’une image suppose d’abord un capteur, comme la rétine du système visuel humain. Mais elle suppose aussi un rayonnement, une radiation qui est émise par des objets ou qui traverse des objets. L’existence de trois facteurs permet donc la formation d’une image: l’objet, le rayon, le capteur. L’analyse des images a comme objectif l’analyse du phénomène physique ou la reconstitution de la réalité physique. En même temps une image constitue une source d’information, qui selon un proverbe est aussi riche que “mille mots”. La transmission de cette information ou la compression des images constitue un domaine de grand intérêt à la fois pour la distribution, la communication par l’image et l’archivage des images, voire la constitution de bases de données. Par ailleurs il se peut que le processus de formation de l’image entraîne des perturbations ou transformations, qu’il serait nécessaire de restaurer avant l’analyse.

L’analyse des images, qui commence avec la détection d'indices visuels et la segmentation, a comme objectif ambitieux la vision par ordinateur: fabriquer une machine qui a des capacités de perception visuelle. Le codage d’images s’applique à la transmission ou l’archivage et s’efforce à obtenir, avec un coût et une distorsion aussi faible que possible, une réduction efficace de la redondance. L’amélioration et la restauration des images rendent possible une analyse d’images, soit par l’homme, soit par la machine, plus fiable et plus efficace.

Mais revenons au schéma de la formation des images. Le capteur est en général étendu spatialement sur caractérisée par sa longueur d’onde et son intensité, qui peut varier temporellement. Nous arrivons donc à une grandeur physique que nous pouvons décrire par la fonction d’intensité £(x, y, , t), (x, y) étant un point sur la surface du capteur, que nous supposons plane pour simplifier, étant la longueur d’onde et t étant le temps.

(cid:129)

En réalité le capteur a un certain spectre de sensibilité sur les longueurs d’onde, supposons S( homogène temporellement et spatialement

(cid:129)

)

(!, ", #) = $ %((cid:129)) (!, ", (cid:129), #)&(cid:129) Un système de vision ou d’observations d’images peut comporter plusieurs capteurs de ce type et chacun couvre une partie du spectre de longueur d’onde. Le système visuel humain comporte trois types de capteurs de la lumière, sensibles aux trois couleurs, qu’il convient d’appeler fondamentales : rouge, vert, bleu. Les images en télédétection comportent plusieurs canaux, qui correspondent a des bandes différentes allant de l’infrarouge au visible. Dans la suite nous allons nous limiter a un seul capteur (monochrome) et pour une grande partie de ce manuscrit nous considérerons des images statiques, c’est-à-dire a un instant donné. Avant d’aller plus loin dans la modélisation mathématique, nous voulons nous attarder sur certains aspects de la perception visuelle. Cela nous

Slim M’HIRI

ENSI II3

Slim M’HIRI

ENSI II3

Traitement et analyse d’image

paraît utile parce que même pour des tâches d’analyse automatisées, le juge de la qualité est l’homme et plus précisément le système visuel humain. Phénomènes visuels

Nous présentons brièvement certaines propriétés de la vision humaine qui peuvent être utiles en traitement d’images. Nous ne prétendons pas exposer une théorie du système visuel, cela dépassant l’objectif de ce manuscrit et nos compétences. Tout d’abord il existe des seuils de détection d’un stimulus visuel pour la luminance, la durée et la dimension apparente. Il existe aussi des seuils sur la perception de différences tant en chrominance qu’en luminance. Pour une large bande de luminance le seuil de contraste visible est de l’ordre de 2% (loi de Weber),

Le système visuel humain se comporte d’une certaine manière comme un filtre passe-bande (Fig.3 extraite de M. Kunt “Traitement numérique des signaux”). En pratique pour un système de traitement d’images cela signifie que l’on peut être plus tolérant sur la reconstitution de l’intensité dans des zones d’importantes variations spatiales.

* > +- = 0,02

c’est-à-dire ∆*

(Fig.1). Mais cette courbe dépend du contexte. Si la différence est

observée sur un fond, le seuil est modifié (Fig.2). La dépendance du contexte est aussi illustrée par le phénomène du contraste simultané. Une intensité donnée apparaît plus claire sur fond sombre que sur fond clair. L’effet de la bande de Mach montre que l’œil est moins sensible à des fréquences spatiales hautes ou basses qu’à des fréquences intermédiaires.

Fig. 3. Filage passe-bande spatial dû à l’inhibition latérale

Un modèle plus complet du système visuel humain a été proposé par C.F.Hall et E.L. Hall. Ceci est donné dans la Fig4. Le filtre passe-bas spatial correspond à la résolution spatiale, lié par ailleurs à la séquence d’échantillonnage. L’opération ponctuelle non-linéaire modélise les phénomènes de saturation. Le filtre passe-bande spatial modélise l’inhibition latérale. Finalement le filtre passe-bas temporel exprime les constantes d’excitation et de persistance d’une excitation.

Fig. 4. Un modèle du système visuel humain.

Fig.1. Sensibilité au contraste

Fig.2. Sensibilité au contraste par rapport au fond

Slim M’HIRI

ENSI II3

Slim M’HIRI

ENSI II3

Traitement et analyse d’image

.(/, 1) = (/Δ!, 1Δ!") Nous allons présenter dans la suite les relations entre image discrète et image continue dans le domaine des fréquences spatiales. Définissons d’abord les transformées de Fourier continue :

.6789, 8:; = ∬ (!, ") exp ?−2AB7!89 + "8:;D &!&" et pour le cas échantillonné

EF GF

(1.1)

.789, 8:; = ∑ ∑ .(/, 1) exp ?−2AB7/89 + 18:;D

EF GF

(1.2)

Les transformées inverses sont données dans la suite, pour le cas continu

(!, ") = ∬ .6789, 8:; exp ?2AB7!89 + "8:;D &89&8:

EF GF

(1.3)

et pour le cas discret.

.(/, 1) = ∬

EI/4 GI/4

.789, 8:; exp ?2AB7!89 + "8:;D &89&8:

(1.4)

(resp.

∆!

∆"

) est la période d’échantillonnage en x (resp. en y), nous allons montrer que

Fig5. Exemple de machine pour le traitement d’images

Machines de traitement d’images

Nous allons maintenant présenter rapidement les machines de traitement d’images. Elles component un numériseur qui consiste a un échantillonneur et en un quantificateur, une mémoire d’images, une unité de traitement (calcul) et un poste de visualisation (tube cathodique après conversion analogique). Dans beaucoup de systèmes de traitement on trouve le schéma de la Fig. 5. Les cameras utilisent le plus souvent des éléments photosensibles CCD. Un convertisseur analogique/numérique (CAN) couramment rencontré est capable d’échantillonner une image en 512x512 points, sur 256 niveaux de gris avec un débit de 25 images/sec. La mémoire locale d’images est d’accès aléatoire avec un temps d’accès court, pour permettre la visualisation des images au débit de 25 images/sec.

Echantillonnage

Le développement du traitement et de l’analyse d’images s’est produit avec l’avènement des techniques numériques. Par ailleurs, il est possible de traiter des images analogiques avec des dispositifs optiques, mais nous nous intéresserons uniquement aux traitements numériques. Le premier maillon de du traitement est donc l’échantillonnage et la quantification. Une 4. Chaque élément de la suite correspond à image représentée par une suite : un

.(/, 1) de

3 l’image

indexée dans

échantillon

analogique

EF ∆9∆: ∑ ∑ .6 ? GF

EF GF

KLEM ∆9 ,

KNEO ∆: D

.789, 8:; = Cette relation montre que si la bande du signal analogique est limitée dans un rectangle défini par (-vxM,-vYM) et (vXM,vyM). alors il suffit d’avoir

(1.5)

pour pouvoir reconstituer le signal analogique à partir du signal échantillonné. Pour ce faire, le filtre suivant est utilisé

1 Δ!

> 2Q9RS#

> 2Q:R

1 Δ"

T7Q9, Q:; = U 0 La réponse impulsionnelle de ce filtre est

I 4∆9 , WQ:W < XYZZS[\]

1 |Q9| <

4∆:

(1.6)

∆9∆: ]Y1_ ?

ℎ(!, ") = En réalité pour des signaux bidimensionnels, ii existe plusieurs filtres de reconstitution, selon le domaine de définition de la transformée de Fourier du signal analogique. Ainsi, Si le domaine est un cercle

(1.7)

`9 ∆9D ]Y1_ ?

`: ∆:D

alors la réponse impulsionnelle du filtre de reconstitution est

4 Q9

4 + Q:

4 ≤ Qb

ℎ(!, ") = 4B où

ℬk( )

est la fonction de Bessel d’ordre l.

ℬf?ghi9jE:jD i9jE:j

(1.8)

Slim M’HIRI

ENSI II3

Slim M’HIRI

ENSI II3

Traitement et analyse d’image

Il est prferab1e de filtrer avec le filtre passe-bas (1.6) avant l’échantillonnage pour ne pas avoir d’artefacts dus à l’échantillonnage, connus comme erreur de recouvrement. Si le filtre H n’est pas parfait deux types d’erreur apparaissent: une erreur de recouvrement et une erreur de résolution. L’erreur de recouvrement est mesurée par

l =

mnomq

(1.9)

mq EF GF

Où

ru = ∫

wL GwL

rs = ∬ W.6789, 8:;. T789, 8:;W

EF GF

wN ∫ ∬ W.6789, 8:;. T789, 8:;W GwLN I 4∆9 , y: =

avec

y9 =

4∆:

&89&8: 4

&89&8:

la perte de résolution est mesurée par

lu =

mqzomq

(1.10)

EF GF De la même manière on peut caractériser le filtre d’interpolation pour la reconstruction d’une image à partir de ses échantillons par une erreur de résolution et une erreur d’interpolation.

wN ∫ ∬ W.6789, 8:;W GwLN

ruR = ∫

&89&8:

Avec

mqz wL GwL

Quantification

Une approche pour déterminer le quantificateur consiste à utiliser la loi de Weber sur le contraste. Il faudra évidemment l’utiliser en négligeant complètement les effets du contexte. Considérons alors un support avec une dynamique allant de L0 a LT,.., cette dernière étant le seuil de saturation (Fig.6 extraite de M.Kunt “Traitement numérique des signaux”).

N† =

‡ˆ‰Š

‹ƒ ‹„

(1.11)

‡ˆ‰(I E (cid:141)Ž)

On utilise généralement le log10, parce qu’il est utilisé pour caractériser la densité optique des films. Pour une pellicule de qualité courante, on aura une densité optique de2. Si = 0,02, alors on trouve , ce qui veut dire que 8 bits ou 256 niveaux suffiraient pour représenter sans défauts visibles une telle image. D’après cette approche, le quantificateur est uniforme sur le logarithme de la luminance (Fig. 7).

N† = 232,55

Fig. 7. Quantificateur d’après la loi de Weber.

L’autre approche est probabiliste. On considère que la quantité a quantifier est une variable aléatoire dont la densité de probabilité est connue, admettons p(x). Si le nombre des niveaux de quantification est fixée à Nq, on doit déterminer Nq niveaux de représentation ri pour Nq intervalles (di-1, di) ; i = 1,..., Nq. Ceci est fait en minimisant un critère de distorsion. Considérons la distorsion quadratique

D = ∑ ∫

~€ “˜I

•– •–o—

p(x)(x − r“)

(1.12)

La solution de ce problème d’optimisation est donnée par Max Lloyd sous la forme de deux équations :

d“ =

™–E™–š— 4

, i = 1, … , N† − 1

(1.13)

r“ =

Ÿ– ∫ Ÿ–o— Ÿ– ∫ Ÿ–o—

(cid:157)ž((cid:157))•(cid:157)

, i = 1, … , N†

ž((cid:157))•(cid:157)

(1.14)

La solution itérative de ces équations détermine le quantificateur. La Fig. 8 donne un exemple du quantificateur optimal pour une densité de probabilité laplacienne, qui est définie ci-après, pour une variable aléatoire dont la moyenne est m et l’écart-type est

, σ √2|x − m| σ

Fig. 6. Courbe de densité optique en fonction de l’exposition.

p(x) =

σ√2

exp ¢

Si CW est la constante de Weber dans la partie linéaire, il faudra au moins Nq niveaux, o

(1 + C}) Ainsi le nombre des niveaux de quantification est

~€ =

‚ƒ ‚„

pour que les effets de quantification soient invisibles.

Une autre façon de voir les choses consiste à considérer qu’une quantification a été effectuée et que l’on désire représenter au mieux la même image avec moins de niveaux de gris, pour la réduction de données, par exemple. Dans ce cas, nous ne connaissons pas la densité de probabilité, mais nous pouvons déterminer l’histogramme des intensités. Nous pouvons alors appliquer la même approche que ci-dessus utilisant l’histogramme.

Slim M’HIRI

ENSI II3

Slim M’HIRI

ENSI II3

Traitement et analyse d’image

Sachant que la distorsion d’une variable est proportionnelle à G4ª«¬, nous nous proposons 2 de résoudre le problème d’optimisation sous la contrainte que la distorsion est la même pour toutes les variables, c’est-à-dire

4 σ¥¦

où

b¥¦ =

I 4 (Z®¯4σ¥¦

(1.16)

− Z®¯4_)

c = σ¥¦

G4ª«¬

Utilisant (1.15) et (1.16) nous obtenons

b¥¦ =

° R± +

I 4 ?Z®¯4σ¥¦

I R R± Z®¯4 ∏ ´˜I

−

± ∏ σ¥¦ ³˜I

(1.17) D

le nombre optimal de bits pour la variable Xmn.

Fig. 8. Quantificateur de Max-Lloyd pour la loi laplacienne (4 niveaux).

Toutes les approches présentées concernent la quantification scalaire, indépendamment du contexte. Elles ne tiennent pas compte ni des propriétés spatiales de la perception visuelle, ni des probabilités de cooccurrence des différents niveaux de gris. Et même si les variables étaient indépendantes, la solution optimale n’est pas la même si l’on considère globalement un vecteur des variables, que si on les considère séquentiellement. Une diminution de la distorsion peut être obtenue, pour la même quantité d’informations, par une quantification vectorielle. La quantification vectorielle ne peut pas être aisément réalisée ni par une approche probabiliste ni par une analyse d’histogramme. En pratique on utilise les données pour effectuer une partition utilisant des méthodes de classification automatique. Une représentation est choisie pour initialiser l’algorithme de classification et la partition est effectuée selon le critère retenu. Une nouvelle représentation à partir de la dernière partition est déterminée et ainsi de suite jusqu’à la convergence de l’algorithme, qui est assurée, mais vers une solution sous-optimale.

Quand on peut supposer qu’un bloc est constitué de variables indépendantes de variance différente, on peut se poser le problème de la quantification par bloc en tenant uniquement compte de la variance de chaque variable et en cherchant a optimiser le nombre de bits affectés à chacune des variables. Considérons un bloc de MN variables et soit B le nombre total de bits 4 Ia variance de la variable Xmn et bmn le nombre de bits alloués. Nous avons donc alloués. Soit

σ¥¦

∑

~ ¦˜I

∑

b¥¦ =

(1.15)

Slim M’HIRI

ENSI II3

Slim M’HIRI

ENSI II3

Traitement et analyse d’image

2. SIGNAUX ET SYSTEMES BIDIMENSIONNELS

Après l’échantillonnage, nous retenons comme modèle pour une image, une suite indexée par 4. Nous appelons signal 2D la suite {x(m,n)}. Nous appelons système ou filtre bidimensionnel 3 (2D) toute application T définie sur les suites bidimensionnelles. Un système est dit linéaire, si l’application T est linéaire, i.e.

T(a x1 + b x2) = a T(x1) + b T(x2)

Alors pour une application linéaire y= T(x) on peut écrire

"(/, 1) = ∑ ∑ ℎ(Y, A; /, 1)!(/ − Y, 1 − A)

(2.1)

Si h est indépendant de (m,n) le filtre est dit invariant par translation. Alors h(i, j) est appelée est une suite dite impulsion réponse impulsionnelle du filtre. Elle est égale à unitaire et définie par

ℎ = ¸(¹)

où

¹(/, 1) = º

1 (/, 1) = (0,0) 0 (/, 1) ≠ (0,0)

Un filtre linéaire invariant par translation (FLI) est dit séparable, si

il est dit invariant par rotation, si impulsionnelle finie (RIF), si infinie (RII) dans le cas contraire. Exemple. Le filtre gaussien, dont la réponse impulsionnelle a la forme suivante

ℎ(/, 1) = ℎI(/). ℎ4(1) 4) ℎ(/, 1) = ℎb(/ |/| > ¼, |1| > ½

ℎ(/, 1) = 0

pour

+ 1

. On dit qu’un FLI est à réponse et à réponse impulsionnelle

ℎ(/, 1) =

2B¾4 S!¿ ¢−

4 + 1 2¾4 ¤ , (m, n)ϵℤ

est un filtre RU séparable et invariant par rotation utilisé pour un filtrage passe-bas.

Récursivité

Les filtres RIF ne font apparaitre aucune difficulté supplémentaire par rapport au cas monodimensionnel. Par contre de nouveaux problèmes apparaissent avec le passage à 2D des filtres RII. Ceci est principalement dû à la perte du concept de causalité. Cette perte est intrinsèque aux suites 2D. Mais on se trouve confronté aux questions de causalité et de récursivité, si l’on veut réaliser des filtres RII. Nous allons considérer un filtre RII décrit par une équation aux différences du type

"(/, 1) = ∑

(·,¶)ÃÄÅG{(b,b)}

X(Y, A)"(/ − Y, 1 − A) +

∑

(·,¶)ÃÄÉ

È(Y, A)!(/ − Y, 1 − A)

(2.2)

étant des sous-ensembles finis de

.6 un ordre de progression dans

.Ê

4, (0,0) appartenant 4 permettant de disposer des

ℤ

. Ce filtre est récursif, s’il existe pour

.6 "(/ − Y, 1 − A)

avant d’avoir calculé

{(0,0)} plus petit secteur angulaire

(Y, A)Ë.6 − . II est montré que le filtre défini par (2.2) est récursif, si le

ℤ "(/, 1) de sommet (0,0), contenant tous les points de ‘a

a une ouverture strictement inférieure à

Fig.9. Filtre récursif (

Í < Î

)

Considérons le filtre récursif

"(/, 1) = Ï X(Y, A)"(/ − Y, 1 − A) +

!(/, 1)

La réponse impulsionnelle h de ce filtre est solution de

(·,¶)ÃÄÅG{(b,b)}

ℎ(/, 1) = Ï X(Y, A)ℎ(/ − Y, 1 − A) +

¹(/, 1)

(·,¶)ÃÄÅG{(b,b)}

Fig. 10. Support des filtres quart de plan et demi-plan asymétrique.

h est donc une suite dont le support est inclu dans plus couramment utilisés : quart de plan dont la réponse impulsionnelle est nulle hors de {0})4, et demi plan asymétrique dont la réponse impulsionnelle est nulle hors de 1, 1 ∈ ℤ} ∪ {(0, 1): 1 ∈ ℕ}

. Parmi les filtres récursifs deux types sont les

(ℕ ∪ {(/, 1): / ≥

Slim M’HIRI

ENSI II3

Slim M’HIRI

ENSI II3

Traitement et analyse d’image

Stabilité

Un filtre est dit stable si pour une entrée bornée la sortie est bornée. On peut montrer que pour une réponse impulsionnelle h, la stabilité est équivalente à

∑

(´,³)∈ℤj

(2.3) |ℎ(/, 1)| Il est évident que tous les filtres RIF sont stables. Pour l’étude de la stabilité de filtres RII la condition ci-dessus est difficilement exploitable. On utilise alors de critères portant sur la fonction de transfert. Pour cela la définition de la transformée en (z,w), extension en 2D de la transformée 4, la fonction X(z,w) est définie sur C2 en Z, est introduite. Si x(m,n) est une suite indexée par ℤ par

< ∞

G³ (2.4) Les valeurs de (z,w) pour lesquelles la transformée existe constituent la région de convergence dans l’hyperplan (z,w). La transformée inverse est donnée par

X(z, w) = ∑

!(/, 1)Ù

(´,³)∈ℤj

G´

x(m, n) =

(4ÛÜ)j ∮ ∮ H(z, w) (cid:141)—

(cid:141)j

´GI

³GI

&Ù&Ú

(2.5)

Les intégrales sont évaluées sur des contours fermés, appartenant à la région de convergence de X(z,w) et encerclant l’origine (0,0) dans le sens trigonométrique. La fonction de transfert de h est sa transformée H(z,w). Considérons maintenant une fonction de transfert égale à l’inverse d’un polynôme premier quart de plan

Le filtre, dont la fonction de transfert est H(z,w), est stable si, et seulement Si,

H(z, w) =

1 A(z, w)

Si, et seulement si,

A(z, w) ≠ 0, pour |z| ≥ 1, |w| ≥ 1

(2.6)

a. b.

A(z, w) ≠ 0, pour |z| ≥ 1, |w| = 1 A(z, w) ≠ 0, pour |z| = 1, |w| ≥ 1

Si, et seulement Si,

(2.7)

Les conditions de stabilité s’écrivent comme suit

De ces deux inégalités on déduit que

|a| < W1 − be |b| < W1 − ae

GÜèjW GÜè—W

|acoswI + bcosw4| < 1 Pour que le système soit stable, il faut donc . Si cette condition est vraie, alors on peut |a| + |b| < 1 constater que les deux conditions (2.7) sont vérifiées. La condition ci-dessus est donc nécessaire et suffisante. Le théorème de stabilité que nous avons énoncé plus haut concernait uniquement des filtres premiers quarts de plan. Nous allons dans la suite montrer qu’un filtre demi-plan asymétrique peut être transformé en un filtre quart de plan et ainsi le théorème peut être appliqué pour tout filtre récursif. Le support d’un filtre récursif est délimité par un angle inférieur à . Soit N1= (N11,N21) et N2=(N12,N22) les deux vecteurs qui déterminent la frontière de l’angle. Alors la transformation

m1 = N22n1 - N12n2 m2=-N21n1 +N11n2

transforme le support du filtre a un quart de plan. Le vecteur N1 se transforme en (D,O) et N2 en (O,D), D étant :

D= N11 N12- N12 N21

Cette transformation n’est pas unique, mais on peut prouver que, pour que tous les points du quart de plan appartiennent au domaine de la transformation, il faut et il suffit que lDl=1.

Exemple Considérons le support ci-dessous

a. b.

A(z, w) ≠ 0, pour |z| ≥ 1, |w| = 1 A(a, w) ≠ 0, pour |z| = 1, a tel que |a| = 1

(2.8)

Si, et seulement Si,

a. b. c.

A(z, w) ≠ 0, pour |z| = |w| = 1 A(a, w) ≠ 0, pour |w| ≥ 1, a tel que |a| = 1 A(z, b) ≠ 0, pour |z| ≥ 1, b tel que |b| = 1

(2.9)

Exemple Considérons

A(z, w) = 1 − az

− bw

La réponse impulsionnel du filtre correspondant est donnée par

h(m, n) =

(¥E¦)! ¥!¦! a

La transformation ci-dessus donne pour cet exemple

m1 = n1 m2=n1+n2

Le support du filtre se trouve ainsi transformé en un quart de plan

Slim M’HIRI

ENSI II3

Slim M’HIRI

ENSI II3

Traitement et analyse d’image

A l’aide des modèles linéaires que nous avons définis nous allons étudier les processus aléatoires 2D.

Processus stochastiques bidimensionnels

Nous allons d’abord considérer des modélisations causales. Cela nécessite la désignation d’un 4 n’est pas naturel. Il dépend d’une définition. Prenons l’ordre “passé“. L’ordre dans lexicographique ligne par ligne. Par rapport au point (m,n) le “passé” est défini par l’ensemble

ℤ

P(m, n) = {(k, l), k < m, ∀l} ∪ {(m, l), l < n} On appelle processus ARMA lexicographique ou unilatéral tout processus 2D défini par l’équation aux différences :

Représentation à modèle d’état

Les représentations utilisées jusqu’à présent étaient externes. Nous nous posons maintenant la question de l’existence d’une représentation à modèle d’état. Considérons un filtre quart de plan dont la fonction de transfert est H(z,w), strictement causal et défini par l’équation aux différences

RÅ

±Å

RÉ

±É

"(/, 1) = ∑ avec "(/, 1)

(ì,k)ÃÄÅG{(b,b)} bruit blanc 2D de variance 1

X(ë, Z)"(/ − ë, 1 − Z) +

∑

(ì,k)ÃÄÉ

È(ë, Z)!(/ − ë, 1 − Z)

(2.12)

ø(Ù, Ú) = 1 − Ï X(ë, Z)Ù

Gì

(ì,k)ÃÄÅG{(b,b)}

ù(Ù, Ú) = Ï È(ë, Z)Ù

Gì

"(/, 1) = Ï Ï X(ë, Z)"(/ − ë, 1 − Z) +

Ï Ï È(ë, Z)!(/ − ë, 1 − Z) + ì˜b

k˜b

ì˜b

k˜b (ì,k)í(b,b)

Il est clair que le calcul de

n’est pas possible que si les (

"(/, 1), (/ ≥ 0, 1 ≥ 0)

{"(−ë, Z), ë = sont fixés par conditions 1, … , ¼6; Z = −½6, … , ∞} initiales. Dans ces conditions l’état du filtre a une dimension infinie, sauf si A(z,w) est séparable. Dans ce dernier cas la dimension de la variable d’état est MaNa (en général). Dans ce cas, on peut obtenir l’équation d’état (vecteur d’état X) suivante

{"(ë, −Z), ë = 0, … , +∞; Z = 1, … , ½6}

et les

î(/, 1) = ïIî(/ − 1, 1) + ï4î(/, 1 − 1) − ïIï4î(/ − 1, 1 − 1) + ð!(/, 1) "(/, 1) = Tî(/, 1)

(2.10)

Les matrices F1 et F2 commutent F1F2 = F2F1 et la réponse impulsionnelle du filtre est donnée par

Polynômes demi-plan asymétrique et vérifiant les conditions de stabilité. Le bruit blanc

est égal au processus d’innovation normalisé

(ì,k)ÃÄÉ

ÿ(/, 1)

ÿ(/, 1) =

"(/, 1) − r{"(/, 1)|"(ë, Z): (ë, Z) ∈ (/, 1)} iÿX\("(/, 1) − r{"(/, 1)|"(ë, Z): (ë, Z) ∈ (/, 1)})

La représentation (2.12) est unique, ce qui ne serait pas le cas si aux différences bilatérales. Il existe principalement deux différences entre les processus ARMA 1D et 2D. La première différence s’exprime par l’existence de directions “privilégiées”. Cela veut dire que l’inverse du

était défini par une équation

filtre dont la fonction de transfert est °(!,-) "(!,-)

c’est-à-dire le filtre avec fonction de transfert

, a un support qui est inclu dans un cône C de sommet (0,0) et d’ouverture inférieure à

"(!,-) °(!,-)

´ ℎ(/, 1) = TïI

³ ï4

r{"(/, 1)|"(ë, Z): (ë, Z) ∈ (/, 1)} = Ï ¯(ë, Z)"(/ − ë, 1 − Z)

(ì,k)Ã#G{(b,b)}

Ce modèle étant limité au cas des filtres séparables, un autre modèle d’état a été introduit pour le cas général d’un filtre quart de plan quelconque, qui utilise deux variables d’état appelées horizontale et verticale. L’équation d’état est la suivante

⎧ô

î î

(/, 1) (/, 1)

÷ = ô

øII øI4 ø4I ø44

î î

÷ ô

⎨ ⎩

"(/, 1) = [+I +4] ô

(/, 1 − 1) (/ − 1, 1) õ î î

(/, 1) (/, 1)

÷ + ô

ùI ù4

÷ !(/, 1)

(2.11)

La deuxième différence provient du fait que les processus 2D a densité spectrale rationnelle ne sont nécessairement des processus ARMA. Ceci est dû au fait que les polynômes 2D ne peuvent se décomposer en produit de facteurs d’ordre 1. Les processus ARMA étant par nature unilatéraux s’utilisent en théorie de prédiction linéaire (par exemple en codage prédictif). En interpolation linéaire il est parfois plus intéressant d’utiliser des modèles des champs markoviens, qui sont par nature non-causaux ou bilatéraux. On appelle L-champ markovien au sens large sur

pour lequel

4 Ie processus

ℤ

"(/, 1)

Slim M’HIRI

ENSI II3

Slim M’HIRI

ENSI II3

Traitement et analyse d’image

r{"(/, 1)|"(ë, Z): (ë, Z) ≠ (/, 1)} = ∑

(ì,k)Ã*

_(ë, Z)"(/ − ë, 1 − Z)

est un sous ensemble fini de

4 ne contenant pas (0,0).

est un L-champ markovien au sens large si, et seulement Si,

ℤ

où Un processus 2D

(2.13)

"(/, 1) = Ï _(ë, Z)"(/ − ë, 1 − Z) + S(/, 1)

étant un processus stationnaire de densité spectrale (par définition la transformée de Fourier

(ì,k)Ã*

S(/, 1) de la suite de covariance du processus)

4 y$([, ÿ) = ¾$

%1 − Ï _(ë, Z)exp (−2AB(ë[ + Zÿ))

avec

y$([, ÿ)

> 0 et avec

(ì,k)Ã*

4 égale a la variance de

S(/, 1) 4 r{"(/, 1)S(ë, Z)} = ¾$

¹(/, ë)¹(1, Z)

. En plus il est

Il en résulte que la densité spectrale d’un L-champ markovien peut s’écrire

y:([, ÿ) =

4 ¾$

1 − ∑

(ì,k)Ã*

_(ë, Z)exp (2AB(ë[ + Zÿ))

3. TRANSFORMATIONS UNITAIRES BIDIMENSIONNELLES

Les transformations unitaires trouvent principalement deux applications: l’extraction des caractéristiques du signal 2D et la compression des données. Dans la suite nous allons considérer une Suite 2D limitée spatialement. Nous pouvons la représenter donc a l’aide d’une matrice X de dimension M*N. Définissons d’abord une transformation linéaire de X en Y, que nous notons Y=T.X à l’aide de l’équation suivante :

"(/, 1) = ∑

RGI ·˜b

±GI ì˜b

∑

#(Y, ë; /, 1)

!(Y, ë)

(3.1)

Nous considérons uniquement le cas où X et Y appartiennent au même espace, c’est-à- dire Y est , aussi une matrice de dimension M*N. Les matrices constituent la base de la transformation. On peut écrire

{#∗(Y, ë; /, 1)}

, avec éléments

{Φ(/, 1)}

étant le produit scalaire dans l’espace vectoriel des matrices de dimension M*N défini

"(/, 1) = 〈î, Φ(/, 1)〉

〈. , . 〉 comme suivant

〈ø, B〉 = #\(ù

Eétant la transconjuguée de B.

ø)

La transformation adjointe inverse T-1 est telle que

E est définie a I’aide des éléments

{#∗(/, 1; Y, ë)}

. La transformation

est la transformation identité définie par les éléments

où et le domaine transformé est alors identique au domaine spatial. Une transformation est appelée unitaire, si l’inverse existe et est égale à l’adjointe

{¹(Y, /)¹(ë, 1)}

¸ = ¸ ¸

= .

Une transformation est appelée séparable, si l’on peut écrire

= ¸

Dans ce cas nous avons une relation matricielle simple entre X et Y

#(Y, ë; /, 1) = #I(Y, /)#4(ë, 1)

(3.2)

) est une matrice carré de dimension M*M (resp. N*N). Nous pouvons écrire

+ = ¸I

,î¸4

(3.3)

(resp.

où

¸I

¸4

Slim M’HIRI

ENSI II3

Slim M’HIRI

ENSI II3

L’opérateur de la transformation inverse est aussi séparable et donnée par

¸4⨂¸I = .

#I(0,0)¸4 ⋮

⋯ ⋱

#I(0, ¼ − 1)¸4 ⋮

#I(¼ − 1,0)¸4 ⋯ #I(¼ − 1, ¼ − 1)¸4

Où

note le produit direct entre matrices défini ci-après

¸ = ¸4⨂¸I

⨂

Traitement et analyse d’image

et, si la transformation directe est unitaire, on obtient

¸ = ¸4

⨂¸I

Ce noyau est séparable et Ia transformation est unitaire. Le résultat d’une TFD-2D est en général une matrice complexe. La valeur à l’origine dans le domaine transformé est

RGI

±GI

∗ î = ¸I La séparabilité conduit aussi a une réduction du nombre d’opérations arithmétiques nécessaires pour la réalisation de la transformation. Tandis que dans le cas général, il faut M2N2 multiplications, dans le cas d’une transformation séparable il faut MN(M+N) multiplications.

+¸4

"(0,0) =

√¼½ fois la moyenne spatiale de X.

Ï Ï !(Y, ë) ·˜b

ì˜b

C’est-à-dire En ce qui concerne la réalisation de la TFD-2D utilisant la séparabilité, l’on peut l’effectuer à l’aide des algorithmes de TF rapide séparément sur les deux coordonnées.

√¼½

Nous présentons dans la suite quelques transformations parmi les plus utilisées.

Alors le nombre de multiplications sera R±

4 Z®¯4(¼½)

, ¼

étant des puissances de 2.

Transformation de Karhunen-Loève

La transformation de Karhunen-Loève (TKL) s’obtient en utilisant comme base de décomposition celle constituée par les éléments propres de l’opérateur covariance de la matrice X. Cet opérateur est défini de la manière suivante

Soit

{r(/, 1)}

Γ(Y, ë; /, 1) = r{(!(Y, ë) − r(!(Y, ë)))(!(/, 1) − r(!(/, 1)))}

l’ensernble des matrices propres de l’opérateur covariance. La TKL estdonnée par

Si l’opérateur

est séparable

"(/, 1) = 〈î, r(/, 1)〉

alors l’opérateur de la transformation doit l’être également

Γ = Γ4⨂ΓI

) est une matrice carré de dimension M*M (resp. N*N) comprenant les vecteurs

T = T4⨂TI

(resp. TI propres de

(resp.

ΓI

Γ4

La TKL présente plutôt un intérêt théorique que pratique. Elle permet effectivement d’obtenir le meilleur compactage de l’énergie, mais elle nécessite la connaissance a priori de l’opérateur covariance ou au moins son estimation et ensuite la détermination des matrices propres. D’autres transformations unitaires conduisent à un compactage important de l’énergie tout en étant indépendantes d’hypothèses probabilistes ou de problèmes d’estimation statistiques. Nous en présenterons certaines dans la suite.

Transformation de Fourier discrète 2D

La transformation de Fourier discrète 2D (TFD-2D) est définie a l’aide du noyau suivant

Mais ii est aussi possible d’appliquer directement sur la TFD-2D le même principe que celui utilisé avec la TFD-1D pour obtenir des algorithmes rapides. Pour simplifier nous supposons que

M=N et nous exprimons la TFD-2D pour N*N points à l’aide de la TFD-2D pour ±

points.

4 ∗

En posant

5± = exp Š−

2AB ½

%bb(/, 1) = ∑

6 j GI ·˜b

6 j GI ì˜b

∑

!(2Y, 2ë)

5±

4·´E4ì³ (3.5a)

%bI(/, 1) = ∑

6 j GI ·˜b

6 j GI ì˜b

∑

!(2Y, 2ë + 1)

5±

4·´E4ì³ (3.5b)

%Ib(/, 1) = ∑

%II(/, 1) = ∑

6 j GI ·˜b 6 j GI ·˜b

6 j GI ì˜b 6 j GI ì˜b

∑

!(2Y + 1,2ë)

5±

4·´E4ì³ (3.5c)

!(2Y + 1,2ë + 1)

5±

4·´E4ì³ (3.5d)

Nous pouvons écrire

"(/, 1) = %bb(/, 1) + 5± " ?/ +

± 4 , 1D = %bb(/, 1) + 5± ³

± 4D = %bb(/, 1) − 5±

" ?/, 1 + ± 4 , 1 +

" ?/ +

%bI(/, 1) + 5±

%Ib(/, 1)+5±

³E´

%bI(/, 1)

%bI(/, 1) − 5± ´

%bI(/, 1) + 5±

%Ib(/, 1)−5±

³E´

%bI(/, 1)

%Ib(/, 1)−5±

³E´

%bI(/, 1)

(3.6a)

(3.6b)

(3.6c)

(3.6d)

± 4D = %bb(/, 1) − 5±

%bI(/, 1) − 5±

%Ib(/, 1)+5±

³E´

%bI(/, 1)

#(Y, ë; /, 1) =

I √R± S!¿ Š−2AB ?

·´ R +

ì³ ± DŒ

(3.4)

Par analogie au cas 1D nous avons un papillon de base (2*2) donné par la Fig.11.

Slim M’HIRI

ENSI II3

Slim M’HIRI

ENSI II3

Traitement et analyse d’image

Transformation de Walsh-Hadamard

La transformation de Walsh-Hadamard (TWH) est définie par

Avec

#(Y, ë; /, 1) =

¼ = ½ = 2

* et

± (−1):(·,ì;´,³) (3.8)

Fig. 11. Papillon de base (2*2) pour le calcul de la TFD-2D.

Chaque étape comprend ±j 4

papillons. Chacun d’eux nécessite 3 multiplications complexes et

il faut

Z®¯4(½)

comparer à

partitions de ce type. On aura au total 7±j 8

dans le cas séparable II y a donc un gain de 25%.

Z®¯4(½)

multiplications complexes à

Z®¯4(½)

*GI

¿(Y, ë; /, 1) = Ï?Yk

(G)

/k + ëk

1kD

sont les termes de la représentation binaire m et n respectivement. Par exemple pour

k˜b

où

m=6 (mod 10), nous avons m=110 (mod 2) avec m2=1, m1=1 et m0=O. Les 1k s’obtiennent à partir des représentations binaires de i et k respectivement de la manière suivante

(G)et Yk

ëk

(G)

(pour

(G)) Yk

= Y*GI + Y*G4 ………………