Note sulla compressione di immagini |
 |
|
|
|
I dati generati da un sistema di acquisizione di immagini derivano dal campionamento spaziale di una rappresentazione bidimensionale della scena di interesse, seguito da quantizzazione dei corrispondenti livelli analogici di intensità luminosa. Il passo di campionamento viene di norma scelto sufficientemente piccolo da non richiedere alcuna interpolazione in fase di visualizzazione, e viene in ogni caso correlato alle capacità di integrazione del sistema visivo umano. Un'immagine digitale diventa così una matrice MxN di numeri interi (detti pixel), la cui rappresentazione completa, se B è il numero di bit per pixel, richiede MNB bit. Generalmente, questa forma canonica richiede un enorme numero di bit per la sua rappresentazione: ad esempio, un'immagine da 512x512 pixel con 8 bit per pixel, richiede più di 2 · 106 bit; se l'immagine di interesse è a colori, anziché a livelli di grigio, tale numero va moltiplicato almeno per 3, tante quante sono le componenti cromatiche dell'immagine.
L'obiettivo della compressione delle immagini è quello di ridurre quanto più possibile il numero di bit necessari per la rappresentazione e la ricostruzione di un duplicato identico (o quanto meno fedele) dell'immagine originale. La compressione che consente di recuperare esattamente i dati originali viene detta senza perdite (lossless), in contrapposizione alle tecniche con perdita (lossy) che permettono di riottenere solo copie approssimativamente identiche all'originale (Netravali & Limb, 1980; Jain, 1981). Nonostante la diversità dei risultati e dei processi richiesti per conseguirli, entrambe le tecniche si basano sul fatto che i dati generati da un'immagine reale non possono essere considerati casuali: campioni adiacenti hanno difatti valori di intensità simili, e vi si possono trovare significative ed importanti correlazioni spaziali; è chiaro che, se tali correlazioni vengono esaltate in modo appropriato, il numero totale di bit può essere drasticamente ridotto. In accordo con la teoria dell'informazione, i dati-immagine vengono dunque convertiti in sequenze di messaggi, le quali a loro volta vengono compresse assegnando loro dei codici di lunghezza tanto minore quanto maggiore è la loro probabilità di apparizione (cioè quanto minore è l'informazione da essi trasportata). È altresì facilmente intuibile che le tecniche lossy consentono fattori di compressione difficilmente raggiungibili con le tecniche lossless a parità di complessità computazionale, ed è questa la ragione per cui le tecniche lossless sono scarsamente utilizzate in pratica.
La classe di tecniche lossy più comunemente usata è quella della codifica per trasformate (transform coding). Tale metodo consiste essenzialmente nel trasformare l'insieme di pixel in un altro insieme di coefficienti che presenti una correlazione minore, e che possa dunque essere codificato in maniera più efficiente. L'immagine originale può essere recuperata, dopo opportuna decodifica dei coefficienti in questione, mediante trasformazione inversa. Le trasformazioni più comunemente usate sono di tipo lineare, per via della piena comprensione matematica che si ha del loro comportamento e delle loro peculiarità; tra le trasformazioni lineari possibili, quella ottimale sotto l'aspetto teorico è la trasformata di Karhunen-Loève, che tuttavia per la sua estrema complessità computazionale non viene quasi mai usata in pratica; ad essa si preferisce invece la trasformata di Fourier o, più generalmente, la trasformata coseno che, pur essendo sub-ottimali sotto l'aspetto della capacità di decorrelazione, possono tuttavia essere implementate mediante algoritmi veloci (fast transforms).
Le tecniche di codifica a trasformata (a cui appartiene, ad esempio, la classe nota come JPEG, da Joint Photographic Expert Group, nome della commissione che ne ha definito gli standard) sono dunque per lo più basate sulla trasformata coseno. Al fine di ricondurre entro limiti ragionevoli i tempi di calcolo, l'immagine viene suddivisa in blocchi (generalmente da 8x8 o 16x16 pixel), per ciascuno dei quali viene calcolata la trasformata coseno discreta (Discrete Cosine Transform, DCT) e da questa isolati i coefficienti maggiormente significativi sotto l'aspetto del contenuto informativo; le sequenze di coefficienti così ottenute vengono quindi sottoposte a codifica senza perdite, solitamente di tipo entropico (Huffman coding) o aritmetico (arithmetic coding). La fedeltà dell'immagine recuperata mediante il processo inverso di decompressione può essere controllata semplicemente agendo sulla quantità di coefficienti mantenuti nella codifica, a scapito ovviamente dell'efficienza della compressione stessa. Un inconveniente delle tecniche DCT standard basate sulla divisione in blocchi, solitamente poco sentito ma che in determinate applicazioni può anche essere oltremodo fastidioso, è quello del cosiddetto blocking effect, che nell'immagine ricostruita si riflette nella presenza di variazioni brusche di luminanza e/o di crominanza in corrispondenza ai bordi dei blocchi in cui l'immagine originale era stata suddivisa. Il blocking effect può essere eliminato, o comunque ridotto fino ad essere pressoché inavvertibile, mediante post-elaborazione dell'immagine ricostruita con l'applicazione di opportuni filtri digitali di correzione (Reeve & Lim, 1983): un filtro di correzione opportunamente progettato consente di eliminare la quasi totalità del blocking effect, influenzando nel contempo in maniera pressoché inavvertibile i tempi totali di elaborazione. Metodi più complessi per l'eliminazione del blocking effect hanno anche preso in considerazione la possibilità di suddividere l'immagine in blocchi parzialmente sovrapposti anziché disgiunti come di norma (Pearson & Whybray, 1983).
L'insieme di tecniche basate sulla visione "classica" (legata cioè alla teoria dell'informazione) del problema della codifica delle immagini viene detto di prima generazione. Ora, generalmente l'entropia della sorgente dei dati-immagine non è nota, e dipende in ogni caso in maniera essenziale dal modello matematico utilizzato; di conseguenza, non è possibile raggiungere i limiti di efficienza di compressione teoricamente prevedibili in base alla teoria dell'informazione. Una seconda classe di tecniche, che tendono ad abbandonare questa impostazione del problema e tentano di adattare il problema della codifica a quelle che sono le caratteristiche intrinseche del sistema visivo umano, sono dette di seconda generazione (Musmann et al., 1985; Kunt et al., 1985). L'immagine viene partizionata in una serie di regioni, ognuna dotata di caratteristiche peculiari, separate tra di loro da contorni, in modo che tali regioni coincidano il più fedelmente possibile con gli oggetti presenti nella scena di interesse. La maggiore efficienza di compressione che ne può conseguire deriva sia dall'esistenza di metodi molto efficienti per la codifica dei contorni, sia dal fatto che le regioni all'interno dei contorni hanno in generale un contenuto informativo molto basso e possono quindi essere rappresentate da un numero relativamente basso di bit. L'inconveniente principale di tali tecniche risiede tuttavia nella loro enorme complessità computazionale, che risulta per di più legata in maniera essenziale al contenuto informativo dell'immagine.
In tempi recenti è stata sviluppata una nuova tecnica di compressione, detta compressione frattale. La teoria dei frattali, introdotta da Mandelbrot (1982), parte dall'osservazione che esistono in natura — come pure possono essere definite e create matematicamente — delle strutture autosomiglianti, nel senso che presentano caratteristiche pressoché identiche a qualunque livello di dettaglio vengano ingrandite. Certe classi di frattali geometrici possono essere facilmente costruite mediante l'uso di due soli enti matematici detti rispettivamente iniziatore e generatore: l'iniziatore fornisce la struttura grossolana della forma dell'oggetto frattale, mentre il generatore fornisce informazioni sui suoi dettagli. La costruzione di un frattale consiste allora nell'applicazione ripetuta del generatore all'iniziatore, con corrispondente cambiamento di scala ad ogni applicazione: il risultato finale di tale iterazione è appunto un frattale geometrico. Questi concetti sono stati applicati all'ingegneria, ed in particolare all'elaborazione di segnali e alla compressione di immagini, da Barnsley (1988).
La compressione frattale di immagini si basa sull'osservazione secondo cui gli oggetti frattali deterministici posseggono la proprietà intrinseca di presentare complessità visuali estremamente elevate, pur avendo contenuto informativo estremamente basso — potendo cioè essere descritti e generati mediante algoritmi deterministici ricorsivi estremamente semplici (Mandelbrot, 1982), producendo via via copie di se stessi o di porzioni di se stessi a vari fattori di scala. La compressione frattale di un'immagine allora consiste essenzialmente nel ricercare per l'intera immagine (o per ciascun blocco in cui l'immagine può essere suddivisa) l'oggetto frattale che meglio si attaglia ad approssimarne il contenuto informativo dopo successive iterazioni, e nel codificare infine la descrizione dell'oggetto associato all'immagine o a ciascun blocco (Jacquin, 1993). La ricerca dell'oggetto frattale ottimale ha molti punti in comune con le procedure di quantizzazione vettoriale (Abut, 1990), anche se se ne differenzia in molti altri — ad esempio, non necessita di dizionari (codebooks) precostituiti. È chiaro tuttavia che l'analisi dell'immagine per la determinazione degli oggetti frattali elementari e delle relative trasformazioni da associare a ciascun blocco costituisce un task computazionale formidabile, superiore di ordini di grandezza a quelli comunemente richiesti dalla compressione per trasformate (Jacobs et al., 1992), né è ancora chiaro se e in che misura la maggiore efficienza di compressione che ne può in teoria derivare sia legata ai requisiti computazionali.
Il problema del confronto tra le tecniche di compressione frattale e le tecniche tradizionali a trasformata o a quantizzazione vettoriale è stato affrontato in diversi studi. Øien et al. (1992) suggeriscono di codificare le regioni "complesse" di un'immagine con una compressione frattale a blocchi e le regioni "semplici" con una compressione a trasformata, anche se non danno alcuna indicazione conclusiva della precisione con cui le regioni complesse vengono approssimate in fase di ricostruzione. Laurençot e Jacquin (1992) riferiscono che la compressione frattale dà risultati lievemente migliori della quantizzazione vettoriale quando applicata a scene con bordi molto netti, ma abbastanza simili e in molti casi peggiori quando applicata ad oggetti comprendenti vaste aree strutturate. Jacobs et al. (1992), infine, mostrano come la loro migliore implementazione della compressione frattale a blocchi abbia prestazioni comparabili, ma comunque mai migliori, della compressione con DCT adattativa, sia sotto l'aspetto dell'efficienza di compressione sia sotto quello della fedeltà di ricostruzione.
Sembra dunque possibile concludere che, nonostante l'indiscutibile novità della compressione frattale di immagini e delle teorie che ne stanno alla base, e in assenza di rapporti affidabili e definitivi sulle sue effettive prestazioni misurate su estensivi database di immagini, gli elevatissimi carichi computazionali da una parte e l'incerta caratterizzazione in termini di fedeltà di ricostruzione rappresentino una contropartita ancora inaccettabile ai favorevoli rapporti di compressione che pure sembra possibile ottenere da essa, e suggeriscano per il momento — almeno nell'ambito di applicazioni critiche — il ricorso alle tecniche più tradizionali di compressione, come le codifiche a trasformata eventualmente integrate da alcuni degli accorgimenti a suo tempo citati.
|
|||||||
© 1997-2003 Paolo Marincola (Rome, Italy)
e-mail: pmaNOSPAM@acm.org (eliminare
i caratteri "NOSPAM" per ottenere l'indirizzo esatto)
Commenti, osservazioni e suggerimenti sono estremamente graditi.
Last revised: 2003-12-06 19:36