Pemasangan Permukaan Implisit ke Set Titik Berorientasi

Saya punya pertanyaan tentang quadric fit untuk satu set poin dan normals yang sesuai (atau setara, tangen). Pemasangan permukaan kuadrat ke titik data dieksplorasi dengan baik. Beberapa karya adalah sebagai berikut:

Pemasangan Langsung Berbatas Type-Quadric , James Andrews, Carlo H. Sequin Desain & Aplikasi Berbantuan Komputer, 10 (a), 2013, bbb-ccc
Pemasangan aljabar permukaan kuadrat ke data , I. Al-Subaihi dan GA Watson , University of Dundee

Menyesuaikan dengan kontur proyektif juga dicakup oleh beberapa karya, seperti yang ini .

Dari semua karya ini, saya pikir metode Taubin untuk pemasangan Quadric cukup populer:

G. Taubin, "Estimasi Kurva Planar, Permukaan dan Kurva Luar Angkasa Nonplanar Didefinisikan oleh Persamaan Tersirat, dengan Aplikasi untuk Segmentasi Tepi dan Rentang Gambar ", IEEE Trans. PAMI, Vol. 13, 1991, pp1115-1138.

Biarkan saya meringkas secara singkat. Kuadrat $Q$ dapat ditulis dalam bentuk aljabar:

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

c

$\mathbf{c}$ adalah vektor koefisien dan

x

$\mathbf{x}$ adalah koordinat 3D. Setiap titik

x

$\mathbf{x}$ terletak pada kuadrat

Q

$Q$ jika

x^{T} Q x = 0

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

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

Aljabar Fit Pada prinsipnya, kami ingin menyelesaikan parameter yang meminimalkan jumlah jarak geometrik kuadrat antara titik dan permukaan kuadratik. Sayangnya, ternyata ini adalah masalah optimisasi non-cembung tanpa solusi analitis yang diketahui. Sebaliknya, pendekatan standar adalah untuk menyelesaikan kecocokan aljabar, yaitu untuk memecahkan parameter $\mathbf{c}$ yang meminimalkan:

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

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

{x^{i}}

$\{\mathbf{x}^i\}$ adalah poin di awan titik dan

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$

Perhatikan bahwa minimalisasi langsung seperti itu akan menghasilkan solusi sepele dengan $\mathbf{c}$ pada titik asal. Pertanyaan ini telah dipelajari secara luas dalam literatur. Salah satu resolusi yang telah terbukti bekerja dengan baik dalam praktik adalah metode Taubin (dikutip di atas), memperkenalkan batasan:

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

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

Ini dapat dipecahkan sebagai berikut: Misalkan: mana subskrip menunjukkan turunan. Solusi diberikan oleh dekomposisi Eigen umum, . Vektor parameter yang paling cocok sama dengan vektor Eigen yang sesuai dengan nilai Eigen terkecil.

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$

Pertanyaan Utama Dalam banyak aplikasi, normals dari point cloud tersedia (atau dihitung). Normal dari quadric juga dapat dihitung dengan membedakan dan menormalkan permukaan implisit: $\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})\|}$ mana

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

Namun, metode Taubin hanya menggunakan titik geometri, dan bukan ruang singgung. Dan saya tidak mengetahui banyak metode, yang cocok untuk pas kuadrat sedemikian rupa sehingga garis singgung kuadrat juga cocok dengan garis singgung awan titik yang mendasarinya. Saya mencari ekstensi potensial dari metode di atas, atau yang lain untuk mencakup turunan orde pertama ini.

Apa yang ingin saya capai mungkin ditangani sebagian dalam ruang dimensi yang lebih rendah, dengan tipe permukaan (kurva) yang lebih primitif. Misalnya, menyesuaikan garis ke tepi gambar, dengan mempertimbangkan informasi gradien dibahas di sini . Pas pesawat (jenis sederhana kuadrat) ke awan 3D sangat umum ( tautan 1 ) atau pas bola atau silinder dapat disesuaikan dengan set titik berorientasi ( tautan 2 ). Jadi yang saya ingin tahu adalah sesuatu yang serupa, tetapi primitif yang dipasang adalah kuadrat.

Saya juga akan menyambut baik analisis metode yang diusulkan seperti:

Berapa jumlah minimum titik orientasi yang diperlukan?
Apa saja kasus yang merosot?
Adakah yang bisa dikatakan tentang ketahanan?

Pembaruan : Saya ingin menyajikan arahan untuk diikuti. Secara formal, apa yang ingin saya capai:

‖ \nabla f - n ‖ = 0

$\| \nabla f - \mathbf{n} \| = 0$ pada titik . Mungkin mungkin untuk menggabungkannya dengan metode Taubin untuk menghasilkan kendala tambahan dan meminimalkan menggunakan pengganda Lagrange?

x

$\mathbf{x}$

computational-geometry regression geometry curve-fitting Tolga Birdal
sumber

Tidak banyak elemen Q yang salah posisikan dalam Q?

Museful

Anda benar, dan saya sekarang sudah memperbaikinya.

