Quelques méthodes mathématiques pour le traitement d'image

Page 1 sur 110Lecteur de document UniversityLib

Quelques méthodes mathématiques pour le traitement d'image

Image Processing and Mathematical Analysis · course

Voir tous les documents en mathématiques

Quelques méthodes mathématiques pour le traitement

d’image

2 janvier 2009

Ce cours est une introduction à la théorie mathématique de traitement de l’image . Il est donc

incomplet car les méthodes dans ce domaine sont nombreuses et variées. On se polarisera sur

les méthodes variationnelles.

M. Bergounioux

Master 2 - 2008-2009

2

Chapitre 1

Introduction

1.1 Qu’est-ce qu’une image numérique ?

Une image numérique est composée d’unités élémentaires (appelées pixels) qui représentent

chacun une portion de l’image. Une image est définie par :

– le nombre de pixels qui la compose en largeur et en hauteur (qui peut varier presque à

l’infini),

– l’étendue des teintes de gris ou des couleurs que peut prendre chaque pixel (on parle de

dynamique de l’image).

1. Les images binaires (noir ou blanc)

Exemple, images les plus simples, un pixel peut prendre uniquement les valeurs noir ou

blanc. C’est typiquement le type d’image que l’on utilise pour scanner du texte quand

celui ci est composé d’une seule couleur.

2. Les images en teintes de gris

En général, les images en niveaux de gris renferment 256 teintes de gris. Image à 256

couleurs, simplement chacune de ces 256 couleurs est définie dans la gamme des gris.

Par convention la valeur zéro représente le noir (intensité lumineuse nulle) et la valeur

255 le blanc (intensité lumineuse maximale).

3. Les images couleurs

S’il existe plusieurs modes de représentation de la couleur, le plus utilisé pour le manie-

ment des images numériques est l’espace couleur Rouge, Vert, Bleu (R,V,B).

Cet espace couleur est basé sur la synthese additive des couleurs, c’est a dire que le

mélange des trois composantes (R, V, B) donne une couleur.

3

4

CHAPITRE 1. INTRODUCTION

1.1.1 Quelques définitions

Pixels et niveaux de gris

Echantillonnage et quantification

1.1. QU’EST-CE QU’UNE IMAGE NUM ÉRIQUE ?

5

L’échantillonnage est le procédé de discrétisation spatiale d’une image consistant à asso-

cier à 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.

Une image numérique est une image échantillonnée et quantifiée. La quantification désigne

la limitation du nombre de valeurs différentes que peut prendre I(x, y).

L’échantillonnage est une étape fondamentale qui doit tenir compte du contenu informa-

tionnel pertinent de l’image à analyser. Sur l’exemple ci- dessous, en 1d, le signal échantillonné

« ressemble » à une sinuso¨ıde de fréquence 8 fois plus faible :

6

CHAPITRE 1. INTRODUCTION

Ce phénomène appelé aliasing est encore pire en 2D, car il affecte la fréquence et la direction

des structures périodiques. Imaginons par exemple qu’on souhaite échantillonner l’image cor-

respondant aux bandes noires ci-dessous :

Avec un échantillonnage adapté, l’image numérique fait apparaˆıtre des structures conformes à

l’information présente dans l’image :

Mais en considérant seulement 1 échantillon sur 2, une structure différente apparaˆıt, dont l’ana-

lyse (ici des bandes verticales, plus épaisses) ne sera pas conforme à la réalité de l’objet :

Image originale

sous-échantillonnée

Image

1.1. QU’EST-CE QU’UNE IMAGE NUM ÉRIQUE ?

7

La quantification peut également faire apparaˆıtre des distortions dans les images. Comme pour

l’échantillonnage, il existe des règles pour déterminer la bonne quantification (le bon nombre

de bits) pour coder les images numériques. L’une dépend du capteur, et de sa capacité effective

à observer des signaux de valeurs différentes : le rapport signal sur bruit.

Le rapport signal sur bruit est défini à partir du rapport entre l’amplitude des niveaux de

nmin et le niveau du bruit, en gros l’écart-type σn de la

gris mesurables par le capteur nmax −

perturbation aléatoire qui affecte les niveaux de gris. En prenant le logarithme, on a le nombre

de bits utile au capteur pour coder les images.

Outre les capacités du capteur, le nombre de bits réellement nécessaires pour coder une

image varie d’une image à l’autre, en fonction de leur contenu informationnel. Ce nombre

dépend de l’entropie, définie à partir de la distribution des niveaux de gris de l’image (statis-

tique).

E =

−

N

!i

≤

pi log2(pi) ,

o ù N est le nombre de niveaux de gris présents, pi est la proportion (0 < pi < 1) de points de

l’image ayant pour niveau de gris i. Cette grandeur représente le nombre moyen de bits par

