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