Gaußsche Unschärfe einer über einem Oberflächennetz definierten Funktion

8

Ich habe eine Skalarfunktion über den Eckpunkten eines Oberflächennetzes definiert. Ich möchte eine ungefähre (und verallgemeinerte, nehme ich an) "Gaußsche Unschärfe / Faltung" dieser Funktion über die Oberfläche berechnen.

Ich kann mir vorstellen, für jeden Scheitelpunkt einen Durchschnitt der Funktion an Scheitelpunkten in seiner (Multi-Hop-) Nachbarschaft zu nehmen, gewichtet nach dem Gaußschen ihrer euklidischen Entfernung (in R3) vom aktuellen Scheitelpunkt multipliziert mit dem lokalen Bereich, den sie darstellen. Diese Annäherung wäre gut, wenn die Oberfläche im Maßstab des Gaußschen Kerns nicht zu gekrümmt wäre. Es wäre jedoch immer noch rechenintensiv.

Gibt es einen effizienteren Faltungsalgorithmus, der möglicherweise auf einer Art iteriertem "Fluss" oder teilweisem Austausch durch Kanten des Netzes basiert?

Das Netz kann entweder dreieckige oder viereckige Flächen haben - je nachdem, was für die Beantwortung dieser Frage bequemer ist. Die Kantenlängen sind jedoch nicht konstant, sodass sich die lokale Nachbarschaftsgeometrie zwischen den Scheitelpunkten unterscheidet.

mesh gaussian-blur Museful
quelle
Benötigen Sie eine Nachbarschaft, die über die unmittelbaren Nachbarn hinausgeht, oder wären Sie an Annäherungen interessiert, die auf der wiederholten Anwendung eines Ansatzes für die nächsten Nachbarn beruhen?
Trichoplax
@trichoplax Solange die Anzahl der Iterationen, die erforderlich sind, um eine 10-Hop-Standardabweichung zu erreichen, nicht unerschwinglich ist. (Ich denke, das wäre nicht der Fall, da zumindest im 1D-Fall eine 10-Sprung-Abweichung erreicht werden kann, indem die nächsten Nachbarn 100 Mal gemischt werden.) Ich würde in diesem Fall einfach nicht wissen, wie die Nachbarn gewichtet werden sollen.
Museful
@joojaa Es ist trennbar, wenn es auf eine flache Oberfläche / ein flaches Gitter angewendet wird. Ist es dennoch trennbar, wenn Kanten von jedem Scheitelpunkt in beliebige Richtungen verlaufen?
Museful
@Museful Ok where iterative kleinere Unschärfen , die eine größere sind , dass , wie Sie es nur Verbindungen über den Rand tun können , und lassen Sie die Iterationen die Wirkung propagete. Dies ist in der FEM und Flüssigkeit sims hohen Wirkungsgrad verwendet
joojaa
1
Ich bin nicht sicher, ich bin nicht so tief in die Hintergrundgeschichte von FEM investiert. Alles , was ich weiß , dass sie die Diffusion über unregelmäßige Maschen lösen können , und das ist ganz analog mit Gaußsche Unschärfe.
joojaa

Antworten:

6

Ein paar verschiedenen Ansätze

Ich werde einige Variationen Ihrer spezifischen Anfrage in Betracht ziehen, da Sie die Effizienz erwähnen und ich vermute, dass Ihre spezifische Anfrage die am wenigsten effiziente ist. Ich werde auch Möglichkeiten zur Verbesserung der Effizienz vorschlagen, ohne von Ihrem beabsichtigten Ansatz abzuweichen, damit Sie die Alternativen abwägen können.

Verwischen des Volumens anstelle der Oberfläche

Wenn Sie möchten, dass die Abstandsmetrik eine euklidische 3D-Entfernung anstelle einer euklidischen 2D-Entfernung innerhalb der Oberfläche ist, können Sie die Unschärfe in einem regulären 3D-Raster ausführen, auf das die von Ihnen beabsichtigte Skalarfunktion angewendet wurde. Anschließend können Sie das Endergebnis Ihrer Differenz der Gaußschen Werte verwenden, um die Skalarwerte an den Eckpunkten Ihres unregelmäßigen Netzes zu berechnen. Dadurch wird vermieden, dass die Netzform für den Großteil der Berechnung berücksichtigt werden muss.

