Подгонка неявных поверхностей к ориентированным наборам точек

У меня есть вопрос относительно подгонки квадрики к множеству точек и соответствующих нормалей (или, что эквивалентно, касательных). Подгонка квадратичных поверхностей к точечным данным хорошо изучена. Некоторые работы заключаются в следующем:

Прямая подгонка квадратичных поверхностей по типу , Джеймс Эндрюс, Карло Х. Секвин Компьютерный дизайн и приложения, 10 (a), 2013, bbb-ccc
Алгебраическая подгонка квадратичных поверхностей к данным , И. Аль-Субайхи и Г. А. Уотсон , Университет Данди

Подгонка к проективным контурам также рассматривается в некоторых работах, таких как эта .

Из всех этих работ я думаю, что метод Таубина для подгонки квадрик довольно популярен:

Г. Таубин, "Оценка плоских кривых, поверхностей и неплоских пространственных кривых, определяемых неявными уравнениями, с приложениями к краевой и дистанционной сегментации изображения ", IEEE Trans. PAMI, Vol. 13, 1991, стр.1115-1138.

Позвольте мне кратко подвести итог. Квадрику $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}$

Алгебраическое соответствие В принципе, мы хотели бы найти параметры, которые минимизируют сумму квадратов геометрических расстояний между точками и квадратичной поверхностью. К сожалению, оказывается, что это невыпуклая задача оптимизации без известных аналитических решений. Вместо этого стандартный подход заключается в поиске алгебраического соответствия, то есть в поиске параметров $\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}$ с

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$

Обратите внимание, что такая прямая минимизация даст тривиальное решение с $\mathbf{c}$ в начале координат. Этот вопрос широко изучен в литературе. Одним из решений, которое, как было установлено, хорошо работает на практике, является метод Таубина (приведенный выше), который вводит ограничение:

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

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

Это можно решить следующим образом: Пусть: где индексы обозначают производные. Решение дается обобщенным собственным разложением, . Вектор наиболее подходящего параметра равен собственному вектору, соответствующему наименьшему собственному значению.

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$

Основной вопрос Во многих приложениях нормали облака точек доступны (или вычислены). Нормы квадрики также можно вычислить путем дифференцирования и нормализации неявной поверхности: $\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})\|}$ где

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

Однако метод Таубина использует только точечную геометрию, а не касательное пространство. И я не знаю многих методов, которые подходят для подгонки квадрик таким образом, чтобы касательные квадрики также совпадали с касательными нижележащего облака точек. Я ищу возможные расширения метода выше или любого другого, чтобы покрыть эти производные первого порядка.

То, чего я хотел бы достичь, может быть частично решено в пространствах меньшего размера, с более примитивными типами поверхностей (кривых). Например, подгонка линий к краям изображения с учетом информации о градиенте рассматривается здесь . Подгонка плоскостей (простой тип квадрики) к трехмерным облакам очень распространена ( ссылка 1 ), или подгонка сфер или цилиндров может быть приспособлена к ориентированным наборам точек ( ссылка 2 ). Так что мне интересно что-то похожее, но подобранный примитив - это квадрика.

Я также приветствовал бы анализ предложенного метода, такого как:

Какое минимальное количество ориентированных точек требуется?
Каковы вырожденные случаи?
Что-нибудь можно сказать о надежности?

Обновление : я хотел бы представить направление для подражания. Формально, чего я хочу добиться:

‖ \nabla f - n ‖ = 0

$\| \nabla f - \mathbf{n} \| = 0$ в точке . Может быть, можно было бы объединить его с методом Таубина, чтобы придумать дополнительное ограничение и свести к минимуму использование множителей Лагранжа?

x

$\mathbf{x}$

computational-geometry regression geometry curve-fitting Толга Бердал
источник

Не много ли элементов Q неправильно расположено в Q?

Музейный

Вы правы, и я сейчас исправил это.

Толга Бердал

Ответы:

Я был удивлен, что не получил удовлетворительного ответа на поставленный выше вопрос, и мои исследования показали, что это действительно неисследованная область. Поэтому я приложил некоторые усилия для разработки решений этой проблемы и опубликовал следующие рукописи:

