Bonjour,
Je viens de faire quelques essais et de constater que le codage de golomb est 2x plus efficace quand il traite les données par groupe de 4 bits plutôt que par groupe de 8 bits (dans un fichier .bmp non compressé par exemple)
A la rigueur, ça peut sembler logique car vu que ce sont des valeurs de pixels de 0 à 255, il y a énormément d'endroit avec des sortes de gros applats de couleurs (qui se retrouvent "compactés" en une série de petites valeurs entre 0 et 15) et surout que les valeurs "différencielles" sont alors limitées à 16 (4 bits), ce qui plaît très bien à la compression de golomb qui n'a alors besoin d'y coder que de 1 à 9 bits (plus souvent 1 que 9 ...) par occurence trouvée.
Ci-dessous, le résultat d'un test effectué avec des blocs de 4 bits sur une image .bmp non compressé :
sum = 3330706 sum2 = 10472230
Counter[0] = 1711859 (51%) [size=1 16%]
Counter[5] = 228370 (6%) [size=3 6%]
Counter[7] = 176923 (5%) [size=3 5%]
Counter[12] = 170486 (5%) [size=5 8%]
Counter[10] = 144048 (4%) [size=5 6%]
Counter[4] = 109019 (3%) [size=5 5%]
Counter[3] = 108859 (3%) [size=5 5%]
Counter[8] = 94832 (2%) [size=7 6%]
Counter[14] = 84276 (2%) [size=7 5%]
Counter[15] = 82344 (2%) [size=7 5%]
Counter[13] = 79026 (2%) [size=7 5%]
Counter[2] = 78890 (2%) [size=7 5%]
Counter[11] = 75212 (2%) [size=7 5%]
Counter[9] = 70576 (2%) [size=7 4%]
Counter[6] = 58767 (1%) [size=7 3%]
Counter[1] = 57219 (1%) [size=9 4%]
Compression = 254% (3330706 in 1310052 out)
sum est la taille en **octets** du fichier source
sum2 est la taille en **bits** (soit à diviser par 8 pour avoir la taiile en octet) + il y a 256 octets rajoutés à la taille finale pour stocker la table des valeurs classées des plus courantes au moins courantes
size est la taille en bits de chacune des occurences de cette valeur
Le premier pourcentage des lignes Counter[qqchose] correspond au pourcentage d'occurence de cette valeur par rapport à totale des occurences de toutes les valeurs et le second pourcentage est la taille totale utilisée pour le stockage de toutes les occurences qui ont cette valeur.
La même chose mais en traitant par octet (8bits) et non pas par quartet (4 bits)
sum = 1665353 sum2 = 10565825
Counter[245] = 206383 (12%) [size=1 1%]
Counter[247] = 145761 (8%) [size=3 4%]
Counter[252] = 128816 (7%) [size=3 3%]
Counter[250] = 108755 (6%) [size=5 5%]
Counter[243] = 90474 (5%) [size=5 4%]
Counter[244] = 89522 (5%) [size=5 4%]
Counter[242] = 61132 (3%) [size=5 2%]
Counter[248] = 54127 (3%) [size=7 3%]
Counter[238] = 45097 (2%) [size=7 2%]
Counter[241] = 40199 (2%) [size=7 2%]
Counter[253] = 39188 (2%) [size=7 2%]
Counter[239] = 35433 (2%) [size=7 2%]
Counter[246] = 34551 (2%) [size=7 2%]
Counter[249] = 33898 (2%) [size=7 2%]
Counter[251] = 31821 (1%) [size=7 2%]
...
Counter[8] = 176 (0%) [size=15 0%]
Counter[5] = 168 (0%) [size=15 0%]
Counter[6] = 161 (0%) [size=15 0%]
Counter[4] = 152 (0%) [size=17 0%]
Compression = 125% (1665353 in 1321752 out)
=> la compression par paquets de 4 bits y semble donc 2x plus efficace que par paquets de 8 bits
A noter que je suis arrivé à ce test après avoir remarqué initialement que la compression par paquets de 2 octets étant vraiment bien moins efficace que par paquets d'un octet sur les données d'un fichier .bmp non compressé
=> je me suis alors dit "si ça compresse bien mieux par blocs d'un octet que par blocs de 2 octets, ça compresserait peut-être encore mieux avec des moitiés d'octets ???"
A partir de là, je ne serait même pas étonné que ça compresse encore mieux avec des blocs d'un quart d'octet
(par contre, je ne pense pas que ça marcherait bien avec des blocs d'un seul bit car le codage de golomb n'y servirait alors plus à rien ...)
=> je vais tester ça pour voir
Quelqu'un aurait des infos/idées sur le sujet ?
Rectificatif : à première vue, ce n'est pas si efficace car si la compression est 2x plus efficace, le nombre d'éléments en entrée est aussi le double
=> ça revient un peu au même
\home\yannoo\dev\compression>cat moteurs.tif | ./morecurrent4 | tail -2
Byte Compression = 115% (1665353 bytes in / 1374564 bytes out)
Val Compression = 231% (3330706 elems in / 1374564 bytes out)
\home\yannoo\dev\compression>cat moteurs.tif | ./morecurrent8 | tail -2
Byte Compression = 114% (1665353 bytes in / 1386264 bytes out)
Val Compression = 114% (1665353 elems in / 1386264 bytes out)
\home\yannoo\dev\compression>
\home\yannoo\dev\compression>cat moteurs.tif | ./morecurrent16 | tail -2
Byte Compression = 128% (1665354 bytes in / 1225792 bytes out)
Val Compression = 64% (832677 elems in / 1225792 bytes out)
=> les compressions par quartets et par blocs de 2 octets sont plus efficaces que la compression par blocs d'un seul octet
==> j'ai donc de bonnes intuitions
[par contre, je comprend pas la logique pourquoi sans marche mieux dans les 2 sens ... et surtout pourquoi c'est la compression par blocs de 2 octets qui est la plus efficace alors que j'aurais logiquement crû le contraire ...)
edit 2 : il y a du nouveau
j'ai rajouté un systême de regroupagement des couleurs très proches les unes des autres avant d'en faire la compression + fait un petit script shell de test
4 bits : mini[16]=109% maxi[15]=399% moy=197%
8 bits : mini[34]=130% maxi[175]=798% moy=267%
16 bits : mini[34]=131% maxi[175]=708% moy=243%
Les indices des tableaux mini et maxi sont les seuils de regroupement, les pourcentages de mini et maxi correspondent aux valeurs "Byte Compression" générées par les executables ./morecurrent[4,8,16] et la valeur de moy correspond à la moyenne de tous les tests avec un seuillage/regroupement des couleurs allant de 0 à 255
(le regroupement/seuillage se fait avec value &= ~(step) pour step allant de 0 à 255 et au dessus de 175 la valeur de seuil n'augmente plus le taux de compression => je pense que 175 doit être l'intensité médiane de l'image testée ou qqchose du style)
=> la compression en 8 bits à donc l'air d'être celle qui donne les meilleurs résultats en moyenne, celle en 4 bits semblant carrément à la ramasse (sauf pour les valeurs décimales style 10, 20, 30, ... où elle semble bizarrement assez efficace), celle en 16 bits étant très proche de celle en 8 bits mais un peu moins bien.
[par contre, j'ai l'impression qu'il vaut mieux utiliser la compression par quartet quand on veut une qualité maximale, cf. sans seuillage/regroupement des couleurs et du fait de sa gestion très efficace des "fonds de couleurs unis" grâce à son découplage bits de poids forts / bits de poids faibles)
==> je commence (enfin) vraiment à comprendre pourquoi pas mal d'algos de compression d'images utilisent une "compression par plan de bits" plutôt qu'une "compression par blocs d'octets" ...
===> je vais donc essayer dans la semaine d'adapter mon programme de compression d'image par ondelette en m'appuyant sur un format planar plutôt que sur le format packet qu'il utilise pour l'instant
[à la base, j'ai commencé à faire mes recherches sur les codages de Golomb/Rice/Elias/Gamma/Delta/Zeta et autres parce que j'ai remarqué que la compression par Zlib était vraiment d'une très très grande lenteur (relative), plus de 90% du temps CPU était squatté dans mon programme de compression d'images par les routines de compression de Zlib, tout le reste cf. échantillonage/réordonnancement/quantification/transformée en ondelettes/RLE ne prennant même pas 10% du temps total nécessaire à la compression d'une image/séquence vidéo dans mon algo de compression, algo assez ressemblant à celui utilisé pour les images .jpg]
@+
Yannoo
Partager