1

Echantillonnage,Filtrage numérique (convolution discrète) Analyse en fréquence (transformée de Fourier discrète)

TRAITEMENT NUMERIQUE DES IMAGES

2

échantillonnage (pixelisation)

g g g

ggg

de 4x4 à 128x128 pixels

3

mais une « brosse » d’impulsionsvariant en amplitude d’après la théorie de l’échantillonnage, l’image

n’est pas un pavage de pixels

attention à l’interprétation de l’échantillonnage

x

y

x

y

4

la transformée de Fourier d’une brosse périodique d’impulsions de Dirac b(x,y)est une brosse d’impulsions de Dirac B(u,v) dans le domaine des fréquences

la transformée de Fourier de l’image échantillonnée est périodique

pour reconstituer l’image continue dans le domaine spatial, il faut queson support soit limité dans le domaine des fréquences

la fonction d’interpolation idéale est la tranformée de fourier inversede la fonction support dans le domaine des fréquences (carré en général)

dans le domaine spatial :l’échantillonnage correspond au produit de f(x,y) par b(x,y)

dans le domaine des fréquences : convolution de F(u,v) et de B(u,v)

interprétation fréquentielle de l’échantillonnage

5

128 96 64 32 0 32 64 96 1280

2

4

6

.

128 96 64 32 0 32 64 96 1280

0.2

0.4

.

Fréquence

Fréquence

Rappel du cas monodimensionnel :

- l’échantillonnage se traduit par la périodisation de la transformée de Fourier - pour retrouver le signal initial, il ne faut pas que les répliques se chevauchent

- récupération du signal initial par filtrage passe bas

n

echechech

echech nTxTTnt

