Bacho's Design - Your best online school - E learning Lebanon  (Liban)     
  Bachir Jean EL HAGE - E-Learning Math Lebanon (Liban)  

Traitement dimages

Rdig par Mr. Bachir Jean EL HAGE

Universit Joseph Fourier INPG

Grenoble 1 - FRANCE

A.   Introduction

Dans les coles, lyces et mme aux seins des tablissements universitaires on se pose toujours la question suivante :

 

A quoi servent les maths ?

 

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

 

Daccord mais Mr part a ? Un mdecin na pas besoin des maths ! Un informaticien non plus !

 

Bien sr que si. Les maths sont aussi le cur de toutes les recherches scientifiques, de tout le progrs mdical et informatique. La physique bien videment se base sur les maths, lastronomie aussi, la scurit des systme 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, amliorer la qualit dune image pixlise ou mal scann ou floute.

 

Vous savez aussi que la police possde des logiciels de reconnaissance faciale qui arrive reconnaitre un visage avec un minimum de donnes. Grace une photo de basse qualit prise avec une camra de surveillance on arrive quand mme 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 grce aux mathmatiques ? Aux polynmes, fonctions, drives premire et drive seconde, sinus, cosinus, tangentes,  ?

 

Je vais tenter de vous expliquer dans la suite de ce document comment intervient les mathmatiques dans le traitement dimages tout en vous proposant thorie et exemples raliss sous Matlab pour une comprhension optimale du sujet propos.

 

B.   Interpolation et approximation (dfinitions et exemples)

1.    Gnralit

En analyse numrique l'interpolation est une opration mathmatique permettant de construire une courbe partir de la donne d'un nombre fini de points, ou une fonction partir de la donne d'un nombre fini de valeurs. La solution du problme d'interpolation passe par les points prescrits, et, suivant le type d'interpolation, il lui est demand de vrifier des proprits supplmentaires.

Linterpolant est gnralement construit de lunique fonction scrivant sous la forme :

Exemple dinterpolation par Spline :

Nombre fini de points distribu alatoirement :

Aprs interpolation (par Spline) :

 

2.     Problme

Ayant un nombre fini de points on cherche dterminer une fonction passant par ses points qui soit facile valuer. Le problme cest quil existe une infinit de solutions !

Ce quil faut alors faire cest de se restreindre une famille de fonctions : exponentielle, polynmes, fonctions trigonomtriques,

 

3.    Interpolation linaire

 

Le type le plus simple d'interpolation est l'interpolation linaire, qui consiste joindre les points donns. Elle peut servir estimer les valeurs situes entre les donnes de la table.

 

Par exemple, si nous souhaitons dterminer 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 consquent

f(2,5)=\frac{0,9093+0,1411}{2}=0,5252

Plus gnralement, la droite d'interpolation aura pour quation (trois formulations quivalentes) :

 f(x) = \frac{y_a-y_b}{x_a-x_b} x + \frac{x_a.y_b-x_b.y_a}{x_a-x_b}

Ou bien (formule de Taylor-Young au premier ordre) :

 f(x) = y_a + (x-x_a) \frac{y_b-y_a}{x_b-x_a}

Ou bien :

 f(x) = \frac{x_b-x}{x_b-x_a} y_a + \frac{x-x_a}{x_b-x_a} y_b

Cette dernire formule correspond la moyenne pondre.

Les points rouges correspondent aux points (), et la courbe bleue reprsente la fonction d'interpolation, compose de segments de droite.

Cette mthode est rapide et aise mais elle manque de prcision. Elle prsente aussi linconvnient de ne pas tre drivable au point .

L'erreur d'estimation montre que l'interpolation linaire n'est pas trs prcise. Si la fonction que l'on souhaite interpoler est deux fois continument drivable et si alors l'erreur d'interpolation est donne par :

En d'autres termes, l'erreur est proportionnelle au carr de la distance entre les nuds.

D'autres mthodes d'interpolation permettent d'obtenir des fonctions d'interpolation plus lisses, par exemple, l'interpolation polynomiale

4.    Interpolation polynomiale de type Lagrange

 

Thorme

Soient points distincts rels et rels , il existe un unique polynme tel que pour .

 

Construction du polynme :

 

tant le polynme de Lagrange et est dfinie par :

 

 

Proprit de :

 

Exemple dapplication

 

Soit trouver le polynme interpolant les 3 points suivants 

 

(0 ; 1) , (2 ; 5) et (4 ; 17)

 

Les polynmes de Lagrange associs sont


Calculons alors le polynme dinterpolation

 

Lalgorithme et le rsultat de lexemple 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

pol.JPG

 

Linterpolation polynomiale est facile comprendre et programmer, elle donne en plus des bons rsultats avec une erreur minimale.

 

 

5.     Approximation et courbes de Bzier

 

