Katzenfotos: Zufall und Rekonstruktion

Das Internet ist eine der größten und wichtigsten Errungenschaften des letzten Jahrhunderts, vielleicht sogar Jahrtausends. Mit dem HTML-Format und der allerersten Webseite (siehe hier) hat Sir Tim Berners-Lee, damals Wissenschaftler in Genf, der Menschheit einen großen Dienst erwiesen. Denken wir an soziale Netzwerke, die Wikipedia, allgemein die Informationsgewalt des Internets. Das Internet vereinfacht unser Leben massiv, ob mit Google Maps, Youtube-Tutorials oder Nachrichtenportalen. Neben all diesen allgemeingültig wertvollen Seiten des Internets, haben wir, die Nutzer, in den vergangenen Jahren das Internet in eine Datenbank von Fake News, Schmuddelfilmen und Katzenfotos verwandelt - das hätte sich sicherlich nicht einmal Sir Tim vorstellen können.

Fake News und Schmuddelfilme haben eher ein zweifelhaftes Ansehen. Katzenfotos im Internet erfreuen sich einer riesigen Fanbase. Zu der auch ich mich zähle. Die süßen kleinen Wesen, man würde sie gerne streicheln und knuddeln, oder ihnen nur zuschauen: beim ungeschickten Verhalten der Kleineren und den anmutigen Bewegungen der Älteren. Bevor ich ins Schwärmen gerate: Es soll hier eigentlich um etwas anderes gehen. Nämlich um die Rekonstruktion von Fotos mit einfachen Methoden der räumlichen Statistik. Genauer noch: die Rekonstruktion von unvollständigen oder zerstörten Katzenfotos. Falls Ihr, werte Leser, nun denkt: "Warum sollte man Katzenfotos rekonstruieren? Das Internet ist voll mit ihnen." seid Ihr Monster.

Was ist ein Bild eigentlich? Zuerst beschränken wir uns einmal auf Graustufen, also das, was im Volksmund als "schwarz-weiß" bezeichnet wird. Ein Bild besteht dann aus einem zweidimensionalen Raster aus Bildpunkten. Das Raster kommt zum Vorschein, wenn man ein Bild stark vergrößert. Das sieht man in Abbildung 1, wo wir mit einem (schon recht groben) Katzenfoto starten und immer weiter hineinzoomen. Die Graustufen können wir jetzt in Zahlen umwandeln, Graustufenwerte. Das Bild ist dann eine große Matrix - sagen wir eine Tabelle. Jeder Eintrag der Tabelle bezieht sich auf den Graustufenwert eines Pixels, ein Wert zwischen 0 (schwarz) und 255 (weiß). Die verschiedenen Graustufenwerte lassen sich zum Beispiel in der Wikipedia nachlesen, dort in der üblichen Hexadezimaldarstellung (16er-System) von 00 bis FF.

Abbildung 1. Ein Katzenauge, immer weiter vergrößert; von oben nach unten. Man kann die Pixelstruktur des Fotos recht gut erkennen. Danke an Laura S. und ihren äußerst fotogenen Kater Klaus.

Als zerstörtes Katzenfoto würden wir nun eines bezeichnen, bei dem einzelne Bildpunkte fehlen. Siehe zum Beispiel, das Bild in Abbildung 2. Das Auge von Kater Klaus aus Abbildung 1, wobei jeder zweite Bildpunkt je Spalte und Zeile fehlt. Also 75% der Bildpunkte sind nicht vorhanden. Aus der Perspektive der Graustufenwerte fehlen nun Werte aus der Matrix oder Tabelle, die ich oben erwähnt hatte. Und damit wird das Problem der Katzenfoto-Rekonstruktion ein Problem der Statistik: Wir haben Daten; die gegebenen Bildpunkte, und wir haben Unbekannte; die fehlenden Bildpunkte. Diese unbekannten Bildpunkte wollen wir schätzen.

Abbildung 2. Ein beschädigtes Katzenfoto. Wir sehen pro Spalte und Zeile nur jeden zweiten Bildpunkt aus dem Katzenfoto von eben.

