Ridge-valley lines on meshes via implicit surface fitting

ABSTRACT

We propose a simple and effective method for detecting view-and scale-independent ridge-valley lines defined via first- and second-order curvature derivatives on shapes approximated by dense triangle meshes. A high-quality estimation of high-order surface derivatives is achieved by combining multi-level implicit surface fitting and finite difference approximations. We demonstrate that the ridges and valleys are geometrically and perceptually salient surface features, and, therefore, can be potentially used for shape recognition, coding, and quality evaluation purposes.

REFERENCES

• 1: BELYAEV, A. G., ANOSHKINA, E. V., AND KUNII, T. L. 1997. Ridges, ravines, and singularities. In A. T. Fomenko, and T. L. Kunii, Topological Modeling for Visualization, Springer, 375--383. Chapter 18.
• 2: 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]
• 3: F. Cazals , M. Pouget, Estimating differential quantities using polynomial fitting of osculating jets, Proceedings of the 2003 Eurographics/ACM SIGGRAPH symposium on Geometry processing, June 23-25, 2003, Aachen, Germany
• 4: David Cohen-Steiner , Jean-Marie Morvan, Restricted delaunay triangulations and normal cycle, Proceedings of the nineteenth annual symposium on Computational geometry, June 08-10, 2003, San Diego, California, USA [doi>10.1145/777792.777839]
• 5: Doug DeCarlo , Adam Finkelstein , Szymon Rusinkiewicz , Anthony Santella, Suggestive contours for conveying shape, ACM Transactions on Graphics (TOG), v.22 n.3, July 2003
• 6: Michael S. Floater , Armin Iske, Multistep scattered data interpolation using compactly supported radial basis functions, Journal of Computational and Applied Mathematics, v.73 n.1-2, p.65-78, Oct. 5, 1996 [doi>10.1016/0377-0427(96)00035-0]
• 7: Jack Goldfeather , Victoria Interrante, A novel cubic-order algorithm for approximating principal direction vectors, ACM Transactions on Graphics (TOG), v.23 n.1, p.45-63, January 2004 [doi>10.1145/966131.966134]
• 8: Ulf Grenander , Michael I. Miller, Computational anatomy: an emerging discipline, Quarterly of Applied Mathematics, v.LVI n.4, p.617-694, Dec. 1998
• 9: GUMHOLD, S., WANG, X., AND MCLEOD, R. 2001. Feature extraction from point clouds. In Proc. 10th International Meshing Roundtable, 293--305.
• 10: Peter W. Hallinan , Gaile G. Gordon , A. L. Yuille , Peter Giblin , David Mumford, Two- and three-dimensional patterns of the face, A. K. Peters, Ltd., Natick, MA, 1999
• 11: M. Hosaka, Modeling of curves and surfaces in CAD/CAM, Springer-Verlag New York, Inc., New York, NY, 1992
• 12: Andreas Hubeli , Markus Gross, Multiresolution feature extraction for unstructured meshes, Proceedings of the conference on Visualization '01, October 21-26, 2001, San Diego, California
• 13: ISKE, A., AND LEVESLEY, J. 2002. Multilevel scattered data approximation by adaptive domain decomposition. Tech. Rep. TUM-M0208, Technische Universität München.
• 14: KENT, J. T., MARDIA, K. V., AND WEST, J. 1996. Ridge curves and shape analysis. In The British Machine Vision Conference 1996, 43--52.
• 15: Jan J. Koenderink, Solid shape, MIT Press, Cambridge, MA, 1990
• 16: LITTLE, J. J., AND SHI, P. 2001. Structural lines, TINs and DEMs. Algorithmica 30, 2, 243--263.
• 17: Antonio M. López , Felipe Lumbreras , Joan Serrat, Creaseness from Level Set Extrinsic Curvature, Proceedings of the 5th European Conference on Computer Vision-Volume II, p.156-169, June 02-06, 1998
• 18: Kwan-Liu Ma , Victoria Interrante, Extracting feature lines from 3D unstructured grids, Proceedings of the 8th conference on Visualization '97, p.285-ff., October 18-24, 1997, Phoenix, Arizona, United States
• 19: Stephane Mallat , Sifen Zhong, Characterization of Signals from Multiscale Edges, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.14 n.7, p.710-732, July 1992 [doi>10.1109/34.142909]
• 20: MEYER, M., DESBRUN, M., SCHRÖDER, P., AND BARR, A. H. 2003. Discrete differential-geometry operators for triangulated 2-manifolds. In Visualization and Mathematics III, Springer, H.-C. Hege and K. Polthier, Eds., 35--58.
• 21: MONGA, O., BENAYOUN, S., AND FAUGERAS, O. 1992. From partial derivatives of 3-D density images to ridge lines. In Proc. CVPR'92, IEEE, 354--359.
• 22: Yutaka Ohtake , Alexander Belyaev , Marc Alexa , Greg Turk , Hans-Peter Seidel, Multi-level partition of unity implicits, ACM Transactions on Graphics (TOG), v.22 n.3, July 2003
• 23: Yutaka Ohtake , Alexander Belyaev , Hans-Peter Seidel, A Multi-scale Approach to 3D Scattered Data Interpolation with Compactly Supported Basis Functions, Proceedings of the Shape Modeling International 2003, p.153, May 12-15, 2003
• 24: D. L. Page , Y. Sun , A. F. Koschan , J. Paik , M. A. Abidi, Normal vector voting: crease detection and curvature estimation on large, noisy meshes, Graphical Models, v.64 n.3/4, p.199-229, May/July 2002 [doi>10.1006/gmod.2002.0574]
• 25: PAULY, M., KEISER, R., AND GROSS, M. 2003. Multi-scale feature extraction on point-sampled models. Computer Graphics Forum 22, 3, 281--289. Eurographics 2003 issue.
• 26: Xavier Pennec , Nicholas Ayache , Jean-Philippe Thirion, Landmark-based registration using features identified through differential geometry, Handbook of medical imaging, Academic Press, Inc., Orlando, FL, 2000
• 27: PORTEOUS, I. R. 1994. Geometric Differentiation for the Intelligence of Curves and Surfaces. Cambridge University Press, Cambridge.
• 28: STYLIANOU, G., AND FARIN, G. 2003. Crest lines extraction from 3D triangulated meshes. In Hierarchical and Geometrical Methods in Scientific Visualization, Springer, G. Farin, B. Hamann, and H. Hagen, Eds., 269--281.
• 29: WATANABE, K., AND BELYAEV, A. G. 2001. Detection of salient curvature features on polygonal surfaces. Computer Graphics Forum 20, 3, 385--392. Eurographics 2001 issue.

INDEX TERMS

Keywords:
curvature extrema, implicit surface fitting, ridges