Das 3D-Gitter hat wahrscheinlich eine viel größere Anzahl von Scheitelpunkten als das 2D-Netz, aber sie sind alle gleich weit voneinander entfernt und die große Kernel-Unschärfe kann durch wiederholtes Anwenden einer kleinen Kernel-Unschärfe erreicht werden, wobei nur die 6 nächsten Nachbarn berücksichtigt werden. das wird immer in einem konstanten Abstand entfernt sein. Dieser Ansatz beinhaltet möglicherweise mehr Berechnungen, aber die Leichtigkeit, mit der das reguläre Netz GPU-beschleunigt werden könnte, kann attraktiv sein.

Dies ergibt ein anderes Ergebnis als die Unschärfe an den Netzscheitelpunkten unter Verwendung des euklidischen 3D-Abstands. Beispielsweise wird der 3D-Gitteransatz durch bestimmte Bereiche der 3D-Skalarfunktion beeinflusst, die sich in der Nähe des Netzes befinden, sich jedoch nicht auf dem Netz befinden. Dies kann abhängig von Ihrem spezifischen Zweck wünschenswert sein oder nicht.

Verwenden der 2D-Entfernung anstelle der 3D-Entfernung

Wenn Sie feststellen, dass die Abstandsmetrik innerhalb der Oberfläche 2D-euklidisch sein muss, können Sie eine gute Annäherung an eine größere Kernel-Gauß-Unschärfe erhalten, indem Sie wiederholt eine kleinere Kernel-Gauß-Unschärfe anwenden. Wenn die Kantenlängen in Ihrem Netz nicht zu stark variieren, können Sie möglicherweise eine Kernelgröße auswählen, bei der bei jeder Iteration nur Scheitelpunkte mit einer Kante entfernt berücksichtigt werden. Dies ermöglicht die Verwendung nur einzelner Kantenlängen zur Berechnung der Größe des Beitrags eines Scheitelpunkts, anstatt einen 2D-Mehrkantenabstand zu berechnen.

3D-Abstand unter Verwendung der Oberfläche ohne Volumen

Wenn Sie möchten, dass die Berechnung genau wie in Ihrer Frage beschrieben ist und nicht innerhalb des umgebenden Volumens, sondern auch innerhalb des euklidischen 3D-Abstands berechnet wird, funktioniert die Verwendung der nächsten Nachbarn und mehrerer Iterationen nicht. Wenn das Netz nicht nahezu flach ist, führt die wiederholte Anwendung einer Unschärfe des nächsten Nachbarn zu einer Annäherung an den euklidischen 2D-Abstandsfall, da die Werte nur von Scheitelpunkt zu Scheitelpunkt bluten können und nicht direkt auf dem kürzesten Weg, wie sie sind würde in einem einzigen Durchgang. Dies ergibt eine geringere Streuung als bei einem einzelnen Durchgang, bei dem der 3D-Abstand zu einem 10 Kanten entfernten Scheitelpunkt berechnet wird. (Ich habe 10 Kanten verwendet, seit Sie in Ihrem Kommentar zu der Frage einen 10-Sprung erwähnt haben.)

Das Implementieren der Unschärfe in einem einzigen Durchgang bedeutet, dass der euklidische 3D-Abstand zwischen jedem Scheitelpunkt und jedem anderen Scheitelpunkt innerhalb eines Radius von 10 Kanten berechnet wird. Dies wird teuer, aber durchaus möglich. Da Sie die Effizienz erwähnen, sollten Sie berücksichtigen, dass Sie einige Redundanzen beseitigen können, sofern Sie über ausreichend verfügbaren Speicher verfügen.

Die beiden Unschärfen, die Sie vor der Differenzierung der Gaußschen Werte erzeugen, verwenden denselben Satz von 3D-Abständen bis zum Kantenradius der kleineren Kernel-Unschärfe. Wenn Sie diese speichern können, müssen Sie sie nur einmal und nicht einmal pro Unschärfe berechnen.

Außerdem wird jeder Abstand zweimal pro Unschärfe verwendet - einmal in jeder Richtung, da die Länge von Scheitelpunkt A zu Scheitelpunkt B der Länge von B nach A entspricht. Durch Zwischenspeichern / Speichern dieser Abstände werden sie nicht zweimal berechnet.

Effekte von beliebig vielen Kanten entfernt

