Иерархический РБФ

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

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

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

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

$\varphi$ — это РБФ ; — это коэффициенты, которые являются решением системы, показанной на рисунке: $\лямбда$

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

Другие методы

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

Иерархический алгоритм

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

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

Ссылки

^ Карр, Дж. К.; Битсон, РК; Черри, Дж. Б.; Митчелл, Т. Дж.; Фрайт, В. Р.; МакКаллум BC; Эванс, ТР (2001), «Реконструкция и представление трехмерных объектов с помощью радиальных базисных функций» ACM SIGGRAPH 2001, Лос-Анджелес, Калифорния, стр. 67–76.
^ Башков, Е.А.; Бабков, В.С. (2008) «Исследование возможностей применения RBF-алгоритма и его модификаций для построения компьютерных моделей формы в медицинской практике». Труды Международной конференции «Моделирование-2008», Институт моделирования в энергетике им. А.В. Пухова, [1] Архивировано 22 июля 2011 г. на Wayback Machine (на русском языке)
^ Pouderoux, J. et al. (2004), «Адаптивная иерархическая интерполяция RBF для создания гладких цифровых моделей рельефа», Труды 12-го Международного симпозиума ACM «Достижения в области географических информационных систем» 2004 г., ACP Press, стр. 232–240
^ Qiang, W.; Pan, Z.; Chun, C.; Jiajun, B. (2007), «Поверхностная визуализация для параллельного среза контуров из медицинских изображений», Computing in science & engineering, 9(1), январь–февраль 2007 г., стр. 32–37
^ Бабков, ВС (2008) «Модификация иерархического метода RBF для 3D-моделирования на основе результатов лазерного сканирования». Труды Международной конференции «Современные проблемы и достижения радиосвязи и информатики», Запорожский национальный технический университет, [2] Архивировано 22 июля 2011 г. на Wayback Machine (на украинском языке)

[1] Карр, Дж. К.; Битсон, РК; Черри, Дж. Б.; Митчелл, Т. Дж.; Фрайт, В. Р.; МакКаллум BC; Эванс, ТР (2001), «Реконструкция и представление трехмерных объектов с помощью радиальных базисных функций» ACM SIGGRAPH 2001, Лос-Анджелес, Калифорния, стр. 67–76.

[2] Башков, Е.А.; Бабков, В.С. (2008) «Исследование возможностей применения RBF-алгоритма и его модификаций для построения компьютерных моделей формы в медицинской практике». Труды Международной конференции «Моделирование-2008», Институт моделирования в энергетике им. А.В. Пухова, [1] Архивировано 22 июля 2011 г. на Wayback Machine (на русском языке)

[3] Pouderoux, J. et al. (2004), «Адаптивная иерархическая интерполяция RBF для создания гладких цифровых моделей рельефа», Труды 12-го Международного симпозиума ACM «Достижения в области географических информационных систем» 2004 г., ACP Press, стр. 232–240

[4] Qiang, W.; Pan, Z.; Chun, C.; Jiajun, B. (2007), «Поверхностная визуализация для параллельного среза контуров из медицинских изображений», Computing in science & engineering, 9(1), январь–февраль 2007 г., стр. 32–37

[5] Бабков, ВС (2008) «Модификация иерархического метода RBF для 3D-моделирования на основе результатов лазерного сканирования». Труды Международной конференции «Современные проблемы и достижения радиосвязи и информатики», Запорожский национальный технический университет, [2] Архивировано 22 июля 2011 г. на Wayback Machine (на украинском языке)