Naturverbundene Computergrafik

Bionische Ansätze in der grafischen Datenverarbeitung

Trends & News | News

Berechnete Bilder sind unverzichtbar für die Naturwissenschaften, weil sie Prozesse und Daten visualisieren und Einsichten liefern. Doch es geht auch umgekehrt: Prinzipien aus der Natur eignen sich zur eleganten Lösung komplexer Probleme der Computergrafik.

Bionik bedeutet, raffinierte Prinzipen der Natur in Technik zu übertragen. So profitieren Schwimmer von Badeanzügen, die dank einer Haifischhautstruktur weniger Strömungswiderstand verursachen. Die Arbeitsgruppe von Professor Joachim Weickert von der Universität des Saarlands nutzt Bionik für die Bildverarbeitung. Auf der Konferenz Computer Graphics International 2013 (CGI) in Hannover zeigte Weickert, wie er und sein Team sich Prozesse bei der Osmose, aus Elektrostatik oder Wärmelehre zum Vorbild nehmen und damit zu besseren Lösungen für klassische Aufgaben der grafischen Datenverarbeitung kommen als konventionelle Algorithmen.

Permeable Pixel

Für Organismen ist die Osmose überlebenswichtig, denn sie steuert ihren Wasserhaushalt auf Zellebene. Eine halb durchlässige (semipermeable) Membran zwischen Zellen lässt Wasser hindurch, aber nicht die darin gelösten Stoffe. Der Vorgang lässt sich mathematisch über die sogenannten Drift-Diffusionsgleichungen simulieren, wie sie in ähnlicher Form beispielsweise in der Halbleiterphysik und der Plasmaphysik auftreten.

Etwas kreativer kann man das Prinzip für Collagen nutzen. Dabei platziert man einen Bildschnipsel auf einem Referenzbild und behandelt die Pixel an der Grenze zwischen den Teilen als Zellen. Den Grauwertübergang zwischen benachbarten Bildpunkten modelliert man als Teilchentransport durch eine virtuelle Membran, und zwar asymmetrisch, wie bei der Osmose. Dann lässt man den Prozess für den Bildschnipsel gegen das Referenzbild als Zielvorgabe konvergieren. Das Ergebnis ist eine nahtlose Montage zwischen beiden Teilen. Die vom Schnipsel überlagerten Teile des Referenzbilds verschwinden völlig. Osmose von Farbbildern ist ebenfalls kein Problem: Man behandelt jeden der RGB-Kanäle getrennt.

Während seiner Präsentation auf der CGI 2013 fügte Weickert kurzerhand osmotisch die Gesichtszüge des Mathematikers Lagrange in ein Porträt dessen Lehrmeisters und Mentors Euler ein. Die Methode eignet sich aber auch, um Schlagschatten aus Bildern herauszurechnen und Verfärbungen zu korrigieren.

Elektrisiert …

Auch die Physik liefert Inspiration für die grafische Datenverarbeitung: So kann man sich an der elektrostatischen Ladungsverteilung orientieren, um beispielsweise die Tonerpartikel beim Schwarzweißdruck eines Graustufenbilds so zu verteilen, dass der Eindruck von Verläufen und Schattierungen entsteht (Dithering).

Dazu verteilt man auf der Fläche des zu erzeugenden Bilds Punkte, die man wie negative Ladungen behandelt: Sie stoßen sich ab und verteilen sich gleichmäßig über das Bild. Dann fügt man dem Bilduntergrund positive Ladungen im Pixelraster des Ausgangsbilds hinzu, wobei dunklere Pixel stärker positiv geladen sind. Anschließend simuliert man, wie sich die negativ geladenen Punkte auf der Bildfläche im Spannungsfeld der Kräfte verteilen. Nimmt man statt Punkten Vektoren, entsteht ein Bild, das an eine Handzeichnung erinnert.

In der Mikroelektronik wird das Verfahren bereits industriell eingesetzt, etwa um Komponenten optimal auf der Grundfläche eines IC zu verteilen. Der Einsatz in der Computergrafik ist hingegen neu. Verglichen mit klassischen Dithering-Verfahren wie dem von Floyd und Steinberg liefert die elektrostatische Methode bessere Ergebnisse bei vergleichbarer Laufzeit – für Informatiker: O(n log n).

… und angewärmt

Besonderen Charme entwickelt das elektrostatisch inspirierte Verfahren in Kombination mit simulierter Wärmeleitung, genauer: dem Wärmefluss in einem ruhenden Medium, der durch einen Temperaturunterschied entsteht. Mit beidem zusammen kann man Bilder extrem stark komprimieren und anschließend fast ohne sichtbaren Verlust aus den verbleibenden Informationen wieder rekonstruieren.

