Ajuste de superficies implícitas a conjuntos de puntos orientados

Tengo una pregunta sobre el ajuste cuadrático de un conjunto de puntos y las normales correspondientes (o, de forma equivalente, tangentes). La exploración de las superficies cuadráticas para señalar datos está bien explorada. Algunos trabajos son los siguientes:

Adaptación directa con restricciones de tipo de superficies cuadráticas , James Andrews, Diseño y aplicaciones asistidas por computadora Carlo H. Sequin , 10 (a), 2013, bbb-ccc
Adaptación algebraica de superficies cuadráticas a datos , I. Al-Subaihi y GA Watson , Universidad de Dundee

La adaptación a contornos proyectivos también está cubierta por algunos trabajos, como este .

De todos estos trabajos, creo que el método de Taubin para la adaptación cuadrática es bastante popular:

G. Taubin, "Estimación de curvas planas, superficies y curvas espaciales no planas definidas por ecuaciones implícitas, con aplicaciones a la segmentación de imagen de borde y rango ", IEEE Trans. PAMI, vol. 13, 1991, pp1115-1138.

Déjame resumir brevemente. Una $Q$ cuadrática se puede escribir en forma algebraica:

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

c

$\mathbf{c}$ es el vector coeficiente y

x

$\mathbf{x}$ son las coordenadas 3D. Cualquier punto

x

$\mathbf{x}$ encuentra en el cuadrático

Q

$Q$ si

x^{T} Q x = 0

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

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

Ajuste algebraico En principio, nos gustaría resolver los parámetros que minimizan la suma de las distancias geométricas cuadradas entre los puntos y la superficie cuadrática. Desafortunadamente, resulta que este es un problema de optimización no convexo sin soluciones analíticas conocidas. En cambio, un enfoque estándar es resolver un ajuste algebraico, es decir, resolver los parámetros $\mathbf{c}$ que minimizan:

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

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

{x^{i}}

$\{\mathbf{x}^i\}$ son los puntos en la nube de puntos y

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$

Observe que tal minimización directa produciría la solución trivial con $\mathbf{c}$ en el origen. Esta pregunta ha sido estudiada ampliamente en la literatura. Una resolución que funciona bien en la práctica es el método de Taubin (citado anteriormente), que introduce la restricción:

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

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

Esto se puede resolver de la siguiente manera: Sea: donde los subíndices denotan las derivadas. La solución viene dada por la descomposición generalizada de Eigen, . El vector de parámetro de mejor ajuste es igual al vector propio correspondiente al valor propio más pequeño.

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$

Pregunta principal En muchas aplicaciones, las normales de la nube de puntos están disponibles (o calculadas). Las normales del quadric también se pueden calcular diferenciando y normalizando la superficie implícita: $\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})\|}$ where

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

Sin embargo, el método de Taubin utiliza solo la geometría del punto, y no el espacio tangente. Y no conozco muchos métodos, que son adecuados para ajustar cuádricos de modo que las tangentes del cuadrático también coincidan con las tangentes de la nube de puntos subyacente. Estoy buscando posibles extensiones del método anterior, o cualquier otra para cubrir estos derivados de primer orden.

Lo que me gustaría lograr quizás se aborde parcialmente en espacios de dimensiones inferiores, con tipos de superficie (curva) más primitivos. Por ejemplo, ajustando líneas a los bordes de la imagen, teniendo en cuenta la información del gradiente, aquí se trata . El ajuste de planos (un tipo simple de cuadrático) a nubes 3D es muy común ( enlace 1 ) o las esferas o cilindros de ajuste se pueden ajustar a conjuntos de puntos orientados ( enlace 2 ). Entonces, lo que me pregunto es algo similar, pero la primitiva ajustada es un cuádruple.

También agradecería el análisis del método propuesto, como por ejemplo:

¿Cuál es el número mínimo de puntos orientados requeridos?
¿Cuáles son los casos degenerados?
¿Se puede decir algo sobre la robustez?

Actualización : me gustaría presentar una dirección a seguir. Formalmente, lo que deseo lograr:

‖ \nabla f - n ‖ = 0

$\| \nabla f - \mathbf{n} \| = 0$ en el punto . ¿Tal vez sea posible fusionarlo con el método de Taubin para crear una restricción adicional y minimizar el uso de multiplicadores de Lagrange?

x

$\mathbf{x}$

computational-geometry regression geometry curve-fitting Tolga Birdal
fuente

¿No están mal posicionados muchos de los elementos de Q en Q?

Museful

