Les membres ayant 30 points peuvent parler sur les canaux annonces, projets et hs du chat.

Forum Casio - Actualités


Index du Forum » Actualités » Aventure Python : données compactes et Bad Apple sur Graph 90+E
Lephenixnoir En ligne Administrateur Points: 19811 Défis: 142 Message

Aventure Python : données compactes et Bad Apple sur Graph 90+E

Posté le 15/04/2021 17:34

Hier Loieducode a posté sa version de Bad Apple en C sur Graph 90, ce qui a rappelé à Dark Storm qu'il en avait fait une version Python durant le concours de démos graphiques.

Pourquoi est-ce notable ? « Parce que les performances de ces langages sont deux mondes différents », vous me direz ? Eh bien... pas tant que ça, en fait. Voici une petite histoire Python démontrant que la toute dernière appli en date en a plus sous le capot qu'on pourrait le croire.

Et voilà le résultat (avec overclock), un peu lent dans les passages difficiles mais plus rapide que l'original la plupart du temps !


Vous pouvez télécharger le programme ici : télécharger bad-apple-python.zip. Pour l'installer :

• Transférez le dossier ba dans la mémoire de stockage (avec les 44 fichiers dedans).
• Transférez demo.py à côté de ba (vous pouvez le renommer).
• Lancez demo.py, et enjoy!

La plupart des optimisations réalisées sont spécifiques à ce programme, mais j'ai trouvé au passage une bonne façon de stocker des données de façon très compacte, qui peut être réutilisée.

Version originale : noir et blanc, différences entre frames

Le but de ce programme est de faire un rendu vidéo de Bad Apple. C'est une vidéo très pratique parce que tout est en noir et blanc donc il y a peu de détails à afficher, et la plupart des pixels ne changent pas de couleur d'une image à l'autre (le fond en particulier ne change quasiment jamais).

Le programme original de Darks pour le concours de démos graphiques affiche la première image de la vidéo en taille 128x96, et ensuite contient seulement les pixels à modifier pour passer d'une image à la suivante. On gagne beaucoup de place parce que sur les ~12000 pixels la majorité ne change pas de couleur et donc on n'a pas besoin de les lister ni de les redessiner.

De plus, les pixels ne changent pas de couleurs tous seuls, souvent ils changent en groupe (quand un pixel change, la plupart du temps ses voisins changent aussi). Darks groupe donc les pixels qui changent par bandes horizontales ; c'est une optimisation bien connue qui s'appelle run-length encoding. La bande est représentée par un tuple (y,x1,x2,color) : y est la ligne où elle se trouve, x1 et x2 sont les positions horizontales du début et de la fin de la bande, et color vaut 0 si la bande est noire dans la nouvelle image, 1 si elle est blanche.

Voilà par exemple les modifications nécessaires pour passer de l'image 15 à l'image 16 :

[(43,127,128,1),(44,127,128,1),(45,127,128,1),(46,127,128,1),(47,126,128,1),(48,126,128,1),(49,126,128,1)]

Il y a 7 plages, entre les lignes 43 et 49, qui deviennent toutes blanches.

Pour afficher la vidéo, on commence par la première image (qui est blanche) et ensuite on affiche toutes les bandes avec cette boucle :

colors = [(0,0,0), (255,255,255)]
for (y, x1, x2, c) in frame:
    for x in range(x1, x2 + 1):
        set_pixel(2*x, 2*y, colors[c])
        set_pixel(2*x+1, 2*y, colors[c])
        set_pixel(2*x, 2*y+1, colors[c])
        set_pixel(2*x+1, 2*y+1, colors[c])
show_screen()

Il y a 4 set_pixel() parce que l'image est agrandie au passage de 128x96 (la résolution de la vidéo) à 256x192 (plus proche de la taille de l'écran). Prendre la vidéo directement à 256x192 aurait été plus difficile.

Le script Python charge les images une par une depuis des fichiers Python, comme ça il peut supprimer les images de la mémoire après les avoir affichées. C'est pratique, mais du coup il y a des fichiers très petits comme celui ci-dessus et d'autres beaucoup plus gros lorsqu'on passe par exemple d'une fond blanc à un fond noir ou inversement.

À ce stade, le programme tourne à 2-3 FPS sans overclock. Clairement, on peut faire mieux ! Il y a trois pistes à explorer : rendre le code Python plus compact, rendre le format vidéo plus compact, et éviter de charger trop de fichiers.

Compacter le code avec des bytes

Ma première idée pour améliorer le format était de grouper les tuples en entiers. En effet, les valeurs sont toutes petites : y est entre 0 et 95, x1 et x2 sont entre 0 et 127, et c vaut soit 0 soit 1. On peut aisément combiner les 4 dans un entier de 32 bits, ce qui donne le résultat suivant pour le premier exemple (avec c en octet de poids fort pour gagner quelque chiffres).

[19627904,19693440,19758976,19824512,19889792,19955328,20020864]

Le défaut des tuples c'est qu'ils sont alloués dans le tas, donc il faut faire un malloc() chaque fois qu'on en crée un, et ça prend du temps supplémentaire qui s'accumule vite. Je pensais que les petits entiers en étaient exempts, mais les performances n'ont pas vraiment grimpé avec cette modification, donc peut-être qu'ils y passent aussi.

Cependant, l'idée de compacter ainsi est bonne, il suffit de la formuler autrement. Si un entier ne convient pas, alors un peut utiliser un bytes. Le type bytes est un tableau d'octets, si vous n'êtes pas familier avec c'est comme une liste sauf que :

• Il est de taille fixe et on ne peut pas modifier les éléments.
• Les éléments sont uniquement des entiers entre 0 et 255 (des « octets »).
• On peut les écrire comme une chaîne de caractères.
• Il est beaucoup plus léger et beaucoup plus compact qu'une liste.

