Anpassen impliziter Flächen an orientierte Punktmengen

Ich habe eine Frage zur quadratischen Anpassung an eine Reihe von Punkten und entsprechenden Normalen (oder gleichwertig Tangenten). Das Anpassen von quadratischen Flächen an Punktdaten ist gut erforscht. Einige Werke sind wie folgt:

Typbeschränkte direkte Anpassung von quadratischen Oberflächen , James Andrews, Carlo H. Sequin Computer-Aided Design & Applications, 10 (a), 2013, bbb-ccc
Algebraische Anpassung quadratischer Flächen an Daten , I. Al-Subaihi und GA Watson , University of Dundee

Die Anpassung an projektive Konturen wird auch von einigen Arbeiten behandelt, wie z. B. dieser .

Von all diesen Arbeiten denke ich, dass Taubins Methode zur Quadric-Anpassung ziemlich beliebt ist:

G. Taubin, "Schätzung planarer Kurven, Oberflächen und nichtplanarer Raumkurven, definiert durch implizite Gleichungen, mit Anwendungen zur Kanten- und Bereichsbildsegmentierung ", IEEE Trans. PAMI. 13, 1991, S. 1115–1138.

Lassen Sie mich kurz zusammenfassen. Ein quadratisches $Q$ kann in der algebraischen Form geschrieben werden:

f (c, x) = A x^{2} + B y^{2} + C z^{2} + 2 D x y + 2 E x z + 2 F y z + 2 G x + 2 H y + 2 I z + J

$f(\mathbf{c},\mathbf{x}) = A x^2 + By^2 + Cz^2 + 2Dxy + 2Exz + 2Fyz + 2Gx + 2Hy + 2Iz + J$ wobei

c

$\mathbf{c}$ der Koeffizientenvektor ist und

x

$\mathbf{x}$ sind die 3D-Koordinaten. Jeder Punkt

x

$\mathbf{x}$ liegt auf dem Quadrat

Q

$Q$ wenn

x^{T} Q x = 0

$\mathbf{x}^TQ\mathbf{x}=0$ , wobei:

Q = [\begin{matrix} A & D & E & G \\ D & B & F & H \\ E & F & C & I \\ G & H & I & J \end{matrix}]

$Q = \begin{bmatrix} A & D & E & G \\ D & B & F & H \\ E & F & C & I \\ G & H & I & J \\ \end{bmatrix}$

Algebraische Anpassung Im Prinzip möchten wir nach den Parametern suchen, die die Summe der quadratischen geometrischen Abstände zwischen den Punkten und der quadratischen Oberfläche minimieren. Leider stellt sich heraus, dass dies ein nicht konvexes Optimierungsproblem ohne bekannte analytische Lösungen ist. Stattdessen besteht ein Standardansatz darin, nach einer algebraischen Anpassung zu suchen, dh nach den Parametern $\mathbf{c}$ zu lösen, die Folgendes minimieren:

\sum_{i = 1}^{n} f (c, x^{i})^{2} = c^{T} M c

$\sum\limits_{i=1}^{n} f(\mathbf{c},\mathbf{x}^i)^2 = \mathbf{c}^T M \mathbf{c}$ mit

M = \sum_{i = 1}^{n} l (x^{i}) l (x^{i})^{T}

$M = \sum\limits_{i=1}^{n} l(\mathbf{x}^i)l(\mathbf{x}^i)^T$ wobei

{x^{i}}

$\{\mathbf{x}^i\}$ die Punkte in der Punktwolke sind und

l = [x^{2}, y^{2}, z^{2}, x y, x z, y z, x, y, z, 1]^{T}

$l = [x^2, y^2, z^2, xy, xz, yz, x,y,z, 1]^T$

Beachten Sie, dass eine solche direkte Minimierung die triviale Lösung mit $\mathbf{c}$ am Ursprung ergeben würde. Diese Frage wurde in der Literatur ausführlich untersucht. Eine Lösung, die sich in der Praxis als gut erwiesen hat, ist die oben zitierte Taubin-Methode, mit der die Einschränkung eingeführt wird:

‖ \nabla_{x} f (c, x^{i}) ‖^{2} = 1

$\| \nabla_x f(\mathbf{c},\mathbf{x}^i) \|^2 = 1$

