Traitement et reconnaissance d'images (TERI)

Exemple :

l'illusion de l' chiquier.

Plusieurs m canismes sont en

niveau

jeu,

(renforcement

des

contrastes) au tr s haut niveau

(interpr tation de

l'ombre et

reconnaissance d'un chiquier)

bas

local

tr s

Antoine MANZANERA Cours TERI Master IAD UPMC Paris 6

page 11

TI & perception visuelle

du

Exemple :

l'illusion de l' chiquier.

Plusieurs m canismes sont en

niveau

jeu,

(renforcement

des

contrastes) au tr s haut niveau

(interpr tation de

l'ombre et

reconnaissance d'un chiquier)

bas

local

tr s

Antoine MANZANERA Cours TERI Master IAD UPMC Paris 6

page 12

I 1 Types d'images, de capteurs

Ph nom ne physique

Grandeur mesur e

Capteur

mission et r flexion

de la lumi re visible

Rayonnement

infra rouge

R flectivit , luminance,...

CCD, CMOS,

Barrettes CCD,...

Luminance IR (chaleur), ...

Bolom tres,...

cho ultra sonore

Distance, densit de tissus,...

chographie,

sonar,...

R sonance magn tique

Pr sence d'un corps chimique,...

IRM, RMN,...

cho lectromagn tique

Distance, sp cularit de surfaces,..

Radar, SAR,...

Absorption des rayons X

Densit de tissus,...

Radiographie,

tomographie,...

Antoine MANZANERA Cours TERI Master IAD UPMC Paris 6

page 13

Images num riques

x

R(x,y)

I(x,y)

y

L' chantillonnage est le proc d de discr tisation spatiale

d'une

image consistant associer chaque zone

rectangulaire R(x,y) d'une image continue une unique

valeur I(x,y).

On parle de sous chantillonnage lorsque l'image est

d j discr tis e et qu'on diminue le nombre d' chantillons.

La quantification d signe la limitation du nombre de valeurs diff rentes que peut

prendre I(x,y).

Une image num rique est une image chantillonn e et quantifi e.

Antoine MANZANERA Cours TERI Master IAD UPMC Paris 6

page 14

O

j

Hauteur

Pixels et niveaux de gris

Largeur

i

Indice de

colonne

Le pixel

I = N

Indice de

ligne

Une image num rique I

Valeur

Niveau de gris

]

N valeurs r elles.

La convolution de I par h est d finie par :

x 2

Ih [ x , y ]=

i= x

1

y 2

j = y

1

h I [ x i , y j ]

Propri t s de la convolution :

COMMUTATIVIT

hg= gh

ASSOCIATIVIT

hg k = h gk = hgk

DISTRIBUTIVITɠ/ +

h g k = hg hk

La fonction h est dite

noyau de convolution

x

h [ x , y ]

y

Les nouvelles valeurs du pixel

sont calcul es par produit scalaire

entre le noyau de convolution et le

voisinage correspondant du pixel.

Antoine MANZANERA Cours TERI Master IAD UPMC Paris 6

page 24

La Convolution

Exemple :

1/152

5

5

5

11

11

11

16

16

16

11

11

11

5

5

5

16

16

16

16

24

24

24

24

16

16

16

16

5

5

5

11

11

11

11

16

16

16

16

11

11

11

11

5

5

5

calculer une

convolution, on

Pour

remplace la valeur de chaque pixel par la

valeur du produit scalaire entre les valeurs

du noyau de convolution et les valeurs du

voisinage du pixel consid r (par rapport

l'origine (0,0) du noyau de convolution).

Attention : impl mentation parall le .

Antoine MANZANERA Cours TERI Master IAD UPMC Paris 6

page 25

III 2 : Le mod le fr quentiel

Le mod le fr quentiel tend d crire l'image en termes de structures p riodiques, en la

d composant dans une base de fonctions p riodiques simples, comme des sinuso des :

La transform e de Fourier :

Outil fondamental d'analyse en traitement du signal, le pendant bidimensionnel de la TF et sa version

discr te peut tre appliqu avec profit aux images num riques. Si son utilisation en tant qu'outil

analytique et algorithmique s'est estomp e en traitement d'images au profit d'approches mieux adapt es

la localisation spatiale des fr quences (ondelettes), elle reste un outil th orique et p dagogique important :

la formalisation du ph nom ne de l'aliasing et des contraintes d' chantillonnage en est un exemple (voir

cours Espace d' chelles).

Antoine MANZANERA Cours TERI Master IAD UPMC Paris 6

page 26

Transform e de Fourier

La transform e de Fourier permet la d composition d'un signal f en combinaison lin aire de

sinuso des complexes, dont les coefficients F dit coefficients de Fourier, fournissent des

informations sur les fr quences (u,v) et permettent des manipulations dans le domaine

fr quentiel.

Transform e de Fourier discr te bidimensionnelle :

(x,y) sont les coordonn es

du domaine spatial

Directe :

w1

F =

x =0

h 1

y= 0

f [ x , y ]e2i ux vy / wh

(u,v) sont les coordonn es

du domaine fr quentiel

Inverse :

f [ x , y ]=

1

wh

w1

u=0

h1

v=0

F e2i ux vy /wh

Propri t s de la transform e de Fourier (1) :

CRITURE SOUS FORME MODULE / PHASE

F [ u , v]=%F [ u , v]%e i [ u , v ]

P RIODICIT

F [ u , v]= F [ u w , v h ]

SYM TRIE

Si F est la transform e de Fourier d'une fonction r elle f :

Antoine MANZANERA Cours TERI Master IAD UPMC Paris 6

page 27

F [ u , v]= F

et donc :

%F [ u , v ]%=%F %

et

=

Transform e de Fourier

Image

Module

v

Phase

v

u

u

f [ x , y ]

ln %F %

Propri t s de la transform e de Fourier (2) :

TF

[ u , v]}

{ f [ x , y ] F [ u , v ]

[ x , y ] F 1

[ x , y ] F 2

[ u , v ]

f 1

f 2

si

CORRESPONDANCE CONVOLUTION / PRODUIT

f 1

[ x , y] f 2

[ x , y] F 1

[ u , v ] F 2

[ u , v]

f 1

[ x , y] f 2

[ x , y ] F 1

[ u , v ]F 2

[ u , v]

D RIVATION

f [ x , y ]

x

iuF [ u , v ]

et

f [ x , y ]

y

ivF [ u , v ]

Antoine MANZANERA Cours TERI Master IAD UPMC Paris 6

LINEARIT

a f 1

[ x , y ] b f 2

[ x , y ] a F 1

[ u , v ] b F 2

[ u , v]

TRANSLATIONS SPATIALES / FR QUENTIELLES

f [ x x ' , y y ' ] F e2i ux ' vy ' /wh

f [ x , y ] e 2i u ' x v ' y / wh F

TH OR ME DE PARSEVAL

w1

x =0

h1

y =0

% f [ x , y ]%2

=

1

wh

w1

u= 0

h 1

v =0

%F [ u , v ]%2

page 28

QUIZZ Transform e de Fourier

Attribuez chaque image son spectre de Fourier

(1)

(2)

(3)

(4)

(a)

(b)

(c)

(d)

Antoine MANZANERA Cours TERI Master IAD UPMC Paris 6

QUIZZ Transform e de Fourier

Attribuez chaque image son spectre de Fourier

(1)

(2)

(3)

(4)

(a)

(b)

(c)

(d)

Antoine MANZANERA Cours TERI Master IAD UPMC Paris 6

III 3 : Le mod le statistique

On s'int resse dans ce mod le aux propri t s statistiques des images : la distribution des

valeurs prises par les pixels, la corr lation existant entre des pixels spatialement proches, la

fr quence d'occurrence de certaines structures spatiales...

Les mesures statistiques fournissent des grandeurs et fonctions empiriques sur lesquelles

peuvent s'appuyer des mod les probabilistes utilis s par les algorithmes d'analyse d'images.

Par exemple, le mod le des champs de Markov consid re l'image comme la r alisation d'un

champ al atoire (chaque pixel correspondant une variable al atoire), o la valeur prise par

un pixel ne d pend que de celle de ses voisins (selon une topologie discr te donn e, voir

plus loin).

Antoine MANZANERA Cours TERI Master IAD UPMC Paris 6

page 31

III 3 : Le mod le statistique

Un autre exemple remarquable d'analyse statistique est l'utilisation des matrices de co

occurrence, habituellement utilis es pour caract riser les textures.

j

La matrice de co occurrence M

associ e au

vecteur v, est la matrice de taille N x N ( N est le

(i,j)

nombre de niveaux de gris), tel que M

repr sente la fr quence du couple de valeurs (i,j)

parmi les couples de pixels (x,x+v).

v

v

i

v

i

j

Ces techniques, et d'autres exemples de mod les statistiques seront pr sent es plus en

d tail dans les prochains cours. Dans le cadre de cette introduction, nous d velopperons

seulement le premier outil statistique d'analyse des images : l'histogramme.

L'histogramme :

Outil de base pour l' tude des capteurs ou de la dynamique d'une sc ne, il est utilis par certains

op rateurs d'analyse. On retiendra cependant qu'il ne faut pas consid rer l'histogramme comme une

caract ristique fondamentale de l'image dans la mesure o on peut le transformer radicalement sans

changer significativement l'image.

Antoine MANZANERA Cours TERI Master IAD UPMC Paris 6

page 32

Histogramme

W

Histogramme

Effectif

H

H(x)

H(x) est le nombre

de pixels dont le

niveau de gris est

gal x.

Il

L'histogramme repr sente la

r partition des pixels en

fonction de leur niveau de

gris.

diverses

fournit

les

informations

statistiques d'ordre (voir ci

(voir

contre),

pr c demment),

peut

permettre d'isoler des objets.

l'entropie

et

comme

Histogramme cumulatif normalis

Niveau de gris

Effectif

relatif

HC(x)

x

i= 0

H x

W H

HC x =

HC(x) est le taux

de pixels dont le

niveau de gris est

inf rieur x.

Antoine MANZANERA Cours TERI Master IAD UPMC Paris 6

Min

M dian

Max

Niveau de gris

page 33

Traitement base d'histogramme

On pr sente dans la suite quelques traitement d'analyse effectu s uniquement partir

de l'histogramme. Retenons que certains de ces traitements sont souvent calcul s au

niveau des capteurs, et qu'en g n ral leur pertinence est tr s intimement li e aux

conditions d'acquisition.

(1) Normalisation

exploiter toute la dynamique de codage.

(2) galisation

quilibrer la dynamique de codage et augmenter le contraste.

(3) Segmentation

simplifier l'image en regroupant les pixels selon leurs valeurs.

Antoine MANZANERA Cours TERI Master IAD UPMC Paris 6

page 34

Histogramme : normalisation

La normalisation d'histogramme, ou expansion de dynamique, est une transformation affine

du niveau de gris des pixels de telle sorte que l'image utilise toute la dynamique de

repr sentation.

ϠD : dynamique

ϠNmin : la plus petite

valeur dans l'image

ϠNmax : la plus

grande valeur dans

l'image

f new

[ x , y ]= f [ x , y ]Nmin

2 D1

Nmax Nmin

Pour rendre la normalisation moins sensible

aux valeurs marginales (outliers), on utilise

g n ralement un param tre , 0< <1,et on

prend :

Nmin HC1

Nmax HC 1 1

image d'origine f

Nmin

Nmax

2D 1

histogramme d'origine

Antoine MANZANERA Cours TERI Master IAD UPMC Paris 6

expansion de dynamique

f

new

histogramme normalis

page 35

Histogramme : galisation

L' galisation d'histogramme est une transformation des niveaux de gris dont le principe est

d' quilibrer le mieux possible la distribution des pixels dans la dynamique (Id alement, on

cherche obtenir un histogramme plat).

La technique classique consiste rendre le plus lin aire

possible l'histogramme cumul de l'image en utilisant la

transformation suivante :

f new

[ x , y ]= 2 D1

HC f [ x , y]

wh

ϠD : dynamique

Ϡ(w,h) : dimension de l'image

ϠHC(.) : histogramme cumul

Histogramme de f

Histogramme de f

new

Original f

Histogramme

cumul de f

Histogramme

cumul de f

new

Apr s galisation f

new

Le r sultat est une augmentation globale du contraste dans l'image. Notez dans l'exemple ci dessus l'accentuation

des d fauts avec la mise en vidence du bruit spatial fixe (effet de tramage) de l'imageur infra rouge.

Antoine MANZANERA Cours TERI Master IAD UPMC Paris 6

page 36

Histogramme : segmentation

Il existe des techniques de segmentation bas es sur un regroupement des niveaux de gris

partir de l'histogramme. Ces techniques sont rarement efficaces car elles ne consid rent que

la valeur des pixels sans tenir compte de crit res g om triques ou topologiques (voir cours

Segmentation).

Par exemple, la m thode ci dessous calcule un certain nombre de quantiles partir de

l'histogramme cumul , les regroupe par classes en fonction d'un crit re de distance, puis

attribut la m me tiquette aux pixels dont la valeur est la plus proche d'une classe donn e :

Image originale

Histogramme cumul avec

agr gation des quantiles

Antoine MANZANERA Cours TERI Master IAD UPMC Paris 6

Image segment e

page 37

III 4 : Le mod le diff rentiel

Dans le mod le diff rentiel, on consid re l'image comme une fonction continue f(x,y),

dont on tudie le comportement local l'aide de ses d riv es.

Une telle tude, fond e sur la formule de Taylor, n'a de sens que si la fonction f a une

certaine r gularit , ce qui constitue le probl me clef des m thodes diff rentielles.

I

I

x

x

Au premier ordre, on peut ainsi associer chaque point

(x,y) un rep re propre (t,g), o le vecteur t donne la

direction de l'isophote (ligne de variation minimale) et g

la direction orthogonale, celle du gradient.

le continu,

le mod le

Gr ce au plongement dans

diff rentiel permet en outre d'exprimer un grand nombre

d'op rations d'analyse en termes d' quations aux d riv es

partielles (EDP), ce qui permet de donner un fondement

math matique satisfaisant aux traitements et aussi de

fournir des m thodes pour les calculer, par des sch mas

num riques de r solution.

g

g

f

f

t

t

y

y

Antoine MANZANERA Cours TERI Master IAD UPMC Paris 6

page 38

(cid:209)

(cid:209)

III 5 : Le mod le ensembliste

En morphologie math matique, l'image est consid r e comme un ensemble, dont on

tudie les propri t s en fonction de relations locales avec un ensemble de r f rence

( l ment structurant) en termes d'intersection et d'inclusion (relations en tout ou rien).

B ) X =

