3D distance transform adaptive filtering for smoothing and denoising triangle meshes

ABSTRACT

In this paper we compute the distance transform of a 3D triangle mesh. A volumetric voxel representation is defined over the mesh to evaluate the distance transform. Optimizations are described to efficiently manipulate the volumetric data structure that represents the mesh. A new method for adaptive filtering of the distance transform is introduced to smooth and reduce the noise on the meshes that were reconstructed from scanned data acquired with a 3D scanner. A modified version of the Marching Cube algorithm is presented to correctly reconstruct the final mesh of the filtered distance transform defined with the voxel representation. The new filtering method is feature preserving and it is more versatile than previous algorithms described in the literature. Results show that this method outperforms previous ones in term of an error metric comparison. Future works are discussed to improve the new method and its computing performances.

REFERENCES

• 1: Nina Amenta , Marshall Bern , Manolis Kamvysselis, A new Voronoi-based surface reconstruction algorithm, Proceedings of the 25th annual conference on Computer graphics and interactive techniques, p.415-421, July 1998 [doi>10.1145/280814.280947]
• 2: Paul J. Besl , Neil D. McKay, A Method for Registration of 3-D Shapes, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.14 n.2, p.239-256, February 1992 [doi>10.1109/34.121791]
• 3: Bobenko A. I., Schroder P. 2005. Discrete Willmore Flow. Third Eurographics Symposium on Geometry Processing, Vienna, Austria, 101--110.
• 4: Daniel Cohen-Or , Amira Solomovic , David Levin, Three-dimensional distance field metamorphosis, ACM Transactions on Graphics (TOG), v.17 n.2, p.116-141, April 1998 [doi>10.1145/274363.274366]
• 5: Davis J., Marschner S., Garr M., Levoy M. 2002. Filling Holes in Complex Surfaces Using Volumetric Diffusion. First International Symposium on 3D Data Processing, Visualization, and Transmission, Padua, Italy.
• 6: 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]
• 7: Shachar Fleishman , Iddo Drori , Daniel Cohen-Or, Bilateral mesh denoising, ACM Transactions on Graphics (TOG), v.22 n.3, July 2003
• 8: Rafael C. Gonzalez , Richard E. Woods, Digital Image Processing, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 2001
• 9: Hildebrandt K., Polthier K. 2004. Anisotropic Filtering of Non-Linear Surface Features. EUROGRAPHICS 2004, Grenoble, France, Computer Graphics Forum, Vol. 23, No. 3, 391--400.
• 10: A. Hilton , A. J. Stoddart , J. Illingworth , T. Windeatt, Implicit surface-based geometric fusion, Computer Vision and Image Understanding, v.69 n.3, p.273-291, March 1998 [doi>10.1006/cviu.1998.0664]
• 11: Jian Huang , Yan Li , Roger Crawfis , Shao Chiung Lu , Shuh Yuan Liou, A complete distance field representation, Proceedings of the conference on Visualization '01, October 21-26, 2001, San Diego, California
• 12: Leif P. Kobbelt , Mario Botsch , Ulrich Schwanecke , Hans-Peter Seidel, Feature sensitive surface extraction from volume data, Proceedings of the 28th annual conference on Computer graphics and interactive techniques, p.57-66, August 2001 [doi>10.1145/383259.383265]
• 13: Levy B., Mallet J.-L. 1999. Constrained Discrete Fairing for Arbitrary Meshes. Tech. Report, ISA-GOCAD (Inria Lorraine/CNRS) ENSG, Vandoeuvre, France.
• 14: William E. Lorensen , Harvey E. Cline, Marching cubes: A high resolution 3D surface construction algorithm, Proceedings of the 14th annual conference on Computer graphics and interactive techniques, p.163-169, August 1987
• 15: Zhihong Mao , Lizhuang Ma , Mingxi Zhao , Xuezhong Xiao, SUSAN structure preserving filtering for mesh denoising, The Visual Computer: International Journal of Computer Graphics, v.22 n.4, p.276-284, April 2006 [doi>10.1007/s00371-006-0005-7]
• 16: Takashi Mashiko , Hirokazu Yagou , Daming Wei , Youdong Ding , Genfeng Wu, 3D Triangle Mesh Smoothing via Adaptive MMSE Filtering, Proceedings of the The Fourth International Conference on Computer and Information Technology (CIT'04), p.734-740, September 14-16, 2004
• 17: Fakir S. Nooruddin , Greg Turk, Simplification and Repair of Polygonal Models Using Volumetric Techniques, IEEE Transactions on Visualization and Computer Graphics, v.9 n.2, p.191-205, April 2003 [doi>10.1109/TVCG.2003.1196006]
• 18: Ohtake Y., Belyaev A. G., Seidel H.-P. 2002. Mesh Smoothing by Adaptive and Anisotropic Gaussian Filter Applied to Mesh Normals. Vision, Modeling, and Visualization 2002, Erlangen, Germany, 203--210.
• 19: Rocchini C., Cignoni P., Montani C., Pingi P., Scopigno R. 2001. A Low Cost 3D Scanner Based on Structured Light. EUROGRAPHICS 2001, Manchester, UK, Computer Graphics Forum, Vol. 20, No. 3, 299--308.
• 20: Sethian J. A. 1999. Level Set Methods and Fast Marching Methods. Cambridge University Press.
• 21: Christian Sigg , Ronald Peikert , Markus Gross, Signed Distance Transform Using Graphics Hardware, Proceedings of the 14th IEEE Visualization 2003 (VIS'03), p.12, October 22-24, 2003 [doi>10.1109/VISUAL.2003.1250358]
• 22: Sud A., Otaduy M. A., Manocha D. 2004. DiFi: Fast 3D Distance Field Computation Using Graphics Hardware. EUROGRAPHICS 2004, Grenoble, France, Computer Graphics Forum, Vol. 23, No. 3, 557--566.
• 23: 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]
• 24: Gokul Varadhan , Shankar Krishnan , TVN Sriram , Dinesh Manocha, Topology preserving surface extraction using adaptive subdivision, Proceedings of the 2004 Eurographics/ACM SIGGRAPH symposium on Geometry processing, July 08-10, 2004, Nice, France [doi>10.1145/1057432.1057464]
• 25: 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
• 26: Yagou H., Ohtake Y., Belyaev A. G. 2003. Mesh Denoising via Iterative Alpha-Trimming and Nonlinear Diffusion of Normals with Automatic Thresholding. Computer Graphics International 2003, Tokyo, Japan, 28--33.

INDEX TERMS

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

Additional Classification:
  I. Computing Methodologies
  I.4 IMAGE PROCESSING AND COMPUTER VISION
      I.4.3 Enhancement

Keywords:
3D convolution, adaptive filtering, distance transform, mesh reconstruction, mesh smoothing, voxel representation