Compression RLE - Page 2

(super simple a faire de la compression BaB comme ça)

sinon -FAT32+IBM-BIOS

Et puis ce serait très lent (plus de 8 fois plus lent)

Tout ça pour en revenir à ce avec quoi j'avais ouvert ce topic, i.-e. le système "flag|nombre_de_fois|byte_répété"... J'aurai au moins compris pourquoi c'est ainsi
Et ça envisage de devenir ingénieur informaticien...

Ethaniel>Je comprend tes arguments en faveur de la répétition des octets plutôt que celle des bits, mais ils ne sont valables que dans le cadre que tu avais toi même instauré, c'est-à-dire celui où l'on mélange les deux plans en mettant les deux bits désignant le même pixel cote-à-cote.

Mais qu'en est-il de ma solution propre, où je sépare les deux plans et conserve ainsi de plus grands aplats unis? Qu'est-ce qui m'empêche de garder mes deux plans séparés, mais dans un unique fichier (l'un après l'autre par exemple)? La place en mémoire est exactement la même que celle occupée par la technique des "bits entrelacés", sauf que du coup on n'a plus de grandes plages de "01010101" correspondant aux zones de gris et qu'on peut alors travailler octet par octet et non bits par bits.
Ma solution reprend alors tout son sens!

Je n'ai jamais envisagé de travailler bits à bits (j'en suis bien incapable, je ne connais pas assez la manipulation de bits), et ma technique se base au contraire sur les octets.
Les seules références aux bits que j'ai fait étaient lorsque je parlait de pixels (mais dans mon cas il s'agit simplement de les compter, ce qui n'est pas sorcier, même sans les prendre en tant que bits) et quand je parlais de l'entrelacement, ou que je voulais illustrer ce qui se passait en mémoire.

Y a t-il donc autre chose qui rend ma technique inutilisable en pratique? Ou ais-je mal compris certaines choses? Merci de m'éclairer.

./35 > Exemple concret : essaie de compresser « 00000000 00000111 11111111 ».
Pour que le codec détermine qu'il y a 13 « 0 » puis 11 « 1 », je te souhaite bien du courage.
Certes, la compression est excellente, mais la complexité du codec et le temps de compression/décompression sont loin d'être optimaux.
Bon, certes, pour ce qui est du temps d'exécution, les images sont limitées à la taille de l'écran de TI, donc ça ne dépassera jamais quelques dizaines de millisecondes, mais quand même, sur le principe, c'est pas top, et il faut d'abord écrire le codec (ce qui, en soit, n'est pas non plus insurmontable, à condition d'avoir une expérience de la manipulation de bits)...

Sachant que, dans mon cas, pour mettre au point une image utilisant mon format je pensais créer moi-même un logiciel de création d'images, cela résout le problème de 'comptage' des pixels.
En effet voir l'image comme des octets qu'il faut d'abord convertir en binaire puis compter dans ces chaines binaires les suites de '0' et de '1', la compression parait très compliquée ^_^.
Mais l'image d'origine à compresser ne sera pas, pour ma part, à l'origine une suite d'octets, mais bel et bien une suite de pixels affichés à l'écran (une image dessinée par l'utilisateur).

A partir de là, si la liste des pixels allumés est stockée dans un tableau de même dimension que l'écran (on peut d'ailleurs aller lire directement dans l'écran, je pense), le comptage n'est plus une épreuve à surmonter.
On peut même éventuellement faire des PixelTests (je ne me souviens plus de l'équivalent de cette fonction en C, mais je l'ai déjà utilisée dans un de mes programmes de Jeu de la Vie) sur tout l'écran. Même si son exécution est lente, ce ne sera pas dans des mesures dramatiques, et de toute façon la compression d'une image ne se fait qu'une fois, éventuellement lentement, alors que sa lecture, elle, se fera assez rapidement. Mais je préfère quand même la technique du tableau, qui de plus permet de créer une image de plus grande dimension que l'écran ^^.

Je pense donc que c'est tout à fait faisable, même avec des connaissances en C plutôt approximatives.

Je vais essayer de m'y mettre dès que j'aurais un peu plus de temps. Merci de vos remarques!