Dies kann wie folgt gelöst werden: Sei: wobei Indizes die Ableitungen bezeichnen. Die Lösung ergibt sich aus der verallgemeinerten Eigenzerlegung . Der am besten passende Parametervektor ist gleich dem Eigenvektor, der dem kleinsten Eigenwert entspricht.

N = \sum_{i = 1}^{n} l_{x} (x^{i}) l_{x} (x^{i})^{T} + l_{y} (x^{i}) l_{y} (x^{i})^{T} + l_{z} (x^{i}) l_{z} (x^{i})^{T}

$N = \sum\limits_{i=1}^n l_x(\mathbf{x}^i)l_x(\mathbf{x}^i)^T+ l_y(\mathbf{x}^i)l_y(\mathbf{x}^i)^T + l_z(\mathbf{x}^i)l_z(\mathbf{x}^i)^T$

(M - λ N) c = 0

$(M −\lambda N) \mathbf{c} = 0$

Hauptfrage In vielen Anwendungen sind die Normalen der Punktwolke verfügbar (oder werden berechnet). Die Normalen des Quadrats können auch durch Differenzieren und Normalisieren der impliziten Oberfläche berechnet werden: $\mathbf{N}(x)$

N (x) = \frac{\nabla f (c, x)}{‖ \nabla f (c, x) ‖}

$\mathbf{N}(x) = \frac{\nabla f(\mathbf{c},\mathbf{x})}{\|\nabla f(\mathbf{c},\mathbf{x})\|}$ wobei

\nabla f (c, x) = 2 [\begin{matrix} A x + D y + F z + G \\ B y + D x + E z + H \\ C z + E y + F x + I \end{matrix}]

$\nabla f(\mathbf{c},\mathbf{x}) = 2 \begin{bmatrix} Ax + Dy + Fz + G \\ By + Dx + Ez + H \\ Cz + Ey + Fx + I \\ \end{bmatrix}$

Taubins Methode verwendet jedoch nur die Punktgeometrie und nicht den Tangentenraum. Und mir sind nicht viele Methoden bekannt, die zum Anpassen von Quadriken geeignet sind, so dass die Tangenten der Quadrik auch mit den Tangenten der zugrunde liegenden Punktwolke übereinstimmen. Ich suche nach möglichen Erweiterungen der oben genannten Methode oder einer anderen, um diese Derivate erster Ordnung abzudecken.

Was ich erreichen möchte, wird möglicherweise teilweise in niederdimensionalen Räumen mit primitiveren Oberflächentypen (Kurven) angesprochen. Zum Beispiel Einpassen Linien auf Bildkanten unter Berücksichtigung der Gradienteninformation bedeckt ist hier . Das Anpassen von Ebenen (eine einfache Art von Quadrik) an 3D-Wolken ist sehr häufig ( Link 1 ), oder das Anpassen von Kugeln oder Zylindern kann an orientierte Punktmengen angepasst werden ( Link 2 ). Was ich mich frage, ist etwas Ähnliches, aber das angepasste Grundelement ist ein Quadriz.

Ich würde auch die Analyse der vorgeschlagenen Methode begrüßen, wie zum Beispiel:

Was ist die Mindestanzahl an orientierten Punkten?
Was sind die entarteten Fälle?
Kann man etwas über Robustheit sagen?

Update : Ich möchte eine Richtung vorstellen, der ich folgen soll. Formal, was ich erreichen möchte:

‖ \nabla f - n ‖ = 0

$\| \nabla f - \mathbf{n} \| = 0$ am Punkt . Vielleicht ist es möglich, es mit Taubins Methode zu verschmelzen, um eine zusätzliche Einschränkung zu finden und die Verwendung von Lagrange-Multiplikatoren zu minimieren?

x

$\mathbf{x}$

computational-geometry regression geometry curve-fitting Tolga Birdal
quelle

Sind nicht viele Elemente von Q in Q falsch positioniert?

Museful

Sie haben Recht, und ich habe dies jetzt behoben.

Tolga Birdal

Antworten:

Ich war überrascht, dass ich keine zufriedenstellende Antwort auf die obige Frage erhalten hatte, und meine Untersuchungen zeigten, dass dies tatsächlich ein unerforschter Bereich ist. Daher habe ich einige Anstrengungen unternommen, um Lösungen für dieses Problem zu entwickeln, und die folgenden Manuskripte veröffentlicht:

