Иерархический RBF

В компьютерной графике, иерархический RBF - это метод интерполяции, основанный на радиальных базисных функциях (RBF). Иерархическая интерполяция RBF применяется при построении моделей формы в 3D компьютерной графике (см. Изображение Stanford Bunny ниже), обработке результатов с 3D-сканера, реконструкция местности и др.

Эта проблема неофициально называется «интерполяция множества точек с большим разбросом».

Этапы метода (например, в 3D) состоят из следующего:

• Пусть разбросанные точки представлены в виде набора $P\; =\; \{c\; i\; =\; (x\; i,\; y\; i,\; z\; i)\; |\; я\; знак\; равно\; 1\; N\; \subset \; R\; 3\}\; \{\backslash \; Displaystyle\; \backslash \; mathbf\; \{P\}\; =\; \backslash \; \{\backslash \; mathbf\; \{c\}\; \_\; \{i\}\; =\; (\backslash \; mathbf\; \{x\}\; \_\; \{i\},\; \backslash \; mathbf\; \{y\}\; \_\; \{i\},\; \backslash \; mathbf\; \{z\}\; \_\; \{i\})\; \backslash \; vert\; \_\; \{i\; =\; 1\}\; ^\; \{N\}\; \backslash \; subset\; \backslash \; mathbb\; \{R\}\; ^\; \{3\}\; \backslash \}\}$
• Пусть существует набор значений некоторой функции в разбросанные точки $H\; =\; \{привет\; |\; я\; знак\; равно\; 1\; N\; \subset \; R\}\; \{\backslash \; displaystyle\; \backslash \; mathbf\; \{H\}\; =\; \backslash \; \{\backslash \; mathbf\; \{h\}\; \_\; \{i\}\; \backslash \; vert\; \_\; \{i\; =\; 1\}\; ^\; \{N\}\; \backslash \; subset\; \backslash \; mathbb\; \{R\}\; \backslash \}\}$
• Найдите функцию $f\; (x)\; \{\backslash \; displaystyle\; \backslash \; mathbf\; \{f\}\; (\backslash \; mathbf\; \{x\})\}$, которая будет удовлетворять условию $f\; (x)\; =\; 1\; \{\backslash \; displaystyle\; \backslash \; mathbf\; \{f\}\; (\backslash \; mathbf\; \{x\})\; =\; 1\}$для точек, лежащих на фигуре, и $f\; (x)\; \ne \; 1\; \{\backslash \; displaystyle\; \backslash \; mathbf\; \{f\}\; (\backslash \; mathbf\; \{\; x\})\; \backslash \; neq\; 1\}$для точек, не лежащих на форме
• Как JC Carr et al. как показано, эта функция выглядит так: $е\; (x)\; =\; \sum \; i\; =\; 1\; N\; \lambda \; i\; \phi \; (x,\; ci)\; \{\backslash \; displaystyle\; \backslash \; mathbf\; \{f\}\; (\backslash \; mathbf\; \{x\})\; =\; \backslash \; sum\; \_\; \{i\; =\; 1\; \}\; ^\; \{N\}\; \backslash \; lambda\; \_\; \{i\}\; \backslash \; varphi\; (\backslash \; mathbf\; \{x\},\; \backslash \; mathbf\; \{c\}\; \_\; \{i\})\}$где:

$\phi \; \{\backslash \; displaystyle\; \backslash \; varphi\}$- это RBF ; $\lambda \; \{\backslash \; displaystyle\; \backslash \; lambda\}$- коэффициенты, являющиеся решением системы , показанной на рисунке:

Для определения поверхности необходимо оценить значение функции $f\; (x)\; \{\backslash \; displaystyle\; \backslash \; mathbf\; \{f\}\; (\backslash \; mathbf\; \{x\})\}$в интересных точках x. Отсутствие такого метода значительно усложняет $O\; (n\; 2)\; \{\backslash \; displaystyle\; \backslash \; mathbf\; \{O\}\; (\backslash \; mathbf\; \{n\}\; ^\; \{2\})\}$для вычисления RBF, решите систему и определите поверхность.

• Уменьшить центры интерполяции ($O\; (n\; 2)\; \{\backslash \; displaystyle\; \backslash \; mathbf\; \{O\}\; (\backslash \; mathbf\; \{n\}\; ^\; \{2\})\}$до вычислить RBF и решить system, $O\; (mn)\; \{\backslash \; displaystyle\; \backslash \; mathbf\; \{O\}\; (\backslash \; mathbf\; \{m\}\; \backslash \; mathbf\; \{n\})\}$для определения поверхности)
• Компактная поддержка RBF ($O\; (n\; log\; \; n)\; \{\backslash \; displaystyle\; \backslash \; mathbf\; \{O\}\; (\backslash \; mathbf\; \{n\}\; \backslash \; log\; \{\backslash \; mathbf\; \{n\}\})\}$для вычисления RBF, $O\; (n\; 1.2..1.5)\; \{\backslash \; displaystyle\; \backslash \; mathbf\; \{O\}\; (\backslash \; mathbf\; \{n\}\; ^\; \{\; 1.2..1.5\})\}$для решения system, $O\; (m\; log\; \; n)\; \{\backslash \; displaystyle\; \backslash \; mathbf\; \{O\}\; (\backslash \; mathbf\; \{m\}\; \backslash \; log\; \{\; \backslash \; mathbf\; \{n\}\})\}$для определения поверхности)
• FMM ($O\; (n\; 2)\; \{\backslash \; displaystyle\; \backslash \; mathbf\; \{O\}\; (\backslash \; mathbf\; \{n\}\; ^\; \{\; 2\})\}$для вычисления RBF, $O\; (n\; log\; \; n)\; \{\backslash \; displaystyle\; \backslash \; mathbf\; \{O\}\; (\backslash \; mathbf\; \{n\}\; \backslash \; log\; \{\backslash \; mathbf\; \{\; n\}\})\}$для решения system, $O\; (m\; +\; n\; log\; \; n)\; \{\backslash \; displaystyle\; \backslash \; mathbf\; \{O\}\; (\backslash \; mathbf\; \{m\}\; +\; \backslash \; mathbf\; \{n\}\; \backslash \; log\; \{\backslash \; mathbf\; \{n\}\})\}$для определения поверхности)

Идея иерархического алгоритма заключается в ускорении вычислений за счет декомпозиции сложных задач на множество простых (см. картина).

В этом случае иерархическое разделение пространства содержит точки на элементарных частях, а система малой размерности решает для каждой. Расчет поверхности в этом случае сводится к иерархическому (на основе древовидной структуры ) расчету интерполянта. Метод для случая 2D предложен Pouderoux J. et al. Для случая 3D в задачах 3D-графики используется метод W. Qiang et al. и модифицировано Бабковым В.