Compressione lossy di immagini n. 3

Leonardo Maffi - 9 Feb. '99

16 Gen '99

Livelli di compressione

Spesso un compressore di immagini non viene usato con un continuum di tassi di compressione, ma con solo tre livelli. Essi sono definiti perchè rispecchiano esigenze diverse:

Compressione lossless. Utile durante i lavori su una immagine, o per conservare dati esatti. Conviene usare Png, formati proprietari dei programmi grafici, o formati particolari come Bmf e Imstar Minerva.
Near lossless percettivo (Nlp): anche ingrandita e confrontata con l'originale l'immagine pare avere tutti i pixel al loro posto o quasi. Spesso è il modo in cui si conservano le immagini di dimensioni comuni. Di solito si usa sempre il formato Jpeg.
Massima compressione: l'importante è avere un file più piccolo possibile. Si accetta che l'immagine sembri differente dall'originale, purchè ovviamente contenega la stessa informazione (eccetto nei minimi dettagli).

Ritengo che ai fini pratici il formato Bmf si avvicini a sufficienza alla massima compressione entropica di immagini fotografiche truecolor.
Per il near-lossless percettivo il formato Jpeg è solitamente accettabile, in attesa di futuri standard migliori.
Per i massimi tassi di compressione può essere usato il Jpeg, ma esso mostra i propri limiti. Altri formati, come quelli basati su wavelet sembrano comportarsi meglio. Ma ancora non ho trovato un formato veramente adatto. Senza contare del fatto che non esiste nessuno standard. A questi livelli i compressori come il Jpeg riducono l'immagine ad un mucchio di blocchi, e i metodi basati su wavelet fanno un lavoro quasi decente, producendo una immagine sfuocata, la più simile possibile a quella originale. Io ritengo invece che a questi data rate si dovrebbe accettare che l'immagine risultante sia visibilmente differente dall'originale, pur contendendo gran parte dell'informazione visiva, eccettuati i dettagli minimi.

Compressione lossy WIF

Una casa software Compression Engines Inc., produce un software freeware, per privati, omonimo alla ditta, che comprime-decomprime immagini nel formato lossy proprietario Wif, utilizzabile dove lo è il Jpeg. Questo formato utilizza la wavelet. Ecco alcune prove:


Bird Originale 256x256 1 byte/pixel 65536 byte Raw, 35361 byte Png 28404 byte Bmf.	Bird compresso con Wif con Param=255, poi decompresso e ricompresso il Jpeg Nlp. Wif: 15.34 pixel/bit 0.0651 bit/pixel, 534 byte. (Jpeg mostrata 5365 byte)	Byte dell'immagine precedente. (l'immagine punta al file Wif originale)

Altro esempio, confrontato col Jpeg. Ho usato il miglior formato di Jpeg disponibile: ho usato la compressione adattiva del Jpeg Optimizer, poi ho tolto commenti inutili dal file e poi l'ho compresso entropicamente in maniera migliore con l'Acb. Il file Wif l'ho confrontato con l'immagine Jpeg ricostruita con Minerva.

Volpe in Jpeg near lossless percettivo Volpe Jpeg a compressione eccessiva

Volpe Primavera, 512x512x24M 786'432 byte Raw
278'704 byte Bmf (35.43%)
35'849 byte questa Jpeg (4.558%) Compressa col Jpeg Optimizer v. 3.01 con comando MagiCompress,
=> 2900 byte. Con PicPress tolti commenti e altri dati inutili => 2856 byte.
(Compressa poi con Acb => 2177 byte).