T. Birdal, B. Busam, N. Navab, S. Ilic und P. Sturm. "Ein minimalistischer Ansatz zur typunabhängigen Erkennung von Quadriken in Punktwolken." Vorträge der IEEE-Konferenz zu Computer Vision und Mustererkennung. 2018. http://openaccess.thecvf.com/content_cvpr_2018/html/Birdal_A_Minimalist_Approach_CVPR_2018_paper.html

T. Birdal, B. Busam, N. Navab, S. Ilic und P. Sturm, "Generische primitive Detektion in Punktwolken unter Verwendung neuartiger minimaler quadratischer Anpassungen", in IEEE-Transaktionen zur Musteranalyse und Maschinenintelligenz. https://arxiv.org/abs/1901.01255

Ich werde hier kurz auf die Hauptidee eingehen:

Dieser Ansatz ähnelt der Gradienten-Eins-Anpassung ( ). Wir richten den Gradientenvektor des Quadrats an der Normalen der Punktwolke . Im Gegensatz zu -fits verwenden wir jedoch eine lineare Einschränkung, um den Rang zu erhöhen, anstatt die Lösung zu regulieren. Dies scheint nicht trivial zu sein, da die Vektor-Vektor-Ausrichtung eine nichtlineare Einschränkung in einer der folgenden Formen mit sich bringt: $\nabla 1$ $\nabla \mathbf{Q}(\mathbf{x}_i)$ $\mathbf{n}_i \in \mathbb{R}^3$ $\nabla 1$

\begin{aligned} \frac{\nabla Q (x_{i})}{‖ \nabla Q (x_{i}) ‖} - n_{i} = 0 or \frac{\nabla Q (x_{i})}{‖ \nabla Q (x_{i}) ‖} \cdot n_{i} = 1. \end{aligned}

$\begin{align} \frac{\nabla \mathbf{Q}(\mathbf{x}_i)}{\|\nabla \mathbf{Q}(\mathbf{x}_i)\|} - \mathbf{n}_i\, = \,0\,\quad\text{or}\,\quad \frac{\nabla \mathbf{Q}(\mathbf{x}_i)}{\|\nabla \mathbf{Q}(\mathbf{x}_i)\|} \,\cdot\, \mathbf{n}_i\, = \,1. \end{align}$ Die Nichtlinearität wird durch die Normalisierung verursacht, da es schwierig ist, die Größe und damit die homogene Skala im Voraus zu kennen. Wir lösen dieses Problem, indem wir eine normale homogene Skala unter den Unbekannten einführen und schreiben: wobei Stapeln für alle Punkte und Normalen führt zu einem System der Form :

α_{i}

$\alpha_i$

\begin{aligned} \nabla Q (x_{i}) = \nabla v_{i}^{T} q = α_{i} n_{i} \end{aligned}

$\begin{align} \nabla \mathbf{Q}( \mathbf{x}_i) = \nabla \mathbf{v}^T_i \mathbf{q} = \alpha_i \mathbf{n}_i \end{align}$

v = {[\begin{matrix} x^{2} & y^{2} & z^{2} & 2 x y & 2 x z & 2 y z & 2 x & 2 y & 2 z & 1 \end{matrix}]}^{T}

$\mathbf{v} = \begin{bmatrix} x^2 & y^2 & z^2 & 2xy & 2xz & 2yz & 2x & 2y & 2z & 1 \end{bmatrix}^T$

N

$N$

x_{i}

$\mathbf{x}_i$

n_{i}

$\mathbf{n}_i$

