méthode d`agrandissement d`une région d`une image
Contents
1. Agrandissement x2 et filtre de Gauss Effet de flou 28 Entr es sorties L application peut charger des images au formats ppm et png en m moire avoir acc s au diff rentes donn es concernant l image telles que la largeur la hauteur la repr sentation de couleurs et bien s r les valeurs correspondant chaque pixel composantes transpa rence Aussi il est possible d crire un fichier image partir des donn es en m moire Extraction de l objet L application sait op rer un suivi de contour selon une ou plusieurs tiquettes situ es dans un fichier tiquette au format ppm ou png De cette exctraction de contours on obtient un code de Freeman et un point de d part pour chaque tiquette Cela permet alors d isoler le contenu de l objet afin de l agrandir et aussi de cr er un chemin euclidien afin d agrandir le contour discret obtenu Agrandissement du contenu de l objet L application agrandit le contenu de l objet l aide du filtre pass en param tre Mit chell si aucun n est sp cifi L objet est interpol de quelques pixels sur les bords afin d viter l utilisation de mauvaises donn ees hors objet par le filtre Le facteur d agran dissement est bas sur un nombre r el qui doit tre sup rieur 1 Cr ation et agrandissement du chemin euclidien Le chemin euclidien est correctement calcul partir de contour discret extrait au paravant Il est ensuite possible de l agrand2. Bartlett Contrairement au filtre bo te le filtre de BARTLETT conserve plus hautes fr quences et de ce fait plus de d tails dans l image cependant certaines basses fr quences utiles sont supprim es Il d fini par une fonction de transfert B spline La transform e B spline fournit une repr sentation continue d un signal discret Plus simplement il s agit d une courbe lisse qui traverse deux points sp cifiques ou plus L in terpolation par les fonctions splines sont souvent pr f r es aux interpolations lin aires car le taux d erreur y est moindre 1 4 FIG 1 4 Approximation par une fonction spline de segments discrets La transform e B spline poss de de bonnes propri t s de lissage et la modification d un point du polygone n entraine qu une modification locale de la courbe obtenue Approximation par une fonction spline de segments discrets Median Une interpolation m diane est une interpolation non lin aire produisant comme r sultat le m dian des valeurs trait es L id e est simple prenons un ensemble de pixels au voisinage d un pixel donn et rangeons les niveaux de gris de cet ensemble de pixels en ordre croissant puis choisissons le niveau de gris qui arrive en position m diane Ce niveau de gris sera celui du pixel donn Exemple Si la liste des niveaux de gris d un pixel est 64 64 64 64 255 255 64 64 255 La liste dans l ordre croissant est alors 64 64 64 64 64 6
3. Point euclidien Il existe plusieurs m thodes permettant de g n rer un chemin euclidien toutes assurant la r versibilit Nous utilisons les chemins euclidiens dirig par la tangente cette m thode impos e par notre client est de toute fa on la plus appropri e car elle ne d pend ni du point de d part ni du sens de parcours du contour et reste peu co teuse Aussi l utilisateur n a pas besoin de sp cifier la longueur du voisinage celle ci d pendant uniquement du contour 19 Chemin euclidien dirig par la tangente Longueur du voisinage d termin par le motif du contour Pour chaque point discret Pi du contour on cherche d abord le segment de droite discr te Le plus long centr en Pi Le calcul de la tangente discr te d duite ne d pend alors que de lui m me et de son voisinage partir de cette tangente discr te on peut approximer une tangente r elle qui nous donnera alors le point euclidien La construction du chemin euclidien sera donc bien ind pendante du point de d part et du sens de parcours Le nouveau contour tant constitu de points euclidiens on est assur que l on peut retrouver le contour discret initial Les deux caract ristiques pr sent es au d but sont donc bien respect es Bilan Un contour continu tel que les courbes splines augmente le risque d oscillations ou bien devient tr s co teux alors que la polygonalisation fait appara tre des points angu leux et peut d pendre du
4. e aa a e a a RARAS 12 Exemple de d tection des contours 15 M thode de la Cordel man mate Ge E lies 16 Reconnaissance de droite discrete 17 Point anguleux stes SEL MS SC des si A Das Me Lune dd 17 Importance du point de d part 17 Courbe de B zier lt a aa a 19 EE EE 19 Point eclesial la Ss Lu s 19 Contour discret et euclidien sur l oeil de Lenna 21 Diagramme de fonctionnement 1 22 Diagramme de fonctionnement A ire ado adora 23 Structure un fichier ppm a E R O e RER RON 25 e TEEN EE 26 Agrandissement x2 au plus proche voisin Pixellisation 27 Agrandissement x2 et filtre de Gauss Effet de flou 28 e a a a a ala iio 31 Exemple de fonctionnement 32 EC eg pis iio e a a a e RS a eSa tu 33 Fichier etiquette E aa a 34 Objet agrandi on remarque le lissage sur les bords de la coque du bateau 35 Architecture s te e era a a a ad E Ee a E i SCC 37 Lerouleme t sra drames de a aa A A aa a a 38 Suivi du contour et codage de Freeman 41 Contour discret et chemin euclidien 41 Aire de recouvrement du domaine euclidien d un pixel 43 Aire de recouvrement du domaine euclidien sur quatre pixels 43 Aire de recouvrement d une cellule 44 Comparaison des r sultats du calcul du che
5. es afin d y acc der facilement code Le pointeur sur caract re code contient le code de Freeman relatif au contour de notre objet tout simplement une suite compos e de valeurs 0 droite 1 haut 2 gauche ou 3 bas 4 1 3 ContourLisse ContourLisse contient les coordonn es de notre contour discret sous forme r elle ceci avant et apr s son agrandissement nb_points De la m me mani re que ContourDiscret contenait le nombre de d placements contenus dans code ContourLisse contient le nombre de points du contour lisse ceci afin de faciliter le parcours de ces points points Points est un pointeur sur r el float qui contient la liste des points coordonn es r elles du contour 4 1 4 filter h et pnm h Les fichiers filter h et pnm h nous ont t fournis par notre client Le premier contient un certain nombre de filtres de reconstruction utilis s lors de l agrandissement d images Ils nous a donc suffit de reprendre ce fichier afin de l int grer notre programme et proposer notre tour l utilisation de ces diff rents filtres Quant au second il permet de manipuler les fichiers au format pnm lecture criture et modification Nous avons donc fait le lien entre ces fonctions relatives un format de fichier et TabPixel qui lui est ind pendant du format 40 i 1 j 1 G j 1 i 1 j G D 3 FIG 4 1 Suivi du contour et codage de Freeman Did I
6. I I I a I I I I e Ms Dios FIG 4 2 Contour discret et chemin euclidien 4 2 Algorithmes et techniques 4 2 1 Suivi de contour La technique employ e pour le suivi de contour n implique pas un grand nombre de calcul et ne comporte fondamentalement que quatres cas traiter Ainsi apr s avoir initialis notre structure TabPixel repr sentant le fichier tiquette on parcourt les pixels en commen ant par celui situ le plus en haut gauche coordonn es 0 0 il contient la couleur du fond Puis cela ligne par ligne nous nous arr tons lorsque l on rencontre un pixel de couleur diff rente de celle du fond C est alors que nous avons trouv le premier pixel de notre tiquette Par convention on choisit de suivre notre contour dans le sens trigonom trique 41 Le code de Freeman du contour discret figure 4 2 ayant comme point de d part le point le plus en haut gauche est le suivant 3 2 3 2 3 3 0 gt 3 0 gt 3 0 gt 170 gt 0 gt 170 gt 0 gt 1f2 172 LE E Il nous suffit alors de comparer les couleurs des pixels voisins et d ajouter la valeur codant le d placement en cas de couleur diff rente 4 2 2 Chemins euclidiens Voir page 19 et document 4 2 3 Filtre de Mitchell 4 2 4 Antialiasing On souhaite antialiaser les bords de la r gion extraite agrandi avant la composition de l objet sur un fond Le canal alpha est un 4 me canal RGB qui permet de stocker la transparence de chacun des
7. complication et pourrait tre trait lors d une eventuelle extension du programme 6 2 3 Fichier image de format inconnu et facteur d agrandisse ment inf rieur 1 L utilisation d un facteur d agrandissement inf rieur 1 fait appel au module de gestion d erreurs fourni par notre client Ainsi un message pr cisant que le facteur doit tre sup rieur 1 apparait figure 6 2 47 6 3 Tests de validation 6 3 1 Fiabilit Notre logiciel peut tre consid r comme fiable car en suivant la chane de traitement de bout en bout comme illustr dans le d roulement Fig 42 il est capabe de restituer fid lement toutes les diff rentes carat ristiques de l image source Cette v rification est bas e sur le r sulat visuel de l agrandissement d une image donn e en entr e 6 3 2 Rapidit Nous nous sommes fix s comme moyenne en temps de r ponse la seconde Toutefois un agrandissement d image peut prendre un temps un peu plus long selon les param tres d entr e nous restons n anmoins dans l ordre fix Aussi compte tenu de la contrainte inh rente au temps de r ponse nous n avons utilis que des algorithmes de complexit lin aire 6 3 3 Complexit finale Comme vu auparavant la complexit des trois principaux algorithmes employ s lors du traitement des images est reconnue lin aire Leur utilisation s quentielle est donc aussi de complexit lin aire 48 Chapitre 7 R capitulatif et
8. des images et la rapidit de leur traitement en liminant les phases de d veloppement et de num risation Ces exemples montrent que l agrandissement des images est un domaine qui touche des secteurs vari s sans cesse la recherche de nouvelles m thodes plus performantes et d am liorations 1 2 Analyse de l existant L agrandissement d images num riques est une op ration utile et n cessaire Agrandir une image permet d am liorer le confort visuel de celui qui la regarde d augmenter sa r solution ou encore sa taille En bref l agrandissement d une image permet l acc s ses d tails Aussi selon l approche que l on adopte par rapport l image tudier le contexte d tude le syst me d acquisition etc et des connaissances que l on a sur celle ci en niveau de gris couleur 2D etc il existe plusieurs techniques permettant son agrandis sement Leur tude et leur recensement font l objet de notre analyse de l existant 1 2 1 Repr sentation d une image R f rence 7 Domaine spatial Une image peut tre repr sent e comme une variation d intensit dans l espace On se r fere alors aux signaux dans le domaine spatial et l image peut tre d finie parune fonction f x y qui donne la valeur de l intensit en fonction des coordonn es x y d un point donn Domaine spectral Une image peut aussi tre repr sent e dans le domaine fr quentiel Celui ci est tres compl ment
9. du sein avec une loupe pour faire un meilleur diagnostique Dans le domaine de la photographie il existe maintenant un zoom num rique qui consiste recadrer et agrandir l image obtenue par le capteur optique gr ce une m thode num rique d agrandissement Actuellement le zoom num rique produit des clich s d une qualit insuffisante par rapport ceux pris en utilisant uniquement le zoom optique Une autre application possible est l agrandissement d une photo apr es la prise de celle ci Actuellement les appareils photos num riques ont nettement moins de ressources alors le clich pris en utilisant le zoom optique peut tre agrandi en utilisant un ordinateur pour obtenir une meilleure qualit En g ographie des satellites sont actuellement utilis s pour prendre des photos de la surface terrestre La communication entre les laboratoires et ces derniers tant peu rapide les photographies sont envoy es en petit format et agrandies num riquement par la suite Dans le domaine de la cartographie depuis 1993 l IGN Institut G ographique National ol utilise des avions sp cialement quip s de cam ras num riques pour la prise de vue a rienne dans le but d laboration de cartes Cette flotte survole des terrains pr cis une hauteur de 4800 m afin de photographier tout le terrain Les clich s pris peuvent par la suite tre agrandis Le passage l imagerie num rique a am lior la dynamique la disponibilit
10. effet dot de sa couleur RGB mais aussi d un canal alpha qui sert ajouter divers niveaux de transparence la couleur Le traitement de l image se d roulera de la mani re suivante Suivi du contour de l objet facilit ici par l tiquette de l image Construction du contour liss puis agrandissement de ce contour Discr tisation du nouveau contour liss agrandi Reconstruction du nouvel objet agrandi avec son nouveau contour Incrustation de l objet sur un fond ou un autre objet Enfin l algorithme utilis chemins euclidiens est relativement r cent et donc encore peu utilis La th se d Anne Vialard est l unique r f rence que nous avons sur le sujet Les figures 1 15 page 22 et 1 16 page 23 illustrent le fonctionnement du projet 1 3 1 Les diff rents formats de fichiers image source 2 4 On consid re ici uniquement les formats en mode point bitmap et non les formats vectoriels qui ne nous int ressent pas dans le cadre de ce projet Gif Graphics Interchange Format Le format gif n est plus sous brevet depuis peu il permet de coder 256 couleurs l aide d une palette Il propose un algorithme de compression sans perte ainsi que le support de la transparence et des images anim es 21 Fond Objet DETECTION DE CONTOUR Contour Objet AGRANDISSEMENT SEPARE Objet agrandi Contour agrandi REASSEMBLAGE F1G 1 15 Diagramme de fonctionneme
11. fonnel d Z Le vm tt agente a ben d r paa aaia A VR Een ET em Ee erte CHE Can pa e e ad bit mag Less geg rl We P BANA bit H FS AT DER AS A PA A Ti Mr Maut FRONT mei pri CE eu b P TS Enn o Eat ehr t pre kees Seen e SKYDERS A Corpa mit MBAM 11 mere pe eme A FIG 2 3 Fichier image 33 FIG 2 4 Fichier etiquette 34 FIG 2 5 Objet agrandi on remarque le lissage sur les bords de la coque du bateau 39 Chapitre 3 Architecture et d coupage modulaire L architecture a t con ue de mani re permettre des extensions au programme Ainsi la structure TabPixel permet de faire abstraction du format de fichier utilis et m me si pour le moment nous nous sommes content s de pnm d autres formats peuvent tre ajout s facilement sans affecter le fontionnement du programme 36 TabPixel int largeur int hauteur unsigned short donnees tabPixel tabPixel_charger char chemin tabPixel tabPixel_creer int L int h unsigned short donnees int tabPixel_largeur tabPixel t int tabPixel_hauteur tabPixel t unsigned short tabPixel_donnees tabPixel t tabPixel_contenu tabPixel image tabPixel etiquette contourDiscret d tabPixel tabPixel_agrandir tabPixel t double coeff filter f tabPixel agrandir_betement tabPixel t double coeff pnm tabPixel_sauvegarder tabPixel t char chemin tabPixel_imprimer tabPixel t void tabPixel_detruire tabPixel t void tabPixel_compositi
12. ils permettent de d tecter et dessiner les ar tes pr sentes l image mais nous sommes loin d obtenir des r egions clairement d finies voir figure 1 6 Il faudrait donc ajouter un traitement suppl mentaire pour dessiner des r gions partir des ar tes ce qui est relativement complexe L autre possibilit consid rable est d utiliser un technique de segmentation d image par couleur On quadrille alors l image et on obtient un certain nombre de points de d parts qu on propage suivant les pixels voisins de couleur similaire 92 Cette extension est donc la plus cons quente mais palierait le plus gros inconv nient pour Putilisateur 93 Manuel d utilisation Notre logiciel ne prend en compte que les images couleur au format ppm et ou png Options Il s agit de d crire dans cette partie le r le et le fonctionnement de chacun des outils propos s par notre application Une fois le programme compil et ex cut la page principale s affiche DI Notre logiciel 1 0 x CL ER IS NT T a d Objets 20 r PARAMETRES Image v Voir Etiquette Actualiser y Voir Filtre utilise d Coefficient Visualisation du contour discret agrandi C oui e Non Enregistrer sous ppm C png Traitement avec Traitement sans Traitement avec regions regions regions sans antialiasing Agrandir Agrandir Agrandir FIG 7 6 Page principale Chargement et vi
13. m thode d interpolation simple qui consiste prendre la moyenne de deux valeurs Elle est rapide et ais e mais manque de pr cision Plus pr cis ment l erreur est proportionnelle au carr de la distance entre les noeuds Bilin aire Ce type d interpolation donne globalement de meilleurs r sultats que l interpolation lin aire avec quelques calculs suppl mentaires Choix des deux points les plus proches de chaque c t du point tudi puis pond ration par des coefficients inversement propot tionnels la distance et dont la somme vaut 1 1x 1y Gx 1 iy E E dolo re ei e EE Jee Ea 200 y Ey x y e ix iy 1 ix 1 iy 1 x x 1 FIG 1 2 Mise en oeuvre de l interpolation Interpolation bilin aire 181 Interpolation au plus proche voisin 200 On retrouve l interpolation bilin aire tout comme la pr c dente assez souvent dans les applications en temps r el Cependant le rendu se traduit encore par un flou visuel assez important Quadratique L interpolation ici est effectu e entre les trois points les plus proches en utilisant trois polyn mes de degr deux Par rapport aux m thodes pr c dentes l image interpol e para t moins floue Cependant l effet de pixellisation est encore visible FIG 1 3 Interpolation quadratique Cubique L interpolation cubique est le processus travers lequel on trouve un point en utilisant une moyenne pes e de huit valeurs d
14. objets Aussi on peut noter l apparition des m mes pixels blancs l int rieur de la r gion trou Le probl me des r gions trous tant assez complexe nous n avons pas eu le temps n cessaire pour le traiter correctement 7 2 Application plusieurs objets totale Initiallement ce programme traite un seul objet donc une image avec 2 tiquettes diff rentes fond et objet mais il a t tendu plusieurs r gions donc un nombre d tiquettes sup rieur 2 L tiquette du premier pixel de l image sera consid r e comme celle du fond la suivante comme la premi re r gion A la rencontre de cette derni re on traite celle ci suivi du contour extraction de l objet puis on l limine en rempla ant son tiquette avec celle du fond et on relance la recherche de nouvelles r gions jusqu ce que l on n en trouve plus Cependant les r gions trous trait es dans la section suivante et celles fronti res communes m ritent une attention particuli re Dans le cas de ces derni res un traitement adapt de la partie commune de leurs frontites doit tre fait Le premier et le dernier point ne doivent tre d finis comme tant fixes c est dire qui ne doivent pas tre d plac s par le lissage A nsi nous sommes s rs d obtenir le m me Chemin Euclidien dans les contours des deux r gions et obtenir les bons r sultats en effectuant l antialiasing 7 3 Application aux objets
15. point de d part Dans ce projet nous resterons donc sur une repr sentation de type polygonal mais en approximant chaque point au mieux de la fronti re r elle de l objet en d pla ant dans le plan euclidien les points fronti re discret et dirig selon la tangente locale 1 3 Le Projet Il existe deux grandes cat gories d images Les images vectorielles sont constitu es d entit s de formes g om triques qui sont repr sent es par des formules math matiques et qui ne posent donc aucun probl me dans tout redimensionnement tel que agrandis sement r tr cissement ou encore largissement L autre type d image est l image dite bitmap Les informations sont stock es dans une matrice qui associe chacun des pixels sa couleur RGB Ici on consid rera ce deuxi me type d image non compress et sans perte d informations comme l est par exemple JPEG On se restreindra aux formats ppm et png Dans ce projet on etudiera des images simples form es de une ou plusieurs formes sur un fond initial Notre travail sera simplifi par l utilisation d images avec etiquette c est dire que chaque pixel de l image sera etiquett de fa on savoir quel objet il appartient qui permettra ainsi le suivi des contours de mani re relativement ais e L agrandissement d une image de largeur L et de hauteur H en une image plus grande de nouvelle largeur L et de nouvelle hauteur H impose de devoir calculer les couleurs d
16. se termine par le point PN mais ne passe pas a priori par les autres points de contr le qui d terminent cependant l allure g n rale de la courbe Les courbes de B zier cubique de degr 3 et d finies par ses points de contr le PO P1 P2 P3 sont les plus utilis es Sa forme param trique est B t Pal t 3Pit 1 t 3Pot 1 t Pst t 0 1 B splines B Spline d signe une courbe continue polynomiale par morceaux Une courbe B Spline est constitu e d une cha ne continue de courbes de B zier du m me degr 3 connect s entre elles Chaque courbe est tangente aux autres en ses points de d but et fin Un exemple de B Spline o les Pi sont les points de contr les Ceci dit l ensemble des points de contr le tant important on est confront de fortes oscillations qui pourraient tre evit es en augmentant fortement le degr des polyn mes Et cela devient assez co teux 18 p4 pl FIG 1 11 Courbe de B zier P3 o P2 e e P8 P7 e P1 e Ple FIG 1 12 Courbe spline Les chemins euclidiens Le probl me de r versibilit nous impose que le nouveau point du contour interpol ne doit pas d passer un demi pixel de facon retrouver le contour discret initial On a autant de points initiaux que de points euclidiens Point euclidien le point approxime m y doit rester dans ce plan KE Point discret de contour Cellule du point de contour FIG 1 13
17. 4 255 255 255 et la valeur du pixel devient donc la 5 i me valeur de la liste soit 64 L avantage du filtre m dian r side dans la simplicit de sa mise en oeuvre et dans le temps de calcul relativement faible Il pr serve mieux la nettet que les filtres lin aires 11 10 SA 19 38 Ue 75 00 136 36 Valeur Bee 38 m diane Eet 149 10 49 a 75 19 98 22 98 99 FIG 1 5 Filtre median mais a tendance d former les structures pr sentes dans l image puisque celles ci ne sont pas analys es Wiener L utilisation d un filtre de Wiener n cessite un apprentissage pr alable pour valuer ses poids Celui ci consiste partir d une image originale et de sa version r duite optimiser les poids du filtre d interpolation afi n de minimiser l erreur entre l image originale et l image interpol e d apr s la version r duite Il s agit en fait d un probl me classique de minimisation par les moindres carr s La qualit de l interpolation avec un filtre de Wiener va d pendre du couple d images utilis pour calculer ses poids En g n ral il est pr f rable de prendre comme couple d images l image originale que l on veut agrandir et sa version r duite L interpolation avec le filtre de Wiener donne un r sultat correct lorsque l image interpoler a des caract ristiques tr s simples Ce type de filtre produit des r sultats sensiblem
18. 5 255 255 255 255 255 255 0 0 0 255 0 0 0 255 255 255 255 y eebe Pixel Pixel Pixel Pixel rouge vert bleu HON FIG 1 17 Structure d un fichier ppm On peut aussi se servir des pixels voisins et en faire une moyenne pour trouver la valeur du nouveau pixel Cela a un inconv nient qui est de donner un aspect flou a l image ce qui est tout de m me moins g enant qu un aspect pixellis Cet effet de flou vient du fait que pr s d un contour le filtre peut baser son calcul de la valeur du nouveau pixel sur des voisins qui appartiennent une autre r gion Cela a pour effet de donner des valeurs qui sont des moyennes entre deux r gions et donc de ne pas pr server la nettet Nous souhaitons donc palier ces d fauts c est dire reconstruire une zone sans que celle ci se pixellise mais aussi pr server des contours bien nets Or nous savons parfaite ment reconstruire une zone unie ou d grad e sans changement brusque de couleur Nous pouvons m me appliquer par la suite un filtre de lissage sur son contour pour un r sultat encore am lior L id e est donc de ne pas appliquer le traitement sur l image en sa globalit mais de la d couper en autant de r gions objets relativement uniformes que n cessaire et traiter ces r gions une par une avant de les r assembler Cependant pour d buter notre approche consistera agrandir uniquement un objet de l image 1 5 Besoins non fonctionnels Complexit Nous d
19. 6 6 1 3 Agrandissement uo a MN CNRS D 46 6 2 Tests d TODUSTOSSO 4 eri ye din AA D 2 Aa Mau fe L et 47 6 2 1 Facteur d agrandissement maximal 47 6 2 2 Objet de forme peu commune 47 6 2 3 Fichier image de format inconnu et facteur d agrandissement inf rieur de ls A N S css Y 47 6 3 Tests de validation Au ki s as e aa e e e e de 48 EE e SA A A iS a ets 48 6 3 2 Rapidite LE 5 6 ad Daube Lau e e ter ee SA 48 Dia Complexit finale e Se s i ce ri na e OS y e tr sl 48 7 R capitulatif et extensions possibles A9 TE Trava xactomplis e hise e e cl ege a et 49 7 2 Application plusieurs objets totale 51 7 3 Application aux objets trous A Aa Re 51 7 4 Application aux objets situ s sur le bord de l image 52 7 5 V ritable d tection de contours permettant de s affranchir de l tiquetage 52 Bibliographie 57 Table des figures 1 1 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 1 10 1 11 1 12 1 13 1 14 1 15 1 16 1 17 1 18 1 19 1 20 2 1 202 2 3 2 4 2 5 3 1 3 2 4 1 4 2 4 3 4 4 4 5 6 1 6 2 Signal dans le domaine spatial et son spectre droite 8 Mise en oeuvre de l interpolation Interpolation bilin aire 181 Interpola tion au plus proche voisin 200 rm anses A et e 9 Interpolation quadratique 2 4 ces a AM E 10 Approximation par une fonction spline de segments discrets 11 Filtre median
20. S IN E T A pos E d biets 20 Norbert Matthias Yana Sabrina KOUANDOU LARCHER POPOVA WONS Charg s de TD Pascal DESBARATS Anne VIALARD Client Achille BRAQUELAIRE April 7 2006 R sum Les images num riques 2D issues d chantillonage de donn es r elles pr sentent des d fauts de cr nelage L application d un filtre d agrandissement sur de telles images sans traitement distinct des r gions rend les fronti res ind sirablement floues ou crenel es Afin de pr server leur nettet durant le redimensionnement on agrandit s par ment les r gions objets en gardant la meilleure approximation possible de la fronti re r elle Le d faut de flou apparaissant l int rieur des objets n est non seulement plus un probl me mais permet m me d obtenir un meilleur r sultat puisqu ils sont constitu s de d grad s de couleurs Nous consid rons ici le cas d images pr alablement segment es avec des fronti res bien nettes accompagn es de leurs etiquettes La segmentation de l image permet le suivi du contour discret des objets traiter La construction d un chemin euclidien dirig par la tangente sur ce contour approxime au mieux la fronti re r elle ce qui att nue d une part l effet d escalier ou de flou en gendr apr s agrandissement et d autre part permet le calcul du canal alpha utilis dans Pantialiasing lors de l incrustation de l objet sur un fond Au final cette application permet d a
21. aire du domaine spatial et pr sente une image comme un ensemble de si nusoides de fr quences diff rentes ayant chacune une amplitude et un d calage de phase particuliers Le passage du domaine spatial au domaine spectral se fait par l interm diaire de la transform e de Fourier gt D FIG 1 1 Signal dans le domaine spatial et son spectre droite Transform e de Fourier La transform e de Fourier est utilis e pour transformer un signal du domaine spatial en un spectre du domaine fr quentiel Inversement on peut aussi ajouter les sinuso des entre elles afin de reconstituer une repr sentation spatiale de l image c est la transform e inverse de Fourier Figure On remarque que la transform e de l image du babouin est plus claire que celle de Lena ce qui traduit une pr sence plus importante de hautes fr quences Echantillonage L chantillonnage consiste transformer un signal continu en signal discret en captu rant des valeurs intervalle de temps r gulier C est une tape n cessaire pour pouvoir enregistrer analyser et traiter un signal par ordinateur car celui ci ne peut traiter que des nombres Si la fr quence d chantillonnage est tr s faible les acquisitions seront tr s espac es et de ce fait si le signal original comporte des d tails entre deux positions de capture ils ne seront pas enregistr s C est pour cela que la fr quence d chantillonnage doit tre b
22. antialiasing Agrandir Sans regions Visualiser FIG 7 13 Choix du type d agrandissement 96 Bibliographie 1 http homepages inf ed ac uk rbf HIPR2 featops htm Features de tector 2005 2 http www bibl ulaval ca vitrine giri mod1 1_4 htm Principaux formats de fichiers 3 http www cse nd edu kwb HeathSarkarSanockiBowyerPAMI_1997 pdf A Robust Visual Method for Assessing the Relative Performance of Edge Detection Algorithms 2005 4 http www ext upmc fr urfist image_numerique format htm Format d image 5 http www gpa etsmtl ca cours sys844 Documents Chapitre4 padf D tection des ar tes d une image 2005 http www ign fr Site officiel IGN 2005 7 Fanny Chevalier Eric Hany Gamou Seck Sidiki Tall Traitement d images agrandissement par r gions 2003 8 J P Braquelaire and A Vialard Euclidean paths A new representation of boundary of discrete regions 1995 97
23. de contour Pi 42 Chemin euclidien Aire de recouvrement FIG 4 3 Aire de recouvrement du domaine euclidien d un pixel cellule contour pixel 1 pixel 3 FIG 4 4 Aire de recouvrement du domaine euclidien sur quatre pixels 43 FIG 4 5 Aire de recouvrement d une cellule Pour chaque point Pi du contour discret on doit donc calculer l aire engendr e par les points euclidiens pi pi 1 et pi 1 Pour cela on utilise une m thode de sur chantillonage de la cellule contour On a utilis une r solution de 8 8 qui parait assez satisfaisante tant donn que l on traite des pixels Ainsi on obtient alpha en comptant le nombre de sous cellules qui appartiennent au domaine euclidien A4 Chapitre 5 Complexit des principaux algorithmes 5 1 Chemins Euclidiens Voir document 8 5 2 Antialiasing D abord on fait un parcours du contour discret qui construira une structure de donn es permettant alors de savoir si un pixel x appartient ou non l objet discret de fa on tr s rapide LI algorithme traite tous les points du contour discret pour lesquels il construit la grille subdivis e de la cellule Il doit ensuite trouver quelle partie de la grille appartient au domaine euclidien Puis il ne lui reste plus qu compter les cases de cette partie Tous les a
24. econna tre les droites discr tels A partir d un point initial tant que le segment est un segment de droite discr te on parcours le chemin en rajoutant le point visit Lorsque ce point ne permet plus d tendre le segment On recommence le processus partir du dernier point La vectorisation sera donc bas sur les extr mit s de tous les segments de droite trouv s Une droite discr te L et l ensemble despoints x y de Z qui satisfait la double in galit suivante u lt Ax By lt u wavecA B u E Z w N 16 Segment retenu Fin de la reconnaissance x Points conserves pour la vectorisation Debut de la reconnaissance FIG 1 8 Reconnaissance de droite discrete Inconv nients Mais de telles m thodes peuvent faire apparatre des points anguleux FIG 1 9 Point anguleux Aussi elles peuvent d pendre du pixel de d part pour effectuer la polygonalisation First point IS e FIG 1 10 Importance du point de d part Il est clair dans cet exemple que changer de point de d part modifiera l orientation de ce polygone 17 Perte d informations si on ne retient qu un sous ensemble de points pour la vectori sation on ne pourra pas retrouver le chemin discret initial Les courbes polynomiales Pour viter les probl mes de points anguleux et de d pendance du point de d part li s l iterpolation
25. eilleure approximation possible de la fronti re r elle ce nouveau contour devra satisfaire les deux caract ristiques suivantes La construction de ce contour doit tre ind pendante du point de d part et du sens de parcours L algorithme doit tre sans perte d informations c est dire r versible partir du nouveau contour on doit pouvoir r cup rer le contour initial en le rediscr tisant Il existe plusieurs m thodes permettant ce lissage La vectorisation C est un proc d qui recherche partir du contour discret de l objet trait une repr sentation polygonale suite de segments de droite Ce nombre de segments doit tre minimal tout en gardant une bonne approximation des caract ristiques de la fronti re M thode de la corde L algorithme propos par V Ramer consiste substituer len semble des points par un ensemble de segments garantissant la distance minimale entre ceux ci et les points On approxime l ensemble des points par un segment Si la distance entre le segment et le point le plus loign est sup rieur un seuil donn ce point de vient un point de rupture Le processus recommence en consid rant les deux ensembles de points ainsi constitu s 2 FIG 1 7 M thode de la corde Image http depinfo u bourgogne fr Maitrise info trait_images analysel pdf Vectorisation bas e sur la reconnaissance de droites discr tes L algorithme de Debled consiste r
26. elle l agrandissement d une image par un facteur 20 tant d j norme Le choix du filtre de reconstruction employ lors de l agrandissement de l image est aussi laiss l utilisateur bien que le filtre de Mitchell offre g n ralement le meilleur r sultat l utilisation d autres filtres comme Bell Bspline Lanczos ou Bartlett peut tre justifi e dans des cas sp cifiques ou encore titre exp rimental 30 Ol Notre logicielti J LOX Fichier UNIVA ATA Ki ssement d Objets 20 Y gt E d AS Agrar gt r PARAMETRES Image v Voir Etiquette Actualiser v Voir Filtre utilise v Coefficient Visualisation du contour discret agrandi 3 C Oui Non Enregistrer sous ppm C png Traitement avec Traitement sans Traitement avec regions regions regions sans antialiasing Agrandir Agrandir Agrandir FIG 2 1 Interface 2 3 Interface graphique Une fois arriv s un stade avanc du d veloppement de l application nous avons choisi de concevoir une interface graphique l g re et simple d utilisation et ce afin de pouvoir directement visualiser le r sultat du traitement de limage mais aussi comparer avec un traitement plus classique ou encore visualiser le contour discret L interface permet l utilisateur de choisir une image une tiquette et de les visualiser Ensuite il est possible de sp cifier le facteur d agrandissement et de proc der au trait
27. ement de l image L opportunit de visionner clairement le contour discret est aussi offerte Enfin le r sultat obtenu par notre application et le r sultat issu d un traitement basique sont affich s pour comparaison 2 4 Fonctionnement Exemple de ligne de commande pour lancer l application figure exfonc 31 z Mlarcher pepita net cremimlarcher Pdap Mitchell Src test Fichier dition Affichage Terminal Onglets Aide mlarcher pepita test 6 mitch snail ppm snail_etiquette ppm AS Ex cutable Coefficient Filtre de Image Image contenant d agrandissement reconstruction contenant l tiquetage de utilis l objet l objet agrandir FIG 2 2 Exemple de fonctionnement Ici on agrandit l objet d crit par l tiquette snail_ tiquette ppm figure 2 4 qui est contenu dans l image snail ppm figure 2 3 par un facteur de 4 On obtient en sortie un fichier ppm incrust par d faut sur un fond gris Il est aussi possible de retourner deux fichiers l un contenant l objet agrandi et l autre son canal alpha ou encore directement un fichier png qui g re lui m me la transparence Voici les r sultats obtenus avec le fichier image et le fichier tiquette suivants L exemple suivant est principalement destin montrer le lissage sur le bord de la coque du bateau La zone d finie par l tiquette n est pas totalement uniforme 32 la force Imbattable d une quipe de profes
28. ent meilleurs que le filtre m dian Cependant en raison de la phase d apprentissage il n cessite beaucoup plus de calculs que ce dernier Mitchell Le client a sugg r l utilisation de ce fi re car il est un bon compromis entre l effet de lissage d un B spline et l effet d accentuation obtenu par un filtre bo te D autre part les autres filtres ont un co t de calcul quivalent et celui ci convient particuli rement nos attentes 1 2 4 D tection de contours R f rences 3 5 1 Nous ne sommes pas directement concern s par les m thodes de d tection de contour proprement parler Nous allons utiliser comme donn es d entr e une image tiquettes ce qui signifie que ses r gions seront d j d finies et identifiables Le travail consistera 12 alors suivre les bords de ces r gions afin de construire leur contour Nous n aurons donc pas rechercher les r gions en utilisant un des algorithmes cit s pr c demment malgr cela il est int ressant de conna tre leur existence dans l ventualit d une modification des donn es d entr e La d tection des contours associ e une segementation de l image repr sente l extension la plus int ressante qui pourrait tre apport e notre programme Ainsi la contrainte de l tiquetage manuel des r gions ne serait plus Le but de la d tection de contours est de rep rer dans une image les changements brusques de couleur et ainsi pouvoir la s pare
29. es pixels manquants Cela se fera au moyen d un filtre de reconstruction qui nous permettra alors d interpoler ces donn es Un bon filtre semble tre celui de Mitchell Mais un autre probl me survient lors du grossissement du contour sur le bord de la r gion etudi e appara t un important effet de marche d escalier si aucun pr traitement n a t effectu Dans ce projet on se donne pour but de lisser au mieux la fronti re r elle de l objet avant agrandissement de celui ci de facon minimiser l erreur d la pixellisation Il existe 20 FIG 1 14 Contour discret et euclidien sur l oeil de Lenna un algorithme de complexit lin aire permettant de lisser g om triquement ce chemin par de petits d placements de chacun de ces points le chemin euclidien Cette technique nous garanti une meilleure approximation de la fronti re r elle que les m thodes existantes tels que la polygonalisation ou bien les courbes splines Ainsi la discr tisation du nouveau contour agrandi liss on aura conserv des informations plus pr cises Pour r incruster l objet on utilisera la technique d antialiasing sur les bords de l objet Cela consiste faire appara tre les pixels du contour d une couleur de teinte interm diaire selon un certain coefficient entre celle de l objet trait et celle de sa r gion voisine Le chemin euclidien du contour permet de calculer ce coefficient alpha Chaque pixel est en
30. es points voisins Zoom fractal Cette m thode est fondamentalement diff rente des pr c dentes puisqu elle ne tient pas com pte des notions de contours et de r gions mais plut t de la recherche des similarit s structurelles de l image et l hypoth se de leur invariance par changement de r solution L ensemble de ces relations constitue le code fractal qui est une repr sentation approxi mative de cette image L utilisation du code fractal pour l agrandissement d images est r cente originale et s appuie sur son ind pendance vis vis de la r solution de l image initiale d une part mais d autre part permet de respecter la nature discontinue des images naturelles et d introduire des d tails suppl mentaires gr ce l autosimilarit Toutefois un de ses principaux d fauts est d introduire de fausses discontinuit s 1 2 3 Filtres Boite Le filtre bo te doit son nom sa fonction de transfert repr sent e par la formule Filtrer consiste multiplier la fonction de transfert par le spectre que l on d sire filtrer Dans le domaine spatial il faut proc der la convolution de la transform e de Fourier par la fonction de transfert appel e r ponse impulsionnelle h t du filtre Cette derni re pour le filtre bo te correspond la fonction sinus cardinal sinc x sin pi x pi x Cependant elle a un inconv nient majeur elle supprime de trop nombreux d tails d o l aspect flou de l image 10
31. evons veiller pr server la lin arit des diff rents algorithmes que nous em ployons et aussi que leur assemblage dans l application reste lin aire Ceci est n cessaire la rapidit du traitement des images 25 FIG 1 18 Image de test Robustesse L application doit prendre en charge les entr es inattendues ou incorrectes et renvoyer des erreurs correctement g r es l utilisateur Une partie de ces erreur concernant les entr es sorties avec le format ppm est g r es par un module d exceptions fourni par notre client Fiabilit L application doit permettre un redimensionnement correct conservant l aspect origi nal de l image Pour ce faire les algorithmes les plus fiables en terme de qualit filtre de Mitchell chemins Euclidiens sont utilis s afin d obtenir un r sultat de grande pr cision R utilisabilit Le code doit tre modulaire et donc r utilisable et am liorable Faciliter l ajout de nouveaux formats d image ou l impl mentation de nouveaux algorithmes concernant le suivi de contours le redimensionnement ou encore le lissage 1 6 Besoins fonctionnels Formats support s Nous avons choisi d opter pour les formats ppm tout d abord pour sa simplicit d uti lisation puis png pour son support de la transparence Ces deux formats sont non compress s et libres de droits 26 FIG 1 19 Agrandissement x2 au plus proche voisin Pixellisation 27 F1G 1 20
32. extensions possibles 7 1 Travaux accomplis Le chargement en m moire d images aux formats ppm et png est g r par notre appli cation la lecture de l tiquette et le suivi du contour permettent l extraction de l objet et la repr sentation de son contour sous forme discr te L impl mentation de diff rents filtres et notamment celui de Mitchell permet d agrandir les r gions de couleur unie ou d grad e avec un r sultat visuel proche de la perfection Enfin le calcul rapide des che mins euclidiens associ au lissage des bords d livre un r sultat de grande qualit une image avec des bords lisses et un contenu net De plus il est possible de traiter des images contenant plusieurs objets avec un r sultat satisfaisant l impl mentation de cette partie n ayant pas pu tre termin e faute de temps Voir figure 7 1 Comme on peut le voir figure 7 3 le r sultat n est pas encore tout fait au point L inconv nient tant la gestion de fronti res communes plusieurs objets En effet pour obtenir un bon r sultat les points de d part pour le calcul des chemins euclidiens doivent tre les m mes pour les deux objets le long de leur fronti re commune figure 7 4 Ici les chemins sont diff rents et on aper oit donc des pixels blancs g nants O FIG 7 1 Multiples objets 49 FIG 7 2 Etiquetage correspondant FIG 7 3 R sultat 90 FIG 7 4 D tail d une fronti re commune deux
33. grandir une image segment e en limitant les d sagr ments inh rents l agrandissement sur les bords des r gions et donc d am liorer la qualit visuelle de l image Mots cl s agrandissement chemin euclidien aliasing cr nelage canal alpha Abstract Two dimensional digital pictures sampled from real data all suffer from aliasing pro blems Applying a resizing filter on such pictures in a global way without defining regions blurs the borders or make aliasing appear In order to preserve clearness during resizing we resize sparately the regions objects while keeping the best approximation of the real border The blur effect generated inside the objects is no more a problem it s even producing a better result as they ar made of colour gradients Here we consider the case of previously segmented pictures with clear borders associated to a file containing their labels Picture segmentation allows the following of the discrete border of the objects The construction of an euclidean path directed by the tangent on this edge approximates at best the real border on one hand this attenuates the aliasing effect and makes the blur unnoticeable after resizing and on the other hand this allows the computation of an alpha canal used to apply antialiasing when recomposing the object with a background To conclude this application allows to increase the size of a segmented picture while reducing the inherent nuisance of enlargement o
34. htm Finalement l algorithme le plus utilis est celui de Canny Il se divise en plusieurs tapes tout d abord un filtre gaussien d adoucissement est utilis pour r duire le bruit pr sent sur l image originale Ensuite un gradient retournant l intensit des contours est appliqu en utilisant l op rateur de Sobel constitu de deux noyaux de convolution 3x3 un horizontal un vertical Gx Puis la direction des contours est calcul e on obtient donc pour chaque pixel un gradient d intensit et la direction du contour La d tection des contours se fait en utilisant une m thode de seuillage hyst r sis un maximum et un minimum sont sp cifi s on utilise la valeur maximale pour d tecter les contours nets puis ils sont trac s tant que la valeur minimale n est pas atteinte cela permet de dessiner un contour qui s estompe progressivement 1 2 5 Lissage des contours R f rence principale 8 14 dl A E a Nabwa mean 5 31 b Rothwell mesa z 25 38 e Ivarson grga 5 56 W Bergholm Gain o 69 e Canay imac 6 13 FIG 1 6 Exemple de d tection des contours 15 Afin d att nuer les effets de cr nelage d s au sur chantillonage de donn es r elles pr sents sur le contour discret d un objet le lissage est un traitement qui partir d une liste de points le contour discret fournit une repr sentation continue de l objet Dans le but d obtenir une m
35. ien choisie et suffisamment grande pour restituer correctement l ensemble des informations transport es par le signal analogique Le th or me de Shannon montre que toutes les fr quences du signal inf rieures la moiti de la fr quence d chantillonnage sont correctement restitu es 1 2 2 M thodes d interpolation Zero padding La m thode du zero padding se r sume par trois tapes illustr es par la figure 1 Dans la premi re il s agit de passer du domaine spatial au domaine fr quentiel avec la transform e de Fourier Dans la deuxi me le spectre est largi avec des z ros Et dans la troisieme tape on utilise la transform e de Fourier inverse pour revenir dans le domaine spatial Fonctions polynomiales Il s agit ici de m thodes d interpolation obtenues partir de fonction polynomiales de diff rents degr s Chacune est une am lioration de la pr c dente prenant en compte diverses contraintes notamment la sym trie la normalisation la continuit aux points de raccord ou encore la pr servation des chantillons originaux L interpolation se fait de mani re g n rale en r alisant une moyenne d un ou de plusieurs voisins selon l orientation des droites et de la position du pixel interpoler Plus proche voisin On la nomme ainsi car seul le point le plus proche intervient dans l interpolation Elle g n re beaucoup d erreurs notamment l effet de pixellisation de l image Lin aire C est une
36. ir en fonction de facteur d agrandissement sp cifi Recomposition et lissage On peut enfin choisir de recoller l objet sur un fond dont on sp cifie la couleur et ce afin d effectuer un lissage des bords de l objet et liminer tout effet d aliasing 29 Chapitre 2 Exemples de fonctionnement Pour plus de d tails sur l utilisation de l application se r f rer au manuel d utilisation en annexe 2 1 Ligne de commande Notre application tant destin un usage tr s sp cifique son ex cution est tr s ra pide et ne comporte que peu d options C est pourquoi l impl mentation d une interface graphique n tait pas indispensable De plus notre client nous a sugg r une application en ligne de commande et nous a pr cis que l utilisation d une interface graphique ne lui tait pas utile Nous avons donc avant tout d velopp notre application dans cette optique en proposant quelques options d crites ci apr s 2 2 Les options Notre application comporte certains param tres qui ont une influence significative sur le r sultat obtenu Tout d abord le facteur de redimensionnement de l image qui est bien s r le plus important mais aussi le filtre de reconstruction employ Le facteur d agrandissement notre application n tant pas con ue pour le r tr cissement d image est tout simplement un r el qui n a th oriquement pas de v ritable limite dans le cadre d une utilisation habitu
37. llage est utilis pour limiter l apparition de contours inutiles L algorithme de d tection d Iverson tente d am liorer les performances des algorithmes lin aires en ajoutant des v rifications logiques de l existence de contours et ce dans l optique de diminuer le nombre de faux contours d tect s L algorithme de Bergholm a pour but encore une fois de rep rer uniquement les contours significatifs ceux ci sont repr sent s sur l espace d chelle convolution avec un noyau de Gauss La technique consiste analyser l image en basse r solution puis projeter les contours d tect s sur l image haute r solution afin de les localiser pr cis ment Pour cela l image analys e est d abord modifi e l aide d un filtre de blur L algorithme de Rothwell est assez similaire celui de Canny d crit ci dessous mais n utilise pas de m thode de seuillage hyst r sis En effet le seuillage est ici dynamique et a une seule valeur 13 Le d tecteur par passage par zero zero crossing est bas sur un filtre Log Laplacian of Gaussian Le Laplacien d une image fait appara tre les changements d intensit rapides Il est calcul en utilisant trois noyaux de convolution 3x3 Une fois calcul on note quand il croise l axe de abscisses car cela signifie qu un contour a t d tect principe de la seconde d riv e Image http homepages inf ed ac uk rbf HIPR2 featops
38. lphas des quarts de pixels trouv s sont stock es dans un tableau tri au fur et mesure Il faut encore r organiser ce tableau de fa on obtenir les alphas des pixels entiers La complexit de ces trois tapes est fonction du nombre de points du contour discret 45 Chapitre 6 Tests 6 1 Tests unitaires 6 1 1 Code de Freeman Nous avons compar les r sultats obtenus lorsque nous suivons le contour de l tiquette avec ceux retourn s par le module de suivi de contour qui nous t fourni par Anne Vialard ceci bien s r sur le m me fichier tiquette Ils sont pour ainsi dire identiques car la seule diff rence observ e concerne le point de d part du contour qui n est pas le m me et donc le code de Freeman est d cal d un d placement Nous sommes donc assur s que notre travail se base sur un r sultat exacts 6 1 2 Chemins euclidiens De m me les r sultats obtenus lors du calcul des chemins euclidiens partir du contour discret ont t compar s ceux retourn s par le module cod par Anne Vialard Ici la diff rence se fait plus remarquer mais reste tout de m me acceptable en effet elle est la hauteur de plusieurs centi mes 6 1 3 Agrandissement V rifions l agrandissement d une image en comparant la taille avant et apr s agrandis sement et bien s r le facteur L agrandissement est effectu par un facteur 2 Apr s ouverture des deux fichiers ppm avec un diteur de texte on co
39. min euclidien 47 Facteur sp cifi incorrect ne 24 ae Pia ed nt EN ie Se 47 L Multiples OB T A SA dE A E A de SL 49 7 2 Etiquetage correspondant 50 ER CU LS ER ET ae o 50 7 4 D tail d une fronti re commune deux objets 51 ES o E A IA 52 10 Page principale ssi EE ER E A e ep SS 54 7 7 S lection du fichier image traiter ena le 54 7 8 Selection du fichier tiquette 2 4 2 versa a RE e 55 7 9 Bouton refresh gt eds AE atada tia la sa 55 Mi o A Due ss arms Mg AEN 55 vel Diff rents filtres das Na aa re tease le te de dre ad 56 12 Cho d ee aci rd ir o Sl 56 7 13 Choix du type d agrandissement 56 Chapitre 1 Introduction 1 1 Domaines d application Depuis son apparition dans les ann es 70 l imagerie num rique est devenue un l ment indispensable dans le domaine scientifique mais aussi de la vie courante On appelle image num rique toute image stock e sous forme binaire Elle peut tre acquise par un capteur CCD Charged Coupled Device ou cr e num riquement On appelle ces derni res images de synth se Les avantages des images num riques par rapport aux images dites classiques sont nombreux Leur stockage et r f rencement est simple et rapide Il est bien plus ais et rapide d envoyer une image num rique gr ce aux r seaux informatiques qu une image classique par voie postale Elles s
40. mpare les tailles sp cifi es dans les ent tes Snail ppm 256 256 Snailx2 ppm 512 512 Valeur coh rente 46 Notre modue Module cod par A Vialard zs A E 78 470589 213 625000 77 764706 213 285714 77 058823 212 950000 76 352940 212 650000 74 941177 74 235294 73 529411 72 823528 72 117645 212 050000 211 750000 211 470588 211 176471 210 857143 75 617060 212 352911 75 650000 212 350000 FIG 6 1 Comparaison des r sultats du calcul du chemin euclidien gt gt scale lt 1 0 Abandon FIG 6 2 Facteur sp cifi incorrect 6 2 Tests de robustesse 6 2 1 Facteur d agrandissement maximal Un petit objet de taille environ 50x50 pixels a t agrandi 100 fois avec succ s nous n avons pas pouss plus loin nos tests du plus grand facteur d agrandissement sp cifiable consid rant qu un facteur sup rieur d j qu agrandir 100 fois un objet est inutile 6 2 2 Objet de forme peu commune L application a t test e avec diff rents fichiers tiquette de forme inattendue Le comportement a t normal et le r sultat conforme avec les objets suivants Objet dont la longueur ou la largeur est de 1 pixel Objet dont la forme est complexe et dont les bords ne sont jamais droits Objet compos d un seul pixel Cependant l ex cution ne se d roulera pas si un ojet est situ sur le bord de l image nous avons exclu ce cas qui apporte diff rentes
41. n the regions borders hence improving the visual image quality Key words zoom Euclidian path aliasing alpha channel enlargement Sommaire 4 2 1 4 2 2 Chemins euclidiens 4 2 3 Filtre de Mitchell 4 2 4 Antialiasing 5 Complexit des principaux algorithmes 9 1 9 2 Chemins Euclidiens Antialiasing 1 Introduction 1 1 Domaines d application 1 2 Analyse de l existant 1 2 1 Repr sentation d une image 1 2 2 M thodes d interpolation L23 F ES LS Let es Les 1 2 4 D tection de contours 1 2 5 Lissage des contours LS Le e esti ra e 1 3 1 Les diff rents formats de fichiers image 1 4 L importance du d coupage par r gion 1 5 Besoins non fonctionnels 1 6 Besoins fonctionnels 2 Exemples de fonctionnement 2 1 Ligne de commande 2 2 Les options eu E E pa a 2 3 Interface graphique 2 4 Fonctionnement 3 Architecture et d coupage modulaire 4 Structures de donn es et algorithmes 4 1 Structures 4 1 1 TabPixel 4 1 2 ContourDiscret 4 1 3 ContourLisse LA filter h et pam D ENEE EE a 4 2 Algorithmes et techniques Suivi de Condo XA ADO O0 12 14 20 21 24 25 26 30 30 30 31 31 36 39 39 39 39 40 40 41 41 42 42 42 6 Tests 46 6 1 Tests unitaires sd td ir td dr 46 6 1 1 de Freeman dilo e EE 46 6 1 2 Chemins euclidiens 24 ius a e 8 4
42. nt 1 22 Puer image format ppm mg Lecture de l in age Tables de pixels Chemin Luck due Contour Tableau plus gend incomplet Agrandissem ent et Filtre de dscr lisalion reconsiruch op Contour agrendi Tableau complet Super post on Otet agrandi et liss canal alpha FIG 1 16 Diagramme de fonctionnement 2 23 256 n tant pas un nombre de couleur suffisant pour notre travail nous avons cart ce format Jpeg Joint Photography Experts Group Ce format est libre de droits et permet de repr senter 16 millions de couleurs Malheu reusement la compression associ e implique des pertes d informations m me au taux le plus faible c est pourquoi nous n avons pas travaill avec ce format d image Png Portable Network Graphics Png propose une compression sans perte la repr sentation de 16 millions de couleur ainsi que le support de la transparence De plus ce format est libre et s av re donc tre un bon choix pour nos travaux Tiff Tagged Image File Format Utilis pour l archivage d images de qualit Utilise un algorithme de compression sans perte Fichiers de relativement grandes dimensions Doum Portable Any Map Pnm regroupe en r alit 3 formats ppm pgm et pbm qui sont respectivement utilis s pour les images en couleurs en niveaux de gris et en monochrome Ce format peut tre cod en Ascii ou en Brut cette deuxi me solution est assez simple d utilisation ca
43. on introduit les courbes polynomiales Interpolation polynomiale A partir d un ensemble de points l interpolation poly nomiale lin raire bilin aire Lagrange fournit un polyn me qui passe exactement par chacun de ces points Ici on se contentera de passer au voisinage de ces points car nous cherchons plutot lisser une s rie de points et non pas trouver quel polyn me repr sente le mieux ces points Splines Une fonction spline est une fonction continue d finie par morceaux par des polyn mes L approximation Les splines d approximation peuvent passer par certains points de contr le mais en g n ral ne passent pas par tous les points Cette technique pose donc un choix des points a traiter Ce qui lisse encore mieux mais qui implique in vitablement une perte de localisation Le lissage devant tre r versible c est dire que l on doit pouvoir retrouver tous les points initiaux cette technique ne nous concernera pas L interpolation L interpolation quant elle traite tous les points que l on appelle points de contr le On ne demande pas la nouvelle repr sentation du contour de passer exactement par le point elle peut passer dans un voisinage du point Courbes de B zier Les splines sont une g n ralisation des courbes de B zier qui sont des courbes polynomiales param triques La courbe est l int rieur de l enveloppe convexe des points de contr le La courbe commence par le point PO et
44. on tabPixel t tabPixel objet contourDiscret d int tabPixel tabPixel lire_png char chemin int tabPixel_ecrire_png tabPixel t char chemin int tabPixel_ecrire_png_alpha tabPixel t tabPixel trans char chemin fichier ppm fichier ppm Ze gt agrandir l tint main int argc char argv Etiquette TabPixel alpha ContourDiscret int x int y int taille char code code de Freeman contourLisse contourLisse_creer contourDiscret c float contourLisse_vecteur contourLisse 1 void contourLisse_imprimer contourLisse 1 float contourDiscret_x discret c void contourLisse zoom contourLisse c double coeff void contourDiscret_modif_x discret c float x float contourDiscret_y discret c void contourDiscret_modif_y discret c float y int contourDiscret_taille discret c char contourDiscret_code discret c void contourDiscret_ajouter contourDiscret d unsigned char zc int contourDiscret_verifier contourDiscret d void interface_lancement contourDiscret contourDiscret_vide float x float y void agrandir char file char etiquette contourDiscret contourDiscret_creer float x float y int taille char code aaa f char save_ contourDiscret contourDiscret_suivre tabPixel etiquette g float contourDiscret_euclidiens discret c void contourDiscret_visualiser contourDiscret d tabPixel t char nom void contourDiscret_imprimer contourDiscret d int contourDiscret_dans_obje
45. ont plus faciles traiter changer une ou plusieurs couleurs diminuer ou agrandir la taille etc et analyser La plupart des images num riques sont repr sent es sous forme d un ensemble de points appel s pixels chacun tant caract ris par sa couleur Dans la plupart des cas ceux ci sont plac s sur une grille C est dans cette repr sentation que r side le probl me majeur de la qualit des images plus la grille contenant les pixels est fine meilleure est la qualit de l image et r ciproquement une grille moins fine repr sentera une image de qualit inf rieure En agrandissant une image num rique c est en effet sa grille qui change de dimension ce qui cr e un manque d informations combler Ceci conduit une approximation de valeurs et les contours des objets dans l image r sultante deviennent flous Ce qui est important c est de pouvoir agrandir une image tout en gardant ces derniers nets L agrandissement d images num riques trouve son application dans plusieurs domaines qu ils soient scientifiques ou de la vie courante Pour donner quelques exemples prenons d abord le domaine de la m decine plus particuli rement la mammographie o le traite ment de l image est uniquement bas sur l agrandissement car la faible diff rence de den sit des tissus du sein ne permet pas au syst me num rique de faire des auto d tections Les radiologues sont oblig s d examiner tr s finement le clich
46. pixels de l image Si alpha 1 le pixel est opaque et si alpha 0 le pixel est transparent et si 0 alpha 1 la nouvelle couleur du pixel est un mixage de la couleur du pixel avec celle du fond calcul e selon alpha Filtrage L antialiasing peut tre effectu gr ce aux filtres utilis s en imagerie tel que filtre de Gauss par exemple sur le contour de l objet qui va remplacer chacun des pixels trait s par un m lange des couleurs de ses voisins Mais il laisse encore des d fauts car le filtrage rend le cr nelage flou mais toujours pr sent On choisit donc d effectuer l antialiasing en approximant les fronti res r elles Principe M thode propos e dans le document On se basera sur la construction du chemin euclidien dirig par la tangente afin de calculer le canal alpha sur les bors de l objet Pour le reste des pixels contenus dans la bote englobante cet alpha d pendera juste de leur appartenance l objet discret ou non Notre but est donc de calculer pour chaque pixel travers par le chemin euclidien l aire de recouvrement du domaine euclidien qui sera la valeur de alpha L algorithme va s effectuer sur tous les points du contour discret La cellule qui encadre ce point Pi est l intersection de quatres quarts de pixels qui entourent eux m mes ce point et donc fournit des donn es pour quatre pixels Il faudra donc recomposer pour chaque pixel ses quatre quarts de pixel trouver par les points
47. r en r gions Un contour peut tre la limite entre deux zones de couleur diff rente ou encore une ligne traversant une zone de couleur uniforme Dans ce cas le contour se situe de chaque c t de la ligne L approche la plus simple pour la d tection s effectue en parcourant les lignes de pixels horizontales et verticales s par ment On lit donc les valeurs des pixels se suivant sur chaque ligne en surveillant les changements importants On a alors deux images s par es l une repr sentant les contours horizontaux et l autre les contours verticaux En superposant les deux on obtient une image contenant tous les contours Pr sentons maintenant les diff rentes m thodes de d tection de contours existantes Un des premiers algorithmes de d tection fut celui appel Roberts Cross Il est assez simple et utilise deux noyaux de convolution 2x2 Cette approche est toujours utilis e car sa faible complexit rend l ex cution tr s rapide cependant elle est tr s limit e car trop sensible au bruit sur les images cela tant d la trop petite taille des noyaux 10 ofi ofa 0 Gx Gy L algorithme de d tection des contours de Nalwa fonctionne par remplissage de surface Il n utilise pas le calcul de la d riv e mais des fonctions tangentes hyperboliques et quadratiques sont utilis es pour correspondre l intensit de l image dans un noyau de 5x5 pixels La fonction avec la plus faible erreur est retenue Un seui
48. r un fichier peut alors tre tout simplement ouvert avec un diteur de texte afin de voir les valeurs des composantes de chaque pixels Ce format est sans compression et ne supporte pas la transparence Cependant sa simplicit d utilisation en fait un bon choix pour d buter notre projet Jpeg2000 Le format jpeg2000 a t cr pour palier aux d fauts du format jpeg Il permet une compression sans perte des donn es mais ne supporte pas la transparence 1 4 L importance du d coupage par r gion Comme cela a t pr cis pr c demment nous savons combler les pixels manquant lors de l agrandissement d une image Ceci est fait gr ce un filtre de reconstruction qui se sert des pixels voisins pour donner une valeur au nouveau pixel Il y a pour cela diff rentes m thodes existantes L approche la plus simple consiste r utiliser les valeurs de pixels d j existants et de les reproduire pour les pixels manquants Le r sultat est peu convaincant et on obtient une image tr s pixellis e avec des contours tr s alias s mais dont la nettet est pr serv e 24 P3 a P3 correspond au format ppm nomfichier ppm a Le nom du fichier est ecrit dans l entete 256256 Largeur et longueur du fichier 255 Valeur maximale d une composante Elle sera utilisee pour remplacer une valeur incoherente Composantes rouge verte bleue du premier pixel de l image ps 255 255 255 255 255 255 255 255 255 25
49. s valeurs des composantes rouge verte et bleue de chaque pixel de l image repr sent e par le TabPixel Les donn es associ es ce pointeur sont les plus utilis es tout au long du programme En effet chaque pixel de l image a deux coordonn es x et y Cependant ils sont ensuite stock s dans un tableau a une dimension raison de trois valeur par pixel une chaque composante et pour retrouver le pixel souhait partir de sa position on a recours deux valeurs shift_X et shift_Y Par exemple pour retrouver les trois composantes du pixel la position i j on lit le pointeur donn es aux positions suivantes i shift_X j shift_Y rouge i shift_X j shift_V 1 vert i shift_X j shift_Y 2 bleu o shift_X 3 trois composantes et shift_Y est gal la largeur de l image 4 1 2 ContourDiscret ContourDiscret permet de repr senter le contour de notre objet l aide d un point de d part et d un code de Freeman 39 X y Les deux entiers x et y sont les coordonn es du point de d part du contour il est int ressant de note qu un contour tant situ entre les pixels ne poss de pas de coot donn es enti re mais demi enti res taille Nous avons besoin de connaitre le nombre de d placements n cessaire au suivi du contour afin de le parcourir et cela nombreuses reprises C est pourquoi nous avons choisi d int grer un entier repr sentant ce nombre la structure de donn
50. sualisation image tiquette R le et Fonctionnement Le bouton correspondant fichier traiter permet de charger une image tiquette au format ppm ou png On peut aussi sp cifier un nom de fichier manuellement Une fois le chargement effectu nous pouvons visualiser 7 7 l image gr ce au bouton voir FIG 7 7 S lection du fichier image traiter 54 Etiquette Refresh fille_etiquette ppm y Voir FIG 7 8 Selection du fichier tiquette Etiquette Refresh FIG 7 9 Bouton refresh Refresh R le et Fonctionnement Le bouton refresh a pour r le de g n rer un tiquette relative l image visualis e 7 13 Une fois l image visualiser choisie un clic sur le bouton refresh g n re une liste d tiquettes On peut donc en s lectionner une et la visualiser Coefficient d Agrandissement R le et Fonctionnement 7 10 Avec cette option nous avons la possibilit d effectuer un agrandissement de l image avec le facteur de zoom d sir Filtres Le logiciel permet l utilisation de plusieurs filtres Fonctionnement 7 11 Agrandissements R gions avec lissage R gions sans lissage Sans r gions 7 12 Coefficient le el F1G 7 10 Coefficient 99 Altre utilise Mitchell v Fic 7 11 Diff rents filtres Enregistrer sous ppm C png F1G 7 12 Choix du format Traitement avec Traitement sans Traitement avec regions regions regions sans
51. t int i int j tabPixel etiquette contourDiscret Id int contourDiscret min max contourDiscret d int delimination contourDiscret d void contourDiscret_eliminer_region int limites tabPixel etiquette int referenc int isAppartient int lignes int x int y void contourDiscret_detruire discret c float aliasing contourDiscret d int delimitatfion EH RAISE error message FIG 3 1 Architecture 37 Image 2D tiqut e Fond Objet Extraction de l objet OBJET 2D CONTENU CONTOUR discret Lissage chemin Euclidien Agrandissement Agrandissement interpolation lin aire Filtre de reconstruction de Mitchell Netravali Discretisation CONTOUR discret OBJET 2D CANAL ALPHA AGRANDI Image 2D avec objet agrandi FIG 3 2 D roulement CONTENU agrandi Chapitre 4 Structures de donn es et algorithmes 4 1 Structures 4 1 1 TabPixel TabPixel est la structure de donn es qui nous permet de repr senter l image Toutes les op rations de lecture et d criture d image passent par elle largeur hauteur La largeur et la hauteur sont repr sent es par deux entiers et correspondent aux di mensions de l image Ces deux l ments sont tres souvent utilis s notament pour ajuster la valeur de shift_Y n cessaire au parcours des donn es contenues par le TabPixel donn es Donn es est un pointeur sur unsigned short qui contient le
52. trous Les objets trous correspondent des r gions plusieurs contours Un exemple est illustr sur la figure 7 6 page 54 Notre logiciel ne les traite pas actuellement mais c est 51 FIG 7 5 R gion trou e une extension possible Il suffit de cr er une nouvelle structure dans laquelle on pourrait attribuer un objet plusieurs objets de type contourDiscret 7 4 Application aux objets situ s sur le bord de l image Une des conditions d utilisation de notre logiciel est que les objets ne se situent pas sur le bord de l image c est dire avoir au minimum une ligne de pixels entre la r gion et le bord car l algorithme de suivi du contour devient tr s complexe dans le cas contraire Ainsi si l image traiter contient des objets sur le bord il suffit de rajouter au pr alable une ligne suppl mentaire de pixels pour assurer les bonnes conditions du suivi du contour 7 5 V ritable d tection de contours permettant de s affranchir de l tiquetage Actuellement nous travaillons par r gions d finies au pr alable mais une des extensions possibles de notre logiciel est celle de la recherche de contours ferm s dans l image Ainsi la recherche de r gions se fera automatiquement par le logiciel et l utilisateur pourrait donner seulement l image traiter en entr e Cependant les algorithmes actuels de d tection de contours ne sont pas suffisants malgr leur relative efficacit En effet
Download Pdf Manuals
Related Search