reports/kompr.teknikker.html

   1 <HTML>
   2 <HEAD>
   3 <TITLE>Sammenligning av komprimeringsteknikker</TITLE>
   4 <!-- Changed by: Petter Reinholdtsen,  1-Dec-1995 -->
   5 <LINK REV="made" HREF="mailto:petterr@stud.cs.uit.no">
   6 </HEAD>
   7 <BODY>
   8 <H1>Sammenligning av komprimeringsteknikker</H1>
   9
  10 <H2>Samendrag</H2>
  11
  12 Jeg tar her for meg tre komprimeringsteknikker for bilder/bilde-
  13 sekvenser; Discrete Cosine Transform (JPEG), Wavelet Transform og
  14 Deflate/LZ77 (PNG).  JPEG og Wavelet er "lossy", mens PNG er
  15 "lossless"
  16
  17 <P>Disse blir sammenlignet med hensyn på bildekvalitet, komprimeringsgrad
  18 og hastighet.
  19
  20 <HR>
  21 <H2>Innholdsfortegnelse</H2>
  22 <UL>
  23 <LI><A HREF="#innledning">Innledning</A>
  24 <LI><A HREF="#DCT">Discrete Cosine Transform (JPEG)</A>
  25 <LI><A HREF="#wavelet">Wavelet Transform</A>
  26 <LI><A HREF="#LZ77">Deflage/LZ77 (PNG)</A>
  27 <LI><A HREF="#bildekvalitet">Bildekvalitet</A>
  28 <LI><A HREF="#komprimeringsgrad">komprimeringsgrad</A>
  29 <LI><A HREF="#hastighet">Hastighet</A>
  30 <LI><A HREF="#konklusjon">Konklusjon</A>
  31 <LI><A HREF="#kilder">Kilder</A>
  32 </UL>
  33 <HR>
  34
  35 <A NAME="#innledning"><H2>Innledning</H2>
  36
  37 For multimediasystemer er bilder og video meget viktige mediatyper.
  38 Datamengden som brukes for å lagre og overføre desse mediene gjør at
  39 det er meget å vinne ved å komprimere dem.  Ved å utnytte egenskaper i
  40 det menneskelige øyet kan man benytte komprimeringsteknikker som ikke
  41 gir en tro kopi av originalen, men et bilde som er visuelt likt.
  42
  43 <P>Jeg vil her sammenligne JPEG og Wavelet på stillbilder.  Disse
  44 resultatene blir sammenlignet med PNG.
  45 </A>
  46
  47 <A NAME="DCT"><H2>Discrete Cosine Transform (JPEG)</H2>
  48
  49 JPEG-komprimering[1] er en transform komprimering som bruker DCT for å
  50 konvertere farge og lysverdiene til en form der antall verdier med
  51 betydning reduseres.  JPEG deler bildet opp i 8x8-ruter som
  52 konververes til en sekvens av 64 koeffisienter.
  53
  54 <P>Til forskjell fra hver pixelverdi som inneholder like stor del av
  55 bildeinformasjonen, representerer koeffisientene ulik mengde
  56 informasjon.  De første koeffisientene representerer mer informasjon.
  57 Denne sekvensen av koeffisienter blir dividert med en
  58 kvantifiseringsfaktor som varierer i forhold til sekvensnummeret.
  59 Dette resulterer i at en god del av koeffisientene blir avrundet til
  60 null.
  61
  62 <P>Deretter blir sekvensene av verdier løpelengde-kodet med
  63 Huffman-koding.  Kvantifiseringstabellen og Huffman-tabellen blir
  64 lagret sammen med de ferdigkomprimerte dataene.
  65 </A>
  66
  67 <A NAME="wavelet"><H2>Wavelet Transform</H2>
  68
  69 Wavelet-transform, slik de er implementer av Kristian Elstad[2], deler
  70 ikke bildet opp i mindre deler.  Her reduseres hele bildet til en
  71 sekvens koeffisienter.  Koeffisientene representerer ulike
  72 "signalfrekvenser", De første koeffisientene tilsvarer lave frekvenser
  73 og dermed lav oppløsning.  De etterfølgende koeffisienter tilsvar
  74 høyere frekvenser og dermed flere detaljer i bildet.
  75 </A>
  76
  77 <A NAME="LZ77"><H2>Deflage/LZ77 (PNG)</H2>
  78
  79 PNG[3] bruker løpelenge-kodingen Deflate/Enflate basert på LZ77 og
  80 Huffman-koding.  PNG kan brukes i "stream"-modus, der en kan vise
  81 deler av bildet mens det blir overført.
  82 </A>
  83
  84 <A NAME="bildekvalitet"><H2>Bildekvalitet</H2>
  85
  86 Ved høy komprimering gir JPEG en blokk-effekt pga. dens inndeling i
  87 8x8-ruter.  Ved middels komprimering gir JPEG bilder som er visuelt
  88 nært originalen.
  89
  90 <P>Wavelet gir visuelt gode bilder også ved høy komprimeringsgrad.  Det er ingen blokk-effekt
  91
  92 <P>PNG har har ikke variabel bildekvalitet.
  93
  94 </A>
  95 <A NAME="komprimeringsgrad"><H2>komprimeringsgrad</H2>
  96
  97 Jeg har her basert meg på tall fra [2], samt størrelsen på tilsvarende
  98 GIF-bilder.  GIF har tilnærmet samme komprimeringsgrad som PNG.
  99
 100 <P>Komprimerings-graden ved Wavelet-komprimering kan variere fra
 101 ca. 2,5:1 til mer en 30:1.  Ved en komprimerings-grad på 16,21:1 er
 102 bildet (subjektivt) visuelt nært originalen.
 103
 104 Ved å sammenligne JPEG og wavelet for samme kompresjonsgrad med
 105 originalen og beregne "objektiv" bildekvalitet blir det i [2]
 106 konkludert med at JPEG er objektivt bedre en wavelet på en gikk
 107 kompresjonsgrad.
 108
 109 GIF gav på et utvalg (3 forskjellige) bilder en gjennomsnittlig
 110 kompresjonsgrad på 3,5:1.
 111
 112 </A>
 113 <A NAME="hastighet"><H2>Hastighet</H2>
 114
 115 Måling foretatt av Kristian Elstad[2] med en fritt tilgjengelig
 116 implementasjon av JPEG samt hans egen Wavelet-implementasjon viser at
 117 wavelet kommer godt ut.
 118
 119 <P>Tidsforbruket varierer med kompresjonsgrad,
 120 men for en gitt kompresjonsgrad bruker denne wavelet-implementasjonen
 121 rundt 0.5 sekunder på et bilde med oppløsning 513x513 der JPEG bruker
 122 rundt 2 sekunder.
 123
 124 Jeg har ingen målinger med PNG.
 125 </A>
 126
 127 <A NAME="konklusjon"><H2>Konklusjon</H2>
 128
 129 Wavelet er en god kandidat for nærmere forskning på bildekomprimering.
 130 Ved store komprimeringsgrader gir den et jevnere bilde en JPEG, og
 131 tilsynelatende er hastigheten ved kompirimgering og dekomprimering
 132 større.  Det er nødvendig med en undersøkelse av DCT-transformering
 133 uten oppdeling i blokker for å se om dette gir et bedre bilde ved høye
 134 kompresjonsgrader.
 135
 136 <P>PNG gir ikke på langt nær god kompresjon, og bør nok kun brukes der
 137 man ikke kan akseptere tap av bildekvalitet.
 138
 139 </A>
 140
 141 <A NAME="kilder"><H2>Kilder</H2>
 142 <OL>
 143 <LI>The JPEG Still Picture Compression Standard, av G. K. Wallance,
 144 1991
 145 <LI>Bilde Komprimering ved bruk av Wavelet Transform Koding, av
 146 K. Elstad, 1994
 147 <LI><A HREF="http://sunsite.unc.edu/boutell/png.html">PNG (Portable
 148 Network Graphics) Specification, Tenth Draft</A>, av Thomas Boutell,
 149 5. May 1995.
 150 </OL>
 151 </A>
 152 <HR>
 153 <ADDRESS>Petter Reinholdtsen -
 154 <A HREF="mailto:petterr@stud.cs.uit.no">petterr@stud.cs.uit.no</A></ADDRESS>
 155
 156 </BODY>
 157 </HTML>
 158