Image Growing

Image Growing (englisch „Bildanbau“), gemeinhin auch „Textursynthese nach Efros und Leung“ genannt, ist ein nichtparametrischer Textursynthesealgorithmus. Die Technik wurde 1999 von Alexei A. Efros und Thomas K. Leung vorgestellt.

Ziel der nichtparametrischen Textursynthese ist es, aus einem Vorlagebild automatisch neue Bilder zu erzeugen, die der Vorlage zwar möglichst ähnlich sehen, aber nicht identisch mit ihr sind. Image Growing lässt aus einer Rastergrafik Pixel für Pixel ein neues, ähnliches digitales Bild „wachsen“.

Funktionsweise

Es gibt zwei Varianten dieser Technik, die sich nur unwesentlich unterscheiden. Beim eigentlichen Image Growing ist in einem größtenteils leeren Bild ein kleines Stück der Vorlage als Saat untergebracht. Anschließend lässt der Algorithmus Pixel für Pixel um die Saat herum die Textur „wachsen“. Sind alle leeren Bildbereiche vollständig gefüllt, so ist die Synthese beendet; die Textur kann „geerntet“ werden. In der Variante Hole Filling ist die Ausgangssituation gerade andersherum: Ein größtenteils ausgefülltes Bild enthält einige Löcher, leere Stellen, die vom Algorithmus gefüllt werden. Die Funktionsweise ist in beiden Fällen dieselbe.

Um einen Pixel zu setzen sucht Image Growing in der Vorlage nach Pixeln, die eine ähnliche Umgebung aufweisen und fasst diese zu einer Kandidatenliste zusammen. Der neue Pixel übernimmt den Farbwert eines zufällig aus dieser Kandidatenliste ausgewählten Pixels.

Eingabe

Der Algorithmus erhält in seiner Grundform drei Eingaben:

• Vorlage: Als Vorlagebild kann jedes beliebige digitale Bild dienen. Größe, Inhalt, Grafikformat, Farbtiefe und Farbraum sind aus Sicht des Algorithmus egal und hängen nur von der jeweiligen Implementierung und der verwendeten Hardware ab.
• Vorbereitete Ausgabe: Dies ist ein digitales Bild mit den Wunschmaßen der Ausgabe. Es enthält sowohl Pixel mit Bildinhalt als auch Pixel mit einem besonderen Farbwert leer. Der Algorithmus arbeitet auf diesem Bild und füllt alle als leer markierten Pixel auf. Nach Beendigung des Algorithmus enthält dieses Bild die synthetisierte Textur. Der Farbwert leer darf nicht in der Vorlage vorkommen, nach Möglichkeit sollte es sich überhaupt nicht um einen gültigen Farbwert handeln.
• Umgebung: Diese Filtermaske gibt an, welche Pixel zur Umgebung eines Pixels gehören und wie stark sie beim Umgebungsvergleich berücksichtigt werden. Anschaulich handelt es sich um eine Matrix mit ungerader Zeilen- und Spaltenanzahl, die Zahlen zwischen 0 und 1 enthält, die sich zu 1 aufsummieren; je größer eine Zahl, desto bedeutender ist der zugehörige Pixel beim Umgebungsvergleich. Der mittlere Eintrag wird ignoriert und kann daher einen beliebigen Wert enthalten. Details zum komplexen Thema Filtermasken bietet der Artikel Bildverarbeitung.

${\tfrac {1}{16}}\cdot {\begin{pmatrix}1&2&1\\2&4&2\\1&2&1\end{pmatrix}}$
Gauß-ähnliche 3x3-Umgebung.

Neben diesen Hauptargumenten benötigt der Algorithmus einen weiteren Parameter, der entweder als Benutzereingabe abgefragt oder fest im Algorithmus vorgegeben werden kann:

• Schwellenwert: Der Schwellenwert gibt an, ab welcher Umgebungsähnlichkeit ein Pixel als Kandidat zählt. Der Wert ist größer oder gleich 0 und nach oben potenziell unbeschränkt. Je geringer der Wert ist, desto ähnlicher müssen sich die Umgebungen sein.

Algorithmus

1. Bestimme die Menge der leeren Pixel, die in diesem Durchlauf gesetzt werden. Dies sind alle Pixel des Ausgabebildes, die senkrecht, waagrecht oder diagonal direkt an einen nichtleeren Pixel angrenzen. Falls es keine leeren Pixel mehr gibt, beende den Algorithmus.
2. Wähle einen beliebigen Pixel aus der Menge der leeren Pixel. Für diesen Pixel wird jetzt in einer inneren Schleife die Kandidatenliste erstellt:
   1. Wähle einen in dieser inneren Schleife bisher noch nicht betrachteten Pixel des Vorlagebilds.
   2. Lege Vorlagebild, Ausgabebild und Filtermaske so übereinander, dass die gerade betrachteten Pixel und das Zentrum der Filtermaske direkt übereinander liegen; im Folgenden wird nur der Bereich unter der Filtermaske betrachtet. Ziehe die übereinander liegenden Farbwerte der beiden Bilder jeweils voneinander ab, nimm den Betrag und multipliziere diesen mit der darüberliegenden Zahl der Filtermaske. Addiere alle ermittelten Werte. Wichtig: Pixel, die leer sind, und Bereiche, in denen sich die Bilder nicht überlappen, werden vollständig ignoriert.
   3. Ist der gerade ermittelte Wert kleiner als der Schwellenwert, so füge den betrachteten Vorlagenpixel der Kandidatenliste hinzu. Falls noch nicht alle Pixel der Vorlage betrachtet wurden, weiter bei 2.1.