Т. Бирдал, Б. Бусам, Н. Наваб, С. Илич и П. Штурм. «Минималистский подход к типографическому обнаружению квадрик в облаках точек». Материалы конференции IEEE по компьютерному зрению и распознаванию образов. 2018. http://openaccess.thecvf.com/content_cvpr_2018/html/Birdal_A_Minimalist_Approach_CVPR_2018_paper.html

Т. Бирдал, Б. Бусам, Н. Наваб, С. Илич и П. Штурм, «Общее примитивное обнаружение в облаках точек с использованием новых минимальных квадратичных подборок», в транзакциях IEEE по анализу образов и машинному интеллекту. https://arxiv.org/abs/1901.01255

Я кратко коснусь основной идеи здесь:

Этот подход похож на аппроксимацию по градиенту один ( ). Мы выровняем вектор градиента квадрики с нормалью облака точек . Однако, в отличие от -приборов, мы предпочитаем использовать линейное ограничение для увеличения ранга, а не для регуляризации решения. Это, по-видимому, нетривиально, поскольку выравнивание вектор-вектор приводит к нелинейному ограничению любого вида: $\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}$ Нелинейность вызвана нормализацией, поскольку трудно заранее определить величину и, следовательно, однородную шкалу. Мы решаем эту проблему, вводя обычную однородную шкалу среди неизвестных и пишем: где Собираем это для всех точек и нормалей чтобы получить систему вида :

α_{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 {уравнение} где , является

\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$ вектор-столбец нулей, равен и - неизвестные однородные шкалы.

A^{'}

$\mathbf{A}^\prime$

4 N \times (N + 10)

$4N\times(N+10)$

α = {α_{i}}

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

Хотя решение этой формулировки, лежащее в пустом пространстве дает приемлемые результаты, система совершенно не стеснена в своих действиях (масштабные коэффициенты слишком свободны). Лучше найти подходящий регуляризатор, который также не слишком сложен для реализации. На практике, снова аналогично аппроксимации градиентом один, мы могли бы предпочесть полиномиальные градиенты единичной нормы, и, таким образом, можно написать или, что эквивалентно, , один общий масштабный коэффициент. Это мягкое ограничение $\mathbf{A}^{\prime}$ $\alpha_i=1$ $\alpha_i \gets \bar{\alpha}$ будет пытаться заставить нулевой набор полинома соблюдать локальную непрерывность данных. Такая регуляризация также избавляет нас от решения чувствительной однородной системы и позволяет переписать систему в более компактной форме : $\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}$

В общем, решение этой системы уравнений будет одновременно направлять квадрику, попадающую в облако точек, и выравнивать ее градиенты по нормали. Также можно по-разному взвешивать вклады точек и нормалей. В некоторых случаях, чтобы получить специфичное для типа соответствие, достаточно небольшого изменения учетом желаемого примитива. Для всех этих деталей, а также для некоторого теоретического анализа и псевдокода, я отсылаю вас к вышеупомянутым публикациям. $\mathbf{A}$

Толга Бердал
источник

Это здорово! Как изменить A так, чтобы он по-разному взвешивал относительные вклады точек и нормалей?

Музейный

Просто умножьте первые строки, являющиеся точечными уравнениями, на желаемый вес. Необязательно, чтобы масштабировать строки, соответствующие нормали, нужно также масштабировать правую часть уравнения: .

n

$\mathbf{n}$

Толга Бердал

Спасибо. Не следует ли убрать символ транспонирования из q и n в последнем уравнении?

Музейный

Еще раз спасибо. Убрал их.

Толга

Я знаю один пример, когда нормали были включены в процедуру подбора. Это не прямая подгонка квадрик. Локально параметризованный патч устанавливается на точки и нормали. Использование нормалей дает больше уравнений в задаче подгонки, позволяя использовать многочлены более высокого порядка.

Новый алгоритм кубического порядка для аппроксимации главных векторов направления

Абхилаш Редди М
источник

Смотрите также эту статью

Эрмитова интерполяция неявных поверхностей с радиальными базисными функциями

и это расширение

Основные функции Эрмита

LHF
источник