L'interpolation doit tre distingue de l'approximation de fonction, qui consiste chercher la fonction la plus proche possible, selon certains critres, d'une fonction donne. Les courbes de Bziers sont un exemple dapproximation :

 

 

Dans le cas de l'approximation, il n'est en gnral plus impos de passer exactement par les points donns initialement. Ceci permet de mieux prendre en compte le cas des erreurs de mesure, et c'est ainsi que l'exploitation de donnes exprimentales pour la recherche de lois empiriques relve plus souvent de la rgression linaire, ou plus gnralement de la mthode des moindres carrs.

Aprs lexplication thorique de linterpolation et de la manire dont on trouve le polynme ou la fonction ou la courbe interpolant un nombre fini de points, nous allons passer tout de suite son utilit dans le traitement dimages !

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 rsolution d'image.

 

L'interpolation est un procd d'estimation de valeur entre deux informations prexistantes. Il est utilis dans les scanners, les appareils numriques et les logiciels d'dition d'images afin de produire une image avec une rsolution (le nombre de pixels verticaux et horizontaux) plus grande que celle capture 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 mcanisme d'une simple interpolation. Notez que dans une interpolation relle des pixels de couleur, ceux-ci serait de couleur identique celle des originaux environnants.

 

Il existe diffrentes mthodes pour interpoler une image: Linaire, Bilinaire, Bicubique et Fractale. Toutes tentent d'augmenter la taille de l'image tout en limitant au maximum les effets d'un tel processus.

Gnralement, le problme majeur avec l'interpolation est qu'elle peut augmenter fortement un dfaut de l'image en l'agrandissant. L'interpolation Bicubique est habituellement considre comme la meilleure mthode, mais pourtant, il arrive qu'elle ne produise pas les meilleurs rsultats.

L'interpolation fonctionne le mieux lorsqu'elle est applique petite dose et sur une grande quantit d'informations. Une image constitue d'une faible quantit de pixels montrera plus de trace de dgradation qu'une image plus riche au dpart. Dans tous les cas, l'interpolation n'inventera pas des dtails qui ne se trouvaient pas dans l'image originale.

1.     Utilit de linterpolation

En terme informatique, linterpolation est un procd qui permet d'augmenter la rsolution d'une image numrise en dfinissant des pixels intermdiaires entre des pixels rels grce un algorithme mathmatique, en calculant la moyenne des couleurs des pixels avoisinants. Cette technologie permet donc d'obtenir des rsultats intressants.

Toshiba a dvelopp une nouvelle technique de super-rsolution pour la cration de haute rsolution dimages ou vido partir de ceux faible rsolution.

Si une partie de l'image est agrandie, la dgradation de la qualit d'image et l'image reste incertain, mme si l'interpolation est effectue en douceur entre les pixels.

2.     Quelques rsultats intressants crs sous Matlab :

Avec une bonne connaissance de Matlab on arrive crer son propre logiciel capable de faire un zoom sur les images en gardant une bonne qualit, de crer des surfaces en 3D colories en utilisant des fonctions mathmatiques telles le sinus, le cosinus ou lexponentielle. Dutiliser linterpolation pour fusionner les couleurs,

bachos.jpg

 

Jeux de cosinus, sinus, etc. :

Linterpolation permet aussi de corriger le flou dune image 

En travaillant sur la direction du flou et sur des caractristiques de la vitesse on peut utiliser lespace de Fourier pour avoir le rsultat suivant :

 

bougeFlou.jpg

bougeCorrection.jpg

 

Etes-vous toujours convaincu que les Maths ne servent rien ?

 

D.   Dtection des contours

Le but de la dtection de contours est de reprer les points d'une image numrique qui correspondent un changement brutal de l'intensit lumineuse. Ces changements de proprits de l'image traduisent en gnral des vnements importants ou des changements dans les proprits du monde. Ils incluent des discontinuits dans la profondeur, dans l'orientation d'une surface, dans les proprits d'un matriau et dans l'clairage d'une scne. La dtection de contour est un champ de la recherche qui appartient au traitement d'image et la vision par ordinateur, particulirement dans le domaine de l'extraction de caractristiques.

La dtection des contours d'une image rduit de manire significative la quantit de donnes et limine les informations qu'on peut juger moins pertinentes, tout en prservant les proprits structurelles importantes de l'image. Il existe un grand nombre de mthodes de dtection de l'image mais la plupart d'entre elles peuvent tre regroupes en deux catgories. La premire recherche les extremums de la drive premire, en gnral les maximums locaux de l'intensit du gradient. La seconde recherche les annulations de la drive seconde, en gnral les annulations du laplacien ou d'une expression diffrentielle non-linaire.

Il existe plusieurs model pour la dtection des contours :

Quelques modles de contours. Le plus utilis est celui en marche descalier.

