taralino

Bildkompression

In diesem Abschnitt zeigen wir, wie das zuvor beschriebene Reduktionsverfahren zur Bildkompression eingesetzt werden kann. Zunächst betrachten wir nur Schwarz-Weiß-Bilder und müssen verstehen, dass Bilder nichts anderes sind als eine gitterartige Anordnung einzelner kleiner Quadrate, die sogenannten Pixel.

Die Abbildung veranschaulicht, wie ein Schwarz-Weiß-Bild entsprechend anhand von Zahlen definiert werden kann (und umgekehrt). Die einzelnen Quadrate bzw. Pixel des Bildes beschreiben wir durch eine Zahl mit folgender Bedeutung:

Eine 0 bedeutet ein schwarzes Pixel, eine 255 steht für ein weißes Pixel. Die Zahlenwerte dazwischen entsprechen den jeweiligen Graustufen.

Zusammenfassend kann ein Schwarz-Weiß-Bild damit auch als Datenmatrix angesehen werden, für die eine Singulärwertzerlegung bestimmt werden kann. Um das Vorgehen anhand eines kleine Beispiels zu veranschaulichen, verwenden wir das Picture-Paket:

Zur Referenz

Dieses beinhaltet ein (farbiges) Beispielbild bestehend aus 48 x 96 Pixel, welches in ein Schwarz-Weiß-Bild überführt werden kann. Anschließend kann eine Singulärwertzerlegung bestimmt werden.

Beispiel

Es wird die Singulärwertzerlegung eines Schwarz-Weiß-Bildes bestimmt. Anschließend werden die Singulärwerte in ein Datenfeld übertragen und ausgegeben.

<!DOCTYPE html>
<html>
<head>
  <meta charset="utf-8">
  <meta name="viewport" content="width=device-width, initial-scale=1.0">
  <script src="taralino.js"></script>
</head>
<body>
<script>

// Schwarz-Weiß-Bild als Datenmatrix
var A = Picture.example();
A = Picture.monochrome(A);

// Singulaerwertzerlegung bestimmen
var T = LinearAlgebra.svd(A);

// Singulaerwerte in Datenfeld (Vektor) speichern
var q = Math.min(A.length, A[0].length);
var R = [];
for (var k = 0; k < q; k++) R.push(T.S[k][k]);

// Singulaerwerte ausgeben
Console.print(R);

</script>
</body>
</html>

Vorschau Download Kopie speichern

Bildkompression

Wie im Abschnitt zuvor beschrieben, kann nun das Reduktionsverfahren angewandt werden. Aus den reduzierten Matrizen kann eine Approximation der Datenmatrix bzw. des Schwarz-Weiß-Bildes bestimmt werden. Diese Vorgehensweise demonstriert das folgende Beispiel. Dargestellt wird sowohl das Originalbild als auch das komprimierte bzw. approximierte Bild.

Beispiel

Es wird die Singulärwertzerlegung eines Schwarz-Weiß-Bildes bestimmt. Anschließend wird das Reduktionsverfahren zwecks Erprobung als Methode zur Bildkompression angewandt.

<!DOCTYPE html>
<html>
<head>
  <meta charset="utf-8">
  <meta name="viewport" content="width=device-width, initial-scale=1.0">
  <script src="taralino.js"></script>
</head>
<body>
<script>

// Schwarz-Weiß-Bild als Datenmatrix
var A = Picture.example();
A = Picture.monochrome(A);
Picture.draw(A, {zoom:4});

// Parameter zur Reduktion / Kompression
var q = 12;

// Dimension der Datenmatrix
var m = A.length;
var n = A[0].length;

// Singulaerwertzerlegung bestimmen
var T = LinearAlgebra.svd(A);

// Null-Matrix mit gleicher Dimension wie A
var B = [];
for (var i = 0; i < m; i++) {
  B.push([]);
  for (var j = 0; j < n; j++) B[i].push(0);
};

// Approximation der Datenmatrix bestimmen
for (var i = 0; i < m; i++) {
  for (var j = 0; j < n; j++) {
    for (var k = 0; k < q; k++) B[i][j] += T.U[i][k] * T.S[k][k] * T.V[k][j];
  };
};

// Approximation der Datenmatrix als Schwarz-Weiß-Bild ausgeben
Picture.draw(B, {zoom:4});

</script>
</body>
</html>

Vorschau Download Kopie speichern

Aufgabe

Mache die mit dem Quellcode zuvor vertraut. Welche Zahlen für den Parameter q sind zulässig? Wie gut ist die Approximation des Originalbildes in Abhängigkeit von q?