Levelsatz (Datenstrukturen) – Wikipedia

Posted on by

In der Informatik wird eine Level-Set-Datenstruktur entworfen, um diskret abgetastete dynamische Level-Set-Funktionen darzustellen.

Eine übliche Verwendung dieser Form der Datenstruktur ist das effiziente Rendern von Bildern. Die zugrunde liegende Methode erstellt ein vorzeichenbehaftetes Distanzfeld, das sich von der Grenze aus erstreckt, und kann verwendet werden, um die Bewegung der Grenze in diesem Feld zu lösen.

Chronologische Entwicklungen[edit]

Die leistungsstarke Level-Set-Methode geht auf Osher und Sethian 1988 zurück.[1] Die einfache Implementierung über ein dichtes d-dimensionales Array von Werten führt jedoch sowohl zu Zeit- als auch zu Speicherkomplexität von

Ö((nd){ displaystyle O (n ^ {d})}

, wo

n{ displaystyle n}

ist die Querschnittsauflösung der räumlichen Ausdehnung der Domäne und

d{ displaystyle d}

ist die Anzahl der räumlichen Dimensionen der Domäne.

Schmales Band[edit]

Die 1995 von Adalsteinsson und Sethian eingeführte Schmalband-Level-Set-Methode,[2] Die meisten Berechnungen beschränkten sich auf ein dünnes Band aktiver Voxel, die die Grenzfläche unmittelbar umgeben, wodurch die zeitliche Komplexität in drei Dimensionen auf reduziert wurde

Ö((n2){ displaystyle O (n ^ {2})}

für die meisten Operationen. Regelmäßige Aktualisierungen der Schmalbandstruktur, um die Liste der aktiven Voxel neu zu erstellen, waren erforderlich, was eine

Ö((n3){ displaystyle O (n ^ {3})}

Operation, bei der auf Voxel über das gesamte Volumen zugegriffen wurde. Die Speicherkomplexität für dieses Schmalbandschema war immer noch

Ö((n3).{ displaystyle O (n ^ {3}).}

Differentialkonstruktionen über der Schmalbanddomänenkante erfordern sorgfältige Interpolations- und Domänenänderungsschemata, um die Lösung zu stabilisieren.[3]

Spärliches Feld[edit]

Diese

Ö((n3){ displaystyle O (n ^ {3})}

Die zeitliche Komplexität wurde bei der von Whitaker 1998 eingeführten Methode zur Festlegung des ungefähren “spärlichen Feldes” beseitigt.[4] Die Methode zum Festlegen der Ebene auf geringer Feldebene verwendet eine Reihe verknüpfter Listen, um die aktiven Voxel um die Schnittstelle herum zu verfolgen. Dies ermöglicht eine schrittweise Erweiterung des aktiven Bereichs nach Bedarf, ohne dass ein erheblicher Overhead entsteht. Während konsequent

Ö((n2){ displaystyle O (n ^ {2})}

effizient in der Zeit,

Ö((n3){ displaystyle O (n ^ {3})}

Speicherplatz wird weiterhin von der Methode zum Festlegen der Ebene mit geringer Feldebene benötigt. Sehen[5] für Implementierungsdetails.

Spärliches Blockgitter[edit]

Die 2003 von Bridson eingeführte Methode des spärlichen Blockgitters[6] teilt das gesamte Begrenzungsvolumen der Größe

n3{ displaystyle n ^ {3}}

in kleine kubische Blöcke von

m3{ displaystyle m ^ {3}}

jeweils Voxel. Ein grobes Gitter von Größe

((n/.m)3{ displaystyle (n / m) ^ {3}}

speichert dann nur Zeiger auf die Blöcke, die das schmale Band des eingestellten Pegels schneiden. Blockzuweisung und Freigabe erfolgen, wenn sich die Oberfläche ausbreitet, um den Verformungen Rechnung zu tragen. Diese Methode hat eine suboptimale Speicherkomplexität von

Ö((((nm)3+m3n2){ displaystyle O left ((nm) 3 + m ^ {3} n ^ {2} right)}

, behält aber den konstanten zeitlichen Zugriff bei, der dichten Gittern innewohnt.

Octree[edit]

Die von Strain 1999 eingeführte Octree-Level-Set-Methode[7] und verfeinert von Losasso, Gibou und Fedkiw,[8] und in jüngerer Zeit von Min und Gibou[9] verwendet einen Baum verschachtelter Würfel, deren Blattknoten vorzeichenbehaftete Abstandswerte enthalten. Octree-Level-Sets erfordern derzeit eine gleichmäßige Verfeinerung entlang der Grenzfläche (dh des schmalen Bandes), um eine ausreichende Präzision zu erzielen. Diese Darstellung ist effizient in Bezug auf die Speicherung,

Ö((n2),{ displaystyle O (n ^ {2}),}

und relativ effizient in Bezug auf Zugriffsabfragen,

Ö((Logn).{ displaystyle O ( log , n).}

Ein Vorteil der Level-Methode für Octree-Datenstrukturen besteht darin, dass man die partiellen Differentialgleichungen lösen kann, die mit typischen Problemen der freien Grenzen verbunden sind, die die Level-Set-Methode verwenden. Die CASL-Forschungsgruppe[10] hat diese Arbeit in den Bereichen Computermaterialien, Computational Fluid Dynamics, Elektrokinetik, bildgesteuerte Chirurgie und Kontrollen entwickelt.

Lauflänge codiert[edit]

Die 2004 eingeführte RLE-Level-Set-Methode (Run-Length Coding)[11] wendet das RLE-Schema an, um Bereiche außerhalb des Schmalbandes auf ihre Vorzeichendarstellung zu komprimieren, während das Schmalband mit voller Präzision gespeichert wird. Das sequentielle Durchlaufen des Schmalbandes ist optimal und die Speichereffizienz wird gegenüber dem eingestellten Octree-Level weiter verbessert. Das Hinzufügen einer Beschleunigungsnachschlagetabelle ermöglicht eine schnelle

Ö((Log⁡r){ displaystyle O ( log r)}

Direktzugriff, wobei r die Anzahl der Läufe pro Querschnitt ist. Zusätzliche Effizienz wird durch die Anwendung des RLE-Schemas in einer rekursiven Dimension erzielt, eine Technik, die von Nielsen & Museths ähnlichem DT-Grid eingeführt wurde.[12]

Hash Level Local Level Set[edit]

Die 2011 von Eyiyurekli und Breen eingeführte Hash Table Local Level Set-Methode [13] und 2012 von Brun, Guittet und Gibou erweitert,[14] Berechnet nur die Level-Set-Daten in einem Band um die Schnittstelle, wie bei der Narrow-Band-Level-Set-Methode, speichert aber auch nur die Daten in demselben Band. Es wird eine Hash-Tabellendatenstruktur verwendet, die eine bereitstellt

Ö((1){ displaystyle O (1)}

Zugriff auf die Daten. Brun et al. schlussfolgern, dass ihre Methode zwar einfacher zu implementieren ist, aber schlechter abschneidet als eine Quadtree-Implementierung. Sie finden das

wie es ist, […] Eine Quadtree-Datenstruktur scheint für Level-Set-Algorithmen besser geeignet zu sein als die Hash-Tabellen-Datenstruktur.

Drei Hauptgründe für eine schlechtere Effizienz sind aufgeführt:

  1. Um genaue Ergebnisse zu erhalten, ist in der Nähe der Schnittstelle ein ziemlich großes Band erforderlich, das das Fehlen von Gitterknoten weit entfernt von der Schnittstelle ausgleicht.
  2. Die Leistungen werden durch Extrapolationsverfahren an den Außenkanten des lokalen Gitters und verschlechtert
  3. Die Breite des Bandes schränkt den Zeitschritt ein und verlangsamt die Methode.

Punktbasiert[edit]

Corbett im Jahr 2005 [15] führte die punktbasierte Level-Set-Methode ein. Anstatt eine einheitliche Abtastung des Pegelsatzes zu verwenden, wird die kontinuierliche Pegelsatzfunktion aus einem Satz unorganisierter Punktabtastwerte über das Verschieben der kleinsten Quadrate rekonstruiert.

Verweise[edit]

  1. ^ Osher, S. & Sethian, JA 1988. “Fronten, die sich mit krümmungsabhängiger Geschwindigkeit ausbreiten: Algorithmen basierend auf Hamilton-Jacobi-Formulierungen”. Journal of Computation Physics 79: 12–49.
  2. ^ Adalsteinsson, D. & Sethian, JA 1995. “Eine schnelle Level-Set-Methode zur Verbreitung von Schnittstellen.” Zeitschrift für Computerphysik. 118 (2) 269–277.
  3. ^ Adalsteinsson, D; Sethian, J. (1994). “Eine schnell eingestellte Methode zur Weitergabe von Schnittstellen”. Zeitschrift für Computerphysik. 118 (2): 269. Bibcode:1995JCoPh.118..269A. CiteSeerX 10.1.1.46.1716. doi:10.1006 / jcph.1995.1098.
  4. ^ Whitaker, RT 1998. “Ein Level-Set-Ansatz zur 3D-Rekonstruktion aus Entfernungsdaten.” Internationale Zeitschrift für Computer Vision. 29 (3) 203–231.
  5. ^ S. Lankton. “Sparse Field Method – Technischer Bericht.” 21. April 2009http://www.shawnlankton.com/2009/04/sfm-and-active-contours/>
  6. ^ Bridson, R. 2003. “Computergestützte Aspekte dynamischer Oberflächen (Dissertation).” Stanford University, Stanford, Kalifornien.
  7. ^ Strain, J. 1999. “Baummethoden zum Verschieben von Schnittstellen.” Zeitschrift für Computerphysik. 151 (2) 616–648.
  8. ^ Losasso, F., Gibou, F. & Fedkiw, R. 2004. Simulation von Wasser und Rauch mit einer Octree-Datenstruktur. ACM-Transaktionen auf Grafiken. 23 (3) 457–462.
  9. ^ Min, C. & Gibou, F. 2007. Eine genaue Level-Set-Methode zweiter Ordnung für nicht abgestufte adaptive kartesische Gitter. Zeitschrift für Computerphysik. 225 (1) 300–321.
  10. ^ http://www1.engr.ucsb.edu/~fgibou/Research.html
  11. ^ Houston, B., Nielsen, M., Batty, C., Nilsson, O. & K. Museth. 2006. “Hierarchisches RLE-Level-Set: Eine kompakte und vielseitige Darstellung verformbarer Oberflächen.” ACM-Transaktionen auf Grafiken. 25 (1).
  12. ^ Nielsen, MB & Museth K. 2006. “Dynamic Tubular Grid: Eine effiziente Datenstruktur und Algorithmen für hochauflösende Level-Sets.” Journal of Scientific Computing. 26 (1) 1–39.
  13. ^ Eyiyurekli, M. & Breen, D. 2011. “Datenstrukturen für die interaktive hochauflösende Oberflächenbearbeitung mit eingestellter Ebene”, Proc. Grafikschnittstelle. S. 95-102.
  14. ^ Brun, E., Guittet, A. & Gibou, F. 2012. “Eine lokale Level-Set-Methode unter Verwendung einer Hash-Tabellen-Datenstruktur.” Zeitschrift für Computerphysik. 231 (6) 2528-2536.
  15. ^ Corbett, R. 2005. “Punktbasierte Level-Sets und Fortschritte in Richtung unorganisierter Partikel-Level-Sets (These).” Universität von British Columbia, Kanada.