si tu veux lire directement à l'écran, tu te retrouve avec le problème de manipulation de bits car il y a 8 pixels d'enregistrés par bytes.

Daniel Vouaux (./37) :
[...] la compression d'une image ne se fait qu'une fois, éventuellement lentement, alors que sa lecture, elle, se fera assez rapidement. [...]

Zut, je n'ai donné que la moitié de la réponse avec :

Ethaniel (./36) :
./35 > Exemple concret : essaie de compresser « 00000000 00000111 11111111 ».Pour que le codec détermine qu'il y a 13 « 0 » puis 11 « 1 », je te souhaite bien du courage.

J'aurais dû ajouter :

De même, pour décompresser « 13|0|11|1 » en « 00000000 00000111 11111111 », même combat, même complexité du code.

Si tu fais un tableau d'octets, chacun ne contenant que 0 ou 1 selon le pixel, déjà, tu multiplies par 8 la taille du fichier intermédiaire, et tu es de toute façon obligé de lire et d'écrire bit à bit lors des transformation image TI <=> tableau de pixels, tu y gagnes juste un peu sur la complexité du codec puisque tu découpes les opérations de compression et décompression en 2 étapes un peu plus simples (c'est pour ça que je parle de fichier intermédiaire pour ton tableau), mais rendant le tout encore plus long.

Selon moi (AMHA, toussah), entrelacer les plans et faire du RLE octet par octet est le meilleur compromis entre le taux de compression, le temps d'exécution et la complexité du codec (et par là même son temps de développement).
Par contre, si tu avais fait de l'assembleur (ce qui selon toute vraisemblance n'est pas le cas, puisque l'Asm fait beaucoup faire de manipulation bit à bit), là je t'aurais incité à travailler en plans séparés et bit à bit (sans passer par le tableau d'octets intermédiaire, quelle horreur ) afin d'avoir un taux de compression très très bon ( et quand on code en Asm, le codec correspondant n'est pas si compliqué que ça, la manipulation des bits y est naturelle (voire élégante, à mes yeux d'assembliste )).

C'est exactement ce que je pense Ethaniel et d'ici 2042 ça me plairait bien de faire un chtit algo comme ça, le truc qui me fait chier en fait, c'est la gestion de fichier qui va autour, je ne supporte pas ça... Faire choisir le fichier, et en enregistrer un nouveau...

Tout d'abord, pour la taille de fichier intermédiaire, je suis d'accord ça multiplie la taille par 8. C'est un vrai problème, car je ne sais pas combien de mémoire vive possède la calculatrice (je ne sais même pas si on parle de mémoire vive sur une calculatrice ).
Cependant hormis ça la présence d'un tableau intermédiaire est loin d'être une "étape inutile", puisqu'elle permet d'éviter le passage octet=>bits ou vice versa.
En effet comme je l'ai dit précedement dans mon cas je pensais faire en parallèle un programme de création d'images. A partir de ce moment là il suffit, dès qu'on dessine un pixel sur l'écran, d'écrire un '1' dans la zone du tableau correspondant... Plus de manipulation bits à bits, et une compression accélérée!

Et puis, une fois la compression effectuée, le "tableau intermédiaire" serait effacé donc la place exhorbitante prise en mémoire serait elle aussi rendue.

A vrai dire j'ai déjà réalisé ce dont je vous parle (l'histoire du tableau virtuel), mais à une échelle miniature, dans un programme de création de sprites. Malheureusement je ne me suis pas penché pour lui sur l'histoire de la compression RLE adaptée, sachant que sur une image 32x32, et surtout sur un sprite où les détails sont légions, elle ne serait pas forcément "rentable". Je vous posterais quand même ce programme dès qu'il sera fini!

Comme l'a fait remarquer Martial Demolins, il est aussi possible de passer par la manipulation de bits (et encore, un bien grand mot pour une petite chose, s'il suffit de convertir des octets en binaire) mais je préfèrerai m'y pencher sérieusement que si ma solution initiale, gourmande en octets intermédiaires, est vraiment irréalisable au niveau des capacités de la machine.

Pou ce qui est du code et des idées crades, je suis désolé mais je viens de la programmation basic sur TIz80, que j'ai appris en autodidacte, et je me suis donc habitué à passer par des solutions "pas très conventionnelles" pour arriver à mes fins.
M'enfin après tout si ça marche sans inconvénients majeurs, je vois pas le mal ^_^.

