Journal Home > Volume 3 , Issue 2
Computational Visual Media 2017, 3(2): 147-160 https://doi.org/10.1007/s41095-016-0071-3
Research Article | Open Access | Issue | Published: 02 March 2017

Feature-aligned segmentation using correlation clustering

Show Author's Information Yixin Zhuang1( ),  Hang Dou2,  Nathan Carr3,  Tao Ju2( )
National Digital Switching System Engineering & Technological Research Center, Zhengzhou, 450001, China.
Washington University in St. Louis, St. Louis, 63130, USA.
Adobe, San Francisco, 94103, USA.
Keywords:
mesh segmentation, correlation clustering (CC), feature lines
Cite this article:
Zhuang Y, Dou H, Carr N, et al. Feature-aligned segmentation using correlation clustering. Computational Visual Media, 2017, 3(2): 147-160. https://doi.org/10.1007/s41095-016-0071-3
Download citation
EndNote(RIS)
BibTeX

578

Views

17

Downloads

Citations

12

Crossref

N/A

WoS

14

Scopus

4

CSCD

Abstract Full text Electronic supplementary material About this article

We present an algorithm for segmenting a mesh into patches whose boundaries are aligned with prominent ridge and valley lines of the shape. Our key insight is that this problem can be formulated as correlation clustering (CC), a graph partitioning problem originating from the data mining community. The formulation lends two unique advantages to our method over existing segmentation methods. First, since CC is non-parametric, our method has few parameters to tune. Second, as CC is governed by edge weights in the graph, our method offers users direct and local control over the segmentation result. Our technical contributions include the construction of the weighted graph on which CC is defined, a strategy for rapidly computing CC on this graph, and an interactive tool for editing the segmentation. Our experiments show that our method produces qualitatively better segmentations than existing methods on a wide range of inputs.


menu
Abstract
Full text
Outline
Electronic supplementary material
About this article

Feature-aligned segmentation using correlation clustering

Show Author's information Yixin Zhuang1( ), Hang Dou2, Nathan Carr3, Tao Ju2( )
National Digital Switching System Engineering & Technological Research Center, Zhengzhou, 450001, China.
Washington University in St. Louis, St. Louis, 63130, USA.
Adobe, San Francisco, 94103, USA.

Abstract

We present an algorithm for segmenting a mesh into patches whose boundaries are aligned with prominent ridge and valley lines of the shape. Our key insight is that this problem can be formulated as correlation clustering (CC), a graph partitioning problem originating from the data mining community. The formulation lends two unique advantages to our method over existing segmentation methods. First, since CC is non-parametric, our method has few parameters to tune. Second, as CC is governed by edge weights in the graph, our method offers users direct and local control over the segmentation result. Our technical contributions include the construction of the weighted graph on which CC is defined, a strategy for rapidly computing CC on this graph, and an interactive tool for editing the segmentation. Our experiments show that our method produces qualitatively better segmentations than existing methods on a wide range of inputs.

Keywords: mesh segmentation, correlation clustering (CC), feature lines

References(53)

