Dopasowywanie powierzchni niejawnych do zestawów punktów zorientowanych

Mam pytanie dotyczące dopasowania kwadratowego do zbioru punktów i odpowiadających normalnych (lub równoważnie stycznych). Dopasowanie kwadratowych powierzchni do danych punktowych jest dobrze zbadane. Niektóre prace są następujące:

Bezpośrednie dopasowanie powierzchni kwadratowych o ograniczonym typie , James Andrews, Carlo H. Sequin Komputerowe projektowanie i zastosowania, 10 (a), 2013, bbb-ccc
Algebraiczne dopasowanie kwadratowych powierzchni do danych , I. Al-Subaihi i GA Watson , University of Dundee

Dopasowywanie do konturów rzutowych jest również objęte niektórymi pracami, takimi jak ten .

Z tych wszystkich prac uważam, że metoda Taubina do dopasowania Quadric jest dość popularna:

G. Taubin, „Oszacowanie krzywych planarnych, powierzchni i krzywych przestrzeni nieplanarnej określonych przez niejawne równania, z zastosowaniem do segmentacji obrazu krawędzi i zakresu ”, IEEE Trans. PAMI, t. 13, 1991, str. 1115-1138.

Pozwól, że krótko podsumuję. Quadric można zapisać w formie algebraicznej: gdzie to wektor współczynnika, a to współrzędne 3D. Dowolny punkt leży na kwadracie jeśli , gdzie: $Q$

fa (do, x) = ZA x^{2)} + b y^{2)} + do z^{2)} + 2) re x y + 2) mi x z + 2) fa y z + 2) sol x + 2) H. y + 2) ja z + jot

$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} ZA & re & mi & sol \\ re & b & fa & H. \\ mi & fa & do & ja \\ sol & H. & ja & jot \end{matrix}]

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

Dopasowanie algebraiczne Zasadniczo chcielibyśmy rozwiązać parametry, które minimalizują sumę kwadratowych odległości geometrycznych między punktami a kwadratową powierzchnią. Niestety okazuje się, że jest to niewypukły problem optymalizacji bez znanych rozwiązań analitycznych. Zamiast tego standardowym podejściem jest rozwiązanie algebraicznego dopasowania, czyli rozwiązanie dla parametrów które minimalizują: $\mathbf{c}$

\sum_{ja = 1}^{n} fa (do, x^{ja})^{2)} = {do}^{T.} M. do

$\sum\limits_{i=1}^{n} f(\mathbf{c},\mathbf{x}^i)^2 = \mathbf{c}^T M \mathbf{c}$ z gdzie to punkty w punkcie chmura i

M. = \sum_{ja = 1}^{n} l (x^{ja}) l (x^{ja})^{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$

Zauważ, że taka bezpośrednia minimalizacja dałaby trywialne rozwiązanie z na początku. To pytanie zostało szeroko zbadane w literaturze. Jednym z rozwiązań, które okazało się dobrze sprawdzać w praktyce, jest metoda Taubina (cytowana powyżej), wprowadzająca ograniczenie: $\mathbf{c}$

‖ \nabla_{x} fa (do, x^{ja}) ‖^{2)} = 1

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

Można to rozwiązać w następujący sposób: Niech: gdzie indeksy dolne oznaczają pochodne. Rozwiązaniem jest uogólniony rozkład Eigen, . Wektor parametru najlepszego dopasowania jest równy wektorowi własnemu odpowiadającemu najmniejszej wartości własnej.

