J'ai actuellement le tableau suivant dans un programme Java,
byte[] data = new byte[800];
7 Réponses :
Un algorithme de compression / décompression vraiment simple qui est pratique dans de minuscules environnements embarqués et est facile à "rouler le vôtre" est en train de coder de longueur. Fondamentalement, cela signifie remplacer une série de valeurs dupliquées avec une paire (comptage, valeur). Bien sûr, vous avez besoin d'une valeur sentinelle (magique) pour introduire la paire, puis un mécanisme permettant à la valeur magique d'apparaître dans des données normales (généralement une séquence d'évacuation peut être utilisée pour les deux travaux). Dans votre exemple, il serait peut-être préférable d'utiliser des valeurs 16 bits (2 octets).
Mais naturellement, tout dépend de la donnée. Les données suffisamment aléatoires sont incompressibles par définition. Vous feriez de mieux pour collecter d'abord quelques données d'abord, puis évaluer vos options de compression.
Modifier après des informations supplémentaires publiées Juste pour le plaisir et pour montrer comment Le codage de longueur d'exécution facile est que j'ai codé quelque chose. J'ai bien peur que je n'ai pas utilisé C pour la compression aussi, car je ne suis pas un gars Java. Pour garder les choses simples, j'ai entièrement fonctionné avec des données de 16 bits. Une optimisation serait d'utiliser un nombre de 8 bits dans la paire (comptage, valeur)). Je n'ai pas essayé de compiler ou de tester ce code. Voir aussi mon commentaire à votre question sur les avantages possibles de la mangling les adresses LED.
Le codage de la longueur d'exécution est peu susceptible d'être très utile pour les données d'image 16 bits, à moins que l'image elle-même n'est générée par ordinateur.
+1 .. Pour une compression supplémentaire: divisez les pixels de "haute couleur" 16 bits dans les composants R, G, B. Ensuite, faites une simple prédiction de premier ordre par composant et la longueur de la longueur d'exécution de chaque composant est propre. Cela vous donnera trois flux bit qui sont triviaux à décompresser.
@CAF J'ai qualifié ma recommandation en disant d'abord de collecter certaines données. Avec certaines données devant vous, il est facile de dire si le codage de la longueur d'exécution est utile ou non. Fondamentalement, je suis d'accord avec votre commentaire à la question elle-même.
Bien sûr, le code que j'ai affiché assume des processeurs à chaque extrémité du fil sont à la fois petit Endian, soit à la fois grand Endian.
LZ77 / 78 sont relativement faciles à écrire http://fr.wikipedia.org/wiki/lz77_and_lz78 < / a>
Toutefois, étant donné la petite quantité de données que vous transférez, il ne vaut probablement pas la peine de la compresser du tout.
Si les données sont "plus ou moins aléatoires", vous n'aurez pas beaucoup de chance de la compresser, j'ai peur.
Compte tenu des nouvelles informations, je parie que vous n'avez pas besoin de couleurs 32K sur votre écran LED. J'imaginais qu'une palette de 1024 ou 256 couleurs pourrait être suffisante. Vous pouvez donc vous éloigner avec un schéma de compression trivial (cartographier simplement chaque mot à travers une table de recherche, ou éventuellement simplement supprimer les LSB de chaque composant), cela fonctionnerait même pour des valeurs de pixels complètement non corrélées.
Downvoter: Explique, s'il vous plaît? Cette réponse est parfaitement sérieuse; La plupart des autres réponses sont des propositions basées sur des hypothèses qu'il existe une certaine structure aux données.
Je suis allé de l'avant et je viens de laisser tomber le LSB mais malheureusement que le dernier bit était plutôt remarquable (les roses ont fini de rouge droit, etc.). J'irai de l'avant et j'essaie de limiter le nombre de couleurs, peut-être que j'aurais peut-être plus de chance avec ça.
@William: C'est étrange. Je ne m'attendrais pas à ce que les valeurs changeantes de 1 font une différence notable avec 32 couleurs par canal! (Essayez-le dans la peinture MS ou quelque chose ...) Votre affichage doit avoir une courbe gamma étrange.
Je pense que vous avez peut-être laissé tomber le MSB par erreur. La plupart des LED ont une caractéristique assez linéaire ..
O Homme, je n'ai pas vu votre commentaire avant juste maintenant, mais en regardant dans le code, c'est exactement ce que j'ai fait sur les chaînes bleues et vertes. J'ai décalé un trop grand-chose et j'ai laissé tomber les MSB et le LSB sur ceux-ci. Maintenant, les couleurs ont l'air juste!
L'une des premières choses à faire serait de convertir de RVB en YUV, ou YCRCB, ou quelque chose sur cet ordre. Ayant fait cela, vous pouvez généralement vous échapper avec des canaux U et V (ou CR / CB) à la demi-résolution. Ceci est assez courant dans la plupart des types d'images (par exemple, JPEG et MPEG le font, et ainsi les capteurs dans la plupart des appareils photo numériques).
Réalisme, en commençant par 800 octets de données, la plupart des autres formes de compression vont être une perte de temps et d'effort. Vous allez devoir mettre en place un peu de travail avant d'accomplir beaucoup (et de le garder raisonnablement rapide sur un Arduino ne sera pas trivial pour non plus).
Edit: D'accord, si vous êtes absolument certain que vous ne pouvez pas modifier les données du tout, les choses deviennent plus difficiles très rapidement. La vraie question à ce stade est le type d'entrée avec laquelle vous avez affaire. D'autres ont déjà mentionné la possibilité de quelque chose de l'ordre d'une compression prédictive du delta - par exemple sur les pixels précédents, prédisez ce que le prochain est susceptible d'être, puis de ne coder que la différence entre la prévision et la valeur réelle. Toutefois, il faut au maximum, il faut généralement exécuter le résultat par une sorte d'algorithme basé sur entropie comme Shannon-Fanno ou Compression Huffman. Ceux-ci, malheureusement, ne sont généralement pas les plus rapides à décompresser cependant.
Si vos données sont la plupart des éléments tels que des graphiques ou des graphiques, où vous pouvez vous attendre à avoir de grandes zones de pixels identiques, le codage de la longueur (ou de l'exécution) peut fonctionner assez bien. Cela a l'avantage d'être vraiment trivial à décompresser également.
Je doute que la compression de LZ soit si bien fonctionne si bien. La compression basée sur la LZ fonctionne (en général) en construisant un dictionnaire de chaînes d'octets qui ont été observées, et lorsque / si la même chaîne d'octets est revue, transmet le code attribué à l'instance précédente au lieu de redéfinir la ré-transmission de l'ensemble. chaîne de caractères. Le problème est que vous ne peut pas transmettre des octets non compressés - vous commencez en envoyant le mot de code qui représente cet octet dans le dictionnaire. Dans votre cas, vous pouvez utiliser (par exemple) un mot de code 10 bits. Cela signifie la première fois que vous envoyez des caractères particulièrement, vous devez l'envoyer sous 10 bits, pas seulement 8. Vous ne commencez à obtenir qu'une certaine compression lorsque vous pouvez vous accumuler plus longtemps (deux octets, trois octets, etc.) Cordes dans votre dictionnaire, et trouver une chaîne correspondante plus tard dans l'entrée.
Cela signifie que la compression basée sur la LZ obtient généralement une compression assez médiocre pour les centaines de centaines d'octets d'environ deux centaines d'octets environ, puis des pauses, même pendant un moment, et seulement après avoir fonctionné sur une entrée pendant un moment, cela commence-t-il vraiment à compresser bien . Traiter avec seulement 800 octets à la fois, je ne suis pas du tout sûr que vous allez jamais voir beaucoup de compression - en fait, travailler dans de tels blocages, il ne serait pas particulièrement surprenant de voir les données se développer sur un base assez régulière (surtout si c'est très aléatoire).
Les données sont plus ou moins aléatoires, je dirais que cela représente une valeur de couleur RVB pour chaque 16 bits.
Quel serait le meilleur moyen de compresser ces données? Aucune idée de combien de compression je pourrais éventuellement obtenir?
Idéalement, vous pouvez compresser 800 octets de données de couleur à un octet si l'image entière est la même couleur. Comme Oli Charlesworth mentionne cependant les données les plus aléatoires, moins vous pouvez la compresser. Si vos images ressemblent à Statique sur un téléviseur, alors, bien, bonne chance, de la sorte de compression.
considère définitivement la réponse d'Oli Charlesworth. Sur une grille 20x20, je ne sais pas si vous avez besoin d'une palette de couleurs 32K.
Aussi, dans votre précédente Question , vous avez dit Vous essayiez de courir cela sur une période de 20 ms (50 Hz). Avez-vous vraiment besoin de beaucoup de vitesse pour cet affichage? A 115200 BPS, vous pouvez transmettre ~ 11520 octets / sec - appelez-le à 10 kbps pour une marge de sécurité (par exemple, votre micro pourraient avoir un délai entre des octets, vous devriez faire des expériences pour voir ce que la largeur de bande «réelle» est). À 50 Hz, cela vous permet seulement d'environ 200 octets par paquet - vous recherchez un ratio de compression sur 75%, ce qui peut ne pas être réalisable en aucune circonstance. Vous semblez jolie marié à vos besoins, mais il peut être temps de faire un chat maladroit.
Si vous voulez aller à la route de compression, vous devrez probablement simplement essayer plusieurs algorithmes différents avec des données «réelles», car d'autres l'ont dit, et essayez différents codages. Je parie que vous pouvez trouver du temps de traitement supplémentaire en faisant des mathématiques Matrix, etc. Entre la réception d'octets sur la liaison série (vous aurez environ 80 microsecondes entre des octets) - si vous utilisez des interruptions pour lire les données de série au lieu d'interrogation, vous Peut probablement faire assez bien en utilisant un double tampon et en traitement / affichage du tampon précédent tout en lisant dans le tampon actuel.
EDIT:
Est-il possible d'augmenter la vitesse du port série au-dessus de 115200? Ce Adaptateur USB-Serial à Amazon dit que ça va Jusqu'à 1 Mbps (probablement réellement 921600 bps). Selon votre matériel et votre environnement, vous devrez peut-être vous soucier des mauvaises données, mais si vous augmentez suffisamment la vitesse, vous pouvez probablement ajouter une somme de contrôle, et peut-être même une correction d'erreur limitée.
Je ne connais pas l'Arduino, mais j'ai eu une voiture de freeCale HCS08 8 bits à 1,25 Mbps, bien que le bus fonctionne réellement RS-485, et non RS-232 (485 utilise la signalisation différentielle pour mieux Performances sonores), et je n'ai aucun problème avec des erreurs de bruit. Vous pouvez même envisager un adaptateur USB RS-485, si vous pouvez filer que sur votre Arduino (vous auriez besoin de matériel de conversion pour modifier les signaux 485 des niveaux de l'Arduino).
edit 2:
Vous pouvez également considérer ce Adaptateur USB-SPI / I2C , Si vous avez une interface I2C ou SPI disponible, vous pouvez gérer le câblage. Il est dit que cela peut aller à 400 kHz I2C ou 200 kHz SPI, ce qui n'est toujours pas assez suffisant, mais vous pouvez diviser les données entre le SPI / I2C et la liaison série que vous avez déjà.
800 octets n'est pas beaucoup de données ... est-ce juste pour l'illustration, ou est-ce que tout ce que vous allez jamais être envoyé?
Une bonne compression dépend beaucoup des caractéristiques des données que vous avez à compresser. Si vous pouvez créer un lien vers quelques échantillons représentatifs des données, vous obtiendrez de meilleures réponses.
Il n'y a nulle part assez d'informations pour répondre judicieusement de cette question. Si vos données sont vraiment aléatoires, alors c'est incompressible. Si vos données représentent des images de quelque sorte, vous pourriez avoir de la chance. Mais vous n'avez pas précisé quelle sorte d'image, ni si vous êtes prêt à tolérer la perte de pertes, etc.
Je n'ai rien de plus précisément à l'esprit, mais si vous avez une plate-forme qui gère Java à une extrémité et une Arduino à l'autre, et vous n'envoyez que Java à C, vous pouvez bien avoir un ordinateur de bureau / ordinateur portable à la En l'envoi de la fin, auquel cas vous n'avez pas besoin de compression symétrique, mais vous pouvez vous permettre d'avoir quelque chose avec un coût de processeur beaucoup plus élevé pour comprimer qu'il fonctionne pour décompresser, comme beaucoup de codecs vidéo numériques.
@Rook il peut utiliser la liaison série; 800 octets se trouvent trois quarts d'une seconde à 9600 bauds, ce qui est un moment important. Si vous envoyez 1,5 km sur une liaison radio Baud 9600, le premier octet atteint la lune avant de terminer la transmission.
Les informations supplémentaires me rendent plus confiance en codage de longueur d'exécution pour vous travailler. Vous pouvez exploiter le fait que le bit MS de vos données 16 bits est toujours 0 pour encoder efficacement la valeur sentinelle / magie avec un 1 dans ce bit. Une belle raffinement pourrait être de manquer les adresses de LED. C'est-à-dire que vous n'aurez pas nécessairement la LED en haut à gauche au mot 0 et la LED inférieure droite au mot 399. Il peut être avantageux d'utiliser un schéma différent qui le rendra plus probable que les mots adjacents ont la valeur d'enregistrement (couleur).