Wie man einen Punkt auf ein verzerrtes Gitter abbildet

Question

Angenommen, Sie haben eine Sammlung von Punkten mit Koordinaten in einem kartesischen Koordinatensystem.

Sie möchten einen anderen Punkt zeichnen und kennen seine Koordinaten im gleichen kartesischen Koordinatensystem.

Die Zeichnung, auf die Sie sich stützen, ist jedoch gegenüber dem Original verzerrt. Stellen Sie sich vor, Sie nehmen die ursprüngliche Ebene, drucken sie auf eine Gummiplatte und dehnen sie an einigen Stellen und drücken sie an anderen asymmetrisch zusammen (keine Überlappung oder etwas Komplexes).

( Quelle )

Sie kennen die gestreckten und ungestreckten Koordinaten der einzelnen Punkte, aber nicht die zugrunde liegende Streckfunktion. Sie kennen die ungestreckten Koordinaten eines neuen Punktes.

Wie kann man auf der Grundlage der gestreckten Positionen der benachbarten Punkte abschätzen, wo der neue Punkt in den gestreckten Koordinaten eingezeichnet werden soll? Es muss nicht exakt sein, da man die tatsächliche Streckungsfunktion nicht aus einer Reihe von neu zugeordneten Punkten bestimmen kann, wenn man nicht über weitere Informationen verfügt.

andere mögliche Schlüsselwörter: verzerrt verzerrtes Gitternetz Netzkoordinaten Ebene unverzerrt

Answer 1

Ok, das klingt nach Image Warping. Das sollten Sie tun:

1. Erstellen einer Delaunay-Triangulation Ihres unverzerrten Gitters und verwenden Sie Ihr Wissen über die Korrespondenzen zwischen dem verzerrten und dem unverzerrten Gitter, um die Triangulation für das verzerrte Gitter zu erstellen. Jetzt kennen Sie die entsprechenden Dreiecke in jedem Bild und da es keine Überschneidungen gibt, sollten Sie den nächsten Schritt ohne große Schwierigkeiten durchführen können.

2. Um nun den entsprechenden Punkt zu finden A in dem verzerrten Bild:

   1. Finden Sie das Dreieck A liegt und die Transformation zwischen dem Dreieck im unverzerrten Gitter und dem verzerrten Gitter verwendet, um die neue Position zu ermitteln.

Dies wird ausdrücklich und ausführlich erklärt hier .

Eine andere (viel kompliziertere) Methode ist die Dünne Platte Spline (was auch in den obigen Folien erklärt wird).

Answer 2

Ich habe es so verstanden, dass Sie eine Eins-zu-eins-Entsprechung zwischen den umhüllten und nicht umhüllten Gitterpunkten haben. Und ich gehe davon aus, dass die Verformung nicht so extrem ist, dass sich die Gitterlinien überschneiden (wie in dem von Ihnen gezeigten Bild).

Die Strategie ist genau das, was Jacob vorschlägt: Triangulieren Sie die beiden Gitter so, dass eine Eins-zu-Eins-Entsprechung zwischen den Dreiecken besteht, lokalisieren Sie den zu kartierenden Punkt in der Triangulation und verwenden Sie dann baryzentrische Koordinaten im entsprechenden Dreieck, um die neue Punktposition zu berechnen.

Vorverarbeiten

1. Erzeugen Sie die Delaunay-Triangulation der Punkte des umhüllten Gitters, nennen wir es WT .
2. Für jedes Dreieck in WT fügen Sie ein Dreieck zwischen den entsprechenden Scheitelpunkten im nicht umrahmten Gitter ein. Dies ergibt eine Triangulation UWT der nicht umschlossenen Punkte.

Einen Punkt kartieren p in das umhüllte Gitter

1. Finden Sie das Dreieck T(p1,p2,p3) en el UWT die Folgendes enthält p .
2. Berechnen Sie die baryzentrische Koordinaten (b1,b2,b3) de p en T(p1,p2,p3)
3. Sea Tw(q1,q2,q3) sei das Dreieck in WT entsprechend T(p1,p2,p3) . Die neue Position lautet
   b1 * q1 + b2 * q2 + b3 * q3 .

Bemerkungen Daraus ergibt sich eine Deformationsfunktion als a linearer Spline . Für ein glatteres Verhalten könnte man dieselbe Triangulation verwenden, aber eine Annäherung höherer Ordnung vornehmen, was zu einer etwas komplizierteren Berechnung anstelle der baryzentrischen Koordinaten führen würde.

Answer 3

Die anderen Antworten sind großartig. Das Einzige, was ich hinzufügen möchte, ist, dass Sie vielleicht einen Blick darauf werfen sollten Verformung der freien Form als Mittel zur Beschreibung der Verformungen.

Wenn das nützlich ist, dann ist es durchaus möglich, ein Verformungsgitter an die bekannten Paare anzupassen, und dann haben Sie eine sehr schnelle Methode, um zukünftige Punkte zu verformen.

Answer 4

Vieles hängt davon ab, wie viele Punkte Sie bereits haben. Wenn Sie nur einen haben, können Sie damit nicht viel anfangen - Sie können den zweiten Punkt um denselben Betrag in dieselbe Richtung verschieben, aber Sie haben nicht genug Daten, um wirklich mehr zu erreichen.

Wenn Sie eine größere Anzahl vorhandener Punkte haben, können Sie eine Oberflächenanpassung durch diese Punkte vornehmen und damit die richtige Position des neuen Punktes annähern. Bei N Punkten kann man mit einem Polynom der Ordnung N immer eine perfekte Anpassung erzielen, aber das ist selten der Fall. Stattdessen geht man normalerweise davon aus, dass die Streckfunktion eine Funktion niedriger Ordnung ist (z. B. quadratisch oder kubisch) und passt auf dieser Grundlage eine Fläche an die Punkte an. Anschließend platzieren Sie den neuen Punkt auf der Grundlage der Funktion für die angepasste Fläche.