B X

B ) X `

Antoine MANZANERA Cours TERI Master IAD UPMC Paris 6

page 39

rosion et Dilatation

Les transformations morphologiques sont d finies partir des 2 op rateurs ensemblistes de

base que sont l' rosion et la dilatation

Original (Matisse 1952)

B X ={x 2 ; B x X }

B X ={x 2 ; B x ) X `}

( l ment structurant : disque)

Antoine MANZANERA Cours TERI Master IAD UPMC Paris 6

page 40

rosion et Dilatation

L' rosion et la dilatation, et par suite l'ensemble des transformations morphologiques, se

g n ralisent des ensembles (Images binaires) aux fonctions (Images en niveaux de gris) par

l'interm diaire des ensembles de niveaux :

I n={x 2 ; I x n }

MIN

MAX

Original (Man Ray 1924)

B I

B I

( l ment structurant : losange)

Antoine MANZANERA Cours TERI Master IAD UPMC Paris 6

page 41

III 6 : Le mod le discret

La g om trie discr te est une discipline au moins aussi ancienne que le traitement

d'images. Alors que le mod le diff rentiel consid re les structures g om triques

(courbes, surfaces, droites, etc) comme des approximations num riques de leurs

homologues continues, ou que le mod le fr quentiel traduit la discr tisation en termes de