Un contour est caractris par un changement brutal de la valeur. Le but de l'opration 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 dcrites 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 drive premire. Cet extremum peut aussi s'interprter comme un zro de la drive seconde.

Dans une image numrise, chaque pixel est associe une valeur qui est en gnral diffrente de la valeur des pixels voisins. La notion de drive correspondant une variation infiniment petite doit donc tre remplace par l'approximation diffrence finie utilise en calcul numrique. Le problme est simplifi car on ne s'intresse ici qu'aux comparaisons entre drives indpendamment de leurs valeurs. Ainsi la drive premire au niveau d'un pixel se rduit la diffrence entre les valeurs des deux pixels voisins, la drive seconde tant la diffrence entre les drives moyennes aux frontires des pixels.

La dtection de contour est trs utile en traitement d'images, c'est par exemple une tape indispensable la reconnaissance de formes. Ces algorithmes sont galement utiliss en imagerie mdicale, cartographies, ...

La dtection des contours de Marr / Hildreth

La dtection des contours de Marr / Hildreth est base sur les passages par zro du Laplacien de l'oprateur gaussien appliqu l'image pour diffrentes valeurs de sigma, l'cart-type de la gaussienne. Ce qui donne une mosaque de passages zro pour quatre choix de Sigma calcul en utilisant la bote outils de traitement d'image Matlab.

 

Exemple dtection des contours de limage suivante  (programm avec Matlab):

Rsultat de la dtection utilisant le Filtre de Canny ( gauche) puis Marr/Hildreth ( droite)

 

log.jpg

canny.jpg

Haut : gauche est sigma = 1, droite est sigma = 2, Bas : gauche est sigma = 3, droite est sigma = 4.

(Matlab Laplacian of Gaussian la dtection de contour slectionne normalement un seuil, afin que seuls les passages par zro de la force suffisante soient affichs. Ici, le seuil est forc zro afin que tous les passages par zro sont rapports, comme c'est requis par thorie de dtection de pointe de Marr / Hildreth.)

Nous ne rentrerons pas dans les dtails des formules mathmatiques utilises par ces procds. Nous nous contenterons des rsultats trouvs et de leur utilit.

 

 

 

Domaine dapplication

En astrologie par exemple, on dsire partir dun clich pris par un tlescope, pouvoir dtecter de nouveaux corps clestes. Par ailleurs, en imagerie mdicale, il est important de pouvoir dceler des tumeurs cancreuses, partir dune scanographie. Dans lexemple qui suit, nous prsenterons une des nombreuses mthodes de dtection utilises en reconnaissance faciale et en imagerie satellite.

Des chercheurs allemands ont dvelopp une nouvelle technologie d'analyse faciale rapide.

Elle permet d'identifier un visage humain sur une photo (ce que Google Images fait dj), et est capable de diffrencier un visage d'homme ou de femme, et d'analyser l'expression du visage (content / triste, etc...).

E.    Codage d'une image, reprsentation spatiale

Une image est considre comme un ensemble de points ou pixels (picture element), associs au quadrillage rectangulaire de l'image d'origine. La reprsentation d'une image se fait donc par l'intermdiaire d'une matrice d'entiers cods entre 0 et 255. Les images en niveau de gris sont reprsentes par des matrices 2D, les images couleurs reprsents par 3 composantes (Rouge, Vert, Bleu) sont reprsentes par des matrices 3D. On accde un pixel grce a son indice de ligne et son indice de colonne. Le premier pixel d'une image est le pixel en haut gauche. Cette reprsentation est appel reprsentation spatiale de l'image.

Dans un prochain projet jexpliciterais aussi le domaine de la cryptographie et lutilit des mathmatique dans les systmes bancaire et tous les programmes travaillant sur la scurit de linformation.

F.    Conclusion

Jespre vous avoir donn ne serait-ce quune petite ide sur lutilit des mathmatiques. Vous navez dsormais plus le droit de dire  les maths a ne sert rien .

Mettez-vous au travail de la matire la plus importante de toutes les matires.

 

 

Rdig par Mr. Bachir Jean EL HAGE

Universit Joseph Fourier INPG

Grenoble 1 - FRANCE

contact@bachosdesign.com

www.bachosdesign.com

 

Bacho's design - Votre site Educatif en ligne par Bachir Jean EL HAGE

Statistiques du Site

Membres et messages

Nous avons 524 membres enregistrés.
Le dernier inscrit est mbaitibetfils3.
Nos membres ont posté messages.

Statistiques d'accès

  • 3384119 pages vues
  • En ce moment : 2 visiteurs connectés


did you like this website?



Bacho's Design web statistics for math education

Partenaires: (echange de lien? m'ecrire)

Recherchez Ici

  Annuaire généraliste

E-Learning Maths & Info - Liban par Bachir Jean EL HAGE Google   Google+     ISN Services Copyright 2008