Amélioration de la compression par codage de Golomb

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 8O

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

Je viens de commencer à remplacer les codes de Golomb/Rice correspondants aux valeurs de 0 à 255 par une décomposition de ces mêmes valeurs en deux nombres premiers
(où chacun de ces 2 nombres premiers est représenté par un code de Golomb/Rice indexant une table des nombres premiers => la multiplication de ces 2 nombres premiers donne alors approximativement la valeur ainsi décomposée)

1 : {0,0} = 1x1 (2 bits) [approx = 1, diff = 0]
2 : {1,0} = 2x1 (3 bits) [approx = 2, diff = 0]
3 : {2,0} = 3x1 (4 bits) [approx = 3, diff = 0]
4 : {1,1} = 2x2 (4 bits) [approx = 4, diff = 0]
5 : {3,0} = 5x1 (4 bits) [approx = 5, diff = 0]
6 : {2,1} = 3x2 (5 bits) [approx = 6, diff = 0]
7 : {4,0} = 7x1 (4 bits) [approx = 7, diff = 0]
8 : {4,0} = 7x1 (4 bits) [approx = 7, diff = 1]
9 : {2,2} = 3x3 (6 bits) [approx = 9, diff = 0]
10 : {3,1} = 5x2 (5 bits) [approx = 10, diff = 0]
11 : {5,0} = 11x1 (5 bits) [approx = 11, diff = 0]
12 : {6,0} = 13x1 (5 bits) [approx = 13, diff = -1]
13 : {6,0} = 13x1 (5 bits) [approx = 13, diff = 0]
14 : {4,1} = 7x2 (5 bits) [approx = 14, diff = 0]
15 : {3,2} = 5x3 (6 bits) [approx = 15, diff = 0]
16 : {7,0} = 17x1 (5 bits) [approx = 17, diff = -1]
17 : {7,0} = 17x1 (5 bits) [approx = 17, diff = 0]
18 : {8,0} = 19x1 (5 bits) [approx = 19, diff = -1]
19 : {8,0} = 19x1 (5 bits) [approx = 19, diff = 0]
20 : {8,0} = 19x1 (5 bits) [approx = 19, diff = 1]
21 : {4,2} = 7x3 (6 bits) [approx = 21, diff = 0]
22 : {5,1} = 11x2 (6 bits) [approx = 22, diff = 0]
23 : {9,0} = 23x1 (5 bits) [approx = 23, diff = 0]
24 : {9,0} = 23x1 (5 bits) [approx = 23, diff = 1]
25 : {3,3} = 5x5 (6 bits) [approx = 25, diff = 0]
26 : {6,1} = 13x2 (6 bits) [approx = 26, diff = 0]
27 : {6,1} = 13x2 (6 bits) [approx = 26, diff = 1]
28 : {10,0} = 29x1 (6 bits) [approx = 29, diff = -1]
29 : {10,0} = 29x1 (6 bits) [approx = 29, diff = 0]
30 : {11,0} = 31x1 (6 bits) [approx = 31, diff = -1]
31 : {11,0} = 31x1 (6 bits) [approx = 31, diff = 0]
32 : {11,0} = 31x1 (6 bits) [approx = 31, diff = 1]
33 : {5,2} = 11x3 (7 bits) [approx = 33, diff = 0]
34 : {7,1} = 17x2 (6 bits) [approx = 34, diff = 0]
35 : {4,3} = 7x5 (6 bits) [approx = 35, diff = 0]
36 : {12,0} = 37x1 (6 bits) [approx = 37, diff = -1]
37 : {12,0} = 37x1 (6 bits) [approx = 37, diff = 0]
38 : {8,1} = 19x2 (6 bits) [approx = 38, diff = 0]
39 : {6,2} = 13x3 (7 bits) [approx = 39, diff = 0]
40 : {13,0} = 41x1 (6 bits) [approx = 41, diff = -1]
41 : {13,0} = 41x1 (6 bits) [approx = 41, diff = 0]
42 : {14,0} = 43x1 (6 bits) [approx = 43, diff = -1]
43 : {14,0} = 43x1 (6 bits) [approx = 43, diff = 0]
44 : {14,0} = 43x1 (6 bits) [approx = 43, diff = 1]
45 : {9,1} = 23x2 (6 bits) [approx = 46, diff = -1]
46 : {9,1} = 23x2 (6 bits) [approx = 46, diff = 0]
47 : {15,0} = 47x1 (6 bits) [approx = 47, diff = 0]
48 : {15,0} = 47x1 (6 bits) [approx = 47, diff = 1]
49 : {4,4} = 7x7 (6 bits) [approx = 49, diff = 0]
50 : {16,0} = 51x1 (6 bits) [approx = 51, diff = -1]
51 : {16,0} = 51x1 (6 bits) [approx = 51, diff = 0]
52 : {16,0} = 51x1 (6 bits) [approx = 51, diff = 1]
53 : {17,0} = 53x1 (7 bits) [approx = 53, diff = 0]
54 : {17,0} = 53x1 (7 bits) [approx = 53, diff = 1]
55 : {5,3} = 11x5 (7 bits) [approx = 55, diff = 0]
56 : {8,2} = 19x3 (7 bits) [approx = 57, diff = -1]
57 : {8,2} = 19x3 (7 bits) [approx = 57, diff = 0]
58 : {10,1} = 29x2 (7 bits) [approx = 58, diff = 0]
59 : {18,0} = 59x1 (7 bits) [approx = 59, diff = 0]
60 : {19,0} = 61x1 (7 bits) [approx = 61, diff = -1]
61 : {19,0} = 61x1 (7 bits) [approx = 61, diff = 0]
62 : {11,1} = 31x2 (7 bits) [approx = 62, diff = 0]
63 : {11,1} = 31x2 (7 bits) [approx = 62, diff = 1]
64 : {6,3} = 13x5 (7 bits) [approx = 65, diff = -1]
65 : {6,3} = 13x5 (7 bits) [approx = 65, diff = 0]
66 : {20,0} = 67x1 (7 bits) [approx = 67, diff = -1]
67 : {20,0} = 67x1 (7 bits) [approx = 67, diff = 0]
68 : {20,0} = 67x1 (7 bits) [approx = 67, diff = 1]
69 : {9,2} = 23x3 (7 bits) [approx = 69, diff = 0]
70 : {21,0} = 71x1 (7 bits) [approx = 71, diff = -1]
71 : {21,0} = 71x1 (7 bits) [approx = 71, diff = 0]
72 : {22,0} = 73x1 (7 bits) [approx = 73, diff = -1]
73 : {22,0} = 73x1 (7 bits) [approx = 73, diff = 0]
74 : {12,1} = 37x2 (7 bits) [approx = 74, diff = 0]
75 : {12,1} = 37x2 (7 bits) [approx = 74, diff = 1]
76 : {5,4} = 11x7 (7 bits) [approx = 77, diff = -1]
77 : {5,4} = 11x7 (7 bits) [approx = 77, diff = 0]
78 : {23,0} = 79x1 (7 bits) [approx = 79, diff = -1]
79 : {23,0} = 79x1 (7 bits) [approx = 79, diff = 0]
80 : {23,0} = 79x1 (7 bits) [approx = 79, diff = 1]
81 : {13,1} = 41x2 (7 bits) [approx = 82, diff = -1]
82 : {13,1} = 41x2 (7 bits) [approx = 82, diff = 0]
83 : {24,0} = 83x1 (7 bits) [approx = 83, diff = 0]
84 : {24,0} = 83x1 (7 bits) [approx = 83, diff = 1]
85 : {7,3} = 17x5 (7 bits) [approx = 85, diff = 0]
86 : {14,1} = 43x2 (7 bits) [approx = 86, diff = 0]
87 : {10,2} = 29x3 (8 bits) [approx = 87, diff = 0]
88 : {25,0} = 89x1 (7 bits) [approx = 89, diff = -1]
89 : {25,0} = 89x1 (7 bits) [approx = 89, diff = 0]
90 : {25,0} = 89x1 (7 bits) [approx = 89, diff = 1]
91 : {26,0} = 91x1 (8 bits) [approx = 91, diff = 0]
92 : {6,4} = 13x7 (7 bits) [approx = 91, diff = 1]
93 : {11,2} = 31x3 (8 bits) [approx = 93, diff = 0]
94 : {15,1} = 47x2 (7 bits) [approx = 94, diff = 0]
95 : {8,3} = 19x5 (7 bits) [approx = 95, diff = 0]
96 : {8,3} = 19x5 (7 bits) [approx = 95, diff = 1]
97 : {27,0} = 97x1 (8 bits) [approx = 97, diff = 0]
98 : {27,0} = 97x1 (8 bits) [approx = 97, diff = 1]
99 : {28,0} = 101x1 (8 bits) [approx = 101, diff = -2]
100 : {28,0} = 101x1 (8 bits) [approx = 101, diff = -1]
101 : {28,0} = 101x1 (8 bits) [approx = 101, diff = 0]
102 : {16,1} = 51x2 (7 bits) [approx = 102, diff = 0]
103 : {29,0} = 103x1 (8 bits) [approx = 103, diff = 0]
104 : {29,0} = 103x1 (8 bits) [approx = 103, diff = 1]
105 : {17,1} = 53x2 (8 bits) [approx = 106, diff = -1]
106 : {17,1} = 53x2 (8 bits) [approx = 106, diff = 0]
107 : {30,0} = 107x1 (8 bits) [approx = 107, diff = 0]
108 : {31,0} = 109x1 (8 bits) [approx = 109, diff = -1]
109 : {31,0} = 109x1 (8 bits) [approx = 109, diff = 0]
110 : {32,0} = 111x1 (8 bits) [approx = 111, diff = -1]
111 : {32,0} = 111x1 (8 bits) [approx = 111, diff = 0]
112 : {33,0} = 113x1 (8 bits) [approx = 113, diff = -1]
113 : {33,0} = 113x1 (8 bits) [approx = 113, diff = 0]
114 : {9,3} = 23x5 (7 bits) [approx = 115, diff = -1]
115 : {9,3} = 23x5 (7 bits) [approx = 115, diff = 0]
116 : {9,3} = 23x5 (7 bits) [approx = 115, diff = 1]
117 : {34,0} = 117x1 (8 bits) [approx = 117, diff = 0]
118 : {18,1} = 59x2 (8 bits) [approx = 118, diff = 0]
119 : {35,0} = 119x1 (8 bits) [approx = 119, diff = 0]
120 : {7,4} = 17x7 (7 bits) [approx = 119, diff = 1]
121 : {5,5} = 11x11 (8 bits) [approx = 121, diff = 0]
122 : {19,1} = 61x2 (8 bits) [approx = 122, diff = 0]
123 : {36,0} = 123x1 (8 bits) [approx = 123, diff = 0]
124 : {36,0} = 123x1 (8 bits) [approx = 123, diff = 1]
125 : {36,0} = 123x1 (8 bits) [approx = 123, diff = 2]
126 : {37,0} = 127x1 (9 bits) [approx = 127, diff = -1]
127 : {37,0} = 127x1 (9 bits) [approx = 127, diff = 0]
128 : {14,2} = 43x3 (8 bits) [approx = 129, diff = -1]
129 : {38,0} = 129x1 (9 bits) [approx = 129, diff = 0]
130 : {14,2} = 43x3 (8 bits) [approx = 129, diff = 1]
131 : {39,0} = 131x1 (9 bits) [approx = 131, diff = 0]
132 : {8,4} = 19x7 (7 bits) [approx = 133, diff = -1]
133 : {40,0} = 133x1 (9 bits) [approx = 133, diff = 0]
134 : {20,1} = 67x2 (8 bits) [approx = 134, diff = 0]
135 : {20,1} = 67x2 (8 bits) [approx = 134, diff = 1]
136 : {41,0} = 137x1 (9 bits) [approx = 137, diff = -1]
137 : {41,0} = 137x1 (9 bits) [approx = 137, diff = 0]
138 : {42,0} = 139x1 (9 bits) [approx = 139, diff = -1]
139 : {42,0} = 139x1 (9 bits) [approx = 139, diff = 0]
140 : {15,2} = 47x3 (8 bits) [approx = 141, diff = -1]
141 : {15,2} = 47x3 (8 bits) [approx = 141, diff = 0]
142 : {21,1} = 71x2 (8 bits) [approx = 142, diff = 0]
143 : {6,5} = 13x11 (8 bits) [approx = 143, diff = 0]
144 : {10,3} = 29x5 (8 bits) [approx = 145, diff = -1]
145 : {10,3} = 29x5 (8 bits) [approx = 145, diff = 0]
146 : {22,1} = 73x2 (8 bits) [approx = 146, diff = 0]
147 : {22,1} = 73x2 (8 bits) [approx = 146, diff = 1]
148 : {44,0} = 149x1 (9 bits) [approx = 149, diff = -1]
149 : {44,0} = 149x1 (9 bits) [approx = 149, diff = 0]
150 : {45,0} = 151x1 (9 bits) [approx = 151, diff = -1]
151 : {45,0} = 151x1 (9 bits) [approx = 151, diff = 0]
152 : {16,2} = 51x3 (8 bits) [approx = 153, diff = -1]
153 : {16,2} = 51x3 (8 bits) [approx = 153, diff = 0]
154 : {16,2} = 51x3 (8 bits) [approx = 153, diff = 1]
155 : {11,3} = 31x5 (8 bits) [approx = 155, diff = 0]
156 : {11,3} = 31x5 (8 bits) [approx = 155, diff = 1]
157 : {46,0} = 157x1 (9 bits) [approx = 157, diff = 0]
158 : {23,1} = 79x2 (8 bits) [approx = 158, diff = 0]
159 : {17,2} = 53x3 (9 bits) [approx = 159, diff = 0]
160 : {9,4} = 23x7 (7 bits) [approx = 161, diff = -1]
161 : {47,0} = 161x1 (9 bits) [approx = 161, diff = 0]
162 : {9,4} = 23x7 (7 bits) [approx = 161, diff = 1]
163 : {48,0} = 163x1 (9 bits) [approx = 163, diff = 0]
164 : {48,0} = 163x1 (9 bits) [approx = 163, diff = 1]
165 : {24,1} = 83x2 (8 bits) [approx = 166, diff = -1]
166 : {24,1} = 83x2 (8 bits) [approx = 166, diff = 0]
167 : {49,0} = 167x1 (9 bits) [approx = 167, diff = 0]
168 : {6,6} = 13x13 (8 bits) [approx = 169, diff = -1]
169 : {50,0} = 169x1 (10 bits) [approx = 169, diff = 0]
170 : {6,6} = 13x13 (8 bits) [approx = 169, diff = 1]
171 : {6,6} = 13x13 (8 bits) [approx = 169, diff = 2]
172 : {51,0} = 173x1 (10 bits) [approx = 173, diff = -1]
173 : {51,0} = 173x1 (10 bits) [approx = 173, diff = 0]
174 : {51,0} = 173x1 (10 bits) [approx = 173, diff = 1]
175 : {18,2} = 59x3 (9 bits) [approx = 177, diff = -2]
176 : {18,2} = 59x3 (9 bits) [approx = 177, diff = -1]
177 : {18,2} = 59x3 (9 bits) [approx = 177, diff = 0]
178 : {25,1} = 89x2 (8 bits) [approx = 178, diff = 0]
179 : {52,0} = 179x1 (10 bits) [approx = 179, diff = 0]
180 : {53,0} = 181x1 (10 bits) [approx = 181, diff = -1]
181 : {53,0} = 181x1 (10 bits) [approx = 181, diff = 0]
182 : {26,1} = 91x2 (9 bits) [approx = 182, diff = 0]
183 : {19,2} = 61x3 (9 bits) [approx = 183, diff = 0]
184 : {12,3} = 37x5 (8 bits) [approx = 185, diff = -1]
185 : {12,3} = 37x5 (8 bits) [approx = 185, diff = 0]
186 : {12,3} = 37x5 (8 bits) [approx = 185, diff = 1]
187 : {54,0} = 187x1 (10 bits) [approx = 187, diff = 0]
188 : {7,5} = 17x11 (8 bits) [approx = 187, diff = 1]
189 : {7,5} = 17x11 (8 bits) [approx = 187, diff = 2]
190 : {55,0} = 191x1 (10 bits) [approx = 191, diff = -1]
191 : {55,0} = 191x1 (10 bits) [approx = 191, diff = 0]
192 : {56,0} = 193x1 (10 bits) [approx = 193, diff = -1]
193 : {56,0} = 193x1 (10 bits) [approx = 193, diff = 0]
194 : {27,1} = 97x2 (9 bits) [approx = 194, diff = 0]
195 : {27,1} = 97x2 (9 bits) [approx = 194, diff = 1]
196 : {57,0} = 197x1 (10 bits) [approx = 197, diff = -1]
197 : {57,0} = 197x1 (10 bits) [approx = 197, diff = 0]
198 : {58,0} = 199x1 (10 bits) [approx = 199, diff = -1]
199 : {58,0} = 199x1 (10 bits) [approx = 199, diff = 0]
200 : {20,2} = 67x3 (9 bits) [approx = 201, diff = -1]
201 : {59,0} = 201x1 (10 bits) [approx = 201, diff = 0]
202 : {28,1} = 101x2 (9 bits) [approx = 202, diff = 0]
203 : {60,0} = 203x1 (10 bits) [approx = 203, diff = 0]
204 : {13,3} = 41x5 (8 bits) [approx = 205, diff = -1]
205 : {13,3} = 41x5 (8 bits) [approx = 205, diff = 0]
206 : {29,1} = 103x2 (9 bits) [approx = 206, diff = 0]
207 : {29,1} = 103x2 (9 bits) [approx = 206, diff = 1]
208 : {8,5} = 19x11 (8 bits) [approx = 209, diff = -1]
209 : {61,0} = 209x1 (10 bits) [approx = 209, diff = 0]
210 : {8,5} = 19x11 (8 bits) [approx = 209, diff = 1]
211 : {62,0} = 211x1 (10 bits) [approx = 211, diff = 0]
212 : {21,2} = 71x3 (9 bits) [approx = 213, diff = -1]
213 : {21,2} = 71x3 (9 bits) [approx = 213, diff = 0]
214 : {30,1} = 107x2 (9 bits) [approx = 214, diff = 0]
215 : {14,3} = 43x5 (8 bits) [approx = 215, diff = 0]
216 : {14,3} = 43x5 (8 bits) [approx = 215, diff = 1]
217 : {63,0} = 217x1 (10 bits) [approx = 217, diff = 0]
218 : {31,1} = 109x2 (9 bits) [approx = 218, diff = 0]
219 : {22,2} = 73x3 (9 bits) [approx = 219, diff = 0]
220 : {7,6} = 17x13 (8 bits) [approx = 221, diff = -1]
221 : {64,0} = 221x1 (10 bits) [approx = 221, diff = 0]
222 : {32,1} = 111x2 (9 bits) [approx = 222, diff = 0]
223 : {65,0} = 223x1 (11 bits) [approx = 223, diff = 0]
224 : {65,0} = 223x1 (11 bits) [approx = 223, diff = 1]
225 : {33,1} = 113x2 (9 bits) [approx = 226, diff = -1]
226 : {33,1} = 113x2 (9 bits) [approx = 226, diff = 0]
227 : {33,1} = 113x2 (9 bits) [approx = 226, diff = 1]
228 : {66,0} = 229x1 (11 bits) [approx = 229, diff = -1]
229 : {66,0} = 229x1 (11 bits) [approx = 229, diff = 0]
230 : {66,0} = 229x1 (11 bits) [approx = 229, diff = 1]
231 : {67,0} = 233x1 (11 bits) [approx = 233, diff = -2]
232 : {67,0} = 233x1 (11 bits) [approx = 233, diff = -1]
233 : {67,0} = 233x1 (11 bits) [approx = 233, diff = 0]
234 : {34,1} = 117x2 (9 bits) [approx = 234, diff = 0]
235 : {15,3} = 47x5 (8 bits) [approx = 235, diff = 0]
236 : {15,3} = 47x5 (8 bits) [approx = 235, diff = 1]
237 : {68,0} = 237x1 (11 bits) [approx = 237, diff = 0]
238 : {35,1} = 119x2 (9 bits) [approx = 238, diff = 0]
239 : {69,0} = 239x1 (11 bits) [approx = 239, diff = 0]
240 : {70,0} = 241x1 (11 bits) [approx = 241, diff = -1]
241 : {70,0} = 241x1 (11 bits) [approx = 241, diff = 0]
242 : {70,0} = 241x1 (11 bits) [approx = 241, diff = 1]
243 : {70,0} = 241x1 (11 bits) [approx = 241, diff = 2]
244 : {36,1} = 123x2 (9 bits) [approx = 246, diff = -2]
245 : {36,1} = 123x2 (9 bits) [approx = 246, diff = -1]
246 : {36,1} = 123x2 (9 bits) [approx = 246, diff = 0]
247 : {71,0} = 247x1 (11 bits) [approx = 247, diff = 0]
248 : {8,6} = 19x13 (8 bits) [approx = 247, diff = 1]
249 : {24,2} = 83x3 (9 bits) [approx = 249, diff = 0]
250 : {24,2} = 83x3 (9 bits) [approx = 249, diff = 1]
251 : {72,0} = 251x1 (11 bits) [approx = 251, diff = 0]
252 : {9,5} = 23x11 (8 bits) [approx = 253, diff = -1]
253 : {73,0} = 253x1 (11 bits) [approx = 253, diff = 0]
254 : {37,1} = 127x2 (10 bits) [approx = 254, diff = 0]
255 : {16,3} = 51x5 (8 bits) [approx = 255, diff = 0]