TTnttx )(.

/)..(

/).(sin)(

6

Rappel : la transformée de Fourier d’une suite régulière d’impulsions(théorème de Shannon dans le cas monodimensionnel)

par transformée de Fourier un produit dans le domaine spatial devient une convolution

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 160.5

0.5

1.5

.

s(t)

t0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

0.5

0.5

1.5

.

S()

T.Fourier

7

première étape

illustration du théorème d’échantillonnagedes signaux bidimensionnels

étude de la fonction d’échantillonnage et sa transformée de Fourier

8

UNE BROSSE REGULIERE D IMPULSIONS

9

EST LE PRODUIT DE DEUX ‘‘LIVRES’’

livrex livrey

livrey livrex( )

x =

x

y

x

y

x

y

10

brosse

livrex livrey

x

y

x

y

x

y

exemple avecmoins de pagesdans le livre

11

la transformée de Fourier de la brosse est la convolution destransformées de Fourier des deux livres(par transformation de Fourier, le produit devient une convolution)

les transformées de Fourier des livres sont des peignes d’impulsionsleurs supports sont respectivement l’axe u et l’axe vnous les nommons ¨PX(u,v) et PY(u,v)

LIVREX LIVREY

livrex LIVREX

T.Fourier

x

y

u

v

u

v

u

v

*

12

la convolution de PY(u,v) avec une des impulsions (placée en u0) se traduitpar la création d’une réplique de PY(u,v) translatée en u0

LIVREDEC

la convolution de PY(u,v) avec PX(u,v)est la somme de toutes les répliquesde peignes décalées, c’est-à-dire une brosse

LIVREY BROSSE

u

v

u

v

u

v

13

utilisation de ce résultat pour interpréter l’effet de l’échantillonnage spatial dans le domaine des fréquences

deuxième étape :

14

dans le domaine spatial, l’échantillonnage d’une fonction f(x,y)se traduit comme un produit de f(x,y) par la fonction d’échantillonnage (la brosse)

f

g( )

avant échantillonnage après échantillonnage

x

y

x

y

15f g( )

autre image où les variations sont plus rapides(il y a plus de hautes fréquences)

avant échantillonnage après échantillonnage

x

y

x

y

16

la transformée de Fourier de la fonction échantillonnée est la convolutionde la transformée F(u,v) de f(x,y) par la transformée de Fourier de la brossequi est elle aussi une brosse

FDEC

GDEC

la convolution par la brosse est la somme des répliques décalées à laposition de chacune des impulsions de la brosse

u

v

u

v

17

retrouver la fonction dans le domaine spatial est équivalent à la retrouver dans le domaine des fréquences

FDEC

GDEC

il ne faut garder qu’une composante fréquentielleil ne faut pas que les répliques décalées se chevauchent

u

v

u

v

18

ici le pas d’échantillonnage est trop grand et les répliques se chevauchentil n’est pas possible de retrouver la fonction initiale par une simple sélection

FDEC

GDEC

u

v

u

v

19

FDEC

GDEC

sélectionner la réplique = effectuer un filtrage passe bas

u

v

u

v

20

« spectre » de l’image initiale (fonction continue de l’espace)

« spectre » de l’image échantillonnée

reconstitution de l’image initiale par filtrage passe bas (interpolation)

fFC

gG

domaine spatial domaine des fréquences

échantillonnage reconstruction

DANS LE DOMAINE DES FREQUENCES : convolution de la tf par une brosse d’impulsions = répétition du spectre suivant la brosse

DANS LE DOMAINE SPATIAL : produit par la « brosse » d’échantillonnage

21

Remarque : il est possible de choisir des motifs de « pavage » différentsmieux adaptés aux caractéristiques spectrales de l’image à échantillonner

ce qui se traduira dans le domaine spatial par un échantillonnage en quinconce plus économique que l’échantillonnage sur un motif carré

par exemple si le spectre de l’image est à symétrie circulaire, le support hexagonal permettra un pavage plus compact que le support carré

22

effectuer le filtrage dans le domaine spatial

calcul de la réponse impulsionnelle du filtre par transforméede Fourier inverse : c’est la transformée de Fourier inversed’un pavé (produit de deux créneaux monodimensionnels en u et v)

sts

x

y

x

y

23

hh.

pour reconstruire l’image à partir de ses échantillons (pixels) il faut que son support spectral soit limité à la moitié de la fréquence d’échantillonnage dans les deux directions u et v ; on en déduit (par transformée de Fourierinverse de la fonction constante sur un support carré) la réponse impulsionnelledu filtre interpolateur

interpolation idéale (voir le cours de traitement numérique du signal)

24

hh.

NOTER LESOSCILLATIONS« Parasites »

25

application à la rotation

)cos.sin.,sin.cos.(),( qpqpfqpg

p

q

)cos.sin..(

)cos.sin..(sin.

)sin.cos..(

)sin.cos..(sin).,(),(

nqp

nqp

mqp

mqpnmfqpf

m n

l’antécédent d’un pixel n’appartient pas à la grille !

)cos.sin.( qp )sin.cos.( qp

calcul par interpolation de

26

gh

gh 255 0.8 2550.2

impulsion « parfaite » avant rotation

impulsion après rotation on voit les oscillationsdes fonctions sinc

gh

gh 255 0.8 2550.2

27

reconstruction par interpolationéchantillonnage

).(

).(sin.

).(

).(sin).,(),(

ny

ny

mx

mxnmfyxf

m n

difficulté : somme infinie, la convergence n’est pas assurée !

combien faut il calculer de termes pour que le résultat ait une précision suffisante(par exemple 10bits soit 1/1000)

approximation : par des fonctions prenant en compte un nombre plus réduit de pixels dans le voisinage de l’échantillon traité

m n

nymxhnmfyxf ),().,(),(

http://www.mathcurve.com/surfaces/beziersu/beziersu.shtml

surfaces de Bézier

28

reconstruction pratique interpolation linéaire par morceaux

réponse impulsionnelle pyramidale

29

éventuellement interpolation plus élaborée tenant compte des caractéristiques spécifiques de l’image : régions lisses, contours nets par exemple

30

FAUT IL RESPECTER LES CONDITIONS DE SHANNON ?

apparition de franges sur les contours

31

inconvénient du filtre passe bas idéal :

les oscillations parasites (Gibbs, Fraunhofer, Airy)

32

transformée de Fourier discrète bidimensionnelle

pas de perte d’information : calculer autant de valeurs dans le domaine des fréquences que dans le domaine spatial (transformée de Fourier inverse)

1

0

1

02

...2exp).,(.

1),(

T

u

T

v T

yvxujvuF

Tyxf

1

0

1

0

...2exp),(),(

T

x

T

y T

yvxujyxfvuF

chaque composante étant calculée par la transformée

(expression de la transformée inverse)

valeurs discrètes (ici entières) de u et de v tout comme de x et de y

33

fréquence (0,0)

il est préférable de placer la fréquence (0,0) au centre

Présentation visuelle du résulta de la transformée de Fourier discrète

la transformée de Fourier discrète (signal échantillonné) est périodique

fréquence d’échantillonnage

½ fréquence d’échantillonnage

34

Présentation visuelle du résulta de la transformée de Fourier discrète

35

Présentation visuelle du résulta de la transformée de Fourier discrète

36

Présentation visuelle du résulta de la transformée de Fourier discrète

37

Présentation visuelle du résulta de la transformée de Fourier discrète

38

il est préférable de placer la fréquence (0,0) au centre

Présentation visuelle du résulta de la transformée de Fourier discrète

la transformée de Fourier discrète (signal échantillonné) est périodique

39

Calcul basé sur la transformée de Fourier rapide monodimensionnelle

1

0

1

0

...2exp),(),(

T

x

T

y T

yvxujyxfvuF

T

yvj

T

xujyxfvuF

T

y

T

x

..2exp

..2exp),(),(

1

0

1

0

1

0

..2exp),(),(

T

x T

xujyxfyuG

on commence par calculer la TF monodimensionnelle de chaque ligne

T

yvjyuGvuF

T

y

..2exp),(),(

1

0

puis la TF monodimensionnelle de chaque colonne de ce tableau intermédiaire

40

1

0

..2exp),(),(

T

x T

xujyxfyuG

T

yvjyuGvuF

T

y

..2exp),(),(

1

0

x

y

u

y

u

y

1. calcul de la transformée monodimensionnelle de chaque ligne de l’image et rangementdans un tableau où la variable en abscisse est u et non plus x

u

v

2. sur ce deuxième tableau, calcul de la transformée monodimensionnellecolonne par colonne et rangement dans un tableau où la variableen ordonnée est maintenant v

f (x,y) G (u,y)

G (u,y)F (u,v)

41

Convolution 2D par transformée de Fourier / produit /

transformée de Fourier inverse

' '

)','()','(),(x y

yxfyyxxhyxg

),(

),(

vuF

yxf

),(

),(

vuH

yxh

),(

),(

vuG

yxg

IMAGEINITIALE

EFFET IMAGEMODIFIEE

),().,(),( vuFvuHvuG

42

Convolution 2D par transformée de Fourier / produit / transformée de Fourier inverse

attention : tout se passe comme si les images et leurs transformées étaient périodiques

échantillonnage spatial = périodisation de la transformée de Fourier

échantillonnage de la transformée = périodisation dans le domaine spatial

1

0

1

0

...2exp),(),(

T

x

T

y T

yvxujyxfvuF

valeurs discrètes (ici entières) de u et de v tout comme de x et de y

1

0

1

02

...2exp).,(.

1),(

T

u

T

v T

yvxujvuF

Tyxf

43

Illustration avec la transformée de Fourier bidimensionnelle

Lorsqu’on effectue une convolution (nécessairement circulaire)en utilisant la transformée de Fourier discrète, le résultat est unefonction périodique dont la période est la dimension du signal (ici 128)

le résultat de la convolution qui déborde en haut de l’image seretrouve reproduit en bas du fait de la périodisation implicite

convolution de f et de g

44

le résultat est réel (mais peut se déduire de la transformée de Fourier)

utilisée en compression jpeg et mpeg

cos

cos

45

application à des médaillons 8x8 ; compression par élimination des composantesde très faible amplitude, et quantification grossière des amplitudes faibles

46

47http://www.egr.msu.edu/waves/people/Ali_files/DCT_TR802.pdf

orig

inal

ou

com

pres

sion

à 5

0%co

mpr

essi

onà

25%

48

transformée en ondelettes (wavelets) JPEG2000

http://fr.wikipedia.org/wiki/Compression_Ondelette_(Images)

antonini, barlaud, mathieu (traitement d’images SI5)

hautes fréquenceshorizontales

basses fréquenceshorizontales

hautes fréquencesverticales

basses fréquencesverticales

filtrage

filtrage

49

vertx 0 lignes rouge( ) 1 rouge

50

log fc

30 log fc

128

points communs entre la DCT et la compression par ondelettes transforméede Fourier

partentière log fc

0 bit

2bits3bits et plus

1 bit

les hautes fréquences sont peuénergétiques, il n’est pas nécessaired’utiliser beaucoup de bits pour les coder

51

signaux aléatoires bidimensionnels

les définitions et les propriétés fondamentales sont des extensions directesde celles qui sont données en traitement du signal monodimensionnel

filtrage des signaux aléatoires

autocorrélation

stationnarité : invariance spatiale des propriétés statistiques

moyenne, variance

densité spectraletransformée de Fourierde la fonction d’autocorrélation

52

bruit blanc : échantillons indépendants

autocorrélation nulle sauf à l’origine m=n=0(valeur de la variance)

densité spectrale constante mais fluctuations importantes autour de cette moyenne constante

x

y

x

y

u

v

x

y

domaine

spatial

domaine

fréquen

tiel