Bilder nachbauen mit Bauklötzen

Geschickte Zerlegung von Bildern mit Hilfe der Mathematik, um sie platzsparend zu speichern und zu übertragen

Überträgt man ein Bild im Internet, etwa eines, das man per E-Mail verschickt, kann man sich das vorstellen, wie das Erzählen einer Geschichte. Der Computer überträgt Stück für Stück die Details des Bildes, so wie ein Autor eine Geschichte erzählt. Dabei darf natürlich nichts verloren gehen. Was der Computer sich dabei jedoch wünscht, ist, dass er wenig erzählt. Denn je weniger er erzählt, desto kleiner ist die E-Mail, desto kürzer muss er selbst das Bild versenden bzw. der Empfänger zuhören. Ein Bild auf einem Computer besteht aus vielen Pixeln, also einzelnen Bildpunkten. Eine übliche Kamera produziert heute Bilder mit 12 Megapixeln, also 12 Millionen mal die 3 Werte für den Blau-, Rot- und Grünanteil. Ohne das zusammenzufassen – auch komprimieren genannt – zu einer kürzeren Form, würde das niemand per E-Mail bekommen wollen.

Eine Möglichkeit, die „Geschichte des Bildes“ zusammenzufassen, sind Wavelets, namentlich eine französisch-englische Mischung, die „kleine Welle“ bedeutet. Um deren Idee zu verstehen, betrachten wir unser Bild zunächst aus einer anderen Perspektive. Zunächst beschränken wir uns auf ein Schwarz-weiß-Bild, die Idee lässt sich später auf die 3 Farbkanäle einzeln anwenden. Legt man dieses Bild nun auf den Boden und baut darauf ein Gebirge, in dem ein Punkt umso höher liegt, je heller er ist, dann wird eine Kante im Bild – wie etwa an den Rändern der Buchstaben auf dieser Seite – in diesem Gebirge zu einer Klippe, der Teppich im Wohnzimmer zu einem Plateau. Beschreibt man das Bild nun über die Höhen der einzelnen Pixel im Gebirge, hat man die alte Beschreibung wieder.

Die Idee der Wavelets ist nun, das Gebirge mit Bauklötzen nachzubauen, die in allen unterschiedlichen Größen vorliegen. Der Einfachheit halber nehmen wir hier auch erstmal nur rechteckige Klötze, also etwa Lego-Steine, nur dass wir auch die Duplo-Größe dabei haben und eine feinere Variante von Lego und noch viele andere Größen. Zum Nachbauen gibt es zwei Regeln: Einen Stein, den man setzte, wählt man so groß wie möglich, dass er noch nicht über das eigentliche Bildgebirge hinausragt. Außerdem darf die Kante des Klotzes nicht nur halb auf einem Pixel liegen oder zu einem Viertel, sondern nur ganz oder gar nicht. Das schränkt sowohl die Größen der Klötze als auch die Positionen ein, an die diese gelegt werden können. Die Größe des Klotzes lässt sich also in Länge und Breite in Pixeln und in der Höhe in Anzahl Farbstufen angeben. Die Verschiebung kann immer in ganzen Pixelschritten angegeben werden.

Ein weißer Strich in einem Bild lässt sich also durch einen schmalen, sehr hohen (weiß waren die Bergspitzen im Gebirge) Klotz beschreiben. Weite Flächen können dann durch wenige große Steine beschrieben werden, nur an ihren Rändern benötigt man für die Details wieder mehr Steine. Den Plan schreibt man dann – beginnend bei den großen Steinen – auf. Kennen beide Computer die Menge aller möglichen Bausteine, muss nur noch der Plan ausgetauscht werden.

Durch die Anordnung im Plan ergibt sich, dass bereits dann, wenn der Empfänger einen kleinen Teil empfangen hat, er die ersten Teile des Bildes anzeigen kann. Je mehr er empfängt, desto mehr Details kann er anzeigen. Das ist auch praktisch für Handys, die mit ihrer knappen Empfangsrate einfach bei genügend Details für ihr Display aufhören können. Vielleicht laden sie dann bei Bedarf nach, wenn jemand ins Bild hineinzoomt.

