Qixing Huang
Abstract
We present an approach to segmenting shapes in a heterogenous shape database. Our approach segments the shapes jointly, utilizing features from multiple shapes to improve the segmentation of each. The approach is entirely unsupervised and is based on an integer quadratic programming formulation of the joint segmentation problem. The program optimizes over possible segmentations of individual shapes as well as over possible correspondences between segments from multiple shapes. The integer quadratic program is solved via a linear programming relaxation, using a block coordinate descent procedure that makes the optimization feasible for large databases. We evaluate the presented approach on the Princeton segmentation benchmark and show that joint shape segmentation significantly outperforms single-shape segmentation techniques.
- Anguelov, D., Srinivasan, P., Pang, H., Koller, D., Thrun, S., and Davis, J. 2005. The correlated correspondence algorithm for unsupervised registration of nonrigid surfaces. In Proc. Neural Information Processing Systems (NIPS), The MIT Press.Google Scholar
- Boyd, S., and Vandenberghe, L. 2004. Convex Optimization. Cambridge University Press. Google ScholarDigital Library
- Chang, W., and Zwicker, M. 2008. Automatic registration for articulated shapes. In Proc. Symposium on Geometry Processing, Eurographics Association. Google ScholarDigital Library
- Chaudhuri, S., Kalogerakis, E., Guibas, L., and Koltun, V. 2011. Probabilistic reasoning for assembly-based 3d modeling. In Proc. SIGGRAPH, ACM. Google ScholarDigital Library
- Chen, X., Golovinskiy, A., and Funkhouser, T. 2009. A benchmark for 3d mesh segmentation. In Proc. SIGGRAPH, ACM. Google ScholarDigital Library
- Golovinskiy, A., and Funkhouser, T. 2008. Randomized cuts for 3d mesh analysis. In Proc. SIGGRAPH Asia, ACM. Google ScholarDigital Library
- Golovinskiy, A., and Funkhouser, T. 2009. Consistent segmentation of 3d models. Computers & Graphics 33, 3, 262--269. Google ScholarDigital Library
- Grant, M., and Boyd, S. 2011. CVX: Matlab Software for Disciplined Convex Programming. http://www.stanford.edu/~boyd/cvx/.Google Scholar
- Kalogerakis, E., Hertzmann, A., and Singh, K. 2010. Learning 3d mesh segmentation and labeling. In Proc. SIGGRAPH, ACM. Google ScholarDigital Library
- Katz, S., and Tal, A. 2003. Hierarchical mesh decomposition using fuzzy clustering and cuts. In Proc. SIGGRAPH, ACM. Google ScholarDigital Library
- Kazhdan, M., Funkhouser, T., and Rusinkiewicz, S. 2004. Shape matching and anisotropy. In Proc. SIGGRAPH, ACM. Google ScholarDigital Library
- Kraevoy, V., Julius, D., and Sheffer, A. 2007. Model composition from interchangeable components. In Proc. Pacific Graphics, IEEE Computer Society, 129--138. Google ScholarDigital Library
- Kumar, M. P., Kolmogorov, V., and Torr, P. H. S. 2009. An analysis of convex relaxations for MAP estimation of discrete MRFs. Journal of Machine Learning Research 10, 71--106. Google ScholarDigital Library
- Osada, R., Funkhouser, T., Chazelle, B., and Dobkin, D. 2002. Shape distributions. ACM Transactions on Graphics 21, 4, 807--832. Google ScholarDigital Library
- Rand, W. M. 1971. Objective criteria for the evaluation of clustering methods. Journal of the American Statistical Association 66, 846--850.Google ScholarCross Ref
- Ren, X., and Malik, J. 2003. Learning a classification model for segmentation. In Proc. IEEE International Conference on Computer Vision. Google ScholarDigital Library
- Shamir, A. 2008. A survey on mesh segmentation techniques. Computer Graphics Forum 27, 1539--1556.Google ScholarCross Ref
- Shapira, L., Shamir, A., and Cohen-Or, D. 2008. Consistent mesh partitioning and skeletonisation using the shape diameter function. The Visual Computer 24, 4, 249--259. Google ScholarDigital Library
- Shapira, L., Shalom, S., Shamir, A., Cohen-Or, D., and Zhang, H. 2010. Contextual part analogies in 3d objects. International Journal of Computer Vision 89, 309--326. Google ScholarDigital Library
- Shi, J., and Malik, J. 2000. Normalized cuts and image segmentation. IEEE Transactions on Pattern Analysis and Machine Intelligence 22, 8, 888--905. Google ScholarDigital Library
- Shotton, J., Winn, J., Rother, C., and Criminisi, A. 2009. Textonboost for image understanding: multi-class object recognition and segmentation by jointly modeling texture, layout, and context. International Journal of Computer Vision 81, 2--23. Google ScholarDigital Library
- Sidi, O., van Kaick, O., Kleiman, Y., Zhang, H., and Cohen-Or, D. 2011. Unsupervised co-segmentation of a set of shapes via descriptor-space spectral clustering. ACM Trans. Graph. 30 (December), 126:1--126:9. Google ScholarDigital Library
- Simari, P., Nowrouzezahrai, D., Kalogerakis, E., and Singh, K. 2009. Multi-objective shape segmentation and labeling. Computer Graphics Forum 28, 5, 1415--1425. Google ScholarDigital Library
- Sontag, D., and Jaakkola, T. 2009. Tree block coordinate descent for MAP in graphical models. Journal of Machine Learning Research - Proceedings Track 5, 544--551.Google Scholar
- Wainwright, M. J., Jaakkola, T., and Willsky, A. S. 2005. MAP estimation via agreement on trees: message-passing and linear programming. IEEE Transactions on Information Theory 51, 11, 3697--3717. Google ScholarDigital Library
- Xu, K., Li, H., Zhang, H., Cohen-Or, D., Xiong, Y., and Cheng, Z.-Q. 2010. Style-content separation by anisotropic part scales. ACM Trans. Graph. 29 (December), 184:1--184:10. Google ScholarDigital Library
Index Terms
- Joint shape segmentation with linear programming
Recommendations
Joint shape segmentation with linear programming
SA '11: Proceedings of the 2011 SIGGRAPH Asia ConferenceWe present an approach to segmenting shapes in a heterogenous shape database. Our approach segments the shapes jointly, utilizing features from multiple shapes to improve the segmentation of each. The approach is entirely unsupervised and is based on an ...
Transformation of a multi-choice linear programming problem
The aim of this paper is to transform a multi-choice linear programming problem to a standard mathematical programming problem where the right hand side goals of some constraints are 'multi-choice' in nature. For each of the constraint there may exist ...
A simplex algorithm for piecewise-linear programming I: Derivation and proof
The simplex method for linear programming can be extended to permit the minimization of any convex separable piecewise-linear objective, subject to linear constraints. This three-part paper develops and analyzes a general, computationally practical ...
Comments