N. = \sum_{ja = 1}^{n} l_{x} (x^{ja}) l_{x} (x^{ja})^{T.} + l_{y} (x^{ja}) l_{y} (x^{ja})^{T.} + l_{z} (x^{ja}) l_{z} (x^{ja})^{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$

Główne pytanie W wielu aplikacjach normalne chmury punktów są dostępne (lub obliczone). Normalne kwadratu można również obliczyć, różnicując i normalizując ukrytą powierzchnię: $\mathbf{N}(x)$

N. (x) = \frac{\nabla fa (do, x)}{‖ \nabla fa (do, x) ‖}

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

gdzie

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

Jednak metoda Taubina wykorzystuje tylko geometrię punktową, a nie przestrzeń styczną. I nie znam wielu metod, które są odpowiednie do dopasowania kwadratów, tak aby styczne kwadratu również pasowały do stycznych podstawowej chmury punktów. Poszukuję potencjalnych rozszerzeń powyższej metody lub innych na pokrycie pochodnych pierwszego rzędu.

To, co chciałbym osiągnąć, może być częściowo rozwiązane w przestrzeniach o niższych wymiarach, z bardziej prymitywnymi typami powierzchni (krzywych). Na przykład, dopasowanie linii do krawędzi obrazu, z uwzględnieniem informacji o gradiencie, jest tutaj omówione . Dopasowywanie płaszczyzn (prosty typ kwadratu) do chmur 3D jest bardzo powszechne ( łącze 1 ) lub dopasowanie kulek lub cylindrów można dopasować do zorientowanych zestawów punktów ( łącze 2 ). Zastanawiam się więc nad czymś podobnym, ale dopasowany prymityw jest kwadratowy.

Z zadowoleniem przyjąłbym również analizę proponowanej metody, taką jak:

Jaka jest minimalna wymagana liczba zorientowanych punktów?
Jakie są przypadki zdegenerowane?
Czy można coś powiedzieć o solidności?

Aktualizacja : Chciałbym przedstawić kierunek do naśladowania. Formalnie to, co chcę osiągnąć:

‖ \nabla f - n ‖ = 0

$\| \nabla f - \mathbf{n} \| = 0$ w punkcie . Może uda się połączyć to z metodą Taubina, aby uzyskać dodatkowe ograniczenie i zminimalizować użycie mnożników Lagrange'a?

x

$\mathbf{x}$

computational-geometry regression geometry curve-fitting Tolga Birdal
źródło

Czy wiele elementów Q nie jest źle pozycjonowanych w Q?

Museful

Masz rację, a ja to naprawiłem.

Tolga Birdal

Odpowiedzi:

Byłem zaskoczony, że nie otrzymałem satysfakcjonującej odpowiedzi na powyższe pytanie, a moje badania wykazały, że jest to niezbadany obszar. Dlatego włożyłem trochę wysiłku w opracowanie rozwiązań tego problemu i opublikowałem następujące manuskrypty:

T. Birdal, B. Busam, N. Navab, S. Ilic i P. Sturm. „Minimalistyczne podejście do agnostycznego wykrywania kwadratów w chmurach punktów”. Materiały z konferencji IEEE nt. Wizji komputerowej i rozpoznawania wzorców. 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 i P. Sturm, „Ogólne wykrywanie prymitywów w chmurach punktów przy użyciu nowatorskich minimalnych dopasowań czterokwadratowych” w Transakcji IEEE dotyczących analizy wzorców i inteligencji maszynowej. https://arxiv.org/abs/1901.01255

Tutaj krótko dotknę głównego pomysłu:

To podejście jest podobne do dopasowania w gradiencie jeden ( ). Wektor gradientowy kwadratu do normalnej chmury punktów . Jednak, w przeciwieństwie do -fits, wybieramy ograniczenie liniowe w celu zwiększenia rangi zamiast regulowania rozwiązania. Z pozoru nie jest to trywialne, ponieważ wyrównanie wektor-wektor wprowadza ograniczenie nieliniowe o dowolnej postaci: $\nabla 1$ $\nabla \mathbf{Q}(\mathbf{x}_i)$ $\mathbf{n}_i \in \mathbb{R}^3$ $\nabla 1$

\begin{aligned} \frac{\nabla Q (x_{ja})}{‖ \nabla Q (x_{ja}) ‖} - n_{ja} = 0 lub \frac{\nabla Q (x_{ja})}{‖ \nabla Q (x_{ja}) ‖} \cdot n_{ja} = 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}$ Nieliniowość jest spowodowana normalizacją, ponieważ trudno jest z góry ustalić wielkość, a tym samym jednorodną skalę. Rozwiązujemy ten problem, wprowadzając normalną jednorodną skalę wśród nieznanych i piszemy: gdzie Zestawienie tego dla wszystkich punktów i normals prowadzi do systemu o postaci :

