Ajustement de surfaces implicites à des ensembles de points orientés

J'ai une question concernant l'ajustement quadrique à un ensemble de points et de normales correspondantes (ou de manière équivalente, des tangentes). L'ajustement de surfaces quadriques à des données ponctuelles est bien exploré. Certains travaux sont les suivants:

Ajustement direct contraint par type de surfaces quadriques , James Andrews, Carlo H. Sequin Conception et applications assistées par ordinateur, 10 (a), 2013, bbb-ccc
Ajustement algébrique des surfaces quadriques aux données , I. Al-Subaihi et GA Watson , Université de Dundee

L'adaptation aux contours projectifs est également couverte par certaines œuvres, comme celle-ci .

De tous ces travaux, je pense que la méthode de Taubin pour l'ajustement quadrique est assez populaire:

G. Taubin, «Estimation des courbes planes, des surfaces et des courbes d'espace non planaires définies par des équations implicites, avec des applications à la segmentation des images de bord et de plage », IEEE Trans. PAMI, vol. 13, 1991, pp1115-1138.

Permettez-moi de résumer brièvement. Un $Q$ quadrique peut s'écrire sous la forme algébrique:

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$ où

c

$\mathbf{c}$ est le vecteur de coefficient et

x

$\mathbf{x}$ sont les coordonnées 3D. Tout point

x

$\mathbf{x}$ se trouve sur la quadrique

Q

$Q$ si

x^{T} Q x = 0

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

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}$

Ajustement algébrique En principe, nous aimerions résoudre les paramètres qui minimisent la somme des distances géométriques au carré entre les points et la surface quadratique. Malheureusement, il s'avère qu'il s'agit d'un problème d'optimisation non convexe sans solutions analytiques connues. Au lieu de cela, une approche standard consiste à résoudre un ajustement algébrique, c'est-à-dire à résoudre les paramètres $\mathbf{c}$ qui minimisent:

\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}$ avec

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$ où

{x^{i}}

$\{\mathbf{x}^i\}$ sont les points du nuage de points et

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$

Notez qu'une telle minimisation directe donnerait la solution triviale avec $\mathbf{c}$ à l'origine. Cette question a été largement étudiée dans la littérature. Une résolution qui s'est avérée bien fonctionner dans la pratique est la méthode de Taubin (citée ci-dessus), introduisant la contrainte:

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

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

Cela peut être résolu comme suit: Soit: où les indices désignent les dérivées. La solution est donnée par la décomposition Eigen généralisée, . Le vecteur de paramètre le mieux adapté est égal au vecteur propre correspondant à la plus petite valeur propre.

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$

Question principale Dans de nombreuses applications, les normales du nuage de points sont disponibles (ou calculées). Les normales de la quadrique peuvent également être calculées en différenciant et en normalisant la surface implicite: $\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})\|}$ où

\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}$

Cependant, la méthode de Taubin utilise uniquement la géométrie du point, et non l'espace tangent. Et je ne connais pas beaucoup de méthodes, qui conviennent pour ajuster des quadriques telles que les tangentes de la quadrique correspondent également aux tangentes du nuage de points sous-jacent. Je recherche des extensions potentielles de la méthode ci-dessus, ou de toute autre pour couvrir ces dérivés de premier ordre.

Ce que je voudrais réaliser est peut-être adressé en partie dans des espaces de dimension inférieure, avec des types de surface (courbe) plus primitifs. Par exemple, l'ajustement des lignes aux bords de l'image, en tenant compte des informations sur le gradient, est couvert ici . Il est très courant d' ajuster des plans (un simple type quadrique) à des nuages 3D ( lien 1 ) ou des sphères ou des cylindres adaptés à des ensembles de points orientés ( lien 2 ). Je me demande donc quelque chose de similaire, mais la primitive ajustée est une quadrique.

Je saluerais également l'analyse de la méthode proposée telle que:

Quel est le nombre minimum de points orientés requis?
Quels sont les cas dégénérés?
Peut-on dire quelque chose sur la robustesse?

Mise à jour : je voudrais présenter une direction à suivre. Formellement, ce que je souhaite atteindre:

‖ \nabla f - n ‖ = 0

$\| \nabla f - \mathbf{n} \| = 0$ au point . Peut-être qu'il serait possible de le fusionner avec la méthode de Taubin pour trouver une contrainte supplémentaire et minimiser l'utilisation des multiplicateurs de Lagrange?

x

$\mathbf{x}$

computational-geometry regression geometry curve-fitting Tolga Birdal
la source

De nombreux éléments de Q ne sont-ils pas mal positionnés dans Q?

