Brevet FR3024263A1 — publié le 20160129

FR À & 04 6e84263 1 Procédé pour choisir un algorithme de compression en fonction du type d'image Les images peuvent appartenir à des types très différents. En particulier, il existe des images très « graphiques » constituées de lignes nettes, et des images beaucoup plus « naturelles » constituées de nombreux dégradés de couleurs. Chaque algorithme de compression utilise une représentation des données qui lui est propre. Par exemple, la compression par ondelettes sépare l'image en sous-images successives avec des transformations fréquentielles, alors que certains codecs, notamment développées par la demanderesse effectuent des différences entre les valeurs numériques de l'image. L'invention se propose donc de définir un codec qui sélectionne automatiquement à l'encodage la meilleure représentation des données à partir du type de données image, et effectue la transformée inverse à la décompression à l'aide d'une information contenue dans l'en-tête de fichier. Chacun des types d'algorithme est plus ou moins adapté à certains types d'images. En particulier, les représentations fréquentielles modélisent très bien les images faiblement contrastées alors que les représentations par différences modélisent bien les images graphiques ou fortement contrastées. Chacune des méthodes (Différences / Ondelettes) peut être utilisée en mode avec ou sans pertes. La transformation est appliquée à chacune des couches séparément. En revanche, le choix du type de transformation se fait sur la couche considérée comme la plus représentative, par exemple la couche Y dans le cas d'une image ayant préalablement subi une transformée YCbCr, ou bien la couche représentant le mieux 3024263 2 l'intensité lumineuse d'une image dans le cas d'une transformation colorimétrique sans perte. Lorsque l'algorithme utilisé est une transformation par ondelettes, cette 5 transformation peut être effectuée par une implémentation spécifique des ondelettes et du codage binaire, ou bien à l'aide de formats standards tels que le Jpeg2000 ou le PGF. Dans l'exemple suivant, et de manière non limitative, les formats par ondelettes utilisés seront le Jpeg2000 et le PGF. 10 Lorsque l'algorithme utilisé est une transformation par différences, la transformation par différences consiste à faire la différence entre les valeurs de deux pixels adjacents sur une même couche, puis à quantifier cette différence par un facteur pré-défini Q. Afin de ne pas propager l'erreur, on effectue la différence par rapport à une valeur décompressée définie ci-dessous. De la même manière, si deux sens de différences 15 sont possibles, on détermine, à partir des valeurs décompressées, quel serait le sens générant la différence la plus faible. On calcule alors la différence à la compression et la décompression. De manière plus détaillée, cette méthode de codage s'effectue de la manière 20 suivante : On considère une matrice à transformer, représentant une couche d'une image en 2 dimensions. On adopte la nomenclature suivante : Vij est une valeur initiale de la matrice, pour laquelle i représente le numéro de ligne et j le numéro de colonne. Cij représente la valeur compressée correspondante, et Dij 25 la valeur décompressée correspondante Ainsi, pour une matrice de 5x5, on a la répartition des valeurs suivantes : VI I V12 V13 V14 V15 V21 V22 V23 V24 V25 V31 V32 V33 V34 V35 V41 V42 V43 V44 V45 V51 V52 V53 V54 V55 C11.- C12 C13 C14 C15 C21 C22 C23 C24 C25 C31, C32 C33 C34 C35 C41 C42 C43 C44 C45 C51 C52 C53 C54 C55 Dll D12 D13 D14 D15 D21 D22 D23 D24 D25 D31 D32 D33 D34 D35 D41 D42 D43 D44 D45 D51 D52 D53 D54 D55 Prenons un exemple numérique avec les valeurs numériques suivantes pour chaque 30 Vij , ainsi qu'un coefficient de quantification Q = 3: 3024263 3- 0 0 0 0.- 0 0 0 255 253 0 0 0 255 253 0 0 0 255 253 0 0 0 - 253 0 255 On effectue les différences ligne par ligne, de la première à la dernière, de gauche à droite. On conserve la première valeur V11 telle quelle. 5 Dans la première ligne horizontale, on effectue pour chaque valeur V1j, la différence par rapport à la valeur décompressée située à sa gauche Dlj-1, puis on quantifie et on arrondit. Ainsi : Dll =C11 =V11=0 ; C12 = ARRONDI (( V12 - Dll ) / Q) = ARRONDI ( ( 0 - 0 ) / 3 ) = 0 10 D12 = ARRONDI ( Dll + ( C12 * Q) ) = ARRONDI ( 0 + 0 * 3 ) = 0 Ainsi de suite jusqu'à la fin de la ligne. Pour chacune des lignes suivantes, on calcule la valeur compressée Cil de la 15 première case de ladite ligne en effectuant une différence entre la valeur courante Vil et la valeur décompressée de la ligne juste au-dessus Di-1 1 : On aura donc, par exemple pour la 2e ligne : C21 = ARRONDI (( V21 - Dll ) / Q) = ARRONDI ( ( 0 - 0 ) / 3 ) = 0 D21 = ARRONDI ( Dll + ( C21 * Q) ) = ARRONDI ( 0 + ( 0 * 3 ) ) = 0 20 Pour chacune des valeurs suivantes de la ligne, on calcule pour chaque valeur Vij la différence horizontalement si (Di-1 j - D i-1 j-1) est inférieur en valeur absolue à (Di j-1 - D i-1 j-1), et on calcule la différence verticalement dans le cas contraire. 25 Ainsi, pour la valeur V22 : - La valeur absolue de (D12-D11) vaut 0 ; - La valeur absolue de (D21-D11) vaut 0 ; - Les deux valeurs étant égales, on choisit la différence verticale ; 3024263 -4 - On calcule donc la valeur compressée : C22 = ARRONDI (( V22 - D12 ) / Q) =ARRONDI(( 0- )/3 )=0 - On calcule ensuite la valeur décompressée : D22 = ARRONDI ( D12 + ( C22 * Q) ) = ARRONDI ( 0 + 0 * 3 ) = 0 5 Ainsi, pour la valeur V23 : - La valeur absolue de (D13-D12) vaut 0 ; - La valeur absolue de (D22-D12) vaut 0 ; - Les deux valeurs étant égales, on choisit la différence verticale ; - On calcule donc la valeur compressée : C23 = ARRONDI (( V23 - D13) / Q) 10 ARRONDI ( ( 255 - 0 ) / 3 ) = 85 - On calcule ensuite la valeur décompressée : D23 = ARRONDI ( D13 + ( C23 * Q) ) = ARRONDI ( 0 + 85 * 3 ) = 255 Ainsi, pour la valeur V24 : - La valeur absolue de (D14-D13) vaut 0 ; 15 - La valeur absolue de (D23-D13) vaut 255 ; - La valeur de la première différence (horizontale) étant la plus petite, on choisit la différence horizontale ; - On calcule donc la valeur compressée : C24 = ARRONDI (( V24 - D23) / Q) = ARRONDI ( ( 253 - 255 ) / 3 ) = -1 20 - On calcule ensuite la valeur décompressée : D24 = ARRONDI ( D23 + ( C24 * Q) ) = ARRONDI ( 255 - 1 * 3 ) = 252 Par itération, on obtient pour cette matrice les valeurs compressées et décompressées suivantes : 25 Vil V12 V13 V14 V15 V21 V22 V23 V24 V25 V31 V32 V33 V34 V35 V41 V42 V43 V44 V45 V51 V52 V53 V54 V55 0 0 0 0 0 0 0 255 253 0 0 0 255 253 0 0 0 255 253 0 0 0 255 253 0 C11 C12 C13 C14 C15 C21 C22 C23 C24 C25 C31 C32 C33 C34 C35 C41 C42 C43 C44 C45 C51 C52 C53 C54 C55 0 0 0 0 0 0 0 85 -1 -84 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 Dli D12 D13 D14 D15 D21 D22 D23 D24 D25 D31 D32 D33 D34 D35 D41 D42 D43 D44 D45 D51 D52 D53 D54 D55 0 0 0 0 0 0 0 255 252 0 0 0 255 252 0 0 0 255 252 0 0 0 255 252 0 3024263 5 Lorsque Q = 1, cette transformation est sans perte. Lorsque Q > 1, elle est avec pertes. 5 On appelle cette transformation des données « APE » Une fois cette transformation « APE » effectuée, on applique une transformation RLE (Run-Length Encoding) puis une compression à l'aide de l'algorithme Bzip2 sur les 10 données obtenues. La chaîne de compression est alors la suivante, pour chacune des couches de l'image : APE, RLE, Bzip Dans un mode de réalisation, on applique deux méthodes de compression par ondelettes, par exemple Jpeg2000 et le PGF, ainsi que la chaîne de compression 15 APE, RLE, Bzip, décrite plus haut, sur 3 images différentes : - La figure 1 est une copie d'écran, contenant beaucoup de texte sur fond blanc, et représente un exemple d'image de type « graphique » ; - La figure 2 est une photographie de ville avec de forts contrastes entre les bâtiments et le ciel, les lumières, etc. Elle représente un exemple d'image de 20 type « fort contraste »; - La figure 3 est une photographie d'un meeting aérien contenant beaucoup de dégradés de couleurs. Elle représente un exemple d'image de type « faible contraste ». 25 On représente l'efficacité de chacune des méthodes (APE / RLE / Bzip, Jpeg2000, PGF) à l'aide d'une courbe dite de PSNR, qui représente la qualité de l'image restituée après compression puis décompression. A chaque paramètre d'encodage correspond un poids de fichier et une valeur de qualité dite PSNR, comprise entre 0 et 100. Le PSNR est une mesure standard, ici calculée sur la couche Y, 100 étant la 30 meilleure qualité possible et correspond à une compression sans perte. On considère qu'une compression est plus performante qu'une autre lorsque, à poids équivalent, elle possède un meilleur PSNR, ou lorsque à PSNR équivalent, le poids est inférieur. 3024263 6 La figure 4 et le tableau ci-dessous représentent l'évolution du PSNR en fonction du poids d'image pour l'image représentée en figure 1. 5 ramure / eàei PSNR Algorithme Paramètre/ Fereteur de Poids (fco) arortification APE + RLE + zlib Q = 80 502 100 PGF PGFConsole, -q 0 1038 100 Jpeg2000 OpenJpeg, 882 100 image_to_j2k, pas de paramètre La figure 5 et le tableau ci-dessous représentent l'évolution du PSNR en fonction du poids d'image pour l'image représentée en figure 2. 10 Programme15" Algorithme Ferraillâtes / Porteur de Poids (-er) qtretettificittion APE + RLE + zlib 1 5832 100 PGF PGFConsole, 0 7893 100 Jpeg2000 OpenJpeg, 7266 100 image_to_j2k, pas de paramètre APE + RLE + zlib Q=22 1155 34 PGF PGFConsole, 0 1212 43 Jpeg2000 OpenJpeg, 1112 44 image_to_j2k, pas de paramètre La figure 6 et le tableau ci-dessous représentent l'évolution du PSNR en fonction du 15 poids d'image pour l'image représentée-en figure 3 : Programme / 11gorithme Paramètres / ..Ëiretear de Poids (kr-) qua krtion APE + RLE + Alrb Q = 1 PGF PGFConsole, -q 0 Jpeg2000 OpenJpeg, image_to-}2k, pas de paramètre 15175 14303 14165 100 100 100 On constate donc que : 20 3024263 -7 - Les codages par ondelettes ont des performances poids/qualités tendanciellement proches, alors que l'APE obtient des résultats radicalement différents ; - Dans le cas de l'image 1 (Image graphique), l'APE est meilleur dans tous les 5 cas ; - Dans le cas de l'image 2 (image fortement contrastée), l'APE est meilleur sur les hautes qualités, les codages par ondelettes pour les plus fortes compressions ; - Dans le cas de l'image 3 (image faiblement contrastée), les codages par 10 ondelettes sont meilleurs dans tous les cas. Dans un premier mode de réalisation de l'invention, le choix de l'algorithme s'effectue après la transformation colorimétrique, YCbCr dans les exemple illustrés. 15 Pour choisir l'algorithme, on pratique de la manière suivante : - on compte le nombre de chacune des valeurs sur la couche la plus représentative (idéalement Y) ; - On construit un histogramme des valeurs tel que représenté dan la figure 7: 20 - On note, pour chaque valeur k généralement comprise entre 0 et 255, le nombre de fois n(k) que cette valeur est présente dans la couche : - Le nombre de pixels de la couche est donc égal à la somme des n(k) : 25E, N = /13(c) k=o 25 - La métrique « FD2 » donne une idée de l'aspect « à pic » de l'histogramme : FD2 355 max n(t) - .4 * (n.(k - 1) ± n(le + 1)) - 0 .1 * (n(k - 2) ± rt.(k + 2)), 0 ]) 2 N k=0 - On effectue la métrique FD2, sur tout ou partie d'une couche de l'image - Plus FD2 est important, plus les valeurs sont concentrées 3024263 a e j-Image2 image3 PD2 0,18 0,00,065 1,1E -Ô6 On voit donclien_queles_différents-types 4:V-images appartiennent à des ordres de grandeur différénts, et que la formule est bien discriminante. 5 - On sépare l'image de la manière suivante : o FD2 > 0.075 : Image graphique o FD2 > 104 : Image fortement contrastée o Sinon : Image faiblement contrastée 10 - Si FD2 > 0.075, on choisit une transformée par différences, par exemple APE + RLE + zlib; - Dans le cas d'une image fortement contrastée, on choisit une transformée par différences, par exemple APE + RLE + zlib dans les modes sans perte et presque sans perte, et un codage par ondelettes dans les autres cas 15 - Dans le cas d'une image faiblement contrastée, on effectue un codage par ondelettes dans tous les cas, par exemple du type JPEG ou PGF. - On stocke dans l'en-tête de fichier le type d'image - On effectue les opérations inverses à la décompression en fonction du type d'image 20 Dans un second mode de réalisation, on compte le nombre de triplets de couleurs RGB uniques de l'image, que l'on ramène à la taille de l'image, de préférence en le divisant par un coefficient fonction du nombre de pixels de l'image. Lorsque le nombre de triplets de coureur RGB uniques de l'image, raméné à la taille de l'image, 25 est en-dessous d'un seuil pré-défini, on considère l'image comme étant une image graphique ; lorsqu'il est au-dessus d'un second seuil, plus élevé que le premier, on considère l'image comme étant une image faiblement contrastée. Entre ces deux seuils, on considère l'image comme étant fortement contrastée. On applique alors les mêmès transformations que dans le premier mode de 30 réalisation : - Dans le cas d'une image fortement contrastée, on choisit une transformée par différences, par exemple APE + RLE + zlib dans les modes sans perte et presque sans perte, un codage par ondèlettes sinon 3024263 9 - Dans le cas d'une image faiblement contrastée, on effectue un codage par ondelettes dans tous les cas, par exemple du type JPEG ou PGF. - On stocke dans l'en-tête de fichier le type d'image - On effectue les opérations inverses à la décompression en fonction du type 5 d'image De façon plus générale : On propose donc un procédé de compression d'une image, caractérisé en ce que : on effectue un calcul d'un niveau de nuances de l'image sur au moins 10 l'ensemble d'une couche de l'image, selon le type des nuances sur au moins l'ensemble d'une couche, on classifie l'image dans l'une des trois classes suivantes : o une première classe si l'image est d'un type graphique ; o une deuxième classe si l'image est d'un type fortement contrastée ; 15 o une troisième classe si l'image est d'un type faiblement contrastée ; et, on choisit un traitement de compression en fonction de la classe de l'image : o un traitement du type par différences, si l'image est de la première ; o un traitement du type fréquentiel, de préférence utilisant des ondelettes, si l'image est de la troisième classe ; et, 20 o si l'image est de la deuxième classe : ^ pour une compression sans perte ou avec une faible perte, on utilise de préférence un traitement du type par différences, et, ^ dans les autres cas on utilise de préférence un traitement du type fréquentiel, de préférence utilisant des ondelettes. 25 Avantageusement, on effectue le calcul sur l'ensemble d'une couche la plus représentative de l'image (par exemple la couche Y) Avantageusement, ces étapes peuvent être précédées d'une transformation 30 colorimétrique, avec ou sans pertes, sur les données d'entrées. Par exemple, on peut appliquer une transformation YCbCr sur des données d'entrée RGB. Afin de classifier l'image, chaque nuance correspondant à une valeur de nuance (de préférence k=0-255 dans le cas de couches 8 bits), pour chaque nuance on calcule le 3024263 - 10 - nombre n(k) de pixels présentant cette nuance ; puis, on calcule un indicateur de concentration des nuances de l'image autour de la valeur k, par exemple : E(k) = n(k) - 0,4 ( n(k-1)+n(k+1) ) - 0,1 ( n(k-2)+n(k+2) ) , en faisant la différence entre le nombre de pixels n(k) de la nuance (k) considérée et 5 une proportion de ceux de ses voisines, de préférence de ses voisines de premier rang (k-1 et k+1) et de deuxième rang (k-2 et k+2), la proportion respective étant plus réduite pour les voisines de rang le plus élevé, par exemple une proportion de 80% pour chacune des voisines de premier rang, c'est-à-dire les voisines immédiates de la nuance (k) considérée et de 20% pour chacune des voisines de deuxième rang, c'est- 10 à-dire les voisines immédiates des voisines de premier rang. De préférence, la somme des proportions des valeurs voisines est égale à un. Dans l'exemple illustré, on a effectivement la somme des proportions qui est égale à 1 (0,4+0,4+0,1+0,1=1). On conserve ensuite l'indicateur de concentration des nuances autour des valeurs k 15 (E(k)) supérieurs à un certain seuil, de préférence les indicateurs de concentration positifs, c'est-à-dire Max(E(k),0), et on ramène chacun de ces indicateurs de concentration à la taille de l'image, par exemple au nombre (N) total des pixels de l'image. 20 De préférence, pour une meilleure discrimination entre les types d'images, c'est-à- dire pour faciliter la classification, on élève ensuite le résultat Max(E(k))/N à une puissance strictement supérieure à 1, de préférence égale à 2. On obtient ensuite une métrique (FD) en compilant ces résultats pour l'ensemble de 25 la couche, de préférence en faisant la somme des résultats ainsi obtenus pour l'ensemble des nuances de la couche. Ainsi, dans l'exemple illustré : FD2 = E (Max(E(k))/N)2 , pour k variant de 0 à 255 REVENDICATIONS: 1. Procédé de compression d'une image, caractérisé en ce que : on effectue un calcul d'un niveau de nuances de l'image sur au moins l'ensemble d'une couche de l'image ; selon le type des nuances d'au moins l'ensemble d'une couche de l'image, on classifie l'image dans l'une des trois classes suivantes : o une première classe si l'image est d'un type graphique ; o une deuxième classe si l'image est d'un type fortement contrastée ; o une troisième classe si l'image est d'un type faiblement contrastée ; et, on choisit un traitement de compression en fonction de la classe de l'image : o un traitement du type par différences, de préférence du type APE, si l'image est de la première ; o un traitement du type fréquentiel, de préférence utilisant des ondelettes, si l'image est de la troisième classe ; et, o si l'image est de la deuxième classe : ^ pour une compression sans perte ou avec une faible perte, on utilise de préférence un traitement du type par différences, de préférence du type APE, et, ^ dans les autres cas on utilise de préférence un traitement du type fréquentiel, de préférence utilisant des ondelettes. 2. Procédé selon la revendication 1, caractérisé en ce que l'on effectue le calcul sur une couche la plus représentative des nuances (k) de ladite image ; puis, 3. Procédé selon la revendication 2, caractérisé en ce que pour classifier l'image, chaque nuance correspondant à une valeur de nuance (k=0-255), pour chaque nuance : - on calcule le nombre n(k) de pixels présentant cette nuance ; puis, - on calcule des indicateurs de concentration des nuances en faisant la différence entre le nombre de pixels n(k) de la nuance (k) considérée et une proportion de ceux de ses voisines ; puis, 3024263 - 12 - - on conserve les indicateurs de concentration des nuances (E(k)) supérieurs à un certain seuil, de préférence les indicateurs de concentration positifs, et on ramène chacun de ces indicateurs de concentration à la taille de l'image, de préférence au nombre (N) total des pixels de l'image, puis, 5 - on compile les résultats obtenus pour chaque nuance sur l'ensemble de la couche, de préférence en faisant la somme (FD2) des résultats ainsi obtenus pour l'ensemble des nuances de la couche. 10 4. Procédé selon la revendication 3, caractérisé en ce que la proportion respective est plus réduite pour les voisines de rang le plus élevé. 5. Procédé selon l'une des revendications 2 ou 3, caractérisé en ce qu'on utilise les voisines de premier rang (k-1 et k+1) et de deuxième rang (k-2 et k+2), en affectant 15 de préférence une proportion de 80% pour chacune des voisines de premier rang, c'est-à-dire les voisines immédiates de la nuance (k) considérée et de 20% pour chacune des voisines de deuxième rang, c'est-à-dire les voisines immédiates des voisines de premier rang. 20 6 Procédé selon l'une des revendications 3 à 5, caractérisé en ce que la somme des proportions des valeurs voisines est égale à un. 7. Procédé selon l'une des revendications 3 à 6, caractérisé en ce que l'on élève ensuite chaque indicateur de concentration conservé à une puissance strictement 25 supérieure à 1, de préférence égale à 2. 8. Procédé selon l'une des revendications 1 à 7, caractérisé en ce que l'on applique une transformation colorimétrique sur les données d'entrée, avant sélection de la couche la plus représentative. 30 9. Procédé selon la revendication 8, caractérisé en ce que l'on applique une transformation YCbCr à des données d'entrée de type RGB ou BGR 3024263 -13- 10. Procédé selon l'une des revendications 1 à 9, caractérisé en ce que les données d'entrée ou après transformation colorimétrique sont de type YCbCr ou YUV, et que la couche la plus représentative sélectionnée est la couche Y. 5 11. Procédé selon la revendication-1, caractérisé en ce que le calcul d'un niveau de nuances de l'image comprend le calcul du nombre de combinaisons RGB uniques sur l'ensemble de l'image. 12. Procédé selon la revendication 11, caractérisé en ce que l'on divise le nombre 10 de combinaisons RGB uniques sur l'ensemble de l'image par un coefficient fonction du nombre de pixels de l'image. 13. Procédé selon l'une des revendications 11 et 12, caractérisé en ce que l'on compare le nombre de combinaisons RGB uniques sur l'ensemble de l'image ou le 15 nombre de combinaisons RGB uniques sur l'ensemble de l'image divisé par ledit coefficient à un ensemble de seuils, et que l'on classifie l'image selon la règle suivante: - En dessous d'un premier seuil, on classe l'image dans la première classe ; - Au-dessus d'un second seuil, supérieur au premier, on classe l'image dans la 20 troisième classe ; - Entre le premier et le second seuil, on classe l'image dans le seconde classe.