Institut für Visualisierung und Interaktive Systeme
Abteilung Visual Computing
Universität Stuttgart
Universitätsstraße 38
D - 70569 Stuttgart
Diplomarbeit Nr. 3694
Automatisierte Zerlegung von Bildern und die
geordnete Darstellung ihrer Konstituenten
Sven Klingel
Studiengang: Informatik
Prüfer: Jun.-Prof. Dr.-Ing. Martin Fuchs
Betreuerin: Lena Gieseke M.F.A.
begonnen am: 1. Oktober 2014
beendet am: 2. April 2015
CR-Klassifikation: I.4.6, I.3.3

Kurzfassung
Die Neuanordnung von Bildsegmenten stellt ein bislangwenig un-
tersuchtes Gebiet der Bildsynthese dar. In dieser Arbeit werden
zunächst bereits bekannte Verfahren zur Zerlegung von Farb-
bildern in Konstituenten auf ihre Tauglichkeit hin untersucht.
Anschließend werden verschiedene Techniken zur Anordnung
dieser Bildteile unter ästhetischen Gesichtspunkten entwickelt
und in einer Nutzerstudie evaluiert.
BildMosaik Neuanordnung
iii

Inhaltsverzeichnis
1 Einleitung 1
1.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Aufgabenstellung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.3 Gliederung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
2 Grundlagen 3
2.1 Farbmodelle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2.1.1 Farbräume . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2.1.2 Farbmetriken . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2.1.3 Überblick über bekannte Farbmodelle . . . . . . . . . . . . . . . . . . . . . 4
2.2 Farbbilder . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
3 Verwandte Arbeiten 7
3.1 Segmentierung von Bildern . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
3.2 Anordnung von Objekten . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
4 Segmentierung von Farbbildern 9
4.1 Segmentierungsklassen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
4.1.1 Regionenbasiert . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
4.1.2 Kantenfindungsbasiert . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
4.1.3 Merkmalsraum Clusteranalyse . . . . . . . . . . . . . . . . . . . . . . . . . . 10
4.2 Vergleich der Klassen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
4.2.1 Rückgabetyp . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
4.2.2 Benutzbarkeit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
4.2.3 Robustheit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
4.3 Implementierte Verfahren . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
4.3.1 Mean Shift Segmentierung . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
4.3.2 Wasserscheidentransformation . . . . . . . . . . . . . . . . . . . . . . . . . 14
5 Anordnung von Bildsegmenten 17
5.1 Abgrenzung zu anderen Transformationen . . . . . . . . . . . . . . . . . . . . . . . 17
5.2 Handhabung des Bildhintergrundes . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
5.2.1 Extrahieren des Hintergrunds . . . . . . . . . . . . . . . . . . . . . . . . . . 19
5.2.2 Übertragen des Hintergrunds . . . . . . . . . . . . . . . . . . . . . . . . . . 20
5.3 Segmentmerkmale als Ordnungskriterien . . . . . . . . . . . . . . . . . . . . . . . 21
5.3.1 Merkmale im Ortsraum . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
5.3.2 Merkmale im Farbraum . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
5.3.3 Skalierung der Merkmale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
5.4 Zweistufiger Ansatz . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
5.4.1 Aufbau des initialen Layouts . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
5.4.2 Verfeinerung des initialen Layouts . . . . . . . . . . . . . . . . . . . . . . . 25
v
Inhaltsverzeichnis
5.5 Hierarchische Erweiterung durch Clustering . . . . . . . . . . . . . . . . . . . . . . 27
5.5.1 Clusterung im Merkmalsraum . . . . . . . . . . . . . . . . . . . . . . . . . . 27
5.5.2 Kreisförmige Cluster . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
5.5.3 Stapelförmige Cluster . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
6 Ergebnisse 29
6.1 Qualitative Ergebnisse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
6.1.1 Segmentierung von Farbbildern . . . . . . . . . . . . . . . . . . . . . . . . . 29
6.1.2 Anordnung von Bildsegmenten . . . . . . . . . . . . . . . . . . . . . . . . . 29
6.2 Evaluierung anhand einer Benutzerstudie . . . . . . . . . . . . . . . . . . . . . . . 30
6.2.1 Aufgabenstellung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
6.2.2 Durchführung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
6.2.3 Auswertung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
7 Ausblick 31
7.1 Zusammenfassung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
7.1.1 Zerlegung von Farbbildern . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
7.1.2 Anordnung der Konstituenten . . . . . . . . . . . . . . . . . . . . . . . . . . 31
7.2 Künftige Arbeiten . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
7.2.1 Verbesserungen des Bestehenden . . . . . . . . . . . . . . . . . . . . . . . . 31
7.2.2 Neues und Aufbauendes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
A Weitere Abbildungen 33
B Beispielimplementierung 35
Literaturverzeichnis 37
Bildverzeichnis 41
Erklärung 43
vi
Abbildungsverzeichnis
4.1 Schema des Mean Shift Verfahrens . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
4.2 Verarbeitungsschritte der Mean Shift Segmentierung am Bild Venus . . . . . . . . 13
4.3 Verarbeitungsschritte der Wasserscheidentransformation am Bild Venus . . . . . 15
5.1 Verschiedene Beispiele für Bildhintergründe . . . . . . . . . . . . . . . . . . . . . 18
5.2 Schema der Kollisionsverhinderung inklusive Rotation . . . . . . . . . . . . . . . 26
5.3 Beispiel des zweistufigen Ansatzes am BildMoulin Rouge . . . . . . . . . . . . . . . 26
5.4 Beispiel der verschiedenen Clusterformen am Bild Krawatten . . . . . . . . . . . . 28
6.1 Vergleich von Mean Shift und Wasserscheidentransformation am Bild Seemonster 29
A.1 Auswirkung der Kernelradien beim Mean-Shift-Filter am Bild Venus . . . . . . . . 33
A.2 Streudiagramm-Matrix der Segmentmerkmale für das Bild Holzfäller . . . . . . . 34
B.1 GUI der Beispielimplementierung tidy . . . . . . . . . . . . . . . . . . . . . . . . . . 35
Tabellenverzeichnis
4.1 Segmentierungsklassifizierungen nach Cheng et al. und Raut et al. . . . . . . . . . 9
vii

1 Einleitung
1.1 Motivation
Der Schweizer Kabarettist Ursus Wehrli erlangte durch das „Aufräumen“ von Kunst erstmals
selbst Bekanntheit als bildender Künstler. Dazu zerschnitt er Nachdrucke von Kunstwerken in
einzelne Teile und ordnete diese neu an. Die Entscheidungen, wie er ein Bild zerlegte und nach
welchen Kriterien er die Bildteile anordnete, bildeten hierbei den kreativen Prozess der neue
Kunst entstehen ließ. [Weh02, Weh04]
Es stellt sich nun die Frage, wie weit sich dieser kreative Prozess nachbilden und automatisieren
lässt. Ein solcher Automatismus ermöglicht seinerseits weitere interessante Fragestellungen. Bei-
spielsweise welche Anordnungsprinzipien von Betrachtern generell als ästhetisch ansprechender
empfunden werden als andere.
1.2 Aufgabenstellung
Ziel dieser Arbeit ist es, Algorithmen zu finden um Farbbilder automatisch zu zerlegen und die
entstehenden Segmente in visuell ansprechender Form neu anzuordnen. Die konkrete Aufgaben-
stellung umfasst dabei folgende Punkte:
• Vergleich verschiedener Segmentierungsverfahren
Zunächst muss ein Überblick über die bereits existierenden Segmentierungsalgorithmen
gebildet werden. Diese sollen daraufhin hinsichtlich ihrer Eignung für die Zerlegung von
Bildern in semantisch sinnvolle Konstituenten verglichen werden. Ausgehend davon soll
schließlich mindestens ein Verfahren zur näheren Untersuchung ausgewählt werden.
• Finden von Verfahren zur Anordnung von Segmenten
Angestrebt werden Anordnungen, die für einen menschlichen Betrachter sinnvoll erschei-
nen. Hierzu muss zuerst sondiert werden, welche Segmentmerkmale sich als Kriterien
zur Sortierung eignen. Danach sollen Heuristiken entwickelt werden um Anordnungen
basierend auf eben solchen Sortierungskriterien zu erstellen.
• Implementieren eines Prototypen
Um sowohl die Segmentierungs- als auch die Anordnungsverfahren überprüfen und ver-
gleichen zu können, sollen sie in Form eines Prototyps implementiert werden.
• Durchführen einer Nutzerstudie
Zur schlussendlichen Evaluation der entwickelten Sortierungskriterien und Anordnungsal-
gorithmen soll eine Nutzerstudie durchgeführt werden.
1
1 Einleitung
1.3 Gliederung
Die Arbeit ist wie folgt aufgebaut:
Kapitel 1 – Einleitung
Hier wird die zugrundeliegende Motivation zu dieser Arbeit und die daraus hervorgegangene
Aufgabenstellung erläutert. Zusätzlich wird dieser Überblick über die Gliederung geboten.
Kapitel 2 – Grundlagen
Um die folgenden Kapitel übersichtlich halten zu können, werden hier vorab grundlegende
Begriffe, die später als bekannt angenommen werden, genauer ausformuliert und definiert.
Kapitel 3 – Verwandte Arbeiten
In diesem Kapitel werden thematisch ähnliche Arbeiten anderer Autoren vorgestellt, um den
Stand der Forschung zu sondieren und die Ansätze zu differenzieren.
Kapitel 4 – Segmentierung von Farbbildern
Da die Segmentierung von Farbbildern bereits gut untersucht ist, werden in diesem Kapitel die
bekannten Ansätze verglichen und passende zur weiteren Verwendung ausgesucht.
Kapitel 5 – Anordnung von Bildsegmenten
Hier werden schließlich neue Verfahren zur Anordnung von Bildsegmenten entwickelt und
vorgestellt.
Kapitel 6 – Implementierungsdetails
Auf die Besonderheiten und Details der im Rahmen dieser Arbeit entstandenen Beispielimple-
mentierung wird in diesem Kapitel eingegangen.
Kapitel 7 – Ergebnisse
Die Qualität der entwickelten Verfahren und der daraus resultierenden Anordnungen werden in
diesem Kapitel diskutiert und mittels einer Nutzerstudie evaluiert.
Kapitel 8 – Ausblick
Abschließend wird in diesem Kapitel darauf eingegangen, wie die Algorithmen weiter verfeinert
oder erweitert werden könnten und welche künftigen Anwendungen dadurch ermöglicht werden.
2
2 Grundlagen
Damit die folgenden Kapitel übersichtlich bleiben, werden hier grundlegende Begriffe genauer
erläutert und ausformuliert. Da die im Rahmen dieser Arbeit entstandenen Verfahren vornehm-
lich mit Farbbildern arbeiten, soll zunächst gezeigt werden wie Farben mittels Farbmodellen in
mathematischen Strukturen dargestellt werden können. Darauf aufbauend werden Farbbilder
selbst als Abbildungen auf eben diese Strukturen definiert.
2.1 Farbmodelle
UmFarben als solche in einemmathematischen Kontext verwenden zu könnenmuss der abstrakte
Begriff zunächst formalisiert werden. Ein Farbmodell gibt hierzu an auf welche Weise Farben als
n-Tupel von Zahlen dargestellt werden können.
Den ersten bis heute gültigenAnsatz lieferte bereits 1853HermannGraßmann [Gra53]mit seiner
„Theorie der Farbenmischung“. Darin beschreibt er, wie sich farbiges Licht in „drei mathematisch
bestimmbare Momente“ zerlegen lässt.
„Hiernach haben wir also bei jedem Lichteindruck Dreierlei zu unterscheiden: die Intensität
der Farbe, den Farbenton, die Intensität des beigemischten farblosen Lichtes.“
— H. Graßmann, 1853
Die beiden Intensitäten lassen sich demnach jeweils auf ein Intervall der Art [Imin, Imax] ⊂ R ab-
bilden. Für den „Farbenton“ schlägt Graßmann aufgrund einer Falschannahme1 die Verwendung
der Wellenlänge vor. Ersetzt man diese jedoch durch den Winkel im Farbkreis, einer zyklischen
Anordnung aller Farbtöne, kann auch dieserMoment auf beispielsweise das Intervall (−pi, pi] ⊂ R
abgebildet werden.
Basierend auf dieser Erkenntnis lässt sich eine vonMenschenwahrgenommene2 Farbe f folglich
eindeutig als Tripel aus reellen Zahlen darstellen.
f : (f1, f2, f3) ∈ R3
2.1.1 Farbräume
Für die Mischung solcher Farbtupel postulierte Graßmann selbst bereits Rechengesetze, die er
mangels der nötigen Notationen noch weitestgehend frei formulierte [Gra53]. Als die Mathematik
1975 schließlich die nötigen Werkzeuge parat hielt, formalisierte David Krantz diese Gesetze und
fasste siemit derMenge der Farbtupel F ⊂ R3 zu einer „Graßmann Struktur“ (F,⊕,) zusammen.
Davon ausgehend zeigte er, dass eine Farbmischung nach diesen Gesetzen einer Linearkombina-
tion entspricht und somit eine solche Struktur einen Vektorraum, genannt Farbraum, darstellt.
[Kra75]
1Graßmann ging davon aus, dass die fiktive Farbe „Purpur“ sowohl Infrarot als auch Ultraviolett entspricht und den
Farbkreis somit bereits lückenlos schließt.
2Andere Eigenschaften des Lichtes, wie z.B. die spektrale Zusammensetzung oder Polarisation, werden in diesem Modell
nicht berücksichtigt, können vom Menschen jedoch auch nicht wahrgenommen werden.
3
2 Grundlagen
Die Farbtupel lassen sich folglich als Koordinaten im Farbraum F , die sogenannten Farbörter,
interpretieren. Das zugrundeliegende Farbmodell gibt dabei die Art der Koordinaten vor. Für ein
Modell nach Graßmann ergibt sich beispielsweise ein Farbraum mit Zylinderkoordinaten.
2.1.2 Farbmetriken
Eine Metrik ist eine Abbildung, die einem Elementenpaar eines metrischen Raumes einen re-
ellwertigen Abstand zuordnet. Da Vektorräume und somit auch Farbräume bekanntermaßen
metrisch sind, können solche Abstandsfunktionen auch auf ihnen als Farbabstand ∆E definiert
werden.
∆E : F × F → R
Ein solcher Farbabstand kann verwendet werden um Farbähnlichkeiten zu messen, indem ein
geringerer Abstand mit einer größeren Ähnlichkeit gleichgesetzt wird. Problematisch ist dabei
allerdings, dass Farbpaare mit gleichem Abstand innerhalb eines Farbraumes von menschlichen
Betrachtern nicht zwingend als gleich ähnlich empfunden werden. [DIN11]
2.1.3 Überblick über bekannte Farbmodelle
Im Laufe der Zeit wurden für verschiedene Anwendungsgebiete zahlreiche Farbmodelle entwi-
ckelt, die wiederum auf unterschiedliche Arten klassifiziert werden können. An dieser Stelle soll
deshalb nur ein grober Überblick über die bekanntesten Modelle geschaffen werden, bei dem nur
an relevanter Stelle weiter ins Detail gegangen wird.
Darstellungsorientierte Modelle
Modelle dieser Klasse orientieren sich an der Funktionsweise von Ausgabegeräten. Dadurch lassen
sich die Farbtupel ohne Umrechnung auf entsprechenden Geräten ausgeben. Für Menschen sind
sie jedoch oft schwer zu interpretieren und gleiche Farbabstände werden selten als gleich ähnlich
empfunden.
Ein weit verbreitete Beispiel bildet das RGB-Farbmodell, bei dem die Farben aus den drei Grund-
farben Rot, Grün und Blau zusammengesetzt werden. Es wird vor allem in Verbindung mit selbst-
leuchtenden Ausgabegeräten wie Monitoren verwendet, welche die Anzeigefarben ebenfalls nach
diesem Prinzip erzeugen.
Wahrnehmungsorientierte Modelle
Im Gegensatz zu den Darstellungsorientierten Modellen richten sich diese an der menschlichen
Farbperzeption aus. Die Farbtupel müssen hierbei zur Ausgabe zwar meist konvertiert werden,
sind dafür jedoch von Menschen einfach als Farbeindruck interpretierbar. Die Modelle lassen
sich dabei noch weiter in zwei Gruppen unterteilen.
Lineare Modelle lassen sich durch lineare Transformationen in DarstellungsorientierteModelle
umrechnen. Sie bieten folglich trotz intuitiver Handhabung eine effiziente Ausgabe, haben jedoch
noch das selbe Problem der nicht vergleichbaren Farbabstände.
Ein Beispiel hierfür stellt das HSV-Modell dar. Es basiert auf den Überlegungen von Graßmann
und setzt eine Farbe aus den drei Komponenten Farbwinkel (hue), Sättigung (saturation) und
Hellwert (value) zusammen.
4
2.2 Farbbilder
Nichtlineare Modelle versuchen die Farbabstände durch nichtlineare Transformationen an die
menschliche Farbwahrnehmung anzupassen. Um die Abstände zusätzlich noch verständlicher zu
gestalten wurde vorgeschrieben dass ein Farbabstand von ∆E = 1 die Grenze zum gerade noch
wahrnehmbaren Farbunterschied darstellen soll.
Unter diesen Bedingungen entstand 1976 das CIE L*a*b*-Farbmodell. Die Farben werden hierbei
ähnlich der Farbwahrnehmung in der Ganglienzellschicht der Retina durch den Hell-Dunkel-,
den Rot-Grün- sowie den Gelb-Blau-Kontrast dargestellt. [SLH10, DIN11]
Da sich dieses Modell jedoch als nicht optimal herausstellte wurde durch erneute nichtlineare
Transformation daraus das DIN99-Modell abgeleitet. Dieses Farbmodell wird aufgrund seiner
Vorzüge im Rahmen dieser Arbeit für Farbabstandsberechnungen verwendet. [DIN01]
2.2 Farbbilder
Unter einem Farbbild B verstehen wir eine Funktion die den diskreten zweidimensionalen Orts-
raum O auf einen Farbraum F abbildet. Der Ortsraum wird dabei durch die Bildbreite w und die
Bildhöhe h eingeschränkt.
O = {1, . . . , w} × {1, . . . , h} ⊂ N2
B : O → F
Aus dieser Definition als Abbildung folgt, dass ein Bild alternativ als eine endliche Menge
von 2 -Tupeln bestehend aus einem Ort und einer Farbe interpretiert werden kann. Diese Tupel
werden im Folgenden Bildpunkte oder auch Pixel ~p genannt.
B ⊂ O × F
~p =
(
~o, ~f
)
∈ B
5

