Discussion :

[brekiano]

bonjour,
je cherche une api pour la compression des vidéos en utilisant les ondelettes.

[slim_java]

tu peux appliquer une compression sur les images, donc a savoir un algorithme comme LZW

[yannoo95170]

J'ai un embryon d' API qui permet de faire de la compression par ondelette (+zizag+rle+zlib) sous Linux (mais ça doit assez facilement être portable sous MacOs ou Windobe, c'est surtout au niveau des librairies à linker que ça devrait être le plus galère à gérer ...)

Pour l'instant, il n'y a qu'une partie de l'algo de compression par ondelette qui est implémentée (les transformées de Haar ne se font que sur des blocs indépendants de 8 lignes x 8 colonnes, cf. il n'y a pas encore la récursivité permettant de "mipmapper les blocs entre eux", seul le mimappage intra-bloc est pour l'instant géré).

Quelque part, ç'est aussi un avantage car ça me permet de rester sur des composantes de type "char" (cf. 8 bits signés) et donc de ne pas être obligé de passer par des floats 64 bits ou entiers à virgules fixes 16/32 bits => la transformée d'un bloc 8x8 prend exactement la même taille que celle du bloc 8x8 d'origine, soit 64 octets
(en passant c'est une très bonne chose car ça permet aussi d'entrevoir une "compression sur place" via le passage par un petit buffer de 64 octets par bloc, et donc d'en imaginer une future implémentation en hardware qui serait bien plus rapide et/ou économe en énergie/calculs que les trucs à base de recherche de vecteurs de déplacements et autres calculs hyper gourmands des solutions MPEG/Divx/H26x actuelles ...)

1) La transformée de Haar est effectuée sur chacun des blocs 8x8 de l'image width*height

2) ces coefficients sont alors stockés selon un schéma en zizgag qui est paramêtrable via une table APIsée (ce qui permet aussi de gérer l'entrelacement/désentrelacement, la "(de)bayerisation" et autres joyeusetés du style dans la foulée...)

3) Une mise à zéro des coefficients dont la valeur absolue est inférieure à un seuil paramêtrable y est alors effectuée

4) une sorte de RLE qui code "0 suivi du nombre de 0 suivants" ou "directement une valeur différente de 0" compresse les coefficients (les fameuses ondelettes) qui viennent d'être seuillée à l'étape précédente
(vraiment très efficace pour coder des suites continues de 0 => jusqu'à 127 zéros d'affilée qui sont compactés en 2 octets par cette "RLE de 0", et bientôt 255 quand j'aurais rêglé les effets de bord dû au transtypage "signed char"/"unsigned char" qui est alors nécessaire)

5) une compression par zlib me permet encore de diviser par 2 la taille finale des données

=> avec tout ça, j'obtiens une compression de 200% à 400% (voir jusqu'à 10x plus avec des images style BD avec de grands applats en noir et blanc) .

La transformée de Haar transforme simplement un espace 2D en un autre et ne compresse pas en elle-même les données (au contraire elle aurait plutôt tendance à obliger à utiliser des nombres à virgules fixes ou flottants en 32/64 bits à la place de simples octets) mais elle les prépare **vraiment très bien** pour les compressions qui suivent par contre ...

Ca ne gère pour l'instant que 256 niveaux de gris (la couleur arrivera bientôt via un codage YCbCr 4:2:0 planar, cf. l'image en gris suivie de 2 images 4x plus petites qui contiennent les données de couleurs)

La transformée 2D de Haar n'est pour l'instant pas complêtement implémentée, le côté récursif de la division par 2 de l'image n'a pas encore été faite et ça fait donc comme des "gros points d'intensités différentes en haut à gauche de chaque bloc 8x8", soit des points alignés tous les 8 pixels sur les lignes et les colonnes.
(de l'autre côté, ça me permet de rester sur des "signed char" plutôt que d'avoir à travailler sur des "float" 8 fois plus gros ...)
=> c'est d'ailleurs étonnant de visualiser à l'écran qu'autant d'infos soit stockée dans si peu de points/octets visibles, heureusement que la transformation inverse renvoie sur l'écran une image qui est à très peu de chose prêt la même que l'originale (j'ai toujours du mal à me dire que si, c'est bel et bien possible, et que j'en ai de plus la preuve par l'image sous les yeux ...)