Tolga Birdal

Jawaban:

Saya terkejut karena tidak menerima jawaban yang memuaskan untuk pertanyaan di atas dan penyelidikan saya menunjukkan kepada saya bahwa ini memang area yang belum dijelajahi. Oleh karena itu, saya berupaya mengembangkan solusi untuk masalah ini, dan menerbitkan manuskrip berikut:

T. Birdal, B. Busam, N. Navab, S. Ilic dan P. Sturm. "Pendekatan Minimalis untuk Deteksi Quadric Agnostik Tipe di Awan Titik." Prosiding Konferensi IEEE tentang Visi Komputer dan Pengenalan Pola. 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 dan P. Sturm, "Deteksi Primitif Generik di Awan Titik Menggunakan Novel Minimal Quadric Fits," dalam Transaksi IEEE tentang Analisis Pola dan Kecerdasan Mesin. https://arxiv.org/abs/1901.01255

Secara singkat saya akan menyentuh ide utama di sini:

Pendekatan ini mirip dengan pas gradien-satu ( ). Kami menyelaraskan vektor gradien kuadrat dengan normal dari titik cloud . Namun, tidak seperti cocok, kami memilih untuk menggunakan batasan linier untuk meningkatkan peringkat daripada mengatur solusi. Ini tampaknya non-sepele karena penyelarasan vektor-vektor membawa kendala non-linear salah satu dari bentuk: $\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}$ Non-linearitas disebabkan oleh normalisasi karena sulit untuk mengetahui besarnya dan dengan demikian skala homogen di muka. Kami memecahkan masalah ini dengan memperkenalkan skala homogen normal antara yang tidak diketahui dan menulis: mana Menyusun ini untuk semua poin dan normals mengarah ke sistem formulir :

α_{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 {persamaan} di mana , adalah 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$ vektor vektor nol, adalah dan adalah skala homogen yang tidak diketahui.

A^{'}

$\mathbf{A}^\prime$

4 N \times (N + 10)

$4N\times(N+10)$

α = {α_{i}}

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

Sementara solusi dari formulasi ini terletak pada ruang nol dari menghasilkan hasil yang dapat diterima, sistem ini cukup tidak dibatasi dalam apa yang bisa dilakukannya (faktor skala terlalu bebas). Lebih baik untuk menemukan regulator yang tepat yang juga tidak terlalu rumit untuk diterapkan. Dalam praktiknya, sekali lagi analog dengan pas gradien-satu, kita bisa lebih suka gradien polinomial unit-norma, dan dengan demikian, dapat menulis atau ekivalen , satu faktor skala umum. Kendala lembut ini $\mathbf{A}^{\prime}$ $\alpha_i=1$ $\alpha_i \gets \bar{\alpha}$ akan mencoba untuk memaksa set nol polinomial menghormati kesinambungan data lokal. Regulatorisasi seperti itu juga menyelamatkan kita dari penyelesaian sistem homogen yang sensitif, dan memungkinkan kita menulis ulang sistem dalam bentuk yang lebih ringkas : $\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}$

Secara keseluruhan, menyelesaikan sistem persamaan ini secara simultan akan memandu kuadrat untuk menjadi insiden ke awan titik sambil menyelaraskan gradiennya terhadap normals. Dimungkinkan juga untuk menimbang kontribusi poin dan normal secara berbeda. Dalam kasus-kasus tertentu, untuk mendapatkan kecocokan jenis-spesifik, desain ulang minor disesuaikan dengan kecukupan primitif yang diinginkan. Untuk semua perincian ini serta beberapa analisis teoretis dan kode semu, saya merujuk Anda ke publikasi yang disebutkan di atas. $\mathbf{A}$

Tolga Birdal
sumber

Ini bagus! Bagaimana seseorang akan memodifikasi A untuk mempertimbangkan kontribusi relatif dari poin dan normal secara berbeda?

Museful

Cukup gandakan baris pertama yang merupakan titik-persamaan, dengan bobot yang diinginkan. Secara opsional, untuk skala baris yang sesuai dengan normals, kita juga perlu skala sisi kanan persamaan: .

n

$\mathbf{n}$

Tolga Birdal

Terima kasih. Bukankah simbol transpos harus dihapus dari q dan n dalam persamaan terakhir?

Museful

Terima kasih lagi. Dihapus mereka.

Tolga Birdal

Saya tahu satu contoh di mana normals telah dimasukkan dalam prosedur pemasangan. Ini bukan pas quadric langsung sekalipun. Patch yang diparameterisasi secara lokal dipasang ke titik dan normal. Menggunakan norma memberikan lebih banyak persamaan dalam masalah pemasangan, memungkinkan polinomial orde tinggi untuk digunakan.

Algoritma cubic-order novel untuk mendekati vektor arah utama

Abhilash Reddy M
sumber

Lihat juga makalah ini

Interpolasi Hermit pada Permukaan Tersirat dengan Fungsi Radial Basis

dan ekstensi ist

Implikasi Fungsi Dasar Radial Hermit

lhf
sumber