perte d'information, le mod le discret, lui, int gre l'espace chantillonn comme cadre

math matique, et s'efforce de donner un cadre formel aux structures g om triques

discr tes : d finition, propri t s, th or mes,...

Quelle est la distance

entre les 2 points ?

Qu'est ce qu'un trou ?

Qu'est ce

droite ?

qu'une

Antoine MANZANERA Cours TERI Master IAD UPMC Paris 6

page 42

Pavages du plan

Un pavage du plan est une partition du plan en cellules l mentaires (pixels).

Il n'existe que 3 pavages r guliers du plan :

triangulaire

carr

hexagonal

... mais de nombreux pavages irr guliers :

Antoine MANZANERA Cours TERI Master IAD UPMC Paris 6

page 43

Pavages du plan

D'autres pavages irr guliers du plan...

Pavage ap riodique de Penrose

Antoine MANZANERA Cours TERI Master IAD UPMC Paris 6

page 44

Pavage p riodique d'Escher

Pavages et maillages

A tout pavage du plan on peut associer un graphe o les sommets (noeuds) repr sentent

les cellules l mentaires, et o les ar tes repr sentent la relation d'adjacence entre les

cellules (2 cellules sont adjacentes si elles ont un c t en commun). Un tel graphe est un

maillage du plan.