pixel nécessaires pour coder toute l’information présente. Elle est utilisée dans les techniques

de compression sans perte pour adapter le volume de donnée des images à leur contenu infor-

mationnel.

8

CHAPITRE 1. INTRODUCTION

Profil - Histogramme

Il est possible de tracer un trait sur le flanc du zèbre de l’image en niveaux de gris ci-dessous

et obtenir le profil correspondant, c’est à dire le niveau de gris de chaque point ou pixel traversé

par la ligne :

L’histogramme de l’image en niveau de gris ci-dessous permet d’établir une stricte corrélation

entre les données numériques codant la nuance de gris et la position des pixels de l’image.

1.2 Qu’est-ce que le traitement d’image ?

Les pages qui suivent sont extraites des cours en ligne [BMT, M].

1.2. QU’EST-CE QUE LE TRAITEMENT D’IMAGE ?

9

1.2.1 Quelques aspects du Traitement d’Image

– Filtrage / déconvolution (ou filtrage inverse)

– Compression

– Segmentation

– Restauration / reconnaissance

– Reconstruction tomographique

10

CHAPITRE 1. INTRODUCTION

1.2. QU’EST-CE QUE LE TRAITEMENT D’IMAGE ?

11

Dans ce cours nous évoquerons successivement trois aspects fondamentaux :

– Filtrage

L’outil mathématique essentiel pour le filtrage est la transformation de Fourier (ou toute

autre transformation du même type comme la transformation en ondelettes)

– Segmentation

La segmentation fait intervenir des notions d’optimisation, des outils géométriques et des

équations aux dérivées partielles

– Restauration

Les modèles variationnels en restauration utilisent de l’optimisation et de l’analyse fonc-

tionnelle fine (Banach, théorie de la mesure).

12

CHAPITRE 1. INTRODUCTION

1.2.2 Applications

– Robotique - Industrie

– Assemblage, reconnaissance de pièces

– Contr ôle de qualité

– Véhicule autonome

– etc ...

– Télédétection

– Météo

– Cartographie

– Analyse des ressources terrestres

– Astronomie

– Restauration

– etc...

– Applications militaires

– Guidage de missile

– Reconnaissance (aérienne, sous-marine, etc ...)

– etc ...

– Imagerie médicale

– Tomographie

– Aide au diagnostic

– Comptage (nombre de cellules)

– Suivi de formes anatomiques

1.2. QU’EST-CE QUE LE TRAITEMENT D’IMAGE ?

13

– Restauration

– etc...

– Sécurité

– Reconnaissance (d’empreintes, visages, signatures)

– Détection de mouvement

– etc...

14

CHAPITRE 1. INTRODUCTION

Chapitre 2

Traitement ponctuel des images

numériques

On s’intéresse d’abord aux traitements ponctuels qui consistent a faire subir a chaque pixel

une correction ne dépendant que de sa valeur. On trouve dans cette catégorie, les fonctions de

recadrage ou d’égalisation de dynamique, de binarisation ...

Sauf mention particulière, nous supposerons dans ce qui suit des images comportant N 2

pixels codés sur 256 niveaux de gris différents.

2.1 Correction ponctuelle d’une image -Recadrage de dynamique

Il s’agit d’une transformation du type f " = t(f ) qui permet de modifier la dynamique des

niveaux de gris dans le but d’améliorer l’aspect visuel de l’image. À un niveau de gris f de

l’image originale correspond le niveau t(f ) dans l’image transformée. On fait subir à chaque

pixel un traitement ne dépendant que de sa valeur. La transformation t(f ) peut être réalisée

en temps réel sur l’image en cours d’acquisition à l’aide d’une table de transcodage dans la-

quelle les valeurs de la transformation sont mémorisées. Un adressage de cette mémoire par

une donnée f fournit directement la valeur t(f ).

2.1.1 Transformation de recadrage

On suppose une image de départ présentant un histogramme concentré dans l’intervalle

[a, b]. Les valeurs a, b correspondent aux niveaux de gris extrêmes présents dans cette image. Le

recadrage de dynamique consiste a étendre la dynamique de l’image transformée a l’étendue

totale [0, 255]. La transformation de recadrage est donc une application affine qui s’écrit :

15

16

CHAPITRE 2. TRAITEMENT PONCTUEL DES IMAGES NUM ÉRIQUES

Original

Recadrage : a = 30, b = 200

Variantes pour le rehaussement des contrastes

Les types de correction donnés ci-dessous permettent d’accentuer le contraste dans une

plage précise de niveau.

Dilatation de la dynamique des zones sombres

Dilatation de la dynamique des zones claires

Fonction de rehaussement de contraste.