Stetigkeit. Wie gehen wir vor? Wir treffen zuerst verschiedene Annahmen. Wir nehmen an, dass das Motiv, dass auf dem Bild dargestellt wird, eine stetige Funktion ist. Diese Funktion hat zwei Eingabevariable (x- und y-Achse) und eine Ausgabe, die Graustufe. Was war noch mal eine stetige Funktion? Zur Erinnerung, folgender Merksatz aus der Schulmathematik: Eine stetige Funktion (in einer Dimension) kann man mit einem Strich durchzeichnen. Siehe auch Abbildung 3 für Beispiele von stetigen und unstetigen Funktionen in 1D und Abbildung 4 für solche in 2D. Das bedeutet für unser Motiv, dass es keine heftigen Farbumschwünge gibt. Im Gegensatz, die Farben verlaufen alle in gewisser Weise ineinander. Fotografiert man ein Schachbrett aus der Nähe, ist das sicherlich Blödsinn. Der Übergang von schwarz zu weiß ist ein heftiger Farbumschwung. Fotografiert man ein Gebirge bei grau-blauem leicht-bewölkten Himmel, mag es stimmen. Die Stelle, an der der Berg aufhört und der Himmel anfängt, lässt sich nicht so genau bestimmen.

Abbildung 3. Oben eine stetige Funktion, unten eine unstetige Funktion, in 1D.

Abbildung 4. Oben eine stetige Funktion, unten eine unstetige Funktion, jeweils in 2D. Die Farbe steht für den Wert, den die Funktion an einer gewissen Stelle (x,y) hat. Je kleiner der Wert, desto dunkler der Bildpunkt.

Gauß'sche Prozesse. Außerdem nehmen wir an, dass das Motiv die Realisierung eines Gauß'schen Prozesses ist. Ein Gauß'scher Prozess ist eine zufällige Funktion f, bei der f(x) einer Normalverteilung folgt, für beliebiges x. Das heißt, was wir sehen, wird mit gewisser Wahrscheinlichkeit von einer solchen zufälligen Funktion dargestellt. Fährt man mit dem Rasenmäher durch die Wahrscheinlichkeitstheorie, könnte man intuitiv(!) sagen: Bei einem ganz normalen Würfel mit sechs Seiten können die Zahlen eins bis sechs vorkommen. Jede dieser Zahlen ist eine mögliche Realisierung des Würfels. Wenn wir annehmen, dass jedes Motiv, das wir sehen, die Realisierung eines Gauß'schen Prozesses ist, so nehmen wir an, dass wir (wenn wir nur lange genug würfeln) irgendwann genau dieses Motiv herausbekommen.

