Approximation eines Umrisses mit einer kleinen Anzahl von Bausteinen
Oliver Burghard
Allgemein
Die Arbeit wurde in Israel verfasst und hat den englischen original Titel: »Shape approximation by an aggregation of a small set of primitives«
Betreuer:
- Prof. Daniel Cohen-Or (Tel Aviv, Isreal)
- Prof. Dr. Hartmut Prautzsch (Karlsruhe)
Motivation
In verschiedenen Bereichen wäre es wünschenswert eine beliebige Figur unter Benutzung einer begrenzten Menge von Bausteinen zu erstellen. Die original Figur wird dafür durch dichtes aneinanderlegen von Kopien der wenigen Bausteinen approximiert. Die Schwierigkeit liegt in der Wahl der Bausteine und in der Anordnung der Kopien. Grundlegend ist dabei die Frage was eine gute Approximation des Originals ausmacht.
Herangehensweise
Zuerst wird definiert was als Approximation und was als Baustein zulässig ist. Die originale Figur wird dann mit diesen Bausteinen dargestellt, zunächst mit beliebig vielen. Durch Zusammenfassen der benutzten Bausteine zu Clustern wird eine Approximation mit einer begrenzten Anzahl von Bausteinen gebildet. Diese wird optimiert durch zufällige Mutation unter Hilfe von Simuliertem Tempern. Ausgehend von der aktuellen Lösung werden dann zufällig ähnliche Lösungen erstellt. Diese werden bewertet und die beste Lösung ersetzt die aktuelle Lösung. Die Bewertungsfunktion vergleicht dazu lokal die originale und approximierte Figur. In die Bewertung fließen ein die Fläche und vom Umriß die Normalen, Krümmungen und die Länge.
Ergebnisse
 |
| Links ist das Ursprungsbild und rechts eine Approximation mit 10 Bausteinen. |
 |
| Für sechs verschiedene Ursprungsbilder (jeweils links) ist daneben eine Approximation mit 10 Bausteinen gegeben. |
Ausblick
Am Ende der Arbeit werden einige Möglichkeiten diskutiert um bessere Ergebnisse zu erzielen. Diese gehören in mehrere Kathegorien:
- das Lockern von Einschränkungen an die Bausteine und die Approximation um bessere Ergebnisse möglich zu machen
- Variation der Mutation um kleinere Minima der Bewertungsfunktion zu erreichen
- genaue Untersuchung der Bewertungsfunktion (Menschliche Wahrnehmung und die Realisierung in der Bewertungsfunktion) damit die Minima der Bewertungsfunktion dem subjektivem Empfinden besser entsprechen.
Darüber hinaus wäre ein entsprechender Algorithmus für den dreidimensionalen Raum interessant.