Algortihme de compression/decompression

Version imprimable

18/12/2009, 20h03
Glycol

Algortihme de compression/decompression

Bonsoir,
Pour les besoins d'un projet je dois trouver un algorithme de compression/décompression d'image très rapide pouvant être executé sur un µcontroleur.
Le but du jeu serai de compresser une image de 320x240 pixels en 8bits/256 couleurs (3bits pour le rouge, 3 pour le vert et 2 pour le bleu) par un facteur 8 minimum (passer de 76800 octets à 9600 octets). Et ensuite car sinon ca serai trop simple je doit la décompresser ligne par ligne pour un affichage en temps réel sur un écran d'ordinateur (VGA).

Malgré les quelques recherches que j'ai fait, je n'ai pas trouvé de solution concrète pour le moment.

Les contraintes hard :
- µcontroleur 16bit de chez Microchip tournant à 40MIPS
- 16ko de RAM
- 128ko de ROM
- Un coeur DSP pouvant réaliser une instruction MAC + divers truc (post/pré incrémentation de registre, ect...) en 1 seul cycle 8-)

Contraintes soft :
- Pouvoir recompresser une partie de l'image sans avoir a decompresser l'image entiere.

Comme je l'ai dit le principale problème vient du temps de décompression en effet je dispose de 500 cycle sans problème pour décompresser une ligne. Je peux si besoin est "volé" des cycles pour monter jusqu'à 1850 cycles environ, mais la programmation va devenir très compliqué... :?

Donc si l'un de vous avais une idée pour me faire avancer n'hésitez pas à la partager.

Merci.
18/12/2009, 21h07
Mac LAK

Regarde du côté de la librairie LZO (miniLZO pour être plus précis), en effectuant une compression non pas de l'image complète (une modif = on recompresse TOUT), mais en compressant par paquets (ex : compresser par paquets de 8 lignes). Ainsi, ton image 320x240 devient un tableau de 30 (240/8) vecteurs de données compressées, et tu n'as à recompresser que les blocs touchés en cas de modifications.
Comme les données sources sont contigües en mémoire, tu n'as quasiment aucune pénalité de temps de compression par rapport à une compression totale. Côté décompression, cela demande à stocker les 8 lignes en mémoire pour ensuite les expédier vers l'affichage, mais tu auras une meilleure compression globale qu'en réduisant tes paquets à une seule ligne.
On pourrait faire plus fin en découpant en zones rectangulaires l'image, mais dans ce cas, tu n'as plus la contigüité des données pour un bloc de compression, ce qui peut devenir pénalisant (ou pas, à tester).

L'algo utilisé est de type LZW (ZIP, si tu préfères). La librairie est extrêmement rapide à la décompression (plus lente à la compression par contre), peut décompresser "in place" (= sur les données sources, donc économie d'un buffer temporaire), et possède suffisamment de variantes d'algo différentes pour que tu puisses y trouver le compromis taille/vitesse adéquat. Elle est tout particulièrement conçue pour l'embarqué et pour être économique sur son footprint. Bonus, elle est très portable.
Seul "hic" : la compression minimale requiert 8 ko de mémoire, à toi de voir si tu pourras te le permettre...

Je l'ai utilisée avec succès sur des CPU 386 à 33 MHz, pour des données texte et images, sans impact visible sur les performances. Au contraire, ça allait même plus vite que sans compression à cause de la lenteur des accès à la Flash où étaient stockées les données compressées.

Si tes taux de compression ne sont pas très bons avec tes pixels compactés, il faudra envisager alors une séparation de l'image en composantes R/V/B et tester la compression de chaque plan de couleur séparément, de façon à avoir plus de chances de trouver des éléments compressibles.

Si tout ça ne passe pas dans tes contraintes, il faudra voir à utiliser ton DSP : cela peut demander beaucoup plus de réflexion, ainsi bien sûr que la liste exhaustive des capacités du circuit.
19/12/2009, 08h16
Glycol

Merci pour cette reponse trés complète, je vais faire des testes pour voir si les timing sont bon. Je vous tiens au courant.
19/12/2009, 16h43
Glycol

J'ai fais quelques testes en compressant des lignes entières (320 octets), résultats :

14 oct. (4.3%) pour une ligne monochromatique,
139 oct. (43.4%) pour une ligne avec peu de détail et 30 couleurs différentes,
279 oct. (87.2%) pour une ligne de couleurs aléatoires.