3 Verwandte Arbeiten
Die Kombination aus Zerlegung und Neuanordnung von Farbbildern wurde in dieser Form bisher
kaumuntersucht. Dennoch lassen sich zumindest zu denbeidenTeilthemen jeweils entsprechende
Arbeiten finden.
3.1 Segmentierung von Bildern
Das Zerlegen von Bildern in Segmente bildet die Grundlage zahlreicher Verfahren in der digitalen
Bildverarbeitung. Die Menge an Arbeiten die sich damit beschäftigen ist dementsprechend selbst
bei einer Beschränkung auf Farbbilder noch überwältigend.
An dieser Stelle sei daher an Raut et al. [RRDR09] und Cheng et al. [CJSW01] verwiesen. Beide
Gruppen befassen sich in ihren Arbeiten mit der Menge an bekannten Segmentierungsverfahren
und versuchen durch eine Kategorisierung einen Überblick zu schaffen. Cheng et al. beschränken
sich dabei sogar explizit auf das Segmentieren von Farbbildern.
Eine weitere Arbeit zu diesem Thema stammt von Haindl und Mikeš [HM08]. Auch sie un-
tersuchen verschiedene bekannte Verfahren, diesmal allerdings in Hinsicht auf ihre Güte und
Geschwindigkeit.
3.2 Anordnung von Objekten
Mit dem Anordnen von Objekten, wie beispielsweise Bildsegmenten, haben sich bereits mehrere
Gruppen befasst.
Bei Dalal et al. [DKLS06] werden beliebig geformteMosaiksteinemöglichst dicht in vorgegebene
Formen verteilt. Dabei kann jeder Stein, wie bei Mosaiken üblich, mehrfach platziert werden. Um
die Dichte zu erhöhen werden die Steine zusätzlich rotiert. Einen ähnlichen Ansatz verfolgen
Kim und Pellacini [KP02], wobei sie durch eine abschließende Verzerrung der Steine die Dichte
noch weiter erhöhen.
Hauser [Hau01] beschäftigt sich ebenfalls mit der Erstellung vonMosaiken. Dabei beschränkt er
sich allerdings auf quadratische Steine. Außerdem steht bei ihm nicht die Dichte im Vordergrund,
sondern die Nachbildung von Details innerhalb des Mosaiks. Dazu versucht er die Steine so
auszurichten, dass ihre Kanten entlang von markanten Linien verlaufen.
Ähnlich einem Mosaik ordnen auch Lagae und Dutré [LD05] Instanzen von vorgegebenen
Objekten in einem Zielbild an. Bei ihnen wird die Dichte allerdings vorgegeben und ist typischer-
weise eher dünn. Sie versuchen die Abstände möglichst gleichmäßig zu gestalten, ohne dabei
Muster entstehen zu lassen. Dadurch können beispielsweise beliebig große, sich jedoch nicht
wiederholende Texturen geschaffen werden. Das Team um Hurtut [HLT+09] hingegen versucht
solche bereits bestehenden gleichmäßigen Anordnungen nachzubilden. Dazu werden zunächst in
einem Eingabebild Objekte gesucht und deren Form und Verteilung abstrahiert. Auf dieser Basis
können daraufhin, ähnlich wie bei Hurtut et al., beliebig große Bilderer generiert werden, die dem
Ausgangsbild in den Bildobjekten und deren Verteilung ähneln, sich jedoch nicht wiederholen.
7
3 Verwandte Arbeiten
Reinert et al. [RRS13] verteilen hingegen eine vorgegebene Menge an Bildobjekten möglichst
gleichmäßig in einemBild fester Größe. Zusätzlich versuchen sie von einzelnen vomBenutzer plat-
zierten Objekten Sortierkriterien für beide Koordinatenachsen abzuleiten und die Bildsegmente
dementsprechend zu sortieren.
Noch einen Schritt weiter gehen schließlich Yu et al. [YYT+11]. Sie ordnen Möbel im Grund-
riss eines Zimmers an, wobei komplexere Bedingungen eingehalten werden müssen. So muss
beispielsweise ein Fernseher von einem Sitzmöbel aus sichtbar sein.
8
4 Segmentierung von Farbbildern
Unter der Segmentierung eines Bildes verstehtman das Zusammenfassen von Bildpunkten zu Seg-
menten, wobei gewisse Kriterien erfüllt werden müssen. So muss die Segmentierung vollständig
und überdeckungsfrei sein, d.h. jeder Bildpunkt muss genau einem Segment zugeordnet werden.
Die Segmente selbst müssen zusammenhängend sein und entsprechen damit geschlossenen
Regionen. Zusätzlich zu diesen Bedingungen ist eine gewisse Qualität wünschenswert, die sich
aus der Semantik der Segmente ergibt. Entsprechen sie tatsächlichen Objekten im Bild, ist die
Segmentierung qualitativ hochwertig. [Tön05]
Anwendung findet das Segmentieren hauptsächlich als Vorverarbeitungsschritt in der Bildver-
arbeitung. Beispiele hierfür sind das Trennen von Text und Hintergrund bei der Texterkennung
oder das Differenzieren einzelner Gewebearten in CT-Datensätzen bei der medizinischen Visuali-
sierung. Da die Qualität der Segmentierung hierbei entscheidenden Einfluss auf das Ergebnis der
aufbauenden Verfahren hat, wurden bereits zahlreiche Segmentierungsalgorithmen entwickelt
und erforscht. [CJSW01, Tön05, RRDR09]
Um die Auswahl eines passenden Verfahrens zu vereinfachen, wird in diesem Kapitel zunächst
ein Überblick gebildet, indem eine Klassifizierung ausgearbeitet wird. Nach demUmreißen der er-
mittelten Klassen werden ihre Stärken und Schwächen abgewogen und verglichen. Abschließend
werden die zur Implementierung ausgewählten Verfahren im Detail vorgestellt.
4.1 Segmentierungsklassen
Auch wenn die bisher bekannten Verfahren das gemeinsame Ziel einer den oben genannten
Kriterien entsprechenden Segmentierung haben, gibt es unterschiedliche Ansätze wie dies er-
reicht werden kann. Dadurch wird es möglich, die Verfahren in Klassen entsprechend eben dieser
Ansätze einzuteilen.
Eine solche Klassifizierung wurde bereits von Cheng et al. [CJSW01] als auch von Raut et al.
[RRDR09] durchgeführt, mit teilweise unterschiedlichen Ergebnissen. In Tabelle 4.1 werden die
jeweils gebildeten Klassen aufgelistet.
Cheng et al. Raut et al.
Histogram thresholding Threshold based
Feature space clustering Histogram based
Region based Region based
Edge detection Edge detection
Neural networks Watershed Transformation
Fuzzy Graph Partitioning
Tabelle 4.1: Segmentierungsklassifizierungen nach Cheng et al. und Raut et al.
Durch unterschiedliche Abgrenzungen kommen sie auf verschiedene Segmentklassen.
9
4 Segmentierung von Farbbildern
Um die Klassifizierungen zu vereinheitlichen, wird im Folgenden ein eigenes Modell mit nur
drei Klassen eingeführt.
Wie durch die Gegenüberstellung erkennbar wird, haben sich die Klassen Regionenbasiert und
Kantenfindungsbasiert bereits etabliert und werden deshalb übernommen. Die Wasserscheiden-
transformation und ihre Varianten werden dabei zu den kantenfindungsbasierten Verfahren
gezählt.
Interpretiert man die Farbkanäle als Merkmale, lassen sich die Klassen Grenzwertbasiert und
Histogrammbasiertmit derMerkmalsraum Clusteranalyse vereinen und bilden somit eine dritte, gut
untersuchte Klasse. Die Neuronalen Netze gehen als Werkzeuge zur Clusteranalyse ebenfalls in
dieser Klasse auf.
Übrig bleiben somit lediglich die unscharfen Verfahren und die Graph Partitionierung, auf die,
um es einfach zu halten, hier nicht gesondert eingegangen wird.
4.1.1 Regionenbasiert
Bei den regionenbasierten Ansätzen, wie z.B. Region Growing, Region Merging oder Split and Merge,
geht es darum, benachbarte Pixel, die ein Homogenitätskriterium erfüllen, zu einer Region zu-
sammenzufassen. Entscheidend ist dabei die Wahl eines sinnvollen Kriteriums, wie beispielsweise
ein geringer Farbabstand oder ein ähnliches Texturmaß. Des Weiteren ist der Geltungsbereich
des Kriteriums von Bedeutung, da bei einer lokalen Definition auf Nachbarschaftsebene Chaining,
sprich das Zusammenfassen von langsamen Übergängen, schnell zur Untersegmentierung führen
kann. [Tön05]
4.1.2 Kantenfindungsbasiert
Die Verfahren dieser Klasse basieren auf der Findung von Kanten und der Annahme, dass geschlos-
sene Kantenzüge homogene Segmente einschließen. Prominente Beispiele hierfür sind unter
anderem der Canny Algorithmus, Active-Shape-Models (ASM) und die bereits erwähnteWasserschei-
dentransformation. Aufgrund einer Neigung zur Übersegmentierung bei Bildrauschen ist oftmals
ein glättender Vorverarbeitungsschritt notwendig. Da sie außerdem nicht alle geschlossene Kan-
tenzüge ergeben, muss bei manchen noch ein kantenzugbildender Nachverarbeitungsschritt,
beispielsweise Edge Linking, angewendet werden. [Tön05]
4.1.3 Merkmalsraum Clusteranalyse
Hierbei geht es schlussendlich darum, in der Dichteverteilung von Merkmalsräumen Cluster zu
finden, die im Bildraum geeigneten Segmenten entsprechen. Diese Merkmalsräume bestehen
dabei gewöhnlich aus Farbe und gegebenenfalls Ort. Die bekanntesten Verfahren stellen z.B. das
einfache Schwellwertverfahren, bei dem der typischerweise eindimensionale Merkmalsraum an
einem Schwellwert geteilt wird, oder das k-Means Verfahren, bei dem im n-dimensionalen Merk-
malsraum k Clusterzentren verteilt werden, dar. Ein Problem dieser Verfahren ist allerdings, dass
als Merkmale meist nur die Farbkanäle verwendet werden, was selten zu zusammenhängenden
Segmenten führt. Eine Möglichkeit das zu ändern ist z.B. den Ort auch in den Merkmalsraum
aufzunehmen, wie es bei derMean Shift Segmentierung geschieht, wobei wiederum auf eine pas-
sende Skalierung geachtet werden muss, um die unterschiedlichen Merkmale gleichwertig zu
gewichten. [Tön05]
10
4.2 Vergleich der Klassen
4.2 Vergleich der Klassen
Um die Eignung der Verfahren für unsere Zwecke besser abschätzen zu können, werden die
einzelnen Klassen hier bezüglich verschiedener relevanter Eigenschaften verglichen.
4.2.1 Rückgabetyp
Das Ziel dieser Arbeit ist es, die Konstituenten der Bilder neu anzuordnen. Dafür sind Verfahren
von Vorteil, die bereits zusammenhängende Segmente ergeben.
Die kantenfindungsbasierten Verfahren liefern, wie der Name bereits vermuten lässt, zunächst
nur Kanten. Diese sind zumeist nicht einmal zusammenhängend, sodass teilweise erheblicher
Aufwand betrieben werden muss um tatsächliche Segmente zu erhalten.
Verfahren zur Clusteranalyse in Merkmalsräumen hingegen resultieren zwar in zusammenge-
hörigen Pixelmengen, diese sind jedoch nicht zwangsläufig auch räumlich zusammenhängend.
Hier ist folglich ebenfalls oftmals ein Nachbearbeitungsschritt nötig um die Cluster weiter in
Segmente zu zerteilen.
Das Ergebnis der regionenbasierten Verfahren besteht schließlich direkt aus Segmenten in
Form von zusammenhängenden Pixelmengen. [Tön05]
4.2.2 Benutzbarkeit
Trotz einer guten Segmentierung kann ein Verfahren auch unpraktikabel sein, wenn die Wahl
der entsprechenden Parameter ein neues Problem darstellt. Wünschenswert sind folglich Algo-
rithmen mit möglichst wenigen oder zumindest einfach zu bestimmenden Parametern.
Regionenbasierte Verfahren erfüllen diese Anforderung im allgemeinen nur ungenügend, da
ihr Ergebnis stark von dem gewählten Homogenitätskriterium abhängt.
Im Gegensatz dazu sind die kantenfindungsbasierten Verfahren sogar komplett parameterfrei.
Sie finden ohne steuernde Kriterien sämtliche im Bild vorhandenen Kanten.
Über die dritte Klasse lässt sich diesbezüglich allerdings keine allgemeine Aussage treffen. Wäh-
rend eine Segmentierung mit k-Means beispielsweise stark von dem namensgebenden Parameter
k abhängt, gilt die Mean Shift Segmentierung wiederum als parameterfrei. [Tön05]
4.2.3 Robustheit
Verschiedene Bilder eignen sich unterschiedlich gut zur Segmentierung. Da in dieser Arbeit keine
Einschränkung bezüglich der Eingabebilder gemacht wird, sollen die Segmentierungsverfahren
folglich auch bei Problemfällen gut funktionieren.
Die regionenbasiertenVerfahren haben beispielsweise Probleme bei weichgezeichneten Bildern
mit sanften Übergängen. Je nach Definition des Homogenitätskriteriums kann es hier schnell
zum bereits angesprochenen Chaining kommen. Dieser Effekt kann dabei entweder gewollt sein
oder zur Untersegmentierung führen.
Kantenfindungsbasierte Verfahren funktionieren auf derartigen Bildern hingegen besonders
gut. Für sie werden vielmehr Bilder mit jedweder Art von Rauschen zum Problem. Da sie jegliche
hochfrequenten Bilddetails als Kante erkennen, neigen sie hierbei zur Übersegmentierung.
Die Verfahren auf Basis einer Clusterung im Merkmalsraum sind wiederum durch den Cluster-
ansatz robust gegen Rauschen. In weichen Bildern klare Clustergrenzen zu finden stellt jedoch
ein Problem für sie dar. [Tön05]
11
4 Segmentierung von Farbbildern
4.3 Implementierte Verfahren
Auf Basis der bisherigen Untersuchungen wurden schlussendlich zwei Verfahren zur Implemen-
tierung gewählt.
Aus der Klasse der Merkmalsraum Clusteranalysen wird das Mean Shift Verfahren verwendet.
Sein Vorteil besteht darin, dass es parameterfrei und robust gegenüber Bildrauschen ist. Außer-
dem liefert es aufgrund des geschickt gewählten Merkmalraumes direkt zusammenhängende
Segmente.
Dem gegenübergestellt wird die Wasserscheidentransformation. Sie unterscheidet sich grund-
legend vomMean Shift Verfahren, kann jedoch leicht modifiziert werden um ebenfalls zusam-
menhängende Segmente zu generieren.
4.3.1 Mean Shift Segmentierung
Mean Shift ist ein von Fukanaga und Hostetler [FH75] eingeführtes Verfahren um Dichtezentren,
sogenannteModi, in multidimensionalen Merkmalsräumen zu ermitteln. Da die Anzahl der zu
findenden Modi, im Gegensatz zu beispielsweise k-Means, nicht angegeben werden muss, gilt es
als parameterfrei.
Das Verfahren basiert auf der Annahme, dass bei einem Gradientenaufstieg über die Dichte-
funktion jeder Punkt zu demModus konvergiert, in dessen Cluster er sich befindet. Weist man
dementsprechend jedem Punkt initial sich selbst als Modus zu und verschiebt diese temporären
Modi iterativ entlang dem Dichtegradienten, sammeln sich diese an den Stellen der tatsächlichen
Modi und können in einem Nachbearbeitungsschritt zu diesen zusammengefasst werden.
Die Verschiebung (der namensgebende „Mean Shift“) wird folgendermaßen berechnet. Zu-
nächst werden alle Punkte ermittelt, die sich innerhalb eines n-dimensionalen Ellipsoiden, im
weiteren Kernel genannt, befinden. Deren Orte werden daraufhin gewichtet gemittelt. Der sich
daraus ergebende kernellokale Modus ist das Ziel des Shifts. [FH75]
Kernel
x1
x2
• Punkt • globaler Modus • lokaler Modus
Abbildung 4.1: Schema des Mean Shift Verfahrens.
Um den temporären Modus wird zunächst ein n-dimensionaler Kernel gelegt. Dar-
aufhin wird der kernellokale Modus als Durchschnitt aller im Kernel befindlichen
Punkte ermittelt. Abschließend wird der temporäre Modus auf den kernelloka-
len verschoben und das Verfahren beginn von neuem. Dadurch nähert sich der
temporäre Modus einem globalen an.
12
4.3 Implementierte Verfahren
Anwendung als Segmentierungsverfahren
Das Verfahren wird von Comaniciu und Meer [CM02] zum Segmentieren von Bildern verwendet
indem Sie einen 5-dimensionalen Merkmalsraum aus den drei Farbkanälen und zusätzlich den x-
und y-Koordinaten der Pixel aufbauen. Als Farbraumwählen sie dabei wegen seiner Anpassung an
die menschliche Farbperzeption den nichtlinearen CIELUV Raum, wobei Sie CIELAB als vergleich-
bare Alternative vorschlagen. Um die Berechnungen zu vereinfachen, werden die Merkmale so
skaliert, dass als Kernel anstatt eines Ellipsoiden eine Einheitskugel verwendet werden kann. Die
Gewichtung der Punkte bei der Kernelmodusbestimmung wird fest auf 1,0 gesetzt.
Unter diesen Bedingungen wird ein Mean Shift Filter definiert, der für jeden Pixel den Mean
Shift ausführt und ihm anschließend die Farbe des ermittelten Modus zuweist (Abbildung 4.2b).
Das so gefilterte Bild kann daraufhin mit einem einfachen regionenbasierten Verfahren, wie
beispielsweise Region Growing, segmentiert werden (Abbildung 4.2c).
Da durch Rauschen oder sanfte Übergänge allerdings oft eine Übersegmentierung auftritt, wer-
den als Nachbearbeitung benachbarte Segmente, deren Durchschnittsfarben einen bestimmten
Farbabstand unterschreiten, verschmolzen. Ebenso werden solche, deren Größe einen gegebenen
Schwellwert unterschreitet, mit dem Nachbar der den geringsten Farbabstand aufweist ver-
schmolzen. Dadurch sollen zu kleine Bilddetails, deren semantische Bedeutung möglicherweise
zu gering ist, entfernt werden (Abbildung 4.2d). Die fertige Segmentierung wird abschließend
auf das ungefilterte Originalbild übertragen. [CM02]
(a) Originalbild
164.864 Pixel
(b) Mit Mean Shift gefiltert
(c) Mit Region Growing segmentiert
10.240 Segmente
(d) Nachbearbeitet
195 Segmente
Abbildung 4.2: Verarbeitungsschritte der Mean Shift Segmentierung am Bild Venus
Zunächst wird das Bild mit dem Mean Shift Filter bearbeitet (b). Anschließend
werden die Flächen mittels Region Growing zu Segmenten zusammengefasst (c),
und abschließend deren Anzahl durch Verschmelzung noch reduziert (d).
13
4 Segmentierung von Farbbildern
Parameterwahl
Die Stellschrauben dieses Verfahrens sind die Skalierung der Farbkanäle und der Pixelpositionen
in Form der Radien des unskalierten Kernel-Ellipsoids σFarb und σPos, der Farbähnlichkeits-
schwellwert εFarb und die minimale Segmentgröße k. Weiterhin hat sich beim Implementieren
dieminimale Schrittweite desMean Shifts εShift als Abbruchkriterium der Iteration als Parameter
mit großem Einfluss sowohl auf die Qualität als auch die Rechenzeit herausgestellt.
Der Farbradius σFarb ist abhängig von der Farbverteilung des Bildes und wird von Comaniciu
und Meer mit einemWertebereich von (4 . . . 20) angegeben. Dabei entspricht ein größerer Radius
einer größeren Toleranz gegenüber Farbschwankungen innerhalb eines Segments.
Der Ortsradius σPos wird von ihnen allerdings ohne Begründung konstant auf 132 der Kanten-länge der quadratischen Testbilder gesetzt. Er sollte sich normalerweise nach der typischen
Bildobjektgröße richten, der voreingestellte Wert hat sich dabei jedoch in der Praxis durchaus als
gute Abschätzung erwiesen.
Für k, das wiederum stark vom Bildinhalt abhängig ist, wird ein Wertebereich von (20 . . . 40)
vorgeschlagen. Tatsächlich hat es sich oftmals allerdings als notwendig herausgestellt, diese
Grenze bis auf Werte im mittleren dreistelligen Bereich anzuheben.
Die beiden Parameter εFarb und εShift werden im Paper zwar leider nicht erwähnt, in der
Beispielimplementierung werden sie jedoch fest auf 0,5 [Längeneinheiten im Farbraum] respek-
tive 0,01 [Längeneinheiten im skalierten Merkmalsraum] gesetzt. Der Farbgrenzwert für die
Verschmelzung εFarb wird in unserer Implementierung auf 1,0, laut Definition den kleinsten noch
wahrnehmbaren Farbunterschied [DIN11], angehoben.
Die minimale Schrittweite des Mean Shifts εShift ist ein schwieriger Parameter. Je kleiner sie
gewählt wird, desto homogener sind die durch die Filterung entstehenden Flächen. Die Laufzeit
wird durch zu kleine Werte allerdings drastisch erhöht, da der Algorithmus so erst viel später
abbricht.
Ein paar Beispiele zur Auswirkung der Kernelradien auf das Filterergebnis ist im Anhang in
Abbildung A.1 zu sehen.
4.3.2 Wasserscheidentransformation
Dem Verfahren von Beucher und Lantuéjoul [BL79] liegt die Annahme zugrunde, dass homogene
Regionen durch geschlossene Kantenzüge begrenzt werden. Das Ermitteln dieser Züge geschieht
dabei jedoch nicht direkt auf dem Ursprungsbild. Als Vorbereitung werden zunächst die Gradi-
enten aller Pixel berechnet. Deren Beträge werden daraufhin als Grauwerte in ein neues Bild
gespeichert, das sogenannte Gradientenbetragsbild (siehe Abbildung 4.3c).
Interpretiert man die Grauwerte dieses Bildes als Höheninformation, ergibt sich daraus ein Re-
lief. Dessen Bergketten und Täler entsprechen im Ursprungsbild Kanten respektiven homogenen
Flächen.
Das eigentliche Verfahren flutet diese Landschaft, indem das Wasserlevel langsam angehoben
wird. Dabei wird beobachtet, an welchen Stellen die sich bildenden Wasserbecken aufeinander-
treffen. Die so ermittelten namensgebenden Wasserscheiden entsprechen im Ursprungsbild den
Grenzen zwischen den Segmenten.
Bei der Flutung eines neuen Pixels kann es dabei zu folgenden drei Fällen kommen:
1. Keiner der Nachbarpixel wurde bislang überflutet.
2. Alle bereits überfluteten Nachbarpixel gehören zum selben Wasserbecken.
3. Die überfluteten Nachbarpixel gehören zu mindestens zwei verschiedenen Wasserbecken.
14
4.3 Implementierte Verfahren
Fall eins bedeutet, dass der Pixel der erste in seiner Nachbarschaft ist, der mit Wasser in
Berührung kommt. Er stellt somit die Quelle für ein neues Wasserbecken und somit auch für eine
neue Region dar.
Im zweiten Fall breitet sich ein bereits bestehendes Becken auf den neuen Pixel aus, er kann
folglich zu der Region hinzugefügt werden.
Der dritte Fall beschreibt schlussendlich das Szenario, dass zwei oder mehr benachbarte Was-
serbecken aufeinander treffen. Hierbei ist der Pixel folglich Teil der Wasserscheide. [BL79]
(a) Originalbild
164.864 Pixel
(b) Mit einem 31x31 Gaußfilter
geglättet
(c) Gradientenbetragsbild
(d) Nach Wasserscheidentransformation
2.260 Segmente
(e) Nach der Nachbearbeitung
172 Segmente
Abbildung 4.3: Verarbeitungsschritte der Wasserscheidentransformation am Bild Venus
Zunächst werden hochfrequente Bilddetails durch einen Tiefpassfilter entfernt (b).
Auf dieser Basis wird das Gradientenbetragsbild erstellt (c). Die Wasserscheiden-
transformation führt zu einer Segmentierung des Bildes (d). Um der Übersegmen-
tierung entgegenzuwirken werden abschließend ähnliche und kleine Segmente
verschmolzen (e).
Problem der Übersegmentierung
Die Wasserscheidentransformation neigt, wie jedes kantenfindungsbasierte Verfahren, zur Über-
segmentierung. Diesem Problem wird in dieser Arbeit begegnet, indem vor dem Bilden des Gradi-
entenbetragsbildes das Ausgangsbild mit einem Tiefpassfilter bearbeitet wird (Abbildung 4.3b).
Dadurch werden hochfrequente Störungen wie Rauschen entfernt.
Zusätzlich wird im Anschluss die selbe Nachbearbeitung, die auch bei der Mean Shift Segmen-
tierung zum Einsatz kommt, angewendet. Benachbarte Segmente mit ähnlicher Farbe und zu
kleine Segmente werden verschmolzen (Abbildung 4.3e).
15
4 Segmentierung von Farbbildern
Berechnung des Gradientenbetragsbildes bei Farbbildern
Die ursprüngliche Wasserscheidentransformation nach Beucher und Lantuéjoul [BL79] wurde
nur auf Graustufenbildern definiert. Diese können aufgrund der eindimensionalen Grauwerte
als Skalarfelder verstanden werden. Der Gradient grad(·) ist auf einem solchen Feld eindeutig
definiert und ergibt ein Vektorfeld. Darauf wiederum ist der Betrag durch die euklidische Norm
‖~v‖2 bestimmt. [BSMM05]
Farbbilder hingegen sind durch den dreidimensionalen Farbraum selbst bereits Vektorfelder.
Mit der Jacobi-Matrix J ist der Vektorgradient grad
(
~V
)
bestimmt und im diskreten Bildraum
einfach zu berechnen. Die von der euklidischenNorm abgeleitete Spektralnorm ‖A‖2 fürMatrizen
erfordert jedoch einen größeren Rechenaufwand.
Stattdessen wird im Folgenden die einfachere und ebenfalls auf der euklidischen Norm basie-
rende Frobeniusnorm ‖A‖F verwendet. [BSMM05]
‖A‖2 =
√
λmax (ATA)
‖A‖F =
√√√√ m∑
i=1
n∑
j=1
(aij)2
16
5 Anordnung von Bildsegmenten
Ein Bildsegment S im Sinne einer Segmentierung ist eineMenge von untereinander benachbarten
Bildpunkten ~p. Seine Position ~oS im Bild wird durch seinen Schwerpunkt repräsentiert. Da alle
Pixel gleich gewichtet werden, entspricht dieser dem Mittelwert aller Pixelpositionen ~o~p.
~oS =
1
|S|
∑
~p∈S
~o~p
Die räumliche Ausrichtung wird durch den Winkel αS zwischen der ersten Hauptkomponente
~vS,1 und der x-Achse definiert. Die erste Hauptkomponente ist dabei gemäß der Hauptkom-
ponentenanalyse (PCA) nach Pearson [Pea01] der Eigenvektor der Autokorrelationsmatrix der
Pixelpositionen mit dem größten Eigenwert.
αS = ^
(
~vS,1,
(
1
0
))
Unter einer Anordnung verstehen wir schließlich eine Transformation, die jedes Segment Si
eines Bildes an einen neuen Ort ~o ′Si verschiebt und gegebenenfalls zu einer neuen Ausrichtung
α′Si rotiert. Als einschränkende Bedingung wird gefordert, dass die neu platzierten Segmentesich nicht überschneiden dürfen.
Die Intention dabei ist es die Segmente nach gewissen Kriterien zu ordnen oder gar zu gruppie-
ren. Dadurch sollen übersichtliche und ästhetisch ansprechende Ergebnisbilder erzielt werden.
5.1 Abgrenzung zu anderen Transformationen
In den verwandten Arbeiten wurden bereits andere Transformationen von Bildsegmenten er-
wähnt. Zur Verdeutlichung der Unterschiede folgt eine kleine Übersicht.
Layout wird im Folgenden als übergreifende Bezeichnung verwendet. Sie umfasst sämtliche
Transformationen, die Bildsegmente verschieben und/oder rotieren. Dabeiwerden keineweiteren
Einschränkungen gefordert, nicht einmal Überschneidungsfreiheit.
„Packing“ Layout benennt ein Layout bei dem eine optimale Raumausnutzung imVordergrund
steht. Neben der Überschneidungsfreiheit werden deshalb uniforme und minimale Abstände
gefordert. [RRS13]
Mosaik bezeichnet in der Bildsynthese eine besondere Formvon Packing Layout. Ziel ist es dabei,
ein gegebenes Motiv durch ein dichtes Layout in Form und gegebenenfalls Farbe zu imitieren.
Um dies zu erreichen, darf jedes Bildsegment an beliebig vielen Stellen platziert werden. Dadurch
sind Mosaiken Layouts auf der Menge der verwendeten Segmentinstanzen, nicht jedoch auf den
Segmenten selbst. [DKLS06]
17
5 Anordnung von Bildsegmenten
5.2 Handhabung des Bildhintergrundes
Der Hintergrund eines Bildes ist typischerweise ein Objekt das sich über den gesamten Ortsraum
erstreckt und sich hinter allen anderen Bildobjekten befindet. Ein gutes Beispiel ist in Abbil-
dung 5.1a zu sehen, in dem die Krawatten offensichtlich vor einem beigen Hintergrund platziert
sind.
Werden bei einer Neuanordnung alle Bildsegmente gleich behandelt, verlieren die Segmente
des Hintergrunds diese Bedeutung. An ihre Stelle treten die neu entstehenden Zwischenräume,
für die jedoch keine Farbe definiert ist.
Es bietet sich folglich an, den Bildhintergrund gesondert zu behandeln. Im Folgenden soll er
zunächst aus dem Ausgangsbild extrahiert und anschließend auf das Zielbild übertragen werden.
(a) Bild Krawatten:
Der Hintergrund (beige Unterlage)
ist eindeutig erkennbar.
(b) Bild Holzfäller:
Ein einheitlicher Hintergrund
ist nicht erkennbar.
(c) Bild Venus:
Der Hintergrund besteht aus zwei
Objekten (Himmel und Wasser).
(d) Bild Pizza:
Der Hintergrund (Tisch) ist klein
und unzusammenhängend.
Abbildung 5.1: Verschiedene Beispiele für Bildhintergründe, die unterschiedlich deutlich erkenn-
bar sind.
18
5.2 Handhabung des Bildhintergrundes
5.2.1 Extrahieren des Hintergrunds
Um den Bildhintergrund extrahieren zu können, muss dieser vorher identifiziert werden. Da
jedoch keine Informationen über die Segmentbedeutung zur Verfügung stehen, müssen allge-
meinere Kriterien gefunden werden. Dazu werden zunächst anhand eines einfachen Beispiels
Bedingungen gesucht, die vornehmlich von Hintergrundsegmenten erfüllt werden. Diese werden
daraufhin unter Berücksichtigung von möglichen Sonderfällen evaluiert und gegebenenfalls
angepasst. Abschließend wird daraus ein Verfahren zur Hintergrunderkennung und -extraktion
ausformuliert.
Bedingungen für Hintergrundsegmente
Bei der Betrachtung von Abbildung 5.1a fällt auf, dass der Hintergrund sich tatsächlich über das
gesamte Bild erstreckt und nur an wenigen Stellen von anderen Bildobjekten verdeckt wird. Aus
dieser Beobachtung lassen sich direkt zwei Bedingungen herleiten:
1. Der Hintergrund nimmt die größte Fläche ein, da er die gesamte Bildfläche umfasst die
nicht von anderen Objekten überdeckt wird.
2. Der Hintergrund hat die meisten Segmentnachbarn, da jedes überdeckende Segment einen
potentiellen Nachbarn darstellt.
Sonderfälle
Als problematisch erweisen sich beispielsweise Bilder bei denen die Bildobjektsegmente aufgrund
ihrer Größe oder Anzahl einen zu großen Bereich des Hintergrunds verdecken. Dadurch kann es
leicht passieren, dass der Hintergrund nicht mehr das größte Segment darstellt. In diesem Fall
sollte dementsprechend besser aufgrund der Anzahl an Nachbarsegmenten entschieden werden.
Einen weiteren Problemfall stellen Bilder dar, bei denen der Hintergrund in mehrere Segmente
zerfällt. Das kann aufgrund seiner Textur oder wie bei dem Bild Pizza in Abbildung 5.1d durch
Überdeckung geschehen. Hierwäre es sinnvoll die einzelnen Segmente als eineHintergrundobjekt
zu behandeln. Das wiederum stellt eine neue nichttriviale Aufgabe dar, da hierzu zunächst alle
Segmente ohne Zusatzwissen zu Objekten zusammengefasst werden müssen.
Besteht der Hintergrund selbst noch aus mehreren solcher Objekte, wie beispielsweise bei dem
Bild Venus in Abbildung 5.1c aus Meer und Himmel, müssen diese Objekte selbst wiederum zu
neuenMetaobjekten zusammengefasstwerden. Somit kommt zu der Segmentbildung ohne Zusatz-
wissen noch eine hierarchische Komponente hinzu, für die noch zusätzlich ein Abbruchkriterium
gefunden werden muss.
Ist das Bild schließlich so dicht mit Objekten besetzt, dass kein Hintergrund mehr erkennbar
ist, wie bei dem Bild Holzfäller in Abbildung 5.1b, muss dennoch eine passende Hintergrundfarbe
gefundenwerden. Dafür bietet sich wiederum das größte Segment bzw. die ammeisten vertretene
Farbe an, da der Hintergrund im Zielbild ebenfalls die größte Fläche einnehmen wird.
Entwickeltes Verfahren
Das Zusammenfassen von Segmenten zu Objekten und Metaobjekten ohne Hintergrundwissen
stellt ein sehr komplexes Problem dar, das den Rahmen dieser Arbeit sprengen würde. Deshalb
wird dieser Ansatz nicht weiter verfolgt.
19
5 Anordnung von Bildsegmenten
Tatsächlich werden zunächst lediglich die beiden Merkmale Größe und Anzahl an Nachbarn
für alle Segmente ermittelt. Daraufhin wird für jedes Merkmal das Segment mit dem größten
Merkmalswert ausgewählt. Ist diese Wahl einstimmig, gilt der Hintergrund als gefunden.
Werden dabei zwei unterschiedliche Segmente gewählt, wird für jedesMerkmal die Standardab-
weichung über allen Bildsegmenten berechnet. Die maximalen Merkmalswerte werden daraufhin
durch die jeweilige Standardabweichung geteilt. Der entstehende Quotient gibt Aufschluss über
die Signifikanz des Merkmalswerts. Hintergrund wird folglich das Segment mit dem größeren
Quotient.
Durch dieses Verfahren soll sichergestellt werden, dass ein möglichst eindeutiger Hintergrund
gefunden wird. Auch wenn dies durch die genannten Problemfälle erschwert wird.
5.2.2 Übertragen des Hintergrunds
Ist der Hintergrund des Ursprungsbildes gefunden, muss er auf das Zielbild übertragen werden.
Ein Problem dabei bilden die Lücken, an denen der Hintergrund von den anderen Bildobjekten
verdeckt wurde. Des Weiteren ist das Zielbild durch die entstehenden Segmentzwischenräume
größer als das Ursprungsbild, sodass um den alten Hintergrund ein leerer Rand verbleibt. An
diesen Stellen fehlt Bildinformation, die rekonstruiert oder anderweitig ersetzt werden muss.
Erweiterung durch Inpainting und Extrapolation
Eine elegante Lösung wäre es, die Lücken mittels eines Inpainting-Verfahrens aufzufüllen. Die
Schwierigkeit dabei besteht allerdings darin, dass hierfür nicht zwingend genügend Informatio-
nen zur Verfügung stehen. Bei dem Bild Pizza in Abbildung 5.1d beispielsweise wird weit mehr als
die Hälfte des Hintergrunds verdeckt.
Die Extrapolation des Bildrandes gestaltet sich aus ähnlichen Gründen problematisch. Bei dem
Bild Holzfäller in Abbildung 5.1b beispielsweise bietet sich das weiße Hemd des namensgebenden
Arbeiters durch seine Größe noch am ehesten als Hintergrund an. Trotz dieser Größe muss das
entsprechende Segment für den Hintergrund jedoch auf ein zweistelliges Vielfaches seiner Größe
erweitert werden.
Solche Verfahren führen in Einzelfällen durchaus zu guten Ergebnissen, für den allgemeinen
Fall sind sie jedoch leider nicht praktikabel.
Verwenden der durchschnittlichen Farbe
Bei einer genaueren Untersuchung von Bildhintergründen stellt sich heraus, dass diese sich
zumeist durch eine gleichmäßige Färbung auszeichnen. Weisen sie ein zu prägnantes Muster auf,
zerfallen sie außerdembei der SegmentierungundwerdennachdemebenvorgestelltenVerfahren
getrennt betrachtet. Zusätzlich ist die Aufgabe des Hintergrunds im Zielbild hauptsächlich das
Auffüllen von Lücken, von dem eigentlichen Bildinhalt soll er möglichst wenig ablenken.
All das führt zu dem Ansatz, den Hintergrund des Zielbilds direkt mit der durchschnittlichen
Farbe des gefundenen Hintergrundsegments einzufärben. Aufgrund seiner Einfachheit und der
Güte der damit erzielten Resultatewird der Ansatz im Folgenden für die Hintergrundsübertragung
verwendet.
Um das Hintergrundsegment nicht noch zusätzlich mit den restlichen Segmenten anzuordnen,
muss es schließlich noch aus der Menge der Segmente entfernt werden. Damit dies auch bei
zerfallenen Hintergründen mit dem gesamten Objekt geschieht, werden alle Objekte mit einem
Farbabstand ∆E99 von weniger als 5 Einheiten entfernt.
20
5.3 Segmentmerkmale als Ordnungskriterien
5.3 Segmentmerkmale als Ordnungskriterien
Wie bereits am Kapitelanfang angemerkt wurde, sollen die Anordnungen die Bildsegmente in eine
geordnete Form überführen. Das bedeutet, dass die Segmente sowohl sortiert als auch gruppiert
werden müssen. Damit diese Ordnung auch für den menschlichen Betrachter nachvollziehbar
ist und damit tatsächlich ordentlich erscheint, muss zusätzlich jedem Kriterium eine gewisse
Semantik innewohnen.
Um diesen Bedingungen zu genügen bietet es sich an, eindimensionale Segmentmerkmale
als Ordnungskriterien zu verwenden. Auf diesen muss sowohl eine Ordnungsrelation für die
Sortierung als auch eine Norm für die Gruppierung definiert werden können. Zur tatsächlichen
Ordnung können die Merkmale somit durch Homomorphismen bezüglich der Reihenfolge und
Abstände direkt auf eine Position im Ortsraum abgebildet werden.
5.3.1 Merkmale im Ortsraum
Die Segmentposition selbst eignet sich nicht als Ordnungskriterium, da hierdurch der Ort auf
sich selbst abgebildet und damit keine Neuanordnung erreicht würde. Dennoch gibt es weitere
räumliche Merkmale bei denen sich eine genauere Untersuchung lohnt.
Segmentgröße
Die Segmentgröße ergibt sich direkt aus der Anzahl an Pixeln die zu dem Segment gehören. Der
Wertebereich erstreckt sich dabei theoretisch von einem Pixel bis zur Bildgröße selbst. Dabei
wird die Mindestgröße jedoch durch einen Parameter des Segmentierungsalgorithmus, der zu
kleine Segmente verbietet, angehoben.
Standardabweichung der Pixelpositionen
Mit der Standardabweichung der Pixelpositionen σ~o sollen Rückschlüsse auf die räumliche Kom-
plexität der Segmente ermöglicht werden. Die Überlegung dabei lautet, dass die Pixel bei kom-
plexeren Segmenten weiter im Raum verteilt sind und die Standardabweichung dadurch größer
ist. Allerdings sind die Pixel auch bei größeren Segmenten weiter im Raum verteilt, sodass die
Standardabweichung mehr eine Kombination aus Größe und räumlicher Komplexität bildet.
Berechnet wird sie gemäß der mathematischen Definition als Wurzel der Varianz:
σ~o,S =
√
1
|S|
∑
~p∈S
(~o~p − ~oS)2
Der Wertebereich ist dabei abermals abhängig von der Größe des Bildraums, diesmal entspricht
das theoretische Maximum jedoch der halben Bilddiagonale.
Kompaktheit
Um die Größenabhängigkeit aus der Standardabweichung der Pixelpositionen zu entfernen, wird
diese durch die Standardabweichung eines Kreises mit der selben Fläche geteilt. Übrig bleibt die
tatsächliche räumliche Komplexität der Segmente.
21
5 Anordnung von Bildsegmenten
Da dieWerte allerdings schwer deutbar sind, wird anschließend der Kehrwert gebildet. Dadurch
entsteht die Kompaktheit, die einen Wertebereich von (0; 1] aufweist. Ein Kompaktheitswert von
1 steht dabei für maximale Kompaktheit.
Ausrichtungswinkel
Der Ausrichtungswinkel wurde bereits in der Kapiteleinleitung als αS eingeführt. Wenn er als
Ordnungskriterium verwendet wird, sollte bei der Anordnung auf Rotationen verzichtet werden,
da das Merkmal sonst modifiziert wird und die Ordnung dadurch chaotisch wirkt.
Der Wertebereich kann aus Symmetriegründen auf [0, pi] festgelegt werden.
5.3.2 Merkmale im Farbraum
Die Segmentierung aus der die Bildsegmente hervorgehen, geschieht anhand der Pixelfarben.
Daraus folgt, dass die Segmente zu einem gewissen Grad homogen gefärbt sind und somit gut
durch ihre Durchschnittsfarbe repräsentiert werden können.
Mit dem Farbabstand ∆E99 ist für dieses Merkmal bereits eine Norm für die Gruppierung gege-
ben. Für die Sortierung lässt sich aufgrund des dreidimensionalen Charakters der Farben jedoch
nur schwer eine Ordnungsrelation definieren. Daher bietet es sich an, die Durchschnittsfarbe in
mehrere eindimensionale Merkmale aufzuteilen.
Die einzelnen Komponenten der Din99-Farbtupel lassen sich dabei direkt als intuitiv verständ-
liche Merkmale verwenden. Weitere können beispielsweise durch Farbraumtransformationen
gewonnen werden.
Helligkeit
Die Helligkeit der Durchschnittsfarbe gibt an, wie hell bzw. dunkel das Segment wirkt. Sie kann
als L99 direkt aus dem DIN99 Farbsystem übernommen werden. Der Wertebereich ist auf das
Intervall [0; 100] festgesetzt. [DIN01]
Grün-Rot-Kontrast
Der Grün-Rot-Kontrast, auch Rotheit genannt, gibt an wie rot bzw. grün das Segment wirkt. Er
kann als a99 ebenfalls direkt aus dem DIN99 Farbsystem übernommen werden. Das Merkmal kann
für die Farben aus dem RGB-Farbkörper extremal Werte zwischen ca. −27,4 und 36,2 annehmen.
Da es jedoch in Hinsicht auf konstante Farbabstände nichtlinear transformiert wird, hängt der
tatsächliche Wertebereich von b99 ab. [DIN01]
Blau-Gelb-Kontrast
Der Blau-Gelb-Kontrast, auch Gelbheit genannt, verhält sich bezüglich der Blau-Gelb-Achse
analog zur Rotheit. Im DIN99 Farbsystem wird er durch die Komponente b99 repräsentiert. Sein
extremaler Wertebereich liegt bei ca. −33,4 bis 31,2, hängt jedoch seinerseits von a99 ab. [DIN01]
Farbton
Der Farbton h99, auch Bunttonwinkel genannt, gibt den Winkel der Farbe im Farbkreis an. Er
ergibt sich durch eine Polarkoordinatentransformation der Bunttonebene a99-b99 nach folgendem
Schema.
22
5.3 Segmentmerkmale als Ordnungskriterien
h99 = arctan
(
a99
b99
)
Sein Wertebereich ist folglich zyklisch und wird typischerweise mit dem Intervall [−pi; pi]
angegeben. [DIN01]
Sättigung
Die Sättigung C99 gibt den Abstand der Farbe zur Unbuntachse an. Damit ist sie der Radius der
Polarkoordinatentransformation und kann durch folgende Formel berechnet werden.
C99 =
√
a299 + b299
DerWertebereich beginnt bei 0, reicht wegen der nichtlinearen Verformung der Bunttonachsen
a99 und b99 jedoch bis maximal ca. 37,9, abhängig vom Bunttonwinkel. [DIN01]
Standardabweichung der Farben
Die Pixelfarben eines Segments sollten durch das Homogenitätskriterium der Segmentierung
nur wenig variieren. Allerdings kann es durch das Verschmelzen kleinerer Segmente trotzdem zu
signifikanten Farbdiversitäten kommen.
Diese können dabei durch die Standardabweichung der Pixelfarben charakterisiert werden.
Sie wird analog zur Standardabweichung der Pixelpositionen berechnet, wodurch sich auch hier
eine Abhängigkeit von der Größe des zu Grunde liegenden Farbraums ergibt. Da dieser allerdings
im Gegensatz zum Ortsraum eine segmentunabhängige Größe hat, muss sie nicht wie bei der
Kompaktheit entfernt werden.
5.3.3 Skalierung der Merkmale
Damit die Merkmale leichter auszutauschen und zu kombinieren sind, müssen sie skaliert werden.
Wünschenswert wäre dabei, dass Segmente mit einem gleichen Abstand in einem beliebigen
Merkmalsraum auch als gleich ähnlich wahrgenommen werden.
Die Merkmale, die auf der durchschnittlichen Segmentfarbe basieren, sind durch das verwen-
dete Farbsystem bereits dementsprechend skaliert. Diese Skalierung wurde jedoch über mehrere
Jahre mit vielen Studien verfeinert und ist dennoch auch heute noch nicht perfekt [DIN01, DIN11].
Den selben Aufwand auch für die verbleibenden Merkmale aufzubringen übersteigt folglich den
Umfang einer einzelnen Arbeit erheblich.
Umdennoch eine einheitliche Skalierung zu erreichen,werdendieWertebereiche derMerkmale
durchgehend auf den Intervall [0; 1] abgebildet. Dadurchwird zwar den Abständen keine Semantik
zugesprochen, die Bereichsgrenzen können jedoch ohne weitere Umrechnung als Intensitäten
von 0% und 100% interpretiert werden.
Vorteile und Probleme der Skalierung
Manche Merkmale, wie beispielsweise die Helligkeit der Durchschnittsfarbe, haben einen festen
Wertebereich der direkt auf das Zielintervall abgebildet werden kann. Die Segmente sind dadurch
nicht zwingend über die gesamte Breite des Wertebereichs verteilt, was jedoch wegen der festen
Grenzen durchaus informativ sein kann.
23
5 Anordnung von Bildsegmenten
Andere Merkmale, wie beispielsweise die Segmentgröße, haben hingegen keinen sehr sinn-
vollen Wertebereich. Da es maximal ein Segment geben kann dessen Größe die halbe Bildgröße
übertrifft, ist die zweite Hälfte des Wertebereichs mit eben diesem maximal einen Segment sehr
dünn besetzt. Zum einen bietet es sich wegen dieser Seltenheit großer Segmente an, das Merkmal
generell zu logarithmieren. Zusätzlich ist es jedoch wegen der schwach begründeten oberen
Grenze auch sinnvoll, nicht den gesamten theoretischen Wertebereich auf das Zielintervall zu
stauchen. Vielmehr soll nur das Fenster in dem tatsächlich Segmente liegen darauf abgebildet
werden. Durch dieses Vorgehen können größere Leerräume an den Intervallgrenzen effektiv
vermieden werden.
Eine weitere Besonderheit stellen die zyklischen Merkmale wie der Bunttonwinkel dar. Die
Wertebereichsgrenzen können hierbei beliebig gewählt werden. Durch diese Wahl und die Abbil-
dung auf den linearen Zielintervall wird dieser zyklische Charakter jedoch entfernt. Die Grenzen
sollten folglich abhängig von der Dichteverteilung der Segmente im Merkmalsraum geschehen.
Schlussendliche Lösung
Für eine einheitliche Lösungwird ein Ansatz formuliert der bei allenMerkmalen für ein zufrieden-
stellendes Ergebnis sorgt. Zunächst werden für alle Merkmale die Maximal- und Minimalwerte
über alle Bildsegmente ermittelt. Diese Intervalle werden daraufhin auf den Zielintervall [0; 1]
abgebildet und die Merkmalswerte der Segmente dementsprechend angepasst.
Damit werden auch die informationstragenden leeren Ränder bei den Merkmalen mit festen
Grenzen entfernt. Das wird jedoch toleriert, da diese sich sonst von den anderen Merkmalen
abheben würden und die Skalierung somit nicht mehr einheitlich wäre.
Die Grenzen der zyklischen Merkmale werden bei den Standardwerten belassen. Eine Verfei-
nerung in diesem Bereich würde noch tiefgreifendere Analysen erfordern und wird künftigen
Arbeiten überlassen.
5.4 Zweistufiger Ansatz
Sowohl Yu et al. als auch Reinert et al. untersuchten bereits das Generieren von überschneidungs-
freien Layouts, die pragmatische oder ästhetische Kriterien erfüllen. Dabei standen beide Teams
vor dem Problem, dass die möglichen Layouts einen zu großen Suchraum darstellen um durch
simple Sondierung in akzeptabler Zeit ein Optimum zu finden. Um dieses Problem zu umgehen,
nutzten beide Gruppen einen ähnlichen Ansatz der in zwei Schritten verläuft. [YYT+11, RRS13]
1. Zunächst wird ein Layout generiert, welches noch nicht allen Bedingungen genügen muss.
Ein solches Layout ist leicht zu erstellen und bietet einen guten Ausgangspunkt für den
zweiten Schritt.
2. Das initiale Layout wird daraufhin durch iterative Verfahren solange verfeinert, bis ein
akzeptables Ergebnis erzielt wird.
Dieser Ansatz hat sich in beiden Arbeiten bewährt und wird auch im Folgenden als Ausgangs-
punkt verwendet.
5.4.1 Aufbau des initialen Layouts
Bei der Erzeugung des initialen Layouts muss dessen Güte gegen den Erstellungsaufwand abgewo-
gen werden. Erfüllt es zu wenige Bedingungen, werden mehr verfeinernde Iterationen benötigt.
24
5.4 Zweistufiger Ansatz
Versucht man jedoch bereits zu Beginn zu viele Bedingungen zu erfüllen, wird das Erzeugen
selbst wiederum aufwändiger.
In dieser Arbeit werden deshalb für das initiale Layout nur die Ordnungskriterien verwen-
det. Dafür werden vom Benutzer zwei Merkmale ausgewählt, die über die dafür geforderten
Homomorphismen auf die x- und y-Achse abgebildet werden. Sie werden somit zu einem zweidi-
mensionalen Merkmalsraum kombiniert. Die Homomorphismen selbst können dabei einfache
lineare Abbildungen sein, da sowohl die Merkmale als auch die Ortsraumdimensionen linear sind.
Das Resultat ähnelt somit einem Streudiagramm, wobei anstatt von einfachen Punkten direkt
die Segmente platziert werden.
5.4.2 Verfeinerung des initialen Layouts
Durch das geschickte Platzieren der Segmente im initialen Layout erfüllen diese bereits das
Ordnungskriterium. Folglich muss in den verfeinernden Iterationsschritten lediglich die Über-
schneidungsfreiheit erreicht werden, um eine vollständige Anordnung gemäß unserer Definition
zu erhalten.
Hierzu muss im Sinne einer einfachen Starrkörpersimulation eine Kollisionserkennung im-
plementiert werden. Auf deren Basis werden sich überschneidende Segmente mit Strafkräften
auseinandergetrieben und gegebenenfalls rotiert. Die Kräfte wirken dabei in Richtung des Verbin-
dungsvektors der Segmentzentren. Ein klassisches Masse-Feder-Systemwird dabei nicht benötigt,
da bereits überschneidungsfreie Segmente keinerlei Interaktion bedürfen.
Proportionale Kräfte
Ein erster Ansatz war es, die Strafkräfte proportional zu der Überschneidungsfläche zu skalieren.
Dabei wurde zum Problem, dass ähnliche Segmente im initialen Layout sehr dicht beieinander
liegen. Die daraus resultierende Überschneidungsfläche führte zu entsprechend großen Strafkräf-
ten, wodurch die Segmente im ersten Iterationsschritt zu weit auseinander getrieben wurden.
Zusätzlich verhinderten die schwachen Kräfte bei geringer Überlappung eine rasche Konvergenz
gegen einen stabilen Zustand.
Trotz verschiedener Ansätze, die Kräfte linear oder auch nichtlinear aus der Überschneidungs-
fläche abzuleiten, konnten diese Probleme nicht hinreichend behoben werden. Zusätzlich trieb
die fortlaufende Berechnung dieser Flächen die Laufzeit des Verfahrens weiter in die Höhe.
Aus diesen Gründen wurde der Ansatz zu Gunsten eines einfacheren nicht mehr weiter verfolgt.
Alles-oder-nichts-Kräfte
Damit der Aufwand für die Kraftberechnung drastisch reduziert werden konnte, wurde sie durch
ein einfaches Alles-oder-nichts-Prinzip ersetzt. Sollten Segmente sich überlappen, werden sie
dementsprechend mit einer festen Kraft F auseinandergetrieben, unabhängig von der Über-
schneidungsfläche oder sonstigen Faktoren.
Durch diesen simplen Ansatz können große Sprünge bei den ersten Iterationen effektiv verhin-
dert werden, ebenfalls wird auch die Konvergenz nicht unnötig ausgebremst.
Zusätzliche Rotation der Segmente
DieAnordnungenmüssennachDefinition imGesamtennicht dicht gepackt sein. Dennoch sollen in
den ordnungsbedingt dichteren Gebieten keine unnötigen Leerräume durch die Verschiebungen
der Kollisionsvermeidung entstehen.
25
5 Anordnung von Bildsegmenten
Damit diese Leerräume minimiert werden können, wird zusätzlich eine optionale Rotation ein-
geführt. Diese funktioniert ähnlich wie die Strafkräfte nach dem Alles-oder-nichts-Prinzip. Dabei
werden die Objekte bei einer Überschneidung um einen festen Winkel α rotiert. Die Richtung
ergibt sich aus demWinkel zwischen der Hauptachse des Segments und dem Verbindungsvektor
der Segmentpositionen. Ist dieserWinkel kleiner als 90◦, wird alpha aufaddiert, ansonsten abgezo-
gen. Dadurch versuchen die Segmente sich gegenseitig möglichst parallel und somit platzsparend
auszurichten.
Gesamtverfahren
Zum Überblick wird in Abbildung 5.2 die gesamte Kollisionsbehandlung an einem einfachen
Beispiel verdeutlicht.
α1 α2
~F1 ~F2
(a) Vorher (b) Nacher
Abbildung 5.2: Schema der Kollisionsverhinderung inklusive Rotation.
Durch die Überschneidung werden die Segmente zum einen entlang der Richtung
des Verbindungsvektors der Segmentpositionen auseinandergeschoben und zum
anderen in Richtung einer parallelen Ausrichtung rotiert.
Abbildung 5.3 zeigt ein konkretes Beispiel des Verfahrens, in Abbildung A.2 im Anhang finden
sich weitere in Form einer Streudiagramm-Matrix.
(a) Initiales Layout (b) Verfeinertes Layout
Abbildung 5.3: Beispiel des zweistufigen Ansatzes am BildMoulin Rouge. Die Segmente sind initial
in x-Richtung nach der Sättigung, in y-Richtung nach der Helligkeit angeordnet.
26
5.5 Hierarchische Erweiterung durch Clustering
5.5 Hierarchische Erweiterung durch Clustering
Die bloße Ordnung der Segmente führt noch oft zu dünnbesetzten Bereichen. Auch wenn diese
Abstände Informationen beinhalten, kann es sowohl ästhetischer als auch informativer sein, die
Dichteverteilung besser hervorzuheben.
Dazu wird in dem zweidimensionalen Merkmalsraum auf dem das initiale Layout basiert eine
Clusterung vorgenommen. Die Segmente werden daraufhin in der fertigen Anordnung in diesen
Clustern konzentriert.
5.5.1 Clusterung im Merkmalsraum
Für das Clustering kommt der bereits bekannte Mean-Shift-Algorithmus zum Einsatz. Er arbei-
tet diesmal in dem von den beiden gewählten Merkmalen aufgespannten, zweidimensionalen
Merkmalsraum.
Die Daten werden dabei wie gewohnt zunächst gefiltert. Das Zusammenfassen zu Segmenten
wurde bei der Mean Shift Segmentation per Region Growing erledigt. Da das Verfahren allerdings
auf einem festen Gitter basiert, kann es in dem kontinuierlichen Merkmalsraum so nicht verwen-
det werden. Es kann allerdings leicht angepasst werden, wenn statt der Vierernachbarschaft ein
zweidimensionaler runder Kernel verwendet wird.
Zur Nachbearbeitung bietet es sich abermals an, zu kleine Cluster mit dem nächstgelegenen
zu verschmelzen. Auf diese Weise können Ausreißer in die Ordnung eingegliedert werden. Eine
Verschmelzung von nahen Clustern hingegen ist in diesem Szenario nicht notwendig.
Im Folgenden werden die einzelnen Cluster zunächst getrennt angeordnet und anschließend
als Ganzes im Zielbild platziert.
5.5.2 Kreisförmige Cluster
Werden die Segmente eines Clusters nach dem bisher verwendeten zweistufigen Ansatz angeord-
net, ergibt sich nicht zwangsläufig eine runde Form. Damit dieses Ziel dennoch erreicht werden
kann, wird eine zusätzliche Kompressionskraft eingeführt. Diese drückt die Segmente unabhängig
von Überschneidungen in Richtung des Clusterzentrums. Sie fängt zunächst stark an, um eine
Kompression zu garantieren. Anschließend nimmt sie jedoch über zehn Iterationen hinweg stetig
ab, um die Kollisionsvermeidung wieder zu ermöglichen.
Um die Form noch weiter zu optimieren, wird außerdem die Segmentrotation überschrie-
ben. Die Segmente werden jetzt jeder Zeit mit ihrer Hauptachse senkrecht zum Clusterradius
ausgerichtet.
Clusteranordnung
Die Cluster selbst werden, um die Ordnung auch in höherer Ebene zu bewahren, entsprechend
ihrerModi im Bild platziert. Damit die Anordnung jedoch auch im Ganzen einen runden Charakter
annimmt, wird die Clusteranordnung wiederum nach dem gleichen Prinzip wie die Segmentan-
ordnungen innerhalb der Cluster verfeinert. Das heißt, sie werden ebenfalls bei Überschneidung
auseinander geschoben und auch anfangs durch eine Kompressionskraft näher zusammengeführt.
Anders ist dabei nur, dass die Cluster nicht rotiert werden.
27
5 Anordnung von Bildsegmenten
5.5.3 Stapelförmige Cluster
Damit die Segmente eines Clusters gut gestapelt werden können, müssen sie zunächst waagerecht
ausgerichtet werden. Diese Ausrichtung bleibt ab diesem Punkt auch fest, Rotationen finden
nicht mehr statt.
Für die Stapelform werden abermals Strafkräfte verwendet. Diesmal sind diese jedoch nur
parallel zur x-Ache in Richtung des Clusterzentrums gerichtet. Entlang der y-Achse wird leicht in
Richtung des tiefsten Segments geschoben, um Ausreißer zu verdichten.
Clusteranordnung
Bei diesem Ansatz werden die Cluster auf eine andere Art angeordnet. Die Platzierung orientiert
sich mehr an denen von Wehrli [Weh02], der die Segmente ebenfalls gruppiert, stapelt und
entlang der x-Achse aufreiht.
Dementsprechend wird auch hier vorgegangen. Zunächst werden die Cluster nach ihrer Ge-
samtfläche, sprich der Summe der Flächen der enthaltenen Segmente, sortiert. Daraufhin werden
die Cluster, beginnend mit dem größten, mit der Unterkante auf die x-Achse gesetzt, jeweils mit
einem kleinen Abstand rechts neben dem zuletzt platzierten.
Als Sortierkriterium wurde zunächst auch mit der Segmentanzahl der Cluster experimentiert,
allerdings wird die Anordnung bei stark unterschiedlichen Segmentgrößen schnell unintuitiv.
(a) Verfeinertes Layout (b) Kreisförmiges Layout
(c) Stapelförmiges Layout
Abbildung 5.4: Beispiel der verschiedenen Clusterformen am Bild Krawatten.
Die Segmente sind initial nach Rot-Grün- und Gelb-Blau-Kontrast angeordnet.
Dabei wird deutlich, wie sehr das Clustering zu einem ordentlichen Eindruck
beiträgt.
28
6 Ergebnisse
6.1 Qualitative Ergebnisse
6.1.1 Segmentierung von Farbbildern
Die beiden Segmentierungsverfahren funktionieren ähnlich gut. Das Mean Shift Verfahren ist
jedoch robuster gegenüber hohen Bildfrequenzen, sodass es bei verrauschten Bildern besse-
re Ergebnisse liefert. Die Wasserscheidentransformation hingegen findet auch in gleichmäßig
gefärbten Bildern mehr Details.
(a) Original (b) Mean Shift Segmentierung (c) Wasserscheidentransf.
Abbildung 6.1: Vergleich von Mean Shift und Wasserscheidentransformation am Bild Seemonster
Die Wasserscheidentransformation kann im Gegensatz zur Mean Shift Segmentie-
rung auch in dem sehr weich gezeichneten Bild noch diverse Segmente finden.
6.1.2 Anordnung von Bildsegmenten
Aus eigenen Beobachtungen hat sich ergeben, dass sich für die Anordnung in erster Linie Merk-
male aus dem Farbraum eignen. Das lässt sich damit erklären, dass die Segmentierung, aus der
die Segmente hervorgehen, selbst im Farbraum arbeitet. Dadurch wird die Farbe automatisch das
markanteste Segmentmerkmal.
Von diesen Merkmalen eignen sich vor allem die Kombinationen Grün-Rot-Kontrast und
Blau-Gelb-Kontrast, die zusammen die Bunttonebene aufspannen. Des Weiteren hat sich die
Kombination aus Helligkeit und Sättigung hervorgetan, neben dem Buntton die beiden anderen
Eindrücke über die wir nach Graßmann [Gra53] Farben wahrnehmen.
Eine weitere Besonderheit fällt bei den Stapellayouts auf. Hier ist zu beobachten, dass vor
allen ähnliche Merkmale, wie beispielsweise Größe und Räumliche Standardabweichung, oder
abermals die beiden Buntkontraste, zu intuitiven Ergebnissen führen. Auch hierfür findet sich
eine Erklärung: Durch die Anordnung der Stapel an der x-Achse geht eine räumliche Dimension
verloren. Kombinationen von möglichst voneinander abhängigen Merkmalen liefern ebenfalls
relativ lineare Anordnungen und bilden deshalb auf diese eine Achse besonders gut ab.
29
6 Ergebnisse
6.2 Evaluierung anhand einer Benutzerstudie
Die entwickelten Verfahren sollen in einer Nutzerstudie evaluiert werden. Dabei ist besonders
von Interesse, welche Merkmale die Benutzer als geeignete Ordnungskriterien empfinden. Da die
Anzahl an Kombinationsmöglichkeiten für zehnMerkmale und zwei Anordnungenmit (102 )·2 = 90pro Bild allerdings für eine sinnvolle Sondierung viel zu groß ist, musste diese Menge zunächst
reduziert werden.
Darum wurde sich durch eine Vorauswahl auf die sechs Merkmale Größe, Kompaktheit, Grün-
Rot-Kontrast, Blau-Gelb-Kontrast, Helligkeit und Sättigung beschränkt.
6.2.1 Aufgabenstellung
Die Teilnehmer sollten eine Menge von 30 verschiedenen Anordnungen pro Bild nach ihrem
eigenen Geschmack sortieren.
6.2.2 Durchführung
Durchgeführt wurde die Studie in Form einer Online-Umfrage. Die Teilnehmer bekamen auf
der Startseite zuerst eine Erklärung zu der Thematik und wie die Studie zu bedienen ist. Nach
einer Bestätigung diese Erklärung verstanden zu haben, folgte zugleich die eigentliche Studie.
Auf einer Seite wurde links oben das Ursprungsbild als Referenz angezeigt. Im mittleren und
rechten Drittel wurden in einem 5x6 Gitter die 30 möglichen Anordnungen zufällig verteilt. Diese
konnten mit der Maus im Gitter verschoben und zur Detailansicht gezoomt werden. Nachdem
die Teilnehmer mit der Sortierung der Anordnungen zufrieden waren, gelangten sie über einen
Button zur nächsten Seite.
Insgesamt wurden so jedem Teilnehmer vier zufällig gewählte Bilder angezeigt, für die er
die Anordnungen sortieren musste. Als letzte Seite wurde noch ein Freitextfeld für Kritik und
Kommentare angezeigt, im Anschluss war die Studie beendet.
Über die Teilnehmer wurden dabei keinerlei Daten erhoben, so dass keine Aussagen über
beispielsweise ihr Geschlecht oder ihre Bevölkerungsgruppe gemacht werden kann.
6.2.3 Auswertung
Leider führte die Studie zu keinen verwertbaren Daten, die 23 Datensätze lassen keine Tendenzen
erkennen.
In dem Freitextfeld wurde dementsprechend bemängelt, dass es zu viele zu ähnliche Anord-
nungen waren um sie komplett zu ordnen.
Daraus folgt, dass für eine erneute Studie entweder die Anzahl an Merkmalen noch weiter
reduziert werden muss, oder auch hier jeder Teilnehmer nur eine zufällige Auswahl zu sehen
bekommt. Alternativ können die Anforderungen auch gelockertwerden, indemnur die besten und
schlechtesten n Anordnungen tatsächlich sortiert werden müssen, und die dazwischenliegenden
nicht gewertet werden.
30
7 Ausblick
7.1 Zusammenfassung
Der Hauptteil der Arbeit lässt sich in zwei Teile zerlegen.
7.1.1 Zerlegung von Farbbildern
In dieser Arbeit wurden zunächst Segmentierungsverfahren gesucht um Farbbilder in ihre Kon-
stituenten zu zerlegen. Dazu wurde ein Überblick über die zahlreichen Verfahren gebildet und
schließlich zwei davon ausgewählt.
Diese Verfahren, namentlich Mean Shift Segmentierung undWasserscheidentransformation, wur-
den implementiert und untersucht. Mit beiden konnten dabei gute Ergebnisse erzielt werden.
Die Mean Shift Segmentierung schnitt in puncto Übersegmentierung etwas besser ab, die Was-
serscheidentransformation war dafür um ein vielfaches schneller.
7.1.2 Anordnung der Konstituenten
Die Anordnung der Bildsegmente wurde in zwei Schritte unterteilt. Zunächst werden die Seg-
mente anhand von zwei wählbaren Merkmalen im Bildraum geordnet, wobei Sortierung und
Abstände der Merkmale erhalten bleiben. Daraufhin werden die Segmente mit einem iterativen
Verfahren verschoben, bis keine Überschneidungen mehr auftreten.
Dieser Ansatz wurde noch weiter überarbeitet, indem die Segmente zunächst nach ihren
gewählten Merkmalen zu Clustern zusammengefügt werden. Innerhalb der Cluster werden sie
wie gewohnt angeordnet, wobei zusätzlich noch darauf geachtet wird den Clustern eine feste
Form zu geben. Diese Cluster werden daraufhin selbst im Bildraum angeordnet. Als Clusterformen
wurde mit Kreisen und Stapeln experimentiert, die beide gut funktionierten.
7.2 Künftige Arbeiten
Ursus Wehrli, dessen Werke die Inspiration zu dieser Arbeit lieferten, hat sich vom Kunstaufräu-
mer zum Performancekünstler weiterentwickelt, indem er jetzt physische Objekte, wie beispiels-
weise Autos auf einem Parkplatz, sortiert [Weh11]. Auf diesemWeg kann ihmmit denWerkzeugen
der automatischen Bildverarbeitung nicht weiter gefolgt werden.
Nichtsdestotrotz gibt es noch genug Möglichkeiten die vorhandenen Erkenntnisse zu verbes-
sern oder neue Ansätze daraus zu entwickeln.
7.2.1 Verbesserungen des Bestehenden
Die implementierten Verfahren können noch weiterentwickelt werden. Hier war nicht das Mögli-
che, sondern viel mehr die zur Verfügung stehende Zeit die Grenze.
31
7 Ausblick
Segmentierungsalgorithmen
Die verwendete Mean Shift Segmentierung wurde bereits 2002 von Christoudias et al. [CGM02]
weiterentwickelt. Dabei gewichten sie die Pixel entsprechend des Gradientenbetragsbildes um
die Segmentierung noch weiter zu verbessern.
Bei der Wasserscheidentransformation gibt es auch zahlreiche Ansätze zur Verbesserung. So
kann der Übersegmentierung beispielsweise mit einem hierarchischen Ansatz, der Wasserfall-
transformation, begegnet werden [Tön05]. Rahman und Islam [RI13] hingegen führen eine eigene
Wasserscheidentransformation auf jedem Farbkanal durch und kombinieren die Ergebnisse ge-
schickt.
Pan et al. [PZW03] kombinieren sogar die beiden verwendeten Algorithmen.
Für bessere Abbruchkriterien wurden von Zhang et al. [ZFG08] und Heidemann [Hei08] Maße
zur automatischen Evaluierung von Segmentierungen formuliert.
Anordnungen
Bei der Behandlung des Hintergrundes besteht noch Raum für Verbesserungen. So kann bei-
spielsweise mittels Objekterkennung tatsächlich versucht werden zerfallene Objekte wieder
zusammenzufügen. Oder die daraus gezogene Semantik kann die Wahl des Hintergrundes be-
einflussen. Möglich wäre auch Einzelfälle zu erkennen, bei denen Inpainting-Verfahren zur
Hintergrundsrestauration tatsächlich gute Ergebnisse liefern.
Die Skalierung der Merkmale kann ebenfalls mit Nutzerstudien noch weiter optimiert werden.
Ebenso wie die Grenzen der Zyklischen Merkmale mithilfe von Dichteanalysen weiter verfeinert
werden können.
Neue Clusterformen, wie beispielsweise Sterne, bieten ebenfalls noch viel Raum für Kreativität.
7.2.2 Neues und Aufbauendes
Bei den Anordnungen dieser Arbeit stand hauptsächlich die Ästhetik im Vordergrund. Diesen
Ansatz kann man noch weiter ausbauen um in weiteren Studien zu erforschen, welche Merkmale
und Merkmalskombinationen Menschen als ansehnlich empfinden, und welche nicht.
Denkbar währen jedoch auch in eine andere Richtung zu gehen und neue Verfahren zur Infor-
mationsvisualisierung zu entwickeln.
32
A Weitere Abbildungen
Ke
rn
elr
ad
ius
im
Or
tsr
au
m
(in
Pix
eln
)
32
16
8
4
4 8 16
Kernelradius im Farbraum (in ∆E99-Einheiten)
Abbildung A.1: Auswirkung der Kernelradien beim Mean-Shift-Filter am Bild Venus.
Das Ausgangsbild ist 512x322 Pixel groß und der Mean-Shift wurde bei einer
Schrittweite von unter 0,03LE abgebrochen.
33
A Weitere Abbildungen
Größe
σ der
Pixelposi-
tionen
Kompakt-
heit
Helligkeit
Grün-Rot-
Kontrast
Blau-
Gelb-
Kontrast
Sättigung
Farbton
σ der
Farben
Ausrich-
tungswin-
kel
Abbildung A.2: Streudiagramm-Matrix der Segmentmerkmale für das Bild Holzfäller.
Dabei werden Streudiagramme für alle möglichen Merkmalskombinationen in
einem Gitter angeordnet. Zur Visualisierung wurden in den Streudiagrammen
statt Punkten die tatsächlichen Segmente platziert und Verdeckungen durch
Verschiebung und Rotation vermieden.
Wegen symmetrischer Redundanz wird nur die untere Hälfte der Matrix dar-
gestellt. Die Einträge in der Hauptdiagonale geben an welches Merkmal in der
Spalte/Zeile für die x- resp. y-Achse verwendet wurde.
34
B Beispielimplementierung
Im Rahmen dieser Arbeit entstand die Beispielimplementierung tidy. Mit ihr ist es möglich Bilder
zu laden, die Verfahren und zugehörigen Parameter zu wählen und Segmentierungen sowie
Anordnungen zu generieren.
Abbildung B.1: GUI der Beispielimplementierung tidy
Links können die implementierten Verfahren und Parameter gewählt werden. In der dreigeteil-
ten Mitte wird links das Originalbild dargestellt. In der Mitte wird die Segmentierung dargestellt,
indem jedes Segment mit seiner Durchschnittsfarbe gefärbt wird. Rechts schließlich wird die
fertige Anordnung ausgegeben.
35