2.1. CORRECTION PONCTUELLE D’UNE IMAGE -RECADRAGE DE DYNAMIQUE

17

f

b

a

(255

−

t(f ) = 





pour 0

a)

−

pour a

f

f

≤

≤

≤

≤

a

255

b) f + 255(b

255

a

−

Original

Histogramme

Dilatation de la dynamique des zones claires

Dilatation de la dynamique des zones sombres

18

CHAPITRE 2. TRAITEMENT PONCTUEL DES IMAGES NUM ÉRIQUES

2.1.2

Égalisation de l’histogramme

L’histogramme d’une image est rarement plat ce qui traduit une entropie non maximale. La

transformation d’égalisation est construite de telle fac¸on que l’histogramme de l’image trans-

formée soit le plus plat possible. Cette technique améliore le contraste et permet d’augmenter

artificiellement la clarté d’une image grâce à une meilleure répartition des intensités relatives.

Fonction d’aplatissement continue

Considérons l’histogramme continu h(f ) donné ci-dessous. En notant f " = t(f ), l’histo-

gramme égalisé h(f ") doit s’approcher de la forme idéale décrite ci-dessous.

Deux surfaces élémentaires en correspondance dans les histogrammes initiaux et égalisés,

présentent le même nombre de points ce qui permet d’écrire :

f " = t(f ) =

256

N 2

f

0

&

h(s) ds .

Histogramme d’origine

Histogramme plat idéal

Fonction idéale d’égalisation d’un histogramme

Fonction d’aplatissement discrète

En remplac¸ant l’intégration continue par une somme, on obtient la transformation d’égalisation

discrète suivante :

f " = t(f ) =

256

N 2

f

!i=0

h(i) .

2.1. CORRECTION PONCTUELLE D’UNE IMAGE -RECADRAGE DE DYNAMIQUE

19

Original

Histogramme

Image égalisée

Publicité

Histogramme égalisé

2.1.3 Binarisation

Le but de la binarisation d’une image est d’affecter un niveau uniforme au pixels pertinents

et d’éliminer les autres.

Seuillage

Le seuillage consiste a affecter le niveau 255 aux pixels dont la valeur est supérieure a un

seuil S et 0 le niveau aux autres. Le graphe de la transformation correspondante est le suivant

Fonction « seuillage »

20

CHAPITRE 2. TRAITEMENT PONCTUEL DES IMAGES NUM ÉRIQUES

Seuillage à 70

Extraction d’une fenêtre d’intensité

Avec la transformation décrite ci-dessous, la nouvelle image ne visualise que les pixels dont

le e niveau d’intensité appartient à l’intervalle [a, b]. Sous réserve d’une connaissance a priori

de la distribution des niveaux de gris des objets de l’image originale, cette technique permet

une segmentation d’objets particuliers de l’image.

Fonction « fenêtre d’intensité »

Original

Histogramme

2.2. ANAYSE DE LA NETTET É D’UNE IMAGE NUM ÉRIQUE

21

Seuillage avec fenêtre d’intensité entre 30 et 100

2.2 Anayse de la netteté d’une image numérique

La focalisation automatique, ou mise au point, des systèmes de prise de vue traditionnels

(appareils photo,, graphiques caméras analogiques ... ) exploite généralement un télémètre qui

mesure avec précision la distance appareil-plan objet. Les systèmes de vision numériques ac-

tuels (appareils et caméras numériques ... ) réalisent automatiquement leur mise au point à par-

tir d’une analyse de l’image restituée. Pour cela un critère de netteté de l’image est déterminé

à partir des valeurs f (i, .j) := fij de l’intensité (luminance) des pixels.

Un grand nombre de criteres a été proposé. Parmi les plus utilisés figurent les criteres basés

sur l’analyse de la distribution des niveaux d’intensité pixel et ceux mesurant le contenu spec-

tral de l’image.

La première catégorie repose sur le fait que la défocalisation engendre l’uniformisation des

niveaux de gris, ou ce qui revient au même, que l’image nette présente l’histogramme le plus

large.

La seconde catégorie repose sur le principe similaire qu’une image focalisée contient plus

de fréquences spatiales élevées qu’une image floue.

Dans toutes ces méthodes, on recherche la distance de mise au point qui assure la majora-

tion du critère

2.2.1 Exemples de critères de netteté

Critères de netteté basés sur l’analyse de l’histogramme de l’image

On note hk la distribution statistique (histogramme) des niveaux k d’intensité des pixels.

22

CHAPITRE 2. TRAITEMENT PONCTUEL DES IMAGES NUM ÉRIQUES

Critère mathématique

Méthode de

Mendelsohn

et Mayall

F =

k hk

!k>T

T est un paramètre choisi

proche du niveau de gris moyen de l’image

Méthode de

F =

Mason et Green ∆ij = 2

i

(k

T ) hk et T =

−

!k>T

(fi,j+1 −

1 −

fi,j

−

fi+1,j+1)2 + (fi

−

’

’

i

1)2 + (fi+1,j −

’

’

1,j+1 −

(

−

j fij∆ij

j ∆ij

fi

−

fi+1,j

1,j)2

1)2

)

−

+ (fi

−

1,j

Variance des

niveaux de gris

F =

j f 2

ij

i

N 2

’

’

2

j fij

N 4

’

)

i

− (’

Critères de netteté basés sur l’analyse spectrale de l’image

Critère mathématique

Norme "1 du gradient1

F =

fi,j −

(

|

fi,j

1|

−

+

fi,j+1 −

|

)

fi,j|

!i,j

Norme "2 du gradient

F =

(fi+1,j −

fi,j)2 + (fi,j+1 −

fi,j)2

!i,j

Remarques générales

– Les tests des critères de netteté réalisés sur un grand nombre d’images différentes montrent

que leurs performances dépendent du type et du contenu de l’image analysée ;

– En regle générale, l’extremum des criteres est peu prononcé lorsque l’image contient peu

de détails

2.3. CORR ÉLATION D’IMAGES NUM ÉRIQUES

23

– L’algorithme de Brenner est souvent utilisé car il présente généralement une bonne sen-

sibilité et la charge de calculs qu’il nécessite est raisonnable.

2.3 Corrélation d’images numériques

Nous considérons deux fonctions bidimensionnelles discrètes f (i, j) et g(i, j) avec 1

i, j

≤

≤

N.

Ces fonctions sont représentatives de deux images numériques monochromes comportant

N 2 pixels. Leurs versions centrées et réduites sont définies respectivement par

fc(i, j) =

µf

f (i, j)

σf

−

et gc(i, j) =

µg

g(i, j)

σg

−

o ù µ et σ sont respectivement la moyenne et l’écart type de chaque fonction.

La fonction d’intercorrélation entre fc et gc est définie par la relation :

ϕf g(k, l) =

1

N 2

!i,j

fc(i, j)gc(i

k, j

l) .

−

−

(2.3.1)

Il est souvent plus pratique de travailler sur des images dont les valeurs sont centrées et

réduites. Ceci permet d’une part d’éliminer de ϕf g(k, l) le carré des moyennes des images,

d’autre part de normaliser les fonctions de corrélation.

Pour éviter les effets de bord qui introduisent un biais dans le calcul de ϕf g(k, l) il convient :

– soit de s’assurer que la double sommation est réalisée sur des valeurs dont les coor-

données ne sortentjainais de l’image. Cela revient à définir un cadre d’intégration dont

le format, inférieur à celui de l’image, est choisi en fonction du domaine de calcul de

ϕf g(k, l) ;

– soit de remplacer dans l’expression (2.3.1) le diviseur N 2 par la valeur variable M qui

dépend de k et l selon la relation : M = (N

k

)(N

|

−|

l

).

|

−|

2.3.1 Application à la reconnaissance d’empreintes digitales

Les fonctions d’intercorrélation bidimensionnelles peuvent être utilisées en reconnaissance

d’images. La comparaison de l’empreinte digitale d’un suspect avec celles contenues dans un

fichier en est un exemple. les deux images représentées ci-dessous représentent les empreintes

digitales de deux individus que nous appellerons F et G.

24

CHAPITRE 2. TRAITEMENT PONCTUEL DES IMAGES NUM ÉRIQUES

Les caractéristiques générales de ces deux images sont données dans le tableau suivant :

Format

Codage en niveaux de gris

Moyenne µ

Écart type σ

Individu F

256 x 256

0 à 255

132,8

33,8

Individu G

256 x 256

0 à 255

127

36,4

Les valeurs des deux images sont centrées et réduites. Pour éviter les effets de bords, l’in-

tercorrélation est réalisée entre deux zones carrées de 151 x 151 pixels (voir figure ci-dessous)

La fonction est estimée dans la gamme

20

−

≤

k, l

≤

20 grâce à la formule suivante

ϕf g(k, l) =

1

1512

200

!i,j=50

fc(i, j)gc(i

k, j

l) .

−

−

(2.3.2)

La représentation 3D à gauche dans la figure ci-dessous est celle de la fonction d’autocorrélation

ϕf g(k, l) effectuée sur l’empreinte F . Son maximum estégal à 1 au centre du graphique qui cor-

respond ici à la position k = l = 0. La représentation de droite est la fonction d’intercorrélation

entre les empreintes F et G.

2.3. CORR ÉLATION D’IMAGES NUM ÉRIQUES

25

Ses valeurs ne dépassent pas 0.15 ce qui prouve que les deux empreintes ne sont pas iden-

tiques.

Dans la réalité, les empreintes ne sont pas toutes obtenues dans les mêmes conditions de

positionnement. Il est nécessaire d’ajouter un parametre de rotation d’image a la fonction d’in-

tercorrélation ce qui peut alourdir considérablement les calculs.

2.3.2 Application à l’analyse de la texture d’une image

Par définition la texture d’une image est la structure spatiale sur laquelle sont organisés les

pixels. Les relations structurelles peuvent être :

– déterministes : c’est le cas de la répétition quasi périodique d’un motif de base (brique,

carrelage, mailles de tissu ... ) ;

– aléatoires : il n’y a pas de motif de base (sable, mur crépi...)

La fonction d’autocorrélation bidimensionnelle est bien adaptée pour mettre en évidence les

propriétés de la texture d’une image. La figure suivante représente deux exemples de texture.

Nous donnons ci-dessous la fonction d’auto-corrélation des textures « sable » et « tissu ».

26

CHAPITRE 2. TRAITEMENT PONCTUEL DES IMAGES NUM ÉRIQUES

2.4 Transformation de Hough

[,a transformation de Hough est utilisée pour détecter de manière systématique la présence

de relations structurelles spécifiques entre des pixels dans une image Par exemple une image

représentant un site urbain est composée de nombreuses lignes droites (immeubles, fenêtres)

en revanche, une vue de campagne en est quasiment dépourvue .

Publicité

Hough propose une méthode de détection basée sur une transformation d’image permet-

tant la reconnaissance de structures simples (droite, cercle, ... ) liant des pixels entre eux. Pour

limiter la charge de calcul, l’image originale est préalablement limitée aux contours des objets

puis binarisée (2 niveaux possibles pour coder l’intensité pixel).

2.4.1 Principe de la méthode pour la recherche de ligne droite

Supposons que l’on suspecte la présence d’une droite ∆ reliant un certain nombre de pixesl

Pi. Soit le pixel P1 de coordonnées (x1, y1). Une infinité de droites d’équation : y1 = ax1 + b

peuvent passer par P1. Cependant, dans le plan des paramètres ab l’équation qui s’écrit b =

ax1 + y1 devient une droite unique D1 (voir figures ci-dessous).

−

Un second pixel P2 = (x2, y2) permet de définir une seconde droite D2 du type b =

ax2+y2

dans le plan ab.L’intersection de D2 avec D1 fournit le couple "a", b") qui sont les paramètres

−

2.4. TRANSFORMATION DE HOUGH

27

de la droite recherchée ∆ dans le plan image. Ainsi, tous les pixels Pi qui sont alignés sur ∆

possède une droite Di dnas le plan ab qui coupe les autres au point particulier (a", b").

2.4.2 Problème pour la recherche de ligne verticale Représentation normale d’une

droite

Dans le plan image, une droite verticale possede des parametres a etb infinis, ce qui ne

permet pas d’exploiter la méthode précédente. Pour contourner ce problème, on utilise la

représentation normale des droites. Cette représentation, de parametres ρ et θ, obéit a l’équation

Cette équation représente le produit scalaire (projection) entre les vecteurs &V =

x cos θ + y sin θ = ρ.

(2.4.3)

cos θ

sin θ

et

+

*

x

y

*

+

−−→OM =

. Ainsi l’ensemble des points M d’une droite se projettent sur un même vecteur

particulier de coordonnées polaires (ρ, θ) . Les cas de droites horizontales et verticales sont

illustrés ci-dessous :

2.4.3 Transformation de Hough pour la détection de droites dans une image binaire

Domaine de variation des paramètres θ et ρ

Il est a noter que si (ρ, θ) sont les parametres d’une droite (

ρ, θ + π) le sont également. Par

conséquent l’intervalle [0,π [correspond au domaine de variation complet du paramètre θ. Les

coordonnées cartésiennes x et y des pixels d’une image numérique sont généralement positives,

l’origine étant placée à un sommet de l’image. En considérant une image carrée comportant

N pixels, les valeurs de ρ calculées par l’équation (2.4.3) peuvent être majorées par √2N .

N

−

×

Quadrillage du plan θρ

On suspecte dans l’image la présence d’une ou plusieurs structures caractérisées par l’ali-

gnement d’un certain nombre de pixels. Soit les deux intervalles [θmin,θ max] dans lesquels on

cherche a calculer les parametres de la représentation normale d’une ou plusieurs droites.

28

CHAPITRE 2. TRAITEMENT PONCTUEL DES IMAGES NUM ÉRIQUES

Le plan θρ limité aux intervalles de recherche, est subdivisé en cellules par quantification

des paramètres θ et ρ avec les pas respectifs ∆θ et ∆ρ (indexation par les indices p et q). La

figure ci-dessous donne un exemple de quadrillage du plan θρ. Un tableau A(p, q) dont les

valeurs sont initialement mises a zéro, est associé a ce quadrillage

Procédure de transformation

– Pour chaque pixel non nul Pi(xi, yi) de l’image, on balaye l’axe des θ de θmin à θmax

suivant la trame du tableau et pour chaque θp on résout l’équation (2.4.3) ;

– le résultat ρ obtenu est arrondi à la valeur ρq du tableau la plus proche ;

– si à la valeur θp correspond la solution ρq la valeur A(p, q) est incrémentée d’une unité.

À la fin de cette procédure, A(p, q) = M signifie que M points de l’image sont alignés sur

la droite de parametres approximatifs (θp,ρ q). Apres transformation complète, le tableau peut

être représenté sous la forme d’une image en niveaux de gris (exemple plus loin) ou celle d’un

graphique 3D. La décision sur la détection de droites peut être prise après recherche des coor-

données des valeurs significatives du tableau.

La charge de calcul nécessaire pour réaliser la transformation de Hough est importante. Elle

dépend du nombre de paramètres recherchés :

  • recherche de droites : 2 paramètres ;
  • recherche de cercles : 3 paramètres.

Exemple pour la recherche de droite : pour N pixels non nuls de l’image binaire et K sub-

divisions de l’axe θ. il y a N K déterminations de l’équation (2.4.3). Une réduction du temps

de calcul peut être obtenue par l’utilisation de tables préenregistrées des conversions sin θp et

cos θp

Exemple

Nous considérons dans cet exemple une image binaire comportant 6 x 6 pixels dont les

valeurs sont données dans le tableau suivant

2.4. TRANSFORMATION DE HOUGH

29

Deux droites ∆1 et ∆2 comportant chacune 6 pixels alignés apparaissent clans cette image.

La procédure de calcul décrite au paragraphe précédent est utilisée avec les paramètres sui-

vants : θp varie de 0 à 180o par pas de 1o.

Plus généralement si on considère une image de taille N1×

1)2 + (N2 −

1)2. Si on discrétise l’espace de Hough avec une résolution de

et ρmax =

hθ (par exemple 1o) pour θ et une résolution de hρ pour ρ le tableau de référence est donné par

1)2 + (N2 −

N2, ρmin =

(N1 −

(N1 −

,

−

,

1)2

θp =

90 + phθ avec p

−

0, Nθ}

et

∈{

−

90 + Nθhθ = 90 ,

ρq = ρmin + qhρ avec q

0, Nρ}

∈{

et ρmin + Nρhρ = ρmax.

Le programme itératif suivant permet le calcul de la transformation de Hough :

Mi,j sont les valeurs binaires de l’image originale : Mi,j ∈{

Pour p de 1 à Nθ

0, 1

}

Pour q de 1 à Nρ

Ap,q = 0

Pour i de 1 à N1

Pour j de 1 à N2

Pour p de 1 à Nθ

p

q = Arrondi

i cos

180

= 0

Ap,q = Ap,q + 1 si Mi,j ’

.

-

1

hρ

(

π

+ j sin

/

.

p

180

π

−

/)

ρmin

0

30

CHAPITRE 2. TRAITEMENT PONCTUEL DES IMAGES NUM ÉRIQUES

Le même type de programme appliqué à l’image binaire (64

64) donne le résultat ci-dessous :

×

Chapitre 3

Filtrage

3.1 Filtrage linéaire des signaux 1D

L’exemple le plus courant de signal 1D est le signal sonore.

Définition 3.1.1 (Filtre) Un filtre est un système linéaire continu et invariant. En d’autres termes,

ainsi qu’un opérateur linéaire continu, invariant par translation

on se donne deux espaces normés

et

:

A

.

X → Y

X

Y

Supposons qu’ on puisse définir la transformée de Fourier des signaux d’entrée f et de

sortie g (par exemple si ces fonctions sont dans L1(R) ou dans L2(R) et que le signal de sortie

le filtrage de f par un filtre linéaire est tel que

ˆg = H ˆf

o ù ˆg désigne la transformée de Fourier de g. La fonction H est appelée fonction de transfert

du filtre. Si la fonction de transfert H est dans L2(R)

L∞(R), elle admet une transformée de

1H, bornée et a décroissance rapide, continue (sauf peut-être a l’origine)

Fourier inverse h =

et la relation

F −

∩

entraˆıne

ˆg = ˆh ˆf

g = h

f .

∗

La réponse à l’entrée f est donc un produit de convolution de l’entrée avec une fonction fixe

h que l’on appelle réponse impulsionnelle.

Définition 3.1.2 On appelle réponse indicielle d’un filtre sa réponse à l’échelon unité (fonction de

Heaviside) :

t

h1(t) =

h(s) ds .

&

−∞

31

32

CHAPITRE 3. FILTRAGE

Notons que la plupart des filtres courants sont des filtres de convolution. Il est courant de

définir un filtre par la fac¸on dont il modifie les fréquences du signal d’entrée, c’est-à-dire par

sa fonction de transfert H(λ) puisque les fréquences de l’entrée f et de la sortie g sont liées par

ˆg(λ) = H(λ) ˆf (λ) .

Un filtre idéal est un filtre qui élimine totalement les bandes de fréquence indésirables sans

transition et sans déphasage dans les bandes conservées.

Selon la bande rejetée, on rencontre 4 grandes catégories de filtres.

La région o ù les fréquences sont coupées est en gris ci-dessus. Par exemple le passe-bas idéal

est le filtre qui ne modifie par les fréquences λ telles que λ

λc (fréquence de coupure) et

supprime les autres. D’o ù

≤

H(λ) =

1 si

|≤

0 sinon

λ

|

λc

1

L2(R) telle que ˆh = H. C’est

On reconnaˆıt h

∈

h(t) =

sin 2πλct

πt

.

Si on se limite à des signaux d’entrée d’énergie finie, f, h et H sont dans L2(R) et g = h

sait que g est continue, bornée et nulle à l’infini. h

f est dans L2(R) comme ˆf .

f . On

∗

Toutefois un tel filtre n’est pas réalisable. On se contente de filtres passe-bas approchés

(voir ci-dessous un dispositif physique de réalisation d’un tel filtre) qui atténuent les hautes

fréquences au lieu de les supprimer (voir exercices) et qui entraˆınent un déphasage :

∗

3.2. FILTRAGE 2D : CONVOLUTION /M ÉDIAN

33

3.2 Filtrage 2D : convolution /médian

Le célèbre format bitmap, qui tire son nom de l’anglais « bitmap » pour « carte de bits »

montre qu’une image est avant tout un domaine spatial sur lequel on peut se promener avec

la souris de l’ordinateur : les distances en pixels dans l’image I sont dès lors liées aux distances

réelles en metres dans la scene réelle S.

La fréquence spatiale est un concept délicat qui découle du fait que les images appar-

tiennent au domaine spatial. Pour commencer on peut rappeler que la fréquence est une gran-

deur qui caractérise le nombre de phénomènes qui se déroulent au cours d’un temps donné :

en voiture le long d’une route vous voyez 2 bandes blanches PAR seconde : c’est une fréquence

temporelle. Il est ensuite facile de comprendre que ce concept de fréquence « temporelle » peut

aussi se traduire en disant qu’il y a 200 bandes blanches PAR kilomètre : c’est une fréquence

spatiale.

Dans une image, les détails se répètent fréquemment sur un petit nombre de pixels, on dit

qu’ils ont une fréquence élevée : c’est le cas pour les bords et les contours dans une image.

Au contraire, les fréquences basses correspondent a des variations qui se répetent peu car,

diluées sur de grandes parties de l’image, par exemple des variations de fond de ciel.

Nous verrons dans la suite que la plupart des filtres agissent sélectivement sur ces fréquences

pour les sélectionner, en vue de les amplifier ou de les réduire.

34

CHAPITRE 3. FILTRAGE

3.2.1 Filtrage spatial

Filtres de convolution

Le filtrage spatial est essentiellement une opération de convolution (2D). Si f est l’image à

filtrer (ou à rehausser) et g le filtre spatial (ou PSF ou masque) on a :

Publicité

f (x, y)

∗

g(x, y) =

1

−

F

F



(f (x, y))

· F

(g(x, y))

}



G(u,v)

.

G est la fonction de transfert du filtre. On peut distinguer trois types de filtrage :

2

34

5





Une image numérique étant essentiellement discrète (pixels et niveaux de gris) nous allons

présenter les filtres dans le cas discret. Dans tout ce qui suit x et y sont des entiers (coordonnées

des pixels) et f est a valeurs entieres (dans

, 255

).

0,

{

· · ·

}

3.2. FILTRAGE 2D : CONVOLUTION /M ÉDIAN

35

On ne fait pas en général une convolution globale mais une transformation basée sur le

voisinage d’un point (x, y) :

Le noyau de convolution du filtre κ est à support compact inclus dans [x1, x2]

[y1, y2] :

×

g(x, y) = (f

κ)(x, y) =

∗

x2

y2

!i=x1

!j=y1

f (x

i, y

−

−

j)κ(i, j) .

Généralement le filtre est de dimension d impaire et est symétrique. Dans ce cas

[x1, x2] = [y1, y2] = [

d/2, d/2] ,

−

κ)(x, y) =

(f

∗

1)/2

(d

−

1)/2

(d

−

(d

!i=

−

−

1)/2

(d

!j=

−

−

1)/2

f (x + i, y + j)κ(i, j) .

(3.2.1)

Filtre(i,j)

w2

w5

w8

↑

x

w3 ←

w6 ←

w9 ←

↑

x + 1

w1

w4

w7

x

↑

−

1

1

−

y

y

y + 1

Ici d = 3. On ne filtre pas les bords pour éviter des distorsions ; donc κ(0, 0) = w5.

Sur cet exemple on a précisément

g(x, y) = w1f (x

1, y

1) + w2f (x, y

1) + w3f (x + 1, y

1)

−

−

+w4f (x

+w7f (x

−

−

1, y) + w5f (x, y) + w6f (x + 1, y)

1, y + 1) + w8f (x, y + 1) + w9f (x + 1, y + 1) .

−

−

Afin de conserver la moyenne de l’image f , la somme des éléments du filtre est normalisée à

1 :

wi = 1.

!i

36

CHAPITRE 3. FILTRAGE

Un filtre 2D est dit séparable s’il est possible de décomposer le noyau de convolution h2D en

deux filtres 1D appliqués successivement en horizontal puis en vertical (ou inversement) :

h2D = hV

1D ⊗

hH

1D ,

⊗

désigne le produit de convolution. On peut alors traiter séparément les lignes

o ù le symbole

et les colonnes de l’image.

Pour qu’un filtre 2D soit séparable il faut et il suffit que les coefficients de ses lignes et de ses

colonnes soient proportionnels.

Exemple 3.2.1 (Filtres séparables )

a b

c

⊗

α

β

γ

=

aα bα cα

aβ bβ cβ

cγ

bγ

aγ

Exemple 3.2.2 (Filtre de moyenne passe -bas )

1

9 ·

1 1 1

1 1 1

1 1 1

1

25 ·

1 1 1 1 1

1 1 1 1 1

1 1 1 1 1

1 1 1 1 1

1 1 1 1 1

Filtre 3 x 3

Filtre 5 x 5

Ce sont des filtres séparables.

3.2. FILTRAGE 2D : CONVOLUTION /M ÉDIAN

37

Exemple 3.2.3 (Filtre gaussien)

1

16 ·

1 2 1

2 4 2

1 2 1

(6σ +1). En général un filtre gaussien

Idéalement, on devrait prévoir un filtre de taille (6σ +1)

avec σ< 1 est utilisé pour réduire le bruit, et si σ> 1 c’est dans le but de fabriquer une image

qu’on va utiliser pour faire un « masque flou » personnalisé. Il faut noter que plus σ est grand,

plus le flou appliqué à l’image sera marqué.

×

Exemple 3.2.4 (Filtre bin ômial)

Les coefficients de ce filtre sont obtenus par le binôme de Newton. Un filtre 1D binômial d’ordre 4

(1 4 6 4 1). Un filtre 2D binômial d’ordre 4 est donné

est un filtre séparable donné par le vecteur v =

par v"v :

1

16

1

256 ·

4

4

1

1

6

4 16 24 16 4

6 24 36 24 6

4 16 24 16 4

1

6

1

4

4

Filtres médians

Ce ne sont pas des filtres de convolution, ni des filtres linéaires.

g(x, y) = médian

{

f (n, m)

|

(n, m)

∈

S(x, y)

,

}

o ù S(x, y) est un voisinage de (x, y).

38

Exemple :

CHAPITRE 3. FILTRAGE

20

10

30

10 250 25

30

25

20

→

10 10 20 20

25

25 30 30

↑

médiane

bruit

↓

250

On remplace la valeur du pixel par la valeur médiane ou la valeur moyenne. Ce filtre est utile

pour contrer l’effet « Poivre et Sel » (P& S) c’est-à-dire des faux « 0 » et « 255 » dans l’image.

Image bruitée « Poivre et Sel »

3.2. FILTRAGE 2D : CONVOLUTION /M ÉDIAN

39

Filtre de moyenne : rayon 3

Filtre de moyenne : rayon 5

Filtre de moyenne : rayon 7

Filtre médian : rayon 3

Filtre médian : rayon 5

40

CHAPITRE 3. FILTRAGE

Si le bruit P& S est supérieur à la moitié de la dimension du filtre, le filtrage est inefficace.

Filtre médian : rayon 7

Filtres passe-haut

L’image obtenue par un filtre passe-haut correspond en général a ce qui « reste » apres un

filtrage passe-bas.

3.2. FILTRAGE 2D : CONVOLUTION /M ÉDIAN

41

3.2.2 Filtrage fréquentiel

Transformation de Fourier 2D

Avant d’envisager le...