Par exemple (et j'évite de rentre dans les détails), le bytes suivant contient deux éléments, 64 et 47. La partie b" au début est fixe et signifie qu'on crée un bytes, le " à la fin est fixe aussi et marque la fin de la séquence, et les deux caractères au milieu représentent un élément chacun (@ c'est 64 et / c'est 47).

b"@/"

Il y a deux avantages à ce système : d'une part il n'y a pas besoin de créer de liste, d'entiers ou de tuples, ce qui simplifie beaucoup le chargement ; et d'autre part pour chaque caractère dans le code source on a un octet de données dans le programme, ce qui parfait en termes de compacité, car c'est le maximum possible !

(Pour les curieux : il y a quelques caractères qu'il faut échapper, à savoir le backslash, les \r et \n, et le guillemet fermant. MicroPython accepte les octets nuls bruts, ce qui est vraiment important parce qu'il y en a parfois beaucoup !)

L'inconvénient de cette méthode c'est que beaucoup de valeurs entre 0 et 255 ne correspondent pas à des caractères très lisibles voire pas à des caractères du tout, donc le fichier devient illisible dans un éditeur de texte, et la calculatrice affiche des espaces partout. Ci-dessous vous pouvez voir ce à quoi ça ressemble dans vim (les parties rouges sont des caractères qui existent comme @ et /, pour les parties en bleu aucun caractère ne correspond donc vim improvise dans une autre couleur pour indiquer que c'est le bordel).


Bref, ces fichiers-là on les génère avec un programme, on les copie sur la calculatrice et on les ouvre jamais !

Compacter le format de la vidéo

Une autre amélioration que j'ai apportée au programme est de changer le format de la vidéo. Chaque image est représentée comme une liste de bandes horizontales qui doivent changer de couleur pour passer de l'image précédente à l'image actuelle. Mais dans l'ancien système avec quatre valeurs y, x1, x2 et color, il y a beaucoup de répétition :

• D'une part il y a souvent plusieurs bandes sur la même ligne, donc en moyenne le même y est recopié 4 fois sur 4 bandes successives ;
• D'autre part color ne peut valoir que 0 ou 1, lui donner un octet entier (qui peut représenter 8 fois plus d'information que ça) c'est du gâchis d'espace.

Je ne vais pas rentrer dans les détails ici, mais j'ai modifié le format pour que chaque bande soit encodée avec deux octets seulement : d'abord la valeur de x1, et ensuite une combinaison entre la valeur de x2 et celle de color. Pour la valeur de y, on commence sur la ligne 0 au début de l'image, et chaque fois qu'une bande est sur une nouvelle ligne j'ai un octet spécial qui indique de combien il faut descendre.

Ensemble, ces deux optimisations réduisent l'espace occupé par chaque bande de 4 octets à environ 2.25 en moyenne. Ce qui est super, parce que moins de données à manipuler ça veut dire que le chargement est beaucoup plus rapide, et souvent le code aussi.

Améliorer le chargement des fichiers

Initialement on avait un fichier Python par image, et Darks avait extrait 1000 images de la vidéo (la moitié environ). Ça fait beaucoup, surtout que sur les 1000 images certaines sont presque identiques aux précédentes, ce qui donne des fichiers quasi-vides et donc des import quasi-inutiles.

Darks avait programmé une option dans sa démo initiale pour mettre plusieurs images dans un seul fichier, et quand je l'ai testée j'ai tout de suite remarqué que c'était crucial : avec 3 images par fichier, on a un enchaînement fluide de 3 images, une petite saccade le temps de charger le fichier suivant, de nouveau 3 images fluides, une petite saccade...

Il est clair que la plupart du temps est passé à charger les fichiers puis à créer les variables listes ou bytes qui contiennent les séquences de bandes. C'est pour ça que compacter est si important : réduire la taille du fichier accélère la première partie, et éliminer des tuples et des listes accélère la seconde.

En plus, le fichier principal (demo.py) peut être très long s'il doit importer 1000 fichiers différents, donc plus on groupe d'images dans les mêmes sous-fichiers, plus demo.py est court, plus le chargement initial est rapide. C'est gagant-gagnant-gagnant !

Pour profiter au maximum de cette possibilité, j'ai modifié le convertisseur qui génère les données à partir de la vidéo pour mettre autant d'images possible dans chaque fichier, jusqu'à atteindre une taille choisie à l'avance (10 kio). Ça veut dire que dans les parties où les images ne changent pas beaucoup je peux mettre beaucoup d'images dans le même fichier, et dans les parties où les images changent beaucoup je garde des fichiers assez petits pour ne pas saturer la mémoire l'appli Python.

Les modifications que j'ai présentées ci-dessus réduisent la taille totale du projet de 2587 kio à 463 kio (soit 5 fois plus petit environ), et demo.py de 42 kio à juste 2 kio. Il y avait 1000 fichiers au début pour stocker toutes les images, et seulement 44 maintenant grâce au groupement. Et cerise sur le gâteau, c'est beaucoup plus rapide !

Conclusion

Malgré les limitations qui lui sont propres, Python dépasse le Basic CASIO de loin sur plusieurs aspects. Le module de dessin casioplot, bien plus flexible (et performant) que les alternatives en Basic, nous montre bien que le langage et l'interpréteur offrent des possibilités tout à fait inédites et jusqu'ici seulement accessibles aux add-ins.

Il faut bien sûr un grain de folie pour utiliser des bytes comme ça, mais c'est loin d'être la technique la plus extravagante utilisée couramment sur Planète Casio. Je pense qu'avec le temps d'autres astuces vont apparaître et rendre le Python de plus en plus attractif!

N'hésitez pas à demander des clarifications en commentaires, ou à proposer d'autres idées pour des projets fous en Python.

À bientôt sur Planète Casio !

Fichier joint


FlamingKite Hors ligne Membre Points: 302 Défis: 3 Message

Citer : Posté le 15/04/2021 18:18 | #


Est ce qu'il y a besoin de préciser la qualité d'un article de Lephe ?

En vrai, c'est un super article, même si je n'ai pas compris tous les détails de la partie "Compacter le code avec des bytes" x) (note à moi même : revoir ton TDM sur les données ou sur la mémoire, je dois voir lequel correspond).

Ça pourrait limite être un TDM comme exemple, mais vu qu'on est jeudi, c'est pas possible
Cliquez pour découvrir
Cliquez pour recouvrir
"Un pessimiste voit la difficulté dans chaque opportunité, un optimiste voit l'opportunité dans chaque difficulté"
Winston Churchill


J'ai bien envie aussi de mettre mes programmes en signature, après j'en ai que 2 donc c'est pas génial Bon allez, je les met quand même :
les 2 smileys c'est pour garder la bonne humeur
Lephenixnoir En ligne Administrateur Points: 19811 Défis: 142 Message

Citer : Posté le 15/04/2021 19:19 | #