3. Wähle zufällig einen Pixel der Kandidatenliste aus und weise dessen Farbwert dem momentan betrachteten Pixel des Ausgabebildes zu.
4. Entferne den eben gesetzten Pixel aus der Menge der leeren Pixel. Falls die Menge leer ist, zurück zu 1, ansonsten zu 2.

Ausgabe

Die Ausgabe des Algorithmus besteht aus dem synthetisierten Bild, das sich in der veränderten vorbereiteten Ausgabe befindet.

Theorie

Eine Textur in der Textursynthese ist immer ein stationäres Bild, d. h. alle Teile des Bildes sehen sich ähnlich; betrachtet man verschiedene Bereiche einer solchen Textur durch ein kleines Sichtfenster, so hat man den Eindruck, immer dasselbe zu sehen. Diese besondere Eigenschaft macht sich die Textursynthese nach Efros und Leung zunutze, indem sie Textur als Markow-Netzwerk modelliert. Ein Markow-Netzwerk besteht aus miteinander verbundenen Objekten, sogenannten Knoten, die verschiedene Zustände einnehmen können. In einem solchen Markow-Netzwerk gilt die sogenannte Markow-Eigenschaft: Der Zustand jedes Knotens ist von den Zuständen der ihn in einem örtlich begrenzten Umfeld umgebenden Pixel abhängig.

In einer Textur stellt jeder Pixel einen Knoten in einem Markow-Netzwerk dar, wobei jeder Pixel mit seinen acht Nachbarpixeln verbunden ist. Das örtlich begrenzte Umfeld ist durch die Umgebungsmaske vorgegeben; diese gibt nicht nur an, wie groß das Umfeld ist, sondern auch, wie ein Pixel durch seine Nachbarn beeinflusst wird. Die Markow-Eigenschaft ist dabei eng mit der Stationarität verwandt; versucht man, ein nichtstationäres Bild in ähnlicher Weise zu modellieren, so stellt man fest, dass der Zustand eines Pixels von allen anderen Pixeln abhängt.

Beurteilung

Image Growing erzeugt qualitativ hochwertige Bilder, wenn die Parameter richtig gewählt werden. In der Regel gilt: Je größer die Filtermaske, desto besser die Ergebnisse. Die Größe sollte so gewählt sein, dass die Filtermaske die größte in der Vorlage vorkommende Struktur abdeckt.

A. A. Efros und T. K. Leung bemerkten einen wichtigen Schwachpunkt bereits selbst: Manchmal versteift sich der Algorithmus bei seiner Suche nach Kandidaten auf einen kleinen Teilbereich der Vorlage und produziert ab da unbefriedigende Ergebnisse. Größere Strukturen zerfallen dann nach und nach zu Bildrauschen oder Vorlagenteile werden identisch kopiert.

Laufzeit

Nach dem klassischen Modell der Registermaschine haben folgende Parameter Einfluss auf die Laufzeit des Algorithmus:

• Anzahl n der Pixel im Vorlagebebild.
• Anzahl m der Pixel im Ausgabebild.
• Anzahl b der Tabellenzellen der Filtermaske.

Die Laufzeit wird asymptotisch nach oben abgeschätzt durch O(m·n·b). Dabei wird die wiederholte Suche nach noch leeren Pixeln großzügig vernachlässigt, da sie je nach Verfahren und Fortschritt sehr unterschiedlich ausfallen kann. Da für gewöhnlich m >> n und b > 1 gilt, ist diese Laufzeit deutlich schlechter als O(n²). Der Algorithmus ist damit selbst auf schnellen Rechnern sehr langsam.

Speicherbedarf

Der Speicherbedarf des Algorithmus ist vergleichsweise gering. Er variiert mit der Zeit mit der Größe der Menge der zu setzenden Pixel und der Größe der Kandidatenliste, für diese lassen sich jedoch die Bildergrößen als obere Schranken einsetzen.

Verbesserungsansätze

Leere Pixel

Im Originalansatz wird das Bild bei jedem Durchlauf vollständig durchsucht, um diejenigen leeren Pixel herauszusuchen, die im kommenden Durchlauf gesetzt werden. Diese erschöpfende Suche ist alles andere als optimal und kann beschleunigt werden.

Ein einfacher Ansatz ist es, Größe, Form und Positionierung der Saat fest vorzuschreiben. Dadurch ist es möglich, in jedem Schritt die nächsten leeren Pixel vorauszusagen, ohne sie überhaupt betrachten zu müssen. Dieser Ansatz ist insbesondere beim Hole Filling nicht praktikabel, wo Position, Größe und Form der leeren Bereiche nicht vorbestimmt werden können. Auch ist bei der Positionierung der Saat in der Bildmitte ein leichter Qualitätsgewinn zu beobachten.

Kompliziertere Ansätze verwenden zusätzliche Datenstrukturen, die im Voraus erzeugt werden, und schnelleres Suchen nach leeren Pixeln ermöglichen. So wäre beispielsweise ein Graph denkbar, in dem jeder Pixel auf diejenigen Pixel verweist, die gesetzt werden können, sobald der Pixel selbst gesetzt wurde.

Kandidatenliste

Auch der Aufbau der Kandidatenliste kann durch Einbeziehung zusätzlicher Suchstrukturen beschleunigt werden. So schlägt beispielsweise die Textursynthese mit Binärbaum-gestützter Vektorquantisierung einen speziellen Binärbaum vor, in dem die Pixel inklusive ihrer Umgebungen geschickt angeordnet werden.