Ajustando superfícies implícitas a conjuntos de pontos orientados

Eu tenho uma pergunta sobre o ajuste quadrático de um conjunto de pontos e normais correspondentes (ou equivalentes, tangentes). Ajustar superfícies quadráticas para apontar dados é bem explorado. Alguns trabalhos são os seguintes:

Montagem direta com restrição de tipo de superfícies quadráticas , James Andrews, Carlo H. Sequin Design e aplicações auxiliados por computador, 10 (a), 2013, bbb-ccc
Adaptação algébrica de superfícies quadráticas aos dados , I. Al-Subaihi e GA Watson , Universidade de Dundee

O ajuste aos contornos projetivos também é coberto por alguns trabalhos, como este .

De todos esses trabalhos, acho que o método de Taubin para o ajuste Quadric é bastante popular:

G. Taubin, "Estimação de curvas planares, superfícies e curvas não planares de espaço definidas por equações implícitas, com aplicações para segmentação de imagens de bordas e faixas ", IEEE Trans. PAMI, vol. 13, 1991, pp 1115-1138.

Deixe-me resumir brevemente. Um quadrático pode ser escrito na forma algébrica: onde é o vetor de coeficiente e são as coordenadas 3D. Qualquer ponto está no quadrático se , onde: $Q$

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$

c

$\mathbf{c}$

x

$\mathbf{x}$

x

$\mathbf{x}$

Q

$Q$

x^{T} Q x = 0

$\mathbf{x}^TQ\mathbf{x}=0$

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 Algébrico Em princípio, gostaríamos de resolver os parâmetros que minimizam a soma das distâncias geométricas ao quadrado entre os pontos e a superfície quadrática. Infelizmente, verifica-se que esse é um problema de otimização não convexo, sem soluções analíticas conhecidas. Em vez disso, uma abordagem padrão é resolver um ajuste algébrico, ou seja, resolver os parâmetros que minimizam: $\mathbf{c}$

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

com onde são os pontos no ponto nuvem e

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$

{x^{i}}

$\{\mathbf{x}^i\}$

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 essa minimização direta produziria a solução trivial com na origem. Esta questão foi estudada extensivamente na literatura. Uma resolução que funcionou bem na prática é o método de Taubin (citado acima), introduzindo a restrição: $\mathbf{c}$

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

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

Isso pode ser resolvido da seguinte maneira: Let: que os subscritos indicam as derivadas. A solução é dada pela decomposição generalizada de Eigen, . O vetor de parâmetro de melhor ajuste é igual ao vetor próprio correspondente ao menor valor próprio.

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$

Pergunta principal Em muitos aplicativos, as normais da nuvem de pontos estão disponíveis (ou computadas). As normais do quadric também podem ser calculadas diferenciando e normalizando a superfície 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})\|}$ onde

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

No entanto, o método de Taubin utiliza apenas a geometria do ponto, e não o espaço tangente. E eu não conheço muitos métodos, que são adequados para ajustar quadriculos de tal modo que as tangentes do quadric também coincidam com as da nuvem de pontos subjacente. Estou procurando possíveis extensões do método acima, ou qualquer outro para cobrir esses derivativos de primeira ordem.

O que eu gostaria de alcançar talvez seja abordado parcialmente em espaços dimensionais inferiores, com tipos de superfície (curva) mais primitivos. Por exemplo, o ajuste de linhas nas bordas da imagem, levando em consideração as informações de gradiente, é abordado aqui . A montagem de planos (um tipo simples de quadriculado) em nuvens 3D é muito comum ( link 1 ) ou esferas ou cilindros adequados podem ser ajustados a conjuntos de pontos orientados ( link 2 ). Então, o que eu quero saber é algo semelhante, mas o primitivo ajustado é um quadriculado.

Eu também gostaria de receber a análise do método proposto, como:

Qual é o número mínimo de pontos orientados necessários?
Quais são os casos degenerados?
Pode-se dizer algo sobre robustez?

Atualização : eu gostaria de apresentar uma direção a seguir. Formalmente, o que desejo alcançar:

‖ \nabla f - n ‖ = 0

$\| \nabla f - \mathbf{n} \| = 0$ no ponto . Talvez seja possível fundi-lo com o método de Taubin para criar uma restrição adicional e minimizar o uso de multiplicadores Lagrange?

x

$\mathbf{x}$

computational-geometry regression geometry curve-fitting Tolga Birdal
fonte