Die beiden Annahmen (Stetigkeit und Gauß'scher Prozess) lassen sich einfach vereinen: Wir kennen diverse Gauß'sche Prozesse, die die Stetigkeitsannahme erfüllen. Das heißt, wenn wir eine zufällige Funktion "würfeln", ist diese Funktion tatsächlich stetig. In Abbildung 5 habe ich einmal ein paar Realisierungen von solchen Gauß'schen Prozessen in 1D geplottet. Man sieht tatsächlich stetige Funktionen. In den nächsten Abschnitten werden wir nur von 1D sprechen, obwohl Fotos 2D sind. 1D lässt sich besser veranschaulichen und ist einfacher zu verstehen. Dieselben Ideen funktionieren jedoch auch in 2D.

Abbildung 5. Gauß'sche Prozesse in 1D mit exponentieller Kovarianzfunktion. Die Realisierungen sind stetige Funktionen.

Die Bildrekonstruktion besteht nun darin eine stetige Funktion zu finden, die genau durch die vorhandenen Bildpunkte geht. Eine Strategie ist, mit einem Gauß'schen Prozess stetige Funktionen zu würfeln, bis wir eine finden, die genau durch alle vorhandenen Bildpunkte geht. Das ist eine denkbar schlechte Idee. Wenn ich einmal vom Rasenmäher absteige und mit der Nagelschere an der Wahrscheinlichkeitstheorie weiterarbeite, fällt mir ein, das die Wahrscheinlichkeit eine solche Funktion zu würfeln, gerade 0 ist. Damit ist das keine Option. Wie hilflos dieser Versuch ist, habe ich einmal in Abbildung 6 angedeutet. Dort habe ich fünf Datenpunkte eingezeichnet und überprüfe, ob die Funktionen aus Abbildung 5 vielleicht durch diese Punkte laufen. Tun sie nicht.

Abbildung 6. Dieselben Realisierungen wie vorher. Dazu fünf Datenpunkte in rot. Manche Prozesse laufen nah an den Datenpunkten vorbei. Keine der Realisierungen verbindet alle Datenpunkte.

Gauß'sche Prozess Regression. Stattdessen können wir auch direkt von den stetigen Gauß'schen Prozessen würfeln, die genau durch die gegebenen Bildpunkte gehen. Dann würfeln wir nur noch Prozesse, die diese beiden Voraussetzungen erfüllen. Das sieht dann so aus, wie in Abbildung 7. Dort gehen alle realisierten Funktionen direkt durch die Datenpunkte und sind stetig. Wir bekommen die Verteilung dieses speziellen Gauß'schen Prozesse mittels bedingter Wahrscheinlichkeit und Bayes'scher Statistik. Die resultierende Methode nennt sich Kriging, oder Gauß'sche Prozess Regression (Gaussian Process Regression, GPR). Herleitung und genaue Anwendung möchte ich hier lieber überspringen. GPR spielt heutzutage eine große Rolle in maschinellem Lernen und räumlicher Statistik.

Abbildung 7. Stetige Gauß'sche Prozesse, die exakt durch die Datenpunkte gehen. Das Ergebnis einer Gauß'schen Prozess Regression.

Wir können jetzt Funktionen würfeln, die stetig sind (also unsere Annahme erfüllen), die Realisierungen von einem Gauß'schen Prozess sind, und die durch alle uns bekannten Datenpunkte gehen. Welche dieser Funktionen nehmen wir nun? Irgendeine, zum Beispiel. Eine andere gute Idee ist der Mittelwert all dieser Funktionen. Diesen können wir entweder berechnen oder per Monte Carlo Simulation bestimmen. Die daraus resultierenden Funktionen zeige ich in Abbildung 8.

Abbildung 8. Wir können die Funktion würfeln, wir können aber auch den Mittelwert bestimmen und diesen als Funktion verwenden. Im linken Bild habe ich den Mittelwert (die schwarze Kurve) analytisch berechnet. Im rechten Bild hab ich 11 Monte Carlo Samples gezogen und den Stichprobenmittelwert (wieder die schwarze Kurve) bestimmt. Die 11 Monte Carlo Samples sieht man im Hintergrund.

Zurück zu den Katzenfotos. Zusammenfassend rekonstruieren wir also ein unvollständiges Katzenfoto, in dem wir zufällige Funktionen in 2D würfeln, die in allen bekannten Punkten mit dem Katzenfoto übereinstimmen und stetig sind. Das bekommen wir mit Gauß'scher Prozess Regression hin. Die resultierende Funktion ist dann entweder eins der Würfelergebnisse oder der Mittelwert des resultierenden Prozesses. Letzterer kann entweder analytisch oder via Monte Carlo Simulation bestimmt werden. Dann übertragen wir (nach Auf-/Abrunden) die passenden Funktionswerte in die fehlenden Felder der Graustufentabelle. Aus der Graustufentabelle erhalten wir dann das rekonstruierte Katzenfoto. 

Für das beschädigte Foto von Kater Klaus in Abbildung 2 habe ich das einmal getan. Die Rekonstruktion basiert hier auf dem analytisch berechneten Mittelwert des resultierenden Gauß'schen Prozesses. Original und Rekonstruktion zeige ich in Abbildung 9.

Mir gefällt's; ist aber auch 'ne Katze.

Abbildung 9. Kater Klaus rekonstruiert (oben) und im Original (unten). Das rekonstruierte Bild wirkt etwas weniger detailreich, als das Original.