“Coupled segmentation and similarity detection for architectural models”

  • ©Ilke Demir, Daniel G. Aliaga, and Bedrich Benes




    Coupled segmentation and similarity detection for architectural models

Session/Category Title: Reconstruction & Analysis




    Recent shape retrieval and interactive modeling algorithms enable the re-use of existing models in many applications. However, most of those techniques require a pre-labeled model with some semantic information. We introduce a fully automatic approach to simultaneously segment and detect similarities within an existing 3D architectural model. Our framework approaches the segmentation problem as a weighted minimum set cover over an input triangle soup, and maximizes the repetition of similar segments to find a best set of unique component types and instances. The solution for this set-cover formulation starts with a search space reduction to eliminate unlikely combinations of triangles, and continues with a combinatorial optimization within each disjoint subspace that outputs the components and their types. We show the discovered components of a variety of architectural models obtained from public databases. We demonstrate experiments testing the robustness of our algorithm, in terms of threshold sensitivity, vertex displacement, and triangulation variations of the original model. In addition, we compare our components with those of competing approaches and evaluate our results against user-based segmentations. We have processed a database of 50 buildings, with various structures and over 200K polygons per building, with a segmentation time averaging up to 4 minutes.


    1. Agathos, A., Pratikakis, I., Perantonis, S., and Sapidis, N. S. 2009. Protrusion-oriented 3d mesh segmentation. Vis. Comput. 26, 1, 63–81. Google ScholarDigital Library
    2. Attene, M., Falcidieno, B., and Spagnuolo, M. 2006. Hierarchical mesh segmentation based on fitting primitives. Vis. Comput. 22, 3, 181–193. Google ScholarDigital Library
    3. Berner, A., Bokeloh, M., Wand, M., Schilling, A., and Seidel, H.-P. 2008. A graph-based approach to symmetry detection. In Proc. of the IEEE VGTC Conference on Point-Based Graphics, Eurographics Association, SPBG’08, 1–8. Google ScholarDigital Library
    4. Bokeloh, M., Wand, M., and Seidel, H.-P. 2010. A connection between partial symmetry and inverse procedural modeling. ACM Trans. Graph. 29, 4 (July), 104:1–104:10. Google ScholarDigital Library
    5. Bokeloh, M., Wand, M., Seidel, H.-P., and Koltun, V. 2012. An algebraic model for parameterized shape editing. ACM Trans. Graph. 31, 4 (July), 78:1–78:10. Google ScholarDigital Library
    6. Demir, I., Aliaga, D., and Benes, B. 2014. Proceduralization of buildings at city scale. In 3D Vision (3DV), 2014 2nd International Conference on, vol. 1, 456–463. Google ScholarDigital Library
    7. Gelfand, N., and Guibas, L. J. 2004. Shape segmentation using local slippage analysis. In Proc. of the Symp. on Geometry Processing, ACM, SGP ’04, 214–223. Google ScholarDigital Library
    8. Kalogerakis, E., Hertzmann, A., and Singh, K. 2010. Learning 3d mesh segmentation and labeling. ACM Trans. Graph. 29, 4 (July), 102:1–102:12. Google ScholarDigital Library
    9. Kalogerakis, E., Chaudhuri, S., Koller, D., and Koltun, V. 2012. A probabilistic model for component-based shape synthesis. ACM Trans. Graph. 31, 4 (July), 55:1–55:11. Google ScholarDigital Library
    10. Kalojanov, J., Bokeloh, M., Wand, M., Guibas, L., Seidel, H.-P., and Slusallek, P. 2012. Microtiles: Extracting building blocks from correspondences. Comp. Graph. Forum 31, 5 (Aug.), 1597–1606. Google ScholarDigital Library
    11. Korte, B., and Vygen, J. 2007. Combinatorial Optimization: Theory and Algorithms, 4th ed. Springer Publishing Company, Incorporated. Google Scholar
    12. Lin, H., Gao, J., Zhou, Y., Lu, G., Ye, M., Zhang, C., Liu, L., and Yang, R. 2013. Semantic decomposition and reconstruction of residential scenes from lidar data. ACM Trans. Graph., 32, 4. Google ScholarDigital Library
    13. Lipman, Y., Chen, X., Daubechies, I., and Funkhouser, T. 2010. Symmetry factored embedding and distance. ACM Trans. Graph. 29, 4 (July), 103:1–103:12. Google ScholarDigital Library
    14. Mitra, N. J., Guibas, L. J., and Pauly, M. 2006. Partial and approximate symmetry detection for 3d geometry. ACM Trans. Graph. 25, 3 (July), 560–568. Google ScholarDigital Library
    15. Nan, L., Sharf, A., Zhang, H., Cohen-Or, D., and Chen, B. 2010. Smartboxes for interactive urban reconstruction. ACM Trans. Graph., 29, 4, Article 93. Google ScholarDigital Library
    16. Pauly, M., Mitra, N. J., Wallner, J., Pottmann, H., and Guibas, L. J. 2008. Discovering structural regularity in 3d geometry. ACM Trans. Graph. 27, 3 (Aug.), 43:1–43:11. Google ScholarDigital Library
    17. Schindler, F., and Förstner, W. 2011. Fast Marching for Robust Surface Segmentation. In LNCS, Photogrammetric Image Analysis. Google ScholarDigital Library
    18. Shamir, A. 2008. A survey on mesh segmentation techniques. Comput. Graph. Forum 27, 6, 1539–1556.Google ScholarCross Ref
    19. Shapira, L., Shamir, A., and Cohen-Or, D. 2008. Consistent mesh partitioning and skeletonisation using the shape diameter function. Vis. Comput. 24, 4 (Mar.), 249–259. Google ScholarDigital Library
    20. Simari, P., Kalogerakis, E., and Singh, K. 2006. Folding meshes: Hierarchical mesh segmentation based on planar symmetry. In Proc. of the SGP, 111–119. Google ScholarDigital Library
    21. Toshev, A., Mordohai, P., and Taskar, B. 2010. Detecting and parsing architecture at city scale from range data. In Computer Vision and Pattern Recognition (CVPR), 2010 IEEE Conference on, 398–405.Google Scholar
    22. Wu, F., Yan, D.-M., Dong, W., Zhang, X., and Wonka, P. 2013. Inverse procedural modeling of facade layouts. CoRR abs/1308.0419.Google Scholar
    23. Zhang, H., Xu, K., Jiang, W., Lin, J., Cohen-Or, D., and Chen, B. 2013. Layered analysis of irregular facades via symmetry maximization. ACM Trans. Graph., 32, 4, 104:1–104:10. Google ScholarDigital Library
    24. Zheng, Y., Fu, H., Cohen-Or, D., Au, O. K.-C., and Tai, C.-L. 2011. Component-wise controllers for structure-preserving shape manipulation. Comput. Graph. Forum 30, 2, 563–572.Google ScholarCross Ref

ACM Digital Library Publication:

Overview Page: