\articolo{Compressione di immagini e suoni}{Giuseppe Ligorio} \noindent La compressione dati svolge un ruolo molto importante nella memorizzazione delle informazioni; infatti, il consumo di memoria è sempre un problema rilevante, per cui si cerca di realizzare algoritmi sempre più potenti e veloci che consentano migliori prestazioni; naturalmente questa necessità si fa ancora più presente nel caso di immagini, animazioni e suoni, in quanto i dati relativi occupano un grande quantitativo di memoria. \paragrafo{Compressione di immagini} Esistono numerosi formati distinti per la memorizzazione di immagini. I più semplici sono l'ILBM e il PCX, che implementano il \emph{Run Length Encoding}: questo semplice algoritmo di compressione sostituisce le ripetizioni consecutive di un byte con una coppia $\langle\text{byte},\text{numero di ripetizioni}\rangle$. Questa compressione risulta accettabile in caso di immagini a pseudo-codifica (non in true color). Un altro formato molto famoso è il GIF (\emph{CompuServe Graphics Interchange Format}), che utilizza come algoritmo di compressione il \emph{Lempel Zivel Welch} (LZW). In questo caso la compressione si basa sulla presenza di ripetizioni di catene di byte. L'algoritmo LZW è sicuramente più efficiente del Run Length Encoding e l'implementazione mantiene comunque una buona velocità, tanto che è utilizzato anche per la compressione di dati generici (come in LhArc ad esempio). Il formato successivo che illustreremo è senz'altro quello che ha rivoluzionato la compressione delle immagini: il JPEG (\emph{Joint Photographic Expert Group}). Questo formato prevede il passaggio dal domino temporale (o spaziale nel caso delle immagini) a quello delle frequenze, mediante la cosiddetta trasformata ``dei coseni'', versione ``ridotta'' di quella di Fourier. Dopo la trasformazione l'immagine viene compressa secondo l'algoritmo di Huffman, che sostituisce le parole a lunghezza fissa del segnale con dati a lunghezza variabile. La codifica viene generata mediante un albero binario che permette di assegnare lunghezze minori a quei simboli che si presentano con frequenza maggiore. \paragrafo{Compressione di animazioni} Per le animazioni i formati presenti non sono molti; quello principalmente utilizzato su \A è l'ANIM inventato con Deluxe Paint III. Questo formato prevede la compressione con Run Length Encoding per ogni immagine dell'animazione, ma tiene conto anche delle variazioni tra un frame e il successivo. Un altro formato, sicuramente il più potente mai realizzato, è l'MPEG (\emph{Motion Photographic Expert Group}), estensione naturale del JPEG. Questo formato prevede anche la memorizzazione di audio digitale stereofonico a 16 bit per la riproduzione perfetta di filmati in digitale, e consente di memorizzare 60 minuti di audio e video in un CD (circa 600\,Mbyte di memoria). \paragrafo{Compressione di suoni} Anche per i suoni i formati progettati sono pochi; quello utilizzato prevalentemente su \A è l'8SVX che non prevedeva alla sua nascita alcun algoritmo di compressione. Un algoritmo di compressione molto utilizzato per i segnali sonori è la compressione Delta, che consiste nel considerare le differenze (i delta appunto) tra un campione e quello precedente; dato che si presuppone che non ci sia una variazione notevole tra un campione e il successivo, questi valori non risultano essere molto elevati per cui possono essere rappresentati con un numero inferiore di bit. Naturalmente per ottenere una buona compressione occorre forzare i limiti di variazione introducendo un certo errore. L'algoritmo Delta-Fibonacci, utilizzato negli attuali 8SVX, si avvicina molto a quello Delta; anche in questo algoritmo vengono considerati i delta tra un campione e il precedente, ma sono utilizzabili solo i valori presenti in una tabella di 16 elementi (8 negativi ed 8 positivi) che seguono la successione di Fibonacci ($-$34, $-$21, $-$13, $-$8, $-$5, $-$3, $-$2, $-$1, 0, 1, 2, 3, 5, 8, 13, 21). Memorizzando con quattro bit la posizione del delta che più si avvicina a quello reale si ha una compressione di circa il 50\%, con la possibilità di coprire una ampiezza maggiore rispetto al puro metodo Delta. Entrambi gli algoritmi introducono un errore non indifferente, che si traduce in un abbassamento della qualità dinamica. Anche per i suoni si potrebbe applicare l'equivalente del JPEG ottenendo rapporti di compressione impressionanti anche se al prezzo di tempi molto lunghi per la compressione/decompressione. \paragrafo{Compressione di Huffman e varianti} L'algoritmo che vorrei a questo punto presentare consiste in una variante alla codifica di Huffman; questo algoritmo è stato sviluppato per la compressione di immagini in pseudo-codifica (non true-color) già compresse con il Run Length Encoding (utilizzato di default in IFF ILBM o altri formati quali il PCX); prima di procedere risulta quindi doverosa un'introduzione al funzionamento della compressione di Huffman. La codifica di Huffman consiste principalmente nell'utilizzo di codici a lunghezza variabile che sostituiscono sequenze di lunghezza fissa. La prima fase della codifica consiste nel calcolo delle frequenze dei diversi simboli contenuti nel file da comprimere. Tramite un particolare procedimento viene costruito un albero binario di codifica/decodifica. La decompressione consiste nel discendere dalla radice dell'albero lungo il rami sinistro o destro di un nodo a seconda che il bit prelevato dal file compresso valga 0 o 1. Il raggiungimento di una foglia indica il termine della decompressione di un simbolo, che è memorizzato dentro tale nodo. L'implementazione dell'algoritmo prevede l'uso di una tabella che rappresenta l'albero, e che deve essere memorizzata insieme ai dati compressi per consentirne la decodifica. La costruzione dell'albero assegna i simboli più frequenti alle foglie dell'albero meno distanti dalla radice. L'algoritmo funziona bene per file di testo, in cui sono presenti solo una parte dei codici possibili (i caratteri realmente utilizzati saranno circa 80 sui possibili 256), ma ha una buona resa anche nel caso in cui tutti i 256 simboli siano presenti, a patto che alcuni di essi abbiano una frequenza nettamente superiore agli altri. Questo è proprio il caso che si presenta per le immagini in pseudo-codifica: normalmente infatti tutti o quasi i 256 simboli sono presenti, ma molti di essi si ripetono una o due volte mentre solo alcuni possono ripetersi molte volte, e comunque con una frequenza considerevole rispetto agli altri. Se l'immagine viene compressa con il Run Length Encoding, come normalmente accade nei file IFF ILBM, un successivo tentativo di compressione con l'algoritmo di Huffman non produce risultati molto buoni La variante da me realizzata consiste in una codifica mista a lunghezza variabile e fissa, particolarmente adatta all'applicazione nei casi in cui non vi siano predominanze di alte frequenze di simboli (come nel caso di immagini compresse con il Run Length Encoding). Il principale problema del caso prima visto consiste non solo nel fatto che i codici con bassa frequenza possono essere codificati con lunghezza fino ai 14-16 bit, ma il fatto di codificare tutti i 256 simboli (o quelli presenti) implica la realizzazione di un albero che costringe anche i simboli a frequenza maggiore ad avere una codifica molto lunga (anche se inferiore ad 8 bit); la variante prevede di costruire l'albero (comprimendo con codici a lunghezza variabile) solo per i simboli a frequenza alta; ciò richiede l'uso di un bit aggiuntivo per indicare se il codice è a lunghezza variabile o fissa. Questo algoritmo raggiunge livelli di compressione molto vicini a quelli realizzati con gli algoritmi di LhArc; questo è già un bel successo dato che l'algoritmo applica un solo tipo di compressione, mentre LhArc (come altri compressori come PKZip o ArJ) applicano una serie di diversi algoritmi per ottenere la compressione migliore, con inevitabile rallentamento della codifica e decodifica. L'algoritmo inoltre brilla nella velocità di decompressione; infatti per la sua struttura si presta a una particolare ottimizzazione. Dato che l'albero di decodifica possiede un numero limitato di simboli, non capita mai che la lunghezza dei codici compressi raggiunga 8 bit (infatti in tal caso sarebbe conveniente memorizzare il simbolo direttamente in quanto lo spazio occupato è identico), per cui si può costruire una tabella di 256 byte e utilizzando il codice come i bit più significativi di un byte (8 bit) vengono fatti variare in tutte le possibili combinazioni i bit restanti; i valori così calcolati vengono utilizzati come indici del vettore e in quelle posizioni viene memorizzato il byte decodificato; in questa maniera, nella fase di decompressione, vengono comunque presi i primi 8 bit (senza preoccuparsi della lunghezza del codice) e utilizzando questo valore come indice della tabella viene prelevato direttamente il codice decodificato; in tal modo si evita il procedimento di percorrimento dell'albero che comporta un costo in termini di tempo, notevolmente maggiore; allo stesso modo viene preparata una seconda tabella contenente la lunghezza del codice, in modo da conoscere quanti bit saltare del codice in ingresso. Per questo la decompressione richiede un tempo molto ristretto (dipende sempre naturalmente dal processore e dalla lunghezza del file) e sicuramente molto inferiore a quello impiegato anche dal più ottimizzato LhArc. \begin{thebibliography}{10} \bibitem{Ia} Ifeachor Jervis. \emph{Digital Signal Processing: A Practical Approach}. Addison-Wesley. \bibitem{IIa}William B. Pennebaker, Joan L. Mitchel. \emph{JPEG Still image data compression standard}. Van Nostrand Reinhold. \bibitem{IIIa} James A. Storer. \emph{Image and text compression}. Kluwer Academic Publishers. \bibitem{IVa} V. Cappellini. \emph{Data Compression and Error Control Techniques with Application}. Academic Press. \bibitem{Va} C.A. Andrews, G.R. Schwartz. \emph{Adaptive data compression}. Proc.~IEEE. \bibitem{VIa} G. Benelli, V. Cappellini, F. Lotti. \emph{Data compression techniques and applications}. Radio Electron. \bibitem{VIIa}Allen Gersho, Robert M. Gray. \emph{Vector Quantization and Signal Compression}. Kluwer Academic Publishers. \bibitem{VIIIa} A. Jacquin. \emph{A Fractal Theory of Iterated Markov Operators with Application to Digital Image Coding}. Georgia Institute of Technology. \bibitem{IXa} R.D. Boss, E.W. Jacobs, Y. Fisher. \emph{Fractal Image Compression Via Adaptive Image Partitioning}. \bibitem{Xa} M. Rabbani, P.W. Jones. \emph{Digital Image Compression Techniques}. SPIE Optical Engineering Press. \end{thebibliography} \autore{% Giuseppe Ligorio \\ Via Valeggio 15 \\ I-10128 Torino TO \\ Tel.:~(011)9494530}{} \citazione{\selectlanguage{english}% Declare foo as pointer to function returning pointer to function returning pointer to array 3 of pointer to function returning pointer to array 4 of array 2 of pointer to pointer to function returning pointer to array 5 of pointer to pointer to char\\ \mbox{\upshape{\c{\scriptsize char **(*(**(*(*(*(*(*foo)())())[3])())[4][2])())[5]}}}\\ To turn the above into a cast, remove the name \upshape{\c{foo}} and add \upshape{\c{()}}:\\ \mbox{\upshape{\c{\scriptsize (char **(*(**(*(*(*(*(*)())())[3])())[4][2])())[5])}}}}{}