Tienes razón, y ahora he arreglado esto.

Tolga Birdal

Respuestas:

Me sorprendió no haber recibido una respuesta satisfactoria a la pregunta anterior y mis investigaciones me mostraron que esto, de hecho, es un área inexplorada. Por lo tanto, puse un esfuerzo en desarrollar soluciones a este problema y publiqué los siguientes manuscritos:

T. Birdal, B. Busam, N. Navab, S. Ilic y P. Sturm. "Un enfoque minimalista para la detección agnóstica de tipos de cuádricos en nubes de puntos". Actas de la Conferencia IEEE sobre visión por computadora y reconocimiento de patrones. 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 y P. Sturm, "Detección primitiva genérica en nubes de puntos utilizando ajustes cuádruples mínimos novedosos", en Transacciones IEEE sobre análisis de patrones e inteligencia artificial. https://arxiv.org/abs/1901.01255

Tocaré brevemente la idea principal aquí:

Este enfoque es similar al ajuste de gradiente uno ( ). Alineamos el vector gradiente del cuadrático con la normalidad de la nube de puntos . Sin embargo, a diferencia de -fits, optamos por usar una restricción lineal para aumentar el rango en lugar de regularizar la solución. Esto aparentemente no es trivial ya que la alineación vector-vector trae una restricción no lineal de cualquiera de las formas: $\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 no linealidad es causada por la normalización, ya que es difícil conocer la magnitud y, por lo tanto, la escala homogénea de antemano. Resolvemos este problema introduciendo una escala homogénea normal entre las incógnitas y escribimos: donde Apilando esto para todos los puntos y normales conduce a un sistema de la forma :

α_{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 {ecuación} donde , es 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$ vector de columna de ceros, es y son las escalas homogéneas desconocidas.

A^{'}

$\mathbf{A}^\prime$

4 N \times (N + 10)

$4N\times(N+10)$

α = {α_{i}}

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

Si bien la solución de esta formulación que se encuentra en el espacio nulo de produce resultados aceptables, el sistema no tiene restricciones en cuanto a lo que podría hacer (los factores de escala son demasiado libres). Es mejor encontrar un regularizador apropiado que tampoco sea demasiado complicado de implementar. En la práctica, una vez más análogo al ajuste de gradiente uno, podríamos preferir gradientes polinómicos de norma unitaria y, por lo tanto, podemos escribir o equivalentemente , un factor de escala común. Esta restricción suave $\mathbf{A}^{\prime}$ $\alpha_i=1$ $\alpha_i \gets \bar{\alpha}$ intentará forzar un conjunto cero del polinomio respetando la continuidad local de los datos. Dicha regularización también nos salva de resolver el sistema homogéneo sensible y nos permite volver a escribir el sistema en una forma más compacta : $\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}$

En general, la resolución de este sistema de ecuaciones guiará simultáneamente el cuadrático para que incida en la nube de puntos mientras alinea sus gradientes hacia las normales. También es posible sopesar las contribuciones de puntos y normales de manera diferente. En ciertos casos, para obtener un ajuste de tipo específico, basta un rediseño menor de adaptado a las primitivas deseadas. Para todos estos detalles, así como algunos análisis teóricos y pseudocódigo, los remito a las publicaciones antes mencionadas. $\mathbf{A}$

Tolga Birdal
fuente

¡Esto es genial! ¿Cómo se modificaría A para ponderar las contribuciones relativas de puntos y normales de manera diferente?

Museful

Simplemente multiplique las primeras filas que son las ecuaciones de puntos, con el peso deseado. Opcionalmente, para escalar las filas correspondientes a las normales, también sería necesario escalar el lado derecho de la ecuación: .

n

$\mathbf{n}$

Tolga Birdal

Gracias. ¿No debería eliminarse el símbolo de transposición de q y n en la última ecuación?

Museful

Gracias de nuevo. Los quitó.

Tolga Birdal

Sé de un ejemplo donde las normales se han incluido en el procedimiento de ajuste. Sin embargo, no es un ajuste cuádrico directo. Se ajusta un parche parametrizado localmente a los puntos y normales. El uso de normales da más ecuaciones en el problema de ajuste, lo que permite utilizar polinomios de orden superior.

Un nuevo algoritmo de orden cúbico para aproximar vectores de dirección principal

Abhilash Reddy M
fuente

Ver también este documento

Interpolación Hermite de Superficies Implícitas con Funciones de Base Radial

y su extensión

Hermite Funciones de la base radial Implicitos

lhf
fuente