Literaturverzeichnis
[BL79] Beucher, Serge ; Lantuéjoul, Christian: Use of watersheds in contour detection. In:
International workshop on image processing, real-time edge and motion detection, 1979
[BSMM05] Bronstein, Ilja N. ; Semendjajew, Konstantin A. ;Musiol, Gerhard ;Mühlig, Heiner:
Taschenbuch der Mathematik. 6. Harri Deutsch, 2005. – ISBN 3–8171–2006–0
[CGM02] Christoudias, C.M. ; Georgescu, B. ;Meer, P.: Synergism in Low Level Vision. In:
Proceedings of the 16th International Conference on Pattern Recognition Bd. 4, IEEE, 2002
(ICPR ’02). – DOI 10.1109/ICPR.2002.1047421. – ISBN 0–7695–1695–X, S. 150–155
[CJSW01] Cheng, H.D. ; Jiang, X.H. ; Sun, Y. ;Wang, Jingli: Color Image Segmentation: Advances
and Prospects. In: Pattern Recognition 34 (2001), Dezember, Nr. 12, S. 2259–2281. – DOI
10.1016/S0031–3203(00)00149–7. – ISSN 0031–3203
[CM02] Comaniciu, Dorin ;Meer, Peter: Mean shift: A robust approach toward feature space
analysis. In: IEEE Transactions on Pattern Analysis andMachine Intelligence 24 (2002), Mai,
Nr. 5, S. 603–619. – DOI 10.1109/34.1000236. – ISSN 0162–8828
[DIN01] NormDIN 6176März 2001. Farbmetrische Bestimmung von Farbabständen bei Körperfarben
nach der DIN99-Formel
[DIN11] Norm DIN EN ISO 11664-4 Juli 2011. Farbmetrik – Teil 4: CIE 1976 L*a*b* Farbenraum
[DKLS06] Dalal, Ketan ; Klein, Allison W. ; Liu, Yunjun ; Smith, Kaleigh: A Spectral Approach
to NPR Packing. In: Proceedings of the 4th International Symposium on Non-photorealistic
Animation and Rendering. New York, NY, USA : ACM, Juni 2006 (NPAR ’06). – DOI
10.1145/1124728.1124741. – ISBN 1–59593–357–3, S. 71–78
[FH75] Fukunaga, K. ; Hostetler, L.: The estimation of the gradient of a density function,
with applications in pattern recognition. In: IEEE Transactions on Information Theory 21
(1975), Januar, Nr. 1, S. 32–40. – DOI 10.1109/TIT.1975.1055330. – ISSN 0018–9448
[Gra53] Grassmann, Hermann G.: Zur Theorie der Farbenmischung. In: Annalen der Physik
165 (1853), Nr. 5, S. 69–84. – DOI 10.1002/andp.18531650505. – ISSN 1521–3889
[Hau01] Hausner, Alejo: Simulating Decorative Mosaics. In: Proceedings of the 28th Annual
Conference on Computer Graphics and Interactive Techniques. New York, NY, USA : ACM,
August 2001 (SIGGRAPH ’01). – DOI 10.1145/383259.383327. – ISBN 1–58113–374–X, S.
573–580
[Hei08] Heidemann, Gunther: Region Saliency as a Measure for Colour Segmentation Sta-
bility. In: Image and Vision Computing 26 (2008), Februar, Nr. 2, S. 211–227. – DOI
10.1016/j.imavis.2007.05.001. – ISSN 0262–8856
37
Literaturverzeichnis
[HLT+09] Hurtut, T. ; Landes, P.-E. ; Thollot, J. ;Gousseau, Y. ;Drouillhet, R. ; Coeurjolly, J.-
F.: Appearance-guided Synthesis of Element Arrangements by Example. In: Proceedings
of the 7th International Symposium on Non-Photorealistic Animation and Rendering. New
York, NY, USA : ACM, August 2009 (NPAR ’09). – DOI 10.1145/1572614.1572623. – ISBN
1–60558–604–5, S. 51–60
[HM08] Haindl, M. ; Mikeš, S.: Texture Segmentation Benchmark. In: 19th International
Conference on Pattern Recognition, IEEE, Dezember 2008 (ICPR ’08). http://mosaic.
utia.cas.cz, Abruf: 13.11.2014. – DOI 10.1109/ICPR.2008.4761118. – ISBN 1–4244–
2174–9, 1–4
[KP02] Kim, Junhwan ; Pellacini, Fabio: Jigsaw Image Mosaics. In: Proceedings of the 29th
Annual Conference on Computer Graphics and Interactive Techniques. New York, NY, USA :
ACM, Juli 2002 (SIGGRAPH ’02). – DOI 10.1145/566570.566633. – ISBN 1–58113–521–1,
S. 657–664
[Kra75] Krantz, David H.: Color measurement and color theory: I. Representation theorem
for Grassmann structures. In: Journal of Mathematical Psychology 12 (1975), Nr. 3, S.
283–303. – DOI 10.1016/0022–2496(75)90026–7. – ISSN 0022–2496
[LD05] Lagae, Ares ; Dutré, Philip: A Procedural Object Distribution Function. In: ACM
Transactions on Graphics 24 (2005), Nr. 4, S. 1442–1461. – DOI 10.1145/1095878.1095888.
– ISSN 0730–0301
[Pea01] Pearson, Karl: On lines and planes of closest fit to systems of points in space. In:
The London, Edinburgh and Dublin Philosophical Magazine and Journal of Science Series 6 2
(1901), Nr. 11, S. 559–572. – DOI 10.1080/14786440109462720
[PZW03] Pan, Chen ; Zheng, Cong-Xun ;Wang, Hao-Jun: Robust color image segmentation
based on mean shift and marker-controlled watershed algorithm. In: International
Conference on Machine Learning and Cybernetics Bd. 5, IEEE, November 2003 (ICMLC ’03).
– DOI 10.1109/ICMLC.2003.1260013. – ISBN 0–7803–8131–9, S. 2752–2756
[RI13] Rahman, M.H. ; Islam, M.R.: Segmentation of Color Image using Adaptive Threshol-
ding andMaskingwithWatershedAlgorithm. In: International Conference on Informatics,
Electronics & Vision, IEEE, 2013 (ICIEV ’13). – DOI 10.1109/ICIEV.2013.6572557. – ISBN
1–4799–0397–9, S. 1–6
[RRDR09] Raut, S. ;Raghuvanshi, M. ;Dharaskar, R. ;Raut, A.: Image Segmentation—A State-
Of-Art Survey for Prediction. In: International Conference on Advanced Computer Control,
IEEE, Januar 2009 (ICACC ’09). – DOI 10.1109/ICACC.2009.78. – ISBN 1–4244–3330–8, S.
420–424
[RRS13] Reinert, Bernhard ; Ritschel, Tobias ; Seidel, Hans-Peter: Interactive By-example De-
sign of Artistic Packing Layouts. In: ACM Transactions on Graphics 32 (2013), November,
Nr. 6, S. 218:1–218:7. – DOI 10.1145/2508363.2508409. – ISSN 0730–0301
[SLH10] Schmidt, Robert F. ; Lang, Florian ; Heckmann, Manfred: Physiologie des Menschen –
mit Pathophysiologie. 31. Springer, 2010. – ISBN 3–6420–1650–2
[Tön05] Tönnies, Klaus D.: Grundlagen der Bildverarbeitung. Pearson Studium, 2005. – ISBN
3–8273–7155–3
38
Literaturverzeichnis
[Weh02] Wehrli, Ursus: Kunst aufräumen. Kein & Aber, 2002. – ISBN 3–0369–5200–0
[Weh04] Wehrli, Ursus: Noch mehr Kunst aufräumen. Kein & Aber, 2004. – ISBN 3–0369–5223–3
[Weh11] Wehrli, Ursus: Die Kunst, aufzuräumen. Kein & Aber, 2011. – ISBN 3–0369–5297–7
[YYT+11] Yu, Lap-Fai ; Yeung, Sai-Kit ; Tang, Chi-Keung ; Terzopoulos, Demetri ; Chan, Tony F.
; Osher, Stanley J.: Make It Home: Automatic Optimization of Furniture Arrangement.
In: ACM SIGGRAPH 2011 Papers. New York, NY, USA : ACM, Juli 2011 (SIGGRAPH ’11). –
DOI 10.1145/1964921.1964981. – ISBN 1–4503–0943–1, S. 86:1–86:12
[ZFG08] Zhang, Hui ; Fritts, Jason E. ; Goldman, Sally A.: Image Segmentation Evaluation:
A Survey of Unsupervised Methods. In: Computer Vision and Image Understanding 110
(2008), Mai, Nr. 2, S. 260–280. – DOI 10.1016/j.cviu.2007.08.003. – ISSN 1077–3142
39