Les pavages et les maillages r guliers sont duaux :

Questions :

repr sentation dans Z2 ?

combien de directions ?

r cursivit ?

Pavage triangulaire

Pavage carr

Pavage hexagonal

Maillage hexagonal

Maillage carr

Maillage triangulaire

Antoine MANZANERA Cours TERI Master IAD UPMC Paris 6

page 45

Maillage et connexit

Les relations topologiques dans les images discr tes sont d finies partir de la relation

de connexit induite par le graphe du maillage (X,S), o X repr sente les sommets et S les

ar tes.

X $2 ; S X 2

Soient x et y 2 points de X, par d finition x et y sont voisins si :

xH y Ԟ x , y S

maille carr e

4 connexe

maille carr e

8 connexe

maille triang.

6 connexe

La cl ture transitive de la relation de voisinage est une relation d' quivalence

il existe un chemin connexe entre x et y :

}/ xH x1, ... , x i

Les classes d' quivalence de cette relation s'appellent les composantes connexes de X

x~ y {x 1, ... , x n

H x i 1 , ... , x n

H y

Antoine MANZANERA Cours TERI Master IAD UPMC Paris 6

Topologie dans la maille carr e

Dans la maille carr e, la notion de trou dans un objet X (X Z2), qui doit correspondre

une composante connexe finie du compl mentaire Xc, n'est pas bien d finie...

Ce probl me est li la validit du th or me de

Jordan, selon lequel une courbe simple ferm e

s pare le plan en 2 composantes connexes, dont

une born e.

8 connexit

4 connexit

...sauf si l'on consid re des connexit s diff rentes pour X et pour Xc :

(8,4) connexit

(4,8) connexit

Le th or me de Jordan est v rifi

pour ces connexit s.

Antoine MANZANERA Cours TERI Master IAD UPMC Paris 6

Questions :

de

combien

composantes

connexes, combien de trous

compte l'image ci contre

en (8,4) connexit ?

en (4,8) connexit ?

M trique dans la maille carr e

Le graphe du maillage induit galement une distance dans le plan discret, la distance

entre 2 points x et y tant d finie par la longueur du plus court chemin connect entre x et

y. En pond rant toutes les ar tes du maillage par la valeur 1, on trouve :

distance de la 4 connexit

d 4 x , y =#x1 y 1# #x 2 y 2#

1

1

1

distance de la 8 connexit

d 8 x , y = max #x 1 y1#,#x 2 y 2#

On peut aussi pond rer diff remment les ar tes du maillage 8 connexe, voire utiliser des

maillages plus complexes (i.e. des voisinages plus grands) :

4

3

distance du

chamfrein (3,4)

11

7

55

distance du

chamfrein (5,7,11)

Questions :

y

(x,y), d

calculer les distances d

(x,y), d

4

8

entre les 2 points x et y ci contre :

(x,y), d

ch(3,4)

ch(5,7,11)

(x,y)

x

Antoine MANZANERA Cours TERI Master IAD UPMC Paris 6

Conclusion

quivalence convolution /

multiplication

mod le

lin aire

mod le

fr quentiel

Ondelettes

Corr lation

ACP

mod le

statistique

Morphologie

statistique

.../...

mod le

ensembliste

Filtres

diff rentiels

mod le

diff rentiel

EDP / Ensemble

de niveaux

A retenir pour ce cours :

image num rique

chantillonnage

quantification

histogramme

convolution

repr sentation fr quentielle

connexit et distance

discr tes

Antoine MANZANERA Cours TERI Master IAD UPMC Paris 6

page 49

Sources et bibliographie Liens utiles

Livres :

ϠJ.P. Cocquerez et S. Philipp Analyse d'images : filtrage et segmentation Masson 1995

ϠR.C. Gonzalez et Woods Digital Image Processing 2d edition

Addison Wesley 2002

ϠA. Rosenfeld et A.C. Kak Digital picture processing Academic Press London 1982.

ϠH. Ma tre (ss la direction de) Le traitement des images Hermes Lavoisier IC2 2003.

ϠJ.R. Parker Algorithms for Image Processing and Computer Vision Wiley & Sons 1997.

ϠS. Bres, J.M. Jolion, F. Lebourgeois Traitement et analyse des images num riques

2003

Hermes Lavoisier

ϠI.T. Young, J.J. Gerbrands et L.J. Van Vliet Fundamentals of Image Processing Universit de Delft.

internet : http://www.ph.tn.tudelft.nl/~lucas/publications/1995/FIP95TYJGLV/FIP2.2.pdf)

(sur

ϠD. Lingrand Introduction au Traitement d'images Vuibert 2004

Pages web :

ϠTelesun INSA : http://telesun.insa lyon.fr/~telesun/

ϠUniv. de Delft : http://www ict.its.tudelft.nl/html/education/courses/

ϠProjet Marble : http://www.icbl.hw....