Anisotropic diffusion of surfaces and functions on surfaces

ABSTRACT

We present a unified anisotropic geometric diffusion PDE model for smoothing (fairing) out noise both in triangulated two-manifold surface meshes in IR³ and functions defined on these surface meshes, while enhancing curve features on both by careful choice of an anisotropic diffusion tensor. We combine the C¹ limit representation of Loop's subdivision for triangular surface meshes and vector functions on the surface mesh with the established diffusion model to arrive at a discretized version of the diffusion problem in the spatial direction. The time direction discretization then leads to a sparse linear system of equations. Iteratively solving the sparse linear system yields a sequence of faired (smoothed) meshes as well as faired functions.

REFERENCES

• 1: Action, S. T. 1998. Multigrid anisotropic diffusion. IEEE Trans. Image Process. 7, 3, 280--291.
• 2: Arden, G. 2001. Approximation properties of subdivision surfaces. PhD Thesis, University of Washington.
• 3: Bansch, E. and Mikula, K. 2001. Adaptivity in 3D image processing. Manuscript.
• 4: Bertalmio, M., Cheng, L. T., and Osher, S. 2000a. Variational problems and partial differential equations on implicit surfaces. CAM Rep. 00-23, UCLA, Mathematics Department.
• 5: Bertalmio, M., Sapiro, G., Cheng, L. T., and Osher S. 2000b. A framework for solving surface partial differential equations for computer graphics applications. CAM Rep. 00-43, UCLA, Mathematics Department.
• 6: Catmull, E. and Clark, J. 1978. Recursively generated B-spline surfaces on arbitrary topological meshes. Comput. Aided Des. 10, 6, 350--355.
• 7: Chan, T. and Shen, J. 1999. Variational restoration of non-flat images features: Models and algorithms. CAM Rep. 99-20, UCLA, Mathematics Department.
• 8: Chopp, D. L. and Sethian, J. A. 1999. Motion by intrinsic Laplacian of curvature. Interfaces Free Bound. 1, 1--18.
• 9: Cirak, F., Ortiz, M., and Schroder, P. 2000. Subdivision surfaces: A new paradigm for thin-shell finite-element analysis. Int. J. Numer. Meth. Eng. 47, 2039--2072.
• 10: 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
• 11: 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]
• 12: Desbrun, M., Meyer, M., Schröder, P., and Barr, A. H. 2000b. Anisotropic feature-preserving denoising of height fields and bivariate data. In Proceedings of Graphics Interface'2000, 145--152.
• 13: Desbrun, M., Meyer, M., Schröder, P., and Barr, A. H. 2000c. Discrete differential-geometry operators in nD. Available at http://www.multires.caltech.edu/pubs/.
• 14: do Carmo, M. 1992. Riemannian Geometry. Boston.
• 15: Doo, D. and Sabin, M. 1978. Behaviours of recursive division surfaces near extraordinary points. Comput. Aided Des. 10, 6, 356--360.
• 16: Nira Dyn , David Levine , John A. Gregory, A butterfly subdivision scheme for surface interpolation with tension control, ACM Transactions on Graphics (TOG), v.9 n.2, p.160-169, April 1990 [doi>10.1145/78956.78958]
• 17: Greiner. G. 1994. Variational design and fairing of spline surface. Comput. Graph. Forum 13, 143--154.
• 18: Igor Guskov , Wim Sweldens , Peter Schröder, Multiresolution signal processing for meshes, Proceedings of the 26th annual conference on Computer graphics and interactive techniques, p.325-334, July 1999 [doi>10.1145/311535.311577]
• 19: Bart M. Romeny, Geometry-Driven Diffusion in Computer Vision, Kluwer Academic Publishers, Norwell, MA, 1994
• 20: Hugues Hoppe , Tony DeRose , Tom Duchamp , Mark Halstead , Hubert Jin , John McDonald , Jean Schweitzer , Werner Stuetzle, Piecewise smooth surface reconstruction, Proceedings of the 21st annual conference on Computer graphics and interactive techniques, p.295-302, July 1994 [doi>10.1145/192161.192233]
• 21: Hugues Hoppe , Tony DeRose , Tom Duchamp , John McDonald , Werner Stuetzle, Mesh optimization, Proceedings of the 20th annual conference on Computer graphics and interactive techniques, p.19-26, September 1993 [doi>10.1145/166117.166119]
• 22: Andreas Hubeli , Markus Gross, Fairing of non-manifolds for visualization, Proceedings of the conference on Visualization '00, p.407-414, October 2000, Salt Lake City, Utah, United States
• 23: Kawohl, B. and Kutev, N. 1998. Maximum amd comparison principle for one-dimensional anisotropic diffusion. Math. Ann. 311, 1, 107--123.
• 24: Ron Kimmel, Intrinsic scale space for images on surfaces: The Geodesic Curvature Flow, Graphical Models and Image Processing, v.59 n.5, p.365-372, Nov. 1997 [doi>10.1006/gmip.1997.0442]
• 25: Ron Kimmel , Nir A. Sochen, Geometric-Variational Approach for Color Image Enhancement and Segmentation, Proceedings of the Second International Conference on Scale-Space Theories in Computer Vision, p.294-305, September 26-27, 1999
• 26: Ron Kimmel , Ravi Malladi , Nir A. Sochen, Image Processing via the Beltrami Operator, Proceedings of the Third Asian Conference on Computer Vision-Volume I, p.574-581, January 08-10, 1998
• 27: Kobbelt, L. 1996. Discrete fairing. In The Mathematics of Surfaces VII, T. Goodman and R. Martin, Eds., Information Geometers, 101--129.
• 28: Leif Kobbelt , Swen Campagna , Jens Vorsatz , Hans-Peter Seidel, Interactive multi-resolution modeling on arbitrary meshes, Proceedings of the 25th annual conference on Computer graphics and interactive techniques, p.105-114, July 1998 [doi>10.1145/280814.280831]
• 29: Kobbelt, L., Hesse, T., Prautzsch, H., and Schweizerhof, K. 1997. Iterative mesh generation for FE-computation on free form surfaces. Eng. Comput. 14, 806--820.
• 30: Loop, C. T. 1978. Smooth subdivision surfaces based on triangles. Master's Thesis. Tech. Rep. Department of Mathematics, University of Utah.
• 31: Mallet, J. L. 1992. Discrete smooth interpolation in geometric modelling. Comput. Aided Des. 24, 4, 178--191.
• 32: Henry P. Moreton , Carlo H. Séquin, Functional optimization for fair surface design, ACM SIGGRAPH Computer Graphics, v.26 n.2, p.167-176, July 1992
• 33: Osher, S. J. and Fedkiw, R. P. 2000. Level set methods. CAM Rep. 00-07, UCLA, Mathematics Department.
• 34: Perona, P. and Malik, J. 1987. Scale space and edge detection using anisotropic diffusion. In IEEE Computer Society Workshop on Computer Vision.
• 35: Jörg Peters , Ulrich Reif, The simplest subdivision scheme for smoothing polyhedra, ACM Transactions on Graphics (TOG), v.16 n.4, p.420-431, Oct. 1997 [doi>10.1145/263834.263851]
• 36: Preuβer, T. and Rumpf, M. 1999. An adaptive finite element method for large scale image processing. Scale-Space Theor. Comput. Vis. 232--234.
• 37: Rosenberg, S. 1997. The Laplacian on a Riemannian Manifold. Cambridge University Press, New York.
• 38: Sabin, M. 1976. The use of piecewise form of numerical representation of shape. PhD Thesis, Hungarian Academy of Science, Budapest.
• 39: Nicholas S. Sapidis, Designing Fair Curves and Surfaces: Shape Quality in Geometric Modeling and Computer-Aided Design, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1994
• 40: Geometric partial differential equations and image analysis, Cambridge University Press, New York, NY, 2001
• 41: Sapiro, G. and Ringach, D. L. 1998. Anisotropic diffusion on multivalued images with applications to color filtering. IEEE Trans. Image Process. 5, 11, 1582--1586.
• 42: Jean Elaine Schweitzer , Anthony D. Derose, Analysis and application of subdivision surfaces, 1996
• 43: Sethian, J. A. 1999. Level Set Methods and Fast Marching Methods. Cambridge University Press, New York.
• 44: Sochen, N., Kimmel, R., and Malladi, R. 1998. A general framework for low level vision. IEEE Trans. Image Process. 7, 3, 310--318.
• 45: Jos Stam, Exact evaluation of Catmull-Clark subdivision surfaces at arbitrary parameter values, Proceedings of the 25th annual conference on Computer graphics and interactive techniques, p.395-404, July 1998 [doi>10.1145/280814.280945]
• 46: Tang, B., Sapiro, G., and Caselles, V. 2000a. Color image enhancement via chromaticity diffusion. Int. J. of Comput. Vis. 10, 5, 701--707.
• 47: Bei Tang , Guillermo Sapiro , Vicent Caselles, Diffusion of General Data on Non-Flat Manifolds viaHarmonic Maps Theory: The Direction Diffusion Case, International Journal of Computer Vision, v.36 n.2, p.149-161, Feb. 2000 [doi>10.1023/A:1008152115986]
• 48: 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]
• 49: Weickert, J. 1996. Foundations and applications of nonlinear anisotropic diffusion filtering. Z. Angew. Math. Mech. 76, 283--286.
• 50: Weickert, J. 1997. Coherence-enhancing diffusion of colour images. In Proceedings of the VII National Symposium on Pattern and Image Analysis, vol. 1 (April), 239--244.
• 51: Weickert, J. 1998. Anisotropic Diffusion in Image Processing. Teubner, Stuttgart.
• 52: William Welch , Andrew Witkin, Variational surface modeling, ACM SIGGRAPH Computer Graphics, v.26 n.2, p.157-166, July 1992
• 53: William Welch , Andrew Witkin, Free-form shape design using triangulated surfaces, Proceedings of the 21st annual conference on Computer graphics and interactive techniques, p.247-256, July 1994 [doi>10.1145/192161.192216]
• 54: Rüdiger Westermann , Christopher Johnson , Thomas Ertl, A level-set method for flow visualization, Proceedings of the conference on Visualization '00, p.147-154, October 2000, Salt Lake City, Utah, United States
• 55: Whitaker, R. and Breen, D. 1998. Level set models for the deformation of solid objects. In Proceedings of the Third International Workshop on Implicit Surfaces, Eurographics Association (June), 19--35.
• 56: Willmore, T. J. 1982. Total Curvature in Riemannian Geometry. Ellis Horwood Limited, UK.
• 57: Willmore, T. J. 1993. Riemannian Geometry, Clarendon, New York.
• 58: Xu, G. and Bajaj, C. 2002. Curvature computations of 2-manifold in IRk. J. Comput. Math. (to appear).
• 59: Yezzi, A., Jr. 1998. Modified curvature motion for image smoothing and enhancement. IEEE Trans. Image Process. 7, 3, 345--352.
• 60: Zhao, H. K., Osher, S., and Fedkiw, R. 2001. Fast surface reconstruction using the level set method. CAM Rep. 01-01, UCLA, Mathematics Department.
• 61: Hong-Kai Zhao , Stanley Osher , Barry Merriman , Myungjoo Kang, Implicit and nonparametric shape reconstruction from unorganized data using a variational level set method, Computer Vision and Image Understanding, v.80 n.3, p.295-314, Dec. 2000 [doi>10.1006/cviu.2000.0875]
• 62: Denis Zorin , Peter Schröder , Wim Sweldens, Interpolating Subdivision for meshes with arbitrary topology, Proceedings of the 23rd annual conference on Computer graphics and interactive techniques, p.189-192, August 1996 [doi>10.1145/237170.237254]

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

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.8 Partial Differential Equations
          Subjects: Finite element methods

  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Splines
      I.3.7 Three-Dimensional Graphics and Realism
          Subjects: Color, shading, shadowing, and texture
  I.4 IMAGE PROCESSING AND COMPUTER VISION
      I.4.3 Enhancement

General Terms:
Algorithms, Experimentation

Keywords:
Loop's subdivision, Riemannian manifold, Surface function diffusion, noise reduction, texture mapping