UniversityLibHub Documents

méthodes mathématiques pour le traitement d’image

1/1
100%

Quelques m ́ethodes math ́ematiques pour le traitement d’image 2 janvier 2009 Ce cours est une introduction `a la th ́eorie math ́ematique de traitement de l’image . Il est donc incomplet car les m ́ethodes dans ce domaine sont nombreuses et vari ́ees. On se polarisera sur les m ́ethodes variationnelles. Bergounioux Master 2 - 2008-2009 2 Chapitre 1 Introduction 1.1 Qu’est-ce qu’une image num ́erique ? Une image num ́erique est compos ́ee d’unit ́es ́el ́ementaires (appel ́ees pixels) qui repr ́esentent chacun une portion de l’image. Une image est d ́efinie par : – le nombre de pixels qui la compose en largeur et en hauteur (qui peut varier presque `a l’infini), – l’ ́etendue des teintes de gris ou des couleurs que peut prendre chaque pixel (on parle de dynamique de l’image). 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 ́e d’une seule couleur. 2. Les images en teintes de gris En g ́en ́eral, les images en niveaux de gris renferment 256 teintes de gris. Image `a 256 couleurs, simplement chacune de ces 256 couleurs est d ́efinie dans la gamme des gris. Par convention la valeur z ́ero repr ́esente le noir (intensit ́e lumineuse nulle) et la valeur 255 le blanc (intensit ́e lumineuse maximale). 3. Les images couleurs S’il existe plusieurs modes de repr ́esentation de la couleur, le plus utilis ́e pour le manie- ment des images num ́eriques est l’espace couleur Rouge, Vert, Bleu (R,V,B). Cet espace couleur est bas ́e sur la synth`ese additive des couleurs, c’est `a dire que le m ́elange des trois composantes (R, V, B) donne une couleur. 3 4 CHAPITRE 1. INTRODUCTION 1.1.1 Quelques d ́efinitions Pixels et niveaux de gris Echantillonnage et quantification 1.1. QU’EST-CE QU’UNE IMAGE NUM ́ ERIQUE ? 5 L’ ́echantillonnage est le proc ́ed ́e de discr ́etisation spatiale d’une image consistant `a asso- cier `a chaque zone rectangulaire R ( x, y ) d’une image continue une unique valeur I ( x, y ). On parle de sous- ́echantillonnage lorsque l’image est d ́ej`a discr ́etis ́ee et qu’on diminue le nombre d’ ́echantillons. Une image num ́erique est une image ́echantillonn ́ee et quantifi ́ee. La quantification d ́esigne la limitation du nombre de valeurs diff ́erentes que peut prendre I ( x, y ) . L’ ́echantillonnage est une ́etape fondamentale qui doit tenir compte du contenu informa- tionnel pertinent de l’image `a analyser. Sur l’exemple ci- dessous, en 1d, le signal ́echantillonn ́e « ressemble » `a une sinusoıde de fr ́equence 8 fois plus faible : 6 CHAPITRE 1. INTRODUCTION Ce ph ́enom`ene appel ́e aliasing est encore pire en 2D, car il affecte la fr ́equence et la direction des structures p ́eriodiques. Imaginons par exemple qu’on souhaite ́echantillonner l’image cor- respondant aux bandes noires ci-dessous : Avec un ́echantillonnage adapt ́e, l’image num ́erique fait apparaıtre des structures conformes `a l’information pr ́esente dans l’image : Mais en consid ́erant seulement 1 ́echantillon sur 2, une structure diff ́erente apparaıt, dont l’ana- lyse (ici des bandes verticales, plus ́epaisses) ne sera pas conforme `a la r ́ealit ́e de l’objet : Image originale Image sous- ́echantillonn ́ee 1.1. QU’EST-CE QU’UNE IMAGE NUMERIQUE ́ ? 7 La quantification peut ́egalement faire apparaıtre des distortions dans les images. Comme pour l’ ́echantillonnage, il existe des r`egles pour d ́eterminer la bonne quantification (le bon nombre de bits) pour coder les images num ́eriques. L’une d ́epend du capteur , et de sa capacit ́e effective `a observer des signaux de valeurs diff ́erentes : le rapport signal sur bruit . Le rapport signal sur bruit est d ́efini `a partir du rapport entre l’amplitude des niveaux de gris mesurables par le capteur n max − n min et le niveau du bruit, en gros l’ ́ecart-type σ n de la perturbation al ́eatoire 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 ́es du capteur, le nombre de bits r ́eellement n ́ecessaires pour coder une image varie d’une image `a l’autre, en fonction de leur contenu informationnel. Ce nombre d ́epend de l’entropie , d ́efinie `a partir de la distribution des niveaux de gris de l’image (statis- tique). E = − ∑ i≤N p i log 2 ( p i ) , o`u N est le nombre de niveaux de gris pr ́esents, p i est la proportion (0 < p i < 1) de points de l’image ayant pour niveau de gris i . Cette grandeur repr ́esente le nombre moyen de bits par pixel n ́ecessaires pour coder toute l’information pr ́esente. Elle est utilis ́ee dans les techniques de compression sans perte pour adapter le volume de donn ́ee des images `a leur contenu infor- mationnel. 8 CHAPITRE 1. INTRODUCTION Profil - Histogramme Il est possible de tracer un trait sur le flanc du z`ebre de l’image en niveaux de gris ci-dessous et obtenir le profil correspondant, c’est `a dire le niveau de gris de chaque point ou pixel travers ́e par la ligne : L’histogramme de l’image en niveau de gris ci-dessous permet d’ ́etablir une stricte corr ́elation entre les donn ́ees num ́eriques 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 ́econvolution (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 ́evoquerons successivement trois aspects fondamentaux : – Filtrage L’outil math ́ematique essentiel pour le filtrage est la transformation de Fourier (ou toute autre transformation du mˆeme type comme la transformation en ondelettes) – Segmentation La segmentation fait intervenir des notions d’optimisation, des outils g ́eom ́etriques et des ́equations aux d ́eriv ́ees partielles – Restauration Les mod`eles variationnels en restauration utilisent de l’optimisation et de l’analyse fonc- tionnelle fine (Banach, th ́eorie de la mesure). 12 CHAPITRE 1. INTRODUCTION 1.2.2 Applications – Robotique - Industrie – Assemblage, reconnaissance de pi`eces – Contrˆole de qualit ́e – V ́ehicule autonome – etc ... – T ́el ́ed ́etection – M ́et ́eo – Cartographie – Analyse des ressources terrestres – Astronomie – Restauration – etc... – Applications militaires – Guidage de missile – Reconnaissance (a ́erienne, sous-marine, etc ...) – etc ... – Imagerie m ́edicale – 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 ́ecurit ́e – Reconnaissance (d’empreintes, visages, signatures) – D ́etection de mouvement – etc... 14 CHAPITRE 1. INTRODUCTION Chapitre 2 Traitement ponctuel des images num ́eriques On s’int ́eresse d’abord aux traitements ponctuels qui consistent `a faire subir `a chaque pixel une correction ne d ́ependant que de sa valeur. On trouve dans cette cat ́egorie, les fonctions de recadrage ou d’ ́egalisation de dynamique, de binarisation ... Sauf mention particuli`ere, nous supposerons dans ce qui suit des images comportant N 2 pixels cod ́es sur 256 niveaux de gris diff ́erents. 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 ́eliorer l’aspect visuel de l’image. ` A un niveau de gris f de l’image originale correspond le niveau t ( f ) dans l’image transform ́ee. On fait subir `a chaque pixel un traitement ne d ́ependant que de sa valeur. La transformation t ( f ) peut ˆetre r ́ealis ́ee en temps r ́eel sur l’image en cours d’acquisition `a l’aide d’une table de transcodage dans la- quelle les valeurs de la transformation sont m ́emoris ́ees. Un adressage de cette m ́emoire par une donn ́ee f fournit directement la valeur t ( f ). 2.1.1 Transformation de recadrage On suppose une image de d ́epart pr ́esentant un histogramme concentr ́e dans l’intervalle [ a, b ]. Les valeurs a, b correspondent aux niveaux de gris extrˆemes pr ́esents dans cette image. Le recadrage de dynamique consiste `a ́etendre la dynamique de l’image transform ́ee `a l’ ́etendue totale [0 , 255]. La transformation de recadrage est donc une application affine qui s’ ́ecrit : 15 16 CHAPITRE 2. TRAITEMENT PONCTUEL DES IMAGES NUM ́ ERIQUES Original Recadrage : a = 30 , b = 200 Variantes pour le rehaussement des contrastes Les types de correction donn ́es ci-dessous permettent d’accentuer le contraste dans une plage pr ́ecise 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 t ( f ) =   a bf pour 0 ≤ f ≤ a (255 − b ) f + 255( b 255 − a − a ) pour a ≤ f ≤ 255 Dilatation de la dynamique des zones sombres Dilatation de la dynamique des zones claires Original Histogramme 18 CHAPITRE 2. TRAITEMENT PONCTUEL DES IMAGES NUMERIQUES ́ 2.1.2 Egalisation ́ de l’histogramme L’histogramme d’une image est rarement plat ce qui traduit une entropie non maximale. La transformation d’ ́egalisation est construite de telle fac ̧on que l’histogramme de l’image trans- form ́ee soit le plus plat possible. Cette technique am ́eliore le contraste et permet d’augmenter artificiellement la clart ́e d’une image grˆace `a une meilleure r ́epartition des intensit ́es relatives. Fonction d’aplatissement continue Consid ́erons l’histogramme continu h ( f ) donn ́e ci-dessous. En notant f = t ( f ), l’histo- gramme ́egalis ́e h ( f ) doit s’approcher de la forme id ́eale d ́ecrite ci-dessous. Deux surfaces ́el ́ementaires en correspondance dans les histogrammes initiaux et ́egalis ́es, pr ́esentent le mˆeme nombre de points ce qui permet d’ ́ecrire : f = t ( f ) = 256 N 2 ∫ f 0 h ( s ) ds . Histogramme d’origine Histogramme plat id ́eal Fonction id ́eale d’ ́egalisation d’un histogramme Fonction d’aplatissement discr`ete En remplac ̧ant l’int ́egration continue par une somme, on obtient la transformation d’ ́egalisation discr`ete suivante : f = t ( f ) = 256 N 2 ∑ f i =0 h ( i ) . h ( i ) . 2.1. CORRECTION PONCTUELLE D’UNE IMAGE -RECADRAGE DE DYNAMIQUE 19 Image ́egalis ́ee Histogramme ́egalis ́e 2.1.3 Binarisation Le but de la binarisation d’une image est d’affecter un niveau uniforme au pixels pertinents et d’ ́eliminer les autres. Seuillage Le seuillage consiste `a affecter le niveau 255 aux pixels dont la valeur est sup ́erieure `a un seuil S et 0 le niveau aux autres. Le graphe de la transformation correspondante est le suivant Original Histogramme Fonction « seuillage » 20 CHAPITRE 2. TRAITEMENT PONCTUEL DES IMAGES NUM ́ ERIQUES Seuillage `a 70 Extraction d’une fenêtre d’intensité Avec la transformation d ́ecrite ci-dessous, la nouvelle image ne visualise que les pixels dont le e niveau d’intensit ́e appartient `a l’intervalle [ a, b ]. Sous r ́eserve 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. Original Histogramme Fonction « fenˆetre d’intensit ́e » 2.2. ANAYSE DE LA NETTET ́ E D’UNE IMAGE NUM ́ ERIQUE 21 Seuillage avec fenˆetre d’intensit ́e entre 30 et 100 2.2 Anayse de la nettet ́e d’une image num ́erique La focalisation automatique, ou mise au point, des syst`emes de prise de vue traditionnels (appareils photo,, graphiques cam ́eras analogiques ... ) exploite g ́en ́eralement un t ́el ́em`etre qui mesure avec pr ́ecision la distance appareil-plan objet. Les syst`emes de vision num ́eriques ac- tuels (appareils et cam ́eras num ́eriques ... ) r ́ealisent automatiquement leur mise au point `a par- tir d’une analyse de l’image restitu ́ee. Pour cela un crit`ere de nettet ́e de l’image est d ́etermin ́e `a partir des valeurs f ( i, .j ) := f ij de l’intensit ́e (luminance) des pixels. Un grand nombre de crit`eres a ́et ́e propos ́e. Parmi les plus utilis ́es figurent les crit`eres bas ́es sur l’analyse de la distribution des niveaux d’intensit ́e pixel et ceux mesurant le contenu spec- tral de l’image. La premi`ere cat ́egorie repose sur le fait que la d ́efocalisation engendre l’uniformisation des niveaux de gris, ou ce qui revient au mˆeme, que l’image nette pr ́esente l’histogramme le plus large. La seconde cat ́egorie repose sur le principe similaire qu’une image focalis ́ee contient plus de fr ́equences spatiales ́elev ́ees qu’une image floue. Dans toutes ces m ́ethodes, on recherche la distance de mise au point qui assure la majora- tion du crit`ere 2.2.1 Exemples de crit`eres de nettet ́e Crit`eres de nettet ́e bas ́es sur l’analyse de l’histogramme de l’image On note h k la distribution statistique (histogramme) des niveaux k d’intensit ́e des pixels. 22 CHAPITRE 2. TRAITEMENT PONCTUEL DES IMAGES NUMERIQUES ́ Crit`ere math ́ematique M ́ethode de F = ∑ k>T k h k Mendelsohn T est un param`etre choisi et Mayall proche du niveau de gris moyen de l’image M ́ethode de F = ∑ k>T ( k − T ) h k et T = ∑ ∑ i ∑ j f ij ∆ ij i ∑ j ∆ ij Mason et Green ∆ ij = 2 [ ( f i,j +1 − f i,j− 1 ) 2 + ( f i +1 ,j − f i− 1 ,j ) 2 ] + ( f i− 1 ,j− 1 − f i +1 ,j +1 ) 2 + ( f i− 1 ,j +1 − f i +1 ,j− 1 ) 2 Variance des F = ∑[ ∑ i i ∑ j f ij ] 2 niveaux de gris N 4 Crit`eres de nettet ́e bas ́es sur l’analyse spectrale de l’image Crit`ere math ́ematique Norme l 1 du gradient 1 F = ∑ i,j ∑ j f ij 2 N 2 − ( |f i,j − f i,j− 1 | + |f i,j +1 − f i,j | ) Norme l 2 du gradient F = ∑ i,j ( f i +1 ,j − f i,j ) 2 + ( f i,j +1 − f i,j ) 2 Remarques g ́en ́erales – Les tests des crit`eres de nettet ́e r ́ealis ́es sur un grand nombre d’images diff ́erentes montrent que leurs performances d ́ependent du type et du contenu de l’image analys ́ee ; – En r`egle g ́en ́erale, l’extremum des crit`eres est peu prononc ́e lorsque l’image contient peu de d ́etails 2.3. CORR ELATION ́ D’IMAGES NUMERIQUES ́ 23 – L’algorithme de Brenner est souvent utilis ́e car il pr ́esente g ́en ́eralement une bonne sen- sibilit ́e et la charge de calculs qu’il n ́ecessite est raisonnable. 2.3 Corr ́elation d’images num ́eriques Nous consid ́erons deux fonctions bidimensionnelles discr`etes f ( i, j ) et g ( i, j ) avec 1 ≤ i, j ≤ N. Ces fonctions sont repr ́esentatives de deux images num ́eriques monochromes comportant N 2 pixels. Leurs versions centr ́ees et r ́eduites sont d ́efinies respectivement par f c ( i, j ) = f ( i, j ) σ f − μ f et g c ( i, j ) = g ( i, j ) − μ g σ g o`u μ et σ sont respectivement la moyenne et l’ ́ecart type de chaque fonction. La fonction d’intercorr ́elation entre f c et g c est d ́efinie par la relation : φ fg ( k, l ) = N 1 2 ∑ i,j f c ( i, j ) g c ( i − k, j − l ) . (2.3.1) Il est souvent plus pratique de travailler sur des images dont les valeurs sont centr ́ees et r ́eduites. Ceci permet d’une part d’ ́eliminer de φ fg ( k, l ) le carr ́e des moyennes des images, d’autre part de normaliser les fonctions de corr ́elation. Pour ́eviter les effets de bord qui introduisent un biais dans le calcul de φ fg ( k, l ) il convient : – soit de s’assurer que la double sommation est r ́ealis ́ee sur des valeurs dont les coor- donn ́ees ne sortentjainais de l’image. Cela revient `a d ́efinir un cadre d’int ́egration dont le format, inf ́erieur `a celui de l’image, est choisi en fonction du domaine de calcul de φ fg ( k, l ); – soit de remplacer dans l’expression ( 2.3.1 ) le diviseur N 2 par la valeur variable M qui d ́epend de k et l selon la relation : M = ( N − |k| )( N − |l| ) . 2.3.1 Application `a la reconnaissance d’empreintes digitales Les fonctions d’intercorr ́elation bidimensionnelles peuvent ˆetre utilis ́ees 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 ́esent ́ees ci-dessous repr ́esentent les empreintes digitales de deux individus que nous appellerons F et G. 24 CHAPITRE 2. TRAITEMENT PONCTUEL DES IMAGES NUM ́ ERIQUES Les caract ́eristiques g ́en ́erales de ces deux images sont donn ́ees dans le tableau suivant : Individu F Individu G Format 256 x 256 256 x 256 Codage en niveaux de gris 0 `a 255 0 `a 255 Moyenne μ 132,8 127 ́ Ecart type σ 33,8 36,4 Les valeurs des deux images sont centr ́ees et r ́eduites. Pour ́eviter les effets de bords, l’in- tercorr ́elation est r ́ealis ́ee entre deux zones carr ́ees de 151 x 151 pixels (voir figure ci-dessous) La fonction est estim ́ee dans la gamme − 20 ≤ k, l ≤ 20 grˆace `a la formule suivante φ fg ( k, l ) = 1511 2 ∑ 200 i,j =50 f c ( i, j ) g c ( i − k, j − l ) . (2.3.2) ∑ 200 i,j =50 f c ( i, j ) g c ( i − k, j − l ) . (2.3.2) La repr ́esentation 3D `a gauche dans la figure ci-dessous est celle de la fonction d’autocorr ́elation φ fg ( k, l ) effectu ́ee sur l’empreinte F . Son maximum est ́egal `a 1 au centre du graphique qui cor- respond ici `a la position k = l = 0. La repr ́esentation de droite est la fonction d’intercorr ́elation entre les empreintes F et G . 2.3. CORR ́ ELATION D’IMAGES NUM ́ ERIQUES 25 Ses valeurs ne d ́epassent pas 0 . 15 ce qui prouve que les deux empreintes ne sont pas iden- tiques. Dans la r ́ealit ́e, les empreintes ne sont pas toutes obtenues dans les mˆemes conditions de positionnement. Il est n ́ecessaire d’ajouter un param`etre de rotation d’image `a la fonction d’in- tercorr ́elation ce qui peut alourdir consid ́erablement les calculs. 2.3.2 Application `a l’analyse de la texture d’une image Par d ́efinition la texture d’une image est la structure spatiale sur laquelle sont organis ́es les pixels. Les relations structurelles peuvent ˆetre : – d ́eterministes : c’est le cas de la r ́ep ́etition quasi p ́eriodique d’un motif de base (brique, carrelage, mailles de tissu ... ) ; – al ́eatoires : il n’y a pas de motif de base (sable, mur cr ́epi...) La fonction d’autocorr ́elation bidimensionnelle est bien adapt ́ee pour mettre en ́evidence les propri ́et ́es de la texture d’une image. La figure suivante repr ́esente deux exemples de texture. Nous donnons ci-dessous la fonction d’auto-corr ́elation des textures « sable » et « tissu » . 26 CHAPITRE 2. TRAITEMENT PONCTUEL DES IMAGES NUM ́ ERIQUES 2.4 Transformation de Hough [,a transformation de Hough est utilis ́ee pour d ́etecter de mani`ere syst ́ematique la pr ́esence de relations structurelles sp ́ecifiques entre des pixels dans une image Par exemple une image repr ́esentant un site urbain est compos ́ee de nombreuses lignes droites (immeubles, fenˆetres) en revanche, une vue de campagne en est quasiment d ́epourvue . Hough propose une m ́ethode de d ́etection bas ́ee 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 ́ealablement limit ́ee aux contours des objets puis binaris ́ee (2 niveaux possibles pour coder l’intensit ́e pixel). 2.4.1 Principe de la m ́ethode pour la recherche de ligne droite Supposons que l’on suspecte la pr ́esence d’une droite ∆ reliant un certain nombre de pixesl P i . Soit le pixel P 1 de coordonn ́ees ( x 1 ,y 1 ). Une infinit ́e de droites d’ ́equation : y 1 = ax 1 + b peuvent passer par P 1 . Cependant, dans le plan des param`etres ab l’ ́equation qui s’ ́ecrit b = −ax 1 + y 1 devient une droite unique D 1 (voir figures ci-dessous). Un second pixel P 2 = ( x 2 ,y 2 ) permet de d ́efinir une seconde droite D 2 du type b = −ax 2 + y 2 dans le plan ab .L’intersection de D 2 avec D 1 fournit le couple a ,b ) qui sont les param`etres 2.4. TRANSFORMATION DE HOUGH 27 de la droite recherch ́ee ∆ dans le plan image. Ainsi, tous les pixels P i qui sont align ́es sur ∆ poss`ede une droite D i dnas le plan ab qui coupe les autres au point particulier ( a ,b ). 2.4.2 Probl`eme pour la recherche de ligne verticale Repr ́esentation normale d’une droite Dans le plan image, une droite verticale poss`ede des param`etres a et b infinis, ce qui ne permet pas d’exploiter la m ́ethode pr ́ec ́edente. Pour contourner ce probl`eme, on utilise la repr ́esentation normale des droites. Cette repr ́esentation, de param`etres ρ et θ , ob ́eit `a l’ ́equation x cos θ + y sin θ = ρ . (2.4.3) Cette ́equation repr ́esente le produit scalaire (projection) entre les vecteurs V = ( cos θ sin θ ) et −−→ OM = ( xy ) . Ainsi l’ensemble des points M d’une droite se projettent sur un mˆeme vecteur particulier de coordonn ́ees polaires ( ρ,θ ) . Les cas de droites horizontales et verticales sont illustr ́es ci-dessous : 2.4.3 Transformation de Hough pour la d ́etection de droites dans une image binaire Domaine de variation des param`etres θ et ρ Il est `a noter que si ( ρ,θ ) sont les param`etres d’une droite ( −ρ,θ + π ) le sont ́egalement. Par cons ́equent l’intervalle [0 ,π dans lesquels on cherche `a calculer les param`etres de la repr ́esentation normale d’une ou plusieurs droites. 28 CHAPITRE 2. TRAITEMENT PONCTUEL DES IMAGES NUM ́ ERIQUES Le plan θρ limit ́e aux intervalles de recherche, est subdivis ́e en cellules par quantification des param`etres θ 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 ́ero, est associ ́e `a ce quadrillage Proc ́edure de transformation – Pour chaque pixel non nul P i ( x i ,y i ) de l’image, on balaye l’axe des θ de θ min `a θ max suivant la trame du tableau et pour chaque θ p on r ́esout l’ ́equation ( 2.4.3 ) ; – le r ́esultat ρ obtenu est arrondi `a la valeur ρ q du tableau la plus proche ; – si `a la valeur θ p correspond la solution ρ q la valeur A ( p, q ) est incr ́ement ́ee d’une unit ́e. ` A la fin de cette proc ́edure, A ( p, q ) = M signifie que M points de l’image sont align ́es sur la droite de param`etres approximatifs ( θ p ,ρ q ). Apr`es transformation compl`ete, le tableau peut ˆetre repr ́esent ́e sous la forme d’une image en niveaux de gris (exemple plus loin) ou celle d’un graphique 3D. La d ́ecision sur la d ́etection de droites peut ˆetre prise apr`es recherche des coor- donn ́ees des valeurs significatives du tableau. La charge de calcul n ́ecessaire pour r ́ealiser la transformation de Hough est importante. Elle d ́epend du nombre de param`etres recherch ́es : - recherche de droites : 2 param`etres ; - recherche de cercles : 3 param`etres. Exemple pour la recherche de droite : pour N pixels non nuls de l’image binaire et K sub- divisions de l’axe θ .ilya NK d ́eterminations de l’ ́equation ( 2.4.3 ). Une r ́eduction du temps de calcul peut ˆetre obtenue par l’utilisation de tables pr ́eenregistr ́ees des conversions sin θ p et cos θ p Exemple Nous consid ́erons dans cet exemple une image binaire comportant 6 x 6 pixels dont les valeurs sont donn ́ees dans le tableau suivant 2.4. TRANSFORMATION DE HOUGH 29 Deux droites ∆ 1 et ∆ 2 comportant chacune 6 pixels align ́es apparaissent clans cette image. La proc ́edure de calcul d ́ecrite au paragraphe pr ́ec ́edent est utilis ́ee avec les param`etres sui- vants : θ p varie de 0 `a 180 o par pas de 1 o . Plus et ρ max = g ́en ́eralement √ ( N 1 si on consid`ere − 1) 2 + ( N 2 − 1) 2 . une Si on image de taille N 1 ×N 2 , ρ min = − √ ( N 1 − 1) 2 + ( N 2 − 1) 2 discr ́etise l’espace de Hough avec une r ́esolution de h θ (par exemple 1 o ) pour θ et une r ́esolution de h ρ pour ρ le tableau de r ́ef ́erence est donn ́e par θ 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 ́eratif suivant permet le calcul de la transformation de Hough : M i,j sont les valeurs binaires de l’image originale : M i,j ∈ { 0 , 1 } Pour p de 1 `a N θ Pour q de 1 `a N ρ A p,q = 0 Pour i de 1 `a N 1 Pour j de 1 `a N 2 Pour p de 1 `a N θ q = Arrondi { 1 h ρ [ i cos ( p 180 π ) + j sin ( p 180 π )] − ρ min } A p,q = A p,q + 1 si M i,j = 0 30 CHAPITRE 2. TRAITEMENT PONCTUEL DES IMAGES NUM ́ ERIQUES Le mˆeme type de programme appliqu ́e `a l’image binaire (64 × 64) donne le r ́esultat ci-dessous : Chapitre 3 Filtrage 3.1 Filtrage lin ́eaire des signaux 1D L’exemple le plus courant de signal 1D est le signal sonore. D ́efinition 3.1.1 (Filtre) Un filtre est un syst`eme lin ́eaire continu et invariant . En d’autres termes, on se donne deux espaces normés X et Y ainsi qu’un opérateur linéaire continu, invariant par translation A : X → Y. Supposons qu’ on puisse d ́efinir la transform ́ee de Fourier des signaux d’entrée f et de sortie g (par exemple si ces fonctions sont dans L 1 (R) ou dans L 2 (R) et que le signal de sortie le filtrage de f par un filtre lin ́eaire est tel que ˆ g = H f ˆo`u ˆ g d ́esigne la transform ́ee de Fourier de g . La fonction H est appel ́ee fonction de transfert du filtre. Si la fonction de transfert H est dans L 2 (R) ∩ L ∞ (R), elle admet une transform ́ee de Fourier inverse h = F − 1 H , born ́ee et `a d ́ecroissance rapide, continue (sauf peut-ˆetre `a l’origine) et la relation ˆ g = h ˆ f ˆ entraıne g = h ∗ f . La r ́eponse `a l’entr ́ee f est donc un produit de convolution de l’entr ́ee avec une fonction fixe h que l’on appelle r ́eponse impulsionnelle . D ́efinition 3.1.2 On appelle r ́eponse indicielle d’un filtre sa réponse `a l’échelon unité (fonction de Heaviside) : h 1 ( t ) = ∫ 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 ́efinir un filtre par la fac ̧on dont il modifie les fr ́equences du signal d’entr ́ee, c’est-`a-dire par sa fonction de transfert H ( λ ) puisque les fr ́equences de l’entr ́ee f et de la sortie g sont li ́ees par ˆ g ( λ ) = H ( λ ) ˆ f ( λ ) . Un filtre id ́eal est un filtre qui ́elimine totalement les bandes de fr ́equence ind ́esirables sans transition et sans d ́ephasage dans les bandes conserv ́ees. Selon la bande rejet ́ee, on rencontre 4 grandes cat ́egories de filtres. La r ́egion o`u les fr ́equences sont coup ́ees est en gris ci-dessus. Par exemple le passe-bas id ́eal est le filtre qui ne modifie par les fr ́equences λ telles que λ ≤ λ c (fr ́equence de coupure) et supprime les autres. D’o `u H ( λ ) = { 1 si |λ| ≤ λ c 0 sinon On reconnaıt h ∈ L 2 (R) telle que h ˆ = H . C’est h ( t ) = sin 2 πλ πt c t . Si sait on que se limite g est continue, `a des signaux born ́ee d’entr ́ee et nulle d’ ́energie `a l’infini. finie, h ∗ f f, est h dans et H sont L 2 (R) dans comme L 2 (R) f . ˆ et g = h∗f . On Toutefois un tel filtre n’est pas r ́ealisable. On se contente de filtres passe-bas approch ́es (voir ci-dessous un dispositif physique de r ́ealisation d’un tel filtre) qui att ́enuent les hautes fr ́equences au lieu de les supprimer (voir exercices) et qui entraınent un d ́ephasage : 3.2. FILTRAGE 2D : CONVOLUTION /M ́ EDIAN 33 3.2 Filtrage 2D : convolution /m ́edian Le c ́el`ebre 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`es lors li ́ees aux distances r ́eelles en m`etres dans la sc`ene r ́eelle S . La fr ́equence spatiale est un concept d ́elicat qui d ́ecoule du fait que les images appar- tiennent au domaine spatial. Pour commencer on peut rappeler que la fr ́equence est une gran- deur qui caract ́erise le nombre de ph ́enom`enes qui se d ́eroulent au cours d’un temps donn ́e : en voiture le long d’une route vous voyez 2 bandes blanches PAR seconde : c’est une fr ́equence temporelle. Il est ensuite facile de comprendre que ce concept de fr ́equence « temporelle » peut aussi se traduire en disant qu’il y a 200 bandes blanches PAR kilom`etre : c’est une fr ́equence spatiale. Dans une image, les d ́etails se r ́ep`etent fr ́equemment sur un petit nombre de pixels, on dit qu’ils ont une fr ́equence ́elev ́ee : c’est le cas pour les bords et les contours dans une image. Au contraire, les fr ́equences basses correspondent `a des variations qui se r ́ep`etent peu car, dilu ́ees 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 ́electivement sur ces fr ́equences pour les s ́electionner, en vue de les amplifier ou de les r ́eduire. 34 CHAPITRE 3. FILTRAGE 3.2.1 Filtrage spatial Filtres de convolution Le filtrage spatial est essentiellement une op ́eration de convolution (2D). Si f est l’image `a filtrer (ou `a rehausser ) et g le filtre spatial (ou PSF ou masque )ona: f ( x, y ) ∗ g ( x, y ) = F − 1   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 : Une image num ́erique ́etant essentiellement discr`ete (pixels et niveaux de gris) nous allons pr ́esenter les filtres dans le cas discret. Dans tout ce qui suit x et y sont des entiers (coordonn ́ees des pixels) et f est `a valeurs enti`eres (dans { 0 ,··· , 255 } ). 3.2. FILTRAGE 2D : CONVOLUTION /M ́ EDIAN 35 On ne fait pas en g ́en ́eral une convolution globale mais une transformation bas ́ee sur le voisinage d’un point ( x, y ) : Le noyau de convolution du filtre κ est `a support compact inclus dans [ x 1 ,x 2 ] × [ y 1 ,y 2 ] : g ( x, y )=( f ∗ κ )( x, y ) = ∑ x 2 ∑ y 2 i = x 1 j = y 1 f ( x − i, y − j ) κ ( i, j ) . G ́en ́eralement le filtre est de dimension d impaire et est sym ́etrique. Dans ce cas [ x 1 ,x 2 ]=[ y 1 ,y 2 ]=[ −d/ 2 , d/ 2] , ( f ∗ κ )( x, y ) = ( d− 1) / 2 ∑ i = − ( d− 1) / 2 ( d− 1) / 2 ∑ j = − ( d− 1) / 2 f ( x + i, y + j ) κ ( i, j ) . (3.2.1) Filtre(i,j) w 1 w 2...

Page 1 sur 1Lecteur de document UniversityLib

méthodes mathématiques pour le traitement d’image

Informatique · exam

Browse all mathématiques documents

Quelques m ́ethodes math ́ematiques pour le traitement d’image 2 janvier 2009 Ce cours est une introduction `a la th ́eorie math ́ematique de traitement de l’image . Il est donc incomplet car les m ́ethodes dans ce domaine sont nombreuses et vari ́ees. On se polarisera sur les m ́ethodes variationnelles. Bergounioux Master 2 - 2008-2009 2 Chapitre 1 Introduction 1.1 Qu’est-ce qu’une image num ́erique ? Une image num ́erique est compos ́ee d’unit ́es ́el ́ementaires (appel ́ees pixels) qui repr ́esentent chacun une portion de l’image. Une image est d ́efinie par : – le nombre de pixels qui la compose en largeur et en hauteur (qui peut varier presque `a l’infini), – l’ ́etendue des teintes de gris ou des couleurs que peut prendre chaque pixel (on parle de dynamique de l’image). 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 ́e d’une seule couleur. 2. Les images en teintes de gris En g ́en ́eral, les images en niveaux de gris renferment 256 teintes de gris. Image `a 256 couleurs, simplement chacune de ces 256 couleurs est d ́efinie dans la gamme des gris. Par convention la valeur z ́ero repr ́esente le noir (intensit ́e lumineuse nulle) et la valeur 255 le blanc (intensit ́e lumineuse maximale). 3. Les images couleurs S’il existe plusieurs modes de repr ́esentation de la couleur, le plus utilis ́e pour le manie- ment des images num ́eriques est l’espace couleur Rouge, Vert, Bleu (R,V,B). Cet espace couleur est bas ́e sur la synth`ese additive des couleurs, c’est `a dire que le m ́elange des trois composantes (R, V, B) donne une couleur. 3 4 CHAPITRE 1. INTRODUCTION 1.1.1 Quelques d ́efinitions Pixels et niveaux de gris Echantillonnage et quantification 1.1. QU’EST-CE QU’UNE IMAGE NUM ́ ERIQUE ? 5 L’ ́echantillonnage est le proc ́ed ́e de discr ́etisation spatiale d’une image consistant `a asso- cier `a chaque zone rectangulaire R ( x, y ) d’une image continue une unique valeur I ( x, y ). On parle de sous- ́echantillonnage lorsque l’image est d ́ej`a discr ́etis ́ee et qu’on diminue le nombre d’ ́echantillons. Une image num ́erique est une image ́echantillonn ́ee et quantifi ́ee. La quantification d ́esigne la limitation du nombre de valeurs diff ́erentes que peut prendre I ( x, y ) . L’ ́echantillonnage est une ́etape fondamentale qui doit tenir compte du contenu informa- tionnel pertinent de l’image `a analyser. Sur l’exemple ci- dessous, en 1d, le signal ́echantillonn ́e « ressemble » `a une sinusoıde de fr ́equence 8 fois plus faible : 6 CHAPITRE 1. INTRODUCTION Ce ph ́enom`ene appel ́e aliasing est encore pire en 2D, car il affecte la fr ́equence et la direction des structures p ́eriodiques. Imaginons par exemple qu’on souhaite ́echantillonner l’image cor- respondant aux bandes noires ci-dessous : Avec un ́echantillonnage adapt ́e, l’image num ́erique fait apparaıtre des structures conformes `a l’information pr ́esente dans l’image : Mais en consid ́erant seulement 1 ́echantillon sur 2, une structure diff ́erente apparaıt, dont l’ana- lyse (ici des bandes verticales, plus ́epaisses) ne sera pas conforme `a la r ́ealit ́e de l’objet : Image originale Image sous- ́echantillonn ́ee 1.1. QU’EST-CE QU’UNE IMAGE NUMERIQUE ́ ? 7 La quantification peut ́egalement faire apparaıtre des distortions dans les images. Comme pour l’ ́echantillonnage, il existe des r`egles pour d ́eterminer la bonne quantification (le bon nombre de bits) pour coder les images num ́eriques. L’une d ́epend du capteur , et de sa capacit ́e effective `a observer des signaux de valeurs diff ́erentes : le rapport signal sur bruit . Le rapport signal sur bruit est d ́efini `a partir du rapport entre l’amplitude des niveaux de gris mesurables par le capteur n max − n min et le niveau du bruit, en gros l’ ́ecart-type σ n de la perturbation al ́eatoire 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 ́es du capteur, le nombre de bits r ́eellement n ́ecessaires pour coder une image varie d’une image `a l’autre, en fonction de leur contenu informationnel. Ce nombre d ́epend de l’entropie , d ́efinie `a partir de la distribution des niveaux de gris de l’image (statis- tique). E = − ∑ i≤N p i log 2 ( p i ) , o`u N est le nombre de niveaux de gris pr ́esents, p i est la proportion (0 < p i < 1) de points de l’image ayant pour niveau de gris i . Cette grandeur repr ́esente le nombre moyen de bits par pixel n ́ecessaires pour coder toute l’information pr ́esente. Elle est utilis ́ee dans les techniques de compression sans perte pour adapter le volume de donn ́ee des images `a leur contenu infor- mationnel. 8 CHAPITRE 1. INTRODUCTION Profil - Histogramme Il est possible de tracer un trait sur le flanc du z`ebre de l’image en niveaux de gris ci-dessous et obtenir le profil correspondant, c’est `a dire le niveau de gris de chaque point ou pixel travers ́e par la ligne : L’histogramme de l’image en niveau de gris ci-dessous permet d’ ́etablir une stricte corr ́elation entre les donn ́ees num ́eriques 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 ́econvolution (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 ́evoquerons successivement trois aspects fondamentaux : – Filtrage L’outil math ́ematique essentiel pour le filtrage est la transformation de Fourier (ou toute autre transformation du mˆeme type comme la transformation en ondelettes) – Segmentation La segmentation fait intervenir des notions d’optimisation, des outils g ́eom ́etriques et des ́equations aux d ́eriv ́ees partielles – Restauration Les mod`eles variationnels en restauration utilisent de l’optimisation et de l’analyse fonc- tionnelle fine (Banach, th ́eorie de la mesure). 12 CHAPITRE 1. INTRODUCTION 1.2.2 Applications – Robotique - Industrie – Assemblage, reconnaissance de pi`eces – Contrˆole de qualit ́e – V ́ehicule autonome – etc ... – T ́el ́ed ́etection – M ́et ́eo – Cartographie – Analyse des ressources terrestres – Astronomie – Restauration – etc... – Applications militaires – Guidage de missile – Reconnaissance (a ́erienne, sous-marine, etc ...) – etc ... – Imagerie m ́edicale – 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 ́ecurit ́e – Reconnaissance (d’empreintes, visages, signatures) – D ́etection de mouvement – etc... 14 CHAPITRE 1. INTRODUCTION Chapitre 2 Traitement ponctuel des images num ́eriques On s’int ́eresse d’abord aux traitements ponctuels qui consistent `a faire subir `a chaque pixel une correction ne d ́ependant que de sa valeur. On trouve dans cette cat ́egorie, les fonctions de recadrage ou d’ ́egalisation de dynamique, de binarisation ... Sauf mention particuli`ere, nous supposerons dans ce qui suit des images comportant N 2 pixels cod ́es sur 256 niveaux de gris diff ́erents. 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 ́eliorer l’aspect visuel de l’image. ` A un niveau de gris f de l’image originale correspond le niveau t ( f ) dans l’image transform ́ee. On fait subir `a chaque pixel un traitement ne d ́ependant que de sa valeur. La transformation t ( f ) peut ˆetre r ́ealis ́ee en temps r ́eel sur l’image en cours d’acquisition `a l’aide d’une table de transcodage dans la- quelle les valeurs de la transformation sont m ́emoris ́ees. Un adressage de cette m ́emoire par une donn ́ee f fournit directement la valeur t ( f ). 2.1.1 Transformation de recadrage On suppose une image de d ́epart pr ́esentant un histogramme concentr ́e dans l’intervalle [ a, b ]. Les valeurs a, b correspondent aux niveaux de gris extrˆemes pr ́esents dans cette image. Le recadrage de dynamique consiste `a ́etendre la dynamique de l’image transform ́ee `a l’ ́etendue totale [0 , 255]. La transformation de recadrage est donc une application affine qui s’ ́ecrit : 15 16 CHAPITRE 2. TRAITEMENT PONCTUEL DES IMAGES NUM ́ ERIQUES Original Recadrage : a = 30 , b = 200 Variantes pour le rehaussement des contrastes Les types de correction donn ́es ci-dessous permettent d’accentuer le contraste dans une plage pr ́ecise 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 t ( f ) =   a bf pour 0 ≤ f ≤ a (255 − b ) f + 255( b 255 − a − a ) pour a ≤ f ≤ 255 Dilatation de la dynamique des zones sombres Dilatation de la dynamique des zones claires Original Histogramme 18 CHAPITRE 2. TRAITEMENT PONCTUEL DES IMAGES NUMERIQUES ́ 2.1.2 Egalisation ́ de l’histogramme L’histogramme d’une image est rarement plat ce qui traduit une entropie non maximale. La transformation d’ ́egalisation est construite de telle fac ̧on que l’histogramme de l’image trans- form ́ee soit le plus plat possible. Cette technique am ́eliore le contraste et permet d’augmenter artificiellement la clart ́e d’une image grˆace `a une meilleure r ́epartition des intensit ́es relatives. Fonction d’aplatissement continue Consid ́erons l’histogramme continu h ( f ) donn ́e ci-dessous. En notant f = t ( f ), l’histo- gramme ́egalis ́e h ( f ) doit s’approcher de la forme id ́eale d ́ecrite ci-dessous. Deux surfaces ́el ́ementaires en correspondance dans les histogrammes initiaux et ́egalis ́es, pr ́esentent le mˆeme nombre de points ce qui permet d’ ́ecrire : f = t ( f ) = 256 N 2 ∫ f 0 h ( s ) ds . Histogramme d’origine Histogramme plat id ́eal Fonction id ́eale d’ ́egalisation d’un histogramme Fonction d’aplatissement discr`ete En remplac ̧ant l’int ́egration continue par une somme, on obtient la transformation d’ ́egalisation discr`ete suivante : f = t ( f ) = 256 N 2 ∑ f i =0 h ( i ) . h ( i ) . 2.1. CORRECTION PONCTUELLE D’UNE IMAGE -RECADRAGE DE DYNAMIQUE 19 Image ́egalis ́ee Histogramme ́egalis ́e 2.1.3 Binarisation Le but de la binarisation d’une image est d’affecter un niveau uniforme au pixels pertinents et d’ ́eliminer les autres. Seuillage Le seuillage consiste `a affecter le niveau 255 aux pixels dont la valeur est sup ́erieure `a un seuil S et 0 le niveau aux autres. Le graphe de la transformation correspondante est le suivant Original Histogramme Fonction « seuillage » 20 CHAPITRE 2. TRAITEMENT PONCTUEL DES IMAGES NUM ́ ERIQUES Seuillage `a 70 Extraction d’une fenêtre d’intensité Avec la transformation d ́ecrite ci-dessous, la nouvelle image ne visualise que les pixels dont le e niveau d’intensit ́e appartient `a l’intervalle [ a, b ]. Sous r ́eserve 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. Original Histogramme Fonction « fenˆetre d’intensit ́e » 2.2. ANAYSE DE LA NETTET ́ E D’UNE IMAGE NUM ́ ERIQUE 21 Seuillage avec fenˆetre d’intensit ́e entre 30 et 100 2.2 Anayse de la nettet ́e d’une image num ́erique La focalisation automatique, ou mise au point, des syst`emes de prise de vue traditionnels (appareils photo,, graphiques cam ́eras analogiques ... ) exploite g ́en ́eralement un t ́el ́em`etre qui mesure avec pr ́ecision la distance appareil-plan objet. Les syst`emes de vision num ́eriques ac- tuels (appareils et cam ́eras num ́eriques ... ) r ́ealisent automatiquement leur mise au point `a par- tir d’une analyse de l’image restitu ́ee. Pour cela un crit`ere de nettet ́e de l’image est d ́etermin ́e `a partir des valeurs f ( i, .j ) := f ij de l’intensit ́e (luminance) des pixels. Un grand nombre de crit`eres a ́et ́e propos ́e. Parmi les plus utilis ́es figurent les crit`eres bas ́es sur l’analyse de la distribution des niveaux d’intensit ́e pixel et ceux mesurant le contenu spec- tral de l’image. La premi`ere cat ́egorie repose sur le fait que la d ́efocalisation engendre l’uniformisation des niveaux de gris, ou ce qui revient au mˆeme, que l’image nette pr ́esente l’histogramme le plus large. La seconde cat ́egorie repose sur le principe similaire qu’une image focalis ́ee contient plus de fr ́equences spatiales ́elev ́ees qu’une image floue. Dans toutes ces m ́ethodes, on recherche la distance de mise au point qui assure la majora- tion du crit`ere 2.2.1 Exemples de crit`eres de nettet ́e Crit`eres de nettet ́e bas ́es sur l’analyse de l’histogramme de l’image On note h k la distribution statistique (histogramme) des niveaux k d’intensit ́e des pixels. 22 CHAPITRE 2. TRAITEMENT PONCTUEL DES IMAGES NUMERIQUES ́ Crit`ere math ́ematique M ́ethode de F = ∑ k>T k h k Mendelsohn T est un param`etre choisi et Mayall proche du niveau de gris moyen de l’image M ́ethode de F = ∑ k>T ( k − T ) h k et T = ∑ ∑ i ∑ j f ij ∆ ij i ∑ j ∆ ij Mason et Green ∆ ij = 2 [ ( f i,j +1 − f i,j− 1 ) 2 + ( f i +1 ,j − f i− 1 ,j ) 2 ] + ( f i− 1 ,j− 1 − f i +1 ,j +1 ) 2 + ( f i− 1 ,j +1 − f i +1 ,j− 1 ) 2 Variance des F = ∑[ ∑ i i ∑ j f ij ] 2 niveaux de gris N 4 Crit`eres de nettet ́e bas ́es sur l’analyse spectrale de l’image Crit`ere math ́ematique Norme l 1 du gradient 1 F = ∑ i,j ∑ j f ij 2 N 2 − ( |f i,j − f i,j− 1 | + |f i,j +1 − f i,j | ) Norme l 2 du gradient F = ∑ i,j ( f i +1 ,j − f i,j ) 2 + ( f i,j +1 − f i,j ) 2 Remarques g ́en ́erales – Les tests des crit`eres de nettet ́e r ́ealis ́es sur un grand nombre d’images diff ́erentes montrent que leurs performances d ́ependent du type et du contenu de l’image analys ́ee ; – En r`egle g ́en ́erale, l’extremum des crit`eres est peu prononc ́e lorsque l’image contient peu de d ́etails 2.3. CORR ELATION ́ D’IMAGES NUMERIQUES ́ 23 – L’algorithme de Brenner est souvent utilis ́e car il pr ́esente g ́en ́eralement une bonne sen- sibilit ́e et la charge de calculs qu’il n ́ecessite est raisonnable. 2.3 Corr ́elation d’images num ́eriques Nous consid ́erons deux fonctions bidimensionnelles discr`etes f ( i, j ) et g ( i, j ) avec 1 ≤ i, j ≤ N. Ces fonctions sont repr ́esentatives de deux images num ́eriques monochromes comportant N 2 pixels. Leurs versions centr ́ees et r ́eduites sont d ́efinies respectivement par f c ( i, j ) = f ( i, j ) σ f − μ f et g c ( i, j ) = g ( i, j ) − μ g σ g o`u μ et σ sont respectivement la moyenne et l’ ́ecart type de chaque fonction. La fonction d’intercorr ́elation entre f c et g c est d ́efinie par la relation : φ fg ( k, l ) = N 1 2 ∑ i,j f c ( i, j ) g c ( i − k, j − l ) . (2.3.1) Il est souvent plus pratique de travailler sur des images dont les valeurs sont centr ́ees et r ́eduites. Ceci permet d’une part d’ ́eliminer de φ fg ( k, l ) le carr ́e des moyennes des images, d’autre part de normaliser les fonctions de corr ́elation. Pour ́eviter les effets de bord qui introduisent un biais dans le calcul de φ fg ( k, l ) il convient : – soit de s’assurer que la double sommation est r ́ealis ́ee sur des valeurs dont les coor- donn ́ees ne sortentjainais de l’image. Cela revient `a d ́efinir un cadre d’int ́egration dont le format, inf ́erieur `a celui de l’image, est choisi en fonction du domaine de calcul de φ fg ( k, l ); – soit de remplacer dans l’expression ( 2.3.1 ) le diviseur N 2 par la valeur variable M qui d ́epend de k et l selon la relation : M = ( N − |k| )( N − |l| ) . 2.3.1 Application `a la reconnaissance d’empreintes digitales Les fonctions d’intercorr ́elation bidimensionnelles peuvent ˆetre utilis ́ees 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 ́esent ́ees ci-dessous repr ́esentent les empreintes digitales de deux individus que nous appellerons F et G. 24 CHAPITRE 2. TRAITEMENT PONCTUEL DES IMAGES NUM ́ ERIQUES Les caract ́eristiques g ́en ́erales de ces deux images sont donn ́ees dans le tableau suivant : Individu F Individu G Format 256 x 256 256 x 256 Codage en niveaux de gris 0 `a 255 0 `a 255 Moyenne μ 132,8 127 ́ Ecart type σ 33,8 36,4 Les valeurs des deux images sont centr ́ees et r ́eduites. Pour ́eviter les effets de bords, l’in- tercorr ́elation est r ́ealis ́ee entre deux zones carr ́ees de 151 x 151 pixels (voir figure ci-dessous) La fonction est estim ́ee dans la gamme − 20 ≤ k, l ≤ 20 grˆace `a la formule suivante φ fg ( k, l ) = 1511 2 ∑ 200 i,j =50 f c ( i, j ) g c ( i − k, j − l ) . (2.3.2) ∑ 200 i,j =50 f c ( i, j ) g c ( i − k, j − l ) . (2.3.2) La repr ́esentation 3D `a gauche dans la figure ci-dessous est celle de la fonction d’autocorr ́elation φ fg ( k, l ) effectu ́ee sur l’empreinte F . Son maximum est ́egal `a 1 au centre du graphique qui cor- respond ici `a la position k = l = 0. La repr ́esentation de droite est la fonction d’intercorr ́elation entre les empreintes F et G . 2.3. CORR ́ ELATION D’IMAGES NUM ́ ERIQUES 25 Ses valeurs ne d ́epassent pas 0 . 15 ce qui prouve que les deux empreintes ne sont pas iden- tiques. Dans la r ́ealit ́e, les empreintes ne sont pas toutes obtenues dans les mˆemes conditions de positionnement. Il est n ́ecessaire d’ajouter un param`etre de rotation d’image `a la fonction d’in- tercorr ́elation ce qui peut alourdir consid ́erablement les calculs. 2.3.2 Application `a l’analyse de la texture d’une image Par d ́efinition la texture d’une image est la structure spatiale sur laquelle sont organis ́es les pixels. Les relations structurelles peuvent ˆetre : – d ́eterministes : c’est le cas de la r ́ep ́etition quasi p ́eriodique d’un motif de base (brique, carrelage, mailles de tissu ... ) ; – al ́eatoires : il n’y a pas de motif de base (sable, mur cr ́epi...) La fonction d’autocorr ́elation bidimensionnelle est bien adapt ́ee pour mettre en ́evidence les propri ́et ́es de la texture d’une image. La figure suivante repr ́esente deux exemples de texture. Nous donnons ci-dessous la fonction d’auto-corr ́elation des textures « sable » et « tissu » . 26 CHAPITRE 2. TRAITEMENT PONCTUEL DES IMAGES NUM ́ ERIQUES 2.4 Transformation de Hough [,a transformation de Hough est utilis ́ee pour d ́etecter de mani`ere syst ́ematique la pr ́esence de relations structurelles sp ́ecifiques entre des pixels dans une image Par exemple une image repr ́esentant un site urbain est compos ́ee de nombreuses lignes droites (immeubles, fenˆetres) en revanche, une vue de campagne en est quasiment d ́epourvue . Hough propose une m ́ethode de d ́etection bas ́ee 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 ́ealablement limit ́ee aux contours des objets puis binaris ́ee (2 niveaux possibles pour coder l’intensit ́e pixel). 2.4.1 Principe de la m ́ethode pour la recherche de ligne droite Supposons que l’on suspecte la pr ́esence d’une droite ∆ reliant un certain nombre de pixesl P i . Soit le pixel P 1 de coordonn ́ees ( x 1 ,y 1 ). Une infinit ́e de droites d’ ́equation : y 1 = ax 1 + b peuvent passer par P 1 . Cependant, dans le plan des param`etres ab l’ ́equation qui s’ ́ecrit b = −ax 1 + y 1 devient une droite unique D 1 (voir figures ci-dessous). Un second pixel P 2 = ( x 2 ,y 2 ) permet de d ́efinir une seconde droite D 2 du type b = −ax 2 + y 2 dans le plan ab .L’intersection de D 2 avec D 1 fournit le couple a ,b ) qui sont les param`etres 2.4. TRANSFORMATION DE HOUGH 27 de la droite recherch ́ee ∆ dans le plan image. Ainsi, tous les pixels P i qui sont align ́es sur ∆ poss`ede une droite D i dnas le plan ab qui coupe les autres au point particulier ( a ,b ). 2.4.2 Probl`eme pour la recherche de ligne verticale Repr ́esentation normale d’une droite Dans le plan image, une droite verticale poss`ede des param`etres a et b infinis, ce qui ne permet pas d’exploiter la m ́ethode pr ́ec ́edente. Pour contourner ce probl`eme, on utilise la repr ́esentation normale des droites. Cette repr ́esentation, de param`etres ρ et θ , ob ́eit `a l’ ́equation x cos θ + y sin θ = ρ . (2.4.3) Cette ́equation repr ́esente le produit scalaire (projection) entre les vecteurs V = ( cos θ sin θ ) et −−→ OM = ( xy ) . Ainsi l’ensemble des points M d’une droite se projettent sur un mˆeme vecteur particulier de coordonn ́ees polaires ( ρ,θ ) . Les cas de droites horizontales et verticales sont illustr ́es ci-dessous : 2.4.3 Transformation de Hough pour la d ́etection de droites dans une image binaire Domaine de variation des param`etres θ et ρ Il est `a noter que si ( ρ,θ ) sont les param`etres d’une droite ( −ρ,θ + π ) le sont ́egalement. Par cons ́equent l’intervalle [0 ,π dans lesquels on cherche `a calculer les param`etres de la repr ́esentation normale d’une ou plusieurs droites. 28 CHAPITRE 2. TRAITEMENT PONCTUEL DES IMAGES NUM ́ ERIQUES Le plan θρ limit ́e aux intervalles de recherche, est subdivis ́e en cellules par quantification des param`etres θ 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 ́ero, est associ ́e `a ce quadrillage Proc ́edure de transformation – Pour chaque pixel non nul P i ( x i ,y i ) de l’image, on balaye l’axe des θ de θ min `a θ max suivant la trame du tableau et pour chaque θ p on r ́esout l’ ́equation ( 2.4.3 ) ; – le r ́esultat ρ obtenu est arrondi `a la valeur ρ q du tableau la plus proche ; – si `a la valeur θ p correspond la solution ρ q la valeur A ( p, q ) est incr ́ement ́ee d’une unit ́e. ` A la fin de cette proc ́edure, A ( p, q ) = M signifie que M points de l’image sont align ́es sur la droite de param`etres approximatifs ( θ p ,ρ q ). Apr`es transformation compl`ete, le tableau peut ˆetre repr ́esent ́e sous la forme d’une image en niveaux de gris (exemple plus loin) ou celle d’un graphique 3D. La d ́ecision sur la d ́etection de droites peut ˆetre prise apr`es recherche des coor- donn ́ees des valeurs significatives du tableau. La charge de calcul n ́ecessaire pour r ́ealiser la transformation de Hough est importante. Elle d ́epend du nombre de param`etres recherch ́es : - recherche de droites : 2 param`etres ; - recherche de cercles : 3 param`etres. Exemple pour la recherche de droite : pour N pixels non nuls de l’image binaire et K sub- divisions de l’axe θ .ilya NK d ́eterminations de l’ ́equation ( 2.4.3 ). Une r ́eduction du temps de calcul peut ˆetre obtenue par l’utilisation de tables pr ́eenregistr ́ees des conversions sin θ p et cos θ p Exemple Nous consid ́erons dans cet exemple une image binaire comportant 6 x 6 pixels dont les valeurs sont donn ́ees dans le tableau suivant 2.4. TRANSFORMATION DE HOUGH 29 Deux droites ∆ 1 et ∆ 2 comportant chacune 6 pixels align ́es apparaissent clans cette image. La proc ́edure de calcul d ́ecrite au paragraphe pr ́ec ́edent est utilis ́ee avec les param`etres sui- vants : θ p varie de 0 `a 180 o par pas de 1 o . Plus et ρ max = g ́en ́eralement √ ( N 1 si on consid`ere − 1) 2 + ( N 2 − 1) 2 . une Si on image de taille N 1 ×N 2 , ρ min = − √ ( N 1 − 1) 2 + ( N 2 − 1) 2 discr ́etise l’espace de Hough avec une r ́esolution de h θ (par exemple 1 o ) pour θ et une r ́esolution de h ρ pour ρ le tableau de r ́ef ́erence est donn ́e par θ 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 ́eratif suivant permet le calcul de la transformation de Hough : M i,j sont les valeurs binaires de l’image originale : M i,j ∈ { 0 , 1 } Pour p de 1 `a N θ Pour q de 1 `a N ρ A p,q = 0 Pour i de 1 `a N 1 Pour j de 1 `a N 2 Pour p de 1 `a N θ q = Arrondi { 1 h ρ [ i cos ( p 180 π ) + j sin ( p 180 π )] − ρ min } A p,q = A p,q + 1 si M i,j = 0 30 CHAPITRE 2. TRAITEMENT PONCTUEL DES IMAGES NUM ́ ERIQUES Le mˆeme type de programme appliqu ́e `a l’image binaire (64 × 64) donne le r ́esultat ci-dessous : Chapitre 3 Filtrage 3.1 Filtrage lin ́eaire des signaux 1D L’exemple le plus courant de signal 1D est le signal sonore. D ́efinition 3.1.1 (Filtre) Un filtre est un syst`eme lin ́eaire continu et invariant . En d’autres termes, on se donne deux espaces normés X et Y ainsi qu’un opérateur linéaire continu, invariant par translation A : X → Y. Supposons qu’ on puisse d ́efinir la transform ́ee de Fourier des signaux d’entrée f et de sortie g (par exemple si ces fonctions sont dans L 1 (R) ou dans L 2 (R) et que le signal de sortie le filtrage de f par un filtre lin ́eaire est tel que ˆ g = H f ˆo`u ˆ g d ́esigne la transform ́ee de Fourier de g . La fonction H est appel ́ee fonction de transfert du filtre. Si la fonction de transfert H est dans L 2 (R) ∩ L ∞ (R), elle admet une transform ́ee de Fourier inverse h = F − 1 H , born ́ee et `a d ́ecroissance rapide, continue (sauf peut-ˆetre `a l’origine) et la relation ˆ g = h ˆ f ˆ entraıne g = h ∗ f . La r ́eponse `a l’entr ́ee f est donc un produit de convolution de l’entr ́ee avec une fonction fixe h que l’on appelle r ́eponse impulsionnelle . D ́efinition 3.1.2 On appelle r ́eponse indicielle d’un filtre sa réponse `a l’échelon unité (fonction de Heaviside) : h 1 ( t ) = ∫ 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 ́efinir un filtre par la fac ̧on dont il modifie les fr ́equences du signal d’entr ́ee, c’est-`a-dire par sa fonction de transfert H ( λ ) puisque les fr ́equences de l’entr ́ee f et de la sortie g sont li ́ees par ˆ g ( λ ) = H ( λ ) ˆ f ( λ ) . Un filtre id ́eal est un filtre qui ́elimine totalement les bandes de fr ́equence ind ́esirables sans transition et sans d ́ephasage dans les bandes conserv ́ees. Selon la bande rejet ́ee, on rencontre 4 grandes cat ́egories de filtres. La r ́egion o`u les fr ́equences sont coup ́ees est en gris ci-dessus. Par exemple le passe-bas id ́eal est le filtre qui ne modifie par les fr ́equences λ telles que λ ≤ λ c (fr ́equence de coupure) et supprime les autres. D’o `u H ( λ ) = { 1 si |λ| ≤ λ c 0 sinon On reconnaıt h ∈ L 2 (R) telle que h ˆ = H . C’est h ( t ) = sin 2 πλ πt c t . Si sait on que se limite g est continue, `a des signaux born ́ee d’entr ́ee et nulle d’ ́energie `a l’infini. finie, h ∗ f f, est h dans et H sont L 2 (R) dans comme L 2 (R) f . ˆ et g = h∗f . On Toutefois un tel filtre n’est pas r ́ealisable. On se contente de filtres passe-bas approch ́es (voir ci-dessous un dispositif physique de r ́ealisation d’un tel filtre) qui att ́enuent les hautes fr ́equences au lieu de les supprimer (voir exercices) et qui entraınent un d ́ephasage : 3.2. FILTRAGE 2D : CONVOLUTION /M ́ EDIAN 33 3.2 Filtrage 2D : convolution /m ́edian Le c ́el`ebre 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`es lors li ́ees aux distances r ́eelles en m`etres dans la sc`ene r ́eelle S . La fr ́equence spatiale est un concept d ́elicat qui d ́ecoule du fait que les images appar- tiennent au domaine spatial. Pour commencer on peut rappeler que la fr ́equence est une gran- deur qui caract ́erise le nombre de ph ́enom`enes qui se d ́eroulent au cours d’un temps donn ́e : en voiture le long d’une route vous voyez 2 bandes blanches PAR seconde : c’est une fr ́equence temporelle. Il est ensuite facile de comprendre que ce concept de fr ́equence « temporelle » peut aussi se traduire en disant qu’il y a 200 bandes blanches PAR kilom`etre : c’est une fr ́equence spatiale. Dans une image, les d ́etails se r ́ep`etent fr ́equemment sur un petit nombre de pixels, on dit qu’ils ont une fr ́equence ́elev ́ee : c’est le cas pour les bords et les contours dans une image. Au contraire, les fr ́equences basses correspondent `a des variations qui se r ́ep`etent peu car, dilu ́ees 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 ́electivement sur ces fr ́equences pour les s ́electionner, en vue de les amplifier ou de les r ́eduire. 34 CHAPITRE 3. FILTRAGE 3.2.1 Filtrage spatial Filtres de convolution Le filtrage spatial est essentiellement une op ́eration de convolution (2D). Si f est l’image `a filtrer (ou `a rehausser ) et g le filtre spatial (ou PSF ou masque )ona: f ( x, y ) ∗ g ( x, y ) = F − 1   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 : Une image num ́erique ́etant essentiellement discr`ete (pixels et niveaux de gris) nous allons pr ́esenter les filtres dans le cas discret. Dans tout ce qui suit x et y sont des entiers (coordonn ́ees des pixels) et f est `a valeurs enti`eres (dans { 0 ,··· , 255 } ). 3.2. FILTRAGE 2D : CONVOLUTION /M ́ EDIAN 35 On ne fait pas en g ́en ́eral une convolution globale mais une transformation bas ́ee sur le voisinage d’un point ( x, y ) : Le noyau de convolution du filtre κ est `a support compact inclus dans [ x 1 ,x 2 ] × [ y 1 ,y 2 ] : g ( x, y )=( f ∗ κ )( x, y ) = ∑ x 2 ∑ y 2 i = x 1 j = y 1 f ( x − i, y − j ) κ ( i, j ) . G ́en ́eralement le filtre est de dimension d impaire et est sym ́etrique. Dans ce cas [ x 1 ,x 2 ]=[ y 1 ,y 2 ]=[ −d/ 2 , d/ 2] , ( f ∗ κ )( x, y ) = ( d− 1) / 2 ∑ i = − ( d− 1) / 2 ( d− 1) / 2 ∑ j = − ( d− 1) / 2 f ( x + i, y + j ) κ ( i, j ) . (3.2.1) Filtre(i,j) w 1 w 2...