Différence négative maximum : -2
Différence positive maximum : 2
Somme des 256 différences : 14
Variance : 0.52
Taille minimum (en bits) : 2
Taille maximum (en bits) : 11

=> ça compresse mes données de tests de 1 à 4x
(mais c'est un format avec [une très légère] perte => ça ne marche donc pas avec du texte [ça le corrompt un tout petit peu], ni surtout avec des executables => par contre ça à l'air hyper efficace pour compresser des tableaux d'octets, mots ou double-mots représentant des valeurs numériques)
[et avec l'ajout d'une table de quantisation faisant de sorte que ce soit le plus souvent possible les plus petits codes qui soient utilisés + la gestion des 0, je pense arriver à une compression de l'ordre de 10x]

=> je pourrais alors bientôt remplacer la compression finale de mes coefficients d'ondelettes via zlib par autre chose d'aussi efficace en terme de compression mais surtout au moins 10x plus rapide :)


@+
Yannoo

Je viens de comparer la "compression par nombres premiers" au codage de Golomb :

Sur une image entièrement noire : Golomb = 12.5% NbPremiers = 25%

Sur une image entièrement blanche : Golomb = 12.5% NbPremiers = 100%

Sur une image noire avec quelques aplats de couleurs : Golomb = 25% NbPremiers = 50%

Sur des images de paysages : Golomb = 145% NbPremiers = 90%

Sur des plans/factures : Golomb = 80% NbPremiers = 110%


La compression par nombres premiers n'a donc l'air d'être plus efficace que le codage de Golomb que lorsqu'il y a beaucoup d'intensités différentes à traiter, comme la plupart des photos par exemple

Mais même sur ce type d'images, elle ne permet qu'un gain assez faible de seulement 10% de la taille du fichier économisé :(
(mais même si la compression par nombres premiers n'y est pas très efficace, elle y est néanmoins quasiment 2x plus efficace que le codage de Golomb qui lui fait enfler la taille des données de presque 50% ...)

=> la compression par nombres premiers est donc à première vue rentable sur la plupart des images/photos
(alors que le codage de Golomb fait systématiquement enfler la taille de 40 à 50%)

=> ça m'encourage donc assez pour remplacer la compression zlib de mon utilitaire par un codage de Golomb pour commencer (car c'est le plus facile à faire) puis une compression par nombres premiers par la suite, histoire de multiplier par 10 la vitesse de traitement de mon utilitaire de compresssion d'images :)
[et si en plus, ça me donne un taux de compression encore meilleur que celui de zlib, ce serait le top ...]


@+
Yannoo