Muitos dos elementos de Q não estão mal posicionados em Q?

Museful

Você está certo, e eu já corrigi isso.

Tolga Birdal

Respostas:

Fiquei surpreso por não receber uma resposta satisfatória à pergunta acima e minhas investigações me mostraram que essa é realmente uma área inexplorada. Por isso, esforcei-me por desenvolver soluções para esse problema e publiquei os seguintes manuscritos:

T. Birdal, B. Busam, N. Navab, S. Ilic e P. Sturm. "Uma abordagem minimalista da detecção agnóstica de quadríceps em nuvens de pontos". Anais da Conferência IEEE sobre Visão Computacional e Reconhecimento de Padrões. 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 e P. Sturm, "Detecção primitiva genérica em nuvens de pontos usando novos ajustes quadráticos mínimos", em transações IEEE sobre análise de padrões e inteligência de máquina. https://arxiv.org/abs/1901.01255

Vou tocar brevemente a idéia principal aqui:

Essa abordagem é semelhante ao encaixe gradiente um ( ). Alinhamos o vetor gradiente do quadriculado com o normal da nuvem de pontos . No entanto, diferentemente de fit, optamos por usar uma restrição linear para aumentar a classificação, em vez de regularizar a solução. Isso aparentemente não é trivial, pois o alinhamento vetor-vetor traz uma restrição não linear, seja da forma: $\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}$ A não linearidade é causada pela normalização, pois é difícil conhecer antecipadamente a magnitude e, portanto, a escala homogênea. Resolvemos esse problema introduzindo uma escala homogênea normal entre as incógnitas e escrevemos: onde Empilhar isso para todos os pontos e normais leva a um sistema no formato :

α_{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 {equação} em que , é um

\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$ vetor de coluna de zeros, é e são as escalas homogêneas desconhecidas.

A^{'}

$\mathbf{A}^\prime$

4 N \times (N + 10)

$4N\times(N+10)$

α = {α_{i}}

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

Enquanto a solução desta formulação, situada no espaço nulo de produz resultados aceitáveis, o sistema não tem restrições quanto ao que poderia fazer (os fatores de escala são muito livres). É melhor encontrar um regularizador apropriado que também não seja muito complicado de implementar. Na prática, mais uma vez análogo ao ajuste de gradiente um, poderíamos preferir gradientes polinomiais de norma de unidade e, portanto, podemos escrever ou equivalentemente , um fator de escala comum. Essa restrição suave $\mathbf{A}^{\prime}$ $\alpha_i=1$ $\alpha_i \gets \bar{\alpha}$ tentará forçar o conjunto zero do polinômio a respeitar a continuidade local dos dados. Essa regularização também nos impede de resolver o sistema homogêneo sensível e permite reescrever o sistema de forma mais 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}$

Em suma, a solução desse sistema de equações guiará simultaneamente o quadriculado a ser incidente na nuvem de pontos, alinhando seus gradientes com os normais. Também é possível ponderar as contribuições de pontos e normais de maneira diferente. Em certos casos, para obter um ajuste específico do tipo, basta uma pequena reformulação de adaptada às primitivas desejadas. Para todos esses detalhes, bem como algumas análises teóricas e pseudocódigo, refiro-lhe as publicações mencionadas acima. $\mathbf{A}$

Tolga Birdal
fonte

Isso é ótimo! Como alguém modifica A para ponderar as contribuições relativas de pontos e normais de maneira diferente?

Museful

Apenas multiplique as primeiras linhas que são as equações de ponto, com o peso desejado. Opcionalmente, para dimensionar as linhas correspondentes às normais, também é necessário dimensionar o lado direito da equação: .

n

$\mathbf{n}$

Tolga Birdal

Obrigado. O símbolo de transposição não deve ser removido de q e n na última equação?

28519 Museful

Obrigado novamente. Removido eles.

precisa

Conheço um exemplo em que os normais foram incluídos no procedimento de ajuste. No entanto, não é um encaixe quadrático direto. Um patch parametrizado localmente é ajustado aos pontos e às normais. O uso de normais fornece mais equações no problema de ajuste, permitindo que polinômios de ordem superior sejam usados.

Um novo algoritmo de ordem cúbica para aproximar vetores de direção principais

Abhilash Reddy M
fonte

Veja também este artigo

Interpolação Hermite de Superfícies Implícitas com Funções de Base Radial

e extensão ist

Funções da base radial da Hermite Implícitas

lhf
fonte