Brevet FR2846837A1 — 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 15 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, 01 12064 et 01 13922 concernent de tels modes de codage. Pour que le codage soit efficace, c'est-à-dire qu'il présente un bon rapport débit-distorsion, il est nécessaire de déterminer le parcours de manière adaptée. Il existe des techniques pour déterminer un parcours parmi un ensemble d'échantillons. Ces techniques sont connues sous le nom de techniques de résolution du problème du voyageur de commerce. Une revue de ces techniques est par exemple exposée dans l'ouvrage de Gerhard Reinelt intitulé " The traveling salesman, computational solutions for TSP applications ", Springer-Verlag, 1994. Ces techniques utilisent le calcul évolutionnaire, qui fournit une solution optimale au problème mais nécessite un temps de calcul élevé. La présente invention vise à remédier aux inconvénients de la technique antérieure, en fournissant un procédé et un dispositif de codage de données numérique selon lesquels un parcours est déterminé plus rapidement que selon la technique antérieure. A cette fin, l'invention propose un procédé de codage d'échantillons numériques d'un ensemble de données représentatives de grandeurs physiques, le codage incluant la détermination d'un modèle d'amplitude et d'un parcours parmi les échantillons de l'ensemble, caractérisé en ce qu'il comporte les étapes de: - détermination d'un nombre d'échantillons à coder, - construction d'une liste comportant le nombre déterminé d'échantillons, classés par amplitude décroissante. L'invention permet de déterminer plus rapidement le parcours parmi 2 0 les échantillons que selon la technique antérieure. La dégradation des performances de compression (débit et distorsion) est faible et généralement négligeable. Selon un premier mode préféré de réalisation, le procédé comporte les étapes de: - détermination d'une liste initiale d'échantillons, - calcul d'un cot de codage en fonction de la liste d'échantillons, - modification de la liste d'échantillons, les étapes de calcul et modification étant réitérées pour trouver un cot de codage minimal. Ainsi, selon ce mode de réalisation, une liste d'échantillons est déterminée. Selon une caractéristique préférée, le procédé comporte en outre l'étape de codage de l'ensemble de données à partir de la liste d'échantillons qui fournit le cot de codage minimal. La liste déterminée selon l'invention est ainsi utilisée pour coder les données. Selon une caractéristique préférée, la liste initiale d'échantillons comporte tous les échantillons de l'ensemble de données. Selon une caractéristique préférée, la modification de la liste d'échantillons comporte le retrait de l'échantillon de plus faible amplitude. Ainsi, les listes envisagées auront un nombre d'échantillons décroissant au fur et à mesure des itérations. Selon des caractéristiques préférées qui peuvent être combinées, le cot de codage comporte le débit des données codées et le cot de codage comporte la distorsion des données codées. Le débit et la distorsion sont 15 couramment pris en compte lors de la compression de données. Parmi les listes envisagées, celle qui a le cot de codage le plus faible est retenue pour coder les données. La détermination de cette liste est rapide, et par construction son cot de codage est faible. 2 0 Selon un second mode de réalisation, l'invention concerne un procédé tel que précédemment présenté, comportant une initialisation d'algorithme évolutionnaire selon laquelle une population de listes d'échantillons est déterminée, la population comportant un nombre prédéterminé de listes, caractérisé en ce que la détermination de la population 25 comporte les étapes de: - détermination d'une première liste d'échantillons classés par amplitude décroissante, - modification de la première liste par retrait d'un nombre prédéterminé d'échantillons de plus faible amplitude, pour former une seconde 3 0 liste, les étapes de détermination et modification étant réitérées en prenant la seconde liste d'une itération comme première liste pour l'itération suivante, tant que le nombre prédéterminé de listes n'est pas atteint et que la seconde liste a un nombre d'échantillons non nul. Selon ce mode de réalisation, c'est l'initialisation du calcul évolutionnaire qui est simplifiée et rendue plus rapide à exécuter. En outre, les 5 listes créées selon l'invention sont généralement meilleures que des listes tirées aléatoirement, ce qui signifie que la convergence du calcul évolutionnaire est favorisée. Selon une caractéristique préférée, la population est complétée par des listes tirées aléatoirement, si la seconde liste formée a un nombre 10 d'échantillons nul avant que le nombre prédéterminé de listes ne soit atteint. Selon une caractéristique préférée, l'ensemble de données est un bloc d'échantillons formé dans un ensemble plus vaste de données. Selon une caractéristique préférée, les données sont une image numérique. Corrélativement, l'invention concerne un dispositif de codage d'échantillons numériques d'un ensemble de données représentatives de grandeurs physiques, comportant des moyens de détermination d'un modèle d'amplitude et d'un parcours parmi les échantillons de l'ensemble, caractérisé en ce qu'il comporte: - des moyens de détermination d'un nombre d'échantillons à coder, - des moyens de construction d'une liste comportant le nombre déterminé d'échantillons, classés par amplitude décroissante. Le dispositif selon l'invention comporte des moyens de mise en oeuvre des caractéristiques précédemment présentées et présente des 2 5 avantages analogues à ceux précédemment présentés. L'invention concerne aussi un appareil numérique incluant le 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 3 0 photocopieur, un télécopieur. Les avantages du dispositif et de l'appareil numérique sont identiques à ceux précédemment exposés. 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 5 comportant une ou plusieurs séquence d'instructions est apte à mettre en 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 10 illustré par les dessins ci-joints, dans lesquels: - la figure 1 est 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 premier 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 second mode de réalisation de procédé 20 de codage selon 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 microordinateur 10 connecté à différents périphériques, par exemple une caméra numérique 107 25 (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. 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 30 10 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 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 oeuvre l'invention, pourra être 5 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 à 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 10 selon l'invention seront dans ce cas du signal audio. Ce même dispositif possède un écran 104 permettant de visualiser 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). s L'unité centrale 100 (appelée CPU sur le dessin) exécute les instructions relatives à la mise en òuvre de l'invention, instructions stockées 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 20 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 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 25 dispositif, éventuellement amovible, mémorise un programme mettant en ceuvre 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 30 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 3 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 5 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 gestion de base de données ou encore un ordinateur. Un appareil photographique numérique 1 effectue l'acquisition d'une image numérique IM. L'image est transmise à un dispositif de codage 2 dont le 10 fonctionnement sera détaillé dans la suite à l'aide d'algorithmes. Le dispositif de codage comporte un module de transformation 21. Selon l'invention, il comporte: - des moyens 22 de détermination d'un nombre d'échantillons à coder, - des moyens 23 de construction d'une liste comportant le nombre déterminé d'échantillons, classés par amplitude décroissante. Il comporte enfin un module 24 de codage proprement dit. L'image codée peut être transmise par un module de transmission 3 dont le fonctionnement est classique vers un dispositif de décodage 4. En 20 variante, l'image codée est simplement mémorisée pour être décodée ultérieurement. L'image décodée IM' est par exemple transmise à un dispositif d'affichage 5. La figure 3 représente un premier 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 à El 1. Le procédé comporte globalement une transformation du signal à coder, puis la détermination d'un modèle d'amplitude des coefficients issus de 30 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 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 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 El est une transformation linéaire ou non linéaire d'une image numérique IM à traiter selon l'invention. Dans le mode préféré de réalisation de l'invention, la transformation est une transformation en cosinus discrète (DCT) par blocs, telle que celle appliquée dans la norme JPEG. En variante, une autre transformation est utilisée, par exemple une transformation en ondelettes discrète, comme dans la norme JPEG2000. Le traitement suivant est réalisé bloc par bloc, puisque la transformation DCT génère des blocs. Si la transformation ne génère pas de bloc, le traitement est appliqué globalement à toute l'image. L'étape suivante E2 est une initialisation à laquelle est considéré un premier bloc. L'étape suivante E3 est un classement des coefficients du bloc courant par amplitude décroissante. Le résultat est une liste P de coefficients. L'étape suivante E4 est la détermination d'un modèle d'amplitude. 25 Pour cela, une fonction d'approximation de la suite des coefficients classés est déterminée. 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. La demande de brevet français n' 01 06933 décrit en détail cette étape. 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ème coefficient classé par ordre décroissant. L'étape suivante E5 est la détermination du cot de codage associé 5 à la liste P. Le cot de codage d'un bloc est la fonction C = R + X.D, dans laquelle R représente le débit de transmission de la forme codée du bloc, D représente la distorsion générée dans le bloc reconstruit après codage et décodage, par rapport au bloc d'origine et X est un paramètre de réglage entre compression de l'image et distorsion générée par le codage. Il est à noter que la distorsion est calculée en effectuant la somme des erreurs quadratiques entre l'amplitude de chaque coefficient du bloc et l'amplitude qu'il aura après décodage. L'étape suivante E6 est la mémorisation de la liste P comme liste optimale Pcpt, si le cot de codage C calculé à l'étape précédente est inférieur 15 au cot de codage de la liste optimale P0pt précédemment mémorisé. Lors du premier passage par cette étape, la liste courante est mémorisée en tant que liste optimale. L'étape suivante E7 est un test pour déterminer si la liste courante P a une longueur nulle. Si la réponse est négative, cette étape est suivie de l'étape E8 à laquelle la liste courante P est modifiée. Le dernier échantillon est retiré de la liste, ce qui a pour résultat une nouvelle liste. L'étape E8 est suivie de l'étape E5 précédemment décrite. Si la réponse est positive à l'étape E7, cette étape est suivie de 25 l'étape E9 qui est le codage du bloc courant avec la liste Popt c'est-àdire avec la liste qui fournit le plus petit cot de codage. Cette étape est également détaillée dans la demande de brevet n' 01 06933. Cette étape comporte le codage des emplacements des coefficients à partir de la liste P0,pt. Pour cela, un parcours est déterminé par un coefficient 3 o 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 ne passe pas forcement par tous les coefficients du bloc courant. 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 entropique. La forme codée d'un bloc de l'image comporte un modèle d'amplitude qui fournit une approximation de l'amplitude des coefficients et un 10 parcours qui fournit une suite ordonnée des emplacements des coefficients. L'emplacement du keme 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. L'étape suivante E10 est un test pour déterminer si le bloc courant 15 est le dernier bloc de l'image à coder. Si la réponse est négative, cette étape est suivie de l'étape El 1 à laquelle un bloc suivant est considéré. L'étape El 1 est suivie de l'étape E3 précédemment décrite. Si la réponse est positive à l'étape E10, alors le codage de l'image 2o est terminé. La figure 5 représente un second 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 E20 à E28. Là aussi, 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 30 de brevet français n' 01 06933. il L'invention concerne ici l'initialisation du calcul évolutionnaire, et plus particulièrement la détermination d'une population initiale de listes de coefficients. Cette population comporte un nombre prédéterminé d'individus. Le procédé est réalisé sous la forme d'un algorithme qui peut être 5 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 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 10 compact à mémoire figée). On considère ici le codage d'un bloc de l'image. Le bloc considéré comporte L coefficients. L'étape E20 est une initialisation à laquelle le nombre N de coefficients de la liste à construire est initialisé à la valeur L. L'étape suivante E21 est la construction d'une liste de coefficients qui comporte les N plus grands coefficients du bloc, classés par ordre décroissant d'amplitude. L'étape suivante E22 est l'ajout de la liste courante P à la population initiale de l'algorithme évolutionnaire. L'étape suivante E23 est un test pour déterminer si la population initiale comporte le nombre souhaité d'individus, qui sont ici des listes. Si la réponse est négative, cette étape est suivie de l'étape E24 qui est un test pour déterminer si la liste courante P a une longueur nulle. Si la réponse est négative à l'étape E24, cette étape est suivie de 25 l'étape E25 qui est une modification du nombre N de coefficients de la liste. Par exemple, le nombre N est diminué de 10 % et arrondi à l'entier le plus proche. L'étape E25 est suivie de l'étape E21 précédemment décrite. Si la réponse est positive à l'étape E24, il n'est plus possible de construire des listes avec les coefficients du bloc de la manière exposée ci30 dessus et cette étape est suivie de l'étape E26 à laquelle la population est complétée avec des listes tirées aléatoirement. L'étape suivante E27 est le calcul d'une liste de coefficients par calcul évolutionnaire, à partir des listes construites par les étapes précédentes comme population initiale de listes. Ce calcul est réalisé comme dans la demande de brevet français n001 06933 et ne sera pas décrit ici. Si la réponse est positive à l'étape E23, cela signifie que le nombre de listes de la population initiale est atteint. Cette étape est alors suivie de l'étape E27 précédemment décrite. L'étape E27 est suivie de l'étape E28 qui est le codage du bloc courant à partir de la liste obtenue à l'étape E27. Là aussi, ce codage est 10 réalisé comme dans la demande de brevet français n'0106933. 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 codage d'échantillons numériques d'un ensemble de données représentatives de grandeurs physiques, le codage incluant la détermination d'un modèle d'amplitude et d'un parcours parmi les échantillons de l'ensemble, caractérisé en ce qu'il comporte les étapes de: - détermination (E5, E20, E25) d'un nombre d'échantillons à coder, construction (E3, E21) d'une liste comportant le nombre déterminé d'échantillons, classés par amplitude décroissante. 2. Procédé selon la revendication 1, caractérisé en ce qu'il comporte 15 les étapes de: - détermination (E3) d'une liste initiale d'échantillons, calcul (E5) d'un cot de codage en fonction de la liste d'échantillons, modification (E8) de la liste d'échantillons, les étapes de calcul et modification étant réitérées pour trouver un cot de codage minimal. 3. Procédé selon la revendication 2, caractérisé en ce qu'il comporte en outre l'étape de codage (ElO) de l'ensemble de données à partir de la liste 25 d'échantillons qui fournit le cot de codage minimal. 4. Procédé selon la revendication 2 ou 3, caractérisé en ce que la liste initiale d'échantillons comporte tous les échantillons de l'ensemble de données. 5. Procédé selon l'une quelconque des revendications 2 à 4, caractérisé en ce que la modification (E9) de la liste d'échantillons comporte le retrait de l'échantillon de plus faible amplitude. 6. Procédé selon l'une quelconque des revendications 2 à 5, caractérisé en ce que le cot de codage (E6) comporte le débit des données codées. 7. Procédé selon l'une quelconque des revendications 2 à 6, 10 caractérisé en ce que le cot de codage (E6) comporte la distorsion des données codées. 8. Procédé selon la revendication 1, comportant une initialisation d'algorithme évolutionnaire selon laquelle une population de listes 15 d'échantillons est déterminée, la population comportant un nombre prédéterminé de listes, caractérisé en ce que la détermination de la population comporte les étapes de: - détermination (E21) d'une première liste d'échantillons classés par amplitude décroissante, - modification (E25) de la première liste par retrait d'un nombre prédéterminé d'échantillons de plus faible amplitude, pour former une seconde liste, les étapes de détermination et modification étant réitérées en prenant la seconde liste d'une itération comme première liste pour l'itération 25 suivante, tant que le nombre prédéterminé de listes n'est pas atteint (E23) et que la seconde liste a un nombre d'échantillons non nul (E24). 9. Procédé selon la revendication 8, caractérisé en ce que la population est complétée (E26) par des listes tirées aléatoirement, si la 30 seconde liste formée a un nombre d'échantillons nul avant que le nombre prédéterminé de listes ne soit atteint. 10. Procédé selon l'une quelconque des revendications 1 à 9, caractérisé en ce que l'ensemble de données est un bloc d'échantillons formé dans un ensemble plus vaste de données. 11. Procédé selon l'une quelconque des revendications 1 à 10, caractérisé en ce que les données sont une image numérique. 12. Dispositif de codage d'échantillons numériques d'un ensemble de données représentatives de grandeurs physiques, comportant des moyens 10 de détermination d'un modèle d'amplitude et d'un parcours parmi les échantillons de l'ensemble, caractérisé en ce qu'il comporte (2): - des moyens (22) de détermination d'un nombre d'échantillons à coder, - des moyens (23) de construction d'une liste comportant le nombre déterminé d'échantillons, classés par amplitude décroissante. 13. Dispositif selon la revendication 12, caractérisé en ce qu'il comporte: - des moyens de détermination d'une liste initiale (P) d'échantillons, - des moyens de calcul d'un cot de codage (C) en fonction de la liste d'échantillons, - des moyens de modification de la liste d'échantillons, le fonctionnement des moyens de calcul et modification étant réitéré 25 pour trouver un cot de codage minimal. 14. Dispositif selon la revendication 13, caractérisé en ce qu'il comporte en outre des moyens de codage de l'ensemble de données à partir de la liste d'échantillons qui fournit le cot de codage minimal. 30 15. Dispositif selon la revendication 13 ou 14, caractérisé en ce que les moyens de détermination de la liste initiale d'échantillons sont adaptés à la former de sorte qu'elle comporte tous les échantillons de l'ensemble de données. 16. Dispositif selon l'une quelconque des revendications 13 à 15, 5 caractérisé en ce que les moyens de modification de la liste d'échantillons sont adaptés à retirer l'échantillon de plus faible amplitude. 17. Dispositif selon l'une quelconque des revendications 13 à 16, caractérisé en ce qu'il est adapté à considérer un cot de codage qui comporte 10 le débit des données codées. 18. Dispositif selon l'une quelconque des revendications 13 à 17, caractérisé en ce qu'il est adapté à considérer un cot de codage qui comporte la distorsion des données codées. 19. Dispositif selon la revendication 12, comportant des moyens d'initialisation d'algorithme évolutionnaire selon laquelle une population de listes d'échantillons est déterminée, la population comportant un nombre prédéterminé de listes, caractérisé en ce que les moyens de détermination de 20 la population comporte: - des moyens de détermination d'une première liste d'échantillons classés par amplitude décroissante, des moyens de modification de la première liste par retrait d'un nombre prédéterminé d'échantillons de plus faible amplitude, pour former une 25 seconde liste, le fonctionnement des moyens de détermination et modification étant réitérées en prenant la seconde liste d'une itération comme première liste pour l'itération suivante, tant que le nombre prédéterminé de listes n'est pas atteint et que la seconde liste a un nombre d'échantillons non nul. 30 20. Dispositif selon la revendication 19, caractérisé en ce qu'il est adapté à compléter la population par des listes tirées aléatoirement, si la seconde liste formée a un nombre d'échantillons nul avant que le nombre prédéterminé de listes ne soit atteint. 21. Dispositif selon l'une quelconque des revendications 12 à 20, 5 caractérisé en ce qu'il est adapté à coder un ensemble de données qui est un bloc d'échantillons formé dans un ensemble plus vaste de données. 22. Dispositif selon l'une quelconque des revendications 12 à 21, caractérisé en ce qu'il est adapté à coder des données qui sont une image 1o numérique. 23. Dispositif de codage selon l'une quelconque des revendications 12 à 22, caractérisé en ce que les moyens de détermination et construction 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 à enregistrer des variables modifiées au cours de l'exécution dudit programme. 20 24. 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 à 11. 25. Appareil de traitement (10) d'une image numérique, caractérisé en ce qu'il comporte le dispositif selon l'une quelconque des revendications 12 à 23.