Stage pratique DEA : Tatouage dimages et laris.univ- ? Stage pratique DEA : Tatouage dimages

  • Published on
    14-Sep-2018

  • View
    212

  • Download
    0

Transcript

Stage pratique DEA :Tatouage dimages et Cryptographie :Pour assurer confidentialit, intgrit etauthentification des images mdicales et insrerdes donnes confidentiellesRomain Hrault20 aot 2004RemerciementsJe tiens remercier : Monsieur le Professeur Jean-Jacques Le Jeune, chef du service, pour sonaccueil au sein du laboratoire de Mdecine Nuclaire et de Biophysique duCHU dAngers. Madame le Docteur Christine Cavaro-Mnard, Matre de confrences etresponsable de lunit de Traitement dImages Mdicales au LISA, pour len-cadrement de ce stage, ses conseils aviss et sa disponibilit. Messieurs le Docteur Alain Le Duff, le Docteur Guy Plantier, le DocteurDaniel Schang, enseignants-chercheurs lESEO, pour avoir su motiver mondsir deffectuer ce DEA et de poursuivre dans le domaine de la recherche. Aymeric Histace et Xavier Baty, doctorants au LISA, Tangy Le Fol, Ben-jamin Vallet, Jean-Pierre Kinn, Fabien Lefvre, Pierre-Yves Daniau-Clavreul, stagiaires au LISA, pour leur soutien, aide et conseils ainsi queleur bonne humeur.1Synthse du StageService de Mdecine NuclaireHpital LarreyRue Larrey49000 AngersLISA FRE 2656 CNRSUniversit dAngers62, avenue Notre Dame du Lac49000 AngersHrault RomainUniversit dAngersFvrier-Septembre 2004Tatouage dimages et CryptographieLe dploiement des PACS et des dossiers mdicaux lectroniques ncessite un effort de s-curit accru en termes de confidentialit, fiabilit et disponibilit. Le tatouage de donnes (ouwatermarking) permet de renforcer la scurit en faveur de la fiabilit des donnes images par lin-sertion dans limage source dannotations (authentification) et/ou par linsertion dune signaturede limage source (intgrit). Le watermarking permet galement dintgrer dans les images desdonnes confidentielles telles que des informations physiologiques (ECG ...) et/ou diagnostiques, cequi assure une plus grande confidentialit aux donnes patients. Pour renforcer cette confidentialitet obtenir une authentification rigoureuse, nous devrons insrer une tape de cryptologie dans lachane de tatouage.RsultatsNotre tude a port sur : la dfinition des caractristiques des mthodes cryptologiques, la mise en uvre des mthodes cryptologiques adaptes au domaine de limagerie mdicale, loptimisation du programme complet de tatouage et linsertion de la cryptologie, la quantification des dgradations dencodage pour des tudes futures du laboratoire.Les travaux effectus durant ce stage ont permis : didentifier les caractristiques et donc les mthodes de cryptologie optimales pour notreapplication, de mettre en uvre toutes les briques logicielles ncessaires la ralisation de la chane detatouage, dimplmenter les nouvelles mthodes dvaluation de la dgradation.Mots-Cls : Codage, tatouage rversible, confidentialit, disponibilit, fiabilit, intgrit, au-thentification, imagerie mdicale, cryptologie, information diagnostique.2Table des matires1 Prsentation du sujet 62 tat de lart 82.1 Mthodes de tatouage rversibles . . . . . . . . . . . . . . . . . . . . 82.1.1 La mthode de Fridrich . . . . . . . . . . . . . . . . . . . . . . 82.1.2 La mthode de Celik . . . . . . . . . . . . . . . . . . . . . . . 102.2 Cryptologie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122.2.1 Introduction la cryptologie . . . . . . . . . . . . . . . . . . . 122.2.2 Caractristiques des mthodes de cryptage . . . . . . . . . . . 132.2.3 Tableau rcapitulatif des bibliothques cryptographiques dis-ponibles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153 Algorithme prdiction-expansion 183.1 Le tatouage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 183.1.1 La premire tape . . . . . . . . . . . . . . . . . . . . . . . . . 183.1.2 La deuxime tape . . . . . . . . . . . . . . . . . . . . . . . . 193.1.3 La troisime tape . . . . . . . . . . . . . . . . . . . . . . . . 203.1.4 La quatrime tape . . . . . . . . . . . . . . . . . . . . . . . . 203.1.5 La cinquime tape . . . . . . . . . . . . . . . . . . . . . . . . 203.1.6 La sixime tape . . . . . . . . . . . . . . . . . . . . . . . . . 203.2 La reconstruction de limage originale . . . . . . . . . . . . . . . . . . 213.3 Diffrence-expansion . . . . . . . . . . . . . . . . . . . . . . . . . . . 224 Insertion de la cryptologie dans la chane de tatouage 234.1 Donnes embarquer . . . . . . . . . . . . . . . . . . . . . . . . . . . 234.2 Acteurs de la communication . . . . . . . . . . . . . . . . . . . . . . . 244.3 Dfinition des droits daccs . . . . . . . . . . . . . . . . . . . . . . . 244.4 Insertion de la cryptologie . . . . . . . . . . . . . . . . . . . . . . . . 245 Amliorations des algorithmes dj existants 265.1 Problmes techniques . . . . . . . . . . . . . . . . . . . . . . . . . . . 2635.1.1 Cration de DLL en C++ pour Matlab . . . . . . . . . . . . . 265.1.2 Bibliothques cryptographiques . . . . . . . . . . . . . . . . . 275.2 Mthodes de compression rversible du flot de bits . . . . . . . . . . . 275.2.1 La transformation de Burrow-Wheeler (BWT) . . . . . . . . . 285.2.2 Compression JBIG . . . . . . . . . . . . . . . . . . . . . . . . 306 Mesure de la dissimilarit 316.1 LEQM : lcart quadratique moyen . . . . . . . . . . . . . . . . . . . 316.2 Le PSNR : le rapport signal bruit . . . . . . . . . . . . . . . . . . . . 316.3 La distance de Baddeley . . . . . . . . . . . . . . . . . . . . . . . . . 326.3.1 Transformation dune image 2D (A) en niveaux de gris en uneimage 3D binarise (B) . . . . . . . . . . . . . . . . . . . . . . 326.3.2 Transformation distance . . . . . . . . . . . . . . . . . . . . . 326.3.3 Exemple de calcul de la transforme distance . . . . . . . . . . 346.3.4 Calcul de la distance de Baddeley . . . . . . . . . . . . . . . . 387 Phase de test 397.1 Le panel dimages tests . . . . . . . . . . . . . . . . . . . . . . . . . . 397.2 Quels sont les besoins? . . . . . . . . . . . . . . . . . . . . . . . . . . 397.3 Le protocole de test . . . . . . . . . . . . . . . . . . . . . . . . . . . . 407.3.1 Mthodes de tatouages . . . . . . . . . . . . . . . . . . . . . . 407.3.2 Algorithmes de compression et cryptages . . . . . . . . . . . . 408 Rsultats et interprtations 418.1 Mthodes de tatouage . . . . . . . . . . . . . . . . . . . . . . . . . . 418.1.1 Algorithme de Cellik . . . . . . . . . . . . . . . . . . . . . . . 418.1.2 Algorithme de Fridrich . . . . . . . . . . . . . . . . . . . . . . 418.1.3 Algorithme de Tian . . . . . . . . . . . . . . . . . . . . . . . . 428.1.4 Algorithme Prdiction-Expansion . . . . . . . . . . . . . . . . 468.1.5 Comparaison de Tian et Prdiction-Expansion . . . . . . . . . 498.2 Mesure de dissimilarit . . . . . . . . . . . . . . . . . . . . . . . . . . 518.3 Mthode de cryptage et de compression . . . . . . . . . . . . . . . . . 539 Perspectives 5410 Conclusion 5511 Rfrences 56A Algorithmes 61A.1 Mthode des LSB . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61A.2 Mthode des LSB gnralise : G-LSB . . . . . . . . . . . . . . . . . . 614A.3 Le Codage Arithmtique . . . . . . . . . . . . . . . . . . . . . . . . . 61B Introduction la programmation dune DLL en C 635Chapitre 1Prsentation du sujetLutilisation des images en mdecine et dans le domaine de la recherche est enpleine expansion. Le dploiement des PACS (Picture Archiving and CommunicationSystems) et des dossiers mdicaux lectroniques ncessitent un effort de scurit ac-crue. Daprs G. Coatrieux et al. [1], ces rgles de scurit reposent sur 3 principesfondamentaux : Confidentialit, Fiabilit et Disponibilit. La confidentialit assure lefait que seules les personnes autorises peuvent accder linformation. La fiabilitde linformation doit tre comprise comme tant lassociation dune double vrifi-cation : lintgrit et lauthenticit des donnes. Limage ne doit pas avoir subi demodification (intgrit) volontaire ou non depuis son acquisition ou aprs tout trai-tement considr faisant partie dun protocole entirement dfini et connu. Limagedoit de plus tre en adquation avec lidentit du patient (authenticit). La dis-ponibilit du systme dinformation (maintenance, astreinte informatique) pour lesutilisateurs est videmment la troisime rgle de scurit. Pare-feu, contrle dac-cs, antivirus, cryptographie, signature lectronique et accrditation logicielle sontles garants actuels de lintgrit et de la confidentialit des donnes mdicales avecles limites humaines et matrielles que lon connat. Le tatouage de donnes (ouwatermarking) permet de renforcer la scurit en faveur de la fiabilit des donnesimages par linsertion dannotation dans limage source (authentification) et/ou parlinsertion dune signature de limage source (intgrit). Le watermarking permetgalement dintgrer dans les images des donnes confidentielles telles que des infor-mations physiologiques (ECG ...) et/ou diagnostiques, ce qui assure une plus grandeconfidentialit aux donnes patients.Une premire tude [2] a abouti la mise en uvre dun algorithme rversiblede tatouage dimage qui exploite la corrlation spatiale des niveaux de gris duneimage. Cette mthode tatoue la marque dans lerreur de prdiction locale des pixelsde limage. Elle sinspire de lapproche de Tian prsente dans [3]. Lalgorithme deprdiction-expansion permet daugmenter de faon significative la capacit despacelibr pour linsertion du rsum de limage (intgrit), de la globalit de len-tte6DICOM (authentification) et de certaines donnes physiologiques et/ou diagnos-tiques. Mais lalgorithme prdiction-expansion ne ralise pas de contrle dintgritet dauthentification, au sens cryptographique du terme, des donnes insres (si-gnatures, donnes diagnostiques).Lobjectif de ce stage sera donc : de faire ltat de lart des mthodes de cryptologie et de leurs caractristiques, danalyser les besoins dans le domaine de limagerie mdicale afin de dfinirles caractristiques des mthodes de cryptographie utiliser, dinsrer la cryptographie dans la chane de tatouage, damliorer la programmation actuelle de la chane afin de la rendre plus fonc-tionnelle, de mettre en uvre des mthodes de quantification des dgradations engen-dres par lencodage afin de raliser par la suite une tude des mthodes de ta-touage irrversibles plus robustes aux attaques potentielles telles que le zoom,le changement de dynamique...7Chapitre 2tat de lart2.1 Mthodes de tatouage rversiblesLe tatouage dune image consiste insrer des donnes (ou marque) lintrieurde limage.Les techniques de tatouage peuvent tres spares en 2 catgories : les mthodesrversibles et les mthodes irrversibles. Aprs extraction et vrification de la validitde la marque, les mthodes rversibles sont capables de fournir un duplicata exactde limage originale.Le critre de rversibilit est bien entendu primordial pour des considrationsdordre thique : limage est en partie la source dun diagnostic.Suite une recherche bibliograhique sur le tatouage rversible, nous nous sommesaperus que seuls quatre algorithmes rversibles rpondent notre objectif: tatouerlimage avec une faible dgradation de limage tatoue. Limage tatoue devra treglobalement similaire limage originale afin de servir de support visuel au diagnosticralis sur limage originale. Les algorithmes retenus sont :1. lalgorithme de Fridrich, algorithme en cours dimplmentation [4][5],2. lalgorithme de Celik [6],3. lalgorithme diffrence-expansion propos par Tian [3],4. lalgorithme prdiction-expansion prsent dans [2].Les publications de ces articles sont relativement rcentes (1999-2003). Les deuxdernires mthodes, proches dans leur conception, seront prsentes dans le chapitre3 puisque la mthode prdiction-expansion quil ma fallu optimiser, a t developpeau LISA.2.1.1 La mthode de Fridrich- Les pixels de limage sont assembls en groupes de pixels (blocs...).8- Deux fonctions commutatives f(x1,x2,...) et F (X) sont dfinies : la fonction f dite de discrimination cherche mesurer la rgularit desgroupes de pixels. Cette fonction peut-tre, par exemple, la fonction va-riation f(x1,x2,...,xn) =n1i=1 |xi+1 xi| la fonction F de permutation tel que F (F (X)) = X. Cette fonction peut-tre par exemple la fonction qui 1 associe 0 et 1 associe 0, 3 associe2 et 2 associe 3, ...- Pour chaque groupe de pixels est attribue une catgorie R, S ou U suivant leschma suivant : R (Regular) si f(F (G)) > f(G) S (Singular) si f(F (G)) < f(G) U (Unusable) si f(F (G)) = f(G)- La carte binaire de localisation contenant les positions de R et S est compresseet rajoute aux donnes embarquer.- Le code 0 est attribu au groupe R, le code 1 au groupe S. Pour faire changerdtat un groupe de pixels, il suffit de lui appliquer la fonction F .- Lors de la reconstruction, il suffira de rappliquer la fonction de permutation,suivant la carte de localisation, sur un pixel pour obtenir la valeur initiale dupixel.Cet algorithme rcent (2002) na pas encore t test au laboratoire.ExempleSoit le groupe de pixel G suivant :A BC DLa fonction de discrimination est calcule sur ce groupe :f1 = f(A,B,C,D)La fonction de permutation est calcule pour chaque pixel :A = F (A) B = F (B) C = F (C) C = F (C)La fonction de discrimination est calcule sur le nouveau groupe :f2 = f(A,B,C ,D)Si f1 = f2 le groupe est dit "unusable" et donc non retenu.Si f1 > f2 le groupe est dit "singular" et quivaut la valeur 1.Si f1 < f2 le groupe est dit "regular" et quivaut la valeur 0.9Si le groupe ne correspond pas la valeur dsire pour le marquage, les valeurs(A,B,C,D) du groupe de pixels sont substitues par les valeurs du groupe permut(A,B,C,D).Lors de la reconstruction suivant la carte embarque, il suffira de rappliquer lafonction de permutation sur (A,B,C,D) pour obtenir (A,B,C,D).2.1.2 La mthode de CelikCelik and al. prsentent [6] un algorithme de tatouage rversible, nomm LAW(Localized Lossless Authentication Watermark). Une opration de quantification esttout dabord effectue afin de librer un espace variable dans limage originale. Lacompression du flux des rsidus de lopration de quantification permet dassurer larversibilit du marquage et dinsrer le flux de donnes ncessaire pour le contrledintgrit. Le procesus peut tre rendu hirarchique afin deffectuer la localisationdventuelles attaques (volontaires ou non). Le processus dauthentification quant lui est ralis par un algorithme de cryptographie combinant cls prive et publique.Opration de quantificationUne fonction de quantification scalaire de niveau L est la base du processus.Soit s le vecteur reprsantant le signal original.QL(s) = LbsLc (2.1)bc : reprsente la fonction du plus grand entier infrieur ou gal *.Le tatouage (Equation 2.2) et le dtatouage (Equation 2.3) sont effectus par lesystme dquations (2.2) suivant :sw = QL(s) + w (2.2)w = sw QL(sw) = sw QL(s) (2.3)sw est le signal marqu. w reprsente la marque constitue de symboles wi ditL-aire symboles, cest dire wi {0,1,...,L 1}.Opration de conversions L-air binaireLutilisation dune marque constitue de caractres de type L-aire ncessite uneconversion binaire vers L-aire pour les flux de bits entrant et une conversion L-aire vers binaire pour rcuprer le flux binaire du message. Ces conversions peuvententraner des dpassements de capacit (underflow ou overflow). Dans le cas duneimage code sur 8 bits (de 0 255 valeurs) par exemple, si L=6, QL(s) = 252 et10w=5 alors le pixel marqu aura la valeur sw = 257. Ce rsultat ne peut pas trecod entre 0 et 255, il sagit donc dun dpassement de capacit ou overflow. Celikpropose un codage arithmtique modifi pour viter ces risques de dpassement eteffectuer les conversions .Codage arithmtique modifiLe codage arithmtique modifi est bas sur le codage arithmtique prsent enannexes (cf. A.3). Le flux de bits tatouer est reprsent par un nombre H.H = 0,h0h1h2... H [0,1[. (2.4)Au dpart R reprsente lintervalle [0,1[. Limage possde des pixels de valeurscomprises entre 0 et smax. Pour assurer la rversibilit du systme le nombre H devratre marqu sur un nombre suffisant de valeurs de s (ici les pixels correspondantssont connexes). Pour la premire valeur de s, la valeur de QL(s) est calcule ainsiquun nombre de niveaux N tel que :N = min(L,smax QL(s)) (2.5)Lquation 2.5 permet dviter les risques de dpassement de capacit. Le codagearithmtique modifi consiste alors diviser R en N intervalles quivalents R0 RN1. Puis lintervalle satisfaisant H Rn (n [0,N 1]) est slectionn et lamarque insrer est w=n. Le nouvel intervalle R est dfini par R = Rn pour laprochaine valeur de s.Quantit dinformation embarqueLun des avantages du codage arithmtique est que chaque caractre peut trecod sur un nombre non-entier de bits (contrairement un algorithme du typeHuffman). En effet, cet algorithme ne code pas les fichiers caractre par caractremais par chanes de caractres, plus ou moins longues suivant la capacit de lamachine coder des rels plus ou moins grands. Si un caractre apparat avec uneprobabilit de 90%, la taille optimale du code serait de 0.15 bit 1.Chaque signal original embarque une marque L-aire w daprs lquation (2.2),provenant du rsultat du codage arithmtique modifi. Daprs la thorie de lin-formation chaque w reprsentera une capacit C = ln(L) mesure en bps (bit persample).1. Quantit information = ln (probabilit)= ln 0,9 = 0,105 ' ln 20,1511Rversibilit : Mthode G-LSB sans perteBase sur la mthode LSB prsente en annexe (Cf. A.1), la mthode G-LSB estcapable de crer une image marque avec de faibles distorsions mais le processusreste irrversible. En effet lors de lopration de quantification, un rsidu r est cr(Equation 2.6) puis remplac par le signal de la marque.r = sQL(s) (2.6)s = QL(s) + r = QL(sw) + r (2.7)La rversibilit est obtenue en embarquant le rsidu r comme flux de donnesdans la marque insrer. Lors du dtatouage, les valeurs de r seront rcupres et lesignal original pourra tre recalcul (Equation 2.7). Pour optimiser la taille du fluxdes donnes r, lalgorithme de compression CALIC [7] est utilis. La compressionest un lment majeur pour amliorer la capacit dembarquement de la mthodeG-LSB sans perte. Plus CResidu r sera faible, meilleure sera la compression et doncplus la capacit CGLSB sans perte sera importante (Equation 2.8)CGLSB sans perte = CGLSB CResidu r (2.8)2.2 Cryptologie2.2.1 Introduction la cryptologieUn peu de vocabulaireIl existe 3 grands thmes souvent associs la cryptologie eux-mme diviss ensous-thmes [8] :- Cryptographie. Cryptologie : lart de coder un message pour le rendre illisible pour lespersonnes auxquelles il nest pas destin. Cryptanalyse : lart de casser les codes.- Stganographie : lart de communiquer un message sans que la transmissiondu message soit dtecte. Tatouage. Image autorparatrice (image embarquant des donnes qui permettent dela reconstruire en cas daltration). Evasion de frquences (mission dun message qui ressemble du bruit). Message subliminale.12- Empreintes : lart de faire correspondre un message une empreinte ou signa-ture qui identifie le message. Dtection derreur. Fonction de hachage (dveloppe ci-dessous).Fonction de hachageElle sert au calcul dune empreinte du message. Lempreinte (ou rsum) est unchiffre identifiant, idalement de faon unique, le message. Une fonction de hachageest considre comme sre si deux messages probables ne donnent pas le mmersum (collision) et si partir de lempreinte on ne peut prsumer du contenu dumessage.Une fonction de hachage permet de vrifier lintgrit dun message.Il existe diffrentes fonctions de hachage dcrites dans la littrature. Le MD5(traditionellemnt utilis cf table 2.2) est de plus en plus remplac par le SHA-256(cf table 2.2) considr comme plus sr : dune part il est calcul sur 256 bits (moinsde risque de collision) dautre part il est plus difficile de contourner sa protectioncryptographique.2.2.2 Caractristiques des mthodes de cryptageTraditionellement, les termes "crypter" et "dcrypter" un message sont utiliss,mais il y a une volonte de remplacer ces termes par "coder" et "dcoder" pour nepas choquer certaines cultures; decrypter pouvant signifier profaner.Pour dfinir les principales caractristiques des mthodes de cryptage, un en-semble de personnages aux rles spcifiques est souvent cit dans les publications,notamment :- Alice : lmettrice du message,- Bob : le rcepteur du message,- Eve : une espionne qui coute la transmission,- Martin : un espion qui coute la transmission et qui peut la modifier,- Norbert : un tiers de confiance.Cryptographie cl secrte (mode symtrique)Alice et Bob possdent un secret en commun qui sert de cl de cryptage etde dcryptage. Alice doit avoir confiance dans Bob et inversement. Ce mode decryptographie est le plus ancien, le plus rpandu et le plus sr. Il est namoinsfragilis par la distribution des cls. En effet, pour chaque couple (Alice, Bob), ildoit exister une cl unique; voire pour chaque transmission (Alice et Bob doivent13Mode symtrique Mode assymtrique15 cls 12 clsFig. 2.1 Rpartition des cls pour 6 intervenantsgnrer une cl qui sera jete la fin de la communication). Le nombre de cl devientrapidement grand ce qui pose le problme de la transmission des cls par un canalsr (cf figure 2.1)Cryptographie cl publique (mode assymtrique)Ce mode de cryptographie a permis de rsoudre le problme de la distributiondes cls : La cl servant au codage (cl publique) est diffrente de la cl servant audcodage (cl prive). Alice utilise la cl publique de Bob pour coder son message;Bob utilise sa cl prive pour dcoder le message. Il suffit seulement de 2 cls parintervenant.En plus du cryptage, ce mode permet lauthentification des messages : Aliceutilise sa cl prive pour coder le message ; Bob utilise la cl publique dAlice pourdcoder le message. Comme seule la cl prive dAlice correspond la cl publiquedAlice, si le message est intelligible, Bob est assur de la provenance du message.Les algorithmes cl publique sont bass sur une difficult de calcul (inversiondune exponentiation par exemple) et sont donc moins srs que les algorithmes cl secrte. Une combinaison des modes est le plus souvent utilise (dans [9] ou [10]par exemple), le mode cl publique servant de canal sr la transmission dun clsecrte entre Alice et Bob.142.2.3 Tableau rcapitulatif des bibliothques cryptographiquesdisponiblesLes tableaux rcapitulatifs (Tab. 2.1 et Tab. 2.2) prsentent un bilan des bi-bliothques cryptographiques disponibles sur Internet. Chaque ligne reprsente unprogramme ou une librairie, chaque colonne une fonctionalit. Les dtails concernantles licences dutilisation en vigueur pour ces bibliothques sont donnes ci-dessous.Les licences dutilisationLes licences MIT (Masachusets Institute of Technology) :Il existe plusieurs types de licences dutilisation en usage au MIT, elles permettentsous conditions strictes davoir accs au code source et de le modifier pour ses besoins,la redistribution du code est gnralement limite.La licence GPL (General Public Licence) :Issue des licences MIT, elle garantit en plus de laccs aux sources, la libert duti-lisation et de redistribution du logiciel condition que tout programme issu de cecode ou utilisant ce code (mme travers une bibliothque) soit publi sous cettemme licence.La licence LGPL (Lesser General Public Licence) :Plus souple que la GPL, elle autorise lutilisation par un programme non GPL ouLGPL dune bibliothque LGPL en liaison dynamique.Les licences BSD (Berkeley Software Distribution) :Licence en usage luniversit de Berkeley, trs souple au niveau des conditionsdutilisation et daccs au code source. Il nest mme pas ncessaire de prciser laprovenance dun code BSD et son auteur dans un programme tiers lutilisant (la loifranaise nous y oblige quand mme).Les logiciels dits "freeware" :Logiciels libres dutilisation mais dont le code source est partiellement ou complte-ment clos. Ces logiciels sont souvent freeware pour une utilisation en recherche ouenseignement et proritaire pour une application commerciale.Les logiciels dits "shareware" (ou partagiciels) :Logiciels libres dutilisation dans un temps imparti ou dans une limitation de cesfonctionalits. Le logiciel devient compltement fonctionel aprs rtribution de sonauteur. Code source clos.Les logiciels dits "propritaires" :Logiciels qui peuvent tre partiellement brids dans leur fonctionnement et dontlaccs au code source est quasiment impossible sauf accords commerciaux trs on-reux.15Tab. 2.1 Tableau rcapitulatif : partie 1Appellation url Licence SourceCTCjava http://www.bifroest.demon.co.uk/ctc/ free? ouibeecrypt http://sourceforge.net/projects/beecrypt/?borzoi http://www.dragongate-technologies.com/products.html GPL ouicertlib ?cryptix http://www.cryptix.org/ BSD-like ouicryptlib http://www.cs.auckland.ac.nz/ pgut001/cryptlib/ free nc ouicrypto++ http://www.eskimo.com/ weidai/cryptlib.html free ouicryptokit http://packages.debian.org/unstable/libs/libcryptokit-ocaml LGPL ouiCTClib http://www.bifroest.demon.co.uk/ctc/ free? ouidealib ?EGD http://egd.sourceforge.net/ GPL/MIT ouiGnuPG http://www.gnupg.org GPL ouilibdes http://linux.maruhn.com/sec/libdes.html MITlibgcrypt http://www.gnu.org/directory/security/libgcrypt.html LGPL ouilibmcrypt http://mcrypt.hellug.gr/ GPLlibTomCrypt http://libtomcrypt.org/ free ouimacCTC http://www.bifroest.demon.co.uk/ctc/ free? ouimhash http://mhash.sourceforge.net/ LGPL ouiMIRACL http://indigo.ie/ mscott/ free for educationopencl/botan http://botan.randombit.net/pycrypto http://www.amk.ca/python/code/crypto.html free? ouiRSAeuroSSLava http://www.phaos.com/products/category/crypto.htmlSSLeay http://www2.psy.uq.edu.au/ ftp/Crypto/ ouitplockbox http://sourceforge.net/projects/tplockbox/ GPL/LGPL ouiAppellation PossibilitsAlatoire SymtriqueAES(Rijndael)ARC2ARC4BlowfishCAST5CAST128DES3DESDiamond2gostIDEAISSACLionlubyrackMARSMisty1NoekonpanamaRC2RC4RC5RC6safersapphireskipjacksealserpentsharksquareTEAXTEATwofishwakeCTCjava X X X X X Xbeecryptborzoi Xcertlibcryptix X X X X X X X X X X X X X Xcryptlib X X X X X X X X X Xcrypto++ X X X X X X X X X X X X X X X X X X X X X Xcryptokit X X X XCTClib X X X X X XdealibEGD XGnuPG X X X X X X X Xlibdes X Xlibgcrypt X X X X X X X Xlibmcrypt X X X X X X X X X X X X XlibTomCrypt X X X X X X X X X X X X X XmacCTC X X X X X Xmhash XMIRACL Xopencl/botan X X X X X X X X X X X X X X X X X X X X X X X Xpycrypto X X X X X X X X XRSAeuro X XSSLava X XSSLeay X X X X Xtplockbox X X X X16Tab. 2.2 Tableau rcapitulatif : partie 2Appellation PossibilitsAsymtrique HashblumgoldwassrDiffie-HelmanDSAElGamalelepticcurveluclucdiflucelgNyberg-RueppelqNewrabinrabin-williamsrawDSARSARSASSA-PKCS1RSASSA-PSSCRCHAVALHAS-160MD2MD4MD5panamaRIPEMD-128RIPE-MD160SHA-0SHA-1SHA-256...SHSTIGERWhirpoolCTCjava X Xbeecryptborzoi X X Xcertlibcryptix X X X X X X X X X X X X X X Xcryptlib X X X X X X X X Xcrypto++ X X X X X X X X X X X X X X X X X X X X X X Xcryptokit X X X XCTClib X XdealibEGDGnuPG X X X X X X X Xlibdeslibgcrypt X X X X X X X XlibmcryptlibTomCrypt X X X X X X X X X X X XmacCTC X Xmhash X X X X X X XMIRACL X X X Xopencl/botan X X X X X X X X X X X X X X X Xpycrypto X X X X X X XRSAeuro X X X XSSLava X X XSSLeay X X X X X Xtplockbox X X X17Chapitre 3Algorithme prdiction-expansionLe principe de lalgorithme de tatouage prdiction-expansion, qui a t dveloppau LISA, pour des images en niveaux de gris (cas des images mdicales), se base surla diffrence damplitudes entre un pixel et sa valeur prdite grce son voisinage(les 3 pixels suprieurs et les 3 pixels infrieurs). Si cette diffrence rpond uncritre prcis (que nous verrons par la suite), alors elle va pouvoir tre tatoue.Ainsi, la valeur de la diffrence va tre lgrement modifie et donc la valeur dupixel reconstruit aussi. Limage sera ainsi tatoue (ou marque); les lignes pairessont tout dabord traites puis les lignes impaires, excepte la premire ligne pourpouvoir initier le processus de reconstruction.3.1 Le tatouageIl se dcompose en six tapes rsumes ci-aprs.3.1.1 La premire tapeLa diffrence entre la valeur x dun pixel et sa prdiction l (quation (3.1)), ob-tenue partir des 3 pixels suprieurs et des 3 pixels infrieurs, est calcule et noteh (quation (3.2)). Deux listes de valeurs h et l sont donc obtenues.Soit x lamplitude du pixel en cours de traitement, yi lensemble des 6 pixels sup-rieurs et infrieurs :y1 y2 y3xy4 y5 y6l =aiyiai(3.1)18h = x l (3.2)La transformation inverse des quations (3.1) et (3.2) est donne par :x = l + h (3.3)Si lamplitude x doit tre comprise entre 0 et 2n 1, n tant le nombre de bits decodage des amplitudes de limage source (ici 8), il est clair que :h 255 l et h l (3.4)Il est ds lors possible dinsrer les bits de tatouage b dans la valeur h selon lunedes quations suivantes :h = 2h + b (3.5)h = 2bh2c+ b (3.6)bxc : fonction plus grand entier infrieur ou gal x.Pour prvenir les problmes doverflow et dunderflow, h doit satisfaire :|h| min(255 l,l) (3.7)quelque soit la valeur de b (0 ou 1)Ainsi, deux adjectifs caractrisent h :h est dit "extensible" si|2h + b| min(255 l,l) (3.8)quelque soit la valeur de b (0 ou 1)h est dit changeable si|2bh2c+ b| min(255 l,l) (3.9)quelque soit la valeur de b (0 ou 1)3.1.2 La deuxime tapeElle permet de crer quatre groupes (EZ, EN, CN et NC) disjoints des valeurs hselon des critres indiquant si elles sont aptes tre marques et dans quelle mesure.EZ : contient tous les h "extensibles" dont la valeur est soit 0 soit -1.EN : contient tous les h "extensibles" 6 EZ.CN : contient tous les h "changeables" 6 (EZ EN).NC : contient tous les h "non-changeables".193.1.3 La troisime tapeElle permet de crer une carte de localisation binaire L des valeurs h qui serontmarques. Lors de cette tape, il est possible de contrler les dgradations de limageen scindant le groupe EN en deux groupes EN1 (dont les valeurs h seront tatouesselon lquation (3.5)) et EN2 (dont les valeurs h seront tatoues selon lquation(3.6)). Le critre de slection des h de EN1 peut se baser sur la simple valeur de h :EN1 sera constitu des plus faibles valeurs de EN, do lutilisation dun seuil T telque :EN1 = {h EN : |h| T} et EN2 = {h EN : |h| > T} (3.10)Pour h EZ EN1, la valeur 1 est assigne la carte L. Ces valeurs seronttatoues selon lquation (3.5). Pour h EN2 CN , la valeur 0 est assigne lacarte L. Ces valeurs seront tatoues selon lquation (3.6).Une tudes complmentaire ma t demande afin de fixer le seuil T en fonctiondu nombre de bits insrer et ainsi optimiser le rapport entre EN1 et EN2 et doncla qualit de limage marque en fonction du flot de bits tatouer.3.1.4 La quatrime tapePuisque lquation (3.6) substitue le bit de poids faible des valeurs h, il estnecssaire pour obtenir un tatouage rversible de transmettre pour ces valeurs lesbits dorigine. Cette tape permet de rcuprer les bits de poids faible des valeursh de EN2 et CN. Le flux de bits B est alors constitu ; B sera trs utile lors de lareconstruction de limage pour retrouver les valeurs originales des pixels.3.1.5 La cinquime tapeElle est vritablement lopration de tatouage de limage. Tout dabord, la marqueM insrer est obtenue en concatnant la carte de localisation compresse L, le fluxde bits de poids faible B et un rsum not R de limage tatouer. Cest aussi cemoment que peuvent tre insres dautres informations relatives limage (nom dupatient, informations diagnostiques ...) si la taille de la marque M ne dpasse pas lenombre de valeurs h extensibles ou changeables. Une fois la marque cre, la valeurh est tatoue selon lquation (3.5) ou (3.6) selon son groupe dappartenance (cf.tape 3).3.1.6 La sixime tapeElle permet de construire limage tatoue selon lquation (3.3) partir de la listedes valeurs l (cre ltape 1) et la nouvelle liste des valeurs marques h (cre ltape 5).203.2 La reconstruction de limage originalePour savoir si limage tatoue a t altre dune manire volontaire (falsification)ou non (zoom...), nous devons procder son dmarquage, et extraire le rsum delimage originale. Le rsum de limage restaure peut alors tre compar au rsumde limage originale prsent dans la marque. Si les deux rsums concident, alorslimage na pas t dgrade.Limage restaure est construite partir de limage tatoue en enlevant la marqueprsente dans les bits de poids faible de toutes les valeurs h marques (cest direchangeables) puis en restaurant les valeurs h originales puis les amplitudes des pixels.Les cinq tapes de restauration de limage sont dcrites ci-aprs.La premire tape de restauration est identique la premire tape du tatouageet consiste calculer la diffrence h entre la valeur de chaque pixel avec la prdiction lobtenue grce aux pixels voisins. Les listes des valeurs diffrence h et des prdictionsl sont calcules daprs les quations (3.1) et (3.2). La valeur l calcule est alorsidentique celle calcule lors du codage du fait que les valeurs des pixels du voisinagesont identiques lors de ces deux phases. En effet, les lignes paires sont tout dabordcodes puis les lignes impaires. Lors du dcodage, ce sont les lignes impaires quisont tout dabord traites prenant en compte les valeurs tatoues des lignes pairescomme pour la phase de codage.La deuxime tape permet de classer toutes les valeurs h dans deux groupes dis-joints :CH contient tous les h changeables selon lquation (3.9), ces h contiennent lamarque.NC contient tous les h non changeables (ne contiennent pas la marque).La troisime tape consiste extraire les bits de poids faible de toutes les valeursh appartenant au groupe CH, cest--dire thoriquement celles qui ont t tatoues.On obtient alors un flux de bits correspondant la marque M insre lors du tatouageduquel il suffit dextraire les flux de bits L, B et R.La quatrime tape permet de rcuprer les valeurs h originales. La carte delocalisation L et le flux de donnes B permettent de restaurer les valeurs h originales.Les h associs la valeur 1 de la carte de localisation L sont restaures grce unesimple division entire (quation (3.11)). Les autres h de CH auront utiliser le fluxde bits B pour retrouver leurs valeurs initiales (quation (3.12)).h = 2bh2c (3.11)h = 2bh2c+ br (3.12)br tant le bit rcupr.21La dernire tape consiste reconstruire limage initiale grce aux valeurs hrestaures et aux valeurs l de ltape 1 (quations 3.3). On obtient ainsi limagerestaure partir de limage tatoue.3.3 Diffrence-expansionLalgorithme prdiction-expansion est une modification profonde de lagorithmediffrence-expansion de Tian [3]. Cet algorithme est bas sur la dcomposition enondelettes entires de Haar. Tian travaille alors sur 2 pixels voisins. Pour les valeursx et y de pixels voisins, nous obtenons :l = bx + y2c (3.13)h = x y (3.14)Les tailles des matrices L et H changent. En effet, pour lalgorithme prdiction-expansion, elles ont une taille similaire la taille de limage originale (aux premireet dernire lignes prs) alors que pour Tian, elles font la moiti de la taille de limageoriginale. Cest pourquoi nous pourrons insrer davantage dinformations relativesau patient ou au diagnostic dans la marque de limage. De plus, le fait de tenircompte dun plus grand voisinage permet une meilleure prdiction du pixel centralet donc une erreur (ou diffrence) plus faible ce qui augmente le nombre de pixelstatouables. Par contre, lquation (3.2) montre la modification directe de x et nondes deux pixels voisins comme Tian 1. La dgradation peut donc tre plus importantecar supporte par un seul pixel. Une tude des dgradations engendres sera doncncssaire.1. Limage est conserve lchelle 1:222Chapitre 4Insertion de la cryptologie dans lachane de tatouageDans le titre mme du projet, il est dit que le procd utilis doit permettre das-surer la confidentialit, lintgrit, et lauthentification des images. Les mthodesde tatouage rversibles permettent en combinaison avec les fonctions de hachagedassurer lintgrit de limage. Une faible confidentialit est obtenue par laspectstganographique du tatouage. Aucune authentification de lorignie du message, ausens strict, nest assure dans la chane actuelle du tatouage cependant, des infor-mations sur le patient et lorigine de limage sont contenus dans len-tte DICOMembarque dans limage. Lintroduction de la cryptographie dans la chane actuelledoit apporter ces deux dernires fonctions. Lauthentification par un algorithme cl publique et la confidentialit par une combinaison cl publique cl secrte.4.1 Donnes embarquerNous pouvons distinguer 4 types de donnes embarquer dans limage : Le rsum de limage qui doit permettre le contrle de lintgrit (prvu dansla chane de tatouage). Len-tte DICOM qui contient en plus des informations patients des informa-tions complmentaires la prise de vue telles que dfinies par ce standard (T1ou T2, le temps de relaxationen IRM ...) Les traitements subis par limage avant tatouage : pour une meilleure lecturedu diagnostic. Le dossier mdical initial : donnes annexes entres par le mdecin lors ducompte rendu. Le dossier complmentaire : donnes ajoutes en sus du dossier initial pour lesuivi du patient (volution du diagnostic...)23Patient Corps mdical Corps mdical autoris MachineRsum R R R RWAEn-tte DICOM R R RWATraitement de limage R R RWADossier Initial R R RWADossier complmentaire R RW RWTab. 4.1 Rsum des droits daccs4.2 Acteurs de la communicationDans le cadre de la transmission dimage, nous pouvons considrer quil y a 4acteurs intervenant dans la communication : la machine qui gnre limage, le patient, le corps mdical, le corps mdical "autoris" ajouter des donnes limage.4.3 Dfinition des droits daccsLe tableau 4.1 suivant rsume les diffrents droits daccs de chaque acteur surchaque section (R : droit de lecture, W : Droit dcriture , A : authentification) :4.4 Insertion de la cryptologieNous prconisons lutilisation dun schma cl publique du fait que nous devonspermettre certaine personne la lecture sans leur autoriser lcriture et que nousdevons permettre lauthentification tous. Nous pouvons ds maintenant regrouperle cas du dossier initial, des traitements subis avant tatouage et de len-tte DICOM,les droits daccs de ces groupes sont identiques.Nous pouvons donc distinguer alors 3 lots de clefs : CA1 et CA2 pour le rsum, CB1 et CB2 pour le dossier initial, len-tte DICOM et le processus de traite-ment de limage, CC1 et CC2 pour le dossier complmentaire.Chaque couple correspond aux 2 cls gnres par un schma cl publique.Par contre seule la cl CA1 est publique : CA2 est conserve par la machine qui24seule peut accder en criture cette partie. Tout le monde peut lire le rsum doncvrifier lintgrit de limage car la cl CA1 est publique.De mme CB2 est conserve par la machine mais CB1 est seulement donne aucorps mdical, restreignant ainsi laccs en lecture mais garantissant lauthentifica-tion par la machine (CB2 est secrte).CC2 est uniquement donne au corps mdical autoris et CC1 est donne tousle corps mdical ce qui permet de la mme faon de grer les droits daccs demanire cryptographique.Des amnagements sont possibles avec un sytme hybride cl secrte, cl privepour rduire le temps de calcul comme pour le GPG [10] : le mode assymtriqueservant de canal sr la transmission dune cl secrte.25Chapitre 5Amliorations des algorithmes djexistantsPlusieurs algorithmes ont t tests au laboratoire. Pour les algorithmes Prdiction-Expansion et Diffrence-Expansion la compression de limage de localisation a tsimplement ralise par les mthodes RLE, Huffman et LZW. Les mthodes utili-ses prcdement donnent des rsultats relativement mdiocres par rapport desalgorithmes avancs, comme JBIG2. De plus il reste finaliser limplmentationde lalgorithme prdiction-expansion developp par le laboratoire et programmerlalgorithme de Fridrich.5.1 Problmes techniques5.1.1 Cration de DLL en C++ pour MatlabLe mcanisme des mex-files permet de programmer en C directement dans Mat-lab et de compiler grce au compilateur LCC. Malheuresement, le dbugage estextrmement difficile car si la dll bloque, cest lensemble de Matlab qui bloque.Nous devons donc introduire de nombreux tests dans le code et imprimer un mes-sage la moindre suspicion derreur.Malheureusement, LCC ne peut compiler que du C et lenvironement de program-mation de Matlab est assez pauvre. Notamment nous ne pouvons utiliser make pourgrer les sources, ni gdb pour deboguer. Pour pouvoir programmer en C++, nousdevons utiliser un autre compilateur. Pour ce faire, jai propos et install le pro-gramme gnumex [11] qui intgre gcc (GNU Compilers Collection [12]) Matlab,ainsi que lenvironement de programmation mingw qui fournit des outils indispen-sables comme make et gdb (dbogage).265.1.2 Bibliothques cryptographiquesDe nombreuses bibliothques cryptographiques sont disponibles via lInternet.Malheureusement la plupart des programmes pour Microsoft Windows r sont ensources closes ce qui nest pas pertinent pour lapplication mdicale ; en effet lascurit dun systme cryptographique ne peut tre base uniquement sur le secret deson algorithme car dune part le secret peut tre bris et, dautre part, lalgorithme nepeut tre test et adapt lapplication par la communaut scientifique. De plus, leslicences sont strictes quand lutilisation des logiciels et ncessitent un paiement dsque lon sort du contexte de recherche. Deux bibliothques restent donc utilisables,Botan [13] (licence BSD) et libgcrypt [14] (license LGPL). Botan est disponible pourWindows r mais nest plus maintenue. libgcrypt est maintenant considre commeun standard, cette bibliothque fait partie du projet GNU [15] ce qui lui assure unegrande stabilit et prinit; nanmoins lintgration dans Windows nest pas encoretermine (gnrateur dalas non compatibles). Dans un premier temps, jutiliseraiBotan pour tester les algorithmes. libgcrypt sera utilise pour finaliser lapplication.Fonctions de compression et fonctions de hachagePlusieurs fonctions de compressions et de hachage ont t developpes grce labibliothque Botan :- dlllzw compression LZW,- dllrle compression RLE,- dllhuffman compression Huffman,- dllari compression arithmtique,- dllsha256 fonction de hachage.Dans le futur, des fonctions de cryptographies viendront se rajouter (dllrsadllaes).5.2 Mthodes de compression rversible du flot debitsIl existe de nombreuses mthodes de compression rversibles de donnes ba-ses sur le codage statistique (Huffman, Arithmtique, LZW), sur le codage spa-tiale(RLE,...). Nous tudierons deux nouvelles mthodes de compression : la BWTbase sur un tri lexicographique et JBIG (1 et 2) base sur un codage vectoriel plusadapte au codage dimages binaires telles que les images de localisation.275.2.1 La transformation de Burrow-Wheeler (BWT)La transformation Burrow-Wheeler (BWT) est une transformation de lespacedes donnes vers un autre espace plus propice la compression de donnes : cettetransforme a pour but daugmenter la corrlation spatiale dans le message traiteret ainsi damliorer la compression par des algorithme de codage du type RLE ouLZW.Transforme directeAlgorithme1. Cration dun tableau contenant toutes les rotations du message.2. Trie du tableau par ordre lexicographique.3. La transforme du message correspond la dernire colonne du tableau ainsiqu la position dans le tableau tri du message de dpart.Exemple Lexemple se fera avec le message bananas.tape 1 tape 2 tape 3bananasananasbnanasbaanasbannasbanaasbanansbananaananasbanasbanasbananbananasnanasbanasbanasbananaananasbanasbanasbananbananasnanasbanasbanasbananaLa transforme du message bananas est donc bnnsaaa,4.Transforme inverseAlgorithme1. Une colonne est remplie avec le message dcoder.2. Cration dun tableau contenant en premire colonne, la colonne de la premiretape trie et en dernire colonne, la colonne de la premire tape non trie.3. On ajoute ct de chaque colonne, une colonne qui contient le nombre defois que la lettre correspondante est apparue dans la dite colonne.4. La position du message est utilise comme point de dpart de lalgorithme dereconstruction. Nous avons alors la premire et la dernire lettre du message.Une lettre (colonne impaire) et un chiffre (colonne paire) forment une cl.28Lalgorithme de reconstruction consiste prendre la deuxime cl de la lignedtude puis selectionner la ligne qui contient cette cl en premire colonne.Exemple Nous devons dcoder le message bnnsaaa,4tape 1 tape 2 tape 3bnnsaaaa ba na nb sn an as aa 1 b 1a 2 n 1a 3 n 2b 1 s 1n 1 a 1n 2 a 2s 1 a 3tape 4 : nous commenons par tudier la ligne 4, nous savons dornavant quenotre message commence par b et se finit par s. La deuxime cl de la ligne 4 est(s, 1) nous recherchons cette cl dans la premire colonne; elle se situe en ligne 7,nous obtenons alors une nouvelle cl (a, 3). Le processus est rpt jusqu obtentiondu message de dpart.(s,1) (a,3) (n,2) (a,2) (n,1) (a,1) (b,1)Partant de la dernire cl, nous retrouvons bien le message : bananas.RsulatsLalgorithme de la BWT demandant le tri et la gestion en mmoire dun grandtableau, la puissance de Matlab r nest pas suffisante (3 heures pour une image 8bits 512x512). Jai donc dcid de programmer lalgorithme en C et de lutiliser travers une dll dans Matlab. La programmation de lalgorithme en C a permis depasser dun temps de calcul de 3 heures 2 minutes. Lnorme diffrence vient dufait que je contrle tout le processus, notament de la gestion de la mmmoire : pourune image 512x512, Matlab doit alouer 512x512x512x512 pour faire le tri; en C,grce un dcalage judicieux, je nai besoin que dune liste 512x512. En effet, je nedois pas caculer explicitement toutes les rotations de limages, mais seulement untableau contenant la position de la rotation dans le tableau tri.Employer cette mthode sur des images 2 ou 3 niveaux de gris ne semble pas trsconcluant : le faible nombre de niveaux de gris ne permet pas de sparer correctementles donnes lors de la phase de tri.Jai contact deux tudiants anglais qui travaillent sur une extension en 2D de cettetransforme, leur travail na pas encore abouti. Une compression vectorielle type29JBIG est plus intressante pour des plans de bits. La BWT est certainement retenir pour les autres donnes embarquer telles que les donnes diagnostiques.5.2.2 Compression JBIGLa compression JBIG est une quantification vectorielle developpe la base pourle fac-simil. Les parties lmentaires de limage sont transformes puis compares un dictionaire. Limage compresse contient les indexs utiliss dans le dictionnaireainsi que les transformation. La version 1 et 2 de cet algorithme diffre essentielle-ment par le dictionnaire utilis et par une optimisation sur les transformations.Ladoption de gcc ma permis dintgrer plus facilement des bibliothques djexistantes dans Matlab.Une premire tentative dintgration de la bibliothque JBIG en C issue de Linuxavait chou. Jai donc dcid dintroduire une couche dabstraction en C++ (com-patible avec gcc) qui ma permis de grer beaucoup plus facilement les objets enmmoire et ainsi viter les fuites de mmoire (trs grande dimension des tableaux)et les erreurs de segmentation qui rendait le programme inutilisable dans sa premireversion.La compression JBIG est directement utilisable dans Matlab travers les appelsdlljbig() pour la compression et dllijbig() pour la dcompression.Tian utilise JBIG2 dans ces articles; malheuresement, seul JBIG est disponiblegratuitement et je nai trouv aucun programme utilisable depuis Matlab qui ap-plique la compression JBIG2. Nanmoins, les rsultats obtenus sont nettement plusprobant quavec une simple compression RLE puis LZW-HUFFMAN (gain de 20%).30Chapitre 6Mesure de la dissimilaritBien que travaillant sur des mthodes rversibles, il est intressant de quantifierla dgradation de limage tatoue qui pourra servir de support visuel au diagnosticralis sur limage original. De plus le laboratoire envisage dtudier galement unechane de tatouage irrversible pour satisfaire le critre de robustesse face desmodifications de limage (zoom ou fentrage pour un meilleur diagnostiqc) Afin depouvoir quantifier lerreur introduite par la chane de tatouage, nous devons retenirun critre de dissimilarit entre limage de dpart et limage tatoue. La plupart despublications utilise le PSNR comme critre mais il est peu judicieux en imageriemdical, car trop global. La perception du mdecin lors dun diagnostiqc ntantpas la mme quun individu non initi devant un image classique. De plus, ce critrene met pas en avant les modifications gomtriques engendres par le codage (trsvisibles lors dune compression JPEG par exemple), et pouvant tre importantesdans une chane de tatouage si les contours supportent une grande partie de lamarque.6.1 LEQM : lcart quadratique moyenCest le critre de dissimilarit le plus connu, il est gnralement associ auPSNR :eqm =Ni=1 x2i x2iN(6.1)6.2 Le PSNR : le rapport signal bruitLe psnr nest quune mise chelle logarithmique de lEQM :psnr = 10log(max2eqm)(6.2)31Leqm et le psnr ne tiennent comptent que de la diffrence de niveau de grispixel par pixel.6.3 La distance de BaddeleyPour pallier cet inconvnient, nous avons introduit la distance de Baddeleyqui prend en compte non seulement les variations de niveaux de gris mais aussi lesdformations gomtriques [16]. Cette mesure est base sur une extension de limage2D en niveaux de gris, en une image 3D binarise. On mesure ensuite la distanceentre la surface reprsente par limage tatoue et la surface de rfrence reprsentepar limage originale (Figure 6.1).Fig. 6.1 Distance du pixel la surface de rfrence6.3.1 Transformation dune image 2D (A) en niveaux de grisen une image 3D binarise (B)Une troisime dimension reprsentant lchelle de niveau de gris est ajoute,limage B est cre par la rgle suivante :B(i,j,z) = 1 si A(i,j) = z sinon B(i,j,z) = 06.3.2 Transformation distanceDistance de ChanfreinOn appelle une distance sur le plan discret ZZ2, toute fonction d dfinie surZZ2 ZZ2 valeurs relles non ngatives satisfaisants les trois axiomes suivants : d(p,p) = 0 et pour p 6= q d(p,q) > 0 d(p,q) = d(q,p) d(p,r) < d(p,q) + d(q,r)32Une approche classique en gomtrie discrte consiste mettre une pondration surladjacence dun pixel ses voisins, valant la distance entre ces 2 pixels. Ainsi, lastructure donne ZZ2 est celle dun graphe pondr, dont les artes sont celles de la8-adjacence. A chaque arte entre 2 pixels voisins p et q on donne un poids P (p,q).La distance entre p et q correspond au poids minimum des 8-chemins pour aller dep q. Pour une 8-adjacence, un tableau 3x3 est ncessaire la dfinition des poids.Ce tableau est appel tableau de Chanfrein et la distance corespondante distance deChanfrein.b a ba 0 ab a bTab. 6.1 Tableau de ChanfreinLa distance euclidienne est obtenue avec a = 1 et b =2. Si on considre un8-chemin pour aller du point M au point N , le poids total du chemin correspond la somme des poids lmentaires.Conditions de MontanariPour respecter les axiomes de la distance, Montanarie a dfini deux conditionssur a et b : a > 0 a b 2aDans notre cas, nous nous efforcerons de nous raprocher de la distance euclidiennetout en restant dans lensemble des entiers naturels en prenant a = 3 et b = 4.Le masque de Chanfrein peut-tre tendu une matrice 5x5 appelle masque deBorgefors.Transformation distance 2DCette transformation associe chaque pixel une valeur correspondant la dis-tance de ce pixel avec un objet de rfrence. Lobjet de rfrence sera dfini parla valeur 1 dans limage de dpart et le fond 0. Lalgorithme utilis permet en 2parcours de limage dobtenir le rsultat. La matrice de Chanfrein est rduite lamatrice de prcdence du parcours dfini [16].La valeur de chaque pixel P est obtenue grce la matrice (Tab. 6.2) de prc-dente M par la formule suivante :P = min(P + M(i,j)) i [1 3] j [1 3]33b a ba 0 Tab. 6.2 Matrice de prcdence du premier parcoursUn deuxime parcours est effectu dans le sens inverse avec la matrice M retour-ne 180.Extension la 3DLe principe est identique, la valeur de chaque voxel corresponds la distance dupixel la surface de rfrence (surface 3D). La matrice de Chanfrein est elle-aussitendue la troisime dimension (Tab. 6.3) :c b cb a bc b cb a ba 0 ab a bc b cb a bc b cTab. 6.3 Tableau de Chanfrein tendu la troisime dimensionDo la matrice de prcdence suivante (Tab. 6.4) :c b cb a bc b cb a ba 0 Tab. 6.4 Matrice de prcdence tendue la troisime dimension6.3.3 Exemple de calcul de la transforme distanceNous allons prendre un exemple simple pour illustrer cette transforme, limagede dpart est la table 6.5.InitialisationLa premire tape est de transformer limage de dpart en une matrice qui nousservira dtat initial pour le premier parcours : la valeur 0 de limage correspond une distance infinie, la valeur 1 de limage (sur la surface de rfrence) correspond une distance nulle (table 6.6) .340 0 0 0 0 00 0 0 1 1 10 0 1 0 0 00 1 0 0 0 01 0 0 0 0 00 0 0 0 0 0Tab. 6.5 Image de dpart 0 0 0 0 0 0 Tab. 6.6 Matrice initialePremier parcoursNous allons parcourir limage avec la matrice de prcdence (table 6.2) danslorde dcrit la figure 6.2.Fig. 6.2 Parcours de limageNous prenons le premier pixel (1,1) et son voisinage, nous les aditionnons avecla matrice de prcdence puis gardons la valeur minimum, dans ce cas la valeurminimum reste (table 6.7).Le premier pixel changer de valeur est le pixel (4,3) comme le montre la table6.8.35Voisinage du pixel Martrice de prcdence Somme Minimum 0 Tab. 6.7 Calcul du Pixel (1,1)Voisinage du pixel Martrice de prcdence Somme Minimum 0 00 4 3 43 0 3 43 3Tab. 6.8 Calcul du Pixel (4,3)Lalgorithme est le mme pour chaque pixel, le rsultat du premier parcours setrouve en Table 6.9. 0 0 0 0 3 3 3 0 3 4 6 60 3 4 7 8 93 4 7 8 11 12Tab. 6.9 Matrice obtenue la fin du premier parcoursSecond parcoursLa dmarche est identique pour le second parcours, seul change le sens du par-cours (figure 6.3) et la matrice de prcdence (table 6.10).36Fig. 6.3 Parcours de limage 0 34 3 4Tab. 6.10 Matrice de prcdence retourne 180Le rsultat du second parcours donne la matrice transforme distance (table6.11).8 7 4 3 3 37 4 3 0 0 04 3 0 3 3 33 0 3 4 6 60 3 4 7 8 93 4 7 8 11 12Tab. 6.11 Matrice transforme distance376.3.4 Calcul de la distance de BaddeleyLa transfome distance est calcule pour les deux images comparer. On obtientlespace S pour limage source et lespace I pour limage tester. La distance D estcalcule comme suit :D =[vS(S(v)d I(v)d)]1dcard(S)On prend gnralement d = 2 pour tre conforme la distance Euclidienne. Cettedistance prend en compte la fois les dformations gomtriques et les variationsde niveaux de gris.Ici, le voxel v est de forme cubique. En modifiant sa forme pour obtenir unparalllpipde, on peut jouer sur la ddection des dissemblances et dfavoriser lesdformations gomtriques au profit des variations de niveaux de gris ou inversement.38Chapitre 7Phase de test7.1 Le panel dimages testsLa difficult en imagerie mdicale est que nous ne disposons pas de donnesstandards comme les clichs de Lenna ou de Barbara. De plus chaque modalit ragitdiffremment au traitement, ce qui accrot considrablement le nombre dimagesncssaires la constitution du panel reprsentatif. Nous avons retenu 133 imagesrparties comme suit: Rsonance magntique: 38 clichs. Mdecine nuclaire: 25 clichs dont 22 PETs. Scanner X: 59 clichs. Non mdicales: 11 clichs.7.2 Quels sont les besoins?Le protocole que nous devons mettre en place doit permettre de rpondre cesdeux questions, pour chaque chane de tatouage : Quelle est la taille de donnes quil est possible dembarquer? A quantit embarque constante, quelle est la qualit des images marques?Nous ne pouvons savoir exactement a priori ni la qualit ni la quantit dinfor-mations que nous pourrons embarquer. Voil pourquoi, nous chercherons mesurerdiffrents paramtres annexes qui nous donnerons des indices pour rpondre auxquestions poses : Le maximum dinformations embarques. Les dgradations engendres. Linfluence du seuil (diffrent pour chaque algorithme) sur la quantit embar-que et sur la qualit des images.39Dautres part, la phase de test devra permettre une comparaison entre les dif-frentes mthodes de mesure des dgradations et dissimilarits entre les images. Lacomparaison des rsultats pour les diffrentes mthodes de tatouages sur un seulclich montre la difficult de trouver une mthode dvaluation unique.7.3 Le protocole de test7.3.1 Mthodes de tatouagesPour chaque image, nous allons appliquer les mthodes de marquages de Diffrences-Expansions et de Prdictions-Expansions suivant sept niveaux de seuils (0%, 10%,25%, 50%, 75%, 90%, 100%) avec trois algorithmes de compressions diffrents (RLEnon modifi utilis lors du prcedent stage, RLE amlior et JBIG). Par image, il ya donc 2x7x3=42 tests effectus.Pour chaque test, nous notons la quantit de bits librs, la capacit par pixel lib-re (i.e. la quantit divise par la taille de limage), le PSNR et lcart quadratiquemoyen.La distance de Baddeley demandant un nombre important de calculs, elle sera r-serve un nombre limit de squence de test.7.3.2 Algorithmes de compression et cryptagesLes algorithmes de compressions et de cryptages seront tests sur les fichiers derapport 4Dwrite issus de la base de donnes 4D du service de mdecine nuclaire delhpital Larrey.40Chapitre 8Rsultats et interprtations8.1 Mthodes de tatouage8.1.1 Algorithme de CellikCette mthode de tatouage est uniquement disponible, pour linstant, sous formede programme binaire (sans source) et nest capable de tatouer que des images auformat 8 bits. Nous ne pouvons donc lutiliser sur lensemble du panel dimages(uniquement les images non-mdicales). Nous ne ltudierons donc pas pour linstant.8.1.2 Algorithme de FridrichRsultatsTaille des images Nombre de bits librs Capacit128x128 -400 -0.024256x256 240 0.0037512x512 400 0.0015Tab. 8.1 Tatouage par la mthode de FridrichObservations et interprtationsCette mthode ne libre pas assez de place pour insrer la marque sur des imagesmdicales. Elle ne pourra donc pas tre utilise telle quelle. Les fonctions de per-mutations et de discriminations ne semblent pas adaptes limagerie mdiacle:cet algorithme constitue un brevet qui a t dpos par Kodak aux tats-Unis, lesfonctions publies dans les articles de Fridrich [5] ne sont donc pas optimises.418.1.3 Algorithme de TianRappels des travaux prcdentsLorsque le seuil augmente, la capacit embarque augmente jusqu saturation(figure 8.1). En effet, plus le seuil augmente plus le nombre de pixels marqus par ex-tension augmente et donc le flux de bits conserv aprs le marquage par modificationdu bit de poids faible diminue, la capacit embarque augmente alors. La saturationest due la limite de la compression de la carte de localisation par lalgorithme decompression.Nanmoins, nous pouvons noter que plus le seuil augmente plus la dgradation estimportante (Le PSNR diminue) (figure 8.2) La mthode de marquage par expansionest plus dgradante que la mthode de marquage par modification du bit de poidfaible. En consquence, plus la capacit augmente plus limage est dgrade (Figure8.3).Fig. 8.1 Capacit libre en fonction du seuil42Fig. 8.2 Dgradation engendre en fonction du seuilFig. 8.3 Dgradation engendre en fonction de la capacit43Amliorations par modification des algorithmes de compressionLtude prcdente utilisait une mthode de compression spatiale RLE (RunLength Encoding) simple. Nous allons comparer cette mthode de compression avecdeux nouvelles mthodes RLE modifi (utilisation de compression statitisque etadaptation aux donnes embarquer) et JBIG.Fig. 8.4 Comparaison de la capacit libre pour diffrents algorithmes de compressiontude sur la capacit Les courbes obtenues (figure 8.4) montrent que JBIGapporte une meilleure capacit que RLE qui est lui mme suprieur pour cettemme capacit au RLE non modifi. Ils permettent de compresser davantage lacarte et le flux de bits et, donc,pour un seuil donn, daugmenter la place libre.44Fig. 8.5 Comparaison de la dgradation engendre pour diffrents algorithmes decompressiontude de la dgradation Les courbes de dgradations (figure 8.5) restent trsproches pour les diffrents algorithme nanmoins JBIG semble tre un peu moinsdestructif.Conclusion JBIG devient donc la mthode la plus intressante de compressionde la carte de localisation pour le tatouage de Tian. Outre son amlioration de lacapacit, elle apporte aussi une diminution de la dgradation. JBIG doit donc treconsidre comme la mthode adopter pour le marquage de Tian.458.1.4 Algorithme Prdiction-ExpansionComme lalgorithme de Prdiction-Expansion marque chaque pixel et non un groupede 2 pixels comme le fait Tian, il devrait tre plus performant. Avant de comparer les deuxmthodes, nous allons tudier seul lalgorithme de Prdiction-Expansion pour savoir si soncomportement est identique lalgorithme de Tian.Capacit en fonction du seuilFig. 8.6 Comparaison de la capacit libre pour diffrents algorithmes de compressionLalgorithme RLE non modifi semble plus performant suivi par JBIG et par RLE(figure 8.6 ). JBIG est cens amliorer la compression donc devrait tre meilleur que RLEnon modifi or lexprience nous montre le contraire. JBIG et RLE peuvent tre moinsperformants dans le cas de la compression de trs grandes plages, provenant de grandesimages, qui peuvent entrainer des dpassements de capacits.Nous allons recommencer ltude en nous limitant des images plus petites que 512par 512 pixels (figure 8.7). Cette fois-ci nous obtenons bien le meilleur rsultat par JBIGpuis RLE et enfin RLE non modifi.46Fig. 8.7 Comparaison de la capacit libre sur lensemble rduitDgradation en fonction du seuilLes mthodes JBIG et RLE se dtachent trs nettement de la mthode RLE nonmodifie. En effet, les deux mthodes les moins dgradantes compressent les donnes embarqer de faon plus bruite. Le marquage de limage en est moins destructif.47Fig. 8.8 Comparaison de la dgradation engendreConclusionSur des images de taille infrieure ou gale 512x512, lalgorithme se comporte commeTian. Il faudra dvelopper de nouvelles mthodes de compression de donnes pour quecette mthode se comporte idalement avec des images plus grandes.488.1.5 Comparaison de Tian et Prdiction-ExpansionCapacit embarqueFig. 8.9 Comparaison de la capacit libreLalgorithme de Prdiction-Expension marquant limage sur lensemble des pixels,et non sur la moiti des pixels comme Tian, permet une augmentation de la capacit.Lalgorithme de Prdiction-Expension est donc le plus efficace.49Dgradation apporte limageFig. 8.10 Comparaison de la dgradation engendreAlgorithme de compression original Du fait mme que Tian garde limage lchelle 1:2 et que lalgorithme de prdiction-Expension modifie lensemble despixels, Tian dgrade moins les images.JBIG et RLE modifi JBIG et RLE modifi apportent du bruit dans la marque,lalgorihtme de Prduction-Expension surpasse alors Tian. En effet, plus la marqueressemble du bruit, mieux elle est intgre limage et les dgradations sontdonc moins perceptibles. La mthode de Prdiction-Expansion avec lalgorithme decompression JBIG surpasse alors toutes les autres mthodes.508.2 Mesure de dissimilaritFig. 8.11 Distance de Baddeley en fonction du seuilLes rsultats obtenus par la distance de Baddeley sont similaires aux rsultatsobtenus par le PSNR: il existe une relation quasiment linaire entre la distance etle rapport signal/bruit (figure 8.12). Le mme effet de saturation apparat partirdun seuil de 50% (figure 8.11).Le calcul de la distance tant trs long, car crit en Matlab, nous conseillonsdutiliser le PSNR pour explorer un large ventail dimage puis Baddeley pour affinerles rsultats.51Fig. 8.12 Distance de Baddeley en fonction du rapport signal/bruit528.3 Mthode de cryptage et de compressionTaille du fichier original (Ko)Taille du fichier crypt et com-press (Ko)Taille du fichier crypt et com-press avec BWT (Ko)5,67 3,56 3,025,92 3,60 3,05Tab. 8.2 Rsultats de la compression et du cryptageLes fichiers compresss affiche une taille infrieur 55% des fichiers originaux.Lintroduction de la Burrow Wheeler Transform, quand elle, permet un gain delordre de 18 % sur un fichier compress uniquement par RLE puis Huffman. Ilest important dutiliser une bonne compression avant le cryptage car le fichier unefois crypt ressemblant fortement du bruit, il est dificille de le compresser. Cetteressemblance au bruit namoins lavantage de rduire la dgradation de limage.53Chapitre 9PerspectivesIl serait intressant de rflchir une mthode de tatouage rversible et robuste certaines attaques. Cette mthode pourrait reconstruire limage seulement si limagena pas t dgrade. Dans la cas contraire, la mthode ne pourrait pas reconstruirelimage mais pourrait en extraire des informations pertinentes comme le dossiermdical.La robustesse peut venir par exemple de la redondance des donnes embarquesou de lutilisation de codes de correction derreurs.Dautres part, certaines modalits utilisent une reprsentation en trois dimen-sions des informations, une gnralisation de lalgorithme de prdiction-expansion ce nombre de dimension serait un moyen de gagner encore en qualit et en quantitde donnes embarques.54Chapitre 10ConclusionCe stage a confort ma volont de poursuivre mon parcours professionnel dansle domaine de la recherche. En effet, ces six derniers mois ont confirm ce que javaisdj pressenti lors de mon stage technique. Je suis actuellement en recherche definancement pour une allocation de recherche en vue de la prparation dune thse.Lapport personnel de ce stage a t trs important, il ma permis daborder lescontraintes spcifiques du milieu mdical qui demandent lutilisation de nouvellestechniques de mesure de qualit et de dissimilarit. Il ma permis dacqurir unebonne connaissance technique du domaine de la cryptologie, domaine que javaisdj abord lors de mon stage de premire anne mais dans une approche pluslgislative.Enfin, jai t marqu par la bonne ambiance de travail et de convivialit au seindu laboratoire dautant plus enrichissante que lunit se trouve linterface de deuxmondes : le millieu scientifique et le milieu hospitalier.55Chapitre 11Rfrences56Bibliographie[1] G. Coatrieux, H. Matre, B. Sankur, Y. Rolland, and R. Collorec.Relevance of watermarking in medical imaging. In Information TechnologyApplications in Biomedicine, EMBS International Conference, pages 250255.IEEE, November 2000.[2] C. Cavaro-Mnard and S. Amiard. Reversible data embedding for integritycontrol and authentication of medical images. July 2004.[3] J. Tian. Reversible data embedding and content authentication using differenceexpansion. IEEE Transaction on Circuits and systems for Video Technology,February 2003.[4] J.Fridrich, M. Goljan, and R.Du. Invertible authentication. In Security andWatermarking of Multimedia contents III, volume 3971, pages 197208. SPIEPhotonics West, January 2001.[5] J.Fridrich, M. Goljan, and R.Du. Lossless data embedding - new paradigmin digital watermarking. Specials Issue on Emerging Applictions of MultimediaData Hiding, 2002(2):185196, February 2002.[6] Mehmet Utku Celik, Gaurav Sharma, Ahmet Murat Te-kalp, and Eli Saber. Lossless generalized-lsb data embedding.http://citeseer.ist.psu.edu/586093.html.[7] X. Wu. Lossless compression of continous-tone images via context selec-tion, quantization, and modelling. IEEE Transactions on Image Processing,6:656:664, May 1997.[8] Bruce Schneier. Applied cryptography, second edition. John Wiley and Sons,1998.[9] http://www.pgp.com/.[10] http://www.gnupg.org/.[11] http://gnumex.sourceforge.net/.[12] http://gcc.gnu.org/.[13] http://botan.randombit.net/.[14] http://www.gnu.org/directory/libgcrypt.html.[15] http://www.gnu.org/.57[16] Yousra Chehadeh. Oprateurs locaux de distance en maillages rectangulaireset parallelepipediques: application lanalyse dimage. PhD thesis, Universitde Savoie, 1997.58Table des figures2.1 Rpartition des cls pour 6 intervenants . . . . . . . . . . . . . . . . 146.1 Distance du pixel la surface de rfrence . . . . . . . . . . . . . . . 326.2 Parcours de limage . . . . . . . . . . . . . . . . . . . . . . . . . . . . 356.3 Parcours de limage . . . . . . . . . . . . . . . . . . . . . . . . . . . . 378.1 Capacit libre en fonction du seuil . . . . . . . . . . . . . . . . . . 428.2 Dgradation engendre en fonction du seuil . . . . . . . . . . . . . . . 438.3 Dgradation engendre en fonction de la capacit . . . . . . . . . . . 438.4 Comparaison de la capacit libre pour diffrents algorithmes de compression 448.5 Comparaison de la dgradation engendre pour diffrents algorithmes decompression . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 458.6 Comparaison de la capacit libre pour diffrents algorithmes de compression 468.7 Comparaison de la capacit libre sur lensemble rduit . . . . . . . 478.8 Comparaison de la dgradation engendre . . . . . . . . . . . . . . . . . 488.9 Comparaison de la capacit libre . . . . . . . . . . . . . . . . . . . 498.10 Comparaison de la dgradation engendre . . . . . . . . . . . . . . . 508.11 Distance de Baddeley en fonction du seuil . . . . . . . . . . . . . . . 518.12 Distance de Baddeley en fonction du rapport signal/bruit . . . . . . . 52A.1 Construction du code du message eaii! . . . . . . . . . . . . . . . . . 6259Liste des tableaux2.1 Tableau rcapitulatif : partie 1 . . . . . . . . . . . . . . . . . . . . . . 162.2 Tableau rcapitulatif : partie 2 . . . . . . . . . . . . . . . . . . . . . . 174.1 Rsum des droits daccs . . . . . . . . . . . . . . . . . . . . . . . . 246.1 Tableau de Chanfrein . . . . . . . . . . . . . . . . . . . . . . . . . . . 336.2 Matrice de prcdence du premier parcours . . . . . . . . . . . . . . . 346.3 Tableau de Chanfrein tendu la troisime dimension . . . . . . . . . 346.4 Matrice de prcdence tendue la troisime dimension . . . . . . . . 346.5 Image de dpart . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 356.6 Matrice initiale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 356.7 Calcul du Pixel (1,1) . . . . . . . . . . . . . . . . . . . . . . . . . . . 366.8 Calcul du Pixel (4,3) . . . . . . . . . . . . . . . . . . . . . . . . . . . 366.9 Matrice obtenue la fin du premier parcours . . . . . . . . . . . . . . 366.10 Matrice de prcdence retourne 180 . . . . . . . . . . . . . . . . . 376.11 Matrice transforme distance . . . . . . . . . . . . . . . . . . . . . . . 378.1 Tatouage par la mthode de Fridrich . . . . . . . . . . . . . . . . . . 418.2 Rsultats de la compression et du cryptage . . . . . . . . . . . . . . . 53A.1 Partition de lintervalle [0 1[ pour lalphabet (a,e,i,o,u,!) . . . . . . . 6260Annexe AAlgorithmesA.1 Mthode des LSBLa mthode des LSB (Low State Binary ou bits de poids faible) est une mthodesimple et bien connue. Elle consiste remplacer les bits de poids faibles pour y insrerde nouvelles donnes. Etant donn que lon ne modifie quun seul bit, la capacitC en bit par pixel (bpp) est de 1. Cette mthode est invisible,peu robuste maissurtout totalement irrversible. En effet la suppression des bits de poids faibles delimage originale entrane certes une faible variation du niveau de gris (1/256 pourune image 8 bits, 1/65536 pour une image 16 bits) mais une perte dinformationdfinitive. Laugmentation de la taille des donnes insrer et donc de la capacit C(C= 2 ...bpp) est possible en changeant le nombre de bits de poids faibles modifis(2 et plus). En contrepartie, la dgradation de limage augmente et la mthode restetoujours irrversible.A.2 Mthode des LSB gnralise : G-LSBLa capacit C de la mthode LSB est C=n avec n IN. La mthode G-LSB sepropose de rendre C granulaire de telle manire que C=n avec n ZZ+.A.3 Le Codage ArithmtiqueLe codage arithmtique attribue une valeur relle une suite de symboles. Leprincipe de base consiste diviser lintervalle des rels [0 1[ en sous-intervalles dontles longueurs sont fonction des probabilits des symboles. Au fur et mesure ducodage des symboles, la longueur de lintervalle diminue en tenant compte du modle61et du sous-intervalle prcdent.Symboles Probabilit partition Initialea 0,2 [0 0,2[e 0,3 [0,2 0,5[i 0,1 [0,5 0,6[o 0,2 [0,6 0,8[u 0,1 [0,8 0,9[! 0,1 [0,9 1,0[Tab. A.1 Partition de lintervalle [0 1[ pour lalphabet (a,e,i,o,u,!)Intevalle de travail : [0 1,0[Symbole traiter : e(1,0 0) [0,2 0,5[+0 = [0,2 0,5[Symbole traiter : a(0,5 0,2) [0 0,2[+0,2 = [0,2 0,26[Symbole traiter : i(0,26 0,2) [0,5 0,6[+0,2 = [0,230 0,236[Symbole traiter : i(0,236 0,230) [0,5 0,6[+0,230 = [0,233 0,2336[Symbole traiter : !(0,2336 0,233) [0,9 1,0[+0,233 = [0,23354 0,2336[Tout rel appartenant lintervalle [0,23354 0,2336[ code le message eaii!Fig. A.1 Construction du code du message eaii!62Annexe BIntroduction la programmationdune DLL en CCe document a t ralis dans un but pdagogique pour faciliter lcriture deDLL en C pour tout autre personne du laboratoire. Ce document est mettre jour pour expliquer linstallation et la configuration de gcc et de loutil gnumexpour Matlab r. Gcc permet de compiler en C, en Cpp, en Fortran et Java ...63

Recommended

View more >