Bildverzeichnis
Holzfäller Kasimir S. Malewitsch: Der Holzfäller. Gemeinfrei, 1912/13.
Krawatten David Wright: Course 2579 – Tie (Ausschnitt). CC BY 2.0, 2012.
https://www.flickr.com/photos/dhwright/6689906321
Leopard Jerine Lay: Leopard Cat Fabric. CC BY 2.0, 2009.
https://www.flickr.com/photos/jerine/6944472527
Mosaik Souz Gerbino:Mosaik. CC BY 2.0, 2011.
https://www.flickr.com/photos/docsu70/5438581761/
Moulin Rouge Henri de Toulouse-Lautrec:Moulin Rouge – La Goulue (Ausschnitt). Gemeinfrei,
1891.
Pizza Andy Ciordia: Pizza Time (Ausschnitt). CC BY-NC 2.0, 2006.
https://www.flickr.com/photos/ciordia/220245404
Seemonster Joseph M. W. Turner: Sunrise with Sea Monsters. Gemeinfrei, 1845.
Sternennacht Vincent van Gogh: De sterrennacht (Ausschnitt). Gemeinfrei, 1889.
Supermarkt Josefine Stenudd: Veganz, a supermarket (Ausschnitt). CC BY-NC 2.0, 2012.
https://www.flickr.com/photos/72616463@N00/8209737977
Venus Sandro Botticelli: La nascita di Venere. Gemeinfrei, ca. 1485/86.
Bildlizenzverzeichnis
CC BY 2.0 Creative Commons Attribution 2.0 Generic
https://creativecommons.org/licenses/by/2.0/
CC BY-NC 2.0 Creative Commons Attribution-NonCommercial 2.0 Generic
https://creativecommons.org/licenses/by-nc/2.0/
Alle URLs wurden zuletzt am 2. März 2015 abgerufen.
41

Erklärung
Ich versichere, diese Arbeit selbstständig verfasst zu haben. Ich
habe keine anderen als die angegebenen Quellen benutzt und alle
wörtlich oder sinngemäß aus anderen Werken übernommene
Aussagen als solche gekennzeichnet.
Weder diese Arbeit noch wesentliche Teile daraus waren bisher
Gegenstand eines anderen Prüfungsverfahrens. Ich habe diese
Arbeit bisher weder teilweise noch vollständig veröffentlicht.
Das elektronische Exemplar stimmt mit allen eingereichten
Exemplaren überein.
Stuttgart, den 2. April 2015
43