Merci ! Pour l'histoire des bytes c'est un vraiment le sujet couvert dans le TDM oui. Ultimement, un bytes c'est vraiment une séquence d'octets sous sa forme la plus pure. Ce type incarne la notion de « données libres » parfaitement, car tu peux y mettre ce que tu veux au bit près.

Ensuite tu arrives avec toute la partie « chaîne de caractère » qui est moins intuitive. Si tu veux avoir les trois octets 35, 87 et 73, tu peux écrire bytes([ 35, 87, 73 ]), mais ça prend beaucoup de texte et le fichier Python est gros. C'est là que le texte aide : cette séquence de trois octets sert à représenter le texte "#WI" en encodage ASCII (ou UTF-8 ici), et pour te simplifier la vie Python te laisse écrire ces trois caractères dans le code source (entre b" et ") et il récupère les octets associés. C'est plus court !

Tant que la séquence que tu veux correspond à du texte ASCII ou UTF-8, tu peux faire ça. Maintenant y'a plein d'octets que tu ne « peux pas » obtenir en ASCII ou UTF-8, par exemple 129, donc il n'y a pas de caractère que tu peux mettre entre b"" pour avoir l'octet 129 dans la séquence. Mais comme je suis têtu, je mets quand même un octet 129 dans le fichier source Python entre le b" et le ". Ça fait de mon fichier Python un fichier texte invalide et du coup il ne ressemble à rien dans vim, mais MicroPython ne s'en soucie pas trop et il accepte l'octet quand même. C'est un peu osé mais c'est super efficace !
FlamingKite Hors ligne Membre Points: 302 Défis: 3 Message

Citer : Posté le 15/04/2021 19:22 | #


D'accord, je vois, c'est super clair !

Je vais quand même finir de revoir le TDM, ça sera sans aucun doute utile
Cliquez pour découvrir
Cliquez pour recouvrir
"Un pessimiste voit la difficulté dans chaque opportunité, un optimiste voit l'opportunité dans chaque difficulté"
Winston Churchill


J'ai bien envie aussi de mettre mes programmes en signature, après j'en ai que 2 donc c'est pas génial Bon allez, je les met quand même :
les 2 smileys c'est pour garder la bonne humeur
Loieducode Hors ligne Membre Points: 55 Défis: 0 Message

Citer : Posté le 18/04/2021 10:19 | #




on avance petit a petit(en 256*256 avec RLE en haut et meme resolution, sans RLE 2 couleurs en bas ) (Imgur ne marche pas)
J'ai beacoup trop de projets, nyohoho!
Lephenixnoir En ligne Administrateur Points: 19811 Défis: 142 Message

Citer : Posté le 18/04/2021 11:15 | #


Pas mal ! Du coup RLE 2 couleurs c'est ce que j'ai fait comme format (enfin Darks plus précisément) et j'ai 1m41s pour les 1000 frames, couvrant 463 kio. Si on extrapole un peu, on peut s'attendre à ce que la vidéo complète tienne en moins d'1 Mo en 128x96.

256x256 ce serait stylé pour un add-in. 16 Mo c'est pas mal déjà mais ça tient pas encore dans la mémoire de stockage, est-ce qu'il te reste des pistes sur le format ou toute la différence est liée à la plus grande résolution ?