Pour ce qui est de la programmation ASM, j'y ait pensé mais je me suis dit que je préfèrerai améliorer mon niveau en C plutôt que de me jeter dans un autre langage.

Martial Demolins (./44) :
T'es au courant qu'avec ta solution, une fois que tu auras enregistré 5-6 images sur la calc, la mémoire sera pleine?

Je ne comprend pas pourquoi tu dis ça... As-tu compris ce que je voulais faire?
Je ne compte pas enregistrer en mémoire les tableaux représentant l'écran (qui en effet seront très lourds) mais uniquement m'en servir comme des fichiers temporaires.

Je pense, au contraire, que ma technique permettraient une économie de place conséquente au niveau du stockage d'images, si l'on met entre parenthèses le fameux tableau qui est, je l'admet très lourd à stocker (mais après tout on s'en fiche puisqu'il n'existe que durant la création de l'image et est effacé ensuite!) .

Je te comprends toujours pas =_= .

Dit moi clairement ce qui selon toi pèserais aussi lourd et boufferais toute la place s'il te plait.

Oui, on est d'accord sur ce point.
Mais comme je l'ai précisé, ce n'est pas ça que je vais enregistrer. Ma technique de compression est toute autre. D'ailleurs si on utilisait ce système là pour compresser ce serait tout le contraire d'une compression.

Dans mon idée, le tableau en question ne serait qu'un fichier temporaire, qui ne durerait que le temps de la création et de la compression de l'image. Autrement dit, il ne prendrait pas de place sur la calculette (ou du moins que dans la mémoire "vive").

Le fichier généré par ma compression serait lui bien plus petit.

Selon wikipédia: "Les caractéristiques de cette mémoire sont : sa volatilité (cette volatilité implique que les données sont perdues dès que l'ordinateur cesse d'être alimenté en électricité)."

Oui, et dans un programme, quand on aloue de la mémoire et qu'on la libère à la fin, cela ne reste pas sur la calculatrice, si?

Mon tableau, qui n'est stocké que temporairement, ne prendrait donc pas de place à long terme sur la calculatrice.

Ok, donc le problème n'est pas dans ce cas la place prise par les images une fois compressées, mais bien la place prise pendant l'exécution.

Le plus simple serait donc que mes données soient elles mêmes stockées sous la forme de 8 pixels par octet (forme "naturelle" mais un peu plus chiante à mettre en place, pour une grosse économie de mémoire).

Je pense alors créer un tableau (j'aime bien les tableaux ^^) contenant ces informations.

Je vais essayer de m'y mettre, voir ce que ça donne.

Avec la méthode d'Ethaniel, tu as aussi la possibilité de coder par duplets de bits si tu tiens à garder une granularité au pixel.
Néanmoins la méthode d'Ethaniel présente l'avantage de permettre une meilleure compression des images utilisant du dithering.

Spectras> Peux-tu préciser ta première phrase s'il-te-plait? Quel est l'intérêt de voir chaque pixel comme un élément unique?

Je ne suis pas persuadé que mettre les bits cote à cote permette une meilleure compression lors du passage en niveau de gris. De toute façon je met au point petit à petit mon logiciel de compression: on verra bien le résultat!

Ca dépend de la nature des images que tu codes, mais le simple fait de séparer fait que tu vas coder tous les changements en double. En travaillant au pixel, tu peux potentiellement éviter cette duplication.
Si tu codes par exemple une image gray4 composée de bandes noires et blanches verticales alternées, en séparant les plans tu obtiens une taille fichier quasiment double (le quasiment vient de la nécessite en ne séparant pas de spécifier la couleur de l'aplat suivant, alors qu'en séparant chaque plan peut se contenter de sa longueur, le blanc suivant forcément le noir et réciproquement).

Bah c'est toujours le même constat: sur des surfaces blanches ou noires le RLE "classique" est efficace, alors que sur des surfaces grisées ma technique est plus rentable.

Justement non. Là sur des surfaces grises les deux techniques sont équivalentes, alors que sur des surfaces noires ou blanche celle de Ethaniel est devant.