Textursynthese
Textursynthese nennt man die automatische Erzeugung von Texturen, also zweidimensionalen digitalen Bildern, die Oberflächenstrukturen oder vergleichbare Inhalte zeigen. Es gibt zwei grundlegend verschiedene Arten der Textursynthese: Prozedurale Textursyntheseverfahren erzeugen aus dem Nichts eine neue Textur, vorlagenbasierte Verfahren ahmen eine gegebene Bildvorlage nach. Ziel beider Verfahren ist es, Bilder zu erzeugen, die von realen Vorbildern nicht zu unterscheiden sind.
Die Textursynthese bildet zusammen mit der Texturanalyse den gemeinsamen Forschungsbereich der Richtungen Bildverarbeitung, Computergrafik und Maschinelles Sehen, der sich den besonderen Eigenschaften von Texturen widmet. Neben der Textursynthese werden in diesem Fachbereich drei weitere Problemkreise untersucht: Texturklassifikation, die Unterscheidung verschiedener Texturarten anhand messbarer Eigenschaften, Textursegmentation, das Zerlegen eines Bildes in einheitlich texturierte Flächen und die Shape from Texture genannte Instanz der allgemeineren Fragestellung Shape from X, bei der aus einem zweidimensionalen Bild auf die dreidimensionale Form des abgebildeten Objekts geschlossen werden soll.[1]
Anwendung findet die Textursynthese in der Bildbearbeitung, z. B. wenn unerwünschte Details in einem digitalen Foto unauffällig retuschiert werden sollen oder die Materialbeschaffenheit eines abgebildeten Objekts verändert werden soll. In der 3D-Computergrafik dient sie dazu, dreidimensionale Modelle mit möglichst realistisch wirkenden Oberflächen zu überziehen und gleichzeitig den Speicherbedarf für Texturen zu reduzieren.
Texturen
Menschen erfassen den Begriff der Textur intuitiv, eine präzise und damit maschinell nachvollziehbare Ausformulierung gestaltet sich jedoch schwierig und ist eines der noch unerreichten Ziele der Texturanalyse.[1] Eine brauchbare Definition von Textur ist: Textur ist die Schwankung von Daten in einer Größenordnung, die kleiner ist als die Größenordnung, für die sich der Betrachter interessiert[2]. Ob eine Abbildung Textur ist oder nicht, ist danach eine Frage der Skalierung und des Standpunkts des Betrachters.
In der Textursynthese unterscheidet man zwei Texturartenextreme, die fließend ineinander übergehen: Regelmäßige oder deterministische Texturen zeigen ausgeprägte Strukturen, die sich mit geometrischer Regelmäßigkeit wiederholen, stochastische Texturen zeigen überhaupt keine Struktur, sondern erinnern an Bildrauschen. Für die Anwendungspraxis sind vor allem die in der Natur häufig anzutreffenden fast regelmäßigen und fast stochastischen Texturen von Interesse. Die Texturklassifikation kennt weitere Texturarten und unterteilt beispielsweise die regelmäßigen Texturen noch in geometrisch und farblich regelmäßige Texturen.[3]
Prozedurale Verfahren
Prozedurale Textursyntheseverfahren erzeugen Texturen aus dem Nichts. Der Benutzer wählt lediglich eine Reihe von numerischen Parametern – man spricht daher auch von parametrischer Textursynthese –, die an eine mathematische Funktion oder einen Algorithmus übergeben werden und die Ausgabe des Verfahrens beeinflussen.
Der Ursprung der parametrischen Textursynthese ist Perlin-Noise, eine 1982 von Ken Perlin für den Film Tron entwickelte mathematische Funktion, die Texturbilder durch zufällige Verzerrung abwechslungsreicher gestaltet. Eine systematische Forschung auf diesem Gebiet findet nicht statt, prozedurale Verfahren werden durch Versuch und Irrtum oder durch Zufall entdeckt.
Statt der eigentlichen Textur muss bei der prozeduralen Textursynthese nur das Verfahren gespeichert werden, mit dem die Textur erzeugt wird. Dies spart in der Regel extrem viel Speicherplatz und ist damit besonders für solche Szenarien von Interesse, in denen nur wenig Speicher zur Verfügung steht, z. B. in der Demoszene, wo aus nur 64 KB Speicher möglichst vielseitige Grafiken erzeugt werden sollen. Ein zweiter Pluspunkt ist, dass die prozedurale Textursynthese mitunter sehr schnell große Texturen erzeugt und sich damit zur Texturerzeugung on the fly für 3D-Computerspiele und ähnliche Anwendungen eignet, wo schnelle Reaktionszeiten garantiert werden müssen.
Stationarität
Für die Textursynthese sind hauptsächlich stationäre Texturen von Interesse: Wo immer der Blick gerade in einem solchen Bild umherwandert, man hat immer das Gefühl, das Gleiche zu sehen – gerade so als bewegte sich der Blick überhaupt nicht von der Stelle. In der Fachsprache sagt man, die Bildinformation sei gleichmäßig über das gesamte Bild verteilt.[2]
Markow-Ketten
Eine der wichtigsten mathematischen Grundlagen der Textursynthese ist die Erkenntnis, dass Texturen als Produkt einer Markow-Kette begriffen werden können. Die Aussage dieses Modells der Wahrscheinlichkeitstheorie lautet im Zusammenhang der Textursynthese: Jeder Bildpunkt einer Textur hängt nur von den Bildpunkten in seiner unmittelbaren Umgebung ab, jedoch nicht von den Bildpunkten außerhalb dieses fest eingrenzbaren Bereichs. Diese sogenannte Markow-Eigenschaft übersetzt die Eigenschaft der Stationarität in ein handfestes Berechnungsmodell und ist der mathematische Unterbau nahezu aller Textursyntheseverfahren.
Torusgeometrie
In der Anfangszeit setzte die Textursynthese auf das folgende geometrische Prinzip: Ein Bild, dessen rechter und linker sowie oberer und unterer Rand sauber zueinander passen, kann ohne sichtbare Nahtstellen beliebig oft aneinander angefügt werden. Weil sich dies besonders deutlich zeigt, wenn man das flache Bild zu einem Torus verformt, spricht man hier auch von Torusgeometrie. Der Geometrie der ebenen kristallographischen Gruppen pm und pmm zufolge lässt sich auch ein Bild mit beliebigen Rändern durch geeignetes Spiegeln nahtlos aneinanderreihen. Heute sind diese geometrischen Ideen von untergeordneter Bedeutung.
Algorithmen
Alle bislang entwickelten Algorithmen zur Textursynthese verfolgen entweder den Mosaikansatz oder den Pixelansatz. Beim Mosaikansatz wird das Ergebnisbild aus größeren Stücken der Vorlage zusammengesetzt, während es beim Pixelansatz Bildpunkt für Bildpunkt aufgebaut wird.
Ein Textursynthesealgorithmus erhält als Eingaben ein digitales Bild, die gewünschte Größe des Ausgabebildes sowie eventuell einige algorithmusspezifische Parameter, mit denen seine Funktionsweise näher bestimmt werden kann. Die Ausgabe des Algorithmus besteht aus dem synthetisierten Bild.
Stochastische Synthese
Bei der stochastischen Synthese wird das Ausgabebild Bildpunkt für Bildpunkt zusammengesetzt. Der Farbwert des gerade betrachteten Bildpunkts wird festgelegt, indem der Farbwert eines zufällig ausgewählten Pixels im Vorlagenbild übernommen wird. Diese Methode ist sehr schnell, funktioniert aber nur bei hochgradig stochastischen Texturen, d. h. wenn die Einzelteile der Textur höchstens einen Bildpunkt groß sind.
Kacheln
Von Kacheln (englisch tiling) spricht man, wenn die Vorlage wiederholt dupliziert und aneinandergefügt wird. Diese Methode ist schnell, erzeugt aber höchstens bei strukturierten Texturen befriedigende Ergebnisse; und nicht einmal dort immer. Erfüllt die Vorlage nicht spezielle Symmetriebedingungen, so ist im Endresultat deutlich erkennbar, wo die Duplikate aneinandergrenzen. Da sich der Bildinhalt in regelmäßigen Abständen wiederholt, ist das Ergebnis immer eine strukturierte Textur. Kacheln ist also für andere Texturklassen gänzlich ungeeignet. Spiegelt man die Duplikate wiederholt, so verschwinden zwar die Grenzen zwischen den Kacheln, der Wiederholungseffekt bleibt aber bestehen. Kacheln wird häufig zur Erstellung einfacher Hintergrundbilder für Websites und grafische Benutzeroberflächen angewandt.
Synthese nach Efros und Leung
Diese Technik wurde 1999 von Alexei A. Efros und Thomas K. Leung vorgestellt[4] und wird gemeinhin „Synthese nach Efros und Leung“, gelegentlich aber auch Image Growing genannt.
Hier wird zunächst ein leeres Bild mit den gewünschten Maßen erzeugt. In dieses Bild hinein wird die sogenannte Saat kopiert, ein kleines, zufällig ausgewähltes Stückchen der Vorlage. Dann wird das Bild, ausgehend von der Saat, in mehreren Durchgängen Pixel für Pixel befüllt. In jedem Durchgang werden zunächst alle an den bereits ausgefüllten Bildbereich angrenzenden Pixel bestimmt. Dann wird für jeden dieser Pixel eine Reihe von Bildpunkten in der Vorlage ermittelt, deren Umgebungen der Umgebung des neuen Bildpunkts möglichst ähnlich sind. Aus diesen wird ein Bildpunkt zufällig ausgewählt und dessen Farbe dem neuen Bildpunkt zugewiesen.
Qualität der Ergebnisse und Geschwindigkeit des Verfahrens sind von der Größe der betrachteten Umgebung, der sogenannten Randbreite, abhängig. Je strukturierter eine Textur ist, desto weiträumiger müssen die Umgebungen der Bildpunkte verglichen werden, bei stochastischen Texturen hingegen ist eine möglichst kleine Umgebungsgröße angezeigt, um keine unerwünschten Strukturen zu erhalten. Je größer die betrachtete Umgebung ist, desto langsamer ist der Algorithmus. Wird die Umgebungsgröße auf null gesetzt, so entspricht das Verfahren der stochastischen Synthese (s. o.).
Zahlreiche Nachfolgearbeiten (z. B.[5]) haben das Verfahren seitdem verfeinert, indem sie die vorhandenen Such- und Vergleichsaktionen algorithmisch optimierten.
Quilten
Beim Quilten wird das Ergebnisbild Flicken für Flicken aus der Vorlage zusammengesetzt. Für jede Flickenposition des Ausgabebildes werden in der Vorlage Bildteile gesucht, deren Umgebung der Umgebung des neuen Flickens möglichst ähnlich ist. Aus den ermittelten Teilen wird dann zufällig einer ausgewählt. Um die Übergänge zwischen den Flicken zu verstecken, wird der neue Flicken vor dem Einfügen zurechtgeschnitten, das heißt sein Rand wird so beschnitten, dass er sich möglichst gut in das bislang erzeugte Bild einfügt.
Quilten ist die qualitativ hochwertigste aber auch zeitaufwändigste Mosaiktechnik. Sie eignet sich für teilstrukturierte und teilstochastische Texturen sowie teilweise für strukturierte und stochastische Texturen. Liegt eine unstrukturierte Mustertextur vor, also eine mit nicht rein geometrisch begründeter Struktur, so wird das Ergebnis nur bedingt zufriedenstellend: Da strukturierte Objekte willkürlich zerschnitten und neu zusammengesetzt werden, können befremdliche Effekte entstehen; so mögen beispielsweise aus Tomaten der Güteklasse A zerstückelte oder verwachsene Tomaten werden. Hochgradig strukturierte Vorlagen liefern nur bei genügend großer Flickengröße befriedigende Ergebnisse, während hochgradig stochastische Vorlagen nach einer möglichst kleinen Flickengröße verlangen. Wird die Flickengröße auf einen Bildpunkt festgelegt, so entspricht Quilten der Technik des Image Growing (s. u.).
Chaosmosaik
Chaosmosaik wurde 2000 von Ying-Qing Xu, Baining Guo und Harry Shum in einem technischen Report der Forschungsabteilung der Firma Microsoft vorgestellt[7]. Die Technik verwendet eine „chaotische“ Form des Kachelns mit einer frei wählbaren untergeordneten Synthesetechnik; die Originalarbeit verwendete die pixelbasierte Textursynthese nach Efros und Leung.
Der erste Schritt von Chaosmosaik besteht darin, durch Kacheln ein Bild mit den gewünschten Maßen zu erstellen. Im zweiten Schritt werden in diesem Kachelbild zufällig ausgewählte Blöcke zufälliger Größe an zufällig ausgewählte Positionen kopiert. Ohne weitere Behandlung enthielte das Ergebnis sichtbare Fugen, wo der Bildinhalt des verschobenen Mosaikstücks nicht mit dem Untergrund zusammenpasst. Bei jedem dieser Kopiervorgänge wird daher um das neu eingefügte Mosaiksteinchen herum ein schmaler Rand ausgeschwärzt. Der geschwärzte Bereich wird in einem Unterschritt mit Hilfe des untergeordneten Syntheseverfahrens ausgefüllt. Diese Form des Chaosmosaik liefert gute Ergebnisse und benötigt wenig Speicherplatz. Die Geschwindigkeit wird hauptsächlich vom untergeordneten Syntheseverfahren bestimmt und ist für die Technik nach Efros und Leung langsam.
Xu, Guo und Shum präsentierten daher gleichzeitig eine abgewandelte Form, um den Forderungen nach einem schnellen Syntheseverfahren für 3D-Computergrafiken entgegenzukommen. In dieser Variante wird kein Ausschwärzen und nachfolgendes Wiederauffüllen verwendet. Stattdessen werden die Ränder der Mosaikteile mit einem Glättungsfilter geglättet, wodurch harte Kanten und scharfe Farbübergänge verschwimmen. Die Ergebnisse sind schlechter als im ursprünglichen Verfahren, werden aber mit einem erheblichen Geschwindigkeitszuwachs belohnt, da Filter sehr effizient angewandt werden können.
Textursynthese mit Binärbaum-basierter Vektorquantisierung
Dieser Algorithmus wurde 2000 von Li-Yi Wei und Marc Levoy vorgeschlagen[8]. Er erweitert das Verfahren von Efros und Leung um einen Multiskalenansatz und verwendet einen effizienteren Suchalgorithmus.
Zunächst wird ein Bild mit den gewünschten Ausgabemaßen erzeugt, das mit zufälligen Farbwerten (weißes Rauschen) aufgefüllt wird; im Folgenden wird dieses Bild so verändert, dass es am Ende die synthetisierte Textur enthält. Nun wird aus dem Vorlagebild und dem Rauschbild jeweils eine Multiskalenpyramide erstellt: Durch wiederholtes Filtern werden aus dem Ursprungsbild nacheinander Bilder erzeugt, die jeweils etwa halb so groß sind wie ihr Vorgängerbild; der Größe nach angeordnet bilden diese eine Pyramide, mit dem Ursprungsbild zuunterst. Die Art des Filters hängt vom Anwendungszweck ab, Wei und Levoy verwendeten einen Gaußfilter, denkbar sind aber auch Laplace- oder Waveletfilter; einen Überblick über Filterung bietet der Artikel Bildverarbeitung.
Bei der Synthese werden von oben nach unten die Bilder der Rauschbildpyramide mit dem Verfahren nach Efros und Leung gefüllt. Dabei beinhaltet die Umgebung eines Pixels nicht nur die Pixelumgebung im selben Bild, sondern auch Pixel aller darüberliegenden Pyramidenbilder, die an etwa derselben Stelle im Bild liegen. Dieser Vergleich auf mehreren Auflösungsstufen zur gleichen Zeit ist der Inbegriff der Multiskalenanalyse und sorgt dafür, dass sich das Syntheseverfahren selbständig Strukturen verschiedener Größe in der Vorlage anpasst.
Dieser Multiskalenansatz wird durch die Binärbaum-basierte Vektorquantisierung (tree-structured vector quantization, TSVQ) ergänzt. Zentraler Bestandteil dieses Verfahrens, das eigentlich der Datenkompression dient, ist ein Binärbaum, in dessen Knoten Vektoren untergebracht sind. Jeder Vektor enthält neben einem Pixel eines Bildes der Vorlagepyramide alle Pixel der Umgebung dieses Pixels (inklusive denen auf höheren Pyramidenebenen), jeder Knoten enthält den mittleren Durchschnittsvektor aller seiner Kinder. In dieser Datenstruktur kann deutlich schneller nach ähnlichen Kandidaten gesucht werden als im Ursprungsbild.
Obwohl bei dieser Technik statt einzelner Bilder ganze Bilderpyramiden synthetisiert werden müssen und vor der ersten Synthese zunächst der Binärbaum aufgebaut werden muss, ist dieser Algorithmus erheblich schneller als sein Vorgänger. Zusätzlich deckt er durch die Multiskalenanalyse einige Texturarten besser ab.
Weblinks
- Texture Synthesis by Non-parametric Sampling – Homepage von A. A. Efros und T. K. Leung mit Zusatzinformationen und Beispielbildern
- Revolution der virtuellen Welten – Procedural Textures – Artikel zum Einsatz von Prozeduralen Texturverfahren in Anwendungen mit interaktiven Beispielen
Einzelnachweise
- M. Tuceryan, A. K. Jain: Texture Analysis. In: C. H. Chen, L. F. Pau, P. S. P. Wang (Editoren): The Handbook of Pattern Recognition and Computer Vision (2nd Edition). World Scientific Publishing Co., 1998, Kapitel 2.1, S. 207–248.
- M. Petrou, P. G. Sevilla: Image Processing: Dealing With Texture. Wiley, 2006. ISBN 0-470-02628-6
- Y. Liu, W.-C. Lin, J. Hays: Near-Regular Texture Analysis and Manipulation. 2004
- A. A. Efros, T. K. Leung: Texture Synthesis by Non-parametric Sampling. In: Proceedings of IEEE International Conference on Computer Vision, Corfu, Greece, September 1999. PDF 1 MB
- M. Ashikhmin: Synthesizing Natural Textures. (PDF; 2 MB) In: The proceedings of 2001 ACM Symposium on Interactive 3D Graphics, Research Triangle Park, NorthCarolina March 19-21. S. 217–226
- Image Quilting for Texture Synthesis and Transfer, Alexei A. Efros en Willian T. Freeman (englisch)
- B. Guo, H. Shum, Y.-Q. Xu: Chaos Mosaic: Fast and Memory Efficient Texture Synthesis. Microsoft Research MSR-TR-2000-32, April 2000. PDF 8 MB
- L.-Y. Wei, M. Levoy: Fast Texture Synthesis using Tree-structured Vector Quantization. (PDF; 4,5 MB)