(J'ai corrigé tes liens.)
Loieducode Hors ligne Membre Points: 55 Défis: 0 Message

Citer : Posté le 18/04/2021 13:50 | #


Alors, quand je disais
J'ai a écrit :
sans RLE 2 couleurs en bas

je voulais dire que cette version est démunie de RLE et elle est en 2 couleurs
la version en haut est en RLE avec 256 couleurs
Ce que je pourrais faire pour optimiser c'est de mettre du RLE pas que pour les pixels d'une frame, mais pour les frames aussi, mais bon, c'est trop pour que mon cerveau comprenne.
J'ai beacoup trop de projets, nyohoho!
Lephenixnoir En ligne Administrateur Points: 19811 Défis: 142 Message

Citer : Posté le 18/04/2021 19:08 | #


Ah, je vois c'est plus clair. Effectivement en 256 couleurs inutile de faire du RLE... j'ai toujours pensé que pour bien compresser avec beaucoup de couleurs il fallait regarder du côté de vrais codecs vidéos (genre les simples), mais j'ai jamais vraiment cherché en détail et je sais pas si on a assez de puissance de calcul pour décoder en temps réel.
Dark storm En ligne Labélisateur Points: 11412 Défis: 176 Message

Citer : Posté le 18/04/2021 20:44 | #


il fallait regarder du côté de vrais codecs vidéos (genre les simples)

J'avais commencé à regarder, le plus simple selon moi est le M-JPEG. En gros c'est une succession de Jpeg les uns derrière les autres (pour faire simple).
Le problème est que quelque soit le codec que tu implémente, tu te retrouve avec un code assez… compliqué. Je comprends ce que tu disais quand les HID vidéo étaient difficiles à appréhender, je pense que ça vient aussi du fait que la vidéo est quelque chose de non-trivial.

Niveau performances faut voir, mais je pense qu'encore une fois ce qui risque de limiter, c'est la flash.
Finir est souvent bien plus difficile que commencer. — Jack Beauregard
Lephenixnoir En ligne Administrateur Points: 19811 Défis: 142 Message

Citer : Posté le 18/04/2021 23:02 | #


Hmm le JPG c'est pas évident à cause de la transformation en cosinus discrète, qui demande pas mal de calcul en plus d'avoir du point fixe/flottant. C'est pas impossible avec des tables mais vu qu'il y a, pour chaque bloc de 8x8 pixels, une double somme (8x8 = 64 termes) de produits de cosinus pour chacun des 64 pixels, tu te retrouves avec 128 facteurs de la forme cos((2x+1)uπ/16) à calculer par pixel, et il devient évident pourquoi le SH7724 a un module périphérique qui fait ça à ta place.
Loieducode Hors ligne Membre Points: 55 Défis: 0 Message

Citer : Posté le 24/04/2021 14:40 | #


Hmm, j'ai pensé a une methode de compression(bon elle est a perte, mais bon)
1: Créer des "blocks" et leur donner un ID(ces blocks ne contiennent pas de couleur, juste des indexs)
2: On regarde tout les blocks de pixels(de la meme taille que les block d'index), un à un et on se pose la question: "Quel block d'index est le plus proche de ce block de pixel?"
3: On met l'id du block d'index le plus proche dans le fichier, et on met une approximation de toutes les couleurs dans le block de pixels juste apres(voila pourquoi il y a des indexs dans les blocks)

Enfin c'est la premiere idée que j'ai eu en tete après avoir abandonné le RLE pour le mode 256 couleurs.
J'ai beacoup trop de projets, nyohoho!
Lephenixnoir En ligne Administrateur Points: 19811 Défis: 142 Message

Citer : Posté le 24/04/2021 15:08 | #


En gros une palette de blocs. C'est pas stupide... je pense qu'on peut calculer un peu pour se donner une idée de si ça va bien marcher.

Clairement une palette de 256 blocs c'est trop petit pour du 256 couleurs. Si tu veux prendre plus, l'option naturelle suivante c'est soit 4096 soit 65536 blocs. Le second est tentant, le truc c'est qu'il faudrait mettre au moins 3 pixels dedans sinon l'index prend autant de place que les valeurs, et 3×64k ça ne rentrerait pas dans la mémoire de travail en Python, et serait aussi très gros à charger en C.

Imaginons qu'on fasse des blocs de 2×2 pour voir. La distance avec laquelle on va chercher le « plus proche » n'est pas n'importe laquelle. Après tout, on peut se permettre des approximations sur la couleur des pixels mais on peut pas trop se permettre d'avoir les couleurs dans le mauvais ordre. Si on part dans le cas simple où la distance c'est une combinaison des distances sur chaque pixel individuel du bloc, la compression reviendra au même que pré-discrétiser la vidéo, et on gagne juste le stockage des blocs ; ce qui peut être pas mal déjà, d'autant plus que coder à la main un algo pour trouver une bonne palette c'est pas facile.

Sur du 2×2, en 256 couleurs tu représentes 4 octets de données par entrée de la palette. Mais quand on y réfléchit, même une vidéo de 192×192 n'a que 9216 blocs de cette taille par image (96²), ce que tient dans 16 (14) bits. Donc même sans compression, tu passes de 192²×2 = 74 kio de données brutes à 96²×2 indices de blocs + 96²×4 contenus de blocs = 55 kio.

Tu peux d'ailleurs faire des blocs de plus en plus gros et ce motif converge.

With blocs of size 2x2:
  Blocks: 9216
  Bytes per index: 2
  Bytes per definition: 4
  Total size: 55296
With blocs of size 3x3:
  Blocks: 4096
  Bytes per index: 2
  Bytes per definition: 9
  Total size: 45056
With blocs of size 4x4:
  Blocks: 2304
  Bytes per index: 2
  Bytes per definition: 16
  Total size: 41472
With blocs of size 6x6:
  Blocks: 1024
  Bytes per index: 2
  Bytes per definition: 36
  Total size: 38912
With blocs of size 8x8:
  Blocks: 576
  Bytes per index: 2
  Bytes per definition: 64
  Total size: 38016
With blocs of size 12x12:
  Blocks: 256
  Bytes per index: 1
  Bytes per definition: 144
  Total size: 37120
With blocs of size 16x16:
  Blocks: 144
  Bytes per index: 1
  Bytes per definition: 256
  Total size: 37008

Mais maintenant ce qui est intéressant c'est de prendre les 9216 blocs et d'en supprimer. Une fois éliminé les tous noirs et tous blancs qui méritent 100% un encodage spécial à 1 octet voire du RLE, un petit coup de clustering type k-medians paraît approprié ici pour réduire le nombre de blocs différents sans détruire l'aspect visuel. Il est peu probable de passer sous 256 blocs, mais passer sous 4096 devrait être totalement faisable, ce qui laisserait 96²×1.5 octets d'indices + 4096×4 octets de couleurs = 30 kio de données par frame. On est déjà sous la limite du système sans compression même avec les gros blocs, et encore j'ai pas compté l'optimisation des blocs tous noirs ou tous blancs.

Après on reste relativement loin du format mono RLE (qui fait tenir un frame en 463 octets en moyenne dans mon cas), mais ça pourrait déjà être pas mal.

Sinon, au lieu de s'emmerder avec les blocs tous noirs ou tous blancs, tu passes juste un coup de Huffman ou de DEFLATE sur le résultat et ça compressera automatiquement tous ces blocs qui se répètent. Le décodage ne serait pas un problème en C, mais en Python c'est une autre affaire c'est sûr.

Note que tout ça ressemble un peu à JPEG; la différence est quand le format JPEG on décrit le blocs comme une combinaisons de motifs prédéfinis (à base de transformée en cosinus discrète) et ensuite on supprime l'information concernant les motifs moins visibles pour l'oeil humain.

LienAjouter une imageAjouter une vidéoAjouter un lien vers un profilAjouter du codeCiterAjouter un spoiler(texte affichable/masquable par un clic)Ajouter une barre de progressionItaliqueGrasSoulignéAfficher du texte barréCentréJustifiéPlus petitPlus grandPlus de smileys !
Cliquez pour épingler Cliquez pour détacher Cliquez pour fermer
Alignement de l'image: Redimensionnement de l'image (en pixel):
Afficher la liste des membres
:bow: :cool: :good: :love: ^^
:omg: :fusil: :aie: :argh: :mdr:
:boulet2: :thx: :champ: :whistle: :bounce:
valider
 :)  ;)  :D  :p
 :lol:  8)  :(  :@
 0_0  :oops:  :grr:  :E
 :O  :sry:  :mmm:  :waza:
 :'(  :here:  ^^  >:)

Σ π θ ± α β γ δ Δ σ λ
Veuillez donner la réponse en chiffre
Vous devez activer le Javascript dans votre navigateur pour pouvoir valider ce formulaire.

Si vous n'avez pas volontairement désactivé cette fonctionnalité de votre navigateur, il s'agit probablement d'un bug : contactez l'équipe de Planète Casio.

Planète Casio v42 © créé par Neuronix et Muelsaco 2004 - 2021 | Il y a 81 connectés | Nous contacter | Qui sommes-nous ? | Licences et remerciements

Planète Casio est un site communautaire non affilié à Casio. Toute reproduction de Planète Casio, même partielle, est interdite.
Les programmes et autres publications présentes sur Planète Casio restent la propriété de leurs auteurs et peuvent être soumis à des licences ou copyrights.
CASIO est une marque déposée par CASIO Computer Co., Ltd