TUD Logo

TUD Startseite » ... » Ergebnisse studentischer Arbeiten » Große Belege » S. Broecker

Computergraphik

Großer Beleg von Stefan Broecker

Segmentierung von 3D-Modellen

Studiengang Medieninformatik, Wintersemester 2005/2006
Institut für Software- und Multimediatechnik
Lehrstuhl für Computergraphik und Visualisierung

Hochschullehrer & Betreuer: Prof. Dr. Stefan Gumhold

Inhalt

  • Einleitung
  • Aufgabenstellung
  • Verfahren
  • Umsetzung
  • Kurzbeschreibung der Anwendung
  • Download

Einleitung

In der Computergrafik können Objekte durch polygonale Netze beschrieben werden. Diese sind schnell darstellbar und es existiert eine Vielzahl von Werkzeugen zu deren Bearbeitung. Eine Möglichkeit, um auch detaillierte Objekte darstellen zu können, bietet die Texturierung polygonaler Netze. Dabei legt man Bilddateien über das Netz, um z.B. Farbe oder feine Reliefs darzustellen. Bei der Texturierung kann es nötig sein, ein polygonales Netz in mehrere Teile zu zerlegen, wenn man z.B. bei einem 3D-Modell eines Menschen verschiedene Bilddateien für Arme, Beine, Torso und Kopf nutzen möchte. Diese Zerlegung eines polygonalen Netzes in semantisch bedeutungsvolle Teilnetze nennt man Segmentierung. Beim Betrachten von Bildern wird dies noch anschaulicher. Ein Bild von einem Wanderer in einer Landschaft könnte man z.B. in Vordergrund (Wanderer) und Hintergrund (Berge, Himmel) zerlegen.

Eine mögliche Herangehensweise zur Segmentierung besteht in der Gruppierung ähnlicher Elemente eines Objektes. Dazu betrachtet man deren Merkmale. Elemente mit ähnlichen Merkmalen können gruppiert werden. Hat man bei der Verarbeitung von Bilddateien beispielsweise Graustufen als Merkmale, um Pixel zu gruppieren, so kann man bei 3D-Modellen z.B. Ortskoordinaten oder Normalen zur Gruppierung von Facetten in Betracht ziehen. Um die Ergebnisse einer Segmentierung objektiv beurteilen zu können, führt man Qualitätsmaße ein, die auf den betrachteten Merkmalen basieren.

Aufgabenstellung

Die vorliegende Arbeit verfolgt das Ziel, 3D-Modelle automatisch in primitive Formen zu zerlegen. Beispielsweise sollte ein Würfel in sechs Abschnitte unterteilt werden, wobei jeder Abschnitt eine der sechs ebenen Würfelflächen darstellt. Eine Konservendose dagegen soll in Boden, Deckel und Dosenkörper zerlegt werden. Dafür sollte ein bereits bestehendes Segmentierungsverfahren erweitert werden.

Verfahren

Um ein 3D-Modell in Teilnetze (Cluster) einfacher Formen zerlegen zu können, gruppiert man ähnliche Facetten. Diese Cluster bilden immer eine bestimmte Form aus. Sollen diese Cluster nun die Form von einfachen Objekten aufweisen, nutzt man Referenzobjekte. Diese so genannten Proxies dienen als Vergleichsobjekte zu den jeweiligen Clustern, wobei jeder Cluster einen Proxy zugewiesen bekommt. Je ähnlicher die Cluster zu ihren Proxies sind, desto besser nähern sie sich primitiven Formen an.

Die Proxies können durch quadratische Funktionen repräsentiert werden. Somit hat man die Möglichkeit, z.B. ebene, ellipsoid- und zylinderförmige Bereiche anzunähern. Das Problem besteht nun darin, die richtige Form und Platzierung der Proxies zu bestimmen, damit das polygonale Netz in Cluster mit der Form dieser Proxies unterteilt werden kann.

Eine mögliche Lösung bietet die so genannte Lloyd-Segmentierung. Hierbei betrachtet man das Segmentierungsproblem als Optimierungsproblem. Optimiert bzw. minimiert werden soll der Fehler zwischen den Clustern und ihren Proxies. Man beginnt damit, die Proxies zufällig zu initialisieren und dann iterativ nach der optimalen Form und Platzierung zu suchen. Dazu ist der Algorithmus in zwei Phasen geteilt. In der ersten Phase versucht man die Cluster für feste Proxies zu optimieren. In der zweiten Phase werden die Proxies für feste Cluster optimiert. Durch die iterative Anwendung der beiden Phasen nähern sich die Cluster und die Proxies an, bis ein Minimum erreicht ist. Im Sinne des Optimierungsproblems ist dann eine optimale Segmentierung gefunden.

Screenshot
Links: 3D-Modell ohne Segmentierung, rechts: Modell mit Segmentierung (jeder Cluster wird durch eine Farbe repräsentiert)

Umsetzung

Das Programm wurde in C++ unter Microsoft Visual Studio .NET 2003 entwickelt. Basis war die CGV-Template-Library von Dr. Gumhold. Die GUI bzw. die Anzeige mit OpenGL und bestimmte Routinen waren somit bereits implementiert. Ein bestehendes Segmentierungsverfahren, welches Ebenen als Proxies nutzte, war ebenfalls bereits vorhanden.

Kurzbeschreibung der Anwendung

Gestartet wird das Programm mit der Datei "MeshSegmentor.exe". Um ein 3D-Modell zu laden, klickt man im rechten Fenster oben auf "Mesh" (optional Strg+M) und dann auf den Button "PM". Nun klappt ein Menü auf. Durch Betätigen des oberen "Execute"-Buttons öffnet sich ein Dialog, um die Modell-Datei laden zu können. Im Ordner "Meshes_Polygonal" befinden sich ein paar Beispielmodelle zum Testen.

Im Ansichtsfenster kann man mittels der Maus und optional mit der Alt-Taste den Blickwinkel auf das Objekt ändern. Die Einstellungen für das Segmentierungsverfahren befinden sich im rechten Fenster unter "MeshSegm" (optional Strg+X). Im Folgenden eine Liste der wichtigsten Einstellungen.

  • nrClusters: die Anzahl der Cluster, in die das Modell zerlegt werden soll
  • showProxies/showProxyNr: zeigt den Proxy jedes Clusters nach einer Segmentierung an
  • clusterMeasure: bestimmt, welche Merkmale zur Segmentierung betrachtet werden. Für die vorliegende Arbeit sind die folgenden Metriken relevant.
    • normal: nutzt Facettennormalen als Merkmal / Ebenen als Proxies
    • normalTayl: nutzt Facettennormalen als Merkmal / quadratische Funktionen als Proxies
    • distance: nutzt Ortskoordinaten als Merkmal / Ebenen als Proxies
    • distTayl: nutzt Ortskoordinaten als Merkmal / quadratische Funktionen als Proxies
  • build clustering: führt den gesamten Segmentierungsalgorithmus aus

Eine weitere Möglichkeit zur Nutzung des Programms besteht darin, im Ansichtsfenster mit F1 Tastenkürzel zu aktivieren und Einstellungen vorzunehmen.

Screenshot
Links: Ansichtsfenster, rechts: Optionen für das Segmentierungsverfahren

Download

  • Ausführbares Programm (.zip): Download (8,14 MB)
  • Belegarbeit (.pdf): Download (2,53 MB)
  • Vortragsfolien (.pdf): Download (0,75 MB)
Stand: 1.2.2010, 14:40 Uhr
Autor: Dipl.-Medieninf. cand. Johannes Richter