Wenn die Oberflächenkurven so sind, dass einige Scheitelpunkte, die viele Kanten entfernt sind, immer noch nahe genug sind, um sich in 3D-Entfernung gegenseitig zu beeinflussen, müssen Sie möglicherweise alle Scheitelpunkte innerhalb eines bestimmten 3D-Radius berücksichtigen, anstatt Scheitelpunkte innerhalb einer bestimmten Anzahl von Kanten entfernt zu berücksichtigen , unabhängig davon, wie lang der Weg über Kanten ist. In diesem Fall können Sie weniger Scheitelpunkte berücksichtigen, indem Sie die Raumpartitionierung verwenden und eine bestimmte Methode auswählen, die zum Netz passt.

Wenn Sie nicht möchten, dass Teile der Oberfläche, die sich einander nähern, sich gegenseitig beeinflussen, möchten Sie wahrscheinlich eine 2D-Abstandsmetrik anstelle der 3D-Metrik.

Wenn Sie einen großen Bereich unterschiedlicher Kantenlängen haben, kann es sein, dass Sie nicht in der Lage sind, eine festgelegte Anzahl von Kanten zu definieren, die durchlaufen werden sollen, selbst wenn das Netz ziemlich flach ist. Auch hier müssen Sie möglicherweise einen 3D-Abstand anstelle einer Anzahl von Kanten definieren und alle Scheitelpunkte berücksichtigen, die innerhalb dieses Radius liegen.

Trichoplax
quelle
Vielen Dank. Meine Erwähnung der euklidischen 3D-Distanz hat mehr Schaden als Nutzen gebracht. Ich habe es nur als teure (und bedingte) Annäherung gemeint, die einfach zu erklären ist. Ich würde die Annäherung nicht verfolgen, wenn sie weniger erreichbar wäre als die ideale Antwort.
Museful
Was ich idealerweise suche, ist das, was Sie "mit 2D-Abstand" nennen. In einem regulären Raster (mit konsistenter lokaler Geometrie) ist dies einfach, da derselbe symmetrische 1-Hop-Nachbarschafts-Kernel (wiederholt) im gesamten Raster angewendet werden kann. Mein eigentliches Problem besteht darin, die Kerngewichte von 1-Hop-Nachbarn um jeden Scheitelpunkt aus der lokalen Geometrie dieser 1-Hop-Nachbarschaft zu bestimmen .
Museful
Jeder Scheitelpunkt hat die Wertigkeit 4, aber die Kantenlängen und -richtungen variieren. (Alternativ (wenn aus irgendeinem Grund planare Flächen das Problem handhabbar machen) kann jede viereckige Fläche entlang ihrer kürzesten Diagonale in zwei (jetzt planare) Dreiecke unterteilt werden. In diesem Fall variiert die Scheitelpunktvalenz zwischen 4 und 8, und die Kantenlängen werden noch vielfältiger .)
Museful
Letztendlich habe ich einen Scheitelpunkt mit einem Ring von Nachbarn in unterschiedlichen Abständen und Winkeln, und ich muss die lokalen Kernelgewichte über diesen Nachbarn kennen. Die Beschränkung des Mittelwerts / Schwerpunkts des Kernels auf "in der Mitte" (was in diesem Fall vermutlich bedeutet, dass die mittlere Krümmungsnormale vom Scheitelpunkt entfernt ist) beschränkt 2DoF bereits auf die Gewichte des Kernels. Die Auswahl einer Varianz bietet eine weitere Einschränkung. Das System ist jedoch immer noch unterbestimmt, da die Wertigkeit> 3 ist. Wie wählt man die Gewichte?
Museful
Ja, "2D-Abstand verwenden" ist etwas vage. Ich denke, wir sollten zwischen "kürzester Kantenabstand" und "kürzester Abstand innerhalb der Oberfläche" unterscheiden (was nicht unbedingt an den Kanten bleiben muss). Glücklicherweise wird der Unterschied weniger relevant, je öfter Sie die Unschärfe anwenden (selbst ein Boxfilter nähert sich einer Gaußschen Unschärfe an, wenn er mehrmals angewendet wird). Wenn Sie feststellen können, ob Sie eine Gaußsche Unschärfe mit einem genauen Parameter oder nur eine Gaußsche Unschärfe mit einem einstellbaren Parameter benötigen, können Sie entscheiden, ob ein wiederholter Filter im Box-Stil ausreicht.
Trichoplax