Dans une application, je travaille sur, je dois envoyer une matrice de 256 x 256 sur une prise. Je développe un client de visualisation pour un simulateur de système offshore qui fonctionne sur un cluster, et cette matrice est une chaîne de hauteur représentant l'état actuel de la surface océanique.
Ceci est une application en temps réel. La vitesse est donc un must. Et, en utilisant une matrice de flotteurs de 256 x 256 de flotteurs, je dois envoyer 256 kilo -tes de données chaque seconde, pour une bande passante de 256 Ko / seconde.
C'est beaucoup, du moins pour mon application.
Donc, ma question est, y a-t-il une bonne méthode de compression de cette matrice avant de l'envoyer via la prise? Et, s'il y a une telle méthode, combien de réduction OS puis-je m'attendre?
Comme ma matrice représente une surface continue, les méthodes de compression de perte ne sont pas un problème pour moi. Je suis surtout préoccupé par le ratio de compression, le temps qu'il faut pour la compression pour avoir lieu et, enfin, s'il existe déjà une mise en œuvre de cette méthode pour C ++.
8 Réponses :
Eh bien, une matrice n'est qu'un signal 2D. Donc, il y a beaucoup de méthodes de compression différentes. Je voudrais d'abord essayer la solution facile: allez pour gonfler / dégonfler sans conteneur (essentiellement un zip, sans zip). http://fr.wikipedia.org/wiki/deflate Le niveau de compression dépendra des données afin que je ne puisse pas dire, vous devez l'essayer vous-même.
Sinon, le moyen plus intelligent de le faire serait d'envoyer uniquement les modifications. Si vous avez accès au code côté serveur, vous pouvez simplement envoyer quelques octets du hauteur de haut niveau qui est modifié chaque seconde. Ce serait la solution idéale et si vous le souhaitez, vous pouvez même comprimer les octets modifiés avec une défloyeuse.
Deflate et Lzo valent toujours la peine d'être testés pour ce genre de chose. Ils sont normalement rapides et peuvent générer une réduction significative avec un seul appel à la bibliothèque de votre côté!
Si vous êtes assez extrêmement offshore et / ou dans des états de mer calmes, des vagues ne sont pas susceptibles d'être un gros problème. Si tel est le cas, la surface sera bien continue et ressemblera probablement beaucoup à la superposition de plusieurs vagues sinus / cosinus dans X et Y.
Les FFTS 2-D de la surface pourraient vous donner une idée. Vous pourriez être capable de représenter la surface en tant que FFT 2-D limitée à bande passante et de supprimer des données pour des fréquences spatiales plus élevées.
Je pense que pour le travail FFT, votre domaine doit être périodique, ce qui ne sera pas le cas pour les vagues océaniques en général
Premièrement, je pouvais déterminer si vous pouvez modifier le codage de base du point flottant 32 bits à une sorte de point fixe. En supposant que vos valeurs tombent tout tombent dans une plage assez spécifique (ce qui semble probable) cela pourrait bien être suffisant pour couper votre bande passante en deux. Selon la plage (et la précision) nécessaire, vous voudrez peut-être représenter une valeur exponentielle. Vous pouvez donc capturer une idée assez décente d'une large gamme de grandeurs, mais de petites différences sont principalement ignorées.
Je suppose que vous n'attendez pas (probablement) que énorme changements de hauteur d'un échantillon à l'autre, et (à une supposition), vous voyez probablement assez souvent des pentes qui continuent à travers un certain nombre de échantillons.
Si tel est le cas, une compression prédictive du delta fonctionnera probablement bien. L'idée de base est que pour chaque point (non-bord), vous prédisez la valeur de ce point en fonction des points environnants, puis de ne coder que la différence entre ce que cela prédit et la valeur réelle du point. En fonction de la quantité de précision que vous pouvez perdre, vous pourriez bien être capable de coder ce delta en un seul octet (ou peut-être même deux par octet).
Une fois que vous avez fait cela, vous pouvez envisager d'utiliser la compression de Huffman ou même la compression arithmétique, mais l'une ou l'autre va ralentir votre compression une quantité juste.
Tout d'abord, regardez vos données. Combien de morceaux d'informations dans ces flotteurs avez-vous vraiment besoin d'envoyer? Jouez avec couper les bits les moins importants et voir si c'est assez précis. Commencez ensuite avec les algorithmes de base sans perte. Compressez-la via les méthodes LZ, sans perte (LZ78, LZW, ...) Obtenez un rapport sans perte de base avec une vitesse de décompressage rapide. Ensuite, essayez Bzip et les goûts pour une méthode de compression éventuellement meilleure et une décompression plus lente. Vous avez maintenant votre limite sans perte. Maintenant, essayez des algorithmes de perte. JPEG et les goûts ont des ratios de perte convaincables et de décompresser toujours très vite. Enfin, ajoutez des filtres. Vos données se compresseraient probablement très bien avec une passe différentielle simple le long de l'axe X ou Y (ou essayez les deux et enregistrez le résultat sous forme 1 bit.) Cela devrait rendre vos données encore plus compressables.
Tout a dit, je suppose que vous pourriez avoir au moins X3 votre bande passante actuelle sans perte et x10 avec une petite perte.
Je voudrais essayer ce qui suit:
Parce que le changement de hauteur devrait être assez faible à chaque seconde, essayez d'envoyer les différences de hauteur entre 2 transferts consécutifs. Multiplier ces chiffres avec 10 ^ N, donc nous n'avons pas à les envoyer sous forme de flotteurs, mais des entiers à la place. Ensuite, utilisez le codage compressé zéro (PLZ Google pour celui-ci) qui peut réduire considérablement le nombre d'octets à envoyer de manière significative. Après cela, utilisez un algorithme de compression pour emballer ces octets.
Je penserais que cela peut être réduit d'environ 50% (à moins que les différences ne soient assez grandes pour être utilisées 3-4 octets pour chacun).
Tout d'abord: Représentation numérique
Depuis que je suppose que la plage physique de l'océan High est limitée (disons -50,0 à 50 mètres d'ondes) Si je comprends votre description correctement, le typique IEEE 754-2008 Le point flottant 32 bits (c'est-à-dire Si votre variance minimale mesurée (ou calculée) est de 1 mm, 0,001 mètres, vous pouvez réduire la taille du point flottant nécessaire à au moins 16 bits. IEEE 754 définit une valeur de point flottante 16 bits, pour des utilisations comme format d'échange. Ce qui est 5 bits pour l'exposant, 10 bits pour la fraction et 1 bit pour le signe. Je crois que cela conviendrait et réduisait immédiatement vos besoins à 128 kb / s (1024 kbps).
Après avoir écrit à l'origine, je me suis rendu compte que si vous vouliez une représentation uniforme, avec une très petite quantité d'erreur dans la représentation (<= 2 mm), puis convertissant en un entier signé de 16 bits qu'une unité C'est une représentation alternative très simple basée sur l'hypothèse de simulation selon laquelle a) la plage de valeurs valide est de +/- 65,5 mètres et que la résolution de 2 mm est acceptable pour la transmission.
secondaire: modifiant (filtrage) les données
Je ne sais pas si un Transformation de cosinus discrète (DCT), similaire Pour ce qui est utilisé dans la compression JPEG peut être utile comme une technique de compression pertes . Fondamentalement, il s'agit de quantifier les données de sorte que des valeurs voisines presque égales soient lissées de manière à pouvoir être mieux comprimées par des méthodes de compression sans perte.
Troisième: Compression sans perte traditionnelle
des techniques de compression sans perte sans perte raisonnablement rapides telles que les méthodes basées sur Lempel-ZIV (LZ, LZH, LZW, etc.) et peut-être le rapide lzo méthode. float en C / C ++) utilise 8 bits pour son exposant (portée de -126 à 127) et 23 bits pour la fraction et un bit pour le signe. Note, c'est la base 2.
< / code> représente 2 mm de hauteur physique. Pour que vous ayez une représentation uniforme avec une résolution de 2 mm, à partir de valeurs allant de -32768 (== -65536 mm ou environ -65 mètres, -200 ft) à 32767 (== 65534 mm ou d'environ 65,5 mètres).
Si je vous comprends bien, la surface est mesurée chaque seconde. Donc, si les modifications d'une seconde ne sont pas trop élevées, pourquoi ne pas traiter les données comme vidéo et essayer un algorithme de compression vidéo. La compression vidéo prend également Compensation de mouvement en compte. La compensation de mouvement est, parmi les autres parties de l'algorithme, importante pour les taux de compression vidéo élevés.
Eh bien d'abord, combien de niveaux de hauteur avez-vous besoin? Quelle est la différence maximale de la hauteur du pic d'onde à un creux? Je parie que vous pouvez le représenter avec seulement 256 ou 65536 valeurs de hauteur possibles qui réduit immédiatement vos données à 1/2 ou 1/4 sans avoir à modifier votre structure de données. Vous pouvez envoyer les valeurs min / max sous forme de floats, ainsi que chaque mise à jour, les 256 niveaux sont toujours utilisés pour obtenir le plus de précision possible ... Au fur et à mesure que la mer devient rude, vous perdez la précision.
Vous pouvez également enregistrer une image de 256x256 à l'aide d'algorithmes d'image standard. Vous n'avez pas tout à fait une coupe de bitmap Format standard pourrait le traiter comme une grisCale - si chaque sommet V est mis à l'échelle à une valeur 0-255, vous pouvez créer une couleur (V, V, V) et d'utiliser gratuitement une bibliothèque JPG. qui existe déjà. Ou vous pouvez probablement trouver un format de fichier DDS disposant d'une seule chaîne de données 8/16 / 32 bits également.
La première partie de cela que j'ai fait dans le passé, avec succès. La 2e partie, je tiens à éviter d'écrire votre propre algorithme, mais d'obtenir vos données sous une forme, elle peut utiliser des bibliothèques existantes, telles que D3DX, par exemple.
Pourquoi le vote en direct, ce serait bien d'entendre ce qui était considéré comme mauvais. Surtout que cela est une mise en œuvre de travail que j'ai utilisée dans la vie réelle.