[1]
F. Cole,; K. Sanik,; D. DeCarlo,; A. Finkelstein,; T. Funkhouser,; S. Rusinkiewicz,; M. Singh, How well do line drawings depict shape? ACM Transactions on Graphics Vol. 28, No. 3, Article No. 28, 2009.
DOI Google Scholar
[2]
R. Mehra,; Q. Zhou,; J. Long,; A. Sheffer,; A. A. Gooch,; N. J. Mitra, Abstraction of man-made shapes. ACM Transactions on Graphics Vol. 28, No. 5, Article No. 137, 2009.
DOI Google Scholar
[3]
A. Gehre,; I. Lim,; L. Kobbelt, Adapting feature curve networks to a prescribed scale. Computer Graphics Forum Vol. 35, No. 2, 319-330, 2016.
DOI Google Scholar
[4]
R. Gal,; O. Sorkine,; N. J. Mitra,; D. Cohen-Or, iWIRES: An analyze-and-edit approach to shape manipulation. ACM Transactions on Graphics Vol. 28, No. 3, Article No. 33, 2009.
DOI Google Scholar
[5]
D.-M. Yan,; W. Wang,; Y. Liu,; Z. Yang, Variational mesh segmentation via quadric surface fitting. Computer-Aided Design Vol. 44, No. 11, 1072-1082, 2012.
DOI Google Scholar
[6]
M. Nieser,; C. Schulz,; K. Polthier, Patch layout from feature graphs. Computer-Aided Design Vol. 42, No. 3, 213-220, 2010.
DOI Google Scholar
[7]
J. Mitani,; H. Suzuki, Making papercraft toys from meshes using strip-based approximate unfolding. ACM Transactions on Graphics Vol. 23, No. 3, 259-263, 2004.
DOI Google Scholar
[8]
Y. Cao,; D.-M. Yan,; P. Wonka, Patch layout generation by detecting feature networks. Computers & Graphics Vol. 46, 275-282, 2015.
DOI Google Scholar
[9]
N. Bansal,; A. Blum,; S. Chawla, Correlation clustering. Machine Learning Vol. 56, No. 1, 89-113, 2004.
DOI Google Scholar
[10]
M. Keuper,; E. Levinkov,; N. Bonneel,; G. Lavoue,; T. Brox,; B. Andres, Efficient decomposition of image and mesh graphs by lifted multicuts. In: Proceedings of the IEEE International Conference on Computer Vision, 1751-1759, 2015.
DOI
[11]
A. Shamir, A survey on mesh segmentation techniques. Computer Graphics Forum Vol. 27, No. 6, 1539-1556, 2008.
DOI Google Scholar
[12]
M. Attene,; S. Katz,; M. Mortara,; G. Patane,; M. Spagnuolo,; A. Tal, Mesh segmentation—A comparative study. In: Proceedings of the IEEE International Conference on Shape Modeling and Applications, 7, 2006.
[13]
S. Katz,; A. Tal, Hierarchical mesh decomposition using fuzzy clustering and cuts. ACM Transactions on Graphics Vol. 22, No. 3, 954-961, 2003.
DOI Google Scholar
[14]
O. K.-C. Au,; Y. Zheng,; M. Chen,; P. Xu,; C.-L. Tai, Mesh segmentation with concavity-aware fields. IEEE Transactions on Visualization and Computer Graphics Vol. 18, No. 7, 1125-1134, 2012.
DOI Google Scholar
[15]
J.-M. Lien,; N. M. Amato, Approximate convex decomposition of polyhedra and its applications. Computer Aided Geometric Design Vol. 25, No. 7, 503-522, 2008.
DOI Google Scholar
[16]
S. Asafi,; A. Goren,; D. Cohen-Or, Weak convex decomposition by lines-of-sight. Computer Graphics Forum Vol. 32, No. 5, 23-31, 2013.
DOI Google Scholar
[17]
R. Fan,; X. Jin,; C. C. L. Wang, Multiregion segmentation based on compact shape prior. IEEE Transactions on Automation Science and Engineering Vol. 12, No. 3, 1047-1058, 2015.
DOI Google Scholar
[18]
L. Shapira,; A. Shamir,; D. Cohen-Or, Consistent mesh partitioning and skeletonisation using the shape diameter function. The Visual Computer Vol. 24, No. 4, 249-259, 2008.
DOI Google Scholar
[19]
H. Zhang,; R. Liu, Mesh segmentation via recursive and visually salient spectral cuts. In: Proceedings of Vision, Modeling, and Visualization, 429-436, 2005.
[20]
Y. Lee,; S. Lee,; A. Shamir,; D. Cohen-Or,; H.-P. Seidel, Mesh scissoring with minima rule and part salience. Computer Aided Geometric Design Vol. 22, No. 5, 444-465, 2005.
DOI Google Scholar
[21]
E. Kalogerakis,; A. Hertzmann,; K. Singh, Learning 3D mesh segmentation and labeling. ACM Transactions on Graphics Vol. 29, No. 4, Article No. 102, 2010.
DOI Google Scholar
[22]
D. Cohen-Steiner,; P. Alliez,; M. Desbrun, Variational shape approximation. ACM Transactions on Graphics Vol. 23, No. 3, 905-914, 2004.
DOI Google Scholar
[23]
J. Wu,; L. Kobbelt, Structure recovery via hybrid variational surface approximation. Computer Graphics Forum Vol. 24, No. 3, 277-284, 2005.
DOI Google Scholar
[24]
M. Attene,; B. Falcidieno,; M. Spagnuolo, Hierarchical mesh segmentation based on fitting primitives. The Visual Computer Vol. 22, No. 3, 181-193, 2006.
DOI Google Scholar
[25]
H. Zhang,; C. Li,; L. Gao,; G. Wang, Hierarchical mesh segmentation based on quadric surface fitting. In: Proceedings of the 14th International Conference on Computer-Aided Design and Computer Graphics (CAD/Graphics), 33-40, 2015.
DOI
[26]
D. Julius,; V. Kraevoy,; A. Sheffer, D-charts: Quasi-developablemesh segmentation. Computer Graphics Forum Vol. 24, No. 3, 581-590, 2005.
DOI Google Scholar
[27]
C. Wang, Computing length-preserved free boundary for quasi-developable mesh segmentation. IEEE Transactions on Visualization and Computer Graphics Vol. 14, No. 1, 25-36, 2008.
DOI Google Scholar
[28]
A. P. Mangan,; R. T. Whitaker, Partitioning 3D surface meshes using watershed segmentation. IEEE Transactions on Visualization and Computer Graphics Vol. 5, No. 4, 308-321, 1999.
DOI Google Scholar
[29]
Y. Sun,; J. K. Paik,; A. F. Koschan,; D. L. Page,; M. A. Abidi, Triangle mesh-based edge detection and its application to surface segmentation and adaptive surface smoothing. In: Proceedings of the International Conference on Image Processing, Vol. 3, 825-828, 2002.
[30]
A. Razdan,; M. Bae, A hybrid approach to feature segmentation of triangle meshes. Computer-Aided Design Vol. 35, No. 9, 783-789, 2003.
DOI Google Scholar
[31]
G. Lavoue,; F. Dupont,; A. Baskurt, A new CAD mesh segmentation method, based on curvature tensor analysis. Computer-Aided Design Vol. 37, No. 10, 975-987, 2005.
DOI Google Scholar
[32]
H. S. Kim,; H. K. Choi,; K. H. Lee, Feature detection of triangular meshes based on tensor voting theory. Computer-Aided Design Vol. 41, No. 1, 47-58, 2009.
DOI Google Scholar
[33]
N. Gelfand,; L. J. Guibas, Shape segmentation using local slippage analysis. In: Proceedings of the Eurographics/ACM SIGGRAPH Symposium on Geometry Processing, 214-223, 2004.
DOI
[34]
Y.-K. Lai,; S.-M. Hu,; R. R. Martin,; P. L. Rosin, Rapid and effective segmentation of 3D models using random walks. Computer Aided Geometric Design Vol. 26, No. 6, 665-679, 2008.
DOI Google Scholar
[35]
S. Wang,; T. Hou,; S. Li,; Z. Su,; H. Qin, Anisotropic elliptic PDEs for feature classification. IEEE Transactions on Visualization and Computer Graphics Vol. 19, No. 10, 1606-1618, 2013.
DOI Google Scholar
[36]
B. Lévy,; S. Petitjean,; N. Ray,; J. Maillot, Least squares conformal maps for automatic texture atlas generation. ACM Transactions on Graphics Vol. 21, No. 3, 362-371, 2002.
DOI Google Scholar
[37]
A. Arasu,; C. Ré,; D. Suciu, Large-scale deduplication with constraints using dedupalog. In: Proceedings of the IEEE 25th International Conference on Data Engineering, 952-963, 2009.
DOI
[38]
B. Yang,; W. K. Cheung,; J. Liu, Community mining from signed social networks. IEEE Transactions on Knowledge and Data Engineering Vol. 19, No. 10, 1333-1348, 2007.
DOI Google Scholar
[39]
A. Ben-Dor,; R. Shamir,; Z. Yakhin, Clustering gene expression patterns. Journal of Computational Biology Vol. 6, Nos. 3–4, 281-297, 2004.
DOI Google Scholar
[40]
S. Kim,; S. Nowozin,; P. Kohli,; C. D. Yoo, Higher-order correlation clustering for image segmentation. In: Proceedings of Advances in Neural Information Processing Systems, 1530-1538, 2011.
[41]
J. Yarkony,; A. T. Ihler,; C. C. Fowlkes, Fast planar correlation clustering for image segmentation. In: Computer Vision–ECCV 2012. A. Fitzgibbon,; S. Lazebnik,; P. Perona,; Y. Sato,; C. Schmid, Eds. Springer Berlin Heidelberg, 568-581, 2012.
DOI
[42]
T. Beier,; T. Kroger,; J. H. Kappes,; U. Kothe,; F. A. Hamprecht, Cut, glue, & cut: A fast, approximate solver for multicut partitioning. In: Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, 73-80, 2014.
DOI
[43]
J. H. Kappes,; P. Swoboda,; B. Savchynskyy,; T. Hazan,; C. Schnörr, Probabilistic correlation clustering and image partitioning using perturbed multicuts. In: Scale Space and Variational Methods in Computer Vision. J.-F. Aujol,; M. Nikolova,; N. Papadakis, Eds. Springer International Publishing, 231-242, 2015.
DOI
[44]
P. Arbelaez,; M. Maire,; C. Fowlkes,; J. Malik, Contour detection and hierarchical image segmentation. IEEE Transactions on Pattern Analysis and Machine Intelligence Vol. 33, No. 5, 898-916, 2011.
DOI Google Scholar
[45]
E. D. Demaine,; D. Emanuel,; A. Fiat,; N. Immorlica, Correlation clustering in general weighted graphs. Theoretical Computer Science Vol. 361, Nos. 2–3, 172-187, 2006.
DOI Google Scholar
[46]
N. Ailon,; M. Charikar,; A. Newman, Aggregating inconsistent information: Ranking and clustering. Journal of the ACM Vol. 55, No. 5, Article No. 23, 2008.
DOI Google Scholar
[47]
S. Bagon,; M. Galun, Large scale correlation clustering optimization. arXiv preprint arXiv:1112.2903, 2011.
[48]
A. Lingas,; M. Persson,; D. Sledneu, Iterative merging heuristics for correlation clustering. International Journal of Metaheuristics Vol. 3, No. 2, 105-117, 2014.
DOI Google Scholar
[49]
F. Chierichetti,; N. Dalvi,; R. Kumar, Correlation clustering in MapReduce. In: Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 641-650, 2014.
DOI
[50]
X. Pan,; D. S. Papailiopoulos,; S. Oymak,; B. Recht,; K. Ramchandran,; M. I. Jordan, Parallel correlation clustering on big graphs. In: Proceedings of Advances in Neural Information Processing Systems, 82-90, 2015.
[51]
S. Yoshizawa,; A. Belyaev,; H.-P. Seidel, Fast and robust detection of crest lines on meshes. In: Proceedings of the ACM Symposium on Solid and Physical Modeling, 227-232, 2005.
DOI
[52]
Y. Zhuang,; M. Zou,; N. Carr,; T. Ju, Anisotropic geodesics for live-wire mesh segmentation. Computer Graphics Forum Vol. 33, No. 7, 111-120, 2014.
DOI Google Scholar
[53]
L. Vincent,; P. Soille, Watersheds in digital spaces: An efficient algorithm based on immersion simulations. IEEE Transactions on Pattern Analysis and Machine Intelligence Vol. 13, No. 6, 583-598, 1991.
DOI Google Scholar
File
41095_2016_71_MOESM1_ESM.wmv (70.7 MB)
Publication history
Copyright
Acknowledgements
Rights and permissions

Publication history

Revised: 24 August 2016
Accepted: 22 December 2016
Published: 02 March 2017
Issue date: June 2017

Copyright

© The Author(s) 2016

Acknowledgements

We thank Dongming Yan for providing the code from Ref. [5] for comparison. The models in this paper were obtained from AIM@SHAPE and Princeton Segmentation Benchmark. The work was supported in part by a gift from Adobe System, Inc.

Rights and permissions

This article is published with open access at Springerlink.com

The articles published in this journal are distributed under the terms of the Creative Commons Attribution 4.0 International License (http:// creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution, and reproduction in any medium, provided you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license, and indicate if changes were made.

Other papers from this open access journal are available free of charge from http://www.springer.com/journal/41095. To submit a manuscript, please go to https://www. editorialmanager.com/cvmj.

Return