Museful

Vous avez raison, et j'ai maintenant corrigé cela.

Tolga Birdal

Réponses:

J'ai été surpris de ne pas avoir reçu de réponse satisfaisante à la question ci-dessus et mes investigations m'ont montré qu'il s'agit effectivement d'un domaine inexploré. Par conséquent, j'ai mis un certain effort dans le développement de solutions à ce problème et j'ai publié les manuscrits suivants:

T. Birdal, B. Busam, N. Navab, S. Ilic et P. Sturm. "Une approche minimaliste de la détection agnostique de type des quadriques dans les nuages de points." Actes de la conférence de l'IEEE sur la vision par ordinateur et la reconnaissance des formes. 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 et P. Sturm, «Generic Primitive Detection in Point Clouds Using Novel Minimal Quadric Fits», dans IEEE Transactions on Pattern Analysis and Machine Intelligence. https://arxiv.org/abs/1901.01255

Je toucherai brièvement l'idée principale ici:

Cette approche est similaire à l'ajustement à gradient un ( ). Nous alignons le vecteur de gradient de la quadrique avec la normale du nuage de points . Cependant, contrairement à -fits, nous choisissons d'utiliser une contrainte linéaire pour augmenter le classement plutôt que de régulariser la solution. Ceci est apparemment non trivial car l'alignement vecteur-vecteur apporte une contrainte non linéaire de la forme: $\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}$ La non-linéarité est causée par la normalisation car il est difficile de connaître à l'avance l'amplitude et donc l'échelle homogène. Nous résolvons ce problème en introduisant une échelle homogène normale parmi les inconnues et écrivons: où empilant pour tous les points et les normales conduit à un système de la forme :

α_{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 {equation} où , est un

\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$ vecteur colonne de zéros, vaut et sont les échelles homogènes inconnues.

A^{'}

$\mathbf{A}^\prime$

4 N \times (N + 10)

$4N\times(N+10)$

α = {α_{i}}

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

Alors que la solution de cette formulation située dans l'espace nul de produit des résultats acceptables, le système est assez libre de ce qu'il pourrait faire (les facteurs d'échelle sont trop libres). Il est préférable de trouver un régularisateur approprié qui n'est pas trop compliqué à mettre en œuvre. En pratique, une fois de plus, comme pour l'ajustement à gradient un, nous pourrions préférer les gradients polynomiaux à norme unitaire, et ainsi, nous pouvons écrire ou de manière équivalente , un facteur d'échelle commun. Cette contrainte douce $\mathbf{A}^{\prime}$ $\alpha_i=1$ $\alpha_i \gets \bar{\alpha}$ va essayer de forcer le zéro du polynôme à respecter la continuité locale des données. Une telle régularisation nous évite également de résoudre le système homogène sensible et nous permet de réécrire le système sous une forme plus compacte : $\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}$

Dans l'ensemble, la résolution de ce système d'équations guidera simultanément la quadrique à être incidente au nuage de points tout en alignant ses gradients vers les normales. Il est également possible de peser différemment les contributions des points et des normales. Dans certains cas, pour obtenir un ajustement spécifique au type, une refonte mineure de adaptée à la primitive souhaitée suffit. Pour tous ces détails ainsi que quelques analyses théoriques et pseudo-code, je vous renvoie aux publications précitées. $\mathbf{A}$

Tolga Birdal
la source

C'est bien! Comment modifierait-on A pour pondérer différemment les contributions relatives des points et des normales?

Museful

Multipliez simplement les premières lignes qui sont les équations ponctuelles, avec le poids souhaité. Facultativement, pour mettre à l'échelle les lignes correspondant aux normales, il faudrait également mettre à l'échelle le côté droit de l'équation: .

n

$\mathbf{n}$

Tolga Birdal

Merci. Le symbole de transposition ne devrait-il pas être supprimé de q et n dans la dernière équation?

Museful

Merci encore. Les a supprimés.

Tolga Birdal

Je connais un exemple où les normales ont été incluses dans la procédure d'ajustement. Ce n'est cependant pas un raccord quadrique direct. Un patch paramétré localement est ajusté aux points et aux normales. L'utilisation de normales donne plus d'équations dans le problème d'ajustement, ce qui permet d'utiliser des polynômes d'ordre supérieur.

Un nouvel algorithme d'ordre cubique pour approximer les vecteurs de direction principaux

Abhilash Reddy M
la source

Voir aussi cet article

Interpolation Hermite de surfaces implicites avec fonctions de base radiale

et sa première extension

Les fonctions de la base radiale Hermite impliquent

lhf
la source