Immagine Jpeg-Acb da 2177 byte ricostruita col PicPress (o Minerva),
(poi ricompressa in Jpeg a 13189 byte) Compressa in Wif con param=246, a 2174 byte,
non comprimibili entropicamente. (L'immagine punta il file Wif).

Nonostante il Jpeg sia al meglio delle sue possibilità (o quasi, sarebbe servita la compressione aritmetica) si deve ammettere che a questi data rate il Wif è leggermente migliore. Questa differenza è leggera, ma è consistente per tutte le immagini che ho provato, ed è quindi un ottimo risultato. E' la prima volta che posso utilizzare un formato grafico più efficiente del Jpeg.
Nell'immagine della volpe, in confronto alla jpeg, la Wif ha più dettagli, sia cromatici che spaziali, e inoltre non ha le blocchettature che Minerva mette nelle zone che non contengono solo la componenete continua (DC) della traformata coseno (DCT 8x8); decisamente occorrono metodi migliori di quello del Minerva per ricostruire le Jpeg.
Comprimere-decomprimere una immagine col Wif a basso tasso (~ 25-45) è un buon modo per farne un filetraggio antirumore.
In fatto di velocità il Wif è paragonabile al jpeg, quindi molto rapido.
Wif è migliore del jpeg soprattutto ai tassi di compressione più alti.
Per questo formato non esistono programmi per compressione variabile a zone e per scelta interattiva di fattore di compressione, però la dimensione dell'immagine finale è molto più modulabile del jpeg.
Il Wif è un formato grafico proprietario. La standardizzazione è quasi indispensabile per formati lossy di dati, perchè coi lossless si può sempre almeno ricostruirli usando la procedura originale; se sono in formati lossy i dati sono comunque perduti e la conversione in altri formati lossless standard, se possibile, non fa che peggiorare i dati.
Conclusioni sul Wif: comprime leggermente di più del jpeg, ma non conviene usarlo per motivi di standardizzazione.

Wavelet & Jpeg 2000

Attualmente i tre metodi migliori per la compressione lossy di immagini fotografiche (dette a tono continuo) sono basati sulla trasformata coseno (Jpeg), Wavelet (ad esempio Wif, Wi, o Pic Minerva), e trasformata frattale (ad esempio il formato Fif della Iterated systems).
In base alle prove fatte finora mi sembra che la compressione frattale sia molto più lenta e leggermente meno efficiente del Jpeg. Quindi in ordine di efficienza crescente: frattali, DCT e wavelet. Ma perchè nonostante i metodi siano differenti i risultati sono molto vicini? Probabilmente ne esistono molti altri peggiori, ma i migliori sono allineati. Possibili risposte che ho trovato:

Questo è lo stato dell'arte, che è quindi generale. Finora non è stato trovata nessuna idea radicamente migliore.
Per motivi intrinseci alle immagini: quella è l'entropia delle immagini.
Quella è l'entropia delle immagini per quel tipo di scorrelazione, basata sulle frequenze spaziali, su dettagli via via più grandi nelle immagini (ad esempio Dct e Wavelet sono approssimazioni della trasformata Karhunen-Loeve ottimale).

Presto sarà reso disponibile un nuovo formato grafico lossless, detto Jpeg2000 o J2K. Non è radicalmente migliore del jpeg, specialmente a tassi di compressione Nlp, e quindi è forse prematuro. Penso sarebbe stato meglio aspettare un avanzamento naturale della ricerca, invece che forzare l'uscita di un nuovo standard. Il Jpeg ha dei difetti, ma mi immagino che molti preferiranno continuare ad usarlo ancora per parecchio.
J2k è basato sulla wavelet e raccoglie in sè tutte le migliori idee trovate in questi anni. Pare che sia già disponibile un decompressore scritto in Java e vari file di esempio.
Vedi http://ltswww.epfl.ch/~neximage/index.html .

Quello che segue è tratto da un articolo in postscipt: Embedded Wavelet Image Compression Based on a Joint Probability Model, Eero P. Simoncelli, Robert W. Buccigrossi.

Figure. Relative rate-distortion tradeoff for four image coders (JPEG, EZW, EPWIC-1, and EPWIC-2). Left: PSNR values (in dB), relative to EPWIC-1 (dotted horizontal line), as a function of the number of encoded bytes. Right: Number of bytes necessary to achieve a given PSNR, relative to EPWIC-1 (dotted horizontal line). All curves are averages over the set of 13 images (of size 512x512) in our collection.

EWIC-1 outperforms EZW for most compression ratios by about 0.3dB, and EPWIC-2 outperforms EZW by 0.5dB at 1Kbyte, and nearly 1.5dB at 16Kbytes and above. Also shown in figure is the encoding size (relative to that of EWIC-1) as a function of target PSNR. This gives a sense of how long one would wait during a progressive transmission for an image of a given quality. For example, EZW would have a transmission time roughly 30% higher than EPWIC-2 for an image quality of 25dB.

Aggiunta del 21 Gen. '99

Il formato Wif comprime di più del Jpeg le zone dell'immagine con altre frequenze a basso contrasto. Ciò non è un difetto nè un pregio, ma entro certi limiti solo una scelta progettuale. Ovviamente fuori di questi limiti si nota un degrado non bilanciato in qualche caratteristica dell'immagine.
Questo è vero se i byte risparmiati dal Wif in quelle zone sono utilizzati in altre. Ma se appare che queste altre zone sono in condizioni peggiori o uguali al jpeg allora possiamo dire che il compressore è peggiore del Jpeg.
In un articolo ho trovato una immagine B/N ottima per fare altri confronti.


Case 378x250 8b/pixel, 94'500 byte Raw, 71'124 byte Png (PSP5), 66'108 byte Bmf	In Jpeg ad alta compressione, ~1 b/pixel 11'744 byte Jpeg Wgo, Progressivo

Questa immagine presenta una sfida per un compressore per vari motivi: ha una entropia molto alta, pur avendo poco rumore, ha un mucchio di dettagli ad alta frequenza ben visibili, e alcuni quasi alla massima, sul tetto della casa centrale. Inoltre ha una zona a basso contrasto, ma con alcuni dettagli (lo sfondo) e una zona a luminosità molto alta vicina ad una a bassa luminosità (al centro dell'immagine). Ci sono molti dettagli come la lanterna appesa sulla strada, la A di Alfred a basso contrasto, il filo che regge la lanterna, e sotto i cornicioni i punti chiari regolari costituiti dalle estremità delle assi dei tetti.

Ho compresso questa immagine a circa 1 b/pixel anche in wif: Case116_0107_19990121.wif (zippato per poterlo caricare su questo sito).
(Param=116, 11'792 byte). Sia la Jpeg che la Wif non sono riuscito a comprimerle entropicamente ulteriolmente.

Di seguito ecco qualche dettaglio ingrandito per confronto. Nonostante le tassellature vedo che soggettivamente Jpeg ha fatto un lavoro migliore.


Originale	Jpeg	Wif

Il seguente dettaglio era in ombra, ho corretto la gamma (Val=1.5 col PaintShop5) e poi ingrandito 2:1


Orig.	Jpeg	Wif

Per finire ho fatto delle prove più oggettive, ho calcolato con PpmDiff il RMSE (Root Mean Square Error, vedi più avanti definizione) fra le immagini originali e le compresse. Questo metodo non misura l'effettiva qualità visiva soggettiva di una immagine, ma ne da un valore oggettivo, semplice e veloce da calcolare.

Il primo caso mette a confronto l'immagine della volpe a primavera vista precedntemente, il secondo l'immagine delle case di montagna.
Ho provato anche il programma SPIHT, già compilato per Pc, C++ version 8.01 del 8/16/96, di Amir Said: amir@densis.fee.unicamp.br e William A. Pearlman - pearlman@ecse.rpi.edu, vedi http://ipl.rpi.edu/research/SPIHT/spiht0.html, questo metodo basato su Wavelet pare essere il migliore compressore lossy di immagini.

Immagine Volpe
File JpegOptimizer:                 2856 byte
File precedente compresso con Acb: 2177
File Wif246:                        2174
SPIHT:                              2176

Ecco i confronti:
volpe.ppm volpe246wif.ppm   RMSE: 11.248368
volpe.ppm volpeaJPO1.ppm    RMSE: 15.459730
volpe.ppm volpeaJpo1nr.ppm RMSE: 17.262547 (non ricostruita col minerva)
volpe.ppm volpeSPIHT.ppm    RMSE: 10.637528

Immagine Case
Jpeg WebGraphicsOtimizer: 11744 (non comprimibile entropicamente)
Wif116: 11792
SPIHT: 11812

Confronti:
case.ppm caseWgo.ppm        RMSE: 12.957367
case.ppm case116Wif.ppm     RMSE: 10.893498
case.ppm caseSPIHT.ppm      RMSE: 9.878976
casei.ppm case116Wifi.ppm   RMSE: 22.174690 (1)
casei.ppm casewgoi.ppm      RMSE: 27.969070 (1)

(1) = prima sono state tutte e tre intensificate con unsharp masking del PaintShopPro v.5 (r=1 forza=163%, clipping=1).

Primo dettaglio immagine case (vedi nota precedente):
caseo.ppm casejpg.ppm RMSE: 10.578094
caseo.ppm casewif.ppm RMSE: 10.244960

RMSE =
_Ö ì
ï
í
ï
ï
î

n

å (Imm_i - Imm'_i)²

i = 1

n ü
ï
ý
ï
ï
þ

Si vede che in tutti i casi la compressione Wavelet ha battuto il Jpeg.
Questo non prova che ho mal interpretato le immagini risultanti, ma che al contrario l'RMSE non è una buona misura di qualità soggettiva di immagini. In ogni caso il Wif non è un formato da sottovalutare, specialmente per i livelli di compressione più alti.
Si vede anche che SPIHT è sempre il migliore, e Wif è sempre migliore del Jpeg ottimizzato.
Il programma SPIHT è abbastanza lento rispetto al jpeg, ma pur sempre ben utilizzabile. Se devo usare un formato lossless non standard preferisco usare il migliore, cioè SPIHT. In ogni caso la differenza rispetto al Jpeg non è molto grande, soggettivamente circa 1.5 volte migliore, quasi sempre migliore.

N.B. Spiht è ottimo anche perchè perfettamente progressivo. Citazione da una delle pagine del sito di Spiht:

Optimized Embedded Coding
A strict definition of the embedded coding scheme is: if two files produced by the encoder have size M and N bits, with M > N, then the file with size N is identical to the first N bits of the file with size M.
Let's see how this abstract definition is used in practice. Suppose you need to compress an image for three remote users. Each one have different needs of image reproduction quality, and you find that those qualities can be obtained with the image compressed to at least 8 Kb, 30 Kb, and 80 Kb, respectively. If you use a non-embedded encoder (like JPEG), to save in transmission costs (or time) you must prepare one file for each user. On the other hand, if you use an embedded encoder (like SPIHT) then you can compress the image to a single 80 Kb file, and then send the first 8 Kb of the file to the first user, the first 30 Kb to the second user, and the whole file to the third user.
But what is the price to pay for this "amenity"? Surprisingly, with SPIHT all three users would get (for the same file size) an image quality comparable or superior to the most sophisticated non-embedded encoders available today. SPIHT achieves this feat by optimizing the embedded coding process and always coding the most important information first.
An even more important application is for progressive image transmission, where the user can decide at which point the image quality satisfies his needs, or abort the transmission after a quick inspection, etc.

Non si butterebbero via dati per vedere thumbnail di immagini su Internet, tutti i dati della immagine piccola sarebbero sfruttati per l'immagine ad alta risoluzione.
Nella codifica ai massimi tassi, per ottenere thumbnail nota che è molto più efficiente comprimere molto una grande immagine, che meno una piccola. Al limite la grande si può sempre ridurre di dimensioni.
Per immagini molto piccole (dell'ordine di 100x100) Spiht forse risulta peggiore o molto vicino al Jpeg.

Aggiunta del 27 Gen '99 - Un'altra prova

Bike_d

Ho compresso parecchio, in maniera quasi Npl (near percueptual lossless) una immagine, Bike_d, 512x512 truecolor, composta da vaste aree con sfumature dolcissime, alto microcontrasto, rumore quasi nullo, forte contrasto cromatico, colori saturi, e alcune zone con massime frequenze spaziali.

Nome file      compressa con        n. byte file
Bike.cmp       SPIHT                   16384
BikeJPO.jpg    file Jpeg Optimizer     16554
Bike59.wif     Compression Engine      16413

File1,file2        RMSE
bike bikejpoMin   7.492867 (Decompresso con minerva)
bike bikejpo      7.290542
bike bike59Wif    5.845390
bike bikeSPIHT    5.430063

Questi risultati sono interessanti, dato che l'immagine Jpeg decompresa con Minerva appare visivamente leggermente migliore della decompressa normalmente.

N. 101 19990116 e n. 107 19990121


Volpe Primavera, 512x512x24M 786'432 byte Raw 278'704 byte Bmf (35.43%) 35'849 byte questa Jpeg (4.558%)	Compressa col Jpeg Optimizer v. 3.01 con comando MagiCompress, => 2900 byte. Con PicPress tolti commenti e altri dati inutili => 2856 byte. (Compressa poi con Acb => 2177 byte).


Immagine Jpeg-Acb da 2177 byte ricostruita col PicPress (o Minerva), (poi ricompressa in Jpeg a 13189 byte)	Compressa in Wif con param=246, a 2174 byte, non comprimibili entropicamente. (L'immagine punta il file Wif).