Die Menge der Bausteine muss gut gewählt werden, denn sind es zu viele, benötigt man zum Erzählen, welchen Baustein man denn meint, wieder zu viel Zeit. Daher beschränkt man sich auf ganz wenige Bausteine und gibt ihnen zusätzlich eine Skalierung (um wie viel vergrößert, üblicherweise beschränkt auf die Werte 2, 4, 8, …) und eine Rotation mit. Bei den obigen also, ob sie horizontal oder vertikal liegen, denn mehr lässt die zweite Regel nicht zu.

Großer Nachteil dieser Art Bauklötze ist, dass sie sehr auf horizontale und vertikale Linien im Bild „abfahren“, diese also zwar schnell erfassen können, aber auch erzeugen, wenn man nur den Anfang des Plans hat. Dadurch nähern sie ein Bild erst dann gut an, wenn der Empfänger viele Detailstufen des Plans kennt. Dem kann man abhelfen, indem man den Stein rundherum ein wenig größer macht – dann verletzt er an sich die zweite Regel – und dann geschickt die Kanten anschrägt, vielleicht sogar nette Kurvenformen an den Kanten fräst. So entstehen glatte Bausteine. Allerdings hakt dann an dieser Stelle das Bild der Bauklötze, denn man kann sie nun nicht mehr so schön stapeln wie bisher, sondern muss sich vorstellen, dass die Bausteine wie kleine Nägel gebaut sind. Auf einer Ebene haben sie ihre Bauklotzform (mit den kurvigen Rändern), stellt man sie aufeinander, sacken die Nägel hinunter auf die Oberfläche der Bausteine unter sich und bilden so das Gebirge.

Möchte man diese Idee für ein gegebenes Bild und eine Menge von Bauklötzen auf dem Computer umsetzen, so gelangt man mathematisch in tiefe Raumtheorie, spätestens dann, wenn es darum geht, sowohl das Zerlegen eines Bildes als auch das Anzeigen schnell zu berechnen.

Das Erste ist die Analyse des Bildes und beschäftigt sich also zum Einen damit, wie gut die Bauklötze bestimmte Formen annähern können, die sogenannte Approximationsgüte. Zum Anderen aber damit, den Plan zu erzeugen, also Form und Position einzelner Bauklötze im Bild zu finden. Um das zu berechnen, müssen die Grundformen weitere – mathematische – Eigenschaften erfüllen. Ähnliche Probleme ergeben sich mathematisch auch beim – an sich gar nicht so kompliziert klingenden – Zusammenbau, der Synthese, des Bildes, vor allem, wenn diese schnell berechenbar sein soll.

Seinen Ursprung hat die Wavelet-Theorie zu Beginn der 1990er Jahre in der Verarbeitung von Audio-Signalen. Die Bauklötze waren zu Beginn Formen, die nur einen kleinen Bereich beschrieben und aus trickreich gewählten Sinus- und Kosinus-Summen gebildet wurden. Kleine – lokale – Wellen. Für Bilder ergibt sich die zusätzliche Herausforderung, den Bauklötzen Richtungspräferenzen mitzugeben. Wenn man beispielsweise ein Meer von oben fotografiert, wird es Wellen in eine bestimmte Richtung geben. Wählt man seine Grundformen so, dass sie diese berücksichtigen und kann diese kurz beschreiben, so wird der Plan zum Nachbauen sehr kurz. Denkt man weiter an 3D-Daten wie Videos, 4D-Daten wie Raumtemperaturvideos, so lässt sich das Prinzip auch da anwenden. Oder auf noch höheren Daten – das stelle man sich aber lieber nicht mehr vor. Auch hier liegt die Herausforderung darin, schnelle Algorithmen zu entwickeln, die kleine Beschreibungen der Daten erzeugen.

Noch keine Kommentare, sei der Erste!