hierarchical RBF

{{Multiple issues|

{{expert needed|Mathematics|ex2=Computing|reason=The explanation is incomplete and the math contains inconsistencies|date=September 2020}}

}}

In computer graphics, hierarchical RBF is an interpolation method based on radial basis functions (RBFs). Hierarchical RBF interpolation has applications in treatment of results from a 3D scanner, terrain reconstruction, and the construction of shape models in 3D computer graphics (such as the Stanford bunny, a popular 3D model).

This problem is informally named as "large scattered data point set interpolation."

Method

The steps of the interpolation method (in three dimensions) are as follows:

Let the scattered points be presented as set $\mathbf{P}=\{\mathbf{c}_i=(\mathbf{x}_i,\mathbf{y}_i,\mathbf{z}_i)\vert^{N}_{i=1} \subset \mathbb{R}^3\}$
Let there exist a set of values of some function in scattered points $\mathbf{H}=\{\mathbf{h}_i \vert^{N}_{i=1}\subset \mathbb{R}\}$
Find a function $\mathbf{f}(\mathbf{x})$ that will meet the condition $\mathbf{f}(\mathbf{x})=1$ for points lying on the shape and $\mathbf{f}(\mathbf{x})\neq1$ for points not lying on the shape

As J. C. Carr et al. showed,Carr, J.C.; Beatson, R.K.; Cherrie, J.B.; Mitchell, T.J.; Fright, W.R.; McCallum B.C.; Evans, T.R. (2001), “Reconstruction and Representation of 3D Objects with Radial Basis Functions” ACM SIGGRAPH 2001, Los Angeles, CA, P. 67–76. this function takes the form $\mathbf{f}(\mathbf{x})=\sum_{i=1}^N \lambda_i \varphi(\mathbf{x},\mathbf{c}_i)$ where $\varphi$ is a radial basis function and $\lambda$ are the coefficients that are the solution of the following linear system of equations:

$\begin{bmatrix} \varphi(c_1,c_1) & \varphi(c_1,c_2) & ... & \varphi(c_1,c_N) \\ \varphi(c_2,c_1) & \varphi(c_2,c_2) & ... & \varphi(c_2,c_N) \\ ... & ... & ... & ... \\ \varphi(c_N,c_1) & \varphi(c_N,c_2) & ... & \varphi(c_N,c_N) \end{bmatrix}* \begin{bmatrix} \lambda_1 \\ \lambda_2 \\ ... \\ \lambda_N \end{bmatrix}=\begin{bmatrix} h_1 \\ h_2 \\ ... \\ h_N \end{bmatrix}$

For determination of surface, it is necessary to estimate the value of function $\mathbf{f}(\mathbf{x})$ in specific points x. A lack of such method is a considerable complication on the order of $\mathbf{O}(\mathbf{n}^2)$ to calculate RBF, solve system, and determine surface.Bashkov, E.A.; Babkov, V.S. (2008) “Research of RBF-algorithm and his modifications apply

possibilities for the construction of shape computer models in medical practice”. Proc Int.

Conference "Simulation-2008", Pukhov Institute for Modelling in Energy Engineering, [http://babkov.name/article/2008-09.pdf] {{Webarchive|url=https://web.archive.org/web/20110722234353/http://babkov.name/article/2008-09.pdf|date=2011-07-22}} (in Russian)

Other methods

Reduce interpolation centers ( $\mathbf{O}(\mathbf{n}^2)$ to calculate RBF and solve system, $\mathbf{O}(\mathbf{m}\mathbf{n})$ to determine surface)
Compactly support RBF ( $\mathbf{O}(\mathbf{n}\log{\mathbf{n}})$ to calculate RBF, $\mathbf{O}(\mathbf{n}^{1.2..1.5})$ to solve system, $\mathbf{O}(\mathbf{m}\log{\mathbf{n}})$ to determine surface)
FMM ( $\mathbf{O}(\mathbf{n}^2)$ to calculate RBF, $\mathbf{O}(\mathbf{n}\log{\mathbf{n}})$ to solve system, $\mathbf{O}(\mathbf{m}+\mathbf{n}\log{\mathbf{n}})$ to determine surface)

Hierarchical algorithm

A hierarchical algorithm allows for an acceleration of calculations due to decomposition of intricate problems on the great number of simple (see picture). File:Hierarchical algorithm flow chart.gif

In this case, hierarchical division of space contains points on elementary parts, and the system of small dimension solves for each. The calculation of surface in this case is taken to the hierarchical (on the basis of tree-structure) calculation of interpolant. A method for a 2D case is offered by Pouderoux J. et al.Pouderoux, J. et al. (2004), “Adaptive hierarchical RBF interpolation for creating smooth digital elevathion models”, Proc. 12-th ACM Int. Symp. Advances in Geographical information Systems 2004, ACP Press, P. 232–240 For a 3D case, a method is used in the tasks of 3D graphics by W. Qiang et al.Qiang, W.; Pan, Z.; Chun, C.; Jiajun, B. (2007), “Surface rendering for parallel slice of contours from medical imaging”, Computing in science & engineering, 9(1), January–February 2007, P 32–37 and modified by Babkov V.Babkov, V.S. (2008) “Modification of hierarchical RBF method for 3D-modelling based on laser scan result”. Proc. Int. Conference “Modern problems and achievement of radio, communication

and informatics”, Zaporizhzhya National Technical University, [http://babkov.name/article/2008-08.pdf] {{Webarchive|url=https://web.archive.org/web/20110722234420/http://babkov.name/article/2008-08.pdf|date=2011-07-22}} (in Ukrainian)

References

Category:Geometric algorithms

Category:Computer graphics

Category:Interpolation