Brevet FR2846833A1 — publié le 20040507

La présente invention concerne d'une manière générale le codage de signal numérique et propose à cette fin un dispositif et un procédé de codage d'un signal numérique. Le codage a pour but de compresser le signal, ce qui permet de transmettre, respectivement mémoriser, le signal numérique en réduisant le is temps de transmission, ou le débit de transmission, respectivement en réduisant la place mémoire utilisée. L'invention se situe dans le domaine de la compression avec perte de signaux numériques. Les signaux numériques considérés ici sont de nature quelconque, par exemple des images fixes, de la vidéo, du son, des données 2 0 informatiques. Dans la suite, on considère plus particulièrement le codage et le décodage d'une image fixe. Dans ce contexte, certains modes de codage utilisent un parcours établi parmi un ensemble d'échantillons numériques. Par exemple, les 25 demandes de brevet français no 01 06933 et 01 13922 concernent de tels modes de codage. De manière générale, on souhaite que le résultat du codage soit aussi compact que possible. Ainsi, dans le cas du codage utilisant un parcours établi parmi un ensemble d'échantillons numériques, ce parcours est décrit par 3 0 le chemin le plus court possible (problème du voyageur de commerce). Plus les vecteurs de déplacement reliant chaque point du parcours sont petits, plus leur codage aura un résultat compact. Dans cette optique, la demande de brevet français no 01 12064 propose l'utilisation de vecteurs modifiés de manière à engendrer des distances entre points plus faibles que selon la technique antérieure. La présente invention fournit un procédé et un dispositif de 5 détermination d'un parcours parmi des échantillons d'un signal qui permettent d'obtenir une description de ce parcours qui soit encore plus compact que selon les méthodes connues. A cette fin, l'invention propose un procédé de détermination d'un 10 parcours parmi des échantillons d'un signal numérique de taille finie, caractérisé en ce qu'il comporte l'étape, pour toutes les combinaisons possibles entre lesdits échantillons pris deux à deux, de détermination d'une distance minimale parmi toutes les distances calculées entre un premier échantillon et chacun des éléments du groupe comprenant un 15 second échantillon et des copies de ce second échantillon obtenues par au moins une rotation du second échantillon selon un angle prédéterminé et par rapport à un axe de rotation déterminé en fonction de la taille du signal, ou - au moins une symétrie du second échantillon par rapport à 2 0 un axe de symétrie déterminé en fonction de la taille du signal. L'invention permet de décrire un parcours parmi des échantillons d'un signal numérique, de façon compacte. En effet, selon la présente invention, les caractéristiques du signal sont prises en compte dans la 2 5 formation du parcours. Selon l'invention, de nouvelles distances sont définies de la manière suivante. Un "cadre" contenant les échantillons du signal est défini. Des "copies" de ce cadre sont effectuées autour de celui-ci, de manière adjacente 30 audit cadre, suivant différentes directions. Puis est déterminée la plus petite distance possible entre un premier échantillon du cadre et un second échantillon du cadre, ainsi qu'entre ce premier échantillon et les "copies" du second échantillon à l'intérieur des copies respectives du cadre. On définit de la sorte un nouveau vecteur de déplacement W pour chaque couple d'échantillons ainsi traité et dont la norme est la plus petite qui 5 soit. La norme des vecteurs W est en effet inférieure ou égale à celle des vecteurs de déplacement formés selon la technique antérieure. Selon une caractéristique préférée, des copies du second échantillon sont en outre obtenues par - au moins une translation du second échantillon suivant une direction prédéterminée et selon une valeur qui dépend de la taille du signal. Ainsi, il est possible d'adapter le calcul aux caractéristiques du signal. Selon une caractéristique préférée, ladite au moins une translation est combinée avec une symétrie du second échantillon par rapport à un axe de symétrie déterminé en fonction de la taille du signal. Là encore, cela permet d'adapter le calcul aux caractéristiques du signal. 2 0 Selon une caractéristique préférée, des copies du second échantillon sont en outre obtenues par une combinaison de plusieurs transformations isométriques. Selon une caractéristique préférée, le procédé comporte l'étape préalable de détermination parmi les coordonnées desdits échantillons des 25 coordonnées extrêmes sur chaque axe de coordonnées d'un repère. Ainsi, les limites du signal d'origine sont connues. Selon une caractéristique préférée, les copies du second échantillon sont effectuées dans les deux directions possibles de chaque axe et de chaque diagonale, de sorte que les signaux numériques contenant les copies 3 0 d'échantillons sont adjacents au signal numérique d'origine. Selon une caractéristique préférée, le procédé comporte l'étape ultérieure de détermination d'un parcours minimal joignant les échantillons, en fonction des distances minimales entre échantillons. Selon une caractéristique préférée, le signal numérique est un signal d'image. L'invention a également trait à un procédé de codage d'un signal numérique, caractérisé en ce qu'il comporte le procédé de détermination de parcours précédemment présenté. L'invention a également trait à un procédé de décodage d'un signal 10 numérique codé par le procédé de codage précédent, comportant un décodage de parcours pour déterminer des échantillons décodés, caractérisé en ce qu'il comporte les étapes de: - test pour déterminer si un échantillon décodé correspond à un échantillon d'origine ou à une copie d'échantillon d'origine, - ajustement, si l'échantillon décodé correspond à une copie d'échantillon d'origine, pour retrouver l'échantillon d'origine. Selon une caractéristique préférée, le test comporte la comparaison des coordonnées de l'échantillon décodé par rapport aux limites du signal décodé. Ainsi, il est possible de déterminer si l'échantillon décodé est compris dans le cadre du signal d'origine ou non. Selon une caractéristique préférée, l'ajustement comporte la projection de l'échantillon décodé dans le signal décodé. Lorsque l'échantillon décodé correspond à une copie d'échantillon, l'ajustement est une projection 25 de cette copie dans le cadre du signal d'origine. Corrélativement, l'invention concerne un dispositif de détermination d'un parcours parmi des échantillons d'un signal numérique de taille finie, caractérisé en ce qu'il comporte des moyens de détermination, pour 30 toutes les combinaisons possibles entre lesdits échantillons pris deux à deux, d'une distance minimale parmi toutes les distances calculées entre un premier échantillon et chacun des éléments du groupe comprenant un second échantillon et des copies de ce second échantillon obtenues par au moins une rotation du second échantillon selon un angle prédéterminé et par rapport à un axe de rotation déterminé en fonction de la taille du signal, ou - au moins une symétrie du second échantillon par rapport à un axe de symétrie déterminé en fonction de la taille du signal. Le dispositif de détermination d'un parcours comporte des moyens de mise en oeuvre des caractéristiques présentées précédemment. L'invention concerne aussi un dispositif de codage incluant le dispositif de détermination présenté ci-dessus. Le dispositif de détermination, le procédé et le dispositif de codage présentent des avantages analogues à ceux précédemment présentés. L'invention concerne aussi un appareil numérique incluant le 15 dispositif selon l'invention ou des moyens de mise en oeuvre du procédé selon l'invention. Cet appareil numérique est par exemple un appareil photographique numérique, un caméscope numérique, un scanner, une imprimante, un photocopieur, un télécopieur. Les avantages du dispositif et de l'appareil numérique sont identiques à ceux précédemment exposés. 2 0 Un moyen de stockage d'information, lisible par un ordinateur ou par un microprocesseur, intégré ou non au dispositif, éventuellement amovible, mémorise un programme mettant en oeuvre le procédé selon l'invention. Un programme d'ordinateur lisible par un microprocesseur et comportant une ou plusieurs séquence d'instructions est apte à mettre en 2 5 oeuvre les procédés selon l'invention. Les caractéristiques et avantages de la présente invention apparaîtront plus clairement à la lecture d'un mode préféré de réalisation illustré par les dessins ci-joints, dans lesquels: 3 0 - la figure 1 représente un mode de réalisation d'un dispositif mettant en oeuvre l'invention, - la figure 2 représente un dispositif de codage selon l'invention et un dispositif de décodage correspondant, - la figure 3 représente un mode de réalisation de procédé de codage selon l'invention, - la figure 4 représente un modèle d'amplitude utilisé selon la présente invention, - la figure 5 représente un mode de réalisation de codage d'emplacements de coefficients mis en oeuvre selon l'invention, - la figure 6 représente un exemple de signal en cours de traitement 10 selon l'invention, - la figure 7 représente un mode de réalisation de détermination de vecteurs de déplacement selon l'invention - la figure 8 représente un premier mode de réalisation de l'invention, - la figure 9 représente un parcours parmi des coefficients d'un 15 signal, formé selon la technique antérieure, - la figure 10 représente un parcours parmi des coefficients d'un signal, formé selon la présente invention, - la figure 11 représente un mode de réalisation de décodage selon l'invention, 2 0 - la figure 12 représente un deuxième mode de réalisation de l'invention, - la figure 13 représente un troisième mode de réalisation de l'invention. Selon le mode de réalisation choisi et représenté à la figure 1, un dispositif mettant en oeuvre l'invention est par exemple un micro-ordinateur 10 connecté à différents périphériques, par exemple une caméra numérique 107 (ou un scanner, ou tout moyen d'acquisition ou de stockage d'image) reliée à une carte graphique et fournissant des informations à traiter selon l'invention. 3 0 Le dispositif 10 comporte une interface de communication 112 reliée à un réseau 113 apte à transmettre des données numériques à traiter ou inversement à transmettre des données traitées par le dispositif. Le dispositif comporte également un moyen de stockage 108 tel que par exemple un disque dur. Il comporte aussi un lecteur 109 de disque 110. Ce disque 110 peut être une disquette, un CD-ROM ou un DVD-ROM, par exemple. Le disque 110 comme le disque 108 peuvent contenir des données traitées selon l'invention 5 ainsi que le ou les programmes mettant en oeuvre l'invention qui, une fois lu par le dispositif 10, sera stocké dans le disque dur 108. Selon une variante, le programme permettant au dispositif de mettre en couvre l'invention, pourra être stocké en mémoire morte 102 (appelée ROM sur le dessin). En seconde variante, le programme pourra être reçu pour être stocké de façon identique à 10 celle décrite précédemment par l'intermédiaire du réseau de communication 113. Le dispositif 10 est relié à un microphone 111. Les données à traiter selon l'invention seront dans ce cas du signal audio. Ce même dispositif possède un écran 104 permettant de visualiser 15 les données à traiter ou de servir d'interface avec l'utilisateur qui peut ainsi paramétrer certains modes de traitement, à l'aide du clavier 114 ou de tout autre moyen (souris par exemple). L'unité centrale 100 (appelée CPU sur le dessin) exécute les instructions relatives à la mise en oeuvre de l'invention, instructions stockées 20 dans la mémoire morte 102 ou dans les autres éléments de stockage. Lors de la mise sous tension, les programmes de traitement stockés dans une mémoire non volatile, par exemple la ROM 102, sont transférés dans la mémoire vive RAM 103 qui contiendra alors le code exécutable de l'invention ainsi que des registres pour mémoriser les variables nécessaires à la mise en oeuvre de 25 l'invention. De manière plus générale, un moyen de stockage d'information, lisible par un ordinateur ou par un microprocesseur, intégré ou non au dispositif, éventuellement amovible, mémorise un programme mettant en couvre le procédé selon l'invention. Le bus de communication 101 permet la communication entre les différents éléments inclus dans le micro-ordinateur 10 ou reliés à lui. La représentation du bus 101 n'est pas limitative et notamment l'unité centrale 100 est susceptible de communiquer des instructions à tout élément du microordinateur 10 directement ou par l'intermédiaire d'un autre élément du microordinateur 10. En référence à la figure 2, un mode de réalisation de dispositif de codage selon l'invention est destiné à coder un signal numérique dans le but de le compresser. Le dispositif de codage est intégré dans un appareil, qui est par exemple un appareil photographique numérique, un caméscope numérique, un scanner, une imprimante, un photocopieur, un télécopieur, un système de 10 gestion de base de données ou encore un ordinateur. Une source d'image 1 fournit une image numérique au dispositif de codage 2, dont le fonctionnement sera détaillé dans la suite. Le codage inclut la détermination d'un parcours parmi les échantillons de l'ensemble. Le dispositif de codage comporte un circuit de transformation 21 15 relié à un circuit de calcul de modèle d'amplitude 22. Le circuit 21 est également relié à un circuit 23 de détermination d'une valeur BW dépendante de la taille du signal. Le circuit de transformation délivre une image transformée IM aux circuits 22 et 23. Le circuit 23 est relié à un circuit 24 de détermination de vecteurs de 2 o déplacement W. Le circuit 24 est relié à un circuit 25 de détermination d'un parcours à partir des vecteurs de déplacement précédemment déterminés. Le circuit 25 est relié à un circuit 26 de codage qui réalise un codage entropique du parcours précédemment déterminé. Le fonctionnement du dispositif de codage sera détaillé dans la suite. Le dispositif de codage fournit un fichier contenant des données représentant l'image compressée à des moyens de transmission et/ou de mémorisation 3. Ces moyens sont classiques et ne seront pas décrits ici. Les moyens 3 sont reliés à un dispositif de décodage 4 dont le fonctionnement sera détaillé dans la suite. Le dispositif de décodage comporte un circuit 41 de lecture du modèle d'amplitude à utiliser pour décoder le signal. Le dispositif de décodage comporte aussi un circuit 42 de lecture de la valeur BW. Le circuit 42 est relié à un circuit 43 de décodage des vecteurs de déplacement W. Le circuit 43 est relié à un circuit 44 de reconstruction des coordonnées des coefficients du signal. Le circuit 41 et le circuit 44 permettent de restituer le signal 10 transformé IM'. Les circuits 41 et 44 sont reliés à un circuit 45 de transformation inverse qui fournit une image décodée à un dispositif 5 de visualisation d'image. Il est à noter que le dispositif de codage et le dispositif de décodage peuvent être intégrés dans un même appareil, par exemple l'ordinateur 10 de la 15 figure 1. La figure 3 représente un mode de réalisation de procédé de codage d'une image, selon l'invention. Ce procédé est mis en oeuvre dans le dispositif de codage et comporte des étapes El à E4. Le procédé comporte globalement une transformation du signal à coder, puis la détermination d'un modèle d'amplitude des coefficients issus de la transformation. Les emplacements de ces coefficients sont ensuite codés selon une méthode qui utilise un parcours établi parmi les coefficients. Un tel procédé de codage est décrit par exemple dans la demande 25 de brevet français n' 01 06933. Le procédé est réalisé sous la forme d'un algorithme qui peut être mémorisé en totalité ou en partie dans tout moyen de stockage d'information capable de coopérer avec le microprocesseur. Ce moyen de stockage est lisible par un ordinateur ou par un microprocesseur. Ce moyen de stockage est 3 o intégré ou non au dispositif, et peut être amovible. Par exemple, il peut comporter une bande magnétique, une disquette ou un CD-ROM (disque compact à mémoire figée). L'étape El est une transformation linéaire ou non linéaire d'une image numérique IM à traiter selon l'invention. L'image a par exemple une taille de 512 x 512 pixels. Dans le mode préféré de réalisation de l'invention, la transformation s est une transformation en cosinus discrète dite DCT. Cette transformation permet de décorréler les pixels de l'image et de concentrer l'énergie du signal sur certains coefficients, ce qui facilite la compression du signal. Ainsi, les plus basses fréquences, qui sont généralement présentes dans une image naturelle, se retrouvent concentrées dans le coin supérieur 10 gauche du signal transformé. D'autres types de transformation peuvent être utilisés, par exemple la transformation en ondelettes discrètes dite DWT (d'après l'anglais Discrete Wavelet Transform) à M niveaux de résolution ou la transformation de Fourier ou encore une transformation non-linéaire comme une transformation 15 morphologique. L'étape suivante E2 est un classement des coefficients du signal. Le signe des coefficients est tout d'abord codé de manière indépendante. Les coefficients sont ensuite considérés en valeur absolue et sont classés du plus grand au plus petit. L'étape suivante E3 est la détermination d'une fonction d'approximation de la suite des coefficients classés. Cette fonction est par exemple une exponentielle décroissante définie par un jeu de paramètres qui sont déterminés par régression. Cette fonction est un modèle d'amplitude. La figure 4 représente un exemple de modèle d'amplitude A. A chaque valeur entière k en abscisse correspond une valeur A(k) fournie par le modèle d'amplitude. La valeur A(k) est une approximation de l'amplitude du kène coefficient classé par ordre décroissant. 3 0 L'étape suivante E4 est le codage des emplacements des coefficients. Cette étape comporte la détermination d'un parcours parmi les coefficients du signal de sorte que le cot de codage de ce parcours soit il minimal. Le parcours comporte un coefficient initial et la liste des vecteurs joignant les autres coefficients. Chaque coefficient du parcours différent du coefficient initial est représenté par un vecteur décrivant son emplacement par rapport au coefficient précédent dans le parcours. Il est à noter que le parcours 5 ne passe pas forcement par tous les coefficients du signal. En effet, il est possible de ne coder qu'une partie des coefficients et de mettre les autres coefficients à la valeur zéro lors du décodage ultérieur. Une fois le parcours déterminé, les coordonnées du coefficient initial sont codées par un codage binaire et les vecteurs sont codés par un codage lo entropique. L'étape E4 est détaillée dans la suite. La forme codée de l'image comporte un modèle d'amplitude qui fournit une approximation de l'amplitude des coefficients et un parcours qui fournit une suite ordonnée des emplacements des coefficients. L'emplacement 15 du kème coefficient de cette suite est déterminé par le parcours et son amplitude est déterminée par l'ordonnée correspondant à l'abscisse k selon le modèle d'amplitude. La figure 5 représente un mode de réalisation de l'étape E4 de 20 codage des emplacements des coefficients. Ce codage comporte des étapes E41 à E48. Ce codage comporte globalement la détermination d'un parcours parmi les coefficients et le codage des coefficients en fonction du parcours. Un parcours comporte un coefficient du signal, dit coefficient initial, et une liste de 25 vecteurs joignant au moins une partie des autres coefficients. Comme représenté à la figure 6, le signal en cours de traitement est bidimensionnel et de taille finie. Le signal est par exemple inscrit dans un carré. Un repère cartésien d'axes de coordonnées x et y est centré sur l'emplacement 3o de coefficient placé dans le coin supérieur gauche. Le signal comporte ici sept coefficients a1 à a7 dont l'emplacement est à coder. Les différents échantillons forment un ensemble G et sont matérialisés dans des cases hachurées, respectivement positionnées aux emplacements suivants: a1 = (0, 0), a2 = (1, 2), a3 = (3, 0), a4 = (4, 1), a5 = (5, 0), a6 = (8, 1), a7 = (0, 6). Au lieu de coder l'ensemble de tous les échantillons avec leurs amplitudes et leurs coordonnées, la présente invention propose de définir, par l'intermédiaire de nouveaux vecteurs de déplacements, une suite des positions des échantillons de l'ensemble G et de la coder. On notera que les signaux numériques concernés par l'invention ne 10 sont pas nécessairement bidimensionnels puisque l'invention s'applique par exemple à des signaux mono-dimensionnels tels que des signaux sonores ou encore à des signaux tridimensionnels tels que des signaux vidéo. L'étape E41 est l'acquisition des coefficients dont l'emplacement est 15 à coder, c'est-à-dire des coefficients de l'ensemble G. L'étape suivante E42 est le calcul des coordonnées extrêmes du signal, dans le repère précédemment défini. Les coordonnées extrêmes sont les valeurs maximales et minimales que le signal atteint sur chaque axe du repère. Ainsi: L =min(x) R = max(x) B min(y) T =max(y) Dans l'exemple représenté à la figure 6, on obtient les valeurs: L = 0, R =8, B = O et T = 6. La détermination des coordonnées extrêmes permet de définir un cadre virtuel C qui délimite au plus près l'ensemble G des échantillons. Le cadre C comporte tous les points du parcours. Le cadre est carré, de coté BW = max (R-L+1, T-B+1). La valeur BW est associée aux données de codage du signal. En variante, on n'utilise pas le carré de coté BW, on considère simplement le signal dans son ensemble. La taille du signal est connue aussi bien du codeur que du décodeur, il n'est donc pas nécessaire de l'associer aux données de codage. Les distances calculées selon cette variante sont cependant moins courtes qu'avec le carré de coté BW. L'étape suivante E43 est la mémorisation et/ou la transmission de la valeur BW. L'étape suivante E44 est la détermination des vecteurs de 10 déplacement W selon l'invention. Cette étape est détaillée à la figure 7 sous la forme d'un algorithme comportant des étapes E440 à E444. Pour ce faire, on définit préalablement la notion de distance à utiliser pour le calcul de la distance entre deux échantillons et l'on prendra, par 15 exemple, la distance euclidienne d = SQRT ((x2 - x12 + (Y2 _ y0)2) entre deux points M1 et M2 de coordonnées respectives (x1, Yi) et (x2, Y2) , o SQRT représente la racine carrée. La détermination de ces nouveaux vecteurs nécessite de traiter tous les échantillons de l'ensemble G deux par deux. A l'étape E440, un couple de coefficients de coordonnées (x1, yi) et (x2, Y2) est considéré. Selon l'invention, on considère, dans un premier temps, des "copies" du cadre C de la figure 6 effectuées autour du cadre dans les huit directions possibles. De cette façon, on réalise des "copies" des échantillons de l'ensemble G à l'intérieur des différentes "copies" du cadre. L'étape suivante E441 est ainsi le calcul des copies du deuxième coefficient du couple. La figure 8 représente un premier mode de réalisation. 3 0 Les "copies" d'échantillons sont obtenues par: - rotation d'un échantillon considéré autour d'axes déterminés en fonction des coordonnées extrêmes et selon des angles prédéterminés, et - translation d'un échantillon considéré suivant les diagonales et selon une valeur qui dépend des coordonnées extrêmes. Plus précisément, le signal initial est enveloppé par huit blocs, déterminés selon les règles suivantes: - bloc de gauche: rotation de -90 en (-0,5; -0,5), - bloc du haut: rotation de +90 en (-0,5; -0,5), - bloc de droite: rotation de -90 en (BW-0,5; BW-0,5), - bloc du bas: rotation de +90 en (BW-0,5; BW-0,5), - bloc supérieur gauche: translation de -BW selon l'axe x et de -BW 10 selon l'axe des y, - bloc supérieur droit: translation de +BW selon l'axe x et de -BW selon l'axe des y, - bloc inférieur gauche: translation de -BW selon l'axe x et de +BW selon l'axe des y, - bloc inférieur droit: translation de +BW selon l'axe x et de +BW selon l'axe des y. Ainsi, lorsque l'on considère les deux coefficients de coordonnées (xI, Yi) et (x2, Y2) du signal initial, on calcule à l'étape suivante E442 les vecteurs joignant le premier coefficient du couple au second coefficient et à ses 2 0 huit copies. On obtient ainsi les neuf vecteurs suivants: W1 = (X1, yl), (x2, Y2) W2 = (X1, Yi), (-1-y2, x2) W3= (X1, Yi), (y2, -1-X2) W4 = (x1, YI), (2.BW-1 -y2, x2) 25 W5 = (X1, y,), (Y2, 2.BW-1-x2) W6 = (x1, Yi), (x2-BW, y2-BW) W7 = (x1, Yi), (x2+BW, y2-BW) W8 = (xI, Y1), (x2BW, y2+BW) W9 = (xI, yI), (x2+BW, Y2+BW) 30 L'étape suivante E443 est la sélection du vecteur W qui a l'amplitude la plus faible pour la distance considérée parmi les neuf vecteurs précédents. L'étape suivante E444 est un test pour déterminer s'il reste au moins un autre couple à tester. Si la réponse est positive, alors cette étape est suivie de l'étape E440. Lorsque la réponse est négative, tous les couples de coefficients de l'ensemble G ont été traités. L'étape E44 (figure 5) a alors pour résultat un vecteur W pour chaque couple de coefficients du signal en cours de traitement. Dans ce qui suit, un chemin minimal joignant les coefficients est calculé. Ce problème est connu sous le nom du " problème du plus court chemin hamiltonien " qui peut être réduit au " problème du voyageur de 10 commerce ". Il s'agit de passer une seule fois par tous les points du parcours, sans retourner au point d'origine. Des solutions à ce problème peuvent être trouvées dans l'article de R.E. Burkard et AL, "Well-solvable special cases of the TSP: a survey", SPEZIAL FORSCHUNGSBEREICH F003, Bericht n0 52, Dec. 1995. L'étape suivante E45 est la détermination du point de départ du chemin. Les coordonnées du point de départ font partie des données de codage du signal. L'étape suivante E46 est le calcul du chemin le plus court pour parcourir tous les coefficients. Selon l'invention, ce calcul est effectué à partir 2o des vecteurs W déterminés à l'étape E44. Cette méthode est appelée "méthode par insertion" et repose sur l'idée principale qui est de construire d'abord un parcours comportant un sousensemble des échantillons à visiter. Par exemple, on choisit trois échantillons au hasard et on les relie de 25 la seule façon possible. Ensuite, pour chaque échantillon non encore inséré, on va calculer entrequelles paires successives d'échantillons du parcours il s'insère le mieux (c'est-à-dire en augmentant le moins possible le parcours), ce qui représentera le cot de cet échantillon. On insère alors dans le parcours l'échantillon de cot minimal. Ce processus est réitéré jusqu'à insertion de tous les échantillons. On obtient ainsi un parcours dont la longueur est faible. Il est à noter que ce parcours n'a pas nécessairement la plus petite distance qui soit, mais la solution obtenue est néanmoins satisfaisante. En effet, il n'existe pas à l'heure actuelle de solution garantissant un calcul de parcours minimal lorsque le nombre d'échantillons est élevé, et ce pour un temps de calcul raisonnable. Le résultat de l'étape E46 est un parcours ou chemin minimal entre les échantillons de l'ensemble G qui est représenté par une suite de vecteurs de déplacement du nouveau type et qui sont donc chacun, par définition, de norme réduite. En d'autres termes, le parcours est une liste ordonnée de 10 vecteurs notés Wi, o i est un indice entier représentant l'ordre du vecteur. L'étape suivante E47 est un codage entropique des vecteurs de déplacement précédemment déterminés. Le codage utilisé ici est par exemple un codage de Huffman ou un codage arithmétique. Les vecteurs utilisés étant plus courts que selon la technique antérieure, leur codage fournit des données 15 codées de taille réduite par rapport à la technique antérieure. L'étape E47 comporte en outre un codage binaire du coefficient initial. A l'étape E48, les vecteurs codés et le coefficient initial codé sont transmis ou mémorisés. La figure 9 est un exemple de parcours minimal calculé selon la technique antérieure pour le signal de la figure 6. Ce parcours a été calculé sans considérer de copie du signal à coder. Le parcours est: a6-a5-a4-a3-ala2a7. La longueur de ce chemin est de 14,35, en utilisant la distance précédemment citée. La figure 10 est un exemple de parcours minimal calculé selon la présente invention, pour le même signal. Le parcours est: a6-a7-a5-a4-a3a2-a1. La longueur de ce chemin est de 11,54, en utilisant la distance précédemment citée. La figure Il représente un mode de réalisation de procédé de décodage de données préalablement codées selon le procédé de la figure 3. Ce procédé est mis en oeuvre dans le dispositif de décodage et comporte des étapes E21 à E32. Le procédé est réalisé sous la forme d'un algorithme qui peut être mémorisé en totalité ou en partie dans tout moyen de stockage d'information 5 capable de coopérer avec le microprocesseur. Ce moyen de stockage est lisible par un ordinateur ou par un microprocesseur. Ce moyen de stockage est intégré ou non au dispositif, et peut être amovible. Par exemple, il peut comporter une bande magnétique, une disquette ou un CD-ROM (disque compact à mémoire figée). L'étape E21 est la lecture et le décodage de la valeur de BW. L'étape suivante E22 est la lecture et le décodage des coordonnées du coefficient initial du parcours. L'étape suivante E23 est le décodage entropique des vecteurs de déplacement. Le décodage correspond au codage qui a été réalisé à l'étape 15 E47. Cette étape a pour résultat la liste des vecteurs Wi. L'étape suivante E24 est une initialisation à laquelle le paramètre i est mis à la valeur un pour considérer le premier vecteur de déplacement de la liste. L'étape suivante E25 est le calcul des coordonnées (xi+1, yi+i) d'un 20 coefficient suivant, en fonction du coefficient courant (xi, yi) et du vecteur de déplacement courant Wi. Lors du premier passage, le coefficient courant est l'échantillon initial. L'étape suivante E26 est un test pour déterminer si les coordonnées (xi+1, yi+.) du coefficient qui ont été calculées à l'étape précédente sont à 25 l'extérieur du cadre contenant le signal initial. Si au moins l'une des coordonnées xi+1 et yi+l est soit négative soit supérieure ou égale à BW, alors la réponse est positive. L'étape E26 est alors suivie de l'étape E27 qui est le calcul des coordonnées du coefficient situé dans le cadre contenant le signal initial et correspondant au coefficient calculé 30 à l'étape E25. Il s'agit de projeter le coefficient calculé à l'étape E25 dans le cadre contenant le signal initial. Les coordonnées du vecteur Wi courant selon les axes x et y sont notées wx1 et wyi. Les formules de calcul sont les suivantes: Si 0 Yi + wyj. Si xi + wxi Xi + wxi. Si BW 2.BW -1 - (xi + wxi). Si 0 et Yi+1 = xi + wxi. Si xi + wxi Si BW Si xi + wxi wyi - BW. Si BW +wyi - BW. Lorsque la réponse est négative à l'étape E26, cela signifie que les coordonnées calculées à l'étape E25 sont dans le cadre contenant le signal initial. Il n'y a alors aucune projection à faire. L'étape E26 est alors suivie de l'étape E28. De même, l'étape E27 est suivie de l'étape E28 qui est un test pour déterminer si tous les vecteurs ont été traités. Tant que la réponse est négative, cette étape est suivie de l'étape E29 à laquelle un vecteur suivant est considéré. L'étape E29 est suivie de l'étape E25 précédemment décrite. Lorsque la réponse est positive à l'étape E28, cela signifie que tous 3 0 les vecteurs ont été traités et l'ensemble G a été reconstitué. L'étape E28 est alors suivie de l'étape E31. L'étape E30 est la détermination du modèle d'amplitude à partir des données transmises par le codeur. L'étape E30 est également suivie de l'étape E31. L'étape E31 est une reconstruction du signal à partir du modèle d'amplitude et des coordonnées des coefficients. L'étape suivante E32 est une transformation DCT inverse du signal. Le résultat est une image décodée qui est par exemple affichée sur un écran de visualisation. La figure 12 représente un second mode de réalisation de procédé selon l'invention. Pour un signal de nature différente, il est envisageable d'utiliser d'autres types d'isométries de manière à exploiter convenablement les caractéristiques du signal. Ainsi le bloc d'origine contenant l'ensemble des coefficients à coder peut subir tout type d'isométries ou de combinaison d'isométries. Dans l'exemple représenté, les blocs diagonaux (blocs inférieurs droit et gauche, et supérieurs droit et gauche) sont construits à partir du bloc central par une combinaison d'une translation avec une symétrie orthogonale, au lieu d'une 2 0 simple translation comme dans l'exemple précédent. Ainsi, on enveloppe le signal de la façon suivante: - bloc de gauche: rotation de -90 en (-0,5; -0,5) - bloc du haut: rotation de +90 en (-0, 5; -0,5) - bloc de droite: rotation de -90' en (BW-0,5; BW-0,5) 25 - bloc du bas: rotation de +90' en (BW-0,5; BW-0,5) - bloc supérieur gauche: symétrie orthogonale d'axe Y = -0.5 et translation de -BW selon l'axe x bloc supérieur droit: symétrie orthogonale d'axe Y = -0.5 et translation de +BW selon l'axe x - bloc inférieur gauche: symétrie orthogonale d'axe Y = BW-0.5 et translation de -BW selon l'axe x - bloc inférieur droit: symétrie orthogonale d'axe Y = BW-0.5 et translation de +BW selon l'axe x. On choisit le vecteur W qui a l'amplitude la plus faible parmi neufs vecteurs W1, W2,..., W9: W1 = (xi, YI), (x2, Y2) W2 = (xi, yI), (-1-y2, x2) W3 = (xI, YI), (Y2, -1-x2) W4 = (xI, YI), (2.BW-1-y2, x2) 10 W5 = (xi, Y,), (Y2, 2.BW-1-x2) W6 = (xI, YI), (x2-BW, -y2-1) W7 = (XI, yî), (x2+BW, -y2-1) W8 = (xi, y,), (x2-BW, 2.BW-1-y2) Wg = (xi, y,), (x2+BW, 2.BW-1y2) 15 Le décodage, et particulièrement les formules de l'étape E27 sont adaptées de manière correspondante. De manière générale, on peut utiliser une combinaison de plusieurs *transformations isométriques. La figure 13 représente un troisième mode de réalisation de procédé selon l'invention. Dans ce mode de réalisation, on n'effectue que des symétries du signal original pour exploiter au mieux les caractéristiques de celui-ci. 25 Ainsi, on enveloppe le signal de la façon suivante: - bloc de gauche: symétrie orthogonale d'axe X = -0,5 - bloc du haut: symétrie orthogonale d'axe Y = -0,5 - bloc de droite: symétrie orthogonale d'axe X = BW - 0,5 bloc du bas: symétrie orthogonale d'axe Y = BW - 0,5 3 o - bloc supérieur gauche: symétrie orthogonale d'axe Y = -X - 1 - bloc supérieur droit: symétrie orthogonale d'axe Y = X - BW - bloc inférieur gauche: symétrie orthogonale d'axe Y = X + BW - bloc inférieur droit: symétrie orthogonale d'axe Y = -X + 2.BW - 1. On choisit le vecteur W qui a l'amplitude la plus faible parmi neufs vecteurs W1, W2,..., W9: W1 = (xI, yI), (x2, Y2) W2 = (Xl, Y), (-1-X2, Y2) W3 = (xI, Y), (x2, -1-y2) W4 = (x1, Yl), (2.BW-1-x2, Y2) W5 = (xi, Y,), (x2, 2.BW-1-y2) 1:0 W6 = (xI, Y), (-y2-1, -x2-1) W7 = (xI, YI), (y2+BW, x2-BW) W8 = (xi, Y,), (y2-BW, BW+x2) W9 = (xi, y,), (2.BW-1- Y2, 2.BW-1x2) Là aussi, le décodage, et particulièrement les formules de l'étape z5 E27 sont adaptées de manière correspondante. Bien entendu, la présente invention n'est nullement limitée aux modes de réalisation décrits et représentés, mais englobe, bien au contraire, toute variante à la portée de l'homme du métier. REVENDICATIONS 1. Procédé de détermination d'un parcours parmi des échantillons d'un signal numérique de taille finie, caractérisé en ce qu'il comporte l'étape (E44), pour toutes les combinaisons possibles entre lesdits échantillons pris deux à deux, de détermination d'une distance minimale parmi toutes les distances calculées 10 entre un premier échantillon et chacun des éléments du groupe comprenant un second échantillon et des copies de ce second échantillon obtenues par - au moins une rotation du second échantillon selon un angle prédéterminé et par rapport à un axe de rotation déterminé en fonction de la taille du signal, ou - au moins une symétrie du second échantillon par rapport à un axe de symétrie déterminé en fonction de la taille du signal. 2. Procédé selon la revendication 1, caractérisé en ce que des copies du second échantillon sont en outre obtenues par 2 0 - au moins une translation du second échantillon suivant une direction prédéterminée et selon une valeur qui dépend de la taille du signal. 3. Procédé selon la revendication 2, caractérisé en ce que ladite au moins une translation est combinée avec une symétrie du second échantillon 25 par rapport à un axe de symétrie déterminé en fonction de la taille du signal. 4. Procédé selon l'une quelconque des revendications 1 à 3, caractérisé en ce que des copies du second échantillon sont en outre obtenues par une combinaison de plusieurs transformations isométriques. 30 5. Procédé selon l'une quelconque des revendications 1 à 4, caractérisé en ce qu'il comporte l'étape préalable (E42) de détermination parmi les coordonnées desdits échantillons des coordonnées extrêmes (L, R, B, T) sur chaque axe de coordonnées (x, y) d'un repère. 6. Procédé selon la revendication 5, caractérisé en ce que (E441) les 5 copies du second échantillon sont effectuées dans les deux directions possibles de chaque axe et de chaque diagonale, de sorte que les signaux numériques contenant les copies d'échantillons sont adjacents au signal numérique d'origine. 7. Procédé selon l'une quelconque des revendications 1 à 6, caractérisé en ce qu'il comporte l'étape ultérieure (E46) de détermination d'un parcours minimal joignant les échantillons, en fonction des distances minimales entre échantillons. 8. Procédé selon l'une quelconque des revendications 1 à 7, caractérisé en ce que le signal numérique est un signal d'image (IM). 9. Procédé de codage d'un signal numérique, caractérisé en ce qu'il comporte le procédé de détermination de parcours selon l'une quelconque des 2 o revendications 1 à 8. 10. Procédé de décodage d'un signal numérique codé par le procédé selon la revendication 9, comportant un décodage de parcours pour déterminer des échantillons décodés, caractérisé en ce qu'il comporte les 25 étapes de: test (E26) pour déterminer si un échantillon décodé correspond à un échantillon d'origine ou à une copie d'échantillon d'origine, - ajustement (E27), si l'échantillon décodé correspond à une copie d'échantillon d'origine, pour retrouver l'échantillon d'origine. 11. Procédé selon la revendication 10, caractérisé en ce que le test (E26) comporte la comparaison des coordonnées de l'échantillon décodé par rapport aux limites (BW) du signal décodé. 12. Procédé selon la revendication 10 ou 11, caractérisé en ce que l'ajustement (E27) comporte la projection de l'échantillon décodé dans le signal décodé. 13. Dispositif de détermination d'un parcours parmi des échantillons 10 d'un signal numérique de taille finie, caractérisé en ce qu'il comporte des moyens (24) de détermination, pour toutes les combinaisons possibles entre lesdits échantillons pris deux à deux, d'une distance minimale parmi toutes les distances calculées entre un premier échantillon et chacun des éléments du groupe comprenant un second 15 échantillon et des copies de ce second échantillon obtenues par - au moins une rotation du second échantillon selon un angle prédéterminé et par rapport à un axe de rotation déterminé en fonction de la taille du signal, ou - au moins une symétrie du second échantillon par rapport à un axe 2o de symétrie déterminé en fonction de la taille du signal. 14. Dispositif selon la revendication 13, caractérisé en ce que les moyens de détermination sont adaptés à considérer en outre des copies du second échantillon obtenues par - au moins une translation du second échantillon suivant une direction prédéterminée et selon une valeur qui dépend de la taille du signal. 15. Dispositif selon la revendication 14, caractérisé en ce que ladite au moins une translation est combinée avec une symétrie du second 30 échantillon par rapport à un axe de symétrie déterminé en fonction de la taille du signal. 16. Dispositif selon l'une quelconque des revendications 13 à 15, caractérisé en ce que les moyens de détermination sont adaptés à considérer en outre des copies du second échantillon obtenues par une combinaison de plusieurs transformations isométriques. 17. Dispositif selon l'une quelconque des revendications 13 à 16, caractérisé en ce qu'il comporte des moyens préalables de détermination parmi les coordonnées desdits échantillons des coordonnées extrêmes (L, R, B, T) sur chaque axe de coordonnées (x, y) d'un repère. 18. Dispositif selon la revendication 17, caractérisé en ce que les moyens de détermination sont adaptés à effectuer les copies du second échantillon dans les deux directions possibles de chaque axe et de chaque diagonale, de sorte que les signaux numériques contenant les copies 15 d'échantillons sont adjacents au signal numérique d'origine. 19. Dispositif selon l'une quelconque des revendications 13 à 18, caractérisé en ce qu'il comporte des moyens ultérieurs (25) de détermination d'un parcours minimal joignant les échantillons, en fonction des distances 20 minimales entre échantillons. 20. Dispositif selon l'une quelconque des revendications 13 à 19, caractérisé en ce qu'il est adapté à traiter un signal numérique qui est un signal d'image (IM). 21. Dispositif de codage (2) d'un signal numérique, caractérisé en ce qu'il comporte le dispositif de détermination de parcours selon l'une quelconque des revendications 13 à 20. 22. Dispositif de décodage d'un signal numérique codé par le dispositif selon la revendication 21, comportant des moyens de décodage de parcours pour déterminer des échantillons décodés, caractérisé en ce qu'il comporte (43): - des moyens de test pour déterminer si un échantillon décodé correspond à un échantillon d'origine ou à une copie d'échantillon d'origine, - des moyens d'ajustement, si l'échantillon décodé correspond à une copie d'échantillon d'origine, pour retrouver l'échantillon d'origine. 23. Dispositif selon la revendication 22, caractérisé en ce que les moyens de test comportent des moyens de comparaison des coordonnées de 10 l'échantillon décodé par rapport aux limites (BW) du signal décodé. 24. Dispositif selon la revendication 22 ou 23, caractérisé en ce que les moyens d'ajustement comportent des moyens de projection de l'échantillon décodé dans le signal décodé. 25. Dispositif selon l'une quelconque des revendications 13 à 21, caractérisé en ce que les moyens de détermination sont incorporés dans: un microprocesseur (100), - une mémoire morte (102) comportant un programme pour traiter 20 les données, et - une mémoire vive (103) comportant des registres adaptés à enregistrer des variables modifiées au cours de l'exécution dudit programme. 26. Dispositif selon l'une quelconque des revendications 22 à 24, 25 caractérisé en ce que les moyens de test et ajustement sont incorporés dans: - un microprocesseur (100), - une mémoire morte (102) comportant un programme pour traiter les données, et - une mémoire vive (103) comportant des registres adaptés à 3o enregistrer des variables modifiées au cours de l'exécution dudit programme. 27. Appareil de traitement (10) d'une image numérique, caractérisé en ce qu'il comporte des moyens adaptés à mettre en oeuvre le procédé selon l'une quelconque des revendications 1 à 12. 28. Appareil de traitement (10) d'une image numérique, caractérisé en ce qu'il comporte le dispositif selon l'une quelconque des revendications 13 à 26.