Smooth surface reconstruction from noisy range data

ABSTRACT

This paper shows that scattered range data can be smoothed at low cost by fitting a Radial Basis Function (RBF) to the data and convolving with a smoothing kernel (low pass filtering). The RBF exactly describes the range data and interpolates across holes and gaps. The data is smoothed during evaluation of the RBF by simply changing the basic function. The amount of smoothing can be varied as required without having to fit a new RBF to the data. The key feature of our approach is that it avoids resampling the RBF on a fine grid or performing a numerical convolution. Furthermore, the computation required is independent of the extent of the smoothing kernel, i.e., the amount of smoothing. We show that particular smoothing kernels result in the applicability of fast numerical methods. We also discuss an alternative approach in which a discrete approximation to the smoothing kernel achieves similar results by adding new centres to the original RBF during evaluation. This approach allows arbitrary filter kernels, including anisotropic and spatially varying filters, to be applied while also using established fast evaluation methods. We illustrate both techniques with LIDAR laser scan data and noisy synthetic data.

REFERENCES

• 1: Milton Abramowitz, Handbook of Mathematical Functions, With Formulas, Graphs, and Mathematical Tables,, Dover Publications, Incorporated, 1974
• 2: R. K. Beatson , N. Dyn, Multiquadric B-splines, Journal of Approximation Theory, v.87 n.1, p.1-24, Oct. 1996 [doi>10.1006/jath.1996.0089]
• 3: BEATSON, R. K., AND LIGHT, W. A. 1997. Fast evaluation of radial basis functions: Methods for two-dimensional polyharmonic splines. IMA Journal of Numerical Analysis 17, 343-372.
• 4: R. K. Beatson , W. A. Light , S. Billings, Fast Solution of the Radial Basis Function Interpolation Equations: Domain Decomposition Methods, SIAM Journal on Scientific Computing, v.22 n.5, p.1717-1740, 2000 [doi>10.1137/S1064827599361771]
• 5: BEATSON, R. K., CHERRIE, J. B., AND RAGOZIN, D. L. 2001. Fast evaluation of radial basis functions: Methods for four-dimensional polyharmonic splines. SIAM J. Math. Anal. 32, 6, 1272-1310.
• 6: J. C. Carr , R. K. Beatson , J. B. Cherrie , T. J. Mitchell , W. R. Fright , B. C. McCallum , T. R. Evans, Reconstruction and representation of 3D objects with radial basis functions, Proceedings of the 28th annual conference on Computer graphics and interactive techniques, p.67-76, August 2001 [doi>10.1145/383259.383266]
• 7: CHENEY, E. W., AND LIGHT, W. A. 1999. A Course in Approximation Theory. Brooks Cole, Pacific Grove.
• 8: J. B. Cherrie , R. K. Beatson , G. N. Newsam, Fast Evaluation of Radial Basis Functions: Methods for Generalized Multiquadrics in $\RR^\protectn$, SIAM Journal on Scientific Computing, v.23 n.5, p.1549-1571, 2002 [doi>10.1137/S1064827500367609]
• 9: DINH, H. Q., SLABAUGH, G., AND TURK, G. 2001. Reconstructing surfaces using anisotropic basis functions. In International Conference on Computer Vision (ICCV) 2001, Vancouver, Canada,, 606-613.
• 10: MICCHELLI, C. A. 1986. Interpolation of scattered data: Distance matrices and conditionally positive definite functions. Constr. Approx. 2, 11-22.
• 11: Bryan S. Morse , Terry S. Yoo , David T. Chen , Penny Rheingans , K. R. Subramanian, Interpolating Implicit Surfaces from Scattered Surface Data Using Compactly Supported Radial Basis Functions, Proceedings of the International Conference on Shape Modeling & Applications, p.89, May 07-11, 2001
• 12: Mark Pauly , Markus Gross, Spectral processing of point-sampled geometry, Proceedings of the 28th annual conference on Computer graphics and interactive techniques, p.379-386, August 2001 [doi>10.1145/383259.383301]
• 13: SAVCHENKO, V. V., PASKO, A. A., OKUNEV, O. G., AND KUNII, T. L. 1995. Function representation of solids reconstructed from scattered surface points and contours. Computer Graphics Forum 14, 4, 181-188.
• 14: Gabriel Taubin, A signal processing approach to fair surface design, Proceedings of the 22nd annual conference on Computer graphics and interactive techniques, p.351-358, September 1995 [doi>10.1145/218380.218473]
• 15: TURK, G., AND O'BRIEN, J. F. 1999. Variational implicit surfaces. Tech. Rep. GIT-GVU-99-15, Georgia Institute of Technology, May.
• 16: Greg Turk , Huong Quynh Dinh , James F. O'Brien , Gary Yngve, Implicit Surfaces that Interpolate, Proceedings of the International Conference on Shape Modeling & Applications, p.62, May 07-11, 2001
• 17: WAHBA, G. 1990. Spline Models for Observational Data. No. 59 in CBMS-NSF Regional Conference Series in Applied Math. SIAM.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Splines

Keywords:
anti-aliasing, low pass filtering, noise reduction, point-cloud surfacing, radial basis functions, spline smoothing, surface reconstruction