=> avec une transformée de Haar complête (cf. récursive) je ne serais pas étonné du tout que les compressions qui suivent soient encore bien plus efficaces ...

De l'autre côté, cette implémentation non complête de la transformée 2D de Haar me permet aussi d'aller "log2 la taille de l'image" plus vite et prépare/simplifie grandement ma prochaine implémentation de cette transformée via des instructions MMX, qui adorent justement traiter des données 8 bits signés par blocs de 8 ...

Mais je pense que celà limite énormément le ratio des compressions qui suivent
(car les points sont espacés, il vaudrait mieux qu'il soient regroupés pour faire de grandes zones gris/blanc et de **TRES GRANDES ZONES** remplies de 0)

Je pense implémenter assez vite le côté récursif de la division par 2 (cf. celle inter-bloc, la compression intra-bloc étant déjà faite comme expliquée quelques lignes plus haut) et même y rajouter une petite couche de transmission progressive pour le streaming (une image de piètre qualité est dispo dès les premiers octets et elle s'affine au fur et à mesure que le flot d'octets arrive)
=> ça sera surement très utile pour l'extension vidéo (cf. plusieurs images successives à 50 img/s) que je veux aussi y apporter

En gros, ça ressemble pas mal à du JPEG 2000 quoi ...

Mais c'est encore très loin de compresser aussi bien et d'être aussi exhaussif pour les formats d'images et le codage des couleurs/palettes que les ténors M(J)PEG(1,2,3,4), H26x et autres VP par contre ...

Mais vu que c'est codé "100% by moi-même", je trouve ça plutôt pas mal pour ma première implémentation **fonctionnelle** en compression d'images
(et en plus, ça me laisse entrevoir une implémentation hyper speed du bouzin via des shaders sous OpenGL ... et là ça va sûrement dépoter avec une bonne carte graphique

Et en étendant l'idée de la transformée de Haar 2D en une transformée 3D (cf. une video 2D étant un suite d'images 2D les unes après les autres, on peut donc voir ça comme une image 3D où chaque plan est une image 2D très peu differente de celle du plan précédent et/ou suivant) => j'imagine déjà assez facilement le taux de compression faramineux que l'on peut alors obtenir avec cette extension 3D en ne stockant que les différences entre images et en les (ré)entrelaçant/ZIGZAGant/HARRant/SEUILant/RLEant/ZLIBan
(et en plus les temps de compression/décompressions semblent assez symétrique => eeePC, Pocket PC et autres iPhones vont-ils bientôt eux-aussi pouvoir faire de la compression vidéo en temps-réel ?)


Je veux bien mettre cet embryon d'API à dispo si ça intéresse quelqu'un
(enfin bon, c'est plus pour l'instant un ensemble de fonctions imbriquées les unes dans les autres qu'autre chose et c'est limité aux .TIF, mais je pense rapidement en faire une vrai API avec un .lib généré à partir des .o et un #include qui regroupe les autres .h, puis débugger tout ça, y'en a vraiment besoin, et y ajouter tout plein de choses en plus ... comme le support du MMX/SSE et des shaders OpenGL par exemple)


@+
Yannoo (yann.lepetitcorps@free.fr)

[yannoo95170]

Pour créer les executables, je lance cette commande sous Linux

make all

(y'a des tas d'injures de la part de gcc mais ça crée bien des executables sur mes postes Linux)

Ca crée ces 3 executables :

first
second
third
wavelet

Pour tester l'algo, il faut décompresser les 2 premières archives jointes qui contiennent une matrice 8x8 d'exemple pour first (mat8x8.txt) et un image .tif pour les autres (test.tif)

tar -xf mat8x8.txt.tar.gz
tar -xf test.tif.tar.gz

On peut ensuite utiliser ces 2 fichiers exemples avec les executables crées :

./first mat8x8.txt (simplement un test de la compression par ondelette sur une matrice 8x8 stockée dans le fichier mat8x8.txt)

./second test.tif (ca crée une images harred.tif , qui est la transformée par ondelette de l'image test.tif , mais que le premier niveau, il faut mettre 1 au valeurs demandée pour du texte mais avec de vraies images/photos on peut mettre des valeurs plus grandes, plus les valeurs sont petites meilleure est la qualité mais moins bonne est la compression, 1 est la valeur minimale)

./second test.tif (pareil, mais c'est mon troisième executable "fonctionnel" donc je l'ai appellé third)

./wavelet test.tif (comme les deux précédents, mais j'ai éclaté le source en plusieurs fichiers .h et .c pour pouvoir modifier chaque bloc de l'algo indépendamment des autres)

Les fichiers TIF ont les mêmes tailles car je convertit toujours l'image pour qu'elle soit facilement lisibles depuis pas mal de visualisateurs d'images ... je pense coder le visualisateur très vite afin de m'affranchir du format .tif et que la compression de la taille des données soit donc réellement visibles sur la taille du fichier de sortie ...)

Il y a les fichiers src.tif, src_grey.tif haared.tif seuilled.tif unharred.tif qui sont [re]générés lors de l'execution de second, third et wavelet (qui font voir le résultat après chaque étape).

Le fichier unharred.tif est le fichier résultat d'une compression par ondelette puis de sa décompression (à comparer avec src_grey.tif pour voir la perte d'image crée par la compression/décompression par ondelette)

Il n'y a qu'un itération de la compression par ondelette pour l'instant, la partie récursive arrivera très bientôt.

En fait, dès que la version de harr.c en MMX sera fonctionnelle car pour l'instant il n'y a encore rien d'optimisé dans ces codes sources et ce n'est donc pas vraiment très rapide.
(quoique c'est loin d'être aussi lent que je ne l'aurait craint en fait)

=> ce sera pour dans quelques jours avec des tests de performances + une amélioration/APIsation de la partie décimage (quantification) dont je n'ai pas encore trop parlé et qui passera là aussi par des tables de conversion couleurs/gris/N&B (pour être le plus générique/exhaussif possible et permettre de plus un maximum de personnalisation/optimisation de l'étape de quantification pour avoir une meilleure qualité en sortie).


@+
Yannoo

[yannoo95170]

La couleur arrivera très bientôt (en attendant, ça ne fait le qu'après conversion de l'image couleur en niveau de gris)

Je pense aussi profiter de cette nouvelle table de conversion en entrée pour faire de la conversion de format RGB[A] <-> YCbCr / YCoCg et autres YIC, HSV ou HSL (voir même Pantone si j'arrive à trouver les specs)

A noter que des fonctions de conversions de formats 4:2:2 <-> 4:2:1 <-> 4:2:0 seront aussi très bientôt ajoutées dans le fichier zigzag.c (je pense déplacer les tables, et en mettre de nouvelles pour ces conversions de format, du fichier zigzag.c vers le fichier d'entête zizgzag.h pour qu'elles soient aussi directement accessibles aux autres modules)


@+
Yannoo

[yannoo95170]

Il y a aussi ça que je viens de trouver :

http://www.maven.de/code/wavelet
http://nalag.cs.kuleuven.be/research/software/wavelets

Je ne les connaissais pas encore hier soir, mais je pense les connaître pas mal vite fait


@+
Yannoo

[yannoo95170]

A première vue, il faudrait aussi y implémenter de l "Embedded Zerotree Wavelet" pour que ça se compresse encore mieux.
(ZLIB/LZW c'est finalement vraiment bien trop lent pour du temps réel)

J'ai trouvé un lien sur l' EZW qui semble pas mal à http://polyvalens.pagesperso-orange.....html#section3

=> quelqu'un qui aurait déjà touché à ça (l'EZW) pourrait-il m'aider ?
(ça à l'air de ne traiter l'image que par des blocs indépendants de 8x8 donc ça semble être tout particulièrement adapté par la compression par bloc que je fais pour l'instant ... mais je préssent que ça va de suite devenir plus compliqué quand je vais vouloir y implémenter un traitement "par mipmap" et non plus par blocs indépendants de 8x8 ...)