Dopasowywanie powierzchni niejawnych do zestawów punktów zorientowanych


13

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:

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:

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)=ZAx2)+by2)+doz2)+2)rexy+2)mixz+2)fayz+2)solx+2)H.y+2)jaz+jot
doxxQxT.Qx=0
Q=[ZAremisolrebfaH.mifadojasolH.jajot]

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ą:do

ja=1nfa(do,xja)2)=doT.M.do
z gdzie to punkty w punkcie chmura i
M.=ja=1nl(xja)l(xja)T.
{xja}
l=[x2),y2),z2),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:do

xfa(do,xja)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.=ja=1nlx(xja)lx(xja)T.+ly(xja)ly(xja)T.+lz(xja)lz(xja)T.
(M.-λN.)do=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ę:N.(x)

N.(x)=fa(do,x)fa(do,x)
f(c,x)=2[ A x + D y + F z + G B y + D x + E z + H C z + E y + F x + I ] gdzie
f(c,x)=2[Ax+Dy+Fz+GBy+Dx+Ez+HCz+Ey+Fx+I]

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ąć:

fn=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


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

Masz rację, a ja to naprawiłem.
Tolga Birdal

Odpowiedzi:


5

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: 1Q(xja)njaR3)1

Q(xja)Q(xja)-nja=0lubQ(xja)Q(xja)nja=1.
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 : αja
Q(xja)=vjaT.q=αjanja
v=[x2)y2)z2)2)xy2)xz2)yz2)x2)y2)z1]T.
N.xjanjaZAq=0
[v1T.000v2)T.000vnT.000v1T.-n103)03)v2)T.03)-n2)03)vnT.03)03)-nn][ZAbjajotα1α2)αn]=0
- \ 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 , tovjaT.=v(xja)T.R3)×1003)3)×1 wektor zerowy kolumn, to a to nieznane skale jednorodne.ZA4N.×(N.+10)α={αja}

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 ograniczenieZAαja=1αjaα¯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 :ZAq=n

[x12)y12)z12)2)x1y12)x1z12)y1z12)x12)y12)z11x2)2)y2)2)z2)2)2)x2)y2)2)x2)z2)2)y2)z2)2)x2)2)y2)2)z2)12)x1002)y12)z102)00002)y102)x102)z102)00002)z102)x12)y1002)02)x2)002)y2)2)z2)02)00002)y2)02)x2)02)z2)02)00002)z2)02)x2)2)y2)002)0][ZAbdoremifasolH.jajot]=[00nx1ny1nz1nx2)ny2)nz2)]

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.ZA


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


Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.