α_{i}

$\alpha_i$

\begin{aligned} \nabla Q (x_{ja}) = \nabla v_{ja}^{T.} q = α_{ja} n_{ja} \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} ZA \\ b \\ ⋮ \\ ja \\ jot \\ α_{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} gdzie , to

\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$ wektor zerowy kolumn, to a to nieznane skale jednorodne.

A^{'}

$\mathbf{A}^\prime$

4 N \times (N + 10)

$4N\times(N+10)$

α = {α_{i}}

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

Podczas gdy rozwiązanie tego sformułowania leżące w pustej przestrzeni daje akceptowalne wyniki, system jest dość ograniczony w tym, co mógłby zrobić (współczynniki skali są zbyt wolne). Lepiej jest znaleźć odpowiedni regulizator, który również nie jest zbyt skomplikowany do wdrożenia. W praktyce, po raz kolejny analogiczny do dopasowania gradient-jeden, moglibyśmy preferować gradienty wielomianowe według normy jednostkowej, a zatem zapisać lub równoważnie , jeden wspólny współczynnik skali. To miękkie ograniczenie $\mathbf{A}^{\prime}$ $\alpha_i=1$ $\alpha_i \gets \bar{\alpha}$ spróbuje wymusić zerowy zbiór wielomianu z uwzględnieniem lokalnej ciągłości danych. Taka regularyzacja oszczędza nam również rozwiązywania wrażliwego jednorodnego systemu i pozwala nam ponownie napisać system w bardziej zwartej formie : $\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} ZA \\ b \\ do \\ re \\ mi \\ fa \\ sol \\ H. \\ ja \\ jot \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}$

Podsumowując, rozwiązanie tego układu równań będzie jednocześnie prowadziło kwadrat do incydentu z chmurą punktów, jednocześnie wyrównując jej gradienty do normalnych. Możliwe jest także inne ważenie wkładu punktów i normalnych. W niektórych przypadkach, aby uzyskać dopasowanie specyficzne dla typu, wystarczy niewielkie przeprojektowanie dostosowanego do pożądanego elementu pierwotnego. Wszystkie te szczegóły, a także niektóre analizy teoretyczne i pseudokod, odsyłam do wyżej wymienionych publikacji. $\mathbf{A}$

Tolga Birdal
źródło

To jest świetne! Jak zmodyfikować A, aby inaczej przypisać względny udział punktów i normalnych?

Museful

Wystarczy pomnożyć pierwsze rzędy, które są równaniami punktowymi, o pożądanej masie. Opcjonalnie, aby przeskalować rzędy odpowiadające normalnym, należałoby również przeskalować prawą stronę równania: .

n

$\mathbf{n}$

Tolga Birdal

Dzięki. Czy symbol transpozycji nie powinien zostać usunięty z q i n w ostatnim równaniu?

Museful

Dzięki jeszcze raz. Usunąłem je.

Tolga Birdal

Znam jeden przykład, w którym normalne zostały uwzględnione w procedurze dopasowania. Nie jest to jednak bezpośrednie dopasowanie do kwadratu. Lokalnie parametryzowana łatka jest dopasowana do punktów i normałów. Użycie normalnych daje więcej równań w problemie dopasowania, umożliwiając użycie wielomianów wyższego rzędu.

Nowatorski algorytm rzędu sześciennego do aproksymacji głównych wektorów kierunkowych

Abhilash Reddy M.
źródło

Zobacz także ten artykuł

Hermityczna interpolacja niejawnych powierzchni z funkcjami radialnej podstawy

i istnieje rozszerzenie

Hermite Radialne funkcje podstawowe Implikacje

lhf
źródło