Traitement d’images
Rédigé par Mr. Bachir Jean EL HAGE
Université Joseph Fourier – INPG
Grenoble 1 - FRANCE
A. Introduction
Dans les écoles, lycées et même aux seins des établissements universitaires on se pose toujours la question suivante :
A quoi servent les maths ?
Tout d’abord les maths nous procurent « un esprit critique » nous permettant de raisonner avec logique et de mieux dialoguer dans notre vie quotidienne, de convaincre et de critiquer un argument.
D’accord mais Mr à part ça ? Un médecin n’a pas besoin des maths ! Un informaticien non plus !
Bien sûr que si. Les maths sont aussi le cœur de toutes les recherches scientifiques, de tout le progrès médical et informatique. La physique bien évidement se base sur les maths, l’astronomie aussi, la sécurité des système et la chiffrement des codes…
Vous avez certainement regardé vos photos sur un ordinateur, vous avez aussi essayé de faire un zoom. Vous avez peut être utilisé des logiciels comme adobe Photoshop ou autre pour retoucher vos photos, améliorer la qualité d’une image pixélisée ou mal scanné ou floutée.
Vous savez aussi que la police possède des logiciels de reconnaissance faciale qui arrive à reconnaitre un visage avec un minimum de données. Grace à une photo de basse qualité prise avec une caméra de surveillance on arrive quand même à reconnaitre la personne en question avec certitude !
Mais êtes-vous demandé un jour comment cela fonctionne-t-il ? Pensiez-vous que tout cela se joue grâce aux mathématiques ? Aux polynômes, fonctions, dérivées première et dérivée seconde, sinus, cosinus, tangentes, … ?
Je vais tenter de vous expliquer dans la suite de ce document comment intervient les mathématiques dans le traitement d’images tout en vous proposant théorie et exemples réalisés sous Matlab pour une compréhension optimale du sujet proposé.
B. Interpolation et approximation (définitions et exemples)
1. Généralité
En analyse numérique l'interpolation est une opération mathématique permettant de construire une courbe à partir de la donnée d'un nombre fini de points, ou une fonction à partir de la donnée d'un nombre fini de valeurs. La solution du problème d'interpolation passe par les points prescrits, et, suivant le type d'interpolation, il lui est demandé de vérifier des propriétés supplémentaires.
L’interpolant 
est
généralement construit de l’unique fonction s’écrivant sous la forme :
Exemple d’interpolation par Spline :
|
Nombre fini de points distribué aléatoirement :
|
Après interpolation (par Spline) :
|
2. Problème
Ayant un nombre fini de points on
cherche à déterminer une fonction 
passant par ses points qui soit
facile à évaluer. Le problème c’est qu’il existe une infinité de
solutions !
Ce qu’il faut alors faire c’est de se restreindre à une famille de fonctions : exponentielle, polynômes, fonctions trigonométriques, …
3. Interpolation linéaire
Le type le plus simple d'interpolation est l'interpolation linéaire, qui consiste à joindre les points donnés. Elle peut servir à estimer les valeurs situées entre les données de la table.
Par exemple, si nous souhaitons
déterminer 
alors
que l'on connait les valeurs de 
, on
prend la moyenne des 2 valeurs sachant que 2,5 est le milieu des 2 points.
On obtient par conséquent
Plus généralement, la droite d'interpolation aura pour équation (trois formulations équivalentes) :
Ou bien (formule de Taylor-Young au premier ordre) :
Ou bien :
Cette dernière formule correspond à la moyenne pondérée.
|
Les points rouges correspondent aux points
( |
Cette méthode est
rapide et aisée mais elle manque de précision. Elle présente aussi l’inconvénient
de ne pas être dérivable au point 
.
L'erreur d'estimation
montre que l'interpolation linéaire n'est pas très précise. Si la fonction 
que l'on souhaite
interpoler est deux fois continument dérivable et si 
alors l'erreur
d'interpolation est donnée par :
En d'autres termes, l'erreur est proportionnelle au carré de la distance entre les nœuds.
D'autres méthodes d'interpolation permettent d'obtenir des fonctions d'interpolation plus lisses, par exemple, l'interpolation polynomiale
4. Interpolation polynomiale de type Lagrange
Théorème
Soient 
points distincts 
réels et réels 
, il existe un unique
polynôme 
tel que 
pour 
.
Construction du
polynôme 
:
étant le
polynôme de Lagrange et est définie par :
Propriété de 
:
Exemple d’application
Soit à trouver le polynôme interpolant les 3 points suivants
(0 ; 1) , (2 ; 5) et (4 ; 17)
Les polynômes de Lagrange associés sont
Calculons alors le polynôme d’interpolation
L’algorithme et le résultat de l’exemple sous Matlab :
|
Fonction (P)=lagrange(X,Y) n= nombre de points. x=poly(0,"x");P=0; pour i=1 à n, L=1; pour j=[1:i-1,i+1:n] L=L*(x-X(j))/(X(i)-X(j)); Fin pour P=P+L*Y(i); Fin pour Fin fonction
Compilation : -->X=[0;2;4]; Y=[1;5;17]; P=lagrange(X,Y) P = 1 + x^2 |
|
L’interpolation polynomiale est facile à comprendre et à programmer, elle donne en plus des bons résultats avec une erreur minimale.
5. Approximation et courbes de Bézier
|
L'interpolation doit être distinguée de l'approximation de fonction, qui consiste à chercher la fonction la plus proche possible, selon certains critères, d'une fonction donnée. Les courbes de Béziers sont un exemple d’approximation :
|
|
Dans le cas de l'approximation, il n'est en général plus imposé de passer exactement par les points donnés initialement. Ceci permet de mieux prendre en compte le cas des erreurs de mesure, et c'est ainsi que l'exploitation de données expérimentales pour la recherche de lois empiriques relève plus souvent de la régression linéaire, ou plus généralement de la méthode des moindres carrés.
Après l’explication théorique de l’interpolation et de la manière dont on trouve le polynôme ou la fonction ou la courbe interpolant un nombre fini de points, nous allons passer tout de suite à son utilité dans le traitement d’images !
C. Comment l'interpolation fonctionne-t-elle ?
Dans notre recherche nous nous concentrerons exclusivement sur la fonction de l'interpolation dans le contexte de la résolution d'image.
L'interpolation est un procédé d'estimation de valeur entre deux informations préexistantes. Il est utilisé dans les scanners, les appareils numériques et les logiciels d'édition d'images afin de produire une image avec une résolution (le nombre de pixels verticaux et horizontaux) plus grande que celle capturée par le capteur.
Simplement formulé, l'interpolation "invente" des pixels là où il n'y en avait pas et les intercale entre deux originaux pour augmenter la taille d'image. Si cela semble être de la triche-et c'est parfois effectivement le cas. Les images ci-dessous montrent le mécanisme d'une simple interpolation. Notez que dans une interpolation réelle des pixels de couleur, ceux-ci serait de couleur identique à celle des originaux environnants.
|
|
|
|
Il existe différentes méthodes pour interpoler une image: Linéaire, Bilinéaire, Bicubique et Fractale. Toutes tentent d'augmenter la taille de l'image tout en limitant au maximum les effets d'un tel processus.
Généralement, le problème majeur avec l'interpolation est qu'elle peut augmenter fortement un défaut de l'image en l'agrandissant. L'interpolation Bicubique est habituellement considérée comme la meilleure méthode, mais pourtant, il arrive qu'elle ne produise pas les meilleurs résultats.
L'interpolation fonctionne le mieux lorsqu'elle est appliquée à petite dose et sur une grande quantité d'informations. Une image constituée d'une faible quantité de pixels montrera plus de trace de dégradation qu'une image plus riche au départ. Dans tous les cas, l'interpolation n'inventera pas des détails qui ne se trouvaient pas dans l'image originale.
1. Utilité de l’interpolation
En terme informatique, l’interpolation est un procédé qui permet d'augmenter la résolution d'une image numérisée en définissant des pixels intermédiaires entre des pixels réels grâce à un algorithme mathématique, en calculant la moyenne des couleurs des pixels avoisinants. Cette technologie permet donc d'obtenir des résultats intéressants.
Toshiba a développé une nouvelle technique de super-résolution pour la création de haute résolution d’images ou vidéo à partir de ceux à faible résolution.
Si une partie de l'image est agrandie, la dégradation de la qualité d'image et l'image reste incertain, même si l'interpolation est effectuée en douceur entre les pixels.
2. Quelques résultats intéressants créés sous Matlab :
Avec une bonne connaissance de Matlab on arrive à créer son propre logiciel capable de faire un zoom sur les images en gardant une bonne qualité, de créer des surfaces en 3D coloriées en utilisant des fonctions mathématiques telles le sinus, le cosinus ou l’exponentielle. D’utiliser l’interpolation pour fusionner les couleurs, …
|
|
Jeux de cosinus, sinus, etc. :
|
|
|
|
L’interpolation permet aussi de corriger le flou d’une image
En travaillant sur la direction du flou et sur des caractéristiques de la vitesse on peut utiliser l’espace de Fourier pour avoir le résultat suivant :
|
|
|
Etes-vous toujours convaincu que les Maths ne servent à rien ?
D. Détection des contours
Le but de la détection de contours est de repérer les points d'une image numérique qui correspondent à un changement brutal de l'intensité lumineuse. Ces changements de propriétés de l'image traduisent en général des événements importants ou des changements dans les propriétés du monde. Ils incluent des discontinuités dans la profondeur, dans l'orientation d'une surface, dans les propriétés d'un matériau et dans l'éclairage d'une scène. La détection de contour est un champ de la recherche qui appartient au traitement d'image et à la vision par ordinateur, particulièrement dans le domaine de l'extraction de caractéristiques.
La détection des contours d'une image réduit de manière significative la quantité de données et élimine les informations qu'on peut juger moins pertinentes, tout en préservant les propriétés structurelles importantes de l'image. Il existe un grand nombre de méthodes de détection de l'image mais la plupart d'entre elles peuvent être regroupées en deux catégories. La première recherche les extremums de la dérivée première, en général les maximums locaux de l'intensité du gradient. La seconde recherche les annulations de la dérivée seconde, en général les annulations du laplacien ou d'une expression différentielle non-linéaire.
Il existe plusieurs model pour la détection des contours :
Quelques modèles de contours. Le plus utilisé est celui en marche d’escalier.
Un contour est caractérisé par un changement brutal de la valeur. Le but de l'opération est de transformer cette image en une autre dans laquelle les contours apparaissent par convention en blanc sur fond noir.
Dans une section horizontale (ou verticale) de l'image rectangulaire, les variations de la valeur sont décrites par une courbe. Sur celle-ci un point d'un contour est associé à un maximum de la pente, c'est-à-dire à un extremum (maximum ou minimum) de la dérivée première. Cet extremum peut aussi s'interpréter comme un zéro de la dérivée seconde.
Dans une image numérisée, à chaque pixel est associée une valeur qui est en général différente de la valeur des pixels voisins. La notion de dérivée correspondant à une variation infiniment petite doit donc être remplacée par l'approximation différence finie utilisée en calcul numérique. Le problème est simplifié car on ne s'intéresse ici qu'aux comparaisons entre dérivées indépendamment de leurs valeurs. Ainsi la dérivée première au niveau d'un pixel se réduit à la différence entre les valeurs des deux pixels voisins, la dérivée seconde étant la différence entre les dérivées moyennées aux frontières des pixels.
La détection de contour est très utile en traitement d'images, c'est par exemple une étape indispensable à la reconnaissance de formes. Ces algorithmes sont également utilisés en imagerie médicale, cartographies, ...
La détection des contours de Marr / Hildreth
La détection des contours de Marr / Hildreth est basée sur les passages par zéro du Laplacien de l'opérateur gaussien appliqué à l'image pour différentes valeurs de sigma, l'écart-type de la gaussienne. Ce qui donne une mosaïque de passages à zéro pour quatre choix de Sigma calculé en utilisant la boîte à outils de traitement d'image Matlab.
Exemple détection des contours de l’image suivante (programmé avec Matlab):
Résultat de la détection utilisant le Filtre de Canny (à gauche) puis Marr/Hildreth (à droite)
|
|
|
Haut : à gauche est sigma = 1, à droite est sigma = 2, Bas : à gauche est sigma = 3, à droite est sigma = 4.
(Matlab Laplacian of Gaussian la détection de contour sélectionne normalement un seuil, afin que seuls les passages par zéro de la force suffisante soient affichés. Ici, le seuil est forcé à zéro afin que tous les passages par zéro sont rapportés, comme c'est requis par théorie de détection de pointe de Marr / Hildreth.)
Nous ne rentrerons pas dans les détails des formules mathématiques utilisées par ces procédés. Nous nous contenterons des résultats trouvés et de leur utilité.
Domaine d’application
En astrologie par exemple, on désire à partir d’un cliché pris par un télescope, pouvoir détecter de nouveaux corps célestes. Par ailleurs, en imagerie médicale, il est important de pouvoir déceler des tumeurs cancéreuses, à partir d’une scanographie. Dans l’exemple qui suit, nous présenterons une des nombreuses méthodes de détection utilisées en reconnaissance faciale et en imagerie satellite.
Des chercheurs allemands ont développé une nouvelle technologie d'analyse faciale rapide.
Elle permet d'identifier un visage humain sur une photo (ce que Google Images fait déjà), et est capable de différencier un visage d'homme ou de femme, et d'analyser l'expression du visage (content / triste, etc...).
E. Codage d'une image, représentation spatiale
Une image est considérée comme un ensemble de points ou pixels (picture element), associés au quadrillage rectangulaire de l'image d'origine. La représentation d'une image se fait donc par l'intermédiaire d'une matrice d'entiers codés entre 0 et 255. Les images en niveau de gris sont représentées par des matrices 2D, les images couleurs représentés par 3 composantes (Rouge, Vert, Bleu) sont représentées par des matrices 3D. On accède à un pixel grâce a son indice de ligne et son indice de colonne. Le premier pixel d'une image est le pixel en haut à gauche. Cette représentation est appelé représentation spatiale de l'image.
Dans un prochain projet j’expliciterais aussi le domaine de la cryptographie et l’utilité des mathématique dans les systèmes bancaire et tous les programmes travaillant sur la sécurité de l’information.
F. Conclusion
J’espère vous avoir donné ne serait-ce qu’une petite idée sur l’utilité des mathématiques. Vous n’avez désormais plus le droit de dire « les maths ça ne sert à rien ».
Mettez-vous au travail de la matière la plus importante de toutes les matières.
Rédigé par Mr. Bachir Jean EL HAGE
Université Joseph Fourier – INPG
Grenoble 1 - FRANCE
www.bachosdesign.com