Universität Mannheim
Lehrstuhl für Praktische Informatik IV
Prof. Dr. W. Effelsberg
Jürgen Vogel
Thomas Hänselmann
Stephan Kopf

Multimedia-Systeme: Übungsblatt 2 (Musterlösung)

Übung: 08.11.02

Die Aufgaben, die auf dieser Seite ausgefüllt werden können, werden auch über das Web ausgewertet. Dazu muß die Matrikelnummer eingegeben werden und das Ganze abgeschickt werden. Voraussetzung ist allerdings, daß der/die Studierende auch für die elektronische Auswertung angemeldet ist.

Aufgabe 1: Arithmetische Kodierung

Die folgende Tabelle gibt die Wahrscheinlichkeiten für ein Alphabet {a,b,c,d,e} an. Kodieren Sie den String aabdcea mit der statischen arithmetischen Kodierung. Teilen Sie das Intervall so auf, daß das Teilintervall für a bei 0 beginnt und gehen Sie dann alphabetisch aufsteigend weiter vor!



graphische Darstellung der Lösung

Berechnung der Grenzen für ein gegebenes Zeichen z:

  • u= left + ((right - left) * probCum[z]);
  • o= left + ((right - left) * probCum[z+1]);

Kodierung: 0,038826

Intervallgrenzen bei Schritt 4 der Dekodierung:

Untere Grenze: 0,0378

Obere Grenze: 0,0396

Aufgabe 2: Diskrete Cosinus-Transformation

Gegeben sei folgender 8x8-Block aus obigem Bild: 

185 190 195 203 190 190 186 190
137 166 178 195 190 195 190 184
104 104 104 162 182 190 190 184
131 104 104 117 159 171 182 178
141 145 150 138 146 159 169 178
150 177 152 162 152 159 169 178
126 165 157 155 159 159 164 169
 78 111 163 150 152 156 162 169
Programmieren Sie den DCT-Algorithmus nach der in der Vorlesung angebenen Formel und berechnen Sie A'=DCT(A). Runden Sie die Koeffizienten der Ergebnismatrix A' auf ganze Zahlen durch Abschneiden der Nachkommastellen. 

const double PI = 3.14159;
const double INVSQRT2 = 0.7071;

const unsigned int MSIZE = 8;
typedef int matrix[MSIZE][MSIZE];

void fdct (matrix& src, matrix& dest)
{
  for (int v = 0; v < MSIZE; v++)
    for (int u = 0; u < MSIZE; u++) {
      double Cu = (u == 0) ? INVSQRT2 : 1.0;
      double Cv = (v == 0) ? INVSQRT2 : 1.0;

      double result = 0.0;
      for (int y = 0; y < MSIZE; y++)
        for (int x = 0; x < MSIZE; x++)
          result += src[y][x]*
            cos((2.0*x+1)*u*PI/16.0)*
            cos((2.0*y+1)*v*PI/16.0);

      result *= 0.25*Cu*Cv;
      dest[v][u] = (int) result;
    }
}
Anwendung der Funktion fdct auf A ergibt: 
 1281  -121   -21   -11    -7    -6    -7    -6
   83    -3    -9    29    17    10    -2    -7
   60    32   -41   -39   -12     0     4    -2
   72    85    31   -17    -7    -6    -5    -9
  -20     0    14    -1     0     7    19    17
   -7    -2    16    24    11    -3    -6     0
   -7   -15    -2     3    11     5    -3    -7
   -2    -3    -6    -3     1     0     0    -2

Aufgabe 3: Quantisierung

Berechnen Sie nun die quantisierte Matrix A'' aus der in Aufgabe 1 ermittelten Matrix A'. Verwenden Sie dabei untenstehende JPEG-Quantisierungstabelle für Luminanzblöcke (Helligkeitsblöcke). Runden Sie auch hier die Werte durch Abschneiden der Nachkommastellen. 
 16  11  10  16  24  40  51  61
 12  12  14  19  26  58  60  55
 14  13  16  24  40  57  69  56
 14  17  22  29  51  87  80  62
 18  22  37  56  68 109 103  77
 24  35  55  64  81 104 113  92
 49  64  78  87 103 121 120 101
 72  92  95  98 112 100 103  99

(a) Wieviele Nullwerte enthält die längste Kette, die bei der Lauflängenkodierung im Zick-Zack-Verfahren erzeugt wird? 
void quantize (matrix& srcDest, matrix& q)
{
   for (int i = 0; i < MSIZE; i++)
     for (int j = 0; j < MSIZE; j++)
       srcDest[i][j] = (int) (srcDest[i][j]/q[i][j]);
}
Anwendung der Funktion quantize auf A' ergibt: 
   80   -11    -2     0     0     0     0     0
    6     0     0     1     0     0     0     0
    4     2    -2    -1     0     0     0     0
    5     5     1     0     0     0     0     0
   -1     0     0     0     0     0     0     0
    0     0     0     0     0     0     0     0
    0     0     0     0     0     0     0     0
    0     0     0     0     0     0     0     0
Aus dem Zick-Zack-Verfahren ergibt sich als längste Kette mit Nullwerten eine Kette von 45 Koeffizienten.

(b) Welche wahrnehmungspsychologische Beobachtung spiegelt sich in der Wahl der Koeffizienten der Quantisierungstabelle wider?
Die Werte der Quantisierungstabelle nehmen von links oben nach rechts unten zu. D.h. die Koeffizienten der hohen Frequenzen in der unteren Dreiecksmatrix werden stärker quantisiert als die der oberen Dreiecksmatrix. Dieses ist möglich, da das menschliche visuelle System bzgl. der hohen Frequenzen kontrastunempfindlicher ist. Daher kommt es auf die exakten Wert dieser Koeffizienten nicht an, eine grobe Abschätzung - die sich effizienter speichern läßt - reicht aus.

Aufgabe 4: Dequantisierung und inverse DCT

(a) Dekodieren Sie den Block (Dequantisierung und Inverse DCT) und berechnen Sie die Ergebnismatrix. Ermitteln oder recherchieren Sie die Formel der Inversen DCT dabei selbständig. 


void dequantize (matrix& s, int q)
{
  for (int i = 0; i < MSIZE; i++)
    for (int j = 0; j < MSIZE; j++)
      s[i][j] *= q;
}


void idct (matrix& src, matrix& dest)
{
  for (int y = 0; y < MSIZE; y++)
    for (int x = 0; x < MSIZE; x++) {

      double result = 0.0;
      for (int v = 0; v < MSIZE; v++) {
        double Cv = (v == 0) ? INVSQRT2 : 1.0;
        for (int u = 0; u < MSIZE; u++) {
          double Cu = (u == 0) ? INVSQRT2 : 1.0;
          result += Cu*src[v][u]*
            cos((2.0*x+1)*u*PI/16.0)*
            cos((2.0*y+1)*v*PI/16.0);
        }
        result *= Cv;
      }

      result *= 0.25;
      dest[y][x] = ((int) result);
    }
}
Anwendung von dequantize gefolgt von idct auf A'' ergibt: 
  185   189   194   196   194   189   185   182
  145   151   162   175   186   191   190   188
  108   113   125   147   170   185   189   187
  111   110   115   132   154   172   178   178
  147   141   137   141   152   163   169   170
  164   162   160   158   159   162   167   171
  133   144   157   163   162   162   166   172
   88   112   141   157   159   158   163   170
(b) Stellen Sie die Ergebnismatrix als Grauwertbild dar und vergleichen Sie es mit dem Original.
Original:
 Ergebnis:
vogel@informatik.uni-mannheim.de