Brevet FR2655450A1 — publié le 19910607

La présente invention se rapporte à un procédé de compression par blocs d'images numériques, par autoorganisation, d'un réseau neuronal. La technique de compression d'images consiste à réduire la quantité de données nécessaires pour représenter une image. Cette technique est très utilisée dans les domaines des transmissions ou du stockage d'images. Lorsqu'une image comprimée est décodée pour reconstruire sa forme originale, une distorsion affecte l'image reconstruite. Par conséquent, l'efficacité d'un algorithme de compression se mesure à la fois par son taux de compression, la distorsion résultante, sa complexité d'implémentation. La complexité d'implémentation est un point particulièrement important pour la réalisation matérielle des codeurs et des décodeurs. Les principales méthodes de compression par blocs d'images numériques connues utilisent des algorithmes tels que la transformation de Karhunen-Loève, la transformation de Hadamard, la transformation cosinus, la quantification vectorielle. Ces algorithmes sont implémentés sur des machines séquentielles pour lesquelles le traitement des données est lent et des manipulations manuelles sont nécessaires lorsqu'il faut s'adapter à un type d'image différent. En intelligence artificielle, les réseaux neuronauxconnexionistes ou neuro-mimétiques connaissent actuellement un regain d'intérêt, et l'architecture des réseaux neuronaux possède intrinsèquement un potentiel de traitement parallèle massif. Le traitement des données en parallèle permet un gain de temps considérable par rapport aux machines séquentielles, mais les algorithmes utilisés jusqu'à présent pour la compression d'images sont adaptés aux machines séquentielles et leur parallélisation est peu aisée. L'invention concerne une nouvelle méthode de compression d'images entièrement automatique quel que soit le type d'image à comprimer, simple à mettre en oeuvre, qui utilise un algorithme directement compatible avec les futures machines connexionistes massivement parrallèles qui seront développées dans les prochaines années. Cette méthode est basée sur la notion d'apprentissage, ce qui lui permet de s'adapter au mieux à un type d'image particulier, tel que les images télévision, les images aériennes, etc ..., et donc de fournir une faible distorsion pour ce type d'image. De plus, le système peut être rapidement reconfiguré pour s'adapter à un autre type d'image simplement en relançant un apprentissage sur des images de ce type. Selon l'invention, le procédé de compression d'images par auto-organisation d'un réseau neuronal est caractérisé en ce qu'il consiste - à traiter un bloc de pixels courant déplacé dans l'image à comprimer en utilisant un réseau de N neurones, 1 à N, disposés dans un même plan, chaque neurone ayant un nombre d'entrées égal à la dimension des blocs extraits de l'image, et tels que, après une phase d'apprentissage pendant laquelle le réseau s'est auto-organisé de façon que les neurones représentent des valeurs d'entrées les plus probables, chaque neurone j reçoit, au même instant, sur ses entrées les pixels du bloc courant et délivre en sortie un signal, ou potentiel, dj, qui est positif et d'autant plus faible que l'état du neurone j correspondant est voisin de l'état des entrées ei, - à coder le bloc de pixels courant par un code associé au neurone j dont le potentiel d. est minimal. D'autres particularités et avantages de l'invention apparaîtront clairement dans la description suivante donnée à titre d'exemple non limitatif, et faite en regard des figures annexées qui représentent - la figure 1, la structure générale des réseaux neuronaux de Kohonen; - la figure 2, un exemple de réseau neuronal selon l'invention; - la figure 3, un organigramme de la phase d'apprentissage, selon l'invention - la figure 4, un exemple de variation de l'étendue du voisinage en cours d'apprentissage, selon l'invention; - la figure 5, un organigramme de la phase de compression d'une image source, selon l'invention; - la figure 6, un organigramme du décodage d'une image comprimée, selon l'invention. La figure 1 montre la structure générale des réseaux neuronaux dits de Kohonen. Ce type de réseau ne comprend qu'une seule couche de N neurones disposés dans un même plan. Chaque neurone est connecté à toutes les entrées e1 . . . ex qui sont destinées à recevoir des données telles que par exemple des pixels extraits d'une image. Entre les neurones de cette couche, il y a des connexions internes, de type excitatrices si les neurones sont proches voisins ou inhibitrices s'ils sont éloignés. La notion de voisinage dépend de la distance entre les neurones. Ces réseaux de neurones à connexions latérales simulent partiellement la structure des aires V17 et V18 du cortex visuel. Ils s'auto-organisent naturellement en fonction des entrées reçues pour réagir à un groupe de données qui ont des caractéristiques semblables ; un neurone et ses voisins représentent une catégorie d'entrées. Après une phase d'apprentissage qui consiste en une recherche de similarités, ces réseaux réalisent une compression des données dont la nature s'apparente formellement à la quantification vectorielle, c'est-à-dire qu'à un groupe de données correspond un vecteur caractéristique. Dans une image en niveaux de gris découpée en blocs de par exemple n x n pixels, certaines configurations sont beaucoup plus probables que d'autres. Dans une phase d'apprentissage, l'utilisation d'un réseau de neurones à connexions latérales permet de découvrir ces configurations les plus probables. A cet effet, le réseau neuronal représenté sur la figure 2 comporte N neurones numérotés de 1 à N dont les entrées sont des blocs n x n (par exemple n = 4 ou 8) extraits d'une image de dimension très grande devant n. Le nombre d'entrées nécessaires pour chaque neurone est égal à la dimension du bloc de pixels extrait de l'image. Dans le cas de 2 blocs n x x pixels, chaque neurone comporte au moins n entrées et une sortie. Le réseau est bouclé préférentiellement en anneau pour éviter les effets de bord, c'est-à-dire de façon que tous les neurones soient entourés du même nombre de neurones voisins. Les neurones j reçoivent tous les mêmes entrées qui sont à un instant donné, les n2 pixels du bloc n x n extraits de l'image et délivrent en sortie leur réponse dj à ces entrées. Dans une phase d'apprentissage, le réseau de neurones est alimenté par des blocs extraits aleatoirement, d'une ou plusieurs images de même type (par exemple des images aériennes). A chaque connexion neuronale liant une entrée ei à un neurone de numéro j, est affecté un coefficient, dit poids de la connexion wij, qui est ajusté par approches successives jusqu a ce que les configurations les plus fréquentes soient repérées par les poids des connexions neuronales. Outre les connexions entre un neurone j et toutes les entrées ei, la définition d'un rayon de voisinage du neurone j permet à d'autres neurones du réseau appartenant à ce voisinage d'apprendre en même temps.Ce rayon de voisinage est choisi élevé au début des itérations afin que beaucoup de neurones apprennent en même temps et diminue en cours d'apprentissage jusqu a un minimum correspondant à un seul voisin en fin d'apprentissage, de façon à faciliter la différenciation des neurones lorsque le nombre d'itérations augmente. Par exemple, pour un réseau de N = 512 neurones, un voisinage initial Vo = 128 et un voisinage final VT = O, 5 sont des valeurs bien adaptées. Pour cette phase d'apprentissage, l'algorithme d'auto-organisation utilisé est l'algorithme de Kohonen dont l'organigramme est représenté sur la figure 3. Cet algorithme est choisi pour sa totale compatibilité avec les futures machines connexionistes pour lesquelles le traitement des données s'effectue en parallèle et comporte les étapes suivantes Dans une première étape est effectuée l'initialisation du réseau, 1; les poids W.. des connexions neuronales entre iJ un neurone j et les entrées ei sont initialisés pour chacun des neurones et l'étendue d'un rayon de voisinage initial Vo est choisi.Les valeurs initiales des poids des connexions neuronales sont fixées aléatoirement selon une loi de probabilité uniforme sur les niveaux de gris possibles, ces niveaux étant situés généralement entre 0 et 255, c'est-à-dire que les valeurs des poids Wij sont comprises entre O et 255. La valeur initiale de l'étendue du voisinage VO est définie par l'utilisateur. Dans une deuxième étape, à la première itération, 2, il est procédé à l'extraction d'un bloc n x n, 3, sur une image et au calcul des potentiels, 4, de chacun des neurones, ce calcul étant effectué en parallèle. Un bloc n x n pixels est extrait aléatoirement de l'image, les n2 pixels du bloc sont présentés aux entrées du réseau de neurones, et les potentiels d. de tous les neurones j du réseau sont calculés par la formule suivante pour tous les neurones j où W est le poids de la connexion liant l'entrée i au neurone j ; e. est le niveau de gris du ie pixel du bloc extrait sur l'image. Il est à remarquer que d. est une fonction positive qui mesure l'écart entre l'état du neurone j et l'état des entrées ei ; dj est une distance entre le vecteur des poids wij et le vecteur des entrées ei. Dans une troisième étape, il y a détermination du neurone "vainqueur", 5, et ajustement des poids pour les neurones compris dans le voisinage du neurone vainqueur, 6. Le neurone jO qui se rapproche le plus des entrées est recherché. il est tel que son potentiel d. est minimal. Les poids des connexions liant les entrées e. au neurone Jo, dit "neurone vainqueur", à ses voisins sont modifiés selon la formule suivante, où t est le rang de l'itération, est la constante d'apprentissage, V est l'étendue du voisinage pour le rang d'itération t. wij(t+1)=wij(t)+ # (ei(t)-wij(t)) pour tous les neurones j tels que |(j-j0)mod N| @V, de façon que le neurone j et tous les neurones appartenant au voisinage du neurone j aient leurs poids qui se rapprochent des valeurs des entrées. Pour les neurones j situés à l'extérieur du voisinage V, les poids des connexions liant les entrées e. aux neurones j sont inchangés : W.. (t+1) = W.. (t) pour les neurones j tels que |(j-j0)mod N| > V. La vitesse d'apprentissage dépend de la valeur de la constante d'apprentissage # doit être comprise entre 0 et 1. Par exemple, # est choisi égal à 0,1 de façon à ce que les variations des poids à chaque itération ne soit pas trop importantes et à ce que le temps d'apprentissage ne soit pas trop long. Il y a ensuite restriction du rayon de voisinage, 7, et un test 8 est effectué pour savoir si toutes les itérations ont été effectuées; si le test 8 est négatif il y a passage à l'itération suivante, 9, en reprenant toutes les étapes 3 à 7, de l'organigramme avec un nouveau bloc n x n pixels extrait aléatoirement d'une image. L'étendue du voisinage V est réduite en cours d'apprentissage de façon à faciliter la différentiation des neurones lorsqu'ils se sont rapprochés des configurations des entrées les plus probables. La figure 4 montre un exemple de variation de l'étendue du voisinage en cours d'apprentissage. Sur l'exemple de la figure 4, il a été choisi une loi exponentielle décroissante qui s'écrit V= VO exp (-t/K) mais tout autre loi décroissante pourrait convenir. où VO est le voisinage initial, t est le rang de l'itération et K est une constante positive. La valeur de K est choisie de façon à ce qu a la fin de l'apprentissage, c'est-à-dire à la dernière itération, la valeur du voisinage V soit minimale. il faut un grand nombre d'itérations pour que le réseau s 'auto-organise : par exemple pour un réseau de 512 neurones et une image de 512 x 512 pixels, 32000 blocs 8 x 8 pixels, soit 32000 itérations, permettent une bonne convergence de l'algorithme de Kohonen, avec les paramètres suivants T = 0,1 pour le taux d'apprentissage Vo = 128 pour le voisinage initial VT = 0,5 pour le voisinage final. Lorsque le processus d'auto-organisation est stabilisé, c'est-à-dire que le test 8, figure 3, indique que la dernière itération a été atteinte, les poids des connexions neuronales sont gelés, par la sauvegarde 10 de ces poids et le réseau de neurones peut être utilisé à des fins de compression. La figure 5 représente l'organigramme correspondant à la compression d'une image source. Pour la phase de compression, l'image à comprimer est découpée en blocs n x n, étape 11, et il y a extraction, 12, du premier bloc de l'image. Pour chaque bloc, les n2 pixels du bloc sont présentés aux entrées du réseau de neurones. Les potentiels des neurones sont calculés, étape 13, et le neurone jO dont le potentiel d. JO est minimal est recherché, étape 14. Le bloc n x n correspondant à ce neurone dit "neurone vainqueur" est alors codé par le numéro de ce neurone, par une étape de codage 15, chaque neurone étant numéroté de 1 à N, N = 512 par exemple. Un test 16 est effectué pour savoir si ce bloc est le dernier bloc de l'image, si non il y a extraction, 17, du bloc suivant sur l'image. Les n2 pixels du bloc suivant sont alors, à leur tour, présentés aux entrées du réseau de neurones et un nouveau neurone est déclaré "vainqueur", ce bloc est alors codé par le numéro de ce neurone ; et ainsi de suite jusqu a ce que tous les blocs de l'image source soient codés. Lorsque tous les blocs n x n constituant l'image sont codés, l'image est transmise. Si b est le nombre de bits par pixel dans l'image p et N est le nombre de neurones, le taux de compression Tc obtenu est le suivant Tc= bp (image source) /bp (image codée) Tc= bp x n2/log2N Ce taux de compression peut être amélioré en utilisant un codage à longueur variable, tel que par exemple un codage de Huffman, pour les numéros des neurones. Un codage à longueur variable permet de coder sur une longueur plus courte les numéros des neurones revenant plus fréquemment. La figure 6 représente l'organigramme correspondant au décodage de l'image comprimée. A la réception de l'image, pour décoder l'image comprimée, il suffit de faire les opérations inverses du codage, c'est-à-dire, de remplacer les numéros de l'image codée par les poids des connexions des neurones correspondant à ces numéros. Chaque code est regardé séparément, en commençant par le premier,20, il est procédé au remplacement de ce code par les poids du neurone correspondant, 21, un test,22, détermine s'il s'agit du dernier code, si non le code suivant,23, est présenté et ainsi de suite jusqu'au dernier code. L'image est reconstruite lorsque tous les codes ont été décryptés. La présente invention n'est pas limitée aux exemples de réalisation précisément décrits ; notamment il n'est pas indispensable que le réseau de neurones soit bouclé en anneau, un réseau de neurones disposés en ligne peut être utilisé à condition de tenir compte des effets de bord. De même, il n'est pas indispensable que la décroissance de l'étendue du voisinage en cours d'apprentissage suive une loi exponentielle ; toute loi permettant de faire décroître l'étendue du voisinage en cours d'apprentissage, par exemple une loi linéaire qui aurait comme voisinage initial VO et un voisinage final minimal, peut convenir également. Il n'est pas indispensable, non plus, que la dimension des blocs extraits de l'image soit n x n, les blocs peuvent avoir une dimension n x k, n étant différent de k. L'image source, dans l'exemple décrit est en niveau de gris, pour une image couleur, le procédé convient aussi bien mais avec trois fois plus de valeurs de pixels puisqu'il faut rajouter les valeurs chrominances. Pour coder l'image, dans l'exemple décrit, les N neurones ont été numérotés de 1 à N; tout autre codage permettant de repérer les neurones vainqueurs convient. REVENDICATIONS 1. Procédé de compression d'images par autoorganisation d'un réseau neuronal, caractérisé en ce qu'il consiste - à traiter un bloc de pixels courant déplacé dans l'image à comprimer en utilisant un réseau de N neurones, I à N, disposés dans un même plan, chaque neurone ayant un nombre d'entrées égal à la dimension des blocs extraits de l'image, et tels que, après une phase d'apprentissage pendant laquelle le réseau s'est auto-organisé de façon que les neurones représentent des valeurs d'entrées les plus probables, chaque neurone;; reçoit, au même instant, sur ses entrées, les pixels du bloc courant et délivre en sortie un signal, ou potentiel, d., qui est positif et d'autant plus faible que l'état du neurone j correspondant est voisin de l'état des entrées ei, - à coder le bloc de pixels courant par un code associé au neurone j dont le potentiel dj est minimal. 2. Procédé selon la revendication 1, caractérisé en ce que dans une phase d'apprentissage, le réseau de neurones est préalablement auto-organisé selon l'algorithme de Kohonen. 3. Procédé selon la revendication 2, caractérisé en ce qu'il comprend - une phase d'initialisation pendant laquelle des coefficients, ou poids, sont affectés à chaque connexion liant un neurone j à une entrée ei, et un rayon de voisinage initial Vo est choisi déterminant les neurones voisins du neurone j - une phase d'apprentissage pendant laquelle le réseau de neurones est alimenté par des blocs de pixels extraits d'une ou plusieurs images et les poids des connexions neuronales évoluent par approches successives suivant l'algorithme de Kohonen jusqu a ce que leurs valeurs soient aussi proches que possible des valeurs des entrées les plus probables - une phase de compression pendant laquelle l'image source est découpée en blocs de pixels, chaque bloc étant présenté l'un après l'autre aux entrées du réseau de neurones et codé en fonction du neurone dont les valeurs des poids sont les plus proches des entrées. 4. Procédé selon la revendication 3, caractérisé en ce que le rayon de voisinage entre un neurone j et les autres neurones du réseau diminue au cours de la phase d'apprentissage. 5. Procédé selon l'une quelconque des revendications précédentes, caractérisé en ce que le réseau de neurones est bouclé en anneau.