006 Spezielle Computerverfahren
Filtern
Dokumenttyp
- Bachelorarbeit (1)
- Dissertation (1)
- Masterarbeit (1)
Sprache
- Englisch (3) (entfernen)
Schlagworte
- Ad-hoc-Netz (1)
- Algorithmische Geometrie (1)
- Beaconless (1)
- Distributed Algorithm (1)
- Drahtloses Sensorsystem (1)
- Drahtloses vermachtes Netz (1)
- Ebener Graph (1)
- Geographic routing (1)
- Geometric spanner (1)
- Graph (1)
Institut
Diese Bachelorarbeit erforscht eine Methode zur 3D-Objekterkennung und Posenschätzung, basierend auf dem Punkte-Paare-Eigenschaften-Verfahren (PPE) von Drost et. al. [Dro+10]. Die Methoden der Posenschätzung haben sich in den letzten Jahre zwar deutlich verbessert, stellen jedoch weiterhin ein zentrales Problem im Bereich der Computervisualistik dar. Im Rahmen dieser Arbeit wurde ein Programm implementiert, welches Punktewolkenszenen als Ausgangspunkt erhält und daraus eine Objekterkennung und Posenschätzung durchführt. Das Programm deckt alle Schritte eines Objekterkennungsprogramm ab, indem es 3D-Modelle von Objekten verarbeitet, um deren PPE zu extrahieren. Diese Eigenschaften werden gruppiert und in einer Tabelle gespeichert. Anhand des Auswahlverfahrens, bei dem die Übereinstimmung der Eigenschaften überprüft wird, können potenzielle Posen des Objekts ermittelt werden. Die Posen mit der größten Übereinstimmung werden miteinander verglichen, um ähnliche Posen zu gruppieren. Die Gruppen mit der höchsten Übereinstimmung werden erneut überprüft, sodass am Ende nur eine Pose ausgewählt wird. Das Programm wurde anhand von Real– und Simulationsdaten Daten getestet. Die erhaltenen Ergebnisse wurden anschließend analysiert und evaluiert.
Die Material Point Method (MPM) hat sich in der Computergrafik als äußerst fähige Simulationsmethode erwiesen, die in der Lage ist ansonsten schwierig zu animierende Materialien zu modellieren [1, 2]. Abgesehen von der Simulation einzelner Materialien stellt die Simulation mehrerer Materialien und ihrer Interaktion weitere Herausforderungen bereit. Dies ist Thema dieser Arbeit. Es wird gezeigt, dass die MPM durch die Fähigkeit Eigenkollisionen implizit handzuhaben ebenfalls in der Lage ist Kollisionen zwischen Objekten verschiedenster Materialien zu beschreiben, selbst, wenn verschiedene Materialmodelle eingesetzt werden. Dies wird dann um die Interaktion poröser Materialien wie in [3] erweitert, was ebenfalls gut mit der MPM integriert. Außerdem wird gezeigt das MPM auf Basis eines einzelnen Gitters als Untermenge dieses Mehrgitterverfahrens betrachtet werden kann, sodass man das gleiche Verhalten auch mit mehreren Gittern modellieren kann. Die poröse Interaktion wird auf beliebige Materialien erweitert, einschließlich eines frei formulierbaren Materialinteraktionsterms. Das Resultat ist ein flexibles, benutzersteuerbares Framework das unabhängig vom Materialmodell ist. Zusätzlich wird eine einfache GPU-Implementation der MPM vorgestellt, die die Rasterisierungspipeline benutzt um Schreibkonflikte aufzulösen. Anders als andere Implementationen wie [4] ist die vorgestellte Implementation kompatibel mit einer Breite an Hardware.
Reaktiv lokale Algorithmen sind verteilte Algorithmen, die den Anforderungen großer, batteriebetriebener, Drahtloser Ad Hoc und Sensornetzwerke im besonderen Maße gerecht werden. Durch Vermeidung überflüssiger Nachrichtenübertragungen sowie Verzicht auf proaktive Ermittlung von Nachbarschaftstabellen (d.h. beaconing) minimieren solche Algorithmen den Kommunikationsaufwand und skalieren gut bei wachsender Netzgröße. Auf diese Weise werden Ressourcen wie Bandbreite und Energie geschont, es kommt seltener zu Nachrichtenkollisionen und dadurch zu einer Erhöhung der Paketempfangsrate, sowie einer Reduktion der Latenzen.
Derzeit wird diese Algorithmenklasse hauptsächlich für Geografisches Routing, sowie zur Topologiekontrolle, insbesondere zur Ermittlung der Adjazenzliste eines Knotens in zusammenhängenden, kantenschnittfreien (planaren) Repräsentationen des Netzgraphen, eingesetzt. Ersteres ermöglicht drahtlose multi-hop Kommunikation auf Grundlage von geografischen Knotenpositionen ohne Zuhilfenahme zusätzlicher Netzwerkinfrastruktur, wohingegen Letzteres eine hinreichende Grundlage für effiziente, lokale Lösungen einer Reihe algorithmischer Problemstellungen ist.
Die vorliegende Dissertation liefert neue Erkenntnisse zum Forschungsgebiet der reaktiven Algorithmen, zum Einen auf einer abstrakten Ebene und zum Anderen durch die Einführung neuer Algorithmen.
Erstens betrachtet diese Arbeit reaktive Algorithmen erstmalig im Ganzen und als eigenständiges Forschungsfeld. Es wird eine umfangreiche Literaturstudie zu dieser Thematik präsentiert, welche die aus der Literatur bekannten Algorithmen, Techniken und Anwendungsfelder systematisch auflistet, klassifiziert und einordnet. Weiterhin wird das mathematische Konzept der O- und Omega-reaktiv lokalen Topologiekontrolle eingeführt. Dieses Konzept ermöglicht erstmals die eindeutige Unterscheidung reaktiver von konventionellen, beacon-basierten, verteilten Topologiekontrollalgorithmen. Darüber hinaus dient es als Klassifikationsschema für existierende, sowie zukünftige Algorithmen dieser Art. Zu guter Letzt ermöglicht dieses Konzept grundlegende Aussagen über die Mächtigkeit des reaktiven Prinzips, welche über Entwurf und Analyse von Algorithmen hinaus reichen.
Zweitens werden in dieser Arbeit neue reaktiv lokale Algorithmen zur Topologiekontrolle und Geografischem Routing eingeführt, wobei drahtlose Netze durch Unit Disk bzw. Quasi Unit Disk Graphen modelliert werden. Diese Algorithmen berechnen für einen gegebenen Knoten die lokale Sicht auf zusammenhängende, planare, Euklidische bzw. Topologische Spanner mit konstanter Spannrate bzgl. des Netzgraphen und routen Nachrichten reaktiv entlang der Kanten dieser Spanner, wobei die Nachrichtenauslieferung garantiert wird. Alle bisher bekannten Verfahren sind entweder nicht reaktiv oder gewährleisten keine konstanten Euklidischen oder Topologischen Spannraten. Ein wesentliches Teilergebnis dieser Arbeit ist der Nachweis, dass die partielle Delaunay Triangulierung (PDT) ein Euklidischer Spanner mit konstanter Spannrate für Unit Disk Graphen ist.
Die in dieser Dissertation gewonnenen Erkenntnisse bilden die Basis für grundlegende und strukturierte Forschung auf diesem Gebiet und zeigen, dass das reaktive Prinzip ein wichtiges Werkzeug des Algorithmenentwurfs für Drahtlose Ad Hoc und Sensornetzwerke ist.