Geometric surface processing via normal maps

ABSTRACT

We propose that the generalization of signal and image processing to surfaces entails filtering the normals of the surface, rather than filtering the positions of points on a mesh. Using a variational strategy, penalty functions on the surface geometry can be formulated as penalty functions on the surface normals, which are computed using geometry-based shape metrics and minimized using fourth-order gradient descent partial differential equations (PDEs). In this paper, we introduce a two-step approach to implementing geometric processing tools for surfaces: (i) operating on the normal map of a surface, and (ii) manipulating the surface to fit the processed normals. Iterating this two-step process, we efficiently can implement geometric fourth-order flows by solving a set of coupled second-order PDEs. The computational approach uses level set surface models; therefore, the processing does not depend on any underlying parameterization. This paper will demonstrate that the proposed strategy provides for a wide range of surface processing operations, including edge-preserving smoothing and high-boost filtering. Furthermore, the generality of the implementation makes it appropriate for very complex surface models, for example, those constructed directly from measured data.

REFERENCES

• 1: David Adalsteinsson , James A. Sethian, A fast level set method for propagating interfaces, Journal of Computational Physics, v.118 n.2, p.269-277, May 1995 [doi>10.1006/jcph.1995.1098]
• 2: Marc Alexa, Wiener Filtering of Meshes, Proceedings of the Shape Modeling International 2002 (SMI'02), p.51, May 17-22, 2002
• 3: Ballester, C., Bertalmio, M., Caselles, V., Sapiro, G., and Verdera, J. 2001. Filling-in by joint interpolation of vector fields and gray levels. IEEE Trans. Image Process. 10, 8 (Aug.), 1200--1211.
• 4: Marcelo Bertalmío , Li-Tien Cheng , Stanley Osher , Guillermo Sapiro, Variational problems and partial differential equations on implicit surfaces, Journal of Computational Physics, v.174 n.2, p.759-780, December 10, 2001 [doi>10.1006/jcph.2001.6937]
• 5: Burchard, P. 2002. Total variation geometry 1: Concepts and motivation. Tech. rep. UCLA CAM-02-01. University of California, Los Angeles, Los Angeles, CA.
• 6: Chopp, D. L. and Sethian, J. A. 1999. Motion by intrinsic laplacian of curvature. Interfaces Free Bound. 1, 1--18.
• 7: 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
• 8: Brian Curless , Marc Levoy, A volumetric method for building complex models from range images, Proceedings of the 23rd annual conference on Computer graphics and interactive techniques, p.303-312, August 1996 [doi>10.1145/237170.237269]
• 9: 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]
• 10: Desbrun, M., Meyer, M., Schröder, P., and Barr, A. H. 2000. Anisotropic feature-preserving denoising of height fields and bivariate data. In Proceedings of Graphics Interface. 145--152.
• 11: DoCarmo, M. P. 1976. Differential Geometry of Curves and Surfaces. Prentice Hall, Englewood Cliffs, NJ.
• 12: Eberly, D. 1996. Ridges in Image and Data Analysis. Kluwer Academic Publishers, Norwell, MA.
• 13: Rafael C. Gonzalez , Richard E. Woods, Digital Image Processing, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1992
• 14: 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]
• 15: Mark Halstead , Michael Kass , Tony DeRose, Efficient, fair interpolation using Catmull-Clark surfaces, Proceedings of the 20th annual conference on Computer graphics and interactive techniques, p.35-44, September 1993 [doi>10.1145/166117.166121]
• 16: 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]
• 17: 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
• 18: Liana M. Lorigo , Olivier D. Faugeras , W. Eric L. Grimson , Renaud Keriven , Ron Kikinis , Carl-Fredrik Westin, Co-dimension 2 Geodesic Active Contours for MRA Segmentation, Proceedings of the 16th International Conference on Information Processing in Medical Imaging, p.126-139, June 28-July 02, 1999
• 19: Ravikanth Malladi , James A. Sethian , Baba C. Vemuri, Shape Modeling with Front Propagation: A Level Set Approach, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.17 n.2, p.158-175, February 1995 [doi>10.1109/34.368173]
• 20: Henry P. Moreton , Carlo H. Séquin, Functional optimization for fair surface design, Proceedings of the 19th annual conference on Computer graphics and interactive techniques, p.167-176, July 1992
• 21: Yutaka Ohtake , Alexander G. Belyaev , Ilia A. Bogaevski, Polyhedral Surface Smoothing with Simultaneous Mesh Regularization, Proceedings of the Geometric Modeling and Processing 2000, p.229, April 10-12, 2000
• 22: Stanley Osher , James A. Sethian, Fronts propagating with curvature-dependent speed: algorithms based on Hamilton-Jacobi formulations, Journal of Computational Physics, v.79 n.1, p.12-49, Nov. 1988 [doi>10.1016/0021-9991(88)90002-2]
• 23: Danping Peng , Barry Merriman , Stanley Osher , Hongkai Zhao , Myungjoo Kang, A PDE-based fast local level set method, Journal of Computational Physics, v.155 n.2, p.410-438, Nov. 1, 1999 [doi>10.1006/jcph.1999.6345]
• 24: Perona, P. 1998. Orientation diffusion. IEEE Trans. Image Processing 7, 3, 457--467.
• 25: P. Perona , J. Malik, Scale-Space and Edge Detection Using Anisotropic Diffusion, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.12 n.7, p.629-639, July 1990 [doi>10.1109/34.56205]
• 26: Polden, A. 1997. Compact surfaces of least total curvature. Tech. rep., University of Tubingen, Tubingen, Germany.
• 27: Leonid I. Rudin , Stanley Osher , Emad Fatemi, Nonlinear total variation based noise removal algorithms, Physica D, v.60 n.1-4, p.259-268, Nov. 1, 1992
• 28: G. Sapiro, Geometric partial differential equations in image analysis: past, present, and future, Proceedings of the 1995 International Conference on Image Processing (Vol. 3)-Volume 3, p.3001, October 23-26, 1995
• 29: Robert Schneider , Leif Kobbelt, Generating Fair Meshes with G1 Boundary Conditions, Proceedings of the Geometric Modeling and Processing 2000, p.251, April 10-12, 2000
• 30: Schneider, R. and Kobbelt, L. 2001. Geometric fairing of irregular meshes for free-form surface design. Comput. Aid. Geom. Des. 18, 359--379.
• 31: Sethian, J. A. 1999. Level Set Methods and Fast Marching Methods Evolving Interfaces in Computational Geometry, Fluid Mechanics, Computer Vision, and Materials Science. Cambridge University Press, Cambridge, U.K.
• 32: 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]
• 33: 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
• 34: 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]
• 35: Taubin, G. 2001. Linear anisotropic mesh filtering. Tech. rep. RC22213. IBM Research Division, Yorktown Heights, NY.
• 36: Gabriel Taubin , Tong Zhang , Gene H. Golub, Optimal Surface Smoothing as Filter Design, Proceedings of the 4th European Conference on Computer Vision-Volume I, p.283-292, April 15-18, 1996
• 37: William Welch , Andrew Witkin, Variational surface modeling, Proceedings of the 19th annual conference on Computer graphics and interactive techniques, p.157-166, July 1992
• 38: 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]
• 39: Whitaker, R. T. 1994. Volumetric deformable models: Active blobs. In Visualization in Biomedical Computing, R. A. Robb, Ed. SPIE Press, Bellingham, WA. 122--134.
• 40: Ross T. Whitaker, A Level-Set Approach to 3D Reconstruction from Range Data, International Journal of Computer Vision, v.29 n.3, p.203-231, Sept. 1998 [doi>10.1023/A:1008036829907]

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

General Terms:
Algorithms, Theory

Keywords:
Surface fairing, anisotropic diffusion, geometric surface processing, high-boost filtering, level sets