| | This Article | |
| |
| |
| | Share | |
| |
| |
| | Bibliographic References | |
| |
| |
| | Add to: | |
| |
 Digg
 Furl
 Spurl
 Blink
 Simpy
 Google
 Del.icio.us
 Y!MyWeb
| |
| | Search | |
| |
| |
| | |
Three-Dimensional Surface Mesh Segmentation Using Curvedness-Based Region Growing Approach
December 2007 (vol. 29 no. 12)
pp. 2195-2204
A new parameter-free graph morphology based segmentation algorithm is proposed to address the problem of partitioning a 3D triangular mesh into disjoint sub- eshes that correspond to the physical parts of the underlying object. Curvedness, which is a rotation and translation invariant shape descriptor, is computed at every vertex in the input triangulation. Iterative graph dilation and morphological filtering of the outlier curvedness values result in multiple, disjoint, maximally connected sub-meshes such that each sub-mesh contains a set of vertices with similar curvedness values, and vertices in disjoint sub-meshes have significantly different curvedness values. Experimental evaluations using the triangulations of a number of complex objects demonstrate the robustness and the efficiency of the proposed algorithm and the results prove that it compares well with a number of state-of-the-art mesh segmentation algorithms.
[1] A.P. Mangan and R.T. Whitaker, “Partitioning 3D Surface Meshes Using Watershed Segmentation,” IEEE Trans. Visualization and Computer Graphics, vol. 5, no. 4, pp. 308-321, Oct.-Dec. 1999.
[2] D.L. Page, A.F. Koschan, and M.A. Abidi, “Perception-Based 3D Triangle Mesh Segmentation Using Fast Marching Watersheds,” Proc. IEEE Conf. Computer Vision and Pattern Recognition, vol. 2, pp.27-32, 2003.
[3] C. Rössl, L. Kobbelt, and H.P. Seidel, “Extraction of Feature Lines on Triangulated Surfaces Using Morphological Operators,” Proc. AAAI Symp. Smart Graphics, pp. 71-75, 2000.
[4] M. Suk and S.M. Bhandarkar, Three-Dimensional Object Recognition from Range Images. Springer, 1992.
[5] C. Dorai and A.K. Jain, “COSMOS: A Representation Scheme for 3D Free-Form Objects,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 19, no. 10, pp. 1115-1130, Oct. 1997.
[6] Math. Morphology in Image Processing, E.R. Dougherty, ed. first ed., 1993.
[7] H. Heijmans, P. Nacken, A. Toet, and L. Vincent, “Graph Morphology,” J. Visual Comm. and Image Representation, vol. 3, no. 1, pp. 24-38, 1992.
[8] L. Vincent, “Graphs and Mathematical Morphology,” Signal Processing, vol. 16, pp. 365-388, 1989.
[9] N. Dyn, K. Hormann, S.J. Kim, and D. Levin, “Optimizing 3D Triangulations Using Discrete Curvature Analysis,” Math. Methods for Curves and Surfaces, pp. 135-146, 2000.
[10] J.J. Koenderink, Solid Shape. MIT Press, 1990.
[11] J.J. Koenderink and A.J. Van Doorn, “Surface Shape and Curvature Scales,” Image and Vision Computing, vol. 8, pp. 557-565, 1992.
[12] C.C. Pu and F.Y. Shih, “Threshold Decomposition of Gray-Scale Soft Morphology into Binary Soft Morphology,” CVGIP: Graphical Models and Image Processing, vol. 57, no. 6, pp. 522-526, 1995.
[13] P. Kuosmanen and J. Astola, “Soft Morphological Filtering,” J.Math. Imaging and Vision, vol. 5, no. 3, pp. 231-262, 1995.
[14] J.M. Reinhardt and W.E. Higgins, “Efficient Morphological Shape Representation,” IEEE Trans. Image Processing, vol. 5, no. 1, pp. 89-101, 1996.
[15] C.D. Ruberto and A.G. Dempster, “Attributed Skeleton Graphs Using Mathematical Morphology,” IEEE Electronics Letters, vol. 37, no. 22, 2001.
[16] I. Pitas and A.N. Venetsanopoulos, “Morphological Shape Decomposition,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 12, no. 1, pp. 38-45, Jan. 1990.
[17] T.H. Cormen, C.E. Leiserson, and R.L. Rivest, Introduction to Algorithms, MIT Electrical Eng. and Computer Science, 1994.
[18] R.C. Gonzalez and R.E. Woods, Digital Image Processing, second ed. Prentice Hall, 2001.
[19] A. Guéziec, G. Taubin, F. Lazarus, and B. Horn, “Cutting and Stitching: Converting Sets of Polygons to Manifold Surfaces,” IEEE Trans. Visualization and Computer Graphics, vol. 7, no. 2, 2001.
[20] Y. Shinagawa and T.L. Kunii, “Constructing a Reeb Graph from Cross Sections,” IEEE Computer Graphics and Applications, pp. 44-51, 1991.
[21] M. Mortara and G. Patanè, “Affine-Invariant Skeleton of 3D Shapes,” Proc. Shape Modeling Int'l, pp. 1-8, 2002.
[22] D. Bespalov, A. Shokoufandeh, W.C. Regli, and W. Sun, “Scale-Space Representation of 3D Models and Topological Matching,” Proc. Eighth ACM Symp. Solid Modeling and Applications, pp. 208-215, 2003.
[23] S. Takahashi, Y. Shinagawa, and T.L. Kunii, “A Feature-Based Approach for Smooth Surfaces,” Proc. Fourth ACM Symp. Solid Modeling and Applications, pp. 97-110, 1997.
[24] E.C. Sherbrooke, N.M. Patrikalakis, and E. Brisson, “An Algorithm for Medial Axis Transform of 3D Polyhedral Solids,” IEEE Trans. Visualization and Computer Graphics, vol. 2, no. 1, Jan.-Apr. 1996.
[25] K. Siddiqi and B.B. Kimia, “Parts of Visual Form: Computational Aspects,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 17, no. 3, pp. 239-251, Mar. 1995.
[26] M. Werthheimer, “Laws of Organization in Perceptual Forms,” A Sourcebook of Gestalt Psychology, pp. 71-88, 1950.
[27] K. Wu and M.D. Levine, “3D Part Segmentation Using Simulated Electrical Charge Distributions,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 19, no. 11, Nov. 1997.
[28] R.O. Duda, P.E. Hart, and D.G. Stork, Pattern Classification. Wiley-InterScience, 2001.
[29] D. Scott, “On Optimal and Data-Based Histograms,” Biometrika, vol. 66, pp. 605-610, 1979.
[30] W.J. Schroeder, J.A. Zarge, and W.E. Lorenson, “Decimation of Triangular Meshes,” Proc. ACM SIGGRAPH '92, pp. 65-70, 1992.
[31] M. Alexa, J. Behr, D. Cohen-Or, S. Fleishman, D. Levin, and C.T. Silva, “Computing and Rendering Point Set Surfaces,” IEEE Trans. Visualization and Computer Graphics, vol. 9, no. 1, pp. 3-15, Jan.-Apr. 2003.
[32] A. Pichler, R.B. Fisher, and M. Vincze, “Decomposition of Range Images Using Markov Random Fields,” Proc. IEEE Int'l Conf. Image Processing, pp. 1205-1208, 2004.
[33] S. Katz and A. Tal, “Hierarchical Mesh Decomposition Using Fuzzy Clustering and Cuts,” ACM Trans. Graphics, vol. 22, pp. 954-961, 2003.
[34] X. Li, T.W. Toon, T.S. Tan, and Z. Huang, “Decomposing Polygon Meshes for Interactive Applications,” Proc. Symp. Interactive 3D Graphics, pp. 35-42, 2001.
Index Terms:
mesh segmentation, shape descriptor, curvedness, graph morphology
Citation:
Anupama Jagannathan, Eric. L. Miller, "Three-Dimensional Surface Mesh Segmentation Using Curvedness-Based Region Growing Approach," IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 29, no. 12, pp. 2195-2204, June 2007, doi:10.1109/TPAMI.2007.1125
