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

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

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

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

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

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

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

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

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

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

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

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

Рекомендации

^ Carr, J.C .; Beatson, R.K .; Cherrie, J.B .; Mitchell, T.J .; Страх, W.R .; McCallum B.C .; Эванс, Т. (2001), «Реконструкция и представление трехмерных объектов с радиальными базовыми функциями» ACM SIGGRAPH 2001, Лос-Анджелес, Калифорния, стр. 67–76.
^ Башков, Е.А .; Бабков, В. (2008) «Исследование RBF-алгоритма и его модификаций для применения возможностей построения компьютерных моделей форм в медицинской практике». Материалы международной конференции «Симуляторы-2008», Институт моделирования в энергетике им. Пухова, г. [1] В архиве 2011-07-22 на Wayback Machine (на русском)
^ Pouderoux, J. et al. (2004), «Адаптивная иерархическая интерполяция RBF для создания гладких цифровых моделей элеватионов», Proc. 12-й ACM Int. Symp. Достижения в географических информационных системах 2004, ACP Press, стр. 232–240
^ Qiang, W .; Пан, З .; Chun, C .; Цзяцзюнь, Б. (2007), «Рендеринг поверхности для параллельного среза контуров из медицинских изображений», Вычисления в науке и технике, 9 (1), январь – февраль 2007 г., стр. 32–37
^ Бабков, В. (2008) «Модификация иерархического метода RBF для 3D-моделирования на основе результатов лазерного сканирования». Proc. Int. Конференция «Современные проблемы и достижения радио, связи и информатики», Запорожский национальный технический университет, г. [2] В архиве 2011-07-22 на Wayback Machine (на украинском языке)

[1] Carr, J.C .; Beatson, R.K .; Cherrie, J.B .; Mitchell, T.J .; Страх, W.R .; McCallum B.C .; Эванс, Т. (2001), «Реконструкция и представление трехмерных объектов с радиальными базовыми функциями» ACM SIGGRAPH 2001, Лос-Анджелес, Калифорния, стр. 67–76.

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

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

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

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

[1]

[2]

[3]

[4]

[5]