Fürs Komprimieren wählt man einen kleinen Teil der Pixel aus, die für das Bild besonders wichtig sind. Hierbei kommt wieder das elektrostatische Halbtonverfahren zum Einsatz: Man behält nur jene Pixel, die sich an der Position eines der simulierten Ladungspunkte befinden – sie zeichnen sich durch einen besonders hohen Informationsgehalt für das gesamte Bild aus. Die übrigen Pixel werden verworfen.

Später, bei der Rekonstruktion der fehlenden Bildinformation, behandelt man die verbliebenen Pixel in Abhängigkeit von ihrem Farbwert als Wärmequellen, deren Temperatur sich iterativ an die Umgebung überträgt. Je nach gewählter Wärmeleitungsgleichung zeigen sich Unterschiede: Eine richtungsabhängige (anisotrope) Wärmeleitung erweist sich als recht robust, während eine homogene Temperaturausbreitung zwar einfacher zu berechnen ist, dabei aber stärker ins Gewicht fällt, ob bei der Komprimierung geeignete Pixel ausgewählt wurden.

Der Algorithmus rekonstruiert Bilder aus lediglich zehn Prozent der originalen Daten, ohne dass der Qualitätsverlust ins Auge springt. Vergleicht man die aus der Natur abgeschaute Methode mit aktuellen Kompressionsstandards wie JPEG und seinem Nachfolger JPEG 2000, die auf orthogonalen Transformationen beruhen (diskrete Cosinus-Transformation bei JPEG und diskrete Wavelet-Transformation bei JPEG 2000), zeigt sich bei extremen Kompressionsraten ab 80:1, dass das bionische Verfahren besser als die JPEG-Codecs arbeitet, es sei denn, die Bilder zeigen allzu unruhige Texturen.

Das Verfahren taugt nicht nur, um komprimierte Grafiken wiederherzustellen, sondern auch, um Löcher in beschädigten Bildern zu schließen. Außerdem kann man es benutzen, um geschickt Informationen in Bildern zu verstecken (Steganografie). Auf der Webseite der Arbeitsgruppe für mathematische Bildanalyse der Universität des Saarlandes kann man das selbst ausprobieren (siehe c’t-Link). Hier wird eine Person durch einen schwarzen Zensurbalken über dem Gesicht scheinbar anonymisiert. Für den Betrachter nicht erkennbar werden jedoch genügend Informationen unsichtbar in die Bilddaten gepackt, sodass sich der schwarze Balken mit Hilfe der Wärmeleitungssimulation jederzeit wieder wegrechnen lässt.

Interdisziplinär

Dass sich die grafische Datenverarbeitung wie in den geschilderten bionischen Beispielen bei Methoden anderer Wissenschaften bedient, ist allerdings immer noch die Ausnahme – viel häufiger liefern die Computergrafiker nützliche Werkzeuge für andere Disziplinen. Weitere Referenten auf der Konferenz CGI 2013 präsentierten beispielsweise Ansätze und Lösungen zur effizienten Darstellung von CAD-Modellen auf Smartphones oder für die 3D-Modellierung von Asteroiden nach Sondenfotos. Andere zeigten eine Methode, die aus einer Serie zweidimensionaler Porträtbilder einer Person eine Hohlform berechnet, die dank des Tiefenumkehr-Tricks (Hollow-Face-Illusion) wie eine Büste wirkt, die ihren Kopf stets auf den Betrachter richtet und dabei auch noch den Gesichtsausdruck verändert.

Dass man sich trotz der vielen praktischen Anwendungen nicht als Dienstleister für andere Bereiche, sondern als gleichberechtigte Wissenschaft sieht, wurde bei der Abschlussdiskussion zur Konferenz mehr als einmal betont. Das Podium war sich allerdings weitgehend einig, dass die Zukunft der grafischen Datenverarbeitung in der interdisziplinären Zusammenarbeit liegt: Ohne geeignete Visualisierungen erscheinen viele wissenschaftliche Großprojekte nicht mehr machbar, etwa das „Human Brain Project“ (HBP), das den Versuch unternimmt, das menschliche Gehirn in einem Computer möglichst genau zu modellieren (c’t 5/13, S. 40). Dabei sollen Unmengen von experimentellen Daten erfasst und zusammengeführt werden, um bestehende Wissenslücken zu erkennen und zu schließen – grafische Darstellungen können hier wichtige Erkenntnisse liefern. Professor Bodo Rosenhahn von der Leibniz Universität Hannover erinnerte die Kolleginnen und Kollegen in diesem Zusammenhang an ihre Verantwortung: Computergrafik und Visualisierungen sind keine Spielerei, sondern bilden oft auch die Grundlage für weitreichende Entscheidungen. (pek)

Artikel kostenlos herunterladen

weiterführende Links

Anzeige
Anzeige