Bon j'ai pas poussé plus loin car cette méthode me pose deux problèmes, le premier c'est que pour obtenir le taux de compression minimum (12.5%) je doit avoir une images avec très peu de détails ou beaucoup de répétition (si j'ai bien compris le principe de la compression LZW). Le deuxième c'est que la taille de la chaine en sortie n'est pas constante, et avec des taux de compression aussi haut, je risque de manquer de mémoire pour stocker l'image entière.

Mais ca reste une lib intéressante et trés rapide... :ccool:

Après ces testes je me demande :
Est ce qu'une techniques de compression d'images avec pertes ne serait pas plus efficaces ? Et si oui laquel utilisé (DCT, ondelettes, ...) ?

Merci.
19/12/2009, 17h37
Matthieu Brucher

Déjà il faut que tu saches que tu n'auras jamais sur toutes les images une compression de 8 pour 1. C'est impossible. Maintenant, tu peux partir sur des technologies destructrices, c'est à toi de voir. DCT (jpeg) ou ondelettes (JPEG200) nécessitent tous deux phases de décompression : décompression du flux (Huffman) et ensuite la DCT ou l'ondelette inverse (ça peut être costaud car il existe plusieurs bases à avoir en mémoire).
21/12/2009, 09h56
Glycol

Bon j'ai regardé en profondeur la compression par ondelette, et j'ai du mal a comprendre comment choisir la matrice de quantification pour obtenir un résultat correct. J'ai cru comprendre que pour un résultat optimal, elle devait être générer lors de la compression, mais est-ce qu'il n'existe pas une sorte de matrice "de base" pour obtenir un résultat convenable ?
21/12/2009, 10h07
Matthieu Brucher

Tu peux prendre la première ondelette, mais comme tu l'as dit, tu pourras avoir des images générées avec d'autres ondelettes si tu autorises l'utilisation d'images que tu n'as pas faites.
21/12/2009, 10h13
Mac LAK

Citation:

Envoyé par Glycol

J'ai fais quelques testes en compressant des lignes entières (320 octets), résultats :

D'où ce que je te disais : prendre un bloc plus important pour obtenir de meilleurs taux de compression.
Typiquement, les algos de type LZ fonctionne (relativement) mal avec des données de très petite taille, et ce ne sont pas les seuls d'ailleurs.

As-tu essayé en séparant les 3 plans de couleur, également ? Quitte à faire des tests, autant les pousser un peu afin d'avoir réellement toutes les billes en main...

Citation:

Envoyé par Glycol

le premier c'est que pour obtenir le taux de compression minimum (12.5%) je doit avoir une images avec très peu de détails ou beaucoup de répétition (si j'ai bien compris le principe de la compression LZW).

Les répétitions n'ont pas besoin d'être contigües, c'est l'avantage par rapport à un algo de type RLE.
Pour augmenter le niveau de redondance des données, tu peux notamment séparer ton image en trois plans de couleurs.

Citation:

Envoyé par Glycol

Le deuxième c'est que la taille de la chaine en sortie n'est pas constante, et avec des taux de compression aussi haut, je risque de manquer de mémoire pour stocker l'image entière.

Ta sortie ne sera JAMAIS de taille constante... De plus, quel que soit l'algorithme de compression non-destructif, tu auras TOUJOURS des données qui sont soit incompressibles, soit des données pour lesquelles la compression augmentera (!) la taille des données... Et c'est démontrable mathématiquement, en plus.
Il faut surtout regarder le taux moyen de compression, et non pas un taux individuel sur UN test.

Citation:

Envoyé par Glycol

Est ce qu'une techniques de compression d'images avec pertes ne serait pas plus efficaces ? Et si oui laquel utilisé (DCT, ondelettes, ...) ?

Le souci d'un algo destructif, c'est qu'il est souvent très lent à l'exécution sans assistance hardware... Dans ton cas, pour du JPEG par exemple, il va falloir transformer l'espace de couleur, effectuer une FFT, une discrétisation puis un codage de Huffman. Tout ça coûte beaucoup de temps CPU et de mémoire.
C'est pour cela que je ne saurais trop t'encourager à pousser un peu plus tes tests avec LZO avant de t'engager dans cette voie.
De plus, tes images source ont déjà bien peu de détails : 256 couleurs maximum (parmi 256, ça réduit beaucoup l'espace de couleur...) et en "seulement" 320x240. Les pertes sur de telles images risquent d'être assez violentes.