A^{'} q = 0

$\mathbf{A}^{\prime}\mathbf{q}=\mathbf{0}$

[\begin{matrix} v_{1}^{T} & 0 & 0 & \dots & 0 \\ v_{2}^{T} & 0 & 0 & \dots & 0 \\ ⋮ & ⋮ & ⋮ & ⋱ & ⋮ \\ v_{n}^{T} & 0 & 0 & \dots & 0 \\ \nabla v_{1}^{T} & - n_{1} & 0_{3} & \dots & 0_{3} \\ \nabla v_{2}^{T} & 0_{3} & - n_{2} & \dots & 0_{3} \\ ⋮ & ⋮ & ⋮ & ⋱ & ⋮ \\ \nabla v_{n}^{T} & 0_{3} & 0_{3} & \dots & - n_{n} \end{matrix}] [\begin{matrix} A \\ B \\ ⋮ \\ I \\ J \\ α_{1} \\ α_{2} \\ ⋮ \\ α_{n} \end{matrix}] = 0

$\begin{equation} \begin{bmatrix} \mathbf{v}^T_1 & 0 & 0 & \cdots & 0 \\ \mathbf{v}^T_2 & 0 & 0 & \cdots & 0 \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ \mathbf{v}^T_n & 0 & 0 & \cdots & 0 \\ {\nabla \mathbf{v}_1^T} & -\mathbf{n}_1 & \mathbf{0}_3 & \cdots & \mathbf{0}_3 \\ {\nabla \mathbf{v}_2^T} & \mathbf{0}_3 & -\mathbf{n}_2 & \cdots & \mathbf{0}_3 \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ {\nabla \mathbf{v}_n^T} & \mathbf{0}_3 & \mathbf{0}_3 & \cdots & -\mathbf{n}_n \end{bmatrix} \begin{bmatrix} A \\ B \\ \vdots \\ I \\ J \\ \alpha_1 \\ \alpha_2 \\ \vdots \\ \alpha_n \end{bmatrix} = \mathbf{0} \end{equation}$ - \ mathbf {n} _n \ end {bmatrix} \ begin {bmatrix} A \\ B \\ \ vdots \\ I \\ J \\ \ alpha_1 \\ \ alpha_2 \\ \ vdots \\ \ alpha_n \ end { bmatrix} = \ mathbf {0} \ end {Gleichung} wobei , ist a

\nabla v_{i}^{T} = \nabla v (x_{i})^{T} \in R^{3 \times 10}

${\nabla \mathbf{v}_i^T}= {\nabla \mathbf{v}(\mathbf{x}_i)^T \in \mathbb{R}^{3\times 10}}$

0_{3}

$\mathbf{0}_3$

3 \times 1

$3\times 1$ Spaltenvektor von Nullen, ist und sind die unbekannten homogenen Skalen.

A^{'}

$\mathbf{A}^\prime$

4 N \times (N + 10)

$4N\times(N+10)$

α = {α_{i}}

$\boldsymbol{\alpha}=\{\alpha_i\}$

Während die Lösung dieser Formulierung, die im Nullraum von akzeptable Ergebnisse liefert, ist das System in seinen Möglichkeiten völlig uneingeschränkt (die Skalierungsfaktoren sind zu frei). Es ist besser, einen geeigneten Regularisierer zu finden, dessen Implementierung ebenfalls nicht zu kompliziert ist. In der Praxis könnten wir, wieder analog zur Anpassung mit Gradient 1, Polynomgradienten mit Einheitsnorm bevorzugen und somit oder äquivalent schreiben , einen gemeinsamen Skalierungsfaktor. Diese weiche Einschränkung $\mathbf{A}^{\prime}$ $\alpha_i=1$ $\alpha_i \gets \bar{\alpha}$ wird versuchen, einen Nullsatz des Polynoms zu erzwingen, der die lokale Kontinuität der Daten berücksichtigt. Eine solche Regularisierung erspart uns auch das Lösen des empfindlichen homogenen Systems und ermöglicht es uns, das System in einer kompakteren Form neu zu schreiben : $\mathbf{A}\mathbf{q}=\mathbf{n}$

[\begin{matrix} x_{1}^{2} & y_{1}^{2} & z_{1}^{2} & 2 x_{1} y_{1} & 2 x_{1} z_{1} & 2 y_{1} z_{1} & 2 x_{1} & 2 y_{1} & 2 z_{1} & 1 \\ x_{2}^{2} & y_{2}^{2} & z_{2}^{2} & 2 x_{2} y_{2} & 2 x_{2} z_{2} & 2 y_{2} z_{2} & 2 x_{2} & 2 y_{2} & 2 z_{2} & 1 \\ ⋮ \\ 2 x_{1} & 0 & 0 & 2 y_{1} & 2 z_{1} & 0 & 2 & 0 & 0 & 0 \\ 0 & 2 y_{1} & 0 & 2 x_{1} & 0 & 2 z_{1} & 0 & 2 & 0 & 0 \\ 0 & 0 & 2 z_{1} & 0 & 2 x_{1} & 2 y_{1} & 0 & 0 & 2 & 0 \\ 2 x_{2} & 0 & 0 & 2 y_{2} & 2 z_{2} & 0 & 2 & 0 & 0 & 0 \\ 0 & 2 y_{2} & 0 & 2 x_{2} & 0 & 2 z_{2} & 0 & 2 & 0 & 0 \\ 0 & 0 & 2 z_{2} & 0 & 2 x_{2} & 2 y_{2} & 0 & 0 & 2 & 0 \\ ⋮ \end{matrix}] [\begin{matrix} A \\ B \\ C \\ D \\ E \\ F \\ G \\ H \\ I \\ J \end{matrix}] = [\begin{matrix} 0 \\ 0 \\ \dots \\ n_{x}^{1} \\ n_{y}^{1} \\ n_{z}^{1} \\ n_{x}^{2} \\ n_{y}^{2} \\ n_{z}^{2} \\ \dots \end{matrix}]

$\small \begin{bmatrix} x_1^2 & y_1^2 & z_1^2 & 2x_1y_1 & 2x_1z_1 & 2y_1z_1 & 2x_1 & 2y_1 & 2z_1 & 1\\ x_2^2 & y_2^2 & z_2^2 & 2x_2y_2 & 2x_2z_2 & 2y_2z_2 & 2x_2 & 2y_2 & 2z_2 & 1\\ &&&& \vdots &&&&&\\ 2x_1 & 0 & 0 & 2y_1 & 2z_1 & 0 & 2 & 0 & 0 & 0\\ 0 & 2y_1 & 0 & 2x_1 & 0 & 2z_1 & 0 & 2 & 0 & 0\\ 0 & 0 & 2z_1 & 0 & 2x_1 & 2y_1 & 0 & 0 & 2 & 0\\ 2x_2 & 0 & 0 & 2y_2 & 2z_2 & 0 & 2 & 0 & 0 & 0\\ 0 & 2y_2 & 0 & 2x_2 & 0 & 2z_2 & 0 & 2 & 0 & 0\\ 0 & 0 & 2z_2 & 0 & 2x_2 & 2y_2 & 0 & 0 & 2 & 0\\ &&&& \vdots &&&&& \end{bmatrix} \begin{bmatrix} A \\ B \\ C \\ D \\ E \\ F \\ G \\ H \\ I \\ J \end{bmatrix} = \begin{bmatrix} 0 \\ 0 \\ \dots \\ {n}^1_x \\ {n}^1_y \\ {n}^1_z \\ {n}^2_x \\ {n}^2_y \\ {n}^2_z \\ \dots \end{bmatrix}$

Alles in allem führt das Lösen dieses Gleichungssystems gleichzeitig dazu, dass das Quadrat auf die Punktwolke fällt, während seine Gradienten in Richtung der Normalen ausgerichtet werden. Es ist auch möglich, die Beiträge von Punkten und Normalen unterschiedlich abzuwägen. In bestimmten Fällen reicht eine geringfügige Neugestaltung von die auf das gewünschte Grundelement zugeschnitten ist, um eine typspezifische Anpassung zu erhalten . Für all diese Details sowie einige theoretische Analysen und Pseudocodes verweise ich Sie auf die oben genannten Veröffentlichungen. $\mathbf{A}$

Tolga Birdal
quelle

Das ist toll! Wie würde man A modifizieren, um die relativen Beiträge von Punkten und Normalen unterschiedlich zu gewichten?

Museful

Multiplizieren Sie einfach die ersten Zeilen, die die Punktgleichungen sind, mit dem gewünschten Gewicht. Um die den Normalen entsprechenden Zeilen zu skalieren, müsste optional auch die rechte Seite der Gleichung skaliert werden: .

n

$\mathbf{n}$

Tolga Birdal

Vielen Dank. Sollte das Transponierungssymbol in der letzten Gleichung nicht aus q und n entfernt werden?

Museful

Danke noch einmal. Entfernte sie.

Tolga Birdal

Ich kenne ein Beispiel, bei dem die Normalen in das Anpassungsverfahren einbezogen wurden. Es ist jedoch keine direkte quadratische Anpassung. Ein lokal parametrisiertes Patch wird an die Punkte und Normalen angepasst. Die Verwendung von Normalen ergibt mehr Gleichungen im Anpassungsproblem, wodurch Polynome höherer Ordnung verwendet werden können.

Ein neuartiger Algorithmus kubischer Ordnung zur Approximation von Hauptrichtungsvektoren

Abhilash Reddy M.
quelle

Siehe auch dieses Papier

Hermite-Interpolation impliziter Oberflächen mit radialen Basisfunktionen

und ist Erweiterung

Hermite Radial Basis Funktionen Implicits

lhf
quelle