Brevet FR2681750A1 — publié le 19930326

i PROCEDE DE COMPRESSION D'IMAGES La présente invention concerne un procédé de compression d'images Elle s'applique notamment dans les domaines de la transmission ou du stockage d'images. La compression d'images consiste à réduire la quantité de données nécessaire pour représenter une image La quantification vectorielle exposée dans l'article de R M GRAY "Vector Quantization" paru dans la revue IEEE ASSP Magazine d'Avril 1984 est une méthode de compression d'images qui a été largement utilisée Cette méthode consiste à découper l'image en blocs et à remplacer chaque bloc par un index Cet index se rapporte à un dictionnaire contenant un nombre limité de blocs représentatifs La constitution du dictionnaire est réalisée suivant l'algorithme des "k-means" développé dans l'article de J MAC QUEEN "Some methods for classification and analysis of multivariate observations" paru dans le catalogue " 5th Berkeley Symposium on Mathematics, statistic and probabilities" de 1967 ou suivant l'algorithme LBG exposé dans l'article de Y LINDE, A BUZO et R M GRAY "An algorithm for Vector Quantizer Design" paru dans la revue IEEE Communications de Janvier 1980. L'utilité de la compression est évidente quand il s'agit de transmettre ou de stocker des images Néanmoins, les méthodes précitées ont encore des taux de compression médiocres et il n'est pas toujours possible de réduire de façon significative la quantité de données nécessaire à la représentation de l'image tout en conservant à celle-ci une bonne qualité Ces faibles taux de compression entraînent des problèmes de place mémoire dans les systèmes de stockage ou d'encombrement dans les lignes de transmission dont les bandes passantes ne sont pas extensibles. Le but de l'invention est de pallier les inconvénients précités A cet effet, l'invention a pour objet un procédé de compression d'images comprenant une première étape de quantification vectorielle o une image source est décomposée en blocs, chaque bloc étant comparé aux éléments d'un dictionnaire en vue de le remplacer par l'index de l'élément du dictionnaire qui s'en rapproche le plus, de manière à obtenir une image comprimée et cohérente par rapport à l'image source caractérisée en ce que cette première étape est suivie d'une deuxième étape de compression de l'image comprimée suivant une méthode de prédiction. L'invention a pour principal avantage qu'elle permet d'améliorer le taux de compression de l'image sans perte de qualité au niveau de celle-ci. D'autres caractéristiques et avantages de l'invention apparaîtront à l'aide de la description qui suit, faite en regard des dessins annexés qui représentent: La figure 1: un organigramme de la compression d'images selon l'invention. La figure 2 une illustration de l'algorithme de construction d'un dictionnaire de blocs de pixels améliorant les performances du procédé selon l'invention. La figure 3 a: une illustration des blocs du dictionnaire utilisé par l'invention et des blocs issus d'un ensemble d'apprentissage. La figure 3 b: une illustration des domaines associés à chacun des blocs du dictionnaire utilisé par l'invention. La figure 1 présente un organigramme de la compression d'images selon l'invention Dans une première étape de quantification vectorielle 1, l'image source 2 est découpée en blocs, chaque bloc est comparé aux éléments du dictionnaire 3 qui s'en rapproche le plus. L'image comprimée est obtenue lorsque tous les blocs de l'image source ont été remplacés par un index Cette image est l'image des index 4. Le procédé, selon l'invention, utilise une méthode de quantification vectorielle qui conserve à l'image des index 4 une cohérence par rapport à l'image source 2 de façon à pouvoir utiliser cette image des index 4 comme entrée d'une deuxième étape 5 de compression utilisant selon l'invention une méthode de prédiction A cet égard, et afin d'améliorer la prédiction le procédé utilise dans la première étape 1 un dictionnaire 3 construit selon l'algorithme illustré par la figure 2 L'algorithme commence par une première étape d'initialisation des éléments du dictionnaire 21 Ces éléments sont des blocs choisis de manière aléatoire et sont représentés par des vecteurs Le dictionnaire 3 peut contenir par exemple M éléments notés Wj o j est un indice appartenant aux nombres entiers compris entre O et M 1 inclus j représente l'index du bloc représenté par le vecteur Wj, ce bloc est appelé bloc d'index j Les composantes du vecteur Wj sont les luminances des pixels du bloc d'index j Ces luminances sont par exemple codées sur 8 bits et ont des valeurs comprises entre O et 255 La figure 3 a représente la projection du lieu géométrique des vecteurs Wj suivant deux composantes associées à deux pixels successifs pris deux à deux dans le sens de balayage de 1 ' l'image source 2 Les ronds représentent les vecteurs Wj associés aux blocs du dictionnaire et les points les blocs de l'image Ces blocs sont extraits d'un ensemble d'apprentissage A contenant un grand nombre de blocs extraits d'une ou plusieurs images, sont très nombreux et sont extraits d'une ou plusieurs images Les axes Il et 12 indiquent les luminances des deux pixels successifs codés entre O et 255 Chaque vecteur Wj génère un domaine Dj comprenant des vecteurs x représentant des blocs de l'ensemble d'apprentissage A précité La figure 3 b représente les domaines Dj associés aux vecteurs Wj, ces domaines sont séparés par des traits pleins Une loi d'initialisation des blocs du _-> dictionnaire 3 peut, par exemple, définir les vecteurs Wj par W = j/ +b ij o Wij est la composante de rang i du vecteur Wj, ij 2 fls ns un nombre entier choisi par exemple de telle sorte que 2 ns soit égal au nombre de niveaux de gris de l'image source et bij un bruit de densité uniforme compris par exemple entre -5 et 5. L'étape 21 est suivie d'une étape 22 de mise à jour des domaines -> précédemment définis Un domaine Dk associé au vecteur Wk représentant un bloc du dictionnaire 3 d'index k est mis à jour de la manière suivante selon l'algorithme des k means précédemment cité chaque nouveau vecteur x appartenant à Dk est déterminé par la relation ú=M-11 _ __ 112 M-1 _ 114 142 cake x _W 1 = 0 1 = O quelque soit l'indice j différent de l'indice k. Les coefficients a k I, e je relatifs respectivement aux domaines Dk et Dj traduisent les interactions topologiques à l'intérieur du dictionnaire Un coefficient a jk traduisant les interactions entre le domaine Dj et le domaine Dk est par exemple défini à l'itération t par - (j-k)2 2 ajk(t) = e t avec u t=al T étant le nombre d'itérations totales préalablement déterminé. î 1 correspond à la première itération, il peut prendre par exemple une valeur comprise entre 1 et 10. îr T correspond à la dernière itération, il exemple une valeur comprise entre 0,1 et 1. peut prendre par L'étape 22 est suivie d'une étape 23 de mise à jour des éléments du dictionnaire Un vecteur Wj représentant du dictionnaire est mis à jour par la relation: -4 un bloc d'index j k=M-1 -> 1 ajk pk bk k= O k-M-1 Y ajk pk k= O ajk est le coefficient précédemment défini. Pk est la probabilité qu'un bloc de l'ensemble d'apprentissage ait son vecteur associé x qui appartient à un domaine Dk précédemment défini. bk est un vecteur dont l'extrémité représente le barycentre des extrémités des vecteurs du domaine Dk. L'étape 23 est suivie d'une étape de test d'arrêt Si le nombre d'itérations déjà effectuées est égal au nombre total T accordé, la construction du dictionnaire 3 est achevée Dans le cas contraire, l'étape 24 est suivie à nouveau de l'étape 22 de mise à jour des domaines Le nombre total T d'itérations est par exemple égal à quelques centaines et permet d'obtenir des résultats satisfaisants L'algorithme de constitution du dictionnaire 3 selon l'invention revient en fait à réaliser des mises à jour successives des domaines et des éléments du dictionnaire Cet algorithme permet avantageusement de converger vers une meilleure définition du dictionnaire Par ailleurs, les contenus des blocs d'index proches dans le dictionnaire sont presque semblables, cette conservation de la topologie permet de conserver une cohérence de l'image des index 4 par rapport à l'image source 2 et autorise la mise en oeuvre de la seconde étape 5 du procédé selon l'invention de compression de l'image des index 4 suivant une autre méthode de prédiction comme le montre la figure 1 L'opérateur de prédiction peut être par exemple un réseau de neurones multicouches Un algorithme d'apprentissage permet d'obtenir les coefficients 6 de ce réseau Pour prédire la valeur de l'index i (x, y) situé dans l'image comprimée à la colonne x et à la ligne y, le réseau de prédiction 5 reçoit en entrée un vecteur élaboré à partir de quatre pixels voisins dans l'image comprimée dont les index sont i (x-1, y-1), i(x, y-1), i(x+ 1, y-1) et i(x-1, y) La prédiction de i(x, y) obtenue en sortie de la deuxième étape 5 est notée î(x, y) Afin de ne pas induire de perte de qualité, les erreurs de prédiction i(x, y) î(x, y) sont transmises avec l'index i(x, y) correspondant, à un codeur 8 après une élaboration de cette erreur 7 L'erreur de prédiction peut être par exemple codée suivant un code de HUFFMAN, présenté dans l'ouvrage de Georges CULLMANN "Codage et transmission de l'information" (pp 87-88), Eyrolles, 1968. La nouvelle image comprimée et codée peut ainsi être stockée dans une mémoire de masse ou transmise par exemple, et cela avec un très bon taux de compression pour une qualité d'image reconstituée satisfaisante. REVENDICATIONS 1 Procédé de compression d'images comprenant une première étape ( 1) de quantification vectorielle o une image source ( 2) est découpée en blocs, chaque bloc étant comparé aux éléments d'un dictionnaire ( 3) en vue de le remplacer par l'index de l'élément du dictionnaire ( 3) qui s'en rapproche le plus, de manière à obtenir une image comprimée ( 4) et cohérente par rapport à l'image source ( 2), caractérisé en ce que cette première étape ( 1) est suivie d'une deuxième étape ( 5) de compression de l'image comprimée suivant une méthode de prédiction. 2 Procédé selon la revendication 1, caractérisé en ce que le dictionnaire ( 3) est construit suivant un algorithme qui réalise des mises à jour successives des éléments du dictionnaire ( 23) et des domaines ( 22) associés à ces éléments, ces domaines comprenant des blocs d'images issus d'un ensemble d'apprentissage réalisé à partir d'une ou plusieurs images. 3 Procédé selon l'une des revendications 1 et 2 caractérisé en ce que les mises à jour des éléments du dictionnaire et des domaines font intervenir des interactions topologiques cijk, qui permettent de conserver la cohérence topologique du dictionnaire. 4 Procédé selon l'une des revendications 1 et 2, caractérisé en ce que l'algorithme de construction du dictionnaire ( 3) réalise les mises à jour suivant un nombre total d'itérations prédéterminé. 5 Procédé selon l'une quelconque des revendications précédentes, caractérisé en ce que le dictionnaire ( 3) est initialisé avec des éléments choisis de façon aléatoire. 6 Procédé selon l'une quelconque des revendications précédentes, caractérisé en ce que l'étape de prédiction ( 5) est réalisée suivant un réseau de neurones multicouches. 7 Procédé selon l'une quelconque des revendications précédentes, caractérisé en ce que l'erreur de prédiction ( 7) est codée suivant un code de HUFFMAN ( 8).