Sammenligning av komprimeringsteknikker

Samendrag

Jeg tar her for meg tre komprimeringsteknikker for bilder/bilde- sekvenser; Discrete Cosine Transform (JPEG), Wavelet Transform og Deflate/LZ77 (PNG). JPEG og Wavelet er "lossy", mens PNG er "lossless"

Disse blir sammenlignet med hensyn på bildekvalitet, komprimeringsgrad og hastighet.

Innholdsfortegnelse

Innledning

For multimediasystemer er bilder og video meget viktige mediatyper. Datamengden som brukes for å lagre og overføre desse mediene gjør at det er meget å vinne ved å komprimere dem. Ved å utnytte egenskaper i det menneskelige øyet kan man benytte komprimeringsteknikker som ikke gir en tro kopi av originalen, men et bilde som er visuelt likt.

Jeg vil her sammenligne JPEG og Wavelet på stillbilder. Disse resultatene blir sammenlignet med PNG.

Discrete Cosine Transform (JPEG)

JPEG-komprimering[1] er en transform komprimering som bruker DCT for å konvertere farge og lysverdiene til en form der antall verdier med betydning reduseres. JPEG deler bildet opp i 8x8-ruter som konververes til en sekvens av 64 koeffisienter.

Til forskjell fra hver pixelverdi som inneholder like stor del av bildeinformasjonen, representerer koeffisientene ulik mengde informasjon. De første koeffisientene representerer mer informasjon. Denne sekvensen av koeffisienter blir dividert med en kvantifiseringsfaktor som varierer i forhold til sekvensnummeret. Dette resulterer i at en god del av koeffisientene blir avrundet til null.

Deretter blir sekvensene av verdier løpelengde-kodet med Huffman-koding. Kvantifiseringstabellen og Huffman-tabellen blir lagret sammen med de ferdigkomprimerte dataene.

Wavelet Transform

Wavelet-transform, slik de er implementer av Kristian Elstad[2], deler ikke bildet opp i mindre deler. Her reduseres hele bildet til en sekvens koeffisienter. Koeffisientene representerer ulike "signalfrekvenser", De første koeffisientene tilsvarer lave frekvenser og dermed lav oppløsning. De etterfølgende koeffisienter tilsvar høyere frekvenser og dermed flere detaljer i bildet.

Deflage/LZ77 (PNG)

PNG[3] bruker løpelenge-kodingen Deflate/Enflate basert på LZ77 og Huffman-koding. PNG kan brukes i "stream"-modus, der en kan vise deler av bildet mens det blir overført.

Bildekvalitet

Ved høy komprimering gir JPEG en blokk-effekt pga. dens inndeling i 8x8-ruter. Ved middels komprimering gir JPEG bilder som er visuelt nært originalen.

Wavelet gir visuelt gode bilder også ved høy komprimeringsgrad. Det er ingen blokk-effekt

PNG har har ikke variabel bildekvalitet.

komprimeringsgrad

Jeg har her basert meg på tall fra [2], samt størrelsen på tilsvarende GIF-bilder. GIF har tilnærmet samme komprimeringsgrad som PNG.

Komprimerings-graden ved Wavelet-komprimering kan variere fra ca. 2,5:1 til mer en 30:1. Ved en komprimerings-grad på 16,21:1 er bildet (subjektivt) visuelt nært originalen. Ved å sammenligne JPEG og wavelet for samme kompresjonsgrad med originalen og beregne "objektiv" bildekvalitet blir det i [2] konkludert med at JPEG er objektivt bedre en wavelet på en gikk kompresjonsgrad. GIF gav på et utvalg (3 forskjellige) bilder en gjennomsnittlig kompresjonsgrad på 3,5:1.

Hastighet

Måling foretatt av Kristian Elstad[2] med en fritt tilgjengelig implementasjon av JPEG samt hans egen Wavelet-implementasjon viser at wavelet kommer godt ut.

Tidsforbruket varierer med kompresjonsgrad, men for en gitt kompresjonsgrad bruker denne wavelet-implementasjonen rundt 0.5 sekunder på et bilde med oppløsning 513x513 der JPEG bruker rundt 2 sekunder. Jeg har ingen målinger med PNG.

Konklusjon

Wavelet er en god kandidat for nærmere forskning på bildekomprimering. Ved store komprimeringsgrader gir den et jevnere bilde en JPEG, og tilsynelatende er hastigheten ved kompirimgering og dekomprimering større. Det er nødvendig med en undersøkelse av DCT-transformering uten oppdeling i blokker for å se om dette gir et bedre bilde ved høye kompresjonsgrader.

PNG gir ikke på langt nær god kompresjon, og bør nok kun brukes der man ikke kan akseptere tap av bildekvalitet.

Kilder

  1. The JPEG Still Picture Compression Standard, av G. K. Wallance, 1991
  2. Bilde Komprimering ved bruk av Wavelet Transform Koding, av K. Elstad, 1994
  3. PNG (Portable Network Graphics) Specification, Tenth Draft, av Thomas Boutell, 5. May 1995.
Petter Reinholdtsen - petterr@stud.cs.uit.no