Random walks for mesh denoising

ABSTRACT

This paper considers an approach to mesh denoising based on the concept of random walks. The proposed method consists of two stages: a face normal filtering procedure, followed by a vertex position updating procedure which integrates the denoised face normals in a least-squares sense. Face normal filtering is performed by weighted averaging of normals in a neighbourhood. The weights are based on the probability of arriving at a given neighbour after a random walk of a virtual particle starting at a given face of the mesh and moving a fixed number of steps. The probability of a particle stepping from its current face to a given neighboring face is determined by the angle between the two face normals, using a Gaussian distribution whose width is adaptively adjusted to enhance the feature-preserving property of the algorithm. The vertex position updating procedure uses the conjugate gradient algorithm for speed of convergence. Analysis and experiments show that random walks of different step lengths yield similar denoising results. In particular, iterative application of a one-step random walk in a progressive manner effectively preserves detailed features while denoising the mesh very well. We observe that this approach is faster than many other feature-preserving mesh denoising algorithms.

REFERENCES

• 1: Azzabou, N., Paragios, N., and Guichard, F. 2006. Random walks, constrained multiple hypothesis testing and image enhancement. In ECCV 2006 Proceedings, Springer, A. Leonardis, H. Bischof, and A. Pinz, Eds., vol. 1, 379--390.
• 2: Chandrajit L. Bajaj , Guoliang Xu, Anisotropic diffusion of surfaces and functions on surfaces, ACM Transactions on Graphics (TOG), v.22 n.1, p.4-32, January 2003 [doi>10.1145/588272.588276]
• 3: Botsch, M., and Kobbelt, L. P. 2001. Resampling feature and blend regions in polygonal meshes for surface anti-aliasing. In EG 2001 Proceedings, Blackwell Publishing, A. Chalmers and T.-M. Rhyne, Eds., vol. 20(3), 402--410.
• 4: Botsch, M., Bommes, D., and Kobbelt, L. 2005. Efficient linear system solvers for mesh processing. In Proceedings of the IMA Mathematics of Surfaces XI, Lecture Notes in Computer Science, vol. 3604, 62--83.
• 5: Chun-Yen Chen , Kuo-Young Cheng, A sharpness dependent filter for mesh smoothing, Computer Aided Geometric Design, v.22 n.5, p.376-391, July 2005 [doi>10.1016/j.cagd.2005.04.003]
• 6: U. Clarenz , U. Diewald , M. Rumpf, Anisotropic geometric diffusion in surface processing, Proceedings of the conference on Visualization '00, p.397-405, October 2000, Salt Lake City, Utah, United States
• 7: Mathieu Desbrun , Mark Meyer , Peter Schröder , Alan H. Barr, Implicit fairing of irregular meshes using diffusion and curvature flow, Proceedings of the 26th annual conference on Computer graphics and interactive techniques, p.317-324, July 1999 [doi>10.1145/311535.311576]
• 8: Desbrun, M., Meyer, M., Schröder, P., and Barr, A. H. 2000. Anisotropic Feature-Preserving denoising of height fields and bivariate data. In Graphics Interface'2000 Proceedings, 145--152.
• 9: James R. Diebel , Sebastian Thrun , Michael Brünig, A Bayesian method for probable surface reconstruction and decimation, ACM Transactions on Graphics (TOG), v.25 n.1, p.39-59, January 2006 [doi>10.1145/1122501.1122504]
• 10: Field, D. A. 1988. Laplacian smoothing and delaunay triangulations. Communications in Numerical Methods in Engineering 4, 709--712.
• 11: Shachar Fleishman , Iddo Drori , Daniel Cohen-Or, Bilateral mesh denoising, ACM Transactions on Graphics (TOG), v.22 n.3, July 2003
• 12: Leo Grady, Random Walks for Image Segmentation, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.28 n.11, p.1768-1783, November 2006 [doi>10.1109/TPAMI.2006.233]
• 13: Hildebrandt, K., and Polthier, K. 2004. Anisotropic filtering of non-linear surface features. Computer Graphics Forum 23, 3, 391--400.
• 14: Thouis R. Jones , Frédo Durand , Mathieu Desbrun, Non-iterative, feature-preserving mesh smoothing, ACM Transactions on Graphics (TOG), v.22 n.3, July 2003
• 15: Kim, B., and Rossignac, J. 2005. Geofilter: Geometric selection of mesh filter parameters. Computer Graphics Forum 24, 3, 295--302.
• 16: Diego Nehab , Szymon Rusinkiewicz , James Davis , Ravi Ramamoorthi, Efficiently combining positions and normals for precise 3D geometry, ACM Transactions on Graphics (TOG), v.24 n.3, July 2005
• 17: Nehorai, A., and Hawkes, M. 2000. Performance bounds for estimatin vector systems. IEEE Trans. Signal Processing 48, 6, 1737--1749.
• 18: Ohtake, Y., Belyaev, A., and Bogaevski, I. 2001. Mesh regularization and adaptive smoothing. Computer-Aided Design 33, 11, 789--800.
• 19: Ohtake, Y., Belyaev, A., and Seidel, H.-P. 2002. Mesh smoothing by adaptive and anisotropic gaussian filter applied to mesh normals. In Vision, Modeling, and Visualization 2002, 203--210.
• 20: William H. Press , Saul A. Teukolsky , William T. Vetterling , Brian P. Flannery, Numerical recipes in C (2nd ed.): the art of scientific computing, Cambridge University Press, New York, NY, 1992
• 21: Yuzhong Shen , Kenneth E. Barner, Fuzzy Vector Median-Based Surface Smoothing, IEEE Transactions on Visualization and Computer Graphics, v.10 n.3, p.252-265, May 2004 [doi>10.1109/TVCG.2004.1272725]
• 22: Shen, J., Maxim, B., and Akingbehin, K. 2005. Accurate correction of surface noises of polygonal meshes. International Journal for Numerical Methods in Engineering 64, 12, 1678--1698.
• 23: B. Smolka , K. W. Wojciechowski, Random walk approach to image enhancement, Signal Processing, v.81 n.3, p.465-482, March 2001 [doi>10.1016/S0165-1684(00)00226-7]
• 24: Spitzer, F. 2001. Principles of Random Walk, 2nd ed. Springer, New York.
• 25: M. Szczepanski , B. Smolka , K. N. Plataniotis , A. N. Venetsanopoulos, On the geodesic paths approach to color image filtering, Signal Processing, v.83 n.6, p.1309-1342, June 2003 [doi>10.1016/S0165-1684(03)00058-6]
• 26: Tolga Tasdizen , Ross Whitaker , Paul Burchard , Stanley Osher, Geometric surface smoothing via anisotropic diffusion of normals, Proceedings of the conference on Visualization '02, October 27-November 01, 2002, Boston, Massachusetts
• 27: 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]
• 28: Taubin, G., 2001. Linear anisotropic mesh filtering. IBM Research Report RC22213(W0110-051), IBM T.J. Watson Research Center, October.
• 29: Vollmer, J., Mencl, R., and Müller, H. 1999. Improved laplacian smoothing of noisy surface meshes. Computer Graphics Forum 18, 3, 131--138.
• 30: Wechsler, H., and Kidode, M. 1979. A random walk procedure for texture discrimination. IEEE Transactions on Pattern Analysis and Machine Intelligence PAMI-1, 3, 272--280.
• 31: Hirokazu Yagou , Yutaka Ohtake , Alexander Belyaev, Mesh Smoothing via Mean and Median Filtering Applied to Face Normals, Proceedings of the Geometric Modeling and Processing — Theory and Applications (GMP'02), p.124, July 10-12, 2002
• 32: Yagou, H., Ohtake, Y., and Belyaev, A. G. 2003. Mesh denoising via iterative alpha-trimming and nonlinear diffusion of normals with automatic thresholding. In Computer Graphics International 2003 (CGI'03), 28--34.
• 33: Yizhou Yu , Kun Zhou , Dong Xu , Xiaohan Shi , Hujun Bao , Baining Guo , Heung-Yeung Shum, Mesh editing with poisson-based gradient field manipulation, ACM Transactions on Graphics (TOG), v.23 n.3, August 2004

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Curve, surface, solid, and object representations

Keywords:
feature preservation, mesh denoising, mesh smoothing, random walk