Brevet FR2907565A1 — publié le 20080425

La présente invention concerne un procédé et un dispositif pour déterminer une valeur d'une grandeur physique, un procédé et un dispositif de codage, un programme d'ordinateur et un support d'information pour mettre en oeuvre un tel procédé. Elle s'applique, en particulier, à la détermination d'un pas de quantification pour le codage d'une image numérique, par exemple une image provenant d'un appareil photo numérique, d'un camescope ou d'un moyen de stockage de données d'image. Dans le domaine du codage d'image numérique, une technique classique consiste à déterminer un pas de quantification dit optimal en minimisant, sur chaque partie du signal représentatif de l'image, une fonction de coût de codage, qui est une combinaison linéaire du débit et de la distorsion induits par le codage de ladite partie du signal. On sait que la fonction de coût en question est globalement convexe. Il est connu, pour déterminer un pas de quantification optimal, d'appliquer une trichotomie à cette fonction de coût, la trichotomie étant méthode présentant notamment l'avantage d'être implémentable de façon très simple, et de se prêter à la récursivité. La trichotomie est décrite sur la page Internet suivante : http://www.math.jussieu.fr/ùcochet/ScienceEnFete/trichotomie.html. Toutefois, dans certains cas, une fonction, par exemple de coût, sur laquelle on recherche un minimum n'est pas parfaitement convexe, notamment en raison d'erreurs d'arrondi entre données réelles et données entières, par exemple. On ne peut alors pas appliquer la trichotomie classique. La présente invention vise à remédier à ces inconvénients. A cet effet, la présente invention vise, selon un premier aspect, un procédé pour déterminer une valeur d'une grandeur physique dite optimale , par recherche d'une estimation d'un minimum local d'une fonction associée à ladite grandeur physique, qui comporte une étape de sélection d'un nombre d'au moins quatre valeurs dites candidates et, de manière itérative : 2907565 2 - lorsque les images, par ladite fonction, des valeurs candidates correspondent à une convexité, une étape de sélection dudit nombre de nouvelles valeurs candidates pour réaliser une nouvelle itération, qui comporte, pour au moins une itération : 5 - lorsque les images, par ladite fonction, des valeurs candidates ne correspondent ni à une concavité, ni à une convexité, une étape de sélection dudit nombre de nouvelles valeurs candidates pour réaliser une nouvelle itération, les valeurs extrêmes sélectionnées comme nouvelles valeurs étant respectivement égales à une valeur extrême de l'itération en cours et à la 10 valeur la plus proche et différente de l'autre valeur extrême de l'itération en cours. Grâce à ces dispositions, si la fonction n'est ni convexe ni concave, la mise en oeuvre de la présente invention permet de poursuivre les itérations afin de rechercher un minimum, au moins local, en réduisant peu l'intervalle de 15 recherche, ce qui limite le risque que le minimum recherché soit exclu du nouvel intervalle de recherche. Ainsi, on réduit progressivement l'intervalle sur lequel les évaluations de la fonction sont effectuées, en maintenant le minimum à l'intérieur de cet intervalle. On détermine ainsi un minimum calculé de la fonction, dont on 20 observe qu'il n'est pas nécessairement égal au minimum absolu de la fonction. Cette approche garantit de trouver un minimum calculé qui est soit égal au minimum global de la fonction, soit très proche, tout en conservant la très grande simplicité d'implémentation récursive. La mise en oeuvre de la présente invention présente les mêmes 25 avantages que la trichotomie classique, dans le cas des fonctions convexes, et permet de déterminer un extrémum de la fonction pour les autres types de fonction. Ainsi, la mise en oeuvre de la présente invention permet la détermination du minimum d'une fonction, par exemple la fonction représentant le coût de codage associé à un pas de quantification, par application d'une 30 méthode récursive, même dans le cas où cette fonction est globalement convexe mais présente des petites concavités locales. 2907565 3 Selon des caractéristiques particulières, ladite grandeur physique est un pas de quantification. La présente invention s'applique, ainsi, à tous les cas d'utilisation d'une quantification, par exemple, pour le codage de signaux représentatifs d'images. 5 Selon des caractéristiques particulières, le procédé tel que succinctement exposé ci-dessus comporte, au cours d'une itération pour laquelle les valeurs candidates se trouvent dans un intervalle de valeurs dont la largeur est inférieure ou égale à une largeur limite prédéterminée, une étape de sélection d'une valeur optimale et d'arrêt des itérations. 10 Grâce à ces dispositions, on applique un critère classique d'arrêt des itérations afin de limiter la durée de la recherche. Selon des caractéristiques particulières, le procédé tel que succinctement exposé ci-dessus comporte, en outre, pour au moins une itération, lorsque les images, par ladite fonction, des valeurs candidates 15 correspondent à une concavité, une étape de sélection d'une valeur optimale et d'arrêt des itérations. Grâce à ces dispositions, même dans le cas des fonctions présentant une concavité locale prononcée, on détermine une approximation du minimum. 20 Selon des caractéristiques particulières, au cours de l'étape de sélection dudit nombre de nouvelles valeurs candidates pour réaliser une nouvelle itération, les nouvelles valeurs candidates sont uniformément réparties sur l'intervalle des nouvelles valeurs. Grâce à ces dispositions, on dispose de pas candidats décrivant 25 régulièrement l'évolution de la fonction sur l'intervalle de recherche. Selon des caractéristiques particulières, au cours de l'étape de sélection dudit nombre de nouvelles valeurs candidates pour réaliser une nouvelle itération, la valeur extrême de l'itération en cours conservée comme nouvelle valeur extrême est celle qui est la plus proche du minimum, sur les 30 valeurs candidates, de ladite fonction. On observe que, si le minimum de la fonction, parmi les valeurs de la fonction pour les pas candidats, se trouve sur l'une des valeurs extrêmes, celle2907565 4 ci est conservée dans l'intervalle de recherche de l'itération suivante et que, sinon, ce minimum se trouve au milieu du nouvel intervalle de recherche. La recherche récursive est donc efficace. Selon un deuxième aspect, la présente invention vise un procédé de 5 codage, caractérisé en ce que : - il comporte une étape de codage mettant en oeuvre un pas de quantification auquel est associée une fonction de coût de codage et - il met en oeuvre le procédé de détermination tel que succinctement exposé ci-dessus, pour déterminer un pas de quantification correspondant à un 10 minimum local de ladite fonction de coût, ladite étape de codage mettant en oeuvre ledit pas de quantification. Selon un troisième aspect, la présente invention vise un dispositif pour déterminer une valeur d'une grandeur physique dite optimale , par recherche d'une estimation d'un minimum local d'une fonction associée à ladite 15 grandeur physique, qui comporte un moyen de sélection d'un nombre d'au moins quatre valeurs dites candidates , adapté, de manière itérative : - lorsque les images, par ladite fonction, des valeurs candidates correspondent à une convexité, à sélectionner ledit nombre de nouvelles valeurs de candidates pour réaliser une nouvelle itération, 20 ledit moyen de sélection étant, en outre, adapté, pour au moins une itération : - lorsque les images, par ladite fonction, des valeurs candidates ne correspondent ni à une concavité, ni à une convexité, à sélectionner ledit nombre de nouvelles valeurs candidates pour réaliser une nouvelle itération, les 25 valeurs extrêmes sélectionnées comme nouvelles valeurs étant respectivement égales à une valeur extrême de l'itération en cours et à la valeur la plus proche et différente de l'autre valeur extrême de l'itération en cours. Selon des caractéristiques particulières, le moyen de sélection est adapté, pour sélectionner ledit nombre de nouvelles valeurs candidates pour 30 réaliser une nouvelle itération, à conserver la valeur extrême de l'itération en cours qui est la plus proche du minimum, sur les valeurs candidates, de ladite fonction. 2907565 5 Selon un quatrième aspect, la présente invention vise un dispositif de codage, qui comporte : - un moyen de codage mettant en oeuvre un pas de quantification auquel est associée une fonction de coût de codage et 5 - un dispositif de détermination tel que succinctement exposé ci-dessus, adapté à déterminer un pas de quantification correspondant à un minimum local de ladite fonction de coût, le moyen de codage mettant en oeuvre ledit pas de quantification. Selon un cinquième aspect, la présente invention vise un programme 10 d'ordinateur chargeable dans un système informatique, ledit programme contenant des instructions permettant la mise en oeuvre du procédé tel que succinctement exposé ci-dessus, lorsque ce programme est chargé et exécuté par un système informatique. Selon un sixième aspect, la présente invention vise un support 15 d'informations lisibles par un ordinateur ou un microprocesseur, amovible ou non, conservant des instructions d'un programme informatique, qui permet la mise en oeuvre du procédé tel que succinctement exposé ci-dessus. Les avantages, buts et caractéristiques de ce procédé de codage, de ce dispositif de détermination, de ce dispositif de codage, de ce programme 20 d'ordinateur et de ce support d'informations étant similaires à ceux du procédé de détermination d'un pas de quantification, tel que succinctement exposé ci-dessus, ils ne sont pas rappelés ici. D'autres avantages, buts et caractéristiques de la présente invention ressortiront de la description qui va suivre, faite, dans un but explicatif et 25 nullement limitatif, en regard des dessins annexés dans lesquels : - la figure 1 représente, sous forme d'un schéma bloc, un mode de réalisation particulier du dispositif de codage objet de la présente invention ; - la figure 2 représente, sous forme d'un logigramme, des étapes mises en oeuvre dans un mode de réalisation particulier du procédé objet de la 30 présente invention et - la figure 3 représente, schématiquement, un mode de réalisation particulier du dispositif objet de la présente invention. 2907565 6 Dans toute la description, on a particulièrement décrit une application de la présente invention à la détermination d'une estimation d'une valeur optimale de pas de quantification. Cependant, la présente invention ne se limite pas à ce type de grandeur physique mais s'étend, bien au contraire, à la 5 détermination d'une estimation d'une valeur optimale de toute grandeur physique associée à une fonction dont on recherche un extrémum. La figure 1 présente une mise en situation de l'invention dans un système comportant un codeur 105 et un décodeur 155 de signal multidimensionnel, par exemple de signal représentatif d'images. Avec le 10 codeur 105, une image originale 110 est compressée en vue de son stockage ou de sa transmission. Lors de cette compression, l'image subis les étapes de transformation, bloc 115, détermination du pas de quantification dit optimal , bloc 120, quantification, bloc 125, et codage entropique, bloc 130. Au cours de la transformation, bloc 115, l'image est transformée à 15 l'aide d'une transformée spatio-fréquentielle classiquement utilisée en compression des images, par exemple la DCT (acronyme de Discrete Cosine Transform ou transformée cosinus discrète) utilisée dans le standard JPEG (acronyme de Joint Picture Expert Group pour groupe d'expert en image) ou encore la transformée en ondelettes (utilisée dans le standard JPEG2000). 20 L'image est alors typiquement divisée en sous-parties (les blocs de la DCT ou les sous-bandes de la transformée en ondelettes). Au cours de la détermination du pas de quantification dit optimal , bloc 120, deux schémas différents peuvent s'appliquer. On peut choisir de quantifier chaque sous-partie du signal avec le même pas de quantification ou 25 déterminer un pas de quantification optimal indépendamment pour chaque sous-partie. La présente invention concerne ces deux cas, en s'appliquant, une seule fois, à tout le signal ou autant de fois qu'il y a de sous-parties, respectivement. Pour déterminer le pas de quantification dit optimal , on cherche à 30 minimiser une fonction de coût de codage du signal (par signal, on entend soit l'image complète, soit la sous-partie). 2907565 7 Le coût de codage s'écrit C(Q) = R(Q) + 1. D(Q), formule dans laquelle : - R(Q) est le débit nécessaire au codage du signal lorsqu'il est quantifié avec le pas de quantification Q, 5 - D(Q) est la distorsion (erreur quadratique) générée par le codage du signal dans l'image reconstruite, lorsqu'il est quantifié avec le pas Q, et - est un paramètre fixé par l'utilisateur, qui lui permet de choisir un compromis donné entre compression et qualité de l'image. On observe que le pas de quantification dit optimal n'est pas 10 nécessairement optimal sur l'ensemble de l'intervalle de recherche initial mais correspond localement à une approximation d'un minimum de la fonction de coût. On commence le calcul du minimum de coût de codage par la détermination d'un pas de quantification minimal Qmin et un pas de 15 quantification maximal Qmax. Ceux-ci sont en général prédéterminés. Par exemple on utilise respectivement 1 et 100. On détermine, également, une résolution minimale RM de pas de quantification, qui sert de condition d'arrêt, comme exposé plus loin. Cette résolution minimale vaut, par exemple, RM = 0,1. 20 On applique alors le procédé de détermination d'un pas de quantification dit optimal objet de la présente invention correspondant au minimum à la fonction de coût CO. Ce procédé est détaillé en regard des figures 2 et 3. On suppose, dans la suite de la description de la figure 1, que le pas 25 de quantification optimal est calculé pour l'image ou pour toutes les sous- parties de l'image. Au cours de la quantification, bloc 125, on quantifie l'image avec le(s) pas de quantification optimal(aux) obtenu(s) pour les différentes sous-parties. Il s'agit d'une quantification scalaire uniforme connue de l'homme du métier, telle 30 que celle utilisée dans le standard JPEG. Cette étape produit donc une suite de symboles de quantification représentatifs du signal. 2907565 8 Au cours du codage entropique, bloc 130, on applique un codage entropique aux symboles quantifiés produits précédemment. Le codage entropique est d'un type classique connu de l'homme du métier, comme le codage de Huffman (tel que celui mis en oeuvre dans le standard JPEG) ou le 5 codage arithmétique (tel que celui mis en oeuvre dans le standard JPEG2000). Cette étape produit une suite de données binaires qui représente le fichier compressé. Le fichier compressé 135 est soit stocké pour décompression ultérieure, soit transmis sur un moyen de communication tel que le réseau 10 internet, par le bloc fonctionnel 140. Avec le décodeur 155, le fichier compressé 135 est décompressée en vue de son stockage ou de son exploitation, par exemple sa diffusion ou sa visualisation sur un écran. Lors de cette décompression, l'image subit les étapes de décodage entropique, bloc 160, déquantification, étape 165, et 15 transformation inverse, bloc 170, pour former une image décompressée 175. Au cours du décodage entropique, bloc 160, le fichier compressé 135 est décodé avec le décodage entropique qui correspond au codeur entropique 130 utilisé précédemment. Ceci produit une suite de symboles quantifiés. 20 Au cours de la déquantification, bloc 165, les symboles quantifiés sont déquantifiés en utilisant une déquantification scalaire uniforme et un pas de quantification égal à celui utilisé lors de la quantification, bloc 125. Au cours de la transformation inverse, bloc 170, on applique aux symboles déquantifiés une transformée inverse de celle utilisée lors de la 25 transformation, bloc 115, par exemple une DCT inverse ou une transformée en ondelette inverse. L'image décodée 175 est ainsi produite et peut être affichée ou stockée. Dans cette section, on rappelle le fonctionnement de la trichotomie telle qu'utilisée dans l'état de l'art. Nous supposons que les valeurs Qmin, 30 Qmax et RM sont déterminées et que la fonction dont on veut trouver le minimum est la fonction C(.) décrite précédemment. Nous décrivons ici le comportement d'une fonction Trichotomie(f, min, max, epsilon) générique, 2907565 9 c'est-à-dire que, pour trouver le minimum qui nous intéresse, on appelle la fonction Trichotomie(C, Qmin, Qmax, RM). On suppose d'autre part que la fonction, f ou C, dont on souhaite trouver le minimum, est une fonction strictement convexe. 5 Au cours d'une étape d'appel de fonction, on appelle la fonction Trichotomie. Cet appel peut se faire avec les paramètres (C, Qmin, Qmax, RM), si c'est le premier, mais il peut également se faire avec d'autres paramètres, s'il s'agit d'un appel récursif de la fonction (voir étape d'appel récursif, plus loin). Au cours d'une étape de test de largeur d'intervalle, on calcule la 10 largeur de l'intervalle [min ;maxi, soit Imax - mini. Si cette valeur est inférieure à une valeur prédéterminée RM, la prochaine étape est l'étape d'arrêt et de sortie du résultat, qui revient à considérer que la largeur de l'intervalle est suffisamment petite, c'est-à-dire inférieure à la précision que l'on souhaite sur le pas de quantification qui réalise le minimum. On fournit alors, en sortie, le 15 centre de l'intervalle [min ; maxi, soit (min + max)/2 et la trichotomie est terminée. Sinon, l'étape suivante est le calcul de med1 et med2 telles que min bc>_d cas 2 : a >b cet c d cas 3 : a bet b REVENDICATIONS 1 - Procédé pour déterminer une valeur d'une grandeur physique dite optimale , par recherche d'une estimation d'un minimum local d'une fonction associée à ladite grandeur physique, qui comporte une étape (205) de sélection d'un nombre d'au moins quatre valeurs dites candidates et, de manière itérative : - lorsque les images, par ladite fonction, des valeurs candidates 10 correspondent à une convexité, une étape (240) de sélection dudit nombre de nouvelles valeurs candidates pour réaliser une nouvelle itération, caractérisé en ce qu'il comporte, pour au moins une itération : - lorsque les images, par ladite fonction, des valeurs candidates ne correspondent ni à une concavité, ni à une convexité, une étape (245) de 15 sélection dudit nombre de nouvelles valeurs candidates pour réaliser une nouvelle itération, les valeurs extrêmes sélectionnées comme nouvelles valeurs étant respectivement égales à une valeur extrême de l'itération en cours et à la valeur la plus proche et différente de l'autre valeur extrême de l'itération en cours. 20 2 û Procédé selon la revendication 1, caractérisé en ce ladite grandeur physique est un pas de quantification. 3 û Procédé selon l'une quelconque des revendications 1 ou 2, caractérisé en ce qu'il comporte, au cours d'une itération pour laquelle les valeurs candidates se trouvent dans un intervalle de valeurs dont la largeur est 25 inférieure ou égale à une largeur limite prédéterminée, une étape (212) de sélection d'une valeur optimale et d'arrêt des itérations. 4 - Procédé selon l'une quelconque des revendications 1 à 3, caractérisé en ce qu'il comporte, en outre, pour au moins une itération, lorsque les images, par ladite fonction, des valeurs candidates correspondent à une 30 concavité, une étape (235) de sélection d'une valeur optimale et d'arrêt des itérations. 2907565 18 5 û Procédé selon l'une quelconque des revendications 1 à 4, caractérisé en ce que, au cours de l'étape (240, 245) de sélection dudit nombre de nouvelles valeurs candidates pour réaliser une nouvelle itération, les nouvelles valeurs candidates sont uniformément réparties sur l'intervalle des 5 nouvelles valeurs. 6 û Procédé selon l'une quelconque des revendications 1 à 5, caractérisé en ce que, au cours de l'étape (240, 245) de sélection dudit nombre de nouvelles valeurs candidates pour réaliser une nouvelle itération, la valeur extrême de l'itération en cours conservée comme nouvelle valeur extrême est celle qui est la plus proche du minimum, sur les valeurs candidates, de ladite fonction. 7 û Procédé de codage, caractérisé en ce que : - il comporte une étape de codage (105) mettant en oeuvre un pas de quantification auquel est associée une fonction de coût de codage et - il met en oeuvre le procédé de détermination selon l'une quelconque des revendications 1 à 6, pour déterminer un pas de quantification correspondant à un minimum local de ladite fonction de coût, ladite étape de codage mettant en oeuvre ledit pas de quantification. 8 û Dispositif pour déterminer une valeur d'une grandeur physique dite optimale , par recherche d'une estimation d'un minimum local d'une fonction associée à ladite grandeur physique, qui comporte un moyen (300, 303, 306, 308, 312) de sélection d'un nombre d'au moins quatre valeurs dites candidates , adapté, de manière itérative : - lorsque les images, par ladite fonction, des valeurs candidates 25 correspondent à une convexité, à sélectionner ledit nombre de nouvelles valeurs de candidates pour réaliser une nouvelle itération, caractérisé en ce que ledit moyen de sélection est, en outre, adapté, pour au moins une itération : - lorsque les images, par ladite fonction, des valeurs candidates ne 30 correspondent ni à une concavité, ni à une convexité, à sélectionner ledit nombre de nouvelles valeurs candidates pour réaliser une nouvelle itération, les valeurs extrêmes sélectionnées comme nouvelles valeurs étant respectivement 2907565 19 égales à une valeur extrême de l'itération en cours et à la valeur la plus proche et différente de l'autre valeur extrême de l'itération en cours. 9 û Dispositif selon la revendication 8, caractérisé en ce que le moyen de sélection (300, 303, 306, 308, 312) est adapté, pour sélectionner ledit 5 nombre de nouvelles valeurs candidates pour réaliser une nouvelle itération, à conserver la valeur extrême de l'itération en cours qui est la plus proche du minimum, sur les valeurs candidates, de ladite fonction. 10 û Dispositif de codage (300), caractérisé en ce qu'il comporte : - un moyen de codage mettant en oeuvre un pas de quantification 10 auquel est associée une fonction de coût de codage et - un dispositif de détermination selon l'une quelconque des revendications 8 ou 9, adapté à déterminer un pas de quantification correspondant à un minimum local de ladite fonction de coût, le moyen de codage mettant en oeuvre ledit pas de quantification. 15 11 - Programme d'ordinateur chargeable dans un système informatique, ledit programme contenant des instructions permettant la mise en oeuvre du procédé selon l'une quelconque des revendications 1 à 7, lorsque ce programme est chargé et exécuté par un système informatique. 12 - Support d'informations (306, 308, 312, 316) lisibles par un 20 ordinateur ou un microprocesseur, amovible ou non, conservant des instructions d'un programme informatique, caractérisé en ce qu'il permet la mise en oeuvre du procédé selon l'une quelconque des revendications 1 à 7.