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

В компьютерной графике иерархический RBF — это метод интерполяции , основанный на радиальных базисных функциях (RBF). Иерархическая RBF-интерполяция находит применение при построении моделей формы в 3D-компьютерной графике (см. изображение Стэнфордского кролика ниже), обработке результатов 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$ для точек, не лежащих на фигуре
Как JC Carr et al. показал, ^[1] эта функция выглядит как $\mathbf {f} (\mathbf {x} )=\sum _{i=1}^{N}\lambda _{i}\varphi (\mathbf {x} ,\mathbf {c} _{i})$ где:

$\varphi$ — есть RBF ; $\lambda$ — коэффициенты, являющиеся решением системы, изображенной на рисунке:

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

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

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

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

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

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

Ссылки

^ Карр, Дж.К.; Битсон, РК; Черри, Джей Би; Митчелл, Ти Джей; Испуг, WR; МакКаллум, Британская Колумбия; Эванс, Т.Р. (2001), «Реконструкция и представление трехмерных объектов с радиальными базисными функциями», ACM SIGGRAPH 2001, Лос-Анджелес, Калифорния, стр. 67–76.
^ Башков, Е.А.; Бабков В.С. (2008) «Исследование RBF-алгоритма и его модификаций, применимыхвозможности построения фигурных компьютерных моделей в медицинской практике». Проц Межд.Конференция «Моделирование-2008», Институт моделирования в энергетике имени Пухова, [1] Архивировано 22 июля 2011 г. на Wayback Machine (на русском языке).
^ Пудеру, Дж. и др. (2004), «Адаптивная иерархическая RBF-интерполяция для создания плавных цифровых моделей высот», Proc. 12-й Международный чемпионат ACM. Симп. Достижения в области географических информационных систем 2004, ACP Press, стр. 232–240.
^ Цян, В.; Пан, З.; Чун, К.; Цзяцзюнь, Б. (2007), «Рендеринг поверхности для параллельных срезов контуров медицинских изображений», Computing in Science & Engineering, 9 (1), январь – февраль 2007 г., стр. 32–37.
^ Бабков, В.С. (2008) «Модификация иерархического RBF-метода для 3D-моделирования на основе результатов лазерного сканирования». Учеб. Межд. Конференция «Современные проблемы и достижения радио, связи».и информатики», Запорожский национальный технический университет, [2] Архивировано 22 июля 2011 г. в Wayback Machine (на украинском языке).

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

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

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

[4] Цян, В.; Пан, З.; Чун, К.; Цзяцзюнь, Б. (2007), «Рендеринг поверхности для параллельных срезов контуров медицинских изображений», Computing in Science & Engineering, 9 (1), январь – февраль 2007 г., стр. 32–37.

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

[1]

[2]

[3]

[4]

[5]